1 // Copyright 2006-2008 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 // const $Array = global.Array; 31 32 // ------------------------------------------------------------------- 33 34 // Global list of arrays visited during toString, toLocaleString and 35 // join invocations. 36 var visited_arrays = new $Array(); 37 38 39 // Gets a sorted array of array keys. Useful for operations on sparse 40 // arrays. Dupes have not been removed. 41 function GetSortedArrayKeys(array, intervals) { 42 var length = intervals.length; 43 var keys = []; 44 for (var k = 0; k < length; k++) { 45 var key = intervals[k]; 46 if (key < 0) { 47 var j = -1 - key; 48 var limit = j + intervals[++k]; 49 for (; j < limit; j++) { 50 var e = array[j]; 51 if (!IS_UNDEFINED(e) || j in array) { 52 keys.push(j); 53 } 54 } 55 } else { 56 // The case where key is undefined also ends here. 57 if (!IS_UNDEFINED(key)) { 58 var e = array[key]; 59 if (!IS_UNDEFINED(e) || key in array) { 60 keys.push(key); 61 } 62 } 63 } 64 } 65 keys.sort(function(a, b) { return a - b; }); 66 return keys; 67 } 68 69 70 // Optimized for sparse arrays if separator is ''. 71 function SparseJoin(array, len, convert) { 72 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len)); 73 var last_key = -1; 74 var keys_length = keys.length; 75 76 var elements = new $Array(keys_length); 77 var elements_length = 0; 78 79 for (var i = 0; i < keys_length; i++) { 80 var key = keys[i]; 81 if (key != last_key) { 82 var e = array[key]; 83 if (!IS_STRING(e)) e = convert(e); 84 elements[elements_length++] = e; 85 last_key = key; 86 } 87 } 88 return %StringBuilderConcat(elements, elements_length, ''); 89 } 90 91 92 function UseSparseVariant(object, length, is_array) { 93 return is_array && 94 length > 1000 && 95 (!%_IsSmi(length) || 96 %EstimateNumberOfElements(object) < (length >> 2)); 97 } 98 99 100 function Join(array, length, separator, convert) { 101 if (length == 0) return ''; 102 103 var is_array = IS_ARRAY(array); 104 105 if (is_array) { 106 // If the array is cyclic, return the empty string for already 107 // visited arrays. 108 if (!%PushIfAbsent(visited_arrays, array)) return ''; 109 } 110 111 // Attempt to convert the elements. 112 try { 113 if (UseSparseVariant(array, length, is_array) && (separator.length == 0)) { 114 return SparseJoin(array, length, convert); 115 } 116 117 // Fast case for one-element arrays. 118 if (length == 1) { 119 var e = array[0]; 120 if (!IS_UNDEFINED(e) || (0 in array)) { 121 if (IS_STRING(e)) return e; 122 return convert(e); 123 } 124 } 125 126 // Construct an array for the elements. 127 var elements; 128 var elements_length = 0; 129 130 // We pull the empty separator check outside the loop for speed! 131 if (separator.length == 0) { 132 elements = new $Array(length); 133 for (var i = 0; i < length; i++) { 134 var e = array[i]; 135 if (!IS_UNDEFINED(e) || (i in array)) { 136 if (!IS_STRING(e)) e = convert(e); 137 elements[elements_length++] = e; 138 } 139 } 140 } else { 141 elements = new $Array(length << 1); 142 for (var i = 0; i < length; i++) { 143 var e = array[i]; 144 if (i != 0) elements[elements_length++] = separator; 145 if (!IS_UNDEFINED(e) || (i in array)) { 146 if (!IS_STRING(e)) e = convert(e); 147 elements[elements_length++] = e; 148 } 149 } 150 } 151 return %StringBuilderConcat(elements, elements_length, ''); 152 } finally { 153 // Make sure to pop the visited array no matter what happens. 154 if (is_array) visited_arrays.pop(); 155 } 156 } 157 158 159 function ConvertToString(e) { 160 if (e == null) return ''; 161 else return ToString(e); 162 } 163 164 165 function ConvertToLocaleString(e) { 166 if (e == null) { 167 return ''; 168 } else { 169 // e_obj's toLocaleString might be overwritten, check if it is a function. 170 // Call ToString if toLocaleString is not a function. 171 // See issue 877615. 172 var e_obj = ToObject(e); 173 if (IS_FUNCTION(e_obj.toLocaleString)) 174 return ToString(e_obj.toLocaleString()); 175 else 176 return ToString(e); 177 } 178 } 179 180 181 // This function implements the optimized splice implementation that can use 182 // special array operations to handle sparse arrays in a sensible fashion. 183 function SmartSlice(array, start_i, del_count, len, deleted_elements) { 184 // Move deleted elements to a new array (the return value from splice). 185 // Intervals array can contain keys and intervals. See comment in Concat. 186 var intervals = %GetArrayKeys(array, start_i + del_count); 187 var length = intervals.length; 188 for (var k = 0; k < length; k++) { 189 var key = intervals[k]; 190 if (key < 0) { 191 var j = -1 - key; 192 var interval_limit = j + intervals[++k]; 193 if (j < start_i) { 194 j = start_i; 195 } 196 for (; j < interval_limit; j++) { 197 // ECMA-262 15.4.4.12 line 10. The spec could also be 198 // interpreted such that %HasLocalProperty would be the 199 // appropriate test. We follow KJS in consulting the 200 // prototype. 201 var current = array[j]; 202 if (!IS_UNDEFINED(current) || j in array) { 203 deleted_elements[j - start_i] = current; 204 } 205 } 206 } else { 207 if (!IS_UNDEFINED(key)) { 208 if (key >= start_i) { 209 // ECMA-262 15.4.4.12 line 10. The spec could also be 210 // interpreted such that %HasLocalProperty would be the 211 // appropriate test. We follow KJS in consulting the 212 // prototype. 213 var current = array[key]; 214 if (!IS_UNDEFINED(current) || key in array) { 215 deleted_elements[key - start_i] = current; 216 } 217 } 218 } 219 } 220 } 221 } 222 223 224 // This function implements the optimized splice implementation that can use 225 // special array operations to handle sparse arrays in a sensible fashion. 226 function SmartMove(array, start_i, del_count, len, num_additional_args) { 227 // Move data to new array. 228 var new_array = new $Array(len - del_count + num_additional_args); 229 var intervals = %GetArrayKeys(array, len); 230 var length = intervals.length; 231 for (var k = 0; k < length; k++) { 232 var key = intervals[k]; 233 if (key < 0) { 234 var j = -1 - key; 235 var interval_limit = j + intervals[++k]; 236 while (j < start_i && j < interval_limit) { 237 // The spec could also be interpreted such that 238 // %HasLocalProperty would be the appropriate test. We follow 239 // KJS in consulting the prototype. 240 var current = array[j]; 241 if (!IS_UNDEFINED(current) || j in array) { 242 new_array[j] = current; 243 } 244 j++; 245 } 246 j = start_i + del_count; 247 while (j < interval_limit) { 248 // ECMA-262 15.4.4.12 lines 24 and 41. The spec could also be 249 // interpreted such that %HasLocalProperty would be the 250 // appropriate test. We follow KJS in consulting the 251 // prototype. 252 var current = array[j]; 253 if (!IS_UNDEFINED(current) || j in array) { 254 new_array[j - del_count + num_additional_args] = current; 255 } 256 j++; 257 } 258 } else { 259 if (!IS_UNDEFINED(key)) { 260 if (key < start_i) { 261 // The spec could also be interpreted such that 262 // %HasLocalProperty would be the appropriate test. We follow 263 // KJS in consulting the prototype. 264 var current = array[key]; 265 if (!IS_UNDEFINED(current) || key in array) { 266 new_array[key] = current; 267 } 268 } else if (key >= start_i + del_count) { 269 // ECMA-262 15.4.4.12 lines 24 and 41. The spec could also 270 // be interpreted such that %HasLocalProperty would be the 271 // appropriate test. We follow KJS in consulting the 272 // prototype. 273 var current = array[key]; 274 if (!IS_UNDEFINED(current) || key in array) { 275 new_array[key - del_count + num_additional_args] = current; 276 } 277 } 278 } 279 } 280 } 281 // Move contents of new_array into this array 282 %MoveArrayContents(new_array, array); 283 } 284 285 286 // This is part of the old simple-minded splice. We are using it either 287 // because the receiver is not an array (so we have no choice) or because we 288 // know we are not deleting or moving a lot of elements. 289 function SimpleSlice(array, start_i, del_count, len, deleted_elements) { 290 for (var i = 0; i < del_count; i++) { 291 var index = start_i + i; 292 // The spec could also be interpreted such that %HasLocalProperty 293 // would be the appropriate test. We follow KJS in consulting the 294 // prototype. 295 var current = array[index]; 296 if (!IS_UNDEFINED(current) || index in array) 297 deleted_elements[i] = current; 298 } 299 } 300 301 302 function SimpleMove(array, start_i, del_count, len, num_additional_args) { 303 if (num_additional_args !== del_count) { 304 // Move the existing elements after the elements to be deleted 305 // to the right position in the resulting array. 306 if (num_additional_args > del_count) { 307 for (var i = len - del_count; i > start_i; i--) { 308 var from_index = i + del_count - 1; 309 var to_index = i + num_additional_args - 1; 310 // The spec could also be interpreted such that 311 // %HasLocalProperty would be the appropriate test. We follow 312 // KJS in consulting the prototype. 313 var current = array[from_index]; 314 if (!IS_UNDEFINED(current) || from_index in array) { 315 array[to_index] = current; 316 } else { 317 delete array[to_index]; 318 } 319 } 320 } else { 321 for (var i = start_i; i < len - del_count; i++) { 322 var from_index = i + del_count; 323 var to_index = i + num_additional_args; 324 // The spec could also be interpreted such that 325 // %HasLocalProperty would be the appropriate test. We follow 326 // KJS in consulting the prototype. 327 var current = array[from_index]; 328 if (!IS_UNDEFINED(current) || from_index in array) { 329 array[to_index] = current; 330 } else { 331 delete array[to_index]; 332 } 333 } 334 for (var i = len; i > len - del_count + num_additional_args; i--) { 335 delete array[i - 1]; 336 } 337 } 338 } 339 } 340 341 342 // ------------------------------------------------------------------- 343 344 345 function ArrayToString() { 346 if (!IS_ARRAY(this)) { 347 throw new $TypeError('Array.prototype.toString is not generic'); 348 } 349 return Join(this, this.length, ',', ConvertToString); 350 } 351 352 353 function ArrayToLocaleString() { 354 if (!IS_ARRAY(this)) { 355 throw new $TypeError('Array.prototype.toString is not generic'); 356 } 357 return Join(this, this.length, ',', ConvertToLocaleString); 358 } 359 360 361 function ArrayJoin(separator) { 362 if (IS_UNDEFINED(separator)) { 363 separator = ','; 364 } else if (!IS_STRING(separator)) { 365 separator = ToString(separator); 366 } 367 var length = TO_UINT32(this.length); 368 return Join(this, length, separator, ConvertToString); 369 } 370 371 372 // Removes the last element from the array and returns it. See 373 // ECMA-262, section 15.4.4.6. 374 function ArrayPop() { 375 var n = TO_UINT32(this.length); 376 if (n == 0) { 377 this.length = n; 378 return; 379 } 380 n--; 381 var value = this[n]; 382 this.length = n; 383 delete this[n]; 384 return value; 385 } 386 387 388 // Appends the arguments to the end of the array and returns the new 389 // length of the array. See ECMA-262, section 15.4.4.7. 390 function ArrayPush() { 391 var n = TO_UINT32(this.length); 392 var m = %_ArgumentsLength(); 393 for (var i = 0; i < m; i++) { 394 this[i+n] = %_Arguments(i); 395 } 396 this.length = n + m; 397 return this.length; 398 } 399 400 401 function ArrayConcat(arg1) { // length == 1 402 // TODO: can we just use arguments? 403 var arg_count = %_ArgumentsLength(); 404 var arrays = new $Array(1 + arg_count); 405 arrays[0] = this; 406 for (var i = 0; i < arg_count; i++) { 407 arrays[i + 1] = %_Arguments(i); 408 } 409 410 return %ArrayConcat(arrays); 411 } 412 413 414 // For implementing reverse() on large, sparse arrays. 415 function SparseReverse(array, len) { 416 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len)); 417 var high_counter = keys.length - 1; 418 var low_counter = 0; 419 while (low_counter <= high_counter) { 420 var i = keys[low_counter]; 421 var j = keys[high_counter]; 422 423 var j_complement = len - j - 1; 424 var low, high; 425 426 if (j_complement <= i) { 427 high = j; 428 while (keys[--high_counter] == j); 429 low = j_complement; 430 } 431 if (j_complement >= i) { 432 low = i; 433 while (keys[++low_counter] == i); 434 high = len - i - 1; 435 } 436 437 var current_i = array[low]; 438 if (!IS_UNDEFINED(current_i) || low in array) { 439 var current_j = array[high]; 440 if (!IS_UNDEFINED(current_j) || high in array) { 441 array[low] = current_j; 442 array[high] = current_i; 443 } else { 444 array[high] = current_i; 445 delete array[low]; 446 } 447 } else { 448 var current_j = array[high]; 449 if (!IS_UNDEFINED(current_j) || high in array) { 450 array[low] = current_j; 451 delete array[high]; 452 } 453 } 454 } 455 } 456 457 458 function ArrayReverse() { 459 var j = TO_UINT32(this.length) - 1; 460 461 if (UseSparseVariant(this, j, IS_ARRAY(this))) { 462 SparseReverse(this, j+1); 463 return this; 464 } 465 466 for (var i = 0; i < j; i++, j--) { 467 var current_i = this[i]; 468 if (!IS_UNDEFINED(current_i) || i in this) { 469 var current_j = this[j]; 470 if (!IS_UNDEFINED(current_j) || j in this) { 471 this[i] = current_j; 472 this[j] = current_i; 473 } else { 474 this[j] = current_i; 475 delete this[i]; 476 } 477 } else { 478 var current_j = this[j]; 479 if (!IS_UNDEFINED(current_j) || j in this) { 480 this[i] = current_j; 481 delete this[j]; 482 } 483 } 484 } 485 return this; 486 } 487 488 489 function ArrayShift() { 490 var len = TO_UINT32(this.length); 491 492 if (len === 0) { 493 this.length = 0; 494 return; 495 } 496 497 var first = this[0]; 498 499 if (IS_ARRAY(this)) 500 SmartMove(this, 0, 1, len, 0); 501 else 502 SimpleMove(this, 0, 1, len, 0); 503 504 this.length = len - 1; 505 506 return first; 507 } 508 509 510 function ArrayUnshift(arg1) { // length == 1 511 var len = TO_UINT32(this.length); 512 var num_arguments = %_ArgumentsLength(); 513 514 if (IS_ARRAY(this)) 515 SmartMove(this, 0, 0, len, num_arguments); 516 else 517 SimpleMove(this, 0, 0, len, num_arguments); 518 519 for (var i = 0; i < num_arguments; i++) { 520 this[i] = %_Arguments(i); 521 } 522 523 this.length = len + num_arguments; 524 525 return len + num_arguments; 526 } 527 528 529 function ArraySlice(start, end) { 530 var len = TO_UINT32(this.length); 531 var start_i = TO_INTEGER(start); 532 var end_i = len; 533 534 if (end !== void 0) end_i = TO_INTEGER(end); 535 536 if (start_i < 0) { 537 start_i += len; 538 if (start_i < 0) start_i = 0; 539 } else { 540 if (start_i > len) start_i = len; 541 } 542 543 if (end_i < 0) { 544 end_i += len; 545 if (end_i < 0) end_i = 0; 546 } else { 547 if (end_i > len) end_i = len; 548 } 549 550 var result = []; 551 552 if (end_i < start_i) return result; 553 554 if (IS_ARRAY(this)) { 555 SmartSlice(this, start_i, end_i - start_i, len, result); 556 } else { 557 SimpleSlice(this, start_i, end_i - start_i, len, result); 558 } 559 560 result.length = end_i - start_i; 561 562 return result; 563 } 564 565 566 function ArraySplice(start, delete_count) { 567 var num_arguments = %_ArgumentsLength(); 568 569 // SpiderMonkey and JSC return undefined in the case where no 570 // arguments are given instead of using the implicit undefined 571 // arguments. This does not follow ECMA-262, but we do the same for 572 // compatibility. 573 // TraceMonkey follows ECMA-262 though. 574 if (num_arguments == 0) return; 575 576 var len = TO_UINT32(this.length); 577 var start_i = TO_INTEGER(start); 578 579 if (start_i < 0) { 580 start_i += len; 581 if (start_i < 0) start_i = 0; 582 } else { 583 if (start_i > len) start_i = len; 584 } 585 586 // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is 587 // given differently from when an undefined delete count is given. 588 // This does not follow ECMA-262, but we do the same for 589 // compatibility. 590 var del_count = 0; 591 if (num_arguments > 1) { 592 del_count = TO_INTEGER(delete_count); 593 if (del_count < 0) del_count = 0; 594 if (del_count > len - start_i) del_count = len - start_i; 595 } else { 596 del_count = len - start_i; 597 } 598 599 var deleted_elements = []; 600 deleted_elements.length = del_count; 601 602 // Number of elements to add. 603 var num_additional_args = 0; 604 if (num_arguments > 2) { 605 num_additional_args = num_arguments - 2; 606 } 607 608 var use_simple_splice = true; 609 610 if (IS_ARRAY(this) && num_additional_args !== del_count) { 611 // If we are only deleting/moving a few things near the end of the 612 // array then the simple version is going to be faster, because it 613 // doesn't touch most of the array. 614 var estimated_non_hole_elements = %EstimateNumberOfElements(this); 615 if (len > 20 && (estimated_non_hole_elements >> 2) < (len - start_i)) { 616 use_simple_splice = false; 617 } 618 } 619 620 if (use_simple_splice) { 621 SimpleSlice(this, start_i, del_count, len, deleted_elements); 622 SimpleMove(this, start_i, del_count, len, num_additional_args); 623 } else { 624 SmartSlice(this, start_i, del_count, len, deleted_elements); 625 SmartMove(this, start_i, del_count, len, num_additional_args); 626 } 627 628 // Insert the arguments into the resulting array in 629 // place of the deleted elements. 630 var i = start_i; 631 var arguments_index = 2; 632 var arguments_length = %_ArgumentsLength(); 633 while (arguments_index < arguments_length) { 634 this[i++] = %_Arguments(arguments_index++); 635 } 636 this.length = len - del_count + num_additional_args; 637 638 // Return the deleted elements. 639 return deleted_elements; 640 } 641 642 643 function ArraySort(comparefn) { 644 // In-place QuickSort algorithm. 645 // For short (length <= 22) arrays, insertion sort is used for efficiency. 646 647 var custom_compare = IS_FUNCTION(comparefn); 648 649 function Compare(x,y) { 650 // Assume the comparefn, if any, is a consistent comparison function. 651 // If it isn't, we are allowed arbitrary behavior by ECMA 15.4.4.11. 652 if (x === y) return 0; 653 if (custom_compare) { 654 // Don't call directly to avoid exposing the builtin's global object. 655 return comparefn.call(null, x, y); 656 } 657 if (%_IsSmi(x) && %_IsSmi(y)) { 658 return %SmiLexicographicCompare(x, y); 659 } 660 x = ToString(x); 661 y = ToString(y); 662 if (x == y) return 0; 663 else return x < y ? -1 : 1; 664 }; 665 666 function InsertionSort(a, from, to) { 667 for (var i = from + 1; i < to; i++) { 668 var element = a[i]; 669 // Pre-convert the element to a string for comparison if we know 670 // it will happen on each compare anyway. 671 var key = 672 (custom_compare || %_IsSmi(element)) ? element : ToString(element); 673 // place element in a[from..i[ 674 // binary search 675 var min = from; 676 var max = i; 677 // The search interval is a[min..max[ 678 while (min < max) { 679 var mid = min + ((max - min) >> 1); 680 var order = Compare(a[mid], key); 681 if (order == 0) { 682 min = max = mid; 683 break; 684 } 685 if (order < 0) { 686 min = mid + 1; 687 } else { 688 max = mid; 689 } 690 } 691 // place element at position min==max. 692 for (var j = i; j > min; j--) { 693 a[j] = a[j - 1]; 694 } 695 a[min] = element; 696 } 697 } 698 699 function QuickSort(a, from, to) { 700 // Insertion sort is faster for short arrays. 701 if (to - from <= 22) { 702 InsertionSort(a, from, to); 703 return; 704 } 705 var pivot_index = $floor($random() * (to - from)) + from; 706 var pivot = a[pivot_index]; 707 // Pre-convert the element to a string for comparison if we know 708 // it will happen on each compare anyway. 709 var pivot_key = 710 (custom_compare || %_IsSmi(pivot)) ? pivot : ToString(pivot); 711 // Issue 95: Keep the pivot element out of the comparisons to avoid 712 // infinite recursion if comparefn(pivot, pivot) != 0. 713 a[pivot_index] = a[from]; 714 a[from] = pivot; 715 var low_end = from; // Upper bound of the elements lower than pivot. 716 var high_start = to; // Lower bound of the elements greater than pivot. 717 // From low_end to i are elements equal to pivot. 718 // From i to high_start are elements that haven't been compared yet. 719 for (var i = from + 1; i < high_start; ) { 720 var element = a[i]; 721 var order = Compare(element, pivot_key); 722 if (order < 0) { 723 a[i] = a[low_end]; 724 a[low_end] = element; 725 i++; 726 low_end++; 727 } else if (order > 0) { 728 high_start--; 729 a[i] = a[high_start]; 730 a[high_start] = element; 731 } else { // order == 0 732 i++; 733 } 734 } 735 QuickSort(a, from, low_end); 736 QuickSort(a, high_start, to); 737 } 738 739 var length; 740 741 // Copies elements in the range 0..length from obj's prototype chain 742 // to obj itself, if obj has holes. Returns one more than the maximal index 743 // of a prototype property. 744 function CopyFromPrototype(obj, length) { 745 var max = 0; 746 for (var proto = obj.__proto__; proto; proto = proto.__proto__) { 747 var indices = %GetArrayKeys(proto, length); 748 if (indices.length > 0) { 749 if (indices[0] == -1) { 750 // It's an interval. 751 var proto_length = indices[1]; 752 for (var i = 0; i < proto_length; i++) { 753 if (!obj.hasOwnProperty(i) && proto.hasOwnProperty(i)) { 754 obj[i] = proto[i]; 755 if (i >= max) { max = i + 1; } 756 } 757 } 758 } else { 759 for (var i = 0; i < indices.length; i++) { 760 var index = indices[i]; 761 if (!IS_UNDEFINED(index) && 762 !obj.hasOwnProperty(index) && proto.hasOwnProperty(index)) { 763 obj[index] = proto[index]; 764 if (index >= max) { max = index + 1; } 765 } 766 } 767 } 768 } 769 } 770 return max; 771 } 772 773 // Set a value of "undefined" on all indices in the range from..to 774 // where a prototype of obj has an element. I.e., shadow all prototype 775 // elements in that range. 776 function ShadowPrototypeElements(obj, from, to) { 777 for (var proto = obj.__proto__; proto; proto = proto.__proto__) { 778 var indices = %GetArrayKeys(proto, to); 779 if (indices.length > 0) { 780 if (indices[0] == -1) { 781 // It's an interval. 782 var proto_length = indices[1]; 783 for (var i = from; i < proto_length; i++) { 784 if (proto.hasOwnProperty(i)) { 785 obj[i] = void 0; 786 } 787 } 788 } else { 789 for (var i = 0; i < indices.length; i++) { 790 var index = indices[i]; 791 if (!IS_UNDEFINED(index) && from <= index && 792 proto.hasOwnProperty(index)) { 793 obj[index] = void 0; 794 } 795 } 796 } 797 } 798 } 799 } 800 801 function SafeRemoveArrayHoles(obj) { 802 // Copy defined elements from the end to fill in all holes and undefineds 803 // in the beginning of the array. Write undefineds and holes at the end 804 // after loop is finished. 805 var first_undefined = 0; 806 var last_defined = length - 1; 807 var num_holes = 0; 808 while (first_undefined < last_defined) { 809 // Find first undefined element. 810 while (first_undefined < last_defined && 811 !IS_UNDEFINED(obj[first_undefined])) { 812 first_undefined++; 813 } 814 // Maintain the invariant num_holes = the number of holes in the original 815 // array with indices <= first_undefined or > last_defined. 816 if (!obj.hasOwnProperty(first_undefined)) { 817 num_holes++; 818 } 819 820 // Find last defined element. 821 while (first_undefined < last_defined && 822 IS_UNDEFINED(obj[last_defined])) { 823 if (!obj.hasOwnProperty(last_defined)) { 824 num_holes++; 825 } 826 last_defined--; 827 } 828 if (first_undefined < last_defined) { 829 // Fill in hole or undefined. 830 obj[first_undefined] = obj[last_defined]; 831 obj[last_defined] = void 0; 832 } 833 } 834 // If there were any undefineds in the entire array, first_undefined 835 // points to one past the last defined element. Make this true if 836 // there were no undefineds, as well, so that first_undefined == number 837 // of defined elements. 838 if (!IS_UNDEFINED(obj[first_undefined])) first_undefined++; 839 // Fill in the undefineds and the holes. There may be a hole where 840 // an undefined should be and vice versa. 841 var i; 842 for (i = first_undefined; i < length - num_holes; i++) { 843 obj[i] = void 0; 844 } 845 for (i = length - num_holes; i < length; i++) { 846 // For compatability with Webkit, do not expose elements in the prototype. 847 if (i in obj.__proto__) { 848 obj[i] = void 0; 849 } else { 850 delete obj[i]; 851 } 852 } 853 854 // Return the number of defined elements. 855 return first_undefined; 856 } 857 858 length = TO_UINT32(this.length); 859 if (length < 2) return this; 860 861 var is_array = IS_ARRAY(this); 862 var max_prototype_element; 863 if (!is_array) { 864 // For compatibility with JSC, we also sort elements inherited from 865 // the prototype chain on non-Array objects. 866 // We do this by copying them to this object and sorting only 867 // local elements. This is not very efficient, but sorting with 868 // inherited elements happens very, very rarely, if at all. 869 // The specification allows "implementation dependent" behavior 870 // if an element on the prototype chain has an element that 871 // might interact with sorting. 872 max_prototype_element = CopyFromPrototype(this, length); 873 } 874 875 var num_non_undefined = %RemoveArrayHoles(this, length); 876 if (num_non_undefined == -1) { 877 // There were indexed accessors in the array. Move array holes and 878 // undefineds to the end using a Javascript function that is safe 879 // in the presence of accessors. 880 num_non_undefined = SafeRemoveArrayHoles(this); 881 } 882 883 QuickSort(this, 0, num_non_undefined); 884 885 if (!is_array && (num_non_undefined + 1 < max_prototype_element)) { 886 // For compatibility with JSC, we shadow any elements in the prototype 887 // chain that has become exposed by sort moving a hole to its position. 888 ShadowPrototypeElements(this, num_non_undefined, max_prototype_element); 889 } 890 891 return this; 892 } 893 894 895 // The following functions cannot be made efficient on sparse arrays while 896 // preserving the semantics, since the calls to the receiver function can add 897 // or delete elements from the array. 898 function ArrayFilter(f, receiver) { 899 if (!IS_FUNCTION(f)) { 900 throw MakeTypeError('called_non_callable', [ f ]); 901 } 902 // Pull out the length so that modifications to the length in the 903 // loop will not affect the looping. 904 var length = this.length; 905 var result = []; 906 var result_length = 0; 907 for (var i = 0; i < length; i++) { 908 var current = this[i]; 909 if (!IS_UNDEFINED(current) || i in this) { 910 if (f.call(receiver, current, i, this)) result[result_length++] = current; 911 } 912 } 913 return result; 914 } 915 916 917 function ArrayForEach(f, receiver) { 918 if (!IS_FUNCTION(f)) { 919 throw MakeTypeError('called_non_callable', [ f ]); 920 } 921 // Pull out the length so that modifications to the length in the 922 // loop will not affect the looping. 923 var length = TO_UINT32(this.length); 924 for (var i = 0; i < length; i++) { 925 var current = this[i]; 926 if (!IS_UNDEFINED(current) || i in this) { 927 f.call(receiver, current, i, this); 928 } 929 } 930 } 931 932 933 // Executes the function once for each element present in the 934 // array until it finds one where callback returns true. 935 function ArraySome(f, receiver) { 936 if (!IS_FUNCTION(f)) { 937 throw MakeTypeError('called_non_callable', [ f ]); 938 } 939 // Pull out the length so that modifications to the length in the 940 // loop will not affect the looping. 941 var length = TO_UINT32(this.length); 942 for (var i = 0; i < length; i++) { 943 var current = this[i]; 944 if (!IS_UNDEFINED(current) || i in this) { 945 if (f.call(receiver, current, i, this)) return true; 946 } 947 } 948 return false; 949 } 950 951 952 function ArrayEvery(f, receiver) { 953 if (!IS_FUNCTION(f)) { 954 throw MakeTypeError('called_non_callable', [ f ]); 955 } 956 // Pull out the length so that modifications to the length in the 957 // loop will not affect the looping. 958 var length = TO_UINT32(this.length); 959 for (var i = 0; i < length; i++) { 960 var current = this[i]; 961 if (!IS_UNDEFINED(current) || i in this) { 962 if (!f.call(receiver, current, i, this)) return false; 963 } 964 } 965 return true; 966 } 967 968 function ArrayMap(f, receiver) { 969 if (!IS_FUNCTION(f)) { 970 throw MakeTypeError('called_non_callable', [ f ]); 971 } 972 // Pull out the length so that modifications to the length in the 973 // loop will not affect the looping. 974 var length = TO_UINT32(this.length); 975 var result = new $Array(length); 976 for (var i = 0; i < length; i++) { 977 var current = this[i]; 978 if (!IS_UNDEFINED(current) || i in this) { 979 result[i] = f.call(receiver, current, i, this); 980 } 981 } 982 return result; 983 } 984 985 986 function ArrayIndexOf(element, index) { 987 var length = this.length; 988 if (index == null) { 989 index = 0; 990 } else { 991 index = TO_INTEGER(index); 992 // If index is negative, index from the end of the array. 993 if (index < 0) index = length + index; 994 // If index is still negative, search the entire array. 995 if (index < 0) index = 0; 996 } 997 // Lookup through the array. 998 for (var i = index; i < length; i++) { 999 var current = this[i]; 1000 if (!IS_UNDEFINED(current) || i in this) { 1001 if (current === element) return i; 1002 } 1003 } 1004 return -1; 1005 } 1006 1007 1008 function ArrayLastIndexOf(element, index) { 1009 var length = this.length; 1010 if (index == null) { 1011 index = length - 1; 1012 } else { 1013 index = TO_INTEGER(index); 1014 // If index is negative, index from end of the array. 1015 if (index < 0) index = length + index; 1016 // If index is still negative, do not search the array. 1017 if (index < 0) index = -1; 1018 else if (index >= length) index = length - 1; 1019 } 1020 // Lookup through the array. 1021 for (var i = index; i >= 0; i--) { 1022 var current = this[i]; 1023 if (!IS_UNDEFINED(current) || i in this) { 1024 if (current === element) return i; 1025 } 1026 } 1027 return -1; 1028 } 1029 1030 1031 function ArrayReduce(callback, current) { 1032 if (!IS_FUNCTION(callback)) { 1033 throw MakeTypeError('called_non_callable', [callback]); 1034 } 1035 // Pull out the length so that modifications to the length in the 1036 // loop will not affect the looping. 1037 var length = this.length; 1038 var i = 0; 1039 1040 find_initial: if (%_ArgumentsLength() < 2) { 1041 for (; i < length; i++) { 1042 current = this[i]; 1043 if (!IS_UNDEFINED(current) || i in this) { 1044 i++; 1045 break find_initial; 1046 } 1047 } 1048 throw MakeTypeError('reduce_no_initial', []); 1049 } 1050 1051 for (; i < length; i++) { 1052 var element = this[i]; 1053 if (!IS_UNDEFINED(element) || i in this) { 1054 current = callback.call(null, current, element, i, this); 1055 } 1056 } 1057 return current; 1058 } 1059 1060 function ArrayReduceRight(callback, current) { 1061 if (!IS_FUNCTION(callback)) { 1062 throw MakeTypeError('called_non_callable', [callback]); 1063 } 1064 var i = this.length - 1; 1065 1066 find_initial: if (%_ArgumentsLength() < 2) { 1067 for (; i >= 0; i--) { 1068 current = this[i]; 1069 if (!IS_UNDEFINED(current) || i in this) { 1070 i--; 1071 break find_initial; 1072 } 1073 } 1074 throw MakeTypeError('reduce_no_initial', []); 1075 } 1076 1077 for (; i >= 0; i--) { 1078 var element = this[i]; 1079 if (!IS_UNDEFINED(element) || i in this) { 1080 current = callback.call(null, current, element, i, this); 1081 } 1082 } 1083 return current; 1084 } 1085 1086 // ES5, 15.4.3.2 1087 function ArrayIsArray(obj) { 1088 return IS_ARRAY(obj); 1089 } 1090 1091 // ------------------------------------------------------------------- 1092 1093 1094 function UpdateFunctionLengths(lengths) { 1095 for (var key in lengths) { 1096 %FunctionSetLength(this[key], lengths[key]); 1097 } 1098 } 1099 1100 1101 // ------------------------------------------------------------------- 1102 function SetupArray() { 1103 // Setup non-enumerable constructor property on the Array.prototype 1104 // object. 1105 %SetProperty($Array.prototype, "constructor", $Array, DONT_ENUM); 1106 1107 // Setup non-enumerable functions on the Array object. 1108 InstallFunctions($Array, DONT_ENUM, $Array( 1109 "isArray", ArrayIsArray 1110 )); 1111 1112 // Setup non-enumerable functions of the Array.prototype object and 1113 // set their names. 1114 InstallFunctionsOnHiddenPrototype($Array.prototype, DONT_ENUM, $Array( 1115 "toString", ArrayToString, 1116 "toLocaleString", ArrayToLocaleString, 1117 "join", ArrayJoin, 1118 "pop", ArrayPop, 1119 "push", ArrayPush, 1120 "concat", ArrayConcat, 1121 "reverse", ArrayReverse, 1122 "shift", ArrayShift, 1123 "unshift", ArrayUnshift, 1124 "slice", ArraySlice, 1125 "splice", ArraySplice, 1126 "sort", ArraySort, 1127 "filter", ArrayFilter, 1128 "forEach", ArrayForEach, 1129 "some", ArraySome, 1130 "every", ArrayEvery, 1131 "map", ArrayMap, 1132 "indexOf", ArrayIndexOf, 1133 "lastIndexOf", ArrayLastIndexOf, 1134 "reduce", ArrayReduce, 1135 "reduceRight", ArrayReduceRight 1136 )); 1137 1138 // Manipulate the length of some of the functions to meet 1139 // expectations set by ECMA-262 or Mozilla. 1140 UpdateFunctionLengths({ 1141 ArrayFilter: 1, 1142 ArrayForEach: 1, 1143 ArraySome: 1, 1144 ArrayEvery: 1, 1145 ArrayMap: 1, 1146 ArrayIndexOf: 1, 1147 ArrayLastIndexOf: 1, 1148 ArrayPush: 1, 1149 ArrayReduce: 1, 1150 ArrayReduceRight: 1 1151 }); 1152 } 1153 1154 1155 SetupArray(); 1156