[analyzer] LoopUnrolling: fix crash when a loop counter is captured in a lambda by reference

[steakhal]

I'm gonna have a look at this tomorrow.

[vsavchenko]

Great job on the patch! Thanks!

clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

165–198

One thought here.
I think it's better to not have implicit connections between parameters that are not obvious to the user of the function (or to the person who is going to modify this function in the future). Here we always have VD = DR->getDecl()->getCanonicalDecl(). So, IMO, the interface of this function will be much cleaner if we accept only a DeclRefExpr.

184–185

But actually, it's a bit different with this one. I don't know exact details and rules how clang sema fills in the class for lambda.
According to cppreference:

For the entities that are captured by reference (with the default capture [&] or when using the character &, e.g. [&a, &b, &c]), it is unspecified if additional data members are declared in the closure type

It can be pretty much specified in clang, that's true, but it looks like in DeadStoreChecker we have a very similar situation and we do not assume that captured variable always have a corresponding field.

187–190

There is a general rule in LLVM's style guide of trying to minimize nestedness of if's, forms and so on.
In this particular situation this assertion can be more local: assert(MD && MD->getParent()->isLambda() & ...);.
This way it is more obvious what it checks and we avoid confusion while reading this function because if (condition) automatically means that !condition is something that might happen.
The same applies to another assertion here.

201–202

I think that this comment has to be updated now.

201–202

I think this whole section is less obvious now and requires one good solid comment explaining what are the different situations here, what is "entry" and so on.

[steakhal]

By checking the line coverage of the LoopUnrolling.cpp test file, looks like all lines are covered you touched.

There are only two return statements uncovered though: L200, L251.
We should consider extending this test file to cover them as well in a follow-up patch.

[AbbasSabra]

Updating D102273: [analyzer] Apply code review

[AbbasSabra]

clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

184–185

Yes, I based this on the fact that DeadStoreChecker considers it possible, but I have never faced a case where it does not have a corresponding field.

[vsavchenko]

Thanks for addressing my comments! I still have some left though

clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

170

dyn_cast_or_null also tells the reader that D can be null and can be not CXXMethodDecl. So it's better to use cast here if you are sure about D and have assertions about it.

174–177

Body of this function seems to be too dense. It is usually hard to read something that doesn't have rest places for eyes. You can think of it as paragraphs in the written text.
In this particular situation, you can split all these statements and declarations in groups of 3-4. It would be perfect if they are grouped semantically (like good paragraphs).

178

We can just do cast here

184–185

I still think that we should do something about this else

191–192

I think it's a great idea to list all the cases. I think we can go even further: enumerate them and actually pinpoint in the implementation where we cover which case. With numbers it can be much easier.

193

Can we not introduce new terms and simply call it a reference?

196

This should be also modified then

[vsavchenko]

clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

184–185

It still would be good to have some proof that it is indeed like this or simply fallback into returning true (which you already do when in doubt).

[AbbasSabra]

Updating D102273: [analyzer] Apply code review part 2

[AbbasSabra]

clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

184–185

As I said, I believe it cannot happen but I assumed based on the other checker that there is something I don't know.
I think based on getCaptureFields the implementation we are iterating over all captures. For that algorithm to work number of captures should be equal to number of fields

void CXXRecordDecl::getCaptureFields(
       llvm::DenseMap<const VarDecl *, FieldDecl *> &Captures,
       FieldDecl *&ThisCapture) const {
  Captures.clear();
  ThisCapture = nullptr;

  LambdaDefinitionData &Lambda = getLambdaData();
  RecordDecl::field_iterator Field = field_begin();
  for (const LambdaCapture *C = Lambda.Captures, *CEnd = C + Lambda.NumCaptures;
       C != CEnd; ++C, ++Field) {
    if (C->capturesThis())
      ThisCapture = *Field;
    else if (C->capturesVariable())
      Captures[C->getCapturedVar()] = *Field;
  }
  assert(Field == field_end());
}

I dropped the defensive code

[AbbasSabra]

Updating D102273: [analyzer] Update comments + fix typos

[NoQ]

I've just been patching up clang-tidy's infinite loop checker and the problem sounds soooo similar. Maybe we should move clang-tidy's alias analysis into libAnalysis and re-use it?

[AbbasSabra]

In D102273#2766531, @NoQ wrote:

I've just been patching up clang-tidy's infinite loop checker and the problem sounds soooo similar. Maybe we should move clang-tidy's alias analysis into libAnalysis and re-use it?

I'm not familiar with clang-tidy's alias analysis. Do you think it should be part of this patch? or a follow-up one?

[AbbasSabra]

Note: I don't have the right to re-run the failed build/test. I assume that it is not related to my change since the test compile and runs omp code(Static analyzer doesn't run on that test)

[AbbasSabra]

ping

[AbbasSabra]

ping

[AbbasSabra]

@vsavchenko any update on this?

[vsavchenko]

Great! Thanks for addressing all of the comments!

clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

184–185

OK, sounds reasonable!

[AbbasSabra]

In D102273#2866532, @vsavchenko wrote:

Great! Thanks for addressing all of the comments!

Thank you for the review! Can you take care of merging it? I don't have the required permission.

clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

 
 ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) {
   auto LS = State->get<LoopStack>();
   if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt)
     State = State->set<LoopStack>(LS.getTail());
   return State;
 }
 
-static internal::Matcher<Stmt> simpleCondition(StringRef BindName) {
-  return binaryOperator(anyOf(hasOperatorName("<"), hasOperatorName(">"),
-                              hasOperatorName("<="), hasOperatorName(">="),
-                              hasOperatorName("!=")),
-                        hasEitherOperand(ignoringParenImpCasts(declRefExpr(
-                            to(varDecl(hasType(isInteger())).bind(BindName))))),
-                        hasEitherOperand(ignoringParenImpCasts(
-                            integerLiteral().bind("boundNum"))))
+static internal::Matcher<Stmt> simpleCondition(StringRef BindName,
+                                               StringRef RefName) {
+  return binaryOperator(
+             anyOf(hasOperatorName("<"), hasOperatorName(">"),
+                 declRefExpr(to(varDecl(hasType(isInteger())).bind(BindName)))
+                     .bind(RefName))),
+             hasEitherOperand(
+                 ignoringParenImpCasts(integerLiteral().bind("boundNum"))))
       .bind("conditionOperator");
 }
 
 static internal::Matcher<Stmt>
 changeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher) {
   return anyOf(
       unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")),
                     hasUnaryOperand(ignoringParenImpCasts(
return hasDescendant(stmt(
             changeIntBoundNode(equalsBoundNode(std::string(NodeName))),
             callByRef(equalsBoundNode(std::string(NodeName))),
             getAddrTo(equalsBoundNode(std::string(NodeName))),
             assignedToRef(equalsBoundNode(std::string(NodeName))))));
 }
 
 static internal::Matcher<Stmt> forLoopMatcher() {
   return forStmt(
-             hasCondition(simpleCondition("initVarName")),
+             hasCondition(simpleCondition("initVarName", "initVarRef")),
              // Initialization should match the form: 'int i = 6' or 'i = 42'.
              hasLoopInit(
                  anyOf(declStmt(hasSingleDecl(
                            varDecl(allOf(hasInitializer(ignoringParenImpCasts(
                                              integerLiteral().bind("initNum"))),
                                          equalsBoundNode("initVarName"))))),
                        binaryOperator(hasLHS(declRefExpr(to(varDecl(
                                           equalsBoundNode("initVarName"))))),
                                       hasRHS(ignoringParenImpCasts(
                                           integerLiteral().bind("initNum")))))),
              // Incrementation should be a simple increment or decrement
              // operator call.
              hasIncrement(unaryOperator(
                  anyOf(hasOperatorName("++"), hasOperatorName("--")),
                  hasUnaryOperand(declRefExpr(
                      to(varDecl(allOf(equalsBoundNode("initVarName"),
                                       hasType(isInteger())))))))),
-             unless(hasBody(hasSuspiciousStmt("initVarName")))).bind("forLoop");
+             unless(hasBody(hasSuspiciousStmt("initVarName"))))
+      .bind("forLoop");
 }
 
-static bool isPossiblyEscaped(const VarDecl *VD, ExplodedNode *N) {
-  // Global variables assumed as escaped variables.
+static bool isCapturedByReference(ExplodedNode *N, const DeclRefExpr *DR) {
+
+  // Get the lambda CXXRecordDecl
+  assert(DR->refersToEnclosingVariableOrCapture());
+  const LocationContext *LocCtxt = N->getLocationContext();
+  const Decl *D = LocCtxt->getDecl();
+  const auto *MD = cast<CXXMethodDecl>(D);
+  assert(MD && MD->getParent()->isLambda() &&
+         "Captured variable should only be seen while evaluating a lambda");
+  const CXXRecordDecl *LambdaCXXRec = MD->getParent();
+
+  // Lookup the fields of the lambda
+  llvm::DenseMap<const VarDecl *, FieldDecl *> LambdaCaptureFields;
+  FieldDecl *LambdaThisCaptureField;
+  LambdaCXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField);
+
+  // Check if the counter is captured by reference
+  const VarDecl *VD = cast<VarDecl>(DR->getDecl()->getCanonicalDecl());
+  assert(VD);
+  const FieldDecl *FD = LambdaCaptureFields[VD];
+  assert(FD && "Captured variable without a corresponding field");
+  return FD->getType()->isReferenceType();
+}
+
+// A loop counter is considered escaped if:
+// case 1: It is a global variable.
+// case 2: It is a reference parameter or a reference capture.
+// case 3: It is assigned to a non-const reference variable or parameter.
+// case 4: Has its address taken.
+static bool isPossiblyEscaped(ExplodedNode *N, const DeclRefExpr *DR) {
+  const VarDecl *VD = cast<VarDecl>(DR->getDecl()->getCanonicalDecl());
+  assert(VD);
+  // Case 1:
   if (VD->hasGlobalStorage())
     return true;
 
-  const bool isParm = isa<ParmVarDecl>(VD);
-  // Reference parameters are assumed as escaped variables.
-  if (isParm && VD->getType()->isReferenceType())
+  const bool IsRefParamOrCapture =
+      isa<ParmVarDecl>(VD) || DR->refersToEnclosingVariableOrCapture();
+  // Case 2:
+  if ((DR->refersToEnclosingVariableOrCapture() &&
+       isCapturedByReference(N, DR)) ||
+      (IsRefParamOrCapture && VD->getType()->isReferenceType()))
     return true;
 
   while (!N->pred_empty()) {
     // FIXME: getStmtForDiagnostics() does nasty things in order to provide
     // a valid statement for body farms, do we need this behavior here?
     const Stmt *S = N->getStmtForDiagnostics();
     if (!S) {
       N = N->getFirstPred();
       continue;
     }
 
     if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) {
       for (const Decl *D : DS->decls()) {
         // Once we reach the declaration of the VD we can return.
         if (D->getCanonicalDecl() == VD)
           return false;
       }
     }
     // Check the usage of the pass-by-ref function calls and adress-of operator
     // on VD and reference initialized by VD.
     ASTContext &ASTCtx =
         N->getLocationContext()->getAnalysisDeclContext()->getASTContext();
+    // Case 3 and 4:
     auto Match =
         match(stmt(anyOf(callByRef(equalsNode(VD)), getAddrTo(equalsNode(VD)),
                          assignedToRef(equalsNode(VD)))),
               *S, ASTCtx);
     if (!Match.empty())
       return true;
 
     N = N->getFirstPred();
   }
 
-  // Parameter declaration will not be found.
-  if (isParm)
+  // Reference parameter and reference capture will not be found.
+  if (IsRefParamOrCapture)
     return false;
 
   llvm_unreachable("Reached root without finding the declaration of VD");
 }
 
 bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
                             ExplodedNode *Pred, unsigned &maxStep) {
 
   if (!isLoopStmt(LoopStmt))
     return false;
 
   // TODO: Match the cases where the bound is not a concrete literal but an
   // integer with known value
   auto Matches = match(forLoopMatcher(), *LoopStmt, ASTCtx);
   if (Matches.empty())
     return false;
 
-  auto CounterVar = Matches[0].getNodeAs<VarDecl>("initVarName");
+  const auto *CounterVarRef = Matches[0].getNodeAs<DeclRefExpr>("initVarRef");
   llvm::APInt BoundNum =
       Matches[0].getNodeAs<IntegerLiteral>("boundNum")->getValue();
   llvm::APInt InitNum =
       Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue();
   auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator");
   if (InitNum.getBitWidth() != BoundNum.getBitWidth()) {
     InitNum = InitNum.zextOrSelf(BoundNum.getBitWidth());
     BoundNum = BoundNum.zextOrSelf(InitNum.getBitWidth());
   }
 
   if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE)
     maxStep = (BoundNum - InitNum + 1).abs().getZExtValue();
   else
     maxStep = (BoundNum - InitNum).abs().getZExtValue();
 
   // Check if the counter of the loop is not escaped before.
-  return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred);
+  return !isPossiblyEscaped(Pred, CounterVarRef);
 }
 
 bool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt) {
   const Stmt *S = nullptr;
   while (!N->pred_empty()) {
     if (N->succ_size() > 1)
       return true;
 

clang/test/Analysis/loop-unrolling.cpp

-// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true -verify -std=c++11 -analyzer-config exploration_strategy=unexplored_first_queue %s
-// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true,exploration_strategy=dfs -verify -std=c++11 -DDFS=1 %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true -verify -std=c++14 -analyzer-config exploration_strategy=unexplored_first_queue %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true,exploration_strategy=dfs -verify -std=c++14 -DDFS=1 %s
 
 void clang_analyzer_numTimesReached();
 void clang_analyzer_warnIfReached();
 
 int getNum();
 void foo(int &);
 
 int simple_unroll1() {
void parm_by_value_as_loop_counter(int i) {
   }
 }
 
 void parm_by_ref_as_loop_counter(int &i) {
   for (i = 0; i < 10; ++i) {
     clang_analyzer_numTimesReached(); // expected-warning {{4}}
   }
 }
+
+void capture_by_value_as_loop_counter() {
+  int out = 0;
+  auto l = [i = out]() mutable {
+    for (i = 0; i < 10; ++i) {
+      clang_analyzer_numTimesReached(); // expected-warning {{10}}
+    }
+  };
+}
+
+void capture_by_ref_as_loop_counter() {
+  int out = 0;
+  auto l = [&i = out]() {
+    for (i = 0; i < 10; ++i) {
+      clang_analyzer_numTimesReached(); // expected-warning {{4}}
+    }
+  };
+}
+
+void capture_implicitly_by_value_as_loop_counter() {
+  int i = 0;
+  auto l = [=]() mutable {
+    for (i = 0; i < 10; ++i) {
+      clang_analyzer_numTimesReached(); // expected-warning {{10}}
+    }
+  };
+}
+
+void capture_implicitly_by_ref_as_loop_counter() {
+  int i = 0;
+  auto l = [&]() mutable {
+    for (i = 0; i < 10; ++i) {
+      clang_analyzer_numTimesReached(); // expected-warning {{4}}
+    }
+  };
+}