gix-commitgraph 0.42.0

use crate::{File, Graph, MAX_COMMITS, Parent};
use gix_error::Result;
use gix_error::{
    OptionExt, ResourceExhaustionKind, ResultExt, bail, corruption, message, resource_exhaustion, validation,
};
use std::{
    io::{BufRead, BufReader, Read},
    path::Path,
};

/// Instantiate a `Graph` from various sources.
impl Graph {
    /// Instantiate a commit graph from `path` which may be a directory containing graph files or the graph file itself.
    ///
    /// Chain entries and graph files must use `object_hash`, typically the repository's hash kind.
    /// Mismatches are reported as corruption.
    ///
    /// `alloc_limit_bytes` bounds a conservative capacity estimate for parent buffers derived from
    /// each file's EDGE chunk, including geometric buffer growth. `None` disables the limit.
    /// The mapped graph data itself is not allocated on the heap.
    ///
    /// Filesystem errors retain their [`std::io::Error`] source, including when `path` does not exist.
    pub fn at(path: &Path, object_hash: gix_hash::Kind, alloc_limit_bytes: Option<usize>) -> Result<Self> {
        let metadata = path
            .metadata()
            .or_raise(|| message!("Could not access commit-graph path at \"{}\"", path.display()))?;
        let graph = if metadata.is_file() {
            Self::from_file(path, object_hash)
        } else if metadata.is_dir() {
            if path.join("commit-graph-chain").is_file() {
                Self::from_commit_graphs_dir(path, object_hash)
            } else {
                Self::from_info_dir(path, object_hash)
            }
        } else {
            Err(message!(
                "Did not find any files that look like commit graphs at \"{}\"",
                path.display()
            )
            .validation_error())
        }?;
        if let Some(limit) = alloc_limit_bytes {
            for file in &graph.files {
                if let Some(edges) = file.extra_edges_data() {
                    // shortcut: estimate from the whole EDGE chunk, scan individual lists if valid graphs hit the limit.
                    // Include the inline parent and spare capacity for traversal buffers that double when growing.
                    let parent_bytes = (edges.len() / 4 + 1).checked_mul(2 * std::mem::size_of::<Result<Parent>>());
                    if parent_bytes.is_none_or(|bytes| bytes > limit) {
                        bail!(resource_exhaustion(
                            ResourceExhaustionKind::AllocationLimit,
                            "Commit-graph parents require more memory than allowed",
                        ));
                    }
                }
            }
        }
        Ok(graph)
    }

    /// Instantiate a commit graph from the directory containing all of its files.
    ///
    /// Chain entries and graph files must use `object_hash`.
    pub fn from_commit_graphs_dir(path: &Path, object_hash: gix_hash::Kind) -> Result<Self> {
        let commit_graphs_dir = path;
        let chain_file_path = commit_graphs_dir.join("commit-graph-chain");
        let chain_file = std::fs::File::open(&chain_file_path).or_raise(|| {
            message!(
                "Could not open commit-graph chain file at \"{}\"",
                chain_file_path.display()
            )
        })?;

        let files = read_chain_files(chain_file, &chain_file_path, commit_graphs_dir, object_hash)?;
        Self::new(files).or_raise(|| {
            message!(
                "Could not assemble commit-graph from chain file at \"{}\"",
                chain_file_path.display()
            )
            .corrupted()
        })
    }

    /// Instantiate a commit graph from a `.git/objects/info/commit-graph` or
    /// `.git/objects/info/commit-graphs/graph-*.graph` file.
    ///
    /// The graph file must use `object_hash`.
    pub fn from_file(path: &Path, object_hash: gix_hash::Kind) -> Result<Self> {
        let file = read_graph_file(path, object_hash)?;
        Self::new(vec![file])
            .or_raise(|| message!("Could not assemble commit-graph from file at \"{}\"", path.display()).corrupted())
    }

    /// Instantiate a commit graph from an `.git/objects/info` directory.
    ///
    /// Chain entries and graph files must use `object_hash`.
    pub fn from_info_dir(info_dir: &Path, object_hash: gix_hash::Kind) -> Result<Self> {
        Self::from_file(&info_dir.join("commit-graph"), object_hash).or_else(|err| {
            if err.is_not_found() {
                Self::from_commit_graphs_dir(&info_dir.join("commit-graphs"), object_hash)
            } else {
                Err(err)
            }
        })
    }

    /// Create a new commit graph from a list of `files`.
    ///
    /// Invalid file combinations are classified as [`gix_error::Class::Validation`].
    pub fn new(files: Vec<File>) -> Result<Self> {
        if files.len() > 256 {
            bail!(validation("Commit-graph must contain at most 256 files"));
        }
        let mut files = nonempty::NonEmpty::from_vec(files)
            .ok_or_raise(|| validation("Commit-graph must contain at least one file"))?;
        let num_commits: u64 = files.iter().map(|f| u64::from(f.num_commits())).sum();
        if num_commits > u64::from(MAX_COMMITS) {
            bail!(
                "Commit-graph files contain {num_commits} commits altogether, but only {MAX_COMMITS} commits are allowed".validation()
            );
        }

        let mut f1 = files.first();
        for f2 in files.tail() {
            if f1.object_hash() != f2.object_hash() {
                bail!(
                    "Commit-graph files mismatch: \"{path1}\" uses hash {hash1:?}, but \"{path2}\" uses hash {hash2:?}"
                        .validation(),
                    path1 = f1.path().display(),
                    hash1 = f1.object_hash(),
                    path2 = f2.path().display(),
                    hash2 = f2.object_hash(),
                );
            }
            f1 = f2;
        }

        let mut parent_position_limit = 0;
        for file in files.iter_mut() {
            parent_position_limit += file.num_commits();
            file.parent_position_limit = parent_position_limit;
        }
        Ok(Self { files })
    }
}

/// Read bounded chain entries of `object_hash` and open their graph files in chain order.
fn read_chain_files(
    chain_file: std::fs::File,
    chain_file_path: &Path,
    commit_graphs_dir: &Path,
    object_hash: gix_hash::Kind,
) -> Result<Vec<File>> {
    let mut files = Vec::new();
    let mut reader = BufReader::new(chain_file);
    let mut line = Vec::with_capacity(object_hash.len_in_hex() + 2 /* CRLF */);
    loop {
        line.clear();
        // Read one extra byte to detect oversized entries without buffering an unbounded line.
        let bytes = reader
            .by_ref()
            .take((object_hash.len_in_hex() + 2 /* CRLF */ + 1/* detect oversized entries */) as u64)
            .read_until(b'\n', &mut line)
            .or_raise(|| {
                message!(
                    "Could not read (enough data) from commit-graph file at \"{}\"",
                    chain_file_path.display()
                )
            })?;
        if bytes == 0 {
            break;
        }
        if line.len() > object_hash.len_in_hex() + 2
        /* CRLF */
        {
            bail!(corruption("Commit-graph chain entry exceeds the maximum hash length"));
        }
        if line.last() == Some(&b'\n') {
            line.pop();
            if line.last() == Some(&b'\r') {
                line.pop();
            }
        }
        if line.len() != object_hash.len_in_hex() {
            bail!(
                "Commit-graph chain entry has {} hex digits, but hash kind {object_hash} requires {}".corrupted(),
                line.len(),
                object_hash.len_in_hex()
            );
        }
        gix_hash::ObjectId::from_hex(&line)
            .or_raise(|| corruption("Commit-graph chain entry is not a valid object ID"))?;
        let hash = std::str::from_utf8(&line).expect("validated hexadecimal object IDs contain only ASCII");
        if files.len() == 256 {
            bail!(corruption("Commit-graph chain contains more than 256 files"));
        }
        let graph_file_path = commit_graphs_dir.join(format!("graph-{hash}.graph"));
        files.push(read_graph_file(&graph_file_path, object_hash)?);
    }
    Ok(files)
}

/// Open a graph file and require its header to declare `object_hash`.
fn read_graph_file(path: &Path, object_hash: gix_hash::Kind) -> Result<File> {
    let file = File::at(path)?;
    if file.object_hash() != object_hash {
        bail!(
            "Commit-graph file at \"{}\" uses hash kind {}, but expected {object_hash}".corrupted(),
            path.display(),
            file.object_hash()
        );
    }
    Ok(file)
}