[analyzer] Handling non-POD multidimensional arrays in ArrayInitLoopExpr

[isuckatcs]

Summary

This patch makes it possible for lambdas, implicit copy/move ctors and structured bindings to
handle non-POD multidimensional arrays.

[NoQ]

Lovely, thanks!

[xazax.hun]

clang/lib/Analysis/CFG.cpp

1724

Would a regular dyn_cast work? I would not expect getSubExpr to return nullptr. This applies to some other places as well.

3432–3436

Instead of duplicating both the code and adding this comment, I wonder if a well named small utility function can make this code equally clear and reduce duplication.

clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

569

Do you need a dyn_cast here? ``AILE alreadt has the right type.

[isuckatcs]

clang/lib/Analysis/CFG.cpp

3432–3436

I've been thinking about the same thing. I would also place the getArrayInitLoopExprSize() helper function into ASTContext as it also has a similar helper called getConstantArrayElementCount().

clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

569

It handles if the user passes a nullptr to the function. Also because AILE is an ArrayInitLoopExpr *, in the loop I also have
AILE = dyn_cast<ArrayInitLoopExpr>(E->getSubExpr()) which can still make a nullptr from AILE.

This might not be the best solution but this helper will be reworked anyway due to a mistake I've made below.

575

[xazax.hun]

clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

569

I think if you just declare E to be const ArrayInitLoopExpr*, you might not need the cast at all. while should already guard against nullptr from the user.

[isuckatcs]

• Moved getArrayInitLoopExprSize() to ASTContext.
• Addressed comments.

[xazax.hun]

Some nits inline but overall looks good to me.

clang/lib/AST/ASTContext.cpp

6917

Did you see examples where the SubExpr of an ArrayInitLoopExpr returned a nullptr? If not, I'd go with dyn_cast for now.

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

544–545

Shouldn't this also use extractElementInitializerFromNestedAILE?

clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

544–545

extractElementInitializerFromNestedAILE?

1169–1170

extractElementInitializerFromNestedAILE?

[isuckatcs]

• Rebased
• Moved extractElementInitializerFromNestedAILE() to ExprEngine
• Addressed comments

[isuckatcs]

clang/lib/AST/ASTContext.cpp

6917

getSubExpr() uses a regular cast, so it cannot return nullptr.

[isuckatcs]

clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h

983 ↗

(On Diff #452932)

The definition is in the header, because this method is used in CFG.cpp, but that source file is not linked against any of the ExprEngine source files and I don't want to change the linking of libraries.

@xazax.hun do you have any suggestions, where to put a function that is referenced in both the Analysis and the Static Analyzer library? I want to avoid creating the same helper twice.

[xazax.hun]

clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h

983 ↗

(On Diff #452932)

Are you sure? CFG.cpp is linked into clangAnalysis and clangAnalysis is linked a dependency of the static analyzer core. I'd expect putting this in CFG.cpp should work perfectly well. Just be sure to not put the implementation in an anonymous namespace.

[xazax.hun]

Overall looks good to me. I think extractElementInitializerFromNestedAILE should live somewhere in the clangAnalysis component due to how layering is done, but otherwise it looks wonderful, thanks!

[isuckatcs]

Moved extractElementInitializerFromNestedAILE to CFG.cpp.

@xazax.hun is this how you meant it?

[xazax.hun]

In D131840#3733717, @isuckatcs wrote:

Moved extractElementInitializerFromNestedAILE to CFG.cpp.

@xazax.hun is this how you meant it?

Yep, looks great, thanks!

[xazax.hun]

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

236–237

Would moving this declaration to CFG.h work?

[isuckatcs]

Added a testcase for the crashing snippet. (Wrong revision)

[isuckatcs]

Moved the declaration of extractElementInitializerFromNestedAILE to CFG.h.

clang/include/clang/AST/ASTContext.h

public:
 
   /// Return the innermost element type of a type (which needn't
   /// actually be an array type).
   QualType getBaseElementType(QualType QT) const;
 
   /// Return number of constant array elements.
   uint64_t getConstantArrayElementCount(const ConstantArrayType *CA) const;
 
+  /// Return number of elements initialized in an ArrayInitLoopExpr.
+  uint64_t
+  getArrayInitLoopExprElementCount(const ArrayInitLoopExpr *AILE) const;
+
   /// Perform adjustment on the parameter type of a function.
   ///
   /// This routine adjusts the given parameter type @p T to the actual
   /// parameter type used by semantic analysis (C99 6.7.5.3p[7,8],
   /// C++ [dcl.fct]p3). The adjusted parameter type is returned.
   QualType getAdjustedParameterType(QualType T) const;
 
   /// Retrieve the parameter type as adjusted for use in the signature

clang/include/clang/Analysis/CFG.h

private:
   /// This is the collection of such blocks present in the CFG.
   std::vector<const CFGBlock *> TryDispatchBlocks;
 
   /// Collects DeclStmts synthesized for this CFG and maps each one back to its
   /// source DeclStmt.
   llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts;
 };
 
+Expr *extractElementInitializerFromNestedAILE(const ArrayInitLoopExpr *AILE);
+
 } // namespace clang
 
 //===----------------------------------------------------------------------===//
 // GraphTraits specializations for CFG basic block graphs (source-level CFGs)
 //===----------------------------------------------------------------------===//
 
 namespace llvm {
 

clang/lib/AST/ASTContext.cpp

ASTContext::getConstantArrayElementCount(const ConstantArrayType *CA)  const {
   do {
     ElementCount *= CA->getSize().getZExtValue();
     CA = dyn_cast_or_null<ConstantArrayType>(
       CA->getElementType()->getAsArrayTypeUnsafe());
   } while (CA);
   return ElementCount;
 }
 
+uint64_t ASTContext::getArrayInitLoopExprElementCount(
+    const ArrayInitLoopExpr *AILE) const {
+  if (!AILE)
+    return 0;
+
+  uint64_t ElementCount = 1;
+
+  do {
+    ElementCount *= AILE->getArraySize().getZExtValue();
+    AILE = dyn_cast<ArrayInitLoopExpr>(AILE->getSubExpr());
+  } while (AILE);
+
+  return ElementCount;
+}
+
 /// getFloatingRank - Return a relative rank for floating point types.
 /// This routine will assert if passed a built-in type that isn't a float.
 static FloatingRank getFloatingRank(QualType T) {
   if (const auto *CT = T->getAs<ComplexType>())
     return getFloatingRank(CT->getElementType());
 
   switch (T->castAs<BuiltinType>()->getKind()) {
   default: llvm_unreachable("getFloatingRank(): not a floating type");

clang/lib/Analysis/CFG.cpp

TryResult evaluateAsBooleanConditionNoCache(Expr *E) {
     return {};
   }
 
   bool hasTrivialDestructor(VarDecl *VD);
 };
 
 } // namespace
 
+Expr *
+clang::extractElementInitializerFromNestedAILE(const ArrayInitLoopExpr *AILE) {
+  if (!AILE)
+    return nullptr;
+
+  Expr *AILEInit = AILE->getSubExpr();
+  while (const auto *E = dyn_cast<ArrayInitLoopExpr>(AILEInit))
+    AILEInit = E->getSubExpr();
+
+  return AILEInit;
+}
+
 inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder,
                                      const Stmt *stmt) const {
   return builder.alwaysAdd(stmt) || kind == AlwaysAdd;
 }
 
 bool CFGBuilder::alwaysAdd(const Stmt *stmt) {
   bool shouldAdd = BuildOpts.alwaysAdd(stmt);
 
CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) {
   }
 
   autoCreateBlock();
   appendInitializer(Block, I);
 
   if (Init) {
     // 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);
+    auto *AILEInit = extractElementInitializerFromNestedAILE(
+        dyn_cast<ArrayInitLoopExpr>(Init));
 
     findConstructionContexts(
         ConstructionContextLayer::create(cfg->getBumpVectorContext(), I),
-        AILE ? AILE->getSubExpr() : Init);
+        AILEInit ? AILEInit : Init);
 
     if (HasTemporaries) {
       // For expression with temporaries go directly to subexpression to omit
       // generating destructors for the second time.
       return Visit(cast<ExprWithCleanups>(Init)->getSubExpr());
     }
     if (BuildOpts.AddCXXDefaultInitExprInCtors) {
       if (CXXDefaultInitExpr *Default = dyn_cast<CXXDefaultInitExpr>(Init)) {
CFGBlock *CFGBuilder::VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc) {
 
   unsigned Idx = 0;
   for (LambdaExpr::capture_init_iterator it = E->capture_init_begin(),
                                          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);
+      auto *AILEInit = extractElementInitializerFromNestedAILE(
+          dyn_cast<ArrayInitLoopExpr>(Init));
 
       findConstructionContexts(ConstructionContextLayer::create(
                                    cfg->getBumpVectorContext(), {E, Idx}),
-                               AILE ? AILE->getSubExpr() : Init);
+                               AILEInit ? AILEInit : Init);
 
       CFGBlock *Tmp = Visit(Init);
       if (Tmp)
         LastBlock = Tmp;
     }
   }
   return LastBlock;
 }

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

if (TrimInterval != 0) {
     G.enableNodeReclamation(TrimInterval);
   }
 }
 
 //===----------------------------------------------------------------------===//
 // Utility methods.
 //===----------------------------------------------------------------------===//
 
 ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) {
   ProgramStateRef state = StateMgr.getInitialState(InitLoc);
   const Decl *D = InitLoc->getDecl();
 
   // Preconditions.
   // FIXME: It would be nice if we had a more general mechanism to add
   // such preconditions.  Some day.
   do {
     if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
       // Precondition: the first argument of 'main' is an integer guaranteed
ExprEngine::addObjectUnderConstruction(ProgramStateRef State,
 
   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().
+  // getSubExpr(). Note that AILEs can be nested in case of
+  // multidimesnional arrays.
   if (const auto *AILE = dyn_cast_or_null<ArrayInitLoopExpr>(Init))
-    Init = AILE->getSubExpr();
+    Init = extractElementInitializerFromNestedAILE(AILE);
 
   // FIXME: Currently the state might already contain the marker due to
   // incorrect handling of temporaries bound to default parameters.
   // The state will already contain the marker if we construct elements
   // in an array, as we visit the same statement multiple times before
   // the array declaration. The marker is removed when we exit the
   // constructor call.
   assert((!State->get<ObjectsUnderConstruction>(Key) ||
           Key.getItem().getKind() ==
               ConstructionContextItem::TemporaryDestructorKind ||

clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

bindRequiredArrayElementToEnvironment(ProgramStateRef State,
   //   `-CXXConstructExpr
   //     `-ArraySubscriptExpr
   //       |-ImplicitCastExpr
   //       | `-OpaqueValueExpr
   //       |   `-MemberExpr
   //       |     `-DeclRefExpr
   //       `-ArrayInitIndexExpr
   //
+  // The resulting expression for a multidimensional array.
+  // ArrayInitLoopExpr                  <-- we're here
+  // |-OpaqueValueExpr
+  // | `-DeclRefExpr                    <-- match this
+  // `-ArrayInitLoopExpr
+  //   |-OpaqueValueExpr
+  //   | `-ArraySubscriptExpr
+  //   |   |-ImplicitCastExpr
+  //   |   | `-OpaqueValueExpr
+  //   |   |   `-DeclRefExpr
+  //   |   `-ArrayInitIndexExpr
+  //   `-CXXConstructExpr             <-- extract this
+  //     ` ...
+
+  const auto *OVESrc = AILE->getCommonExpr()->getSourceExpr();
+
   // HACK: There is no way we can put the index of the array element into the
   // CFG unless we unroll the loop, so we manually select and bind the required
   // parameter to the environment.
-  const auto *CE = cast<CXXConstructExpr>(AILE->getSubExpr());
-  const auto *OVESrc = AILE->getCommonExpr()->getSourceExpr();
+  const auto *CE =
+      cast<CXXConstructExpr>(extractElementInitializerFromNestedAILE(AILE));
 
   SVal Base = UnknownVal();
   if (const auto *ME = dyn_cast<MemberExpr>(OVESrc))
     Base = State->getSVal(ME, LCtx);
-  else if (const auto *DRE = cast<DeclRefExpr>(OVESrc))
+  else if (const auto *DRE = dyn_cast<DeclRefExpr>(OVESrc))
     Base = State->getLValue(cast<VarDecl>(DRE->getDecl()), LCtx);
   else
     llvm_unreachable("ArrayInitLoopExpr contains unexpected source expression");
 
   SVal NthElem = State->getLValue(CE->getType(), Idx, Base);
 
   return State->BindExpr(CE->getArg(0), LCtx, NthElem);
 }
 
 void ExprEngine::handleConstructor(const Expr *E,
                                    ExplodedNode *Pred,
                                    ExplodedNodeSet &destNodes) {
   const auto *CE = dyn_cast<CXXConstructExpr>(E);
   const auto *CIE = dyn_cast<CXXInheritedCtorInitExpr>(E);
   assert(CE || CIE);
 
   const LocationContext *LCtx = Pred->getLocationContext();
   ProgramStateRef State = Pred->getState();
 
   SVal Target = UnknownVal();
 
   if (CE) {
     if (Optional<SVal> ElidedTarget =
             getObjectUnderConstruction(State, CE, LCtx)) {
       // We've previously modeled an elidable constructor by pretending that it
       // in fact constructs into the correct target. This constructor can
       // therefore be skipped.
       Target = *ElidedTarget;
       StmtNodeBuilder Bldr(Pred, destNodes, *currBldrCtx);
       State = finishObjectConstruction(State, CE, LCtx);
       if (auto L = Target.getAs<Loc>())
case CXXConstructExpr::CK_Complete: {
     if (CE->getType()->isArrayType() || AILE) {
       Idx = getIndexOfElementToConstruct(State, CE, LCtx).value_or(0u);
       State = setIndexOfElementToConstruct(State, CE, LCtx, Idx + 1);
     }
 
     if (AILE) {
       // Only set this once even though we loop through it multiple times.
       if (!getPendingInitLoop(State, CE, LCtx))
-        State = setPendingInitLoop(State, CE, LCtx,
-                                   AILE->getArraySize().getLimitedValue());
+        State = setPendingInitLoop(
+            State, CE, LCtx,
+            getContext().getArrayInitLoopExprElementCount(AILE));
 
       State = bindRequiredArrayElementToEnvironment(
           State, AILE, LCtx, svalBuilder.makeArrayIndex(Idx));
     }
 
     // The target region is found from construction context.
     std::tie(State, Target) =
         handleConstructionContext(CE, State, LCtx, CC, CallOpts, Idx);
for (LambdaExpr::const_capture_init_iterator i = LE->capture_init_begin(),
     SVal InitVal;
     if (!FieldForCapture->hasCapturedVLAType()) {
       const Expr *InitExpr = *i;
 
       assert(InitExpr && "Capture missing initialization expression");
 
       // With C++17 copy elision the InitExpr can be anything, so instead of
       // pattern matching all cases, we simple check if the current field is
       // under construction or not, regardless what it's InitExpr is.
       if (const auto OUC =
               getObjectUnderConstruction(State, {LE, Idx}, LocCtxt)) {
         InitVal = State->getSVal(OUC->getAsRegion());
 
         State = finishObjectConstruction(State, {LE, Idx}, LocCtxt);
       } else
         InitVal = State->getSVal(InitExpr, LocCtxt);
 
     } else {

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

void move_ctor_init_non_pod() {
 
   S5 moved = (S5 &&) orig;
 
   clang_analyzer_eval(moved.arr[0].i == 3); // expected-warning{{TRUE}}
   clang_analyzer_eval(moved.arr[1].i == 4); // expected-warning{{TRUE}}
   clang_analyzer_eval(moved.arr[2].i == 5); // expected-warning{{TRUE}}
   clang_analyzer_eval(moved.arr[3].i == 6); // expected-warning{{TRUE}}
 }
+
+//Note: This is the only solution I could find to check the values without 
+// crashing clang. For more details on the crash see Issue #57135.
+void lambda_capture_multi_array() {
+  S3 arr[2][2] = {1,2,3,4};
+
+  {
+    int x = [arr] { return arr[0][0].i; }();
+    clang_analyzer_eval(x == 1); // expected-warning{{TRUE}}
+  }
+
+  {
+    int x = [arr] { return arr[0][1].i; }();
+    clang_analyzer_eval(x == 2); // expected-warning{{TRUE}}
+  }
+
+  {
+    int x = [arr] { return arr[1][0].i; }();
+    clang_analyzer_eval(x == 3); // expected-warning{{TRUE}}
+  }
+
+  {
+    int x = [arr] { return arr[1][1].i; }();
+    clang_analyzer_eval(x == 4); // expected-warning{{TRUE}}
+  }
+}
+
+// This struct will force constructor inlining in MultiWrapper.
+struct UserDefinedCtor {
+  int i;
+  UserDefinedCtor() {}
+  UserDefinedCtor(const UserDefinedCtor &copy) {
+    int j = 1;
+    i = copy.i;
+  }
+};
+
+struct MultiWrapper {
+  UserDefinedCtor arr[2][2];
+};
+
+void copy_ctor_multi() {
+  MultiWrapper MW;
+
+  MW.arr[0][0].i = 0;
+  MW.arr[0][1].i = 1;
+  MW.arr[1][0].i = 2;
+  MW.arr[1][1].i = 3;
+
+  MultiWrapper MWCopy = MW;
+  
+  clang_analyzer_eval(MWCopy.arr[0][0].i == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(MWCopy.arr[0][1].i == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(MWCopy.arr[1][0].i == 2); // expected-warning{{TRUE}}
+  clang_analyzer_eval(MWCopy.arr[1][1].i == 3); // expected-warning{{TRUE}}
+} 
+
+void move_ctor_multi() {
+  MultiWrapper MW;
+
+  MW.arr[0][0].i = 0;
+  MW.arr[0][1].i = 1;
+  MW.arr[1][0].i = 2;
+  MW.arr[1][1].i = 3;
+
+  MultiWrapper MWMove = (MultiWrapper &&) MW;
+  
+  clang_analyzer_eval(MWMove.arr[0][0].i == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(MWMove.arr[0][1].i == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(MWMove.arr[1][0].i == 2); // expected-warning{{TRUE}}
+  clang_analyzer_eval(MWMove.arr[1][1].i == 3); // expected-warning{{TRUE}}
+} 
+
+void structured_binding_multi() {
+  S3 arr[2][2] = {1,2,3,4};
+
+  auto [a,b] = arr;
+
+  clang_analyzer_eval(a[0].i == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(a[1].i == 2); // expected-warning{{TRUE}}
+  clang_analyzer_eval(b[0].i == 3); // expected-warning{{TRUE}}
+  clang_analyzer_eval(b[1].i == 4); // expected-warning{{TRUE}}
+}