git_policy_cli/index/
index_cache_tree.rs

1//! What:
2//!  The `TREE` (cache-tree) index extension: read, written back byte for byte, and invalidated along a path
3//!  (`cache-tree.c`: `read_one`, `write_one`, `do_invalidate_path`).
4//! Why:
5//!  Git marks every directory above a changed path as not valid and drops a subtree that the path names; an in-process
6//!  index update must leave the extension exactly as that does, or the next `write-tree` would trust a stale tree name.
7//!
8//! In TS you'd write (pseudocode):
9//! ```ts
10//! const tree = CacheTree.read(bytes, hashLength); tree.invalidate(path); const out = tree.write();
11//! ```
12
13/// The deepest nesting the reader follows: the depth the tree reader follows (`TREE_DEPTH_LIMIT` in `repo_read_tree.rs`).
14const DEPTH_LIMIT: usize = 256;
15
16/// One directory of the cache-tree.
17#[derive(Clone, Debug, Eq, PartialEq)]
18pub struct CacheTree {
19    /// The number of index entries below, or -1 when the directory is not valid.
20    pub entry_count: i64,
21    /// The tree object name; present exactly when `entry_count` is not negative.
22    pub id: Vec<u8>,
23    /// The subdirectories by name, in the byte order the file keeps.
24    pub subtrees: Vec<(Vec<u8>, CacheTree)>,
25}
26
27/// The decimal number at the start of `bytes` (with `-` signs, as `parse_int`), the bytes after it.
28fn parse_number(bytes: &[u8]) -> Option<(i64, &[u8])> {
29    let signs: usize = bytes.iter().take_while(|byte| { return **byte == b'-'; }).count();
30    let digits: usize = bytes[signs..].iter().take_while(|byte| { return byte.is_ascii_digit(); }).count();
31    let text: &str = std::str::from_utf8(&bytes[signs..signs + digits]).ok()?;
32    let magnitude: i64 = if text.is_empty() { 0 } else { text.parse::<i64>().ok()? };
33    let value: i64 = if signs % 2 == 1 { -magnitude } else { magnitude };
34    return Some((value, &bytes[signs + digits..]));
35}
36
37/// Read one directory and the subdirectories after it; the bytes left and the name of the directory.
38fn read_one<'a>(bytes: &'a [u8], hash_length: usize, depth: usize) -> Option<(Vec<u8>, CacheTree, &'a [u8])> {
39    if depth > DEPTH_LIMIT {
40        return None;
41    }
42    let nul: usize = bytes.iter().position(|byte| { return *byte == 0; })?;
43    let name: Vec<u8> = bytes[..nul].to_vec();
44    let (entry_count, after_count) = parse_number(&bytes[nul + 1..])?;
45    let after_space: &[u8] = after_count.strip_prefix(b" ")?;
46    let (subtree_count, after_subtrees) = parse_number(after_space)?;
47    let mut rest: &[u8] = after_subtrees.strip_prefix(b"\n")?;
48    let mut id: Vec<u8> = Vec::new();
49    if entry_count >= 0 {
50        id = rest.get(..hash_length)?.to_vec();
51        rest = &rest[hash_length..];
52    }
53    let mut subtrees: Vec<(Vec<u8>, CacheTree)> = Vec::new();
54    for _ in 0..usize::try_from(subtree_count).ok()? {
55        let (child_name, child, after) = read_one(rest, hash_length, depth + 1)?;
56        // Git sorts subtrees on insertion by length first and then by bytes (`subtree_name_cmp`); a file that is not already
57        //  in that order is left to Git.
58        if subtrees.last().is_some_and(|(previous, _)| { return (previous.len(), previous.as_slice()) >= (child_name.len(), child_name.as_slice()); }) {
59            return None;
60        }
61        subtrees.push((child_name, child));
62        rest = after;
63    }
64    return Some((name, CacheTree { entry_count, id, subtrees }, rest));
65}
66
67/// Append one directory and its subdirectories under `name`.
68fn write_one(out: &mut Vec<u8>, name: &[u8], tree: &CacheTree) {
69    out.extend_from_slice(name);
70    out.extend_from_slice(format!("\0{} {}\n", tree.entry_count, tree.subtrees.len()).as_bytes());
71    if tree.entry_count >= 0 {
72        out.extend_from_slice(tree.id.as_slice());
73    }
74    for (child_name, child) in &tree.subtrees {
75        write_one(out, child_name.as_slice(), child);
76    }
77}
78
79impl CacheTree {
80    /// The tree of an extension's bytes, or `None` for any malformed or trailing content (Git would drop the extension).
81    pub fn read(bytes: &[u8], hash_length: usize) -> Option<CacheTree> {
82        let (_, tree, rest) = read_one(bytes, hash_length, 0)?;
83        if !rest.is_empty() {
84            return None;
85        }
86        return Some(tree);
87    }
88
89    /// The extension's bytes.
90    pub fn write(&self) -> Vec<u8> {
91        let mut out: Vec<u8> = Vec::new();
92        write_one(&mut out, b"", self);
93        return out;
94    }
95
96    /// Mark every directory above `path` as not valid and remove the subtree `path` names (`do_invalidate_path`).
97    pub fn invalidate(&mut self, path: &[u8]) {
98        self.entry_count = -1;
99        self.id.clear();
100        let Some(slash) = path.iter().position(|byte| { return *byte == b'/'; }) else {
101            self.subtrees.retain(|(name, _)| { return name.as_slice() != path; });
102            return;
103        };
104        if let Some((_, child)) = self.subtrees.iter_mut().find(|(name, _)| { return name.as_slice() == &path[..slash]; }) {
105            child.invalidate(&path[slash + 1..]);
106        }
107    }
108}
109
110#[cfg(test)]
111#[path = "index_cache_tree_tests.rs"]
112mod tests;
git_policy_cli/index/index_cache_tree.rs

git_policy_cli/index/
index_cache_tree.rs
