1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
// |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');
}
|
