Index: cfe/trunk/test/Analysis/exploded-graph-rewriter/edge.dot =================================================================== --- cfe/trunk/test/Analysis/exploded-graph-rewriter/edge.dot +++ cfe/trunk/test/Analysis/exploded-graph-rewriter/edge.dot @@ -0,0 +1,12 @@ +// RUN: %exploded_graph_rewriter %s | FileCheck %s + +Node0x1 [shape=record,label= + "{{ "node_id": 1, "pointer": "0x1", + "program_state": null, "program_points": []}\l}"]; + +// CHECK: Node0x1 -> Node0x2; +Node0x1 -> Node0x2; + +Node0x2 [shape=record,label= + "{{ "node_id": 2, "pointer": "0x2", + "program_state": null, "program_points": []}\l}"]; Index: cfe/trunk/test/Analysis/exploded-graph-rewriter/empty.dot =================================================================== --- cfe/trunk/test/Analysis/exploded-graph-rewriter/empty.dot +++ cfe/trunk/test/Analysis/exploded-graph-rewriter/empty.dot @@ -0,0 +1,9 @@ +// RUN: %exploded_graph_rewriter %s | FileCheck %s + +digraph "Exploded Graph" { + label="Exploded Graph"; +} + +// CHECK: digraph "ExplodedGraph" { +// CHECK-NEXT: label=""; +// CHECK-NEXT: } Index: cfe/trunk/test/Analysis/exploded-graph-rewriter/environment.dot =================================================================== --- cfe/trunk/test/Analysis/exploded-graph-rewriter/environment.dot +++ cfe/trunk/test/Analysis/exploded-graph-rewriter/environment.dot @@ -0,0 +1,50 @@ +// RUN: %exploded_graph_rewriter %s | FileCheck %s + +// CHECK: Environment: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME:
+// CHECK-SAME: #0 Call +// CHECK-SAME: +// CHECK-SAME: foo (line 4) +// CHECK-SAME:
+// CHECK-SAME: S5 +// CHECK-SAME: +// CHECK-SAME: bar() +// CHECK-SAME: +// CHECK-SAME: Unknown +// CHECK-SAME:
+Node0x1 [shape=record,label= + "{ + { "node_id": 1, + "pointer": "0x1", + "state_id": 2, + "program_points": [], + "program_state": { + "store": null, + "environment": [ + { + "location_context": "#0 Call", + "lctx_id": 3, + "calling": "foo", + "call_line": 4, + "items": [ + { + "stmt_id": 5, + "pretty": "bar()", + "value": "Unknown" + } + ] + } + ] + } + } +\l}"]; Index: cfe/trunk/test/Analysis/exploded-graph-rewriter/lit.local.cfg =================================================================== --- cfe/trunk/test/Analysis/exploded-graph-rewriter/lit.local.cfg +++ cfe/trunk/test/Analysis/exploded-graph-rewriter/lit.local.cfg @@ -0,0 +1,13 @@ +import lit.util +import lit.formats +import os + +use_lit_shell = os.environ.get("LIT_USE_INTERNAL_SHELL") +config.test_format = lit.formats.ShTest(use_lit_shell == "0") + +config.substitutions.append(('%exploded_graph_rewriter', + lit.util.which('exploded-graph-rewriter.py', + os.path.join(config.clang_src_dir, + 'utils', 'analyzer')))) + +config.suffixes = ['.dot'] Index: cfe/trunk/test/Analysis/exploded-graph-rewriter/program_points.dot =================================================================== --- cfe/trunk/test/Analysis/exploded-graph-rewriter/program_points.dot +++ cfe/trunk/test/Analysis/exploded-graph-rewriter/program_points.dot @@ -0,0 +1,60 @@ +// RUN: %exploded_graph_rewriter %s | FileCheck %s + +// CHECK: Program point: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME:
+// CHECK-SAME: - +// CHECK-SAME: +// CHECK-SAME: Edge +// CHECK-SAME: +// CHECK-SAME: [B0] -> [B1] +// CHECK-SAME:
+Node0x1 [shape=record,label= + "{ + { "node_id": 1, "pointer": "0x1", + "program_state": null, "program_points": [ + { + "kind": "Edge", + "src_id": 0, + "dst_id": 1, + "terminator": null, + "term_kind": null, + "tag": null } + ]} +\l}"]; + +// CHECK-NEXT: Program point: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME:
+// CHECK-SAME: (main file):4:5: +// CHECK-SAME: +// CHECK-SAME: DeclRefExpr +// CHECK-SAME: x
+Node0x2 [shape=record,label= + "{ + { "node_id": 2, "pointer": "0x2", + "program_state": null, "program_points": [ + { + "kind": "Statement", + "stmt_kind": "DeclRefExpr", + "stmd_id": 3, + "pointer": "0x3", + "pretty": "x", + "location": { + "line": 4, + "column": 5 + }, + "tag": null + } + ]} +\l}"]; Index: cfe/trunk/test/Analysis/exploded-graph-rewriter/store.dot =================================================================== --- cfe/trunk/test/Analysis/exploded-graph-rewriter/store.dot +++ cfe/trunk/test/Analysis/exploded-graph-rewriter/store.dot @@ -0,0 +1,42 @@ +// RUN: %exploded_graph_rewriter %s | FileCheck %s + +// CHECK: Store: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME: +// CHECK-SAME:
+// CHECK-SAME: x +// CHECK-SAME: +// CHECK-SAME: 0 +// CHECK-SAME: +// CHECK-SAME: (Default) +// CHECK-SAME: +// CHECK-SAME: Undefined +// CHECK-SAME:
+Node0x1 [shape=record,label= + "{ + { "node_id": 1, + "pointer": "0x1", + "state_id": 2, + "program_points": [], + "program_state": { + "environment": null, + "store": [ + { + "cluster": "x", + "items": [ + { + "kind": "Default", + "offset": 0, + "value": "Undefined" + } + ] + } + ] + } + } +\l}"]; Index: cfe/trunk/utils/analyzer/exploded-graph-rewriter.py =================================================================== --- cfe/trunk/utils/analyzer/exploded-graph-rewriter.py +++ cfe/trunk/utils/analyzer/exploded-graph-rewriter.py @@ -0,0 +1,398 @@ +#!/usr/bin/env python + +from __future__ import print_function + +import argparse +import collections +import json +import logging +import re + + +# A deserialized source location. +class SourceLocation(object): + def __init__(self, json_loc): + super(SourceLocation, self).__init__() + self.line = json_loc['line'] + self.col = json_loc['column'] + self.filename = json_loc['filename'] \ + if 'filename' in json_loc else '(main file)' + + +# A deserialized program point. +class ProgramPoint(object): + def __init__(self, json_pp): + super(ProgramPoint, self).__init__() + self.kind = json_pp['kind'] + self.tag = json_pp['tag'] + if self.kind == 'Edge': + self.src_id = json_pp['src_id'] + self.dst_id = json_pp['dst_id'] + elif self.kind == 'Statement': + self.stmt_kind = json_pp['stmt_kind'] + self.pointer = json_pp['pointer'] + self.pretty = json_pp['pretty'] + self.loc = SourceLocation(json_pp['location']) \ + if json_pp['location'] is not None else None + elif self.kind == 'BlockEntrance': + self.block_id = json_pp['block_id'] + + +# A value of a single expression in a deserialized Environment. +class EnvironmentBinding(object): + def __init__(self, json_eb): + super(EnvironmentBinding, self).__init__() + self.stmt_id = json_eb['stmt_id'] + self.pretty = json_eb['pretty'] + self.value = json_eb['value'] + + +# Deserialized description of a location context. +class LocationContext(object): + def __init__(self, json_frame): + super(LocationContext, self).__init__() + self.lctx_id = json_frame['lctx_id'] + self.caption = json_frame['location_context'] + self.decl = json_frame['calling'] + self.line = json_frame['call_line'] + + +# A group of deserialized Environment bindings that correspond to a specific +# location context. +class EnvironmentFrame(object): + def __init__(self, json_frame): + super(EnvironmentFrame, self).__init__() + self.location_context = LocationContext(json_frame) + self.bindings = [EnvironmentBinding(b) for b in json_frame['items']] \ + if json_frame['items'] is not None else [] + + +# A deserialized Environment. +class Environment(object): + def __init__(self, json_e): + super(Environment, self).__init__() + self.frames = [EnvironmentFrame(f) for f in json_e] + + +# A single binding in a deserialized RegionStore cluster. +class StoreBinding(object): + def __init__(self, json_sb): + super(StoreBinding, self).__init__() + self.kind = json_sb['kind'] + self.offset = json_sb['offset'] + self.value = json_sb['value'] + + +# A single cluster of the deserialized RegionStore. +class StoreCluster(object): + def __init__(self, json_sc): + super(StoreCluster, self).__init__() + self.base_region = json_sc['cluster'] + self.bindings = [StoreBinding(b) for b in json_sc['items']] + + +# A deserialized RegionStore. +class Store(object): + def __init__(self, json_s): + super(Store, self).__init__() + self.clusters = [StoreCluster(c) for c in json_s] + + +# A deserialized program state. +class ProgramState(object): + def __init__(self, state_id, json_ps): + super(ProgramState, self).__init__() + logging.debug('Adding ProgramState ' + str(state_id)) + + self.state_id = state_id + self.store = Store(json_ps['store']) \ + if json_ps['store'] is not None else None + self.environment = Environment(json_ps['environment']) \ + if json_ps['environment'] is not None else None + # TODO: Objects under construction. + # TODO: Constraint ranges. + # TODO: Dynamic types of objects. + # TODO: Checker messages. + + +# A deserialized exploded graph node. Has a default constructor because it +# may be referenced as part of an edge before its contents are deserialized, +# and in this moment we already need a room for predecessors and successors. +class ExplodedNode(object): + def __init__(self): + super(ExplodedNode, self).__init__() + self.predecessors = [] + self.successors = [] + + def construct(self, node_id, json_node): + logging.debug('Adding ' + node_id) + self.node_id = json_node['node_id'] + self.ptr = json_node['pointer'] + self.points = [ProgramPoint(p) for p in json_node['program_points']] + self.state = ProgramState(json_node['state_id'], + json_node['program_state']) \ + if json_node['program_state'] is not None else None + + assert self.node_name() == node_id + + def node_name(self): + return 'Node' + self.ptr + + +# A deserialized ExplodedGraph. Constructed by consuming a .dot file +# line-by-line. +class ExplodedGraph(object): + # Parse .dot files with regular expressions. + node_re = re.compile( + '^(Node0x[0-9a-f]*) \\[shape=record,.*label="{(.*)\\\\l}"\\];$') + edge_re = re.compile( + '^(Node0x[0-9a-f]*) -> (Node0x[0-9a-f]*);$') + + def __init__(self): + super(ExplodedGraph, self).__init__() + self.nodes = collections.defaultdict(ExplodedNode) + self.root_id = None + self.incomplete_line = '' + + def add_raw_line(self, raw_line): + if raw_line.startswith('//'): + return + + # Allow line breaks by waiting for ';'. This is not valid in + # a .dot file, but it is useful for writing tests. + if len(raw_line) > 0 and raw_line[-1] != ';': + self.incomplete_line += raw_line + return + raw_line = self.incomplete_line + raw_line + self.incomplete_line = '' + + # Apply regexps one by one to see if it's a node or an edge + # and extract contents if necessary. + logging.debug('Line: ' + raw_line) + result = self.edge_re.match(raw_line) + if result is not None: + logging.debug('Classified as edge line.') + pred = result.group(1) + succ = result.group(2) + self.nodes[pred].successors.append(succ) + self.nodes[succ].predecessors.append(pred) + return + result = self.node_re.match(raw_line) + if result is not None: + logging.debug('Classified as node line.') + node_id = result.group(1) + if len(self.nodes) == 0: + self.root_id = node_id + # Note: when writing tests you don't need to escape everything, + # even though in a valid dot file everything is escaped. + node_label = result.group(2).replace('\\l', '') \ + .replace(' ', '') \ + .replace('\\"', '"') \ + .replace('\\{', '{') \ + .replace('\\}', '}') \ + .replace('\\<', '\\\\<') \ + .replace('\\>', '\\\\>') \ + .rstrip(',') + logging.debug(node_label) + json_node = json.loads(node_label) + self.nodes[node_id].construct(node_id, json_node) + return + logging.debug('Skipping.') + + +# A visitor that dumps the ExplodedGraph into a DOT file with fancy HTML-based +# syntax highlighing. +class DotDumpVisitor(object): + def __init__(self): + super(DotDumpVisitor, self).__init__() + + @staticmethod + def _dump_raw(s): + print(s, end='') + + @staticmethod + def _dump(s): + print(s.replace('&', '&') + .replace('{', '\\{') + .replace('}', '\\}') + .replace('\\<', '<') + .replace('\\>', '>') + .replace('\\l', '
') + .replace('|', ''), end='') + + def visit_begin_graph(self, graph): + self._graph = graph + self._dump_raw('digraph "ExplodedGraph" {\n') + self._dump_raw('label="";\n') + + def visit_program_point(self, p): + if p.kind in ['Edge', 'BlockEntrance', 'BlockExit']: + color = 'gold3' + elif p.kind in ['PreStmtPurgeDeadSymbols', + 'PostStmtPurgeDeadSymbols']: + color = 'red' + elif p.kind in ['CallEnter', 'CallExitBegin', 'CallExitEnd']: + color = 'blue' + elif p.kind in ['Statement']: + color = 'cyan3' + else: + color = 'forestgreen' + + if p.kind == 'Statement': + if p.loc is not None: + self._dump('' + '%s:%s:%s:' + '' + '%s%s' + % (p.loc.filename, p.loc.line, + p.loc.col, color, p.stmt_kind, p.pretty)) + else: + self._dump('' + 'Invalid Source Location:' + '' + '%s%s' + % (color, p.stmt_kind, p.pretty)) + elif p.kind == 'Edge': + self._dump('-' + '' + '%s' + '[B%d] -\\> [B%d]' + % (color, p.kind, p.src_id, p.dst_id)) + else: + # TODO: Print more stuff for other kinds of points. + self._dump('-' + '' + '%s' + % (color, p.kind)) + + def visit_environment(self, e): + self._dump('') + + for f in e.frames: + self._dump('' + '' + % (f.location_context.caption, + f.location_context.decl, + ('(line %s)' % f.location_context.line) + if f.location_context.line is not None else '')) + for b in f.bindings: + self._dump('' + '' + '' + % (b.stmt_id, b.pretty, b.value)) + + self._dump('
%s%s ' + '%s
S%s%s%s
') + + def visit_store(self, s): + self._dump('') + + for c in s.clusters: + for b in c.bindings: + self._dump('' + '' + '' + '' + % (c.base_region, b.offset, + '(Default)' if b.kind == 'Default' + else '', + b.value)) + + self._dump('
%s%s%s%s
') + + def visit_state(self, s): + self._dump('' + 'Store: ') + if s.store is None: + self._dump(' Nothing!') + else: + self._dump('' + '') + self.visit_store(s.store) + + self._dump('
' + '' + 'Environment: ') + if s.environment is None: + self._dump(' Nothing!') + else: + self._dump('' + '') + self.visit_environment(s.environment) + + self._dump('') + + def visit_node(self, node): + self._dump('%s [shape=record,label=<' + % (node.node_name())) + + self._dump('' + % (node.node_id, node.ptr, node.state.state_id + if node.state is not None else 'Unspecified')) + self._dump('') + else: + self._dump('Program point:') + self._dump('') + + if node.state is not None: + self._dump('
') + self.visit_state(node.state) + self._dump_raw('
Node %d (%s) - ' + 'State %s
') + if len(node.points) > 1: + self._dump('Program points:
' + '') + for p in node.points: + self.visit_program_point(p) + self._dump('
>];\n') + + def visit_edge(self, pred, succ): + self._dump_raw('%s -> %s;\n' % (pred.node_name(), succ.node_name())) + + def visit_end_of_graph(self): + self._dump_raw('}\n') + + +# A class that encapsulates traversal of the ExplodedGraph. Different explorer +# kinds could potentially traverse specific sub-graphs. +class Explorer(object): + def __init__(self): + super(Explorer, 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() + + +def main(): + parser = argparse.ArgumentParser() + parser.add_argument('filename', type=str) + parser.add_argument('-d', '--debug', action='store_const', dest='loglevel', + const=logging.DEBUG, default=logging.WARNING, + help='enable debug prints') + parser.add_argument('-v', '--verbose', action='store_const', + dest='loglevel', const=logging.INFO, + default=logging.WARNING, + help='enable info prints') + 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 = Explorer() + visitor = DotDumpVisitor() + explorer.explore(graph, visitor) + + +if __name__ == '__main__': + main()