[analyzer][NFC] Refactoring BugReporter.cpp P2.: Clean up the construction of bug paths and finding a valid report

[Szelethus]

Summary

This patch refactors the utility functions and classes around the construction of a bug path.

At a very high level, this consists of 3 steps:

1. For all BugReports in the same BugReportEquivClass, collect all their error nodes in a set. With that set, create a new, trimmed ExplodedGraph whose leafs are all error nodes.
2. Until a valid report is found, construct a bug path, which is yet another ExplodedGraph, that is linear from a given error node to the root of the graph.
3. Run all visitors on the constructed bug path. If in this process the report got invalidated, start over from step 2.

Now, to the changes within this patch:

• Do not allow the invalidation of BugReports up to the point where the trimmed graph is constructed. Checkers shouldn't add bug reports that are known to be invalid, and should use visitors and argue about the entirety of the bug path if needed.
• Do not calculate indices. I may be biased, but I personally find code like this the hardest to follow. I'd like to point you to one of the comments in the original code:

SmallVector<const ExplodedNode *, 32> errorNodes;
for (const auto I : bugReports) {
  if (I->isValid()) {
    HasValid = true;
    errorNodes.push_back(I->getErrorNode());
  } else {
    // Keep the errorNodes list in sync with the bugReports list.
    errorNodes.push_back(nullptr);
  }
}

Not on my watch. Instead, use a far easier to follow trick: store a pointer to the BugReport in question, not an index to it.

• Add range iterators to ExplodedGraph's successors and predecessors, and a visitor range to BugReporter.
• Rename TrimmedGraph to BugPathGetter. Because that is what it has always been: no sane graph type should store an iterator-like state, or have an interface not exposing a single graph-like functionalities.
• Rename ReportGraph to BugPathInfo, because it is only a linear path with some other context.
• Instead of having both and out and in parameter (which I think isn't ever excusable unless we use the out-param for caching), return a record object with descriptive getter methods.
• Where descriptive names weren't sufficient, compliment the code with comments.

[NoQ]

If only somebody could explain to me why do even need trimming in the first place :/

I was only keeping it around for easier exploded graph dumps reading, but these days we can trivially replace it with a flag to exploded-graph-rewriter (i.e., combine D65345 with D64110).

[xazax.hun]

Looks good, some nits inline. I agree with Artem, we should consider omitting the trimming and document how to get something similar if desired for debugging.

Just a random idea: maybe the original purpose of the trimming was to be able to reclaim parts of the exploded graph as soon as possible?

clang/lib/StaticAnalyzer/Core/BugReporter.cpp

2269 ↗

(On Diff #212118)

This comment was really hard for me to understand, could you rephrase it?

2305 ↗

(On Diff #212118)

Formatting might be off here?

[Szelethus]

clang-format, rephrase the comment.

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

public:
 
     virtual const ExplodedNode*
             getOriginalNode(const ExplodedNode *N) = 0;
   };
 
   using ranges_iterator = const SourceRange *;
   using VisitorList = SmallVector<std::unique_ptr<BugReporterVisitor>, 8>;
   using visitor_iterator = VisitorList::iterator;
+  using visitor_range = llvm::iterator_range<visitor_iterator>;
   using ExtraTextList = SmallVector<StringRef, 2>;
   using NoteList = SmallVector<std::shared_ptr<PathDiagnosticNotePiece>, 4>;
 
 protected:
   friend class BugReportEquivClass;
   friend class BugReporter;
 
   const BugType& BT;
public:
   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(); }
+  visitor_range visitors() { return {visitor_begin(), visitor_end()}; }
 
   /// Notes that the condition of the CFGBlock associated with \p Cond is
   /// being tracked.
   /// \returns false if the condition is already being tracked.
   bool addTrackedCondition(const ExplodedNode *Cond) {
     return TrackedConditions.insert(Cond).second;
   }
 

cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h

public:
   }
 
   const ExplodedNode *getFirstSucc() const {
     return const_cast<ExplodedNode*>(this)->getFirstSucc();
   }
 
   // Iterators over successor and predecessor vertices.
   using succ_iterator = ExplodedNode * const *;
+  using succ_range = llvm::iterator_range<succ_iterator>;
+
   using const_succ_iterator = const ExplodedNode * const *;
+  using const_succ_range = llvm::iterator_range<const_succ_iterator>;
+
   using pred_iterator = ExplodedNode * const *;
+  using pred_range = llvm::iterator_range<pred_iterator>;
+
   using const_pred_iterator = const ExplodedNode * const *;
+  using const_pred_range = llvm::iterator_range<const_pred_iterator>;
 
   pred_iterator pred_begin() { return Preds.begin(); }
   pred_iterator pred_end() { return Preds.end(); }
+  pred_range preds() { return {Preds.begin(), Preds.end()}; }
 
   const_pred_iterator pred_begin() const {
     return const_cast<ExplodedNode*>(this)->pred_begin();
   }
   const_pred_iterator pred_end() const {
     return const_cast<ExplodedNode*>(this)->pred_end();
   }
+  const_pred_range preds() const { return {Preds.begin(), Preds.end()}; }
 
   succ_iterator succ_begin() { return Succs.begin(); }
   succ_iterator succ_end() { return Succs.end(); }
+  succ_range succs() { return {Succs.begin(), Succs.end()}; }
 
   const_succ_iterator succ_begin() const {
     return const_cast<ExplodedNode*>(this)->succ_begin();
   }
   const_succ_iterator succ_end() const {
     return const_cast<ExplodedNode*>(this)->succ_end();
   }
+  const_succ_range succs() const { return {Succs.begin(), Succs.end()}; }
 
   int64_t getID(ExplodedGraph *G) const;
 
   /// The node is trivial if it has only one successor, only one predecessor,
   /// it's predecessor has only one successor,
   /// and its program state is the same as the program state of the previous
   /// node.
   /// Trivial nodes may be skipped while printing exploded graph.

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

 }
 
 //===----------------------------------------------------------------------===//
 // PathDiagnostics generation.
 //===----------------------------------------------------------------------===//
 
 namespace {
 
-/// A wrapper around a report graph, which contains only a single path, and its
-/// node maps.
-class ReportGraph {
+/// A wrapper around an ExplodedGraph that contains a single path from the root
+/// to the error node, and a map that maps the nodes in this path to the ones in
+/// the original ExplodedGraph.
+class BugPathInfo {
 public:
-  InterExplodedGraphMap BackMap;
-  std::unique_ptr<ExplodedGraph> Graph;
+  InterExplodedGraphMap MapToOriginNodes;
+  std::unique_ptr<ExplodedGraph> Path;
+  BugReport *Report;
   const ExplodedNode *ErrorNode;
-  size_t Index;
 };
 
-/// A wrapper around a trimmed graph and its node maps.
-class TrimmedGraph {
+/// A wrapper around an ExplodedGraph whose leafs are all error nodes. Can
+/// conveniently retrieve bug paths from a single error node to the root.
+class BugPathGetter {
+  std::unique_ptr<ExplodedGraph> TrimmedGraph;
+
+  /// Map from the trimmed graph to the original.
   InterExplodedGraphMap InverseMap;
 
   using PriorityMapTy = llvm::DenseMap<const ExplodedNode *, unsigned>;
 
+  /// Assign each node with its distance from the root.
   PriorityMapTy PriorityMap;
 
-  using NodeIndexPair = std::pair<const ExplodedNode *, size_t>;
-
-  SmallVector<NodeIndexPair, 32> ReportNodes;
+  /// Since the getErrorNode() or BugReport refers to the original ExplodedGraph,
+  /// we need to pair it to the error node of the constructed trimmed graph.
+  using ReportNewNodePair = std::pair<BugReport *, const ExplodedNode *>;
+  SmallVector<ReportNewNodePair, 32> ReportNodes;
 
-  std::unique_ptr<ExplodedGraph> G;
+  BugPathInfo CurrentBugPath;
 
   /// A helper class for sorting ExplodedNodes by priority.
   template <bool Descending>
   class PriorityCompare {
     const PriorityMapTy &PriorityMap;
 
   public:
     PriorityCompare(const PriorityMapTy &M) : PriorityMap(M) {}
 
     bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const {
       PriorityMapTy::const_iterator LI = PriorityMap.find(LHS);
       PriorityMapTy::const_iterator RI = PriorityMap.find(RHS);
       PriorityMapTy::const_iterator E = PriorityMap.end();
 
       if (LI == E)
         return Descending;
       if (RI == E)
         return !Descending;
 
       return Descending ? LI->second > RI->second
                         : LI->second < RI->second;
     }
 
-    bool operator()(const NodeIndexPair &LHS, const NodeIndexPair &RHS) const {
-      return (*this)(LHS.first, RHS.first);
+    bool operator()(const ReportNewNodePair &LHS,
+                    const ReportNewNodePair &RHS) const {
+      return (*this)(LHS.second, RHS.second);
     }
   };
 
 public:
-  TrimmedGraph(const ExplodedGraph *OriginalGraph,
-               ArrayRef<const ExplodedNode *> Nodes);
+  BugPathGetter(const ExplodedGraph *OriginalGraph,
+                ArrayRef<BugReport *> &bugReports);
 
-  bool popNextReportGraph(ReportGraph &GraphWrapper);
+  BugPathInfo *getNextBugPath();
 };
 
 } // namespace
 
-TrimmedGraph::TrimmedGraph(const ExplodedGraph *OriginalGraph,
-                           ArrayRef<const ExplodedNode *> Nodes) {
+BugPathGetter::BugPathGetter(const ExplodedGraph *OriginalGraph,
+                             ArrayRef<BugReport *> &bugReports) {
+  SmallVector<const ExplodedNode *, 32> Nodes;
+  for (const auto I : bugReports) {
+    assert(I->isValid() &&
+           "We only allow BugReporterVisitors and BugReporter itself to "
+           "invalidate reports!");
+    Nodes.emplace_back(I->getErrorNode());
+  }
+
   // The trimmed graph is created in the body of the constructor to ensure
   // that the DenseMaps have been initialized already.
   InterExplodedGraphMap ForwardMap;
-  G = OriginalGraph->trim(Nodes, &ForwardMap, &InverseMap);
+  TrimmedGraph = OriginalGraph->trim(Nodes, &ForwardMap, &InverseMap);
 
   // Find the (first) error node in the trimmed graph.  We just need to consult
   // the node map which maps from nodes in the original graph to nodes
   // in the new graph.
   llvm::SmallPtrSet<const ExplodedNode *, 32> RemainingNodes;
 
-  for (unsigned i = 0, count = Nodes.size(); i < count; ++i) {
-    if (const ExplodedNode *NewNode = ForwardMap.lookup(Nodes[i])) {
-      ReportNodes.push_back(std::make_pair(NewNode, i));
-      RemainingNodes.insert(NewNode);
-    }
-  }
+  for (BugReport *Report : bugReports) {
+    const ExplodedNode *NewNode = ForwardMap.lookup(Report->getErrorNode());
+    assert(NewNode &&
+           "Failed to construct a trimmed graph that contains this error "
+           "node!");
+    ReportNodes.emplace_back(Report, NewNode);
 
   assert(!RemainingNodes.empty() && "No error node found in the trimmed graph");
 
   // Perform a forward BFS to find all the shortest paths.
   std::queue<const ExplodedNode *> WS;
 
-  assert(G->num_roots() == 1);
-  WS.push(*G->roots_begin());
+  assert(TrimmedGraph->num_roots() == 1);
+  WS.push(*TrimmedGraph->roots_begin());
   unsigned Priority = 0;
 
   while (!WS.empty()) {
     const ExplodedNode *Node = WS.front();
     WS.pop();
 
     PriorityMapTy::iterator PriorityEntry;
     bool IsNew;
-    std::tie(PriorityEntry, IsNew) =
-      PriorityMap.insert(std::make_pair(Node, Priority));
+    std::tie(PriorityEntry, IsNew) = PriorityMap.insert({Node, Priority});
     ++Priority;
 
     if (!IsNew) {
       assert(PriorityEntry->second <= Priority);
       continue;
     }
 
     if (RemainingNodes.erase(Node))
       if (RemainingNodes.empty())
         break;
 
-    for (ExplodedNode::const_pred_iterator I = Node->succ_begin(),
-                                           E = Node->succ_end();
-         I != E; ++I)
-      WS.push(*I);
+    for (const ExplodedNode *Succ : Node->succs())
+      WS.push(Succ);
   }
 
   // Sort the error paths from longest to shortest.
   llvm::sort(ReportNodes, PriorityCompare<true>(PriorityMap));
 }
 
-bool TrimmedGraph::popNextReportGraph(ReportGraph &GraphWrapper) {
+BugPathInfo *BugPathGetter::getNextBugPath() {
   if (ReportNodes.empty())
-    return false;
+    return nullptr;
 
   const ExplodedNode *OrigN;
-  std::tie(OrigN, GraphWrapper.Index) = ReportNodes.pop_back_val();
+  std::tie(CurrentBugPath.Report, OrigN) = ReportNodes.pop_back_val();
   assert(PriorityMap.find(OrigN) != PriorityMap.end() &&
          "error node not accessible from root");
 
-  // Create a new graph with a single path.  This is the graph
-  // that will be returned to the caller.
+  // Create a new graph with a single path. This is the graph that will be
+  // returned to the caller.
   auto GNew = llvm::make_unique<ExplodedGraph>();
-  GraphWrapper.BackMap.clear();
+  CurrentBugPath.MapToOriginNodes.clear();
 
   // Now walk from the error node up the BFS path, always taking the
   // predeccessor with the lowest number.
   ExplodedNode *Succ = nullptr;
   while (true) {
     // Create the equivalent node in the new graph with the same state
     // and location.
-    ExplodedNode *NewN = GNew->createUncachedNode(OrigN->getLocation(), OrigN->getState(),
-                                       OrigN->isSink());
+    ExplodedNode *NewN = GNew->createUncachedNode(
+        OrigN->getLocation(), OrigN->getState(), OrigN->isSink());
 
     // Store the mapping to the original node.
     InterExplodedGraphMap::const_iterator IMitr = InverseMap.find(OrigN);
     assert(IMitr != InverseMap.end() && "No mapping to original node.");
-    GraphWrapper.BackMap[NewN] = IMitr->second;
+    CurrentBugPath.MapToOriginNodes[NewN] = IMitr->second;
 
     // Link up the new node with the previous node.
     if (Succ)
       Succ->addPredecessor(NewN, *GNew);
     else
-      GraphWrapper.ErrorNode = NewN;
+      CurrentBugPath.ErrorNode = NewN;
 
     Succ = NewN;
 
     // Are we at the final node?
     if (OrigN->pred_empty()) {
       GNew->addRoot(NewN);
       break;
     }
 
     // Find the next predeccessor node.  We choose the node that is marked
     // with the lowest BFS number.
     OrigN = *std::min_element(OrigN->pred_begin(), OrigN->pred_end(),
                               PriorityCompare<false>(PriorityMap));
   }
 
-  GraphWrapper.Graph = std::move(GNew);
+  CurrentBugPath.Path = std::move(GNew);
 
-  return true;
+  return &CurrentBugPath;
 }
 
 /// CompactMacroExpandedPieces - This function postprocesses a PathDiagnostic
 /// object and collapses PathDiagosticPieces that are expanded by macros.
 static void CompactMacroExpandedPieces(PathPieces &path,
                                        const SourceManager& SM) {
   using MacroStackTy =
       std::vector<
generateVisitorsDiagnostics(BugReport *R, const ExplodedNode *ErrorNode,
   auto Notes = llvm::make_unique<VisitorsDiagnosticsTy>();
   BugReport::VisitorList visitors;
 
   // Run visitors on all nodes starting from the node *before* the last one.
   // The last node is reserved for notes generated with {@code getEndPath}.
   const ExplodedNode *NextNode = ErrorNode->getFirstPred();
   while (NextNode) {
 
-    // At each iteration, move all visitors from report to visitor list.
-    for (BugReport::visitor_iterator I = R->visitor_begin(),
-                                     E = R->visitor_end();
-         I != E; ++I) {
-      visitors.push_back(std::move(*I));
-    }
+    // At each iteration, move all visitors from report to visitor list. This is
+    // important, because the Profile() functions of the visitors make sure that
+    // a visitor isn't added multiple times for the same node, but it's fine
+    // to add the a visitor with Profile() for different nodes (e.g. tracking
+    // a region at different points of the symbolic execution).
+    for (std::unique_ptr<BugReporterVisitor> &Visitor : R->visitors())
+      visitors.push_back(std::move(Visitor));
+
     R->clearVisitors();
 
     const ExplodedNode *Pred = NextNode->getFirstPred();
     if (!Pred) {
       std::shared_ptr<PathDiagnosticPiece> LastPiece;
       for (auto &V : visitors) {
         V->finalizeVisitor(BRC, ErrorNode, *R);
 
         if (auto Piece = V->getEndPath(BRC, ErrorNode, *R)) {
           assert(!LastPiece &&
                  "There can only be one final piece in a diagnostic.");
+          assert(Piece->getKind() == PathDiagnosticPiece::Kind::Event &&
+                 "The final piece must contain a message!");
           LastPiece = std::move(Piece);
           (*Notes)[ErrorNode].push_back(LastPiece);
         }
       }
       break;
     }
 
     for (auto &V : visitors) {
       auto P = V->VisitNode(NextNode, BRC, *R);
       if (P)
         (*Notes)[NextNode].push_back(std::move(P));
     }
 
     if (!R->isValid())
       break;
 
     NextNode = Pred;
   }
 
   return Notes;
 }
 
-/// Find a non-invalidated report for a given equivalence class,
-/// and return together with a cache of visitors notes.
-/// If none found, return a nullptr paired with an empty cache.
-static
-std::pair<BugReport*, std::unique_ptr<VisitorsDiagnosticsTy>> findValidReport(
-  TrimmedGraph &TrimG,
-  ReportGraph &ErrorGraph,
-  ArrayRef<BugReport *> &bugReports,
-  AnalyzerOptions &Opts,
+class ReportInfo {
+  BugPathInfo BugPath;
+  std::unique_ptr<VisitorsDiagnosticsTy> VisitorDiagnostics;
+
+public:
+  ReportInfo(BugPathInfo &&BugPath, std::unique_ptr<VisitorsDiagnosticsTy> V)
+      : BugPath(std::move(BugPath)), VisitorDiagnostics(std::move(V)) {}
+
+  ReportInfo() = default;
+
+  bool isValid() { return static_cast<bool>(VisitorDiagnostics); }
+
+  BugReport *getBugReport() { return BugPath.Report; }
+  const ExplodedNode *getErrorNode() { return BugPath.ErrorNode; }
+
+  InterExplodedGraphMap &getMapToOriginNodes() {
+    return BugPath.MapToOriginNodes;
+  }
+
+  VisitorsDiagnosticsTy &getVisitorsDiagnostics() {
+    return *VisitorDiagnostics;
+  }
+};
+
+/// Find a non-invalidated report for a given equivalence class,  and returns
+/// the bug path associated with it together with a cache of visitors notes.
+/// If none found, returns an isInvalid() object.
+static ReportInfo findValidReport(ArrayRef<BugReport *> &bugReports,
                                   GRBugReporter &Reporter) {
+  BugPathGetter BugGraph(&Reporter.getGraph(), bugReports);
 
-  while (TrimG.popNextReportGraph(ErrorGraph)) {
+  while (BugPathInfo *BugPath = BugGraph.getNextBugPath()) {
     // Find the BugReport with the original location.
-    assert(ErrorGraph.Index < bugReports.size());
-    BugReport *R = bugReports[ErrorGraph.Index];
+    BugReport *R = BugPath->Report;
     assert(R && "No original report found for sliced graph.");
     assert(R->isValid() && "Report selected by trimmed graph marked invalid.");
-    const ExplodedNode *ErrorNode = ErrorGraph.ErrorNode;
+    const ExplodedNode *ErrorNode = BugPath->ErrorNode;
 
     // Register refutation visitors first, if they mark the bug invalid no
     // further analysis is required
     R->addVisitor(llvm::make_unique<LikelyFalsePositiveSuppressionBRVisitor>());
 
     // Register additional node visitors.
     R->addVisitor(llvm::make_unique<NilReceiverBRVisitor>());
     R->addVisitor(llvm::make_unique<ConditionBRVisitor>());
     R->addVisitor(llvm::make_unique<TagVisitor>());
 
-    BugReporterContext BRC(Reporter, ErrorGraph.BackMap);
+    BugReporterContext BRC(Reporter, BugPath->MapToOriginNodes);
 
     // Run all visitors on a given graph, once.
     std::unique_ptr<VisitorsDiagnosticsTy> visitorNotes =
         generateVisitorsDiagnostics(R, ErrorNode, BRC);
 
     if (R->isValid()) {
-      if (Opts.ShouldCrosscheckWithZ3) {
+      if (Reporter.getAnalyzerOptions().ShouldCrosscheckWithZ3) {
         // If crosscheck is enabled, remove all visitors, add the refutation
         // visitor and check again
         R->clearVisitors();
         R->addVisitor(llvm::make_unique<FalsePositiveRefutationBRVisitor>());
 
         // We don't overrite the notes inserted by other visitors because the
         // refutation manager does not add any new note to the path
-        generateVisitorsDiagnostics(R, ErrorGraph.ErrorNode, BRC);
+        generateVisitorsDiagnostics(R, BugPath->ErrorNode, BRC);
       }
 
       // Check if the bug is still valid
       if (R->isValid())
-        return std::make_pair(R, std::move(visitorNotes));
+        return {std::move(*BugPath), std::move(visitorNotes)};
     }
   }
 
-  return std::make_pair(nullptr, llvm::make_unique<VisitorsDiagnosticsTy>());
+  return {};
 }
 
 std::unique_ptr<DiagnosticForConsumerMapTy>
 GRBugReporter::generatePathDiagnostics(
     ArrayRef<PathDiagnosticConsumer *> consumers,
     ArrayRef<BugReport *> &bugReports) {
   assert(!bugReports.empty());
 
   auto Out = llvm::make_unique<DiagnosticForConsumerMapTy>();
-  bool HasValid = false;
-  SmallVector<const ExplodedNode *, 32> errorNodes;
-  for (const auto I : bugReports) {
-    if (I->isValid()) {
-      HasValid = true;
-      errorNodes.push_back(I->getErrorNode());
-    } else {
-      // Keep the errorNodes list in sync with the bugReports list.
-      errorNodes.push_back(nullptr);
-    }
-  }
-
-  // If all the reports have been marked invalid by a previous path generation,
-  // we're done.
-  if (!HasValid)
-    return Out;
 
-  TrimmedGraph TrimG(&getGraph(), errorNodes);
-  ReportGraph ErrorGraph;
-  auto ReportInfo = findValidReport(TrimG, ErrorGraph, bugReports,
-                  getAnalyzerOptions(), *this);
-  BugReport *R = ReportInfo.first;
+  ReportInfo Info = findValidReport(bugReports, *this);
 
-  if (R && R->isValid()) {
-    const ExplodedNode *ErrorNode = ErrorGraph.ErrorNode;
+  if (Info.isValid()) {
     for (PathDiagnosticConsumer *PC : consumers) {
-      PathDiagnosticBuilder PDB(*this, R, ErrorGraph.BackMap, PC);
+      PathDiagnosticBuilder PDB(*this, Info.getBugReport(),
+                                Info.getMapToOriginNodes(), PC);
       std::unique_ptr<PathDiagnostic> PD = generatePathDiagnosticForConsumer(
-          PC->getGenerationScheme(), PDB, ErrorNode, *ReportInfo.second);
+          PC->getGenerationScheme(), PDB, Info.getErrorNode(),
+          Info.getVisitorsDiagnostics());
       (*Out)[PC] = std::move(PD);
     }
   }
 
   return Out;
 }
 
 void BugReporter::Register(const BugType *BT) {