hara_native/vm/
schema_catalog.rs

1//! Admission of exact std.typed catalogs before HBC1 programs become usable.
2//!
3//! HBC1 carries exact schema coordinates but no mutable lookup policy. This
4//! module validates a complete catalog manifest, including dependency closure
5//! and #901 strongly connected component evidence, before returning a linked
6//! program to an embedding caller.
7
8use sha2::{Digest, Sha256};
9use std::collections::{BTreeMap, BTreeSet};
10use std::fmt::Write as _;
11
12use crate::hbc_schema_links::{decode_linked_program, LinkedProgram, SchemaCoordinate};
13
14const COMPONENT_EPOCH: &str = ":std.typed.catalog/component-v2";
15const HASH_PREFIX: &str = "sha256:";
16const DIGEST_HEX_LENGTH: usize = 64;
17
18/// One exact admitted catalog entry and its exact direct dependencies.
19#[derive(Debug, Clone, PartialEq, Eq)]
20pub struct CatalogEntry {
21    pub coordinate: SchemaCoordinate,
22    pub dependencies: Vec<SchemaCoordinate>,
23}
24
25impl CatalogEntry {
26    pub fn new(
27        coordinate: SchemaCoordinate,
28        dependencies: Vec<SchemaCoordinate>,
29    ) -> Result<Self, String> {
30        validate_coordinate(&coordinate)?;
31        Ok(Self {
32            coordinate,
33            dependencies: canonical_coordinates(&dependencies, "catalog entry dependencies")?,
34        })
35    }
36}
37
38/// One deterministic strongly connected component from `std.typed.catalog`.
39#[derive(Debug, Clone, PartialEq, Eq)]
40pub struct CatalogComponent {
41    pub id: String,
42    pub members: Vec<SchemaCoordinate>,
43    pub dependencies: Vec<String>,
44}
45
46impl CatalogComponent {
47    pub fn new(
48        id: impl Into<String>,
49        members: Vec<SchemaCoordinate>,
50        dependencies: Vec<String>,
51    ) -> Result<Self, String> {
52        let id = id.into();
53        validate_hash(&id, "schema catalog component id")?;
54        let members = canonical_coordinates(&members, "schema catalog component members")?;
55        if members.is_empty() {
56            return Err("schema catalog component requires at least one member".into());
57        }
58        Ok(Self {
59            id,
60            members,
61            dependencies: canonical_component_dependencies(&dependencies)?,
62        })
63    }
64}
65
66/// A catalog whose exact identities, edges, components, and component order
67/// have been validated atomically.
68#[derive(Debug, Clone)]
69pub struct AdmittedCatalog {
70    entries: BTreeMap<SchemaCoordinate, CatalogEntry>,
71    components: BTreeMap<String, CatalogComponent>,
72    owners: BTreeMap<SchemaCoordinate, String>,
73    component_order: Vec<String>,
74}
75
76impl AdmittedCatalog {
77    pub fn entry(&self, coordinate: &SchemaCoordinate) -> Option<&CatalogEntry> {
78        self.entries.get(coordinate)
79    }
80
81    pub fn component_for(&self, coordinate: &SchemaCoordinate) -> Option<&CatalogComponent> {
82        self.owners
83            .get(coordinate)
84            .and_then(|id| self.components.get(id))
85    }
86
87    pub fn component_order(&self) -> &[String] {
88        &self.component_order
89    }
90
91    pub fn entries(&self) -> impl Iterator<Item = &CatalogEntry> {
92        self.entries.values()
93    }
94}
95
96/// A linked program released only after every exact link and transitive
97/// dependency has been admitted.
98#[derive(Debug, Clone)]
99pub struct AdmittedLinkedProgram {
100    pub linked: LinkedProgram,
101    pub resolved_coordinates: Vec<SchemaCoordinate>,
102}
103
104/// Reproduces the portable #901 component identity exactly:
105/// `sha256(pr-str [:std.typed.catalog/component-v2 members])`.
106pub fn component_id(members: &[SchemaCoordinate]) -> Result<String, String> {
107    let members = canonical_coordinates(members, "schema catalog component members")?;
108    if members.is_empty() {
109        return Err("schema catalog component requires at least one member".into());
110    }
111    let mut input = format!("[{COMPONENT_EPOCH} [");
112    for (index, coordinate) in members.iter().enumerate() {
113        if index > 0 {
114            input.push(' ');
115        }
116        write!(
117            &mut input,
118            "[:schema :{} \"{}\"]",
119            coordinate.id, coordinate.hash
120        )
121        .expect("writing to String cannot fail");
122    }
123    input.push_str("]]");
124    let digest = Sha256::digest(input.as_bytes());
125    let mut output = String::from(HASH_PREFIX);
126    for byte in digest {
127        write!(&mut output, "{byte:02x}").expect("writing to String cannot fail");
128    }
129    Ok(output)
130}
131
132/// Validates a complete catalog manifest without partially admitting entries.
133pub fn admit_catalog(
134    entries: &[CatalogEntry],
135    components: &[CatalogComponent],
136) -> Result<AdmittedCatalog, String> {
137    let mut entry_index = BTreeMap::new();
138        let mut identities = BTreeMap::<String, String>::new();
139    for raw_entry in entries {
140        let entry =
141            CatalogEntry::new(raw_entry.coordinate.clone(), raw_entry.dependencies.clone())?;
142        let identity = entry.coordinate.id.clone();
143        if let Some(existing) = identities.insert(identity, entry.coordinate.hash.clone()) {
144            if existing == entry.coordinate.hash {
145                return Err("schema catalog contains duplicate exact entry".into());
146            }
147            return Err("schema catalog contains conflicting immutable identity".into());
148        }
149        if entry_index
150            .insert(entry.coordinate.clone(), entry)
151            .is_some()
152        {
153            return Err("schema catalog contains duplicate exact entry".into());
154        }
155    }
156
157    for entry in entry_index.values() {
158        for dependency in &entry.dependencies {
159            if !entry_index.contains_key(dependency) {
160                return Err(format!(
161                    "schema catalog dependency is not admitted: {}",
162                    display_coordinate(dependency)
163                ));
164            }
165        }
166    }
167
168    let graph = entry_graph(&entry_index);
169    let computed_components = strongly_connected_components(&graph);
170
171    let mut component_index = BTreeMap::new();
172    let mut owners = BTreeMap::new();
173    let mut declared_components = Vec::new();
174    for raw_component in components {
175        let component = CatalogComponent::new(
176            raw_component.id.clone(),
177            raw_component.members.clone(),
178            raw_component.dependencies.clone(),
179        )?;
180        let expected_id = component_id(&component.members)?;
181        if component.id != expected_id {
182            return Err(format!(
183                "schema catalog component id mismatch: expected {expected_id}"
184            ));
185        }
186        if component_index
187            .insert(component.id.clone(), component.clone())
188            .is_some()
189        {
190            return Err("schema catalog contains duplicate component id".into());
191        }
192        for member in &component.members {
193            if !entry_index.contains_key(member) {
194                return Err(format!(
195                    "schema catalog component member is not admitted: {}",
196                    display_coordinate(member)
197                ));
198            }
199            if owners
200                .insert(member.clone(), component.id.clone())
201                .is_some()
202            {
203                return Err(format!(
204                    "schema catalog entry belongs to multiple components: {}",
205                    display_coordinate(member)
206                ));
207            }
208        }
209        declared_components.push(component.members.clone());
210    }
211
212    if owners.len() != entry_index.len() {
213        let missing = entry_index
214            .keys()
215            .find(|coordinate| !owners.contains_key(*coordinate))
216            .expect("owner count differs only when one entry is missing");
217        return Err(format!(
218            "schema catalog entry has no component evidence: {}",
219            display_coordinate(missing)
220        ));
221    }
222
223    declared_components.sort();
224    if declared_components != computed_components {
225        return Err("schema catalog component evidence does not match dependency graph".into());
226    }
227
228    for component in component_index.values() {
229        let expected = expected_component_dependencies(component, &entry_index, &owners);
230        if component.dependencies != expected {
231            return Err(format!(
232                "schema catalog component dependencies mismatch for {}",
233                component.id
234            ));
235        }
236    }
237
238    let component_graph: BTreeMap<String, BTreeSet<String>> = component_index
239        .iter()
240        .map(|(id, component)| (id.clone(), component.dependencies.iter().cloned().collect()))
241        .collect();
242    let component_order = dependency_first_order(component_graph)?;
243
244    Ok(AdmittedCatalog {
245        entries: entry_index,
246        components: component_index,
247        owners,
248        component_order,
249    })
250}
251
252/// Decodes HBC1 and releases it only when every linked coordinate and its
253/// dependency closure exists in the admitted catalog.
254pub fn admit_linked_program(
255    artifact: &[u8],
256    catalog: &AdmittedCatalog,
257) -> Result<AdmittedLinkedProgram, String> {
258    let linked = decode_linked_program(artifact)?;
259    let mut reachable = BTreeSet::new();
260    let mut pending = linked.schema_links.clone();
261    while let Some(coordinate) = pending.pop() {
262        let Some(entry) = catalog.entry(&coordinate) else {
263            return Err(format!(
264                "linked bytecode schema coordinate is not admitted: {}",
265                display_coordinate(&coordinate)
266            ));
267        };
268        if reachable.insert(coordinate) {
269            pending.extend(entry.dependencies.iter().cloned());
270        }
271    }
272
273    let mut resolved_coordinates = Vec::new();
274    for component_id in &catalog.component_order {
275        let component = catalog
276            .components
277            .get(component_id)
278            .expect("admitted component order references an existing component");
279        for member in &component.members {
280            if reachable.contains(member) {
281                resolved_coordinates.push(member.clone());
282            }
283        }
284    }
285
286    Ok(AdmittedLinkedProgram {
287        linked,
288        resolved_coordinates,
289    })
290}
291
292fn validate_coordinate(coordinate: &SchemaCoordinate) -> Result<(), String> {
293    SchemaCoordinate::new(coordinate.id.clone(), coordinate.hash.clone())
294    .map(|_| ())
295}
296
297fn validate_hash(value: &str, label: &str) -> Result<(), String> {
298    let Some(digest) = value.strip_prefix(HASH_PREFIX) else {
299        return Err(format!("{label} must use sha256"));
300    };
301    if digest.len() == DIGEST_HEX_LENGTH
302        && digest
303            .bytes()
304            .all(|value| value.is_ascii_digit() || (b'a'..=b'f').contains(&value))
305    {
306        Ok(())
307    } else {
308        Err(format!("{label} must be canonical lowercase hex"))
309    }
310}
311
312fn canonical_coordinates(
313    values: &[SchemaCoordinate],
314    label: &str,
315) -> Result<Vec<SchemaCoordinate>, String> {
316    let mut output = values.to_vec();
317    output.sort();
318    let mut identities = BTreeMap::<String, String>::new();
319    for coordinate in &output {
320        validate_coordinate(coordinate)?;
321        let identity = coordinate.id.clone();
322        if let Some(existing) = identities.insert(identity, coordinate.hash.clone()) {
323            if existing == coordinate.hash {
324                return Err(format!("{label} contain a duplicate coordinate"));
325            }
326            return Err(format!("{label} contain conflicting immutable identities"));
327        }
328    }
329    Ok(output)
330}
331
332fn canonical_component_dependencies(values: &[String]) -> Result<Vec<String>, String> {
333    let mut output = values.to_vec();
334    output.sort();
335    for value in &output {
336        validate_hash(value, "schema catalog component dependency")?;
337    }
338    if output.windows(2).any(|pair| pair[0] == pair[1]) {
339        return Err("schema catalog component dependencies contain a duplicate".into());
340    }
341    Ok(output)
342}
343
344fn entry_graph(
345    entries: &BTreeMap<SchemaCoordinate, CatalogEntry>,
346) -> BTreeMap<SchemaCoordinate, BTreeSet<SchemaCoordinate>> {
347    entries
348        .iter()
349        .map(|(coordinate, entry)| {
350            (
351                coordinate.clone(),
352                entry.dependencies.iter().cloned().collect(),
353            )
354        })
355        .collect()
356}
357
358fn strongly_connected_components(
359    graph: &BTreeMap<SchemaCoordinate, BTreeSet<SchemaCoordinate>>,
360) -> Vec<Vec<SchemaCoordinate>> {
361    fn visit_order(
362        node: &SchemaCoordinate,
363        graph: &BTreeMap<SchemaCoordinate, BTreeSet<SchemaCoordinate>>,
364        seen: &mut BTreeSet<SchemaCoordinate>,
365        order: &mut Vec<SchemaCoordinate>,
366    ) {
367        if !seen.insert(node.clone()) {
368            return;
369        }
370        for dependency in graph.get(node).into_iter().flatten() {
371            visit_order(dependency, graph, seen, order);
372        }
373        order.push(node.clone());
374    }
375
376    fn visit_component(
377        node: &SchemaCoordinate,
378        reverse: &BTreeMap<SchemaCoordinate, BTreeSet<SchemaCoordinate>>,
379        seen: &mut BTreeSet<SchemaCoordinate>,
380        members: &mut Vec<SchemaCoordinate>,
381    ) {
382        if !seen.insert(node.clone()) {
383            return;
384        }
385        members.push(node.clone());
386        for dependency in reverse.get(node).into_iter().flatten() {
387            visit_component(dependency, reverse, seen, members);
388        }
389    }
390
391    let mut reverse = graph
392        .keys()
393        .cloned()
394        .map(|coordinate| (coordinate, BTreeSet::new()))
395        .collect::<BTreeMap<_, _>>();
396    for (coordinate, dependencies) in graph {
397        for dependency in dependencies {
398            reverse
399                .get_mut(dependency)
400                .expect("validated dependency exists in graph")
401                .insert(coordinate.clone());
402        }
403    }
404
405    let mut seen = BTreeSet::new();
406    let mut order = Vec::new();
407    for coordinate in graph.keys() {
408        visit_order(coordinate, graph, &mut seen, &mut order);
409    }
410
411    seen.clear();
412    let mut output = Vec::new();
413    while let Some(coordinate) = order.pop() {
414        if seen.contains(&coordinate) {
415            continue;
416        }
417        let mut members = Vec::new();
418        visit_component(&coordinate, &reverse, &mut seen, &mut members);
419        members.sort();
420        output.push(members);
421    }
422    output.sort();
423    output
424}
425
426fn expected_component_dependencies(
427    component: &CatalogComponent,
428    entries: &BTreeMap<SchemaCoordinate, CatalogEntry>,
429    owners: &BTreeMap<SchemaCoordinate, String>,
430) -> Vec<String> {
431    let mut output = BTreeSet::new();
432    for member in &component.members {
433        for dependency in &entries
434            .get(member)
435            .expect("component member is an admitted entry")
436            .dependencies
437        {
438            let owner = owners
439                .get(dependency)
440                .expect("admitted dependency has component evidence");
441            if owner != &component.id {
442                output.insert(owner.clone());
443            }
444        }
445    }
446    output.into_iter().collect()
447}
448
449fn dependency_first_order(
450    mut graph: BTreeMap<String, BTreeSet<String>>,
451) -> Result<Vec<String>, String> {
452    let mut output = Vec::new();
453    while !graph.is_empty() {
454        let ready = graph
455            .iter()
456            .filter_map(|(component, dependencies)| {
457                dependencies.is_empty().then_some(component.clone())
458            })
459            .collect::<Vec<_>>();
460        if ready.is_empty() {
461            return Err("schema catalog component graph contains a cycle".into());
462        }
463        let ready_set = ready.iter().cloned().collect::<BTreeSet<_>>();
464        for component in &ready {
465            graph.remove(component);
466        }
467        for dependencies in graph.values_mut() {
468            dependencies.retain(|dependency| !ready_set.contains(dependency));
469        }
470        output.extend(ready);
471    }
472    Ok(output)
473}
474
475fn display_coordinate(coordinate: &SchemaCoordinate) -> String {
476    format!("[:schema :{} \"{}\"]", coordinate.id, coordinate.hash)
477}
478
479#[cfg(test)]
480mod tests {
481    use super::*;
482    use crate::hbc_schema_links::encode_linked_program;
483    use crate::vm::compile_source;
484
485    fn coordinate(id: &str, digit: char) -> SchemaCoordinate {
486        SchemaCoordinate::new(
487            id,
488            format!("sha256:{}", digit.to_string().repeat(64)),
489        )
490        .unwrap()
491    }
492
493    fn component(members: Vec<SchemaCoordinate>, dependencies: Vec<String>) -> CatalogComponent {
494        CatalogComponent::new(component_id(&members).unwrap(), members, dependencies).unwrap()
495    }
496
497    #[test]
498    fn component_identity_matches_the_portable_catalog_epoch() {
499        let identifier = coordinate("model/id", '1');
500        assert_eq!(
501            component_id(&[identifier]).unwrap(),
502            "sha256:eb2433d563d47c84b3469d37f8786ee00ae0f7080b2505fc839d851615171c32"
503        );
504    }
505
506    #[test]
507    fn linked_program_is_released_with_dependency_first_exact_closure() {
508        let identifier = coordinate("model/id", '1');
509        let profile = coordinate("model/profile", '2');
510        let identifier_component = component(vec![identifier.clone()], vec![]);
511        let profile_component =
512            component(vec![profile.clone()], vec![identifier_component.id.clone()]);
513        let catalog = admit_catalog(
514            &[
515                CatalogEntry::new(identifier.clone(), vec![]).unwrap(),
516                CatalogEntry::new(profile.clone(), vec![identifier.clone()]).unwrap(),
517            ],
518            &[profile_component, identifier_component],
519        )
520        .unwrap();
521
522        let program = compile_source("(+ 19 23)").unwrap();
523        let artifact = encode_linked_program(&program, &[profile.clone()]).unwrap();
524        let admitted = admit_linked_program(&artifact, &catalog).unwrap();
525        assert_eq!(admitted.linked.schema_links, vec![profile.clone()]);
526        assert_eq!(admitted.resolved_coordinates, vec![identifier, profile]);
527    }
528
529    #[test]
530    fn stale_or_missing_exact_links_fail_before_program_release() {
531        let identifier = coordinate("model/id", '1');
532        let catalog = admit_catalog(
533            &[CatalogEntry::new(identifier.clone(), vec![]).unwrap()],
534            &[component(vec![identifier], vec![])],
535        )
536        .unwrap();
537        let stale = coordinate("model/id", '2');
538        let program = compile_source("42").unwrap();
539        let artifact = encode_linked_program(&program, &[stale]).unwrap();
540        assert!(admit_linked_program(&artifact, &catalog)
541            .unwrap_err()
542            .contains("is not admitted"));
543    }
544
545    #[test]
546    fn forged_component_evidence_is_rejected_atomically() {
547        let identifier = coordinate("model/id", '1');
548        let profile = coordinate("model/profile", '2');
549        let forged = component(vec![identifier.clone(), profile.clone()], vec![]);
550        assert_eq!(
551            admit_catalog(
552                &[
553                    CatalogEntry::new(identifier.clone(), vec![]).unwrap(),
554                    CatalogEntry::new(profile, vec![identifier]).unwrap(),
555                ],
556                &[forged],
557            )
558            .unwrap_err(),
559            "schema catalog component evidence does not match dependency graph"
560        );
561    }
562
563    #[test]
564    fn valid_self_recursion_remains_one_admitted_component() {
565        let node = coordinate("tree/node", '3');
566        let catalog = admit_catalog(
567            &[CatalogEntry::new(node.clone(), vec![node.clone()]).unwrap()],
568            &[component(vec![node.clone()], vec![])],
569        )
570        .unwrap();
571        assert_eq!(catalog.component_order().len(), 1);
572        assert_eq!(catalog.entries().count(), 1);
573        assert_eq!(catalog.component_for(&node).unwrap().members, vec![node]);
574    }
575}
hara_native/vm/schema_catalog.rs

hara_native/vm/
schema_catalog.rs
