| |
| /** |
| * A test case spec is an array of objects of the following kind: |
| * { 'match': Num|Str|Null, |
| * 'body': Num|Str|Null, |
| * 'fallthrough': Boolean } |
| * |
| * If the 'match' is null, then it represents a 'default:' |
| * If the 'match' is not null, it represents a 'case X:' where X is the value. |
| * If the 'body' is null, then it means that the case body is empty. Otherwise, |
| * it means that the case body is a single 'arr.push(V);' where "arr" is an input |
| * array to the function containing the switch statement, and V is the value. |
| * If 'fallthrough' is false, then the body is terminated with a break, otherwise |
| * it is not. |
| * |
| * So a spec: [{'match':3, 'body':null, 'fallthrough':false}, {'match':null, 'body':"foo", 'fallthrough':true}] |
| * Represents a switch function: |
| * function(x, arr) { |
| * switch(x) { |
| * case 3: |
| * break; |
| * default: |
| * arr.push('foo'); |
| * } |
| * } |
| * |
| * GenerateSpecPermutes generates a bunch of relevant specs, using the given case match-values, |
| * and appends them to result the array passed into it. |
| * |
| * InterpretSwitch takes a spec, a value, and a result array, and behaves as if the switch specified |
| * by the spec had been called on the value and the result array. |
| * |
| * VerifySwitchSpec is there but not used in the code. I was using it while testing the test case |
| * generator. It verifies that a switch spec is sane. |
| * |
| * RunSpec uses eval to run the test directly. It's not used currently. |
| * |
| * GenerateSwitchCode generates a string of the form "function NAME(x, arg) { .... }" which |
| * contains the switch modeled by its input spec. |
| * |
| * RunTest is there to be used from within the generated script. Its code is dumped out |
| * to the generated script text, and invoked there. |
| * |
| * Hope all of this makes some sort of sense. |
| * -kannan |
| */ |
| |
| /** HELPERS **/ |
| |
| function ASSERT(cond, msg) { assertEq(cond, true, msg); } |
| |
| function IsUndef(x) { return typeof(x) == 'undefined'; } |
| function IsNull(x) { return typeof(x) == 'object' && x == null; } |
| function IsNum(x) { return typeof(x) == 'number'; } |
| function IsStr(x) { return typeof(x) == 'string'; } |
| function IsBool(x) { return typeof(x) == 'boolean'; } |
| |
| function Repr(x) { |
| ASSERT(IsNum(x) || IsStr(x), "Repr"); |
| if(IsNum(x)) { return ""+x; } |
| else { return "'"+x+"'"; } |
| } |
| |
| function RandBool() { return Math.random() >= 0.5; } |
| function RandInt(max) { |
| if(IsUndef(max)) { max = 0x7fffffff; } |
| return (Math.random() * max)|0; |
| } |
| |
| var CHARS = "abcdefghijklmnopqrstuvywxyzABCDEFGHIJKLMNOPQRSTUVYWXYZ0123456789~!@#$%^&*()-_=+{}[]"; |
| function RandStr() { |
| var arr = []; |
| var len = Math.floor(Math.random() * 10) + 1; |
| for(var i = 0; i < len; i++) { |
| var c = Math.floor(Math.random() * CHARS.length); |
| arr.push(CHARS[c]); |
| } |
| return arr.join(''); |
| } |
| |
| function RandVal() { return RandBool() ? RandInt() : RandStr(); } |
| |
| /** |
| * Compare two arrays and ensure they are equal. |
| */ |
| function ArraysEqual(arr1, arr2) { |
| ASSERT(arr1.length == arr2.length, "Lengths not equal"); |
| for(var i = 0; i < arr1.length; i++) { |
| ASSERT(typeof(arr1[i]) == typeof(arr2[i]), "Types not equal for position " + i); |
| ASSERT(arr1[i] == arr2[i], "Values not equal for position " + i); |
| } |
| } |
| |
| function VerifySwitchSpec(spec) { |
| var foundDefault = undefined; |
| for(var i = 0; i < spec.length; i++) { |
| var caseSpec = spec[i], |
| match = caseSpec.match, |
| body = caseSpec.body, |
| fallthrough = caseSpec.fallthrough; |
| ASSERT(IsNum(match) || IsStr(match) || IsNull(match), "Invalid case match for " + i); |
| ASSERT(IsNum(body) || IsStr(body) || IsNull(body), "Invalid case body for " + i); |
| ASSERT(IsBool(fallthrough), "Invalid fallthrough for " + i); |
| |
| if(IsNull(match)) { |
| ASSERT(IsUndef(foundDefault), "Duplicate default found at " + i); |
| foundDefault = i; |
| } |
| } |
| } |
| |
| /** |
| * Do a manual interpretation of a particular spec, given an input |
| * and outputting to an output array. |
| */ |
| function InterpretSwitch(spec, input, outputArray) { |
| var foundMatch = undefined, foundDefault = undefined; |
| // Go through cases, trying to find a matching clause. |
| for(var i = 0; i < spec.length; i++) { |
| var caseSpec = spec[i], match = caseSpec.match; |
| |
| if(IsNull(match)) { |
| foundDefault = i; |
| continue; |
| } else if(match === input) { |
| foundMatch = i; |
| break; |
| } |
| } |
| // Select either matching clause or default. |
| var matchI = IsNum(foundMatch) ? foundMatch : foundDefault; |
| |
| // If match or default was found, interpret body from that point on. |
| if(IsNum(matchI)) { |
| for(var i = matchI; i < spec.length; i++) { |
| var caseSpec = spec[i], |
| match = caseSpec.match, |
| body = caseSpec.body, |
| fallthrough = caseSpec.fallthrough; |
| if(!IsNull(body)) { outputArray.push(body); } |
| if(!fallthrough) { break; } |
| } |
| } |
| } |
| |
| /** |
| * Generate the code string for a javascript function containing the |
| * switch specified by the spec, in pure JS syntax. |
| */ |
| function GenerateSwitchCode(spec, name) { |
| var lines = []; |
| if(!name) { name = ""; } |
| |
| lines.push("function "+name+"(x, arr) {"); |
| lines.push(" switch(x) {"); |
| for(var i = 0; i < spec.length; i++) { |
| var caseSpec = spec[i], |
| match = caseSpec.match, |
| body = caseSpec.body, |
| fallthrough = caseSpec.fallthrough; |
| |
| if(IsNull(match)) { lines.push(" default:"); } |
| else { lines.push(" case "+Repr(match)+":"); } |
| |
| if(!IsNull(body)) { lines.push(" arr.push("+Repr(body)+");"); } |
| if(!fallthrough) { lines.push(" break;"); } |
| } |
| lines.push(" }"); |
| lines.push("}"); |
| return lines.join("\n"); |
| } |
| |
| /** |
| * Generates all possible specs for a given set of case match values. |
| */ |
| function GenerateSpecPermutes(matchVals, resultArray) { |
| ASSERT((0 < matchVals.length) && (matchVals.length <= 5), "Invalid matchVals"); |
| var maxPermuteBody = (1 << matchVals.length) - 1; |
| for(var bod_pm = 0; bod_pm <= maxPermuteBody; bod_pm++) { |
| var maxPermuteFallthrough = (1 << matchVals.length) - 1; |
| |
| for(var ft_pm = 0; ft_pm <= maxPermuteFallthrough; ft_pm++) { |
| // use bod_m and ft_pm to decide the placement of null vs value bodies, |
| // and the placement of fallthroughs vs breaks. |
| // Empty bodies always fall through, so fallthrough bitmask 1s must be |
| // a subset of the body bitmask 1s. |
| if((bod_pm | ft_pm) != bod_pm) { |
| continue; |
| } |
| |
| var spec = []; |
| for(var k = 0; k < matchVals.length; k++) { |
| var match = matchVals[k]; |
| var body = ((bod_pm & (1 << k)) > 0) ? null : RandVal(); |
| var fallthrough = ((ft_pm & (1 << k)) > 0) ? true : false; |
| var caseSpec = {'match':match, 'body':body, 'fallthrough':fallthrough}; |
| spec.push(caseSpec); |
| } |
| |
| // Variant specs for following cases: |
| |
| // Default with empty body, fallthrough |
| GenerateDefaultPermutes(spec, null, true, resultArray); |
| // Default with nonempty body, fallthrough |
| GenerateDefaultPermutes(spec, RandVal(), true, resultArray); |
| // Default with nonempty body, break |
| GenerateDefaultPermutes(spec, RandVal(), false, resultArray); |
| } |
| } |
| } |
| function GenerateDefaultPermutes(spec, body, fallthrough, resultArray) { |
| if(spec.length <= 2) { |
| for(var i = 0; i <= spec.length; i++) { |
| var copy = CopySpec(spec); |
| if(IsNull(body)) { |
| copy.splice(i,0,{'match':null, 'body':null, 'fallthrough':true}); |
| } else { |
| copy.splice(i,0,{'match':null, 'body':body, 'fallthrough':fallthrough}); |
| } |
| resultArray.push(copy); |
| } |
| } else { |
| var posns = [0, Math.floor(spec.length / 2), spec.length]; |
| posns.forEach(function (i) { |
| var copy = CopySpec(spec); |
| if(IsNull(body)) { |
| copy.splice(i,0,{'match':null, 'body':null, 'fallthrough':true}); |
| } else { |
| copy.splice(i,0,{'match':null, 'body':body, 'fallthrough':fallthrough}); |
| } |
| resultArray.push(copy); |
| }); |
| } |
| } |
| function CopySpec(spec) { |
| var newSpec = []; |
| for(var i = 0; i < spec.length; i++) { |
| var caseSpec = spec[i]; |
| newSpec.push({'match':caseSpec.match, |
| 'body':caseSpec.body, |
| 'fallthrough':caseSpec.fallthrough}); |
| } |
| return newSpec; |
| } |
| |
| |
| function RunSpec(spec, matchVals) { |
| var code = GenerateSwitchCode(spec); |
| |
| // Generate roughly 200 inputs for the test case spec, exercising |
| // every match value, as well as 3 randomly generated values for every |
| // iteration of the match values. |
| var inputs = []; |
| while(inputs.length < 500) { |
| for(var i = 0; i < matchVals.length; i++) { inputs.push(matchVals[i]); } |
| for(var i = 0; i < 3; i++) { inputs.push(RandVal()); } |
| } |
| |
| // Interpret the lookupswitch with the inputs. |
| var interpResults = []; |
| for(var i = 0; i < inputs.length; i++) { |
| InterpretSwitch(spec, inputs[i], interpResults); |
| } |
| |
| // Run compiled lookupswitch with the inputs. |
| var fn = eval("_ = " + code); |
| print("Running spec: " + code); |
| var compileResults = RunCompiled(fn, inputs); |
| print("Done Running spec"); |
| |
| // Verify that they produce the same output. |
| ASSERT(interpResults.length == compileResults.length, "Length mismatch"); |
| for(var i = 0; i < interpResults.length; i++) { |
| ASSERT(interpResults[i] == compileResults[i], "Value mismatch"); |
| } |
| } |
| function RunCompiled(fn, inputs) { |
| var results = []; |
| var len = inputs.length; |
| for(var i = 0; i < len; i++) { fn(inputs[i], results); } |
| return results; |
| } |
| |
| function PrintSpec(spec, inputs, fname) { |
| var code = GenerateSwitchCode(spec, fname); |
| var input_s = fname + ".INPUTS = [" + inputs.map(Repr).join(', ') + "];"; |
| var spec_s = fname + ".SPEC = " + JSON.stringify(spec) + ";"; |
| print(code + "\n" + input_s + "\n" + spec_s); |
| } |
| |
| function RunTest(test) { |
| // Exercise every test case as well as one case which won't match with any of the |
| // ("But what if it randomly generates a string case match whose value is |
| // UNMATCHED_CASE?!", you ask incredulously. Well, RandStr limits itself to 11 chars. |
| // So there.) |
| var inputs = test.INPUTS; |
| inputs.push("UNMATCHED_CASE"); |
| var spec = test.SPEC; |
| |
| var results1 = []; |
| for(var i = 0; i < 80; i++) { |
| for(var j = 0; j < inputs.length; j++) { |
| test(inputs[j], results1); |
| } |
| } |
| |
| var results2 = []; |
| for(var i = 0; i < 80; i++) { |
| for(var j = 0; j < inputs.length; j++) { |
| InterpretSwitch(spec, inputs[j], results2); |
| } |
| } |
| ArraysEqual(results1, results2); |
| } |
| |
| // NOTES: |
| // * RunTest is used within the generated test script. |
| // * InterpretSwitch is printed out into the generated test script. |
| |
| print("/////////////////////////////////////////"); |
| print("// This is a generated file!"); |
| print("// See jit-tests/etc/generate-lookupswitch-tests.js for the code"); |
| print("// that generated this code!"); |
| print("/////////////////////////////////////////"); |
| print(""); |
| print("/////////////////////////////////////////"); |
| print("// PRELUDE //"); |
| print("/////////////////////////////////////////"); |
| print(""); |
| print("// Avoid eager compilation of the global-scope."); |
| print("try{} catch (x) {};"); |
| print(""); |
| print(ASSERT); |
| print(IsNull); |
| print(IsNum); |
| print(ArraysEqual); |
| print(InterpretSwitch); |
| print(RunTest); |
| print(""); |
| print("/////////////////////////////////////////"); |
| print("// TEST CASES //"); |
| print("/////////////////////////////////////////"); |
| print(""); |
| print("var TESTS = [];"); |
| var MATCH_SETS = [["foo", "bar", "zing"]]; |
| var count = 0; |
| for(var i = 0; i < MATCH_SETS.length; i++) { |
| var matchSet = MATCH_SETS[i]; |
| var specs = []; |
| GenerateSpecPermutes(matchSet, specs); |
| for(var j = 0; j < specs.length; j++) { |
| count++; |
| PrintSpec(specs[j], matchSet.slice(), 'test_'+count); |
| print("TESTS.push(test_"+count+");\n"); |
| } |
| } |
| |
| print(""); |
| print("/////////////////////////////////////////"); |
| print("// RUNNER //"); |
| print("/////////////////////////////////////////"); |
| print(""); |
| print("for(var i = 0; i < TESTS.length; i++) {"); |
| print(" RunTest(TESTS[i]);"); |
| print("}"); |