transitions.h

Go to the documentation of this file.

// Copyright 2012 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
 
#ifndef V8_OBJECTS_TRANSITIONS_H_
#define V8_OBJECTS_TRANSITIONS_H_
 
#include <optional>
 
#include "src/common/checks.h"
#include "src/execution/isolate.h"
#include "src/objects/descriptor-array.h"
#include "src/objects/elements-kind.h"
#include "src/objects/map.h"
#include "src/objects/maybe-object.h"
#include "src/objects/name.h"
#include "src/objects/objects.h"
 
// Has to be the last include (doesn't have include guards):
#include "src/objects/object-macros.h"
 
namespace v8::internal {
 
// Find all transitions with given name and calls the callback.
using ForEachTransitionCallback = std::function<void(Tagged<Map>)>;
 
// Descriptor for the contents of special side-step transition arrays.
// Side-step transitions are accessed through the TransitionsAccessor which
// enforces adherence to this format. The entries are either weak, Empty, or
// Unreachable.
struct SideStepTransition {
  enum class Kind : uint32_t {
    kCloneObject,
    kObjectAssign,
    kObjectAssignValidityCell,
  };
  static constexpr uint32_t kSize =
      static_cast<uint32_t>(Kind::kObjectAssignValidityCell) + 1;
 
  static constexpr Tagged<Smi> Empty = Smi::FromInt(0);
  static constexpr Tagged<Smi> Unreachable = Smi::FromInt(1);
 
 private:
  static constexpr int index_of(Kind kind) {
    return static_cast<uint32_t>(kind);
  }
  static constexpr uint32_t kFirstMapIdx =
      static_cast<uint32_t>(Kind::kCloneObject);
  static constexpr uint32_t kLastMapIdx =
      static_cast<uint32_t>(Kind::kObjectAssign);
  friend class TransitionsAccessor;
  friend class TransitionArray;
  friend class ObjectAssignAssembler;
};
 
std::ostream& operator<<(std::ostream& os, SideStepTransition::Kind sidestep);
 
// 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.
//
// 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.
class V8_EXPORT_PRIVATE TransitionsAccessor {
 public:
  // {concurrent_access} signals that the TransitionsAccessor will only be used
  // in background threads. It acquires a reader lock for critical paths, as
  // well as blocking the accessor from modifying the TransitionsArray.
  inline TransitionsAccessor(Isolate* isolate, Tagged<Map> map,
                             bool concurrent_access = false);
 
  // Insert a new transition into |map|'s transition array, extending it
  // as necessary. This can trigger GC.
  static void Insert(Isolate* isolate, DirectHandle<Map> map,
                     DirectHandle<Name> name, DirectHandle<Map> target,
                     TransitionKindFlag flag) {
    InsertHelper(isolate, map, name, DirectHandle<Map>(target), flag);
  }
  static void InsertNoneSentinel(Isolate* isolate, DirectHandle<Map> map,
                                 DirectHandle<Name> name) {
    InsertHelper(isolate, map, name, DirectHandle<Map>(),
                 TransitionKindFlag::SPECIAL_TRANSITION);
  }
 
  Tagged<Map> SearchTransition(Tagged<Name> name, PropertyKind kind,
                               PropertyAttributes attributes);
  static inline MaybeHandle<Map> SearchTransition(
      Isolate* isolate, DirectHandle<Map> map, Tagged<Name> name,
      PropertyKind kind, PropertyAttributes attributes);
 
  // Searches for a transition with a special symbol.
  Tagged<Map> SearchSpecial(Tagged<Symbol> name);
  static inline MaybeHandle<Map> SearchSpecial(Isolate* isolate,
                                               DirectHandle<Map> map,
                                               Tagged<Symbol> name);
 
  // Returns true for non-property transitions like elements kind, or
  // or frozen/sealed transitions.
  static bool IsSpecialTransition(ReadOnlyRoots roots, Tagged<Name> name);
 
  MaybeHandle<Map> FindTransitionToField(DirectHandle<String> name);
 
  // Find all transitions with given name and calls the callback.
  // Neither GCs nor operations requiring Isolate::full_transition_array_access
  // lock are allowed inside the callback.
  // If any of the GC- or lock-requiring processing is necessary, it has to be
  // done outside of the callback.
  void ForEachTransitionTo(Tagged<Name> name,
                           const ForEachTransitionCallback& callback,
                           DisallowGarbageCollection* no_gc);
 
  template <typename Char>
  inline bool IsExpectedTransition(Tagged<Name> transition_name,
                                   Tagged<Map> transition_target,
                                   base::Vector<const Char> key_chars);
 
  template <typename Char>
  inline std::pair<Handle<String>, Handle<Map>> ExpectedTransition(
      base::Vector<const Char> key_chars);
 
  template <typename Callback, typename ProtoCallback,
            typename SideStepCallback>
  void ForEachTransition(DisallowGarbageCollection* no_gc, Callback callback,
                         ProtoCallback proto_transition_callback,
                         SideStepCallback side_step_transition_callback) {
    ForEachTransitionWithKey<Callback, ProtoCallback, SideStepCallback, false>(
        no_gc, callback, proto_transition_callback,
        side_step_transition_callback);
  }
 
  template <typename Callback, typename ProtoCallback,
            typename SideStepCallback, bool with_key = true>
  void ForEachTransitionWithKey(DisallowGarbageCollection* no_gc,
                                Callback callback,
                                ProtoCallback proto_transition_callback,
                                SideStepCallback side_step_transition_callback);
 
  int NumberOfTransitions();
  // 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.
  static const int kMaxNumberOfTransitions = 1024 + 512;
  inline Tagged<Name> GetKey(int transition_number);
  inline Tagged<Map> GetTarget(int transition_number);
  static inline PropertyDetails GetTargetDetails(Tagged<Name> name,
                                                 Tagged<Map> target);
 
  static bool CanHaveMoreTransitions(Isolate* isolate, DirectHandle<Map> map);
 
  static bool IsMatchingMap(Tagged<Map> target, Tagged<Name> name,
                            PropertyKind kind, PropertyAttributes attributes);
 
  bool HasIntegrityLevelTransitionTo(
      Tagged<Map> to, Tagged<Symbol>* out_symbol = nullptr,
      PropertyAttributes* out_integrity_level = nullptr);
 
  // ===== ITERATION =====
  using TraverseCallback = std::function<void(Tagged<Map>)>;
 
  // Traverse the transition tree in preorder.
  void TraverseTransitionTree(const TraverseCallback& callback) {
    // Make sure that we do not allocate in the callback.
    DisallowGarbageCollection no_gc;
    base::MutexGuardIf mutex_guard(isolate_->full_transition_array_access(),
                                   concurrent_access_);
    TraverseTransitionTreeInternal(callback, &no_gc);
  }
 
  // ===== 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.
  // PutPrototypeTransition can trigger GC.
  static bool PutPrototypeTransition(Isolate* isolate, DirectHandle<Map>,
                                     DirectHandle<Object> prototype,
                                     DirectHandle<Map> target_map);
  static std::optional<Tagged<Map>> GetPrototypeTransition(
      Isolate* isolate, Tagged<Map> map, Tagged<Object> prototype);
  bool HasPrototypeTransitions();
 
  // During the first-time Map::Update and Map::TryUpdate, the migration target
  // map could be cached in the raw_transitions slot of the old map that is
  // deprecated from the map transition tree. The next time old map is updated,
  // we will check this cache slot as a shortcut to get the migration target
  // map.
  static void SetMigrationTarget(Isolate* isolate, DirectHandle<Map> map,
                                 Tagged<Map> migration_target);
  Tagged<Map> GetMigrationTarget();
 
  inline bool HasSideStepTransitions();
  static void EnsureHasSideStepTransitions(Isolate* isolate,
                                           DirectHandle<Map> map);
  inline Tagged<Object> GetSideStepTransition(SideStepTransition::Kind i);
  inline void SetSideStepTransition(SideStepTransition::Kind i,
                                    Tagged<Object> target);
 
#if DEBUG || OBJECT_PRINT
  void PrintTransitions(std::ostream& os);
  static void PrintOneTransition(std::ostream& os, Tagged<Name> key,
                                 Tagged<Map> target);
  void PrintTransitionTree();
  void PrintTransitionTree(std::ostream& os, int level,
                           DisallowGarbageCollection* no_gc);
#endif
#if DEBUG
  static void CheckNewTransitionsAreConsistent(Isolate* isolate,
                                               DirectHandle<Map> map,
                                               Tagged<Object> transitions);
  bool IsConsistentWithBackPointers();
  bool IsSortedNoDuplicates();
#endif
 
 protected:
  // Allow tests to use inheritance to access internals.
  enum Encoding {
    kPrototypeInfo,
    kUninitialized,
    kMigrationTarget,
    kWeakRef,
    kFullTransitionArray,
  };
 
  inline Encoding encoding() { return encoding_; }
 
  inline int Capacity();
 
  inline Tagged<TransitionArray> transitions();
 
  DISALLOW_GARBAGE_COLLECTION(no_gc_)
 
 private:
  friend class MarkCompactCollector;  // For HasSimpleTransitionTo.
  friend class TransitionArray;
 
  static inline Encoding GetEncoding(Isolate* isolate,
                                     Tagged<MaybeObject> raw_transitions);
  static inline Encoding GetEncoding(Isolate* isolate,
                                     Tagged<TransitionArray> array);
  static inline Encoding GetEncoding(Isolate* isolate, DirectHandle<Map> map);
 
  static inline Tagged<TransitionArray> GetTransitionArray(
      Isolate* isolate, Tagged<MaybeObject> raw_transitions);
  static inline Tagged<TransitionArray> GetTransitionArray(
      Isolate* isolate, DirectHandle<Map> map);
 
  static inline Tagged<Map> GetSimpleTransition(Isolate* isolate,
                                                DirectHandle<Map> map);
  static inline Tagged<Name> GetSimpleTransitionKey(Tagged<Map> transition);
  inline PropertyDetails GetSimpleTargetDetails(Tagged<Map> transition);
 
  static inline Tagged<Map> GetTargetFromRaw(Tagged<MaybeObject> raw);
 
  static void EnsureHasFullTransitionArray(Isolate* isolate,
                                           DirectHandle<Map> map);
  static void SetPrototypeTransitions(
      Isolate* isolate, DirectHandle<Map> map,
      DirectHandle<WeakFixedArray> proto_transitions);
  static Tagged<WeakFixedArray> GetPrototypeTransitions(Isolate* isolate,
                                                        Tagged<Map> map);
 
  static void InsertHelper(Isolate* isolate, DirectHandle<Map> map,
                           DirectHandle<Name> name, DirectHandle<Map> target,
                           TransitionKindFlag flag);
 
  static inline void ReplaceTransitions(
      Isolate* isolate, DirectHandle<Map> map,
      Tagged<UnionOf<TransitionArray, MaybeWeak<Map>>> new_transitions);
  static inline void ReplaceTransitions(
      Isolate* isolate, DirectHandle<Map> map,
      DirectHandle<TransitionArray> new_transitions);
 
  bool HasSimpleTransitionTo(Tagged<Map> map);
 
  inline Tagged<Map> GetTargetMapFromWeakRef();
 
  void TraverseTransitionTreeInternal(const TraverseCallback& callback,
                                      DisallowGarbageCollection* no_gc);
 
  Isolate* isolate_;
  Tagged<Map> map_;
  Tagged<MaybeObject> raw_transitions_;
  Encoding encoding_;
  bool concurrent_access_;
 
  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:
// [0] Tagged<Smi>(0) or WeakFixedArray of prototype transitions (strong ref)
// [1] Tagged<Smi>(0) or WeakFixedArray of side-step transitions (strong ref)
// [2] Number of transitions (can be zero after trimming)
// [3] First transition key (strong ref)
// [4] First transition target (weak ref)
// ...
// [4 + number of transitions * kTransitionSize]: start of slack
// TODO(olivf): The slots for prototype transitions and side-steps could be
// shared.
class TransitionArray : public WeakFixedArray {
 public:
  inline int number_of_transitions() const;
 
  inline Tagged<WeakFixedArray> GetPrototypeTransitions();
  inline bool HasPrototypeTransitions();
 
  // Accessors for fetching instance transition at transition number.
  inline void SetKey(int transition_number, Tagged<Name> value);
  inline Tagged<Name> GetKey(int transition_number);
  inline HeapObjectSlot GetKeySlot(int transition_number);
 
  inline Tagged<Map> GetTarget(int transition_number);
  inline void SetRawTarget(int transition_number, Tagged<MaybeObject> target);
  inline Tagged<MaybeObject> GetRawTarget(int transition_number);
  inline HeapObjectSlot GetTargetSlot(int transition_number);
  inline bool GetTargetIfExists(int transition_number, Isolate* isolate,
                                Tagged<Map>* target);
 
  static constexpr int kNotFound = -1;
 
#ifdef DEBUG
  V8_EXPORT_PRIVATE bool IsSortedNoDuplicates();
#endif
 
  V8_EXPORT_PRIVATE void Sort();
 
  void PrintInternal(std::ostream& os);
 
  DECL_PRINTER(TransitionArray)
  DECL_VERIFIER(TransitionArray)
 
  // Layout for full transition arrays.
  static const int kPrototypeTransitionsIndex = 0;
  static const int kSideStepTransitionsIndex = 1;
  static const int kTransitionLengthIndex = 2;
  static const int kFirstIndex = 3;
 
  // 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(Tagged<Name> name,
                                  int* out_insertion_index = nullptr);
 
  inline Tagged<Map> SearchAndGetTargetForTesting(
      PropertyKind kind, Tagged<Name> name, PropertyAttributes attributes);
 
  // Accessors for side-step transitions.
  inline bool HasSideStepTransitions();
  static void CreateSideStepTransitions(
      Isolate* isolate, DirectHandle<TransitionArray> transitions);
 
 private:
  friend class Factory;
  friend class MarkCompactCollector;
  friend class TransitionsAccessor;
 
  inline void SetNumberOfTransitions(int number_of_transitions);
 
  inline int Capacity();
 
  // ===== 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;
 
  inline void SetPrototypeTransitions(
      Tagged<WeakFixedArray> prototype_transitions);
 
  static inline int NumberOfPrototypeTransitions(
      Tagged<WeakFixedArray> proto_transitions);
  static void SetNumberOfPrototypeTransitions(
      Tagged<WeakFixedArray> proto_transitions, int value);
 
  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.
  int Search(PropertyKind kind, Tagged<Name> name,
             PropertyAttributes attributes, int* out_insertion_index = nullptr);
 
  V8_EXPORT_PRIVATE Tagged<Map> SearchAndGetTarget(
      PropertyKind kind, Tagged<Name> name, PropertyAttributes attributes);
 
  // Search a non-property transition (like elements kind, observe or frozen
  // transitions).
  inline int SearchSpecial(Tagged<Symbol> symbol,
                           bool concurrent_search = false,
                           int* out_insertion_index = nullptr);
  // Search a first transition for a given property name.
  inline int SearchName(Tagged<Name> name, bool concurrent_search = false,
                        int* out_insertion_index = nullptr);
  int SearchDetails(int transition, PropertyKind kind,
                    PropertyAttributes attributes, int* out_insertion_index);
  Tagged<Map> SearchDetailsAndGetTarget(int transition, PropertyKind kind,
                                        PropertyAttributes attributes);
 
  inline int LinearSearchName(Tagged<Name> name, int* out_insertion_index);
  inline int BinarySearchName(Tagged<Name> name, int* out_insertion_index);
 
  // Find all transitions with given name and calls the callback.
  void ForEachTransitionTo(Tagged<Name> name,
                           const ForEachTransitionCallback& callback);
 
  static bool CompactPrototypeTransitionArray(Isolate* isolate,
                                              Tagged<WeakFixedArray> array);
 
  static DirectHandle<WeakFixedArray> GrowPrototypeTransitionArray(
      DirectHandle<WeakFixedArray> array, int new_capacity, Isolate* isolate);
 
  // Compares two tuples <key, kind, attributes>, returns -1 if
  // tuple1 is "less" than tuple2, 0 if tuple1 equal to tuple2 and 1 otherwise.
  static inline int CompareKeys(Tagged<Name> key1, uint32_t hash1,
                                PropertyKind kind1,
                                PropertyAttributes attributes1,
                                Tagged<Name> key2, uint32_t hash2,
                                PropertyKind kind2,
                                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(Tagged<Name> key1, uint32_t hash1,
                                 Tagged<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.
  static inline int CompareDetails(PropertyKind kind1,
                                   PropertyAttributes attributes1,
                                   PropertyKind kind2,
                                   PropertyAttributes attributes2);
 
  inline void Set(int transition_number, Tagged<Name> key,
                  Tagged<MaybeObject> target);
 
  inline Tagged<WeakFixedArray> GetSideStepTransitions();
  inline void SetSideStepTransitions(Tagged<WeakFixedArray> transitions);
};
 
}  // namespace v8::internal
 
#include "src/objects/object-macros-undef.h"
 
#endif  // V8_OBJECTS_TRANSITIONS_H_