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_OBJECTS_MAP_UPDATER_H_ 6 #define V8_OBJECTS_MAP_UPDATER_H_ 7 8 #include "src/common/globals.h" 9 #include "src/handles/handles.h" 10 #include "src/objects/elements-kind.h" 11 #include "src/objects/field-type.h" 12 #include "src/objects/map.h" 13 #include "src/objects/property-details.h" 14 15 namespace v8 { 16 namespace 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. 50 class 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(InternalIndex 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_| in dictionary mode. 127 State Normalize(const char* reason); 128 129 // Returns name of a |descriptor| property. 130 inline Name GetKey(InternalIndex descriptor) const; 131 132 // Returns property details of a |descriptor| in "updated" |old_descrtiptors_| 133 // array. 134 inline PropertyDetails GetDetails(InternalIndex descriptor) const; 135 136 // Returns value of a |descriptor| with kDescriptor location in "updated" 137 // |old_descrtiptors_| array. 138 inline Object GetValue(InternalIndex descriptor) const; 139 140 // Returns field type for a |descriptor| with kField location in "updated" 141 // |old_descrtiptors_| array. 142 inline FieldType GetFieldType(InternalIndex descriptor) const; 143 144 // If a |descriptor| property in "updated" |old_descriptors_| has kField 145 // location then returns it's field type otherwise computes optimal field 146 // type for the descriptor's value and |representation|. The |location| 147 // value must be a pre-fetched location for |descriptor|. 148 inline Handle<FieldType> GetOrComputeFieldType( 149 InternalIndex descriptor, PropertyLocation location, 150 Representation representation) const; 151 152 // If a |descriptor| property in given |descriptors| array has kField 153 // location then returns it's field type otherwise computes optimal field 154 // type for the descriptor's value and |representation|. 155 // The |location| value must be a pre-fetched location for |descriptor|. 156 inline Handle<FieldType> GetOrComputeFieldType( 157 Handle<DescriptorArray> descriptors, InternalIndex descriptor, 158 PropertyLocation location, Representation representation); 159 160 void GeneralizeField(Handle<Map> map, InternalIndex modify_index, 161 PropertyConstness new_constness, 162 Representation new_representation, 163 Handle<FieldType> new_field_type); 164 165 bool TrySaveIntegrityLevelTransitions(); 166 167 Isolate* isolate_; 168 Handle<Map> old_map_; 169 Handle<DescriptorArray> old_descriptors_; 170 Handle<Map> root_map_; 171 Handle<Map> target_map_; 172 Handle<Map> result_map_; 173 int old_nof_; 174 175 // Information about integrity level transitions. 176 bool has_integrity_level_transition_ = false; 177 PropertyAttributes integrity_level_ = NONE; 178 Handle<Symbol> integrity_level_symbol_; 179 Handle<Map> integrity_source_map_; 180 181 State state_ = kInitialized; 182 ElementsKind new_elements_kind_; 183 bool is_transitionable_fast_elements_kind_; 184 185 // If |modified_descriptor_.is_found()|, then the fields below form 186 // an "update" of the |old_map_|'s descriptors. 187 InternalIndex modified_descriptor_ = InternalIndex::NotFound(); 188 PropertyKind new_kind_ = kData; 189 PropertyAttributes new_attributes_ = NONE; 190 PropertyConstness new_constness_ = PropertyConstness::kMutable; 191 PropertyLocation new_location_ = kField; 192 Representation new_representation_ = Representation::None(); 193 194 // Data specific to kField location. 195 Handle<FieldType> new_field_type_; 196 197 // Data specific to kDescriptor location. 198 Handle<Object> new_value_; 199 }; 200 201 } // namespace internal 202 } // namespace v8 203 204 #endif // V8_OBJECTS_MAP_UPDATER_H_ 205