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
IteratorCloseOnException(TNode<Context> context,const IteratorRecord & iterator,Label * if_exception,TVariable<Object> * exception)136 void IteratorBuiltinsAssembler::IteratorCloseOnException(
137 TNode<Context> context, const IteratorRecord& iterator, Label* if_exception,
138 TVariable<Object>* exception) {
139 // Perform ES #sec-iteratorclose when an exception occurs. This simpler
140 // algorithm does not include redundant steps which are never reachable from
141 // the spec IteratorClose algorithm.
142 DCHECK((if_exception != nullptr && exception != nullptr));
143 CSA_ASSERT(this, IsNotTheHole(exception->value()));
144 CSA_ASSERT(this, IsJSReceiver(iterator.object));
145
146 // Let return be ? GetMethod(iterator, "return").
147 TNode<Object> method;
148 {
149 compiler::ScopedExceptionHandler handler(this, if_exception, exception);
150 method = GetProperty(context, iterator.object, factory()->return_string());
151 }
152
153 // If return is undefined, return Completion(completion).
154 GotoIf(Word32Or(IsUndefined(method), IsNull(method)), if_exception);
155
156 {
157 // Let innerResult be Call(return, iterator, « »).
158 // If an exception occurs, the original exception remains bound.
159 compiler::ScopedExceptionHandler handler(this, if_exception, nullptr);
160 Call(context, method, iterator.object);
161 }
162
163 // (If completion.[[Type]] is throw) return Completion(completion).
164 Goto(if_exception);
165 }
166
IteratorCloseOnException(TNode<Context> context,const IteratorRecord & iterator,TNode<Object> exception)167 void IteratorBuiltinsAssembler::IteratorCloseOnException(
168 TNode<Context> context, const IteratorRecord& iterator,
169 TNode<Object> exception) {
170 Label rethrow(this, Label::kDeferred);
171 TVARIABLE(Object, exception_variable, exception);
172 IteratorCloseOnException(context, iterator, &rethrow, &exception_variable);
173
174 BIND(&rethrow);
175 CallRuntime(Runtime::kReThrow, context, exception_variable.value());
176 Unreachable();
177 }
178
IterableToList(TNode<Context> context,TNode<Object> iterable,TNode<Object> iterator_fn)179 TNode<JSArray> IteratorBuiltinsAssembler::IterableToList(
180 TNode<Context> context, TNode<Object> iterable, TNode<Object> iterator_fn) {
181 // 1. Let iteratorRecord be ? GetIterator(items, method).
182 IteratorRecord iterator_record = GetIterator(context, iterable, iterator_fn);
183
184 // 2. Let values be a new empty List.
185 GrowableFixedArray values(state());
186
187 Label loop_start(
188 this, {values.var_array(), values.var_length(), values.var_capacity()}),
189 done(this);
190 Goto(&loop_start);
191 // 3. Let next be true.
192 // 4. Repeat, while next is not false
193 BIND(&loop_start);
194 {
195 // a. Set next to ? IteratorStep(iteratorRecord).
196 TNode<JSReceiver> next = IteratorStep(context, iterator_record, &done);
197 // b. If next is not false, then
198 // i. Let nextValue be ? IteratorValue(next).
199 TNode<Object> next_value = IteratorValue(context, next);
200 // ii. Append nextValue to the end of the List values.
201 values.Push(next_value);
202 Goto(&loop_start);
203 }
204
205 BIND(&done);
206 return values.ToJSArray(context);
207 }
208
TF_BUILTIN(IterableToList,IteratorBuiltinsAssembler)209 TF_BUILTIN(IterableToList, IteratorBuiltinsAssembler) {
210 TNode<Context> context = CAST(Parameter(Descriptor::kContext));
211 TNode<Object> iterable = CAST(Parameter(Descriptor::kIterable));
212 TNode<Object> iterator_fn = CAST(Parameter(Descriptor::kIteratorFn));
213
214 Return(IterableToList(context, iterable, iterator_fn));
215 }
216
TF_BUILTIN(IterableToFixedArrayForWasm,IteratorBuiltinsAssembler)217 TF_BUILTIN(IterableToFixedArrayForWasm, IteratorBuiltinsAssembler) {
218 TNode<Context> context = CAST(Parameter(Descriptor::kContext));
219 TNode<Object> iterable = CAST(Parameter(Descriptor::kIterable));
220 TNode<Smi> expected_length = CAST(Parameter(Descriptor::kExpectedLength));
221
222 TNode<Object> iterator_fn = GetIteratorMethod(context, iterable);
223
224 IteratorRecord iterator_record = GetIterator(context, iterable, iterator_fn);
225
226 GrowableFixedArray values(state());
227
228 Label loop_start(
229 this, {values.var_array(), values.var_length(), values.var_capacity()}),
230 compare_length(this), done(this);
231 Goto(&loop_start);
232 BIND(&loop_start);
233 {
234 TNode<JSReceiver> next =
235 IteratorStep(context, iterator_record, &compare_length);
236 TNode<Object> next_value = IteratorValue(context, next);
237 values.Push(next_value);
238 Goto(&loop_start);
239 }
240
241 BIND(&compare_length);
242 GotoIf(WordEqual(SmiUntag(expected_length), values.var_length()->value()),
243 &done);
244 Return(CallRuntime(
245 Runtime::kThrowTypeError, context,
246 SmiConstant(MessageTemplate::kWasmTrapMultiReturnLengthMismatch)));
247
248 BIND(&done);
249 Return(values.var_array()->value());
250 }
251
StringListFromIterable(TNode<Context> context,TNode<Object> iterable)252 TNode<JSArray> IteratorBuiltinsAssembler::StringListFromIterable(
253 TNode<Context> context, TNode<Object> iterable) {
254 Label done(this);
255 GrowableFixedArray list(state());
256 // 1. If iterable is undefined, then
257 // a. Return a new empty List.
258 GotoIf(IsUndefined(iterable), &done);
259
260 // 2. Let iteratorRecord be ? GetIterator(items).
261 IteratorRecord iterator_record = GetIterator(context, iterable);
262
263 // 3. Let list be a new empty List.
264
265 Label loop_start(this,
266 {list.var_array(), list.var_length(), list.var_capacity()});
267 Goto(&loop_start);
268 // 4. Let next be true.
269 // 5. Repeat, while next is not false
270 Label if_isnotstringtype(this, Label::kDeferred),
271 if_exception(this, Label::kDeferred);
272 BIND(&loop_start);
273 {
274 // a. Set next to ? IteratorStep(iteratorRecord).
275 TNode<JSReceiver> next = IteratorStep(context, iterator_record, &done);
276 // b. If next is not false, then
277 // i. Let nextValue be ? IteratorValue(next).
278 TNode<Object> next_value = IteratorValue(context, next);
279 // ii. If Type(nextValue) is not String, then
280 GotoIf(TaggedIsSmi(next_value), &if_isnotstringtype);
281 TNode<Uint16T> next_value_type = LoadInstanceType(CAST(next_value));
282 GotoIfNot(IsStringInstanceType(next_value_type), &if_isnotstringtype);
283 // iii. Append nextValue to the end of the List list.
284 list.Push(next_value);
285 Goto(&loop_start);
286 // 5.b.ii
287 BIND(&if_isnotstringtype);
288 {
289 // 1. Let error be ThrowCompletion(a newly created TypeError object).
290 TVARIABLE(Object, var_exception);
291 {
292 compiler::ScopedExceptionHandler handler(this, &if_exception,
293 &var_exception);
294 CallRuntime(Runtime::kThrowTypeError, context,
295 SmiConstant(MessageTemplate::kIterableYieldedNonString),
296 next_value);
297 }
298 Unreachable();
299
300 // 2. Return ? IteratorClose(iteratorRecord, error).
301 BIND(&if_exception);
302 IteratorCloseOnException(context, iterator_record, var_exception.value());
303 }
304 }
305
306 BIND(&done);
307 // 6. Return list.
308 return list.ToJSArray(context);
309 }
310
TF_BUILTIN(StringListFromIterable,IteratorBuiltinsAssembler)311 TF_BUILTIN(StringListFromIterable, IteratorBuiltinsAssembler) {
312 TNode<Context> context = CAST(Parameter(Descriptor::kContext));
313 TNode<Object> iterable = CAST(Parameter(Descriptor::kIterable));
314
315 Return(StringListFromIterable(context, iterable));
316 }
317
318 // This builtin always returns a new JSArray and is thus safe to use even in the
319 // presence of code that may call back into user-JS. This builtin will take the
320 // fast path if the iterable is a fast array and the Array prototype and the
321 // Symbol.iterator is untouched. The fast path skips the iterator and copies the
322 // backing store to the new array. Note that if the array has holes, the holes
323 // will be copied to the new array, which is inconsistent with the behavior of
324 // an actual iteration, where holes should be replaced with undefined (if the
325 // prototype has no elements). To maintain the correct behavior for holey
326 // arrays, use the builtins IterableToList or IterableToListWithSymbolLookup.
TF_BUILTIN(IterableToListMayPreserveHoles,IteratorBuiltinsAssembler)327 TF_BUILTIN(IterableToListMayPreserveHoles, IteratorBuiltinsAssembler) {
328 TNode<Context> context = CAST(Parameter(Descriptor::kContext));
329 TNode<Object> iterable = CAST(Parameter(Descriptor::kIterable));
330 TNode<Object> iterator_fn = CAST(Parameter(Descriptor::kIteratorFn));
331
332 Label slow_path(this);
333
334 GotoIfNot(IsFastJSArrayWithNoCustomIteration(context, iterable), &slow_path);
335
336 // The fast path will copy holes to the new array.
337 TailCallBuiltin(Builtins::kCloneFastJSArray, context, iterable);
338
339 BIND(&slow_path);
340 TailCallBuiltin(Builtins::kIterableToList, context, iterable, iterator_fn);
341 }
342
FastIterableToList(TNode<Context> context,TNode<Object> iterable,TVariable<JSArray> * var_result,Label * slow)343 void IteratorBuiltinsAssembler::FastIterableToList(
344 TNode<Context> context, TNode<Object> iterable,
345 TVariable<JSArray>* var_result, Label* slow) {
346 Label done(this), check_string(this), check_map(this), check_set(this);
347
348 GotoIfNot(
349 Word32Or(IsFastJSArrayWithNoCustomIteration(context, iterable),
350 IsFastJSArrayForReadWithNoCustomIteration(context, iterable)),
351 &check_string);
352
353 // Fast path for fast JSArray.
354 *var_result = CAST(
355 CallBuiltin(Builtins::kCloneFastJSArrayFillingHoles, context, iterable));
356 Goto(&done);
357
358 BIND(&check_string);
359 {
360 Label string_maybe_fast_call(this);
361 StringBuiltinsAssembler string_assembler(state());
362 string_assembler.BranchIfStringPrimitiveWithNoCustomIteration(
363 iterable, context, &string_maybe_fast_call, &check_map);
364
365 BIND(&string_maybe_fast_call);
366 const TNode<IntPtrT> length = LoadStringLengthAsWord(CAST(iterable));
367 // Use string length as conservative approximation of number of codepoints.
368 GotoIf(
369 IntPtrGreaterThan(length, IntPtrConstant(JSArray::kMaxFastArrayLength)),
370 slow);
371 *var_result = CAST(CallBuiltin(Builtins::kStringToList, context, iterable));
372 Goto(&done);
373 }
374
375 BIND(&check_map);
376 {
377 Label map_fast_call(this);
378 BranchIfIterableWithOriginalKeyOrValueMapIterator(
379 state(), iterable, context, &map_fast_call, &check_set);
380
381 BIND(&map_fast_call);
382 *var_result =
383 CAST(CallBuiltin(Builtins::kMapIteratorToList, context, iterable));
384 Goto(&done);
385 }
386
387 BIND(&check_set);
388 {
389 Label set_fast_call(this);
390 BranchIfIterableWithOriginalValueSetIterator(state(), iterable, context,
391 &set_fast_call, slow);
392
393 BIND(&set_fast_call);
394 *var_result =
395 CAST(CallBuiltin(Builtins::kSetOrSetIteratorToList, context, iterable));
396 Goto(&done);
397 }
398
399 BIND(&done);
400 }
401
FastIterableToList(TNode<Context> context,TNode<Object> iterable,Label * slow)402 TNode<JSArray> IteratorBuiltinsAssembler::FastIterableToList(
403 TNode<Context> context, TNode<Object> iterable, Label* slow) {
404 TVARIABLE(JSArray, var_fast_result);
405 FastIterableToList(context, iterable, &var_fast_result, slow);
406 return var_fast_result.value();
407 }
408
409 // This builtin loads the property Symbol.iterator as the iterator, and has fast
410 // paths for fast arrays, for primitive strings, for sets and set iterators, and
411 // for map iterators. These fast paths will only be taken if Symbol.iterator and
412 // the Iterator prototype are not modified in a way that changes the original
413 // iteration behavior.
414 // * In case of fast holey arrays, holes will be converted to undefined to
415 // reflect iteration semantics. Note that replacement by undefined is only
416 // correct when the NoElements protector is valid.
417 // * In case of map/set iterators, there is an additional requirement that the
418 // iterator is not partially consumed. To be spec-compliant, after spreading
419 // the iterator is set to be exhausted.
TF_BUILTIN(IterableToListWithSymbolLookup,IteratorBuiltinsAssembler)420 TF_BUILTIN(IterableToListWithSymbolLookup, IteratorBuiltinsAssembler) {
421 TNode<Context> context = CAST(Parameter(Descriptor::kContext));
422 TNode<Object> iterable = CAST(Parameter(Descriptor::kIterable));
423
424 Label slow_path(this);
425
426 GotoIfForceSlowPath(&slow_path);
427
428 TVARIABLE(JSArray, var_result);
429 FastIterableToList(context, iterable, &var_result, &slow_path);
430 Return(var_result.value());
431
432 BIND(&slow_path);
433 {
434 TNode<Object> iterator_fn = GetIteratorMethod(context, iterable);
435 TailCallBuiltin(Builtins::kIterableToList, context, iterable, iterator_fn);
436 }
437 }
438
TF_BUILTIN(GetIteratorWithFeedbackLazyDeoptContinuation,IteratorBuiltinsAssembler)439 TF_BUILTIN(GetIteratorWithFeedbackLazyDeoptContinuation,
440 IteratorBuiltinsAssembler) {
441 TNode<Context> context = CAST(Parameter(Descriptor::kContext));
442 TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));
443 // TODO(v8:10047): Use TaggedIndex here once TurboFan supports it.
444 TNode<Smi> call_slot_smi = CAST(Parameter(Descriptor::kCallSlot));
445 TNode<TaggedIndex> call_slot = SmiToTaggedIndex(call_slot_smi);
446 TNode<FeedbackVector> feedback = CAST(Parameter(Descriptor::kFeedback));
447 TNode<Object> iterator_method = CAST(Parameter(Descriptor::kResult));
448
449 TNode<Object> result =
450 CallBuiltin(Builtins::kCallIteratorWithFeedback, context, receiver,
451 iterator_method, call_slot, feedback);
452 Return(result);
453 }
454
455 } // namespace internal
456 } // namespace v8
457