ic-backup 0.61.0

//! Deterministic bounded dependency order over the authoritative operation rows.
use super::{OperationPlanError, PlannedOperationRecord};
use std::collections::BTreeSet;
/// Maximum operations in one plan.
pub const MAX_PLAN_OPERATIONS: usize = 8192;
/// Maximum prerequisites declared by one operation.
pub const MAX_PLAN_DEPENDENCIES: usize = 1024;
/// Maximum dependencies across one plan.
pub const MAX_PLAN_EDGES: usize = 65536;

pub(super) fn order(nodes: &[PlannedOperationRecord]) -> Result<Vec<usize>, OperationPlanError> {
    let mut edges = 0;
    for node in nodes {
        edges = add_edges(edges, node.depends_on().len())?;
    }
    let mut dependents = vec![Vec::new(); nodes.len()];
    let mut remaining: Vec<_> = nodes.iter().map(|node| node.depends_on().len()).collect();
    for (index, node) in nodes.iter().enumerate() {
        for dependency in node.depends_on() {
            let parent = nodes
                .binary_search_by_key(dependency, PlannedOperationRecord::operation_sequence)
                .map_err(|_| OperationPlanError::MissingDependency {
                    operation_sequence: node.operation_sequence(),
                    dependency: *dependency,
                })?;
            dependents[parent].push(index);
        }
    }
    let mut ready: BTreeSet<_> = remaining
        .iter()
        .enumerate()
        .filter_map(|(index, count)| (*count == 0).then_some(index))
        .collect();
    let mut order = Vec::with_capacity(nodes.len());
    while let Some(index) = ready.pop_first() {
        order.push(index);
        for dependent in &dependents[index] {
            remaining[*dependent] -= 1;
            if remaining[*dependent] == 0 {
                ready.insert(*dependent);
            }
        }
    }
    if order.len() != nodes.len() {
        return Err(OperationPlanError::Cycle);
    }
    Ok(order)
}

pub(super) fn add_edges(current: usize, additional: usize) -> Result<usize, OperationPlanError> {
    current
        .checked_add(additional)
        .filter(|total| *total <= MAX_PLAN_EDGES)
        .ok_or(OperationPlanError::TooManyEdges)
}

#[cfg(test)]
mod tests;