4 files changed, 263 insertions, 0 deletions
diff --git a/vendor/gix-index/src/extension/tree/decode.rs b/vendor/gix-index/src/extension/tree/decode.rs
new file mode 100644
index 000000000..82221b48c
--- /dev/null
+++ b/vendor/gix-index/src/extension/tree/decode.rs
@@ -0,0 +1,63 @@
+use std::convert::TryInto;
+
+use gix_hash::ObjectId;
+
+use crate::{
+    extension::Tree,
+    util::{split_at_byte_exclusive, split_at_pos},
+};
+
+/// A recursive data structure
+pub fn decode(data: &[u8], object_hash: gix_hash::Kind) -> Option<Tree> {
+    let (tree, data) = one_recursive(data, object_hash.len_in_bytes())?;
+    assert!(
+        data.is_empty(),
+        "BUG: should fully consume the entire tree extension chunk, got {} left",
+        data.len()
+    );
+    Some(tree)
+}
+
+fn one_recursive(data: &[u8], hash_len: usize) -> Option<(Tree, &[u8])> {
+    let (path, data) = split_at_byte_exclusive(data, 0)?;
+
+    let (entry_count, data) = split_at_byte_exclusive(data, b' ')?;
+    let num_entries: i32 = btoi::btoi(entry_count).ok()?;
+
+    let (subtree_count, data) = split_at_byte_exclusive(data, b'\n')?;
+    let subtree_count: usize = btoi::btou(subtree_count).ok()?;
+
+    let (id, mut data) = if num_entries >= 0 {
+        let (hash, data) = split_at_pos(data, hash_len)?;
+        (ObjectId::from(hash), data)
+    } else {
+        (
+            ObjectId::null(gix_hash::Kind::from_hex_len(hash_len * 2).expect("valid hex_len")),
+            data,
+        )
+    };
+
+    let mut subtrees = Vec::with_capacity(subtree_count);
+    for _ in 0..subtree_count {
+        let (tree, rest) = one_recursive(data, hash_len)?;
+        subtrees.push(tree);
+        data = rest;
+    }
+
+    subtrees.sort_by(|a, b| a.name.cmp(&b.name));
+    let num_trees = subtrees.len();
+    subtrees.dedup_by(|a, b| a.name == b.name);
+    if num_trees != subtrees.len() {
+        return None;
+    }
+
+    Some((
+        Tree {
+            id,
+            num_entries: num_entries.try_into().ok(),
+            name: path.into(),
+            children: subtrees,
+        },
+        data,
+    ))
+}
diff --git a/vendor/gix-index/src/extension/tree/mod.rs b/vendor/gix-index/src/extension/tree/mod.rs
new file mode 100644
index 000000000..f20759399
--- /dev/null
+++ b/vendor/gix-index/src/extension/tree/mod.rs
@@ -0,0 +1,21 @@
+use crate::extension::Signature;
+
+/// The signature for tree extensions
+pub const SIGNATURE: Signature = *b"TREE";
+
+///
+pub mod verify;
+
+mod decode;
+pub use decode::decode;
+
+mod write;
+
+#[cfg(test)]
+mod tests {
+
+    #[test]
+    fn size_of_tree() {
+        assert_eq!(std::mem::size_of::<crate::extension::Tree>(), 88);
+    }
+}
diff --git a/vendor/gix-index/src/extension/tree/verify.rs b/vendor/gix-index/src/extension/tree/verify.rs
new file mode 100644
index 000000000..82fd03c8c
--- /dev/null
+++ b/vendor/gix-index/src/extension/tree/verify.rs
@@ -0,0 +1,134 @@
+use std::cmp::Ordering;
+
+use bstr::{BString, ByteSlice};
+
+use crate::extension::Tree;
+
+/// The error returned by [Tree::verify()][crate::extension::Tree::verify()].
+#[derive(Debug, thiserror::Error)]
+#[allow(missing_docs)]
+pub enum Error {
+    #[error("The entry {entry_id} at path '{name}' in parent tree {parent_id} wasn't found in the nodes children, making it incomplete")]
+    MissingTreeDirectory {
+        parent_id: gix_hash::ObjectId,
+        entry_id: gix_hash::ObjectId,
+        name: BString,
+    },
+    #[error("The tree with id {oid} wasn't found in the object database")]
+    TreeNodeNotFound { oid: gix_hash::ObjectId },
+    #[error("The tree with id {oid} should have {expected_childcount} children, but its cached representation had {actual_childcount} of them")]
+    TreeNodeChildcountMismatch {
+        oid: gix_hash::ObjectId,
+        expected_childcount: usize,
+        actual_childcount: usize,
+    },
+    #[error("The root tree was named '{name}', even though it should be empty")]
+    RootWithName { name: BString },
+    #[error(
+        "Expected not more than {expected} entries to be reachable from the top-level, but actual count was {actual}"
+    )]
+    EntriesCount { actual: u32, expected: u32 },
+    #[error(
+        "Parent tree '{parent_id}' contained out-of order trees prev = '{previous_path}' and next = '{current_path}'"
+    )]
+    OutOfOrder {
+        parent_id: gix_hash::ObjectId,
+        current_path: BString,
+        previous_path: BString,
+    },
+}
+
+impl Tree {
+    ///
+    pub fn verify<F>(&self, use_find: bool, mut find: F) -> Result<(), Error>
+    where
+        F: for<'a> FnMut(&gix_hash::oid, &'a mut Vec<u8>) -> Option<gix_object::TreeRefIter<'a>>,
+    {
+        fn verify_recursive<F>(
+            parent_id: gix_hash::ObjectId,
+            children: &[Tree],
+            mut find_buf: Option<&mut Vec<u8>>,
+            find: &mut F,
+        ) -> Result<Option<u32>, Error>
+        where
+            F: for<'a> FnMut(&gix_hash::oid, &'a mut Vec<u8>) -> Option<gix_object::TreeRefIter<'a>>,
+        {
+            if children.is_empty() {
+                return Ok(None);
+            }
+            let mut entries = 0;
+            let mut prev = None::<&Tree>;
+            for child in children {
+                entries += child.num_entries.unwrap_or(0);
+                if let Some(prev) = prev {
+                    if prev.name.cmp(&child.name) != Ordering::Less {
+                        return Err(Error::OutOfOrder {
+                            parent_id,
+                            previous_path: prev.name.as_bstr().into(),
+                            current_path: child.name.as_bstr().into(),
+                        });
+                    }
+                }
+                prev = Some(child);
+            }
+            if let Some(buf) = find_buf.as_mut() {
+                let tree_entries = find(&parent_id, buf).ok_or(Error::TreeNodeNotFound { oid: parent_id })?;
+                let mut num_entries = 0;
+                for entry in tree_entries
+                    .filter_map(Result::ok)
+                    .filter(|e| e.mode == gix_object::tree::EntryMode::Tree)
+                {
+                    children
+                        .binary_search_by(|e| e.name.as_bstr().cmp(entry.filename))
+                        .map_err(|_| Error::MissingTreeDirectory {
+                            parent_id,
+                            entry_id: entry.oid.to_owned(),
+                            name: entry.filename.to_owned(),
+                        })?;
+                    num_entries += 1;
+                }
+
+                if num_entries != children.len() {
+                    return Err(Error::TreeNodeChildcountMismatch {
+                        oid: parent_id,
+                        expected_childcount: num_entries,
+                        actual_childcount: children.len(),
+                    });
+                }
+            }
+            for child in children {
+                // This is actually needed here as it's a mut ref, which isn't copy. We do a re-borrow here.
+                #[allow(clippy::needless_option_as_deref)]
+                let actual_num_entries = verify_recursive(child.id, &child.children, find_buf.as_deref_mut(), find)?;
+                if let Some((actual, num_entries)) = actual_num_entries.zip(child.num_entries) {
+                    if actual > num_entries {
+                        return Err(Error::EntriesCount {
+                            actual,
+                            expected: num_entries,
+                        });
+                    }
+                }
+            }
+            Ok(entries.into())
+        }
+
+        if !self.name.is_empty() {
+            return Err(Error::RootWithName {
+                name: self.name.as_bstr().into(),
+            });
+        }
+
+        let mut buf = Vec::new();
+        let declared_entries = verify_recursive(self.id, &self.children, use_find.then_some(&mut buf), &mut find)?;
+        if let Some((actual, num_entries)) = declared_entries.zip(self.num_entries) {
+            if actual > num_entries {
+                return Err(Error::EntriesCount {
+                    actual,
+                    expected: num_entries,
+                });
+            }
+        }
+
+        Ok(())
+    }
+}
diff --git a/vendor/gix-index/src/extension/tree/write.rs b/vendor/gix-index/src/extension/tree/write.rs
new file mode 100644
index 000000000..2b1e3d949
--- /dev/null
+++ b/vendor/gix-index/src/extension/tree/write.rs
@@ -0,0 +1,45 @@
+use std::convert::TryFrom;
+
+use crate::extension::{tree, Tree};
+
+impl Tree {
+    /// Serialize this instance to `out`.
+    pub fn write_to(&self, mut out: impl std::io::Write) -> Result<(), std::io::Error> {
+        fn tree_entry(out: &mut impl std::io::Write, tree: &Tree) -> Result<(), std::io::Error> {
+            let mut buf = itoa::Buffer::new();
+            let num_entries = match tree.num_entries {
+                Some(num_entries) => buf.format(num_entries),
+                None => buf.format(-1),
+            };
+
+            out.write_all(tree.name.as_slice())?;
+            out.write_all(b"\0")?;
+            out.write_all(num_entries.as_bytes())?;
+            out.write_all(b" ")?;
+            let num_children = buf.format(tree.children.len());
+            out.write_all(num_children.as_bytes())?;
+            out.write_all(b"\n")?;
+            if tree.num_entries.is_some() {
+                out.write_all(tree.id.as_bytes())?;
+            }
+
+            for child in &tree.children {
+                tree_entry(out, child)?;
+            }
+
+            Ok(())
+        }
+
+        let signature = tree::SIGNATURE;
+
+        let estimated_size = self.num_entries.unwrap_or(0) * (300 + 3 + 1 + 3 + 1 + 20);
+        let mut entries: Vec<u8> = Vec::with_capacity(estimated_size as usize);
+        tree_entry(&mut entries, self)?;
+
+        out.write_all(&signature)?;
+        out.write_all(&(u32::try_from(entries.len()).expect("less than 4GB tree extension")).to_be_bytes())?;
+        out.write_all(&entries)?;
+
+        Ok(())
+    }
+}