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
11namespace v8 {
12namespace internal {
13
14
15// static
16void TransitionArray::Insert(Handle<Map> map, Handle<Name> name,
17                             Handle<Map> target, SimpleTransitionFlag flag) {
18  Isolate* isolate = map->GetIsolate();
19  target->SetBackPointer(*map);
20
21  // If the map doesn't have any transitions at all yet, install the new one.
22  if (CanStoreSimpleTransition(map->raw_transitions())) {
23    if (flag == SIMPLE_PROPERTY_TRANSITION) {
24      Handle<WeakCell> cell = Map::WeakCellForMap(target);
25      ReplaceTransitions(map, *cell);
26      return;
27    }
28    // If the flag requires a full TransitionArray, allocate one.
29    Handle<TransitionArray> result = Allocate(isolate, 0, 1);
30    ReplaceTransitions(map, *result);
31  }
32
33  bool is_special_transition = flag == SPECIAL_TRANSITION;
34  // If the map has a simple transition, check if it should be overwritten.
35  if (IsSimpleTransition(map->raw_transitions())) {
36    Map* old_target = GetSimpleTransition(map->raw_transitions());
37    Name* key = GetSimpleTransitionKey(old_target);
38    PropertyDetails old_details = GetSimpleTargetDetails(old_target);
39    PropertyDetails new_details = is_special_transition
40                                      ? PropertyDetails::Empty()
41                                      : GetTargetDetails(*name, *target);
42    if (flag == SIMPLE_PROPERTY_TRANSITION && key->Equals(*name) &&
43        old_details.kind() == new_details.kind() &&
44        old_details.attributes() == new_details.attributes()) {
45      Handle<WeakCell> cell = Map::WeakCellForMap(target);
46      ReplaceTransitions(map, *cell);
47      return;
48    }
49    // Otherwise allocate a full TransitionArray with slack for a new entry.
50    Handle<TransitionArray> result = Allocate(isolate, 1, 1);
51    // Re-read existing data; the allocation might have caused it to be cleared.
52    if (IsSimpleTransition(map->raw_transitions())) {
53      old_target = GetSimpleTransition(map->raw_transitions());
54      result->Set(0, GetSimpleTransitionKey(old_target), old_target);
55    } else {
56      result->SetNumberOfTransitions(0);
57    }
58    ReplaceTransitions(map, *result);
59  }
60
61  // At this point, we know that the map has a full TransitionArray.
62  DCHECK(IsFullTransitionArray(map->raw_transitions()));
63
64  int number_of_transitions = 0;
65  int new_nof = 0;
66  int insertion_index = kNotFound;
67  DCHECK_EQ(is_special_transition, IsSpecialTransition(*name));
68  PropertyDetails details = is_special_transition
69                                ? PropertyDetails::Empty()
70                                : GetTargetDetails(*name, *target);
71
72  {
73    DisallowHeapAllocation no_gc;
74    TransitionArray* array = TransitionArray::cast(map->raw_transitions());
75    number_of_transitions = array->number_of_transitions();
76    new_nof = number_of_transitions;
77
78    int index =
79        is_special_transition
80            ? array->SearchSpecial(Symbol::cast(*name), &insertion_index)
81            : array->Search(details.kind(), *name, details.attributes(),
82                            &insertion_index);
83    // If an existing entry was found, overwrite it and return.
84    if (index != kNotFound) {
85      array->SetTarget(index, *target);
86      return;
87    }
88
89    ++new_nof;
90    CHECK(new_nof <= kMaxNumberOfTransitions);
91    DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
92
93    // If there is enough capacity, insert new entry into the existing array.
94    if (new_nof <= Capacity(array)) {
95      array->SetNumberOfTransitions(new_nof);
96      for (index = number_of_transitions; index > insertion_index; --index) {
97        array->SetKey(index, array->GetKey(index - 1));
98        array->SetTarget(index, array->GetTarget(index - 1));
99      }
100      array->SetKey(index, *name);
101      array->SetTarget(index, *target);
102      SLOW_DCHECK(array->IsSortedNoDuplicates());
103      return;
104    }
105  }
106
107  // We're gonna need a bigger TransitionArray.
108  Handle<TransitionArray> result = Allocate(
109      map->GetIsolate(), new_nof,
110      Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions));
111
112  // The map's transition array may have shrunk during the allocation above as
113  // it was weakly traversed, though it is guaranteed not to disappear. Trim the
114  // result copy if needed, and recompute variables.
115  DCHECK(IsFullTransitionArray(map->raw_transitions()));
116  DisallowHeapAllocation no_gc;
117  TransitionArray* array = TransitionArray::cast(map->raw_transitions());
118  if (array->number_of_transitions() != number_of_transitions) {
119    DCHECK(array->number_of_transitions() < number_of_transitions);
120
121    number_of_transitions = array->number_of_transitions();
122    new_nof = number_of_transitions;
123
124    insertion_index = kNotFound;
125    int index =
126        is_special_transition
127            ? array->SearchSpecial(Symbol::cast(*name), &insertion_index)
128            : array->Search(details.kind(), *name, details.attributes(),
129                            &insertion_index);
130    if (index == kNotFound) {
131      ++new_nof;
132    } else {
133      insertion_index = index;
134    }
135    DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
136
137    result->Shrink(ToKeyIndex(new_nof));
138    result->SetNumberOfTransitions(new_nof);
139  }
140
141  if (array->HasPrototypeTransitions()) {
142    result->SetPrototypeTransitions(array->GetPrototypeTransitions());
143  }
144
145  DCHECK_NE(kNotFound, insertion_index);
146  for (int i = 0; i < insertion_index; ++i) {
147    result->Set(i, array->GetKey(i), array->GetTarget(i));
148  }
149  result->Set(insertion_index, *name, *target);
150  for (int i = insertion_index; i < number_of_transitions; ++i) {
151    result->Set(i + 1, array->GetKey(i), array->GetTarget(i));
152  }
153
154  SLOW_DCHECK(result->IsSortedNoDuplicates());
155  ReplaceTransitions(map, *result);
156}
157
158
159// static
160Map* TransitionArray::SearchTransition(Map* map, PropertyKind kind, Name* name,
161                                       PropertyAttributes attributes) {
162  DCHECK(name->IsUniqueName());
163  Object* raw_transitions = map->raw_transitions();
164  if (IsSimpleTransition(raw_transitions)) {
165    Map* target = GetSimpleTransition(raw_transitions);
166    Name* key = GetSimpleTransitionKey(target);
167    if (key != name) return nullptr;
168    PropertyDetails details = GetSimpleTargetDetails(target);
169    if (details.attributes() != attributes) return nullptr;
170    if (details.kind() != kind) return nullptr;
171    return target;
172  }
173  if (IsFullTransitionArray(raw_transitions)) {
174    TransitionArray* transitions = TransitionArray::cast(raw_transitions);
175    int transition = transitions->Search(kind, name, attributes);
176    if (transition == kNotFound) return nullptr;
177    return transitions->GetTarget(transition);
178  }
179  return NULL;
180}
181
182
183// static
184Map* TransitionArray::SearchSpecial(Map* map, Symbol* name) {
185  Object* raw_transitions = map->raw_transitions();
186  if (IsFullTransitionArray(raw_transitions)) {
187    TransitionArray* transitions = TransitionArray::cast(raw_transitions);
188    int transition = transitions->SearchSpecial(name);
189    if (transition == kNotFound) return NULL;
190    return transitions->GetTarget(transition);
191  }
192  return NULL;
193}
194
195
196// static
197Handle<Map> TransitionArray::FindTransitionToField(Handle<Map> map,
198                                                   Handle<Name> name) {
199  DCHECK(name->IsUniqueName());
200  DisallowHeapAllocation no_gc;
201  Map* target = SearchTransition(*map, kData, *name, NONE);
202  if (target == NULL) return Handle<Map>::null();
203  PropertyDetails details = target->GetLastDescriptorDetails();
204  DCHECK_EQ(NONE, details.attributes());
205  if (details.location() != kField) return Handle<Map>::null();
206  DCHECK_EQ(kData, details.kind());
207  return Handle<Map>(target);
208}
209
210
211// static
212Handle<String> TransitionArray::ExpectedTransitionKey(Handle<Map> map) {
213  DisallowHeapAllocation no_gc;
214  Object* raw_transition = map->raw_transitions();
215  if (!IsSimpleTransition(raw_transition)) return Handle<String>::null();
216  Map* target = GetSimpleTransition(raw_transition);
217  PropertyDetails details = GetSimpleTargetDetails(target);
218  if (details.location() != kField) return Handle<String>::null();
219  DCHECK_EQ(kData, details.kind());
220  if (details.attributes() != NONE) return Handle<String>::null();
221  Name* name = GetSimpleTransitionKey(target);
222  if (!name->IsString()) return Handle<String>::null();
223  return Handle<String>(String::cast(name));
224}
225
226
227// static
228bool TransitionArray::CanHaveMoreTransitions(Handle<Map> map) {
229  if (map->is_dictionary_map()) return false;
230  Object* raw_transitions = map->raw_transitions();
231  if (IsFullTransitionArray(raw_transitions)) {
232    TransitionArray* transitions = TransitionArray::cast(raw_transitions);
233    return transitions->number_of_transitions() < kMaxNumberOfTransitions;
234  }
235  return true;
236}
237
238
239// static
240bool TransitionArray::CompactPrototypeTransitionArray(FixedArray* array) {
241  const int header = kProtoTransitionHeaderSize;
242  int number_of_transitions = NumberOfPrototypeTransitions(array);
243  if (number_of_transitions == 0) {
244    // Empty array cannot be compacted.
245    return false;
246  }
247  int new_number_of_transitions = 0;
248  for (int i = 0; i < number_of_transitions; i++) {
249    Object* cell = array->get(header + i);
250    if (!WeakCell::cast(cell)->cleared()) {
251      if (new_number_of_transitions != i) {
252        array->set(header + new_number_of_transitions, cell);
253      }
254      new_number_of_transitions++;
255    }
256  }
257  // Fill slots that became free with undefined value.
258  for (int i = new_number_of_transitions; i < number_of_transitions; i++) {
259    array->set_undefined(header + i);
260  }
261  if (number_of_transitions != new_number_of_transitions) {
262    SetNumberOfPrototypeTransitions(array, new_number_of_transitions);
263  }
264  return new_number_of_transitions < number_of_transitions;
265}
266
267
268// static
269Handle<FixedArray> TransitionArray::GrowPrototypeTransitionArray(
270    Handle<FixedArray> array, int new_capacity, Isolate* isolate) {
271  // Grow array by factor 2 up to MaxCachedPrototypeTransitions.
272  int capacity = array->length() - kProtoTransitionHeaderSize;
273  new_capacity = Min(kMaxCachedPrototypeTransitions, new_capacity);
274  DCHECK_GT(new_capacity, capacity);
275  int grow_by = new_capacity - capacity;
276  array = isolate->factory()->CopyFixedArrayAndGrow(array, grow_by, TENURED);
277  if (capacity < 0) {
278    // There was no prototype transitions array before, so the size
279    // couldn't be copied. Initialize it explicitly.
280    SetNumberOfPrototypeTransitions(*array, 0);
281  }
282  return array;
283}
284
285
286// static
287int TransitionArray::NumberOfPrototypeTransitionsForTest(Map* map) {
288  FixedArray* transitions = GetPrototypeTransitions(map);
289  CompactPrototypeTransitionArray(transitions);
290  return TransitionArray::NumberOfPrototypeTransitions(transitions);
291}
292
293
294// static
295void TransitionArray::PutPrototypeTransition(Handle<Map> map,
296                                             Handle<Object> prototype,
297                                             Handle<Map> target_map) {
298  DCHECK(HeapObject::cast(*prototype)->map()->IsMap());
299  // Don't cache prototype transition if this map is either shared, or a map of
300  // a prototype.
301  if (map->is_prototype_map()) return;
302  if (map->is_dictionary_map() || !FLAG_cache_prototype_transitions) return;
303
304  const int header = kProtoTransitionHeaderSize;
305
306  Handle<WeakCell> target_cell = Map::WeakCellForMap(target_map);
307
308  Handle<FixedArray> cache(GetPrototypeTransitions(*map));
309  int capacity = cache->length() - header;
310  int transitions = NumberOfPrototypeTransitions(*cache) + 1;
311
312  if (transitions > capacity) {
313    // Grow the array if compacting it doesn't free space.
314    if (!CompactPrototypeTransitionArray(*cache)) {
315      if (capacity == kMaxCachedPrototypeTransitions) return;
316      cache = GrowPrototypeTransitionArray(cache, 2 * transitions,
317                                           map->GetIsolate());
318      SetPrototypeTransitions(map, cache);
319    }
320  }
321
322  // Reload number of transitions as they might have been compacted.
323  int last = NumberOfPrototypeTransitions(*cache);
324  int entry = header + last;
325
326  cache->set(entry, *target_cell);
327  SetNumberOfPrototypeTransitions(*cache, last + 1);
328}
329
330
331// static
332Handle<Map> TransitionArray::GetPrototypeTransition(Handle<Map> map,
333                                                    Handle<Object> prototype) {
334  DisallowHeapAllocation no_gc;
335  FixedArray* cache = GetPrototypeTransitions(*map);
336  int number_of_transitions = NumberOfPrototypeTransitions(cache);
337  for (int i = 0; i < number_of_transitions; i++) {
338    WeakCell* target_cell =
339        WeakCell::cast(cache->get(kProtoTransitionHeaderSize + i));
340    if (!target_cell->cleared() &&
341        Map::cast(target_cell->value())->prototype() == *prototype) {
342      return handle(Map::cast(target_cell->value()));
343    }
344  }
345  return Handle<Map>();
346}
347
348
349// static
350FixedArray* TransitionArray::GetPrototypeTransitions(Map* map) {
351  Object* raw_transitions = map->raw_transitions();
352  Heap* heap = map->GetHeap();
353  if (!IsFullTransitionArray(raw_transitions)) {
354    return heap->empty_fixed_array();
355  }
356  TransitionArray* transitions = TransitionArray::cast(raw_transitions);
357  if (!transitions->HasPrototypeTransitions()) {
358    return heap->empty_fixed_array();
359  }
360  return transitions->GetPrototypeTransitions();
361}
362
363
364// static
365void TransitionArray::SetNumberOfPrototypeTransitions(
366    FixedArray* proto_transitions, int value) {
367  DCHECK(proto_transitions->length() != 0);
368  proto_transitions->set(kProtoTransitionNumberOfEntriesOffset,
369                         Smi::FromInt(value));
370}
371
372
373// static
374int TransitionArray::NumberOfTransitions(Object* raw_transitions) {
375  if (CanStoreSimpleTransition(raw_transitions)) return 0;
376  if (IsSimpleTransition(raw_transitions)) return 1;
377  // Prototype maps don't have transitions.
378  if (raw_transitions->IsPrototypeInfo()) return 0;
379  DCHECK(IsFullTransitionArray(raw_transitions));
380  return TransitionArray::cast(raw_transitions)->number_of_transitions();
381}
382
383
384// static
385int TransitionArray::Capacity(Object* raw_transitions) {
386  if (!IsFullTransitionArray(raw_transitions)) return 1;
387  TransitionArray* t = TransitionArray::cast(raw_transitions);
388  if (t->length() <= kFirstIndex) return 0;
389  return (t->length() - kFirstIndex) / kTransitionSize;
390}
391
392
393// Private static helper functions.
394
395Handle<TransitionArray> TransitionArray::Allocate(Isolate* isolate,
396                                                  int number_of_transitions,
397                                                  int slack) {
398  Handle<FixedArray> array = isolate->factory()->NewTransitionArray(
399      LengthFor(number_of_transitions + slack));
400  array->set(kPrototypeTransitionsIndex, Smi::kZero);
401  array->set(kTransitionLengthIndex, Smi::FromInt(number_of_transitions));
402  return Handle<TransitionArray>::cast(array);
403}
404
405
406// static
407void TransitionArray::ZapTransitionArray(TransitionArray* transitions) {
408  // Do not zap the next link that is used by GC.
409  STATIC_ASSERT(kNextLinkIndex + 1 == kPrototypeTransitionsIndex);
410  MemsetPointer(transitions->data_start() + kPrototypeTransitionsIndex,
411                transitions->GetHeap()->the_hole_value(),
412                transitions->length() - kPrototypeTransitionsIndex);
413  transitions->SetNumberOfTransitions(0);
414}
415
416
417void TransitionArray::ReplaceTransitions(Handle<Map> map,
418                                         Object* new_transitions) {
419  Object* raw_transitions = map->raw_transitions();
420  if (IsFullTransitionArray(raw_transitions)) {
421    TransitionArray* old_transitions = TransitionArray::cast(raw_transitions);
422#ifdef DEBUG
423    CheckNewTransitionsAreConsistent(map, old_transitions, new_transitions);
424    DCHECK(old_transitions != new_transitions);
425#endif
426    // Transition arrays are not shared. When one is replaced, it should not
427    // keep referenced objects alive, so we zap it.
428    // When there is another reference to the array somewhere (e.g. a handle),
429    // not zapping turns from a waste of memory into a source of crashes.
430    ZapTransitionArray(old_transitions);
431  }
432  map->set_raw_transitions(new_transitions);
433}
434
435
436void TransitionArray::SetPrototypeTransitions(
437    Handle<Map> map, Handle<FixedArray> proto_transitions) {
438  EnsureHasFullTransitionArray(map);
439  TransitionArray* transitions = TransitionArray::cast(map->raw_transitions());
440  transitions->SetPrototypeTransitions(*proto_transitions);
441}
442
443
444void TransitionArray::EnsureHasFullTransitionArray(Handle<Map> map) {
445  Object* raw_transitions = map->raw_transitions();
446  if (IsFullTransitionArray(raw_transitions)) return;
447  int nof = IsSimpleTransition(raw_transitions) ? 1 : 0;
448  Handle<TransitionArray> result = Allocate(map->GetIsolate(), nof);
449  DisallowHeapAllocation no_gc;
450  // Reload pointer after the allocation that just happened.
451  raw_transitions = map->raw_transitions();
452  int new_nof = IsSimpleTransition(raw_transitions) ? 1 : 0;
453  if (new_nof != nof) {
454    DCHECK(new_nof == 0);
455    result->Shrink(ToKeyIndex(0));
456    result->SetNumberOfTransitions(0);
457  } else if (nof == 1) {
458    Map* target = GetSimpleTransition(raw_transitions);
459    Name* key = GetSimpleTransitionKey(target);
460    result->Set(0, key, target);
461  }
462  ReplaceTransitions(map, *result);
463}
464
465
466void TransitionArray::TraverseTransitionTreeInternal(Map* map,
467                                                     TraverseCallback callback,
468                                                     void* data) {
469  Object* raw_transitions = map->raw_transitions();
470  if (IsFullTransitionArray(raw_transitions)) {
471    TransitionArray* transitions = TransitionArray::cast(raw_transitions);
472    if (transitions->HasPrototypeTransitions()) {
473      FixedArray* proto_trans = transitions->GetPrototypeTransitions();
474      for (int i = 0; i < NumberOfPrototypeTransitions(proto_trans); ++i) {
475        int index = TransitionArray::kProtoTransitionHeaderSize + i;
476        WeakCell* cell = WeakCell::cast(proto_trans->get(index));
477        if (!cell->cleared()) {
478          TraverseTransitionTreeInternal(Map::cast(cell->value()), callback,
479                                         data);
480        }
481      }
482    }
483    for (int i = 0; i < transitions->number_of_transitions(); ++i) {
484      TraverseTransitionTreeInternal(transitions->GetTarget(i), callback, data);
485    }
486  } else if (IsSimpleTransition(raw_transitions)) {
487    TraverseTransitionTreeInternal(GetSimpleTransition(raw_transitions),
488                                   callback, data);
489  }
490  callback(map, data);
491}
492
493
494#ifdef DEBUG
495void TransitionArray::CheckNewTransitionsAreConsistent(
496    Handle<Map> map, TransitionArray* old_transitions, Object* transitions) {
497  // This function only handles full transition arrays.
498  DCHECK(IsFullTransitionArray(transitions));
499  TransitionArray* new_transitions = TransitionArray::cast(transitions);
500  for (int i = 0; i < old_transitions->number_of_transitions(); i++) {
501    Map* target = old_transitions->GetTarget(i);
502    if (target->instance_descriptors() == map->instance_descriptors()) {
503      Name* key = old_transitions->GetKey(i);
504      int new_target_index;
505      if (TransitionArray::IsSpecialTransition(key)) {
506        new_target_index = new_transitions->SearchSpecial(Symbol::cast(key));
507      } else {
508        PropertyDetails details =
509            TransitionArray::GetTargetDetails(key, target);
510        new_target_index =
511            new_transitions->Search(details.kind(), key, details.attributes());
512      }
513      DCHECK_NE(TransitionArray::kNotFound, new_target_index);
514      DCHECK_EQ(target, new_transitions->GetTarget(new_target_index));
515    }
516  }
517}
518#endif
519
520
521// Private non-static helper functions (operating on full transition arrays).
522
523int TransitionArray::SearchDetails(int transition, PropertyKind kind,
524                                   PropertyAttributes attributes,
525                                   int* out_insertion_index) {
526  int nof_transitions = number_of_transitions();
527  DCHECK(transition < nof_transitions);
528  Name* key = GetKey(transition);
529  for (; transition < nof_transitions && GetKey(transition) == key;
530       transition++) {
531    Map* target = GetTarget(transition);
532    PropertyDetails target_details = GetTargetDetails(key, target);
533
534    int cmp = CompareDetails(kind, attributes, target_details.kind(),
535                             target_details.attributes());
536    if (cmp == 0) {
537      return transition;
538    } else if (cmp < 0) {
539      break;
540    }
541  }
542  if (out_insertion_index != NULL) *out_insertion_index = transition;
543  return kNotFound;
544}
545
546
547int TransitionArray::Search(PropertyKind kind, Name* name,
548                            PropertyAttributes attributes,
549                            int* out_insertion_index) {
550  int transition = SearchName(name, out_insertion_index);
551  if (transition == kNotFound) return kNotFound;
552  return SearchDetails(transition, kind, attributes, out_insertion_index);
553}
554}  // namespace internal
555}  // namespace v8
556