|
|
# 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))
|
|
|
|
