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