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 #include "src/builtins/builtins-iterator-gen.h"
6 #include "src/builtins/growable-fixed-array-gen.h"
7
8 #include "src/builtins/builtins-collections-gen.h"
9 #include "src/builtins/builtins-string-gen.h"
10 #include "src/builtins/builtins-utils-gen.h"
11 #include "src/builtins/builtins.h"
12 #include "src/codegen/code-stub-assembler.h"
13 #include "src/heap/factory-inl.h"
14
15 namespace v8 {
16 namespace internal {
17
18 using IteratorRecord = TorqueStructIteratorRecord;
19 using compiler::Node;
20
GetIteratorMethod(TNode<Context> context,TNode<Object> object)21 TNode<Object> IteratorBuiltinsAssembler::GetIteratorMethod(
22 TNode<Context> context, TNode<Object> object) {
23 return GetProperty(context, object, factory()->iterator_symbol());
24 }
25
GetIterator(TNode<Context> context,TNode<Object> object)26 IteratorRecord IteratorBuiltinsAssembler::GetIterator(TNode<Context> context,
27 TNode<Object> object) {
28 TNode<Object> method = GetIteratorMethod(context, object);
29 return GetIterator(context, object, method);
30 }
31
GetIterator(TNode<Context> context,TNode<Object> object,TNode<Object> method)32 IteratorRecord IteratorBuiltinsAssembler::GetIterator(TNode<Context> context,
33 TNode<Object> object,
34 TNode<Object> method) {
35 Label if_not_callable(this, Label::kDeferred), if_callable(this);
36 GotoIf(TaggedIsSmi(method), &if_not_callable);
37 Branch(IsCallable(CAST(method)), &if_callable, &if_not_callable);
38
39 BIND(&if_not_callable);
40 CallRuntime(Runtime::kThrowIteratorError, context, object);
41 Unreachable();
42
43 BIND(&if_callable);
44 {
45 TNode<Object> iterator = Call(context, method, object);
46
47 Label get_next(this), if_notobject(this, Label::kDeferred);
48 GotoIf(TaggedIsSmi(iterator), &if_notobject);
49 Branch(IsJSReceiver(CAST(iterator)), &get_next, &if_notobject);
50
51 BIND(&if_notobject);
52 CallRuntime(Runtime::kThrowSymbolIteratorInvalid, context);
53 Unreachable();
54
55 BIND(&get_next);
56 TNode<Object> next =
57 GetProperty(context, iterator, factory()->next_string());
58 return IteratorRecord{TNode<JSReceiver>::UncheckedCast(iterator),
59 TNode<Object>::UncheckedCast(next)};
60 }
61 }
62
IteratorStep(TNode<Context> context,const IteratorRecord & iterator,Label * if_done,base::Optional<TNode<Map>> fast_iterator_result_map)63 TNode<JSReceiver> IteratorBuiltinsAssembler::IteratorStep(
64 TNode<Context> context, const IteratorRecord& iterator, Label* if_done,
65 base::Optional<TNode<Map>> fast_iterator_result_map) {
66 DCHECK_NOT_NULL(if_done);
67 // 1. a. Let result be ? Invoke(iterator, "next", « »).
68 TNode<Object> result = Call(context, iterator.next, iterator.object);
69
70 // 3. If Type(result) is not Object, throw a TypeError exception.
71 Label if_notobject(this, Label::kDeferred), return_result(this);
72 GotoIf(TaggedIsSmi(result), &if_notobject);
73 TNode<HeapObject> heap_object_result = CAST(result);
74 TNode<Map> result_map = LoadMap(heap_object_result);
75
76 if (fast_iterator_result_map) {
77 // Fast iterator result case:
78 Label if_generic(this);
79
80 // 4. Return result.
81 GotoIfNot(TaggedEqual(result_map, *fast_iterator_result_map), &if_generic);
82
83 // IteratorComplete
84 // 2. Return ToBoolean(? Get(iterResult, "done")).
85 TNode<Object> done =
86 LoadObjectField(heap_object_result, JSIteratorResult::kDoneOffset);
87 BranchIfToBooleanIsTrue(done, if_done, &return_result);
88
89 BIND(&if_generic);
90 }
91
92 // Generic iterator result case:
93 {
94 // 3. If Type(result) is not Object, throw a TypeError exception.
95 GotoIfNot(IsJSReceiverMap(result_map), &if_notobject);
96
97 // IteratorComplete
98 // 2. Return ToBoolean(? Get(iterResult, "done")).
99 TNode<Object> done =
100 GetProperty(context, heap_object_result, factory()->done_string());
101 BranchIfToBooleanIsTrue(done, if_done, &return_result);
102 }
103
104 BIND(&if_notobject);
105 CallRuntime(Runtime::kThrowIteratorResultNotAnObject, context, result);
106 Unreachable();
107
108 BIND(&return_result);
109 return CAST(heap_object_result);
110 }
111
IteratorValue(TNode<Context> context,TNode<JSReceiver> result,base::Optional<TNode<Map>> fast_iterator_result_map)112 TNode<Object> IteratorBuiltinsAssembler::IteratorValue(
113 TNode<Context> context, TNode<JSReceiver> result,
114 base::Optional<TNode<Map>> fast_iterator_result_map) {
115 Label exit(this);
116 TVARIABLE(Object, var_value);
117 if (fast_iterator_result_map) {
118 // Fast iterator result case:
119 Label if_generic(this);
120 TNode<Map> map = LoadMap(result);
121 GotoIfNot(TaggedEqual(map, *fast_iterator_result_map), &if_generic);
122 var_value = LoadObjectField(result, JSIteratorResult::kValueOffset);
123 Goto(&exit);
124
125 BIND(&if_generic);
126 }
127
128 // Generic iterator result case:
129 var_value = GetProperty(context, result, factory()->value_string());
130 Goto(&exit);
131
132 BIND(&exit);
133 return var_value.value();
134 }
135
IterableToList(TNode<Context> context,TNode<Object> iterable,TNode<Object> iterator_fn)136 TNode<JSArray> IteratorBuiltinsAssembler::IterableToList(
137 TNode<Context> context, TNode<Object> iterable, TNode<Object> iterator_fn) {
138 GrowableFixedArray values(state());
139 FillFixedArrayFromIterable(context, iterable, iterator_fn, &values);
140 return values.ToJSArray(context);
141 }
142
IterableToFixedArray(TNode<Context> context,TNode<Object> iterable,TNode<Object> iterator_fn)143 TNode<FixedArray> IteratorBuiltinsAssembler::IterableToFixedArray(
144 TNode<Context> context, TNode<Object> iterable, TNode<Object> iterator_fn) {
145 GrowableFixedArray values(state());
146 FillFixedArrayFromIterable(context, iterable, iterator_fn, &values);
147 TNode<FixedArray> new_array = values.ToFixedArray();
148 return new_array;
149 }
150
FillFixedArrayFromIterable(TNode<Context> context,TNode<Object> iterable,TNode<Object> iterator_fn,GrowableFixedArray * values)151 void IteratorBuiltinsAssembler::FillFixedArrayFromIterable(
152 TNode<Context> context, TNode<Object> iterable, TNode<Object> iterator_fn,
153 GrowableFixedArray* values) {
154 // 1. Let iteratorRecord be ? GetIterator(items, method).
155 IteratorRecord iterator_record = GetIterator(context, iterable, iterator_fn);
156
157 // 2. Let values be a new empty List.
158
159 // The GrowableFixedArray has already been created. It's ok if we do this step
160 // out of order, since creating an empty List is not observable.
161
162 Label loop_start(this, {values->var_array(), values->var_length(),
163 values->var_capacity()}),
164 done(this);
165 Goto(&loop_start);
166 // 3. Let next be true.
167 // 4. Repeat, while next is not false
168 BIND(&loop_start);
169 {
170 // a. Set next to ? IteratorStep(iteratorRecord).
171 TNode<JSReceiver> next = IteratorStep(context, iterator_record, &done);
172 // b. If next is not false, then
173 // i. Let nextValue be ? IteratorValue(next).
174 TNode<Object> next_value = IteratorValue(context, next);
175 // ii. Append nextValue to the end of the List values.
176 values->Push(next_value);
177 Goto(&loop_start);
178 }
179
180 BIND(&done);
181 }
182
TF_BUILTIN(IterableToList,IteratorBuiltinsAssembler)183 TF_BUILTIN(IterableToList, IteratorBuiltinsAssembler) {
184 auto context = Parameter<Context>(Descriptor::kContext);
185 auto iterable = Parameter<Object>(Descriptor::kIterable);
186 auto iterator_fn = Parameter<Object>(Descriptor::kIteratorFn);
187
188 Return(IterableToList(context, iterable, iterator_fn));
189 }
190
TF_BUILTIN(IterableToFixedArray,IteratorBuiltinsAssembler)191 TF_BUILTIN(IterableToFixedArray, IteratorBuiltinsAssembler) {
192 auto context = Parameter<Context>(Descriptor::kContext);
193 auto iterable = Parameter<Object>(Descriptor::kIterable);
194 auto iterator_fn = Parameter<Object>(Descriptor::kIteratorFn);
195
196 Return(IterableToFixedArray(context, iterable, iterator_fn));
197 }
198
TF_BUILTIN(IterableToFixedArrayForWasm,IteratorBuiltinsAssembler)199 TF_BUILTIN(IterableToFixedArrayForWasm, IteratorBuiltinsAssembler) {
200 auto context = Parameter<Context>(Descriptor::kContext);
201 auto iterable = Parameter<Object>(Descriptor::kIterable);
202 auto expected_length = Parameter<Smi>(Descriptor::kExpectedLength);
203
204 TNode<Object> iterator_fn = GetIteratorMethod(context, iterable);
205 GrowableFixedArray values(state());
206
207 Label done(this);
208
209 FillFixedArrayFromIterable(context, iterable, iterator_fn, &values);
210
211 GotoIf(WordEqual(SmiUntag(expected_length), values.var_length()->value()),
212 &done);
213 Return(CallRuntime(
214 Runtime::kThrowTypeError, context,
215 SmiConstant(MessageTemplate::kWasmTrapMultiReturnLengthMismatch)));
216
217 BIND(&done);
218 Return(values.var_array()->value());
219 }
220
StringListFromIterable(TNode<Context> context,TNode<Object> iterable)221 TNode<JSArray> IteratorBuiltinsAssembler::StringListFromIterable(
222 TNode<Context> context, TNode<Object> iterable) {
223 Label done(this);
224 GrowableFixedArray list(state());
225 // 1. If iterable is undefined, then
226 // a. Return a new empty List.
227 GotoIf(IsUndefined(iterable), &done);
228
229 // 2. Let iteratorRecord be ? GetIterator(items).
230 IteratorRecord iterator_record = GetIterator(context, iterable);
231
232 // 3. Let list be a new empty List.
233
234 Label loop_start(this,
235 {list.var_array(), list.var_length(), list.var_capacity()});
236 Goto(&loop_start);
237 // 4. Let next be true.
238 // 5. Repeat, while next is not false
239 Label if_isnotstringtype(this, Label::kDeferred),
240 if_exception(this, Label::kDeferred);
241 BIND(&loop_start);
242 {
243 // a. Set next to ? IteratorStep(iteratorRecord).
244 TNode<JSReceiver> next = IteratorStep(context, iterator_record, &done);
245 // b. If next is not false, then
246 // i. Let nextValue be ? IteratorValue(next).
247 TNode<Object> next_value = IteratorValue(context, next);
248 // ii. If Type(nextValue) is not String, then
249 GotoIf(TaggedIsSmi(next_value), &if_isnotstringtype);
250 TNode<Uint16T> next_value_type = LoadInstanceType(CAST(next_value));
251 GotoIfNot(IsStringInstanceType(next_value_type), &if_isnotstringtype);
252 // iii. Append nextValue to the end of the List list.
253 list.Push(next_value);
254 Goto(&loop_start);
255 // 5.b.ii
256 BIND(&if_isnotstringtype);
257 {
258 // 1. Let error be ThrowCompletion(a newly created TypeError object).
259 TVARIABLE(Object, var_exception);
260 {
261 compiler::ScopedExceptionHandler handler(this, &if_exception,
262 &var_exception);
263 CallRuntime(Runtime::kThrowTypeError, context,
264 SmiConstant(MessageTemplate::kIterableYieldedNonString),
265 next_value);
266 }
267 Unreachable();
268
269 // 2. Return ? IteratorClose(iteratorRecord, error).
270 BIND(&if_exception);
271 IteratorCloseOnException(context, iterator_record);
272 CallRuntime(Runtime::kReThrow, context, var_exception.value());
273 Unreachable();
274 }
275 }
276
277 BIND(&done);
278 // 6. Return list.
279 return list.ToJSArray(context);
280 }
281
TF_BUILTIN(StringListFromIterable,IteratorBuiltinsAssembler)282 TF_BUILTIN(StringListFromIterable, IteratorBuiltinsAssembler) {
283 auto context = Parameter<Context>(Descriptor::kContext);
284 auto iterable = Parameter<Object>(Descriptor::kIterable);
285
286 Return(StringListFromIterable(context, iterable));
287 }
288
289 // This builtin always returns a new JSArray and is thus safe to use even in the
290 // presence of code that may call back into user-JS. This builtin will take the
291 // fast path if the iterable is a fast array and the Array prototype and the
292 // Symbol.iterator is untouched. The fast path skips the iterator and copies the
293 // backing store to the new array. Note that if the array has holes, the holes
294 // will be copied to the new array, which is inconsistent with the behavior of
295 // an actual iteration, where holes should be replaced with undefined (if the
296 // prototype has no elements). To maintain the correct behavior for holey
297 // arrays, use the builtins IterableToList or IterableToListWithSymbolLookup.
TF_BUILTIN(IterableToListMayPreserveHoles,IteratorBuiltinsAssembler)298 TF_BUILTIN(IterableToListMayPreserveHoles, IteratorBuiltinsAssembler) {
299 auto context = Parameter<Context>(Descriptor::kContext);
300 auto iterable = Parameter<Object>(Descriptor::kIterable);
301 auto iterator_fn = Parameter<Object>(Descriptor::kIteratorFn);
302
303 Label slow_path(this);
304
305 GotoIfNot(IsFastJSArrayWithNoCustomIteration(context, iterable), &slow_path);
306
307 // The fast path will copy holes to the new array.
308 TailCallBuiltin(Builtins::kCloneFastJSArray, context, iterable);
309
310 BIND(&slow_path);
311 TailCallBuiltin(Builtins::kIterableToList, context, iterable, iterator_fn);
312 }
313
FastIterableToList(TNode<Context> context,TNode<Object> iterable,TVariable<JSArray> * var_result,Label * slow)314 void IteratorBuiltinsAssembler::FastIterableToList(
315 TNode<Context> context, TNode<Object> iterable,
316 TVariable<JSArray>* var_result, Label* slow) {
317 Label done(this), check_string(this), check_map(this), check_set(this);
318
319 GotoIfNot(
320 Word32Or(IsFastJSArrayWithNoCustomIteration(context, iterable),
321 IsFastJSArrayForReadWithNoCustomIteration(context, iterable)),
322 &check_string);
323
324 // Fast path for fast JSArray.
325 *var_result = CAST(
326 CallBuiltin(Builtins::kCloneFastJSArrayFillingHoles, context, iterable));
327 Goto(&done);
328
329 BIND(&check_string);
330 {
331 Label string_maybe_fast_call(this);
332 StringBuiltinsAssembler string_assembler(state());
333 string_assembler.BranchIfStringPrimitiveWithNoCustomIteration(
334 iterable, context, &string_maybe_fast_call, &check_map);
335
336 BIND(&string_maybe_fast_call);
337 const TNode<IntPtrT> length = LoadStringLengthAsWord(CAST(iterable));
338 // Use string length as conservative approximation of number of codepoints.
339 GotoIf(
340 IntPtrGreaterThan(length, IntPtrConstant(JSArray::kMaxFastArrayLength)),
341 slow);
342 *var_result = CAST(CallBuiltin(Builtins::kStringToList, context, iterable));
343 Goto(&done);
344 }
345
346 BIND(&check_map);
347 {
348 Label map_fast_call(this);
349 BranchIfIterableWithOriginalKeyOrValueMapIterator(
350 state(), iterable, context, &map_fast_call, &check_set);
351
352 BIND(&map_fast_call);
353 *var_result =
354 CAST(CallBuiltin(Builtins::kMapIteratorToList, context, iterable));
355 Goto(&done);
356 }
357
358 BIND(&check_set);
359 {
360 Label set_fast_call(this);
361 BranchIfIterableWithOriginalValueSetIterator(state(), iterable, context,
362 &set_fast_call, slow);
363
364 BIND(&set_fast_call);
365 *var_result =
366 CAST(CallBuiltin(Builtins::kSetOrSetIteratorToList, context, iterable));
367 Goto(&done);
368 }
369
370 BIND(&done);
371 }
372
FastIterableToList(TNode<Context> context,TNode<Object> iterable,Label * slow)373 TNode<JSArray> IteratorBuiltinsAssembler::FastIterableToList(
374 TNode<Context> context, TNode<Object> iterable, Label* slow) {
375 TVARIABLE(JSArray, var_fast_result);
376 FastIterableToList(context, iterable, &var_fast_result, slow);
377 return var_fast_result.value();
378 }
379
380 // This builtin loads the property Symbol.iterator as the iterator, and has fast
381 // paths for fast arrays, for primitive strings, for sets and set iterators, and
382 // for map iterators. These fast paths will only be taken if Symbol.iterator and
383 // the Iterator prototype are not modified in a way that changes the original
384 // iteration behavior.
385 // * In case of fast holey arrays, holes will be converted to undefined to
386 // reflect iteration semantics. Note that replacement by undefined is only
387 // correct when the NoElements protector is valid.
388 // * In case of map/set iterators, there is an additional requirement that the
389 // iterator is not partially consumed. To be spec-compliant, after spreading
390 // the iterator is set to be exhausted.
TF_BUILTIN(IterableToListWithSymbolLookup,IteratorBuiltinsAssembler)391 TF_BUILTIN(IterableToListWithSymbolLookup, IteratorBuiltinsAssembler) {
392 auto context = Parameter<Context>(Descriptor::kContext);
393 auto iterable = Parameter<Object>(Descriptor::kIterable);
394
395 Label slow_path(this);
396
397 GotoIfForceSlowPath(&slow_path);
398
399 TVARIABLE(JSArray, var_result);
400 FastIterableToList(context, iterable, &var_result, &slow_path);
401 Return(var_result.value());
402
403 BIND(&slow_path);
404 {
405 TNode<Object> iterator_fn = GetIteratorMethod(context, iterable);
406 TailCallBuiltin(Builtins::kIterableToList, context, iterable, iterator_fn);
407 }
408 }
409
TF_BUILTIN(GetIteratorWithFeedbackLazyDeoptContinuation,IteratorBuiltinsAssembler)410 TF_BUILTIN(GetIteratorWithFeedbackLazyDeoptContinuation,
411 IteratorBuiltinsAssembler) {
412 auto context = Parameter<Context>(Descriptor::kContext);
413 auto receiver = Parameter<Object>(Descriptor::kReceiver);
414 // TODO(v8:10047): Use TaggedIndex here once TurboFan supports it.
415 auto call_slot_smi = Parameter<Smi>(Descriptor::kCallSlot);
416 TNode<TaggedIndex> call_slot = SmiToTaggedIndex(call_slot_smi);
417 auto feedback = Parameter<FeedbackVector>(Descriptor::kFeedback);
418 auto iterator_method = Parameter<Object>(Descriptor::kResult);
419
420 TNode<Object> result =
421 CallBuiltin(Builtins::kCallIteratorWithFeedback, context, receiver,
422 iterator_method, call_slot, feedback);
423 Return(result);
424 }
425
426 // This builtin creates a FixedArray based on an Iterable and doesn't have a
427 // fast path for anything.
TF_BUILTIN(IterableToFixedArrayWithSymbolLookupSlow,IteratorBuiltinsAssembler)428 TF_BUILTIN(IterableToFixedArrayWithSymbolLookupSlow,
429 IteratorBuiltinsAssembler) {
430 auto context = Parameter<Context>(Descriptor::kContext);
431 auto iterable = Parameter<Object>(Descriptor::kIterable);
432
433 TNode<Object> iterator_fn = GetIteratorMethod(context, iterable);
434 TailCallBuiltin(Builtins::kIterableToFixedArray, context, iterable,
435 iterator_fn);
436 }
437
438 } // namespace internal
439 } // namespace v8
440