vendor/gix-commitgraph/src/verify.rs

   1 //! Auxiliary types used by graph verification methods.
   2 use std::{
   3     cmp::{max, min},
   4     collections::BTreeMap,
   5     convert::TryInto,
   6     path::PathBuf,
   7 };
   8
   9 use crate::{
  10     file::{self, commit},
  11     Graph, Position, GENERATION_NUMBER_MAX,
  12 };
  13
  14 /// The error used in [`verify_integrity()`][Graph::verify_integrity].
  15 #[derive(thiserror::Error, Debug)]
  16 #[allow(missing_docs)]
  17 pub enum Error<E: std::error::Error + 'static> {
  18     #[error("'{}' should have {expected} base graphs, but claims {actual} base graphs", .path.display())]
  19     BaseGraphCount { actual: u8, expected: u8, path: PathBuf },
  20     #[error("'{}' base graph at index {index} should have ID {expected} but is {actual}", .path.display())]
  21     BaseGraphId {
  22         actual: gix_hash::ObjectId,
  23         expected: gix_hash::ObjectId,
  24         index: u8,
  25         path: PathBuf,
  26     },
  27     #[error(transparent)]
  28     Commit(#[from] commit::Error),
  29     #[error("{}: {err}", .path.display())]
  30     File {
  31         // Use zero-size error type. We will never return
  32         // `graph::verify::Error::File(file::verify::Error::Processor(...))`, because we are the
  33         // file's processor, and we convert`file::verify::Error::Processor<graph::verify::Error>`
  34         // variants into direct `graph::verify::Error` values.
  35         err: file::verify::Error<std::convert::Infallible>,
  36         path: PathBuf,
  37     },
  38     #[error("Commit {id}'s generation should be {expected} but is {actual}")]
  39     Generation {
  40         actual: u32,
  41         expected: u32,
  42         id: gix_hash::ObjectId,
  43     },
  44     #[error(
  45         "Commit {id} has parent position {parent_pos} that is out of range (should be in range 0-{max_valid_pos})"
  46     )]
  47     ParentOutOfRange {
  48         id: gix_hash::ObjectId,
  49         max_valid_pos: Position,
  50         parent_pos: Position,
  51     },
  52     #[error("{0}")]
  53     Processor(#[source] E),
  54     #[error("Commit-graph should be composed of at most 256 files but actually contains {0} files")]
  55     TooManyFiles(usize),
  56 }
  57
  58 /// Statistics gathered while verifying the integrity of the graph as returned by [`Graph::verify_integrity()`].
  59 #[derive(Clone, Debug, Eq, PartialEq)]
  60 #[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
  61 pub struct Outcome {
  62     /// The length of the longest path between any two commits in this graph.
  63     ///
  64     /// For example, this will be `Some(9)` for a commit graph containing 10 linear commits.
  65     /// This will be `Some(0)` for a commit graph containing 0 or 1 commits.
  66     /// If the longest path length is too large to fit in a [u32], then this will be [None].
  67     pub longest_path_length: Option<u32>,
  68     /// The total number of commits traversed.
  69     pub num_commits: u32,
  70     /// A mapping of `N -> number of commits with N parents`.
  71     pub parent_counts: BTreeMap<u32, u32>,
  72 }
  73
  74 impl Graph {
  75     /// Traverse all commits in the graph and call `processor(&commit) -> Result<(), E>` on it while verifying checksums.
  76     ///
  77     /// When `processor` returns an error, the entire verification is stopped and the error returned.
  78     pub fn verify_integrity<E>(
  79         &self,
  80         mut processor: impl FnMut(&file::Commit<'_>) -> Result<(), E>,
  81     ) -> Result<Outcome, Error<E>>
  82     where
  83         E: std::error::Error + 'static,
  84     {
  85         if self.files.len() > 256 {
  86             // A file in a split chain can only have up to 255 base files.
  87             return Err(Error::TooManyFiles(self.files.len()));
  88         }
  89
  90         let mut stats = Outcome {
  91             longest_path_length: None,
  92             num_commits: 0,
  93             parent_counts: BTreeMap::new(),
  94         };
  95         let mut max_generation = 0u32;
  96
  97         // TODO: Detect duplicate commit IDs across different files. Not sure how to do this without
  98         //   a separate loop, e.g. self.iter_sorted_ids().
  99
 100         let mut file_start_pos = Position(0);
 101         for (file_index, file) in self.files.iter().enumerate() {
 102             if usize::from(file.base_graph_count()) != file_index {
 103                 return Err(Error::BaseGraphCount {
 104                     actual: file.base_graph_count(),
 105                     expected: file_index
 106                         .try_into()
 107                         .expect("files.len() check to protect against this"),
 108                     path: file.path().to_owned(),
 109                 });
 110             }
 111
 112             for (base_graph_index, (expected, actual)) in self.files[..file_index]
 113                 .iter()
 114                 .map(crate::File::checksum)
 115                 .zip(file.iter_base_graph_ids())
 116                 .enumerate()
 117             {
 118                 if actual != expected {
 119                     return Err(Error::BaseGraphId {
 120                         actual: actual.into(),
 121                         expected: expected.into(),
 122                         index: base_graph_index
 123                             .try_into()
 124                             .expect("files.len() check to protect against this"),
 125                         path: file.path().to_owned(),
 126                     });
 127                 }
 128             }
 129
 130             let next_file_start_pos = Position(file_start_pos.0 + file.num_commits());
 131             let file_stats = file
 132                 .traverse(|commit| {
 133                     let mut max_parent_generation = 0u32;
 134                     for parent_pos in commit.iter_parents() {
 135                         let parent_pos = parent_pos.map_err(Error::Commit)?;
 136                         if parent_pos >= next_file_start_pos {
 137                             return Err(Error::ParentOutOfRange {
 138                                 parent_pos,
 139                                 id: commit.id().into(),
 140                                 max_valid_pos: Position(next_file_start_pos.0 - 1),
 141                             });
 142                         }
 143                         let parent = self.commit_at(parent_pos);
 144                         max_parent_generation = max(max_parent_generation, parent.generation());
 145                     }
 146
 147                     // If the max parent generation is GENERATION_NUMBER_MAX, then this commit's
 148                     // generation should be GENERATION_NUMBER_MAX too.
 149                     let expected_generation = min(max_parent_generation + 1, GENERATION_NUMBER_MAX);
 150                     if commit.generation() != expected_generation {
 151                         return Err(Error::Generation {
 152                             actual: commit.generation(),
 153                             expected: expected_generation,
 154                             id: commit.id().into(),
 155                         });
 156                     }
 157
 158                     processor(commit).map_err(Error::Processor)?;
 159
 160                     Ok(())
 161                 })
 162                 .map_err(|err| Error::File {
 163                     err: match err {
 164                         file::verify::Error::Processor(e) => return e,
 165                         file::verify::Error::RootTreeId { id, root_tree_id } => {
 166                             file::verify::Error::RootTreeId { id, root_tree_id }
 167                         }
 168                         file::verify::Error::Mismatch { actual, expected } => {
 169                             file::verify::Error::Mismatch { actual, expected }
 170                         }
 171                         file::verify::Error::Generation { generation, id } => {
 172                             file::verify::Error::Generation { generation, id }
 173                         }
 174                         file::verify::Error::Filename(expected) => file::verify::Error::Filename(expected),
 175                         file::verify::Error::Commit(err) => file::verify::Error::Commit(err),
 176                         file::verify::Error::CommitId { id, pos } => file::verify::Error::CommitId { id, pos },
 177                         file::verify::Error::CommitsOutOfOrder {
 178                             id,
 179                             pos,
 180                             predecessor_id,
 181                         } => file::verify::Error::CommitsOutOfOrder {
 182                             id,
 183                             pos,
 184                             predecessor_id,
 185                         },
 186                     },
 187                     path: file.path().to_owned(),
 188                 })?;
 189
 190             max_generation = max(max_generation, file_stats.max_generation);
 191             stats.num_commits += file_stats.num_commits;
 192             for (key, value) in file_stats.parent_counts.into_iter() {
 193                 *stats.parent_counts.entry(key).or_insert(0) += value;
 194             }
 195             file_start_pos = next_file_start_pos;
 196         }
 197
 198         stats.longest_path_length = if max_generation < GENERATION_NUMBER_MAX {
 199             Some(max_generation.saturating_sub(1))
 200         } else {
 201             None
 202         };
 203         Ok(stats)
 204     }
 205 }