haz-dag 0.1.0

//! [`TaskGraph`]: the validated task DAG of a workspace.
//!
//! A `TaskGraph` is the structural result of running construction
//! over a fully-loaded workspace. It carries the set of nodes
//! ([`TaskId`]s) and the set of [`Edge`]s tagged by kind. The
//! single `edges` bag makes `DAG-014` cycle detection natural,
//! since cycle detection operates on the *union* of hard, soft,
//! and producer-matching edges; rules that target a single kind
//! (hard-only topological order, weak-only conditional ordering)
//! filter by [`EdgeKind`] cheaply.
//!
//! The data layer holds no construction-time invariants. Those
//! belong to the graph-construction module.

use std::collections::BTreeSet;

use haz_domain::task_id::TaskId;

use crate::edge::Edge;

/// The validated task graph of a workspace.
///
/// # Examples
///
/// ```
/// use std::collections::BTreeSet;
/// use std::str::FromStr;
/// use haz_dag::edge::{Edge, EdgeKind};
/// use haz_dag::graph::TaskGraph;
/// use haz_domain::name::{ProjectName, TaskName};
/// use haz_domain::task_id::TaskId;
///
/// let a = TaskId {
///     project: ProjectName::from_str("p").unwrap(),
///     task: TaskName::from_str("a").unwrap(),
/// };
/// let b = TaskId {
///     project: ProjectName::from_str("p").unwrap(),
///     task: TaskName::from_str("b").unwrap(),
/// };
///
/// let graph = TaskGraph {
///     nodes: BTreeSet::from([a.clone(), b.clone()]),
///     edges: BTreeSet::from([Edge {
///         from: a,
///         to: b,
///         kind: EdgeKind::Hard,
///     }]),
/// };
/// assert_eq!(graph.nodes.len(), 2);
/// assert_eq!(graph.edges.len(), 1);
/// ```
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct TaskGraph {
    /// Every task that participates in the graph, by identity.
    pub nodes: BTreeSet<TaskId>,
    /// Every edge in the graph, tagged by [`crate::edge::EdgeKind`].
    pub edges: BTreeSet<Edge>,
}

#[cfg(test)]
mod tests {
    use std::collections::BTreeSet;
    use std::str::FromStr;

    use haz_domain::name::{ProjectName, TaskName};
    use haz_domain::task_id::TaskId;

    use crate::edge::{Edge, EdgeKind};
    use crate::graph::TaskGraph;

    fn id(project: &str, task: &str) -> TaskId {
        TaskId {
            project: ProjectName::from_str(project).unwrap(),
            task: TaskName::from_str(task).unwrap(),
        }
    }

    fn edge(from: TaskId, to: TaskId, kind: EdgeKind) -> Edge {
        Edge { from, to, kind }
    }

    #[test]
    fn default_graph_is_empty() {
        let graph = TaskGraph::default();
        assert!(graph.nodes.is_empty());
        assert!(graph.edges.is_empty());
    }

    #[test]
    fn graph_with_isolated_nodes_no_edges() {
        let graph = TaskGraph {
            nodes: BTreeSet::from([id("p", "a"), id("p", "b"), id("q", "a")]),
            edges: BTreeSet::new(),
        };
        assert_eq!(graph.nodes.len(), 3);
        assert!(graph.edges.is_empty());
    }

    #[test]
    fn graph_with_hard_chain_a_to_b_to_c() {
        let a = id("p", "a");
        let b = id("p", "b");
        let c = id("p", "c");
        let graph = TaskGraph {
            nodes: BTreeSet::from([a.clone(), b.clone(), c.clone()]),
            edges: BTreeSet::from([
                edge(a.clone(), b.clone(), EdgeKind::Hard),
                edge(b.clone(), c.clone(), EdgeKind::Hard),
            ]),
        };

        assert_eq!(graph.nodes.len(), 3);
        assert_eq!(graph.edges.len(), 2);

        let hard: Vec<_> = graph
            .edges
            .iter()
            .filter(|e| e.kind == EdgeKind::Hard)
            .cloned()
            .collect();
        assert_eq!(hard.len(), 2);
        assert!(hard.iter().any(|e| e.from == a && e.to == b));
        assert!(hard.iter().any(|e| e.from == b && e.to == c));
    }

    #[test]
    fn graph_admits_producer_matching_self_edge() {
        // DAG-013: a formatter/auto-fixer task whose own outputs
        // re-feed its own inputs gets a producer-matching self-edge.
        let node = id("formatter", "format");
        let graph = TaskGraph {
            nodes: BTreeSet::from([node.clone()]),
            edges: BTreeSet::from([edge(node.clone(), node.clone(), EdgeKind::ProducerMatching)]),
        };
        assert_eq!(graph.nodes.len(), 1);
        assert_eq!(graph.edges.len(), 1);
        let only = graph.edges.iter().next().unwrap();
        assert_eq!(only.from, only.to);
        assert_eq!(only.kind, EdgeKind::ProducerMatching);
    }

    #[test]
    fn graph_clones_preserve_value() {
        let a = id("p", "a");
        let b = id("p", "b");
        let original = TaskGraph {
            nodes: BTreeSet::from([a.clone(), b.clone()]),
            edges: BTreeSet::from([edge(a, b, EdgeKind::Soft)]),
        };
        let cloned = original.clone();
        assert_eq!(original, cloned);
    }
}