• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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