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/elements-kind.h"
      9 #include "src/heap.h"
     10 #include "src/isolate.h"
     11 #include "src/objects.h"
     12 #include "src/v8checks.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] First transition
     34 // [length() - kTransitionSize] Last transition
     35 class TransitionArray: public FixedArray {
     36  public:
     37   // Accessors for fetching instance transition at transition number.
     38   inline Name* GetKey(int transition_number);
     39   inline void SetKey(int transition_number, Name* value);
     40   inline Object** GetKeySlot(int transition_number);
     41   int GetSortedKeyIndex(int transition_number) { return transition_number; }
     42 
     43   Name* GetSortedKey(int transition_number) {
     44     return GetKey(transition_number);
     45   }
     46 
     47   inline Map* GetTarget(int transition_number);
     48   inline void SetTarget(int transition_number, Map* target);
     49 
     50   inline PropertyDetails GetTargetDetails(int transition_number);
     51 
     52   inline bool HasElementsTransition();
     53 
     54   inline Object* back_pointer_storage();
     55   inline void set_back_pointer_storage(
     56       Object* back_pointer,
     57       WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
     58 
     59   inline FixedArray* GetPrototypeTransitions();
     60   inline void SetPrototypeTransitions(
     61       FixedArray* prototype_transitions,
     62       WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
     63   inline Object** GetPrototypeTransitionsSlot();
     64   inline bool HasPrototypeTransitions();
     65 
     66   // Returns the number of transitions in the array.
     67   int number_of_transitions() {
     68     if (IsSimpleTransition()) return 1;
     69     int len = length();
     70     return len <= kFirstIndex ? 0 : (len - kFirstIndex) / kTransitionSize;
     71   }
     72 
     73   inline int number_of_entries() { return number_of_transitions(); }
     74 
     75   // Creates a FullTransitionArray from a SimpleTransitionArray in
     76   // containing_map.
     77   static Handle<TransitionArray> ExtendToFullTransitionArray(
     78       Handle<Map> containing_map);
     79 
     80   // Create a transition array, copying from the owning map if it already has
     81   // one, otherwise creating a new one according to flag.
     82   // TODO(verwaest): This should not cause an existing transition to be
     83   // overwritten.
     84   static Handle<TransitionArray> CopyInsert(Handle<Map> map,
     85                                             Handle<Name> name,
     86                                             Handle<Map> target,
     87                                             SimpleTransitionFlag flag);
     88 
     89   // Search a transition for a given property name.
     90   inline int Search(Name* name);
     91 
     92   // Allocates a TransitionArray.
     93   static Handle<TransitionArray> Allocate(
     94       Isolate* isolate, int number_of_transitions);
     95 
     96   bool IsSimpleTransition() {
     97     return length() == kSimpleTransitionSize &&
     98         get(kSimpleTransitionTarget)->IsHeapObject() &&
     99         // The IntrusivePrototypeTransitionIterator may have set the map of the
    100         // prototype transitions array to a smi. In that case, there are
    101         // prototype transitions, hence this transition array is a full
    102         // transition array.
    103         HeapObject::cast(get(kSimpleTransitionTarget))->map()->IsMap() &&
    104         get(kSimpleTransitionTarget)->IsMap();
    105   }
    106 
    107   bool IsFullTransitionArray() {
    108     return length() > kFirstIndex ||
    109         (length() == kFirstIndex && !IsSimpleTransition());
    110   }
    111 
    112   // Casting.
    113   static inline TransitionArray* cast(Object* obj);
    114 
    115   // Constant for denoting key was not found.
    116   static const int kNotFound = -1;
    117 
    118   static const int kBackPointerStorageIndex = 0;
    119 
    120   // Layout for full transition arrays.
    121   static const int kPrototypeTransitionsIndex = 1;
    122   static const int kFirstIndex = 2;
    123 
    124   // Layout for simple transition arrays.
    125   static const int kSimpleTransitionTarget = 1;
    126   static const int kSimpleTransitionSize = 2;
    127   static const int kSimpleTransitionIndex = 0;
    128   STATIC_ASSERT(kSimpleTransitionIndex != kNotFound);
    129 
    130   static const int kBackPointerStorageOffset = FixedArray::kHeaderSize;
    131 
    132   // Layout for the full transition array header.
    133   static const int kPrototypeTransitionsOffset = kBackPointerStorageOffset +
    134                                                  kPointerSize;
    135 
    136   // Layout of map transition entries in full transition arrays.
    137   static const int kTransitionKey = 0;
    138   static const int kTransitionTarget = 1;
    139   static const int kTransitionSize = 2;
    140 
    141 #ifdef OBJECT_PRINT
    142   // Print all the transitions.
    143   inline void PrintTransitions() {
    144     PrintTransitions(stdout);
    145   }
    146   void PrintTransitions(FILE* out);
    147 #endif
    148 
    149 #ifdef DEBUG
    150   bool IsSortedNoDuplicates(int valid_entries = -1);
    151   bool IsConsistentWithBackPointers(Map* current_map);
    152   bool IsEqualTo(TransitionArray* other);
    153 #endif
    154 
    155   // The maximum number of transitions we want in a transition array (should
    156   // fit in a page).
    157   static const int kMaxNumberOfTransitions = 1024 + 512;
    158 
    159  private:
    160   // Conversion from transition number to array indices.
    161   static int ToKeyIndex(int transition_number) {
    162     return kFirstIndex +
    163            (transition_number * kTransitionSize) +
    164            kTransitionKey;
    165   }
    166 
    167   static int ToTargetIndex(int transition_number) {
    168     return kFirstIndex +
    169            (transition_number * kTransitionSize) +
    170            kTransitionTarget;
    171   }
    172 
    173   static Handle<TransitionArray> AllocateSimple(
    174       Isolate* isolate, Handle<Map> target);
    175 
    176   // Allocate a new transition array with a single entry.
    177   static Handle<TransitionArray> NewWith(Handle<Map> map,
    178                                          Handle<Name> name,
    179                                          Handle<Map> target,
    180                                          SimpleTransitionFlag flag);
    181 
    182   inline void NoIncrementalWriteBarrierSet(int transition_number,
    183                                            Name* key,
    184                                            Map* target);
    185 
    186   // Copy a single transition from the origin array.
    187   inline void NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
    188                                                 int origin_transition,
    189                                                 int target_transition);
    190 
    191   DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
    192 };
    193 
    194 
    195 } }  // namespace v8::internal
    196 
    197 #endif  // V8_TRANSITIONS_H_
    198