transitions.cc 26.8 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/objects/transitions.h"
6

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

namespace v8 {
namespace internal {

15
Map TransitionsAccessor::GetSimpleTransition() {
16
  switch (encoding()) {
17
    case kWeakRef:
18
      return Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
19
    default:
20
      return Map();
21 22 23
  }
}

24
bool TransitionsAccessor::HasSimpleTransitionTo(Map map) {
25
  switch (encoding()) {
26
    case kWeakRef:
27
      return raw_transitions_->GetHeapObjectAssumeWeak() == map;
28 29
    case kPrototypeInfo:
    case kUninitialized:
30
    case kMigrationTarget:
31 32 33 34 35 36 37 38
    case kFullTransitionArray:
      return false;
  }
  UNREACHABLE();
}

void TransitionsAccessor::Insert(Handle<Name> name, Handle<Map> target,
                                 SimpleTransitionFlag flag) {
39
  DCHECK(!concurrent_access_);
40
  DCHECK(!map_handle_.is_null());
41
  DCHECK_NE(kPrototypeInfo, encoding());
42
  target->SetBackPointer(map_);
43 44

  // If the map doesn't have any transitions at all yet, install the new one.
45
  if (encoding() == kUninitialized || encoding() == kMigrationTarget) {
46
    if (flag == SIMPLE_PROPERTY_TRANSITION) {
47
      ReplaceTransitions(HeapObjectReference::Weak(*target));
48 49 50
      return;
    }
    // If the flag requires a full TransitionArray, allocate one.
51
    Handle<TransitionArray> result =
52 53
        isolate_->factory()->NewTransitionArray(1, 0);
    result->Set(0, *name, HeapObjectReference::Weak(*target));
54
    ReplaceTransitions(MaybeObject::FromObject(*result));
55
    Reload();
56
    DCHECK_EQ(kFullTransitionArray, encoding());
57
    return;
58
  }
59

60 61 62
  if (encoding() == kWeakRef) {
    Map simple_transition = GetSimpleTransition();
    DCHECK(!simple_transition.is_null());
63 64 65 66 67 68 69 70 71 72

    if (flag == SIMPLE_PROPERTY_TRANSITION) {
      Name key = GetSimpleTransitionKey(simple_transition);
      PropertyDetails old_details = GetSimpleTargetDetails(simple_transition);
      PropertyDetails new_details = GetTargetDetails(*name, *target);
      if (key.Equals(*name) && old_details.kind() == new_details.kind() &&
          old_details.attributes() == new_details.attributes()) {
        ReplaceTransitions(HeapObjectReference::Weak(*target));
        return;
      }
73
    }
74

75
    // Otherwise allocate a full TransitionArray with slack for a new entry.
76
    Handle<Map> map(simple_transition, isolate_);
77
    Handle<TransitionArray> result =
78
        isolate_->factory()->NewTransitionArray(1, 1);
79
    // Reload state; allocations might have caused it to be cleared.
80 81
    Reload();
    simple_transition = GetSimpleTransition();
82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
    if (simple_transition.is_null()) {
      result->Set(0, *name, HeapObjectReference::Weak(*target));
      ReplaceTransitions(MaybeObject::FromObject(*result));
      Reload();
      DCHECK_EQ(kFullTransitionArray, encoding());
      return;
    }

    // Insert the original transition in index 0.
    result->Set(0, GetSimpleTransitionKey(simple_transition),
                HeapObjectReference::Weak(simple_transition));

    // Search for the correct index to insert the new transition.
    int insertion_index;
    int index;
    if (flag == SPECIAL_TRANSITION) {
98 99
      index =
          result->SearchSpecial(Symbol::cast(*name), false, &insertion_index);
100
    } else {
101 102 103
      PropertyDetails details = GetTargetDetails(*name, *target);
      index = result->Search(details.kind(), *name, details.attributes(),
                             &insertion_index);
104
    }
105 106 107 108 109 110 111 112 113 114 115 116 117 118
    DCHECK_EQ(index, kNotFound);
    USE(index);

    result->SetNumberOfTransitions(2);
    if (insertion_index == 0) {
      // If the new transition will be inserted in index 0, move the original
      // transition to index 1.
      result->Set(1, GetSimpleTransitionKey(simple_transition),
                  HeapObjectReference::Weak(simple_transition));
    }
    result->SetKey(insertion_index, *name);
    result->SetRawTarget(insertion_index, HeapObjectReference::Weak(*target));

    SLOW_DCHECK(result->IsSortedNoDuplicates());
119
    ReplaceTransitions(MaybeObject::FromObject(*result));
120
    Reload();
121 122
    DCHECK_EQ(kFullTransitionArray, encoding());
    return;
123 124
  }

125
  // At this point, we know that the map has a full TransitionArray.
126
  DCHECK_EQ(kFullTransitionArray, encoding());
127

128 129 130
  int number_of_transitions = 0;
  int new_nof = 0;
  int insertion_index = kNotFound;
131
  const bool is_special_transition = flag == SPECIAL_TRANSITION;
132 133
  DCHECK_EQ(is_special_transition,
            IsSpecialTransition(ReadOnlyRoots(isolate_), *name));
134
  PropertyDetails details = is_special_transition
135
                                ? PropertyDetails::Empty()
136
                                : GetTargetDetails(*name, *target);
137

138
  {
139
    DisallowGarbageCollection no_gc;
140
    TransitionArray array = transitions();
141
    number_of_transitions = array.number_of_transitions();
142

143 144 145 146 147
    int index =
        is_special_transition
            ? array.SearchSpecial(Symbol::cast(*name), false, &insertion_index)
            : array.Search(details.kind(), *name, details.attributes(),
                           &insertion_index);
148
    // If an existing entry was found, overwrite it and return.
149
    if (index != kNotFound) {
150
      base::SharedMutexGuard<base::kExclusive> shared_mutex_guard(
151
          isolate_->full_transition_array_access());
152
      array.SetRawTarget(index, HeapObjectReference::Weak(*target));
153
      return;
154 155
    }

156
    new_nof = number_of_transitions + 1;
157
    CHECK_LE(new_nof, kMaxNumberOfTransitions);
158 159
    DCHECK_GE(insertion_index, 0);
    DCHECK_LE(insertion_index, number_of_transitions);
160 161

    // If there is enough capacity, insert new entry into the existing array.
162
    if (new_nof <= array.Capacity()) {
163
      base::SharedMutexGuard<base::kExclusive> shared_mutex_guard(
164
          isolate_->full_transition_array_access());
165
      array.SetNumberOfTransitions(new_nof);
166 167 168
      for (int i = number_of_transitions; i > insertion_index; --i) {
        array.SetKey(i, array.GetKey(i - 1));
        array.SetRawTarget(i, array.GetRawTarget(i - 1));
169
      }
170 171
      array.SetKey(insertion_index, *name);
      array.SetRawTarget(insertion_index, HeapObjectReference::Weak(*target));
172
      SLOW_DCHECK(array.IsSortedNoDuplicates());
173
      return;
174 175
    }
  }
176

177
  // We're gonna need a bigger TransitionArray.
178
  Handle<TransitionArray> result = isolate_->factory()->NewTransitionArray(
179
      new_nof,
verwaest's avatar
verwaest committed
180
      Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions));
181

182
  // The map's transition array may have shrunk during the allocation above as
183 184
  // it was weakly traversed, though it is guaranteed not to disappear. Trim the
  // result copy if needed, and recompute variables.
185
  Reload();
186
  DisallowGarbageCollection no_gc;
187
  TransitionArray array = transitions();
188
  if (array.number_of_transitions() != number_of_transitions) {
189
    DCHECK_LT(array.number_of_transitions(), number_of_transitions);
190

191 192 193 194 195
    int index =
        is_special_transition
            ? array.SearchSpecial(Symbol::cast(*name), false, &insertion_index)
            : array.Search(details.kind(), *name, details.attributes(),
                           &insertion_index);
196 197 198 199
    CHECK_EQ(index, kNotFound);
    USE(index);
    DCHECK_GE(insertion_index, 0);
    DCHECK_LE(insertion_index, number_of_transitions);
200

201 202
    number_of_transitions = array.number_of_transitions();
    new_nof = number_of_transitions + 1;
203
    result->SetNumberOfTransitions(new_nof);
204 205
  }

206 207
  if (array.HasPrototypeTransitions()) {
    result->SetPrototypeTransitions(array.GetPrototypeTransitions());
208 209
  }

210 211
  DCHECK_NE(kNotFound, insertion_index);
  for (int i = 0; i < insertion_index; ++i) {
212
    result->Set(i, array.GetKey(i), array.GetRawTarget(i));
213
  }
214
  result->Set(insertion_index, *name, HeapObjectReference::Weak(*target));
215
  for (int i = insertion_index; i < number_of_transitions; ++i) {
216
    result->Set(i + 1, array.GetKey(i), array.GetRawTarget(i));
217 218
  }

219
  SLOW_DCHECK(result->IsSortedNoDuplicates());
220
  ReplaceTransitions(MaybeObject::FromObject(*result));
221 222
}

223
Map TransitionsAccessor::SearchTransition(Name name, PropertyKind kind,
224
                                          PropertyAttributes attributes) {
225
  DCHECK(name.IsUniqueName());
226 227 228
  switch (encoding()) {
    case kPrototypeInfo:
    case kUninitialized:
229
    case kMigrationTarget:
230
      return Map();
231
    case kWeakRef: {
232 233
      Map map = Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
      if (!IsMatchingMap(map, name, kind, attributes)) return Map();
234
      return map;
235
    }
236
    case kFullTransitionArray: {
237
      base::SharedMutexGuardIf<base::kShared> scope(
238
          isolate_->full_transition_array_access(), concurrent_access_);
239
      return transitions().SearchAndGetTarget(kind, name, attributes);
240
    }
241
  }
242
  UNREACHABLE();
243 244
}

245
Map TransitionsAccessor::SearchSpecial(Symbol name) {
246
  if (encoding() != kFullTransitionArray) return Map();
247 248 249
  base::SharedMutexGuardIf<base::kShared> scope(
      isolate_->full_transition_array_access(), concurrent_access_);
  int transition = transitions().SearchSpecial(name, concurrent_access_);
250
  if (transition == kNotFound) return Map();
251
  return transitions().GetTarget(transition);
252
}
253 254

// static
255
bool TransitionsAccessor::IsSpecialTransition(ReadOnlyRoots roots, Name name) {
256
  if (!name.IsSymbol()) return false;
257 258 259 260
  return name == roots.nonextensible_symbol() ||
         name == roots.sealed_symbol() || name == roots.frozen_symbol() ||
         name == roots.elements_transition_symbol() ||
         name == roots.strict_function_transition_symbol();
261 262
}

263 264
MaybeHandle<Map> TransitionsAccessor::FindTransitionToDataProperty(
    Handle<Name> name, RequestedLocation requested_location) {
265
  DCHECK(name->IsUniqueName());
266
  DisallowGarbageCollection no_gc;
267
  PropertyAttributes attributes = name->IsPrivate() ? DONT_ENUM : NONE;
268 269
  Map target = SearchTransition(*name, kData, attributes);
  if (target.is_null()) return MaybeHandle<Map>();
270
  PropertyDetails details = target.GetLastDescriptorDetails(isolate_);
271
  DCHECK_EQ(attributes, details.attributes());
272
  DCHECK_EQ(kData, details.kind());
273 274
  if (requested_location == kFieldOnly &&
      details.location() != PropertyLocation::kField) {
275 276
    return MaybeHandle<Map>();
  }
277
  return Handle<Map>(target, isolate_);
278 279
}

280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307
void TransitionsAccessor::ForEachTransitionTo(
    Name name, const ForEachTransitionCallback& callback,
    DisallowGarbageCollection* no_gc) {
  DCHECK(name.IsUniqueName());
  switch (encoding()) {
    case kPrototypeInfo:
    case kUninitialized:
    case kMigrationTarget:
      return;
    case kWeakRef: {
      Map target = Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
      InternalIndex descriptor = target.LastAdded();
      DescriptorArray descriptors = target.instance_descriptors(kRelaxedLoad);
      Name key = descriptors.GetKey(descriptor);
      if (key == name) {
        callback(target);
      }
      return;
    }
    case kFullTransitionArray: {
      base::SharedMutexGuardIf<base::kShared> scope(
          isolate_->full_transition_array_access(), concurrent_access_);
      return transitions().ForEachTransitionTo(name, callback);
    }
  }
  UNREACHABLE();
}

308
bool TransitionsAccessor::CanHaveMoreTransitions() {
309
  if (map_.is_dictionary_map()) return false;
310
  if (encoding() == kFullTransitionArray) {
311
    return transitions().number_of_transitions() < kMaxNumberOfTransitions;
312 313 314 315
  }
  return true;
}

316
// static
317
bool TransitionsAccessor::IsMatchingMap(Map target, Name name,
318 319
                                        PropertyKind kind,
                                        PropertyAttributes attributes) {
320
  InternalIndex descriptor = target.LastAdded();
321
  DescriptorArray descriptors = target.instance_descriptors(kRelaxedLoad);
322
  Name key = descriptors.GetKey(descriptor);
323
  if (key != name) return false;
324
  return descriptors.GetDetails(descriptor)
325
      .HasKindAndAttributes(kind, attributes);
326
}
327

328
// static
329
bool TransitionArray::CompactPrototypeTransitionArray(Isolate* isolate,
330
                                                      WeakFixedArray array) {
331 332 333 334 335 336 337 338
  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++) {
339
    MaybeObject target = array.Get(header + i);
340
    DCHECK(target->IsCleared() ||
341
           (target->IsWeak() && target->GetHeapObject().IsMap()));
342
    if (!target->IsCleared()) {
343
      if (new_number_of_transitions != i) {
344
        array.Set(header + new_number_of_transitions, target);
345 346 347 348 349
      }
      new_number_of_transitions++;
    }
  }
  // Fill slots that became free with undefined value.
350
  MaybeObject undefined =
351
      MaybeObject::FromObject(*isolate->factory()->undefined_value());
352
  for (int i = new_number_of_transitions; i < number_of_transitions; i++) {
353
    array.Set(header + i, undefined);
354 355 356 357 358 359 360 361
  }
  if (number_of_transitions != new_number_of_transitions) {
    SetNumberOfPrototypeTransitions(array, new_number_of_transitions);
  }
  return new_number_of_transitions < number_of_transitions;
}

// static
362 363
Handle<WeakFixedArray> TransitionArray::GrowPrototypeTransitionArray(
    Handle<WeakFixedArray> array, int new_capacity, Isolate* isolate) {
364 365
  // Grow array by factor 2 up to MaxCachedPrototypeTransitions.
  int capacity = array->length() - kProtoTransitionHeaderSize;
366
  new_capacity = std::min({kMaxCachedPrototypeTransitions, new_capacity});
367 368
  DCHECK_GT(new_capacity, capacity);
  int grow_by = new_capacity - capacity;
369
  array = isolate->factory()->CopyWeakFixedArrayAndGrow(array, grow_by);
370 371 372 373 374 375 376 377
  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;
}

378 379
void TransitionsAccessor::PutPrototypeTransition(Handle<Object> prototype,
                                                 Handle<Map> target_map) {
380
  DCHECK(HeapObject::cast(*prototype).map().IsMap());
381 382
  // Don't cache prototype transition if this map is either shared, or a map of
  // a prototype.
383 384
  if (map_.is_prototype_map()) return;
  if (map_.is_dictionary_map() || !FLAG_cache_prototype_transitions) return;
385

386
  const int header = TransitionArray::kProtoTransitionHeaderSize;
387

388
  Handle<WeakFixedArray> cache(GetPrototypeTransitions(), isolate_);
389
  int capacity = cache->length() - header;
390
  int transitions = TransitionArray::NumberOfPrototypeTransitions(*cache) + 1;
391

392 393 394
  base::SharedMutexGuard<base::kExclusive> scope(
      isolate_->full_transition_array_access());

395
  if (transitions > capacity) {
396
    // Grow the array if compacting it doesn't free space.
397
    if (!TransitionArray::CompactPrototypeTransitionArray(isolate_, *cache)) {
398 399
      if (capacity == TransitionArray::kMaxCachedPrototypeTransitions) return;
      cache = TransitionArray::GrowPrototypeTransitionArray(
400
          cache, 2 * transitions, isolate_);
401 402
      Reload();
      SetPrototypeTransitions(cache);
403 404 405
    }
  }

406
  // Reload number of transitions as they might have been compacted.
407
  int last = TransitionArray::NumberOfPrototypeTransitions(*cache);
408 409
  int entry = header + last;

410
  cache->Set(entry, HeapObjectReference::Weak(*target_map));
411
  TransitionArray::SetNumberOfPrototypeTransitions(*cache, last + 1);
412 413
}

414 415
Handle<Map> TransitionsAccessor::GetPrototypeTransition(
    Handle<Object> prototype) {
416
  DisallowGarbageCollection no_gc;
417
  WeakFixedArray cache = GetPrototypeTransitions();
418 419
  int length = TransitionArray::NumberOfPrototypeTransitions(cache);
  for (int i = 0; i < length; i++) {
420
    MaybeObject target =
421
        cache.Get(TransitionArray::kProtoTransitionHeaderSize + i);
422
    DCHECK(target->IsWeakOrCleared());
423
    HeapObject heap_object;
424
    if (target->GetHeapObjectIfWeak(&heap_object)) {
425
      Map map = Map::cast(heap_object);
426
      if (map.prototype() == *prototype) {
427
        return handle(map, isolate_);
428
      }
429
    }
430 431 432 433
  }
  return Handle<Map>();
}

434
WeakFixedArray TransitionsAccessor::GetPrototypeTransitions() {
435
  if (encoding() != kFullTransitionArray ||
436
      !transitions().HasPrototypeTransitions()) {
437
    return ReadOnlyRoots(isolate_).empty_weak_fixed_array();
438
  }
439
  return transitions().GetPrototypeTransitions();
440 441 442 443
}

// static
void TransitionArray::SetNumberOfPrototypeTransitions(
444
    WeakFixedArray proto_transitions, int value) {
445 446 447
  DCHECK_NE(proto_transitions.length(), 0);
  proto_transitions.Set(kProtoTransitionNumberOfEntriesOffset,
                        MaybeObject::FromSmi(Smi::FromInt(value)));
448 449
}

450 451 452 453
int TransitionsAccessor::NumberOfTransitions() {
  switch (encoding()) {
    case kPrototypeInfo:
    case kUninitialized:
454
    case kMigrationTarget:
455
      return 0;
456
    case kWeakRef:
457 458
      return 1;
    case kFullTransitionArray:
459
      return transitions().number_of_transitions();
460 461
  }
  UNREACHABLE();
462 463
}

464 465 466 467
void TransitionsAccessor::SetMigrationTarget(Map migration_target) {
  // We only cache the migration target for maps with empty transitions for GC's
  // sake.
  if (encoding() != kUninitialized) return;
468
  DCHECK(map_.is_deprecated());
469 470
  map_.set_raw_transitions(MaybeObject::FromObject(migration_target),
                           kReleaseStore);
471 472 473 474 475
  MarkNeedsReload();
}

Map TransitionsAccessor::GetMigrationTarget() {
  if (encoding() == kMigrationTarget) {
476
    return map_.raw_transitions(kAcquireLoad)->cast<Map>();
477 478 479 480
  }
  return Map();
}

481
void TransitionsAccessor::ReplaceTransitions(MaybeObject new_transitions) {
482 483
  if (encoding() == kFullTransitionArray) {
#if DEBUG
484
    TransitionArray old_transitions = transitions();
485 486 487
    CheckNewTransitionsAreConsistent(
        old_transitions, new_transitions->GetHeapObjectAssumeStrong());
    DCHECK(old_transitions != new_transitions->GetHeapObjectAssumeStrong());
488 489
#endif
  }
490
  map_.set_raw_transitions(new_transitions, kReleaseStore);
491
  MarkNeedsReload();
492 493
}

494
void TransitionsAccessor::SetPrototypeTransitions(
495
    Handle<WeakFixedArray> proto_transitions) {
496
  EnsureHasFullTransitionArray();
497
  transitions().SetPrototypeTransitions(*proto_transitions);
498 499
}

500 501
void TransitionsAccessor::EnsureHasFullTransitionArray() {
  if (encoding() == kFullTransitionArray) return;
502 503
  int nof =
      (encoding() == kUninitialized || encoding() == kMigrationTarget) ? 0 : 1;
504
  Handle<TransitionArray> result = isolate_->factory()->NewTransitionArray(nof);
505 506
  Reload();  // Reload after possible GC.
  if (nof == 1) {
507
    if (encoding() == kUninitialized) {
508 509 510 511
      // If allocation caused GC and cleared the target, trim the new array.
      result->SetNumberOfTransitions(0);
    } else {
      // Otherwise populate the new array.
512
      Handle<Map> target(GetSimpleTransition(), isolate_);
513
      Name key = GetSimpleTransitionKey(*target);
514
      result->Set(0, key, HeapObjectReference::Weak(*target));
515
    }
516
  }
517
  ReplaceTransitions(MaybeObject::FromObject(*result));
518
  Reload();  // Reload after replacing transitions.
519 520
}

521
void TransitionsAccessor::TraverseTransitionTreeInternal(
522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565
    const TraverseCallback& callback, DisallowGarbageCollection* no_gc) {
  // Mostly arbitrary but more than enough to run the test suite in static
  // memory.
  static constexpr int kStaticStackSize = 16;
  base::SmallVector<Map, kStaticStackSize> stack;
  stack.emplace_back(map_);

  // Pre-order iterative depth-first-search.
  while (!stack.empty()) {
    Map current_map = stack.back();
    stack.pop_back();

    callback(current_map);

    MaybeObject raw_transitions =
        current_map.raw_transitions(isolate_, kAcquireLoad);
    Encoding encoding = GetEncoding(isolate_, raw_transitions);

    switch (encoding) {
      case kPrototypeInfo:
      case kUninitialized:
      case kMigrationTarget:
        break;
      case kWeakRef: {
        stack.emplace_back(
            Map::cast(raw_transitions->GetHeapObjectAssumeWeak()));
        break;
      }
      case kFullTransitionArray: {
        TransitionArray transitions =
            TransitionArray::cast(raw_transitions->GetHeapObjectAssumeStrong());
        if (transitions.HasPrototypeTransitions()) {
          WeakFixedArray proto_trans = transitions.GetPrototypeTransitions();
          int length =
              TransitionArray::NumberOfPrototypeTransitions(proto_trans);
          for (int i = 0; i < length; ++i) {
            int index = TransitionArray::kProtoTransitionHeaderSize + i;
            MaybeObject target = proto_trans.Get(index);
            HeapObject heap_object;
            if (target->GetHeapObjectIfWeak(&heap_object)) {
              stack.emplace_back(Map::cast(heap_object));
            } else {
              DCHECK(target->IsCleared());
            }
566
          }
567
        }
568 569 570 571
        for (int i = 0; i < transitions.number_of_transitions(); ++i) {
          stack.emplace_back(transitions.GetTarget(i));
        }
        break;
572 573 574 575 576 577
      }
    }
  }
}

#ifdef DEBUG
578
void TransitionsAccessor::CheckNewTransitionsAreConsistent(
579
    TransitionArray old_transitions, Object transitions) {
580
  // This function only handles full transition arrays.
581
  DCHECK_EQ(kFullTransitionArray, encoding());
582
  TransitionArray new_transitions = TransitionArray::cast(transitions);
583 584
  for (int i = 0; i < old_transitions.number_of_transitions(); i++) {
    Map target = old_transitions.GetTarget(i);
585 586
    if (target.instance_descriptors(isolate_) ==
        map_.instance_descriptors(isolate_)) {
587
      Name key = old_transitions.GetKey(i);
588
      int new_target_index;
589
      if (IsSpecialTransition(ReadOnlyRoots(isolate_), key)) {
590
        new_target_index = new_transitions.SearchSpecial(Symbol::cast(key));
591
      } else {
592
        PropertyDetails details = GetTargetDetails(key, target);
593
        new_target_index =
594
            new_transitions.Search(details.kind(), key, details.attributes());
595 596
      }
      DCHECK_NE(TransitionArray::kNotFound, new_target_index);
597
      DCHECK_EQ(target, new_transitions.GetTarget(new_target_index));
598 599 600 601 602 603 604
    }
  }
}
#endif

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

605
int TransitionArray::SearchDetails(int transition, PropertyKind kind,
606 607 608 609
                                   PropertyAttributes attributes,
                                   int* out_insertion_index) {
  int nof_transitions = number_of_transitions();
  DCHECK(transition < nof_transitions);
610
  Name key = GetKey(transition);
611 612
  for (; transition < nof_transitions && GetKey(transition) == key;
       transition++) {
613
    Map target = GetTarget(transition);
614
    PropertyDetails target_details =
615
        TransitionsAccessor::GetTargetDetails(key, target);
616

617
    int cmp = CompareDetails(kind, attributes, target_details.kind(),
618 619 620 621 622 623 624
                             target_details.attributes());
    if (cmp == 0) {
      return transition;
    } else if (cmp < 0) {
      break;
    }
  }
625
  if (out_insertion_index != nullptr) *out_insertion_index = transition;
626 627 628
  return kNotFound;
}

629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651
Map TransitionArray::SearchDetailsAndGetTarget(int transition,
                                               PropertyKind kind,
                                               PropertyAttributes attributes) {
  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);
    PropertyDetails target_details =
        TransitionsAccessor::GetTargetDetails(key, target);

    int cmp = CompareDetails(kind, attributes, target_details.kind(),
                             target_details.attributes());
    if (cmp == 0) {
      return target;
    } else if (cmp < 0) {
      break;
    }
  }
  return Map();
}

652
int TransitionArray::Search(PropertyKind kind, Name name,
653 654
                            PropertyAttributes attributes,
                            int* out_insertion_index) {
655
  int transition = SearchName(name, false, out_insertion_index);
656
  if (transition == kNotFound) return kNotFound;
657
  return SearchDetails(transition, kind, attributes, out_insertion_index);
658
}
659

660 661
Map TransitionArray::SearchAndGetTarget(PropertyKind kind, Name name,
                                        PropertyAttributes attributes) {
662
  int transition = SearchName(name);
663 664 665 666 667 668
  if (transition == kNotFound) {
    return Map();
  }
  return SearchDetailsAndGetTarget(transition, kind, attributes);
}

669 670
void TransitionArray::ForEachTransitionTo(
    Name name, const ForEachTransitionCallback& callback) {
671
  int transition = SearchName(name);
672 673 674 675 676 677 678 679 680 681 682 683
  if (transition == kNotFound) return;

  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);
    callback(target);
  }
}

684
void TransitionArray::Sort() {
685
  DisallowGarbageCollection no_gc;
686 687
  // In-place insertion sort.
  int length = number_of_transitions();
688
  ReadOnlyRoots roots = GetReadOnlyRoots();
689
  for (int i = 1; i < length; i++) {
690
    Name key = GetKey(i);
691
    MaybeObject target = GetRawTarget(i);
692 693
    PropertyKind kind = kData;
    PropertyAttributes attributes = NONE;
694
    if (!TransitionsAccessor::IsSpecialTransition(roots, key)) {
695
      Map target_map = TransitionsAccessor::GetTargetFromRaw(target);
696
      PropertyDetails details =
697
          TransitionsAccessor::GetTargetDetails(key, target_map);
698 699 700 701 702
      kind = details.kind();
      attributes = details.attributes();
    }
    int j;
    for (j = i - 1; j >= 0; j--) {
703
      Name temp_key = GetKey(j);
704
      MaybeObject temp_target = GetRawTarget(j);
705 706
      PropertyKind temp_kind = kData;
      PropertyAttributes temp_attributes = NONE;
707
      if (!TransitionsAccessor::IsSpecialTransition(roots, temp_key)) {
708
        Map temp_target_map =
Yang Guo's avatar
Yang Guo committed
709
            TransitionsAccessor::GetTargetFromRaw(temp_target);
710 711
        PropertyDetails details =
            TransitionsAccessor::GetTargetDetails(temp_key, temp_target_map);
712 713 714
        temp_kind = details.kind();
        temp_attributes = details.attributes();
      }
715 716
      int cmp = CompareKeys(temp_key, temp_key.hash(), temp_kind,
                            temp_attributes, key, key.hash(), kind, attributes);
717 718
      if (cmp > 0) {
        SetKey(j + 1, temp_key);
719
        SetRawTarget(j + 1, temp_target);
720 721 722 723 724
      } else {
        break;
      }
    }
    SetKey(j + 1, key);
725
    SetRawTarget(j + 1, target);
726
  }
727
  DCHECK(IsSortedNoDuplicates());
728 729
}

730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747
bool TransitionsAccessor::HasIntegrityLevelTransitionTo(
    Map to, Symbol* out_symbol, PropertyAttributes* out_integrity_level) {
  ReadOnlyRoots roots(isolate_);
  if (SearchSpecial(roots.frozen_symbol()) == to) {
    if (out_integrity_level) *out_integrity_level = FROZEN;
    if (out_symbol) *out_symbol = roots.frozen_symbol();
  } else if (SearchSpecial(roots.sealed_symbol()) == to) {
    if (out_integrity_level) *out_integrity_level = SEALED;
    if (out_symbol) *out_symbol = roots.sealed_symbol();
  } else if (SearchSpecial(roots.nonextensible_symbol()) == to) {
    if (out_integrity_level) *out_integrity_level = NONE;
    if (out_symbol) *out_symbol = roots.nonextensible_symbol();
  } else {
    return false;
  }
  return true;
}

748 749
}  // namespace internal
}  // namespace v8