cl_interpret/
interpret.rs

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

cl_interpret/
interpret.rs
