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 99157516 : void TransitionsAccessor::Initialize() {
15 198315032 : raw_transitions_ = map_->raw_transitions();
16 99157516 : if (raw_transitions_->IsSmi()) {
17 44841071 : encoding_ = kUninitialized;
18 54316460 : } else if (HeapObject::cast(raw_transitions_)->IsWeakCell()) {
19 27349214 : encoding_ = kWeakCell;
20 26967246 : } else if (StoreHandler::IsHandler(raw_transitions_)) {
21 323789 : encoding_ = kHandler;
22 53286893 : } else if (HeapObject::cast(raw_transitions_)->IsTransitionArray()) {
23 26285050 : encoding_ = kFullTransitionArray;
24 : } else {
25 : DCHECK(HeapObject::cast(raw_transitions_)->IsPrototypeInfo());
26 358394 : encoding_ = kPrototypeInfo;
27 : }
28 99157518 : target_cell_ = nullptr;
29 : #if DEBUG
30 : needs_reload_ = false;
31 : #endif
32 99157518 : }
33 :
34 726061 : Map* TransitionsAccessor::GetSimpleTransition() {
35 571467 : switch (encoding()) {
36 : case kWeakCell:
37 123362 : return Map::cast(GetTargetCell<kWeakCell>()->value());
38 : case kHandler:
39 31232 : return Map::cast(GetTargetCell<kHandler>()->value());
40 : default:
41 : return nullptr;
42 : }
43 : }
44 :
45 101766 : bool TransitionsAccessor::HasSimpleTransitionTo(WeakCell* cell) {
46 : DCHECK(cell->value()->IsMap());
47 101766 : switch (encoding()) {
48 : case kWeakCell:
49 15510 : return raw_transitions_ == cell;
50 : case kHandler:
51 14036 : return StoreHandler::GetTransitionCell(raw_transitions_) == cell;
52 : case kPrototypeInfo:
53 : case kUninitialized:
54 : case kFullTransitionArray:
55 : return false;
56 : }
57 0 : UNREACHABLE();
58 : return false; // Make GCC happy.
59 : }
60 :
61 6145953 : void TransitionsAccessor::Insert(Handle<Name> name, Handle<Map> target,
62 6704500 : SimpleTransitionFlag flag) {
63 : DCHECK(!map_handle_.is_null());
64 6145953 : Isolate* isolate = map_->GetIsolate();
65 6145953 : Handle<WeakCell> weak_cell_with_target = Map::WeakCellForMap(target);
66 : Reload();
67 6145954 : target->SetBackPointer(map_);
68 :
69 : // If the map doesn't have any transitions at all yet, install the new one.
70 6145954 : if (encoding() == kUninitialized) {
71 5889108 : if (flag == SIMPLE_PROPERTY_TRANSITION) {
72 5648721 : ReplaceTransitions(*weak_cell_with_target);
73 5648721 : return;
74 : }
75 : // If the flag requires a full TransitionArray, allocate one.
76 240387 : Handle<TransitionArray> result = TransitionArray::Allocate(isolate, 0, 1);
77 240387 : ReplaceTransitions(*result);
78 : Reload();
79 : }
80 :
81 497233 : bool is_special_transition = flag == SPECIAL_TRANSITION;
82 : // If the map has a simple transition, check if it should be overwritten.
83 497233 : Map* simple_transition = GetSimpleTransition();
84 497233 : if (simple_transition != nullptr) {
85 80360 : Name* key = GetSimpleTransitionKey(simple_transition);
86 80360 : PropertyDetails old_details = GetSimpleTargetDetails(simple_transition);
87 : PropertyDetails new_details = is_special_transition
88 : ? PropertyDetails::Empty()
89 80360 : : GetTargetDetails(*name, *target);
90 179922 : if (flag == SIMPLE_PROPERTY_TRANSITION && key->Equals(*name) &&
91 95678 : old_details.kind() == new_details.kind() &&
92 : old_details.attributes() == new_details.attributes()) {
93 12711 : ReplaceTransitions(*weak_cell_with_target);
94 : return;
95 : }
96 : // Otherwise allocate a full TransitionArray with slack for a new entry.
97 67649 : Handle<TransitionArray> result = TransitionArray::Allocate(isolate, 1, 1);
98 : // Reload state; the allocation might have caused it to be cleared.
99 : Reload();
100 67649 : simple_transition = GetSimpleTransition();
101 67649 : if (simple_transition != nullptr) {
102 : result->Set(0, GetSimpleTransitionKey(simple_transition),
103 135298 : raw_transitions_);
104 : } else {
105 : result->SetNumberOfTransitions(0);
106 : }
107 67649 : ReplaceTransitions(*result);
108 : Reload();
109 : }
110 :
111 : // At this point, we know that the map has a full TransitionArray.
112 : DCHECK_EQ(kFullTransitionArray, encoding());
113 :
114 : int number_of_transitions = 0;
115 : int new_nof = 0;
116 484522 : int insertion_index = kNotFound;
117 : DCHECK_EQ(is_special_transition, IsSpecialTransition(*name));
118 : PropertyDetails details = is_special_transition
119 : ? PropertyDetails::Empty()
120 484522 : : GetTargetDetails(*name, *target);
121 :
122 : {
123 : DisallowHeapAllocation no_gc;
124 : TransitionArray* array = transitions();
125 484522 : number_of_transitions = array->number_of_transitions();
126 : new_nof = number_of_transitions;
127 :
128 : int index =
129 : is_special_transition
130 : ? array->SearchSpecial(Symbol::cast(*name), &insertion_index)
131 : : array->Search(details.kind(), *name, details.attributes(),
132 726771 : &insertion_index);
133 : // If an existing entry was found, overwrite it and return.
134 484522 : if (index != kNotFound) {
135 : array->SetTarget(index, *weak_cell_with_target);
136 : return;
137 : }
138 :
139 474032 : ++new_nof;
140 474032 : CHECK_LE(new_nof, kMaxNumberOfTransitions);
141 : DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
142 :
143 : // If there is enough capacity, insert new entry into the existing array.
144 474032 : if (new_nof <= array->Capacity()) {
145 : array->SetNumberOfTransitions(new_nof);
146 10417784 : for (index = number_of_transitions; index > insertion_index; --index) {
147 : array->SetKey(index, array->GetKey(index - 1));
148 9617768 : array->SetTarget(index, array->GetRawTarget(index - 1));
149 : }
150 : array->SetKey(index, *name);
151 : array->SetTarget(index, *weak_cell_with_target);
152 : SLOW_DCHECK(array->IsSortedNoDuplicates());
153 : return;
154 : }
155 : }
156 :
157 : // We're gonna need a bigger TransitionArray.
158 : Handle<TransitionArray> result = TransitionArray::Allocate(
159 : isolate, new_nof,
160 74024 : Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions));
161 :
162 : // The map's transition array may have shrunk during the allocation above as
163 : // it was weakly traversed, though it is guaranteed not to disappear. Trim the
164 : // result copy if needed, and recompute variables.
165 : Reload();
166 : DisallowHeapAllocation no_gc;
167 : TransitionArray* array = transitions();
168 74024 : if (array->number_of_transitions() != number_of_transitions) {
169 : DCHECK(array->number_of_transitions() < number_of_transitions);
170 :
171 0 : number_of_transitions = array->number_of_transitions();
172 : new_nof = number_of_transitions;
173 :
174 0 : insertion_index = kNotFound;
175 : int index =
176 : is_special_transition
177 : ? array->SearchSpecial(Symbol::cast(*name), &insertion_index)
178 : : array->Search(details.kind(), *name, details.attributes(),
179 0 : &insertion_index);
180 0 : if (index == kNotFound) {
181 0 : ++new_nof;
182 : } else {
183 0 : insertion_index = index;
184 : }
185 : DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
186 :
187 0 : result->Shrink(TransitionArray::ToKeyIndex(new_nof));
188 : result->SetNumberOfTransitions(new_nof);
189 : }
190 :
191 74024 : if (array->HasPrototypeTransitions()) {
192 : result->SetPrototypeTransitions(array->GetPrototypeTransitions());
193 : }
194 :
195 : DCHECK_NE(kNotFound, insertion_index);
196 285925 : for (int i = 0; i < insertion_index; ++i) {
197 423802 : result->Set(i, array->GetKey(i), array->GetRawTarget(i));
198 : }
199 74024 : result->Set(insertion_index, *name, *weak_cell_with_target);
200 375979 : for (int i = insertion_index; i < number_of_transitions; ++i) {
201 455862 : result->Set(i + 1, array->GetKey(i), array->GetRawTarget(i));
202 : }
203 :
204 : SLOW_DCHECK(result->IsSortedNoDuplicates());
205 74024 : ReplaceTransitions(*result);
206 : }
207 :
208 456291 : void TransitionsAccessor::UpdateHandler(Name* name, Object* handler) {
209 444766 : if (map_->is_dictionary_map()) return;
210 209922 : switch (encoding()) {
211 : case kPrototypeInfo:
212 : case kUninitialized:
213 0 : UNREACHABLE();
214 : return;
215 : case kWeakCell:
216 : case kHandler:
217 : DCHECK_EQ(GetSimpleTransition(), GetTargetFromRaw(handler));
218 197929 : ReplaceTransitions(handler);
219 197929 : return;
220 : case kFullTransitionArray: {
221 11993 : PropertyAttributes attributes = name->IsPrivate() ? DONT_ENUM : NONE;
222 11993 : int transition = transitions()->Search(kData, name, attributes);
223 : DCHECK_NE(kNotFound, transition);
224 : DCHECK_EQ(transitions()->GetTarget(transition),
225 : GetTargetFromRaw(handler));
226 : transitions()->SetTarget(transition, handler);
227 : return;
228 : }
229 : }
230 : }
231 :
232 4303862 : Object* TransitionsAccessor::SearchHandler(Name* name,
233 4351300 : Handle<Map>* out_transition) {
234 4303862 : switch (encoding()) {
235 : case kPrototypeInfo:
236 : case kUninitialized:
237 : case kWeakCell:
238 : return nullptr;
239 : case kHandler: {
240 : Object* raw_handler = StoreHandler::ValidHandlerOrNull(
241 21260 : raw_transitions_, name, out_transition);
242 21260 : if (raw_handler == nullptr) return raw_handler;
243 : // Check transition key.
244 11075 : WeakCell* target_cell = StoreHandler::GetTransitionCell(raw_handler);
245 11075 : if (!IsMatchingMap(target_cell, name, kData, NONE)) return nullptr;
246 1530 : return raw_handler;
247 : }
248 :
249 : case kFullTransitionArray: {
250 32356 : int transition = transitions()->Search(kData, name, NONE);
251 32356 : if (transition == kNotFound) return nullptr;
252 15082 : Object* raw_handler = transitions()->GetRawTarget(transition);
253 15082 : if (StoreHandler::IsHandler(raw_handler)) {
254 : return StoreHandler::ValidHandlerOrNull(raw_handler, name,
255 1554 : out_transition);
256 : }
257 : return nullptr;
258 : }
259 : }
260 0 : UNREACHABLE();
261 : return nullptr; // Make GCC happy.
262 : }
263 :
264 32003680 : Map* TransitionsAccessor::SearchTransition(Name* name, PropertyKind kind,
265 59106496 : PropertyAttributes attributes) {
266 : DCHECK(name->IsUniqueName());
267 : WeakCell* cell = nullptr;
268 32003680 : switch (encoding()) {
269 : case kPrototypeInfo:
270 : case kUninitialized:
271 : return nullptr;
272 : case kWeakCell:
273 : cell = GetTargetCell<kWeakCell>();
274 5532773 : break;
275 : case kHandler:
276 : cell = GetTargetCell<kHandler>();
277 62865 : break;
278 : case kFullTransitionArray: {
279 10871848 : int transition = transitions()->Search(kind, name, attributes);
280 10871848 : if (transition == kNotFound) return nullptr;
281 10635330 : return transitions()->GetTarget(transition);
282 : }
283 : }
284 : DCHECK(!cell->cleared());
285 5595637 : if (!IsMatchingMap(cell, name, kind, attributes)) return nullptr;
286 5518059 : return Map::cast(cell->value());
287 : }
288 :
289 4687370 : Map* TransitionsAccessor::SearchSpecial(Symbol* name) {
290 1912309 : if (encoding() != kFullTransitionArray) return nullptr;
291 : int transition = transitions()->SearchSpecial(name);
292 1388321 : if (transition == kNotFound) return nullptr;
293 1386740 : return transitions()->GetTarget(transition);
294 : }
295 :
296 : // static
297 0 : bool TransitionsAccessor::IsSpecialTransition(Name* name) {
298 0 : if (!name->IsSymbol()) return false;
299 0 : Heap* heap = name->GetHeap();
300 0 : return name == heap->nonextensible_symbol() ||
301 0 : name == heap->sealed_symbol() || name == heap->frozen_symbol() ||
302 0 : name == heap->elements_transition_symbol() ||
303 0 : name == heap->strict_function_transition_symbol();
304 : }
305 :
306 10298749 : Handle<Map> TransitionsAccessor::FindTransitionToField(Handle<Name> name) {
307 : DCHECK(name->IsUniqueName());
308 : DisallowHeapAllocation no_gc;
309 10298749 : Map* target = SearchTransition(*name, kData, NONE);
310 10298749 : if (target == nullptr) return Handle<Map>::null();
311 : PropertyDetails details = target->GetLastDescriptorDetails();
312 : DCHECK_EQ(NONE, details.attributes());
313 10199752 : if (details.location() != kField) return Handle<Map>::null();
314 : DCHECK_EQ(kData, details.kind());
315 10199742 : return Handle<Map>(target);
316 : }
317 :
318 49185650 : Handle<String> TransitionsAccessor::ExpectedTransitionKey() {
319 : DisallowHeapAllocation no_gc;
320 : WeakCell* cell = nullptr;
321 29687580 : switch (encoding()) {
322 : case kPrototypeInfo:
323 : case kUninitialized:
324 : case kFullTransitionArray:
325 : return Handle<String>::null();
326 : case kWeakCell:
327 : cell = GetTargetCell<kWeakCell>();
328 19498065 : break;
329 : case kHandler:
330 : cell = GetTargetCell<kHandler>();
331 5 : break;
332 : }
333 : DCHECK(!cell->cleared());
334 : Map* target = Map::cast(cell->value());
335 19498070 : PropertyDetails details = GetSimpleTargetDetails(target);
336 19498070 : if (details.location() != kField) return Handle<String>::null();
337 : DCHECK_EQ(kData, details.kind());
338 19497715 : if (details.attributes() != NONE) return Handle<String>::null();
339 19497715 : Name* name = GetSimpleTransitionKey(target);
340 19497715 : if (!name->IsString()) return Handle<String>::null();
341 : return handle(String::cast(name));
342 : }
343 :
344 19488806 : Handle<Map> TransitionsAccessor::ExpectedTransitionTarget() {
345 : DCHECK(!ExpectedTransitionKey().is_null());
346 38977612 : return handle(GetTarget(0));
347 : }
348 :
349 25377202 : bool TransitionsAccessor::CanHaveMoreTransitions() {
350 25283984 : if (map_->is_dictionary_map()) return false;
351 12560236 : if (encoding() == kFullTransitionArray) {
352 174974 : return transitions()->number_of_transitions() < kMaxNumberOfTransitions;
353 : }
354 : return true;
355 : }
356 :
357 : // static
358 5606713 : bool TransitionsAccessor::IsMatchingMap(WeakCell* target_cell, Name* name,
359 : PropertyKind kind,
360 : PropertyAttributes attributes) {
361 : Map* target = Map::cast(target_cell->value());
362 : int descriptor = target->LastAdded();
363 : DescriptorArray* descriptors = target->instance_descriptors();
364 : Name* key = descriptors->GetKey(descriptor);
365 5606713 : if (key != name) return false;
366 5527929 : PropertyDetails details = descriptors->GetDetails(descriptor);
367 11051118 : return (details.kind() == kind && details.attributes() == attributes);
368 : }
369 :
370 : // static
371 157249 : bool TransitionArray::CompactPrototypeTransitionArray(FixedArray* array) {
372 : const int header = kProtoTransitionHeaderSize;
373 157249 : int number_of_transitions = NumberOfPrototypeTransitions(array);
374 157249 : if (number_of_transitions == 0) {
375 : // Empty array cannot be compacted.
376 : return false;
377 : }
378 : int new_number_of_transitions = 0;
379 24785 : for (int i = 0; i < number_of_transitions; i++) {
380 20618 : Object* cell = array->get(header + i);
381 20618 : if (!WeakCell::cast(cell)->cleared()) {
382 15692 : if (new_number_of_transitions != i) {
383 8 : array->set(header + new_number_of_transitions, cell);
384 : }
385 15692 : new_number_of_transitions++;
386 : }
387 : }
388 : // Fill slots that became free with undefined value.
389 9093 : for (int i = new_number_of_transitions; i < number_of_transitions; i++) {
390 4926 : array->set_undefined(header + i);
391 : }
392 4167 : if (number_of_transitions != new_number_of_transitions) {
393 : SetNumberOfPrototypeTransitions(array, new_number_of_transitions);
394 : }
395 4167 : return new_number_of_transitions < number_of_transitions;
396 : }
397 :
398 :
399 : // static
400 154802 : Handle<FixedArray> TransitionArray::GrowPrototypeTransitionArray(
401 : Handle<FixedArray> array, int new_capacity, Isolate* isolate) {
402 : // Grow array by factor 2 up to MaxCachedPrototypeTransitions.
403 154802 : int capacity = array->length() - kProtoTransitionHeaderSize;
404 : new_capacity = Min(kMaxCachedPrototypeTransitions, new_capacity);
405 : DCHECK_GT(new_capacity, capacity);
406 154802 : int grow_by = new_capacity - capacity;
407 154802 : array = isolate->factory()->CopyFixedArrayAndGrow(array, grow_by, TENURED);
408 154802 : if (capacity < 0) {
409 : // There was no prototype transitions array before, so the size
410 : // couldn't be copied. Initialize it explicitly.
411 : SetNumberOfPrototypeTransitions(*array, 0);
412 : }
413 154802 : return array;
414 : }
415 :
416 202818 : void TransitionsAccessor::PutPrototypeTransition(Handle<Object> prototype,
417 : Handle<Map> target_map) {
418 : DCHECK(HeapObject::cast(*prototype)->map()->IsMap());
419 : // Don't cache prototype transition if this map is either shared, or a map of
420 : // a prototype.
421 434644 : if (map_->is_prototype_map()) return;
422 189295 : if (map_->is_dictionary_map() || !FLAG_cache_prototype_transitions) return;
423 :
424 : const int header = TransitionArray::kProtoTransitionHeaderSize;
425 :
426 173810 : Handle<FixedArray> cache(GetPrototypeTransitions());
427 173810 : int capacity = cache->length() - header;
428 173810 : int transitions = TransitionArray::NumberOfPrototypeTransitions(*cache) + 1;
429 :
430 173810 : if (transitions > capacity) {
431 : // Grow the array if compacting it doesn't free space.
432 157249 : if (!TransitionArray::CompactPrototypeTransitionArray(*cache)) {
433 154802 : if (capacity == TransitionArray::kMaxCachedPrototypeTransitions) return;
434 : cache = TransitionArray::GrowPrototypeTransitionArray(
435 154802 : cache, 2 * transitions, target_map->GetIsolate());
436 : Reload();
437 154802 : SetPrototypeTransitions(cache);
438 : }
439 : }
440 :
441 : // Reload number of transitions as they might have been compacted.
442 173810 : int last = TransitionArray::NumberOfPrototypeTransitions(*cache);
443 173810 : int entry = header + last;
444 :
445 173810 : Handle<WeakCell> target_cell = Map::WeakCellForMap(target_map);
446 : Reload(); // Reload after possible GC.
447 173810 : cache->set(entry, *target_cell);
448 : TransitionArray::SetNumberOfPrototypeTransitions(*cache, last + 1);
449 : }
450 :
451 2650252 : Handle<Map> TransitionsAccessor::GetPrototypeTransition(
452 : Handle<Object> prototype) {
453 : DisallowHeapAllocation no_gc;
454 2650252 : FixedArray* cache = GetPrototypeTransitions();
455 2650252 : int length = TransitionArray::NumberOfPrototypeTransitions(cache);
456 2650252 : for (int i = 0; i < length; i++) {
457 : WeakCell* target_cell = WeakCell::cast(
458 3704644 : cache->get(TransitionArray::kProtoTransitionHeaderSize + i));
459 6529408 : if (!target_cell->cleared() &&
460 : Map::cast(target_cell->value())->prototype() == *prototype) {
461 : return handle(Map::cast(target_cell->value()));
462 : }
463 : }
464 202818 : return Handle<Map>();
465 : }
466 :
467 7810044 : FixedArray* TransitionsAccessor::GetPrototypeTransitions() {
468 5321154 : if (encoding() != kFullTransitionArray ||
469 : !transitions()->HasPrototypeTransitions()) {
470 670344 : return map_->GetHeap()->empty_fixed_array();
471 : }
472 2488890 : return transitions()->GetPrototypeTransitions();
473 : }
474 :
475 : // static
476 0 : void TransitionArray::SetNumberOfPrototypeTransitions(
477 : FixedArray* proto_transitions, int value) {
478 : DCHECK_NE(proto_transitions->length(), 0);
479 : proto_transitions->set(kProtoTransitionNumberOfEntriesOffset,
480 : Smi::FromInt(value));
481 0 : }
482 :
483 1936549 : int TransitionsAccessor::NumberOfTransitions() {
484 1936028 : switch (encoding()) {
485 : case kPrototypeInfo:
486 : case kUninitialized:
487 : return 0;
488 : case kWeakCell:
489 : case kHandler:
490 1599929 : return 1;
491 : case kFullTransitionArray:
492 521 : return transitions()->number_of_transitions();
493 : }
494 0 : UNREACHABLE();
495 : return 0; // Make GCC happy.
496 : }
497 :
498 531041 : Handle<TransitionArray> TransitionArray::Allocate(Isolate* isolate,
499 : int number_of_transitions,
500 : int slack) {
501 : Handle<FixedArray> array = isolate->factory()->NewTransitionArray(
502 1062082 : LengthFor(number_of_transitions + slack));
503 : array->set(kPrototypeTransitionsIndex, Smi::kZero);
504 : array->set(kTransitionLengthIndex, Smi::FromInt(number_of_transitions));
505 531041 : return Handle<TransitionArray>::cast(array);
506 : }
507 :
508 74024 : void TransitionArray::Zap() {
509 : MemsetPointer(data_start() + kPrototypeTransitionsIndex,
510 : GetHeap()->the_hole_value(),
511 74024 : length() - kPrototypeTransitionsIndex);
512 : SetNumberOfTransitions(0);
513 74024 : }
514 :
515 6464423 : void TransitionsAccessor::ReplaceTransitions(Object* new_transitions) {
516 6390399 : if (encoding() == kFullTransitionArray) {
517 : TransitionArray* old_transitions = transitions();
518 : #if DEBUG
519 : CheckNewTransitionsAreConsistent(old_transitions, new_transitions);
520 : DCHECK(old_transitions != new_transitions);
521 : #endif
522 : // Transition arrays are not shared. When one is replaced, it should not
523 : // keep referenced objects alive, so we zap it.
524 : // When there is another reference to the array somewhere (e.g. a handle),
525 : // not zapping turns from a waste of memory into a source of crashes.
526 74024 : old_transitions->Zap();
527 : }
528 6390399 : map_->set_raw_transitions(new_transitions);
529 : MarkNeedsReload();
530 6390400 : }
531 :
532 154802 : void TransitionsAccessor::SetPrototypeTransitions(
533 154802 : Handle<FixedArray> proto_transitions) {
534 154802 : EnsureHasFullTransitionArray();
535 : transitions()->SetPrototypeTransitions(*proto_transitions);
536 154802 : }
537 :
538 161387 : void TransitionsAccessor::EnsureHasFullTransitionArray() {
539 309604 : if (encoding() == kFullTransitionArray) return;
540 148981 : int nof = encoding() == kUninitialized ? 0 : 1;
541 : Handle<TransitionArray> result =
542 297962 : TransitionArray::Allocate(map_->GetIsolate(), nof);
543 : Reload(); // Reload after possible GC.
544 148981 : if (nof == 1) {
545 6585 : if (encoding() == kUninitialized) {
546 : // If allocation caused GC and cleared the target, trim the new array.
547 0 : result->Shrink(TransitionArray::ToKeyIndex(0));
548 : result->SetNumberOfTransitions(0);
549 : } else {
550 : // Otherwise populate the new array.
551 6585 : Handle<Map> target(GetSimpleTransition());
552 6585 : Handle<WeakCell> weak_cell_with_target = Map::WeakCellForMap(target);
553 : Reload(); // Reload after possible GC.
554 6585 : Name* key = GetSimpleTransitionKey(*target);
555 6585 : result->Set(0, key, *weak_cell_with_target);
556 : }
557 : }
558 148981 : ReplaceTransitions(*result);
559 : Reload(); // Reload after replacing transitions.
560 : }
561 :
562 321938 : void TransitionsAccessor::TraverseTransitionTreeInternal(
563 561272 : TraverseCallback callback, void* data, DisallowHeapAllocation* no_gc) {
564 : Map* simple_target = nullptr;
565 321938 : switch (encoding()) {
566 : case kPrototypeInfo:
567 : case kUninitialized:
568 : break;
569 : case kWeakCell:
570 : simple_target = Map::cast(GetTargetCell<kWeakCell>()->value());
571 56814 : break;
572 : case kHandler:
573 : simple_target = Map::cast(GetTargetCell<kHandler>()->value());
574 169340 : break;
575 : case kFullTransitionArray: {
576 2568 : if (transitions()->HasPrototypeTransitions()) {
577 : FixedArray* proto_trans = transitions()->GetPrototypeTransitions();
578 60 : int length = TransitionArray::NumberOfPrototypeTransitions(proto_trans);
579 300 : for (int i = 0; i < length; ++i) {
580 180 : int index = TransitionArray::kProtoTransitionHeaderSize + i;
581 : WeakCell* cell = WeakCell::cast(proto_trans->get(index));
582 180 : if (cell->cleared()) continue;
583 : TransitionsAccessor(Map::cast(cell->value()), no_gc)
584 180 : .TraverseTransitionTreeInternal(callback, data, no_gc);
585 : }
586 : }
587 10552 : for (int i = 0; i < transitions()->number_of_transitions(); ++i) {
588 : TransitionsAccessor(transitions()->GetTarget(i), no_gc)
589 3992 : .TraverseTransitionTreeInternal(callback, data, no_gc);
590 : }
591 : break;
592 : }
593 : }
594 321938 : if (simple_target != nullptr) {
595 : TransitionsAccessor(simple_target, no_gc)
596 226154 : .TraverseTransitionTreeInternal(callback, data, no_gc);
597 : }
598 321938 : callback(map_, data);
599 321938 : }
600 :
601 : #ifdef DEBUG
602 : void TransitionsAccessor::CheckNewTransitionsAreConsistent(
603 : TransitionArray* old_transitions, Object* transitions) {
604 : // This function only handles full transition arrays.
605 : DCHECK_EQ(kFullTransitionArray, encoding());
606 : TransitionArray* new_transitions = TransitionArray::cast(transitions);
607 : for (int i = 0; i < old_transitions->number_of_transitions(); i++) {
608 : Map* target = old_transitions->GetTarget(i);
609 : if (target->instance_descriptors() == map_->instance_descriptors()) {
610 : Name* key = old_transitions->GetKey(i);
611 : int new_target_index;
612 : if (IsSpecialTransition(key)) {
613 : new_target_index = new_transitions->SearchSpecial(Symbol::cast(key));
614 : } else {
615 : PropertyDetails details = GetTargetDetails(key, target);
616 : new_target_index =
617 : new_transitions->Search(details.kind(), key, details.attributes());
618 : }
619 : DCHECK_NE(TransitionArray::kNotFound, new_target_index);
620 : DCHECK_EQ(target, new_transitions->GetTarget(new_target_index));
621 : }
622 : }
623 : }
624 : #endif
625 :
626 : // Private non-static helper functions (operating on full transition arrays).
627 :
628 10683076 : int TransitionArray::SearchDetails(int transition, PropertyKind kind,
629 : PropertyAttributes attributes,
630 : int* out_insertion_index) {
631 10683076 : int nof_transitions = number_of_transitions();
632 : DCHECK(transition < nof_transitions);
633 : Name* key = GetKey(transition);
634 21405628 : for (; transition < nof_transitions && GetKey(transition) == key;
635 : transition++) {
636 : Map* target = GetTarget(transition);
637 : PropertyDetails target_details =
638 : TransitionsAccessor::GetTargetDetails(key, target);
639 :
640 : int cmp = CompareDetails(kind, attributes, target_details.kind(),
641 : target_details.attributes());
642 10697626 : if (cmp == 0) {
643 : return transition;
644 24731 : } else if (cmp < 0) {
645 : break;
646 : }
647 : }
648 10181 : if (out_insertion_index != nullptr) *out_insertion_index = transition;
649 : return kNotFound;
650 : }
651 :
652 :
653 11158446 : int TransitionArray::Search(PropertyKind kind, Name* name,
654 : PropertyAttributes attributes,
655 : int* out_insertion_index) {
656 11158446 : int transition = SearchName(name, out_insertion_index);
657 11158445 : if (transition == kNotFound) return kNotFound;
658 10683076 : return SearchDetails(transition, kind, attributes, out_insertion_index);
659 : }
660 :
661 0 : void TransitionArray::Sort() {
662 : DisallowHeapAllocation no_gc;
663 : // In-place insertion sort.
664 0 : int length = number_of_transitions();
665 0 : for (int i = 1; i < length; i++) {
666 : Name* key = GetKey(i);
667 : Map* target = GetTarget(i);
668 : PropertyKind kind = kData;
669 : PropertyAttributes attributes = NONE;
670 0 : if (!TransitionsAccessor::IsSpecialTransition(key)) {
671 : PropertyDetails details =
672 : TransitionsAccessor::GetTargetDetails(key, target);
673 : kind = details.kind();
674 : attributes = details.attributes();
675 : }
676 : int j;
677 0 : for (j = i - 1; j >= 0; j--) {
678 : Name* temp_key = GetKey(j);
679 : Map* temp_target = GetTarget(j);
680 : PropertyKind temp_kind = kData;
681 : PropertyAttributes temp_attributes = NONE;
682 0 : if (!TransitionsAccessor::IsSpecialTransition(temp_key)) {
683 : PropertyDetails details =
684 : TransitionsAccessor::GetTargetDetails(temp_key, temp_target);
685 : temp_kind = details.kind();
686 : temp_attributes = details.attributes();
687 : }
688 : int cmp =
689 : CompareKeys(temp_key, temp_key->Hash(), temp_kind, temp_attributes,
690 : key, key->Hash(), kind, attributes);
691 0 : if (cmp > 0) {
692 : SetKey(j + 1, temp_key);
693 : SetTarget(j + 1, temp_target);
694 : } else {
695 : break;
696 : }
697 : }
698 : SetKey(j + 1, key);
699 : SetTarget(j + 1, target);
700 : }
701 : DCHECK(IsSortedNoDuplicates());
702 0 : }
703 :
704 : } // namespace internal
705 : } // namespace v8
|
