haz-dag 0.1.0

//! Hard-edge graph traversal helpers for relational queries.
//!
//! Per `QRY-004`, the relational filters (`--child-of`,
//! `--parent-of`, `--depends-on`, `--ancestor-of`) operate on the
//! hard-edge graph of `DAG-008` only. Weak edges (`DAG-009`) and
//! producer-matching edges (`DAG-013`) MUST NOT contribute to any
//! relational filter.
//!
//! These helpers expose that hard-edge view as four primitives:
//! direct and transitive predecessor / successor sets. They operate
//! against a [`crate::graph::TaskGraph`] post-construction, so they
//! rely on `DAG-012` (no hard / soft self-loops) and `DAG-014` (no
//! cycles in the hard-edge subgraph) for termination.

use std::collections::{BTreeSet, VecDeque};

use haz_domain::task_id::TaskId;

use crate::edge::EdgeKind;
use crate::graph::TaskGraph;

/// Direct hard-edge predecessors of `node`: every task `B` such
/// that a hard edge `B -> node` exists in `graph`. Returns the
/// empty set when `node` has no hard-edge predecessors (or is not
/// present in `graph` at all).
#[must_use]
pub fn direct_predecessors(graph: &TaskGraph, node: &TaskId) -> BTreeSet<TaskId> {
    graph
        .edges
        .iter()
        .filter(|edge| edge.kind == EdgeKind::Hard && &edge.to == node)
        .map(|edge| edge.from.clone())
        .collect()
}

/// Direct hard-edge successors of `node`: every task `B` such that
/// a hard edge `node -> B` exists in `graph`. Returns the empty
/// set when `node` has no hard-edge successors (or is not present
/// in `graph` at all).
#[must_use]
pub fn direct_successors(graph: &TaskGraph, node: &TaskId) -> BTreeSet<TaskId> {
    graph
        .edges
        .iter()
        .filter(|edge| edge.kind == EdgeKind::Hard && &edge.from == node)
        .map(|edge| edge.to.clone())
        .collect()
}

/// Transitive hard-edge predecessors of `node`: every task
/// reachable from `node` by walking hard edges backwards. The
/// result does NOT contain `node` itself (the closure is strict,
/// not reflexive); callers that need a reflexive view union the
/// returned set with `{node}` themselves.
#[must_use]
pub fn transitive_predecessors(graph: &TaskGraph, node: &TaskId) -> BTreeSet<TaskId> {
    bfs(graph, node, EdgeDirection::Backward)
}

/// Transitive hard-edge successors of `node`: every task reachable
/// from `node` by walking hard edges forwards. The result does NOT
/// contain `node` itself (the closure is strict, not reflexive);
/// callers that need a reflexive view union the returned set with
/// `{node}` themselves.
#[must_use]
pub fn transitive_successors(graph: &TaskGraph, node: &TaskId) -> BTreeSet<TaskId> {
    bfs(graph, node, EdgeDirection::Forward)
}

#[derive(Clone, Copy)]
enum EdgeDirection {
    Forward,
    Backward,
}

fn bfs(graph: &TaskGraph, seed: &TaskId, direction: EdgeDirection) -> BTreeSet<TaskId> {
    let mut visited: BTreeSet<TaskId> = BTreeSet::new();
    let mut queue: VecDeque<TaskId> = VecDeque::new();
    queue.push_back(seed.clone());
    while let Some(current) = queue.pop_front() {
        let neighbours = match direction {
            EdgeDirection::Forward => direct_successors(graph, &current),
            EdgeDirection::Backward => direct_predecessors(graph, &current),
        };
        for neighbour in neighbours {
            if &neighbour == seed {
                continue;
            }
            if visited.insert(neighbour.clone()) {
                queue.push_back(neighbour);
            }
        }
    }
    visited
}

#[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;
    use crate::traversal::{
        direct_predecessors, direct_successors, transitive_predecessors, transitive_successors,
    };

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

    fn graph_with(nodes: &[TaskId], edges: &[Edge]) -> TaskGraph {
        TaskGraph {
            nodes: nodes.iter().cloned().collect(),
            edges: edges.iter().cloned().collect(),
        }
    }

    fn ids(items: &[(&str, &str)]) -> BTreeSet<TaskId> {
        items.iter().map(|(p, t)| id(p, t)).collect()
    }

    // --- direct_predecessors / direct_successors ----------------

    #[test]
    fn direct_predecessors_returns_empty_for_isolated_node() {
        let a = id("p", "a");
        let graph = graph_with(std::slice::from_ref(&a), &[]);
        assert!(direct_predecessors(&graph, &a).is_empty());
    }

    #[test]
    fn direct_predecessors_returns_only_immediate_hard_predecessors() {
        let a = id("p", "a");
        let b = id("p", "b");
        let c = id("p", "c");
        let graph = graph_with(
            &[a.clone(), b.clone(), c.clone()],
            &[
                Edge {
                    from: a.clone(),
                    to: b.clone(),
                    kind: EdgeKind::Hard,
                },
                Edge {
                    from: b.clone(),
                    to: c.clone(),
                    kind: EdgeKind::Hard,
                },
            ],
        );
        assert_eq!(direct_predecessors(&graph, &c), ids(&[("p", "b")]));
        assert_eq!(direct_predecessors(&graph, &b), ids(&[("p", "a")]));
        assert!(direct_predecessors(&graph, &a).is_empty());
    }

    #[test]
    fn direct_successors_returns_only_immediate_hard_successors() {
        let a = id("p", "a");
        let b = id("p", "b");
        let c = id("p", "c");
        let graph = graph_with(
            &[a.clone(), b.clone(), c.clone()],
            &[
                Edge {
                    from: a.clone(),
                    to: b.clone(),
                    kind: EdgeKind::Hard,
                },
                Edge {
                    from: a.clone(),
                    to: c.clone(),
                    kind: EdgeKind::Hard,
                },
            ],
        );
        assert_eq!(
            direct_successors(&graph, &a),
            ids(&[("p", "b"), ("p", "c")])
        );
        assert!(direct_successors(&graph, &b).is_empty());
        assert!(direct_successors(&graph, &c).is_empty());
    }

    #[test]
    fn direct_predecessors_ignores_soft_edges() {
        let a = id("p", "a");
        let b = id("p", "b");
        let graph = graph_with(
            &[a.clone(), b.clone()],
            &[Edge {
                from: a,
                to: b.clone(),
                kind: EdgeKind::Soft,
            }],
        );
        assert!(direct_predecessors(&graph, &b).is_empty());
    }

    #[test]
    fn direct_predecessors_ignores_producer_matching_edges() {
        let a = id("p", "a");
        let b = id("p", "b");
        let graph = graph_with(
            &[a.clone(), b.clone()],
            &[Edge {
                from: a,
                to: b.clone(),
                kind: EdgeKind::ProducerMatching,
            }],
        );
        assert!(direct_predecessors(&graph, &b).is_empty());
    }

    #[test]
    fn direct_successors_ignores_soft_and_producer_edges() {
        let a = id("p", "a");
        let b = id("p", "b");
        let c = id("p", "c");
        let graph = graph_with(
            &[a.clone(), b.clone(), c.clone()],
            &[
                Edge {
                    from: a.clone(),
                    to: b,
                    kind: EdgeKind::Soft,
                },
                Edge {
                    from: a.clone(),
                    to: c,
                    kind: EdgeKind::ProducerMatching,
                },
            ],
        );
        assert!(direct_successors(&graph, &a).is_empty());
    }

    // --- transitive_predecessors / transitive_successors --------

    #[test]
    fn transitive_predecessors_walks_chain_backwards() {
        // a -> b -> c -> d
        let a = id("p", "a");
        let b = id("p", "b");
        let c = id("p", "c");
        let d = id("p", "d");
        let graph = graph_with(
            &[a.clone(), b.clone(), c.clone(), d.clone()],
            &[
                Edge {
                    from: a,
                    to: b.clone(),
                    kind: EdgeKind::Hard,
                },
                Edge {
                    from: b,
                    to: c.clone(),
                    kind: EdgeKind::Hard,
                },
                Edge {
                    from: c,
                    to: d.clone(),
                    kind: EdgeKind::Hard,
                },
            ],
        );
        assert_eq!(
            transitive_predecessors(&graph, &d),
            ids(&[("p", "a"), ("p", "b"), ("p", "c")]),
        );
    }

    #[test]
    fn transitive_successors_walks_chain_forwards() {
        // a -> b -> c -> d
        let a = id("p", "a");
        let b = id("p", "b");
        let c = id("p", "c");
        let d = id("p", "d");
        let graph = graph_with(
            &[a.clone(), b.clone(), c.clone(), d.clone()],
            &[
                Edge {
                    from: a.clone(),
                    to: b.clone(),
                    kind: EdgeKind::Hard,
                },
                Edge {
                    from: b,
                    to: c.clone(),
                    kind: EdgeKind::Hard,
                },
                Edge {
                    from: c,
                    to: d,
                    kind: EdgeKind::Hard,
                },
            ],
        );
        assert_eq!(
            transitive_successors(&graph, &a),
            ids(&[("p", "b"), ("p", "c"), ("p", "d")]),
        );
    }

    #[test]
    fn transitive_closure_handles_diamond_without_duplicates() {
        // a -> b, a -> c, b -> d, c -> d
        let a = id("p", "a");
        let b = id("p", "b");
        let c = id("p", "c");
        let d = id("p", "d");
        let graph = graph_with(
            &[a.clone(), b.clone(), c.clone(), d.clone()],
            &[
                Edge {
                    from: a.clone(),
                    to: b.clone(),
                    kind: EdgeKind::Hard,
                },
                Edge {
                    from: a.clone(),
                    to: c.clone(),
                    kind: EdgeKind::Hard,
                },
                Edge {
                    from: b,
                    to: d.clone(),
                    kind: EdgeKind::Hard,
                },
                Edge {
                    from: c,
                    to: d.clone(),
                    kind: EdgeKind::Hard,
                },
            ],
        );
        assert_eq!(
            transitive_successors(&graph, &a),
            ids(&[("p", "b"), ("p", "c"), ("p", "d")]),
        );
        assert_eq!(
            transitive_predecessors(&graph, &d),
            ids(&[("p", "a"), ("p", "b"), ("p", "c")]),
        );
    }

    #[test]
    fn transitive_closure_excludes_starting_node() {
        // a -> b -> a is impossible per DAG-012 / DAG-014, but the
        // helper still treats the seed itself as "outside" the
        // closure so the caller is responsible for any reflexive
        // semantics.
        let a = id("p", "a");
        let b = id("p", "b");
        let graph = graph_with(
            &[a.clone(), b.clone()],
            &[
                Edge {
                    from: a.clone(),
                    to: b.clone(),
                    kind: EdgeKind::Hard,
                },
                Edge {
                    from: b,
                    to: a.clone(),
                    kind: EdgeKind::Hard,
                },
            ],
        );
        assert_eq!(transitive_successors(&graph, &a), ids(&[("p", "b")]));
    }

    #[test]
    fn transitive_closure_ignores_soft_edges() {
        // a -> b is soft; transitive_successors(a) is empty.
        let a = id("p", "a");
        let b = id("p", "b");
        let graph = graph_with(
            &[a.clone(), b.clone()],
            &[Edge {
                from: a.clone(),
                to: b,
                kind: EdgeKind::Soft,
            }],
        );
        assert!(transitive_successors(&graph, &a).is_empty());
    }

    #[test]
    fn transitive_closure_ignores_producer_matching_edges() {
        let a = id("p", "a");
        let b = id("p", "b");
        let c = id("p", "c");
        let graph = graph_with(
            &[a.clone(), b.clone(), c.clone()],
            &[
                Edge {
                    from: a.clone(),
                    to: b.clone(),
                    kind: EdgeKind::Hard,
                },
                Edge {
                    from: b,
                    to: c,
                    kind: EdgeKind::ProducerMatching,
                },
            ],
        );
        assert_eq!(transitive_successors(&graph, &a), ids(&[("p", "b")]));
    }

    #[test]
    fn transitive_closure_handles_unrelated_subgraphs() {
        // Component 1: a -> b. Component 2: x -> y.
        let a = id("p", "a");
        let b = id("p", "b");
        let x = id("p", "x");
        let y = id("p", "y");
        let graph = graph_with(
            &[a.clone(), b.clone(), x.clone(), y.clone()],
            &[
                Edge {
                    from: a.clone(),
                    to: b,
                    kind: EdgeKind::Hard,
                },
                Edge {
                    from: x.clone(),
                    to: y,
                    kind: EdgeKind::Hard,
                },
            ],
        );
        assert_eq!(transitive_successors(&graph, &a), ids(&[("p", "b")]));
        assert_eq!(transitive_successors(&graph, &x), ids(&[("p", "y")]));
    }

    #[test]
    fn transitive_closure_returns_empty_for_dead_end() {
        // a is a sink; transitive_successors(a) is empty.
        let a = id("p", "a");
        let b = id("p", "b");
        let graph = graph_with(
            &[a.clone(), b.clone()],
            &[Edge {
                from: b,
                to: a.clone(),
                kind: EdgeKind::Hard,
            }],
        );
        assert!(transitive_successors(&graph, &a).is_empty());
    }

    #[test]
    fn transitive_closure_returns_empty_for_isolated_node() {
        let a = id("p", "a");
        let graph = graph_with(std::slice::from_ref(&a), &[]);
        assert!(transitive_successors(&graph, &a).is_empty());
        assert!(transitive_predecessors(&graph, &a).is_empty());
    }
}