girt 0.14.0

//! Directory snapshots as byte names, entry modes, and object identities.
//!
//! Use [`Tree`] for one directory. Each [`TreeEntry`] names a blob, subtree, or gitlink. A commit
//! names the root tree; subdirectories are other tree objects, not slash-containing names in one
//! tree. Regular files, executable files, and symlinks all point to blobs. For a symlink the blob
//! stores the link target bytes. A gitlink names a commit in another repository; traversal treats
//! it as a leaf.
//!
//! # Construct a directory snapshot
//!
//! ```
//! use girt::{EntryMode, ObjectFormat, ObjectId, Tree, TreeEntry};
//! let format = ObjectFormat::Sha1;
//! let tree = Tree::new(
//!     format,
//!     vec![TreeEntry {
//!         mode: EntryMode::Blob,
//!         name: b"README.md".to_vec(),
//!         id: ObjectId::for_blob(format, b"# Project\n"),
//!     }],
//! )?;
//! assert_eq!(tree.entries()[0].name, b"README.md");
//! assert_eq!(Tree::parse(format, &tree.encode())?.id(), tree.id());
//! # Ok::<(), girt::TreeError>(())
//! ```
//!
//! This creates no storage and does not check whether the referenced blob exists. Write the blob
//! and then [`crate::LooseObjects::write_tree`] to store a complete snapshot. Use
//! [`crate::Objects::compare_trees`] to compare snapshots, and [`crate::checkout`] to apply one
//! under that module's filesystem policy.
//!
//! # Parsing and validation
//!
//! [`Tree::parse`] preserves accepted bytes, including unusual ordering and mode spellings.
//! [`Tree::validate`] checks names, uniqueness, and Git ordering; [`Tree::new`] validates names and
//! sorts caller-supplied entries. Reconstructing a parsed tree can change its ID. Inspection tools
//! can retain a parsed tree after validation fails and report individual records.
//!
//! [`TreeError`] separates malformed records from invalid names or ordering. Correct
//! caller-supplied entries before construction; report malformed stored bytes instead of silently
//! repairing them. Names are raw bytes, not paths safe for every operating system. Structural
//! validity is not checkout safety. Memory grows with the input; bound storage reads before
//! parsing.

#![warn(
    clippy::unwrap_used,
    clippy::expect_used,
    clippy::panic,
    clippy::unreachable,
    clippy::indexing_slicing,
    reason = "parses untrusted repository or network input (#103)"
)]
mod editor;
use std::cmp::Ordering;
use std::collections::HashSet;

pub use editor::{TreeEditor, TreeWriteError};

use crate::{ObjectId, ObjectKind};

/// An owned, in-memory Git tree in an explicitly selected object format: names, modes, and
/// references to other objects.
///
/// A tree payload can be readable even when its entries violate tree rules. For example, two
/// records can both name `hello.txt`, or their names can be out of Git order. Inspection tools need
/// to read those records to report the problem, and an object's identity depends on its exact
/// encoded bytes, including entry order. Sorting or removing entries would create a different
/// object; rejecting them during parsing would prevent inspection through this API.
///
/// The operations therefore make separate promises:
///
/// - [`Tree::parse`] decodes supported records and preserves their bytes. Success means the modes,
///   delimiters, and format-sized IDs can be read; it does not establish valid names or ordering.
/// - [`Tree::validate`] checks component names, uniqueness, and Git order without changing entries.
///   Use it after parsing when your operation requires those properties. Inspection, hashing, and
///   exact re-encoding do not require it.
/// - [`Tree::new`] constructs a tree from caller-supplied entries. It rejects invalid or duplicate
///   names and sorts entries into Git order. Its result already passes validation.
///
/// A parsed tree remains available when validation fails, so callers can inspect its entries and
/// decide what to report or repair. A caller choosing to reconstruct it with [`Tree::new`] must
/// expect a changed identity if sorting changes the payload; invalid or duplicate names still need
/// an explicit correction. Validation returns a result, not a new type or a repaired tree.
///
/// Parsing interprets octal modes by type and owner-execute bits, including historical permission
/// bits and leading zeros. Other numeric types follow Git's gitlink interpretation. Only the low
/// mode bits affect interpretation; arbitrarily padded or large octal text is accepted, while
/// non-octal digits are rejected. [`Tree::new`] emits canonical [`EntryMode`] spellings. Every
/// accepted payload encodes byte-for-byte unchanged.
///
/// Names are bytes, without UTF-8 conversion. No operation resolves object references or checks
/// their existence or type. This API does not traverse directories, access storage, validate
/// checkout safety on a particular filesystem. Memory use is proportional
/// to the supplied payload; callers must bound input size when reading untrusted objects.
/// [`crate::LooseObjects::read_tree`] provides a payload limit for loose storage.
/// Use [`crate::LooseObjects::write_tree`] to store an existing tree without normalization.
///
/// ```
/// use girt::{EntryMode, ObjectId, Tree, TreeEntry};
///
/// let tree = Tree::new(
///     girt::ObjectFormat::Sha1,
///     vec![TreeEntry {
///         mode: EntryMode::Blob,
///         name: b"hello.txt".to_vec(),
///         id: ObjectId::for_blob(girt::ObjectFormat::Sha1, b"hello\n"),
///     }],
/// )?;
///
/// let payload = tree.encode();
/// let parsed = Tree::parse(girt::ObjectFormat::Sha1, &payload)?;
///
/// // Require valid names and ordering when accepting a payload from another source.
/// // This check is redundant for the unchanged encoding of Tree::new above.
/// parsed.validate()?;
///
/// assert_eq!(parsed.entries()[0].name, b"hello.txt");
/// assert_eq!(parsed.id(), tree.id());
/// # Ok::<(), girt::TreeError>(())
/// ```
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Tree {
    format: crate::ObjectFormat,
    entries: Vec<TreeEntry>,
    original: Vec<u8>,
}

impl Tree {
    /// Consumes entries in the selected format, validates them, and sorts them into Git's tree
    /// order.
    ///
    /// # Errors
    ///
    /// Returns [`TreeError::InvalidName`] for empty names, NUL, `/`, `.` or `..`, and
    /// [`TreeError::DuplicateName`] for repeated byte-identical names, regardless of mode.
    /// Names such as `.git` and platform-specific aliases are not checked: this is structural
    /// validation, not a complete `git fsck` or checkout-safety check. Object IDs are not validated
    /// against a database, and even all-zero IDs are preserved. Foreign-format IDs return
    /// [`TreeError::ObjectFormat`] before encoding.
    ///
    /// ```
    /// use girt::{EntryMode, ObjectFormat, ObjectId, Tree, TreeEntry};
    /// let format = ObjectFormat::Sha1;
    /// let tree = Tree::new(
    ///     format,
    ///     vec![TreeEntry {
    ///         mode: EntryMode::Blob,
    ///         name: b"notes.txt".to_vec(),
    ///         id: ObjectId::for_blob(format, b"notes\n"),
    ///     }],
    /// )?;
    /// assert_eq!(tree.entries()[0].name, b"notes.txt");
    /// # Ok::<(), girt::TreeError>(())
    /// ```
    pub fn new(
        format: crate::ObjectFormat,
        mut entries: Vec<TreeEntry>,
    ) -> Result<Self, TreeError> {
        for entry in &entries {
            entry.id.require_format(format)?;
        }
        validate_names(&entries)?;
        entries.sort_by(TreeEntry::git_cmp);
        let original = encode_entries(&entries);
        let tree = Self {
            format,
            entries,
            original,
        };
        Ok(tree)
    }

    /// Builds a tree from entries already validated and in Git order, as a directory of a
    /// validated index is: index paths sort exactly as Git orders tree entries.
    pub(crate) fn from_ordered(format: crate::ObjectFormat, entries: Vec<TreeEntry>) -> Self {
        debug_assert!(entries.iter().all(|e| e.id.format() == format));
        debug_assert!(validate_names(&entries).is_ok());
        debug_assert!(entries.is_sorted_by(|a, b| a.git_cmp(b).is_lt()));
        let original = encode_entries(&entries);
        Self {
            format,
            entries,
            original,
        }
    }

    /// Parses a tree payload, excluding the `tree <length>\0` object header.
    ///
    /// Copies names and IDs into owned entries. Does not sort or validate names or duplicates;
    /// [`Tree::validate`] provides that separate check. This allows inspection of readable but
    /// invalid trees, such as those containing duplicate names. Every accepted payload
    /// round-trips exactly.
    ///
    /// # Errors
    ///
    /// Returns an error for a missing mode/name delimiter, unsupported or malformed mode spelling,
    /// or fewer than `format.digest_len()` bytes for an entry's ID. The caller must select the
    /// payload's format; these binary records have no reliable format autodetection. Empty trees
    /// also retain the selected format for hashing.
    ///
    /// ```
    /// use girt::{EntryMode, ObjectFormat, ObjectId, Tree, TreeEntry};
    /// let format = ObjectFormat::Sha1;
    /// let tree = Tree::new(
    ///     format,
    ///     vec![TreeEntry {
    ///         mode: EntryMode::Blob,
    ///         name: b"notes.txt".to_vec(),
    ///         id: ObjectId::for_blob(format, b"notes\n"),
    ///     }],
    /// )?;
    /// let bytes = tree.encode();
    /// let parsed = Tree::parse(format, &bytes)?;
    /// assert_eq!(parsed.encode(), bytes);
    /// assert_eq!(parsed.id(), tree.id());
    /// # Ok::<(), girt::TreeError>(())
    /// ```
    pub fn parse(format: crate::ObjectFormat, payload: &[u8]) -> Result<Self, TreeError> {
        let original = payload.to_vec();
        let mut entries = Vec::new();
        for entry in RawEntries::new(format, payload) {
            let (mode, name, id) = entry?;
            entries.push(TreeEntry {
                mode,
                name: name.to_vec(),
                id,
            });
        }

        Ok(Self {
            format,
            entries,
            original,
        })
    }

    /// The format selected for this tree, including an empty tree.
    pub fn object_format(&self) -> crate::ObjectFormat {
        self.format
    }

    /// Borrows entries in their stored order, without allowing mutation of the tree.
    pub fn entries(&self) -> &[TreeEntry] {
        &self.entries
    }

    /// Checks structural names, unique names, and Git order without changing the tree.
    ///
    /// Call this after [`Tree::parse`] when accepting a tree for operations that rely on these
    /// properties. It is unnecessary for inspection or exact re-encoding, and redundant for a tree
    /// returned by [`Tree::new`]. Returns `Ok(())` on success; on failure, the tree remains
    /// available for inspection. Does not repair entries or check object references or checkout
    /// safety.
    ///
    /// # Errors
    ///
    /// Returns the name errors documented by [`Tree::new`], or [`TreeError::Unsorted`] if entries
    /// are out of Git order. The same object-reference and checkout-safety exclusions apply.
    ///
    /// ```
    /// use girt::{ObjectFormat, ObjectId, Tree, TreeError};
    /// let id = ObjectId::for_blob(ObjectFormat::Sha1, b"payload");
    /// let mut bytes = b"100644 .\0".to_vec();
    /// bytes.extend_from_slice(id.as_bytes());
    /// let parsed = Tree::parse(ObjectFormat::Sha1, &bytes)?;
    /// assert!(matches!(parsed.validate(), Err(TreeError::InvalidName)));
    /// // Inspection and exact retention remain possible after validation rejects the component.
    /// assert_eq!(parsed.entries()[0].name, b".");
    /// assert_eq!(parsed.encode(), bytes);
    /// # Ok::<(), girt::TreeError>(())
    /// ```
    pub fn validate(&self) -> Result<(), TreeError> {
        validate_names(&self.entries)?;

        if !self.entries.is_sorted_by(|a, b| a.git_cmp(b).is_le()) {
            return Err(TreeError::Unsorted);
        }

        Ok(())
    }

    /// Encodes the payload as repeated `mode SP name NUL raw-id` records.
    ///
    /// Returns an owned buffer without an object header or compression. Preserves parsed order and
    /// names even when [`Tree::validate`] would fail; never silently repairs an existing object.
    pub fn encode(&self) -> Vec<u8> {
        self.original.clone()
    }

    /// Hashes `tree <decimal payload length>\0` followed by the exact encoded payload.
    ///
    /// Hashes retained bytes directly without validation, normalization, or a temporary buffer.
    pub fn id(&self) -> ObjectId {
        self.format
            .hash_object(crate::ObjectKind::Tree, &self.original)
    }
}

fn encode_entries(entries: &[TreeEntry]) -> Vec<u8> {
    let mut payload = Vec::new();
    for entry in entries {
        payload.extend_from_slice(entry.mode.bytes());
        payload.push(b' ');
        payload.extend_from_slice(&entry.name);
        payload.push(0);
        payload.extend_from_slice(entry.id.as_bytes());
    }
    payload
}

/// Entries of a tree payload in stored order, borrowing their names.
///
/// Yields exactly what [`Tree::parse`] accepts and stops after the first error, which is the
/// error `Tree::parse` returns. Walks over many trees use this to avoid copying each payload and
/// name.
pub(crate) struct RawEntries<'a> {
    format: crate::ObjectFormat,
    payload: &'a [u8],
}

impl<'a> RawEntries<'a> {
    pub(crate) fn new(format: crate::ObjectFormat, payload: &'a [u8]) -> Self {
        Self { format, payload }
    }

    fn parse_one(&mut self) -> Result<(EntryMode, &'a [u8], ObjectId), TreeError> {
        let (mode, rest) =
            crate::bytes::split_once(self.payload, b' ').ok_or(TreeError::MissingModeDelimiter)?;
        let mode = EntryMode::parse(mode)?;
        let (name, rest) =
            crate::bytes::split_once(rest, 0).ok_or(TreeError::MissingNameDelimiter)?;
        let (raw_id, rest) = rest
            .split_at_checked(self.format.digest_len())
            .ok_or(TreeError::TruncatedObjectId)?;
        let id =
            ObjectId::from_bytes(self.format, raw_id).map_err(|_| TreeError::TruncatedObjectId)?;
        self.payload = rest;
        Ok((mode, name, id))
    }
}

impl<'a> Iterator for RawEntries<'a> {
    type Item = Result<(EntryMode, &'a [u8], ObjectId), TreeError>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.payload.is_empty() {
            return None;
        }
        let entry = self.parse_one();
        if entry.is_err() {
            self.payload = &[];
        }
        Some(entry)
    }
}

/// One tree entry, with an uninterpreted byte name and a format-bearing reference.
///
/// Fields are freely editable before construction. [`Tree::new`] checks names and duplicates.
///
/// ```
/// use girt::{EntryMode, ObjectFormat, ObjectId, Tree, TreeEntry};
/// let format = ObjectFormat::Sha1;
/// let tree = Tree::new(
///     format,
///     vec![TreeEntry {
///         mode: EntryMode::Blob,
///         name: b"notes.txt".to_vec(),
///         id: ObjectId::for_blob(format, b"notes\n"),
///     }],
/// )?;
/// assert_eq!(tree.entries()[0].mode, EntryMode::Blob);
/// # Ok::<(), girt::TreeError>(())
/// ```
#[derive(Clone, Debug, Eq, Hash, PartialEq)]
pub struct TreeEntry {
    /// The entry's Git type and executable status.
    pub mode: EntryMode,

    /// A single path component as bytes, without text conversion.
    pub name: Vec<u8>,

    /// Referenced blob, tree, or commit identity; existence and type are not checked.
    pub id: ObjectId,
}

impl TreeEntry {
    /// Compares names using Git's byte order, treating a tree's name as ending in `/`.
    ///
    /// Other modes, including gitlinks, use a NUL terminator. IDs do not affect order. For example,
    /// file `a.c` precedes tree `a`, which precedes file `a0`. This does not validate names; the
    /// Git ordering contract applies to valid single-component names.
    pub fn git_cmp(&self, other: &Self) -> Ordering {
        let left = self
            .name
            .iter()
            .copied()
            .chain(std::iter::once(self.mode.terminator()));
        let right = other
            .name
            .iter()
            .copied()
            .chain(std::iter::once(other.mode.terminator()));

        left.cmp(right)
    }
}

/// Supported modes with their exact octal spelling in an encoded tree payload.
///
/// ```
/// use girt::{EntryMode, ObjectFormat, ObjectId, Tree, TreeEntry};
/// let format = ObjectFormat::Sha1;
/// let blob = ObjectId::for_blob(format, b"#!/bin/sh\nexit 0\n");
/// let snapshot = |mode| {
///     Tree::new(
///         format,
///         vec![TreeEntry {
///             mode,
///             name: b"run.sh".to_vec(),
///             id: blob,
///         }],
///     )
/// };
/// let regular = snapshot(EntryMode::Blob)?;
/// let executable = snapshot(EntryMode::Executable)?;
/// assert_ne!(regular.id(), executable.id()); // Mode changes alter the tree, not the blob.
/// assert_eq!(regular.entries()[0].id, executable.entries()[0].id);
/// # Ok::<(), girt::TreeError>(())
/// ```
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
#[non_exhaustive]
pub enum EntryMode {
    /// Regular, non-executable blob (`100644`).
    Blob,
    /// Executable blob (`100755`).
    Executable,
    /// Symbolic link whose target bytes are stored in a blob (`120000`).
    Symlink,
    /// Subtree (`40000`, without a leading zero).
    Tree,
    /// Submodule commit reference (`160000`); ordered like a file, not a subtree.
    Gitlink,
}

impl EntryMode {
    /// Returns the six-digit octal mode Git prints, as in `git ls-tree` and `git diff` headers.
    ///
    /// Trees print as `040000`; tree objects store the same mode as `40000` without the leading
    /// zero, which [`Tree::new`] writes. This replaces matching each variant to a literal.
    ///
    /// ```
    /// use girt::EntryMode;
    ///
    /// assert_eq!(EntryMode::Executable.octal(), "100755");
    /// assert_eq!(EntryMode::Tree.octal(), "040000");
    /// ```
    #[must_use]
    pub fn octal(self) -> &'static str {
        match self {
            Self::Blob => "100644",
            Self::Executable => "100755",
            Self::Symlink => "120000",
            Self::Tree => "040000",
            Self::Gitlink => "160000",
        }
    }

    /// Returns the kind of object an entry with this mode names.
    ///
    /// Blobs, executables and symlinks name blobs, trees name trees and gitlinks name commits in
    /// another repository. [`ObjectKind::as_str`] gives the name `git ls-tree` prints.
    ///
    /// ```
    /// use girt::{EntryMode, ObjectKind};
    ///
    /// assert_eq!(EntryMode::Symlink.object_kind(), ObjectKind::Blob);
    /// assert_eq!(EntryMode::Gitlink.object_kind().as_str(), "commit");
    /// ```
    #[must_use]
    pub fn object_kind(self) -> ObjectKind {
        match self {
            Self::Blob | Self::Executable | Self::Symlink => ObjectKind::Blob,
            Self::Tree => ObjectKind::Tree,
            Self::Gitlink => ObjectKind::Commit,
        }
    }

    fn bytes(self) -> &'static [u8] {
        match self {
            Self::Blob => b"100644",
            Self::Executable => b"100755",
            Self::Symlink => b"120000",
            Self::Tree => b"40000",
            Self::Gitlink => b"160000",
        }
    }

    fn parse(bytes: &[u8]) -> Result<Self, TreeError> {
        if bytes.is_empty() {
            return Err(TreeError::UnsupportedMode);
        }
        let mut mode = 0u32;
        for &byte in bytes {
            if !(b'0'..=b'7').contains(&byte) {
                return Err(TreeError::UnsupportedMode);
            }
            mode = mode.wrapping_mul(8).wrapping_add(u32::from(byte - b'0'));
        }
        // Interpret the type and owner-execute bit as Git's tree readers do.
        Ok(match mode & 0o170000 {
            0o040000 => Self::Tree,
            0o100000 if mode & 0o100 != 0 => Self::Executable,
            0o100000 => Self::Blob,
            0o120000 => Self::Symlink,
            _ => Self::Gitlink,
        })
    }

    fn terminator(self) -> u8 {
        if self == Self::Tree { b'/' } else { 0 }
    }
}

/// A tree payload could not be parsed, or entries failed structural validation.
#[derive(Clone, Copy, Debug, Eq, PartialEq, thiserror::Error)]
#[non_exhaustive]
pub enum TreeError {
    /// An entry identity differs from the selected tree format.
    /// Use IDs in the selected tree format; do not truncate or pad digests.
    #[error(transparent)]
    ObjectFormat(#[from] crate::ObjectFormatError),
    /// No space separates the mode from the name.
    /// Report the original malformed payload; newly encoded entries need a mode followed by a
    /// space.
    #[error("missing tree mode delimiter")]
    MissingModeDelimiter,
    /// The mode is empty or contains non-octal bytes.
    /// Supply octal mode text or retain the unreadable stored object for diagnostics.
    #[error("unsupported or malformed tree entry mode")]
    UnsupportedMode,
    /// No NUL separates the name from the raw identity.
    /// Report the malformed record; names and digest bytes need a NUL separator.
    #[error("missing tree name delimiter")]
    MissingNameDelimiter,
    /// Fewer than the selected format's raw identity bytes follow the name delimiter.
    /// Read the full payload and verify its format; a larger parser tolerance cannot reconstruct
    /// missing digest bytes.
    #[error("truncated tree entry object identity")]
    TruncatedObjectId,
    /// A name is empty, contains NUL or `/`, or is `.` or `..`.
    /// Correct the component explicitly before construction; retain parsed bytes when inspecting
    /// stored data.
    #[error("invalid tree entry name")]
    InvalidName,
    /// Two entries have byte-identical names, even if their modes differ.
    /// Choose which same-name entry the intended snapshot contains before reconstructing it.
    #[error("duplicate tree entry name")]
    DuplicateName,
    /// Entries are not in Git's tree order.
    /// Use [`Tree::new`] for intentional canonical construction; sorting an imported tree changes
    /// its identity.
    #[error("tree entries are not in Git order")]
    Unsorted,
}

fn validate_names(entries: &[TreeEntry]) -> Result<(), TreeError> {
    let mut names = HashSet::with_capacity(entries.len());

    for entry in entries {
        let name = entry.name.as_slice();
        if name.is_empty()
            || name.contains(&0)
            || name.contains(&b'/')
            || name == b"."
            || name == b".."
        {
            return Err(TreeError::InvalidName);
        }

        // Duplicate file/tree names need not be adjacent in Git order (a, a.c, a/).
        if !names.insert(name) {
            return Err(TreeError::DuplicateName);
        }
    }

    Ok(())
}

#[cfg(test)]
mod tests {
    use rstest::rstest;

    use super::*;

    fn entry(mode: EntryMode, name: &[u8]) -> TreeEntry {
        TreeEntry {
            mode,
            name: name.to_vec(),
            id: ObjectId::Sha1([0x81; 20]),
        }
    }

    // Literal framing plus a fixed identity keeps expected bytes independent of the encoder.
    fn record(prefix: &[u8]) -> Vec<u8> {
        [prefix, &[0x81; 20]].concat()
    }

    #[rstest]
    #[case::mode_without_space(b"100644".as_slice(), TreeError::MissingModeDelimiter)]
    #[case::name_without_nul(b"100644 a", TreeError::MissingNameDelimiter)]
    #[case::delimiters_at_end(b"100644 \0", TreeError::TruncatedObjectId)]
    #[case::short_id(&[b"100644 a\0".as_slice(), &[0x81; 19]].concat(), TreeError::TruncatedObjectId)]
    fn rejects_truncated_entry(#[case] payload: &[u8], #[case] expected: TreeError) {
        assert_eq!(
            Tree::parse(crate::ObjectFormat::Sha1, payload),
            Err(expected)
        );
    }

    #[test]
    fn empty_tree_has_git_identity() {
        let tree = Tree::new(crate::ObjectFormat::Sha1, vec![]).unwrap();

        assert_eq!(tree.encode(), b"");
        assert_eq!(Tree::parse(crate::ObjectFormat::Sha1, b"").unwrap(), tree);
        assert_eq!(tree.validate(), Ok(()));
        assert_eq!(
            tree.id().to_string(),
            "4b825dc642cb6eb9a060e54bf8d69288fbee4904"
        );
    }

    #[rstest]
    #[case::regular(EntryMode::Blob, b"100644 a\0")]
    #[case::executable(EntryMode::Executable, b"100755 a\0")]
    #[case::symlink(EntryMode::Symlink, b"120000 a\0")]
    #[case::directory(EntryMode::Tree, b"40000 a\0")]
    #[case::gitlink(EntryMode::Gitlink, b"160000 a\0")]
    fn preserves_supported_modes(#[case] mode: EntryMode, #[case] prefix: &[u8]) {
        let expected = record(prefix);
        let tree = Tree::new(crate::ObjectFormat::Sha1, vec![entry(mode, b"a")]).unwrap();

        assert_eq!(tree.encode(), expected);
        assert_eq!(
            Tree::parse(crate::ObjectFormat::Sha1, &expected)
                .unwrap()
                .entries(),
            &[entry(mode, b"a")]
        );
    }

    /// Delimiters inside the fixed-width ID must not split records or shift the next entry.
    #[test]
    fn preserves_delimiter_bytes_inside_object_id() {
        let raw_id = *b"\0 abcdefghijklmnop\0 ";
        let payload = [
            b"100644 a\0".as_slice(),
            &raw_id,
            b"100755 b\0",
            &[0x81; 20],
        ]
        .concat();

        let tree = Tree::parse(crate::ObjectFormat::Sha1, &payload).unwrap();

        assert_eq!(
            tree.entries(),
            &[
                TreeEntry {
                    mode: EntryMode::Blob,
                    name: b"a".to_vec(),
                    id: ObjectId::Sha1(raw_id),
                },
                entry(EntryMode::Executable, b"b"),
            ]
        );
        assert_eq!(tree.encode(), payload);
        assert_eq!(tree.validate(), Ok(()));
    }

    #[rstest]
    #[case::non_utf8(b"\xff\x80")]
    #[case::whitespace(b"a b\t\n")]
    #[case::backslash(b"a\\b")]
    fn preserves_name_bytes(#[case] name: &[u8]) {
        let expected = [b"100644 ".as_slice(), name, b"\0", &[0x81; 20]].concat();
        let tree = Tree::new(
            crate::ObjectFormat::Sha1,
            vec![entry(EntryMode::Blob, name)],
        )
        .unwrap();

        assert_eq!(tree.encode(), expected);
        assert_eq!(
            Tree::parse(crate::ObjectFormat::Sha1, &expected)
                .unwrap()
                .entries()[0]
                .name,
            name
        );
    }

    #[rstest]
    #[case::file_prefix(EntryMode::Blob, b"a", EntryMode::Blob, b"a.c")]
    #[case::directory_after_dot(EntryMode::Blob, b"a.c", EntryMode::Tree, b"a")]
    #[case::directory_before_zero(EntryMode::Tree, b"a", EntryMode::Blob, b"a0")]
    #[case::longer_directory(EntryMode::Tree, b"a", EntryMode::Tree, b"aa")]
    #[case::gitlink_is_file(EntryMode::Gitlink, b"a", EntryMode::Blob, b"a.c")]
    #[case::symlink_is_file(EntryMode::Symlink, b"a", EntryMode::Tree, b"a")]
    #[case::unsigned_bytes(EntryMode::Blob, b"z", EntryMode::Blob, b"\x80")]
    fn compares_git_names(
        #[case] left_mode: EntryMode,
        #[case] left_name: &[u8],
        #[case] right_mode: EntryMode,
        #[case] right_name: &[u8],
    ) {
        let left = entry(left_mode, left_name);
        let right = entry(right_mode, right_name);

        assert_eq!(left.git_cmp(&right), Ordering::Less);
        assert_eq!(right.git_cmp(&left), Ordering::Greater);
    }

    #[test]
    fn sorts_file_and_directory_prefixes() {
        let tree = Tree::new(
            crate::ObjectFormat::Sha1,
            vec![
                entry(EntryMode::Blob, b"a0"),
                entry(EntryMode::Tree, b"a"),
                entry(EntryMode::Blob, b"a.c"),
            ],
        )
        .unwrap();
        let names: Vec<_> = tree
            .entries()
            .iter()
            .map(|entry| entry.name.as_slice())
            .collect();

        assert_eq!(names, [b"a.c".as_slice(), b"a", b"a0"]);
        assert_eq!(tree.validate(), Ok(()));
    }

    #[rstest]
    #[case::empty(b"")]
    #[case::nul(b"a\0b")]
    #[case::slash(b"a/b")]
    #[case::dot(b".")]
    #[case::dot_dot(b"..")]
    fn rejects_invalid_new_names(#[case] name: &[u8]) {
        assert_eq!(
            Tree::new(
                crate::ObjectFormat::Sha1,
                vec![entry(EntryMode::Blob, name)]
            ),
            Err(TreeError::InvalidName)
        );
    }

    #[rstest]
    #[case::empty(b"100644 \0")]
    #[case::slash(b"100644 a/b\0")]
    #[case::dot(b"100644 .\0")]
    #[case::dot_dot(b"100644 ..\0")]
    fn parses_invalid_names_without_repair(#[case] prefix: &[u8]) {
        let payload = record(prefix);
        let tree = Tree::parse(crate::ObjectFormat::Sha1, &payload).unwrap();

        assert_eq!(tree.encode(), payload);
        assert_eq!(tree.validate(), Err(TreeError::InvalidName));
    }

    #[test]
    fn preserves_unsorted_input_until_explicit_reconstruction() {
        let payload = [record(b"40000 a\0"), record(b"100644 a.c\0")].concat();
        let tree = Tree::parse(crate::ObjectFormat::Sha1, &payload).unwrap();

        assert_eq!(tree.encode(), payload);
        assert_eq!(tree.validate(), Err(TreeError::Unsorted));

        let rebuilt = Tree::new(crate::ObjectFormat::Sha1, tree.entries().to_vec()).unwrap();

        assert_eq!(rebuilt.entries()[0].name, b"a.c");
        assert_ne!(rebuilt.id(), tree.id());
    }

    #[rstest]
    #[case::same_mode(b"100644 a\0")]
    #[case::different_mode(b"40000 a\0")]
    fn detects_duplicate_names_even_when_nonadjacent(#[case] last: &[u8]) {
        let payload = [record(b"100644 a\0"), record(b"100644 a.c\0"), record(last)].concat();
        let tree = Tree::parse(crate::ObjectFormat::Sha1, &payload).unwrap();

        assert_eq!(tree.encode(), payload);
        assert_eq!(tree.validate(), Err(TreeError::DuplicateName));
        assert_eq!(
            Tree::new(crate::ObjectFormat::Sha1, tree.entries().to_vec()),
            Err(TreeError::DuplicateName)
        );
    }

    #[rstest]
    #[case::empty(b" a\0")]
    #[case::non_octal(b"100648 a\0")]
    #[case::negative(b"-100644 a\0")]
    fn rejects_unsupported_mode_spellings(#[case] prefix: &[u8]) {
        assert_eq!(
            Tree::parse(crate::ObjectFormat::Sha1, &record(prefix)),
            Err(TreeError::UnsupportedMode)
        );
    }

    #[rstest]
    #[case::missing_space(b"100644", TreeError::MissingModeDelimiter)]
    #[case::missing_nul(b"100644 name", TreeError::MissingNameDelimiter)]
    #[case::no_id(b"100644 a\0", TreeError::TruncatedObjectId)]
    #[case::short_id(b"100644 a\0abcdefghijklmnopqrs", TreeError::TruncatedObjectId)]
    fn rejects_incomplete_records(#[case] payload: &[u8], #[case] error: TreeError) {
        assert_eq!(Tree::parse(crate::ObjectFormat::Sha1, payload), Err(error));
    }

    #[test]
    fn rejects_trailing_partial_entry() {
        let payload = [record(b"100644 a\0"), b"100644 b\0short".to_vec()].concat();

        assert_eq!(
            Tree::parse(crate::ObjectFormat::Sha1, &payload),
            Err(TreeError::TruncatedObjectId)
        );
    }
}

#[cfg(test)]
mod format_boundary_tests {
    use super::*;

    #[test]
    fn rejects_sha256_entry_before_encoding() {
        let result = Tree::new(
            crate::ObjectFormat::Sha1,
            vec![TreeEntry {
                mode: EntryMode::Blob,
                name: b"a".to_vec(),
                id: ObjectId::Sha256([1; 32]),
            }],
        );
        assert!(matches!(result, Err(TreeError::ObjectFormat(_))));
    }
}

#[cfg(test)]
mod dual_format_tests {
    use rstest::rstest;

    use super::*;
    use crate::ObjectFormat;

    #[rstest]
    #[case::sha1(ObjectFormat::Sha1, "4b825dc642cb6eb9a060e54bf8d69288fbee4904")]
    #[case::sha256(
        ObjectFormat::Sha256,
        "6ef19b41225c5369f1c104d45d8d85efa9b057b53b14b4b9b939dd74decc5321"
    )]
    fn empty_tree_retains_selected_identity(#[case] format: ObjectFormat, #[case] expected: &str) {
        let tree = Tree::new(format, vec![]).unwrap();
        assert_eq!(tree.id().to_string(), expected);
        assert_eq!(Tree::parse(format, b"").unwrap(), tree);
    }

    #[rstest]
    #[case::sha1(ObjectFormat::Sha1)]
    #[case::sha256(ObjectFormat::Sha256)]
    fn truncated_digest_is_rejected(#[case] format: ObjectFormat) {
        let mut bytes = b"160000 submodule\0".to_vec();
        bytes.extend(vec![1; format.digest_len() - 1]);
        assert_eq!(
            Tree::parse(format, &bytes),
            Err(TreeError::TruncatedObjectId)
        );
    }

    #[test]
    fn sha256_tree_rejects_sha1_gitlink() {
        assert!(matches!(
            Tree::new(
                ObjectFormat::Sha256,
                vec![TreeEntry {
                    mode: EntryMode::Gitlink,
                    name: b"submodule".to_vec(),
                    id: ObjectId::Sha1([1; 20])
                }]
            ),
            Err(TreeError::ObjectFormat(_))
        ));
    }
}