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/factory.h" 10 #include "src/isolate-inl.h" 11 #include "src/messages.h" 12 #include "src/objects-inl.h" 13 #include "src/utils.h" 14 15 // Each concrete ElementsAccessor can handle exactly one ElementsKind, 16 // several abstract ElementsAccessor classes are used to allow sharing 17 // common code. 18 // 19 // Inheritance hierarchy: 20 // - ElementsAccessorBase (abstract) 21 // - FastElementsAccessor (abstract) 22 // - FastSmiOrObjectElementsAccessor 23 // - FastPackedSmiElementsAccessor 24 // - FastHoleySmiElementsAccessor 25 // - FastPackedObjectElementsAccessor 26 // - FastHoleyObjectElementsAccessor 27 // - FastDoubleElementsAccessor 28 // - FastPackedDoubleElementsAccessor 29 // - FastHoleyDoubleElementsAccessor 30 // - TypedElementsAccessor: template, with instantiations: 31 // - FixedUint8ElementsAccessor 32 // - FixedInt8ElementsAccessor 33 // - FixedUint16ElementsAccessor 34 // - FixedInt16ElementsAccessor 35 // - FixedUint32ElementsAccessor 36 // - FixedInt32ElementsAccessor 37 // - FixedFloat32ElementsAccessor 38 // - FixedFloat64ElementsAccessor 39 // - FixedUint8ClampedElementsAccessor 40 // - DictionaryElementsAccessor 41 // - SloppyArgumentsElementsAccessor 42 // - FastSloppyArgumentsElementsAccessor 43 // - SlowSloppyArgumentsElementsAccessor 44 // - StringWrapperElementsAccessor 45 // - FastStringWrapperElementsAccessor 46 // - SlowStringWrapperElementsAccessor 47 48 namespace v8 { 49 namespace internal { 50 51 52 namespace { 53 54 55 static const int kPackedSizeNotKnown = -1; 56 57 enum Where { AT_START, AT_END }; 58 59 60 // First argument in list is the accessor class, the second argument is the 61 // accessor ElementsKind, and the third is the backing store class. Use the 62 // fast element handler for smi-only arrays. The implementation is currently 63 // identical. Note that the order must match that of the ElementsKind enum for 64 // the |accessor_array[]| below to work. 65 #define ELEMENTS_LIST(V) \ 66 V(FastPackedSmiElementsAccessor, FAST_SMI_ELEMENTS, FixedArray) \ 67 V(FastHoleySmiElementsAccessor, FAST_HOLEY_SMI_ELEMENTS, FixedArray) \ 68 V(FastPackedObjectElementsAccessor, FAST_ELEMENTS, FixedArray) \ 69 V(FastHoleyObjectElementsAccessor, FAST_HOLEY_ELEMENTS, FixedArray) \ 70 V(FastPackedDoubleElementsAccessor, FAST_DOUBLE_ELEMENTS, FixedDoubleArray) \ 71 V(FastHoleyDoubleElementsAccessor, FAST_HOLEY_DOUBLE_ELEMENTS, \ 72 FixedDoubleArray) \ 73 V(DictionaryElementsAccessor, DICTIONARY_ELEMENTS, SeededNumberDictionary) \ 74 V(FastSloppyArgumentsElementsAccessor, FAST_SLOPPY_ARGUMENTS_ELEMENTS, \ 75 FixedArray) \ 76 V(SlowSloppyArgumentsElementsAccessor, SLOW_SLOPPY_ARGUMENTS_ELEMENTS, \ 77 FixedArray) \ 78 V(FastStringWrapperElementsAccessor, FAST_STRING_WRAPPER_ELEMENTS, \ 79 FixedArray) \ 80 V(SlowStringWrapperElementsAccessor, SLOW_STRING_WRAPPER_ELEMENTS, \ 81 FixedArray) \ 82 V(FixedUint8ElementsAccessor, UINT8_ELEMENTS, FixedUint8Array) \ 83 V(FixedInt8ElementsAccessor, INT8_ELEMENTS, FixedInt8Array) \ 84 V(FixedUint16ElementsAccessor, UINT16_ELEMENTS, FixedUint16Array) \ 85 V(FixedInt16ElementsAccessor, INT16_ELEMENTS, FixedInt16Array) \ 86 V(FixedUint32ElementsAccessor, UINT32_ELEMENTS, FixedUint32Array) \ 87 V(FixedInt32ElementsAccessor, INT32_ELEMENTS, FixedInt32Array) \ 88 V(FixedFloat32ElementsAccessor, FLOAT32_ELEMENTS, FixedFloat32Array) \ 89 V(FixedFloat64ElementsAccessor, FLOAT64_ELEMENTS, FixedFloat64Array) \ 90 V(FixedUint8ClampedElementsAccessor, UINT8_CLAMPED_ELEMENTS, \ 91 FixedUint8ClampedArray) 92 93 template<ElementsKind Kind> class ElementsKindTraits { 94 public: 95 typedef FixedArrayBase BackingStore; 96 }; 97 98 #define ELEMENTS_TRAITS(Class, KindParam, Store) \ 99 template<> class ElementsKindTraits<KindParam> { \ 100 public: /* NOLINT */ \ 101 static const ElementsKind Kind = KindParam; \ 102 typedef Store BackingStore; \ 103 }; 104 ELEMENTS_LIST(ELEMENTS_TRAITS) 105 #undef ELEMENTS_TRAITS 106 107 108 MUST_USE_RESULT 109 MaybeHandle<Object> ThrowArrayLengthRangeError(Isolate* isolate) { 110 THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kInvalidArrayLength), 111 Object); 112 } 113 114 115 void CopyObjectToObjectElements(FixedArrayBase* from_base, 116 ElementsKind from_kind, uint32_t from_start, 117 FixedArrayBase* to_base, ElementsKind to_kind, 118 uint32_t to_start, int raw_copy_size) { 119 DCHECK(to_base->map() != 120 from_base->GetIsolate()->heap()->fixed_cow_array_map()); 121 DisallowHeapAllocation no_allocation; 122 int copy_size = raw_copy_size; 123 if (raw_copy_size < 0) { 124 DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd || 125 raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 126 copy_size = Min(from_base->length() - from_start, 127 to_base->length() - to_start); 128 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 129 int start = to_start + copy_size; 130 int length = to_base->length() - start; 131 if (length > 0) { 132 Heap* heap = from_base->GetHeap(); 133 MemsetPointer(FixedArray::cast(to_base)->data_start() + start, 134 heap->the_hole_value(), length); 135 } 136 } 137 } 138 DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() && 139 (copy_size + static_cast<int>(from_start)) <= from_base->length()); 140 if (copy_size == 0) return; 141 FixedArray* from = FixedArray::cast(from_base); 142 FixedArray* to = FixedArray::cast(to_base); 143 DCHECK(IsFastSmiOrObjectElementsKind(from_kind)); 144 DCHECK(IsFastSmiOrObjectElementsKind(to_kind)); 145 146 WriteBarrierMode write_barrier_mode = 147 (IsFastObjectElementsKind(from_kind) && IsFastObjectElementsKind(to_kind)) 148 ? UPDATE_WRITE_BARRIER 149 : SKIP_WRITE_BARRIER; 150 for (int i = 0; i < copy_size; i++) { 151 Object* value = from->get(from_start + i); 152 to->set(to_start + i, value, write_barrier_mode); 153 } 154 } 155 156 157 static void CopyDictionaryToObjectElements( 158 FixedArrayBase* from_base, uint32_t from_start, FixedArrayBase* to_base, 159 ElementsKind to_kind, uint32_t to_start, int raw_copy_size) { 160 DisallowHeapAllocation no_allocation; 161 SeededNumberDictionary* from = SeededNumberDictionary::cast(from_base); 162 int copy_size = raw_copy_size; 163 if (raw_copy_size < 0) { 164 DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd || 165 raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 166 copy_size = from->max_number_key() + 1 - from_start; 167 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 168 int start = to_start + copy_size; 169 int length = to_base->length() - start; 170 if (length > 0) { 171 Heap* heap = from->GetHeap(); 172 MemsetPointer(FixedArray::cast(to_base)->data_start() + start, 173 heap->the_hole_value(), length); 174 } 175 } 176 } 177 DCHECK(to_base != from_base); 178 DCHECK(IsFastSmiOrObjectElementsKind(to_kind)); 179 if (copy_size == 0) return; 180 FixedArray* to = FixedArray::cast(to_base); 181 uint32_t to_length = to->length(); 182 if (to_start + copy_size > to_length) { 183 copy_size = to_length - to_start; 184 } 185 WriteBarrierMode write_barrier_mode = IsFastObjectElementsKind(to_kind) 186 ? UPDATE_WRITE_BARRIER 187 : SKIP_WRITE_BARRIER; 188 for (int i = 0; i < copy_size; i++) { 189 int entry = from->FindEntry(i + from_start); 190 if (entry != SeededNumberDictionary::kNotFound) { 191 Object* value = from->ValueAt(entry); 192 DCHECK(!value->IsTheHole(from->GetIsolate())); 193 to->set(i + to_start, value, write_barrier_mode); 194 } else { 195 to->set_the_hole(i + to_start); 196 } 197 } 198 } 199 200 201 // NOTE: this method violates the handlified function signature convention: 202 // raw pointer parameters in the function that allocates. 203 // See ElementsAccessorBase::CopyElements() for details. 204 static void CopyDoubleToObjectElements(FixedArrayBase* from_base, 205 uint32_t from_start, 206 FixedArrayBase* to_base, 207 uint32_t to_start, int raw_copy_size) { 208 int copy_size = raw_copy_size; 209 if (raw_copy_size < 0) { 210 DisallowHeapAllocation no_allocation; 211 DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd || 212 raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 213 copy_size = Min(from_base->length() - from_start, 214 to_base->length() - to_start); 215 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 216 // Also initialize the area that will be copied over since HeapNumber 217 // allocation below can cause an incremental marking step, requiring all 218 // existing heap objects to be propertly initialized. 219 int start = to_start; 220 int length = to_base->length() - start; 221 if (length > 0) { 222 Heap* heap = from_base->GetHeap(); 223 MemsetPointer(FixedArray::cast(to_base)->data_start() + start, 224 heap->the_hole_value(), length); 225 } 226 } 227 } 228 229 DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() && 230 (copy_size + static_cast<int>(from_start)) <= from_base->length()); 231 if (copy_size == 0) return; 232 233 // From here on, the code below could actually allocate. Therefore the raw 234 // values are wrapped into handles. 235 Isolate* isolate = from_base->GetIsolate(); 236 Handle<FixedDoubleArray> from(FixedDoubleArray::cast(from_base), isolate); 237 Handle<FixedArray> to(FixedArray::cast(to_base), isolate); 238 239 // Use an outer loop to not waste too much time on creating HandleScopes. 240 // On the other hand we might overflow a single handle scope depending on 241 // the copy_size. 242 int offset = 0; 243 while (offset < copy_size) { 244 HandleScope scope(isolate); 245 offset += 100; 246 for (int i = offset - 100; i < offset && i < copy_size; ++i) { 247 Handle<Object> value = 248 FixedDoubleArray::get(*from, i + from_start, isolate); 249 to->set(i + to_start, *value, UPDATE_WRITE_BARRIER); 250 } 251 } 252 } 253 254 255 static void CopyDoubleToDoubleElements(FixedArrayBase* from_base, 256 uint32_t from_start, 257 FixedArrayBase* to_base, 258 uint32_t to_start, int raw_copy_size) { 259 DisallowHeapAllocation no_allocation; 260 int copy_size = raw_copy_size; 261 if (raw_copy_size < 0) { 262 DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd || 263 raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 264 copy_size = Min(from_base->length() - from_start, 265 to_base->length() - to_start); 266 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 267 for (int i = to_start + copy_size; i < to_base->length(); ++i) { 268 FixedDoubleArray::cast(to_base)->set_the_hole(i); 269 } 270 } 271 } 272 DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() && 273 (copy_size + static_cast<int>(from_start)) <= from_base->length()); 274 if (copy_size == 0) return; 275 FixedDoubleArray* from = FixedDoubleArray::cast(from_base); 276 FixedDoubleArray* to = FixedDoubleArray::cast(to_base); 277 Address to_address = to->address() + FixedDoubleArray::kHeaderSize; 278 Address from_address = from->address() + FixedDoubleArray::kHeaderSize; 279 to_address += kDoubleSize * to_start; 280 from_address += kDoubleSize * from_start; 281 int words_per_double = (kDoubleSize / kPointerSize); 282 CopyWords(reinterpret_cast<Object**>(to_address), 283 reinterpret_cast<Object**>(from_address), 284 static_cast<size_t>(words_per_double * copy_size)); 285 } 286 287 288 static void CopySmiToDoubleElements(FixedArrayBase* from_base, 289 uint32_t from_start, 290 FixedArrayBase* to_base, uint32_t to_start, 291 int raw_copy_size) { 292 DisallowHeapAllocation no_allocation; 293 int copy_size = raw_copy_size; 294 if (raw_copy_size < 0) { 295 DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd || 296 raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 297 copy_size = from_base->length() - from_start; 298 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 299 for (int i = to_start + copy_size; i < to_base->length(); ++i) { 300 FixedDoubleArray::cast(to_base)->set_the_hole(i); 301 } 302 } 303 } 304 DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() && 305 (copy_size + static_cast<int>(from_start)) <= from_base->length()); 306 if (copy_size == 0) return; 307 FixedArray* from = FixedArray::cast(from_base); 308 FixedDoubleArray* to = FixedDoubleArray::cast(to_base); 309 Object* the_hole = from->GetHeap()->the_hole_value(); 310 for (uint32_t from_end = from_start + static_cast<uint32_t>(copy_size); 311 from_start < from_end; from_start++, to_start++) { 312 Object* hole_or_smi = from->get(from_start); 313 if (hole_or_smi == the_hole) { 314 to->set_the_hole(to_start); 315 } else { 316 to->set(to_start, Smi::cast(hole_or_smi)->value()); 317 } 318 } 319 } 320 321 322 static void CopyPackedSmiToDoubleElements(FixedArrayBase* from_base, 323 uint32_t from_start, 324 FixedArrayBase* to_base, 325 uint32_t to_start, int packed_size, 326 int raw_copy_size) { 327 DisallowHeapAllocation no_allocation; 328 int copy_size = raw_copy_size; 329 uint32_t to_end; 330 if (raw_copy_size < 0) { 331 DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd || 332 raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 333 copy_size = packed_size - from_start; 334 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 335 to_end = to_base->length(); 336 for (uint32_t i = to_start + copy_size; i < to_end; ++i) { 337 FixedDoubleArray::cast(to_base)->set_the_hole(i); 338 } 339 } else { 340 to_end = to_start + static_cast<uint32_t>(copy_size); 341 } 342 } else { 343 to_end = to_start + static_cast<uint32_t>(copy_size); 344 } 345 DCHECK(static_cast<int>(to_end) <= to_base->length()); 346 DCHECK(packed_size >= 0 && packed_size <= copy_size); 347 DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() && 348 (copy_size + static_cast<int>(from_start)) <= from_base->length()); 349 if (copy_size == 0) return; 350 FixedArray* from = FixedArray::cast(from_base); 351 FixedDoubleArray* to = FixedDoubleArray::cast(to_base); 352 for (uint32_t from_end = from_start + static_cast<uint32_t>(packed_size); 353 from_start < from_end; from_start++, to_start++) { 354 Object* smi = from->get(from_start); 355 DCHECK(!smi->IsTheHole(from->GetIsolate())); 356 to->set(to_start, Smi::cast(smi)->value()); 357 } 358 } 359 360 361 static void CopyObjectToDoubleElements(FixedArrayBase* from_base, 362 uint32_t from_start, 363 FixedArrayBase* to_base, 364 uint32_t to_start, int raw_copy_size) { 365 DisallowHeapAllocation no_allocation; 366 int copy_size = raw_copy_size; 367 if (raw_copy_size < 0) { 368 DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd || 369 raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 370 copy_size = from_base->length() - from_start; 371 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 372 for (int i = to_start + copy_size; i < to_base->length(); ++i) { 373 FixedDoubleArray::cast(to_base)->set_the_hole(i); 374 } 375 } 376 } 377 DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() && 378 (copy_size + static_cast<int>(from_start)) <= from_base->length()); 379 if (copy_size == 0) return; 380 FixedArray* from = FixedArray::cast(from_base); 381 FixedDoubleArray* to = FixedDoubleArray::cast(to_base); 382 Object* the_hole = from->GetHeap()->the_hole_value(); 383 for (uint32_t from_end = from_start + copy_size; 384 from_start < from_end; from_start++, to_start++) { 385 Object* hole_or_object = from->get(from_start); 386 if (hole_or_object == the_hole) { 387 to->set_the_hole(to_start); 388 } else { 389 to->set(to_start, hole_or_object->Number()); 390 } 391 } 392 } 393 394 395 static void CopyDictionaryToDoubleElements(FixedArrayBase* from_base, 396 uint32_t from_start, 397 FixedArrayBase* to_base, 398 uint32_t to_start, 399 int raw_copy_size) { 400 DisallowHeapAllocation no_allocation; 401 SeededNumberDictionary* from = SeededNumberDictionary::cast(from_base); 402 int copy_size = raw_copy_size; 403 if (copy_size < 0) { 404 DCHECK(copy_size == ElementsAccessor::kCopyToEnd || 405 copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole); 406 copy_size = from->max_number_key() + 1 - from_start; 407 if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) { 408 for (int i = to_start + copy_size; i < to_base->length(); ++i) { 409 FixedDoubleArray::cast(to_base)->set_the_hole(i); 410 } 411 } 412 } 413 if (copy_size == 0) return; 414 FixedDoubleArray* to = FixedDoubleArray::cast(to_base); 415 uint32_t to_length = to->length(); 416 if (to_start + copy_size > to_length) { 417 copy_size = to_length - to_start; 418 } 419 for (int i = 0; i < copy_size; i++) { 420 int entry = from->FindEntry(i + from_start); 421 if (entry != SeededNumberDictionary::kNotFound) { 422 to->set(i + to_start, from->ValueAt(entry)->Number()); 423 } else { 424 to->set_the_hole(i + to_start); 425 } 426 } 427 } 428 429 static void TraceTopFrame(Isolate* isolate) { 430 StackFrameIterator it(isolate); 431 if (it.done()) { 432 PrintF("unknown location (no JavaScript frames present)"); 433 return; 434 } 435 StackFrame* raw_frame = it.frame(); 436 if (raw_frame->is_internal()) { 437 Code* apply_builtin = 438 isolate->builtins()->builtin(Builtins::kFunctionPrototypeApply); 439 if (raw_frame->unchecked_code() == apply_builtin) { 440 PrintF("apply from "); 441 it.Advance(); 442 raw_frame = it.frame(); 443 } 444 } 445 JavaScriptFrame::PrintTop(isolate, stdout, false, true); 446 } 447 448 static void SortIndices( 449 Handle<FixedArray> indices, uint32_t sort_size, 450 WriteBarrierMode write_barrier_mode = UPDATE_WRITE_BARRIER) { 451 struct { 452 bool operator()(Object* a, Object* b) { 453 if (a->IsSmi() || !a->IsUndefined(HeapObject::cast(a)->GetIsolate())) { 454 if (!b->IsSmi() && b->IsUndefined(HeapObject::cast(b)->GetIsolate())) { 455 return true; 456 } 457 return a->Number() < b->Number(); 458 } 459 return !b->IsSmi() && b->IsUndefined(HeapObject::cast(b)->GetIsolate()); 460 } 461 } cmp; 462 Object** start = 463 reinterpret_cast<Object**>(indices->GetFirstElementAddress()); 464 std::sort(start, start + sort_size, cmp); 465 if (write_barrier_mode != SKIP_WRITE_BARRIER) { 466 FIXED_ARRAY_ELEMENTS_WRITE_BARRIER(indices->GetIsolate()->heap(), *indices, 467 0, sort_size); 468 } 469 } 470 471 // Base class for element handler implementations. Contains the 472 // the common logic for objects with different ElementsKinds. 473 // Subclasses must specialize method for which the element 474 // implementation differs from the base class implementation. 475 // 476 // This class is intended to be used in the following way: 477 // 478 // class SomeElementsAccessor : 479 // public ElementsAccessorBase<SomeElementsAccessor, 480 // BackingStoreClass> { 481 // ... 482 // } 483 // 484 // This is an example of the Curiously Recurring Template Pattern (see 485 // http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern). We use 486 // CRTP to guarantee aggressive compile time optimizations (i.e. inlining and 487 // specialization of SomeElementsAccessor methods). 488 template <typename Subclass, typename ElementsTraitsParam> 489 class ElementsAccessorBase : public ElementsAccessor { 490 public: 491 explicit ElementsAccessorBase(const char* name) 492 : ElementsAccessor(name) { } 493 494 typedef ElementsTraitsParam ElementsTraits; 495 typedef typename ElementsTraitsParam::BackingStore BackingStore; 496 497 static ElementsKind kind() { return ElementsTraits::Kind; } 498 499 static void ValidateContents(Handle<JSObject> holder, int length) { 500 } 501 502 static void ValidateImpl(Handle<JSObject> holder) { 503 Handle<FixedArrayBase> fixed_array_base(holder->elements()); 504 if (!fixed_array_base->IsHeapObject()) return; 505 // Arrays that have been shifted in place can't be verified. 506 if (fixed_array_base->IsFiller()) return; 507 int length = 0; 508 if (holder->IsJSArray()) { 509 Object* length_obj = Handle<JSArray>::cast(holder)->length(); 510 if (length_obj->IsSmi()) { 511 length = Smi::cast(length_obj)->value(); 512 } 513 } else { 514 length = fixed_array_base->length(); 515 } 516 Subclass::ValidateContents(holder, length); 517 } 518 519 void Validate(Handle<JSObject> holder) final { 520 DisallowHeapAllocation no_gc; 521 Subclass::ValidateImpl(holder); 522 } 523 524 static bool IsPackedImpl(Handle<JSObject> holder, 525 Handle<FixedArrayBase> backing_store, uint32_t start, 526 uint32_t end) { 527 if (IsFastPackedElementsKind(kind())) return true; 528 for (uint32_t i = start; i < end; i++) { 529 if (!Subclass::HasElementImpl(holder, i, backing_store, ALL_PROPERTIES)) { 530 return false; 531 } 532 } 533 return true; 534 } 535 536 static void TryTransitionResultArrayToPacked(Handle<JSArray> array) { 537 if (!IsHoleyElementsKind(kind())) return; 538 int length = Smi::cast(array->length())->value(); 539 Handle<FixedArrayBase> backing_store(array->elements()); 540 if (!Subclass::IsPackedImpl(array, backing_store, 0, length)) { 541 return; 542 } 543 ElementsKind packed_kind = GetPackedElementsKind(kind()); 544 Handle<Map> new_map = 545 JSObject::GetElementsTransitionMap(array, packed_kind); 546 JSObject::MigrateToMap(array, new_map); 547 if (FLAG_trace_elements_transitions) { 548 JSObject::PrintElementsTransition(stdout, array, kind(), backing_store, 549 packed_kind, backing_store); 550 } 551 } 552 553 bool HasElement(Handle<JSObject> holder, uint32_t index, 554 Handle<FixedArrayBase> backing_store, 555 PropertyFilter filter) final { 556 return Subclass::HasElementImpl(holder, index, backing_store, filter); 557 } 558 559 static bool HasElementImpl(Handle<JSObject> holder, uint32_t index, 560 Handle<FixedArrayBase> backing_store, 561 PropertyFilter filter) { 562 return Subclass::GetEntryForIndexImpl(*holder, *backing_store, index, 563 filter) != kMaxUInt32; 564 } 565 566 bool HasAccessors(JSObject* holder) final { 567 return Subclass::HasAccessorsImpl(holder, holder->elements()); 568 } 569 570 static bool HasAccessorsImpl(JSObject* holder, 571 FixedArrayBase* backing_store) { 572 return false; 573 } 574 575 Handle<Object> Get(Handle<JSObject> holder, uint32_t entry) final { 576 return Subclass::GetImpl(holder, entry); 577 } 578 579 static Handle<Object> GetImpl(Handle<JSObject> holder, uint32_t entry) { 580 return Subclass::GetImpl(holder->elements(), entry); 581 } 582 583 static Handle<Object> GetImpl(FixedArrayBase* backing_store, uint32_t entry) { 584 Isolate* isolate = backing_store->GetIsolate(); 585 uint32_t index = GetIndexForEntryImpl(backing_store, entry); 586 return handle(BackingStore::cast(backing_store)->get(index), isolate); 587 } 588 589 void Set(Handle<JSObject> holder, uint32_t entry, Object* value) final { 590 Subclass::SetImpl(holder, entry, value); 591 } 592 593 void Reconfigure(Handle<JSObject> object, Handle<FixedArrayBase> store, 594 uint32_t entry, Handle<Object> value, 595 PropertyAttributes attributes) final { 596 Subclass::ReconfigureImpl(object, store, entry, value, attributes); 597 } 598 599 static void ReconfigureImpl(Handle<JSObject> object, 600 Handle<FixedArrayBase> store, uint32_t entry, 601 Handle<Object> value, 602 PropertyAttributes attributes) { 603 UNREACHABLE(); 604 } 605 606 void Add(Handle<JSObject> object, uint32_t index, Handle<Object> value, 607 PropertyAttributes attributes, uint32_t new_capacity) final { 608 Subclass::AddImpl(object, index, value, attributes, new_capacity); 609 } 610 611 static void AddImpl(Handle<JSObject> object, uint32_t index, 612 Handle<Object> value, PropertyAttributes attributes, 613 uint32_t new_capacity) { 614 UNREACHABLE(); 615 } 616 617 uint32_t Push(Handle<JSArray> receiver, Arguments* args, 618 uint32_t push_size) final { 619 return Subclass::PushImpl(receiver, args, push_size); 620 } 621 622 static uint32_t PushImpl(Handle<JSArray> receiver, Arguments* args, 623 uint32_t push_sized) { 624 UNREACHABLE(); 625 return 0; 626 } 627 628 uint32_t Unshift(Handle<JSArray> receiver, Arguments* args, 629 uint32_t unshift_size) final { 630 return Subclass::UnshiftImpl(receiver, args, unshift_size); 631 } 632 633 static uint32_t UnshiftImpl(Handle<JSArray> receiver, Arguments* args, 634 uint32_t unshift_size) { 635 UNREACHABLE(); 636 return 0; 637 } 638 639 Handle<JSArray> Slice(Handle<JSObject> receiver, uint32_t start, 640 uint32_t end) final { 641 return Subclass::SliceImpl(receiver, start, end); 642 } 643 644 static Handle<JSArray> SliceImpl(Handle<JSObject> receiver, 645 uint32_t start, uint32_t end) { 646 UNREACHABLE(); 647 return Handle<JSArray>(); 648 } 649 650 Handle<JSArray> Splice(Handle<JSArray> receiver, uint32_t start, 651 uint32_t delete_count, Arguments* args, 652 uint32_t add_count) final { 653 return Subclass::SpliceImpl(receiver, start, delete_count, args, add_count); 654 } 655 656 static Handle<JSArray> SpliceImpl(Handle<JSArray> receiver, 657 uint32_t start, uint32_t delete_count, 658 Arguments* args, uint32_t add_count) { 659 UNREACHABLE(); 660 return Handle<JSArray>(); 661 } 662 663 Handle<Object> Pop(Handle<JSArray> receiver) final { 664 return Subclass::PopImpl(receiver); 665 } 666 667 static Handle<Object> PopImpl(Handle<JSArray> receiver) { 668 UNREACHABLE(); 669 return Handle<Object>(); 670 } 671 672 Handle<Object> Shift(Handle<JSArray> receiver) final { 673 return Subclass::ShiftImpl(receiver); 674 } 675 676 static Handle<Object> ShiftImpl(Handle<JSArray> receiver) { 677 UNREACHABLE(); 678 return Handle<Object>(); 679 } 680 681 void SetLength(Handle<JSArray> array, uint32_t length) final { 682 Subclass::SetLengthImpl(array->GetIsolate(), array, length, 683 handle(array->elements())); 684 } 685 686 static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array, 687 uint32_t length, 688 Handle<FixedArrayBase> backing_store) { 689 DCHECK(!array->SetLengthWouldNormalize(length)); 690 DCHECK(IsFastElementsKind(array->GetElementsKind())); 691 uint32_t old_length = 0; 692 CHECK(array->length()->ToArrayIndex(&old_length)); 693 694 if (old_length < length) { 695 ElementsKind kind = array->GetElementsKind(); 696 if (!IsFastHoleyElementsKind(kind)) { 697 kind = GetHoleyElementsKind(kind); 698 JSObject::TransitionElementsKind(array, kind); 699 } 700 } 701 702 // Check whether the backing store should be shrunk. 703 uint32_t capacity = backing_store->length(); 704 old_length = Min(old_length, capacity); 705 if (length == 0) { 706 array->initialize_elements(); 707 } else if (length <= capacity) { 708 if (IsFastSmiOrObjectElementsKind(kind())) { 709 JSObject::EnsureWritableFastElements(array); 710 if (array->elements() != *backing_store) { 711 backing_store = handle(array->elements(), isolate); 712 } 713 } 714 if (2 * length <= capacity) { 715 // If more than half the elements won't be used, trim the array. 716 isolate->heap()->RightTrimFixedArray<Heap::CONCURRENT_TO_SWEEPER>( 717 *backing_store, capacity - length); 718 } else { 719 // Otherwise, fill the unused tail with holes. 720 for (uint32_t i = length; i < old_length; i++) { 721 BackingStore::cast(*backing_store)->set_the_hole(i); 722 } 723 } 724 } else { 725 // Check whether the backing store should be expanded. 726 capacity = Max(length, JSObject::NewElementsCapacity(capacity)); 727 Subclass::GrowCapacityAndConvertImpl(array, capacity); 728 } 729 730 array->set_length(Smi::FromInt(length)); 731 JSObject::ValidateElements(array); 732 } 733 734 static uint32_t GetMaxIndex(JSObject* receiver, FixedArrayBase* elements) { 735 if (receiver->IsJSArray()) { 736 DCHECK(JSArray::cast(receiver)->length()->IsSmi()); 737 return static_cast<uint32_t>( 738 Smi::cast(JSArray::cast(receiver)->length())->value()); 739 } 740 return Subclass::GetCapacityImpl(receiver, elements); 741 } 742 743 static uint32_t GetMaxNumberOfEntries(JSObject* receiver, 744 FixedArrayBase* elements) { 745 return Subclass::GetMaxIndex(receiver, elements); 746 } 747 748 static Handle<FixedArrayBase> ConvertElementsWithCapacity( 749 Handle<JSObject> object, Handle<FixedArrayBase> old_elements, 750 ElementsKind from_kind, uint32_t capacity) { 751 return ConvertElementsWithCapacity( 752 object, old_elements, from_kind, capacity, 0, 0, 753 ElementsAccessor::kCopyToEndAndInitializeToHole); 754 } 755 756 static Handle<FixedArrayBase> ConvertElementsWithCapacity( 757 Handle<JSObject> object, Handle<FixedArrayBase> old_elements, 758 ElementsKind from_kind, uint32_t capacity, int copy_size) { 759 return ConvertElementsWithCapacity(object, old_elements, from_kind, 760 capacity, 0, 0, copy_size); 761 } 762 763 static Handle<FixedArrayBase> ConvertElementsWithCapacity( 764 Handle<JSObject> object, Handle<FixedArrayBase> old_elements, 765 ElementsKind from_kind, uint32_t capacity, uint32_t src_index, 766 uint32_t dst_index, int copy_size) { 767 Isolate* isolate = object->GetIsolate(); 768 Handle<FixedArrayBase> new_elements; 769 if (IsFastDoubleElementsKind(kind())) { 770 new_elements = isolate->factory()->NewFixedDoubleArray(capacity); 771 } else { 772 new_elements = isolate->factory()->NewUninitializedFixedArray(capacity); 773 } 774 775 int packed_size = kPackedSizeNotKnown; 776 if (IsFastPackedElementsKind(from_kind) && object->IsJSArray()) { 777 packed_size = Smi::cast(JSArray::cast(*object)->length())->value(); 778 } 779 780 Subclass::CopyElementsImpl(*old_elements, src_index, *new_elements, 781 from_kind, dst_index, packed_size, copy_size); 782 783 return new_elements; 784 } 785 786 static void GrowCapacityAndConvertImpl(Handle<JSObject> object, 787 uint32_t capacity) { 788 ElementsKind from_kind = object->GetElementsKind(); 789 if (IsFastSmiOrObjectElementsKind(from_kind)) { 790 // Array optimizations rely on the prototype lookups of Array objects 791 // always returning undefined. If there is a store to the initial 792 // prototype object, make sure all of these optimizations are invalidated. 793 object->GetIsolate()->UpdateArrayProtectorOnSetLength(object); 794 } 795 Handle<FixedArrayBase> old_elements(object->elements()); 796 // This method should only be called if there's a reason to update the 797 // elements. 798 DCHECK(IsFastDoubleElementsKind(from_kind) != 799 IsFastDoubleElementsKind(kind()) || 800 IsDictionaryElementsKind(from_kind) || 801 static_cast<uint32_t>(old_elements->length()) < capacity); 802 Subclass::BasicGrowCapacityAndConvertImpl(object, old_elements, from_kind, 803 kind(), capacity); 804 } 805 806 static void BasicGrowCapacityAndConvertImpl( 807 Handle<JSObject> object, Handle<FixedArrayBase> old_elements, 808 ElementsKind from_kind, ElementsKind to_kind, uint32_t capacity) { 809 Handle<FixedArrayBase> elements = 810 ConvertElementsWithCapacity(object, old_elements, from_kind, capacity); 811 812 if (IsHoleyElementsKind(from_kind)) to_kind = GetHoleyElementsKind(to_kind); 813 Handle<Map> new_map = JSObject::GetElementsTransitionMap(object, to_kind); 814 JSObject::SetMapAndElements(object, new_map, elements); 815 816 // Transition through the allocation site as well if present. 817 JSObject::UpdateAllocationSite(object, to_kind); 818 819 if (FLAG_trace_elements_transitions) { 820 JSObject::PrintElementsTransition(stdout, object, from_kind, old_elements, 821 to_kind, elements); 822 } 823 } 824 825 void GrowCapacityAndConvert(Handle<JSObject> object, 826 uint32_t capacity) final { 827 Subclass::GrowCapacityAndConvertImpl(object, capacity); 828 } 829 830 void Delete(Handle<JSObject> obj, uint32_t entry) final { 831 Subclass::DeleteImpl(obj, entry); 832 } 833 834 static void CopyElementsImpl(FixedArrayBase* from, uint32_t from_start, 835 FixedArrayBase* to, ElementsKind from_kind, 836 uint32_t to_start, int packed_size, 837 int copy_size) { 838 UNREACHABLE(); 839 } 840 841 void CopyElements(JSObject* from_holder, uint32_t from_start, 842 ElementsKind from_kind, Handle<FixedArrayBase> to, 843 uint32_t to_start, int copy_size) final { 844 int packed_size = kPackedSizeNotKnown; 845 bool is_packed = IsFastPackedElementsKind(from_kind) && 846 from_holder->IsJSArray(); 847 if (is_packed) { 848 packed_size = 849 Smi::cast(JSArray::cast(from_holder)->length())->value(); 850 if (copy_size >= 0 && packed_size > copy_size) { 851 packed_size = copy_size; 852 } 853 } 854 FixedArrayBase* from = from_holder->elements(); 855 // NOTE: the Subclass::CopyElementsImpl() methods 856 // violate the handlified function signature convention: 857 // raw pointer parameters in the function that allocates. This is done 858 // intentionally to avoid ArrayConcat() builtin performance degradation. 859 // 860 // Details: The idea is that allocations actually happen only in case of 861 // copying from object with fast double elements to object with object 862 // elements. In all the other cases there are no allocations performed and 863 // handle creation causes noticeable performance degradation of the builtin. 864 Subclass::CopyElementsImpl(from, from_start, *to, from_kind, to_start, 865 packed_size, copy_size); 866 } 867 868 Handle<SeededNumberDictionary> Normalize(Handle<JSObject> object) final { 869 return Subclass::NormalizeImpl(object, handle(object->elements())); 870 } 871 872 static Handle<SeededNumberDictionary> NormalizeImpl( 873 Handle<JSObject> object, Handle<FixedArrayBase> elements) { 874 UNREACHABLE(); 875 return Handle<SeededNumberDictionary>(); 876 } 877 878 Maybe<bool> CollectValuesOrEntries(Isolate* isolate, Handle<JSObject> object, 879 Handle<FixedArray> values_or_entries, 880 bool get_entries, int* nof_items, 881 PropertyFilter filter) { 882 return Subclass::CollectValuesOrEntriesImpl( 883 isolate, object, values_or_entries, get_entries, nof_items, filter); 884 } 885 886 static Maybe<bool> CollectValuesOrEntriesImpl( 887 Isolate* isolate, Handle<JSObject> object, 888 Handle<FixedArray> values_or_entries, bool get_entries, int* nof_items, 889 PropertyFilter filter) { 890 int count = 0; 891 KeyAccumulator accumulator(isolate, KeyCollectionMode::kOwnOnly, 892 ALL_PROPERTIES); 893 Subclass::CollectElementIndicesImpl( 894 object, handle(object->elements(), isolate), &accumulator); 895 Handle<FixedArray> keys = accumulator.GetKeys(); 896 897 for (int i = 0; i < keys->length(); ++i) { 898 Handle<Object> key(keys->get(i), isolate); 899 Handle<Object> value; 900 uint32_t index; 901 if (!key->ToUint32(&index)) continue; 902 903 uint32_t entry = Subclass::GetEntryForIndexImpl( 904 *object, object->elements(), index, filter); 905 if (entry == kMaxUInt32) continue; 906 907 PropertyDetails details = Subclass::GetDetailsImpl(*object, entry); 908 909 if (details.kind() == kData) { 910 value = Subclass::GetImpl(object, entry); 911 } else { 912 LookupIterator it(isolate, object, index, LookupIterator::OWN); 913 ASSIGN_RETURN_ON_EXCEPTION_VALUE( 914 isolate, value, Object::GetProperty(&it), Nothing<bool>()); 915 } 916 if (get_entries) { 917 value = MakeEntryPair(isolate, index, value); 918 } 919 values_or_entries->set(count++, *value); 920 } 921 922 *nof_items = count; 923 return Just(true); 924 } 925 926 void CollectElementIndices(Handle<JSObject> object, 927 Handle<FixedArrayBase> backing_store, 928 KeyAccumulator* keys) final { 929 if (keys->filter() & ONLY_ALL_CAN_READ) return; 930 Subclass::CollectElementIndicesImpl(object, backing_store, keys); 931 } 932 933 static void CollectElementIndicesImpl(Handle<JSObject> object, 934 Handle<FixedArrayBase> backing_store, 935 KeyAccumulator* keys) { 936 DCHECK_NE(DICTIONARY_ELEMENTS, kind()); 937 // Non-dictionary elements can't have all-can-read accessors. 938 uint32_t length = Subclass::GetMaxIndex(*object, *backing_store); 939 PropertyFilter filter = keys->filter(); 940 Factory* factory = keys->isolate()->factory(); 941 for (uint32_t i = 0; i < length; i++) { 942 if (Subclass::HasElementImpl(object, i, backing_store, filter)) { 943 keys->AddKey(factory->NewNumberFromUint(i)); 944 } 945 } 946 } 947 948 static Handle<FixedArray> DirectCollectElementIndicesImpl( 949 Isolate* isolate, Handle<JSObject> object, 950 Handle<FixedArrayBase> backing_store, GetKeysConversion convert, 951 PropertyFilter filter, Handle<FixedArray> list, uint32_t* nof_indices, 952 uint32_t insertion_index = 0) { 953 uint32_t length = Subclass::GetMaxIndex(*object, *backing_store); 954 for (uint32_t i = 0; i < length; i++) { 955 if (Subclass::HasElementImpl(object, i, backing_store, filter)) { 956 if (convert == GetKeysConversion::kConvertToString) { 957 Handle<String> index_string = isolate->factory()->Uint32ToString(i); 958 list->set(insertion_index, *index_string); 959 } else { 960 list->set(insertion_index, Smi::FromInt(i), SKIP_WRITE_BARRIER); 961 } 962 insertion_index++; 963 } 964 } 965 *nof_indices = insertion_index; 966 return list; 967 } 968 969 Handle<FixedArray> PrependElementIndices(Handle<JSObject> object, 970 Handle<FixedArrayBase> backing_store, 971 Handle<FixedArray> keys, 972 GetKeysConversion convert, 973 PropertyFilter filter) final { 974 return Subclass::PrependElementIndicesImpl(object, backing_store, keys, 975 convert, filter); 976 } 977 978 static Handle<FixedArray> PrependElementIndicesImpl( 979 Handle<JSObject> object, Handle<FixedArrayBase> backing_store, 980 Handle<FixedArray> keys, GetKeysConversion convert, 981 PropertyFilter filter) { 982 Isolate* isolate = object->GetIsolate(); 983 uint32_t nof_property_keys = keys->length(); 984 uint32_t initial_list_length = 985 Subclass::GetCapacityImpl(*object, *backing_store); 986 initial_list_length += nof_property_keys; 987 988 // Collect the element indices into a new list. 989 uint32_t nof_indices = 0; 990 Handle<FixedArray> combined_keys = 991 isolate->factory()->NewFixedArray(initial_list_length); 992 combined_keys = Subclass::DirectCollectElementIndicesImpl( 993 isolate, object, backing_store, convert, filter, combined_keys, 994 &nof_indices); 995 996 // Sort the indices list if necessary. 997 if (IsDictionaryElementsKind(kind()) || IsSloppyArgumentsElements(kind())) { 998 SortIndices(combined_keys, nof_indices, SKIP_WRITE_BARRIER); 999 uint32_t array_length = 0; 1000 // Indices from dictionary elements should only be converted after 1001 // sorting. 1002 if (convert == GetKeysConversion::kConvertToString) { 1003 for (uint32_t i = 0; i < nof_indices; i++) { 1004 Handle<Object> index_string = isolate->factory()->Uint32ToString( 1005 combined_keys->get(i)->Number()); 1006 combined_keys->set(i, *index_string); 1007 } 1008 } else if (!(object->IsJSArray() && 1009 JSArray::cast(*object)->length()->ToArrayLength( 1010 &array_length) && 1011 array_length <= Smi::kMaxValue)) { 1012 // Since we use std::sort above, the GC will no longer know where the 1013 // HeapNumbers are. For Arrays with valid Smi length, we are sure to 1014 // have no HeapNumber indices and thus we can skip this step. 1015 FIXED_ARRAY_ELEMENTS_WRITE_BARRIER(isolate->heap(), *combined_keys, 0, 1016 nof_indices); 1017 } 1018 } 1019 1020 // Copy over the passed-in property keys. 1021 CopyObjectToObjectElements(*keys, FAST_ELEMENTS, 0, *combined_keys, 1022 FAST_ELEMENTS, nof_indices, nof_property_keys); 1023 1024 if (IsHoleyElementsKind(kind())) { 1025 // Shrink combined_keys to the final size. 1026 int final_size = nof_indices + nof_property_keys; 1027 DCHECK_LE(final_size, combined_keys->length()); 1028 combined_keys->Shrink(final_size); 1029 } 1030 1031 return combined_keys; 1032 } 1033 1034 void AddElementsToKeyAccumulator(Handle<JSObject> receiver, 1035 KeyAccumulator* accumulator, 1036 AddKeyConversion convert) final { 1037 Subclass::AddElementsToKeyAccumulatorImpl(receiver, accumulator, convert); 1038 } 1039 1040 static uint32_t GetCapacityImpl(JSObject* holder, 1041 FixedArrayBase* backing_store) { 1042 return backing_store->length(); 1043 } 1044 1045 uint32_t GetCapacity(JSObject* holder, FixedArrayBase* backing_store) final { 1046 return Subclass::GetCapacityImpl(holder, backing_store); 1047 } 1048 1049 static uint32_t GetIndexForEntryImpl(FixedArrayBase* backing_store, 1050 uint32_t entry) { 1051 return entry; 1052 } 1053 1054 static uint32_t GetEntryForIndexImpl(JSObject* holder, 1055 FixedArrayBase* backing_store, 1056 uint32_t index, PropertyFilter filter) { 1057 if (IsHoleyElementsKind(kind())) { 1058 return index < Subclass::GetCapacityImpl(holder, backing_store) && 1059 !BackingStore::cast(backing_store)->is_the_hole(index) 1060 ? index 1061 : kMaxUInt32; 1062 } else { 1063 uint32_t length = Subclass::GetMaxIndex(holder, backing_store); 1064 return index < length ? index : kMaxUInt32; 1065 } 1066 } 1067 1068 uint32_t GetEntryForIndex(JSObject* holder, FixedArrayBase* backing_store, 1069 uint32_t index) final { 1070 return Subclass::GetEntryForIndexImpl(holder, backing_store, index, 1071 ALL_PROPERTIES); 1072 } 1073 1074 static PropertyDetails GetDetailsImpl(FixedArrayBase* backing_store, 1075 uint32_t entry) { 1076 return PropertyDetails(NONE, DATA, 0, PropertyCellType::kNoCell); 1077 } 1078 1079 static PropertyDetails GetDetailsImpl(JSObject* holder, uint32_t entry) { 1080 return PropertyDetails(NONE, DATA, 0, PropertyCellType::kNoCell); 1081 } 1082 1083 PropertyDetails GetDetails(JSObject* holder, uint32_t entry) final { 1084 return Subclass::GetDetailsImpl(holder, entry); 1085 } 1086 1087 private: 1088 DISALLOW_COPY_AND_ASSIGN(ElementsAccessorBase); 1089 }; 1090 1091 1092 class DictionaryElementsAccessor 1093 : public ElementsAccessorBase<DictionaryElementsAccessor, 1094 ElementsKindTraits<DICTIONARY_ELEMENTS> > { 1095 public: 1096 explicit DictionaryElementsAccessor(const char* name) 1097 : ElementsAccessorBase<DictionaryElementsAccessor, 1098 ElementsKindTraits<DICTIONARY_ELEMENTS> >(name) {} 1099 1100 static uint32_t GetMaxIndex(JSObject* receiver, FixedArrayBase* elements) { 1101 // We cannot properly estimate this for dictionaries. 1102 UNREACHABLE(); 1103 } 1104 1105 static uint32_t GetMaxNumberOfEntries(JSObject* receiver, 1106 FixedArrayBase* backing_store) { 1107 SeededNumberDictionary* dict = SeededNumberDictionary::cast(backing_store); 1108 return dict->NumberOfElements(); 1109 } 1110 1111 static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array, 1112 uint32_t length, 1113 Handle<FixedArrayBase> backing_store) { 1114 Handle<SeededNumberDictionary> dict = 1115 Handle<SeededNumberDictionary>::cast(backing_store); 1116 int capacity = dict->Capacity(); 1117 uint32_t old_length = 0; 1118 CHECK(array->length()->ToArrayLength(&old_length)); 1119 if (length < old_length) { 1120 if (dict->requires_slow_elements()) { 1121 // Find last non-deletable element in range of elements to be 1122 // deleted and adjust range accordingly. 1123 for (int entry = 0; entry < capacity; entry++) { 1124 DisallowHeapAllocation no_gc; 1125 Object* index = dict->KeyAt(entry); 1126 if (index->IsNumber()) { 1127 uint32_t number = static_cast<uint32_t>(index->Number()); 1128 if (length <= number && number < old_length) { 1129 PropertyDetails details = dict->DetailsAt(entry); 1130 if (!details.IsConfigurable()) length = number + 1; 1131 } 1132 } 1133 } 1134 } 1135 1136 if (length == 0) { 1137 // Flush the backing store. 1138 JSObject::ResetElements(array); 1139 } else { 1140 DisallowHeapAllocation no_gc; 1141 // Remove elements that should be deleted. 1142 int removed_entries = 0; 1143 Handle<Object> the_hole_value = isolate->factory()->the_hole_value(); 1144 for (int entry = 0; entry < capacity; entry++) { 1145 Object* index = dict->KeyAt(entry); 1146 if (index->IsNumber()) { 1147 uint32_t number = static_cast<uint32_t>(index->Number()); 1148 if (length <= number && number < old_length) { 1149 dict->SetEntry(entry, the_hole_value, the_hole_value); 1150 removed_entries++; 1151 } 1152 } 1153 } 1154 1155 // Update the number of elements. 1156 dict->ElementsRemoved(removed_entries); 1157 } 1158 } 1159 1160 Handle<Object> length_obj = isolate->factory()->NewNumberFromUint(length); 1161 array->set_length(*length_obj); 1162 } 1163 1164 static void CopyElementsImpl(FixedArrayBase* from, uint32_t from_start, 1165 FixedArrayBase* to, ElementsKind from_kind, 1166 uint32_t to_start, int packed_size, 1167 int copy_size) { 1168 UNREACHABLE(); 1169 } 1170 1171 1172 static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) { 1173 // TODO(verwaest): Remove reliance on index in Shrink. 1174 Handle<SeededNumberDictionary> dict( 1175 SeededNumberDictionary::cast(obj->elements())); 1176 uint32_t index = GetIndexForEntryImpl(*dict, entry); 1177 Handle<Object> result = SeededNumberDictionary::DeleteProperty(dict, entry); 1178 USE(result); 1179 DCHECK(result->IsTrue(dict->GetIsolate())); 1180 Handle<FixedArray> new_elements = 1181 SeededNumberDictionary::Shrink(dict, index); 1182 obj->set_elements(*new_elements); 1183 } 1184 1185 static bool HasAccessorsImpl(JSObject* holder, 1186 FixedArrayBase* backing_store) { 1187 DisallowHeapAllocation no_gc; 1188 SeededNumberDictionary* dict = SeededNumberDictionary::cast(backing_store); 1189 if (!dict->requires_slow_elements()) return false; 1190 int capacity = dict->Capacity(); 1191 Isolate* isolate = dict->GetIsolate(); 1192 for (int i = 0; i < capacity; i++) { 1193 Object* key = dict->KeyAt(i); 1194 if (!dict->IsKey(isolate, key)) continue; 1195 DCHECK(!dict->IsDeleted(i)); 1196 PropertyDetails details = dict->DetailsAt(i); 1197 if (details.type() == ACCESSOR_CONSTANT) return true; 1198 } 1199 return false; 1200 } 1201 1202 static Object* GetRaw(FixedArrayBase* store, uint32_t entry) { 1203 SeededNumberDictionary* backing_store = SeededNumberDictionary::cast(store); 1204 return backing_store->ValueAt(entry); 1205 } 1206 1207 static Handle<Object> GetImpl(Handle<JSObject> holder, uint32_t entry) { 1208 return GetImpl(holder->elements(), entry); 1209 } 1210 1211 static Handle<Object> GetImpl(FixedArrayBase* backing_store, uint32_t entry) { 1212 return handle(GetRaw(backing_store, entry), backing_store->GetIsolate()); 1213 } 1214 1215 static inline void SetImpl(Handle<JSObject> holder, uint32_t entry, 1216 Object* value) { 1217 SetImpl(holder->elements(), entry, value); 1218 } 1219 1220 static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry, 1221 Object* value) { 1222 SeededNumberDictionary::cast(backing_store)->ValueAtPut(entry, value); 1223 } 1224 1225 static void ReconfigureImpl(Handle<JSObject> object, 1226 Handle<FixedArrayBase> store, uint32_t entry, 1227 Handle<Object> value, 1228 PropertyAttributes attributes) { 1229 SeededNumberDictionary* dictionary = SeededNumberDictionary::cast(*store); 1230 if (attributes != NONE) object->RequireSlowElements(dictionary); 1231 dictionary->ValueAtPut(entry, *value); 1232 PropertyDetails details = dictionary->DetailsAt(entry); 1233 details = PropertyDetails(attributes, DATA, details.dictionary_index(), 1234 PropertyCellType::kNoCell); 1235 dictionary->DetailsAtPut(entry, details); 1236 } 1237 1238 static void AddImpl(Handle<JSObject> object, uint32_t index, 1239 Handle<Object> value, PropertyAttributes attributes, 1240 uint32_t new_capacity) { 1241 PropertyDetails details(attributes, DATA, 0, PropertyCellType::kNoCell); 1242 Handle<SeededNumberDictionary> dictionary = 1243 object->HasFastElements() || object->HasFastStringWrapperElements() 1244 ? JSObject::NormalizeElements(object) 1245 : handle(SeededNumberDictionary::cast(object->elements())); 1246 Handle<SeededNumberDictionary> new_dictionary = 1247 SeededNumberDictionary::AddNumberEntry( 1248 dictionary, index, value, details, 1249 object->map()->is_prototype_map()); 1250 if (attributes != NONE) object->RequireSlowElements(*new_dictionary); 1251 if (dictionary.is_identical_to(new_dictionary)) return; 1252 object->set_elements(*new_dictionary); 1253 } 1254 1255 static bool HasEntryImpl(FixedArrayBase* store, uint32_t entry) { 1256 DisallowHeapAllocation no_gc; 1257 SeededNumberDictionary* dict = SeededNumberDictionary::cast(store); 1258 Object* index = dict->KeyAt(entry); 1259 return !index->IsTheHole(dict->GetIsolate()); 1260 } 1261 1262 static uint32_t GetIndexForEntryImpl(FixedArrayBase* store, uint32_t entry) { 1263 DisallowHeapAllocation no_gc; 1264 SeededNumberDictionary* dict = SeededNumberDictionary::cast(store); 1265 uint32_t result = 0; 1266 CHECK(dict->KeyAt(entry)->ToArrayIndex(&result)); 1267 return result; 1268 } 1269 1270 static uint32_t GetEntryForIndexImpl(JSObject* holder, FixedArrayBase* store, 1271 uint32_t index, PropertyFilter filter) { 1272 DisallowHeapAllocation no_gc; 1273 SeededNumberDictionary* dictionary = SeededNumberDictionary::cast(store); 1274 int entry = dictionary->FindEntry(index); 1275 if (entry == SeededNumberDictionary::kNotFound) return kMaxUInt32; 1276 if (filter != ALL_PROPERTIES) { 1277 PropertyDetails details = dictionary->DetailsAt(entry); 1278 PropertyAttributes attr = details.attributes(); 1279 if ((attr & filter) != 0) return kMaxUInt32; 1280 } 1281 return static_cast<uint32_t>(entry); 1282 } 1283 1284 static PropertyDetails GetDetailsImpl(JSObject* holder, uint32_t entry) { 1285 return GetDetailsImpl(holder->elements(), entry); 1286 } 1287 1288 static PropertyDetails GetDetailsImpl(FixedArrayBase* backing_store, 1289 uint32_t entry) { 1290 return SeededNumberDictionary::cast(backing_store)->DetailsAt(entry); 1291 } 1292 1293 static uint32_t FilterKey(Handle<SeededNumberDictionary> dictionary, 1294 int entry, Object* raw_key, PropertyFilter filter) { 1295 DCHECK(!dictionary->IsDeleted(entry)); 1296 DCHECK(raw_key->IsNumber()); 1297 DCHECK_LE(raw_key->Number(), kMaxUInt32); 1298 PropertyDetails details = dictionary->DetailsAt(entry); 1299 PropertyAttributes attr = details.attributes(); 1300 if ((attr & filter) != 0) return kMaxUInt32; 1301 return static_cast<uint32_t>(raw_key->Number()); 1302 } 1303 1304 static uint32_t GetKeyForEntryImpl(Isolate* isolate, 1305 Handle<SeededNumberDictionary> dictionary, 1306 int entry, PropertyFilter filter) { 1307 DisallowHeapAllocation no_gc; 1308 Object* raw_key = dictionary->KeyAt(entry); 1309 if (!dictionary->IsKey(isolate, raw_key)) return kMaxUInt32; 1310 return FilterKey(dictionary, entry, raw_key, filter); 1311 } 1312 1313 static void CollectElementIndicesImpl(Handle<JSObject> object, 1314 Handle<FixedArrayBase> backing_store, 1315 KeyAccumulator* keys) { 1316 if (keys->filter() & SKIP_STRINGS) return; 1317 Isolate* isolate = keys->isolate(); 1318 Handle<SeededNumberDictionary> dictionary = 1319 Handle<SeededNumberDictionary>::cast(backing_store); 1320 int capacity = dictionary->Capacity(); 1321 Handle<FixedArray> elements = isolate->factory()->NewFixedArray( 1322 GetMaxNumberOfEntries(*object, *backing_store)); 1323 int insertion_index = 0; 1324 PropertyFilter filter = keys->filter(); 1325 for (int i = 0; i < capacity; i++) { 1326 uint32_t key = GetKeyForEntryImpl(isolate, dictionary, i, filter); 1327 if (key == kMaxUInt32) continue; 1328 Handle<Object> key_handle = isolate->factory()->NewNumberFromUint(key); 1329 elements->set(insertion_index, *key_handle); 1330 insertion_index++; 1331 } 1332 SortIndices(elements, insertion_index); 1333 for (int i = 0; i < insertion_index; i++) { 1334 keys->AddKey(elements->get(i)); 1335 } 1336 } 1337 1338 static Handle<FixedArray> DirectCollectElementIndicesImpl( 1339 Isolate* isolate, Handle<JSObject> object, 1340 Handle<FixedArrayBase> backing_store, GetKeysConversion convert, 1341 PropertyFilter filter, Handle<FixedArray> list, uint32_t* nof_indices, 1342 uint32_t insertion_index = 0) { 1343 if (filter & SKIP_STRINGS) return list; 1344 if (filter & ONLY_ALL_CAN_READ) return list; 1345 1346 Handle<SeededNumberDictionary> dictionary = 1347 Handle<SeededNumberDictionary>::cast(backing_store); 1348 uint32_t capacity = dictionary->Capacity(); 1349 for (uint32_t i = 0; i < capacity; i++) { 1350 uint32_t key = GetKeyForEntryImpl(isolate, dictionary, i, filter); 1351 if (key == kMaxUInt32) continue; 1352 Handle<Object> index = isolate->factory()->NewNumberFromUint(key); 1353 list->set(insertion_index, *index); 1354 insertion_index++; 1355 } 1356 *nof_indices = insertion_index; 1357 return list; 1358 } 1359 1360 static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver, 1361 KeyAccumulator* accumulator, 1362 AddKeyConversion convert) { 1363 Isolate* isolate = accumulator->isolate(); 1364 Handle<Object> undefined = isolate->factory()->undefined_value(); 1365 Handle<Object> the_hole = isolate->factory()->the_hole_value(); 1366 SeededNumberDictionary* dictionary = 1367 SeededNumberDictionary::cast(receiver->elements()); 1368 int capacity = dictionary->Capacity(); 1369 for (int i = 0; i < capacity; i++) { 1370 Object* k = dictionary->KeyAt(i); 1371 if (k == *undefined) continue; 1372 if (k == *the_hole) continue; 1373 if (dictionary->IsDeleted(i)) continue; 1374 Object* value = dictionary->ValueAt(i); 1375 DCHECK(!value->IsTheHole(isolate)); 1376 DCHECK(!value->IsAccessorPair()); 1377 DCHECK(!value->IsAccessorInfo()); 1378 accumulator->AddKey(value, convert); 1379 } 1380 } 1381 }; 1382 1383 1384 // Super class for all fast element arrays. 1385 template <typename Subclass, typename KindTraits> 1386 class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> { 1387 public: 1388 explicit FastElementsAccessor(const char* name) 1389 : ElementsAccessorBase<Subclass, KindTraits>(name) {} 1390 1391 typedef typename KindTraits::BackingStore BackingStore; 1392 1393 static Handle<SeededNumberDictionary> NormalizeImpl( 1394 Handle<JSObject> object, Handle<FixedArrayBase> store) { 1395 Isolate* isolate = store->GetIsolate(); 1396 ElementsKind kind = Subclass::kind(); 1397 1398 // Ensure that notifications fire if the array or object prototypes are 1399 // normalizing. 1400 if (IsFastSmiOrObjectElementsKind(kind)) { 1401 isolate->UpdateArrayProtectorOnNormalizeElements(object); 1402 } 1403 1404 int capacity = object->GetFastElementsUsage(); 1405 Handle<SeededNumberDictionary> dictionary = 1406 SeededNumberDictionary::New(isolate, capacity); 1407 1408 PropertyDetails details = PropertyDetails::Empty(); 1409 bool used_as_prototype = object->map()->is_prototype_map(); 1410 int j = 0; 1411 for (int i = 0; j < capacity; i++) { 1412 if (IsHoleyElementsKind(kind)) { 1413 if (BackingStore::cast(*store)->is_the_hole(i)) continue; 1414 } 1415 Handle<Object> value = Subclass::GetImpl(*store, i); 1416 dictionary = SeededNumberDictionary::AddNumberEntry( 1417 dictionary, i, value, details, used_as_prototype); 1418 j++; 1419 } 1420 return dictionary; 1421 } 1422 1423 static void DeleteAtEnd(Handle<JSObject> obj, 1424 Handle<BackingStore> backing_store, uint32_t entry) { 1425 uint32_t length = static_cast<uint32_t>(backing_store->length()); 1426 Heap* heap = obj->GetHeap(); 1427 for (; entry > 0; entry--) { 1428 if (!backing_store->is_the_hole(entry - 1)) break; 1429 } 1430 if (entry == 0) { 1431 FixedArray* empty = heap->empty_fixed_array(); 1432 // Dynamically ask for the elements kind here since we manually redirect 1433 // the operations for argument backing stores. 1434 if (obj->GetElementsKind() == FAST_SLOPPY_ARGUMENTS_ELEMENTS) { 1435 FixedArray::cast(obj->elements())->set(1, empty); 1436 } else { 1437 obj->set_elements(empty); 1438 } 1439 return; 1440 } 1441 1442 heap->RightTrimFixedArray<Heap::CONCURRENT_TO_SWEEPER>(*backing_store, 1443 length - entry); 1444 } 1445 1446 static void DeleteCommon(Handle<JSObject> obj, uint32_t entry, 1447 Handle<FixedArrayBase> store) { 1448 DCHECK(obj->HasFastSmiOrObjectElements() || obj->HasFastDoubleElements() || 1449 obj->HasFastArgumentsElements() || 1450 obj->HasFastStringWrapperElements()); 1451 Handle<BackingStore> backing_store = Handle<BackingStore>::cast(store); 1452 if (!obj->IsJSArray() && 1453 entry == static_cast<uint32_t>(store->length()) - 1) { 1454 DeleteAtEnd(obj, backing_store, entry); 1455 return; 1456 } 1457 1458 backing_store->set_the_hole(entry); 1459 1460 // TODO(verwaest): Move this out of elements.cc. 1461 // If an old space backing store is larger than a certain size and 1462 // has too few used values, normalize it. 1463 // To avoid doing the check on every delete we require at least 1464 // one adjacent hole to the value being deleted. 1465 const int kMinLengthForSparsenessCheck = 64; 1466 if (backing_store->length() < kMinLengthForSparsenessCheck) return; 1467 if (backing_store->GetHeap()->InNewSpace(*backing_store)) return; 1468 uint32_t length = 0; 1469 if (obj->IsJSArray()) { 1470 JSArray::cast(*obj)->length()->ToArrayLength(&length); 1471 } else { 1472 length = static_cast<uint32_t>(store->length()); 1473 } 1474 if ((entry > 0 && backing_store->is_the_hole(entry - 1)) || 1475 (entry + 1 < length && backing_store->is_the_hole(entry + 1))) { 1476 if (!obj->IsJSArray()) { 1477 uint32_t i; 1478 for (i = entry + 1; i < length; i++) { 1479 if (!backing_store->is_the_hole(i)) break; 1480 } 1481 if (i == length) { 1482 DeleteAtEnd(obj, backing_store, entry); 1483 return; 1484 } 1485 } 1486 int num_used = 0; 1487 for (int i = 0; i < backing_store->length(); ++i) { 1488 if (!backing_store->is_the_hole(i)) { 1489 ++num_used; 1490 // Bail out if a number dictionary wouldn't be able to save at least 1491 // 75% space. 1492 if (4 * SeededNumberDictionary::ComputeCapacity(num_used) * 1493 SeededNumberDictionary::kEntrySize > 1494 backing_store->length()) { 1495 return; 1496 } 1497 } 1498 } 1499 JSObject::NormalizeElements(obj); 1500 } 1501 } 1502 1503 static void ReconfigureImpl(Handle<JSObject> object, 1504 Handle<FixedArrayBase> store, uint32_t entry, 1505 Handle<Object> value, 1506 PropertyAttributes attributes) { 1507 Handle<SeededNumberDictionary> dictionary = 1508 JSObject::NormalizeElements(object); 1509 entry = dictionary->FindEntry(entry); 1510 DictionaryElementsAccessor::ReconfigureImpl(object, dictionary, entry, 1511 value, attributes); 1512 } 1513 1514 static void AddImpl(Handle<JSObject> object, uint32_t index, 1515 Handle<Object> value, PropertyAttributes attributes, 1516 uint32_t new_capacity) { 1517 DCHECK_EQ(NONE, attributes); 1518 ElementsKind from_kind = object->GetElementsKind(); 1519 ElementsKind to_kind = Subclass::kind(); 1520 if (IsDictionaryElementsKind(from_kind) || 1521 IsFastDoubleElementsKind(from_kind) != 1522 IsFastDoubleElementsKind(to_kind) || 1523 Subclass::GetCapacityImpl(*object, object->elements()) != 1524 new_capacity) { 1525 Subclass::GrowCapacityAndConvertImpl(object, new_capacity); 1526 } else { 1527 if (IsFastElementsKind(from_kind) && from_kind != to_kind) { 1528 JSObject::TransitionElementsKind(object, to_kind); 1529 } 1530 if (IsFastSmiOrObjectElementsKind(from_kind)) { 1531 DCHECK(IsFastSmiOrObjectElementsKind(to_kind)); 1532 JSObject::EnsureWritableFastElements(object); 1533 } 1534 } 1535 Subclass::SetImpl(object, index, *value); 1536 } 1537 1538 static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) { 1539 ElementsKind kind = KindTraits::Kind; 1540 if (IsFastPackedElementsKind(kind)) { 1541 JSObject::TransitionElementsKind(obj, GetHoleyElementsKind(kind)); 1542 } 1543 if (IsFastSmiOrObjectElementsKind(KindTraits::Kind)) { 1544 JSObject::EnsureWritableFastElements(obj); 1545 } 1546 DeleteCommon(obj, entry, handle(obj->elements())); 1547 } 1548 1549 static bool HasEntryImpl(FixedArrayBase* backing_store, uint32_t entry) { 1550 return !BackingStore::cast(backing_store)->is_the_hole(entry); 1551 } 1552 1553 static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver, 1554 KeyAccumulator* accumulator, 1555 AddKeyConversion convert) { 1556 Handle<FixedArrayBase> elements(receiver->elements(), 1557 accumulator->isolate()); 1558 uint32_t length = Subclass::GetMaxNumberOfEntries(*receiver, *elements); 1559 for (uint32_t i = 0; i < length; i++) { 1560 if (IsFastPackedElementsKind(KindTraits::Kind) || 1561 HasEntryImpl(*elements, i)) { 1562 accumulator->AddKey(Subclass::GetImpl(*elements, i), convert); 1563 } 1564 } 1565 } 1566 1567 static void ValidateContents(Handle<JSObject> holder, int length) { 1568 #if DEBUG 1569 Isolate* isolate = holder->GetIsolate(); 1570 Heap* heap = isolate->heap(); 1571 HandleScope scope(isolate); 1572 Handle<FixedArrayBase> elements(holder->elements(), isolate); 1573 Map* map = elements->map(); 1574 if (IsFastSmiOrObjectElementsKind(KindTraits::Kind)) { 1575 DCHECK_NE(map, heap->fixed_double_array_map()); 1576 } else if (IsFastDoubleElementsKind(KindTraits::Kind)) { 1577 DCHECK_NE(map, heap->fixed_cow_array_map()); 1578 if (map == heap->fixed_array_map()) DCHECK_EQ(0, length); 1579 } else { 1580 UNREACHABLE(); 1581 } 1582 if (length == 0) return; // nothing to do! 1583 #if ENABLE_SLOW_DCHECKS 1584 DisallowHeapAllocation no_gc; 1585 Handle<BackingStore> backing_store = Handle<BackingStore>::cast(elements); 1586 if (IsFastSmiElementsKind(KindTraits::Kind)) { 1587 for (int i = 0; i < length; i++) { 1588 DCHECK(BackingStore::get(*backing_store, i, isolate)->IsSmi() || 1589 (IsFastHoleyElementsKind(KindTraits::Kind) && 1590 backing_store->is_the_hole(i))); 1591 } 1592 } else if (KindTraits::Kind == FAST_ELEMENTS || 1593 KindTraits::Kind == FAST_DOUBLE_ELEMENTS) { 1594 for (int i = 0; i < length; i++) { 1595 DCHECK(!backing_store->is_the_hole(i)); 1596 } 1597 } else { 1598 DCHECK(IsFastHoleyElementsKind(KindTraits::Kind)); 1599 } 1600 #endif 1601 #endif 1602 } 1603 1604 static Handle<Object> PopImpl(Handle<JSArray> receiver) { 1605 return Subclass::RemoveElement(receiver, AT_END); 1606 } 1607 1608 static Handle<Object> ShiftImpl(Handle<JSArray> receiver) { 1609 return Subclass::RemoveElement(receiver, AT_START); 1610 } 1611 1612 static uint32_t PushImpl(Handle<JSArray> receiver, 1613 Arguments* args, uint32_t push_size) { 1614 Handle<FixedArrayBase> backing_store(receiver->elements()); 1615 return Subclass::AddArguments(receiver, backing_store, args, push_size, 1616 AT_END); 1617 } 1618 1619 static uint32_t UnshiftImpl(Handle<JSArray> receiver, 1620 Arguments* args, uint32_t unshift_size) { 1621 Handle<FixedArrayBase> backing_store(receiver->elements()); 1622 return Subclass::AddArguments(receiver, backing_store, args, unshift_size, 1623 AT_START); 1624 } 1625 1626 static Handle<JSArray> SliceImpl(Handle<JSObject> receiver, 1627 uint32_t start, uint32_t end) { 1628 Isolate* isolate = receiver->GetIsolate(); 1629 Handle<FixedArrayBase> backing_store(receiver->elements(), isolate); 1630 int result_len = end < start ? 0u : end - start; 1631 Handle<JSArray> result_array = isolate->factory()->NewJSArray( 1632 KindTraits::Kind, result_len, result_len); 1633 DisallowHeapAllocation no_gc; 1634 Subclass::CopyElementsImpl(*backing_store, start, result_array->elements(), 1635 KindTraits::Kind, 0, kPackedSizeNotKnown, 1636 result_len); 1637 Subclass::TryTransitionResultArrayToPacked(result_array); 1638 return result_array; 1639 } 1640 1641 static Handle<JSArray> SpliceImpl(Handle<JSArray> receiver, 1642 uint32_t start, uint32_t delete_count, 1643 Arguments* args, uint32_t add_count) { 1644 Isolate* isolate = receiver->GetIsolate(); 1645 Heap* heap = isolate->heap(); 1646 uint32_t length = Smi::cast(receiver->length())->value(); 1647 uint32_t new_length = length - delete_count + add_count; 1648 1649 ElementsKind kind = KindTraits::Kind; 1650 if (new_length <= static_cast<uint32_t>(receiver->elements()->length()) && 1651 IsFastSmiOrObjectElementsKind(kind)) { 1652 HandleScope scope(isolate); 1653 JSObject::EnsureWritableFastElements(receiver); 1654 } 1655 1656 Handle<FixedArrayBase> backing_store(receiver->elements(), isolate); 1657 1658 if (new_length == 0) { 1659 receiver->set_elements(heap->empty_fixed_array()); 1660 receiver->set_length(Smi::FromInt(0)); 1661 return isolate->factory()->NewJSArrayWithElements( 1662 backing_store, KindTraits::Kind, delete_count); 1663 } 1664 1665 // Construct the result array which holds the deleted elements. 1666 Handle<JSArray> deleted_elements = isolate->factory()->NewJSArray( 1667 KindTraits::Kind, delete_count, delete_count); 1668 if (delete_count > 0) { 1669 DisallowHeapAllocation no_gc; 1670 Subclass::CopyElementsImpl(*backing_store, start, 1671 deleted_elements->elements(), KindTraits::Kind, 1672 0, kPackedSizeNotKnown, delete_count); 1673 } 1674 1675 // Delete and move elements to make space for add_count new elements. 1676 if (add_count < delete_count) { 1677 Subclass::SpliceShrinkStep(isolate, receiver, backing_store, start, 1678 delete_count, add_count, length, new_length); 1679 } else if (add_count > delete_count) { 1680 backing_store = 1681 Subclass::SpliceGrowStep(isolate, receiver, backing_store, start, 1682 delete_count, add_count, length, new_length); 1683 } 1684 1685 // Copy over the arguments. 1686 Subclass::CopyArguments(args, backing_store, add_count, 3, start); 1687 1688 receiver->set_length(Smi::FromInt(new_length)); 1689 Subclass::TryTransitionResultArrayToPacked(deleted_elements); 1690 return deleted_elements; 1691 } 1692 1693 static Maybe<bool> CollectValuesOrEntriesImpl( 1694 Isolate* isolate, Handle<JSObject> object, 1695 Handle<FixedArray> values_or_entries, bool get_entries, int* nof_items, 1696 PropertyFilter filter) { 1697 int count = 0; 1698 uint32_t length = object->elements()->length(); 1699 for (uint32_t index = 0; index < length; ++index) { 1700 if (!HasEntryImpl(object->elements(), index)) continue; 1701 Handle<Object> value = Subclass::GetImpl(object->elements(), index); 1702 if (get_entries) { 1703 value = MakeEntryPair(isolate, index, value); 1704 } 1705 values_or_entries->set(count++, *value); 1706 } 1707 *nof_items = count; 1708 return Just(true); 1709 } 1710 1711 static void MoveElements(Isolate* isolate, Handle<JSArray> receiver, 1712 Handle<FixedArrayBase> backing_store, int dst_index, 1713 int src_index, int len, int hole_start, 1714 int hole_end) { 1715 Heap* heap = isolate->heap(); 1716 Handle<BackingStore> dst_elms = Handle<BackingStore>::cast(backing_store); 1717 if (heap->CanMoveObjectStart(*dst_elms) && dst_index == 0) { 1718 // Update all the copies of this backing_store handle. 1719 *dst_elms.location() = 1720 BackingStore::cast(heap->LeftTrimFixedArray(*dst_elms, src_index)); 1721 receiver->set_elements(*dst_elms); 1722 // Adjust the hole offset as the array has been shrunk. 1723 hole_end -= src_index; 1724 DCHECK_LE(hole_start, backing_store->length()); 1725 DCHECK_LE(hole_end, backing_store->length()); 1726 } else if (len != 0) { 1727 if (IsFastDoubleElementsKind(KindTraits::Kind)) { 1728 MemMove(dst_elms->data_start() + dst_index, 1729 dst_elms->data_start() + src_index, len * kDoubleSize); 1730 } else { 1731 DisallowHeapAllocation no_gc; 1732 heap->MoveElements(FixedArray::cast(*dst_elms), dst_index, src_index, 1733 len); 1734 } 1735 } 1736 if (hole_start != hole_end) { 1737 dst_elms->FillWithHoles(hole_start, hole_end); 1738 } 1739 } 1740 1741 private: 1742 // SpliceShrinkStep might modify the backing_store. 1743 static void SpliceShrinkStep(Isolate* isolate, Handle<JSArray> receiver, 1744 Handle<FixedArrayBase> backing_store, 1745 uint32_t start, uint32_t delete_count, 1746 uint32_t add_count, uint32_t len, 1747 uint32_t new_length) { 1748 const int move_left_count = len - delete_count - start; 1749 const int move_left_dst_index = start + add_count; 1750 Subclass::MoveElements(isolate, receiver, backing_store, 1751 move_left_dst_index, start + delete_count, 1752 move_left_count, new_length, len); 1753 } 1754 1755 // SpliceGrowStep might modify the backing_store. 1756 static Handle<FixedArrayBase> SpliceGrowStep( 1757 Isolate* isolate, Handle<JSArray> receiver, 1758 Handle<FixedArrayBase> backing_store, uint32_t start, 1759 uint32_t delete_count, uint32_t add_count, uint32_t length, 1760 uint32_t new_length) { 1761 // Check we do not overflow the new_length. 1762 DCHECK((add_count - delete_count) <= (Smi::kMaxValue - length)); 1763 // Check if backing_store is big enough. 1764 if (new_length <= static_cast<uint32_t>(backing_store->length())) { 1765 Subclass::MoveElements(isolate, receiver, backing_store, 1766 start + add_count, start + delete_count, 1767 (length - delete_count - start), 0, 0); 1768 // MoveElements updates the backing_store in-place. 1769 return backing_store; 1770 } 1771 // New backing storage is needed. 1772 int capacity = JSObject::NewElementsCapacity(new_length); 1773 // Partially copy all elements up to start. 1774 Handle<FixedArrayBase> new_elms = Subclass::ConvertElementsWithCapacity( 1775 receiver, backing_store, KindTraits::Kind, capacity, start); 1776 // Copy the trailing elements after start + delete_count 1777 Subclass::CopyElementsImpl(*backing_store, start + delete_count, *new_elms, 1778 KindTraits::Kind, start + add_count, 1779 kPackedSizeNotKnown, 1780 ElementsAccessor::kCopyToEndAndInitializeToHole); 1781 receiver->set_elements(*new_elms); 1782 return new_elms; 1783 } 1784 1785 static Handle<Object> RemoveElement(Handle<JSArray> receiver, 1786 Where remove_position) { 1787 Isolate* isolate = receiver->GetIsolate(); 1788 ElementsKind kind = KindTraits::Kind; 1789 if (IsFastSmiOrObjectElementsKind(kind)) { 1790 HandleScope scope(isolate); 1791 JSObject::EnsureWritableFastElements(receiver); 1792 } 1793 Handle<FixedArrayBase> backing_store(receiver->elements(), isolate); 1794 uint32_t length = 1795 static_cast<uint32_t>(Smi::cast(receiver->length())->value()); 1796 DCHECK(length > 0); 1797 int new_length = length - 1; 1798 int remove_index = remove_position == AT_START ? 0 : new_length; 1799 Handle<Object> result = Subclass::GetImpl(*backing_store, remove_index); 1800 if (remove_position == AT_START) { 1801 Subclass::MoveElements(isolate, receiver, backing_store, 0, 1, new_length, 1802 0, 0); 1803 } 1804 Subclass::SetLengthImpl(isolate, receiver, new_length, backing_store); 1805 1806 if (IsHoleyElementsKind(kind) && result->IsTheHole(isolate)) { 1807 return isolate->factory()->undefined_value(); 1808 } 1809 return result; 1810 } 1811 1812 static uint32_t AddArguments(Handle<JSArray> receiver, 1813 Handle<FixedArrayBase> backing_store, 1814 Arguments* args, uint32_t add_size, 1815 Where add_position) { 1816 uint32_t length = Smi::cast(receiver->length())->value(); 1817 DCHECK(0 < add_size); 1818 uint32_t elms_len = backing_store->length(); 1819 // Check we do not overflow the new_length. 1820 DCHECK(add_size <= static_cast<uint32_t>(Smi::kMaxValue - length)); 1821 uint32_t new_length = length + add_size; 1822 1823 if (new_length > elms_len) { 1824 // New backing storage is needed. 1825 uint32_t capacity = JSObject::NewElementsCapacity(new_length); 1826 // If we add arguments to the start we have to shift the existing objects. 1827 int copy_dst_index = add_position == AT_START ? add_size : 0; 1828 // Copy over all objects to a new backing_store. 1829 backing_store = Subclass::ConvertElementsWithCapacity( 1830 receiver, backing_store, KindTraits::Kind, capacity, 0, 1831 copy_dst_index, ElementsAccessor::kCopyToEndAndInitializeToHole); 1832 receiver->set_elements(*backing_store); 1833 } else if (add_position == AT_START) { 1834 // If the backing store has enough capacity and we add elements to the 1835 // start we have to shift the existing objects. 1836 Isolate* isolate = receiver->GetIsolate(); 1837 Subclass::MoveElements(isolate, receiver, backing_store, add_size, 0, 1838 length, 0, 0); 1839 } 1840 1841 int insertion_index = add_position == AT_START ? 0 : length; 1842 // Copy the arguments to the start. 1843 Subclass::CopyArguments(args, backing_store, add_size, 1, insertion_index); 1844 // Set the length. 1845 receiver->set_length(Smi::FromInt(new_length)); 1846 return new_length; 1847 } 1848 1849 static void CopyArguments(Arguments* args, Handle<FixedArrayBase> dst_store, 1850 uint32_t copy_size, uint32_t src_index, 1851 uint32_t dst_index) { 1852 // Add the provided values. 1853 DisallowHeapAllocation no_gc; 1854 FixedArrayBase* raw_backing_store = *dst_store; 1855 WriteBarrierMode mode = raw_backing_store->GetWriteBarrierMode(no_gc); 1856 for (uint32_t i = 0; i < copy_size; i++) { 1857 Object* argument = (*args)[src_index + i]; 1858 DCHECK(!argument->IsTheHole(raw_backing_store->GetIsolate())); 1859 Subclass::SetImpl(raw_backing_store, dst_index + i, argument, mode); 1860 } 1861 } 1862 }; 1863 1864 template <typename Subclass, typename KindTraits> 1865 class FastSmiOrObjectElementsAccessor 1866 : public FastElementsAccessor<Subclass, KindTraits> { 1867 public: 1868 explicit FastSmiOrObjectElementsAccessor(const char* name) 1869 : FastElementsAccessor<Subclass, KindTraits>(name) {} 1870 1871 static inline void SetImpl(Handle<JSObject> holder, uint32_t entry, 1872 Object* value) { 1873 SetImpl(holder->elements(), entry, value); 1874 } 1875 1876 static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry, 1877 Object* value) { 1878 FixedArray::cast(backing_store)->set(entry, value); 1879 } 1880 1881 static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry, 1882 Object* value, WriteBarrierMode mode) { 1883 FixedArray::cast(backing_store)->set(entry, value, mode); 1884 } 1885 1886 static Object* GetRaw(FixedArray* backing_store, uint32_t entry) { 1887 uint32_t index = Subclass::GetIndexForEntryImpl(backing_store, entry); 1888 return backing_store->get(index); 1889 } 1890 1891 1892 // NOTE: this method violates the handlified function signature convention: 1893 // raw pointer parameters in the function that allocates. 1894 // See ElementsAccessor::CopyElements() for details. 1895 // This method could actually allocate if copying from double elements to 1896 // object elements. 1897 static void CopyElementsImpl(FixedArrayBase* from, uint32_t from_start, 1898 FixedArrayBase* to, ElementsKind from_kind, 1899 uint32_t to_start, int packed_size, 1900 int copy_size) { 1901 DisallowHeapAllocation no_gc; 1902 ElementsKind to_kind = KindTraits::Kind; 1903 switch (from_kind) { 1904 case FAST_SMI_ELEMENTS: 1905 case FAST_HOLEY_SMI_ELEMENTS: 1906 case FAST_ELEMENTS: 1907 case FAST_HOLEY_ELEMENTS: 1908 CopyObjectToObjectElements(from, from_kind, from_start, to, to_kind, 1909 to_start, copy_size); 1910 break; 1911 case FAST_DOUBLE_ELEMENTS: 1912 case FAST_HOLEY_DOUBLE_ELEMENTS: { 1913 AllowHeapAllocation allow_allocation; 1914 DCHECK(IsFastObjectElementsKind(to_kind)); 1915 CopyDoubleToObjectElements(from, from_start, to, to_start, copy_size); 1916 break; 1917 } 1918 case DICTIONARY_ELEMENTS: 1919 CopyDictionaryToObjectElements(from, from_start, to, to_kind, to_start, 1920 copy_size); 1921 break; 1922 case FAST_SLOPPY_ARGUMENTS_ELEMENTS: 1923 case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: 1924 case FAST_STRING_WRAPPER_ELEMENTS: 1925 case SLOW_STRING_WRAPPER_ELEMENTS: 1926 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) case TYPE##_ELEMENTS: 1927 TYPED_ARRAYS(TYPED_ARRAY_CASE) 1928 #undef TYPED_ARRAY_CASE 1929 // This function is currently only used for JSArrays with non-zero 1930 // length. 1931 UNREACHABLE(); 1932 break; 1933 case NO_ELEMENTS: 1934 break; // Nothing to do. 1935 } 1936 } 1937 }; 1938 1939 1940 class FastPackedSmiElementsAccessor 1941 : public FastSmiOrObjectElementsAccessor< 1942 FastPackedSmiElementsAccessor, 1943 ElementsKindTraits<FAST_SMI_ELEMENTS> > { 1944 public: 1945 explicit FastPackedSmiElementsAccessor(const char* name) 1946 : FastSmiOrObjectElementsAccessor< 1947 FastPackedSmiElementsAccessor, 1948 ElementsKindTraits<FAST_SMI_ELEMENTS> >(name) {} 1949 }; 1950 1951 1952 class FastHoleySmiElementsAccessor 1953 : public FastSmiOrObjectElementsAccessor< 1954 FastHoleySmiElementsAccessor, 1955 ElementsKindTraits<FAST_HOLEY_SMI_ELEMENTS> > { 1956 public: 1957 explicit FastHoleySmiElementsAccessor(const char* name) 1958 : FastSmiOrObjectElementsAccessor< 1959 FastHoleySmiElementsAccessor, 1960 ElementsKindTraits<FAST_HOLEY_SMI_ELEMENTS> >(name) {} 1961 }; 1962 1963 1964 class FastPackedObjectElementsAccessor 1965 : public FastSmiOrObjectElementsAccessor< 1966 FastPackedObjectElementsAccessor, 1967 ElementsKindTraits<FAST_ELEMENTS> > { 1968 public: 1969 explicit FastPackedObjectElementsAccessor(const char* name) 1970 : FastSmiOrObjectElementsAccessor< 1971 FastPackedObjectElementsAccessor, 1972 ElementsKindTraits<FAST_ELEMENTS> >(name) {} 1973 }; 1974 1975 1976 class FastHoleyObjectElementsAccessor 1977 : public FastSmiOrObjectElementsAccessor< 1978 FastHoleyObjectElementsAccessor, 1979 ElementsKindTraits<FAST_HOLEY_ELEMENTS> > { 1980 public: 1981 explicit FastHoleyObjectElementsAccessor(const char* name) 1982 : FastSmiOrObjectElementsAccessor< 1983 FastHoleyObjectElementsAccessor, 1984 ElementsKindTraits<FAST_HOLEY_ELEMENTS> >(name) {} 1985 }; 1986 1987 template <typename Subclass, typename KindTraits> 1988 class FastDoubleElementsAccessor 1989 : public FastElementsAccessor<Subclass, KindTraits> { 1990 public: 1991 explicit FastDoubleElementsAccessor(const char* name) 1992 : FastElementsAccessor<Subclass, KindTraits>(name) {} 1993 1994 static Handle<Object> GetImpl(Handle<JSObject> holder, uint32_t entry) { 1995 return GetImpl(holder->elements(), entry); 1996 } 1997 1998 static Handle<Object> GetImpl(FixedArrayBase* backing_store, uint32_t entry) { 1999 Isolate* isolate = backing_store->GetIsolate(); 2000 return FixedDoubleArray::get(FixedDoubleArray::cast(backing_store), entry, 2001 isolate); 2002 } 2003 2004 static inline void SetImpl(Handle<JSObject> holder, uint32_t entry, 2005 Object* value) { 2006 SetImpl(holder->elements(), entry, value); 2007 } 2008 2009 static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry, 2010 Object* value) { 2011 FixedDoubleArray::cast(backing_store)->set(entry, value->Number()); 2012 } 2013 2014 static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry, 2015 Object* value, WriteBarrierMode mode) { 2016 FixedDoubleArray::cast(backing_store)->set(entry, value->Number()); 2017 } 2018 2019 static void CopyElementsImpl(FixedArrayBase* from, uint32_t from_start, 2020 FixedArrayBase* to, ElementsKind from_kind, 2021 uint32_t to_start, int packed_size, 2022 int copy_size) { 2023 DisallowHeapAllocation no_allocation; 2024 switch (from_kind) { 2025 case FAST_SMI_ELEMENTS: 2026 CopyPackedSmiToDoubleElements(from, from_start, to, to_start, 2027 packed_size, copy_size); 2028 break; 2029 case FAST_HOLEY_SMI_ELEMENTS: 2030 CopySmiToDoubleElements(from, from_start, to, to_start, copy_size); 2031 break; 2032 case FAST_DOUBLE_ELEMENTS: 2033 case FAST_HOLEY_DOUBLE_ELEMENTS: 2034 CopyDoubleToDoubleElements(from, from_start, to, to_start, copy_size); 2035 break; 2036 case FAST_ELEMENTS: 2037 case FAST_HOLEY_ELEMENTS: 2038 CopyObjectToDoubleElements(from, from_start, to, to_start, copy_size); 2039 break; 2040 case DICTIONARY_ELEMENTS: 2041 CopyDictionaryToDoubleElements(from, from_start, to, to_start, 2042 copy_size); 2043 break; 2044 case FAST_SLOPPY_ARGUMENTS_ELEMENTS: 2045 case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: 2046 case FAST_STRING_WRAPPER_ELEMENTS: 2047 case SLOW_STRING_WRAPPER_ELEMENTS: 2048 case NO_ELEMENTS: 2049 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) case TYPE##_ELEMENTS: 2050 TYPED_ARRAYS(TYPED_ARRAY_CASE) 2051 #undef TYPED_ARRAY_CASE 2052 // This function is currently only used for JSArrays with non-zero 2053 // length. 2054 UNREACHABLE(); 2055 break; 2056 } 2057 } 2058 }; 2059 2060 2061 class FastPackedDoubleElementsAccessor 2062 : public FastDoubleElementsAccessor< 2063 FastPackedDoubleElementsAccessor, 2064 ElementsKindTraits<FAST_DOUBLE_ELEMENTS> > { 2065 public: 2066 explicit FastPackedDoubleElementsAccessor(const char* name) 2067 : FastDoubleElementsAccessor< 2068 FastPackedDoubleElementsAccessor, 2069 ElementsKindTraits<FAST_DOUBLE_ELEMENTS> >(name) {} 2070 }; 2071 2072 2073 class FastHoleyDoubleElementsAccessor 2074 : public FastDoubleElementsAccessor< 2075 FastHoleyDoubleElementsAccessor, 2076 ElementsKindTraits<FAST_HOLEY_DOUBLE_ELEMENTS> > { 2077 public: 2078 explicit FastHoleyDoubleElementsAccessor(const char* name) 2079 : FastDoubleElementsAccessor< 2080 FastHoleyDoubleElementsAccessor, 2081 ElementsKindTraits<FAST_HOLEY_DOUBLE_ELEMENTS> >(name) {} 2082 }; 2083 2084 2085 // Super class for all external element arrays. 2086 template<ElementsKind Kind> 2087 class TypedElementsAccessor 2088 : public ElementsAccessorBase<TypedElementsAccessor<Kind>, 2089 ElementsKindTraits<Kind> > { 2090 public: 2091 explicit TypedElementsAccessor(const char* name) 2092 : ElementsAccessorBase<AccessorClass, 2093 ElementsKindTraits<Kind> >(name) {} 2094 2095 typedef typename ElementsKindTraits<Kind>::BackingStore BackingStore; 2096 typedef TypedElementsAccessor<Kind> AccessorClass; 2097 2098 static inline void SetImpl(Handle<JSObject> holder, uint32_t entry, 2099 Object* value) { 2100 SetImpl(holder->elements(), entry, value); 2101 } 2102 2103 static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry, 2104 Object* value) { 2105 BackingStore::cast(backing_store)->SetValue(entry, value); 2106 } 2107 2108 static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry, 2109 Object* value, WriteBarrierMode mode) { 2110 BackingStore::cast(backing_store)->SetValue(entry, value); 2111 } 2112 2113 static Handle<Object> GetImpl(Handle<JSObject> holder, uint32_t entry) { 2114 return GetImpl(holder->elements(), entry); 2115 } 2116 2117 static Handle<Object> GetImpl(FixedArrayBase* backing_store, uint32_t entry) { 2118 return BackingStore::get(BackingStore::cast(backing_store), entry); 2119 } 2120 2121 static PropertyDetails GetDetailsImpl(JSObject* holder, uint32_t entry) { 2122 return PropertyDetails(DONT_DELETE, DATA, 0, PropertyCellType::kNoCell); 2123 } 2124 2125 static PropertyDetails GetDetailsImpl(FixedArrayBase* backing_store, 2126 uint32_t entry) { 2127 return PropertyDetails(DONT_DELETE, DATA, 0, PropertyCellType::kNoCell); 2128 } 2129 2130 static bool HasElementImpl(Handle<JSObject> holder, uint32_t index, 2131 Handle<FixedArrayBase> backing_store, 2132 PropertyFilter filter) { 2133 return index < AccessorClass::GetCapacityImpl(*holder, *backing_store); 2134 } 2135 2136 static bool HasAccessorsImpl(JSObject* holder, 2137 FixedArrayBase* backing_store) { 2138 return false; 2139 } 2140 2141 static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array, 2142 uint32_t length, 2143 Handle<FixedArrayBase> backing_store) { 2144 // External arrays do not support changing their length. 2145 UNREACHABLE(); 2146 } 2147 2148 static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) { 2149 UNREACHABLE(); 2150 } 2151 2152 static uint32_t GetIndexForEntryImpl(FixedArrayBase* backing_store, 2153 uint32_t entry) { 2154 return entry; 2155 } 2156 2157 static uint32_t GetEntryForIndexImpl(JSObject* holder, 2158 FixedArrayBase* backing_store, 2159 uint32_t index, PropertyFilter filter) { 2160 return index < AccessorClass::GetCapacityImpl(holder, backing_store) 2161 ? index 2162 : kMaxUInt32; 2163 } 2164 2165 static uint32_t GetCapacityImpl(JSObject* holder, 2166 FixedArrayBase* backing_store) { 2167 JSArrayBufferView* view = JSArrayBufferView::cast(holder); 2168 if (view->WasNeutered()) return 0; 2169 return backing_store->length(); 2170 } 2171 2172 static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver, 2173 KeyAccumulator* accumulator, 2174 AddKeyConversion convert) { 2175 Handle<FixedArrayBase> elements(receiver->elements()); 2176 uint32_t length = AccessorClass::GetCapacityImpl(*receiver, *elements); 2177 for (uint32_t i = 0; i < length; i++) { 2178 Handle<Object> value = AccessorClass::GetImpl(*elements, i); 2179 accumulator->AddKey(value, convert); 2180 } 2181 } 2182 2183 static Maybe<bool> CollectValuesOrEntriesImpl( 2184 Isolate* isolate, Handle<JSObject> object, 2185 Handle<FixedArray> values_or_entries, bool get_entries, int* nof_items, 2186 PropertyFilter filter) { 2187 int count = 0; 2188 if ((filter & ONLY_CONFIGURABLE) == 0) { 2189 Handle<FixedArrayBase> elements(object->elements()); 2190 uint32_t length = AccessorClass::GetCapacityImpl(*object, *elements); 2191 for (uint32_t index = 0; index < length; ++index) { 2192 Handle<Object> value = AccessorClass::GetImpl(*elements, index); 2193 if (get_entries) { 2194 value = MakeEntryPair(isolate, index, value); 2195 } 2196 values_or_entries->set(count++, *value); 2197 } 2198 } 2199 *nof_items = count; 2200 return Just(true); 2201 } 2202 }; 2203 2204 2205 2206 #define FIXED_ELEMENTS_ACCESSOR(Type, type, TYPE, ctype, size) \ 2207 typedef TypedElementsAccessor<TYPE##_ELEMENTS > \ 2208 Fixed##Type##ElementsAccessor; 2209 2210 TYPED_ARRAYS(FIXED_ELEMENTS_ACCESSOR) 2211 #undef FIXED_ELEMENTS_ACCESSOR 2212 2213 template <typename Subclass, typename ArgumentsAccessor, typename KindTraits> 2214 class SloppyArgumentsElementsAccessor 2215 : public ElementsAccessorBase<Subclass, KindTraits> { 2216 public: 2217 explicit SloppyArgumentsElementsAccessor(const char* name) 2218 : ElementsAccessorBase<Subclass, KindTraits>(name) { 2219 USE(KindTraits::Kind); 2220 } 2221 2222 static Handle<Object> GetImpl(Handle<JSObject> holder, uint32_t entry) { 2223 return GetImpl(holder->elements(), entry); 2224 } 2225 2226 static Handle<Object> GetImpl(FixedArrayBase* parameters, uint32_t entry) { 2227 Isolate* isolate = parameters->GetIsolate(); 2228 Handle<FixedArray> parameter_map(FixedArray::cast(parameters), isolate); 2229 uint32_t length = parameter_map->length() - 2; 2230 if (entry < length) { 2231 DisallowHeapAllocation no_gc; 2232 Object* probe = parameter_map->get(entry + 2); 2233 Context* context = Context::cast(parameter_map->get(0)); 2234 int context_entry = Smi::cast(probe)->value(); 2235 DCHECK(!context->get(context_entry)->IsTheHole(isolate)); 2236 return handle(context->get(context_entry), isolate); 2237 } else { 2238 // Object is not mapped, defer to the arguments. 2239 Handle<Object> result = ArgumentsAccessor::GetImpl( 2240 FixedArray::cast(parameter_map->get(1)), entry - length); 2241 // Elements of the arguments object in slow mode might be slow aliases. 2242 if (result->IsAliasedArgumentsEntry()) { 2243 DisallowHeapAllocation no_gc; 2244 AliasedArgumentsEntry* alias = AliasedArgumentsEntry::cast(*result); 2245 Context* context = Context::cast(parameter_map->get(0)); 2246 int context_entry = alias->aliased_context_slot(); 2247 DCHECK(!context->get(context_entry)->IsTheHole(isolate)); 2248 return handle(context->get(context_entry), isolate); 2249 } 2250 return result; 2251 } 2252 } 2253 2254 static void GrowCapacityAndConvertImpl(Handle<JSObject> object, 2255 uint32_t capacity) { 2256 UNREACHABLE(); 2257 } 2258 2259 static inline void SetImpl(Handle<JSObject> holder, uint32_t entry, 2260 Object* value) { 2261 SetImpl(holder->elements(), entry, value); 2262 } 2263 2264 static inline void SetImpl(FixedArrayBase* store, uint32_t entry, 2265 Object* value) { 2266 FixedArray* parameter_map = FixedArray::cast(store); 2267 uint32_t length = parameter_map->length() - 2; 2268 if (entry < length) { 2269 Object* probe = parameter_map->get(entry + 2); 2270 Context* context = Context::cast(parameter_map->get(0)); 2271 int context_entry = Smi::cast(probe)->value(); 2272 DCHECK(!context->get(context_entry)->IsTheHole(store->GetIsolate())); 2273 context->set(context_entry, value); 2274 } else { 2275 FixedArray* arguments = FixedArray::cast(parameter_map->get(1)); 2276 Object* current = ArgumentsAccessor::GetRaw(arguments, entry - length); 2277 if (current->IsAliasedArgumentsEntry()) { 2278 AliasedArgumentsEntry* alias = AliasedArgumentsEntry::cast(current); 2279 Context* context = Context::cast(parameter_map->get(0)); 2280 int context_entry = alias->aliased_context_slot(); 2281 DCHECK(!context->get(context_entry)->IsTheHole(store->GetIsolate())); 2282 context->set(context_entry, value); 2283 } else { 2284 ArgumentsAccessor::SetImpl(arguments, entry - length, value); 2285 } 2286 } 2287 } 2288 2289 static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array, 2290 uint32_t length, 2291 Handle<FixedArrayBase> parameter_map) { 2292 // Sloppy arguments objects are not arrays. 2293 UNREACHABLE(); 2294 } 2295 2296 static uint32_t GetCapacityImpl(JSObject* holder, 2297 FixedArrayBase* backing_store) { 2298 FixedArray* parameter_map = FixedArray::cast(backing_store); 2299 FixedArrayBase* arguments = FixedArrayBase::cast(parameter_map->get(1)); 2300 return parameter_map->length() - 2 + 2301 ArgumentsAccessor::GetCapacityImpl(holder, arguments); 2302 } 2303 2304 static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver, 2305 KeyAccumulator* accumulator, 2306 AddKeyConversion convert) { 2307 FixedArrayBase* elements = receiver->elements(); 2308 uint32_t length = GetCapacityImpl(*receiver, elements); 2309 for (uint32_t entry = 0; entry < length; entry++) { 2310 if (!HasEntryImpl(elements, entry)) continue; 2311 Handle<Object> value = GetImpl(elements, entry); 2312 accumulator->AddKey(value, convert); 2313 } 2314 } 2315 2316 static bool HasEntryImpl(FixedArrayBase* parameters, uint32_t entry) { 2317 FixedArray* parameter_map = FixedArray::cast(parameters); 2318 uint32_t length = parameter_map->length() - 2; 2319 if (entry < length) { 2320 return !GetParameterMapArg(parameter_map, entry) 2321 ->IsTheHole(parameter_map->GetIsolate()); 2322 } 2323 2324 FixedArrayBase* arguments = FixedArrayBase::cast(parameter_map->get(1)); 2325 return ArgumentsAccessor::HasEntryImpl(arguments, entry - length); 2326 } 2327 2328 static bool HasAccessorsImpl(JSObject* holder, 2329 FixedArrayBase* backing_store) { 2330 FixedArray* parameter_map = FixedArray::cast(backing_store); 2331 FixedArrayBase* arguments = FixedArrayBase::cast(parameter_map->get(1)); 2332 return ArgumentsAccessor::HasAccessorsImpl(holder, arguments); 2333 } 2334 2335 static uint32_t GetIndexForEntryImpl(FixedArrayBase* parameters, 2336 uint32_t entry) { 2337 FixedArray* parameter_map = FixedArray::cast(parameters); 2338 uint32_t length = parameter_map->length() - 2; 2339 if (entry < length) return entry; 2340 2341 FixedArray* arguments = FixedArray::cast(parameter_map->get(1)); 2342 return ArgumentsAccessor::GetIndexForEntryImpl(arguments, entry - length); 2343 } 2344 2345 static uint32_t GetEntryForIndexImpl(JSObject* holder, 2346 FixedArrayBase* parameters, 2347 uint32_t index, PropertyFilter filter) { 2348 FixedArray* parameter_map = FixedArray::cast(parameters); 2349 Object* probe = GetParameterMapArg(parameter_map, index); 2350 if (!probe->IsTheHole(holder->GetIsolate())) return index; 2351 2352 FixedArray* arguments = FixedArray::cast(parameter_map->get(1)); 2353 uint32_t entry = ArgumentsAccessor::GetEntryForIndexImpl(holder, arguments, 2354 index, filter); 2355 if (entry == kMaxUInt32) return kMaxUInt32; 2356 return (parameter_map->length() - 2) + entry; 2357 } 2358 2359 static PropertyDetails GetDetailsImpl(JSObject* holder, uint32_t entry) { 2360 FixedArray* parameter_map = FixedArray::cast(holder->elements()); 2361 uint32_t length = parameter_map->length() - 2; 2362 if (entry < length) { 2363 return PropertyDetails(NONE, DATA, 0, PropertyCellType::kNoCell); 2364 } 2365 FixedArray* arguments = FixedArray::cast(parameter_map->get(1)); 2366 return ArgumentsAccessor::GetDetailsImpl(arguments, entry - length); 2367 } 2368 2369 static Object* GetParameterMapArg(FixedArray* parameter_map, uint32_t index) { 2370 uint32_t length = parameter_map->length() - 2; 2371 return index < length 2372 ? parameter_map->get(index + 2) 2373 : Object::cast(parameter_map->GetHeap()->the_hole_value()); 2374 } 2375 2376 static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) { 2377 FixedArray* parameter_map = FixedArray::cast(obj->elements()); 2378 uint32_t length = static_cast<uint32_t>(parameter_map->length()) - 2; 2379 if (entry < length) { 2380 // TODO(kmillikin): We could check if this was the last aliased 2381 // parameter, and revert to normal elements in that case. That 2382 // would enable GC of the context. 2383 parameter_map->set_the_hole(entry + 2); 2384 } else { 2385 Subclass::DeleteFromArguments(obj, entry - length); 2386 } 2387 } 2388 2389 static void CollectElementIndicesImpl(Handle<JSObject> object, 2390 Handle<FixedArrayBase> backing_store, 2391 KeyAccumulator* keys) { 2392 Isolate* isolate = keys->isolate(); 2393 uint32_t nof_indices = 0; 2394 Handle<FixedArray> indices = isolate->factory()->NewFixedArray( 2395 GetCapacityImpl(*object, *backing_store)); 2396 DirectCollectElementIndicesImpl(isolate, object, backing_store, 2397 GetKeysConversion::kKeepNumbers, 2398 ENUMERABLE_STRINGS, indices, &nof_indices); 2399 SortIndices(indices, nof_indices); 2400 for (uint32_t i = 0; i < nof_indices; i++) { 2401 keys->AddKey(indices->get(i)); 2402 } 2403 } 2404 2405 static Handle<FixedArray> DirectCollectElementIndicesImpl( 2406 Isolate* isolate, Handle<JSObject> object, 2407 Handle<FixedArrayBase> backing_store, GetKeysConversion convert, 2408 PropertyFilter filter, Handle<FixedArray> list, uint32_t* nof_indices, 2409 uint32_t insertion_index = 0) { 2410 FixedArray* parameter_map = FixedArray::cast(*backing_store); 2411 uint32_t length = parameter_map->length() - 2; 2412 2413 for (uint32_t i = 0; i < length; ++i) { 2414 if (parameter_map->get(i + 2)->IsTheHole(isolate)) continue; 2415 if (convert == GetKeysConversion::kConvertToString) { 2416 Handle<String> index_string = isolate->factory()->Uint32ToString(i); 2417 list->set(insertion_index, *index_string); 2418 } else { 2419 list->set(insertion_index, Smi::FromInt(i), SKIP_WRITE_BARRIER); 2420 } 2421 insertion_index++; 2422 } 2423 2424 Handle<FixedArrayBase> store(FixedArrayBase::cast(parameter_map->get(1))); 2425 return ArgumentsAccessor::DirectCollectElementIndicesImpl( 2426 isolate, object, store, convert, filter, list, nof_indices, 2427 insertion_index); 2428 } 2429 }; 2430 2431 2432 class SlowSloppyArgumentsElementsAccessor 2433 : public SloppyArgumentsElementsAccessor< 2434 SlowSloppyArgumentsElementsAccessor, DictionaryElementsAccessor, 2435 ElementsKindTraits<SLOW_SLOPPY_ARGUMENTS_ELEMENTS> > { 2436 public: 2437 explicit SlowSloppyArgumentsElementsAccessor(const char* name) 2438 : SloppyArgumentsElementsAccessor< 2439 SlowSloppyArgumentsElementsAccessor, DictionaryElementsAccessor, 2440 ElementsKindTraits<SLOW_SLOPPY_ARGUMENTS_ELEMENTS> >(name) {} 2441 2442 static void DeleteFromArguments(Handle<JSObject> obj, uint32_t entry) { 2443 Handle<FixedArray> parameter_map(FixedArray::cast(obj->elements())); 2444 Handle<SeededNumberDictionary> dict( 2445 SeededNumberDictionary::cast(parameter_map->get(1))); 2446 // TODO(verwaest): Remove reliance on index in Shrink. 2447 uint32_t index = GetIndexForEntryImpl(*dict, entry); 2448 Handle<Object> result = SeededNumberDictionary::DeleteProperty(dict, entry); 2449 USE(result); 2450 DCHECK(result->IsTrue(dict->GetIsolate())); 2451 Handle<FixedArray> new_elements = 2452 SeededNumberDictionary::Shrink(dict, index); 2453 parameter_map->set(1, *new_elements); 2454 } 2455 2456 static void AddImpl(Handle<JSObject> object, uint32_t index, 2457 Handle<Object> value, PropertyAttributes attributes, 2458 uint32_t new_capacity) { 2459 Handle<FixedArray> parameter_map(FixedArray::cast(object->elements())); 2460 Handle<FixedArrayBase> old_elements( 2461 FixedArrayBase::cast(parameter_map->get(1))); 2462 Handle<SeededNumberDictionary> dictionary = 2463 old_elements->IsSeededNumberDictionary() 2464 ? Handle<SeededNumberDictionary>::cast(old_elements) 2465 : JSObject::NormalizeElements(object); 2466 PropertyDetails details(attributes, DATA, 0, PropertyCellType::kNoCell); 2467 Handle<SeededNumberDictionary> new_dictionary = 2468 SeededNumberDictionary::AddNumberEntry( 2469 dictionary, index, value, details, 2470 object->map()->is_prototype_map()); 2471 if (attributes != NONE) object->RequireSlowElements(*new_dictionary); 2472 if (*dictionary != *new_dictionary) { 2473 FixedArray::cast(object->elements())->set(1, *new_dictionary); 2474 } 2475 } 2476 2477 static void ReconfigureImpl(Handle<JSObject> object, 2478 Handle<FixedArrayBase> store, uint32_t entry, 2479 Handle<Object> value, 2480 PropertyAttributes attributes) { 2481 Handle<FixedArray> parameter_map = Handle<FixedArray>::cast(store); 2482 uint32_t length = parameter_map->length() - 2; 2483 Isolate* isolate = store->GetIsolate(); 2484 if (entry < length) { 2485 Object* probe = parameter_map->get(entry + 2); 2486 DCHECK(!probe->IsTheHole(isolate)); 2487 Context* context = Context::cast(parameter_map->get(0)); 2488 int context_entry = Smi::cast(probe)->value(); 2489 DCHECK(!context->get(context_entry)->IsTheHole(isolate)); 2490 context->set(context_entry, *value); 2491 2492 // Redefining attributes of an aliased element destroys fast aliasing. 2493 parameter_map->set_the_hole(entry + 2); 2494 // For elements that are still writable we re-establish slow aliasing. 2495 if ((attributes & READ_ONLY) == 0) { 2496 value = isolate->factory()->NewAliasedArgumentsEntry(context_entry); 2497 } 2498 2499 PropertyDetails details(attributes, DATA, 0, PropertyCellType::kNoCell); 2500 Handle<SeededNumberDictionary> arguments( 2501 SeededNumberDictionary::cast(parameter_map->get(1)), isolate); 2502 arguments = SeededNumberDictionary::AddNumberEntry( 2503 arguments, entry, value, details, object->map()->is_prototype_map()); 2504 // If the attributes were NONE, we would have called set rather than 2505 // reconfigure. 2506 DCHECK_NE(NONE, attributes); 2507 object->RequireSlowElements(*arguments); 2508 parameter_map->set(1, *arguments); 2509 } else { 2510 Handle<FixedArrayBase> arguments( 2511 FixedArrayBase::cast(parameter_map->get(1)), isolate); 2512 DictionaryElementsAccessor::ReconfigureImpl( 2513 object, arguments, entry - length, value, attributes); 2514 } 2515 } 2516 }; 2517 2518 2519 class FastSloppyArgumentsElementsAccessor 2520 : public SloppyArgumentsElementsAccessor< 2521 FastSloppyArgumentsElementsAccessor, FastHoleyObjectElementsAccessor, 2522 ElementsKindTraits<FAST_SLOPPY_ARGUMENTS_ELEMENTS> > { 2523 public: 2524 explicit FastSloppyArgumentsElementsAccessor(const char* name) 2525 : SloppyArgumentsElementsAccessor< 2526 FastSloppyArgumentsElementsAccessor, 2527 FastHoleyObjectElementsAccessor, 2528 ElementsKindTraits<FAST_SLOPPY_ARGUMENTS_ELEMENTS> >(name) {} 2529 2530 static Handle<FixedArray> GetArguments(Isolate* isolate, 2531 FixedArrayBase* backing_store) { 2532 FixedArray* parameter_map = FixedArray::cast(backing_store); 2533 return Handle<FixedArray>(FixedArray::cast(parameter_map->get(1)), isolate); 2534 } 2535 2536 static Handle<JSArray> SliceImpl(Handle<JSObject> receiver, uint32_t start, 2537 uint32_t end) { 2538 Isolate* isolate = receiver->GetIsolate(); 2539 uint32_t result_len = end < start ? 0u : end - start; 2540 Handle<JSArray> result_array = isolate->factory()->NewJSArray( 2541 FAST_HOLEY_ELEMENTS, result_len, result_len); 2542 DisallowHeapAllocation no_gc; 2543 FixedArray* elements = FixedArray::cast(result_array->elements()); 2544 FixedArray* parameters = FixedArray::cast(receiver->elements()); 2545 uint32_t insertion_index = 0; 2546 for (uint32_t i = start; i < end; i++) { 2547 uint32_t entry = 2548 GetEntryForIndexImpl(*receiver, parameters, i, ALL_PROPERTIES); 2549 if (entry != kMaxUInt32 && HasEntryImpl(parameters, entry)) { 2550 elements->set(insertion_index, *GetImpl(parameters, entry)); 2551 } else { 2552 elements->set_the_hole(insertion_index); 2553 } 2554 insertion_index++; 2555 } 2556 return result_array; 2557 } 2558 2559 static Handle<SeededNumberDictionary> NormalizeImpl( 2560 Handle<JSObject> object, Handle<FixedArrayBase> elements) { 2561 Handle<FixedArray> arguments = 2562 GetArguments(elements->GetIsolate(), *elements); 2563 return FastHoleyObjectElementsAccessor::NormalizeImpl(object, arguments); 2564 } 2565 2566 static void DeleteFromArguments(Handle<JSObject> obj, uint32_t entry) { 2567 Handle<FixedArray> arguments = 2568 GetArguments(obj->GetIsolate(), obj->elements()); 2569 FastHoleyObjectElementsAccessor::DeleteCommon(obj, entry, arguments); 2570 } 2571 2572 static void AddImpl(Handle<JSObject> object, uint32_t index, 2573 Handle<Object> value, PropertyAttributes attributes, 2574 uint32_t new_capacity) { 2575 DCHECK_EQ(NONE, attributes); 2576 Handle<FixedArray> parameter_map(FixedArray::cast(object->elements())); 2577 Handle<FixedArrayBase> old_elements( 2578 FixedArrayBase::cast(parameter_map->get(1))); 2579 if (old_elements->IsSeededNumberDictionary() || 2580 static_cast<uint32_t>(old_elements->length()) < new_capacity) { 2581 GrowCapacityAndConvertImpl(object, new_capacity); 2582 } 2583 FixedArray* arguments = FixedArray::cast(parameter_map->get(1)); 2584 // For fast holey objects, the entry equals the index. The code above made 2585 // sure that there's enough space to store the value. We cannot convert 2586 // index to entry explicitly since the slot still contains the hole, so the 2587 // current EntryForIndex would indicate that it is "absent" by returning 2588 // kMaxUInt32. 2589 FastHoleyObjectElementsAccessor::SetImpl(arguments, index, *value); 2590 } 2591 2592 static void ReconfigureImpl(Handle<JSObject> object, 2593 Handle<FixedArrayBase> store, uint32_t entry, 2594 Handle<Object> value, 2595 PropertyAttributes attributes) { 2596 Handle<SeededNumberDictionary> dictionary = 2597 JSObject::NormalizeElements(object); 2598 FixedArray::cast(*store)->set(1, *dictionary); 2599 uint32_t length = static_cast<uint32_t>(store->length()) - 2; 2600 if (entry >= length) { 2601 entry = dictionary->FindEntry(entry - length) + length; 2602 } 2603 SlowSloppyArgumentsElementsAccessor::ReconfigureImpl(object, store, entry, 2604 value, attributes); 2605 } 2606 2607 static void CopyElementsImpl(FixedArrayBase* from, uint32_t from_start, 2608 FixedArrayBase* to, ElementsKind from_kind, 2609 uint32_t to_start, int packed_size, 2610 int copy_size) { 2611 DCHECK(!to->IsDictionary()); 2612 if (from_kind == SLOW_SLOPPY_ARGUMENTS_ELEMENTS) { 2613 CopyDictionaryToObjectElements(from, from_start, to, FAST_HOLEY_ELEMENTS, 2614 to_start, copy_size); 2615 } else { 2616 DCHECK_EQ(FAST_SLOPPY_ARGUMENTS_ELEMENTS, from_kind); 2617 CopyObjectToObjectElements(from, FAST_HOLEY_ELEMENTS, from_start, to, 2618 FAST_HOLEY_ELEMENTS, to_start, copy_size); 2619 } 2620 } 2621 2622 static void GrowCapacityAndConvertImpl(Handle<JSObject> object, 2623 uint32_t capacity) { 2624 Handle<FixedArray> parameter_map(FixedArray::cast(object->elements())); 2625 Handle<FixedArray> old_elements(FixedArray::cast(parameter_map->get(1))); 2626 ElementsKind from_kind = object->GetElementsKind(); 2627 // This method should only be called if there's a reason to update the 2628 // elements. 2629 DCHECK(from_kind == SLOW_SLOPPY_ARGUMENTS_ELEMENTS || 2630 static_cast<uint32_t>(old_elements->length()) < capacity); 2631 Handle<FixedArrayBase> elements = 2632 ConvertElementsWithCapacity(object, old_elements, from_kind, capacity); 2633 Handle<Map> new_map = JSObject::GetElementsTransitionMap( 2634 object, FAST_SLOPPY_ARGUMENTS_ELEMENTS); 2635 JSObject::MigrateToMap(object, new_map); 2636 parameter_map->set(1, *elements); 2637 JSObject::ValidateElements(object); 2638 } 2639 }; 2640 2641 template <typename Subclass, typename BackingStoreAccessor, typename KindTraits> 2642 class StringWrapperElementsAccessor 2643 : public ElementsAccessorBase<Subclass, KindTraits> { 2644 public: 2645 explicit StringWrapperElementsAccessor(const char* name) 2646 : ElementsAccessorBase<Subclass, KindTraits>(name) { 2647 USE(KindTraits::Kind); 2648 } 2649 2650 static Handle<Object> GetImpl(Handle<JSObject> holder, uint32_t entry) { 2651 Isolate* isolate = holder->GetIsolate(); 2652 Handle<String> string(GetString(*holder), isolate); 2653 uint32_t length = static_cast<uint32_t>(string->length()); 2654 if (entry < length) { 2655 return isolate->factory()->LookupSingleCharacterStringFromCode( 2656 String::Flatten(string)->Get(entry)); 2657 } 2658 return BackingStoreAccessor::GetImpl(holder, entry - length); 2659 } 2660 2661 static PropertyDetails GetDetailsImpl(JSObject* holder, uint32_t entry) { 2662 uint32_t length = static_cast<uint32_t>(GetString(holder)->length()); 2663 if (entry < length) { 2664 PropertyAttributes attributes = 2665 static_cast<PropertyAttributes>(READ_ONLY | DONT_DELETE); 2666 return PropertyDetails(attributes, v8::internal::DATA, 0, 2667 PropertyCellType::kNoCell); 2668 } 2669 return BackingStoreAccessor::GetDetailsImpl(holder, entry - length); 2670 } 2671 2672 static uint32_t GetEntryForIndexImpl(JSObject* holder, 2673 FixedArrayBase* backing_store, 2674 uint32_t index, PropertyFilter filter) { 2675 uint32_t length = static_cast<uint32_t>(GetString(holder)->length()); 2676 if (index < length) return index; 2677 uint32_t backing_store_entry = BackingStoreAccessor::GetEntryForIndexImpl( 2678 holder, backing_store, index, filter); 2679 if (backing_store_entry == kMaxUInt32) return kMaxUInt32; 2680 DCHECK(backing_store_entry < kMaxUInt32 - length); 2681 return backing_store_entry + length; 2682 } 2683 2684 static void DeleteImpl(Handle<JSObject> holder, uint32_t entry) { 2685 uint32_t length = static_cast<uint32_t>(GetString(*holder)->length()); 2686 if (entry < length) { 2687 return; // String contents can't be deleted. 2688 } 2689 BackingStoreAccessor::DeleteImpl(holder, entry - length); 2690 } 2691 2692 static void SetImpl(Handle<JSObject> holder, uint32_t entry, Object* value) { 2693 uint32_t length = static_cast<uint32_t>(GetString(*holder)->length()); 2694 if (entry < length) { 2695 return; // String contents are read-only. 2696 } 2697 BackingStoreAccessor::SetImpl(holder->elements(), entry - length, value); 2698 } 2699 2700 static void AddImpl(Handle<JSObject> object, uint32_t index, 2701 Handle<Object> value, PropertyAttributes attributes, 2702 uint32_t new_capacity) { 2703 DCHECK(index >= static_cast<uint32_t>(GetString(*object)->length())); 2704 // Explicitly grow fast backing stores if needed. Dictionaries know how to 2705 // extend their capacity themselves. 2706 if (KindTraits::Kind == FAST_STRING_WRAPPER_ELEMENTS && 2707 (object->GetElementsKind() == SLOW_STRING_WRAPPER_ELEMENTS || 2708 BackingStoreAccessor::GetCapacityImpl(*object, object->elements()) != 2709 new_capacity)) { 2710 GrowCapacityAndConvertImpl(object, new_capacity); 2711 } 2712 BackingStoreAccessor::AddImpl(object, index, value, attributes, 2713 new_capacity); 2714 } 2715 2716 static void ReconfigureImpl(Handle<JSObject> object, 2717 Handle<FixedArrayBase> store, uint32_t entry, 2718 Handle<Object> value, 2719 PropertyAttributes attributes) { 2720 uint32_t length = static_cast<uint32_t>(GetString(*object)->length()); 2721 if (entry < length) { 2722 return; // String contents can't be reconfigured. 2723 } 2724 BackingStoreAccessor::ReconfigureImpl(object, store, entry - length, value, 2725 attributes); 2726 } 2727 2728 static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver, 2729 KeyAccumulator* accumulator, 2730 AddKeyConversion convert) { 2731 Isolate* isolate = receiver->GetIsolate(); 2732 Handle<String> string(GetString(*receiver), isolate); 2733 string = String::Flatten(string); 2734 uint32_t length = static_cast<uint32_t>(string->length()); 2735 for (uint32_t i = 0; i < length; i++) { 2736 accumulator->AddKey( 2737 isolate->factory()->LookupSingleCharacterStringFromCode( 2738 string->Get(i)), 2739 convert); 2740 } 2741 BackingStoreAccessor::AddElementsToKeyAccumulatorImpl(receiver, accumulator, 2742 convert); 2743 } 2744 2745 static void CollectElementIndicesImpl(Handle<JSObject> object, 2746 Handle<FixedArrayBase> backing_store, 2747 KeyAccumulator* keys) { 2748 uint32_t length = GetString(*object)->length(); 2749 Factory* factory = keys->isolate()->factory(); 2750 for (uint32_t i = 0; i < length; i++) { 2751 keys->AddKey(factory->NewNumberFromUint(i)); 2752 } 2753 BackingStoreAccessor::CollectElementIndicesImpl(object, backing_store, 2754 keys); 2755 } 2756 2757 static void GrowCapacityAndConvertImpl(Handle<JSObject> object, 2758 uint32_t capacity) { 2759 Handle<FixedArrayBase> old_elements(object->elements()); 2760 ElementsKind from_kind = object->GetElementsKind(); 2761 // This method should only be called if there's a reason to update the 2762 // elements. 2763 DCHECK(from_kind == SLOW_STRING_WRAPPER_ELEMENTS || 2764 static_cast<uint32_t>(old_elements->length()) < capacity); 2765 Subclass::BasicGrowCapacityAndConvertImpl(object, old_elements, from_kind, 2766 FAST_STRING_WRAPPER_ELEMENTS, 2767 capacity); 2768 } 2769 2770 static void CopyElementsImpl(FixedArrayBase* from, uint32_t from_start, 2771 FixedArrayBase* to, ElementsKind from_kind, 2772 uint32_t to_start, int packed_size, 2773 int copy_size) { 2774 DCHECK(!to->IsDictionary()); 2775 if (from_kind == SLOW_STRING_WRAPPER_ELEMENTS) { 2776 CopyDictionaryToObjectElements(from, from_start, to, FAST_HOLEY_ELEMENTS, 2777 to_start, copy_size); 2778 } else { 2779 DCHECK_EQ(FAST_STRING_WRAPPER_ELEMENTS, from_kind); 2780 CopyObjectToObjectElements(from, FAST_HOLEY_ELEMENTS, from_start, to, 2781 FAST_HOLEY_ELEMENTS, to_start, copy_size); 2782 } 2783 } 2784 2785 private: 2786 static String* GetString(JSObject* holder) { 2787 DCHECK(holder->IsJSValue()); 2788 JSValue* js_value = JSValue::cast(holder); 2789 DCHECK(js_value->value()->IsString()); 2790 return String::cast(js_value->value()); 2791 } 2792 }; 2793 2794 class FastStringWrapperElementsAccessor 2795 : public StringWrapperElementsAccessor< 2796 FastStringWrapperElementsAccessor, FastHoleyObjectElementsAccessor, 2797 ElementsKindTraits<FAST_STRING_WRAPPER_ELEMENTS>> { 2798 public: 2799 explicit FastStringWrapperElementsAccessor(const char* name) 2800 : StringWrapperElementsAccessor< 2801 FastStringWrapperElementsAccessor, FastHoleyObjectElementsAccessor, 2802 ElementsKindTraits<FAST_STRING_WRAPPER_ELEMENTS>>(name) {} 2803 2804 static Handle<SeededNumberDictionary> NormalizeImpl( 2805 Handle<JSObject> object, Handle<FixedArrayBase> elements) { 2806 return FastHoleyObjectElementsAccessor::NormalizeImpl(object, elements); 2807 } 2808 }; 2809 2810 class SlowStringWrapperElementsAccessor 2811 : public StringWrapperElementsAccessor< 2812 SlowStringWrapperElementsAccessor, DictionaryElementsAccessor, 2813 ElementsKindTraits<SLOW_STRING_WRAPPER_ELEMENTS>> { 2814 public: 2815 explicit SlowStringWrapperElementsAccessor(const char* name) 2816 : StringWrapperElementsAccessor< 2817 SlowStringWrapperElementsAccessor, DictionaryElementsAccessor, 2818 ElementsKindTraits<SLOW_STRING_WRAPPER_ELEMENTS>>(name) {} 2819 2820 static bool HasAccessorsImpl(JSObject* holder, 2821 FixedArrayBase* backing_store) { 2822 return DictionaryElementsAccessor::HasAccessorsImpl(holder, backing_store); 2823 } 2824 }; 2825 2826 } // namespace 2827 2828 2829 void CheckArrayAbuse(Handle<JSObject> obj, const char* op, uint32_t index, 2830 bool allow_appending) { 2831 DisallowHeapAllocation no_allocation; 2832 Object* raw_length = NULL; 2833 const char* elements_type = "array"; 2834 if (obj->IsJSArray()) { 2835 JSArray* array = JSArray::cast(*obj); 2836 raw_length = array->length(); 2837 } else { 2838 raw_length = Smi::FromInt(obj->elements()->length()); 2839 elements_type = "object"; 2840 } 2841 2842 if (raw_length->IsNumber()) { 2843 double n = raw_length->Number(); 2844 if (FastI2D(FastD2UI(n)) == n) { 2845 int32_t int32_length = DoubleToInt32(n); 2846 uint32_t compare_length = static_cast<uint32_t>(int32_length); 2847 if (allow_appending) compare_length++; 2848 if (index >= compare_length) { 2849 PrintF("[OOB %s %s (%s length = %d, element accessed = %d) in ", 2850 elements_type, op, elements_type, static_cast<int>(int32_length), 2851 static_cast<int>(index)); 2852 TraceTopFrame(obj->GetIsolate()); 2853 PrintF("]\n"); 2854 } 2855 } else { 2856 PrintF("[%s elements length not integer value in ", elements_type); 2857 TraceTopFrame(obj->GetIsolate()); 2858 PrintF("]\n"); 2859 } 2860 } else { 2861 PrintF("[%s elements length not a number in ", elements_type); 2862 TraceTopFrame(obj->GetIsolate()); 2863 PrintF("]\n"); 2864 } 2865 } 2866 2867 2868 MaybeHandle<Object> ArrayConstructInitializeElements(Handle<JSArray> array, 2869 Arguments* args) { 2870 if (args->length() == 0) { 2871 // Optimize the case where there are no parameters passed. 2872 JSArray::Initialize(array, JSArray::kPreallocatedArrayElements); 2873 return array; 2874 2875 } else if (args->length() == 1 && args->at<Object>(0)->IsNumber()) { 2876 uint32_t length; 2877 if (!args->at<Object>(0)->ToArrayLength(&length)) { 2878 return ThrowArrayLengthRangeError(array->GetIsolate()); 2879 } 2880 2881 // Optimize the case where there is one argument and the argument is a small 2882 // smi. 2883 if (length > 0 && length < JSArray::kInitialMaxFastElementArray) { 2884 ElementsKind elements_kind = array->GetElementsKind(); 2885 JSArray::Initialize(array, length, length); 2886 2887 if (!IsFastHoleyElementsKind(elements_kind)) { 2888 elements_kind = GetHoleyElementsKind(elements_kind); 2889 JSObject::TransitionElementsKind(array, elements_kind); 2890 } 2891 } else if (length == 0) { 2892 JSArray::Initialize(array, JSArray::kPreallocatedArrayElements); 2893 } else { 2894 // Take the argument as the length. 2895 JSArray::Initialize(array, 0); 2896 JSArray::SetLength(array, length); 2897 } 2898 return array; 2899 } 2900 2901 Factory* factory = array->GetIsolate()->factory(); 2902 2903 // Set length and elements on the array. 2904 int number_of_elements = args->length(); 2905 JSObject::EnsureCanContainElements( 2906 array, args, 0, number_of_elements, ALLOW_CONVERTED_DOUBLE_ELEMENTS); 2907 2908 // Allocate an appropriately typed elements array. 2909 ElementsKind elements_kind = array->GetElementsKind(); 2910 Handle<FixedArrayBase> elms; 2911 if (IsFastDoubleElementsKind(elements_kind)) { 2912 elms = Handle<FixedArrayBase>::cast( 2913 factory->NewFixedDoubleArray(number_of_elements)); 2914 } else { 2915 elms = Handle<FixedArrayBase>::cast( 2916 factory->NewFixedArrayWithHoles(number_of_elements)); 2917 } 2918 2919 // Fill in the content 2920 switch (elements_kind) { 2921 case FAST_HOLEY_SMI_ELEMENTS: 2922 case FAST_SMI_ELEMENTS: { 2923 Handle<FixedArray> smi_elms = Handle<FixedArray>::cast(elms); 2924 for (int entry = 0; entry < number_of_elements; entry++) { 2925 smi_elms->set(entry, (*args)[entry], SKIP_WRITE_BARRIER); 2926 } 2927 break; 2928 } 2929 case FAST_HOLEY_ELEMENTS: 2930 case FAST_ELEMENTS: { 2931 DisallowHeapAllocation no_gc; 2932 WriteBarrierMode mode = elms->GetWriteBarrierMode(no_gc); 2933 Handle<FixedArray> object_elms = Handle<FixedArray>::cast(elms); 2934 for (int entry = 0; entry < number_of_elements; entry++) { 2935 object_elms->set(entry, (*args)[entry], mode); 2936 } 2937 break; 2938 } 2939 case FAST_HOLEY_DOUBLE_ELEMENTS: 2940 case FAST_DOUBLE_ELEMENTS: { 2941 Handle<FixedDoubleArray> double_elms = 2942 Handle<FixedDoubleArray>::cast(elms); 2943 for (int entry = 0; entry < number_of_elements; entry++) { 2944 double_elms->set(entry, (*args)[entry]->Number()); 2945 } 2946 break; 2947 } 2948 default: 2949 UNREACHABLE(); 2950 break; 2951 } 2952 2953 array->set_elements(*elms); 2954 array->set_length(Smi::FromInt(number_of_elements)); 2955 return array; 2956 } 2957 2958 2959 void ElementsAccessor::InitializeOncePerProcess() { 2960 static ElementsAccessor* accessor_array[] = { 2961 #define ACCESSOR_ARRAY(Class, Kind, Store) new Class(#Kind), 2962 ELEMENTS_LIST(ACCESSOR_ARRAY) 2963 #undef ACCESSOR_ARRAY 2964 }; 2965 2966 STATIC_ASSERT((sizeof(accessor_array) / sizeof(*accessor_array)) == 2967 kElementsKindCount); 2968 2969 elements_accessors_ = accessor_array; 2970 } 2971 2972 2973 void ElementsAccessor::TearDown() { 2974 if (elements_accessors_ == NULL) return; 2975 #define ACCESSOR_DELETE(Class, Kind, Store) delete elements_accessors_[Kind]; 2976 ELEMENTS_LIST(ACCESSOR_DELETE) 2977 #undef ACCESSOR_DELETE 2978 elements_accessors_ = NULL; 2979 } 2980 2981 Handle<JSArray> ElementsAccessor::Concat(Isolate* isolate, Arguments* args, 2982 uint32_t concat_size, 2983 uint32_t result_len) { 2984 ElementsKind result_elements_kind = GetInitialFastElementsKind(); 2985 bool has_raw_doubles = false; 2986 { 2987 DisallowHeapAllocation no_gc; 2988 bool is_holey = false; 2989 for (uint32_t i = 0; i < concat_size; i++) { 2990 Object* arg = (*args)[i]; 2991 ElementsKind arg_kind = JSArray::cast(arg)->GetElementsKind(); 2992 has_raw_doubles = has_raw_doubles || IsFastDoubleElementsKind(arg_kind); 2993 is_holey = is_holey || IsFastHoleyElementsKind(arg_kind); 2994 result_elements_kind = 2995 GetMoreGeneralElementsKind(result_elements_kind, arg_kind); 2996 } 2997 if (is_holey) { 2998 result_elements_kind = GetHoleyElementsKind(result_elements_kind); 2999 } 3000 } 3001 3002 // If a double array is concatted into a fast elements array, the fast 3003 // elements array needs to be initialized to contain proper holes, since 3004 // boxing doubles may cause incremental marking. 3005 bool requires_double_boxing = 3006 has_raw_doubles && !IsFastDoubleElementsKind(result_elements_kind); 3007 ArrayStorageAllocationMode mode = requires_double_boxing 3008 ? INITIALIZE_ARRAY_ELEMENTS_WITH_HOLE 3009 : DONT_INITIALIZE_ARRAY_ELEMENTS; 3010 Handle<JSArray> result_array = isolate->factory()->NewJSArray( 3011 result_elements_kind, result_len, result_len, mode); 3012 if (result_len == 0) return result_array; 3013 3014 uint32_t insertion_index = 0; 3015 Handle<FixedArrayBase> storage(result_array->elements(), isolate); 3016 ElementsAccessor* accessor = ElementsAccessor::ForKind(result_elements_kind); 3017 for (uint32_t i = 0; i < concat_size; i++) { 3018 // It is crucial to keep |array| in a raw pointer form to avoid 3019 // performance degradation. 3020 JSArray* array = JSArray::cast((*args)[i]); 3021 uint32_t len = 0; 3022 array->length()->ToArrayLength(&len); 3023 if (len == 0) continue; 3024 ElementsKind from_kind = array->GetElementsKind(); 3025 accessor->CopyElements(array, 0, from_kind, storage, insertion_index, len); 3026 insertion_index += len; 3027 } 3028 3029 DCHECK_EQ(insertion_index, result_len); 3030 return result_array; 3031 } 3032 3033 ElementsAccessor** ElementsAccessor::elements_accessors_ = NULL; 3034 } // namespace internal 3035 } // namespace v8 3036