1use std::collections::BTreeMap;
2
3pub type Store = BTreeMap<String, String>;
5
6#[derive(Clone, Debug, PartialEq, Eq)]
8pub enum CanonNum {
9 Finite(i64),
10 Nan,
11 SignedZero(bool),
12 OverflowI64,
13}
14
15impl CanonNum {
16 pub fn token(&self) -> String {
18 match self {
19 Self::Nan => "NAN".into(),
20 Self::OverflowI64 => "OVERFLOW_I64".into(),
21 Self::SignedZero(neg) => format!("SIGNED_ZERO:{}0", if *neg { "-" } else { "+" }),
22 Self::Finite(val) => format!("FINITE_I64:{}", val),
23 }
24 }
25}
26
27pub enum Step {
29 Ret(String),
30 Tau(serde_json::Value, Store),
31 Vis(String, serde_json::Value, Store),
32}
33
34pub(crate) fn encode_num_val(raw: &serde_json::Value) -> Result<CanonNum, String> {
35 if let Some(i) = raw.as_i64() {
36 return Ok(if i == 0 {
37 CanonNum::SignedZero(false)
38 } else {
39 CanonNum::Finite(i)
40 });
41 }
42 if raw.as_u64().is_some() {
43 return Ok(CanonNum::OverflowI64);
44 }
45 if let Some(f) = raw.as_f64() {
46 if f.is_nan() {
47 return Ok(CanonNum::Nan);
48 }
49 if f.is_infinite() || f.fract() != 0.0 {
50 return Ok(CanonNum::OverflowI64);
51 }
52 if f == 0.0 {
53 return Ok(CanonNum::SignedZero(f.is_sign_negative()));
54 }
55 if f >= (i64::MIN as f64) && f < 9223372036854775808.0 {
56 return Ok(CanonNum::Finite(f as i64));
57 }
58 return Ok(CanonNum::OverflowI64);
59 }
60 if let Some(raw_str) = raw.as_str() {
61 let trimmed = raw_str.trim();
62 if trimmed.eq_ignore_ascii_case("NAN") {
63 return Ok(CanonNum::Nan);
64 }
65 if trimmed == "OVERFLOW_I64" {
66 return Ok(CanonNum::OverflowI64);
67 }
68 if matches!(trimmed, "SIGNED_ZERO:+0" | "+0" | "+0.0" | "0" | "0.0") {
69 return Ok(CanonNum::SignedZero(false));
70 }
71 if matches!(trimmed, "SIGNED_ZERO:-0" | "-0" | "-0.0") {
72 return Ok(CanonNum::SignedZero(true));
73 }
74 let body = trimmed.strip_prefix("FINITE_I64:").unwrap_or(trimmed);
75 let digits = body
76 .strip_prefix('+')
77 .or_else(|| body.strip_prefix('-'))
78 .unwrap_or(body);
79 if !digits.is_empty() && digits.bytes().all(|b| b.is_ascii_digit()) {
80 return Ok(match body.parse::<i64>() {
81 Ok(0) => CanonNum::SignedZero(body.starts_with('-')),
82 Ok(val) => CanonNum::Finite(val),
83 Err(_) => CanonNum::OverflowI64,
84 });
85 }
86 }
87 Err(format!("Unsupported numeric literal: {}", raw))
88}
89
90pub(crate) fn apply_num_op(op: &str, left: &CanonNum, right: &CanonNum) -> CanonNum {
91 if matches!(left, CanonNum::Nan) || matches!(right, CanonNum::Nan) {
92 return CanonNum::Nan;
93 }
94 if matches!(left, CanonNum::OverflowI64) || matches!(right, CanonNum::OverflowI64) {
95 return CanonNum::OverflowI64;
96 }
97 let lv = if let CanonNum::Finite(v) = left { *v } else { 0 };
98 let rv = if let CanonNum::Finite(v) = right { *v } else { 0 };
99 if op == "add" || op == "sub" {
100 if let (CanonNum::SignedZero(ln), CanonNum::SignedZero(rn)) = (left, right) {
101 let neg = if op == "add" { *ln && *rn } else { *ln && !*rn };
102 return CanonNum::SignedZero(neg);
103 }
104 let checked = if op == "add" {
105 lv.checked_add(rv)
106 } else {
107 lv.checked_sub(rv)
108 };
109 return match checked {
110 None => CanonNum::OverflowI64,
111 Some(0) => CanonNum::SignedZero(false),
112 Some(val) => CanonNum::Finite(val),
113 };
114 }
115 let ln = match left {
116 CanonNum::SignedZero(neg) => *neg,
117 CanonNum::Finite(val) => *val < 0,
118 _ => false,
119 };
120 let rn = match right {
121 CanonNum::SignedZero(neg) => *neg,
122 CanonNum::Finite(val) => *val < 0,
123 _ => false,
124 };
125 match lv.checked_mul(rv) {
126 None => CanonNum::OverflowI64,
127 Some(0) => CanonNum::SignedZero(ln != rn),
128 Some(val) => CanonNum::Finite(val),
129 }
130}
131
132pub(crate) fn preserve_json_numeric_tokens(raw: &str) -> String {
133 let bytes = raw.as_bytes();
134 let mut out = String::with_capacity(raw.len() + 16);
135 let mut idx = 0;
136 let mut in_string = false;
137 let mut escaped = false;
138 while idx < bytes.len() {
139 let ch = bytes[idx] as char;
140 if in_string {
141 out.push(ch);
142 if escaped {
143 escaped = false;
144 } else if ch == '\\' {
145 escaped = true;
146 } else if ch == '"' {
147 in_string = false;
148 }
149 idx += 1;
150 continue;
151 }
152 if ch == '"' {
153 in_string = true;
154 out.push(ch);
155 idx += 1;
156 continue;
157 }
158 let prev_ok = idx == 0
159 || matches!(
160 bytes[idx - 1],
161 b':' | b',' | b'[' | b' ' | b'\n' | b'\t' | b'\r'
162 );
163 if (ch == '-' || ch.is_ascii_digit()) && prev_ok {
164 let start = idx;
165 idx += 1;
166 while idx < bytes.len() && (bytes[idx].is_ascii_digit() || bytes[idx] == b'.') {
167 idx += 1;
168 }
169 let tok = &raw[start..idx];
170 if tok.starts_with("-0") || tok.trim_start_matches('-').len() >= 15 {
171 out.push('"');
172 out.push_str(tok);
173 out.push('"');
174 } else {
175 out.push_str(tok);
176 }
177 continue;
178 }
179 out.push(ch);
180 idx += 1;
181 }
182 out
183}
184
185pub(crate) fn mk_obj(mut pairs: Vec<(&str, serde_json::Value)>) -> serde_json::Value {
186 pairs.sort_by(|a, b| a.0.cmp(b.0));
187 let mut map = serde_json::Map::new();
188 for (key, val) in pairs {
189 map.insert(key.to_string(), val);
190 }
191 serde_json::Value::Object(map)
192}
193
194fn bin_keys(tag: &str) -> Option<(&'static str, &'static str)> {
195 match tag {
196 "Add" | "Sub" | "Mul" => Some(("left", "right")),
197 "App" => Some(("fn", "arg")),
198 "Seq" => Some(("first", "second")),
199 _ => None,
200 }
201}
202
203pub(crate) fn canon_ast(raw: &serde_json::Value) -> Result<serde_json::Value, String> {
204 let tag = raw
205 .get("tag")
206 .and_then(|v| v.as_str())
207 .ok_or("Missing AST tag")?;
208 if let Some((lk, rk)) = bin_keys(tag) {
209 let lhs = canon_ast(raw.get(lk).ok_or("Missing lhs")?)?;
210 let rhs = canon_ast(raw.get(rk).ok_or("Missing rhs")?)?;
211 return Ok(mk_obj(vec![(lk, lhs), (rk, rhs), ("tag", tag.into())]));
212 }
213 match tag {
214 "Lit" => {
215 let tok = encode_num_val(raw.get("value").ok_or("Missing value")?)?.token();
216 Ok(mk_obj(vec![("tag", "Lit".into()), ("value", tok.into())]))
217 }
218 "Var" | "MCardGet" => {
219 let key = if tag == "Var" { "name" } else { "handle" };
220 let val = raw.get(key).and_then(|v| v.as_str()).ok_or("Missing key")?;
221 Ok(mk_obj(vec![(key, val.into()), ("tag", tag.into())]))
222 }
223 "AddZero" => {
224 let expr = canon_ast(raw.get("expr").ok_or("Missing expr")?)?;
225 Ok(mk_obj(vec![("expr", expr), ("tag", "AddZero".into())]))
226 }
227 "Lam" | "MCardPut" => {
228 let (child_key, str_key) = if tag == "Lam" {
229 ("body", "param")
230 } else {
231 ("expr", "handle")
232 };
233 let child = canon_ast(raw.get(child_key).ok_or("Missing child")?)?;
234 let text = raw
235 .get(str_key)
236 .and_then(|v| v.as_str())
237 .ok_or("Missing str")?;
238 Ok(mk_obj(vec![
239 (child_key, child),
240 (str_key, text.into()),
241 ("tag", tag.into()),
242 ]))
243 }
244 _ => Err(format!("Unknown AST tag: {}", tag)),
245 }
246}
247
248fn subst_ast(node: &serde_json::Value, param: &str, repl: &serde_json::Value) -> serde_json::Value {
249 let tag = node["tag"].as_str().unwrap_or("");
250 if tag == "Var" {
251 return if node["name"].as_str() == Some(param) {
252 repl.clone()
253 } else {
254 node.clone()
255 };
256 }
257 if tag == "Lam" && node["param"].as_str() == Some(param) {
258 return node.clone();
259 }
260 let pairs = node
261 .as_object()
262 .unwrap()
263 .iter()
264 .map(|(k, v)| {
265 let next = if v.is_object() {
266 subst_ast(v, param, repl)
267 } else {
268 v.clone()
269 };
270 (k.as_str(), next)
271 })
272 .collect();
273 mk_obj(pairs)
274}
275
276fn lift_step(step: Step, wrap: impl FnOnce(serde_json::Value) -> serde_json::Value) -> Step {
277 match step {
278 Step::Tau(next, store) => Step::Tau(wrap(next), store),
279 Step::Vis(event, next, store) => Step::Vis(event, wrap(next), store),
280 Step::Ret(val) => Step::Ret(val),
281 }
282}
283
284pub(crate) fn step_ast(expr: &serde_json::Value, store: &Store) -> Step {
285 let tag = expr["tag"].as_str().unwrap_or("");
286 if matches!(tag, "Lit" | "Lam" | "Var") {
287 let ret = if tag == "Lit" {
288 expr["value"].as_str().unwrap().into()
289 } else if tag == "Var" {
290 format!("ERR_UNBOUND:{}", expr["name"].as_str().unwrap())
291 } else {
292 format!(
293 "LAM:{}:{}",
294 expr["param"].as_str().unwrap(),
295 serde_json::to_string(&expr["body"]).unwrap()
296 )
297 };
298 return Step::Ret(ret);
299 }
300 if tag == "AddZero" || tag == "MCardPut" {
301 let inner = &expr["expr"];
302 let sub = step_ast(inner, store);
303 if !matches!(sub, Step::Ret(_)) {
304 return lift_step(sub, |next| {
305 if tag == "AddZero" {
306 mk_obj(vec![("expr", next), ("tag", "AddZero".into())])
307 } else {
308 mk_obj(vec![
309 ("expr", next),
310 ("handle", expr["handle"].clone()),
311 ("tag", "MCardPut".into()),
312 ])
313 }
314 });
315 }
316 if inner["tag"].as_str() != Some("Lit") {
317 return Step::Ret("ERR_TYPE".into());
318 }
319 if tag == "AddZero" {
320 let lhs = encode_num_val(&inner["value"]).unwrap();
321 let nv = apply_num_op("add", &lhs, &CanonNum::SignedZero(false)).token();
322 return Step::Tau(
323 mk_obj(vec![("tag", "Lit".into()), ("value", nv.into())]),
324 store.clone(),
325 );
326 }
327 let handle = expr["handle"].as_str().unwrap();
328 let tok = inner["value"].as_str().unwrap();
329 let mut next_store = store.clone();
330 next_store.insert(handle.into(), tok.into());
331 return Step::Vis(format!("PUT:{}:{}", handle, tok), inner.clone(), next_store);
332 }
333 if tag == "MCardGet" {
334 let handle = expr["handle"].as_str().unwrap();
335 let tok = store
336 .get(handle)
337 .cloned()
338 .unwrap_or_else(|| "SIGNED_ZERO:+0".into());
339 return Step::Vis(
340 format!("GET:{}:{}", handle, tok),
341 mk_obj(vec![("tag", "Lit".into()), ("value", tok.into())]),
342 store.clone(),
343 );
344 }
345 let (lk, rk) = bin_keys(tag).unwrap();
346 let (ln, rn) = (&expr[lk], &expr[rk]);
347 let ls = step_ast(ln, store);
348 if tag == "Seq" && matches!(ls, Step::Ret(_)) {
349 return Step::Tau(rn.clone(), store.clone());
350 }
351 if !matches!(ls, Step::Ret(_)) {
352 return lift_step(ls, |next| {
353 mk_obj(vec![(lk, next), (rk, rn.clone()), ("tag", tag.into())])
354 });
355 }
356 let rs = step_ast(rn, store);
357 if !matches!(rs, Step::Ret(_)) {
358 return lift_step(rs, |next| {
359 mk_obj(vec![(lk, ln.clone()), (rk, next), ("tag", tag.into())])
360 });
361 }
362 if tag == "App" {
363 if ln["tag"].as_str() != Some("Lam") {
364 return Step::Ret("ERR_TYPE".into());
365 }
366 let body = subst_ast(&ln["body"], ln["param"].as_str().unwrap(), rn);
367 return Step::Tau(body, store.clone());
368 }
369 if ln["tag"].as_str() != Some("Lit") || rn["tag"].as_str() != Some("Lit") {
370 return Step::Ret("ERR_TYPE".into());
371 }
372 let op = match tag {
373 "Add" => "add",
374 "Sub" => "sub",
375 _ => "mul",
376 };
377 let nv = apply_num_op(
378 op,
379 &encode_num_val(&ln["value"]).unwrap(),
380 &encode_num_val(&rn["value"]).unwrap(),
381 )
382 .token();
383 Step::Tau(
384 mk_obj(vec![("tag", "Lit".into()), ("value", nv.into())]),
385 store.clone(),
386 )
387}