//! 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)
}