Skip to main content

clm_rust_core/layer2/
sheaf.rs

1//! Sheaf gluing engine scaffold for Stage 4.
2//!
3//! Implements the bare-bones sheaf model from Sprint 139.4 Story 1:
4//! - `Place` is an open-set identifier.
5//! - `Marking` maps token colors to ordered lists of manifest hashes.
6//! - `Section` pairs an open set with a local marking.
7//! - `Sheaf::gluing_check` validates pairwise restriction agreement and either
8//!   produces a global section or returns a `CohomologyError`.
9
10use serde::{Deserialize, Serialize};
11use std::collections::{BTreeSet, HashMap};
12
13#[cfg(feature = "native")]
14pub use crate::cpn::mcard_token::PlaceMCard;
15#[cfg(feature = "native")]
16pub use crate::cpn::token_namespace::MCardMarking;
17
18#[cfg(not(feature = "native"))]
19#[derive(Debug, Clone, Hash, Eq, PartialEq, Ord, PartialOrd, Serialize, Deserialize)]
20pub struct PlaceMCard {
21    pub place_id: String,
22    pub role: String,
23    pub color_type: String,
24}
25
26#[cfg(not(feature = "native"))]
27impl PlaceMCard {
28    pub fn new(id: impl Into<String>) -> Self {
29        Self {
30            place_id: id.into(),
31            role: "Ordinary".into(),
32            color_type: "unit".into(),
33        }
34    }
35}
36
37#[cfg(not(feature = "native"))]
38#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
39pub struct MCardMarking {
40    pub by_place: std::collections::BTreeMap<String, Vec<String>>,
41}
42
43#[cfg(not(feature = "native"))]
44impl MCardMarking {
45    pub fn new() -> Self {
46        Self::default()
47    }
48
49    pub fn restrict(&self, colors: &BTreeSet<String>) -> Self {
50        let mut by_place = std::collections::BTreeMap::new();
51        for (p, toks) in &self.by_place {
52            if colors.contains(p) {
53                by_place.insert(p.clone(), toks.clone());
54            }
55        }
56        Self { by_place }
57    }
58}
59
60
61
62/// Unified canonical Petri Net Marking alias for Sheaf sections (Sprint 551).
63pub type Marking = MCardMarking;
64
65#[derive(Debug, Clone, Hash, Eq, PartialEq, Ord, PartialOrd, Serialize, Deserialize)]
66pub struct Place {
67    pub id: String,
68}
69
70impl Place {
71    pub fn new(id: impl Into<String>) -> Self {
72        Self { id: id.into() }
73    }
74
75    pub fn to_mcard(&self) -> PlaceMCard {
76        PlaceMCard::new(&self.id)
77    }
78
79    pub fn from_mcard(mcard: &PlaceMCard) -> Self {
80        Self { id: mcard.place_id.clone() }
81    }
82}
83
84impl From<PlaceMCard> for Place {
85    fn from(m: PlaceMCard) -> Self {
86        Self { id: m.place_id }
87    }
88}
89
90impl From<&PlaceMCard> for Place {
91    fn from(m: &PlaceMCard) -> Self {
92        Self { id: m.place_id.clone() }
93    }
94}
95
96impl From<Place> for PlaceMCard {
97    fn from(p: Place) -> Self {
98        PlaceMCard::new(p.id)
99    }
100}
101
102impl From<&Place> for PlaceMCard {
103    fn from(p: &Place) -> Self {
104        PlaceMCard::new(&p.id)
105    }
106}
107
108#[derive(Debug, Clone, Default, Eq, PartialEq, Hash, Serialize, Deserialize)]
109pub struct OpenSet {
110    pub places: BTreeSet<Place>,
111}
112
113impl OpenSet {
114    pub fn new() -> Self {
115        Self::default()
116    }
117
118    pub fn from_places<I: IntoIterator<Item = Place>>(places: I) -> Self {
119        Self {
120            places: places.into_iter().collect(),
121        }
122    }
123
124    pub fn intersection(&self, other: &OpenSet) -> OpenSet {
125        OpenSet {
126            places: self
127                .places
128                .intersection(&other.places)
129                .cloned()
130                .collect(),
131        }
132    }
133
134    pub fn is_disjoint(&self, other: &OpenSet) -> bool {
135        self.places.is_disjoint(&other.places)
136    }
137
138    pub fn is_subset(&self, other: &OpenSet) -> bool {
139        self.places.is_subset(&other.places)
140    }
141
142    pub fn is_empty(&self) -> bool {
143        self.places.is_empty()
144    }
145
146    pub fn colors(&self) -> BTreeSet<String> {
147        // In this simple model, each place carries a single color equal to its id.
148        self.places.iter().map(|p| p.id.clone()).collect()
149    }
150}
151
152#[derive(Debug, Clone, Serialize, Deserialize)]
153pub struct Section {
154    pub open_set: OpenSet,
155    pub marking: Marking,
156}
157
158impl Section {
159    pub fn new(open_set: OpenSet, marking: Marking) -> Self {
160        Self { open_set, marking }
161    }
162
163    /// Restrict this section to a smaller open set.
164    pub fn restrict(&self, subset: &OpenSet) -> Result<Section, CohomologyError> {
165        if !subset.is_subset(&self.open_set) {
166            return Err(CohomologyError::InvalidRestriction {
167                subset: subset.clone(),
168                superset: self.open_set.clone(),
169            });
170        }
171        let colors = subset.colors();
172        let marking = self.marking.restrict(&colors);
173        Ok(Section {
174            open_set: subset.clone(),
175            marking,
176        })
177    }
178}
179
180#[derive(Debug, Clone, Serialize, Deserialize)]
181pub struct Sheaf {
182    pub sections: HashMap<OpenSet, Section>,
183}
184
185impl Default for Sheaf {
186    fn default() -> Self {
187        Self::new()
188    }
189}
190
191impl Sheaf {
192    pub fn new() -> Self {
193        Self {
194            sections: HashMap::new(),
195        }
196    }
197
198    /// Restrict a section to a smaller open set.
199    pub fn restriction(&self, section: &Section, subset: &OpenSet) -> Result<Section, CohomologyError> {
200        section.restrict(subset)
201    }
202
203    /// Verify that a list of local sections agree on all pairwise intersections
204    /// and, if so, return a global section over the union of the cover.
205    ///
206    /// Uses Merkle sub-root comparison for O(1) per-overlap verification.
207    /// On failure, returns a `CohomologyError::GluingFailure` containing
208    /// the mismatched markings for conflict report generation.
209    pub fn gluing_check(
210        &self,
211        local_sections: &[Section],
212        open_cover: &[OpenSet],
213    ) -> Result<Section, CohomologyError> {
214        if local_sections.len() != open_cover.len() {
215            return Err(CohomologyError::InputMismatch);
216        }
217        if local_sections.is_empty() {
218            return Ok(Section::new(OpenSet::new(), Marking::new()));
219        }
220
221        // Pre-compute Merkle trees for each section.
222        let merkle_trees: Vec<MerkleNode> =
223            local_sections.iter().map(section_to_merkle).collect();
224
225        let n = local_sections.len();
226        for i in 0..n {
227            for j in (i + 1)..n {
228                let intersection = open_cover[i].intersection(&open_cover[j]);
229                if intersection.is_empty() {
230                    continue;
231                }
232                // O(1) per-overlap: compare Merkle sub-roots.
233                let root_i = merkle_sub_root(&merkle_trees[i], &intersection.places);
234                let root_j = merkle_sub_root(&merkle_trees[j], &intersection.places);
235                if root_i != root_j {
236                    // Mismatch detected — fall back to full restriction
237                    // to capture the expected/actual markings for the
238                    // conflict report.
239                    let left = self.restriction(&local_sections[i], &intersection)?;
240                    let right = self.restriction(&local_sections[j], &intersection)?;
241                    return Err(CohomologyError::GluingFailure {
242                        place_i: local_sections[i].open_set.places.iter().next().cloned().unwrap_or(Place::new("?")),
243                        place_j: local_sections[j].open_set.places.iter().next().cloned().unwrap_or(Place::new("?")),
244                        intersection: intersection.clone(),
245                        expected_marking: left.marking,
246                        actual_marking: right.marking,
247                        cohomology_class: "[delta_s]".to_string(),
248                    });
249                }
250            }
251        }
252
253        let mut union = OpenSet::new();
254        let mut marking = Marking::new();
255        for (section, cover) in local_sections.iter().zip(open_cover.iter()) {
256            union.places.extend(cover.places.iter().cloned());
257            // Merge tokens; gluing_check guarantees consistency on overlaps.
258            for (color, vals) in &section.marking.by_place {
259                marking.by_place.insert(color.clone(), vals.clone());
260            }
261        }
262        Ok(Section::new(union, marking))
263    }
264}
265
266#[derive(Debug, Clone, Serialize, Deserialize)]
267pub enum CohomologyError {
268    InputMismatch,
269    InvalidRestriction { subset: OpenSet, superset: OpenSet },
270    GluingFailure {
271        place_i: Place,
272        place_j: Place,
273        intersection: OpenSet,
274        expected_marking: Marking,
275        actual_marking: Marking,
276        cohomology_class: String,
277    },
278}
279
280impl std::fmt::Display for CohomologyError {
281    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
282        match self {
283            CohomologyError::InputMismatch => write!(f, "open cover and local sections have different lengths"),
284            CohomologyError::InvalidRestriction { subset, superset } => {
285                write!(f, "cannot restrict {:?} to subset {:?}", superset, subset)
286            }
287            CohomologyError::GluingFailure { place_i, place_j, intersection, .. } => {
288                write!(
289                    f,
290                    "COHOMOLOGICAL OBSTRUCTION: Sections disagree on intersection of {:?} and {:?}: {:?}",
291                    place_i.id, place_j.id, intersection
292                )
293            }
294        }
295    }
296}
297
298impl std::error::Error for CohomologyError {}
299
300// ─────────────────────────────────────────────────────────────────────
301// Merkle-DAG Section Encoding (Story 139.4.2)
302// ─────────────────────────────────────────────────────────────────────
303
304/// A Merkle node for content-addressed section encoding.
305#[derive(Debug, Clone, Serialize, Deserialize)]
306pub struct MerkleNode {
307    pub hash: [u8; 32],
308    pub children: Vec<MerkleNode>,
309    pub place_id: Option<String>,
310    pub payload: Option<Vec<u8>>,
311}
312
313/// Compute the content hash of a payload, returning a 32-byte hash.
314pub fn compute_merkle_root(payload: &[u8]) -> [u8; 32] {
315    crate::hash::raw_hash_bytes_32(payload)
316}
317
318/// Compute the Merkle root of a set of child nodes by hashing their
319/// concatenated child hashes.
320pub fn compute_merkle_node(children: &[MerkleNode]) -> [u8; 32] {
321    let mut combined = Vec::new();
322    for child in children {
323        combined.extend_from_slice(&child.hash);
324    }
325    crate::hash::raw_hash_bytes_32(&combined)
326}
327
328/// Encode a section as a Merkle tree — one leaf per place in the section.
329/// Each leaf is the SHA-256 of the place's marking (serialized as
330/// `color:hash1,hash2,...` sorted by color).
331pub fn section_to_merkle(section: &Section) -> MerkleNode {
332    let mut leaves: Vec<MerkleNode> = section
333        .open_set
334        .places
335        .iter()
336        .map(|place| {
337            let tokens = section.marking.by_place.get(&place.id);
338            let payload = match tokens {
339                Some(vals) => format!("{}:{}", place.id, vals.join(",")),
340                None => place.id.clone(),
341            };
342            let hash = compute_merkle_root(payload.as_bytes());
343            MerkleNode {
344                hash,
345                children: vec![],
346                place_id: Some(place.id.clone()),
347                payload: Some(payload.into_bytes()),
348            }
349        })
350        .collect();
351    leaves.sort_by(|a, b| a.place_id.cmp(&b.place_id));
352    let root_hash = compute_merkle_node(&leaves);
353    MerkleNode {
354        hash: root_hash,
355        children: leaves,
356        place_id: None,
357        payload: None,
358    }
359}
360
361/// Compute the Merkle root of the subset of leaves corresponding to the
362/// given places. This enables O(1) per-overlap verification by comparing
363/// only the sub-root hashes.
364pub fn merkle_sub_root(node: &MerkleNode, places: &BTreeSet<Place>) -> [u8; 32] {
365    let place_ids: BTreeSet<String> = places.iter().map(|p| p.id.clone()).collect();
366    let matching: Vec<&MerkleNode> = node
367        .children
368        .iter()
369        .filter(|c| {
370            c.place_id
371                .as_ref()
372                .map(|id| place_ids.contains(id))
373                .unwrap_or(false)
374        })
375        .collect();
376    if matching.is_empty() {
377        return [0u8; 32];
378    }
379    let mut combined = Vec::new();
380    for child in &matching {
381        combined.extend_from_slice(&child.hash);
382    }
383    crate::hash::raw_hash_bytes_32(&combined)
384}
385
386#[cfg(feature = "native")]
387pub use crate::layer2::sheaf_persistence::{load_section_merkle, store_section_merkle};
388
389// ─────────────────────────────────────────────────────────────────────
390// Cohomology Conflict Reporter (Story 139.4.3)
391// ─────────────────────────────────────────────────────────────────────
392
393/// A structured conflict report produced when gluing fails. This is
394/// content-addressed and stored as an MCard in `execution_log`.
395#[derive(Debug, Clone, Serialize, Deserialize)]
396pub struct CohomologyConflictReport {
397    pub conflicting_places: (Place, Place),
398    pub intersection: OpenSet,
399    pub expected_marking: Marking,
400    pub actual_marking: Marking,
401    pub cohomology_class: String,
402    pub timestamp: String,
403    pub agent_dids: Vec<String>,
404}
405
406impl CohomologyConflictReport {
407    /// Serialize the conflict report as YAML.
408    pub fn to_yaml(&self) -> String {
409        serde_yaml::to_string(self).unwrap_or_else(|_| "cohomology_conflict: <error>".to_string())
410    }
411
412    /// Compute the content address of the report.
413    pub fn content_hash(&self) -> String {
414        crate::hash::raw_hash_string(&self.to_yaml())
415    }
416
417    /// Create a conflict report from a `CohomologyError::GluingFailure`.
418    pub fn from_error(
419        err: &CohomologyError,
420        agent_dids: Vec<String>,
421    ) -> Option<Self> {
422        match err {
423            CohomologyError::GluingFailure {
424                place_i,
425                place_j,
426                intersection,
427                expected_marking,
428                actual_marking,
429                cohomology_class,
430            } => Some(CohomologyConflictReport {
431                conflicting_places: (place_i.clone(), place_j.clone()),
432                intersection: intersection.clone(),
433                expected_marking: expected_marking.clone(),
434                actual_marking: actual_marking.clone(),
435                cohomology_class: cohomology_class.clone(),
436                timestamp: chrono::Utc::now().to_rfc3339(),
437                agent_dids,
438            }),
439            _ => None,
440        }
441    }
442}
443
444#[cfg(feature = "native")]
445pub use crate::layer2::sheaf_persistence::store_conflict_report;
446
447#[cfg(test)]
448#[path = "sheaf_tests.rs"]
449mod tests;