src/transitions.h

   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
  14 namespace v8 {
  15 namespace internal {
  16
  17
  18 // TransitionArrays are fixed arrays used to hold map transitions for property,
  19 // constant, and element changes. "Simple" transitions storing only a single
  20 // property transition are stored inline (i.e. the target map is stored
  21 // directly); otherwise a full transition array is used that has
  22 // prototype transitions and multiple property transitons. The details related
  23 // to property transitions are accessed in the descriptor array of the target
  24 // map. In the case of a simple transition, the key is also read from the
  25 // descriptor array of the target map.
  26 //
  27 // This class provides a static interface that operates directly on maps
  28 // and handles the distinction between simple and full transitions storage.
  29 //
  30 // The full format is:
  31 // [0] Smi(0) or fixed array of prototype transitions
  32 // [1] Number of transitions
  33 // [2] First transition
  34 // [2 + number of transitions * kTransitionSize]: start of slack
  35 class TransitionArray: public FixedArray {
  36  public:
  37   // Insert a new transition into |map|'s transition array, extending it
  38   // as necessary.
  39   static void Insert(Handle<Map> map, Handle<Name> name, Handle<Map> target,
  40                      SimpleTransitionFlag flag);
  41
  42   static Map* SearchTransition(Map* map, PropertyKind kind, Name* name,
  43                                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   static Handle<Map> ExpectedTransitionTarget(Handle<Map> map) {
  52     DCHECK(!ExpectedTransitionKey(map).is_null());
  53     return Handle<Map>(GetSimpleTransition(map->raw_transitions()));
  54   }
  55   // Returns true if |raw_transition| can be overwritten with a simple
  56   // transition (because it's either uninitialized, or has been cleared).
  57   static inline bool CanStoreSimpleTransition(Object* raw_transition) {
  58     return raw_transition->IsSmi() ||
  59            (raw_transition->IsWeakCell() &&
  60             WeakCell::cast(raw_transition)->cleared());
  61   }
  62   static inline bool IsSimpleTransition(Object* raw_transition) {
  63     DCHECK(!raw_transition->IsWeakCell() ||
  64            WeakCell::cast(raw_transition)->cleared() ||
  65            WeakCell::cast(raw_transition)->value()->IsMap());
  66     return raw_transition->IsWeakCell() &&
  67            !WeakCell::cast(raw_transition)->cleared();
  68   }
  69   static inline Map* GetSimpleTransition(Object* raw_transition) {
  70     DCHECK(IsSimpleTransition(raw_transition));
  71     DCHECK(raw_transition->IsWeakCell());
  72     return Map::cast(WeakCell::cast(raw_transition)->value());
  73   }
  74   static inline bool IsFullTransitionArray(Object* raw_transitions) {
  75     return raw_transitions->IsTransitionArray();
  76   }
  77
  78   // The size of transition arrays are limited so they do not end up in large
  79   // object space. Otherwise ClearNonLiveReferences would leak memory while
  80   // applying in-place right trimming.
  81   static bool CanHaveMoreTransitions(Handle<Map> map);
  82
  83   // ===== PROTOTYPE TRANSITIONS =====
  84   // When you set the prototype of an object using the __proto__ accessor you
  85   // need a new map for the object (the prototype is stored in the map).  In
  86   // order not to multiply maps unnecessarily we store these as transitions in
  87   // the original map.  That way we can transition to the same map if the same
  88   // prototype is set, rather than creating a new map every time.  The
  89   // transitions are in the form of a map where the keys are prototype objects
  90   // and the values are the maps they transition to.
  91   // Cache format:
  92   //    0: finger - index of the first free cell in the cache
  93   //    1 + i: target map
  94   static const int kMaxCachedPrototypeTransitions = 256;
  95   static void PutPrototypeTransition(Handle<Map> map, Handle<Object> prototype,
  96                                      Handle<Map> target_map);
  97
  98   static Handle<Map> GetPrototypeTransition(Handle<Map> map,
  99                                             Handle<Object> prototype);
 100
 101   static FixedArray* GetPrototypeTransitions(Map* map);
 102
 103   static int NumberOfPrototypeTransitions(FixedArray* proto_transitions) {
 104     if (proto_transitions->length() == 0) return 0;
 105     Object* raw = proto_transitions->get(kProtoTransitionNumberOfEntriesOffset);
 106     return Smi::cast(raw)->value();
 107   }
 108
 109   static void SetNumberOfPrototypeTransitions(FixedArray* proto_transitions,
 110                                               int value);
 111
 112   inline FixedArray* GetPrototypeTransitions();
 113   inline void SetPrototypeTransitions(
 114       FixedArray* prototype_transitions,
 115       WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
 116   inline Object** GetPrototypeTransitionsSlot();
 117   inline bool HasPrototypeTransitions();
 118
 119   // ===== ITERATION =====
 120
 121   typedef void (*TraverseCallback)(Map* map, void* data);
 122
 123   // Traverse the transition tree in postorder.
 124   static void TraverseTransitionTree(Map* map, TraverseCallback callback,
 125                                      void* data) {
 126     // Make sure that we do not allocate in the callback.
 127     DisallowHeapAllocation no_allocation;
 128     TraverseTransitionTreeInternal(map, callback, data);
 129   }
 130
 131   // ===== LOW-LEVEL ACCESSORS =====
 132
 133   // Accessors for fetching instance transition at transition number.
 134   static inline Name* GetKey(Object* raw_transitions, int transition_number);
 135   inline Name* GetKey(int transition_number);
 136   inline void SetKey(int transition_number, Name* value);
 137   inline Object** GetKeySlot(int transition_number);
 138   int GetSortedKeyIndex(int transition_number) { return transition_number; }
 139
 140   Name* GetSortedKey(int transition_number) {
 141     return GetKey(transition_number);
 142   }
 143
 144   static inline Map* GetTarget(Object* raw_transitions, int transition_number);
 145   inline Map* GetTarget(int transition_number);
 146   inline void SetTarget(int transition_number, Map* target);
 147
 148   static inline PropertyDetails GetTargetDetails(Name* name, Map* target);
 149
 150   // Returns the number of transitions in the array.
 151   static int NumberOfTransitions(Object* raw_transitions);
 152   // Required for templatized Search interface.
 153   inline int number_of_entries() { return number_of_transitions(); }
 154
 155   inline void SetNumberOfTransitions(int number_of_transitions);
 156
 157   static int Capacity(Object* raw_transitions);
 158
 159   // Casting.
 160   static inline TransitionArray* cast(Object* obj);
 161
 162   static const int kTransitionSize = 2;
 163   static const int kProtoTransitionHeaderSize = 1;
 164
 165 #if defined(DEBUG) || defined(OBJECT_PRINT)
 166   // For our gdb macros, we should perhaps change these in the future.
 167   void Print();
 168
 169   // Print all the transitions.
 170   static void PrintTransitions(std::ostream& os, Object* transitions,
 171                                bool print_header = true);  // NOLINT
 172 #endif
 173
 174 #ifdef DEBUG
 175   bool IsSortedNoDuplicates(int valid_entries = -1);
 176   static bool IsSortedNoDuplicates(Map* map);
 177   static bool IsConsistentWithBackPointers(Map* map);
 178
 179   // Returns true for a non-property transitions like elements kind, observed
 180   // or frozen transitions.
 181   static inline bool IsSpecialTransition(Name* name);
 182 #endif
 183
 184   // Constant for denoting key was not found.
 185   static const int kNotFound = -1;
 186
 187   // The maximum number of transitions we want in a transition array (should
 188   // fit in a page).
 189   static const int kMaxNumberOfTransitions = 1024 + 512;
 190
 191  private:
 192   // Layout for full transition arrays.
 193   static const int kPrototypeTransitionsIndex = 0;
 194   static const int kTransitionLengthIndex = 1;
 195   static const int kFirstIndex = 2;
 196
 197   // Layout of map transition entries in full transition arrays.
 198   static const int kTransitionKey = 0;
 199   static const int kTransitionTarget = 1;
 200   STATIC_ASSERT(kTransitionSize == 2);
 201
 202   static const int kProtoTransitionNumberOfEntriesOffset = 0;
 203   STATIC_ASSERT(kProtoTransitionHeaderSize == 1);
 204
 205   // Conversion from transition number to array indices.
 206   static int ToKeyIndex(int transition_number) {
 207     return kFirstIndex +
 208            (transition_number * kTransitionSize) +
 209            kTransitionKey;
 210   }
 211
 212   static int ToTargetIndex(int transition_number) {
 213     return kFirstIndex +
 214            (transition_number * kTransitionSize) +
 215            kTransitionTarget;
 216   }
 217
 218   // Returns the fixed array length required to hold number_of_transitions
 219   // transitions.
 220   static int LengthFor(int number_of_transitions) {
 221     return ToKeyIndex(number_of_transitions);
 222   }
 223
 224   // Allocates a TransitionArray.
 225   static Handle<TransitionArray> Allocate(Isolate* isolate,
 226                                           int number_of_transitions,
 227                                           int slack = 0);
 228
 229   static void EnsureHasFullTransitionArray(Handle<Map> map);
 230   static void ReplaceTransitions(Handle<Map> map, Object* new_transitions);
 231
 232   // Search a  transition for a given kind, property name and attributes.
 233   int Search(PropertyKind kind, Name* name, PropertyAttributes attributes,
 234              int* out_insertion_index = NULL);
 235
 236   // Search a non-property transition (like elements kind, observe or frozen
 237   // transitions).
 238   inline int SearchSpecial(Symbol* symbol, int* out_insertion_index = NULL) {
 239     return SearchName(symbol, out_insertion_index);
 240   }
 241   // Search a first transition for a given property name.
 242   inline int SearchName(Name* name, int* out_insertion_index = NULL);
 243   int SearchDetails(int transition, PropertyKind kind,
 244                     PropertyAttributes attributes, int* out_insertion_index);
 245
 246   int number_of_transitions() {
 247     if (length() < kFirstIndex) return 0;
 248     return Smi::cast(get(kTransitionLengthIndex))->value();
 249   }
 250
 251   static inline PropertyDetails GetSimpleTargetDetails(Map* transition) {
 252     return transition->GetLastDescriptorDetails();
 253   }
 254
 255   static inline Name* GetSimpleTransitionKey(Map* transition) {
 256     int descriptor = transition->LastAdded();
 257     return transition->instance_descriptors()->GetKey(descriptor);
 258   }
 259
 260   static void TraverseTransitionTreeInternal(Map* map,
 261                                              TraverseCallback callback,
 262                                              void* data);
 263
 264   static void SetPrototypeTransitions(Handle<Map> map,
 265                                       Handle<FixedArray> proto_transitions);
 266
 267   // Compares two tuples <key, kind, attributes>, returns -1 if
 268   // tuple1 is "less" than tuple2, 0 if tuple1 equal to tuple2 and 1 otherwise.
 269   static inline int CompareKeys(Name* key1, uint32_t hash1, PropertyKind kind1,
 270                                 PropertyAttributes attributes1, Name* key2,
 271                                 uint32_t hash2, PropertyKind kind2,
 272                                 PropertyAttributes attributes2);
 273
 274   // Compares keys, returns -1 if key1 is "less" than key2,
 275   // 0 if key1 equal to key2 and 1 otherwise.
 276   static inline int CompareNames(Name* key1, uint32_t hash1, Name* key2,
 277                                  uint32_t hash2);
 278
 279   // Compares two details, returns -1 if details1 is "less" than details2,
 280   // 0 if details1 equal to details2 and 1 otherwise.
 281   static inline int CompareDetails(PropertyKind kind1,
 282                                    PropertyAttributes attributes1,
 283                                    PropertyKind kind2,
 284                                    PropertyAttributes attributes2);
 285
 286   inline void NoIncrementalWriteBarrierSet(int transition_number,
 287                                            Name* key,
 288                                            Map* target);
 289
 290   // Copy a single transition from the origin array.
 291   inline void NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
 292                                                 int origin_transition,
 293                                                 int target_transition);
 294
 295 #ifdef DEBUG
 296   static void CheckNewTransitionsAreConsistent(Handle<Map> map,
 297                                                TransitionArray* old_transitions,
 298                                                Object* transitions);
 299 #endif
 300
 301   DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
 302 };
 303
 304
 305 } }  // namespace v8::internal
 306
 307 #endif  // V8_TRANSITIONS_H_