"""Flexible enumeration of C types."""
from __future__ import division, print_function
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(object):
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(it):
i, t = it
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 = [getField(f) for f in 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 range(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 = [
self.typeGen.get(f)
for f in 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 = [self.typeGen.get(i) for i in 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()
Codebase Browser
llvm