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    // C207: for a folder, a document governing a file or glob inside it governs part of it.
22    let dir = c.cfg.root.join(path);
23    let inside = (!path.is_empty() && dir.is_dir()).then(|| files_under(&c.cfg.root, path));
24    let mut out = vec![];
25    for (i, d) in c.docs.iter().enumerate() {
26        let globs = d.rel().remove("governs").unwrap_or_default();
27        if globs.is_empty() {
28            let Some(owner) = c.owners.by_id(&d.id.owner) else { continue };
29            let under = inside.is_some() && owner.path.starts_with(&format!("{path}/"));
30            if !owner.path.is_empty() && (path == owner.path || path.starts_with(&format!("{}/", owner.path)) || under)
31            {
32                out.push(Governing { idx: i, pattern: format!("{}/**", owner.path), specificity: owner.path.len() });
33            }
34            continue;
35        }
36        for g in globs {
37            let below = || inside.as_ref().is_some_and(|files| below_dir(&g, path, files));
38            if matcher(&g).is_some_and(|m| m.is_match(path)) || below() {
39                let specificity = g.split(['*', '?', '[', '{']).next().unwrap_or("").len();
40                out.push(Governing { idx: i, pattern: g, specificity });
41                break;
42            }
43        }
44    }
45    out.sort_by(|a, b| b.specificity.cmp(&a.specificity).then(a.idx.cmp(&b.idx)));
46    out
47}
48
49/// Whether glob `g` claims something below folder `dir`: its literal part lies inside it, or it
50/// matches one of the files there.
51fn below_dir(g: &str, dir: &str, files: &[String]) -> bool {
52    let lit = g.split(['*', '?', '[', '{']).next().unwrap_or("");
53    if lit.starts_with(&format!("{dir}/")) {
54        return true;
55    }
56    matcher(g).is_some_and(|m| files.iter().any(|f| m.is_match(f)))
57}
58
59/// Up to a few thousand file paths below `dir`, relative to the root, skipping dot folders.
60fn files_under(root: &std::path::Path, dir: &str) -> Vec<String> {
61    const MAX: usize = 5000;
62    let mut out = vec![];
63    let mut stack = vec![dir.to_string()];
64    while let Some(d) = stack.pop() {
65        let Ok(rd) = std::fs::read_dir(root.join(&d)) else { continue };
66        for e in rd.flatten() {
67            let name = e.file_name().to_string_lossy().to_string();
68            if name.starts_with('.') {
69                continue;
70            }
71            let rel = format!("{d}/{name}");
72            if e.file_type().is_ok_and(|t| t.is_dir()) {
73                stack.push(rel);
74            } else if out.len() < MAX {
75                out.push(rel);
76            }
77        }
78        if out.len() >= MAX {
79            break;
80        }
81    }
82    out
83}
84
85/// Every document that reaches `idx` through incoming edges, nearest first.
86pub fn impact(g: &Graph, idx: usize) -> Vec<(usize, usize)> {
87    let mut seen = BTreeSet::from([idx]);
88    let mut out = vec![];
89    let mut q = VecDeque::from([(idx, 0usize)]);
90    while let Some((cur, depth)) = q.pop_front() {
91        for e in g.edges_to(cur) {
92            if seen.insert(e.from) {
93                out.push((e.from, depth + 1));
94                q.push_back((e.from, depth + 1));
95            }
96        }
97    }
98    out
99}
100
101/// A `supersedes` cycle through `idx`, as the documents in order, or None. In a cycle every
102/// member is superseded, so nothing in it is current.
103pub fn supersede_cycle(g: &Graph, idx: usize) -> Option<Vec<usize>> {
104    let mut stack = vec![(idx, vec![idx])];
105    let mut seen = BTreeSet::new();
106    while let Some((cur, path)) = stack.pop() {
107        for e in g.edges_from(cur).filter(|e| e.kind == "supersedes") {
108            if e.to == idx {
109                return Some(path);
110            }
111            if seen.insert(e.to) {
112                let mut next = path.clone();
113                next.push(e.to);
114                stack.push((e.to, next));
115            }
116        }
117    }
118    None
119}
120
121/// Follows `supersedes` edges backwards from `idx` to the document that replaced it last.
122pub fn chain(g: &Graph, idx: usize) -> Vec<usize> {
123    let mut path = vec![idx];
124    let mut cur = idx;
125    loop {
126        let next = g.edges_to(cur).find(|e| e.kind == "supersedes").map(|e| e.from);
127        match next {
128            Some(n) if !path.contains(&n) => {
129                path.push(n);
130                cur = n;
131            }
132            _ => return path,
133        }
134    }
135}
specfold_core/graph/query.rs

specfold_core/graph/
query.rs
