behavior_contracts/
canonical.rs

1//! canonical — canonical-serialization.md reference implementation.
2//!
3//! Three primitives:
4//!   - `py_float_repr(n)`   : CPython repr(float) byte-identical decimal.
5//!   - `canonical_value(v)` : key identity (top-level keys sorted only).
6//!   - `canonical_json(v)`  : fingerprint (all levels key-sorted; arrays keep order).
7//!
8//! Object-key sort is Unicode **code-point order** across all languages. Rust
9//! `str` Ord is UTF-8 byte order which equals code-point order, so `sort()` on
10//! `&str`/`String` is the normative comparator (verified by the astral vector).
11
12use crate::expr::FORBIDDEN_OBJECT_KEY;
13use crate::value::Value;
14
15#[derive(Debug, Clone, Copy, PartialEq, Eq)]
16pub enum CanonicalFailureCode {
17    NanOrInf,
18    InvalidValue,
19    ForbiddenKey,
20}
21
22impl CanonicalFailureCode {
23    pub fn as_str(self) -> &'static str {
24        match self {
25            CanonicalFailureCode::NanOrInf => "NAN_OR_INF",
26            CanonicalFailureCode::InvalidValue => "INVALID_VALUE",
27            CanonicalFailureCode::ForbiddenKey => "FORBIDDEN_KEY",
28        }
29    }
30}
31
32#[derive(Debug, Clone)]
33pub struct CanonicalFailure {
34    pub code: CanonicalFailureCode,
35    pub message: String,
36}
37
38impl std::fmt::Display for CanonicalFailure {
39    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
40        write!(f, "{}: {}", self.code.as_str(), self.message)
41    }
42}
43impl std::error::Error for CanonicalFailure {}
44
45fn fail<T>(code: CanonicalFailureCode, message: impl Into<String>) -> Result<T, CanonicalFailure> {
46    Err(CanonicalFailure {
47        code,
48        message: message.into(),
49    })
50}
51
52/// Reject an object whose own keys contain `"__proto__"` (fail-closed), matching
53/// the expression `obj` node's forbidden-key rule (expression-ir.md §2.3/§8).
54fn guard_keys(pairs: &[(String, Value)]) -> Result<(), CanonicalFailure> {
55    if pairs.iter().any(|(k, _)| k == FORBIDDEN_OBJECT_KEY) {
56        return fail(
57            CanonicalFailureCode::ForbiddenKey,
58            format!("object key \"{FORBIDDEN_OBJECT_KEY}\" is forbidden (fail-closed)"),
59        );
60    }
61    Ok(())
62}
63
64// ── §4.1 CPython repr(float) — ported from graphddb pyfloat.{rs,go} ──────────
65/// Render `f` exactly as CPython `repr(float)` / `json.dumps(float)` would.
66/// Finite floats only; NaN/±Inf return a Failure.
67pub fn py_float_repr(f: f64) -> Result<String, CanonicalFailure> {
68    if f.is_nan() || f.is_infinite() {
69        return fail(
70            CanonicalFailureCode::NanOrInf,
71            format!("non-finite float cannot be serialized: {f}"),
72        );
73    }
74    // Zero handled before digit extraction. f == 0.0 matches +0.0 and -0.0;
75    // the sign is recovered via is_sign_negative.
76    if f == 0.0 {
77        return Ok(if f.is_sign_negative() {
78            "-0.0".into()
79        } else {
80            "0.0".into()
81        });
82    }
83
84    let (neg, digits, decpt) = shortest_digits(f);
85    let n = digits.len() as i32;
86
87    // format_float_short 'r': scientific iff decpt <= -4 or decpt > 16.
88    let out = if decpt <= -4 || decpt > 16 {
89        let mut mant = String::new();
90        mant.push(digits.as_bytes()[0] as char);
91        if n > 1 {
92            mant.push('.');
93            mant.push_str(&digits[1..]);
94        }
95        let e = decpt - 1;
96        let esign = if e < 0 { '-' } else { '+' };
97        let mut eabs = e.abs().to_string();
98        if eabs.len() < 2 {
99            eabs = format!("0{eabs}");
100        }
101        format!("{mant}e{esign}{eabs}")
102    } else if decpt <= 0 {
103        format!("0.{}{}", "0".repeat((-decpt) as usize), digits)
104    } else if decpt >= n {
105        format!("{}{}.0", digits, "0".repeat((decpt - n) as usize))
106    } else {
107        format!(
108            "{}.{}",
109            &digits[..decpt as usize],
110            &digits[decpt as usize..]
111        )
112    };
113
114    Ok(if neg { format!("-{out}") } else { out })
115}
116
117/// Shortest round-trip decimal digits + decimal-point position (CPython David-Gay
118/// mode 0 with round-half-to-even tie-break; matches `{:.p e}` smallest p that
119/// round-trips).
120fn shortest_digits(f: f64) -> (bool, String, i32) {
121    let mut chosen: Option<String> = None;
122    for p in 0..=17usize {
123        let s = format!("{:.*e}", p, f);
124        if s.parse::<f64>() == Ok(f) {
125            chosen = Some(s);
126            break;
127        }
128    }
129    let s = chosen.unwrap_or_else(|| format!("{:.17e}", f));
130    let mut bytes = s.as_str();
131    let neg = bytes.starts_with('-');
132    if neg {
133        bytes = &bytes[1..];
134    }
135    let (mantissa, exp_part) = match bytes.split_once('e') {
136        Some((m, e)) => (m, e),
137        None => (bytes, "0"),
138    };
139    let exp: i32 = exp_part.parse().expect("f64 {:e} exponent is integer");
140    let (int_part, frac_part) = match mantissa.split_once('.') {
141        Some((i, f)) => (i, f),
142        None => (mantissa, ""),
143    };
144    let mut digits: String = format!("{int_part}{frac_part}");
145    let mut decpt = int_part.len() as i32 + exp;
146
147    let lead = digits.len() - digits.trim_start_matches('0').len();
148    if lead == digits.len() {
149        return (neg, "0".to_string(), 1);
150    }
151    digits = digits[lead..].to_string();
152    decpt -= lead as i32;
153
154    let trimmed = digits.trim_end_matches('0');
155    let digits = if trimmed.is_empty() {
156        "0".to_string()
157    } else {
158        trimmed.to_string()
159    };
160    (neg, digits, decpt)
161}
162
163// ── §2 canonicalValue — top-level keys sorted only ───────────────────────────
164/// Key-identity canonical serialization: only the top-level object's keys are
165/// code-point sorted; nested values keep insertion order.
166pub fn canonical_value(v: &Value) -> Result<String, CanonicalFailure> {
167    if let Value::Obj(pairs) = v {
168        guard_keys(pairs)?;
169        let mut keyed: Vec<&(String, Value)> = pairs.iter().collect();
170        keyed.sort_by(|a, b| a.0.cmp(&b.0)); // code-point order (UTF-8 byte order)
171        let mut parts = Vec::with_capacity(keyed.len());
172        for (k, val) in keyed {
173            parts.push(format!("{}:{}", json_string(k), encode_nested(val)?));
174        }
175        Ok(format!("{{{}}}", parts.join(",")))
176    } else {
177        encode_nested(v)
178    }
179}
180
181// ── §3 canonicalJson — all levels key-sorted ─────────────────────────────────
182/// Fingerprint canonical serialization: all object levels code-point key-sorted;
183/// arrays keep order.
184pub fn canonical_json(v: &Value) -> Result<String, CanonicalFailure> {
185    match v {
186        Value::Obj(pairs) => {
187            guard_keys(pairs)?;
188            let mut keyed: Vec<&(String, Value)> = pairs.iter().collect();
189            keyed.sort_by(|a, b| a.0.cmp(&b.0));
190            let mut parts = Vec::with_capacity(keyed.len());
191            for (k, val) in keyed {
192                parts.push(format!("{}:{}", json_string(k), canonical_json(val)?));
193            }
194            Ok(format!("{{{}}}", parts.join(",")))
195        }
196        Value::Arr(a) => {
197            let mut parts = Vec::with_capacity(a.len());
198            for e in a {
199                parts.push(canonical_json(e)?);
200            }
201            Ok(format!("[{}]", parts.join(",")))
202        }
203        _ => scalar_json(v),
204    }
205}
206
207fn encode_nested(v: &Value) -> Result<String, CanonicalFailure> {
208    match v {
209        Value::Obj(pairs) => {
210            guard_keys(pairs)?;
211            let mut parts = Vec::with_capacity(pairs.len());
212            for (k, val) in pairs {
213                parts.push(format!("{}:{}", json_string(k), encode_nested(val)?));
214            }
215            Ok(format!("{{{}}}", parts.join(",")))
216        }
217        Value::Arr(a) => {
218            let mut parts = Vec::with_capacity(a.len());
219            for e in a {
220                parts.push(encode_nested(e)?);
221            }
222            Ok(format!("[{}]", parts.join(",")))
223        }
224        _ => scalar_json(v),
225    }
226}
227
228fn scalar_json(v: &Value) -> Result<String, CanonicalFailure> {
229    match v {
230        Value::Null => Ok("null".into()),
231        Value::Bool(b) => Ok(if *b { "true".into() } else { "false".into() }),
232        Value::Str(s) => Ok(json_string(s)),
233        Value::Int(i) => Ok(i.to_string()),
234        Value::Float(f) => py_float_repr(*f),
235        _ => fail(
236            CanonicalFailureCode::InvalidValue,
237            "cannot serialize value of unknown type",
238        ),
239    }
240}
241
242/// JSON-encode a string with ensure_ascii=False semantics (non-ASCII passed
243/// through as UTF-8, matching `JSON.stringify` / `json.dumps(ensure_ascii=False)`).
244fn json_string(s: &str) -> String {
245    let mut out = String::with_capacity(s.len() + 2);
246    out.push('"');
247    for c in s.chars() {
248        match c {
249            '"' => out.push_str("\\\""),
250            '\\' => out.push_str("\\\\"),
251            '\n' => out.push_str("\\n"),
252            '\r' => out.push_str("\\r"),
253            '\t' => out.push_str("\\t"),
254            '\u{08}' => out.push_str("\\b"),
255            '\u{0c}' => out.push_str("\\f"),
256            c if (c as u32) < 0x20 => out.push_str(&format!("\\u{:04x}", c as u32)),
257            c => out.push(c),
258        }
259    }
260    out.push('"');
261    out
262}
behavior_contracts/canonical.rs

behavior_contracts/
canonical.rs
