[analyzer] Pass external Dst set to NodeBuilder

This moves the responsibility for storing the output node set from the
builder to the clients. The builder is just responsible for transforming
an input set into the output set: {SrcSet/SrcNode} -> {Frontier}.

llvm-svn: 142826

8 files changed, 71 insertions, 71 deletions

diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h
index ad587ae928d..522749c37c2 100644
--- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h
+++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h
@@ -29,8 +29,6 @@ class CheckerContext {
   const ProgramPoint Location;
   const ProgramState *ST;
   const unsigned size;
-  // TODO: Use global context.
-  NodeBuilderContext Ctx;
   NodeBuilder &NB;
 public:
   bool *respondsToCallback;
@@ -48,7 +46,6 @@ public:
       Location(loc),
       ST(st),
       size(Dst.size()),
-      Ctx(builder.C.Eng, builder.getBlock(), pred),
       NB(builder),
       respondsToCallback(respondsToCB) {
     assert(!(ST && ST != Pred->getState()));
diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
index b151dfef228..934d15d8cc4 100644
--- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
+++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
@@ -165,7 +165,7 @@ public:
   }
 
   /// Enqueue the results of the node builder onto the work list.
-  void enqueue(NodeBuilder &NB);
+  void enqueue(ExplodedNodeSet &NB);
 };
 
 struct NodeBuilderContext {
@@ -181,12 +181,7 @@ class NodeBuilder {
 protected:
   friend class StmtNodeBuilder;
 
-  ExplodedNode *BuilderPred;
-
-// TODO: Context should become protected after refactoring is done.
-public:
   const NodeBuilderContext &C;
-protected:
 
   /// Specifies if the builder results have been finalized. For example, if it
   /// is set to false, autotransitions are yet to be generated.
@@ -196,8 +191,7 @@ protected:
 
   /// \brief The frontier set - a set of nodes which need to be propagated after
   /// the builder dies.
-  typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy;
-  DeferredTy Deferred;
+  ExplodedNodeSet &Frontier;
 
   BlockCounter getBlockCounter() const { return C.Eng.WList->getBlockCounter();}
 
@@ -205,9 +199,6 @@ protected:
   virtual bool checkResults() {
     if (!Finalized)
       return false;
-    for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I)
-      if ((*I)->isSink())
-        return false;
     return true;
   }
 
@@ -220,15 +211,16 @@ protected:
                                  bool MarkAsSink = false);
 
 public:
-  NodeBuilder(NodeBuilderContext &Ctx, bool F = true)
-    : C(Ctx), Finalized(F), HasGeneratedNodes(false) {
-    Deferred.insert(C.ContextPred);
+  NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
+              const NodeBuilderContext &Ctx, bool F = true)
+    : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) {
+    Frontier.insert(SrcNode);
   }
 
-  /// Create a new builder using the parent builder's context.
-  NodeBuilder(const NodeBuilder &ParentBldr, bool F = true)
-    : C(ParentBldr.C), Finalized(F), HasGeneratedNodes(false) {
-    Deferred.insert(C.ContextPred);
+  NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
+              const NodeBuilderContext &Ctx, bool F = true)
+    : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) {
+    Frontier.insert(SrcSet);
   }
 
   virtual ~NodeBuilder() {}
@@ -249,21 +241,29 @@ public:
     return HasGeneratedNodes;
   }
 
-  typedef DeferredTy::iterator iterator;
+  const ExplodedNodeSet &getResults() {
+    finalizeResults();
+    assert(checkResults());
+    return Frontier;
+  }
+
+  typedef ExplodedNodeSet::iterator iterator;
   /// \brief Iterators through the results frontier.
-  inline iterator results_begin() {
+  inline iterator begin() {
     finalizeResults();
     assert(checkResults());
-    return Deferred.begin();
+    return Frontier.begin();
   }
-  inline iterator results_end() {
+  inline iterator end() {
     finalizeResults();
-    return Deferred.end();
+    return Frontier.end();
   }
 
   /// \brief Return the CFGBlock associated with this builder.
   const CFGBlock *getBlock() const { return C.Block; }
 
+  const NodeBuilderContext &getContext() { return C; }
+
   /// \brief Returns the number of times the current basic block has been
   /// visited on the exploded graph path.
   unsigned getCurrentBlockCount() const {
@@ -297,7 +297,11 @@ public:
   void GenerateAutoTransition(ExplodedNode *N);
 
 public:
-  StmtNodeBuilder(ExplodedNode *N, unsigned idx, NodeBuilderContext &Ctx);
+  StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
+                  unsigned idx, const NodeBuilderContext &Ctx)
+    : NodeBuilder(SrcNode, DstSet, Ctx), Idx(idx),
+      PurgingDeadSymbols(false), BuildSinks(false), hasGeneratedNode(false),
+      PointKind(ProgramPoint::PostStmtKind), Tag(0) {}
 
   ~StmtNodeBuilder();
   
@@ -364,8 +368,8 @@ public:
   void importNodesFromBuilder(const NodeBuilder &NB) {
     ExplodedNode *NBPred = const_cast<ExplodedNode*>(NB.C.ContextPred);
     if (NB.hasGeneratedNodes()) {
-      Deferred.erase(NBPred);
-      Deferred.insert(NB.Deferred.begin(), NB.Deferred.end());
+      Frontier.erase(NBPred);
+      Frontier.insert(NB.Frontier);
     }
   }
 };
@@ -378,15 +382,16 @@ class BranchNodeBuilder: public NodeBuilder {
   bool InFeasibleFalse;
 
 public:
-  BranchNodeBuilder(NodeBuilderContext &C,
+  BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
+                    const NodeBuilderContext &C,
                     const CFGBlock *dstT, const CFGBlock *dstF)
-  : NodeBuilder(C), DstT(dstT), DstF(dstF),
+  : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF),
     InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {}
 
-  /// Create a new builder using the parent builder's context.
-  BranchNodeBuilder(BranchNodeBuilder &ParentBldr)
-  : NodeBuilder(ParentBldr), DstT(ParentBldr.DstT),
-    DstF(ParentBldr.DstF),
+  BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
+                    const NodeBuilderContext &C,
+                    const CFGBlock *dstT, const CFGBlock *dstF)
+  : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF),
     InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {}
 
   ExplodedNode *generateNode(const ProgramState *State, bool branch,
diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
index 43700f8f3f4..258fbeb9524 100644
--- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
+++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
@@ -386,6 +386,7 @@ public:
 
   unsigned size() const { return Impl.size();  }
   bool empty()    const { return Impl.empty(); }
+  bool erase(ExplodedNode *N) { return Impl.erase(N); }
 
   void clear() { Impl.clear(); }
   void insert(const ExplodedNodeSet &S) {
diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
index 07b2cedbd00..f18b04b8b8a 100644
--- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
+++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
@@ -117,6 +117,10 @@ public:
   BugReporter& getBugReporter() { return BR; }
 
   StmtNodeBuilder &getBuilder() { assert(Builder); return *Builder; }
+  const NodeBuilderContext &getBuilderContext() {
+    assert(Builder);
+    return Builder->getContext();
+  }
 
   bool isObjCGCEnabled() { return ObjCGCEnabled; }
 
@@ -163,6 +167,7 @@ public:
   void processBranch(const Stmt *Condition, const Stmt *Term, 
                      NodeBuilderContext& BuilderCtx,
                      ExplodedNode *Pred,
+                     ExplodedNodeSet &Dst,
                      const CFGBlock *DstT,
                      const CFGBlock *DstF);
 
diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h
index 8dfc1865bdb..e891e8fc423 100644
--- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h
+++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h
@@ -69,6 +69,7 @@ public:
   virtual void processBranch(const Stmt *Condition, const Stmt *Term,
                              NodeBuilderContext& BuilderCtx,
                              ExplodedNode *Pred,
+                             ExplodedNodeSet &Dst,
                              const CFGBlock *DstT,
                              const CFGBlock *DstF) = 0;
 
diff --git a/clang/lib/StaticAnalyzer/Core/CheckerContext.cpp b/clang/lib/StaticAnalyzer/Core/CheckerContext.cpp
index 26479d05521..5f43b77ceb6 100644
--- a/clang/lib/StaticAnalyzer/Core/CheckerContext.cpp
+++ b/clang/lib/StaticAnalyzer/Core/CheckerContext.cpp
@@ -18,8 +18,8 @@ using namespace ento;
 
 CheckerContext::~CheckerContext() {
   // Copy the results into the Dst set.
-  for (NodeBuilder::iterator I = NB.results_begin(),
-                             E = NB.results_end(); I != E; ++I) {
+  for (NodeBuilder::iterator I = NB.begin(),
+                             E = NB.end(); I != E; ++I) {
     Dst.Add(*I);
   }
 }
diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
index 525bd71111f..b9ab7b4c744 100644
--- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -315,7 +315,8 @@ void CoreEngine::HandleBlockEntrance(const BlockEntrance &L,
   // Process the entrance of the block.
   if (CFGElement E = L.getFirstElement()) {
     NodeBuilderContext Ctx(*this, L.getBlock(), Pred);
-    StmtNodeBuilder Builder(Pred, 0, Ctx);
+    ExplodedNodeSet Dst;
+    StmtNodeBuilder Builder(Pred, Dst, 0, Ctx);
     SubEng.processCFGElement(E, Builder, Pred);
   }
   else
@@ -419,8 +420,11 @@ void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,
                                 const CFGBlock * B, ExplodedNode *Pred) {
   assert(B->succ_size() == 2);
   NodeBuilderContext Ctx(*this, B, Pred);
-  SubEng.processBranch(Cond, Term, Ctx, Pred,
+  ExplodedNodeSet Dst;
+  SubEng.processBranch(Cond, Term, Ctx, Pred, Dst,
                        *(B->succ_begin()), *(B->succ_begin()+1));
+  // Enqueue the new frontier onto the worklist.
+  enqueue(Dst);
 }
 
 void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, 
@@ -432,7 +436,8 @@ void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx,
     HandleBlockExit(B, Pred);
   else {
     NodeBuilderContext Ctx(*this, B, Pred);
-    StmtNodeBuilder Builder(Pred, StmtIdx, Ctx);
+    ExplodedNodeSet Dst;
+    StmtNodeBuilder Builder(Pred, Dst, StmtIdx, Ctx);
     SubEng.processCFGElement((*B)[StmtIdx], Builder, Pred);
   }
 }
@@ -457,9 +462,9 @@ void CoreEngine::generateNode(const ProgramPoint &Loc,
   if (IsNew) WList->enqueue(Node);
 }
 
-void CoreEngine::enqueue(NodeBuilder &NB) {
-  for (NodeBuilder::iterator I = NB.results_begin(),
-                               E = NB.results_end(); I != E; ++I) {
+void CoreEngine::enqueue(ExplodedNodeSet &S) {
+  for (ExplodedNodeSet::iterator I = S.begin(),
+                                 E = S.end(); I != E; ++I) {
     WList->enqueue(*I);
   }
 }
@@ -494,28 +499,19 @@ ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc,
   bool IsNew;
   ExplodedNode *N = C.Eng.G->getNode(Loc, State, &IsNew);
   N->addPredecessor(FromN, *C.Eng.G);
-  Deferred.erase(FromN);
+  Frontier.erase(FromN);
 
   if (MarkAsSink)
     N->markAsSink();
-
-  if (IsNew && !N->isSink())
-    Deferred.insert(N);
+    
+  if (IsNew)
+    Frontier.Add(N);
 
   return (IsNew ? N : 0);
 }
 
-
-StmtNodeBuilder::StmtNodeBuilder(ExplodedNode *N, unsigned idx,
-                                 NodeBuilderContext &Ctx)
-  : NodeBuilder(Ctx), Idx(idx),
-    PurgingDeadSymbols(false), BuildSinks(false), hasGeneratedNode(false),
-    PointKind(ProgramPoint::PostStmtKind), Tag(0) {
-  Deferred.insert(N);
-}
-
 StmtNodeBuilder::~StmtNodeBuilder() {
-  for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I)
+  for (iterator I=Frontier.begin(), E=Frontier.end(); I!=E; ++I)
     if (!(*I)->isSink())
       GenerateAutoTransition(*I);
 }
@@ -554,14 +550,14 @@ void StmtNodeBuilder::GenerateAutoTransition(ExplodedNode *N) {
     C.Eng.WList->enqueue(Succ, C.Block, Idx+1);
 }
 
-ExplodedNode *StmtNodeBuilder::MakeNode(ExplodedNodeSet &Dst,
+ExplodedNode *StmtNodeBuilder::MakeNode(ExplodedNodeSet &DstSet,
                                         const Stmt *S, 
                                         ExplodedNode *Pred,
                                         const ProgramState *St,
                                         ProgramPoint::Kind K) {
   ExplodedNode *N = generateNode(S, St, Pred, K, 0, BuildSinks);
   if (N && !BuildSinks){
-      Dst.Add(N);
+      DstSet.Add(N);
   }
   return N;
 }
diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
index 269d7c74ee5..5742266de2b 100644
--- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -945,15 +945,14 @@ static SVal RecoverCastedSymbol(ProgramStateManager& StateMgr,
 void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term,
                                NodeBuilderContext& BldCtx,
                                ExplodedNode *Pred,
+                               ExplodedNodeSet &Dst,
                                const CFGBlock *DstT,
                                const CFGBlock *DstF) {
-
   // Check for NULL conditions; e.g. "for(;;)"
   if (!Condition) {
-    BranchNodeBuilder NullCondBldr(BldCtx, DstT, DstF);
+    BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF);
     NullCondBldr.markInfeasible(false);
     NullCondBldr.generateNode(Pred->getState(), true, Pred);
-    Engine.enqueue(NullCondBldr);
     return;
   }
 
@@ -961,18 +960,19 @@ void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term,
                                 Condition->getLocStart(),
                                 "Error evaluating branch");
 
-  NodeBuilder CheckerBldr(BldCtx);
+  ExplodedNodeSet TmpCheckersOut;
+  NodeBuilder CheckerBldr(Pred, TmpCheckersOut, BldCtx);
   getCheckerManager().runCheckersForBranchCondition(Condition, CheckerBldr,
                                                     Pred, *this);
 
-  for (NodeBuilder::iterator I = CheckerBldr.results_begin(),
-                             E = CheckerBldr.results_end(); E != I; ++I) {
+  BranchNodeBuilder builder(CheckerBldr.getResults(), Dst, BldCtx, DstT, DstF);
+  for (NodeBuilder::iterator I = CheckerBldr.begin(),
+                             E = CheckerBldr.end(); E != I; ++I) {
     ExplodedNode *PredI = *I;
 
     if (PredI->isSink())
       continue;
 
-    BranchNodeBuilder builder(BldCtx, DstT, DstF);
     const ProgramState *PrevState = Pred->getState();
     SVal X = PrevState->getSVal(Condition);
 
@@ -998,8 +998,6 @@ void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term,
     if (X.isUnknownOrUndef()) {
       builder.generateNode(MarkBranch(PrevState, Term, true), true, PredI);
       builder.generateNode(MarkBranch(PrevState, Term, false), false, PredI);
-      // Enqueue the results into the work list.
-      Engine.enqueue(builder);
       continue;
     }
 
@@ -1020,9 +1018,6 @@ void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term,
       else
         builder.markInfeasible(false);
     }
-
-    // Enqueue the results into the work list.
-    Engine.enqueue(builder);
   }
 }