https://github.com/NagyDonat created https://github.com/llvm/llvm-project/pull/187742
`ExplodedNodeSet` is a simple and useful utility type in the analyzer, but its insertion methods were a bit confusing, so this commit clarifies them (and adds doc-comments for this class). Previously this class had `void Add(ExplodedNode*)` for inserting single nodes and `void insert(const ExplodedNodeSet &)` for inserting all nodes from another set; but `ExplodedNode*` is implicitly convertible to `ExplodedNodeSet`, so it was also possible to insert single nodes with `insert`. There was also a subtle difference between `Set.Add(Node)` and `Set.insert(Node)`: `Add` accepted and ignored nullpointers and sink nodes (which is often useful) while the constructor `ExplodedNodeSet(ExplodedNode*)` enforced the same invariant in a less helpful way, with an assertion. This commit eliminates the name `Add` (because `insert` is more customary for set types), but standardizes its "null or sink nodes are silently ignored" behavior which is very useful in practice. After this commit `insert` has two overloads: `ExplodedNodeSet::insert(ExplodedNode*)` which inserts a single node (or does nothing if the argument is null or sink) and `ExplodedNodeSet::insert(const ExplodedNodeSet&)` which inserts all nodes from the other set. Note that around half of the calls to `Add` were recently introduced by my `NodeBuilder` cleanup commit series; I expect to introduce dozens of calls in the foreseeable future, so it would be nice to clean up the naming situation here. From 0c81f2bf7e102c4a77c357727f35eac82d39d8cc Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Fri, 20 Mar 2026 15:57:21 +0100 Subject: [PATCH 1/4] [NFC] Consistently accept and ignore null or sink nodes in set `ExplodedNodeSet` has a (very useful) invariant that its elements are never null or sink. The constructor `ExplodedNodeSet(ExplodedNode *N)` previously enforced this invariant with an assertion; but this commit replaces that with a call to `Add()`, which ignores null or sink nodes. This constructor is frequently used when a single node is passed to a function that expects a node set; and in those situations ignoring null or sink nodes is alwyas the "right thing to do", while the current assertion is a footgun that could trigger surprise crashes in rare corner cases. --- .../clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h index a536f5ee046e1..04df9364c8969 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -446,8 +446,8 @@ class ExplodedNodeSet { public: ExplodedNodeSet(ExplodedNode *N) { - assert(N && !N->isSink()); - Impl.insert(N); + if (N && !N->isSink()) + Impl.insert(N); } ExplodedNodeSet() = default; From 0e0ab50a8639a8498fd9c01830d46ffd297ea78d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Fri, 20 Mar 2026 16:37:17 +0100 Subject: [PATCH 2/4] [NFC] Return early instead of assertion Mathematically, inserting the elements that are already present in a set is well-defined and doesn't change anything; so there is no reason to trigger an assertion in this corner case (which will probably never happen in practice). --- .../clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h index 04df9364c8969..5b659c3ef8cf5 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -446,8 +446,7 @@ class ExplodedNodeSet { public: ExplodedNodeSet(ExplodedNode *N) { - if (N && !N->isSink()) - Impl.insert(N); + Add(N); } ExplodedNodeSet() = default; @@ -467,7 +466,8 @@ class ExplodedNodeSet { void clear() { Impl.clear(); } void insert(const ExplodedNodeSet &S) { - assert(&S != this); + if (&S == this) + return; if (empty()) Impl = S.Impl; else From 1330e9cda87048f1bcc0fc14cf56530bb290fb41 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Fri, 20 Mar 2026 17:17:12 +0100 Subject: [PATCH 3/4] [NFC] Rename `ExplodedNodeSet::Add` to `insert` This new `insert(ExplodedNode *)` becomes a second overload along with the previously existing `insert(const ExplodedNodeSet &)`. This serves multiple purposes: 1. Improves consistency with other set types (e.g. with `SmallSetVector`), the `Impl` behind the `ExplodedNodeSet`) that also use `insert` as the name of the method that inserts a single element. 2. As there is implicit conversion from `ExplodedNode*` to `ExplodedNodeSet`, it was already possible to insert single nodes with `insert(const ExplodedNodeSet &S)` and there were a few call sites that already used this. Instead of fighting against this naturally occuring pattern, let's embrace and support it. 3. It gets rid of the method name `Add`, whose capitalization goes against our coding standard. Note that around half of the calls to `Add` were recently introduced by my `NodeBuilder` cleanup commit series; I expect to introduce dozens of calls in the foreseeable future, so it would be good to clean up the name before that. --- .../StaticAnalyzer/Core/PathSensitive/CoreEngine.h | 4 ++-- .../Core/PathSensitive/ExplodedGraph.h | 14 ++++++-------- clang/lib/StaticAnalyzer/Core/CoreEngine.cpp | 2 +- clang/lib/StaticAnalyzer/Core/ExprEngine.cpp | 10 +++++----- clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp | 4 ++-- .../Core/ExprEngineCallAndReturn.cpp | 4 ++-- 6 files changed, 18 insertions(+), 20 deletions(-) diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index 8d5dcc1ca8b13..76bd8346f269e 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -259,7 +259,7 @@ class NodeBuilder { NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, const NodeBuilderContext &Ctx) : NodeBuilder(DstSet, Ctx) { - Frontier.Add(SrcNode); + Frontier.insert(SrcNode); } NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, @@ -314,7 +314,7 @@ class NodeBuilder { void takeNodes(ExplodedNode *N) { Frontier.erase(N); } void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); } - void addNodes(ExplodedNode *N) { Frontier.Add(N); } + void addNodes(ExplodedNode *N) { Frontier.insert(N); } }; /// BranchNodeBuilder is responsible for constructing the nodes diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h index 5b659c3ef8cf5..ae277ce5fbc43 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -445,17 +445,10 @@ class ExplodedNodeSet { ImplTy Impl; public: - ExplodedNodeSet(ExplodedNode *N) { - Add(N); - } + ExplodedNodeSet(ExplodedNode *N) { insert(N); } ExplodedNodeSet() = default; - void Add(ExplodedNode *N) { - if (N && !N->isSink()) - Impl.insert(N); - } - using iterator = ImplTy::iterator; using const_iterator = ImplTy::const_iterator; @@ -465,6 +458,11 @@ class ExplodedNodeSet { void clear() { Impl.clear(); } + void insert(ExplodedNode *N) { + if (N && !N->isSink()) + Impl.insert(N); + } + void insert(const ExplodedNodeSet &S) { if (&S == this) return; diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index 26672ff75996c..a348f7947ad98 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -689,7 +689,7 @@ ExplodedNode *NodeBuilder::generateNode(const ProgramPoint &Loc, Frontier.erase(FromN); ExplodedNode *N = C.getEngine().makeNode(Loc, State, FromN, MarkAsSink); - Frontier.Add(N); + Frontier.insert(N); return N; } diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 0fb8f1d00b618..e9522a7975515 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -1131,7 +1131,7 @@ void ExprEngine::ProcessStmt(const Stmt *currStmt, ExplodedNode *Pred) { removeDead(Pred, CleanedStates, currStmt, Pred->getLocationContext()); } else - CleanedStates.Add(Pred); + CleanedStates.insert(Pred); // Visit the statement. ExplodedNodeSet Dst; @@ -1190,7 +1190,7 @@ void ExprEngine::ProcessInitializer(const CFGInitializer CFGInit, // But we still need to stop tracking the object under construction. State = finishObjectConstruction(State, BMI, LC); PostStore PS(Init, LC, /*Loc*/ nullptr, /*tag*/ nullptr); - Tmp.Add(Engine.makeNode(PS, State, Pred)); + Tmp.insert(Engine.makeNode(PS, State, Pred)); } else { const ValueDecl *Field; if (BMI->isIndirectMemberInitializer()) { @@ -1245,7 +1245,7 @@ void ExprEngine::ProcessInitializer(const CFGInitializer CFGInit, ExplodedNodeSet Dst; for (ExplodedNode *Pred : Tmp) - Dst.Add(Engine.makeNode(PP, Pred->getState(), Pred)); + Dst.insert(Engine.makeNode(PP, Pred->getState(), Pred)); // Enqueue the new nodes onto the work list. Engine.enqueueStmtNodes(Dst, getCurrBlock(), currStmtIdx); } @@ -1328,7 +1328,7 @@ void ExprEngine::ProcessNewAllocator(const CXXNewExpr *NE, const LocationContext *LCtx = Pred->getLocationContext(); PostImplicitCall PP(NE->getOperatorNew(), NE->getBeginLoc(), LCtx, getCFGElementRef()); - Dst.Add(Engine.makeNode(PP, Pred->getState(), Pred)); + Dst.insert(Engine.makeNode(PP, Pred->getState(), Pred)); } Engine.enqueueStmtNodes(Dst, getCurrBlock(), currStmtIdx); } @@ -2999,7 +2999,7 @@ void ExprEngine::processIndirectGoto(ExplodedNodeSet &Dst, const Expr *Tgt, // FIXME: If 'V' was a symbolic value, then record that on this execution // path it is equal to the address of the label leading to 'Succ'. BlockEdge BE(getCurrBlock(), Succ, Pred->getLocationContext()); - Dst.Add(Engine.makeNode(BE, State, Pred)); + Dst.insert(Engine.makeNode(BE, State, Pred)); } } } diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp index cf22b62225f2f..701c7fdc88497 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp @@ -93,7 +93,7 @@ void ExprEngine::performTrivialCopy(NodeBuilder &Bldr, ExplodedNode *Pred, // In that case, copying the empty base class subobject would overwrite the // object that it overlaps with - so let's not do that. // See issue-157467.cpp for an example. - Dst.Add(Pred); + Dst.insert(Pred); } PostStmt PS(CallExpr, LCtx); @@ -1130,7 +1130,7 @@ void ExprEngine::VisitCXXCatchStmt(const CXXCatchStmt *CS, ExplodedNode *Pred, ExplodedNodeSet &Dst) { const VarDecl *VD = CS->getExceptionDecl(); if (!VD) { - Dst.Add(Pred); + Dst.insert(Pred); return; } diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp index f6ba3699312ec..b4dc4fa8a077d 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp @@ -169,7 +169,7 @@ void ExprEngine::removeDeadOnEndOfFunction(ExplodedNode *Pred, const CFGBlock *Blk = nullptr; std::tie(LastSt, Blk) = getLastStmt(Pred); if (!Blk || !LastSt) { - Dst.Add(Pred); + Dst.insert(Pred); return; } @@ -369,7 +369,7 @@ void ExprEngine::processCallExit(ExplodedNode *CEBNode) { /*DiagnosticStmt=*/CalleeCtx->getAnalysisDeclContext()->getBody(), ProgramPoint::PostStmtPurgeDeadSymbolsKind); } else { - CleanedNodes.Add(CEBNode); + CleanedNodes.insert(CEBNode); } // The second half of this process happens in the caller context. This is an From 2b7a267f758c924ca59d1f8596053fed3cbbea70 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Fri, 20 Mar 2026 17:39:22 +0100 Subject: [PATCH 4/4] [NFC] Document ExplodedNodeSet in comment --- .../StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h | 8 ++++++++ 1 file changed, 8 insertions(+) diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h index ae277ce5fbc43..bb2297a6889c9 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -440,6 +440,14 @@ class ExplodedGraph { void collectNode(ExplodedNode *node); }; +/// ExplodedNodeSet is a set of `ExplodedNode *` elements with the invariant +/// that its elements cannot be nullpointers or sink nodes. Insertion of null +/// or sink nodes is silently ignored (which is comfortable in many use cases). +/// Note that `ExplodedNode *` is implicitly convertible to an +/// `ExplodedNodeSet` containing 0 or 1 elements (where null pointers and sink +/// nodes converted to the empty set). +/// This type has set semantics (repeated insertions are ignored), but the +/// iteration order is always the order of (first) insertion. class ExplodedNodeSet { using ImplTy = llvm::SmallSetVector<ExplodedNode *, 4>; ImplTy Impl; _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
