From c7bc10fea93b960ec0cb1f38a09217f0f87c104e Mon Sep 17 00:00:00 2001
From: Artem Dergachev <artem.dergachev@gmail.com>
Date: Mon, 8 Jul 2019 23:54:11 +0000
Subject: [PATCH] [analyzer] exploded-graph-rewriter: Implement a single-path
 mode.

Instead of rewriting the whole graph, rewrite the leftmost path in the
graph. Useful for trimmed graphs that are still too large to display due
to multiple equivalent reports mixed into them.

Differential Revision: https://reviews.llvm.org/D64263

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@365409 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../exploded-graph-rewriter/explorers.dot     | 37 ++++++++++++++++
 utils/analyzer/exploded-graph-rewriter.py     | 44 +++++++++++++++++--
 2 files changed, 78 insertions(+), 3 deletions(-)
 create mode 100644 test/Analysis/exploded-graph-rewriter/explorers.dot

diff --git a/test/Analysis/exploded-graph-rewriter/explorers.dot b/test/Analysis/exploded-graph-rewriter/explorers.dot
new file mode 100644
index 0000000000..226c63911c
--- /dev/null
+++ b/test/Analysis/exploded-graph-rewriter/explorers.dot
@@ -0,0 +1,37 @@
+// RUN: %exploded_graph_rewriter %s \
+// RUN:     | FileCheck %s -check-prefixes=CHECK,BASIC
+// RUN: %exploded_graph_rewriter -s %s \
+// RUN:     | FileCheck %s -check-prefixes=CHECK,SINGLE
+
+// FIXME: Substitution doesn't seem to work on Windows.
+// UNSUPPORTED: system-windows
+
+Node0x1 [shape=record,label=
+ "{{ "node_id": 1, "pointer": "0x1", "has_report": false, "is_sink": false,
+      "program_state": null, "program_points": []}\l}"];
+
+Node0x2 [shape=record,label=
+ "{{ "node_id": 2, "pointer": "0x2", "has_report": false, "is_sink": false,
+      "program_state": null, "program_points": []}\l}"];
+
+Node0x3 [shape=record,label=
+ "{{ "node_id": 3, "pointer": "0x3", "has_report": false, "is_sink": false,
+      "program_state": null, "program_points": []}\l}"];
+
+Node0x4 [shape=record,label=
+ "{{ "node_id": 4, "pointer": "0x4", "has_report": false, "is_sink": false,
+      "program_state": null, "program_points": []}\l}"];
+
+// CHECK: Node0x1 -> Node0x2;
+Node0x1 -> Node0x2;
+
+// BASIC: Node0x1 -> Node0x3;
+// SINGLE-NOT: Node0x1 -> Node0x3;
+Node0x1 -> Node0x3;
+
+// CHECK: Node0x2 -> Node0x4;
+Node0x2 -> Node0x4;
+
+// BASIC: Node0x3 -> Node0x4;
+// SINGLE-NOT: Node0x3 -> Node0x4;
+Node0x3 -> Node0x4;
diff --git a/utils/analyzer/exploded-graph-rewriter.py b/utils/analyzer/exploded-graph-rewriter.py
index b78789f0b6..3ff9e5b93f 100755
--- a/utils/analyzer/exploded-graph-rewriter.py
+++ b/utils/analyzer/exploded-graph-rewriter.py
@@ -804,8 +804,7 @@ class DotDumpVisitor(object):
 #===-----------------------------------------------------------------------===#
 
 
-# A class that encapsulates traversal of the ExplodedGraph. Different explorer
-# kinds could potentially traverse specific sub-graphs.
+# BasicExplorer explores the whole graph in no particular order.
 class BasicExplorer(object):
     def __init__(self):
         super(BasicExplorer, self).__init__()
@@ -821,6 +820,39 @@ class BasicExplorer(object):
         visitor.visit_end_of_graph()
 
 
+# SinglePathExplorer traverses only a single path - the leftmost path
+# from the root. Useful when the trimmed graph is still too large
+# due to a large amount of equivalent reports.
+class SinglePathExplorer(object):
+    def __init__(self):
+        super(SinglePathExplorer, self).__init__()
+
+    def explore(self, graph, visitor):
+        visitor.visit_begin_graph(graph)
+
+        # Keep track of visited nodes in order to avoid loops.
+        visited = set()
+        node_id = graph.root_id
+        while True:
+            visited.add(node_id)
+            node = graph.nodes[node_id]
+            logging.debug('Visiting ' + node_id)
+            visitor.visit_node(node)
+            if len(node.successors) == 0:
+                break
+
+            succ_id = node.successors[0]
+            succ = graph.nodes[succ_id]
+            logging.debug('Visiting edge: %s -> %s ' % (node_id, succ_id))
+            visitor.visit_edge(node, succ)
+            if succ_id in visited:
+                break
+
+            node_id = succ_id
+
+        visitor.visit_end_of_graph()
+
+
 #===-----------------------------------------------------------------------===#
 # The entry point to the script.
 #===-----------------------------------------------------------------------===#
@@ -836,6 +868,11 @@ def main():
     parser.add_argument('-d', '--diff', action='store_const', dest='diff',
                         const=True, default=False,
                         help='display differences between states')
+    parser.add_argument('-s', '--single-path', action='store_const',
+                        dest='single_path', const=True, default=False,
+                        help='only display the leftmost path in the graph '
+                             '(useful for trimmed graphs that still '
+                             'branch too much)')
     parser.add_argument('--dark', action='store_const', dest='dark',
                         const=True, default=False,
                         help='dark mode')
@@ -851,8 +888,9 @@ def main():
             raw_line = raw_line.strip()
             graph.add_raw_line(raw_line)
 
-    explorer = BasicExplorer()
+    explorer = SinglePathExplorer() if args.single_path else BasicExplorer()
     visitor = DotDumpVisitor(args.diff, args.dark, args.gray)
+
     explorer.explore(graph, visitor)
 
 
-- 
2.40.0