Fix max length check in ArrayPrototype.js' concatSlowPath().
[WebKit-https.git] / Source / JavaScriptCore / builtins / ArrayPrototype.js
1 /*
2  * Copyright (C) 2014-2017 Apple Inc. All rights reserved.
3  * Copyright (C) 2015 Yusuke Suzuki <utatane.tea@gmail.com>.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 @constructor
28 @globalPrivate
29 function createArrayIterator(iteratedObject, kind, iterationFunction)
30 {
31     this.@iteratedObject = iteratedObject;
32     this.@arrayIteratorKind = kind;
33     this.@arrayIteratorNextIndex = 0;
34     this.@arrayIteratorNext = iterationFunction;
35     this.@arrayIteratorIsDone = false;
36 }
37
38 function values()
39 {
40     "use strict";
41
42     if (this === null || this === @undefined)
43         @throwTypeError("Array.prototype.values requires that |this| not be null or undefined");
44
45     return new @createArrayIterator(@Object(this), "value", @arrayIteratorValueNext);
46 }
47
48 function keys()
49 {
50     "use strict";
51
52     if (this === null || this === @undefined)
53         @throwTypeError("Array.prototype.keys requires that |this| not be null or undefined");
54
55     return new @createArrayIterator(@Object(this), "key", @arrayIteratorKeyNext);
56 }
57
58 function entries()
59 {
60     "use strict";
61
62     if (this === null || this === @undefined)
63         @throwTypeError("Array.prototype.entries requires that |this| not be null or undefined");
64
65     return new @createArrayIterator(@Object(this), "key+value", @arrayIteratorKeyValueNext);
66 }
67
68 function reduce(callback /*, initialValue */)
69 {
70     "use strict";
71
72     if (this === null || this === @undefined)
73         @throwTypeError("Array.prototype.reduce requires that |this| not be null or undefined");
74
75     var array = @Object(this);
76     var length = @toLength(array.length);
77
78     if (typeof callback !== "function")
79         @throwTypeError("Array.prototype.reduce callback must be a function");
80
81     var argumentCount = @argumentCount();
82     if (length === 0 && argumentCount < 2)
83         @throwTypeError("reduce of empty array with no initial value");
84
85     var accumulator, k = 0;
86     if (argumentCount > 1)
87         accumulator = @argument(1);
88     else {
89         while (k < length && !(k in array))
90             k += 1;
91         if (k >= length)
92             @throwTypeError("reduce of empty array with no initial value");
93         accumulator = array[k++];
94     }
95
96     while (k < length) {
97         if (k in array)
98             accumulator = callback.@call(@undefined, accumulator, array[k], k, array);
99         k += 1;
100     }
101     return accumulator;
102 }
103
104 function reduceRight(callback /*, initialValue */)
105 {
106     "use strict";
107
108     if (this === null || this === @undefined)
109         @throwTypeError("Array.prototype.reduceRight requires that |this| not be null or undefined");
110
111     var array = @Object(this);
112     var length = @toLength(array.length);
113
114     if (typeof callback !== "function")
115         @throwTypeError("Array.prototype.reduceRight callback must be a function");
116
117     var argumentCount = @argumentCount();
118     if (length === 0 && argumentCount < 2)
119         @throwTypeError("reduceRight of empty array with no initial value");
120
121     var accumulator, k = length - 1;
122     if (argumentCount > 1)
123         accumulator = @argument(1);
124     else {
125         while (k >= 0 && !(k in array))
126             k -= 1;
127         if (k < 0)
128             @throwTypeError("reduceRight of empty array with no initial value");
129         accumulator = array[k--];
130     }
131
132     while (k >= 0) {
133         if (k in array)
134             accumulator = callback.@call(@undefined, accumulator, array[k], k, array);
135         k -= 1;
136     }
137     return accumulator;
138 }
139
140 function every(callback /*, thisArg */)
141 {
142     "use strict";
143
144     if (this === null || this === @undefined)
145         @throwTypeError("Array.prototype.every requires that |this| not be null or undefined");
146     
147     var array = @Object(this);
148     var length = @toLength(array.length);
149
150     if (typeof callback !== "function")
151         @throwTypeError("Array.prototype.every callback must be a function");
152     
153     var thisArg = @argument(1);
154     
155     for (var i = 0; i < length; i++) {
156         if (!(i in array))
157             continue;
158         if (!callback.@call(thisArg, array[i], i, array))
159             return false;
160     }
161     
162     return true;
163 }
164
165 function forEach(callback /*, thisArg */)
166 {
167     "use strict";
168
169     if (this === null || this === @undefined)
170         @throwTypeError("Array.prototype.forEach requires that |this| not be null or undefined");
171     
172     var array = @Object(this);
173     var length = @toLength(array.length);
174
175     if (typeof callback !== "function")
176         @throwTypeError("Array.prototype.forEach callback must be a function");
177     
178     var thisArg = @argument(1);
179     
180     for (var i = 0; i < length; i++) {
181         if (i in array)
182             callback.@call(thisArg, array[i], i, array);
183     }
184 }
185
186 function filter(callback /*, thisArg */)
187 {
188     "use strict";
189
190     if (this === null || this === @undefined)
191         @throwTypeError("Array.prototype.filter requires that |this| not be null or undefined");
192     
193     var array = @Object(this);
194     var length = @toLength(array.length);
195
196     if (typeof callback !== "function")
197         @throwTypeError("Array.prototype.filter callback must be a function");
198     
199     var thisArg = @argument(1);
200
201     // Do 9.4.2.3 ArraySpeciesCreate
202     var result;
203     var constructor;
204     if (@isArray(array)) {
205         constructor = array.constructor;
206         // We have this check so that if some array from a different global object
207         // calls this map they don't get an array with the Array.prototype of the
208         // other global object.
209         if (@isArrayConstructor(constructor) && @Array !== constructor)
210             constructor = @undefined;
211         if (@isObject(constructor)) {
212             constructor = constructor.@speciesSymbol;
213             if (constructor === null)
214                 constructor = @undefined;
215         }
216     }
217     if (constructor === @Array || constructor === @undefined)
218         result = @newArrayWithSize(0);
219     else
220         result = new constructor(0);
221
222     var nextIndex = 0;
223     for (var i = 0; i < length; i++) {
224         if (!(i in array))
225             continue;
226         var current = array[i]
227         if (callback.@call(thisArg, current, i, array)) {
228             @putByValDirect(result, nextIndex, current);
229             ++nextIndex;
230         }
231     }
232     return result;
233 }
234
235 function map(callback /*, thisArg */)
236 {
237     "use strict";
238
239     if (this === null || this === @undefined)
240         @throwTypeError("Array.prototype.map requires that |this| not be null or undefined");
241     
242     var array = @Object(this);
243     var length = @toLength(array.length);
244
245     if (typeof callback !== "function")
246         @throwTypeError("Array.prototype.map callback must be a function");
247     
248     var thisArg = @argument(1);
249
250     // Do 9.4.2.3 ArraySpeciesCreate
251     var result;
252     var constructor;
253     if (@isArray(array)) {
254         constructor = array.constructor;
255         // We have this check so that if some array from a different global object
256         // calls this map they don't get an array with the Array.prototype of the
257         // other global object.
258         if (@isArrayConstructor(constructor) && @Array !== constructor)
259             constructor = @undefined;
260         if (@isObject(constructor)) {
261             constructor = constructor.@speciesSymbol;
262             if (constructor === null)
263                 constructor = @undefined;
264         }
265     }
266     if (constructor === @Array || constructor === @undefined)
267         result = @newArrayWithSize(length);
268     else
269         result = new constructor(length);
270
271     var nextIndex = 0;
272     for (var i = 0; i < length; i++) {
273         if (!(i in array))
274             continue;
275         var mappedValue = callback.@call(thisArg, array[i], i, array);
276         @putByValDirect(result, i, mappedValue);
277     }
278     return result;
279 }
280
281 function some(callback /*, thisArg */)
282 {
283     "use strict";
284
285     if (this === null || this === @undefined)
286         @throwTypeError("Array.prototype.some requires that |this| not be null or undefined");
287     
288     var array = @Object(this);
289     var length = @toLength(array.length);
290
291     if (typeof callback !== "function")
292         @throwTypeError("Array.prototype.some callback must be a function");
293     
294     var thisArg = @argument(1);
295     for (var i = 0; i < length; i++) {
296         if (!(i in array))
297             continue;
298         if (callback.@call(thisArg, array[i], i, array))
299             return true;
300     }
301     return false;
302 }
303
304 function fill(value /* [, start [, end]] */)
305 {
306     "use strict";
307
308     if (this === null || this === @undefined)
309         @throwTypeError("Array.prototype.fill requires that |this| not be null or undefined");
310
311     var array = @Object(this);
312     var length = @toLength(array.length);
313
314     var relativeStart = @toInteger(@argument(1));
315     var k = 0;
316     if (relativeStart < 0) {
317         k = length + relativeStart;
318         if (k < 0)
319             k = 0;
320     } else {
321         k = relativeStart;
322         if (k > length)
323             k = length;
324     }
325     var relativeEnd = length;
326     var end = @argument(2);
327     if (end !== @undefined)
328         relativeEnd = @toInteger(end);
329     var final = 0;
330     if (relativeEnd < 0) {
331         final = length + relativeEnd;
332         if (final < 0)
333             final = 0;
334     } else {
335         final = relativeEnd;
336         if (final > length)
337             final = length;
338     }
339     for (; k < final; k++)
340         array[k] = value;
341     return array;
342 }
343
344 function find(callback /*, thisArg */)
345 {
346     "use strict";
347
348     if (this === null || this === @undefined)
349         @throwTypeError("Array.prototype.find requires that |this| not be null or undefined");
350     
351     var array = @Object(this);
352     var length = @toLength(array.length);
353
354     if (typeof callback !== "function")
355         @throwTypeError("Array.prototype.find callback must be a function");
356     
357     var thisArg = @argument(1);
358     for (var i = 0; i < length; i++) {
359         var kValue = array[i];
360         if (callback.@call(thisArg, kValue, i, array))
361             return kValue;
362     }
363     return @undefined;
364 }
365
366 function findIndex(callback /*, thisArg */)
367 {
368     "use strict";
369
370     if (this === null || this === @undefined)
371         @throwTypeError("Array.prototype.findIndex requires that |this| not be null or undefined");
372     
373     var array = @Object(this);
374     var length = @toLength(array.length);
375
376     if (typeof callback !== "function")
377         @throwTypeError("Array.prototype.findIndex callback must be a function");
378     
379     var thisArg = @argument(1);
380     for (var i = 0; i < length; i++) {
381         if (callback.@call(thisArg, array[i], i, array))
382             return i;
383     }
384     return -1;
385 }
386
387 function includes(searchElement /*, fromIndex*/)
388 {
389     "use strict";
390
391     if (this === null || this === @undefined)
392         @throwTypeError("Array.prototype.includes requires that |this| not be null or undefined");
393
394     var array = @Object(this);
395     var length = @toLength(array.length);
396
397     if (length === 0)
398         return false;
399
400     var fromIndex = 0;
401     var from = @argument(1);
402     if (from !== @undefined)
403         fromIndex = @toInteger(from);
404
405     var index;
406     if (fromIndex >= 0)
407         index = fromIndex;
408     else
409         index = length + fromIndex;
410
411     if (index < 0)
412         index = 0;
413
414     var currentElement;
415     for (; index < length; ++index) {
416         currentElement = array[index];
417         // Use SameValueZero comparison, rather than just StrictEquals.
418         if (searchElement === currentElement || (searchElement !== searchElement && currentElement !== currentElement))
419             return true;
420     }
421     return false;
422 }
423
424 function sort(comparator)
425 {
426     "use strict";
427
428     function min(a, b)
429     {
430         return a < b ? a : b;
431     }
432
433     function stringComparator(a, b)
434     {
435         var aString = a.string;
436         var bString = b.string;
437
438         var aLength = aString.length;
439         var bLength = bString.length;
440         var length = min(aLength, bLength);
441
442         for (var i = 0; i < length; ++i) {
443             var aCharCode = aString.@charCodeAt(i);
444             var bCharCode = bString.@charCodeAt(i);
445
446             if (aCharCode == bCharCode)
447                 continue;
448
449             return aCharCode - bCharCode;
450         }
451
452         return aLength - bLength;
453     }
454
455     // Move undefineds and holes to the end of a sparse array. Result is [values..., undefineds..., holes...].
456     function compactSparse(array, dst, src, length)
457     {
458         var values = [ ];
459         var seen = { };
460         var valueCount = 0;
461         var undefinedCount = 0;
462
463         // Clean up after the in-progress non-sparse compaction that failed.
464         for (var i = dst; i < src; ++i)
465             delete array[i];
466
467         for (var object = array; object; object = @Object.@getPrototypeOf(object)) {
468             var propertyNames = @Object.@getOwnPropertyNames(object);
469             for (var i = 0; i < propertyNames.length; ++i) {
470                 var index = propertyNames[i];
471                 if (index < length) { // Exclude non-numeric properties and properties past length.
472                     if (seen[index]) // Exclude duplicates.
473                         continue;
474                     seen[index] = 1;
475
476                     var value = array[index];
477                     delete array[index];
478
479                     if (value === @undefined) {
480                         ++undefinedCount;
481                         continue;
482                     }
483
484                     array[valueCount++] = value;
485                 }
486             }
487         }
488
489         for (var i = valueCount; i < valueCount + undefinedCount; ++i)
490             array[i] = @undefined;
491
492         return valueCount;
493     }
494
495     function compactSlow(array, length)
496     {
497         var holeCount = 0;
498
499         for (var dst = 0, src = 0; src < length; ++src) {
500             if (!(src in array)) {
501                 ++holeCount;
502                 if (holeCount < 256)
503                     continue;
504                 return compactSparse(array, dst, src, length);
505             }
506
507             var value = array[src];
508             if (value === @undefined)
509                 continue;
510
511             array[dst++] = value;
512         }
513
514         var valueCount = dst;
515         var undefinedCount = length - valueCount - holeCount;
516
517         for (var i = valueCount; i < valueCount + undefinedCount; ++i)
518             array[i] = @undefined;
519
520         for (var i = valueCount + undefinedCount; i < length; ++i)
521             delete array[i];
522
523         return valueCount;
524     }
525
526     // Move undefineds and holes to the end of an array. Result is [values..., undefineds..., holes...].
527     function compact(array, length)
528     {
529         for (var i = 0; i < array.length; ++i) {
530             if (array[i] === @undefined)
531                 return compactSlow(array, length);
532         }
533
534         return length;
535     }
536
537     function merge(dst, src, srcIndex, srcEnd, width, comparator)
538     {
539         var left = srcIndex;
540         var leftEnd = min(left + width, srcEnd);
541         var right = leftEnd;
542         var rightEnd = min(right + width, srcEnd);
543
544         for (var dstIndex = left; dstIndex < rightEnd; ++dstIndex) {
545             if (right < rightEnd) {
546                 if (left >= leftEnd || comparator(src[right], src[left]) < 0) {
547                     dst[dstIndex] = src[right++];
548                     continue;
549                 }
550             }
551
552             dst[dstIndex] = src[left++];
553         }
554     }
555
556     function mergeSort(array, valueCount, comparator)
557     {
558         var buffer = [ ];
559         buffer.length = valueCount;
560
561         var dst = buffer;
562         var src = array;
563         for (var width = 1; width < valueCount; width *= 2) {
564             for (var srcIndex = 0; srcIndex < valueCount; srcIndex += 2 * width)
565                 merge(dst, src, srcIndex, valueCount, width, comparator);
566
567             var tmp = src;
568             src = dst;
569             dst = tmp;
570         }
571
572         if (src != array) {
573             for(var i = 0; i < valueCount; i++)
574                 array[i] = src[i];
575         }
576     }
577
578     function bucketSort(array, dst, bucket, depth)
579     {
580         if (bucket.length < 32 || depth > 32) {
581             mergeSort(bucket, bucket.length, stringComparator);
582             for (var i = 0; i < bucket.length; ++i)
583                 array[dst++] = bucket[i].value;
584             return dst;
585         }
586
587         var buckets = [ ];
588         for (var i = 0; i < bucket.length; ++i) {
589             var entry = bucket[i];
590             var string = entry.string;
591             if (string.length == depth) {
592                 array[dst++] = entry.value;
593                 continue;
594             }
595
596             var c = string.@charCodeAt(depth);
597             if (!buckets[c])
598                 buckets[c] = [ ];
599             buckets[c][buckets[c].length] = entry;
600         }
601
602         for (var i = 0; i < buckets.length; ++i) {
603             if (!buckets[i])
604                 continue;
605             dst = bucketSort(array, dst, buckets[i], depth + 1);
606         }
607
608         return dst;
609     }
610
611     function comparatorSort(array, length, comparator)
612     {
613         var valueCount = compact(array, length);
614         mergeSort(array, valueCount, comparator);
615     }
616
617     function stringSort(array, length)
618     {
619         var valueCount = compact(array, length);
620
621         var strings = @newArrayWithSize(valueCount);
622         for (var i = 0; i < valueCount; ++i)
623             strings[i] = { string: @toString(array[i]), value: array[i] };
624
625         bucketSort(array, 0, strings, 0);
626     }
627
628     if (this === null || this === @undefined)
629         @throwTypeError("Array.prototype.sort requires that |this| not be null or undefined");
630
631     var array = @Object(this);
632
633     var length = array.length >>> 0;
634
635     // For compatibility with Firefox and Chrome, do nothing observable
636     // to the target array if it has 0 or 1 sortable properties.
637     if (length < 2)
638         return array;
639
640     if (typeof comparator == "function")
641         comparatorSort(array, length, comparator);
642     else if (comparator === @undefined)
643         stringSort(array, length);
644     else
645         @throwTypeError("Array.prototype.sort requires the comparsion function be a function or undefined");
646
647     return array;
648 }
649
650 function concatSlowPath()
651 {
652     "use strict";
653
654     if (this === null || this === @undefined)
655         @throwTypeError("Array.prototype.concat requires that |this| not be null or undefined");
656
657     var currentElement = @Object(this);
658
659     var constructor;
660     if (@isArray(currentElement)) {
661         constructor = currentElement.constructor;
662         // We have this check so that if some array from a different global object
663         // calls this map they don't get an array with the Array.prototype of the
664         // other global object.
665         if (@isArrayConstructor(constructor) && @Array !== constructor)
666             constructor = @undefined;
667         else if (@isObject(constructor)) {
668             constructor = constructor.@speciesSymbol;
669             if (constructor === null)
670                 constructor = @Array;
671         }
672     }
673
674     var argCount = arguments.length;
675     var result;
676     if (constructor === @Array || constructor === @undefined)
677         result = @newArrayWithSize(0);
678     else
679         result = new constructor(0);
680     var resultIsArray = @isJSArray(result);
681
682     var resultIndex = 0;
683     var argIndex = 0;
684
685     do {
686         let spreadable = @isObject(currentElement) && currentElement.@isConcatSpreadableSymbol;
687         if ((spreadable === @undefined && @isArray(currentElement)) || spreadable) {
688             let length = @toLength(currentElement.length);
689             if (length + resultIndex > @MAX_ARRAY_INDEX)
690                 @throwRangeError("Length exceeded the maximum array length");
691             if (resultIsArray && @isJSArray(currentElement)) {
692                 @appendMemcpy(result, currentElement, resultIndex);
693                 resultIndex += length;
694             } else {
695                 for (var i = 0; i < length; i++) {
696                     if (i in currentElement)
697                         @putByValDirect(result, resultIndex, currentElement[i]);
698                     resultIndex++;
699                 }
700             }
701         } else {
702             if (resultIndex >= @MAX_ARRAY_INDEX)
703                 @throwRangeError("Length exceeded the maximum array length");
704             @putByValDirect(result, resultIndex++, currentElement);
705         }
706         currentElement = arguments[argIndex];
707     } while (argIndex++ < argCount);
708
709     result.length = resultIndex;
710     return result;
711 }
712
713 function concat(first)
714 {
715     "use strict";
716
717     if (@argumentCount() === 1
718         && @isJSArray(this)
719         && this.@isConcatSpreadableSymbol === @undefined
720         && (!@isObject(first) || first.@isConcatSpreadableSymbol === @undefined)) {
721
722         let result = @concatMemcpy(this, first);
723         if (result !== null)
724             return result;
725     }
726
727     return @tailCallForwardArguments(@concatSlowPath, this);
728 }
729
730 function copyWithin(target, start /*, end */)
731 {
732     "use strict";
733
734     function maxWithPositives(a, b)
735     {
736         return (a < b) ? b : a;
737     }
738
739     function minWithMaybeNegativeZeroAndPositive(maybeNegativeZero, positive)
740     {
741         return (maybeNegativeZero < positive) ? maybeNegativeZero : positive;
742     }
743
744     if (this === null || this === @undefined)
745         @throwTypeError("Array.copyWithin requires that |this| not be null or undefined");
746
747     var array = @Object(this);
748     var length = @toLength(array.length);
749
750     var relativeTarget = @toInteger(target);
751     var to = (relativeTarget < 0) ? maxWithPositives(length + relativeTarget, 0) : minWithMaybeNegativeZeroAndPositive(relativeTarget, length);
752
753     var relativeStart = @toInteger(start);
754     var from = (relativeStart < 0) ? maxWithPositives(length + relativeStart, 0) : minWithMaybeNegativeZeroAndPositive(relativeStart, length);
755
756     var relativeEnd;
757     var end = @argument(2);
758     if (end === @undefined)
759         relativeEnd = length;
760     else
761         relativeEnd = @toInteger(end);
762
763     var finalValue = (relativeEnd < 0) ? maxWithPositives(length + relativeEnd, 0) : minWithMaybeNegativeZeroAndPositive(relativeEnd, length);
764
765     var count = minWithMaybeNegativeZeroAndPositive(finalValue - from, length - to);
766
767     var direction = 1;
768     if (from < to && to < from + count) {
769         direction = -1;
770         from = from + count - 1;
771         to = to + count - 1;
772     }
773
774     for (var i = 0; i < count; ++i, from += direction, to += direction) {
775         if (from in array)
776             array[to] = array[from];
777         else
778             delete array[to];
779     }
780
781     return array;
782 }