• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1// Copyright 2009 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28/**
29 * @fileoverview Test reduce and reduceRight
30 */
31
32function clone(v) {
33  // Shallow-copies arrays, returns everything else verbatim.
34  if (v instanceof Array) {
35    // Shallow-copy an array.
36    var newArray = new Array(v.length);
37    for (var i in v) {
38      newArray[i] = v[i];
39    }
40    return newArray;
41  }
42  return v;
43}
44
45
46// Creates a callback function for reduce/reduceRight that tests the number
47// of arguments and otherwise behaves as "func", but which also
48// records all calls in an array on the function (as arrays of arguments
49// followed by result).
50function makeRecorder(func, testName) {
51  var record = [];
52  var f = function recorder(a, b, i, s) {
53    assertEquals(4, arguments.length,
54                 testName + "(number of arguments: " + arguments.length + ")");
55    assertEquals("number", typeof(i), testName + "(index must be number)");
56    assertEquals(s[i], b, testName + "(current argument is at index)");
57    if (record.length > 0) {
58      var prevRecord = record[record.length - 1];
59      var prevResult = prevRecord[prevRecord.length - 1];
60      assertEquals(prevResult, a,
61                   testName + "(prev result -> current input)");
62    }
63    var args = [clone(a), clone(b), i, clone(s)];
64    var result = func.apply(this, arguments);
65    args.push(clone(result));
66    record.push(args);
67    return result;
68  };
69  f.record = record;
70  return f;
71}
72
73
74function testReduce(type,
75                    testName,
76                    expectedResult,
77                    expectedCalls,
78                    array,
79                    combine,
80                    init) {
81  var rec = makeRecorder(combine);
82  var result;
83  var performsCall;
84  if (arguments.length > 6) {
85    result = array[type](rec, init);
86  } else {
87    result = array[type](rec);
88  }
89  var calls = rec.record;
90  assertEquals(expectedCalls.length, calls.length,
91               testName + " (number of calls)");
92  for (var i = 0; i < expectedCalls.length; i++) {
93    assertEquals(expectedCalls[i], calls[i],
94                 testName + " (call " + (i + 1) + ")");
95  }
96  assertEquals(expectedResult, result, testName + " (result)");
97}
98
99
100function sum(a, b) { return a + b; }
101function prod(a, b) { return a * b; }
102function dec(a, b, i, arr) { return a + b * Math.pow(10, arr.length - i - 1); }
103function accumulate(acc, elem, i) { acc[i] = elem; return acc; }
104
105// ---- Test Reduce[Left]
106
107var simpleArray = [2,4,6]
108
109testReduce("reduce", "SimpleReduceSum", 12,
110           [[0, 2, 0, simpleArray, 2],
111            [2, 4, 1, simpleArray, 6],
112            [6, 6, 2, simpleArray, 12]],
113           simpleArray, sum, 0);
114
115testReduce("reduce", "SimpleReduceProd", 48,
116           [[1, 2, 0, simpleArray, 2],
117            [2, 4, 1, simpleArray, 8],
118            [8, 6, 2, simpleArray, 48]],
119           simpleArray, prod, 1);
120
121testReduce("reduce", "SimpleReduceDec", 246,
122           [[0, 2, 0, simpleArray, 200],
123            [200, 4, 1, simpleArray, 240],
124            [240, 6, 2, simpleArray, 246]],
125           simpleArray, dec, 0);
126
127testReduce("reduce", "SimpleReduceAccumulate", simpleArray,
128           [[[], 2, 0, simpleArray, [2]],
129            [[2], 4, 1, simpleArray, [2, 4]],
130            [[2,4], 6, 2, simpleArray, simpleArray]],
131           simpleArray, accumulate, []);
132
133
134testReduce("reduce", "EmptyReduceSum", 0, [], [], sum, 0);
135testReduce("reduce", "EmptyReduceProd", 1, [], [], prod, 1);
136testReduce("reduce", "EmptyReduceDec", 0, [], [], dec, 0);
137testReduce("reduce", "EmptyReduceAccumulate", [], [], [], accumulate, []);
138
139testReduce("reduce", "EmptyReduceSumNoInit", 0, [], [0], sum);
140testReduce("reduce", "EmptyReduceProdNoInit", 1, [], [1], prod);
141testReduce("reduce", "EmptyReduceDecNoInit", 0, [], [0], dec);
142testReduce("reduce", "EmptyReduceAccumulateNoInit", [], [], [[]], accumulate);
143
144
145var simpleSparseArray = [,,,2,,4,,6,,];
146testReduce("reduce", "SimpleSparseReduceSum", 12,
147           [[0, 2, 3, simpleSparseArray, 2],
148            [2, 4, 5, simpleSparseArray, 6],
149            [6, 6, 7, simpleSparseArray, 12]],
150           simpleSparseArray, sum, 0);
151
152testReduce("reduce", "SimpleSparseReduceProd", 48,
153           [[1, 2, 3, simpleSparseArray, 2],
154            [2, 4, 5, simpleSparseArray, 8],
155            [8, 6, 7, simpleSparseArray, 48]],
156           simpleSparseArray, prod, 1);
157
158testReduce("reduce", "SimpleSparseReduceDec", 204060,
159           [[0, 2, 3, simpleSparseArray, 200000],
160            [200000, 4, 5, simpleSparseArray, 204000],
161            [204000, 6, 7, simpleSparseArray, 204060]],
162           simpleSparseArray, dec, 0);
163
164testReduce("reduce", "SimpleSparseReduceAccumulate", [,,,2,,4,,6],
165           [[[], 2, 3, simpleSparseArray, [,,,2]],
166            [[,,,2], 4, 5, simpleSparseArray, [,,,2,,4]],
167            [[,,,2,,4], 6, 7, simpleSparseArray, [,,,2,,4,,6]]],
168           simpleSparseArray, accumulate, []);
169
170
171testReduce("reduce", "EmptySparseReduceSumNoInit", 0, [], [,,0,,], sum);
172testReduce("reduce", "EmptySparseReduceProdNoInit", 1, [], [,,1,,], prod);
173testReduce("reduce", "EmptySparseReduceDecNoInit", 0, [], [,,0,,], dec);
174testReduce("reduce", "EmptySparseReduceAccumulateNoInit",
175           [], [], [,,[],,], accumulate);
176
177
178var verySparseArray = [];
179verySparseArray.length = 10000;
180verySparseArray[2000] = 2;
181verySparseArray[5000] = 4;
182verySparseArray[9000] = 6;
183var verySparseSlice2 = verySparseArray.slice(0, 2001);
184var verySparseSlice4 = verySparseArray.slice(0, 5001);
185var verySparseSlice6 = verySparseArray.slice(0, 9001);
186
187testReduce("reduce", "VerySparseReduceSum", 12,
188           [[0, 2, 2000, verySparseArray, 2],
189            [2, 4, 5000, verySparseArray, 6],
190            [6, 6, 9000, verySparseArray, 12]],
191           verySparseArray, sum, 0);
192
193testReduce("reduce", "VerySparseReduceProd", 48,
194           [[1, 2, 2000, verySparseArray, 2],
195            [2, 4, 5000, verySparseArray, 8],
196            [8, 6, 9000, verySparseArray, 48]],
197           verySparseArray, prod, 1);
198
199testReduce("reduce", "VerySparseReduceDec", Infinity,
200           [[0, 2, 2000, verySparseArray, Infinity],
201            [Infinity, 4, 5000, verySparseArray, Infinity],
202            [Infinity, 6, 9000, verySparseArray, Infinity]],
203           verySparseArray, dec, 0);
204
205testReduce("reduce", "VerySparseReduceAccumulate",
206           verySparseSlice6,
207           [[[], 2, 2000, verySparseArray, verySparseSlice2],
208            [verySparseSlice2, 4, 5000, verySparseArray, verySparseSlice4],
209            [verySparseSlice4, 6, 9000, verySparseArray, verySparseSlice6]],
210           verySparseArray, accumulate, []);
211
212
213testReduce("reduce", "VerySparseReduceSumNoInit", 12,
214           [[2, 4, 5000, verySparseArray, 6],
215            [6, 6, 9000, verySparseArray, 12]],
216           verySparseArray, sum);
217
218testReduce("reduce", "VerySparseReduceProdNoInit", 48,
219           [[2, 4, 5000, verySparseArray, 8],
220            [8, 6, 9000, verySparseArray, 48]],
221           verySparseArray, prod);
222
223testReduce("reduce", "VerySparseReduceDecNoInit", Infinity,
224           [[2, 4, 5000, verySparseArray, Infinity],
225            [Infinity, 6, 9000, verySparseArray, Infinity]],
226           verySparseArray, dec);
227
228testReduce("reduce", "SimpleSparseReduceAccumulateNoInit",
229           2,
230           [[2, 4, 5000, verySparseArray, 2],
231            [2, 6, 9000, verySparseArray, 2]],
232           verySparseArray, accumulate);
233
234
235// ---- Test ReduceRight
236
237testReduce("reduceRight", "SimpleReduceRightSum", 12,
238           [[0, 6, 2, simpleArray, 6],
239            [6, 4, 1, simpleArray, 10],
240            [10, 2, 0, simpleArray, 12]],
241           simpleArray, sum, 0);
242
243testReduce("reduceRight", "SimpleReduceRightProd", 48,
244           [[1, 6, 2, simpleArray, 6],
245            [6, 4, 1, simpleArray, 24],
246            [24, 2, 0, simpleArray, 48]],
247           simpleArray, prod, 1);
248
249testReduce("reduceRight", "SimpleReduceRightDec", 246,
250           [[0, 6, 2, simpleArray, 6],
251            [6, 4, 1, simpleArray, 46],
252            [46, 2, 0, simpleArray, 246]],
253           simpleArray, dec, 0);
254
255testReduce("reduceRight", "SimpleReduceRightAccumulate", simpleArray,
256           [[[], 6, 2, simpleArray, [,,6]],
257            [[,,6], 4, 1, simpleArray, [,4,6]],
258            [[,4,6], 2, 0, simpleArray, simpleArray]],
259           simpleArray, accumulate, []);
260
261
262testReduce("reduceRight", "EmptyReduceRightSum", 0, [], [], sum, 0);
263testReduce("reduceRight", "EmptyReduceRightProd", 1, [], [], prod, 1);
264testReduce("reduceRight", "EmptyReduceRightDec", 0, [], [], dec, 0);
265testReduce("reduceRight", "EmptyReduceRightAccumulate", [],
266           [], [], accumulate, []);
267
268testReduce("reduceRight", "EmptyReduceRightSumNoInit", 0, [], [0], sum);
269testReduce("reduceRight", "EmptyReduceRightProdNoInit", 1, [], [1], prod);
270testReduce("reduceRight", "EmptyReduceRightDecNoInit", 0, [], [0], dec);
271testReduce("reduceRight", "EmptyReduceRightAccumulateNoInit",
272           [], [], [[]], accumulate);
273
274
275testReduce("reduceRight", "SimpleSparseReduceRightSum", 12,
276           [[0, 6, 7, simpleSparseArray, 6],
277            [6, 4, 5, simpleSparseArray, 10],
278            [10, 2, 3, simpleSparseArray, 12]],
279           simpleSparseArray, sum, 0);
280
281testReduce("reduceRight", "SimpleSparseReduceRightProd", 48,
282           [[1, 6, 7, simpleSparseArray, 6],
283            [6, 4, 5, simpleSparseArray, 24],
284            [24, 2, 3, simpleSparseArray, 48]],
285           simpleSparseArray, prod, 1);
286
287testReduce("reduceRight", "SimpleSparseReduceRightDec", 204060,
288           [[0, 6, 7, simpleSparseArray, 60],
289            [60, 4, 5, simpleSparseArray, 4060],
290            [4060, 2, 3, simpleSparseArray, 204060]],
291           simpleSparseArray, dec, 0);
292
293testReduce("reduceRight", "SimpleSparseReduceRightAccumulate", [,,,2,,4,,6],
294           [[[], 6, 7, simpleSparseArray, [,,,,,,,6]],
295            [[,,,,,,,6], 4, 5, simpleSparseArray, [,,,,,4,,6]],
296            [[,,,,,4,,6], 2, 3, simpleSparseArray, [,,,2,,4,,6]]],
297           simpleSparseArray, accumulate, []);
298
299
300testReduce("reduceRight", "EmptySparseReduceRightSumNoInit",
301           0, [], [,,0,,], sum);
302testReduce("reduceRight", "EmptySparseReduceRightProdNoInit",
303           1, [], [,,1,,], prod);
304testReduce("reduceRight", "EmptySparseReduceRightDecNoInit",
305           0, [], [,,0,,], dec);
306testReduce("reduceRight", "EmptySparseReduceRightAccumulateNoInit",
307           [], [], [,,[],,], accumulate);
308
309
310var verySparseSuffix6 = [];
311verySparseSuffix6[9000] = 6;
312var verySparseSuffix4 = [];
313verySparseSuffix4[5000] = 4;
314verySparseSuffix4[9000] = 6;
315var verySparseSuffix2 = verySparseSlice6;
316
317
318testReduce("reduceRight", "VerySparseReduceRightSum", 12,
319           [[0, 6, 9000, verySparseArray, 6],
320            [6, 4, 5000, verySparseArray, 10],
321            [10, 2, 2000, verySparseArray, 12]],
322           verySparseArray, sum, 0);
323
324testReduce("reduceRight", "VerySparseReduceRightProd", 48,
325           [[1, 6, 9000, verySparseArray, 6],
326            [6, 4, 5000, verySparseArray, 24],
327            [24, 2, 2000, verySparseArray, 48]],
328           verySparseArray, prod, 1);
329
330testReduce("reduceRight", "VerySparseReduceRightDec", Infinity,
331           [[0, 6, 9000, verySparseArray, Infinity],
332            [Infinity, 4, 5000, verySparseArray, Infinity],
333            [Infinity, 2, 2000, verySparseArray, Infinity]],
334           verySparseArray, dec, 0);
335
336testReduce("reduceRight", "VerySparseReduceRightAccumulate",
337           verySparseSuffix2,
338           [[[], 6, 9000, verySparseArray, verySparseSuffix6],
339            [verySparseSuffix6, 4, 5000, verySparseArray, verySparseSuffix4],
340            [verySparseSuffix4, 2, 2000, verySparseArray, verySparseSuffix2]],
341           verySparseArray, accumulate, []);
342
343
344testReduce("reduceRight", "VerySparseReduceRightSumNoInit", 12,
345           [[6, 4, 5000, verySparseArray, 10],
346            [10, 2, 2000, verySparseArray, 12]],
347           verySparseArray, sum);
348
349testReduce("reduceRight", "VerySparseReduceRightProdNoInit", 48,
350           [[6, 4, 5000, verySparseArray, 24],
351            [24, 2, 2000, verySparseArray, 48]],
352           verySparseArray, prod);
353
354testReduce("reduceRight", "VerySparseReduceRightDecNoInit", Infinity,
355           [[6, 4, 5000, verySparseArray, Infinity],
356            [Infinity, 2, 2000, verySparseArray, Infinity]],
357           verySparseArray, dec);
358
359testReduce("reduceRight", "SimpleSparseReduceRightAccumulateNoInit",
360           6,
361           [[6, 4, 5000, verySparseArray, 6],
362            [6, 2, 2000, verySparseArray, 6]],
363           verySparseArray, accumulate);
364
365
366// undefined is an element
367var undefArray = [,,undefined,,undefined,,];
368
369testReduce("reduce", "SparseUndefinedReduceAdd", NaN,
370           [[0, undefined, 2, undefArray, NaN],
371            [NaN, undefined, 4, undefArray, NaN],
372           ],
373           undefArray, sum, 0);
374
375testReduce("reduceRight", "SparseUndefinedReduceRightAdd", NaN,
376           [[0, undefined, 4, undefArray, NaN],
377            [NaN, undefined, 2, undefArray, NaN],
378           ], undefArray, sum, 0);
379
380testReduce("reduce", "SparseUndefinedReduceAddNoInit", NaN,
381           [[undefined, undefined, 4, undefArray, NaN],
382           ], undefArray, sum);
383
384testReduce("reduceRight", "SparseUndefinedReduceRightAddNoInit", NaN,
385           [[undefined, undefined, 2, undefArray, NaN],
386           ], undefArray, sum);
387
388
389// Ignore non-array properties:
390
391var arrayPlus = [1,2,,3];
392arrayPlus[-1] = NaN;
393arrayPlus[Math.pow(2,32)] = NaN;
394arrayPlus[NaN] = NaN;
395arrayPlus["00"] = NaN;
396arrayPlus["02"] = NaN;
397arrayPlus["-0"] = NaN;
398
399testReduce("reduce", "ArrayWithNonElementPropertiesReduce", 6,
400           [[0, 1, 0, arrayPlus, 1],
401            [1, 2, 1, arrayPlus, 3],
402            [3, 3, 3, arrayPlus, 6],
403           ], arrayPlus, sum, 0);
404
405testReduce("reduceRight", "ArrayWithNonElementPropertiesReduceRight", 6,
406           [[0, 3, 3, arrayPlus, 3],
407            [3, 2, 1, arrayPlus, 5],
408            [5, 1, 0, arrayPlus, 6],
409           ], arrayPlus, sum, 0);
410
411
412// Test error conditions:
413
414var exception = false;
415try {
416  [1].reduce("not a function");
417} catch (e) {
418  exception = true;
419  assertTrue(e instanceof TypeError,
420             "reduce callback not a function not throwing TypeError");
421  assertTrue(e.message.indexOf(" is not a function") >= 0,
422             "reduce non function TypeError type");
423}
424assertTrue(exception);
425
426exception = false;
427try {
428  [1].reduceRight("not a function");
429} catch (e) {
430  exception = true;
431  assertTrue(e instanceof TypeError,
432             "reduceRight callback not a function not throwing TypeError");
433  assertTrue(e.message.indexOf(" is not a function") >= 0,
434             "reduceRight non function TypeError type");
435}
436assertTrue(exception);
437
438exception = false;
439try {
440  [].reduce(sum);
441} catch (e) {
442  exception = true;
443  assertTrue(e instanceof TypeError,
444             "reduce no initial value not throwing TypeError");
445  assertEquals("Reduce of empty array with no initial value", e.message,
446               "reduce no initial TypeError type");
447}
448assertTrue(exception);
449
450exception = false;
451try {
452  [].reduceRight(sum);
453} catch (e) {
454  exception = true;
455  assertTrue(e instanceof TypeError,
456             "reduceRight no initial value not throwing TypeError");
457  assertEquals("Reduce of empty array with no initial value", e.message,
458               "reduceRight no initial TypeError type");
459}
460assertTrue(exception);
461
462exception = false;
463try {
464  [,,,].reduce(sum);
465} catch (e) {
466  exception = true;
467  assertTrue(e instanceof TypeError,
468             "reduce sparse no initial value not throwing TypeError");
469  assertEquals("Reduce of empty array with no initial value", e.message,
470               "reduce no initial TypeError type");
471}
472assertTrue(exception);
473
474exception = false;
475try {
476  [,,,].reduceRight(sum);
477} catch (e) {
478  exception = true;
479  assertTrue(e instanceof TypeError,
480             "reduceRight sparse no initial value not throwing TypeError");
481  assertEquals("Reduce of empty array with no initial value", e.message,
482               "reduceRight no initial TypeError type");
483}
484assertTrue(exception);
485
486
487// Array changing length
488
489function manipulator(a, b, i, s) {
490  if (s.length % 2) {
491    s[s.length * 3] = i;
492  } else {
493    s.length = s.length >> 1;
494  }
495  return a + b;
496}
497
498var arr = [1, 2, 3, 4];
499testReduce("reduce", "ArrayManipulationShort", 3,
500           [[0, 1, 0, [1, 2, 3, 4], 1],
501            [1, 2, 1, [1, 2], 3],
502           ], arr, manipulator, 0);
503
504var arr = [1, 2, 3, 4, 5];
505testReduce("reduce", "ArrayManipulationLonger", 10,
506           [[0, 1, 0, [1, 2, 3, 4, 5], 1],
507            [1, 2, 1, [1, 2, 3, 4, 5,,,,,,,,,,, 0], 3],
508            [3, 3, 2, [1, 2, 3, 4, 5,,,,], 6],
509            [6, 4, 3, [1, 2, 3, 4], 10],
510           ], arr, manipulator, 0);
511
512function extender(a, b, i, s) {
513  s[s.length] = s.length;
514  return a + b;
515}
516
517var arr = [1, 2, 3, 4];
518testReduce("reduce", "ArrayManipulationExtender", 10,
519           [[0, 1, 0, [1, 2, 3, 4], 1],
520            [1, 2, 1, [1, 2, 3, 4, 4], 3],
521            [3, 3, 2, [1, 2, 3, 4, 4, 5], 6],
522            [6, 4, 3, [1, 2, 3, 4, 4, 5, 6], 10],
523           ], arr, extender, 0);
524