[analyzer] PR43102: Fix an assertion and an out-of-bounds error for diagnostic location construction

[Szelethus]

Summary

https://bugs.llvm.org/show_bug.cgi?id=43102

In today's edition of "Is this any better now that it isn't crashing?", I'd like to show you a very interesting test case with loop widening.

Looking at the included test case, it's immediately obvious that this is not only a false positive, but also a very bad bug report in general. We can see how the analyzer mistakenly invalidated b, instead of its pointee, resulting in it reporting a null pointer dereference error. Not only that, the point at which this change of value is noted at is at the loop, rather then at the method call.

It turns out that FindLastStoreVisitor works correctly, rather the supplied explodedgraph is faulty, because BlockEdge really is the ProgramPoint where this happens.

So it's fair to say that this needs improving on multiple fronts. In any case, at least the crash is gone.

Full ExplodedGraph:

loop.dot94 KBDownload

[Szelethus]

Note how I am partially at fault here, which is why the bug reports state that the crash originates from TrackControlDependencyVisitor, but even after that is fixed, the diagnostics construction flopped on an out-of-bounds error.

[TWeaver]

Hi there!

thanks so much for this patch, can confirm that with this patch applied on my local machine clang no longer crashes for the loop-widening.cpp test.

LGTM for me, but this isn't really my area of expertise so I can't judge on whether these changes are the correct ones to make.

Thanks again!

[NoQ]

I don't understand. Isn't widening supposed to happen after we exit the loop? The loop isn't over yet when the bug is being reported. Why is this problem widening-specific? Given that we also have a weird invalidation of b, i suspect that we're doing widening in a wrong moment of time.

[Szelethus]

In D66716#1647668, @NoQ wrote:

I don't understand. Isn't widening supposed to happen after we exit the loop? The loop isn't over yet when the bug is being reported. Why is this problem widening-specific? Given that we also have a weird invalidation of b, i suspect that we're doing widening in a wrong moment of time.

Something is totally off here. Do you think its ever okay to find a last store in a BlockEdge? Should I rather fix this by changing how loop widening works?

[NoQ]

Do you think its ever okay to find a last store in a BlockEdge?

*In a BlockEntrance into an empty block (that has no elements but does have a terminator). At least that's what your code is fixing.

Attaching store notes to such program points is most likely not ok. We can always make ourselves a WideningPoint for that specific purpose, or maybe even PreWidening / PostWidening. Program points are not set in stone, we are free to make as many kinds of them as we need (which is why we also have tags).

Being able to attach an event note at all to such program point is most likely ok. Any program point can potentially represent an interesting event. So this is anyway a good change. I'd love to have some more careful testing, maybe a unittest (or somehow trick -verify with line breaks), so that to know where exactly does the note go in this case (is it the jump from the bottom of the loop? is it jump from increment to condition?). This way we'll make sure that the implementation is correct.

I'd still want you to figure out why is this widening-specific. Do i understand correctly that we're doing widening in an inappropriate moment of time? I'd prefer to have this confirmed. Or can we reproduce this crash / incorrect behavior / false positive without widening?

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1805 ↗

(On Diff #217041)

Why did this even compile? I thought i deleted these conversions in D61814 >.<

clang/lib/StaticAnalyzer/Core/PathDiagnostic.cpp

774–775 ↗

(On Diff #217041)

What exactly is the terminator here in your case? Is it NullStmt? Is there always a terminator and/or a terminator statement?

What if that's a BlockEntrance to the exit-block? (do we even make such program points? i hope we don't)

I think this code needs comments in order to explain what picture do we have in mind.

[Szelethus]

I'm still working on this, just been kinda busy. I'll try to get it out of the way asap.

[TWeaver]

Hi there,

just checking in, is this patch still going ahead?

thanks
Tom W

[Szelethus]

In D66716#1671105, @TWeaver wrote:

Hi there,

just checking in, is this patch still going ahead?

thanks
Tom W

Unfortunately, it seems like the correct solution is a bit more complex than these if branches, so it might take just a bit longer, but I'm definitely on it! I'm also talking to folks behind to scenes to catch up with how loop widening works.

[Szelethus]

While we're there, could you please see whether the included test case (note how condition tracking is turned off) fails on your platform without the rest of the patch applied (it definitely does on mine, which is why I was surprised to see this bug report pop up only now)? If not, I can just push a small commit with the llvm::isa_and_nonnull change to get some breathing room.

[Szelethus]

We have no solid evidence to conclude that such an event should not occur at a BlockEntrance, so fixing this error mustn't be that bad. I certainly should've used llvm::isa_or_nonnull, so the patch overall makes sense, so I'm commiting it as is. With that said, this test case highlights a fundamental flaw in how loop wideining is implemented (hence it being off-by-default), and it should be addressed later separately.

I have talked to @NoQ about this behind the scenes, which is why I'm not concerned with the green check mark :)

cfe/trunk/lib/Analysis/PathDiagnostic.cpp

return getLocationForCaller(CEE->getCalleeContext(),
                                 SMng);
   } else if (auto CEB = P.getAs<CallExitBegin>()) {
     if (const ReturnStmt *RS = CEB->getReturnStmt())
       return PathDiagnosticLocation::createBegin(RS, SMng,
                                                  CEB->getLocationContext());
     return PathDiagnosticLocation(
         CEB->getLocationContext()->getDecl()->getSourceRange().getEnd(), SMng);
   } else if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) {
-    CFGElement BlockFront = BE->getBlock()->front();
-    if (auto StmtElt = BlockFront.getAs<CFGStmt>()) {
+    if (Optional<CFGElement> BlockFront = BE->getFirstElement()) {
+      if (auto StmtElt = BlockFront->getAs<CFGStmt>()) {
         return PathDiagnosticLocation(StmtElt->getStmt()->getBeginLoc(), SMng);
-    } else if (auto NewAllocElt = BlockFront.getAs<CFGNewAllocator>()) {
+      } else if (auto NewAllocElt = BlockFront->getAs<CFGNewAllocator>()) {
         return PathDiagnosticLocation(
             NewAllocElt->getAllocatorExpr()->getBeginLoc(), SMng);
       }
       llvm_unreachable("Unexpected CFG element at front of block");
+    }
+
+    return PathDiagnosticLocation(
+        BE->getBlock()->getTerminatorStmt()->getBeginLoc(), SMng);
   } else if (Optional<FunctionExitPoint> FE = P.getAs<FunctionExitPoint>()) {
     return PathDiagnosticLocation(FE->getStmt(), SMng,
                                   FE->getLocationContext());
   } else {
     llvm_unreachable("Unexpected ProgramPoint");
   }
 
   return PathDiagnosticLocation(S, SMng, P.getLocationContext());

cfe/trunk/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

if (!StoreSite) {
     // If this is a CXXTempObjectRegion, the Expr responsible for its creation
     // is wrapped inside of it.
     if (const auto *TmpR = dyn_cast<CXXTempObjectRegion>(R))
       InitE = TmpR->getExpr();
   }
 
   if (!StoreSite)
     return nullptr;
+
   Satisfied = true;
 
   // If we have an expression that provided the value, try to track where it
   // came from.
   if (InitE) {
     if (!IsParam)
       InitE = InitE->IgnoreParenCasts();
 
if (!OriginB || !NB)
     return nullptr;
 
   if (isAssertlikeBlock(NB, BRC.getASTContext()))
     return nullptr;
 
   if (ControlDeps.isControlDependent(OriginB, NB)) {
     // We don't really want to explain for range loops. Evidence suggests that
     // the only thing that leads to is the addition of calls to operator!=.
-    if (isa<CXXForRangeStmt>(NB->getTerminator()))
+    if (llvm::isa_and_nonnull<CXXForRangeStmt>(NB->getTerminatorStmt()))
       return nullptr;
 
     if (const Expr *Condition = NB->getLastCondition()) {
       // Keeping track of the already tracked conditions on a visitor level
       // isn't sufficient, because a new visitor is created for each tracked
       // expression, hence the BugReport level set.
       if (BR.addTrackedCondition(N)) {
         bugreporter::trackExpressionValue(

cfe/trunk/test/Analysis/loop-widening.cpp

+// RUN: %clang_analyze_cc1 -verify %s \
+// RUN:   -analyzer-checker=core \
+// RUN:   -analyzer-config widen-loops=true \
+// RUN:   -analyzer-config track-conditions=false \
+// RUN:   -analyzer-max-loop 2 -analyzer-output=text
+
+namespace pr43102 {
+class A {
+public:
+  void m_fn1();
+};
+bool g;
+void fn1() {
+  A a;
+  A *b = &a;
+
+  for (;;) { // expected-note{{Loop condition is true.  Entering loop body}}
+             // expected-note@-1{{Loop condition is true.  Entering loop body}}
+             // expected-note@-2{{Value assigned to 'b'}}
+             // no crash during bug report construction
+
+    g = !b;     // expected-note{{Assuming 'b' is null}}
+    b->m_fn1(); // expected-warning{{Called C++ object pointer is null}}
+                // expected-note@-1{{Called C++ object pointer is null}}
+  }
+}
+} // end of namespace pr43102