girt 0.3.3

use std::collections::{HashMap, HashSet, VecDeque};
use std::sync::atomic::{AtomicBool, Ordering};
use std::sync::{Arc, Mutex};

#[cfg(test)]
use flate2::{Decompress, FlushDecompress, Status};

use super::delta::{apply, byte, charge, size};
#[cfg(test)]
use super::index::{Index, verify_hash, word};
use crate::{Object, ObjectId, ObjectKind, ObjectReadError as Error, ReadLimits};

#[cfg(test)]
#[derive(Debug)]
pub(crate) struct Pack {
    index: Index,
    data: Vec<u8>,
}

#[cfg(test)]
impl Pack {
    pub fn open(
        format: crate::ObjectFormat,
        index_bytes: &[u8],
        data: Vec<u8>,
    ) -> Result<Self, Error> {
        if data.len() < 12 + format.digest_len() || &data[..4] != b"PACK" {
            return Err(Error::Corrupt("pack header"));
        }
        let version = word(&data, 4)?;
        if !matches!(version, 2 | 3) {
            return Err(Error::PackVersion(version));
        }
        let end = data.len() - format.digest_len();
        let index = Index::parse(format, index_bytes, end)?;
        if word(&data, 8)? as usize != index.entries.len() {
            return Err(Error::Corrupt("pack object count"));
        }
        verify_hash(format, &data, "pack checksum")?;
        if *index.pack_hash.as_bytes() != data[end..] {
            return Err(Error::Corrupt("index/pack checksum disagreement"));
        }
        for entry in &index.entries {
            if entry
                .crc
                .is_some_and(|crc| crc32fast::hash(&data[entry.offset..entry.end]) != crc)
            {
                return Err(Error::Corrupt("entry CRC"));
            }
        }
        Ok(Self { index, data })
    }

    pub fn find(&self, id: ObjectId) -> Option<usize> {
        self.index.find(id)
    }

    pub fn read(&self, position: usize, limits: ReadLimits) -> Result<Object, Error> {
        decode(self, position, limits, &AtomicBool::new(false))
    }
}

pub(crate) trait Source {
    fn format(&self) -> crate::ObjectFormat;
    fn entry(&self, position: usize) -> Result<super::index::Entry, Error>;
    fn find(&self, id: ObjectId) -> Result<Option<usize>, Error>;
    fn at_offset(&self, offset: usize) -> Result<usize, Error>;
    fn prefix(&self, entry: &super::index::Entry) -> Result<Vec<u8>, Error>;
    fn inflate(
        &self,
        start: usize,
        end: usize,
        expected: usize,
        cancelled: &AtomicBool,
    ) -> Result<Vec<u8>, Error>;
    /// Decoded objects kept to avoid re-inflating shared delta bases, if this source has one.
    fn base_cache(&self) -> Option<&BaseCache> {
        None
    }
}

/// Recently decoded pack entries, keyed by entry position, like Git's delta base cache.
///
/// Reading a deltified object reconstructs its whole chain, and neighbouring objects usually
/// share bases, so caching them avoids inflating the same bases repeatedly. Entries record
/// whether their identity was checked; an unchecked entry is checked before being returned as
/// the requested object.
pub(crate) struct BaseCache {
    inner: Mutex<CacheInner>,
}

impl std::fmt::Debug for BaseCache {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("BaseCache").finish_non_exhaustive()
    }
}

#[derive(Default)]
struct CacheInner {
    entries: HashMap<usize, Cached>,
    order: VecDeque<usize>,
    bytes: usize,
}

#[derive(Clone)]
struct Cached {
    kind: ObjectKind,
    data: Arc<Vec<u8>>,
    verified: bool,
}

impl BaseCache {
    /// Total decoded bytes retained, matching Git's default `core.deltaBaseCacheLimit`.
    const LIMIT: usize = 96 * 1024 * 1024;

    pub(crate) fn new() -> Self {
        Self {
            inner: Mutex::new(CacheInner::default()),
        }
    }

    fn get(&self, position: usize) -> Option<Cached> {
        let inner = self.inner.lock().unwrap_or_else(|error| error.into_inner());
        inner.entries.get(&position).cloned()
    }

    pub(crate) fn insert(&self, position: usize, object: &Object, verified: bool) {
        if object.data.len() <= Self::LIMIT / 8 {
            self.insert_owned(position, object.clone(), verified);
        }
    }

    /// Indexing can transfer a decoded payload into the cache instead of copying it.
    pub(crate) fn insert_owned(&self, position: usize, object: Object, verified: bool) {
        let size = object.data.len();
        // One large object shouldn't evict every shared base.
        if size > Self::LIMIT / 8 {
            return;
        }
        let mut inner = self.inner.lock().unwrap_or_else(|error| error.into_inner());
        if let Some(existing) = inner.entries.get_mut(&position) {
            existing.verified |= verified;
            return;
        }
        while inner.bytes + size > Self::LIMIT {
            let Some(oldest) = inner.order.pop_front() else {
                break;
            };
            if let Some(evicted) = inner.entries.remove(&oldest) {
                inner.bytes -= evicted.data.len();
            }
        }
        inner.bytes += size;
        inner.order.push_back(position);
        inner.entries.insert(
            position,
            Cached {
                kind: object.kind,
                data: Arc::new(object.data),
                verified,
            },
        );
    }

    fn mark_verified(&self, position: usize) {
        let mut inner = self.inner.lock().unwrap_or_else(|error| error.into_inner());
        if let Some(entry) = inner.entries.get_mut(&position) {
            entry.verified = true;
        }
    }
}

#[cfg(test)]
impl Source for Pack {
    fn format(&self) -> crate::ObjectFormat {
        self.index.pack_hash.format()
    }
    fn entry(&self, position: usize) -> Result<super::index::Entry, Error> {
        Ok(self.index.entries[position].clone())
    }
    fn find(&self, id: ObjectId) -> Result<Option<usize>, Error> {
        Ok(self.find(id))
    }
    fn at_offset(&self, offset: usize) -> Result<usize, Error> {
        self.index.at_offset(offset)
    }
    fn prefix(&self, entry: &super::index::Entry) -> Result<Vec<u8>, Error> {
        Ok(self.data[entry.offset..entry.end.min(entry.offset.saturating_add(64))].to_vec())
    }
    fn inflate(
        &self,
        start: usize,
        end: usize,
        expected: usize,
        _: &AtomicBool,
    ) -> Result<Vec<u8>, Error> {
        inflate(&self.data[start..end], expected)
    }
}

pub(crate) fn check_cancelled(cancelled: &AtomicBool) -> Result<(), Error> {
    if cancelled.load(Ordering::Relaxed) {
        Err(Error::Cancelled)
    } else {
        Ok(())
    }
}

pub(crate) fn decode(
    source: &impl Source,
    position: usize,
    limits: ReadLimits,
    cancelled: &AtomicBool,
) -> Result<Object, Error> {
    let mut remaining = limits.max_decode_bytes;
    decode_budgeted(source, position, limits, cancelled, &mut remaining)
}

pub(crate) fn decode_budgeted(
    source: &impl Source,
    mut position: usize,
    limits: ReadLimits,
    cancelled: &AtomicBool,
    remaining: &mut usize,
) -> Result<Object, Error> {
    let format = source.format();
    let mut input_remaining = limits.max_input_bytes;
    let mut pending = Vec::new();
    let mut seen = HashSet::new();
    let cache = source.base_cache();
    let requested = position;
    let mut object = loop {
        if !seen.insert(position) {
            return Err(Error::DeltaCycle);
        }
        check_cancelled(cancelled)?;
        if let Some(hit) = cache.and_then(|cache| cache.get(position)) {
            let object = Object {
                kind: hit.kind,
                data: hit.data.as_ref().clone(),
                format,
            };
            if position == requested && !hit.verified {
                verify_identity(&object, source.entry(position)?.id)?;
                cache
                    .expect("hit came from the cache")
                    .mark_verified(position);
            }
            break object;
        }
        let entry = source.entry(position)?;
        input_remaining = input_remaining
            .checked_sub(entry.end - entry.offset)
            .ok_or(Error::Limit("compressed entry bytes"))?;
        let EntryHeader {
            kind,
            length,
            base,
            data_start: start,
        } = entry_header(source, &entry)?;
        let limit = if base.is_some() {
            limits.max_delta_bytes
        } else {
            limits.max_object_bytes
        };
        if length > limit {
            return Err(Error::Limit(if base.is_some() {
                "delta program bytes"
            } else {
                "object bytes"
            }));
        }
        if base.is_some() && pending.len() >= limits.max_delta_depth {
            return Err(Error::Limit("delta depth"));
        }
        charge(remaining, length)?;
        let data = source.inflate(start, entry.end, length, cancelled)?;
        if let Some(base) = base {
            pending.push((position, data));
            position = base;
        } else {
            let kind = match kind {
                1 => ObjectKind::Commit,
                2 => ObjectKind::Tree,
                3 => ObjectKind::Blob,
                4 => ObjectKind::Tag,
                _ => unreachable!("non-delta kinds validated above"),
            };
            let object = Object { kind, data, format };
            // Only the requested object's identity is checked: a corrupt base changes every
            // object reconstructed from it, so the final check still catches it.
            let verified = position == requested;
            if verified {
                verify_identity(&object, entry.id)?;
            }
            if let Some(cache) = cache {
                cache.insert(position, &object, verified);
            }
            break object;
        }
    };
    while let Some((position, program)) = pending.pop() {
        check_cancelled(cancelled)?;
        object.data = apply(&object.data, &program, limits.max_object_bytes, remaining)?;
        let verified = position == requested;
        if verified {
            verify_identity(&object, source.entry(position)?.id)?;
        }
        if let Some(cache) = cache {
            cache.insert(position, &object, verified);
        }
    }
    Ok(object)
}

/// A pack entry's parsed header: type code, declared size, resolved base and payload offset.
pub(crate) struct EntryHeader {
    /// Pack type code: 1-4 for whole objects, 6 or 7 for deltas.
    pub kind: u8,
    /// Declared inflated size of the object or delta program.
    pub length: usize,
    /// Position of the delta base within the same pack, for delta entries.
    pub base: Option<usize>,
    /// Offset of the first zlib byte.
    pub data_start: usize,
}

/// Parses an entry header and resolves a delta base to a position in the same pack.
pub(crate) fn entry_header(
    source: &impl Source,
    entry: &super::index::Entry,
) -> Result<EntryHeader, Error> {
    let width = source.format().digest_len();
    let prefix = source.prefix(entry)?;
    let mut input = prefix.as_slice();
    let header = byte(&mut input)?;
    let kind = (header >> 4) & 7;
    let length = size(&mut input, (header & 15) as usize, 4, header & 128 != 0)?;
    let base = match kind {
        1..=4 => None,
        6 => {
            let mut next = byte(&mut input)?;
            let mut distance = (next & 127) as usize;
            while next & 128 != 0 {
                next = byte(&mut input)?;
                distance = distance
                    .checked_add(1)
                    .and_then(|n| n.checked_mul(128))
                    .and_then(|n| n.checked_add((next & 127) as usize))
                    .ok_or(Error::Corrupt("delta offset overflow"))?;
            }
            if distance == 0 {
                return Err(Error::Corrupt("zero delta distance"));
            }
            let offset = entry
                .offset
                .checked_sub(distance)
                .ok_or(Error::Corrupt("delta offset before pack"))?;
            Some(source.at_offset(offset)?)
        }
        7 => {
            let raw = input
                .get(..width)
                .ok_or(Error::Corrupt("truncated base identity"))?;
            let id = ObjectId::from_bytes(source.format(), raw).unwrap();
            input = &input[width..];
            Some(source.find(id)?.ok_or(Error::MissingBase(id))?)
        }
        other => return Err(Error::ObjectType(other)),
    };
    Ok(EntryHeader {
        kind,
        length,
        base,
        data_start: entry.offset + prefix.len() - input.len(),
    })
}

fn verify_identity(object: &Object, expected: ObjectId) -> Result<(), Error> {
    if object.id() != expected {
        return Err(Error::Corrupt("object identity"));
    }
    Ok(())
}

#[cfg(test)]
fn inflate(input: &[u8], expected: usize) -> Result<Vec<u8>, Error> {
    let (data, consumed) = inflate_prefix(input, expected)?;
    if consumed != input.len() {
        return Err(Error::Corrupt("packed entry length or trailing data"));
    }
    Ok(data)
}

#[cfg(test)]
pub(crate) fn inflate_prefix(mut input: &[u8], expected: usize) -> Result<(Vec<u8>, usize), Error> {
    let mut inflater = Decompress::new(true);
    let mut output = [0; 8192];
    let mut data = Vec::new();
    loop {
        let before_in = inflater.total_in();
        let before_out = inflater.total_out();
        let status = inflater
            .decompress(input, &mut output, FlushDecompress::None)
            .map_err(|_| Error::Corrupt("invalid packed zlib stream"))?;
        let consumed = (inflater.total_in() - before_in) as usize;
        let produced = (inflater.total_out() - before_out) as usize;
        input = &input[consumed..];
        if produced > expected.saturating_sub(data.len()) {
            return Err(Error::Corrupt("inflated entry exceeds declared size"));
        }
        data.extend_from_slice(&output[..produced]);
        if status == Status::StreamEnd {
            if data.len() != expected {
                return Err(Error::Corrupt("packed entry length or trailing data"));
            }
            return Ok((data, inflater.total_in() as usize));
        }
        if produced == 0 && consumed == 0 {
            return Err(Error::Corrupt("truncated packed zlib stream"));
        }
    }
}