| """Flexible enumeration of C types.""" |
| |
| from Enumeration import * |
| |
| # TODO: |
| |
| # - struct improvements (flexible arrays, packed & |
| # unpacked, alignment) |
| # - objective-c qualified id |
| # - anonymous / transparent unions |
| # - VLAs |
| # - block types |
| # - K&R functions |
| # - pass arguments of different types (test extension, transparent union) |
| # - varargs |
| |
| ### |
| # Actual type types |
| |
| class Type: |
| def isBitField(self): |
| return False |
| |
| def isPaddingBitField(self): |
| return False |
| |
| def getTypeName(self, printer): |
| name = 'T%d' % len(printer.types) |
| typedef = self.getTypedefDef(name, printer) |
| printer.addDeclaration(typedef) |
| return name |
| |
| class BuiltinType(Type): |
| def __init__(self, name, size, bitFieldSize=None): |
| self.name = name |
| self.size = size |
| self.bitFieldSize = bitFieldSize |
| |
| def isBitField(self): |
| return self.bitFieldSize is not None |
| |
| def isPaddingBitField(self): |
| return self.bitFieldSize is 0 |
| |
| def getBitFieldSize(self): |
| assert self.isBitField() |
| return self.bitFieldSize |
| |
| def getTypeName(self, printer): |
| return self.name |
| |
| def sizeof(self): |
| return self.size |
| |
| def __str__(self): |
| return self.name |
| |
| class EnumType(Type): |
| unique_id = 0 |
| |
| def __init__(self, index, enumerators): |
| self.index = index |
| self.enumerators = enumerators |
| self.unique_id = self.__class__.unique_id |
| self.__class__.unique_id += 1 |
| |
| def getEnumerators(self): |
| result = '' |
| for i, init in enumerate(self.enumerators): |
| if i > 0: |
| result = result + ', ' |
| result = result + 'enum%dval%d_%d' % (self.index, i, self.unique_id) |
| if init: |
| result = result + ' = %s' % (init) |
| |
| return result |
| |
| def __str__(self): |
| return 'enum { %s }' % (self.getEnumerators()) |
| |
| def getTypedefDef(self, name, printer): |
| return 'typedef enum %s { %s } %s;'%(name, self.getEnumerators(), name) |
| |
| class RecordType(Type): |
| def __init__(self, index, isUnion, fields): |
| self.index = index |
| self.isUnion = isUnion |
| self.fields = fields |
| self.name = None |
| |
| def __str__(self): |
| def getField(t): |
| if t.isBitField(): |
| return "%s : %d;" % (t, t.getBitFieldSize()) |
| else: |
| return "%s;" % t |
| |
| return '%s { %s }'%(('struct','union')[self.isUnion], |
| ' '.join(map(getField, self.fields))) |
| |
| def getTypedefDef(self, name, printer): |
| def getField((i, t)): |
| if t.isBitField(): |
| if t.isPaddingBitField(): |
| return '%s : 0;'%(printer.getTypeName(t),) |
| else: |
| return '%s field%d : %d;'%(printer.getTypeName(t),i, |
| t.getBitFieldSize()) |
| else: |
| return '%s field%d;'%(printer.getTypeName(t),i) |
| fields = map(getField, enumerate(self.fields)) |
| # Name the struct for more readable LLVM IR. |
| return 'typedef %s %s { %s } %s;'%(('struct','union')[self.isUnion], |
| name, ' '.join(fields), name) |
| |
| class ArrayType(Type): |
| def __init__(self, index, isVector, elementType, size): |
| if isVector: |
| # Note that for vectors, this is the size in bytes. |
| assert size > 0 |
| else: |
| assert size is None or size >= 0 |
| self.index = index |
| self.isVector = isVector |
| self.elementType = elementType |
| self.size = size |
| if isVector: |
| eltSize = self.elementType.sizeof() |
| assert not (self.size % eltSize) |
| self.numElements = self.size // eltSize |
| else: |
| self.numElements = self.size |
| |
| def __str__(self): |
| if self.isVector: |
| return 'vector (%s)[%d]'%(self.elementType,self.size) |
| elif self.size is not None: |
| return '(%s)[%d]'%(self.elementType,self.size) |
| else: |
| return '(%s)[]'%(self.elementType,) |
| |
| def getTypedefDef(self, name, printer): |
| elementName = printer.getTypeName(self.elementType) |
| if self.isVector: |
| return 'typedef %s %s __attribute__ ((vector_size (%d)));'%(elementName, |
| name, |
| self.size) |
| else: |
| if self.size is None: |
| sizeStr = '' |
| else: |
| sizeStr = str(self.size) |
| return 'typedef %s %s[%s];'%(elementName, name, sizeStr) |
| |
| class ComplexType(Type): |
| def __init__(self, index, elementType): |
| self.index = index |
| self.elementType = elementType |
| |
| def __str__(self): |
| return '_Complex (%s)'%(self.elementType) |
| |
| def getTypedefDef(self, name, printer): |
| return 'typedef _Complex %s %s;'%(printer.getTypeName(self.elementType), name) |
| |
| class FunctionType(Type): |
| def __init__(self, index, returnType, argTypes): |
| self.index = index |
| self.returnType = returnType |
| self.argTypes = argTypes |
| |
| def __str__(self): |
| if self.returnType is None: |
| rt = 'void' |
| else: |
| rt = str(self.returnType) |
| if not self.argTypes: |
| at = 'void' |
| else: |
| at = ', '.join(map(str, self.argTypes)) |
| return '%s (*)(%s)'%(rt, at) |
| |
| def getTypedefDef(self, name, printer): |
| if self.returnType is None: |
| rt = 'void' |
| else: |
| rt = str(self.returnType) |
| if not self.argTypes: |
| at = 'void' |
| else: |
| at = ', '.join(map(str, self.argTypes)) |
| return 'typedef %s (*%s)(%s);'%(rt, name, at) |
| |
| ### |
| # Type enumerators |
| |
| class TypeGenerator(object): |
| def __init__(self): |
| self.cache = {} |
| |
| def setCardinality(self): |
| abstract |
| |
| def get(self, N): |
| T = self.cache.get(N) |
| if T is None: |
| assert 0 <= N < self.cardinality |
| T = self.cache[N] = self.generateType(N) |
| return T |
| |
| def generateType(self, N): |
| abstract |
| |
| class FixedTypeGenerator(TypeGenerator): |
| def __init__(self, types): |
| TypeGenerator.__init__(self) |
| self.types = types |
| self.setCardinality() |
| |
| def setCardinality(self): |
| self.cardinality = len(self.types) |
| |
| def generateType(self, N): |
| return self.types[N] |
| |
| # Factorial |
| def fact(n): |
| result = 1 |
| while n > 0: |
| result = result * n |
| n = n - 1 |
| return result |
| |
| # Compute the number of combinations (n choose k) |
| def num_combinations(n, k): |
| return fact(n) / (fact(k) * fact(n - k)) |
| |
| # Enumerate the combinations choosing k elements from the list of values |
| def combinations(values, k): |
| # From ActiveState Recipe 190465: Generator for permutations, |
| # combinations, selections of a sequence |
| if k==0: yield [] |
| else: |
| for i in xrange(len(values)-k+1): |
| for cc in combinations(values[i+1:],k-1): |
| yield [values[i]]+cc |
| |
| class EnumTypeGenerator(TypeGenerator): |
| def __init__(self, values, minEnumerators, maxEnumerators): |
| TypeGenerator.__init__(self) |
| self.values = values |
| self.minEnumerators = minEnumerators |
| self.maxEnumerators = maxEnumerators |
| self.setCardinality() |
| |
| def setCardinality(self): |
| self.cardinality = 0 |
| for num in range(self.minEnumerators, self.maxEnumerators + 1): |
| self.cardinality += num_combinations(len(self.values), num) |
| |
| def generateType(self, n): |
| # Figure out the number of enumerators in this type |
| numEnumerators = self.minEnumerators |
| valuesCovered = 0 |
| while numEnumerators < self.maxEnumerators: |
| comb = num_combinations(len(self.values), numEnumerators) |
| if valuesCovered + comb > n: |
| break |
| numEnumerators = numEnumerators + 1 |
| valuesCovered += comb |
| |
| # Find the requested combination of enumerators and build a |
| # type from it. |
| i = 0 |
| for enumerators in combinations(self.values, numEnumerators): |
| if i == n - valuesCovered: |
| return EnumType(n, enumerators) |
| |
| i = i + 1 |
| |
| assert False |
| |
| class ComplexTypeGenerator(TypeGenerator): |
| def __init__(self, typeGen): |
| TypeGenerator.__init__(self) |
| self.typeGen = typeGen |
| self.setCardinality() |
| |
| def setCardinality(self): |
| self.cardinality = self.typeGen.cardinality |
| |
| def generateType(self, N): |
| return ComplexType(N, self.typeGen.get(N)) |
| |
| class VectorTypeGenerator(TypeGenerator): |
| def __init__(self, typeGen, sizes): |
| TypeGenerator.__init__(self) |
| self.typeGen = typeGen |
| self.sizes = tuple(map(int,sizes)) |
| self.setCardinality() |
| |
| def setCardinality(self): |
| self.cardinality = len(self.sizes)*self.typeGen.cardinality |
| |
| def generateType(self, N): |
| S,T = getNthPairBounded(N, len(self.sizes), self.typeGen.cardinality) |
| return ArrayType(N, True, self.typeGen.get(T), self.sizes[S]) |
| |
| class FixedArrayTypeGenerator(TypeGenerator): |
| def __init__(self, typeGen, sizes): |
| TypeGenerator.__init__(self) |
| self.typeGen = typeGen |
| self.sizes = tuple(size) |
| self.setCardinality() |
| |
| def setCardinality(self): |
| self.cardinality = len(self.sizes)*self.typeGen.cardinality |
| |
| def generateType(self, N): |
| S,T = getNthPairBounded(N, len(self.sizes), self.typeGen.cardinality) |
| return ArrayType(N, false, self.typeGen.get(T), self.sizes[S]) |
| |
| class ArrayTypeGenerator(TypeGenerator): |
| def __init__(self, typeGen, maxSize, useIncomplete=False, useZero=False): |
| TypeGenerator.__init__(self) |
| self.typeGen = typeGen |
| self.useIncomplete = useIncomplete |
| self.useZero = useZero |
| self.maxSize = int(maxSize) |
| self.W = useIncomplete + useZero + self.maxSize |
| self.setCardinality() |
| |
| def setCardinality(self): |
| self.cardinality = self.W * self.typeGen.cardinality |
| |
| def generateType(self, N): |
| S,T = getNthPairBounded(N, self.W, self.typeGen.cardinality) |
| if self.useIncomplete: |
| if S==0: |
| size = None |
| S = None |
| else: |
| S = S - 1 |
| if S is not None: |
| if self.useZero: |
| size = S |
| else: |
| size = S + 1 |
| return ArrayType(N, False, self.typeGen.get(T), size) |
| |
| class RecordTypeGenerator(TypeGenerator): |
| def __init__(self, typeGen, useUnion, maxSize): |
| TypeGenerator.__init__(self) |
| self.typeGen = typeGen |
| self.useUnion = bool(useUnion) |
| self.maxSize = int(maxSize) |
| self.setCardinality() |
| |
| def setCardinality(self): |
| M = 1 + self.useUnion |
| if self.maxSize is aleph0: |
| S = aleph0 * self.typeGen.cardinality |
| else: |
| S = 0 |
| for i in range(self.maxSize+1): |
| S += M * (self.typeGen.cardinality ** i) |
| self.cardinality = S |
| |
| def generateType(self, N): |
| isUnion,I = False,N |
| if self.useUnion: |
| isUnion,I = (I&1),I>>1 |
| fields = map(self.typeGen.get,getNthTuple(I,self.maxSize,self.typeGen.cardinality)) |
| return RecordType(N, isUnion, fields) |
| |
| class FunctionTypeGenerator(TypeGenerator): |
| def __init__(self, typeGen, useReturn, maxSize): |
| TypeGenerator.__init__(self) |
| self.typeGen = typeGen |
| self.useReturn = useReturn |
| self.maxSize = maxSize |
| self.setCardinality() |
| |
| def setCardinality(self): |
| if self.maxSize is aleph0: |
| S = aleph0 * self.typeGen.cardinality() |
| elif self.useReturn: |
| S = 0 |
| for i in range(1,self.maxSize+1+1): |
| S += self.typeGen.cardinality ** i |
| else: |
| S = 0 |
| for i in range(self.maxSize+1): |
| S += self.typeGen.cardinality ** i |
| self.cardinality = S |
| |
| def generateType(self, N): |
| if self.useReturn: |
| # Skip the empty tuple |
| argIndices = getNthTuple(N+1, self.maxSize+1, self.typeGen.cardinality) |
| retIndex,argIndices = argIndices[0],argIndices[1:] |
| retTy = self.typeGen.get(retIndex) |
| else: |
| retTy = None |
| argIndices = getNthTuple(N, self.maxSize, self.typeGen.cardinality) |
| args = map(self.typeGen.get, argIndices) |
| return FunctionType(N, retTy, args) |
| |
| class AnyTypeGenerator(TypeGenerator): |
| def __init__(self): |
| TypeGenerator.__init__(self) |
| self.generators = [] |
| self.bounds = [] |
| self.setCardinality() |
| self._cardinality = None |
| |
| def getCardinality(self): |
| if self._cardinality is None: |
| return aleph0 |
| else: |
| return self._cardinality |
| def setCardinality(self): |
| self.bounds = [g.cardinality for g in self.generators] |
| self._cardinality = sum(self.bounds) |
| cardinality = property(getCardinality, None) |
| |
| def addGenerator(self, g): |
| self.generators.append(g) |
| for i in range(100): |
| prev = self._cardinality |
| self._cardinality = None |
| for g in self.generators: |
| g.setCardinality() |
| self.setCardinality() |
| if (self._cardinality is aleph0) or prev==self._cardinality: |
| break |
| else: |
| raise RuntimeError,"Infinite loop in setting cardinality" |
| |
| def generateType(self, N): |
| index,M = getNthPairVariableBounds(N, self.bounds) |
| return self.generators[index].get(M) |
| |
| def test(): |
| fbtg = FixedTypeGenerator([BuiltinType('char', 4), |
| BuiltinType('char', 4, 0), |
| BuiltinType('int', 4, 5)]) |
| |
| fields1 = AnyTypeGenerator() |
| fields1.addGenerator( fbtg ) |
| |
| fields0 = AnyTypeGenerator() |
| fields0.addGenerator( fbtg ) |
| # fields0.addGenerator( RecordTypeGenerator(fields1, False, 4) ) |
| |
| btg = FixedTypeGenerator([BuiltinType('char', 4), |
| BuiltinType('int', 4)]) |
| etg = EnumTypeGenerator([None, '-1', '1', '1u'], 0, 3) |
| |
| atg = AnyTypeGenerator() |
| atg.addGenerator( btg ) |
| atg.addGenerator( RecordTypeGenerator(fields0, False, 4) ) |
| atg.addGenerator( etg ) |
| print 'Cardinality:',atg.cardinality |
| for i in range(100): |
| if i == atg.cardinality: |
| try: |
| atg.get(i) |
| raise RuntimeError,"Cardinality was wrong" |
| except AssertionError: |
| break |
| print '%4d: %s'%(i, atg.get(i)) |
| |
| if __name__ == '__main__': |
| test() |
