Skip to main content

elly_core/eval/
iter.rs

1//! Iterators: the [`Iter`] behind a [`Value::Iter`], the constructors over
2//! the builtin kinds (`__iter`, `List.iter`, `Int.range`, …), the cursor
3//! methods and `zip`, and the drains that walk an iterator to its end
4//! (`docs/done/2026-10-21_elly-iter-v0.md`).
5//!
6//! An iterator is an immutable cursor, a position in a source: `next` makes a
7//! new one and leaves the old one as it was, so reading an iterator again
8//! answers the same. A drain holds the only reference to the cursor it walks,
9//! so it steps that one in place instead ([`step`]), allocating nothing per
10//! element.
11//!
12//! The loops `Iter.each` and `Iter.for` are lazy: a step runs when the
13//! iterator is first read (`empty`, `get`, `next`), and its result is kept, so
14//! it runs once. That makes reading such an iterator where its steps' effects
15//! and errors happen. A step ends in an outcome ([`Outcome`]): its value, or a
16//! [`Signal`] its cursor raised, caught by the loop whose identity the cursor
17//! carries.
18
19use alloc::boxed::Box;
20use alloc::rc::Rc;
21use alloc::string::String;
22use alloc::vec::Vec;
23use core::cell::OnceCell;
24use core::cmp::Ordering;
25use core::fmt;
26
27use rpds::{HashTrieMap, Vector};
28
29use crate::builtins::Builtin;
30use crate::code::Text;
31use crate::eval;
32use crate::eval::builtin::as_bool;
33use crate::eval::error::{Raised, Signal};
34use crate::sym::Sym;
35use crate::value::Value;
36use crate::Ctx;
37
38/// An iterator: the payload of a [`Value::Iter`], always behind an `Rc`.
39pub struct Iter(Src);
40
41/// Where an iterator is: in which source, and at which position.
42enum Src {
43    /// No elements left.
44    End,
45    /// A list from index `at` on. Also `__true`, as the list `[()]`.
46    List { list: Vector<Value>, at: usize },
47    /// A string's codepoints from byte offset `at` on, which is always on a
48    /// character boundary.
49    Str { text: Text, at: usize },
50    /// A map's `[k, v]` pairs from index `at` on. `__iter` copies the pairs
51    /// out once, since the map's own iterator borrows the map.
52    Map {
53        pairs: Rc<[(Value, Value)]>,
54        at: usize,
55    },
56    /// The integers `at`, `at + 1`, … up to and not including `to`. Both are
57    /// `Int` values, so the bounds may be `BigInt`s.
58    Range { at: Value, to: Value },
59    /// `[i, x]` pairs over `inner`, `i` counting up from where it started.
60    Index { inner: Rc<Iter>, i: u64 },
61    /// `[x, y]` pairs of two iterators, ending with the shorter.
62    Zip(Rc<Iter>, Rc<Iter>),
63    /// The cursor a loop hands its step: `inner`, carrying the loop's identity
64    /// and kind so the signal methods can name the loop. Moving it on keeps
65    /// both, so `it.next.__break` still ends the loop.
66    Step {
67        loop_id: u64,
68        kind: LoopKind,
69        inner: Rc<Iter>,
70    },
71    /// `Iter.each` / `Iter.for` at one position, run when first read.
72    Lazy(Lazy),
73}
74
75/// Which loop issued a step's cursor: the signals mean different things in
76/// each, and `__yield` means nothing in a fold.
77#[derive(Debug, Clone, Copy, PartialEq, Eq)]
78enum LoopKind {
79    For,
80    Fold,
81}
82
83/// A lazy loop at one position: what it runs per element, where its source
84/// is, what a `__yield` has left to give, and, once read, its result.
85struct Lazy {
86    body: Run,
87    arguments: Rc<Iter>,
88    to_yield: Option<Rc<Iter>>,
89    /// Filled on the first `empty` / `get` / `next`, so each step runs at most
90    /// once however often the iterator is read. A step that raises leaves it
91    /// empty, so reading again runs the step again.
92    current: OnceCell<Forced>,
93}
94
95/// What a lazy loop runs per element.
96#[derive(Clone)]
97enum Run {
98    /// `Iter.each f`: `f` of each element.
99    Each(Value),
100    /// `Iter.for step`: `step` of a cursor at each element, with the loop's
101    /// identity for the cursors it hands out.
102    For { step: Value, loop_id: u64 },
103}
104
105/// A forced lazy loop: the end, or an element and the loop after it.
106enum Forced {
107    End,
108    At(Value, Rc<Iter>),
109}
110
111/// Copies a position, for `next` to move on. A lazy loop is not copied: it
112/// moves on to the rest its result holds (see [`step`] and [`Iter::next`]),
113/// and a copy of its cell would run its steps a second time.
114impl Clone for Src {
115    fn clone(&self) -> Src {
116        match self {
117            Src::End => Src::End,
118            Src::List { list, at } => Src::List {
119                list: list.clone(),
120                at: *at,
121            },
122            Src::Str { text, at } => Src::Str {
123                text: text.clone(),
124                at: *at,
125            },
126            Src::Map { pairs, at } => Src::Map {
127                pairs: pairs.clone(),
128                at: *at,
129            },
130            Src::Range { at, to } => Src::Range {
131                at: at.clone(),
132                to: to.clone(),
133            },
134            Src::Index { inner, i } => Src::Index {
135                inner: inner.clone(),
136                i: *i,
137            },
138            Src::Zip(a, b) => Src::Zip(a.clone(), b.clone()),
139            Src::Step {
140                loop_id,
141                kind,
142                inner,
143            } => Src::Step {
144                loop_id: *loop_id,
145                kind: *kind,
146                inner: inner.clone(),
147            },
148            Src::Lazy(_) => unreachable!("a lazy loop moves on by its result, not by copy"),
149        }
150    }
151}
152
153/// Drops a forced lazy loop's chain of rests one node at a time: holding the
154/// first of a long forced loop holds every node after it, and dropping them
155/// recursively would overflow the stack.
156impl Drop for Iter {
157    fn drop(&mut self) {
158        let Src::Lazy(lazy) = &mut self.0 else {
159            return;
160        };
161        let Some(Forced::At(_, mut rest)) = lazy.current.take() else {
162            return;
163        };
164        loop {
165            let Ok(mut node) = Rc::try_unwrap(rest) else {
166                return;
167            };
168            let Src::Lazy(lazy) = &mut node.0 else {
169                return;
170            };
171            let Some(Forced::At(_, next)) = lazy.current.take() else {
172                return;
173            };
174            rest = next;
175        }
176    }
177}
178
179impl fmt::Debug for Iter {
180    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
181        let kind = match &self.0 {
182            Src::End => "End",
183            Src::List { .. } => "List",
184            Src::Str { .. } => "Str",
185            Src::Map { .. } => "Map",
186            Src::Range { .. } => "Range",
187            Src::Index { .. } => "Index",
188            Src::Zip(..) => "Zip",
189            Src::Step { .. } => "Step",
190            Src::Lazy(_) => "Lazy",
191        };
192        write!(f, "Iter::{kind}")
193    }
194}
195
196impl Iter {
197    fn new(src: Src) -> Rc<Iter> {
198        Rc::new(Iter(src))
199    }
200
201    /// Whether there is no current element.
202    pub(crate) fn empty(&self, ctx: &Ctx) -> Result<bool, Raised> {
203        Ok(match &self.0 {
204            Src::End => true,
205            Src::List { list, at } => *at >= list.len(),
206            Src::Str { text, at } => *at >= text.len(),
207            Src::Map { pairs, at } => *at >= pairs.len(),
208            Src::Range { at, to } => !less(at, to),
209            Src::Index { inner, .. } => inner.empty(ctx)?,
210            Src::Zip(a, b) => a.empty(ctx)? || b.empty(ctx)?,
211            Src::Step { inner, .. } => inner.empty(ctx)?,
212            Src::Lazy(lazy) => matches!(lazy.force(ctx)?, Forced::End),
213        })
214    }
215
216    /// The current element, or `.iter_end` past the end.
217    pub(crate) fn get(&self, ctx: &Ctx) -> Result<Value, Raised> {
218        let end = || Raised::symbol(Sym::ITER_END);
219        match &self.0 {
220            Src::End => Err(end()),
221            Src::List { list, at } => list.get(*at).cloned().ok_or_else(end),
222            Src::Str { text, at } => {
223                let ch = text[*at..].chars().next().ok_or_else(end)?;
224                Ok(Value::I64(i64::from(u32::from(ch))))
225            }
226            Src::Map { pairs, at } => {
227                let (k, v) = pairs.get(*at).ok_or_else(end)?;
228                Ok(Value::pair(k.clone(), v.clone()))
229            }
230            Src::Range { at, to } => {
231                if less(at, to) {
232                    Ok(at.clone())
233                } else {
234                    Err(end())
235                }
236            }
237            Src::Index { inner, i } => Ok(Value::pair(Value::from_u64(*i), inner.get(ctx)?)),
238            Src::Zip(a, b) => Ok(Value::pair(a.get(ctx)?, b.get(ctx)?)),
239            Src::Step { inner, .. } => inner.get(ctx),
240            Src::Lazy(lazy) => match lazy.force(ctx)? {
241                Forced::End => Err(end()),
242                Forced::At(x, _) => Ok(x.clone()),
243            },
244        }
245    }
246
247    /// The iterator one element further on, or `.iter_end` past the end.
248    pub(crate) fn next(&self, ctx: &Ctx) -> Result<Rc<Iter>, Raised> {
249        if let Src::Lazy(lazy) = &self.0 {
250            return match lazy.force(ctx)? {
251                Forced::End => Err(Raised::symbol(Sym::ITER_END)),
252                Forced::At(_, rest) => Ok(rest.clone()),
253            };
254        }
255        if self.empty(ctx)? {
256            return Err(Raised::symbol(Sym::ITER_END));
257        }
258        let mut src = self.0.clone();
259        src.advance(ctx)?;
260        Ok(Iter::new(src))
261    }
262
263    /// How many elements are left, counted without walking where the source
264    /// knows its length.
265    fn count(self: &Rc<Iter>, ctx: &Ctx) -> Result<Value, Raised> {
266        let left = |len: usize, at: usize| Value::from_u64(len.saturating_sub(at) as u64);
267        Ok(match &self.0 {
268            Src::End => Value::I64(0),
269            Src::List { list, at } => left(list.len(), *at),
270            Src::Map { pairs, at } => left(pairs.len(), *at),
271            Src::Str { text, at } => left(text[*at..].chars().count(), 0),
272            Src::Range { at, to } => {
273                if less(at, to) {
274                    to.int_sub(at).expect("a range's bounds are integers")
275                } else {
276                    Value::I64(0)
277                }
278            }
279            Src::Index { inner, .. } => inner.count(ctx)?,
280            Src::Zip(a, b) => {
281                let (a, b) = (a.count(ctx)?, b.count(ctx)?);
282                if less(&a, &b) {
283                    a
284                } else {
285                    b
286                }
287            }
288            Src::Step { inner, .. } => inner.count(ctx)?,
289            Src::Lazy(_) => {
290                let mut n: u64 = 0;
291                walk(self.clone(), ctx, |_| {
292                    n += 1;
293                    Ok(())
294                })?;
295                Value::from_u64(n)
296            }
297        })
298    }
299
300    /// `[i, x]` pairs over this iterator, `i` counting from 0 here.
301    pub(crate) fn index(self: &Rc<Iter>) -> Rc<Iter> {
302        Iter::new(Src::Index {
303            inner: self.clone(),
304            i: 0,
305        })
306    }
307}
308
309impl Src {
310    /// Moves this position one element on. The caller has checked that there
311    /// is a current element.
312    fn advance(&mut self, ctx: &Ctx) -> Result<(), Raised> {
313        match self {
314            Src::End => unreachable!("an empty iterator does not advance"),
315            Src::List { at, .. } | Src::Map { at, .. } => *at += 1,
316            Src::Str { text, at } => *at += text[*at..].chars().next().map_or(0, char::len_utf8),
317            Src::Range { at, .. } => *at = at.int_succ().expect("a range's bounds are integers"),
318            Src::Index { inner, i } => {
319                step(inner, ctx)?;
320                *i += 1;
321            }
322            Src::Zip(a, b) => {
323                step(a, ctx)?;
324                step(b, ctx)?;
325            }
326            Src::Step { inner, .. } => step(inner, ctx)?,
327            Src::Lazy(_) => unreachable!("a lazy loop moves on by its result, in `step`"),
328        }
329        Ok(())
330    }
331}
332
333impl Lazy {
334    /// The loop's result here, running steps the first time.
335    fn force(&self, ctx: &Ctx) -> Result<&Forced, Raised> {
336        if let Some(forced) = self.current.get() {
337            return Ok(forced);
338        }
339        let forced = self.run_steps(ctx)?;
340        Ok(self.current.get_or_init(|| forced))
341    }
342
343    /// Runs steps from here until one produces an element or the loop ends.
344    /// A `__continue` produces nothing and moves on; a `__yield` produces the
345    /// elements it was given before the source moves on.
346    fn run_steps(&self, ctx: &Ctx) -> Result<Forced, Raised> {
347        let mut inner = self.arguments.clone();
348        let mut pending = self.to_yield.clone();
349        loop {
350            if let Some(yielded) = pending.take() {
351                if !yielded.empty(ctx)? {
352                    let x = yielded.get(ctx)?;
353                    let rest = self.at(inner, Some(yielded.next(ctx)?));
354                    return Ok(Forced::At(x, rest));
355                }
356                // The step that yielded is done with: on to the next element.
357                inner = inner.next(ctx)?;
358            }
359            if inner.empty(ctx)? {
360                return Ok(Forced::End);
361            }
362            match &self.body {
363                Run::Each(f) => {
364                    let x = eval::apply1(f.clone(), inner.get(ctx)?, ctx)?;
365                    return Ok(Forced::At(x, self.at(inner.next(ctx)?, None)));
366                }
367                Run::For { step, loop_id } => {
368                    let cursor = Iter::new(Src::Step {
369                        loop_id: *loop_id,
370                        kind: LoopKind::For,
371                        inner: inner.clone(),
372                    });
373                    let ran = eval::apply1(step.clone(), Value::Iter(cursor), ctx);
374                    match outcome(ran, *loop_id)? {
375                        Outcome::Produce(x) => {
376                            return Ok(Forced::At(x, self.at(inner.next(ctx)?, None)));
377                        }
378                        Outcome::Continue => inner = inner.next(ctx)?,
379                        Outcome::Break => return Ok(Forced::End),
380                        Outcome::Yield(xs) => pending = Some(xs),
381                    }
382                }
383            }
384        }
385    }
386
387    /// The same loop, unread, with its source at `inner`.
388    fn at(&self, inner: Rc<Iter>, pending: Option<Rc<Iter>>) -> Rc<Iter> {
389        Iter::new(Src::Lazy(Lazy {
390            body: self.body.clone(),
391            arguments: inner,
392            to_yield: pending,
393            current: OnceCell::new(),
394        }))
395    }
396}
397
398/// How a step ended, for the loop of `loop_id`.
399enum Outcome {
400    /// With a value: the step's own, or a `__return`'s.
401    Produce(Value),
402    Continue,
403    Break,
404    /// With `__yield`, and the iterator it was given.
405    Yield(Rc<Iter>),
406}
407
408/// Reads a step's result as an outcome of the loop `loop_id`: its value, or a
409/// signal for this loop. Anything else, a signal for another loop included,
410/// goes on unwinding.
411fn outcome(ran: Result<Value, Raised>, loop_id: u64) -> Result<Outcome, Raised> {
412    match ran {
413        Ok(x) => Ok(Outcome::Produce(x)),
414        Err(Raised::Signal(s)) if s.loop_id() == loop_id => Ok(match s {
415            Signal::Continue(_) => Outcome::Continue,
416            Signal::Break(_) => Outcome::Break,
417            Signal::Return(b) => Outcome::Produce(b.1),
418            Signal::Yield(b) => match b.1 {
419                Value::Iter(xs) => Outcome::Yield(xs),
420                _ => unreachable!("`__yield` hands on an iterator"),
421            },
422        }),
423        Err(e) => Err(e),
424    }
425}
426
427/// Moves the cursor `it` one element on: in place when nothing else holds it,
428/// else by replacing it with its `next`. The caller has checked that there is
429/// a current element.
430fn step(it: &mut Rc<Iter>, ctx: &Ctx) -> Result<(), Raised> {
431    if let Src::Lazy(_) = &it.0 {
432        *it = it.next(ctx)?;
433        return Ok(());
434    }
435    match Rc::get_mut(it) {
436        Some(only) => only.0.advance(ctx),
437        None => {
438            *it = it.next(ctx)?;
439            Ok(())
440        }
441    }
442}
443
444// ---------------------------------------------------------------------------
445// Constructors
446// ---------------------------------------------------------------------------
447
448/// `__iter v`: an iterator over any iterable value. A list, string or map
449/// walks its elements, codepoints or `[k, v]` pairs; an integer `n` counts
450/// `0 … n - 1`; `__false` is empty and `__true` has the one element `()`; an
451/// iterator is itself. Anything else, objects included, raises `.not_iterable`.
452pub(crate) fn of(v: &Value, ctx: &Ctx) -> Result<Rc<Iter>, Raised> {
453    Ok(Iter::new(match v {
454        Value::Iter(it) => return Ok(it.clone()),
455        Value::List(list) => Src::List {
456            list: list.clone(),
457            at: 0,
458        },
459        Value::Str(text) => Src::Str {
460            text: text.clone(),
461            at: 0,
462        },
463        Value::Map(m) => {
464            let pairs: Vec<(Value, Value)> =
465                m.iter().map(|(k, v)| (k.clone(), v.clone())).collect();
466            Src::Map {
467                pairs: pairs.into(),
468                at: 0,
469            }
470        }
471        Value::I64(_) | Value::BigInt(_) => Src::Range {
472            at: Value::I64(0),
473            to: v.clone(),
474        },
475        Value::Iota { .. } => match as_bool(v, ctx) {
476            Ok(false) => Src::End,
477            Ok(true) => Src::List {
478                list: Vector::new().push_back(Value::Unit),
479                at: 0,
480            },
481            Err(_) => return Err(Raised::symbol(Sym::NOT_ITERABLE)),
482        },
483        _ => return Err(Raised::symbol(Sym::NOT_ITERABLE)),
484    }))
485}
486
487/// `List.iter` / `Map.iter` / `Str.iter` / `Int.upto`: [`of`] for the one kind
488/// `op` belongs to, raising that kind's tag on any other value.
489pub(crate) fn of_kind(op: Builtin, v: &Value, ctx: &Ctx) -> Result<Rc<Iter>, Raised> {
490    let (is, tag) = match op {
491        Builtin::ListIter => (matches!(v, Value::List(_)), Sym::NOT_A_LIST),
492        Builtin::MapIter => (matches!(v, Value::Map(_)), Sym::NOT_A_MAP),
493        Builtin::StrIter => (matches!(v, Value::Str(_)), Sym::NOT_A_STR),
494        Builtin::IntUpto => (
495            matches!(v, Value::I64(_) | Value::BigInt(_)),
496            Sym::NOT_AN_INT,
497        ),
498        _ => unreachable!("{op:?} is not a kind's iterator constructor"),
499    };
500    if !is {
501        return Err(Raised::symbol(tag));
502    }
503    of(v, ctx)
504}
505
506/// `Int.range m n`: the integers `m … n - 1`, empty when `m >= n`. A
507/// non-integer bound raises `.not_an_int`.
508pub(crate) fn range(from: &Value, to: &Value) -> Result<Rc<Iter>, Raised> {
509    if from.int_cmp(to).is_none() {
510        return Err(Raised::symbol(Sym::NOT_AN_INT));
511    }
512    Ok(Iter::new(Src::Range {
513        at: from.clone(),
514        to: to.clone(),
515    }))
516}
517
518/// `Iter.zip a b`: `[x, y]` pairs of two iterables, ending with the shorter.
519pub(crate) fn zip(a: &Value, b: &Value, ctx: &Ctx) -> Result<Rc<Iter>, Raised> {
520    Ok(Iter::new(Src::Zip(of(a, ctx)?, of(b, ctx)?)))
521}
522
523/// Borrows a value as an iterator, or raises `.not_an_iter`: `get` and `next`
524/// take an iterator and nothing else, with no implicit `__iter`.
525pub(crate) fn as_iter(v: &Value) -> Result<&Rc<Iter>, Raised> {
526    match v {
527        Value::Iter(it) => Ok(it),
528        _ => Err(Raised::symbol(Sym::NOT_AN_ITER)),
529    }
530}
531
532// ---------------------------------------------------------------------------
533// Loops and signals
534// ---------------------------------------------------------------------------
535
536/// `Iter.each f xs`: `f` of each element of `xs`, run when read.
537pub(crate) fn each(f: &Value, xs: &Value, ctx: &Ctx) -> Result<Rc<Iter>, Raised> {
538    Ok(Iter::new(Src::Lazy(Lazy {
539        body: Run::Each(f.clone()),
540        arguments: of(xs, ctx)?,
541        to_yield: None,
542        current: OnceCell::new(),
543    })))
544}
545
546/// `Iter.for step xs`: `step` of a cursor at each element of `xs`, run when
547/// read; what each step produces is decided by how it ends ([`Outcome`]).
548pub(crate) fn for_(step: &Value, xs: &Value, ctx: &Ctx) -> Result<Rc<Iter>, Raised> {
549    Ok(Iter::new(Src::Lazy(Lazy {
550        body: Run::For {
551            step: step.clone(),
552            loop_id: ctx.next_id(),
553        },
554        arguments: of(xs, ctx)?,
555        to_yield: None,
556        current: OnceCell::new(),
557    })))
558}
559
560/// `Iter.fold state step xs`: `step it acc` for a cursor `it` at each element
561/// and the state so far, eagerly. A step's value or `__return` is the new
562/// state, `__continue` keeps it, and `__break` ends the fold with it.
563pub(crate) fn fold(state: &Value, f: &Value, xs: &Value, ctx: &Ctx) -> Result<Value, Raised> {
564    // One cursor for the whole fold: when a step keeps no reference to it,
565    // `step` moves it and its source on in place, so a fold allocates nothing
566    // per element. A step that keeps it gets a copy at the next element.
567    let loop_id = ctx.next_id();
568    let mut cursor = Iter::new(Src::Step {
569        loop_id,
570        kind: LoopKind::Fold,
571        inner: of(xs, ctx)?,
572    });
573    let mut acc = state.clone();
574    while !cursor.empty(ctx)? {
575        let ran = eval::apply1(f.clone(), Value::Iter(cursor.clone()), ctx)
576            .and_then(|g| eval::apply1(g, acc.clone(), ctx));
577        match outcome(ran, loop_id)? {
578            Outcome::Produce(next) => acc = next,
579            Outcome::Continue => {}
580            Outcome::Break => break,
581            Outcome::Yield(_) => {
582                unreachable!("`__yield` on a fold's cursor raises where it is called")
583            }
584        }
585        step(&mut cursor, ctx)?;
586    }
587    Ok(acc)
588}
589
590/// `it.__continue` / `__break` / `__return v` / `__yield xs`: the signal for
591/// the loop that issued the cursor `it`, to raise. A cursor no loop issued
592/// raises `.not_in_loop`; `__yield` on a fold's cursor raises
593/// `.yield_in_fold`, and of a non-iterable `.not_iterable`, here where it is
594/// called rather than where the loop catches it.
595pub(crate) fn signal(op: Builtin, it: &Value, arg: Option<&Value>, ctx: &Ctx) -> Raised {
596    let (loop_id, kind) = match as_iter(it) {
597        Ok(it) => match &it.0 {
598            Src::Step { loop_id, kind, .. } => (*loop_id, *kind),
599            _ => return Raised::symbol(Sym::NOT_IN_LOOP),
600        },
601        Err(e) => return e,
602    };
603    let arg = || arg.expect("a signal with a value is given one").clone();
604    Raised::Signal(match op {
605        Builtin::IterContinue => Signal::Continue(loop_id),
606        Builtin::IterBreak => Signal::Break(loop_id),
607        Builtin::IterReturn => Signal::Return(Box::new((loop_id, arg()))),
608        Builtin::IterYield => {
609            if kind == LoopKind::Fold {
610                return Raised::symbol(Sym::YIELD_IN_FOLD);
611            }
612            match of(&arg(), ctx) {
613                Ok(xs) => Signal::Yield(Box::new((loop_id, Value::Iter(xs)))),
614                Err(e) => return e,
615            }
616        }
617        _ => unreachable!("{op:?} is not a signal"),
618    })
619}
620
621// ---------------------------------------------------------------------------
622// Drains
623// ---------------------------------------------------------------------------
624
625/// Walks `it` to its end, handing each element to `f`.
626fn walk(
627    mut it: Rc<Iter>,
628    ctx: &Ctx,
629    mut f: impl FnMut(Value) -> Result<(), Raised>,
630) -> Result<(), Raised> {
631    while !it.empty(ctx)? {
632        f(it.get(ctx)?)?;
633        step(&mut it, ctx)?;
634    }
635    Ok(())
636}
637
638/// `Int.count xs`: the number of elements. Counted without walking where the
639/// source knows its length.
640pub(crate) fn count(xs: &Value, ctx: &Ctx) -> Result<Value, Raised> {
641    of(xs, ctx)?.count(ctx)
642}
643
644/// `List.from xs`: a list of the elements.
645pub(crate) fn to_list(xs: &Value, ctx: &Ctx) -> Result<Value, Raised> {
646    let it = of(xs, ctx)?;
647    if let Src::List { list, at: 0 } = &it.0 {
648        return Ok(Value::List(list.clone()));
649    }
650    let mut out = Vector::new();
651    walk(it, ctx, |x| {
652        out.push_back_mut(x);
653        Ok(())
654    })?;
655    Ok(Value::List(out))
656}
657
658/// `Str.from xs`: a string of the elements, each a codepoint. An element that
659/// is not an integer raises `.not_an_int`, one that is not a Unicode scalar
660/// `.bad_codepoint`.
661pub(crate) fn to_str(xs: &Value, ctx: &Ctx) -> Result<Value, Raised> {
662    let it = of(xs, ctx)?;
663    if let Src::Str { text, at } = &it.0 {
664        return Ok(Value::Str(if *at == 0 {
665            text.clone()
666        } else {
667            Text::from(&text[*at..])
668        }));
669    }
670    let mut out = String::new();
671    walk(it, ctx, |x| {
672        out.push(x.to_codepoint()?);
673        Ok(())
674    })?;
675    Ok(Value::Str(Text::from(out.as_str())))
676}
677
678/// `Map.from xs`: a map from `[k, v]` pairs, a repeated key keeping its last
679/// value. Any other element raises `.not_a_pair`.
680pub(crate) fn to_map(xs: &Value, ctx: &Ctx) -> Result<Value, Raised> {
681    let mut out = HashTrieMap::new();
682    walk(of(xs, ctx)?, ctx, |x| {
683        match &x {
684            Value::List(kv) if kv.len() == 2 => {
685                out.insert_mut(kv[0].clone(), kv[1].clone());
686            }
687            _ => return Err(Raised::symbol(Sym::NOT_A_PAIR)),
688        }
689        Ok(())
690    })?;
691    Ok(Value::Map(out))
692}
693
694/// `Iter.eq a b`: whether two iterables have equal elements, by `__eq`, and
695/// the same length. Stops at the first difference.
696pub(crate) fn eq(a: &Value, b: &Value, ctx: &Ctx) -> Result<bool, Raised> {
697    let (mut a, mut b) = (of(a, ctx)?, of(b, ctx)?);
698    loop {
699        match (a.empty(ctx)?, b.empty(ctx)?) {
700            (true, true) => return Ok(true),
701            (false, false) => {}
702            _ => return Ok(false),
703        }
704        if a.get(ctx)? != b.get(ctx)? {
705            return Ok(false);
706        }
707        step(&mut a, ctx)?;
708        step(&mut b, ctx)?;
709    }
710}
711
712/// `Iter.run xs`: walks an iterable for what reading it does, to `()`.
713pub(crate) fn run(xs: &Value, ctx: &Ctx) -> Result<Value, Raised> {
714    walk(of(xs, ctx)?, ctx, |_| Ok(()))?;
715    Ok(Value::Unit)
716}
717
718/// `a < b` over two integers already checked to be integers.
719fn less(a: &Value, b: &Value) -> bool {
720    a.int_cmp(b).expect("compared values are integers") == Ordering::Less
721}