behavior-contracts 0.2.5

//! canonical — canonical-serialization.md reference implementation.
//!
//! Three primitives:
//!   - `py_float_repr(n)`   : CPython repr(float) byte-identical decimal.
//!   - `canonical_value(v)` : key identity (top-level keys sorted only).
//!   - `canonical_json(v)`  : fingerprint (all levels key-sorted; arrays keep order).
//!
//! Object-key sort is Unicode **code-point order** across all languages. Rust
//! `str` Ord is UTF-8 byte order which equals code-point order, so `sort()` on
//! `&str`/`String` is the normative comparator (verified by the astral vector).

use crate::expr::FORBIDDEN_OBJECT_KEY;
use crate::value::Value;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum CanonicalFailureCode {
    NanOrInf,
    InvalidValue,
    ForbiddenKey,
}

impl CanonicalFailureCode {
    pub fn as_str(self) -> &'static str {
        match self {
            CanonicalFailureCode::NanOrInf => "NAN_OR_INF",
            CanonicalFailureCode::InvalidValue => "INVALID_VALUE",
            CanonicalFailureCode::ForbiddenKey => "FORBIDDEN_KEY",
        }
    }
}

#[derive(Debug, Clone)]
pub struct CanonicalFailure {
    pub code: CanonicalFailureCode,
    pub message: String,
}

impl std::fmt::Display for CanonicalFailure {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}: {}", self.code.as_str(), self.message)
    }
}
impl std::error::Error for CanonicalFailure {}

fn fail<T>(code: CanonicalFailureCode, message: impl Into<String>) -> Result<T, CanonicalFailure> {
    Err(CanonicalFailure {
        code,
        message: message.into(),
    })
}

/// Reject an object whose own keys contain `"__proto__"` (fail-closed), matching
/// the expression `obj` node's forbidden-key rule (expression-ir.md §2.3/§8).
fn guard_keys(pairs: &[(String, Value)]) -> Result<(), CanonicalFailure> {
    if pairs.iter().any(|(k, _)| k == FORBIDDEN_OBJECT_KEY) {
        return fail(
            CanonicalFailureCode::ForbiddenKey,
            format!("object key \"{FORBIDDEN_OBJECT_KEY}\" is forbidden (fail-closed)"),
        );
    }
    Ok(())
}

// ── §4.1 CPython repr(float) — ported from graphddb pyfloat.{rs,go} ──────────
/// Render `f` exactly as CPython `repr(float)` / `json.dumps(float)` would.
/// Finite floats only; NaN/±Inf return a Failure.
pub fn py_float_repr(f: f64) -> Result<String, CanonicalFailure> {
    if f.is_nan() || f.is_infinite() {
        return fail(
            CanonicalFailureCode::NanOrInf,
            format!("non-finite float cannot be serialized: {f}"),
        );
    }
    // Zero handled before digit extraction. f == 0.0 matches +0.0 and -0.0;
    // the sign is recovered via is_sign_negative.
    if f == 0.0 {
        return Ok(if f.is_sign_negative() {
            "-0.0".into()
        } else {
            "0.0".into()
        });
    }

    let (neg, digits, decpt) = shortest_digits(f);
    let n = digits.len() as i32;

    // format_float_short 'r': scientific iff decpt <= -4 or decpt > 16.
    let out = if decpt <= -4 || decpt > 16 {
        let mut mant = String::new();
        mant.push(digits.as_bytes()[0] as char);
        if n > 1 {
            mant.push('.');
            mant.push_str(&digits[1..]);
        }
        let e = decpt - 1;
        let esign = if e < 0 { '-' } else { '+' };
        let mut eabs = e.abs().to_string();
        if eabs.len() < 2 {
            eabs = format!("0{eabs}");
        }
        format!("{mant}e{esign}{eabs}")
    } else if decpt <= 0 {
        format!("0.{}{}", "0".repeat((-decpt) as usize), digits)
    } else if decpt >= n {
        format!("{}{}.0", digits, "0".repeat((decpt - n) as usize))
    } else {
        format!(
            "{}.{}",
            &digits[..decpt as usize],
            &digits[decpt as usize..]
        )
    };

    Ok(if neg { format!("-{out}") } else { out })
}

/// Shortest round-trip decimal digits + decimal-point position (CPython David-Gay
/// mode 0 with round-half-to-even tie-break; matches `{:.p e}` smallest p that
/// round-trips).
fn shortest_digits(f: f64) -> (bool, String, i32) {
    let mut chosen: Option<String> = None;
    for p in 0..=17usize {
        let s = format!("{:.*e}", p, f);
        if s.parse::<f64>() == Ok(f) {
            chosen = Some(s);
            break;
        }
    }
    let s = chosen.unwrap_or_else(|| format!("{:.17e}", f));
    let mut bytes = s.as_str();
    let neg = bytes.starts_with('-');
    if neg {
        bytes = &bytes[1..];
    }
    let (mantissa, exp_part) = match bytes.split_once('e') {
        Some((m, e)) => (m, e),
        None => (bytes, "0"),
    };
    let exp: i32 = exp_part.parse().expect("f64 {:e} exponent is integer");
    let (int_part, frac_part) = match mantissa.split_once('.') {
        Some((i, f)) => (i, f),
        None => (mantissa, ""),
    };
    let mut digits: String = format!("{int_part}{frac_part}");
    let mut decpt = int_part.len() as i32 + exp;

    let lead = digits.len() - digits.trim_start_matches('0').len();
    if lead == digits.len() {
        return (neg, "0".to_string(), 1);
    }
    digits = digits[lead..].to_string();
    decpt -= lead as i32;

    let trimmed = digits.trim_end_matches('0');
    let digits = if trimmed.is_empty() {
        "0".to_string()
    } else {
        trimmed.to_string()
    };
    (neg, digits, decpt)
}

// ── §2 canonicalValue — top-level keys sorted only ───────────────────────────
/// Key-identity canonical serialization: only the top-level object's keys are
/// code-point sorted; nested values keep insertion order.
pub fn canonical_value(v: &Value) -> Result<String, CanonicalFailure> {
    if let Value::Obj(pairs) = v {
        guard_keys(pairs)?;
        let mut keyed: Vec<&(String, Value)> = pairs.iter().collect();
        keyed.sort_by(|a, b| a.0.cmp(&b.0)); // code-point order (UTF-8 byte order)
        let mut parts = Vec::with_capacity(keyed.len());
        for (k, val) in keyed {
            parts.push(format!("{}:{}", json_string(k), encode_nested(val)?));
        }
        Ok(format!("{{{}}}", parts.join(",")))
    } else {
        encode_nested(v)
    }
}

// ── §3 canonicalJson — all levels key-sorted ─────────────────────────────────
/// Fingerprint canonical serialization: all object levels code-point key-sorted;
/// arrays keep order.
pub fn canonical_json(v: &Value) -> Result<String, CanonicalFailure> {
    match v {
        Value::Obj(pairs) => {
            guard_keys(pairs)?;
            let mut keyed: Vec<&(String, Value)> = pairs.iter().collect();
            keyed.sort_by(|a, b| a.0.cmp(&b.0));
            let mut parts = Vec::with_capacity(keyed.len());
            for (k, val) in keyed {
                parts.push(format!("{}:{}", json_string(k), canonical_json(val)?));
            }
            Ok(format!("{{{}}}", parts.join(",")))
        }
        Value::Arr(a) => {
            let mut parts = Vec::with_capacity(a.len());
            for e in a {
                parts.push(canonical_json(e)?);
            }
            Ok(format!("[{}]", parts.join(",")))
        }
        _ => scalar_json(v),
    }
}

fn encode_nested(v: &Value) -> Result<String, CanonicalFailure> {
    match v {
        Value::Obj(pairs) => {
            guard_keys(pairs)?;
            let mut parts = Vec::with_capacity(pairs.len());
            for (k, val) in pairs {
                parts.push(format!("{}:{}", json_string(k), encode_nested(val)?));
            }
            Ok(format!("{{{}}}", parts.join(",")))
        }
        Value::Arr(a) => {
            let mut parts = Vec::with_capacity(a.len());
            for e in a {
                parts.push(encode_nested(e)?);
            }
            Ok(format!("[{}]", parts.join(",")))
        }
        _ => scalar_json(v),
    }
}

fn scalar_json(v: &Value) -> Result<String, CanonicalFailure> {
    match v {
        Value::Null => Ok("null".into()),
        Value::Bool(b) => Ok(if *b { "true".into() } else { "false".into() }),
        Value::Str(s) => Ok(json_string(s)),
        Value::Int(i) => Ok(i.to_string()),
        Value::Float(f) => py_float_repr(*f),
        _ => fail(
            CanonicalFailureCode::InvalidValue,
            "cannot serialize value of unknown type",
        ),
    }
}

/// JSON-encode a string with ensure_ascii=False semantics (non-ASCII passed
/// through as UTF-8, matching `JSON.stringify` / `json.dumps(ensure_ascii=False)`).
fn json_string(s: &str) -> String {
    let mut out = String::with_capacity(s.len() + 2);
    out.push('"');
    for c in s.chars() {
        match c {
            '"' => out.push_str("\\\""),
            '\\' => out.push_str("\\\\"),
            '\n' => out.push_str("\\n"),
            '\r' => out.push_str("\\r"),
            '\t' => out.push_str("\\t"),
            '\u{08}' => out.push_str("\\b"),
            '\u{0c}' => out.push_str("\\f"),
            c if (c as u32) < 0x20 => out.push_str(&format!("\\u{:04x}", c as u32)),
            c => out.push(c),
        }
    }
    out.push('"');
    out
}