dagparser.py
515 lines
| 15.1 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 | |||
import re | ||||
import string | ||||
from .i18n import _ | ||||
|
r34207 | from . import ( | ||
error, | ||||
|
r34208 | pycompat, | ||
|
r37102 | ) | ||
|
r43346 | from .utils import stringutil | ||
|
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): | ||||
|
r34133 | >>> len(list(parsedag(b""" | ||
|
r11335 | ... | ||
... +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: | ||||
|
r34133 | >>> list(parsedag(b"")) | ||
|
r11335 | [] | ||
A simple linear run: | ||||
|
r34133 | >>> list(parsedag(b"+3")) | ||
|
r11335 | [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))] | ||
Some non-standard ways to define such runs: | ||||
|
r34133 | >>> list(parsedag(b"+1+2")) | ||
|
r11335 | [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))] | ||
|
r34133 | >>> list(parsedag(b"+1*1*")) | ||
|
r11335 | [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))] | ||
|
r34133 | >>> list(parsedag(b"*")) | ||
|
r11335 | [('n', (0, [-1]))] | ||
|
r34133 | >>> list(parsedag(b"...")) | ||
|
r11335 | [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))] | ||
A fork and a join, using numeric back references: | ||||
|
r34133 | >>> list(parsedag(b"+2*2*/2")) | ||
|
r11335 | [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [0])), ('n', (3, [2, 1]))] | ||
|
r34133 | >>> list(parsedag(b"+2<2+1/2")) | ||
|
r11335 | [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [0])), ('n', (3, [2, 1]))] | ||
Placing a label: | ||||
|
r34133 | >>> list(parsedag(b"+1 :mylabel +1")) | ||
|
r11335 | [('n', (0, [-1])), ('l', (0, 'mylabel')), ('n', (1, [0]))] | ||
An empty label (silly, really): | ||||
|
r34133 | >>> list(parsedag(b"+1:+1")) | ||
|
r11335 | [('n', (0, [-1])), ('l', (0, '')), ('n', (1, [0]))] | ||
Fork and join, but with labels instead of numeric back references: | ||||
|
r34133 | >>> list(parsedag(b"+1:f +1:p2 *f */p2")) | ||
|
r11335 | [('n', (0, [-1])), ('l', (0, 'f')), ('n', (1, [0])), ('l', (1, 'p2')), | ||
('n', (2, [0])), ('n', (3, [2, 1]))] | ||||
|
r34133 | >>> list(parsedag(b"+1:f +1:p2 <f +1 /p2")) | ||
|
r11335 | [('n', (0, [-1])), ('l', (0, 'f')), ('n', (1, [0])), ('l', (1, 'p2')), | ||
('n', (2, [0])), ('n', (3, [2, 1]))] | ||||
Restarting from the root: | ||||
|
r34133 | >>> list(parsedag(b"+1 $ +1")) | ||
|
r11335 | [('n', (0, [-1])), ('n', (1, [-1]))] | ||
Annotations, which are meant to introduce sticky state for subsequent nodes: | ||||
|
r34133 | >>> list(parsedag(b"+1 @ann +1")) | ||
|
r11335 | [('n', (0, [-1])), ('a', 'ann'), ('n', (1, [0]))] | ||
|
r34133 | >>> list(parsedag(b'+1 @"my annotation" +1')) | ||
|
r11335 | [('n', (0, [-1])), ('a', 'my annotation'), ('n', (1, [0]))] | ||
Commands, which are meant to operate on the most recently created node: | ||||
|
r34133 | >>> list(parsedag(b"+1 !cmd +1")) | ||
|
r11335 | [('n', (0, [-1])), ('c', 'cmd'), ('n', (1, [0]))] | ||
|
r34133 | >>> list(parsedag(b'+1 !"my command" +1')) | ||
|
r11335 | [('n', (0, [-1])), ('c', 'my command'), ('n', (1, [0]))] | ||
|
r34133 | >>> list(parsedag(b'+1 !!my command line\\n +1')) | ||
|
r11335 | [('n', (0, [-1])), ('C', 'my command line'), ('n', (1, [0]))] | ||
Comments, which extend to the end of the line: | ||||
|
r34133 | >>> list(parsedag(b'+1 # comment\\n+1')) | ||
|
r11335 | [('n', (0, [-1])), ('n', (1, [0]))] | ||
Error: | ||||
|
r34133 | >>> try: list(parsedag(b'+1 bad')) | ||
|
r34140 | ... except Exception as e: print(pycompat.sysstr(bytes(e))) | ||
|
r11335 | invalid character in dag description: bad... | ||
''' | ||||
if not desc: | ||||
return | ||||
|
r47545 | # pytype: disable=wrong-arg-types | ||
wordchars = pycompat.bytestr(string.ascii_letters + string.digits) | ||||
# pytype: enable=wrong-arg-types | ||||
|
r11335 | |||
labels = {} | ||||
p1 = -1 | ||||
r = 0 | ||||
def resolve(ref): | ||||
if not ref: | ||||
return p1 | ||||
|
r47545 | # pytype: disable=wrong-arg-types | ||
elif ref[0] in pycompat.bytestr(string.digits): | ||||
# pytype: enable=wrong-arg-types | ||||
|
r11335 | return r - int(ref) | ||
else: | ||||
return labels[ref] | ||||
|
r34209 | chiter = pycompat.iterbytestr(desc) | ||
|
r11335 | |||
def nextch(): | ||||
|
r43347 | return next(chiter, b'\0') | ||
|
r11335 | |||
def nextrun(c, allow): | ||||
|
r43347 | s = b'' | ||
|
r11335 | while c in allow: | ||
s += c | ||||
c = nextch() | ||||
return c, s | ||||
def nextdelimited(c, limit, escape): | ||||
|
r43347 | s = b'' | ||
|
r11335 | while c != limit: | ||
if c == escape: | ||||
c = nextch() | ||||
s += c | ||||
c = nextch() | ||||
return nextch(), s | ||||
def nextstring(c): | ||||
|
r43347 | if c == b'"': | ||
return nextdelimited(nextch(), b'"', b'\\') | ||||
|
r11335 | else: | ||
return nextrun(c, wordchars) | ||||
c = nextch() | ||||
|
r43347 | while c != b'\0': | ||
|
r47545 | # pytype: disable=wrong-arg-types | ||
while c in pycompat.bytestr(string.whitespace): | ||||
# pytype: enable=wrong-arg-types | ||||
|
r11335 | c = nextch() | ||
|
r43347 | if c == b'.': | ||
yield b'n', (r, [p1]) | ||||
|
r11335 | p1 = r | ||
r += 1 | ||||
c = nextch() | ||||
|
r43347 | elif c == b'+': | ||
|
r47545 | # pytype: disable=wrong-arg-types | ||
c, digs = nextrun(nextch(), pycompat.bytestr(string.digits)) | ||||
# pytype: enable=wrong-arg-types | ||||
|
r11335 | n = int(digs) | ||
|
r38806 | for i in pycompat.xrange(0, n): | ||
|
r43347 | yield b'n', (r, [p1]) | ||
|
r11335 | p1 = r | ||
r += 1 | ||||
|
r43347 | elif c in b'*/': | ||
if c == b'*': | ||||
|
r11335 | c = nextch() | ||
c, pref = nextstring(c) | ||||
prefs = [pref] | ||||
|
r43347 | while c == b'/': | ||
|
r11335 | c, pref = nextstring(nextch()) | ||
prefs.append(pref) | ||||
ps = [resolve(ref) for ref in prefs] | ||||
|
r43347 | yield b'n', (r, ps) | ||
|
r11335 | p1 = r | ||
r += 1 | ||||
|
r43347 | elif c == b'<': | ||
|
r11335 | c, ref = nextstring(nextch()) | ||
p1 = resolve(ref) | ||||
|
r43347 | elif c == b':': | ||
|
r11335 | c, name = nextstring(nextch()) | ||
labels[name] = p1 | ||||
|
r43347 | yield b'l', (p1, name) | ||
elif c == b'@': | ||||
|
r11335 | c, text = nextstring(nextch()) | ||
|
r43347 | yield b'a', text | ||
elif c == b'!': | ||||
|
r11335 | c = nextch() | ||
|
r43347 | if c == b'!': | ||
cmd = b'' | ||||
|
r11335 | c = nextch() | ||
|
r43347 | while c not in b'\n\r\0': | ||
|
r11335 | cmd += c | ||
c = nextch() | ||||
|
r43347 | yield b'C', cmd | ||
|
r11335 | else: | ||
c, cmd = nextstring(c) | ||||
|
r43347 | yield b'c', cmd | ||
elif c == b'#': | ||||
while c not in b'\n\r\0': | ||||
|
r11335 | c = nextch() | ||
|
r43347 | elif c == b'$': | ||
|
r11335 | p1 = -1 | ||
c = nextch() | ||||
|
r43347 | elif c == b'\0': | ||
|
r43346 | return # in case it was preceded by whitespace | ||
|
r11335 | else: | ||
|
r43347 | s = b'' | ||
|
r11335 | i = 0 | ||
|
r43347 | while c != b'\0' and i < 10: | ||
|
r11335 | s += c | ||
i += 1 | ||||
c = nextch() | ||||
|
r43346 | raise error.Abort( | ||
|
r43387 | _(b'invalid character in dag description: %s...') % s | ||
|
r43346 | ) | ||
|
r11335 | |||
|
r43346 | def dagtextlines( | ||
events, | ||||
addspaces=True, | ||||
wraplabels=False, | ||||
wrapannotations=False, | ||||
wrapcommands=False, | ||||
wrapnonlinear=False, | ||||
usedots=False, | ||||
maxlinewidth=70, | ||||
): | ||||
|
r11335 | '''generates single lines for dagtext()''' | ||
def wrapstring(text): | ||||
|
r43347 | if re.match(b"^[0-9a-z]*$", text): | ||
|
r11335 | return text | ||
|
r43347 | return b'"' + text.replace(b'\\', b'\\\\').replace(b'"', b'\"') + b'"' | ||
|
r11335 | |||
def gen(): | ||||
labels = {} | ||||
run = 0 | ||||
wantr = 0 | ||||
needroot = False | ||||
for kind, data in events: | ||||
|
r43347 | if kind == b'n': | ||
|
r11335 | r, ps = data | ||
# sanity check | ||||
if r != wantr: | ||||
|
r43347 | raise error.Abort(_(b"expected id %i, got %i") % (wantr, r)) | ||
|
r11335 | if not ps: | ||
ps = [-1] | ||||
else: | ||||
for p in ps: | ||||
if p >= r: | ||||
|
r43346 | raise error.Abort( | ||
_( | ||||
|
r43347 | b"parent id %i is larger than " | ||
b"current id %i" | ||||
|
r43346 | ) | ||
% (p, r) | ||||
) | ||||
|
r11335 | wantr += 1 | ||
# new root? | ||||
p1 = r - 1 | ||||
if len(ps) == 1 and ps[0] == -1: | ||||
if needroot: | ||||
if run: | ||||
|
r43347 | yield b'+%d' % run | ||
|
r11335 | run = 0 | ||
if wrapnonlinear: | ||||
|
r43347 | yield b'\n' | ||
yield b'$' | ||||
|
r11335 | p1 = -1 | ||
else: | ||||
needroot = True | ||||
if len(ps) == 1 and ps[0] == p1: | ||||
if usedots: | ||||
|
r43347 | yield b"." | ||
|
r11335 | else: | ||
run += 1 | ||||
else: | ||||
if run: | ||||
|
r43347 | yield b'+%d' % run | ||
|
r11335 | run = 0 | ||
if wrapnonlinear: | ||||
|
r43347 | yield b'\n' | ||
|
r11335 | prefs = [] | ||
for p in ps: | ||||
if p == p1: | ||||
|
r43347 | prefs.append(b'') | ||
|
r11335 | elif p in labels: | ||
prefs.append(labels[p]) | ||||
else: | ||||
|
r43347 | prefs.append(b'%d' % (r - p)) | ||
yield b'*' + b'/'.join(prefs) | ||||
|
r11335 | else: | ||
if run: | ||||
|
r43347 | yield b'+%d' % run | ||
|
r11335 | run = 0 | ||
|
r43347 | if kind == b'l': | ||
|
r11335 | rid, name = data | ||
labels[rid] = name | ||||
|
r43347 | yield b':' + name | ||
|
r11335 | if wraplabels: | ||
|
r43347 | yield b'\n' | ||
elif kind == b'c': | ||||
yield b'!' + wrapstring(data) | ||||
|
r11335 | if wrapcommands: | ||
|
r43347 | yield b'\n' | ||
elif kind == b'C': | ||||
yield b'!!' + data | ||||
yield b'\n' | ||||
elif kind == b'a': | ||||
|
r11335 | if wrapannotations: | ||
|
r43347 | yield b'\n' | ||
yield b'@' + wrapstring(data) | ||||
elif kind == b'#': | ||||
yield b'#' + data | ||||
yield b'\n' | ||||
|
r11335 | else: | ||
|
r43346 | raise error.Abort( | ||
|
r43387 | _(b"invalid event type in dag: ('%s', '%s')") | ||
|
r43346 | % ( | ||
stringutil.escapestr(kind), | ||||
stringutil.escapestr(data), | ||||
) | ||||
) | ||||
|
r11335 | if run: | ||
|
r43347 | yield b'+%d' % run | ||
|
r11335 | |||
|
r43347 | line = b'' | ||
|
r11335 | for part in gen(): | ||
|
r43347 | if part == b'\n': | ||
|
r11335 | if line: | ||
yield line | ||||
|
r43347 | line = b'' | ||
|
r11335 | else: | ||
if len(line) + len(part) >= maxlinewidth: | ||||
yield line | ||||
|
r43347 | line = b'' | ||
elif addspaces and line and part != b'.': | ||||
line += b' ' | ||||
|
r11335 | line += part | ||
if line: | ||||
yield line | ||||
|
r43346 | |||
def dagtext( | ||||
dag, | ||||
addspaces=True, | ||||
wraplabels=False, | ||||
wrapannotations=False, | ||||
wrapcommands=False, | ||||
wrapnonlinear=False, | ||||
usedots=False, | ||||
maxlinewidth=70, | ||||
): | ||||
|
r46554 | """generates lines of a textual representation for a dag event stream | ||
|
r11335 | |||
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: | ||||
|
r34133 | >>> dagtext([(b'n', (0, [-1])), (b'n', (1, [0]))]) | ||
|
r11335 | '+2' | ||
Two roots: | ||||
|
r34133 | >>> dagtext([(b'n', (0, [-1])), (b'n', (1, [-1]))]) | ||
|
r11335 | '+1 $ +1' | ||
Fork and join: | ||||
|
r34133 | >>> dagtext([(b'n', (0, [-1])), (b'n', (1, [0])), (b'n', (2, [0])), | ||
... (b'n', (3, [2, 1]))]) | ||||
|
r11335 | '+2 *2 */2' | ||
Fork and join with labels: | ||||
|
r34133 | >>> dagtext([(b'n', (0, [-1])), (b'l', (0, b'f')), (b'n', (1, [0])), | ||
... (b'l', (1, b'p2')), (b'n', (2, [0])), (b'n', (3, [2, 1]))]) | ||||
|
r11335 | '+1 :f +1 :p2 *f */p2' | ||
Annotations: | ||||
|
r34133 | >>> dagtext([(b'n', (0, [-1])), (b'a', b'ann'), (b'n', (1, [0]))]) | ||
|
r11335 | '+1 @ann +1' | ||
|
r34133 | >>> dagtext([(b'n', (0, [-1])), | ||
... (b'a', b'my annotation'), | ||||
... (b'n', (1, [0]))]) | ||||
|
r11335 | '+1 @"my annotation" +1' | ||
Commands: | ||||
|
r34133 | >>> dagtext([(b'n', (0, [-1])), (b'c', b'cmd'), (b'n', (1, [0]))]) | ||
|
r11335 | '+1 !cmd +1' | ||
|
r34133 | >>> dagtext([(b'n', (0, [-1])), | ||
... (b'c', b'my command'), | ||||
... (b'n', (1, [0]))]) | ||||
|
r11335 | '+1 !"my command" +1' | ||
|
r34133 | >>> dagtext([(b'n', (0, [-1])), | ||
... (b'C', b'my command line'), | ||||
... (b'n', (1, [0]))]) | ||||
|
r11335 | '+1 !!my command line\\n+1' | ||
Comments: | ||||
|
r34133 | >>> dagtext([(b'n', (0, [-1])), (b'#', b' comment'), (b'n', (1, [0]))]) | ||
|
r11335 | '+1 # comment\\n+1' | ||
>>> dagtext([]) | ||||
'' | ||||
Combining parsedag and dagtext: | ||||
|
r34133 | >>> dagtext(parsedag(b'+1 :f +1 :p2 *f */p2')) | ||
|
r11335 | '+1 :f +1 :p2 *f */p2' | ||
|
r46554 | """ | ||
|
r43347 | return b"\n".join( | ||
|
r43346 | dagtextlines( | ||
dag, | ||||
addspaces, | ||||
wraplabels, | ||||
wrapannotations, | ||||
wrapcommands, | ||||
wrapnonlinear, | ||||
usedots, | ||||
maxlinewidth, | ||||
) | ||||
) | ||||