# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1286502074 14400
# Node ID 5c12eeee395f5b3db37b11667a6c14af217eccc7
# Parent  f42246bbc0e51bde0f0c382d460deb3e233382c6
Holy shit I have an undo graph.

diff -r f42246bbc0e5 -r 5c12eeee395f plugin/gundo.vim
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/plugin/gundo.vim	Thu Oct 07 21:41:14 2010 -0400
@@ -0,0 +1,338 @@
+python << ENDPYTHON
+import vim
+from pprint import pprint
+
+normal = lambda s: vim.command('normal %s' % s)
+
+ut = vim.eval('undotree()')
+tip = ut['seq_last']
+current = ut['seq_cur']
+entries = ut['entries']
+
+class Buffer(object):
+    def __init__(self):
+        self.b = ''
+    def write(self, s):
+        self.b += s
+
+class Node(object):
+    def __init__(self, n, parent):
+        self.n = int(n)
+        self.parent = parent
+        self.children = []
+
+    def pprint(self, indent=0):
+        print '%sn%d -> %s, %s\n' % (
+                  '    ' * indent,
+                  self.n,
+                  self.parent.n if self.parent else 'n/a',
+                  [c.n for c in self.children]),
+        for c in self.children:
+            c.pprint(indent+1)
+
+    def __str__(self):
+        return 'Node: %s' % str(self.n)
+
+root = Node(0, None)
+
+nodes = []
+def make_nodes(alts, parent=None):
+    p = parent
+
+    for alt in alts:
+        node = Node(n=alt['seq'], parent=p)
+        nodes.append(node)
+        if alt.get('alt'):
+            make_nodes(alt['alt'], parent=p)
+        p = node
+
+    return nodes
+make_nodes(entries, root)
+
+for node in nodes:
+    node.children = [n for n in nodes if n.parent == node]
+
+tips = [node for node in nodes if not node.children]
+
+
+def walk_nodes(nodes):
+    for node in nodes:
+        yield(node, [node.parent] if node.parent else [])
+
+def asciiedges(seen, rev, parents):
+    """adds edge info to changelog DAG walk suitable for ascii()"""
+    if rev not in seen:
+        seen.append(rev)
+    nodeidx = seen.index(rev)
+
+    knownparents = []
+    newparents = []
+    for parent in parents:
+        if parent in seen:
+            knownparents.append(parent)
+        else:
+            newparents.append(parent)
+
+    ncols = len(seen)
+    seen[nodeidx:nodeidx + 1] = newparents
+    edges = [(nodeidx, seen.index(p)) for p in knownparents]
+
+    if len(newparents) > 0:
+        edges.append((nodeidx, nodeidx))
+    if len(newparents) > 1:
+        edges.append((nodeidx, nodeidx + 1))
+
+    nmorecols = len(seen) - ncols
+    return nodeidx, edges, ncols, nmorecols
+
+def get_nodeline_edges_tail(
+        node_index, p_node_index, n_columns, n_columns_diff, p_diff, fix_tail):
+    if fix_tail and n_columns_diff == p_diff and n_columns_diff != 0:
+        # Still going in the same non-vertical direction.
+        if n_columns_diff == -1:
+            start = max(node_index + 1, p_node_index)
+            tail = ["|", " "] * (start - node_index - 1)
+            tail.extend(["/", " "] * (n_columns - start))
+            return tail
+        else:
+            return ["\\", " "] * (n_columns - node_index - 1)
+    else:
+        return ["|", " "] * (n_columns - node_index - 1)
+
+def draw_edges(edges, nodeline, interline):
+    for (start, end) in edges:
+        if start == end + 1:
+            interline[2 * end + 1] = "/"
+        elif start == end - 1:
+            interline[2 * start + 1] = "\\"
+        elif start == end:
+            interline[2 * start] = "|"
+        else:
+            nodeline[2 * end] = "+"
+            if start > end:
+                (start, end) = (end, start)
+            for i in range(2 * start + 1, 2 * end):
+                if nodeline[i] != "+":
+                    nodeline[i] = "-"
+
+def ascii(buf, state, type, char, text, coldata):
+    """prints an ASCII graph of the DAG
+
+    takes the following arguments (one call per node in the graph):
+
+      - ui to write to
+      - Somewhere to keep the needed state in (init to asciistate())
+      - Column of the current node in the set of ongoing edges.
+      - Type indicator of node data == ASCIIDATA.
+      - Payload: (char, lines):
+        - Character to use as node's symbol.
+        - List of lines to display as the node's text.
+      - Edges; a list of (col, next_col) indicating the edges between
+        the current node and its parents.
+      - Number of columns (ongoing edges) in the current revision.
+      - The difference between the number of columns (ongoing edges)
+        in the next revision and the number of columns (ongoing edges)
+        in the current revision. That is: -1 means one column removed;
+        0 means no columns added or removed; 1 means one column added.
+    """
+
+    idx, edges, ncols, coldiff = coldata
+    assert -2 < coldiff < 2
+    if coldiff == -1:
+        # Transform
+        #
+        #     | | |        | | |
+        #     o | |  into  o---+
+        #     |X /         |/ /
+        #     | |          | |
+        fix_long_right_edges(edges)
+
+    # add_padding_line says whether to rewrite
+    #
+    #     | | | |        | | | |
+    #     | o---+  into  | o---+
+    #     |  / /         |   | |  # <--- padding line
+    #     o | |          |  / /
+    #                    o | |
+    add_padding_line = (len(text) > 2 and coldiff == -1 and
+                        [x for (x, y) in edges if x + 1 < y])
+
+    # fix_nodeline_tail says whether to rewrite
+    #
+    #     | | o | |        | | o | |
+    #     | | |/ /         | | |/ /
+    #     | o | |    into  | o / /   # <--- fixed nodeline tail
+    #     | |/ /           | |/ /
+    #     o | |            o | |
+    fix_nodeline_tail = len(text) <= 2 and not add_padding_line
+
+    # nodeline is the line containing the node character (typically o)
+    nodeline = ["|", " "] * idx
+    nodeline.extend([char, " "])
+
+    nodeline.extend(
+        get_nodeline_edges_tail(idx, state[1], ncols, coldiff,
+                                state[0], fix_nodeline_tail))
+
+    # shift_interline is the line containing the non-vertical
+    # edges between this entry and the next
+    shift_interline = ["|", " "] * idx
+    if coldiff == -1:
+        n_spaces = 1
+        edge_ch = "/"
+    elif coldiff == 0:
+        n_spaces = 2
+        edge_ch = "|"
+    else:
+        n_spaces = 3
+        edge_ch = "\\"
+    shift_interline.extend(n_spaces * [" "])
+    shift_interline.extend([edge_ch, " "] * (ncols - idx - 1))
+
+    # draw edges from the current node to its parents
+    draw_edges(edges, nodeline, shift_interline)
+
+    # lines is the list of all graph lines to print
+    lines = [nodeline]
+    if add_padding_line:
+        lines.append(get_padding_line(idx, ncols, edges))
+    lines.append(shift_interline)
+
+    # make sure that there are as many graph lines as there are
+    # log strings
+    while len(text) < len(lines):
+        text.append("")
+    if len(lines) < len(text):
+        extra_interline = ["|", " "] * (ncols + coldiff)
+        while len(lines) < len(text):
+            lines.append(extra_interline)
+
+    # print lines
+    indentation_level = max(ncols, ncols + coldiff)
+    for (line, logstr) in zip(lines, text):
+        ln = "%-*s %s" % (2 * indentation_level, "".join(line), logstr)
+        buf.write(ln.rstrip() + '\n')
+
+    # ... and start over
+    state[0] = coldiff
+    state[1] = idx
+
+def fix_long_right_edges(edges):
+    for (i, (start, end)) in enumerate(edges):
+        if end > start:
+            edges[i] = (start, end + 1)
+
+def ascii(buf, state, type, char, text, coldata):
+    """prints an ASCII graph of the DAG
+
+    takes the following arguments (one call per node in the graph):
+
+      - Somewhere to keep the needed state in (init to asciistate())
+      - Column of the current node in the set of ongoing edges.
+      - Type indicator of node data == ASCIIDATA.
+      - Payload: (char, lines):
+        - Character to use as node's symbol.
+        - List of lines to display as the node's text.
+      - Edges; a list of (col, next_col) indicating the edges between
+        the current node and its parents.
+      - Number of columns (ongoing edges) in the current revision.
+      - The difference between the number of columns (ongoing edges)
+        in the next revision and the number of columns (ongoing edges)
+        in the current revision. That is: -1 means one column removed;
+        0 means no columns added or removed; 1 means one column added.
+    """
+
+    idx, edges, ncols, coldiff = coldata
+    assert -2 < coldiff < 2
+    if coldiff == -1:
+        # Transform
+        #
+        #     | | |        | | |
+        #     o | |  into  o---+
+        #     |X /         |/ /
+        #     | |          | |
+        fix_long_right_edges(edges)
+
+    # add_padding_line says whether to rewrite
+    #
+    #     | | | |        | | | |
+    #     | o---+  into  | o---+
+    #     |  / /         |   | |  # <--- padding line
+    #     o | |          |  / /
+    #                    o | |
+    add_padding_line = (len(text) > 2 and coldiff == -1 and
+                        [x for (x, y) in edges if x + 1 < y])
+
+    # fix_nodeline_tail says whether to rewrite
+    #
+    #     | | o | |        | | o | |
+    #     | | |/ /         | | |/ /
+    #     | o | |    into  | o / /   # <--- fixed nodeline tail
+    #     | |/ /           | |/ /
+    #     o | |            o | |
+    fix_nodeline_tail = len(text) <= 2 and not add_padding_line
+
+    # nodeline is the line containing the node character (typically o)
+    nodeline = ["|", " "] * idx
+    nodeline.extend([char, " "])
+
+    nodeline.extend(
+        get_nodeline_edges_tail(idx, state[1], ncols, coldiff,
+                                state[0], fix_nodeline_tail))
+
+    # shift_interline is the line containing the non-vertical
+    # edges between this entry and the next
+    shift_interline = ["|", " "] * idx
+    if coldiff == -1:
+        n_spaces = 1
+        edge_ch = "/"
+    elif coldiff == 0:
+        n_spaces = 2
+        edge_ch = "|"
+    else:
+        n_spaces = 3
+        edge_ch = "\\"
+    shift_interline.extend(n_spaces * [" "])
+    shift_interline.extend([edge_ch, " "] * (ncols - idx - 1))
+
+    # draw edges from the current node to its parents
+    draw_edges(edges, nodeline, shift_interline)
+
+    # lines is the list of all graph lines to print
+    lines = [nodeline]
+    if add_padding_line:
+        lines.append(get_padding_line(idx, ncols, edges))
+    lines.append(shift_interline)
+
+    # make sure that there are as many graph lines as there are
+    # log strings
+    while len(text) < len(lines):
+        text.append("")
+    if len(lines) < len(text):
+        extra_interline = ["|", " "] * (ncols + coldiff)
+        while len(lines) < len(text):
+            lines.append(extra_interline)
+
+    # print lines
+    indentation_level = max(ncols, ncols + coldiff)
+    for (line, logstr) in zip(lines, text):
+        ln = "%-*s %s" % (2 * indentation_level, "".join(line), logstr)
+        buf.write(ln.rstrip() + '\n')
+
+    # ... and start over
+    state[0] = coldiff
+    state[1] = idx
+
+def generate(dag, edgefn):
+    seen, state = [], [0, 0]
+    buf = Buffer()
+    for node, parents in dag:
+        char = '@' if node.n == int(current) else 'o'
+        ascii(buf, state, 'C', char, ['[%s]' % str(node.n)], edgefn(seen, node, parents))
+    return buf.b
+
+dag = sorted(nodes, key=lambda n: int(n.n), reverse=True) + [root]
+result = generate(walk_nodes(dag), asciiedges)
+print result
+
+ENDPYTHON