map-updater.h 8.43 KB
Newer Older
1 2 3 4
// Copyright 2017 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.

5 6
#ifndef V8_MAP_UPDATER_H_
#define V8_MAP_UPDATER_H_
7 8

#include "src/elements-kind.h"
9
#include "src/field-type.h"
10 11
#include "src/globals.h"
#include "src/handles.h"
12
#include "src/objects/map.h"
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
#include "src/property-details.h"

namespace v8 {
namespace internal {

// The |MapUpdater| class implements all sorts of map reconfigurations
// including changes of elements kind, property attributes, property kind,
// property location and field representations/type changes. It ensures that
// the reconfigured map and all the intermediate maps are properly integrated
// into the exising transition tree.
//
// To avoid high degrees over polymorphism, and to stabilize quickly, on every
// rewrite the new type is deduced by merging the current type with any
// potential new (partial) version of the type in the transition tree.
// To do this, on each rewrite:
28 29
// - Search the root of the transition tree using FindRootMap, remember
//   the integrity level (preventExtensions/seal/freeze) transitions.
30 31 32 33
// - Find/create a |root_map| with requested |new_elements_kind|.
// - Find |target_map|, the newest matching version of this map using the
//   "updated" |old_map|'s descriptor array (i.e. whose entry at |modify_index|
//   is considered to be of |new_kind| and having |new_attributes|) to walk
34 35 36 37
//   the transition tree. If there was an integrity level transition on the path
//   to the old map, use the descriptor array of the map preceding the first
//   integrity level transition (|integrity_source_map|), and try to replay
//   the integrity level transition afterwards.
38 39 40 41 42 43 44
// - Merge/generalize the "updated" descriptor array of the |old_map| and
//   descriptor array of the |target_map|.
// - Generalize the |modify_index| descriptor using |new_representation| and
//   |new_field_type|.
// - Walk the tree again starting from the root towards |target_map|. Stop at
//   |split_map|, the first map who's descriptor array does not match the merged
//   descriptor array.
45 46
// - If |target_map| == |split_map|, and there are no integrity level
//   transitions, |target_map| is in the expected state. Return it.
47 48
// - Otherwise, invalidate the outdated transition target from |target_map|, and
//   replace its transition tree with a new branch for the updated descriptors.
49
// - If the |old_map| had integrity level transition, create the new map for it.
50 51
class MapUpdater {
 public:
52
  MapUpdater(Isolate* isolate, Handle<Map> old_map);
53 54 55 56 57 58

  // Prepares for reconfiguring of a property at |descriptor| to data field
  // with given |attributes| and |representation|/|field_type| and
  // performs the steps 1-5.
  Handle<Map> ReconfigureToDataField(int descriptor,
                                     PropertyAttributes attributes,
59
                                     PropertyConstness constness,
60 61 62 63 64 65 66 67 68 69 70
                                     Representation representation,
                                     Handle<FieldType> field_type);

  // Prepares for reconfiguring elements kind and performs the steps 1-5.
  Handle<Map> ReconfigureElementsKind(ElementsKind elements_kind);

  // Prepares for updating deprecated map to most up-to-date non-deprecated
  // version and performs the steps 1-5.
  Handle<Map> Update();

 private:
71 72 73 74 75 76 77
  enum State {
    kInitialized,
    kAtRootMap,
    kAtTargetMap,
    kAtIntegrityLevelSource,
    kEnd
  };
78 79 80

  // Try to reconfigure property in-place without rebuilding transition tree
  // and creating new maps. See implementation for details.
81
  State TryReconfigureToDataFieldInplace();
82 83 84 85 86 87 88

  // Step 1.
  // - Search the root of the transition tree using FindRootMap.
  // - Find/create a |root_map_| with requested |new_elements_kind_|.
  State FindRootMap();

  // Step 2.
89
  // - Find |target_map|, the newest matching version of this map using the
90
  //   "updated" |old_map|'s descriptor array (i.e. whose entry at
91 92 93 94 95 96
  //   |modify_index| is considered to be of |new_kind| and having
  //   |new_attributes|) to walk the transition tree. If there was an integrity
  //   level transition on the path to the old map, use the descriptor array
  //   of the map preceding the first integrity level transition
  //   (|integrity_source_map|), and try to replay the integrity level
  //   transition afterwards.
97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
  State FindTargetMap();

  // Step 3.
  // - Merge/generalize the "updated" descriptor array of the |old_map_| and
  //   descriptor array of the |target_map_|.
  // - Generalize the |modified_descriptor_| using |new_representation| and
  //   |new_field_type_|.
  Handle<DescriptorArray> BuildDescriptorArray();

  // Step 4.
  // - Walk the tree again starting from the root towards |target_map|. Stop at
  //   |split_map|, the first map who's descriptor array does not match the
  //   merged descriptor array.
  Handle<Map> FindSplitMap(Handle<DescriptorArray> descriptors);

  // Step 5.
  // - If |target_map| == |split_map|, |target_map| is in the expected state.
  //   Return it.
  // - Otherwise, invalidate the outdated transition target from |target_map|,
  //   and replace its transition tree with a new branch for the updated
  //   descriptors.
  State ConstructNewMap();

120 121 122 123 124
  // Step 6 (if there was
  // - If the |old_map| had integrity level transition, create the new map
  //   for it.
  State ConstructNewMapWithIntegrityLevelTransition();

125 126 127
  // When a requested reconfiguration can not be done the result is a copy
  // of |old_map_| where every field has |Tagged| representation and |Any|
  // field type. This map is disconnected from the transition tree.
128
  State CopyGeneralizeAllFields(const char* reason);
129 130

  // Returns name of a |descriptor| property.
131
  inline Name GetKey(int descriptor) const;
132 133 134 135 136 137 138

  // Returns property details of a |descriptor| in "updated" |old_descrtiptors_|
  // array.
  inline PropertyDetails GetDetails(int descriptor) const;

  // Returns value of a |descriptor| with kDescriptor location in "updated"
  // |old_descrtiptors_| array.
139
  inline Object GetValue(int descriptor) const;
140 141 142

  // Returns field type for a |descriptor| with kField location in "updated"
  // |old_descrtiptors_| array.
143
  inline FieldType GetFieldType(int descriptor) const;
144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160

  // If a |descriptor| property in "updated" |old_descriptors_| has kField
  // location then returns it's field type otherwise computes optimal field
  // type for the descriptor's value and |representation|. The |location|
  // value must be a pre-fetched location for |descriptor|.
  inline Handle<FieldType> GetOrComputeFieldType(
      int descriptor, PropertyLocation location,
      Representation representation) const;

  // If a |descriptor| property in given |descriptors| array has kField
  // location then returns it's field type otherwise computes optimal field
  // type for the descriptor's value and |representation|.
  // The |location| value must be a pre-fetched location for |descriptor|.
  inline Handle<FieldType> GetOrComputeFieldType(
      Handle<DescriptorArray> descriptors, int descriptor,
      PropertyLocation location, Representation representation);

161 162 163 164 165
  void GeneralizeField(Handle<Map> map, int modify_index,
                       PropertyConstness new_constness,
                       Representation new_representation,
                       Handle<FieldType> new_field_type);

166
  bool TrySaveIntegrityLevelTransitions();
167

168 169 170 171 172 173 174 175
  Isolate* isolate_;
  Handle<Map> old_map_;
  Handle<DescriptorArray> old_descriptors_;
  Handle<Map> root_map_;
  Handle<Map> target_map_;
  Handle<Map> result_map_;
  int old_nof_;

176 177 178 179 180 181
  // Information about integrity level transitions.
  bool has_integrity_level_transition_ = false;
  PropertyAttributes integrity_level_ = NONE;
  Handle<Symbol> integrity_level_symbol_;
  Handle<Map> integrity_source_map_;

182 183
  State state_ = kInitialized;
  ElementsKind new_elements_kind_;
184
  bool is_transitionable_fast_elements_kind_;
185

186
  // If |modified_descriptor_| is not equal to -1 then the fields below form
187 188 189 190
  // an "update" of the |old_map_|'s descriptors.
  int modified_descriptor_ = -1;
  PropertyKind new_kind_ = kData;
  PropertyAttributes new_attributes_ = NONE;
191
  PropertyConstness new_constness_ = PropertyConstness::kMutable;
192 193 194 195 196 197 198 199 200 201 202 203 204
  PropertyLocation new_location_ = kField;
  Representation new_representation_ = Representation::None();

  // Data specific to kField location.
  Handle<FieldType> new_field_type_;

  // Data specific to kDescriptor location.
  Handle<Object> new_value_;
};

}  // namespace internal
}  // namespace v8

205
#endif  // V8_MAP_UPDATER_H_