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 32 function 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). 50 function 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 74 function 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 100 function sum(a, b) { return a + b; } 101 function prod(a, b) { return a * b; } 102 function dec(a, b, i, arr) { return a + b * Math.pow(10, arr.length - i - 1); } 103 function accumulate(acc, elem, i) { acc[i] = elem; return acc; } 104 105 // ---- Test Reduce[Left] 106 107 var simpleArray = [2,4,6] 108 109 testReduce("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 115 testReduce("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 121 testReduce("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 127 testReduce("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 134 testReduce("reduce", "EmptyReduceSum", 0, [], [], sum, 0); 135 testReduce("reduce", "EmptyReduceProd", 1, [], [], prod, 1); 136 testReduce("reduce", "EmptyReduceDec", 0, [], [], dec, 0); 137 testReduce("reduce", "EmptyReduceAccumulate", [], [], [], accumulate, []); 138 139 testReduce("reduce", "EmptyReduceSumNoInit", 0, [], [0], sum); 140 testReduce("reduce", "EmptyReduceProdNoInit", 1, [], [1], prod); 141 testReduce("reduce", "EmptyReduceDecNoInit", 0, [], [0], dec); 142 testReduce("reduce", "EmptyReduceAccumulateNoInit", [], [], [[]], accumulate); 143 144 145 var simpleSparseArray = [,,,2,,4,,6,,]; 146 testReduce("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 152 testReduce("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 158 testReduce("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 164 testReduce("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 171 testReduce("reduce", "EmptySparseReduceSumNoInit", 0, [], [,,0,,], sum); 172 testReduce("reduce", "EmptySparseReduceProdNoInit", 1, [], [,,1,,], prod); 173 testReduce("reduce", "EmptySparseReduceDecNoInit", 0, [], [,,0,,], dec); 174 testReduce("reduce", "EmptySparseReduceAccumulateNoInit", 175 [], [], [,,[],,], accumulate); 176 177 178 var verySparseArray = []; 179 verySparseArray.length = 10000; 180 verySparseArray[2000] = 2; 181 verySparseArray[5000] = 4; 182 verySparseArray[9000] = 6; 183 var verySparseSlice2 = verySparseArray.slice(0, 2001); 184 var verySparseSlice4 = verySparseArray.slice(0, 5001); 185 var verySparseSlice6 = verySparseArray.slice(0, 9001); 186 187 testReduce("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 193 testReduce("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 199 testReduce("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 205 testReduce("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 213 testReduce("reduce", "VerySparseReduceSumNoInit", 12, 214 [[2, 4, 5000, verySparseArray, 6], 215 [6, 6, 9000, verySparseArray, 12]], 216 verySparseArray, sum); 217 218 testReduce("reduce", "VerySparseReduceProdNoInit", 48, 219 [[2, 4, 5000, verySparseArray, 8], 220 [8, 6, 9000, verySparseArray, 48]], 221 verySparseArray, prod); 222 223 testReduce("reduce", "VerySparseReduceDecNoInit", Infinity, 224 [[2, 4, 5000, verySparseArray, Infinity], 225 [Infinity, 6, 9000, verySparseArray, Infinity]], 226 verySparseArray, dec); 227 228 testReduce("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 237 testReduce("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 243 testReduce("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 249 testReduce("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 255 testReduce("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 262 testReduce("reduceRight", "EmptyReduceRightSum", 0, [], [], sum, 0); 263 testReduce("reduceRight", "EmptyReduceRightProd", 1, [], [], prod, 1); 264 testReduce("reduceRight", "EmptyReduceRightDec", 0, [], [], dec, 0); 265 testReduce("reduceRight", "EmptyReduceRightAccumulate", [], 266 [], [], accumulate, []); 267 268 testReduce("reduceRight", "EmptyReduceRightSumNoInit", 0, [], [0], sum); 269 testReduce("reduceRight", "EmptyReduceRightProdNoInit", 1, [], [1], prod); 270 testReduce("reduceRight", "EmptyReduceRightDecNoInit", 0, [], [0], dec); 271 testReduce("reduceRight", "EmptyReduceRightAccumulateNoInit", 272 [], [], [[]], accumulate); 273 274 275 testReduce("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 281 testReduce("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 287 testReduce("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 293 testReduce("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 300 testReduce("reduceRight", "EmptySparseReduceRightSumNoInit", 301 0, [], [,,0,,], sum); 302 testReduce("reduceRight", "EmptySparseReduceRightProdNoInit", 303 1, [], [,,1,,], prod); 304 testReduce("reduceRight", "EmptySparseReduceRightDecNoInit", 305 0, [], [,,0,,], dec); 306 testReduce("reduceRight", "EmptySparseReduceRightAccumulateNoInit", 307 [], [], [,,[],,], accumulate); 308 309 310 var verySparseSuffix6 = []; 311 verySparseSuffix6[9000] = 6; 312 var verySparseSuffix4 = []; 313 verySparseSuffix4[5000] = 4; 314 verySparseSuffix4[9000] = 6; 315 var verySparseSuffix2 = verySparseSlice6; 316 317 318 testReduce("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 324 testReduce("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 330 testReduce("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 336 testReduce("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 344 testReduce("reduceRight", "VerySparseReduceRightSumNoInit", 12, 345 [[6, 4, 5000, verySparseArray, 10], 346 [10, 2, 2000, verySparseArray, 12]], 347 verySparseArray, sum); 348 349 testReduce("reduceRight", "VerySparseReduceRightProdNoInit", 48, 350 [[6, 4, 5000, verySparseArray, 24], 351 [24, 2, 2000, verySparseArray, 48]], 352 verySparseArray, prod); 353 354 testReduce("reduceRight", "VerySparseReduceRightDecNoInit", Infinity, 355 [[6, 4, 5000, verySparseArray, Infinity], 356 [Infinity, 2, 2000, verySparseArray, Infinity]], 357 verySparseArray, dec); 358 359 testReduce("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 367 var undefArray = [,,undefined,,undefined,,]; 368 369 testReduce("reduce", "SparseUndefinedReduceAdd", NaN, 370 [[0, undefined, 2, undefArray, NaN], 371 [NaN, undefined, 4, undefArray, NaN], 372 ], 373 undefArray, sum, 0); 374 375 testReduce("reduceRight", "SparseUndefinedReduceRightAdd", NaN, 376 [[0, undefined, 4, undefArray, NaN], 377 [NaN, undefined, 2, undefArray, NaN], 378 ], undefArray, sum, 0); 379 380 testReduce("reduce", "SparseUndefinedReduceAddNoInit", NaN, 381 [[undefined, undefined, 4, undefArray, NaN], 382 ], undefArray, sum); 383 384 testReduce("reduceRight", "SparseUndefinedReduceRightAddNoInit", NaN, 385 [[undefined, undefined, 2, undefArray, NaN], 386 ], undefArray, sum); 387 388 389 // Ignore non-array properties: 390 391 var arrayPlus = [1,2,,3]; 392 arrayPlus[-1] = NaN; 393 arrayPlus[Math.pow(2,32)] = NaN; 394 arrayPlus[NaN] = NaN; 395 arrayPlus["00"] = NaN; 396 arrayPlus["02"] = NaN; 397 arrayPlus["-0"] = NaN; 398 399 testReduce("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 405 testReduce("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 414 var exception = false; 415 try { 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 } 424 assertTrue(exception); 425 426 exception = false; 427 try { 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 } 436 assertTrue(exception); 437 438 exception = false; 439 try { 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 } 448 assertTrue(exception); 449 450 exception = false; 451 try { 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 } 460 assertTrue(exception); 461 462 exception = false; 463 try { 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 } 472 assertTrue(exception); 473 474 exception = false; 475 try { 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 } 484 assertTrue(exception); 485 486 487 // Array changing length 488 489 function 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 498 var arr = [1, 2, 3, 4]; 499 testReduce("reduce", "ArrayManipulationShort", 3, 500 [[0, 1, 0, [1, 2, 3, 4], 1], 501 [1, 2, 1, [1, 2], 3], 502 ], arr, manipulator, 0); 503 504 var arr = [1, 2, 3, 4, 5]; 505 testReduce("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 512 function extender(a, b, i, s) { 513 s[s.length] = s.length; 514 return a + b; 515 } 516 517 var arr = [1, 2, 3, 4]; 518 testReduce("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
