cartulary 0.3.0-alpha.1

//! Detect cycles in the `parent-of` graph. Errors.

use crate::domain::model::check::{CheckViolationKind, Severity};
use crate::domain::model::issue::Issue;
use crate::domain::model::record_ref::IssueRef;
use crate::domain::usecases::check::{CheckViolation, IssueCheckCtx, IssueFinding, IssueRule};

pub struct ParentOfCycleRule;

pub const RULE_ID: &str = "issue/parent-of-cycle";

impl IssueRule for ParentOfCycleRule {
    fn id(&self) -> &'static str {
        RULE_ID
    }

    fn find(&self, ctx: &IssueCheckCtx<'_>) -> anyhow::Result<Vec<IssueFinding>> {
        let issues: Vec<Issue> = ctx.issues.iter().map(|(_, i)| i.clone()).collect();
        let mut out = Vec::new();
        for (id, kind) in find_violations(&issues) {
            let Some(path) = ctx.path_of(&id) else {
                continue;
            };
            out.push(IssueFinding::report(CheckViolation {
                rule_id: RULE_ID,
                path: path.to_path_buf(),
                severity: Severity::Error,
                kind,
            }));
        }
        Ok(out)
    }
}

fn find_violations(issues: &[Issue]) -> Vec<(IssueRef, CheckViolationKind)> {
    use std::collections::{HashMap, HashSet};

    let by_id: HashMap<&IssueRef, &Issue> = issues.iter().map(|i| (&i.id, i)).collect();

    let neighbours_of = |node: &IssueRef| -> Vec<IssueRef> {
        by_id
            .get(node)
            .map(|issue| issue.children().cloned().collect())
            .unwrap_or_default()
    };

    let mut colour: HashMap<IssueRef, u8> = HashMap::new();
    let mut violations: Vec<(IssueRef, CheckViolationKind)> = Vec::new();
    let mut reported: HashSet<IssueRef> = HashSet::new();

    for issue in issues {
        let start = issue.id.clone();
        if colour.get(&start).copied().unwrap_or(0) == 2 {
            continue;
        }
        let mut dfs_stack: Vec<(IssueRef, Vec<IssueRef>, usize, Vec<IssueRef>)> =
            vec![(start.clone(), neighbours_of(&start), 0, vec![start.clone()])];
        colour.insert(start, 1);

        while let Some((node, neighbours, idx, path)) = dfs_stack.last_mut() {
            let node = node.clone();
            if *idx >= neighbours.len() {
                colour.insert(node, 2);
                dfs_stack.pop();
                continue;
            }
            let next = neighbours[*idx].clone();
            *idx += 1;
            match colour.get(&next).copied().unwrap_or(0) {
                1 => {
                    let cycle_start = path.iter().position(|n| n == &next).unwrap_or(0);
                    let cycle: Vec<IssueRef> = path[cycle_start..].to_vec();
                    let mut entity_cycle: Vec<_> =
                        cycle.iter().map(|n| n.as_entity_ref().clone()).collect();
                    entity_cycle.push(next.as_entity_ref().clone());
                    let kind = CheckViolationKind::ParentOfCycle {
                        cycle: entity_cycle,
                    };
                    for n in &cycle {
                        if reported.insert(n.clone()) {
                            violations.push((n.clone(), kind.clone()));
                        }
                    }
                }
                2 => {}
                _ => {
                    let mut next_path = path.clone();
                    next_path.push(next.clone());
                    let nb = neighbours_of(&next);
                    colour.insert(next.clone(), 1);
                    dfs_stack.push((next, nb, 0, next_path));
                }
            }
        }
    }

    violations
}