| 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 |
|---|
Chromium Code Reviews
Issue 1398733002:
Move builtin JavaScript sources into own directory. (Closed)
Base URL: https://chromium.googlesource.com/v8/v8.git@master