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