transitions.h 6.78 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4 5 6 7

#ifndef V8_TRANSITIONS_H_
#define V8_TRANSITIONS_H_

8
#include "src/checks.h"
9
#include "src/elements-kind.h"
10
#include "src/heap/heap.h"
11 12
#include "src/isolate.h"
#include "src/objects.h"
13 14 15 16 17 18

namespace v8 {
namespace internal {


// TransitionArrays are fixed arrays used to hold map transitions for property,
19 20
// constant, and element changes. They can either be simple transition arrays
// that store a single property transition, or a full transition array that has
21 22 23 24
// prototype transitions and multiple property transitons. The details related
// to property transitions are accessed in the descriptor array of the target
// map. In the case of a simple transition, the key is also read from the
// descriptor array of the target map.
25 26 27 28 29 30 31
//
// The simple format of the these objects is:
// [0] Undefined or back pointer map
// [1] Single transition
//
// The full format is:
// [0] Undefined or back pointer map
32 33
// [1] Smi(0) or fixed array of prototype transitions
// [2] First transition
34 35 36 37
// [length() - kTransitionSize] Last transition
class TransitionArray: public FixedArray {
 public:
  // Accessors for fetching instance transition at transition number.
38 39
  inline Name* GetKey(int transition_number);
  inline void SetKey(int transition_number, Name* value);
40
  inline Object** GetKeySlot(int transition_number);
41 42
  int GetSortedKeyIndex(int transition_number) { return transition_number; }

43
  Name* GetSortedKey(int transition_number) {
44 45
    return GetKey(transition_number);
  }
46

47 48
  inline Map* GetTarget(int transition_number);
  inline void SetTarget(int transition_number, Map* target);
49

50
  inline PropertyDetails GetTargetDetails(int transition_number);
51 52 53

  inline bool HasElementsTransition();

54 55 56 57 58
  inline Object* back_pointer_storage();
  inline void set_back_pointer_storage(
      Object* back_pointer,
      WriteBarrierMode mode = UPDATE_WRITE_BARRIER);

59 60 61 62 63 64
  inline FixedArray* GetPrototypeTransitions();
  inline void SetPrototypeTransitions(
      FixedArray* prototype_transitions,
      WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
  inline Object** GetPrototypeTransitionsSlot();
  inline bool HasPrototypeTransitions();
65 66 67

  // Returns the number of transitions in the array.
  int number_of_transitions() {
68
    if (IsSimpleTransition()) return 1;
69 70 71 72 73 74
    int len = length();
    return len <= kFirstIndex ? 0 : (len - kFirstIndex) / kTransitionSize;
  }

  inline int number_of_entries() { return number_of_transitions(); }

75 76
  // Creates a FullTransitionArray from a SimpleTransitionArray in
  // containing_map.
77
  static Handle<TransitionArray> ExtendToFullTransitionArray(
78
      Handle<Map> containing_map);
79

80 81
  // Create a transition array, copying from the owning map if it already has
  // one, otherwise creating a new one according to flag.
82 83
  // TODO(verwaest): This should not cause an existing transition to be
  // overwritten.
84 85
  static Handle<TransitionArray> CopyInsert(Handle<Map> map,
                                            Handle<Name> name,
86 87
                                            Handle<Map> target,
                                            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 97 98 99 100 101 102 103 104 105 106 107 108 109 110
  bool IsSimpleTransition() {
    return length() == kSimpleTransitionSize &&
        get(kSimpleTransitionTarget)->IsHeapObject() &&
        // The IntrusivePrototypeTransitionIterator may have set the map of the
        // prototype transitions array to a smi. In that case, there are
        // prototype transitions, hence this transition array is a full
        // transition array.
        HeapObject::cast(get(kSimpleTransitionTarget))->map()->IsMap() &&
        get(kSimpleTransitionTarget)->IsMap();
  }

  bool IsFullTransitionArray() {
    return length() > kFirstIndex ||
        (length() == kFirstIndex && !IsSimpleTransition());
  }
111

112 113 114 115 116 117
  // Casting.
  static inline TransitionArray* cast(Object* obj);

  // Constant for denoting key was not found.
  static const int kNotFound = -1;

118
  static const int kBackPointerStorageIndex = 0;
119 120

  // Layout for full transition arrays.
121 122
  static const int kPrototypeTransitionsIndex = 1;
  static const int kFirstIndex = 2;
123

124
  // Layout for simple transition arrays.
125 126
  static const int kSimpleTransitionTarget = 1;
  static const int kSimpleTransitionSize = 2;
127 128 129
  static const int kSimpleTransitionIndex = 0;
  STATIC_ASSERT(kSimpleTransitionIndex != kNotFound);

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 140 141 142
  static const int kTransitionSize = 2;

#ifdef OBJECT_PRINT
  // Print all the transitions.
143
  void PrintTransitions(std::ostream& os);  // NOLINT
144 145 146
#endif

#ifdef DEBUG
147
  bool IsSortedNoDuplicates(int valid_entries = -1);
148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163
  bool IsConsistentWithBackPointers(Map* current_map);
  bool IsEqualTo(TransitionArray* other);
#endif

  // The maximum number of transitions we want in a transition array (should
  // fit in a page).
  static const int kMaxNumberOfTransitions = 1024 + 512;

 private:
  // Conversion from transition number to array indices.
  static int ToKeyIndex(int transition_number) {
    return kFirstIndex +
           (transition_number * kTransitionSize) +
           kTransitionKey;
  }

164
  static int ToTargetIndex(int transition_number) {
165 166
    return kFirstIndex +
           (transition_number * kTransitionSize) +
167
           kTransitionTarget;
168 169
  }

170 171 172 173 174 175 176 177 178
  static Handle<TransitionArray> AllocateSimple(
      Isolate* isolate, Handle<Map> target);

  // Allocate a new transition array with a single entry.
  static Handle<TransitionArray> NewWith(Handle<Map> map,
                                         Handle<Name> name,
                                         Handle<Map> target,
                                         SimpleTransitionFlag flag);

179
  inline void NoIncrementalWriteBarrierSet(int transition_number,
180
                                           Name* key,
181
                                           Map* target);
182

183 184 185 186 187
  // Copy a single transition from the origin array.
  inline void NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
                                                int origin_transition,
                                                int target_transition);

188 189 190 191 192 193 194
  DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
};


} }  // namespace v8::internal

#endif  // V8_TRANSITIONS_H_