diff -r 5bf465160632 -r 3201ff1459dd mercurial/dagparser.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/mercurial/dagparser.py	Thu Jun 10 11:48:15 2010 +0200
@@ -0,0 +1,473 @@
+# dagparser.py - parser and generator for concise description of DAGs
+#
+# Copyright 2010 Peter Arrenbrecht <peter@arrenbrecht.ch>
+#
+# This software may be used and distributed according to the terms of the
+# GNU General Public License version 2 or any later version.
+
+import re, string
+import util
+
+def parsedag(desc):
+    '''parses a DAG from a concise textual description; generates events
+
+    "+n" is a linear run of n nodes based on the current default parent
+    "." is a single node based on the current default parent
+    "$" resets the default parent to -1 (implied at the start);
+        otherwise the default parent is always the last node created
+    "<p" sets the default parent to the backref p
+    "*p" is a fork at parent p, where p is a backref
+    "*p1/p2/.../pn" is a merge of parents p1..pn, where the pi are backrefs
+    "/p2/.../pn" is a merge of the preceding node and p2..pn
+    ":name" defines a label for the preceding node; labels can be redefined
+    "@text" emits an annotation event for text
+    "!command" emits an action event for the current node
+    "!!my command\n" is like "!", but to the end of the line
+    "#...\n" is a comment up to the end of the line
+
+    Whitespace between the above elements is ignored.
+
+    A backref is either
+     * a number n, which references the node curr-n, where curr is the current
+       node, or
+     * the name of a label you placed earlier using ":name", or
+     * empty to denote the default parent.
+
+    All string valued-elements are either strictly alphanumeric, or must
+    be enclosed in double quotes ("..."), with "\" as escape character.
+
+    Generates sequence of
+
+      ('n', (id, [parentids])) for node creation
+      ('l', (id, labelname)) for labels on nodes
+      ('a', text) for annotations
+      ('c', command) for actions (!)
+      ('C', command) for line actions (!!)
+
+    Examples
+    --------
+
+    Example of a complex graph (output not shown for brevity):
+
+        >>> len(list(parsedag("""
+        ...
+        ... +3         # 3 nodes in linear run
+        ... :forkhere  # a label for the last of the 3 nodes from above
+        ... +5         # 5 more nodes on one branch
+        ... :mergethis # label again
+        ... <forkhere  # set default parent to labelled fork node
+        ... +10        # 10 more nodes on a parallel branch
+        ... @stable    # following nodes will be annotated as "stable"
+        ... +5         # 5 nodes in stable
+        ... !addfile   # custom command; could trigger new file in next node
+        ... +2         # two more nodes
+        ... /mergethis # merge last node with labelled node
+        ... +4         # 4 more nodes descending from merge node
+        ...
+        ... """)))
+        34
+
+    Empty list:
+
+        >>> list(parsedag(""))
+        []
+
+    A simple linear run:
+
+        >>> list(parsedag("+3"))
+        [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))]
+
+    Some non-standard ways to define such runs:
+
+        >>> list(parsedag("+1+2"))
+        [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))]
+
+        >>> list(parsedag("+1*1*"))
+        [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))]
+
+        >>> list(parsedag("*"))
+        [('n', (0, [-1]))]
+
+        >>> list(parsedag("..."))
+        [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))]
+
+    A fork and a join, using numeric back references:
+
+        >>> list(parsedag("+2*2*/2"))
+        [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [0])), ('n', (3, [2, 1]))]
+
+        >>> list(parsedag("+2<2+1/2"))
+        [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [0])), ('n', (3, [2, 1]))]
+
+    Placing a label:
+
+        >>> list(parsedag("+1 :mylabel +1"))
+        [('n', (0, [-1])), ('l', (0, 'mylabel')), ('n', (1, [0]))]
+
+    An empty label (silly, really):
+
+        >>> list(parsedag("+1:+1"))
+        [('n', (0, [-1])), ('l', (0, '')), ('n', (1, [0]))]
+
+    Fork and join, but with labels instead of numeric back references:
+
+        >>> list(parsedag("+1:f +1:p2 *f */p2"))
+        [('n', (0, [-1])), ('l', (0, 'f')), ('n', (1, [0])), ('l', (1, 'p2')),
+         ('n', (2, [0])), ('n', (3, [2, 1]))]
+
+        >>> list(parsedag("+1:f +1:p2 <f +1 /p2"))
+        [('n', (0, [-1])), ('l', (0, 'f')), ('n', (1, [0])), ('l', (1, 'p2')),
+         ('n', (2, [0])), ('n', (3, [2, 1]))]
+
+    Restarting from the root:
+
+        >>> list(parsedag("+1 $ +1"))
+        [('n', (0, [-1])), ('n', (1, [-1]))]
+
+    Annotations, which are meant to introduce sticky state for subsequent nodes:
+
+        >>> list(parsedag("+1 @ann +1"))
+        [('n', (0, [-1])), ('a', 'ann'), ('n', (1, [0]))]
+
+        >>> list(parsedag('+1 @"my annotation" +1'))
+        [('n', (0, [-1])), ('a', 'my annotation'), ('n', (1, [0]))]
+
+    Commands, which are meant to operate on the most recently created node:
+
+        >>> list(parsedag("+1 !cmd +1"))
+        [('n', (0, [-1])), ('c', 'cmd'), ('n', (1, [0]))]
+
+        >>> list(parsedag('+1 !"my command" +1'))
+        [('n', (0, [-1])), ('c', 'my command'), ('n', (1, [0]))]
+
+        >>> list(parsedag('+1 !!my command line\\n +1'))
+        [('n', (0, [-1])), ('C', 'my command line'), ('n', (1, [0]))]
+
+    Comments, which extend to the end of the line:
+
+        >>> list(parsedag('+1 # comment\\n+1'))
+        [('n', (0, [-1])), ('n', (1, [0]))]
+
+    Error:
+
+        >>> try: list(parsedag('+1 bad'))
+        ... except Exception, e: print e
+        invalid character in dag description: bad...
+
+    '''
+    if not desc:
+        return
+
+    wordchars = string.ascii_letters + string.digits
+
+    labels = {}
+    p1 = -1
+    r = 0
+
+    def resolve(ref):
+        if not ref:
+            return p1
+        elif ref[0] in string.digits:
+            return r - int(ref)
+        else:
+            return labels[ref]
+
+    chiter = (c for c in desc)
+
+    def nextch():
+        try:
+            return chiter.next()
+        except StopIteration:
+            return '\0'
+
+    def nextrun(c, allow):
+        s = ''
+        while c in allow:
+            s += c
+            c = nextch()
+        return c, s
+
+    def nextdelimited(c, limit, escape):
+        s = ''
+        while c != limit:
+            if c == escape:
+                c = nextch()
+            s += c
+            c = nextch()
+        return nextch(), s
+
+    def nextstring(c):
+        if c == '"':
+            return nextdelimited(nextch(), '"', '\\')
+        else:
+            return nextrun(c, wordchars)
+
+    c = nextch()
+    while c != '\0':
+        while c in string.whitespace:
+            c = nextch()
+        if c == '.':
+            yield 'n', (r, [p1])
+            p1 = r
+            r += 1
+            c = nextch()
+        elif c == '+':
+            c, digs = nextrun(nextch(), string.digits)
+            n = int(digs)
+            for i in xrange(0, n):
+                yield 'n', (r, [p1])
+                p1 = r
+                r += 1
+        elif c == '*' or c == '/':
+            if c == '*':
+                c = nextch()
+            c, pref = nextstring(c)
+            prefs = [pref]
+            while c == '/':
+                c, pref = nextstring(nextch())
+                prefs.append(pref)
+            ps = [resolve(ref) for ref in prefs]
+            yield 'n', (r, ps)
+            p1 = r
+            r += 1
+        elif c == '<':
+            c, ref = nextstring(nextch())
+            p1 = resolve(ref)
+        elif c == ':':
+            c, name = nextstring(nextch())
+            labels[name] = p1
+            yield 'l', (p1, name)
+        elif c == '@':
+            c, text = nextstring(nextch())
+            yield 'a', text
+        elif c == '!':
+            c = nextch()
+            if c == '!':
+                cmd = ''
+                c = nextch()
+                while c not in '\n\r\0':
+                    cmd += c
+                    c = nextch()
+                yield 'C', cmd
+            else:
+                c, cmd = nextstring(c)
+                yield 'c', cmd
+        elif c == '#':
+            while c not in '\n\r\0':
+                c = nextch()
+        elif c == '$':
+            p1 = -1
+            c = nextch()
+        elif c == '\0':
+            return # in case it was preceded by whitespace
+        else:
+            s = ''
+            i = 0
+            while c != '\0' and i < 10:
+                s += c
+                i += 1
+                c = nextch()
+            raise util.Abort("invalid character in dag description: %s..." % s)
+
+def dagtextlines(events,
+                 addspaces=True,
+                 wraplabels=False,
+                 wrapannotations=False,
+                 wrapcommands=False,
+                 wrapnonlinear=False,
+                 usedots=False,
+                 maxlinewidth=70):
+    '''generates single lines for dagtext()'''
+
+    def wrapstring(text):
+        if re.match("^[0-9a-z]*$", text):
+            return text
+        return '"' + text.replace('\\', '\\\\').replace('"', '\"') + '"'
+
+    def gen():
+        labels = {}
+        run = 0
+        wantr = 0
+        needroot = False
+        for kind, data in events:
+            if kind == 'n':
+                r, ps = data
+
+                # sanity check
+                if r != wantr:
+                    raise util.Abort("Expected id %i, got %i" % (wantr, r))
+                if not ps:
+                    ps = [-1]
+                else:
+                    for p in ps:
+                        if p >= r:
+                            raise util.Abort("Parent id %i is larger than "
+                                             "current id %i" % (p, r))
+                wantr += 1
+
+                # new root?
+                p1 = r - 1
+                if len(ps) == 1 and ps[0] == -1:
+                    if needroot:
+                        if run:
+                            yield '+' + str(run)
+                            run = 0
+                        if wrapnonlinear:
+                            yield '\n'
+                        yield '$'
+                        p1 = -1
+                    else:
+                        needroot = True
+                if len(ps) == 1 and ps[0] == p1:
+                    if usedots:
+                        yield "."
+                    else:
+                        run += 1
+                else:
+                    if run:
+                        yield '+' + str(run)
+                        run = 0
+                    if wrapnonlinear:
+                        yield '\n'
+                    prefs = []
+                    for p in ps:
+                        if p == p1:
+                            prefs.append('')
+                        elif p in labels:
+                            prefs.append(labels[p])
+                        else:
+                            prefs.append(str(r - p))
+                    yield '*' + '/'.join(prefs)
+            else:
+                if run:
+                    yield '+' + str(run)
+                    run = 0
+                if kind == 'l':
+                    rid, name = data
+                    labels[rid] = name
+                    yield ':' + name
+                    if wraplabels:
+                        yield '\n'
+                elif kind == 'c':
+                    yield '!' + wrapstring(data)
+                    if wrapcommands:
+                        yield '\n'
+                elif kind == 'C':
+                    yield '!!' + data
+                    yield '\n'
+                elif kind == 'a':
+                    if wrapannotations:
+                        yield '\n'
+                    yield '@' + wrapstring(data)
+                elif kind == '#':
+                    yield '#' + data
+                    yield '\n'
+                else:
+                    raise util.Abort("invalid event type in dag: "
+                                     + format((type, data)))
+        if run:
+            yield '+' + str(run)
+
+    line = ''
+    for part in gen():
+        if part == '\n':
+            if line:
+                yield line
+                line = ''
+        else:
+            if len(line) + len(part) >= maxlinewidth:
+                yield line
+                line = ''
+            elif addspaces and line and part != '.':
+                line += ' '
+            line += part
+    if line:
+        yield line
+
+def dagtext(dag,
+            addspaces=True,
+            wraplabels=False,
+            wrapannotations=False,
+            wrapcommands=False,
+            wrapnonlinear=False,
+            usedots=False,
+            maxlinewidth=70):
+    '''generates lines of a textual representation for a dag event stream
+
+    events should generate what parsedag() does, so:
+
+      ('n', (id, [parentids])) for node creation
+      ('l', (id, labelname)) for labels on nodes
+      ('a', text) for annotations
+      ('c', text) for commands
+      ('C', text) for line commands ('!!')
+      ('#', text) for comment lines
+
+    Parent nodes must come before child nodes.
+
+    Examples
+    --------
+
+    Linear run:
+
+        >>> dagtext([('n', (0, [-1])), ('n', (1, [0]))])
+        '+2'
+
+    Two roots:
+
+        >>> dagtext([('n', (0, [-1])), ('n', (1, [-1]))])
+        '+1 $ +1'
+
+    Fork and join:
+
+        >>> dagtext([('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [0])),
+        ...          ('n', (3, [2, 1]))])
+        '+2 *2 */2'
+
+    Fork and join with labels:
+
+        >>> dagtext([('n', (0, [-1])), ('l', (0, 'f')), ('n', (1, [0])),
+        ...          ('l', (1, 'p2')), ('n', (2, [0])), ('n', (3, [2, 1]))])
+        '+1 :f +1 :p2 *f */p2'
+
+    Annotations:
+
+        >>> dagtext([('n', (0, [-1])), ('a', 'ann'), ('n', (1, [0]))])
+        '+1 @ann +1'
+
+        >>> dagtext([('n', (0, [-1])), ('a', 'my annotation'), ('n', (1, [0]))])
+        '+1 @"my annotation" +1'
+
+    Commands:
+
+        >>> dagtext([('n', (0, [-1])), ('c', 'cmd'), ('n', (1, [0]))])
+        '+1 !cmd +1'
+
+        >>> dagtext([('n', (0, [-1])), ('c', 'my command'), ('n', (1, [0]))])
+        '+1 !"my command" +1'
+
+        >>> dagtext([('n', (0, [-1])), ('C', 'my command line'), ('n', (1, [0]))])
+        '+1 !!my command line\\n+1'
+
+    Comments:
+
+        >>> dagtext([('n', (0, [-1])), ('#', ' comment'), ('n', (1, [0]))])
+        '+1 # comment\\n+1'
+
+        >>> dagtext([])
+        ''
+
+    Combining parsedag and dagtext:
+
+        >>> dagtext(parsedag('+1 :f +1 :p2 *f */p2'))
+        '+1 :f +1 :p2 *f */p2'
+
+    '''
+    return "\n".join(dagtextlines(dag,
+                                  addspaces,
+                                  wraplabels,
+                                  wrapannotations,
+                                  wrapcommands,
+                                  wrapnonlinear,
+                                  usedots,
+                                  maxlinewidth))