The Tor Browser / file comparison

comparison: js/src/jit-test/etc/generate-lookupswitch-tests.js

js/src/jit-test/etc/generate-lookupswitch-tests.js

changeset 0
6474c204b198
equal deleted inserted replaced
-1:000000000000 0:03b69249da65
1
2 /**
3 * A test case spec is an array of objects of the following kind:
4 * { 'match': Num|Str|Null,
5 * 'body': Num|Str|Null,
6 * 'fallthrough': Boolean }
7 *
8 * If the 'match' is null, then it represents a 'default:'
9 * If the 'match' is not null, it represents a 'case X:' where X is the value.
10 * If the 'body' is null, then it means that the case body is empty. Otherwise,
11 * it means that the case body is a single 'arr.push(V);' where "arr" is an input
12 * array to the function containing the switch statement, and V is the value.
13 * If 'fallthrough' is false, then the body is terminated with a break, otherwise
14 * it is not.
15 *
16 * So a spec: [{'match':3, 'body':null, 'fallthrough':false}, {'match':null, 'body':"foo", 'fallthrough':true}]
17 * Represents a switch function:
18 * function(x, arr) {
19 * switch(x) {
20 * case 3:
21 * break;
22 * default:
23 * arr.push('foo');
24 * }
25 * }
26 *
27 * GenerateSpecPermutes generates a bunch of relevant specs, using the given case match-values,
28 * and appends them to result the array passed into it.
29 *
30 * InterpretSwitch takes a spec, a value, and a result array, and behaves as if the switch specified
31 * by the spec had been called on the value and the result array.
32 *
33 * VerifySwitchSpec is there but not used in the code. I was using it while testing the test case
34 * generator. It verifies that a switch spec is sane.
35 *
36 * RunSpec uses eval to run the test directly. It's not used currently.
37 *
38 * GenerateSwitchCode generates a string of the form "function NAME(x, arg) { .... }" which
39 * contains the switch modeled by its input spec.
40 *
41 * RunTest is there to be used from within the generated script. Its code is dumped out
42 * to the generated script text, and invoked there.
43 *
44 * Hope all of this makes some sort of sense.
45 * -kannan
46 */
47
48 /** HELPERS **/
49
50 function ASSERT(cond, msg) { assertEq(cond, true, msg); }
51
52 function IsUndef(x) { return typeof(x) == 'undefined'; }
53 function IsNull(x) { return typeof(x) == 'object' && x == null; }
54 function IsNum(x) { return typeof(x) == 'number'; }
55 function IsStr(x) { return typeof(x) == 'string'; }
56 function IsBool(x) { return typeof(x) == 'boolean'; }
57
58 function Repr(x) {
59 ASSERT(IsNum(x) || IsStr(x), "Repr");
60 if(IsNum(x)) { return ""+x; }
61 else { return "'"+x+"'"; }
62 }
63
64 function RandBool() { return Math.random() >= 0.5; }
65 function RandInt(max) {
66 if(IsUndef(max)) { max = 0x7fffffff; }
67 return (Math.random() * max)|0;
68 }
69
70 var CHARS = "abcdefghijklmnopqrstuvywxyzABCDEFGHIJKLMNOPQRSTUVYWXYZ0123456789~!@#$%^&*()-_=+{}[]";
71 function RandStr() {
72 var arr = [];
73 var len = Math.floor(Math.random() * 10) + 1;
74 for(var i = 0; i < len; i++) {
75 var c = Math.floor(Math.random() * CHARS.length);
76 arr.push(CHARS[c]);
77 }
78 return arr.join('');
79 }
80
81 function RandVal() { return RandBool() ? RandInt() : RandStr(); }
82
83 /**
84 * Compare two arrays and ensure they are equal.
85 */
86 function ArraysEqual(arr1, arr2) {
87 ASSERT(arr1.length == arr2.length, "Lengths not equal");
88 for(var i = 0; i < arr1.length; i++) {
89 ASSERT(typeof(arr1[i]) == typeof(arr2[i]), "Types not equal for position " + i);
90 ASSERT(arr1[i] == arr2[i], "Values not equal for position " + i);
91 }
92 }
93
94 function VerifySwitchSpec(spec) {
95 var foundDefault = undefined;
96 for(var i = 0; i < spec.length; i++) {
97 var caseSpec = spec[i],
98 match = caseSpec.match,
99 body = caseSpec.body,
100 fallthrough = caseSpec.fallthrough;
101 ASSERT(IsNum(match) || IsStr(match) || IsNull(match), "Invalid case match for " + i);
102 ASSERT(IsNum(body) || IsStr(body) || IsNull(body), "Invalid case body for " + i);
103 ASSERT(IsBool(fallthrough), "Invalid fallthrough for " + i);
104
105 if(IsNull(match)) {
106 ASSERT(IsUndef(foundDefault), "Duplicate default found at " + i);
107 foundDefault = i;
108 }
109 }
110 }
111
112 /**
113 * Do a manual interpretation of a particular spec, given an input
114 * and outputting to an output array.
115 */
116 function InterpretSwitch(spec, input, outputArray) {
117 var foundMatch = undefined, foundDefault = undefined;
118 // Go through cases, trying to find a matching clause.
119 for(var i = 0; i < spec.length; i++) {
120 var caseSpec = spec[i], match = caseSpec.match;
121
122 if(IsNull(match)) {
123 foundDefault = i;
124 continue;
125 } else if(match === input) {
126 foundMatch = i;
127 break;
128 }
129 }
130 // Select either matching clause or default.
131 var matchI = IsNum(foundMatch) ? foundMatch : foundDefault;
132
133 // If match or default was found, interpret body from that point on.
134 if(IsNum(matchI)) {
135 for(var i = matchI; i < spec.length; i++) {
136 var caseSpec = spec[i],
137 match = caseSpec.match,
138 body = caseSpec.body,
139 fallthrough = caseSpec.fallthrough;
140 if(!IsNull(body)) { outputArray.push(body); }
141 if(!fallthrough) { break; }
142 }
143 }
144 }
145
146 /**
147 * Generate the code string for a javascript function containing the
148 * switch specified by the spec, in pure JS syntax.
149 */
150 function GenerateSwitchCode(spec, name) {
151 var lines = [];
152 if(!name) { name = ""; }
153
154 lines.push("function "+name+"(x, arr) {");
155 lines.push(" switch(x) {");
156 for(var i = 0; i < spec.length; i++) {
157 var caseSpec = spec[i],
158 match = caseSpec.match,
159 body = caseSpec.body,
160 fallthrough = caseSpec.fallthrough;
161
162 if(IsNull(match)) { lines.push(" default:"); }
163 else { lines.push(" case "+Repr(match)+":"); }
164
165 if(!IsNull(body)) { lines.push(" arr.push("+Repr(body)+");"); }
166 if(!fallthrough) { lines.push(" break;"); }
167 }
168 lines.push(" }");
169 lines.push("}");
170 return lines.join("\n");
171 }
172
173 /**
174 * Generates all possible specs for a given set of case match values.
175 */
176 function GenerateSpecPermutes(matchVals, resultArray) {
177 ASSERT((0 < matchVals.length) && (matchVals.length <= 5), "Invalid matchVals");
178 var maxPermuteBody = (1 << matchVals.length) - 1;
179 for(var bod_pm = 0; bod_pm <= maxPermuteBody; bod_pm++) {
180 var maxPermuteFallthrough = (1 << matchVals.length) - 1;
181
182 for(var ft_pm = 0; ft_pm <= maxPermuteFallthrough; ft_pm++) {
183 // use bod_m and ft_pm to decide the placement of null vs value bodies,
184 // and the placement of fallthroughs vs breaks.
185 // Empty bodies always fall through, so fallthrough bitmask 1s must be
186 // a subset of the body bitmask 1s.
187 if((bod_pm | ft_pm) != bod_pm) {
188 continue;
189 }
190
191 var spec = [];
192 for(var k = 0; k < matchVals.length; k++) {
193 var match = matchVals[k];
194 var body = ((bod_pm & (1 << k)) > 0) ? null : RandVal();
195 var fallthrough = ((ft_pm & (1 << k)) > 0) ? true : false;
196 var caseSpec = {'match':match, 'body':body, 'fallthrough':fallthrough};
197 spec.push(caseSpec);
198 }
199
200 // Variant specs for following cases:
201
202 // Default with empty body, fallthrough
203 GenerateDefaultPermutes(spec, null, true, resultArray);
204 // Default with nonempty body, fallthrough
205 GenerateDefaultPermutes(spec, RandVal(), true, resultArray);
206 // Default with nonempty body, break
207 GenerateDefaultPermutes(spec, RandVal(), false, resultArray);
208 }
209 }
210 }
211 function GenerateDefaultPermutes(spec, body, fallthrough, resultArray) {
212 if(spec.length <= 2) {
213 for(var i = 0; i <= spec.length; i++) {
214 var copy = CopySpec(spec);
215 if(IsNull(body)) {
216 copy.splice(i,0,{'match':null, 'body':null, 'fallthrough':true});
217 } else {
218 copy.splice(i,0,{'match':null, 'body':body, 'fallthrough':fallthrough});
219 }
220 resultArray.push(copy);
221 }
222 } else {
223 var posns = [0, Math.floor(spec.length / 2), spec.length];
224 posns.forEach(function (i) {
225 var copy = CopySpec(spec);
226 if(IsNull(body)) {
227 copy.splice(i,0,{'match':null, 'body':null, 'fallthrough':true});
228 } else {
229 copy.splice(i,0,{'match':null, 'body':body, 'fallthrough':fallthrough});
230 }
231 resultArray.push(copy);
232 });
233 }
234 }
235 function CopySpec(spec) {
236 var newSpec = [];
237 for(var i = 0; i < spec.length; i++) {
238 var caseSpec = spec[i];
239 newSpec.push({'match':caseSpec.match,
240 'body':caseSpec.body,
241 'fallthrough':caseSpec.fallthrough});
242 }
243 return newSpec;
244 }
245
246
247 function RunSpec(spec, matchVals) {
248 var code = GenerateSwitchCode(spec);
249
250 // Generate roughly 200 inputs for the test case spec, exercising
251 // every match value, as well as 3 randomly generated values for every
252 // iteration of the match values.
253 var inputs = [];
254 while(inputs.length < 500) {
255 for(var i = 0; i < matchVals.length; i++) { inputs.push(matchVals[i]); }
256 for(var i = 0; i < 3; i++) { inputs.push(RandVal()); }
257 }
258
259 // Interpret the lookupswitch with the inputs.
260 var interpResults = [];
261 for(var i = 0; i < inputs.length; i++) {
262 InterpretSwitch(spec, inputs[i], interpResults);
263 }
264
265 // Run compiled lookupswitch with the inputs.
266 var fn = eval("_ = " + code);
267 print("Running spec: " + code);
268 var compileResults = RunCompiled(fn, inputs);
269 print("Done Running spec");
270
271 // Verify that they produce the same output.
272 ASSERT(interpResults.length == compileResults.length, "Length mismatch");
273 for(var i = 0; i < interpResults.length; i++) {
274 ASSERT(interpResults[i] == compileResults[i], "Value mismatch");
275 }
276 }
277 function RunCompiled(fn, inputs) {
278 var results = [];
279 var len = inputs.length;
280 for(var i = 0; i < len; i++) { fn(inputs[i], results); }
281 return results;
282 }
283
284 function PrintSpec(spec, inputs, fname) {
285 var code = GenerateSwitchCode(spec, fname);
286 var input_s = fname + ".INPUTS = [" + inputs.map(Repr).join(', ') + "];";
287 var spec_s = fname + ".SPEC = " + JSON.stringify(spec) + ";";
288 print(code + "\n" + input_s + "\n" + spec_s);
289 }
290
291 function RunTest(test) {
292 // Exercise every test case as well as one case which won't match with any of the
293 // ("But what if it randomly generates a string case match whose value is
294 // UNMATCHED_CASE?!", you ask incredulously. Well, RandStr limits itself to 11 chars.
295 // So there.)
296 var inputs = test.INPUTS;
297 inputs.push("UNMATCHED_CASE");
298 var spec = test.SPEC;
299
300 var results1 = [];
301 for(var i = 0; i < 80; i++) {
302 for(var j = 0; j < inputs.length; j++) {
303 test(inputs[j], results1);
304 }
305 }
306
307 var results2 = [];
308 for(var i = 0; i < 80; i++) {
309 for(var j = 0; j < inputs.length; j++) {
310 InterpretSwitch(spec, inputs[j], results2);
311 }
312 }
313 ArraysEqual(results1, results2);
314 }
315
316 // NOTES:
317 // * RunTest is used within the generated test script.
318 // * InterpretSwitch is printed out into the generated test script.
319
320 print("/////////////////////////////////////////");
321 print("// This is a generated file!");
322 print("// See jit-tests/etc/generate-lookupswitch-tests.js for the code");
323 print("// that generated this code!");
324 print("/////////////////////////////////////////");
325 print("");
326 print("/////////////////////////////////////////");
327 print("// PRELUDE //");
328 print("/////////////////////////////////////////");
329 print("");
330 print("// Avoid eager compilation of the global-scope.");
331 print("try{} catch (x) {};");
332 print("");
333 print(ASSERT);
334 print(IsNull);
335 print(IsNum);
336 print(ArraysEqual);
337 print(InterpretSwitch);
338 print(RunTest);
339 print("");
340 print("/////////////////////////////////////////");
341 print("// TEST CASES //");
342 print("/////////////////////////////////////////");
343 print("");
344 print("var TESTS = [];");
345 var MATCH_SETS = [["foo", "bar", "zing"]];
346 var count = 0;
347 for(var i = 0; i < MATCH_SETS.length; i++) {
348 var matchSet = MATCH_SETS[i];
349 var specs = [];
350 GenerateSpecPermutes(matchSet, specs);
351 for(var j = 0; j < specs.length; j++) {
352 count++;
353 PrintSpec(specs[j], matchSet.slice(), 'test_'+count);
354 print("TESTS.push(test_"+count+");\n");
355 }
356 }
357
358 print("");
359 print("/////////////////////////////////////////");
360 print("// RUNNER //");
361 print("/////////////////////////////////////////");
362 print("");
363 print("for(var i = 0; i < TESTS.length; i++) {");
364 print(" RunTest(TESTS[i]);");
365 print("}");

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial