OLD | NEW |
| (Empty) |
1 // Copyright 2012 the V8 project authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 (function(global, utils) { | |
6 | |
7 "use strict"; | |
8 | |
9 %CheckIsBootstrapping(); | |
10 | |
11 // ------------------------------------------------------------------- | |
12 // Imports | |
13 | |
14 var Delete; | |
15 var GlobalArray = global.Array; | |
16 var InternalArray = utils.InternalArray; | |
17 var InternalPackedArray = utils.InternalPackedArray; | |
18 var MathMin; | |
19 var ObjectHasOwnProperty; | |
20 var ObjectIsFrozen; | |
21 var ObjectIsSealed; | |
22 var ObjectToString; | |
23 var unscopablesSymbol = utils.ImportNow("unscopables_symbol"); | |
24 | |
25 utils.Import(function(from) { | |
26 Delete = from.Delete; | |
27 MathMin = from.MathMin; | |
28 ObjectHasOwnProperty = from.ObjectHasOwnProperty; | |
29 ObjectIsFrozen = from.ObjectIsFrozen; | |
30 ObjectIsSealed = from.ObjectIsSealed; | |
31 ObjectToString = from.ObjectToString; | |
32 }); | |
33 | |
34 // ------------------------------------------------------------------- | |
35 | |
36 // Global list of arrays visited during toString, toLocaleString and | |
37 // join invocations. | |
38 var visited_arrays = new InternalArray(); | |
39 | |
40 | |
41 // Gets a sorted array of array keys. Useful for operations on sparse | |
42 // arrays. Dupes have not been removed. | |
43 function GetSortedArrayKeys(array, indices) { | |
44 var keys = new InternalArray(); | |
45 if (IS_NUMBER(indices)) { | |
46 // It's an interval | |
47 var limit = indices; | |
48 for (var i = 0; i < limit; ++i) { | |
49 var e = array[i]; | |
50 if (!IS_UNDEFINED(e) || i in array) { | |
51 keys.push(i); | |
52 } | |
53 } | |
54 } else { | |
55 var length = indices.length; | |
56 for (var k = 0; k < length; ++k) { | |
57 var key = indices[k]; | |
58 if (!IS_UNDEFINED(key)) { | |
59 var e = array[key]; | |
60 if (!IS_UNDEFINED(e) || key in array) { | |
61 keys.push(key); | |
62 } | |
63 } | |
64 } | |
65 keys.sort(function(a, b) { return a - b; }); | |
66 } | |
67 return keys; | |
68 } | |
69 | |
70 | |
71 function SparseJoinWithSeparatorJS(array, len, convert, separator) { | |
72 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len)); | |
73 var totalLength = 0; | |
74 var elements = new InternalArray(keys.length * 2); | |
75 var previousKey = -1; | |
76 for (var i = 0; i < keys.length; i++) { | |
77 var key = keys[i]; | |
78 if (key != previousKey) { // keys may contain duplicates. | |
79 var e = array[key]; | |
80 if (!IS_STRING(e)) e = convert(e); | |
81 elements[i * 2] = key; | |
82 elements[i * 2 + 1] = e; | |
83 previousKey = key; | |
84 } | |
85 } | |
86 return %SparseJoinWithSeparator(elements, len, separator); | |
87 } | |
88 | |
89 | |
90 // Optimized for sparse arrays if separator is ''. | |
91 function SparseJoin(array, len, convert) { | |
92 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len)); | |
93 var last_key = -1; | |
94 var keys_length = keys.length; | |
95 | |
96 var elements = new InternalArray(keys_length); | |
97 var elements_length = 0; | |
98 | |
99 for (var i = 0; i < keys_length; i++) { | |
100 var key = keys[i]; | |
101 if (key != last_key) { | |
102 var e = array[key]; | |
103 if (!IS_STRING(e)) e = convert(e); | |
104 elements[elements_length++] = e; | |
105 last_key = key; | |
106 } | |
107 } | |
108 return %StringBuilderConcat(elements, elements_length, ''); | |
109 } | |
110 | |
111 | |
112 function UseSparseVariant(array, length, is_array, touched) { | |
113 // Only use the sparse variant on arrays that are likely to be sparse and the | |
114 // number of elements touched in the operation is relatively small compared to | |
115 // the overall size of the array. | |
116 if (!is_array || length < 1000 || %IsObserved(array) || | |
117 %HasComplexElements(array)) { | |
118 return false; | |
119 } | |
120 if (!%_IsSmi(length)) { | |
121 return true; | |
122 } | |
123 var elements_threshold = length >> 2; // No more than 75% holes | |
124 var estimated_elements = %EstimateNumberOfElements(array); | |
125 return (estimated_elements < elements_threshold) && | |
126 (touched > estimated_elements * 4); | |
127 } | |
128 | |
129 | |
130 function Join(array, length, separator, convert) { | |
131 if (length == 0) return ''; | |
132 | |
133 var is_array = IS_ARRAY(array); | |
134 | |
135 if (is_array) { | |
136 // If the array is cyclic, return the empty string for already | |
137 // visited arrays. | |
138 if (!%PushIfAbsent(visited_arrays, array)) return ''; | |
139 } | |
140 | |
141 // Attempt to convert the elements. | |
142 try { | |
143 if (UseSparseVariant(array, length, is_array, length)) { | |
144 %NormalizeElements(array); | |
145 if (separator.length == 0) { | |
146 return SparseJoin(array, length, convert); | |
147 } else { | |
148 return SparseJoinWithSeparatorJS(array, length, convert, separator); | |
149 } | |
150 } | |
151 | |
152 // Fast case for one-element arrays. | |
153 if (length == 1) { | |
154 var e = array[0]; | |
155 if (IS_STRING(e)) return e; | |
156 return convert(e); | |
157 } | |
158 | |
159 // Construct an array for the elements. | |
160 var elements = new InternalArray(length); | |
161 | |
162 // We pull the empty separator check outside the loop for speed! | |
163 if (separator.length == 0) { | |
164 var elements_length = 0; | |
165 for (var i = 0; i < length; i++) { | |
166 var e = array[i]; | |
167 if (!IS_STRING(e)) e = convert(e); | |
168 elements[elements_length++] = e; | |
169 } | |
170 elements.length = elements_length; | |
171 var result = %_FastOneByteArrayJoin(elements, ''); | |
172 if (!IS_UNDEFINED(result)) return result; | |
173 return %StringBuilderConcat(elements, elements_length, ''); | |
174 } | |
175 // Non-empty separator case. | |
176 // If the first element is a number then use the heuristic that the | |
177 // remaining elements are also likely to be numbers. | |
178 if (!IS_NUMBER(array[0])) { | |
179 for (var i = 0; i < length; i++) { | |
180 var e = array[i]; | |
181 if (!IS_STRING(e)) e = convert(e); | |
182 elements[i] = e; | |
183 } | |
184 } else { | |
185 for (var i = 0; i < length; i++) { | |
186 var e = array[i]; | |
187 if (IS_NUMBER(e)) { | |
188 e = %_NumberToString(e); | |
189 } else if (!IS_STRING(e)) { | |
190 e = convert(e); | |
191 } | |
192 elements[i] = e; | |
193 } | |
194 } | |
195 var result = %_FastOneByteArrayJoin(elements, separator); | |
196 if (!IS_UNDEFINED(result)) return result; | |
197 | |
198 return %StringBuilderJoin(elements, length, separator); | |
199 } finally { | |
200 // Make sure to remove the last element of the visited array no | |
201 // matter what happens. | |
202 if (is_array) visited_arrays.length = visited_arrays.length - 1; | |
203 } | |
204 } | |
205 | |
206 | |
207 function ConvertToString(x) { | |
208 if (IS_NULL_OR_UNDEFINED(x)) { | |
209 return ''; | |
210 } else { | |
211 return TO_STRING(x); | |
212 } | |
213 } | |
214 | |
215 | |
216 function ConvertToLocaleString(e) { | |
217 if (IS_NULL_OR_UNDEFINED(e)) { | |
218 return ''; | |
219 } else { | |
220 return TO_STRING(e.toLocaleString()); | |
221 } | |
222 } | |
223 | |
224 | |
225 // This function implements the optimized splice implementation that can use | |
226 // special array operations to handle sparse arrays in a sensible fashion. | |
227 function SparseSlice(array, start_i, del_count, len, deleted_elements) { | |
228 // Move deleted elements to a new array (the return value from splice). | |
229 var indices = %GetArrayKeys(array, start_i + del_count); | |
230 if (IS_NUMBER(indices)) { | |
231 var limit = indices; | |
232 for (var i = start_i; i < limit; ++i) { | |
233 var current = array[i]; | |
234 if (!IS_UNDEFINED(current) || i in array) { | |
235 %AddElement(deleted_elements, i - start_i, current); | |
236 } | |
237 } | |
238 } else { | |
239 var length = indices.length; | |
240 for (var k = 0; k < length; ++k) { | |
241 var key = indices[k]; | |
242 if (!IS_UNDEFINED(key)) { | |
243 if (key >= start_i) { | |
244 var current = array[key]; | |
245 if (!IS_UNDEFINED(current) || key in array) { | |
246 %AddElement(deleted_elements, key - start_i, current); | |
247 } | |
248 } | |
249 } | |
250 } | |
251 } | |
252 } | |
253 | |
254 | |
255 // This function implements the optimized splice implementation that can use | |
256 // special array operations to handle sparse arrays in a sensible fashion. | |
257 function SparseMove(array, start_i, del_count, len, num_additional_args) { | |
258 // Bail out if no moving is necessary. | |
259 if (num_additional_args === del_count) return; | |
260 // Move data to new array. | |
261 var new_array = new InternalArray( | |
262 // Clamp array length to 2^32-1 to avoid early RangeError. | |
263 MathMin(len - del_count + num_additional_args, 0xffffffff)); | |
264 var big_indices; | |
265 var indices = %GetArrayKeys(array, len); | |
266 if (IS_NUMBER(indices)) { | |
267 var limit = indices; | |
268 for (var i = 0; i < start_i && i < limit; ++i) { | |
269 var current = array[i]; | |
270 if (!IS_UNDEFINED(current) || i in array) { | |
271 new_array[i] = current; | |
272 } | |
273 } | |
274 for (var i = start_i + del_count; i < limit; ++i) { | |
275 var current = array[i]; | |
276 if (!IS_UNDEFINED(current) || i in array) { | |
277 new_array[i - del_count + num_additional_args] = current; | |
278 } | |
279 } | |
280 } else { | |
281 var length = indices.length; | |
282 for (var k = 0; k < length; ++k) { | |
283 var key = indices[k]; | |
284 if (!IS_UNDEFINED(key)) { | |
285 if (key < start_i) { | |
286 var current = array[key]; | |
287 if (!IS_UNDEFINED(current) || key in array) { | |
288 new_array[key] = current; | |
289 } | |
290 } else if (key >= start_i + del_count) { | |
291 var current = array[key]; | |
292 if (!IS_UNDEFINED(current) || key in array) { | |
293 var new_key = key - del_count + num_additional_args; | |
294 new_array[new_key] = current; | |
295 if (new_key > 0xfffffffe) { | |
296 big_indices = big_indices || new InternalArray(); | |
297 big_indices.push(new_key); | |
298 } | |
299 } | |
300 } | |
301 } | |
302 } | |
303 } | |
304 // Move contents of new_array into this array | |
305 %MoveArrayContents(new_array, array); | |
306 // Add any moved values that aren't elements anymore. | |
307 if (!IS_UNDEFINED(big_indices)) { | |
308 var length = big_indices.length; | |
309 for (var i = 0; i < length; ++i) { | |
310 var key = big_indices[i]; | |
311 array[key] = new_array[key]; | |
312 } | |
313 } | |
314 } | |
315 | |
316 | |
317 // This is part of the old simple-minded splice. We are using it either | |
318 // because the receiver is not an array (so we have no choice) or because we | |
319 // know we are not deleting or moving a lot of elements. | |
320 function SimpleSlice(array, start_i, del_count, len, deleted_elements) { | |
321 var is_array = IS_ARRAY(array); | |
322 for (var i = 0; i < del_count; i++) { | |
323 var index = start_i + i; | |
324 if (HAS_INDEX(array, index, is_array)) { | |
325 var current = array[index]; | |
326 // The spec requires [[DefineOwnProperty]] here, %AddElement is close | |
327 // enough (in that it ignores the prototype). | |
328 %AddElement(deleted_elements, i, current); | |
329 } | |
330 } | |
331 } | |
332 | |
333 | |
334 function SimpleMove(array, start_i, del_count, len, num_additional_args) { | |
335 var is_array = IS_ARRAY(array); | |
336 if (num_additional_args !== del_count) { | |
337 // Move the existing elements after the elements to be deleted | |
338 // to the right position in the resulting array. | |
339 if (num_additional_args > del_count) { | |
340 for (var i = len - del_count; i > start_i; i--) { | |
341 var from_index = i + del_count - 1; | |
342 var to_index = i + num_additional_args - 1; | |
343 if (HAS_INDEX(array, from_index, is_array)) { | |
344 array[to_index] = array[from_index]; | |
345 } else { | |
346 delete array[to_index]; | |
347 } | |
348 } | |
349 } else { | |
350 for (var i = start_i; i < len - del_count; i++) { | |
351 var from_index = i + del_count; | |
352 var to_index = i + num_additional_args; | |
353 if (HAS_INDEX(array, from_index, is_array)) { | |
354 array[to_index] = array[from_index]; | |
355 } else { | |
356 delete array[to_index]; | |
357 } | |
358 } | |
359 for (var i = len; i > len - del_count + num_additional_args; i--) { | |
360 delete array[i - 1]; | |
361 } | |
362 } | |
363 } | |
364 } | |
365 | |
366 | |
367 // ------------------------------------------------------------------- | |
368 | |
369 | |
370 function ArrayToString() { | |
371 var array; | |
372 var func; | |
373 if (IS_ARRAY(this)) { | |
374 func = this.join; | |
375 if (func === ArrayJoin) { | |
376 return Join(this, this.length, ',', ConvertToString); | |
377 } | |
378 array = this; | |
379 } else { | |
380 array = TO_OBJECT(this); | |
381 func = array.join; | |
382 } | |
383 if (!IS_CALLABLE(func)) { | |
384 return %_CallFunction(array, ObjectToString); | |
385 } | |
386 return %_Call(func, array); | |
387 } | |
388 | |
389 | |
390 function InnerArrayToLocaleString(array, length) { | |
391 var len = TO_LENGTH_OR_UINT32(length); | |
392 if (len === 0) return ""; | |
393 return Join(array, len, ',', ConvertToLocaleString); | |
394 } | |
395 | |
396 | |
397 function ArrayToLocaleString() { | |
398 var array = TO_OBJECT(this); | |
399 var arrayLen = array.length; | |
400 return InnerArrayToLocaleString(array, arrayLen); | |
401 } | |
402 | |
403 | |
404 function InnerArrayJoin(separator, array, length) { | |
405 if (IS_UNDEFINED(separator)) { | |
406 separator = ','; | |
407 } else { | |
408 separator = TO_STRING(separator); | |
409 } | |
410 | |
411 var result = %_FastOneByteArrayJoin(array, separator); | |
412 if (!IS_UNDEFINED(result)) return result; | |
413 | |
414 // Fast case for one-element arrays. | |
415 if (length === 1) { | |
416 var e = array[0]; | |
417 if (IS_NULL_OR_UNDEFINED(e)) return ''; | |
418 return TO_STRING(e); | |
419 } | |
420 | |
421 return Join(array, length, separator, ConvertToString); | |
422 } | |
423 | |
424 | |
425 function ArrayJoin(separator) { | |
426 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.join"); | |
427 | |
428 var array = TO_OBJECT(this); | |
429 var length = TO_LENGTH_OR_UINT32(array.length); | |
430 | |
431 return InnerArrayJoin(separator, array, length); | |
432 } | |
433 | |
434 | |
435 function ObservedArrayPop(n) { | |
436 n--; | |
437 var value = this[n]; | |
438 | |
439 try { | |
440 $observeBeginPerformSplice(this); | |
441 delete this[n]; | |
442 this.length = n; | |
443 } finally { | |
444 $observeEndPerformSplice(this); | |
445 $observeEnqueueSpliceRecord(this, n, [value], 0); | |
446 } | |
447 | |
448 return value; | |
449 } | |
450 | |
451 | |
452 // Removes the last element from the array and returns it. See | |
453 // ECMA-262, section 15.4.4.6. | |
454 function ArrayPop() { | |
455 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.pop"); | |
456 | |
457 var array = TO_OBJECT(this); | |
458 var n = TO_LENGTH_OR_UINT32(array.length); | |
459 if (n == 0) { | |
460 array.length = n; | |
461 return; | |
462 } | |
463 | |
464 if (%IsObserved(array)) | |
465 return ObservedArrayPop.call(array, n); | |
466 | |
467 n--; | |
468 var value = array[n]; | |
469 Delete(array, n, true); | |
470 array.length = n; | |
471 return value; | |
472 } | |
473 | |
474 | |
475 function ObservedArrayPush() { | |
476 var n = TO_LENGTH_OR_UINT32(this.length); | |
477 var m = %_ArgumentsLength(); | |
478 | |
479 try { | |
480 $observeBeginPerformSplice(this); | |
481 for (var i = 0; i < m; i++) { | |
482 this[i+n] = %_Arguments(i); | |
483 } | |
484 var new_length = n + m; | |
485 this.length = new_length; | |
486 } finally { | |
487 $observeEndPerformSplice(this); | |
488 $observeEnqueueSpliceRecord(this, n, [], m); | |
489 } | |
490 | |
491 return new_length; | |
492 } | |
493 | |
494 | |
495 // Appends the arguments to the end of the array and returns the new | |
496 // length of the array. See ECMA-262, section 15.4.4.7. | |
497 function ArrayPush() { | |
498 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.push"); | |
499 | |
500 if (%IsObserved(this)) | |
501 return ObservedArrayPush.apply(this, arguments); | |
502 | |
503 var array = TO_OBJECT(this); | |
504 var n = TO_LENGTH_OR_UINT32(array.length); | |
505 var m = %_ArgumentsLength(); | |
506 | |
507 for (var i = 0; i < m; i++) { | |
508 array[i+n] = %_Arguments(i); | |
509 } | |
510 | |
511 var new_length = n + m; | |
512 array.length = new_length; | |
513 return new_length; | |
514 } | |
515 | |
516 | |
517 // For implementing reverse() on large, sparse arrays. | |
518 function SparseReverse(array, len) { | |
519 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len)); | |
520 var high_counter = keys.length - 1; | |
521 var low_counter = 0; | |
522 while (low_counter <= high_counter) { | |
523 var i = keys[low_counter]; | |
524 var j = keys[high_counter]; | |
525 | |
526 var j_complement = len - j - 1; | |
527 var low, high; | |
528 | |
529 if (j_complement <= i) { | |
530 high = j; | |
531 while (keys[--high_counter] == j) { } | |
532 low = j_complement; | |
533 } | |
534 if (j_complement >= i) { | |
535 low = i; | |
536 while (keys[++low_counter] == i) { } | |
537 high = len - i - 1; | |
538 } | |
539 | |
540 var current_i = array[low]; | |
541 if (!IS_UNDEFINED(current_i) || low in array) { | |
542 var current_j = array[high]; | |
543 if (!IS_UNDEFINED(current_j) || high in array) { | |
544 array[low] = current_j; | |
545 array[high] = current_i; | |
546 } else { | |
547 array[high] = current_i; | |
548 delete array[low]; | |
549 } | |
550 } else { | |
551 var current_j = array[high]; | |
552 if (!IS_UNDEFINED(current_j) || high in array) { | |
553 array[low] = current_j; | |
554 delete array[high]; | |
555 } | |
556 } | |
557 } | |
558 } | |
559 | |
560 function PackedArrayReverse(array, len) { | |
561 var j = len - 1; | |
562 for (var i = 0; i < j; i++, j--) { | |
563 var current_i = array[i]; | |
564 var current_j = array[j]; | |
565 array[i] = current_j; | |
566 array[j] = current_i; | |
567 } | |
568 return array; | |
569 } | |
570 | |
571 | |
572 function GenericArrayReverse(array, len) { | |
573 var j = len - 1; | |
574 for (var i = 0; i < j; i++, j--) { | |
575 if (i in array) { | |
576 var current_i = array[i]; | |
577 if (j in array) { | |
578 var current_j = array[j]; | |
579 array[i] = current_j; | |
580 array[j] = current_i; | |
581 } else { | |
582 array[j] = current_i; | |
583 delete array[i]; | |
584 } | |
585 } else { | |
586 if (j in array) { | |
587 var current_j = array[j]; | |
588 array[i] = current_j; | |
589 delete array[j]; | |
590 } | |
591 } | |
592 } | |
593 return array; | |
594 } | |
595 | |
596 | |
597 function ArrayReverse() { | |
598 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reverse"); | |
599 | |
600 var array = TO_OBJECT(this); | |
601 var len = TO_LENGTH_OR_UINT32(array.length); | |
602 var isArray = IS_ARRAY(array); | |
603 | |
604 if (UseSparseVariant(array, len, isArray, len)) { | |
605 %NormalizeElements(array); | |
606 SparseReverse(array, len); | |
607 return array; | |
608 } else if (isArray && %_HasFastPackedElements(array)) { | |
609 return PackedArrayReverse(array, len); | |
610 } else { | |
611 return GenericArrayReverse(array, len); | |
612 } | |
613 } | |
614 | |
615 | |
616 function ObservedArrayShift(len) { | |
617 var first = this[0]; | |
618 | |
619 try { | |
620 $observeBeginPerformSplice(this); | |
621 SimpleMove(this, 0, 1, len, 0); | |
622 this.length = len - 1; | |
623 } finally { | |
624 $observeEndPerformSplice(this); | |
625 $observeEnqueueSpliceRecord(this, 0, [first], 0); | |
626 } | |
627 | |
628 return first; | |
629 } | |
630 | |
631 | |
632 function ArrayShift() { | |
633 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.shift"); | |
634 | |
635 var array = TO_OBJECT(this); | |
636 var len = TO_LENGTH_OR_UINT32(array.length); | |
637 | |
638 if (len === 0) { | |
639 array.length = 0; | |
640 return; | |
641 } | |
642 | |
643 if (ObjectIsSealed(array)) throw MakeTypeError(kArrayFunctionsOnSealed); | |
644 | |
645 if (%IsObserved(array)) | |
646 return ObservedArrayShift.call(array, len); | |
647 | |
648 var first = array[0]; | |
649 | |
650 if (UseSparseVariant(array, len, IS_ARRAY(array), len)) { | |
651 SparseMove(array, 0, 1, len, 0); | |
652 } else { | |
653 SimpleMove(array, 0, 1, len, 0); | |
654 } | |
655 | |
656 array.length = len - 1; | |
657 | |
658 return first; | |
659 } | |
660 | |
661 | |
662 function ObservedArrayUnshift() { | |
663 var len = TO_LENGTH_OR_UINT32(this.length); | |
664 var num_arguments = %_ArgumentsLength(); | |
665 | |
666 try { | |
667 $observeBeginPerformSplice(this); | |
668 SimpleMove(this, 0, 0, len, num_arguments); | |
669 for (var i = 0; i < num_arguments; i++) { | |
670 this[i] = %_Arguments(i); | |
671 } | |
672 var new_length = len + num_arguments; | |
673 this.length = new_length; | |
674 } finally { | |
675 $observeEndPerformSplice(this); | |
676 $observeEnqueueSpliceRecord(this, 0, [], num_arguments); | |
677 } | |
678 | |
679 return new_length; | |
680 } | |
681 | |
682 | |
683 function ArrayUnshift(arg1) { // length == 1 | |
684 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.unshift"); | |
685 | |
686 if (%IsObserved(this)) | |
687 return ObservedArrayUnshift.apply(this, arguments); | |
688 | |
689 var array = TO_OBJECT(this); | |
690 var len = TO_LENGTH_OR_UINT32(array.length); | |
691 var num_arguments = %_ArgumentsLength(); | |
692 | |
693 if (len > 0 && UseSparseVariant(array, len, IS_ARRAY(array), len) && | |
694 !ObjectIsSealed(array)) { | |
695 SparseMove(array, 0, 0, len, num_arguments); | |
696 } else { | |
697 SimpleMove(array, 0, 0, len, num_arguments); | |
698 } | |
699 | |
700 for (var i = 0; i < num_arguments; i++) { | |
701 array[i] = %_Arguments(i); | |
702 } | |
703 | |
704 var new_length = len + num_arguments; | |
705 array.length = new_length; | |
706 return new_length; | |
707 } | |
708 | |
709 | |
710 function ArraySlice(start, end) { | |
711 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.slice"); | |
712 | |
713 var array = TO_OBJECT(this); | |
714 var len = TO_LENGTH_OR_UINT32(array.length); | |
715 var start_i = TO_INTEGER(start); | |
716 var end_i = len; | |
717 | |
718 if (!IS_UNDEFINED(end)) end_i = TO_INTEGER(end); | |
719 | |
720 if (start_i < 0) { | |
721 start_i += len; | |
722 if (start_i < 0) start_i = 0; | |
723 } else { | |
724 if (start_i > len) start_i = len; | |
725 } | |
726 | |
727 if (end_i < 0) { | |
728 end_i += len; | |
729 if (end_i < 0) end_i = 0; | |
730 } else { | |
731 if (end_i > len) end_i = len; | |
732 } | |
733 | |
734 var result = []; | |
735 | |
736 if (end_i < start_i) return result; | |
737 | |
738 if (UseSparseVariant(array, len, IS_ARRAY(array), end_i - start_i)) { | |
739 %NormalizeElements(array); | |
740 %NormalizeElements(result); | |
741 SparseSlice(array, start_i, end_i - start_i, len, result); | |
742 } else { | |
743 SimpleSlice(array, start_i, end_i - start_i, len, result); | |
744 } | |
745 | |
746 result.length = end_i - start_i; | |
747 | |
748 return result; | |
749 } | |
750 | |
751 | |
752 function ComputeSpliceStartIndex(start_i, len) { | |
753 if (start_i < 0) { | |
754 start_i += len; | |
755 return start_i < 0 ? 0 : start_i; | |
756 } | |
757 | |
758 return start_i > len ? len : start_i; | |
759 } | |
760 | |
761 | |
762 function ComputeSpliceDeleteCount(delete_count, num_arguments, len, start_i) { | |
763 // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is | |
764 // given as a request to delete all the elements from the start. | |
765 // And it differs from the case of undefined delete count. | |
766 // This does not follow ECMA-262, but we do the same for | |
767 // compatibility. | |
768 var del_count = 0; | |
769 if (num_arguments == 1) | |
770 return len - start_i; | |
771 | |
772 del_count = TO_INTEGER(delete_count); | |
773 if (del_count < 0) | |
774 return 0; | |
775 | |
776 if (del_count > len - start_i) | |
777 return len - start_i; | |
778 | |
779 return del_count; | |
780 } | |
781 | |
782 | |
783 function ObservedArraySplice(start, delete_count) { | |
784 var num_arguments = %_ArgumentsLength(); | |
785 var len = TO_LENGTH_OR_UINT32(this.length); | |
786 var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len); | |
787 var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len, | |
788 start_i); | |
789 var deleted_elements = []; | |
790 deleted_elements.length = del_count; | |
791 var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0; | |
792 | |
793 try { | |
794 $observeBeginPerformSplice(this); | |
795 | |
796 SimpleSlice(this, start_i, del_count, len, deleted_elements); | |
797 SimpleMove(this, start_i, del_count, len, num_elements_to_add); | |
798 | |
799 // Insert the arguments into the resulting array in | |
800 // place of the deleted elements. | |
801 var i = start_i; | |
802 var arguments_index = 2; | |
803 var arguments_length = %_ArgumentsLength(); | |
804 while (arguments_index < arguments_length) { | |
805 this[i++] = %_Arguments(arguments_index++); | |
806 } | |
807 this.length = len - del_count + num_elements_to_add; | |
808 | |
809 } finally { | |
810 $observeEndPerformSplice(this); | |
811 if (deleted_elements.length || num_elements_to_add) { | |
812 $observeEnqueueSpliceRecord(this, | |
813 start_i, | |
814 deleted_elements.slice(), | |
815 num_elements_to_add); | |
816 } | |
817 } | |
818 | |
819 // Return the deleted elements. | |
820 return deleted_elements; | |
821 } | |
822 | |
823 | |
824 function ArraySplice(start, delete_count) { | |
825 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.splice"); | |
826 | |
827 if (%IsObserved(this)) | |
828 return ObservedArraySplice.apply(this, arguments); | |
829 | |
830 var num_arguments = %_ArgumentsLength(); | |
831 var array = TO_OBJECT(this); | |
832 var len = TO_LENGTH_OR_UINT32(array.length); | |
833 var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len); | |
834 var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len, | |
835 start_i); | |
836 var deleted_elements = []; | |
837 deleted_elements.length = del_count; | |
838 var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0; | |
839 | |
840 if (del_count != num_elements_to_add && ObjectIsSealed(array)) { | |
841 throw MakeTypeError(kArrayFunctionsOnSealed); | |
842 } else if (del_count > 0 && ObjectIsFrozen(array)) { | |
843 throw MakeTypeError(kArrayFunctionsOnFrozen); | |
844 } | |
845 | |
846 var changed_elements = del_count; | |
847 if (num_elements_to_add != del_count) { | |
848 // If the slice needs to do a actually move elements after the insertion | |
849 // point, then include those in the estimate of changed elements. | |
850 changed_elements += len - start_i - del_count; | |
851 } | |
852 if (UseSparseVariant(array, len, IS_ARRAY(array), changed_elements)) { | |
853 %NormalizeElements(array); | |
854 %NormalizeElements(deleted_elements); | |
855 SparseSlice(array, start_i, del_count, len, deleted_elements); | |
856 SparseMove(array, start_i, del_count, len, num_elements_to_add); | |
857 } else { | |
858 SimpleSlice(array, start_i, del_count, len, deleted_elements); | |
859 SimpleMove(array, start_i, del_count, len, num_elements_to_add); | |
860 } | |
861 | |
862 // Insert the arguments into the resulting array in | |
863 // place of the deleted elements. | |
864 var i = start_i; | |
865 var arguments_index = 2; | |
866 var arguments_length = %_ArgumentsLength(); | |
867 while (arguments_index < arguments_length) { | |
868 array[i++] = %_Arguments(arguments_index++); | |
869 } | |
870 array.length = len - del_count + num_elements_to_add; | |
871 | |
872 // Return the deleted elements. | |
873 return deleted_elements; | |
874 } | |
875 | |
876 | |
877 function InnerArraySort(array, length, comparefn) { | |
878 // In-place QuickSort algorithm. | |
879 // For short (length <= 22) arrays, insertion sort is used for efficiency. | |
880 | |
881 if (!IS_CALLABLE(comparefn)) { | |
882 comparefn = function (x, y) { | |
883 if (x === y) return 0; | |
884 if (%_IsSmi(x) && %_IsSmi(y)) { | |
885 return %SmiLexicographicCompare(x, y); | |
886 } | |
887 x = TO_STRING(x); | |
888 y = TO_STRING(y); | |
889 if (x == y) return 0; | |
890 else return x < y ? -1 : 1; | |
891 }; | |
892 } | |
893 var InsertionSort = function InsertionSort(a, from, to) { | |
894 for (var i = from + 1; i < to; i++) { | |
895 var element = a[i]; | |
896 for (var j = i - 1; j >= from; j--) { | |
897 var tmp = a[j]; | |
898 var order = comparefn(tmp, element); | |
899 if (order > 0) { | |
900 a[j + 1] = tmp; | |
901 } else { | |
902 break; | |
903 } | |
904 } | |
905 a[j + 1] = element; | |
906 } | |
907 }; | |
908 | |
909 var GetThirdIndex = function(a, from, to) { | |
910 var t_array = new InternalArray(); | |
911 // Use both 'from' and 'to' to determine the pivot candidates. | |
912 var increment = 200 + ((to - from) & 15); | |
913 var j = 0; | |
914 from += 1; | |
915 to -= 1; | |
916 for (var i = from; i < to; i += increment) { | |
917 t_array[j] = [i, a[i]]; | |
918 j++; | |
919 } | |
920 t_array.sort(function(a, b) { | |
921 return comparefn(a[1], b[1]); | |
922 }); | |
923 var third_index = t_array[t_array.length >> 1][0]; | |
924 return third_index; | |
925 } | |
926 | |
927 var QuickSort = function QuickSort(a, from, to) { | |
928 var third_index = 0; | |
929 while (true) { | |
930 // Insertion sort is faster for short arrays. | |
931 if (to - from <= 10) { | |
932 InsertionSort(a, from, to); | |
933 return; | |
934 } | |
935 if (to - from > 1000) { | |
936 third_index = GetThirdIndex(a, from, to); | |
937 } else { | |
938 third_index = from + ((to - from) >> 1); | |
939 } | |
940 // Find a pivot as the median of first, last and middle element. | |
941 var v0 = a[from]; | |
942 var v1 = a[to - 1]; | |
943 var v2 = a[third_index]; | |
944 var c01 = comparefn(v0, v1); | |
945 if (c01 > 0) { | |
946 // v1 < v0, so swap them. | |
947 var tmp = v0; | |
948 v0 = v1; | |
949 v1 = tmp; | |
950 } // v0 <= v1. | |
951 var c02 = comparefn(v0, v2); | |
952 if (c02 >= 0) { | |
953 // v2 <= v0 <= v1. | |
954 var tmp = v0; | |
955 v0 = v2; | |
956 v2 = v1; | |
957 v1 = tmp; | |
958 } else { | |
959 // v0 <= v1 && v0 < v2 | |
960 var c12 = comparefn(v1, v2); | |
961 if (c12 > 0) { | |
962 // v0 <= v2 < v1 | |
963 var tmp = v1; | |
964 v1 = v2; | |
965 v2 = tmp; | |
966 } | |
967 } | |
968 // v0 <= v1 <= v2 | |
969 a[from] = v0; | |
970 a[to - 1] = v2; | |
971 var pivot = v1; | |
972 var low_end = from + 1; // Upper bound of elements lower than pivot. | |
973 var high_start = to - 1; // Lower bound of elements greater than pivot. | |
974 a[third_index] = a[low_end]; | |
975 a[low_end] = pivot; | |
976 | |
977 // From low_end to i are elements equal to pivot. | |
978 // From i to high_start are elements that haven't been compared yet. | |
979 partition: for (var i = low_end + 1; i < high_start; i++) { | |
980 var element = a[i]; | |
981 var order = comparefn(element, pivot); | |
982 if (order < 0) { | |
983 a[i] = a[low_end]; | |
984 a[low_end] = element; | |
985 low_end++; | |
986 } else if (order > 0) { | |
987 do { | |
988 high_start--; | |
989 if (high_start == i) break partition; | |
990 var top_elem = a[high_start]; | |
991 order = comparefn(top_elem, pivot); | |
992 } while (order > 0); | |
993 a[i] = a[high_start]; | |
994 a[high_start] = element; | |
995 if (order < 0) { | |
996 element = a[i]; | |
997 a[i] = a[low_end]; | |
998 a[low_end] = element; | |
999 low_end++; | |
1000 } | |
1001 } | |
1002 } | |
1003 if (to - high_start < low_end - from) { | |
1004 QuickSort(a, high_start, to); | |
1005 to = low_end; | |
1006 } else { | |
1007 QuickSort(a, from, low_end); | |
1008 from = high_start; | |
1009 } | |
1010 } | |
1011 }; | |
1012 | |
1013 // Copy elements in the range 0..length from obj's prototype chain | |
1014 // to obj itself, if obj has holes. Return one more than the maximal index | |
1015 // of a prototype property. | |
1016 var CopyFromPrototype = function CopyFromPrototype(obj, length) { | |
1017 var max = 0; | |
1018 for (var proto = %_GetPrototype(obj); proto; proto = %_GetPrototype(proto))
{ | |
1019 var indices = %GetArrayKeys(proto, length); | |
1020 if (IS_NUMBER(indices)) { | |
1021 // It's an interval. | |
1022 var proto_length = indices; | |
1023 for (var i = 0; i < proto_length; i++) { | |
1024 if (!HAS_OWN_PROPERTY(obj, i) && HAS_OWN_PROPERTY(proto, i)) { | |
1025 obj[i] = proto[i]; | |
1026 if (i >= max) { max = i + 1; } | |
1027 } | |
1028 } | |
1029 } else { | |
1030 for (var i = 0; i < indices.length; i++) { | |
1031 var index = indices[i]; | |
1032 if (!IS_UNDEFINED(index) && !HAS_OWN_PROPERTY(obj, index) | |
1033 && HAS_OWN_PROPERTY(proto, index)) { | |
1034 obj[index] = proto[index]; | |
1035 if (index >= max) { max = index + 1; } | |
1036 } | |
1037 } | |
1038 } | |
1039 } | |
1040 return max; | |
1041 }; | |
1042 | |
1043 // Set a value of "undefined" on all indices in the range from..to | |
1044 // where a prototype of obj has an element. I.e., shadow all prototype | |
1045 // elements in that range. | |
1046 var ShadowPrototypeElements = function(obj, from, to) { | |
1047 for (var proto = %_GetPrototype(obj); proto; proto = %_GetPrototype(proto))
{ | |
1048 var indices = %GetArrayKeys(proto, to); | |
1049 if (IS_NUMBER(indices)) { | |
1050 // It's an interval. | |
1051 var proto_length = indices; | |
1052 for (var i = from; i < proto_length; i++) { | |
1053 if (HAS_OWN_PROPERTY(proto, i)) { | |
1054 obj[i] = UNDEFINED; | |
1055 } | |
1056 } | |
1057 } else { | |
1058 for (var i = 0; i < indices.length; i++) { | |
1059 var index = indices[i]; | |
1060 if (!IS_UNDEFINED(index) && from <= index && | |
1061 HAS_OWN_PROPERTY(proto, index)) { | |
1062 obj[index] = UNDEFINED; | |
1063 } | |
1064 } | |
1065 } | |
1066 } | |
1067 }; | |
1068 | |
1069 var SafeRemoveArrayHoles = function SafeRemoveArrayHoles(obj) { | |
1070 // Copy defined elements from the end to fill in all holes and undefineds | |
1071 // in the beginning of the array. Write undefineds and holes at the end | |
1072 // after loop is finished. | |
1073 var first_undefined = 0; | |
1074 var last_defined = length - 1; | |
1075 var num_holes = 0; | |
1076 while (first_undefined < last_defined) { | |
1077 // Find first undefined element. | |
1078 while (first_undefined < last_defined && | |
1079 !IS_UNDEFINED(obj[first_undefined])) { | |
1080 first_undefined++; | |
1081 } | |
1082 // Maintain the invariant num_holes = the number of holes in the original | |
1083 // array with indices <= first_undefined or > last_defined. | |
1084 if (!HAS_OWN_PROPERTY(obj, first_undefined)) { | |
1085 num_holes++; | |
1086 } | |
1087 | |
1088 // Find last defined element. | |
1089 while (first_undefined < last_defined && | |
1090 IS_UNDEFINED(obj[last_defined])) { | |
1091 if (!HAS_OWN_PROPERTY(obj, last_defined)) { | |
1092 num_holes++; | |
1093 } | |
1094 last_defined--; | |
1095 } | |
1096 if (first_undefined < last_defined) { | |
1097 // Fill in hole or undefined. | |
1098 obj[first_undefined] = obj[last_defined]; | |
1099 obj[last_defined] = UNDEFINED; | |
1100 } | |
1101 } | |
1102 // If there were any undefineds in the entire array, first_undefined | |
1103 // points to one past the last defined element. Make this true if | |
1104 // there were no undefineds, as well, so that first_undefined == number | |
1105 // of defined elements. | |
1106 if (!IS_UNDEFINED(obj[first_undefined])) first_undefined++; | |
1107 // Fill in the undefineds and the holes. There may be a hole where | |
1108 // an undefined should be and vice versa. | |
1109 var i; | |
1110 for (i = first_undefined; i < length - num_holes; i++) { | |
1111 obj[i] = UNDEFINED; | |
1112 } | |
1113 for (i = length - num_holes; i < length; i++) { | |
1114 // For compatability with Webkit, do not expose elements in the prototype. | |
1115 if (i in %_GetPrototype(obj)) { | |
1116 obj[i] = UNDEFINED; | |
1117 } else { | |
1118 delete obj[i]; | |
1119 } | |
1120 } | |
1121 | |
1122 // Return the number of defined elements. | |
1123 return first_undefined; | |
1124 }; | |
1125 | |
1126 if (length < 2) return array; | |
1127 | |
1128 var is_array = IS_ARRAY(array); | |
1129 var max_prototype_element; | |
1130 if (!is_array) { | |
1131 // For compatibility with JSC, we also sort elements inherited from | |
1132 // the prototype chain on non-Array objects. | |
1133 // We do this by copying them to this object and sorting only | |
1134 // own elements. This is not very efficient, but sorting with | |
1135 // inherited elements happens very, very rarely, if at all. | |
1136 // The specification allows "implementation dependent" behavior | |
1137 // if an element on the prototype chain has an element that | |
1138 // might interact with sorting. | |
1139 max_prototype_element = CopyFromPrototype(array, length); | |
1140 } | |
1141 | |
1142 // %RemoveArrayHoles returns -1 if fast removal is not supported. | |
1143 var num_non_undefined = %RemoveArrayHoles(array, length); | |
1144 | |
1145 if (num_non_undefined == -1) { | |
1146 // The array is observed, or there were indexed accessors in the array. | |
1147 // Move array holes and undefineds to the end using a Javascript function | |
1148 // that is safe in the presence of accessors and is observable. | |
1149 num_non_undefined = SafeRemoveArrayHoles(array); | |
1150 } | |
1151 | |
1152 QuickSort(array, 0, num_non_undefined); | |
1153 | |
1154 if (!is_array && (num_non_undefined + 1 < max_prototype_element)) { | |
1155 // For compatibility with JSC, we shadow any elements in the prototype | |
1156 // chain that has become exposed by sort moving a hole to its position. | |
1157 ShadowPrototypeElements(array, num_non_undefined, max_prototype_element); | |
1158 } | |
1159 | |
1160 return array; | |
1161 } | |
1162 | |
1163 | |
1164 function ArraySort(comparefn) { | |
1165 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort"); | |
1166 | |
1167 var array = TO_OBJECT(this); | |
1168 var length = TO_LENGTH_OR_UINT32(array.length); | |
1169 return InnerArraySort(array, length, comparefn); | |
1170 } | |
1171 | |
1172 | |
1173 // The following functions cannot be made efficient on sparse arrays while | |
1174 // preserving the semantics, since the calls to the receiver function can add | |
1175 // or delete elements from the array. | |
1176 function InnerArrayFilter(f, receiver, array, length) { | |
1177 if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f); | |
1178 | |
1179 var accumulator = new InternalArray(); | |
1180 var accumulator_length = 0; | |
1181 var is_array = IS_ARRAY(array); | |
1182 var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f); | |
1183 for (var i = 0; i < length; i++) { | |
1184 if (HAS_INDEX(array, i, is_array)) { | |
1185 var element = array[i]; | |
1186 // Prepare break slots for debugger step in. | |
1187 if (stepping) %DebugPrepareStepInIfStepping(f); | |
1188 if (%_Call(f, receiver, element, i, array)) { | |
1189 accumulator[accumulator_length++] = element; | |
1190 } | |
1191 } | |
1192 } | |
1193 return accumulator; | |
1194 } | |
1195 | |
1196 function ArrayFilter(f, receiver) { | |
1197 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.filter"); | |
1198 | |
1199 // Pull out the length so that modifications to the length in the | |
1200 // loop will not affect the looping and side effects are visible. | |
1201 var array = TO_OBJECT(this); | |
1202 var length = TO_LENGTH_OR_UINT32(array.length); | |
1203 var accumulator = InnerArrayFilter(f, receiver, array, length); | |
1204 var result = new GlobalArray(); | |
1205 %MoveArrayContents(accumulator, result); | |
1206 return result; | |
1207 } | |
1208 | |
1209 function InnerArrayForEach(f, receiver, array, length) { | |
1210 if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f); | |
1211 | |
1212 var is_array = IS_ARRAY(array); | |
1213 var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f); | |
1214 for (var i = 0; i < length; i++) { | |
1215 if (HAS_INDEX(array, i, is_array)) { | |
1216 var element = array[i]; | |
1217 // Prepare break slots for debugger step in. | |
1218 if (stepping) %DebugPrepareStepInIfStepping(f); | |
1219 %_Call(f, receiver, element, i, array); | |
1220 } | |
1221 } | |
1222 } | |
1223 | |
1224 function ArrayForEach(f, receiver) { | |
1225 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.forEach"); | |
1226 | |
1227 // Pull out the length so that modifications to the length in the | |
1228 // loop will not affect the looping and side effects are visible. | |
1229 var array = TO_OBJECT(this); | |
1230 var length = TO_LENGTH_OR_UINT32(array.length); | |
1231 InnerArrayForEach(f, receiver, array, length); | |
1232 } | |
1233 | |
1234 | |
1235 function InnerArraySome(f, receiver, array, length) { | |
1236 if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f); | |
1237 | |
1238 var is_array = IS_ARRAY(array); | |
1239 var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f); | |
1240 for (var i = 0; i < length; i++) { | |
1241 if (HAS_INDEX(array, i, is_array)) { | |
1242 var element = array[i]; | |
1243 // Prepare break slots for debugger step in. | |
1244 if (stepping) %DebugPrepareStepInIfStepping(f); | |
1245 if (%_Call(f, receiver, element, i, array)) return true; | |
1246 } | |
1247 } | |
1248 return false; | |
1249 } | |
1250 | |
1251 | |
1252 // Executes the function once for each element present in the | |
1253 // array until it finds one where callback returns true. | |
1254 function ArraySome(f, receiver) { | |
1255 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.some"); | |
1256 | |
1257 // Pull out the length so that modifications to the length in the | |
1258 // loop will not affect the looping and side effects are visible. | |
1259 var array = TO_OBJECT(this); | |
1260 var length = TO_LENGTH_OR_UINT32(array.length); | |
1261 return InnerArraySome(f, receiver, array, length); | |
1262 } | |
1263 | |
1264 | |
1265 function InnerArrayEvery(f, receiver, array, length) { | |
1266 if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f); | |
1267 | |
1268 var is_array = IS_ARRAY(array); | |
1269 var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f); | |
1270 for (var i = 0; i < length; i++) { | |
1271 if (HAS_INDEX(array, i, is_array)) { | |
1272 var element = array[i]; | |
1273 // Prepare break slots for debugger step in. | |
1274 if (stepping) %DebugPrepareStepInIfStepping(f); | |
1275 if (!%_Call(f, receiver, element, i, array)) return false; | |
1276 } | |
1277 } | |
1278 return true; | |
1279 } | |
1280 | |
1281 function ArrayEvery(f, receiver) { | |
1282 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.every"); | |
1283 | |
1284 // Pull out the length so that modifications to the length in the | |
1285 // loop will not affect the looping and side effects are visible. | |
1286 var array = TO_OBJECT(this); | |
1287 var length = TO_LENGTH_OR_UINT32(array.length); | |
1288 return InnerArrayEvery(f, receiver, array, length); | |
1289 } | |
1290 | |
1291 | |
1292 function InnerArrayMap(f, receiver, array, length) { | |
1293 if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f); | |
1294 | |
1295 var accumulator = new InternalArray(length); | |
1296 var is_array = IS_ARRAY(array); | |
1297 var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f); | |
1298 for (var i = 0; i < length; i++) { | |
1299 if (HAS_INDEX(array, i, is_array)) { | |
1300 var element = array[i]; | |
1301 // Prepare break slots for debugger step in. | |
1302 if (stepping) %DebugPrepareStepInIfStepping(f); | |
1303 accumulator[i] = %_Call(f, receiver, element, i, array); | |
1304 } | |
1305 } | |
1306 return accumulator; | |
1307 } | |
1308 | |
1309 | |
1310 function ArrayMap(f, receiver) { | |
1311 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.map"); | |
1312 | |
1313 // Pull out the length so that modifications to the length in the | |
1314 // loop will not affect the looping and side effects are visible. | |
1315 var array = TO_OBJECT(this); | |
1316 var length = TO_LENGTH_OR_UINT32(array.length); | |
1317 var accumulator = InnerArrayMap(f, receiver, array, length); | |
1318 var result = new GlobalArray(); | |
1319 %MoveArrayContents(accumulator, result); | |
1320 return result; | |
1321 } | |
1322 | |
1323 | |
1324 // For .indexOf, we don't need to pass in the number of arguments | |
1325 // at the callsite since ToInteger(undefined) == 0; however, for | |
1326 // .lastIndexOf, we need to pass it, since the behavior for passing | |
1327 // undefined is 0 but for not including the argument is length-1. | |
1328 function InnerArrayIndexOf(array, element, index, length) { | |
1329 if (length == 0) return -1; | |
1330 if (IS_UNDEFINED(index)) { | |
1331 index = 0; | |
1332 } else { | |
1333 index = TO_INTEGER(index); | |
1334 // If index is negative, index from the end of the array. | |
1335 if (index < 0) { | |
1336 index = length + index; | |
1337 // If index is still negative, search the entire array. | |
1338 if (index < 0) index = 0; | |
1339 } | |
1340 } | |
1341 var min = index; | |
1342 var max = length; | |
1343 if (UseSparseVariant(array, length, IS_ARRAY(array), max - min)) { | |
1344 %NormalizeElements(array); | |
1345 var indices = %GetArrayKeys(array, length); | |
1346 if (IS_NUMBER(indices)) { | |
1347 // It's an interval. | |
1348 max = indices; // Capped by length already. | |
1349 // Fall through to loop below. | |
1350 } else { | |
1351 if (indices.length == 0) return -1; | |
1352 // Get all the keys in sorted order. | |
1353 var sortedKeys = GetSortedArrayKeys(array, indices); | |
1354 var n = sortedKeys.length; | |
1355 var i = 0; | |
1356 while (i < n && sortedKeys[i] < index) i++; | |
1357 while (i < n) { | |
1358 var key = sortedKeys[i]; | |
1359 if (!IS_UNDEFINED(key) && array[key] === element) return key; | |
1360 i++; | |
1361 } | |
1362 return -1; | |
1363 } | |
1364 } | |
1365 // Lookup through the array. | |
1366 if (!IS_UNDEFINED(element)) { | |
1367 for (var i = min; i < max; i++) { | |
1368 if (array[i] === element) return i; | |
1369 } | |
1370 return -1; | |
1371 } | |
1372 // Lookup through the array. | |
1373 for (var i = min; i < max; i++) { | |
1374 if (IS_UNDEFINED(array[i]) && i in array) { | |
1375 return i; | |
1376 } | |
1377 } | |
1378 return -1; | |
1379 } | |
1380 | |
1381 | |
1382 function ArrayIndexOf(element, index) { | |
1383 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.indexOf"); | |
1384 | |
1385 var length = TO_LENGTH_OR_UINT32(this.length); | |
1386 return InnerArrayIndexOf(this, element, index, length); | |
1387 } | |
1388 | |
1389 | |
1390 function InnerArrayLastIndexOf(array, element, index, length, argumentsLength) { | |
1391 if (length == 0) return -1; | |
1392 if (argumentsLength < 2) { | |
1393 index = length - 1; | |
1394 } else { | |
1395 index = TO_INTEGER(index); | |
1396 // If index is negative, index from end of the array. | |
1397 if (index < 0) index += length; | |
1398 // If index is still negative, do not search the array. | |
1399 if (index < 0) return -1; | |
1400 else if (index >= length) index = length - 1; | |
1401 } | |
1402 var min = 0; | |
1403 var max = index; | |
1404 if (UseSparseVariant(array, length, IS_ARRAY(array), index)) { | |
1405 %NormalizeElements(array); | |
1406 var indices = %GetArrayKeys(array, index + 1); | |
1407 if (IS_NUMBER(indices)) { | |
1408 // It's an interval. | |
1409 max = indices; // Capped by index already. | |
1410 // Fall through to loop below. | |
1411 } else { | |
1412 if (indices.length == 0) return -1; | |
1413 // Get all the keys in sorted order. | |
1414 var sortedKeys = GetSortedArrayKeys(array, indices); | |
1415 var i = sortedKeys.length - 1; | |
1416 while (i >= 0) { | |
1417 var key = sortedKeys[i]; | |
1418 if (!IS_UNDEFINED(key) && array[key] === element) return key; | |
1419 i--; | |
1420 } | |
1421 return -1; | |
1422 } | |
1423 } | |
1424 // Lookup through the array. | |
1425 if (!IS_UNDEFINED(element)) { | |
1426 for (var i = max; i >= min; i--) { | |
1427 if (array[i] === element) return i; | |
1428 } | |
1429 return -1; | |
1430 } | |
1431 for (var i = max; i >= min; i--) { | |
1432 if (IS_UNDEFINED(array[i]) && i in array) { | |
1433 return i; | |
1434 } | |
1435 } | |
1436 return -1; | |
1437 } | |
1438 | |
1439 | |
1440 function ArrayLastIndexOf(element, index) { | |
1441 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.lastIndexOf"); | |
1442 | |
1443 var length = TO_LENGTH_OR_UINT32(this.length); | |
1444 return InnerArrayLastIndexOf(this, element, index, length, | |
1445 %_ArgumentsLength()); | |
1446 } | |
1447 | |
1448 | |
1449 function InnerArrayReduce(callback, current, array, length, argumentsLength) { | |
1450 if (!IS_CALLABLE(callback)) { | |
1451 throw MakeTypeError(kCalledNonCallable, callback); | |
1452 } | |
1453 | |
1454 var is_array = IS_ARRAY(array); | |
1455 var i = 0; | |
1456 find_initial: if (argumentsLength < 2) { | |
1457 for (; i < length; i++) { | |
1458 if (HAS_INDEX(array, i, is_array)) { | |
1459 current = array[i++]; | |
1460 break find_initial; | |
1461 } | |
1462 } | |
1463 throw MakeTypeError(kReduceNoInitial); | |
1464 } | |
1465 | |
1466 var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(callback); | |
1467 for (; i < length; i++) { | |
1468 if (HAS_INDEX(array, i, is_array)) { | |
1469 var element = array[i]; | |
1470 // Prepare break slots for debugger step in. | |
1471 if (stepping) %DebugPrepareStepInIfStepping(callback); | |
1472 current = callback(current, element, i, array); | |
1473 } | |
1474 } | |
1475 return current; | |
1476 } | |
1477 | |
1478 | |
1479 function ArrayReduce(callback, current) { | |
1480 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reduce"); | |
1481 | |
1482 // Pull out the length so that modifications to the length in the | |
1483 // loop will not affect the looping and side effects are visible. | |
1484 var array = TO_OBJECT(this); | |
1485 var length = TO_LENGTH_OR_UINT32(array.length); | |
1486 return InnerArrayReduce(callback, current, array, length, | |
1487 %_ArgumentsLength()); | |
1488 } | |
1489 | |
1490 | |
1491 function InnerArrayReduceRight(callback, current, array, length, | |
1492 argumentsLength) { | |
1493 if (!IS_CALLABLE(callback)) { | |
1494 throw MakeTypeError(kCalledNonCallable, callback); | |
1495 } | |
1496 | |
1497 var is_array = IS_ARRAY(array); | |
1498 var i = length - 1; | |
1499 find_initial: if (argumentsLength < 2) { | |
1500 for (; i >= 0; i--) { | |
1501 if (HAS_INDEX(array, i, is_array)) { | |
1502 current = array[i--]; | |
1503 break find_initial; | |
1504 } | |
1505 } | |
1506 throw MakeTypeError(kReduceNoInitial); | |
1507 } | |
1508 | |
1509 var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(callback); | |
1510 for (; i >= 0; i--) { | |
1511 if (HAS_INDEX(array, i, is_array)) { | |
1512 var element = array[i]; | |
1513 // Prepare break slots for debugger step in. | |
1514 if (stepping) %DebugPrepareStepInIfStepping(callback); | |
1515 current = callback(current, element, i, array); | |
1516 } | |
1517 } | |
1518 return current; | |
1519 } | |
1520 | |
1521 | |
1522 function ArrayReduceRight(callback, current) { | |
1523 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reduceRight"); | |
1524 | |
1525 // Pull out the length so that side effects are visible before the | |
1526 // callback function is checked. | |
1527 var array = TO_OBJECT(this); | |
1528 var length = TO_LENGTH_OR_UINT32(array.length); | |
1529 return InnerArrayReduceRight(callback, current, array, length, | |
1530 %_ArgumentsLength()); | |
1531 } | |
1532 | |
1533 // ES5, 15.4.3.2 | |
1534 function ArrayIsArray(obj) { | |
1535 return IS_ARRAY(obj); | |
1536 } | |
1537 | |
1538 | |
1539 // ------------------------------------------------------------------- | |
1540 | |
1541 // Set up non-enumerable constructor property on the Array.prototype | |
1542 // object. | |
1543 %AddNamedProperty(GlobalArray.prototype, "constructor", GlobalArray, | |
1544 DONT_ENUM); | |
1545 | |
1546 // Set up unscopable properties on the Array.prototype object. | |
1547 var unscopables = { | |
1548 __proto__: null, | |
1549 copyWithin: true, | |
1550 entries: true, | |
1551 fill: true, | |
1552 find: true, | |
1553 findIndex: true, | |
1554 keys: true, | |
1555 }; | |
1556 | |
1557 %AddNamedProperty(GlobalArray.prototype, unscopablesSymbol, unscopables, | |
1558 DONT_ENUM | READ_ONLY); | |
1559 | |
1560 // Set up non-enumerable functions on the Array object. | |
1561 utils.InstallFunctions(GlobalArray, DONT_ENUM, [ | |
1562 "isArray", ArrayIsArray | |
1563 ]); | |
1564 | |
1565 var specialFunctions = %SpecialArrayFunctions(); | |
1566 | |
1567 var getFunction = function(name, jsBuiltin, len) { | |
1568 var f = jsBuiltin; | |
1569 if (specialFunctions.hasOwnProperty(name)) { | |
1570 f = specialFunctions[name]; | |
1571 } | |
1572 if (!IS_UNDEFINED(len)) { | |
1573 %FunctionSetLength(f, len); | |
1574 } | |
1575 return f; | |
1576 }; | |
1577 | |
1578 // Set up non-enumerable functions of the Array.prototype object and | |
1579 // set their names. | |
1580 // Manipulate the length of some of the functions to meet | |
1581 // expectations set by ECMA-262 or Mozilla. | |
1582 utils.InstallFunctions(GlobalArray.prototype, DONT_ENUM, [ | |
1583 "toString", getFunction("toString", ArrayToString), | |
1584 "toLocaleString", getFunction("toLocaleString", ArrayToLocaleString), | |
1585 "join", getFunction("join", ArrayJoin), | |
1586 "pop", getFunction("pop", ArrayPop), | |
1587 "push", getFunction("push", ArrayPush, 1), | |
1588 "reverse", getFunction("reverse", ArrayReverse), | |
1589 "shift", getFunction("shift", ArrayShift), | |
1590 "unshift", getFunction("unshift", ArrayUnshift, 1), | |
1591 "slice", getFunction("slice", ArraySlice, 2), | |
1592 "splice", getFunction("splice", ArraySplice, 2), | |
1593 "sort", getFunction("sort", ArraySort), | |
1594 "filter", getFunction("filter", ArrayFilter, 1), | |
1595 "forEach", getFunction("forEach", ArrayForEach, 1), | |
1596 "some", getFunction("some", ArraySome, 1), | |
1597 "every", getFunction("every", ArrayEvery, 1), | |
1598 "map", getFunction("map", ArrayMap, 1), | |
1599 "indexOf", getFunction("indexOf", ArrayIndexOf, 1), | |
1600 "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1), | |
1601 "reduce", getFunction("reduce", ArrayReduce, 1), | |
1602 "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1) | |
1603 ]); | |
1604 | |
1605 %FinishArrayPrototypeSetup(GlobalArray.prototype); | |
1606 | |
1607 // The internal Array prototype doesn't need to be fancy, since it's never | |
1608 // exposed to user code. | |
1609 // Adding only the functions that are actually used. | |
1610 utils.SetUpLockedPrototype(InternalArray, GlobalArray(), [ | |
1611 "indexOf", getFunction("indexOf", ArrayIndexOf), | |
1612 "join", getFunction("join", ArrayJoin), | |
1613 "pop", getFunction("pop", ArrayPop), | |
1614 "push", getFunction("push", ArrayPush), | |
1615 "shift", getFunction("shift", ArrayShift), | |
1616 "sort", getFunction("sort", ArraySort), | |
1617 "splice", getFunction("splice", ArraySplice) | |
1618 ]); | |
1619 | |
1620 utils.SetUpLockedPrototype(InternalPackedArray, GlobalArray(), [ | |
1621 "join", getFunction("join", ArrayJoin), | |
1622 "pop", getFunction("pop", ArrayPop), | |
1623 "push", getFunction("push", ArrayPush), | |
1624 "shift", getFunction("shift", ArrayShift) | |
1625 ]); | |
1626 | |
1627 // ------------------------------------------------------------------- | |
1628 // Exports | |
1629 | |
1630 utils.Export(function(to) { | |
1631 to.ArrayIndexOf = ArrayIndexOf; | |
1632 to.ArrayJoin = ArrayJoin; | |
1633 to.ArrayPush = ArrayPush; | |
1634 to.ArrayToString = ArrayToString; | |
1635 to.InnerArrayEvery = InnerArrayEvery; | |
1636 to.InnerArrayFilter = InnerArrayFilter; | |
1637 to.InnerArrayForEach = InnerArrayForEach; | |
1638 to.InnerArrayIndexOf = InnerArrayIndexOf; | |
1639 to.InnerArrayJoin = InnerArrayJoin; | |
1640 to.InnerArrayLastIndexOf = InnerArrayLastIndexOf; | |
1641 to.InnerArrayMap = InnerArrayMap; | |
1642 to.InnerArrayReduce = InnerArrayReduce; | |
1643 to.InnerArrayReduceRight = InnerArrayReduceRight; | |
1644 to.InnerArraySome = InnerArraySome; | |
1645 to.InnerArraySort = InnerArraySort; | |
1646 to.InnerArrayToLocaleString = InnerArrayToLocaleString; | |
1647 to.PackedArrayReverse = PackedArrayReverse; | |
1648 }); | |
1649 | |
1650 %InstallToContext([ | |
1651 "array_pop", ArrayPop, | |
1652 "array_push", ArrayPush, | |
1653 "array_shift", ArrayShift, | |
1654 "array_splice", ArraySplice, | |
1655 "array_slice", ArraySlice, | |
1656 "array_unshift", ArrayUnshift, | |
1657 ]); | |
1658 | |
1659 }); | |
OLD | NEW |