1// Copyright 2017 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_MAP_UPDATER_H_
6#define V8_MAP_UPDATER_H_
7
8#include "src/elements-kind.h"
9#include "src/field-type.h"
10#include "src/globals.h"
11#include "src/handles.h"
12#include "src/objects/map.h"
13#include "src/property-details.h"
14
15namespace v8 {
16namespace internal {
17
18// The |MapUpdater| class implements all sorts of map reconfigurations
19// including changes of elements kind, property attributes, property kind,
20// property location and field representations/type changes. It ensures that
21// the reconfigured map and all the intermediate maps are properly integrated
22// into the exising transition tree.
23//
24// To avoid high degrees over polymorphism, and to stabilize quickly, on every
25// rewrite the new type is deduced by merging the current type with any
26// potential new (partial) version of the type in the transition tree.
27// To do this, on each rewrite:
28// - Search the root of the transition tree using FindRootMap, remember
29// the integrity level (preventExtensions/seal/freeze) transitions.
30// - Find/create a |root_map| with requested |new_elements_kind|.
31// - Find |target_map|, the newest matching version of this map using the
32// "updated" |old_map|'s descriptor array (i.e. whose entry at |modify_index|
33// is considered to be of |new_kind| and having |new_attributes|) to walk
34// the transition tree. If there was an integrity level transition on the path
35// to the old map, use the descriptor array of the map preceding the first
36// integrity level transition (|integrity_source_map|), and try to replay
37// the integrity level transition afterwards.
38// - Merge/generalize the "updated" descriptor array of the |old_map| and
39// descriptor array of the |target_map|.
40// - Generalize the |modify_index| descriptor using |new_representation| and
41// |new_field_type|.
42// - Walk the tree again starting from the root towards |target_map|. Stop at
43// |split_map|, the first map who's descriptor array does not match the merged
44// descriptor array.
45// - If |target_map| == |split_map|, and there are no integrity level
46// transitions, |target_map| is in the expected state. Return it.
47// - Otherwise, invalidate the outdated transition target from |target_map|, and
48// 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.
50class MapUpdater {
51 public:
52 MapUpdater(Isolate* isolate, Handle<Map> old_map);
53
54 // Prepares for reconfiguring of a property at |descriptor| to data field
55 // with given |attributes| and |representation|/|field_type| and
56 // performs the steps 1-5.
57 Handle<Map> ReconfigureToDataField(int descriptor,
58 PropertyAttributes attributes,
59 PropertyConstness constness,
60 Representation representation,
61 Handle<FieldType> field_type);
62
63 // Prepares for reconfiguring elements kind and performs the steps 1-5.
64 Handle<Map> ReconfigureElementsKind(ElementsKind elements_kind);
65
66 // Prepares for updating deprecated map to most up-to-date non-deprecated
67 // version and performs the steps 1-5.
68 Handle<Map> Update();
69
70 private:
71 enum State {
72 kInitialized,
73 kAtRootMap,
74 kAtTargetMap,
75 kAtIntegrityLevelSource,
76 kEnd
77 };
78
79 // Try to reconfigure property in-place without rebuilding transition tree
80 // and creating new maps. See implementation for details.
81 State TryReconfigureToDataFieldInplace();
82
83 // Step 1.
84 // - Search the root of the transition tree using FindRootMap.
85 // - Find/create a |root_map_| with requested |new_elements_kind_|.
86 State FindRootMap();
87
88 // 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 // |modify_index| is considered to be of |new_kind| and having
92 // |new_attributes|) to walk the transition tree. If there was an integrity
93 // level transition on the path to the old map, use the descriptor array
94 // of the map preceding the first integrity level transition
95 // (|integrity_source_map|), and try to replay the integrity level
96 // transition afterwards.
97 State FindTargetMap();
98
99 // Step 3.
100 // - Merge/generalize the "updated" descriptor array of the |old_map_| and
101 // descriptor array of the |target_map_|.
102 // - Generalize the |modified_descriptor_| using |new_representation| and
103 // |new_field_type_|.
104 Handle<DescriptorArray> BuildDescriptorArray();
105
106 // Step 4.
107 // - Walk the tree again starting from the root towards |target_map|. Stop at
108 // |split_map|, the first map who's descriptor array does not match the
109 // merged descriptor array.
110 Handle<Map> FindSplitMap(Handle<DescriptorArray> descriptors);
111
112 // Step 5.
113 // - If |target_map| == |split_map|, |target_map| is in the expected state.
114 // Return it.
115 // - Otherwise, invalidate the outdated transition target from |target_map|,
116 // and replace its transition tree with a new branch for the updated
117 // descriptors.
118 State ConstructNewMap();
119
120 // Step 6 (if there was
121 // - If the |old_map| had integrity level transition, create the new map
122 // for it.
123 State ConstructNewMapWithIntegrityLevelTransition();
124
125 // When a requested reconfiguration can not be done the result is a copy
126 // of |old_map_| where every field has |Tagged| representation and |Any|
127 // 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 // Returns property details of a |descriptor| in "updated" |old_descrtiptors_|
134 // array.
135 inline PropertyDetails GetDetails(int descriptor) const;
136
137 // Returns value of a |descriptor| with kDescriptor location in "updated"
138 // |old_descrtiptors_| array.
139 inline Object GetValue(int descriptor) const;
140
141 // Returns field type for a |descriptor| with kField location in "updated"
142 // |old_descrtiptors_| array.
143 inline FieldType GetFieldType(int descriptor) const;
144
145 // If a |descriptor| property in "updated" |old_descriptors_| has kField
146 // location then returns it's field type otherwise computes optimal field
147 // type for the descriptor's value and |representation|. The |location|
148 // value must be a pre-fetched location for |descriptor|.
149 inline Handle<FieldType> GetOrComputeFieldType(
150 int descriptor, PropertyLocation location,
151 Representation representation) const;
152
153 // If a |descriptor| property in given |descriptors| array has kField
154 // location then returns it's field type otherwise computes optimal field
155 // type for the descriptor's value and |representation|.
156 // The |location| value must be a pre-fetched location for |descriptor|.
157 inline Handle<FieldType> GetOrComputeFieldType(
158 Handle<DescriptorArray> descriptors, int descriptor,
159 PropertyLocation location, Representation representation);
160
161 void GeneralizeField(Handle<Map> map, int modify_index,
162 PropertyConstness new_constness,
163 Representation new_representation,
164 Handle<FieldType> new_field_type);
165
166 bool TrySaveIntegrityLevelTransitions();
167
168 Isolate* isolate_;
169 Handle<Map> old_map_;
170 Handle<DescriptorArray> old_descriptors_;
171 Handle<Map> root_map_;
172 Handle<Map> target_map_;
173 Handle<Map> result_map_;
174 int old_nof_;
175
176 // Information about integrity level transitions.
177 bool has_integrity_level_transition_ = false;
178 PropertyAttributes integrity_level_ = NONE;
179 Handle<Symbol> integrity_level_symbol_;
180 Handle<Map> integrity_source_map_;
181
182 State state_ = kInitialized;
183 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 // an "update" of the |old_map_|'s descriptors.
188 int modified_descriptor_ = -1;
189 PropertyKind new_kind_ = kData;
190 PropertyAttributes new_attributes_ = NONE;
191 PropertyConstness new_constness_ = PropertyConstness::kMutable;
192 PropertyLocation new_location_ = kField;
193 Representation new_representation_ = Representation::None();
194
195 // Data specific to kField location.
196 Handle<FieldType> new_field_type_;
197
198 // Data specific to kDescriptor location.
199 Handle<Object> new_value_;
200};
201
202} // namespace internal
203} // namespace v8
204
205#endif // V8_MAP_UPDATER_H_
206