diff options
author | Daniel Dunbar <daniel@zuster.org> | 2009-01-15 04:24:17 +0000 |
---|---|---|
committer | Daniel Dunbar <daniel@zuster.org> | 2009-01-15 04:24:17 +0000 |
commit | a83fb8647bfca3aa9bd7049f817979f092244e83 (patch) | |
tree | 58b787c6864824712df6a044f818e882be63330c /utils/ABITest | |
parent | 4bb64e77dd3b22070e28b7f9ff99feb576eaf6ef (diff) | |
download | clang-a83fb8647bfca3aa9bd7049f817979f092244e83.tar.gz |
Add utils/ABITest, my ABI test generation tool.
- Mostly written as an entertaining exercise in enumerating large or
(countably, naturally) infinite sets. But hey, its useful too!
- Idea is to number all C-types so that the N-th type can quickly be
computed, with a good deal of flexibility about what types to
include, and taking some care so that the (N+1)-th type is
interestingly different from the N-th type. For example, using the
default generator, the 1,000,000-th function type is:
--
typedef _Complex int T0;
typedef char T1 __attribute__ ((vector_size (4)));
typedef int T2 __attribute__ ((vector_size (4)));
T2 fn1000000(T0 arg0, signed long long arg1, T1 arg2, T0 arg3);
--
and the 1,000,001-th type is:
--
typedef _Complex char T0;
typedef _Complex char T2;
typedef struct T1 { T2 field0; T2 field1; T2 field2; } T1;
typedef struct T3 { } T3;
unsigned short fn1000001(T0 arg0, T1 arg1, T3 arg2);
--
Computing the 10^1600-th type takes a little less than 1s. :)
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@62253 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'utils/ABITest')
-rwxr-xr-x | utils/ABITest/ABITestGen.py | 476 | ||||
-rw-r--r-- | utils/ABITest/Enumeration.py | 276 | ||||
-rw-r--r-- | utils/ABITest/TypeGen.py | 316 |
3 files changed, 1068 insertions, 0 deletions
diff --git a/utils/ABITest/ABITestGen.py b/utils/ABITest/ABITestGen.py new file mode 100755 index 0000000000..c50abe1ea9 --- /dev/null +++ b/utils/ABITest/ABITestGen.py @@ -0,0 +1,476 @@ +#!/usr/bin/python + +from pprint import pprint +import random, atexit, time +from random import randrange + +from Enumeration import * +from TypeGen import * + +#### + +class TypePrinter: + def __init__(self, output, outputHeader=None, + outputTests=None, outputDriver=None, + headerName=None, info=None): + self.output = output + self.outputHeader = outputHeader + self.outputTests = outputTests + self.outputDriver = outputDriver + self.writeBody = outputHeader or outputTests or outputDriver + self.types = {} + self.testValues = {} + self.testReturnValues = {} + + if info: + for f in (self.output,self.outputHeader,self.outputTests,self.outputDriver): + if f: + print >>f,info + + if self.writeBody: + print >>self.output, '#include <stdio.h>\n' + if self.outputTests: + print >>self.outputTests, '#include <stdio.h>\n' + + if headerName: + for f in (self.output,self.outputTests,self.outputDriver): + if f is not None: + print >>f, '#include "%s"\n'%(headerName,) + + if self.outputDriver: + print >>self.outputDriver, 'int main(int argc, char **argv) {' + + def finish(self): + if self.outputDriver: + print >>self.outputDriver, ' return 0;' + print >>self.outputDriver, '}' + + def getTypeName(self, T): + if isinstance(T,BuiltinType): + return T.name + name = self.types.get(T) + if name is None: + name = 'T%d'%(len(self.types),) + # Reserve slot + self.types[T] = None + if self.outputHeader: + print >>self.outputHeader,T.getTypedefDef(name, self) + else: + print >>self.output,T.getTypedefDef(name, self) + if self.outputTests: + print >>self.outputTests,T.getTypedefDef(name, self) + self.types[T] = name + return name + + def writeFunction(self, i, FT): + args = ', '.join(['%s arg%d'%(self.getTypeName(t),i) for i,t in enumerate(FT.argTypes)]) + if not args: + args = 'void' + + if FT.returnType is None: + retvalName = None + retvalTypeName = 'void' + else: + retvalTypeName = self.getTypeName(FT.returnType) + if self.writeBody or self.outputTests: + retvalName = self.getTestReturnValue(FT.returnType) + + fnName = 'fn%d'%(FT.index,) + if self.outputHeader: + print >>self.outputHeader,'%s %s(%s);'%(retvalTypeName, fnName, args) + elif self.outputTests: + print >>self.outputTests,'%s %s(%s);'%(retvalTypeName, fnName, args) + + print >>self.output,'%s %s(%s)'%(retvalTypeName, fnName, args), + if self.writeBody: + print >>self.output, '{' + + for i,t in enumerate(FT.argTypes): + self.printValueOfType(' %s'%fnName, 'arg%d'%i, t) + + if retvalName is not None: + print >>self.output, ' return %s;'%(retvalName,) + print >>self.output, '}' + else: + print >>self.output, '{}' + print >>self.output + + if self.outputDriver: + print >>self.outputDriver, ' { extern void test_%s(void); test_%s(); }\n'%(fnName,fnName,) + + if self.outputTests: + if self.outputHeader: + print >>self.outputHeader, 'void test_%s(void);'%(fnName,) + + if retvalName is None: + retvalTests = None + else: + retvalTests = self.getTestValuesArray(FT.returnType) + tests = map(self.getTestValuesArray, FT.argTypes) + print >>self.outputTests, 'void test_%s(void) {'%(fnName,) + + if retvalTests is not None: + print >>self.outputTests, ' printf("%s: testing return.\\n");'%(fnName,) + print >>self.outputTests, ' for (int i=0; i<%d; ++i) {'%(retvalTests[1],) + args = ', '.join(['%s[%d]'%(t,randrange(l)) for t,l in tests]) + print >>self.outputTests, ' %s RV;'%(retvalTypeName,) + print >>self.outputTests, ' %s = %s[i];'%(retvalName, retvalTests[0]) + print >>self.outputTests, ' RV = %s(%s);'%(fnName, args) + self.printValueOfType(' %s_RV'%fnName, 'RV', FT.returnType, output=self.outputTests, indent=4) + print >>self.outputTests, ' }' + + if tests: + print >>self.outputTests, ' printf("%s: testing arguments.\\n");'%(fnName,) + for i,(array,length) in enumerate(tests): + for j in range(length): + args = ['%s[%d]'%(t,randrange(l)) for t,l in tests] + args[i] = '%s[%d]'%(array,j) + print >>self.outputTests, ' %s(%s);'%(fnName, ', '.join(args),) + print >>self.outputTests, '}' + + def getTestReturnValue(self, type): + typeName = self.getTypeName(type) + info = self.testReturnValues.get(typeName) + if info is None: + name = '%s_retval'%(typeName.replace(' ','_').replace('*','star'),) + print >>self.output, '%s %s;'%(typeName,name) + if self.outputHeader: + print >>self.outputHeader, 'extern %s %s;'%(typeName,name) + elif self.outputTests: + print >>self.outputTests, 'extern %s %s;'%(typeName,name) + info = self.testReturnValues[typeName] = name + return info + + def getTestValuesArray(self, type): + typeName = self.getTypeName(type) + info = self.testValues.get(typeName) + if info is None: + name = '%s_values'%(typeName.replace(' ','_').replace('*','star'),) + print >>self.outputTests, 'static %s %s[] = {'%(typeName,name) + length = 0 + for item in self.getTestValues(type): + print >>self.outputTests, '\t%s,'%(item,) + length += 1 + print >>self.outputTests,'};' + info = self.testValues[typeName] = (name,length) + return info + + def getTestValues(self, t): + if isinstance(t, BuiltinType): + if t.name=='float': + for i in ['0.0','-1.0','1.0']: + yield i+'f' + elif t.name=='double': + for i in ['0.0','-1.0','1.0']: + yield i + elif t.name in ('void *'): + yield '(void*) 0' + yield '(void*) -1' + else: + yield '(%s) 0'%(t.name,) + yield '(%s) -1'%(t.name,) + yield '(%s) 1'%(t.name,) + elif isinstance(t, RecordType): + fieldValues = [list(self.getTestValues(f)) for f in t.fields] + if not t.fields: + yield '{ }' + for i,values in enumerate(fieldValues): + for v in values: + elements = map(random.choice,fieldValues) + elements[i] = v + yield '{ %s }'%(', '.join(elements)) + elif isinstance(t, ComplexType): + for t in self.getTestValues(t.elementType): + yield '%s + %si'%(t,t) + elif isinstance(t, ArrayType) and not t.isVector: + values = list(self.getTestValues(t.elementType)) + if not values: + yield '{ }' + for i in range(t.size): + for v in values: + elements = [random.choice(values) for i in range(t.size)] + elements[i] = v + yield '{ %s }'%(', '.join(elements)) + else: + raise NotImplementedError,'Cannot make tests values of type: "%s"'%(t,) + + def printValueOfType(self, prefix, name, t, output=None, indent=2): + if output is None: + output = self.output + if isinstance(t, BuiltinType): + if t.name.endswith('long long'): + code = 'lld' + elif t.name.endswith('long'): + code = 'ld' + elif t.name.split(' ')[-1] in ('_Bool','char','short','int'): + code = 'd' + elif t.name in ('float','double'): + code = 'f' + elif t.name == 'long double': + code = 'Lf' + else: + code = 'p' + print >>output, '%*sprintf("%s: %s = %%%s\\n", %s);'%(indent, '', prefix, name, code, name) + elif isinstance(t, RecordType): + if not t.fields: + print >>output, '%*sprintf("%s: %s (empty)\\n");'%(indent, '', prefix, name) + for i,f in enumerate(t.fields): + fname = '%s.field%d'%(name,i) + self.printValueOfType(prefix, fname, f, output=output, indent=indent) + elif isinstance(t, ComplexType): + self.printValueOfType(prefix, '(__real %s)'%name, t.elementType, output=output,indent=indent) + self.printValueOfType(prefix, '(__imag %s)'%name, t.elementType, output=output,indent=indent) + elif isinstance(t, ArrayType) and not t.isVector: + for i in range(t.size): + self.printValueOfType(prefix, '(%s)[%d]'%(name,i), t.elementType, output=output,indent=indent) + else: + raise NotImplementedError,'Cannot print value of type: "%s"'%(t,) + +import sys + +def main(): + from optparse import OptionParser, OptionGroup + parser = OptionParser("%prog [options] {indices}") + parser.add_option("", "--mode", dest="mode", + help="autogeneration mode (random or linear) [default %default]", + type='choice', choices=('random','linear'), default='linear') + parser.add_option("", "--count", dest="count", + help="autogenerate COUNT functions according to MODE", + type=int, default=0) + parser.add_option("", "--min", dest="minIndex", metavar="N", + help="start autogeneration with the Nth function type [default %default]", + type=int, default=0) + parser.add_option("", "--max", dest="maxIndex", metavar="N", + help="maximum index for random autogeneration [default %default]", + type=int, default=10000000) + parser.add_option("", "--seed", dest="seed", + help="random number generator seed [default %default]", + type=int, default=1) + parser.add_option("", "--use-random-seed", dest="useRandomSeed", + help="use random value for initial random number generator seed", + action='store_true', default=False) + parser.add_option("-o", "--output", dest="output", metavar="FILE", + help="write output to FILE [default %default]", + type=str, default='-') + parser.add_option("-O", "--output-header", dest="outputHeader", metavar="FILE", + help="write header file for output to FILE [default %default]", + type=str, default=None) + parser.add_option("-T", "--output-tests", dest="outputTests", metavar="FILE", + help="write function tests to FILE [default %default]", + type=str, default=None) + parser.add_option("-D", "--output-driver", dest="outputDriver", metavar="FILE", + help="write test driver to FILE [default %default]", + type=str, default=None) + + group = OptionGroup(parser, "Type Enumeration Options") + # Builtins - Ints + group.add_option("", "--no-char", dest="useChar", + help="do not generate char types", + action="store_false", default=True) + group.add_option("", "--no-short", dest="useShort", + help="do not generate short types", + action="store_false", default=True) + group.add_option("", "--no-int", dest="useInt", + help="do not generate int types", + action="store_false", default=True) + group.add_option("", "--no-long", dest="useLong", + help="do not generate long types", + action="store_false", default=True) + group.add_option("", "--no-long-long", dest="useLongLong", + help="do not generate long long types", + action="store_false", default=True) + group.add_option("", "--no-unsigned", dest="useUnsigned", + help="do not generate unsigned integer types", + action="store_false", default=True) + + # Other builtins + group.add_option("", "--no-bool", dest="useBool", + help="do not generate bool types", + action="store_false", default=True) + group.add_option("", "--no-float", dest="useFloat", + help="do not generate float types", + action="store_false", default=True) + group.add_option("", "--no-double", dest="useDouble", + help="do not generate double types", + action="store_false", default=True) + group.add_option("", "--no-long-double", dest="useLongDouble", + help="do not generate long double types", + action="store_false", default=True) + group.add_option("", "--no-void-pointer", dest="useVoidPointer", + help="do not generate void* types", + action="store_false", default=True) + + # Derived types + group.add_option("", "--no-array", dest="useArray", + help="do not generate record types", + action="store_false", default=True) + group.add_option("", "--no-complex", dest="useComplex", + help="do not generate complex types", + action="store_false", default=True) + group.add_option("", "--no-record", dest="useRecord", + help="do not generate record types", + action="store_false", default=True) + group.add_option("", "--no-union", dest="recordUseUnion", + help="do not generate union types", + action="store_false", default=True) + group.add_option("", "--no-vector", dest="useVector", + help="do not generate vector types", + action="store_false", default=True) + + # Tuning + group.add_option("", "--no-function-return", dest="functionUseReturn", + help="do not generate return types for functions", + action="store_false", default=True) + group.add_option("", "--vector-sizes", dest="vectorSizes", + help="comma separated list of sizes for vectors [default %default]", + action="store", type=str, default='4,8', metavar="N") + + group.add_option("", "--max-args", dest="functionMaxArgs", + help="maximum number of arguments per function [default %default]", + action="store", type=int, default=4, metavar="N") + group.add_option("", "--max-array", dest="arrayMaxSize", + help="maximum array size [default %default]", + action="store", type=int, default=4, metavar="N") + group.add_option("", "--max-record", dest="recordMaxSize", + help="maximum number of fields per record [default %default]", + action="store", type=int, default=4, metavar="N") + group.add_option("", "--max-record-depth", dest="recordMaxDepth", + help="maximum nested structure depth [default %default]", + action="store", type=int, default=None, metavar="N") + parser.add_option_group(group) + (opts, args) = parser.parse_args() + + if not opts.useRandomSeed: + random.seed(opts.seed) + + # Contruct type generator + builtins = [] + ints = [] + if opts.useChar: ints.append('char') + if opts.useShort: ints.append('short') + if opts.useInt: ints.append('int') + if opts.useLong: ints.append('long') + if opts.useLongLong: ints.append('long long') + if opts.useUnsigned: + ints = (['unsigned %s'%i for i in ints] + + ['signed %s'%i for i in ints]) + builtins.extend(ints) + + if opts.useBool: builtins.append('_Bool') + if opts.useFloat: builtins.append('float') + if opts.useDouble: builtins.append('double') + if opts.useLongDouble: builtins.append('long double') + if opts.useVoidPointer: builtins.append('void*') + + btg = FixedTypeGenerator(map(BuiltinType,builtins)) + sbtg = FixedTypeGenerator(map(BuiltinType,['char','int','float'])) + + atg = AnyTypeGenerator() + artg = AnyTypeGenerator() + def makeGenerator(atg, subgen, useRecord, useArray): + atg.addGenerator(btg) + if useRecord and opts.useRecord: + assert subgen + atg.addGenerator(RecordTypeGenerator(subgen, opts.recordUseUnion, + opts.recordMaxSize)) + if opts.useComplex: + # FIXME: Allow overriding builtins here + atg.addGenerator(ComplexTypeGenerator(sbtg)) + if useArray and opts.useArray: + assert subgen + atg.addGenerator(ArrayTypeGenerator(subgen, opts.arrayMaxSize)) + if opts.useVector: + atg.addGenerator(VectorTypeGenerator(sbtg, + map(int, opts.vectorSizes.split(',')))) + + + if opts.recordMaxDepth is None: + # Fully recursive, just avoid top-level arrays. + subTG = AnyTypeGenerator() + atg = AnyTypeGenerator() + makeGenerator(subTG, atg, True, True) + makeGenerator(atg, subTG, True, False) + else: + # Make a chain of type generators, each builds smaller + # structures. + base = AnyTypeGenerator() + makeGenerator(base, None, False, False) + for i in range(opts.recordMaxDepth): + n = AnyTypeGenerator() + makeGenerator(n, base, True, True) + base = n + atg = AnyTypeGenerator() + makeGenerator(atg, base, True, False) + + ftg = FunctionTypeGenerator(atg, opts.functionUseReturn, opts.functionMaxArgs) + + # Override max,min,count if finite + if opts.maxIndex is None: + if ftg.cardinality is aleph0: + opts.maxIndex = 10000000 + else: + opts.maxIndex = ftg.cardinality + opts.maxIndex = min(opts.maxIndex, ftg.cardinality) + opts.minIndex = max(0,min(opts.maxIndex-1, opts.minIndex)) + if not opts.mode=='random': + opts.count = min(opts.count, opts.maxIndex-opts.minIndex) + + if opts.output=='-': + output = sys.stdout + else: + output = open(opts.output,'w') + atexit.register(lambda: output.close()) + + outputHeader = None + if opts.outputHeader: + outputHeader = open(opts.outputHeader,'w') + atexit.register(lambda: outputHeader.close()) + + outputTests = None + if opts.outputTests: + outputTests = open(opts.outputTests,'w') + atexit.register(lambda: outputTests.close()) + + outputDriver = None + if opts.outputDriver: + outputDriver = open(opts.outputDriver,'w') + atexit.register(lambda: outputDriver.close()) + + info = '' + info += '// %s\n'%(' '.join(sys.argv),) + info += '// Generated: %s\n'%(time.strftime('%Y-%m-%d %H:%M'),) + info += '// Cardinality of function generator: %s\n'%(ftg.cardinality,) + info += '// Cardinality of type generator: %s\n'%(atg.cardinality,) + + P = TypePrinter(output, + outputHeader=outputHeader, + outputTests=outputTests, + outputDriver=outputDriver, + headerName=opts.outputHeader, + info=info) + + def write(N): + try: + FT = ftg.get(N) + except RuntimeError,e: + if e.args[0]=='maximum recursion depth exceeded': + print >>sys.stderr,'WARNING: Skipped %d, recursion limit exceeded (bad arguments?)'%(N,) + return + raise + P.writeFunction(N, FT) + + if args: + [write(int(a)) for a in args] + + for i in range(opts.count): + if opts.mode=='linear': + index = opts.minIndex + i + else: + index = opts.minIndex + int((opts.maxIndex-opts.minIndex) * random.random()) + write(index) + + P.finish() + +if __name__=='__main__': + main() + diff --git a/utils/ABITest/Enumeration.py b/utils/ABITest/Enumeration.py new file mode 100644 index 0000000000..47e47026db --- /dev/null +++ b/utils/ABITest/Enumeration.py @@ -0,0 +1,276 @@ +"""Utilities for enumeration of finite and countably infinite sets. +""" +### +# Countable iteration + +# Simplifies some calculations +class Aleph0(int): + _singleton = None + def __new__(type): + if type._singleton is None: + type._singleton = int.__new__(type) + return type._singleton + def __repr__(self): return '<aleph0>' + def __str__(self): return 'inf' + + def __cmp__(self, b): + return 1 + + def __sub__(self, b): + raise ValueError,"Cannot subtract aleph0" + __rsub__ = __sub__ + + def __add__(self, b): + return self + __radd__ = __add__ + + def __mul__(self, b): + if b == 0: return b + return self + __rmul__ = __mul__ + + def __floordiv__(self, b): + if b == 0: raise ZeroDivisionError + return self + __rfloordiv__ = __floordiv__ + __truediv__ = __floordiv__ + __rtuediv__ = __floordiv__ + __div__ = __floordiv__ + __rdiv__ = __floordiv__ + + def __pow__(self, b): + if b == 0: return 1 + return self +aleph0 = Aleph0() + +def base(line): + return line*(line+1)//2 + +def pairToN((x,y)): + line,index = x+y,y + return base(line)+index + +def getNthPairInfo(N): + # Avoid various singularities + if N==0: + return (0,0) + + # Gallop to find bounds for line + line = 1 + next = 2 + while base(next)<=N: + line = next + next = line << 1 + + # Binary search for starting line + lo = line + hi = line<<1 + while lo + 1 != hi: + #assert base(lo) <= N < base(hi) + mid = (lo + hi)>>1 + if base(mid)<=N: + lo = mid + else: + hi = mid + + line = lo + return line, N - base(line) + +def getNthPair(N): + line,index = getNthPairInfo(N) + return (line - index, index) + +def getNthPairBounded(N,W=aleph0,H=aleph0,useDivmod=False): + """getNthPairBounded(N, W, H) -> (x, y) + + Return the N-th pair such that 0 <= x < W and 0 <= y < H.""" + + if W <= 0 or H <= 0: + raise ValueError,"Invalid bounds" + elif N >= W*H: + raise ValueError,"Invalid input (out of bounds)" + + # Simple case... + if W is aleph0 and H is aleph0: + return getNthPair(N) + + # Otherwise simplify by assuming W < H + if H < W: + x,y = getNthPairBounded(N,H,W,useDivmod=useDivmod) + return y,x + + if useDivmod: + return N%W,N//W + else: + # Conceptually we want to slide a diagonal line across a + # rectangle. This gives more interesting results for large + # bounds than using divmod. + + # If in lower left, just return as usual + cornerSize = base(W) + if N < cornerSize: + return getNthPair(N) + + # Otherwise if in upper right, subtract from corner + if H is not aleph0: + M = W*H - N - 1 + if M < cornerSize: + x,y = getNthPair(M) + return (W-1-x,H-1-y) + + # Otherwise, compile line and index from number of times we + # wrap. + N = N - cornerSize + index,offset = N%W,N//W + # p = (W-1, 1+offset) + (-1,1)*index + return (W-1-index, 1+offset+index) +def getNthPairBoundedChecked(N,W=aleph0,H=aleph0,useDivmod=False,GNP=getNthPairBounded): + x,y = GNP(N,W,H,useDivmod) + assert 0 <= x < W and 0 <= y < H + return x,y + +def getNthNTuple(N, W, H=aleph0, useLeftToRight=False): + """getNthNTuple(N, W, H) -> (x_0, x_1, ..., x_W) + + Return the N-th W-tuple, where for 0 <= x_i < H.""" + + if useLeftToRight: + elts = [None]*W + for i in range(W): + elts[i],N = getNthPairBounded(N, H) + return tuple(elts) + else: + if W==0: + return () + elif W==1: + return (N,) + elif W==2: + return getNthPairBounded(N, H, H) + else: + LW,RW = W//2, W - (W//2) + L,R = getNthPairBounded(N, H**LW, H**RW) + return (getNthNTuple(L,LW,H=H,useLeftToRight=useLeftToRight) + + getNthNTuple(R,RW,H=H,useLeftToRight=useLeftToRight)) +def getNthNTupleChecked(N, W, H=aleph0, useLeftToRight=False, GNT=getNthNTuple): + t = GNT(N,W,H,useLeftToRight) + assert len(t) == W + for i in t: + assert i < H + return t + +def getNthTuple(N, maxSize=aleph0, maxElement=aleph0, useDivmod=False, useLeftToRight=False): + """getNthTuple(N, maxSize, maxElement) -> x + + Return the N-th tuple where len(x) < maxSize and for y in x, 0 <= + y < maxElement.""" + + # All zero sized tuples are isomorphic, don't ya know. + if N == 0: + return () + N -= 1 + if maxElement is not aleph0: + if maxSize is aleph0: + raise NotImplementedError,'Max element size without max size unhandled' + bounds = [maxElement**i for i in range(1, maxSize+1)] + S,M = getNthPairVariableBounds(N, bounds) + else: + S,M = getNthPairBounded(N, maxSize, useDivmod=useDivmod) + return getNthNTuple(M, S+1, maxElement, useLeftToRight=useLeftToRight) +def getNthTupleChecked(N, maxSize=aleph0, maxElement=aleph0, + useDivmod=False, useLeftToRight=False, GNT=getNthTuple): + # FIXME: maxsize is inclusive + t = GNT(N,maxSize,maxElement,useDivmod,useLeftToRight) + assert len(t) <= maxSize + for i in t: + assert i < maxElement + return t + +def getNthPairVariableBounds(N, bounds): + """getNthPairVariableBounds(N, bounds) -> (x, y) + + Given a finite list of bounds (which may be finite or aleph0), + return the N-th pair such that 0 <= x < len(bounds) and 0 <= y < + bounds[x].""" + + if not bounds: + raise ValueError,"Invalid bounds" + if not (0 <= N < sum(bounds)): + raise ValueError,"Invalid input (out of bounds)" + + level = 0 + active = range(len(bounds)) + active.sort(key=lambda i: bounds[i]) + prevLevel = 0 + for i,index in enumerate(active): + level = bounds[index] + W = len(active) - i + if level is aleph0: + H = aleph0 + else: + H = level - prevLevel + levelSize = W*H + if N<levelSize: # Found the level + idelta,delta = getNthPairBounded(N, W, H) + return active[i+idelta],prevLevel+delta + else: + N -= levelSize + prevLevel = level + else: + raise RuntimError,"Unexpected loop completion" + +def getNthPairVariableBoundsChecked(N, bounds, GNVP=getNthPairVariableBounds): + x,y = GNVP(N,bounds) + assert 0 <= x < len(bounds) and 0 <= y < bounds[x] + return (x,y) + +### + +def testPairs(): + W = 3 + H = 6 + a = [[' ' for x in range(10)] for y in range(10)] + b = [[' ' for x in range(10)] for y in range(10)] + for i in range(min(W*H,40)): + x,y = getNthPairBounded(i,W,H) + x2,y2 = getNthPairBounded(i,W,H,useDivmod=True) + print i,(x,y),(x2,y2) + a[y][x] = '%2d'%i + b[y2][x2] = '%2d'%i + + print '-- a --' + for ln in a[::-1]: + if ''.join(ln).strip(): + print ' '.join(ln) + print '-- b --' + for ln in b[::-1]: + if ''.join(ln).strip(): + print ' '.join(ln) + +def testPairsVB(): + bounds = [2,2,4,aleph0,5,aleph0] + a = [[' ' for x in range(15)] for y in range(15)] + b = [[' ' for x in range(15)] for y in range(15)] + for i in range(min(sum(bounds),40)): + x,y = getNthPairVariableBounds(i, bounds) + print i,(x,y) + a[y][x] = '%2d'%i + + print '-- a --' + for ln in a[::-1]: + if ''.join(ln).strip(): + print ' '.join(ln) + +### + +# Toggle to use checked versions of enumeration routines. +if False: + getNthPairVariableBounds = getNthPairVariableBoundsChecked + getNthPairBounded = getNthPairBoundedChecked + getNthNTuple = getNthNTupleChecked + getNthTuple = getNthTupleChecked + +if __name__ == '__main__': + testPairs() + + testPairsVB() + diff --git a/utils/ABITest/TypeGen.py b/utils/ABITest/TypeGen.py new file mode 100644 index 0000000000..ce34a25e64 --- /dev/null +++ b/utils/ABITest/TypeGen.py @@ -0,0 +1,316 @@ +"""Flexible enumeration of C types.""" + +from Enumeration import * + +# TODO: + +# - struct improvements (bitfields, flexible arrays, packed & +# unpacked, alignment) + +### +# Actual type types + +class BuiltinType: + def __init__(self, name): + self.name = name + + def __str__(self): + return self.name + +class RecordType: + def __init__(self, index, isUnion, fields): + self.index = index + self.isUnion = isUnion + self.fields = fields + self.name = None + + def __str__(self): + return '%s { %s }'%(('struct','union')[self.isUnion], + ' '.join(['%s;'%f for f in self.fields])) + + def getTypedefDef(self, name, printer): + fields = ['%s field%d;'%(printer.getTypeName(t),i) for i,t 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: + 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 + + 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: + 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: + 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] + +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(): + atg = AnyTypeGenerator() + btg = FixedTypeGenerator(map(BuiltinType,['int','float'])) + atg.addGenerator( btg ) + atg.addGenerator( ComplexTypeGenerator(btg) ) + atg.addGenerator( RecordTypeGenerator(atg, True, 2) ) + atg.addGenerator( VectorTypeGenerator(btg, (4,8)) ) + atg.addGenerator( ArrayTypeGenerator(btg, 4) ) + atg.addGenerator( FunctionTypeGenerator(btg, False, 2) ) + print 'Cardinality:',atg.cardinality + for i in range(100): + print '%4d: %s'%(i, atg.get(i)) + +if __name__ == '__main__': + test() |