Function compute_insert_order

atomic-repository/src/apply/mod.rs:157–202

Determine the order to insert a set of changes respecting dependencies. This performs a topological sort of the changes based on their dependency relationships. # Arguments `changes` - Map of change hash to change # Returns Ordered list of hashes to insert (dependencies first).

(
    changes: &std::collections::HashMap<Hash, Change>,
)

///
/// Ordered list of hashes to insert (dependencies first).
pub fn compute_insert_order(
    changes: &std::collections::HashMap<Hash, Change>,
) -> InsertResult<Vec<Hash>> {
    let mut order = Vec::new();
    let mut visited = HashSet::new();
    let mut in_progress = HashSet::new();

    fn visit(
        hash: &Hash,
        changes: &std::collections::HashMap<Hash, Change>,
        visited: &mut HashSet<Hash>,
        in_progress: &mut HashSet<Hash>,
        order: &mut Vec<Hash>,
    ) -> InsertResult<()> {
        if visited.contains(hash) {
            return Ok(());
        }
        if in_progress.contains(hash) {
            return Err(InsertError::CyclicDependency {
                message: format!("Cycle detected involving {}", hash.to_base32()),
            });
        }

        in_progress.insert(*hash);

        if let Some(change) = changes.get(hash) {
            for dep in change.dependencies() {
                if changes.contains_key(dep) {
                    visit(dep, changes, visited, in_progress, order)?;
                }
            }
        }

        in_progress.remove(hash);
        visited.insert(*hash);
        order.push(*hash);

        Ok(())
    }

    for hash in changes.keys() {
        visit(hash, changes, &mut visited, &mut in_progress, &mut order)?;
    }

    Ok(order)
}

/// Write a change to the graph and add it to a view's change log.
///