• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/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 namespace v8 {
13 namespace internal {
14 
15 // static
GetSimpleTransition(Isolate * isolate,Handle<Map> map)16 Map TransitionsAccessor::GetSimpleTransition(Isolate* isolate,
17                                              Handle<Map> map) {
18   MaybeObject raw_transitions = map->raw_transitions(isolate, kAcquireLoad);
19   switch (GetEncoding(isolate, raw_transitions)) {
20     case kWeakRef:
21       return Map::cast(raw_transitions->GetHeapObjectAssumeWeak());
22     default:
23       return Map();
24   }
25 }
26 
HasSimpleTransitionTo(Map map)27 bool TransitionsAccessor::HasSimpleTransitionTo(Map map) {
28   switch (encoding()) {
29     case kWeakRef:
30       return raw_transitions_->GetHeapObjectAssumeWeak() == map;
31     case kPrototypeInfo:
32     case kUninitialized:
33     case kMigrationTarget:
34     case kFullTransitionArray:
35       return false;
36   }
37   UNREACHABLE();
38 }
39 
40 // static
Insert(Isolate * isolate,Handle<Map> map,Handle<Name> name,Handle<Map> target,SimpleTransitionFlag flag)41 void TransitionsAccessor::Insert(Isolate* isolate, Handle<Map> map,
42                                  Handle<Name> name, Handle<Map> target,
43                                  SimpleTransitionFlag flag) {
44   Encoding encoding = GetEncoding(isolate, map);
45   DCHECK_NE(kPrototypeInfo, encoding);
46   target->SetBackPointer(*map);
47 
48   // If the map doesn't have any transitions at all yet, install the new one.
49   if (encoding == kUninitialized || encoding == kMigrationTarget) {
50     if (flag == SIMPLE_PROPERTY_TRANSITION) {
51       ReplaceTransitions(isolate, map, HeapObjectReference::Weak(*target));
52       return;
53     }
54     // If the flag requires a full TransitionArray, allocate one.
55     Handle<TransitionArray> result =
56         isolate->factory()->NewTransitionArray(1, 0);
57     result->Set(0, *name, HeapObjectReference::Weak(*target));
58     ReplaceTransitions(isolate, map, result);
59     DCHECK_EQ(kFullTransitionArray, GetEncoding(isolate, *result));
60     return;
61   }
62 
63   if (encoding == kWeakRef) {
64     Map simple_transition = GetSimpleTransition(isolate, map);
65     DCHECK(!simple_transition.is_null());
66 
67     if (flag == SIMPLE_PROPERTY_TRANSITION) {
68       Name key = GetSimpleTransitionKey(simple_transition);
69       PropertyDetails old_details =
70           simple_transition.GetLastDescriptorDetails(isolate);
71       PropertyDetails new_details = GetTargetDetails(*name, *target);
72       if (key.Equals(*name) && old_details.kind() == new_details.kind() &&
73           old_details.attributes() == new_details.attributes()) {
74         ReplaceTransitions(isolate, map, HeapObjectReference::Weak(*target));
75         return;
76       }
77     }
78 
79     // Otherwise allocate a full TransitionArray with slack for a new entry.
80     Handle<TransitionArray> result =
81         isolate->factory()->NewTransitionArray(1, 1);
82 
83     // Reload `simple_transition`. Allocations might have caused it to be
84     // cleared.
85     simple_transition = GetSimpleTransition(isolate, map);
86     if (simple_transition.is_null()) {
87       result->Set(0, *name, HeapObjectReference::Weak(*target));
88       ReplaceTransitions(isolate, map, result);
89       DCHECK_EQ(kFullTransitionArray, GetEncoding(isolate, *result));
90       return;
91     }
92 
93     // Insert the original transition in index 0.
94     result->Set(0, GetSimpleTransitionKey(simple_transition),
95                 HeapObjectReference::Weak(simple_transition));
96 
97     // Search for the correct index to insert the new transition.
98     int insertion_index;
99     int index;
100     if (flag == SPECIAL_TRANSITION) {
101       index =
102           result->SearchSpecial(Symbol::cast(*name), false, &insertion_index);
103     } else {
104       PropertyDetails details = GetTargetDetails(*name, *target);
105       index = result->Search(details.kind(), *name, details.attributes(),
106                              &insertion_index);
107     }
108     DCHECK_EQ(index, kNotFound);
109     USE(index);
110 
111     result->SetNumberOfTransitions(2);
112     if (insertion_index == 0) {
113       // If the new transition will be inserted in index 0, move the original
114       // transition to index 1.
115       result->Set(1, GetSimpleTransitionKey(simple_transition),
116                   HeapObjectReference::Weak(simple_transition));
117     }
118     result->SetKey(insertion_index, *name);
119     result->SetRawTarget(insertion_index, HeapObjectReference::Weak(*target));
120 
121     SLOW_DCHECK(result->IsSortedNoDuplicates());
122     ReplaceTransitions(isolate, map, result);
123     DCHECK_EQ(kFullTransitionArray, GetEncoding(isolate, *result));
124     return;
125   }
126 
127   // At this point, we know that the map has a full TransitionArray.
128   DCHECK_EQ(kFullTransitionArray, encoding);
129 
130   int number_of_transitions = 0;
131   int new_nof = 0;
132   int insertion_index = kNotFound;
133   const bool is_special_transition = flag == SPECIAL_TRANSITION;
134   DCHECK_EQ(is_special_transition,
135             IsSpecialTransition(ReadOnlyRoots(isolate), *name));
136   PropertyDetails details = is_special_transition
137                                 ? PropertyDetails::Empty()
138                                 : GetTargetDetails(*name, *target);
139 
140   {
141     DisallowGarbageCollection no_gc;
142     TransitionArray array = GetTransitionArray(isolate, map);
143     number_of_transitions = array.number_of_transitions();
144 
145     int index =
146         is_special_transition
147             ? array.SearchSpecial(Symbol::cast(*name), false, &insertion_index)
148             : array.Search(details.kind(), *name, details.attributes(),
149                            &insertion_index);
150     // If an existing entry was found, overwrite it and return.
151     if (index != kNotFound) {
152       base::SharedMutexGuard<base::kExclusive> shared_mutex_guard(
153           isolate->full_transition_array_access());
154       array.SetRawTarget(index, HeapObjectReference::Weak(*target));
155       return;
156     }
157 
158     new_nof = number_of_transitions + 1;
159     CHECK_LE(new_nof, kMaxNumberOfTransitions);
160     DCHECK_GE(insertion_index, 0);
161     DCHECK_LE(insertion_index, number_of_transitions);
162 
163     // If there is enough capacity, insert new entry into the existing array.
164     if (new_nof <= array.Capacity()) {
165       base::SharedMutexGuard<base::kExclusive> shared_mutex_guard(
166           isolate->full_transition_array_access());
167       array.SetNumberOfTransitions(new_nof);
168       for (int i = number_of_transitions; i > insertion_index; --i) {
169         array.SetKey(i, array.GetKey(i - 1));
170         array.SetRawTarget(i, array.GetRawTarget(i - 1));
171       }
172       array.SetKey(insertion_index, *name);
173       array.SetRawTarget(insertion_index, HeapObjectReference::Weak(*target));
174       SLOW_DCHECK(array.IsSortedNoDuplicates());
175       return;
176     }
177   }
178 
179   // We're gonna need a bigger TransitionArray.
180   Handle<TransitionArray> result = isolate->factory()->NewTransitionArray(
181       new_nof,
182       Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions));
183 
184   // The map's transition array may have shrunk during the allocation above as
185   // it was weakly traversed, though it is guaranteed not to disappear. Trim the
186   // result copy if needed, and recompute variables.
187   DisallowGarbageCollection no_gc;
188   TransitionArray array = GetTransitionArray(isolate, map);
189   if (array.number_of_transitions() != number_of_transitions) {
190     DCHECK_LT(array.number_of_transitions(), number_of_transitions);
191 
192     int index =
193         is_special_transition
194             ? array.SearchSpecial(Symbol::cast(*name), false, &insertion_index)
195             : array.Search(details.kind(), *name, details.attributes(),
196                            &insertion_index);
197     CHECK_EQ(index, kNotFound);
198     USE(index);
199     DCHECK_GE(insertion_index, 0);
200     DCHECK_LE(insertion_index, number_of_transitions);
201 
202     number_of_transitions = array.number_of_transitions();
203     new_nof = number_of_transitions + 1;
204     result->SetNumberOfTransitions(new_nof);
205   }
206 
207   if (array.HasPrototypeTransitions()) {
208     result->SetPrototypeTransitions(array.GetPrototypeTransitions());
209   }
210 
211   DCHECK_NE(kNotFound, insertion_index);
212   for (int i = 0; i < insertion_index; ++i) {
213     result->Set(i, array.GetKey(i), array.GetRawTarget(i));
214   }
215   result->Set(insertion_index, *name, HeapObjectReference::Weak(*target));
216   for (int i = insertion_index; i < number_of_transitions; ++i) {
217     result->Set(i + 1, array.GetKey(i), array.GetRawTarget(i));
218   }
219 
220   SLOW_DCHECK(result->IsSortedNoDuplicates());
221   ReplaceTransitions(isolate, map, result);
222 }
223 
SearchTransition(Name name,PropertyKind kind,PropertyAttributes attributes)224 Map TransitionsAccessor::SearchTransition(Name name, PropertyKind kind,
225                                           PropertyAttributes attributes) {
226   DCHECK(name.IsUniqueName());
227   switch (encoding()) {
228     case kPrototypeInfo:
229     case kUninitialized:
230     case kMigrationTarget:
231       return Map();
232     case kWeakRef: {
233       Map map = Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
234       if (!IsMatchingMap(map, name, kind, attributes)) return Map();
235       return map;
236     }
237     case kFullTransitionArray: {
238       base::SharedMutexGuardIf<base::kShared> scope(
239           isolate_->full_transition_array_access(), concurrent_access_);
240       return transitions().SearchAndGetTarget(kind, name, attributes);
241     }
242   }
243   UNREACHABLE();
244 }
245 
SearchSpecial(Symbol name)246 Map TransitionsAccessor::SearchSpecial(Symbol name) {
247   if (encoding() != kFullTransitionArray) return Map();
248   base::SharedMutexGuardIf<base::kShared> scope(
249       isolate_->full_transition_array_access(), concurrent_access_);
250   int transition = transitions().SearchSpecial(name, concurrent_access_);
251   if (transition == kNotFound) return Map();
252   return transitions().GetTarget(transition);
253 }
254 
255 // static
IsSpecialTransition(ReadOnlyRoots roots,Name name)256 bool TransitionsAccessor::IsSpecialTransition(ReadOnlyRoots roots, Name name) {
257   if (!name.IsSymbol()) return false;
258   return name == roots.nonextensible_symbol() ||
259          name == roots.sealed_symbol() || name == roots.frozen_symbol() ||
260          name == roots.elements_transition_symbol() ||
261          name == roots.strict_function_transition_symbol();
262 }
263 
FindTransitionToDataProperty(Handle<Name> name,RequestedLocation requested_location)264 MaybeHandle<Map> TransitionsAccessor::FindTransitionToDataProperty(
265     Handle<Name> name, RequestedLocation requested_location) {
266   DCHECK(name->IsUniqueName());
267   DisallowGarbageCollection no_gc;
268   PropertyAttributes attributes = name->IsPrivate() ? DONT_ENUM : NONE;
269   Map target = SearchTransition(*name, PropertyKind::kData, attributes);
270   if (target.is_null()) return MaybeHandle<Map>();
271   PropertyDetails details = target.GetLastDescriptorDetails(isolate_);
272   DCHECK_EQ(attributes, details.attributes());
273   DCHECK_EQ(PropertyKind::kData, details.kind());
274   if (requested_location == kFieldOnly &&
275       details.location() != PropertyLocation::kField) {
276     return MaybeHandle<Map>();
277   }
278   return Handle<Map>(target, isolate_);
279 }
280 
ForEachTransitionTo(Name name,const ForEachTransitionCallback & callback,DisallowGarbageCollection * no_gc)281 void TransitionsAccessor::ForEachTransitionTo(
282     Name name, const ForEachTransitionCallback& callback,
283     DisallowGarbageCollection* no_gc) {
284   DCHECK(name.IsUniqueName());
285   switch (encoding()) {
286     case kPrototypeInfo:
287     case kUninitialized:
288     case kMigrationTarget:
289       return;
290     case kWeakRef: {
291       Map target = Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
292       InternalIndex descriptor = target.LastAdded();
293       DescriptorArray descriptors = target.instance_descriptors(kRelaxedLoad);
294       Name key = descriptors.GetKey(descriptor);
295       if (key == name) {
296         callback(target);
297       }
298       return;
299     }
300     case kFullTransitionArray: {
301       base::SharedMutexGuardIf<base::kShared> scope(
302           isolate_->full_transition_array_access(), concurrent_access_);
303       return transitions().ForEachTransitionTo(name, callback);
304     }
305   }
306   UNREACHABLE();
307 }
308 
309 // static
CanHaveMoreTransitions(Isolate * isolate,Handle<Map> map)310 bool TransitionsAccessor::CanHaveMoreTransitions(Isolate* isolate,
311                                                  Handle<Map> map) {
312   if (map->is_dictionary_map()) return false;
313   MaybeObject raw_transitions = map->raw_transitions(isolate, kAcquireLoad);
314   if (GetEncoding(isolate, raw_transitions) == kFullTransitionArray) {
315     return GetTransitionArray(isolate, raw_transitions)
316                .number_of_transitions() < kMaxNumberOfTransitions;
317   }
318   return true;
319 }
320 
321 // static
IsMatchingMap(Map target,Name name,PropertyKind kind,PropertyAttributes attributes)322 bool TransitionsAccessor::IsMatchingMap(Map target, Name name,
323                                         PropertyKind kind,
324                                         PropertyAttributes attributes) {
325   InternalIndex descriptor = target.LastAdded();
326   DescriptorArray descriptors = target.instance_descriptors(kRelaxedLoad);
327   Name key = descriptors.GetKey(descriptor);
328   if (key != name) return false;
329   return descriptors.GetDetails(descriptor)
330       .HasKindAndAttributes(kind, attributes);
331 }
332 
333 // static
CompactPrototypeTransitionArray(Isolate * isolate,WeakFixedArray array)334 bool TransitionArray::CompactPrototypeTransitionArray(Isolate* isolate,
335                                                       WeakFixedArray array) {
336   const int header = kProtoTransitionHeaderSize;
337   int number_of_transitions = NumberOfPrototypeTransitions(array);
338   if (number_of_transitions == 0) {
339     // Empty array cannot be compacted.
340     return false;
341   }
342   int new_number_of_transitions = 0;
343   for (int i = 0; i < number_of_transitions; i++) {
344     MaybeObject target = array.Get(header + i);
345     DCHECK(target->IsCleared() ||
346            (target->IsWeak() && target->GetHeapObject().IsMap()));
347     if (!target->IsCleared()) {
348       if (new_number_of_transitions != i) {
349         array.Set(header + new_number_of_transitions, target);
350       }
351       new_number_of_transitions++;
352     }
353   }
354   // Fill slots that became free with undefined value.
355   MaybeObject undefined =
356       MaybeObject::FromObject(*isolate->factory()->undefined_value());
357   for (int i = new_number_of_transitions; i < number_of_transitions; i++) {
358     array.Set(header + i, undefined);
359   }
360   if (number_of_transitions != new_number_of_transitions) {
361     SetNumberOfPrototypeTransitions(array, new_number_of_transitions);
362   }
363   return new_number_of_transitions < number_of_transitions;
364 }
365 
366 // static
GrowPrototypeTransitionArray(Handle<WeakFixedArray> array,int new_capacity,Isolate * isolate)367 Handle<WeakFixedArray> TransitionArray::GrowPrototypeTransitionArray(
368     Handle<WeakFixedArray> array, int new_capacity, Isolate* isolate) {
369   // Grow array by factor 2 up to MaxCachedPrototypeTransitions.
370   int capacity = array->length() - kProtoTransitionHeaderSize;
371   new_capacity = std::min({kMaxCachedPrototypeTransitions, new_capacity});
372   DCHECK_GT(new_capacity, capacity);
373   int grow_by = new_capacity - capacity;
374   array = isolate->factory()->CopyWeakFixedArrayAndGrow(array, grow_by);
375   if (capacity < 0) {
376     // There was no prototype transitions array before, so the size
377     // couldn't be copied. Initialize it explicitly.
378     SetNumberOfPrototypeTransitions(*array, 0);
379   }
380   return array;
381 }
382 
383 // static
PutPrototypeTransition(Isolate * isolate,Handle<Map> map,Handle<Object> prototype,Handle<Map> target_map)384 void TransitionsAccessor::PutPrototypeTransition(Isolate* isolate,
385                                                  Handle<Map> map,
386                                                  Handle<Object> prototype,
387                                                  Handle<Map> target_map) {
388   DCHECK(HeapObject::cast(*prototype).map().IsMap());
389   // Don't cache prototype transition if this map is either shared, or a map of
390   // a prototype.
391   if (map->is_prototype_map()) return;
392   if (map->is_dictionary_map() || !FLAG_cache_prototype_transitions) return;
393 
394   const int header = TransitionArray::kProtoTransitionHeaderSize;
395 
396   Handle<WeakFixedArray> cache(GetPrototypeTransitions(isolate, map), isolate);
397   int capacity = cache->length() - header;
398   int transitions = TransitionArray::NumberOfPrototypeTransitions(*cache) + 1;
399 
400   base::SharedMutexGuard<base::kExclusive> scope(
401       isolate->full_transition_array_access());
402 
403   if (transitions > capacity) {
404     // Grow the array if compacting it doesn't free space.
405     if (!TransitionArray::CompactPrototypeTransitionArray(isolate, *cache)) {
406       if (capacity == TransitionArray::kMaxCachedPrototypeTransitions) return;
407       cache = TransitionArray::GrowPrototypeTransitionArray(
408           cache, 2 * transitions, isolate);
409       SetPrototypeTransitions(isolate, map, cache);
410     }
411   }
412 
413   // Reload number of transitions as they might have been compacted.
414   int last = TransitionArray::NumberOfPrototypeTransitions(*cache);
415   int entry = header + last;
416 
417   cache->Set(entry, HeapObjectReference::Weak(*target_map));
418   TransitionArray::SetNumberOfPrototypeTransitions(*cache, last + 1);
419 }
420 
421 // static
GetPrototypeTransition(Isolate * isolate,Handle<Map> map,Handle<Object> prototype)422 Handle<Map> TransitionsAccessor::GetPrototypeTransition(
423     Isolate* isolate, Handle<Map> map, Handle<Object> prototype) {
424   DisallowGarbageCollection no_gc;
425   WeakFixedArray cache = GetPrototypeTransitions(isolate, map);
426   int length = TransitionArray::NumberOfPrototypeTransitions(cache);
427   for (int i = 0; i < length; i++) {
428     MaybeObject target =
429         cache.Get(TransitionArray::kProtoTransitionHeaderSize + i);
430     DCHECK(target->IsWeakOrCleared());
431     HeapObject heap_object;
432     if (target->GetHeapObjectIfWeak(&heap_object)) {
433       Map target_map = Map::cast(heap_object);
434       if (target_map.prototype() == *prototype) {
435         return handle(target_map, isolate);
436       }
437     }
438   }
439   return Handle<Map>();
440 }
441 
442 // static
GetPrototypeTransitions(Isolate * isolate,Handle<Map> map)443 WeakFixedArray TransitionsAccessor::GetPrototypeTransitions(Isolate* isolate,
444                                                             Handle<Map> map) {
445   MaybeObject raw_transitions = map->raw_transitions(isolate, kAcquireLoad);
446   if (GetEncoding(isolate, raw_transitions) != kFullTransitionArray) {
447     return ReadOnlyRoots(isolate).empty_weak_fixed_array();
448   }
449   TransitionArray transition_array =
450       GetTransitionArray(isolate, raw_transitions);
451   if (!transition_array.HasPrototypeTransitions()) {
452     return ReadOnlyRoots(isolate).empty_weak_fixed_array();
453   }
454   return transition_array.GetPrototypeTransitions();
455 }
456 
457 // static
SetNumberOfPrototypeTransitions(WeakFixedArray proto_transitions,int value)458 void TransitionArray::SetNumberOfPrototypeTransitions(
459     WeakFixedArray proto_transitions, int value) {
460   DCHECK_NE(proto_transitions.length(), 0);
461   proto_transitions.Set(kProtoTransitionNumberOfEntriesOffset,
462                         MaybeObject::FromSmi(Smi::FromInt(value)));
463 }
464 
NumberOfTransitions()465 int TransitionsAccessor::NumberOfTransitions() {
466   switch (encoding()) {
467     case kPrototypeInfo:
468     case kUninitialized:
469     case kMigrationTarget:
470       return 0;
471     case kWeakRef:
472       return 1;
473     case kFullTransitionArray:
474       return transitions().number_of_transitions();
475   }
476   UNREACHABLE();
477 }
478 
479 // static
SetMigrationTarget(Isolate * isolate,Handle<Map> map,Map migration_target)480 void TransitionsAccessor::SetMigrationTarget(Isolate* isolate, Handle<Map> map,
481                                              Map migration_target) {
482   // We only cache the migration target for maps with empty transitions for GC's
483   // sake.
484   if (GetEncoding(isolate, map) != kUninitialized) return;
485   DCHECK(map->is_deprecated());
486   map->set_raw_transitions(MaybeObject::FromObject(migration_target),
487                            kReleaseStore);
488 }
489 
GetMigrationTarget()490 Map TransitionsAccessor::GetMigrationTarget() {
491   if (encoding() == kMigrationTarget) {
492     return map_.raw_transitions(kAcquireLoad)->cast<Map>();
493   }
494   return Map();
495 }
496 
497 // static
ReplaceTransitions(Isolate * isolate,Handle<Map> map,MaybeObject new_transitions)498 void TransitionsAccessor::ReplaceTransitions(Isolate* isolate, Handle<Map> map,
499                                              MaybeObject new_transitions) {
500 #if DEBUG
501   if (GetEncoding(isolate, map) == kFullTransitionArray) {
502     CheckNewTransitionsAreConsistent(
503         isolate, map, new_transitions->GetHeapObjectAssumeStrong());
504     DCHECK_NE(GetTransitionArray(isolate, map),
505               new_transitions->GetHeapObjectAssumeStrong());
506   }
507 #endif
508   map->set_raw_transitions(new_transitions, kReleaseStore);
509   USE(isolate);
510 }
511 
512 // static
ReplaceTransitions(Isolate * isolate,Handle<Map> map,Handle<TransitionArray> new_transitions)513 void TransitionsAccessor::ReplaceTransitions(
514     Isolate* isolate, Handle<Map> map,
515     Handle<TransitionArray> new_transitions) {
516   ReplaceTransitions(isolate, map, MaybeObject::FromObject(*new_transitions));
517 }
518 
519 // static
SetPrototypeTransitions(Isolate * isolate,Handle<Map> map,Handle<WeakFixedArray> proto_transitions)520 void TransitionsAccessor::SetPrototypeTransitions(
521     Isolate* isolate, Handle<Map> map,
522     Handle<WeakFixedArray> proto_transitions) {
523   EnsureHasFullTransitionArray(isolate, map);
524   GetTransitionArray(isolate, map->raw_transitions(isolate, kAcquireLoad))
525       .SetPrototypeTransitions(*proto_transitions);
526 }
527 
528 // static
EnsureHasFullTransitionArray(Isolate * isolate,Handle<Map> map)529 void TransitionsAccessor::EnsureHasFullTransitionArray(Isolate* isolate,
530                                                        Handle<Map> map) {
531   Encoding encoding =
532       GetEncoding(isolate, map->raw_transitions(isolate, kAcquireLoad));
533   if (encoding == kFullTransitionArray) return;
534   int nof =
535       (encoding == kUninitialized || encoding == kMigrationTarget) ? 0 : 1;
536   Handle<TransitionArray> result = isolate->factory()->NewTransitionArray(nof);
537   // Reload encoding after possible GC.
538   encoding = GetEncoding(isolate, map->raw_transitions(isolate, kAcquireLoad));
539   if (nof == 1) {
540     if (encoding == kUninitialized) {
541       // If allocation caused GC and cleared the target, trim the new array.
542       result->SetNumberOfTransitions(0);
543     } else {
544       // Otherwise populate the new array.
545       Map target = GetSimpleTransition(isolate, map);
546       Name key = GetSimpleTransitionKey(target);
547       result->Set(0, key, HeapObjectReference::Weak(target));
548     }
549   }
550   ReplaceTransitions(isolate, map, result);
551 }
552 
TraverseTransitionTreeInternal(const TraverseCallback & callback,DisallowGarbageCollection * no_gc)553 void TransitionsAccessor::TraverseTransitionTreeInternal(
554     const TraverseCallback& callback, DisallowGarbageCollection* no_gc) {
555   // Mostly arbitrary but more than enough to run the test suite in static
556   // memory.
557   static constexpr int kStaticStackSize = 16;
558   base::SmallVector<Map, kStaticStackSize> stack;
559   stack.emplace_back(map_);
560 
561   // Pre-order iterative depth-first-search.
562   while (!stack.empty()) {
563     Map current_map = stack.back();
564     stack.pop_back();
565 
566     callback(current_map);
567 
568     MaybeObject raw_transitions =
569         current_map.raw_transitions(isolate_, kAcquireLoad);
570     Encoding encoding = GetEncoding(isolate_, raw_transitions);
571 
572     switch (encoding) {
573       case kPrototypeInfo:
574       case kUninitialized:
575       case kMigrationTarget:
576         break;
577       case kWeakRef: {
578         stack.emplace_back(
579             Map::cast(raw_transitions->GetHeapObjectAssumeWeak()));
580         break;
581       }
582       case kFullTransitionArray: {
583         TransitionArray transitions =
584             TransitionArray::cast(raw_transitions->GetHeapObjectAssumeStrong());
585         if (transitions.HasPrototypeTransitions()) {
586           WeakFixedArray proto_trans = transitions.GetPrototypeTransitions();
587           int length =
588               TransitionArray::NumberOfPrototypeTransitions(proto_trans);
589           for (int i = 0; i < length; ++i) {
590             int index = TransitionArray::kProtoTransitionHeaderSize + i;
591             MaybeObject target = proto_trans.Get(index);
592             HeapObject heap_object;
593             if (target->GetHeapObjectIfWeak(&heap_object)) {
594               stack.emplace_back(Map::cast(heap_object));
595             } else {
596               DCHECK(target->IsCleared());
597             }
598           }
599         }
600         for (int i = 0; i < transitions.number_of_transitions(); ++i) {
601           stack.emplace_back(transitions.GetTarget(i));
602         }
603         break;
604       }
605     }
606   }
607 }
608 
609 #ifdef DEBUG
610 // static
CheckNewTransitionsAreConsistent(Isolate * isolate,Handle<Map> map,Object transitions)611 void TransitionsAccessor::CheckNewTransitionsAreConsistent(Isolate* isolate,
612                                                            Handle<Map> map,
613                                                            Object transitions) {
614   // This function only handles full transition arrays.
615   TransitionArray old_transitions = GetTransitionArray(isolate, map);
616   DCHECK_EQ(kFullTransitionArray, GetEncoding(isolate, old_transitions));
617   TransitionArray new_transitions = TransitionArray::cast(transitions);
618   for (int i = 0; i < old_transitions.number_of_transitions(); i++) {
619     Map target = old_transitions.GetTarget(i);
620     if (target.instance_descriptors(isolate) ==
621         map->instance_descriptors(isolate)) {
622       Name key = old_transitions.GetKey(i);
623       int new_target_index;
624       if (IsSpecialTransition(ReadOnlyRoots(isolate), key)) {
625         new_target_index = new_transitions.SearchSpecial(Symbol::cast(key));
626       } else {
627         PropertyDetails details = GetTargetDetails(key, target);
628         new_target_index =
629             new_transitions.Search(details.kind(), key, details.attributes());
630       }
631       DCHECK_NE(TransitionArray::kNotFound, new_target_index);
632       DCHECK_EQ(target, new_transitions.GetTarget(new_target_index));
633     }
634   }
635 }
636 #endif
637 
638 // Private non-static helper functions (operating on full transition arrays).
639 
SearchDetails(int transition,PropertyKind kind,PropertyAttributes attributes,int * out_insertion_index)640 int TransitionArray::SearchDetails(int transition, PropertyKind kind,
641                                    PropertyAttributes attributes,
642                                    int* out_insertion_index) {
643   int nof_transitions = number_of_transitions();
644   DCHECK(transition < nof_transitions);
645   Name key = GetKey(transition);
646   for (; transition < nof_transitions && GetKey(transition) == key;
647        transition++) {
648     Map target = GetTarget(transition);
649     PropertyDetails target_details =
650         TransitionsAccessor::GetTargetDetails(key, target);
651 
652     int cmp = CompareDetails(kind, attributes, target_details.kind(),
653                              target_details.attributes());
654     if (cmp == 0) {
655       return transition;
656     } else if (cmp < 0) {
657       break;
658     }
659   }
660   if (out_insertion_index != nullptr) *out_insertion_index = transition;
661   return kNotFound;
662 }
663 
SearchDetailsAndGetTarget(int transition,PropertyKind kind,PropertyAttributes attributes)664 Map TransitionArray::SearchDetailsAndGetTarget(int transition,
665                                                PropertyKind kind,
666                                                PropertyAttributes attributes) {
667   int nof_transitions = number_of_transitions();
668   DCHECK(transition < nof_transitions);
669   Name key = GetKey(transition);
670   for (; transition < nof_transitions && GetKey(transition) == key;
671        transition++) {
672     Map target = GetTarget(transition);
673     PropertyDetails target_details =
674         TransitionsAccessor::GetTargetDetails(key, target);
675 
676     int cmp = CompareDetails(kind, attributes, target_details.kind(),
677                              target_details.attributes());
678     if (cmp == 0) {
679       return target;
680     } else if (cmp < 0) {
681       break;
682     }
683   }
684   return Map();
685 }
686 
Search(PropertyKind kind,Name name,PropertyAttributes attributes,int * out_insertion_index)687 int TransitionArray::Search(PropertyKind kind, Name name,
688                             PropertyAttributes attributes,
689                             int* out_insertion_index) {
690   int transition = SearchName(name, false, out_insertion_index);
691   if (transition == kNotFound) return kNotFound;
692   return SearchDetails(transition, kind, attributes, out_insertion_index);
693 }
694 
SearchAndGetTarget(PropertyKind kind,Name name,PropertyAttributes attributes)695 Map TransitionArray::SearchAndGetTarget(PropertyKind kind, Name name,
696                                         PropertyAttributes attributes) {
697   int transition = SearchName(name);
698   if (transition == kNotFound) {
699     return Map();
700   }
701   return SearchDetailsAndGetTarget(transition, kind, attributes);
702 }
703 
ForEachTransitionTo(Name name,const ForEachTransitionCallback & callback)704 void TransitionArray::ForEachTransitionTo(
705     Name name, const ForEachTransitionCallback& callback) {
706   int transition = SearchName(name);
707   if (transition == kNotFound) return;
708 
709   int nof_transitions = number_of_transitions();
710   DCHECK(transition < nof_transitions);
711   Name key = GetKey(transition);
712   for (; transition < nof_transitions && GetKey(transition) == key;
713        transition++) {
714     Map target = GetTarget(transition);
715     callback(target);
716   }
717 }
718 
Sort()719 void TransitionArray::Sort() {
720   DisallowGarbageCollection no_gc;
721   // In-place insertion sort.
722   int length = number_of_transitions();
723   ReadOnlyRoots roots = GetReadOnlyRoots();
724   for (int i = 1; i < length; i++) {
725     Name key = GetKey(i);
726     MaybeObject target = GetRawTarget(i);
727     PropertyKind kind = PropertyKind::kData;
728     PropertyAttributes attributes = NONE;
729     if (!TransitionsAccessor::IsSpecialTransition(roots, key)) {
730       Map target_map = TransitionsAccessor::GetTargetFromRaw(target);
731       PropertyDetails details =
732           TransitionsAccessor::GetTargetDetails(key, target_map);
733       kind = details.kind();
734       attributes = details.attributes();
735     }
736     int j;
737     for (j = i - 1; j >= 0; j--) {
738       Name temp_key = GetKey(j);
739       MaybeObject temp_target = GetRawTarget(j);
740       PropertyKind temp_kind = PropertyKind::kData;
741       PropertyAttributes temp_attributes = NONE;
742       if (!TransitionsAccessor::IsSpecialTransition(roots, temp_key)) {
743         Map temp_target_map =
744             TransitionsAccessor::GetTargetFromRaw(temp_target);
745         PropertyDetails details =
746             TransitionsAccessor::GetTargetDetails(temp_key, temp_target_map);
747         temp_kind = details.kind();
748         temp_attributes = details.attributes();
749       }
750       int cmp = CompareKeys(temp_key, temp_key.hash(), temp_kind,
751                             temp_attributes, key, key.hash(), kind, attributes);
752       if (cmp > 0) {
753         SetKey(j + 1, temp_key);
754         SetRawTarget(j + 1, temp_target);
755       } else {
756         break;
757       }
758     }
759     SetKey(j + 1, key);
760     SetRawTarget(j + 1, target);
761   }
762   DCHECK(IsSortedNoDuplicates());
763 }
764 
HasIntegrityLevelTransitionTo(Map to,Symbol * out_symbol,PropertyAttributes * out_integrity_level)765 bool TransitionsAccessor::HasIntegrityLevelTransitionTo(
766     Map to, Symbol* out_symbol, PropertyAttributes* out_integrity_level) {
767   ReadOnlyRoots roots(isolate_);
768   if (SearchSpecial(roots.frozen_symbol()) == to) {
769     if (out_integrity_level) *out_integrity_level = FROZEN;
770     if (out_symbol) *out_symbol = roots.frozen_symbol();
771   } else if (SearchSpecial(roots.sealed_symbol()) == to) {
772     if (out_integrity_level) *out_integrity_level = SEALED;
773     if (out_symbol) *out_symbol = roots.sealed_symbol();
774   } else if (SearchSpecial(roots.nonextensible_symbol()) == to) {
775     if (out_integrity_level) *out_integrity_level = NONE;
776     if (out_symbol) *out_symbol = roots.nonextensible_symbol();
777   } else {
778     return false;
779   }
780   return true;
781 }
782 
783 }  // namespace internal
784 }  // namespace v8
785