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 #include "src/elements.h" 6 7 #include "src/arguments.h" 8 #include "src/conversions.h" 9 #include "src/frames.h" 10 #include "src/heap/factory.h" 11 #include "src/heap/heap-write-barrier-inl.h" 12 #include "src/isolate-inl.h" 13 #include "src/messages.h" 14 #include "src/objects-inl.h" 15 #include "src/objects/arguments-inl.h" 16 #include "src/objects/hash-table-inl.h" 17 #include "src/objects/js-array-buffer-inl.h" 18 #include "src/objects/js-array-inl.h" 19 #include "src/utils.h" 20 21 // Each concrete ElementsAccessor can handle exactly one ElementsKind, 22 // several abstract ElementsAccessor classes are used to allow sharing 23 // common code. 24 // 25 // Inheritance hierarchy: 26 // - ElementsAccessorBase (abstract) 27 // - FastElementsAccessor (abstract) 28 // - FastSmiOrObjectElementsAccessor 29 // - FastPackedSmiElementsAccessor 30 // - FastHoleySmiElementsAccessor 31 // - FastPackedObjectElementsAccessor 32 // - FastHoleyObjectElementsAccessor 33 // - FastDoubleElementsAccessor 34 // - FastPackedDoubleElementsAccessor 35 // - FastHoleyDoubleElementsAccessor 36 // - TypedElementsAccessor: template, with instantiations: 37 // - FixedUint8ElementsAccessor 38 // - FixedInt8ElementsAccessor 39 // - FixedUint16ElementsAccessor 40 // - FixedInt16ElementsAccessor 41 // - FixedUint32ElementsAccessor 42 // - FixedInt32ElementsAccessor 43 // - FixedFloat32ElementsAccessor 44 // - FixedFloat64ElementsAccessor 45 // - FixedUint8ClampedElementsAccessor 46 // - FixedBigUint64ElementsAccessor 47 // - FixedBigInt64ElementsAccessor 48 // - DictionaryElementsAccessor 49 // - SloppyArgumentsElementsAccessor 50 // - FastSloppyArgumentsElementsAccessor 51 // - SlowSloppyArgumentsElementsAccessor 52 // - StringWrapperElementsAccessor 53 // - FastStringWrapperElementsAccessor 54 // - SlowStringWrapperElementsAccessor 55 56 namespace v8 { 57 namespace internal { 58 59 60 namespace { 61 62 63 static const int kPackedSizeNotKnown = -1; 64 65 enum Where { AT_START, AT_END }; 66 67 68 // First argument in list is the accessor class, the second argument is the 69 // accessor ElementsKind, and the third is the backing store class. Use the 70 // fast element handler for smi-only arrays. The implementation is currently 71 // identical. Note that the order must match that of the ElementsKind enum for 72 // the |accessor_array[]| below to work. 73 #define ELEMENTS_LIST(V) \ 74 V(FastPackedSmiElementsAccessor, PACKED_SMI_ELEMENTS, FixedArray) \ 75 V(FastHoleySmiElementsAccessor, HOLEY_SMI_ELEMENTS, FixedArray) \ 76 V(FastPackedObjectElementsAccessor, PACKED_ELEMENTS, FixedArray) \ 77 V(FastHoleyObjectElementsAccessor, HOLEY_ELEMENTS, FixedArray) \ 78 V(FastPackedDoubleElementsAccessor, PACKED_DOUBLE_ELEMENTS, \ 79 FixedDoubleArray) \ 80 V(FastHoleyDoubleElementsAccessor, HOLEY_DOUBLE_ELEMENTS, FixedDoubleArray) \ 81 V(DictionaryElementsAccessor, DICTIONARY_ELEMENTS, NumberDictionary) \ 82 V(FastSloppyArgumentsElementsAccessor, FAST_SLOPPY_ARGUMENTS_ELEMENTS, \ 83 FixedArray) \ 84 V(SlowSloppyArgumentsElementsAccessor, SLOW_SLOPPY_ARGUMENTS_ELEMENTS, \ 85 FixedArray) \ 86 V(FastStringWrapperElementsAccessor, FAST_STRING_WRAPPER_ELEMENTS, \ 87 FixedArray) \ 88 V(SlowStringWrapperElementsAccessor, SLOW_STRING_WRAPPER_ELEMENTS, \ 89 FixedArray) \ 90 V(FixedUint8ElementsAccessor, UINT8_ELEMENTS, FixedUint8Array) \ 91 V(FixedInt8ElementsAccessor, INT8_ELEMENTS, FixedInt8Array) \ 92 V(FixedUint16ElementsAccessor, UINT16_ELEMENTS, FixedUint16Array) \ 93 V(FixedInt16ElementsAccessor, INT16_ELEMENTS, FixedInt16Array) \ 94 V(FixedUint32ElementsAccessor, UINT32_ELEMENTS, FixedUint32Array) \ 95 V(FixedInt32ElementsAccessor, INT32_ELEMENTS, FixedInt32Array) \ 96 V(FixedFloat32ElementsAccessor, FLOAT32_ELEMENTS, FixedFloat32Array) \ 97 V(FixedFloat64ElementsAccessor, FLOAT64_ELEMENTS, FixedFloat64Array) \ 98 V(FixedUint8ClampedElementsAccessor, UINT8_CLAMPED_ELEMENTS, \ 99 FixedUint8ClampedArray) \ 100 V(FixedBigUint64ElementsAccessor, BIGUINT64_ELEMENTS, FixedBigUint64Array) \ 101 V(FixedBigInt64ElementsAccessor, BIGINT64_ELEMENTS, FixedBigInt64Array) 102 103 template<ElementsKind Kind> class ElementsKindTraits { 104 public: 105 typedef FixedArrayBase BackingStore; 106 }; 107 108 #define ELEMENTS_TRAITS(Class, KindParam, Store) \ 109 template <> \ 110 class ElementsKindTraits<KindParam> { \ 111 public: /* NOLINT */ \ 112 static constexpr ElementsKind Kind = KindParam; \ 113 typedef Store BackingStore; \ 114 }; \ 115 constexpr ElementsKind ElementsKindTraits<KindParam>::Kind; 116 ELEMENTS_LIST(ELEMENTS_TRAITS) 117 #undef ELEMENTS_TRAITS 118 119 V8_WARN_UNUSED_RESULT 120 MaybeHandle<Object> ThrowArrayLengthRangeError(Isolate* isolate) { 121 THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kInvalidArrayLength), 122 Object); 123 } 124 125 WriteBarrierMode GetWriteBarrierMode(ElementsKind kind) { 126 if (IsSmiElementsKind(kind)) return SKIP_WRITE_BARRIER; 127 if (IsDoubleElementsKind(kind)) return SKIP_WRITE_BARRIER; 128 return UPDATE_WRITE_BARRIER; 129 } 130 131 void CopyObjectToObjectElements(Isolate* isolate, FixedArrayBase* from_base, 132 ElementsKind from_kind, uint32_t from_start, 133 FixedArrayBase* to_base, ElementsKind to_kind, 134 uint32_t to_start, int raw_copy_size) { 135 ReadOnlyRoots roots(isolate); 136 DCHECK(to_base->map() != roots.fixed_cow_array_map()); 137 DisallowHeapAllocation no_allocation; 138 int copy_size = raw_copy_size; 139 if (raw_copy_size < 0) { 140 DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd || 141 raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 142 copy_size = Min(from_base->length() - from_start, 143 to_base->length() - to_start); 144 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 145 int start = to_start + copy_size; 146 int length = to_base->length() - start; 147 if (length > 0) { 148 MemsetPointer(FixedArray::cast(to_base)->data_start() + start, 149 roots.the_hole_value(), length); 150 } 151 } 152 } 153 DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() && 154 (copy_size + static_cast<int>(from_start)) <= from_base->length()); 155 if (copy_size == 0) return; 156 FixedArray* from = FixedArray::cast(from_base); 157 FixedArray* to = FixedArray::cast(to_base); 158 DCHECK(IsSmiOrObjectElementsKind(from_kind)); 159 DCHECK(IsSmiOrObjectElementsKind(to_kind)); 160 161 WriteBarrierMode write_barrier_mode = 162 (IsObjectElementsKind(from_kind) && IsObjectElementsKind(to_kind)) 163 ? UPDATE_WRITE_BARRIER 164 : SKIP_WRITE_BARRIER; 165 for (int i = 0; i < copy_size; i++) { 166 Object* value = from->get(from_start + i); 167 to->set(to_start + i, value, write_barrier_mode); 168 } 169 } 170 171 static void CopyDictionaryToObjectElements( 172 Isolate* isolate, FixedArrayBase* from_base, uint32_t from_start, 173 FixedArrayBase* to_base, ElementsKind to_kind, uint32_t to_start, 174 int raw_copy_size) { 175 DisallowHeapAllocation no_allocation; 176 NumberDictionary* from = NumberDictionary::cast(from_base); 177 int copy_size = raw_copy_size; 178 if (raw_copy_size < 0) { 179 DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd || 180 raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 181 copy_size = from->max_number_key() + 1 - from_start; 182 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 183 int start = to_start + copy_size; 184 int length = to_base->length() - start; 185 if (length > 0) { 186 MemsetPointer(FixedArray::cast(to_base)->data_start() + start, 187 ReadOnlyRoots(isolate).the_hole_value(), length); 188 } 189 } 190 } 191 DCHECK(to_base != from_base); 192 DCHECK(IsSmiOrObjectElementsKind(to_kind)); 193 if (copy_size == 0) return; 194 FixedArray* to = FixedArray::cast(to_base); 195 uint32_t to_length = to->length(); 196 if (to_start + copy_size > to_length) { 197 copy_size = to_length - to_start; 198 } 199 WriteBarrierMode write_barrier_mode = GetWriteBarrierMode(to_kind); 200 for (int i = 0; i < copy_size; i++) { 201 int entry = from->FindEntry(isolate, i + from_start); 202 if (entry != NumberDictionary::kNotFound) { 203 Object* value = from->ValueAt(entry); 204 DCHECK(!value->IsTheHole(isolate)); 205 to->set(i + to_start, value, write_barrier_mode); 206 } else { 207 to->set_the_hole(isolate, i + to_start); 208 } 209 } 210 } 211 212 213 // NOTE: this method violates the handlified function signature convention: 214 // raw pointer parameters in the function that allocates. 215 // See ElementsAccessorBase::CopyElements() for details. 216 static void CopyDoubleToObjectElements(Isolate* isolate, 217 FixedArrayBase* from_base, 218 uint32_t from_start, 219 FixedArrayBase* to_base, 220 uint32_t to_start, int raw_copy_size) { 221 int copy_size = raw_copy_size; 222 if (raw_copy_size < 0) { 223 DisallowHeapAllocation no_allocation; 224 DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd || 225 raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 226 copy_size = Min(from_base->length() - from_start, 227 to_base->length() - to_start); 228 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 229 // Also initialize the area that will be copied over since HeapNumber 230 // allocation below can cause an incremental marking step, requiring all 231 // existing heap objects to be propertly initialized. 232 int start = to_start; 233 int length = to_base->length() - start; 234 if (length > 0) { 235 MemsetPointer(FixedArray::cast(to_base)->data_start() + start, 236 ReadOnlyRoots(isolate).the_hole_value(), length); 237 } 238 } 239 } 240 241 DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() && 242 (copy_size + static_cast<int>(from_start)) <= from_base->length()); 243 if (copy_size == 0) return; 244 245 // From here on, the code below could actually allocate. Therefore the raw 246 // values are wrapped into handles. 247 Handle<FixedDoubleArray> from(FixedDoubleArray::cast(from_base), isolate); 248 Handle<FixedArray> to(FixedArray::cast(to_base), isolate); 249 250 // Use an outer loop to not waste too much time on creating HandleScopes. 251 // On the other hand we might overflow a single handle scope depending on 252 // the copy_size. 253 int offset = 0; 254 while (offset < copy_size) { 255 HandleScope scope(isolate); 256 offset += 100; 257 for (int i = offset - 100; i < offset && i < copy_size; ++i) { 258 Handle<Object> value = 259 FixedDoubleArray::get(*from, i + from_start, isolate); 260 to->set(i + to_start, *value, UPDATE_WRITE_BARRIER); 261 } 262 } 263 } 264 265 266 static void CopyDoubleToDoubleElements(FixedArrayBase* from_base, 267 uint32_t from_start, 268 FixedArrayBase* to_base, 269 uint32_t to_start, int raw_copy_size) { 270 DisallowHeapAllocation no_allocation; 271 int copy_size = raw_copy_size; 272 if (raw_copy_size < 0) { 273 DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd || 274 raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 275 copy_size = Min(from_base->length() - from_start, 276 to_base->length() - to_start); 277 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 278 for (int i = to_start + copy_size; i < to_base->length(); ++i) { 279 FixedDoubleArray::cast(to_base)->set_the_hole(i); 280 } 281 } 282 } 283 DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() && 284 (copy_size + static_cast<int>(from_start)) <= from_base->length()); 285 if (copy_size == 0) return; 286 FixedDoubleArray* from = FixedDoubleArray::cast(from_base); 287 FixedDoubleArray* to = FixedDoubleArray::cast(to_base); 288 Address to_address = to->address() + FixedDoubleArray::kHeaderSize; 289 Address from_address = from->address() + FixedDoubleArray::kHeaderSize; 290 to_address += kDoubleSize * to_start; 291 from_address += kDoubleSize * from_start; 292 int words_per_double = (kDoubleSize / kPointerSize); 293 CopyWords(reinterpret_cast<Object**>(to_address), 294 reinterpret_cast<Object**>(from_address), 295 static_cast<size_t>(words_per_double * copy_size)); 296 } 297 298 299 static void CopySmiToDoubleElements(FixedArrayBase* from_base, 300 uint32_t from_start, 301 FixedArrayBase* to_base, uint32_t to_start, 302 int raw_copy_size) { 303 DisallowHeapAllocation no_allocation; 304 int copy_size = raw_copy_size; 305 if (raw_copy_size < 0) { 306 DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd || 307 raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 308 copy_size = from_base->length() - from_start; 309 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 310 for (int i = to_start + copy_size; i < to_base->length(); ++i) { 311 FixedDoubleArray::cast(to_base)->set_the_hole(i); 312 } 313 } 314 } 315 DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() && 316 (copy_size + static_cast<int>(from_start)) <= from_base->length()); 317 if (copy_size == 0) return; 318 FixedArray* from = FixedArray::cast(from_base); 319 FixedDoubleArray* to = FixedDoubleArray::cast(to_base); 320 Object* the_hole = from->GetReadOnlyRoots().the_hole_value(); 321 for (uint32_t from_end = from_start + static_cast<uint32_t>(copy_size); 322 from_start < from_end; from_start++, to_start++) { 323 Object* hole_or_smi = from->get(from_start); 324 if (hole_or_smi == the_hole) { 325 to->set_the_hole(to_start); 326 } else { 327 to->set(to_start, Smi::ToInt(hole_or_smi)); 328 } 329 } 330 } 331 332 333 static void CopyPackedSmiToDoubleElements(FixedArrayBase* from_base, 334 uint32_t from_start, 335 FixedArrayBase* to_base, 336 uint32_t to_start, int packed_size, 337 int raw_copy_size) { 338 DisallowHeapAllocation no_allocation; 339 int copy_size = raw_copy_size; 340 uint32_t to_end; 341 if (raw_copy_size < 0) { 342 DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd || 343 raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 344 copy_size = packed_size - from_start; 345 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 346 to_end = to_base->length(); 347 for (uint32_t i = to_start + copy_size; i < to_end; ++i) { 348 FixedDoubleArray::cast(to_base)->set_the_hole(i); 349 } 350 } else { 351 to_end = to_start + static_cast<uint32_t>(copy_size); 352 } 353 } else { 354 to_end = to_start + static_cast<uint32_t>(copy_size); 355 } 356 DCHECK(static_cast<int>(to_end) <= to_base->length()); 357 DCHECK(packed_size >= 0 && packed_size <= copy_size); 358 DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() && 359 (copy_size + static_cast<int>(from_start)) <= from_base->length()); 360 if (copy_size == 0) return; 361 FixedArray* from = FixedArray::cast(from_base); 362 FixedDoubleArray* to = FixedDoubleArray::cast(to_base); 363 for (uint32_t from_end = from_start + static_cast<uint32_t>(packed_size); 364 from_start < from_end; from_start++, to_start++) { 365 Object* smi = from->get(from_start); 366 DCHECK(!smi->IsTheHole()); 367 to->set(to_start, Smi::ToInt(smi)); 368 } 369 } 370 371 372 static void CopyObjectToDoubleElements(FixedArrayBase* from_base, 373 uint32_t from_start, 374 FixedArrayBase* to_base, 375 uint32_t to_start, int raw_copy_size) { 376 DisallowHeapAllocation no_allocation; 377 int copy_size = raw_copy_size; 378 if (raw_copy_size < 0) { 379 DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd || 380 raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 381 copy_size = from_base->length() - from_start; 382 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 383 for (int i = to_start + copy_size; i < to_base->length(); ++i) { 384 FixedDoubleArray::cast(to_base)->set_the_hole(i); 385 } 386 } 387 } 388 DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() && 389 (copy_size + static_cast<int>(from_start)) <= from_base->length()); 390 if (copy_size == 0) return; 391 FixedArray* from = FixedArray::cast(from_base); 392 FixedDoubleArray* to = FixedDoubleArray::cast(to_base); 393 Object* the_hole = from->GetReadOnlyRoots().the_hole_value(); 394 for (uint32_t from_end = from_start + copy_size; 395 from_start < from_end; from_start++, to_start++) { 396 Object* hole_or_object = from->get(from_start); 397 if (hole_or_object == the_hole) { 398 to->set_the_hole(to_start); 399 } else { 400 to->set(to_start, hole_or_object->Number()); 401 } 402 } 403 } 404 405 static void CopyDictionaryToDoubleElements( 406 Isolate* isolate, FixedArrayBase* from_base, uint32_t from_start, 407 FixedArrayBase* to_base, uint32_t to_start, int raw_copy_size) { 408 DisallowHeapAllocation no_allocation; 409 NumberDictionary* from = NumberDictionary::cast(from_base); 410 int copy_size = raw_copy_size; 411 if (copy_size < 0) { 412 DCHECK(copy_size == ElementsAccessor::kCopyToEnd || 413 copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 414 copy_size = from->max_number_key() + 1 - from_start; 415 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 416 for (int i = to_start + copy_size; i < to_base->length(); ++i) { 417 FixedDoubleArray::cast(to_base)->set_the_hole(i); 418 } 419 } 420 } 421 if (copy_size == 0) return; 422 FixedDoubleArray* to = FixedDoubleArray::cast(to_base); 423 uint32_t to_length = to->length(); 424 if (to_start + copy_size > to_length) { 425 copy_size = to_length - to_start; 426 } 427 for (int i = 0; i < copy_size; i++) { 428 int entry = from->FindEntry(isolate, i + from_start); 429 if (entry != NumberDictionary::kNotFound) { 430 to->set(i + to_start, from->ValueAt(entry)->Number()); 431 } else { 432 to->set_the_hole(i + to_start); 433 } 434 } 435 } 436 437 static void TraceTopFrame(Isolate* isolate) { 438 StackFrameIterator it(isolate); 439 if (it.done()) { 440 PrintF("unknown location (no JavaScript frames present)"); 441 return; 442 } 443 StackFrame* raw_frame = it.frame(); 444 if (raw_frame->is_internal()) { 445 Code* current_code_object = 446 isolate->heap()->GcSafeFindCodeForInnerPointer(raw_frame->pc()); 447 if (current_code_object->builtin_index() == 448 Builtins::kFunctionPrototypeApply) { 449 PrintF("apply from "); 450 it.Advance(); 451 raw_frame = it.frame(); 452 } 453 } 454 JavaScriptFrame::PrintTop(isolate, stdout, false, true); 455 } 456 457 static void SortIndices( 458 Isolate* isolate, Handle<FixedArray> indices, uint32_t sort_size, 459 WriteBarrierMode write_barrier_mode = UPDATE_WRITE_BARRIER) { 460 // Use AtomicElement wrapper to ensure that std::sort uses atomic load and 461 // store operations that are safe for concurrent marking. 462 base::AtomicElement<Object*>* start = 463 reinterpret_cast<base::AtomicElement<Object*>*>( 464 indices->GetFirstElementAddress()); 465 std::sort(start, start + sort_size, 466 [isolate](const base::AtomicElement<Object*>& elementA, 467 const base::AtomicElement<Object*>& elementB) { 468 const Object* a = elementA.value(); 469 const Object* b = elementB.value(); 470 if (a->IsSmi() || !a->IsUndefined(isolate)) { 471 if (!b->IsSmi() && b->IsUndefined(isolate)) { 472 return true; 473 } 474 return a->Number() < b->Number(); 475 } 476 return !b->IsSmi() && b->IsUndefined(isolate); 477 }); 478 if (write_barrier_mode != SKIP_WRITE_BARRIER) { 479 FIXED_ARRAY_ELEMENTS_WRITE_BARRIER(isolate->heap(), *indices, 0, sort_size); 480 } 481 } 482 483 static Maybe<bool> IncludesValueSlowPath(Isolate* isolate, 484 Handle<JSObject> receiver, 485 Handle<Object> value, 486 uint32_t start_from, uint32_t length) { 487 bool search_for_hole = value->IsUndefined(isolate); 488 for (uint32_t k = start_from; k < length; ++k) { 489 LookupIterator it(isolate, receiver, k); 490 if (!it.IsFound()) { 491 if (search_for_hole) return Just(true); 492 continue; 493 } 494 Handle<Object> element_k; 495 ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, element_k, 496 Object::GetProperty(&it), Nothing<bool>()); 497 498 if (value->SameValueZero(*element_k)) return Just(true); 499 } 500 501 return Just(false); 502 } 503 504 static Maybe<int64_t> IndexOfValueSlowPath(Isolate* isolate, 505 Handle<JSObject> receiver, 506 Handle<Object> value, 507 uint32_t start_from, 508 uint32_t length) { 509 for (uint32_t k = start_from; k < length; ++k) { 510 LookupIterator it(isolate, receiver, k); 511 if (!it.IsFound()) { 512 continue; 513 } 514 Handle<Object> element_k; 515 ASSIGN_RETURN_ON_EXCEPTION_VALUE( 516 isolate, element_k, Object::GetProperty(&it), Nothing<int64_t>()); 517 518 if (value->StrictEquals(*element_k)) return Just<int64_t>(k); 519 } 520 521 return Just<int64_t>(-1); 522 } 523 524 // The InternalElementsAccessor is a helper class to expose otherwise protected 525 // methods to its subclasses. Namely, we don't want to publicly expose methods 526 // that take an entry (instead of an index) as an argument. 527 class InternalElementsAccessor : public ElementsAccessor { 528 public: 529 explicit InternalElementsAccessor(const char* name) 530 : ElementsAccessor(name) {} 531 532 virtual uint32_t GetEntryForIndex(Isolate* isolate, JSObject* holder, 533 FixedArrayBase* backing_store, 534 uint32_t index) = 0; 535 536 virtual PropertyDetails GetDetails(JSObject* holder, uint32_t entry) = 0; 537 }; 538 539 // Base class for element handler implementations. Contains the 540 // the common logic for objects with different ElementsKinds. 541 // Subclasses must specialize method for which the element 542 // implementation differs from the base class implementation. 543 // 544 // This class is intended to be used in the following way: 545 // 546 // class SomeElementsAccessor : 547 // public ElementsAccessorBase<SomeElementsAccessor, 548 // BackingStoreClass> { 549 // ... 550 // } 551 // 552 // This is an example of the Curiously Recurring Template Pattern (see 553 // http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern). We use 554 // CRTP to guarantee aggressive compile time optimizations (i.e. inlining and 555 // specialization of SomeElementsAccessor methods). 556 template <typename Subclass, typename ElementsTraitsParam> 557 class ElementsAccessorBase : public InternalElementsAccessor { 558 public: 559 explicit ElementsAccessorBase(const char* name) 560 : InternalElementsAccessor(name) {} 561 562 typedef ElementsTraitsParam ElementsTraits; 563 typedef typename ElementsTraitsParam::BackingStore BackingStore; 564 565 static ElementsKind kind() { return ElementsTraits::Kind; } 566 567 static void ValidateContents(JSObject* holder, int length) {} 568 569 static void ValidateImpl(JSObject* holder) { 570 FixedArrayBase* fixed_array_base = holder->elements(); 571 if (!fixed_array_base->IsHeapObject()) return; 572 // Arrays that have been shifted in place can't be verified. 573 if (fixed_array_base->IsFiller()) return; 574 int length = 0; 575 if (holder->IsJSArray()) { 576 Object* length_obj = JSArray::cast(holder)->length(); 577 if (length_obj->IsSmi()) { 578 length = Smi::ToInt(length_obj); 579 } 580 } else { 581 length = fixed_array_base->length(); 582 } 583 Subclass::ValidateContents(holder, length); 584 } 585 586 void Validate(JSObject* holder) final { 587 DisallowHeapAllocation no_gc; 588 Subclass::ValidateImpl(holder); 589 } 590 591 static bool IsPackedImpl(JSObject* holder, FixedArrayBase* backing_store, 592 uint32_t start, uint32_t end) { 593 DisallowHeapAllocation no_gc; 594 if (IsFastPackedElementsKind(kind())) return true; 595 Isolate* isolate = holder->GetIsolate(); 596 for (uint32_t i = start; i < end; i++) { 597 if (!Subclass::HasElementImpl(isolate, holder, i, backing_store, 598 ALL_PROPERTIES)) { 599 return false; 600 } 601 } 602 return true; 603 } 604 605 static void TryTransitionResultArrayToPacked(Handle<JSArray> array) { 606 if (!IsHoleyElementsKind(kind())) return; 607 Handle<FixedArrayBase> backing_store(array->elements(), 608 array->GetIsolate()); 609 int length = Smi::ToInt(array->length()); 610 if (!Subclass::IsPackedImpl(*array, *backing_store, 0, length)) return; 611 612 ElementsKind packed_kind = GetPackedElementsKind(kind()); 613 Handle<Map> new_map = 614 JSObject::GetElementsTransitionMap(array, packed_kind); 615 JSObject::MigrateToMap(array, new_map); 616 if (FLAG_trace_elements_transitions) { 617 JSObject::PrintElementsTransition(stdout, array, kind(), backing_store, 618 packed_kind, backing_store); 619 } 620 } 621 622 bool HasElement(JSObject* holder, uint32_t index, 623 FixedArrayBase* backing_store, PropertyFilter filter) final { 624 return Subclass::HasElementImpl(holder->GetIsolate(), holder, index, 625 backing_store, filter); 626 } 627 628 static bool HasElementImpl(Isolate* isolate, JSObject* holder, uint32_t index, 629 FixedArrayBase* backing_store, 630 PropertyFilter filter = ALL_PROPERTIES) { 631 return Subclass::GetEntryForIndexImpl(isolate, holder, backing_store, index, 632 filter) != kMaxUInt32; 633 } 634 635 bool HasEntry(JSObject* holder, uint32_t entry) final { 636 return Subclass::HasEntryImpl(holder->GetIsolate(), holder->elements(), 637 entry); 638 } 639 640 static bool HasEntryImpl(Isolate* isolate, FixedArrayBase* backing_store, 641 uint32_t entry) { 642 UNIMPLEMENTED(); 643 } 644 645 bool HasAccessors(JSObject* holder) final { 646 return Subclass::HasAccessorsImpl(holder, holder->elements()); 647 } 648 649 static bool HasAccessorsImpl(JSObject* holder, 650 FixedArrayBase* backing_store) { 651 return false; 652 } 653 654 Handle<Object> Get(Handle<JSObject> holder, uint32_t entry) final { 655 return Subclass::GetInternalImpl(holder, entry); 656 } 657 658 static Handle<Object> GetInternalImpl(Handle<JSObject> holder, 659 uint32_t entry) { 660 return Subclass::GetImpl(holder->GetIsolate(), holder->elements(), entry); 661 } 662 663 static Handle<Object> GetImpl(Isolate* isolate, FixedArrayBase* backing_store, 664 uint32_t entry) { 665 uint32_t index = GetIndexForEntryImpl(backing_store, entry); 666 return handle(BackingStore::cast(backing_store)->get(index), isolate); 667 } 668 669 void Set(Handle<JSObject> holder, uint32_t entry, Object* value) final { 670 Subclass::SetImpl(holder, entry, value); 671 } 672 673 void Reconfigure(Handle<JSObject> object, Handle<FixedArrayBase> store, 674 uint32_t entry, Handle<Object> value, 675 PropertyAttributes attributes) final { 676 Subclass::ReconfigureImpl(object, store, entry, value, attributes); 677 } 678 679 static void ReconfigureImpl(Handle<JSObject> object, 680 Handle<FixedArrayBase> store, uint32_t entry, 681 Handle<Object> value, 682 PropertyAttributes attributes) { 683 UNREACHABLE(); 684 } 685 686 void Add(Handle<JSObject> object, uint32_t index, Handle<Object> value, 687 PropertyAttributes attributes, uint32_t new_capacity) final { 688 Subclass::AddImpl(object, index, value, attributes, new_capacity); 689 } 690 691 static void AddImpl(Handle<JSObject> object, uint32_t index, 692 Handle<Object> value, PropertyAttributes attributes, 693 uint32_t new_capacity) { 694 UNREACHABLE(); 695 } 696 697 uint32_t Push(Handle<JSArray> receiver, Arguments* args, 698 uint32_t push_size) final { 699 return Subclass::PushImpl(receiver, args, push_size); 700 } 701 702 static uint32_t PushImpl(Handle<JSArray> receiver, Arguments* args, 703 uint32_t push_sized) { 704 UNREACHABLE(); 705 } 706 707 uint32_t Unshift(Handle<JSArray> receiver, Arguments* args, 708 uint32_t unshift_size) final { 709 return Subclass::UnshiftImpl(receiver, args, unshift_size); 710 } 711 712 static uint32_t UnshiftImpl(Handle<JSArray> receiver, Arguments* args, 713 uint32_t unshift_size) { 714 UNREACHABLE(); 715 } 716 717 Handle<JSObject> Slice(Handle<JSObject> receiver, uint32_t start, 718 uint32_t end) final { 719 return Subclass::SliceImpl(receiver, start, end); 720 } 721 722 static Handle<JSObject> SliceImpl(Handle<JSObject> receiver, uint32_t start, 723 uint32_t end) { 724 UNREACHABLE(); 725 } 726 727 Handle<JSArray> Splice(Handle<JSArray> receiver, uint32_t start, 728 uint32_t delete_count, Arguments* args, 729 uint32_t add_count) final { 730 return Subclass::SpliceImpl(receiver, start, delete_count, args, add_count); 731 } 732 733 static Handle<JSArray> SpliceImpl(Handle<JSArray> receiver, 734 uint32_t start, uint32_t delete_count, 735 Arguments* args, uint32_t add_count) { 736 UNREACHABLE(); 737 } 738 739 Handle<Object> Pop(Handle<JSArray> receiver) final { 740 return Subclass::PopImpl(receiver); 741 } 742 743 static Handle<Object> PopImpl(Handle<JSArray> receiver) { 744 UNREACHABLE(); 745 } 746 747 Handle<Object> Shift(Handle<JSArray> receiver) final { 748 return Subclass::ShiftImpl(receiver); 749 } 750 751 static Handle<Object> ShiftImpl(Handle<JSArray> receiver) { 752 UNREACHABLE(); 753 } 754 755 void SetLength(Handle<JSArray> array, uint32_t length) final { 756 Subclass::SetLengthImpl(array->GetIsolate(), array, length, 757 handle(array->elements(), array->GetIsolate())); 758 } 759 760 static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array, 761 uint32_t length, 762 Handle<FixedArrayBase> backing_store) { 763 DCHECK(!array->SetLengthWouldNormalize(length)); 764 DCHECK(IsFastElementsKind(array->GetElementsKind())); 765 uint32_t old_length = 0; 766 CHECK(array->length()->ToArrayIndex(&old_length)); 767 768 if (old_length < length) { 769 ElementsKind kind = array->GetElementsKind(); 770 if (!IsHoleyElementsKind(kind)) { 771 kind = GetHoleyElementsKind(kind); 772 JSObject::TransitionElementsKind(array, kind); 773 } 774 } 775 776 // Check whether the backing store should be shrunk. 777 uint32_t capacity = backing_store->length(); 778 old_length = Min(old_length, capacity); 779 if (length == 0) { 780 array->initialize_elements(); 781 } else if (length <= capacity) { 782 if (IsSmiOrObjectElementsKind(kind())) { 783 JSObject::EnsureWritableFastElements(array); 784 if (array->elements() != *backing_store) { 785 backing_store = handle(array->elements(), isolate); 786 } 787 } 788 if (2 * length + JSObject::kMinAddedElementsCapacity <= capacity) { 789 // If more than half the elements won't be used, trim the array. 790 // Do not trim from short arrays to prevent frequent trimming on 791 // repeated pop operations. 792 // Leave some space to allow for subsequent push operations. 793 int elements_to_trim = length + 1 == old_length 794 ? (capacity - length) / 2 795 : capacity - length; 796 isolate->heap()->RightTrimFixedArray(*backing_store, elements_to_trim); 797 // Fill the non-trimmed elements with holes. 798 BackingStore::cast(*backing_store) 799 ->FillWithHoles(length, 800 std::min(old_length, capacity - elements_to_trim)); 801 } else { 802 // Otherwise, fill the unused tail with holes. 803 BackingStore::cast(*backing_store)->FillWithHoles(length, old_length); 804 } 805 } else { 806 // Check whether the backing store should be expanded. 807 capacity = Max(length, JSObject::NewElementsCapacity(capacity)); 808 Subclass::GrowCapacityAndConvertImpl(array, capacity); 809 } 810 811 array->set_length(Smi::FromInt(length)); 812 JSObject::ValidateElements(*array); 813 } 814 815 uint32_t NumberOfElements(JSObject* receiver) final { 816 return Subclass::NumberOfElementsImpl(receiver, receiver->elements()); 817 } 818 819 static uint32_t NumberOfElementsImpl(JSObject* receiver, 820 FixedArrayBase* backing_store) { 821 UNREACHABLE(); 822 } 823 824 static uint32_t GetMaxIndex(JSObject* receiver, FixedArrayBase* elements) { 825 if (receiver->IsJSArray()) { 826 DCHECK(JSArray::cast(receiver)->length()->IsSmi()); 827 return static_cast<uint32_t>( 828 Smi::ToInt(JSArray::cast(receiver)->length())); 829 } 830 return Subclass::GetCapacityImpl(receiver, elements); 831 } 832 833 static uint32_t GetMaxNumberOfEntries(JSObject* receiver, 834 FixedArrayBase* elements) { 835 return Subclass::GetMaxIndex(receiver, elements); 836 } 837 838 static Handle<FixedArrayBase> ConvertElementsWithCapacity( 839 Handle<JSObject> object, Handle<FixedArrayBase> old_elements, 840 ElementsKind from_kind, uint32_t capacity) { 841 return ConvertElementsWithCapacity( 842 object, old_elements, from_kind, capacity, 0, 0, 843 ElementsAccessor::kCopyToEndAndInitializeToHole); 844 } 845 846 static Handle<FixedArrayBase> ConvertElementsWithCapacity( 847 Handle<JSObject> object, Handle<FixedArrayBase> old_elements, 848 ElementsKind from_kind, uint32_t capacity, int copy_size) { 849 return ConvertElementsWithCapacity(object, old_elements, from_kind, 850 capacity, 0, 0, copy_size); 851 } 852 853 static Handle<FixedArrayBase> ConvertElementsWithCapacity( 854 Handle<JSObject> object, Handle<FixedArrayBase> old_elements, 855 ElementsKind from_kind, uint32_t capacity, uint32_t src_index, 856 uint32_t dst_index, int copy_size) { 857 Isolate* isolate = object->GetIsolate(); 858 Handle<FixedArrayBase> new_elements; 859 if (IsDoubleElementsKind(kind())) { 860 new_elements = isolate->factory()->NewFixedDoubleArray(capacity); 861 } else { 862 new_elements = isolate->factory()->NewUninitializedFixedArray(capacity); 863 } 864 865 int packed_size = kPackedSizeNotKnown; 866 if (IsFastPackedElementsKind(from_kind) && object->IsJSArray()) { 867 packed_size = Smi::ToInt(JSArray::cast(*object)->length()); 868 } 869 870 Subclass::CopyElementsImpl(isolate, *old_elements, src_index, *new_elements, 871 from_kind, dst_index, packed_size, copy_size); 872 873 return new_elements; 874 } 875 876 static void TransitionElementsKindImpl(Handle<JSObject> object, 877 Handle<Map> to_map) { 878 Handle<Map> from_map = handle(object->map(), object->GetIsolate()); 879 ElementsKind from_kind = from_map->elements_kind(); 880 ElementsKind to_kind = to_map->elements_kind(); 881 if (IsHoleyElementsKind(from_kind)) { 882 to_kind = GetHoleyElementsKind(to_kind); 883 } 884 if (from_kind != to_kind) { 885 // This method should never be called for any other case. 886 DCHECK(IsFastElementsKind(from_kind)); 887 DCHECK(IsFastElementsKind(to_kind)); 888 DCHECK_NE(TERMINAL_FAST_ELEMENTS_KIND, from_kind); 889 890 Handle<FixedArrayBase> from_elements(object->elements(), 891 object->GetIsolate()); 892 if (object->elements() == 893 object->GetReadOnlyRoots().empty_fixed_array() || 894 IsDoubleElementsKind(from_kind) == IsDoubleElementsKind(to_kind)) { 895 // No change is needed to the elements() buffer, the transition 896 // only requires a map change. 897 JSObject::MigrateToMap(object, to_map); 898 } else { 899 DCHECK( 900 (IsSmiElementsKind(from_kind) && IsDoubleElementsKind(to_kind)) || 901 (IsDoubleElementsKind(from_kind) && IsObjectElementsKind(to_kind))); 902 uint32_t capacity = static_cast<uint32_t>(object->elements()->length()); 903 Handle<FixedArrayBase> elements = ConvertElementsWithCapacity( 904 object, from_elements, from_kind, capacity); 905 JSObject::SetMapAndElements(object, to_map, elements); 906 } 907 if (FLAG_trace_elements_transitions) { 908 JSObject::PrintElementsTransition( 909 stdout, object, from_kind, from_elements, to_kind, 910 handle(object->elements(), object->GetIsolate())); 911 } 912 } 913 } 914 915 static void GrowCapacityAndConvertImpl(Handle<JSObject> object, 916 uint32_t capacity) { 917 ElementsKind from_kind = object->GetElementsKind(); 918 if (IsSmiOrObjectElementsKind(from_kind)) { 919 // Array optimizations rely on the prototype lookups of Array objects 920 // always returning undefined. If there is a store to the initial 921 // prototype object, make sure all of these optimizations are invalidated. 922 object->GetIsolate()->UpdateNoElementsProtectorOnSetLength(object); 923 } 924 Handle<FixedArrayBase> old_elements(object->elements(), 925 object->GetIsolate()); 926 // This method should only be called if there's a reason to update the 927 // elements. 928 DCHECK(IsDoubleElementsKind(from_kind) != IsDoubleElementsKind(kind()) || 929 IsDictionaryElementsKind(from_kind) || 930 static_cast<uint32_t>(old_elements->length()) < capacity); 931 Subclass::BasicGrowCapacityAndConvertImpl(object, old_elements, from_kind, 932 kind(), capacity); 933 } 934 935 static void BasicGrowCapacityAndConvertImpl( 936 Handle<JSObject> object, Handle<FixedArrayBase> old_elements, 937 ElementsKind from_kind, ElementsKind to_kind, uint32_t capacity) { 938 Handle<FixedArrayBase> elements = 939 ConvertElementsWithCapacity(object, old_elements, from_kind, capacity); 940 941 if (IsHoleyElementsKind(from_kind)) { 942 to_kind = GetHoleyElementsKind(to_kind); 943 } 944 Handle<Map> new_map = JSObject::GetElementsTransitionMap(object, to_kind); 945 JSObject::SetMapAndElements(object, new_map, elements); 946 947 // Transition through the allocation site as well if present. 948 JSObject::UpdateAllocationSite(object, to_kind); 949 950 if (FLAG_trace_elements_transitions) { 951 JSObject::PrintElementsTransition(stdout, object, from_kind, old_elements, 952 to_kind, elements); 953 } 954 } 955 956 void TransitionElementsKind(Handle<JSObject> object, Handle<Map> map) final { 957 Subclass::TransitionElementsKindImpl(object, map); 958 } 959 960 void GrowCapacityAndConvert(Handle<JSObject> object, 961 uint32_t capacity) final { 962 Subclass::GrowCapacityAndConvertImpl(object, capacity); 963 } 964 965 bool GrowCapacity(Handle<JSObject> object, uint32_t index) final { 966 // This function is intended to be called from optimized code. We don't 967 // want to trigger lazy deopts there, so refuse to handle cases that would. 968 if (object->map()->is_prototype_map() || 969 object->WouldConvertToSlowElements(index)) { 970 return false; 971 } 972 Handle<FixedArrayBase> old_elements(object->elements(), 973 object->GetIsolate()); 974 uint32_t new_capacity = JSObject::NewElementsCapacity(index + 1); 975 DCHECK(static_cast<uint32_t>(old_elements->length()) < new_capacity); 976 Handle<FixedArrayBase> elements = 977 ConvertElementsWithCapacity(object, old_elements, kind(), new_capacity); 978 979 DCHECK_EQ(object->GetElementsKind(), kind()); 980 // Transition through the allocation site as well if present. 981 if (JSObject::UpdateAllocationSite<AllocationSiteUpdateMode::kCheckOnly>( 982 object, kind())) { 983 return false; 984 } 985 986 object->set_elements(*elements); 987 return true; 988 } 989 990 void Delete(Handle<JSObject> obj, uint32_t entry) final { 991 Subclass::DeleteImpl(obj, entry); 992 } 993 994 static void CopyElementsImpl(Isolate* isolate, FixedArrayBase* from, 995 uint32_t from_start, FixedArrayBase* to, 996 ElementsKind from_kind, uint32_t to_start, 997 int packed_size, int copy_size) { 998 UNREACHABLE(); 999 } 1000 1001 void CopyElements(JSObject* from_holder, uint32_t from_start, 1002 ElementsKind from_kind, Handle<FixedArrayBase> to, 1003 uint32_t to_start, int copy_size) final { 1004 int packed_size = kPackedSizeNotKnown; 1005 bool is_packed = IsFastPackedElementsKind(from_kind) && 1006 from_holder->IsJSArray(); 1007 if (is_packed) { 1008 packed_size = Smi::ToInt(JSArray::cast(from_holder)->length()); 1009 if (copy_size >= 0 && packed_size > copy_size) { 1010 packed_size = copy_size; 1011 } 1012 } 1013 FixedArrayBase* from = from_holder->elements(); 1014 // NOTE: the Subclass::CopyElementsImpl() methods 1015 // violate the handlified function signature convention: 1016 // raw pointer parameters in the function that allocates. This is done 1017 // intentionally to avoid ArrayConcat() builtin performance degradation. 1018 // 1019 // Details: The idea is that allocations actually happen only in case of 1020 // copying from object with fast double elements to object with object 1021 // elements. In all the other cases there are no allocations performed and 1022 // handle creation causes noticeable performance degradation of the builtin. 1023 Subclass::CopyElementsImpl(from_holder->GetIsolate(), from, from_start, *to, 1024 from_kind, to_start, packed_size, copy_size); 1025 } 1026 1027 void CopyElements(Isolate* isolate, Handle<FixedArrayBase> source, 1028 ElementsKind source_kind, 1029 Handle<FixedArrayBase> destination, int size) { 1030 Subclass::CopyElementsImpl(isolate, *source, 0, *destination, source_kind, 1031 0, kPackedSizeNotKnown, size); 1032 } 1033 1034 void CopyTypedArrayElementsSlice(JSTypedArray* source, 1035 JSTypedArray* destination, size_t start, 1036 size_t end) { 1037 Subclass::CopyTypedArrayElementsSliceImpl(source, destination, start, end); 1038 } 1039 1040 static void CopyTypedArrayElementsSliceImpl(JSTypedArray* source, 1041 JSTypedArray* destination, 1042 size_t start, size_t end) { 1043 UNREACHABLE(); 1044 } 1045 1046 Object* CopyElements(Handle<Object> source, Handle<JSObject> destination, 1047 size_t length, uint32_t offset) final { 1048 return Subclass::CopyElementsHandleImpl(source, destination, length, 1049 offset); 1050 } 1051 1052 static Object* CopyElementsHandleImpl(Handle<Object> source, 1053 Handle<JSObject> destination, 1054 size_t length, uint32_t offset) { 1055 UNREACHABLE(); 1056 } 1057 1058 Handle<NumberDictionary> Normalize(Handle<JSObject> object) final { 1059 return Subclass::NormalizeImpl( 1060 object, handle(object->elements(), object->GetIsolate())); 1061 } 1062 1063 static Handle<NumberDictionary> NormalizeImpl( 1064 Handle<JSObject> object, Handle<FixedArrayBase> elements) { 1065 UNREACHABLE(); 1066 } 1067 1068 Maybe<bool> CollectValuesOrEntries(Isolate* isolate, Handle<JSObject> object, 1069 Handle<FixedArray> values_or_entries, 1070 bool get_entries, int* nof_items, 1071 PropertyFilter filter) { 1072 return Subclass::CollectValuesOrEntriesImpl( 1073 isolate, object, values_or_entries, get_entries, nof_items, filter); 1074 } 1075 1076 static Maybe<bool> CollectValuesOrEntriesImpl( 1077 Isolate* isolate, Handle<JSObject> object, 1078 Handle<FixedArray> values_or_entries, bool get_entries, int* nof_items, 1079 PropertyFilter filter) { 1080 DCHECK_EQ(*nof_items, 0); 1081 KeyAccumulator accumulator(isolate, KeyCollectionMode::kOwnOnly, 1082 ALL_PROPERTIES); 1083 Subclass::CollectElementIndicesImpl( 1084 object, handle(object->elements(), isolate), &accumulator); 1085 Handle<FixedArray> keys = accumulator.GetKeys(); 1086 1087 int count = 0; 1088 int i = 0; 1089 ElementsKind original_elements_kind = object->GetElementsKind(); 1090 1091 for (; i < keys->length(); ++i) { 1092 Handle<Object> key(keys->get(i), isolate); 1093 uint32_t index; 1094 if (!key->ToUint32(&index)) continue; 1095 1096 DCHECK_EQ(object->GetElementsKind(), original_elements_kind); 1097 uint32_t entry = Subclass::GetEntryForIndexImpl( 1098 isolate, *object, object->elements(), index, filter); 1099 if (entry == kMaxUInt32) continue; 1100 PropertyDetails details = Subclass::GetDetailsImpl(*object, entry); 1101 1102 Handle<Object> value; 1103 if (details.kind() == kData) { 1104 value = Subclass::GetImpl(isolate, object->elements(), entry); 1105 } else { 1106 // This might modify the elements and/or change the elements kind. 1107 LookupIterator it(isolate, object, index, LookupIterator::OWN); 1108 ASSIGN_RETURN_ON_EXCEPTION_VALUE( 1109 isolate, value, Object::GetProperty(&it), Nothing<bool>()); 1110 } 1111 if (get_entries) value = MakeEntryPair(isolate, index, value); 1112 values_or_entries->set(count++, *value); 1113 if (object->GetElementsKind() != original_elements_kind) break; 1114 } 1115 1116 // Slow path caused by changes in elements kind during iteration. 1117 for (; i < keys->length(); i++) { 1118 Handle<Object> key(keys->get(i), isolate); 1119 uint32_t index; 1120 if (!key->ToUint32(&index)) continue; 1121 1122 if (filter & ONLY_ENUMERABLE) { 1123 InternalElementsAccessor* accessor = 1124 reinterpret_cast<InternalElementsAccessor*>( 1125 object->GetElementsAccessor()); 1126 uint32_t entry = accessor->GetEntryForIndex(isolate, *object, 1127 object->elements(), index); 1128 if (entry == kMaxUInt32) continue; 1129 PropertyDetails details = accessor->GetDetails(*object, entry); 1130 if (!details.IsEnumerable()) continue; 1131 } 1132 1133 Handle<Object> value; 1134 LookupIterator it(isolate, object, index, LookupIterator::OWN); 1135 ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, value, Object::GetProperty(&it), 1136 Nothing<bool>()); 1137 1138 if (get_entries) value = MakeEntryPair(isolate, index, value); 1139 values_or_entries->set(count++, *value); 1140 } 1141 1142 *nof_items = count; 1143 return Just(true); 1144 } 1145 1146 void CollectElementIndices(Handle<JSObject> object, 1147 Handle<FixedArrayBase> backing_store, 1148 KeyAccumulator* keys) final { 1149 if (keys->filter() & ONLY_ALL_CAN_READ) return; 1150 Subclass::CollectElementIndicesImpl(object, backing_store, keys); 1151 } 1152 1153 static void CollectElementIndicesImpl(Handle<JSObject> object, 1154 Handle<FixedArrayBase> backing_store, 1155 KeyAccumulator* keys) { 1156 DCHECK_NE(DICTIONARY_ELEMENTS, kind()); 1157 // Non-dictionary elements can't have all-can-read accessors. 1158 uint32_t length = Subclass::GetMaxIndex(*object, *backing_store); 1159 PropertyFilter filter = keys->filter(); 1160 Isolate* isolate = keys->isolate(); 1161 Factory* factory = isolate->factory(); 1162 for (uint32_t i = 0; i < length; i++) { 1163 if (Subclass::HasElementImpl(isolate, *object, i, *backing_store, 1164 filter)) { 1165 keys->AddKey(factory->NewNumberFromUint(i)); 1166 } 1167 } 1168 } 1169 1170 static Handle<FixedArray> DirectCollectElementIndicesImpl( 1171 Isolate* isolate, Handle<JSObject> object, 1172 Handle<FixedArrayBase> backing_store, GetKeysConversion convert, 1173 PropertyFilter filter, Handle<FixedArray> list, uint32_t* nof_indices, 1174 uint32_t insertion_index = 0) { 1175 uint32_t length = Subclass::GetMaxIndex(*object, *backing_store); 1176 uint32_t const kMaxStringTableEntries = 1177 isolate->heap()->MaxNumberToStringCacheSize(); 1178 for (uint32_t i = 0; i < length; i++) { 1179 if (Subclass::HasElementImpl(isolate, *object, i, *backing_store, 1180 filter)) { 1181 if (convert == GetKeysConversion::kConvertToString) { 1182 bool use_cache = i < kMaxStringTableEntries; 1183 Handle<String> index_string = 1184 isolate->factory()->Uint32ToString(i, use_cache); 1185 list->set(insertion_index, *index_string); 1186 } else { 1187 list->set(insertion_index, Smi::FromInt(i), SKIP_WRITE_BARRIER); 1188 } 1189 insertion_index++; 1190 } 1191 } 1192 *nof_indices = insertion_index; 1193 return list; 1194 } 1195 1196 MaybeHandle<FixedArray> PrependElementIndices( 1197 Handle<JSObject> object, Handle<FixedArrayBase> backing_store, 1198 Handle<FixedArray> keys, GetKeysConversion convert, 1199 PropertyFilter filter) final { 1200 return Subclass::PrependElementIndicesImpl(object, backing_store, keys, 1201 convert, filter); 1202 } 1203 1204 static MaybeHandle<FixedArray> PrependElementIndicesImpl( 1205 Handle<JSObject> object, Handle<FixedArrayBase> backing_store, 1206 Handle<FixedArray> keys, GetKeysConversion convert, 1207 PropertyFilter filter) { 1208 Isolate* isolate = object->GetIsolate(); 1209 uint32_t nof_property_keys = keys->length(); 1210 uint32_t initial_list_length = 1211 Subclass::GetMaxNumberOfEntries(*object, *backing_store); 1212 1213 initial_list_length += nof_property_keys; 1214 if (initial_list_length > FixedArray::kMaxLength || 1215 initial_list_length < nof_property_keys) { 1216 return isolate->Throw<FixedArray>(isolate->factory()->NewRangeError( 1217 MessageTemplate::kInvalidArrayLength)); 1218 } 1219 1220 // Collect the element indices into a new list. 1221 MaybeHandle<FixedArray> raw_array = 1222 isolate->factory()->TryNewFixedArray(initial_list_length); 1223 Handle<FixedArray> combined_keys; 1224 1225 // If we have a holey backing store try to precisely estimate the backing 1226 // store size as a last emergency measure if we cannot allocate the big 1227 // array. 1228 if (!raw_array.ToHandle(&combined_keys)) { 1229 if (IsHoleyOrDictionaryElementsKind(kind())) { 1230 // If we overestimate the result list size we might end up in the 1231 // large-object space which doesn't free memory on shrinking the list. 1232 // Hence we try to estimate the final size for holey backing stores more 1233 // precisely here. 1234 initial_list_length = 1235 Subclass::NumberOfElementsImpl(*object, *backing_store); 1236 initial_list_length += nof_property_keys; 1237 } 1238 combined_keys = isolate->factory()->NewFixedArray(initial_list_length); 1239 } 1240 1241 uint32_t nof_indices = 0; 1242 bool needs_sorting = IsDictionaryElementsKind(kind()) || 1243 IsSloppyArgumentsElementsKind(kind()); 1244 combined_keys = Subclass::DirectCollectElementIndicesImpl( 1245 isolate, object, backing_store, 1246 needs_sorting ? GetKeysConversion::kKeepNumbers : convert, filter, 1247 combined_keys, &nof_indices); 1248 1249 if (needs_sorting) { 1250 SortIndices(isolate, combined_keys, nof_indices); 1251 // Indices from dictionary elements should only be converted after 1252 // sorting. 1253 if (convert == GetKeysConversion::kConvertToString) { 1254 for (uint32_t i = 0; i < nof_indices; i++) { 1255 Handle<Object> index_string = isolate->factory()->Uint32ToString( 1256 combined_keys->get(i)->Number()); 1257 combined_keys->set(i, *index_string); 1258 } 1259 } 1260 } 1261 1262 // Copy over the passed-in property keys. 1263 CopyObjectToObjectElements(isolate, *keys, PACKED_ELEMENTS, 0, 1264 *combined_keys, PACKED_ELEMENTS, nof_indices, 1265 nof_property_keys); 1266 1267 // For holey elements and arguments we might have to shrink the collected 1268 // keys since the estimates might be off. 1269 if (IsHoleyOrDictionaryElementsKind(kind()) || 1270 IsSloppyArgumentsElementsKind(kind())) { 1271 // Shrink combined_keys to the final size. 1272 int final_size = nof_indices + nof_property_keys; 1273 DCHECK_LE(final_size, combined_keys->length()); 1274 return FixedArray::ShrinkOrEmpty(isolate, combined_keys, final_size); 1275 } 1276 1277 return combined_keys; 1278 } 1279 1280 void AddElementsToKeyAccumulator(Handle<JSObject> receiver, 1281 KeyAccumulator* accumulator, 1282 AddKeyConversion convert) final { 1283 Subclass::AddElementsToKeyAccumulatorImpl(receiver, accumulator, convert); 1284 } 1285 1286 static uint32_t GetCapacityImpl(JSObject* holder, 1287 FixedArrayBase* backing_store) { 1288 return backing_store->length(); 1289 } 1290 1291 uint32_t GetCapacity(JSObject* holder, FixedArrayBase* backing_store) final { 1292 return Subclass::GetCapacityImpl(holder, backing_store); 1293 } 1294 1295 static Object* FillImpl(Handle<JSObject> receiver, Handle<Object> obj_value, 1296 uint32_t start, uint32_t end) { 1297 UNREACHABLE(); 1298 } 1299 1300 Object* Fill(Handle<JSObject> receiver, Handle<Object> obj_value, 1301 uint32_t start, uint32_t end) { 1302 return Subclass::FillImpl(receiver, obj_value, start, end); 1303 } 1304 1305 static Maybe<bool> IncludesValueImpl(Isolate* isolate, 1306 Handle<JSObject> receiver, 1307 Handle<Object> value, 1308 uint32_t start_from, uint32_t length) { 1309 return IncludesValueSlowPath(isolate, receiver, value, start_from, length); 1310 } 1311 1312 Maybe<bool> IncludesValue(Isolate* isolate, Handle<JSObject> receiver, 1313 Handle<Object> value, uint32_t start_from, 1314 uint32_t length) final { 1315 return Subclass::IncludesValueImpl(isolate, receiver, value, start_from, 1316 length); 1317 } 1318 1319 static Maybe<int64_t> IndexOfValueImpl(Isolate* isolate, 1320 Handle<JSObject> receiver, 1321 Handle<Object> value, 1322 uint32_t start_from, uint32_t length) { 1323 return IndexOfValueSlowPath(isolate, receiver, value, start_from, length); 1324 } 1325 1326 Maybe<int64_t> IndexOfValue(Isolate* isolate, Handle<JSObject> receiver, 1327 Handle<Object> value, uint32_t start_from, 1328 uint32_t length) final { 1329 return Subclass::IndexOfValueImpl(isolate, receiver, value, start_from, 1330 length); 1331 } 1332 1333 static Maybe<int64_t> LastIndexOfValueImpl(Handle<JSObject> receiver, 1334 Handle<Object> value, 1335 uint32_t start_from) { 1336 UNREACHABLE(); 1337 } 1338 1339 Maybe<int64_t> LastIndexOfValue(Handle<JSObject> receiver, 1340 Handle<Object> value, 1341 uint32_t start_from) final { 1342 return Subclass::LastIndexOfValueImpl(receiver, value, start_from); 1343 } 1344 1345 static void ReverseImpl(JSObject* receiver) { UNREACHABLE(); } 1346 1347 void Reverse(JSObject* receiver) final { Subclass::ReverseImpl(receiver); } 1348 1349 static uint32_t GetIndexForEntryImpl(FixedArrayBase* backing_store, 1350 uint32_t entry) { 1351 return entry; 1352 } 1353 1354 static uint32_t GetEntryForIndexImpl(Isolate* isolate, JSObject* holder, 1355 FixedArrayBase* backing_store, 1356 uint32_t index, PropertyFilter filter) { 1357 DCHECK(IsFastElementsKind(kind())); 1358 uint32_t length = Subclass::GetMaxIndex(holder, backing_store); 1359 if (IsHoleyElementsKind(kind())) { 1360 return index < length && 1361 !BackingStore::cast(backing_store) 1362 ->is_the_hole(isolate, index) 1363 ? index 1364 : kMaxUInt32; 1365 } else { 1366 return index < length ? index : kMaxUInt32; 1367 } 1368 } 1369 1370 uint32_t GetEntryForIndex(Isolate* isolate, JSObject* holder, 1371 FixedArrayBase* backing_store, 1372 uint32_t index) final { 1373 return Subclass::GetEntryForIndexImpl(isolate, holder, backing_store, index, 1374 ALL_PROPERTIES); 1375 } 1376 1377 static PropertyDetails GetDetailsImpl(FixedArrayBase* backing_store, 1378 uint32_t entry) { 1379 return PropertyDetails(kData, NONE, PropertyCellType::kNoCell); 1380 } 1381 1382 static PropertyDetails GetDetailsImpl(JSObject* holder, uint32_t entry) { 1383 return PropertyDetails(kData, NONE, PropertyCellType::kNoCell); 1384 } 1385 1386 PropertyDetails GetDetails(JSObject* holder, uint32_t entry) final { 1387 return Subclass::GetDetailsImpl(holder, entry); 1388 } 1389 1390 Handle<FixedArray> CreateListFromArrayLike(Isolate* isolate, 1391 Handle<JSObject> object, 1392 uint32_t length) final { 1393 return Subclass::CreateListFromArrayLikeImpl(isolate, object, length); 1394 }; 1395 1396 static Handle<FixedArray> CreateListFromArrayLikeImpl(Isolate* isolate, 1397 Handle<JSObject> object, 1398 uint32_t length) { 1399 UNREACHABLE(); 1400 } 1401 1402 private: 1403 DISALLOW_COPY_AND_ASSIGN(ElementsAccessorBase); 1404 }; 1405 1406 1407 class DictionaryElementsAccessor 1408 : public ElementsAccessorBase<DictionaryElementsAccessor, 1409 ElementsKindTraits<DICTIONARY_ELEMENTS> > { 1410 public: 1411 explicit DictionaryElementsAccessor(const char* name) 1412 : ElementsAccessorBase<DictionaryElementsAccessor, 1413 ElementsKindTraits<DICTIONARY_ELEMENTS> >(name) {} 1414 1415 static uint32_t GetMaxIndex(JSObject* receiver, FixedArrayBase* elements) { 1416 // We cannot properly estimate this for dictionaries. 1417 UNREACHABLE(); 1418 } 1419 1420 static uint32_t GetMaxNumberOfEntries(JSObject* receiver, 1421 FixedArrayBase* backing_store) { 1422 return NumberOfElementsImpl(receiver, backing_store); 1423 } 1424 1425 static uint32_t NumberOfElementsImpl(JSObject* receiver, 1426 FixedArrayBase* backing_store) { 1427 NumberDictionary* dict = NumberDictionary::cast(backing_store); 1428 return dict->NumberOfElements(); 1429 } 1430 1431 static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array, 1432 uint32_t length, 1433 Handle<FixedArrayBase> backing_store) { 1434 Handle<NumberDictionary> dict = 1435 Handle<NumberDictionary>::cast(backing_store); 1436 int capacity = dict->Capacity(); 1437 uint32_t old_length = 0; 1438 CHECK(array->length()->ToArrayLength(&old_length)); 1439 { 1440 DisallowHeapAllocation no_gc; 1441 ReadOnlyRoots roots(isolate); 1442 if (length < old_length) { 1443 if (dict->requires_slow_elements()) { 1444 // Find last non-deletable element in range of elements to be 1445 // deleted and adjust range accordingly. 1446 for (int entry = 0; entry < capacity; entry++) { 1447 Object* index = dict->KeyAt(entry); 1448 if (dict->IsKey(roots, index)) { 1449 uint32_t number = static_cast<uint32_t>(index->Number()); 1450 if (length <= number && number < old_length) { 1451 PropertyDetails details = dict->DetailsAt(entry); 1452 if (!details.IsConfigurable()) length = number + 1; 1453 } 1454 } 1455 } 1456 } 1457 1458 if (length == 0) { 1459 // Flush the backing store. 1460 array->initialize_elements(); 1461 } else { 1462 // Remove elements that should be deleted. 1463 int removed_entries = 0; 1464 for (int entry = 0; entry < capacity; entry++) { 1465 Object* index = dict->KeyAt(entry); 1466 if (dict->IsKey(roots, index)) { 1467 uint32_t number = static_cast<uint32_t>(index->Number()); 1468 if (length <= number && number < old_length) { 1469 dict->ClearEntry(isolate, entry); 1470 removed_entries++; 1471 } 1472 } 1473 } 1474 1475 if (removed_entries > 0) { 1476 // Update the number of elements. 1477 dict->ElementsRemoved(removed_entries); 1478 } 1479 } 1480 } 1481 } 1482 1483 Handle<Object> length_obj = isolate->factory()->NewNumberFromUint(length); 1484 array->set_length(*length_obj); 1485 } 1486 1487 static void CopyElementsImpl(Isolate* isolate, FixedArrayBase* from, 1488 uint32_t from_start, FixedArrayBase* to, 1489 ElementsKind from_kind, uint32_t to_start, 1490 int packed_size, int copy_size) { 1491 UNREACHABLE(); 1492 } 1493 1494 static Handle<JSObject> SliceImpl(Handle<JSObject> receiver, uint32_t start, 1495 uint32_t end) { 1496 Isolate* isolate = receiver->GetIsolate(); 1497 uint32_t result_length = end < start ? 0u : end - start; 1498 1499 // Result must also be a dictionary. 1500 Handle<JSArray> result_array = 1501 isolate->factory()->NewJSArray(0, HOLEY_ELEMENTS); 1502 JSObject::NormalizeElements(result_array); 1503 result_array->set_length(Smi::FromInt(result_length)); 1504 Handle<NumberDictionary> source_dict( 1505 NumberDictionary::cast(receiver->elements()), isolate); 1506 int entry_count = source_dict->Capacity(); 1507 ReadOnlyRoots roots(isolate); 1508 for (int i = 0; i < entry_count; i++) { 1509 Object* key = source_dict->KeyAt(i); 1510 if (!source_dict->ToKey(roots, i, &key)) continue; 1511 uint64_t key_value = NumberToInt64(key); 1512 if (key_value >= start && key_value < end) { 1513 Handle<NumberDictionary> dest_dict( 1514 NumberDictionary::cast(result_array->elements()), isolate); 1515 Handle<Object> value(source_dict->ValueAt(i), isolate); 1516 PropertyDetails details = source_dict->DetailsAt(i); 1517 PropertyAttributes attr = details.attributes(); 1518 AddImpl(result_array, static_cast<uint32_t>(key_value) - start, value, 1519 attr, 0); 1520 } 1521 } 1522 1523 return result_array; 1524 } 1525 1526 static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) { 1527 Handle<NumberDictionary> dict(NumberDictionary::cast(obj->elements()), 1528 obj->GetIsolate()); 1529 dict = NumberDictionary::DeleteEntry(obj->GetIsolate(), dict, entry); 1530 obj->set_elements(*dict); 1531 } 1532 1533 static bool HasAccessorsImpl(JSObject* holder, 1534 FixedArrayBase* backing_store) { 1535 DisallowHeapAllocation no_gc; 1536 NumberDictionary* dict = NumberDictionary::cast(backing_store); 1537 if (!dict->requires_slow_elements()) return false; 1538 int capacity = dict->Capacity(); 1539 ReadOnlyRoots roots = holder->GetReadOnlyRoots(); 1540 for (int i = 0; i < capacity; i++) { 1541 Object* key = dict->KeyAt(i); 1542 if (!dict->IsKey(roots, key)) continue; 1543 PropertyDetails details = dict->DetailsAt(i); 1544 if (details.kind() == kAccessor) return true; 1545 } 1546 return false; 1547 } 1548 1549 static Object* GetRaw(FixedArrayBase* store, uint32_t entry) { 1550 NumberDictionary* backing_store = NumberDictionary::cast(store); 1551 return backing_store->ValueAt(entry); 1552 } 1553 1554 static Handle<Object> GetImpl(Isolate* isolate, FixedArrayBase* backing_store, 1555 uint32_t entry) { 1556 return handle(GetRaw(backing_store, entry), isolate); 1557 } 1558 1559 static inline void SetImpl(Handle<JSObject> holder, uint32_t entry, 1560 Object* value) { 1561 SetImpl(holder->elements(), entry, value); 1562 } 1563 1564 static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry, 1565 Object* value) { 1566 NumberDictionary::cast(backing_store)->ValueAtPut(entry, value); 1567 } 1568 1569 static void ReconfigureImpl(Handle<JSObject> object, 1570 Handle<FixedArrayBase> store, uint32_t entry, 1571 Handle<Object> value, 1572 PropertyAttributes attributes) { 1573 NumberDictionary* dictionary = NumberDictionary::cast(*store); 1574 if (attributes != NONE) object->RequireSlowElements(dictionary); 1575 dictionary->ValueAtPut(entry, *value); 1576 PropertyDetails details = dictionary->DetailsAt(entry); 1577 details = PropertyDetails(kData, attributes, PropertyCellType::kNoCell, 1578 details.dictionary_index()); 1579 1580 dictionary->DetailsAtPut(object->GetIsolate(), entry, details); 1581 } 1582 1583 static void AddImpl(Handle<JSObject> object, uint32_t index, 1584 Handle<Object> value, PropertyAttributes attributes, 1585 uint32_t new_capacity) { 1586 PropertyDetails details(kData, attributes, PropertyCellType::kNoCell); 1587 Handle<NumberDictionary> dictionary = 1588 object->HasFastElements() || object->HasFastStringWrapperElements() 1589 ? JSObject::NormalizeElements(object) 1590 : handle(NumberDictionary::cast(object->elements()), 1591 object->GetIsolate()); 1592 Handle<NumberDictionary> new_dictionary = NumberDictionary::Add( 1593 object->GetIsolate(), dictionary, index, value, details); 1594 new_dictionary->UpdateMaxNumberKey(index, object); 1595 if (attributes != NONE) object->RequireSlowElements(*new_dictionary); 1596 if (dictionary.is_identical_to(new_dictionary)) return; 1597 object->set_elements(*new_dictionary); 1598 } 1599 1600 static bool HasEntryImpl(Isolate* isolate, FixedArrayBase* store, 1601 uint32_t entry) { 1602 DisallowHeapAllocation no_gc; 1603 NumberDictionary* dict = NumberDictionary::cast(store); 1604 Object* index = dict->KeyAt(entry); 1605 return !index->IsTheHole(isolate); 1606 } 1607 1608 static uint32_t GetIndexForEntryImpl(FixedArrayBase* store, uint32_t entry) { 1609 DisallowHeapAllocation no_gc; 1610 NumberDictionary* dict = NumberDictionary::cast(store); 1611 uint32_t result = 0; 1612 CHECK(dict->KeyAt(entry)->ToArrayIndex(&result)); 1613 return result; 1614 } 1615 1616 static uint32_t GetEntryForIndexImpl(Isolate* isolate, JSObject* holder, 1617 FixedArrayBase* store, uint32_t index, 1618 PropertyFilter filter) { 1619 DisallowHeapAllocation no_gc; 1620 NumberDictionary* dictionary = NumberDictionary::cast(store); 1621 int entry = dictionary->FindEntry(isolate, index); 1622 if (entry == NumberDictionary::kNotFound) return kMaxUInt32; 1623 if (filter != ALL_PROPERTIES) { 1624 PropertyDetails details = dictionary->DetailsAt(entry); 1625 PropertyAttributes attr = details.attributes(); 1626 if ((attr & filter) != 0) return kMaxUInt32; 1627 } 1628 return static_cast<uint32_t>(entry); 1629 } 1630 1631 static PropertyDetails GetDetailsImpl(JSObject* holder, uint32_t entry) { 1632 return GetDetailsImpl(holder->elements(), entry); 1633 } 1634 1635 static PropertyDetails GetDetailsImpl(FixedArrayBase* backing_store, 1636 uint32_t entry) { 1637 return NumberDictionary::cast(backing_store)->DetailsAt(entry); 1638 } 1639 1640 static uint32_t FilterKey(Handle<NumberDictionary> dictionary, int entry, 1641 Object* raw_key, PropertyFilter filter) { 1642 DCHECK(raw_key->IsNumber()); 1643 DCHECK_LE(raw_key->Number(), kMaxUInt32); 1644 PropertyDetails details = dictionary->DetailsAt(entry); 1645 PropertyAttributes attr = details.attributes(); 1646 if ((attr & filter) != 0) return kMaxUInt32; 1647 return static_cast<uint32_t>(raw_key->Number()); 1648 } 1649 1650 static uint32_t GetKeyForEntryImpl(Isolate* isolate, 1651 Handle<NumberDictionary> dictionary, 1652 int entry, PropertyFilter filter) { 1653 DisallowHeapAllocation no_gc; 1654 Object* raw_key = dictionary->KeyAt(entry); 1655 if (!dictionary->IsKey(ReadOnlyRoots(isolate), raw_key)) return kMaxUInt32; 1656 return FilterKey(dictionary, entry, raw_key, filter); 1657 } 1658 1659 static void CollectElementIndicesImpl(Handle<JSObject> object, 1660 Handle<FixedArrayBase> backing_store, 1661 KeyAccumulator* keys) { 1662 if (keys->filter() & SKIP_STRINGS) return; 1663 Isolate* isolate = keys->isolate(); 1664 Handle<NumberDictionary> dictionary = 1665 Handle<NumberDictionary>::cast(backing_store); 1666 int capacity = dictionary->Capacity(); 1667 Handle<FixedArray> elements = isolate->factory()->NewFixedArray( 1668 GetMaxNumberOfEntries(*object, *backing_store)); 1669 int insertion_index = 0; 1670 PropertyFilter filter = keys->filter(); 1671 ReadOnlyRoots roots(isolate); 1672 for (int i = 0; i < capacity; i++) { 1673 Object* raw_key = dictionary->KeyAt(i); 1674 if (!dictionary->IsKey(roots, raw_key)) continue; 1675 uint32_t key = FilterKey(dictionary, i, raw_key, filter); 1676 if (key == kMaxUInt32) { 1677 keys->AddShadowingKey(raw_key); 1678 continue; 1679 } 1680 elements->set(insertion_index, raw_key); 1681 insertion_index++; 1682 } 1683 SortIndices(isolate, elements, insertion_index); 1684 for (int i = 0; i < insertion_index; i++) { 1685 keys->AddKey(elements->get(i)); 1686 } 1687 } 1688 1689 static Handle<FixedArray> DirectCollectElementIndicesImpl( 1690 Isolate* isolate, Handle<JSObject> object, 1691 Handle<FixedArrayBase> backing_store, GetKeysConversion convert, 1692 PropertyFilter filter, Handle<FixedArray> list, uint32_t* nof_indices, 1693 uint32_t insertion_index = 0) { 1694 if (filter & SKIP_STRINGS) return list; 1695 if (filter & ONLY_ALL_CAN_READ) return list; 1696 1697 Handle<NumberDictionary> dictionary = 1698 Handle<NumberDictionary>::cast(backing_store); 1699 uint32_t capacity = dictionary->Capacity(); 1700 for (uint32_t i = 0; i < capacity; i++) { 1701 uint32_t key = GetKeyForEntryImpl(isolate, dictionary, i, filter); 1702 if (key == kMaxUInt32) continue; 1703 Handle<Object> index = isolate->factory()->NewNumberFromUint(key); 1704 list->set(insertion_index, *index); 1705 insertion_index++; 1706 } 1707 *nof_indices = insertion_index; 1708 return list; 1709 } 1710 1711 static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver, 1712 KeyAccumulator* accumulator, 1713 AddKeyConversion convert) { 1714 Isolate* isolate = accumulator->isolate(); 1715 Handle<NumberDictionary> dictionary( 1716 NumberDictionary::cast(receiver->elements()), isolate); 1717 int capacity = dictionary->Capacity(); 1718 ReadOnlyRoots roots(isolate); 1719 for (int i = 0; i < capacity; i++) { 1720 Object* k = dictionary->KeyAt(i); 1721 if (!dictionary->IsKey(roots, k)) continue; 1722 Object* value = dictionary->ValueAt(i); 1723 DCHECK(!value->IsTheHole(isolate)); 1724 DCHECK(!value->IsAccessorPair()); 1725 DCHECK(!value->IsAccessorInfo()); 1726 accumulator->AddKey(value, convert); 1727 } 1728 } 1729 1730 static bool IncludesValueFastPath(Isolate* isolate, Handle<JSObject> receiver, 1731 Handle<Object> value, uint32_t start_from, 1732 uint32_t length, Maybe<bool>* result) { 1733 DisallowHeapAllocation no_gc; 1734 NumberDictionary* dictionary = NumberDictionary::cast(receiver->elements()); 1735 int capacity = dictionary->Capacity(); 1736 Object* the_hole = ReadOnlyRoots(isolate).the_hole_value(); 1737 Object* undefined = ReadOnlyRoots(isolate).undefined_value(); 1738 1739 // Scan for accessor properties. If accessors are present, then elements 1740 // must be accessed in order via the slow path. 1741 bool found = false; 1742 for (int i = 0; i < capacity; ++i) { 1743 Object* k = dictionary->KeyAt(i); 1744 if (k == the_hole) continue; 1745 if (k == undefined) continue; 1746 1747 uint32_t index; 1748 if (!k->ToArrayIndex(&index) || index < start_from || index >= length) { 1749 continue; 1750 } 1751 1752 if (dictionary->DetailsAt(i).kind() == kAccessor) { 1753 // Restart from beginning in slow path, otherwise we may observably 1754 // access getters out of order 1755 return false; 1756 } else if (!found) { 1757 Object* element_k = dictionary->ValueAt(i); 1758 if (value->SameValueZero(element_k)) found = true; 1759 } 1760 } 1761 1762 *result = Just(found); 1763 return true; 1764 } 1765 1766 static Maybe<bool> IncludesValueImpl(Isolate* isolate, 1767 Handle<JSObject> receiver, 1768 Handle<Object> value, 1769 uint32_t start_from, uint32_t length) { 1770 DCHECK(JSObject::PrototypeHasNoElements(isolate, *receiver)); 1771 bool search_for_hole = value->IsUndefined(isolate); 1772 1773 if (!search_for_hole) { 1774 Maybe<bool> result = Nothing<bool>(); 1775 if (DictionaryElementsAccessor::IncludesValueFastPath( 1776 isolate, receiver, value, start_from, length, &result)) { 1777 return result; 1778 } 1779 } 1780 ElementsKind original_elements_kind = receiver->GetElementsKind(); 1781 USE(original_elements_kind); 1782 Handle<NumberDictionary> dictionary( 1783 NumberDictionary::cast(receiver->elements()), isolate); 1784 // Iterate through entire range, as accessing elements out of order is 1785 // observable 1786 for (uint32_t k = start_from; k < length; ++k) { 1787 DCHECK_EQ(receiver->GetElementsKind(), original_elements_kind); 1788 int entry = dictionary->FindEntry(isolate, k); 1789 if (entry == NumberDictionary::kNotFound) { 1790 if (search_for_hole) return Just(true); 1791 continue; 1792 } 1793 1794 PropertyDetails details = GetDetailsImpl(*dictionary, entry); 1795 switch (details.kind()) { 1796 case kData: { 1797 Object* element_k = dictionary->ValueAt(entry); 1798 if (value->SameValueZero(element_k)) return Just(true); 1799 break; 1800 } 1801 case kAccessor: { 1802 LookupIterator it(isolate, receiver, k, 1803 LookupIterator::OWN_SKIP_INTERCEPTOR); 1804 DCHECK(it.IsFound()); 1805 DCHECK_EQ(it.state(), LookupIterator::ACCESSOR); 1806 Handle<Object> element_k; 1807 1808 ASSIGN_RETURN_ON_EXCEPTION_VALUE( 1809 isolate, element_k, JSObject::GetPropertyWithAccessor(&it), 1810 Nothing<bool>()); 1811 1812 if (value->SameValueZero(*element_k)) return Just(true); 1813 1814 // Bailout to slow path if elements on prototype changed 1815 if (!JSObject::PrototypeHasNoElements(isolate, *receiver)) { 1816 return IncludesValueSlowPath(isolate, receiver, value, k + 1, 1817 length); 1818 } 1819 1820 // Continue if elements unchanged 1821 if (*dictionary == receiver->elements()) continue; 1822 1823 // Otherwise, bailout or update elements 1824 1825 // If switched to initial elements, return true if searching for 1826 // undefined, and false otherwise. 1827 if (receiver->map()->GetInitialElements() == receiver->elements()) { 1828 return Just(search_for_hole); 1829 } 1830 1831 // If switched to fast elements, continue with the correct accessor. 1832 if (receiver->GetElementsKind() != DICTIONARY_ELEMENTS) { 1833 ElementsAccessor* accessor = receiver->GetElementsAccessor(); 1834 return accessor->IncludesValue(isolate, receiver, value, k + 1, 1835 length); 1836 } 1837 dictionary = 1838 handle(NumberDictionary::cast(receiver->elements()), isolate); 1839 break; 1840 } 1841 } 1842 } 1843 return Just(false); 1844 } 1845 1846 static Maybe<int64_t> IndexOfValueImpl(Isolate* isolate, 1847 Handle<JSObject> receiver, 1848 Handle<Object> value, 1849 uint32_t start_from, uint32_t length) { 1850 DCHECK(JSObject::PrototypeHasNoElements(isolate, *receiver)); 1851 1852 ElementsKind original_elements_kind = receiver->GetElementsKind(); 1853 USE(original_elements_kind); 1854 Handle<NumberDictionary> dictionary( 1855 NumberDictionary::cast(receiver->elements()), isolate); 1856 // Iterate through entire range, as accessing elements out of order is 1857 // observable. 1858 for (uint32_t k = start_from; k < length; ++k) { 1859 DCHECK_EQ(receiver->GetElementsKind(), original_elements_kind); 1860 int entry = dictionary->FindEntry(isolate, k); 1861 if (entry == NumberDictionary::kNotFound) continue; 1862 1863 PropertyDetails details = GetDetailsImpl(*dictionary, entry); 1864 switch (details.kind()) { 1865 case kData: { 1866 Object* element_k = dictionary->ValueAt(entry); 1867 if (value->StrictEquals(element_k)) { 1868 return Just<int64_t>(k); 1869 } 1870 break; 1871 } 1872 case kAccessor: { 1873 LookupIterator it(isolate, receiver, k, 1874 LookupIterator::OWN_SKIP_INTERCEPTOR); 1875 DCHECK(it.IsFound()); 1876 DCHECK_EQ(it.state(), LookupIterator::ACCESSOR); 1877 Handle<Object> element_k; 1878 1879 ASSIGN_RETURN_ON_EXCEPTION_VALUE( 1880 isolate, element_k, JSObject::GetPropertyWithAccessor(&it), 1881 Nothing<int64_t>()); 1882 1883 if (value->StrictEquals(*element_k)) return Just<int64_t>(k); 1884 1885 // Bailout to slow path if elements on prototype changed. 1886 if (!JSObject::PrototypeHasNoElements(isolate, *receiver)) { 1887 return IndexOfValueSlowPath(isolate, receiver, value, k + 1, 1888 length); 1889 } 1890 1891 // Continue if elements unchanged. 1892 if (*dictionary == receiver->elements()) continue; 1893 1894 // Otherwise, bailout or update elements. 1895 if (receiver->GetElementsKind() != DICTIONARY_ELEMENTS) { 1896 // Otherwise, switch to slow path. 1897 return IndexOfValueSlowPath(isolate, receiver, value, k + 1, 1898 length); 1899 } 1900 dictionary = 1901 handle(NumberDictionary::cast(receiver->elements()), isolate); 1902 break; 1903 } 1904 } 1905 } 1906 return Just<int64_t>(-1); 1907 } 1908 1909 static void ValidateContents(JSObject* holder, int length) { 1910 DisallowHeapAllocation no_gc; 1911 #if DEBUG 1912 DCHECK_EQ(holder->map()->elements_kind(), DICTIONARY_ELEMENTS); 1913 if (!FLAG_enable_slow_asserts) return; 1914 ReadOnlyRoots roots = holder->GetReadOnlyRoots(); 1915 NumberDictionary* dictionary = NumberDictionary::cast(holder->elements()); 1916 // Validate the requires_slow_elements and max_number_key values. 1917 int capacity = dictionary->Capacity(); 1918 bool requires_slow_elements = false; 1919 int max_key = 0; 1920 for (int i = 0; i < capacity; ++i) { 1921 Object* k; 1922 if (!dictionary->ToKey(roots, i, &k)) continue; 1923 DCHECK_LE(0.0, k->Number()); 1924 if (k->Number() > NumberDictionary::kRequiresSlowElementsLimit) { 1925 requires_slow_elements = true; 1926 } else { 1927 max_key = Max(max_key, Smi::ToInt(k)); 1928 } 1929 } 1930 if (requires_slow_elements) { 1931 DCHECK(dictionary->requires_slow_elements()); 1932 } else if (!dictionary->requires_slow_elements()) { 1933 DCHECK_LE(max_key, dictionary->max_number_key()); 1934 } 1935 #endif 1936 } 1937 }; 1938 1939 1940 // Super class for all fast element arrays. 1941 template <typename Subclass, typename KindTraits> 1942 class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> { 1943 public: 1944 explicit FastElementsAccessor(const char* name) 1945 : ElementsAccessorBase<Subclass, KindTraits>(name) {} 1946 1947 typedef typename KindTraits::BackingStore BackingStore; 1948 1949 static Handle<NumberDictionary> NormalizeImpl(Handle<JSObject> object, 1950 Handle<FixedArrayBase> store) { 1951 Isolate* isolate = object->GetIsolate(); 1952 ElementsKind kind = Subclass::kind(); 1953 1954 // Ensure that notifications fire if the array or object prototypes are 1955 // normalizing. 1956 if (IsSmiOrObjectElementsKind(kind) || 1957 kind == FAST_STRING_WRAPPER_ELEMENTS) { 1958 isolate->UpdateNoElementsProtectorOnNormalizeElements(object); 1959 } 1960 1961 int capacity = object->GetFastElementsUsage(); 1962 Handle<NumberDictionary> dictionary = 1963 NumberDictionary::New(isolate, capacity); 1964 1965 PropertyDetails details = PropertyDetails::Empty(); 1966 int j = 0; 1967 int max_number_key = -1; 1968 for (int i = 0; j < capacity; i++) { 1969 if (IsHoleyElementsKind(kind)) { 1970 if (BackingStore::cast(*store)->is_the_hole(isolate, i)) continue; 1971 } 1972 max_number_key = i; 1973 Handle<Object> value = Subclass::GetImpl(isolate, *store, i); 1974 dictionary = 1975 NumberDictionary::Add(isolate, dictionary, i, value, details); 1976 j++; 1977 } 1978 1979 if (max_number_key > 0) { 1980 dictionary->UpdateMaxNumberKey(static_cast<uint32_t>(max_number_key), 1981 object); 1982 } 1983 return dictionary; 1984 } 1985 1986 static void DeleteAtEnd(Handle<JSObject> obj, 1987 Handle<BackingStore> backing_store, uint32_t entry) { 1988 uint32_t length = static_cast<uint32_t>(backing_store->length()); 1989 Isolate* isolate = obj->GetIsolate(); 1990 for (; entry > 0; entry--) { 1991 if (!backing_store->is_the_hole(isolate, entry - 1)) break; 1992 } 1993 if (entry == 0) { 1994 FixedArray* empty = ReadOnlyRoots(isolate).empty_fixed_array(); 1995 // Dynamically ask for the elements kind here since we manually redirect 1996 // the operations for argument backing stores. 1997 if (obj->GetElementsKind() == FAST_SLOPPY_ARGUMENTS_ELEMENTS) { 1998 SloppyArgumentsElements::cast(obj->elements())->set_arguments(empty); 1999 } else { 2000 obj->set_elements(empty); 2001 } 2002 return; 2003 } 2004 2005 isolate->heap()->RightTrimFixedArray(*backing_store, length - entry); 2006 } 2007 2008 static void DeleteCommon(Handle<JSObject> obj, uint32_t entry, 2009 Handle<FixedArrayBase> store) { 2010 DCHECK(obj->HasSmiOrObjectElements() || obj->HasDoubleElements() || 2011 obj->HasFastArgumentsElements() || 2012 obj->HasFastStringWrapperElements()); 2013 Handle<BackingStore> backing_store = Handle<BackingStore>::cast(store); 2014 if (!obj->IsJSArray() && 2015 entry == static_cast<uint32_t>(store->length()) - 1) { 2016 DeleteAtEnd(obj, backing_store, entry); 2017 return; 2018 } 2019 2020 Isolate* isolate = obj->GetIsolate(); 2021 backing_store->set_the_hole(isolate, entry); 2022 2023 // TODO(verwaest): Move this out of elements.cc. 2024 // If an old space backing store is larger than a certain size and 2025 // has too few used values, normalize it. 2026 const int kMinLengthForSparsenessCheck = 64; 2027 if (backing_store->length() < kMinLengthForSparsenessCheck) return; 2028 if (Heap::InNewSpace(*backing_store)) return; 2029 uint32_t length = 0; 2030 if (obj->IsJSArray()) { 2031 JSArray::cast(*obj)->length()->ToArrayLength(&length); 2032 } else { 2033 length = static_cast<uint32_t>(store->length()); 2034 } 2035 2036 // To avoid doing the check on every delete, use a counter-based heuristic. 2037 const int kLengthFraction = 16; 2038 // The above constant must be large enough to ensure that we check for 2039 // normalization frequently enough. At a minimum, it should be large 2040 // enough to reliably hit the "window" of remaining elements count where 2041 // normalization would be beneficial. 2042 STATIC_ASSERT(kLengthFraction >= 2043 NumberDictionary::kEntrySize * 2044 NumberDictionary::kPreferFastElementsSizeFactor); 2045 size_t current_counter = isolate->elements_deletion_counter(); 2046 if (current_counter < length / kLengthFraction) { 2047 isolate->set_elements_deletion_counter(current_counter + 1); 2048 return; 2049 } 2050 // Reset the counter whenever the full check is performed. 2051 isolate->set_elements_deletion_counter(0); 2052 2053 if (!obj->IsJSArray()) { 2054 uint32_t i; 2055 for (i = entry + 1; i < length; i++) { 2056 if (!backing_store->is_the_hole(isolate, i)) break; 2057 } 2058 if (i == length) { 2059 DeleteAtEnd(obj, backing_store, entry); 2060 return; 2061 } 2062 } 2063 int num_used = 0; 2064 for (int i = 0; i < backing_store->length(); ++i) { 2065 if (!backing_store->is_the_hole(isolate, i)) { 2066 ++num_used; 2067 // Bail out if a number dictionary wouldn't be able to save much space. 2068 if (NumberDictionary::kPreferFastElementsSizeFactor * 2069 NumberDictionary::ComputeCapacity(num_used) * 2070 NumberDictionary::kEntrySize > 2071 static_cast<uint32_t>(backing_store->length())) { 2072 return; 2073 } 2074 } 2075 } 2076 JSObject::NormalizeElements(obj); 2077 } 2078 2079 static void ReconfigureImpl(Handle<JSObject> object, 2080 Handle<FixedArrayBase> store, uint32_t entry, 2081 Handle<Object> value, 2082 PropertyAttributes attributes) { 2083 Handle<NumberDictionary> dictionary = JSObject::NormalizeElements(object); 2084 entry = dictionary->FindEntry(object->GetIsolate(), entry); 2085 DictionaryElementsAccessor::ReconfigureImpl(object, dictionary, entry, 2086 value, attributes); 2087 } 2088 2089 static void AddImpl(Handle<JSObject> object, uint32_t index, 2090 Handle<Object> value, PropertyAttributes attributes, 2091 uint32_t new_capacity) { 2092 DCHECK_EQ(NONE, attributes); 2093 ElementsKind from_kind = object->GetElementsKind(); 2094 ElementsKind to_kind = Subclass::kind(); 2095 if (IsDictionaryElementsKind(from_kind) || 2096 IsDoubleElementsKind(from_kind) != IsDoubleElementsKind(to_kind) || 2097 Subclass::GetCapacityImpl(*object, object->elements()) != 2098 new_capacity) { 2099 Subclass::GrowCapacityAndConvertImpl(object, new_capacity); 2100 } else { 2101 if (IsFastElementsKind(from_kind) && from_kind != to_kind) { 2102 JSObject::TransitionElementsKind(object, to_kind); 2103 } 2104 if (IsSmiOrObjectElementsKind(from_kind)) { 2105 DCHECK(IsSmiOrObjectElementsKind(to_kind)); 2106 JSObject::EnsureWritableFastElements(object); 2107 } 2108 } 2109 Subclass::SetImpl(object, index, *value); 2110 } 2111 2112 static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) { 2113 ElementsKind kind = KindTraits::Kind; 2114 if (IsFastPackedElementsKind(kind)) { 2115 JSObject::TransitionElementsKind(obj, GetHoleyElementsKind(kind)); 2116 } 2117 if (IsSmiOrObjectElementsKind(KindTraits::Kind)) { 2118 JSObject::EnsureWritableFastElements(obj); 2119 } 2120 DeleteCommon(obj, entry, handle(obj->elements(), obj->GetIsolate())); 2121 } 2122 2123 static bool HasEntryImpl(Isolate* isolate, FixedArrayBase* backing_store, 2124 uint32_t entry) { 2125 return !BackingStore::cast(backing_store)->is_the_hole(isolate, entry); 2126 } 2127 2128 static uint32_t NumberOfElementsImpl(JSObject* receiver, 2129 FixedArrayBase* backing_store) { 2130 uint32_t max_index = Subclass::GetMaxIndex(receiver, backing_store); 2131 if (IsFastPackedElementsKind(Subclass::kind())) return max_index; 2132 Isolate* isolate = receiver->GetIsolate(); 2133 uint32_t count = 0; 2134 for (uint32_t i = 0; i < max_index; i++) { 2135 if (Subclass::HasEntryImpl(isolate, backing_store, i)) count++; 2136 } 2137 return count; 2138 } 2139 2140 static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver, 2141 KeyAccumulator* accumulator, 2142 AddKeyConversion convert) { 2143 Isolate* isolate = accumulator->isolate(); 2144 Handle<FixedArrayBase> elements(receiver->elements(), isolate); 2145 uint32_t length = Subclass::GetMaxNumberOfEntries(*receiver, *elements); 2146 for (uint32_t i = 0; i < length; i++) { 2147 if (IsFastPackedElementsKind(KindTraits::Kind) || 2148 HasEntryImpl(isolate, *elements, i)) { 2149 accumulator->AddKey(Subclass::GetImpl(isolate, *elements, i), convert); 2150 } 2151 } 2152 } 2153 2154 static void ValidateContents(JSObject* holder, int length) { 2155 #if DEBUG 2156 Isolate* isolate = holder->GetIsolate(); 2157 Heap* heap = isolate->heap(); 2158 FixedArrayBase* elements = holder->elements(); 2159 Map* map = elements->map(); 2160 if (IsSmiOrObjectElementsKind(KindTraits::Kind)) { 2161 DCHECK_NE(map, ReadOnlyRoots(heap).fixed_double_array_map()); 2162 } else if (IsDoubleElementsKind(KindTraits::Kind)) { 2163 DCHECK_NE(map, ReadOnlyRoots(heap).fixed_cow_array_map()); 2164 if (map == ReadOnlyRoots(heap).fixed_array_map()) DCHECK_EQ(0, length); 2165 } else { 2166 UNREACHABLE(); 2167 } 2168 if (length == 0) return; // nothing to do! 2169 #if ENABLE_SLOW_DCHECKS 2170 DisallowHeapAllocation no_gc; 2171 BackingStore* backing_store = BackingStore::cast(elements); 2172 if (IsSmiElementsKind(KindTraits::Kind)) { 2173 HandleScope scope(isolate); 2174 for (int i = 0; i < length; i++) { 2175 DCHECK(BackingStore::get(backing_store, i, isolate)->IsSmi() || 2176 (IsHoleyElementsKind(KindTraits::Kind) && 2177 backing_store->is_the_hole(isolate, i))); 2178 } 2179 } else if (KindTraits::Kind == PACKED_ELEMENTS || 2180 KindTraits::Kind == PACKED_DOUBLE_ELEMENTS) { 2181 for (int i = 0; i < length; i++) { 2182 DCHECK(!backing_store->is_the_hole(isolate, i)); 2183 } 2184 } else { 2185 DCHECK(IsHoleyElementsKind(KindTraits::Kind)); 2186 } 2187 #endif 2188 #endif 2189 } 2190 2191 static Handle<Object> PopImpl(Handle<JSArray> receiver) { 2192 return Subclass::RemoveElement(receiver, AT_END); 2193 } 2194 2195 static Handle<Object> ShiftImpl(Handle<JSArray> receiver) { 2196 return Subclass::RemoveElement(receiver, AT_START); 2197 } 2198 2199 static uint32_t PushImpl(Handle<JSArray> receiver, 2200 Arguments* args, uint32_t push_size) { 2201 Handle<FixedArrayBase> backing_store(receiver->elements(), 2202 receiver->GetIsolate()); 2203 return Subclass::AddArguments(receiver, backing_store, args, push_size, 2204 AT_END); 2205 } 2206 2207 static uint32_t UnshiftImpl(Handle<JSArray> receiver, 2208 Arguments* args, uint32_t unshift_size) { 2209 Handle<FixedArrayBase> backing_store(receiver->elements(), 2210 receiver->GetIsolate()); 2211 return Subclass::AddArguments(receiver, backing_store, args, unshift_size, 2212 AT_START); 2213 } 2214 2215 static Handle<JSObject> SliceImpl(Handle<JSObject> receiver, uint32_t start, 2216 uint32_t end) { 2217 Isolate* isolate = receiver->GetIsolate(); 2218 Handle<FixedArrayBase> backing_store(receiver->elements(), isolate); 2219 int result_len = end < start ? 0u : end - start; 2220 Handle<JSArray> result_array = isolate->factory()->NewJSArray( 2221 KindTraits::Kind, result_len, result_len); 2222 DisallowHeapAllocation no_gc; 2223 Subclass::CopyElementsImpl(isolate, *backing_store, start, 2224 result_array->elements(), KindTraits::Kind, 0, 2225 kPackedSizeNotKnown, result_len); 2226 Subclass::TryTransitionResultArrayToPacked(result_array); 2227 return result_array; 2228 } 2229 2230 static Handle<JSArray> SpliceImpl(Handle<JSArray> receiver, 2231 uint32_t start, uint32_t delete_count, 2232 Arguments* args, uint32_t add_count) { 2233 Isolate* isolate = receiver->GetIsolate(); 2234 Heap* heap = isolate->heap(); 2235 uint32_t length = Smi::ToInt(receiver->length()); 2236 uint32_t new_length = length - delete_count + add_count; 2237 2238 ElementsKind kind = KindTraits::Kind; 2239 if (new_length <= static_cast<uint32_t>(receiver->elements()->length()) && 2240 IsSmiOrObjectElementsKind(kind)) { 2241 HandleScope scope(isolate); 2242 JSObject::EnsureWritableFastElements(receiver); 2243 } 2244 2245 Handle<FixedArrayBase> backing_store(receiver->elements(), isolate); 2246 2247 if (new_length == 0) { 2248 receiver->set_elements(ReadOnlyRoots(heap).empty_fixed_array()); 2249 receiver->set_length(Smi::kZero); 2250 return isolate->factory()->NewJSArrayWithElements( 2251 backing_store, KindTraits::Kind, delete_count); 2252 } 2253 2254 // Construct the result array which holds the deleted elements. 2255 Handle<JSArray> deleted_elements = isolate->factory()->NewJSArray( 2256 KindTraits::Kind, delete_count, delete_count); 2257 if (delete_count > 0) { 2258 DisallowHeapAllocation no_gc; 2259 Subclass::CopyElementsImpl(isolate, *backing_store, start, 2260 deleted_elements->elements(), KindTraits::Kind, 2261 0, kPackedSizeNotKnown, delete_count); 2262 } 2263 2264 // Delete and move elements to make space for add_count new elements. 2265 if (add_count < delete_count) { 2266 Subclass::SpliceShrinkStep(isolate, receiver, backing_store, start, 2267 delete_count, add_count, length, new_length); 2268 } else if (add_count > delete_count) { 2269 backing_store = 2270 Subclass::SpliceGrowStep(isolate, receiver, backing_store, start, 2271 delete_count, add_count, length, new_length); 2272 } 2273 2274 // Copy over the arguments. 2275 Subclass::CopyArguments(args, backing_store, add_count, 3, start); 2276 2277 receiver->set_length(Smi::FromInt(new_length)); 2278 Subclass::TryTransitionResultArrayToPacked(deleted_elements); 2279 return deleted_elements; 2280 } 2281 2282 static void MoveElements(Isolate* isolate, Handle<JSArray> receiver, 2283 Handle<FixedArrayBase> backing_store, int dst_index, 2284 int src_index, int len, int hole_start, 2285 int hole_end) { 2286 Heap* heap = isolate->heap(); 2287 Handle<BackingStore> dst_elms = Handle<BackingStore>::cast(backing_store); 2288 if (len > JSArray::kMaxCopyElements && dst_index == 0 && 2289 heap->CanMoveObjectStart(*dst_elms)) { 2290 // Update all the copies of this backing_store handle. 2291 *dst_elms.location() = 2292 BackingStore::cast(heap->LeftTrimFixedArray(*dst_elms, src_index)); 2293 receiver->set_elements(*dst_elms); 2294 // Adjust the hole offset as the array has been shrunk. 2295 hole_end -= src_index; 2296 DCHECK_LE(hole_start, backing_store->length()); 2297 DCHECK_LE(hole_end, backing_store->length()); 2298 } else if (len != 0) { 2299 if (IsDoubleElementsKind(KindTraits::Kind)) { 2300 MemMove(dst_elms->data_start() + dst_index, 2301 dst_elms->data_start() + src_index, len * kDoubleSize); 2302 } else { 2303 DisallowHeapAllocation no_gc; 2304 WriteBarrierMode mode = GetWriteBarrierMode(KindTraits::Kind); 2305 heap->MoveElements(FixedArray::cast(*dst_elms), dst_index, src_index, 2306 len, mode); 2307 } 2308 } 2309 if (hole_start != hole_end) { 2310 dst_elms->FillWithHoles(hole_start, hole_end); 2311 } 2312 } 2313 2314 static Object* FillImpl(Handle<JSObject> receiver, Handle<Object> obj_value, 2315 uint32_t start, uint32_t end) { 2316 // Ensure indexes are within array bounds 2317 DCHECK_LE(0, start); 2318 DCHECK_LE(start, end); 2319 2320 // Make sure COW arrays are copied. 2321 if (IsSmiOrObjectElementsKind(Subclass::kind())) { 2322 JSObject::EnsureWritableFastElements(receiver); 2323 } 2324 2325 // Make sure we have enough space. 2326 uint32_t capacity = 2327 Subclass::GetCapacityImpl(*receiver, receiver->elements()); 2328 if (end > capacity) { 2329 Subclass::GrowCapacityAndConvertImpl(receiver, end); 2330 CHECK_EQ(Subclass::kind(), receiver->GetElementsKind()); 2331 } 2332 DCHECK_LE(end, Subclass::GetCapacityImpl(*receiver, receiver->elements())); 2333 2334 for (uint32_t index = start; index < end; ++index) { 2335 Subclass::SetImpl(receiver, index, *obj_value); 2336 } 2337 return *receiver; 2338 } 2339 2340 static Maybe<bool> IncludesValueImpl(Isolate* isolate, 2341 Handle<JSObject> receiver, 2342 Handle<Object> search_value, 2343 uint32_t start_from, uint32_t length) { 2344 DCHECK(JSObject::PrototypeHasNoElements(isolate, *receiver)); 2345 DisallowHeapAllocation no_gc; 2346 FixedArrayBase* elements_base = receiver->elements(); 2347 Object* the_hole = ReadOnlyRoots(isolate).the_hole_value(); 2348 Object* undefined = ReadOnlyRoots(isolate).undefined_value(); 2349 Object* value = *search_value; 2350 2351 // Elements beyond the capacity of the backing store treated as undefined. 2352 if (value == undefined && 2353 static_cast<uint32_t>(elements_base->length()) < length) { 2354 return Just(true); 2355 } 2356 2357 if (start_from >= length) return Just(false); 2358 2359 length = std::min(static_cast<uint32_t>(elements_base->length()), length); 2360 2361 if (!value->IsNumber()) { 2362 if (value == undefined) { 2363 // Only PACKED_ELEMENTS, HOLEY_ELEMENTS, HOLEY_SMI_ELEMENTS, and 2364 // HOLEY_DOUBLE_ELEMENTS can have `undefined` as a value. 2365 if (!IsObjectElementsKind(Subclass::kind()) && 2366 !IsHoleyElementsKind(Subclass::kind())) { 2367 return Just(false); 2368 } 2369 2370 // Search for `undefined` or The Hole in PACKED_ELEMENTS, 2371 // HOLEY_ELEMENTS or HOLEY_SMI_ELEMENTS 2372 if (IsSmiOrObjectElementsKind(Subclass::kind())) { 2373 auto elements = FixedArray::cast(receiver->elements()); 2374 2375 for (uint32_t k = start_from; k < length; ++k) { 2376 Object* element_k = elements->get(k); 2377 2378 if (IsHoleyElementsKind(Subclass::kind()) && 2379 element_k == the_hole) { 2380 return Just(true); 2381 } 2382 if (IsObjectElementsKind(Subclass::kind()) && 2383 element_k == undefined) { 2384 return Just(true); 2385 } 2386 } 2387 return Just(false); 2388 } else { 2389 // Search for The Hole in HOLEY_DOUBLE_ELEMENTS 2390 DCHECK_EQ(Subclass::kind(), HOLEY_DOUBLE_ELEMENTS); 2391 auto elements = FixedDoubleArray::cast(receiver->elements()); 2392 2393 for (uint32_t k = start_from; k < length; ++k) { 2394 if (IsHoleyElementsKind(Subclass::kind()) && 2395 elements->is_the_hole(k)) { 2396 return Just(true); 2397 } 2398 } 2399 return Just(false); 2400 } 2401 } else if (!IsObjectElementsKind(Subclass::kind())) { 2402 // Search for non-number, non-Undefined value, with either 2403 // PACKED_SMI_ELEMENTS, PACKED_DOUBLE_ELEMENTS, HOLEY_SMI_ELEMENTS or 2404 // HOLEY_DOUBLE_ELEMENTS. Guaranteed to return false, since these 2405 // elements kinds can only contain Number values or undefined. 2406 return Just(false); 2407 } else { 2408 // Search for non-number, non-Undefined value with either 2409 // PACKED_ELEMENTS or HOLEY_ELEMENTS. 2410 DCHECK(IsObjectElementsKind(Subclass::kind())); 2411 auto elements = FixedArray::cast(receiver->elements()); 2412 2413 for (uint32_t k = start_from; k < length; ++k) { 2414 Object* element_k = elements->get(k); 2415 if (IsHoleyElementsKind(Subclass::kind()) && element_k == the_hole) { 2416 continue; 2417 } 2418 2419 if (value->SameValueZero(element_k)) return Just(true); 2420 } 2421 return Just(false); 2422 } 2423 } else { 2424 if (!value->IsNaN()) { 2425 double search_value = value->Number(); 2426 if (IsDoubleElementsKind(Subclass::kind())) { 2427 // Search for non-NaN Number in PACKED_DOUBLE_ELEMENTS or 2428 // HOLEY_DOUBLE_ELEMENTS --- Skip TheHole, and trust UCOMISD or 2429 // similar operation for result. 2430 auto elements = FixedDoubleArray::cast(receiver->elements()); 2431 2432 for (uint32_t k = start_from; k < length; ++k) { 2433 if (IsHoleyElementsKind(Subclass::kind()) && 2434 elements->is_the_hole(k)) { 2435 continue; 2436 } 2437 if (elements->get_scalar(k) == search_value) return Just(true); 2438 } 2439 return Just(false); 2440 } else { 2441 // Search for non-NaN Number in PACKED_ELEMENTS, HOLEY_ELEMENTS, 2442 // PACKED_SMI_ELEMENTS or HOLEY_SMI_ELEMENTS --- Skip non-Numbers, 2443 // and trust UCOMISD or similar operation for result 2444 auto elements = FixedArray::cast(receiver->elements()); 2445 2446 for (uint32_t k = start_from; k < length; ++k) { 2447 Object* element_k = elements->get(k); 2448 if (element_k->IsNumber() && element_k->Number() == search_value) { 2449 return Just(true); 2450 } 2451 } 2452 return Just(false); 2453 } 2454 } else { 2455 // Search for NaN --- NaN cannot be represented with Smi elements, so 2456 // abort if ElementsKind is PACKED_SMI_ELEMENTS or HOLEY_SMI_ELEMENTS 2457 if (IsSmiElementsKind(Subclass::kind())) return Just(false); 2458 2459 if (IsDoubleElementsKind(Subclass::kind())) { 2460 // Search for NaN in PACKED_DOUBLE_ELEMENTS or 2461 // HOLEY_DOUBLE_ELEMENTS --- Skip The Hole and trust 2462 // std::isnan(elementK) for result 2463 auto elements = FixedDoubleArray::cast(receiver->elements()); 2464 2465 for (uint32_t k = start_from; k < length; ++k) { 2466 if (IsHoleyElementsKind(Subclass::kind()) && 2467 elements->is_the_hole(k)) { 2468 continue; 2469 } 2470 if (std::isnan(elements->get_scalar(k))) return Just(true); 2471 } 2472 return Just(false); 2473 } else { 2474 // Search for NaN in PACKED_ELEMENTS, HOLEY_ELEMENTS, 2475 // PACKED_SMI_ELEMENTS or HOLEY_SMI_ELEMENTS. Return true if 2476 // elementK->IsHeapNumber() && std::isnan(elementK->Number()) 2477 DCHECK(IsSmiOrObjectElementsKind(Subclass::kind())); 2478 auto elements = FixedArray::cast(receiver->elements()); 2479 2480 for (uint32_t k = start_from; k < length; ++k) { 2481 if (elements->get(k)->IsNaN()) return Just(true); 2482 } 2483 return Just(false); 2484 } 2485 } 2486 } 2487 } 2488 2489 static Handle<FixedArray> CreateListFromArrayLikeImpl(Isolate* isolate, 2490 Handle<JSObject> object, 2491 uint32_t length) { 2492 Handle<FixedArray> result = isolate->factory()->NewFixedArray(length); 2493 Handle<FixedArrayBase> elements(object->elements(), isolate); 2494 for (uint32_t i = 0; i < length; i++) { 2495 if (!Subclass::HasElementImpl(isolate, *object, i, *elements)) continue; 2496 Handle<Object> value; 2497 value = Subclass::GetImpl(isolate, *elements, i); 2498 if (value->IsName()) { 2499 value = isolate->factory()->InternalizeName(Handle<Name>::cast(value)); 2500 } 2501 result->set(i, *value); 2502 } 2503 return result; 2504 } 2505 2506 private: 2507 // SpliceShrinkStep might modify the backing_store. 2508 static void SpliceShrinkStep(Isolate* isolate, Handle<JSArray> receiver, 2509 Handle<FixedArrayBase> backing_store, 2510 uint32_t start, uint32_t delete_count, 2511 uint32_t add_count, uint32_t len, 2512 uint32_t new_length) { 2513 const int move_left_count = len - delete_count - start; 2514 const int move_left_dst_index = start + add_count; 2515 Subclass::MoveElements(isolate, receiver, backing_store, 2516 move_left_dst_index, start + delete_count, 2517 move_left_count, new_length, len); 2518 } 2519 2520 // SpliceGrowStep might modify the backing_store. 2521 static Handle<FixedArrayBase> SpliceGrowStep( 2522 Isolate* isolate, Handle<JSArray> receiver, 2523 Handle<FixedArrayBase> backing_store, uint32_t start, 2524 uint32_t delete_count, uint32_t add_count, uint32_t length, 2525 uint32_t new_length) { 2526 // Check we do not overflow the new_length. 2527 DCHECK((add_count - delete_count) <= (Smi::kMaxValue - length)); 2528 // Check if backing_store is big enough. 2529 if (new_length <= static_cast<uint32_t>(backing_store->length())) { 2530 Subclass::MoveElements(isolate, receiver, backing_store, 2531 start + add_count, start + delete_count, 2532 (length - delete_count - start), 0, 0); 2533 // MoveElements updates the backing_store in-place. 2534 return backing_store; 2535 } 2536 // New backing storage is needed. 2537 int capacity = JSObject::NewElementsCapacity(new_length); 2538 // Partially copy all elements up to start. 2539 Handle<FixedArrayBase> new_elms = Subclass::ConvertElementsWithCapacity( 2540 receiver, backing_store, KindTraits::Kind, capacity, start); 2541 // Copy the trailing elements after start + delete_count 2542 Subclass::CopyElementsImpl(isolate, *backing_store, start + delete_count, 2543 *new_elms, KindTraits::Kind, start + add_count, 2544 kPackedSizeNotKnown, 2545 ElementsAccessor::kCopyToEndAndInitializeToHole); 2546 receiver->set_elements(*new_elms); 2547 return new_elms; 2548 } 2549 2550 static Handle<Object> RemoveElement(Handle<JSArray> receiver, 2551 Where remove_position) { 2552 Isolate* isolate = receiver->GetIsolate(); 2553 ElementsKind kind = KindTraits::Kind; 2554 if (IsSmiOrObjectElementsKind(kind)) { 2555 HandleScope scope(isolate); 2556 JSObject::EnsureWritableFastElements(receiver); 2557 } 2558 Handle<FixedArrayBase> backing_store(receiver->elements(), isolate); 2559 uint32_t length = static_cast<uint32_t>(Smi::ToInt(receiver->length())); 2560 DCHECK_GT(length, 0); 2561 int new_length = length - 1; 2562 int remove_index = remove_position == AT_START ? 0 : new_length; 2563 Handle<Object> result = 2564 Subclass::GetImpl(isolate, *backing_store, remove_index); 2565 if (remove_position == AT_START) { 2566 Subclass::MoveElements(isolate, receiver, backing_store, 0, 1, new_length, 2567 0, 0); 2568 } 2569 Subclass::SetLengthImpl(isolate, receiver, new_length, backing_store); 2570 2571 if (IsHoleyElementsKind(kind) && result->IsTheHole(isolate)) { 2572 return isolate->factory()->undefined_value(); 2573 } 2574 return result; 2575 } 2576 2577 static uint32_t AddArguments(Handle<JSArray> receiver, 2578 Handle<FixedArrayBase> backing_store, 2579 Arguments* args, uint32_t add_size, 2580 Where add_position) { 2581 uint32_t length = Smi::ToInt(receiver->length()); 2582 DCHECK_LT(0, add_size); 2583 uint32_t elms_len = backing_store->length(); 2584 // Check we do not overflow the new_length. 2585 DCHECK(add_size <= static_cast<uint32_t>(Smi::kMaxValue - length)); 2586 uint32_t new_length = length + add_size; 2587 2588 if (new_length > elms_len) { 2589 // New backing storage is needed. 2590 uint32_t capacity = JSObject::NewElementsCapacity(new_length); 2591 // If we add arguments to the start we have to shift the existing objects. 2592 int copy_dst_index = add_position == AT_START ? add_size : 0; 2593 // Copy over all objects to a new backing_store. 2594 backing_store = Subclass::ConvertElementsWithCapacity( 2595 receiver, backing_store, KindTraits::Kind, capacity, 0, 2596 copy_dst_index, ElementsAccessor::kCopyToEndAndInitializeToHole); 2597 receiver->set_elements(*backing_store); 2598 } else if (add_position == AT_START) { 2599 // If the backing store has enough capacity and we add elements to the 2600 // start we have to shift the existing objects. 2601 Isolate* isolate = receiver->GetIsolate(); 2602 Subclass::MoveElements(isolate, receiver, backing_store, add_size, 0, 2603 length, 0, 0); 2604 } 2605 2606 int insertion_index = add_position == AT_START ? 0 : length; 2607 // Copy the arguments to the start. 2608 Subclass::CopyArguments(args, backing_store, add_size, 1, insertion_index); 2609 // Set the length. 2610 receiver->set_length(Smi::FromInt(new_length)); 2611 return new_length; 2612 } 2613 2614 static void CopyArguments(Arguments* args, Handle<FixedArrayBase> dst_store, 2615 uint32_t copy_size, uint32_t src_index, 2616 uint32_t dst_index) { 2617 // Add the provided values. 2618 DisallowHeapAllocation no_gc; 2619 FixedArrayBase* raw_backing_store = *dst_store; 2620 WriteBarrierMode mode = raw_backing_store->GetWriteBarrierMode(no_gc); 2621 for (uint32_t i = 0; i < copy_size; i++) { 2622 Object* argument = (*args)[src_index + i]; 2623 DCHECK(!argument->IsTheHole()); 2624 Subclass::SetImpl(raw_backing_store, dst_index + i, argument, mode); 2625 } 2626 } 2627 }; 2628 2629 template <typename Subclass, typename KindTraits> 2630 class FastSmiOrObjectElementsAccessor 2631 : public FastElementsAccessor<Subclass, KindTraits> { 2632 public: 2633 explicit FastSmiOrObjectElementsAccessor(const char* name) 2634 : FastElementsAccessor<Subclass, KindTraits>(name) {} 2635 2636 static inline void SetImpl(Handle<JSObject> holder, uint32_t entry, 2637 Object* value) { 2638 SetImpl(holder->elements(), entry, value); 2639 } 2640 2641 static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry, 2642 Object* value) { 2643 FixedArray::cast(backing_store)->set(entry, value); 2644 } 2645 2646 static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry, 2647 Object* value, WriteBarrierMode mode) { 2648 FixedArray::cast(backing_store)->set(entry, value, mode); 2649 } 2650 2651 static Object* GetRaw(FixedArray* backing_store, uint32_t entry) { 2652 uint32_t index = Subclass::GetIndexForEntryImpl(backing_store, entry); 2653 return backing_store->get(index); 2654 } 2655 2656 // NOTE: this method violates the handlified function signature convention: 2657 // raw pointer parameters in the function that allocates. 2658 // See ElementsAccessor::CopyElements() for details. 2659 // This method could actually allocate if copying from double elements to 2660 // object elements. 2661 static void CopyElementsImpl(Isolate* isolate, FixedArrayBase* from, 2662 uint32_t from_start, FixedArrayBase* to, 2663 ElementsKind from_kind, uint32_t to_start, 2664 int packed_size, int copy_size) { 2665 DisallowHeapAllocation no_gc; 2666 ElementsKind to_kind = KindTraits::Kind; 2667 switch (from_kind) { 2668 case PACKED_SMI_ELEMENTS: 2669 case HOLEY_SMI_ELEMENTS: 2670 case PACKED_ELEMENTS: 2671 case HOLEY_ELEMENTS: 2672 CopyObjectToObjectElements(isolate, from, from_kind, from_start, to, 2673 to_kind, to_start, copy_size); 2674 break; 2675 case PACKED_DOUBLE_ELEMENTS: 2676 case HOLEY_DOUBLE_ELEMENTS: { 2677 AllowHeapAllocation allow_allocation; 2678 DCHECK(IsObjectElementsKind(to_kind)); 2679 CopyDoubleToObjectElements(isolate, from, from_start, to, to_start, 2680 copy_size); 2681 break; 2682 } 2683 case DICTIONARY_ELEMENTS: 2684 CopyDictionaryToObjectElements(isolate, from, from_start, to, to_kind, 2685 to_start, copy_size); 2686 break; 2687 case FAST_SLOPPY_ARGUMENTS_ELEMENTS: 2688 case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: 2689 case FAST_STRING_WRAPPER_ELEMENTS: 2690 case SLOW_STRING_WRAPPER_ELEMENTS: 2691 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype) case TYPE##_ELEMENTS: 2692 TYPED_ARRAYS(TYPED_ARRAY_CASE) 2693 #undef TYPED_ARRAY_CASE 2694 // This function is currently only used for JSArrays with non-zero 2695 // length. 2696 UNREACHABLE(); 2697 break; 2698 case NO_ELEMENTS: 2699 break; // Nothing to do. 2700 } 2701 } 2702 2703 static Maybe<bool> CollectValuesOrEntriesImpl( 2704 Isolate* isolate, Handle<JSObject> object, 2705 Handle<FixedArray> values_or_entries, bool get_entries, int* nof_items, 2706 PropertyFilter filter) { 2707 int count = 0; 2708 if (get_entries) { 2709 // Collecting entries needs to allocate, so this code must be handlified. 2710 Handle<FixedArray> elements(FixedArray::cast(object->elements()), 2711 isolate); 2712 uint32_t length = elements->length(); 2713 for (uint32_t index = 0; index < length; ++index) { 2714 if (!Subclass::HasEntryImpl(isolate, *elements, index)) continue; 2715 Handle<Object> value = Subclass::GetImpl(isolate, *elements, index); 2716 value = MakeEntryPair(isolate, index, value); 2717 values_or_entries->set(count++, *value); 2718 } 2719 } else { 2720 // No allocations here, so we can avoid handlification overhead. 2721 DisallowHeapAllocation no_gc; 2722 FixedArray* elements = FixedArray::cast(object->elements()); 2723 uint32_t length = elements->length(); 2724 for (uint32_t index = 0; index < length; ++index) { 2725 if (!Subclass::HasEntryImpl(isolate, elements, index)) continue; 2726 Object* value = GetRaw(elements, index); 2727 values_or_entries->set(count++, value); 2728 } 2729 } 2730 *nof_items = count; 2731 return Just(true); 2732 } 2733 2734 static Maybe<int64_t> IndexOfValueImpl(Isolate* isolate, 2735 Handle<JSObject> receiver, 2736 Handle<Object> search_value, 2737 uint32_t start_from, uint32_t length) { 2738 DCHECK(JSObject::PrototypeHasNoElements(isolate, *receiver)); 2739 DisallowHeapAllocation no_gc; 2740 FixedArrayBase* elements_base = receiver->elements(); 2741 Object* value = *search_value; 2742 2743 if (start_from >= length) return Just<int64_t>(-1); 2744 2745 length = std::min(static_cast<uint32_t>(elements_base->length()), length); 2746 2747 // Only FAST_{,HOLEY_}ELEMENTS can store non-numbers. 2748 if (!value->IsNumber() && !IsObjectElementsKind(Subclass::kind())) { 2749 return Just<int64_t>(-1); 2750 } 2751 // NaN can never be found by strict equality. 2752 if (value->IsNaN()) return Just<int64_t>(-1); 2753 2754 FixedArray* elements = FixedArray::cast(receiver->elements()); 2755 for (uint32_t k = start_from; k < length; ++k) { 2756 if (value->StrictEquals(elements->get(k))) return Just<int64_t>(k); 2757 } 2758 return Just<int64_t>(-1); 2759 } 2760 }; 2761 2762 class FastPackedSmiElementsAccessor 2763 : public FastSmiOrObjectElementsAccessor< 2764 FastPackedSmiElementsAccessor, 2765 ElementsKindTraits<PACKED_SMI_ELEMENTS>> { 2766 public: 2767 explicit FastPackedSmiElementsAccessor(const char* name) 2768 : FastSmiOrObjectElementsAccessor< 2769 FastPackedSmiElementsAccessor, 2770 ElementsKindTraits<PACKED_SMI_ELEMENTS>>(name) {} 2771 }; 2772 2773 class FastHoleySmiElementsAccessor 2774 : public FastSmiOrObjectElementsAccessor< 2775 FastHoleySmiElementsAccessor, 2776 ElementsKindTraits<HOLEY_SMI_ELEMENTS>> { 2777 public: 2778 explicit FastHoleySmiElementsAccessor(const char* name) 2779 : FastSmiOrObjectElementsAccessor<FastHoleySmiElementsAccessor, 2780 ElementsKindTraits<HOLEY_SMI_ELEMENTS>>( 2781 name) {} 2782 }; 2783 2784 class FastPackedObjectElementsAccessor 2785 : public FastSmiOrObjectElementsAccessor< 2786 FastPackedObjectElementsAccessor, 2787 ElementsKindTraits<PACKED_ELEMENTS>> { 2788 public: 2789 explicit FastPackedObjectElementsAccessor(const char* name) 2790 : FastSmiOrObjectElementsAccessor<FastPackedObjectElementsAccessor, 2791 ElementsKindTraits<PACKED_ELEMENTS>>( 2792 name) {} 2793 }; 2794 2795 class FastHoleyObjectElementsAccessor 2796 : public FastSmiOrObjectElementsAccessor< 2797 FastHoleyObjectElementsAccessor, ElementsKindTraits<HOLEY_ELEMENTS>> { 2798 public: 2799 explicit FastHoleyObjectElementsAccessor(const char* name) 2800 : FastSmiOrObjectElementsAccessor<FastHoleyObjectElementsAccessor, 2801 ElementsKindTraits<HOLEY_ELEMENTS>>( 2802 name) {} 2803 }; 2804 2805 template <typename Subclass, typename KindTraits> 2806 class FastDoubleElementsAccessor 2807 : public FastElementsAccessor<Subclass, KindTraits> { 2808 public: 2809 explicit FastDoubleElementsAccessor(const char* name) 2810 : FastElementsAccessor<Subclass, KindTraits>(name) {} 2811 2812 static Handle<Object> GetImpl(Isolate* isolate, FixedArrayBase* backing_store, 2813 uint32_t entry) { 2814 return FixedDoubleArray::get(FixedDoubleArray::cast(backing_store), entry, 2815 isolate); 2816 } 2817 2818 static inline void SetImpl(Handle<JSObject> holder, uint32_t entry, 2819 Object* value) { 2820 SetImpl(holder->elements(), entry, value); 2821 } 2822 2823 static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry, 2824 Object* value) { 2825 FixedDoubleArray::cast(backing_store)->set(entry, value->Number()); 2826 } 2827 2828 static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry, 2829 Object* value, WriteBarrierMode mode) { 2830 FixedDoubleArray::cast(backing_store)->set(entry, value->Number()); 2831 } 2832 2833 static void CopyElementsImpl(Isolate* isolate, FixedArrayBase* from, 2834 uint32_t from_start, FixedArrayBase* to, 2835 ElementsKind from_kind, uint32_t to_start, 2836 int packed_size, int copy_size) { 2837 DisallowHeapAllocation no_allocation; 2838 switch (from_kind) { 2839 case PACKED_SMI_ELEMENTS: 2840 CopyPackedSmiToDoubleElements(from, from_start, to, to_start, 2841 packed_size, copy_size); 2842 break; 2843 case HOLEY_SMI_ELEMENTS: 2844 CopySmiToDoubleElements(from, from_start, to, to_start, copy_size); 2845 break; 2846 case PACKED_DOUBLE_ELEMENTS: 2847 case HOLEY_DOUBLE_ELEMENTS: 2848 CopyDoubleToDoubleElements(from, from_start, to, to_start, copy_size); 2849 break; 2850 case PACKED_ELEMENTS: 2851 case HOLEY_ELEMENTS: 2852 CopyObjectToDoubleElements(from, from_start, to, to_start, copy_size); 2853 break; 2854 case DICTIONARY_ELEMENTS: 2855 CopyDictionaryToDoubleElements(isolate, from, from_start, to, to_start, 2856 copy_size); 2857 break; 2858 case FAST_SLOPPY_ARGUMENTS_ELEMENTS: 2859 case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: 2860 case FAST_STRING_WRAPPER_ELEMENTS: 2861 case SLOW_STRING_WRAPPER_ELEMENTS: 2862 case NO_ELEMENTS: 2863 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype) case TYPE##_ELEMENTS: 2864 TYPED_ARRAYS(TYPED_ARRAY_CASE) 2865 #undef TYPED_ARRAY_CASE 2866 // This function is currently only used for JSArrays with non-zero 2867 // length. 2868 UNREACHABLE(); 2869 break; 2870 } 2871 } 2872 2873 static Maybe<bool> CollectValuesOrEntriesImpl( 2874 Isolate* isolate, Handle<JSObject> object, 2875 Handle<FixedArray> values_or_entries, bool get_entries, int* nof_items, 2876 PropertyFilter filter) { 2877 Handle<FixedDoubleArray> elements( 2878 FixedDoubleArray::cast(object->elements()), isolate); 2879 int count = 0; 2880 uint32_t length = elements->length(); 2881 for (uint32_t index = 0; index < length; ++index) { 2882 if (!Subclass::HasEntryImpl(isolate, *elements, index)) continue; 2883 Handle<Object> value = Subclass::GetImpl(isolate, *elements, index); 2884 if (get_entries) { 2885 value = MakeEntryPair(isolate, index, value); 2886 } 2887 values_or_entries->set(count++, *value); 2888 } 2889 *nof_items = count; 2890 return Just(true); 2891 } 2892 2893 static Maybe<int64_t> IndexOfValueImpl(Isolate* isolate, 2894 Handle<JSObject> receiver, 2895 Handle<Object> search_value, 2896 uint32_t start_from, uint32_t length) { 2897 DCHECK(JSObject::PrototypeHasNoElements(isolate, *receiver)); 2898 DisallowHeapAllocation no_gc; 2899 FixedArrayBase* elements_base = receiver->elements(); 2900 Object* value = *search_value; 2901 2902 length = std::min(static_cast<uint32_t>(elements_base->length()), length); 2903 2904 if (start_from >= length) return Just<int64_t>(-1); 2905 2906 if (!value->IsNumber()) { 2907 return Just<int64_t>(-1); 2908 } 2909 if (value->IsNaN()) { 2910 return Just<int64_t>(-1); 2911 } 2912 double numeric_search_value = value->Number(); 2913 FixedDoubleArray* elements = FixedDoubleArray::cast(receiver->elements()); 2914 2915 for (uint32_t k = start_from; k < length; ++k) { 2916 if (elements->is_the_hole(k)) { 2917 continue; 2918 } 2919 if (elements->get_scalar(k) == numeric_search_value) { 2920 return Just<int64_t>(k); 2921 } 2922 } 2923 return Just<int64_t>(-1); 2924 } 2925 }; 2926 2927 class FastPackedDoubleElementsAccessor 2928 : public FastDoubleElementsAccessor< 2929 FastPackedDoubleElementsAccessor, 2930 ElementsKindTraits<PACKED_DOUBLE_ELEMENTS>> { 2931 public: 2932 explicit FastPackedDoubleElementsAccessor(const char* name) 2933 : FastDoubleElementsAccessor<FastPackedDoubleElementsAccessor, 2934 ElementsKindTraits<PACKED_DOUBLE_ELEMENTS>>( 2935 name) {} 2936 }; 2937 2938 class FastHoleyDoubleElementsAccessor 2939 : public FastDoubleElementsAccessor< 2940 FastHoleyDoubleElementsAccessor, 2941 ElementsKindTraits<HOLEY_DOUBLE_ELEMENTS>> { 2942 public: 2943 explicit FastHoleyDoubleElementsAccessor(const char* name) 2944 : FastDoubleElementsAccessor<FastHoleyDoubleElementsAccessor, 2945 ElementsKindTraits<HOLEY_DOUBLE_ELEMENTS>>( 2946 name) {} 2947 }; 2948 2949 2950 // Super class for all external element arrays. 2951 template <ElementsKind Kind, typename ctype> 2952 class TypedElementsAccessor 2953 : public ElementsAccessorBase<TypedElementsAccessor<Kind, ctype>, 2954 ElementsKindTraits<Kind>> { 2955 public: 2956 explicit TypedElementsAccessor(const char* name) 2957 : ElementsAccessorBase<AccessorClass, 2958 ElementsKindTraits<Kind> >(name) {} 2959 2960 typedef typename ElementsKindTraits<Kind>::BackingStore BackingStore; 2961 typedef TypedElementsAccessor<Kind, ctype> AccessorClass; 2962 2963 static inline void SetImpl(Handle<JSObject> holder, uint32_t entry, 2964 Object* value) { 2965 SetImpl(holder->elements(), entry, value); 2966 } 2967 2968 static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry, 2969 Object* value) { 2970 BackingStore::cast(backing_store)->SetValue(entry, value); 2971 } 2972 2973 static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry, 2974 Object* value, WriteBarrierMode mode) { 2975 BackingStore::cast(backing_store)->SetValue(entry, value); 2976 } 2977 2978 static Handle<Object> GetImpl(Isolate* isolate, FixedArrayBase* backing_store, 2979 uint32_t entry) { 2980 return BackingStore::get(isolate, BackingStore::cast(backing_store), entry); 2981 } 2982 2983 static PropertyDetails GetDetailsImpl(JSObject* holder, uint32_t entry) { 2984 return PropertyDetails(kData, DONT_DELETE, PropertyCellType::kNoCell); 2985 } 2986 2987 static PropertyDetails GetDetailsImpl(FixedArrayBase* backing_store, 2988 uint32_t entry) { 2989 return PropertyDetails(kData, DONT_DELETE, PropertyCellType::kNoCell); 2990 } 2991 2992 static bool HasElementImpl(Isolate* isolate, JSObject* holder, uint32_t index, 2993 FixedArrayBase* backing_store, 2994 PropertyFilter filter) { 2995 return index < AccessorClass::GetCapacityImpl(holder, backing_store); 2996 } 2997 2998 static bool HasAccessorsImpl(JSObject* holder, 2999 FixedArrayBase* backing_store) { 3000 return false; 3001 } 3002 3003 static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array, 3004 uint32_t length, 3005 Handle<FixedArrayBase> backing_store) { 3006 // External arrays do not support changing their length. 3007 UNREACHABLE(); 3008 } 3009 3010 static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) { 3011 UNREACHABLE(); 3012 } 3013 3014 static uint32_t GetIndexForEntryImpl(FixedArrayBase* backing_store, 3015 uint32_t entry) { 3016 return entry; 3017 } 3018 3019 static uint32_t GetEntryForIndexImpl(Isolate* isolate, JSObject* holder, 3020 FixedArrayBase* backing_store, 3021 uint32_t index, PropertyFilter filter) { 3022 return index < AccessorClass::GetCapacityImpl(holder, backing_store) 3023 ? index 3024 : kMaxUInt32; 3025 } 3026 3027 static bool WasNeutered(JSObject* holder) { 3028 JSArrayBufferView* view = JSArrayBufferView::cast(holder); 3029 return view->WasNeutered(); 3030 } 3031 3032 static uint32_t GetCapacityImpl(JSObject* holder, 3033 FixedArrayBase* backing_store) { 3034 if (WasNeutered(holder)) return 0; 3035 return backing_store->length(); 3036 } 3037 3038 static uint32_t NumberOfElementsImpl(JSObject* receiver, 3039 FixedArrayBase* backing_store) { 3040 return AccessorClass::GetCapacityImpl(receiver, backing_store); 3041 } 3042 3043 static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver, 3044 KeyAccumulator* accumulator, 3045 AddKeyConversion convert) { 3046 Isolate* isolate = receiver->GetIsolate(); 3047 Handle<FixedArrayBase> elements(receiver->elements(), isolate); 3048 uint32_t length = AccessorClass::GetCapacityImpl(*receiver, *elements); 3049 for (uint32_t i = 0; i < length; i++) { 3050 Handle<Object> value = AccessorClass::GetImpl(isolate, *elements, i); 3051 accumulator->AddKey(value, convert); 3052 } 3053 } 3054 3055 static Maybe<bool> CollectValuesOrEntriesImpl( 3056 Isolate* isolate, Handle<JSObject> object, 3057 Handle<FixedArray> values_or_entries, bool get_entries, int* nof_items, 3058 PropertyFilter filter) { 3059 int count = 0; 3060 if ((filter & ONLY_CONFIGURABLE) == 0) { 3061 Handle<FixedArrayBase> elements(object->elements(), isolate); 3062 uint32_t length = AccessorClass::GetCapacityImpl(*object, *elements); 3063 for (uint32_t index = 0; index < length; ++index) { 3064 Handle<Object> value = 3065 AccessorClass::GetImpl(isolate, *elements, index); 3066 if (get_entries) { 3067 value = MakeEntryPair(isolate, index, value); 3068 } 3069 values_or_entries->set(count++, *value); 3070 } 3071 } 3072 *nof_items = count; 3073 return Just(true); 3074 } 3075 3076 static Object* FillImpl(Handle<JSObject> receiver, Handle<Object> obj_value, 3077 uint32_t start, uint32_t end) { 3078 Handle<JSTypedArray> array = Handle<JSTypedArray>::cast(receiver); 3079 DCHECK(!array->WasNeutered()); 3080 DCHECK(obj_value->IsNumeric()); 3081 3082 ctype value = BackingStore::FromHandle(obj_value); 3083 3084 // Ensure indexes are within array bounds 3085 CHECK_LE(0, start); 3086 CHECK_LE(start, end); 3087 CHECK_LE(end, array->length_value()); 3088 3089 DisallowHeapAllocation no_gc; 3090 BackingStore* elements = BackingStore::cast(receiver->elements()); 3091 ctype* data = static_cast<ctype*>(elements->DataPtr()); 3092 std::fill(data + start, data + end, value); 3093 return *array; 3094 } 3095 3096 static Maybe<bool> IncludesValueImpl(Isolate* isolate, 3097 Handle<JSObject> receiver, 3098 Handle<Object> value, 3099 uint32_t start_from, uint32_t length) { 3100 DisallowHeapAllocation no_gc; 3101 3102 // TODO(caitp): return Just(false) here when implementing strict throwing on 3103 // neutered views. 3104 if (WasNeutered(*receiver)) { 3105 return Just(value->IsUndefined(isolate) && length > start_from); 3106 } 3107 3108 BackingStore* elements = BackingStore::cast(receiver->elements()); 3109 if (value->IsUndefined(isolate) && 3110 length > static_cast<uint32_t>(elements->length())) { 3111 return Just(true); 3112 } 3113 ctype typed_search_value; 3114 // Prototype has no elements, and not searching for the hole --- limit 3115 // search to backing store length. 3116 if (static_cast<uint32_t>(elements->length()) < length) { 3117 length = elements->length(); 3118 } 3119 3120 if (Kind == BIGINT64_ELEMENTS || Kind == BIGUINT64_ELEMENTS) { 3121 if (!value->IsBigInt()) return Just(false); 3122 bool lossless; 3123 typed_search_value = BackingStore::FromHandle(value, &lossless); 3124 if (!lossless) return Just(false); 3125 } else { 3126 if (!value->IsNumber()) return Just(false); 3127 double search_value = value->Number(); 3128 if (!std::isfinite(search_value)) { 3129 // Integral types cannot represent +Inf or NaN. 3130 if (Kind < FLOAT32_ELEMENTS || Kind > FLOAT64_ELEMENTS) { 3131 return Just(false); 3132 } 3133 if (std::isnan(search_value)) { 3134 for (uint32_t k = start_from; k < length; ++k) { 3135 double element_k = elements->get_scalar(k); 3136 if (std::isnan(element_k)) return Just(true); 3137 } 3138 return Just(false); 3139 } 3140 } else if (search_value < std::numeric_limits<ctype>::lowest() || 3141 search_value > std::numeric_limits<ctype>::max()) { 3142 // Return false if value can't be represented in this space. 3143 return Just(false); 3144 } 3145 typed_search_value = static_cast<ctype>(search_value); 3146 if (static_cast<double>(typed_search_value) != search_value) { 3147 return Just(false); // Loss of precision. 3148 } 3149 } 3150 3151 for (uint32_t k = start_from; k < length; ++k) { 3152 ctype element_k = elements->get_scalar(k); 3153 if (element_k == typed_search_value) return Just(true); 3154 } 3155 return Just(false); 3156 } 3157 3158 static Maybe<int64_t> IndexOfValueImpl(Isolate* isolate, 3159 Handle<JSObject> receiver, 3160 Handle<Object> value, 3161 uint32_t start_from, uint32_t length) { 3162 DisallowHeapAllocation no_gc; 3163 3164 if (WasNeutered(*receiver)) return Just<int64_t>(-1); 3165 3166 BackingStore* elements = BackingStore::cast(receiver->elements()); 3167 ctype typed_search_value; 3168 3169 if (Kind == BIGINT64_ELEMENTS || Kind == BIGUINT64_ELEMENTS) { 3170 if (!value->IsBigInt()) return Just<int64_t>(-1); 3171 bool lossless; 3172 typed_search_value = BackingStore::FromHandle(value, &lossless); 3173 if (!lossless) return Just<int64_t>(-1); 3174 } else { 3175 if (!value->IsNumber()) return Just<int64_t>(-1); 3176 double search_value = value->Number(); 3177 if (!std::isfinite(search_value)) { 3178 // Integral types cannot represent +Inf or NaN. 3179 if (Kind < FLOAT32_ELEMENTS || Kind > FLOAT64_ELEMENTS) { 3180 return Just<int64_t>(-1); 3181 } 3182 if (std::isnan(search_value)) { 3183 return Just<int64_t>(-1); 3184 } 3185 } else if (search_value < std::numeric_limits<ctype>::lowest() || 3186 search_value > std::numeric_limits<ctype>::max()) { 3187 // Return false if value can't be represented in this ElementsKind. 3188 return Just<int64_t>(-1); 3189 } 3190 typed_search_value = static_cast<ctype>(search_value); 3191 if (static_cast<double>(typed_search_value) != search_value) { 3192 return Just<int64_t>(-1); // Loss of precision. 3193 } 3194 } 3195 3196 // Prototype has no elements, and not searching for the hole --- limit 3197 // search to backing store length. 3198 if (static_cast<uint32_t>(elements->length()) < length) { 3199 length = elements->length(); 3200 } 3201 3202 for (uint32_t k = start_from; k < length; ++k) { 3203 ctype element_k = elements->get_scalar(k); 3204 if (element_k == typed_search_value) return Just<int64_t>(k); 3205 } 3206 return Just<int64_t>(-1); 3207 } 3208 3209 static Maybe<int64_t> LastIndexOfValueImpl(Handle<JSObject> receiver, 3210 Handle<Object> value, 3211 uint32_t start_from) { 3212 DisallowHeapAllocation no_gc; 3213 DCHECK(!WasNeutered(*receiver)); 3214 3215 BackingStore* elements = BackingStore::cast(receiver->elements()); 3216 ctype typed_search_value; 3217 3218 if (Kind == BIGINT64_ELEMENTS || Kind == BIGUINT64_ELEMENTS) { 3219 if (!value->IsBigInt()) return Just<int64_t>(-1); 3220 bool lossless; 3221 typed_search_value = BackingStore::FromHandle(value, &lossless); 3222 if (!lossless) return Just<int64_t>(-1); 3223 } else { 3224 if (!value->IsNumber()) return Just<int64_t>(-1); 3225 double search_value = value->Number(); 3226 if (!std::isfinite(search_value)) { 3227 if (std::is_integral<ctype>::value) { 3228 // Integral types cannot represent +Inf or NaN. 3229 return Just<int64_t>(-1); 3230 } else if (std::isnan(search_value)) { 3231 // Strict Equality Comparison of NaN is always false. 3232 return Just<int64_t>(-1); 3233 } 3234 } else if (search_value < std::numeric_limits<ctype>::lowest() || 3235 search_value > std::numeric_limits<ctype>::max()) { 3236 // Return -1 if value can't be represented in this ElementsKind. 3237 return Just<int64_t>(-1); 3238 } 3239 typed_search_value = static_cast<ctype>(search_value); 3240 if (static_cast<double>(typed_search_value) != search_value) { 3241 return Just<int64_t>(-1); // Loss of precision. 3242 } 3243 } 3244 3245 DCHECK_LT(start_from, elements->length()); 3246 3247 uint32_t k = start_from; 3248 do { 3249 ctype element_k = elements->get_scalar(k); 3250 if (element_k == typed_search_value) return Just<int64_t>(k); 3251 } while (k-- != 0); 3252 return Just<int64_t>(-1); 3253 } 3254 3255 static void ReverseImpl(JSObject* receiver) { 3256 DisallowHeapAllocation no_gc; 3257 DCHECK(!WasNeutered(receiver)); 3258 3259 BackingStore* elements = BackingStore::cast(receiver->elements()); 3260 3261 uint32_t len = elements->length(); 3262 if (len == 0) return; 3263 3264 ctype* data = static_cast<ctype*>(elements->DataPtr()); 3265 std::reverse(data, data + len); 3266 } 3267 3268 static Handle<FixedArray> CreateListFromArrayLikeImpl(Isolate* isolate, 3269 Handle<JSObject> object, 3270 uint32_t length) { 3271 DCHECK(!WasNeutered(*object)); 3272 DCHECK(object->IsJSTypedArray()); 3273 Handle<FixedArray> result = isolate->factory()->NewFixedArray(length); 3274 Handle<BackingStore> elements(BackingStore::cast(object->elements()), 3275 isolate); 3276 for (uint32_t i = 0; i < length; i++) { 3277 Handle<Object> value = AccessorClass::GetImpl(isolate, *elements, i); 3278 result->set(i, *value); 3279 } 3280 return result; 3281 } 3282 3283 static void CopyTypedArrayElementsSliceImpl(JSTypedArray* source, 3284 JSTypedArray* destination, 3285 size_t start, size_t end) { 3286 DisallowHeapAllocation no_gc; 3287 DCHECK_EQ(destination->GetElementsKind(), AccessorClass::kind()); 3288 DCHECK(!source->WasNeutered()); 3289 DCHECK(!destination->WasNeutered()); 3290 DCHECK_LE(start, end); 3291 DCHECK_LE(end, source->length_value()); 3292 3293 size_t count = end - start; 3294 DCHECK_LE(count, destination->length_value()); 3295 3296 FixedTypedArrayBase* src_elements = 3297 FixedTypedArrayBase::cast(source->elements()); 3298 BackingStore* dest_elements = BackingStore::cast(destination->elements()); 3299 3300 size_t element_size = source->element_size(); 3301 uint8_t* source_data = 3302 static_cast<uint8_t*>(src_elements->DataPtr()) + start * element_size; 3303 3304 // Fast path for the same type result array 3305 if (source->type() == destination->type()) { 3306 uint8_t* dest_data = static_cast<uint8_t*>(dest_elements->DataPtr()); 3307 3308 // The spec defines the copy-step iteratively, which means that we 3309 // cannot use memcpy if the buffer is shared. 3310 uint8_t* end_ptr = source_data + count * element_size; 3311 while (source_data < end_ptr) { 3312 *dest_data++ = *source_data++; 3313 } 3314 return; 3315 } 3316 3317 switch (source->GetElementsKind()) { 3318 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype) \ 3319 case TYPE##_ELEMENTS: \ 3320 CopyBetweenBackingStores<Type##ArrayTraits>(source_data, dest_elements, \ 3321 count, 0); \ 3322 break; 3323 TYPED_ARRAYS(TYPED_ARRAY_CASE) 3324 #undef TYPED_ARRAY_CASE 3325 default: 3326 UNREACHABLE(); 3327 break; 3328 } 3329 } 3330 3331 static bool HasSimpleRepresentation(InstanceType type) { 3332 return !(type == FIXED_FLOAT32_ARRAY_TYPE || 3333 type == FIXED_FLOAT64_ARRAY_TYPE || 3334 type == FIXED_UINT8_CLAMPED_ARRAY_TYPE); 3335 } 3336 3337 template <typename SourceTraits> 3338 static void CopyBetweenBackingStores(void* source_data_ptr, 3339 BackingStore* dest, size_t length, 3340 uint32_t offset) { 3341 DisallowHeapAllocation no_gc; 3342 for (uint32_t i = 0; i < length; i++) { 3343 // We use scalar accessors to avoid boxing/unboxing, so there are no 3344 // allocations. 3345 typename SourceTraits::ElementType elem = 3346 FixedTypedArray<SourceTraits>::get_scalar_from_data_ptr( 3347 source_data_ptr, i); 3348 dest->set(offset + i, dest->from(elem)); 3349 } 3350 } 3351 3352 static void CopyElementsFromTypedArray(JSTypedArray* source, 3353 JSTypedArray* destination, 3354 size_t length, uint32_t offset) { 3355 // The source is a typed array, so we know we don't need to do ToNumber 3356 // side-effects, as the source elements will always be a number. 3357 DisallowHeapAllocation no_gc; 3358 3359 FixedTypedArrayBase* source_elements = 3360 FixedTypedArrayBase::cast(source->elements()); 3361 BackingStore* destination_elements = 3362 BackingStore::cast(destination->elements()); 3363 3364 DCHECK_LE(offset, destination->length_value()); 3365 DCHECK_LE(length, destination->length_value() - offset); 3366 DCHECK(source->length()->IsSmi()); 3367 DCHECK_LE(length, source->length_value()); 3368 3369 InstanceType source_type = source_elements->map()->instance_type(); 3370 InstanceType destination_type = 3371 destination_elements->map()->instance_type(); 3372 3373 bool same_type = source_type == destination_type; 3374 bool same_size = source->element_size() == destination->element_size(); 3375 bool both_are_simple = HasSimpleRepresentation(source_type) && 3376 HasSimpleRepresentation(destination_type); 3377 3378 uint8_t* source_data = static_cast<uint8_t*>(source_elements->DataPtr()); 3379 uint8_t* dest_data = static_cast<uint8_t*>(destination_elements->DataPtr()); 3380 size_t source_byte_length = NumberToSize(source->byte_length()); 3381 size_t dest_byte_length = NumberToSize(destination->byte_length()); 3382 3383 // We can simply copy the backing store if the types are the same, or if 3384 // we are converting e.g. Uint8 <-> Int8, as the binary representation 3385 // will be the same. This is not the case for floats or clamped Uint8, 3386 // which have special conversion operations. 3387 if (same_type || (same_size && both_are_simple)) { 3388 size_t element_size = source->element_size(); 3389 std::memmove(dest_data + offset * element_size, source_data, 3390 length * element_size); 3391 } else { 3392 std::unique_ptr<uint8_t[]> cloned_source_elements; 3393 3394 // If the typedarrays are overlapped, clone the source. 3395 if (dest_data + dest_byte_length > source_data && 3396 source_data + source_byte_length > dest_data) { 3397 cloned_source_elements.reset(new uint8_t[source_byte_length]); 3398 std::memcpy(cloned_source_elements.get(), source_data, 3399 source_byte_length); 3400 source_data = cloned_source_elements.get(); 3401 } 3402 3403 switch (source->GetElementsKind()) { 3404 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype) \ 3405 case TYPE##_ELEMENTS: \ 3406 CopyBetweenBackingStores<Type##ArrayTraits>( \ 3407 source_data, destination_elements, length, offset); \ 3408 break; 3409 TYPED_ARRAYS(TYPED_ARRAY_CASE) 3410 default: 3411 UNREACHABLE(); 3412 break; 3413 } 3414 #undef TYPED_ARRAY_CASE 3415 } 3416 } 3417 3418 static bool HoleyPrototypeLookupRequired(Isolate* isolate, Context* context, 3419 JSArray* source) { 3420 DisallowHeapAllocation no_gc; 3421 DisallowJavascriptExecution no_js(isolate); 3422 3423 #ifdef V8_ENABLE_FORCE_SLOW_PATH 3424 if (isolate->force_slow_path()) return true; 3425 #endif 3426 3427 Object* source_proto = source->map()->prototype(); 3428 3429 // Null prototypes are OK - we don't need to do prototype chain lookups on 3430 // them. 3431 if (source_proto->IsNull(isolate)) return false; 3432 if (source_proto->IsJSProxy()) return true; 3433 if (!context->native_context()->is_initial_array_prototype( 3434 JSObject::cast(source_proto))) { 3435 return true; 3436 } 3437 3438 return !isolate->IsNoElementsProtectorIntact(context); 3439 } 3440 3441 static bool TryCopyElementsFastNumber(Context* context, JSArray* source, 3442 JSTypedArray* destination, 3443 size_t length, uint32_t offset) { 3444 if (Kind == BIGINT64_ELEMENTS || Kind == BIGUINT64_ELEMENTS) return false; 3445 Isolate* isolate = source->GetIsolate(); 3446 DisallowHeapAllocation no_gc; 3447 DisallowJavascriptExecution no_js(isolate); 3448 3449 size_t current_length; 3450 DCHECK(source->length()->IsNumber() && 3451 TryNumberToSize(source->length(), ¤t_length) && 3452 length <= current_length); 3453 USE(current_length); 3454 3455 size_t dest_length = destination->length_value(); 3456 DCHECK(length + offset <= dest_length); 3457 USE(dest_length); 3458 3459 ElementsKind kind = source->GetElementsKind(); 3460 BackingStore* dest = BackingStore::cast(destination->elements()); 3461 3462 // When we find the hole, we normally have to look up the element on the 3463 // prototype chain, which is not handled here and we return false instead. 3464 // When the array has the original array prototype, and that prototype has 3465 // not been changed in a way that would affect lookups, we can just convert 3466 // the hole into undefined. 3467 if (HoleyPrototypeLookupRequired(isolate, context, source)) return false; 3468 3469 Object* undefined = ReadOnlyRoots(isolate).undefined_value(); 3470 3471 // Fastpath for packed Smi kind. 3472 if (kind == PACKED_SMI_ELEMENTS) { 3473 FixedArray* source_store = FixedArray::cast(source->elements()); 3474 3475 for (uint32_t i = 0; i < length; i++) { 3476 Object* elem = source_store->get(i); 3477 DCHECK(elem->IsSmi()); 3478 int int_value = Smi::ToInt(elem); 3479 dest->set(offset + i, dest->from(int_value)); 3480 } 3481 return true; 3482 } else if (kind == HOLEY_SMI_ELEMENTS) { 3483 FixedArray* source_store = FixedArray::cast(source->elements()); 3484 for (uint32_t i = 0; i < length; i++) { 3485 if (source_store->is_the_hole(isolate, i)) { 3486 dest->SetValue(offset + i, undefined); 3487 } else { 3488 Object* elem = source_store->get(i); 3489 DCHECK(elem->IsSmi()); 3490 int int_value = Smi::ToInt(elem); 3491 dest->set(offset + i, dest->from(int_value)); 3492 } 3493 } 3494 return true; 3495 } else if (kind == PACKED_DOUBLE_ELEMENTS) { 3496 // Fastpath for packed double kind. We avoid boxing and then immediately 3497 // unboxing the double here by using get_scalar. 3498 FixedDoubleArray* source_store = 3499 FixedDoubleArray::cast(source->elements()); 3500 3501 for (uint32_t i = 0; i < length; i++) { 3502 // Use the from_double conversion for this specific TypedArray type, 3503 // rather than relying on C++ to convert elem. 3504 double elem = source_store->get_scalar(i); 3505 dest->set(offset + i, dest->from(elem)); 3506 } 3507 return true; 3508 } else if (kind == HOLEY_DOUBLE_ELEMENTS) { 3509 FixedDoubleArray* source_store = 3510 FixedDoubleArray::cast(source->elements()); 3511 for (uint32_t i = 0; i < length; i++) { 3512 if (source_store->is_the_hole(i)) { 3513 dest->SetValue(offset + i, undefined); 3514 } else { 3515 double elem = source_store->get_scalar(i); 3516 dest->set(offset + i, dest->from(elem)); 3517 } 3518 } 3519 return true; 3520 } 3521 return false; 3522 } 3523 3524 static Object* CopyElementsHandleSlow(Handle<Object> source, 3525 Handle<JSTypedArray> destination, 3526 size_t length, uint32_t offset) { 3527 Isolate* isolate = destination->GetIsolate(); 3528 Handle<BackingStore> destination_elements( 3529 BackingStore::cast(destination->elements()), isolate); 3530 for (uint32_t i = 0; i < length; i++) { 3531 LookupIterator it(isolate, source, i); 3532 Handle<Object> elem; 3533 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, elem, 3534 Object::GetProperty(&it)); 3535 if (Kind == BIGINT64_ELEMENTS || Kind == BIGUINT64_ELEMENTS) { 3536 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, elem, 3537 BigInt::FromObject(isolate, elem)); 3538 } else { 3539 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, elem, 3540 Object::ToNumber(isolate, elem)); 3541 } 3542 3543 if (V8_UNLIKELY(destination->WasNeutered())) { 3544 const char* op = "set"; 3545 const MessageTemplate::Template message = 3546 MessageTemplate::kDetachedOperation; 3547 Handle<String> operation = 3548 isolate->factory()->NewStringFromAsciiChecked(op); 3549 THROW_NEW_ERROR_RETURN_FAILURE(isolate, 3550 NewTypeError(message, operation)); 3551 } 3552 // The spec says we store the length, then get each element, so we don't 3553 // need to check changes to length. 3554 destination_elements->SetValue(offset + i, *elem); 3555 } 3556 return *isolate->factory()->undefined_value(); 3557 } 3558 3559 // This doesn't guarantee that the destination array will be completely 3560 // filled. The caller must do this by passing a source with equal length, if 3561 // that is required. 3562 static Object* CopyElementsHandleImpl(Handle<Object> source, 3563 Handle<JSObject> destination, 3564 size_t length, uint32_t offset) { 3565 Isolate* isolate = destination->GetIsolate(); 3566 Handle<JSTypedArray> destination_ta = 3567 Handle<JSTypedArray>::cast(destination); 3568 DCHECK_LE(offset + length, destination_ta->length_value()); 3569 3570 if (length == 0) return *isolate->factory()->undefined_value(); 3571 3572 // All conversions from TypedArrays can be done without allocation. 3573 if (source->IsJSTypedArray()) { 3574 Handle<JSTypedArray> source_ta = Handle<JSTypedArray>::cast(source); 3575 ElementsKind source_kind = source_ta->GetElementsKind(); 3576 bool source_is_bigint = 3577 source_kind == BIGINT64_ELEMENTS || source_kind == BIGUINT64_ELEMENTS; 3578 bool target_is_bigint = 3579 Kind == BIGINT64_ELEMENTS || Kind == BIGUINT64_ELEMENTS; 3580 if (target_is_bigint) { 3581 if (V8_UNLIKELY(!source_is_bigint)) { 3582 Handle<Object> first = 3583 JSReceiver::GetElement(isolate, source_ta, 0).ToHandleChecked(); 3584 THROW_NEW_ERROR_RETURN_FAILURE( 3585 isolate, NewTypeError(MessageTemplate::kBigIntFromObject, first)); 3586 } 3587 } else { 3588 if (V8_UNLIKELY(source_is_bigint)) { 3589 THROW_NEW_ERROR_RETURN_FAILURE( 3590 isolate, NewTypeError(MessageTemplate::kBigIntToNumber)); 3591 } 3592 } 3593 // If we have to copy more elements than we have in the source, we need to 3594 // do special handling and conversion; that happens in the slow case. 3595 if (length + offset <= source_ta->length_value()) { 3596 DCHECK(length == 0 || !source_ta->WasNeutered()); 3597 CopyElementsFromTypedArray(*source_ta, *destination_ta, length, offset); 3598 return *isolate->factory()->undefined_value(); 3599 } 3600 } 3601 3602 // Fast cases for packed numbers kinds where we don't need to allocate. 3603 if (source->IsJSArray()) { 3604 Handle<JSArray> source_js_array = Handle<JSArray>::cast(source); 3605 size_t current_length; 3606 if (source_js_array->length()->IsNumber() && 3607 TryNumberToSize(source_js_array->length(), ¤t_length)) { 3608 if (length <= current_length) { 3609 Handle<JSArray> source_array = Handle<JSArray>::cast(source); 3610 if (TryCopyElementsFastNumber(isolate->context(), *source_array, 3611 *destination_ta, length, offset)) { 3612 return *isolate->factory()->undefined_value(); 3613 } 3614 } 3615 } 3616 } 3617 // Final generic case that handles prototype chain lookups, getters, proxies 3618 // and observable side effects via valueOf, etc. 3619 return CopyElementsHandleSlow(source, destination_ta, length, offset); 3620 } 3621 }; 3622 3623 #define FIXED_ELEMENTS_ACCESSOR(Type, type, TYPE, ctype) \ 3624 typedef TypedElementsAccessor<TYPE##_ELEMENTS, ctype> \ 3625 Fixed##Type##ElementsAccessor; 3626 3627 TYPED_ARRAYS(FIXED_ELEMENTS_ACCESSOR) 3628 #undef FIXED_ELEMENTS_ACCESSOR 3629 3630 template <typename Subclass, typename ArgumentsAccessor, typename KindTraits> 3631 class SloppyArgumentsElementsAccessor 3632 : public ElementsAccessorBase<Subclass, KindTraits> { 3633 public: 3634 explicit SloppyArgumentsElementsAccessor(const char* name) 3635 : ElementsAccessorBase<Subclass, KindTraits>(name) { 3636 USE(KindTraits::Kind); 3637 } 3638 3639 static void ConvertArgumentsStoreResult( 3640 Handle<SloppyArgumentsElements> elements, Handle<Object> result) { 3641 UNREACHABLE(); 3642 } 3643 3644 static Handle<Object> GetImpl(Isolate* isolate, FixedArrayBase* parameters, 3645 uint32_t entry) { 3646 Handle<SloppyArgumentsElements> elements( 3647 SloppyArgumentsElements::cast(parameters), isolate); 3648 uint32_t length = elements->parameter_map_length(); 3649 if (entry < length) { 3650 // Read context mapped entry. 3651 DisallowHeapAllocation no_gc; 3652 Object* probe = elements->get_mapped_entry(entry); 3653 DCHECK(!probe->IsTheHole(isolate)); 3654 Context* context = elements->context(); 3655 int context_entry = Smi::ToInt(probe); 3656 DCHECK(!context->get(context_entry)->IsTheHole(isolate)); 3657 return handle(context->get(context_entry), isolate); 3658 } else { 3659 // Entry is not context mapped, defer to the arguments. 3660 Handle<Object> result = ArgumentsAccessor::GetImpl( 3661 isolate, elements->arguments(), entry - length); 3662 return Subclass::ConvertArgumentsStoreResult(isolate, elements, result); 3663 } 3664 } 3665 3666 static void TransitionElementsKindImpl(Handle<JSObject> object, 3667 Handle<Map> map) { 3668 UNREACHABLE(); 3669 } 3670 3671 static void GrowCapacityAndConvertImpl(Handle<JSObject> object, 3672 uint32_t capacity) { 3673 UNREACHABLE(); 3674 } 3675 3676 static inline void SetImpl(Handle<JSObject> holder, uint32_t entry, 3677 Object* value) { 3678 SetImpl(holder->elements(), entry, value); 3679 } 3680 3681 static inline void SetImpl(FixedArrayBase* store, uint32_t entry, 3682 Object* value) { 3683 SloppyArgumentsElements* elements = SloppyArgumentsElements::cast(store); 3684 uint32_t length = elements->parameter_map_length(); 3685 if (entry < length) { 3686 // Store context mapped entry. 3687 DisallowHeapAllocation no_gc; 3688 Object* probe = elements->get_mapped_entry(entry); 3689 DCHECK(!probe->IsTheHole()); 3690 Context* context = elements->context(); 3691 int context_entry = Smi::ToInt(probe); 3692 DCHECK(!context->get(context_entry)->IsTheHole()); 3693 context->set(context_entry, value); 3694 } else { 3695 // Entry is not context mapped defer to arguments. 3696 FixedArray* arguments = elements->arguments(); 3697 Object* current = ArgumentsAccessor::GetRaw(arguments, entry - length); 3698 if (current->IsAliasedArgumentsEntry()) { 3699 AliasedArgumentsEntry* alias = AliasedArgumentsEntry::cast(current); 3700 Context* context = elements->context(); 3701 int context_entry = alias->aliased_context_slot(); 3702 DCHECK(!context->get(context_entry)->IsTheHole()); 3703 context->set(context_entry, value); 3704 } else { 3705 ArgumentsAccessor::SetImpl(arguments, entry - length, value); 3706 } 3707 } 3708 } 3709 3710 static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array, 3711 uint32_t length, 3712 Handle<FixedArrayBase> parameter_map) { 3713 // Sloppy arguments objects are not arrays. 3714 UNREACHABLE(); 3715 } 3716 3717 static uint32_t GetCapacityImpl(JSObject* holder, FixedArrayBase* store) { 3718 SloppyArgumentsElements* elements = SloppyArgumentsElements::cast(store); 3719 FixedArray* arguments = elements->arguments(); 3720 return elements->parameter_map_length() + 3721 ArgumentsAccessor::GetCapacityImpl(holder, arguments); 3722 } 3723 3724 static uint32_t GetMaxNumberOfEntries(JSObject* holder, 3725 FixedArrayBase* backing_store) { 3726 SloppyArgumentsElements* elements = 3727 SloppyArgumentsElements::cast(backing_store); 3728 FixedArrayBase* arguments = elements->arguments(); 3729 return elements->parameter_map_length() + 3730 ArgumentsAccessor::GetMaxNumberOfEntries(holder, arguments); 3731 } 3732 3733 static uint32_t NumberOfElementsImpl(JSObject* receiver, 3734 FixedArrayBase* backing_store) { 3735 Isolate* isolate = receiver->GetIsolate(); 3736 SloppyArgumentsElements* elements = 3737 SloppyArgumentsElements::cast(backing_store); 3738 FixedArrayBase* arguments = elements->arguments(); 3739 uint32_t nof_elements = 0; 3740 uint32_t length = elements->parameter_map_length(); 3741 for (uint32_t entry = 0; entry < length; entry++) { 3742 if (HasParameterMapArg(isolate, elements, entry)) nof_elements++; 3743 } 3744 return nof_elements + 3745 ArgumentsAccessor::NumberOfElementsImpl(receiver, arguments); 3746 } 3747 3748 static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver, 3749 KeyAccumulator* accumulator, 3750 AddKeyConversion convert) { 3751 Isolate* isolate = accumulator->isolate(); 3752 Handle<FixedArrayBase> elements(receiver->elements(), isolate); 3753 uint32_t length = GetCapacityImpl(*receiver, *elements); 3754 for (uint32_t entry = 0; entry < length; entry++) { 3755 if (!HasEntryImpl(isolate, *elements, entry)) continue; 3756 Handle<Object> value = GetImpl(isolate, *elements, entry); 3757 accumulator->AddKey(value, convert); 3758 } 3759 } 3760 3761 static bool HasEntryImpl(Isolate* isolate, FixedArrayBase* parameters, 3762 uint32_t entry) { 3763 SloppyArgumentsElements* elements = 3764 SloppyArgumentsElements::cast(parameters); 3765 uint32_t length = elements->parameter_map_length(); 3766 if (entry < length) { 3767 return HasParameterMapArg(isolate, elements, entry); 3768 } 3769 FixedArrayBase* arguments = elements->arguments(); 3770 return ArgumentsAccessor::HasEntryImpl(isolate, arguments, entry - length); 3771 } 3772 3773 static bool HasAccessorsImpl(JSObject* holder, 3774 FixedArrayBase* backing_store) { 3775 SloppyArgumentsElements* elements = 3776 SloppyArgumentsElements::cast(backing_store); 3777 FixedArray* arguments = elements->arguments(); 3778 return ArgumentsAccessor::HasAccessorsImpl(holder, arguments); 3779 } 3780 3781 static uint32_t GetIndexForEntryImpl(FixedArrayBase* parameters, 3782 uint32_t entry) { 3783 SloppyArgumentsElements* elements = 3784 SloppyArgumentsElements::cast(parameters); 3785 uint32_t length = elements->parameter_map_length(); 3786 if (entry < length) return entry; 3787 FixedArray* arguments = elements->arguments(); 3788 return ArgumentsAccessor::GetIndexForEntryImpl(arguments, entry - length); 3789 } 3790 3791 static uint32_t GetEntryForIndexImpl(Isolate* isolate, JSObject* holder, 3792 FixedArrayBase* parameters, 3793 uint32_t index, PropertyFilter filter) { 3794 SloppyArgumentsElements* elements = 3795 SloppyArgumentsElements::cast(parameters); 3796 if (HasParameterMapArg(isolate, elements, index)) return index; 3797 FixedArray* arguments = elements->arguments(); 3798 uint32_t entry = ArgumentsAccessor::GetEntryForIndexImpl( 3799 isolate, holder, arguments, index, filter); 3800 if (entry == kMaxUInt32) return kMaxUInt32; 3801 // Arguments entries could overlap with the dictionary entries, hence offset 3802 // them by the number of context mapped entries. 3803 return elements->parameter_map_length() + entry; 3804 } 3805 3806 static PropertyDetails GetDetailsImpl(JSObject* holder, uint32_t entry) { 3807 SloppyArgumentsElements* elements = 3808 SloppyArgumentsElements::cast(holder->elements()); 3809 uint32_t length = elements->parameter_map_length(); 3810 if (entry < length) { 3811 return PropertyDetails(kData, NONE, PropertyCellType::kNoCell); 3812 } 3813 FixedArray* arguments = elements->arguments(); 3814 return ArgumentsAccessor::GetDetailsImpl(arguments, entry - length); 3815 } 3816 3817 static bool HasParameterMapArg(Isolate* isolate, 3818 SloppyArgumentsElements* elements, 3819 uint32_t index) { 3820 uint32_t length = elements->parameter_map_length(); 3821 if (index >= length) return false; 3822 return !elements->get_mapped_entry(index)->IsTheHole(isolate); 3823 } 3824 3825 static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) { 3826 Handle<SloppyArgumentsElements> elements( 3827 SloppyArgumentsElements::cast(obj->elements()), obj->GetIsolate()); 3828 uint32_t length = elements->parameter_map_length(); 3829 uint32_t delete_or_entry = entry; 3830 if (entry < length) { 3831 delete_or_entry = kMaxUInt32; 3832 } 3833 Subclass::SloppyDeleteImpl(obj, elements, delete_or_entry); 3834 // SloppyDeleteImpl allocates a new dictionary elements store. For making 3835 // heap verification happy we postpone clearing out the mapped entry. 3836 if (entry < length) { 3837 elements->set_mapped_entry(entry, 3838 obj->GetReadOnlyRoots().the_hole_value()); 3839 } 3840 } 3841 3842 static void SloppyDeleteImpl(Handle<JSObject> obj, 3843 Handle<SloppyArgumentsElements> elements, 3844 uint32_t entry) { 3845 // Implemented in subclasses. 3846 UNREACHABLE(); 3847 } 3848 3849 static void CollectElementIndicesImpl(Handle<JSObject> object, 3850 Handle<FixedArrayBase> backing_store, 3851 KeyAccumulator* keys) { 3852 Isolate* isolate = keys->isolate(); 3853 uint32_t nof_indices = 0; 3854 Handle<FixedArray> indices = isolate->factory()->NewFixedArray( 3855 GetCapacityImpl(*object, *backing_store)); 3856 DirectCollectElementIndicesImpl(isolate, object, backing_store, 3857 GetKeysConversion::kKeepNumbers, 3858 ENUMERABLE_STRINGS, indices, &nof_indices); 3859 SortIndices(isolate, indices, nof_indices); 3860 for (uint32_t i = 0; i < nof_indices; i++) { 3861 keys->AddKey(indices->get(i)); 3862 } 3863 } 3864 3865 static Handle<FixedArray> DirectCollectElementIndicesImpl( 3866 Isolate* isolate, Handle<JSObject> object, 3867 Handle<FixedArrayBase> backing_store, GetKeysConversion convert, 3868 PropertyFilter filter, Handle<FixedArray> list, uint32_t* nof_indices, 3869 uint32_t insertion_index = 0) { 3870 Handle<SloppyArgumentsElements> elements = 3871 Handle<SloppyArgumentsElements>::cast(backing_store); 3872 uint32_t length = elements->parameter_map_length(); 3873 3874 for (uint32_t i = 0; i < length; ++i) { 3875 if (elements->get_mapped_entry(i)->IsTheHole(isolate)) continue; 3876 if (convert == GetKeysConversion::kConvertToString) { 3877 Handle<String> index_string = isolate->factory()->Uint32ToString(i); 3878 list->set(insertion_index, *index_string); 3879 } else { 3880 list->set(insertion_index, Smi::FromInt(i), SKIP_WRITE_BARRIER); 3881 } 3882 insertion_index++; 3883 } 3884 3885 Handle<FixedArray> store(elements->arguments(), isolate); 3886 return ArgumentsAccessor::DirectCollectElementIndicesImpl( 3887 isolate, object, store, convert, filter, list, nof_indices, 3888 insertion_index); 3889 } 3890 3891 static Maybe<bool> IncludesValueImpl(Isolate* isolate, 3892 Handle<JSObject> object, 3893 Handle<Object> value, 3894 uint32_t start_from, uint32_t length) { 3895 DCHECK(JSObject::PrototypeHasNoElements(isolate, *object)); 3896 Handle<Map> original_map(object->map(), isolate); 3897 Handle<SloppyArgumentsElements> elements( 3898 SloppyArgumentsElements::cast(object->elements()), isolate); 3899 bool search_for_hole = value->IsUndefined(isolate); 3900 3901 for (uint32_t k = start_from; k < length; ++k) { 3902 DCHECK_EQ(object->map(), *original_map); 3903 uint32_t entry = 3904 GetEntryForIndexImpl(isolate, *object, *elements, k, ALL_PROPERTIES); 3905 if (entry == kMaxUInt32) { 3906 if (search_for_hole) return Just(true); 3907 continue; 3908 } 3909 3910 Handle<Object> element_k = Subclass::GetImpl(isolate, *elements, entry); 3911 3912 if (element_k->IsAccessorPair()) { 3913 LookupIterator it(isolate, object, k, LookupIterator::OWN); 3914 DCHECK(it.IsFound()); 3915 DCHECK_EQ(it.state(), LookupIterator::ACCESSOR); 3916 ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, element_k, 3917 Object::GetPropertyWithAccessor(&it), 3918 Nothing<bool>()); 3919 3920 if (value->SameValueZero(*element_k)) return Just(true); 3921 3922 if (object->map() != *original_map) { 3923 // Some mutation occurred in accessor. Abort "fast" path 3924 return IncludesValueSlowPath(isolate, object, value, k + 1, length); 3925 } 3926 } else if (value->SameValueZero(*element_k)) { 3927 return Just(true); 3928 } 3929 } 3930 return Just(false); 3931 } 3932 3933 static Maybe<int64_t> IndexOfValueImpl(Isolate* isolate, 3934 Handle<JSObject> object, 3935 Handle<Object> value, 3936 uint32_t start_from, uint32_t length) { 3937 DCHECK(JSObject::PrototypeHasNoElements(isolate, *object)); 3938 Handle<Map> original_map(object->map(), isolate); 3939 Handle<SloppyArgumentsElements> elements( 3940 SloppyArgumentsElements::cast(object->elements()), isolate); 3941 3942 for (uint32_t k = start_from; k < length; ++k) { 3943 DCHECK_EQ(object->map(), *original_map); 3944 uint32_t entry = 3945 GetEntryForIndexImpl(isolate, *object, *elements, k, ALL_PROPERTIES); 3946 if (entry == kMaxUInt32) { 3947 continue; 3948 } 3949 3950 Handle<Object> element_k = Subclass::GetImpl(isolate, *elements, entry); 3951 3952 if (element_k->IsAccessorPair()) { 3953 LookupIterator it(isolate, object, k, LookupIterator::OWN); 3954 DCHECK(it.IsFound()); 3955 DCHECK_EQ(it.state(), LookupIterator::ACCESSOR); 3956 ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, element_k, 3957 Object::GetPropertyWithAccessor(&it), 3958 Nothing<int64_t>()); 3959 3960 if (value->StrictEquals(*element_k)) { 3961 return Just<int64_t>(k); 3962 } 3963 3964 if (object->map() != *original_map) { 3965 // Some mutation occurred in accessor. Abort "fast" path. 3966 return IndexOfValueSlowPath(isolate, object, value, k + 1, length); 3967 } 3968 } else if (value->StrictEquals(*element_k)) { 3969 return Just<int64_t>(k); 3970 } 3971 } 3972 return Just<int64_t>(-1); 3973 } 3974 3975 static Handle<JSObject> SliceImpl(Handle<JSObject> receiver, uint32_t start, 3976 uint32_t end) { 3977 Isolate* isolate = receiver->GetIsolate(); 3978 uint32_t result_len = end < start ? 0u : end - start; 3979 Handle<JSArray> result_array = 3980 isolate->factory()->NewJSArray(HOLEY_ELEMENTS, result_len, result_len); 3981 DisallowHeapAllocation no_gc; 3982 FixedArray* elements = FixedArray::cast(result_array->elements()); 3983 FixedArray* parameters = FixedArray::cast(receiver->elements()); 3984 uint32_t insertion_index = 0; 3985 for (uint32_t i = start; i < end; i++) { 3986 uint32_t entry = GetEntryForIndexImpl(isolate, *receiver, parameters, i, 3987 ALL_PROPERTIES); 3988 if (entry != kMaxUInt32 && HasEntryImpl(isolate, parameters, entry)) { 3989 elements->set(insertion_index, *GetImpl(isolate, parameters, entry)); 3990 } else { 3991 elements->set_the_hole(isolate, insertion_index); 3992 } 3993 insertion_index++; 3994 } 3995 return result_array; 3996 } 3997 }; 3998 3999 4000 class SlowSloppyArgumentsElementsAccessor 4001 : public SloppyArgumentsElementsAccessor< 4002 SlowSloppyArgumentsElementsAccessor, DictionaryElementsAccessor, 4003 ElementsKindTraits<SLOW_SLOPPY_ARGUMENTS_ELEMENTS> > { 4004 public: 4005 explicit SlowSloppyArgumentsElementsAccessor(const char* name) 4006 : SloppyArgumentsElementsAccessor< 4007 SlowSloppyArgumentsElementsAccessor, DictionaryElementsAccessor, 4008 ElementsKindTraits<SLOW_SLOPPY_ARGUMENTS_ELEMENTS> >(name) {} 4009 4010 static Handle<Object> ConvertArgumentsStoreResult( 4011 Isolate* isolate, Handle<SloppyArgumentsElements> elements, 4012 Handle<Object> result) { 4013 // Elements of the arguments object in slow mode might be slow aliases. 4014 if (result->IsAliasedArgumentsEntry()) { 4015 DisallowHeapAllocation no_gc; 4016 AliasedArgumentsEntry* alias = AliasedArgumentsEntry::cast(*result); 4017 Context* context = elements->context(); 4018 int context_entry = alias->aliased_context_slot(); 4019 DCHECK(!context->get(context_entry)->IsTheHole(isolate)); 4020 return handle(context->get(context_entry), isolate); 4021 } 4022 return result; 4023 } 4024 static void SloppyDeleteImpl(Handle<JSObject> obj, 4025 Handle<SloppyArgumentsElements> elements, 4026 uint32_t entry) { 4027 // No need to delete a context mapped entry from the arguments elements. 4028 if (entry == kMaxUInt32) return; 4029 Isolate* isolate = obj->GetIsolate(); 4030 Handle<NumberDictionary> dict(NumberDictionary::cast(elements->arguments()), 4031 isolate); 4032 int length = elements->parameter_map_length(); 4033 dict = NumberDictionary::DeleteEntry(isolate, dict, entry - length); 4034 elements->set_arguments(*dict); 4035 } 4036 static void AddImpl(Handle<JSObject> object, uint32_t index, 4037 Handle<Object> value, PropertyAttributes attributes, 4038 uint32_t new_capacity) { 4039 Isolate* isolate = object->GetIsolate(); 4040 Handle<SloppyArgumentsElements> elements( 4041 SloppyArgumentsElements::cast(object->elements()), isolate); 4042 Handle<FixedArrayBase> old_arguments( 4043 FixedArrayBase::cast(elements->arguments()), isolate); 4044 Handle<NumberDictionary> dictionary = 4045 old_arguments->IsNumberDictionary() 4046 ? Handle<NumberDictionary>::cast(old_arguments) 4047 : JSObject::NormalizeElements(object); 4048 PropertyDetails details(kData, attributes, PropertyCellType::kNoCell); 4049 Handle<NumberDictionary> new_dictionary = 4050 NumberDictionary::Add(isolate, dictionary, index, value, details); 4051 if (attributes != NONE) object->RequireSlowElements(*new_dictionary); 4052 if (*dictionary != *new_dictionary) { 4053 elements->set_arguments(*new_dictionary); 4054 } 4055 } 4056 4057 static void ReconfigureImpl(Handle<JSObject> object, 4058 Handle<FixedArrayBase> store, uint32_t entry, 4059 Handle<Object> value, 4060 PropertyAttributes attributes) { 4061 Isolate* isolate = object->GetIsolate(); 4062 Handle<SloppyArgumentsElements> elements = 4063 Handle<SloppyArgumentsElements>::cast(store); 4064 uint32_t length = elements->parameter_map_length(); 4065 if (entry < length) { 4066 Object* probe = elements->get_mapped_entry(entry); 4067 DCHECK(!probe->IsTheHole(isolate)); 4068 Context* context = elements->context(); 4069 int context_entry = Smi::ToInt(probe); 4070 DCHECK(!context->get(context_entry)->IsTheHole(isolate)); 4071 context->set(context_entry, *value); 4072 4073 // Redefining attributes of an aliased element destroys fast aliasing. 4074 elements->set_mapped_entry(entry, 4075 ReadOnlyRoots(isolate).the_hole_value()); 4076 // For elements that are still writable we re-establish slow aliasing. 4077 if ((attributes & READ_ONLY) == 0) { 4078 value = isolate->factory()->NewAliasedArgumentsEntry(context_entry); 4079 } 4080 4081 PropertyDetails details(kData, attributes, PropertyCellType::kNoCell); 4082 Handle<NumberDictionary> arguments( 4083 NumberDictionary::cast(elements->arguments()), isolate); 4084 arguments = 4085 NumberDictionary::Add(isolate, arguments, entry, value, details); 4086 // If the attributes were NONE, we would have called set rather than 4087 // reconfigure. 4088 DCHECK_NE(NONE, attributes); 4089 object->RequireSlowElements(*arguments); 4090 elements->set_arguments(*arguments); 4091 } else { 4092 Handle<FixedArrayBase> arguments(elements->arguments(), isolate); 4093 DictionaryElementsAccessor::ReconfigureImpl( 4094 object, arguments, entry - length, value, attributes); 4095 } 4096 } 4097 }; 4098 4099 4100 class FastSloppyArgumentsElementsAccessor 4101 : public SloppyArgumentsElementsAccessor< 4102 FastSloppyArgumentsElementsAccessor, FastHoleyObjectElementsAccessor, 4103 ElementsKindTraits<FAST_SLOPPY_ARGUMENTS_ELEMENTS> > { 4104 public: 4105 explicit FastSloppyArgumentsElementsAccessor(const char* name) 4106 : SloppyArgumentsElementsAccessor< 4107 FastSloppyArgumentsElementsAccessor, 4108 FastHoleyObjectElementsAccessor, 4109 ElementsKindTraits<FAST_SLOPPY_ARGUMENTS_ELEMENTS> >(name) {} 4110 4111 static Handle<Object> ConvertArgumentsStoreResult( 4112 Isolate* isolate, Handle<SloppyArgumentsElements> paramtere_map, 4113 Handle<Object> result) { 4114 DCHECK(!result->IsAliasedArgumentsEntry()); 4115 return result; 4116 } 4117 4118 static Handle<FixedArray> GetArguments(Isolate* isolate, 4119 FixedArrayBase* store) { 4120 SloppyArgumentsElements* elements = SloppyArgumentsElements::cast(store); 4121 return Handle<FixedArray>(elements->arguments(), isolate); 4122 } 4123 4124 static Handle<NumberDictionary> NormalizeImpl( 4125 Handle<JSObject> object, Handle<FixedArrayBase> elements) { 4126 Handle<FixedArray> arguments = 4127 GetArguments(object->GetIsolate(), *elements); 4128 return FastHoleyObjectElementsAccessor::NormalizeImpl(object, arguments); 4129 } 4130 4131 static Handle<NumberDictionary> NormalizeArgumentsElements( 4132 Handle<JSObject> object, Handle<SloppyArgumentsElements> elements, 4133 uint32_t* entry) { 4134 Handle<NumberDictionary> dictionary = JSObject::NormalizeElements(object); 4135 elements->set_arguments(*dictionary); 4136 // kMaxUInt32 indicates that a context mapped element got deleted. In this 4137 // case we only normalize the elements (aka. migrate to SLOW_SLOPPY). 4138 if (*entry == kMaxUInt32) return dictionary; 4139 uint32_t length = elements->parameter_map_length(); 4140 if (*entry >= length) { 4141 *entry = 4142 dictionary->FindEntry(object->GetIsolate(), *entry - length) + length; 4143 } 4144 return dictionary; 4145 } 4146 4147 static void SloppyDeleteImpl(Handle<JSObject> obj, 4148 Handle<SloppyArgumentsElements> elements, 4149 uint32_t entry) { 4150 // Always normalize element on deleting an entry. 4151 NormalizeArgumentsElements(obj, elements, &entry); 4152 SlowSloppyArgumentsElementsAccessor::SloppyDeleteImpl(obj, elements, entry); 4153 } 4154 4155 static void AddImpl(Handle<JSObject> object, uint32_t index, 4156 Handle<Object> value, PropertyAttributes attributes, 4157 uint32_t new_capacity) { 4158 DCHECK_EQ(NONE, attributes); 4159 Isolate* isolate = object->GetIsolate(); 4160 Handle<SloppyArgumentsElements> elements( 4161 SloppyArgumentsElements::cast(object->elements()), isolate); 4162 Handle<FixedArray> old_arguments(elements->arguments(), isolate); 4163 if (old_arguments->IsNumberDictionary() || 4164 static_cast<uint32_t>(old_arguments->length()) < new_capacity) { 4165 GrowCapacityAndConvertImpl(object, new_capacity); 4166 } 4167 FixedArray* arguments = elements->arguments(); 4168 // For fast holey objects, the entry equals the index. The code above made 4169 // sure that there's enough space to store the value. We cannot convert 4170 // index to entry explicitly since the slot still contains the hole, so the 4171 // current EntryForIndex would indicate that it is "absent" by returning 4172 // kMaxUInt32. 4173 FastHoleyObjectElementsAccessor::SetImpl(arguments, index, *value); 4174 } 4175 4176 static void ReconfigureImpl(Handle<JSObject> object, 4177 Handle<FixedArrayBase> store, uint32_t entry, 4178 Handle<Object> value, 4179 PropertyAttributes attributes) { 4180 DCHECK_EQ(object->elements(), *store); 4181 Handle<SloppyArgumentsElements> elements( 4182 SloppyArgumentsElements::cast(*store), object->GetIsolate()); 4183 NormalizeArgumentsElements(object, elements, &entry); 4184 SlowSloppyArgumentsElementsAccessor::ReconfigureImpl(object, store, entry, 4185 value, attributes); 4186 } 4187 4188 static void CopyElementsImpl(Isolate* isolate, FixedArrayBase* from, 4189 uint32_t from_start, FixedArrayBase* to, 4190 ElementsKind from_kind, uint32_t to_start, 4191 int packed_size, int copy_size) { 4192 DCHECK(!to->IsDictionary()); 4193 if (from_kind == SLOW_SLOPPY_ARGUMENTS_ELEMENTS) { 4194 CopyDictionaryToObjectElements(isolate, from, from_start, to, 4195 HOLEY_ELEMENTS, to_start, copy_size); 4196 } else { 4197 DCHECK_EQ(FAST_SLOPPY_ARGUMENTS_ELEMENTS, from_kind); 4198 CopyObjectToObjectElements(isolate, from, HOLEY_ELEMENTS, from_start, to, 4199 HOLEY_ELEMENTS, to_start, copy_size); 4200 } 4201 } 4202 4203 static void GrowCapacityAndConvertImpl(Handle<JSObject> object, 4204 uint32_t capacity) { 4205 Isolate* isolate = object->GetIsolate(); 4206 Handle<SloppyArgumentsElements> elements( 4207 SloppyArgumentsElements::cast(object->elements()), isolate); 4208 Handle<FixedArray> old_arguments(FixedArray::cast(elements->arguments()), 4209 isolate); 4210 ElementsKind from_kind = object->GetElementsKind(); 4211 // This method should only be called if there's a reason to update the 4212 // elements. 4213 DCHECK(from_kind == SLOW_SLOPPY_ARGUMENTS_ELEMENTS || 4214 static_cast<uint32_t>(old_arguments->length()) < capacity); 4215 Handle<FixedArrayBase> arguments = 4216 ConvertElementsWithCapacity(object, old_arguments, from_kind, capacity); 4217 Handle<Map> new_map = JSObject::GetElementsTransitionMap( 4218 object, FAST_SLOPPY_ARGUMENTS_ELEMENTS); 4219 JSObject::MigrateToMap(object, new_map); 4220 elements->set_arguments(FixedArray::cast(*arguments)); 4221 JSObject::ValidateElements(*object); 4222 } 4223 }; 4224 4225 template <typename Subclass, typename BackingStoreAccessor, typename KindTraits> 4226 class StringWrapperElementsAccessor 4227 : public ElementsAccessorBase<Subclass, KindTraits> { 4228 public: 4229 explicit StringWrapperElementsAccessor(const char* name) 4230 : ElementsAccessorBase<Subclass, KindTraits>(name) { 4231 USE(KindTraits::Kind); 4232 } 4233 4234 static Handle<Object> GetInternalImpl(Handle<JSObject> holder, 4235 uint32_t entry) { 4236 return GetImpl(holder, entry); 4237 } 4238 4239 static Handle<Object> GetImpl(Handle<JSObject> holder, uint32_t entry) { 4240 Isolate* isolate = holder->GetIsolate(); 4241 Handle<String> string(GetString(*holder), isolate); 4242 uint32_t length = static_cast<uint32_t>(string->length()); 4243 if (entry < length) { 4244 return isolate->factory()->LookupSingleCharacterStringFromCode( 4245 String::Flatten(isolate, string)->Get(entry)); 4246 } 4247 return BackingStoreAccessor::GetImpl(isolate, holder->elements(), 4248 entry - length); 4249 } 4250 4251 static Handle<Object> GetImpl(Isolate* isolate, FixedArrayBase* elements, 4252 uint32_t entry) { 4253 UNREACHABLE(); 4254 } 4255 4256 static PropertyDetails GetDetailsImpl(JSObject* holder, uint32_t entry) { 4257 uint32_t length = static_cast<uint32_t>(GetString(holder)->length()); 4258 if (entry < length) { 4259 PropertyAttributes attributes = 4260 static_cast<PropertyAttributes>(READ_ONLY | DONT_DELETE); 4261 return PropertyDetails(kData, attributes, PropertyCellType::kNoCell); 4262 } 4263 return BackingStoreAccessor::GetDetailsImpl(holder, entry - length); 4264 } 4265 4266 static uint32_t GetEntryForIndexImpl(Isolate* isolate, JSObject* holder, 4267 FixedArrayBase* backing_store, 4268 uint32_t index, PropertyFilter filter) { 4269 uint32_t length = static_cast<uint32_t>(GetString(holder)->length()); 4270 if (index < length) return index; 4271 uint32_t backing_store_entry = BackingStoreAccessor::GetEntryForIndexImpl( 4272 isolate, holder, backing_store, index, filter); 4273 if (backing_store_entry == kMaxUInt32) return kMaxUInt32; 4274 DCHECK(backing_store_entry < kMaxUInt32 - length); 4275 return backing_store_entry + length; 4276 } 4277 4278 static void DeleteImpl(Handle<JSObject> holder, uint32_t entry) { 4279 uint32_t length = static_cast<uint32_t>(GetString(*holder)->length()); 4280 if (entry < length) { 4281 return; // String contents can't be deleted. 4282 } 4283 BackingStoreAccessor::DeleteImpl(holder, entry - length); 4284 } 4285 4286 static void SetImpl(Handle<JSObject> holder, uint32_t entry, Object* value) { 4287 uint32_t length = static_cast<uint32_t>(GetString(*holder)->length()); 4288 if (entry < length) { 4289 return; // String contents are read-only. 4290 } 4291 BackingStoreAccessor::SetImpl(holder->elements(), entry - length, value); 4292 } 4293 4294 static void AddImpl(Handle<JSObject> object, uint32_t index, 4295 Handle<Object> value, PropertyAttributes attributes, 4296 uint32_t new_capacity) { 4297 DCHECK(index >= static_cast<uint32_t>(GetString(*object)->length())); 4298 // Explicitly grow fast backing stores if needed. Dictionaries know how to 4299 // extend their capacity themselves. 4300 if (KindTraits::Kind == FAST_STRING_WRAPPER_ELEMENTS && 4301 (object->GetElementsKind() == SLOW_STRING_WRAPPER_ELEMENTS || 4302 BackingStoreAccessor::GetCapacityImpl(*object, object->elements()) != 4303 new_capacity)) { 4304 GrowCapacityAndConvertImpl(object, new_capacity); 4305 } 4306 BackingStoreAccessor::AddImpl(object, index, value, attributes, 4307 new_capacity); 4308 } 4309 4310 static void ReconfigureImpl(Handle<JSObject> object, 4311 Handle<FixedArrayBase> store, uint32_t entry, 4312 Handle<Object> value, 4313 PropertyAttributes attributes) { 4314 uint32_t length = static_cast<uint32_t>(GetString(*object)->length()); 4315 if (entry < length) { 4316 return; // String contents can't be reconfigured. 4317 } 4318 BackingStoreAccessor::ReconfigureImpl(object, store, entry - length, value, 4319 attributes); 4320 } 4321 4322 static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver, 4323 KeyAccumulator* accumulator, 4324 AddKeyConversion convert) { 4325 Isolate* isolate = receiver->GetIsolate(); 4326 Handle<String> string(GetString(*receiver), isolate); 4327 string = String::Flatten(isolate, string); 4328 uint32_t length = static_cast<uint32_t>(string->length()); 4329 for (uint32_t i = 0; i < length; i++) { 4330 accumulator->AddKey( 4331 isolate->factory()->LookupSingleCharacterStringFromCode( 4332 string->Get(i)), 4333 convert); 4334 } 4335 BackingStoreAccessor::AddElementsToKeyAccumulatorImpl(receiver, accumulator, 4336 convert); 4337 } 4338 4339 static void CollectElementIndicesImpl(Handle<JSObject> object, 4340 Handle<FixedArrayBase> backing_store, 4341 KeyAccumulator* keys) { 4342 uint32_t length = GetString(*object)->length(); 4343 Factory* factory = keys->isolate()->factory(); 4344 for (uint32_t i = 0; i < length; i++) { 4345 keys->AddKey(factory->NewNumberFromUint(i)); 4346 } 4347 BackingStoreAccessor::CollectElementIndicesImpl(object, backing_store, 4348 keys); 4349 } 4350 4351 static void GrowCapacityAndConvertImpl(Handle<JSObject> object, 4352 uint32_t capacity) { 4353 Handle<FixedArrayBase> old_elements(object->elements(), 4354 object->GetIsolate()); 4355 ElementsKind from_kind = object->GetElementsKind(); 4356 if (from_kind == FAST_STRING_WRAPPER_ELEMENTS) { 4357 // The optimizing compiler relies on the prototype lookups of String 4358 // objects always returning undefined. If there's a store to the 4359 // initial String.prototype object, make sure all the optimizations 4360 // are invalidated. 4361 object->GetIsolate()->UpdateNoElementsProtectorOnSetLength(object); 4362 } 4363 // This method should only be called if there's a reason to update the 4364 // elements. 4365 DCHECK(from_kind == SLOW_STRING_WRAPPER_ELEMENTS || 4366 static_cast<uint32_t>(old_elements->length()) < capacity); 4367 Subclass::BasicGrowCapacityAndConvertImpl(object, old_elements, from_kind, 4368 FAST_STRING_WRAPPER_ELEMENTS, 4369 capacity); 4370 } 4371 4372 static void CopyElementsImpl(Isolate* isolate, FixedArrayBase* from, 4373 uint32_t from_start, FixedArrayBase* to, 4374 ElementsKind from_kind, uint32_t to_start, 4375 int packed_size, int copy_size) { 4376 DCHECK(!to->IsDictionary()); 4377 if (from_kind == SLOW_STRING_WRAPPER_ELEMENTS) { 4378 CopyDictionaryToObjectElements(isolate, from, from_start, to, 4379 HOLEY_ELEMENTS, to_start, copy_size); 4380 } else { 4381 DCHECK_EQ(FAST_STRING_WRAPPER_ELEMENTS, from_kind); 4382 CopyObjectToObjectElements(isolate, from, HOLEY_ELEMENTS, from_start, to, 4383 HOLEY_ELEMENTS, to_start, copy_size); 4384 } 4385 } 4386 4387 static uint32_t NumberOfElementsImpl(JSObject* object, 4388 FixedArrayBase* backing_store) { 4389 uint32_t length = GetString(object)->length(); 4390 return length + 4391 BackingStoreAccessor::NumberOfElementsImpl(object, backing_store); 4392 } 4393 4394 private: 4395 static String* GetString(JSObject* holder) { 4396 DCHECK(holder->IsJSValue()); 4397 JSValue* js_value = JSValue::cast(holder); 4398 DCHECK(js_value->value()->IsString()); 4399 return String::cast(js_value->value()); 4400 } 4401 }; 4402 4403 class FastStringWrapperElementsAccessor 4404 : public StringWrapperElementsAccessor< 4405 FastStringWrapperElementsAccessor, FastHoleyObjectElementsAccessor, 4406 ElementsKindTraits<FAST_STRING_WRAPPER_ELEMENTS>> { 4407 public: 4408 explicit FastStringWrapperElementsAccessor(const char* name) 4409 : StringWrapperElementsAccessor< 4410 FastStringWrapperElementsAccessor, FastHoleyObjectElementsAccessor, 4411 ElementsKindTraits<FAST_STRING_WRAPPER_ELEMENTS>>(name) {} 4412 4413 static Handle<NumberDictionary> NormalizeImpl( 4414 Handle<JSObject> object, Handle<FixedArrayBase> elements) { 4415 return FastHoleyObjectElementsAccessor::NormalizeImpl(object, elements); 4416 } 4417 }; 4418 4419 class SlowStringWrapperElementsAccessor 4420 : public StringWrapperElementsAccessor< 4421 SlowStringWrapperElementsAccessor, DictionaryElementsAccessor, 4422 ElementsKindTraits<SLOW_STRING_WRAPPER_ELEMENTS>> { 4423 public: 4424 explicit SlowStringWrapperElementsAccessor(const char* name) 4425 : StringWrapperElementsAccessor< 4426 SlowStringWrapperElementsAccessor, DictionaryElementsAccessor, 4427 ElementsKindTraits<SLOW_STRING_WRAPPER_ELEMENTS>>(name) {} 4428 4429 static bool HasAccessorsImpl(JSObject* holder, 4430 FixedArrayBase* backing_store) { 4431 return DictionaryElementsAccessor::HasAccessorsImpl(holder, backing_store); 4432 } 4433 }; 4434 4435 } // namespace 4436 4437 4438 void CheckArrayAbuse(Handle<JSObject> obj, const char* op, uint32_t index, 4439 bool allow_appending) { 4440 DisallowHeapAllocation no_allocation; 4441 Object* raw_length = nullptr; 4442 const char* elements_type = "array"; 4443 if (obj->IsJSArray()) { 4444 JSArray* array = JSArray::cast(*obj); 4445 raw_length = array->length(); 4446 } else { 4447 raw_length = Smi::FromInt(obj->elements()->length()); 4448 elements_type = "object"; 4449 } 4450 4451 if (raw_length->IsNumber()) { 4452 double n = raw_length->Number(); 4453 if (FastI2D(FastD2UI(n)) == n) { 4454 int32_t int32_length = DoubleToInt32(n); 4455 uint32_t compare_length = static_cast<uint32_t>(int32_length); 4456 if (allow_appending) compare_length++; 4457 if (index >= compare_length) { 4458 PrintF("[OOB %s %s (%s length = %d, element accessed = %d) in ", 4459 elements_type, op, elements_type, static_cast<int>(int32_length), 4460 static_cast<int>(index)); 4461 TraceTopFrame(obj->GetIsolate()); 4462 PrintF("]\n"); 4463 } 4464 } else { 4465 PrintF("[%s elements length not integer value in ", elements_type); 4466 TraceTopFrame(obj->GetIsolate()); 4467 PrintF("]\n"); 4468 } 4469 } else { 4470 PrintF("[%s elements length not a number in ", elements_type); 4471 TraceTopFrame(obj->GetIsolate()); 4472 PrintF("]\n"); 4473 } 4474 } 4475 4476 4477 MaybeHandle<Object> ArrayConstructInitializeElements(Handle<JSArray> array, 4478 Arguments* args) { 4479 if (args->length() == 0) { 4480 // Optimize the case where there are no parameters passed. 4481 JSArray::Initialize(array, JSArray::kPreallocatedArrayElements); 4482 return array; 4483 4484 } else if (args->length() == 1 && args->at(0)->IsNumber()) { 4485 uint32_t length; 4486 if (!args->at(0)->ToArrayLength(&length)) { 4487 return ThrowArrayLengthRangeError(array->GetIsolate()); 4488 } 4489 4490 // Optimize the case where there is one argument and the argument is a small 4491 // smi. 4492 if (length > 0 && length < JSArray::kInitialMaxFastElementArray) { 4493 ElementsKind elements_kind = array->GetElementsKind(); 4494 JSArray::Initialize(array, length, length); 4495 4496 if (!IsHoleyElementsKind(elements_kind)) { 4497 elements_kind = GetHoleyElementsKind(elements_kind); 4498 JSObject::TransitionElementsKind(array, elements_kind); 4499 } 4500 } else if (length == 0) { 4501 JSArray::Initialize(array, JSArray::kPreallocatedArrayElements); 4502 } else { 4503 // Take the argument as the length. 4504 JSArray::Initialize(array, 0); 4505 JSArray::SetLength(array, length); 4506 } 4507 return array; 4508 } 4509 4510 Factory* factory = array->GetIsolate()->factory(); 4511 4512 // Set length and elements on the array. 4513 int number_of_elements = args->length(); 4514 JSObject::EnsureCanContainElements( 4515 array, args, 0, number_of_elements, ALLOW_CONVERTED_DOUBLE_ELEMENTS); 4516 4517 // Allocate an appropriately typed elements array. 4518 ElementsKind elements_kind = array->GetElementsKind(); 4519 Handle<FixedArrayBase> elms; 4520 if (IsDoubleElementsKind(elements_kind)) { 4521 elms = Handle<FixedArrayBase>::cast( 4522 factory->NewFixedDoubleArray(number_of_elements)); 4523 } else { 4524 elms = Handle<FixedArrayBase>::cast( 4525 factory->NewFixedArrayWithHoles(number_of_elements)); 4526 } 4527 4528 // Fill in the content 4529 switch (elements_kind) { 4530 case HOLEY_SMI_ELEMENTS: 4531 case PACKED_SMI_ELEMENTS: { 4532 Handle<FixedArray> smi_elms = Handle<FixedArray>::cast(elms); 4533 for (int entry = 0; entry < number_of_elements; entry++) { 4534 smi_elms->set(entry, (*args)[entry], SKIP_WRITE_BARRIER); 4535 } 4536 break; 4537 } 4538 case HOLEY_ELEMENTS: 4539 case PACKED_ELEMENTS: { 4540 DisallowHeapAllocation no_gc; 4541 WriteBarrierMode mode = elms->GetWriteBarrierMode(no_gc); 4542 Handle<FixedArray> object_elms = Handle<FixedArray>::cast(elms); 4543 for (int entry = 0; entry < number_of_elements; entry++) { 4544 object_elms->set(entry, (*args)[entry], mode); 4545 } 4546 break; 4547 } 4548 case HOLEY_DOUBLE_ELEMENTS: 4549 case PACKED_DOUBLE_ELEMENTS: { 4550 Handle<FixedDoubleArray> double_elms = 4551 Handle<FixedDoubleArray>::cast(elms); 4552 for (int entry = 0; entry < number_of_elements; entry++) { 4553 double_elms->set(entry, (*args)[entry]->Number()); 4554 } 4555 break; 4556 } 4557 default: 4558 UNREACHABLE(); 4559 break; 4560 } 4561 4562 array->set_elements(*elms); 4563 array->set_length(Smi::FromInt(number_of_elements)); 4564 return array; 4565 } 4566 4567 void CopyFastNumberJSArrayElementsToTypedArray(Context* context, 4568 JSArray* source, 4569 JSTypedArray* destination, 4570 uintptr_t length, 4571 uintptr_t offset) { 4572 DCHECK(context->IsContext()); 4573 DCHECK(source->IsJSArray()); 4574 DCHECK(destination->IsJSTypedArray()); 4575 4576 switch (destination->GetElementsKind()) { 4577 #define TYPED_ARRAYS_CASE(Type, type, TYPE, ctype) \ 4578 case TYPE##_ELEMENTS: \ 4579 CHECK(Fixed##Type##ElementsAccessor::TryCopyElementsFastNumber( \ 4580 context, source, destination, length, static_cast<uint32_t>(offset))); \ 4581 break; 4582 TYPED_ARRAYS(TYPED_ARRAYS_CASE) 4583 #undef TYPED_ARRAYS_CASE 4584 default: 4585 UNREACHABLE(); 4586 } 4587 } 4588 4589 void CopyTypedArrayElementsToTypedArray(JSTypedArray* source, 4590 JSTypedArray* destination, 4591 uintptr_t length, uintptr_t offset) { 4592 switch (destination->GetElementsKind()) { 4593 #define TYPED_ARRAYS_CASE(Type, type, TYPE, ctype) \ 4594 case TYPE##_ELEMENTS: \ 4595 Fixed##Type##ElementsAccessor::CopyElementsFromTypedArray( \ 4596 source, destination, length, static_cast<uint32_t>(offset)); \ 4597 break; 4598 TYPED_ARRAYS(TYPED_ARRAYS_CASE) 4599 #undef TYPED_ARRAYS_CASE 4600 default: 4601 UNREACHABLE(); 4602 } 4603 } 4604 4605 void CopyTypedArrayElementsSlice(JSTypedArray* source, 4606 JSTypedArray* destination, uintptr_t start, 4607 uintptr_t end) { 4608 destination->GetElementsAccessor()->CopyTypedArrayElementsSlice( 4609 source, destination, start, end); 4610 } 4611 4612 void ElementsAccessor::InitializeOncePerProcess() { 4613 static ElementsAccessor* accessor_array[] = { 4614 #define ACCESSOR_ARRAY(Class, Kind, Store) new Class(#Kind), 4615 ELEMENTS_LIST(ACCESSOR_ARRAY) 4616 #undef ACCESSOR_ARRAY 4617 }; 4618 4619 STATIC_ASSERT((sizeof(accessor_array) / sizeof(*accessor_array)) == 4620 kElementsKindCount); 4621 4622 elements_accessors_ = accessor_array; 4623 } 4624 4625 4626 void ElementsAccessor::TearDown() { 4627 if (elements_accessors_ == nullptr) return; 4628 #define ACCESSOR_DELETE(Class, Kind, Store) delete elements_accessors_[Kind]; 4629 ELEMENTS_LIST(ACCESSOR_DELETE) 4630 #undef ACCESSOR_DELETE 4631 elements_accessors_ = nullptr; 4632 } 4633 4634 Handle<JSArray> ElementsAccessor::Concat(Isolate* isolate, Arguments* args, 4635 uint32_t concat_size, 4636 uint32_t result_len) { 4637 ElementsKind result_elements_kind = GetInitialFastElementsKind(); 4638 bool has_raw_doubles = false; 4639 { 4640 DisallowHeapAllocation no_gc; 4641 bool is_holey = false; 4642 for (uint32_t i = 0; i < concat_size; i++) { 4643 Object* arg = (*args)[i]; 4644 ElementsKind arg_kind = JSArray::cast(arg)->GetElementsKind(); 4645 has_raw_doubles = has_raw_doubles || IsDoubleElementsKind(arg_kind); 4646 is_holey = is_holey || IsHoleyElementsKind(arg_kind); 4647 result_elements_kind = 4648 GetMoreGeneralElementsKind(result_elements_kind, arg_kind); 4649 } 4650 if (is_holey) { 4651 result_elements_kind = GetHoleyElementsKind(result_elements_kind); 4652 } 4653 } 4654 4655 // If a double array is concatted into a fast elements array, the fast 4656 // elements array needs to be initialized to contain proper holes, since 4657 // boxing doubles may cause incremental marking. 4658 bool requires_double_boxing = 4659 has_raw_doubles && !IsDoubleElementsKind(result_elements_kind); 4660 ArrayStorageAllocationMode mode = requires_double_boxing 4661 ? INITIALIZE_ARRAY_ELEMENTS_WITH_HOLE 4662 : DONT_INITIALIZE_ARRAY_ELEMENTS; 4663 Handle<JSArray> result_array = isolate->factory()->NewJSArray( 4664 result_elements_kind, result_len, result_len, mode); 4665 if (result_len == 0) return result_array; 4666 4667 uint32_t insertion_index = 0; 4668 Handle<FixedArrayBase> storage(result_array->elements(), isolate); 4669 ElementsAccessor* accessor = ElementsAccessor::ForKind(result_elements_kind); 4670 for (uint32_t i = 0; i < concat_size; i++) { 4671 // It is crucial to keep |array| in a raw pointer form to avoid 4672 // performance degradation. 4673 JSArray* array = JSArray::cast((*args)[i]); 4674 uint32_t len = 0; 4675 array->length()->ToArrayLength(&len); 4676 if (len == 0) continue; 4677 ElementsKind from_kind = array->GetElementsKind(); 4678 accessor->CopyElements(array, 0, from_kind, storage, insertion_index, len); 4679 insertion_index += len; 4680 } 4681 4682 DCHECK_EQ(insertion_index, result_len); 4683 return result_array; 4684 } 4685 4686 ElementsAccessor** ElementsAccessor::elements_accessors_ = nullptr; 4687 4688 #undef ELEMENTS_LIST 4689 } // namespace internal 4690 } // namespace v8 4691