Home | History | Annotate | Download | only in tools 
      1 #!/usr/bin/env python
      2 # Copyright (c) 2011 The Chromium Authors. All rights reserved.
      3 # Use of this source code is governed by a BSD-style license that can be
      4 # found in the LICENSE file.
      5 
      6 """Process a History database and dump a .dot file suitable for GraphViz.
      7 
      8 This is useful for debugging history redirect flows.
      9 
     10 An example run of this program:
     11   python /src/history-viz.py History > foo.dot
     12   /c/Program\ Files/Graphviz2.18/bin/dot -Tpng foo.dot -o foo.png
     13 """
     14 
     15 import struct
     16 import subprocess
     17 import sys
     18 import urlparse
     19 
     20 
     21 # Some transition types, copied from page_transition_types.h.
     22 TRANS_TYPES = {
     23   0: 'link',
     24   1: 'typed',
     25   2: 'most-visited',
     26   3: 'auto subframe',
     27   7: 'form',
     28 }
     29 
     30 
     31 class URL(object):
     32   """Represents a broken-down URL from our most visited database."""
     33 
     34   def __init__(self, id, url):
     35     """Initialize a new URL object.  |id| is the database id of the URL."""
     36     self.id = id
     37     self.url = url
     38     scheme, loc, path, query, fragment = urlparse.urlsplit(url)
     39     if scheme == 'http':
     40       scheme = ''  # Shorten for display purposes.
     41     if len(scheme) > 0:
     42       scheme += '://'
     43     self.host = scheme + loc
     44     self.path = path
     45 
     46     extra = ''
     47     if len(query) > 0:
     48       extra += '?' + query
     49     if len(fragment) > 0 or url.find('#') > 0:
     50       extra += '#' + fragment
     51     self.extra = extra
     52 
     53   def PrettyPrint(self, include_host=True, include_path=True):
     54     """Pretty-print this URL in a form more suitable for the graph.
     55 
     56     This will elide very long paths and potentially puts newlines between parts
     57     of long components.  include_host and include_path determine whether to
     58     include the host and path in the output.
     59 
     60     Returns: the pretty-printed string."""
     61     MAX_LEN = 30  # Maximum length of a line in the output.
     62     parts = []
     63     if include_host:
     64       parts.append(self.host)
     65     if include_path:
     66       parts.append(self.path)
     67     parts.append(self.extra)
     68     lines = []
     69     line = ''
     70     for part in parts:
     71       if len(part) > MAX_LEN:
     72         part = part[0:MAX_LEN-3] + '...'
     73       if len(line)+len(part) > MAX_LEN:
     74         lines.append(line)
     75         line = ''
     76       line += part
     77     if len(line) > 0:
     78       lines.append(line)
     79     return '\n'.join(lines)
     80 
     81 
     82 class Edge(object):
     83   """Represents an edge in the history graph, connecting two pages.
     84 
     85   If a link is traversed twice, it is one Edge with two entries in
     86   the .transitions array."""
     87   def __init__(self, src, dst):
     88     self.src = src
     89     self.dst = dst
     90     self.transitions = []
     91 
     92   def Transitions(self):
     93     """Return a dictionary mapping transition type -> occurences."""
     94     all = {}
     95     for trans in self.transitions:
     96       all[trans] = all.get(trans, 0) + 1
     97       # We currently don't use the chain type.
     98       # TODO(evanm): make this a command-line option.
     99       # if trans & 0x30000000 != 0:
    100       #   chain = ''
    101       #   if trans & 0x10000000:
    102       #     chain = 'start'
    103       #   if trans & 0x20000000:
    104       #     if len(chain) == 0:
    105       #       chain = 'end'
    106       #     else:
    107       #       chain = ''
    108       #   if len(chain) > 0:
    109       #     edge['chain'] = chain
    110     return all
    111 
    112 
    113 def ClusterBy(objs, pred):
    114   """Group a list of objects by a predicate.
    115 
    116   Given a list of objects and a predicate over the objects, return a
    117   dictionary mapping pred(obj) -> all objs with the same pred(obj)."""
    118   clusters = {}
    119   for obj in objs:
    120     cluster = pred(obj)
    121     clusters[cluster] = clusters.get(cluster, [])
    122     clusters[cluster].append(obj)
    123   return clusters
    124 
    125 
    126 def EscapeDot(string):
    127   """Escape a string suitable for embedding in a graphviz graph."""
    128   # TODO(evanm): this is likely not sufficient.
    129   return string.replace('\n', '\\n')
    130 
    131 
    132 class SQLite(object):
    133   """Trivial interface to executing SQLite queries.
    134   Spawns a new process with each call."""
    135   def __init__(self, file=None):
    136     self.file = file
    137 
    138   def Run(self, sql):
    139     """Execute |sql|, yielding each row of results as an array."""
    140     subproc = subprocess.Popen(['sqlite', self.file],
    141                                stdin=subprocess.PIPE,
    142                                stdout=subprocess.PIPE)
    143     subproc.stdin.write('.mode tabs\n')
    144     subproc.stdin.write(sql + ';')
    145     subproc.stdin.close()
    146     for line in subproc.stdout:
    147       row = line.strip().split('\t')
    148       yield row
    149 
    150 
    151 def LoadHistory(filename):
    152   db = SQLite(filename)
    153 
    154   urls = {}  # Map of urlid => url.
    155   urls['0'] = URL('0', 'start')  # Node name '0' is our special 'start' node.
    156   for id, url in db.Run('SELECT id, url FROM urls'):
    157     urls[id] = URL(id, url)
    158 
    159   visiturlids = {}  # Map of visitid => urlid.
    160   visiturlids['0'] = '0'  # '0' is our special 'start' node.
    161   edges = {}  # Map of urlid->urlid->Edge.
    162   for src, dst, url, trans in db.Run('SELECT from_visit, id, url, transition '
    163                                      'FROM visits ORDER BY id'):
    164     visiturlids[dst] = url
    165     src = visiturlids[src]
    166     dst = visiturlids[dst]
    167     edges[src] = edges.get(src, {})
    168     edge = edges[src][dst] = edges[src].get(dst, Edge(src, dst))
    169     # SQLite outputs transition values as signed integers, but they're really
    170     # a bitfield.  Below does "unsigned trans = static_cast<unsigned>(trans)".
    171     trans = struct.unpack('I', struct.pack('i', int(trans)))[0]
    172     edge.transitions.append(trans)
    173 
    174   return urls, edges
    175 
    176 
    177 def main():
    178   urls, edges = LoadHistory(sys.argv[1])
    179   print 'digraph G {'
    180   print '  graph [rankdir=LR]'  # Display left to right.
    181   print '  node [shape=box]'    # Display nodes as boxes.
    182   print '  subgraph { rank=source; 0 [label="start"] }'
    183 
    184   # Output all the nodes within graph clusters.
    185   hosts = ClusterBy(urls.values(), lambda url: url.host)
    186   for i, (host, urls) in enumerate(hosts.items()):
    187     # Cluster all URLs under this host if it has more than one entry.
    188     host_clustered = len(urls) > 1
    189     if host_clustered:
    190       print 'subgraph clusterhost%d {' % i
    191       print '  label="%s"' % host
    192     paths = ClusterBy(urls, lambda url: url.path)
    193     for j, (path, urls) in enumerate(paths.items()):
    194       # Cluster all URLs under this host if it has more than one entry.
    195       path_clustered = host_clustered and len(urls) > 1
    196       if path_clustered:
    197         print '  subgraph cluster%d%d {' % (i, j)
    198         print '    label="%s"' % path
    199       for url in urls:
    200         if url.id == '0': continue  # We already output the special start node.
    201         pretty = url.PrettyPrint(include_host=not host_clustered,
    202                                 include_path=not path_clustered)
    203         print '    %s [label="%s"]' % (url.id, EscapeDot(pretty))
    204       if path_clustered:
    205         print '  }'
    206     if host_clustered:
    207       print '}'
    208 
    209   # Output all the edges between nodes.
    210   for src, dsts in edges.items():
    211     for dst, edge in dsts.items():
    212       # Gather up all the transitions into the label.
    213       label = []      # Label for the edge.
    214       transitions = edge.Transitions()
    215       for trans, count in transitions.items():
    216         text = ''
    217         if count > 1:
    218           text = '%dx ' % count
    219         base_type = trans & 0xFF
    220         redir = (trans & 0xC0000000) != 0
    221         start = (trans & 0x10000000) != 0
    222         end = (trans & 0x20000000) != 0
    223         if start or end:
    224           if start:
    225             text += '<'
    226           if end:
    227             text += '>'
    228           text += ' '
    229         if redir:
    230           text += 'R '
    231         text += TRANS_TYPES.get(base_type, 'trans%d' % base_type)
    232         label.append(text)
    233       if len(label) == 0:
    234         continue
    235 
    236       edgeattrs = []  # Graphviz attributes for the edge.
    237       # If the edge is from the start and the transitions are fishy, make it
    238       # display as a dotted line.
    239       if src == '0' and len(transitions.keys()) == 1 and transitions.has_key(0):
    240         edgeattrs.append('style=dashed')
    241       if len(label) > 0:
    242         edgeattrs.append('label="%s"' % EscapeDot('\n'.join(label)))
    243 
    244       out = '%s -> %s' % (src, dst)
    245       if len(edgeattrs) > 0:
    246         out += ' [%s]' % ','.join(edgeattrs)
    247       print out
    248   print '}'
    249   return 0
    250 
    251 
    252 if __name__ == '__main__':
    253   sys.exit(main())
    254