a47bf6b7ac87722617edfb388878cf1969782e54
[WebKit-https.git] / Source / JavaScriptCore / builtins / ArrayPrototype.js
1 /*
2  * Copyright (C) 2014-2016 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)
43         throw new @TypeError("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)
53         throw new @TypeError("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)
63         throw new @TypeError("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)
73         throw new @TypeError("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         throw new @TypeError("Array.prototype.reduce callback must be a function");
80
81     if (length === 0 && arguments.length < 2)
82         throw new @TypeError("reduce of empty array with no initial value");
83
84     var accumulator, k = 0;
85     if (arguments.length > 1)
86         accumulator = arguments[1];
87     else {
88         while (k < length && !(k in array))
89             k += 1;
90         if (k >= length)
91             throw new @TypeError("reduce of empty array with no initial value");
92         accumulator = array[k++];
93     }
94
95     while (k < length) {
96         if (k in array)
97             accumulator = callback.@call(@undefined, accumulator, array[k], k, array);
98         k += 1;
99     }
100     return accumulator;
101 }
102
103 function reduceRight(callback /*, initialValue */)
104 {
105     "use strict";
106
107     if (this == null)
108         throw new @TypeError("Array.prototype.reduceRight requires that |this| not be null or undefined");
109
110     var array = @Object(this);
111     var length = @toLength(array.length);
112
113     if (typeof callback !== "function")
114         throw new @TypeError("Array.prototype.reduceRight callback must be a function");
115
116     if (length === 0 && arguments.length < 2)
117         throw new @TypeError("reduceRight of empty array with no initial value");
118
119     var accumulator, k = length - 1;
120     if (arguments.length > 1)
121         accumulator = arguments[1];
122     else {
123         while (k >= 0 && !(k in array))
124             k -= 1;
125         if (k < 0)
126             throw new @TypeError("reduceRight of empty array with no initial value");
127         accumulator = array[k--];
128     }
129
130     while (k >= 0) {
131         if (k in array)
132             accumulator = callback.@call(@undefined, accumulator, array[k], k, array);
133         k -= 1;
134     }
135     return accumulator;
136 }
137
138 function every(callback /*, thisArg */)
139 {
140     "use strict";
141
142     if (this == null)
143         throw new @TypeError("Array.prototype.every requires that |this| not be null or undefined");
144     
145     var array = @Object(this);
146     var length = @toLength(array.length);
147
148     if (typeof callback !== "function")
149         throw new @TypeError("Array.prototype.every callback must be a function");
150     
151     var thisArg = arguments.length > 1 ? arguments[1] : @undefined;
152     
153     for (var i = 0; i < length; i++) {
154         if (!(i in array))
155             continue;
156         if (!callback.@call(thisArg, array[i], i, array))
157             return false;
158     }
159     
160     return true;
161 }
162
163 function forEach(callback /*, thisArg */)
164 {
165     "use strict";
166
167     if (this == null)
168         throw new @TypeError("Array.prototype.forEach requires that |this| not be null or undefined");
169     
170     var array = @Object(this);
171     var length = @toLength(array.length);
172
173     if (typeof callback !== "function")
174         throw new @TypeError("Array.prototype.forEach callback must be a function");
175     
176     var thisArg = arguments.length > 1 ? arguments[1] : @undefined;
177     
178     for (var i = 0; i < length; i++) {
179         if (i in array)
180             callback.@call(thisArg, array[i], i, array);
181     }
182 }
183
184 function filter(callback /*, thisArg */)
185 {
186     "use strict";
187
188     if (this == null)
189         throw new @TypeError("Array.prototype.filter requires that |this| not be null or undefined");
190     
191     var array = @Object(this);
192     var length = @toLength(array.length);
193
194     if (typeof callback !== "function")
195         throw new @TypeError("Array.prototype.filter callback must be a function");
196     
197     var thisArg = arguments.length > 1 ? arguments[1] : @undefined;
198
199     // Do 9.4.2.3 ArraySpeciesCreate
200     var result;
201     var constructor;
202     if (@isArray(array)) {
203         constructor = array.constructor;
204         // We have this check so that if some array from a different global object
205         // calls this map they don't get an array with the Array.prototype of the
206         // other global object.
207         if (@isArrayConstructor(constructor) && @Array !== constructor)
208             constructor = @undefined;
209         if (@isObject(constructor)) {
210             constructor = constructor.@speciesSymbol;
211             if (constructor === null)
212                 constructor = @undefined;
213         }
214     }
215     if (constructor === @Array || constructor === @undefined)
216         result = [];
217     else
218         result = new constructor(0);
219
220     var nextIndex = 0;
221     for (var i = 0; i < length; i++) {
222         if (!(i in array))
223             continue;
224         var current = array[i]
225         if (callback.@call(thisArg, current, i, array)) {
226             @putByValDirect(result, nextIndex, current);
227             ++nextIndex;
228         }
229     }
230     return result;
231 }
232
233 function map(callback /*, thisArg */)
234 {
235     "use strict";
236
237     if (this == null)
238         throw new @TypeError("Array.prototype.map requires that |this| not be null or undefined");
239     
240     var array = @Object(this);
241     var length = @toLength(array.length);
242
243     if (typeof callback !== "function")
244         throw new @TypeError("Array.prototype.map callback must be a function");
245     
246     var thisArg = arguments.length > 1 ? arguments[1] : @undefined;
247
248     // Do 9.4.2.3 ArraySpeciesCreate
249     var result;
250     var constructor;
251     if (@isArray(array)) {
252         constructor = array.constructor;
253         // We have this check so that if some array from a different global object
254         // calls this map they don't get an array with the Array.prototype of the
255         // other global object.
256         if (@isArrayConstructor(constructor) && @Array !== constructor)
257             constructor = @undefined;
258         if (@isObject(constructor)) {
259             constructor = constructor.@speciesSymbol;
260             if (constructor === null)
261                 constructor = @undefined;
262         }
263     }
264     if (constructor === @Array || constructor === @undefined)
265         result = @Array(length);
266     else
267         result = new constructor(length);
268
269     var nextIndex = 0;
270     for (var i = 0; i < length; i++) {
271         if (!(i in array))
272             continue;
273         var mappedValue = callback.@call(thisArg, array[i], i, array);
274         @putByValDirect(result, i, mappedValue);
275     }
276     return result;
277 }
278
279 function some(callback /*, thisArg */)
280 {
281     "use strict";
282
283     if (this == null)
284         throw new @TypeError("Array.prototype.some requires that |this| not be null or undefined");
285     
286     var array = @Object(this);
287     var length = @toLength(array.length);
288
289     if (typeof callback !== "function")
290         throw new @TypeError("Array.prototype.some callback must be a function");
291     
292     var thisArg = arguments.length > 1 ? arguments[1] : @undefined;
293     for (var i = 0; i < length; i++) {
294         if (!(i in array))
295             continue;
296         if (callback.@call(thisArg, array[i], i, array))
297             return true;
298     }
299     return false;
300 }
301
302 function fill(value /* [, start [, end]] */)
303 {
304     "use strict";
305
306     if (this == null)
307         throw new @TypeError("Array.prototype.fill requires that |this| not be null or undefined");
308
309     var array = @Object(this);
310     var length = @toLength(array.length);
311
312     var relativeStart = 0;
313     if (arguments.length > 1 && arguments[1] !== @undefined)
314         relativeStart = arguments[1] | 0;
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     if (arguments.length > 2 && arguments[2] !== @undefined)
327         relativeEnd = arguments[2] | 0;
328     var final = 0;
329     if (relativeEnd < 0) {
330         final = length + relativeEnd;
331         if (final < 0)
332             final = 0;
333     } else {
334         final = relativeEnd;
335         if (final > length)
336             final = length;
337     }
338     for (; k < final; k++)
339         array[k] = value;
340     return array;
341 }
342
343 function find(callback /*, thisArg */)
344 {
345     "use strict";
346
347     if (this == null)
348         throw new @TypeError("Array.prototype.find requires that |this| not be null or undefined");
349     
350     var array = @Object(this);
351     var length = @toLength(array.length);
352
353     if (typeof callback !== "function")
354         throw new @TypeError("Array.prototype.find callback must be a function");
355     
356     var thisArg = arguments.length > 1 ? arguments[1] : @undefined;
357     for (var i = 0; i < length; i++) {
358         var kValue = array[i];
359         if (callback.@call(thisArg, kValue, i, array))
360             return kValue;
361     }
362     return @undefined;
363 }
364
365 function findIndex(callback /*, thisArg */)
366 {
367     "use strict";
368
369     if (this == null)
370         throw new @TypeError("Array.prototype.findIndex requires that |this| not be null or undefined");
371     
372     var array = @Object(this);
373     var length = @toLength(array.length);
374
375     if (typeof callback !== "function")
376         throw new @TypeError("Array.prototype.findIndex callback must be a function");
377     
378     var thisArg = arguments.length > 1 ? arguments[1] : @undefined;
379     for (var i = 0; i < length; i++) {
380         if (callback.@call(thisArg, array[i], i, array))
381             return i;
382     }
383     return -1;
384 }
385
386 function includes(searchElement /*, fromIndex*/)
387 {
388     "use strict";
389
390     if (this == null)
391         throw new @TypeError("Array.prototype.includes requires that |this| not be null or undefined");
392
393     var array = @Object(this);
394     var length = @toLength(array.length);
395
396     if (length === 0)
397         return false;
398
399     var fromIndex = 0;
400     if (arguments.length > 1 && arguments[1] !== @undefined)
401         fromIndex = @toInteger(arguments[1]);
402
403     var index;
404     if (fromIndex >= 0)
405         index = fromIndex;
406     else
407         index = length + fromIndex;
408
409     if (index < 0)
410         index = 0;
411
412     var currentElement;
413     for (; index < length; ++index) {
414         currentElement = array[index];
415         // Use SameValueZero comparison, rather than just StrictEquals.
416         if (searchElement === currentElement || (searchElement !== searchElement && currentElement !== currentElement))
417             return true;
418     }
419     return false;
420 }
421
422 function sort(comparator)
423 {
424     "use strict";
425
426     function min(a, b)
427     {
428         return a < b ? a : b;
429     }
430
431     function stringComparator(a, b)
432     {
433         var aString = a.string;
434         var bString = b.string;
435
436         var aLength = aString.length;
437         var bLength = bString.length;
438         var length = min(aLength, bLength);
439
440         for (var i = 0; i < length; ++i) {
441             var aCharCode = aString.@charCodeAt(i);
442             var bCharCode = bString.@charCodeAt(i);
443
444             if (aCharCode == bCharCode)
445                 continue;
446
447             return aCharCode - bCharCode;
448         }
449
450         return aLength - bLength;
451     }
452
453     // Move undefineds and holes to the end of a sparse array. Result is [values..., undefineds..., holes...].
454     function compactSparse(array, dst, src, length)
455     {
456         var values = [ ];
457         var seen = { };
458         var valueCount = 0;
459         var undefinedCount = 0;
460
461         // Clean up after the in-progress non-sparse compaction that failed.
462         for (var i = dst; i < src; ++i)
463             delete array[i];
464
465         for (var object = array; object; object = @Object.@getPrototypeOf(object)) {
466             var propertyNames = @Object.@getOwnPropertyNames(object);
467             for (var i = 0; i < propertyNames.length; ++i) {
468                 var index = propertyNames[i];
469                 if (index < length) { // Exclude non-numeric properties and properties past length.
470                     if (seen[index]) // Exclude duplicates.
471                         continue;
472                     seen[index] = 1;
473
474                     var value = array[index];
475                     delete array[index];
476
477                     if (value === @undefined) {
478                         ++undefinedCount;
479                         continue;
480                     }
481
482                     array[valueCount++] = value;
483                 }
484             }
485         }
486
487         for (var i = valueCount; i < valueCount + undefinedCount; ++i)
488             array[i] = @undefined;
489
490         return valueCount;
491     }
492
493     function compactSlow(array, length)
494     {
495         var holeCount = 0;
496
497         for (var dst = 0, src = 0; src < length; ++src) {
498             if (!(src in array)) {
499                 ++holeCount;
500                 if (holeCount < 256)
501                     continue;
502                 return compactSparse(array, dst, src, length);
503             }
504
505             var value = array[src];
506             if (value === @undefined)
507                 continue;
508
509             array[dst++] = value;
510         }
511
512         var valueCount = dst;
513         var undefinedCount = length - valueCount - holeCount;
514
515         for (var i = valueCount; i < valueCount + undefinedCount; ++i)
516             array[i] = @undefined;
517
518         for (var i = valueCount + undefinedCount; i < length; ++i)
519             delete array[i];
520
521         return valueCount;
522     }
523
524     // Move undefineds and holes to the end of an array. Result is [values..., undefineds..., holes...].
525     function compact(array, length)
526     {
527         for (var i = 0; i < array.length; ++i) {
528             if (array[i] === @undefined)
529                 return compactSlow(array, length);
530         }
531
532         return length;
533     }
534
535     function merge(dst, src, srcIndex, srcEnd, width, comparator)
536     {
537         var left = srcIndex;
538         var leftEnd = min(left + width, srcEnd);
539         var right = leftEnd;
540         var rightEnd = min(right + width, srcEnd);
541
542         for (var dstIndex = left; dstIndex < rightEnd; ++dstIndex) {
543             if (right < rightEnd) {
544                 if (left >= leftEnd || comparator(src[right], src[left]) < 0) {
545                     dst[dstIndex] = src[right++];
546                     continue;
547                 }
548             }
549
550             dst[dstIndex] = src[left++];
551         }
552     }
553
554     function mergeSort(array, valueCount, comparator)
555     {
556         var buffer = [ ];
557         buffer.length = valueCount;
558
559         var dst = buffer;
560         var src = array;
561         for (var width = 1; width < valueCount; width *= 2) {
562             for (var srcIndex = 0; srcIndex < valueCount; srcIndex += 2 * width)
563                 merge(dst, src, srcIndex, valueCount, width, comparator);
564
565             var tmp = src;
566             src = dst;
567             dst = tmp;
568         }
569
570         if (src != array) {
571             for(var i = 0; i < valueCount; i++)
572                 array[i] = src[i];
573         }
574     }
575
576     function bucketSort(array, dst, bucket, depth)
577     {
578         if (bucket.length < 32 || depth > 32) {
579             mergeSort(bucket, bucket.length, stringComparator);
580             for (var i = 0; i < bucket.length; ++i)
581                 array[dst++] = bucket[i].value;
582             return dst;
583         }
584
585         var buckets = [ ];
586         for (var i = 0; i < bucket.length; ++i) {
587             var entry = bucket[i];
588             var string = entry.string;
589             if (string.length == depth) {
590                 array[dst++] = entry.value;
591                 continue;
592             }
593
594             var c = string.@charCodeAt(depth);
595             if (!buckets[c])
596                 buckets[c] = [ ];
597             buckets[c][buckets[c].length] = entry;
598         }
599
600         for (var i = 0; i < buckets.length; ++i) {
601             if (!buckets[i])
602                 continue;
603             dst = bucketSort(array, dst, buckets[i], depth + 1);
604         }
605
606         return dst;
607     }
608
609     function comparatorSort(array, comparator)
610     {
611         var length = array.length >>> 0;
612
613         // For compatibility with Firefox and Chrome, do nothing observable
614         // to the target array if it has 0 or 1 sortable properties.
615         if (length < 2)
616             return;
617
618         var valueCount = compact(array, length);
619         mergeSort(array, valueCount, comparator);
620     }
621
622     function stringSort(array)
623     {
624         var length = array.length >>> 0;
625
626         // For compatibility with Firefox and Chrome, do nothing observable
627         // to the target array if it has 0 or 1 sortable properties.
628         if (length < 2)
629             return;
630
631         var valueCount = compact(array, length);
632
633         var strings = new @Array(valueCount);
634         for (var i = 0; i < valueCount; ++i)
635             strings[i] = { string: @toString(array[i]), value: array[i] };
636
637         bucketSort(array, 0, strings, 0);
638     }
639
640     if (this == null)
641         throw new @TypeError("Array.prototype.sort requires that |this| not be null or undefined");
642
643     if (typeof this == "string")
644         throw new @TypeError("Attempted to assign to readonly property.");
645
646     var array = @Object(this);
647
648     if (typeof comparator == "function")
649         comparatorSort(array, comparator);
650     else
651         stringSort(array);
652
653     return array;
654 }
655
656 function concatSlowPath()
657 {
658     "use strict";
659
660     if (this == null)
661         throw new @TypeError("Array.prototype.concat requires that |this| not be null or undefined");
662
663     var currentElement = @Object(this);
664
665     var constructor;
666     if (@isArray(currentElement)) {
667         constructor = currentElement.constructor;
668         // We have this check so that if some array from a different global object
669         // calls this map they don't get an array with the Array.prototype of the
670         // other global object.
671         if (@isArrayConstructor(constructor) && @Array !== constructor)
672             constructor = @undefined;
673         else if (@isObject(constructor)) {
674             constructor = constructor.@speciesSymbol;
675             if (constructor === null)
676                 constructor = @Array;
677         }
678     }
679
680     var argCount = arguments.length;
681     var result;
682     if (constructor === @Array || constructor === @undefined)
683         result = [];
684     else
685         result = new constructor(0);
686     var resultIsArray = @isJSArray(result);
687
688     var resultIndex = 0;
689     var argIndex = 0;
690
691     do {
692         let spreadable = @isObject(currentElement) && currentElement.@isConcatSpreadableSymbol;
693         if ((spreadable === @undefined && @isArray(currentElement)) || spreadable) {
694             let length = @toLength(currentElement.length);
695             if (resultIsArray && @isJSArray(currentElement)) {
696                 @appendMemcpy(result, currentElement, resultIndex);
697                 resultIndex += length;
698             } else {
699                 if (length + resultIndex > @MAX_SAFE_INTEGER)
700                     throw @TypeError("length exceeded the maximum safe integer");
701                 for (var i = 0; i < length; i++) {
702                     if (i in currentElement)
703                         @putByValDirect(result, resultIndex, currentElement[i]);
704                     resultIndex++;
705                 }
706             }
707         } else {
708             if (resultIndex >= @MAX_SAFE_INTEGER)
709                 throw @TypeError("length exceeded the maximum safe integer");
710             @putByValDirect(result, resultIndex++, currentElement);
711         }
712         currentElement = arguments[argIndex];
713     } while (argIndex++ < argCount);
714
715     result.length = resultIndex;
716     return result;
717 }
718
719 function concat(first)
720 {
721     "use strict";
722
723     if (@argumentCount() === 1
724         && @isJSArray(this)
725         && this.@isConcatSpreadableSymbol === @undefined
726         && (!@isObject(first) || first.@isConcatSpreadableSymbol === @undefined)) {
727
728         let result = @concatMemcpy(this, first);
729         if (result !== null)
730             return result;
731     }
732
733     return @tailCallForwardArguments(@concatSlowPath, this);
734 }
735
736 function copyWithin(target, start /*, end */)
737 {
738     "use strict";
739
740     function maxWithPositives(a, b)
741     {
742         return (a < b) ? b : a;
743     }
744
745     function minWithMaybeNegativeZeroAndPositive(maybeNegativeZero, positive)
746     {
747         return (maybeNegativeZero < positive) ? maybeNegativeZero : positive;
748     }
749
750     if (this == null)
751         throw new @TypeError("Array.copyWithin requires that |this| not be null or undefined");
752
753     var array = @Object(this);
754     var length = @toLength(array.length);
755
756     var relativeTarget = @toInteger(target);
757     var to = (relativeTarget < 0) ? maxWithPositives(length + relativeTarget, 0) : minWithMaybeNegativeZeroAndPositive(relativeTarget, length);
758
759     var relativeStart = @toInteger(start);
760     var from = (relativeStart < 0) ? maxWithPositives(length + relativeStart, 0) : minWithMaybeNegativeZeroAndPositive(relativeStart, length);
761
762     var relativeEnd;
763     if (arguments.length >= 3) {
764         var end = arguments[2];
765         if (end === @undefined)
766             relativeEnd = length;
767         else
768             relativeEnd = @toInteger(end);
769     } else
770         relativeEnd = length;
771
772     var finalValue = (relativeEnd < 0) ? maxWithPositives(length + relativeEnd, 0) : minWithMaybeNegativeZeroAndPositive(relativeEnd, length);
773
774     var count = minWithMaybeNegativeZeroAndPositive(finalValue - from, length - to);
775
776     var direction = 1;
777     if (from < to && to < from + count) {
778         direction = -1;
779         from = from + count - 1;
780         to = to + count - 1;
781     }
782
783     for (var i = 0; i < count; ++i, from += direction, to += direction) {
784         if (from in array)
785             array[to] = array[from];
786         else
787             delete array[to];
788     }
789
790     return array;
791 }