OCD Dev Log #002

Current Progress

Finally finished the implementation of the cluster definition parser as crate::model::Cluster. This new type only operates on strings via FromStr trait. The FromStr implementation also performs a series of checks to ensure that the cluster definition follows these pre-conditions:

1. Node dependencies exist in cluster.
2. Node dependencies are acyclic.
3. Directory aliases are always expanded.

I am very happy with how the code came out. I ended up using Kahn’s algorithm to perform acyclic check on cluster nodes in order to produce a valid path of dependencies for a given node using a stack variant of DFS.

Here is what the acyclic check function looks like right now:

fn acyclic_check(&self) -> Result<()> {
    let mut in_degree: HashMap<String, usize> = HashMap::new();
    let mut queue: VecDeque<String> = VecDeque::new();
    let mut visited: HashSet<String> = HashSet::new();

    // INVARIANT: The in-degree of each node is the sum of all incoming edges to each
    // destination node.
    for (name, node) in &self.nodes {
        in_degree.entry(name.clone()).or_insert(0);
        for dependency in node.dependencies.iter().flatten() {
            *in_degree.entry(dependency.clone()).or_insert(0) += 1;
        }
    }

    // INVARIANT: Queue always contains nodes with in-degree of 0, i.e., nodes with no incoming
    // edges.
    for (name, degree) in &in_degree {
        if *degree == 0 {
            queue.push_back(name.clone());
        }
    }

    // BFS traversal such that the in-degree of all dependencies of a popped node from queue is
    // decremented by one. If a given dependency's in-degree becomes zero, push it into the
    // queue to be traversed. Finally, mark the currently popped node as visisted.
    while let Some(current) = queue.pop_front() {
        for dependency in self.nodes[&current].dependencies.iter().flatten() {
            *in_degree.get_mut(dependency).unwrap() -= 1;
            if *in_degree.get(dependency).unwrap() == 0 {
                queue.push_back(dependency.clone());
            }
        }
        // INVARIANT: Visited nodes represent the topological sort of graph.
        visited.insert(current);
    }

    // INVARIANT: Queue is empty, but graph has not been fully visited.
    //   - There exists a cycle.
    //   - The unvisited nodes represent this cycle.
    if visited.len() != self.nodes.len() {
        let cycle: Vec<String> =
            self.nodes.keys().filter(|key| !visited.contains(*key)).cloned().collect();

        // TODO: Pretty print structure of cycle, besides printing names of problematic nodes.
        return Err(Error::CircularDependencies { cycle });
    }

    debug!("Topological sort of cluster nodes: {visited:?}");

    Ok(())
}

Here is the stack based DFS implementation:

#[derive(Debug)]
pub struct DependencyIter<'cluster> {
    graph: &'cluster HashMap<String, NodeEntry>,
    visited: HashSet<String>,
    stack: VecDeque<String>,
}

impl<'cluster> Iterator for DependencyIter<'cluster> {
    type Item = (&'cluster str, &'cluster NodeEntry);

    fn next(&mut self) -> Option<Self::Item> {
        // INVARIANT: Nodes and their dependencies are acyclic through acyclic check performed
        // during deserialization through `Cluster::from_str`.
        if let Some(node) = self.stack.pop_front() {
            let (name, node) = self.graph.get_key_value(&node)?;
            for dependency in node.dependencies.iter().flatten() {
                if !self.visited.contains(dependency) {
                    self.stack.push_front(dependency.clone());
                    self.visited.insert(dependency.clone());
                }
            }

            return Some((name.as_ref(), node));
        }

        None
    }
}

Finally, deserialization of cluster definition data is simply performed through the TryFrom trait for the new crate::model::{RootEntry, NodeEntry} types. The toml_edit crate really carries the entire code there, including the serialization method crate::model::NodeEntry::to_toml.

Overall, I am now moving on to the vcs module, which is where I will be implementing the core logic for the manipulation of repositories in repository store.