grit-lib 0.5.18

//! Parsed-tree cache and per-side directory metadata for three-way tree merges.

use std::collections::{HashMap, HashSet};
use std::rc::Rc;

use super::merge_trees_walk::PathPrefixIndex;
use crate::objects::{parse_tree, ObjectId, ObjectKind, TreeEntry};
use crate::odb::Odb;

const MODE_DIR: u32 = 0o040000;

/// Which root tree a side-specific helper refers to.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) enum MergeTreeSide {
    Base,
    Ours,
    Theirs,
}

/// Per-merge cache: parsed tree bodies and directory paths known to contain files.
#[derive(Default)]
pub(crate) struct MergeTreeCache {
    parsed: HashMap<ObjectId, Rc<[TreeEntry]>>,
    dir_with_descendant: [HashSet<Vec<u8>>; 3],
}

impl MergeTreeCache {
    /// Drop parsed trees and path hints so long replay sequences do not retain every step's trees.
    pub(crate) fn clear_retained(&mut self) {
        self.parsed.clear();
        self.dir_with_descendant = [HashSet::new(), HashSet::new(), HashSet::new()];
    }

    pub(crate) fn tree_entries(
        &mut self,
        odb: &Odb,
        oid: &ObjectId,
    ) -> crate::error::Result<Rc<[TreeEntry]>> {
        if let Some(entries) = self.parsed.get(oid) {
            return Ok(Rc::clone(entries));
        }
        let obj = odb.read(oid)?;
        let entries: Rc<[TreeEntry]> = if obj.kind == ObjectKind::Tree {
            parse_tree(&obj.data)?.into()
        } else {
            Rc::from(Vec::new())
        };
        self.parsed.insert(*oid, Rc::clone(&entries));
        Ok(entries)
    }

    pub(crate) fn note_file_path(&mut self, side: MergeTreeSide, path: &[u8]) {
        let idx = side as usize;
        for (i, &b) in path.iter().enumerate() {
            if b == b'/' {
                self.dir_with_descendant[idx].insert(path[..i].to_vec());
            }
        }
    }

    /// True when a noted file lies under `prefix/`. [`Self::note_file_path`] records every
    /// ancestor directory, so any deeper recorded directory implies `prefix` itself is recorded.
    pub(crate) fn dir_has_descendant(&self, side: MergeTreeSide, prefix: &[u8]) -> bool {
        self.dir_with_descendant[side as usize].contains(prefix)
    }
}

pub(crate) fn find_tree_entry<'a>(entries: &'a [TreeEntry], name: &[u8]) -> Option<&'a TreeEntry> {
    entries.iter().find(|e| e.name.as_slice() == name)
}

fn tree_entry_to_index(path: &[u8], te: &TreeEntry) -> crate::index::IndexEntry {
    crate::index::IndexEntry {
        ctime_sec: 0,
        ctime_nsec: 0,
        mtime_sec: 0,
        mtime_nsec: 0,
        dev: 0,
        ino: 0,
        mode: te.mode,
        uid: 0,
        gid: 0,
        size: 0,
        oid: te.oid,
        flags: path.len().min(0xFFF) as u16,
        flags_extended: None,
        path: path.to_vec(),
        base_index_pos: 0,
    }
}

pub(crate) fn lookup_index_entry_at_path_cached(
    cache: &mut MergeTreeCache,
    odb: &Odb,
    tree_oid: &ObjectId,
    path: &[u8],
) -> crate::error::Result<Option<crate::index::IndexEntry>> {
    if path.is_empty() {
        return Ok(None);
    }
    let parts: Vec<&[u8]> = path
        .split(|&b| b == b'/')
        .filter(|s| !s.is_empty())
        .collect();
    let mut current = *tree_oid;
    for (i, comp) in parts.iter().enumerate() {
        let entries = cache.tree_entries(odb, &current)?;
        let Some(te) = find_tree_entry(&entries, comp) else {
            return Ok(None);
        };
        let is_last = i + 1 == parts.len();
        if is_last {
            return Ok(Some(tree_entry_to_index(path, te)));
        }
        if te.mode != MODE_DIR {
            return Ok(None);
        }
        current = te.oid;
    }
    Ok(None)
}

pub(crate) fn tree_has_entries_with_path_prefix_cached(
    cache: &mut MergeTreeCache,
    odb: &Odb,
    tree_oid: &ObjectId,
    side: MergeTreeSide,
    prefix: &[u8],
) -> crate::error::Result<bool> {
    if cache.dir_has_descendant(side, prefix) {
        return Ok(true);
    }
    // Descend only along `prefix`'s components; `rest` is the part of `prefix` not yet
    // matched. Every tree entry name is compared against `rest` the same way a full-path
    // comparison would, so names that themselves contain `/` are still honoured.
    fn walk(
        cache: &mut MergeTreeCache,
        odb: &Odb,
        tree_oid: &ObjectId,
        rest: &[u8],
    ) -> crate::error::Result<bool> {
        let entries = cache.tree_entries(odb, tree_oid)?;
        let mut descend: Vec<(ObjectId, usize)> = Vec::new();
        for te in entries.iter() {
            let name = te.name.as_slice();
            if name.len() > rest.len() && name.starts_with(rest) && name[rest.len()] == b'/' {
                return Ok(true);
            }
            if te.mode != MODE_DIR {
                continue;
            }
            if name == rest {
                descend.push((te.oid, rest.len()));
            } else if rest.len() > name.len() && rest.starts_with(name) && rest[name.len()] == b'/'
            {
                descend.push((te.oid, name.len() + 1));
            }
        }
        drop(entries);
        for (oid, consumed) in descend {
            if consumed == rest.len() {
                if !cache.tree_entries(odb, &oid)?.is_empty() {
                    return Ok(true);
                }
            } else if walk(cache, odb, &oid, &rest[consumed..])? {
                return Ok(true);
            }
        }
        Ok(false)
    }
    if prefix.is_empty() {
        return Ok(false);
    }
    walk(cache, odb, tree_oid, prefix)
}

pub(crate) fn side_tree_has_descendant_at_cached(
    cache: &mut MergeTreeCache,
    odb: &Odb,
    tree_oid: &ObjectId,
    side: MergeTreeSide,
    prefix: &[u8],
    sparse_paths: &PathPrefixIndex,
) -> crate::error::Result<bool> {
    if sparse_paths.has_descendant(prefix) {
        return Ok(true);
    }
    if cache.dir_has_descendant(side, prefix) {
        return Ok(true);
    }
    if let Some(entry) = lookup_index_entry_at_path_cached(cache, odb, tree_oid, prefix)? {
        if entry.mode == MODE_DIR {
            let children = cache.tree_entries(odb, &entry.oid)?;
            if !children.is_empty() {
                return Ok(true);
            }
        }
    }
    tree_has_entries_with_path_prefix_cached(cache, odb, tree_oid, side, prefix)
}