use std::collections::BTreeMap;
pub type Store = BTreeMap<String, String>;
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum CanonNum {
Finite(i64),
Nan,
SignedZero(bool),
OverflowI64,
}
impl CanonNum {
pub fn token(&self) -> String {
match self {
Self::Nan => "NAN".into(),
Self::OverflowI64 => "OVERFLOW_I64".into(),
Self::SignedZero(neg) => format!("SIGNED_ZERO:{}0", if *neg { "-" } else { "+" }),
Self::Finite(val) => format!("FINITE_I64:{}", val),
}
}
}
pub enum Step {
Ret(String),
Tau(serde_json::Value, Store),
Vis(String, serde_json::Value, Store),
}
pub(crate) fn encode_num_val(raw: &serde_json::Value) -> Result<CanonNum, String> {
if let Some(i) = raw.as_i64() {
return Ok(if i == 0 {
CanonNum::SignedZero(false)
} else {
CanonNum::Finite(i)
});
}
if raw.as_u64().is_some() {
return Ok(CanonNum::OverflowI64);
}
if let Some(f) = raw.as_f64() {
if f.is_nan() {
return Ok(CanonNum::Nan);
}
if f.is_infinite() || f.fract() != 0.0 {
return Ok(CanonNum::OverflowI64);
}
if f == 0.0 {
return Ok(CanonNum::SignedZero(f.is_sign_negative()));
}
if f >= (i64::MIN as f64) && f < 9223372036854775808.0 {
return Ok(CanonNum::Finite(f as i64));
}
return Ok(CanonNum::OverflowI64);
}
if let Some(raw_str) = raw.as_str() {
let trimmed = raw_str.trim();
if trimmed.eq_ignore_ascii_case("NAN") {
return Ok(CanonNum::Nan);
}
if trimmed == "OVERFLOW_I64" {
return Ok(CanonNum::OverflowI64);
}
if matches!(trimmed, "SIGNED_ZERO:+0" | "+0" | "+0.0" | "0" | "0.0") {
return Ok(CanonNum::SignedZero(false));
}
if matches!(trimmed, "SIGNED_ZERO:-0" | "-0" | "-0.0") {
return Ok(CanonNum::SignedZero(true));
}
let body = trimmed.strip_prefix("FINITE_I64:").unwrap_or(trimmed);
let digits = body
.strip_prefix('+')
.or_else(|| body.strip_prefix('-'))
.unwrap_or(body);
if !digits.is_empty() && digits.bytes().all(|b| b.is_ascii_digit()) {
return Ok(match body.parse::<i64>() {
Ok(0) => CanonNum::SignedZero(body.starts_with('-')),
Ok(val) => CanonNum::Finite(val),
Err(_) => CanonNum::OverflowI64,
});
}
}
Err(format!("Unsupported numeric literal: {}", raw))
}
pub(crate) fn apply_num_op(op: &str, left: &CanonNum, right: &CanonNum) -> CanonNum {
if matches!(left, CanonNum::Nan) || matches!(right, CanonNum::Nan) {
return CanonNum::Nan;
}
if matches!(left, CanonNum::OverflowI64) || matches!(right, CanonNum::OverflowI64) {
return CanonNum::OverflowI64;
}
let lv = if let CanonNum::Finite(v) = left { *v } else { 0 };
let rv = if let CanonNum::Finite(v) = right { *v } else { 0 };
if op == "add" || op == "sub" {
if let (CanonNum::SignedZero(ln), CanonNum::SignedZero(rn)) = (left, right) {
let neg = if op == "add" { *ln && *rn } else { *ln && !*rn };
return CanonNum::SignedZero(neg);
}
let checked = if op == "add" {
lv.checked_add(rv)
} else {
lv.checked_sub(rv)
};
return match checked {
None => CanonNum::OverflowI64,
Some(0) => CanonNum::SignedZero(false),
Some(val) => CanonNum::Finite(val),
};
}
let ln = match left {
CanonNum::SignedZero(neg) => *neg,
CanonNum::Finite(val) => *val < 0,
_ => false,
};
let rn = match right {
CanonNum::SignedZero(neg) => *neg,
CanonNum::Finite(val) => *val < 0,
_ => false,
};
match lv.checked_mul(rv) {
None => CanonNum::OverflowI64,
Some(0) => CanonNum::SignedZero(ln != rn),
Some(val) => CanonNum::Finite(val),
}
}
pub(crate) fn preserve_json_numeric_tokens(raw: &str) -> String {
let bytes = raw.as_bytes();
let mut out = String::with_capacity(raw.len() + 16);
let mut idx = 0;
let mut in_string = false;
let mut escaped = false;
while idx < bytes.len() {
let ch = bytes[idx] as char;
if in_string {
out.push(ch);
if escaped {
escaped = false;
} else if ch == '\\' {
escaped = true;
} else if ch == '"' {
in_string = false;
}
idx += 1;
continue;
}
if ch == '"' {
in_string = true;
out.push(ch);
idx += 1;
continue;
}
let prev_ok = idx == 0
|| matches!(
bytes[idx - 1],
b':' | b',' | b'[' | b' ' | b'\n' | b'\t' | b'\r'
);
if (ch == '-' || ch.is_ascii_digit()) && prev_ok {
let start = idx;
idx += 1;
while idx < bytes.len() && (bytes[idx].is_ascii_digit() || bytes[idx] == b'.') {
idx += 1;
}
let tok = &raw[start..idx];
if tok.starts_with("-0") || tok.trim_start_matches('-').len() >= 15 {
out.push('"');
out.push_str(tok);
out.push('"');
} else {
out.push_str(tok);
}
continue;
}
out.push(ch);
idx += 1;
}
out
}
pub(crate) fn mk_obj(mut pairs: Vec<(&str, serde_json::Value)>) -> serde_json::Value {
pairs.sort_by(|a, b| a.0.cmp(b.0));
let mut map = serde_json::Map::new();
for (key, val) in pairs {
map.insert(key.to_string(), val);
}
serde_json::Value::Object(map)
}
fn bin_keys(tag: &str) -> Option<(&'static str, &'static str)> {
match tag {
"Add" | "Sub" | "Mul" => Some(("left", "right")),
"App" => Some(("fn", "arg")),
"Seq" => Some(("first", "second")),
_ => None,
}
}
pub(crate) fn canon_ast(raw: &serde_json::Value) -> Result<serde_json::Value, String> {
let tag = raw
.get("tag")
.and_then(|v| v.as_str())
.ok_or("Missing AST tag")?;
if let Some((lk, rk)) = bin_keys(tag) {
let lhs = canon_ast(raw.get(lk).ok_or("Missing lhs")?)?;
let rhs = canon_ast(raw.get(rk).ok_or("Missing rhs")?)?;
return Ok(mk_obj(vec![(lk, lhs), (rk, rhs), ("tag", tag.into())]));
}
match tag {
"Lit" => {
let tok = encode_num_val(raw.get("value").ok_or("Missing value")?)?.token();
Ok(mk_obj(vec![("tag", "Lit".into()), ("value", tok.into())]))
}
"Var" | "MCardGet" => {
let key = if tag == "Var" { "name" } else { "handle" };
let val = raw.get(key).and_then(|v| v.as_str()).ok_or("Missing key")?;
Ok(mk_obj(vec![(key, val.into()), ("tag", tag.into())]))
}
"AddZero" => {
let expr = canon_ast(raw.get("expr").ok_or("Missing expr")?)?;
Ok(mk_obj(vec![("expr", expr), ("tag", "AddZero".into())]))
}
"Lam" | "MCardPut" => {
let (child_key, str_key) = if tag == "Lam" {
("body", "param")
} else {
("expr", "handle")
};
let child = canon_ast(raw.get(child_key).ok_or("Missing child")?)?;
let text = raw
.get(str_key)
.and_then(|v| v.as_str())
.ok_or("Missing str")?;
Ok(mk_obj(vec![
(child_key, child),
(str_key, text.into()),
("tag", tag.into()),
]))
}
_ => Err(format!("Unknown AST tag: {}", tag)),
}
}
fn subst_ast(node: &serde_json::Value, param: &str, repl: &serde_json::Value) -> serde_json::Value {
let tag = node["tag"].as_str().unwrap_or("");
if tag == "Var" {
return if node["name"].as_str() == Some(param) {
repl.clone()
} else {
node.clone()
};
}
if tag == "Lam" && node["param"].as_str() == Some(param) {
return node.clone();
}
let pairs = node
.as_object()
.unwrap()
.iter()
.map(|(k, v)| {
let next = if v.is_object() {
subst_ast(v, param, repl)
} else {
v.clone()
};
(k.as_str(), next)
})
.collect();
mk_obj(pairs)
}
fn lift_step(step: Step, wrap: impl FnOnce(serde_json::Value) -> serde_json::Value) -> Step {
match step {
Step::Tau(next, store) => Step::Tau(wrap(next), store),
Step::Vis(event, next, store) => Step::Vis(event, wrap(next), store),
Step::Ret(val) => Step::Ret(val),
}
}
pub(crate) fn step_ast(expr: &serde_json::Value, store: &Store) -> Step {
let tag = expr["tag"].as_str().unwrap_or("");
if matches!(tag, "Lit" | "Lam" | "Var") {
let ret = if tag == "Lit" {
expr["value"].as_str().unwrap().into()
} else if tag == "Var" {
format!("ERR_UNBOUND:{}", expr["name"].as_str().unwrap())
} else {
format!(
"LAM:{}:{}",
expr["param"].as_str().unwrap(),
serde_json::to_string(&expr["body"]).unwrap()
)
};
return Step::Ret(ret);
}
if tag == "AddZero" || tag == "MCardPut" {
let inner = &expr["expr"];
let sub = step_ast(inner, store);
if !matches!(sub, Step::Ret(_)) {
return lift_step(sub, |next| {
if tag == "AddZero" {
mk_obj(vec![("expr", next), ("tag", "AddZero".into())])
} else {
mk_obj(vec![
("expr", next),
("handle", expr["handle"].clone()),
("tag", "MCardPut".into()),
])
}
});
}
if inner["tag"].as_str() != Some("Lit") {
return Step::Ret("ERR_TYPE".into());
}
if tag == "AddZero" {
let lhs = encode_num_val(&inner["value"]).unwrap();
let nv = apply_num_op("add", &lhs, &CanonNum::SignedZero(false)).token();
return Step::Tau(
mk_obj(vec![("tag", "Lit".into()), ("value", nv.into())]),
store.clone(),
);
}
let handle = expr["handle"].as_str().unwrap();
let tok = inner["value"].as_str().unwrap();
let mut next_store = store.clone();
next_store.insert(handle.into(), tok.into());
return Step::Vis(format!("PUT:{}:{}", handle, tok), inner.clone(), next_store);
}
if tag == "MCardGet" {
let handle = expr["handle"].as_str().unwrap();
let tok = store
.get(handle)
.cloned()
.unwrap_or_else(|| "SIGNED_ZERO:+0".into());
return Step::Vis(
format!("GET:{}:{}", handle, tok),
mk_obj(vec![("tag", "Lit".into()), ("value", tok.into())]),
store.clone(),
);
}
let (lk, rk) = bin_keys(tag).unwrap();
let (ln, rn) = (&expr[lk], &expr[rk]);
let ls = step_ast(ln, store);
if tag == "Seq" && matches!(ls, Step::Ret(_)) {
return Step::Tau(rn.clone(), store.clone());
}
if !matches!(ls, Step::Ret(_)) {
return lift_step(ls, |next| {
mk_obj(vec![(lk, next), (rk, rn.clone()), ("tag", tag.into())])
});
}
let rs = step_ast(rn, store);
if !matches!(rs, Step::Ret(_)) {
return lift_step(rs, |next| {
mk_obj(vec![(lk, ln.clone()), (rk, next), ("tag", tag.into())])
});
}
if tag == "App" {
if ln["tag"].as_str() != Some("Lam") {
return Step::Ret("ERR_TYPE".into());
}
let body = subst_ast(&ln["body"], ln["param"].as_str().unwrap(), rn);
return Step::Tau(body, store.clone());
}
if ln["tag"].as_str() != Some("Lit") || rn["tag"].as_str() != Some("Lit") {
return Step::Ret("ERR_TYPE".into());
}
let op = match tag {
"Add" => "add",
"Sub" => "sub",
_ => "mul",
};
let nv = apply_num_op(
op,
&encode_num_val(&ln["value"]).unwrap(),
&encode_num_val(&rn["value"]).unwrap(),
)
.token();
Step::Tau(
mk_obj(vec![("tag", "Lit".into()), ("value", nv.into())]),
store.clone(),
)
}