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