Line data Source code
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 100392838 : void TransitionsAccessor::Initialize() {
15 100392838 : raw_transitions_ = map_->raw_transitions();
16 100392838 : HeapObject heap_object;
17 162492509 : if (raw_transitions_->IsSmi() || raw_transitions_->IsCleared()) {
18 38304779 : encoding_ = kUninitialized;
19 62088059 : } else if (raw_transitions_->IsWeak()) {
20 29494540 : encoding_ = kWeakRef;
21 32593519 : } else if (raw_transitions_->GetHeapObjectIfStrong(&heap_object)) {
22 32593525 : if (heap_object->IsTransitionArray()) {
23 32314036 : encoding_ = kFullTransitionArray;
24 279489 : } else if (heap_object->IsPrototypeInfo()) {
25 279489 : encoding_ = kPrototypeInfo;
26 : } else {
27 : DCHECK(map_->is_deprecated());
28 : DCHECK(heap_object->IsMap());
29 0 : encoding_ = kMigrationTarget;
30 : }
31 : } else {
32 0 : UNREACHABLE();
33 : }
34 : #if DEBUG
35 : needs_reload_ = false;
36 : #endif
37 100392844 : }
38 :
39 528276 : Map TransitionsAccessor::GetSimpleTransition() {
40 528276 : switch (encoding()) {
41 : case kWeakRef:
42 128788 : return Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
43 : default:
44 399488 : return Map();
45 : }
46 : }
47 :
48 74924 : bool TransitionsAccessor::HasSimpleTransitionTo(Map map) {
49 74924 : switch (encoding()) {
50 : case kWeakRef:
51 14630 : return raw_transitions_->GetHeapObjectAssumeWeak() == map;
52 : case kPrototypeInfo:
53 : case kUninitialized:
54 : case kMigrationTarget:
55 : case kFullTransitionArray:
56 : return false;
57 : }
58 0 : UNREACHABLE();
59 : }
60 :
61 7258351 : void TransitionsAccessor::Insert(Handle<Name> name, Handle<Map> target,
62 7258357 : SimpleTransitionFlag flag) {
63 : DCHECK(!map_handle_.is_null());
64 7258351 : target->SetBackPointer(map_);
65 :
66 : // If the map doesn't have any transitions at all yet, install the new one.
67 7258357 : if (encoding() == kUninitialized || encoding() == kMigrationTarget) {
68 7017400 : if (flag == SIMPLE_PROPERTY_TRANSITION) {
69 6795179 : ReplaceTransitions(HeapObjectReference::Weak(*target));
70 6795180 : return;
71 : }
72 : // If the flag requires a full TransitionArray, allocate one.
73 : Handle<TransitionArray> result =
74 222221 : isolate_->factory()->NewTransitionArray(0, 1);
75 222220 : ReplaceTransitions(MaybeObject::FromObject(*result));
76 222221 : Reload();
77 : }
78 :
79 463178 : bool is_special_transition = flag == SPECIAL_TRANSITION;
80 : // If the map has a simple transition, check if it should be overwritten.
81 463178 : Map simple_transition = GetSimpleTransition();
82 463176 : if (!simple_transition.is_null()) {
83 63687 : Name key = GetSimpleTransitionKey(simple_transition);
84 : PropertyDetails old_details = GetSimpleTargetDetails(simple_transition);
85 : PropertyDetails new_details = is_special_transition
86 : ? PropertyDetails::Empty()
87 126564 : : GetTargetDetails(*name, *target);
88 138064 : if (flag == SIMPLE_PROPERTY_TRANSITION && key->Equals(*name) &&
89 70985 : old_details.kind() == new_details.kind() &&
90 : old_details.attributes() == new_details.attributes()) {
91 4823 : ReplaceTransitions(HeapObjectReference::Weak(*target));
92 4823 : return;
93 : }
94 : // Otherwise allocate a full TransitionArray with slack for a new entry.
95 58864 : Handle<Map> map(simple_transition, isolate_);
96 : Handle<TransitionArray> result =
97 58864 : isolate_->factory()->NewTransitionArray(1, 1);
98 : // Reload state; allocations might have caused it to be cleared.
99 58864 : Reload();
100 58864 : simple_transition = GetSimpleTransition();
101 58864 : if (!simple_transition.is_null()) {
102 : DCHECK_EQ(*map, simple_transition);
103 58864 : if (encoding_ == kWeakRef) {
104 : result->Set(0, GetSimpleTransitionKey(simple_transition),
105 117728 : HeapObjectReference::Weak(simple_transition));
106 : } else {
107 0 : UNREACHABLE();
108 : }
109 : } else {
110 0 : result->SetNumberOfTransitions(0);
111 : }
112 58864 : ReplaceTransitions(MaybeObject::FromObject(*result));
113 58864 : 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 458353 : 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 692462 : : GetTargetDetails(*name, *target);
127 :
128 : {
129 : DisallowHeapAllocation no_gc;
130 458353 : TransitionArray array = transitions();
131 458351 : 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 692455 : &insertion_index);
139 : // If an existing entry was found, overwrite it and return.
140 458350 : if (index != kNotFound) {
141 : array->SetRawTarget(index, HeapObjectReference::Weak(*target));
142 5650 : return;
143 : }
144 :
145 452700 : ++new_nof;
146 452700 : 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 452700 : if (new_nof <= array->Capacity()) {
151 : array->SetNumberOfTransitions(new_nof);
152 12003933 : for (index = number_of_transitions; index > insertion_index; --index) {
153 11240952 : 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 381492 : return;
160 : }
161 : }
162 :
163 : // We're gonna need a bigger TransitionArray.
164 : Handle<TransitionArray> result = isolate_->factory()->NewTransitionArray(
165 : new_nof,
166 71208 : 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 71211 : Reload();
172 : DisallowHeapAllocation no_gc;
173 71210 : TransitionArray array = transitions();
174 71210 : if (array->number_of_transitions() != number_of_transitions) {
175 : DCHECK(array->number_of_transitions() < number_of_transitions);
176 :
177 0 : number_of_transitions = array->number_of_transitions();
178 : new_nof = number_of_transitions;
179 :
180 0 : 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 0 : &insertion_index);
186 0 : if (index == kNotFound) {
187 0 : ++new_nof;
188 : } else {
189 0 : insertion_index = index;
190 : }
191 : DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
192 :
193 0 : result->SetNumberOfTransitions(new_nof);
194 : }
195 :
196 71209 : if (array->HasPrototypeTransitions()) {
197 4584 : result->SetPrototypeTransitions(array->GetPrototypeTransitions());
198 : }
199 :
200 : DCHECK_NE(kNotFound, insertion_index);
201 251127 : for (int i = 0; i < insertion_index; ++i) {
202 359830 : result->Set(i, array->GetKey(i), array->GetRawTarget(i));
203 : }
204 213636 : result->Set(insertion_index, *name, HeapObjectReference::Weak(*target));
205 434022 : for (int i = insertion_index; i < number_of_transitions; ++i) {
206 583196 : result->Set(i + 1, array->GetKey(i), array->GetRawTarget(i));
207 : }
208 :
209 : SLOW_DCHECK(result->IsSortedNoDuplicates());
210 71212 : ReplaceTransitions(MaybeObject::FromObject(*result));
211 : }
212 :
213 34038633 : Map TransitionsAccessor::SearchTransition(Name name, PropertyKind kind,
214 34038633 : PropertyAttributes attributes) {
215 : DCHECK(name->IsUniqueName());
216 34038633 : switch (encoding()) {
217 : case kPrototypeInfo:
218 : case kUninitialized:
219 : case kMigrationTarget:
220 16283314 : return Map();
221 : case kWeakRef: {
222 5717748 : Map map = Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
223 5717749 : if (!IsMatchingMap(map, name, kind, attributes)) return Map();
224 5643324 : return map;
225 : }
226 : case kFullTransitionArray: {
227 12037571 : return transitions()->SearchAndGetTarget(kind, name, attributes);
228 : }
229 : }
230 0 : UNREACHABLE();
231 : }
232 :
233 8374917 : Map TransitionsAccessor::SearchSpecial(Symbol name) {
234 8374917 : if (encoding() != kFullTransitionArray) return Map();
235 15747084 : int transition = transitions()->SearchSpecial(name);
236 7873541 : if (transition == kNotFound) return Map();
237 7870901 : return transitions()->GetTarget(transition);
238 : }
239 :
240 : // static
241 10 : bool TransitionsAccessor::IsSpecialTransition(ReadOnlyRoots roots, Name name) {
242 10 : if (!name->IsSymbol()) return false;
243 0 : return name == roots.nonextensible_symbol() ||
244 0 : name == roots.sealed_symbol() || name == roots.frozen_symbol() ||
245 0 : name == roots.elements_transition_symbol() ||
246 : name == roots.strict_function_transition_symbol();
247 : }
248 :
249 11575279 : MaybeHandle<Map> TransitionsAccessor::FindTransitionToDataProperty(
250 : Handle<Name> name, RequestedLocation requested_location) {
251 : DCHECK(name->IsUniqueName());
252 : DisallowHeapAllocation no_gc;
253 11575279 : PropertyAttributes attributes = name->IsPrivate() ? DONT_ENUM : NONE;
254 11575279 : Map target = SearchTransition(*name, kData, attributes);
255 11575279 : if (target.is_null()) return MaybeHandle<Map>();
256 11461011 : PropertyDetails details = target->GetLastDescriptorDetails();
257 : DCHECK_EQ(attributes, details.attributes());
258 : DCHECK_EQ(kData, details.kind());
259 22922022 : if (requested_location == kFieldOnly && details.location() != kField) {
260 0 : return MaybeHandle<Map>();
261 : }
262 22922022 : return Handle<Map>(target, isolate_);
263 : }
264 :
265 33297178 : Handle<String> TransitionsAccessor::ExpectedTransitionKey() {
266 : DisallowHeapAllocation no_gc;
267 33297178 : switch (encoding()) {
268 : case kPrototypeInfo:
269 : case kUninitialized:
270 : case kMigrationTarget:
271 : case kFullTransitionArray:
272 : return Handle<String>::null();
273 : case kWeakRef: {
274 21837143 : Map target = Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
275 : PropertyDetails details = GetSimpleTargetDetails(target);
276 21837143 : if (details.location() != kField) return Handle<String>::null();
277 : DCHECK_EQ(kData, details.kind());
278 21837143 : if (details.attributes() != NONE) return Handle<String>::null();
279 21832453 : Name name = GetSimpleTransitionKey(target);
280 21832453 : if (!name->IsString()) return Handle<String>::null();
281 21832453 : return handle(String::cast(name), isolate_);
282 : }
283 : }
284 0 : UNREACHABLE();
285 : }
286 :
287 21822112 : Handle<Map> TransitionsAccessor::ExpectedTransitionTarget() {
288 : DCHECK(!ExpectedTransitionKey().is_null());
289 43644224 : return handle(GetTarget(0), isolate_);
290 : }
291 :
292 28038822 : bool TransitionsAccessor::CanHaveMoreTransitions() {
293 14060321 : if (map_->is_dictionary_map()) return false;
294 13978501 : if (encoding() == kFullTransitionArray) {
295 182434 : return transitions()->number_of_transitions() < kMaxNumberOfTransitions;
296 : }
297 : return true;
298 : }
299 :
300 : // static
301 5717748 : bool TransitionsAccessor::IsMatchingMap(Map target, Name name,
302 : PropertyKind kind,
303 : PropertyAttributes attributes) {
304 5717748 : int descriptor = target->LastAdded();
305 5717751 : DescriptorArray descriptors = target->instance_descriptors();
306 5717750 : Name key = descriptors->GetKey(descriptor);
307 5717750 : if (key != name) return false;
308 : return descriptors->GetDetails(descriptor)
309 5650964 : .HasKindAndAttributes(kind, attributes);
310 : }
311 :
312 : // static
313 134566 : bool TransitionArray::CompactPrototypeTransitionArray(Isolate* isolate,
314 : WeakFixedArray array) {
315 : const int header = kProtoTransitionHeaderSize;
316 134566 : int number_of_transitions = NumberOfPrototypeTransitions(array);
317 134566 : if (number_of_transitions == 0) {
318 : // Empty array cannot be compacted.
319 : return false;
320 : }
321 : int new_number_of_transitions = 0;
322 17558 : for (int i = 0; i < number_of_transitions; i++) {
323 15836 : MaybeObject target = array->Get(header + i);
324 : DCHECK(target->IsCleared() ||
325 : (target->IsWeak() && target->GetHeapObject()->IsMap()));
326 15836 : if (!target->IsCleared()) {
327 15083 : if (new_number_of_transitions != i) {
328 321 : array->Set(header + new_number_of_transitions, target);
329 : }
330 15083 : new_number_of_transitions++;
331 : }
332 : }
333 : // Fill slots that became free with undefined value.
334 : MaybeObject undefined =
335 1722 : MaybeObject::FromObject(*isolate->factory()->undefined_value());
336 4197 : for (int i = new_number_of_transitions; i < number_of_transitions; i++) {
337 753 : array->Set(header + i, undefined);
338 : }
339 1722 : if (number_of_transitions != new_number_of_transitions) {
340 : SetNumberOfPrototypeTransitions(array, new_number_of_transitions);
341 : }
342 1722 : return new_number_of_transitions < number_of_transitions;
343 : }
344 :
345 : // static
346 134531 : Handle<WeakFixedArray> TransitionArray::GrowPrototypeTransitionArray(
347 : Handle<WeakFixedArray> array, int new_capacity, Isolate* isolate) {
348 : // Grow array by factor 2 up to MaxCachedPrototypeTransitions.
349 134531 : int capacity = array->length() - kProtoTransitionHeaderSize;
350 : new_capacity = Min(kMaxCachedPrototypeTransitions, new_capacity);
351 : DCHECK_GT(new_capacity, capacity);
352 134531 : int grow_by = new_capacity - capacity;
353 : array =
354 134531 : isolate->factory()->CopyWeakFixedArrayAndGrow(array, grow_by, TENURED);
355 134531 : if (capacity < 0) {
356 : // There was no prototype transitions array before, so the size
357 : // couldn't be copied. Initialize it explicitly.
358 : SetNumberOfPrototypeTransitions(*array, 0);
359 : }
360 134531 : return array;
361 : }
362 :
363 169268 : void TransitionsAccessor::PutPrototypeTransition(Handle<Object> prototype,
364 : Handle<Map> target_map) {
365 : DCHECK(HeapObject::cast(*prototype)->map()->IsMap());
366 : // Don't cache prototype transition if this map is either shared, or a map of
367 : // a prototype.
368 169268 : if (map_->is_prototype_map()) return;
369 155499 : if (map_->is_dictionary_map() || !FLAG_cache_prototype_transitions) return;
370 :
371 : const int header = TransitionArray::kProtoTransitionHeaderSize;
372 :
373 148570 : Handle<WeakFixedArray> cache(GetPrototypeTransitions(), isolate_);
374 148570 : int capacity = cache->length() - header;
375 148570 : int transitions = TransitionArray::NumberOfPrototypeTransitions(*cache) + 1;
376 :
377 148570 : if (transitions > capacity) {
378 : // Grow the array if compacting it doesn't free space.
379 134566 : if (!TransitionArray::CompactPrototypeTransitionArray(isolate_, *cache)) {
380 134531 : if (capacity == TransitionArray::kMaxCachedPrototypeTransitions) return;
381 : cache = TransitionArray::GrowPrototypeTransitionArray(
382 134531 : cache, 2 * transitions, isolate_);
383 134531 : Reload();
384 134531 : SetPrototypeTransitions(cache);
385 : }
386 : }
387 :
388 : // Reload number of transitions as they might have been compacted.
389 148570 : int last = TransitionArray::NumberOfPrototypeTransitions(*cache);
390 148570 : int entry = header + last;
391 :
392 297140 : cache->Set(entry, HeapObjectReference::Weak(*target_map));
393 : TransitionArray::SetNumberOfPrototypeTransitions(*cache, last + 1);
394 : }
395 :
396 185475 : Handle<Map> TransitionsAccessor::GetPrototypeTransition(
397 : Handle<Object> prototype) {
398 : DisallowHeapAllocation no_gc;
399 185475 : WeakFixedArray cache = GetPrototypeTransitions();
400 185475 : int length = TransitionArray::NumberOfPrototypeTransitions(cache);
401 737743 : for (int i = 0; i < length; i++) {
402 : MaybeObject target =
403 383000 : cache->Get(TransitionArray::kProtoTransitionHeaderSize + i);
404 : DCHECK(target->IsWeakOrCleared());
405 383000 : HeapObject heap_object;
406 383000 : if (target->GetHeapObjectIfWeak(&heap_object)) {
407 : Map map = Map::cast(heap_object);
408 363604 : if (map->prototype() == *prototype) {
409 16207 : return handle(map, isolate_);
410 : }
411 : }
412 : }
413 169268 : return Handle<Map>();
414 : }
415 :
416 334045 : WeakFixedArray TransitionsAccessor::GetPrototypeTransitions() {
417 1002135 : if (encoding() != kFullTransitionArray ||
418 433671 : !transitions()->HasPrototypeTransitions()) {
419 286386 : return ReadOnlyRoots(isolate_).empty_weak_fixed_array();
420 : }
421 47659 : return transitions()->GetPrototypeTransitions();
422 : }
423 :
424 : // static
425 0 : void TransitionArray::SetNumberOfPrototypeTransitions(
426 : WeakFixedArray proto_transitions, int value) {
427 : DCHECK_NE(proto_transitions->length(), 0);
428 : proto_transitions->Set(kProtoTransitionNumberOfEntriesOffset,
429 281449 : MaybeObject::FromSmi(Smi::FromInt(value)));
430 0 : }
431 :
432 1529075 : int TransitionsAccessor::NumberOfTransitions() {
433 1529075 : switch (encoding()) {
434 : case kPrototypeInfo:
435 : case kUninitialized:
436 : case kMigrationTarget:
437 : return 0;
438 : case kWeakRef:
439 1252361 : return 1;
440 : case kFullTransitionArray:
441 1092 : return transitions()->number_of_transitions();
442 : }
443 0 : UNREACHABLE();
444 : return 0; // Make GCC happy.
445 : }
446 :
447 0 : void TransitionsAccessor::SetMigrationTarget(Map migration_target) {
448 : // We only cache the migration target for maps with empty transitions for GC's
449 : // sake.
450 0 : if (encoding() != kUninitialized) return;
451 : DCHECK(map_->is_deprecated());
452 0 : map_->set_raw_transitions(MaybeObject::FromObject(migration_target));
453 : MarkNeedsReload();
454 : }
455 :
456 755 : Map TransitionsAccessor::GetMigrationTarget() {
457 755 : if (encoding() == kMigrationTarget) {
458 0 : return map_->raw_transitions()->cast<Map>();
459 : }
460 755 : return Map();
461 : }
462 :
463 71208 : void TransitionArray::Zap(Isolate* isolate) {
464 : MemsetTagged(ObjectSlot(RawFieldOfElementAt(kPrototypeTransitionsIndex)),
465 : ReadOnlyRoots(isolate).the_hole_value(),
466 71209 : length() - kPrototypeTransitionsIndex);
467 : SetNumberOfTransitions(0);
468 71208 : }
469 :
470 7284059 : void TransitionsAccessor::ReplaceTransitions(MaybeObject new_transitions) {
471 7284059 : if (encoding() == kFullTransitionArray) {
472 71209 : TransitionArray old_transitions = transitions();
473 : #if DEBUG
474 : CheckNewTransitionsAreConsistent(
475 : old_transitions, new_transitions->GetHeapObjectAssumeStrong());
476 : DCHECK(old_transitions != new_transitions->GetHeapObjectAssumeStrong());
477 : #endif
478 : // Transition arrays are not shared. When one is replaced, it should not
479 : // keep referenced objects alive, so we zap it.
480 : // When there is another reference to the array somewhere (e.g. a handle),
481 : // not zapping turns from a waste of memory into a source of crashes.
482 71210 : old_transitions->Zap(isolate_);
483 : }
484 7284058 : map_->set_raw_transitions(new_transitions);
485 : MarkNeedsReload();
486 7284062 : }
487 :
488 134531 : void TransitionsAccessor::SetPrototypeTransitions(
489 : Handle<WeakFixedArray> proto_transitions) {
490 134531 : EnsureHasFullTransitionArray();
491 269062 : transitions()->SetPrototypeTransitions(*proto_transitions);
492 134531 : }
493 :
494 140768 : void TransitionsAccessor::EnsureHasFullTransitionArray() {
495 269062 : if (encoding() == kFullTransitionArray) return;
496 : int nof =
497 131767 : (encoding() == kUninitialized || encoding() == kMigrationTarget) ? 0 : 1;
498 131767 : Handle<TransitionArray> result = isolate_->factory()->NewTransitionArray(nof);
499 131767 : Reload(); // Reload after possible GC.
500 131767 : if (nof == 1) {
501 6237 : if (encoding() == kUninitialized) {
502 : // If allocation caused GC and cleared the target, trim the new array.
503 0 : result->SetNumberOfTransitions(0);
504 : } else {
505 : // Otherwise populate the new array.
506 6237 : Handle<Map> target(GetSimpleTransition(), isolate_);
507 6237 : Name key = GetSimpleTransitionKey(*target);
508 12474 : result->Set(0, key, HeapObjectReference::Weak(*target));
509 : }
510 : }
511 131767 : ReplaceTransitions(MaybeObject::FromObject(*result));
512 131767 : Reload(); // Reload after replacing transitions.
513 : }
514 :
515 733089 : void TransitionsAccessor::TraverseTransitionTreeInternal(
516 733089 : TraverseCallback callback, void* data, DisallowHeapAllocation* no_gc) {
517 733089 : switch (encoding()) {
518 : case kPrototypeInfo:
519 : case kUninitialized:
520 : case kMigrationTarget:
521 : break;
522 : case kWeakRef: {
523 : Map simple_target =
524 464147 : Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
525 : TransitionsAccessor(isolate_, simple_target, no_gc)
526 928296 : .TraverseTransitionTreeInternal(callback, data, no_gc);
527 : break;
528 : }
529 : case kFullTransitionArray: {
530 11886 : if (transitions()->HasPrototypeTransitions()) {
531 54 : WeakFixedArray proto_trans = transitions()->GetPrototypeTransitions();
532 54 : int length = TransitionArray::NumberOfPrototypeTransitions(proto_trans);
533 270 : for (int i = 0; i < length; ++i) {
534 162 : int index = TransitionArray::kProtoTransitionHeaderSize + i;
535 162 : MaybeObject target = proto_trans->Get(index);
536 162 : HeapObject heap_object;
537 162 : if (target->GetHeapObjectIfWeak(&heap_object)) {
538 : TransitionsAccessor(isolate_, Map::cast(heap_object), no_gc)
539 324 : .TraverseTransitionTreeInternal(callback, data, no_gc);
540 : } else {
541 : DCHECK(target->IsCleared());
542 : }
543 : }
544 : }
545 6449 : for (int i = 0; i < transitions()->number_of_transitions(); ++i) {
546 : TransitionsAccessor(isolate_, transitions()->GetTarget(i), no_gc)
547 12898 : .TraverseTransitionTreeInternal(callback, data, no_gc);
548 : }
549 : break;
550 : }
551 : }
552 733086 : callback(map_, data);
553 733083 : }
554 :
555 : #ifdef DEBUG
556 : void TransitionsAccessor::CheckNewTransitionsAreConsistent(
557 : TransitionArray old_transitions, Object transitions) {
558 : // This function only handles full transition arrays.
559 : DCHECK_EQ(kFullTransitionArray, encoding());
560 : TransitionArray new_transitions = TransitionArray::cast(transitions);
561 : for (int i = 0; i < old_transitions->number_of_transitions(); i++) {
562 : Map target = old_transitions->GetTarget(i);
563 : if (target->instance_descriptors() == map_->instance_descriptors()) {
564 : Name key = old_transitions->GetKey(i);
565 : int new_target_index;
566 : if (IsSpecialTransition(ReadOnlyRoots(isolate_), key)) {
567 : new_target_index = new_transitions->SearchSpecial(Symbol::cast(key));
568 : } else {
569 : PropertyDetails details = GetTargetDetails(key, target);
570 : new_target_index =
571 : new_transitions->Search(details.kind(), key, details.attributes());
572 : }
573 : DCHECK_NE(TransitionArray::kNotFound, new_target_index);
574 : DCHECK_EQ(target, new_transitions->GetTarget(new_target_index));
575 : }
576 : }
577 : }
578 : #endif
579 :
580 : // Private non-static helper functions (operating on full transition arrays).
581 :
582 17198 : int TransitionArray::SearchDetails(int transition, PropertyKind kind,
583 : PropertyAttributes attributes,
584 : int* out_insertion_index) {
585 17198 : int nof_transitions = number_of_transitions();
586 : DCHECK(transition < nof_transitions);
587 17198 : Name key = GetKey(transition);
588 54632 : for (; transition < nof_transitions && GetKey(transition) == key;
589 : transition++) {
590 28332 : Map target = GetTarget(transition);
591 : PropertyDetails target_details =
592 28332 : TransitionsAccessor::GetTargetDetails(key, target);
593 :
594 : int cmp = CompareDetails(kind, attributes, target_details.kind(),
595 : target_details.attributes());
596 28332 : if (cmp == 0) {
597 5650 : return transition;
598 22682 : } else if (cmp < 0) {
599 : break;
600 : }
601 : }
602 11548 : if (out_insertion_index != nullptr) *out_insertion_index = transition;
603 : return kNotFound;
604 : }
605 :
606 11789593 : Map TransitionArray::SearchDetailsAndGetTarget(int transition,
607 : PropertyKind kind,
608 : PropertyAttributes attributes) {
609 11789593 : int nof_transitions = number_of_transitions();
610 : DCHECK(transition < nof_transitions);
611 11789594 : Name key = GetKey(transition);
612 11819708 : for (; transition < nof_transitions && GetKey(transition) == key;
613 : transition++) {
614 11803427 : Map target = GetTarget(transition);
615 : PropertyDetails target_details =
616 11803427 : TransitionsAccessor::GetTargetDetails(key, target);
617 :
618 : int cmp = CompareDetails(kind, attributes, target_details.kind(),
619 : target_details.attributes());
620 11803427 : if (cmp == 0) {
621 11787581 : return target;
622 15846 : } else if (cmp < 0) {
623 : break;
624 : }
625 : }
626 2014 : return Map();
627 : }
628 :
629 234102 : int TransitionArray::Search(PropertyKind kind, Name name,
630 : PropertyAttributes attributes,
631 : int* out_insertion_index) {
632 234102 : int transition = SearchName(name, out_insertion_index);
633 234106 : if (transition == kNotFound) return kNotFound;
634 17198 : return SearchDetails(transition, kind, attributes, out_insertion_index);
635 : }
636 :
637 12037567 : Map TransitionArray::SearchAndGetTarget(PropertyKind kind, Name name,
638 : PropertyAttributes attributes) {
639 12037567 : int transition = SearchName(name, nullptr);
640 12037574 : if (transition == kNotFound) {
641 247979 : return Map();
642 : }
643 11789595 : return SearchDetailsAndGetTarget(transition, kind, attributes);
644 : }
645 :
646 5 : void TransitionArray::Sort() {
647 : DisallowHeapAllocation no_gc;
648 : // In-place insertion sort.
649 5 : int length = number_of_transitions();
650 5 : ReadOnlyRoots roots = GetReadOnlyRoots();
651 15 : for (int i = 1; i < length; i++) {
652 5 : Name key = GetKey(i);
653 : MaybeObject target = GetRawTarget(i);
654 : PropertyKind kind = kData;
655 : PropertyAttributes attributes = NONE;
656 5 : if (!TransitionsAccessor::IsSpecialTransition(roots, key)) {
657 5 : Map target_map = TransitionsAccessor::GetTargetFromRaw(target);
658 : PropertyDetails details =
659 5 : TransitionsAccessor::GetTargetDetails(key, target_map);
660 : kind = details.kind();
661 : attributes = details.attributes();
662 : }
663 : int j;
664 10 : for (j = i - 1; j >= 0; j--) {
665 5 : Name temp_key = GetKey(j);
666 : MaybeObject temp_target = GetRawTarget(j);
667 : PropertyKind temp_kind = kData;
668 : PropertyAttributes temp_attributes = NONE;
669 5 : if (!TransitionsAccessor::IsSpecialTransition(roots, temp_key)) {
670 : Map temp_target_map =
671 5 : TransitionsAccessor::GetTargetFromRaw(temp_target);
672 : PropertyDetails details =
673 5 : TransitionsAccessor::GetTargetDetails(temp_key, temp_target_map);
674 : temp_kind = details.kind();
675 : temp_attributes = details.attributes();
676 : }
677 : int cmp =
678 : CompareKeys(temp_key, temp_key->Hash(), temp_kind, temp_attributes,
679 5 : key, key->Hash(), kind, attributes);
680 5 : if (cmp > 0) {
681 : SetKey(j + 1, temp_key);
682 : SetRawTarget(j + 1, temp_target);
683 : } else {
684 : break;
685 : }
686 : }
687 : SetKey(j + 1, key);
688 : SetRawTarget(j + 1, target);
689 : }
690 : DCHECK(IsSortedNoDuplicates());
691 5 : }
692 :
693 : } // namespace internal
694 178779 : } // namespace v8
|
