[analyzer] Do not run visitors until the fixpoint, run only once

[george.karpenkov]

Summary

In the current implementation, we run visitors until the fixed point is reached.
That is, if a visitor adds another visitor, the currently processed path is destroyed, all diagnostics is discarded, and it is regenerated again, until it's no longer modified.
This pattern has a few negative implications:

• This loop does not even guarantee to terminate. E.g. just imagine two visitors bouncing a diagnostics around.
• Performance-wise, e.g. for sqlite3 all visitors are being re-run at least 10 times for some bugs. We have already seen a few reports where it leads to timeouts.
• If we want to add more computationally intense visitors, this will become worse
• From architectural standpoint, the current layout requires copying visitors, which is conceptually wrong, and can be annoying (e.g. no unique_ptr on visitors allowed)

The proposed change is a much simpler architecture: the outer loop processes nodes upwards, and whenever the visitor is added it only processes current nodes and above, thus guaranteeing termination.

[mikhail.ramalho]

Just a heads-up: FalsePositiveRefutationBRVisitor in BugReporterVisitors.h needs to be updated as well, as per the current master.

[george.karpenkov]

Fix the test crash associated with last piece of diagnostic.

Only let the visitors added initially (with the report generation) change the last piece.

[george.karpenkov]

Current problem: visitors are reused across different consumers, so the current code does not work for plist/html/etc, as the second invocation of the visitor will be incorrect (as state has changed by then).

[george.karpenkov]

Now the code *really* runs each visitor only once, even when multiple consumers are present.
5 tests still failing.

[george.karpenkov]

All tests are passing now. The diff is larger then necessary due to a few functions which I had to move around.

[george.karpenkov]

Rebased, minor cleanup.

[george.karpenkov]

Updated, another cleanup.

[NoQ]

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

484–488

Maybe just remove the implementation?

clang/lib/StaticAnalyzer/Core/BugReporter.cpp

1884–1890

I suggest:

This function is responsible for generating diagnostic pieces that are *not* provided by bug report visitors, once visitors populate VisitorsCache with their diagnostics for every node. These diagnostics may differ depending on the consumer's settings, and are therefore constructed separately for each consumer. Namely, there are two path diagnostics generation modes: ...

Then probably rename VisitorsCache to VisitorDiagnostics because it doesn't really act like a cache (i.e. we won't invoke the visitor if the diagnostic is missing in the cache).

[george.karpenkov]

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

484–488

This cannot be done. BugReporter is actually not an abstract class, but a bug reporter class used for path-insenstive diagnostics.

[NoQ]

Let's make BugReporter great again. One bug report at a time.

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

 #include "llvm/ADT/ilist_node.h"
 #include "llvm/ADT/iterator_range.h"
 #include <cassert>
 #include <memory>
 #include <string>
 #include <utility>
 #include <vector>
 
+#include<set>
+
 namespace clang {
 
 class AnalyzerOptions;
 class ASTContext;
 class Decl;
 class DiagnosticsEngine;
 class LocationContext;
 class SourceManager;
protected:
   llvm::SmallSet<const LocationContext *, 2> InterestingLocationContexts;
 
   /// A set of custom visitors which generate "event" diagnostics at
   /// interesting points in the path.
   VisitorList Callbacks;
 
   /// Used for ensuring the visitors are only added once.
   llvm::FoldingSet<BugReporterVisitor> CallbacksSet;
-
-  /// Used for clients to tell if the report's configuration has changed
-  /// since the last time they checked.
-  unsigned ConfigurationChangeToken = 0;
-  
+  std::set<unsigned> CallbacksHashes;
   /// When set, this flag disables all callstack pruning from a diagnostic
   /// path.  This is useful for some reports that want maximum fidelty
   /// when reporting an issue.
   bool DoNotPrunePath = false;
 
   /// Used to track unique reasons why a bug report might be invalid.
   ///
   /// \sa markInvalid
public:
   void markInteresting(SVal V);
   void markInteresting(const LocationContext *LC);
   
   bool isInteresting(SymbolRef sym);
   bool isInteresting(const MemRegion *R);
   bool isInteresting(SVal V);
   bool isInteresting(const LocationContext *LC);
 
-  unsigned getConfigurationChangeToken() const {
-    return ConfigurationChangeToken;
-  }
-
   /// Returns whether or not this report should be considered valid.
   ///
   /// Invalid reports are those that have been classified as likely false
   /// positives after the fact.
   bool isValid() const {
     return Invalidations.empty();
   }
 
public:
   ///
   /// The visitors should be used when the default trace is not sufficient.
   /// For example, they allow constructing a more elaborate trace.
   /// \sa registerConditionVisitor(), registerTrackNullOrUndefValue(),
   /// registerFindLastStore(), registerNilReceiverVisitor(), and
   /// registerVarDeclsLastStore().
   void addVisitor(std::unique_ptr<BugReporterVisitor> visitor);
 
+  /// Remove all visitors attached to this bug report.
+  void clearVisitors();
+
   /// Iterators through the custom diagnostic visitors.
   visitor_iterator visitor_begin() { return Callbacks.begin(); }
   visitor_iterator visitor_end() { return Callbacks.end(); }
 
   /// Profile to identify equivalent bug reports for error report coalescing.
   /// Reports are uniqued to ensure that we do not emit multiple diagnostics
   /// for each bug.
   virtual void Profile(llvm::FoldingSetNodeID& hash) const;
public:
   SourceManager &getSourceManager() { return D.getSourceManager(); }
 
   AnalyzerOptions &getAnalyzerOptions() { return D.getAnalyzerOptions(); }
 
   virtual bool generatePathDiagnostic(PathDiagnostic& pathDiagnostic,
                                       PathDiagnosticConsumer &PC,
                                       ArrayRef<BugReport *> &bugReports) {
     return true;
   }
 
   void Register(BugType *BT);
 
   /// Add the given report to the set of reports tracked by BugReporter.
   ///
   /// The reports are usually generated by the checkers. Further, they are
   /// folded based on the profile value, which is done to coalesce similar
   /// reports.
   void emitReport(std::unique_ptr<BugReport> R);
 
   void EmitBasicReport(const Decl *DeclWithIssue, const CheckerBase *Checker,
                        StringRef BugName, StringRef BugCategory,

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

 
 class BugReport;
 class BugReporterContext;
 class ExplodedNode;
 class MemRegion;
 class PathDiagnosticPiece;
 
 /// BugReporterVisitors are used to add custom diagnostics along a path.
-///
-/// Custom visitors should subclass the BugReporterVisitorImpl class for a
-/// default implementation of the clone() method.
-/// (Warning: if you have a deep subclass of BugReporterVisitorImpl, the
-/// default implementation of clone() will NOT do the right thing, and you
-/// will have to provide your own implementation.)
 class BugReporterVisitor : public llvm::FoldingSetNode {
 public:
   BugReporterVisitor() = default;
   BugReporterVisitor(const BugReporterVisitor &) = default;
   BugReporterVisitor(BugReporterVisitor &&) {}
   virtual ~BugReporterVisitor();
 
-  /// Returns a copy of this BugReporter.
-  ///
-  /// Custom BugReporterVisitors should not override this method directly.
-  /// Instead, they should inherit from BugReporterVisitorImpl and provide
-  /// a protected or public copy constructor.
-  ///
-  /// (Warning: if you have a deep subclass of BugReporterVisitorImpl, the
-  /// default implementation of clone() will NOT do the right thing, and you
-  /// will have to provide your own implementation.)
-  virtual std::unique_ptr<BugReporterVisitor> clone() const = 0;
-
   /// Return a diagnostic piece which should be associated with the
   /// given node.
   ///
   /// The last parameter can be used to register a new visitor with the given
   /// BugReport while processing a node.
   virtual std::shared_ptr<PathDiagnosticPiece>
   VisitNode(const ExplodedNode *Succ, const ExplodedNode *Pred,
             BugReporterContext &BRC, BugReport &BR) = 0;
public:
   virtual void Profile(llvm::FoldingSetNodeID &ID) const = 0;
 
   /// Generates the default final diagnostic piece.
   static std::unique_ptr<PathDiagnosticPiece>
   getDefaultEndPath(BugReporterContext &BRC, const ExplodedNode *N,
                     BugReport &BR);
 };
 
-/// This class provides a convenience implementation for clone() using the
-/// Curiously-Recurring Template Pattern. If you are implementing a custom
-/// BugReporterVisitor, subclass BugReporterVisitorImpl and provide a public
-/// or protected copy constructor.
-///
-/// (Warning: if you have a deep subclass of BugReporterVisitorImpl, the
-/// default implementation of clone() will NOT do the right thing, and you
-/// will have to provide your own implementation.)
-template <class DERIVED>
-class BugReporterVisitorImpl : public BugReporterVisitor {
-  std::unique_ptr<BugReporterVisitor> clone() const override {
-    return llvm::make_unique<DERIVED>(*static_cast<const DERIVED *>(this));
-  }
-};
-
-class FindLastStoreBRVisitor final
-    : public BugReporterVisitorImpl<FindLastStoreBRVisitor> {
+class FindLastStoreBRVisitor final : public BugReporterVisitor {
   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;
 
public:
   void Profile(llvm::FoldingSetNodeID &ID) const override;
 
   std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N,
                                                  const ExplodedNode *PrevN,
                                                  BugReporterContext &BRC,
                                                  BugReport &BR) override;
 };
 
-class TrackConstraintBRVisitor final
-    : public BugReporterVisitorImpl<TrackConstraintBRVisitor> {
+class TrackConstraintBRVisitor final : public BugReporterVisitor {
   DefinedSVal Constraint;
   bool Assumption;
   bool IsSatisfied = false;
   bool IsZeroCheck;
 
   /// We should start tracking from the last node along the path in which the
   /// value is constrained.
   bool IsTrackingTurnedOn = false;

 
 private:
   /// Checks if the constraint is valid in the current state.
   bool isUnderconstrained(const ExplodedNode *N) const;
 };
 
 /// \class NilReceiverBRVisitor
 /// Prints path notes when a message is sent to a nil receiver.
-class NilReceiverBRVisitor final
-    : public BugReporterVisitorImpl<NilReceiverBRVisitor> {
+class NilReceiverBRVisitor final : public BugReporterVisitor {
 public:
   void Profile(llvm::FoldingSetNodeID &ID) const override {
     static int x = 0;
     ID.AddPointer(&x);
   }
 
   std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N,
                                                  const ExplodedNode *PrevN,
                                                  BugReporterContext &BRC,
                                                  BugReport &BR) override;
 
   /// If the statement is a message send expression with nil receiver, returns
   /// the receiver expression. Returns NULL otherwise.
   static const Expr *getNilReceiver(const Stmt *S, const ExplodedNode *N);
 };
 
 /// Visitor that tries to report interesting diagnostics from conditions.
-class ConditionBRVisitor final
-    : public BugReporterVisitorImpl<ConditionBRVisitor> {
+class ConditionBRVisitor final : public BugReporterVisitor {
   // FIXME: constexpr initialization isn't supported by MSVC2013.
   static const char *const GenericTrueMessage;
   static const char *const GenericFalseMessage;
 
 public:
   void Profile(llvm::FoldingSetNodeID &ID) const override {
     static int x = 0;
     ID.AddPointer(&x);
public:
 
   static bool isPieceMessageGeneric(const PathDiagnosticPiece *Piece);
 };
 
 /// Suppress reports that might lead to known false positives.
 ///
 /// Currently this suppresses reports based on locations of bugs.
 class LikelyFalsePositiveSuppressionBRVisitor final
-    : public BugReporterVisitorImpl<LikelyFalsePositiveSuppressionBRVisitor> {
+    : public BugReporterVisitor {
 public:
   static void *getTag() {
     static int Tag = 0;
     return static_cast<void *>(&Tag);
   }
 
   void Profile(llvm::FoldingSetNodeID &ID) const override {
     ID.AddPointer(getTag());

 };
 
 /// When a region containing undefined value or '0' value is passed 
 /// as an argument in a call, marks the call as interesting.
 ///
 /// As a result, BugReporter will not prune the path through the function even
 /// if the region's contents are not modified/accessed by the call.
 class UndefOrNullArgVisitor final
-    : public BugReporterVisitorImpl<UndefOrNullArgVisitor> {
+    : public BugReporterVisitor {
   /// The interesting memory region this visitor is tracking.
   const MemRegion *R;
 
 public:
   UndefOrNullArgVisitor(const MemRegion *InR) : R(InR) {}
 
   void Profile(llvm::FoldingSetNodeID &ID) const override {
     static int Tag = 0;
     ID.AddPointer(&Tag);
     ID.AddPointer(R);
   }
 
   std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N,
                                                  const ExplodedNode *PrevN,
                                                  BugReporterContext &BRC,
                                                  BugReport &BR) override;
 };
 
-class SuppressInlineDefensiveChecksVisitor final
-    : public BugReporterVisitorImpl<SuppressInlineDefensiveChecksVisitor> {
+class SuppressInlineDefensiveChecksVisitor final : public BugReporterVisitor {
   /// The symbolic value for which we are tracking constraints.
   /// This value is constrained to null in the end of path.
   DefinedSVal V;
 
   /// Track if we found the node where the constraint was first added.
   bool IsSatisfied = false;
 
   /// Since the visitors can be registered on nodes previous to the last
public:
   static const char *getTag();
 
   std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *Succ,
                                                  const ExplodedNode *Pred,
                                                  BugReporterContext &BRC,
                                                  BugReport &BR) override;
 };
 
-class CXXSelfAssignmentBRVisitor final
-    : public BugReporterVisitorImpl<CXXSelfAssignmentBRVisitor> {
+class CXXSelfAssignmentBRVisitor final : public BugReporterVisitor {
   bool Satisfied = false;
 
 public:
   CXXSelfAssignmentBRVisitor() = default;
 
   void Profile(llvm::FoldingSetNodeID &ID) const override {}
 
   std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *Succ,
                                                  const ExplodedNode *Pred,
                                                  BugReporterContext &BRC,
                                                  BugReport &BR) override;
 };
 
 /// The bug visitor prints a diagnostic message at the location where a given
 /// variable was tainted.
-class TaintBugVisitor final : public BugReporterVisitorImpl<TaintBugVisitor> {
+class TaintBugVisitor final : public BugReporterVisitor {
 private:
   const SVal V;
 
 public:
   TaintBugVisitor(const SVal V) : V(V) {}
   void Profile(llvm::FoldingSetNodeID &ID) const override { ID.Add(V); }
 
   std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N,

clang/lib/StaticAnalyzer/Checkers/DeleteWithNonVirtualDtorChecker.cpp

 using namespace clang;
 using namespace ento;
 
 namespace {
 class DeleteWithNonVirtualDtorChecker
     : public Checker<check::PreStmt<CXXDeleteExpr>> {
   mutable std::unique_ptr<BugType> BT;
 
-  class DeleteBugVisitor : public BugReporterVisitorImpl<DeleteBugVisitor> {
+  class DeleteBugVisitor : public BugReporterVisitor {
   public:
     DeleteBugVisitor() : Satisfied(false) {}
     void Profile(llvm::FoldingSetNodeID &ID) const override {
       static int X = 0;
       ID.AddPointer(&X);
     }
     std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N,
                                                    const ExplodedNode *PrevN,

clang/lib/StaticAnalyzer/Checkers/DynamicTypeChecker.cpp

 class DynamicTypeChecker : public Checker<check::PostStmt<ImplicitCastExpr>> {
   mutable std::unique_ptr<BugType> BT;
   void initBugType() const {
     if (!BT)
       BT.reset(
           new BugType(this, "Dynamic and static type mismatch", "Type Error"));
   }
 
-  class DynamicTypeBugVisitor
-      : public BugReporterVisitorImpl<DynamicTypeBugVisitor> {
+  class DynamicTypeBugVisitor : public BugReporterVisitor {
   public:
     DynamicTypeBugVisitor(const MemRegion *Reg) : Reg(Reg) {}
 
     void Profile(llvm::FoldingSetNodeID &ID) const override {
       static int X = 0;
       ID.AddPointer(&X);
       ID.AddPointer(Reg);
     }

clang/lib/StaticAnalyzer/Checkers/DynamicTypePropagation.cpp

class DynamicTypePropagation:
 
   mutable std::unique_ptr<BugType> ObjCGenericsBugType;
   void initBugType() const {
     if (!ObjCGenericsBugType)
       ObjCGenericsBugType.reset(
           new BugType(this, "Generics", categories::CoreFoundationObjectiveC));
   }
 
-  class GenericsBugVisitor : public BugReporterVisitorImpl<GenericsBugVisitor> {
+  class GenericsBugVisitor : public BugReporterVisitor {
   public:
     GenericsBugVisitor(SymbolRef S) : Sym(S) {}
 
     void Profile(llvm::FoldingSetNodeID &ID) const override {
       static int X = 0;
       ID.AddPointer(&X);
       ID.AddPointer(Sym);
     }

clang/lib/StaticAnalyzer/Checkers/LocalizationChecker.cpp

REGISTER_MAP_WITH_PROGRAMSTATE(LocalizedMemMap, const MemRegion *,
                                LocalizedState)
 
 NonLocalizedStringChecker::NonLocalizedStringChecker() {
   BT.reset(new BugType(this, "Unlocalizable string",
                        "Localizability Issue (Apple)"));
 }
 
 namespace {
-class NonLocalizedStringBRVisitor final
-    : public BugReporterVisitorImpl<NonLocalizedStringBRVisitor> {
+class NonLocalizedStringBRVisitor final : public BugReporterVisitor {
 
   const MemRegion *NonLocalizedString;
   bool Satisfied;
 
 public:
   NonLocalizedStringBRVisitor(const MemRegion *NonLocalizedString)
       : NonLocalizedString(NonLocalizedString), Satisfied(false) {
         assert(NonLocalizedString);

clang/lib/StaticAnalyzer/Checkers/MPI-Checker/MPIBugReporter.h

private:
 
   // path-sensitive bug types
   std::unique_ptr<BugType> UnmatchedWaitBugType;
   std::unique_ptr<BugType> MissingWaitBugType;
   std::unique_ptr<BugType> DoubleNonblockingBugType;
 
   /// Bug visitor class to find the node where the request region was previously
   /// used in order to include it into the BugReport path.
-  class RequestNodeVisitor : public BugReporterVisitorImpl<RequestNodeVisitor> {
+  class RequestNodeVisitor : public BugReporterVisitor {
   public:
     RequestNodeVisitor(const MemRegion *const MemoryRegion,
                        const std::string &ErrText)
         : RequestRegion(MemoryRegion), ErrorText(ErrText) {}
 
     void Profile(llvm::FoldingSetNodeID &ID) const override {
       static int X = 0;
       ID.AddPointer(&X);

clang/lib/StaticAnalyzer/Checkers/MacOSKeychainAPIChecker.cpp

private:
   void markInteresting(BugReport *R, const AllocationPair &AP) const {
     R->markInteresting(AP.first);
     R->markInteresting(AP.second->Region);
   }
 
   /// The bug visitor which allows us to print extra diagnostics along the
   /// BugReport path. For example, showing the allocation site of the leaked
   /// region.
-  class SecKeychainBugVisitor
-    : public BugReporterVisitorImpl<SecKeychainBugVisitor> {
+  class SecKeychainBugVisitor : public BugReporterVisitor {
   protected:
     // The allocated region symbol tracked by the main analysis.
     SymbolRef Sym;
 
   public:
     SecKeychainBugVisitor(SymbolRef S) : Sym(S) {}
 
     void Profile(llvm::FoldingSetNodeID &ID) const override {

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

private:
   LeakInfo getAllocationSite(const ExplodedNode *N, SymbolRef Sym,
                              CheckerContext &C) const;
 
   void reportLeak(SymbolRef Sym, ExplodedNode *N, CheckerContext &C) const;
 
   /// The bug visitor which allows us to print extra diagnostics along the
   /// BugReport path. For example, showing the allocation site of the leaked
   /// region.
-  class MallocBugVisitor final
-      : public BugReporterVisitorImpl<MallocBugVisitor> {
+  class MallocBugVisitor final : public BugReporterVisitor {
   protected:
     enum NotificationMode {
       Normal,
       ReallocationFailed
     };
 
     // The allocated region symbol tracked by the main analysis.
     SymbolRef Sym;

clang/lib/StaticAnalyzer/Checkers/MisusedMovedObjectChecker.cpp

checkRegionChanges(ProgramStateRef State,
                      ArrayRef<const MemRegion *> ExplicitRegions,
                      ArrayRef<const MemRegion *> Regions,
                      const LocationContext *LCtx, const CallEvent *Call) const;
   void printState(raw_ostream &Out, ProgramStateRef State,
                   const char *NL, const char *Sep) const override;
 
 private:
   enum MisuseKind {MK_FunCall, MK_Copy, MK_Move};
-  class MovedBugVisitor : public BugReporterVisitorImpl<MovedBugVisitor> {
+  class MovedBugVisitor : public BugReporterVisitor {
   public:
     MovedBugVisitor(const MemRegion *R) : Region(R), Found(false) {}
 
     void Profile(llvm::FoldingSetNodeID &ID) const override {
       static int X = 0;
       ID.AddPointer(&X);
       ID.AddPointer(Region);
     }

clang/lib/StaticAnalyzer/Checkers/NullabilityChecker.cpp

public:
   NullabilityChecksFilter Filter;
   // When set to false no nullability information will be tracked in
   // NullabilityMap. It is possible to catch errors like passing a null pointer
   // to a callee that expects nonnull argument without the information that is
   // stroed in the NullabilityMap. This is an optimization.
   DefaultBool NeedTracking;
 
 private:
-  class NullabilityBugVisitor
-      : public BugReporterVisitorImpl<NullabilityBugVisitor> {
+  class NullabilityBugVisitor : public BugReporterVisitor {
   public:
     NullabilityBugVisitor(const MemRegion *M) : Region(M) {}
 
     void Profile(llvm::FoldingSetNodeID &ID) const override {
       static int X = 0;
       ID.AddPointer(&X);
       ID.AddPointer(Region);
     }

clang/lib/StaticAnalyzer/Checkers/ObjCSuperDeallocChecker.cpp

 
 } // End anonymous namespace.
 
 // Remember whether [super dealloc] has previously been called on the
 // SymbolRef for the receiver.
 REGISTER_SET_WITH_PROGRAMSTATE(CalledSuperDealloc, SymbolRef)
 
 namespace {
-class SuperDeallocBRVisitor final
-    : public BugReporterVisitorImpl<SuperDeallocBRVisitor> {
-
+class SuperDeallocBRVisitor final : public BugReporterVisitor {
   SymbolRef ReceiverSymbol;
   bool Satisfied;
 
 public:
   SuperDeallocBRVisitor(SymbolRef ReceiverSymbol)
       : ReceiverSymbol(ReceiverSymbol),
         Satisfied(false) {}
 

clang/lib/StaticAnalyzer/Checkers/RetainCountChecker.cpp

     const char *getDescription() const override { return ""; }
 
     bool isLeak() const override { return true; }
   };
 
   //===---------===//
   // Bug Reports.  //
   //===---------===//
-
-  class CFRefReportVisitor : public BugReporterVisitorImpl<CFRefReportVisitor> {
+  class CFRefReportVisitor : public BugReporterVisitor {
   protected:
     SymbolRef Sym;
     const SummaryLogTy &SummaryLog;
     bool GCEnabled;
 
   public:
     CFRefReportVisitor(SymbolRef sym, bool gcEnabled, const SummaryLogTy &log)
        : Sym(sym), SummaryLog(log), GCEnabled(gcEnabled) {}

   public:
     CFRefLeakReportVisitor(SymbolRef sym, bool GCEnabled,
                            const SummaryLogTy &log)
        : CFRefReportVisitor(sym, GCEnabled, log) {}
 
     std::unique_ptr<PathDiagnosticPiece> getEndPath(BugReporterContext &BRC,
                                                     const ExplodedNode *N,
                                                     BugReport &BR) override;
-
-    std::unique_ptr<BugReporterVisitor> clone() const override {
-      // The curiously-recurring template pattern only works for one level of
-      // subclassing. Rather than make a new template base for
-      // CFRefReportVisitor, we simply override clone() to do the right thing.
-      // This could be trouble someday if BugReporterVisitorImpl is ever
-      // used for something else besides a convenient implementation of clone().
-      return llvm::make_unique<CFRefLeakReportVisitor>(*this);
-    }
   };
 
   class CFRefReport : public BugReport {
     void addGCModeDescription(const LangOptions &LOpts, bool GCEnabled);
 
   public:
     CFRefReport(CFRefBug &D, const LangOptions &LOpts, bool GCEnabled,
                 const SummaryLogTy &Log, ExplodedNode *n, SymbolRef sym,

clang/lib/StaticAnalyzer/Checkers/TestAfterDivZeroChecker.cpp

public:
 
   void Profile(llvm::FoldingSetNodeID &ID) const {
     ID.AddInteger(BlockID);
     ID.AddPointer(SFC);
     ID.AddPointer(ZeroSymbol);
   }
 };
 
-class DivisionBRVisitor : public BugReporterVisitorImpl<DivisionBRVisitor> {
+class DivisionBRVisitor : public BugReporterVisitor {
 private:
   SymbolRef ZeroSymbol;
   const StackFrameContext *SFC;
   bool Satisfied;
 
 public:
   DivisionBRVisitor(SymbolRef ZeroSymbol, const StackFrameContext *SFC)
       : ZeroSymbol(ZeroSymbol), SFC(SFC), Satisfied(false) {}

clang/lib/StaticAnalyzer/Checkers/ValistChecker.cpp

private:
   void reportLeakedVALists(const RegionVector &LeakedVALists, StringRef Msg1,
                            StringRef Msg2, CheckerContext &C, ExplodedNode *N,
                            bool ReportUninit = false) const;
 
   void checkVAListStartCall(const CallEvent &Call, CheckerContext &C,
                             bool IsCopy) const;
   void checkVAListEndCall(const CallEvent &Call, CheckerContext &C) const;
 
-  class ValistBugVisitor : public BugReporterVisitorImpl<ValistBugVisitor> {
+  class ValistBugVisitor : public BugReporterVisitor {
   public:
     ValistBugVisitor(const MemRegion *Reg, bool IsLeak = false)
         : Reg(Reg), IsLeak(IsLeak) {}
     void Profile(llvm::FoldingSetNodeID &ID) const override {
       static int X = 0;
       ID.AddPointer(&X);
       ID.AddPointer(Reg);
     }

clang/lib/StaticAnalyzer/Checkers/VirtualCallChecker.cpp

public:
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
 
 private:
   void registerCtorDtorCallInState(bool IsBeginFunction,
                                    CheckerContext &C) const;
   void reportBug(StringRef Msg, bool PureError, const MemRegion *Reg,
                  CheckerContext &C) const;
 
-  class VirtualBugVisitor : public BugReporterVisitorImpl<VirtualBugVisitor> {
+  class VirtualBugVisitor : public BugReporterVisitor {
   private:
     const MemRegion *ObjectRegion;
     bool Found;
 
   public:
     VirtualBugVisitor(const MemRegion *R) : ObjectRegion(R), Found(false) {}
 
     void Profile(llvm::FoldingSetNodeID &ID) const override {

clang/lib/StaticAnalyzer/Core/BugReporter.cpp

   ProgramPoint P = N->getLocation();
   const SourceManager& SM = PDB.getSourceManager();
 
   // Have we encountered an entrance to a call?  It may be
   // the case that we have not encountered a matching
   // call exit before this point.  This means that the path
   // terminated within the call itself.
   if (auto CE = P.getAs<CallEnter>()) {
-
     if (AddPathEdges) {
       // Add an edge to the start of the function.
       const StackFrameContext *CalleeLC = CE->getCalleeContext();
       const Decl *D = CalleeLC->getDecl();
       // Add the edge only when the callee has body. We jump to the beginning
       // of the *declaration*, however we expect it to be followed by the
       // body. This isn't the case for autosynthesized property accessors in
       // Objective-C. No need for a similar extra check for CallExit points

 /// There are two path diagnostics generation modes: with adding edges (used
 /// for plists) and without  (used for HTML and text).
 /// When edges are added (\p ActiveScheme is Extensive),
 /// the path is modified to insert artificially generated
 /// edges.
 /// Otherwise, more detailed diagnostics is emitted for block edges, explaining
 /// the transitions in words.
 static bool generatePathDiagnostics(
+    BugReport *R,
     PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N,
     LocationContextMap &LCM,
-    ArrayRef<std::unique_ptr<BugReporterVisitor>> visitors,
     PathDiagnosticConsumer::PathGenerationScheme ActiveScheme) {
   BugReport *report = PDB.getBugReport();
   StackDiagVector CallStack;
   InterestingExprs IE;
   bool AddPathEdges = (ActiveScheme == PathDiagnosticConsumer::Extensive);
   bool GenerateDiagnostics = (ActiveScheme != PathDiagnosticConsumer::None);
 
-  PathDiagnosticLocation PrevLoc = GenerateDiagnostics ?
-    PD.getLocation() : PathDiagnosticLocation();
+  PathDiagnosticLocation PrevLoc = PD.getLocation();
+  BugReport::VisitorList visitors;
 
   const ExplodedNode *NextNode = N->getFirstPred();
   while (NextNode) {
+
+    // Visitors may add new visitors to BugReport `R`.
+    // At each iteration, we move all visitors from `R` to `visitors`.
+    for (BugReport::visitor_iterator I = R->visitor_begin(),
+         E = R->visitor_end(); I != E; ++I) {
+      visitors.push_back(std::move(*I));
+    }
+    R->clearVisitors();
+
     N = NextNode;
     NextNode = N->getFirstPred();
 
     if (GenerateDiagnostics)
       generatePathDiagnosticsForNode(
           N, PD, PrevLoc, PDB, LCM, CallStack, IE, AddPathEdges);
 
     if (!NextNode)

                  lexicalContains(PM, s2Start, s2End) &&
                  !lexicalContains(PM, s1End, s1Start)) {
           removeEdge = true;
         }
         // Trim edges from a subexpression back to the top level if the
         // subexpression is on a different line.
         //
         // A.1 -> A -> B
         // becomes
         // A.1 -> B
         //
         // These edges just look ugly and don't usually add anything.
         else if (s1Start && s2End &&
                  lexicalContains(PM, s1Start, s1End)) {
           SourceRange EdgeRange(PieceI->getEndLocation().asLocation(),
                                 PieceI->getStartLocation().asLocation());
           if (!getLengthOnSingleLine(SM, EdgeRange).hasValue())
             removeEdge = true;
         }
       }
 
       if (removeEdge) {
         PieceI->setEndLocation(PieceNextI->getEndLocation());

 void BugReport::NodeResolver::anchor() {}
 
 void BugReport::addVisitor(std::unique_ptr<BugReporterVisitor> visitor) {
   if (!visitor)
     return;
 
   llvm::FoldingSetNodeID ID;
   visitor->Profile(ID);
-  void *InsertPos;
 
-  if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos))
+  unsigned HashValue = ID.ComputeHash();
+  // TODO: hashing is not perfect, store the entire ID instead.
+  auto P = CallbacksHashes.insert(HashValue);
+  if (!P.second)
     return;
 
-  CallbacksSet.InsertNode(visitor.get(), InsertPos);
   Callbacks.push_back(std::move(visitor));
-  ++ConfigurationChangeToken;
+}
+
+void BugReport::clearVisitors() {
+  Callbacks.clear();
 }
 
 BugReport::~BugReport() {
   while (!interestingSymbols.empty()) {
     popInterestingSymbolsAndRegions();
   }
 }
 

     hash.AddInteger(range.getEnd().getRawEncoding());
   }
 }
 
 void BugReport::markInteresting(SymbolRef sym) {
   if (!sym)
     return;
 
-  // If the symbol wasn't already in our set, note a configuration change.
-  if (getInterestingSymbols().insert(sym).second)
-    ++ConfigurationChangeToken;
+  getInterestingSymbols().insert(sym);
 
   if (const auto *meta = dyn_cast<SymbolMetadata>(sym))
     getInterestingRegions().insert(meta->getRegion());
 }
 
 void BugReport::markInteresting(const MemRegion *R) {
   if (!R)
     return;
 
-  // If the base region wasn't already in our set, note a configuration change.
   R = R->getBaseRegion();
-  if (getInterestingRegions().insert(R).second)
-    ++ConfigurationChangeToken;
+  getInterestingRegions().insert(R);
 
   if (const auto *SR = dyn_cast<SymbolicRegion>(R))
     getInterestingSymbols().insert(SR->getSymbol());
 }
 
 void BugReport::markInteresting(SVal V) {
   markInteresting(V.getAsRegion());
   markInteresting(V.getAsSymbol());

     const ExplodedNode *N = ErrorGraph.ErrorNode;
 
     // Register additional node visitors.
     R->addVisitor(llvm::make_unique<NilReceiverBRVisitor>());
     R->addVisitor(llvm::make_unique<ConditionBRVisitor>());
     R->addVisitor(llvm::make_unique<LikelyFalsePositiveSuppressionBRVisitor>());
     R->addVisitor(llvm::make_unique<CXXSelfAssignmentBRVisitor>());
 
-    BugReport::VisitorList visitors;
-    unsigned origReportConfigToken, finalReportConfigToken;
-    LocationContextMap LCM;
-
-    // While generating diagnostics, it's possible the visitors will decide
-    // new symbols and regions are interesting, or add other visitors based on
-    // the information they find. If they do, we need to regenerate the path
-    // based on our new report configuration.
-    int jj=0;
-    do { // TODO: dump statistics on the MAX number of iterations of this loop.
-      jj++;
-      assert(jj<10);
-      // Get a clean copy of all the visitors.
-      for (BugReport::visitor_iterator I = R->visitor_begin(),
-                                       E = R->visitor_end(); I != E; ++I)
-        visitors.push_back((*I)->clone());
-
-      // Clear out the active path from any previous work.
-      PD.resetPath();
-      origReportConfigToken = R->getConfigurationChangeToken();
-
-      // Generate the very last diagnostic piece - the piece is visible before
-      // the trace is expanded.
+    // Only the initially added visitors can set the last diagnostic piece.
+    if (ActiveScheme != PathDiagnosticConsumer::None) {
       std::unique_ptr<PathDiagnosticPiece> LastPiece;
-      for (BugReport::visitor_iterator I = visitors.begin(), E = visitors.end();
-          I != E; ++I) {
+      for (BugReport::visitor_iterator I = R->visitor_begin(),
+                                       E = R->visitor_end();
+           I != E; ++I) {
         if (std::unique_ptr<PathDiagnosticPiece> Piece =
                 (*I)->getEndPath(PDB, N, *R)) {
           assert(!LastPiece &&
                  "There can only be one final piece in a diagnostic.");
           LastPiece = std::move(Piece);
         }
       }
 
-      if (ActiveScheme != PathDiagnosticConsumer::None) {
-        if (!LastPiece)
-          LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R);
-        assert(LastPiece);
-        PD.setEndOfPath(std::move(LastPiece));
-      }
-
-      // Make sure we get a clean location context map so we don't
-      // hold onto old mappings.
-      LCM.clear();
-
-      generatePathDiagnostics(PD, PDB, N, LCM, visitors, ActiveScheme);
-
-      // Clean up the visitors we used.
-      visitors.clear();
+      if (!LastPiece)
+        LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R);
+      assert(LastPiece);
+      PD.setEndOfPath(std::move(LastPiece));
+    }
 
-      // Did anything change while generating this path?
-      finalReportConfigToken = R->getConfigurationChangeToken();
-    } while (finalReportConfigToken != origReportConfigToken);
+    LocationContextMap LCM;
+    generatePathDiagnostics(R, PD, PDB, N, LCM, ActiveScheme);
 
     if (!R->isValid())
       continue;
 
     // Finally, prune the diagnostic path of uninteresting stuff.
     if (!PD.path.empty()) {
       if (R->shouldPrunePath() && getAnalyzerOptions().shouldPrunePaths()) {
         bool stillHasNotes = removeUnneededCalls(PD.getMutablePieces(), R, LCM);

   }
 }
 
 LLVM_DUMP_METHOD void PathDiagnosticCallPiece::dump() const {
   llvm::errs() << "CALL\n--------------\n";
 
   if (const Stmt *SLoc = getLocStmt(getLocation()))
     SLoc->dump();
-  else if (const auto *ND = dyn_cast<NamedDecl>(getCallee()))
+  else if (const auto *ND = dyn_cast_or_null<NamedDecl>(getCallee()))
     llvm::errs() << *ND << "\n";
   else
     getLocation().dump();
 }
 
 LLVM_DUMP_METHOD void PathDiagnosticEventPiece::dump() const {
   llvm::errs() << "EVENT\n--------------\n";
   llvm::errs() << getString() << "\n";

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

 }
 
 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
 /// pointer dereference outside.
-class NoStoreFuncVisitor final
-    : public BugReporterVisitorImpl<NoStoreFuncVisitor> {
+class NoStoreFuncVisitor final : public BugReporterVisitor {
   const SubRegion *RegionOfInterest;
   static constexpr const char *DiagnosticsMsg =
       "Returning without writing to '";
 
   /// Frames writing into \c RegionOfInterest.
   /// This visitor generates a note only if a function does not write into
   /// a region of interest. This information is not immediately available
   /// by looking at the node associated with the exit from the function
for (auto I = Subregions.rbegin(), E = Subregions.rend(); I != E; ++I) {
       } else {
         llvm_unreachable("Previous check has missed an unexpected region");
       }
     }
     return true;
   }
 };
 
-class MacroNullReturnSuppressionVisitor final
-    : public BugReporterVisitorImpl<MacroNullReturnSuppressionVisitor> {
+class MacroNullReturnSuppressionVisitor final : public BugReporterVisitor {
   const SubRegion *RegionOfInterest;
 
 public:
   MacroNullReturnSuppressionVisitor(const SubRegion *R) : RegionOfInterest(R) {}
 
   static void *getTag() {
     static int Tag = 0;
     return static_cast<void *>(&Tag);

 
 /// 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 BugReporterVisitorImpl<ReturnVisitor> {
+class ReturnVisitor : public BugReporterVisitor {
   const StackFrameContext *StackFrame;
   enum {
     Initial,
     MaybeUnsuppress,
     Satisfied
   } Mode = Initial;
 
   bool EnableNullFPSuppression;