[analyzer] exploded-graph-rewriter: Implement manual graph trimming.

[NoQ]

Summary

When -trim-egraph is unavailable (say, when you're debugging a crash on a real-world code that takes too long to reduce), it makes sense to view the untrimmed graph up to the crashing node's predecessor, then dump the ID (or a pointer) of the node in the attached debugger, and then trim the dumped graph in order to keep only paths from the root to the node.

Implement the last part of that plan. Now you can do:

$ exploded-graph-rewriter.py ExprEngine.dot --to 0x12229acd0

And it'll chop out the unnecessary chunks of the graph. You can also specify multiple nodes and you can specify nodes by stable IDs rather than by pointers.

[Charusso]

It is a great idea, thanks!

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

918 ↗

(On Diff #211985)

Extra comma at (eg.,

989 ↗

(On Diff #211985)

only display for consistency with the above arguments.

cfe/trunk/test/Analysis/exploded-graph-rewriter/trimmers.dot

 // RUN: %exploded_graph_rewriter %s \
-// RUN:     | FileCheck %s -check-prefixes=CHECK,BASIC
+// RUN:     | FileCheck %s -check-prefixes=ONE,TWO,THREE,FOUR
 // RUN: %exploded_graph_rewriter -s %s \
-// RUN:     | FileCheck %s -check-prefixes=CHECK,SINGLE
+// RUN:     | FileCheck %s -check-prefixes=ONE,TWO,NOTHREE,FOUR
+// RUN: %exploded_graph_rewriter --to=0x2 %s \
+// RUN:     | FileCheck %s -check-prefixes=ONE,TWO,NOTHREE,NOFOUR
+// RUN: %exploded_graph_rewriter --to 2 %s \
+// RUN:     | FileCheck %s -check-prefixes=ONE,TWO,NOTHREE,NOFOUR
+// RUN: %exploded_graph_rewriter --to 2,3 %s \
+// RUN:     | FileCheck %s -check-prefixes=ONE,TWO,THREE,NOFOUR
+// RUN: %exploded_graph_rewriter --to 4 %s \
+// RUN:     | FileCheck %s -check-prefixes=ONE,TWO,THREE,FOUR
+// RUN: %exploded_graph_rewriter --to 4 -s %s \
+// RUN:     | FileCheck %s -check-prefixes=ONE,TWO,NOTHREE,FOUR
 
 // 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;
+
+// ONE: Node0x1
+// NOTONE-NOT: Node0x1
+// TWO: Node0x2
+// NOTTWO-NOT: Node0x2
+// THREE: Node0x3
+// NOTTHREE-NOT: Node0x3
+// FOUR: Node0x4
+// NOTFOUR-NOT: Node0x4

cfe/trunk/utils/analyzer/exploded-graph-rewriter.py

def trim(self, graph):
                     break
                 node_id = succ_id
             else:
                 break
         graph.nodes = {node_id: graph.nodes[node_id]
                        for node_id in visited_nodes}
 
 
+# TargetedTrimmer keeps paths that lead to specific nodes and discards all
+# other paths. Useful when you cannot use -trim-egraph (e.g. when debugging
+# a crash).
+class TargetedTrimmer(object):
+    def __init__(self, target_nodes):
+        super(TargetedTrimmer, self).__init__()
+        self._target_nodes = target_nodes
+
+    @staticmethod
+    def parse_target_node(node, graph):
+        if node.startswith('0x'):
+            ret = 'Node' + node
+            assert ret in graph.nodes
+            return ret
+        else:
+            for other_id in graph.nodes:
+                other = graph.nodes[other_id]
+                if other.node_id == int(node):
+                    return other_id
+
+    @staticmethod
+    def parse_target_nodes(target_nodes, graph):
+        return [TargetedTrimmer.parse_target_node(node, graph)
+                for node in target_nodes.split(',')]
+
+    def trim(self, graph):
+        queue = self._target_nodes
+        visited_nodes = set()
+
+        while len(queue) > 0:
+            node_id = queue.pop()
+            visited_nodes.add(node_id)
+            node = graph.nodes[node_id]
+            for pred_id in node.predecessors:
+                if pred_id not in visited_nodes:
+                    queue.append(pred_id)
+        graph.nodes = {node_id: graph.nodes[node_id]
+                       for node_id in visited_nodes}
+        for node_id in graph.nodes:
+            node = graph.nodes[node_id]
+            node.successors = [succ_id for succ_id in node.successors
+                               if succ_id in visited_nodes]
+            node.predecessors = [succ_id for succ_id in node.predecessors
+                                 if succ_id in visited_nodes]
+
+
 #===-----------------------------------------------------------------------===#
 # The entry point to the script.
 #===-----------------------------------------------------------------------===#
 
 
 def main():
     parser = argparse.ArgumentParser(
         description='Display and manipulate Exploded Graph dumps.')
def main():
     parser.add_argument('-t', '--topology', action='store_const',
                         dest='topology', const=True, default=False,
                         help='only display program points, omit 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('--to', type=str, default=None,
+                        help='only display execution paths from the root '
+                             'to the given comma-separated list of nodes '
+                             'identified by a pointer or a stable ID; '
+                             'compatible with --single-path')
     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')
     parser.add_argument('--dump-dot-only', action='store_const',
                         dest='dump_dot_only', const=True, default=False,
                         help='instead of writing an HTML file and immediately '
                              'displaying it, dump the rewritten dot file '
                              'to stdout')
     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)
 
     trimmers = []
+    if args.to is not None:
+        trimmers.append(TargetedTrimmer(
+            TargetedTrimmer.parse_target_nodes(args.to, graph)))
     if args.single_path:
         trimmers.append(SinglePathTrimmer())
 
     explorer = BasicExplorer()
 
     visitor = DotDumpVisitor(args.diff, args.dark, args.gray, args.topology,
                              args.dump_dot_only)
 
     for trimmer in trimmers:
         trimmer.trim(graph)
 
     explorer.explore(graph, visitor)
 
 
 if __name__ == '__main__':
     main()