Line data Source code
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/code-stub-assembler.h"
13 : #include "src/heap/factory-inl.h"
14 : #include "torque-generated/builtins-base-from-dsl-gen.h"
15 :
16 : namespace v8 {
17 : namespace internal {
18 :
19 : typedef IteratorBuiltinsFromDSLAssembler::IteratorRecord IteratorRecord;
20 :
21 : using compiler::Node;
22 :
23 560 : TNode<Object> IteratorBuiltinsAssembler::GetIteratorMethod(Node* context,
24 : Node* object) {
25 1120 : return GetProperty(context, object, factory()->iterator_symbol());
26 : }
27 :
28 448 : IteratorRecord IteratorBuiltinsAssembler::GetIterator(Node* context,
29 : Node* object,
30 : Label* if_exception,
31 : Variable* exception) {
32 896 : Node* method = GetIteratorMethod(context, object);
33 448 : return GetIterator(context, object, method, if_exception, exception);
34 : }
35 :
36 560 : IteratorRecord IteratorBuiltinsAssembler::GetIterator(Node* context,
37 : Node* object,
38 : Node* method,
39 : Label* if_exception,
40 : Variable* exception) {
41 560 : GotoIfException(method, if_exception, exception);
42 :
43 560 : Label if_not_callable(this, Label::kDeferred), if_callable(this);
44 1120 : GotoIf(TaggedIsSmi(method), &if_not_callable);
45 1120 : Branch(IsCallable(method), &if_callable, &if_not_callable);
46 :
47 560 : BIND(&if_not_callable);
48 : {
49 : Node* ret = CallRuntime(Runtime::kThrowIteratorError, context, object);
50 560 : GotoIfException(ret, if_exception, exception);
51 560 : Unreachable();
52 : }
53 :
54 560 : BIND(&if_callable);
55 : {
56 560 : Callable callable = CodeFactory::Call(isolate());
57 560 : Node* iterator = CallJS(callable, context, method, object);
58 560 : GotoIfException(iterator, if_exception, exception);
59 :
60 560 : Label get_next(this), if_notobject(this, Label::kDeferred);
61 1120 : GotoIf(TaggedIsSmi(iterator), &if_notobject);
62 1120 : Branch(IsJSReceiver(iterator), &get_next, &if_notobject);
63 :
64 560 : BIND(&if_notobject);
65 : {
66 : Node* ret = CallRuntime(Runtime::kThrowSymbolIteratorInvalid, context);
67 560 : GotoIfException(ret, if_exception, exception);
68 560 : Unreachable();
69 : }
70 :
71 560 : BIND(&get_next);
72 1680 : Node* const next = GetProperty(context, iterator, factory()->next_string());
73 560 : GotoIfException(next, if_exception, exception);
74 :
75 : return IteratorRecord{TNode<JSReceiver>::UncheckedCast(iterator),
76 560 : TNode<Object>::UncheckedCast(next)};
77 : }
78 : }
79 :
80 560 : TNode<Object> IteratorBuiltinsAssembler::IteratorStep(
81 : Node* context, const IteratorRecord& iterator, Label* if_done,
82 : Node* fast_iterator_result_map, Label* if_exception, Variable* exception) {
83 : DCHECK_NOT_NULL(if_done);
84 : // 1. a. Let result be ? Invoke(iterator, "next", « »).
85 560 : Callable callable = CodeFactory::Call(isolate());
86 560 : Node* result = CallJS(callable, context, iterator.next, iterator.object);
87 560 : GotoIfException(result, if_exception, exception);
88 :
89 : // 3. If Type(result) is not Object, throw a TypeError exception.
90 560 : Label if_notobject(this, Label::kDeferred), return_result(this);
91 1120 : GotoIf(TaggedIsSmi(result), &if_notobject);
92 1120 : Node* result_map = LoadMap(result);
93 :
94 560 : if (fast_iterator_result_map != nullptr) {
95 : // Fast iterator result case:
96 504 : Label if_generic(this);
97 :
98 : // 4. Return result.
99 1008 : GotoIfNot(WordEqual(result_map, fast_iterator_result_map), &if_generic);
100 :
101 : // IteratorComplete
102 : // 2. Return ToBoolean(? Get(iterResult, "done")).
103 : Node* done = LoadObjectField(result, JSIteratorResult::kDoneOffset);
104 504 : BranchIfToBooleanIsTrue(done, if_done, &return_result);
105 :
106 504 : BIND(&if_generic);
107 : }
108 :
109 : // Generic iterator result case:
110 : {
111 : // 3. If Type(result) is not Object, throw a TypeError exception.
112 1120 : GotoIfNot(IsJSReceiverMap(result_map), &if_notobject);
113 :
114 : // IteratorComplete
115 : // 2. Return ToBoolean(? Get(iterResult, "done")).
116 1680 : Node* done = GetProperty(context, result, factory()->done_string());
117 560 : GotoIfException(done, if_exception, exception);
118 560 : BranchIfToBooleanIsTrue(done, if_done, &return_result);
119 : }
120 :
121 560 : BIND(&if_notobject);
122 : {
123 : Node* ret =
124 : CallRuntime(Runtime::kThrowIteratorResultNotAnObject, context, result);
125 560 : GotoIfException(ret, if_exception, exception);
126 560 : Unreachable();
127 : }
128 :
129 560 : BIND(&return_result);
130 560 : return UncheckedCast<Object>(result);
131 : }
132 :
133 560 : Node* IteratorBuiltinsAssembler::IteratorValue(Node* context, Node* result,
134 : Node* fast_iterator_result_map,
135 : Label* if_exception,
136 : Variable* exception) {
137 : CSA_ASSERT(this, IsJSReceiver(result));
138 :
139 1120 : Label exit(this);
140 1120 : VARIABLE(var_value, MachineRepresentation::kTagged);
141 560 : if (fast_iterator_result_map != nullptr) {
142 : // Fast iterator result case:
143 504 : Label if_generic(this);
144 1008 : Node* map = LoadMap(result);
145 1008 : GotoIfNot(WordEqual(map, fast_iterator_result_map), &if_generic);
146 504 : var_value.Bind(LoadObjectField(result, JSIteratorResult::kValueOffset));
147 504 : Goto(&exit);
148 :
149 504 : BIND(&if_generic);
150 : }
151 :
152 : // Generic iterator result case:
153 : {
154 1680 : Node* value = GetProperty(context, result, factory()->value_string());
155 560 : GotoIfException(value, if_exception, exception);
156 560 : var_value.Bind(value);
157 560 : Goto(&exit);
158 : }
159 :
160 560 : BIND(&exit);
161 1120 : return var_value.value();
162 : }
163 :
164 504 : void IteratorBuiltinsAssembler::IteratorCloseOnException(
165 : Node* context, const IteratorRecord& iterator, Label* if_exception,
166 : Variable* exception) {
167 : // Perform ES #sec-iteratorclose when an exception occurs. This simpler
168 : // algorithm does not include redundant steps which are never reachable from
169 : // the spec IteratorClose algorithm.
170 : DCHECK((if_exception != nullptr && exception != nullptr));
171 : CSA_ASSERT(this, IsNotTheHole(exception->value()));
172 : CSA_ASSERT(this, IsJSReceiver(iterator.object));
173 :
174 : // Let return be ? GetMethod(iterator, "return").
175 : Node* method =
176 1512 : GetProperty(context, iterator.object, factory()->return_string());
177 504 : GotoIfException(method, if_exception, exception);
178 :
179 : // If return is undefined, return Completion(completion).
180 2016 : GotoIf(Word32Or(IsUndefined(method), IsNull(method)), if_exception);
181 :
182 : {
183 : // Let innerResult be Call(return, iterator, « »).
184 : // If an exception occurs, the original exception remains bound
185 : Node* inner_result =
186 1008 : CallJS(CodeFactory::Call(isolate()), context, method, iterator.object);
187 504 : GotoIfException(inner_result, if_exception, nullptr);
188 :
189 : // (If completion.[[Type]] is throw) return Completion(completion).
190 504 : Goto(if_exception);
191 : }
192 504 : }
193 :
194 336 : void IteratorBuiltinsAssembler::IteratorCloseOnException(
195 : Node* context, const IteratorRecord& iterator, TNode<Object> exception) {
196 672 : Label rethrow(this, Label::kDeferred);
197 : TVARIABLE(Object, exception_variable, exception);
198 336 : IteratorCloseOnException(context, iterator, &rethrow, &exception_variable);
199 :
200 336 : BIND(&rethrow);
201 : CallRuntime(Runtime::kReThrow, context, exception_variable.value());
202 336 : Unreachable();
203 336 : }
204 :
205 56 : TNode<JSArray> IteratorBuiltinsAssembler::IterableToList(
206 : TNode<Context> context, TNode<Object> iterable, TNode<Object> iterator_fn) {
207 : // 1. Let iteratorRecord be ? GetIterator(items, method).
208 56 : IteratorRecord iterator_record = GetIterator(context, iterable, iterator_fn);
209 :
210 : // 2. Let values be a new empty List.
211 112 : GrowableFixedArray values(state());
212 :
213 : Variable* vars[] = {values.var_array(), values.var_length(),
214 56 : values.var_capacity()};
215 112 : Label loop_start(this, 3, vars), done(this);
216 56 : Goto(&loop_start);
217 : // 3. Let next be true.
218 : // 4. Repeat, while next is not false
219 56 : BIND(&loop_start);
220 : {
221 : // a. Set next to ? IteratorStep(iteratorRecord).
222 56 : TNode<Object> next = IteratorStep(context, iterator_record, &done);
223 : // b. If next is not false, then
224 : // i. Let nextValue be ? IteratorValue(next).
225 56 : TNode<Object> next_value = CAST(IteratorValue(context, next));
226 : // ii. Append nextValue to the end of the List values.
227 56 : values.Push(next_value);
228 56 : Goto(&loop_start);
229 : }
230 :
231 56 : BIND(&done);
232 112 : return values.ToJSArray(context);
233 : }
234 :
235 280 : TF_BUILTIN(IterableToList, IteratorBuiltinsAssembler) {
236 56 : TNode<Context> context = CAST(Parameter(Descriptor::kContext));
237 56 : TNode<Object> iterable = CAST(Parameter(Descriptor::kIterable));
238 56 : TNode<Object> iterator_fn = CAST(Parameter(Descriptor::kIteratorFn));
239 :
240 112 : Return(IterableToList(context, iterable, iterator_fn));
241 56 : }
242 :
243 : // This builtin always returns a new JSArray and is thus safe to use even in the
244 : // presence of code that may call back into user-JS. This builtin will take the
245 : // fast path if the iterable is a fast array and the Array prototype and the
246 : // Symbol.iterator is untouched. The fast path skips the iterator and copies the
247 : // backing store to the new array. Note that if the array has holes, the holes
248 : // will be copied to the new array, which is inconsistent with the behavior of
249 : // an actual iteration, where holes should be replaced with undefined (if the
250 : // prototype has no elements). To maintain the correct behavior for holey
251 : // arrays, use the builtins IterableToList or IterableToListWithSymbolLookup.
252 224 : TF_BUILTIN(IterableToListMayPreserveHoles, IteratorBuiltinsAssembler) {
253 : TNode<Context> context = CAST(Parameter(Descriptor::kContext));
254 56 : TNode<Object> iterable = CAST(Parameter(Descriptor::kIterable));
255 56 : TNode<Object> iterator_fn = CAST(Parameter(Descriptor::kIteratorFn));
256 :
257 56 : Label slow_path(this);
258 :
259 112 : GotoIfNot(IsFastJSArrayWithNoCustomIteration(context, iterable), &slow_path);
260 :
261 : // The fast path will copy holes to the new array.
262 56 : TailCallBuiltin(Builtins::kCloneFastJSArray, context, iterable);
263 :
264 56 : BIND(&slow_path);
265 56 : TailCallBuiltin(Builtins::kIterableToList, context, iterable, iterator_fn);
266 56 : }
267 :
268 112 : void IteratorBuiltinsAssembler::FastIterableToList(
269 : TNode<Context> context, TNode<Object> iterable,
270 : TVariable<Object>* var_result, Label* slow) {
271 224 : Label done(this), check_string(this), check_map(this), check_set(this);
272 :
273 224 : GotoIfNot(IsFastJSArrayWithNoCustomIteration(context, iterable),
274 112 : &check_string);
275 :
276 : // Fast path for fast JSArray.
277 224 : *var_result =
278 : CallBuiltin(Builtins::kCloneFastJSArrayFillingHoles, context, iterable);
279 112 : Goto(&done);
280 :
281 112 : BIND(&check_string);
282 : {
283 112 : Label string_maybe_fast_call(this);
284 : StringBuiltinsAssembler string_assembler(state());
285 : string_assembler.BranchIfStringPrimitiveWithNoCustomIteration(
286 112 : iterable, context, &string_maybe_fast_call, &check_map);
287 :
288 112 : BIND(&string_maybe_fast_call);
289 112 : TNode<IntPtrT> const length = LoadStringLengthAsWord(CAST(iterable));
290 : // Use string length as conservative approximation of number of codepoints.
291 112 : GotoIf(
292 336 : IntPtrGreaterThan(length, IntPtrConstant(JSArray::kMaxFastArrayLength)),
293 112 : slow);
294 224 : *var_result = CallBuiltin(Builtins::kStringToList, context, iterable);
295 112 : Goto(&done);
296 : }
297 :
298 112 : BIND(&check_map);
299 : {
300 112 : Label map_fast_call(this);
301 : BranchIfIterableWithOriginalKeyOrValueMapIterator(
302 112 : state(), iterable, context, &map_fast_call, &check_set);
303 :
304 112 : BIND(&map_fast_call);
305 224 : *var_result = CallBuiltin(Builtins::kMapIteratorToList, context, iterable);
306 112 : Goto(&done);
307 : }
308 :
309 112 : BIND(&check_set);
310 : {
311 112 : Label set_fast_call(this);
312 : BranchIfIterableWithOriginalValueSetIterator(state(), iterable, context,
313 112 : &set_fast_call, slow);
314 :
315 112 : BIND(&set_fast_call);
316 224 : *var_result =
317 : CallBuiltin(Builtins::kSetOrSetIteratorToList, context, iterable);
318 112 : Goto(&done);
319 : }
320 :
321 112 : BIND(&done);
322 112 : }
323 :
324 : // This builtin loads the property Symbol.iterator as the iterator, and has fast
325 : // paths for fast arrays, for primitive strings, for sets and set iterators, and
326 : // for map iterators. These fast paths will only be taken if Symbol.iterator and
327 : // the Iterator prototype are not modified in a way that changes the original
328 : // iteration behavior.
329 : // * In case of fast holey arrays, holes will be converted to undefined to
330 : // reflect iteration semantics. Note that replacement by undefined is only
331 : // correct when the NoElements protector is valid.
332 : // * In case of map/set iterators, there is an additional requirement that the
333 : // iterator is not partially consumed. To be spec-compliant, after spreading
334 : // the iterator is set to be exhausted.
335 168 : TF_BUILTIN(IterableToListWithSymbolLookup, IteratorBuiltinsAssembler) {
336 : TNode<Context> context = CAST(Parameter(Descriptor::kContext));
337 : TNode<Object> iterable = CAST(Parameter(Descriptor::kIterable));
338 :
339 56 : Label slow_path(this);
340 :
341 56 : GotoIfForceSlowPath(&slow_path);
342 :
343 : TVARIABLE(Object, var_result);
344 56 : FastIterableToList(context, iterable, &var_result, &slow_path);
345 56 : Return(var_result.value());
346 :
347 56 : BIND(&slow_path);
348 : {
349 56 : TNode<Object> iterator_fn = GetIteratorMethod(context, iterable);
350 56 : TailCallBuiltin(Builtins::kIterableToList, context, iterable, iterator_fn);
351 : }
352 56 : }
353 :
354 : } // namespace internal
355 59456 : } // namespace v8
|