1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jit-test/etc/generate-lookupswitch-tests.js Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,365 @@
1.4 +
1.5 +/**
1.6 + * A test case spec is an array of objects of the following kind:
1.7 + * { 'match': Num|Str|Null,
1.8 + * 'body': Num|Str|Null,
1.9 + * 'fallthrough': Boolean }
1.10 + *
1.11 + * If the 'match' is null, then it represents a 'default:'
1.12 + * If the 'match' is not null, it represents a 'case X:' where X is the value.
1.13 + * If the 'body' is null, then it means that the case body is empty. Otherwise,
1.14 + * it means that the case body is a single 'arr.push(V);' where "arr" is an input
1.15 + * array to the function containing the switch statement, and V is the value.
1.16 + * If 'fallthrough' is false, then the body is terminated with a break, otherwise
1.17 + * it is not.
1.18 + *
1.19 + * So a spec: [{'match':3, 'body':null, 'fallthrough':false}, {'match':null, 'body':"foo", 'fallthrough':true}]
1.20 + * Represents a switch function:
1.21 + * function(x, arr) {
1.22 + * switch(x) {
1.23 + * case 3:
1.24 + * break;
1.25 + * default:
1.26 + * arr.push('foo');
1.27 + * }
1.28 + * }
1.29 + *
1.30 + * GenerateSpecPermutes generates a bunch of relevant specs, using the given case match-values,
1.31 + * and appends them to result the array passed into it.
1.32 + *
1.33 + * InterpretSwitch takes a spec, a value, and a result array, and behaves as if the switch specified
1.34 + * by the spec had been called on the value and the result array.
1.35 + *
1.36 + * VerifySwitchSpec is there but not used in the code. I was using it while testing the test case
1.37 + * generator. It verifies that a switch spec is sane.
1.38 + *
1.39 + * RunSpec uses eval to run the test directly. It's not used currently.
1.40 + *
1.41 + * GenerateSwitchCode generates a string of the form "function NAME(x, arg) { .... }" which
1.42 + * contains the switch modeled by its input spec.
1.43 + *
1.44 + * RunTest is there to be used from within the generated script. Its code is dumped out
1.45 + * to the generated script text, and invoked there.
1.46 + *
1.47 + * Hope all of this makes some sort of sense.
1.48 + * -kannan
1.49 + */
1.50 +
1.51 +/** HELPERS **/
1.52 +
1.53 +function ASSERT(cond, msg) { assertEq(cond, true, msg); }
1.54 +
1.55 +function IsUndef(x) { return typeof(x) == 'undefined'; }
1.56 +function IsNull(x) { return typeof(x) == 'object' && x == null; }
1.57 +function IsNum(x) { return typeof(x) == 'number'; }
1.58 +function IsStr(x) { return typeof(x) == 'string'; }
1.59 +function IsBool(x) { return typeof(x) == 'boolean'; }
1.60 +
1.61 +function Repr(x) {
1.62 + ASSERT(IsNum(x) || IsStr(x), "Repr");
1.63 + if(IsNum(x)) { return ""+x; }
1.64 + else { return "'"+x+"'"; }
1.65 +}
1.66 +
1.67 +function RandBool() { return Math.random() >= 0.5; }
1.68 +function RandInt(max) {
1.69 + if(IsUndef(max)) { max = 0x7fffffff; }
1.70 + return (Math.random() * max)|0;
1.71 +}
1.72 +
1.73 +var CHARS = "abcdefghijklmnopqrstuvywxyzABCDEFGHIJKLMNOPQRSTUVYWXYZ0123456789~!@#$%^&*()-_=+{}[]";
1.74 +function RandStr() {
1.75 + var arr = [];
1.76 + var len = Math.floor(Math.random() * 10) + 1;
1.77 + for(var i = 0; i < len; i++) {
1.78 + var c = Math.floor(Math.random() * CHARS.length);
1.79 + arr.push(CHARS[c]);
1.80 + }
1.81 + return arr.join('');
1.82 +}
1.83 +
1.84 +function RandVal() { return RandBool() ? RandInt() : RandStr(); }
1.85 +
1.86 +/**
1.87 + * Compare two arrays and ensure they are equal.
1.88 + */
1.89 +function ArraysEqual(arr1, arr2) {
1.90 + ASSERT(arr1.length == arr2.length, "Lengths not equal");
1.91 + for(var i = 0; i < arr1.length; i++) {
1.92 + ASSERT(typeof(arr1[i]) == typeof(arr2[i]), "Types not equal for position " + i);
1.93 + ASSERT(arr1[i] == arr2[i], "Values not equal for position " + i);
1.94 + }
1.95 +}
1.96 +
1.97 +function VerifySwitchSpec(spec) {
1.98 + var foundDefault = undefined;
1.99 + for(var i = 0; i < spec.length; i++) {
1.100 + var caseSpec = spec[i],
1.101 + match = caseSpec.match,
1.102 + body = caseSpec.body,
1.103 + fallthrough = caseSpec.fallthrough;
1.104 + ASSERT(IsNum(match) || IsStr(match) || IsNull(match), "Invalid case match for " + i);
1.105 + ASSERT(IsNum(body) || IsStr(body) || IsNull(body), "Invalid case body for " + i);
1.106 + ASSERT(IsBool(fallthrough), "Invalid fallthrough for " + i);
1.107 +
1.108 + if(IsNull(match)) {
1.109 + ASSERT(IsUndef(foundDefault), "Duplicate default found at " + i);
1.110 + foundDefault = i;
1.111 + }
1.112 + }
1.113 +}
1.114 +
1.115 +/**
1.116 + * Do a manual interpretation of a particular spec, given an input
1.117 + * and outputting to an output array.
1.118 + */
1.119 +function InterpretSwitch(spec, input, outputArray) {
1.120 + var foundMatch = undefined, foundDefault = undefined;
1.121 + // Go through cases, trying to find a matching clause.
1.122 + for(var i = 0; i < spec.length; i++) {
1.123 + var caseSpec = spec[i], match = caseSpec.match;
1.124 +
1.125 + if(IsNull(match)) {
1.126 + foundDefault = i;
1.127 + continue;
1.128 + } else if(match === input) {
1.129 + foundMatch = i;
1.130 + break;
1.131 + }
1.132 + }
1.133 + // Select either matching clause or default.
1.134 + var matchI = IsNum(foundMatch) ? foundMatch : foundDefault;
1.135 +
1.136 + // If match or default was found, interpret body from that point on.
1.137 + if(IsNum(matchI)) {
1.138 + for(var i = matchI; i < spec.length; i++) {
1.139 + var caseSpec = spec[i],
1.140 + match = caseSpec.match,
1.141 + body = caseSpec.body,
1.142 + fallthrough = caseSpec.fallthrough;
1.143 + if(!IsNull(body)) { outputArray.push(body); }
1.144 + if(!fallthrough) { break; }
1.145 + }
1.146 + }
1.147 +}
1.148 +
1.149 +/**
1.150 + * Generate the code string for a javascript function containing the
1.151 + * switch specified by the spec, in pure JS syntax.
1.152 + */
1.153 +function GenerateSwitchCode(spec, name) {
1.154 + var lines = [];
1.155 + if(!name) { name = ""; }
1.156 +
1.157 + lines.push("function "+name+"(x, arr) {");
1.158 + lines.push(" switch(x) {");
1.159 + for(var i = 0; i < spec.length; i++) {
1.160 + var caseSpec = spec[i],
1.161 + match = caseSpec.match,
1.162 + body = caseSpec.body,
1.163 + fallthrough = caseSpec.fallthrough;
1.164 +
1.165 + if(IsNull(match)) { lines.push(" default:"); }
1.166 + else { lines.push(" case "+Repr(match)+":"); }
1.167 +
1.168 + if(!IsNull(body)) { lines.push(" arr.push("+Repr(body)+");"); }
1.169 + if(!fallthrough) { lines.push(" break;"); }
1.170 + }
1.171 + lines.push(" }");
1.172 + lines.push("}");
1.173 + return lines.join("\n");
1.174 +}
1.175 +
1.176 +/**
1.177 + * Generates all possible specs for a given set of case match values.
1.178 + */
1.179 +function GenerateSpecPermutes(matchVals, resultArray) {
1.180 + ASSERT((0 < matchVals.length) && (matchVals.length <= 5), "Invalid matchVals");
1.181 + var maxPermuteBody = (1 << matchVals.length) - 1;
1.182 + for(var bod_pm = 0; bod_pm <= maxPermuteBody; bod_pm++) {
1.183 + var maxPermuteFallthrough = (1 << matchVals.length) - 1;
1.184 +
1.185 + for(var ft_pm = 0; ft_pm <= maxPermuteFallthrough; ft_pm++) {
1.186 + // use bod_m and ft_pm to decide the placement of null vs value bodies,
1.187 + // and the placement of fallthroughs vs breaks.
1.188 + // Empty bodies always fall through, so fallthrough bitmask 1s must be
1.189 + // a subset of the body bitmask 1s.
1.190 + if((bod_pm | ft_pm) != bod_pm) {
1.191 + continue;
1.192 + }
1.193 +
1.194 + var spec = [];
1.195 + for(var k = 0; k < matchVals.length; k++) {
1.196 + var match = matchVals[k];
1.197 + var body = ((bod_pm & (1 << k)) > 0) ? null : RandVal();
1.198 + var fallthrough = ((ft_pm & (1 << k)) > 0) ? true : false;
1.199 + var caseSpec = {'match':match, 'body':body, 'fallthrough':fallthrough};
1.200 + spec.push(caseSpec);
1.201 + }
1.202 +
1.203 + // Variant specs for following cases:
1.204 +
1.205 + // Default with empty body, fallthrough
1.206 + GenerateDefaultPermutes(spec, null, true, resultArray);
1.207 + // Default with nonempty body, fallthrough
1.208 + GenerateDefaultPermutes(spec, RandVal(), true, resultArray);
1.209 + // Default with nonempty body, break
1.210 + GenerateDefaultPermutes(spec, RandVal(), false, resultArray);
1.211 + }
1.212 + }
1.213 +}
1.214 +function GenerateDefaultPermutes(spec, body, fallthrough, resultArray) {
1.215 + if(spec.length <= 2) {
1.216 + for(var i = 0; i <= spec.length; i++) {
1.217 + var copy = CopySpec(spec);
1.218 + if(IsNull(body)) {
1.219 + copy.splice(i,0,{'match':null, 'body':null, 'fallthrough':true});
1.220 + } else {
1.221 + copy.splice(i,0,{'match':null, 'body':body, 'fallthrough':fallthrough});
1.222 + }
1.223 + resultArray.push(copy);
1.224 + }
1.225 + } else {
1.226 + var posns = [0, Math.floor(spec.length / 2), spec.length];
1.227 + posns.forEach(function (i) {
1.228 + var copy = CopySpec(spec);
1.229 + if(IsNull(body)) {
1.230 + copy.splice(i,0,{'match':null, 'body':null, 'fallthrough':true});
1.231 + } else {
1.232 + copy.splice(i,0,{'match':null, 'body':body, 'fallthrough':fallthrough});
1.233 + }
1.234 + resultArray.push(copy);
1.235 + });
1.236 + }
1.237 +}
1.238 +function CopySpec(spec) {
1.239 + var newSpec = [];
1.240 + for(var i = 0; i < spec.length; i++) {
1.241 + var caseSpec = spec[i];
1.242 + newSpec.push({'match':caseSpec.match,
1.243 + 'body':caseSpec.body,
1.244 + 'fallthrough':caseSpec.fallthrough});
1.245 + }
1.246 + return newSpec;
1.247 +}
1.248 +
1.249 +
1.250 +function RunSpec(spec, matchVals) {
1.251 + var code = GenerateSwitchCode(spec);
1.252 +
1.253 + // Generate roughly 200 inputs for the test case spec, exercising
1.254 + // every match value, as well as 3 randomly generated values for every
1.255 + // iteration of the match values.
1.256 + var inputs = [];
1.257 + while(inputs.length < 500) {
1.258 + for(var i = 0; i < matchVals.length; i++) { inputs.push(matchVals[i]); }
1.259 + for(var i = 0; i < 3; i++) { inputs.push(RandVal()); }
1.260 + }
1.261 +
1.262 + // Interpret the lookupswitch with the inputs.
1.263 + var interpResults = [];
1.264 + for(var i = 0; i < inputs.length; i++) {
1.265 + InterpretSwitch(spec, inputs[i], interpResults);
1.266 + }
1.267 +
1.268 + // Run compiled lookupswitch with the inputs.
1.269 + var fn = eval("_ = " + code);
1.270 + print("Running spec: " + code);
1.271 + var compileResults = RunCompiled(fn, inputs);
1.272 + print("Done Running spec");
1.273 +
1.274 + // Verify that they produce the same output.
1.275 + ASSERT(interpResults.length == compileResults.length, "Length mismatch");
1.276 + for(var i = 0; i < interpResults.length; i++) {
1.277 + ASSERT(interpResults[i] == compileResults[i], "Value mismatch");
1.278 + }
1.279 +}
1.280 +function RunCompiled(fn, inputs) {
1.281 + var results = [];
1.282 + var len = inputs.length;
1.283 + for(var i = 0; i < len; i++) { fn(inputs[i], results); }
1.284 + return results;
1.285 +}
1.286 +
1.287 +function PrintSpec(spec, inputs, fname) {
1.288 + var code = GenerateSwitchCode(spec, fname);
1.289 + var input_s = fname + ".INPUTS = [" + inputs.map(Repr).join(', ') + "];";
1.290 + var spec_s = fname + ".SPEC = " + JSON.stringify(spec) + ";";
1.291 + print(code + "\n" + input_s + "\n" + spec_s);
1.292 +}
1.293 +
1.294 +function RunTest(test) {
1.295 + // Exercise every test case as well as one case which won't match with any of the
1.296 + // ("But what if it randomly generates a string case match whose value is
1.297 + // UNMATCHED_CASE?!", you ask incredulously. Well, RandStr limits itself to 11 chars.
1.298 + // So there.)
1.299 + var inputs = test.INPUTS;
1.300 + inputs.push("UNMATCHED_CASE");
1.301 + var spec = test.SPEC;
1.302 +
1.303 + var results1 = [];
1.304 + for(var i = 0; i < 80; i++) {
1.305 + for(var j = 0; j < inputs.length; j++) {
1.306 + test(inputs[j], results1);
1.307 + }
1.308 + }
1.309 +
1.310 + var results2 = [];
1.311 + for(var i = 0; i < 80; i++) {
1.312 + for(var j = 0; j < inputs.length; j++) {
1.313 + InterpretSwitch(spec, inputs[j], results2);
1.314 + }
1.315 + }
1.316 + ArraysEqual(results1, results2);
1.317 +}
1.318 +
1.319 +// NOTES:
1.320 +// * RunTest is used within the generated test script.
1.321 +// * InterpretSwitch is printed out into the generated test script.
1.322 +
1.323 +print("/////////////////////////////////////////");
1.324 +print("// This is a generated file!");
1.325 +print("// See jit-tests/etc/generate-lookupswitch-tests.js for the code");
1.326 +print("// that generated this code!");
1.327 +print("/////////////////////////////////////////");
1.328 +print("");
1.329 +print("/////////////////////////////////////////");
1.330 +print("// PRELUDE //");
1.331 +print("/////////////////////////////////////////");
1.332 +print("");
1.333 +print("// Avoid eager compilation of the global-scope.");
1.334 +print("try{} catch (x) {};");
1.335 +print("");
1.336 +print(ASSERT);
1.337 +print(IsNull);
1.338 +print(IsNum);
1.339 +print(ArraysEqual);
1.340 +print(InterpretSwitch);
1.341 +print(RunTest);
1.342 +print("");
1.343 +print("/////////////////////////////////////////");
1.344 +print("// TEST CASES //");
1.345 +print("/////////////////////////////////////////");
1.346 +print("");
1.347 +print("var TESTS = [];");
1.348 +var MATCH_SETS = [["foo", "bar", "zing"]];
1.349 +var count = 0;
1.350 +for(var i = 0; i < MATCH_SETS.length; i++) {
1.351 + var matchSet = MATCH_SETS[i];
1.352 + var specs = [];
1.353 + GenerateSpecPermutes(matchSet, specs);
1.354 + for(var j = 0; j < specs.length; j++) {
1.355 + count++;
1.356 + PrintSpec(specs[j], matchSet.slice(), 'test_'+count);
1.357 + print("TESTS.push(test_"+count+");\n");
1.358 + }
1.359 +}
1.360 +
1.361 +print("");
1.362 +print("/////////////////////////////////////////");
1.363 +print("// RUNNER //");
1.364 +print("/////////////////////////////////////////");
1.365 +print("");
1.366 +print("for(var i = 0; i < TESTS.length; i++) {");
1.367 +print(" RunTest(TESTS[i]);");
1.368 +print("}");
