haz_dag/

construction.rs

//! [`build_task_graph`]: turn a loaded [`Workspace`] into a
//! validated [`TaskGraph`].
//!
//! This module is the orchestrator for `DAG-001`..`DAG-015` of
//! `docs/spec/07-dag-semantics.md`:
//!
//! - `DAG-001`..`DAG-006` (overlay merging): the function first
//!   delegates to [`crate::effective::compute_effective_tasks`]
//!   to determine each project's effective task set. Collisions
//!   surface as [`BuildError::OverlayCollision`] and short-circuit
//!   the rest of the pipeline (without an unambiguous effective
//!   task set, downstream analysis cannot run soundly).
//! - `DAG-007` (node identity), `DAG-008` (hard edges from
//!   `deps`), `DAG-009` (soft edges from `weakDeps`).
//! - `DAG-010`: a node that resolves into BOTH `deps` and
//!   `weakDeps` of the same bearing task is rejected.
//! - `DAG-011`: every error from `DAG-007`..`DAG-015` is
//!   accumulated into a single [`BuildErrors`]; the function does
//!   not short-circuit within those phases.
//! - `DAG-012`: a reference whose resolved set contains the
//!   bearing node is rejected as a trivial self-cycle; the whole
//!   reference is discarded and no edges from it are added.
//! - `DAG-013`: producer-matching edges are merged in via
//!   [`crate::producer::compute_producer_edges`].
//! - `DAG-014`: cycles of length two or more in the union edge
//!   set are rejected via [`crate::cycles::detect_cycles`].
//! - `DAG-015`: literal outputs MUST be uniquely produced;
//!   collisions are emitted via
//!   [`crate::outputs::detect_literal_output_collisions`].
//!   `DAG-016` (glob-output overlap) is correctly deferred to
//!   runtime per the spec.

use std::collections::{BTreeMap, BTreeSet};
use std::fmt;

use haz_domain::name::{ProjectName, TaskName};
use haz_domain::project::Project;
use haz_domain::resolution::{ResolutionError, resolve_task_ref};
use haz_domain::task::Task;
use haz_domain::task_id::TaskId;
use haz_domain::task_ref::TaskRef;
use haz_domain::workspace::Workspace;
use snafu::Snafu;

use crate::edge::{Edge, EdgeKind};
use crate::effective::{
    DefinitionSource, EffectiveTasksByProject, OverlayMergeError, compute_effective_tasks,
};
use crate::graph::TaskGraph;

/// A single error encountered during [`build_task_graph`].
///
/// Multiple instances are accumulated into [`BuildErrors`] per
/// `DAG-011`: a workspace with N broken references and M overlap
/// violations produces a [`BuildErrors`] with `N + M + ...`
/// entries, not the first one.
#[derive(Debug, Clone, PartialEq, Eq, Snafu)]
pub enum BuildError {
    /// More than one definition source supplies a body for the
    /// `(project, task)` pair AND no unique winner exists under
    /// the specialisation order (`DAG-006`). Surfaced from
    /// [`crate::effective::compute_effective_tasks`].
    #[snafu(display(
        "task `{project}:{task}`: overlay-merge collision among {n} sources (DAG-006)",
        n = sources.len()
    ))]
    OverlayCollision {
        /// The project the collision applies to.
        project: ProjectName,
        /// The task name the collision applies to.
        task: TaskName,
        /// Every contributing definition source for the pair.
        sources: BTreeSet<DefinitionSource>,
    },

    /// A task reference could not be resolved against the
    /// workspace. The bearing task identifies WHERE in the
    /// workspace the unresolved reference lives.
    #[snafu(display("task `{bearing}`: reference `{reference}` is unresolved: {source}"))]
    UnresolvedReference {
        /// The bearing task (the task that owns the offending
        /// reference).
        bearing: TaskId,
        /// The reference, as parsed.
        reference: TaskRef,
        /// The resolution failure mode.
        source: ResolutionError,
    },

    /// A reference in `deps` or `weakDeps` resolved to the
    /// bearing task itself (`DAG-012`). The whole reference is
    /// rejected: no edges from it are added to the graph.
    ///
    /// The legitimate way to fan out across siblings without
    /// reaching the bearing is the sibling-modifier form
    /// (`^~:<task>` or `[<tag>]~:<task>`, per `REF-008`).
    #[snafu(display(
        "task `{bearing}`: reference `{reference}` resolves to the task itself (DAG-012)"
    ))]
    SelfReference {
        /// The bearing task.
        bearing: TaskId,
        /// The reference, as parsed.
        reference: TaskRef,
    },

    /// A node resolved into BOTH `deps` and `weakDeps` of the
    /// same bearing task (`DAG-010`). The two fields are
    /// mutually exclusive by intent; the workspace MUST be
    /// rejected.
    #[snafu(display(
        "task `{bearing}`: `{overlap}` listed in both `deps` and `weakDeps` (DAG-010)"
    ))]
    DepsWeakDepsOverlap {
        /// The bearing task.
        bearing: TaskId,
        /// The node that appears in both fields.
        overlap: TaskId,
    },

    /// A strongly-connected component of size two or more in the
    /// union of hard, soft, and producer-matching edges
    /// (`DAG-014`). Length-one cycles (a single task whose
    /// outputs intersect its own inputs per `DAG-013`) are
    /// permitted; this variant covers only length-two-or-more
    /// cycles.
    #[snafu(display("cyclic dependency among {n} tasks (DAG-014)", n = nodes.len()))]
    Cycle {
        /// The tasks participating in the strongly-connected
        /// component. Always `|nodes| >= 2`.
        nodes: std::collections::BTreeSet<TaskId>,
    },

    /// A literal output path is declared as an output by more
    /// than one task (`DAG-015`). Glob-output overlaps are
    /// deferred to runtime per `DAG-016` and do NOT produce this
    /// variant.
    #[snafu(display(
        "literal output `{path}` declared by {n} tasks (DAG-015)",
        n = tasks.len()
    ))]
    LiteralOutputCollision {
        /// Workspace-absolute string form of the colliding
        /// literal output path.
        path: String,
        /// Tasks that declared this path. Always `|tasks| >= 2`.
        tasks: std::collections::BTreeSet<TaskId>,
    },
}

/// All construction errors accumulated by [`build_task_graph`]
/// in a single pass over the workspace (`DAG-011`).
///
/// The collection is ordered: workspace-projects iteration is
/// sorted by [`haz_domain::name::ProjectName`], each project's
/// tasks iteration is sorted by
/// [`haz_domain::name::TaskName`], and per-task errors appear in
/// `deps`-then-`weakDeps` declaration order. This makes the
/// printed diagnostic stable across runs.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BuildErrors(Vec<BuildError>);

impl BuildErrors {
    /// View the underlying slice without consuming.
    #[must_use]
    pub fn as_slice(&self) -> &[BuildError] {
        &self.0
    }

    /// Consume and return the underlying vector.
    #[must_use]
    pub fn into_inner(self) -> Vec<BuildError> {
        self.0
    }

    /// Number of accumulated errors. Always `>= 1` for a value
    /// that escapes [`build_task_graph`] as `Err(_)`.
    #[must_use]
    pub fn len(&self) -> usize {
        self.0.len()
    }

    /// `true` if there are no errors (defensive; the constructor
    /// rejects empty input).
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.0.is_empty()
    }
}

impl fmt::Display for BuildErrors {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let n = self.0.len();
        writeln!(f, "{n} error(s) during DAG construction:")?;
        for (i, err) in self.0.iter().enumerate() {
            writeln!(f, "  {}. {err}", i + 1)?;
        }
        Ok(())
    }
}

impl std::error::Error for BuildErrors {}

/// Build the [`TaskGraph`] of a fully-loaded [`Workspace`].
///
/// Returns the `(graph, effective_workspace)` pair on success. The
/// `effective_workspace` is the input `workspace` with each
/// project's `tasks` replaced by its post-overlay-merge effective
/// task set per `DAG-001`..`DAG-006`. Downstream callers (target
/// resolution, cache-key derivation, `haz why`, `haz query`) MUST
/// read from the returned `effective_workspace`; the un-merged
/// input is missing overlay-attached tasks and is unsafe to
/// consult for those phases.
///
/// Nodes are every `(project, task)` pair in the effective
/// workspace (`DAG-007`). Hard edges come from `deps` (`DAG-008`);
/// soft edges come from `weakDeps` (`DAG-009`). Producer-matching
/// edges come from the `outputs`/`inputs` intersection
/// (`DAG-013`). The function then rejects length-two-or-more
/// cycles in the union of all edge kinds (`DAG-014`) and
/// duplicate literal-output declarations (`DAG-015`).
///
/// # Errors
///
/// Returns [`BuildErrors`] containing every construction error
/// found across every task in the workspace per `DAG-011`. The
/// function does NOT short-circuit on the first error; a user
/// fixing a workspace expects every broken reference to surface
/// in one run.
pub fn build_task_graph(workspace: &Workspace) -> Result<(TaskGraph, Workspace), BuildErrors> {
    // DAG-001..DAG-006: overlay merging. The effective task set is
    // required by every downstream phase; a collision means
    // (P, n)'s body is undefined, so we cannot continue.
    let effective = match compute_effective_tasks(workspace) {
        Ok(effective) => effective,
        Err(overlay_errors) => {
            let errors = overlay_errors
                .into_inner()
                .into_iter()
                .map(|e| {
                    let OverlayMergeError::Collision {
                        project,
                        task,
                        sources,
                    } = e;
                    BuildError::OverlayCollision {
                        project,
                        task,
                        sources,
                    }
                })
                .collect();
            return Err(BuildErrors(errors));
        }
    };

    // Build an "effective workspace" where each project's `tasks`
    // is its effective task set (project tasks plus the bodies
    // contributed by attached overlays). All subsequent phases
    // (resolution, producer matching, output uniqueness) operate
    // on this view per `DAG-008`/`DAG-009`'s "post-overlay-merging"
    // qualifier.
    let workspace = apply_effective_tasks(workspace, &effective);

    let mut errors: Vec<BuildError> = Vec::new();
    let mut nodes: BTreeSet<TaskId> = BTreeSet::new();
    let mut edges: BTreeSet<Edge> = BTreeSet::new();

    for (project_name, project) in &workspace.projects {
        for task_name in project.tasks.keys() {
            let bearing_id = TaskId {
                project: project_name.clone(),
                task: task_name.clone(),
            };
            nodes.insert(bearing_id.clone());

            let task = &project.tasks[task_name];

            let hard_set = resolve_field(&task.deps, project, &workspace, &bearing_id, &mut errors);
            let soft_set = resolve_field(
                &task.weak_deps,
                project,
                &workspace,
                &bearing_id,
                &mut errors,
            );

            // DAG-010: a node listed (post-resolution) in BOTH
            // fields is rejected. Iterate the intersection in
            // canonical order (the sets are BTreeSets).
            for overlap_id in hard_set.intersection(&soft_set) {
                errors.push(BuildError::DepsWeakDepsOverlap {
                    bearing: bearing_id.clone(),
                    overlap: overlap_id.clone(),
                });
            }

            for source in &hard_set {
                edges.insert(Edge {
                    from: source.clone(),
                    to: bearing_id.clone(),
                    kind: EdgeKind::Hard,
                });
            }
            for source in &soft_set {
                edges.insert(Edge {
                    from: source.clone(),
                    to: bearing_id.clone(),
                    kind: EdgeKind::Soft,
                });
            }
        }
    }

    // DAG-013: merge in the producer-matching edges. They do
    // not produce errors; they are pure metadata derived from
    // declared `outputs`/`inputs` patterns.
    edges.extend(crate::producer::compute_producer_edges(&workspace));

    // DAG-014: reject simple cycles of length two or more in
    // the union edge set. Length-one cycles (formatter
    // producer-matching self-edges per DAG-013) are permitted.
    let provisional = TaskGraph {
        nodes: nodes.clone(),
        edges: edges.clone(),
    };
    for scc_nodes in crate::cycles::detect_cycles(&provisional) {
        errors.push(BuildError::Cycle { nodes: scc_nodes });
    }

    // DAG-015: literal outputs MUST be uniquely produced. Glob
    // outputs are deferred to runtime per DAG-016.
    for collision in crate::outputs::detect_literal_output_collisions(&workspace) {
        errors.push(BuildError::LiteralOutputCollision {
            path: collision.path,
            tasks: collision.tasks,
        });
    }

    if errors.is_empty() {
        Ok((TaskGraph { nodes, edges }, workspace))
    } else {
        Err(BuildErrors(errors))
    }
}

/// Construct a "shadow" workspace whose every project carries its
/// effective task set in place of its declared `tasks`.
///
/// Tag and root metadata are preserved verbatim. The original
/// workspace is left untouched. Subsequent phases of
/// [`build_task_graph`] are written against this view so the
/// "post-overlay-merging" qualifier in `DAG-008`/`DAG-009` becomes
/// a structural property of the input rather than a per-call-site
/// concern.
fn apply_effective_tasks(workspace: &Workspace, effective: &EffectiveTasksByProject) -> Workspace {
    let projects: BTreeMap<ProjectName, Project> = workspace
        .projects
        .iter()
        .map(|(name, project)| {
            let tasks: BTreeMap<TaskName, Task> = effective.get(name).cloned().unwrap_or_default();
            (
                name.clone(),
                Project {
                    name: project.name.clone(),
                    root: project.root.clone(),
                    tags: project.tags.clone(),
                    tasks,
                },
            )
        })
        .collect();
    Workspace {
        root: workspace.root.clone(),
        projects,
        overlays: workspace.overlays.clone(),
        settings: workspace.settings.clone(),
    }
}

/// Resolve every reference in `field_refs` against
/// `(bearing_project, workspace)`, accumulating successes into a
/// set and pushing failures into `errors`.
///
/// A successful resolution whose set contains the bearing itself
/// triggers a `DAG-012` self-reference error and contributes
/// NOTHING to the returned set (the whole reference is rejected).
/// Other successes are merged.
fn resolve_field(
    field_refs: &[TaskRef],
    bearing_project: &Project,
    workspace: &Workspace,
    bearing_id: &TaskId,
    errors: &mut Vec<BuildError>,
) -> BTreeSet<TaskId> {
    let mut result: BTreeSet<TaskId> = BTreeSet::new();
    for reference in field_refs {
        match resolve_task_ref(reference, bearing_project, workspace) {
            Ok(resolved) => {
                if resolved.contains(bearing_id) {
                    errors.push(BuildError::SelfReference {
                        bearing: bearing_id.clone(),
                        reference: reference.clone(),
                    });
                    continue;
                }
                result.extend(resolved);
            }
            Err(source) => {
                errors.push(BuildError::UnresolvedReference {
                    bearing: bearing_id.clone(),
                    reference: reference.clone(),
                    source,
                });
            }
        }
    }
    result
}

#[cfg(test)]
mod tests {
    use std::collections::{BTreeMap, BTreeSet};
    use std::path::PathBuf;
    use std::str::FromStr;

    use haz_domain::action::TaskAction;
    use haz_domain::env::EnvSettings;
    use haz_domain::name::{ProjectName, TagName, TaskName};
    use haz_domain::path::{CanonicalPath, HazPath, ProjectRoot, WorkspaceRootPath};
    use haz_domain::project::Project;
    use haz_domain::resolution::ResolutionError;
    use haz_domain::settings::WorkspaceSettings;
    use haz_domain::task::Task;
    use haz_domain::task_id::TaskId;
    use haz_domain::task_ref::TaskRef;
    use haz_domain::workspace::Workspace;
    use nonempty::NonEmpty;

    use crate::construction::{BuildError, build_task_graph};
    use crate::edge::{Edge, EdgeKind};
    use crate::effective::DefinitionSource;

    fn project_name(s: &str) -> ProjectName {
        ProjectName::from_str(s).unwrap()
    }
    fn tag_name(s: &str) -> TagName {
        TagName::from_str(s).unwrap()
    }
    fn task_name(s: &str) -> TaskName {
        TaskName::from_str(s).unwrap()
    }

    fn task_with(name: &str, deps: &[&str], weak_deps: &[&str]) -> Task {
        Task {
            name: task_name(name),
            action: TaskAction::Command(NonEmpty::from_vec(vec!["true".to_owned()]).unwrap()),
            inputs: vec![],
            outputs: vec![],
            deps: deps.iter().map(|r| TaskRef::parse(r).unwrap()).collect(),
            weak_deps: weak_deps
                .iter()
                .map(|r| TaskRef::parse(r).unwrap())
                .collect(),
            mutex: None,
            env: EnvSettings::default(),
        }
    }

    fn task_with_mutex(name: &str, mutex_name: &str) -> Task {
        use haz_domain::mutex::{Mutex, MutexMode, MutexScope};
        use haz_domain::name::MutexName;
        Task {
            name: task_name(name),
            action: TaskAction::Command(NonEmpty::from_vec(vec!["true".to_owned()]).unwrap()),
            inputs: vec![],
            outputs: vec![],
            deps: vec![],
            weak_deps: vec![],
            mutex: Some(Mutex {
                scope: MutexScope::Workspace,
                name: MutexName::from_str(mutex_name).unwrap(),
                mode: MutexMode::Exclusive,
            }),
            env: EnvSettings::default(),
        }
    }

    fn project_with(name: &str, root: &str, tags: &[&str], tasks: Vec<Task>) -> Project {
        Project {
            name: project_name(name),
            root: ProjectRoot::Nested(
                CanonicalPath::from_absolute(&HazPath::parse(root).unwrap()).unwrap(),
            ),
            tags: tags.iter().map(|t| tag_name(t)).collect(),
            tasks: tasks.into_iter().map(|t| (t.name.clone(), t)).collect(),
        }
    }

    fn workspace_with(projects: Vec<Project>) -> Workspace {
        let mut map = BTreeMap::new();
        for project in projects {
            map.insert(project.name.clone(), project);
        }
        Workspace {
            root: WorkspaceRootPath::try_new(PathBuf::from("/abs/ws")).unwrap(),
            projects: map,
            overlays: BTreeMap::new(),
            settings: WorkspaceSettings::default(),
        }
    }

    fn id(project: &str, task: &str) -> TaskId {
        TaskId {
            project: project_name(project),
            task: task_name(task),
        }
    }

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

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

    // DAG-007: node identity.

    #[test]
    fn dag_007_nodes_are_every_project_task_pair() {
        let p = project_with(
            "p",
            "/p",
            &[],
            vec![task_with("a", &[], &[]), task_with("b", &[], &[])],
        );
        let q = project_with("q", "/q", &[], vec![task_with("a", &[], &[])]);
        let workspace = workspace_with(vec![p, q]);

        let (graph, _) = build_task_graph(&workspace).unwrap();
        assert_eq!(
            graph.nodes,
            BTreeSet::from([id("p", "a"), id("p", "b"), id("q", "a")])
        );
        assert!(graph.edges.is_empty());
    }

    #[test]
    fn empty_workspace_is_empty_graph() {
        let workspace = workspace_with(vec![]);
        let (graph, _) = build_task_graph(&workspace).unwrap();
        assert!(graph.nodes.is_empty());
        assert!(graph.edges.is_empty());
    }

    // DAG-008: hard edges from `deps`.

    #[test]
    fn dag_008_same_project_dep_adds_one_hard_edge() {
        let p = project_with(
            "p",
            "/p",
            &[],
            vec![
                task_with("other", &[], &[]),
                task_with("bearing", &["~:other"], &[]),
            ],
        );
        let workspace = workspace_with(vec![p]);

        let (graph, _) = build_task_graph(&workspace).unwrap();
        assert_eq!(
            graph.edges,
            BTreeSet::from([hard(id("p", "other"), id("p", "bearing"))])
        );
    }

    #[test]
    fn dag_008_fan_out_dep_adds_hard_edges_to_every_matching_project() {
        let a = project_with("a", "/a", &[], vec![task_with("compile", &[], &[])]);
        let b = project_with("b", "/b", &[], vec![task_with("compile", &[], &[])]);
        let bearing = project_with(
            "z",
            "/z",
            &[],
            vec![task_with("build", &["^:compile"], &[])],
        );
        let workspace = workspace_with(vec![a, b, bearing]);

        let (graph, _) = build_task_graph(&workspace).unwrap();
        assert!(
            graph
                .edges
                .contains(&hard(id("a", "compile"), id("z", "build")))
        );
        assert!(
            graph
                .edges
                .contains(&hard(id("b", "compile"), id("z", "build")))
        );
        assert_eq!(
            graph
                .edges
                .iter()
                .filter(|e| e.kind == EdgeKind::Hard)
                .count(),
            2
        );
    }

    // DAG-009: soft edges from `weakDeps`.

    #[test]
    fn dag_009_same_project_weak_dep_adds_one_soft_edge() {
        let p = project_with(
            "p",
            "/p",
            &[],
            vec![
                task_with("gen", &[], &[]),
                task_with("build", &[], &["~:gen"]),
            ],
        );
        let workspace = workspace_with(vec![p]);

        let (graph, _) = build_task_graph(&workspace).unwrap();
        assert_eq!(
            graph.edges,
            BTreeSet::from([soft(id("p", "gen"), id("p", "build"))])
        );
    }

    #[test]
    fn deps_and_weak_deps_to_different_nodes_coexist() {
        let p = project_with(
            "p",
            "/p",
            &[],
            vec![
                task_with("compile", &[], &[]),
                task_with("gen", &[], &[]),
                task_with("build", &["~:compile"], &["~:gen"]),
            ],
        );
        let workspace = workspace_with(vec![p]);

        let (graph, _) = build_task_graph(&workspace).unwrap();
        assert!(
            graph
                .edges
                .contains(&hard(id("p", "compile"), id("p", "build")))
        );
        assert!(
            graph
                .edges
                .contains(&soft(id("p", "gen"), id("p", "build")))
        );
        assert_eq!(graph.edges.len(), 2);
    }

    // DAG-010: deps/weakDeps mutual exclusion.

    #[test]
    fn dag_010_same_node_in_deps_and_weak_deps_is_rejected() {
        let p = project_with(
            "p",
            "/p",
            &[],
            vec![
                task_with("other", &[], &[]),
                task_with("bearing", &["~:other"], &["~:other"]),
            ],
        );
        let workspace = workspace_with(vec![p]);

        let errors = build_task_graph(&workspace).unwrap_err();
        let bearing = id("p", "bearing");
        let other = id("p", "other");
        assert!(errors.as_slice().iter().any(|e| matches!(
            e,
            BuildError::DepsWeakDepsOverlap { bearing: b, overlap: o }
                if b == &bearing && o == &other
        )));
    }

    #[test]
    fn dag_010_overlap_detected_through_different_ref_forms() {
        // ^:compile in deps and p:compile in weakDeps both reach
        // (p, compile) in this workspace.
        let p = project_with(
            "p",
            "/p",
            &[],
            vec![
                task_with("compile", &[], &[]),
                task_with("bearing", &["^:compile"], &["p:compile"]),
            ],
        );
        let workspace = workspace_with(vec![p]);

        let errors = build_task_graph(&workspace).unwrap_err();
        assert!(errors.as_slice().iter().any(|e| matches!(
            e,
            BuildError::DepsWeakDepsOverlap { overlap, .. } if overlap == &id("p", "compile")
        )));
    }

    // DAG-011: error accumulation.

    #[test]
    fn dag_011_multiple_errors_across_multiple_tasks_are_all_reported() {
        let p = project_with(
            "p",
            "/p",
            &[],
            vec![
                task_with("a", &["~:ghost1"], &[]),
                task_with("b", &["~:ghost2"], &[]),
            ],
        );
        let q = project_with(
            "q",
            "/q",
            &[],
            vec![task_with("a", &["nonexistent:thing"], &[])],
        );
        let workspace = workspace_with(vec![p, q]);

        let errors = build_task_graph(&workspace).unwrap_err();
        assert_eq!(errors.len(), 3, "all three errors must be accumulated");

        let ghost1_seen = errors.as_slice().iter().any(|e| matches!(
            e,
            BuildError::UnresolvedReference { source: ResolutionError::BearingTaskNotFound { task }, .. }
                if task == &task_name("ghost1")
        ));
        let ghost2_seen = errors.as_slice().iter().any(|e| matches!(
            e,
            BuildError::UnresolvedReference { source: ResolutionError::BearingTaskNotFound { task }, .. }
                if task == &task_name("ghost2")
        ));
        let nonexistent_seen = errors.as_slice().iter().any(|e| matches!(
            e,
            BuildError::UnresolvedReference { source: ResolutionError::ProjectNotFound { project }, .. }
                if project == &project_name("nonexistent")
        ));
        assert!(ghost1_seen && ghost2_seen && nonexistent_seen);
    }

    // DAG-012: self-reference rejection.

    #[test]
    fn dag_012_same_project_self_reference_rejected() {
        let p = project_with("p", "/p", &[], vec![task_with("loop", &["~:loop"], &[])]);
        let workspace = workspace_with(vec![p]);

        let errors = build_task_graph(&workspace).unwrap_err();
        assert_eq!(errors.len(), 1);
        assert!(matches!(
            errors.as_slice()[0],
            BuildError::SelfReference { .. }
        ));
    }

    #[test]
    fn dag_012_project_ref_self_reference_rejected() {
        let p = project_with("p", "/p", &[], vec![task_with("loop", &["p:loop"], &[])]);
        let workspace = workspace_with(vec![p]);

        let errors = build_task_graph(&workspace).unwrap_err();
        assert!(matches!(
            errors.as_slice()[0],
            BuildError::SelfReference { .. }
        ));
    }

    #[test]
    fn dag_012_fan_out_self_reference_rejects_whole_reference() {
        // ^:compile in a task named `compile` resolves to a set
        // that includes the bearing. The WHOLE reference is
        // rejected: no Hard edge from the OTHER projects is
        // added either.
        let a = project_with("a", "/a", &[], vec![task_with("compile", &[], &[])]);
        let bearing = project_with(
            "z",
            "/z",
            &[],
            vec![task_with("compile", &["^:compile"], &[])],
        );
        let workspace = workspace_with(vec![a, bearing]);

        let errors = build_task_graph(&workspace).unwrap_err();
        assert!(
            errors
                .as_slice()
                .iter()
                .any(|e| matches!(e, BuildError::SelfReference { .. }))
        );
    }

    #[test]
    fn mutex_009_shared_mutex_adds_no_edges_between_declaring_tasks() {
        // MUTEX-009: two tasks declaring the same exclusive mutex
        // create only a runtime scheduling constraint, NOT an edge
        // in the task graph. Building the graph for two such tasks
        // (no deps, no shared inputs/outputs, no producer matching)
        // MUST yield zero edges; the cycle detector's union graph
        // therefore cannot mistake the shared mutex for a cycle.
        let p = project_with(
            "p",
            "/p",
            &[],
            vec![task_with_mutex("a", "db"), task_with_mutex("b", "db")],
        );
        let workspace = workspace_with(vec![p]);

        let (graph, _) = build_task_graph(&workspace).unwrap();
        assert_eq!(graph.nodes.len(), 2);
        assert!(
            graph.edges.is_empty(),
            "MUTEX-009: mutex declarations MUST NOT introduce edges; \
             got {:?}",
            graph.edges,
        );
        assert!(
            crate::cycles::detect_cycles(&graph).is_empty(),
            "MUTEX-009: shared mutex MUST NOT register as a DAG-014 cycle",
        );
    }

    #[test]
    fn mutex_009_cross_project_shared_mutex_adds_no_edges() {
        // MUTEX-009: same property at workspace scope across two
        // projects. The mutex is workspace-global so the runtime
        // constraint applies cross-project, but the graph still
        // contains zero edges between the two declaring nodes.
        let a = project_with("a", "/a", &[], vec![task_with_mutex("migrate", "db")]);
        let b = project_with("b", "/b", &[], vec![task_with_mutex("migrate", "db")]);
        let workspace = workspace_with(vec![a, b]);

        let (graph, _) = build_task_graph(&workspace).unwrap();
        assert_eq!(graph.nodes.len(), 2);
        assert!(
            graph.edges.is_empty(),
            "MUTEX-009: cross-project shared mutex MUST NOT add edges; \
             got {:?}",
            graph.edges,
        );
        assert!(crate::cycles::detect_cycles(&graph).is_empty());
    }

    #[test]
    fn dag_012_sibling_fan_out_does_not_trigger_self_reference() {
        // ^~:compile in a `compile` task excludes the bearing by
        // construction and is therefore legitimate.
        let a = project_with("a", "/a", &[], vec![task_with("compile", &[], &[])]);
        let bearing = project_with(
            "z",
            "/z",
            &[],
            vec![task_with("compile", &["^~:compile"], &[])],
        );
        let workspace = workspace_with(vec![a, bearing]);

        let (graph, _) = build_task_graph(&workspace).unwrap();
        assert!(
            graph
                .edges
                .contains(&hard(id("a", "compile"), id("z", "compile")))
        );
        assert_eq!(graph.edges.len(), 1);
    }

    #[test]
    fn dag_012_tag_self_reference_rejected() {
        let a = project_with("a", "/a", &["t"], vec![task_with("compile", &[], &[])]);
        let bearing = project_with(
            "z",
            "/z",
            &["t"],
            vec![task_with("compile", &["[t]:compile"], &[])],
        );
        let workspace = workspace_with(vec![a, bearing]);

        let errors = build_task_graph(&workspace).unwrap_err();
        assert!(
            errors
                .as_slice()
                .iter()
                .any(|e| matches!(e, BuildError::SelfReference { .. }))
        );
    }

    // Stability: error order is deterministic (BTreeMap-driven).

    #[test]
    fn errors_appear_in_project_then_task_order() {
        let p = project_with(
            "p",
            "/p",
            &[],
            vec![
                task_with("a", &["~:ghost"], &[]),
                task_with("b", &["~:ghost"], &[]),
            ],
        );
        let q = project_with("q", "/q", &[], vec![task_with("a", &["~:ghost"], &[])]);
        let workspace = workspace_with(vec![p, q]);

        let errors = build_task_graph(&workspace).unwrap_err();
        let bearings: Vec<TaskId> = errors
            .as_slice()
            .iter()
            .map(|e| match e {
                BuildError::UnresolvedReference { bearing, .. }
                | BuildError::SelfReference { bearing, .. }
                | BuildError::DepsWeakDepsOverlap { bearing, .. } => bearing.clone(),
                BuildError::Cycle { .. }
                | BuildError::LiteralOutputCollision { .. }
                | BuildError::OverlayCollision { .. } => {
                    unreachable!("no cycle/collision/overlay errors in this workspace")
                }
            })
            .collect();
        assert_eq!(bearings, vec![id("p", "a"), id("p", "b"), id("q", "a")]);
    }

    // BuildErrors display rendering.

    #[test]
    fn build_errors_display_renders_count_and_list() {
        let p = project_with("p", "/p", &[], vec![task_with("a", &["~:loop_self"], &[])]);
        let workspace = workspace_with(vec![p]);
        let errors = build_task_graph(&workspace).unwrap_err();
        let rendered = errors.to_string();
        assert!(rendered.starts_with("1 error(s) during DAG construction:"));
        assert!(rendered.contains("1. "));
    }

    // DAG-014: cycle rejection in the union edge set.

    #[test]
    fn dag_014_mutual_hard_deps_form_a_cycle() {
        let p = project_with(
            "p",
            "/p",
            &[],
            vec![task_with("a", &["~:b"], &[]), task_with("b", &["~:a"], &[])],
        );
        let workspace = workspace_with(vec![p]);
        let errors = build_task_graph(&workspace).unwrap_err();

        let cycle_seen = errors.as_slice().iter().any(|e| {
            matches!(
                e,
                BuildError::Cycle { nodes }
                    if nodes == &BTreeSet::from([id("p", "a"), id("p", "b")])
            )
        });
        assert!(cycle_seen, "expected a Cycle error covering {{a, b}}");
    }

    #[test]
    fn dag_014_three_task_cycle_is_detected() {
        let p = project_with(
            "p",
            "/p",
            &[],
            vec![
                task_with("a", &["~:b"], &[]),
                task_with("b", &["~:c"], &[]),
                task_with("c", &["~:a"], &[]),
            ],
        );
        let workspace = workspace_with(vec![p]);
        let errors = build_task_graph(&workspace).unwrap_err();
        let cycle_seen = errors.as_slice().iter().any(|e| {
            matches!(
                e,
                BuildError::Cycle { nodes }
                    if nodes == &BTreeSet::from([id("p", "a"), id("p", "b"), id("p", "c")])
            )
        });
        assert!(cycle_seen);
    }

    #[test]
    fn dag_014_cycle_through_hard_and_soft_is_detected() {
        // A's deps depends on B, B's weakDeps depends on A.
        let p = project_with(
            "p",
            "/p",
            &[],
            vec![task_with("a", &["~:b"], &[]), task_with("b", &[], &["~:a"])],
        );
        let workspace = workspace_with(vec![p]);
        let errors = build_task_graph(&workspace).unwrap_err();
        assert!(
            errors
                .as_slice()
                .iter()
                .any(|e| matches!(e, BuildError::Cycle { .. }))
        );
    }

    #[test]
    fn dag_014_acyclic_workspace_succeeds() {
        let p = project_with(
            "p",
            "/p",
            &[],
            vec![
                task_with("a", &[], &[]),
                task_with("b", &["~:a"], &[]),
                task_with("c", &["~:b"], &[]),
            ],
        );
        let workspace = workspace_with(vec![p]);
        let (graph, _) = build_task_graph(&workspace).unwrap();
        assert_eq!(graph.nodes.len(), 3);
        // a -> b, b -> c
        assert!(graph.edges.contains(&hard(id("p", "a"), id("p", "b"))));
        assert!(graph.edges.contains(&hard(id("p", "b"), id("p", "c"))));
    }

    // DAG-015: literal-output uniqueness.

    #[test]
    fn dag_015_two_tasks_same_literal_output_is_rejected() {
        use haz_domain::path::OutputSpec;

        // Hand-build tasks with conflicting outputs (the
        // task_with helper above doesn't take outputs; build
        // by struct literal here).
        let mut p_tasks = std::collections::BTreeMap::new();
        let task_a = Task {
            name: task_name("a"),
            action: TaskAction::Command(NonEmpty::from_vec(vec!["true".to_owned()]).unwrap()),
            inputs: vec![],
            outputs: vec![OutputSpec::parse("dist/main.js").unwrap()],
            deps: vec![],
            weak_deps: vec![],
            mutex: None,
            env: EnvSettings::default(),
        };
        let task_b = Task {
            name: task_name("b"),
            action: TaskAction::Command(NonEmpty::from_vec(vec!["true".to_owned()]).unwrap()),
            inputs: vec![],
            outputs: vec![OutputSpec::parse("dist/main.js").unwrap()],
            deps: vec![],
            weak_deps: vec![],
            mutex: None,
            env: EnvSettings::default(),
        };
        p_tasks.insert(task_a.name.clone(), task_a);
        p_tasks.insert(task_b.name.clone(), task_b);

        let p = Project {
            name: project_name("p"),
            root: haz_domain::path::ProjectRoot::Nested(
                haz_domain::path::CanonicalPath::from_absolute(
                    &haz_domain::path::HazPath::parse("/p").unwrap(),
                )
                .unwrap(),
            ),
            tags: BTreeSet::new(),
            tasks: p_tasks,
        };
        let workspace = workspace_with(vec![p]);

        let errors = build_task_graph(&workspace).unwrap_err();
        let collision_seen = errors.as_slice().iter().any(|e| {
            matches!(
                e,
                BuildError::LiteralOutputCollision { path, tasks }
                    if path == "/p/dist/main.js"
                        && tasks == &BTreeSet::from([id("p", "a"), id("p", "b")])
            )
        });
        assert!(collision_seen);
    }

    // DAG-001..DAG-006: overlay merging end-to-end via
    // `build_task_graph`.

    fn overlay_name(s: &str) -> haz_domain::name::OverlayName {
        haz_domain::name::OverlayName::from_str(s).unwrap()
    }

    fn overlay_with(
        name: &str,
        matched_projects: &[&str],
        tasks: Vec<Task>,
    ) -> haz_domain::overlay::Overlay {
        haz_domain::overlay::Overlay {
            name: overlay_name(name),
            matched_projects: matched_projects.iter().map(|p| project_name(p)).collect(),
            tasks: tasks.into_iter().map(|t| (t.name.clone(), t)).collect(),
        }
    }

    fn workspace_with_overlays(
        projects: Vec<Project>,
        overlays: Vec<haz_domain::overlay::Overlay>,
    ) -> Workspace {
        Workspace {
            root: WorkspaceRootPath::try_new(PathBuf::from("/abs/ws")).unwrap(),
            projects: projects.into_iter().map(|p| (p.name.clone(), p)).collect(),
            overlays: overlays.into_iter().map(|o| (o.name.clone(), o)).collect(),
            settings: WorkspaceSettings::default(),
        }
    }

    // DAG-001 + DAG-007: an overlay-attached task becomes a node
    // in the graph.

    #[test]
    fn overlay_attached_task_appears_as_a_node() {
        let p = project_with("p", "/p", &[], vec![task_with("build", &[], &[])]);
        let lint = overlay_with("lint", &["p"], vec![task_with("lint", &[], &[])]);
        let workspace = workspace_with_overlays(vec![p], vec![lint]);

        let (graph, _) = build_task_graph(&workspace).unwrap();
        assert!(graph.nodes.contains(&id("p", "build")));
        assert!(graph.nodes.contains(&id("p", "lint")));
        assert_eq!(graph.nodes.len(), 2);
    }

    // DAG-008 post-overlay: an overlay's task body declares `deps`
    // resolved against the EFFECTIVE task set of the bearing
    // project. The reference `~:build` refers to the project's
    // own `build`; the resulting hard edge attaches to the
    // overlay-contributed node.

    #[test]
    fn overlay_task_with_dep_on_project_task_emits_hard_edge() {
        let p = project_with("p", "/p", &[], vec![task_with("build", &[], &[])]);
        let lint = overlay_with("lint", &["p"], vec![task_with("lint", &["~:build"], &[])]);
        let workspace = workspace_with_overlays(vec![p], vec![lint]);

        let (graph, _) = build_task_graph(&workspace).unwrap();
        assert!(
            graph
                .edges
                .contains(&hard(id("p", "build"), id("p", "lint")))
        );
        assert_eq!(graph.edges.len(), 1);
    }

    // A project task can reference an overlay-contributed task
    // because resolution sees the effective task set.

    #[test]
    fn project_task_can_reference_overlay_contributed_sibling() {
        let p = project_with("p", "/p", &[], vec![task_with("build", &["~:lint"], &[])]);
        let lint = overlay_with("lint", &["p"], vec![task_with("lint", &[], &[])]);
        let workspace = workspace_with_overlays(vec![p], vec![lint]);

        let (graph, _) = build_task_graph(&workspace).unwrap();
        assert!(
            graph
                .edges
                .contains(&hard(id("p", "lint"), id("p", "build")))
        );
    }

    // DAG-006: an overlay-merge collision propagates as
    // `BuildError::OverlayCollision` carrying every contributing
    // overlay.

    #[test]
    fn dag_006_overlay_collision_propagates_as_build_error() {
        let p = project_with("p", "/p", &[], vec![]);
        let q = project_with("q", "/q", &[], vec![]);
        let r = project_with("r", "/r", &[], vec![]);
        let pq = overlay_with("pq", &["p", "q"], vec![task_with("lint", &[], &[])]);
        let pr = overlay_with("pr", &["p", "r"], vec![task_with("lint", &[], &[])]);
        let workspace = workspace_with_overlays(vec![p, q, r], vec![pq, pr]);

        let errors = build_task_graph(&workspace).unwrap_err();
        let collision_seen = errors.as_slice().iter().any(|e| {
            matches!(
                e,
                BuildError::OverlayCollision { project, task, sources }
                    if project == &project_name("p")
                        && task == &task_name("lint")
                        && sources.contains(&DefinitionSource::Overlay { name: overlay_name("pq") })
                        && sources.contains(&DefinitionSource::Overlay { name: overlay_name("pr") })
            )
        });
        assert!(
            collision_seen,
            "expected `OverlayCollision` carrying both overlays as sources"
        );
    }

    // Overlay-merge errors short-circuit downstream phases:
    // resolution, cycles, output collisions are not surfaced in
    // the same run.

    #[test]
    fn overlay_collision_short_circuits_downstream_phases() {
        let p = project_with("p", "/p", &[], vec![task_with("a", &["~:ghost"], &[])]);
        let q = project_with("q", "/q", &[], vec![]);
        let pq = overlay_with("pq", &["p", "q"], vec![task_with("lint", &[], &[])]);
        let qp = overlay_with("qp", &["p", "q"], vec![task_with("lint", &[], &[])]);
        let workspace = workspace_with_overlays(vec![p, q], vec![pq, qp]);

        let errors = build_task_graph(&workspace).unwrap_err();
        assert!(
            errors
                .as_slice()
                .iter()
                .all(|e| matches!(e, BuildError::OverlayCollision { .. })),
            "downstream errors must NOT surface alongside overlay collisions"
        );
    }

    // DAG-015 post-overlay: a literal output declared by an
    // overlay-attached task collides with a project-level
    // declaration on the same path.

    #[test]
    fn overlay_output_collides_with_project_literal_output() {
        use haz_domain::path::OutputSpec;

        let task_a = Task {
            name: task_name("a"),
            action: TaskAction::Command(NonEmpty::from_vec(vec!["true".to_owned()]).unwrap()),
            inputs: vec![],
            outputs: vec![OutputSpec::parse("dist/main.js").unwrap()],
            deps: vec![],
            weak_deps: vec![],
            mutex: None,
            env: EnvSettings::default(),
        };
        let p = Project {
            name: project_name("p"),
            root: haz_domain::path::ProjectRoot::Nested(
                haz_domain::path::CanonicalPath::from_absolute(
                    &haz_domain::path::HazPath::parse("/p").unwrap(),
                )
                .unwrap(),
            ),
            tags: BTreeSet::new(),
            tasks: BTreeMap::from([(task_a.name.clone(), task_a)]),
        };

        let task_b = Task {
            name: task_name("b"),
            action: TaskAction::Command(NonEmpty::from_vec(vec!["true".to_owned()]).unwrap()),
            inputs: vec![],
            outputs: vec![OutputSpec::parse("dist/main.js").unwrap()],
            deps: vec![],
            weak_deps: vec![],
            mutex: None,
            env: EnvSettings::default(),
        };
        let lint = haz_domain::overlay::Overlay {
            name: overlay_name("lint"),
            matched_projects: BTreeSet::from([project_name("p")]),
            tasks: BTreeMap::from([(task_b.name.clone(), task_b)]),
        };
        let workspace = workspace_with_overlays(vec![p], vec![lint]);

        let errors = build_task_graph(&workspace).unwrap_err();
        let collision_seen = errors.as_slice().iter().any(|e| {
            matches!(
                e,
                BuildError::LiteralOutputCollision { path, tasks }
                    if path == "/p/dist/main.js"
                        && tasks == &BTreeSet::from([id("p", "a"), id("p", "b")])
            )
        });
        assert!(
            collision_seen,
            "DAG-015 must see overlay-contributed outputs"
        );
    }
}