debuggers.hg

view tools/python/xen/xend/sxp.py @ 19975:e845326ae203

python: Remove tab indents.
Signed-off-by: Keir Fraser <keir.fraser@citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Tue Jul 14 14:43:19 2009 +0100 (2009-07-14)
parents 6f0b467a92c6
children 809b20f066fb
line source
1 #!/usr/bin/env python
2 #============================================================================
3 # This library is free software; you can redistribute it and/or
4 # modify it under the terms of version 2.1 of the GNU Lesser General Public
5 # License as published by the Free Software Foundation.
6 #
7 # This library is distributed in the hope that it will be useful,
8 # but WITHOUT ANY WARRANTY; without even the implied warranty of
9 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
10 # Lesser General Public License for more details.
11 #
12 # You should have received a copy of the GNU Lesser General Public
13 # License along with this library; if not, write to the Free Software
14 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
15 #============================================================================
16 # Copyright (C) 2004, 2005 Mike Wray <mike.wray@hp.com>
17 #============================================================================
19 """
20 Input-driven parsing for s-expression (sxp) format.
21 Create a parser: pin = Parser();
22 Then call pin.input(buf) with your input.
23 Call pin.input_eof() when done.
24 Use pin.read() to see if a value has been parsed, pin.get_val()
25 to get a parsed value. You can call ready and get_val at any time -
26 you don't have to wait until after calling input_eof.
28 """
29 from __future__ import generators
31 import sys
32 import types
33 import errno
34 import string
35 from StringIO import StringIO
37 __all__ = [
38 "mime_type",
39 "ParseError",
40 "Parser",
41 "atomp",
42 "show",
43 "show_xml",
44 "elementp",
45 "name",
46 "attributes",
47 "attribute",
48 "children",
49 "child",
50 "child_at",
51 "child0",
52 "child1",
53 "child2",
54 "child3",
55 "child4",
56 "child_value",
57 "has_id",
58 "with_id",
59 "child_with_id",
60 "elements",
61 "merge",
62 "to_string",
63 "from_string",
64 "all_from_string",
65 "parse",
66 ]
68 mime_type = "application/sxp"
70 escapes = {
71 'a': '\a',
72 'b': '\b',
73 't': '\t',
74 'n': '\n',
75 'v': '\v',
76 'f': '\f',
77 'r': '\r',
78 '\\': '\\',
79 '\'': '\'',
80 '\"': '\"'}
82 k_list_open = "("
83 k_list_close = ")"
84 k_attr_open = "@"
85 k_eval = "!"
87 escapes_rev = {}
88 for k in escapes:
89 escapes_rev[escapes[k]] = k
91 class ParseError(StandardError):
93 def __init__(self, parser, value):
94 self.parser = parser
95 self.value = value
97 def __str__(self):
98 return self.value
100 class ParserState:
102 def __init__(self, fn, parent=None):
103 self.parent = parent
104 self.buf = ''
105 self.val = []
106 self.delim = None
107 self.fn = fn
109 def push(self, fn):
110 return ParserState(fn, parent=self)
112 class Parser:
114 def __init__(self):
115 self.error = sys.stderr
116 self.reset()
118 def reset(self):
119 self.val = []
120 self.eof = 0
121 self.err = 0
122 self.line_no = 0
123 self.char_no = 0
124 self.state = None
126 def push_state(self, fn):
127 self.state = self.state.push(fn)
129 def pop_state(self):
130 val = self.state
131 self.state = self.state.parent
132 if self.state and self.state.fn == self.state_start:
133 # Return to start state - produce the value.
134 self.val += self.state.val
135 self.state.val = []
136 return val
138 def in_class(self, c, s):
139 return s.find(c) >= 0
141 def in_space_class(self, c):
142 return self.in_class(c, ' \t\n\v\f\r')
144 def is_separator(self, c):
145 return self.in_class(c, '{}()<>[]!;')
147 def in_comment_class(self, c):
148 return self.in_class(c, '#')
150 def in_string_quote_class(self, c):
151 return self.in_class(c, '"\'')
153 def in_printable_class(self, c):
154 return self.in_class(c, string.printable)
156 def set_error_stream(self, error):
157 self.error = error
159 def has_error(self):
160 return self.err > 0
162 def at_eof(self):
163 return self.eof
165 def input_eof(self):
166 self.eof = 1
167 self.input_char(-1)
169 def input(self, buf):
170 if not buf or len(buf) == 0:
171 self.input_eof()
172 else:
173 for c in buf:
174 self.input_char(c)
176 def input_char(self, c):
177 if self.at_eof():
178 pass
179 elif c == '\n':
180 self.line_no += 1
181 self.char_no = 0
182 else:
183 self.char_no += 1
185 if self.state is None:
186 self.begin_start(None)
187 self.state.fn(c)
189 def ready(self):
190 return len(self.val) > 0
192 def get_val(self):
193 v = self.val[0]
194 self.val = self.val[1:]
195 return v
197 def get_all(self):
198 return self.val
200 def begin_start(self, c):
201 self.state = ParserState(self.state_start)
203 def end_start(self):
204 self.val += self.state.val
205 self.pop_state()
207 def state_start(self, c):
208 if self.at_eof():
209 self.end_start()
210 elif self.in_space_class(c):
211 pass
212 elif self.in_comment_class(c):
213 self.begin_comment(c)
214 elif c == k_list_open:
215 self.begin_list(c)
216 elif c == k_list_close:
217 raise ParseError(self, "syntax error: "+c)
218 elif self.in_string_quote_class(c):
219 self.begin_string(c)
220 elif self.in_printable_class(c):
221 self.begin_atom(c)
222 elif c == chr(4):
223 # ctrl-D, EOT: end-of-text.
224 self.input_eof()
225 else:
226 raise ParseError(self, "invalid character: code %d" % ord(c))
228 def begin_comment(self, c):
229 self.push_state(self.state_comment)
230 self.state.buf += c
232 def end_comment(self):
233 self.pop_state()
235 def state_comment(self, c):
236 if c == '\n' or self.at_eof():
237 self.end_comment()
238 else:
239 self.state.buf += c
241 def begin_string(self, c):
242 self.push_state(self.state_string)
243 self.state.delim = c
245 def end_string(self):
246 val = self.state.buf
247 self.state.parent.val.append(val)
248 self.pop_state()
250 def state_string(self, c):
251 if self.at_eof():
252 raise ParseError(self, "unexpected EOF")
253 elif c == self.state.delim:
254 self.end_string()
255 elif c == '\\':
256 self.push_state(self.state_escape)
257 else:
258 self.state.buf += c
260 def state_escape(self, c):
261 if self.at_eof():
262 raise ParseError(self, "unexpected EOF")
263 d = escapes.get(c)
264 if d:
265 self.state.parent.buf += d
266 self.pop_state()
267 elif c == 'x':
268 self.state.fn = self.state_hex
269 self.state.val = 0
270 elif c in string.octdigits:
271 self.state.fn = self.state_octal
272 self.state.val = 0
273 self.input_char(c)
274 else:
275 # ignore escape if it doesn't match anything we know
276 self.state.parent.buf += '\\'
277 self.pop_state()
279 def state_octal(self, c):
280 def octaldigit(c):
281 self.state.val *= 8
282 self.state.val += ord(c) - ord('0')
283 self.state.buf += c
284 if self.state.val < 0 or self.state.val > 0xff:
285 raise ParseError(self, "invalid octal escape: out of range " + self.state.buf)
286 if len(self.state.buf) == 3:
287 octaldone()
289 def octaldone():
290 d = chr(self.state.val)
291 self.state.parent.buf += d
292 self.pop_state()
294 if self.at_eof():
295 raise ParseError(self, "unexpected EOF")
296 elif '0' <= c <= '7':
297 octaldigit(c)
298 elif len(self.state.buf):
299 octaldone()
300 self.input_char(c)
302 def state_hex(self, c):
303 def hexdone():
304 d = chr(self.state.val)
305 self.state.parent.buf += d
306 self.pop_state()
308 def hexdigit(c, d):
309 self.state.val *= 16
310 self.state.val += ord(c) - ord(d)
311 self.state.buf += c
312 if self.state.val < 0 or self.state.val > 0xff:
313 raise ParseError(self, "invalid hex escape: out of range " + self.state.buf)
314 if len(self.state.buf) == 2:
315 hexdone()
317 if self.at_eof():
318 raise ParseError(self, "unexpected EOF")
319 elif '0' <= c <= '9':
320 hexdigit(c, '0')
321 elif 'A' <= c <= 'F':
322 hexdigit(c, 'A')
323 elif 'a' <= c <= 'f':
324 hexdigit(c, 'a')
325 elif len(buf):
326 hexdone()
327 self.input_char(c)
329 def begin_atom(self, c):
330 self.push_state(self.state_atom)
331 self.state.buf = c
333 def end_atom(self):
334 val = self.state.buf
335 self.state.parent.val.append(val)
336 self.pop_state()
338 def state_atom(self, c):
339 if self.at_eof():
340 self.end_atom()
341 elif (self.is_separator(c) or
342 self.in_space_class(c) or
343 self.in_comment_class(c)):
344 self.end_atom()
345 self.input_char(c)
346 else:
347 self.state.buf += c
349 def begin_list(self, c):
350 self.push_state(self.state_list)
352 def end_list(self):
353 val = self.state.val
354 self.state.parent.val.append(val)
355 self.pop_state()
357 def state_list(self, c):
358 if self.at_eof():
359 raise ParseError(self, "unexpected EOF")
360 elif c == k_list_close:
361 self.end_list()
362 else:
363 self.state_start(c)
365 def atomp(sxpr):
366 """Check if an sxpr is an atom.
367 """
368 if sxpr.isalnum() or sxpr == '@':
369 return 1
370 for c in sxpr:
371 if c in string.whitespace: return 0
372 if c in '"\'\\(){}[]<>$#&%^': return 0
373 if c in string.ascii_letters: continue
374 if c in string.digits: continue
375 if c in '.-_:/~': continue
376 return 0
377 return 1
379 def show(sxpr, out=sys.stdout):
380 """Print an sxpr in bracketed (lisp-style) syntax.
381 """
382 if isinstance(sxpr, (types.ListType, types.TupleType)):
383 out.write(k_list_open)
384 i = 0
385 for x in sxpr:
386 if i: out.write(' ')
387 show(x, out)
388 i += 1
389 out.write(k_list_close)
390 elif isinstance(sxpr, (types.IntType, types.FloatType)):
391 out.write(str(sxpr))
392 elif isinstance(sxpr, types.StringType) and atomp(sxpr):
393 out.write(sxpr)
394 else:
395 out.write(repr(str(sxpr)))
397 def show_xml(sxpr, out=sys.stdout):
398 """Print an sxpr in XML syntax.
399 """
400 if isinstance(sxpr, (types.ListType, types.TupleType)):
401 element = name(sxpr)
402 out.write('<%s' % element)
403 for attr in attributes(sxpr):
404 out.write(' %s=%s' % (attr[0], attr[1]))
405 out.write('>')
406 i = 0
407 for x in children(sxpr):
408 if i: out.write(' ')
409 show_xml(x, out)
410 i += 1
411 out.write('</%s>' % element)
412 elif isinstance(sxpr, types.StringType) and atomp(sxpr):
413 out.write(sxpr)
414 else:
415 out.write(str(sxpr))
417 def elementp(sxpr, elt=None):
418 """Check if an sxpr is an element of the given type.
420 sxpr sxpr
421 elt element type
422 """
423 return (isinstance(sxpr, (types.ListType, types.TupleType))
424 and len(sxpr)
425 and (None == elt or sxpr[0] == elt))
427 def name(sxpr):
428 """Get the element name of an sxpr.
429 If the sxpr is not an element (i.e. it's an atomic value) its name
430 is None.
432 sxpr
434 returns name (None if not an element).
435 """
436 val = None
437 if isinstance(sxpr, types.StringType):
438 val = sxpr
439 elif isinstance(sxpr, (types.ListType, types.TupleType)) and len(sxpr):
440 val = sxpr[0]
441 return val
443 def attributes(sxpr):
444 """Get the attribute list of an sxpr.
446 sxpr
448 returns attribute list
449 """
450 val = []
451 if isinstance(sxpr, (types.ListType, types.TupleType)) and len(sxpr) > 1:
452 attr = sxpr[1]
453 if elementp(attr, k_attr_open):
454 val = attr[1:]
455 return val
457 def attribute(sxpr, key, val=None):
458 """Get an attribute of an sxpr.
460 sxpr sxpr
461 key attribute key
462 val default value (default None)
464 returns attribute value
465 """
466 for x in attributes(sxpr):
467 if x[0] == key:
468 val = x[1]
469 break
470 return val
472 def children(sxpr, elt=None):
473 """Get children of an sxpr.
475 sxpr sxpr
476 elt optional element type to filter by
478 returns children (filtered by elt if specified)
479 """
480 val = []
481 if isinstance(sxpr, (types.ListType, types.TupleType)) and len(sxpr) > 1:
482 i = 1
483 x = sxpr[i]
484 if elementp(x, k_attr_open):
485 i += 1
486 val = sxpr[i : ]
487 if elt:
488 def iselt(x):
489 return elementp(x, elt)
490 val = filter(iselt, val)
491 return val
493 def child(sxpr, elt, val=None):
494 """Get the first child of the given element type.
496 sxpr sxpr
497 elt element type
498 val default value
499 """
500 for x in children(sxpr):
501 if elementp(x, elt):
502 val = x
503 break
504 return val
506 def child_at(sxpr, index, val=None):
507 """Get the child at the given index (zero-based).
509 sxpr sxpr
510 index index
511 val default value
512 """
513 kids = children(sxpr)
514 if len(kids) > index:
515 val = kids[index]
516 return val
518 def child0(sxpr, val=None):
519 """Get the zeroth child.
520 """
521 return child_at(sxpr, 0, val)
523 def child1(sxpr, val=None):
524 """Get the first child.
525 """
526 return child_at(sxpr, 1, val)
528 def child2(sxpr, val=None):
529 """Get the second child.
530 """
531 return child_at(sxpr, 2, val)
533 def child3(sxpr, val=None):
534 """Get the third child.
535 """
536 return child_at(sxpr, 3, val)
538 def child4(sxpr, val=None):
539 """Get the fourth child.
540 """
541 return child_at(sxpr, 4, val)
543 def child_value(sxpr, elt, val=None):
544 """Get the value of the first child of the given element type.
545 Assumes the child has an atomic value.
547 sxpr sxpr
548 elt element type
549 val default value
550 """
551 kid = child(sxpr, elt)
552 if kid:
553 val = child_at(kid, 0, val)
554 return val
556 def has_id(sxpr, id):
557 """Test if an s-expression has a given id.
558 """
559 return attribute(sxpr, 'id') == id
561 def with_id(sxpr, id, val=None):
562 """Find the first s-expression with a given id, at any depth.
564 sxpr s-exp or list
565 id id
566 val value if not found (default None)
568 return s-exp or val
569 """
570 if isinstance(sxpr, (types.ListType, types.TupleType)):
571 for n in sxpr:
572 if has_id(n, id):
573 val = n
574 break
575 v = with_id(n, id)
576 if v is None: continue
577 val = v
578 break
579 return val
581 def child_with_id(sxpr, id, val=None):
582 """Find the first child with a given id.
584 sxpr s-exp or list
585 id id
586 val value if not found (default None)
588 return s-exp or val
589 """
590 if isinstance(sxpr, (types.ListType, types.TupleType)):
591 for n in sxpr:
592 if has_id(n, id):
593 val = n
594 break
595 return val
597 def elements(sxpr, ctxt=None):
598 """Generate elements (at any depth).
599 Visit elements in pre-order.
600 Values generated are (node, context)
601 The context is None if there is no parent, otherwise
602 (index, parent, context) where index is the node's index w.r.t its parent,
603 and context is the parent's context.
605 sxpr s-exp
607 returns generator
608 """
609 yield (sxpr, ctxt)
610 i = 0
611 for n in children(sxpr):
612 if isinstance(n, (types.ListType, types.TupleType)):
613 # Calling elements() recursively does not generate recursively,
614 # it just returns a generator object. So we must iterate over it.
615 for v in elements(n, (i, sxpr, ctxt)):
616 yield v
617 i += 1
619 def merge(s1, s2):
620 """Merge sxprs s1 and s2.
621 Returns an sxpr containing all the fields from s1 and s2, with
622 entries in s1 overriding s2. Recursively merges fields.
624 @param s1 sxpr
625 @param s2 sxpr
626 @return merged sxpr
627 """
628 if s1 is None:
629 val = s2
630 elif s2 is None:
631 val = s1
632 elif elementp(s1):
633 name1 = name(s1)
634 (m1, v1) = child_map(s1)
635 (m2, v2) = child_map(s2)
636 val = [name1]
637 for (k1, f1) in m1.items():
638 merge_list(val, f1, m2.get(k1, []))
639 for (k2, f2) in m2.items():
640 if k2 in m1: continue
641 val.extend(f2)
642 val.extend(v1)
643 else:
644 val = s1
645 return val
647 def merge_list(sxpr, l1, l2):
648 """Merge element lists l1 and l2 into sxpr.
649 The lists l1 and l2 are all element with the same name.
650 Values from l1 are merged with values in l2 and stored in sxpr.
651 If one list is longer than the other the excess values are used
652 as they are.
654 @param sxpr to merge into
655 @param l1 sxpr list
656 @param l2 sxpr list
657 @return modified sxpr
658 """
659 n1 = len(l1)
660 n2 = len(l2)
661 nmin = min(n1, n2)
662 for i in range(0, nmin):
663 sxpr.append(merge(l1[i], l2[i]))
664 for i in range(nmin, n1):
665 sxpr.append(l1[i])
666 for i in range(nmin, n2):
667 sxpr.append(l2[i])
668 return sxpr
670 def child_map(sxpr):
671 """Get a dict of the elements in sxpr and a list of its values.
672 The dict maps element name to the list of elements with that name,
673 and the list is the non-element children.
675 @param sxpr
676 @return (dict, list)
677 """
678 m = {}
679 v = []
680 for x in children(sxpr):
681 if elementp(x):
682 n = name(x)
683 l = m.get(n, [])
684 l.append(x)
685 m[n] = l
686 else:
687 v.append(x)
688 return (m, v)
690 def to_string(sxpr):
691 """Convert an sxpr to a string.
693 sxpr sxpr
694 returns string
695 """
696 io = StringIO()
697 show(sxpr, io)
698 io.seek(0)
699 val = io.getvalue()
700 io.close()
701 return val
703 def from_string(s):
704 """Create an sxpr by parsing a string.
706 s string
707 returns sxpr
708 """
709 if s == '':
710 return []
712 io = StringIO(s)
713 vals = parse(io)
714 if vals is []:
715 return None
716 else:
717 return vals[0]
720 def all_from_string(s):
721 """Create an sxpr list by parsing a string.
723 s string
724 returns sxpr list
725 """
726 io = StringIO(s)
727 vals = parse(io)
728 return vals
730 def parse(io):
731 """Completely parse all input from 'io'.
733 io input file object
734 returns list of values, None if incomplete
735 raises ParseError on parse error
736 """
737 pin = Parser()
738 while 1:
739 buf = io.readline()
740 pin.input(buf)
741 if len(buf) == 0:
742 break
743 if pin.ready():
744 val = pin.get_all()
745 else:
746 val = None
747 return val
750 if __name__ == '__main__':
751 print ">main"
752 pin = Parser()
753 while 1:
754 buf = sys.stdin.read(1024)
755 #buf = sys.stdin.readline()
756 pin.input(buf)
757 while pin.ready():
758 val = pin.get_val()
759 print
760 print '****** val=', val
761 if len(buf) == 0:
762 break