[clang][dataflow] Fix double visitation of nested logical operators

[li.zhe.hua]

Summary

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.

[ymandel]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

584

I'm afraid this may allow us to hide a bug. Specifically: consider if SubExpr was already evaluated to a RefenceValue and that value's StorageLocation does *not* map to a value. Then, this line will be true, but we won't want to revisit the SubExrp. Now, that may be impossible in practice, so I'm not sure how big a problem this is, but it seems safer to just use SkipPast::None and not rely on any guarantees.

That said, i see why you want the uniformity of Reference because it is used below. That said, any idea if we actually need to use Reference skipping at all? I think so -- the case of a variable or field access as sub-expression, but those probably have a cast around them anyhow, so i'm not sure those will require reference skipping.

[li.zhe.hua]

Address comments

[li.zhe.hua]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

584

I'm afraid this may allow us to hide a bug.

Ah, yes, that is definitely true.

That said, any idea if we actually need to use Reference skipping at all?

Whatever we choose, I imagine it should be kept the same as the analogous line in extendFlowCondition? I've opted to not change it for now, given my uncertainty.

[ymandel]

Thanks!

clang/lib/Analysis/FlowSensitive/Transfer.cpp

BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {
     // blocks. We try to access the value that is assigned to `SubExpr` in the
     // corresponding environment.
     if (const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr)) {
       if (auto *Val = dyn_cast_or_null<BoolValue>(
               SubExprEnv->getValue(SubExpr, SkipPast::Reference)))
         return *Val;
     }
 
+    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 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.
+      // 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;
 
     // If the value of `SubExpr` is still unknown, we create a fresh symbolic
     // boolean value for it.
     return Env.makeAtomicBoolValue();
   }
 
   const StmtToEnvMap &StmtToEnv;

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(
           const auto *BazLeftSubValVal =
               cast<ConjunctionValue>(&BazVal->getLeftSubValue());
           EXPECT_EQ(&BazLeftSubValVal->getLeftSubValue(), FooVal);
           EXPECT_EQ(&BazLeftSubValVal->getRightSubValue(), QuxVal);
 
           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) {
   std::string Code = R"(
     void target() {
       bool Foo = true;
       bool Bar = !(Foo);
       // [[p]]