V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
transitions.cc
1 // Copyright 2012 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "src/transitions.h"
6 
7 #include "src/objects-inl.h"
8 #include "src/transitions-inl.h"
9 #include "src/utils.h"
10 
11 namespace v8 {
12 namespace internal {
13 
14 void TransitionsAccessor::Initialize() {
15  raw_transitions_ = map_->raw_transitions();
16  HeapObject* heap_object;
17  if (raw_transitions_->IsSmi() || raw_transitions_->IsCleared()) {
18  encoding_ = kUninitialized;
19  } else if (raw_transitions_->IsWeak()) {
20  encoding_ = kWeakRef;
21  } else if (raw_transitions_->GetHeapObjectIfStrong(&heap_object)) {
22  if (heap_object->IsTransitionArray()) {
23  encoding_ = kFullTransitionArray;
24  } else if (heap_object->IsPrototypeInfo()) {
25  encoding_ = kPrototypeInfo;
26  } else {
27  DCHECK(map_->is_deprecated());
28  DCHECK(heap_object->IsMap());
29  encoding_ = kMigrationTarget;
30  }
31  } else {
32  UNREACHABLE();
33  }
34 #if DEBUG
35  needs_reload_ = false;
36 #endif
37 }
38 
39 Map TransitionsAccessor::GetSimpleTransition() {
40  switch (encoding()) {
41  case kWeakRef:
42  return Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
43  default:
44  return Map();
45  }
46 }
47 
48 bool TransitionsAccessor::HasSimpleTransitionTo(Map map) {
49  switch (encoding()) {
50  case kWeakRef:
51  return raw_transitions_->GetHeapObjectAssumeWeak() == map;
52  case kPrototypeInfo:
53  case kUninitialized:
54  case kMigrationTarget:
55  case kFullTransitionArray:
56  return false;
57  }
58  UNREACHABLE();
59 }
60 
61 void TransitionsAccessor::Insert(Handle<Name> name, Handle<Map> target,
62  SimpleTransitionFlag flag) {
63  DCHECK(!map_handle_.is_null());
64  target->SetBackPointer(map_);
65 
66  // If the map doesn't have any transitions at all yet, install the new one.
67  if (encoding() == kUninitialized || encoding() == kMigrationTarget) {
68  if (flag == SIMPLE_PROPERTY_TRANSITION) {
69  ReplaceTransitions(HeapObjectReference::Weak(*target));
70  return;
71  }
72  // If the flag requires a full TransitionArray, allocate one.
73  Handle<TransitionArray> result =
74  isolate_->factory()->NewTransitionArray(0, 1);
75  ReplaceTransitions(MaybeObject::FromObject(*result));
76  Reload();
77  }
78 
79  bool is_special_transition = flag == SPECIAL_TRANSITION;
80  // If the map has a simple transition, check if it should be overwritten.
81  Map simple_transition = GetSimpleTransition();
82  if (!simple_transition.is_null()) {
83  Name key = GetSimpleTransitionKey(simple_transition);
84  PropertyDetails old_details = GetSimpleTargetDetails(simple_transition);
85  PropertyDetails new_details = is_special_transition
86  ? PropertyDetails::Empty()
87  : GetTargetDetails(*name, *target);
88  if (flag == SIMPLE_PROPERTY_TRANSITION && key->Equals(*name) &&
89  old_details.kind() == new_details.kind() &&
90  old_details.attributes() == new_details.attributes()) {
91  ReplaceTransitions(HeapObjectReference::Weak(*target));
92  return;
93  }
94  // Otherwise allocate a full TransitionArray with slack for a new entry.
95  Handle<Map> map(simple_transition, isolate_);
96  Handle<TransitionArray> result =
97  isolate_->factory()->NewTransitionArray(1, 1);
98  // Reload state; allocations might have caused it to be cleared.
99  Reload();
100  simple_transition = GetSimpleTransition();
101  if (!simple_transition.is_null()) {
102  DCHECK_EQ(*map, simple_transition);
103  if (encoding_ == kWeakRef) {
104  result->Set(0, GetSimpleTransitionKey(simple_transition),
105  HeapObjectReference::Weak(simple_transition));
106  } else {
107  UNREACHABLE();
108  }
109  } else {
110  result->SetNumberOfTransitions(0);
111  }
112  ReplaceTransitions(MaybeObject::FromObject(*result));
113  Reload();
114  }
115 
116  // At this point, we know that the map has a full TransitionArray.
117  DCHECK_EQ(kFullTransitionArray, encoding());
118 
119  int number_of_transitions = 0;
120  int new_nof = 0;
121  int insertion_index = kNotFound;
122  DCHECK_EQ(is_special_transition,
123  IsSpecialTransition(ReadOnlyRoots(isolate_), *name));
124  PropertyDetails details = is_special_transition
125  ? PropertyDetails::Empty()
126  : GetTargetDetails(*name, *target);
127 
128  {
129  DisallowHeapAllocation no_gc;
130  TransitionArray* array = transitions();
131  number_of_transitions = array->number_of_transitions();
132  new_nof = number_of_transitions;
133 
134  int index =
135  is_special_transition
136  ? array->SearchSpecial(Symbol::cast(*name), &insertion_index)
137  : array->Search(details.kind(), *name, details.attributes(),
138  &insertion_index);
139  // If an existing entry was found, overwrite it and return.
140  if (index != kNotFound) {
141  array->SetRawTarget(index, HeapObjectReference::Weak(*target));
142  return;
143  }
144 
145  ++new_nof;
146  CHECK_LE(new_nof, kMaxNumberOfTransitions);
147  DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
148 
149  // If there is enough capacity, insert new entry into the existing array.
150  if (new_nof <= array->Capacity()) {
151  array->SetNumberOfTransitions(new_nof);
152  for (index = number_of_transitions; index > insertion_index; --index) {
153  array->SetKey(index, array->GetKey(index - 1));
154  array->SetRawTarget(index, array->GetRawTarget(index - 1));
155  }
156  array->SetKey(index, *name);
157  array->SetRawTarget(index, HeapObjectReference::Weak(*target));
158  SLOW_DCHECK(array->IsSortedNoDuplicates());
159  return;
160  }
161  }
162 
163  // We're gonna need a bigger TransitionArray.
164  Handle<TransitionArray> result = isolate_->factory()->NewTransitionArray(
165  new_nof,
166  Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions));
167 
168  // The map's transition array may have shrunk during the allocation above as
169  // it was weakly traversed, though it is guaranteed not to disappear. Trim the
170  // 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  int index =
182  is_special_transition
183  ? array->SearchSpecial(Symbol::cast(*name), &insertion_index)
184  : array->Search(details.kind(), *name, details.attributes(),
185  &insertion_index);
186  if (index == kNotFound) {
187  ++new_nof;
188  } else {
189  insertion_index = index;
190  }
191  DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
192 
193  result->SetNumberOfTransitions(new_nof);
194  }
195 
196  if (array->HasPrototypeTransitions()) {
197  result->SetPrototypeTransitions(array->GetPrototypeTransitions());
198  }
199 
200  DCHECK_NE(kNotFound, insertion_index);
201  for (int i = 0; i < insertion_index; ++i) {
202  result->Set(i, array->GetKey(i), array->GetRawTarget(i));
203  }
204  result->Set(insertion_index, *name, HeapObjectReference::Weak(*target));
205  for (int i = insertion_index; i < number_of_transitions; ++i) {
206  result->Set(i + 1, array->GetKey(i), array->GetRawTarget(i));
207  }
208 
209  SLOW_DCHECK(result->IsSortedNoDuplicates());
210  ReplaceTransitions(MaybeObject::FromObject(*result));
211 }
212 
213 Map TransitionsAccessor::SearchTransition(Name name, PropertyKind kind,
214  PropertyAttributes attributes) {
215  DCHECK(name->IsUniqueName());
216  switch (encoding()) {
217  case kPrototypeInfo:
218  case kUninitialized:
219  case kMigrationTarget:
220  return Map();
221  case kWeakRef: {
222  Map map = Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
223  if (!IsMatchingMap(map, name, kind, attributes)) return Map();
224  return map;
225  }
226  case kFullTransitionArray: {
227  int transition = transitions()->Search(kind, name, attributes);
228  if (transition == kNotFound) return Map();
229  return transitions()->GetTarget(transition);
230  }
231  }
232  UNREACHABLE();
233 }
234 
235 Map TransitionsAccessor::SearchSpecial(Symbol name) {
236  if (encoding() != kFullTransitionArray) return Map();
237  int transition = transitions()->SearchSpecial(name);
238  if (transition == kNotFound) return Map();
239  return transitions()->GetTarget(transition);
240 }
241 
242 // static
243 bool TransitionsAccessor::IsSpecialTransition(ReadOnlyRoots roots, Name name) {
244  if (!name->IsSymbol()) return false;
245  return name == roots.nonextensible_symbol() ||
246  name == roots.sealed_symbol() || name == roots.frozen_symbol() ||
247  name == roots.elements_transition_symbol() ||
248  name == roots.strict_function_transition_symbol();
249 }
250 
251 MaybeHandle<Map> TransitionsAccessor::FindTransitionToDataProperty(
252  Handle<Name> name, RequestedLocation requested_location) {
253  DCHECK(name->IsUniqueName());
254  DisallowHeapAllocation no_gc;
255  PropertyAttributes attributes = name->IsPrivate() ? DONT_ENUM : NONE;
256  Map target = SearchTransition(*name, kData, attributes);
257  if (target.is_null()) return MaybeHandle<Map>();
258  PropertyDetails details = target->GetLastDescriptorDetails();
259  DCHECK_EQ(attributes, details.attributes());
260  DCHECK_EQ(kData, details.kind());
261  if (requested_location == kFieldOnly && details.location() != kField) {
262  return MaybeHandle<Map>();
263  }
264  return Handle<Map>(target, isolate_);
265 }
266 
267 Handle<String> TransitionsAccessor::ExpectedTransitionKey() {
268  DisallowHeapAllocation no_gc;
269  switch (encoding()) {
270  case kPrototypeInfo:
271  case kUninitialized:
272  case kMigrationTarget:
273  case kFullTransitionArray:
274  return Handle<String>::null();
275  case kWeakRef: {
276  Map target = Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
277  PropertyDetails details = GetSimpleTargetDetails(target);
278  if (details.location() != kField) return Handle<String>::null();
279  DCHECK_EQ(kData, details.kind());
280  if (details.attributes() != NONE) return Handle<String>::null();
281  Name name = GetSimpleTransitionKey(target);
282  if (!name->IsString()) return Handle<String>::null();
283  return handle(String::cast(name), isolate_);
284  }
285  }
286  UNREACHABLE();
287 }
288 
289 Handle<Map> TransitionsAccessor::ExpectedTransitionTarget() {
290  DCHECK(!ExpectedTransitionKey().is_null());
291  return handle(GetTarget(0), isolate_);
292 }
293 
294 bool TransitionsAccessor::CanHaveMoreTransitions() {
295  if (map_->is_dictionary_map()) return false;
296  if (encoding() == kFullTransitionArray) {
297  return transitions()->number_of_transitions() < kMaxNumberOfTransitions;
298  }
299  return true;
300 }
301 
302 // static
303 bool TransitionsAccessor::IsMatchingMap(Map target, Name name,
304  PropertyKind kind,
305  PropertyAttributes attributes) {
306  int descriptor = target->LastAdded();
307  DescriptorArray* descriptors = target->instance_descriptors();
308  Name key = descriptors->GetKey(descriptor);
309  if (key != name) return false;
310  PropertyDetails details = descriptors->GetDetails(descriptor);
311  return (details.kind() == kind && details.attributes() == attributes);
312 }
313 
314 // static
315 bool TransitionArray::CompactPrototypeTransitionArray(Isolate* isolate,
316  WeakFixedArray* array) {
317  const int header = kProtoTransitionHeaderSize;
318  int number_of_transitions = NumberOfPrototypeTransitions(array);
319  if (number_of_transitions == 0) {
320  // Empty array cannot be compacted.
321  return false;
322  }
323  int new_number_of_transitions = 0;
324  for (int i = 0; i < number_of_transitions; i++) {
325  MaybeObject target = array->Get(header + i);
326  DCHECK(target->IsCleared() ||
327  (target->IsWeak() && target->GetHeapObject()->IsMap()));
328  if (!target->IsCleared()) {
329  if (new_number_of_transitions != i) {
330  array->Set(header + new_number_of_transitions, target);
331  }
332  new_number_of_transitions++;
333  }
334  }
335  // Fill slots that became free with undefined value.
336  MaybeObject undefined =
337  MaybeObject::FromObject(*isolate->factory()->undefined_value());
338  for (int i = new_number_of_transitions; i < number_of_transitions; i++) {
339  array->Set(header + i, undefined);
340  }
341  if (number_of_transitions != new_number_of_transitions) {
342  SetNumberOfPrototypeTransitions(array, new_number_of_transitions);
343  }
344  return new_number_of_transitions < number_of_transitions;
345 }
346 
347 
348 // static
349 Handle<WeakFixedArray> TransitionArray::GrowPrototypeTransitionArray(
350  Handle<WeakFixedArray> array, int new_capacity, Isolate* isolate) {
351  // Grow array by factor 2 up to MaxCachedPrototypeTransitions.
352  int capacity = array->length() - kProtoTransitionHeaderSize;
353  new_capacity = Min(kMaxCachedPrototypeTransitions, new_capacity);
354  DCHECK_GT(new_capacity, capacity);
355  int grow_by = new_capacity - capacity;
356  array =
357  isolate->factory()->CopyWeakFixedArrayAndGrow(array, grow_by, TENURED);
358  if (capacity < 0) {
359  // There was no prototype transitions array before, so the size
360  // couldn't be copied. Initialize it explicitly.
361  SetNumberOfPrototypeTransitions(*array, 0);
362  }
363  return array;
364 }
365 
366 void TransitionsAccessor::PutPrototypeTransition(Handle<Object> prototype,
367  Handle<Map> target_map) {
368  DCHECK(HeapObject::cast(*prototype)->map()->IsMap());
369  // Don't cache prototype transition if this map is either shared, or a map of
370  // a prototype.
371  if (map_->is_prototype_map()) return;
372  if (map_->is_dictionary_map() || !FLAG_cache_prototype_transitions) return;
373 
374  const int header = TransitionArray::kProtoTransitionHeaderSize;
375 
376  Handle<WeakFixedArray> cache(GetPrototypeTransitions(), isolate_);
377  int capacity = cache->length() - header;
378  int transitions = TransitionArray::NumberOfPrototypeTransitions(*cache) + 1;
379 
380  if (transitions > capacity) {
381  // Grow the array if compacting it doesn't free space.
382  if (!TransitionArray::CompactPrototypeTransitionArray(isolate_, *cache)) {
383  if (capacity == TransitionArray::kMaxCachedPrototypeTransitions) return;
384  cache = TransitionArray::GrowPrototypeTransitionArray(
385  cache, 2 * transitions, isolate_);
386  Reload();
387  SetPrototypeTransitions(cache);
388  }
389  }
390 
391  // Reload number of transitions as they might have been compacted.
392  int last = TransitionArray::NumberOfPrototypeTransitions(*cache);
393  int entry = header + last;
394 
395  cache->Set(entry, HeapObjectReference::Weak(*target_map));
396  TransitionArray::SetNumberOfPrototypeTransitions(*cache, last + 1);
397 }
398 
399 Handle<Map> TransitionsAccessor::GetPrototypeTransition(
400  Handle<Object> prototype) {
401  DisallowHeapAllocation no_gc;
402  WeakFixedArray* cache = GetPrototypeTransitions();
403  int length = TransitionArray::NumberOfPrototypeTransitions(cache);
404  for (int i = 0; i < length; i++) {
405  MaybeObject target =
406  cache->Get(TransitionArray::kProtoTransitionHeaderSize + i);
407  DCHECK(target->IsWeakOrCleared());
408  HeapObject* heap_object;
409  if (target->GetHeapObjectIfWeak(&heap_object)) {
410  Map map = Map::cast(heap_object);
411  if (map->prototype() == *prototype) {
412  return handle(map, isolate_);
413  }
414  }
415  }
416  return Handle<Map>();
417 }
418 
419 WeakFixedArray* TransitionsAccessor::GetPrototypeTransitions() {
420  if (encoding() != kFullTransitionArray ||
421  !transitions()->HasPrototypeTransitions()) {
422  return ReadOnlyRoots(isolate_).empty_weak_fixed_array();
423  }
424  return transitions()->GetPrototypeTransitions();
425 }
426 
427 // static
428 void TransitionArray::SetNumberOfPrototypeTransitions(
429  WeakFixedArray* proto_transitions, int value) {
430  DCHECK_NE(proto_transitions->length(), 0);
431  proto_transitions->Set(kProtoTransitionNumberOfEntriesOffset,
432  MaybeObject::FromSmi(Smi::FromInt(value)));
433 }
434 
435 int TransitionsAccessor::NumberOfTransitions() {
436  switch (encoding()) {
437  case kPrototypeInfo:
438  case kUninitialized:
439  case kMigrationTarget:
440  return 0;
441  case kWeakRef:
442  return 1;
443  case kFullTransitionArray:
444  return transitions()->number_of_transitions();
445  }
446  UNREACHABLE();
447  return 0; // Make GCC happy.
448 }
449 
450 void TransitionsAccessor::SetMigrationTarget(Map migration_target) {
451  // We only cache the migration target for maps with empty transitions for GC's
452  // sake.
453  if (encoding() != kUninitialized) return;
454  DCHECK(map_->is_deprecated());
455  map_->set_raw_transitions(MaybeObject::FromObject(migration_target));
456  MarkNeedsReload();
457 }
458 
459 Map TransitionsAccessor::GetMigrationTarget() {
460  if (encoding() == kMigrationTarget) {
461  return map_->raw_transitions()->cast<Map>();
462  }
463  return Map();
464 }
465 
466 void TransitionArray::Zap(Isolate* isolate) {
467  MemsetPointer(ObjectSlot(data_start() + kPrototypeTransitionsIndex),
468  ReadOnlyRoots(isolate).the_hole_value(),
469  length() - kPrototypeTransitionsIndex);
470  SetNumberOfTransitions(0);
471 }
472 
473 void TransitionsAccessor::ReplaceTransitions(MaybeObject new_transitions) {
474  if (encoding() == kFullTransitionArray) {
475  TransitionArray* old_transitions = transitions();
476 #if DEBUG
477  CheckNewTransitionsAreConsistent(
478  old_transitions, new_transitions->GetHeapObjectAssumeStrong());
479  DCHECK(old_transitions != new_transitions->GetHeapObjectAssumeStrong());
480 #endif
481  // Transition arrays are not shared. When one is replaced, it should not
482  // keep referenced objects alive, so we zap it.
483  // When there is another reference to the array somewhere (e.g. a handle),
484  // not zapping turns from a waste of memory into a source of crashes.
485  old_transitions->Zap(isolate_);
486  }
487  map_->set_raw_transitions(new_transitions);
488  MarkNeedsReload();
489 }
490 
491 void TransitionsAccessor::SetPrototypeTransitions(
492  Handle<WeakFixedArray> proto_transitions) {
493  EnsureHasFullTransitionArray();
494  transitions()->SetPrototypeTransitions(*proto_transitions);
495 }
496 
497 void TransitionsAccessor::EnsureHasFullTransitionArray() {
498  if (encoding() == kFullTransitionArray) return;
499  int nof =
500  (encoding() == kUninitialized || encoding() == kMigrationTarget) ? 0 : 1;
501  Handle<TransitionArray> result = isolate_->factory()->NewTransitionArray(nof);
502  Reload(); // Reload after possible GC.
503  if (nof == 1) {
504  if (encoding() == kUninitialized) {
505  // If allocation caused GC and cleared the target, trim the new array.
506  result->SetNumberOfTransitions(0);
507  } else {
508  // Otherwise populate the new array.
509  Handle<Map> target(GetSimpleTransition(), isolate_);
510  Name key = GetSimpleTransitionKey(*target);
511  result->Set(0, key, HeapObjectReference::Weak(*target));
512  }
513  }
514  ReplaceTransitions(MaybeObject::FromObject(*result));
515  Reload(); // Reload after replacing transitions.
516 }
517 
518 void TransitionsAccessor::TraverseTransitionTreeInternal(
519  TraverseCallback callback, void* data, DisallowHeapAllocation* no_gc) {
520  switch (encoding()) {
521  case kPrototypeInfo:
522  case kUninitialized:
523  case kMigrationTarget:
524  break;
525  case kWeakRef: {
526  Map simple_target =
527  Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
528  TransitionsAccessor(isolate_, simple_target, no_gc)
529  .TraverseTransitionTreeInternal(callback, data, no_gc);
530  break;
531  }
532  case kFullTransitionArray: {
533  if (transitions()->HasPrototypeTransitions()) {
534  WeakFixedArray* proto_trans = transitions()->GetPrototypeTransitions();
535  int length = TransitionArray::NumberOfPrototypeTransitions(proto_trans);
536  for (int i = 0; i < length; ++i) {
537  int index = TransitionArray::kProtoTransitionHeaderSize + i;
538  MaybeObject target = proto_trans->Get(index);
539  HeapObject* heap_object;
540  if (target->GetHeapObjectIfWeak(&heap_object)) {
541  TransitionsAccessor(isolate_, Map::cast(heap_object), no_gc)
542  .TraverseTransitionTreeInternal(callback, data, no_gc);
543  } else {
544  DCHECK(target->IsCleared());
545  }
546  }
547  }
548  for (int i = 0; i < transitions()->number_of_transitions(); ++i) {
549  TransitionsAccessor(isolate_, transitions()->GetTarget(i), no_gc)
550  .TraverseTransitionTreeInternal(callback, data, no_gc);
551  }
552  break;
553  }
554  }
555  callback(map_, data);
556 }
557 
558 #ifdef DEBUG
559 void TransitionsAccessor::CheckNewTransitionsAreConsistent(
560  TransitionArray* old_transitions, Object* transitions) {
561  // This function only handles full transition arrays.
562  DCHECK_EQ(kFullTransitionArray, encoding());
563  TransitionArray* new_transitions = TransitionArray::cast(transitions);
564  for (int i = 0; i < old_transitions->number_of_transitions(); i++) {
565  Map target = old_transitions->GetTarget(i);
566  if (target->instance_descriptors() == map_->instance_descriptors()) {
567  Name key = old_transitions->GetKey(i);
568  int new_target_index;
569  if (IsSpecialTransition(ReadOnlyRoots(isolate_), key)) {
570  new_target_index = new_transitions->SearchSpecial(Symbol::cast(key));
571  } else {
572  PropertyDetails details = GetTargetDetails(key, target);
573  new_target_index =
574  new_transitions->Search(details.kind(), key, details.attributes());
575  }
576  DCHECK_NE(TransitionArray::kNotFound, new_target_index);
577  DCHECK_EQ(target, new_transitions->GetTarget(new_target_index));
578  }
579  }
580 }
581 #endif
582 
583 // Private non-static helper functions (operating on full transition arrays).
584 
585 int TransitionArray::SearchDetails(int transition, PropertyKind kind,
586  PropertyAttributes attributes,
587  int* out_insertion_index) {
588  int nof_transitions = number_of_transitions();
589  DCHECK(transition < nof_transitions);
590  Name key = GetKey(transition);
591  for (; transition < nof_transitions && GetKey(transition) == key;
592  transition++) {
593  Map target = GetTarget(transition);
594  PropertyDetails target_details =
595  TransitionsAccessor::GetTargetDetails(key, target);
596 
597  int cmp = CompareDetails(kind, attributes, target_details.kind(),
598  target_details.attributes());
599  if (cmp == 0) {
600  return transition;
601  } else if (cmp < 0) {
602  break;
603  }
604  }
605  if (out_insertion_index != nullptr) *out_insertion_index = transition;
606  return kNotFound;
607 }
608 
609 int TransitionArray::Search(PropertyKind kind, Name name,
610  PropertyAttributes attributes,
611  int* out_insertion_index) {
612  int transition = SearchName(name, out_insertion_index);
613  if (transition == kNotFound) return kNotFound;
614  return SearchDetails(transition, kind, attributes, out_insertion_index);
615 }
616 
617 void TransitionArray::Sort() {
618  DisallowHeapAllocation no_gc;
619  // In-place insertion sort.
620  int length = number_of_transitions();
621  ReadOnlyRoots roots = GetReadOnlyRoots();
622  for (int i = 1; i < length; i++) {
623  Name key = GetKey(i);
624  MaybeObject target = GetRawTarget(i);
625  PropertyKind kind = kData;
626  PropertyAttributes attributes = NONE;
627  if (!TransitionsAccessor::IsSpecialTransition(roots, key)) {
628  Map target_map = TransitionsAccessor::GetTargetFromRaw(target);
629  PropertyDetails details =
630  TransitionsAccessor::GetTargetDetails(key, target_map);
631  kind = details.kind();
632  attributes = details.attributes();
633  }
634  int j;
635  for (j = i - 1; j >= 0; j--) {
636  Name temp_key = GetKey(j);
637  MaybeObject temp_target = GetRawTarget(j);
638  PropertyKind temp_kind = kData;
639  PropertyAttributes temp_attributes = NONE;
640  if (!TransitionsAccessor::IsSpecialTransition(roots, temp_key)) {
641  Map temp_target_map =
642  TransitionsAccessor::GetTargetFromRaw(temp_target);
643  PropertyDetails details =
644  TransitionsAccessor::GetTargetDetails(temp_key, temp_target_map);
645  temp_kind = details.kind();
646  temp_attributes = details.attributes();
647  }
648  int cmp =
649  CompareKeys(temp_key, temp_key->Hash(), temp_kind, temp_attributes,
650  key, key->Hash(), kind, attributes);
651  if (cmp > 0) {
652  SetKey(j + 1, temp_key);
653  SetRawTarget(j + 1, temp_target);
654  } else {
655  break;
656  }
657  }
658  SetKey(j + 1, key);
659  SetRawTarget(j + 1, target);
660  }
661  DCHECK(IsSortedNoDuplicates());
662 }
663 
664 } // namespace internal
665 } // namespace v8
Definition: libplatform.h:13