518 lines · python
1"""Flexible enumeration of C types."""2from __future__ import division, print_function3 4from Enumeration import *5 6# TODO:7 8# - struct improvements (flexible arrays, packed &9# unpacked, alignment)10# - objective-c qualified id11# - anonymous / transparent unions12# - VLAs13# - block types14# - K&R functions15# - pass arguments of different types (test extension, transparent union)16# - varargs17 18###19# Actual type types20 21 22class Type(object):23 def isBitField(self):24 return False25 26 def isPaddingBitField(self):27 return False28 29 def getTypeName(self, printer):30 name = "T%d" % len(printer.types)31 typedef = self.getTypedefDef(name, printer)32 printer.addDeclaration(typedef)33 return name34 35 36class BuiltinType(Type):37 def __init__(self, name, size, bitFieldSize=None):38 self.name = name39 self.size = size40 self.bitFieldSize = bitFieldSize41 42 def isBitField(self):43 return self.bitFieldSize is not None44 45 def isPaddingBitField(self):46 return self.bitFieldSize is 047 48 def getBitFieldSize(self):49 assert self.isBitField()50 return self.bitFieldSize51 52 def getTypeName(self, printer):53 return self.name54 55 def sizeof(self):56 return self.size57 58 def __str__(self):59 return self.name60 61 62class EnumType(Type):63 unique_id = 064 65 def __init__(self, index, enumerators):66 self.index = index67 self.enumerators = enumerators68 self.unique_id = self.__class__.unique_id69 self.__class__.unique_id += 170 71 def getEnumerators(self):72 result = ""73 for i, init in enumerate(self.enumerators):74 if i > 0:75 result = result + ", "76 result = result + "enum%dval%d_%d" % (self.index, i, self.unique_id)77 if init:78 result = result + " = %s" % (init)79 80 return result81 82 def __str__(self):83 return "enum { %s }" % (self.getEnumerators())84 85 def getTypedefDef(self, name, printer):86 return "typedef enum %s { %s } %s;" % (name, self.getEnumerators(), name)87 88 89class RecordType(Type):90 def __init__(self, index, isUnion, fields):91 self.index = index92 self.isUnion = isUnion93 self.fields = fields94 self.name = None95 96 def __str__(self):97 def getField(t):98 if t.isBitField():99 return "%s : %d;" % (t, t.getBitFieldSize())100 else:101 return "%s;" % t102 103 return "%s { %s }" % (104 ("struct", "union")[self.isUnion],105 " ".join(map(getField, self.fields)),106 )107 108 def getTypedefDef(self, name, printer):109 def getField(it):110 i, t = it111 if t.isBitField():112 if t.isPaddingBitField():113 return "%s : 0;" % (printer.getTypeName(t),)114 else:115 return "%s field%d : %d;" % (116 printer.getTypeName(t),117 i,118 t.getBitFieldSize(),119 )120 else:121 return "%s field%d;" % (printer.getTypeName(t), i)122 123 fields = [getField(f) for f in enumerate(self.fields)]124 # Name the struct for more readable LLVM IR.125 return "typedef %s %s { %s } %s;" % (126 ("struct", "union")[self.isUnion],127 name,128 " ".join(fields),129 name,130 )131 132 133class ArrayType(Type):134 def __init__(self, index, isVector, elementType, size):135 if isVector:136 # Note that for vectors, this is the size in bytes.137 assert size > 0138 else:139 assert size is None or size >= 0140 self.index = index141 self.isVector = isVector142 self.elementType = elementType143 self.size = size144 if isVector:145 eltSize = self.elementType.sizeof()146 assert not (self.size % eltSize)147 self.numElements = self.size // eltSize148 else:149 self.numElements = self.size150 151 def __str__(self):152 if self.isVector:153 return "vector (%s)[%d]" % (self.elementType, self.size)154 elif self.size is not None:155 return "(%s)[%d]" % (self.elementType, self.size)156 else:157 return "(%s)[]" % (self.elementType,)158 159 def getTypedefDef(self, name, printer):160 elementName = printer.getTypeName(self.elementType)161 if self.isVector:162 return "typedef %s %s __attribute__ ((vector_size (%d)));" % (163 elementName,164 name,165 self.size,166 )167 else:168 if self.size is None:169 sizeStr = ""170 else:171 sizeStr = str(self.size)172 return "typedef %s %s[%s];" % (elementName, name, sizeStr)173 174 175class ComplexType(Type):176 def __init__(self, index, elementType):177 self.index = index178 self.elementType = elementType179 180 def __str__(self):181 return "_Complex (%s)" % (self.elementType)182 183 def getTypedefDef(self, name, printer):184 return "typedef _Complex %s %s;" % (printer.getTypeName(self.elementType), name)185 186 187class FunctionType(Type):188 def __init__(self, index, returnType, argTypes):189 self.index = index190 self.returnType = returnType191 self.argTypes = argTypes192 193 def __str__(self):194 if self.returnType is None:195 rt = "void"196 else:197 rt = str(self.returnType)198 if not self.argTypes:199 at = "void"200 else:201 at = ", ".join(map(str, self.argTypes))202 return "%s (*)(%s)" % (rt, at)203 204 def getTypedefDef(self, name, printer):205 if self.returnType is None:206 rt = "void"207 else:208 rt = str(self.returnType)209 if not self.argTypes:210 at = "void"211 else:212 at = ", ".join(map(str, self.argTypes))213 return "typedef %s (*%s)(%s);" % (rt, name, at)214 215 216###217# Type enumerators218 219 220class TypeGenerator(object):221 def __init__(self):222 self.cache = {}223 224 def setCardinality(self):225 abstract226 227 def get(self, N):228 T = self.cache.get(N)229 if T is None:230 assert 0 <= N < self.cardinality231 T = self.cache[N] = self.generateType(N)232 return T233 234 def generateType(self, N):235 abstract236 237 238class FixedTypeGenerator(TypeGenerator):239 def __init__(self, types):240 TypeGenerator.__init__(self)241 self.types = types242 self.setCardinality()243 244 def setCardinality(self):245 self.cardinality = len(self.types)246 247 def generateType(self, N):248 return self.types[N]249 250 251# Factorial252def fact(n):253 result = 1254 while n > 0:255 result = result * n256 n = n - 1257 return result258 259 260# Compute the number of combinations (n choose k)261def num_combinations(n, k):262 return fact(n) // (fact(k) * fact(n - k))263 264 265# Enumerate the combinations choosing k elements from the list of values266def combinations(values, k):267 # From ActiveState Recipe 190465: Generator for permutations,268 # combinations, selections of a sequence269 if k == 0:270 yield []271 else:272 for i in range(len(values) - k + 1):273 for cc in combinations(values[i + 1 :], k - 1):274 yield [values[i]] + cc275 276 277class EnumTypeGenerator(TypeGenerator):278 def __init__(self, values, minEnumerators, maxEnumerators):279 TypeGenerator.__init__(self)280 self.values = values281 self.minEnumerators = minEnumerators282 self.maxEnumerators = maxEnumerators283 self.setCardinality()284 285 def setCardinality(self):286 self.cardinality = 0287 for num in range(self.minEnumerators, self.maxEnumerators + 1):288 self.cardinality += num_combinations(len(self.values), num)289 290 def generateType(self, n):291 # Figure out the number of enumerators in this type292 numEnumerators = self.minEnumerators293 valuesCovered = 0294 while numEnumerators < self.maxEnumerators:295 comb = num_combinations(len(self.values), numEnumerators)296 if valuesCovered + comb > n:297 break298 numEnumerators = numEnumerators + 1299 valuesCovered += comb300 301 # Find the requested combination of enumerators and build a302 # type from it.303 i = 0304 for enumerators in combinations(self.values, numEnumerators):305 if i == n - valuesCovered:306 return EnumType(n, enumerators)307 308 i = i + 1309 310 assert False311 312 313class ComplexTypeGenerator(TypeGenerator):314 def __init__(self, typeGen):315 TypeGenerator.__init__(self)316 self.typeGen = typeGen317 self.setCardinality()318 319 def setCardinality(self):320 self.cardinality = self.typeGen.cardinality321 322 def generateType(self, N):323 return ComplexType(N, self.typeGen.get(N))324 325 326class VectorTypeGenerator(TypeGenerator):327 def __init__(self, typeGen, sizes):328 TypeGenerator.__init__(self)329 self.typeGen = typeGen330 self.sizes = tuple(map(int, sizes))331 self.setCardinality()332 333 def setCardinality(self):334 self.cardinality = len(self.sizes) * self.typeGen.cardinality335 336 def generateType(self, N):337 S, T = getNthPairBounded(N, len(self.sizes), self.typeGen.cardinality)338 return ArrayType(N, True, self.typeGen.get(T), self.sizes[S])339 340 341class FixedArrayTypeGenerator(TypeGenerator):342 def __init__(self, typeGen, sizes):343 TypeGenerator.__init__(self)344 self.typeGen = typeGen345 self.sizes = tuple(size)346 self.setCardinality()347 348 def setCardinality(self):349 self.cardinality = len(self.sizes) * self.typeGen.cardinality350 351 def generateType(self, N):352 S, T = getNthPairBounded(N, len(self.sizes), self.typeGen.cardinality)353 return ArrayType(N, false, self.typeGen.get(T), self.sizes[S])354 355 356class ArrayTypeGenerator(TypeGenerator):357 def __init__(self, typeGen, maxSize, useIncomplete=False, useZero=False):358 TypeGenerator.__init__(self)359 self.typeGen = typeGen360 self.useIncomplete = useIncomplete361 self.useZero = useZero362 self.maxSize = int(maxSize)363 self.W = useIncomplete + useZero + self.maxSize364 self.setCardinality()365 366 def setCardinality(self):367 self.cardinality = self.W * self.typeGen.cardinality368 369 def generateType(self, N):370 S, T = getNthPairBounded(N, self.W, self.typeGen.cardinality)371 if self.useIncomplete:372 if S == 0:373 size = None374 S = None375 else:376 S = S - 1377 if S is not None:378 if self.useZero:379 size = S380 else:381 size = S + 1382 return ArrayType(N, False, self.typeGen.get(T), size)383 384 385class RecordTypeGenerator(TypeGenerator):386 def __init__(self, typeGen, useUnion, maxSize):387 TypeGenerator.__init__(self)388 self.typeGen = typeGen389 self.useUnion = bool(useUnion)390 self.maxSize = int(maxSize)391 self.setCardinality()392 393 def setCardinality(self):394 M = 1 + self.useUnion395 if self.maxSize is aleph0:396 S = aleph0 * self.typeGen.cardinality397 else:398 S = 0399 for i in range(self.maxSize + 1):400 S += M * (self.typeGen.cardinality**i)401 self.cardinality = S402 403 def generateType(self, N):404 isUnion, I = False, N405 if self.useUnion:406 isUnion, I = (I & 1), I >> 1407 fields = [408 self.typeGen.get(f)409 for f in getNthTuple(I, self.maxSize, self.typeGen.cardinality)410 ]411 return RecordType(N, isUnion, fields)412 413 414class FunctionTypeGenerator(TypeGenerator):415 def __init__(self, typeGen, useReturn, maxSize):416 TypeGenerator.__init__(self)417 self.typeGen = typeGen418 self.useReturn = useReturn419 self.maxSize = maxSize420 self.setCardinality()421 422 def setCardinality(self):423 if self.maxSize is aleph0:424 S = aleph0 * self.typeGen.cardinality()425 elif self.useReturn:426 S = 0427 for i in range(1, self.maxSize + 1 + 1):428 S += self.typeGen.cardinality**i429 else:430 S = 0431 for i in range(self.maxSize + 1):432 S += self.typeGen.cardinality**i433 self.cardinality = S434 435 def generateType(self, N):436 if self.useReturn:437 # Skip the empty tuple438 argIndices = getNthTuple(N + 1, self.maxSize + 1, self.typeGen.cardinality)439 retIndex, argIndices = argIndices[0], argIndices[1:]440 retTy = self.typeGen.get(retIndex)441 else:442 retTy = None443 argIndices = getNthTuple(N, self.maxSize, self.typeGen.cardinality)444 args = [self.typeGen.get(i) for i in argIndices]445 return FunctionType(N, retTy, args)446 447 448class AnyTypeGenerator(TypeGenerator):449 def __init__(self):450 TypeGenerator.__init__(self)451 self.generators = []452 self.bounds = []453 self.setCardinality()454 self._cardinality = None455 456 def getCardinality(self):457 if self._cardinality is None:458 return aleph0459 else:460 return self._cardinality461 462 def setCardinality(self):463 self.bounds = [g.cardinality for g in self.generators]464 self._cardinality = sum(self.bounds)465 466 cardinality = property(getCardinality, None)467 468 def addGenerator(self, g):469 self.generators.append(g)470 for i in range(100):471 prev = self._cardinality472 self._cardinality = None473 for g in self.generators:474 g.setCardinality()475 self.setCardinality()476 if (self._cardinality is aleph0) or prev == self._cardinality:477 break478 else:479 raise RuntimeError("Infinite loop in setting cardinality")480 481 def generateType(self, N):482 index, M = getNthPairVariableBounds(N, self.bounds)483 return self.generators[index].get(M)484 485 486def test():487 fbtg = FixedTypeGenerator(488 [BuiltinType("char", 4), BuiltinType("char", 4, 0), BuiltinType("int", 4, 5)]489 )490 491 fields1 = AnyTypeGenerator()492 fields1.addGenerator(fbtg)493 494 fields0 = AnyTypeGenerator()495 fields0.addGenerator(fbtg)496 # fields0.addGenerator( RecordTypeGenerator(fields1, False, 4) )497 498 btg = FixedTypeGenerator([BuiltinType("char", 4), BuiltinType("int", 4)])499 etg = EnumTypeGenerator([None, "-1", "1", "1u"], 0, 3)500 501 atg = AnyTypeGenerator()502 atg.addGenerator(btg)503 atg.addGenerator(RecordTypeGenerator(fields0, False, 4))504 atg.addGenerator(etg)505 print("Cardinality:", atg.cardinality)506 for i in range(100):507 if i == atg.cardinality:508 try:509 atg.get(i)510 raise RuntimeError("Cardinality was wrong")511 except AssertionError:512 break513 print("%4d: %s" % (i, atg.get(i)))514 515 516if __name__ == "__main__":517 test()518