utils/ABITest/TypeGen.py

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