1use 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
38pub struct Iter(Src);
40
41enum Src {
43 End,
45 List { list: Vector<Value>, at: usize },
47 Str { text: Text, at: usize },
50 Map {
53 pairs: Rc<[(Value, Value)]>,
54 at: usize,
55 },
56 Range { at: Value, to: Value },
59 Index { inner: Rc<Iter>, i: u64 },
61 Zip(Rc<Iter>, Rc<Iter>),
63 Step {
67 loop_id: u64,
68 kind: LoopKind,
69 inner: Rc<Iter>,
70 },
71 Lazy(Lazy),
73}
74
75#[derive(Debug, Clone, Copy, PartialEq, Eq)]
78enum LoopKind {
79 For,
80 Fold,
81}
82
83struct Lazy {
86 body: Run,
87 arguments: Rc<Iter>,
88 to_yield: Option<Rc<Iter>>,
89 current: OnceCell<Forced>,
93}
94
95#[derive(Clone)]
97enum Run {
98 Each(Value),
100 For { step: Value, loop_id: u64 },
103}
104
105enum Forced {
107 End,
108 At(Value, Rc<Iter>),
109}
110
111impl 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
153impl 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 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 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 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 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 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 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 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 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 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 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
398enum Outcome {
400 Produce(Value),
402 Continue,
403 Break,
404 Yield(Rc<Iter>),
406}
407
408fn 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
427fn 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
444pub(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
487pub(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
506pub(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
518pub(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
523pub(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
532pub(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
546pub(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
560pub(crate) fn fold(state: &Value, f: &Value, xs: &Value, ctx: &Ctx) -> Result<Value, Raised> {
564 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
590pub(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
621fn 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
638pub(crate) fn count(xs: &Value, ctx: &Ctx) -> Result<Value, Raised> {
641 of(xs, ctx)?.count(ctx)
642}
643
644pub(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
658pub(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
678pub(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
694pub(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
712pub(crate) fn run(xs: &Value, ctx: &Ctx) -> Result<Value, Raised> {
714 walk(of(xs, ctx)?, ctx, |_| Ok(()))?;
715 Ok(Value::Unit)
716}
717
718fn less(a: &Value, b: &Value) -> bool {
720 a.int_cmp(b).expect("compared values are integers") == Ordering::Less
721}