[clang][dataflow] Fix handling of `DeclRefExpr`s to `BindingDecl`s.

[ymandel]

Summary

The invariants around ReferenceValues are subtle (arguably, too much so). That
includes that we need to take care not to double wrap them -- in cases where we
wrap a loc in an ReferenceValue we need to be sure that the pointee isn't
already a ReferenceValue. BindingDecl introduces another situation in which
this can arise. Previously, the code did not properly handle BindingDecl,
resulting in double-wrapped values, which broke other invariants (at least, that
struct values have an AggregateStorageLocation).

This patch adjusts the interpretation of DeclRefExpr to take BindingDecl's
peculiarities into account. It also fixes the two tests which should have caught
this issue but were themselves (subtly) buggy.

[ymandel]

add clarifying comment regarding interpration of DecompositionDecl.

[ymandel]

Rebase onto HEAD

[xazax.hun]

I hope we will be able to get rid of this SkipPast thing at some point by looking at the value categories of the AST instead.

[ymandel]

In D140897#4094945, @xazax.hun wrote:

I hope we will be able to get rid of this SkipPast thing at some point by looking at the value categories of the AST instead.

Thanks! Agreed: filed issue #60444.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

static BoolValue &unpackValue(BoolValue &V, Environment &Env) {
   case Value::Kind::Biconditional:
     return unpackBinaryBoolValue<BiconditionalValue>(Env, V,
                                                      &Environment::makeIff);
   }
   llvm_unreachable("All reachable cases in switch return");
 }
 
 // Unpacks the value (if any) associated with `E` and updates `E` to the new
-// value, if any unpacking occured.
+// value, if any unpacking occured. Also, does the lvalue-to-rvalue conversion,
+// by skipping past the reference.
 static Value *maybeUnpackLValueExpr(const Expr &E, Environment &Env) {
   // FIXME: this is too flexible: it _allows_ a reference, while it should
   // _require_ one, since lvalues should always be wrapped in `ReferenceValue`.
   auto *Loc = Env.getStorageLocation(E, SkipPast::Reference);
   if (Loc == nullptr)
     return nullptr;
   auto *Val = Env.getValue(*Loc);
 
void VisitBinaryOperator(const BinaryOperator *S) {
     assert(RHS != nullptr);
 
     switch (S->getOpcode()) {
     case BO_Assign: {
       auto *LHSLoc = Env.getStorageLocation(*LHS, SkipPast::Reference);
       if (LHSLoc == nullptr)
         break;
 
-      auto *RHSVal = Env.getValue(*RHS, SkipPast::Reference);
+      // No skipping should be necessary, because any lvalues should have
+      // already been stripped off in evaluating the LValueToRValue cast.
+      auto *RHSVal = Env.getValue(*RHS, SkipPast::None);
       if (RHSVal == nullptr)
         break;
 
       // Assign a value to the storage location of the left-hand side.
       Env.setValue(*LHSLoc, *RHSVal);
 
       // Assign a storage location for the whole expression.
       Env.setStorageLocation(*S, *LHSLoc);
public:
 
   void VisitDeclRefExpr(const DeclRefExpr *S) {
     const ValueDecl *VD = S->getDecl();
     assert(VD != nullptr);
     auto *DeclLoc = Env.getStorageLocation(*VD, SkipPast::None);
     if (DeclLoc == nullptr)
       return;
 
-    if (VD->getType()->isReferenceType()) {
-      assert(isa_and_nonnull<ReferenceValue>(Env.getValue((*DeclLoc))) &&
-             "reference-typed declarations map to `ReferenceValue`s");
+    // If the value is already an lvalue, don't double-wrap it.
+    if (isa_and_nonnull<ReferenceValue>(Env.getValue(*DeclLoc))) {
+      // We only expect to encounter a `ReferenceValue` for a reference type
+      // (always) or for `BindingDecl` (sometimes). For the latter, we can't
+      // rely on type, because their type does not indicate whether they are a
+      // reference type. The assert is not strictly necessary, since we don't
+      // depend on its truth to proceed. But, it verifies our assumptions,
+      // which, if violated, probably indicate a problem elsewhere.
+      assert((VD->getType()->isReferenceType() || isa<BindingDecl>(VD)) &&
+             "Only reference-typed declarations or `BindingDecl`s should map "
+             "to `ReferenceValue`s");
       Env.setStorageLocation(*S, *DeclLoc);
     } else {
       auto &Loc = Env.createStorageLocation(*S);
       auto &Val = Env.takeOwnership(std::make_unique<ReferenceValue>(*DeclLoc));
       Env.setStorageLocation(*S, Loc);
       Env.setValue(Loc, Val);
     }
   }
if (InitExpr == nullptr) {
       if (Value *Val = Env.createValue(D.getType()))
         Env.setValue(Loc, *Val);
       return;
     }
 
     if (D.getType()->isReferenceType()) {
       // Initializing a reference variable - do not create a reference to
       // reference.
+      // FIXME: reuse the ReferenceValue instead of creating a new one.
       if (auto *InitExprLoc =
               Env.getStorageLocation(*InitExpr, SkipPast::Reference)) {
         auto &Val =
             Env.takeOwnership(std::make_unique<ReferenceValue>(*InitExprLoc));
         Env.setValue(Loc, Val);
       }
     } else if (auto *InitExprVal = Env.getValue(*InitExpr, SkipPast::None)) {
       Env.setValue(Loc, *InitExprVal);
if (Env.getValue(Loc) == nullptr) {
       // FIXME. If and when we interpret all language cases, change this to
       // assert that `InitExpr` is interpreted, rather than supplying a default
       // value (assuming we don't update the environment API to return
       // references).
       if (Value *Val = Env.createValue(D.getType()))
         Env.setValue(Loc, *Val);
     }
 
+    // `DecompositionDecl` must be handled after we've interpreted the loc
+    // itself, because the binding expression refers back to the
+    // `DecompositionDecl` (even though it has no written name).
     if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) {
       // If VarDecl is a DecompositionDecl, evaluate each of its bindings. This
       // needs to be evaluated after initializing the values in the storage for
       // VarDecl, as the bindings refer to them.
       // FIXME: Add support for ArraySubscriptExpr.
       // FIXME: Consider adding AST nodes used in BindingDecls to the CFG.
       for (const auto *B : Decomp->bindings()) {
         if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding())) {
           auto *DE = dyn_cast_or_null<DeclRefExpr>(ME->getBase());
           if (DE == nullptr)
             continue;
 
           // ME and its base haven't been visited because they aren't included
           // in the statements of the CFG basic block.
           VisitDeclRefExpr(DE);
           VisitMemberExpr(ME);
 
           if (auto *Loc = Env.getStorageLocation(*ME, SkipPast::Reference))
             Env.setStorageLocation(*B, *Loc);
         } else if (auto *VD = B->getHoldingVar()) {
           // Holding vars are used to back the BindingDecls of tuple-like
           // types. The holding var declarations appear *after* this statement,
           // so we have to create a location for them here to share with `B`. We
           // don't visit the binding, because we know it will be a DeclRefExpr
-          // to `VD`.
+          // to `VD`. Note that, by construction of the AST, `VD` will always be
+          // a reference -- either lvalue or rvalue.
           auto &VDLoc = Env.createStorageLocation(*VD);
           Env.setStorageLocation(*VD, VDLoc);
           Env.setStorageLocation(*B, VDLoc);
         }
       }
     }
   }
 
case CK_IntegralToBoolean: {
         // FIXME: If integer modeling is added, then update this code to create
         // the boolean based on the integer model.
         Env.setValue(Loc, Env.makeAtomicBoolValue());
       break;
     }
 
     case CK_LValueToRValue: {
       // When an L-value is used as an R-value, it may result in sharing, so we
-      // need to unpack any nested `Top`s.
+      // need to unpack any nested `Top`s. We also need to strip off the
+      // `ReferenceValue` associated with the lvalue.
       auto *SubExprVal = maybeUnpackLValueExpr(*SubExpr, Env);
       if (SubExprVal == nullptr)
         break;
 
       auto &ExprLoc = Env.createStorageLocation(*S);
       Env.setStorageLocation(*S, ExprLoc);
       Env.setValue(ExprLoc, *SubExprVal);
       break;

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(
         ASSERT_THAT(BoundFooDecl, NotNull());
 
         const ValueDecl *BoundBarDecl = findValueDecl(ASTCtx, "BoundBar");
         ASSERT_THAT(BoundBarDecl, NotNull());
 
         const ValueDecl *BazDecl = findValueDecl(ASTCtx, "Baz");
         ASSERT_THAT(BazDecl, NotNull());
 
+        // BindingDecls always map to references -- either lvalue or rvalue, so
+        // we still need to skip here.
         const Value *BoundFooValue =
             Env1.getValue(*BoundFooDecl, SkipPast::Reference);
         ASSERT_THAT(BoundFooValue, NotNull());
         EXPECT_TRUE(isa<BoolValue>(BoundFooValue));
 
         const Value *BoundBarValue =
             Env1.getValue(*BoundBarDecl, SkipPast::Reference);
         ASSERT_THAT(BoundBarValue, NotNull());
         EXPECT_TRUE(isa<IntegerValue>(BoundBarValue));
 
         // Test that a `DeclRefExpr` to a `BindingDecl` works as expected.
-        EXPECT_EQ(Env1.getValue(*BazDecl, SkipPast::Reference), BoundFooValue);
+        EXPECT_EQ(Env1.getValue(*BazDecl, SkipPast::None), BoundFooValue);
 
         const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
 
         // Test that `BoundFooDecl` retains the value we expect, after the join.
         BoundFooValue = Env2.getValue(*BoundFooDecl, SkipPast::Reference);
-        EXPECT_EQ(Env2.getValue(*BazDecl, SkipPast::Reference), BoundFooValue);
+        EXPECT_EQ(Env2.getValue(*BazDecl, SkipPast::None), BoundFooValue);
       });
 }
 
 TEST(TransferTest, StructuredBindingAssignRefFromTupleLikeType) {
   std::string Code = R"(
     namespace std {
     using size_t = int;
     template <class> struct tuple_size;
runDataflow(
             Env1.getValue(*BoundBarDecl, SkipPast::Reference);
         ASSERT_THAT(BoundBarValue, NotNull());
         EXPECT_TRUE(isa<IntegerValue>(BoundBarValue));
 
         // Test that a `DeclRefExpr` to a `BindingDecl` (with reference type)
         // works as expected. We don't test aliasing properties of the
         // reference, because we don't model `std::get` and so have no way to
         // equate separate references into the tuple.
-        EXPECT_EQ(Env1.getValue(*BazDecl, SkipPast::Reference), BoundFooValue);
+        EXPECT_EQ(Env1.getValue(*BazDecl, SkipPast::None), BoundFooValue);
 
         const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
 
         // Test that `BoundFooDecl` retains the value we expect, after the join.
         BoundFooValue = Env2.getValue(*BoundFooDecl, SkipPast::Reference);
-        EXPECT_EQ(Env2.getValue(*BazDecl, SkipPast::Reference), BoundFooValue);
+        EXPECT_EQ(Env2.getValue(*BazDecl, SkipPast::None), BoundFooValue);
       });
 }
-// TODO: ref binding
 
 TEST(TransferTest, BinaryOperatorComma) {
   std::string Code = R"(
     void target(int Foo, int Bar) {
       int &Baz = (Foo, Bar);
       // [[p]]
     }
   )";