diff options
Diffstat (limited to 'websdk/mercurial/dagparser.py')
| -rw-r--r--[l---------] | websdk/mercurial/dagparser.py | 475 |
1 files changed, 474 insertions, 1 deletions
diff --git a/websdk/mercurial/dagparser.py b/websdk/mercurial/dagparser.py index f94cbde..e02faa5 120000..100644 --- a/websdk/mercurial/dagparser.py +++ b/websdk/mercurial/dagparser.py @@ -1 +1,474 @@ -/usr/share/pyshared/mercurial/dagparser.py
\ No newline at end of file +# 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 +from i18n import _ + +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 in '*/': + 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: %s") + % str((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)) |