| #!/usr/bin/python |
| # Copyright (c) 2009 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 |
| |
| class URL: |
| """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: |
| """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(str): |
| """Escape a string suitable for embedding in a graphviz graph.""" |
| # TODO(evanm): this is likely not sufficient. |
| return str.replace('\n', '\\n') |
| |
| class SQLite: |
| """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 |
| |
| # Some transition types, copied from page_transition_types.h. |
| TRANS_TYPES = { |
| 0: 'link', |
| 1: 'typed', |
| 2: 'most-visited', |
| 3: 'auto subframe', |
| 7: 'form', |
| } |
| |
| 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 '}' |
| |
