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

[NoQ]

Summary

Implement a mode in which the rewriter prints differences between adjacent program states rather than the whole states. The whole state is still printed for nodes with multiple predecessors (because merge diffs were annoying to implement and it's still nice to have the full state occasionally) and for leaf nodes (because they're the important ones).

The diffs are computed "semantically" as opposed to plain text diffs. I.e., the diff algorithm is hand-crafted separately for every state trait, taking the underlying data structures into account. This is especially nice for Environment because textual diffs would have been terrible. This, of course, produces quite some boilerplate, but i think it's isolated enough to not bother me that much.

[NoQ]

I'll add some tests as soon as i'm sure tests for this thing actually work (by landing D62638).

[NoQ]

Remove "-" from program point dumps because it resembles a removal marker in diffs.

[Charusso]

In D62761#1525917, @NoQ wrote:

Remove "-" from program point dumps because it resembles a removal marker in diffs.

Could you add an image? I have not seen any problematic stuff, just that.

[NoQ]

In D62761#1525923, @Charusso wrote:

In D62761#1525917, @NoQ wrote:

Remove "-" from program point dumps because it resembles a removal marker in diffs.

Could you add an image? I have not seen any problematic stuff, just that.

The minus signs in "Program points: - one - two - three" are confusing.

[Charusso]

I asked for the new behavior, but I think it should be cool.

[NoQ]

In D62761#1539137, @Charusso wrote:

I asked for the new behavior, but I think it should be cool.

The new behavior is on the original screenshot, i just uploaded the wrong patch initially >.<

[Charusso]

In D62761#1539143, @NoQ wrote:

In D62761#1539137, @Charusso wrote:

I asked for the new behavior, but I think it should be cool.

The new behavior is on the original screenshot, i just uploaded the wrong patch initially >.<

No problem, thanks for the screenshot and for the clarification!

[NoQ]

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

180–193

This is broken due to possible collisions in cluster keys (eg., two variables with the same name but different scopes).
I guess i'll have to add a unique key to the cluster dump, i.e., a MemRegion pointer.

[Charusso]

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

180–193

It is a good idea, thanks for fixing these errors!

[NoQ]

Add tests, rebase.

[Charusso]

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

287

Ugh, wait with that a little-bit. I have forgot to create a patch! We have to escape the escapes.
E.g. "\x42" -> "\\x42".

[NoQ]

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

287

Yay!

[Charusso]

Thanks for the main development! Could I start to reduce the size with my SVG-magic? What do you think about make it more SVG-based on the styling side?

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

386

Good catch!

[NoQ]

Don't try to sneak in an unrelated change.

clang/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,
+        "environment": [
+          {
+            "location_context": "#0 Call",
+            "lctx_id": 3,
+            "calling": "foo",
+            "call_line": 4,
+            "items": [
+              {
+                "stmt_id": 5,
+                "pretty": "bar()",
+                "value": "Unknown"
+              }
+            ]
+          }
+        ]
+      }
+    }
+\l}"];
+
+Node0x1 -> Node0x6;
+
+// CHECK: Node0x6 [
+// CHECK-SAME: <tr>
+// CHECK-SAME:   <td><font color="red">-</font></td>
+// CHECK-SAME:   <td align="left"><i>S5</i></td>
+// CHECK-SAME:   <td align="left">bar()</td>
+// CHECK-SAME:   <td align="left">Unknown</td>
+// CHECK-SAME: </tr>
+// CHECK-SAME: <tr>
+// CHECK-SAME:   <td><font color="forestgreen">+</font></td>
+// CHECK-SAME:   <td align="left"><i>S9</i></td>
+// CHECK-SAME:   <td align="left">baz()</td>
+// CHECK-SAME:   <td align="left">Undefined</td>
+// CHECK-SAME: </tr>
+Node0x6 [shape=record,label=
+ "{
+    { "node_id": 6,
+      "pointer": "0x6",
+      "state_id": 7,
+      "program_points": [],
+      "program_state": {
+        "store": null,
+        "environment": [
+          {
+            "location_context": "#0 Call",
+            "lctx_id": 3,
+            "calling": "foo",
+            "call_line": 4,
+            "items": [
+              {
+                "stmt_id": 9,
+                "pretty": "baz()",
+                "value": "Undefined"
+              }
+            ]
+          }
+        ]
+      }
+    }
+\l}"];
+
+Node0x6 -> Node0x9;
+// Make sure that the last node in the path is not diffed.
+// CHECK: Node0x9 [
+// CHECK-SAME: <tr>
+// CHECK-SAME:   <td></td>
+// CHECK-SAME:   <td align="left"><i>S9</i></td>
+// CHECK-SAME:   <td align="left">baz()</td>
+// CHECK-SAME:   <td align="left">Undefined</td>
+// CHECK-SAME: </tr>
+Node0x9 [shape=record,label=
+ "{
+    { "node_id": 9,
+      "pointer": "0x9",
+      "state_id": 7,
+      "program_points": [],
+      "program_state": {
+        "store": null,
+        "environment": [
+          {
+            "location_context": "#0 Call",
+            "lctx_id": 3,
+            "calling": "foo",
+            "call_line": 4,
+            "items": [
+              {
+                "stmt_id": 9,
+                "pretty": "baz()",
+                "value": "Undefined"
+              }
+            ]
+          }
+        ]
+      }
+    }
+\l}"];

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

 // RUN: %exploded_graph_rewriter %s | FileCheck %s
 
 // FIXME: Substitution doesn't seem to work on Windows.
 // UNSUPPORTED: system-windows
 
 // CHECK: <b>Program point:</b>
 // CHECK-SAME: <table border="0" align="left" width="0">
 // CHECK-SAME:   <tr>
 // CHECK-SAME:     <td width="0">
-// CHECK-SAME:       -
 // CHECK-SAME:     </td>
 // CHECK-SAME:     <td align="left" width="0">
 // CHECK-SAME:       <font color="gold3">Edge</font>
 // CHECK-SAME:     </td>
 // CHECK-SAME:     <td align="left">
 // CHECK-SAME:     [B0] -&gt; [B1]
 // CHECK-SAME:     </td>
 // CHECK-SAME:   </tr>

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

"{
       "pointer": "0x1",
       "state_id": 2,
       "program_points": [],
       "program_state": {
         "environment": null,
         "store": [
           {
             "cluster": "x",
+            "pointer": "0x3",
             "items": [
               {
                 "kind": "Default",
                 "offset": 0,
                 "value": "Undefined"
               }
             ]
           }
         ]
       }
     }
 \l}"];

clang/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,
+        "store": [
+          {
+            "cluster": "x",
+            "pointer": "0x3",
+            "items": [
+              {
+                "kind": "Default",
+                "offset": 0,
+                "value": "Undefined"
+              }
+            ]
+          }
+        ]
+      }
+    }
+\l}"];
+
+Node0x1 -> Node0x4;
+
+// CHECK: Node0x4 [
+// CHECK-SAME: <tr>
+// CHECK-SAME:   <td><font color="red">-</font></td>
+// CHECK-SAME:   <td align="left">x</td><td align="left">0</td>
+// CHECK-SAME:   <td align="left">(<i>Default</i>)</td>
+// CHECK-SAME:   <td align="left">Undefined</td>
+// CHECK-SAME: </tr>
+// CHECK-SAME: <tr>
+// CHECK-SAME:   <td><font color="forestgreen">+</font></td>
+// CHECK-SAME:   <td align="left">x</td>
+// CHECK-SAME:   <td align="left">0</td>
+// CHECK-SAME:   <td align="left">(<i>Default</i>)</td>
+// CHECK-SAME:   <td align="left">Unknown</td>
+// CHECK-SAME: </tr>
+Node0x4 [shape=record,label=
+ "{
+    { "node_id": 4,
+      "pointer": "0x4",
+      "state_id": 5,
+      "program_points": [],
+      "program_state": {
+        "environment": null,
+        "store": [
+          {
+            "cluster": "x",
+            "pointer": "0x3",
+            "items": [
+              {
+                "kind": "Default",
+                "offset": 0,
+                "value": "Unknown"
+              }
+            ]
+          }
+        ]
+      }
+    }
+\l}"];
+
+Node0x4 -> Node0x6;
+
+Node0x6 [shape=record,label=
+ "{
+    { "node_id": 6,
+      "pointer": "0x6",
+      "state_id": 7,
+      "program_points": [],
+      "program_state": null
+    }
+\l}"];

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

 
 import argparse
 import collections
 import json
 import logging
 import re
 
 
+# A helper function for finding the difference between two dictionaries.
+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)
+
+
 # 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)'
def __init__(self, json_pp):
             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']
+# A single expression acting as a key in a deserialized Environment.
+class EnvironmentBindingKey(object):
+    def __init__(self, json_ek):
+        super(EnvironmentBindingKey, self).__init__()
+        self.stmt_id = json_ek['stmt_id']
+        self.pretty = json_ek['pretty']
+
+    def _key(self):
+        return self.stmt_id
+
+    def __eq__(self, other):
+        return self._key() == other._key()
+
+    def __hash__(self):
+        return hash(self._key())
 
 
 # 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']
 
+    def _key(self):
+        return self.lctx_id
+
+    def __eq__(self, other):
+        return self._key() == other._key()
+
+    def __hash__(self):
+        return hash(self._key())
+
 
 # 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 []
+        self.bindings = collections.OrderedDict(
+            [(EnvironmentBindingKey(b),
+              b['value']) for b in json_frame['items']]
+            if json_frame['items'] is not None else [])
+
+    def diff_bindings(self, prev):
+        return diff_dicts(self.bindings, prev.bindings)
+
+    def is_different(self, prev):
+        removed, added = self.diff_bindings(prev)
+        return len(removed) != 0 or len(added) != 0
 
 
 # A deserialized Environment.
 class Environment(object):
     def __init__(self, json_e):
         super(Environment, self).__init__()
         self.frames = [EnvironmentFrame(f) for f in json_e]
 
+    def diff_frames(self, prev):
+        # TODO: It's difficult to display a good diff when frame numbers shift.
+        if len(self.frames) != len(prev.frames):
+            return None
+
+        updated = []
+        for i in range(len(self.frames)):
+            f = self.frames[i]
+            prev_f = prev.frames[i]
+            if f.location_context == prev_f.location_context:
+                if f.is_different(prev_f):
+                    updated.append(i)
+            else:
+                # We have the whole frame replaced with another frame.
+                # TODO: Produce a nice diff.
+                return None
+
+        # TODO: Add support for added/removed.
+        return updated
 
-# 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']
+    def is_different(self, prev):
+        updated = self.diff_frames(prev)
+        return updated is None or len(updated) > 0
+
+
+# A single binding key in a deserialized RegionStore cluster.
+class StoreBindingKey(object):
+    def __init__(self, json_sk):
+        super(StoreBindingKey, self).__init__()
+        self.kind = json_sk['kind']
+        self.offset = json_sk['offset']
+
+    def _key(self):
+        return (self.kind, self.offset)
+
+    def __eq__(self, other):
+        return self._key() == other._key()
+
+    def __hash__(self):
+        return hash(self._key())
 
 
 # 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']]
+        self.bindings = collections.OrderedDict(
+            [(StoreBindingKey(b), b['value']) for b in json_sc['items']])
+
+    def diff_bindings(self, prev):
+        return diff_dicts(self.bindings, prev.bindings)
+
+    def is_different(self, prev):
+        removed, added = self.diff_bindings(prev)
+        return len(removed) != 0 or len(added) != 0
 
 
 # A deserialized RegionStore.
 class Store(object):
     def __init__(self, json_s):
         super(Store, self).__init__()
-        self.clusters = [StoreCluster(c) for c in json_s]
+        self.clusters = collections.OrderedDict(
+            [(c['pointer'], StoreCluster(c)) for c in json_s])
+
+    def diff_clusters(self, prev):
+        removed = [k for k in prev.clusters if k not in self.clusters]
+        added = [k for k in self.clusters if k not in prev.clusters]
+        updated = [k for k in prev.clusters if k in self.clusters
+                   and prev.clusters[k].is_different(self.clusters[k])]
+        return (removed, added, updated)
+
+    def is_different(self, prev):
+        removed, added, updated = self.diff_clusters(prev)
+        return len(removed) != 0 or len(added) != 0 or len(updated) != 0
 
 
 # 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
def add_raw_line(self, raw_line):
                 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('\\<', '\\\\<') \
                                         .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):
+    def __init__(self, do_diffs):
         super(DotDumpVisitor, self).__init__()
+        self._do_diffs = do_diffs
 
     @staticmethod
     def _dump_raw(s):
         print(s, end='')
 
     @staticmethod
     def _dump(s):
         print(s.replace('&', '&amp;')
                .replace('{', '\\{')
                .replace('}', '\\}')
                .replace('\\<', '&lt;')
                .replace('\\>', '&gt;')
                .replace('\\l', '<br />')
                .replace('|', ''), end='')
 
+    @staticmethod
+    def _diff_plus_minus(is_added):
+        if is_added is None:
+            return ''
+        if is_added:
+            return '<font color="forestgreen">+</font>'
+        return '<font color="red">-</font>'
+
     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'
def visit_program_point(self, p):
                               p.loc.col, color, p.stmt_kind, p.pretty))
             else:
                 self._dump('<tr><td align="left" width="0">'
                            '<i>Invalid Source Location</i>:</td>'
                            '<td align="left" width="0">'
                            '<font color="%s">%s</font></td><td>%s</td></tr>'
                            % (color, p.stmt_kind, p.pretty))
         elif p.kind == 'Edge':
-            self._dump('<tr><td width="0">-</td>'
+            self._dump('<tr><td width="0"></td>'
                        '<td align="left" width="0">'
                        '<font color="%s">%s</font></td><td align="left">'
                        '[B%d] -\\> [B%d]</td></tr>'
                        % (color, p.kind, p.src_id, p.dst_id))
         else:
             # TODO: Print more stuff for other kinds of points.
-            self._dump('<tr><td width="0">-</td>'
+            self._dump('<tr><td width="0"></td>'
                        '<td align="left" width="0" colspan="2">'
                        '<font color="%s">%s</font></td></tr>'
                        % (color, p.kind))
 
-    def visit_environment(self, e):
+    def visit_environment(self, e, prev_e=None):
         self._dump('<table border="0">')
 
-        for f in e.frames:
-            self._dump('<tr><td align="left"><b>%s</b></td>'
+        def dump_location_context(lc, is_added=None):
+            self._dump('<tr><td>%s</td>'
+                       '<td align="left"><b>%s</b></td>'
                        '<td align="left"><font color="grey60">%s </font>'
                        '%s</td></tr>'
-                       % (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('<tr><td align="left"><i>S%s</i></td>'
-                           '<td align="left">%s</td>'
-                           '<td align="left">%s</td></tr>'
-                           % (b.stmt_id, b.pretty, b.value))
+                       % (self._diff_plus_minus(is_added),
+                          lc.caption, lc.decl,
+                          ('(line %s)' % lc.line) if lc.line is not None
+                          else ''))
+
+        def dump_binding(f, b, is_added=None):
+            self._dump('<tr><td>%s</td>'
+                       '<td align="left"><i>S%s</i></td>'
+                       % (self._diff_plus_minus(is_added),
+                          b.stmt_id, b.pretty, f.bindings[b]))
+
+        frames_updated = e.diff_frames(prev_e) if prev_e is not None else None
+        if frames_updated:
+            for i in frames_updated:
+                f = e.frames[i]
+                prev_f = prev_e.frames[i]
+                dump_location_context(f.location_context)
+                bindings_removed, bindings_added = f.diff_bindings(prev_f)
+                for b in bindings_removed:
+                    dump_binding(prev_f, b, False)
+                for b in bindings_added:
+                    dump_binding(f, b, True)
+        else:
+            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_store(self, s):
+    def visit_store(self, s, prev_s=None):
         self._dump('<table border="0">')
 
-        for c in s.clusters:
-            for b in c.bindings:
-                self._dump('<tr><td align="left">%s</td>'
-                           '<td align="left">%s</td>'
-                           '<td align="left">%s</td>'
-                           '<td align="left">%s</td></tr>'
-                           % (c.base_region, b.offset,
-                              '(<i>Default</i>)' if b.kind == 'Default'
-                              else '',
-                              b.value))
+        def dump_binding(s, c, b, is_added=None):
+            self._dump('<tr><td>%s</td>'
+                       '<td align="left">%s</td>'
+                       % (self._diff_plus_minus(is_added),
+                          s.clusters[c].base_region, b.offset,
+                          s.clusters[c].bindings[b]))
+
+        if prev_s is not None:
+            clusters_removed, clusters_added, clusters_updated = \
+                s.diff_clusters(prev_s)
+            for c in clusters_removed:
+                for b in prev_s.clusters[c].bindings:
+                    dump_binding(prev_s, c, b, False)
+            for c in clusters_updated:
+                bindings_removed, bindings_added = \
+                    s.clusters[c].diff_bindings(prev_s.clusters[c])
+                for b in bindings_removed:
+                    dump_binding(prev_s, c, b, False)
+                for b in bindings_added:
+                    dump_binding(s, c, b, True)
+            for c in clusters_added:
+                for b in s.clusters[c].bindings:
+                    dump_binding(s, c, b, True)
+        else:
+            for c in s.clusters:
+                for b in s.clusters[c].bindings:
+                    dump_binding(s, c, b)
 
         self._dump('</table>')
 
-    def visit_state(self, s):
-        self._dump('<tr><td align="left">'
-                   '<b>Store: </b>')
+    def visit_state(self, s, prev_s):
+        # == Store ==
+        self._dump('<tr><td align="left"><b>Store: </b>')
         if s.store is None:
             self._dump('<i> Nothing!</i>')
         else:
-            self._dump('</td></tr>'
-                       '<tr><td align="left">')
+            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:
+                    self._dump('<i> No changes!</i>')
+            else:
+                self._dump('</td></tr><tr><td align="left">')
                 self.visit_store(s.store)
+        self._dump('</td></tr><hr />')
 
-        self._dump('</td></tr><hr />'
-                   '<tr><td align="left">'
+        # == Environment ==
+        self._dump('<tr><td align="left">'
                    '<b>Environment: </b>')
         if s.environment is None:
             self._dump('<i> Nothing!</i>')
         else:
-            self._dump('</td></tr>'
-                       '<tr><td align="left">')
+            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:
+                    self._dump('<i> No changes!</i>')
+            else:
+                self._dump('</td></tr><tr><td align="left">')
                 self.visit_environment(s.environment)
 
         self._dump('</td></tr>')
 
     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 />')
-            self.visit_state(node.state)
+            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)
         self._dump_raw('</table>>];\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')
 
def explore(self, graph, visitor):
                 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,
+                        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')
     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()
+    visitor = DotDumpVisitor(args.diff)
     explorer.explore(graph, visitor)
 
 
 if __name__ == '__main__':
     main()