1// Copyright 2012 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#ifndef V8_TRANSITIONS_H_
29#define V8_TRANSITIONS_H_
30
31#include "elements-kind.h"
32#include "heap.h"
33#include "isolate.h"
34#include "objects.h"
35#include "v8checks.h"
36
37namespace v8 {
38namespace internal {
39
40
41// TransitionArrays are fixed arrays used to hold map transitions for property,
42// constant, and element changes. They can either be simple transition arrays
43// that store a single property transition, or a full transition array that has
44// prototype transitions and multiple property transitons. The details related
45// to property transitions are accessed in the descriptor array of the target
46// map. In the case of a simple transition, the key is also read from the
47// descriptor array of the target map.
48//
49// The simple format of the these objects is:
50// [0] Undefined or back pointer map
51// [1] Single transition
52//
53// The full format is:
54// [0] Undefined or back pointer map
55// [1] Smi(0) or fixed array of prototype transitions
56// [2] First transition
57// [length() - kTransitionSize] Last transition
58class TransitionArray: public FixedArray {
59 public:
60  // Accessors for fetching instance transition at transition number.
61  inline Name* GetKey(int transition_number);
62  inline void SetKey(int transition_number, Name* value);
63  inline Object** GetKeySlot(int transition_number);
64  int GetSortedKeyIndex(int transition_number) { return transition_number; }
65
66  Name* GetSortedKey(int transition_number) {
67    return GetKey(transition_number);
68  }
69
70  inline Map* GetTarget(int transition_number);
71  inline void SetTarget(int transition_number, Map* target);
72
73  inline PropertyDetails GetTargetDetails(int transition_number);
74
75  inline bool HasElementsTransition();
76
77  inline Object* back_pointer_storage();
78  inline void set_back_pointer_storage(
79      Object* back_pointer,
80      WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
81
82  inline FixedArray* GetPrototypeTransitions();
83  inline void SetPrototypeTransitions(
84      FixedArray* prototype_transitions,
85      WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
86  inline Object** GetPrototypeTransitionsSlot();
87  inline bool HasPrototypeTransitions();
88  inline HeapObject* UncheckedPrototypeTransitions();
89
90  // Returns the number of transitions in the array.
91  int number_of_transitions() {
92    if (IsSimpleTransition()) return 1;
93    int len = length();
94    return len <= kFirstIndex ? 0 : (len - kFirstIndex) / kTransitionSize;
95  }
96
97  inline int number_of_entries() { return number_of_transitions(); }
98
99  // Allocate a new transition array with a single entry.
100  static MUST_USE_RESULT MaybeObject* NewWith(
101      SimpleTransitionFlag flag,
102      Name* key,
103      Map* target,
104      Object* back_pointer);
105
106  MUST_USE_RESULT MaybeObject* ExtendToFullTransitionArray();
107
108  // Copy the transition array, inserting a new transition.
109  // TODO(verwaest): This should not cause an existing transition to be
110  // overwritten.
111  MUST_USE_RESULT MaybeObject* CopyInsert(Name* name, Map* target);
112
113  // Copy a single transition from the origin array.
114  inline void NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
115                                                int origin_transition,
116                                                int target_transition);
117
118  // Search a transition for a given property name.
119  inline int Search(Name* name);
120
121  // Allocates a TransitionArray.
122  MUST_USE_RESULT static MaybeObject* Allocate(int number_of_transitions);
123
124  bool IsSimpleTransition() {
125    return length() == kSimpleTransitionSize &&
126        get(kSimpleTransitionTarget)->IsHeapObject() &&
127        // The IntrusivePrototypeTransitionIterator may have set the map of the
128        // prototype transitions array to a smi. In that case, there are
129        // prototype transitions, hence this transition array is a full
130        // transition array.
131        HeapObject::cast(get(kSimpleTransitionTarget))->map()->IsMap() &&
132        get(kSimpleTransitionTarget)->IsMap();
133  }
134
135  bool IsFullTransitionArray() {
136    return length() > kFirstIndex ||
137        (length() == kFirstIndex && !IsSimpleTransition());
138  }
139
140  // Casting.
141  static inline TransitionArray* cast(Object* obj);
142
143  // Constant for denoting key was not found.
144  static const int kNotFound = -1;
145
146  static const int kBackPointerStorageIndex = 0;
147
148  // Layout for full transition arrays.
149  static const int kPrototypeTransitionsIndex = 1;
150  static const int kFirstIndex = 2;
151
152  // Layout for simple transition arrays.
153  static const int kSimpleTransitionTarget = 1;
154  static const int kSimpleTransitionSize = 2;
155  static const int kSimpleTransitionIndex = 0;
156  STATIC_ASSERT(kSimpleTransitionIndex != kNotFound);
157
158  static const int kBackPointerStorageOffset = FixedArray::kHeaderSize;
159
160  // Layout for the full transition array header.
161  static const int kPrototypeTransitionsOffset = kBackPointerStorageOffset +
162                                                 kPointerSize;
163
164  // Layout of map transition entries in full transition arrays.
165  static const int kTransitionKey = 0;
166  static const int kTransitionTarget = 1;
167  static const int kTransitionSize = 2;
168
169#ifdef OBJECT_PRINT
170  // Print all the transitions.
171  inline void PrintTransitions() {
172    PrintTransitions(stdout);
173  }
174  void PrintTransitions(FILE* out);
175#endif
176
177#ifdef DEBUG
178  bool IsSortedNoDuplicates(int valid_entries = -1);
179  bool IsConsistentWithBackPointers(Map* current_map);
180  bool IsEqualTo(TransitionArray* other);
181#endif
182
183  // The maximum number of transitions we want in a transition array (should
184  // fit in a page).
185  static const int kMaxNumberOfTransitions = 1024 + 512;
186
187 private:
188  // Conversion from transition number to array indices.
189  static int ToKeyIndex(int transition_number) {
190    return kFirstIndex +
191           (transition_number * kTransitionSize) +
192           kTransitionKey;
193  }
194
195  static int ToTargetIndex(int transition_number) {
196    return kFirstIndex +
197           (transition_number * kTransitionSize) +
198           kTransitionTarget;
199  }
200
201  inline void NoIncrementalWriteBarrierSet(int transition_number,
202                                           Name* key,
203                                           Map* target);
204
205  DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
206};
207
208
209} }  // namespace v8::internal
210
211#endif  // V8_TRANSITIONS_H_
212