[Static Analyzer] Lambda support.

[xazax.hun]

Summary

This patch adds lambda support to the static analyzer.
All of my initial tests are passed.

Before this patch each time a LambdaExpr was encountered a sink node was generated. This also reduced the coverage of code that is actually not inside a lambda operator(). Also the lack of lambda support is a known cause of some false positives (for example in the dead store checker).

This is a work in progress version of this patch, I will move this feature behind a flag and run it on LLVM to make sure it is also tested with real world code.

[xazax.hun]

• Updated to newest trunk.
• Moved the feature behind an option.
• Fixed a crash when an operator() of a lambda is analyzed as a top level function, and a ThisExpr is referring to the this in the enclosing scope (this can only happen when lambda support is turned off).
• Added a new test case for nested lambdas capturing 'this'.

[zaks.anna]

Have you tested this on a large codebase that uses lambdas? When do you think we should turn this on by default?

Please, add test cases that demonstrate what happens when an issue is reported within a lambda and to check if inlined defensive checks work.

(As a follow up to this patch, we may need to teach LiveVariables.cpp and UninitializedValues.cpp about lambdas. For example, to address issues like this one: https://llvm.org/bugs/show_bug.cgi?id=22834)

[xazax.hun]

• Updated to latest trunk
• Added test for the defensive inline check heuristic case
• Added test for diagnostic within a lambda body
• Added test for path notes

[xazax.hun]

In D12652#243762, @zaks.anna wrote:

Have you tested this on a large codebase that uses lambdas? When do you think we should turn this on by default?

I checked llvm and clang and did not found any failure. There are no obvious limitations or problems that I know of at the moment. I think this is a good candidate to turn on by default. At least some potential errors might be found earlier.

Please, add test cases that demonstrate what happens when an issue is reported within a lambda and to check if inlined defensive checks work.

I extended the tests with these cases.

(As a follow up to this patch, we may need to teach LiveVariables.cpp and UninitializedValues.cpp about lambdas. For example, to address issues like this one: https://llvm.org/bugs/show_bug.cgi?id=22834)

[zaks.anna]

Please, do turn on by default.
LGTM

[jordan_rose]

A few comments coming late…

include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

515–517

"inline" is kind of a misnomer, since we may not actually inline lambdas. I would have suggested "model lambdas" or "lambda support".

lib/StaticAnalyzer/Core/MemRegion.cpp

740–742

Why the extra parameter?

[xazax.hun]

include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

515–517

Even when this configuration option is set to false, the body of the lambda is analyzed as a top level function. For this reason I think the "lambda support" might be a misnomer too. What do you think?

lib/StaticAnalyzer/Core/MemRegion.cpp

740–742

This is just a leftover from code evolution, thank you for spotting this.

[xazax.hun]

include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

515–517

If we come up with a better name for the option I will address that in a separate patch.

[zaks.anna]

Looks like this patch is causing regressions:
https://llvm.org/bugs/show_bug.cgi?id=24914

[xazax.hun]

I will look into it. Do you prefer to revert the patch this it is fixed?

include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

private:
   Optional<unsigned> GraphTrimInterval;
 
   /// \sa getMaxTimesInlineLarge
   Optional<unsigned> MaxTimesInlineLarge;
 
   /// \sa getMaxNodesPerTopLevelFunction
   Optional<unsigned> MaxNodesPerTopLevelFunction;
 
+  /// \sa shouldInlineLambdas
+  Optional<bool> InlineLambdas;
+
   /// A helper function that retrieves option for a given full-qualified
   /// checker name.
   /// Options for checkers can be specified via 'analyzer-config' command-line
   /// option.
   /// Example:
   /// @code-analyzer-config unix.Malloc:OptionName=CheckerOptionValue @endcode
   /// or @code-analyzer-config unix:OptionName=GroupOptionValue @endcode
   /// for groups of checkers.
public:
 
   /// Returns the maximum number of nodes the analyzer can generate while
   /// exploring a top level function (for each exploded graph).
   /// 150000 is default; 0 means no limit.
   ///
   /// This is controlled by the 'max-nodes' config option.
   unsigned getMaxNodesPerTopLevelFunction();
 
+  /// Returns true if lambdas should be inlined. Otherwise a sink node will be
+  /// generated each time a LambdaExpr is visited.
+  bool shouldInlineLambdas();
+
 public:
   AnalyzerOptions() :
     AnalysisStoreOpt(RegionStoreModel),
     AnalysisConstraintsOpt(RangeConstraintsModel),
     AnalysisDiagOpt(PD_HTML),
     AnalysisPurgeOpt(PurgeStmt),
     DisableAllChecks(0),
     ShowCheckerHelp(0),

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

public:
   /// VisitMSAsmStmt - Transfer function logic for MS inline asm.
   void VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
                       ExplodedNodeSet &Dst);
 
   /// VisitBlockExpr - Transfer function logic for BlockExprs.
   void VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred, 
                       ExplodedNodeSet &Dst);
 
+  /// VisitLambdaExpr - Transfer function logic for LambdaExprs.
+  void VisitLambdaExpr(const LambdaExpr *LE, ExplodedNode *Pred, 
+                       ExplodedNodeSet &Dst);
+
   /// VisitBinaryOperator - Transfer function logic for binary operators.
   void VisitBinaryOperator(const BinaryOperator* B, ExplodedNode *Pred, 
                            ExplodedNodeSet &Dst);
 
 
   /// VisitCall - Transfer function for function calls.
   void VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred,
                      ExplodedNodeSet &Dst);

lib/StaticAnalyzer/Core/AnalyzerOptions.cpp

 
 bool AnalyzerOptions::shouldPrunePaths() {
   return getBooleanOption("prune-paths", true);
 }
 
 bool AnalyzerOptions::shouldConditionalizeStaticInitializers() {
   return getBooleanOption("cfg-conditional-static-initializers", true);
 }
+
+bool AnalyzerOptions::shouldInlineLambdas() {
+  return getBooleanOption("inline-lambdas", /*Default=*/false);
+}

lib/StaticAnalyzer/Core/ExprEngine.cpp

switch (S->getStmtClass()) {
     case Stmt::TypoExprClass:
     case Stmt::CXXNoexceptExprClass:
     case Stmt::PackExpansionExprClass:
     case Stmt::SubstNonTypeTemplateParmPackExprClass:
     case Stmt::FunctionParmPackExprClass:
     case Stmt::SEHTryStmtClass:
     case Stmt::SEHExceptStmtClass:
     case Stmt::SEHLeaveStmtClass:
-    case Stmt::LambdaExprClass:
     case Stmt::SEHFinallyStmtClass: {
       const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
       Engine.addAbortedBlock(node, currBldrCtx->getBlock());
       break;
     }
 
     case Stmt::ParenExprClass:
       llvm_unreachable("ParenExprs already handled.");
case Stmt::MSAsmStmtClass:
       break;
 
     case Stmt::BlockExprClass:
       Bldr.takeNodes(Pred);
       VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);
       Bldr.addNodes(Dst);
       break;
 
+    case Stmt::LambdaExprClass:
+      if (AMgr.options.shouldInlineLambdas()) {
+        Bldr.takeNodes(Pred);
+        VisitLambdaExpr(cast<LambdaExpr>(S), Pred, Dst);
+        Bldr.addNodes(Dst);
+      } else {
+        const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
+        Engine.addAbortedBlock(node, currBldrCtx->getBlock());
+      }
+      break;
+
     case Stmt::BinaryOperatorClass: {
       const BinaryOperator* B = cast<BinaryOperator>(S);
       if (B->isLogicalOp()) {
         Bldr.takeNodes(Pred);
         VisitLogicalExpr(B, Pred, Dst);
         Bldr.addNodes(Dst);
         break;
       }
void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
 
   ProgramStateRef state = Pred->getState();
   const LocationContext *LCtx = Pred->getLocationContext();
 
   if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
     // C permits "extern void v", and if you cast the address to a valid type,
     // you can even do things with it. We simply pretend
     assert(Ex->isGLValue() || VD->getType()->isVoidType());
-    SVal V = state->getLValue(VD, Pred->getLocationContext());
+    const LocationContext *LocCtxt = Pred->getLocationContext();
+    const Decl *D = LocCtxt->getDecl();
+    const auto *MD = D ? dyn_cast<CXXMethodDecl>(D) : nullptr;
+    const auto *DeclRefEx = dyn_cast<DeclRefExpr>(Ex);
+    SVal V;
+    bool CaptureByReference = false;
+    if (AMgr.options.shouldInlineLambdas() && DeclRefEx &&
+        DeclRefEx->refersToEnclosingVariableOrCapture() && MD &&
+        MD->getParent()->isLambda()) {
+      // Lookup the field of the lambda.
+      const CXXRecordDecl *CXXRec = MD->getParent();
+      llvm::DenseMap<const VarDecl *, FieldDecl *> LambdaCaptureFields;
+      FieldDecl *LambdaThisCaptureField;
+      CXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField);
+      const FieldDecl *FD = LambdaCaptureFields[VD];
+      Loc CXXThis =
+          svalBuilder.getCXXThis(MD, LocCtxt->getCurrentStackFrame());
+      SVal CXXThisVal = state->getSVal(CXXThis);
+      V = state->getLValue(FD, CXXThisVal);
+      if (FD->getType()->isReferenceType() &&
+          !VD->getType()->isReferenceType())
+        CaptureByReference = true;
+    } else {
+      V = state->getLValue(VD, LocCtxt);
+    }
 
     // For references, the 'lvalue' is the pointer address stored in the
     // reference region.
-    if (VD->getType()->isReferenceType()) {
+    if (VD->getType()->isReferenceType() || CaptureByReference) {
       if (const MemRegion *R = V.getAsRegion())
         V = state->getSVal(R);
       else
         V = UnknownVal();
     }
 
     Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
                       ProgramPoint::PostLValueKind);

lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

const MemRegion *R =
     svalBuilder.getRegionManager().getCXXThisRegion(
                                   getContext().getCanonicalType(TE->getType()),
                                                     LCtx);
 
   ProgramStateRef state = Pred->getState();
   SVal V = state->getSVal(loc::MemRegionVal(R));
   Bldr.generateNode(TE, Pred, state->BindExpr(TE, LCtx, V));
 }
+
+void ExprEngine::VisitLambdaExpr(const LambdaExpr *LE, ExplodedNode *Pred,
+                                 ExplodedNodeSet &Dst) {
+  const LocationContext *LocCtxt = Pred->getLocationContext();
+
+  // Get the region of the lambda itself.
+  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.
+  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) {
+    SVal Field = State->getLValue(*CurField, V);
+    SVal InitExpr = State->getSVal(*i, LocCtxt);
+    State = State->bindLoc(Field, InitExpr);
+  }
+
+  // Decay the Loc into an RValue, because there might be a
+  // MaterializeTemporaryExpr node above this one which expects the bound value
+  // to be an RValue.
+  SVal LambdaRVal = State->getSVal(R);
+
+  ExplodedNodeSet Tmp;
+  StmtNodeBuilder Bldr(Pred, Tmp, *currBldrCtx);
+  // FIXME: is this the right program point kind?
+  Bldr.generateNode(LE, Pred,
+                    State->BindExpr(LE, LocCtxt, LambdaRVal),
+                    nullptr, ProgramPoint::PostLValueKind);
+
+  // FIXME: Move all post/pre visits to ::Visit().
+  getCheckerManager().runCheckersForPostStmt(Dst, Tmp, LE, *this);
+}

lib/StaticAnalyzer/Core/MemRegion.cpp

 }
 
 /// Look through a chain of LocationContexts to either find the
 /// StackFrameContext that matches a DeclContext, or find a VarRegion
 /// for a variable captured by a block.
 static llvm::PointerUnion<const StackFrameContext *, const VarRegion *>
 getStackOrCaptureRegionForDeclContext(const LocationContext *LC,
                                       const DeclContext *DC,
-                                      const VarDecl *VD) {
+                                      const VarDecl *VD,
+                                      MemRegionManager *Mmgr) {
   while (LC) {
     if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) {
       if (cast<DeclContext>(SFC->getDecl()) == DC)
         return SFC;
     }
     if (const BlockInvocationContext *BC =
         dyn_cast<BlockInvocationContext>(LC)) {
       const BlockDataRegion *BR =
         static_cast<const BlockDataRegion*>(BC->getContextData());
if (D->hasGlobalStorage() && !D->isStaticLocal()) {
     }
 
   // Finally handle static locals.
   } else {
     // FIXME: Once we implement scope handling, we will need to properly lookup
     // 'D' to the proper LocationContext.
     const DeclContext *DC = D->getDeclContext();
     llvm::PointerUnion<const StackFrameContext *, const VarRegion *> V =
-      getStackOrCaptureRegionForDeclContext(LC, DC, D);
+      getStackOrCaptureRegionForDeclContext(LC, DC, D, this);
 
     if (V.is<const VarRegion*>())
       return V.get<const VarRegion*>();
 
     const StackFrameContext *STC = V.get<const StackFrameContext*>();
 
     if (!STC)
       sReg = getUnknownRegion();
MemRegionManager::getCXXBaseObjectRegion(const CXXRecordDecl *RD,
   }
 
   return getSubRegion<CXXBaseObjectRegion>(RD, IsVirtual, Super);
 }
 
 const CXXThisRegion*
 MemRegionManager::getCXXThisRegion(QualType thisPointerTy,
                                    const LocationContext *LC) {
-  const StackFrameContext *STC = LC->getCurrentStackFrame();
-  assert(STC);
   const PointerType *PT = thisPointerTy->getAs<PointerType>();
   assert(PT);
+  // Inside the body of the operator() of a lambda a this expr might refer to an
+  // object in one of the parent location contexts.
+  const auto *D = dyn_cast<CXXMethodDecl>(LC->getDecl());
+  // FIXME: when operator() of lambda is analyzed as a top level function and
+  // 'this' refers to a this to the enclosing scope, there is no right region to
+  // return.
+  while (!LC->inTopFrame() &&
+         PT != D->getThisType(getContext())->getAs<PointerType>()) {
+    LC = LC->getParent();
+    D = dyn_cast<CXXMethodDecl>(LC->getDecl());
+  }
+  const StackFrameContext *STC = LC->getCurrentStackFrame();
+  assert(STC);
   return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC));
 }
 
 const AllocaRegion*
 MemRegionManager::getAllocaRegion(const Expr *E, unsigned cnt,
                                   const LocationContext *LC) {
   const StackFrameContext *STC = LC->getCurrentStackFrame();
   assert(STC);

test/Analysis/dead-stores.cpp

template <bool f> int radar13213575_testit(int i) {
   else
     return y;
 }
 
 int radar_13213575() {
   return radar13213575_testit<true>(5) + radar13213575_testit<false>(3);
 }
 
+//===----------------------------------------------------------------------===//
+// Dead store checking involving lambdas.
+//===----------------------------------------------------------------------===//
+
+int basicLambda(int i, int j) {
+  i = 5; // no warning
+  j = 6; // no warning
+  [i] { (void)i; }();
+  [&j] { (void)j; }();
+  i = 2;
+  j = 3;
+  return i + j;
+}
+

test/Analysis/lambdas.cpp

-// RUN: %clang_cc1 -std=c++11 -fsyntax-only -analyze -analyzer-checker=debug.DumpCFG %s > %t 2>&1
+// RUN: %clang_cc1 -std=c++11 -fsyntax-only -analyze -analyzer-checker=core,debug.ExprInspection -analyzer-config inline-lambdas=true -verify %s 
+// RUN: %clang_cc1 -std=c++11 -fsyntax-only -analyze -analyzer-checker=core,debug.DumpCFG -analyzer-config inline-lambdas=true %s > %t 2>&1
 // RUN: FileCheck --input-file=%t %s
 
+void clang_analyzer_warnIfReached();
+void clang_analyzer_eval(int);
+
 struct X { X(const X&); };
 void f(X x) { (void) [x]{}; }
 
+
+// Lambda semantics tests.
+
+void basicCapture() {
+  int i = 5;
+  [i]() mutable {
+    // clang_analyzer_eval does nothing in inlined functions.
+    if (i != 5)
+      clang_analyzer_warnIfReached();
+    ++i;
+  }();
+  [&i] {
+    if (i != 5)
+      clang_analyzer_warnIfReached();
+  }();
+  [&i] {
+    if (i != 5)
+      clang_analyzer_warnIfReached();
+    i++;
+  }();
+  clang_analyzer_eval(i == 6); // expected-warning{{TRUE}}
+}
+
+void deferredLambdaCall() {
+  int i = 5;
+  auto l1 = [i]() mutable {
+    if (i != 5)
+      clang_analyzer_warnIfReached();
+    ++i;
+  };
+  auto l2 = [&i] {
+    if (i != 5)
+      clang_analyzer_warnIfReached();
+  };
+  auto l3 = [&i] {
+    if (i != 5)
+      clang_analyzer_warnIfReached();
+    i++;
+  };
+  l1();
+  l2();
+  l3();
+  clang_analyzer_eval(i == 6); // expected-warning{{TRUE}}
+}
+
+void multipleCaptures() {
+  int i = 5, j = 5;
+  [i, &j]() mutable {
+    if (i != 5 && j != 5)
+      clang_analyzer_warnIfReached();
+    ++i;
+    ++j;
+  }();
+  clang_analyzer_eval(i == 5); // expected-warning{{TRUE}}
+  clang_analyzer_eval(j == 6); // expected-warning{{TRUE}}
+  [=]() mutable {
+    if (i != 5 && j != 6)
+      clang_analyzer_warnIfReached();
+    ++i;
+    ++j;
+  }();
+  clang_analyzer_eval(i == 5); // expected-warning{{TRUE}}
+  clang_analyzer_eval(j == 6); // expected-warning{{TRUE}}
+  [&]() mutable {
+    if (i != 5 && j != 6)
+      clang_analyzer_warnIfReached();
+    ++i;
+    ++j;
+  }();
+  clang_analyzer_eval(i == 6); // expected-warning{{TRUE}}
+  clang_analyzer_eval(j == 7); // expected-warning{{TRUE}}
+}
+
+void testReturnValue() {
+  int i = 5;
+  auto l = [i] (int a) {
+    return i + a;
+  };
+  int b = l(3);
+  clang_analyzer_eval(b == 8); // expected-warning{{TRUE}}
+}
+
+// Nested lambdas.
+
+void testNestedLambdas() {
+  int i = 5;
+  auto l = [i]() mutable {
+    [&i]() {
+      ++i;
+    }();
+    if (i != 6)
+      clang_analyzer_warnIfReached();
+  };
+  l();
+  clang_analyzer_eval(i == 5); // expected-warning{{TRUE}}
+}
+
+// Captured this.
+
+class RandomClass {
+  int i;
+
+  void captureFields() {
+    i = 5;
+    [this]() {
+      // clang_analyzer_eval does nothing in inlined functions.
+      if (i != 5)
+        clang_analyzer_warnIfReached();
+      ++i;
+    }();
+    clang_analyzer_eval(i == 6); // expected-warning{{TRUE}}
+  }
+};
+
+
+// Nested this capture.
+
+class RandomClass2 {
+  int i;
+
+  void captureFields() {
+    i = 5;
+    [this]() {
+      // clang_analyzer_eval does nothing in inlined functions.
+      if (i != 5)
+        clang_analyzer_warnIfReached();
+      ++i;
+      [this]() {
+        // clang_analyzer_eval does nothing in inlined functions.
+        if (i != 6)
+          clang_analyzer_warnIfReached();
+        ++i;
+      }();
+    }();
+    clang_analyzer_eval(i == 7); // expected-warning{{TRUE}}
+  }
+};
+
+
+// Captured function pointers.
+
+void inc(int &x) {
+  ++x;
+}
+
+void testFunctionPointerCapture() {
+  void (*func)(int &) = inc;
+  int i = 5;
+  [&i, func] {
+    func(i);
+  }();
+  clang_analyzer_eval(i == 6); // expected-warning{{TRUE}}
+}
+
 // 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:   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
 

test/Analysis/temporaries.cpp

if (isInner ||
         check(NoReturnDtor()) ||
         testRecursiveFrames(true)) {
       clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
     }
   }
   void testRecursiveFramesStart() { testRecursiveFrames(false); }
 
   void testLambdas() {
-    // This is the test we would like to write:
-    // []() { check(NoReturnDtor()); } != nullptr || check(Dtor());
-    // But currently the analyzer stops when it encounters a lambda:
-    [] {};
-    // The CFG for this now looks correct, but we still do not reach the line
-    // below.
-    clang_analyzer_warnIfReached(); // FIXME: Should warn.
+    []() { check(NoReturnDtor()); } != nullptr || check(Dtor());
   }
 
   void testGnuExpressionStatements(int v) {
     ({ ++v; v == 10 || check(NoReturnDtor()); v == 42; }) || v == 23;
     clang_analyzer_warnIfReached();  // expected-warning{{REACHABLE}}
 
     ({ ++v; check(NoReturnDtor()); v == 42; }) || v == 23;
     clang_analyzer_warnIfReached();  // no warning, unreachable code