[analyzer] Add a test that we are, in fact, doing a DFS on the ExplodedGraph.

Previously:
...the comment said DFS...
...the WorkList being instantiated said BFS...
...and the implementation was actually DFS...
...due to an unintentional change in 2010...
...and everything kept working anyway.

This fixes our std::deque implementation of BFS, but switches back to a
SmallVector-based implementation of DFS.

We should probably still investigate the ramifications of DFS vs. BFS,
especially for large functions (and especially when we hit our block path
limit), since this might completely change our memory use. It can also mask
some bugs and reveal others depending on when we halt analysis. But at least
we will not have this kind of little mistake creep in again.

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

1 files changed, 97 insertions, 0 deletions

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