[analyzer] Lambda capture non-POD type array

[isuckatcs]

Summary

This patch allows us to analyze non-POD type arrays
captured by C++ lambdas.

To be able to capture the mentioned arrays, a new
ConstructionContext has been created, called
LambdaCaptureConstructionContext.

This patch has been extracted from, and depends on D129496.

[NoQ]

Awesome, thanks! I was thinking like, lambdas in one patch, arrays in one patch, but this works too.

clang/test/Analysis/array-init-loop.cpp

169–171

Let's duplicate S3 to make sure both tests emit the warning. It isn't a problem that the warning is deduplicated, that's somewhat intentional. In real life most warnings are found on like 100 different paths each, we definitely need a deduplication mechanism. It's probably not ideal to deduplicate warnings by final node location when they're coming from different *analyses* but it isn't harmful either, users just get less warnings at a time, but eventually they'll see them all.

[isuckatcs]

Addressed comments.

clang/include/clang/Analysis/CFG.h

public:
   explicit CFGCXXRecordTypedCall(Expr *E, const ConstructionContext *C)
       : CFGStmt(E, CXXRecordTypedCall) {
     assert(isCXXRecordTypedCall(E));
     assert(C && (isa<TemporaryObjectConstructionContext>(C) ||
                  // These are possible in C++17 due to mandatory copy elision.
                  isa<ReturnedValueConstructionContext>(C) ||
                  isa<VariableConstructionContext>(C) ||
                  isa<ConstructorInitializerConstructionContext>(C) ||
-                 isa<ArgumentConstructionContext>(C)));
+                 isa<ArgumentConstructionContext>(C) ||
+                 isa<LambdaCaptureConstructionContext>(C)));
     Data2.setPointer(const_cast<ConstructionContext *>(C));
   }
 
   const ConstructionContext *getConstructionContext() const {
     return static_cast<ConstructionContext *>(Data2.getPointer());
   }
 
 private:

clang/include/clang/Analysis/ConstructionContext.h

enum ItemKind {
     VariableKind,
     NewAllocatorKind,
     ReturnKind,
     MaterializationKind,
     TemporaryDestructorKind,
     ElidedDestructorKind,
     ElidableConstructorKind,
     ArgumentKind,
-    STATEMENT_WITH_INDEX_KIND_BEGIN=ArgumentKind,
-    STATEMENT_WITH_INDEX_KIND_END=ArgumentKind,
+    LambdaCaptureKind,
+    STATEMENT_WITH_INDEX_KIND_BEGIN = ArgumentKind,
+    STATEMENT_WITH_INDEX_KIND_END = LambdaCaptureKind,
     STATEMENT_KIND_BEGIN = VariableKind,
-    STATEMENT_KIND_END = ArgumentKind,
+    STATEMENT_KIND_END = LambdaCaptureKind,
     InitializerKind,
-    INITIALIZER_KIND_BEGIN=InitializerKind,
-    INITIALIZER_KIND_END=InitializerKind
+    INITIALIZER_KIND_BEGIN = InitializerKind,
+    INITIALIZER_KIND_END = InitializerKind
   };
 
   LLVM_DUMP_METHOD static StringRef getKindAsString(ItemKind K) {
     switch (K) {
       case VariableKind:            return "construct into local variable";
       case NewAllocatorKind:        return "construct into new-allocator";
       case ReturnKind:              return "construct into return address";
       case MaterializationKind:     return "materialize temporary";
       case TemporaryDestructorKind: return "destroy temporary";
       case ElidedDestructorKind:    return "elide destructor";
       case ElidableConstructorKind: return "elide constructor";
       case ArgumentKind:            return "construct into argument";
+      case LambdaCaptureKind:
+        return "construct into lambda captured variable";
       case InitializerKind:         return "construct into member variable";
     };
     llvm_unreachable("Unknown ItemKind");
   }
 
 private:
   const void *const Data;
   const ItemKind Kind;
   const unsigned Index = 0;
 
   bool hasStatement() const {
     return Kind >= STATEMENT_KIND_BEGIN &&
            Kind <= STATEMENT_KIND_END;
   }
 
   bool hasIndex() const {
     return Kind >= STATEMENT_WITH_INDEX_KIND_BEGIN &&
-           Kind >= STATEMENT_WITH_INDEX_KIND_END;
+           Kind <= STATEMENT_WITH_INDEX_KIND_END;
   }
 
   bool hasInitializer() const {
     return Kind >= INITIALIZER_KIND_BEGIN &&
            Kind <= INITIALIZER_KIND_END;
   }
 
 public:
ConstructionContextItem(const Expr *E, unsigned Index)
     assert(isa<CallExpr>(E) || isa<CXXConstructExpr>(E) ||
            isa<CXXDeleteExpr>(E) || isa<CXXInheritedCtorInitExpr>(E) ||
            isa<ObjCMessageExpr>(E));
   }
 
   ConstructionContextItem(const CXXCtorInitializer *Init)
       : Data(Init), Kind(InitializerKind), Index(0) {}
 
+  ConstructionContextItem(const LambdaExpr *LE, unsigned Index)
+      : Data(LE), Kind(LambdaCaptureKind), Index(Index) {}
+
   ItemKind getKind() const { return Kind; }
 
   LLVM_DUMP_METHOD StringRef getKindAsString() const {
     return getKindAsString(getKind());
   }
 
   /// The construction site - the statement that triggered the construction
   /// for one of its parts. For instance, stack variable declaration statement
enum Kind {
     SimpleTemporaryObjectKind,
     ElidedTemporaryObjectKind,
     TEMPORARY_BEGIN = SimpleTemporaryObjectKind,
     TEMPORARY_END = ElidedTemporaryObjectKind,
     SimpleReturnedValueKind,
     CXX17ElidedCopyReturnedValueKind,
     RETURNED_VALUE_BEGIN = SimpleReturnedValueKind,
     RETURNED_VALUE_END = CXX17ElidedCopyReturnedValueKind,
-    ArgumentKind
+    ArgumentKind,
+    LambdaCaptureKind
   };
 
 protected:
   Kind K;
 
   // Do not make public! These need to only be constructed
   // via createFromLayers().
   explicit ConstructionContext(Kind K) : K(K) {}
public:
   unsigned getIndex() const { return Index; }
   const CXXBindTemporaryExpr *getCXXBindTemporaryExpr() const { return BTE; }
 
   static bool classof(const ConstructionContext *CC) {
     return CC->getKind() == ArgumentKind;
   }
 };
 
+class LambdaCaptureConstructionContext : public ConstructionContext {
+  // The lambda of which the initializer we capture.
+  const LambdaExpr *LE;
+
+  // Index of the captured element in the captured list.
+  unsigned Index;
+
+  friend class ConstructionContext; // Allows to create<>() itself.
+
+  explicit LambdaCaptureConstructionContext(const LambdaExpr *LE,
+                                            unsigned Index)
+      : ConstructionContext(LambdaCaptureKind), LE(LE), Index(Index) {}
+
+public:
+  const LambdaExpr *getLambdaExpr() const { return LE; }
+  unsigned getIndex() const { return Index; }
+
+  const Expr *getInitializer() const {
+    return *(LE->capture_init_begin() + Index);
+  }
+
+  const FieldDecl *getFieldDecl() const {
+    auto It = LE->getLambdaClass()->field_begin();
+    std::advance(It, Index);
+    return *It;
+  }
+
+  const ArrayInitLoopExpr *getArrayInitLoop() const override {
+    return dyn_cast_or_null<ArrayInitLoopExpr>(getInitializer());
+  }
+
+  static bool classof(const ConstructionContext *CC) {
+    return CC->getKind() == LambdaCaptureKind;
+  }
+};
+
 } // end namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_CONSTRUCTIONCONTEXT_H

clang/lib/Analysis/CFG.cpp

if (Expr *CopyExpr = CI.getCopyExpr()) {
         LastBlock = Tmp;
     }
   }
   return LastBlock;
 }
 
 CFGBlock *CFGBuilder::VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc) {
   CFGBlock *LastBlock = VisitNoRecurse(E, asc);
+
+  unsigned Idx = 0;
   for (LambdaExpr::capture_init_iterator it = E->capture_init_begin(),
-       et = E->capture_init_end(); it != et; ++it) {
+                                         et = E->capture_init_end();
+       it != et; ++it, ++Idx) {
     if (Expr *Init = *it) {
+      // If the initializer is an ArrayInitLoopExpr, we want to extract the
+      // initializer, that's used for each element.
+      const auto *AILE = dyn_cast_or_null<ArrayInitLoopExpr>(Init);
+
+      findConstructionContexts(ConstructionContextLayer::create(
+                                   cfg->getBumpVectorContext(), {E, Idx}),
+                               AILE ? AILE->getSubExpr() : Init);
+
       CFGBlock *Tmp = Visit(Init);
       if (Tmp)
         LastBlock = Tmp;
     }
   }
   return LastBlock;
 }
 
static void print_construction_context(raw_ostream &OS,
   }
   case ConstructionContext::ElidedTemporaryObjectKind: {
     const auto *TOCC = cast<ElidedTemporaryObjectConstructionContext>(CC);
     Stmts.push_back(TOCC->getCXXBindTemporaryExpr());
     Stmts.push_back(TOCC->getMaterializedTemporaryExpr());
     Stmts.push_back(TOCC->getConstructorAfterElision());
     break;
   }
+  case ConstructionContext::LambdaCaptureKind: {
+    const auto *LCC = cast<LambdaCaptureConstructionContext>(CC);
+    Helper.handledStmt(const_cast<LambdaExpr *>(LCC->getLambdaExpr()), OS);
+    OS << "+" << LCC->getIndex();
+    return;
+  }
   case ConstructionContext::ArgumentKind: {
     const auto *ACC = cast<ArgumentConstructionContext>(CC);
     if (const Stmt *BTE = ACC->getCXXBindTemporaryExpr()) {
       OS << ", ";
       Helper.handledStmt(const_cast<Stmt *>(BTE), OS);
     }
     OS << ", ";
     Helper.handledStmt(const_cast<Expr *>(ACC->getCallLikeExpr()), OS);

clang/lib/Analysis/ConstructionContext.cpp

const ConstructionContext *ConstructionContext::createBoundTemporaryFromLayers(
   case ConstructionContextItem::InitializerKind: {
     assert(ParentLayer->isLast());
     const auto *I = ParentItem.getCXXCtorInitializer();
     assert(!I->getAnyMember()->getType().getCanonicalType()
              ->getAsCXXRecordDecl()->hasTrivialDestructor());
     return create<CXX17ElidedCopyConstructorInitializerConstructionContext>(
         C, I, BTE);
   }
+  case ConstructionContextItem::LambdaCaptureKind: {
+    assert(ParentLayer->isLast());
+    const auto *E = cast<LambdaExpr>(ParentItem.getStmt());
+    return create<LambdaCaptureConstructionContext>(C, E,
+                                                    ParentItem.getIndex());
+  }
   } // switch (ParentItem.getKind())
 
   llvm_unreachable("Unexpected construction context with destructor!");
 }
 
 const ConstructionContext *ConstructionContext::createFromLayers(
     BumpVectorContext &C, const ConstructionContextLayer *TopLayer) {
   // Before this point all we've had was a stockpile of arbitrary layers.
case ConstructionContextItem::TemporaryDestructorKind: {
     return createBoundTemporaryFromLayers(C, BTE, TopLayer->getParent());
   }
   case ConstructionContextItem::ElidedDestructorKind: {
     llvm_unreachable("Elided destructor items are not produced by the CFG!");
   }
   case ConstructionContextItem::ElidableConstructorKind: {
     llvm_unreachable("The argument needs to be materialized first!");
   }
+  case ConstructionContextItem::LambdaCaptureKind: {
+    assert(TopLayer->isLast());
+    const auto *E = cast<LambdaExpr>(TopItem.getStmt());
+    return create<LambdaCaptureConstructionContext>(C, E, TopItem.getIndex());
+  }
   case ConstructionContextItem::InitializerKind: {
     assert(TopLayer->isLast());
     const CXXCtorInitializer *I = TopItem.getCXXCtorInitializer();
     return create<SimpleConstructorInitializerConstructionContext>(C, I);
   }
   case ConstructionContextItem::ArgumentKind: {
     assert(TopLayer->isLast());
     const auto *E = cast<Expr>(TopItem.getStmt());
     return create<ArgumentConstructionContext>(C, E, TopItem.getIndex(),
                                                /*BTE=*/nullptr);
   }
   } // switch (TopItem.getKind())
   llvm_unreachable("Unexpected construction context!");
 }

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

ExprEngine::addObjectUnderConstruction(ProgramStateRef State,
 
   const Expr *Init = nullptr;
 
   if (auto DS = dyn_cast_or_null<DeclStmt>(Item.getStmtOrNull())) {
     if (auto VD = dyn_cast_or_null<VarDecl>(DS->getSingleDecl()))
       Init = VD->getInit();
   }
 
+  if (auto LE = dyn_cast_or_null<LambdaExpr>(Item.getStmtOrNull()))
+    Init = *(LE->capture_init_begin() + Item.getIndex());
+
   if (!Init && !Item.getStmtOrNull())
     Init = Item.getCXXCtorInitializer()->getInit();
 
   // In an ArrayInitLoopExpr the real initializer is returned by
   // getSubExpr().
   if (const auto *AILE = dyn_cast_or_null<ArrayInitLoopExpr>(Init))
     Init = AILE->getSubExpr();
 

clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

case ConstructionContext::SimpleTemporaryObjectKind: {
 
         if (MTE->getStorageDuration() == SD_Static ||
             MTE->getStorageDuration() == SD_Thread)
           return loc::MemRegionVal(MRMgr.getCXXStaticTempObjectRegion(E));
       }
 
       return loc::MemRegionVal(MRMgr.getCXXTempObjectRegion(E, LCtx));
     }
+    case ConstructionContext::LambdaCaptureKind: {
+      CallOpts.IsTemporaryCtorOrDtor = true;
+
+      const auto *LCC = cast<LambdaCaptureConstructionContext>(CC);
+
+      SVal Base = loc::MemRegionVal(
+          MRMgr.getCXXTempObjectRegion(LCC->getInitializer(), LCtx));
+
+      const auto *CE = dyn_cast_or_null<CXXConstructExpr>(E);
+      if (getIndexOfElementToConstruct(State, CE, LCtx)) {
+        CallOpts.IsArrayCtorOrDtor = true;
+        Base = State->getLValue(E->getType(), svalBuilder.makeArrayIndex(Idx),
+                                Base);
+      }
+
+      return Base;
+    }
     case ConstructionContext::ArgumentKind: {
       // Arguments are technically temporaries.
       CallOpts.IsTemporaryCtorOrDtor = true;
 
       const auto *ACC = cast<ArgumentConstructionContext>(CC);
       const Expr *E = ACC->getCallLikeExpr();
       unsigned Idx = ACC->getIndex();
 
case ConstructionContext::SimpleTemporaryObjectKind: {
       if (const auto *BTE = TCC->getCXXBindTemporaryExpr())
         State = addObjectUnderConstruction(State, BTE, LCtx, V);
 
       if (const auto *MTE = TCC->getMaterializedTemporaryExpr())
         State = addObjectUnderConstruction(State, MTE, LCtx, V);
 
       return State;
     }
+    case ConstructionContext::LambdaCaptureKind: {
+      const auto *LCC = cast<LambdaCaptureConstructionContext>(CC);
+
+      // If we capture and array, we want to store the super region, not a
+      // sub-region.
+      if (const auto *EL = dyn_cast_or_null<ElementRegion>(V.getAsRegion()))
+        V = loc::MemRegionVal(EL->getSuperRegion());
+
+      return addObjectUnderConstruction(
+          State, {LCC->getLambdaExpr(), LCC->getIndex()}, LCtx, V);
+    }
     case ConstructionContext::ArgumentKind: {
       const auto *ACC = cast<ArgumentConstructionContext>(CC);
       if (const auto *BTE = ACC->getCXXBindTemporaryExpr())
         State = addObjectUnderConstruction(State, BTE, LCtx, V);
 
       return addObjectUnderConstruction(
           State, {ACC->getCallLikeExpr(), ACC->getIndex()}, LCtx, V);
     }
void ExprEngine::VisitLambdaExpr(const LambdaExpr *LE, ExplodedNode *Pred,
   const MemRegion *R = svalBuilder.getRegionManager().getCXXTempObjectRegion(
       LE, LocCtxt);
   SVal V = loc::MemRegionVal(R);
 
   ProgramStateRef State = Pred->getState();
 
   // If we created a new MemRegion for the lambda, we should explicitly bind
   // the captures.
+  unsigned Idx = 0;
   CXXRecordDecl::field_iterator CurField = LE->getLambdaClass()->field_begin();
   for (LambdaExpr::const_capture_init_iterator i = LE->capture_init_begin(),
                                                e = LE->capture_init_end();
-       i != e; ++i, ++CurField) {
+       i != e; ++i, ++CurField, ++Idx) {
     FieldDecl *FieldForCapture = *CurField;
     SVal FieldLoc = State->getLValue(FieldForCapture, V);
 
     SVal InitVal;
     if (!FieldForCapture->hasCapturedVLAType()) {
       Expr *InitExpr = *i;
+
+      if (const auto AILE = dyn_cast<ArrayInitLoopExpr>(InitExpr)) {
+        // If the AILE initializes a POD array, we need to keep it as the
+        // InitExpr.
+        if (dyn_cast<CXXConstructExpr>(AILE->getSubExpr()))
+          InitExpr = AILE->getSubExpr();
+      }
+
       assert(InitExpr && "Capture missing initialization expression");
+
+      if (dyn_cast<CXXConstructExpr>(InitExpr)) {
+        InitVal = *getObjectUnderConstruction(State, {LE, Idx}, LocCtxt);
+        InitVal = State->getSVal(InitVal.getAsRegion());
+
+        State = finishObjectConstruction(State, {LE, Idx}, LocCtxt);
+      } else
         InitVal = State->getSVal(InitExpr, LocCtxt);
+
     } else {
+
+      assert(!getObjectUnderConstruction(State, {LE, Idx}, LocCtxt) &&
+             "VLA capture by value is a compile time error!");
+
       // The field stores the length of a captured variable-length array.
       // These captures don't have initialization expressions; instead we
       // get the length from the VLAType size expression.
       Expr *SizeExpr = FieldForCapture->getCapturedVLAType()->getSizeExpr();
       InitVal = State->getSVal(SizeExpr, LocCtxt);
     }
 
     State = State->bindLoc(FieldLoc, InitVal, LocCtxt);

clang/test/Analysis/array-init-loop.cpp

void array_init_non_pod() {
   clang_analyzer_eval(c.i == 4); // expected-warning{{TRUE}}
   clang_analyzer_eval(d.i == 5); // expected-warning{{TRUE}}
 }
 
 struct S3 {
   int i;
 };
 
+// The duplicate is required to emit a warning at 2 different places. 
+struct S3_duplicate {
+  int i;
+};
+
 void array_uninit_non_pod() {
   S3 arr[1];
 
   auto [a] = arr; // expected-warning@159{{ in implicit constructor is garbage or undefined }}
 }
 
 void lambda_init_non_pod() {
   S2::c = 0;
   S2 arr[4];
 
-  // FIXME: These should be TRUE, but we fail to capture the array properly.
   auto l = [arr] { return arr[0].i; }();
-  clang_analyzer_eval(l == 2); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+  clang_analyzer_eval(l == 2); // expected-warning{{TRUE}}
 
   l = [arr] { return arr[1].i; }();
-  clang_analyzer_eval(l == 3); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+  clang_analyzer_eval(l == 3); // expected-warning{{TRUE}}
 
   l = [arr] { return arr[2].i; }();
-  clang_analyzer_eval(l == 4); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+  clang_analyzer_eval(l == 4); // expected-warning{{TRUE}}
 
   l = [arr] { return arr[3].i; }();
-  clang_analyzer_eval(l == 5); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+  clang_analyzer_eval(l == 5); // expected-warning{{TRUE}}
 }
 
 void lambda_uninit_non_pod() {
-  S3 arr[4];
+  S3_duplicate arr[4];
 
-  int l = [arr] { return arr[3].i; }();
+  int l = [arr] { return arr[3].i; }(); // expected-warning@164{{ in implicit constructor is garbage or undefined }}
 }
 
 // If this struct is being copy/move constructed by the implicit ctors, ArrayInitLoopExpr
 // is responsible for the initialization of 'arr' by copy/move constructing each of the
 // elements.
 struct S5 {
   S2 arr[4];
 };

clang/test/Analysis/lambdas.cpp

 
 #endif
 
 // CHECK: [B2 (ENTRY)]
 // CHECK:   Succs (1): B1
 // CHECK: [B1]
 // CHECK:   1: x
 // CHECK:   2: [B1.1] (ImplicitCastExpr, NoOp, const struct X)
-// CHECK:   3: [B1.2] (CXXConstructExpr, struct X)
+// CHECK:   3: [B1.2] (CXXConstructExpr[B1.4]+0, struct X)
 // CHECK:   4: [x]     {
 // CHECK:    }
 // CHECK:   5: (void)[B1.4] (CStyleCastExpr, ToVoid, void)
 // CHECK:   Preds (1): B2
 // CHECK:   Succs (1): B0
 // CHECK: [B0 (EXIT)]
 // CHECK:   Preds (1): B1
-