6 files changed, 164 insertions, 10 deletions
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
index 5bd566ff63..e75cdd8759 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
@@ -65,7 +65,7 @@ private:
   /// WList - A set of queued nodes that need to be processed by the
   ///  worklist algorithm.  It is up to the implementation of WList to decide
   ///  the order that nodes are processed.
-  WorkList* WList;
+  OwningPtr<WorkList> WList;
 
   /// BCounterFactory - A factory object for created BlockCounter objects.
   ///   These are used to record for key nodes in the ExplodedGraph the
@@ -107,20 +107,15 @@ private:
   ExplodedNode *generateCallExitBeginNode(ExplodedNode *N);
 
 public:
-  /// Construct a CoreEngine object to analyze the provided CFG using
-  ///  a DFS exploration of the exploded graph.
+  /// Construct a CoreEngine object to analyze the provided CFG.
   CoreEngine(SubEngine& subengine, SetOfConstDecls *VisitedCallees,
              FunctionSummariesTy *FS)
     : SubEng(subengine), G(new ExplodedGraph()),
-      WList(WorkList::makeBFS()),
+      WList(WorkList::makeDFS()),
       BCounterFactory(G->getAllocator()),
       AnalyzedCallees(VisitedCallees),
       FunctionSummaries(FS){}
 
-  ~CoreEngine() {
-    delete WList;
-  }
-
   /// getGraph - Returns the exploded graph.
   ExplodedGraph& getGraph() { return *G.get(); }
 
@@ -156,7 +151,7 @@ public:
     blocksAborted.push_back(std::make_pair(block, node));
   }
   
-  WorkList *getWorkList() const { return WList; }
+  WorkList *getWorkList() const { return WList.get(); }
 
   BlocksExhausted::const_iterator blocks_exhausted_begin() const {
     return blocksExhausted.begin();
diff --git a/lib/StaticAnalyzer/Checkers/CMakeLists.txt b/lib/StaticAnalyzer/Checkers/CMakeLists.txt
index f121dd5705..79b0539ba0 100644
--- a/lib/StaticAnalyzer/Checkers/CMakeLists.txt
+++ b/lib/StaticAnalyzer/Checkers/CMakeLists.txt
@@ -58,6 +58,7 @@ add_clang_library(clangStaticAnalyzerCheckers
   StackAddrEscapeChecker.cpp
   StreamChecker.cpp
   TaintTesterChecker.cpp
+  TraversalChecker.cpp
   UndefBranchChecker.cpp
   UndefCapturedBlockVarChecker.cpp
   UndefResultChecker.cpp
diff --git a/lib/StaticAnalyzer/Checkers/Checkers.td b/lib/StaticAnalyzer/Checkers/Checkers.td
index 28b0679d35..0969053976 100644
--- a/lib/StaticAnalyzer/Checkers/Checkers.td
+++ b/lib/StaticAnalyzer/Checkers/Checkers.td
@@ -479,6 +479,10 @@ def CallGraphDumper : Checker<"DumpCallGraph">,
   HelpText<"Display Call Graph">,
   DescFile<"DebugCheckers.cpp">;
 
+def TraversalDumper : Checker<"DumpTraversal">,
+  HelpText<"Print branch conditions as they are traversed by the engine">,
+  DescFile<"TraversalChecker.cpp">;
+
 def AnalyzerStatsChecker : Checker<"Stats">,
   HelpText<"Emit warnings with analyzer statistics">,
   DescFile<"AnalyzerStatsChecker.cpp">;
diff --git a/lib/StaticAnalyzer/Checkers/TraversalChecker.cpp b/lib/StaticAnalyzer/Checkers/TraversalChecker.cpp
new file mode 100644
index 0000000000..d0479d4519
--- /dev/null
+++ b/lib/StaticAnalyzer/Checkers/TraversalChecker.cpp
@@ -0,0 +1,57 @@
+//== TraversalChecker.cpp -------------------------------------- -*- C++ -*--=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This checker prints branch statements to llvm::outs as they are encountered.
+// This lets us see exactly how the ExprEngine is traversing the graph.
+//
+//===----------------------------------------------------------------------===//
+#include "ClangSACheckers.h"
+#include "clang/AST/ParentMap.h"
+#include "clang/AST/StmtObjC.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/CheckerManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+class TraversalDumper : public Checker< check::BranchCondition,
+                                        check::EndPath > {
+public:
+  void checkBranchCondition(const Stmt *Condition, CheckerContext &C) const;
+  void checkEndPath(CheckerContext &C) const;
+};
+}
+
+void TraversalDumper::checkBranchCondition(const Stmt *Condition,
+                                           CheckerContext &C) const {
+  // Special-case Objective-C's for-in loop, which uses the entire loop as its
+  // condition. We just print the collection expression.
+  const Stmt *Parent = dyn_cast<ObjCForCollectionStmt>(Condition);
+  if (!Parent) {
+    const ParentMap &Parents = C.getLocationContext()->getParentMap();
+    Parent = Parents.getParent(Condition);
+  }
+
+  // It is mildly evil to print directly to llvm::outs() rather than emitting
+  // warnings, but this ensures things do not get filtered out by the rest of
+  // the static analyzer machinery.
+  SourceLocation Loc = Parent->getLocStart();
+  llvm::outs() << C.getSourceManager().getSpellingLineNumber(Loc) << " "
+               << Parent->getStmtClassName() << "\n";
+}
+
+void TraversalDumper::checkEndPath(CheckerContext &C) const {
+  llvm::outs() << "--END PATH--\n";
+}
+
+void ento::registerTraversalDumper(CheckerManager &mgr) {
+  mgr.registerChecker<TraversalDumper>();
+}
diff --git a/lib/StaticAnalyzer/Core/CoreEngine.cpp b/lib/StaticAnalyzer/Core/CoreEngine.cpp
index f691d5f3d6..689f05714f 100644
--- a/lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ b/lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -76,7 +76,7 @@ public:
   }
 
   virtual void enqueue(const WorkListUnit& U) {
-    Queue.push_front(U);
+    Queue.push_back(U);
   }
 
   virtual WorkListUnit dequeue() {
diff --git a/test/Analysis/traversal-algorithm.mm b/test/Analysis/traversal-algorithm.mm
new file mode 100644
index 0000000000..49e72249e0
--- /dev/null
+++ b/test/Analysis/traversal-algorithm.mm
@@ -0,0 +1,97 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=debug.DumpTraversal -std=c++11 %s | FileCheck -check-prefix=DFS %s
+
+int a();
+int b();
+int c();
+
+int work();
+
+void test(id input) {
+  if (a()) {
+    if (a())
+      b();
+    else
+      c();
+  } else {
+    if (b())
+      a();
+    else
+      c();
+  }
+
+  if (a())
+    work();
+}
+
+// This ordering assumes that true cases happen before the false cases.
+
+// BFS: 10 IfStmt
+// BFS-NEXT: 11 IfStmt
+// BFS-NEXT: 16 IfStmt
+// BFS-NEXT: 22 IfStmt
+// BFS-NEXT: 22 IfStmt
+// BFS-NEXT: 22 IfStmt
+// BFS-NEXT: 22 IfStmt
+// BFS-NEXT: --END PATH--
+// BFS-NEXT: --END PATH--
+// BFS-NEXT: --END PATH--
+// BFS-NEXT: --END PATH--
+// BFS-NEXT: --END PATH--
+// BFS-NEXT: --END PATH--
+// BFS-NEXT: --END PATH--
+// BFS-NEXT: --END PATH--
+
+// And this ordering assumes that false cases happen before the true cases.
+
+// DFS: 10 IfStmt
+// DFS-NEXT: 16 IfStmt
+// DFS-NEXT: 22 IfStmt
+// DFS-NEXT: --END PATH--
+// DFS-NEXT: --END PATH--
+// DFS-NEXT: 22 IfStmt
+// DFS-NEXT: --END PATH--
+// DFS-NEXT: --END PATH--
+// DFS-NEXT: 11 IfStmt
+// DFS-NEXT: 22 IfStmt
+// DFS-NEXT: --END PATH--
+// DFS-NEXT: --END PATH--
+// DFS-NEXT: 22 IfStmt
+// DFS-NEXT: --END PATH--
+// DFS-NEXT: --END PATH--
+
+
+void testLoops(id input) {
+  while (a()) {
+    work();
+    work();
+    work();
+  }
+
+  for (int i = 0; i != b(); ++i) {
+    work();
+  }
+
+  for (id x in input) {
+    work();
+    work();
+    work();
+  }
+
+  int z[] = {1,2,3};
+  for (int y : z) {
+    work();
+    work();
+    work();
+  }
+}
+
+// BFS: 64 WhileStmt
+// BFS: 70 ForStmt
+// BFS-NOT-NEXT: ObjCForCollectionStmt
+// BFS: 74 ObjCForCollectionStmt
+// BFS: 81 CXXForRangeStmt
+
+// DFS: 64 While
+// DFS-NEXT: 70 ForStmt
+// DFS-NEXT: 74 ObjCForCollectionStmt
+// DFS-NEXT: 81 CXXForRangeStmt