js/src/builtin/Array.js@b8a032363ba2
js/src/builtin/Array.js
Thu, 22 Jan 2015 13:21:57 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Thu, 22 Jan 2015 13:21:57 +0100
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
- permissions
- -rw-r--r--
Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6
1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 /* ES5 15.4.4.14. */
6 function ArrayIndexOf(searchElement/*, fromIndex*/) {
7 /* Step 1. */
8 var O = ToObject(this);
10 /* Steps 2-3. */
11 var len = TO_UINT32(O.length);
13 /* Step 4. */
14 if (len === 0)
15 return -1;
17 /* Step 5. */
18 var n = arguments.length > 1 ? ToInteger(arguments[1]) : 0;
20 /* Step 6. */
21 if (n >= len)
22 return -1;
24 var k;
25 /* Step 7. */
26 if (n >= 0)
27 k = n;
28 /* Step 8. */
29 else {
30 /* Step a. */
31 k = len + n;
32 /* Step b. */
33 if (k < 0)
34 k = 0;
35 }
37 /* Step 9. */
38 if (IsPackedArray(O)) {
39 for (; k < len; k++) {
40 if (O[k] === searchElement)
41 return k;
42 }
43 } else {
44 for (; k < len; k++) {
45 if (k in O && O[k] === searchElement)
46 return k;
47 }
48 }
50 /* Step 10. */
51 return -1;
52 }
54 function ArrayStaticIndexOf(list, searchElement/*, fromIndex*/) {
55 if (arguments.length < 1)
56 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.indexOf');
57 var fromIndex = arguments.length > 2 ? arguments[2] : 0;
58 return callFunction(ArrayIndexOf, list, searchElement, fromIndex);
59 }
61 /* ES5 15.4.4.15. */
62 function ArrayLastIndexOf(searchElement/*, fromIndex*/) {
63 /* Step 1. */
64 var O = ToObject(this);
66 /* Steps 2-3. */
67 var len = TO_UINT32(O.length);
69 /* Step 4. */
70 if (len === 0)
71 return -1;
73 /* Step 5. */
74 var n = arguments.length > 1 ? ToInteger(arguments[1]) : len - 1;
76 /* Steps 6-7. */
77 var k;
78 if (n > len - 1)
79 k = len - 1;
80 else if (n < 0)
81 k = len + n;
82 else
83 k = n;
85 /* Step 8. */
86 if (IsPackedArray(O)) {
87 for (; k >= 0; k--) {
88 if (O[k] === searchElement)
89 return k;
90 }
91 } else {
92 for (; k >= 0; k--) {
93 if (k in O && O[k] === searchElement)
94 return k;
95 }
96 }
98 /* Step 9. */
99 return -1;
100 }
102 function ArrayStaticLastIndexOf(list, searchElement/*, fromIndex*/) {
103 if (arguments.length < 1)
104 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.lastIndexOf');
105 var fromIndex;
106 if (arguments.length > 2) {
107 fromIndex = arguments[2];
108 } else {
109 var O = ToObject(list);
110 var len = TO_UINT32(O.length);
111 fromIndex = len - 1;
112 }
113 return callFunction(ArrayLastIndexOf, list, searchElement, fromIndex);
114 }
116 /* ES5 15.4.4.16. */
117 function ArrayEvery(callbackfn/*, thisArg*/) {
118 /* Step 1. */
119 var O = ToObject(this);
121 /* Steps 2-3. */
122 var len = TO_UINT32(O.length);
124 /* Step 4. */
125 if (arguments.length === 0)
126 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.prototype.every');
127 if (!IsCallable(callbackfn))
128 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, callbackfn));
130 /* Step 5. */
131 var T = arguments.length > 1 ? arguments[1] : void 0;
133 /* Steps 6-7. */
134 /* Steps a (implicit), and d. */
135 for (var k = 0; k < len; k++) {
136 /* Step b */
137 if (k in O) {
138 /* Step c. */
139 if (!callFunction(callbackfn, T, O[k], k, O))
140 return false;
141 }
142 }
144 /* Step 8. */
145 return true;
146 }
148 function ArrayStaticEvery(list, callbackfn/*, thisArg*/) {
149 if (arguments.length < 2)
150 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.every');
151 if (!IsCallable(callbackfn))
152 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(1, callbackfn));
153 var T = arguments.length > 2 ? arguments[2] : void 0;
154 return callFunction(ArrayEvery, list, callbackfn, T);
155 }
157 /* ES5 15.4.4.17. */
158 function ArraySome(callbackfn/*, thisArg*/) {
159 /* Step 1. */
160 var O = ToObject(this);
162 /* Steps 2-3. */
163 var len = TO_UINT32(O.length);
165 /* Step 4. */
166 if (arguments.length === 0)
167 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.prototype.some');
168 if (!IsCallable(callbackfn))
169 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, callbackfn));
171 /* Step 5. */
172 var T = arguments.length > 1 ? arguments[1] : void 0;
174 /* Steps 6-7. */
175 /* Steps a (implicit), and d. */
176 for (var k = 0; k < len; k++) {
177 /* Step b */
178 if (k in O) {
179 /* Step c. */
180 if (callFunction(callbackfn, T, O[k], k, O))
181 return true;
182 }
183 }
185 /* Step 8. */
186 return false;
187 }
189 function ArrayStaticSome(list, callbackfn/*, thisArg*/) {
190 if (arguments.length < 2)
191 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.some');
192 if (!IsCallable(callbackfn))
193 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(1, callbackfn));
194 var T = arguments.length > 2 ? arguments[2] : void 0;
195 return callFunction(ArraySome, list, callbackfn, T);
196 }
198 /* ES5 15.4.4.18. */
199 function ArrayForEach(callbackfn/*, thisArg*/) {
200 /* Step 1. */
201 var O = ToObject(this);
203 /* Steps 2-3. */
204 var len = TO_UINT32(O.length);
206 /* Step 4. */
207 if (arguments.length === 0)
208 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.prototype.forEach');
209 if (!IsCallable(callbackfn))
210 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, callbackfn));
212 /* Step 5. */
213 var T = arguments.length > 1 ? arguments[1] : void 0;
215 /* Steps 6-7. */
216 /* Steps a (implicit), and d. */
217 for (var k = 0; k < len; k++) {
218 /* Step b */
219 if (k in O) {
220 /* Step c. */
221 callFunction(callbackfn, T, O[k], k, O);
222 }
223 }
225 /* Step 8. */
226 return void 0;
227 }
229 /* ES5 15.4.4.19. */
230 function ArrayMap(callbackfn/*, thisArg*/) {
231 /* Step 1. */
232 var O = ToObject(this);
234 /* Step 2-3. */
235 var len = TO_UINT32(O.length);
237 /* Step 4. */
238 if (arguments.length === 0)
239 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.prototype.map');
240 if (!IsCallable(callbackfn))
241 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, callbackfn));
243 /* Step 5. */
244 var T = arguments.length > 1 ? arguments[1] : void 0;
246 /* Step 6. */
247 var A = NewDenseArray(len);
249 /* Step 7-8. */
250 /* Step a (implicit), and d. */
251 for (var k = 0; k < len; k++) {
252 /* Step b */
253 if (k in O) {
254 /* Step c.i-iii. */
255 var mappedValue = callFunction(callbackfn, T, O[k], k, O);
256 // UnsafePutElements doesn't invoke setters, so we can use it here.
257 UnsafePutElements(A, k, mappedValue);
258 }
259 }
261 /* Step 9. */
262 return A;
263 }
265 function ArrayStaticMap(list, callbackfn/*, thisArg*/) {
266 if (arguments.length < 2)
267 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.map');
268 if (!IsCallable(callbackfn))
269 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(1, callbackfn));
270 var T = arguments.length > 2 ? arguments[2] : void 0;
271 return callFunction(ArrayMap, list, callbackfn, T);
272 }
274 function ArrayStaticForEach(list, callbackfn/*, thisArg*/) {
275 if (arguments.length < 2)
276 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.forEach');
277 if (!IsCallable(callbackfn))
278 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(1, callbackfn));
279 var T = arguments.length > 2 ? arguments[2] : void 0;
280 callFunction(ArrayForEach, list, callbackfn, T);
281 }
283 /* ES5 15.4.4.21. */
284 function ArrayReduce(callbackfn/*, initialValue*/) {
285 /* Step 1. */
286 var O = ToObject(this);
288 /* Steps 2-3. */
289 var len = TO_UINT32(O.length);
291 /* Step 4. */
292 if (arguments.length === 0)
293 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.prototype.reduce');
294 if (!IsCallable(callbackfn))
295 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, callbackfn));
297 /* Step 6. */
298 var k = 0;
300 /* Steps 5, 7-8. */
301 var accumulator;
302 if (arguments.length > 1) {
303 accumulator = arguments[1];
304 } else {
305 /* Step 5. */
306 if (len === 0)
307 ThrowError(JSMSG_EMPTY_ARRAY_REDUCE);
308 if (IsPackedArray(O)) {
309 accumulator = O[k++];
310 } else {
311 var kPresent = false;
312 for (; k < len; k++) {
313 if (k in O) {
314 accumulator = O[k];
315 kPresent = true;
316 k++;
317 break;
318 }
319 }
320 if (!kPresent)
321 ThrowError(JSMSG_EMPTY_ARRAY_REDUCE);
322 }
323 }
325 /* Step 9. */
326 /* Steps a (implicit), and d. */
327 for (; k < len; k++) {
328 /* Step b */
329 if (k in O) {
330 /* Step c. */
331 accumulator = callbackfn(accumulator, O[k], k, O);
332 }
333 }
335 /* Step 10. */
336 return accumulator;
337 }
339 function ArrayStaticReduce(list, callbackfn) {
340 if (arguments.length < 2)
341 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.reduce');
342 if (!IsCallable(callbackfn))
343 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(1, callbackfn));
344 if (arguments.length > 2)
345 return callFunction(ArrayReduce, list, callbackfn, arguments[2]);
346 else
347 return callFunction(ArrayReduce, list, callbackfn);
348 }
350 /* ES5 15.4.4.22. */
351 function ArrayReduceRight(callbackfn/*, initialValue*/) {
352 /* Step 1. */
353 var O = ToObject(this);
355 /* Steps 2-3. */
356 var len = TO_UINT32(O.length);
358 /* Step 4. */
359 if (arguments.length === 0)
360 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.prototype.reduce');
361 if (!IsCallable(callbackfn))
362 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, callbackfn));
364 /* Step 6. */
365 var k = len - 1;
367 /* Steps 5, 7-8. */
368 var accumulator;
369 if (arguments.length > 1) {
370 accumulator = arguments[1];
371 } else {
372 /* Step 5. */
373 if (len === 0)
374 ThrowError(JSMSG_EMPTY_ARRAY_REDUCE);
375 if (IsPackedArray(O)) {
376 accumulator = O[k--];
377 } else {
378 var kPresent = false;
379 for (; k >= 0; k--) {
380 if (k in O) {
381 accumulator = O[k];
382 kPresent = true;
383 k--;
384 break;
385 }
386 }
387 if (!kPresent)
388 ThrowError(JSMSG_EMPTY_ARRAY_REDUCE);
389 }
390 }
392 /* Step 9. */
393 /* Steps a (implicit), and d. */
394 for (; k >= 0; k--) {
395 /* Step b */
396 if (k in O) {
397 /* Step c. */
398 accumulator = callbackfn(accumulator, O[k], k, O);
399 }
400 }
402 /* Step 10. */
403 return accumulator;
404 }
406 function ArrayStaticReduceRight(list, callbackfn) {
407 if (arguments.length < 2)
408 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.reduceRight');
409 if (!IsCallable(callbackfn))
410 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(1, callbackfn));
411 if (arguments.length > 2)
412 return callFunction(ArrayReduceRight, list, callbackfn, arguments[2]);
413 else
414 return callFunction(ArrayReduceRight, list, callbackfn);
415 }
417 /* ES6 draft 2013-05-14 15.4.3.23. */
418 function ArrayFind(predicate/*, thisArg*/) {
419 /* Steps 1-2. */
420 var O = ToObject(this);
422 /* Steps 3-5. */
423 var len = ToInteger(O.length);
425 /* Step 6. */
426 if (arguments.length === 0)
427 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.prototype.find');
428 if (!IsCallable(predicate))
429 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, predicate));
431 /* Step 7. */
432 var T = arguments.length > 1 ? arguments[1] : undefined;
434 /* Steps 8-9. */
435 /* Steps a (implicit), and e. */
436 /* Note: this will hang in some corner-case situations, because of IEEE-754 numbers'
437 * imprecision for large values. Example:
438 * var obj = { 18014398509481984: true, length: 18014398509481988 };
439 * Array.prototype.find.call(obj, () => true);
440 */
441 for (var k = 0; k < len; k++) {
442 /* Steps b and c (implicit) */
443 if (k in O) {
444 /* Step d. */
445 var kValue = O[k];
446 if (callFunction(predicate, T, kValue, k, O))
447 return kValue;
448 }
449 }
451 /* Step 10. */
452 return undefined;
453 }
455 /* ES6 draft 2013-05-14 15.4.3.23. */
456 function ArrayFindIndex(predicate/*, thisArg*/) {
457 /* Steps 1-2. */
458 var O = ToObject(this);
460 /* Steps 3-5. */
461 var len = ToInteger(O.length);
463 /* Step 6. */
464 if (arguments.length === 0)
465 ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.prototype.find');
466 if (!IsCallable(predicate))
467 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, predicate));
469 /* Step 7. */
470 var T = arguments.length > 1 ? arguments[1] : undefined;
472 /* Steps 8-9. */
473 /* Steps a (implicit), and e. */
474 /* Note: this will hang in some corner-case situations, because of IEEE-754 numbers'
475 * imprecision for large values. Example:
476 * var obj = { 18014398509481984: true, length: 18014398509481988 };
477 * Array.prototype.find.call(obj, () => true);
478 */
479 for (var k = 0; k < len; k++) {
480 /* Steps b and c (implicit) */
481 if (k in O) {
482 /* Step d. */
483 if (callFunction(predicate, T, O[k], k, O))
484 return k;
485 }
486 }
488 /* Step 10. */
489 return -1;
490 }
492 // ES6 draft 2014-04-05 22.1.3.6
493 function ArrayFill(value, start = 0, end = undefined) {
494 // Steps 1-2.
495 var O = ToObject(this);
497 // Steps 3-5.
498 // FIXME: Array operations should use ToLength (bug 924058).
499 var len = ToInteger(O.length);
501 // Steps 6-7.
502 var relativeStart = ToInteger(start);
504 // Step 8.
505 var k = relativeStart < 0
506 ? std_Math_max(len + relativeStart, 0)
507 : std_Math_min(relativeStart, len);
509 // Steps 9-10.
510 var relativeEnd = end === undefined ? len : ToInteger(end);
512 // Step 11.
513 var final = relativeEnd < 0
514 ? std_Math_max(len + relativeEnd, 0)
515 : std_Math_min(relativeEnd, len);
517 // Step 12.
518 for (; k < final; k++) {
519 O[k] = value;
520 }
522 // Step 13.
523 return O;
524 }
526 #define ARRAY_ITERATOR_SLOT_ITERATED_OBJECT 0
527 #define ARRAY_ITERATOR_SLOT_NEXT_INDEX 1
528 #define ARRAY_ITERATOR_SLOT_ITEM_KIND 2
530 #define ITEM_KIND_VALUE 0
531 #define ITEM_KIND_KEY_AND_VALUE 1
532 #define ITEM_KIND_KEY 2
534 // ES6 draft specification, section 22.1.5.1, version 2013-09-05.
535 function CreateArrayIteratorAt(obj, kind, n) {
536 var iteratedObject = ToObject(obj);
537 var iterator = NewArrayIterator();
538 UnsafeSetReservedSlot(iterator, ARRAY_ITERATOR_SLOT_ITERATED_OBJECT, iteratedObject);
539 UnsafeSetReservedSlot(iterator, ARRAY_ITERATOR_SLOT_NEXT_INDEX, n);
540 UnsafeSetReservedSlot(iterator, ARRAY_ITERATOR_SLOT_ITEM_KIND, kind);
541 return iterator;
542 }
543 function CreateArrayIterator(obj, kind) {
544 return CreateArrayIteratorAt(obj, kind, 0);
545 }
547 function ArrayIteratorIdentity() {
548 return this;
549 }
551 function ArrayIteratorNext() {
552 // FIXME: ArrayIterator prototype should not pass this test. Bug 924059.
553 if (!IsObject(this) || !IsArrayIterator(this))
554 ThrowError(JSMSG_INCOMPATIBLE_METHOD, "ArrayIterator", "next", ToString(this));
556 var a = UnsafeGetReservedSlot(this, ARRAY_ITERATOR_SLOT_ITERATED_OBJECT);
557 var index = UnsafeGetReservedSlot(this, ARRAY_ITERATOR_SLOT_NEXT_INDEX);
558 var itemKind = UnsafeGetReservedSlot(this, ARRAY_ITERATOR_SLOT_ITEM_KIND);
560 // FIXME: This should be ToLength, which clamps at 2**53. Bug 924058.
561 if (index >= TO_UINT32(a.length)) {
562 // When the above is changed to ToLength, use +1/0 here instead
563 // of MAX_UINT32.
564 UnsafeSetReservedSlot(this, ARRAY_ITERATOR_SLOT_NEXT_INDEX, 0xffffffff);
565 return { value: undefined, done: true };
566 }
568 UnsafeSetReservedSlot(this, ARRAY_ITERATOR_SLOT_NEXT_INDEX, index + 1);
570 if (itemKind === ITEM_KIND_VALUE)
571 return { value: a[index], done: false };
573 if (itemKind === ITEM_KIND_KEY_AND_VALUE) {
574 var pair = NewDenseArray(2);
575 pair[0] = index;
576 pair[1] = a[index];
577 return { value: pair, done : false };
578 }
580 assert(itemKind === ITEM_KIND_KEY, itemKind);
581 return { value: index, done: false };
582 }
584 function ArrayValuesAt(n) {
585 return CreateArrayIteratorAt(this, ITEM_KIND_VALUE, n);
586 }
588 function ArrayValues() {
589 return CreateArrayIterator(this, ITEM_KIND_VALUE);
590 }
592 function ArrayEntries() {
593 return CreateArrayIterator(this, ITEM_KIND_KEY_AND_VALUE);
594 }
596 function ArrayKeys() {
597 return CreateArrayIterator(this, ITEM_KIND_KEY);
598 }
600 #ifdef ENABLE_PARALLEL_JS
602 /*
603 * Strawman spec:
604 * http://wiki.ecmascript.org/doku.php?id=strawman:data_parallelism
605 */
607 /**
608 * Creates a new array by applying |func(e, i, self)| for each element |e|
609 * with index |i|.
610 */
611 function ArrayMapPar(func, mode) {
612 if (!IsCallable(func))
613 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, func));
615 var self = ToObject(this);
616 var length = self.length;
617 var buffer = NewDenseArray(length);
619 parallel: for (;;) {
620 // Avoid parallel compilation if we are already nested in another
621 // parallel section or the user told us not to parallelize. The
622 // use of a for (;;) loop is working around some ion limitations:
623 //
624 // - Breaking out of named blocks does not currently work (bug 684384);
625 // - Unreachable Code Elim. can't properly handle if (a && b) (bug 669796)
626 if (ShouldForceSequential())
627 break parallel;
628 if (!TRY_PARALLEL(mode))
629 break parallel;
631 var slicesInfo = ComputeSlicesInfo(length);
632 ForkJoin(mapThread, 0, slicesInfo.count, ForkJoinMode(mode));
633 return buffer;
634 }
636 // Sequential fallback:
637 ASSERT_SEQUENTIAL_IS_OK(mode);
638 for (var i = 0; i < length; i++)
639 UnsafePutElements(buffer, i, func(self[i], i, self));
640 return buffer;
642 function mapThread(workerId, sliceStart, sliceEnd) {
643 var sliceShift = slicesInfo.shift;
644 var sliceId;
645 while (GET_SLICE(sliceStart, sliceEnd, sliceId)) {
646 var indexStart = SLICE_START_INDEX(sliceShift, sliceId);
647 var indexEnd = SLICE_END_INDEX(sliceShift, indexStart, length);
648 for (var i = indexStart; i < indexEnd; i++)
649 UnsafePutElements(buffer, i, func(self[i], i, self));
650 }
651 return sliceId;
652 }
654 return undefined;
655 }
657 /**
658 * Reduces the elements in an array in parallel. Order is not fixed and |func|
659 * is assumed to be associative.
660 */
661 function ArrayReducePar(func, mode) {
662 if (!IsCallable(func))
663 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, func));
665 var self = ToObject(this);
666 var length = self.length;
668 if (length === 0)
669 ThrowError(JSMSG_EMPTY_ARRAY_REDUCE);
671 parallel: for (;;) { // see ArrayMapPar() to explain why for(;;) etc
672 if (ShouldForceSequential())
673 break parallel;
674 if (!TRY_PARALLEL(mode))
675 break parallel;
677 var slicesInfo = ComputeSlicesInfo(length);
678 var numSlices = slicesInfo.count;
679 var subreductions = NewDenseArray(numSlices);
681 ForkJoin(reduceThread, 0, numSlices, ForkJoinMode(mode));
683 var accumulator = subreductions[0];
684 for (var i = 1; i < numSlices; i++)
685 accumulator = func(accumulator, subreductions[i]);
686 return accumulator;
687 }
689 // Sequential fallback:
690 ASSERT_SEQUENTIAL_IS_OK(mode);
691 var accumulator = self[0];
692 for (var i = 1; i < length; i++)
693 accumulator = func(accumulator, self[i]);
694 return accumulator;
696 function reduceThread(workerId, sliceStart, sliceEnd) {
697 var sliceShift = slicesInfo.shift;
698 var sliceId;
699 while (GET_SLICE(sliceStart, sliceEnd, sliceId)) {
700 var indexStart = SLICE_START_INDEX(sliceShift, sliceId);
701 var indexEnd = SLICE_END_INDEX(sliceShift, indexStart, length);
702 var accumulator = self[indexStart];
703 for (var i = indexStart + 1; i < indexEnd; i++)
704 accumulator = func(accumulator, self[i]);
705 UnsafePutElements(subreductions, sliceId, accumulator);
706 }
707 return sliceId;
708 }
710 return undefined;
711 }
713 /**
714 * Returns an array [s_0, ..., s_N] where |s_i| is equal to the reduction (as
715 * per |reduce()|) of elements |0..i|. This is the generalization of partial
716 * sum.
717 */
718 function ArrayScanPar(func, mode) {
719 if (!IsCallable(func))
720 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, func));
722 var self = ToObject(this);
723 var length = self.length;
725 if (length === 0)
726 ThrowError(JSMSG_EMPTY_ARRAY_REDUCE);
728 var buffer = NewDenseArray(length);
730 parallel: for (;;) { // see ArrayMapPar() to explain why for(;;) etc
731 if (ShouldForceSequential())
732 break parallel;
733 if (!TRY_PARALLEL(mode))
734 break parallel;
736 var slicesInfo = ComputeSlicesInfo(length);
737 var numSlices = slicesInfo.count;
739 // Scan slices individually (see comment on phase1()).
740 ForkJoin(phase1, 0, numSlices, ForkJoinMode(mode));
742 // Compute intermediates array (see comment on phase2()).
743 var intermediates = [];
744 var accumulator = buffer[finalElement(0)];
745 ARRAY_PUSH(intermediates, accumulator);
746 for (var i = 1; i < numSlices - 1; i++) {
747 accumulator = func(accumulator, buffer[finalElement(i)]);
748 ARRAY_PUSH(intermediates, accumulator);
749 }
751 // Complete each slice using intermediates array (see comment on phase2()).
752 //
753 // We start from slice 1 instead of 0 since there is no work to be done
754 // for slice 0.
755 if (numSlices > 1)
756 ForkJoin(phase2, 1, numSlices, ForkJoinMode(mode));
757 return buffer;
758 }
760 // Sequential fallback:
761 ASSERT_SEQUENTIAL_IS_OK(mode);
762 scan(self[0], 0, length);
763 return buffer;
765 function scan(accumulator, start, end) {
766 UnsafePutElements(buffer, start, accumulator);
767 for (var i = start + 1; i < end; i++) {
768 accumulator = func(accumulator, self[i]);
769 UnsafePutElements(buffer, i, accumulator);
770 }
771 return accumulator;
772 }
774 /**
775 * In phase 1, we divide the source array into |numSlices| slices and
776 * compute scan on each slice sequentially as if it were the entire
777 * array. This function is responsible for computing one of those
778 * slices.
779 *
780 * So, if we have an array [A,B,C,D,E,F,G,H,I], |numSlices === 3|,
781 * and our function |func| is sum, then we would wind up computing a
782 * result array like:
783 *
784 * [A, A+B, A+B+C, D, D+E, D+E+F, G, G+H, G+H+I]
785 * ^~~~~~~~~~~~^ ^~~~~~~~~~~~^ ^~~~~~~~~~~~~^
786 * Slice 0 Slice 1 Slice 2
787 *
788 * Read on in phase2 to see what we do next!
789 */
790 function phase1(workerId, sliceStart, sliceEnd) {
791 var sliceShift = slicesInfo.shift;
792 var sliceId;
793 while (GET_SLICE(sliceStart, sliceEnd, sliceId)) {
794 var indexStart = SLICE_START_INDEX(sliceShift, sliceId);
795 var indexEnd = SLICE_END_INDEX(sliceShift, indexStart, length);
796 scan(self[indexStart], indexStart, indexEnd);
797 }
798 return sliceId;
799 }
801 /**
802 * Computes the index of the final element computed by the slice |sliceId|.
803 */
804 function finalElement(sliceId) {
805 var sliceShift = slicesInfo.shift;
806 return SLICE_END_INDEX(sliceShift, SLICE_START_INDEX(sliceShift, sliceId), length) - 1;
807 }
809 /**
810 * After computing the phase1 results, we compute an
811 * |intermediates| array. |intermediates[i]| contains the result
812 * of reducing the final value from each preceding slice j<i with
813 * the final value of slice i. So, to continue our previous
814 * example, the intermediates array would contain:
815 *
816 * [A+B+C, (A+B+C)+(D+E+F), ((A+B+C)+(D+E+F))+(G+H+I)]
817 *
818 * Here I have used parenthesization to make clear the order of
819 * evaluation in each case.
820 *
821 * An aside: currently the intermediates array is computed
822 * sequentially. In principle, we could compute it in parallel,
823 * at the cost of doing duplicate work. This did not seem
824 * particularly advantageous to me, particularly as the number
825 * of slices is typically quite small (one per core), so I opted
826 * to just compute it sequentially.
827 *
828 * Phase 2 combines the results of phase1 with the intermediates
829 * array to produce the final scan results. The idea is to
830 * reiterate over each element S[i] in the slice |sliceId|, which
831 * currently contains the result of reducing with S[0]...S[i]
832 * (where S0 is the first thing in the slice), and combine that
833 * with |intermediate[sliceId-1]|, which represents the result of
834 * reducing everything in the input array prior to the slice.
835 *
836 * To continue with our example, in phase 1 we computed slice 1 to
837 * be [D, D+E, D+E+F]. We will combine those results with
838 * |intermediates[1-1]|, which is |A+B+C|, so that the final
839 * result is [(A+B+C)+D, (A+B+C)+(D+E), (A+B+C)+(D+E+F)]. Again I
840 * am using parentheses to clarify how these results were reduced.
841 */
842 function phase2(workerId, sliceStart, sliceEnd) {
843 var sliceShift = slicesInfo.shift;
844 var sliceId;
845 while (GET_SLICE(sliceStart, sliceEnd, sliceId)) {
846 var indexPos = SLICE_START_INDEX(sliceShift, sliceId);
847 var indexEnd = SLICE_END_INDEX(sliceShift, indexPos, length);
848 var intermediate = intermediates[sliceId - 1];
849 for (; indexPos < indexEnd; indexPos++)
850 UnsafePutElements(buffer, indexPos, func(intermediate, buffer[indexPos]));
851 }
852 return sliceId;
853 }
855 return undefined;
856 }
858 /**
859 * |scatter()| redistributes the elements in the array into a new array.
860 *
861 * - targets: The index targets[i] indicates where the ith element
862 * should appear in the result.
863 *
864 * - defaultValue: what value to use for indices in the output array that
865 * are never targeted.
866 *
867 * - conflictFunc: The conflict function. Used to resolve what
868 * happens if two indices i and j in the source array are targeted
869 * as the same destination (i.e., targets[i] === targets[j]), then
870 * the final result is determined by applying func(targets[i],
871 * targets[j]). If no conflict function is provided, it is an error
872 * if targets[i] === targets[j].
873 *
874 * - length: length of the output array (if not specified, uses the
875 * length of the input).
876 *
877 * - mode: internal debugging specification.
878 */
879 function ArrayScatterPar(targets, defaultValue, conflictFunc, length, mode) {
880 if (conflictFunc && !IsCallable(conflictFunc))
881 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(2, conflictFunc));
883 var self = ToObject(this);
885 if (length === undefined)
886 length = self.length;
888 var targetsLength = std_Math_min(targets.length, self.length);
890 if (!IS_UINT32(targetsLength) || !IS_UINT32(length))
891 ThrowError(JSMSG_BAD_ARRAY_LENGTH);
893 // FIXME: Bug 965609: Find a better parallel startegy for scatter.
895 // Sequential fallback:
896 ASSERT_SEQUENTIAL_IS_OK(mode);
897 return seq();
899 function seq() {
900 var buffer = NewDenseArray(length);
901 var conflicts = NewDenseArray(length);
903 for (var i = 0; i < length; i++) {
904 UnsafePutElements(buffer, i, defaultValue);
905 UnsafePutElements(conflicts, i, false);
906 }
908 for (var i = 0; i < targetsLength; i++) {
909 var x = self[i];
910 var t = checkTarget(i, targets[i]);
911 if (conflicts[t])
912 x = collide(x, buffer[t]);
914 UnsafePutElements(buffer, t, x, conflicts, t, true);
915 }
917 return buffer;
918 }
920 function collide(elem1, elem2) {
921 if (conflictFunc === undefined)
922 ThrowError(JSMSG_PAR_ARRAY_SCATTER_CONFLICT);
924 return conflictFunc(elem1, elem2);
925 }
927 function checkTarget(i, t) {
928 if (TO_INT32(t) !== t)
929 ThrowError(JSMSG_PAR_ARRAY_SCATTER_BAD_TARGET, i);
931 if (t < 0 || t >= length)
932 ThrowError(JSMSG_PAR_ARRAY_SCATTER_BOUNDS);
934 // It's not enough to return t, as -0 | 0 === -0.
935 return TO_INT32(t);
936 }
938 return undefined;
939 }
941 /**
942 * The filter operation applied in parallel.
943 */
944 function ArrayFilterPar(func, mode) {
945 if (!IsCallable(func))
946 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, func));
948 var self = ToObject(this);
949 var length = self.length;
951 parallel: for (;;) { // see ArrayMapPar() to explain why for(;;) etc
952 if (ShouldForceSequential())
953 break parallel;
954 if (!TRY_PARALLEL(mode))
955 break parallel;
957 var slicesInfo = ComputeSlicesInfo(length);
959 // Step 1. Compute which items from each slice of the result buffer should
960 // be preserved. When we're done, we have a uint8 array |survivors|
961 // containing 0 or 1 for each source element, indicating which members of
962 // the chunk survived. We also keep an array |counts| containing the total
963 // number of items that are being preserved from within one slice.
964 var numSlices = slicesInfo.count;
965 var counts = NewDenseArray(numSlices);
966 for (var i = 0; i < numSlices; i++)
967 UnsafePutElements(counts, i, 0);
969 var survivors = new Uint8Array(length);
970 ForkJoin(findSurvivorsThread, 0, numSlices, ForkJoinMode(mode));
972 // Step 2. Compress the slices into one contiguous set.
973 var count = 0;
974 for (var i = 0; i < numSlices; i++)
975 count += counts[i];
976 var buffer = NewDenseArray(count);
977 if (count > 0)
978 ForkJoin(copySurvivorsThread, 0, numSlices, ForkJoinMode(mode));
980 return buffer;
981 }
983 // Sequential fallback:
984 ASSERT_SEQUENTIAL_IS_OK(mode);
985 var buffer = [];
986 for (var i = 0; i < length; i++) {
987 var elem = self[i];
988 if (func(elem, i, self))
989 ARRAY_PUSH(buffer, elem);
990 }
991 return buffer;
993 /**
994 * As described above, our goal is to determine which items we will preserve
995 * from a given slice, storing "to-keep" bits into 32-bit chunks.
996 */
997 function findSurvivorsThread(workerId, sliceStart, sliceEnd) {
998 var sliceShift = slicesInfo.shift;
999 var sliceId;
1000 while (GET_SLICE(sliceStart, sliceEnd, sliceId)) {
1001 var count = 0;
1002 var indexStart = SLICE_START_INDEX(sliceShift, sliceId);
1003 var indexEnd = SLICE_END_INDEX(sliceShift, indexStart, length);
1004 for (var indexPos = indexStart; indexPos < indexEnd; indexPos++) {
1005 var keep = !!func(self[indexPos], indexPos, self);
1006 UnsafePutElements(survivors, indexPos, keep);
1007 count += keep;
1008 }
1009 UnsafePutElements(counts, sliceId, count);
1010 }
1011 return sliceId;
1012 }
1014 /**
1015 * Copies the survivors from this slice into the correct position. Note
1016 * that this is an idempotent operation that does not invoke user
1017 * code. Therefore, we don't expect bailouts and make an effort to proceed
1018 * chunk by chunk or avoid duplicating work.
1019 */
1020 function copySurvivorsThread(workerId, sliceStart, sliceEnd) {
1021 var sliceShift = slicesInfo.shift;
1022 var sliceId;
1023 while (GET_SLICE(sliceStart, sliceEnd, sliceId)) {
1024 // Total up the items preserved by previous slices.
1025 var total = 0;
1026 for (var i = 0; i < sliceId + 1; i++)
1027 total += counts[i];
1029 // Are we done?
1030 var count = total - counts[sliceId];
1031 if (count === total)
1032 continue;
1034 var indexStart = SLICE_START_INDEX(sliceShift, sliceId);
1035 var indexEnd = SLICE_END_INDEX(sliceShift, indexStart, length);
1036 for (var indexPos = indexStart; indexPos < indexEnd; indexPos++) {
1037 if (survivors[indexPos]) {
1038 UnsafePutElements(buffer, count++, self[indexPos]);
1039 if (count == total)
1040 break;
1041 }
1042 }
1043 }
1045 return sliceId;
1046 }
1048 return undefined;
1049 }
1051 /**
1052 * "Comprehension form": This is the function invoked for
1053 * |Array.{build,buildPar}(len, fn)| It creates a new array with length |len|
1054 * where index |i| is equal to |fn(i)|.
1055 *
1056 * The final |mode| argument is an internal argument used only during our
1057 * unit-testing.
1058 */
1059 function ArrayStaticBuild(length, func) {
1060 if (!IS_UINT32(length))
1061 ThrowError(JSMSG_BAD_ARRAY_LENGTH);
1062 if (!IsCallable(func))
1063 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(1, func));
1065 var buffer = NewDenseArray(length);
1067 for (var i = 0; i < length; i++)
1068 UnsafePutElements(buffer, i, func(i));
1070 return buffer;
1071 }
1073 function ArrayStaticBuildPar(length, func, mode) {
1074 if (!IS_UINT32(length))
1075 ThrowError(JSMSG_BAD_ARRAY_LENGTH);
1076 if (!IsCallable(func))
1077 ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(1, func));
1079 var buffer = NewDenseArray(length);
1081 parallel: for (;;) {
1082 if (ShouldForceSequential())
1083 break parallel;
1084 if (!TRY_PARALLEL(mode))
1085 break parallel;
1087 var slicesInfo = ComputeSlicesInfo(length);
1088 ForkJoin(constructThread, 0, slicesInfo.count, ForkJoinMode(mode));
1089 return buffer;
1090 }
1092 // Sequential fallback:
1093 ASSERT_SEQUENTIAL_IS_OK(mode);
1094 for (var i = 0; i < length; i++)
1095 UnsafePutElements(buffer, i, func(i));
1096 return buffer;
1098 function constructThread(workerId, sliceStart, sliceEnd) {
1099 var sliceShift = slicesInfo.shift;
1100 var sliceId;
1101 while (GET_SLICE(sliceStart, sliceEnd, sliceId)) {
1102 var indexStart = SLICE_START_INDEX(sliceShift, sliceId);
1103 var indexEnd = SLICE_END_INDEX(sliceShift, indexStart, length);
1104 for (var i = indexStart; i < indexEnd; i++)
1105 UnsafePutElements(buffer, i, func(i));
1106 }
1107 return sliceId;
1108 }
1110 return undefined;
1111 }
1113 /*
1114 * Mark the main operations as clone-at-callsite for better precision.
1115 * This is slightly overkill, as all that we really need is to
1116 * specialize to the receiver and the elemental function, but in
1117 * practice this is likely not so different, since element functions
1118 * are often used in exactly one place.
1119 */
1120 SetScriptHints(ArrayMapPar, { cloneAtCallsite: true });
1121 SetScriptHints(ArrayReducePar, { cloneAtCallsite: true });
1122 SetScriptHints(ArrayScanPar, { cloneAtCallsite: true });
1123 SetScriptHints(ArrayScatterPar, { cloneAtCallsite: true });
1124 SetScriptHints(ArrayFilterPar, { cloneAtCallsite: true });
1125 SetScriptHints(ArrayStaticBuildPar, { cloneAtCallsite: true });
1127 #endif /* ENABLE_PARALLEL_JS */
