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 103286301 : void TransitionsAccessor::Initialize() {
15 103286301 : raw_transitions_ = map_->raw_transitions();
16 103286301 : HeapObject heap_object;
17 166967056 : if (raw_transitions_->IsSmi() || raw_transitions_->IsCleared()) {
18 39619851 : encoding_ = kUninitialized;
19 63666450 : } else if (raw_transitions_->IsWeak()) {
20 29510322 : encoding_ = kWeakRef;
21 34156128 : } else if (raw_transitions_->GetHeapObjectIfStrong(&heap_object)) {
22 34156128 : if (heap_object->IsTransitionArray()) {
23 32594413 : encoding_ = kFullTransitionArray;
24 1561717 : } else if (heap_object->IsPrototypeInfo()) {
25 1561717 : 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 103286303 : }
38 :
39 : Map TransitionsAccessor::GetSimpleTransition() {
40 521920 : switch (encoding()) {
41 : case kWeakRef:
42 : return Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
43 : default:
44 : return Map();
45 : }
46 : }
47 :
48 77672 : bool TransitionsAccessor::HasSimpleTransitionTo(Map map) {
49 77672 : 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 0 : UNREACHABLE();
59 : }
60 :
61 7343290 : 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 7343291 : if (encoding() == kUninitialized || encoding() == kMigrationTarget) {
68 7108667 : if (flag == SIMPLE_PROPERTY_TRANSITION) {
69 6887320 : ReplaceTransitions(HeapObjectReference::Weak(*target));
70 6887325 : return;
71 : }
72 : // If the flag requires a full TransitionArray, allocate one.
73 : Handle<TransitionArray> result =
74 221347 : isolate_->factory()->NewTransitionArray(0, 1);
75 221346 : 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 455970 : if (!simple_transition.is_null()) {
83 62052 : Name key = GetSimpleTransitionKey(simple_transition);
84 : PropertyDetails old_details = GetSimpleTargetDetails(simple_transition);
85 : PropertyDetails new_details = is_special_transition
86 : ? PropertyDetails::Empty()
87 123269 : : GetTargetDetails(*name, *target);
88 132147 : if (flag == SIMPLE_PROPERTY_TRANSITION && key->Equals(*name) &&
89 66861 : old_details.kind() == new_details.kind() &&
90 : old_details.attributes() == new_details.attributes()) {
91 2360 : ReplaceTransitions(HeapObjectReference::Weak(*target));
92 2360 : return;
93 : }
94 : // Otherwise allocate a full TransitionArray with slack for a new entry.
95 59693 : Handle<Map> map(simple_transition, isolate_);
96 : Handle<TransitionArray> result =
97 59693 : isolate_->factory()->NewTransitionArray(1, 1);
98 : // Reload state; allocations might have caused it to be cleared.
99 : Reload();
100 : simple_transition = GetSimpleTransition();
101 59693 : if (!simple_transition.is_null()) {
102 : DCHECK_EQ(*map, simple_transition);
103 59693 : if (encoding_ == kWeakRef) {
104 179079 : result->Set(0, GetSimpleTransitionKey(simple_transition),
105 : HeapObjectReference::Weak(simple_transition));
106 : } else {
107 0 : UNREACHABLE();
108 : }
109 : } else {
110 0 : result->SetNumberOfTransitions(0);
111 : }
112 59693 : 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 453611 : 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 683185 : : GetTargetDetails(*name, *target);
127 :
128 : {
129 : DisallowHeapAllocation no_gc;
130 453613 : TransitionArray array = transitions();
131 453613 : 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 907218 : &insertion_index);
139 : // If an existing entry was found, overwrite it and return.
140 453607 : if (index != kNotFound) {
141 : array->SetRawTarget(index, HeapObjectReference::Weak(*target));
142 603 : return;
143 : }
144 :
145 453004 : ++new_nof;
146 453004 : 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 453004 : if (new_nof <= array->Capacity()) {
151 : array->SetNumberOfTransitions(new_nof);
152 21907826 : for (index = number_of_transitions; index > insertion_index; --index) {
153 10763612 : array->SetKey(index, array->GetKey(index - 1));
154 10763612 : 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 380603 : return;
160 : }
161 : }
162 :
163 : // We're gonna need a bigger TransitionArray.
164 72402 : Handle<TransitionArray> result = isolate_->factory()->NewTransitionArray(
165 : new_nof,
166 144804 : 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 72407 : TransitionArray array = transitions();
174 72407 : 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 72406 : if (array->HasPrototypeTransitions()) {
197 3346 : result->SetPrototypeTransitions(array->GetPrototypeTransitions());
198 : }
199 :
200 : DCHECK_NE(kNotFound, insertion_index);
201 538404 : for (int i = 0; i < insertion_index; ++i) {
202 466007 : result->Set(i, array->GetKey(i), array->GetRawTarget(i));
203 : }
204 144802 : result->Set(insertion_index, *name, HeapObjectReference::Weak(*target));
205 306493 : for (int i = insertion_index; i < number_of_transitions; ++i) {
206 468188 : result->Set(i + 1, array->GetKey(i), array->GetRawTarget(i));
207 : }
208 :
209 : SLOW_DCHECK(result->IsSortedNoDuplicates());
210 72399 : ReplaceTransitions(MaybeObject::FromObject(*result));
211 : }
212 :
213 36052036 : Map TransitionsAccessor::SearchTransition(Name name, PropertyKind kind,
214 : PropertyAttributes attributes) {
215 : DCHECK(name->IsUniqueName());
216 36052036 : switch (encoding()) {
217 : case kPrototypeInfo:
218 : case kUninitialized:
219 : case kMigrationTarget:
220 18197603 : return Map();
221 : case kWeakRef: {
222 : Map map = Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
223 5756595 : if (!IsMatchingMap(map, name, kind, attributes)) return Map();
224 5681170 : return map;
225 : }
226 : case kFullTransitionArray: {
227 12097838 : return transitions()->SearchAndGetTarget(kind, name, attributes);
228 : }
229 : }
230 0 : UNREACHABLE();
231 : }
232 :
233 8520444 : Map TransitionsAccessor::SearchSpecial(Symbol name) {
234 8520444 : if (encoding() != kFullTransitionArray) return Map();
235 8016000 : int transition = transitions()->SearchSpecial(name);
236 8016002 : if (transition == kNotFound) return Map();
237 16025574 : 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 11568676 : MaybeHandle<Map> TransitionsAccessor::FindTransitionToDataProperty(
250 : Handle<Name> name, RequestedLocation requested_location) {
251 : DCHECK(name->IsUniqueName());
252 : DisallowHeapAllocation no_gc;
253 11568676 : PropertyAttributes attributes = name->IsPrivate() ? DONT_ENUM : NONE;
254 11568676 : Map target = SearchTransition(*name, kData, attributes);
255 11568676 : if (target.is_null()) return MaybeHandle<Map>();
256 11454048 : PropertyDetails details = target->GetLastDescriptorDetails();
257 : DCHECK_EQ(attributes, details.attributes());
258 : DCHECK_EQ(kData, details.kind());
259 22908096 : if (requested_location == kFieldOnly && details.location() != kField) {
260 0 : return MaybeHandle<Map>();
261 : }
262 22908096 : return Handle<Map>(target, isolate_);
263 : }
264 :
265 33240590 : Handle<String> TransitionsAccessor::ExpectedTransitionKey() {
266 : DisallowHeapAllocation no_gc;
267 33240590 : switch (encoding()) {
268 : case kPrototypeInfo:
269 : case kUninitialized:
270 : case kMigrationTarget:
271 : case kFullTransitionArray:
272 : return Handle<String>::null();
273 : case kWeakRef: {
274 : Map target = Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
275 : PropertyDetails details = GetSimpleTargetDetails(target);
276 21787420 : if (details.location() != kField) return Handle<String>::null();
277 : DCHECK_EQ(kData, details.kind());
278 21787420 : if (details.attributes() != NONE) return Handle<String>::null();
279 21782516 : Name name = GetSimpleTransitionKey(target);
280 21782516 : if (!name->IsString()) return Handle<String>::null();
281 21782516 : return handle(String::cast(name), isolate_);
282 : }
283 : }
284 0 : UNREACHABLE();
285 : }
286 :
287 21772127 : Handle<Map> TransitionsAccessor::ExpectedTransitionTarget() {
288 : DCHECK(!ExpectedTransitionKey().is_null());
289 43544254 : return handle(GetTarget(0), isolate_);
290 : }
291 :
292 14733824 : bool TransitionsAccessor::CanHaveMoreTransitions() {
293 14733824 : if (map_->is_dictionary_map()) return false;
294 14651972 : if (encoding() == kFullTransitionArray) {
295 273389 : return transitions()->number_of_transitions() < kMaxNumberOfTransitions;
296 : }
297 : return true;
298 : }
299 :
300 : // static
301 5756595 : bool TransitionsAccessor::IsMatchingMap(Map target, Name name,
302 : PropertyKind kind,
303 : PropertyAttributes attributes) {
304 : int descriptor = target->LastAdded();
305 5756595 : DescriptorArray descriptors = target->instance_descriptors();
306 : Name key = descriptors->GetKey(descriptor);
307 5756595 : if (key != name) return false;
308 11377327 : return descriptors->GetDetails(descriptor)
309 : .HasKindAndAttributes(kind, attributes);
310 : }
311 :
312 : // static
313 134635 : bool TransitionArray::CompactPrototypeTransitionArray(Isolate* isolate,
314 : WeakFixedArray array) {
315 : const int header = kProtoTransitionHeaderSize;
316 134635 : int number_of_transitions = NumberOfPrototypeTransitions(array);
317 134635 : if (number_of_transitions == 0) {
318 : // Empty array cannot be compacted.
319 : return false;
320 : }
321 : int new_number_of_transitions = 0;
322 33394 : for (int i = 0; i < number_of_transitions; i++) {
323 : MaybeObject target = array->Get(header + i);
324 : DCHECK(target->IsCleared() ||
325 : (target->IsWeak() && target->GetHeapObject()->IsMap()));
326 15836 : if (!target->IsCleared()) {
327 15077 : if (new_number_of_transitions != i) {
328 313 : array->Set(header + new_number_of_transitions, target);
329 : }
330 15077 : 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 3240 : for (int i = new_number_of_transitions; i < number_of_transitions; i++) {
337 759 : 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 134600 : Handle<WeakFixedArray> TransitionArray::GrowPrototypeTransitionArray(
347 : Handle<WeakFixedArray> array, int new_capacity, Isolate* isolate) {
348 : // Grow array by factor 2 up to MaxCachedPrototypeTransitions.
349 134600 : int capacity = array->length() - kProtoTransitionHeaderSize;
350 : new_capacity = Min(kMaxCachedPrototypeTransitions, new_capacity);
351 : DCHECK_GT(new_capacity, capacity);
352 134600 : int grow_by = new_capacity - capacity;
353 : array = isolate->factory()->CopyWeakFixedArrayAndGrow(array, grow_by,
354 134600 : AllocationType::kOld);
355 134600 : 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 134600 : return array;
361 : }
362 :
363 169405 : 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 169405 : if (map_->is_prototype_map()) return;
369 155610 : if (map_->is_dictionary_map() || !FLAG_cache_prototype_transitions) return;
370 :
371 : const int header = TransitionArray::kProtoTransitionHeaderSize;
372 :
373 148681 : Handle<WeakFixedArray> cache(GetPrototypeTransitions(), isolate_);
374 148681 : int capacity = cache->length() - header;
375 148681 : int transitions = TransitionArray::NumberOfPrototypeTransitions(*cache) + 1;
376 :
377 148681 : if (transitions > capacity) {
378 : // Grow the array if compacting it doesn't free space.
379 134635 : if (!TransitionArray::CompactPrototypeTransitionArray(isolate_, *cache)) {
380 134600 : if (capacity == TransitionArray::kMaxCachedPrototypeTransitions) return;
381 : cache = TransitionArray::GrowPrototypeTransitionArray(
382 134600 : cache, 2 * transitions, isolate_);
383 : Reload();
384 134600 : SetPrototypeTransitions(cache);
385 : }
386 : }
387 :
388 : // Reload number of transitions as they might have been compacted.
389 148681 : int last = TransitionArray::NumberOfPrototypeTransitions(*cache);
390 148681 : int entry = header + last;
391 :
392 297362 : cache->Set(entry, HeapObjectReference::Weak(*target_map));
393 : TransitionArray::SetNumberOfPrototypeTransitions(*cache, last + 1);
394 : }
395 :
396 185634 : Handle<Map> TransitionsAccessor::GetPrototypeTransition(
397 : Handle<Object> prototype) {
398 : DisallowHeapAllocation no_gc;
399 185634 : WeakFixedArray cache = GetPrototypeTransitions();
400 185634 : int length = TransitionArray::NumberOfPrototypeTransitions(cache);
401 921108 : for (int i = 0; i < length; i++) {
402 : MaybeObject target =
403 : cache->Get(TransitionArray::kProtoTransitionHeaderSize + i);
404 : DCHECK(target->IsWeakOrCleared());
405 : HeapObject heap_object;
406 383966 : if (target->GetHeapObjectIfWeak(&heap_object)) {
407 : Map map = Map::cast(heap_object);
408 361490 : if (map->prototype() == *prototype) {
409 16229 : return handle(map, isolate_);
410 : }
411 : }
412 : }
413 169405 : return Handle<Map>();
414 : }
415 :
416 334315 : WeakFixedArray TransitionsAccessor::GetPrototypeTransitions() {
417 384268 : if (encoding() != kFullTransitionArray ||
418 : !transitions()->HasPrototypeTransitions()) {
419 286550 : return ReadOnlyRoots(isolate_).empty_weak_fixed_array();
420 : }
421 : 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 281629 : MaybeObject::FromSmi(Smi::FromInt(value)));
430 0 : }
431 :
432 1547041 : int TransitionsAccessor::NumberOfTransitions() {
433 1547041 : switch (encoding()) {
434 : case kPrototypeInfo:
435 : case kUninitialized:
436 : case kMigrationTarget:
437 : return 0;
438 : case kWeakRef:
439 1262576 : return 1;
440 : case kFullTransitionArray:
441 1427 : 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 856 : Map TransitionsAccessor::GetMigrationTarget() {
457 856 : if (encoding() == kMigrationTarget) {
458 : return map_->raw_transitions()->cast<Map>();
459 : }
460 856 : return Map();
461 : }
462 :
463 72401 : void TransitionArray::Zap(Isolate* isolate) {
464 72401 : MemsetTagged(ObjectSlot(RawFieldOfElementAt(kPrototypeTransitionsIndex)),
465 : ReadOnlyRoots(isolate).the_hole_value(),
466 : length() - kPrototypeTransitionsIndex);
467 : SetNumberOfTransitions(0);
468 72402 : }
469 :
470 7374937 : void TransitionsAccessor::ReplaceTransitions(MaybeObject new_transitions) {
471 7374937 : if (encoding() == kFullTransitionArray) {
472 72400 : 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 72400 : old_transitions->Zap(isolate_);
483 : }
484 7374939 : map_->set_raw_transitions(new_transitions);
485 : MarkNeedsReload();
486 7374947 : }
487 :
488 134600 : void TransitionsAccessor::SetPrototypeTransitions(
489 : Handle<WeakFixedArray> proto_transitions) {
490 134600 : EnsureHasFullTransitionArray();
491 269200 : transitions()->SetPrototypeTransitions(*proto_transitions);
492 134600 : }
493 :
494 134600 : void TransitionsAccessor::EnsureHasFullTransitionArray() {
495 134600 : if (encoding() == kFullTransitionArray) return;
496 : int nof =
497 131819 : (encoding() == kUninitialized || encoding() == kMigrationTarget) ? 0 : 1;
498 131819 : Handle<TransitionArray> result = isolate_->factory()->NewTransitionArray(nof);
499 : Reload(); // Reload after possible GC.
500 131819 : if (nof == 1) {
501 6257 : 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 6257 : Handle<Map> target(GetSimpleTransition(), isolate_);
507 6257 : Name key = GetSimpleTransitionKey(*target);
508 12514 : result->Set(0, key, HeapObjectReference::Weak(*target));
509 : }
510 : }
511 131819 : ReplaceTransitions(MaybeObject::FromObject(*result));
512 : Reload(); // Reload after replacing transitions.
513 : }
514 :
515 745254 : void TransitionsAccessor::TraverseTransitionTreeInternal(
516 : TraverseCallback callback, void* data, DisallowHeapAllocation* no_gc) {
517 745254 : switch (encoding()) {
518 : case kPrototypeInfo:
519 : case kUninitialized:
520 : case kMigrationTarget:
521 : break;
522 : case kWeakRef: {
523 : Map simple_target =
524 : Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
525 : TransitionsAccessor(isolate_, simple_target, no_gc)
526 955022 : .TraverseTransitionTreeInternal(callback, data, no_gc);
527 : break;
528 : }
529 : case kFullTransitionArray: {
530 2729 : if (transitions()->HasPrototypeTransitions()) {
531 : WeakFixedArray proto_trans = transitions()->GetPrototypeTransitions();
532 54 : int length = TransitionArray::NumberOfPrototypeTransitions(proto_trans);
533 378 : for (int i = 0; i < length; ++i) {
534 : int index = TransitionArray::kProtoTransitionHeaderSize + i;
535 : MaybeObject target = proto_trans->Get(index);
536 : 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 9223 : for (int i = 0; i < transitions()->number_of_transitions(); ++i) {
546 6494 : TransitionsAccessor(isolate_, transitions()->GetTarget(i), no_gc)
547 6494 : .TraverseTransitionTreeInternal(callback, data, no_gc);
548 : }
549 : break;
550 : }
551 : }
552 745246 : callback(map_, data);
553 745245 : }
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 12131 : int TransitionArray::SearchDetails(int transition, PropertyKind kind,
583 : PropertyAttributes attributes,
584 : int* out_insertion_index) {
585 12131 : int nof_transitions = number_of_transitions();
586 : DCHECK(transition < nof_transitions);
587 12131 : Name key = GetKey(transition);
588 83975 : for (; transition < nof_transitions && GetKey(transition) == key;
589 : transition++) {
590 23257 : Map target = GetTarget(transition);
591 : PropertyDetails target_details =
592 23257 : TransitionsAccessor::GetTargetDetails(key, target);
593 :
594 : int cmp = CompareDetails(kind, attributes, target_details.kind(),
595 : target_details.attributes());
596 23257 : if (cmp == 0) {
597 603 : return transition;
598 22654 : } else if (cmp < 0) {
599 : break;
600 : }
601 : }
602 11528 : if (out_insertion_index != nullptr) *out_insertion_index = transition;
603 : return kNotFound;
604 : }
605 :
606 11756869 : Map TransitionArray::SearchDetailsAndGetTarget(int transition,
607 : PropertyKind kind,
608 : PropertyAttributes attributes) {
609 11756869 : int nof_transitions = number_of_transitions();
610 : DCHECK(transition < nof_transitions);
611 11756870 : Name key = GetKey(transition);
612 23559084 : for (; transition < nof_transitions && GetKey(transition) == key;
613 : transition++) {
614 : Map target = GetTarget(transition);
615 : PropertyDetails target_details =
616 11770591 : TransitionsAccessor::GetTargetDetails(key, target);
617 :
618 : int cmp = CompareDetails(kind, attributes, target_details.kind(),
619 : target_details.attributes());
620 11770593 : if (cmp == 0) {
621 11754715 : return target;
622 15878 : } else if (cmp < 0) {
623 : break;
624 : }
625 : }
626 2156 : return Map();
627 : }
628 :
629 229575 : int TransitionArray::Search(PropertyKind kind, Name name,
630 : PropertyAttributes attributes,
631 : int* out_insertion_index) {
632 : int transition = SearchName(name, out_insertion_index);
633 229575 : if (transition == kNotFound) return kNotFound;
634 12131 : return SearchDetails(transition, kind, attributes, out_insertion_index);
635 : }
636 :
637 12097833 : Map TransitionArray::SearchAndGetTarget(PropertyKind kind, Name name,
638 : PropertyAttributes attributes) {
639 : int transition = SearchName(name, nullptr);
640 12097830 : if (transition == kNotFound) {
641 340961 : return Map();
642 : }
643 11756869 : 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 5 : 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 5 : 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 5 : CompareKeys(temp_key, temp_key->Hash(), temp_kind, temp_attributes,
679 : 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 640 : bool TransitionsAccessor::HasIntegrityLevelTransitionTo(
694 : Map to, Symbol* out_symbol, PropertyAttributes* out_integrity_level) {
695 640 : ReadOnlyRoots roots(isolate_);
696 1280 : if (SearchSpecial(roots.frozen_symbol()) == to) {
697 121 : if (out_integrity_level) *out_integrity_level = FROZEN;
698 242 : if (out_symbol) *out_symbol = roots.frozen_symbol();
699 1038 : } else if (SearchSpecial(roots.sealed_symbol()) == to) {
700 283 : if (out_integrity_level) *out_integrity_level = SEALED;
701 566 : if (out_symbol) *out_symbol = roots.sealed_symbol();
702 472 : } else if (SearchSpecial(roots.nonextensible_symbol()) == to) {
703 209 : if (out_integrity_level) *out_integrity_level = NONE;
704 375 : if (out_symbol) *out_symbol = roots.nonextensible_symbol();
705 : } else {
706 : return false;
707 : }
708 : return true;
709 : }
710 :
711 : } // namespace internal
712 122004 : } // namespace v8
|
