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. 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   void PrintTransitions(OStream& os);  // NOLINT
    144 #endif
    145 
    146 #ifdef DEBUG
    147   bool IsSortedNoDuplicates(int valid_entries = -1);
    148   bool IsConsistentWithBackPointers(Map* current_map);
    149   bool IsEqualTo(TransitionArray* other);
    150 #endif
    151 
    152   // The maximum number of transitions we want in a transition array (should
    153   // fit in a page).
    154   static const int kMaxNumberOfTransitions = 1024 + 512;
    155 
    156  private:
    157   // Conversion from transition number to array indices.
    158   static int ToKeyIndex(int transition_number) {
    159     return kFirstIndex +
    160            (transition_number * kTransitionSize) +
    161            kTransitionKey;
    162   }
    163 
    164   static int ToTargetIndex(int transition_number) {
    165     return kFirstIndex +
    166            (transition_number * kTransitionSize) +
    167            kTransitionTarget;
    168   }
    169 
    170   static Handle<TransitionArray> AllocateSimple(
    171       Isolate* isolate, Handle<Map> target);
    172 
    173   // Allocate a new transition array with a single entry.
    174   static Handle<TransitionArray> NewWith(Handle<Map> map,
    175                                          Handle<Name> name,
    176                                          Handle<Map> target,
    177                                          SimpleTransitionFlag flag);
    178 
    179   inline void NoIncrementalWriteBarrierSet(int transition_number,
    180                                            Name* key,
    181                                            Map* target);
    182 
    183   // Copy a single transition from the origin array.
    184   inline void NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
    185                                                 int origin_transition,
    186                                                 int target_transition);
    187 
    188   DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
    189 };
    190 
    191 
    192 } }  // namespace v8::internal
    193 
    194 #endif  // V8_TRANSITIONS_H_
    195