1pub(crate) mod builtin;
16pub(crate) mod env;
17#[cfg(feature = "stats-env")]
18pub mod env_stats;
19pub(crate) mod error;
20pub(crate) mod iter;
21mod patmatch;
22
23use alloc::boxed::Box;
24use alloc::rc::Rc;
25use alloc::vec::Vec;
26
27use rpds::{HashTrieMap, Vector};
28
29use crate::code::{ChunkId, LambdaId, ModId, Node, NodeId, Pat, PatId, Plan, Run};
30
31use crate::builtins::Builtin;
32use crate::eval::env::{Env, EnvNode, EnvRef};
33use crate::eval::error::Raised;
34use crate::eval::patmatch::{match_pat, match_pattern};
35use crate::sym::{Projection, Sym};
36use crate::value::Value;
37use crate::Ctx;
38
39impl Ctx {
44 pub(crate) fn next_id(&self) -> u64 {
47 let n = self.ids.get();
48 self.ids.set(n + 1);
49 n
50 }
51
52 pub(crate) fn reserve_ids(&self, n: u64) -> u64 {
56 let base = self.ids.get();
57 self.ids.set(base + n);
58 base
59 }
60
61 pub(crate) fn builtin_module(&self, op: Builtin) -> Value {
69 let slot = op.module_slot().expect("a builtin module");
70 self.modules[slot]
71 .get_or_init(|| {
72 instantiate_module(ChunkId::ELLY, ModId::builtin(slot), &[], self)
73 .expect("a builtin module has no frame")
74 })
75 .clone()
76 }
77}
78
79pub fn eval_main(instance: &Value, ctx: &Ctx) -> Result<Option<Value>, Raised> {
91 let Value::Module(home) = instance else {
92 return Err(Raised::symbol(Sym::NOT_A_MODULE));
93 };
94 let EnvNode::Module { chunk, module, .. } = **home else {
95 unreachable!("a module value always holds a module terminal")
96 };
97 let body = ctx.chunk(chunk).module(module).body;
98 let Some(body) = body.get() else {
99 return Ok(None);
100 };
101 ctx.clear_unwind();
102 let result = eval(chunk, body, &Env::from_ref(home.clone()), ctx)?;
103 Ok(Some(result))
104}
105
106pub fn eval_in_module(
111 chunk: ChunkId,
112 instance: &Value,
113 args: &[Value],
114 ctx: &Ctx,
115) -> Result<Value, Raised> {
116 let Value::Module(home) = instance else {
117 return Err(Raised::symbol(Sym::NOT_A_MODULE));
118 };
119 let body = {
120 let code = ctx.chunk(chunk);
121 code.module(code.top()).body
122 };
123 let env = args.iter().fold(Env::from_ref(home.clone()), |env, arg| {
124 env.bind(arg.clone())
125 });
126 ctx.clear_unwind();
127 eval(chunk, body, &env, ctx)
128}
129
130pub fn apply_with(f: &Value, arg: Value, ctx: &Ctx) -> Result<Value, Raised> {
139 ctx.clear_unwind();
140 apply1(f.clone(), arg, ctx)
141}
142
143pub fn eval_env(chunk: ChunkId, env: &Env, ctx: &Ctx) -> Result<Value, Raised> {
147 let body = {
148 let code = ctx.chunk(chunk);
149 let top = code.module(code.top());
150 assert!(
151 top.members.len == 0 && top.frame.len == 0,
152 "only an expression chunk runs on its own"
153 );
154 top.body
155 };
156 ctx.clear_unwind();
157 eval(chunk, body, env, ctx)
158}
159
160pub(crate) fn eval(at: ChunkId, id: NodeId, env: &Env, ctx: &Ctx) -> Result<Value, Raised> {
162 match ctx.node(at, id) {
163 Node::Local { index, .. } => Ok(env.lookup(index)),
165 Node::ModItem { index, depth, .. } => mod_item(env, index, depth, ctx),
167 Node::Home { leaf, depth } => env.home_leaf(leaf, depth),
169 Node::Recur(group) => recur(at, group, env, ctx),
171 Node::Block { len, binds, exprs } => eval_block(at, len, binds, exprs, env, ctx),
173 Node::Builtin(op) => {
176 if op.arity() == 0 {
177 builtin::invoke(op, &[], ctx)
178 } else {
179 Ok(Value::Builtin {
182 op,
183 args: Vec::new(),
184 })
185 }
186 }
187 Node::Int(n) => Ok(Value::I64(n)),
188 Node::BigInt(n) => Ok(Value::BigInt(Rc::new(ctx.chunk(at).int(n).clone()))),
190 Node::Symbol(s) => Ok(Value::Symbol(s)),
191 Node::Str(s) => Ok(Value::Str(ctx.chunk(at).str(s).clone())),
193 Node::Unit => Ok(Value::Unit),
194 Node::List { len, elems } => {
195 ctx.check_run(at, Run::List, elems, len);
196 let mut vs = Vector::new();
197 for i in 0..len {
198 let elem = eval(at, elems.nth(i), env, ctx)?;
199 vs.push_back_mut(elem);
200 }
201 Ok(Value::List(vs))
202 }
203 Node::Map { len, entries } => {
206 ctx.check_run(at, Run::Map, entries, 2 * len);
207 let mut m = HashTrieMap::new();
208 for i in 0..len {
209 let kv = eval(at, entries.nth(i), env, ctx)?;
210 let vv = eval(at, entries.nth(len + i), env, ctx)?;
211 m.insert_mut(kv, vv);
212 }
213 Ok(Value::Map(m))
214 }
215 Node::Abs(code) => Ok(closure(at, code, ctx.next_id(), env, ctx)),
217 Node::App { len, args } => {
221 ctx.check_run(at, Run::App, args, len);
222 let callee = eval(at, args, env, ctx)?;
223 match len - 1 {
227 1 => {
228 let arg = eval(at, args.nth(1), env, ctx)?;
229 apply1_at(callee, arg, at, id, ctx)
230 }
231 2 => {
232 let va = eval(at, args.nth(1), env, ctx)?;
233 let vb = eval(at, args.nth(2), env, ctx)?;
234 apply_n_at(callee, &[va, vb], at, id, ctx)
235 }
236 3 => {
237 let va = eval(at, args.nth(1), env, ctx)?;
238 let vb = eval(at, args.nth(2), env, ctx)?;
239 let vc = eval(at, args.nth(3), env, ctx)?;
240 apply_n_at(callee, &[va, vb, vc], at, id, ctx)
241 }
242 4 => {
243 let va = eval(at, args.nth(1), env, ctx)?;
244 let vb = eval(at, args.nth(2), env, ctx)?;
245 let vc = eval(at, args.nth(3), env, ctx)?;
246 let vd = eval(at, args.nth(4), env, ctx)?;
247 apply_n_at(callee, &[va, vb, vc, vd], at, id, ctx)
248 }
249 n => {
250 let mut argv: Vec<Value> = Vec::with_capacity(n as usize);
251 for i in 1..len {
252 argv.push(eval(at, args.nth(i), env, ctx)?);
253 }
254 apply_n_at(callee, &argv, at, id, ctx)
255 }
256 }
257 }
258 Node::Case { len, conds, exprs } => {
261 ctx.check_run(at, Run::Case, exprs, len + 1);
262 let subj = eval(at, exprs.nth(len), env, ctx)?;
263 run_arms(at, &subj, len, conds, exprs, env, ctx)
264 }
265 #[cfg(debug_assertions)]
266 Node::Barrier { .. } => unreachable!("a barrier is not an operand"),
267 }
268}
269
270#[inline]
274fn closure(at: ChunkId, code: LambdaId, id: u64, env: &Env, ctx: &Ctx) -> Value {
275 let lambda = ctx.lambda(at, code);
276 let env = match lambda.captures {
277 Plan::Chain => env.clone(),
278 Plan::Frame(plan) => env.capture_env(ctx.chunk(at).captures(plan), ctx),
281 };
282 Value::Closure {
283 id,
284 chunk: at,
285 lambda: code,
286 applied: 0,
287 arity: lambda.head.len as u8,
288 env,
289 }
290}
291
292#[inline(never)]
295fn run_arms(
296 at: ChunkId,
297 subj: &Value,
298 len: u32,
299 conds: PatId,
300 bodies: NodeId,
301 env: &Env,
302 ctx: &Ctx,
303) -> Result<Value, Raised> {
304 ctx.check_pat_run(at, Run::Case, conds, len);
305 for i in 0..len {
306 match match_pattern(at, conds.nth(i), subj, env.clone(), ctx) {
307 Ok(arm_env) => {
310 if i > 0 {
312 ctx.caught();
313 }
314 return eval(at, bodies.nth(i), &arm_env, ctx);
315 }
316 Err(Raised::NoMatch(_)) => ctx.caught(),
317 Err(e) => return Err(e),
318 }
319 }
320 Err(ctx.no_arm_matched(at, bodies.nth(len), subj))
321}
322
323#[inline(always)]
327pub(crate) fn apply1(fv: Value, av: Value, ctx: &Ctx) -> Result<Value, Raised> {
328 apply1_at(fv, av, ChunkId::NONE, NodeId::NONE, ctx)
329}
330
331fn apply1_at(fv: Value, av: Value, at: ChunkId, call: NodeId, ctx: &Ctx) -> Result<Value, Raised> {
335 match fv {
336 Value::Closure {
337 chunk,
338 lambda,
339 applied,
340 arity,
341 env,
342 ..
343 } => {
344 let code = ctx.lambda(chunk, lambda);
345 ctx.check_pat_run(chunk, Run::Head, code.head.first, code.head.len);
346 let pat = code.head.first.nth(u32::from(applied));
348 let call_env = match match_pattern(chunk, pat, &av, env, ctx) {
349 Ok(env) => env,
350 Err(r) => {
351 let pat = code.head.first.nth(u32::from(applied));
352 return Err(unbound(r, chunk, pat, &av, at, call, ctx));
353 }
354 };
355 if applied + 1 < arity {
356 return Ok(Value::Closure {
358 id: ctx.next_id(),
359 chunk,
360 lambda,
361 applied: applied + 1,
362 arity,
363 env: call_env,
364 });
365 }
366 let result = eval(chunk, code.body, &call_env, ctx);
367 ctx.release(call_env);
368 traced(result, at, call, ctx)
369 }
370 Value::Builtin {
371 op,
372 args: mut gathered,
373 } => {
374 if gathered.is_empty() && op.arity() == 1 {
376 return traced(builtin::invoke(op, &[av], ctx), at, call, ctx);
377 }
378 gathered.push(av);
379 if gathered.len() == op.arity() {
380 traced(builtin::invoke(op, &gathered, ctx), at, call, ctx)
381 } else {
382 Ok(Value::Builtin { op, args: gathered })
383 }
384 }
385 Value::HostFn {
386 code,
387 args: gathered,
388 } => {
389 if gathered.is_empty() && code.arity == 1 {
390 return traced((code.f)(&[av], ctx), at, call, ctx);
391 }
392 let gathered = extended(&gathered, &[av]);
393 if gathered.len() == code.arity {
394 traced((code.f)(&gathered, ctx), at, call, ctx)
395 } else {
396 Ok(Value::HostFn {
397 code,
398 args: gathered,
399 })
400 }
401 }
402 Value::Module(home) => {
404 let result = match av {
405 Value::Symbol(s) => materialize(&Env::from_ref(home), s, ctx),
406 _ => Err(Raised::symbol(Sym::NOT_APPLICABLE)),
407 };
408 traced(result, at, call, ctx)
409 }
410 fv => traced(receiver(fv, &av, &[], ctx), at, call, ctx),
412 }
413}
414
415#[cold]
421#[inline(never)]
422fn unbound(
423 raised: Raised,
424 chunk: ChunkId,
425 pat: PatId,
426 arg: &Value,
427 at: ChunkId,
428 call: NodeId,
429 ctx: &Ctx,
430) -> Raised {
431 if call == NodeId::NONE {
432 return raised;
433 }
434 ctx.unwound(&raised, at, call);
435 ctx.escaped(raised, chunk, pat, arg)
436}
437
438#[inline(always)]
441fn traced(
442 result: Result<Value, Raised>,
443 at: ChunkId,
444 call: NodeId,
445 ctx: &Ctx,
446) -> Result<Value, Raised> {
447 if let Err(raised) = &result {
448 ctx.unwound(raised, at, call);
449 }
450 result
451}
452
453#[inline(always)]
461fn apply_n(fv: Value, args: &[Value], ctx: &Ctx) -> Result<Value, Raised> {
462 apply_n_at(fv, args, ChunkId::NONE, NodeId::NONE, ctx)
463}
464
465fn apply_n_at(
468 mut fv: Value,
469 mut args: &[Value],
470 at: ChunkId,
471 call: NodeId,
472 ctx: &Ctx,
473) -> Result<Value, Raised> {
474 while !args.is_empty() {
475 match fv {
476 Value::Closure {
481 chunk,
482 lambda,
483 applied,
484 arity,
485 env,
486 ..
487 } => {
488 let code = ctx.lambda(chunk, lambda);
489 ctx.check_pat_run(chunk, Run::Head, code.head.first, code.head.len);
490 let remaining = usize::from(arity - applied);
491 let take = remaining.min(args.len());
492 let mut call_env = env;
495 let first = code.head.first.nth(u32::from(applied));
496 for (i, arg) in args[..take].iter().enumerate() {
497 let matched = match_pattern(chunk, first.nth(i as u32), arg, call_env, ctx);
498 call_env = match matched {
499 Ok(env) => env,
500 Err(r) => {
501 let pat = first.nth(i as u32);
502 return Err(unbound(r, chunk, pat, arg, at, call, ctx));
503 }
504 };
505 }
506 if take < remaining {
507 return Ok(Value::Closure {
509 id: ctx.next_id(),
510 chunk,
511 lambda,
512 applied: applied + take as u8,
513 arity,
514 env: call_env,
515 });
516 }
517 let result = eval(chunk, code.body, &call_env, ctx);
518 ctx.release(call_env);
519 fv = traced(result, at, call, ctx)?;
520 args = &args[take..];
521 }
522 Value::Builtin {
526 op,
527 args: mut gathered,
528 } => {
529 let arity = op.arity();
530 if gathered.is_empty() && args.len() >= arity {
531 fv = traced(builtin::invoke(op, &args[..arity], ctx), at, call, ctx)?;
532 args = &args[arity..];
533 } else {
534 let take = (arity - gathered.len()).min(args.len());
535 gathered.extend(args[..take].iter().cloned());
536 if gathered.len() < arity {
537 return Ok(Value::Builtin { op, args: gathered });
538 }
539 fv = traced(builtin::invoke(op, &gathered, ctx), at, call, ctx)?;
540 args = &args[take..];
541 }
542 }
543 Value::HostFn {
545 code,
546 args: gathered,
547 } => {
548 let arity = code.arity;
549 if gathered.is_empty() && args.len() >= arity {
550 fv = traced((code.f)(&args[..arity], ctx), at, call, ctx)?;
551 args = &args[arity..];
552 } else {
553 let take = (arity - gathered.len()).min(args.len());
554 let gathered = extended(&gathered, &args[..take]);
555 if gathered.len() < arity {
556 return Ok(Value::HostFn {
557 code,
558 args: gathered,
559 });
560 }
561 fv = traced((code.f)(&gathered, ctx), at, call, ctx)?;
562 args = &args[take..];
563 }
564 }
565 Value::Module(home) => {
567 let result = match &args[0] {
568 Value::Symbol(s) => materialize(&Env::from_ref(home), *s, ctx),
569 _ => Err(Raised::symbol(Sym::NOT_APPLICABLE)),
570 };
571 fv = traced(result, at, call, ctx)?;
572 args = &args[1..];
573 }
574 fv => return traced(receiver(fv, &args[0], &args[1..], ctx), at, call, ctx),
577 }
578 }
579 Ok(fv)
580}
581
582fn extended(prefix: &[Value], more: &[Value]) -> Box<[Value]> {
585 let mut all = Vec::with_capacity(prefix.len() + more.len());
586 all.extend_from_slice(prefix);
587 all.extend_from_slice(more);
588 all.into_boxed_slice()
589}
590
591pub(crate) fn proto_of(v: &Value, ctx: &Ctx) -> Value {
598 match v {
599 Value::Object(obj) => obj.proto(),
600 Value::Iota { home, .. } => Value::Module(home.clone()),
601 Value::I64(_) | Value::BigInt(_) => ctx.builtin_module(Builtin::Int),
602 Value::Symbol(_) => ctx.builtin_module(Builtin::Sym),
603 Value::Str(_) => ctx.builtin_module(Builtin::Str),
604 Value::Unit => ctx.builtin_module(Builtin::Unit),
605 Value::List(_) => ctx.builtin_module(Builtin::List),
606 Value::Map(_) => ctx.builtin_module(Builtin::Map),
607 Value::Closure { .. } | Value::Builtin { .. } | Value::HostFn { .. } => {
608 ctx.builtin_module(Builtin::Fun)
609 }
610 Value::Module(_) => ctx.builtin_module(Builtin::Mod),
611 Value::Iter(_) => ctx.builtin_module(Builtin::Iter),
612 }
613}
614
615#[inline(never)]
624pub(crate) fn proto_is(
625 at: ChunkId,
626 expr: NodeId,
627 value: &Value,
628 env: &Env,
629 ctx: &Ctx,
630) -> Result<bool, Raised> {
631 let expected = eval(at, expr, env, ctx)?;
632 if !matches!(expected, Value::Module(_)) {
633 return Err(Raised::symbol(Sym::NOT_A_MODULE));
634 }
635 Ok(proto_of(value, ctx) == expected)
636}
637
638#[inline(never)]
655fn mod_item(env: &Env, index: u32, depth: u32, ctx: &Ctx) -> Result<Value, Raised> {
656 let (env, home, (chunk, module, id_base)) = env
657 .find_module(depth)
658 .ok_or_else(|| Raised::symbol(Sym::NO_MODULE))?;
659 let member = ctx.chunk(chunk).member(module, index);
660 let Some(member) = member else {
661 let code = ctx.chunk(chunk);
663 let index = index - code.member_len(module);
664 if code.iota(module, index).is_none() {
665 return Err(Raised::symbol(Sym::MISSING_PROPERTY));
666 }
667 return Ok(Value::Iota {
668 home: home.clone(),
669 index,
670 });
671 };
672 materialize_body(chunk, member.node, env, id_base, index, ctx)
673}
674
675#[inline(never)]
683fn recur(at: ChunkId, group: ModId, env: &Env, ctx: &Ctx) -> Result<Value, Raised> {
684 let (len, body) = {
685 let code = ctx.chunk(at);
686 (code.member_len(group), code.module(group).body)
687 };
688 let home = EnvRef::new(EnvNode::Module {
689 chunk: at,
690 module: group,
691 id_base: ctx.reserve_ids(u64::from(len)),
692 frame: env.clone(),
693 });
694 eval(at, body, &Env::from_ref(home), ctx)
695}
696
697fn eval_block(
701 at: ChunkId,
702 len: u32,
703 binds: PatId,
704 exprs: NodeId,
705 env: &Env,
706 ctx: &Ctx,
707) -> Result<Value, Raised> {
708 let Some(last) = len.checked_sub(1) else {
709 return Ok(Value::Unit);
710 };
711 ctx.check_pat_run(at, Run::Block, binds, len);
712 ctx.check_run(at, Run::Block, exprs, len);
713 let mut env = env.clone();
714 for i in 0..last {
715 match ctx.pat(at, binds.nth(i)) {
716 Pat::None => {
717 eval(at, exprs.nth(i), &env, ctx)?;
718 }
719 pat => {
720 let v = eval(at, exprs.nth(i), &env, ctx)?;
721 env = match_pat(at, pat, &v, env, ctx)
722 .map_err(|r| ctx.escaped(r, at, binds.nth(i), &v))?;
723 }
724 }
725 }
726 match ctx.pat(at, binds.nth(last)) {
727 Pat::None => {
728 let result = eval(at, exprs.nth(last), &env, ctx);
729 ctx.release(env);
730 result
731 }
732 pat => {
733 let v = eval(at, exprs.nth(last), &env, ctx)?;
734 let env = match_pat(at, pat, &v, env, ctx)
735 .map_err(|r| ctx.escaped(r, at, binds.nth(last), &v))?;
736 ctx.release(env);
737 Ok(v)
738 }
739 }
740}
741
742pub fn instantiate(chunk: ChunkId, frame: &[Value], ctx: &Ctx) -> Result<Value, Raised> {
748 let top = ctx.chunk(chunk).top();
749 instantiate_module(chunk, top, frame, ctx)
750}
751
752pub(crate) fn instantiate_module(
762 chunk: ChunkId,
763 module: ModId,
764 frame: &[Value],
765 ctx: &Ctx,
766) -> Result<Value, Raised> {
767 let (frame_len, len) = {
768 let code = ctx.chunk(chunk);
769 (code.module(module).frame.len, code.member_len(module))
770 };
771 if frame.len() != frame_len as usize {
772 return Err(Raised::symbol(Sym::MODULE_ARITY));
773 }
774 let id_base = ctx.reserve_ids(u64::from(len));
775 let frame = if frame.is_empty() {
776 Env::EMPTY
777 } else {
778 Env::EMPTY.frame(Box::from(frame))
779 };
780 Ok(Value::Module(EnvRef::new(EnvNode::Module {
781 chunk,
782 module,
783 id_base,
784 frame,
785 })))
786}
787
788#[inline]
799fn materialize_body(
800 chunk: ChunkId,
801 body: NodeId,
802 env: &Env,
803 id_base: u64,
804 index: u32,
805 ctx: &Ctx,
806) -> Result<Value, Raised> {
807 if let Node::Abs(code) = ctx.node(chunk, body) {
808 return Ok(closure(chunk, code, id_base + u64::from(index), env, ctx));
809 }
810 eval(chunk, body, env, ctx)
811}
812
813fn materialize(env: &Env, name: Sym, ctx: &Ctx) -> Result<Value, Raised> {
818 let (chunk, module, id_base) = env
819 .as_module()
820 .expect("a module object always holds a module terminal");
821 let member = {
822 let code = ctx.chunk(chunk);
823 code.index_of(module, name)
824 .map(|index| (index, code.member(module, index)))
825 };
826 let Some((index, Some(member))) = member else {
827 return Err(Raised::symbol(Sym::MISSING_PROPERTY));
828 };
829 materialize_body(chunk, member.node, env, id_base, index, ctx)
830}
831
832#[inline(never)]
843fn receiver(this: Value, name: &Value, rest: &[Value], ctx: &Ctx) -> Result<Value, Raised> {
844 let Value::Symbol(s) = name else {
845 return Err(Raised::symbol(Sym::NOT_APPLICABLE));
846 };
847 let s = *s;
848 if let Value::List(elems) = &this {
849 let index = match ctx.projection(s) {
850 Projection::Name => None,
851 Projection::Index(i) => Some(i),
852 Projection::TooLarge => return Err(Raised::symbol(Sym::BAD_PROJECTION)),
853 };
854 if let Some(index) = index {
855 let projected = elems
856 .get(index as usize)
857 .cloned()
858 .ok_or_else(|| Raised::symbol(Sym::PROJECTION_OUT_OF_RANGE))?;
859 return apply_n(projected, rest, ctx);
860 }
861 }
862 let proto = if let Value::Object(obj) = &this {
863 obj.proto.clone()
864 } else if let Value::Module(home) = proto_of(&this, ctx) {
865 home
866 } else {
867 unreachable!("a prototype is always a module value")
868 };
869 dispatch(proto, this, s, rest, ctx)
870}
871
872fn dispatch(
881 proto: EnvRef,
882 this: Value,
883 name: Sym,
884 rest: &[Value],
885 ctx: &Ctx,
886) -> Result<Value, Raised> {
887 let method = materialize(&Env::from_ref(proto), name, ctx)?;
888 match rest {
889 [] => apply1(method, this, ctx),
890 [a] => apply_n(method, &[this, a.clone()], ctx),
891 [a, b] => apply_n(method, &[this, a.clone(), b.clone()], ctx),
892 [a, b, c] => apply_n(method, &[this, a.clone(), b.clone(), c.clone()], ctx),
893 _ => {
894 let mut all: Vec<Value> = Vec::with_capacity(rest.len() + 1);
895 all.push(this);
896 all.extend_from_slice(rest);
897 apply_n(method, &all, ctx)
898 }
899 }
900}