• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1#!/usr/bin/env python
2""" cdecl.py - parse c declarations
3
4(c) 2002, 2003, 2004, 2005 Simon Burton <simon@arrowtheory.com>
5Released under GNU LGPL license.
6
7version 0.xx
8
9"""
10
11import string
12
13
14class Node(list):
15    " A node in a parse tree "
16
17    def __init__(self,*items,**kw):
18        list.__init__( self, items )
19        self.lock1 = 0 # these two should be properties (simplifies serializing)
20        self.lock2 = 0
21        self.verbose = 0
22        for key in kw.keys():
23            self.__dict__[key] = kw[key]
24
25    def __str__(self):
26        attrs = []
27        for item in self:
28            if isinstance(item,Node):
29                attrs.append( str(item) )
30            else:
31                attrs.append( repr(item) )
32        attrs = ','.join(attrs)
33        return "%s(%s)"%(self.__class__.__name__,attrs)
34
35    def safe_repr( self, tank ):
36        tank[ str(self) ] = None
37        attrs = []
38        for item in self:
39            if isinstance(item,Node):
40                attrs.append( item.safe_repr(tank) ) # can we use repr here ?
41            else:
42                attrs.append( repr(item) )
43        # this is the dangerous bit:
44        for key, val in self.__dict__.items():
45            if isinstance(val,Node):
46                if str(val) not in tank:
47                    attrs.append( '%s=%s'%(key,val.safe_repr(tank)) )
48            else:
49                attrs.append( '%s=%s'%(key,repr(val)) )
50        attrs = ','.join(attrs)
51        return "%s(%s)"%(self.__class__.__name__,attrs)
52
53    def __repr__(self):
54        #attrs = ','.join( [repr(item) for item in self] + \
55        # [ '%s=%s'%(key,repr(val)) for key,val in self.__dict__.items() ] )
56        #return "%s%s"%(self.__class__.__name__,tuple(attrs))
57        return self.safe_repr({})
58
59    def __eq__(self,other):
60        if not isinstance(other,Node):
61            return 0
62        if len(self)!=len(other):
63            return 0
64        for i in range(len(self)):
65            if not self[i]==other[i]:
66                return 0
67        return 1
68
69    def __ne__(self,other):
70        return not self==other
71
72    def filter(self,cls):
73        return [x for x in self if isinstance(x,cls)]
74        #return filter( lambda x:isinstance(x,cls), self )
75
76    def deepfilter(self,cls):
77        " bottom-up "
78        return [x for x in self.nodes() if isinstance(x,cls)]
79
80    def find(self,cls):
81        for x in self:
82            if isinstance(x,cls):
83                return x
84        return None
85
86    def deepfind(self,cls):
87        " bottom-up isinstance search "
88        for x in self:
89            if isinstance(x,Node):
90                if isinstance(x,cls):
91                    return x
92                node = x.deepfind(cls)
93                if node is not None:
94                    return node
95        if isinstance(self,cls):
96            return self
97        return None
98
99    def leaves(self):
100        for i in self:
101            if isinstance( i, Node ):
102                for j in i.leaves():
103                    yield j
104            else:
105                yield i
106
107    def nodes(self):
108        " bottom-up iteration "
109        for i in self:
110            if isinstance( i, Node ):
111                for j in i.nodes():
112                    yield j
113        yield self
114
115    def deeplen(self):
116        i=0
117        if not self.lock2:
118            self.lock2=1
119            for item in self:
120                i+=1
121                if isinstance(item,Node):
122                    i+=item.deeplen()
123            self.lock2=0
124        else:
125            i+=1
126        return i
127
128    def deepstr(self,level=0,comment=False,nl='\n',indent='    '):
129        if self.deeplen() < 4:
130            nl = ""; indent = ""
131        #else:
132            #nl="\n"; indent = "    "
133        s = []
134        if not self.lock1:
135            self.lock1=1
136            for item in self:
137                if isinstance(item,Node):
138                    s.append( indent*(level+1)+item.deepstr(level+1,False,nl,indent) )
139                else:
140                    s.append( indent*(level+1)+repr(item) )
141            self.lock1=0
142        else:
143            for item in self:
144                if isinstance(item,Node):
145                    s.append( indent*(level+1)+"<recursion...>" )
146                else:
147                    s.append( indent*(level+1)+"%s"%repr(item) )
148        s = "%s(%s)"%(self.__class__.__name__,nl+string.join(s,","+nl))
149        if comment:
150            s = '#' + s.replace('\n','\n#')
151        return s
152
153    def clone(self):
154        items = []
155        for item in self:
156            if isinstance(item,Node):
157                item = item.clone()
158            items.append(item)
159        # we skip any attributes...
160        return self.__class__(*items)
161
162    def fastclone(self):
163        # XX is it faster ???
164        #print "clone"
165        nodes = [self]
166        idxs = [0]
167        itemss = [ [] ]
168        while nodes:
169            assert len(nodes)==len(idxs)==len(itemss)
170            node = nodes[-1]
171            items = itemss[-1]
172            assert idxs[-1] == len(items)
173            while idxs[-1]==len(node):
174                # pop
175                _node = node.__class__( *items )
176                _node.__dict__.update( node.__dict__ )
177                nodes.pop(-1)
178                idxs.pop(-1)
179                itemss.pop(-1)
180                if not nodes:
181                    #for node0 in self.nodes():
182                        #for node1 in _node.nodes():
183                            #assert node0 is not node1
184                    #assert _node == self
185                    return _node # Done !!
186                node = nodes[-1]
187                items = itemss[-1]
188                items.append(_node) # set
189                idxs[-1] += 1
190                assert idxs[-1] == len(items)
191                #assert idxs[-1] < len(node), str( (node,nodes,idxs,itemss) )
192
193            _node = node[ idxs[-1] ]
194            # while idxs[-1]<len(node):
195            if isinstance(_node,Node):
196                # push
197                nodes.append( _node )
198                idxs.append( 0 )
199                itemss.append( [] )
200            else:
201                # next
202                items.append(_node)
203                idxs[-1] += 1
204                assert idxs[-1] == len(items)
205
206    def expose(self,cls):
207        ' expose children of any <cls> instance '
208        # children first
209        for x in self:
210            if isinstance(x,Node):
211                x.expose(cls)
212        # now the tricky bit
213        i=0
214        while i < len(self):
215            if isinstance(self[i],cls):
216                node=self.pop(i)
217                for x in node:
218                    assert not isinstance(x,cls)
219                    # pass on some attributes
220                    if hasattr(node,'lines') and not hasattr(x,'lines'):
221                        x.lines=node.lines
222                    if hasattr(node,'file') and not hasattr(x,'file'):
223                        x.file=node.file
224                    self.insert(i,x) # expose
225                    i=i+1
226                    assert i<=len(self)
227            else:
228                i=i+1
229
230    def get_parent( self, item ): # XX 25% CPU time here XX
231        assert self != item
232        if item in self:
233            return self
234        for child in self:
235            if isinstance(child, Node):
236                parent = child.get_parent(item)
237                if parent is not None:
238                    return parent
239        return None
240
241    def expose_node( self, item ):
242        assert self != item
243        parent = self.get_parent(item)
244        idx = parent.index( item )
245        parent[idx:idx+1] = item[:]
246
247    def delete(self,cls):
248        ' delete any <cls> subtree '
249        for x in self:
250            if isinstance(x,Node):
251                x.delete(cls)
252        # now the tricky bit
253        i=0
254        while i < len(self):
255            if isinstance(self[i],cls):
256                self.pop(i)
257            else:
258                i=i+1
259
260    def deeprm(self,item):
261        ' remove any items matching <item> '
262        for x in self:
263            if isinstance(x,Node):
264                x.deeprm(item)
265        # now the tricky bit
266        i=0
267        while i < len(self):
268            if self[i] == item:
269                self.pop(i)
270            else:
271                i=i+1
272
273    def idem(self,cls):
274        " <cls> is made idempotent "
275        # children first
276        for x in self:
277            if isinstance(x,Node):
278                x.idem(cls)
279        if isinstance(self,cls):
280            # now the tricky bit
281            i=0
282            while i < len(self):
283                if isinstance(self[i],cls):
284                    node = self.pop(i)
285                    for x in node:
286                        assert not isinstance(x,cls)
287                        self.insert(i,x) # idempotent
288                        i=i+1
289                        assert i<=len(self)
290                else:
291                    i=i+1
292
293if __name__=="__main__":
294    node = Node( 'a', Node(1,2), Node(Node(Node(),1)) )
295
296    print node
297    print node.clone()
298
299
300
301
302