[clang][dataflow] Add transfer functions for structured bindings

[sgatev]

Summary

This is part of the implementation of the dataflow analysis framework.
See "[RFC] A dataflow analysis framework for Clang AST" on cfe-dev.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

87

Did you look into how hard would it be to add structured bindings to the CFG builder? If the effort is comparable to this patch (and not significantly bigger), it might be better to do that work instead of spending effort on some temporary workaround. What do you think?

[sgatev]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

87

Circling back to this after a while. I believe we explored changing the CFG briefly, but don't have a fully fleshed out proposal for it. I recently noticed https://discourse.llvm.org/t/implement-support-for-c-17-structured-bindings-in-the-clang-static-analyzer/60588. It seems that part of the project is exploring necessary changes to the CFG. What do you think about submitting this patch with local pattern matching and revisiting that once the GSoC project completes?

[xazax.hun]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

87

Officially, there is no candidate accepted for that project yet, so there is no guarantee that we will have someone working on this. That being said, the CSA devs started to discuss what would be the best way to represent structured bindings in the CFG, and it is possible that for many of the cases we do not actually need to change the CFG, because the AST nodes have rich information. But of course, none of this is final, but we do not need to block this patch on that. So I'm fine adding this for now.

The AST for the supported case looks like:

`-DeclStmt 0x5599ad9de6b0 <line:8:7, col:45>
   `-DecompositionDecl 0x5599ad9de310 <col:7, col:42> col:13 used 'A &' cinit
     |-DeclRefExpr 0x5599ad9de388 <col:42> 'A' lvalue Var 0x5599ad9ddb80 'Baz' 'A'
     |-BindingDecl 0x5599ad9de280 <col:14> col:14 BoundFooRef 'int'
     | `-MemberExpr 0x5599ad9de630 <col:14> 'int' lvalue .Foo 0x5599ad9dd970
     |   `-DeclRefExpr 0x5599ad9de610 <col:14> 'A':'A' lvalue Decomposition 0x5599ad9de310 '' 'A &'
     `-BindingDecl 0x5599ad9de2c8 <col:27> col:27 BoundBarRef 'int'
       `-MemberExpr 0x5599ad9de680 <col:27> 'int' lvalue .Bar 0x5599ad9dd9d8
         `-DeclRefExpr 0x5599ad9de660 <col:27> 'A':'A' lvalue Decomposition 0x5599ad9de310 '' 'A &'

So each BindingDecl is like:

`-BindingDecl 0x5599ad9de2c8 <col:27> col:27 BoundBarRef 'int'
  `-MemberExpr 0x5599ad9de680 <col:27> 'int' lvalue .Bar 0x5599ad9dd9d8
    `-DeclRefExpr 0x5599ad9de660 <col:27> 'A':'A' lvalue Decomposition 0x5599ad9de310 '' 'A &'

Is there a case where the BindingDecl would have a different shape? If we do not expect that happening, I feel like an StmtVisitor is a bit of an overkill for this and we could handle the supported case more directly. What do you think?

[sgatev]

Rebase main.

[sgatev]

Address comments.

[sgatev]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

87

Agreed. I simplified the patch. Please take a look.

[xazax.hun]

Looks good, thanks!

clang/lib/Analysis/FlowSensitive/Transfer.cpp

case BO_LOr: {
       BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS);
 
       auto &Loc = Env.createStorageLocation(*S);
       Env.setStorageLocation(*S, Loc);
       if (S->getOpcode() == BO_LAnd)
         Env.setValue(Loc, Env.makeAnd(LHSVal, RHSVal));
       else
         Env.setValue(Loc, Env.makeOr(LHSVal, RHSVal));
       break;
     }
     case BO_NE:
     case BO_EQ: {
       auto &LHSEqRHSValue = evaluateBooleanEquality(*LHS, *RHS, Env);
       auto &Loc = Env.createStorageLocation(*S);
       Env.setStorageLocation(*S, Loc);
       Env.setValue(Loc, S->getOpcode() == BO_EQ ? LHSEqRHSValue
                                                 : Env.makeNot(LHSEqRHSValue));
void VisitDeclStmt(const DeclStmt *S) {
     const Expr *InitExpr = D.getInit();
     if (InitExpr == nullptr) {
       // No initializer expression - associate `Loc` with a new value.
       if (Value *Val = Env.createValue(D.getType()))
         Env.setValue(Loc, *Val);
       return;
     }
 
-    InitExpr = D.getInit();
-    assert(InitExpr != nullptr);
-
     if (D.getType()->isReferenceType()) {
       // Initializing a reference variable - do not create a reference to
       // reference.
       if (auto *InitExprLoc =
               Env.getStorageLocation(*InitExpr, SkipPast::Reference)) {
         auto &Val =
             Env.takeOwnership(std::make_unique<ReferenceValue>(*InitExprLoc));
         Env.setValue(Loc, Val);
-        return;
       }
     } else if (auto *InitExprVal = Env.getValue(*InitExpr, SkipPast::None)) {
       Env.setValue(Loc, *InitExprVal);
-      return;
     }
 
+    if (Env.getValue(Loc) == nullptr) {
       // We arrive here in (the few) cases where an expression is intentionally
       // "uninterpreted". There are two ways to handle this situation: propagate
       // the status, so that uninterpreted initializers result in uninterpreted
-    // variables, or provide a default value. We choose the latter so that later
-    // refinements of the variable can be used for reasoning about the
+      // variables, or provide a default value. We choose the latter so that
+      // later refinements of the variable can be used for reasoning about the
       // surrounding code.
       //
-    // 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).
+      // 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);
     }
 
+    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 that are used for structured bindings
+      // to the CFG.
+      for (const auto *B : Decomp->bindings()) {
+        auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding());
+        if (ME == nullptr)
+          continue;
+
+        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);
+      }
+    }
+  }
+
   void VisitImplicitCastExpr(const ImplicitCastExpr *S) {
     const Expr *SubExpr = S->getSubExpr();
     assert(SubExpr != nullptr);
 
     switch (S->getCastKind()) {
     case CK_IntegralToBoolean: {
       // This cast creates a new, boolean value from the integral value. We
       // model that with a fresh value in the environment, unless it's already a

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

TEST_F(TransferTest, DoesNotCrashOnUnionThisExpr) {
   runDataflow(
       Code,
       [](llvm::ArrayRef<
              std::pair<std::string, DataflowAnalysisState<NoopLattice>>>,
          ASTContext &) {},
       LangStandard::lang_cxx17, /*ApplyBuiltinTransfer=*/true, "operator=");
 }
 
+TEST_F(TransferTest, StructuredBindingAssignFromStructIntMembersToRefs) {
+  std::string Code = R"(
+    struct A {
+      int Foo;
+      int Bar;
+    };
+
+    void target() {
+      int Qux;
+      A Baz;
+      Baz.Foo = Qux;
+      auto &FooRef = Baz.Foo;
+      auto &BarRef = Baz.Bar;
+      auto &[BoundFooRef, BoundBarRef] = Baz;
+      // [[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 *FooRefDecl = findValueDecl(ASTCtx, "FooRef");
+        ASSERT_THAT(FooRefDecl, NotNull());
+
+        const ValueDecl *BarRefDecl = findValueDecl(ASTCtx, "BarRef");
+        ASSERT_THAT(BarRefDecl, NotNull());
+
+        const ValueDecl *QuxDecl = findValueDecl(ASTCtx, "Qux");
+        ASSERT_THAT(QuxDecl, NotNull());
+
+        const ValueDecl *BoundFooRefDecl = findValueDecl(ASTCtx, "BoundFooRef");
+        ASSERT_THAT(BoundFooRefDecl, NotNull());
+
+        const ValueDecl *BoundBarRefDecl = findValueDecl(ASTCtx, "BoundBarRef");
+        ASSERT_THAT(BoundBarRefDecl, NotNull());
+
+        const StorageLocation *FooRefLoc =
+            Env.getStorageLocation(*FooRefDecl, SkipPast::Reference);
+        ASSERT_THAT(FooRefLoc, NotNull());
+
+        const StorageLocation *BarRefLoc =
+            Env.getStorageLocation(*BarRefDecl, SkipPast::Reference);
+        ASSERT_THAT(BarRefLoc, NotNull());
+
+        const Value *QuxVal = Env.getValue(*QuxDecl, SkipPast::None);
+        ASSERT_THAT(QuxVal, NotNull());
+
+        const StorageLocation *BoundFooRefLoc =
+            Env.getStorageLocation(*BoundFooRefDecl, SkipPast::Reference);
+        EXPECT_EQ(BoundFooRefLoc, FooRefLoc);
+
+        const StorageLocation *BoundBarRefLoc =
+            Env.getStorageLocation(*BoundBarRefDecl, SkipPast::Reference);
+        EXPECT_EQ(BoundBarRefLoc, BarRefLoc);
+
+        EXPECT_EQ(Env.getValue(*BoundFooRefDecl, SkipPast::Reference), QuxVal);
+      });
+}
+
+TEST_F(TransferTest, StructuredBindingAssignFromStructRefMembersToRefs) {
+  std::string Code = R"(
+    struct A {
+      int &Foo;
+      int &Bar;
+    };
+
+    void target(A Baz) {
+      int Qux;
+      Baz.Foo = Qux;
+      auto &FooRef = Baz.Foo;
+      auto &BarRef = Baz.Bar;
+      auto &[BoundFooRef, BoundBarRef] = Baz;
+      // [[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 *FooRefDecl = findValueDecl(ASTCtx, "FooRef");
+        ASSERT_THAT(FooRefDecl, NotNull());
+
+        const ValueDecl *BarRefDecl = findValueDecl(ASTCtx, "BarRef");
+        ASSERT_THAT(BarRefDecl, NotNull());
+
+        const ValueDecl *QuxDecl = findValueDecl(ASTCtx, "Qux");
+        ASSERT_THAT(QuxDecl, NotNull());
+
+        const ValueDecl *BoundFooRefDecl = findValueDecl(ASTCtx, "BoundFooRef");
+        ASSERT_THAT(BoundFooRefDecl, NotNull());
+
+        const ValueDecl *BoundBarRefDecl = findValueDecl(ASTCtx, "BoundBarRef");
+        ASSERT_THAT(BoundBarRefDecl, NotNull());
+
+        const StorageLocation *FooRefLoc =
+            Env.getStorageLocation(*FooRefDecl, SkipPast::Reference);
+        ASSERT_THAT(FooRefLoc, NotNull());
+
+        const StorageLocation *BarRefLoc =
+            Env.getStorageLocation(*BarRefDecl, SkipPast::Reference);
+        ASSERT_THAT(BarRefLoc, NotNull());
+
+        const Value *QuxVal = Env.getValue(*QuxDecl, SkipPast::None);
+        ASSERT_THAT(QuxVal, NotNull());
+
+        const StorageLocation *BoundFooRefLoc =
+            Env.getStorageLocation(*BoundFooRefDecl, SkipPast::Reference);
+        EXPECT_EQ(BoundFooRefLoc, FooRefLoc);
+
+        const StorageLocation *BoundBarRefLoc =
+            Env.getStorageLocation(*BoundBarRefDecl, SkipPast::Reference);
+        EXPECT_EQ(BoundBarRefLoc, BarRefLoc);
+
+        EXPECT_EQ(Env.getValue(*BoundFooRefDecl, SkipPast::Reference), QuxVal);
+      });
+}
+
+TEST_F(TransferTest, StructuredBindingAssignFromStructIntMembersToInts) {
+  std::string Code = R"(
+    struct A {
+      int Foo;
+      int Bar;
+    };
+
+    void target() {
+      int Qux;
+      A Baz;
+      Baz.Foo = Qux;
+      auto &FooRef = Baz.Foo;
+      auto &BarRef = Baz.Bar;
+      auto [BoundFoo, BoundBar] = Baz;
+      // [[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 *FooRefDecl = findValueDecl(ASTCtx, "FooRef");
+        ASSERT_THAT(FooRefDecl, NotNull());
+
+        const ValueDecl *BarRefDecl = findValueDecl(ASTCtx, "BarRef");
+        ASSERT_THAT(BarRefDecl, NotNull());
+
+        const ValueDecl *BoundFooDecl = findValueDecl(ASTCtx, "BoundFoo");
+        ASSERT_THAT(BoundFooDecl, NotNull());
+
+        const ValueDecl *BoundBarDecl = findValueDecl(ASTCtx, "BoundBar");
+        ASSERT_THAT(BoundBarDecl, NotNull());
+
+        const ValueDecl *QuxDecl = findValueDecl(ASTCtx, "Qux");
+        ASSERT_THAT(QuxDecl, NotNull());
+
+        const StorageLocation *FooRefLoc =
+            Env.getStorageLocation(*FooRefDecl, SkipPast::Reference);
+        ASSERT_THAT(FooRefLoc, NotNull());
+
+        const StorageLocation *BarRefLoc =
+            Env.getStorageLocation(*BarRefDecl, SkipPast::Reference);
+        ASSERT_THAT(BarRefLoc, NotNull());
+
+        const Value *QuxVal = Env.getValue(*QuxDecl, SkipPast::None);
+        ASSERT_THAT(QuxVal, NotNull());
+
+        const StorageLocation *BoundFooLoc =
+            Env.getStorageLocation(*BoundFooDecl, SkipPast::Reference);
+        EXPECT_NE(BoundFooLoc, FooRefLoc);
+
+        const StorageLocation *BoundBarLoc =
+            Env.getStorageLocation(*BoundBarDecl, SkipPast::Reference);
+        EXPECT_NE(BoundBarLoc, BarRefLoc);
+
+        EXPECT_EQ(Env.getValue(*BoundFooDecl, SkipPast::Reference), QuxVal);
+      });
+}
+
 } // namespace