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

ic_backup/model/effect_graph/
mod.rs
