lex_ast/
lib.rs

1//! M2: canonical AST, node IDs, canonicalizer, canonical-JSON, hashing.
2//!
3//! See spec §5.
4
5pub mod canonical;
6pub mod canonicalize;
7pub mod canon_json;
8pub mod canon_print;
9pub mod canonical_format;
10pub mod dead_branch;
11pub mod ids;
12pub mod patch;
13pub mod transforms;
14
15pub use canonical::*;
16pub use canonicalize::{canonicalize_program, canonicalize_item};
17pub use canon_print::{print_example, print_stages};
18pub use ids::{collect_ids, expr_ids, NodeId, NodeRef};
19pub use patch::{apply_patch, Patch, PatchError};
20pub use transforms::{
21    extract_function, inline_let, rename_local, replace_match_arm,
22    ExtractFnSpec, TransformError,
23};
24
25/// SHA-256 over the canonical-JSON encoding of a stage. Excludes NodeIds
26/// (the canonical AST data does not carry IDs; they're derived).
27pub fn stage_canonical_hash(stage: &Stage) -> [u8; 32] {
28    let v = serde_json::to_value(stage).expect("stage is always serializable");
29    canon_json::hash_canonical(&v)
30}
31
32pub fn stage_canonical_hash_hex(stage: &Stage) -> String {
33    canon_json::hex(&stage_canonical_hash(stage))
34}
35
36/// SigId: §4.1. SHA-256 over canonical_json({name, input_types, output_type, effects}).
37pub fn sig_id(stage: &Stage) -> Option<String> {
38    Some(canon_json::hex(&sig_hash(stage, true)?))
39}
40
41/// Structural-sig hash: like SigId but with the name omitted. Used as
42/// input to StageId so renames don't change implementation identity
43/// (per §4.6's open-question default: name lives in SigId, not StageId).
44fn structural_sig_hash(stage: &Stage) -> Option<[u8; 32]> {
45    sig_hash(stage, false)
46}
47
48fn sig_hash(stage: &Stage, include_name: bool) -> Option<[u8; 32]> {
49    let value = match stage {
50        Stage::FnDecl(fd) => {
51            let mut v = serde_json::Map::new();
52            v.insert("effects".into(), serde_json::to_value(&fd.effects).unwrap());
53            v.insert("input_types".into(), serde_json::to_value(
54                fd.params.iter().map(|p| &p.ty).collect::<Vec<_>>()
55            ).unwrap());
56            v.insert("output_type".into(), serde_json::to_value(&fd.return_type).unwrap());
57            // Signature-level examples (#369) are part of the contract:
58            // two signatures with different example sets hash differently.
59            // Omitted entirely when there are no examples, preserving
60            // pre-#369 SigIds bit-for-bit.
61            if !fd.examples.is_empty() {
62                v.insert("examples".into(), serde_json::to_value(&fd.examples).unwrap());
63            }
64            if include_name { v.insert("name".into(), serde_json::Value::String(fd.name.clone())); }
65            serde_json::Value::Object(v)
66        }
67        Stage::TypeDecl(td) => {
68            let mut v = serde_json::Map::new();
69            v.insert("kind".into(), serde_json::Value::String("type".into()));
70            v.insert("params".into(), serde_json::to_value(&td.params).unwrap());
71            if include_name { v.insert("name".into(), serde_json::Value::String(td.name.clone())); }
72            serde_json::Value::Object(v)
73        }
74        Stage::Import(_) => return None,
75    };
76    Some(canon_json::hash_canonical(&value))
77}
78
79/// StageId: §4.1, with §4.6 default applied.
80///
81/// `StageId = SHA-256(structural_sig_hash || implementation_hash)`.
82///
83/// `structural_sig_hash` is SigId with the name field omitted, and
84/// `implementation_hash` is the canonical AST with the name field blanked.
85/// Together they encode "what the function does and what shape it has";
86/// the name lives in SigId only.
87pub fn stage_id(stage: &Stage) -> Option<String> {
88    let sig = canon_json::hex(&structural_sig_hash(stage)?);
89    let impl_h = canon_json::hex(&implementation_hash(stage));
90    use sha2::{Digest, Sha256};
91    let mut h = Sha256::new();
92    h.update(sig.as_bytes());
93    h.update(impl_h.as_bytes());
94    let r = h.finalize();
95    Some(canon_json::hex(&r))
96}
97
98/// SHA-256 over the canonical AST with the *name* fields blanked out.
99/// Two implementations that differ only in their function/type name
100/// produce the same `implementation_hash` (and therefore the same StageId,
101/// given matching SigIds).
102pub fn implementation_hash(stage: &Stage) -> [u8; 32] {
103    let stripped = strip_names(stage);
104    let v = serde_json::to_value(&stripped).expect("stage is always serializable");
105    canon_json::hash_canonical(&v)
106}
107
108fn strip_names(stage: &Stage) -> Stage {
109    match stage.clone() {
110        Stage::FnDecl(mut fd) => { fd.name = String::new(); Stage::FnDecl(fd) }
111        Stage::TypeDecl(mut td) => { td.name = String::new(); Stage::TypeDecl(td) }
112        s @ Stage::Import(_) => s,
113    }
114}
lex_ast/lib.rs

lex_ast/
lib.rs
