Skip to main content

clm_rust_core/layer0/
spec_identity.rs

1//! Layer 0: Identity and keys for quoted specifications (profile `clm.spec.v1`)
2//! Canonical Path: kernel/clm_rust_core/src/layer0/spec_identity.rs
3//!
4//! A specification is data before it is a computation. This module encodes a
5//! restricted JSON payload to canonical bytes, derives an identity from those
6//! bytes, and derives two keys for a quoted recipe. Every function here is pure.
7//! None of them evaluates an operand, resolves a handle or reads a store.
8//!
9//! The payload profile is deliberately narrow so that three runtimes agree on
10//! the bytes. It allows objects with ASCII keys, arrays, strings, booleans, null
11//! and integers inside the IEEE-754 safe range. It refuses floats and duplicate
12//! keys. A decimal travels as a string. The profile does not claim RFC 8785.
13
14use std::collections::{BTreeMap, BTreeSet};
15
16use serde_json::{json, Map, Number, Value};
17
18use crate::layer0::hash::compute_blake3;
19use crate::layer0::spec_profile::{descend, is_safe_integer, Refusable};
20
21pub use crate::layer0::spec_profile::{
22    SpecProfileError, SPEC_DOMAIN_TAG, SPEC_HASH_QUALIFIER, MAX_SAFE_INTEGER, MIN_SAFE_INTEGER, MAX_NESTING_DEPTH,
23    MAX_RECIPE_DEPTH, REFUSED_FLOAT, REFUSED_DUPLICATE_KEY, REFUSED_NON_ASCII_KEY, REFUSED_INTEGER_RANGE,
24    REFUSED_UNSUPPORTED_TYPE, REFUSED_INVALID_STRING, REFUSED_MALFORMED, REFUSED_ACTION_OPERAND,
25    REFUSED_UNRESOLVED_INPUT, REFUSED_UNKNOWN_COMPONENT, OPERAND_REFERENCE, OPERAND_DEFERRED, OPERAND_ACTION,
26    KIND_RECIPE, KIND_DEEP_KEY, KIND_SHALLOW_KEY,
27};
28pub use crate::layer0::spec_scan::decode_payload;
29use crate::layer0::spec_scan::FIRST_UNESCAPED_BYTE;
30
31/// An operand that names stored content by its hash.
32#[derive(Debug, Clone, PartialEq, Eq)]
33pub struct Reference {
34    pub reference: String,
35}
36
37/// An operand that is immediate and effectful. A recipe that holds one has no key.
38#[derive(Debug, Clone, PartialEq, Eq)]
39pub struct Action {
40    pub name: String,
41}
42
43/// A quoted unit: a function reference, ordered operands and named operands.
44///
45/// `rule_refs` lists the hashes of the rules that shaped the unit, in the order
46/// they were applied. `decoder_policy` names how the unit's output is read back.
47#[derive(Debug, Clone, Default, PartialEq, Eq)]
48pub struct Recipe {
49    pub function_ref: String,
50    pub args: Vec<Operand>,
51    pub kwargs: Vec<(String, Operand)>,
52    pub rule_refs: Vec<String>,
53    pub decoder_policy: String,
54}
55
56/// One input of a recipe. Each operand has exactly one class.
57#[derive(Debug, Clone, PartialEq, Eq)]
58pub enum Operand {
59    Reference(Reference),
60    Deferred(Recipe),
61    Action(Action),
62}
63
64fn validate_number(number: &Number, path: &str) -> Refusable<()> {
65    match number.as_i64() {
66        Some(integer) if is_safe_integer(integer) => Ok(()),
67        Some(_) => Err(SpecProfileError::new(REFUSED_INTEGER_RANGE, format!("{path} holds {number}"))),
68        None if number.is_u64() => Err(SpecProfileError::new(REFUSED_INTEGER_RANGE, format!("{path} holds {number}"))),
69        None => Err(SpecProfileError::new(REFUSED_FLOAT, format!("{path} holds a float; write a decimal as a string"))),
70    }
71}
72
73/// Refuses any value outside the payload profile, in the order the value lists its members.
74fn validate(value: &Value, path: &mut String, depth: usize) -> Refusable<()> {
75    match value {
76        Value::Null | Value::Bool(_) | Value::String(_) => Ok(()),
77        Value::Number(number) => validate_number(number, path),
78        Value::Array(items) => {
79            let depth = descend(depth, MAX_NESTING_DEPTH, path)?;
80            let mark = path.len();
81            for (index, item) in items.iter().enumerate() {
82                path.push_str(&format!("[{index}]"));
83                validate(item, path, depth)?;
84                path.truncate(mark);
85            }
86            Ok(())
87        }
88        Value::Object(members) => {
89            let depth = descend(depth, MAX_NESTING_DEPTH, path)?;
90            let mark = path.len();
91            for (key, item) in members {
92                if !key.is_ascii() {
93                    return Err(SpecProfileError::new(REFUSED_NON_ASCII_KEY, format!("{path} has the key {key:?}")));
94                }
95                path.push('.');
96                path.push_str(key);
97                validate(item, path, depth)?;
98                path.truncate(mark);
99            }
100            Ok(())
101        }
102    }
103}
104
105fn write_string(text: &str, out: &mut Vec<u8>) {
106    out.push(b'"');
107    for &byte in text.as_bytes() {
108        match byte {
109            b'"' => out.extend_from_slice(br#"\""#),
110            b'\\' => out.extend_from_slice(br"\\"),
111            0x08 => out.extend_from_slice(br"\b"),
112            0x0C => out.extend_from_slice(br"\f"),
113            b'\n' => out.extend_from_slice(br"\n"),
114            b'\r' => out.extend_from_slice(br"\r"),
115            b'\t' => out.extend_from_slice(br"\t"),
116            control if control < FIRST_UNESCAPED_BYTE => out.extend_from_slice(format!("\\u{control:04x}").as_bytes()),
117            plain => out.push(plain),
118        }
119    }
120    out.push(b'"');
121}
122
123/// Writes a validated value. Keys are ASCII, so byte order is the sort order.
124fn write_canonical(value: &Value, out: &mut Vec<u8>) {
125    match value {
126        Value::Null => out.extend_from_slice(b"null"),
127        Value::Bool(true) => out.extend_from_slice(b"true"),
128        Value::Bool(false) => out.extend_from_slice(b"false"),
129        Value::Number(number) => out.extend_from_slice(number.to_string().as_bytes()),
130        Value::String(text) => write_string(text, out),
131        Value::Array(items) => {
132            out.push(b'[');
133            for (index, item) in items.iter().enumerate() {
134                if index > 0 {
135                    out.push(b',');
136                }
137                write_canonical(item, out);
138            }
139            out.push(b']');
140        }
141        Value::Object(members) => {
142            let mut sorted: Vec<(&String, &Value)> = members.iter().collect();
143            sorted.sort_by(|left, right| left.0.as_bytes().cmp(right.0.as_bytes()));
144            out.push(b'{');
145            for (index, (key, item)) in sorted.into_iter().enumerate() {
146                if index > 0 {
147                    out.push(b',');
148                }
149                write_string(key, out);
150                out.push(b':');
151                write_canonical(item, out);
152            }
153            out.push(b'}');
154        }
155    }
156}
157
158/// Canonical bytes of a payload: sorted keys, no whitespace, UTF-8, minimal escapes.
159pub fn encode_payload(payload: &Value) -> Refusable<Vec<u8>> {
160    validate(payload, &mut String::from("$"), 0)?;
161    let mut out = Vec::new();
162    write_canonical(payload, &mut out);
163    Ok(out)
164}
165
166/// `blake3:<hex>` over the domain tag, a newline and the canonical bytes.
167pub fn spec_identity(payload: &Value) -> Refusable<String> {
168    let preimage = [SPEC_DOMAIN_TAG.as_bytes(), b"\n", &encode_payload(payload)?].concat();
169    Ok(format!("{SPEC_HASH_QUALIFIER}:{}", compute_blake3(&preimage)))
170}
171
172/// The one class of an operand.
173pub fn operand_class(operand: &Operand) -> &'static str {
174    match operand {
175        Operand::Reference(_) => OPERAND_REFERENCE,
176        Operand::Deferred(_) => OPERAND_DEFERRED,
177        Operand::Action(_) => OPERAND_ACTION,
178    }
179}
180
181fn operand_payload(operand: &Operand, depth: usize) -> Refusable<Value> {
182    let (name, value) = match operand {
183        Operand::Reference(reference) => ("ref", Value::String(reference.reference.clone())),
184        Operand::Deferred(recipe) => ("recipe", recipe_payload_at(recipe, depth)?),
185        Operand::Action(action) => ("name", Value::String(action.name.clone())),
186    };
187    let mut members = Map::new();
188    members.insert("class".to_string(), Value::String(operand_class(operand).to_string()));
189    members.insert(name.to_string(), value);
190    Ok(Value::Object(members))
191}
192
193/// The named operands in the order given. Refuses a name that appears twice.
194fn named(kwargs: &[(String, Operand)]) -> Refusable<&[(String, Operand)]> {
195    let mut seen = BTreeSet::new();
196    for (name, _) in kwargs {
197        if !seen.insert(name.as_str()) {
198            let detail = format!("the named operand {name:?} appears twice");
199            return Err(SpecProfileError::new(REFUSED_DUPLICATE_KEY, detail));
200        }
201    }
202    Ok(kwargs)
203}
204
205/// The recursive walks below use plain loops and keep `json!` in leaf functions,
206/// so one level of nesting costs a small and steady amount of call stack.
207fn recipe_payload_at(recipe: &Recipe, depth: usize) -> Refusable<Value> {
208    let depth = descend(depth, MAX_RECIPE_DEPTH, "the recipe")?;
209    let mut args = Vec::with_capacity(recipe.args.len());
210    for operand in &recipe.args {
211        args.push(operand_payload(operand, depth)?);
212    }
213    let mut kwargs = Map::new();
214    for (name, operand) in named(&recipe.kwargs)? {
215        kwargs.insert(name.clone(), operand_payload(operand, depth)?);
216    }
217    Ok(unit_payload(recipe, args, kwargs))
218}
219
220#[inline(never)]
221fn unit_payload(recipe: &Recipe, args: Vec<Value>, kwargs: Map<String, Value>) -> Value {
222    json!({
223        "args": args,
224        "decoder": recipe.decoder_policy,
225        "function": recipe.function_ref,
226        "kwargs": kwargs,
227        "rules": recipe.rule_refs,
228    })
229}
230
231/// The quoted form of a recipe, as a payload inside the profile.
232pub fn recipe_payload(recipe: &Recipe) -> Refusable<Value> {
233    recipe_payload_at(recipe, 0)
234}
235
236fn incomplete(what: &str) -> SpecProfileError {
237    SpecProfileError::new(REFUSED_MALFORMED, format!("the recipe payload is incomplete: {what}"))
238}
239
240fn member<'a>(members: &'a Map<String, Value>, name: &str) -> Refusable<&'a Value> {
241    members.get(name).ok_or_else(|| incomplete(&format!("no member {name:?}")))
242}
243
244fn text_member(members: &Map<String, Value>, name: &str) -> Refusable<String> {
245    let text = member(members, name)?.as_str().ok_or_else(|| incomplete(&format!("{name:?} is not a string")))?;
246    Ok(text.to_string())
247}
248
249fn list_member<'a>(members: &'a Map<String, Value>, name: &str) -> Refusable<&'a Vec<Value>> {
250    member(members, name)?.as_array().ok_or_else(|| incomplete(&format!("{name:?} is not a list")))
251}
252
253fn operand_from_payload(payload: &Value, depth: usize) -> Refusable<Operand> {
254    let members = payload.as_object().ok_or_else(|| incomplete("an operand is not an object"))?;
255    match members.get("class").and_then(Value::as_str) {
256        Some(OPERAND_REFERENCE) => Ok(Operand::Reference(Reference { reference: text_member(members, "ref")? })),
257        Some(OPERAND_DEFERRED) => Ok(Operand::Deferred(recipe_from_payload_at(member(members, "recipe")?, depth)?)),
258        Some(OPERAND_ACTION) => Ok(Operand::Action(Action { name: text_member(members, "name")? })),
259        _ => {
260            let kind = members.get("class").map_or_else(|| "null".to_string(), Value::to_string);
261            Err(SpecProfileError::new(REFUSED_UNSUPPORTED_TYPE, format!("unknown operand class {kind}")))
262        }
263    }
264}
265
266fn recipe_from_payload_at(payload: &Value, depth: usize) -> Refusable<Recipe> {
267    let depth = descend(depth, MAX_RECIPE_DEPTH, "the recipe payload")?;
268    let members = payload.as_object().ok_or_else(|| incomplete("a recipe is not an object"))?;
269    let function_ref = text_member(members, "function")?;
270    let mut args = Vec::new();
271    for item in list_member(members, "args")? {
272        args.push(operand_from_payload(item, depth)?);
273    }
274    let quoted = member(members, "kwargs")?.as_object().ok_or_else(|| incomplete("\"kwargs\" is not an object"))?;
275    let mut sorted: Vec<(&String, &Value)> = quoted.iter().collect();
276    sorted.sort_by(|left, right| left.0.cmp(right.0));
277    let mut kwargs = Vec::with_capacity(sorted.len());
278    for (name, item) in sorted {
279        kwargs.push((name.clone(), operand_from_payload(item, depth)?));
280    }
281    let mut rule_refs = Vec::new();
282    for rule in list_member(members, "rules")? {
283        rule_refs.push(rule.as_str().ok_or_else(|| incomplete("a rule is not a string"))?.to_string());
284    }
285    let decoder_policy = text_member(members, "decoder")?;
286    Ok(Recipe { function_ref, args, kwargs, rule_refs, decoder_policy })
287}
288
289/// Rebuilds a recipe from its quoted form. The inverse of `recipe_payload`.
290pub fn recipe_from_payload(payload: &Value) -> Refusable<Recipe> {
291    recipe_from_payload_at(payload, 0)
292}
293
294/// Identity of the quoted recipe itself. It commits to every operand as written.
295pub fn recipe_identity(recipe: &Recipe) -> Refusable<String> {
296    spec_identity(&json!({ "kind": KIND_RECIPE, "recipe": recipe_payload(recipe)? }))
297}
298
299fn operands(recipe: &Recipe) -> impl Iterator<Item = &Operand> {
300    recipe.args.iter().chain(recipe.kwargs.iter().map(|(_, operand)| operand))
301}
302
303/// False when the recipe, or any recipe it defers to, holds an action operand.
304pub fn is_keyable(recipe: &Recipe) -> bool {
305    let mut pending = vec![recipe];
306    while let Some(unit) = pending.pop() {
307        for operand in operands(unit) {
308            match operand {
309                Operand::Reference(_) => {}
310                Operand::Deferred(inner) => pending.push(inner),
311                Operand::Action(_) => return false,
312            }
313        }
314    }
315    true
316}
317
318fn action_has_no_key(action: &Action) -> SpecProfileError {
319    SpecProfileError::new(REFUSED_ACTION_OPERAND, format!("the action {:?} has no key", action.name))
320}
321
322/// One key over the header of a recipe and one input string for each operand.
323fn key_over(kind: &str, recipe: &Recipe, input: impl Fn(&Operand) -> Refusable<String>) -> Refusable<String> {
324    let mut args = Vec::with_capacity(recipe.args.len());
325    for operand in &recipe.args {
326        args.push(input(operand)?);
327    }
328    let mut kwargs = Map::new();
329    for (name, operand) in named(&recipe.kwargs)? {
330        kwargs.insert(name.clone(), Value::String(input(operand)?));
331    }
332    key_identity(kind, recipe, args, kwargs)
333}
334
335#[inline(never)]
336fn key_identity(kind: &str, recipe: &Recipe, args: Vec<String>, kwargs: Map<String, Value>) -> Refusable<String> {
337    let header =
338        json!({ "decoder": recipe.decoder_policy, "function": recipe.function_ref, "rules": recipe.rule_refs });
339    spec_identity(&json!({ "kind": kind, "header": header, "inputs": { "args": args, "kwargs": kwargs } }))
340}
341
342fn deep_key_at(recipe: &Recipe, depth: usize) -> Refusable<String> {
343    let depth = descend(depth, MAX_RECIPE_DEPTH, "the recipe")?;
344    key_over(KIND_DEEP_KEY, recipe, |operand| match operand {
345        Operand::Reference(reference) => Ok(reference.reference.clone()),
346        Operand::Deferred(inner) => deep_key_at(inner, depth),
347        Operand::Action(action) => Err(action_has_no_key(action)),
348    })
349}
350
351/// Key over the function, the rules, the decoder policy and the deep keys of the inputs.
352///
353/// It is computable from the quoted recipe alone, so a lookup under it reads no
354/// upstream content. It gives no early cutoff: any upstream change changes it.
355pub fn deep_key(recipe: &Recipe) -> Refusable<String> {
356    deep_key_at(recipe, 0)
357}
358
359/// Key over the same header and the content references of the direct inputs.
360///
361/// `content_refs` maps the deep key of each direct deferred input to the content
362/// reference of its result. The caller supplies it, and this function evaluates
363/// nothing. Two upstream changes that yield identical bytes give one shallow key.
364pub fn shallow_key(recipe: &Recipe, content_refs: &BTreeMap<String, String>) -> Refusable<String> {
365    key_over(KIND_SHALLOW_KEY, recipe, |operand| match operand {
366        Operand::Reference(reference) => Ok(reference.reference.clone()),
367        Operand::Deferred(inner) => {
368            let upstream = deep_key_at(inner, 1)?;
369            content_refs.get(&upstream).cloned().ok_or_else(|| {
370                let detail = format!("no content reference is known for the input {upstream}");
371                SpecProfileError::new(REFUSED_UNRESOLVED_INPUT, detail)
372            })
373        }
374        Operand::Action(action) => Err(action_has_no_key(action)),
375    })
376}
377
378/// Named operands for the components a unit reads, out of a composite value.
379///
380/// A composite value is a mapping of component names to operands. A unit that
381/// reads two of five components names only those two, so a change to any other
382/// component leaves both of its keys unchanged.
383pub fn select_components<'a>(
384    components: &BTreeMap<String, Operand>,
385    reads: impl IntoIterator<Item = &'a str>,
386) -> Refusable<Vec<(String, Operand)>> {
387    let wanted: BTreeSet<&str> = reads.into_iter().collect();
388    wanted
389        .into_iter()
390        .map(|name| match components.get(name) {
391            Some(operand) => Ok((name.to_string(), operand.clone())),
392            None => {
393                let detail = format!("the composite value has no component {name:?}");
394                Err(SpecProfileError::new(REFUSED_UNKNOWN_COMPONENT, detail))
395            }
396        })
397        .collect()
398}