map-updater.cc 32.2 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11
// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/map-updater.h"

#include "src/field-type.h"
#include "src/handles.h"
#include "src/isolate.h"
#include "src/objects-inl.h"
#include "src/objects.h"
12
#include "src/property-details.h"
13 14 15 16 17 18 19
#include "src/transitions.h"

namespace v8 {
namespace internal {

namespace {

20
inline bool EqualImmutableValues(Object obj1, Object obj2) {
21 22 23 24 25 26 27
  if (obj1 == obj2) return true;  // Valid for both kData and kAccessor kinds.
  // TODO(ishell): compare AccessorPairs.
  return false;
}

}  // namespace

28 29 30 31 32 33 34 35 36 37 38 39 40 41
MapUpdater::MapUpdater(Isolate* isolate, Handle<Map> old_map)
    : isolate_(isolate),
      old_map_(old_map),
      old_descriptors_(old_map->instance_descriptors(), isolate_),
      old_nof_(old_map_->NumberOfOwnDescriptors()),
      new_elements_kind_(old_map_->elements_kind()),
      is_transitionable_fast_elements_kind_(
          IsTransitionableFastElementsKind(new_elements_kind_)) {
  // We shouldn't try to update remote objects.
  DCHECK(!old_map->FindRootMap(isolate)
              ->GetConstructor()
              ->IsFunctionTemplateInfo());
}

42
Name MapUpdater::GetKey(int descriptor) const {
43 44 45 46 47 48
  return old_descriptors_->GetKey(descriptor);
}

PropertyDetails MapUpdater::GetDetails(int descriptor) const {
  DCHECK_LE(0, descriptor);
  if (descriptor == modified_descriptor_) {
49 50 51 52 53 54 55 56 57 58
    PropertyAttributes attributes = new_attributes_;
    // If the original map was sealed or frozen, let us used the old
    // attributes so that we follow the same transition path as before.
    // Note that the user could not have changed the attributes because
    // both seal and freeze make the properties non-configurable.
    if (integrity_level_ == SEALED || integrity_level_ == FROZEN) {
      attributes = old_descriptors_->GetDetails(descriptor).attributes();
    }
    return PropertyDetails(new_kind_, attributes, new_location_, new_constness_,
                           new_representation_);
59 60 61 62
  }
  return old_descriptors_->GetDetails(descriptor);
}

63
Object MapUpdater::GetValue(int descriptor) const {
64 65 66 67 68 69
  DCHECK_LE(0, descriptor);
  if (descriptor == modified_descriptor_) {
    DCHECK_EQ(kDescriptor, new_location_);
    return *new_value_;
  }
  DCHECK_EQ(kDescriptor, GetDetails(descriptor).location());
70
  return old_descriptors_->GetStrongValue(descriptor);
71 72
}

73
FieldType MapUpdater::GetFieldType(int descriptor) const {
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103
  DCHECK_LE(0, descriptor);
  if (descriptor == modified_descriptor_) {
    DCHECK_EQ(kField, new_location_);
    return *new_field_type_;
  }
  DCHECK_EQ(kField, GetDetails(descriptor).location());
  return old_descriptors_->GetFieldType(descriptor);
}

Handle<FieldType> MapUpdater::GetOrComputeFieldType(
    int descriptor, PropertyLocation location,
    Representation representation) const {
  DCHECK_LE(0, descriptor);
  // |location| is just a pre-fetched GetDetails(descriptor).location().
  DCHECK_EQ(location, GetDetails(descriptor).location());
  if (location == kField) {
    return handle(GetFieldType(descriptor), isolate_);
  } else {
    return GetValue(descriptor)->OptimalType(isolate_, representation);
  }
}

Handle<FieldType> MapUpdater::GetOrComputeFieldType(
    Handle<DescriptorArray> descriptors, int descriptor,
    PropertyLocation location, Representation representation) {
  // |location| is just a pre-fetched GetDetails(descriptor).location().
  DCHECK_EQ(descriptors->GetDetails(descriptor).location(), location);
  if (location == kField) {
    return handle(descriptors->GetFieldType(descriptor), isolate_);
  } else {
104
    return descriptors->GetStrongValue(descriptor)
105 106 107 108 109 110
        ->OptimalType(isolate_, representation);
  }
}

Handle<Map> MapUpdater::ReconfigureToDataField(int descriptor,
                                               PropertyAttributes attributes,
111
                                               PropertyConstness constness,
112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
                                               Representation representation,
                                               Handle<FieldType> field_type) {
  DCHECK_EQ(kInitialized, state_);
  DCHECK_LE(0, descriptor);
  DCHECK(!old_map_->is_dictionary_map());
  modified_descriptor_ = descriptor;
  new_kind_ = kData;
  new_attributes_ = attributes;
  new_location_ = kField;

  PropertyDetails old_details =
      old_descriptors_->GetDetails(modified_descriptor_);

  // If property kind is not reconfigured merge the result with
  // representation/field type from the old descriptor.
  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 134 135 136

    Handle<FieldType> old_field_type =
        GetOrComputeFieldType(old_descriptors_, modified_descriptor_,
                              old_details.location(), new_representation_);

137 138 139 140 141 142 143
    new_field_type_ =
        Map::GeneralizeFieldType(old_representation, old_field_type,
                                 new_representation_, field_type, isolate_);
  } else {
    // We don't know if this is a first property kind reconfiguration
    // and we don't know which value was in this property previously
    // therefore we can't treat such a property as constant.
144
    new_constness_ = PropertyConstness::kMutable;
145 146
    new_representation_ = representation;
    new_field_type_ = field_type;
147 148
  }

149 150 151
  Map::GeneralizeIfCanHaveTransitionableFastElementsKind(
      isolate_, old_map_->instance_type(), &new_constness_,
      &new_representation_, &new_field_type_);
152

153
  if (TryReconfigureToDataFieldInplace() == kEnd) return result_map_;
154 155
  if (FindRootMap() == kEnd) return result_map_;
  if (FindTargetMap() == kEnd) return result_map_;
156 157 158
  if (ConstructNewMap() == kAtIntegrityLevelSource) {
    ConstructNewMapWithIntegrityLevelTransition();
  }
159 160 161 162 163 164 165
  DCHECK_EQ(kEnd, state_);
  return result_map_;
}

Handle<Map> MapUpdater::ReconfigureElementsKind(ElementsKind elements_kind) {
  DCHECK_EQ(kInitialized, state_);
  new_elements_kind_ = elements_kind;
166 167
  is_transitionable_fast_elements_kind_ =
      IsTransitionableFastElementsKind(new_elements_kind_);
168 169 170

  if (FindRootMap() == kEnd) return result_map_;
  if (FindTargetMap() == kEnd) return result_map_;
171 172 173
  if (ConstructNewMap() == kAtIntegrityLevelSource) {
    ConstructNewMapWithIntegrityLevelTransition();
  }
174 175 176 177 178 179 180 181 182 183
  DCHECK_EQ(kEnd, state_);
  return result_map_;
}

Handle<Map> MapUpdater::Update() {
  DCHECK_EQ(kInitialized, state_);
  DCHECK(old_map_->is_deprecated());

  if (FindRootMap() == kEnd) return result_map_;
  if (FindTargetMap() == kEnd) return result_map_;
184 185 186
  if (ConstructNewMap() == kAtIntegrityLevelSource) {
    ConstructNewMapWithIntegrityLevelTransition();
  }
187
  DCHECK_EQ(kEnd, state_);
188 189 190
  if (FLAG_fast_map_update) {
    TransitionsAccessor(isolate_, old_map_).SetMigrationTarget(*result_map_);
  }
191 192 193
  return result_map_;
}

194 195 196 197
void MapUpdater::GeneralizeField(Handle<Map> map, int modify_index,
                                 PropertyConstness new_constness,
                                 Representation new_representation,
                                 Handle<FieldType> new_field_type) {
198 199
  Map::GeneralizeField(isolate_, map, modify_index, new_constness,
                       new_representation, new_field_type);
200

201 202
  DCHECK(*old_descriptors_ == old_map_->instance_descriptors() ||
         *old_descriptors_ == integrity_source_map_->instance_descriptors());
203 204
}

205
MapUpdater::State MapUpdater::CopyGeneralizeAllFields(const char* reason) {
206 207 208
  result_map_ = Map::CopyGeneralizeAllFields(
      isolate_, old_map_, new_elements_kind_, modified_descriptor_, new_kind_,
      new_attributes_, reason);
209 210 211 212
  state_ = kEnd;
  return state_;  // Done.
}

213
MapUpdater::State MapUpdater::TryReconfigureToDataFieldInplace() {
214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234
  // If it's just a representation generalization case (i.e. property kind and
  // attributes stays unchanged) it's fine to transition from None to anything
  // but double without any modification to the object, because the default
  // uninitialized value for representation None can be overwritten by both
  // smi and tagged values. Doubles, however, would require a box allocation.
  if (new_representation_.IsNone() || new_representation_.IsDouble()) {
    return state_;  // Not done yet.
  }

  PropertyDetails old_details =
      old_descriptors_->GetDetails(modified_descriptor_);
  Representation old_representation = old_details.representation();
  if (!old_representation.IsNone()) {
    return state_;  // Not done yet.
  }

  DCHECK_EQ(new_kind_, old_details.kind());
  DCHECK_EQ(new_attributes_, old_details.attributes());
  DCHECK_EQ(kField, old_details.location());
  if (FLAG_trace_generalization) {
    old_map_->PrintGeneralization(
235 236
        isolate_, stdout, "uninitialized field", modified_descriptor_, old_nof_,
        old_nof_, false, old_representation, new_representation_,
237 238 239
        handle(old_descriptors_->GetFieldType(modified_descriptor_), isolate_),
        MaybeHandle<Object>(), new_field_type_, MaybeHandle<Object>());
  }
240 241
  Handle<Map> field_owner(
      old_map_->FindFieldOwner(isolate_, modified_descriptor_), isolate_);
242

243 244
  GeneralizeField(field_owner, modified_descriptor_, new_constness_,
                  new_representation_, new_field_type_);
245 246 247 248 249 250 251 252 253 254 255 256
  // Check that the descriptor array was updated.
  DCHECK(old_descriptors_->GetDetails(modified_descriptor_)
             .representation()
             .Equals(new_representation_));
  DCHECK(old_descriptors_->GetFieldType(modified_descriptor_)
             ->NowIs(new_field_type_));

  result_map_ = old_map_;
  state_ = kEnd;
  return state_;  // Done.
}

257
bool MapUpdater::TrySaveIntegrityLevelTransitions() {
258 259 260 261 262 263 264 265 266 267 268 269 270 271
  // Figure out the most restrictive integrity level transition (it should
  // be the last one in the transition tree).
  Handle<Map> previous =
      handle(Map::cast(old_map_->GetBackPointer()), isolate_);
  Symbol integrity_level_symbol;
  TransitionsAccessor last_transitions(isolate_, previous);
  if (!last_transitions.HasIntegrityLevelTransitionTo(
          *old_map_, &integrity_level_symbol, &integrity_level_)) {
    // The last transition was not integrity level transition - just bail out.
    // This can happen in the following cases:
    // - there are private symbol transitions following the integrity level
    //   transitions (see crbug.com/v8/8854).
    // - there is a getter added in addition to an existing setter (or a setter
    //   in addition to an existing getter).
272 273
    return false;
  }
274 275
  integrity_level_symbol_ = handle(integrity_level_symbol, isolate_);
  integrity_source_map_ = previous;
276

277 278 279 280 281 282 283 284 285 286 287
  // Now walk up the back pointer chain and skip all integrity level
  // transitions. If we encounter any non-integrity level transition interleaved
  // with integrity level transitions, just bail out.
  while (!integrity_source_map_->is_extensible()) {
    previous =
        handle(Map::cast(integrity_source_map_->GetBackPointer()), isolate_);
    TransitionsAccessor transitions(isolate_, previous);
    if (!transitions.HasIntegrityLevelTransitionTo(*integrity_source_map_)) {
      return false;
    }
    integrity_source_map_ = previous;
288
  }
289

290 291 292 293
  // Integrity-level transitions never change number of descriptors.
  CHECK_EQ(old_map_->NumberOfOwnDescriptors(),
           integrity_source_map_->NumberOfOwnDescriptors());

294 295 296
  has_integrity_level_transition_ = true;
  old_descriptors_ =
      handle(integrity_source_map_->instance_descriptors(), isolate_);
297
  return true;
298 299
}

300 301 302
MapUpdater::State MapUpdater::FindRootMap() {
  DCHECK_EQ(kInitialized, state_);
  // Check the state of the root map.
303
  root_map_ = handle(old_map_->FindRootMap(isolate_), isolate_);
304 305
  ElementsKind from_kind = root_map_->elements_kind();
  ElementsKind to_kind = new_elements_kind_;
306

307 308 309 310
  if (root_map_->is_deprecated()) {
    state_ = kEnd;
    result_map_ = handle(
        JSFunction::cast(root_map_->GetConstructor())->initial_map(), isolate_);
311
    result_map_ = Map::AsElementsKind(isolate_, result_map_, to_kind);
312 313 314
    DCHECK(result_map_->is_dictionary_map());
    return state_;
  }
315

316
  if (!old_map_->EquivalentToForTransition(*root_map_)) {
317
    return CopyGeneralizeAllFields("GenAll_NotEquivalent");
318 319 320 321 322
  } else if (old_map_->is_extensible() != root_map_->is_extensible()) {
    DCHECK(!old_map_->is_extensible());
    DCHECK(root_map_->is_extensible());
    // We have an integrity level transition in the tree, let us make a note
    // of that transition to be able to replay it later.
323 324 325
    if (!TrySaveIntegrityLevelTransitions()) {
      return CopyGeneralizeAllFields("GenAll_PrivateSymbolsOnNonExtensible");
    }
326 327 328 329

    // We want to build transitions to the original element kind (before
    // the seal transitions), so change {to_kind} accordingly.
    DCHECK(to_kind == DICTIONARY_ELEMENTS ||
330
           to_kind == SLOW_STRING_WRAPPER_ELEMENTS ||
331 332
           IsFixedTypedArrayElementsKind(to_kind));
    to_kind = integrity_source_map_->elements_kind();
333 334 335 336 337 338 339 340
  }

  // TODO(ishell): Add a test for SLOW_SLOPPY_ARGUMENTS_ELEMENTS.
  if (from_kind != to_kind && to_kind != DICTIONARY_ELEMENTS &&
      to_kind != SLOW_STRING_WRAPPER_ELEMENTS &&
      to_kind != SLOW_SLOPPY_ARGUMENTS_ELEMENTS &&
      !(IsTransitionableFastElementsKind(from_kind) &&
        IsMoreGeneralElementsKindTransition(from_kind, to_kind))) {
341
    return CopyGeneralizeAllFields("GenAll_InvalidElementsTransition");
342 343
  }

344
  int root_nof = root_map_->NumberOfOwnDescriptors();
345 346 347 348 349
  if (modified_descriptor_ >= 0 && modified_descriptor_ < root_nof) {
    PropertyDetails old_details =
        old_descriptors_->GetDetails(modified_descriptor_);
    if (old_details.kind() != new_kind_ ||
        old_details.attributes() != new_attributes_) {
350
      return CopyGeneralizeAllFields("GenAll_RootModification1");
351
    }
352
    if (old_details.location() != kField) {
353
      return CopyGeneralizeAllFields("GenAll_RootModification2");
354
    }
355
    if (new_constness_ != old_details.constness() && !FLAG_modify_map_inplace) {
356
      return CopyGeneralizeAllFields("GenAll_RootModification3");
357
    }
358 359 360 361
    if (!new_representation_.fits_into(old_details.representation())) {
      return CopyGeneralizeAllFields("GenAll_RootModification4");
    }

362 363 364
    DCHECK_EQ(kData, old_details.kind());
    DCHECK_EQ(kData, new_kind_);
    DCHECK_EQ(kField, new_location_);
365
    FieldType old_field_type =
366 367
        old_descriptors_->GetFieldType(modified_descriptor_);
    if (!new_field_type_->NowIs(old_field_type)) {
368
      return CopyGeneralizeAllFields("GenAll_RootModification5");
369
    }
370 371 372 373 374 375 376 377

    // Modify root map in-place.
    if (FLAG_modify_map_inplace && new_constness_ != old_details.constness()) {
      DCHECK(IsGeneralizableTo(old_details.constness(), new_constness_));
      GeneralizeField(old_map_, modified_descriptor_, new_constness_,
                      old_details.representation(),
                      handle(old_field_type, isolate_));
    }
378 379 380
  }

  // From here on, use the map with correct elements kind as root map.
381
  root_map_ = Map::AsElementsKind(isolate_, root_map_, to_kind);
382 383 384 385 386 387 388 389 390 391 392
  state_ = kAtRootMap;
  return state_;  // Not done yet.
}

MapUpdater::State MapUpdater::FindTargetMap() {
  DCHECK_EQ(kAtRootMap, state_);
  target_map_ = root_map_;

  int root_nof = root_map_->NumberOfOwnDescriptors();
  for (int i = root_nof; i < old_nof_; ++i) {
    PropertyDetails old_details = GetDetails(i);
393 394 395 396
    Map transition = TransitionsAccessor(isolate_, target_map_)
                         .SearchTransition(GetKey(i), old_details.kind(),
                                           old_details.attributes());
    if (transition.is_null()) break;
397 398 399 400 401 402 403 404 405 406
    Handle<Map> tmp_map(transition, isolate_);

    Handle<DescriptorArray> tmp_descriptors(tmp_map->instance_descriptors(),
                                            isolate_);

    // Check if target map is incompatible.
    PropertyDetails tmp_details = tmp_descriptors->GetDetails(i);
    DCHECK_EQ(old_details.kind(), tmp_details.kind());
    DCHECK_EQ(old_details.attributes(), tmp_details.attributes());
    if (old_details.kind() == kAccessor &&
407 408
        !EqualImmutableValues(GetValue(i),
                              tmp_descriptors->GetStrongValue(i))) {
409
      // TODO(ishell): mutable accessors are not implemented yet.
410
      return CopyGeneralizeAllFields("GenAll_Incompatible");
411
    }
412
    PropertyConstness tmp_constness = tmp_details.constness();
413 414
    if (!FLAG_modify_map_inplace &&
        !IsGeneralizableTo(old_details.constness(), tmp_constness)) {
415 416 417
      break;
    }
    if (!IsGeneralizableTo(old_details.location(), tmp_details.location())) {
418 419 420 421 422 423 424 425 426 427
      break;
    }
    Representation tmp_representation = tmp_details.representation();
    if (!old_details.representation().fits_into(tmp_representation)) {
      break;
    }

    if (tmp_details.location() == kField) {
      Handle<FieldType> old_field_type =
          GetOrComputeFieldType(i, old_details.location(), tmp_representation);
428 429 430
      PropertyConstness constness =
          FLAG_modify_map_inplace ? old_details.constness() : tmp_constness;
      GeneralizeField(tmp_map, i, constness, tmp_representation,
431
                      old_field_type);
432 433
    } else {
      // kDescriptor: Check that the value matches.
434 435
      if (!EqualImmutableValues(GetValue(i),
                                tmp_descriptors->GetStrongValue(i))) {
436 437 438 439 440 441 442 443 444 445 446 447
        break;
      }
    }
    DCHECK(!tmp_map->is_deprecated());
    target_map_ = tmp_map;
  }

  // Directly change the map if the target map is more general.
  int target_nof = target_map_->NumberOfOwnDescriptors();
  if (target_nof == old_nof_) {
#ifdef DEBUG
    if (modified_descriptor_ >= 0) {
448
      DescriptorArray target_descriptors = target_map_->instance_descriptors();
449 450 451
      PropertyDetails details =
          target_descriptors->GetDetails(modified_descriptor_);
      DCHECK_EQ(new_kind_, details.kind());
452 453
      DCHECK_EQ(GetDetails(modified_descriptor_).attributes(),
                details.attributes());
454
      DCHECK(IsGeneralizableTo(new_constness_, details.constness()));
455 456 457 458 459 460 461 462
      DCHECK_EQ(new_location_, details.location());
      DCHECK(new_representation_.fits_into(details.representation()));
      if (new_location_ == kField) {
        DCHECK_EQ(kField, details.location());
        DCHECK(new_field_type_->NowIs(
            target_descriptors->GetFieldType(modified_descriptor_)));
      } else {
        DCHECK(details.location() == kField ||
463 464 465
               EqualImmutableValues(
                   *new_value_,
                   target_descriptors->GetStrongValue(modified_descriptor_)));
466 467 468 469
      }
    }
#endif
    if (*target_map_ != *old_map_) {
470
      old_map_->NotifyLeafMapLayoutChange(isolate_);
471
    }
472 473 474 475 476 477 478 479 480 481 482 483 484 485
    if (!has_integrity_level_transition_) {
      result_map_ = target_map_;
      state_ = kEnd;
      return state_;  // Done.
    }

    // We try to replay the integrity level transition here.
    Map transition = TransitionsAccessor(isolate_, target_map_)
                         .SearchSpecial(*integrity_level_symbol_);
    if (!transition.is_null()) {
      result_map_ = handle(transition, isolate_);
      state_ = kEnd;
      return state_;  // Done.
    }
486 487 488 489 490
  }

  // Find the last compatible target map in the transition tree.
  for (int i = target_nof; i < old_nof_; ++i) {
    PropertyDetails old_details = GetDetails(i);
491 492 493 494
    Map transition = TransitionsAccessor(isolate_, target_map_)
                         .SearchTransition(GetKey(i), old_details.kind(),
                                           old_details.attributes());
    if (transition.is_null()) break;
495 496 497 498 499 500 501 502 503 504
    Handle<Map> tmp_map(transition, isolate_);
    Handle<DescriptorArray> tmp_descriptors(tmp_map->instance_descriptors(),
                                            isolate_);
#ifdef DEBUG
    // Check that target map is compatible.
    PropertyDetails tmp_details = tmp_descriptors->GetDetails(i);
    DCHECK_EQ(old_details.kind(), tmp_details.kind());
    DCHECK_EQ(old_details.attributes(), tmp_details.attributes());
#endif
    if (old_details.kind() == kAccessor &&
505 506
        !EqualImmutableValues(GetValue(i),
                              tmp_descriptors->GetStrongValue(i))) {
507
      return CopyGeneralizeAllFields("GenAll_Incompatible");
508 509 510 511 512 513 514 515 516 517
    }
    DCHECK(!tmp_map->is_deprecated());
    target_map_ = tmp_map;
  }

  state_ = kAtTargetMap;
  return state_;  // Not done yet.
}

Handle<DescriptorArray> MapUpdater::BuildDescriptorArray() {
518
  InstanceType instance_type = old_map_->instance_type();
519 520 521 522 523 524 525 526
  int target_nof = target_map_->NumberOfOwnDescriptors();
  Handle<DescriptorArray> target_descriptors(
      target_map_->instance_descriptors(), isolate_);

  // Allocate a new descriptor array large enough to hold the required
  // descriptors, with minimally the exact same size as the old descriptor
  // array.
  int new_slack =
527 528
      std::max<int>(old_nof_, old_descriptors_->number_of_descriptors()) -
      old_nof_;
529 530
  Handle<DescriptorArray> new_descriptors =
      DescriptorArray::Allocate(isolate_, old_nof_, new_slack);
531 532 533
  DCHECK(new_descriptors->number_of_all_descriptors() >
             target_descriptors->number_of_all_descriptors() ||
         new_descriptors->number_of_slack_descriptors() > 0 ||
534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550
         new_descriptors->number_of_descriptors() ==
             old_descriptors_->number_of_descriptors());
  DCHECK(new_descriptors->number_of_descriptors() == old_nof_);

  int root_nof = root_map_->NumberOfOwnDescriptors();

  // Given that we passed root modification check in FindRootMap() so
  // the root descriptors are either not modified at all or already more
  // general than we requested. Take |root_nof| entries as is.
  // 0 -> |root_nof|
  int current_offset = 0;
  for (int i = 0; i < root_nof; ++i) {
    PropertyDetails old_details = old_descriptors_->GetDetails(i);
    if (old_details.location() == kField) {
      current_offset += old_details.field_width_in_words();
    }
    Descriptor d(handle(GetKey(i), isolate_),
551 552
                 MaybeObjectHandle(old_descriptors_->GetValue(i), isolate_),
                 old_details);
553 554 555 556 557 558 559 560 561 562 563 564
    new_descriptors->Set(i, &d);
  }

  // Merge "updated" old_descriptor entries with target_descriptor entries.
  // |root_nof| -> |target_nof|
  for (int i = root_nof; i < target_nof; ++i) {
    Handle<Name> key(GetKey(i), isolate_);
    PropertyDetails old_details = GetDetails(i);
    PropertyDetails target_details = target_descriptors->GetDetails(i);

    PropertyKind next_kind = old_details.kind();
    PropertyAttributes next_attributes = old_details.attributes();
565 566 567 568 569 570 571 572
    DCHECK_EQ(next_kind, target_details.kind());
    DCHECK_EQ(next_attributes, target_details.attributes());

    PropertyConstness next_constness = GeneralizeConstness(
        old_details.constness(), target_details.constness());

    // Note: failed values equality check does not invalidate per-object
    // property constness.
573 574 575
    PropertyLocation next_location =
        old_details.location() == kField ||
                target_details.location() == kField ||
576
                !EqualImmutableValues(target_descriptors->GetStrongValue(i),
577 578 579 580
                                      GetValue(i))
            ? kField
            : kDescriptor;

581
    if (!FLAG_track_constant_fields && next_location == kField) {
582
      next_constness = PropertyConstness::kMutable;
583
    }
584
    // Ensure that mutable values are stored in fields.
585 586
    DCHECK_IMPLIES(next_constness == PropertyConstness::kMutable,
                   next_location == kField);
587

588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603
    Representation next_representation =
        old_details.representation().generalize(
            target_details.representation());

    if (next_location == kField) {
      Handle<FieldType> old_field_type =
          GetOrComputeFieldType(i, old_details.location(), next_representation);

      Handle<FieldType> target_field_type =
          GetOrComputeFieldType(target_descriptors, i,
                                target_details.location(), next_representation);

      Handle<FieldType> next_field_type = Map::GeneralizeFieldType(
          old_details.representation(), old_field_type, next_representation,
          target_field_type, isolate_);

604 605
      Map::GeneralizeIfCanHaveTransitionableFastElementsKind(
          isolate_, instance_type, &next_constness, &next_representation,
606
          &next_field_type);
607

608 609
      MaybeObjectHandle wrapped_type(
          Map::WrapFieldType(isolate_, next_field_type));
610 611
      Descriptor d;
      if (next_kind == kData) {
612 613 614
        d = Descriptor::DataField(key, current_offset, next_attributes,
                                  next_constness, next_representation,
                                  wrapped_type);
615 616 617 618 619 620 621 622
      } else {
        // TODO(ishell): mutable accessors are not implemented yet.
        UNIMPLEMENTED();
      }
      current_offset += d.GetDetails().field_width_in_words();
      new_descriptors->Set(i, &d);
    } else {
      DCHECK_EQ(kDescriptor, next_location);
623
      DCHECK_EQ(PropertyConstness::kConst, next_constness);
624 625 626 627

      Handle<Object> value(GetValue(i), isolate_);
      Descriptor d;
      if (next_kind == kData) {
628
        DCHECK(!FLAG_track_constant_fields);
629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645
        d = Descriptor::DataConstant(key, value, next_attributes);
      } else {
        DCHECK_EQ(kAccessor, next_kind);
        d = Descriptor::AccessorConstant(key, value, next_attributes);
      }
      new_descriptors->Set(i, &d);
    }
  }

  // Take "updated" old_descriptor entries.
  // |target_nof| -> |old_nof|
  for (int i = target_nof; i < old_nof_; ++i) {
    PropertyDetails old_details = GetDetails(i);
    Handle<Name> key(GetKey(i), isolate_);

    PropertyKind next_kind = old_details.kind();
    PropertyAttributes next_attributes = old_details.attributes();
646
    PropertyConstness next_constness = old_details.constness();
647 648 649 650 651
    PropertyLocation next_location = old_details.location();
    Representation next_representation = old_details.representation();

    Descriptor d;
    if (next_location == kField) {
652
      Handle<FieldType> next_field_type =
653 654
          GetOrComputeFieldType(i, old_details.location(), next_representation);

655 656
      // If the |new_elements_kind_| is still transitionable then the old map's
      // elements kind is also transitionable and therefore the old descriptors
657 658 659 660
      // array must already have generalized field type.
      CHECK_IMPLIES(
          is_transitionable_fast_elements_kind_,
          Map::IsMostGeneralFieldType(next_representation, *next_field_type));
661

662 663
      MaybeObjectHandle wrapped_type(
          Map::WrapFieldType(isolate_, next_field_type));
664 665
      Descriptor d;
      if (next_kind == kData) {
666 667
        DCHECK_IMPLIES(!FLAG_track_constant_fields,
                       next_constness == PropertyConstness::kMutable);
668 669 670
        d = Descriptor::DataField(key, current_offset, next_attributes,
                                  next_constness, next_representation,
                                  wrapped_type);
671 672 673 674 675 676 677 678
      } else {
        // TODO(ishell): mutable accessors are not implemented yet.
        UNIMPLEMENTED();
      }
      current_offset += d.GetDetails().field_width_in_words();
      new_descriptors->Set(i, &d);
    } else {
      DCHECK_EQ(kDescriptor, next_location);
679
      DCHECK_EQ(PropertyConstness::kConst, next_constness);
680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699

      Handle<Object> value(GetValue(i), isolate_);
      if (next_kind == kData) {
        d = Descriptor::DataConstant(key, value, next_attributes);
      } else {
        DCHECK_EQ(kAccessor, next_kind);
        d = Descriptor::AccessorConstant(key, value, next_attributes);
      }
      new_descriptors->Set(i, &d);
    }
  }

  new_descriptors->Sort();
  return new_descriptors;
}

Handle<Map> MapUpdater::FindSplitMap(Handle<DescriptorArray> descriptors) {
  DisallowHeapAllocation no_allocation;

  int root_nof = root_map_->NumberOfOwnDescriptors();
700
  Map current = *root_map_;
701
  for (int i = root_nof; i < old_nof_; i++) {
702
    Name name = descriptors->GetKey(i);
703
    PropertyDetails details = descriptors->GetDetails(i);
704
    Map next =
705
        TransitionsAccessor(isolate_, current, &no_allocation)
706
            .SearchTransition(name, details.kind(), details.attributes());
707
    if (next.is_null()) break;
708
    DescriptorArray next_descriptors = next->instance_descriptors();
709 710 711 712

    PropertyDetails next_details = next_descriptors->GetDetails(i);
    DCHECK_EQ(details.kind(), next_details.kind());
    DCHECK_EQ(details.attributes(), next_details.attributes());
713
    if (details.constness() != next_details.constness()) break;
714 715 716 717
    if (details.location() != next_details.location()) break;
    if (!details.representation().Equals(next_details.representation())) break;

    if (next_details.location() == kField) {
718
      FieldType next_field_type = next_descriptors->GetFieldType(i);
719 720 721 722
      if (!descriptors->GetFieldType(i)->NowIs(next_field_type)) {
        break;
      }
    } else {
723 724
      if (!EqualImmutableValues(descriptors->GetStrongValue(i),
                                next_descriptors->GetStrongValue(i))) {
725 726 727 728 729 730 731 732 733 734 735 736 737
        break;
      }
    }
    current = next;
  }
  return handle(current, isolate_);
}

MapUpdater::State MapUpdater::ConstructNewMap() {
  Handle<DescriptorArray> new_descriptors = BuildDescriptorArray();

  Handle<Map> split_map = FindSplitMap(new_descriptors);
  int split_nof = split_map->NumberOfOwnDescriptors();
738 739 740 741 742
  if (old_nof_ == split_nof) {
    CHECK(has_integrity_level_transition_);
    state_ = kAtIntegrityLevelSource;
    return state_;
  }
743 744

  PropertyDetails split_details = GetDetails(split_nof);
745
  TransitionsAccessor transitions(isolate_, split_map);
746 747

  // Invalidate a transition target at |key|.
748
  Map maybe_transition = transitions.SearchTransition(
749
      GetKey(split_nof), split_details.kind(), split_details.attributes());
750
  if (!maybe_transition.is_null()) {
751
    maybe_transition->DeprecateTransitionTree(isolate_);
752 753
  }

754
  // If |maybe_transition| is not nullptr then the transition array already
755 756
  // contains entry for given descriptor. This means that the transition
  // could be inserted regardless of whether transitions array is full or not.
757
  if (maybe_transition.is_null() && !transitions.CanHaveMoreTransitions()) {
758
    return CopyGeneralizeAllFields("GenAll_CantHaveMoreTransitions");
759 760
  }

761
  old_map_->NotifyLeafMapLayoutChange(isolate_);
762 763 764 765 766 767 768 769 770 771

  if (FLAG_trace_generalization && modified_descriptor_ >= 0) {
    PropertyDetails old_details =
        old_descriptors_->GetDetails(modified_descriptor_);
    PropertyDetails new_details =
        new_descriptors->GetDetails(modified_descriptor_);
    MaybeHandle<FieldType> old_field_type;
    MaybeHandle<FieldType> new_field_type;
    MaybeHandle<Object> old_value;
    MaybeHandle<Object> new_value;
772
    if (old_details.location() == kField) {
773 774 775
      old_field_type = handle(
          old_descriptors_->GetFieldType(modified_descriptor_), isolate_);
    } else {
776 777
      old_value = handle(old_descriptors_->GetStrongValue(modified_descriptor_),
                         isolate_);
778
    }
779
    if (new_details.location() == kField) {
780 781 782
      new_field_type =
          handle(new_descriptors->GetFieldType(modified_descriptor_), isolate_);
    } else {
783 784
      new_value = handle(new_descriptors->GetStrongValue(modified_descriptor_),
                         isolate_);
785 786 787
    }

    old_map_->PrintGeneralization(
788
        isolate_, stdout, "", modified_descriptor_, split_nof, old_nof_,
789 790 791 792 793 794
        old_details.location() == kDescriptor && new_location_ == kField,
        old_details.representation(), new_details.representation(),
        old_field_type, old_value, new_field_type, new_value);
  }

  Handle<LayoutDescriptor> new_layout_descriptor =
795
      LayoutDescriptor::New(isolate_, split_map, new_descriptors, old_nof_);
796

797 798
  Handle<Map> new_map = Map::AddMissingTransitions(
      isolate_, split_map, new_descriptors, new_layout_descriptor);
799 800 801 802

  // Deprecated part of the transition tree is no longer reachable, so replace
  // current instance descriptors in the "survived" part of the tree with
  // the new descriptors to maintain descriptors sharing invariant.
803 804
  split_map->ReplaceDescriptors(isolate_, *new_descriptors,
                                *new_layout_descriptor);
805

806 807 808 809 810 811 812
  if (has_integrity_level_transition_) {
    target_map_ = new_map;
    state_ = kAtIntegrityLevelSource;
  } else {
    result_map_ = new_map;
    state_ = kEnd;
  }
813 814 815
  return state_;  // Done.
}

816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831
MapUpdater::State MapUpdater::ConstructNewMapWithIntegrityLevelTransition() {
  DCHECK_EQ(kAtIntegrityLevelSource, state_);

  TransitionsAccessor transitions(isolate_, target_map_);
  if (!transitions.CanHaveMoreTransitions()) {
    return CopyGeneralizeAllFields("GenAll_CantHaveMoreTransitions");
  }

  result_map_ = Map::CopyForPreventExtensions(
      isolate_, target_map_, integrity_level_, integrity_level_symbol_,
      "CopyForPreventExtensions");

  state_ = kEnd;
  return state_;
}

832 833
}  // namespace internal
}  // namespace v8