gix_commitgraph/
verify.rs

1//! Auxiliary types used by graph verification methods.
2use gix_error::Result;
3use std::{
4    cmp::{max, min},
5    collections::BTreeMap,
6};
7
8use gix_error::{ResultExt, bail};
9
10use crate::{
11    GENERATION_NUMBER_MAX, Graph, Position,
12    file::{self},
13};
14
15/// Statistics gathered while verifying the integrity of the graph as returned by [`Graph::verify_integrity()`].
16#[derive(Clone, Debug, Eq, PartialEq)]
17#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
18pub struct Outcome {
19    /// The length of the longest path between any two commits in this graph.
20    ///
21    /// For example, this will be `Some(9)` for a commit graph containing 10 linear commits.
22    /// This will be `Some(0)` for a commit graph containing 0 or 1 commits.
23    /// If the longest path length is too large to fit in a [u32], then this will be [None].
24    pub longest_path_length: Option<u32>,
25    /// The total number of commits traversed.
26    pub num_commits: u32,
27    /// A mapping of `N -> number of commits with N parents`.
28    pub parent_counts: BTreeMap<u32, u32>,
29}
30
31impl Graph {
32    /// Traverse all commits in the graph and call `processor(&commit) -> Result<(), E>` on it while verifying checksums.
33    ///
34    /// When `processor` returns an error, the entire verification is stopped and the error returned.
35    pub fn verify_integrity<E>(
36        &self,
37        mut processor: impl FnMut(&file::Commit<'_>) -> std::result::Result<(), E>,
38    ) -> Result<Outcome>
39    where
40        E: std::error::Error + Send + Sync + 'static,
41    {
42        if self.files.len() > 256 {
43            // A file in a split chain can only have up to 255 base files.
44            bail!(
45                "Commit-graph should be composed of at most 256 files but actually contains {} files".corrupted(),
46                self.files.len()
47            );
48        }
49
50        let mut stats = Outcome {
51            longest_path_length: None,
52            num_commits: 0,
53            parent_counts: BTreeMap::new(),
54        };
55        let mut max_generation = 0u32;
56
57        // TODO: Detect duplicate commit IDs across different files. Not sure how to do this without
58        //   a separate loop, e.g. self.iter_sorted_ids().
59
60        let mut file_start_pos = Position(0);
61        for (file_index, file) in self.files.iter().enumerate() {
62            if usize::from(file.base_graph_count()) != file_index {
63                bail!(
64                    "\"{}\" should have {} base graphs, but claims {} base graphs".corrupted(),
65                    file.path().display(),
66                    file_index,
67                    file.base_graph_count()
68                );
69            }
70
71            for (base_graph_index, (expected, actual)) in self
72                .files
73                .iter()
74                .take(file_index)
75                .map(crate::File::checksum)
76                .zip(file.iter_base_graph_ids())
77                .enumerate()
78            {
79                if actual != expected {
80                    bail!(
81                        "\"{}\" base graph at index {} should have ID {} but is {}".corrupted(),
82                        file.path().display(),
83                        base_graph_index,
84                        expected,
85                        actual
86                    );
87                }
88            }
89
90            let next_file_start_pos = Position(file_start_pos.0 + file.num_commits());
91            let file_stats = file.traverse(|commit| {
92                let mut max_parent_generation = 0u32;
93                let mut has_uncomputed_parent_generation = false;
94                for parent_pos in commit.iter_parents() {
95                    let parent_pos = parent_pos?;
96                    if parent_pos >= next_file_start_pos {
97                        bail!(
98                            "Commit {} has parent position {parent_pos} that is out of range (should be in range 0-{})".corrupted(),
99                            commit.id(),
100                            Position(next_file_start_pos.0 - 1)
101                        );
102                    }
103                    let parent = self.commit_at(parent_pos);
104                    max_parent_generation = max(max_parent_generation, parent.generation());
105                    has_uncomputed_parent_generation |= parent.generation() == 0;
106                }
107
108                // Zero denotes legacy, uncomputed generations, not corrupt data.
109                if commit.generation() == 0 || has_uncomputed_parent_generation {
110                    bail!(
111                        "Cannot verify generation numbers for commit {} because it or a parent has an uncomputed generation".unsupported(),
112                        commit.id()
113                    );
114                }
115
116                // If the max parent generation is GENERATION_NUMBER_MAX, then this commit's
117                // generation should be GENERATION_NUMBER_MAX too.
118                let expected_generation = min(max_parent_generation + 1, GENERATION_NUMBER_MAX);
119                if commit.generation() != expected_generation {
120                    bail!(
121                        "Commit {}'s generation should be {expected_generation} but is {}".corrupted(),
122                        commit.id(),
123                        commit.generation()
124                    );
125                }
126
127                processor(commit).or_error()?;
128
129                Ok(())
130            })?;
131
132            max_generation = max(max_generation, file_stats.max_generation);
133            stats.num_commits += file_stats.num_commits;
134            for (key, value) in file_stats.parent_counts.into_iter() {
135                *stats.parent_counts.entry(key).or_insert(0) += value;
136            }
137            file_start_pos = next_file_start_pos;
138        }
139
140        stats.longest_path_length = if max_generation < GENERATION_NUMBER_MAX {
141            Some(max_generation.saturating_sub(1))
142        } else {
143            None
144        };
145        Ok(stats)
146    }
147}
gix_commitgraph/verify.rs

gix_commitgraph/
verify.rs
