Clang Project

clang_source_code/utils/ABITest/TypeGen.py
1"""Flexible enumeration of C types."""
2from __future__ import division, print_function
3
4from Enumeration import *
5
6# TODO:
7
8#  - struct improvements (flexible arrays, packed &
9#    unpacked, alignment)
10#  - objective-c qualified id
11#  - anonymous / transparent unions
12#  - VLAs
13#  - block types
14#  - K&R functions
15#  - pass arguments of different types (test extension, transparent union)
16#  - varargs
17
18###
19# Actual type types
20
21class Type(object):
22    def isBitField(self):
23        return False
24
25    def isPaddingBitField(self):
26        return False
27
28    def getTypeName(self, printer):
29        name = 'T%d' % len(printer.types)
30        typedef = self.getTypedefDef(name, printer)
31        printer.addDeclaration(typedef)
32        return name
33
34class BuiltinType(Type):
35    def __init__(self, name, size, bitFieldSize=None):
36        self.name = name
37        self.size = size
38        self.bitFieldSize = bitFieldSize
39
40    def isBitField(self):
41        return self.bitFieldSize is not None
42
43    def isPaddingBitField(self):
44        return self.bitFieldSize is 0
45
46    def getBitFieldSize(self):
47        assert self.isBitField()
48        return self.bitFieldSize
49
50    def getTypeName(self, printer):
51        return self.name
52
53    def sizeof(self):
54        return self.size
55
56    def __str__(self):
57        return self.name
58
59class EnumType(Type):
60    unique_id = 0
61
62    def __init__(self, index, enumerators):
63        self.index = index
64        self.enumerators = enumerators
65        self.unique_id = self.__class__.unique_id
66        self.__class__.unique_id += 1
67
68    def getEnumerators(self):
69        result = ''
70        for i, init in enumerate(self.enumerators):
71            if i > 0:
72                result = result + ', '
73            result = result + 'enum%dval%d_%d' % (self.index, i, self.unique_id)
74            if init:
75                result = result + ' = %s' % (init)
76
77        return result
78
79    def __str__(self):
80        return 'enum { %s }' % (self.getEnumerators())
81
82    def getTypedefDef(self, name, printer):
83        return 'typedef enum %s { %s } %s;'%(name, self.getEnumerators(), name)
84
85class RecordType(Type):
86    def __init__(self, index, isUnion, fields):
87        self.index = index
88        self.isUnion = isUnion
89        self.fields = fields
90        self.name = None
91
92    def __str__(self):
93        def getField(t):
94            if t.isBitField():
95                return "%s : %d;" % (t, t.getBitFieldSize())
96            else:
97                return "%s;" % t
98
99        return '%s { %s }'%(('struct','union')[self.isUnion],
100                            ' '.join(map(getField, self.fields)))
101
102    def getTypedefDef(self, name, printer):
103        def getField(it):
104            i, t = it
105            if t.isBitField():
106                if t.isPaddingBitField():
107                    return '%s : 0;'%(printer.getTypeName(t),)
108                else:
109                    return '%s field%d : %d;'%(printer.getTypeName(t),i,
110                                               t.getBitFieldSize())
111            else:
112                return '%s field%d;'%(printer.getTypeName(t),i)
113        fields = [getField(f) for f in enumerate(self.fields)]
114        # Name the struct for more readable LLVM IR.
115        return 'typedef %s %s { %s } %s;'%(('struct','union')[self.isUnion],
116                                           name, ' '.join(fields), name)
117                                           
118class ArrayType(Type):
119    def __init__(self, index, isVector, elementType, size):
120        if isVector:
121            # Note that for vectors, this is the size in bytes.
122            assert size > 0
123        else:
124            assert size is None or size >= 0
125        self.index = index
126        self.isVector = isVector
127        self.elementType = elementType
128        self.size = size
129        if isVector:
130            eltSize = self.elementType.sizeof()
131            assert not (self.size % eltSize)
132            self.numElements = self.size // eltSize
133        else:
134            self.numElements = self.size
135
136    def __str__(self):
137        if self.isVector:
138            return 'vector (%s)[%d]'%(self.elementType,self.size)
139        elif self.size is not None:
140            return '(%s)[%d]'%(self.elementType,self.size)
141        else:
142            return '(%s)[]'%(self.elementType,)
143
144    def getTypedefDef(self, name, printer):
145        elementName = printer.getTypeName(self.elementType)
146        if self.isVector:
147            return 'typedef %s %s __attribute__ ((vector_size (%d)));'%(elementName,
148                                                                        name,
149                                                                        self.size)
150        else:
151            if self.size is None:
152                sizeStr = ''
153            else:
154                sizeStr = str(self.size)
155            return 'typedef %s %s[%s];'%(elementName, name, sizeStr)
156
157class ComplexType(Type):
158    def __init__(self, index, elementType):
159        self.index = index
160        self.elementType = elementType
161
162    def __str__(self):
163        return '_Complex (%s)'%(self.elementType)
164
165    def getTypedefDef(self, name, printer):
166        return 'typedef _Complex %s %s;'%(printer.getTypeName(self.elementType), name)
167
168class FunctionType(Type):
169    def __init__(self, index, returnType, argTypes):
170        self.index = index
171        self.returnType = returnType
172        self.argTypes = argTypes
173
174    def __str__(self):
175        if self.returnType is None:
176            rt = 'void'
177        else:
178            rt = str(self.returnType)
179        if not self.argTypes:
180            at = 'void'
181        else:
182            at = ', '.join(map(str, self.argTypes))
183        return '%s (*)(%s)'%(rt, at)
184
185    def getTypedefDef(self, name, printer):
186        if self.returnType is None:
187            rt = 'void'
188        else:
189            rt = str(self.returnType)
190        if not self.argTypes:
191            at = 'void'
192        else:
193            at = ', '.join(map(str, self.argTypes))
194        return 'typedef %s (*%s)(%s);'%(rt, name, at)
195
196###
197# Type enumerators
198
199class TypeGenerator(object):
200    def __init__(self):
201        self.cache = {}
202
203    def setCardinality(self):
204        abstract
205
206    def get(self, N):
207        T = self.cache.get(N)
208        if T is None:
209            assert 0 <= N < self.cardinality
210            T = self.cache[N] = self.generateType(N)
211        return T
212
213    def generateType(self, N):
214        abstract
215
216class FixedTypeGenerator(TypeGenerator):
217    def __init__(self, types):
218        TypeGenerator.__init__(self)
219        self.types = types
220        self.setCardinality()
221
222    def setCardinality(self):
223        self.cardinality = len(self.types)
224
225    def generateType(self, N):
226        return self.types[N]
227
228# Factorial
229def fact(n):
230    result = 1
231    while n > 0:
232        result = result * n
233        n = n - 1
234    return result
235
236# Compute the number of combinations (n choose k)
237def num_combinations(n, k): 
238    return fact(n) // (fact(k) * fact(n - k))
239
240# Enumerate the combinations choosing k elements from the list of values
241def combinations(values, k):
242    # From ActiveState Recipe 190465: Generator for permutations,
243    # combinations, selections of a sequence
244    if k==0: yield []
245    else:
246        for i in range(len(values)-k+1):
247            for cc in combinations(values[i+1:],k-1):
248                yield [values[i]]+cc
249
250class EnumTypeGenerator(TypeGenerator):
251    def __init__(self, values, minEnumerators, maxEnumerators):
252        TypeGenerator.__init__(self)
253        self.values = values
254        self.minEnumerators = minEnumerators
255        self.maxEnumerators = maxEnumerators
256        self.setCardinality()
257
258    def setCardinality(self):
259        self.cardinality = 0
260        for num in range(self.minEnumerators, self.maxEnumerators + 1):
261            self.cardinality += num_combinations(len(self.values), num)
262
263    def generateType(self, n):
264        # Figure out the number of enumerators in this type
265        numEnumerators = self.minEnumerators
266        valuesCovered = 0
267        while numEnumerators < self.maxEnumerators:
268            comb = num_combinations(len(self.values), numEnumerators)
269            if valuesCovered + comb > n:
270                break
271            numEnumerators = numEnumerators + 1
272            valuesCovered += comb
273
274        # Find the requested combination of enumerators and build a
275        # type from it.
276        i = 0
277        for enumerators in combinations(self.values, numEnumerators):
278            if i == n - valuesCovered:
279                return EnumType(n, enumerators)
280                
281            i = i + 1
282
283        assert False
284
285class ComplexTypeGenerator(TypeGenerator):
286    def __init__(self, typeGen):
287        TypeGenerator.__init__(self)
288        self.typeGen = typeGen
289        self.setCardinality()
290    
291    def setCardinality(self):
292        self.cardinality = self.typeGen.cardinality
293
294    def generateType(self, N):
295        return ComplexType(N, self.typeGen.get(N))
296
297class VectorTypeGenerator(TypeGenerator):
298    def __init__(self, typeGen, sizes):
299        TypeGenerator.__init__(self)
300        self.typeGen = typeGen
301        self.sizes = tuple(map(int,sizes))
302        self.setCardinality()
303
304    def setCardinality(self):
305        self.cardinality = len(self.sizes)*self.typeGen.cardinality
306
307    def generateType(self, N):
308        S,T = getNthPairBounded(N, len(self.sizes), self.typeGen.cardinality)
309        return ArrayType(N, True, self.typeGen.get(T), self.sizes[S])
310
311class FixedArrayTypeGenerator(TypeGenerator):
312    def __init__(self, typeGen, sizes):
313        TypeGenerator.__init__(self)
314        self.typeGen = typeGen
315        self.sizes = tuple(size)
316        self.setCardinality()
317
318    def setCardinality(self):
319        self.cardinality = len(self.sizes)*self.typeGen.cardinality
320
321    def generateType(self, N):
322        S,T = getNthPairBounded(N, len(self.sizes), self.typeGen.cardinality)
323        return ArrayType(N, false, self.typeGen.get(T), self.sizes[S])
324
325class ArrayTypeGenerator(TypeGenerator):
326    def __init__(self, typeGen, maxSize, useIncomplete=False, useZero=False):
327        TypeGenerator.__init__(self)
328        self.typeGen = typeGen
329        self.useIncomplete = useIncomplete
330        self.useZero = useZero
331        self.maxSize = int(maxSize)
332        self.W = useIncomplete + useZero + self.maxSize
333        self.setCardinality()
334
335    def setCardinality(self):
336        self.cardinality = self.W * self.typeGen.cardinality
337
338    def generateType(self, N):
339        S,T = getNthPairBounded(N, self.W, self.typeGen.cardinality)
340        if self.useIncomplete:
341            if S==0:
342                size = None
343                S = None
344            else:
345                S = S - 1
346        if S is not None:
347            if self.useZero:
348                size = S
349            else:
350                size = S + 1        
351        return ArrayType(N, False, self.typeGen.get(T), size)
352
353class RecordTypeGenerator(TypeGenerator):
354    def __init__(self, typeGen, useUnion, maxSize):
355        TypeGenerator.__init__(self)
356        self.typeGen = typeGen
357        self.useUnion = bool(useUnion)
358        self.maxSize = int(maxSize)
359        self.setCardinality()
360
361    def setCardinality(self):
362        M = 1 + self.useUnion
363        if self.maxSize is aleph0:
364            S =  aleph0 * self.typeGen.cardinality
365        else:
366            S = 0
367            for i in range(self.maxSize+1):
368                S += M * (self.typeGen.cardinality ** i)
369        self.cardinality = S
370
371    def generateType(self, N):
372        isUnion,I = False,N
373        if self.useUnion:
374            isUnion,I = (I&1),I>>1
375        fields = [self.typeGen.get(f) for f in getNthTuple(I,self.maxSize,self.typeGen.cardinality)]
376        return RecordType(N, isUnion, fields)
377
378class FunctionTypeGenerator(TypeGenerator):
379    def __init__(self, typeGen, useReturn, maxSize):
380        TypeGenerator.__init__(self)
381        self.typeGen = typeGen
382        self.useReturn = useReturn
383        self.maxSize = maxSize
384        self.setCardinality()
385    
386    def setCardinality(self):
387        if self.maxSize is aleph0:
388            S = aleph0 * self.typeGen.cardinality()
389        elif self.useReturn:
390            S = 0
391            for i in range(1,self.maxSize+1+1):
392                S += self.typeGen.cardinality ** i
393        else:
394            S = 0
395            for i in range(self.maxSize+1):
396                S += self.typeGen.cardinality ** i
397        self.cardinality = S
398    
399    def generateType(self, N):
400        if self.useReturn:
401            # Skip the empty tuple
402            argIndices = getNthTuple(N+1, self.maxSize+1, self.typeGen.cardinality)
403            retIndex,argIndices = argIndices[0],argIndices[1:]
404            retTy = self.typeGen.get(retIndex)
405        else:
406            retTy = None
407            argIndices = getNthTuple(N, self.maxSize, self.typeGen.cardinality)
408        args = [self.typeGen.get(i) for i in argIndices]
409        return FunctionType(N, retTy, args)
410
411class AnyTypeGenerator(TypeGenerator):
412    def __init__(self):
413        TypeGenerator.__init__(self)
414        self.generators = []
415        self.bounds = []
416        self.setCardinality()
417        self._cardinality = None
418        
419    def getCardinality(self):
420        if self._cardinality is None:
421            return aleph0
422        else:
423            return self._cardinality
424    def setCardinality(self):
425        self.bounds = [g.cardinality for g in self.generators]
426        self._cardinality = sum(self.bounds)
427    cardinality = property(getCardinality, None)
428
429    def addGenerator(self, g):
430        self.generators.append(g)
431        for i in range(100):
432            prev = self._cardinality
433            self._cardinality = None
434            for g in self.generators:
435                g.setCardinality()
436            self.setCardinality()
437            if (self._cardinality is aleph0) or prev==self._cardinality:
438                break
439        else:
440            raise RuntimeError("Infinite loop in setting cardinality")
441
442    def generateType(self, N):
443        index,M = getNthPairVariableBounds(N, self.bounds)
444        return self.generators[index].get(M)
445
446def test():
447    fbtg = FixedTypeGenerator([BuiltinType('char', 4),
448                               BuiltinType('char', 4, 0),
449                               BuiltinType('int',  4, 5)])
450
451    fields1 = AnyTypeGenerator()
452    fields1.addGenerator( fbtg )
453
454    fields0 = AnyTypeGenerator()
455    fields0.addGenerator( fbtg )
456#    fields0.addGenerator( RecordTypeGenerator(fields1, False, 4) )
457
458    btg = FixedTypeGenerator([BuiltinType('char', 4),
459                              BuiltinType('int',  4)])
460    etg = EnumTypeGenerator([None, '-1', '1', '1u'], 0, 3)
461
462    atg = AnyTypeGenerator()
463    atg.addGenerator( btg )
464    atg.addGenerator( RecordTypeGenerator(fields0, False, 4) )
465    atg.addGenerator( etg )
466    print('Cardinality:',atg.cardinality)
467    for i in range(100):
468        if i == atg.cardinality:
469            try:
470                atg.get(i)
471                raise RuntimeError("Cardinality was wrong")
472            except AssertionError:
473                break
474        print('%4d: %s'%(i, atg.get(i)))
475
476if __name__ == '__main__':
477    test()
478
CodeThinker, Enjoy your reading code