[Analysis] Bug fix for exploded graph branching in evalCall for constructor

[vrnithinkumar]

Summary

Fix for the bug in the implementation of evalCall() for constructors.
The StmtNodeBuilder created isn't actually used during runCheckersForEvalCall(). A new builder is used instead, inside runCheckersForEvalCall(). So NodeBuilder believes that no transitions were added inside runCheckersForEvalCall(), and therefore the analysis must continue from the predecessor node. And it was causing the exploded graph branching in evalCall for a constructor.

Fixing it by passing the NodeBuilder to runCheckersForEvalCall() and use it instead of new NodeBuilder

[NoQ]

Thanks!!

I'm having second thoughts on re-using the existing builder. Most other runCheckers...() methods are building their own. Given how confusing this entire node builder business is, i believe we should not deviate from known working patterns.

Please forgive me if i at some point decide to take over this patch and do this myself. I have strong opinions about this entire NodeBuilder API and i'm pretty much screaming internally when i try to understand why it's made the way it's made, so there's a high chance i'll want to introduce some invasive sanity into it on my own.

clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

619

We should probably delete the copy-constructor for node builders. I've no idea what it's supposed to do anyway and the whole problem that we're having here is due to there being too many of them already.

clang/test/Analysis/smart-ptr-text-output.cpp

39–40

Ok, these notes shouldn't be there; a note on .release() is sufficient to understand the warning and it looks like that's one more place where we should mark the region as uninteresting.

Can you try to debug why did they suddenly show up?

clang/test/Analysis/smart-ptr.cpp

123–124

That's indeed the intended consequence of your patch: we're no longer exploring a bogus execution path that's parallel to the previous null dereference on line 133, therefore we're no longer emitting this warning but instead correctly interrupting the entire analysis after we've found that other null dereference.

That said, we should preserve the test so that it was still testing whatever it was testing previously. Can you split up this function into smaller functions so that each test was running independently?

[vrnithinkumar]

clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

619

So we should disable the copying of NodeBuilder and create a heap allocated NodeBuilder and use pointer to pass around functions?

clang/test/Analysis/smart-ptr-text-output.cpp

39–40

I checked the exploded graph for this test case.
Before the bug fix, there exists a path where the no Note Tag is added to the corresponding CXXConstructExpr. After the fix removed this branching theres always a Note Tag on Ctr.

ExplodedGraphBeforeFix.svg129 KBDownload

Since the note on .release() is sufficient to understand the warning and I agree we should mark this region as uninteresting.

[NoQ]

clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

619

No-no, keep it on the stack and don't pass it around *at all*.

clang/test/Analysis/smart-ptr-text-output.cpp

39–40

Ok, fair enough! Let's add a FIXME.

[vrnithinkumar]

• Addressing review comments

[vrnithinkumar]

clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

619

Sorry, I am still little confused.

Do we have to make the fix without passing around the NodeBuilder?
And delete copy-constructor for NodeBuilder in this patch?

clang/test/Analysis/smart-ptr-text-output.cpp

39–40

Added the FIXME

clang/test/Analysis/smart-ptr.cpp

123–124

Separated the function into smaller functions.

[NoQ]

clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

619

runCheckersForEvalCall() already has its own builder, you don't need another.

[vrnithinkumar]

• Fix without passing the NodeBuilder

[vrnithinkumar]

clang/lib/StaticAnalyzer/Core/CheckerManager.cpp

682 ↗

(On Diff #285763)

runCheckersForEvalCall() already has its own builder, you don't need another.

In that case is it okay to clear the ExplodedNodeSet DstEvaluated passed as Dst which contains parent node contains parent node ?

When the any of the evaluated checker is evaluated the node successfully we can clear the Dst which is part of the StmtNodeBuilder Bldr(DstPreCall, DstEvaluated, *currBldrCtx); before inserting new nodes.

[NoQ]

clang/lib/StaticAnalyzer/Core/CheckerManager.cpp

682 ↗

(On Diff #285763)

Hmm actually your code is now incorrect because runCheckersForEvalCall() is in fact invoked multiple times in a loop (if there were state splits in PreStmt/PreCall), therefore it's possible that Dst does in fact already contain nodes.

That also means that i can't put in the assertions that i thought of; the destination set is indeed potentially non-empty in many cases.

Anyway, here's what i meant:

   ExplodedNodeSet DstPreCall;
   getCheckerManager().runCheckersForPreCall(DstPreCall, PreInitialized,
                                             *Call, *this);

   ExplodedNodeSet DstEvaluated;
-  StmtNodeBuilder Bldr(DstPreCall, DstEvaluated, *currBldrCtx);

   if (CE && CE->getConstructor()->isTrivial() &&
       CE->getConstructor()->isCopyOrMoveConstructor() &&
       !CallOpts.IsArrayCtorOrDtor) {
+    StmtNodeBuilder Bldr(DstPreCall, DstEvaluated, *currBldrCtx);
     // FIXME: Handle other kinds of trivial constructors as well.
     for (ExplodedNodeSet::iterator I = DstPreCall.begin(), E = DstPreCall.end();
          I != E; ++I)
       performTrivialCopy(Bldr, *I, *Call);

   } else {
     for (ExplodedNodeSet::iterator I = DstPreCall.begin(), E = DstPreCall.end();
          I != E; ++I)
       getCheckerManager().runCheckersForEvalCall(DstEvaluated, *I, *Call, *this,
                                                  CallOpts);
   }

   // If the CFG was constructed without elements for temporary destructors
   // and the just-called constructor created a temporary object then
   // stop exploration if the temporary object has a noreturn constructor.
   // This can lose coverage because the destructor, if it were present
   // in the CFG, would be called at the end of the full expression or
   // later (for life-time extended temporaries) -- but avoids infeasible
   // paths when no-return temporary destructors are used for assertions.
+  ExplodedNodeSet DstEvaluatedPostProcessed;
+  StmtNodeBuilder Bldr(DstEvaluated, DstEvaluatedPostProcessed, *currBldrCtx);
   const AnalysisDeclContext *ADC = LCtx->getAnalysisDeclContext();
   if (!ADC->getCFGBuildOptions().AddTemporaryDtors) {
     if (llvm::isa_and_nonnull<CXXTempObjectRegion>(TargetRegion) &&
         cast<CXXConstructorDecl>(Call->getDecl())
             ->getParent()
             ->isAnyDestructorNoReturn()) {

       // If we've inlined the constructor, then DstEvaluated would be empty.
       // In this case we still want a sink, which could be implemented
       // in processCallExit. But we don't have that implemented at the moment,
       // so if you hit this assertion, see if you can avoid inlining
       // the respective constructor when analyzer-config cfg-temporary-dtors
       // is set to false.
       // Otherwise there's nothing wrong with inlining such constructor.
       assert(!DstEvaluated.empty() &&
              "We should not have inlined this constructor!");

       for (ExplodedNode *N : DstEvaluated) {
         Bldr.generateSink(E, N, N->getState());
       }

       // There is no need to run the PostCall and PostStmt checker
       // callbacks because we just generated sinks on all nodes in th
       // frontier.
       return;
     }
   }

   ExplodedNodeSet DstPostArgumentCleanup;
-  for (ExplodedNode *I : DstEvaluated)
+  for (ExplodedNode *I : DstEvaluatedPostProcessed)
     finishArgumentConstruction(DstPostArgumentCleanup, I, *Call);

This way exactly one builder exists at any given moment of time and exactly one builder operates on each pair of source-destination sets.

Also this entire AddTemporaryDtors option could probably be banned already which would make things a whole lot easier; i'll look into that.

[vrnithinkumar]

• Make exactly single NodeBuilder exists at any given time

[vrnithinkumar]

clang/lib/StaticAnalyzer/Core/CheckerManager.cpp

682 ↗

(On Diff #285763)

Hmm actually your code is now incorrect because runCheckersForEvalCall() is in fact invoked multiple times in a loop (if there were state splits in PreStmt/PreCall), therefore it's possible that Dst does in fact already contain nodes.

Oh, I missed that point.

Made the above suggested changes to make sure exactly one NodeBuilder exists at any given time.

[NoQ]

Thanks!~

clang/test/Analysis/smart-ptr.cpp

44

I'm sooo fond of these sanity checks.

clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

if (CE) {
     PreInitialized = DstPreVisit;
   }
 
   ExplodedNodeSet DstPreCall;
   getCheckerManager().runCheckersForPreCall(DstPreCall, PreInitialized,
                                             *Call, *this);
 
   ExplodedNodeSet DstEvaluated;
-  StmtNodeBuilder Bldr(DstPreCall, DstEvaluated, *currBldrCtx);
 
   if (CE && CE->getConstructor()->isTrivial() &&
       CE->getConstructor()->isCopyOrMoveConstructor() &&
       !CallOpts.IsArrayCtorOrDtor) {
+    StmtNodeBuilder Bldr(DstPreCall, DstEvaluated, *currBldrCtx);
     // FIXME: Handle other kinds of trivial constructors as well.
     for (ExplodedNodeSet::iterator I = DstPreCall.begin(), E = DstPreCall.end();
          I != E; ++I)
       performTrivialCopy(Bldr, *I, *Call);
 
   } else {
     for (ExplodedNodeSet::iterator I = DstPreCall.begin(), E = DstPreCall.end();
          I != E; ++I)
       getCheckerManager().runCheckersForEvalCall(DstEvaluated, *I, *Call, *this,
                                                  CallOpts);
   }
 
   // If the CFG was constructed without elements for temporary destructors
   // and the just-called constructor created a temporary object then
   // stop exploration if the temporary object has a noreturn constructor.
   // This can lose coverage because the destructor, if it were present
   // in the CFG, would be called at the end of the full expression or
   // later (for life-time extended temporaries) -- but avoids infeasible
   // paths when no-return temporary destructors are used for assertions.
+  ExplodedNodeSet DstEvaluatedPostProcessed;
+  StmtNodeBuilder Bldr(DstEvaluated, DstEvaluatedPostProcessed, *currBldrCtx);
   const AnalysisDeclContext *ADC = LCtx->getAnalysisDeclContext();
   if (!ADC->getCFGBuildOptions().AddTemporaryDtors) {
     if (llvm::isa_and_nonnull<CXXTempObjectRegion>(TargetRegion) &&
         cast<CXXConstructorDecl>(Call->getDecl())
             ->getParent()
             ->isAnyDestructorNoReturn()) {
 
       // If we've inlined the constructor, then DstEvaluated would be empty.
if (llvm::isa_and_nonnull<CXXTempObjectRegion>(TargetRegion) &&
       // There is no need to run the PostCall and PostStmt checker
       // callbacks because we just generated sinks on all nodes in th
       // frontier.
       return;
     }
   }
 
   ExplodedNodeSet DstPostArgumentCleanup;
-  for (ExplodedNode *I : DstEvaluated)
+  for (ExplodedNode *I : DstEvaluatedPostProcessed)
     finishArgumentConstruction(DstPostArgumentCleanup, I, *Call);
 
   // If there were other constructors called for object-type arguments
   // of this constructor, clean them up.
   ExplodedNodeSet DstPostCall;
   getCheckerManager().runCheckersForPostCall(DstPostCall,
                                              DstPostArgumentCleanup,
                                              *Call, *this);

clang/test/Analysis/smart-ptr-text-output.cpp

 void derefAfterCtrWithNullVariable() {
   A *NullInnerPtr = nullptr; // expected-note {{'NullInnerPtr' initialized to a null pointer value}}
   std::unique_ptr<A> P(NullInnerPtr); // expected-note {{Smart pointer 'P' is constructed using a null value}}
   P->foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
   // expected-note@-1{{Dereference of null smart pointer 'P'}}
 }
 
 void derefAfterRelease() {
-  std::unique_ptr<A> P(new A());
+  std::unique_ptr<A> P(new A()); // expected-note {{Smart pointer 'P' is constructed}}
+  // FIXME: should mark region as uninteresting after release, so above note will not be there
   P.release(); // expected-note {{Smart pointer 'P' is released and set to null}}
   P->foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
   // expected-note@-1{{Dereference of null smart pointer 'P'}}
 }
 
 void derefAfterReset() {
-  std::unique_ptr<A> P(new A());
+  std::unique_ptr<A> P(new A()); // expected-note {{Smart pointer 'P' is constructed}}
   P.reset(); // expected-note {{Smart pointer 'P' reset using a null value}}
   P->foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
   // expected-note@-1{{Dereference of null smart pointer 'P'}}
 }
 
 void derefAfterResetWithNull() {
   A *NullInnerPtr = nullptr; // expected-note {{'NullInnerPtr' initialized to a null pointer value}}
-  std::unique_ptr<A> P(new A());
+  std::unique_ptr<A> P(new A()); // expected-note {{Smart pointer 'P' is constructed}}
   P.reset(NullInnerPtr); // expected-note {{Smart pointer 'P' reset using a null value}}
   P->foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
   // expected-note@-1{{Dereference of null smart pointer 'P'}}
 }
 
 // FIXME: Fix this test when support is added for tracking raw pointer
 // and mark the smart pointer as interesting based on that and add tags.
 void derefOnReleasedNullRawPtr() {
   std::unique_ptr<A> P; // FIXME: add note "Default constructed smart pointer 'P' is null"
   A *AP = P.release(); // expected-note {{'AP' initialized to a null pointer value}}
   AP->foo(); // expected-warning {{Called C++ object pointer is null [core.CallAndMessage]}}
   // expected-note@-1{{Called C++ object pointer is null}}
 }
 
 void derefOnSwappedNullPtr() {
-  std::unique_ptr<A> P(new A());
+  std::unique_ptr<A> P(new A()); // expected-note {{Smart pointer 'P' is constructed}}
   std::unique_ptr<A> PNull; // expected-note {{Default constructed smart pointer 'PNull' is null}}
   P.swap(PNull); // expected-note {{Swapped null smart pointer 'PNull' with smart pointer 'P'}}
   PNull->foo(); // No warning.
   (*P).foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
   // expected-note@-1{{Dereference of null smart pointer 'P'}}
 }
 
 // FIXME: Fix this test when "std::swap" is modeled seperately.
 void derefOnStdSwappedNullPtr() {
-  std::unique_ptr<A> P;
+  std::unique_ptr<A> P; // expected-note {{Default constructed smart pointer 'P' is null}}
   std::unique_ptr<A> PNull; // expected-note {{Default constructed smart pointer 'PNull' is null}}
   std::swap(P, PNull); // expected-note@Inputs/system-header-simulator-cxx.h:978 {{Swapped null smart pointer 'PNull' with smart pointer 'P'}}
   // expected-note@-1 {{Calling 'swap<A>'}}
   // expected-note@-2 {{Returning from 'swap<A>'}}
-  PNull->foo(); // expected-warning {{Dereference of null smart pointer 'PNull' [alpha.cplusplus.SmartPtr]}}
-  // expected-note@-1{{Dereference of null smart pointer 'PNull'}}
   P->foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
   // expected-note@-1{{Dereference of null smart pointer 'P'}}
 }
 
 struct StructWithSmartPtr { // expected-note {{Default constructed smart pointer 'S.P' is null}}
   std::unique_ptr<A> P;
 };
 

clang/test/Analysis/smart-ptr.cpp

 };
 
 A *return_null() {
   return nullptr;
 }
 
 void derefAfterValidCtr() {
   std::unique_ptr<A> P(new A());
+  clang_analyzer_numTimesReached(); // expected-warning {{1}}
   P->foo(); // No warning.
 }
 
 void derefOfUnknown(std::unique_ptr<A> P) {
   P->foo(); // No warning.
 }
 
 void derefAfterDefaultCtr() {
   std::unique_ptr<A> P;
+  clang_analyzer_numTimesReached(); // expected-warning {{1}}
   P->foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
 }
 
 void derefAfterCtrWithNull() {
   std::unique_ptr<A> P(nullptr);
+  clang_analyzer_numTimesReached(); // expected-warning {{1}}
   *P; // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
 }
 
 void derefAfterCtrWithNullVariable() {
   A *InnerPtr = nullptr;
   std::unique_ptr<A> P(InnerPtr);
+  clang_analyzer_numTimesReached(); // expected-warning {{1}}
   P->foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
 }
 
 void derefAfterRelease() {
   std::unique_ptr<A> P(new A());
   P.release();
   clang_analyzer_numTimesReached(); // expected-warning {{1}}
   P->foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
void derefAfterResetWithNull() {
   std::unique_ptr<A> P(new A());
   P.reset(nullptr);
   P->foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
 }
 
 void derefAfterResetWithNonNull() {
   std::unique_ptr<A> P;
   P.reset(new A());
+  clang_analyzer_numTimesReached(); // expected-warning {{1}}
   P->foo(); // No warning.
 }
 
 void derefAfterReleaseAndResetWithNonNull() {
   std::unique_ptr<A> P(new A());
   P.release();
   P.reset(new A());
   P->foo(); // No warning.

 }
 
 void pass_smart_ptr_by_ref(std::unique_ptr<A> &a);
 void pass_smart_ptr_by_const_ref(const std::unique_ptr<A> &a);
 void pass_smart_ptr_by_rvalue_ref(std::unique_ptr<A> &&a);
 void pass_smart_ptr_by_const_rvalue_ref(const std::unique_ptr<A> &&a);
 void pass_smart_ptr_by_ptr(std::unique_ptr<A> *a);
 void pass_smart_ptr_by_const_ptr(const std::unique_ptr<A> *a);
 
-void regioninvalidationTest() {
-  {
-    std::unique_ptr<A> P;
-    pass_smart_ptr_by_ref(P);
-    P->foo(); // no-warning
-  }
-  {
-    std::unique_ptr<A> P;
-    pass_smart_ptr_by_const_ref(P);
-    P->foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
-  }
-  {
-    std::unique_ptr<A> P;
-    pass_smart_ptr_by_rvalue_ref(std::move(P));
-    P->foo(); // no-warning
-  }
-  {
-    std::unique_ptr<A> P;
-    pass_smart_ptr_by_const_rvalue_ref(std::move(P));
-    P->foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
-  }
-  {
-    std::unique_ptr<A> P;
-    pass_smart_ptr_by_ptr(&P);
-    P->foo();
-  }
-  {
-    std::unique_ptr<A> P;
-    pass_smart_ptr_by_const_ptr(&P);
-    P->foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
-  }
-}
+void regioninvalidationWithPassByRef() {
+
+void regioninvalidationWithPassByCostRef() {
+
+void regioninvalidationWithPassByRValueRef() {
+
+void regioninvalidationWithPassByConstRValueRef() {
+
+void regioninvalidationWithPassByPtr() {
+
+void regioninvalidationWithPassByConstPtr() {
 
 struct StructWithSmartPtr {
   std::unique_ptr<A> P;
 };
 
 void pass_struct_with_smart_ptr_by_ref(StructWithSmartPtr &a);
 void pass_struct_with_smart_ptr_by_const_ref(const StructWithSmartPtr &a);
 void pass_struct_with_smart_ptr_by_rvalue_ref(StructWithSmartPtr &&a);
 void pass_struct_with_smart_ptr_by_const_rvalue_ref(const StructWithSmartPtr &&a);
 void pass_struct_with_smart_ptr_by_ptr(StructWithSmartPtr *a);
 void pass_struct_with_smart_ptr_by_const_ptr(const StructWithSmartPtr *a);
 
-void regioninvalidationTestWithinStruct() {
-  {
-    StructWithSmartPtr S;
-    pass_struct_with_smart_ptr_by_ref(S);
-    S.P->foo(); // no-warning
-  }
-  {
-    StructWithSmartPtr S;
-    pass_struct_with_smart_ptr_by_const_ref(S);
-    S.P->foo(); // expected-warning {{Dereference of null smart pointer 'S.P' [alpha.cplusplus.SmartPtr]}}
-  }
-  {
-    StructWithSmartPtr S;
-    pass_struct_with_smart_ptr_by_rvalue_ref(std::move(S));
-    S.P->foo(); // no-warning
-  }
-  {
-    StructWithSmartPtr S;
-    pass_struct_with_smart_ptr_by_const_rvalue_ref(std::move(S));
-    S.P->foo(); // expected-warning {{Dereference of null smart pointer 'S.P' [alpha.cplusplus.SmartPtr]}}
-  }
-  {
-    StructWithSmartPtr S;
-    pass_struct_with_smart_ptr_by_ptr(&S);
-    S.P->foo();
-  }
-  {
-    StructWithSmartPtr S;
-    pass_struct_with_smart_ptr_by_const_ptr(&S);
-    S.P->foo(); // expected-warning {{Dereference of null smart pointer 'S.P' [alpha.cplusplus.SmartPtr]}}
-  }
-}
+void regioninvalidationWithinStructPassByRef() {
+
+void regioninvalidationWithinStructPassByConstRef() {
+
+void regioninvalidationWithinStructPassByRValueRef() {
+
+void regioninvalidationWithinStructPassByConstRValueRef() {
+
+void regioninvalidationWithinStructPassByPtr() {
+  S.P->foo(); // no-warning
+
+void regioninvalidationWithinStructPassByConstPtr() {
 
 void derefAfterAssignment() {
   {
     std::unique_ptr<A> P(new A());
     std::unique_ptr<A> Q;
     Q = std::move(P);
     Q->foo(); // no-warning
   }

 void derefOnSwappedNullPtr() {
   std::unique_ptr<A> P(new A());
   std::unique_ptr<A> PNull;
   P.swap(PNull);
   PNull->foo(); // No warning.
   (*P).foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
 }
 
-void derefOnStdSwappedNullPtr() {
+void derefOnFirstStdSwappedNullPtr() {
   std::unique_ptr<A> P;
   std::unique_ptr<A> PNull;
   std::swap(P, PNull);
-  PNull->foo(); // expected-warning {{Dereference of null smart pointer 'PNull' [alpha.cplusplus.SmartPtr]}}
   P->foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
 }
 
+void derefOnSecondStdSwappedNullPtr() {
+  std::unique_ptr<A> P;
+  std::unique_ptr<A> PNull;
+  std::swap(P, PNull);
+  PNull->foo(); // expected-warning {{Dereference of null smart pointer 'PNull' [alpha.cplusplus.SmartPtr]}}
+}
+
 void derefOnSwappedValidPtr() {
   std::unique_ptr<A> P(new A());
   std::unique_ptr<A> PValid(new A());
   P.swap(PValid);
   (*P).foo(); // No warning.
   PValid->foo(); // No warning.
   std::swap(P, PValid);
   P->foo(); // No warning.
   PValid->foo(); // No warning.
 }