[analyzer] exploded-graph-rewriter: Add support for dynamic types.

[NoQ]

Summary

Slightly cleanup emission of <hr />s and unhardcode the title for generic maps :/

[Charusso]

Nice, the end of that huge work is getting closer. Thanks!

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

229 ↗

(On Diff #207418)

Hm, I would avoid that over-complicated code, but because most likely it is remain like that for the next decade, I see no problem here.

[NoQ]

Bring back a few forgotten <hr />s.

[NoQ]

Remove the TODO.

[NoQ]

Ugh, forgot to git add the actual test.

[NoQ]

rC364871.

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

  "{
     { "node_id": 1,
       "pointer": "0x1",
       "state_id": 2,
       "program_points": [],
       "program_state": {
         "store": null,
         "environment": null,
+        "dynamic_types": null,
         "constraints": [
           { "symbol": "reg_$0<x>", "range": "{ [0, 0] }" }
         ]
       }
     }
 \l}"];

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

 // RUN: %exploded_graph_rewriter -d %s | FileCheck %s
 
 // FIXME: Substitution doesn't seem to work on Windows.
 // UNSUPPORTED: system-windows
 
 Node0x1 [shape=record,label=
  "{
     { "node_id": 1,
       "pointer": "0x1",
       "state_id": 2,
       "program_points": [],
       "program_state": {
         "store": null,
         "environment": null,
+        "dynamic_types": null,
         "constraints": [
           { "symbol": "reg_$0<x>", "range": "{ [0, 10] }" }
         ]
       }
     }
 \l}"];
 
 Node0x1 -> Node0x3;

  "{
     { "node_id": 3,
       "pointer": "0x3",
       "state_id": 4,
       "program_points": [],
       "program_state": {
         "store": null,
         "environment": null,
+        "dynamic_types": null,
         "constraints": [
           { "symbol": "reg_$0<x>", "range": "{ [0, 5] }" }
         ]
       }
     }
 \l}"];
 
 Node0x3 -> Node0x5;
 
 Node0x5 [shape=record,label=
  "{
     { "node_id": 5,
       "pointer": "0x5",
       "state_id": 6,
       "program_points": [],
       "program_state": {
         "store": null,
         "environment": null,
-        "constraints": null
+        "constraints": null,
+        "dynamic_types": null
       }
     }
 \l}"];

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

  "{
     { "node_id": 1,
       "pointer": "0x1",
       "state_id": 2,
       "program_points": [],
       "program_state": {
         "store": null,
         "constraints": null,
+        "dynamic_types": null,
         "environment": {
           "pointer": "0x2",
           "items": [
             {
               "location_context": "#0 Call",
               "lctx_id": 3,
               "calling": "foo",
               "call_line": 4,

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

 // RUN: %exploded_graph_rewriter -d %s | FileCheck %s
 
 // FIXME: Substitution doesn't seem to work on Windows.
 // UNSUPPORTED: system-windows
 
 // No diffs on the first node, nothing to check.
 Node0x1 [shape=record,label=
  "{
     { "node_id": 1,
       "pointer": "0x1",
       "state_id": 2,
       "program_points": [],
       "program_state": {
         "store": null,
         "constraints": null,
+        "dynamic_types": null,
         "environment": {
           "pointer": "0x2",
           "items": [
             {
               "location_context": "#0 Call",
               "lctx_id": 3,
               "calling": "foo",
               "call_line": 4,

  "{
     { "node_id": 6,
       "pointer": "0x6",
       "state_id": 7,
       "program_points": [],
       "program_state": {
         "store": null,
         "constraints": null,
+        "dynamic_types": null,
         "environment": {
           "pointer": "0x2",
           "items": [
             {
               "location_context": "#0 Call",
               "lctx_id": 3,
               "calling": "foo",
               "call_line": 4,

  "{
     { "node_id": 9,
       "pointer": "0x9",
       "state_id": 7,
       "program_points": [],
       "program_state": {
         "store": null,
         "constraints": null,
+        "dynamic_types": null,
         "environment": {
           "pointer": "0x2",
           "items": [
             {
               "location_context": "#0 Call",
               "lctx_id": 3,
               "calling": "foo",
               "call_line": 4,

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

  "{
     { "node_id": 1,
       "pointer": "0x1",
       "state_id": 2,
       "program_points": [],
       "program_state": {
         "environment": null,
         "constraints": null,
+        "dynamic_types": null,
         "store": {
           "pointer": "0x2",
           "items": [
             {
               "cluster": "x",
               "pointer": "0x3",
               "items": [
                 {

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

 // RUN: %exploded_graph_rewriter -d %s | FileCheck %s
 
 // FIXME: Substitution doesn't seem to work on Windows.
 // UNSUPPORTED: system-windows
 
 Node0x1 [shape=record,label=
  "{
     { "node_id": 1,
       "pointer": "0x1",
       "state_id": 2,
       "program_points": [],
       "program_state": {
         "environment": null,
         "constraints": null,
+        "dynamic_types": null,
         "store": {
           "pointer": "0x2",
           "items": [
             {
               "cluster": "x",
               "pointer": "0x3",
               "items": [
                 {

  "{
     { "node_id": 4,
       "pointer": "0x4",
       "state_id": 5,
       "program_points": [],
       "program_state": {
         "environment": null,
         "constraints": null,
+        "dynamic_types": null,
         "store": {
           "pointer": "0x5",
           "items": [
             {
               "cluster": "x",
               "pointer": "0x3",
               "items": [
                 {

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

 def diff_dicts(curr, prev):
     removed = [k for k in prev if k not in curr or curr[k] != prev[k]]
     added = [k for k in curr if k not in prev or curr[k] != prev[k]]
     return (removed, added)
 
 
 # Represents any program state trait that is a dictionary of key-value pairs.
 class GenericMap(object):
-    def __init__(self, generic_map):
-        self.generic_map = generic_map
+    def __init__(self, items):
+        self.generic_map = collections.OrderedDict(items)
 
     def diff(self, prev):
         return diff_dicts(self.generic_map, prev.generic_map)
 
     def is_different(self, prev):
         removed, added = self.diff(prev)
         return len(removed) != 0 or len(added) != 0
 
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
-        self.constraints = GenericMap(collections.OrderedDict([
+        self.constraints = GenericMap([
             (c['symbol'], c['range']) for c in json_ps['constraints']
-        ])) if json_ps['constraints'] is not None else None
+        ]) if json_ps['constraints'] is not None else None
+        self.dynamic_types = GenericMap([
+                (t['region'], '%s%s' % (t['dyn_type'],
+                                        ' (or a sub-class)'
+                                        if t['sub_classable'] else ''))
+                for t in json_ps['dynamic_types']]) \
+            if json_ps['dynamic_types'] is not None else None
+
         # TODO: Objects under construction.
-        # 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):
def visit_environment(self, e, prev_e=None):
             for f in e.frames:
                 dump_location_context(f.location_context)
                 for b in f.bindings:
                     dump_binding(f, b)
 
         self._dump('</table>')
 
     def visit_environment_in_state(self, s, prev_s=None):
-        self._dump('<tr><td align="left">'
-                   '<b>Environment: </b>')
+        self._dump('<hr /><tr><td align="left"><b>Environment: </b>')
         if s.environment is None:
             self._dump('<i> Nothing!</i>')
         else:
             if prev_s is not None and prev_s.environment is not None:
                 if s.environment.is_different(prev_s.environment):
                     self._dump('</td></tr><tr><td align="left">')
                     self.visit_environment(s.environment, prev_s.environment)
                 else:
def visit_store(self, s, prev_s=None):
         else:
             for c in s.clusters:
                 for b in s.clusters[c].bindings:
                     dump_binding(s, c, b)
 
         self._dump('</table>')
 
     def visit_store_in_state(self, s, prev_s=None):
-        self._dump('<tr><td align="left"><b>Store: </b>')
+        self._dump('<hr /><tr><td align="left"><b>Store: </b>')
         if s.store is None:
             self._dump('<i> Nothing!</i>')
         else:
             if prev_s is not None and prev_s.store is not None:
                 if s.store.is_different(prev_s.store):
                     self._dump('</td></tr><tr><td align="left">')
                     self.visit_store(s.store, prev_s.store)
                 else:
def visit_generic_map(self, m, prev_m=None):
             for k in added:
                 dump_pair(m, k, True)
         else:
             for k in m.generic_map:
                 dump_pair(m, k, None)
 
         self._dump('</table>')
 
-    def visit_generic_map_in_state(self, selector, s, prev_s=None):
-        self._dump('<tr><td align="left">'
-                   '<b>Ranges: </b>')
+    def visit_generic_map_in_state(self, selector, title, s, prev_s=None):
         m = getattr(s, selector)
+        prev_m = getattr(prev_s, selector) if prev_s is not None else None
+        if m is None and prev_m is None:
+            return
+
+        self._dump('<hr />')
+        self._dump('<tr><td align="left">'
+                   '<b>%s: </b>' % title)
         if m is None:
             self._dump('<i> Nothing!</i>')
         else:
-            prev_m = None
             if prev_s is not None:
-                prev_m = getattr(prev_s, selector)
                 if prev_m is not None:
                     if m.is_different(prev_m):
                         self._dump('</td></tr><tr><td align="left">')
                         self.visit_generic_map(m, prev_m)
                     else:
                         self._dump('<i> No changes!</i>')
             if prev_m is None:
                 self._dump('</td></tr><tr><td align="left">')
                 self.visit_generic_map(m)
         self._dump('</td></tr>')
 
     def visit_state(self, s, prev_s):
         self.visit_store_in_state(s, prev_s)
-        self._dump('<hr />')
         self.visit_environment_in_state(s, prev_s)
-        self._dump('<hr />')
-        self.visit_generic_map_in_state('constraints', s, prev_s)
+        self.visit_generic_map_in_state('constraints', 'Ranges',
+                                        s, prev_s)
+        self.visit_generic_map_in_state('dynamic_types', 'Dynamic Types',
+                                        s, prev_s)
 
     def visit_node(self, node):
         self._dump('%s [shape=record,label=<<table border="0">'
                    % (node.node_name()))
 
         self._dump('<tr><td bgcolor="grey"><b>Node %d (%s) - '
                    'State %s</b></td></tr>'
                    % (node.node_id, node.ptr, node.state.state_id
                       if node.state is not None else 'Unspecified'))
         self._dump('<tr><td align="left" width="0">')
         if len(node.points) > 1:
             self._dump('<b>Program points:</b></td></tr>')
         else:
             self._dump('<b>Program point:</b></td></tr>')
         self._dump('<tr><td align="left" width="0">'
                    '<table border="0" align="left" width="0">')
         for p in node.points:
             self.visit_program_point(p)
         self._dump('</table></td></tr>')
 
         if node.state is not None:
-            self._dump('<hr />')
             prev_s = None
             # Do diffs only when we have a unique predecessor.
             # Don't do diffs on the leaf nodes because they're
             # the important ones.
             if self._do_diffs and len(node.predecessors) == 1 \
                and len(node.successors) > 0:
                 prev_s = self._graph.nodes[node.predecessors[0]].state
             self.visit_state(node.state, prev_s)