gix_index/extension/tree/
verify.rs

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

gix_index/extension/tree/
verify.rs
