[analyzer] Allow visitors to run callbacks on completion

[RedDocMD]

Summary

This patch introduces the concept of *Stoppable* visitors, ie, a
visitor that must perform some task when it runs out of nodes on which
it has work to do.
Initially, the ReturnVisitor is being made *stoppable*, thus allowing
it to run callbacks on completion. These callbacks are meant to be
supplied from trackExpressionValue.
Thus, this patch will also allow trackExpressionValue to recieve a
callback to run when it is done tracking.

[RedDocMD]

Note: This patch is only partially done.

The following things are still left:

• trackExpressionValue must receive a callback
• The callback must be passed to a visitor (ReturnVisitor for now)
• Tests to verify that ReturnVisitor actually does what we intend it to do (call the callback at the right place).

[vsavchenko]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

895

function_ref is a reference, it doesn't own the function. It means that it shouldn't outlive the actual function object (very similar to StringRef).

[xazax.hun]

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

95

Are we anticipating visitors that do something else other than calling a callback when they are stopped? If that is not the case, I wonder if storing/invoking the visitor in this class would make more sense.

97

Should we allow derived classes or even others query if a visitor was stopped? Or is this only for catching bugs?

101

I prefer really small functions, like this dtor to be in header files. Feel free to ignore.

104

Do you anticipate cases where the visitor itself does not know that it needs to stop (e.g. in the Visit functions) so someone needs to call this from the outside?

[RedDocMD]

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

95

I think it was decided in the last meet that we should not make this new abstraction overtly specific. So a stoppable visitor is free to have a callback (like the ReturnVisitor now does) and is also free to have some more behavior in the OnStop method. Also making the OnStop method pure-virtual means that the sub-classes are required to override it (so it can't be ignored).

97

Right now it can't be queried. The purpose of the Stopped field is primarily for catching bugs. (this ensures visitors are stopped exactly once).

104

No, I don't. Are you suggesting I should make it a protected method?

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

895

So I guess this means that the callback must be a method/lambda that persists (ie, it can't be a lambda in a VisitNode method, but must be stored a field in the class).

1154

I am not entirely certain this is the right place to call the Stop method. It seems reasonable but I am not sure.

[RedDocMD]

trackExpressionValue recieving callback, passing it to ReturnVisitor

[RedDocMD]

The following things are now done:

• trackExpressionValue must receive a callback
• The callback must be passed to a visitor (ReturnVisitor for now)

I still don't know a good way to test the following:

• Tests to verify that ReturnVisitor actually does what we intend it to do (call the callback at the right place).

@vsavchenko, @NoQ, @xazax.hun, @teemperor can you give some suggestions?

[NoQ]

Tests to verify that ReturnVisitor actually does what we intend it to do (call the callback at the right place).

You mean write a test that demonstrates that? I guess unless we're willing to wait for the checker to catch up, a good approach to this would be to write a unit test. See unittests/StaticAnalyzer - there aren't many of them because they're relatively hard to write but these days they're getting more and more popular as we're trying to eliminate mutually exclusive bugs invisible on LIT tests. You can mock some code, emit a warning against it from a mocked checker, and test directly that the visitor is stopped at, say, a given node or a given line number.

Or you mean like, add an assert that ensures that you're doing right thing? I think this is also possible to some extent. For example, you can check when the visitor is stopped that no other visitors were added during the current VisitNode() invocation (otherwise the process has to continue). Or you could assert the opposite: if the visitor has run to completion and no other visitors were added then the callback has to be invoked. I think this can get messy really quickly (esp. knowing that you can't simply count all visitors to see if more were added, given how newly added visitors may be duplicates of existing visitors). But I suspect that it could be easy to check this in at least one direction.

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

109

I think we have to use std::function here.

/// An efficient, type-erasing, non-owning reference to a callable. This is
/// intended for use as the type of a function parameter that is not used
/// after the function in question returns.
///
/// This class does not own the callable, so it is not in general safe to store
/// a function_ref.
template<typename Fn> class function_ref;

An llvm::function_ref becomes a dangling reference as soon as trackExpressionValue() returns. This is too early.

[balazske]

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

95

According to the conventions, should use stop and onStop instead of Stop, OnStop?

[vsavchenko]

I was thinking a lot about this problem after our last call, and even though StoppableVisitor helps to solve the problem that we have, it is extremely unclear when this callback is called and should be called.
I decided to restore the balance (and rid of all younglings, maybe) and put together this interface: D103605. I still need to migrate the existing code into the new architecture, but it can be done incrementally.

[RedDocMD]

In D103434#2795940, @vsavchenko wrote:

I was thinking a lot about this problem after our last call, and even though StoppableVisitor helps to solve the problem that we have, it is extremely unclear when this callback is called and should be called.
I decided to restore the balance (and rid of all younglings, maybe) and put together this interface: D103605. I still need to migrate the existing code into the new architecture, but it can be done incrementally.

Right. I then perhaps should focus now on D98726, and then return to GetNoteEmitter.

[RedDocMD]

I am closing this since it has been addressed much better by the patches from @vsavchenko.

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

public:
   virtual void Profile(llvm::FoldingSetNodeID &ID) const = 0;
 
   /// Generates the default final diagnostic piece.
   static PathDiagnosticPieceRef
   getDefaultEndPath(const BugReporterContext &BRC, const ExplodedNode *N,
                     const PathSensitiveBugReport &BR);
 };
 
+/// StoppableBugReporterVisitor is a special type of visitor that is known to
+/// not have any useful work to do after it reaches a certain node in its
+/// traversal. When it does reach that node, the \ref Stop method must be
+/// called. This in turn calls the \ref OnStop method (which must be overriden
+/// in the sub-class). Note that such visitors *must* be stopped exactly once.
+class StoppableBugReporterVisitor : public BugReporterVisitor {
+  /// This method is run once the \ref Stop method is called.
+  virtual void OnStop(const ExplodedNode *Curr, BugReporterContext &BRC,
+                      PathSensitiveBugReport &BR) const = 0;
+  bool Stopped;
+
+public:
+  StoppableBugReporterVisitor() : Stopped{false} {}
+  virtual ~StoppableBugReporterVisitor();
+
+  /// Call this method once the visitor runs out of useful nodes to process.
+  void Stop(const ExplodedNode *Curr, BugReporterContext &BRC,
+            PathSensitiveBugReport &BR);
+};
+
+// Callback type for trackExpressionValue
+using VisitorCallback = llvm::function_ref<void(
+    const ExplodedNode *, BugReporterContext &, PathSensitiveBugReport &)>;
+
 namespace bugreporter {
 
 /// Specifies the type of tracking for an expression.
 enum class TrackingKind {
   /// Default tracking kind -- specifies that as much information should be
   /// gathered about the tracked expression value as possible.
   Thorough,
   /// Specifies that a more moderate tracking should be used for the expression

 ///         suppression (inlined defensive checks, returned null).
 ///
 /// \return Whether or not the function was able to add visitors for this
 ///         statement. Note that returning \c true does not actually imply
 ///         that any visitors were added.
 bool trackExpressionValue(const ExplodedNode *N, const Expr *E,
                           PathSensitiveBugReport &R,
                           TrackingKind TKind = TrackingKind::Thorough,
-                          bool EnableNullFPSuppression = true);
+                          bool EnableNullFPSuppression = true,
+                          VisitorCallback Callback = nullptr);
 
 const Expr *getDerefExpr(const Stmt *S);
 
 } // namespace bugreporter
 
 /// Finds last store into the given region,
 /// which is different from a given symbolic value.
 class FindLastStoreBRVisitor final : public BugReporterVisitor {

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

auto P = std::make_shared<PathDiagnosticEventPiece>(
       L, BR.getDescription(), Ranges.begin() == Ranges.end());
   for (SourceRange Range : Ranges)
     P->addRange(Range);
 
   return P;
 }
 
 //===----------------------------------------------------------------------===//
+// Implementation of StoppableBugReporterVisitor
+//===----------------------------------------------------------------------===//
+
+StoppableBugReporterVisitor::~StoppableBugReporterVisitor() {
+  assert(Stopped && "Stoppable visitor not stopped in its lifetime");
+}
+
+void StoppableBugReporterVisitor::Stop(const ExplodedNode *Curr,
+                                       BugReporterContext &BRC,
+                                       PathSensitiveBugReport &BR) {
+  assert(!Stopped && "Stop() can be called only once in visitor's lifetime");
+  Stopped = true;
+  OnStop(Curr, BRC, BR);
+}
+
+//===----------------------------------------------------------------------===//
 // Implementation of NoStoreFuncVisitor.
 //===----------------------------------------------------------------------===//
 
 namespace {
 
 /// Put a diagnostic on return statement of all inlined functions
 /// for which  the region of interest \p RegionOfInterest was passed into,
 /// but not written inside, and it has caused an undefined read or a null
Optional<SourceLocation> matchAssignment(const ExplodedNode *N) {
     return None;
   }
 };
 
 } // end of anonymous namespace
 
 namespace {
 
 /// Emits an extra note at the return statement of an interesting stack frame.
 ///
 /// The returned value is marked as an interesting value, and if it's null,
 /// adds a visitor to track where it became null.
 ///
 /// This visitor is intended to be used when another visitor discovers that an
 /// interesting value comes from an inlined function call.
-class ReturnVisitor : public BugReporterVisitor {
+class ReturnVisitor : public StoppableBugReporterVisitor {
   const StackFrameContext *CalleeSFC;
   enum {
     Initial,
     MaybeUnsuppress,
     Satisfied
   } Mode = Initial;
 
   bool EnableNullFPSuppression;
   bool ShouldInvalidate = true;
   AnalyzerOptions& Options;
   bugreporter::TrackingKind TKind;
+  VisitorCallback Callback;
 
 public:
   ReturnVisitor(const StackFrameContext *Frame, bool Suppressed,
-                AnalyzerOptions &Options, bugreporter::TrackingKind TKind)
-      : CalleeSFC(Frame), EnableNullFPSuppression(Suppressed),
-        Options(Options), TKind(TKind) {}
+                AnalyzerOptions &Options, bugreporter::TrackingKind TKind,
+                VisitorCallback &&Callback)
+      : CalleeSFC(Frame), EnableNullFPSuppression(Suppressed), Options(Options),
+        TKind(TKind), Callback(Callback) {}
 
   static void *getTag() {
     static int Tag = 0;
     return static_cast<void *>(&Tag);
   }
 
   void Profile(llvm::FoldingSetNodeID &ID) const override {
     ID.AddPointer(ReturnVisitor::getTag());
     ID.AddPointer(CalleeSFC);
     ID.AddBoolean(EnableNullFPSuppression);
   }
 
+  void OnStop(const ExplodedNode *Curr, BugReporterContext &BRC,
+              PathSensitiveBugReport &BR) const override {
+    if (Callback) {
+      Callback(Curr, BRC, BR);
+    }
+  }
+
   /// Adds a ReturnVisitor if the given statement represents a call that was
   /// inlined.
   ///
   /// This will search back through the ExplodedGraph, starting from the given
   /// node, looking for when the given statement was processed. If it turns out
   /// the statement is a call that was inlined, we add the visitor to the
   /// bug report, so it can print a note later.
   static void addVisitorIfNecessary(const ExplodedNode *Node, const Stmt *S,
                                     PathSensitiveBugReport &BR,
                                     bool InEnableNullFPSuppression,
-                                    bugreporter::TrackingKind TKind) {
+                                    bugreporter::TrackingKind TKind,
+                                    VisitorCallback Callback) {
     if (!CallEvent::isCallStmt(S))
       return;
 
     // First, find when we processed the statement.
     // If we work with a 'CXXNewExpr' that is going to be purged away before
     // its call take place. We would catch that purge in the last condition
     // as a 'StmtPoint' so we have to bypass it.
     const bool BypassCXXNewExprEval = isa<CXXNewExpr>(S);
static void addVisitorIfNecessary(const ExplodedNode *Node, const Stmt *S,
     AnalyzerOptions &Options = State->getAnalysisManager().options;
 
     bool EnableNullFPSuppression = false;
     if (InEnableNullFPSuppression &&
         Options.ShouldSuppressNullReturnPaths)
       if (Optional<Loc> RetLoc = RetVal.getAs<Loc>())
         EnableNullFPSuppression = State->isNull(*RetLoc).isConstrainedTrue();
 
-    BR.addVisitor(std::make_unique<ReturnVisitor>(CalleeContext,
-                                                   EnableNullFPSuppression,
-                                                   Options, TKind));
+    BR.addVisitor(
+        std::make_unique<ReturnVisitor>(CalleeContext, EnableNullFPSuppression,
+                                        Options, TKind, std::move(Callback)));
   }
 
   PathDiagnosticPieceRef visitNodeInitial(const ExplodedNode *N,
                                           BugReporterContext &BRC,
                                           PathSensitiveBugReport &BR) {
     // Only print a message at the interesting return statement.
     if (N->getLocationContext() != CalleeSFC)
       return nullptr;
PathDiagnosticPieceRef visitNodeInitial(const ExplodedNode *N,
 
     // If we determined that the note is meaningless, make it prunable, and
     // don't mark the stackframe interesting.
     if (WouldEventBeMeaningless)
       EventPiece->setPrunable(true);
     else
       BR.markInteresting(CalleeSFC);
 
+    // Since we know that no other notes will be emitted subsequently by this
+    // visitor.
+    Stop(N, BRC, BR);
+
     return EventPiece;
   }
 
   PathDiagnosticPieceRef visitNodeMaybeUnsuppress(const ExplodedNode *N,
                                                   BugReporterContext &BRC,
                                                   PathSensitiveBugReport &BR) {
     assert(Options.ShouldAvoidSuppressingNullArgumentPaths);
 
if (LHSV.isZeroConstant())
                            EnableNullFPSuppression);
   }
 }
 
 bool bugreporter::trackExpressionValue(const ExplodedNode *InputNode,
                                        const Expr *E,
                                        PathSensitiveBugReport &report,
                                        bugreporter::TrackingKind TKind,
-                                       bool EnableNullFPSuppression) {
+                                       bool EnableNullFPSuppression,
+                                       VisitorCallback Callback) {
 
   if (!E || !InputNode)
     return false;
 
   const Expr *Inner = peelOffOuterExpr(E, InputNode);
   const ExplodedNode *LVNode = findNodeForExpression(InputNode, Inner);
   if (!LVNode)
     return false;
if (ExplodedGraph::isInterestingLValueExpr(Inner)) {
     }
   }
 
   // If the expression is not an "lvalue expression", we can still
   // track the constraints on its contents.
   SVal V = LVState->getSValAsScalarOrLoc(Inner, LVNode->getLocationContext());
 
   ReturnVisitor::addVisitorIfNecessary(
-    LVNode, Inner, report, EnableNullFPSuppression, TKind);
+      LVNode, Inner, report, EnableNullFPSuppression, TKind, Callback);
 
   // Is it a symbolic value?
   if (auto L = V.getAs<loc::MemRegionVal>()) {
     // FIXME: this is a hack for fixing a later crash when attempting to
     // dereference a void* pointer.
     // We should not try to dereference pointers at all when we don't care
     // what is written inside the pointer.
     bool CanDereference = true;