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/objects.h"
     11 #include "src/objects/descriptor-array.h"
     12 #include "src/objects/map.h"
     13 #include "src/objects/name.h"
     14 
     15 // Has to be the last include (doesn't have include guards):
     16 #include "src/objects/object-macros.h"
     17 
     18 namespace v8 {
     19 namespace internal {
     20 
     21 // TransitionsAccessor is a helper class to encapsulate access to the various
     22 // ways a Map can store transitions to other maps in its respective field at
     23 // Map::kTransitionsOrPrototypeInfo.
     24 // It caches state information internally, which becomes stale when a Map's
     25 // transitions storage changes or when a GC cycle clears dead transitions;
     26 // so while a TransitionsAccessor instance can be used for several read-only
     27 // operations in a row (provided no GC happens between them), it must be
     28 // discarded and recreated after "Insert" and "UpdateHandler" operations.
     29 //
     30 // Internal details: a Map's field either holds an in-place weak reference to a
     31 // transition target, or a StoreIC handler for a transitioning store (which in
     32 // turn points to its target map), or a TransitionArray for several target maps
     33 // and/or handlers as well as prototype and ElementsKind transitions.  Property
     34 // details (and in case of inline target storage, the key) are retrieved from
     35 // the target map's descriptor array.  Stored transitions are weak in the GC
     36 // sense: both single transitions stored inline and TransitionArray fields are
     37 // cleared when the map they refer to is not otherwise reachable.
     38 class TransitionsAccessor {
     39  public:
     40   TransitionsAccessor(Isolate* isolate, Map* map, DisallowHeapAllocation* no_gc)
     41       : isolate_(isolate), map_(map) {
     42     Initialize();
     43     USE(no_gc);
     44   }
     45   TransitionsAccessor(Isolate* isolate, Handle<Map> map)
     46       : isolate_(isolate), map_handle_(map), map_(*map) {
     47     Initialize();
     48   }
     49 
     50   // Insert a new transition into |map|'s transition array, extending it
     51   // as necessary.
     52   // Requires the constructor that takes a Handle<Map> to have been used.
     53   // This TransitionsAccessor instance is unusable after this operation.
     54   void Insert(Handle<Name> name, Handle<Map> target, SimpleTransitionFlag flag);
     55 
     56   Map* SearchTransition(Name* name, PropertyKind kind,
     57                         PropertyAttributes attributes);
     58 
     59   Map* SearchSpecial(Symbol* name);
     60   // Returns true for non-property transitions like elements kind, or
     61   // or frozen/sealed transitions.
     62   static bool IsSpecialTransition(ReadOnlyRoots roots, Name* name);
     63 
     64   enum RequestedLocation { kAnyLocation, kFieldOnly };
     65   MaybeHandle<Map> FindTransitionToDataProperty(
     66       Handle<Name> name, RequestedLocation requested_location = kAnyLocation);
     67 
     68   MaybeHandle<Map> FindTransitionToField(Handle<Name> name) {
     69     return FindTransitionToDataProperty(name, kFieldOnly);
     70   }
     71 
     72   Handle<String> ExpectedTransitionKey();
     73   Handle<Map> ExpectedTransitionTarget();
     74 
     75   int NumberOfTransitions();
     76   // The size of transition arrays are limited so they do not end up in large
     77   // object space. Otherwise ClearNonLiveReferences would leak memory while
     78   // applying in-place right trimming.
     79   static const int kMaxNumberOfTransitions = 1024 + 512;
     80   bool CanHaveMoreTransitions();
     81   inline Name* GetKey(int transition_number);
     82   inline Map* GetTarget(int transition_number);
     83   static inline PropertyDetails GetTargetDetails(Name* name, Map* target);
     84 
     85   static bool IsMatchingMap(Map* target, Name* name, PropertyKind kind,
     86                             PropertyAttributes attributes);
     87 
     88   // ===== ITERATION =====
     89   typedef void (*TraverseCallback)(Map* map, void* data);
     90 
     91   // Traverse the transition tree in postorder.
     92   void TraverseTransitionTree(TraverseCallback callback, void* data) {
     93     // Make sure that we do not allocate in the callback.
     94     DisallowHeapAllocation no_allocation;
     95     TraverseTransitionTreeInternal(callback, data, &no_allocation);
     96   }
     97 
     98   // ===== PROTOTYPE TRANSITIONS =====
     99   // When you set the prototype of an object using the __proto__ accessor you
    100   // need a new map for the object (the prototype is stored in the map).  In
    101   // order not to multiply maps unnecessarily we store these as transitions in
    102   // the original map.  That way we can transition to the same map if the same
    103   // prototype is set, rather than creating a new map every time.  The
    104   // transitions are in the form of a map where the keys are prototype objects
    105   // and the values are the maps they transition to.
    106   void PutPrototypeTransition(Handle<Object> prototype, Handle<Map> target_map);
    107   Handle<Map> GetPrototypeTransition(Handle<Object> prototype);
    108 
    109 #if DEBUG || OBJECT_PRINT
    110   void PrintTransitions(std::ostream& os);
    111   static void PrintOneTransition(std::ostream& os, Name* key, Map* target);
    112   void PrintTransitionTree();
    113   void PrintTransitionTree(std::ostream& os, int level,
    114                            DisallowHeapAllocation* no_gc);
    115 #endif
    116 #if DEBUG
    117   void CheckNewTransitionsAreConsistent(TransitionArray* old_transitions,
    118                                         Object* transitions);
    119   bool IsConsistentWithBackPointers();
    120   bool IsSortedNoDuplicates();
    121 #endif
    122 
    123  protected:
    124   // Allow tests to use inheritance to access internals.
    125   enum Encoding {
    126     kPrototypeInfo,
    127     kUninitialized,
    128     kWeakRef,
    129     kFullTransitionArray,
    130   };
    131 
    132   void Reload() {
    133     DCHECK(!map_handle_.is_null());
    134     map_ = *map_handle_;
    135     Initialize();
    136   }
    137 
    138   inline Encoding encoding() {
    139     DCHECK(!needs_reload_);
    140     return encoding_;
    141   }
    142 
    143  private:
    144   friend class MarkCompactCollector;  // For HasSimpleTransitionTo.
    145   friend class TransitionArray;
    146 
    147   static inline PropertyDetails GetSimpleTargetDetails(Map* transition) {
    148     return transition->GetLastDescriptorDetails();
    149   }
    150 
    151   static inline Name* GetSimpleTransitionKey(Map* transition) {
    152     int descriptor = transition->LastAdded();
    153     return transition->instance_descriptors()->GetKey(descriptor);
    154   }
    155 
    156   static inline Map* GetTargetFromRaw(MaybeObject* raw);
    157 
    158   void MarkNeedsReload() {
    159 #if DEBUG
    160     needs_reload_ = true;
    161 #endif
    162   }
    163 
    164   void Initialize();
    165 
    166   inline Map* GetSimpleTransition();
    167   bool HasSimpleTransitionTo(Map* map);
    168 
    169   void ReplaceTransitions(MaybeObject* new_transitions);
    170 
    171   inline Map* GetTargetMapFromWeakRef();
    172 
    173   void EnsureHasFullTransitionArray();
    174   void SetPrototypeTransitions(Handle<WeakFixedArray> proto_transitions);
    175   WeakFixedArray* GetPrototypeTransitions();
    176 
    177   void TraverseTransitionTreeInternal(TraverseCallback callback, void* data,
    178                                       DisallowHeapAllocation* no_gc);
    179 
    180   inline TransitionArray* transitions();
    181 
    182   Isolate* isolate_;
    183   Handle<Map> map_handle_;
    184   Map* map_;
    185   MaybeObject* raw_transitions_;
    186   Encoding encoding_;
    187 #if DEBUG
    188   bool needs_reload_;
    189 #endif
    190 
    191   DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionsAccessor);
    192 };
    193 
    194 // TransitionArrays are fixed arrays used to hold map transitions for property,
    195 // constant, and element changes.
    196 // The TransitionArray class exposes a very low-level interface. Most clients
    197 // should use TransitionsAccessors.
    198 // TransitionArrays have the following format:
    199 // [0] Link to next TransitionArray (for weak handling support) (strong ref)
    200 // [1] Smi(0) or WeakFixedArray of prototype transitions (strong ref)
    201 // [2] Number of transitions (can be zero after trimming)
    202 // [3] First transition key (strong ref)
    203 // [4] First transition target (weak ref)
    204 // ...
    205 // [3 + number of transitions * kTransitionSize]: start of slack
    206 class TransitionArray : public WeakFixedArray {
    207  public:
    208   DECL_CAST(TransitionArray)
    209 
    210   inline WeakFixedArray* GetPrototypeTransitions();
    211   inline bool HasPrototypeTransitions();
    212 
    213   // Accessors for fetching instance transition at transition number.
    214   inline void SetKey(int transition_number, Name* value);
    215   inline Name* GetKey(int transition_number);
    216   inline HeapObjectReference** GetKeySlot(int transition_number);
    217 
    218   inline Map* GetTarget(int transition_number);
    219   inline void SetRawTarget(int transition_number, MaybeObject* target);
    220   inline MaybeObject* GetRawTarget(int transition_number);
    221   inline HeapObjectReference** GetTargetSlot(int transition_number);
    222   inline bool GetTargetIfExists(int transition_number, Isolate* isolate,
    223                                 Map** target);
    224 
    225   // Required for templatized Search interface.
    226   static const int kNotFound = -1;
    227   Name* GetSortedKey(int transition_number) {
    228     return GetKey(transition_number);
    229   }
    230   int GetSortedKeyIndex(int transition_number) { return transition_number; }
    231   inline int number_of_entries() const { return number_of_transitions(); }
    232 #ifdef DEBUG
    233   bool IsSortedNoDuplicates(int valid_entries = -1);
    234 #endif
    235 
    236   void Sort();
    237 
    238   void PrintInternal(std::ostream& os);
    239 
    240   DECL_PRINTER(TransitionArray)
    241   DECL_VERIFIER(TransitionArray)
    242 
    243   // Layout for full transition arrays.
    244   static const int kPrototypeTransitionsIndex = 0;
    245   static const int kTransitionLengthIndex = 1;
    246   static const int kFirstIndex = 2;
    247 
    248   // Layout of map transition entries in full transition arrays.
    249   static const int kEntryKeyIndex = 0;
    250   static const int kEntryTargetIndex = 1;
    251   static const int kEntrySize = 2;
    252 
    253   // Conversion from transition number to array indices.
    254   static int ToKeyIndex(int transition_number) {
    255     return kFirstIndex + (transition_number * kEntrySize) + kEntryKeyIndex;
    256   }
    257 
    258   static int ToTargetIndex(int transition_number) {
    259     return kFirstIndex + (transition_number * kEntrySize) + kEntryTargetIndex;
    260   }
    261 
    262   inline int SearchNameForTesting(Name* name,
    263                                   int* out_insertion_index = nullptr) {
    264     return SearchName(name, out_insertion_index);
    265   }
    266 
    267  private:
    268   friend class Factory;
    269   friend class MarkCompactCollector;
    270   friend class TransitionsAccessor;
    271 
    272   inline void SetNumberOfTransitions(int number_of_transitions);
    273 
    274   inline int Capacity();
    275 
    276   // ===== PROTOTYPE TRANSITIONS =====
    277   // Cache format:
    278   //    0: finger - index of the first free cell in the cache
    279   //    1 + i: target map
    280   static const int kProtoTransitionHeaderSize = 1;
    281   static const int kMaxCachedPrototypeTransitions = 256;
    282 
    283   inline void SetPrototypeTransitions(WeakFixedArray* prototype_transitions);
    284 
    285   static inline int NumberOfPrototypeTransitions(
    286       WeakFixedArray* proto_transitions);
    287   static void SetNumberOfPrototypeTransitions(WeakFixedArray* proto_transitions,
    288                                               int value);
    289 
    290   static const int kProtoTransitionNumberOfEntriesOffset = 0;
    291   STATIC_ASSERT(kProtoTransitionHeaderSize == 1);
    292 
    293   // Returns the fixed array length required to hold number_of_transitions
    294   // transitions.
    295   static int LengthFor(int number_of_transitions) {
    296     return ToKeyIndex(number_of_transitions);
    297   }
    298 
    299   // Search a  transition for a given kind, property name and attributes.
    300   int Search(PropertyKind kind, Name* name, PropertyAttributes attributes,
    301              int* out_insertion_index = nullptr);
    302 
    303   // Search a non-property transition (like elements kind, observe or frozen
    304   // transitions).
    305   inline int SearchSpecial(Symbol* symbol, int* out_insertion_index = nullptr) {
    306     return SearchName(symbol, out_insertion_index);
    307   }
    308   // Search a first transition for a given property name.
    309   inline int SearchName(Name* name, int* out_insertion_index = nullptr);
    310   int SearchDetails(int transition, PropertyKind kind,
    311                     PropertyAttributes attributes, int* out_insertion_index);
    312 
    313   inline int number_of_transitions() const;
    314 
    315   static bool CompactPrototypeTransitionArray(Isolate* isolate,
    316                                               WeakFixedArray* array);
    317 
    318   static Handle<WeakFixedArray> GrowPrototypeTransitionArray(
    319       Handle<WeakFixedArray> array, int new_capacity, Isolate* isolate);
    320 
    321   // Compares two tuples <key, kind, attributes>, returns -1 if
    322   // tuple1 is "less" than tuple2, 0 if tuple1 equal to tuple2 and 1 otherwise.
    323   static inline int CompareKeys(Name* key1, uint32_t hash1, PropertyKind kind1,
    324                                 PropertyAttributes attributes1, Name* key2,
    325                                 uint32_t hash2, PropertyKind kind2,
    326                                 PropertyAttributes attributes2);
    327 
    328   // Compares keys, returns -1 if key1 is "less" than key2,
    329   // 0 if key1 equal to key2 and 1 otherwise.
    330   static inline int CompareNames(Name* key1, uint32_t hash1, Name* key2,
    331                                  uint32_t hash2);
    332 
    333   // Compares two details, returns -1 if details1 is "less" than details2,
    334   // 0 if details1 equal to details2 and 1 otherwise.
    335   static inline int CompareDetails(PropertyKind kind1,
    336                                    PropertyAttributes attributes1,
    337                                    PropertyKind kind2,
    338                                    PropertyAttributes attributes2);
    339 
    340   inline void Set(int transition_number, Name* key, MaybeObject* target);
    341 
    342   void Zap(Isolate* isolate);
    343 
    344   DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
    345 };
    346 
    347 }  // namespace internal
    348 }  // namespace v8
    349 
    350 #include "src/objects/object-macros-undef.h"
    351 
    352 #endif  // V8_TRANSITIONS_H_
    353