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

ic_backup/model/effect_graph/
mod.rs
