lean_ctx_doc/
anchor.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! Code anchors: what a page derives from, pinned at a content digest.
4//!
5//! An anchor names a file, a directory or a glob (`file:`, `dir:`, `glob:`
6//! refs). In `shape` mode a directory anchor pins only its listing: an entry
7//! appearing or disappearing moves it, an edit inside a file does not.
8//! Digests are sha256 hex over a canonical manifest (C0 2.2 `doc_anchor`):
9//! the bytes of a file; `<relpath>\0<file digest>\n` per file in bytewise
10//! path order for a directory or glob; `<relpath>\n` for a shape. The file
11//! set is what git tracks, so every checkout computes the same value.
12
13use serde::{Deserialize, Serialize};
14use sha2::{Digest, Sha256};
15
16/// What an anchor covers.
17#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
18#[serde(rename_all = "snake_case")]
19pub enum AnchorKind {
20    /// One file.
21    File,
22    /// A directory with everything under it.
23    Dir,
24    /// The files a glob matches (`*`, `?`, `**`).
25    Glob,
26}
27
28/// What a directory or glob anchor hashes.
29#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]
30#[serde(rename_all = "snake_case")]
31pub enum AnchorMode {
32    /// The files and their contents.
33    #[default]
34    Content,
35    /// The listing only.
36    Shape,
37}
38
39/// Whether the page derives from the target or only consulted it.
40#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
41#[serde(rename_all = "snake_case")]
42pub enum AnchorRole {
43    /// A change makes the page stale.
44    Derived,
45    /// Advisory: the page never goes stale over it.
46    Cites,
47}
48
49/// How a page stands against one anchor.
50#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
51#[serde(rename_all = "snake_case")]
52pub enum AnchorState {
53    /// The target matches the pinned digest.
54    Fresh,
55    /// The target moved and nothing accounts for it.
56    Stale,
57    /// The target moved and an open note covers the change.
58    Noted,
59    /// The target is gone from the checkout.
60    Missing,
61}
62
63/// One anchor of a page. `path` is relative to the repository root and uses
64/// `/` separators; an empty path is the root itself.
65#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
66pub struct Anchor {
67    pub kind: AnchorKind,
68    #[serde(default, skip_serializing_if = "is_content")]
69    pub mode: AnchorMode,
70    pub role: AnchorRole,
71    pub path: String,
72    /// sha256 hex of the manifest at pin time; empty while unpinned.
73    pub digest: String,
74    /// The commit the pin was taken at, when the checkout is a git one.
75    #[serde(default, skip_serializing_if = "Option::is_none")]
76    pub commit: Option<String>,
77}
78
79#[allow(clippy::trivially_copy_pass_by_ref)] // serde's skip_serializing_if takes a reference
80fn is_content(m: &AnchorMode) -> bool {
81    *m == AnchorMode::Content
82}
83
84impl Anchor {
85    /// The wire ref: `file:<path>`, `dir:<path>` or `glob:<pattern>`.
86    pub fn reference(&self) -> String {
87        let scheme = match self.kind {
88            AnchorKind::File => "file",
89            AnchorKind::Dir => "dir",
90            AnchorKind::Glob => "glob",
91        };
92        format!("{scheme}:{}", self.path)
93    }
94
95    /// Does this anchor derive the page from `file` (a repo-relative path)?
96    /// Cited and shape anchors never count, as in a coverage report.
97    pub fn derives(&self, file: &str) -> bool {
98        self.role == AnchorRole::Derived && self.mode == AnchorMode::Content && self.matches(file)
99    }
100
101    /// Is `file` under this anchor's target, whatever its role and mode?
102    pub fn matches(&self, file: &str) -> bool {
103        match self.kind {
104            AnchorKind::File => file == self.path,
105            AnchorKind::Dir => under(&self.path, file),
106            AnchorKind::Glob => glob_match(&self.path, file),
107        }
108    }
109
110    /// The anchor's state given the digest the checkout yields now (`None`
111    /// when the target is gone) and whether an open note covers the move.
112    pub fn state(&self, current: Option<&str>, covered: bool) -> AnchorState {
113        match current {
114            None => AnchorState::Missing,
115            Some(d) if d == self.digest => AnchorState::Fresh,
116            Some(_) if covered => AnchorState::Noted,
117            Some(_) => AnchorState::Stale,
118        }
119    }
120}
121
122/// Is `file` the path `dir` or below it?
123fn under(dir: &str, file: &str) -> bool {
124    let dir = dir.trim_end_matches('/');
125    dir.is_empty() || file == dir || file.strip_prefix(dir).is_some_and(|r| r.starts_with('/'))
126}
127
128/// Does a glob with `*`, `?` and `**` (whole segments) match `path`?
129pub fn glob_match(pattern: &str, path: &str) -> bool {
130    let pat: Vec<&str> = pattern.split('/').filter(|s| !s.is_empty()).collect();
131    let segs: Vec<&str> = path.split('/').filter(|s| !s.is_empty()).collect();
132    match_segments(&pat, &segs)
133}
134
135fn match_segments(pat: &[&str], segs: &[&str]) -> bool {
136    match pat.split_first() {
137        None => segs.is_empty(),
138        Some((&"**", rest)) => (0..=segs.len()).any(|i| match_segments(rest, &segs[i..])),
139        Some((p, rest)) => segs.split_first().is_some_and(|(s, tail)| {
140            match_segment(p.as_bytes(), s.as_bytes()) && match_segments(rest, tail)
141        }),
142    }
143}
144
145fn match_segment(p: &[u8], s: &[u8]) -> bool {
146    match p.split_first() {
147        None => s.is_empty(),
148        Some((b'*', rest)) => (0..=s.len()).any(|i| match_segment(rest, &s[i..])),
149        Some((b'?', rest)) => !s.is_empty() && match_segment(rest, &s[1..]),
150        Some((c, rest)) => s.first() == Some(c) && match_segment(rest, &s[1..]),
151    }
152}
153
154/// Is this path a glob pattern?
155pub fn is_glob(path: &str) -> bool {
156    path.contains(['*', '?', '['])
157}
158
159/// sha256 hex of one file's bytes.
160pub fn file_digest(bytes: &[u8]) -> String {
161    hex(&Sha256::digest(bytes))
162}
163
164/// The digest of a set of files: a `<relpath>\0<file digest>\n` line per
165/// `(relative path, file digest)` entry, in bytewise path order.
166pub fn tree_digest(entries: &[(String, String)]) -> String {
167    let mut sorted: Vec<&(String, String)> = entries.iter().collect();
168    sorted.sort();
169    let mut h = Sha256::new();
170    for (path, digest) in sorted {
171        h.update(path.as_bytes());
172        h.update(b"\0");
173        h.update(digest.as_bytes());
174        h.update(b"\n");
175    }
176    hex(&h.finalize())
177}
178
179/// The digest of a directory listing: a `<relpath>\n` line per path, sorted.
180pub fn shape_digest(paths: &[String]) -> String {
181    let mut sorted: Vec<&String> = paths.iter().collect();
182    sorted.sort();
183    let mut h = Sha256::new();
184    for p in sorted {
185        h.update(p.as_bytes());
186        h.update(b"\n");
187    }
188    hex(&h.finalize())
189}
190
191fn hex(bytes: &[u8]) -> String {
192    use std::fmt::Write as _;
193    bytes
194        .iter()
195        .fold(String::with_capacity(bytes.len() * 2), |mut s, b| {
196            let _ = write!(s, "{b:02x}");
197            s
198        })
199}
200
201/// Which files no page derives from.
202#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
203pub struct Coverage {
204    pub files: usize,
205    pub covered: usize,
206    /// The uncovered files, in path order.
207    pub uncovered: Vec<String>,
208}
209
210/// Coverage of `files` (repo-relative) by the derived anchors of all pages.
211pub fn coverage<'a>(files: &[&str], anchors: impl IntoIterator<Item = &'a Anchor>) -> Coverage {
212    let anchors: Vec<&Anchor> = anchors
213        .into_iter()
214        .filter(|a| a.role == AnchorRole::Derived)
215        .collect();
216    let mut uncovered: Vec<String> = files
217        .iter()
218        .filter(|f| !anchors.iter().any(|a| a.derives(f)))
219        .map(|f| (*f).to_owned())
220        .collect();
221    uncovered.sort();
222    Coverage {
223        files: files.len(),
224        covered: files.len() - uncovered.len(),
225        uncovered,
226    }
227}
228
229#[cfg(test)]
230mod tests {
231    use super::*;
232
233    fn anchor(kind: AnchorKind, role: AnchorRole, path: &str) -> Anchor {
234        Anchor {
235            kind,
236            mode: AnchorMode::Content,
237            role,
238            path: path.into(),
239            digest: "aa".into(),
240            commit: None,
241        }
242    }
243
244    #[test]
245    fn globs_match_segments_and_double_stars() {
246        assert!(glob_match("rust/src/**/*.rs", "rust/src/a.rs"));
247        assert!(glob_match("rust/src/**/*.rs", "rust/src/core/hive/b.rs"));
248        assert!(!glob_match("rust/src/**/*.rs", "rust/srcx/a.rs"));
249        assert!(!glob_match("rust/src/*.rs", "rust/src/core/a.rs"));
250        assert!(glob_match("a/?.md", "a/b.md"));
251        assert!(glob_match("**", "anything/at/all"));
252    }
253
254    #[test]
255    fn path_anchors_cover_their_subtree_only() {
256        let a = anchor(AnchorKind::Dir, AnchorRole::Derived, "rust/src/core");
257        assert!(a.derives("rust/src/core/x.rs"));
258        assert!(!a.derives("rust/src/corex/y.rs"));
259        assert!(anchor(AnchorKind::Dir, AnchorRole::Derived, "").derives("x"));
260        let f = anchor(AnchorKind::File, AnchorRole::Derived, "rust/src/a.rs");
261        assert!(f.derives("rust/src/a.rs") && !f.derives("rust/src/a.rs/b"));
262        assert_eq!(a.reference(), "dir:rust/src/core");
263    }
264
265    #[test]
266    fn coverage_ignores_cites_and_shapes() {
267        let anchors = [
268            anchor(AnchorKind::File, AnchorRole::Derived, "src/a.rs"),
269            anchor(AnchorKind::File, AnchorRole::Cites, "src/b.rs"),
270            Anchor {
271                mode: AnchorMode::Shape,
272                ..anchor(AnchorKind::Dir, AnchorRole::Derived, "src")
273            },
274            anchor(AnchorKind::Glob, AnchorRole::Derived, "src/g/*.rs"),
275        ];
276        let c = coverage(
277            &["src/a.rs", "src/b.rs", "src/g/c.rs", "src/d.rs"],
278            &anchors,
279        );
280        assert_eq!(c.covered, 2);
281        assert_eq!(c.uncovered, ["src/b.rs", "src/d.rs"]);
282    }
283
284    #[test]
285    fn states_follow_the_digest_and_notes() {
286        let a = anchor(AnchorKind::File, AnchorRole::Derived, "x");
287        assert_eq!(a.state(Some("aa"), false), AnchorState::Fresh);
288        assert_eq!(a.state(Some("bb"), false), AnchorState::Stale);
289        assert_eq!(a.state(Some("bb"), true), AnchorState::Noted);
290        assert_eq!(a.state(None, false), AnchorState::Missing);
291    }
292
293    // C0 2.2 vectors (hive-v2 vectors/doc_anchor_digest).
294    #[test]
295    fn digest_vectors() {
296        let lib = file_digest(b"pub mod x;\n");
297        assert_eq!(
298            lib,
299            "1497ba2ae9c58431b70c98c925ac011cdfc28b8b74ce9e0e5ae54c0261ec5fb9"
300        );
301        let dir = tree_digest(&[
302            ("b.md".to_owned(), file_digest(b"beta\n")),
303            ("a.md".to_owned(), file_digest(b"alpha\n")),
304        ]);
305        assert_eq!(
306            dir,
307            "1d71a3193a1273437b70644f06adaff7d368b9c6f0598776ba0503574103f93f"
308        );
309        let glob = tree_digest(&[
310            ("src/lib.rs".to_owned(), lib),
311            ("src/x/y.rs".to_owned(), file_digest(b"pub fn y() {}\n")),
312        ]);
313        assert_eq!(
314            glob,
315            "e5ba8609e0f1153e71e6015814700e24ddf89abe7b5953363ccc53f79aff32f6"
316        );
317        assert!(
318            glob_match("src/**/*.rs", "src/lib.rs") && !glob_match("src/**/*.rs", "src/README.md")
319        );
320        assert_eq!(
321            shape_digest(&["b.md".into(), "a.md".into()]),
322            "80470d491b39cfbc95db36d718eddff3c90a184765b75ab9353d3b53408d65d1"
323        );
324        assert_eq!(
325            tree_digest(&[]),
326            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
327        );
328    }
329
330    #[test]
331    fn digests_are_order_independent_and_path_sensitive() {
332        let a = vec![
333            ("a".to_owned(), "d1".to_owned()),
334            ("b".to_owned(), "d2".to_owned()),
335        ];
336        let b = vec![a[1].clone(), a[0].clone()];
337        assert_eq!(tree_digest(&a), tree_digest(&b));
338        assert_ne!(
339            tree_digest(&a),
340            tree_digest(&[("c".to_owned(), "d1".to_owned())])
341        );
342        assert_ne!(shape_digest(&["a".into()]), shape_digest(&["b".into()]));
343        assert_eq!(
344            file_digest(b"abc"),
345            "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad"
346        );
347    }
348}
lean_ctx_doc/anchor.rs

lean_ctx_doc/
anchor.rs
