deps/v8/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. 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] Number of transitions
  34 // [3] First transition
  35 // [3 + number of transitions * kTransitionSize]: start of slack
  36 class TransitionArray: public FixedArray {
  37  public:
  38   // Accessors for fetching instance transition at transition number.
  39   inline Name* GetKey(int transition_number);
  40   inline void SetKey(int transition_number, Name* value);
  41   inline Object** GetKeySlot(int transition_number);
  42   int GetSortedKeyIndex(int transition_number) { return transition_number; }
  43
  44   Name* GetSortedKey(int transition_number) {
  45     return GetKey(transition_number);
  46   }
  47
  48   inline Map* GetTarget(int transition_number);
  49   inline void SetTarget(int transition_number, Map* target);
  50
  51   inline PropertyDetails GetTargetDetails(int transition_number);
  52   inline Object* GetTargetValue(int transition_number);
  53
  54   inline bool HasElementsTransition();
  55
  56   inline Object* back_pointer_storage();
  57   inline void set_back_pointer_storage(
  58       Object* back_pointer,
  59       WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
  60
  61   inline FixedArray* GetPrototypeTransitions();
  62   inline void SetPrototypeTransitions(
  63       FixedArray* prototype_transitions,
  64       WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
  65   inline Object** GetPrototypeTransitionsSlot();
  66   inline bool HasPrototypeTransitions();
  67
  68   // Returns the number of transitions in the array.
  69   int number_of_transitions() {
  70     if (IsSimpleTransition()) return 1;
  71     if (length() <= kFirstIndex) return 0;
  72     return Smi::cast(get(kTransitionLengthIndex))->value();
  73   }
  74
  75   int number_of_transitions_storage() {
  76     if (IsSimpleTransition()) return 1;
  77     if (length() <= kFirstIndex) return 0;
  78     return (length() - kFirstIndex) / kTransitionSize;
  79   }
  80
  81   int NumberOfSlackTransitions() {
  82     return number_of_transitions_storage() - number_of_transitions();
  83   }
  84
  85   inline void SetNumberOfTransitions(int number_of_transitions);
  86   inline int number_of_entries() { return number_of_transitions(); }
  87
  88   // Creates a FullTransitionArray from a SimpleTransitionArray in
  89   // containing_map.
  90   static Handle<TransitionArray> ExtendToFullTransitionArray(
  91       Handle<Map> containing_map);
  92
  93   // Return a transition array, using the array from the owning map if it
  94   // already has one (copying into a larger array if necessary), otherwise
  95   // creating a new one according to flag.
  96   // TODO(verwaest): This should not cause an existing transition to be
  97   // overwritten.
  98   static Handle<TransitionArray> Insert(Handle<Map> map, Handle<Name> name,
  99                                         Handle<Map> target,
 100                                         SimpleTransitionFlag flag);
 101   // Search a  transition for a given kind, property name and attributes.
 102   int Search(PropertyKind kind, Name* name, PropertyAttributes attributes,
 103              int* out_insertion_index = NULL);
 104
 105   // Search a non-property transition (like elements kind, observe or frozen
 106   // transitions).
 107   inline int SearchSpecial(Symbol* symbol, int* out_insertion_index = NULL) {
 108     return SearchName(symbol, out_insertion_index);
 109   }
 110
 111   static inline PropertyDetails GetTargetDetails(Name* name, Map* target);
 112
 113   // Allocates a TransitionArray.
 114   static Handle<TransitionArray> Allocate(Isolate* isolate,
 115                                           int number_of_transitions,
 116                                           int slack = 0);
 117
 118   bool IsSimpleTransition() {
 119     return length() == kSimpleTransitionSize &&
 120         get(kSimpleTransitionTarget)->IsHeapObject() &&
 121         // The IntrusivePrototypeTransitionIterator may have set the map of the
 122         // prototype transitions array to a smi. In that case, there are
 123         // prototype transitions, hence this transition array is a full
 124         // transition array.
 125         HeapObject::cast(get(kSimpleTransitionTarget))->map()->IsMap() &&
 126         get(kSimpleTransitionTarget)->IsMap();
 127   }
 128
 129   bool IsFullTransitionArray() {
 130     return length() > kFirstIndex ||
 131         (length() == kFirstIndex && !IsSimpleTransition());
 132   }
 133
 134   // Casting.
 135   static inline TransitionArray* cast(Object* obj);
 136
 137   // Constant for denoting key was not found.
 138   static const int kNotFound = -1;
 139
 140   static const int kBackPointerStorageIndex = 0;
 141
 142   // Layout for full transition arrays.
 143   static const int kPrototypeTransitionsIndex = 1;
 144   static const int kTransitionLengthIndex = 2;
 145   static const int kFirstIndex = 3;
 146
 147   // Layout for simple transition arrays.
 148   static const int kSimpleTransitionTarget = 1;
 149   static const int kSimpleTransitionSize = 2;
 150   static const int kSimpleTransitionIndex = 0;
 151   STATIC_ASSERT(kSimpleTransitionIndex != kNotFound);
 152
 153   static const int kBackPointerStorageOffset = FixedArray::kHeaderSize;
 154
 155   // Layout for the full transition array header.
 156   static const int kPrototypeTransitionsOffset = kBackPointerStorageOffset +
 157                                                  kPointerSize;
 158   static const int kTransitionLengthOffset =
 159       kPrototypeTransitionsOffset + kPointerSize;
 160
 161   // Layout of map transition entries in full transition arrays.
 162   static const int kTransitionKey = 0;
 163   static const int kTransitionTarget = 1;
 164   static const int kTransitionSize = 2;
 165
 166 #if defined(DEBUG) || defined(OBJECT_PRINT)
 167   // For our gdb macros, we should perhaps change these in the future.
 168   void Print();
 169
 170   // Print all the transitions.
 171   void PrintTransitions(std::ostream& os, bool print_header = true);  // NOLINT
 172 #endif
 173
 174 #ifdef DEBUG
 175   bool IsSortedNoDuplicates(int valid_entries = -1);
 176   bool IsConsistentWithBackPointers(Map* current_map);
 177   bool IsEqualTo(TransitionArray* other);
 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   // The maximum number of transitions we want in a transition array (should
 185   // fit in a page).
 186   static const int kMaxNumberOfTransitions = 1024 + 512;
 187
 188   // Returns the fixed array length required to hold number_of_transitions
 189   // transitions.
 190   static int LengthFor(int number_of_transitions) {
 191     return ToKeyIndex(number_of_transitions);
 192   }
 193
 194  private:
 195   // Conversion from transition number to array indices.
 196   static int ToKeyIndex(int transition_number) {
 197     return kFirstIndex +
 198            (transition_number * kTransitionSize) +
 199            kTransitionKey;
 200   }
 201
 202   static int ToTargetIndex(int transition_number) {
 203     return kFirstIndex +
 204            (transition_number * kTransitionSize) +
 205            kTransitionTarget;
 206   }
 207
 208   static Handle<TransitionArray> AllocateSimple(
 209       Isolate* isolate, Handle<Map> target);
 210
 211   // Allocate a new transition array with a single entry.
 212   static Handle<TransitionArray> NewWith(Handle<Map> map,
 213                                          Handle<Name> name,
 214                                          Handle<Map> target,
 215                                          SimpleTransitionFlag flag);
 216
 217   // Search a first transition for a given property name.
 218   inline int SearchName(Name* name, int* out_insertion_index = NULL);
 219   int SearchDetails(int transition, PropertyKind kind,
 220                     PropertyAttributes attributes, int* out_insertion_index);
 221
 222   // Compares two tuples <key, kind, attributes>, returns -1 if
 223   // tuple1 is "less" than tuple2, 0 if tuple1 equal to tuple2 and 1 otherwise.
 224   static inline int CompareKeys(Name* key1, uint32_t hash1, PropertyKind kind1,
 225                                 PropertyAttributes attributes1, Name* key2,
 226                                 uint32_t hash2, PropertyKind kind2,
 227                                 PropertyAttributes attributes2);
 228
 229   // Compares keys, returns -1 if key1 is "less" than key2,
 230   // 0 if key1 equal to key2 and 1 otherwise.
 231   static inline int CompareNames(Name* key1, uint32_t hash1, Name* key2,
 232                                  uint32_t hash2);
 233
 234   // Compares two details, returns -1 if details1 is "less" than details2,
 235   // 0 if details1 equal to details2 and 1 otherwise.
 236   static inline int CompareDetails(PropertyKind kind1,
 237                                    PropertyAttributes attributes1,
 238                                    PropertyKind kind2,
 239                                    PropertyAttributes attributes2);
 240
 241   inline void NoIncrementalWriteBarrierSet(int transition_number,
 242                                            Name* key,
 243                                            Map* target);
 244
 245   // Copy a single transition from the origin array.
 246   inline void NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
 247                                                 int origin_transition,
 248                                                 int target_transition);
 249
 250   DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
 251 };
 252
 253
 254 } }  // namespace v8::internal
 255
 256 #endif  // V8_TRANSITIONS_H_