1// Copyright 2017 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/map-updater.h"
6
7#include "src/field-type.h"
8#include "src/handles.h"
9#include "src/isolate.h"
10#include "src/objects-inl.h"
11#include "src/objects.h"
12#include "src/property-details.h"
13#include "src/transitions.h"
14
15namespace v8 {
16namespace internal {
17
18namespace {
19
20inline bool EqualImmutableValues(Object obj1, Object obj2) {
21 if (obj1 == obj2) return true; // Valid for both kData and kAccessor kinds.
22 // TODO(ishell): compare AccessorPairs.
23 return false;
24}
25
26} // namespace
27
28MapUpdater::MapUpdater(Isolate* isolate, Handle<Map> old_map)
29 : isolate_(isolate),
30 old_map_(old_map),
31 old_descriptors_(old_map->instance_descriptors(), isolate_),
32 old_nof_(old_map_->NumberOfOwnDescriptors()),
33 new_elements_kind_(old_map_->elements_kind()),
34 is_transitionable_fast_elements_kind_(
35 IsTransitionableFastElementsKind(new_elements_kind_)) {
36 // We shouldn't try to update remote objects.
37 DCHECK(!old_map->FindRootMap(isolate)
38 ->GetConstructor()
39 ->IsFunctionTemplateInfo());
40}
41
42Name MapUpdater::GetKey(int descriptor) const {
43 return old_descriptors_->GetKey(descriptor);
44}
45
46PropertyDetails MapUpdater::GetDetails(int descriptor) const {
47 DCHECK_LE(0, descriptor);
48 if (descriptor == modified_descriptor_) {
49 PropertyAttributes attributes = new_attributes_;
50 // If the original map was sealed or frozen, let us used the old
51 // attributes so that we follow the same transition path as before.
52 // Note that the user could not have changed the attributes because
53 // both seal and freeze make the properties non-configurable.
54 if (integrity_level_ == SEALED || integrity_level_ == FROZEN) {
55 attributes = old_descriptors_->GetDetails(descriptor).attributes();
56 }
57 return PropertyDetails(new_kind_, attributes, new_location_, new_constness_,
58 new_representation_);
59 }
60 return old_descriptors_->GetDetails(descriptor);
61}
62
63Object MapUpdater::GetValue(int descriptor) const {
64 DCHECK_LE(0, descriptor);
65 if (descriptor == modified_descriptor_) {
66 DCHECK_EQ(kDescriptor, new_location_);
67 return *new_value_;
68 }
69 DCHECK_EQ(kDescriptor, GetDetails(descriptor).location());
70 return old_descriptors_->GetStrongValue(descriptor);
71}
72
73FieldType MapUpdater::GetFieldType(int descriptor) const {
74 DCHECK_LE(0, descriptor);
75 if (descriptor == modified_descriptor_) {
76 DCHECK_EQ(kField, new_location_);
77 return *new_field_type_;
78 }
79 DCHECK_EQ(kField, GetDetails(descriptor).location());
80 return old_descriptors_->GetFieldType(descriptor);
81}
82
83Handle<FieldType> MapUpdater::GetOrComputeFieldType(
84 int descriptor, PropertyLocation location,
85 Representation representation) const {
86 DCHECK_LE(0, descriptor);
87 // |location| is just a pre-fetched GetDetails(descriptor).location().
88 DCHECK_EQ(location, GetDetails(descriptor).location());
89 if (location == kField) {
90 return handle(GetFieldType(descriptor), isolate_);
91 } else {
92 return GetValue(descriptor)->OptimalType(isolate_, representation);
93 }
94}
95
96Handle<FieldType> MapUpdater::GetOrComputeFieldType(
97 Handle<DescriptorArray> descriptors, int descriptor,
98 PropertyLocation location, Representation representation) {
99 // |location| is just a pre-fetched GetDetails(descriptor).location().
100 DCHECK_EQ(descriptors->GetDetails(descriptor).location(), location);
101 if (location == kField) {
102 return handle(descriptors->GetFieldType(descriptor), isolate_);
103 } else {
104 return descriptors->GetStrongValue(descriptor)
105 ->OptimalType(isolate_, representation);
106 }
107}
108
109Handle<Map> MapUpdater::ReconfigureToDataField(int descriptor,
110 PropertyAttributes attributes,
111 PropertyConstness constness,
112 Representation representation,
113 Handle<FieldType> field_type) {
114 DCHECK_EQ(kInitialized, state_);
115 DCHECK_LE(0, descriptor);
116 DCHECK(!old_map_->is_dictionary_map());
117 modified_descriptor_ = descriptor;
118 new_kind_ = kData;
119 new_attributes_ = attributes;
120 new_location_ = kField;
121
122 PropertyDetails old_details =
123 old_descriptors_->GetDetails(modified_descriptor_);
124
125 // If property kind is not reconfigured merge the result with
126 // representation/field type from the old descriptor.
127 if (old_details.kind() == new_kind_) {
128 new_constness_ = GeneralizeConstness(constness, old_details.constness());
129
130 Representation old_representation = old_details.representation();
131 new_representation_ = representation.generalize(old_representation);
132
133 Handle<FieldType> old_field_type =
134 GetOrComputeFieldType(old_descriptors_, modified_descriptor_,
135 old_details.location(), new_representation_);
136
137 new_field_type_ =
138 Map::GeneralizeFieldType(old_representation, old_field_type,
139 new_representation_, field_type, isolate_);
140 } else {
141 // We don't know if this is a first property kind reconfiguration
142 // and we don't know which value was in this property previously
143 // therefore we can't treat such a property as constant.
144 new_constness_ = PropertyConstness::kMutable;
145 new_representation_ = representation;
146 new_field_type_ = field_type;
147 }
148
149 Map::GeneralizeIfCanHaveTransitionableFastElementsKind(
150 isolate_, old_map_->instance_type(), &new_constness_,
151 &new_representation_, &new_field_type_);
152
153 if (TryReconfigureToDataFieldInplace() == kEnd) return result_map_;
154 if (FindRootMap() == kEnd) return result_map_;
155 if (FindTargetMap() == kEnd) return result_map_;
156 if (ConstructNewMap() == kAtIntegrityLevelSource) {
157 ConstructNewMapWithIntegrityLevelTransition();
158 }
159 DCHECK_EQ(kEnd, state_);
160 return result_map_;
161}
162
163Handle<Map> MapUpdater::ReconfigureElementsKind(ElementsKind elements_kind) {
164 DCHECK_EQ(kInitialized, state_);
165 new_elements_kind_ = elements_kind;
166 is_transitionable_fast_elements_kind_ =
167 IsTransitionableFastElementsKind(new_elements_kind_);
168
169 if (FindRootMap() == kEnd) return result_map_;
170 if (FindTargetMap() == kEnd) return result_map_;
171 if (ConstructNewMap() == kAtIntegrityLevelSource) {
172 ConstructNewMapWithIntegrityLevelTransition();
173 }
174 DCHECK_EQ(kEnd, state_);
175 return result_map_;
176}
177
178Handle<Map> MapUpdater::Update() {
179 DCHECK_EQ(kInitialized, state_);
180 DCHECK(old_map_->is_deprecated());
181
182 if (FindRootMap() == kEnd) return result_map_;
183 if (FindTargetMap() == kEnd) return result_map_;
184 if (ConstructNewMap() == kAtIntegrityLevelSource) {
185 ConstructNewMapWithIntegrityLevelTransition();
186 }
187 DCHECK_EQ(kEnd, state_);
188 if (FLAG_fast_map_update) {
189 TransitionsAccessor(isolate_, old_map_).SetMigrationTarget(*result_map_);
190 }
191 return result_map_;
192}
193
194void MapUpdater::GeneralizeField(Handle<Map> map, int modify_index,
195 PropertyConstness new_constness,
196 Representation new_representation,
197 Handle<FieldType> new_field_type) {
198 Map::GeneralizeField(isolate_, map, modify_index, new_constness,
199 new_representation, new_field_type);
200
201 DCHECK(*old_descriptors_ == old_map_->instance_descriptors() ||
202 *old_descriptors_ == integrity_source_map_->instance_descriptors());
203}
204
205MapUpdater::State MapUpdater::CopyGeneralizeAllFields(const char* reason) {
206 result_map_ = Map::CopyGeneralizeAllFields(
207 isolate_, old_map_, new_elements_kind_, modified_descriptor_, new_kind_,
208 new_attributes_, reason);
209 state_ = kEnd;
210 return state_; // Done.
211}
212
213MapUpdater::State MapUpdater::TryReconfigureToDataFieldInplace() {
214 // Updating deprecated maps in-place doesn't make sense.
215 if (old_map_->is_deprecated()) return state_;
216
217 // If it's just a representation generalization case (i.e. property kind and
218 // attributes stays unchanged) it's fine to transition from None to anything
219 // but double without any modification to the object, because the default
220 // uninitialized value for representation None can be overwritten by both
221 // smi and tagged values. Doubles, however, would require a box allocation.
222 if (new_representation_.IsNone() || new_representation_.IsDouble()) {
223 return state_; // Not done yet.
224 }
225
226 PropertyDetails old_details =
227 old_descriptors_->GetDetails(modified_descriptor_);
228 Representation old_representation = old_details.representation();
229 if (!old_representation.CanBeInPlaceChangedTo(new_representation_)) {
230 return state_; // Not done yet.
231 }
232
233 DCHECK_EQ(new_kind_, old_details.kind());
234 DCHECK_EQ(new_attributes_, old_details.attributes());
235 DCHECK_EQ(kField, old_details.location());
236 if (FLAG_trace_generalization) {
237 old_map_->PrintGeneralization(
238 isolate_, stdout, "uninitialized field", modified_descriptor_, old_nof_,
239 old_nof_, false, old_representation, new_representation_,
240 handle(old_descriptors_->GetFieldType(modified_descriptor_), isolate_),
241 MaybeHandle<Object>(), new_field_type_, MaybeHandle<Object>());
242 }
243 Handle<Map> field_owner(
244 old_map_->FindFieldOwner(isolate_, modified_descriptor_), isolate_);
245
246 GeneralizeField(field_owner, modified_descriptor_, new_constness_,
247 new_representation_, new_field_type_);
248 // Check that the descriptor array was updated.
249 DCHECK(old_descriptors_->GetDetails(modified_descriptor_)
250 .representation()
251 .Equals(new_representation_));
252 DCHECK(old_descriptors_->GetFieldType(modified_descriptor_)
253 ->NowIs(new_field_type_));
254
255 result_map_ = old_map_;
256 state_ = kEnd;
257 return state_; // Done.
258}
259
260bool MapUpdater::TrySaveIntegrityLevelTransitions() {
261 // Figure out the most restrictive integrity level transition (it should
262 // be the last one in the transition tree).
263 Handle<Map> previous =
264 handle(Map::cast(old_map_->GetBackPointer()), isolate_);
265 Symbol integrity_level_symbol;
266 TransitionsAccessor last_transitions(isolate_, previous);
267 if (!last_transitions.HasIntegrityLevelTransitionTo(
268 *old_map_, &integrity_level_symbol, &integrity_level_)) {
269 // The last transition was not integrity level transition - just bail out.
270 // This can happen in the following cases:
271 // - there are private symbol transitions following the integrity level
272 // transitions (see crbug.com/v8/8854).
273 // - there is a getter added in addition to an existing setter (or a setter
274 // in addition to an existing getter).
275 return false;
276 }
277 integrity_level_symbol_ = handle(integrity_level_symbol, isolate_);
278 integrity_source_map_ = previous;
279
280 // Now walk up the back pointer chain and skip all integrity level
281 // transitions. If we encounter any non-integrity level transition interleaved
282 // with integrity level transitions, just bail out.
283 while (!integrity_source_map_->is_extensible()) {
284 previous =
285 handle(Map::cast(integrity_source_map_->GetBackPointer()), isolate_);
286 TransitionsAccessor transitions(isolate_, previous);
287 if (!transitions.HasIntegrityLevelTransitionTo(*integrity_source_map_)) {
288 return false;
289 }
290 integrity_source_map_ = previous;
291 }
292
293 // Integrity-level transitions never change number of descriptors.
294 CHECK_EQ(old_map_->NumberOfOwnDescriptors(),
295 integrity_source_map_->NumberOfOwnDescriptors());
296
297 has_integrity_level_transition_ = true;
298 old_descriptors_ =
299 handle(integrity_source_map_->instance_descriptors(), isolate_);
300 return true;
301}
302
303MapUpdater::State MapUpdater::FindRootMap() {
304 DCHECK_EQ(kInitialized, state_);
305 // Check the state of the root map.
306 root_map_ = handle(old_map_->FindRootMap(isolate_), isolate_);
307 ElementsKind from_kind = root_map_->elements_kind();
308 ElementsKind to_kind = new_elements_kind_;
309
310 if (root_map_->is_deprecated()) {
311 state_ = kEnd;
312 result_map_ = handle(
313 JSFunction::cast(root_map_->GetConstructor())->initial_map(), isolate_);
314 result_map_ = Map::AsElementsKind(isolate_, result_map_, to_kind);
315 DCHECK(result_map_->is_dictionary_map());
316 return state_;
317 }
318
319 if (!old_map_->EquivalentToForTransition(*root_map_)) {
320 return CopyGeneralizeAllFields("GenAll_NotEquivalent");
321 } else if (old_map_->is_extensible() != root_map_->is_extensible()) {
322 DCHECK(!old_map_->is_extensible());
323 DCHECK(root_map_->is_extensible());
324 // We have an integrity level transition in the tree, let us make a note
325 // of that transition to be able to replay it later.
326 if (!TrySaveIntegrityLevelTransitions()) {
327 return CopyGeneralizeAllFields("GenAll_PrivateSymbolsOnNonExtensible");
328 }
329
330 // We want to build transitions to the original element kind (before
331 // the seal transitions), so change {to_kind} accordingly.
332 DCHECK(to_kind == DICTIONARY_ELEMENTS ||
333 to_kind == SLOW_STRING_WRAPPER_ELEMENTS ||
334 IsFixedTypedArrayElementsKind(to_kind) ||
335 IsFrozenOrSealedElementsKind(to_kind));
336 to_kind = integrity_source_map_->elements_kind();
337 }
338
339 // TODO(ishell): Add a test for SLOW_SLOPPY_ARGUMENTS_ELEMENTS.
340 if (from_kind != to_kind && to_kind != DICTIONARY_ELEMENTS &&
341 to_kind != SLOW_STRING_WRAPPER_ELEMENTS &&
342 to_kind != SLOW_SLOPPY_ARGUMENTS_ELEMENTS &&
343 !(IsTransitionableFastElementsKind(from_kind) &&
344 IsMoreGeneralElementsKindTransition(from_kind, to_kind))) {
345 return CopyGeneralizeAllFields("GenAll_InvalidElementsTransition");
346 }
347
348 int root_nof = root_map_->NumberOfOwnDescriptors();
349 if (modified_descriptor_ >= 0 && modified_descriptor_ < root_nof) {
350 PropertyDetails old_details =
351 old_descriptors_->GetDetails(modified_descriptor_);
352 if (old_details.kind() != new_kind_ ||
353 old_details.attributes() != new_attributes_) {
354 return CopyGeneralizeAllFields("GenAll_RootModification1");
355 }
356 if (old_details.location() != kField) {
357 return CopyGeneralizeAllFields("GenAll_RootModification2");
358 }
359 if (!new_representation_.fits_into(old_details.representation())) {
360 return CopyGeneralizeAllFields("GenAll_RootModification4");
361 }
362
363 DCHECK_EQ(kData, old_details.kind());
364 DCHECK_EQ(kData, new_kind_);
365 DCHECK_EQ(kField, new_location_);
366
367 // Modify root map in-place. The GeneralizeField method is a no-op
368 // if the {old_map_} is already general enough to hold the requested
369 // {new_constness_} and {new_field_type_}.
370 GeneralizeField(old_map_, modified_descriptor_, new_constness_,
371 old_details.representation(), new_field_type_);
372 }
373
374 // From here on, use the map with correct elements kind as root map.
375 root_map_ = Map::AsElementsKind(isolate_, root_map_, to_kind);
376 state_ = kAtRootMap;
377 return state_; // Not done yet.
378}
379
380MapUpdater::State MapUpdater::FindTargetMap() {
381 DCHECK_EQ(kAtRootMap, state_);
382 target_map_ = root_map_;
383
384 int root_nof = root_map_->NumberOfOwnDescriptors();
385 for (int i = root_nof; i < old_nof_; ++i) {
386 PropertyDetails old_details = GetDetails(i);
387 Map transition = TransitionsAccessor(isolate_, target_map_)
388 .SearchTransition(GetKey(i), old_details.kind(),
389 old_details.attributes());
390 if (transition.is_null()) break;
391 Handle<Map> tmp_map(transition, isolate_);
392
393 Handle<DescriptorArray> tmp_descriptors(tmp_map->instance_descriptors(),
394 isolate_);
395
396 // Check if target map is incompatible.
397 PropertyDetails tmp_details = tmp_descriptors->GetDetails(i);
398 DCHECK_EQ(old_details.kind(), tmp_details.kind());
399 DCHECK_EQ(old_details.attributes(), tmp_details.attributes());
400 if (old_details.kind() == kAccessor &&
401 !EqualImmutableValues(GetValue(i),
402 tmp_descriptors->GetStrongValue(i))) {
403 // TODO(ishell): mutable accessors are not implemented yet.
404 return CopyGeneralizeAllFields("GenAll_Incompatible");
405 }
406 if (!IsGeneralizableTo(old_details.location(), tmp_details.location())) {
407 break;
408 }
409 Representation tmp_representation = tmp_details.representation();
410 if (!old_details.representation().fits_into(tmp_representation)) {
411 break;
412 }
413
414 if (tmp_details.location() == kField) {
415 Handle<FieldType> old_field_type =
416 GetOrComputeFieldType(i, old_details.location(), tmp_representation);
417 GeneralizeField(tmp_map, i, old_details.constness(), tmp_representation,
418 old_field_type);
419 } else {
420 // kDescriptor: Check that the value matches.
421 if (!EqualImmutableValues(GetValue(i),
422 tmp_descriptors->GetStrongValue(i))) {
423 break;
424 }
425 }
426 DCHECK(!tmp_map->is_deprecated());
427 target_map_ = tmp_map;
428 }
429
430 // Directly change the map if the target map is more general.
431 int target_nof = target_map_->NumberOfOwnDescriptors();
432 if (target_nof == old_nof_) {
433#ifdef DEBUG
434 if (modified_descriptor_ >= 0) {
435 DescriptorArray target_descriptors = target_map_->instance_descriptors();
436 PropertyDetails details =
437 target_descriptors->GetDetails(modified_descriptor_);
438 DCHECK_EQ(new_kind_, details.kind());
439 DCHECK_EQ(GetDetails(modified_descriptor_).attributes(),
440 details.attributes());
441 DCHECK(IsGeneralizableTo(new_constness_, details.constness()));
442 DCHECK_EQ(new_location_, details.location());
443 DCHECK(new_representation_.fits_into(details.representation()));
444 if (new_location_ == kField) {
445 DCHECK_EQ(kField, details.location());
446 DCHECK(new_field_type_->NowIs(
447 target_descriptors->GetFieldType(modified_descriptor_)));
448 } else {
449 DCHECK(details.location() == kField ||
450 EqualImmutableValues(
451 *new_value_,
452 target_descriptors->GetStrongValue(modified_descriptor_)));
453 }
454 }
455#endif
456 if (*target_map_ != *old_map_) {
457 old_map_->NotifyLeafMapLayoutChange(isolate_);
458 }
459 if (!has_integrity_level_transition_) {
460 result_map_ = target_map_;
461 state_ = kEnd;
462 return state_; // Done.
463 }
464
465 // We try to replay the integrity level transition here.
466 Map transition = TransitionsAccessor(isolate_, target_map_)
467 .SearchSpecial(*integrity_level_symbol_);
468 if (!transition.is_null()) {
469 result_map_ = handle(transition, isolate_);
470 state_ = kEnd;
471 return state_; // Done.
472 }
473 }
474
475 // Find the last compatible target map in the transition tree.
476 for (int i = target_nof; i < old_nof_; ++i) {
477 PropertyDetails old_details = GetDetails(i);
478 Map transition = TransitionsAccessor(isolate_, target_map_)
479 .SearchTransition(GetKey(i), old_details.kind(),
480 old_details.attributes());
481 if (transition.is_null()) break;
482 Handle<Map> tmp_map(transition, isolate_);
483 Handle<DescriptorArray> tmp_descriptors(tmp_map->instance_descriptors(),
484 isolate_);
485#ifdef DEBUG
486 // Check that target map is compatible.
487 PropertyDetails tmp_details = tmp_descriptors->GetDetails(i);
488 DCHECK_EQ(old_details.kind(), tmp_details.kind());
489 DCHECK_EQ(old_details.attributes(), tmp_details.attributes());
490#endif
491 if (old_details.kind() == kAccessor &&
492 !EqualImmutableValues(GetValue(i),
493 tmp_descriptors->GetStrongValue(i))) {
494 return CopyGeneralizeAllFields("GenAll_Incompatible");
495 }
496 DCHECK(!tmp_map->is_deprecated());
497 target_map_ = tmp_map;
498 }
499
500 state_ = kAtTargetMap;
501 return state_; // Not done yet.
502}
503
504Handle<DescriptorArray> MapUpdater::BuildDescriptorArray() {
505 InstanceType instance_type = old_map_->instance_type();
506 int target_nof = target_map_->NumberOfOwnDescriptors();
507 Handle<DescriptorArray> target_descriptors(
508 target_map_->instance_descriptors(), isolate_);
509
510 // Allocate a new descriptor array large enough to hold the required
511 // descriptors, with minimally the exact same size as the old descriptor
512 // array.
513 int new_slack =
514 std::max<int>(old_nof_, old_descriptors_->number_of_descriptors()) -
515 old_nof_;
516 Handle<DescriptorArray> new_descriptors =
517 DescriptorArray::Allocate(isolate_, old_nof_, new_slack);
518 DCHECK(new_descriptors->number_of_all_descriptors() >
519 target_descriptors->number_of_all_descriptors() ||
520 new_descriptors->number_of_slack_descriptors() > 0 ||
521 new_descriptors->number_of_descriptors() ==
522 old_descriptors_->number_of_descriptors());
523 DCHECK(new_descriptors->number_of_descriptors() == old_nof_);
524
525 int root_nof = root_map_->NumberOfOwnDescriptors();
526
527 // Given that we passed root modification check in FindRootMap() so
528 // the root descriptors are either not modified at all or already more
529 // general than we requested. Take |root_nof| entries as is.
530 // 0 -> |root_nof|
531 int current_offset = 0;
532 for (int i = 0; i < root_nof; ++i) {
533 PropertyDetails old_details = old_descriptors_->GetDetails(i);
534 if (old_details.location() == kField) {
535 current_offset += old_details.field_width_in_words();
536 }
537 Descriptor d(handle(GetKey(i), isolate_),
538 MaybeObjectHandle(old_descriptors_->GetValue(i), isolate_),
539 old_details);
540 new_descriptors->Set(i, &d);
541 }
542
543 // Merge "updated" old_descriptor entries with target_descriptor entries.
544 // |root_nof| -> |target_nof|
545 for (int i = root_nof; i < target_nof; ++i) {
546 Handle<Name> key(GetKey(i), isolate_);
547 PropertyDetails old_details = GetDetails(i);
548 PropertyDetails target_details = target_descriptors->GetDetails(i);
549
550 PropertyKind next_kind = old_details.kind();
551 PropertyAttributes next_attributes = old_details.attributes();
552 DCHECK_EQ(next_kind, target_details.kind());
553 DCHECK_EQ(next_attributes, target_details.attributes());
554
555 PropertyConstness next_constness = GeneralizeConstness(
556 old_details.constness(), target_details.constness());
557
558 // Note: failed values equality check does not invalidate per-object
559 // property constness.
560 PropertyLocation next_location =
561 old_details.location() == kField ||
562 target_details.location() == kField ||
563 !EqualImmutableValues(target_descriptors->GetStrongValue(i),
564 GetValue(i))
565 ? kField
566 : kDescriptor;
567
568 if (!FLAG_track_constant_fields && next_location == kField) {
569 next_constness = PropertyConstness::kMutable;
570 }
571 // Ensure that mutable values are stored in fields.
572 DCHECK_IMPLIES(next_constness == PropertyConstness::kMutable,
573 next_location == kField);
574
575 Representation next_representation =
576 old_details.representation().generalize(
577 target_details.representation());
578
579 if (next_location == kField) {
580 Handle<FieldType> old_field_type =
581 GetOrComputeFieldType(i, old_details.location(), next_representation);
582
583 Handle<FieldType> target_field_type =
584 GetOrComputeFieldType(target_descriptors, i,
585 target_details.location(), next_representation);
586
587 Handle<FieldType> next_field_type = Map::GeneralizeFieldType(
588 old_details.representation(), old_field_type, next_representation,
589 target_field_type, isolate_);
590
591 Map::GeneralizeIfCanHaveTransitionableFastElementsKind(
592 isolate_, instance_type, &next_constness, &next_representation,
593 &next_field_type);
594
595 MaybeObjectHandle wrapped_type(
596 Map::WrapFieldType(isolate_, next_field_type));
597 Descriptor d;
598 if (next_kind == kData) {
599 d = Descriptor::DataField(key, current_offset, next_attributes,
600 next_constness, next_representation,
601 wrapped_type);
602 } else {
603 // TODO(ishell): mutable accessors are not implemented yet.
604 UNIMPLEMENTED();
605 }
606 current_offset += d.GetDetails().field_width_in_words();
607 new_descriptors->Set(i, &d);
608 } else {
609 DCHECK_EQ(kDescriptor, next_location);
610 DCHECK_EQ(PropertyConstness::kConst, next_constness);
611
612 Handle<Object> value(GetValue(i), isolate_);
613 Descriptor d;
614 if (next_kind == kData) {
615 DCHECK(!FLAG_track_constant_fields);
616 d = Descriptor::DataConstant(key, value, next_attributes);
617 } else {
618 DCHECK_EQ(kAccessor, next_kind);
619 d = Descriptor::AccessorConstant(key, value, next_attributes);
620 }
621 new_descriptors->Set(i, &d);
622 }
623 }
624
625 // Take "updated" old_descriptor entries.
626 // |target_nof| -> |old_nof|
627 for (int i = target_nof; i < old_nof_; ++i) {
628 PropertyDetails old_details = GetDetails(i);
629 Handle<Name> key(GetKey(i), isolate_);
630
631 PropertyKind next_kind = old_details.kind();
632 PropertyAttributes next_attributes = old_details.attributes();
633 PropertyConstness next_constness = old_details.constness();
634 PropertyLocation next_location = old_details.location();
635 Representation next_representation = old_details.representation();
636
637 Descriptor d;
638 if (next_location == kField) {
639 Handle<FieldType> next_field_type =
640 GetOrComputeFieldType(i, old_details.location(), next_representation);
641
642 // If the |new_elements_kind_| is still transitionable then the old map's
643 // elements kind is also transitionable and therefore the old descriptors
644 // array must already have generalized field type.
645 CHECK_IMPLIES(
646 is_transitionable_fast_elements_kind_,
647 Map::IsMostGeneralFieldType(next_representation, *next_field_type));
648
649 MaybeObjectHandle wrapped_type(
650 Map::WrapFieldType(isolate_, next_field_type));
651 Descriptor d;
652 if (next_kind == kData) {
653 DCHECK_IMPLIES(!FLAG_track_constant_fields,
654 next_constness == PropertyConstness::kMutable);
655 d = Descriptor::DataField(key, current_offset, next_attributes,
656 next_constness, next_representation,
657 wrapped_type);
658 } else {
659 // TODO(ishell): mutable accessors are not implemented yet.
660 UNIMPLEMENTED();
661 }
662 current_offset += d.GetDetails().field_width_in_words();
663 new_descriptors->Set(i, &d);
664 } else {
665 DCHECK_EQ(kDescriptor, next_location);
666 DCHECK_EQ(PropertyConstness::kConst, next_constness);
667
668 Handle<Object> value(GetValue(i), isolate_);
669 if (next_kind == kData) {
670 d = Descriptor::DataConstant(key, value, next_attributes);
671 } else {
672 DCHECK_EQ(kAccessor, next_kind);
673 d = Descriptor::AccessorConstant(key, value, next_attributes);
674 }
675 new_descriptors->Set(i, &d);
676 }
677 }
678
679 new_descriptors->Sort();
680 return new_descriptors;
681}
682
683Handle<Map> MapUpdater::FindSplitMap(Handle<DescriptorArray> descriptors) {
684 DisallowHeapAllocation no_allocation;
685
686 int root_nof = root_map_->NumberOfOwnDescriptors();
687 Map current = *root_map_;
688 for (int i = root_nof; i < old_nof_; i++) {
689 Name name = descriptors->GetKey(i);
690 PropertyDetails details = descriptors->GetDetails(i);
691 Map next =
692 TransitionsAccessor(isolate_, current, &no_allocation)
693 .SearchTransition(name, details.kind(), details.attributes());
694 if (next.is_null()) break;
695 DescriptorArray next_descriptors = next->instance_descriptors();
696
697 PropertyDetails next_details = next_descriptors->GetDetails(i);
698 DCHECK_EQ(details.kind(), next_details.kind());
699 DCHECK_EQ(details.attributes(), next_details.attributes());
700 if (details.constness() != next_details.constness()) break;
701 if (details.location() != next_details.location()) break;
702 if (!details.representation().Equals(next_details.representation())) break;
703
704 if (next_details.location() == kField) {
705 FieldType next_field_type = next_descriptors->GetFieldType(i);
706 if (!descriptors->GetFieldType(i)->NowIs(next_field_type)) {
707 break;
708 }
709 } else {
710 if (!EqualImmutableValues(descriptors->GetStrongValue(i),
711 next_descriptors->GetStrongValue(i))) {
712 break;
713 }
714 }
715 current = next;
716 }
717 return handle(current, isolate_);
718}
719
720MapUpdater::State MapUpdater::ConstructNewMap() {
721 Handle<DescriptorArray> new_descriptors = BuildDescriptorArray();
722
723 Handle<Map> split_map = FindSplitMap(new_descriptors);
724 int split_nof = split_map->NumberOfOwnDescriptors();
725 if (old_nof_ == split_nof) {
726 CHECK(has_integrity_level_transition_);
727 state_ = kAtIntegrityLevelSource;
728 return state_;
729 }
730
731 PropertyDetails split_details = GetDetails(split_nof);
732 TransitionsAccessor transitions(isolate_, split_map);
733
734 // Invalidate a transition target at |key|.
735 Map maybe_transition = transitions.SearchTransition(
736 GetKey(split_nof), split_details.kind(), split_details.attributes());
737 if (!maybe_transition.is_null()) {
738 maybe_transition->DeprecateTransitionTree(isolate_);
739 }
740
741 // If |maybe_transition| is not nullptr then the transition array already
742 // contains entry for given descriptor. This means that the transition
743 // could be inserted regardless of whether transitions array is full or not.
744 if (maybe_transition.is_null() && !transitions.CanHaveMoreTransitions()) {
745 return CopyGeneralizeAllFields("GenAll_CantHaveMoreTransitions");
746 }
747
748 old_map_->NotifyLeafMapLayoutChange(isolate_);
749
750 if (FLAG_trace_generalization && modified_descriptor_ >= 0) {
751 PropertyDetails old_details =
752 old_descriptors_->GetDetails(modified_descriptor_);
753 PropertyDetails new_details =
754 new_descriptors->GetDetails(modified_descriptor_);
755 MaybeHandle<FieldType> old_field_type;
756 MaybeHandle<FieldType> new_field_type;
757 MaybeHandle<Object> old_value;
758 MaybeHandle<Object> new_value;
759 if (old_details.location() == kField) {
760 old_field_type = handle(
761 old_descriptors_->GetFieldType(modified_descriptor_), isolate_);
762 } else {
763 old_value = handle(old_descriptors_->GetStrongValue(modified_descriptor_),
764 isolate_);
765 }
766 if (new_details.location() == kField) {
767 new_field_type =
768 handle(new_descriptors->GetFieldType(modified_descriptor_), isolate_);
769 } else {
770 new_value = handle(new_descriptors->GetStrongValue(modified_descriptor_),
771 isolate_);
772 }
773
774 old_map_->PrintGeneralization(
775 isolate_, stdout, "", modified_descriptor_, split_nof, old_nof_,
776 old_details.location() == kDescriptor && new_location_ == kField,
777 old_details.representation(), new_details.representation(),
778 old_field_type, old_value, new_field_type, new_value);
779 }
780
781 Handle<LayoutDescriptor> new_layout_descriptor =
782 LayoutDescriptor::New(isolate_, split_map, new_descriptors, old_nof_);
783
784 Handle<Map> new_map = Map::AddMissingTransitions(
785 isolate_, split_map, new_descriptors, new_layout_descriptor);
786
787 // Deprecated part of the transition tree is no longer reachable, so replace
788 // current instance descriptors in the "survived" part of the tree with
789 // the new descriptors to maintain descriptors sharing invariant.
790 split_map->ReplaceDescriptors(isolate_, *new_descriptors,
791 *new_layout_descriptor);
792
793 if (has_integrity_level_transition_) {
794 target_map_ = new_map;
795 state_ = kAtIntegrityLevelSource;
796 } else {
797 result_map_ = new_map;
798 state_ = kEnd;
799 }
800 return state_; // Done.
801}
802
803MapUpdater::State MapUpdater::ConstructNewMapWithIntegrityLevelTransition() {
804 DCHECK_EQ(kAtIntegrityLevelSource, state_);
805
806 TransitionsAccessor transitions(isolate_, target_map_);
807 if (!transitions.CanHaveMoreTransitions()) {
808 return CopyGeneralizeAllFields("GenAll_CantHaveMoreTransitions");
809 }
810
811 result_map_ = Map::CopyForPreventExtensions(
812 isolate_, target_map_, integrity_level_, integrity_level_symbol_,
813 "CopyForPreventExtensions");
814
815 state_ = kEnd;
816 return state_;
817}
818
819} // namespace internal
820} // namespace v8
821