ic_backup/model/effect_graph/
mod.rs

1//! Immutable explicit operation dependencies; no universal application ordering or authority.
2
3use crate::model::evidence_digest::EvidenceDigest;
4mod node;
5pub use node::{EffectNodeRecord, EffectNodeRequest, MAX_EFFECT_DEPENDENCIES};
6
7use crate::model::{artifacts::ArtifactChecksumRecord, bounded_sequence};
8use serde::{Deserialize, Deserializer, Serialize};
9use std::collections::{BTreeMap, BTreeSet};
10use thiserror::Error;
11
12/// Maximum operation identities in a declared dependency graph.
13pub const MAX_EFFECT_OPERATIONS: usize = 8192;
14/// Maximum total explicit dependencies across one graph.
15pub const MAX_EFFECT_EDGES: usize = 65536;
16
17/// Canonical v1 dependency graph over opaque exact operation sequence identities.
18///
19/// Nodes refer to operations owned by a future complete plan. This record contains
20/// no effects, targets, request codecs, current authority or completion receipts.
21/// Parent-before-child and lifecycle order must be explicitly qualified by an integration.
22#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
23#[serde(try_from = "GraphFields")]
24pub struct EffectGraphRecord {
25    version: u16,
26    nodes: Vec<EffectNodeRecord>,
27    #[serde(skip)]
28    order: Vec<usize>,
29}
30
31#[derive(Deserialize)]
32#[serde(deny_unknown_fields)]
33struct GraphFields {
34    version: u16,
35    #[serde(deserialize_with = "bounded_nodes")]
36    nodes: Vec<EffectNodeRecord>,
37}
38impl TryFrom<GraphFields> for EffectGraphRecord {
39    type Error = EffectGraphError;
40    fn try_from(fields: GraphFields) -> Result<Self, Self::Error> {
41        if fields.version != 1 {
42            return Err(EffectGraphError::UnsupportedVersion(fields.version));
43        }
44        Self::new(fields.nodes)
45    }
46}
47
48impl EffectGraphRecord {
49    /// Validate bounded, unique, closed acyclic dependencies without IO.
50    ///
51    /// # Errors
52    /// Rejects empty/excessive graphs, repeated identities, missing edges and cycles.
53    pub fn new(mut nodes: Vec<EffectNodeRecord>) -> Result<Self, EffectGraphError> {
54        if nodes.is_empty() {
55            return Err(EffectGraphError::EmptyGraph);
56        }
57        if nodes.len() > MAX_EFFECT_OPERATIONS {
58            return Err(EffectGraphError::TooManyOperations);
59        }
60        nodes.sort_by_key(EffectNodeRecord::operation_sequence);
61        for pair in nodes.windows(2) {
62            if pair[0].operation_sequence() == pair[1].operation_sequence() {
63                return Err(EffectGraphError::DuplicateOperation(
64                    pair[0].operation_sequence(),
65                ));
66            }
67        }
68        let mut edges = 0;
69        for node in &nodes {
70            edges = add_edges(edges, node.depends_on().len())?;
71        }
72        let order = topological_order(&nodes)?;
73        Ok(Self {
74            version: 1,
75            nodes,
76            order,
77        })
78    }
79    /// Read immutable nodes in ascending operation sequence order.
80    #[must_use]
81    pub fn nodes(&self) -> &[EffectNodeRecord] {
82        &self.nodes
83    }
84    /// Resolve an exact operation identity without treating its numeric value as an order.
85    ///
86    /// # Errors
87    /// Rejects operation identities absent from the original graph.
88    pub fn node(&self, sequence: u64) -> Result<&EffectNodeRecord, EffectGraphError> {
89        self.nodes
90            .binary_search_by_key(&sequence, EffectNodeRecord::operation_sequence)
91            .map(|index| &self.nodes[index])
92            .map_err(|_| EffectGraphError::UnknownOperation(sequence))
93    }
94    /// Project deterministic topological order; smallest currently ready sequence wins ties.
95    ///
96    /// This order grants no effect authorization, target identity or fresh safety evidence.
97    pub fn ordered_nodes(
98        &self,
99    ) -> impl ExactSizeIterator<Item = &EffectNodeRecord> + DoubleEndedIterator + '_ {
100        self.order.iter().map(|index| &self.nodes[*index])
101    }
102    /// Hash canonical explicit identities/edges using the documented v1 binary encoding.
103    #[must_use]
104    pub fn digest(&self) -> ArtifactChecksumRecord {
105        let mut bytes = EvidenceDigest::new(b"ic-backup/effect-graph/v1\0");
106        append_count(&mut bytes, self.nodes.len());
107        for node in &self.nodes {
108            bytes.append(&node.operation_sequence().to_be_bytes());
109            append_count(&mut bytes, node.depends_on().len());
110            for dependency in node.depends_on() {
111                bytes.append(&dependency.to_be_bytes());
112            }
113        }
114        bytes.finish()
115    }
116}
117
118#[expect(
119    clippy::cast_possible_truncation,
120    reason = "validated operation/dependency counts are at most 8192"
121)]
122fn append_count(bytes: &mut EvidenceDigest, count: usize) {
123    bytes.append(&(count as u32).to_be_bytes());
124}
125
126fn topological_order(nodes: &[EffectNodeRecord]) -> Result<Vec<usize>, EffectGraphError> {
127    let indices: BTreeMap<_, _> = nodes
128        .iter()
129        .enumerate()
130        .map(|(index, node)| (node.operation_sequence(), index))
131        .collect();
132    let mut dependents = vec![Vec::new(); nodes.len()];
133    let mut remaining: Vec<_> = nodes.iter().map(|node| node.depends_on().len()).collect();
134    for (index, node) in nodes.iter().enumerate() {
135        for dependency in node.depends_on() {
136            let parent = indices
137                .get(dependency)
138                .ok_or(EffectGraphError::MissingDependency {
139                    operation_sequence: node.operation_sequence(),
140                    dependency: *dependency,
141                })?;
142            dependents[*parent].push(index);
143        }
144    }
145    let mut ready: BTreeSet<_> = remaining
146        .iter()
147        .enumerate()
148        .filter_map(|(index, count)| (*count == 0).then_some(index))
149        .collect();
150    let mut order = Vec::with_capacity(nodes.len());
151    while let Some(index) = ready.pop_first() {
152        order.push(index);
153        for dependent in &dependents[index] {
154            remaining[*dependent] -= 1;
155            if remaining[*dependent] == 0 {
156                ready.insert(*dependent);
157            }
158        }
159    }
160    if order.len() != nodes.len() {
161        return Err(EffectGraphError::Cycle);
162    }
163    Ok(order)
164}
165
166fn add_edges(current: usize, additional: usize) -> Result<usize, EffectGraphError> {
167    current
168        .checked_add(additional)
169        .filter(|total| *total <= MAX_EFFECT_EDGES)
170        .ok_or(EffectGraphError::TooManyEdges)
171}
172
173fn bounded_nodes<'de, D: Deserializer<'de>>(
174    deserializer: D,
175) -> Result<Vec<EffectNodeRecord>, D::Error> {
176    let mut edges = 0;
177    bounded_sequence::deserialize_checked::<D, EffectNodeRecord, _, _, MAX_EFFECT_OPERATIONS>(
178        deserializer,
179        "bounded explicit effect nodes and total edges",
180        EffectGraphError::TooManyOperations,
181        |node| {
182            edges = add_edges(edges, node.depends_on().len())?;
183            Ok::<(), EffectGraphError>(())
184        },
185    )
186}
187
188/// Typed declared graph identity, dependency or resource-bound rejection.
189#[derive(Debug, Error)]
190pub enum EffectGraphError {
191    /// Only protocol generation v1 is maintained.
192    #[error("unsupported effect graph version {0}")]
193    UnsupportedVersion(u16),
194    /// At least one exact operation must be declared.
195    #[error("effect graph contains no operations")]
196    EmptyGraph,
197    /// Node count exceeds its maintained bound.
198    #[error("effect graph exceeds {MAX_EFFECT_OPERATIONS} operations")]
199    TooManyOperations,
200    /// One operation declares too many direct dependencies.
201    #[error("effect node exceeds {MAX_EFFECT_DEPENDENCIES} dependencies")]
202    TooManyDependencies,
203    /// Total graph dependencies exceed the maintained bound.
204    #[error("effect graph exceeds {MAX_EFFECT_EDGES} edges")]
205    TooManyEdges,
206    /// An exact operation was declared more than once.
207    #[error("duplicate effect operation {0}")]
208    DuplicateOperation(u64),
209    /// A requested exact operation is absent.
210    #[error("unknown effect operation {0}")]
211    UnknownOperation(u64),
212    /// A dependency identity appears more than once in one operation.
213    #[error("effect operation {operation_sequence} repeats dependency {dependency}")]
214    DuplicateDependency {
215        /// Exact owning operation sequence.
216        operation_sequence: u64,
217        /// Repeated exact prerequisite sequence.
218        dependency: u64,
219    },
220    /// An edge references an absent exact operation.
221    #[error("effect operation {operation_sequence} has absent dependency {dependency}")]
222    MissingDependency {
223        /// Exact owning operation sequence.
224        operation_sequence: u64,
225        /// Absent prerequisite sequence.
226        dependency: u64,
227    },
228    /// Dependencies include a self-loop or longer cycle.
229    #[error("effect graph contains a dependency cycle")]
230    Cycle,
231}
232
233#[cfg(test)]
234mod tests;
ic_backup/model/effect_graph/mod.rs

ic_backup/model/effect_graph/
mod.rs
