michael@0: // |reftest| skip -- slow
michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: //-----------------------------------------------------------------------------
michael@0: var BUGNUMBER = 350531;
michael@0: var summary = 'exhaustively test parenthesization of binary operator subsets';
michael@0: var actual = '';
michael@0: var expect = '';
michael@0: 
michael@0: 
michael@0: //-----------------------------------------------------------------------------
michael@0: test();
michael@0: //-----------------------------------------------------------------------------
michael@0: 
michael@0: function test()
michael@0: {
michael@0:   enterFunc ('test');
michael@0:   printBugNumber(BUGNUMBER);
michael@0:   printStatus (summary);
michael@0:  
michael@0: // Translated from permcomb.py, found at
michael@0: // http://biotech.embl-ebi.ac.uk:8400/sw/common/share/python/examples/dstruct/classics/permcomb.py
michael@0: // by searching for "permcomb.py".
michael@0: //
michael@0: // This shows bugs, gaps, and verbosities in JS compared to Python:
michael@0: // 1. Lack of range([start, ] end[, step]).
michael@0: // 2. ![] => false, indeed !<any-object> => false.
michael@0: // 3. Missing append or push for strings (if append, then we'd want append for
michael@0: //    arrays too).
michael@0: // 4. Missing slice operator syntax s[i:j].
michael@0: // 5. Lack of + for array concatenation.
michael@0: 
michael@0:   String.prototype.push = function (str) { return this + str; };
michael@0: 
michael@0:   function permute(list) {
michael@0:     if (!list.length)                                   // shuffle any sequence
michael@0:       return [list];                                    // empty sequence
michael@0:     var res = [];
michael@0:     for (var i = 0, n = list.length; i < n; i++) {      // delete current node
michael@0:       var rest = list.slice(0, i).concat(list.slice(i+1));
michael@0:       for each (var x in permute(rest))                 // permute the others
michael@0:         res.push(list.slice(i, i+1).concat(x));         // add node at front
michael@0:     }
michael@0:     return res;
michael@0:   }
michael@0: 
michael@0:   function subset(list, size) {
michael@0:     if (size == 0 || !list.length)                      // order matters here
michael@0:       return [list.slice(0, 0)];                        // an empty sequence
michael@0:     var result = [];
michael@0:     for (var i = 0, n = list.length; i < n; i++) {
michael@0:       var pick = list.slice(i, i+1);                    // sequence slice
michael@0:       var rest = list.slice(0, i).concat(list.slice(i+1)); // keep [:i] part
michael@0:       for each (var x in subset(rest, size-1))
michael@0: 	result.push(pick.concat(x));
michael@0:     }
michael@0:     return result;
michael@0:   }
michael@0: 
michael@0:   function combo(list, size) {
michael@0:     if (size == 0 || !list.length)                      // order doesn't matter
michael@0:       return [list.slice(0, 0)];                        // xyz == yzx
michael@0:     var result = [];
michael@0:     for (var i = 0, n = (list.length - size) + 1; i < n; i++) {
michael@0:       // iff enough left
michael@0:       var pick = list.slice(i, i+1);
michael@0:       var rest = list.slice(i+1);                       // drop [:i] part
michael@0:       for each (var x in combo(rest, size - 1))
michael@0: 	result.push(pick.concat(x));
michael@0:     }
michael@0:     return result;
michael@0:   }
michael@0: 
michael@0: 
michael@0: // Generate all subsets of distinct binary operators and join them from left
michael@0: // to right, parenthesizing minimally.  Decompile, recompile, compress spaces
michael@0: // and compare to test correct parenthesization.
michael@0: 
michael@0: //  load("permcomb.js");
michael@0: 
michael@0:   var bops = [
michael@0:     ["=", "|=", "^=", "&=", "<<=", ">>=", ">>>=", "+=", "-=", "*=", "/=", "%="],
michael@0:     ["||"],
michael@0:     ["&&"],
michael@0:     ["|"],
michael@0:     ["^"],
michael@0:     ["&"],
michael@0:     ["==", "!=", "===", "!=="],
michael@0:     ["<", "<=", ">=", ">", "in", "instanceof"],
michael@0:     ["<<", ">>", ">>>"],
michael@0:     ["+", "-"],
michael@0:     ["*", "/", "%"],
michael@0:     ];
michael@0: 
michael@0:   var prec = {};
michael@0:   var aops = [];
michael@0: 
michael@0:   for (var i = 0; i < bops.length; i++) {
michael@0:     for (var j = 0; j < bops[i].length; j++) {
michael@0:       var k = bops[i][j];
michael@0:       prec[k] = i;
michael@0:       aops.push(k);
michael@0:     }
michael@0:   }
michael@0: 
michael@0: // Theoretically all subsets of size 2 should be enough to test, but in case
michael@0: // there's some large-scale bug, try up to 5 (or higher? The cost in memory is
michael@0: // factorially explosive).
michael@0: next_subset:
michael@0:   for (i = 2; i < 5; i++) {
michael@0:     var sets = subset(aops, i);
michael@0:     gc();
michael@0: 
michael@0:     for each (var set in sets) {
michael@0:       //print('for each set in sets: ' + (uneval(set)) );
michael@0:       var src = "(function () {";
michael@0:       for (j in set) {
michael@0:         var op = set[j], op2 = set[j-1];
michael@0: 
michael@0:         // Precedence 0 is for assignment ops, which are right-
michael@0:         // associative, so don't force left associativity using
michael@0:         // parentheses.
michael@0:         if (prec[op] && prec[op] < prec[op2])
michael@0:           src += "(";
michael@0:       }
michael@0:       src += "x ";
michael@0:       for (j in set) {
michael@0:         var op = set[j], op2 = set[j+1];
michael@0: 
michael@0:         // Parenthesize only if not right-associative (precedence 0) and
michael@0:         // the next op is higher precedence than current.
michael@0:         var term = (prec[op] && prec[op] < prec[op2]) ? " x)" : " x";
michael@0: 
michael@0:         src += op + term;
michael@0:         if (j < set.length - 1)
michael@0:           src += " ";
michael@0:       }
michael@0:       src += ";})";
michael@0:       try {
michael@0:         var ref = uneval(eval(src)).replace(/\s+/g, ' ');
michael@0:         if (ref != src) {
michael@0:           actual += "BROKEN! input: " + src + " output: " + ref + " ";
michael@0:           print("BROKEN! input: " + src + " output: " + ref);
michael@0:           break next_subset;
michael@0:         }
michael@0:       } catch (e) {}
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   reportCompare(expect, actual, summary);
michael@0: 
michael@0:   exitFunc ('test');
michael@0: }