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/checks.h"
9#include "src/elements-kind.h"
10#include "src/heap/heap.h"
11#include "src/isolate.h"
12#include "src/objects.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  void PrintTransitions(OStream& os);  // NOLINT
144#endif
145
146#ifdef DEBUG
147  bool IsSortedNoDuplicates(int valid_entries = -1);
148  bool IsConsistentWithBackPointers(Map* current_map);
149  bool IsEqualTo(TransitionArray* other);
150#endif
151
152  // The maximum number of transitions we want in a transition array (should
153  // fit in a page).
154  static const int kMaxNumberOfTransitions = 1024 + 512;
155
156 private:
157  // Conversion from transition number to array indices.
158  static int ToKeyIndex(int transition_number) {
159    return kFirstIndex +
160           (transition_number * kTransitionSize) +
161           kTransitionKey;
162  }
163
164  static int ToTargetIndex(int transition_number) {
165    return kFirstIndex +
166           (transition_number * kTransitionSize) +
167           kTransitionTarget;
168  }
169
170  static Handle<TransitionArray> AllocateSimple(
171      Isolate* isolate, Handle<Map> target);
172
173  // Allocate a new transition array with a single entry.
174  static Handle<TransitionArray> NewWith(Handle<Map> map,
175                                         Handle<Name> name,
176                                         Handle<Map> target,
177                                         SimpleTransitionFlag flag);
178
179  inline void NoIncrementalWriteBarrierSet(int transition_number,
180                                           Name* key,
181                                           Map* target);
182
183  // Copy a single transition from the origin array.
184  inline void NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
185                                                int origin_transition,
186                                                int target_transition);
187
188  DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
189};
190
191
192} }  // namespace v8::internal
193
194#endif  // V8_TRANSITIONS_H_
195