clm_rust_core/layer0/term/
mod.rs1pub mod parse;
16pub mod reduce;
17pub mod render;
18
19use std::collections::BTreeSet;
20use std::hash::{Hash, Hasher};
21
22use crate::layer0::vocabulary::{
23 GUARD_LIT_NULL, JS_TYPE_BOOLEAN, JS_TYPE_STRING, TERM_KIND_COLLECTION, TERM_KIND_DECIMAL,
24 TERM_KIND_INTEGER, TERM_KIND_VERDICT,
25};
26
27pub use parse::{parse, ParseFailure};
28pub use reduce::{
29 check_kinds, eta_expand, eta_reduce, evaluate, no_primitives, normalize, whnf, PrimRule, Reduced,
30 Reduction, Resolver, Strategy, Stuck, StuckReason,
31};
32pub use render::{name_binders, render, render_literal};
33
34#[derive(Clone, Debug, Default)]
36pub struct Hint(pub String);
37
38impl PartialEq for Hint {
39 fn eq(&self, _: &Self) -> bool {
40 true
41 }
42}
43
44impl Eq for Hint {}
45
46impl Hash for Hint {
47 fn hash<H: Hasher>(&self, _: &mut H) {}
48}
49
50#[derive(Clone, Debug, PartialEq, Eq, Hash)]
51pub enum Term {
52 BoundVar(usize),
53 FreeVar(String),
54 Abs(Box<Term>, Hint),
55 App(Box<Term>, Box<Term>),
56 Lit(Lit),
57 Prim(String, Vec<Term>),
58}
59
60#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
61pub enum LitKind {
62 Null,
63 Boolean,
64 Integer,
65 Decimal,
66 String,
67 Collection,
68 Verdict,
69}
70
71impl LitKind {
72 pub fn as_str(self) -> &'static str {
73 match self {
74 LitKind::Null => GUARD_LIT_NULL,
75 LitKind::Boolean => JS_TYPE_BOOLEAN,
76 LitKind::Integer => TERM_KIND_INTEGER,
77 LitKind::Decimal => TERM_KIND_DECIMAL,
78 LitKind::String => JS_TYPE_STRING,
79 LitKind::Collection => TERM_KIND_COLLECTION,
80 LitKind::Verdict => TERM_KIND_VERDICT,
81 }
82 }
83}
84
85#[derive(Clone, Debug, PartialEq, Eq, Hash)]
86pub struct Verdict {
87 pub outcome: String,
88 pub reason: String,
89 pub invariant_code: String,
90}
91
92#[derive(Clone, Debug, PartialEq, Eq, Hash)]
93pub enum Lit {
94 Null,
95 Boolean(bool),
96 Integer(i64),
97 Decimal(String),
99 String(String),
100 Collection(Collection),
101 Verdict(Verdict),
102}
103
104#[derive(Clone, Debug, Eq)]
106pub enum Collection {
107 List(Vec<Lit>),
108 Map(Vec<(String, Lit)>),
109}
110
111impl Collection {
112 pub fn is_empty(&self) -> bool {
113 match self {
114 Collection::List(items) => items.is_empty(),
115 Collection::Map(entries) => entries.is_empty(),
116 }
117 }
118}
119
120impl PartialEq for Collection {
121 fn eq(&self, other: &Self) -> bool {
122 match (self, other) {
123 (Collection::List(left), Collection::List(right)) => left == right,
124 (Collection::Map(left), Collection::Map(right)) => left == right,
125 _ => self.is_empty() && other.is_empty(),
126 }
127 }
128}
129
130impl Hash for Collection {
132 fn hash<H: Hasher>(&self, state: &mut H) {
133 match self {
134 Collection::List(items) => items.hash(state),
135 Collection::Map(entries) => entries.hash(state),
136 }
137 }
138}
139
140impl Lit {
141 pub fn kind(&self) -> LitKind {
142 match self {
143 Lit::Null => LitKind::Null,
144 Lit::Boolean(_) => LitKind::Boolean,
145 Lit::Integer(_) => LitKind::Integer,
146 Lit::Decimal(_) => LitKind::Decimal,
147 Lit::String(_) => LitKind::String,
148 Lit::Collection(_) => LitKind::Collection,
149 Lit::Verdict(_) => LitKind::Verdict,
150 }
151 }
152
153 pub fn decimal(text: impl Into<String>) -> Lit {
154 Lit::Decimal(text.into())
155 }
156
157 pub fn string(value: impl Into<String>) -> Lit {
158 Lit::String(value.into())
159 }
160
161 pub fn list(items: impl IntoIterator<Item = Lit>) -> Lit {
162 Lit::Collection(Collection::List(items.into_iter().collect()))
163 }
164
165 pub fn map(entries: impl IntoIterator<Item = (String, Lit)>) -> Lit {
167 let mut entries: Vec<(String, Lit)> = entries.into_iter().collect();
168 entries.sort_by(|left, right| left.0.cmp(&right.0));
169 Lit::Collection(Collection::Map(entries))
170 }
171
172 pub fn verdict(outcome: impl Into<String>, reason: impl Into<String>, invariant_code: impl Into<String>) -> Lit {
173 Lit::Verdict(Verdict { outcome: outcome.into(), reason: reason.into(), invariant_code: invariant_code.into() })
174 }
175}
176
177impl Term {
178 pub fn free(name: impl Into<String>) -> Term {
179 Term::FreeVar(name.into())
180 }
181
182 pub fn abs(body: Term, hint: impl Into<String>) -> Term {
183 Term::Abs(Box::new(body), Hint(hint.into()))
184 }
185
186 pub fn app(func: Term, arg: Term) -> Term {
187 Term::App(Box::new(func), Box::new(arg))
188 }
189
190 pub fn prim(name: impl Into<String>, args: Vec<Term>) -> Term {
191 Term::Prim(name.into(), args)
192 }
193
194 pub fn children(&self) -> Vec<&Term> {
195 match self {
196 Term::Abs(body, _) => vec![body],
197 Term::App(func, arg) => vec![func, arg],
198 Term::Prim(_, args) => args.iter().collect(),
199 _ => Vec::new(),
200 }
201 }
202
203 pub fn map_children(&self, mut f: impl FnMut(&Term) -> Term) -> Term {
205 match self {
206 Term::Abs(body, hint) => Term::Abs(Box::new(f(body)), hint.clone()),
207 Term::App(func, arg) => Term::app(f(func), f(arg)),
208 Term::Prim(name, args) => Term::Prim(name.clone(), args.iter().map(f).collect()),
209 _ => self.clone(),
210 }
211 }
212
213 pub fn replace_child(&self, position: usize, replacement: Term) -> Term {
215 let mut replacement = Some(replacement);
216 let mut index = 0;
217 self.map_children(|child| {
218 let next = if index == position { replacement.take() } else { None };
219 index += 1;
220 next.unwrap_or_else(|| child.clone())
221 })
222 }
223
224 fn binders(&self) -> usize {
225 usize::from(matches!(self, Term::Abs(..)))
226 }
227}
228
229pub fn shift(term: &Term, delta: isize, cutoff: usize) -> Term {
233 if let Term::BoundVar(index) = term {
234 if *index < cutoff {
235 return term.clone();
236 }
237 let Some(shifted) = index.checked_add_signed(delta) else { unreachable!() };
238 return Term::BoundVar(shifted);
239 }
240 let inner = cutoff + term.binders();
241 term.map_children(|child| shift(child, delta, inner))
242}
243
244pub fn substitute(term: &Term, index: usize, replacement: &Term) -> Term {
248 if let Term::BoundVar(found) = term {
249 return match (*found).cmp(&index) {
250 std::cmp::Ordering::Equal => shift(replacement, index as isize, 0),
251 std::cmp::Ordering::Greater => Term::BoundVar(found - 1),
252 std::cmp::Ordering::Less => term.clone(),
253 };
254 }
255 let inner = index + term.binders();
256 term.map_children(|child| substitute(child, inner, replacement))
257}
258
259pub fn instantiate(body: &Term, argument: &Term) -> Term {
261 substitute(body, 0, argument)
262}
263
264pub fn occurs(term: &Term, index: usize) -> bool {
266 if let Term::BoundVar(found) = term {
267 return *found == index;
268 }
269 let inner = index + term.binders();
270 term.children().into_iter().any(|child| occurs(child, inner))
271}
272
273pub fn free_names(term: &Term) -> BTreeSet<String> {
274 if let Term::FreeVar(name) = term {
275 return BTreeSet::from([name.clone()]);
276 }
277 term.children().into_iter().flat_map(free_names).collect()
278}
279
280pub fn binder_hints(term: &Term) -> BTreeSet<String> {
281 let mut hints: BTreeSet<String> = term.children().into_iter().flat_map(binder_hints).collect();
282 if let Term::Abs(_, hint) = term {
283 hints.insert(hint.0.clone());
284 }
285 hints
286}
287
288pub fn depth(term: &Term) -> usize {
290 let mut deepest = 0;
291 let mut pending = vec![(term, 1)];
292 while let Some((node, level)) = pending.pop() {
293 deepest = deepest.max(level);
294 pending.extend(node.children().into_iter().map(|child| (child, level + 1)));
295 }
296 deepest
297}