//! Auxiliary types used by graph verification methods.
use std::{
    cmp::{max, min},
    collections::BTreeMap,
};

use gix_error::{ErrorExt, Exn, Message, ResultExt, message};

use crate::{
    GENERATION_NUMBER_MAX, Graph, Position,
    file::{self},
};

/// Statistics gathered while verifying the integrity of the graph as returned by [`Graph::verify_integrity()`].
#[derive(Clone, Debug, Eq, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
pub struct Outcome {
    /// The length of the longest path between any two commits in this graph.
    ///
    /// For example, this will be `Some(9)` for a commit graph containing 10 linear commits.
    /// This will be `Some(0)` for a commit graph containing 0 or 1 commits.
    /// If the longest path length is too large to fit in a [u32], then this will be [None].
    pub longest_path_length: Option<u32>,
    /// The total number of commits traversed.
    pub num_commits: u32,
    /// A mapping of `N -> number of commits with N parents`.
    pub parent_counts: BTreeMap<u32, u32>,
}

impl Graph {
    /// Traverse all commits in the graph and call `processor(&commit) -> Result<(), E>` on it while verifying checksums.
    ///
    /// When `processor` returns an error, the entire verification is stopped and the error returned.
    pub fn verify_integrity<E>(
        &self,
        mut processor: impl FnMut(&file::Commit<'_>) -> Result<(), E>,
    ) -> Result<Outcome, Exn<Message>>
    where
        E: std::error::Error + Send + Sync + 'static,
    {
        if self.files.len() > 256 {
            // A file in a split chain can only have up to 255 base files.
            return Err(message!(
                "Commit-graph should be composed of at most 256 files but actually contains {} files",
                self.files.len()
            )
            .raise());
        }

        let mut stats = Outcome {
            longest_path_length: None,
            num_commits: 0,
            parent_counts: BTreeMap::new(),
        };
        let mut max_generation = 0u32;

        // TODO: Detect duplicate commit IDs across different files. Not sure how to do this without
        //   a separate loop, e.g. self.iter_sorted_ids().

        let mut file_start_pos = Position(0);
        for (file_index, file) in self.files.iter().enumerate() {
            if usize::from(file.base_graph_count()) != file_index {
                return Err(message!(
                    "'{}' should have {} base graphs, but claims {} base graphs",
                    file.path().display(),
                    file_index,
                    file.base_graph_count()
                )
                .raise());
            }

            for (base_graph_index, (expected, actual)) in self
                .files
                .iter()
                .take(file_index)
                .map(crate::File::checksum)
                .zip(file.iter_base_graph_ids())
                .enumerate()
            {
                if actual != expected {
                    return Err(message!(
                        "'{}' base graph at index {} should have ID {} but is {}",
                        file.path().display(),
                        base_graph_index,
                        expected,
                        actual
                    )
                    .raise());
                }
            }

            let next_file_start_pos = Position(file_start_pos.0 + file.num_commits());
            let file_stats = file.traverse(|commit| {
                let mut max_parent_generation = 0u32;
                let mut max_parent_corrected_date = None;
                for parent_pos in commit.iter_parents() {
                    let parent_pos = parent_pos.map_err(|err| err.raise_erased())?;
                    if parent_pos >= next_file_start_pos {
                        return Err(message!(
                            "Commit {} has parent position {parent_pos} that is out of range (should be in range 0-{})",
                            commit.id(),
                            Position(next_file_start_pos.0 - 1)
                        )
                        .raise_erased());
                    }
                    let parent = self.commit_at(parent_pos);
                    max_parent_generation = max(max_parent_generation, parent.generation());
                    let parent_corrected_date = parent.corrected_commit_date().map_err(|err| err.raise_erased())?;
                    max_parent_corrected_date = max(max_parent_corrected_date, parent_corrected_date);
                }

                // If the max parent generation is GENERATION_NUMBER_MAX, then this commit's
                // generation should be GENERATION_NUMBER_MAX too.
                let expected_generation = min(max_parent_generation + 1, GENERATION_NUMBER_MAX);
                if commit.generation() != expected_generation {
                    return Err(message!(
                        "Commit {}'s generation should be {expected_generation} but is {}",
                        commit.id(),
                        commit.generation()
                    )
                    .raise_erased());
                }

                // Only check the lower bound, as dates beyond 34 bits are truncated in the graph.
                let corrected_date = commit.corrected_commit_date().map_err(|err| err.raise_erased())?;
                if let (Some(corrected_date), Some(max_parent_corrected_date)) = (corrected_date, max_parent_corrected_date)
                {
                    if corrected_date <= max_parent_corrected_date {
                        return Err(message!(
                            "Commit {}'s corrected commit date should be greater than {max_parent_corrected_date} but is {corrected_date}",
                            commit.id(),
                        )
                        .raise_erased());
                    }
                }

                processor(commit).or_raise_erased(|| message!("processor failed on commit {id}", id = commit.id()))?;

                Ok(())
            })?;

            max_generation = max(max_generation, file_stats.max_generation);
            stats.num_commits += file_stats.num_commits;
            for (key, value) in file_stats.parent_counts.into_iter() {
                *stats.parent_counts.entry(key).or_insert(0) += value;
            }
            file_start_pos = next_file_start_pos;
        }

        stats.longest_path_length = if max_generation < GENERATION_NUMBER_MAX {
            Some(max_generation.saturating_sub(1))
        } else {
            None
        };
        Ok(stats)
    }
}