Index: clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h =================================================================== --- clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h +++ clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h @@ -87,6 +87,7 @@ using ranges_iterator = const SourceRange *; using VisitorList = SmallVector, 8>; using visitor_iterator = VisitorList::iterator; + using visitor_range = llvm::iterator_range; using ExtraTextList = SmallVector; using NoteList = SmallVector, 4>; @@ -339,6 +340,7 @@ /// 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. Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h =================================================================== --- clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -221,12 +221,20 @@ // Iterators over successor and predecessor vertices. using succ_iterator = ExplodedNode * const *; + using succ_range = llvm::iterator_range; + using const_succ_iterator = const ExplodedNode * const *; + using const_succ_range = llvm::iterator_range; + using pred_iterator = ExplodedNode * const *; + using pred_range = llvm::iterator_range; + using const_pred_iterator = const ExplodedNode * const *; + using const_pred_range = llvm::iterator_range; 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(this)->pred_begin(); @@ -234,9 +242,11 @@ const_pred_iterator pred_end() const { return const_cast(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(this)->succ_begin(); @@ -244,6 +254,7 @@ const_succ_iterator succ_end() const { return const_cast(this)->succ_end(); } + const_succ_range succs() const { return {Succs.begin(), Succs.end()}; } int64_t getID(ExplodedGraph *G) const; Index: clang/lib/StaticAnalyzer/Core/BugReporter.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/BugReporter.cpp +++ clang/lib/StaticAnalyzer/Core/BugReporter.cpp @@ -2241,29 +2241,36 @@ 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 Graph; + InterExplodedGraphMap MapToOriginNodes; + std::unique_ptr 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 TrimmedGraph; + + /// Map from the trimmed graph to the original. InterExplodedGraphMap InverseMap; using PriorityMapTy = llvm::DenseMap; + /// Assign each node with its distance from the root. PriorityMapTy PriorityMap; - using NodeIndexPair = std::pair; - - SmallVector 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; + SmallVector ReportNodes; - std::unique_ptr G; + BugPathInfo CurrentBugPath; /// A helper class for sorting ExplodedNodes by priority. template @@ -2287,37 +2294,48 @@ : 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 Nodes); + BugPathGetter(const ExplodedGraph *OriginalGraph, + ArrayRef &bugReports); - bool popNextReportGraph(ReportGraph &GraphWrapper); + BugPathInfo *getNextBugPath(); }; } // namespace -TrimmedGraph::TrimmedGraph(const ExplodedGraph *OriginalGraph, - ArrayRef Nodes) { +BugPathGetter::BugPathGetter(const ExplodedGraph *OriginalGraph, + ArrayRef &bugReports) { + SmallVector 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 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); + RemainingNodes.insert(NewNode); } assert(!RemainingNodes.empty() && "No error node found in the trimmed graph"); @@ -2325,8 +2343,8 @@ // Perform a forward BFS to find all the shortest paths. std::queue 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()) { @@ -2335,8 +2353,7 @@ 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) { @@ -2348,29 +2365,27 @@ 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(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(); - GraphWrapper.BackMap.clear(); + CurrentBugPath.MapToOriginNodes.clear(); // Now walk from the error node up the BFS path, always taking the // predeccessor with the lowest number. @@ -2378,19 +2393,19 @@ 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; @@ -2403,12 +2418,12 @@ // 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(PriorityMap)); + PriorityCompare(PriorityMap)); } - GraphWrapper.Graph = std::move(GNew); + CurrentBugPath.Path = std::move(GNew); - return true; + return &CurrentBugPath; } /// CompactMacroExpandedPieces - This function postprocesses a PathDiagnostic @@ -2519,12 +2534,14 @@ 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 &Visitor : R->visitors()) + visitors.push_back(std::move(Visitor)); + R->clearVisitors(); const ExplodedNode *Pred = NextNode->getFirstPred(); @@ -2536,6 +2553,8 @@ 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); } @@ -2558,24 +2577,43 @@ 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> findValidReport( - TrimmedGraph &TrimG, - ReportGraph &ErrorGraph, - ArrayRef &bugReports, - AnalyzerOptions &Opts, - GRBugReporter &Reporter) { +class ReportInfo { + BugPathInfo BugPath; + std::unique_ptr VisitorDiagnostics; + +public: + ReportInfo(BugPathInfo &&BugPath, std::unique_ptr V) + : BugPath(std::move(BugPath)), VisitorDiagnostics(std::move(V)) {} + + ReportInfo() = default; + + bool isValid() { return static_cast(VisitorDiagnostics); } - while (TrimG.popNextReportGraph(ErrorGraph)) { + 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 &bugReports, + GRBugReporter &Reporter) { + BugPathGetter BugGraph(&Reporter.getGraph(), bugReports); + + 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 @@ -2586,14 +2624,14 @@ R->addVisitor(llvm::make_unique()); R->addVisitor(llvm::make_unique()); - BugReporterContext BRC(Reporter, ErrorGraph.BackMap); + BugReporterContext BRC(Reporter, BugPath->MapToOriginNodes); // Run all visitors on a given graph, once. std::unique_ptr 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(); @@ -2601,16 +2639,16 @@ // 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()); + return {}; } std::unique_ptr @@ -2620,35 +2658,16 @@ assert(!bugReports.empty()); auto Out = llvm::make_unique(); - bool HasValid = false; - SmallVector 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 PD = generatePathDiagnosticForConsumer( - PC->getGenerationScheme(), PDB, ErrorNode, *ReportInfo.second); + PC->getGenerationScheme(), PDB, Info.getErrorNode(), + Info.getVisitorsDiagnostics()); (*Out)[PC] = std::move(PD); } }