From 5bbef2e3fff123293ed9c2037e2662e352bf37af Mon Sep 17 00:00:00 2001
From: Eric Li <li.zhe.hua@gmail.com>
Date: Tue, 17 May 2022 18:08:25 +0000
Subject: [PATCH] [clang][dataflow] Fix double visitation of nested logical
 operators

Sub-expressions that are logical operators are not spelled out
separately in basic blocks, so we need to manually visit them when we
encounter them. We do this in both the `TerminatorVisitor`
(conditionally) and the `TransferVisitor` (unconditionally), which can
cause cause an expression to be visited twice when the binary
operators are nested 2+ times.

This changes the visit in `TransferVisitor` to check if it has been
evaluated before trying to visit the sub-expression.

Differential Revision: https://reviews.llvm.org/D125821
---
 clang/lib/Analysis/FlowSensitive/Transfer.cpp      | 15 +++---
 .../Analysis/FlowSensitive/TransferTest.cpp        | 61 ++++++++++++++++++++++
 2 files changed, 70 insertions(+), 6 deletions(-)

diff --git a/clang/lib/Analysis/FlowSensitive/Transfer.cpp b/clang/lib/Analysis/FlowSensitive/Transfer.cpp
index 3a94434..f884065 100644
--- a/clang/lib/Analysis/FlowSensitive/Transfer.cpp
+++ b/clang/lib/Analysis/FlowSensitive/Transfer.cpp
@@ -571,12 +571,15 @@ private:
         return *Val;
     }
 
-    // Sub-expressions that are logic operators are not added in basic blocks
-    // (e.g. see CFG for `bool d = a && (b || c);`). If `SubExpr` is a logic
-    // operator, it isn't evaluated and assigned a value yet. In that case, we
-    // need to first visit `SubExpr` and then try to get the value that gets
-    // assigned to it.
-    Visit(&SubExpr);
+    if (Env.getStorageLocation(SubExpr, SkipPast::None) == nullptr) {
+      // Sub-expressions that are logic operators are not added in basic blocks
+      // (e.g. see CFG for `bool d = a && (b || c);`). If `SubExpr` is a logic
+      // operator, it may not have been evaluated and assigned a value yet. In
+      // that case, we need to first visit `SubExpr` and then try to get the
+      // value that gets assigned to it.
+      Visit(&SubExpr);
+    }
+
     if (auto *Val = dyn_cast_or_null<BoolValue>(
             Env.getValue(SubExpr, SkipPast::Reference)))
       return *Val;
diff --git a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
index db1f1cf..9819409 100644
--- a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
@@ -2467,6 +2467,67 @@ TEST_F(TransferTest, AssignFromCompositeBoolExpression) {
           EXPECT_EQ(&BazVal->getRightSubValue(), BarVal);
         });
   }
+
+  {
+    std::string Code = R"(
+      void target(bool A, bool B, bool C, bool D) {
+        bool Foo = ((A && B) && C) && D;
+        // [[p]]
+      }
+    )";
+    runDataflow(
+        Code, [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+          ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+          const Environment &Env = Results[0].second.Env;
+
+          const ValueDecl *ADecl = findValueDecl(ASTCtx, "A");
+          ASSERT_THAT(ADecl, NotNull());
+
+          const auto *AVal =
+              dyn_cast_or_null<BoolValue>(Env.getValue(*ADecl, SkipPast::None));
+          ASSERT_THAT(AVal, NotNull());
+
+          const ValueDecl *BDecl = findValueDecl(ASTCtx, "B");
+          ASSERT_THAT(BDecl, NotNull());
+
+          const auto *BVal =
+              dyn_cast_or_null<BoolValue>(Env.getValue(*BDecl, SkipPast::None));
+          ASSERT_THAT(BVal, NotNull());
+
+          const ValueDecl *CDecl = findValueDecl(ASTCtx, "C");
+          ASSERT_THAT(CDecl, NotNull());
+
+          const auto *CVal =
+              dyn_cast_or_null<BoolValue>(Env.getValue(*CDecl, SkipPast::None));
+          ASSERT_THAT(CVal, NotNull());
+
+          const ValueDecl *DDecl = findValueDecl(ASTCtx, "D");
+          ASSERT_THAT(DDecl, NotNull());
+
+          const auto *DVal =
+              dyn_cast_or_null<BoolValue>(Env.getValue(*DDecl, SkipPast::None));
+          ASSERT_THAT(DVal, NotNull());
+
+          const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+          ASSERT_THAT(FooDecl, NotNull());
+
+          const auto *FooVal = dyn_cast_or_null<ConjunctionValue>(
+              Env.getValue(*FooDecl, SkipPast::None));
+          ASSERT_THAT(FooVal, NotNull());
+
+          const auto &FooLeftSubVal =
+              cast<ConjunctionValue>(FooVal->getLeftSubValue());
+          const auto &FooLeftLeftSubVal =
+              cast<ConjunctionValue>(FooLeftSubVal.getLeftSubValue());
+          EXPECT_EQ(&FooLeftLeftSubVal.getLeftSubValue(), AVal);
+          EXPECT_EQ(&FooLeftLeftSubVal.getRightSubValue(), BVal);
+          EXPECT_EQ(&FooLeftSubVal.getRightSubValue(), CVal);
+          EXPECT_EQ(&FooVal->getRightSubValue(), DVal);
+        });
+  }
 }
 
 TEST_F(TransferTest, AssignFromBoolNegation) {
-- 
2.7.4