dagparser.py
480 lines
| 14.4 KiB
| text/x-python
|
PythonLexer
/ mercurial / dagparser.py
|
r11335 | # 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. | ||||
|
r25941 | from __future__ import absolute_import | ||
import re | ||||
import string | ||||
from .i18n import _ | ||||
|
r26587 | from . import error | ||
|
r11335 | |||
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 | ||||
|
r17500 | ... <forkhere # set default parent to labeled fork node | ||
|
r11335 | ... +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 | ||||
|
r17500 | ... /mergethis # merge last node with labeled node | ||
|
r11335 | ... +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')) | ||||
|
r33682 | ... except Exception, e: print(e) | ||
|
r11335 | 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(): | ||||
|
r25170 | return next(chiter, '\0') | ||
|
r11335 | |||
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 | ||||
|
r12387 | elif c in '*/': | ||
|
r11335 | 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() | ||||
|
r26587 | raise error.Abort(_('invalid character in dag description: ' | ||
|
r16683 | '%s...') % s) | ||
|
r11335 | |||
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: | ||||
|
r26587 | raise error.Abort(_("expected id %i, got %i") % (wantr, r)) | ||
|
r11335 | if not ps: | ||
ps = [-1] | ||||
else: | ||||
for p in ps: | ||||
if p >= r: | ||||
|
r26587 | raise error.Abort(_("parent id %i is larger than " | ||
|
r12134 | "current id %i") % (p, r)) | ||
|
r11335 | 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: | ||||
|
r26587 | raise error.Abort(_("invalid event type in dag: %s") | ||
|
r11344 | % str((type, data))) | ||
|
r11335 | 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' | ||||
|
r16683 | >>> dagtext([('n', (0, [-1])), | ||
... ('a', 'my annotation'), | ||||
... ('n', (1, [0]))]) | ||||
|
r11335 | '+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' | ||||
|
r16683 | >>> dagtext([('n', (0, [-1])), | ||
... ('C', 'my command line'), | ||||
... ('n', (1, [0]))]) | ||||
|
r11335 | '+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)) | ||||