haz_query/engine/

relational.rs

//! Per-task evaluation of the relational filters of `QRY-004`.
//!
//! Each relational filter resolves a user expression to a *target
//! set* (every task whose project/task/tag attributes satisfy the
//! expression), then asks whether the candidate's hard-edge
//! relation to that target set is non-empty.
//!
//! Direct relations (`--child-of`, `--parent-of`) read the
//! candidate's direct hard-edge neighbours and intersect them with
//! the target set. Transitive relations (`--depends-on`,
//! `--ancestor-of`) BFS over hard edges; per `QRY-004` the result
//! excludes the target set itself ("minus the EXPR-matching tasks
//! themselves").
//!
//! Target sets are computed once per relational flag in
//! [`RelationalTargets::from_spec`] and shared across all
//! candidates; per-candidate work is then a set intersection or a
//! BFS.

use std::collections::BTreeSet;

use haz_dag::graph::TaskGraph;
use haz_dag::traversal::{
    direct_predecessors, direct_successors, transitive_predecessors, transitive_successors,
};
use haz_domain::task_id::TaskId;
use haz_domain::workspace::Workspace;
use haz_query_lang::expr::Expr;

use crate::engine::spec::QuerySpec;
use crate::expr::relational::RelationalAtom;

/// Target sets for every relational filter in a [`QuerySpec`].
///
/// A `None` field means the corresponding flag was not supplied;
/// `Some(set)` means the flag was supplied and the contained set
/// is its target set.
#[derive(Debug, Default, Clone)]
pub struct RelationalTargets {
    /// Target set of `--child-of`.
    pub child_of: Option<BTreeSet<TaskId>>,
    /// Target set of `--parent-of`.
    pub parent_of: Option<BTreeSet<TaskId>>,
    /// Target set of `--depends-on`.
    pub depends_on: Option<BTreeSet<TaskId>>,
    /// Target set of `--ancestor-of`.
    pub ancestor_of: Option<BTreeSet<TaskId>>,
}

impl RelationalTargets {
    /// Compute the target set of every relational filter present
    /// in `spec`. An absent filter yields a `None` field; the
    /// computation is therefore proportional to the number of
    /// supplied flags, never four full walks.
    #[must_use]
    pub fn from_spec(workspace: &Workspace, spec: &QuerySpec) -> Self {
        Self {
            child_of: spec
                .child_of
                .as_ref()
                .map(|expr| compute_target_set(workspace, expr)),
            parent_of: spec
                .parent_of
                .as_ref()
                .map(|expr| compute_target_set(workspace, expr)),
            depends_on: spec
                .depends_on
                .as_ref()
                .map(|expr| compute_target_set(workspace, expr)),
            ancestor_of: spec
                .ancestor_of
                .as_ref()
                .map(|expr| compute_target_set(workspace, expr)),
        }
    }
}

/// Compute the target set of a relational expression: every task
/// in the workspace whose `(project_name, task_name,
/// project_tags)` triple satisfies `expr`.
///
/// Returned as a `BTreeSet`, which iterates in canonical
/// `(ProjectName, TaskName)` order.
#[must_use]
pub fn compute_target_set(workspace: &Workspace, expr: &Expr<RelationalAtom>) -> BTreeSet<TaskId> {
    let mut target_set: BTreeSet<TaskId> = BTreeSet::new();
    for project in workspace.projects.values() {
        for task_name in project.tasks.keys() {
            let matches = expr.eval(|atom| atom.matches(&project.name, task_name, &project.tags));
            if matches {
                target_set.insert(TaskId {
                    project: project.name.clone(),
                    task: task_name.clone(),
                });
            }
        }
    }
    target_set
}

/// Whether `candidate` passes every relational filter in
/// `targets`. A `None` filter contributes no constraint; a
/// `Some(set)` filter requires the appropriate hard-edge relation
/// to that set to be non-empty.
#[must_use]
pub fn passes_relational(
    graph: &TaskGraph,
    candidate: &TaskId,
    targets: &RelationalTargets,
) -> bool {
    if let Some(set) = &targets.child_of
        && !passes_child_of(graph, candidate, set)
    {
        return false;
    }
    if let Some(set) = &targets.parent_of
        && !passes_parent_of(graph, candidate, set)
    {
        return false;
    }
    if let Some(set) = &targets.depends_on
        && !passes_depends_on(graph, candidate, set)
    {
        return false;
    }
    if let Some(set) = &targets.ancestor_of
        && !passes_ancestor_of(graph, candidate, set)
    {
        return false;
    }
    true
}

/// `--child-of EXPR`: at least one direct hard-edge predecessor of
/// `candidate` is in `targets` (the candidate's `deps:` names a
/// target).
#[must_use]
pub fn passes_child_of(graph: &TaskGraph, candidate: &TaskId, targets: &BTreeSet<TaskId>) -> bool {
    !direct_predecessors(graph, candidate).is_disjoint(targets)
}

/// `--parent-of EXPR`: at least one direct hard-edge successor of
/// `candidate` is in `targets` (some target's `deps:` names the
/// candidate).
#[must_use]
pub fn passes_parent_of(graph: &TaskGraph, candidate: &TaskId, targets: &BTreeSet<TaskId>) -> bool {
    !direct_successors(graph, candidate).is_disjoint(targets)
}

/// `--depends-on EXPR`: at least one transitive hard-edge
/// predecessor of `candidate` is in `targets` AND `candidate` is
/// not itself in `targets` (per the "minus the EXPR-matching
/// tasks themselves" clause of `QRY-004`).
#[must_use]
pub fn passes_depends_on(
    graph: &TaskGraph,
    candidate: &TaskId,
    targets: &BTreeSet<TaskId>,
) -> bool {
    if targets.contains(candidate) {
        return false;
    }
    !transitive_predecessors(graph, candidate).is_disjoint(targets)
}

/// `--ancestor-of EXPR`: at least one transitive hard-edge
/// successor of `candidate` is in `targets` AND `candidate` is
/// not itself in `targets` (per the "minus the EXPR-matching
/// tasks themselves" clause of `QRY-004`).
#[must_use]
pub fn passes_ancestor_of(
    graph: &TaskGraph,
    candidate: &TaskId,
    targets: &BTreeSet<TaskId>,
) -> bool {
    if targets.contains(candidate) {
        return false;
    }
    !transitive_successors(graph, candidate).is_disjoint(targets)
}

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

    use haz_dag::edge::{Edge, EdgeKind};
    use haz_dag::graph::TaskGraph;
    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::settings::WorkspaceSettings;
    use haz_domain::task::Task;
    use haz_domain::task_id::TaskId;
    use haz_domain::workspace::Workspace;
    use haz_query_lang::expr::Expr;
    use nonempty::NonEmpty;

    use super::*;

    fn argv(parts: &[&str]) -> NonEmpty<String> {
        NonEmpty::from_vec(parts.iter().map(|s| (*s).to_owned()).collect()).unwrap()
    }

    fn bare_task(name: &str) -> Task {
        Task {
            name: TaskName::from_str(name).unwrap(),
            action: TaskAction::Command(argv(&["true"])),
            inputs: vec![],
            outputs: vec![],
            deps: vec![],
            weak_deps: vec![],
            mutex: None,
            env: EnvSettings::default(),
        }
    }

    fn project(name: &str, root: &str, tags: &[&str], task_names: &[&str]) -> Project {
        let mut tasks = BTreeMap::new();
        for &task_name in task_names {
            tasks.insert(TaskName::from_str(task_name).unwrap(), bare_task(task_name));
        }
        Project {
            name: ProjectName::from_str(name).unwrap(),
            root: ProjectRoot::Nested(
                CanonicalPath::from_absolute(&HazPath::parse(root).unwrap()).unwrap(),
            ),
            tags: tags
                .iter()
                .map(|t| TagName::from_str(t).unwrap())
                .collect::<BTreeSet<_>>(),
            tasks,
        }
    }

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

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

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

    fn graph_with_hard_edges(nodes: &[TaskId], edges: &[(TaskId, TaskId)]) -> TaskGraph {
        TaskGraph {
            nodes: nodes.iter().cloned().collect(),
            edges: edges
                .iter()
                .map(|(from, to)| Edge {
                    from: from.clone(),
                    to: to.clone(),
                    kind: EdgeKind::Hard,
                })
                .collect(),
        }
    }

    fn relational_atom(text: &str) -> Expr<RelationalAtom> {
        use haz_query_lang::expr::RawAtom;
        use haz_query_lang::span::Span;

        use crate::expr::relational::parse_relational_atom;
        Expr::Atom(
            parse_relational_atom(RawAtom {
                text: text.to_owned(),
                span: Span { start: 0, end: 0 },
            })
            .unwrap(),
        )
    }

    // --- compute_target_set -------------------------------------

    #[test]
    fn target_set_for_name_atom_collects_matching_tasks_across_projects() {
        let ws = workspace(vec![
            project("lib", "/lib", &[], &["build", "test"]),
            project("web", "/web", &[], &["build", "bundle"]),
        ]);
        let expr = relational_atom("name:build");
        let target = compute_target_set(&ws, &expr);
        assert_eq!(target, ids(&[("lib", "build"), ("web", "build")]));
    }

    #[test]
    fn target_set_for_project_atom_collects_every_task_in_that_project() {
        let ws = workspace(vec![
            project("lib", "/lib", &[], &["build", "test"]),
            project("web", "/web", &[], &["bundle"]),
        ]);
        let expr = relational_atom("project:lib");
        let target = compute_target_set(&ws, &expr);
        assert_eq!(target, ids(&[("lib", "build"), ("lib", "test")]));
    }

    #[test]
    fn target_set_for_tag_atom_collects_tasks_under_tagged_projects() {
        let ws = workspace(vec![
            project("lib", "/lib", &["backend"], &["build"]),
            project("tools", "/tools", &["backend"], &["lint"]),
            project("web", "/web", &["frontend"], &["bundle"]),
        ]);
        let expr = relational_atom("tag:backend");
        let target = compute_target_set(&ws, &expr);
        assert_eq!(target, ids(&[("lib", "build"), ("tools", "lint")]));
    }

    #[test]
    fn target_set_under_boolean_composition_intersects() {
        let ws = workspace(vec![
            project("lib", "/lib", &["backend"], &["build", "test"]),
            project("web", "/web", &["frontend"], &["test"]),
        ]);
        // tag:backend & name:test  -> only lib:test
        let expr = Expr::And(
            Box::new(relational_atom("tag:backend")),
            Box::new(relational_atom("name:test")),
        );
        let target = compute_target_set(&ws, &expr);
        assert_eq!(target, ids(&[("lib", "test")]));
    }

    #[test]
    fn target_set_is_empty_when_no_task_matches() {
        let ws = workspace(vec![project("lib", "/lib", &[], &["build"])]);
        let expr = relational_atom("name:absent");
        let target = compute_target_set(&ws, &expr);
        assert!(target.is_empty());
    }

    // --- passes_child_of / passes_parent_of ---------------------

    #[test]
    fn child_of_passes_when_direct_predecessor_in_target_set() {
        // graph: a -> b
        let a = id("p", "a");
        let b = id("p", "b");
        let graph = graph_with_hard_edges(&[a.clone(), b.clone()], &[(a.clone(), b.clone())]);
        let targets = ids(&[("p", "a")]);
        assert!(passes_child_of(&graph, &b, &targets));
        assert!(!passes_child_of(&graph, &a, &targets));
    }

    #[test]
    fn parent_of_passes_when_direct_successor_in_target_set() {
        // graph: a -> b
        let a = id("p", "a");
        let b = id("p", "b");
        let graph = graph_with_hard_edges(&[a.clone(), b.clone()], &[(a.clone(), b.clone())]);
        let targets = ids(&[("p", "b")]);
        assert!(passes_parent_of(&graph, &a, &targets));
        assert!(!passes_parent_of(&graph, &b, &targets));
    }

    #[test]
    fn child_of_rejects_when_target_is_only_transitive_predecessor() {
        // graph: a -> b -> c, target = a
        let a = id("p", "a");
        let b = id("p", "b");
        let c = id("p", "c");
        let graph = graph_with_hard_edges(
            &[a.clone(), b.clone(), c.clone()],
            &[(a.clone(), b.clone()), (b, c.clone())],
        );
        let targets = ids(&[("p", "a")]);
        // c's only direct predecessor is b, not a.
        assert!(!passes_child_of(&graph, &c, &targets));
    }

    // --- passes_depends_on --------------------------------------

    #[test]
    fn depends_on_passes_when_transitive_predecessor_in_target_set() {
        // graph: a -> b -> c, target = a
        let a = id("p", "a");
        let b = id("p", "b");
        let c = id("p", "c");
        let graph = graph_with_hard_edges(
            &[a.clone(), b.clone(), c.clone()],
            &[(a.clone(), b.clone()), (b.clone(), c.clone())],
        );
        let targets = ids(&[("p", "a")]);
        assert!(passes_depends_on(&graph, &c, &targets));
        assert!(passes_depends_on(&graph, &b, &targets));
        // a is in target_set, so excluded by the QRY-004 clause.
        assert!(!passes_depends_on(&graph, &a, &targets));
    }

    #[test]
    fn depends_on_excludes_self_when_candidate_in_target_set() {
        // graph: a -> b -> c, target = {a, c} (both endpoints).
        // c is in targets, so c MUST be excluded from `depends-on
        // targets` even though c transitively depends on a.
        let a = id("p", "a");
        let b = id("p", "b");
        let c = id("p", "c");
        let graph = graph_with_hard_edges(
            &[a.clone(), b.clone(), c.clone()],
            &[(a.clone(), b.clone()), (b.clone(), c.clone())],
        );
        let targets = ids(&[("p", "a"), ("p", "c")]);
        assert!(!passes_depends_on(&graph, &c, &targets));
        assert!(passes_depends_on(&graph, &b, &targets));
    }

    // --- passes_ancestor_of -------------------------------------

    #[test]
    fn ancestor_of_passes_when_transitive_successor_in_target_set() {
        // graph: a -> b -> c, target = c
        let a = id("p", "a");
        let b = id("p", "b");
        let c = id("p", "c");
        let graph = graph_with_hard_edges(
            &[a.clone(), b.clone(), c.clone()],
            &[(a.clone(), b.clone()), (b.clone(), c.clone())],
        );
        let targets = ids(&[("p", "c")]);
        assert!(passes_ancestor_of(&graph, &a, &targets));
        assert!(passes_ancestor_of(&graph, &b, &targets));
        // c is in target_set, excluded.
        assert!(!passes_ancestor_of(&graph, &c, &targets));
    }

    #[test]
    fn ancestor_of_excludes_self_when_candidate_in_target_set() {
        let a = id("p", "a");
        let b = id("p", "b");
        let c = id("p", "c");
        let graph = graph_with_hard_edges(
            &[a.clone(), b.clone(), c.clone()],
            &[(a.clone(), b.clone()), (b.clone(), c.clone())],
        );
        let targets = ids(&[("p", "a"), ("p", "c")]);
        assert!(!passes_ancestor_of(&graph, &a, &targets));
        assert!(passes_ancestor_of(&graph, &b, &targets));
    }

    // --- empty target set ---------------------------------------

    #[test]
    fn every_relation_fails_when_target_set_is_empty() {
        let a = id("p", "a");
        let b = id("p", "b");
        let graph = graph_with_hard_edges(&[a.clone(), b.clone()], &[(a.clone(), b.clone())]);
        let empty: BTreeSet<TaskId> = BTreeSet::new();
        assert!(!passes_child_of(&graph, &b, &empty));
        assert!(!passes_parent_of(&graph, &a, &empty));
        assert!(!passes_depends_on(&graph, &b, &empty));
        assert!(!passes_ancestor_of(&graph, &a, &empty));
    }

    // --- passes_relational composes the four arms ---------------

    #[test]
    fn passes_relational_returns_true_when_no_filter_set() {
        let a = id("p", "a");
        let graph = graph_with_hard_edges(std::slice::from_ref(&a), &[]);
        let targets = RelationalTargets::default();
        assert!(passes_relational(&graph, &a, &targets));
    }

    #[test]
    fn passes_relational_short_circuits_on_first_failing_filter() {
        // a -> b, candidate = b.
        // child_of = {a} (passes), parent_of = {a} (fails: a has
        // no successor relationship from b).
        let a = id("p", "a");
        let b = id("p", "b");
        let graph = graph_with_hard_edges(&[a.clone(), b.clone()], &[(a.clone(), b.clone())]);
        let targets = RelationalTargets {
            child_of: Some(ids(&[("p", "a")])),
            parent_of: Some(ids(&[("p", "a")])),
            ..RelationalTargets::default()
        };
        assert!(!passes_relational(&graph, &b, &targets));
    }
}