source: trunk/packages/xen-3.1/xen-3.1/tools/python/xen/xend/sxp.py @ 34

Last change on this file since 34 was 34, checked in by hartmans, 18 years ago

Add xen and xen-common

  • Property svn:mime-type set to text/script
File size: 18.7 KB
Line 
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#============================================================================
18
19"""
20Input-driven parsing for s-expression (sxp) format.
21Create a parser: pin = Parser();
22Then call pin.input(buf) with your input.
23Call pin.input_eof() when done.
24Use pin.read() to see if a value has been parsed, pin.get_val()
25to get a parsed value. You can call ready and get_val at any time -
26you don't have to wait until after calling input_eof.
27
28"""
29from __future__ import generators
30
31import sys
32import types
33import errno
34import string
35from StringIO import StringIO
36
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    ]
67
68mime_type = "application/sxp"
69
70escapes = {
71    'a': '\a',
72    'b': '\b',
73    't': '\t',
74    'n': '\n',
75    'v': '\v',
76    'f': '\f',
77    'r': '\r',
78    '\\': '\\',
79    '\'': '\'',
80    '\"': '\"'}
81
82k_list_open  = "("
83k_list_close = ")"
84k_attr_open  = "@"
85k_eval       = "!"
86
87escapes_rev = {}
88for k in escapes:
89    escapes_rev[escapes[k]] = k
90
91class ParseError(StandardError):
92
93    def __init__(self, parser, value):
94        self.parser = parser
95        self.value = value
96
97    def __str__(self):
98        return self.value
99
100class ParserState:
101
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
108
109    def push(self, fn):
110        return ParserState(fn, parent=self)
111   
112class Parser:
113
114    def __init__(self):
115        self.error = sys.stderr
116        self.reset()
117
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
125
126    def push_state(self, fn):
127        self.state = self.state.push(fn)
128
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
137
138    def in_class(self, c, s):
139        return s.find(c) >= 0
140       
141    def in_space_class(self, c):
142        return self.in_class(c, ' \t\n\v\f\r')
143
144    def is_separator(self, c):
145        return self.in_class(c, '{}()<>[]!;')
146
147    def in_comment_class(self, c):
148        return self.in_class(c, '#')
149
150    def in_string_quote_class(self, c):
151        return self.in_class(c, '"\'')
152
153    def in_printable_class(self, c):
154        return self.in_class(c, string.printable)
155
156    def set_error_stream(self, error):
157        self.error = error
158
159    def has_error(self):
160        return self.err > 0
161
162    def at_eof(self):
163        return self.eof
164
165    def input_eof(self):
166        self.eof = 1
167        self.input_char(-1)
168
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)
175
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
184
185        if self.state is None:
186            self.begin_start(None)
187        self.state.fn(c)
188
189    def ready(self):
190        return len(self.val) > 0
191
192    def get_val(self):
193        v = self.val[0]
194        self.val = self.val[1:]
195        return v
196
197    def get_all(self):
198        return self.val
199
200    def begin_start(self, c):
201        self.state = ParserState(self.state_start)
202
203    def end_start(self):
204        self.val += self.state.val
205        self.pop_state()
206   
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))
227
228    def begin_comment(self, c):
229        self.push_state(self.state_comment)
230        self.state.buf += c
231
232    def end_comment(self):
233        self.pop_state()
234   
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
240
241    def begin_string(self, c):
242        self.push_state(self.state_string)
243        self.state.delim = c
244
245    def end_string(self):
246        val = self.state.buf
247        self.state.parent.val.append(val)
248        self.pop_state()
249       
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
259
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()
278
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()
288               
289        def octaldone():
290            d = chr(self.state.val)
291            self.state.parent.buf += d
292            self.pop_state()
293           
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)
301
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()
307           
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()
316           
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)
328
329    def begin_atom(self, c):
330        self.push_state(self.state_atom)
331        self.state.buf = c
332
333    def end_atom(self):
334        val = self.state.buf
335        self.state.parent.val.append(val)
336        self.pop_state()
337   
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
348
349    def begin_list(self, c):
350        self.push_state(self.state_list)
351
352    def end_list(self):
353        val = self.state.val
354        self.state.parent.val.append(val)
355        self.pop_state()
356
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)
364
365def 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
378   
379def 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)))
396
397def 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))
416
417def elementp(sxpr, elt=None):
418    """Check if an sxpr is an element of the given type.
419
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))
426
427def 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.
431
432    sxpr
433
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
442
443def attributes(sxpr):
444    """Get the attribute list of an sxpr.
445
446    sxpr
447
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
456
457def attribute(sxpr, key, val=None):
458    """Get an attribute of an sxpr.
459
460    sxpr sxpr
461    key  attribute key
462    val  default value (default None)
463
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
471
472def children(sxpr, elt=None):
473    """Get children of an sxpr.
474
475    sxpr sxpr
476    elt  optional element type to filter by
477
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
492
493def child(sxpr, elt, val=None):
494    """Get the first child of the given element type.
495
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
505
506def child_at(sxpr, index, val=None):
507    """Get the child at the given index (zero-based).
508
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
517
518def child0(sxpr, val=None):
519    """Get the zeroth child.
520    """
521    return child_at(sxpr, 0, val)
522
523def child1(sxpr, val=None):
524    """Get the first child.
525    """
526    return child_at(sxpr, 1, val)
527
528def child2(sxpr, val=None):
529    """Get the second child.
530    """
531    return child_at(sxpr, 2, val)
532
533def child3(sxpr, val=None):
534    """Get the third child.
535    """
536    return child_at(sxpr, 3, val)
537
538def child4(sxpr, val=None):
539    """Get the fourth child.
540    """
541    return child_at(sxpr, 4, val)
542
543def 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.
546
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
555
556def has_id(sxpr, id):
557    """Test if an s-expression has a given id.
558    """
559    return attribute(sxpr, 'id') == id
560
561def with_id(sxpr, id, val=None):
562    """Find the first s-expression with a given id, at any depth.
563
564    sxpr   s-exp or list
565    id     id
566    val    value if not found (default None)
567
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
580
581def child_with_id(sxpr, id, val=None):
582    """Find the first child with a given id.
583
584    sxpr   s-exp or list
585    id     id
586    val    value if not found (default None)
587
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
596
597def 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.
604
605    sxpr   s-exp
606
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
618
619def 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.
623
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
646
647def 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.
653
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
669
670def 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.
674
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)
689
690def to_string(sxpr):
691    """Convert an sxpr to a string.
692
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
702
703def from_string(s):
704    """Create an sxpr by parsing a string.
705
706    s string
707    returns sxpr
708    """
709    if s == '':
710        return []
711
712    io = StringIO(s)
713    vals = parse(io)
714    if vals is []:
715        return None
716    else:
717        return vals[0]
718   
719
720def all_from_string(s):
721    """Create an sxpr list by parsing a string.
722
723    s string
724    returns sxpr list
725    """
726    io = StringIO(s)
727    vals = parse(io)
728    return vals
729
730def parse(io):
731    """Completely parse all input from 'io'.
732
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
748   
749
750if __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
763
Note: See TracBrowser for help on using the repository browser.