ia64/xen-unstable

view tools/python/xen/xend/sxp.py @ 6552:a9873d384da4

Merge.
author adsharma@los-vmm.sc.intel.com
date Thu Aug 25 12:24:48 2005 -0700 (2005-08-25)
parents 112d44270733 fa0754a9f64f
children dfaf788ab18c
line source
1 #!/usr/bin/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 else:
271 self.state.fn = self.state_octal
272 self.state.val = 0
273 self.input_char(c)
275 def state_octal(self, c):
276 def octaldigit(c):
277 self.state.val *= 8
278 self.state.val += ord(c) - ord('0')
279 self.state.buf += c
280 if self.state.val < 0 or self.state.val > 0xff:
281 raise ParseError(self, "invalid octal escape: out of range " + self.state.buf)
282 if len(self.state.buf) == 3:
283 octaldone()
285 def octaldone():
286 d = chr(self.state.val)
287 self.state.parent.buf += d
288 self.pop_state()
290 if self.at_eof():
291 raise ParseError(self, "unexpected EOF")
292 elif '0' <= c <= '7':
293 octaldigit(c)
294 elif len(self.buf):
295 octaldone()
296 self.input_char(c)
298 def state_hex(self, c):
299 def hexdone():
300 d = chr(self.state.val)
301 self.state.parent.buf += d
302 self.pop_state()
304 def hexdigit(c, d):
305 self.state.val *= 16
306 self.state.val += ord(c) - ord(d)
307 self.state.buf += c
308 if self.state.val < 0 or self.state.val > 0xff:
309 raise ParseError(self, "invalid hex escape: out of range " + self.state.buf)
310 if len(self.state.buf) == 2:
311 hexdone()
313 if self.at_eof():
314 raise ParseError(self, "unexpected EOF")
315 elif '0' <= c <= '9':
316 hexdigit(c, '0')
317 elif 'A' <= c <= 'F':
318 hexdigit(c, 'A')
319 elif 'a' <= c <= 'f':
320 hexdigit(c, 'a')
321 elif len(buf):
322 hexdone()
323 self.input_char(c)
325 def begin_atom(self, c):
326 self.push_state(self.state_atom)
327 self.state.buf = c
329 def end_atom(self):
330 val = self.state.buf
331 self.state.parent.val.append(val)
332 self.pop_state()
334 def state_atom(self, c):
335 if self.at_eof():
336 self.end_atom()
337 elif (self.is_separator(c) or
338 self.in_space_class(c) or
339 self.in_comment_class(c)):
340 self.end_atom()
341 self.input_char(c)
342 else:
343 self.state.buf += c
345 def begin_list(self, c):
346 self.push_state(self.state_list)
348 def end_list(self):
349 val = self.state.val
350 self.state.parent.val.append(val)
351 self.pop_state()
353 def state_list(self, c):
354 if self.at_eof():
355 raise ParseError(self, "unexpected EOF")
356 elif c == k_list_close:
357 self.end_list()
358 else:
359 self.state_start(c)
361 def atomp(sxpr):
362 """Check if an sxpr is an atom.
363 """
364 if sxpr.isalnum() or sxpr == '@':
365 return 1
366 for c in sxpr:
367 if c in string.whitespace: return 0
368 if c in '"\'\\(){}[]<>$#&%^': return 0
369 if c in string.ascii_letters: continue
370 if c in string.digits: continue
371 if c in '.-_:/~': continue
372 return 0
373 return 1
375 def show(sxpr, out=sys.stdout):
376 """Print an sxpr in bracketed (lisp-style) syntax.
377 """
378 if isinstance(sxpr, types.ListType):
379 out.write(k_list_open)
380 i = 0
381 for x in sxpr:
382 if i: out.write(' ')
383 show(x, out)
384 i += 1
385 out.write(k_list_close)
386 elif isinstance(sxpr, (types.IntType, types.FloatType)):
387 out.write(str(sxpr))
388 elif isinstance(sxpr, types.StringType) and atomp(sxpr):
389 out.write(sxpr)
390 else:
391 out.write(repr(str(sxpr)))
393 def show_xml(sxpr, out=sys.stdout):
394 """Print an sxpr in XML syntax.
395 """
396 if isinstance(sxpr, types.ListType):
397 element = name(sxpr)
398 out.write('<%s' % element)
399 for attr in attributes(sxpr):
400 out.write(' %s=%s' % (attr[0], attr[1]))
401 out.write('>')
402 i = 0
403 for x in children(sxpr):
404 if i: out.write(' ')
405 show_xml(x, out)
406 i += 1
407 out.write('</%s>' % element)
408 elif isinstance(sxpr, types.StringType) and atomp(sxpr):
409 out.write(sxpr)
410 else:
411 out.write(str(sxpr))
413 def elementp(sxpr, elt=None):
414 """Check if an sxpr is an element of the given type.
416 sxpr sxpr
417 elt element type
418 """
419 return (isinstance(sxpr, types.ListType)
420 and len(sxpr)
421 and (None == elt or sxpr[0] == elt))
423 def name(sxpr):
424 """Get the element name of an sxpr.
425 If the sxpr is not an element (i.e. it's an atomic value) its name
426 is None.
428 sxpr
430 returns name (None if not an element).
431 """
432 val = None
433 if isinstance(sxpr, types.StringType):
434 val = sxpr
435 elif isinstance(sxpr, types.ListType) and len(sxpr):
436 val = sxpr[0]
437 return val
439 def attributes(sxpr):
440 """Get the attribute list of an sxpr.
442 sxpr
444 returns attribute list
445 """
446 val = []
447 if isinstance(sxpr, types.ListType) and len(sxpr) > 1:
448 attr = sxpr[1]
449 if elementp(attr, k_attr_open):
450 val = attr[1:]
451 return val
453 def attribute(sxpr, key, val=None):
454 """Get an attribute of an sxpr.
456 sxpr sxpr
457 key attribute key
458 val default value (default None)
460 returns attribute value
461 """
462 for x in attributes(sxpr):
463 if x[0] == key:
464 val = x[1]
465 break
466 return val
468 def children(sxpr, elt=None):
469 """Get children of an sxpr.
471 sxpr sxpr
472 elt optional element type to filter by
474 returns children (filtered by elt if specified)
475 """
476 val = []
477 if isinstance(sxpr, types.ListType) and len(sxpr) > 1:
478 i = 1
479 x = sxpr[i]
480 if elementp(x, k_attr_open):
481 i += 1
482 val = sxpr[i : ]
483 if elt:
484 def iselt(x):
485 return elementp(x, elt)
486 val = filter(iselt, val)
487 return val
489 def child(sxpr, elt, val=None):
490 """Get the first child of the given element type.
492 sxpr sxpr
493 elt element type
494 val default value
495 """
496 for x in children(sxpr):
497 if elementp(x, elt):
498 val = x
499 break
500 return val
502 def child_at(sxpr, index, val=None):
503 """Get the child at the given index (zero-based).
505 sxpr sxpr
506 index index
507 val default value
508 """
509 kids = children(sxpr)
510 if len(kids) > index:
511 val = kids[index]
512 return val
514 def child0(sxpr, val=None):
515 """Get the zeroth child.
516 """
517 return child_at(sxpr, 0, val)
519 def child1(sxpr, val=None):
520 """Get the first child.
521 """
522 return child_at(sxpr, 1, val)
524 def child2(sxpr, val=None):
525 """Get the second child.
526 """
527 return child_at(sxpr, 2, val)
529 def child3(sxpr, val=None):
530 """Get the third child.
531 """
532 return child_at(sxpr, 3, val)
534 def child4(sxpr, val=None):
535 """Get the fourth child.
536 """
537 return child_at(sxpr, 4, val)
539 def child_value(sxpr, elt, val=None):
540 """Get the value of the first child of the given element type.
541 Assumes the child has an atomic value.
543 sxpr sxpr
544 elt element type
545 val default value
546 """
547 kid = child(sxpr, elt)
548 if kid:
549 val = child_at(kid, 0, val)
550 return val
552 def has_id(sxpr, id):
553 """Test if an s-expression has a given id.
554 """
555 return attribute(sxpr, 'id') == id
557 def with_id(sxpr, id, val=None):
558 """Find the first s-expression with a given id, at any depth.
560 sxpr s-exp or list
561 id id
562 val value if not found (default None)
564 return s-exp or val
565 """
566 if isinstance(sxpr, types.ListType):
567 for n in sxpr:
568 if has_id(n, id):
569 val = n
570 break
571 v = with_id(n, id)
572 if v is None: continue
573 val = v
574 break
575 return val
577 def child_with_id(sxpr, id, val=None):
578 """Find the first child with a given id.
580 sxpr s-exp or list
581 id id
582 val value if not found (default None)
584 return s-exp or val
585 """
586 if isinstance(sxpr, types.ListType):
587 for n in sxpr:
588 if has_id(n, id):
589 val = n
590 break
591 return val
593 def elements(sxpr, ctxt=None):
594 """Generate elements (at any depth).
595 Visit elements in pre-order.
596 Values generated are (node, context)
597 The context is None if there is no parent, otherwise
598 (index, parent, context) where index is the node's index w.r.t its parent,
599 and context is the parent's context.
601 sxpr s-exp
603 returns generator
604 """
605 yield (sxpr, ctxt)
606 i = 0
607 for n in children(sxpr):
608 if isinstance(n, types.ListType):
609 # Calling elements() recursively does not generate recursively,
610 # it just returns a generator object. So we must iterate over it.
611 for v in elements(n, (i, sxpr, ctxt)):
612 yield v
613 i += 1
615 def merge(s1, s2):
616 """Merge sxprs s1 and s2.
617 Returns an sxpr containing all the fields from s1 and s2, with
618 entries in s1 overriding s2. Recursively merges fields.
620 @param s1 sxpr
621 @param s2 sxpr
622 @return merged sxpr
623 """
624 if s1 is None:
625 val = s2
626 elif s2 is None:
627 val = s1
628 elif elementp(s1):
629 name1 = name(s1)
630 (m1, v1) = child_map(s1)
631 (m2, v2) = child_map(s2)
632 val = [name1]
633 for (k1, f1) in m1.items():
634 merge_list(val, f1, m2.get(k1, []))
635 for (k2, f2) in m2.items():
636 if k2 in m1: continue
637 val.extend(f2)
638 val.extend(v1)
639 else:
640 val = s1
641 return val
643 def merge_list(sxpr, l1, l2):
644 """Merge element lists l1 and l2 into sxpr.
645 The lists l1 and l2 are all element with the same name.
646 Values from l1 are merged with values in l2 and stored in sxpr.
647 If one list is longer than the other the excess values are used
648 as they are.
650 @param sxpr to merge into
651 @param l1 sxpr list
652 @param l2 sxpr list
653 @return modified sxpr
654 """
655 n1 = len(l1)
656 n2 = len(l2)
657 nmin = min(n1, n2)
658 for i in range(0, nmin):
659 sxpr.append(merge(l1[i], l2[i]))
660 for i in range(nmin, n1):
661 sxpr.append(l1[i])
662 for i in range(nmin, n2):
663 sxpr.append(l2[i])
664 return sxpr
666 def child_map(sxpr):
667 """Get a dict of the elements in sxpr and a list of its values.
668 The dict maps element name to the list of elements with that name,
669 and the list is the non-element children.
671 @param sxpr
672 @return (dict, list)
673 """
674 m = {}
675 v = []
676 for x in children(sxpr):
677 if elementp(x):
678 n = name(x)
679 l = m.get(n, [])
680 l.append(x)
681 m[n] = l
682 else:
683 v.append(x)
684 return (m, v)
686 def to_string(sxpr):
687 """Convert an sxpr to a string.
689 sxpr sxpr
690 returns string
691 """
692 io = StringIO()
693 show(sxpr, io)
694 io.seek(0)
695 val = io.getvalue()
696 io.close()
697 return val
699 def from_string(str):
700 """Create an sxpr by parsing a string.
702 str string
703 returns sxpr
704 """
705 io = StringIO(str)
706 vals = parse(io)
707 if vals is []:
708 return None
709 else:
710 return vals[0]
713 def all_from_string(str):
714 """Create an sxpr list by parsing a string.
716 str string
717 returns sxpr list
718 """
719 io = StringIO(str)
720 vals = parse(io)
721 return vals
723 def parse(io):
724 """Completely parse all input from 'io'.
726 io input file object
727 returns list of values, None if incomplete
728 raises ParseError on parse error
729 """
730 pin = Parser()
731 while 1:
732 buf = io.readline()
733 pin.input(buf)
734 if len(buf) == 0:
735 break
736 if pin.ready():
737 val = pin.get_all()
738 else:
739 val = None
740 return val
743 if __name__ == '__main__':
744 print ">main"
745 pin = Parser()
746 while 1:
747 buf = sys.stdin.read(1024)
748 #buf = sys.stdin.readline()
749 pin.input(buf)
750 while pin.ready():
751 val = pin.get_val()
752 print
753 print '****** val=', val
754 if len(buf) == 0:
755 break