// |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');
}