transitions.h 12.9 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 10
#include "src/elements-kind.h"
#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 16 17
// Has to be the last include (doesn't have include guards):
#include "src/objects/object-macros.h"

18 19 20
namespace v8 {
namespace internal {

21 22 23 24 25 26 27 28
// TransitionsAccessor is a helper class to encapsulate access to the various
// ways a Map can store transitions to other maps in its respective field at
// Map::kTransitionsOrPrototypeInfo.
// It caches state information internally, which becomes stale when a Map's
// transitions storage changes or when a GC cycle clears dead transitions;
// so while a TransitionsAccessor instance can be used for several read-only
// operations in a row (provided no GC happens between them), it must be
// discarded and recreated after "Insert" and "UpdateHandler" operations.
29
//
30 31 32 33 34 35 36 37
// Internal details: a Map's field either holds an in-place weak reference to a
// transition target, or a StoreIC handler for a transitioning store (which in
// turn points to its target map), or a TransitionArray for several target maps
// and/or handlers as well as prototype and ElementsKind transitions.  Property
// details (and in case of inline target storage, the key) are retrieved from
// the target map's descriptor array.  Stored transitions are weak in the GC
// sense: both single transitions stored inline and TransitionArray fields are
// cleared when the map they refer to is not otherwise reachable.
38
class TransitionsAccessor {
39
 public:
40 41
  TransitionsAccessor(Isolate* isolate, Map* map, DisallowHeapAllocation* no_gc)
      : isolate_(isolate), map_(map) {
42 43 44
    Initialize();
    USE(no_gc);
  }
45 46
  TransitionsAccessor(Isolate* isolate, Handle<Map> map)
      : isolate_(isolate), map_handle_(map), map_(*map) {
47 48 49
    Initialize();
  }

50 51
  // Insert a new transition into |map|'s transition array, extending it
  // as necessary.
52 53 54
  // Requires the constructor that takes a Handle<Map> to have been used.
  // This TransitionsAccessor instance is unusable after this operation.
  void Insert(Handle<Name> name, Handle<Map> target, SimpleTransitionFlag flag);
55

56 57
  Map* SearchTransition(Name* name, PropertyKind kind,
                        PropertyAttributes attributes);
58

59 60 61
  Map* SearchSpecial(Symbol* name);
  // Returns true for non-property transitions like elements kind, or
  // or frozen/sealed transitions.
62
  static bool IsSpecialTransition(ReadOnlyRoots roots, Name* name);
63

64 65 66 67 68 69 70
  enum RequestedLocation { kAnyLocation, kFieldOnly };
  MaybeHandle<Map> FindTransitionToDataProperty(
      Handle<Name> name, RequestedLocation requested_location = kAnyLocation);

  MaybeHandle<Map> FindTransitionToField(Handle<Name> name) {
    return FindTransitionToDataProperty(name, kFieldOnly);
  }
71 72 73

  Handle<String> ExpectedTransitionKey();
  Handle<Map> ExpectedTransitionTarget();
74

75
  int NumberOfTransitions();
76 77 78
  // The size of transition arrays are limited so they do not end up in large
  // object space. Otherwise ClearNonLiveReferences would leak memory while
  // applying in-place right trimming.
79 80 81 82
  static const int kMaxNumberOfTransitions = 1024 + 512;
  bool CanHaveMoreTransitions();
  inline Name* GetKey(int transition_number);
  inline Map* GetTarget(int transition_number);
83
  static inline PropertyDetails GetTargetDetails(Name* name, Map* target);
84

85 86
  static bool IsMatchingMap(Map* target, Name* name, PropertyKind kind,
                            PropertyAttributes attributes);
87 88 89 90 91 92 93 94 95 96

  // ===== ITERATION =====
  typedef void (*TraverseCallback)(Map* map, void* data);

  // Traverse the transition tree in postorder.
  void TraverseTransitionTree(TraverseCallback callback, void* data) {
    // Make sure that we do not allocate in the callback.
    DisallowHeapAllocation no_allocation;
    TraverseTransitionTreeInternal(callback, data, &no_allocation);
  }
97 98 99 100 101 102 103 104 105

  // ===== PROTOTYPE TRANSITIONS =====
  // When you set the prototype of an object using the __proto__ accessor you
  // need a new map for the object (the prototype is stored in the map).  In
  // order not to multiply maps unnecessarily we store these as transitions in
  // the original map.  That way we can transition to the same map if the same
  // prototype is set, rather than creating a new map every time.  The
  // transitions are in the form of a map where the keys are prototype objects
  // and the values are the maps they transition to.
106 107 108 109 110
  void PutPrototypeTransition(Handle<Object> prototype, Handle<Map> target_map);
  Handle<Map> GetPrototypeTransition(Handle<Object> prototype);

#if DEBUG || OBJECT_PRINT
  void PrintTransitions(std::ostream& os);
111
  static void PrintOneTransition(std::ostream& os, Name* key, Map* target);
112 113 114 115 116 117 118 119
  void PrintTransitionTree();
  void PrintTransitionTree(std::ostream& os, int level,
                           DisallowHeapAllocation* no_gc);
#endif
#if DEBUG
  void CheckNewTransitionsAreConsistent(TransitionArray* old_transitions,
                                        Object* transitions);
  bool IsConsistentWithBackPointers();
120
  bool IsSortedNoDuplicates();
121
#endif
122

123 124 125 126 127
 protected:
  // Allow tests to use inheritance to access internals.
  enum Encoding {
    kPrototypeInfo,
    kUninitialized,
128
    kWeakRef,
129 130 131 132 133 134 135 136
    kFullTransitionArray,
  };

  void Reload() {
    DCHECK(!map_handle_.is_null());
    map_ = *map_handle_;
    Initialize();
  }
137

138 139 140
  inline Encoding encoding() {
    DCHECK(!needs_reload_);
    return encoding_;
141 142
  }

143 144 145
 private:
  friend class MarkCompactCollector;  // For HasSimpleTransitionTo.
  friend class TransitionArray;
146

147 148 149
  static inline PropertyDetails GetSimpleTargetDetails(Map* transition) {
    return transition->GetLastDescriptorDetails();
  }
150

151 152 153 154
  static inline Name* GetSimpleTransitionKey(Map* transition) {
    int descriptor = transition->LastAdded();
    return transition->instance_descriptors()->GetKey(descriptor);
  }
155

156
  static inline Map* GetTargetFromRaw(MaybeObject* raw);
157

158 159 160 161
  void MarkNeedsReload() {
#if DEBUG
    needs_reload_ = true;
#endif
162 163
  }

164 165 166
  void Initialize();

  inline Map* GetSimpleTransition();
167
  bool HasSimpleTransitionTo(Map* map);
168

169
  void ReplaceTransitions(MaybeObject* new_transitions);
170

171 172
  inline Map* GetTargetMapFromWeakRef();

173
  void EnsureHasFullTransitionArray();
174 175
  void SetPrototypeTransitions(Handle<WeakFixedArray> proto_transitions);
  WeakFixedArray* GetPrototypeTransitions();
176 177 178 179 180 181

  void TraverseTransitionTreeInternal(TraverseCallback callback, void* data,
                                      DisallowHeapAllocation* no_gc);

  inline TransitionArray* transitions();

182
  Isolate* isolate_;
183 184
  Handle<Map> map_handle_;
  Map* map_;
185
  MaybeObject* raw_transitions_;
186 187 188 189 190 191 192 193 194 195 196 197 198
  Encoding encoding_;
#if DEBUG
  bool needs_reload_;
#endif

  DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionsAccessor);
};

// TransitionArrays are fixed arrays used to hold map transitions for property,
// constant, and element changes.
// The TransitionArray class exposes a very low-level interface. Most clients
// should use TransitionsAccessors.
// 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 203
// [3] First transition key (strong ref)
// [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 214
  // Accessors for fetching instance transition at transition number.
  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 220 221
  inline void SetRawTarget(int transition_number, MaybeObject* target);
  inline MaybeObject* GetRawTarget(int transition_number);
  inline HeapObjectReference** GetTargetSlot(int transition_number);
222 223
  inline bool GetTargetIfExists(int transition_number, Isolate* isolate,
                                Map** target);
224

225
  // Required for templatized Search interface.
226 227 228 229 230
  static const int kNotFound = -1;
  Name* GetSortedKey(int transition_number) {
    return GetKey(transition_number);
  }
  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 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266
  // Layout for full transition arrays.
  static const int kPrototypeTransitionsIndex = 0;
  static const int kTransitionLengthIndex = 1;
  static const int kFirstIndex = 2;

  // Layout of map transition entries in full transition arrays.
  static const int kEntryKeyIndex = 0;
  static const int kEntryTargetIndex = 1;
  static const int kEntrySize = 2;

  // Conversion from transition number to array indices.
  static int ToKeyIndex(int transition_number) {
    return kFirstIndex + (transition_number * kEntrySize) + kEntryKeyIndex;
  }

  static int ToTargetIndex(int transition_number) {
    return kFirstIndex + (transition_number * kEntrySize) + kEntryTargetIndex;
  }

  inline int SearchNameForTesting(Name* name,
                                  int* out_insertion_index = nullptr) {
    return SearchName(name, out_insertion_index);
  }

267
 private:
268
  friend class Factory;
269 270
  friend class MarkCompactCollector;
  friend class TransitionsAccessor;
271

272
  inline void SetNumberOfTransitions(int number_of_transitions);
273

274
  inline int Capacity();
275

276 277 278 279 280 281 282
  // ===== PROTOTYPE TRANSITIONS =====
  // Cache format:
  //    0: finger - index of the first free cell in the cache
  //    1 + i: target map
  static const int kProtoTransitionHeaderSize = 1;
  static const int kMaxCachedPrototypeTransitions = 256;

283
  inline void SetPrototypeTransitions(WeakFixedArray* prototype_transitions);
284

285 286 287
  static inline int NumberOfPrototypeTransitions(
      WeakFixedArray* proto_transitions);
  static void SetNumberOfPrototypeTransitions(WeakFixedArray* proto_transitions,
288
                                              int value);
289

290 291 292 293 294 295 296 297 298 299
  static const int kProtoTransitionNumberOfEntriesOffset = 0;
  STATIC_ASSERT(kProtoTransitionHeaderSize == 1);

  // Returns the fixed array length required to hold number_of_transitions
  // transitions.
  static int LengthFor(int number_of_transitions) {
    return ToKeyIndex(number_of_transitions);
  }

  // Search a  transition for a given kind, property name and attributes.
300 301
  int Search(PropertyKind kind, Name* name, PropertyAttributes attributes,
             int* out_insertion_index = nullptr);
302

303 304
  // Search a non-property transition (like elements kind, observe or frozen
  // transitions).
305
  inline int SearchSpecial(Symbol* symbol, int* out_insertion_index = nullptr) {
306 307
    return SearchName(symbol, out_insertion_index);
  }
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 312
                    PropertyAttributes attributes, int* out_insertion_index);

313
  inline int number_of_transitions() const;
314

315 316
  static bool CompactPrototypeTransitionArray(Isolate* isolate,
                                              WeakFixedArray* array);
317

318 319
  static Handle<WeakFixedArray> GrowPrototypeTransitionArray(
      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 327 328 329 330 331 332 333 334
                                PropertyAttributes attributes2);

  // Compares keys, returns -1 if key1 is "less" than key2,
  // 0 if key1 equal to key2 and 1 otherwise.
  static inline int CompareNames(Name* key1, uint32_t hash1, Name* key2,
                                 uint32_t hash2);

  // Compares two details, returns -1 if details1 is "less" than details2,
  // 0 if details1 equal to details2 and 1 otherwise.
335
  static inline int CompareDetails(PropertyKind kind1,
336
                                   PropertyAttributes attributes1,
337
                                   PropertyKind kind2,
338 339
                                   PropertyAttributes attributes2);

340
  inline void Set(int transition_number, Name* key, MaybeObject* target);
341

342
  void Zap(Isolate* isolate);
343

344 345 346
  DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
};

347 348
}  // namespace internal
}  // namespace v8
349

350 351
#include "src/objects/object-macros-undef.h"

352
#endif  // V8_TRANSITIONS_H_