girt 0.2.0

use std::collections::BTreeMap;
use std::fs;
use std::io::Read;
use std::path::Path;
use std::sync::atomic::{AtomicBool, Ordering};

use super::store::{check_path, io_error, malformed, parse_loose, read_optional};
use super::{RefName, ReferenceError, References, Target};

/// A full reference name and its stored target, without symbolic resolution or tag peeling.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Reference {
    /// Exact reference-name bytes; enumeration excludes pseudorefs such as HEAD.
    pub name: RefName,
    /// Effective backend value. Symbolic targets may be missing or cyclic.
    pub target: Target,
}

impl References<'_> {
    pub(crate) fn head_controlled(
        &self,
        max_bytes: usize,
        cancel: &AtomicBool,
    ) -> Result<Option<Target>, ReferenceError> {
        let name = RefName::new(b"HEAD").expect("HEAD is a valid name");
        if self.repository.reference_backend() == super::Backend::Reftable {
            if cancel.load(Ordering::Relaxed) {
                return Err(ReferenceError::Cancelled);
            }
            let target = self.read(&name)?;
            if cancel.load(Ordering::Relaxed) {
                return Err(ReferenceError::Cancelled);
            }
            return Ok(target);
        }
        let mut budget = ScanBudget {
            entries: 1,
            bytes: max_bytes,
            cancel,
        };
        let path = self.path(&name)?;
        read_limited(&path, &mut budget)?
            .map(|bytes| parse_loose(self.repository.object_format(), &bytes, &path))
            .transpose()
    }

    /// Lists all `refs/` names in bytewise name order, without resolving symbolic refs.
    ///
    /// Reftable merges bounded common/private stack snapshots using [`References`]'s contract.
    /// The loose/packed traversal details below describe the files backend.
    ///
    /// Includes branches, tags, other shared namespaces, and the current worktree's private
    /// refs. Excludes HEAD, other pseudorefs, other worktrees' private refs, dot-prefixed entries
    /// and `.lock` entries. Empty directories contribute no refs. Loose targets shadow packed
    /// targets, even if symbolic; a malformed loose target fails instead of falling back.
    ///
    /// Reads and validates packed-refs once, then walks loose files without locks. The owned
    /// result is stable after return but is not a point-in-time snapshot: concurrent creation or
    /// deletion may be included or missed, and values can come from different times. A loose
    /// file that disappears during traversal is ignored; a previously read packed value can
    /// remain in the result. Callers must use an expected value when acting on these observations.
    /// Memory use is proportional to packed data, discovered refs, and pending directories;
    /// there is no configurable resource limit.
    ///
    /// # Errors
    ///
    /// Reports I/O errors, invalid names or targets, conflicting effective names, filesystem
    /// symlinks and non-regular files, or malformed/unsupported packed data. Returns no partial
    /// list on error and does not modify storage.
    pub fn list(&self) -> Result<Vec<Reference>, ReferenceError> {
        self.enumerate(None)
    }

    /// Lists references with aggregate files-backend byte and traversal limits.
    ///
    /// The entry limit covers packed names and loose directory entries before they are retained;
    /// the byte limit covers packed-refs and loose file contents. Reftable uses this handle's
    /// [`super::reftable::StackLimits`] for encoded/decoded data and applies the entry limit to
    /// its bounded merged output. Cancellation is checked between files and directory entries.
    /// A failed inventory returns no partial list and must not justify removing objects.
    ///
    /// # Errors
    ///
    /// Returns [`ReferenceError::Limit`] or [`ReferenceError::Cancelled`] at those boundaries,
    /// alongside the malformed, unsupported and I/O failures of [`Self::list`].
    pub fn list_controlled(
        &self,
        max_entries: usize,
        max_bytes: usize,
        cancel: &AtomicBool,
    ) -> Result<Vec<Reference>, ReferenceError> {
        let mut budget = ScanBudget {
            entries: max_entries,
            bytes: max_bytes,
            cancel,
        };
        self.enumerate_with_budget(None, Some(&mut budget))
    }

    /// Lists a full name and its descendants, using `/` as the namespace boundary.
    ///
    /// Use `refs/heads` for branches and `refs/tags` for tags. `refs/heads/topic` includes that
    /// exact ref or its descendants, but not `refs/heads/topic-two`. Missing namespaces return
    /// an empty list. Only selected loose paths are read; packed-refs is always fully validated.
    /// Ordering, symbolic behavior, private namespaces and live-read guarantees match
    /// [`Self::list`].
    ///
    /// # Errors
    ///
    /// Reports errors from [`Self::list`] within the selected loose namespace or anywhere in
    /// packed-refs. HEAD is unsupported here; use [`Self::read`] for pseudorefs.
    ///
    /// ```
    /// use girt::refs::{Expected, RefName, Target};
    /// use girt::{InitKind, ObjectId, Repository};
    /// let directory = tempfile::tempdir()?;
    /// let repo = Repository::init(
    ///     girt::ObjectFormat::Sha1,
    ///     directory.path().join("repo"),
    ///     InitKind::Bare,
    /// )?;
    /// let refs = repo.references()?;
    /// let tag = RefName::new(b"refs/tags/example")?;
    /// let value = Target::Direct(ObjectId::Sha1([1; 20]));
    /// // Reference storage does not require the target object to exist.
    /// refs.update_without_reflog(&tag, value.clone(), Expected::Absent)?;
    /// let tags = refs.list_namespace(&RefName::new(b"refs/tags")?)?;
    /// assert_eq!(tags[0].name, tag);
    /// refs.delete_without_reflog(&tag, Expected::Value(tags[0].target.clone()))?;
    /// assert!(refs.list()?.is_empty());
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    pub fn list_namespace(&self, namespace: &RefName) -> Result<Vec<Reference>, ReferenceError> {
        if namespace.as_bytes() == b"HEAD" {
            return Err(ReferenceError::Unsupported("enumerating pseudorefs"));
        }
        self.enumerate(Some(namespace))
    }

    fn enumerate(&self, namespace: Option<&RefName>) -> Result<Vec<Reference>, ReferenceError> {
        self.enumerate_with_budget(namespace, None)
    }

    fn enumerate_with_budget(
        &self,
        namespace: Option<&RefName>,
        mut budget: Option<&mut ScanBudget<'_>>,
    ) -> Result<Vec<Reference>, ReferenceError> {
        if let Some(budget) = budget.as_deref_mut() {
            budget.check()?;
        }
        if self.repository.reference_backend() == super::Backend::Reftable {
            let result = super::reftable::backend::list(self, namespace)?;
            if let Some(budget) = budget.as_deref_mut() {
                budget.check()?;
                if result.len() > budget.entries {
                    return Err(ReferenceError::Limit("reference entries"));
                }
            }
            return Ok(result);
        }
        let packed = if let Some(budget) = budget.as_deref_mut() {
            let path = self.repository.common_dir().join("packed-refs");
            let bytes = read_limited(&path, budget)?.unwrap_or_default();
            super::packed::parse(self.repository.object_format(), &bytes, &path)?
        } else {
            self.packed()?
        };
        if let Some(budget) = budget.as_deref_mut() {
            budget.charge(packed.len())?;
        }
        let mut entries: BTreeMap<_, _> = packed
            .into_iter()
            .filter(|(name, _)| selected(name.as_bytes(), namespace))
            .map(|(name, id)| (name, Target::Direct(id)))
            .collect();
        let separate = self.repository.git_dir() != self.repository.common_dir();
        collect_loose(
            self.repository.object_format(),
            self.repository.common_dir(),
            namespace,
            if separate {
                LooseScope::Shared
            } else {
                LooseScope::All
            },
            &mut entries,
            budget.as_deref_mut(),
        )?;
        if separate {
            collect_loose(
                self.repository.object_format(),
                self.repository.git_dir(),
                namespace,
                LooseScope::Private,
                &mut entries,
                budget,
            )?;
        }
        // Prefix conflicts are not necessarily adjacent in byte order (a, a.b, a/c).
        for name in entries.keys() {
            for (index, byte) in name.as_bytes().iter().enumerate().skip(5) {
                if *byte == b'/'
                    && RefName::new(&name.as_bytes()[..index])
                        .is_ok_and(|parent| entries.contains_key(&parent))
                {
                    return Err(ReferenceError::Conflict(self.path(name)?));
                }
            }
        }
        Ok(entries
            .into_iter()
            .map(|(name, target)| Reference { name, target })
            .collect())
    }
}

fn selected(name: &[u8], namespace: Option<&RefName>) -> bool {
    namespace.is_none_or(|namespace| within(name, namespace.as_bytes()))
}

fn within(name: &[u8], namespace: &[u8]) -> bool {
    name == namespace
        || name
            .strip_prefix(namespace)
            .is_some_and(|rest| rest.starts_with(b"/"))
}

fn private(name: &[u8]) -> bool {
    let namespaces = [
        b"refs/bisect".as_slice(),
        b"refs/rewritten",
        b"refs/worktree",
    ];
    namespaces.iter().any(|prefix| within(name, prefix))
}

#[derive(Clone, Copy)]
enum LooseScope {
    All,
    Shared,
    Private,
}

fn collect_loose(
    format: crate::ObjectFormat,
    root: &Path,
    namespace: Option<&RefName>,
    scope: LooseScope,
    entries: &mut BTreeMap<RefName, Target>,
    mut budget: Option<&mut ScanBudget<'_>>,
) -> Result<(), ReferenceError> {
    let mut pending = vec![(root.join("refs"), b"refs".to_vec())];
    while let Some((path, bytes)) = pending.pop() {
        if let Some(budget) = budget.as_deref_mut() {
            budget.check()?;
        }
        let metadata = match fs::symlink_metadata(&path) {
            Ok(metadata) => metadata,
            Err(error) if error.kind() == std::io::ErrorKind::NotFound => continue,
            Err(source) => return Err(io_error(&path, source)),
        };
        let is_private = if metadata.is_dir() || metadata.file_type().is_symlink() {
            private(&bytes)
        } else {
            RefName::new(&bytes).is_ok_and(|name| name.per_worktree())
        };
        let excluded = match scope {
            LooseScope::All => false,
            LooseScope::Shared => is_private,
            LooseScope::Private => !is_private,
        };
        if bytes != b"refs" && excluded {
            continue;
        }
        if metadata.file_type().is_symlink() {
            return Err(ReferenceError::Unsupported(
                "filesystem symlink in reference path",
            ));
        }
        if metadata.is_dir() {
            let children = match fs::read_dir(&path) {
                Ok(children) => children,
                Err(error) if error.kind() == std::io::ErrorKind::NotFound => continue,
                Err(source) => return Err(io_error(&path, source)),
            };
            for child in children {
                if let Some(budget) = budget.as_deref_mut() {
                    budget.check()?;
                    budget.charge(1)?;
                }
                let child = child.map_err(|source| io_error(&path, source))?;
                let component = child.file_name();
                // Preserve Unix filename bytes; other hosts require Unicode filesystem names.
                #[cfg(unix)]
                let component = {
                    use std::os::unix::ffi::OsStrExt;
                    component.as_bytes()
                };
                #[cfg(not(unix))]
                let component = component
                    .to_str()
                    .ok_or(ReferenceError::Unsupported("non-UTF-8 filesystem name"))?
                    .as_bytes();
                if component.starts_with(b".") || component.ends_with(b".lock") {
                    continue;
                }
                let mut name = bytes.clone();
                name.push(b'/');
                name.extend_from_slice(component);
                if namespace.is_some_and(|ns| {
                    !within(&name, ns.as_bytes()) && !within(ns.as_bytes(), &name)
                }) {
                    continue;
                }
                pending.push((child.path(), name));
            }
        } else if selected(&bytes, namespace) {
            let name = RefName::new(bytes)
                .map_err(|_| malformed(&path, "invalid loose reference name"))?;
            let value = if let Some(budget) = budget.as_deref_mut() {
                read_limited(&path, budget)?
            } else {
                read_optional(&path)?
            };
            if let Some(bytes) = value {
                entries.insert(name, parse_loose(format, &bytes, &path)?);
            }
        }
    }
    Ok(())
}

struct ScanBudget<'a> {
    entries: usize,
    bytes: usize,
    cancel: &'a AtomicBool,
}

impl ScanBudget<'_> {
    fn check(&self) -> Result<(), ReferenceError> {
        if self.cancel.load(Ordering::Relaxed) {
            Err(ReferenceError::Cancelled)
        } else {
            Ok(())
        }
    }

    fn charge(&mut self, entries: usize) -> Result<(), ReferenceError> {
        self.entries = self
            .entries
            .checked_sub(entries)
            .ok_or(ReferenceError::Limit("reference entries"))?;
        Ok(())
    }
}

fn read_limited(
    path: &Path,
    budget: &mut ScanBudget<'_>,
) -> Result<Option<Vec<u8>>, ReferenceError> {
    budget.check()?;
    check_path(path)?;
    let file = match fs::File::open(path) {
        Ok(file) => file,
        Err(error) if error.kind() == std::io::ErrorKind::NotFound => return Ok(None),
        Err(source) => return Err(io_error(path, source)),
    };
    let mut bytes = Vec::new();
    file.take(budget.bytes.saturating_add(1) as u64)
        .read_to_end(&mut bytes)
        .map_err(|source| io_error(path, source))?;
    if bytes.len() > budget.bytes {
        return Err(ReferenceError::Limit("reference bytes"));
    }
    budget.bytes -= bytes.len();
    budget.check()?;
    Ok(Some(bytes))
}

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

    use super::*;
    use crate::{InitKind, ObjectId, Repository};

    fn fixture() -> (tempfile::TempDir, Repository) {
        let root = tempfile::tempdir().unwrap();
        let repo = Repository::init(
            crate::ObjectFormat::Sha1,
            root.path().join("repo"),
            InitKind::Bare,
        )
        .unwrap();
        fs::create_dir_all(repo.git_dir().join("refs/heads")).unwrap();
        fs::write(
            repo.git_dir().join("refs/heads/a"),
            b"ref: refs/heads/missing\n",
        )
        .unwrap();
        fs::write(repo.git_dir().join("packed-refs"), b"1111111111111111111111111111111111111111 refs/heads/a\n2222222222222222222222222222222222222222 refs/tags/z\n").unwrap();
        (root, repo)
    }

    #[test]
    fn lists_shadowing_symbols_and_packed_tags_in_byte_order() {
        let (_root, repo) = fixture();
        let entries = repo.references().unwrap().list().unwrap();
        assert_eq!(
            entries,
            vec![
                Reference {
                    name: RefName::new(b"refs/heads/a").unwrap(),
                    target: Target::Symbolic(RefName::new(b"refs/heads/missing").unwrap())
                },
                Reference {
                    name: RefName::new(b"refs/tags/z").unwrap(),
                    target: Target::Direct(ObjectId::Sha1([0x22; 20]))
                },
            ]
        );
    }

    #[test]
    fn controlled_inventory_rejects_limits_and_cancellation() {
        let (_root, repo) = fixture();
        let refs = repo.references().unwrap();
        let active = AtomicBool::new(false);
        assert_eq!(
            refs.list_controlled(10, 1024, &active).unwrap(),
            refs.list().unwrap()
        );
        assert!(matches!(
            refs.list_controlled(0, 1024, &active),
            Err(ReferenceError::Limit("reference entries"))
        ));
        assert!(matches!(
            refs.list_controlled(10, 0, &active),
            Err(ReferenceError::Limit("reference bytes"))
        ));
        let cancelled = AtomicBool::new(true);
        assert!(matches!(
            refs.list_controlled(10, 1024, &cancelled),
            Err(ReferenceError::Cancelled)
        ));
    }

    #[rstest]
    #[case::branch_namespace(b"refs/heads", 1)]
    #[case::exact(b"refs/heads/a", 1)]
    #[case::not_a_string_prefix(b"refs/head", 0)]
    #[case::missing(b"refs/other", 0)]
    fn filters_at_namespace_boundaries(#[case] namespace: &[u8], #[case] count: usize) {
        let (_root, repo) = fixture();
        assert_eq!(
            repo.references()
                .unwrap()
                .list_namespace(&RefName::new(namespace).unwrap())
                .unwrap()
                .len(),
            count
        );
    }

    #[test]
    fn skips_locks_dot_entries_and_empty_directories() {
        let (_root, repo) = fixture();
        fs::write(repo.git_dir().join("refs/heads/a.lock"), b"writer").unwrap();
        fs::write(repo.git_dir().join("refs/heads/.hidden"), b"unrelated").unwrap();
        fs::create_dir(repo.git_dir().join("refs/heads/empty")).unwrap();
        assert_eq!(repo.references().unwrap().list().unwrap().len(), 2);
    }

    #[test]
    fn broken_loose_does_not_fall_back_but_unselected_loose_is_not_read() {
        let (_root, repo) = fixture();
        fs::write(repo.git_dir().join("refs/heads/a"), b"broken").unwrap();
        assert!(matches!(
            repo.references().unwrap().list(),
            Err(ReferenceError::Malformed { .. })
        ));
        assert_eq!(
            repo.references()
                .unwrap()
                .list_namespace(&RefName::new(b"refs/tags").unwrap())
                .unwrap()
                .len(),
            1
        );
        assert_eq!(
            fs::read(repo.git_dir().join("refs/heads/a")).unwrap(),
            b"broken"
        );
    }

    #[test]
    fn filtered_list_still_validates_all_packed_data() {
        let (_root, repo) = fixture();
        fs::write(repo.git_dir().join("packed-refs"), b"broken").unwrap();
        assert!(matches!(
            repo.references()
                .unwrap()
                .list_namespace(&RefName::new(b"refs/heads").unwrap()),
            Err(ReferenceError::Malformed { .. })
        ));
    }

    #[cfg(unix)]
    #[test]
    fn rejects_symlink_directory_without_traversing_it() {
        let (_root, repo) = fixture();
        let outside = tempfile::tempdir().unwrap();
        std::os::unix::fs::symlink(outside.path(), repo.git_dir().join("refs/link")).unwrap();
        assert!(matches!(
            repo.references().unwrap().list(),
            Err(ReferenceError::Unsupported(_))
        ));
    }

    #[cfg(unix)]
    #[test]
    fn private_namespace_symlink_is_rejected_in_its_own_worktree() {
        let (_root, repo) = fixture();
        let outside = tempfile::tempdir().unwrap();
        std::os::unix::fs::symlink(outside.path(), repo.git_dir().join("refs/worktree")).unwrap();
        let mut entries = BTreeMap::new();
        assert!(matches!(
            collect_loose(
                repo.object_format(),
                repo.git_dir(),
                None,
                LooseScope::Private,
                &mut entries,
                None,
            ),
            Err(ReferenceError::Unsupported(_))
        ));
    }

    #[test]
    fn rejects_invalid_loose_name() {
        let (_root, repo) = fixture();
        fs::write(
            repo.git_dir().join("refs/heads/bad name"),
            b"1111111111111111111111111111111111111111\n",
        )
        .unwrap();
        assert!(matches!(
            repo.references().unwrap().list(),
            Err(ReferenceError::Malformed { .. })
        ));
    }

    #[test]
    fn rejects_nonadjacent_namespace_conflicts() {
        let (_root, repo) = fixture();
        fs::write(repo.git_dir().join("packed-refs"), b"1111111111111111111111111111111111111111 refs/a\n1111111111111111111111111111111111111111 refs/a.b\n1111111111111111111111111111111111111111 refs/a/c\n").unwrap();
        assert!(matches!(
            repo.references().unwrap().list(),
            Err(ReferenceError::Conflict(_))
        ));
    }

    #[test]
    fn preserves_packed_non_utf8_names() {
        let (_root, repo) = fixture();
        fs::write(
            repo.git_dir().join("packed-refs"),
            b"1111111111111111111111111111111111111111 refs/tags/\xff\n",
        )
        .unwrap();
        let tags = repo
            .references()
            .unwrap()
            .list_namespace(&RefName::new(b"refs/tags").unwrap())
            .unwrap();
        assert_eq!(tags[0].name.as_bytes(), b"refs/tags/\xff");
    }

    #[test]
    fn head_requires_single_name_read() {
        let (_root, repo) = fixture();
        assert!(matches!(
            repo.references()
                .unwrap()
                .list_namespace(&RefName::new(b"HEAD").unwrap()),
            Err(ReferenceError::Unsupported(_))
        ));
    }
}