# 
# 
# add_dir "grapher"
# 
# add_file "grapher/grapher.py"
#  content [c16a01d528199038ce874a90d15672dc7636d427]
# 
#   set "grapher/grapher.py"
#  attr "mtn:execute"
# value "true"
# 
============================================================
--- grapher/grapher.py	c16a01d528199038ce874a90d15672dc7636d427
+++ grapher/grapher.py	c16a01d528199038ce874a90d15672dc7636d427
@@ -0,0 +1,169 @@
+#!/usr/bin/python
+
+import sys
+sys.path.append('..')
+
+import monotone
+import config
+import common
+import string
+
+from StringIO import StringIO
+
+try:
+    a = set()
+except:
+    import sets
+    set = sets.Set
+
+# algorithm:
+#  output a Dot file representing the graph
+#  use this to go to SVG
+#  use an arbitrary tool to go to PNG + HTML image map
+#  cut this up into squares
+#
+# caching:
+#  the trouble is that the graph can change arbitrarily, even 
+#  if it's unlikely to. eg. someone could commit a rev to a 
+#  n.v.monotone's first ever rev and then merge it with head or 
+#  something awful...
+#
+#  hrm.
+#  so, for each block in the image we should list the revs it 
+#  contains. when updating we find the highest image (most vertical 
+#  in the graph) that contains an affected rev. Update the row that 
+#  image is in downwards.
+
+mt = monotone.Monotone(config.monotone, config.dbfile)
+nodeopts = ','.join(map(lambda opt: '%s="%s"' % (opt, config.graphopts['nodeopts'][opt]), config.graphopts['nodeopts'].keys()))
+
+def toposorted_revs(branch):
+    heads = mt.heads(branch)
+    return mt.toposort(mt.ancestors(heads))
+
+def dot_escape(s):
+    # kinda paranoid, should probably revise later
+    permitted=string.digits + string.letters + ' -<>-:,address@hidden&.+_~?/'
+    return ''.join(filter(lambda x: x in permitted, s))
+
+class RevisionNode:
+    def __init__(self, revision_id):
+	self.revision_id = revision_id
+	self.parents = mt.parents(revision_id)
+	self.children = mt.children(revision_id)
+
+    def output_node(self):
+	opts = [nodeopts]
+	if len(self.parents) > 1:
+	    opts.append('label=""')
+	    opts.append('shape="circle"')
+	else:
+	    certs = mt.certs(self.revision_id)
+	    label = '[%s..]' % (self.revision_id[:8])
+	    date = common.extract_cert_from_certs(certs, "date")
+	    if date:
+		date = dot_escape(date)
+		date = date[0:date.find("T")]
+		label += ' on %s' % (date)
+	    label += '\\n'
+	    author = common.extract_cert_from_certs(certs, "author")
+	    if author:
+		label += '\\n%s' % (dot_escape(author))
+	    opts.append('label="%s"' % label)
+	    opts.append('shape="box"')
+	return '    "%s" [' % self.revision_id + ','.join(opts) + ']\n'
+
+    def output_edges(self, local_revisions):
+	edges = []
+	for revision_id in self.children:
+	    if revision_id in local_revisions:
+		edges.append('    "%s" -> "%s"' % (self.revision_id, revision_id))
+	    else:
+		edges.append('    "%s" ->' % (self.revision_id))
+	return '\n'.join(edges) + '\n'
+
+class RevisionGroup:
+    def __init__(self):
+	"""A non-empty group representing a direct graph of revisions. 
+	Only the first and last (top and bottom) revisions may have 
+	links that carry outside of the group. The bottom revision must 
+	have at most one child."""
+	self.nodes = []
+	self.revisions = set()
+	self.references = set()
+	self.first, self.last = None, None
+	self.is_valid = False
+
+    def append(self, node):
+	self.nodes.append(node)
+	self.revisions.add(node.revision_id)
+	self.last = node
+	if not self.first:
+	    self.first = node
+	    self.is_valid = True
+	else:
+	    # note; we make sure that we add to self.references 
+	    # after checking validity, as the final node may have links
+	    # that carry outside of the group (so these links shouldn't 
+	    # count wrt. validity)
+	    unsatisfied = self.revisions - self.references
+	    sys.stderr.write("%s : %s\n" % (node.revision_id, unsatisfied))
+	    self.is_valid = len(unsatisfied) == 0
+	    self.references = self.references.union(node.parents + node.children)
+	if len(self.last.children) > 1:
+	    self.is_valid = False
+
+    def length(self):
+	return len(self.revisions)
+
+    def output(self, fd):
+	fd.write('''
+digraph ancestry {
+    ratio=compress
+    nodesep=0.1
+    ranksep=0.2
+''')
+
+	map(lambda node: fd.write(node.output_node()), self.nodes)
+	map(lambda node: fd.write(node.output_edges(self.revisions)), self.nodes)
+	fd.write('''
+}''')
+
+
+class RevisionGraph:
+    def __init__(self, revisions, min_group_size):
+	self.revisions = revisions
+	self.min_group_size = min_group_size
+	self.groups = []
+	self.revision_to_group = {}
+
+    def calculate(self):
+	group, size = RevisionGroup(), 0
+	for revision in self.revisions:
+	    node = RevisionNode(revision)
+	    group.append(node)
+	    self.revision_to_group[revision] = group
+	    size += 1
+
+	    if size >= self.min_group_size and group.is_valid:
+		self.groups.append(group)
+		group, size = RevisionGroup(), 0
+
+	if size >= 0:
+	    self.groups.append(group)
+
+    def output(self):
+	fd = StringIO()
+	for group in self.groups:
+	    group.output(fd)
+	    fd.read()
+	    print fd.buf
+	    break
+
+if __name__ == '__main__':
+    branch = sys.argv[1]
+    revs = toposorted_revs(branch)
+    graph = RevisionGraph(revs, 20)
+    graph.calculate()
+    graph.output()
+