Skip to main content

nodejs/stdlib/
iterator.rs

1//! Iterator helpers (27.1.4) — `map`, `filter`, `take`, `drop`, `flatMap` and
2//! the terminal `reduce`/`toArray`/`forEach`/`some`/`every`/`find`, plus the
3//! `Iterator` constructor, `Iterator.from` and `Iterator.concat`.
4//!
5//! None of it existed: `[1,2,3].values().map(f)` was "map is not a function".
6//!
7//! The helpers are LAZY, which is the whole point of them — `take(3)` on an
8//! endless generator has to stop after three pulls, not materialise anything.
9//! Each is an `@@native = "IteratorHelper"` object holding the iterator it
10//! draws from, so a chain is a chain of pulls; only the terminal operations
11//! drain. That also makes them work over any iterator, including a user object
12//! with a `next` method.
13
14use crate::host::{call_method, is_callable, with_host, JsObj};
15use fusevm::Value;
16use indexmap::IndexMap;
17
18/// The lazy helpers, which return another iterator.
19pub const LAZY: &[&str] = &["map", "filter", "take", "drop", "flatMap"];
20
21/// The terminal operations, which drain the iterator and return a value.
22pub const TERMINAL: &[&str] = &["reduce", "toArray", "forEach", "some", "every", "find"];
23
24/// Everything `Iterator.prototype` carries, so any iterator answers for it.
25pub const METHODS: &[&str] = &[
26    "map",
27    "filter",
28    "take",
29    "drop",
30    "flatMap",
31    "reduce",
32    "toArray",
33    "forEach",
34    "some",
35    "every",
36    "find",
37    "next",
38    "return",
39    "@@iterator",
40];
41
42/// `Iterator`'s own statics.
43pub const STATIC_METHODS: &[&str] = &["from", "concat"];
44
45/// True if `name` is one of the helper methods (lazy or terminal).
46pub fn is_helper(name: &str) -> bool {
47    LAZY.contains(&name) || TERMINAL.contains(&name)
48}
49
50/// A lazy helper over `src`.
51fn helper(src: &Value, op: &str, arg: Value) -> Value {
52    with_host(|h| {
53        let mut m = IndexMap::new();
54        m.insert("@@native".into(), h.new_str("IteratorHelper"));
55        m.insert("@@src".into(), src.clone());
56        m.insert("@@op".into(), h.new_str(op));
57        m.insert("@@arg".into(), arg);
58        // `take`/`drop` count down; `flatMap` parks the inner iterator here.
59        m.insert("@@count".into(), Value::Float(0.0));
60        m.insert("@@done".into(), Value::Bool(false));
61        h.new_object(m)
62    })
63}
64
65fn slot(recv: &Value, k: &str) -> Option<Value> {
66    with_host(|h| match h.get(recv) {
67        Some(JsObj::Object(p)) => p.get(k).cloned(),
68        _ => None,
69    })
70}
71
72fn set_slot(recv: &Value, k: &str, v: Value) {
73    with_host(|h| {
74        if let Some(JsObj::Object(p)) = h.get_mut(recv) {
75            p.insert(k.to_string(), v);
76        }
77    });
78}
79
80/// `{ value, done }`.
81fn step(value: Value, done: bool) -> Value {
82    with_host(|h| {
83        let mut m = IndexMap::new();
84        m.insert("value".into(), value);
85        m.insert("done".into(), Value::Bool(done));
86        h.new_object(m)
87    })
88}
89
90/// Mark a helper exhausted and close whatever it was drawing from — a `return`
91/// on any stage of a chain has to reach the generator at the bottom of it.
92pub fn helper_return(recv: &Value) -> Value {
93    let src = slot(recv, "@@src").unwrap_or(Value::Undef);
94    let already = slot(recv, "@@done").is_some_and(|v| with_host(|h| h.truthy(&v)));
95    set_slot(recv, "@@done", Value::Bool(true));
96    if !already {
97        // An inner iterator in flight (`flatMap`'s current mapping,
98        // `concat`'s current item) is closed first, then the source.
99        if let Some(inner) = slot(recv, "@@inner").filter(|v| !matches!(v, Value::Undef)) {
100            set_slot(recv, "@@inner", Value::Undef);
101            close(&inner);
102        }
103        close(&src);
104    }
105    done_step()
106}
107
108/// The `{ value: undefined, done: true }` an exhausted iterator reports.
109pub fn done_step() -> Value {
110    step(Value::Undef, true)
111}
112
113/// Pull one step from an iterator of any kind, as `(value, done)`.
114fn pull(it: &Value) -> Result<(Value, bool), String> {
115    let r = call_method(it, "next", Vec::new())?;
116    crate::host::require_iter_result(&r)?;
117    let done = crate::builtins::get_property(&r, "done")?;
118    let done = with_host(|h| h.truthy(&done));
119    let value = crate::builtins::get_property(&r, "value")?;
120    Ok((value, done))
121}
122
123/// Close an iterator that is being abandoned early (7.4.9 IteratorClose): its
124/// `return` runs, so a generator's `finally` block fires.
125fn close(it: &Value) {
126    // `get_property`, not `lookup_chain`: a generator's and a helper's `return`
127    // resolve through the stdlib funnel rather than a property map, so the
128    // chain read alone finds neither and every abandoned iterator stayed open.
129    let f = crate::builtins::get_property(it, "return").unwrap_or(Value::Undef);
130    if with_host(|h| is_callable(h, &f)) {
131        let _ = call_method(it, "return", Vec::new());
132    }
133}
134
135/// 27.1.4.x `ToIntegerOrInfinity` for `take`/`drop`'s limit, which must be a
136/// non-negative number — `take(-1)` and `take(NaN)` are RangeErrors, not silent
137/// no-ops.
138fn limit_arg(args: &[Value]) -> Result<f64, String> {
139    let raw = args.first().cloned().unwrap_or(Value::Undef);
140    let n = with_host(|h| h.to_number(&raw));
141    if n.is_nan() {
142        return Err(crate::host::range_error("NaN must be positive"));
143    }
144    if n < 0.0 {
145        let shown = with_host(|h| h.inspect(&Value::Float(n)));
146        return Err(crate::host::range_error(&format!(
147            "{shown} must be positive"
148        )));
149    }
150    Ok(n.trunc())
151}
152
153/// A callable argument, or the `TypeError` a helper raises without one.
154fn fn_arg(args: &[Value]) -> Result<Value, String> {
155    let f = args.first().cloned().unwrap_or(Value::Undef);
156    if !with_host(|h| is_callable(h, &f)) {
157        return Err(crate::host::type_error(
158            &crate::host::not_a_function_message(&f),
159        ));
160    }
161    Ok(f)
162}
163
164/// Dispatch a helper called on the iterator `recv`.
165pub fn call(recv: &Value, method: &str, args: &[Value]) -> Result<Value, String> {
166    match method {
167        "map" | "filter" | "flatMap" => Ok(helper(recv, method, fn_arg(args)?)),
168        "take" | "drop" => Ok(helper(recv, method, Value::Float(limit_arg(args)?))),
169        "toArray" => {
170            let mut out = Vec::new();
171            loop {
172                let (v, done) = pull(recv)?;
173                if done {
174                    break;
175                }
176                out.push(v);
177            }
178            Ok(with_host(|h| h.new_array(out)))
179        }
180        "forEach" => {
181            let f = fn_arg(args)?;
182            let mut i = 0.0;
183            loop {
184                let (v, done) = pull(recv)?;
185                if done {
186                    break;
187                }
188                crate::host::invoke(&f, vec![v, Value::Float(i)], None)?;
189                i += 1.0;
190            }
191            Ok(Value::Undef)
192        }
193        "reduce" => {
194            let f = fn_arg(args)?;
195            let mut acc = args.get(1).cloned();
196            let mut i = 0.0;
197            loop {
198                let (v, done) = pull(recv)?;
199                if done {
200                    break;
201                }
202                acc = Some(match acc {
203                    // 27.1.4.11 step 5: with no seed the FIRST value becomes the
204                    // accumulator and the reducer is not called for it.
205                    None => v,
206                    Some(a) => crate::host::invoke(&f, vec![a, v, Value::Float(i)], None)?,
207                });
208                i += 1.0;
209            }
210            acc.ok_or_else(|| {
211                crate::host::type_error("Reduce of a done iterator with no initial value")
212            })
213        }
214        "some" | "every" | "find" => {
215            let f = fn_arg(args)?;
216            let mut i = 0.0;
217            loop {
218                let (v, done) = pull(recv)?;
219                if done {
220                    break;
221                }
222                let r = crate::host::invoke(&f, vec![v.clone(), Value::Float(i)], None)?;
223                let hit = with_host(|h| h.truthy(&r));
224                // Each stops at the first decisive element and CLOSES the
225                // iterator it abandoned.
226                match method {
227                    "some" if hit => {
228                        close(recv);
229                        return Ok(Value::Bool(true));
230                    }
231                    "every" if !hit => {
232                        close(recv);
233                        return Ok(Value::Bool(false));
234                    }
235                    "find" if hit => {
236                        close(recv);
237                        return Ok(v);
238                    }
239                    _ => {}
240                }
241                i += 1.0;
242            }
243            Ok(match method {
244                "some" => Value::Bool(false),
245                "every" => Value::Bool(true),
246                _ => Value::Undef,
247            })
248        }
249        _ => Err(crate::host::type_error(&format!(
250            "{method} is not a function"
251        ))),
252    }
253}
254
255/// One step of a lazy helper: pull from the source until this stage produces a
256/// value or the source runs out.
257pub fn helper_next(recv: &Value) -> Result<Value, String> {
258    if slot(recv, "@@done").is_some_and(|v| with_host(|h| h.truthy(&v))) {
259        return Ok(step(Value::Undef, true));
260    }
261    let src = slot(recv, "@@src").unwrap_or(Value::Undef);
262    let op = slot(recv, "@@op")
263        .map(|v| with_host(|h| h.str_of(&v)))
264        .unwrap_or_default();
265    let arg = slot(recv, "@@arg").unwrap_or(Value::Undef);
266    let finish = || {
267        set_slot(recv, "@@done", Value::Bool(true));
268        step(Value::Undef, true)
269    };
270    match op.as_str() {
271        "take" => {
272            let limit = with_host(|h| h.to_number(&arg));
273            let seen = slot(recv, "@@count")
274                .map(|v| with_host(|h| h.to_number(&v)))
275                .unwrap_or(0.0);
276            if seen >= limit {
277                // The source is abandoned, so it is closed.
278                close(&src);
279                return Ok(finish());
280            }
281            let (v, done) = pull(&src)?;
282            if done {
283                return Ok(finish());
284            }
285            set_slot(recv, "@@count", Value::Float(seen + 1.0));
286            Ok(step(v, false))
287        }
288        "drop" => {
289            let limit = with_host(|h| h.to_number(&arg));
290            let mut dropped = slot(recv, "@@count")
291                .map(|v| with_host(|h| h.to_number(&v)))
292                .unwrap_or(0.0);
293            while dropped < limit {
294                let (_, done) = pull(&src)?;
295                dropped += 1.0;
296                set_slot(recv, "@@count", Value::Float(dropped));
297                if done {
298                    return Ok(finish());
299                }
300            }
301            let (v, done) = pull(&src)?;
302            if done {
303                return Ok(finish());
304            }
305            Ok(step(v, false))
306        }
307        "map" => {
308            let (v, done) = pull(&src)?;
309            if done {
310                return Ok(finish());
311            }
312            let i = slot(recv, "@@count")
313                .map(|x| with_host(|h| h.to_number(&x)))
314                .unwrap_or(0.0);
315            set_slot(recv, "@@count", Value::Float(i + 1.0));
316            let out = crate::host::invoke(&arg, vec![v, Value::Float(i)], None)?;
317            Ok(step(out, false))
318        }
319        "filter" => loop {
320            let (v, done) = pull(&src)?;
321            if done {
322                return Ok(finish());
323            }
324            let i = slot(recv, "@@count")
325                .map(|x| with_host(|h| h.to_number(&x)))
326                .unwrap_or(0.0);
327            set_slot(recv, "@@count", Value::Float(i + 1.0));
328            let keep = crate::host::invoke(&arg, vec![v.clone(), Value::Float(i)], None)?;
329            if with_host(|h| h.truthy(&keep)) {
330                return Ok(step(v, false));
331            }
332        },
333        "flatMap" => loop {
334            // An inner iterator already in flight is drained first.
335            if let Some(inner) = slot(recv, "@@inner") {
336                if !matches!(inner, Value::Undef) {
337                    let (v, done) = pull(&inner)?;
338                    if !done {
339                        return Ok(step(v, false));
340                    }
341                    set_slot(recv, "@@inner", Value::Undef);
342                }
343            }
344            let (v, done) = pull(&src)?;
345            if done {
346                return Ok(finish());
347            }
348            let i = slot(recv, "@@count")
349                .map(|x| with_host(|h| h.to_number(&x)))
350                .unwrap_or(0.0);
351            set_slot(recv, "@@count", Value::Float(i + 1.0));
352            let mapped = crate::host::invoke(&arg, vec![v, Value::Float(i)], None)?;
353            let inner = iterator_of(&mapped)?;
354            set_slot(recv, "@@inner", inner);
355        },
356        // `Iterator.concat`: `@@arg` holds the `(method, iterable)` pairs
357        // validated up front, flattened; each iterable is opened only when the
358        // previous one is exhausted, and its values pass through.
359        "concat" => loop {
360            if let Some(inner) = slot(recv, "@@inner").filter(|v| !matches!(v, Value::Undef)) {
361                let (v, done) = pull(&inner)?;
362                if !done {
363                    return Ok(step(v, false));
364                }
365                set_slot(recv, "@@inner", Value::Undef);
366            }
367            let pairs = with_host(|h| match h.get(&arg) {
368                Some(JsObj::Array(items)) => items.clone(),
369                _ => Vec::new(),
370            });
371            let i = slot(recv, "@@count")
372                .map(|x| with_host(|h| h.to_number(&x)) as usize)
373                .unwrap_or(0);
374            if 2 * i >= pairs.len() {
375                return Ok(finish());
376            }
377            set_slot(recv, "@@count", Value::Float((i + 1) as f64));
378            let (method, iterable) = (pairs[2 * i].clone(), pairs[2 * i + 1].clone());
379            let it = crate::host::invoke(&method, Vec::new(), Some(iterable))?;
380            if with_host(|h| crate::host::is_primitive(h, &it) || h.is_nullish(&it)) {
381                return Err(crate::host::type_error(&format!(
382                    "{} is not iterable",
383                    crate::builtins::no_side_effects_string_pub(&it)
384                )));
385            }
386            set_slot(recv, "@@inner", it);
387        },
388        // `Iterator.from`'s wrapper: forward each step unchanged.
389        "wrap" => {
390            let (v, done) = pull(&src)?;
391            if done {
392                return Ok(finish());
393            }
394            Ok(step(v, false))
395        }
396        _ => Ok(finish()),
397    }
398}
399
400/// The iterator for a value, via its `Symbol.iterator` — what `flatMap` and
401/// `Iterator.from` both need.
402fn iterator_of(v: &Value) -> Result<Value, String> {
403    // `get_property` rather than `lookup_chain`: an Array's or a String's
404    // `Symbol.iterator` resolves through the stdlib funnel, not a property map,
405    // so the chain read alone reports every builtin as non-iterable.
406    let f = crate::builtins::get_property(v, "@@iterator").unwrap_or(Value::Undef);
407    if with_host(|h| is_callable(h, &f)) {
408        return call_method(v, "@@iterator", Vec::new());
409    }
410    // A raw iterator object — one with `next` but no `Symbol.iterator` — is
411    // taken as-is, which is what `Iterator.from` accepts.
412    let next = crate::builtins::get_property(v, "next").unwrap_or(Value::Undef);
413    if with_host(|h| is_callable(h, &next)) {
414        return Ok(v.clone());
415    }
416    Err(crate::host::type_error(&format!(
417        "{} is not iterable",
418        with_host(|h| h.inspect(v))
419    )))
420}
421
422/// `GetIteratorFlattenable(obj, iterate-string-primitives)` (27.1.3.2.1.1) —
423/// the iterator `Iterator.from` starts from. A non-string primitive is
424/// refused; an absent `@@iterator` takes `obj` itself as the iterator; a
425/// present but non-callable one, or one returning a non-object, throws with
426/// V8's wording.
427fn iterator_flattenable(obj: &Value) -> Result<Value, String> {
428    let (is_object, is_string) = with_host(|h| {
429        (
430            !crate::host::is_primitive(h, obj) && !h.is_nullish(obj),
431            h.as_str(obj).is_some(),
432        )
433    });
434    if !is_object && !is_string {
435        return Err(crate::host::type_error(
436            "Iterator.from called on non-object",
437        ));
438    }
439    let method = crate::builtins::get_property(obj, "@@iterator")?;
440    if with_host(|h| h.is_nullish(&method)) {
441        return Ok(obj.clone());
442    }
443    if !with_host(|h| is_callable(h, &method)) {
444        let shown = with_host(|h| h.str_of(&method));
445        let owner = crate::builtins::no_side_effects_string_pub(obj);
446        return Err(crate::host::type_error(&format!(
447            "'{shown}' returned for property 'Symbol(Symbol.iterator)' of object '{owner}' is not a function"
448        )));
449    }
450    let it = crate::host::invoke(&method, Vec::new(), Some(obj.clone()))?;
451    if with_host(|h| crate::host::is_primitive(h, &it) || h.is_nullish(&it)) {
452        let owner = crate::builtins::no_side_effects_string_pub(obj);
453        return Err(crate::host::type_error(&format!("{owner} is not iterable")));
454    }
455    Ok(it)
456}
457
458/// `Iterator.from(x)`.
459pub fn static_call(method: &str, args: &[Value]) -> Option<Result<Value, String>> {
460    match method {
461        // `Iterator.from(x)` hands back something that HAS the helpers. A plain
462        // object with a `next` method has none of its own, so 27.1.4.1 wraps it
463        // — here in a pass-through helper, which is the same wrapper every
464        // other stage uses.
465        "from" => Some(
466            iterator_flattenable(&args.first().cloned().unwrap_or(Value::Undef)).map(|it| {
467                if super::native_tag(&it).as_deref() == Some("IteratorHelper")
468                    || matches!(
469                        with_host(|h| h.kind_of(&it)),
470                        Some(crate::host::ObjKind::Generator) | Some(crate::host::ObjKind::Iter)
471                    )
472                {
473                    it
474                } else {
475                    helper(&it, "wrap", Value::Undef)
476                }
477            }),
478        ),
479        "concat" => Some(concat(args)),
480        _ => None,
481    }
482}
483
484/// `Iterator.concat(...items)`: every item is checked BEFORE anything is
485/// opened — it must be an object with a callable `Symbol.iterator` — and the
486/// result is a lazy Iterator Helper that opens each item in turn.
487fn concat(args: &[Value]) -> Result<Value, String> {
488    let mut pairs = Vec::with_capacity(2 * args.len());
489    for item in args {
490        if with_host(|h| crate::host::is_primitive(h, item) || h.is_nullish(item)) {
491            return Err(crate::host::type_error(
492                "Iterator.concat called on non-object",
493            ));
494        }
495        let method = crate::builtins::get_property(item, "@@iterator")?;
496        let owner = crate::builtins::no_side_effects_string_pub(item);
497        if with_host(|h| h.is_nullish(&method)) {
498            return Err(crate::host::type_error(&format!("{owner} is not iterable")));
499        }
500        if !with_host(|h| is_callable(h, &method)) {
501            let shown = with_host(|h| h.str_of(&method));
502            return Err(crate::host::type_error(&format!(
503                "'{shown}' returned for property 'Symbol(Symbol.iterator)' of object '{owner}' is not a function"
504            )));
505        }
506        pairs.push(method);
507        pairs.push(item.clone());
508    }
509    let list = with_host(|h| h.new_array(pairs));
510    Ok(helper(&Value::Undef, "concat", list))
511}