haz-dag 0.1.0

//! [`compute_producer_edges`]: the `DAG-013` producer-matching
//! relation expressed as `EdgeKind::ProducerMatching` edges,
//! plus [`producers_of_path`]: the per-path query `AUX-015`
//! step 3 needs to annotate `haz why` input lines.
//!
//! A producer-matching edge `(Q, B) -> (P, A)` is added whenever
//! task `B`'s declared `outputs` and task `A`'s declared `inputs`
//! share at least one workspace-rooted path. The relation
//! includes self-edges per `DAG-013`: a task whose own outputs
//! and inputs intersect is its own producer (the canonical
//! "code formatter" case in the spec).
//!
//! # Statically vs runtime decidable
//!
//! Of the four output/input combinations, three are statically
//! decidable and one is not:
//!
//! | output  | input   | static decision                     |
//! |---------|---------|-------------------------------------|
//! | literal | literal | byte-equal workspace-absolute paths |
//! | literal | glob    | the glob matches the literal        |
//! | glob    | literal | the glob matches the literal        |
//! | glob    | glob    | NOT decidable; no edge added        |
//!
//! The glob/glob case escapes static analysis without filesystem
//! state. Under-detection is safe for downstream `DAG-014` cycle
//! detection (a false negative does not reject a valid
//! workspace); over-detection would. The runtime executor will
//! observe the actual intersection when files exist.

use std::collections::BTreeSet;

use haz_domain::path::{PathAnchor, PathPattern, ProjectRoot};
use haz_domain::task::Task;
use haz_domain::task_id::TaskId;
use haz_domain::workspace::Workspace;

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

/// Compute every producer-matching edge in `workspace` per
/// `DAG-013`.
///
/// The set is closed under self-edges: a task whose own outputs
/// intersect its own inputs yields an edge `(P, A) -> (P, A)`.
///
/// Worst-case cost is
/// `O(|tasks|^2 * |outputs_per_task| * |inputs_per_task|)`. Tasks
/// with empty `outputs` or empty `inputs` contribute nothing.
#[must_use]
pub fn compute_producer_edges(workspace: &Workspace) -> BTreeSet<Edge> {
    let mut edges: BTreeSet<Edge> = BTreeSet::new();

    for (producer_proj_name, producer_proj) in &workspace.projects {
        for (producer_task_name, producer_task) in &producer_proj.tasks {
            if producer_task.outputs.is_empty() {
                continue;
            }
            let producer_id = TaskId {
                project: producer_proj_name.clone(),
                task: producer_task_name.clone(),
            };

            for (consumer_proj_name, consumer_proj) in &workspace.projects {
                for (consumer_task_name, consumer_task) in &consumer_proj.tasks {
                    if consumer_task.inputs.is_empty() {
                        continue;
                    }
                    if task_pair_produces_match(
                        producer_task,
                        &producer_proj.root,
                        consumer_task,
                        &consumer_proj.root,
                    ) {
                        edges.insert(Edge {
                            from: producer_id.clone(),
                            to: TaskId {
                                project: consumer_proj_name.clone(),
                                task: consumer_task_name.clone(),
                            },
                            kind: EdgeKind::ProducerMatching,
                        });
                    }
                }
            }
        }
    }

    edges
}

/// Producers of `workspace_absolute_path` per `DAG-013`'s
/// statically-decidable arms.
///
/// Walks every task's `outputs` and returns the set of [`TaskId`]s
/// whose patterns match the given path. Used by `haz why` to
/// annotate each materialised input path per `AUX-015` step 3:
///
/// - Zero matches: no annotation.
/// - Exactly one match: `(produced by <project>:<task>)`.
/// - Two or more matches: `(producer: undetermined)`.
///
/// The path argument is the workspace-absolute string form,
/// matching the shape returned by
/// `haz_exec::cache_key::resolve_input_files`.
#[must_use]
pub fn producers_of_path(workspace: &Workspace, workspace_absolute_path: &str) -> BTreeSet<TaskId> {
    let mut producers: BTreeSet<TaskId> = BTreeSet::new();
    for (project_name, project) in &workspace.projects {
        for (task_name, task) in &project.tasks {
            if task_produces_path(task, &project.root, workspace_absolute_path) {
                producers.insert(TaskId {
                    project: project_name.clone(),
                    task: task_name.clone(),
                });
            }
        }
    }
    producers
}

/// `true` if any of `task`'s `outputs` patterns matches
/// `path_str` (workspace-absolute) under `project_root`.
fn task_produces_path(task: &Task, project_root: &ProjectRoot, path_str: &str) -> bool {
    for output in &task.outputs {
        let pattern = output.pattern();
        let pattern_str = anchor_to_workspace_absolute(pattern, project_root);
        let matched = if pattern.is_literal() {
            pattern_str == path_str
        } else {
            glob_matches(&pattern_str, path_str)
        };
        if matched {
            return true;
        }
    }
    false
}

/// `true` if any pair of (producer.output, consumer.input) is a
/// statically-decidable match.
fn task_pair_produces_match(
    producer: &Task,
    producer_root: &ProjectRoot,
    consumer: &Task,
    consumer_root: &ProjectRoot,
) -> bool {
    for output in &producer.outputs {
        for input in &consumer.inputs {
            if pattern_pair_matches(
                output.pattern(),
                producer_root,
                input.pattern(),
                consumer_root,
            ) {
                return true;
            }
        }
    }
    false
}

fn pattern_pair_matches(
    output: &PathPattern,
    output_root: &ProjectRoot,
    input: &PathPattern,
    input_root: &ProjectRoot,
) -> bool {
    let output_str = anchor_to_workspace_absolute(output, output_root);
    let input_str = anchor_to_workspace_absolute(input, input_root);

    match (output.is_literal(), input.is_literal()) {
        (true, true) => output_str == input_str,
        (true, false) => glob_matches(&input_str, &output_str),
        (false, true) => glob_matches(&output_str, &input_str),
        // DAG-013 + DAG-014: glob-vs-glob is not statically
        // decidable without filesystem state.
        (false, false) => false,
    }
}

/// Render `pattern` as the workspace-absolute string it
/// represents under `project_root`.
///
/// Shared across crates that need the same canonicalisation for
/// pattern comparison: `crate::outputs` (DAG-015) for literal-
/// output collision detection, and `haz-query`'s engine for
/// `--inputs` / `--outputs` intersection (QRY-003).
#[must_use]
pub fn anchor_to_workspace_absolute(pattern: &PathPattern, project_root: &ProjectRoot) -> String {
    match pattern.anchor() {
        PathAnchor::WorkspaceAbsolute => pattern.to_string(),
        PathAnchor::ProjectRelative => {
            let prefix = match project_root {
                ProjectRoot::WorkspaceRoot => String::new(),
                ProjectRoot::Nested(c) => c.to_string(),
            };
            format!("{prefix}/{pattern}")
        }
    }
}

/// `true` if the glob pattern `glob_str` (workspace-absolute)
/// matches the literal path `literal_str` (workspace-absolute).
///
/// The builder configuration mirrors `PathPattern::parse` so
/// matching semantics are identical to construction-time
/// validation.
fn glob_matches(glob_str: &str, literal_str: &str) -> bool {
    let Ok(glob) = globset::GlobBuilder::new(glob_str)
        .literal_separator(true)
        .case_insensitive(false)
        .build()
    else {
        // Validation at PathPattern::parse should have caught this;
        // tolerate it defensively rather than panicking.
        return false;
    };
    glob.compile_matcher().is_match(literal_str)
}

#[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, TaskName};
    use haz_domain::path::{
        CanonicalPath, HazPath, InputSpec, OutputSpec, ProjectRoot, WorkspaceRootPath,
    };
    use haz_domain::project::Project;
    use haz_domain::settings::WorkspaceSettings;
    use haz_domain::task::Task;
    use haz_domain::task_id::TaskId;
    use haz_domain::workspace::Workspace;
    use nonempty::NonEmpty;

    use crate::edge::{Edge, EdgeKind};
    use crate::producer::compute_producer_edges;

    fn project_name(s: &str) -> ProjectName {
        ProjectName::from_str(s).unwrap()
    }
    fn task_name(s: &str) -> TaskName {
        TaskName::from_str(s).unwrap()
    }
    fn nested_root(path: &str) -> ProjectRoot {
        ProjectRoot::Nested(CanonicalPath::from_absolute(&HazPath::parse(path).unwrap()).unwrap())
    }
    fn input(s: &str) -> InputSpec {
        InputSpec::parse(s).unwrap()
    }
    fn output(s: &str) -> OutputSpec {
        OutputSpec::parse(s).unwrap()
    }

    fn task_with(name: &str, inputs: Vec<InputSpec>, outputs: Vec<OutputSpec>) -> Task {
        Task {
            name: task_name(name),
            action: TaskAction::Command(NonEmpty::from_vec(vec!["true".to_owned()]).unwrap()),
            inputs,
            outputs,
            deps: vec![],
            weak_deps: vec![],
            mutex: None,
            env: EnvSettings::default(),
        }
    }

    fn project_with(name: &str, root: ProjectRoot, tasks: Vec<Task>) -> Project {
        Project {
            name: project_name(name),
            root,
            tags: BTreeSet::new(),
            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 producer_edge(from: TaskId, to: TaskId) -> Edge {
        Edge {
            from,
            to,
            kind: EdgeKind::ProducerMatching,
        }
    }

    // Literal vs literal: byte-equal workspace-absolute paths.

    #[test]
    fn dag_013_literal_output_matches_identical_literal_input_same_project() {
        let p = project_with(
            "p",
            nested_root("/p"),
            vec![
                task_with("gen", vec![], vec![output("dist/main.js")]),
                task_with("use", vec![input("dist/main.js")], vec![]),
            ],
        );
        let workspace = workspace_with(vec![p]);

        let edges = compute_producer_edges(&workspace);
        assert_eq!(
            edges,
            BTreeSet::from([producer_edge(id("p", "gen"), id("p", "use"))])
        );
    }

    #[test]
    fn dag_013_literal_output_does_not_match_different_literal_input() {
        let p = project_with(
            "p",
            nested_root("/p"),
            vec![
                task_with("gen", vec![], vec![output("dist/main.js")]),
                task_with("use", vec![input("dist/other.js")], vec![]),
            ],
        );
        let workspace = workspace_with(vec![p]);

        assert!(compute_producer_edges(&workspace).is_empty());
    }

    // Literal vs glob (and the symmetric form).

    #[test]
    fn dag_013_literal_output_matches_glob_input() {
        let p = project_with(
            "p",
            nested_root("/p"),
            vec![
                task_with("gen", vec![], vec![output("dist/main.js")]),
                task_with("use", vec![input("dist/*.js")], vec![]),
            ],
        );
        let workspace = workspace_with(vec![p]);

        let edges = compute_producer_edges(&workspace);
        assert!(edges.contains(&producer_edge(id("p", "gen"), id("p", "use"))));
    }

    #[test]
    fn dag_013_glob_output_matches_literal_input() {
        let p = project_with(
            "p",
            nested_root("/p"),
            vec![
                task_with("gen", vec![], vec![output("dist/*.js")]),
                task_with("use", vec![input("dist/main.js")], vec![]),
            ],
        );
        let workspace = workspace_with(vec![p]);

        let edges = compute_producer_edges(&workspace);
        assert!(edges.contains(&producer_edge(id("p", "gen"), id("p", "use"))));
    }

    #[test]
    fn dag_013_glob_does_not_match_literal_outside_its_set() {
        let p = project_with(
            "p",
            nested_root("/p"),
            vec![
                task_with("gen", vec![], vec![output("dist/*.js")]),
                task_with("use", vec![input("other/main.js")], vec![]),
            ],
        );
        let workspace = workspace_with(vec![p]);

        assert!(compute_producer_edges(&workspace).is_empty());
    }

    // Glob vs glob: not statically decidable -> no edge.

    #[test]
    fn dag_013_glob_output_does_not_match_glob_input_statically() {
        let p = project_with(
            "p",
            nested_root("/p"),
            vec![
                task_with("gen", vec![], vec![output("dist/*.js")]),
                task_with("use", vec![input("dist/**/*.js")], vec![]),
            ],
        );
        let workspace = workspace_with(vec![p]);

        // Per DAG-013/014, glob-vs-glob escapes static analysis.
        assert!(compute_producer_edges(&workspace).is_empty());
    }

    // DAG-013 self-edge: formatter / auto-fixer.

    #[test]
    fn dag_013_formatter_self_edge_when_outputs_and_inputs_intersect() {
        let p = project_with(
            "p",
            nested_root("/p"),
            vec![task_with(
                "format",
                vec![input("src/**/*.rs")],
                vec![output("src/**/*.rs")],
            )],
        );
        let workspace = workspace_with(vec![p]);

        // glob-vs-glob is undecidable, so no self-edge here.
        assert!(compute_producer_edges(&workspace).is_empty());
    }

    #[test]
    fn dag_013_formatter_self_edge_when_literal_output_matches_glob_input() {
        // The decidable side of DAG-013 self-edges: a literal on
        // one side and a glob on the other.
        let p = project_with(
            "p",
            nested_root("/p"),
            vec![task_with(
                "fix_lib",
                vec![input("src/*.rs")],
                vec![output("src/lib.rs")],
            )],
        );
        let workspace = workspace_with(vec![p]);

        let edges = compute_producer_edges(&workspace);
        assert_eq!(
            edges,
            BTreeSet::from([producer_edge(id("p", "fix_lib"), id("p", "fix_lib"))])
        );
    }

    // Cross-project: producer in one project, consumer in another.

    #[test]
    fn dag_013_cross_project_match_uses_workspace_absolute_anchoring() {
        let producer_proj = project_with(
            "gen_pkg",
            nested_root("/gen_pkg"),
            vec![task_with("emit", vec![], vec![output("dist/api.js")])],
        );
        let consumer_proj = project_with(
            "web",
            nested_root("/web"),
            vec![task_with(
                "build",
                vec![input("/gen_pkg/dist/api.js")],
                vec![],
            )],
        );
        let workspace = workspace_with(vec![producer_proj, consumer_proj]);

        let edges = compute_producer_edges(&workspace);
        assert_eq!(
            edges,
            BTreeSet::from([producer_edge(id("gen_pkg", "emit"), id("web", "build"))])
        );
    }

    #[test]
    fn workspace_absolute_glob_consumer_matches_relative_producer_output() {
        let producer_proj = project_with(
            "lib_a",
            nested_root("/lib_a"),
            vec![task_with("gen", vec![], vec![output("out/v1.json")])],
        );
        let consumer_proj = project_with(
            "lib_b",
            nested_root("/lib_b"),
            vec![task_with("use", vec![input("/lib_a/out/*.json")], vec![])],
        );
        let workspace = workspace_with(vec![producer_proj, consumer_proj]);

        let edges = compute_producer_edges(&workspace);
        assert_eq!(
            edges,
            BTreeSet::from([producer_edge(id("lib_a", "gen"), id("lib_b", "use"))])
        );
    }

    // Implicit-mode project root (ProjectRoot::WorkspaceRoot).

    #[test]
    fn implicit_project_root_anchors_relative_pattern_at_workspace_root() {
        let p = project_with(
            "root_proj",
            ProjectRoot::WorkspaceRoot,
            vec![
                task_with("gen", vec![], vec![output("build/main.o")]),
                task_with("link", vec![input("/build/main.o")], vec![]),
            ],
        );
        let workspace = workspace_with(vec![p]);

        let edges = compute_producer_edges(&workspace);
        assert_eq!(
            edges,
            BTreeSet::from([producer_edge(
                id("root_proj", "gen"),
                id("root_proj", "link")
            )])
        );
    }

    // Empty workspace, empty task fields.

    #[test]
    fn empty_workspace_has_no_edges() {
        let workspace = workspace_with(vec![]);
        assert!(compute_producer_edges(&workspace).is_empty());
    }

    // ---- producers_of_path: AUX-015 step 3 ----

    use crate::producer::producers_of_path;

    #[test]
    fn producers_of_path_returns_empty_when_no_task_outputs_match() {
        let p = project_with(
            "lib",
            nested_root("/lib"),
            vec![task_with("gen", vec![], vec![output("dist/main.js")])],
        );
        let workspace = workspace_with(vec![p]);
        let producers = producers_of_path(&workspace, "/lib/dist/other.js");
        assert!(producers.is_empty());
    }

    #[test]
    fn producers_of_path_returns_single_producer_for_literal_match() {
        let p = project_with(
            "lib",
            nested_root("/lib"),
            vec![task_with("gen", vec![], vec![output("dist/main.js")])],
        );
        let workspace = workspace_with(vec![p]);
        let producers = producers_of_path(&workspace, "/lib/dist/main.js");
        assert_eq!(producers, BTreeSet::from([id("lib", "gen")]));
    }

    #[test]
    fn producers_of_path_returns_single_producer_for_glob_match() {
        let p = project_with(
            "lib",
            nested_root("/lib"),
            vec![task_with("gen", vec![], vec![output("dist/*.js")])],
        );
        let workspace = workspace_with(vec![p]);
        let producers = producers_of_path(&workspace, "/lib/dist/anything.js");
        assert_eq!(producers, BTreeSet::from([id("lib", "gen")]));
    }

    #[test]
    fn producers_of_path_returns_multiple_producers_when_outputs_overlap() {
        // Two tasks declare overlapping output patterns; both
        // produce the same materialised path. `AUX-015` step 3
        // requires the `(producer: undetermined)` annotation in
        // this case.
        let p = project_with(
            "lib",
            nested_root("/lib"),
            vec![
                task_with("gen_lit", vec![], vec![output("dist/api.js")]),
                task_with("gen_glob", vec![], vec![output("dist/*.js")]),
            ],
        );
        let workspace = workspace_with(vec![p]);
        let producers = producers_of_path(&workspace, "/lib/dist/api.js");
        assert_eq!(
            producers,
            BTreeSet::from([id("lib", "gen_lit"), id("lib", "gen_glob")]),
        );
    }

    #[test]
    fn producers_of_path_uses_workspace_absolute_anchoring_across_projects() {
        // Producer is in project `gen_pkg`, but the consumer
        // names the path as `/gen_pkg/dist/api.js`. The function
        // resolves the producer's relative output to the same
        // workspace-absolute form before comparing.
        let producer_proj = project_with(
            "gen_pkg",
            nested_root("/gen_pkg"),
            vec![task_with("emit", vec![], vec![output("dist/api.js")])],
        );
        let consumer_proj = project_with(
            "web",
            nested_root("/web"),
            vec![task_with(
                "build",
                vec![input("/gen_pkg/dist/api.js")],
                vec![],
            )],
        );
        let workspace = workspace_with(vec![producer_proj, consumer_proj]);
        let producers = producers_of_path(&workspace, "/gen_pkg/dist/api.js");
        assert_eq!(producers, BTreeSet::from([id("gen_pkg", "emit")]));
    }

    #[test]
    fn producers_of_path_handles_implicit_project_root_anchoring() {
        // `ProjectRoot::WorkspaceRoot` projects have empty path
        // prefixes; the producer's relative output anchors at
        // the workspace root.
        let p = project_with(
            "root_proj",
            ProjectRoot::WorkspaceRoot,
            vec![task_with("gen", vec![], vec![output("build/main.o")])],
        );
        let workspace = workspace_with(vec![p]);
        let producers = producers_of_path(&workspace, "/build/main.o");
        assert_eq!(producers, BTreeSet::from([id("root_proj", "gen")]));
    }

    #[test]
    fn task_without_outputs_contributes_nothing() {
        let p = project_with(
            "p",
            nested_root("/p"),
            vec![
                task_with("no_outputs", vec![input("src/main.rs")], vec![]),
                task_with("no_inputs", vec![], vec![output("dist/main.js")]),
            ],
        );
        let workspace = workspace_with(vec![p]);

        // no_outputs produces nothing; no_inputs consumes nothing.
        // No producer-matching edges should be emitted.
        assert!(compute_producer_edges(&workspace).is_empty());
    }
}