specfold_core/graph/
query.rs

1//! Questions the graph answers: what governs a path, what a change would reach, where a
2//! supersede chain ends.
3
4use super::types::Graph;
5use crate::corpus::Corpus;
6use crate::workspace::owners::matcher;
7use std::collections::{BTreeSet, VecDeque};
8
9/// A document that governs a path, and how specific its claim is (longer = narrower).
10#[derive(Debug, Clone)]
11pub struct Governing {
12    pub idx: usize,
13    pub pattern: String,
14    pub specificity: usize,
15}
16
17/// Documents whose `rel.governs` covers `path`, or, without `governs`, whose owner contains it.
18/// Narrowest claims first.
19pub fn governing(c: &Corpus, path: &str) -> Vec<Governing> {
20    let path = path.trim_start_matches("./").trim_end_matches('/');
21    let mut out = vec![];
22    for (i, d) in c.docs.iter().enumerate() {
23        let globs = d.rel().remove("governs").unwrap_or_default();
24        if globs.is_empty() {
25            let Some(owner) = c.owners.by_id(&d.id.owner) else { continue };
26            if !owner.path.is_empty() && (path == owner.path || path.starts_with(&format!("{}/", owner.path))) {
27                out.push(Governing { idx: i, pattern: format!("{}/**", owner.path), specificity: owner.path.len() });
28            }
29            continue;
30        }
31        for g in globs {
32            if matcher(&g).is_some_and(|m| m.is_match(path)) {
33                let specificity = g.split(['*', '?', '[', '{']).next().unwrap_or("").len();
34                out.push(Governing { idx: i, pattern: g, specificity });
35                break;
36            }
37        }
38    }
39    out.sort_by(|a, b| b.specificity.cmp(&a.specificity).then(a.idx.cmp(&b.idx)));
40    out
41}
42
43/// Every document that reaches `idx` through incoming edges, nearest first.
44pub fn impact(g: &Graph, idx: usize) -> Vec<(usize, usize)> {
45    let mut seen = BTreeSet::from([idx]);
46    let mut out = vec![];
47    let mut q = VecDeque::from([(idx, 0usize)]);
48    while let Some((cur, depth)) = q.pop_front() {
49        for e in g.edges_to(cur) {
50            if seen.insert(e.from) {
51                out.push((e.from, depth + 1));
52                q.push_back((e.from, depth + 1));
53            }
54        }
55    }
56    out
57}
58
59/// Follows `supersedes` edges backwards from `idx` to the document that replaced it last.
60pub fn chain(g: &Graph, idx: usize) -> Vec<usize> {
61    let mut path = vec![idx];
62    let mut cur = idx;
63    loop {
64        let next = g.edges_to(cur).find(|e| e.kind == "supersedes").map(|e| e.from);
65        match next {
66            Some(n) if !path.contains(&n) => {
67                path.push(n);
68                cur = n;
69            }
70            _ => return path,
71        }
72    }
73}
specfold_core/graph/query.rs

specfold_core/graph/
query.rs
