ic_backup/model/effect_graph/
mod.rs

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

ic_backup/model/effect_graph/
mod.rs
