use std::collections::VecDeque; /// Returned when using various methods on a [`Tree`]#[derive(thiserror::Error, Debug)]#[allow(missing_docs)]pub enum Error { #[error("Pack offsets must only increment. The previous pack offset was {last_pack_offset}, the current one is {pack_offset}")] InvariantIncreasingPackOffset { /// The last seen pack offset last_pack_offset: u64, /// The invariant violating offset pack_offset: u64, }, #[error("The delta at pack offset {delta_pack_offset} could not find its base at {base_pack_offset} - it should have been seen already")] InvariantBasesBeforeDeltasNeedThem { /// The delta pack offset whose base we could not find delta_pack_offset: u64, /// The base pack offset which was not yet added to the tree base_pack_offset: u64, },} mod iter;pub use iter::{Chunk, Node};///pub mod traverse; ///pub mod from_offsets; /// An item stored within the [`Tree`]pub struct Item<T> { /// The offset into the pack file at which the pack entry's data is located. pub offset: u64, /// The offset of the next item in the pack file. pub next_offset: u64, /// Data to store with each Item, effectively data associated with each entry in a pack. pub data: T, children: Vec<usize>,}/// A tree that allows one-time iteration over all nodes and their children, consuming it in the process,/// while being shareable among threads without a lock./// It does this by making the guarantee that iteration only happens once.pub struct Tree<T> { /// Roots are first, then children. items: VecDeque<Item<T>>, roots: usize, last_index: usize,} impl<T> Tree<T> { /// Instantiate a empty tree capable of storing `num_objects` amounts of items. pub fn with_capacity(num_objects: usize) -> Result<Self, Error> { Ok(Tree { items: VecDeque::with_capacity(num_objects), roots: 0, last_index: 0, }) } fn assert_is_incrementing(&mut self, offset: u64) -> Result<(), Error> { if self.items.is_empty() { return Ok(()); } let last_offset = self.items[self.last_index].offset; if offset <= last_offset { return Err(Error::InvariantIncreasingPackOffset { last_pack_offset: last_offset, pack_offset: offset, }); } self.items[self.last_index].next_offset = offset; Ok(()) } fn set_pack_entries_end(&mut self, pack_entries_end: u64) { if !self.items.is_empty() { self.items[self.last_index].next_offset = pack_entries_end; } } /// Add a new root node, one that only has children but is not a child itself, at the given pack `offset` and associate /// custom `data` with it. pub fn add_root(&mut self, offset: u64, data: T) -> Result<(), Error> { self.assert_is_incrementing(offset)?; self.last_index = 0; self.items.push_front(Item { offset, next_offset: 0, data, children: Vec::new(), }); self.roots += 1; Ok(()) } /// Add a child of the item at `base_offset` which itself resides at pack `offset` and associate custom `data` with it. pub fn add_child(&mut self, base_offset: u64, offset: u64, data: T) -> Result<(), Error> { self.assert_is_incrementing(offset)?; let (roots, children) = self.items.as_mut_slices(); assert_eq!( roots.len(), self.roots, "item deque has been resized, maybe we added more nodes than we declared in the constructor?" ); if let Ok(i) = children.binary_search_by_key(&base_offset, |i| i.offset) { children[i].children.push(children.len()); } else if let Ok(i) = roots.binary_search_by(|i| base_offset.cmp(&i.offset)) { roots[i].children.push(children.len()); } else { return Err(Error::InvariantBasesBeforeDeltasNeedThem { delta_pack_offset: offset, base_pack_offset: base_offset, }); } self.last_index = self.items.len(); self.items.push_back(Item { offset, next_offset: 0, data, children: Vec::new(), }); Ok(()) } /// Transform this `Tree` into its items. pub fn into_items(self) -> VecDeque<Item<T>> { self.items }} #[cfg(test)]mod tests { mod tree { mod from_offsets_in_pack { use std::sync::atomic::AtomicBool; use git_odb::pack; const SMALL_PACK_INDEX: &str = "objects/pack/pack-a2bf8e71d8c18879e499335762dd95119d93d9f1.idx"; const SMALL_PACK: &str = "objects/pack/pack-a2bf8e71d8c18879e499335762dd95119d93d9f1.pack"; const INDEX_V1: &str = "objects/pack/pack-c0438c19fb16422b6bbcce24387b3264416d485b.idx"; const PACK_FOR_INDEX_V1: &str = "objects/pack/pack-c0438c19fb16422b6bbcce24387b3264416d485b.pack"; use git_testtools::fixture_path; #[test] fn v1() -> Result<(), Box<dyn std::error::Error>> { tree(INDEX_V1, PACK_FOR_INDEX_V1) } #[test] fn v2() -> Result<(), Box<dyn std::error::Error>> { tree(SMALL_PACK_INDEX, SMALL_PACK) } fn tree(index_path: &str, pack_path: &str) -> Result<(), Box<dyn std::error::Error>> { let idx = pack::index::File::at(fixture_path(index_path))?; crate::cache::delta::Tree::from_offsets_in_pack( idx.sorted_offsets().into_iter(), |ofs| *ofs, fixture_path(pack_path), git_features::progress::Discard, &AtomicBool::new(false), |id| idx.lookup(id).map(|index| idx.pack_offset_at_index(index)), )?; Ok(()) } } } struct TreeItem<D> { _offset: u64, _data: D, _children: Vec<usize>, } #[test] fn using_option_as_data_does_not_increase_size_in_memory() { struct Entry { pub _id: Option<git_hash::ObjectId>, pub _crc32: u32, } struct TreeItemOption<D> { _offset: u64, _data: Option<D>, _children: Vec<usize>, } assert_eq!( std::mem::size_of::<TreeItem<Entry>>(), std::mem::size_of::<TreeItemOption<Entry>>(), "we hope niche filling optimizations kick in for our data structures to not pay for the Option at all" ); assert_eq!( std::mem::size_of::<[TreeItemOption<Entry>; 7_500_000]>(), 480_000_000, "it should be as small as possible" ); } #[test] fn size_of_pack_verify_data_structure() { use git_odb::pack; pub struct EntryWithDefault { _index_entry: pack::index::Entry, _kind: git_object::Kind, _object_size: u64, _decompressed_size: u64, _compressed_size: u64, _header_size: u16, _level: u16, } assert_eq!( std::mem::size_of::<[TreeItem<EntryWithDefault>; 7_500_000]>(), 780_000_000 ); }}
use std::collections::VecDeque;
/// Returned when using various methods on a [`Tree`]
#[derive(thiserror::Error, Debug)]
#[allow(missing_docs)]
pub enum Error {
#[error("Pack offsets must only increment. The previous pack offset was {last_pack_offset}, the current one is {pack_offset}")]
InvariantIncreasingPackOffset {
/// The last seen pack offset
last_pack_offset: u64,
/// The invariant violating offset
pack_offset: u64,
},
#[error("The delta at pack offset {delta_pack_offset} could not find its base at {base_pack_offset} - it should have been seen already")]
InvariantBasesBeforeDeltasNeedThem {
/// The delta pack offset whose base we could not find
delta_pack_offset: u64,
/// The base pack offset which was not yet added to the tree
base_pack_offset: u64,
},
}
mod iter;
pub use iter::{Chunk, Node};
///
pub mod traverse;
///
pub mod from_offsets;
/// An item stored within the [`Tree`]
pub struct Item<T> {
/// The offset into the pack file at which the pack entry's data is located.
pub offset: u64,
/// The offset of the next item in the pack file.
pub next_offset: u64,
/// Data to store with each Item, effectively data associated with each entry in a pack.
pub data: T,
children: Vec<usize>,
}
/// A tree that allows one-time iteration over all nodes and their children, consuming it in the process,
/// while being shareable among threads without a lock.
/// It does this by making the guarantee that iteration only happens once.
pub struct Tree<T> {
/// Roots are first, then children.
items: VecDeque<Item<T>>,
roots: usize,
last_index: usize,
}
impl<T> Tree<T> {
/// Instantiate a empty tree capable of storing `num_objects` amounts of items.
pub fn with_capacity(num_objects: usize) -> Result<Self, Error> {
Ok(Tree {
items: VecDeque::with_capacity(num_objects),
roots: 0,
last_index: 0,
})
}
fn assert_is_incrementing(&mut self, offset: u64) -> Result<(), Error> {
if self.items.is_empty() {
return Ok(());
}
let last_offset = self.items[self.last_index].offset;
if offset <= last_offset {
return Err(Error::InvariantIncreasingPackOffset {
last_pack_offset: last_offset,
pack_offset: offset,
});
}
self.items[self.last_index].next_offset = offset;
Ok(())
}
fn set_pack_entries_end(&mut self, pack_entries_end: u64) {
if !self.items.is_empty() {
self.items[self.last_index].next_offset = pack_entries_end;
}
}
/// Add a new root node, one that only has children but is not a child itself, at the given pack `offset` and associate
/// custom `data` with it.
pub fn add_root(&mut self, offset: u64, data: T) -> Result<(), Error> {
self.assert_is_incrementing(offset)?;
self.last_index = 0;
self.items.push_front(Item {
offset,
next_offset: 0,
data,
children: Vec::new(),
});
self.roots += 1;
Ok(())
}
/// Add a child of the item at `base_offset` which itself resides at pack `offset` and associate custom `data` with it.
pub fn add_child(&mut self, base_offset: u64, offset: u64, data: T) -> Result<(), Error> {
self.assert_is_incrementing(offset)?;
let (roots, children) = self.items.as_mut_slices();
assert_eq!(
roots.len(),
self.roots,
"item deque has been resized, maybe we added more nodes than we declared in the constructor?"
);
if let Ok(i) = children.binary_search_by_key(&base_offset, |i| i.offset) {
children[i].children.push(children.len());
} else if let Ok(i) = roots.binary_search_by(|i| base_offset.cmp(&i.offset)) {
roots[i].children.push(children.len());
} else {
return Err(Error::InvariantBasesBeforeDeltasNeedThem {
delta_pack_offset: offset,
base_pack_offset: base_offset,
});
}
self.last_index = self.items.len();
self.items.push_back(Item {
offset,
next_offset: 0,
data,
children: Vec::new(),
});
Ok(())
}
/// Transform this `Tree` into its items.
pub fn into_items(self) -> VecDeque<Item<T>> {
self.items
}
}
#[cfg(test)]
mod tests {
mod tree {
mod from_offsets_in_pack {
use std::sync::atomic::AtomicBool;
use git_odb::pack;
const SMALL_PACK_INDEX: &str = "objects/pack/pack-a2bf8e71d8c18879e499335762dd95119d93d9f1.idx";
const SMALL_PACK: &str = "objects/pack/pack-a2bf8e71d8c18879e499335762dd95119d93d9f1.pack";
const INDEX_V1: &str = "objects/pack/pack-c0438c19fb16422b6bbcce24387b3264416d485b.idx";
const PACK_FOR_INDEX_V1: &str = "objects/pack/pack-c0438c19fb16422b6bbcce24387b3264416d485b.pack";
use git_testtools::fixture_path;
#[test]
fn v1() -> Result<(), Box<dyn std::error::Error>> {
tree(INDEX_V1, PACK_FOR_INDEX_V1)
}
#[test]
fn v2() -> Result<(), Box<dyn std::error::Error>> {
tree(SMALL_PACK_INDEX, SMALL_PACK)
}
fn tree(index_path: &str, pack_path: &str) -> Result<(), Box<dyn std::error::Error>> {
let idx = pack::index::File::at(fixture_path(index_path))?;
crate::cache::delta::Tree::from_offsets_in_pack(
idx.sorted_offsets().into_iter(),
|ofs| *ofs,
fixture_path(pack_path),
git_features::progress::Discard,
&AtomicBool::new(false),
|id| idx.lookup(id).map(|index| idx.pack_offset_at_index(index)),
)?;
Ok(())
}
}
}
struct TreeItem<D> {
_offset: u64,
_data: D,
_children: Vec<usize>,
}
#[test]
fn using_option_as_data_does_not_increase_size_in_memory() {
struct Entry {
pub _id: Option<git_hash::ObjectId>,
pub _crc32: u32,
}
struct TreeItemOption<D> {
_offset: u64,
_data: Option<D>,
_children: Vec<usize>,
}
assert_eq!(
std::mem::size_of::<TreeItem<Entry>>(),
std::mem::size_of::<TreeItemOption<Entry>>(),
"we hope niche filling optimizations kick in for our data structures to not pay for the Option at all"
);
assert_eq!(
std::mem::size_of::<[TreeItemOption<Entry>; 7_500_000]>(),
480_000_000,
"it should be as small as possible"
);
}
#[test]
fn size_of_pack_verify_data_structure() {
use git_odb::pack;
pub struct EntryWithDefault {
_index_entry: pack::index::Entry,
_kind: git_object::Kind,
_object_size: u64,
_decompressed_size: u64,
_compressed_size: u64,
_header_size: u16,
_level: u16,
}
assert_eq!(
std::mem::size_of::<[TreeItem<EntryWithDefault>; 7_500_000]>(),
780_000_000
);
}
}