Debian Codegraph @

llvm-project/clang/utils/ABITest/TypeGen.py

raw
1 """Flexible enumeration of C types."""
2 from __future__ import division, print_function
3
4 from 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
21 class 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
34 class 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
59 class 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
85 class 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
118 class 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
157 class 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
168 class 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
199 class 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
216 class 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
229 def 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)
237 def 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
241 def 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
250 class 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
285 class 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
297 class 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
311 class 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
325 class 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
353 class 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
378 class 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
411 class 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
446 def 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
476 if __name__ == '__main__':
477 test()