history-viz.py

#!/usr/bin/env python
# Copyright (c) 2011 The Chromium Authors. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.

"""Process a History database and dump a .dot file suitable for GraphViz.

This is useful for debugging history redirect flows.

An example run of this program:
  python /src/history-viz.py History > foo.dot
  /c/Program\ Files/Graphviz2.18/bin/dot -Tpng foo.dot -o foo.png
"""

import struct
import subprocess
import sys
import urlparse


# Some transition types, copied from page_transition_types.h.
TRANS_TYPES = {
  0: 'link',
  1: 'typed',
  2: 'most-visited',
  3: 'auto subframe',
  7: 'form',
}


class URL(object):
  """Represents a broken-down URL from our most visited database."""

  def __init__(self, id, url):
    """Initialize a new URL object.  |id| is the database id of the URL."""
    self.id = id
    self.url = url
    scheme, loc, path, query, fragment = urlparse.urlsplit(url)
    if scheme == 'http':
      scheme = ''  # Shorten for display purposes.
    if len(scheme) > 0:
      scheme += '://'
    self.host = scheme + loc
    self.path = path

    extra = ''
    if len(query) > 0:
      extra += '?' + query
    if len(fragment) > 0 or url.find('#') > 0:
      extra += '#' + fragment
    self.extra = extra

  def PrettyPrint(self, include_host=True, include_path=True):
    """Pretty-print this URL in a form more suitable for the graph.

    This will elide very long paths and potentially puts newlines between parts
    of long components.  include_host and include_path determine whether to
    include the host and path in the output.

    Returns: the pretty-printed string."""
    MAX_LEN = 30  # Maximum length of a line in the output.
    parts = []
    if include_host:
      parts.append(self.host)
    if include_path:
      parts.append(self.path)
    parts.append(self.extra)
    lines = []
    line = ''
    for part in parts:
      if len(part) > MAX_LEN:
        part = part[0:MAX_LEN-3] + '...'
      if len(line)+len(part) > MAX_LEN:
        lines.append(line)
        line = ''
      line += part
    if len(line) > 0:
      lines.append(line)
    return '\n'.join(lines)


class Edge(object):
  """Represents an edge in the history graph, connecting two pages.

  If a link is traversed twice, it is one Edge with two entries in
  the .transitions array."""
  def __init__(self, src, dst):
    self.src = src
    self.dst = dst
    self.transitions = []

  def Transitions(self):
    """Return a dictionary mapping transition type -> occurences."""
    all = {}
    for trans in self.transitions:
      all[trans] = all.get(trans, 0) + 1
      # We currently don't use the chain type.
      # TODO(evanm): make this a command-line option.
      # if trans & 0x30000000 != 0:
      #   chain = ''
      #   if trans & 0x10000000:
      #     chain = 'start'
      #   if trans & 0x20000000:
      #     if len(chain) == 0:
      #       chain = 'end'
      #     else:
      #       chain = ''
      #   if len(chain) > 0:
      #     edge['chain'] = chain
    return all


def ClusterBy(objs, pred):
  """Group a list of objects by a predicate.

  Given a list of objects and a predicate over the objects, return a
  dictionary mapping pred(obj) -> all objs with the same pred(obj)."""
  clusters = {}
  for obj in objs:
    cluster = pred(obj)
    clusters[cluster] = clusters.get(cluster, [])
    clusters[cluster].append(obj)
  return clusters


def EscapeDot(string):
  """Escape a string suitable for embedding in a graphviz graph."""
  # TODO(evanm): this is likely not sufficient.
  return string.replace('\n', '\\n')


class SQLite(object):
  """Trivial interface to executing SQLite queries.
  Spawns a new process with each call."""
  def __init__(self, file=None):
    self.file = file

  def Run(self, sql):
    """Execute |sql|, yielding each row of results as an array."""
    subproc = subprocess.Popen(['sqlite', self.file],
                               stdin=subprocess.PIPE,
                               stdout=subprocess.PIPE)
    subproc.stdin.write('.mode tabs\n')
    subproc.stdin.write(sql + ';')
    subproc.stdin.close()
    for line in subproc.stdout:
      row = line.strip().split('\t')
      yield row


def LoadHistory(filename):
  db = SQLite(filename)

  urls = {}  # Map of urlid => url.
  urls['0'] = URL('0', 'start')  # Node name '0' is our special 'start' node.
  for id, url in db.Run('SELECT id, url FROM urls'):
    urls[id] = URL(id, url)

  visiturlids = {}  # Map of visitid => urlid.
  visiturlids['0'] = '0'  # '0' is our special 'start' node.
  edges = {}  # Map of urlid->urlid->Edge.
  for src, dst, url, trans in db.Run('SELECT from_visit, id, url, transition '
                                     'FROM visits ORDER BY id'):
    visiturlids[dst] = url
    src = visiturlids[src]
    dst = visiturlids[dst]
    edges[src] = edges.get(src, {})
    edge = edges[src][dst] = edges[src].get(dst, Edge(src, dst))
    # SQLite outputs transition values as signed integers, but they're really
    # a bitfield.  Below does "unsigned trans = static_cast<unsigned>(trans)".
    trans = struct.unpack('I', struct.pack('i', int(trans)))[0]
    edge.transitions.append(trans)

  return urls, edges


def main():
  urls, edges = LoadHistory(sys.argv[1])
  print 'digraph G {'
  print '  graph [rankdir=LR]'  # Display left to right.
  print '  node [shape=box]'    # Display nodes as boxes.
  print '  subgraph { rank=source; 0 [label="start"] }'

  # Output all the nodes within graph clusters.
  hosts = ClusterBy(urls.values(), lambda url: url.host)
  for i, (host, urls) in enumerate(hosts.items()):
    # Cluster all URLs under this host if it has more than one entry.
    host_clustered = len(urls) > 1
    if host_clustered:
      print 'subgraph clusterhost%d {' % i
      print '  label="%s"' % host
    paths = ClusterBy(urls, lambda url: url.path)
    for j, (path, urls) in enumerate(paths.items()):
      # Cluster all URLs under this host if it has more than one entry.
      path_clustered = host_clustered and len(urls) > 1
      if path_clustered:
        print '  subgraph cluster%d%d {' % (i, j)
        print '    label="%s"' % path
      for url in urls:
        if url.id == '0': continue  # We already output the special start node.
        pretty = url.PrettyPrint(include_host=not host_clustered,
                                include_path=not path_clustered)
        print '    %s [label="%s"]' % (url.id, EscapeDot(pretty))
      if path_clustered:
        print '  }'
    if host_clustered:
      print '}'

  # Output all the edges between nodes.
  for src, dsts in edges.items():
    for dst, edge in dsts.items():
      # Gather up all the transitions into the label.
      label = []      # Label for the edge.
      transitions = edge.Transitions()
      for trans, count in transitions.items():
        text = ''
        if count > 1:
          text = '%dx ' % count
        base_type = trans & 0xFF
        redir = (trans & 0xC0000000) != 0
        start = (trans & 0x10000000) != 0
        end = (trans & 0x20000000) != 0
        if start or end:
          if start:
            text += '<'
          if end:
            text += '>'
          text += ' '
        if redir:
          text += 'R '
        text += TRANS_TYPES.get(base_type, 'trans%d' % base_type)
        label.append(text)
      if len(label) == 0:
        continue

      edgeattrs = []  # Graphviz attributes for the edge.
      # If the edge is from the start and the transitions are fishy, make it
      # display as a dotted line.
      if src == '0' and len(transitions.keys()) == 1 and transitions.has_key(0):
        edgeattrs.append('style=dashed')
      if len(label) > 0:
        edgeattrs.append('label="%s"' % EscapeDot('\n'.join(label)))

      out = '%s -> %s' % (src, dst)
      if len(edgeattrs) > 0:
        out += ' [%s]' % ','.join(edgeattrs)
      print out
  print '}'
  return 0


if __name__ == '__main__':
  sys.exit(main())