The Tor Browser / file revision

 /**

  * 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("}");