git_index/extension/tree/
verify.rs

1use std::cmp::Ordering;
2
3use bstr::{BString, ByteSlice};
4
5use crate::extension::Tree;
6
7/// The error returned by [Tree::verify()][crate::extension::Tree::verify()].
8#[derive(Debug, thiserror::Error)]
9#[allow(missing_docs)]
10pub enum Error {
11    #[error("The entry {entry_id} at path '{name}' in parent tree {parent_id} wasn't found in the nodes children, making it incomplete")]
12    MissingTreeDirectory {
13        parent_id: git_hash::ObjectId,
14        entry_id: git_hash::ObjectId,
15        name: BString,
16    },
17    #[error("The tree with id {oid} wasn't found in the object database")]
18    TreeNodeNotFound { oid: git_hash::ObjectId },
19    #[error("The tree with id {oid} should have {expected_childcount} children, but its cached representation had {actual_childcount} of them")]
20    TreeNodeChildcountMismatch {
21        oid: git_hash::ObjectId,
22        expected_childcount: usize,
23        actual_childcount: usize,
24    },
25    #[error("The root tree was named '{name}', even though it should be empty")]
26    RootWithName { name: BString },
27    #[error(
28        "Expected not more than {expected} entries to be reachable from the top-level, but actual count was {actual}"
29    )]
30    EntriesCount { actual: u32, expected: u32 },
31    #[error(
32        "Parent tree '{parent_id}' contained out-of order trees prev = '{previous_path}' and next = '{current_path}'"
33    )]
34    OutOfOrder {
35        parent_id: git_hash::ObjectId,
36        current_path: BString,
37        previous_path: BString,
38    },
39}
40
41impl Tree {
42    ///
43    pub fn verify<F>(&self, use_find: bool, mut find: F) -> Result<(), Error>
44    where
45        F: for<'a> FnMut(&git_hash::oid, &'a mut Vec<u8>) -> Option<git_object::TreeRefIter<'a>>,
46    {
47        fn verify_recursive<F>(
48            parent_id: git_hash::ObjectId,
49            children: &[Tree],
50            mut find_buf: Option<&mut Vec<u8>>,
51            find: &mut F,
52        ) -> Result<Option<u32>, Error>
53        where
54            F: for<'a> FnMut(&git_hash::oid, &'a mut Vec<u8>) -> Option<git_object::TreeRefIter<'a>>,
55        {
56            if children.is_empty() {
57                return Ok(None);
58            }
59            let mut entries = 0;
60            let mut prev = None::<&Tree>;
61            for child in children {
62                entries += child.num_entries.unwrap_or(0);
63                if let Some(prev) = prev {
64                    if prev.name.cmp(&child.name) != Ordering::Less {
65                        return Err(Error::OutOfOrder {
66                            parent_id,
67                            previous_path: prev.name.as_bstr().into(),
68                            current_path: child.name.as_bstr().into(),
69                        });
70                    }
71                }
72                prev = Some(child);
73            }
74            if let Some(buf) = find_buf.as_mut() {
75                let tree_entries = find(&parent_id, buf).ok_or(Error::TreeNodeNotFound { oid: parent_id })?;
76                let mut num_entries = 0;
77                for entry in tree_entries
78                    .filter_map(Result::ok)
79                    .filter(|e| e.mode == git_object::tree::EntryMode::Tree)
80                {
81                    children
82                        .binary_search_by(|e| e.name.as_bstr().cmp(entry.filename))
83                        .map_err(|_| Error::MissingTreeDirectory {
84                            parent_id,
85                            entry_id: entry.oid.to_owned(),
86                            name: entry.filename.to_owned(),
87                        })?;
88                    num_entries += 1;
89                }
90
91                if num_entries != children.len() {
92                    return Err(Error::TreeNodeChildcountMismatch {
93                        oid: parent_id,
94                        expected_childcount: num_entries,
95                        actual_childcount: children.len(),
96                    });
97                }
98            }
99            for child in children {
100                // This is actually needed here as it's a mut ref, which isn't copy. We do a re-borrow here.
101                #[allow(clippy::needless_option_as_deref)]
102                let actual_num_entries = verify_recursive(child.id, &child.children, find_buf.as_deref_mut(), find)?;
103                if let Some((actual, num_entries)) = actual_num_entries.zip(child.num_entries) {
104                    if actual > num_entries {
105                        return Err(Error::EntriesCount {
106                            actual,
107                            expected: num_entries,
108                        });
109                    }
110                }
111            }
112            Ok(entries.into())
113        }
114
115        if !self.name.is_empty() {
116            return Err(Error::RootWithName {
117                name: self.name.as_bstr().into(),
118            });
119        }
120
121        let mut buf = Vec::new();
122        let declared_entries = verify_recursive(self.id, &self.children, use_find.then_some(&mut buf), &mut find)?;
123        if let Some((actual, num_entries)) = declared_entries.zip(self.num_entries) {
124            if actual > num_entries {
125                return Err(Error::EntriesCount {
126                    actual,
127                    expected: num_entries,
128                });
129            }
130        }
131
132        Ok(())
133    }
134}
git_index/extension/tree/verify.rs

git_index/extension/tree/
verify.rs
