transitions.h 12.2 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4 5 6 7

#ifndef V8_TRANSITIONS_H_
#define V8_TRANSITIONS_H_

8
#include "src/checks.h"
9
#include "src/elements-kind.h"
10
#include "src/heap/heap.h"
11 12
#include "src/isolate.h"
#include "src/objects.h"
13 14 15 16 17 18

namespace v8 {
namespace internal {


// TransitionArrays are fixed arrays used to hold map transitions for property,
19 20 21
// constant, and element changes. "Simple" transitions storing only a single
// property transition are stored inline (i.e. the target map is stored
// directly); otherwise a full transition array is used that has
22 23 24 25
// prototype transitions and multiple property transitons. The details related
// to property transitions are accessed in the descriptor array of the target
// map. In the case of a simple transition, the key is also read from the
// descriptor array of the target map.
26
//
27 28
// This class provides a static interface that operates directly on maps
// and handles the distinction between simple and full transitions storage.
29 30
//
// The full format is:
31 32 33 34
// [0] Smi(0) or fixed array of prototype transitions
// [1] Number of transitions
// [2] First transition
// [2 + number of transitions * kTransitionSize]: start of slack
35 36
class TransitionArray: public FixedArray {
 public:
37 38 39 40
  // Insert a new transition into |map|'s transition array, extending it
  // as necessary.
  static void Insert(Handle<Map> map, Handle<Name> name, Handle<Map> target,
                     SimpleTransitionFlag flag);
41

42 43
  static Map* SearchTransition(Map* map, PropertyKind kind, Name* name,
                               PropertyAttributes attributes);
44

45
  static Map* SearchSpecial(Map* map, Symbol* name);
46

47
  static Handle<Map> FindTransitionToField(Handle<Map> map, Handle<Name> name);
48

49
  static Handle<String> ExpectedTransitionKey(Handle<Map> map);
50

51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
  static Handle<Map> ExpectedTransitionTarget(Handle<Map> map) {
    DCHECK(!ExpectedTransitionKey(map).is_null());
    return Handle<Map>(GetSimpleTransition(map->raw_transitions()));
  }
  // Returns true if |raw_transition| can be overwritten with a simple
  // transition (because it's either uninitialized, or has been cleared).
  static inline bool CanStoreSimpleTransition(Object* raw_transition) {
    return raw_transition->IsSmi() ||
           (raw_transition->IsWeakCell() &&
            WeakCell::cast(raw_transition)->cleared());
  }
  static inline bool IsSimpleTransition(Object* raw_transition) {
    DCHECK(!raw_transition->IsWeakCell() ||
           WeakCell::cast(raw_transition)->cleared() ||
           WeakCell::cast(raw_transition)->value()->IsMap());
    return raw_transition->IsWeakCell() &&
           !WeakCell::cast(raw_transition)->cleared();
  }
  static inline Map* GetSimpleTransition(Object* raw_transition) {
    DCHECK(IsSimpleTransition(raw_transition));
71
    DCHECK(raw_transition->IsWeakCell());
72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
    return Map::cast(WeakCell::cast(raw_transition)->value());
  }
  static inline bool IsFullTransitionArray(Object* raw_transitions) {
    return raw_transitions->IsTransitionArray();
  }

  // The size of transition arrays are limited so they do not end up in large
  // object space. Otherwise ClearNonLiveReferences would leak memory while
  // applying in-place right trimming.
  static bool CanHaveMoreTransitions(Handle<Map> map);

  // ===== PROTOTYPE TRANSITIONS =====
  // When you set the prototype of an object using the __proto__ accessor you
  // need a new map for the object (the prototype is stored in the map).  In
  // order not to multiply maps unnecessarily we store these as transitions in
  // the original map.  That way we can transition to the same map if the same
  // prototype is set, rather than creating a new map every time.  The
  // transitions are in the form of a map where the keys are prototype objects
  // and the values are the maps they transition to.
  // Cache format:
  //    0: finger - index of the first free cell in the cache
  //    1 + i: target map
  static const int kMaxCachedPrototypeTransitions = 256;
  static Handle<Map> PutPrototypeTransition(Handle<Map> map,
                                            Handle<Object> prototype,
                                            Handle<Map> target_map);

  static Handle<Map> GetPrototypeTransition(Handle<Map> map,
                                            Handle<Object> prototype);

  static FixedArray* GetPrototypeTransitions(Map* map);

  static int NumberOfPrototypeTransitions(FixedArray* proto_transitions) {
    if (proto_transitions->length() == 0) return 0;
    Object* raw = proto_transitions->get(kProtoTransitionNumberOfEntriesOffset);
    return Smi::cast(raw)->value();
  }

  static void SetNumberOfPrototypeTransitions(FixedArray* proto_transitions,
                                              int value);
112

113 114 115 116 117 118
  inline FixedArray* GetPrototypeTransitions();
  inline void SetPrototypeTransitions(
      FixedArray* prototype_transitions,
      WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
  inline Object** GetPrototypeTransitionsSlot();
  inline bool HasPrototypeTransitions();
119

120
  // ===== ITERATION =====
121

122
  typedef void (*TraverseCallback)(Map* map, void* data);
123

124 125 126 127 128 129
  // Traverse the transition tree in postorder.
  static void TraverseTransitionTree(Map* map, TraverseCallback callback,
                                     void* data) {
    // Make sure that we do not allocate in the callback.
    DisallowHeapAllocation no_allocation;
    TraverseTransitionTreeInternal(map, callback, data);
130 131
  }

132
  // ===== LOW-LEVEL ACCESSORS =====
133

134 135 136 137 138 139
  // Accessors for fetching instance transition at transition number.
  static inline Name* GetKey(Object* raw_transitions, int transition_number);
  inline Name* GetKey(int transition_number);
  inline void SetKey(int transition_number, Name* value);
  inline Object** GetKeySlot(int transition_number);
  int GetSortedKeyIndex(int transition_number) { return transition_number; }
140

141 142
  Name* GetSortedKey(int transition_number) {
    return GetKey(transition_number);
143
  }
144

145 146 147 148
  static inline Map* GetTarget(Object* raw_transitions, int transition_number);
  inline Map* GetTarget(int transition_number);
  inline void SetTarget(int transition_number, Map* target);

149
  static inline PropertyDetails GetTargetDetails(Name* name, Map* target);
150

151 152 153 154
  // Returns the number of transitions in the array.
  static int NumberOfTransitions(Object* raw_transitions);
  // Required for templatized Search interface.
  inline int number_of_entries() { return number_of_transitions(); }
155

156
  inline void SetNumberOfTransitions(int number_of_transitions);
157

158
  static int Capacity(Object* raw_transitions);
159

160 161 162 163
  // Casting.
  static inline TransitionArray* cast(Object* obj);

  static const int kTransitionSize = 2;
164
  static const int kProtoTransitionHeaderSize = 1;
165

166
#if defined(DEBUG) || defined(OBJECT_PRINT)
167 168 169
  // For our gdb macros, we should perhaps change these in the future.
  void Print();

170
  // Print all the transitions.
171 172
  static void PrintTransitions(std::ostream& os, Object* transitions,
                               bool print_header = true);  // NOLINT
173
#endif
174

175
#ifdef DEBUG
176
  bool IsSortedNoDuplicates(int valid_entries = -1);
177 178
  static bool IsSortedNoDuplicates(Map* map);
  static bool IsConsistentWithBackPointers(Map* map);
179 180 181 182

  // Returns true for a non-property transitions like elements kind, observed
  // or frozen transitions.
  static inline bool IsSpecialTransition(Name* name);
183 184
#endif

185 186 187
  // Constant for denoting key was not found.
  static const int kNotFound = -1;

188 189 190 191
  // The maximum number of transitions we want in a transition array (should
  // fit in a page).
  static const int kMaxNumberOfTransitions = 1024 + 512;

192
 private:
193 194 195 196 197 198 199 200 201 202 203 204 205
  // Layout for full transition arrays.
  static const int kPrototypeTransitionsIndex = 0;
  static const int kTransitionLengthIndex = 1;
  static const int kFirstIndex = 2;

  // Layout of map transition entries in full transition arrays.
  static const int kTransitionKey = 0;
  static const int kTransitionTarget = 1;
  STATIC_ASSERT(kTransitionSize == 2);

  static const int kProtoTransitionNumberOfEntriesOffset = 0;
  STATIC_ASSERT(kProtoTransitionHeaderSize == 1);

206 207 208 209 210 211 212
  // Conversion from transition number to array indices.
  static int ToKeyIndex(int transition_number) {
    return kFirstIndex +
           (transition_number * kTransitionSize) +
           kTransitionKey;
  }

213
  static int ToTargetIndex(int transition_number) {
214 215
    return kFirstIndex +
           (transition_number * kTransitionSize) +
216
           kTransitionTarget;
217 218
  }

219 220 221 222 223 224 225 226 227 228 229 230 231
  // Returns the fixed array length required to hold number_of_transitions
  // transitions.
  static int LengthFor(int number_of_transitions) {
    return ToKeyIndex(number_of_transitions);
  }

  // Allocates a TransitionArray.
  static Handle<TransitionArray> Allocate(Isolate* isolate,
                                          int number_of_transitions,
                                          int slack = 0);

  static void EnsureHasFullTransitionArray(Handle<Map> map);
  static void ReplaceTransitions(Handle<Map> map, Object* new_transitions);
232

233 234 235
  // Search a  transition for a given kind, property name and attributes.
  int Search(PropertyKind kind, Name* name, PropertyAttributes attributes,
             int* out_insertion_index = NULL);
236

237 238 239 240 241
  // Search a non-property transition (like elements kind, observe or frozen
  // transitions).
  inline int SearchSpecial(Symbol* symbol, int* out_insertion_index = NULL) {
    return SearchName(symbol, out_insertion_index);
  }
242 243
  // Search a first transition for a given property name.
  inline int SearchName(Name* name, int* out_insertion_index = NULL);
244
  int SearchDetails(int transition, PropertyKind kind,
245 246
                    PropertyAttributes attributes, int* out_insertion_index);

247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267
  int number_of_transitions() {
    if (length() < kFirstIndex) return 0;
    return Smi::cast(get(kTransitionLengthIndex))->value();
  }

  static inline PropertyDetails GetSimpleTargetDetails(Map* transition) {
    return transition->GetLastDescriptorDetails();
  }

  static inline Name* GetSimpleTransitionKey(Map* transition) {
    int descriptor = transition->LastAdded();
    return transition->instance_descriptors()->GetKey(descriptor);
  }

  static void TraverseTransitionTreeInternal(Map* map,
                                             TraverseCallback callback,
                                             void* data);

  static void SetPrototypeTransitions(Handle<Map> map,
                                      Handle<FixedArray> proto_transitions);

268
  // Compares two tuples <key, kind, attributes>, returns -1 if
269
  // tuple1 is "less" than tuple2, 0 if tuple1 equal to tuple2 and 1 otherwise.
270
  static inline int CompareKeys(Name* key1, uint32_t hash1, PropertyKind kind1,
271
                                PropertyAttributes attributes1, Name* key2,
272
                                uint32_t hash2, PropertyKind kind2,
273 274 275 276 277 278 279 280 281
                                PropertyAttributes attributes2);

  // Compares keys, returns -1 if key1 is "less" than key2,
  // 0 if key1 equal to key2 and 1 otherwise.
  static inline int CompareNames(Name* key1, uint32_t hash1, Name* key2,
                                 uint32_t hash2);

  // Compares two details, returns -1 if details1 is "less" than details2,
  // 0 if details1 equal to details2 and 1 otherwise.
282
  static inline int CompareDetails(PropertyKind kind1,
283
                                   PropertyAttributes attributes1,
284
                                   PropertyKind kind2,
285 286
                                   PropertyAttributes attributes2);

287
  inline void NoIncrementalWriteBarrierSet(int transition_number,
288
                                           Name* key,
289
                                           Map* target);
290

291 292 293 294 295
  // Copy a single transition from the origin array.
  inline void NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
                                                int origin_transition,
                                                int target_transition);

296 297 298 299 300 301
#ifdef DEBUG
  static void CheckNewTransitionsAreConsistent(Handle<Map> map,
                                               TransitionArray* old_transitions,
                                               Object* transitions);
#endif

302 303 304 305 306 307 308
  DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
};


} }  // namespace v8::internal

#endif  // V8_TRANSITIONS_H_