Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(208)

Side by Side Diff: src/key-accumulator.cc

Issue 1707743002: [key-accumulator] Starting to reimplement the key-accumulator (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: use proper type Created 4 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/key-accumulator.h ('k') | src/keys.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 // Copyright 2013 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 #include "src/key-accumulator.h"
6
7 #include "src/elements.h"
8 #include "src/factory.h"
9 #include "src/isolate-inl.h"
10 #include "src/objects-inl.h"
11 #include "src/property-descriptor.h"
12
13
14 namespace v8 {
15 namespace internal {
16
17
18 KeyAccumulator::~KeyAccumulator() {
19 for (size_t i = 0; i < elements_.size(); i++) {
20 delete elements_[i];
21 }
22 }
23
24
25 Handle<FixedArray> KeyAccumulator::GetKeys(GetKeysConversion convert) {
26 if (length_ == 0) {
27 return isolate_->factory()->empty_fixed_array();
28 }
29 // Make sure we have all the lengths collected.
30 NextPrototype();
31
32 if (type_ == OWN_ONLY && !ownProxyKeys_.is_null()) {
33 return ownProxyKeys_;
34 }
35 // Assemble the result array by first adding the element keys and then the
36 // property keys. We use the total number of String + Symbol keys per level in
37 // |level_lengths_| and the available element keys in the corresponding bucket
38 // in |elements_| to deduce the number of keys to take from the
39 // |string_properties_| and |symbol_properties_| set.
40 Handle<FixedArray> result = isolate_->factory()->NewFixedArray(length_);
41 int insertion_index = 0;
42 int string_properties_index = 0;
43 int symbol_properties_index = 0;
44 // String and Symbol lengths always come in pairs:
45 size_t max_level = level_lengths_.size() / 2;
46 for (size_t level = 0; level < max_level; level++) {
47 int num_string_properties = level_lengths_[level * 2];
48 int num_symbol_properties = level_lengths_[level * 2 + 1];
49 if (num_string_properties < 0) {
50 // If the |num_string_properties| is negative, the current level contains
51 // properties from a proxy, hence we skip the integer keys in |elements_|
52 // since proxies define the complete ordering.
53 num_string_properties = -num_string_properties;
54 } else if (level < elements_.size()) {
55 // Add the element indices for this prototype level.
56 std::vector<uint32_t>* elements = elements_[level];
57 int num_elements = static_cast<int>(elements->size());
58 for (int i = 0; i < num_elements; i++) {
59 Handle<Object> key;
60 if (convert == KEEP_NUMBERS) {
61 key = isolate_->factory()->NewNumberFromUint(elements->at(i));
62 } else {
63 key = isolate_->factory()->Uint32ToString(elements->at(i));
64 }
65 result->set(insertion_index, *key);
66 insertion_index++;
67 }
68 }
69 // Add the string property keys for this prototype level.
70 for (int i = 0; i < num_string_properties; i++) {
71 Object* key = string_properties_->KeyAt(string_properties_index);
72 result->set(insertion_index, key);
73 insertion_index++;
74 string_properties_index++;
75 }
76 // Add the symbol property keys for this prototype level.
77 for (int i = 0; i < num_symbol_properties; i++) {
78 Object* key = symbol_properties_->KeyAt(symbol_properties_index);
79 result->set(insertion_index, key);
80 insertion_index++;
81 symbol_properties_index++;
82 }
83 }
84
85 DCHECK_EQ(insertion_index, length_);
86 return result;
87 }
88
89
90 namespace {
91
92 bool AccumulatorHasKey(std::vector<uint32_t>* sub_elements, uint32_t key) {
93 return std::binary_search(sub_elements->begin(), sub_elements->end(), key);
94 }
95
96 } // namespace
97
98 bool KeyAccumulator::AddKey(Object* key, AddKeyConversion convert) {
99 return AddKey(handle(key, isolate_), convert);
100 }
101
102
103 bool KeyAccumulator::AddKey(Handle<Object> key, AddKeyConversion convert) {
104 if (key->IsSymbol()) {
105 if (filter_ & SKIP_SYMBOLS) return false;
106 if (Handle<Symbol>::cast(key)->is_private()) return false;
107 return AddSymbolKey(key);
108 }
109 if (filter_ & SKIP_STRINGS) return false;
110 // Make sure we do not add keys to a proxy-level (see AddKeysFromProxy).
111 DCHECK_LE(0, level_string_length_);
112 // In some cases (e.g. proxies) we might get in String-converted ints which
113 // should be added to the elements list instead of the properties. For
114 // proxies we have to convert as well but also respect the original order.
115 // Therefore we add a converted key to both sides
116 if (convert == CONVERT_TO_ARRAY_INDEX || convert == PROXY_MAGIC) {
117 uint32_t index = 0;
118 int prev_length = length_;
119 int prev_proto = level_string_length_;
120 if ((key->IsString() && Handle<String>::cast(key)->AsArrayIndex(&index)) ||
121 key->ToArrayIndex(&index)) {
122 bool key_was_added = AddIntegerKey(index);
123 if (convert == CONVERT_TO_ARRAY_INDEX) return key_was_added;
124 if (convert == PROXY_MAGIC) {
125 // If we had an array index (number) and it wasn't added, the key
126 // already existed before, hence we cannot add it to the properties
127 // keys as it would lead to duplicate entries.
128 if (!key_was_added) {
129 return false;
130 }
131 length_ = prev_length;
132 level_string_length_ = prev_proto;
133 }
134 }
135 }
136 return AddStringKey(key, convert);
137 }
138
139
140 bool KeyAccumulator::AddKey(uint32_t key) { return AddIntegerKey(key); }
141
142
143 bool KeyAccumulator::AddIntegerKey(uint32_t key) {
144 // Make sure we do not add keys to a proxy-level (see AddKeysFromProxy).
145 // We mark proxy-levels with a negative length
146 DCHECK_LE(0, level_string_length_);
147 // Binary search over all but the last level. The last one might not be
148 // sorted yet.
149 for (size_t i = 1; i < elements_.size(); i++) {
150 if (AccumulatorHasKey(elements_[i - 1], key)) return false;
151 }
152 elements_.back()->push_back(key);
153 length_++;
154 return true;
155 }
156
157
158 bool KeyAccumulator::AddStringKey(Handle<Object> key,
159 AddKeyConversion convert) {
160 if (string_properties_.is_null()) {
161 string_properties_ = OrderedHashSet::Allocate(isolate_, 16);
162 }
163 // TODO(cbruni): remove this conversion once we throw the correct TypeError
164 // for non-string/symbol elements returned by proxies
165 if (convert == PROXY_MAGIC && key->IsNumber()) {
166 key = isolate_->factory()->NumberToString(key);
167 }
168 int prev_size = string_properties_->NumberOfElements();
169 string_properties_ = OrderedHashSet::Add(string_properties_, key);
170 if (prev_size < string_properties_->NumberOfElements()) {
171 length_++;
172 level_string_length_++;
173 return true;
174 } else {
175 return false;
176 }
177 }
178
179
180 bool KeyAccumulator::AddSymbolKey(Handle<Object> key) {
181 if (symbol_properties_.is_null()) {
182 symbol_properties_ = OrderedHashSet::Allocate(isolate_, 16);
183 }
184 int prev_size = symbol_properties_->NumberOfElements();
185 symbol_properties_ = OrderedHashSet::Add(symbol_properties_, key);
186 if (prev_size < symbol_properties_->NumberOfElements()) {
187 length_++;
188 level_symbol_length_++;
189 return true;
190 } else {
191 return false;
192 }
193 }
194
195
196 void KeyAccumulator::AddKeys(Handle<FixedArray> array,
197 AddKeyConversion convert) {
198 int add_length = array->length();
199 if (add_length == 0) return;
200 for (int i = 0; i < add_length; i++) {
201 Handle<Object> current(array->get(i), isolate_);
202 AddKey(current, convert);
203 }
204 }
205
206
207 void KeyAccumulator::AddKeys(Handle<JSObject> array_like,
208 AddKeyConversion convert) {
209 DCHECK(array_like->IsJSArray() || array_like->HasSloppyArgumentsElements());
210 ElementsAccessor* accessor = array_like->GetElementsAccessor();
211 accessor->AddElementsToKeyAccumulator(array_like, this, convert);
212 }
213
214
215 void KeyAccumulator::AddKeysFromProxy(Handle<JSObject> array_like) {
216 // Proxies define a complete list of keys with no distinction of
217 // elements and properties, which breaks the normal assumption for the
218 // KeyAccumulator.
219 AddKeys(array_like, PROXY_MAGIC);
220 // Invert the current length to indicate a present proxy, so we can ignore
221 // element keys for this level. Otherwise we would not fully respect the order
222 // given by the proxy.
223 level_string_length_ = -level_string_length_;
224 }
225
226
227 MaybeHandle<FixedArray> FilterProxyKeys(Isolate* isolate, Handle<JSProxy> owner,
228 Handle<FixedArray> keys,
229 PropertyFilter filter) {
230 if (filter == ALL_PROPERTIES) {
231 // Nothing to do.
232 return keys;
233 }
234 int store_position = 0;
235 for (int i = 0; i < keys->length(); ++i) {
236 Handle<Name> key(Name::cast(keys->get(i)), isolate);
237 if (key->FilterKey(filter)) continue; // Skip this key.
238 if (filter & ONLY_ENUMERABLE) {
239 PropertyDescriptor desc;
240 Maybe<bool> found =
241 JSProxy::GetOwnPropertyDescriptor(isolate, owner, key, &desc);
242 MAYBE_RETURN(found, MaybeHandle<FixedArray>());
243 if (!found.FromJust() || !desc.enumerable()) continue; // Skip this key.
244 }
245 // Keep this key.
246 if (store_position != i) {
247 keys->set(store_position, *key);
248 }
249 store_position++;
250 }
251 if (store_position == 0) return isolate->factory()->empty_fixed_array();
252 keys->Shrink(store_position);
253 return keys;
254 }
255
256
257 // Returns "nothing" in case of exception, "true" on success.
258 Maybe<bool> KeyAccumulator::AddKeysFromProxy(Handle<JSProxy> proxy,
259 Handle<FixedArray> keys) {
260 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
261 isolate_, keys, FilterProxyKeys(isolate_, proxy, keys, filter_),
262 Nothing<bool>());
263 // Proxies define a complete list of keys with no distinction of
264 // elements and properties, which breaks the normal assumption for the
265 // KeyAccumulator.
266 if (type_ == OWN_ONLY) {
267 ownProxyKeys_ = keys;
268 level_string_length_ = keys->length();
269 length_ = level_string_length_;
270 } else {
271 AddKeys(keys, PROXY_MAGIC);
272 }
273 // Invert the current length to indicate a present proxy, so we can ignore
274 // element keys for this level. Otherwise we would not fully respect the order
275 // given by the proxy.
276 level_string_length_ = -level_string_length_;
277 return Just(true);
278 }
279
280
281 void KeyAccumulator::AddElementKeysFromInterceptor(
282 Handle<JSObject> array_like) {
283 AddKeys(array_like, CONVERT_TO_ARRAY_INDEX);
284 // The interceptor might introduce duplicates for the current level, since
285 // these keys get added after the objects's normal element keys.
286 SortCurrentElementsListRemoveDuplicates();
287 }
288
289
290 void KeyAccumulator::SortCurrentElementsListRemoveDuplicates() {
291 // Sort and remove duplicates from the current elements level and adjust.
292 // the lengths accordingly.
293 auto last_level = elements_.back();
294 size_t nof_removed_keys = last_level->size();
295 std::sort(last_level->begin(), last_level->end());
296 last_level->erase(std::unique(last_level->begin(), last_level->end()),
297 last_level->end());
298 // Adjust total length by the number of removed duplicates.
299 nof_removed_keys -= last_level->size();
300 length_ -= static_cast<int>(nof_removed_keys);
301 }
302
303
304 void KeyAccumulator::SortCurrentElementsList() {
305 if (elements_.empty()) return;
306 auto element_keys = elements_.back();
307 std::sort(element_keys->begin(), element_keys->end());
308 }
309
310
311 void KeyAccumulator::NextPrototype() {
312 // Store the protoLength on the first call of this method.
313 if (!elements_.empty()) {
314 level_lengths_.push_back(level_string_length_);
315 level_lengths_.push_back(level_symbol_length_);
316 }
317 elements_.push_back(new std::vector<uint32_t>());
318 level_string_length_ = 0;
319 level_symbol_length_ = 0;
320 }
321
322
323 } // namespace internal
324 } // namespace v8
OLDNEW
« no previous file with comments | « src/key-accumulator.h ('k') | src/keys.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698