cl_interpret/
interpret.rs

1//! A work-in-progress tree walk interpreter for Conlang
2//!
3//! Currently, major parts of the interpreter are not yet implemented, and major parts will never be
4//! implemented in its current form. Namely, since no [ConValue] has a stable location, it's
5//! meaningless to get a pointer to one, and would be undefined behavior to dereference a pointer to
6//! one in any situation.
7#![expect(unused, reason = "Work in progress")]
8
9use super::*;
10use crate::{
11    function::Function,
12    place::Place,
13    typeinfo::{Model, Type, TypeInfo},
14};
15use cl_ast::{
16    types::{Literal, Path},
17    *,
18};
19use cl_structures::intern::interned::Interned;
20use std::{collections::HashMap, iter, rc::Rc, slice};
21
22macro trace($($t:tt)*) {{
23    #[cfg(debug_assertions)]
24    if std::env::var("CONLANG_TRACE").is_ok() {
25        eprintln!($($t)*)
26    }
27}}
28
29/// Turns a `todo!` invocation into an [Error::Panic]
30pub macro cl_todo {
31    () => {
32        Err(Error::Panic(format!("Not yet implemented (at {}:{}:{})", file!(), line!(), column!())))
33    },
34    ($($t:tt)*) => {
35        Err(Error::Panic(format!("Not yet implemented: {} (at {}:{}:{})", format_args!($($t)*), file!(), line!(), column!())))
36    }
37}
38
39/// Turns an `unimplemented!` invocation into an [Error::Panic]
40pub macro cl_unimplemented {
41    () => {
42        Err(Error::Panic(format!("Not implemented (at {}:{}:{})", file!(), line!(), column!())))
43    },
44    ($($t:tt)*) => {
45        Err(Error::Panic(format!("Not implemented: {} (at {}:{}:{})", format_args!($($t)*), file!(), line!(), column!())))
46    }
47}
48
49pub use self::{cl_todo as todo, cl_unimplemented as unimplemented};
50
51/// A work-in-progress tree walk interpreter for Conlang
52pub trait Interpret {
53    /// Interprets this thing in the given [`Environment`].
54    ///
55    /// Everything returns a value!™
56    fn interpret(&self, env: &mut Environment) -> IResult<ConValue>;
57}
58
59impl<T: AstNode + Interpret> Interpret for At<T> {
60    fn interpret(&self, env: &mut Environment) -> IResult<ConValue> {
61        self.0.interpret(env).map_err(|e| e.with_span(self.1))
62    }
63}
64
65impl Interpret for Expr<DefaultTypes> {
66    fn interpret(&self, env: &mut Environment) -> IResult<ConValue> {
67        match self {
68            Self::Omitted => Ok(ConValue::Empty),
69            Self::Id(path) => path.interpret(env),
70            Self::MetId(_) => cl_todo!("Meta-identifiers are not allowed here"),
71            Self::Lit(Literal::Bool(v)) => Ok(ConValue::Bool(*v)),
72            Self::Lit(Literal::Char(v)) => Ok(ConValue::Char(*v)),
73            Self::Lit(Literal::Int(v, _)) => Ok(ConValue::Int(*v as _)),
74            Self::Lit(Literal::Str(v)) => Ok(ConValue::Str(v.as_str().into())),
75            Self::Use(_) => cl_todo!("Use `{self}`"),
76            Self::Bind(bind) => bind.interpret(env),
77            Self::Make(make) => make.interpret(env),
78            Self::Match(mtch) => mtch.interpret(env),
79            Self::Op(op, exprs) => {
80                if self.is_place()
81                    && let Ok(place) = Place::new(self, env)
82                {
83                    place.get(env).cloned()
84                } else {
85                    (*op, exprs.as_slice()).interpret(env)
86                }
87            }
88        }
89    }
90}
91
92impl Interpret for (Op, &[At<Expr>]) {
93    fn interpret(&self, env: &mut Environment) -> IResult<ConValue> {
94        match self {
95            (Op::Do, []) => Ok(ConValue::Empty),
96            (Op::Do, [ats @ .., ret]) => {
97                for at in ats {
98                    at.0.interpret(env)?;
99                }
100                ret.0.interpret(env)
101            }
102            (Op::As, [value, ty]) => match ty.interpret(env)? {
103                ConValue::TypeInfo(ty) => value.interpret(env).map(|v| v.cast(&ty)),
104                other => Err(Error::TypeError("type", other.typename())),
105            },
106            (Op::As, [value, ty]) => cl_todo!("{value} as {ty} operator"),
107            (Op::Block, []) => Ok(ConValue::Empty),
108            (Op::Block, [expr]) => expr.interpret(&mut env.frame("block", None)),
109            (Op::Array, []) => Ok(ConValue::Array(Box::new([]))),
110            (Op::Array, exprs) => Ok(ConValue::Array(
111                exprs
112                    .iter()
113                    .map(|e| e.interpret(env))
114                    .collect::<Result<Box<_>, _>>()?,
115            )),
116            (Op::ArRep, [v, rep]) => {
117                let v = v.interpret(env)?;
118                match rep.interpret(env)? {
119                    ConValue::Int(rep) => {
120                        Ok(ConValue::Array(vec![v; rep as usize].into_boxed_slice()))
121                    }
122                    rep => Err(Error::TypeError("int", rep.typename())),
123                }
124            }
125            (Op::Group, [expr]) => expr.interpret(env),
126            (Op::Tuple, []) => Ok(ConValue::Empty),
127            (Op::Tuple, exprs) => Ok(ConValue::Tuple(
128                exprs
129                    .iter()
130                    .map(|e| e.interpret(env))
131                    .collect::<Result<Box<_>, _>>()?,
132            )),
133            (Op::MetaInner, [_, expr]) => expr.interpret(env),
134            (Op::MetaOuter, [_, expr]) => expr.interpret(env),
135            (Op::Try, [expr]) => expr.interpret(env),
136            (Op::Index, [expr, idx]) => expr.interpret(env)?.index(&idx.interpret(env)?, env),
137            (Op::Call, [expr, arg]) => {
138                let callee = expr.interpret(env)?;
139                match arg.interpret(env)? {
140                    ConValue::Empty => callee.call(env, &[]),
141                    ConValue::Tuple(args) => callee.call(env, &args),
142                    arg => callee.call(env, slice::from_ref(&arg)),
143                }
144            }
145
146            // Annotation operators
147            (Op::Pub, [expr]) => expr.interpret(env),
148            (Op::Const, [expr]) => expr.interpret(env), // we are const
149            (Op::Static, [expr]) => expr.interpret(env), // TODO: "static"
150
151            // Control-flow
152            (Op::Macro, _) => cl_todo!("Macros are not supported in the interpreter"),
153            (Op::Loop, [expr]) => loop {
154                match expr.interpret(env) {
155                    Ok(_) => {}
156                    Err(Error { kind: ErrorKind::Break(v), .. }) => break Ok(v),
157                    Err(Error { kind: ErrorKind::Continue, .. }) => continue,
158                    Err(e) => Err(e)?,
159                }
160            },
161            (Op::If, [cond, pass, fail]) => {
162                let mut scope = env.frame("if", None);
163                if cond.interpret(&mut scope)?.truthy()? {
164                    return pass.interpret(&mut scope);
165                }
166                drop(scope);
167                fail.interpret(env)
168            }
169            (Op::While, [cond, pass, fail]) => {
170                loop {
171                    let mut scope = env.frame("while", Some(cond.1.merge(pass.1)));
172                    if cond.interpret(&mut scope)?.truthy()? {
173                        match pass.interpret(&mut scope) {
174                            Ok(_) => {}
175                            Err(Error { kind: ErrorKind::Break(value), .. }) => return Ok(value),
176                            Err(Error { kind: ErrorKind::Continue, .. }) => continue,
177                            Err(e) => Err(e)?,
178                        }
179                    } else {
180                        break;
181                    }
182                }
183                fail.interpret(env)
184            }
185            (Op::Defer, [expr]) => {
186                env.defer(expr.value().clone());
187                Ok(ConValue::Empty)
188            }
189            (Op::Break, [expr]) => Err(Error::Break(expr.interpret(env)?)),
190            (Op::Return, [expr]) => Err(Error::Return(expr.interpret(env)?)),
191            (Op::Continue, []) => Err(Error::Continue()),
192
193            // Dot projection
194            (Op::Dot, [scrutinee, At(Expr::Op(Op::Call, args), _)]) => {
195                let [callee, args] = args.as_slice() else {
196                    cl_todo!("Interpret non-call {args:?}")?
197                };
198                let scrutinee = Place::new_or_temporary(scrutinee.value(), env)?;
199                let function = callee.interpret(env)?;
200                let args = args.interpret(env)?;
201                match args {
202                    ConValue::Empty => function.call(env, &[ConValue::Ref(scrutinee)]),
203                    ConValue::Tuple(args) => function.call(
204                        env,
205                        &iter::once(ConValue::Ref(scrutinee))
206                            .chain(args) // TODO: remove allocation
207                            .collect::<Box<_>>(),
208                    ),
209                    other => function.call(env, &[ConValue::Ref(scrutinee), other]),
210                }
211            }
212            (
213                Op::Dot,
214                [
215                    At(Expr::Lit(Literal::Int(whole, _)), _),
216                    At(Expr::Lit(Literal::Int(frac, _)), _),
217                ],
218            ) => Ok(ConValue::Float(format!("{whole}.{frac}").parse().unwrap())),
219            (Op::Dot, [scrutinee, At(Expr::Lit(Literal::Int(idx, _)), _)]) => {
220                let place = Place::new_or_temporary(scrutinee.value(), env)?;
221                Ok(ConValue::Ref(place.dot_idx(*idx as _)))
222            }
223            (Op::Dot, [scrutinee, At(Expr::Id(path), _)]) if path.parts.len() == 1 => {
224                let name = path.parts[0];
225                match scrutinee.interpret(env)? {
226                    ConValue::Ref(r) => Ok(ConValue::Ref(r.dot_sym(name))),
227                    ConValue::Struct(_, mut p) => p.remove(&name).ok_or(Error::NotDefined(name)),
228                    ConValue::TypeInfo(ti) => ti.getattr(name),
229                    ConValue::Module(m) => m.get(&name).cloned().ok_or(Error::NotDefined(name)),
230                    other => Err(Error::TypeError(name.to_ref(), other.typename())),
231                }
232            }
233            (Op::Dot, [scrutinee, proj]) => cl_todo!("dot: {scrutinee}.{proj}"),
234
235            // Range operators
236            (Op::RangeEx, [lhs, rhs]) => Ok(ConValue::TupleStruct(
237                env.get_type("RangeExc".into())
238                    .ok_or_else(|| Error::NotDefined("RangeExc".into()))?,
239                Box::new([lhs.interpret(env)?, rhs.interpret(env)?]),
240            )),
241            (Op::RangeIn, [lhs, rhs]) => Ok(ConValue::TupleStruct(
242                env.get_type("RangeInc".into())
243                    .ok_or_else(|| Error::NotDefined("RangeInc".into()))?,
244                Box::new([lhs.interpret(env)?, rhs.interpret(env)?]),
245            )),
246            (Op::RangeEx, [rhs]) => Ok(ConValue::TupleStruct(
247                env.get_type("RangeTo".into())
248                    .ok_or_else(|| Error::NotDefined("RangeTo".into()))?,
249                Box::new([rhs.interpret(env)?]),
250            )),
251            (Op::RangeIn, [rhs]) => Ok(ConValue::TupleStruct(
252                env.get_type("RangeToInc".into())
253                    .ok_or_else(|| Error::NotDefined("RangeToInc".into()))?,
254                Box::new([rhs.interpret(env)?]),
255            )),
256
257            // Unary operators
258            (Op::Neg, [expr]) => {
259                let value = expr.interpret(env)?;
260                env.get("neg".into())?.call(env, &[value])
261            }
262            (Op::Not, [expr]) => {
263                let value = expr.interpret(env)?;
264                env.get("not".into())?.call(env, &[value]) // why is this a builtin
265            }
266            (Op::Identity, [expr]) => expr.interpret(env),
267
268            // Reference manipulation operators
269            (Op::Refer, [expr]) => Ok(ConValue::Ref(Place::new(expr.value(), env)?)),
270            (Op::Deref, [expr]) => match expr.interpret(env)? {
271                ConValue::Ref(place) => place.get(env).cloned(),
272                other => Ok(other),
273            },
274            (Op::Deref, [expr]) => cl_todo!("References: *{expr}"),
275
276            // Binary computation operators
277            (Op::Mul, [lhs, rhs]) => lhs.interpret(env)? * rhs.interpret(env)?,
278            (Op::Div, [lhs, rhs]) => lhs.interpret(env)? / rhs.interpret(env)?,
279            (Op::Rem, [lhs, rhs]) => lhs.interpret(env)? % rhs.interpret(env)?,
280            (Op::Add, [lhs, rhs]) => lhs.interpret(env)? + rhs.interpret(env)?,
281            (Op::Sub, [lhs, rhs]) => lhs.interpret(env)? - rhs.interpret(env)?,
282            (Op::Shl, [lhs, rhs]) => lhs.interpret(env)? << rhs.interpret(env)?,
283            (Op::Shr, [lhs, rhs]) => lhs.interpret(env)? >> rhs.interpret(env)?,
284            (Op::And, [lhs, rhs]) => lhs.interpret(env)? & rhs.interpret(env)?,
285            (Op::Xor, [lhs, rhs]) => lhs.interpret(env)? ^ rhs.interpret(env)?,
286            (Op::Or, [lhs, rhs]) => lhs.interpret(env)? | rhs.interpret(env)?,
287
288            // Comparison operators
289            (Op::Lt, [lhs, rhs]) => lhs.interpret(env)?.lt(&rhs.interpret(env)?),
290            (Op::Leq, [lhs, rhs]) => lhs.interpret(env)?.lt_eq(&rhs.interpret(env)?),
291            (Op::Eq, [lhs, rhs]) => lhs.interpret(env)?.eq(&rhs.interpret(env)?),
292            (Op::Neq, [lhs, rhs]) => lhs.interpret(env)?.neq(&rhs.interpret(env)?),
293            (Op::Geq, [lhs, rhs]) => lhs.interpret(env)?.gt_eq(&rhs.interpret(env)?),
294            (Op::Gt, [lhs, rhs]) => lhs.interpret(env)?.gt(&rhs.interpret(env)?),
295
296            // Logical (control flow) operators
297            (Op::LogAnd, [lhs, rhs]) => {
298                let lhs = lhs.interpret(env)?;
299                if lhs.truthy()? {
300                    rhs.interpret(env)
301                } else {
302                    Ok(lhs)
303                }
304            }
305            (Op::LogXor, [lhs, rhs]) => todo!(),
306            (Op::LogOr, [lhs, rhs]) => {
307                let lhs = lhs.interpret(env)?;
308                if lhs.truthy()? {
309                    Ok(lhs)
310                } else {
311                    rhs.interpret(env)
312                }
313            }
314
315            // Assignment operators
316            (Op::Set, [target, value]) => {
317                let place = Place::new(target.value(), env)?;
318                let value = value.interpret(env)?;
319                *(place.get_mut(env)?) = value;
320                Ok(ConValue::Empty)
321            }
322            (Op::MulSet, [target, value]) => {
323                let place = Place::new(target.value(), env)?;
324                let value = value.interpret(env)?;
325                place.get_mut(env)?.mul_assign(value)?;
326                Ok(ConValue::Empty)
327            }
328            (Op::DivSet, [target, value]) => {
329                let place = Place::new(target.value(), env)?;
330                let value = value.interpret(env)?;
331                place.get_mut(env)?.div_assign(value)?;
332                Ok(ConValue::Empty)
333            }
334            (Op::RemSet, [target, value]) => {
335                let place = Place::new(target.value(), env)?;
336                let value = value.interpret(env)?;
337                place.get_mut(env)?.rem_assign(value)?;
338                Ok(ConValue::Empty)
339            }
340            (Op::AddSet, [target, value]) => {
341                let place = Place::new(target.value(), env)?;
342                let value = value.interpret(env)?;
343                place.get_mut(env)?.add_assign(value)?;
344                Ok(ConValue::Empty)
345            }
346            (Op::SubSet, [target, value]) => {
347                let place = Place::new(target.value(), env)?;
348                let value = value.interpret(env)?;
349                place.get_mut(env)?.sub_assign(value)?;
350                Ok(ConValue::Empty)
351            }
352            (Op::ShlSet, [target, value]) => {
353                let place = Place::new(target.value(), env)?;
354                let value = value.interpret(env)?;
355                place.get_mut(env)?.shl_assign(value)?;
356                Ok(ConValue::Empty)
357            }
358            (Op::ShrSet, [target, value]) => {
359                let place = Place::new(target.value(), env)?;
360                let value = value.interpret(env)?;
361                place.get_mut(env)?.shr_assign(value)?;
362                Ok(ConValue::Empty)
363            }
364            (Op::AndSet, [target, value]) => {
365                let place = Place::new(target.value(), env)?;
366                let value = value.interpret(env)?;
367                place.get_mut(env)?.bitand_assign(value)?;
368                Ok(ConValue::Empty)
369            }
370            (Op::XorSet, [target, value]) => {
371                let place = Place::new(target.value(), env)?;
372                let value = value.interpret(env)?;
373                place.get_mut(env)?.bitxor_assign(value)?;
374                Ok(ConValue::Empty)
375            }
376            (Op::OrSet, [target, value]) => {
377                let place = Place::new(target.value(), env)?;
378                let mut value = value.interpret(env)?;
379                place.get_mut(env)?.bitor_assign(value)?;
380                Ok(ConValue::Empty)
381            }
382            (op, exprs) => cl_unimplemented!("Evaluate {op:?} {exprs:#?}"),
383        }
384    }
385}
386
387impl Interpret for Bind<DefaultTypes> {
388    fn interpret(&self, env: &mut Environment) -> IResult<ConValue> {
389        let Bind(op, _generics, pat, exprs) = self;
390        match (op, pat.value(), exprs.as_slice()) {
391            (BindOp::Let, _, []) => cl_todo!("let {pat}"),
392            (BindOp::Let, _, [scrutinee]) => {
393                let mut bind = HashMap::new();
394                let out = pat.matches(
395                    scrutinee.interpret(env)?,
396                    &mut MatchEnv::new(env, &mut bind),
397                );
398
399                Ok(ConValue::Bool(match out {
400                    Ok(_) => {
401                        for (name, value) in bind {
402                            env.bind(name, value);
403                        }
404                        true
405                    }
406                    Err(e) => false,
407                }))
408            }
409            (BindOp::Let, _, [scrutinee, default]) => {
410                let mut bind = HashMap::new();
411                let out = pat.matches(
412                    scrutinee.interpret(env)?,
413                    &mut MatchEnv::new(env, &mut bind),
414                );
415
416                if out.is_ok() {
417                    for (name, value) in bind {
418                        env.bind(name, value);
419                    }
420                    return Ok(ConValue::Empty);
421                }
422
423                bind.clear();
424                pat.matches(default.interpret(env)?, &mut MatchEnv::new(env, &mut bind))?;
425                for (name, value) in bind {
426                    env.bind(name, value);
427                }
428
429                Ok(ConValue::Empty)
430            }
431            (BindOp::Type, _, []) => cl_todo!("type {pat}"),
432            (BindOp::Type, _, [body]) => cl_todo!("type {pat} = {body}"),
433            (BindOp::Fn, _, [body]) => {
434                let func = Rc::new(Function::new(self));
435                if let Some(name) = func.name() {
436                    env.bind(name, ConValue::Function(func.clone()))
437                }
438                Ok(ConValue::Function(func))
439            }
440            (BindOp::Mod, _, [At(Expr::Op(Op::Block, exprs), ..)]) => {
441                let [body] = exprs.as_slice() else {
442                    todo!("{exprs:?}")?
443                };
444                body.interpret(env)
445            }
446            (BindOp::Mod, _, [body]) => body.interpret(env),
447            (BindOp::Impl, _, [body]) => cl_todo!("impl {pat} {body}"),
448            (BindOp::Struct, pat, []) => {
449                let (name, model) = bind_struct(pat, env)?;
450                Ok(ConValue::TypeInfo(if let Some(name) = name {
451                    let typeid = env.def_type(name, model);
452                    env.bind(name, ConValue::TypeInfo(typeid));
453                    typeid
454                } else {
455                    TypeInfo { ident: None, model }.intern()
456                }))
457            }
458            (BindOp::Struct, Pat::Name(name), []) => {
459                let typeid = env.def_type(*name, typeinfo::Model::Unit(0));
460                env.bind(*name, ConValue::TypeInfo(typeid));
461                Ok(ConValue::TypeInfo(typeid))
462            }
463            (BindOp::Struct, pat, []) => cl_todo!("struct {pat}"),
464            (BindOp::Enum, Pat::Name(name), []) => {
465                let typeid = env.def_type(*name, typeinfo::Model::Never);
466                env.bind(*name, ConValue::TypeInfo(typeid));
467                Ok(ConValue::TypeInfo(typeid))
468            }
469            (BindOp::Enum, pat, []) => bind_enum(pat, env),
470            (BindOp::Enum, _, []) => cl_todo!("enum {pat}"),
471            (BindOp::For, _, [iter, pass, fail]) => {
472                let iter: Box<dyn Iterator<Item = ConValue>> = match iter.interpret(env)? {
473                    ConValue::Array(values) | ConValue::Tuple(values) => {
474                        Box::new(values.into_iter())
475                    }
476                    ConValue::String(str) => Box::new(str.into_chars().map(ConValue::Char)),
477                    ConValue::Str(str) => Box::new(str.to_ref().chars().map(ConValue::Char)),
478                    ConValue::TupleStruct(
479                        Interned(TypeInfo { ident: Some(Interned("RangeExc", ..)), .. }, ..),
480                        bounds,
481                    ) => match *bounds {
482                        [ConValue::Int(start), ConValue::Int(end)] => {
483                            Box::new((start..end).map(ConValue::Int))
484                        }
485                        _ => Err(Error::NotIterable())?,
486                    },
487                    ConValue::TupleStruct(
488                        Interned(TypeInfo { ident: Some(Interned("RangeInc", ..)), .. }, ..),
489                        bounds,
490                    ) => match *bounds {
491                        [ConValue::Int(start), ConValue::Int(end)] => {
492                            Box::new((start..=end).map(ConValue::Int))
493                        }
494                        _ => Err(Error::NotIterable())?,
495                    },
496                    _ => Err(Error::NotIterable())?,
497                };
498                for item in iter {
499                    let mut bind = HashMap::new();
500                    pat.matches(item, &mut MatchEnv::new(env, &mut bind))?;
501
502                    let mut scope = env.with_frame("for-loop", bind);
503                    match pass.interpret(&mut scope) {
504                        Ok(_) => {}
505                        Err(Error { kind: ErrorKind::Break(value), .. }) => return Ok(value),
506                        Err(Error { kind: ErrorKind::Continue, .. }) => continue,
507                        Err(e) => Err(e)?,
508                    }
509                }
510                fail.interpret(env)
511            }
512            _ => cl_unimplemented!("{self}"),
513        }
514    }
515}
516
517impl Interpret for Path {
518    fn interpret(&self, env: &mut Environment) -> IResult<ConValue> {
519        match self.parts.as_slice() {
520            &[name] => env.get(name),
521            [first, names @ ..] => {
522                let mut value = env.get(*first)?;
523                for name in names {
524                    value = match value {
525                        ConValue::Module(values) => {
526                            values.get(name).cloned().ok_or(Error::NotDefined(*name))?
527                        }
528                        ConValue::TypeInfo(ty) => ty.getattr(*name)?,
529                        _ => todo!("{self}")?,
530                    };
531                }
532                Ok(value)
533            }
534            [] => unimplemented!("Empty paths"),
535            _ => todo!("Extract value at {self}"),
536        }
537    }
538}
539
540impl Interpret for Sym {
541    fn interpret(&self, env: &mut Environment) -> IResult<ConValue> {
542        env.get(*self)
543    }
544}
545
546fn find_interned_type(model: &Model) -> Option<Type> {
547    let mut ty: Option<Type> = None;
548    // TODO: these functions should return typeinfos
549    typeinfo::TYPE_INTERNER.get().unwrap().foreach(|v| {
550        if v.model == *model {
551            ty = Some(v.already_interned())
552        }
553    });
554    ty
555}
556
557// TODO: these functions should return typeinfos
558fn bind_struct(pat: &Pat, env: &mut Environment) -> IResult<(Option<Sym>, Model)> {
559    fn bind_struct_op(
560        op: PatOp,
561        pats: &[At<Pat>],
562        env: &mut Environment,
563    ) -> IResult<(Option<Sym>, Model)> {
564        match (op, pats) {
565            (PatOp::MetaOuter | PatOp::MetaInner, [_doc, pat]) => bind_struct(pat.value(), env),
566            (PatOp::Pub | PatOp::Mut, [expr]) => bind_struct(expr.value(), env),
567            (PatOp::Ref, [pat]) => {
568                let (name, ty) = bind_struct(pat.value(), env)?;
569                match find_interned_type(&ty) {
570                    Some(ty) => Ok((name, Model::Ref(ty))),
571                    None => todo!("Ref {pat} in bind_struct_op?"),
572                }
573            }
574            (PatOp::Slice, [pat]) => {
575                let (name, ty) = bind_struct(pat.value(), env)?;
576                match find_interned_type(&ty) {
577                    Some(ty) => Ok((name, Model::Slice(ty))),
578                    None => todo!("Ref {pat} in bind_struct_op?"),
579                }
580            }
581            (PatOp::Ptr, [..]) => todo!("Ptr in bind_struct_op?"),
582            (PatOp::Rest, [..]) => {
583                println!(
584                    "Host backtrace:\n{}",
585                    std::backtrace::Backtrace::force_capture()
586                );
587                todo!("Rest in bind_struct_op?")
588            }
589            (PatOp::RangeEx, [..]) => todo!("RangeEx in bind_struct_op?"),
590            (PatOp::RangeIn, [..]) => todo!("RangeIn in bind_struct_op?"),
591            (PatOp::Record, elements) => {
592                let mut members = Vec::new();
593                let mut exhaustive = true;
594                for (idx, member) in elements.iter().enumerate() {
595                    if let Pat::Op(PatOp::Rest, _) = member.value() {
596                        exhaustive = false;
597                        continue;
598                    }
599                    if let (Some(name), model) = bind_struct(member.value(), env)? {
600                        let mut ti: Option<Type> = find_interned_type(&model);
601                        members.push((name, ti.unwrap_or(env.get_type("_".into()).unwrap())));
602                    }
603                }
604                Ok((None, Model::Struct(members.into_boxed_slice(), exhaustive)))
605            }
606            (PatOp::Tuple, elements) => {
607                let members = elements
608                    .iter()
609                    .map(|pat| {
610                        let (_, model) = bind_struct_op(
611                            PatOp::Typed,
612                            &[Pat::Ignore.at(pat.1), pat.clone()],
613                            env,
614                        )?;
615                        Ok(find_interned_type(&model).unwrap_or(env.get_type("_".into()).unwrap()))
616                    })
617                    .collect::<IResult<_>>()?;
618                Ok((None, Model::Tuple(members)))
619            }
620            (PatOp::Typed, [name, ty]) => {
621                let (name, _) = bind_struct(name.value(), env)?;
622                let (_, ty) = bind_struct(ty.value(), env)?;
623                Ok((name, ty))
624            }
625            (PatOp::TypePrefixed, [name, ty]) => match bind_struct(ty.value(), env)? {
626                (None, model) => Ok((name.value().name(), model)),
627                (Some(name), model) => todo!("Typeprefixed {name} :: {model:?}"),
628            },
629            (PatOp::Generic, [first, ..]) => bind_struct(first.value(), env),
630            _ => todo!("{op:?} ({pats:?})"),
631        }
632    }
633    Ok(match pat {
634        Pat::Ignore => (None, Model::Any),
635        Pat::Never => todo!("Pat::Never in struct binding")?,
636        Pat::MetId(_) => todo!("Pat::MetId in struct binding")?,
637        Pat::Name(name) => match env.get(*name) {
638            Ok(ConValue::TypeInfo(ty)) => (Some(*name), ty.model.clone()),
639            _ => (Some(*name), Model::Unit(0)),
640        },
641        Pat::Value(at) => match at.interpret(env)? {
642            ConValue::TypeInfo(t) => (None, t.model.clone()),
643            other => todo!("Pat::Value({other}) in struct binding")?,
644        },
645        Pat::Op(pat_op, pats) => bind_struct_op(*pat_op, pats, env)?,
646    })
647}
648
649fn bind_enum(pat: &Pat, env: &mut Environment) -> IResult<ConValue> {
650    let name = pat
651        .name()
652        .ok_or_else(|| Error::PatFailed(Box::new(pat.clone())))?;
653    let mut variants = vec![];
654    if let Pat::Op(PatOp::TypePrefixed, pats) = pat
655        && let [prefix, pats] = &pats[..]
656        && let Pat::Op(PatOp::Record, pats) = pats.value()
657    {
658        let mut scope = env.frame(name.to_ref(), Default::default());
659        if let Pat::Op(PatOp::Generic, gens) = prefix.value()
660            && let [prefix, vars @ ..] = gens.as_slice()
661        {
662            for var in vars {
663                let Some(name) = var.value().name() else {
664                    continue;
665                };
666                let t = TypeInfo::new(name, Model::Any).intern();
667                scope.bind(name, ConValue::TypeInfo(t));
668            }
669        }
670        for (idx, pat) in pats.iter().enumerate() {
671            if let (Some(name), model) = bind_struct(pat.value(), &mut scope)? {
672                let model = match model {
673                    Model::Unit(_) => Model::Unit(idx),
674                    _ => model,
675                };
676                let typeid = scope.def_type(name, model);
677                variants.push((name, typeid));
678            }
679        }
680    } else {
681        todo!("Bind other enum: {pat}")?
682    };
683
684    let typeid = env.def_type(name, Model::Enum(variants.into_boxed_slice()));
685    env.bind(name, ConValue::TypeInfo(typeid));
686    Ok(ConValue::TypeInfo(typeid))
687}
688
689impl Interpret for Make<DefaultTypes> {
690    fn interpret(&self, env: &mut Environment) -> IResult<ConValue> {
691        let Self(ty, entries) = self;
692
693        let tyinfo = match ty.interpret(env)? {
694            ConValue::TypeInfo(info) => info,
695            other => Err(Error::TypeError("type", other.typename()))?,
696        };
697
698        let mut members = HashMap::new();
699
700        for MakeArm(name, value) in entries {
701            // todo: disallow redefinition?
702            members.insert(
703                *name,
704                match value {
705                    Some(value) => value.interpret(env),
706                    None => env.get(*name),
707                }?,
708            );
709        }
710
711        tyinfo.make_struct(members)
712    }
713}
714
715impl Interpret for cl_ast::ast::Match<DefaultTypes> {
716    fn interpret(&self, env: &mut Environment) -> IResult<ConValue> {
717        let Self(scrutinee, arms) = self;
718        let scrutinee = scrutinee.interpret(env)?;
719        for MatchArm(pat, expr) in arms {
720            let mut bind = HashMap::new();
721            if pat
722                .matches(scrutinee.clone(), &mut MatchEnv::new(env, &mut bind))
723                .is_ok()
724            {
725                return expr.interpret(&mut env.with_frame("match-arm", bind));
726            }
727        }
728        Err(Error::MatchNonexhaustive(ConValue::Empty))
729    }
730}
731
732pub enum BindingMode {
733    Value,
734    Ref,
735    Ptr,
736}
737
738#[derive(Debug)]
739pub struct MatchEnv<'env> {
740    env: &'env mut Environment,
741    bind: &'env mut HashMap<Sym, ConValue>,
742    public: bool,
743    mutable: bool,
744}
745
746impl MatchEnv<'_> {
747    pub fn new<'e>(env: &'e mut Environment, bind: &'e mut HashMap<Sym, ConValue>) -> MatchEnv<'e> {
748        MatchEnv { env, bind, public: false, mutable: false } // TODO: env.public
749    }
750    pub fn public(&mut self) -> MatchEnv<'_> {
751        let Self { ref mut env, ref mut bind, public: _, mutable } = *self;
752        MatchEnv { env, bind, public: true, mutable }
753    }
754
755    pub fn mutable(&mut self) -> MatchEnv<'_> {
756        let Self { ref mut env, ref mut bind, public, mutable: _ } = *self;
757        MatchEnv { env, bind, public, mutable: true }
758    }
759}
760
761pub trait Match<Value = ConValue> {
762    fn matches<'env>(&self, value: Value, in_env: &mut MatchEnv<'env>) -> IResult<()>;
763}
764
765impl Match for At<Pat> {
766    fn matches<'env>(&self, value: ConValue, in_env: &mut MatchEnv<'env>) -> IResult<()> {
767        self.value().matches(value, in_env)
768    }
769}
770
771impl Match for Pat {
772    fn matches<'env>(&self, value: ConValue, in_env: &mut MatchEnv<'env>) -> IResult<()> {
773        match self {
774            Self::Ignore => Ok(()),
775            Self::Never => todo!("Never"),
776            Self::MetId(_) => todo!("Meta-identifiers are not allowed here"),
777            &Self::Name(name) => {
778                in_env.bind.insert(name, value);
779                Ok(())
780            }
781            Self::Value(at) => {
782                let truth = at.interpret(in_env.env)?;
783                if truth.neq(&value)?.truthy()? {
784                    Err(Error::PatFailed(self.clone().into()))
785                } else {
786                    Ok(())
787                }
788            }
789            Self::Op(pat_op, pats) => (*pat_op, &pats[..]).matches(value, in_env),
790        }
791    }
792}
793
794impl Match for (PatOp, &[At<Pat>]) {
795    fn matches<'env>(&self, value: ConValue, in_env: &mut MatchEnv<'env>) -> IResult<()> {
796        match self {
797            (PatOp::MetaInner | PatOp::MetaOuter, [_doc, pat]) => pat.matches(value, in_env),
798            (PatOp::MetaInner | PatOp::MetaOuter, _) => unimplemented!(),
799            (PatOp::Pub, [pat]) => pat.matches(value, &mut in_env.public()),
800            (PatOp::Pub, _) => unimplemented!(),
801            (PatOp::Mut, [pat]) => pat.matches(value, &mut in_env.mutable()),
802            (PatOp::Mut, _) => unimplemented!(),
803            (PatOp::Ref, [pat]) => match value {
804                ConValue::Ref(place) => {
805                    let value = place
806                        .get(in_env.env)
807                        .cloned()
808                        .map_err(|_| Error::PatFailed(pat.value().clone().into()))?;
809                    pat.matches(value, in_env)
810                }
811                // Auto-referencing in patterns..?
812                other => pat.matches(other, in_env),
813            },
814            (PatOp::Ref, _) => unimplemented!("Ref patterns!"),
815            (PatOp::Ptr, _) => todo!("Raw pointer/deref patterns?"),
816            (PatOp::Rest, []) => Ok(()),
817            // Rest pattern with const value is upper-bounded exclusive range
818            (PatOp::Rest, [At(Pat::Value(end), ..)]) => {
819                if end.interpret(in_env.env)?.lt_eq(&value)?.truthy()? {
820                    return Err(Error::MatchNonexhaustive(value));
821                }
822                Ok(())
823            }
824            (PatOp::Rest, [rest]) => rest.matches(value, in_env),
825            (PatOp::Rest, _) => unimplemented!("rest pattern with more than one arg"),
826            (PatOp::RangeEx, [At(Pat::Value(start), ..)]) => {
827                // RangeEx pattern with const value is lower-bounded exclusive range
828                if start.interpret(in_env.env)?.gt(&value)?.truthy()? {
829                    return Err(Error::MatchNonexhaustive(value));
830                }
831                Ok(())
832            }
833            (PatOp::RangeEx, [At(Pat::Value(start), ..), At(Pat::Value(end), ..)]) => {
834                if start.interpret(in_env.env)?.gt(&value)?.truthy()? {
835                    return Err(Error::MatchNonexhaustive(value));
836                }
837                if end.interpret(in_env.env)?.lt_eq(&value)?.truthy()? {
838                    return Err(Error::MatchNonexhaustive(value));
839                }
840                Ok(())
841            }
842            (PatOp::RangeEx, pats) => todo!("RangeEx patterns: {pats:?}"),
843            (PatOp::RangeIn, [At(Pat::Value(start), ..), At(Pat::Value(end), ..)]) => {
844                if start.interpret(in_env.env)?.gt(&value)?.truthy()? {
845                    return Err(Error::MatchNonexhaustive(value));
846                }
847                if end.interpret(in_env.env)?.lt(&value)?.truthy()? {
848                    return Err(Error::MatchNonexhaustive(value));
849                }
850                Ok(())
851            }
852            (PatOp::RangeIn, pats) => todo!("Range patterns: {pats:?}"),
853            (PatOp::Record, pats) => match_pat_for_struct(pats, value, in_env),
854            (PatOp::Tuple, pats) => match value {
855                ConValue::Empty if pats.is_empty() => Ok(()),
856                ConValue::Tuple(values) => (SliceMode::Tuple, *pats).matches(values, in_env),
857                _ => todo!("Match {pats:?} against {value}"),
858            },
859            (PatOp::Slice, pats) => match value {
860                ConValue::Array(values) => (SliceMode::Slice, *pats).matches(values, in_env),
861                _ => todo!("Match {pats:?} against {value}"),
862            },
863            (PatOp::ArRep, _) => todo!(),
864            (PatOp::Typed, [pat, _ty @ ..]) => pat.matches(value, in_env),
865            (PatOp::Typed, _) => todo!(),
866            (PatOp::TypePrefixed, [At(Pat::Value(e), ..), pat]) => {
867                let ty = match e.interpret(in_env.env)? {
868                    ConValue::TypeInfo(ty) => ty,
869                    other => Err(Error::TypeError("type", other.typename()))?,
870                };
871                match value {
872                    ConValue::Struct(value_ty, _) | ConValue::TupleStruct(value_ty, _)
873                        if ty != value_ty =>
874                    {
875                        Err(Error::TypeError(ty.name(), value_ty.name()))?
876                    }
877                    ConValue::TupleStruct(value_ty, values) => {
878                        pat.matches(ConValue::Tuple(values), in_env)
879                    }
880                    _ => pat.matches(value, in_env),
881                }
882            }
883            (PatOp::TypePrefixed, [pat_name, pat]) => match value {
884                ConValue::TupleStruct(value_type, values) => {
885                    let Some(pat_name) = pat_name.value().name() else {
886                        todo!("{pat_name}({pat})")?
887                    };
888                    if in_env.env.get_type(pat_name) != Some(value_type) {
889                        Err(Error::TypeError(pat_name.to_ref(), value_type.name()))?
890                    }
891                    pat.matches(ConValue::Tuple(values), in_env)
892                }
893                ConValue::Struct(ty, _) => {
894                    let Some(pat_name) = pat_name.value().name() else {
895                        todo!("{pat_name}({pat})")?
896                    };
897                    if in_env.env.get_type(pat_name) != Some(ty) {
898                        Err(Error::TypeError(pat_name.to_ref(), ty.name()))?
899                    }
900                    pat.matches(value, in_env)
901                }
902                _ => pat.matches(value, in_env),
903            },
904            (PatOp::TypePrefixed, _) => todo!("TypePrefixed {self:?}"),
905            (PatOp::Generic, [pat, _subs @ ..]) => pat.matches(value, in_env),
906            (PatOp::Generic, _) => todo!(),
907            (PatOp::Fn, [args, _]) => args.matches(value, in_env),
908            (PatOp::Fn, _) => todo!(),
909            (PatOp::Guard, [pat, At(Pat::Value(cond), ..)]) => {
910                use std::mem::{replace, take};
911                pat.matches(value, in_env)?;
912                let mut scope = in_env.env.with_frame("guard", take(in_env.bind));
913                let value = cond.interpret(&mut scope)?;
914                if value.truthy()? {
915                    *in_env.bind = scope.pop_values().unwrap_or_default();
916                    Ok(())
917                } else {
918                    Err(Error::MatchNonexhaustive(value))
919                }
920            }
921            (PatOp::Guard, _) => unimplemented!("Nonbinary guard patterns!"),
922            &(PatOp::Alt, [first @ .., last]) => {
923                for alt in first {
924                    let mut bind = HashMap::new();
925                    if alt
926                        .matches(value.clone(), &mut MatchEnv::new(in_env.env, &mut bind))
927                        .is_ok()
928                    {
929                        in_env.bind.extend(bind);
930                        return Ok(());
931                    }
932                }
933                last.matches(value, in_env)
934            }
935            (PatOp::Alt, _) => Err(Error::MatchNonexhaustive(value)),
936        }
937    }
938}
939
940fn match_pat_for_struct<'env>(
941    pats: &[At<Pat>],
942    value: ConValue,
943    in_env: &mut MatchEnv<'env>,
944) -> IResult<()> {
945    fn match_typed<'env>(
946        pats: &[At<Pat>],
947        values: &mut HashMap<Sym, ConValue>,
948        in_env: &mut MatchEnv<'env>,
949    ) -> IResult<()> {
950        let [At(Pat::Name(name), ..), dest] = pats else {
951            todo!("match_typed could not find name in typed pattern")?
952        };
953        let Some(value) = values.remove(name) else {
954            todo!("Struct {values:?} has no value at {name}")?
955        };
956        dest.matches(value, in_env)
957    }
958
959    let ConValue::Struct(_, mut values) = value else {
960        todo!("match_pat_for_struct called on {}", value)?
961    };
962
963    for pat in pats {
964        match pat.value() {
965            Pat::Op(PatOp::Typed, pats) => match_typed(pats, &mut values, in_env)?,
966            Pat::Op(PatOp::Rest, pats) if pats.is_empty() => break,
967            pat if let Some(name) = pat.name() => {
968                let Some(value) = values.remove(&name) else {
969                    todo!("Struct {values:?} has no value at {name}")?
970                };
971                pat.matches(value, in_env)?
972            }
973            pat => todo!("{pat}")?,
974        }
975    }
976    Ok(())
977}
978
979enum SliceMode {
980    Slice,
981    Tuple,
982}
983
984impl Match<Box<[ConValue]>> for (SliceMode, &[At<Pat>]) {
985    fn matches<'env>(&self, values: Box<[ConValue]>, in_env: &mut MatchEnv<'env>) -> IResult<()> {
986        let (mode, pats) = self;
987
988        let mut values = values.into_iter();
989        let mut pats = pats.iter().peekable();
990        while !matches!(pats.peek(), None | Some(At(Pat::Op(PatOp::Rest, _), ..))) {
991            let (Some(pat), Some(value)) = (pats.next(), values.next()) else {
992                Err(Error::MatchNonexhaustive(ConValue::Empty))?
993            };
994            pat.matches(value, in_env)?;
995        }
996
997        let mut values = values.rev();
998        let mut pats = pats.rev().peekable();
999        while !matches!(pats.peek(), None | Some(At(Pat::Op(PatOp::Rest, _), ..))) {
1000            let (Some(pat), Some(value)) = (pats.next(), values.next()) else {
1001                Err(Error::MatchNonexhaustive(ConValue::Empty))?
1002            };
1003            pat.matches(value, in_env)?;
1004        }
1005
1006        let mut values = values.into_inner();
1007
1008        match (pats.peek(), values.next()) {
1009            (None, None) => Ok(()),
1010            (None, Some(value)) => Err(Error::MatchNonexhaustive(value)),
1011            (Some(At(Pat::Op(PatOp::Rest, rests), ..)), value) if let [pat] = &rests[..] => {
1012                let values = value.into_iter().chain(values).collect();
1013                match mode {
1014                    SliceMode::Slice => pat.matches(ConValue::Array(values), in_env),
1015                    SliceMode::Tuple => pat.matches(ConValue::Tuple(values), in_env),
1016                }
1017            }
1018            (Some(At(Pat::Op(PatOp::Rest, rests), ..)), _) if rests.is_empty() => Ok(()),
1019            (Some(pat), _) => Err(Error::PatFailed(pat.0.clone().into())),
1020        }
1021    }
1022}
cl_interpret/interpret.rs

cl_interpret/
interpret.rs
