monochromatic-git-policy-cli 0.6.0

//! What:
//!  The part of a tree that differs from an index, found by walking the tree beside the index's cache-tree: a directory that
//!  the cache-tree marks valid, with the tree name the tree has there, is equal by construction and is not read.
//! Why:
//!  A commit compares its index with the tree of `HEAD` several times, and the comparison read every directory of the tree
//!  (about 1,400 tree objects, tens of thousands of reads and file probes on the checkout of this repository) to find one
//!  changed file. The index already says which directories changed: Git invalidates the cache-tree along every changed path.
//!
//! In TS you'd write (pseudocode):
//! ```ts
//! const { old, skipped } = unequalParts(odb, treeName, cacheTree, index); // undefined: read the whole tree instead
//! ```

#![cfg(unix)]

use crate::index_cache_tree::CacheTree;
use crate::repo_read_diff::{Change, diff_sorted};
use crate::repo_read_layout::ObjectFormat;
use crate::repo_read_object::{ObjectKind, name_length};
use crate::repo_read_odb::ObjectDatabase;
use crate::repo_read_tree::{FlatEntry, is_tree_mode, parse_tree};

/// The deepest tree nesting the walk follows, as `repo_read_tree.rs` follows it.
const TREE_DEPTH_LIMIT: usize = 256;

/// The most entries the tree side may hold before the reader declines, as `repo_read_tree.rs` holds them.
const FLAT_ENTRY_LIMIT: usize = 4_000_000;

/// What the walk found.
#[derive(Debug)]
pub struct UnequalParts {
    /// The entries of the tree outside the directories that were left unread, in path order.
    pub tree: Vec<FlatEntry>,
    /// The ranges of the index (start, end) that belong to the directories left unread, in index order.
    pub skipped: Vec<(usize, usize)>,
}

/// The state of one walk.
struct Walk<'a> {
    /// Where the tree objects are read from.
    database: &'a ObjectDatabase,
    /// The object format, which fixes the name length.
    format: ObjectFormat,
    /// The index paths, sorted.
    paths: &'a [&'a [u8]],
    /// The entries of the tree seen so far.
    tree: Vec<FlatEntry>,
    /// The index ranges left unread so far.
    skipped: Vec<(usize, usize)>,
}

/// The subdirectory `name` of a cache-tree node; the file keeps its subdirectories sorted by length and then bytes.
fn subtree_of<'a>(node: &'a CacheTree, name: &[u8]) -> Option<&'a CacheTree> {
    // A binary search over the sorted subdirectories by (length, bytes).
    let (mut low, mut high): (usize, usize) = (0, node.subtrees.len());
    while low < high {
        let middle: usize = low + (high - low) / 2;
        let (candidate, subtree) = &node.subtrees[middle];
        match (candidate.len(), candidate.as_slice()).cmp(&(name.len(), name)) {
            std::cmp::Ordering::Less => low = middle + 1,
            std::cmp::Ordering::Greater => high = middle,
            std::cmp::Ordering::Equal => return Some(subtree),
        }
    }
    return None;
}

/// The range of `range` whose paths start with `prefix`, which is one stretch because the paths are sorted.
fn below(paths: &[&[u8]], range: (usize, usize), prefix: &[u8]) -> (usize, usize) {
    let window: &[&[u8]] = &paths[range.0..range.1];
    // Two binary searches over the sorted paths: the first path not before the prefix, then the end of the paths that start with it.
    let (mut low, mut high): (usize, usize) = (0, window.len());
    while low < high {
        let middle: usize = low + (high - low) / 2;
        if window[middle] < prefix {
            low = middle + 1;
        } else {
            high = middle;
        }
    }
    let start: usize = low;
    let rest: &[&[u8]] = &window[start..];
    let (mut inside, mut past): (usize, usize) = (0, rest.len());
    while inside < past {
        let middle: usize = inside + (past - inside) / 2;
        if rest[middle].starts_with(prefix) {
            inside = middle + 1;
        } else {
            past = middle;
        }
    }
    let length: usize = inside;
    return (range.0 + start, range.0 + start + length);
}

impl Walk<'_> {
    /// Walk the directory `tree` (below `prefix`), whose index paths are `range`, and `node` (its cache-tree node when there is one).
    fn directory(&mut self, tree: &[u8], node: Option<&CacheTree>, prefix: &mut Vec<u8>, range: (usize, usize), depth: usize) -> Option<()> {
        if depth > TREE_DEPTH_LIMIT {
            return None;
        }
        let valid_node: Option<&CacheTree> = match node {
            Some(candidate) if candidate.entry_count >= 0 && candidate.id.as_slice() == tree => Some(candidate),
            _ => None,
        };
        if let Some(valid) = valid_node {
            // A node whose count is not the number of index entries below the directory is not trusted; the whole tree is read.
            if usize::try_from(valid.entry_count).ok()? != range.1 - range.0 {
                return None;
            }
            self.skipped.push(range);
            return Some(());
        }
        let object = self.database.read(tree)?;
        if object.kind != ObjectKind::Tree {
            return None;
        }
        for entry in parse_tree(object.bytes.as_slice(), name_length(self.format))? {
            let length: usize = prefix.len();
            prefix.extend_from_slice(entry.name.as_slice());
            if is_tree_mode(entry.mode) {
                prefix.push(b'/');
                let inner: (usize, usize) = below(self.paths, range, prefix.as_slice());
                let child: Option<&CacheTree> = match node {
                    Some(parent) => subtree_of(parent, entry.name.as_slice()),
                    None => None,
                };
                self.directory(entry.id.as_slice(), child, prefix, inner, depth + 1)?;
            } else {
                self.tree.push(FlatEntry { path: prefix.clone(), mode: entry.mode, id: entry.id });
                if self.tree.len() > FLAT_ENTRY_LIMIT {
                    return None;
                }
            }
            prefix.truncate(length);
        }
        return Some(());
    }
}

/// What:
///  The entries of the tree `tree` that lie outside the directories the cache-tree proves equal, and the index ranges of those
///  directories; `None` when the walk cannot be trusted (an unreadable tree, a count that does not match the index).
/// Why:
///   Leaving an equal directory out of both sides leaves their difference as it was, so the caller compares what remains the way
///  it compared the whole lists. The index paths must be sorted and free of unmerged and intent-to-add entries, which the caller
///  checks, because a cache-tree says nothing of an entry it left out of the tree it hashed.
///
/// In TS you'd write (pseudocode):
/// ```ts
/// function unequalParts(odb, tree, format, cache, paths): { tree: FlatEntry[]; skipped: [number, number][] } | undefined;
/// ```
pub fn unequal_parts(database: &ObjectDatabase, tree: &[u8], format: ObjectFormat, cache: &CacheTree, paths: &[&[u8]]) -> Option<UnequalParts> {
    // Git reads the tree it compares with and fails when it is gone, so the root is read before any shortcut: a cache-tree that
    //  names it proves the directories below equal, not that the object is there.
    let root = database.read(tree)?;
    if root.kind != ObjectKind::Tree {
        return None;
    }
    let mut walk: Walk<'_> = Walk { database, format, paths, tree: Vec::new(), skipped: Vec::new() };
    walk.directory(tree, Some(cache), &mut Vec::new(), (0, paths.len()), 0)?;
    walk.skipped.sort_unstable();
    return Some(UnequalParts { tree: walk.tree, skipped: walk.skipped });
}

/// What:
///  The items of `all` outside the `skipped` ranges, in order.
/// Why:
///   The index side of the comparison drops the same directories the tree side left unread.
///
/// In TS you'd write (pseudocode):
/// ```ts
/// function outside<T>(all: T[], skipped: [number, number][]): T[];
/// ```
pub fn outside<'a, Item>(all: &'a [Item], skipped: &[(usize, usize)]) -> Vec<&'a Item> {
    let mut kept: Vec<&Item> = Vec::new();
    let mut at: usize = 0;
    for (start, end) in skipped {
        kept.extend(all[at..*start].iter());
        at = *end;
    }
    kept.extend(all[at..].iter());
    return kept;
}

/// What:
///  The changes from `tree` to `index` found without reading the directories the cache-tree proves equal.
/// Why:
///   The index side drops the same directories the tree side left unread, so `diff_sorted` compares only what can differ and
///  gives the changes the full lists give; `None` when the walk or the comparison declines, and the caller then reads the whole tree.
///
/// In TS you'd write (pseudocode):
/// ```ts
/// function changesWithCache(odb, tree, format, cache, index: FlatEntry[]): Change[] | undefined;
/// ```
pub fn changes_with_cache(database: &ObjectDatabase, tree: &[u8], format: ObjectFormat, cache: &CacheTree, index: &[FlatEntry]) -> Option<Vec<Change>> {
    let mut paths: Vec<&[u8]> = Vec::new();
    for entry in index {
        paths.push(entry.path.as_slice());
    }
    let parts: UnequalParts = unequal_parts(database, tree, format, cache, paths.as_slice())?;
    let mut kept: Vec<FlatEntry> = Vec::new();
    for entry in outside(index, parts.skipped.as_slice()) {
        kept.push(entry.clone());
    }
    return diff_sorted(parts.tree.as_slice(), kept.as_slice());
}

/// Controls for the walk against real Git's trees and indexes stay out of the release executable.
#[cfg(test)]
#[path = "repo_read_tree_cached_tests.rs"]
mod tests;