[analyzer] Change FindLastStoreBRVisitor to use Tracker

[vsavchenko]

Summary

Additionally, this commit completely removes any uses of
FindLastStoreBRVisitor from the analyzer except for the
one in Tracker.

The next step is actually removing this class altogether
from the header file.

[vsavchenko]

Rebase

[vsavchenko]

This one is completely wrong though. Visitor can definitely outlive Tracker, unlike handlers. I need to use some reference-counting solution here.

[vsavchenko]

Fix dangling reference problem

[vsavchenko]

Rebase

[NoQ]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

2273

How does lifetime work here? Do I understand correctly that the tracker is only kept alive by the FindLastStoreBRVisitor instance, even after its completion?

[vsavchenko]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

2273

Correct, every TrackingVisitor keeps its parent tracker alive. We can optimize it a bit by setting it to null when the visitor is done early. But it feels like such a negligible gain that I didn't bother.

[vsavchenko]

Rebase

[NoQ]

Got it, thanks!

[Szelethus]

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

367–368

Different or nested? (D64272)

[vsavchenko]

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

367–368

I'm not sure I understand this question, but it is simply a refactoring, all parameters come from previous interfaces.

[Szelethus]

I know I'm late to the party, and am just mostly thinking aloud. Awesome patch series!

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

331–341

Maybe we could draw more attention to the fact this is a major component of bug report construction? Dividers like this maybe:

//===----------------------------------------------------------------------===//
// Visitor core components.
//===----------------------------------------------------------------------===//

class BugReporterVisitor {};
// ...

class TrackingBugReporterVisitor {};

//===----------------------------------------------------------------------===//
// Specific visitors.
//===----------------------------------------------------------------------===//

340

Why is this a parent tracker? Could visitors have their own child trackers?

367–368

Oh well, then its likely me that made this mistake :^)

Both f's and h's stack frame is different to g's, but only f is nested. As a top level function, the bug path would start from h, so arrows and function call events would be present in it. f may be pruned (no diagnostic pieces would point to it), if the analyzer decides that nothing interesting happens in it (not this, but maybe a similar example). Following this logic, we're looking for nested stack frames in particular, to tell the analyzer not to prune them.

void f(int **p) {
  *p = NULL; // At the point of assignment, the stackframe of f is nested in g's stackframe
}

void h() {
  *p = malloc(...); 
  g(p); // h calls g, g's stackframe is nested in h's
}

void g(int **p) {
  f(p);
  **p = 5; // warning: nullptr reference
}

The comment is a little dumb, as it explicitly mentions "nested" a sentence later.

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

 #ifndef LLVM_CLANG_STATICANALYZER_CORE_BUGREPORTER_BUGREPORTERVISITORS_H
 #define LLVM_CLANG_STATICANALYZER_CORE_BUGREPORTER_BUGREPORTERVISITORS_H
 
 #include "clang/Analysis/ProgramPoint.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 #include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/IntrusiveRefCntPtr.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include <list>
 #include <memory>
 #include <utility>
 
 namespace clang {
 
struct StoreInfo {
   SVal Value;
   /// Memory regions involved in the store operation.
   ///   Dest <- Origin
   /// NOTE: Origin might be null, when the stored value doesn't come
   ///       from another region.
   const MemRegion *Dest, *Origin;
 };
 
+class Tracker;
+using TrackerRef = llvm::IntrusiveRefCntPtr<Tracker>;
+
 class ExpressionHandler;
 class StoreHandler;
 
 /// A generalized component for tracking expressions, values, and stores.
 ///
 /// Tracker aimes at providing a sensible set of default behaviors that can be
 /// used by any checker, while providing mechanisms to hook into any part of the
 /// tracking process and insert checker-specific logic.
-class Tracker {
+class Tracker : public llvm::RefCountedBase<Tracker> {
 private:
   using ExpressionHandlerPtr = std::unique_ptr<ExpressionHandler>;
   using StoreHandlerPtr = std::unique_ptr<StoreHandler>;
 
   PathSensitiveBugReport &Report;
   std::list<ExpressionHandlerPtr> ExpressionHandlers;
   std::list<StoreHandlerPtr> StoreHandlers;
 
-public:
+protected:
   /// \param Report The bug report to which visitors should be attached.
   Tracker(PathSensitiveBugReport &Report);
+
+public:
   virtual ~Tracker() = default;
 
+  static TrackerRef create(PathSensitiveBugReport &Report) {
+    return new Tracker(Report);
+  }
+
   PathSensitiveBugReport &getReport() { return Report; }
 
   /// Describes a tracking result with the most basic information of what was
   /// actually done (or not done).
   struct Result {
     /// Usually it means that the tracker added visitors.
     bool FoundSomethingToTrack = false;
     /// Signifies that the tracking was interrupted at some point.
public:
   ///
   /// \return the produced note, null if the handler doesn't support this kind
   ///         of stores.
   virtual PathDiagnosticPieceRef handle(StoreInfo SI, TrackingOptions Opts) = 0;
 
   Tracker &getParentTracker() { return ParentTracker; }
 };
 
+/// Visitor that tracks expressions and values.
+class TrackingBugReporterVisitor : public BugReporterVisitor {
+private:
+  TrackerRef ParentTracker;
+
+public:
+  TrackingBugReporterVisitor(TrackerRef ParentTracker)
+      : ParentTracker(ParentTracker) {}
+
+  Tracker &getParentTracker() { return *ParentTracker; }
+};
+
 /// Attempts to add visitors to track expression value back to its point of
 /// origin.
 ///
 /// \param N A node "downstream" from the evaluation of the statement.
 /// \param E The expression value which we are tracking
 /// \param R The bug report to which visitors should be attached.
 /// \param EnableNullFPSuppression Whether we should employ false positive
 ///         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);
 
+/// Track how the value got stored into the given region and where it came
+/// from.
+///
+/// \param V We're searching for the store where \c R received this value.
+/// \param R The region we're tracking.
+/// \param Opts Tracking options specifying how we want to track the value.
+/// \param Origin Only adds notes when the last store happened in a
+///        different stackframe to this one. Disregarded if the tracking kind
+///        is thorough.
+///        This is useful, because for non-tracked regions, notes about
+///        changes to its value in a nested stackframe could be pruned, and
+///        this visitor can prevent that without polluting the bugpath too
+///        much.
+void trackStoredValue(KnownSVal V, const MemRegion *R,
+                      PathSensitiveBugReport &Report, TrackingOptions Opts = {},
+                      const StackFrameContext *Origin = 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 {
+class FindLastStoreBRVisitor final
+    : public bugreporter::TrackingBugReporterVisitor {
   const MemRegion *R;
   SVal V;
   bool Satisfied = false;
 
   /// If the visitor is tracking the value directly responsible for the
   /// bug, we are going to employ false positive suppression.
   bool EnableNullFPSuppression;
 
   using TrackingKind = bugreporter::TrackingKind;
   TrackingKind TKind;
   const StackFrameContext *OriginSFC;
 
 public:
   /// \param V We're searching for the store where \c R received this value.
   /// \param R The region we're tracking.
   /// \param TKind May limit the amount of notes added to the bug report.
   /// \param OriginSFC Only adds notes when the last store happened in a
   ///        different stackframe to this one. Disregarded if the tracking kind
   ///        is thorough.
   ///        This is useful, because for non-tracked regions, notes about
   ///        changes to its value in a nested stackframe could be pruned, and
   ///        this visitor can prevent that without polluting the bugpath too
   ///        much.
-  FindLastStoreBRVisitor(KnownSVal V, const MemRegion *R,
-                         bool InEnableNullFPSuppression, TrackingKind TKind,
+  FindLastStoreBRVisitor(bugreporter::TrackerRef ParentTracker, KnownSVal V,
+                         const MemRegion *R, bool InEnableNullFPSuppression,
+                         TrackingKind TKind,
                          const StackFrameContext *OriginSFC = nullptr)
-      : R(R), V(V), EnableNullFPSuppression(InEnableNullFPSuppression),
-        TKind(TKind), OriginSFC(OriginSFC) {
+      : TrackingBugReporterVisitor(ParentTracker), R(R), V(V),
+        EnableNullFPSuppression(InEnableNullFPSuppression), TKind(TKind),
+        OriginSFC(OriginSFC) {
     assert(R);
   }
 
   void Profile(llvm::FoldingSetNodeID &ID) const override;
 
   PathDiagnosticPieceRef VisitNode(const ExplodedNode *N,
                                    BugReporterContext &BRC,
                                    PathSensitiveBugReport &BR) override;

clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountDiagnostics.cpp

if (!AllVarBindings.empty() &&
     // Let's pick one of them at random (if there is something to pick from).
     AllocBindingToReport = AllVarBindings[0].first;
 
     // Because 'AllocBindingToReport' is not the the same as
     // 'AllocFirstBinding', we need to explain how the leaking object
     // got from one to another.
     //
     // NOTE: We use the actual SVal stored in AllocBindingToReport here because
-    //       FindLastStoreBRVisitor compares SVal's and it can get trickier for
+    //       trackStoredValue compares SVal's and it can get trickier for
     //       something like derived regions if we want to construct SVal from
     //       Sym. Instead, we take the value that is definitely stored in that
-    //       region, thus guaranteeing that FindLastStoreBRVisitor will work.
-    addVisitor<FindLastStoreBRVisitor>(
-        AllVarBindings[0].second.castAs<KnownSVal>(), AllocBindingToReport,
-        false, bugreporter::TrackingKind::Thorough);
+    //       region, thus guaranteeing that trackStoredValue will work.
+    bugreporter::trackStoredValue(AllVarBindings[0].second.castAs<KnownSVal>(),
+                                  AllocBindingToReport, *this);
   } else {
     AllocBindingToReport = AllocFirstBinding;
   }
 }
 
 RefLeakReport::RefLeakReport(const RefCountBug &D, const LangOptions &LOpts,
                              ExplodedNode *N, SymbolRef Sym,
                              CheckerContext &Ctx)

clang/lib/StaticAnalyzer/Checkers/UndefCapturedBlockVarChecker.cpp

if (Optional<UndefinedVal> V =
         llvm::raw_svector_ostream os(buf);
 
         os << "Variable '" << VD->getName()
            << "' is uninitialized when captured by block";
 
         auto R = std::make_unique<PathSensitiveBugReport>(*BT, os.str(), N);
         if (const Expr *Ex = FindBlockDeclRefExpr(BE->getBody(), VD))
           R->addRange(Ex->getSourceRange());
-        R->addVisitor(std::make_unique<FindLastStoreBRVisitor>(
-            *V, VR, /*EnableNullFPSuppression*/ false,
-            bugreporter::TrackingKind::Thorough));
+        bugreporter::trackStoredValue(*V, VR, *R,
+                                      {bugreporter::TrackingKind::Thorough,
+                                       /*EnableNullFPSuppression*/ false});
         R->disablePathPruning();
         // need location of block
         C.emitReport(std::move(R));
       }
     }
   }
 }
 
 void ento::registerUndefCapturedBlockVarChecker(CheckerManager &mgr) {
   mgr.registerChecker<UndefCapturedBlockVarChecker>();
 }
 
 bool ento::shouldRegisterUndefCapturedBlockVarChecker(const CheckerManager &mgr) {
   return true;
 }

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

FindLastStoreBRVisitor::VisitNode(const ExplodedNode *Succ,
   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();
 
-    bugreporter::trackExpressionValue(StoreSite, InitE, BR, TKind,
-                                      EnableNullFPSuppression);
+    getParentTracker().track(InitE, StoreSite,
+                             {TKind, EnableNullFPSuppression});
   }
 
   // Let's try to find the region where the value came from.
   const MemRegion *OldRegion = nullptr;
 
   // If we have init expression, it might be simply a reference
   // to a variable, so we can use it.
   if (InitE) {
if (DS) {
       if (VR) {
         // See if we can get the BlockVarRegion.
         ProgramStateRef State = StoreSite->getState();
         SVal V = StoreSite->getSVal(S);
         if (const auto *BDR =
               dyn_cast_or_null<BlockDataRegion>(V.getAsRegion())) {
           if (const VarRegion *OriginalR = BDR->getOriginalRegion(VR)) {
             if (auto KV = State->getSVal(OriginalR).getAs<KnownSVal>())
-              BR.addVisitor<FindLastStoreBRVisitor>(
-                  *KV, OriginalR, EnableNullFPSuppression, TKind, OriginSFC);
+              getParentTracker().track(
+                  *KV, OriginalR, {TKind, EnableNullFPSuppression}, OriginSFC);
           }
         }
       }
     }
     if (action)
       showBRDiagnostics(action, os, R, V, OldRegion, DS);
 
   } else if (StoreSite->getLocation().getAs<CallEnter>()) {
Tracker::Result Tracker::track(const Expr *E, const ExplodedNode *N,
 
   return CombinedResult;
 }
 
 Tracker::Result Tracker::track(SVal V, const MemRegion *R, TrackingOptions Opts,
                                const StackFrameContext *Origin) {
   if (auto KV = V.getAs<KnownSVal>()) {
     Report.addVisitor<FindLastStoreBRVisitor>(
-        *KV, R, Opts.EnableNullFPSuppression, Opts.Kind, Origin);
+        this, *KV, R, Opts.EnableNullFPSuppression, Opts.Kind, Origin);
     return {true};
   }
   return {};
 }
 
 PathDiagnosticPieceRef Tracker::handle(StoreInfo SI, TrackingOptions Opts) {
   // Iterate through the handlers in the order according to their priorities.
   for (StoreHandlerPtr &Handler : StoreHandlers) {
     if (PathDiagnosticPieceRef Result = Handler->handle(SI, Opts))
       // If the handler produced a non-null piece, return it.
       // There is no need in asking other handlers.
       return Result;
   }
   return {};
 }
 
 bool bugreporter::trackExpressionValue(const ExplodedNode *InputNode,
                                        const Expr *E,
                                        PathSensitiveBugReport &report,
                                        bugreporter::TrackingKind TKind,
                                        bool EnableNullFPSuppression) {
-  return Tracker(report)
-      .track(E, InputNode, {TKind, EnableNullFPSuppression})
+  return Tracker::create(report)
+      ->track(E, InputNode, {TKind, EnableNullFPSuppression})
       .FoundSomethingToTrack;
 }
 
+void bugreporter::trackStoredValue(KnownSVal V, const MemRegion *R,
+                                   PathSensitiveBugReport &Report,
+                                   TrackingOptions Opts,
+                                   const StackFrameContext *Origin) {
+  Tracker::create(Report)->track(V, R, Opts, Origin);
+}
+
 //===----------------------------------------------------------------------===//
 // Implementation of NulReceiverBRVisitor.
 //===----------------------------------------------------------------------===//
 
 const Expr *NilReceiverBRVisitor::getNilReceiver(const Stmt *S,
                                                  const ExplodedNode *N) {
   const auto *ME = dyn_cast<ObjCMessageExpr>(S);
   if (!ME)