pub mod parse;
pub mod reduce;
pub mod render;
use std::collections::BTreeSet;
use std::hash::{Hash, Hasher};
use crate::layer0::vocabulary::{
GUARD_LIT_NULL, JS_TYPE_BOOLEAN, JS_TYPE_STRING, TERM_KIND_COLLECTION, TERM_KIND_DECIMAL,
TERM_KIND_INTEGER, TERM_KIND_VERDICT,
};
pub use parse::{parse, ParseFailure};
pub use reduce::{
check_kinds, eta_expand, eta_reduce, evaluate, no_primitives, normalize, whnf, PrimRule, Reduced,
Reduction, Resolver, Strategy, Stuck, StuckReason,
};
pub use render::{name_binders, render, render_literal};
#[derive(Clone, Debug, Default)]
pub struct Hint(pub String);
impl PartialEq for Hint {
fn eq(&self, _: &Self) -> bool {
true
}
}
impl Eq for Hint {}
impl Hash for Hint {
fn hash<H: Hasher>(&self, _: &mut H) {}
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub enum Term {
BoundVar(usize),
FreeVar(String),
Abs(Box<Term>, Hint),
App(Box<Term>, Box<Term>),
Lit(Lit),
Prim(String, Vec<Term>),
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum LitKind {
Null,
Boolean,
Integer,
Decimal,
String,
Collection,
Verdict,
}
impl LitKind {
pub fn as_str(self) -> &'static str {
match self {
LitKind::Null => GUARD_LIT_NULL,
LitKind::Boolean => JS_TYPE_BOOLEAN,
LitKind::Integer => TERM_KIND_INTEGER,
LitKind::Decimal => TERM_KIND_DECIMAL,
LitKind::String => JS_TYPE_STRING,
LitKind::Collection => TERM_KIND_COLLECTION,
LitKind::Verdict => TERM_KIND_VERDICT,
}
}
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Verdict {
pub outcome: String,
pub reason: String,
pub invariant_code: String,
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub enum Lit {
Null,
Boolean(bool),
Integer(i64),
Decimal(String),
String(String),
Collection(Collection),
Verdict(Verdict),
}
#[derive(Clone, Debug, Eq)]
pub enum Collection {
List(Vec<Lit>),
Map(Vec<(String, Lit)>),
}
impl Collection {
pub fn is_empty(&self) -> bool {
match self {
Collection::List(items) => items.is_empty(),
Collection::Map(entries) => entries.is_empty(),
}
}
}
impl PartialEq for Collection {
fn eq(&self, other: &Self) -> bool {
match (self, other) {
(Collection::List(left), Collection::List(right)) => left == right,
(Collection::Map(left), Collection::Map(right)) => left == right,
_ => self.is_empty() && other.is_empty(),
}
}
}
impl Hash for Collection {
fn hash<H: Hasher>(&self, state: &mut H) {
match self {
Collection::List(items) => items.hash(state),
Collection::Map(entries) => entries.hash(state),
}
}
}
impl Lit {
pub fn kind(&self) -> LitKind {
match self {
Lit::Null => LitKind::Null,
Lit::Boolean(_) => LitKind::Boolean,
Lit::Integer(_) => LitKind::Integer,
Lit::Decimal(_) => LitKind::Decimal,
Lit::String(_) => LitKind::String,
Lit::Collection(_) => LitKind::Collection,
Lit::Verdict(_) => LitKind::Verdict,
}
}
pub fn decimal(text: impl Into<String>) -> Lit {
Lit::Decimal(text.into())
}
pub fn string(value: impl Into<String>) -> Lit {
Lit::String(value.into())
}
pub fn list(items: impl IntoIterator<Item = Lit>) -> Lit {
Lit::Collection(Collection::List(items.into_iter().collect()))
}
pub fn map(entries: impl IntoIterator<Item = (String, Lit)>) -> Lit {
let mut entries: Vec<(String, Lit)> = entries.into_iter().collect();
entries.sort_by(|left, right| left.0.cmp(&right.0));
Lit::Collection(Collection::Map(entries))
}
pub fn verdict(outcome: impl Into<String>, reason: impl Into<String>, invariant_code: impl Into<String>) -> Lit {
Lit::Verdict(Verdict { outcome: outcome.into(), reason: reason.into(), invariant_code: invariant_code.into() })
}
}
impl Term {
pub fn free(name: impl Into<String>) -> Term {
Term::FreeVar(name.into())
}
pub fn abs(body: Term, hint: impl Into<String>) -> Term {
Term::Abs(Box::new(body), Hint(hint.into()))
}
pub fn app(func: Term, arg: Term) -> Term {
Term::App(Box::new(func), Box::new(arg))
}
pub fn prim(name: impl Into<String>, args: Vec<Term>) -> Term {
Term::Prim(name.into(), args)
}
pub fn children(&self) -> Vec<&Term> {
match self {
Term::Abs(body, _) => vec![body],
Term::App(func, arg) => vec![func, arg],
Term::Prim(_, args) => args.iter().collect(),
_ => Vec::new(),
}
}
pub fn map_children(&self, mut f: impl FnMut(&Term) -> Term) -> Term {
match self {
Term::Abs(body, hint) => Term::Abs(Box::new(f(body)), hint.clone()),
Term::App(func, arg) => Term::app(f(func), f(arg)),
Term::Prim(name, args) => Term::Prim(name.clone(), args.iter().map(f).collect()),
_ => self.clone(),
}
}
pub fn replace_child(&self, position: usize, replacement: Term) -> Term {
let mut replacement = Some(replacement);
let mut index = 0;
self.map_children(|child| {
let next = if index == position { replacement.take() } else { None };
index += 1;
next.unwrap_or_else(|| child.clone())
})
}
fn binders(&self) -> usize {
usize::from(matches!(self, Term::Abs(..)))
}
}
pub fn shift(term: &Term, delta: isize, cutoff: usize) -> Term {
if let Term::BoundVar(index) = term {
if *index < cutoff {
return term.clone();
}
let Some(shifted) = index.checked_add_signed(delta) else { unreachable!() };
return Term::BoundVar(shifted);
}
let inner = cutoff + term.binders();
term.map_children(|child| shift(child, delta, inner))
}
pub fn substitute(term: &Term, index: usize, replacement: &Term) -> Term {
if let Term::BoundVar(found) = term {
return match (*found).cmp(&index) {
std::cmp::Ordering::Equal => shift(replacement, index as isize, 0),
std::cmp::Ordering::Greater => Term::BoundVar(found - 1),
std::cmp::Ordering::Less => term.clone(),
};
}
let inner = index + term.binders();
term.map_children(|child| substitute(child, inner, replacement))
}
pub fn instantiate(body: &Term, argument: &Term) -> Term {
substitute(body, 0, argument)
}
pub fn occurs(term: &Term, index: usize) -> bool {
if let Term::BoundVar(found) = term {
return *found == index;
}
let inner = index + term.binders();
term.children().into_iter().any(|child| occurs(child, inner))
}
pub fn free_names(term: &Term) -> BTreeSet<String> {
if let Term::FreeVar(name) = term {
return BTreeSet::from([name.clone()]);
}
term.children().into_iter().flat_map(free_names).collect()
}
pub fn binder_hints(term: &Term) -> BTreeSet<String> {
let mut hints: BTreeSet<String> = term.children().into_iter().flat_map(binder_hints).collect();
if let Term::Abs(_, hint) = term {
hints.insert(hint.0.clone());
}
hints
}
pub fn depth(term: &Term) -> usize {
let mut deepest = 0;
let mut pending = vec![(term, 1)];
while let Some((node, level)) = pending.pop() {
deepest = deepest.max(level);
pending.extend(node.children().into_iter().map(|child| (child, level + 1)));
}
deepest
}