← snapshot

//! Trees: directories in the DAG.

use core::fmt;

use jac_core::{BlobId, TreeId};
use thiserror::Error;

/// A single path segment naming a tree entry.
///
/// Validated at construction: non-empty, no `/`, not `.` or `..`. The same
/// rules as [`jac_core::RepoPath`] segments, enforced here so a tree can
/// never contain a name that a path could not reach.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Segment(String);

impl Segment {
    /// Parses and validates a segment.
    ///
    /// # Errors
    ///
    /// Returns [`TreeError::InvalidSegment`] for an empty segment, a segment
    /// containing `/`, or `.`/`..`.
    pub fn parse(s: &str) -> Result<Self, TreeError> {
        if s.is_empty() || s.contains('/') || s == "." || s == ".." {
            return Err(TreeError::InvalidSegment);
        }
        Ok(Self(s.to_owned()))
    }

    /// The segment as a string slice.
    #[must_use]
    pub fn as_str(&self) -> &str {
        &self.0
    }
}

impl fmt::Display for Segment {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(&self.0)
    }
}

/// What a tree entry points at.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum TreeNode {
    /// File content.
    Blob(BlobId),
    /// A subdirectory.
    Tree(TreeId),
}

/// One named entry in a tree.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct TreeEntry {
    /// The entry's name within this directory.
    pub name: Segment,
    /// What the name points at.
    pub node: TreeNode,
}

/// A directory: named references to blobs and subtrees.
///
/// Entries are held sorted by name and duplicate-free — enforced by the only
/// constructor, so equal directories always hash equal. There is no `push`:
/// a tree is made whole or not at all, because an incrementally-mutated tree
/// is how two spellings of the same directory end up with two ids.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Tree {
    entries: Vec<TreeEntry>,
}

impl Tree {
    /// Builds a tree from entries, sorting by name.
    ///
    /// # Errors
    ///
    /// Returns [`TreeError::DuplicateName`] if two entries share a name.
    pub fn new(mut entries: Vec<TreeEntry>) -> Result<Self, TreeError> {
        entries.sort_by(|a, b| a.name.cmp(&b.name));
        for pair in entries.windows(2) {
            if pair[0].name == pair[1].name {
                return Err(TreeError::DuplicateName);
            }
        }
        Ok(Self { entries })
    }

    /// The empty tree.
    #[must_use]
    pub const fn empty() -> Self {
        Self {
            entries: Vec::new(),
        }
    }

    /// The entries, sorted by name.
    #[must_use]
    pub fn entries(&self) -> &[TreeEntry] {
        &self.entries
    }
}

/// Failures constructing tree values.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Error)]
#[non_exhaustive]
pub enum TreeError {
    /// A segment was empty, contained `/`, or was `.`/`..`.
    #[error("invalid tree entry name")]
    InvalidSegment,
    /// Two entries shared a name.
    #[error("duplicate name in tree")]
    DuplicateName,
}

#[cfg(test)]
#[expect(
    clippy::unwrap_used,
    reason = "test assertions read better with unwrap"
)]
mod tests {
    use jac_core::Digest;

    use super::*;

    fn blob_entry(name: &str) -> TreeEntry {
        TreeEntry {
            name: Segment::parse(name).unwrap(),
            node: TreeNode::Blob(BlobId::from_digest(Digest::of(name.as_bytes()))),
        }
    }

    #[test]
    fn entries_are_sorted_regardless_of_input_order() {
        let a = Tree::new(vec![blob_entry("b"), blob_entry("a")]).unwrap();
        let b = Tree::new(vec![blob_entry("a"), blob_entry("b")]).unwrap();
        assert_eq!(a, b);
    }

    #[test]
    fn duplicates_are_rejected() {
        assert_eq!(
            Tree::new(vec![blob_entry("a"), blob_entry("a")]),
            Err(TreeError::DuplicateName)
        );
    }

    #[test]
    fn bad_segments_are_rejected() {
        for bad in ["", "a/b", ".", ".."] {
            assert!(Segment::parse(bad).is_err(), "{bad:?} should be rejected");
        }
    }
}