transitions.cc 25.6 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include "src/transitions.h"
6

7
#include "src/objects-inl.h"
8 9
#include "src/transitions-inl.h"
#include "src/utils.h"
10 11 12 13

namespace v8 {
namespace internal {

14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
void TransitionsAccessor::Initialize() {
  raw_transitions_ = map_->raw_transitions();
  if (raw_transitions_->IsSmi()) {
    encoding_ = kUninitialized;
  } else if (HeapObject::cast(raw_transitions_)->IsWeakCell()) {
    encoding_ = kWeakCell;
  } else if (HeapObject::cast(raw_transitions_)->IsTuple3()) {
    encoding_ = kTuple3Handler;
  } else if (HeapObject::cast(raw_transitions_)->IsFixedArray()) {
    encoding_ = kFixedArrayHandler;
  } else if (HeapObject::cast(raw_transitions_)->IsTransitionArray()) {
    encoding_ = kFullTransitionArray;
  } else {
    DCHECK(HeapObject::cast(raw_transitions_)->IsPrototypeInfo());
    encoding_ = kPrototypeInfo;
  }
  target_cell_ = nullptr;
#if DEBUG
  needs_reload_ = false;
#endif
}
35

36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
Map* TransitionsAccessor::GetSimpleTransition() {
  switch (encoding()) {
    case kWeakCell:
      return Map::cast(GetTargetCell<kWeakCell>()->value());
    case kTuple3Handler:
      return Map::cast(GetTargetCell<kTuple3Handler>()->value());
    case kFixedArrayHandler:
      return Map::cast(GetTargetCell<kFixedArrayHandler>()->value());
    default:
      return nullptr;
  }
}

bool TransitionsAccessor::HasSimpleTransitionTo(WeakCell* cell) {
  DCHECK(cell->value()->IsMap());
  switch (encoding()) {
    case kWeakCell:
      return raw_transitions_ == cell;
    case kTuple3Handler:
      return StoreHandler::GetTuple3TransitionCell(raw_transitions_) == cell;
    case kFixedArrayHandler:
      return StoreHandler::GetArrayTransitionCell(raw_transitions_) == cell;
    case kPrototypeInfo:
    case kUninitialized:
    case kFullTransitionArray:
      return false;
  }
  UNREACHABLE();
  return false;  // Make GCC happy.
}

void TransitionsAccessor::Insert(Handle<Name> name, Handle<Map> target,
                                 SimpleTransitionFlag flag) {
  DCHECK(!map_handle_.is_null());
  Isolate* isolate = map_->GetIsolate();
  target->SetBackPointer(map_);
72 73

  // If the map doesn't have any transitions at all yet, install the new one.
74
  if (encoding() == kUninitialized) {
75
    if (flag == SIMPLE_PROPERTY_TRANSITION) {
76
      ReplaceTransitions(*Map::WeakCellForMap(target));
77 78 79
      return;
    }
    // If the flag requires a full TransitionArray, allocate one.
80 81 82
    Handle<TransitionArray> result = TransitionArray::Allocate(isolate, 0, 1);
    ReplaceTransitions(*result);
    Reload();
83
  }
84

85
  bool is_special_transition = flag == SPECIAL_TRANSITION;
86
  // If the map has a simple transition, check if it should be overwritten.
87 88 89 90
  Map* simple_transition = GetSimpleTransition();
  if (simple_transition != nullptr) {
    Name* key = GetSimpleTransitionKey(simple_transition);
    PropertyDetails old_details = GetSimpleTargetDetails(simple_transition);
91
    PropertyDetails new_details = is_special_transition
92
                                      ? PropertyDetails::Empty()
93 94 95 96
                                      : GetTargetDetails(*name, *target);
    if (flag == SIMPLE_PROPERTY_TRANSITION && key->Equals(*name) &&
        old_details.kind() == new_details.kind() &&
        old_details.attributes() == new_details.attributes()) {
97
      ReplaceTransitions(*Map::WeakCellForMap(target));
98 99 100
      return;
    }
    // Otherwise allocate a full TransitionArray with slack for a new entry.
101 102 103 104 105 106 107 108 109
    Handle<TransitionArray> result = TransitionArray::Allocate(isolate, 1, 1);
    // Reload state; the allocation might have caused it to be cleared.
    Reload();
    simple_transition = GetSimpleTransition();
    if (simple_transition != nullptr) {
      Object* value = raw_transitions_->IsWeakCell()
                          ? WeakCell::cast(raw_transitions_)->value()
                          : raw_transitions_;
      result->Set(0, GetSimpleTransitionKey(simple_transition), value);
110 111 112
    } else {
      result->SetNumberOfTransitions(0);
    }
113 114
    ReplaceTransitions(*result);
    Reload();
115 116
  }

117
  // At this point, we know that the map has a full TransitionArray.
118
  DCHECK_EQ(kFullTransitionArray, encoding());
119

120 121 122
  int number_of_transitions = 0;
  int new_nof = 0;
  int insertion_index = kNotFound;
123 124
  DCHECK_EQ(is_special_transition, IsSpecialTransition(*name));
  PropertyDetails details = is_special_transition
125
                                ? PropertyDetails::Empty()
126
                                : GetTargetDetails(*name, *target);
127

128
  {
129
    DisallowHeapAllocation no_gc;
130
    TransitionArray* array = transitions();
131 132
    number_of_transitions = array->number_of_transitions();
    new_nof = number_of_transitions;
133

134 135 136 137 138 139
    int index =
        is_special_transition
            ? array->SearchSpecial(Symbol::cast(*name), &insertion_index)
            : array->Search(details.kind(), *name, details.attributes(),
                            &insertion_index);
    // If an existing entry was found, overwrite it and return.
140
    if (index != kNotFound) {
141
      array->SetTarget(index, *target);
142
      return;
143 144
    }

145 146 147 148 149
    ++new_nof;
    CHECK(new_nof <= kMaxNumberOfTransitions);
    DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);

    // If there is enough capacity, insert new entry into the existing array.
150
    if (new_nof <= array->Capacity()) {
151 152 153
      array->SetNumberOfTransitions(new_nof);
      for (index = number_of_transitions; index > insertion_index; --index) {
        array->SetKey(index, array->GetKey(index - 1));
154
        array->SetTarget(index, array->GetRawTarget(index - 1));
155 156
      }
      array->SetKey(index, *name);
157
      array->SetTarget(index, *target);
158 159
      SLOW_DCHECK(array->IsSortedNoDuplicates());
      return;
160 161
    }
  }
162

163
  // We're gonna need a bigger TransitionArray.
164 165
  Handle<TransitionArray> result = TransitionArray::Allocate(
      isolate, new_nof,
verwaest's avatar
verwaest committed
166
      Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions));
167

168
  // The map's transition array may have shrunk during the allocation above as
169 170
  // it was weakly traversed, though it is guaranteed not to disappear. Trim the
  // result copy if needed, and recompute variables.
171
  Reload();
172
  DisallowHeapAllocation no_gc;
173
  TransitionArray* array = transitions();
174
  if (array->number_of_transitions() != number_of_transitions) {
175
    DCHECK(array->number_of_transitions() < number_of_transitions);
176 177

    number_of_transitions = array->number_of_transitions();
178
    new_nof = number_of_transitions;
179

180
    insertion_index = kNotFound;
181 182 183 184 185
    int index =
        is_special_transition
            ? array->SearchSpecial(Symbol::cast(*name), &insertion_index)
            : array->Search(details.kind(), *name, details.attributes(),
                            &insertion_index);
186 187 188 189 190 191
    if (index == kNotFound) {
      ++new_nof;
    } else {
      insertion_index = index;
    }
    DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
192

193
    result->Shrink(TransitionArray::ToKeyIndex(new_nof));
194
    result->SetNumberOfTransitions(new_nof);
195 196 197 198
  }

  if (array->HasPrototypeTransitions()) {
    result->SetPrototypeTransitions(array->GetPrototypeTransitions());
199 200
  }

201 202
  DCHECK_NE(kNotFound, insertion_index);
  for (int i = 0; i < insertion_index; ++i) {
203
    result->Set(i, array->GetKey(i), array->GetRawTarget(i));
204
  }
205
  result->Set(insertion_index, *name, *target);
206
  for (int i = insertion_index; i < number_of_transitions; ++i) {
207
    result->Set(i + 1, array->GetKey(i), array->GetRawTarget(i));
208 209
  }

210
  SLOW_DCHECK(result->IsSortedNoDuplicates());
211
  ReplaceTransitions(*result);
212 213
}

214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235
void TransitionsAccessor::UpdateHandler(Name* name, Object* handler) {
  if (map_->is_dictionary_map()) return;
  switch (encoding()) {
    case kPrototypeInfo:
    case kUninitialized:
      UNREACHABLE();
      return;
    case kWeakCell:
    case kTuple3Handler:
    case kFixedArrayHandler:
      DCHECK_EQ(GetSimpleTransition(), GetTargetFromRaw(handler));
      ReplaceTransitions(handler);
      return;
    case kFullTransitionArray: {
      PropertyAttributes attributes = name->IsPrivate() ? DONT_ENUM : NONE;
      int transition = transitions()->Search(kData, name, attributes);
      DCHECK_NE(kNotFound, transition);
      DCHECK_EQ(transitions()->GetTarget(transition),
                GetTargetFromRaw(handler));
      transitions()->SetTarget(transition, handler);
      return;
    }
236
  }
237 238
}

239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260
Object* TransitionsAccessor::SearchHandler(Name* name,
                                           Handle<Map>* out_transition) {
  switch (encoding()) {
    case kPrototypeInfo:
    case kUninitialized:
    case kWeakCell:
      return nullptr;
    case kTuple3Handler:
      return StoreHandler::ValidTuple3HandlerOrNull(raw_transitions_, name,
                                                    out_transition);
    case kFixedArrayHandler:
      return StoreHandler::ValidFixedArrayHandlerOrNull(raw_transitions_, name,
                                                        out_transition);
    case kFullTransitionArray: {
      int transition = transitions()->Search(kData, name, NONE);
      if (transition == kNotFound) return nullptr;
      Object* raw_handler = transitions()->GetRawTarget(transition);
      if (raw_handler->IsTuple3()) {
        return StoreHandler::ValidTuple3HandlerOrNull(raw_handler, nullptr,
                                                      out_transition);
      }
      if (raw_handler->IsFixedArray()) {
261
        return StoreHandler::ValidFixedArrayHandlerOrNull(raw_handler, nullptr,
262 263 264 265 266 267 268 269
                                                          out_transition);
      }
      return nullptr;
    }
  }
  UNREACHABLE();
  return nullptr;  // Make GCC happy.
}
270

271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292
Map* TransitionsAccessor::SearchTransition(Name* name, PropertyKind kind,
                                           PropertyAttributes attributes) {
  DCHECK(name->IsUniqueName());
  WeakCell* cell = nullptr;
  switch (encoding()) {
    case kPrototypeInfo:
    case kUninitialized:
      return nullptr;
    case kWeakCell:
      cell = GetTargetCell<kWeakCell>();
      break;
    case kTuple3Handler:
      cell = GetTargetCell<kTuple3Handler>();
      break;
    case kFixedArrayHandler:
      cell = GetTargetCell<kFixedArrayHandler>();
      break;
    case kFullTransitionArray: {
      int transition = transitions()->Search(kind, name, attributes);
      if (transition == kNotFound) return nullptr;
      return transitions()->GetTarget(transition);
    }
293
  }
294 295 296
  DCHECK(!cell->cleared());
  if (!IsMatchingMap(cell, name, kind, attributes)) return nullptr;
  return Map::cast(cell->value());
297 298
}

299 300 301 302 303 304
Map* TransitionsAccessor::SearchSpecial(Symbol* name) {
  if (encoding() != kFullTransitionArray) return nullptr;
  int transition = transitions()->SearchSpecial(name);
  if (transition == kNotFound) return NULL;
  return transitions()->GetTarget(transition);
}
305 306

// static
307 308 309 310 311 312 313 314 315 316
bool TransitionsAccessor::IsSpecialTransition(Name* name) {
  if (!name->IsSymbol()) return false;
  Heap* heap = name->GetHeap();
  return name == heap->nonextensible_symbol() ||
         name == heap->sealed_symbol() || name == heap->frozen_symbol() ||
         name == heap->elements_transition_symbol() ||
         name == heap->strict_function_transition_symbol();
}

Handle<Map> TransitionsAccessor::FindTransitionToField(Handle<Name> name) {
317
  DCHECK(name->IsUniqueName());
318
  DisallowHeapAllocation no_gc;
319
  Map* target = SearchTransition(*name, kData, NONE);
320 321 322
  if (target == NULL) return Handle<Map>::null();
  PropertyDetails details = target->GetLastDescriptorDetails();
  DCHECK_EQ(NONE, details.attributes());
323 324
  if (details.location() != kField) return Handle<Map>::null();
  DCHECK_EQ(kData, details.kind());
325 326 327
  return Handle<Map>(target);
}

328
Handle<String> TransitionsAccessor::ExpectedTransitionKey() {
329
  DisallowHeapAllocation no_gc;
330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347
  WeakCell* cell = nullptr;
  switch (encoding()) {
    case kPrototypeInfo:
    case kUninitialized:
    case kFullTransitionArray:
      return Handle<String>::null();
    case kWeakCell:
      cell = GetTargetCell<kWeakCell>();
      break;
    case kTuple3Handler:
      cell = GetTargetCell<kTuple3Handler>();
      break;
    case kFixedArrayHandler:
      cell = GetTargetCell<kFixedArrayHandler>();
      break;
  }
  DCHECK(!cell->cleared());
  Map* target = Map::cast(cell->value());
348
  PropertyDetails details = GetSimpleTargetDetails(target);
349 350
  if (details.location() != kField) return Handle<String>::null();
  DCHECK_EQ(kData, details.kind());
351 352 353
  if (details.attributes() != NONE) return Handle<String>::null();
  Name* name = GetSimpleTransitionKey(target);
  if (!name->IsString()) return Handle<String>::null();
354
  return handle(String::cast(name));
355 356
}

357 358 359 360
Handle<Map> TransitionsAccessor::ExpectedTransitionTarget() {
  DCHECK(!ExpectedTransitionKey().is_null());
  return handle(GetTarget(0));
}
361

362 363 364 365
bool TransitionsAccessor::CanHaveMoreTransitions() {
  if (map_->is_dictionary_map()) return false;
  if (encoding() == kFullTransitionArray) {
    return transitions()->number_of_transitions() < kMaxNumberOfTransitions;
366 367 368 369
  }
  return true;
}

370 371 372 373 374 375 376 377 378 379 380 381
// static
bool TransitionsAccessor::IsMatchingMap(WeakCell* target_cell, Name* name,
                                        PropertyKind kind,
                                        PropertyAttributes attributes) {
  Map* target = Map::cast(target_cell->value());
  int descriptor = target->LastAdded();
  DescriptorArray* descriptors = target->instance_descriptors();
  Name* key = descriptors->GetKey(descriptor);
  if (key != name) return false;
  PropertyDetails details = descriptors->GetDetails(descriptor);
  return (details.kind() == kind && details.attributes() == attributes);
}
382

383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419
// static
bool TransitionArray::CompactPrototypeTransitionArray(FixedArray* array) {
  const int header = kProtoTransitionHeaderSize;
  int number_of_transitions = NumberOfPrototypeTransitions(array);
  if (number_of_transitions == 0) {
    // Empty array cannot be compacted.
    return false;
  }
  int new_number_of_transitions = 0;
  for (int i = 0; i < number_of_transitions; i++) {
    Object* cell = array->get(header + i);
    if (!WeakCell::cast(cell)->cleared()) {
      if (new_number_of_transitions != i) {
        array->set(header + new_number_of_transitions, cell);
      }
      new_number_of_transitions++;
    }
  }
  // Fill slots that became free with undefined value.
  for (int i = new_number_of_transitions; i < number_of_transitions; i++) {
    array->set_undefined(header + i);
  }
  if (number_of_transitions != new_number_of_transitions) {
    SetNumberOfPrototypeTransitions(array, new_number_of_transitions);
  }
  return new_number_of_transitions < number_of_transitions;
}


// static
Handle<FixedArray> TransitionArray::GrowPrototypeTransitionArray(
    Handle<FixedArray> array, int new_capacity, Isolate* isolate) {
  // Grow array by factor 2 up to MaxCachedPrototypeTransitions.
  int capacity = array->length() - kProtoTransitionHeaderSize;
  new_capacity = Min(kMaxCachedPrototypeTransitions, new_capacity);
  DCHECK_GT(new_capacity, capacity);
  int grow_by = new_capacity - capacity;
420
  array = isolate->factory()->CopyFixedArrayAndGrow(array, grow_by, TENURED);
421 422 423 424 425 426 427 428
  if (capacity < 0) {
    // There was no prototype transitions array before, so the size
    // couldn't be copied. Initialize it explicitly.
    SetNumberOfPrototypeTransitions(*array, 0);
  }
  return array;
}

429 430
void TransitionsAccessor::PutPrototypeTransition(Handle<Object> prototype,
                                                 Handle<Map> target_map) {
431 432 433
  DCHECK(HeapObject::cast(*prototype)->map()->IsMap());
  // Don't cache prototype transition if this map is either shared, or a map of
  // a prototype.
434 435
  if (map_->is_prototype_map()) return;
  if (map_->is_dictionary_map() || !FLAG_cache_prototype_transitions) return;
436

437
  const int header = TransitionArray::kProtoTransitionHeaderSize;
438

439
  Handle<FixedArray> cache(GetPrototypeTransitions());
440
  int capacity = cache->length() - header;
441
  int transitions = TransitionArray::NumberOfPrototypeTransitions(*cache) + 1;
442 443

  if (transitions > capacity) {
444
    // Grow the array if compacting it doesn't free space.
445 446 447 448 449 450
    if (!TransitionArray::CompactPrototypeTransitionArray(*cache)) {
      if (capacity == TransitionArray::kMaxCachedPrototypeTransitions) return;
      cache = TransitionArray::GrowPrototypeTransitionArray(
          cache, 2 * transitions, target_map->GetIsolate());
      Reload();
      SetPrototypeTransitions(cache);
451 452 453
    }
  }

454
  // Reload number of transitions as they might have been compacted.
455
  int last = TransitionArray::NumberOfPrototypeTransitions(*cache);
456 457
  int entry = header + last;

458
  Handle<WeakCell> target_cell = Map::WeakCellForMap(target_map);
459
  cache->set(entry, *target_cell);
460
  TransitionArray::SetNumberOfPrototypeTransitions(*cache, last + 1);
461 462
}

463 464
Handle<Map> TransitionsAccessor::GetPrototypeTransition(
    Handle<Object> prototype) {
465
  DisallowHeapAllocation no_gc;
466 467 468 469 470
  FixedArray* cache = GetPrototypeTransitions();
  int length = TransitionArray::NumberOfPrototypeTransitions(cache);
  for (int i = 0; i < length; i++) {
    WeakCell* target_cell = WeakCell::cast(
        cache->get(TransitionArray::kProtoTransitionHeaderSize + i));
471 472 473 474
    if (!target_cell->cleared() &&
        Map::cast(target_cell->value())->prototype() == *prototype) {
      return handle(Map::cast(target_cell->value()));
    }
475 476 477 478
  }
  return Handle<Map>();
}

479 480 481 482
FixedArray* TransitionsAccessor::GetPrototypeTransitions() {
  if (encoding() != kFullTransitionArray ||
      !transitions()->HasPrototypeTransitions()) {
    return map_->GetHeap()->empty_fixed_array();
483
  }
484
  return transitions()->GetPrototypeTransitions();
485 486 487 488 489 490 491 492 493 494
}

// static
void TransitionArray::SetNumberOfPrototypeTransitions(
    FixedArray* proto_transitions, int value) {
  DCHECK(proto_transitions->length() != 0);
  proto_transitions->set(kProtoTransitionNumberOfEntriesOffset,
                         Smi::FromInt(value));
}

495 496 497 498 499 500 501 502 503 504 505 506 507 508
int TransitionsAccessor::NumberOfTransitions() {
  switch (encoding()) {
    case kPrototypeInfo:
    case kUninitialized:
      return 0;
    case kWeakCell:
    case kTuple3Handler:
    case kFixedArrayHandler:
      return 1;
    case kFullTransitionArray:
      return transitions()->number_of_transitions();
  }
  UNREACHABLE();
  return 0;  // Make GCC happy.
509 510 511 512 513
}

Handle<TransitionArray> TransitionArray::Allocate(Isolate* isolate,
                                                  int number_of_transitions,
                                                  int slack) {
514 515
  Handle<FixedArray> array = isolate->factory()->NewTransitionArray(
      LengthFor(number_of_transitions + slack));
516
  array->set(kPrototypeTransitionsIndex, Smi::kZero);
517 518 519 520
  array->set(kTransitionLengthIndex, Smi::FromInt(number_of_transitions));
  return Handle<TransitionArray>::cast(array);
}

521 522 523 524 525
void TransitionArray::Zap() {
  MemsetPointer(data_start() + kPrototypeTransitionsIndex,
                GetHeap()->the_hole_value(),
                length() - kPrototypeTransitionsIndex);
  SetNumberOfTransitions(0);
526 527
}

528 529 530 531 532
void TransitionsAccessor::ReplaceTransitions(Object* new_transitions) {
  if (encoding() == kFullTransitionArray) {
    TransitionArray* old_transitions = transitions();
#if DEBUG
    CheckNewTransitionsAreConsistent(old_transitions, new_transitions);
533 534 535 536 537 538
    DCHECK(old_transitions != new_transitions);
#endif
    // Transition arrays are not shared. When one is replaced, it should not
    // keep referenced objects alive, so we zap it.
    // When there is another reference to the array somewhere (e.g. a handle),
    // not zapping turns from a waste of memory into a source of crashes.
539
    old_transitions->Zap();
540
  }
541 542
  map_->set_raw_transitions(new_transitions);
  MarkNeedsReload();
543 544
}

545 546 547 548
void TransitionsAccessor::SetPrototypeTransitions(
    Handle<FixedArray> proto_transitions) {
  EnsureHasFullTransitionArray();
  transitions()->SetPrototypeTransitions(*proto_transitions);
549 550
}

551 552 553 554 555
void TransitionsAccessor::EnsureHasFullTransitionArray() {
  if (encoding() == kFullTransitionArray) return;
  int nof = encoding() == kUninitialized ? 0 : 1;
  Handle<TransitionArray> result =
      TransitionArray::Allocate(map_->GetIsolate(), nof);
556
  DisallowHeapAllocation no_gc;
557 558 559 560 561 562 563 564 565 566 567 568
  Reload();  // Reload after possible GC.
  if (nof == 1) {
    Map* target = GetSimpleTransition();
    if (target == nullptr) {
      // If allocation caused GC and cleared the target, trim the new array.
      result->Shrink(TransitionArray::ToKeyIndex(0));
      result->SetNumberOfTransitions(0);
    } else {
      // Otherwise populate the new array.
      Name* key = GetSimpleTransitionKey(target);
      result->Set(0, key, target);
    }
569
  }
570 571
  ReplaceTransitions(*result);
  Reload();  // Reload after replacing transitions.
572 573
}

574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599
void TransitionsAccessor::TraverseTransitionTreeInternal(
    TraverseCallback callback, void* data, DisallowHeapAllocation* no_gc) {
  Map* simple_target = nullptr;
  switch (encoding()) {
    case kPrototypeInfo:
    case kUninitialized:
      break;
    case kWeakCell:
      simple_target = Map::cast(GetTargetCell<kWeakCell>()->value());
      break;
    case kTuple3Handler:
      simple_target = Map::cast(GetTargetCell<kTuple3Handler>()->value());
      break;
    case kFixedArrayHandler:
      simple_target = Map::cast(GetTargetCell<kFixedArrayHandler>()->value());
      break;
    case kFullTransitionArray: {
      if (transitions()->HasPrototypeTransitions()) {
        FixedArray* proto_trans = transitions()->GetPrototypeTransitions();
        int length = TransitionArray::NumberOfPrototypeTransitions(proto_trans);
        for (int i = 0; i < length; ++i) {
          int index = TransitionArray::kProtoTransitionHeaderSize + i;
          WeakCell* cell = WeakCell::cast(proto_trans->get(index));
          if (cell->cleared()) continue;
          TransitionsAccessor(Map::cast(cell->value()), no_gc)
              .TraverseTransitionTreeInternal(callback, data, no_gc);
600
        }
601
      }
602 603 604 605 606
      for (int i = 0; i < transitions()->number_of_transitions(); ++i) {
        TransitionsAccessor(transitions()->GetTarget(i), no_gc)
            .TraverseTransitionTreeInternal(callback, data, no_gc);
      }
      break;
607 608
    }
  }
609 610 611 612 613
  if (simple_target != nullptr) {
    TransitionsAccessor(simple_target, no_gc)
        .TraverseTransitionTreeInternal(callback, data, no_gc);
  }
  callback(map_, data);
614 615 616
}

#ifdef DEBUG
617 618
void TransitionsAccessor::CheckNewTransitionsAreConsistent(
    TransitionArray* old_transitions, Object* transitions) {
619
  // This function only handles full transition arrays.
620
  DCHECK_EQ(kFullTransitionArray, encoding());
621 622 623
  TransitionArray* new_transitions = TransitionArray::cast(transitions);
  for (int i = 0; i < old_transitions->number_of_transitions(); i++) {
    Map* target = old_transitions->GetTarget(i);
624
    if (target->instance_descriptors() == map_->instance_descriptors()) {
625 626
      Name* key = old_transitions->GetKey(i);
      int new_target_index;
627
      if (IsSpecialTransition(key)) {
628 629
        new_target_index = new_transitions->SearchSpecial(Symbol::cast(key));
      } else {
630
        PropertyDetails details = GetTargetDetails(key, target);
631 632 633 634 635 636 637 638 639 640 641 642
        new_target_index =
            new_transitions->Search(details.kind(), key, details.attributes());
      }
      DCHECK_NE(TransitionArray::kNotFound, new_target_index);
      DCHECK_EQ(target, new_transitions->GetTarget(new_target_index));
    }
  }
}
#endif

// Private non-static helper functions (operating on full transition arrays).

643
int TransitionArray::SearchDetails(int transition, PropertyKind kind,
644 645 646 647 648 649 650 651
                                   PropertyAttributes attributes,
                                   int* out_insertion_index) {
  int nof_transitions = number_of_transitions();
  DCHECK(transition < nof_transitions);
  Name* key = GetKey(transition);
  for (; transition < nof_transitions && GetKey(transition) == key;
       transition++) {
    Map* target = GetTarget(transition);
652 653
    PropertyDetails target_details =
        TransitionsAccessor::GetTargetDetails(key, target);
654

655
    int cmp = CompareDetails(kind, attributes, target_details.kind(),
656 657 658 659 660 661 662 663 664 665 666 667
                             target_details.attributes());
    if (cmp == 0) {
      return transition;
    } else if (cmp < 0) {
      break;
    }
  }
  if (out_insertion_index != NULL) *out_insertion_index = transition;
  return kNotFound;
}


668
int TransitionArray::Search(PropertyKind kind, Name* name,
669 670 671
                            PropertyAttributes attributes,
                            int* out_insertion_index) {
  int transition = SearchName(name, out_insertion_index);
672
  if (transition == kNotFound) return kNotFound;
673
  return SearchDetails(transition, kind, attributes, out_insertion_index);
674
}
675 676 677 678 679 680 681 682 683 684

void TransitionArray::Sort() {
  DisallowHeapAllocation no_gc;
  // In-place insertion sort.
  int length = number_of_transitions();
  for (int i = 1; i < length; i++) {
    Name* key = GetKey(i);
    Map* target = GetTarget(i);
    PropertyKind kind = kData;
    PropertyAttributes attributes = NONE;
685 686 687
    if (!TransitionsAccessor::IsSpecialTransition(key)) {
      PropertyDetails details =
          TransitionsAccessor::GetTargetDetails(key, target);
688 689 690 691 692 693 694 695 696
      kind = details.kind();
      attributes = details.attributes();
    }
    int j;
    for (j = i - 1; j >= 0; j--) {
      Name* temp_key = GetKey(j);
      Map* temp_target = GetTarget(j);
      PropertyKind temp_kind = kData;
      PropertyAttributes temp_attributes = NONE;
697 698 699
      if (!TransitionsAccessor::IsSpecialTransition(temp_key)) {
        PropertyDetails details =
            TransitionsAccessor::GetTargetDetails(temp_key, temp_target);
700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718
        temp_kind = details.kind();
        temp_attributes = details.attributes();
      }
      int cmp =
          CompareKeys(temp_key, temp_key->Hash(), temp_kind, temp_attributes,
                      key, key->Hash(), kind, attributes);
      if (cmp > 0) {
        SetKey(j + 1, temp_key);
        SetTarget(j + 1, temp_target);
      } else {
        break;
      }
    }
    SetKey(j + 1, key);
    SetTarget(j + 1, target);
  }
  DCHECK(IsSortedNoDuplicates());
}

719 720
}  // namespace internal
}  // namespace v8