Something went wrong. Try again.
Monorepo for Tangled forked from tangled.org/core
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143//! Write commit-graph files.use std::{cmp::Ordering, collections::HashSet, io::Write};
use gix_error::{ErrorExt, Exn, Message, ResultExt, message};use gix_hash::ObjectId;use gix_object::{CommitRefIter, Find, Kind, TagRefIter, TreeRefIter, tree::EntryRef};
mod info_dir;pub use info_dir::write_to_info_dir;
use crate::{ BloomFilterSettings, File, Graph, Position, bloom::BloomKey, file::{ BASE_GRAPHS_LIST_CHUNK_ID, BLOOM_FILTER_DATA_CHUNK_ID, BLOOM_FILTER_INDEX_CHUNK_ID, COMMIT_DATA_CHUNK_ID, CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW, EXTENDED_EDGES_LIST_CHUNK_ID, EXTENDED_EDGES_MASK, GENERATION_DATA_CHUNK_ID, GENERATION_DATA_OVERFLOW_CHUNK_ID, LAST_EXTENDED_EDGE_MASK, NO_PARENT, OID_FAN_CHUNK_ID, OID_LOOKUP_CHUNK_ID, SIGNATURE, },};
const GENERATION_NUMBER_MAX: u32 = 0x3FFF_FFFF;const CORRECTED_COMMIT_DATE_OFFSET_MAX: u64 = (1 << 31) - 1;const COMMIT_DATE_MASK: u64 = 0x3_FFFF_FFFF;const BLOOM_MAX_CHANGED_PATHS: usize = 512;
/// Choose the changed-path Bloom filter settings for a write, or `None` to write no filters.////// * `existing` is the graph being replaced. Only its top layer's settings count, so once a layer is written/// without filters, later writes have none either. `None` drops filters, like `--no-changed-paths`./// * `changed_paths` requests filters even if the existing graph has none, like `--changed-paths`./// * `hash_version` (`commitGraph.changedPathsVersion`) overrides the existing graph's version.pub fn bloom_filter_settings( existing: Option<&Graph>, changed_paths: bool, hash_version: Option<u32>,) -> Option<BloomFilterSettings> { let existing = existing.and_then(|graph| graph.files.last().bloom_filter_settings()); let mut settings = existing.or(changed_paths.then_some(BloomFilterSettings { hash_version: 1, num_hashes: 7, bits_per_entry: 10, }))?; settings.hash_version = match hash_version.unwrap_or(settings.hash_version) { 2 => 2, _ => 1, }; Some(settings)}
/// Options for [`write()`].#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]pub struct Options { /// The kind of hash the objects use. pub object_hash: gix_hash::Kind, /// Changed-path Bloom filter settings, or `None` to write no filters. See [`bloom_filter_settings()`]. pub bloom_settings: Option<BloomFilterSettings>, /// Compute at most this many filters, lowest generation first, like `--max-new-filters`. /// The other commits get no filter, which a later write can fill in. `None` means no limit. pub max_new_filters: Option<usize>, /// Compute filters on at most this many threads, or on all cores if `None`. pub thread_limit: Option<usize>, /// Write a single graph, or a layer on top of the existing graph's layers. pub split: Split,}
/// How to lay out the graph, like `git commit-graph write --split`.#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]pub enum Split { /// Write one graph with all commits, like writing without `--split`. #[default] No, /// Write a layer with the commits that aren't in the existing graph yet, like `--split`. /// /// The new layer absorbs the layers below it while the layer below has at most `size_multiple` times as /// many commits as the new layer (git's `--size-multiple`, 2 by default), or while the new layer has more /// than `max_commits` (git's `--max-commits`). Merge { /// How large the layer below may be relative to the new one to be merged into it. 0 means 2. size_multiple: u32, /// Keep merging layers while the new layer has more commits than this. max_commits: Option<u32>, }, /// Write a layer with the commits that aren't in the existing graph yet, and never merge, like `--split=no-merge`. NoMerge, /// Write a single layer with all commits, like `--split=replace`. Replace,}
/// The outcome of [`write()`].#[derive(Debug, Clone, Copy, PartialEq, Eq)]pub struct Outcome { /// The number of commits written to the graph. pub num_commits: u32, /// The number of changed-path Bloom filters that were computed. pub num_filters_computed: usize, /// The number of changed-path Bloom filters reused from the existing graph despite a different hash version, /// possible when no path in the commit's or its first parent's tree has a byte with the high bit set. pub num_filters_upgraded: usize, /// The checksum at the end of the file. pub checksum: ObjectId, /// The number of layers of the existing graph that the written layer is based on, from the bottom. /// The other layers were merged into it. Always 0 unless writing a layer with [`Split::Merge`] or [`Split::NoMerge`]. pub num_base_layers: usize,}
/// The commits to write, sorted by id.struct Commits { ids: Vec<ObjectId>, commits: Vec<Commit>, /// The positions of all parents in the graph including its base layers, see [`Commit::parents`]. parents: Vec<u32>, /// The number of commits in the base layers, which come before the ones written. num_commits_in_base: u32,}
#[derive(Clone, Copy)]struct Commit { tree: ObjectId, /// The range of the commit's parents in [`Commits::parents`]. parents: (u32, u32), seconds: i64, /// The generation and corrected commit date, if taken from the existing graph. known: Option<(u32, u64)>,}
impl Commits { fn parents(&self, pos: usize) -> &[u32] { let (start, end) = self.commits[pos].parents; &self.parents[start as usize..end as usize] }
/// Return the commit at `pos` in the graph including its base layers, if it's one of ours. fn at(&self, pos: u32) -> Option<&Commit> { pos.checked_sub(self.num_commits_in_base) .map(|pos| &self.commits[pos as usize]) }}
/// Write a commit-graph for all commits reachable from `tips` into `out`.////// `graph` is the existing commit-graph, if any. Commits and filters found in it are reused./// Add its commits to `tips` to keep them all, like `--append`.////// With [`Split::Merge`] or [`Split::NoMerge`], only the reachable commits that aren't in `graph` are written,/// along with the commits of the layers merged into the new one, which are kept if they still exist in `objects`./// [`Outcome::num_base_layers`] tells which layers the new one is based on. Nothing is written if there are no new commits.////// Tags in `tips` are peeled; tips that aren't commits are ignored./// It's an error if a tip or a reachable commit or tree is missing./// Returns `None` and writes nothing if there are no commits.////// Filters are computed in parallel, each thread with its own clone of `objects`.pub fn write( objects: &(impl Find + Clone + Send), graph: Option<&Graph>, tips: impl IntoIterator<Item = ObjectId>, Options { object_hash, bloom_settings, max_new_filters, thread_limit, split, }: Options, out: &mut impl std::io::Write,) -> Result<Option<Outcome>, Exn<Message>> { if let Some(graph) = graph.filter(|graph| graph.object_hash() != object_hash) { return Err(message!( "The commit-graph uses {}, but the objects use {object_hash}", graph.object_hash() ) .raise()); } let Some((commits, base_layers)) = collect(objects, graph, tips, split, object_hash)? else { return Ok(None); }; // Readers ignore generation data unless every layer has it. let write_generation_data = base_layers .last() .is_none_or(|file| file.has_generation_data()); let generation_data = generation_data(&commits, graph); let filters = match bloom_settings { Some(settings) => { // The budget goes to lower generations first. Without generation data, corrected dates // aren't computed, so only commit dates count. let mut order: Vec<usize> = (0..commits.ids.len()).collect(); order.sort_by_key(|&pos| { let corrected = if write_generation_data { generation_data[pos].1 } else { 0 }; (corrected, commits.commits[pos].seconds, pos) }); Some(changed_path_filters( objects, graph, &commits, &order, settings, max_new_filters.unwrap_or(usize::MAX), thread_limit, object_hash, )?) } None => None, }; let checksum = serialize( &commits, &generation_data, write_generation_data, bloom_settings.zip(filters.as_ref()), &base_layers, object_hash, out, ) .or_raise(|| message!("Could not write commit-graph"))?; Ok(Some(Outcome { num_commits: commits.ids.len() as u32, num_filters_computed: filters.as_ref().map_or(0, |filters| filters.ends.len()), num_filters_upgraded: filters.as_ref().map_or(0, |filters| filters.upgraded), checksum, num_base_layers: base_layers.len(), }))}
/// Return the commits to write and the layers of `graph` they are based on, or `None` if there is nothing to write.fn collect<'a>( objects: &impl Find, graph: Option<&'a Graph>, tips: impl IntoIterator<Item = ObjectId>, split: Split, object_hash: gix_hash::Kind,) -> Result<Option<(Commits, Vec<&'a File>)>, Exn<Message>> { let mut seeds = Vec::new(); for tip in tips { seeds.extend(peel_to_commit(objects, graph, tip, object_hash)?); } let mut walk = Walk::default(); let layers = graph.filter(|_| matches!(split, Split::Merge { .. } | Split::NoMerge)); let Some(graph) = layers else { walk.run(objects, graph, seeds, 0, &HashSet::new(), object_hash)?; if walk.ids.is_empty() && split != Split::Replace { return Ok(None); } return Ok(Some((walk.into_commits(graph, 0)?, Vec::new()))); };
// The number of new commits decides how many layers are merged, then the merged layers' commits are added. walk.run( objects, Some(graph), seeds, graph.num_commits(), &HashSet::new(), object_hash, )?; if walk.ids.is_empty() { return Ok(None); } let files: Vec<&File> = graph.files.iter().collect(); let num_base_layers = num_base_layers(&files, walk.ids.len(), split); let base_layers = files[..num_base_layers].to_vec(); let num_commits_in_base: u32 = base_layers.iter().map(|file| file.num_commits()).sum(); let (mut merged, mut missing) = (Vec::new(), HashSet::new()); let mut buf = Vec::new(); for pos in num_commits_in_base..graph.num_commits() { let id = graph.id_at(Position(pos)).to_owned(); // Drop commits that don't exist anymore. let exists = objects .try_find(&id, &mut buf) .map_err(|err| message!("Could not read object {id}: {err}"))? .is_some(); if exists { merged.push(id); } else { missing.insert(id); } } walk.run( objects, Some(graph), merged, num_commits_in_base, &missing, object_hash, )?; Ok(Some(( walk.into_commits(Some(graph), num_commits_in_base)?, base_layers, )))}
/// Return how many layers of `files` stay below a new layer with `num_new_commits`, see [`Split::Merge`].fn num_base_layers(files: &[&File], num_new_commits: usize, split: Split) -> usize { let mut num_base_layers = files.len(); if let Split::Merge { size_multiple, max_commits, } = split { let size_multiple = u64::from(if size_multiple == 0 { 2 } else { size_multiple }); let mut num_commits = num_new_commits as u64; while let Some(below) = num_base_layers .checked_sub(1) .map(|index| u64::from(files[index].num_commits())) { let too_many = max_commits.is_some_and(|max| num_commits > u64::from(max)); if below > size_multiple * num_commits && !too_many { break; } num_commits += below; num_base_layers -= 1; } } num_base_layers}
/// The commits found so far, in the order they were found.#[derive(Default)]struct Walk { index: gix_hashtable::HashMap<ObjectId, u32>, ids: Vec<ObjectId>, commits: Vec<Commit>, /// The parents of all commits, see [`Commit::parents`]. parent_ids: Vec<ObjectId>,}
impl Walk { /// Add `seeds` and the commits reachable from them, except the ones at positions before `stop_before` in `graph`. /// It's an error to reach `missing` commits. fn run( &mut self, objects: &impl Find, graph: Option<&Graph>, mut stack: Vec<ObjectId>, stop_before: u32, missing: &HashSet<ObjectId>, object_hash: gix_hash::Kind, ) -> Result<(), Exn<Message>> { let mut buf = Vec::new(); while let Some(id) = stack.pop() { if self.index.contains_key(&id) || (stop_before > 0 && graph .and_then(|graph| graph.lookup(id)) .is_some_and(|pos| pos.0 < stop_before)) { continue; } if missing.contains(&id) { return Err(message!( "Commit {id} is in the commit-graph, but it could not be found" ) .raise()); } let start = self.parent_ids.len(); let mut commit = match graph.and_then(|graph| from_graph(graph, &id, &mut self.parent_ids)) { Some(commit) => commit, None => { self.parent_ids.truncate(start); decode_commit(objects, &id, &mut buf, &mut self.parent_ids, object_hash)? } }; commit.parents = (start as u32, self.parent_ids.len() as u32); stack.extend_from_slice(&self.parent_ids[start..]); self.index.insert(id, self.ids.len() as u32); self.ids.push(id); self.commits.push(commit); } Ok(()) }
/// Sort the commits by id, placing them after the `num_commits_in_base` commits of `graph`'s base layers. fn into_commits( self, graph: Option<&Graph>, num_commits_in_base: u32, ) -> Result<Commits, Exn<Message>> { let mut order: Vec<u32> = (0..self.ids.len() as u32).collect(); order.sort_unstable_by_key(|&index| self.ids[index as usize]); let mut position = vec![0u32; self.ids.len()]; for (pos, &index) in order.iter().enumerate() { position[index as usize] = num_commits_in_base + pos as u32; } let mut sorted = Commits { ids: Vec::with_capacity(self.ids.len()), commits: Vec::with_capacity(self.ids.len()), parents: Vec::with_capacity(self.parent_ids.len()), num_commits_in_base, }; for index in order { let (id, mut commit) = (self.ids[index as usize], self.commits[index as usize]); let (start, end) = commit.parents; let new_start = sorted.parents.len() as u32; for parent in &self.parent_ids[start as usize..end as usize] { let pos = match self.index.get(parent) { Some(&index) => position[index as usize], None => graph .and_then(|graph| graph.lookup(parent)) .map(|pos| pos.0) .filter(|&pos| pos < num_commits_in_base) .ok_or_else(|| message!("Parent {parent} of commit {id} is missing"))?, }; sorted.parents.push(pos); } commit.parents = (new_start, sorted.parents.len() as u32); sorted.ids.push(id); sorted.commits.push(commit); } Ok(sorted) }}
/// Read `id` from `graph` and put its parents into `parents`, or return `None` if it's not there or lacks generation data./// The returned commit's parents aren't set.////// Without generation data, the corrected date needs the full commit date, which the graph stores in 34 bits only.fn from_graph(graph: &Graph, id: &ObjectId, parents: &mut Vec<ObjectId>) -> Option<Commit> { let commit = graph.commit_by_id(id)?; let corrected = commit.corrected_commit_date().ok()??; for parent in commit.iter_parents() { let pos = parent.ok().filter(|pos| pos.0 < graph.num_commits())?; parents.push(graph.id_at(pos).to_owned()); } Some(Commit { tree: commit.root_tree_id().to_owned(), parents: (0, 0), seconds: commit.committer_timestamp() as i64, known: Some((commit.generation(), corrected)), })}
/// Decode commit `id` from `objects` and put its parents into `parents`. The returned commit's parents aren't set.fn decode_commit( objects: &impl Find, id: &ObjectId, buf: &mut Vec<u8>, parents: &mut Vec<ObjectId>, object_hash: gix_hash::Kind,) -> Result<Commit, Exn<Message>> { use gix_object::commit::ref_iter::Token; let data = find(objects, id, buf)?; if data.kind != Kind::Commit { return Err(message!("Object {id} is a {}, expected a commit", data.kind).raise()); } let (mut tree, mut seconds) = (None, 0); for token in CommitRefIter::from_bytes(data.data, object_hash) { match token.or_raise(|| message!("Could not decode commit {id}"))? { Token::Tree { id } => tree = Some(id), Token::Parent { id } => parents.push(id), Token::Committer { signature } => { seconds = signature.seconds(); break; } _ => {} } } Ok(Commit { tree: tree.ok_or_else(|| message!("Commit {id} has no tree"))?, parents: (0, 0), seconds, known: None, })}
fn find<'a>( objects: &impl Find, id: &ObjectId, buf: &'a mut Vec<u8>,) -> Result<gix_object::Data<'a>, Exn<Message>> { objects .try_find(id, buf) .map_err(|err| message!("Could not read object {id}: {err}"))? .ok_or_else(|| message!("Object {id} could not be found").into())}
/// Peel `id` to a commit, or return `None` if it points to another kind of object./// Commits in `graph` aren't read.fn peel_to_commit( objects: &impl Find, graph: Option<&Graph>, mut id: ObjectId, object_hash: gix_hash::Kind,) -> Result<Option<ObjectId>, Exn<Message>> { let mut buf = Vec::new(); loop { if graph.is_some_and(|graph| graph.lookup(id).is_some()) { return Ok(Some(id)); } let data = find(objects, &id, &mut buf)?; match data.kind { Kind::Commit => return Ok(Some(id)), Kind::Tag => { id = TagRefIter::from_bytes(data.data, object_hash) .target_id() .or_raise(|| message!("Could not decode tag {id}"))?; } _ => return Ok(None), } }}
/// Return the generation and corrected commit date of each commit./// Commits taken from the existing graph keep theirs, and so do parents in its base layers.fn generation_data(commits: &Commits, graph: Option<&Graph>) -> Vec<(u32, u64)> { let mut out: Vec<Option<(u32, u64)>> = commits.commits.iter().map(|commit| commit.known).collect(); let num_commits_in_base = commits.num_commits_in_base; let value = |out: &[Option<(u32, u64)>], parent: u32| match parent.checked_sub(num_commits_in_base) { Some(pos) => out[pos as usize], None => Some(base_generation_data( graph.expect("parents in base layers are in the graph"), parent, )), }; let mut stack = Vec::new(); for root in 0..out.len() { stack.push(root); while let Some(&top) = stack.last() { if out[top].is_some() { stack.pop(); continue; } let parents = commits.parents(top); let before = stack.len(); stack.extend( parents .iter() .filter(|&&parent| value(&out, parent).is_none()) .map(|&parent| (parent - num_commits_in_base) as usize), ); if stack.len() == before { let (generation, date) = parents.iter().fold((0, 0), |(generation, date), &parent| { let (parent_generation, parent_date) = value(&out, parent).expect("parents are done"); (generation.max(parent_generation), date.max(parent_date)) }); let seconds = commits.commits[top].seconds.max(0) as u64; out[top] = Some(( generation.saturating_add(1).min(GENERATION_NUMBER_MAX), if seconds > date { seconds } else { date + 1 }, )); stack.pop(); } } } out.into_iter() .map(|data| data.expect("every commit was visited")) .collect()}
/// Return the generation and corrected commit date of the commit at `pos` in `graph`./// If the graph's generation data can't be used, the generation is taken as corrected date.fn base_generation_data(graph: &Graph, pos: u32) -> (u32, u64) { let commit = graph.commit_at(Position(pos)); let generation = commit.generation(); let corrected = commit.corrected_commit_date().ok().flatten(); (generation, corrected.unwrap_or(u64::from(generation)))}
/// Where a commit's filter comes from.#[derive(Clone, Copy)]enum Filter<'a> { /// Not computed, written with zero length. Missing, /// Reused from the existing graph. Stored(&'a [u8]), /// The filter computed at this index. Computed(usize),}
/// The changed-path Bloom filter of each commit.struct Filters<'a> { by_position: Vec<Filter<'a>>, /// The computed filters, one after another. data: Vec<u8>, /// The end of each computed filter in `data`. ends: Vec<usize>, /// How many stored filters were upgraded to another hash version. upgraded: usize,}
impl Filters<'_> { fn get(&self, pos: usize) -> &[u8] { match self.by_position[pos] { Filter::Missing => &[], Filter::Stored(filter) => filter, Filter::Computed(index) => { let start = index .checked_sub(1) .map_or(0, |previous| self.ends[previous]); &self.data[start..self.ends[index]] } } }}
/// Return the filters of the commits in `order`./// Commits beyond the `max_new_filters` budget get no filter, unless one with the same hash version can be reused.#[allow(clippy::too_many_arguments)]fn changed_path_filters<'a>( objects: &(impl Find + Clone + Send), graph: Option<&'a Graph>, commits: &Commits, order: &[usize], settings: BloomFilterSettings, max_new_filters: usize, thread_limit: Option<usize>, object_hash: gix_hash::Kind,) -> Result<Filters<'a>, Exn<Message>> { let mut by_position = vec![Filter::Missing; commits.ids.len()]; let mut upgraded = 0; let mut clean_trees = HashSet::new(); // The first parent's tree and the commit's tree of each filter to compute. let mut jobs: Vec<(Option<ObjectId>, ObjectId)> = Vec::new(); for &pos in order { let tree = commits.commits[pos].tree; let parent_tree = commits .parents(pos) .first() .map(|&parent| match commits.at(parent) { Some(commit) => commit.tree, None => graph .expect("parents in base layers are in the graph") .commit_at(Position(parent)) .root_tree_id() .to_owned(), }); let may_compute = jobs.len() < max_new_filters; if let Some((stored, version)) = graph.and_then(|graph| stored_filter(graph, &commits.ids[pos], settings)) { let reuse = version == settings.hash_version || (may_compute && !has_high_bit_paths(objects, Some(tree), &mut clean_trees, object_hash)? && !has_high_bit_paths(objects, parent_tree, &mut clean_trees, object_hash)?); if reuse { upgraded += usize::from(version != settings.hash_version); by_position[pos] = Filter::Stored(stored); continue; } } if may_compute { by_position[pos] = Filter::Computed(jobs.len()); jobs.push((parent_tree, tree)); } } drop(clean_trees); // Newest first: packs store newer objects as bases of older ones, and only the objects // read are cached, so this way the trees just read are the bases of the next ones. jobs.reverse(); for filter in &mut by_position { if let Filter::Computed(index) = filter { *index = jobs.len() - 1 - *index; } }
// Large chunks of consecutive commits keep each thread's trees close together, which matters more than // balancing the load: with 10000 the linux kernel's filters are computed 15% faster than with 1000. let chunk_size = (jobs.len() / (gix_features::parallel::num_threads(thread_limit) * 8)).clamp(1, 10_000); let chunks = jobs.chunks(chunk_size); let num_chunks = chunks.len(); let computed = gix_features::parallel::in_parallel( chunks.enumerate(), thread_limit, { let objects = objects.clone(); move |_| (objects, TreeDiff::default()) }, |(index, chunk), (objects, diff)| -> Result<_, Exn<Message>> { let mut data = Vec::new(); let mut ends = Vec::with_capacity(chunk.len()); for &(parent_tree, tree) in chunk { diff.changed_paths(objects, parent_tree, tree, object_hash)?; diff.changes.add_filter_to(&mut data, settings); ends.push(data.len()); } Ok((index, data, ends)) }, InOrder(vec![None; num_chunks]), )?;
let mut filters = Filters { by_position, data: Vec::with_capacity(computed.iter().map(|(data, _)| data.len()).sum()), ends: Vec::with_capacity(jobs.len()), upgraded, }; for (data, ends) in computed { let offset = filters.data.len(); filters.data.extend_from_slice(&data); filters .ends .extend(ends.into_iter().map(|end| offset + end)); } Ok(filters)}
/// Collect the computed filters of each chunk in chunk order.struct InOrder(Vec<Option<(Vec<u8>, Vec<usize>)>>);
impl gix_features::parallel::Reduce for InOrder { type Input = Result<(usize, Vec<u8>, Vec<usize>), Exn<Message>>; type FeedProduce = (); type Output = Vec<(Vec<u8>, Vec<usize>)>; type Error = Exn<Message>;
fn feed(&mut self, item: Self::Input) -> Result<(), Self::Error> { let (index, data, ends) = item?; self.0[index] = Some((data, ends)); Ok(()) }
fn finalize(self) -> Result<Self::Output, Self::Error> { Ok(self .0 .into_iter() .map(|chunk| chunk.expect("every chunk was computed")) .collect()) }}
/// Return the filter `graph` has for `id` and its hash version, unless it wasn't computed or used other parameters.fn stored_filter<'a>( graph: &'a Graph, id: &ObjectId, settings: BloomFilterSettings,) -> Option<(&'a [u8], u32)> { let commit = graph.commit_by_id(id)?; let stored = commit.file.bloom_filter_settings()?; let filter = commit.bloom_filter().filter(|filter| !filter.is_empty())?; (stored.num_hashes == settings.num_hashes && stored.bits_per_entry == settings.bits_per_entry) .then_some((filter, stored.hash_version))}
/// Return `true` if a path in `tree` has a byte with the high bit set./// Trees without such paths are added to `clean`.fn has_high_bit_paths( objects: &impl Find, tree: Option<ObjectId>, clean: &mut HashSet<ObjectId>, object_hash: gix_hash::Kind,) -> Result<bool, Exn<Message>> { let mut visited = HashSet::new(); let mut stack: Vec<ObjectId> = tree.into_iter().collect(); let mut buf = Vec::new(); while let Some(id) = stack.pop() { if id == ObjectId::empty_tree(object_hash) || clean.contains(&id) || !visited.insert(id) { continue; } let data = find(objects, &id, &mut buf)?; for entry in TreeRefIter::from_bytes(data.data, object_hash) { let entry = entry.or_raise(|| message!("Could not decode tree {id}"))?; if entry.filename.iter().any(|byte| byte & 0x80 != 0) { return Ok(true); } if entry.mode.is_tree() { stack.push(entry.oid.to_owned()); } } } clean.extend(visited); Ok(false)}
/// A recursive tree diff without rename detection that stops after [`BLOOM_MAX_CHANGED_PATHS`] changes./// Its buffers are reused across diffs.#[derive(Default)]struct TreeDiff { parent: Vec<u8>, commit: Vec<u8>, changes: Changes,}
#[derive(Default)]struct Changes { /// Pairs of subtrees still to compare, with their path and a trailing slash. pending: Vec<(Option<ObjectId>, Option<ObjectId>, Vec<u8>)>, /// The changed paths one after another, each ending at an offset in `ends`. paths: Vec<u8>, ends: Vec<usize>, /// If there were more than [`BLOOM_MAX_CHANGED_PATHS`] changes. too_many: bool,}
impl TreeDiff { /// Diff `parent` against `commit`, remembering the paths of all non-tree entries that differ. fn changed_paths( &mut self, objects: &impl Find, parent: Option<ObjectId>, commit: ObjectId, object_hash: gix_hash::Kind, ) -> Result<(), Exn<Message>> { let changes = &mut self.changes; changes.paths.clear(); changes.ends.clear(); changes.too_many = false; changes.pending.clear(); changes.pending.push((parent, Some(commit), Vec::new())); while let Some((parent, commit, prefix)) = changes.pending.pop() { let mut lhs = tree_iter(objects, parent, &mut self.parent, object_hash)?; let mut rhs = tree_iter(objects, commit, &mut self.commit, object_hash)?; let (mut left, mut right) = (next_entry(&mut lhs, parent)?, next_entry(&mut rhs, commit)?); loop { let order = match (&left, &right) { (None, None) => break, (Some(_), None) => Ordering::Less, (None, Some(_)) => Ordering::Greater, (Some(left), Some(right)) => left.cmp(right), }; match order { Ordering::Less => { let entry = left.take().expect("present"); changes.change(&prefix, entry, true); left = next_entry(&mut lhs, parent)?; } Ordering::Greater => { let entry = right.take().expect("present"); changes.change(&prefix, entry, false); right = next_entry(&mut rhs, commit)?; } Ordering::Equal => { let (old, new) = ( left.take().expect("present"), right.take().expect("present"), ); if old.oid != new.oid || old.mode.kind() != new.mode.kind() { if new.mode.is_tree() { changes.pending.push(( Some(old.oid.to_owned()), Some(new.oid.to_owned()), subtree_prefix(&prefix, new.filename), )); } else { changes.push_path(&prefix, new.filename); } } left = next_entry(&mut lhs, parent)?; right = next_entry(&mut rhs, commit)?; } } if changes.too_many { changes.pending.clear(); return Ok(()); } } } Ok(()) }}
impl Changes { /// Record `entry` as only being in the parent tree (`removed`) or only in the commit's tree. fn change(&mut self, prefix: &[u8], entry: EntryRef<'_>, removed: bool) { if entry.mode.is_tree() { let oid = Some(entry.oid.to_owned()); let prefix = subtree_prefix(prefix, entry.filename); self.pending.push(if removed { (oid, None, prefix) } else { (None, oid, prefix) }); } else { self.push_path(prefix, entry.filename); } }
fn push_path(&mut self, prefix: &[u8], name: &[u8]) { if self.ends.len() == BLOOM_MAX_CHANGED_PATHS { self.too_many = true; return; } self.paths.extend_from_slice(prefix); self.paths.extend_from_slice(name); self.ends.push(self.paths.len()); }
/// Append the filter of the last diff to `out`. fn add_filter_to(&self, out: &mut Vec<u8>, settings: BloomFilterSettings) { const TOO_LARGE: u8 = 0xFF; if self.too_many { out.push(TOO_LARGE); return; } let paths: HashSet<&[u8]> = self .ends .iter() .scan(0, |start, &end| { let path = &self.paths[*start..end]; *start = end; Some(path) }) .flat_map(prefixes) .collect(); if paths.len() > BLOOM_MAX_CHANGED_PATHS { out.push(TOO_LARGE); return; } let bits = paths.len() * settings.bits_per_entry as usize; let start = out.len(); out.resize(start + bits.div_ceil(8).max(1), 0); for path in paths { BloomKey::from_bytes(path, settings).add_to(&mut out[start..]); } }}
fn subtree_prefix(prefix: &[u8], name: &[u8]) -> Vec<u8> { [prefix, name, b"/"].concat()}
/// Read `tree` into `buf`, returning no entries if it's `None` or not a tree.fn tree_iter<'a>( objects: &impl Find, tree: Option<ObjectId>, buf: &'a mut Vec<u8>, object_hash: gix_hash::Kind,) -> Result<TreeRefIter<'a>, Exn<Message>> { let Some(id) = tree.filter(|id| *id != ObjectId::empty_tree(object_hash)) else { return Ok(TreeRefIter::from_bytes(&[], object_hash)); }; let data = find(objects, &id, buf)?; Ok(TreeRefIter::from_bytes( if data.kind == Kind::Tree { data.data } else { &[] }, object_hash, ))}
fn next_entry<'a>( iter: &mut TreeRefIter<'a>, tree: Option<ObjectId>,) -> Result<Option<EntryRef<'a>>, Exn<Message>> { iter.next().transpose().or_raise(|| { message!( "Could not decode tree {}", tree.map_or_else(String::new, |tree| tree.to_string()) ) })}
/// Return `path` and each of its leading directories.fn prefixes(path: &[u8]) -> impl Iterator<Item = &[u8]> { std::iter::once(path).chain( path.iter() .enumerate() .filter(|(_, byte)| **byte == b'/') .map(|(index, _)| &path[..index]), )}
/// Write the graph into `out` and return its checksum./// `base_layers` are the layers the graph is based on, from the bottom.fn serialize( commits: &Commits, generation_data: &[(u32, u64)], write_generation_data: bool, filters: Option<(BloomFilterSettings, &Filters<'_>)>, base_layers: &[&File], object_hash: gix_hash::Kind, out: &mut impl std::io::Write,) -> std::io::Result<ObjectId> { let num_commits = commits.ids.len() as u64; let hash_len = object_hash.len_in_bytes() as u64; // The offset is relative to the 34-bit commit date stored in `CDAT`. let offsets = || { commits .commits .iter() .zip(generation_data) .map(|(commit, (_, corrected))| { corrected.saturating_sub(commit.seconds.max(0) as u64 & COMMIT_DATE_MASK) }) }; let num_overflows = if write_generation_data { offsets() .filter(|&offset| offset > CORRECTED_COMMIT_DATE_OFFSET_MAX) .count() as u64 } else { 0 }; let num_edges: u64 = (0..commits.ids.len()) .map(|pos| commits.parents(pos).len()) .filter(|&len| len > 2) .map(|len| len as u64 - 1) .sum();
let mut index = gix_chunk::file::Index::for_writing(); index.plan_chunk(OID_FAN_CHUNK_ID, 256 * 4); index.plan_chunk(OID_LOOKUP_CHUNK_ID, num_commits * hash_len); index.plan_chunk(COMMIT_DATA_CHUNK_ID, num_commits * (hash_len + 16)); if write_generation_data { index.plan_chunk(GENERATION_DATA_CHUNK_ID, num_commits * 4); } if num_overflows > 0 { index.plan_chunk(GENERATION_DATA_OVERFLOW_CHUNK_ID, num_overflows * 8); } if num_edges > 0 { index.plan_chunk(EXTENDED_EDGES_LIST_CHUNK_ID, num_edges * 4); } if let Some((_, filters)) = filters { let filter_bytes: u64 = (0..commits.ids.len()) .map(|pos| filters.get(pos).len() as u64) .sum(); index.plan_chunk(BLOOM_FILTER_INDEX_CHUNK_ID, num_commits * 4); index.plan_chunk(BLOOM_FILTER_DATA_CHUNK_ID, 12 + filter_bytes); } if !base_layers.is_empty() { index.plan_chunk( BASE_GRAPHS_LIST_CHUNK_ID, base_layers.len() as u64 * hash_len, ); }
let mut out = std::io::BufWriter::new(gix_hash::io::Write::new(out, object_hash)); out.write_all(SIGNATURE)?; let hash_version = match object_hash { gix_hash::Kind::Sha1 => 1u8, _ => 2u8, }; let num_base_layers = u8::try_from(base_layers.len()) .map_err(|_| std::io::Error::other("Too many base layers"))?; out.write_all(&[1, hash_version, index.num_chunks() as u8, num_base_layers])?; let mut out = index.into_write(out, SIGNATURE.len() + 4)?; while let Some(chunk) = out.next_chunk() { match chunk { OID_FAN_CHUNK_ID => { let mut buckets = [0u32; 256]; for id in &commits.ids { buckets[id.as_slice()[0] as usize] += 1; } let mut total = 0; for count in buckets { total += count; out.write_all(&total.to_be_bytes())?; } } OID_LOOKUP_CHUNK_ID => { for id in &commits.ids { out.write_all(id.as_slice())?; } } COMMIT_DATA_CHUNK_ID => { let mut num_edges = 0; for (pos, (commit, (generation, _))) in commits.commits.iter().zip(generation_data).enumerate() { out.write_all(commit.tree.as_slice())?; let fields = match commits.parents(pos) { [] => [NO_PARENT, NO_PARENT], [first] => [*first, NO_PARENT], [first, second] => [*first, *second], [first, rest @ ..] => { let fields = [*first, EXTENDED_EDGES_MASK | num_edges]; num_edges += rest.len() as u32; fields } }; out.write_all(&fields[0].to_be_bytes())?; out.write_all(&fields[1].to_be_bytes())?; let date = (commit.seconds.max(0) as u64) & COMMIT_DATE_MASK; out.write_all(&((u64::from(*generation) << 34) | date).to_be_bytes())?; } } GENERATION_DATA_CHUNK_ID => { let mut num_overflows = 0; for offset in offsets() { let packed = if offset > CORRECTED_COMMIT_DATE_OFFSET_MAX { num_overflows += 1; CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW | (num_overflows - 1) } else { offset as u32 }; out.write_all(&packed.to_be_bytes())?; } } GENERATION_DATA_OVERFLOW_CHUNK_ID => { for offset in offsets().filter(|&offset| offset > CORRECTED_COMMIT_DATE_OFFSET_MAX) { out.write_all(&offset.to_be_bytes())?; } } EXTENDED_EDGES_LIST_CHUNK_ID => { for pos in 0..commits.ids.len() { if let [_, rest @ ..] = commits.parents(pos) && rest.len() > 1 { let (last, init) = rest.split_last().expect("more than one"); for parent in init { out.write_all(&parent.to_be_bytes())?; } out.write_all(&(last | LAST_EXTENDED_EDGE_MASK).to_be_bytes())?; } } } BLOOM_FILTER_INDEX_CHUNK_ID => { let (_, filters) = filters.expect("planned with filters"); let mut end = 0u32; for pos in 0..commits.ids.len() { end = end.saturating_add(filters.get(pos).len() as u32); out.write_all(&end.to_be_bytes())?; } } BLOOM_FILTER_DATA_CHUNK_ID => { let (settings, filters) = filters.expect("planned with filters"); for value in [ settings.hash_version, settings.num_hashes, settings.bits_per_entry, ] { out.write_all(&value.to_be_bytes())?; } for pos in 0..commits.ids.len() { out.write_all(filters.get(pos))?; } } BASE_GRAPHS_LIST_CHUNK_ID => { for file in base_layers { out.write_all(file.checksum().as_bytes())?; } } unknown => unreachable!("BUG: forgot to write chunk {unknown:?}"), } } let out = out .into_inner() .into_inner() .map_err(std::io::IntoInnerError::into_error)?; let checksum = out.hash.try_finalize().map_err(std::io::Error::other)?; out.inner.write_all(checksum.as_slice())?; Ok(checksum)}