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#ifndef V8_TRANSITIONS_H_
6#define V8_TRANSITIONS_H_
7
8#include "src/elements-kind.h"
9#include "src/heap.h"
10#include "src/isolate.h"
11#include "src/objects.h"
12#include "src/v8checks.h"
13
14namespace v8 {
15namespace internal {
16
17
18// TransitionArrays are fixed arrays used to hold map transitions for property,
19// constant, and element changes. They can either be simple transition arrays
20// that store a single property transition, or a full transition array that has
21// prototype transitions and multiple property transitons. The details related
22// to property transitions are accessed in the descriptor array of the target
23// map. In the case of a simple transition, the key is also read from the
24// descriptor array of the target map.
25//
26// The simple format of the these objects is:
27// [0] Undefined or back pointer map
28// [1] Single transition
29//
30// The full format is:
31// [0] Undefined or back pointer map
32// [1] Smi(0) or fixed array of prototype transitions
33// [2] First transition
34// [length() - kTransitionSize] Last transition
35class TransitionArray: public FixedArray {
36 public:
37  // Accessors for fetching instance transition at transition number.
38  inline Name* GetKey(int transition_number);
39  inline void SetKey(int transition_number, Name* value);
40  inline Object** GetKeySlot(int transition_number);
41  int GetSortedKeyIndex(int transition_number) { return transition_number; }
42
43  Name* GetSortedKey(int transition_number) {
44    return GetKey(transition_number);
45  }
46
47  inline Map* GetTarget(int transition_number);
48  inline void SetTarget(int transition_number, Map* target);
49
50  inline PropertyDetails GetTargetDetails(int transition_number);
51
52  inline bool HasElementsTransition();
53
54  inline Object* back_pointer_storage();
55  inline void set_back_pointer_storage(
56      Object* back_pointer,
57      WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
58
59  inline FixedArray* GetPrototypeTransitions();
60  inline void SetPrototypeTransitions(
61      FixedArray* prototype_transitions,
62      WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
63  inline Object** GetPrototypeTransitionsSlot();
64  inline bool HasPrototypeTransitions();
65
66  // Returns the number of transitions in the array.
67  int number_of_transitions() {
68    if (IsSimpleTransition()) return 1;
69    int len = length();
70    return len <= kFirstIndex ? 0 : (len - kFirstIndex) / kTransitionSize;
71  }
72
73  inline int number_of_entries() { return number_of_transitions(); }
74
75  // Creates a FullTransitionArray from a SimpleTransitionArray in
76  // containing_map.
77  static Handle<TransitionArray> ExtendToFullTransitionArray(
78      Handle<Map> containing_map);
79
80  // Create a transition array, copying from the owning map if it already has
81  // one, otherwise creating a new one according to flag.
82  // TODO(verwaest): This should not cause an existing transition to be
83  // overwritten.
84  static Handle<TransitionArray> CopyInsert(Handle<Map> map,
85                                            Handle<Name> name,
86                                            Handle<Map> target,
87                                            SimpleTransitionFlag flag);
88
89  // Search a transition for a given property name.
90  inline int Search(Name* name);
91
92  // Allocates a TransitionArray.
93  static Handle<TransitionArray> Allocate(
94      Isolate* isolate, int number_of_transitions);
95
96  bool IsSimpleTransition() {
97    return length() == kSimpleTransitionSize &&
98        get(kSimpleTransitionTarget)->IsHeapObject() &&
99        // The IntrusivePrototypeTransitionIterator may have set the map of the
100        // prototype transitions array to a smi. In that case, there are
101        // prototype transitions, hence this transition array is a full
102        // transition array.
103        HeapObject::cast(get(kSimpleTransitionTarget))->map()->IsMap() &&
104        get(kSimpleTransitionTarget)->IsMap();
105  }
106
107  bool IsFullTransitionArray() {
108    return length() > kFirstIndex ||
109        (length() == kFirstIndex && !IsSimpleTransition());
110  }
111
112  // Casting.
113  static inline TransitionArray* cast(Object* obj);
114
115  // Constant for denoting key was not found.
116  static const int kNotFound = -1;
117
118  static const int kBackPointerStorageIndex = 0;
119
120  // Layout for full transition arrays.
121  static const int kPrototypeTransitionsIndex = 1;
122  static const int kFirstIndex = 2;
123
124  // Layout for simple transition arrays.
125  static const int kSimpleTransitionTarget = 1;
126  static const int kSimpleTransitionSize = 2;
127  static const int kSimpleTransitionIndex = 0;
128  STATIC_ASSERT(kSimpleTransitionIndex != kNotFound);
129
130  static const int kBackPointerStorageOffset = FixedArray::kHeaderSize;
131
132  // Layout for the full transition array header.
133  static const int kPrototypeTransitionsOffset = kBackPointerStorageOffset +
134                                                 kPointerSize;
135
136  // Layout of map transition entries in full transition arrays.
137  static const int kTransitionKey = 0;
138  static const int kTransitionTarget = 1;
139  static const int kTransitionSize = 2;
140
141#ifdef OBJECT_PRINT
142  // Print all the transitions.
143  inline void PrintTransitions() {
144    PrintTransitions(stdout);
145  }
146  void PrintTransitions(FILE* out);
147#endif
148
149#ifdef DEBUG
150  bool IsSortedNoDuplicates(int valid_entries = -1);
151  bool IsConsistentWithBackPointers(Map* current_map);
152  bool IsEqualTo(TransitionArray* other);
153#endif
154
155  // The maximum number of transitions we want in a transition array (should
156  // fit in a page).
157  static const int kMaxNumberOfTransitions = 1024 + 512;
158
159 private:
160  // Conversion from transition number to array indices.
161  static int ToKeyIndex(int transition_number) {
162    return kFirstIndex +
163           (transition_number * kTransitionSize) +
164           kTransitionKey;
165  }
166
167  static int ToTargetIndex(int transition_number) {
168    return kFirstIndex +
169           (transition_number * kTransitionSize) +
170           kTransitionTarget;
171  }
172
173  static Handle<TransitionArray> AllocateSimple(
174      Isolate* isolate, Handle<Map> target);
175
176  // Allocate a new transition array with a single entry.
177  static Handle<TransitionArray> NewWith(Handle<Map> map,
178                                         Handle<Name> name,
179                                         Handle<Map> target,
180                                         SimpleTransitionFlag flag);
181
182  inline void NoIncrementalWriteBarrierSet(int transition_number,
183                                           Name* key,
184                                           Map* target);
185
186  // Copy a single transition from the origin array.
187  inline void NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
188                                                int origin_transition,
189                                                int target_transition);
190
191  DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
192};
193
194
195} }  // namespace v8::internal
196
197#endif  // V8_TRANSITIONS_H_
198