The Tor Browser / file revision

 // |reftest| skip -- slow

 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

 /* This Source Code Form is subject to the terms of the Mozilla Public

  * License, v. 2.0. If a copy of the MPL was not distributed with this

  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

 //-----------------------------------------------------------------------------

 var BUGNUMBER = 350531;

 var summary = 'exhaustively test parenthesization of binary operator subsets';

 var actual = '';

 var expect = '';

 //-----------------------------------------------------------------------------

 test();

 //-----------------------------------------------------------------------------

 function test()

 {

   enterFunc ('test');

   printBugNumber(BUGNUMBER);

   printStatus (summary);

 // Translated from permcomb.py, found at

 // http://biotech.embl-ebi.ac.uk:8400/sw/common/share/python/examples/dstruct/classics/permcomb.py

 // by searching for "permcomb.py".

 //

 // This shows bugs, gaps, and verbosities in JS compared to Python:

 // 1. Lack of range([start, ] end[, step]).

 // 2. ![] => false, indeed !<any-object> => false.

 // 3. Missing append or push for strings (if append, then we'd want append for

 //    arrays too).

 // 4. Missing slice operator syntax s[i:j].

 // 5. Lack of + for array concatenation.

   String.prototype.push = function (str) { return this + str; };

   function permute(list) {

     if (!list.length)                                   // shuffle any sequence

       return [list];                                    // empty sequence

     var res = [];

     for (var i = 0, n = list.length; i < n; i++) {      // delete current node

       var rest = list.slice(0, i).concat(list.slice(i+1));

       for each (var x in permute(rest))                 // permute the others

         res.push(list.slice(i, i+1).concat(x));         // add node at front

     }

     return res;

   }

   function subset(list, size) {

     if (size == 0 || !list.length)                      // order matters here

       return [list.slice(0, 0)];                        // an empty sequence

     var result = [];

     for (var i = 0, n = list.length; i < n; i++) {

       var pick = list.slice(i, i+1);                    // sequence slice

       var rest = list.slice(0, i).concat(list.slice(i+1)); // keep [:i] part

       for each (var x in subset(rest, size-1))

 	result.push(pick.concat(x));

     }

     return result;

   }

   function combo(list, size) {

     if (size == 0 || !list.length)                      // order doesn't matter

       return [list.slice(0, 0)];                        // xyz == yzx

     var result = [];

     for (var i = 0, n = (list.length - size) + 1; i < n; i++) {

       // iff enough left

       var pick = list.slice(i, i+1);

       var rest = list.slice(i+1);                       // drop [:i] part

       for each (var x in combo(rest, size - 1))

 	result.push(pick.concat(x));

     }

     return result;

   }

 // Generate all subsets of distinct binary operators and join them from left

 // to right, parenthesizing minimally.  Decompile, recompile, compress spaces

 // and compare to test correct parenthesization.

 //  load("permcomb.js");

   var bops = [

     ["=", "|=", "^=", "&=", "<<=", ">>=", ">>>=", "+=", "-=", "*=", "/=", "%="],

     ["||"],

     ["&&"],

     ["|"],

     ["^"],

     ["&"],

     ["==", "!=", "===", "!=="],

     ["<", "<=", ">=", ">", "in", "instanceof"],

     ["<<", ">>", ">>>"],

     ["+", "-"],

     ["*", "/", "%"],

     ];

   var prec = {};

   var aops = [];

   for (var i = 0; i < bops.length; i++) {

     for (var j = 0; j < bops[i].length; j++) {

       var k = bops[i][j];

       prec[k] = i;

       aops.push(k);

     }

   }

 // Theoretically all subsets of size 2 should be enough to test, but in case

 // there's some large-scale bug, try up to 5 (or higher? The cost in memory is

 // factorially explosive).

 next_subset:

   for (i = 2; i < 5; i++) {

     var sets = subset(aops, i);

     gc();

     for each (var set in sets) {

       //print('for each set in sets: ' + (uneval(set)) );

       var src = "(function () {";

       for (j in set) {

         var op = set[j], op2 = set[j-1];

         // Precedence 0 is for assignment ops, which are right-

         // associative, so don't force left associativity using

         // parentheses.

         if (prec[op] && prec[op] < prec[op2])

           src += "(";

       }

       src += "x ";

       for (j in set) {

         var op = set[j], op2 = set[j+1];

         // Parenthesize only if not right-associative (precedence 0) and

         // the next op is higher precedence than current.

         var term = (prec[op] && prec[op] < prec[op2]) ? " x)" : " x";

         src += op + term;

         if (j < set.length - 1)

           src += " ";

       }

       src += ";})";

       try {

         var ref = uneval(eval(src)).replace(/\s+/g, ' ');

         if (ref != src) {

           actual += "BROKEN! input: " + src + " output: " + ref + " ";

           print("BROKEN! input: " + src + " output: " + ref);

           break next_subset;

         }

       } catch (e) {}

     }

   }

   reportCompare(expect, actual, summary);

   exitFunc ('test');

 }