|
1 # dagparser.py - parser and generator for concise description of DAGs |
|
2 # |
|
3 # Copyright 2010 Peter Arrenbrecht <peter@arrenbrecht.ch> |
|
4 # |
|
5 # This software may be used and distributed according to the terms of the |
|
6 # GNU General Public License version 2 or any later version. |
|
7 |
|
8 import re, string |
|
9 import util |
|
10 from i18n import _ |
|
11 |
|
12 def parsedag(desc): |
|
13 '''parses a DAG from a concise textual description; generates events |
|
14 |
|
15 "+n" is a linear run of n nodes based on the current default parent |
|
16 "." is a single node based on the current default parent |
|
17 "$" resets the default parent to -1 (implied at the start); |
|
18 otherwise the default parent is always the last node created |
|
19 "<p" sets the default parent to the backref p |
|
20 "*p" is a fork at parent p, where p is a backref |
|
21 "*p1/p2/.../pn" is a merge of parents p1..pn, where the pi are backrefs |
|
22 "/p2/.../pn" is a merge of the preceding node and p2..pn |
|
23 ":name" defines a label for the preceding node; labels can be redefined |
|
24 "@text" emits an annotation event for text |
|
25 "!command" emits an action event for the current node |
|
26 "!!my command\n" is like "!", but to the end of the line |
|
27 "#...\n" is a comment up to the end of the line |
|
28 |
|
29 Whitespace between the above elements is ignored. |
|
30 |
|
31 A backref is either |
|
32 * a number n, which references the node curr-n, where curr is the current |
|
33 node, or |
|
34 * the name of a label you placed earlier using ":name", or |
|
35 * empty to denote the default parent. |
|
36 |
|
37 All string valued-elements are either strictly alphanumeric, or must |
|
38 be enclosed in double quotes ("..."), with "\" as escape character. |
|
39 |
|
40 Generates sequence of |
|
41 |
|
42 ('n', (id, [parentids])) for node creation |
|
43 ('l', (id, labelname)) for labels on nodes |
|
44 ('a', text) for annotations |
|
45 ('c', command) for actions (!) |
|
46 ('C', command) for line actions (!!) |
|
47 |
|
48 Examples |
|
49 -------- |
|
50 |
|
51 Example of a complex graph (output not shown for brevity): |
|
52 |
|
53 >>> len(list(parsedag(""" |
|
54 ... |
|
55 ... +3 # 3 nodes in linear run |
|
56 ... :forkhere # a label for the last of the 3 nodes from above |
|
57 ... +5 # 5 more nodes on one branch |
|
58 ... :mergethis # label again |
|
59 ... <forkhere # set default parent to labelled fork node |
|
60 ... +10 # 10 more nodes on a parallel branch |
|
61 ... @stable # following nodes will be annotated as "stable" |
|
62 ... +5 # 5 nodes in stable |
|
63 ... !addfile # custom command; could trigger new file in next node |
|
64 ... +2 # two more nodes |
|
65 ... /mergethis # merge last node with labelled node |
|
66 ... +4 # 4 more nodes descending from merge node |
|
67 ... |
|
68 ... """))) |
|
69 34 |
|
70 |
|
71 Empty list: |
|
72 |
|
73 >>> list(parsedag("")) |
|
74 [] |
|
75 |
|
76 A simple linear run: |
|
77 |
|
78 >>> list(parsedag("+3")) |
|
79 [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))] |
|
80 |
|
81 Some non-standard ways to define such runs: |
|
82 |
|
83 >>> list(parsedag("+1+2")) |
|
84 [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))] |
|
85 |
|
86 >>> list(parsedag("+1*1*")) |
|
87 [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))] |
|
88 |
|
89 >>> list(parsedag("*")) |
|
90 [('n', (0, [-1]))] |
|
91 |
|
92 >>> list(parsedag("...")) |
|
93 [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))] |
|
94 |
|
95 A fork and a join, using numeric back references: |
|
96 |
|
97 >>> list(parsedag("+2*2*/2")) |
|
98 [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [0])), ('n', (3, [2, 1]))] |
|
99 |
|
100 >>> list(parsedag("+2<2+1/2")) |
|
101 [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [0])), ('n', (3, [2, 1]))] |
|
102 |
|
103 Placing a label: |
|
104 |
|
105 >>> list(parsedag("+1 :mylabel +1")) |
|
106 [('n', (0, [-1])), ('l', (0, 'mylabel')), ('n', (1, [0]))] |
|
107 |
|
108 An empty label (silly, really): |
|
109 |
|
110 >>> list(parsedag("+1:+1")) |
|
111 [('n', (0, [-1])), ('l', (0, '')), ('n', (1, [0]))] |
|
112 |
|
113 Fork and join, but with labels instead of numeric back references: |
|
114 |
|
115 >>> list(parsedag("+1:f +1:p2 *f */p2")) |
|
116 [('n', (0, [-1])), ('l', (0, 'f')), ('n', (1, [0])), ('l', (1, 'p2')), |
|
117 ('n', (2, [0])), ('n', (3, [2, 1]))] |
|
118 |
|
119 >>> list(parsedag("+1:f +1:p2 <f +1 /p2")) |
|
120 [('n', (0, [-1])), ('l', (0, 'f')), ('n', (1, [0])), ('l', (1, 'p2')), |
|
121 ('n', (2, [0])), ('n', (3, [2, 1]))] |
|
122 |
|
123 Restarting from the root: |
|
124 |
|
125 >>> list(parsedag("+1 $ +1")) |
|
126 [('n', (0, [-1])), ('n', (1, [-1]))] |
|
127 |
|
128 Annotations, which are meant to introduce sticky state for subsequent nodes: |
|
129 |
|
130 >>> list(parsedag("+1 @ann +1")) |
|
131 [('n', (0, [-1])), ('a', 'ann'), ('n', (1, [0]))] |
|
132 |
|
133 >>> list(parsedag('+1 @"my annotation" +1')) |
|
134 [('n', (0, [-1])), ('a', 'my annotation'), ('n', (1, [0]))] |
|
135 |
|
136 Commands, which are meant to operate on the most recently created node: |
|
137 |
|
138 >>> list(parsedag("+1 !cmd +1")) |
|
139 [('n', (0, [-1])), ('c', 'cmd'), ('n', (1, [0]))] |
|
140 |
|
141 >>> list(parsedag('+1 !"my command" +1')) |
|
142 [('n', (0, [-1])), ('c', 'my command'), ('n', (1, [0]))] |
|
143 |
|
144 >>> list(parsedag('+1 !!my command line\\n +1')) |
|
145 [('n', (0, [-1])), ('C', 'my command line'), ('n', (1, [0]))] |
|
146 |
|
147 Comments, which extend to the end of the line: |
|
148 |
|
149 >>> list(parsedag('+1 # comment\\n+1')) |
|
150 [('n', (0, [-1])), ('n', (1, [0]))] |
|
151 |
|
152 Error: |
|
153 |
|
154 >>> try: list(parsedag('+1 bad')) |
|
155 ... except Exception, e: print e |
|
156 invalid character in dag description: bad... |
|
157 |
|
158 ''' |
|
159 if not desc: |
|
160 return |
|
161 |
|
162 wordchars = string.ascii_letters + string.digits |
|
163 |
|
164 labels = {} |
|
165 p1 = -1 |
|
166 r = 0 |
|
167 |
|
168 def resolve(ref): |
|
169 if not ref: |
|
170 return p1 |
|
171 elif ref[0] in string.digits: |
|
172 return r - int(ref) |
|
173 else: |
|
174 return labels[ref] |
|
175 |
|
176 chiter = (c for c in desc) |
|
177 |
|
178 def nextch(): |
|
179 try: |
|
180 return chiter.next() |
|
181 except StopIteration: |
|
182 return '\0' |
|
183 |
|
184 def nextrun(c, allow): |
|
185 s = '' |
|
186 while c in allow: |
|
187 s += c |
|
188 c = nextch() |
|
189 return c, s |
|
190 |
|
191 def nextdelimited(c, limit, escape): |
|
192 s = '' |
|
193 while c != limit: |
|
194 if c == escape: |
|
195 c = nextch() |
|
196 s += c |
|
197 c = nextch() |
|
198 return nextch(), s |
|
199 |
|
200 def nextstring(c): |
|
201 if c == '"': |
|
202 return nextdelimited(nextch(), '"', '\\') |
|
203 else: |
|
204 return nextrun(c, wordchars) |
|
205 |
|
206 c = nextch() |
|
207 while c != '\0': |
|
208 while c in string.whitespace: |
|
209 c = nextch() |
|
210 if c == '.': |
|
211 yield 'n', (r, [p1]) |
|
212 p1 = r |
|
213 r += 1 |
|
214 c = nextch() |
|
215 elif c == '+': |
|
216 c, digs = nextrun(nextch(), string.digits) |
|
217 n = int(digs) |
|
218 for i in xrange(0, n): |
|
219 yield 'n', (r, [p1]) |
|
220 p1 = r |
|
221 r += 1 |
|
222 elif c in '*/': |
|
223 if c == '*': |
|
224 c = nextch() |
|
225 c, pref = nextstring(c) |
|
226 prefs = [pref] |
|
227 while c == '/': |
|
228 c, pref = nextstring(nextch()) |
|
229 prefs.append(pref) |
|
230 ps = [resolve(ref) for ref in prefs] |
|
231 yield 'n', (r, ps) |
|
232 p1 = r |
|
233 r += 1 |
|
234 elif c == '<': |
|
235 c, ref = nextstring(nextch()) |
|
236 p1 = resolve(ref) |
|
237 elif c == ':': |
|
238 c, name = nextstring(nextch()) |
|
239 labels[name] = p1 |
|
240 yield 'l', (p1, name) |
|
241 elif c == '@': |
|
242 c, text = nextstring(nextch()) |
|
243 yield 'a', text |
|
244 elif c == '!': |
|
245 c = nextch() |
|
246 if c == '!': |
|
247 cmd = '' |
|
248 c = nextch() |
|
249 while c not in '\n\r\0': |
|
250 cmd += c |
|
251 c = nextch() |
|
252 yield 'C', cmd |
|
253 else: |
|
254 c, cmd = nextstring(c) |
|
255 yield 'c', cmd |
|
256 elif c == '#': |
|
257 while c not in '\n\r\0': |
|
258 c = nextch() |
|
259 elif c == '$': |
|
260 p1 = -1 |
|
261 c = nextch() |
|
262 elif c == '\0': |
|
263 return # in case it was preceded by whitespace |
|
264 else: |
|
265 s = '' |
|
266 i = 0 |
|
267 while c != '\0' and i < 10: |
|
268 s += c |
|
269 i += 1 |
|
270 c = nextch() |
|
271 raise util.Abort(_("invalid character in dag description: %s...") % s) |
|
272 |
|
273 def dagtextlines(events, |
|
274 addspaces=True, |
|
275 wraplabels=False, |
|
276 wrapannotations=False, |
|
277 wrapcommands=False, |
|
278 wrapnonlinear=False, |
|
279 usedots=False, |
|
280 maxlinewidth=70): |
|
281 '''generates single lines for dagtext()''' |
|
282 |
|
283 def wrapstring(text): |
|
284 if re.match("^[0-9a-z]*$", text): |
|
285 return text |
|
286 return '"' + text.replace('\\', '\\\\').replace('"', '\"') + '"' |
|
287 |
|
288 def gen(): |
|
289 labels = {} |
|
290 run = 0 |
|
291 wantr = 0 |
|
292 needroot = False |
|
293 for kind, data in events: |
|
294 if kind == 'n': |
|
295 r, ps = data |
|
296 |
|
297 # sanity check |
|
298 if r != wantr: |
|
299 raise util.Abort(_("expected id %i, got %i") % (wantr, r)) |
|
300 if not ps: |
|
301 ps = [-1] |
|
302 else: |
|
303 for p in ps: |
|
304 if p >= r: |
|
305 raise util.Abort(_("parent id %i is larger than " |
|
306 "current id %i") % (p, r)) |
|
307 wantr += 1 |
|
308 |
|
309 # new root? |
|
310 p1 = r - 1 |
|
311 if len(ps) == 1 and ps[0] == -1: |
|
312 if needroot: |
|
313 if run: |
|
314 yield '+' + str(run) |
|
315 run = 0 |
|
316 if wrapnonlinear: |
|
317 yield '\n' |
|
318 yield '$' |
|
319 p1 = -1 |
|
320 else: |
|
321 needroot = True |
|
322 if len(ps) == 1 and ps[0] == p1: |
|
323 if usedots: |
|
324 yield "." |
|
325 else: |
|
326 run += 1 |
|
327 else: |
|
328 if run: |
|
329 yield '+' + str(run) |
|
330 run = 0 |
|
331 if wrapnonlinear: |
|
332 yield '\n' |
|
333 prefs = [] |
|
334 for p in ps: |
|
335 if p == p1: |
|
336 prefs.append('') |
|
337 elif p in labels: |
|
338 prefs.append(labels[p]) |
|
339 else: |
|
340 prefs.append(str(r - p)) |
|
341 yield '*' + '/'.join(prefs) |
|
342 else: |
|
343 if run: |
|
344 yield '+' + str(run) |
|
345 run = 0 |
|
346 if kind == 'l': |
|
347 rid, name = data |
|
348 labels[rid] = name |
|
349 yield ':' + name |
|
350 if wraplabels: |
|
351 yield '\n' |
|
352 elif kind == 'c': |
|
353 yield '!' + wrapstring(data) |
|
354 if wrapcommands: |
|
355 yield '\n' |
|
356 elif kind == 'C': |
|
357 yield '!!' + data |
|
358 yield '\n' |
|
359 elif kind == 'a': |
|
360 if wrapannotations: |
|
361 yield '\n' |
|
362 yield '@' + wrapstring(data) |
|
363 elif kind == '#': |
|
364 yield '#' + data |
|
365 yield '\n' |
|
366 else: |
|
367 raise util.Abort(_("invalid event type in dag: %s") |
|
368 % str((type, data))) |
|
369 if run: |
|
370 yield '+' + str(run) |
|
371 |
|
372 line = '' |
|
373 for part in gen(): |
|
374 if part == '\n': |
|
375 if line: |
|
376 yield line |
|
377 line = '' |
|
378 else: |
|
379 if len(line) + len(part) >= maxlinewidth: |
|
380 yield line |
|
381 line = '' |
|
382 elif addspaces and line and part != '.': |
|
383 line += ' ' |
|
384 line += part |
|
385 if line: |
|
386 yield line |
|
387 |
|
388 def dagtext(dag, |
|
389 addspaces=True, |
|
390 wraplabels=False, |
|
391 wrapannotations=False, |
|
392 wrapcommands=False, |
|
393 wrapnonlinear=False, |
|
394 usedots=False, |
|
395 maxlinewidth=70): |
|
396 '''generates lines of a textual representation for a dag event stream |
|
397 |
|
398 events should generate what parsedag() does, so: |
|
399 |
|
400 ('n', (id, [parentids])) for node creation |
|
401 ('l', (id, labelname)) for labels on nodes |
|
402 ('a', text) for annotations |
|
403 ('c', text) for commands |
|
404 ('C', text) for line commands ('!!') |
|
405 ('#', text) for comment lines |
|
406 |
|
407 Parent nodes must come before child nodes. |
|
408 |
|
409 Examples |
|
410 -------- |
|
411 |
|
412 Linear run: |
|
413 |
|
414 >>> dagtext([('n', (0, [-1])), ('n', (1, [0]))]) |
|
415 '+2' |
|
416 |
|
417 Two roots: |
|
418 |
|
419 >>> dagtext([('n', (0, [-1])), ('n', (1, [-1]))]) |
|
420 '+1 $ +1' |
|
421 |
|
422 Fork and join: |
|
423 |
|
424 >>> dagtext([('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [0])), |
|
425 ... ('n', (3, [2, 1]))]) |
|
426 '+2 *2 */2' |
|
427 |
|
428 Fork and join with labels: |
|
429 |
|
430 >>> dagtext([('n', (0, [-1])), ('l', (0, 'f')), ('n', (1, [0])), |
|
431 ... ('l', (1, 'p2')), ('n', (2, [0])), ('n', (3, [2, 1]))]) |
|
432 '+1 :f +1 :p2 *f */p2' |
|
433 |
|
434 Annotations: |
|
435 |
|
436 >>> dagtext([('n', (0, [-1])), ('a', 'ann'), ('n', (1, [0]))]) |
|
437 '+1 @ann +1' |
|
438 |
|
439 >>> dagtext([('n', (0, [-1])), ('a', 'my annotation'), ('n', (1, [0]))]) |
|
440 '+1 @"my annotation" +1' |
|
441 |
|
442 Commands: |
|
443 |
|
444 >>> dagtext([('n', (0, [-1])), ('c', 'cmd'), ('n', (1, [0]))]) |
|
445 '+1 !cmd +1' |
|
446 |
|
447 >>> dagtext([('n', (0, [-1])), ('c', 'my command'), ('n', (1, [0]))]) |
|
448 '+1 !"my command" +1' |
|
449 |
|
450 >>> dagtext([('n', (0, [-1])), ('C', 'my command line'), ('n', (1, [0]))]) |
|
451 '+1 !!my command line\\n+1' |
|
452 |
|
453 Comments: |
|
454 |
|
455 >>> dagtext([('n', (0, [-1])), ('#', ' comment'), ('n', (1, [0]))]) |
|
456 '+1 # comment\\n+1' |
|
457 |
|
458 >>> dagtext([]) |
|
459 '' |
|
460 |
|
461 Combining parsedag and dagtext: |
|
462 |
|
463 >>> dagtext(parsedag('+1 :f +1 :p2 *f */p2')) |
|
464 '+1 :f +1 :p2 *f */p2' |
|
465 |
|
466 ''' |
|
467 return "\n".join(dagtextlines(dag, |
|
468 addspaces, |
|
469 wraplabels, |
|
470 wrapannotations, |
|
471 wrapcommands, |
|
472 wrapnonlinear, |
|
473 usedots, |
|
474 maxlinewidth)) |