LCOV - code coverage report
Current view: top level - src - transitions.h (source / functions) Hit Total Coverage
Test: app.info Lines: 30 30 100.0 %
Date: 2017-04-26 Functions: 9 9 100.0 %

          Line data    Source code
       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/isolate.h"
      11             : #include "src/objects.h"
      12             : #include "src/objects/descriptor-array.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        4563 :   static MaybeHandle<Map> SearchTransition(Handle<Map> map, PropertyKind kind,
      45             :                                            Handle<Name> name,
      46             :                                            PropertyAttributes attributes) {
      47        4563 :     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    28257472 :   static Handle<Map> ExpectedTransitionTarget(Handle<Map> map) {
      60             :     DCHECK(!ExpectedTransitionKey(map).is_null());
      61    28257472 :     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    15958181 :   static inline bool CanStoreSimpleTransition(Object* raw_transition) {
      66    20260452 :     return raw_transition->IsSmi() ||
      67     2752233 :            (raw_transition->IsWeakCell() &&
      68    15958181 :             WeakCell::cast(raw_transition)->cleared());
      69             :   }
      70    98027782 :   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   142603018 :     return raw_transition->IsWeakCell() &&
      75    98027777 :            !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    68987763 :   static inline bool IsFullTransitionArray(Object* raw_transitions) {
      83    68987757 :     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     4408752 :   static int NumberOfPrototypeTransitions(FixedArray* proto_transitions) {
     112     4408752 :     if (proto_transitions->length() == 0) return 0;
     113             :     Object* raw = proto_transitions->get(kProtoTransitionNumberOfEntriesOffset);
     114     4204120 :     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      186071 :     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    37408779 :   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   182312443 :            (transition_number * kTransitionSize) +
     228   182312443 :            kTransitionKey;
     229             :   }
     230             : 
     231             :   static int ToTargetIndex(int transition_number) {
     232             :     return kFirstIndex +
     233    79755160 :            (transition_number * kTransitionSize) +
     234    79755160 :            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     2868077 :     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    60797490 :   int number_of_transitions() {
     266    60797490 :     if (length() < kFirstIndex) return 0;
     267    60797490 :     return Smi::cast(get(kTransitionLengthIndex))->value();
     268             :   }
     269             : 
     270    38578052 :   static inline PropertyDetails GetSimpleTargetDetails(Map* transition) {
     271    38578053 :     return transition->GetLastDescriptorDetails();
     272             :   }
     273             : 
     274    38790520 :   static inline Name* GetSimpleTransitionKey(Map* transition) {
     275             :     int descriptor = transition->LastAdded();
     276    38790520 :     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_

Generated by: LCOV version 1.10