grit_lib/odb/
tree.rs

1//! Looking up one path inside a tree object.
2//!
3//! Callers that need "the entry at `dir/file` in this tree" share [`Odb::tree_entry_at_path`]
4//! instead of reading and parsing each tree on the way by hand.
5
6use crate::error::Result;
7use crate::objects::{ObjectId, TreeEntry, TreeRefIter};
8
9use super::{Odb, SessionTree};
10
11/// Mode of a subtree entry.
12const MODE_TREE: u32 = 0o040000;
13
14impl Odb {
15    /// The entry at `path` inside the tree `tree`.
16    ///
17    /// Each `/`-separated component of `path` is looked up in turn; every component but the last
18    /// must name a subtree. The final entry is returned whatever its mode, so callers that want
19    /// only files filter out [`TreeEntry::mode`] `0o040000` themselves. Trees on the way are read
20    /// through this handle's bounded tree cache, so repeated lookups under the same directories
21    /// do not read or decode them again.
22    ///
23    /// # Parameters
24    ///
25    /// - `tree`: the root tree to start from.
26    /// - `path`: a repository-relative path in tree byte form (no leading or trailing `/`).
27    ///
28    /// # Returns
29    ///
30    /// The entry, with its name set to the last component, or `None` when a component is missing
31    /// or a non-final component is not a subtree. An empty `path` or one with empty components
32    /// names no entry.
33    ///
34    /// # Errors
35    ///
36    /// - [`crate::error::Error::ObjectNotFound`] when a tree on the way is missing.
37    /// - [`crate::error::Error::CorruptObject`] when a tree on the way is not a tree object or
38    ///   does not parse.
39    /// - Any other error [`Self::read`] reports.
40    pub fn tree_entry_at_path(&self, tree: &ObjectId, path: &[u8]) -> Result<Option<TreeEntry>> {
41        let mut current = *tree;
42        let mut components = path.split(|&b| b == b'/').peekable();
43        while let Some(name) = components.next() {
44            let Some((mode, oid)) = self.tree_child(&current, name)? else {
45                return Ok(None);
46            };
47            if components.peek().is_none() {
48                return Ok(Some(TreeEntry {
49                    mode,
50                    name: name.to_vec(),
51                    oid,
52                }));
53            }
54            if mode != MODE_TREE {
55                return Ok(None);
56            }
57            current = oid;
58        }
59        Ok(None)
60    }
61
62    /// Mode and id of the entry called `name` directly inside `tree`.
63    fn tree_child(&self, tree: &ObjectId, name: &[u8]) -> Result<Option<(u32, ObjectId)>> {
64        match self.cached_tree_for_walk(tree)? {
65            SessionTree::Parsed(entries) => Ok(entries
66                .iter()
67                .find(|e| e.name == name)
68                .map(|e| (e.mode, e.oid))),
69            SessionTree::Raw(data) => {
70                for entry in TreeRefIter::with_oid_len(&data, self.hash_algo().len()) {
71                    let entry = entry?;
72                    if entry.name == name {
73                        return Ok(Some((entry.mode, entry.oid)));
74                    }
75                }
76                Ok(None)
77            }
78        }
79    }
80}
81
82#[cfg(test)]
83mod tests {
84    #![allow(clippy::expect_used, clippy::unwrap_used)]
85
86    use super::*;
87    use crate::error::Error;
88    use crate::objects::{serialize_tree, ObjectKind};
89    use tempfile::TempDir;
90
91    fn write_tree(odb: &Odb, mut entries: Vec<TreeEntry>) -> ObjectId {
92        entries.sort_by(|a, b| {
93            crate::objects::tree_entry_cmp(
94                &a.name,
95                a.mode == MODE_TREE,
96                &b.name,
97                b.mode == MODE_TREE,
98            )
99        });
100        odb.write(ObjectKind::Tree, &serialize_tree(&entries))
101            .unwrap()
102    }
103
104    fn entry(mode: u32, name: &[u8], oid: ObjectId) -> TreeEntry {
105        TreeEntry {
106            mode,
107            name: name.to_vec(),
108            oid,
109        }
110    }
111
112    /// `file`, `link -> file`, `sub/` (a gitlink), and `dir/{a, nested/b}`.
113    fn fixture(odb: &Odb) -> (ObjectId, ObjectId, ObjectId, ObjectId) {
114        let blob_a = odb.write(ObjectKind::Blob, b"a\n").unwrap();
115        let blob_b = odb.write(ObjectKind::Blob, b"b\n").unwrap();
116        let nested = write_tree(odb, vec![entry(0o100755, b"b", blob_b)]);
117        let dir = write_tree(
118            odb,
119            vec![
120                entry(0o100644, b"a", blob_a),
121                entry(MODE_TREE, b"nested", nested),
122            ],
123        );
124        let gitlink = ObjectId::from_hex("1111111111111111111111111111111111111111").unwrap();
125        let root = write_tree(
126            odb,
127            vec![
128                entry(0o100644, b"file", blob_a),
129                entry(0o120000, b"link", blob_b),
130                entry(0o160000, b"sub", gitlink),
131                entry(MODE_TREE, b"dir", dir),
132            ],
133        );
134        (root, dir, nested, blob_b)
135    }
136
137    #[test]
138    fn finds_entries_of_every_mode() {
139        let tmp = TempDir::new().unwrap();
140        let odb = Odb::new(tmp.path());
141        let (root, dir, nested, blob_b) = fixture(&odb);
142
143        let found = odb
144            .tree_entry_at_path(&root, b"dir/nested/b")
145            .unwrap()
146            .unwrap();
147        assert_eq!(found, entry(0o100755, b"b", blob_b));
148        assert_eq!(
149            odb.tree_entry_at_path(&root, b"dir").unwrap().unwrap(),
150            entry(MODE_TREE, b"dir", dir)
151        );
152        assert_eq!(
153            odb.tree_entry_at_path(&root, b"dir/nested")
154                .unwrap()
155                .unwrap()
156                .oid,
157            nested
158        );
159        assert_eq!(
160            odb.tree_entry_at_path(&root, b"link")
161                .unwrap()
162                .unwrap()
163                .mode,
164            0o120000
165        );
166        assert_eq!(
167            odb.tree_entry_at_path(&root, b"sub").unwrap().unwrap().mode,
168            0o160000
169        );
170    }
171
172    #[test]
173    fn missing_paths_are_none() {
174        let tmp = TempDir::new().unwrap();
175        let odb = Odb::new(tmp.path());
176        let (root, ..) = fixture(&odb);
177
178        for path in [
179            &b"absent"[..],
180            b"dir/absent",
181            b"dir/nested/b/deeper",
182            b"file/child",
183            b"sub/child",
184            b"",
185            b"dir/",
186            b"/dir",
187            b"dir//a",
188            b"di",
189        ] {
190            assert_eq!(
191                odb.tree_entry_at_path(&root, path).unwrap(),
192                None,
193                "{path:?}"
194            );
195        }
196    }
197
198    #[test]
199    fn parsed_and_raw_cache_entries_agree() {
200        let tmp = TempDir::new().unwrap();
201        let odb = Odb::new(tmp.path());
202        let (root, ..) = fixture(&odb);
203        let raw = odb.tree_entry_at_path(&root, b"dir/a").unwrap();
204
205        let fresh = Odb::new(tmp.path());
206        fresh.cached_tree_entries(&root).unwrap();
207        assert_eq!(fresh.tree_entry_at_path(&root, b"dir/a").unwrap(), raw);
208        assert!(raw.is_some());
209    }
210
211    #[test]
212    fn non_tree_roots_and_missing_trees_are_errors() {
213        let tmp = TempDir::new().unwrap();
214        let odb = Odb::new(tmp.path());
215        let blob = odb.write(ObjectKind::Blob, b"not a tree").unwrap();
216        assert!(matches!(
217            odb.tree_entry_at_path(&blob, b"x"),
218            Err(Error::CorruptObject(_))
219        ));
220
221        let missing = ObjectId::from_hex("2222222222222222222222222222222222222222").unwrap();
222        assert!(matches!(
223            odb.tree_entry_at_path(&missing, b"x"),
224            Err(Error::ObjectNotFound(_))
225        ));
226    }
227}
grit_lib/odb/tree.rs

grit_lib/odb/
tree.rs
