[NFC][analyzer] Clarify that ExplodedGraph has only one root (#139903)
Previously the class `ExplodedGraph` had a data member called `Roots`
which could (in theory) store multiple root nodes -- but in practice
exploded graphs always had at most one root node (zero was possible for
empty and partially copied graphs) and introducing a graph with multiple
roots would've caused severe malfuncitons (e.g. in code that used the
pattern `*roots_begin()` to refer to _the_ root node).
I don't see any practical use case for adding multiple root nodes in a
single graph (this seems to be yet another of the "generalize for the
sake of generalization" decisions which were common in the early history
of the analyzer), so this commit replaces the vector `Roots` with
`ExplodedNode *Root` (which may be null when the graph is empty or under
construction).
Note that the complicated logic of `ExplodedGraph::trim` deserves a
through cleanup, but I left that for a follow-up commit.
diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
index 3754e25..e995151 100644
--- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
+++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
@@ -307,11 +307,9 @@
// Type definitions.
using NodeVector = std::vector<ExplodedNode *>;
- /// The roots of the simulation graph. Usually there will be only
- /// one, but clients are free to establish multiple subgraphs within a single
- /// SimulGraph. Moreover, these subgraphs can often merge when paths from
- /// different roots reach the same state at the same program location.
- NodeVector Roots;
+ /// The root of the simulation graph. Can be nullptr if the graph is empty or
+ /// if it was populated by `createUncachedNode()`.
+ ExplodedNode *Root = nullptr;
/// The nodes in the simulation graph which have been
/// specially marked as the endpoint of an abstract simulation path.
@@ -345,31 +343,31 @@
ExplodedGraph();
~ExplodedGraph();
- /// Retrieve the node associated with a (Location,State) pair,
- /// where the 'Location' is a ProgramPoint in the CFG. If no node for
- /// this pair exists, it is created. IsNew is set to true if
- /// the node was freshly created.
+ /// Get the root node of the graph. This may return nullptr if the graph is
+ /// empty or under construction.
+ ExplodedNode *getRoot() const { return Root; }
+
+ /// Retrieve the node associated with a (Location, State) pair, where the
+ /// 'Location' is a ProgramPoint in the CFG. If no node for this pair exists,
+ /// it is created. IsNew is set to true if the node was freshly created.
ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State,
bool IsSink = false,
bool* IsNew = nullptr);
- /// Create a node for a (Location, State) pair,
- /// but don't store it for deduplication later. This
- /// is useful when copying an already completed
- /// ExplodedGraph for further processing.
+ /// Create a node for a (Location, State) pair, but don't store it for
+ /// deduplication later. This is useful when copying some nodes from an
+ /// already completed ExplodedGraph for further processing.
ExplodedNode *createUncachedNode(const ProgramPoint &L,
ProgramStateRef State,
int64_t Id,
bool IsSink = false);
- std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
- return std::make_unique<ExplodedGraph>();
- }
-
- /// addRoot - Add an untyped node to the set of roots.
- ExplodedNode *addRoot(ExplodedNode *V) {
- Roots.push_back(V);
- return V;
+ /// Mark a node as the root of the graph. Calling this is an error if the
+ /// graph already has a root node.
+ void designateAsRoot(ExplodedNode *V) {
+ assert(V && "Cannot designate nullptr as root!");
+ assert(!Root && "The graph already has a root, cannot designate another!");
+ Root = V;
}
/// addEndOfPath - Add an untyped node to the set of EOP nodes.
@@ -378,7 +376,6 @@
return V;
}
- unsigned num_roots() const { return Roots.size(); }
unsigned num_eops() const { return EndNodes.size(); }
bool empty() const { return NumNodes == 0; }
@@ -389,8 +386,6 @@
// Iterators.
using NodeTy = ExplodedNode;
using AllNodesTy = llvm::FoldingSet<ExplodedNode>;
- using roots_iterator = NodeVector::iterator;
- using const_roots_iterator = NodeVector::const_iterator;
using eop_iterator = NodeVector::iterator;
using const_eop_iterator = NodeVector::const_iterator;
using node_iterator = AllNodesTy::iterator;
@@ -400,14 +395,6 @@
llvm::iterator_range<const_node_iterator> nodes() const { return Nodes; }
- roots_iterator roots_begin() { return Roots.begin(); }
-
- roots_iterator roots_end() { return Roots.end(); }
-
- const_roots_iterator roots_begin() const { return Roots.begin(); }
-
- const_roots_iterator roots_end() const { return Roots.end(); }
-
eop_iterator eop_begin() { return EndNodes.begin(); }
eop_iterator eop_end() { return EndNodes.end(); }
@@ -508,9 +495,7 @@
using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator;
using nodes_iterator = llvm::df_iterator<GraphTy>;
- static NodeRef getEntryNode(const GraphTy G) {
- return *G->roots_begin();
- }
+ static NodeRef getEntryNode(const GraphTy G) { return G->getRoot(); }
static bool predecessorOfTrivial(NodeRef N) {
return N->succ_size() == 1 && N->getFirstSucc()->isTrivial();
diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
index 2851941..b8a4dcb 100644
--- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
+++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
@@ -222,8 +222,8 @@
const Stmt *getStmt() const;
const LocationContext *getRootLocationContext() const {
- assert(G.roots_begin() != G.roots_end());
- return (*G.roots_begin())->getLocation().getLocationContext();
+ assert(G.getRoot());
+ return G.getRoot()->getLocation().getLocationContext();
}
ConstCFGElementRef getCFGElementRef() const {
diff --git a/clang/lib/StaticAnalyzer/Checkers/AnalyzerStatsChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/AnalyzerStatsChecker.cpp
index d030e69..0aaa32f 100644
--- a/clang/lib/StaticAnalyzer/Checkers/AnalyzerStatsChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/AnalyzerStatsChecker.cpp
@@ -45,9 +45,7 @@
const SourceManager &SM = B.getSourceManager();
llvm::SmallPtrSet<const CFGBlock*, 32> reachable;
- // Root node should have the location context of the top most function.
- const ExplodedNode *GraphRoot = *G.roots_begin();
- const LocationContext *LC = GraphRoot->getLocation().getLocationContext();
+ const LocationContext *LC = Eng.getRootLocationContext();
const Decl *D = LC->getDecl();
diff --git a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp b/clang/lib/StaticAnalyzer/Core/BugReporter.cpp
index 28b96f2..d5bc3ac 100644
--- a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp
+++ b/clang/lib/StaticAnalyzer/Core/BugReporter.cpp
@@ -2660,8 +2660,7 @@
// Perform a forward BFS to find all the shortest paths.
std::queue<const ExplodedNode *> WS;
- assert(TrimmedGraph->num_roots() == 1);
- WS.push(*TrimmedGraph->roots_begin());
+ WS.push(TrimmedGraph->getRoot());
unsigned Priority = 0;
while (!WS.empty()) {
@@ -2722,7 +2721,9 @@
// Are we at the final node?
if (OrigN->pred_empty()) {
- GNew->addRoot(NewN);
+ assert(OrigN == TrimmedGraph->getRoot() &&
+ "There should be only one root!");
+ GNew->designateAsRoot(NewN);
break;
}
diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
index 8ba304b..2e6631f 100644
--- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -87,8 +87,9 @@
/// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned MaxSteps,
ProgramStateRef InitState) {
- if (G.num_roots() == 0) { // Initialize the analysis by constructing
- // the root if none exists.
+ if (G.empty()) {
+ assert(!G.getRoot() && "empty graph must not have a root node");
+ // Initialize the analysis by constructing the root if there are no nodes.
const CFGBlock *Entry = &(L->getCFG()->getEntry());
@@ -117,7 +118,7 @@
bool IsNew;
ExplodedNode *Node = G.getNode(StartLoc, InitState, false, &IsNew);
assert(IsNew);
- G.addRoot(Node);
+ G.designateAsRoot(Node);
NodeBuilderContext BuilderCtx(*this, StartLoc.getDst(), Node);
ExplodedNodeSet DstBegin;
@@ -548,15 +549,11 @@
void CoreEngine::generateNode(const ProgramPoint &Loc,
ProgramStateRef State,
ExplodedNode *Pred) {
+ assert(Pred);
bool IsNew;
ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew);
- if (Pred)
- Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor.
- else {
- assert(IsNew);
- G.addRoot(Node); // 'Node' has no predecessor. Make it a root.
- }
+ Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor.
// Only add 'Node' to the worklist if it was freshly generated.
if (IsNew) WList->enqueue(Node);
diff --git a/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
index 7b2cccc..098922d9 100644
--- a/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
@@ -442,6 +442,10 @@
ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks,
InterExplodedGraphMap *ForwardMap,
InterExplodedGraphMap *InverseMap) const {
+ // FIXME: The two-pass algorithm of this function (which was introduced in
+ // 2008) is terribly overcomplicated and should be replaced by a single
+ // (backward) pass.
+
if (Nodes.empty())
return nullptr;
@@ -467,8 +471,9 @@
if (!Pass1.insert(N).second)
continue;
- // If this is a root enqueue it to the second worklist.
+ // If this is the root enqueue it to the second worklist.
if (N->Preds.empty()) {
+ assert(N == getRoot() && "Found non-root node with no predecessors!");
WL2.push_back(N);
continue;
}
@@ -477,12 +482,14 @@
WL1.append(N->Preds.begin(), N->Preds.end());
}
- // We didn't hit a root? Return with a null pointer for the new graph.
+ // We didn't hit the root? Return with a null pointer for the new graph.
if (WL2.empty())
return nullptr;
+ assert(WL2.size() == 1 && "There must be only one root!");
+
// Create an empty graph.
- std::unique_ptr<ExplodedGraph> G = MakeEmptyGraph();
+ std::unique_ptr<ExplodedGraph> G = std::make_unique<ExplodedGraph>();
// ===- Pass 2 (forward DFS to construct the new graph) -===
while (!WL2.empty()) {
@@ -503,9 +510,11 @@
// Also record the reverse mapping from the new node to the old node.
if (InverseMap) (*InverseMap)[NewN] = N;
- // If this node is a root, designate it as such in the graph.
- if (N->Preds.empty())
- G->addRoot(NewN);
+ // If this node is the root, designate it as such in the graph.
+ if (N->Preds.empty()) {
+ assert(N == getRoot());
+ G->designateAsRoot(NewN);
+ }
// In the case that some of the intended predecessors of NewN have already
// been created, we should hook them up as predecessors.
diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
index f71441a..ebad83d 100644
--- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -2529,7 +2529,7 @@
ExplodedGraph &G) {
const LocationContext *CalleeLC = Node->getLocation().getLocationContext();
const LocationContext *RootLC =
- (*G.roots_begin())->getLocation().getLocationContext();
+ G.getRoot()->getLocation().getLocationContext();
if (CalleeLC->getStackFrame() == RootLC->getStackFrame())
return nullptr;
