[analyzer] Node Builder refactoring: Introduce a simple Node Builder responsible for generating the node frontier.

Currently we have a bunch of different node builders which provide some common
functionality but are difficult to refactor. Each builder generates nodes of
different kinds and calculates the frontier nodes, which should be propagated
to the next step (after the builder dies).

Introduce a new NodeBuilder which provides very basic node generation facilities
but takes care of the second problem. The idea is that all the other builders
will eventually use it. Use this builder in CheckerContext instead of
StmtNodeBuilder (the way the frontier is propagated to the StmtBuilder
is a hack and will be removed later on).

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@142443 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 151 insertions, 72 deletions

diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h
index 1f14787132..ea7776c61f 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h
@@ -27,11 +27,10 @@ class CheckerContext {
   StmtNodeBuilder &B;
   ExprEngine &Eng;
   ExplodedNode *Pred;
-  SaveAndRestore<bool> OldSink;
-  SaveOr OldHasGen;
   const ProgramPoint Location;
   const ProgramState *ST;
   const unsigned size;
+  NodeBuilder NB;
 public:
   bool *respondsToCallback;
 public:
@@ -46,12 +45,13 @@ public:
       B(builder),
       Eng(eng),
       Pred(pred),
-      OldSink(B.BuildSinks),
-      OldHasGen(B.hasGeneratedNode),
       Location(loc),
       ST(st),
       size(Dst.size()),
-      respondsToCallback(respondsToCB) {}
+      NB(builder.Eng, pred),
+      respondsToCallback(respondsToCB) {
+    assert(!(ST && ST != Pred->getState()));
+  }
 
   ~CheckerContext();
 
@@ -71,7 +71,6 @@ public:
     return Eng.getStoreManager();
   }
 
-  ExplodedNodeSet &getNodeSet() { return Dst; }
   ExplodedNode *&getPredecessor() { return Pred; }
   const ProgramState *getState() { return ST ? ST : Pred->getState(); }
 
@@ -114,10 +113,9 @@ public:
   ExplodedNode *generateNode(const ProgramState *state,
                              ExplodedNode *pred,
                              const ProgramPointTag *tag = 0,
-                             bool autoTransition = true) {
-    ExplodedNode *N = generateNodeImpl(state, false, pred, tag);
-    if (N && autoTransition)
-      addTransition(N);
+                             bool autoTransition = true,
+                             bool isSink = false) {
+    ExplodedNode *N = generateNodeImpl(state, isSink, pred, tag);
     return N;
   }
 
@@ -126,8 +124,6 @@ public:
                              bool autoTransition = true,
                              const ProgramPointTag *tag = 0) {
     ExplodedNode *N = generateNodeImpl(state, false, 0, tag);
-    if (N && autoTransition)
-      addTransition(N);
     return N;
   }
 
@@ -137,20 +133,13 @@ public:
     return generateNodeImpl(state ? state : getState(), true);
   }
 
-  void addTransition(ExplodedNode *node) {
-    Dst.Add(node);
-  }
-  
   void addTransition(const ProgramState *state,
                      const ProgramPointTag *tag = 0) {
     assert(state);
     // If the 'state' is not new, we need to check if the cached state 'ST'
     // is new.
-    if (state != getState() || (ST && ST != Pred->getState()))
-      // state is new or equals to ST.
+    if (state != getState())
       generateNode(state, true, tag);
-    else
-      Dst.Add(Pred);
   }
 
   void EmitReport(BugReport *R) {
@@ -167,11 +156,9 @@ private:
                                  ExplodedNode *pred = 0,
                                  const ProgramPointTag *tag = 0) {
 
-    ExplodedNode *node = B.generateNode(tag ? Location.withTag(tag) : Location,
+    ExplodedNode *node = NB.generateNode(tag ? Location.withTag(tag) : Location,
                                         state,
-                                        pred ? pred : Pred);
-    if (markAsSink && node)
-      node->markAsSink();
+                                        pred ? pred : Pred, markAsSink);
     return node;
   }
 };
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
index 131d39e755..5849cc1545 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
@@ -37,6 +37,8 @@ namespace ento {
 ///   at the statement and block-level.  The analyses themselves must implement
 ///   any transfer function logic and the sub-expression level (if any).
 class CoreEngine {
+  friend class CommonNodeBuilder;
+  friend class NodeBuilder;
   friend class StmtNodeBuilder;
   friend class GenericNodeBuilderImpl;
   friend class BranchNodeBuilder;
@@ -161,13 +163,80 @@ public:
   }
 };
 
-class StmtNodeBuilder {
+/// This is the simplest builder which generates nodes in the ExplodedGraph.
+class NodeBuilder {
+  friend class StmtNodeBuilder;
+
   CoreEngine& Eng;
-  const CFGBlock &B;
-  const unsigned Idx;
   ExplodedNode *Pred;
+  bool Finalized;
+
+  /// \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;
+
+  BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter(); }
+
+  virtual void finalizeResults() {
+    if (!Finalized) {
+      // TODO: Remove assert after refactoring is complete?
+      for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I)
+        assert(!(*I)->isSink());
+      Finalized = true;
+    }
+  }
+  
+  ExplodedNode *generateNodeImpl(const ProgramPoint &PP,
+                                 const ProgramState *State,
+                                 ExplodedNode *Pred,
+                                 bool MarkAsSink = false);
+
+public:
+  NodeBuilder(CoreEngine& e, ExplodedNode *pred);
+  ~NodeBuilder() {}
+
+  /// \brief Generates a node in the ExplodedGraph.
+  ///
+  /// When a node is marked as sink, the exploration from the node is stopped -
+  /// the node becomes the last node on the path.
+  ExplodedNode *generateNode(const ProgramPoint &PP,
+                             const ProgramState *State,
+                             ExplodedNode *Pred,
+                             bool MarkAsSink = false) {
+    return generateNodeImpl(PP, State, Pred, MarkAsSink);
+  }
+
+  // \brief Get the builder's predecessor - the parent to all the other nodes.
+  const ExplodedNode* getPred() const { return Pred; }
+
+  bool hasGeneratedNodes() const {
+    return (!Deferred.count(Pred));
+  }
+
+  typedef DeferredTy::iterator iterator;
+  /// \brief Iterators through the results frontier.
+  inline iterator results_begin() { finalizeResults(); return Deferred.begin();}
+  inline iterator results_end() { finalizeResults(); return Deferred.end(); }
+
+};
+
+class CommonNodeBuilder {
+protected:
+  ExplodedNode *Pred;
+public:
+  // TODO: make protected.
+  CoreEngine& Eng;
+
+  CommonNodeBuilder(CoreEngine* E, ExplodedNode *P) : Pred(P), Eng(*E) {}
+  BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter(); }
+};
 
 
+class StmtNodeBuilder: public CommonNodeBuilder {
+  const CFGBlock &B;
+  const unsigned Idx;
+
 public:
   bool PurgingDeadSymbols;
   bool BuildSinks;
@@ -189,12 +258,7 @@ public:
   ~StmtNodeBuilder();
 
   ExplodedNode *getPredecessor() const { return Pred; }
-
-  // FIXME: This should not be exposed.
-  WorkList *getWorkList() { return Eng.WList; }
-
-  BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();}
-
+  
   unsigned getCurrentBlockCount() const {
     return getBlockCounter().getNumVisited(
                             Pred->getLocationContext()->getCurrentStackFrame(),
@@ -276,14 +340,21 @@ public:
     BuildSinks = Tmp;
     return N;
   }
+
+  void importNodesFromBuilder(const NodeBuilder &NB) {
+    ExplodedNode *NBPred = const_cast<ExplodedNode*>(NB.getPred());
+    if (NB.hasGeneratedNodes()) {
+      Deferred.erase(NBPred);
+      Deferred.insert(NB.Deferred.begin(), NB.Deferred.end());
+      hasGeneratedNode = true;
+    }
+  }
 };
 
-class BranchNodeBuilder {
-  CoreEngine& Eng;
+class BranchNodeBuilder: public CommonNodeBuilder {
   const CFGBlock *Src;
   const CFGBlock *DstT;
   const CFGBlock *DstF;
-  ExplodedNode *Pred;
 
   typedef SmallVector<ExplodedNode*,3> DeferredTy;
   DeferredTy Deferred;
@@ -296,7 +367,7 @@ class BranchNodeBuilder {
 public:
   BranchNodeBuilder(const CFGBlock *src, const CFGBlock *dstT, 
                       const CFGBlock *dstF, ExplodedNode *pred, CoreEngine* e)
-  : Eng(*e), Src(src), DstT(dstT), DstF(dstF), Pred(pred),
+  : CommonNodeBuilder(e, pred), Src(src), DstT(dstT), DstF(dstF),
     GeneratedTrue(false), GeneratedFalse(false),
     InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {}
 
@@ -306,11 +377,10 @@ public:
 
   const ExplodedGraph& getGraph() const { return *Eng.G; }
 
-  BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();}
-
   /// This function generates a new ExplodedNode but not a new
   /// branch(block edge).
-  ExplodedNode *generateNode(const Stmt *Condition, const ProgramState *State);
+  ExplodedNode *generateNode(const Stmt *Condition, const ProgramState *State,
+                             const ProgramPointTag *Tag = 0);
 
   ExplodedNode *generateNode(const ProgramState *State, bool branch);
 
@@ -472,10 +542,8 @@ public:
   const PP_T &getProgramPoint() const { return cast<PP_T>(pp); }
 };
 
-class EndOfFunctionNodeBuilder {
-  CoreEngine &Eng;
+class EndOfFunctionNodeBuilder : public CommonNodeBuilder {
   const CFGBlock &B;
-  ExplodedNode *Pred;
   const ProgramPointTag *Tag;
 
 public:
@@ -484,7 +552,7 @@ public:
 public:
   EndOfFunctionNodeBuilder(const CFGBlock *b, ExplodedNode *N, CoreEngine* e,
                            const ProgramPointTag *tag = 0)
-    : Eng(*e), B(*b), Pred(N), Tag(tag), hasGeneratedNode(false) {}
+    : CommonNodeBuilder(e, N), B(*b), Tag(tag), hasGeneratedNode(false) {}
 
   ~EndOfFunctionNodeBuilder();
 
@@ -496,10 +564,6 @@ public:
 
   ExplodedNode *getPredecessor() const { return Pred; }
 
-  BlockCounter getBlockCounter() const {
-    return Eng.WList->getBlockCounter();
-  }
-
   unsigned getCurrentBlockCount() const {
     return getBlockCounter().getNumVisited(
                             Pred->getLocationContext()->getCurrentStackFrame(),
diff --git a/lib/StaticAnalyzer/Checkers/RetainCountChecker.cpp b/lib/StaticAnalyzer/Checkers/RetainCountChecker.cpp
index 93e0fe5b4f..be7ce384e7 100644
--- a/lib/StaticAnalyzer/Checkers/RetainCountChecker.cpp
+++ b/lib/StaticAnalyzer/Checkers/RetainCountChecker.cpp
@@ -54,12 +54,18 @@ public:
   GenericNodeBuilderRefCount(EndOfFunctionNodeBuilder &enb)
   : C(0), tag(0), ENB(&enb) {}
 
-  ExplodedNode *MakeNode(const ProgramState *state, ExplodedNode *Pred) {
-    if (C)
-      return C->generateNode(state, Pred, tag, false);
+  ExplodedNode *MakeNode(const ProgramState *state, ExplodedNode *Pred,
+                         bool MarkAsSink = false) {
+    if (C) {
+        return C->generateNode(state, Pred, tag, false, MarkAsSink);
+    }
 
     assert(ENB);
-    return ENB->generateNode(state, Pred);
+    ExplodedNode *N = ENB->generateNode(state, Pred);
+    if (MarkAsSink) 
+      N->markAsSink();
+    
+    return N;
   }
 };
 } // end anonymous namespace
@@ -3366,9 +3372,7 @@ RetainCountChecker::handleAutoreleaseCounts(const ProgramState *state,
   V = V ^ RefVal::ErrorOverAutorelease;
   state = state->set<RefBindings>(Sym, V);
 
-  if (ExplodedNode *N = Bd.MakeNode(state, Pred)) {
-    N->markAsSink();
-
+  if (ExplodedNode *N = Bd.MakeNode(state, Pred, true)) {
     llvm::SmallString<128> sbuf;
     llvm::raw_svector_ostream os(sbuf);
     os << "Object over-autoreleased: object was sent -autorelease ";
diff --git a/lib/StaticAnalyzer/Core/CheckerContext.cpp b/lib/StaticAnalyzer/Core/CheckerContext.cpp
index 5356edc752..e380165c2e 100644
--- a/lib/StaticAnalyzer/Core/CheckerContext.cpp
+++ b/lib/StaticAnalyzer/Core/CheckerContext.cpp
@@ -17,17 +17,13 @@ using namespace clang;
 using namespace ento;
 
 CheckerContext::~CheckerContext() {
-  // Do we need to autotransition?  'Dst' can get populated in a variety of
-  // ways, including 'addTransition()' adding the predecessor node to Dst
-  // without actually generated a new node.  We also shouldn't autotransition
-  // if we are building sinks or we generated a node and decided to not
-  // add it as a transition.
-  if (Dst.size() == size && !B.BuildSinks && !B.hasGeneratedNode) {
-    if (ST && ST != Pred->getState()) {
-      static SimpleProgramPointTag autoTransitionTag("CheckerContext : auto");
-      addTransition(ST, &autoTransitionTag);
-    }
-    else
-      Dst.Add(Pred);
+  // Copy the results into the Dst set.
+  for (NodeBuilder::iterator I = NB.results_begin(),
+                             E = NB.results_end(); I != E; ++I) {
+    Dst.Add(*I);
   }
+
+  // Copy the results  into the StmtNodeBuilder.
+  //TODO: This will be removed after we completely migrate NodeBuilder.
+  B.importNodesFromBuilder(NB);
 }
diff --git a/lib/StaticAnalyzer/Core/CoreEngine.cpp b/lib/StaticAnalyzer/Core/CoreEngine.cpp
index 525219846a..5f2f4ea7f1 100644
--- a/lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ b/lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -475,11 +475,39 @@ GenericNodeBuilderImpl::generateNodeImpl(const ProgramState *state,
   return 0;
 }
 
+NodeBuilder::NodeBuilder(CoreEngine& e, ExplodedNode *N)
+  : Eng(e), Pred(N), Finalized(false) {
+  assert(!N->isSink());
+  Deferred.insert(N);
+}
+
+ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc,
+                                            const ProgramState *State,
+                                            ExplodedNode *Pred,
+                                            bool MarkAsSink) {
+  assert(Finalized == false &&
+         "We cannot create new nodes after the results have been finalized.");
+                                              
+  bool IsNew;
+  ExplodedNode *N = Eng.G->getNode(Loc, State, &IsNew);
+  N->addPredecessor(Pred, *Eng.G);
+  Deferred.erase(Pred);
+
+  if (MarkAsSink)
+    N->markAsSink();
+
+  if (IsNew && !N->isSink())
+    Deferred.insert(N);
+
+  return (IsNew ? N : 0);
+}
+
+
 StmtNodeBuilder::StmtNodeBuilder(const CFGBlock *b,
                                  unsigned idx,
                                  ExplodedNode *N,
                                  CoreEngine* e)
-  : Eng(*e), B(*b), Idx(idx), Pred(N),
+  : CommonNodeBuilder(e, N), B(*b), Idx(idx),
     PurgingDeadSymbols(false), BuildSinks(false), hasGeneratedNode(false),
     PointKind(ProgramPoint::PostStmtKind), Tag(0) {
   Deferred.insert(N);
@@ -574,12 +602,12 @@ StmtNodeBuilder::generateNodeInternal(const ProgramPoint &Loc,
 
 // This function generate a new ExplodedNode but not a new branch(block edge).
 ExplodedNode *BranchNodeBuilder::generateNode(const Stmt *Condition,
-                                              const ProgramState *State) {
+                                              const ProgramState *State,
+                                              const ProgramPointTag *Tag) {
   bool IsNew;
-  
   ExplodedNode *Succ 
-    = Eng.G->getNode(PostCondition(Condition, Pred->getLocationContext()), State,
-                     &IsNew);
+    = Eng.G->getNode(PostCondition(Condition, Pred->getLocationContext(), Tag),
+                     State, &IsNew);
   
   Succ->addPredecessor(Pred, *Eng.G);