[analyzer] exploded-graph-rewriter: Implement a single-path mode.

[NoQ]

Summary

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.

[Charusso]

Smart move! The left-most usually the shortest path, but what if not? I would calculate the length, other than that, cool. Thanks!

clang/test/Analysis/exploded-graph-rewriter/explorers.dot

+// 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;

clang/utils/analyzer/exploded-graph-rewriter.py

 
 
 #===-----------------------------------------------------------------------===#
 # Explorers know how to traverse the ExplodedGraph in a certain order.
 # They would invoke a Visitor on every node or edge they encounter.
 #===-----------------------------------------------------------------------===#
 
 
-# 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__()
 
     def explore(self, graph, visitor):
         visitor.visit_begin_graph(graph)
         for node in sorted(graph.nodes):
             logging.debug('Visiting ' + node)
             visitor.visit_node(graph.nodes[node])
             for succ in sorted(graph.nodes[node].successors):
                 logging.debug('Visiting edge: %s -> %s ' % (node, succ))
                 visitor.visit_edge(graph.nodes[node], graph.nodes[succ])
         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.
 #===-----------------------------------------------------------------------===#
 
 
 def main():
     parser = argparse.ArgumentParser()
     parser.add_argument('filename', type=str)
     parser.add_argument('-v', '--verbose', action='store_const',
                         dest='loglevel', const=logging.DEBUG,
                         default=logging.WARNING,
                         help='enable info prints')
     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')
     parser.add_argument('--gray', action='store_const', dest='gray',
                         const=True, default=False,
                         help='black-and-white mode')
     args = parser.parse_args()
     logging.basicConfig(level=args.loglevel)
 
     graph = ExplodedGraph()
     with open(args.filename) as fd:
         for raw_line in fd:
             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)
 
 
 if __name__ == '__main__':
     main()