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/// A `supersedes` cycle through `idx`, as the documents in order, or None. In a cycle every
60/// member is superseded, so nothing in it is current.
61pub fn supersede_cycle(g: &Graph, idx: usize) -> Option<Vec<usize>> {
62    let mut stack = vec![(idx, vec![idx])];
63    let mut seen = BTreeSet::new();
64    while let Some((cur, path)) = stack.pop() {
65        for e in g.edges_from(cur).filter(|e| e.kind == "supersedes") {
66            if e.to == idx {
67                return Some(path);
68            }
69            if seen.insert(e.to) {
70                let mut next = path.clone();
71                next.push(e.to);
72                stack.push((e.to, next));
73            }
74        }
75    }
76    None
77}
78
79/// Follows `supersedes` edges backwards from `idx` to the document that replaced it last.
80pub fn chain(g: &Graph, idx: usize) -> Vec<usize> {
81    let mut path = vec![idx];
82    let mut cur = idx;
83    loop {
84        let next = g.edges_to(cur).find(|e| e.kind == "supersedes").map(|e| e.from);
85        match next {
86            Some(n) if !path.contains(&n) => {
87                path.push(n);
88                cur = n;
89            }
90            _ => return path,
91        }
92    }
93}
specfold_core/graph/query.rs

specfold_core/graph/
query.rs
