use std::collections::{HashMap, HashSet, VecDeque};
use std::path::Path;
use knot_types::{Oid, UnixSeconds};
use super::ewah::Ewah;
use super::history::History;
use super::packs::{Packs, Reader};
use super::reader::{self, Bitmaps};
use super::revindex::{self, Order, OrderTable};
use super::{BitPosition, BitmapEntryOffset, BitmapIndex, Bitset, IndexPosition};
use knot_git::GitError;
use knot_git::MAX_TREE_DEPTH;
use knot_git::Repo;
const OPT_FULL_DAG: u16 = 0x1;
const OPT_LOOKUP_TABLE: u16 = 0x10;
const CAT_COMMIT: u8 = 0;
const CAT_TREE: u8 = 1;
const CAT_BLOB: u8 = 2;
const CAT_TAG: u8 = 3;
const CAT_UNKNOWN: u8 = u8::MAX;
const MAX_XOR_OFFSET_SEARCH: usize = 10;
const MUST_REGION: usize = 100;
const MIN_REGION: usize = 20_000;
const MIN_COMMITS: usize = 100;
const MAX_COMMITS: usize = 5_000;
pub(super) struct TypeBits {
commits: Ewah,
trees: Ewah,
blobs: Ewah,
tags: Ewah,
}
pub(super) struct Selected {
commit_pos: IndexPosition,
xor_offset: u8,
bits: Ewah,
}
pub(super) struct Previous<'a> {
index: &'a BitmapIndex,
maps: Bitmaps<'a>,
to_new: Vec<Option<BitPosition>>,
}
impl<'a> Previous<'a> {
pub(super) fn new<R: Order>(
index: &'a BitmapIndex,
kind: gix::hash::Kind,
rev: &R,
) -> Option<Self> {
let maps = reader::parse(&index.bytes, kind, index.rev.len()).ok()?;
let to_new = (0..index.rev.len())
.map(|bit| {
let oid = index.rev.oid_at_bit(BitPosition::new(bit as u32))?;
Ok(rev.index_of(oid).map(|position| rev.bit_at_index(position)))
})
.collect::<Result<_, GitError>>()
.ok()?;
Some(Self {
index,
maps,
to_new,
})
}
fn categories(&self, num_bits: usize) -> Result<Vec<u8>, GitError> {
let mut categories = vec![CAT_UNKNOWN; num_bits];
let old_len = self.index.rev.len();
for (category, vector) in (CAT_COMMIT..).zip(self.maps.types()?) {
let mut old = Bitset::zeros(old_len);
old.union_ewah(&vector, old_len)?;
old.ones()
.filter_map(|bit| self.to_new[bit.get() as usize])
.for_each(|bit| categories[bit.get() as usize] = category);
}
Ok(categories)
}
fn bits(&self, commit: Oid, num_bits: usize) -> Option<Bitset> {
let old = self.maps.bitmap(self.index.rev.index_of(commit)?).ok()??;
let mut bits = Bitset::zeros(num_bits);
for bit in old.ones() {
bits.set(self.to_new[bit.get() as usize]?);
}
Some(bits)
}
}
pub(crate) fn write(
repo: &Repo,
pack_idx: &Path,
previous: Option<&BitmapIndex>,
) -> Result<bool, GitError> {
let kind = repo.object_format().kind();
let index = gix_pack::index::File::at(pack_idx, kind)
.map_err(|error| GitError::Backend(format!("open pack index: {error}")))?;
let checksum = index.pack_checksum();
let packs = Packs::of_index(pack_idx, kind)?;
let rev = OrderTable::from_index(index);
if rev.len() == 0 {
return Ok(false);
}
let _boost = knot_resource::saturate();
let previous = previous.and_then(|index| Previous::new(index, kind, &rev));
let categories = categories_in_bit_order(&packs, &rev, previous.as_ref())?;
let types = type_index_bits(&categories)?;
let selected = selected_entries(repo, &rev, &packs, &categories, previous.as_ref())?;
if selected.is_empty() {
return Ok(false);
}
let bytes = assemble(kind, &checksum, &types, &selected)?;
revindex::write(&pack_idx.with_extension("rev"), &rev, kind, &checksum)?;
install(&pack_idx.with_extension("bitmap"), &bytes)?;
Ok(true)
}
pub(super) fn type_index_bits(categories: &[u8]) -> Result<TypeBits, GitError> {
let select = |target: u8| {
let mut bits = Bitset::zeros(categories.len());
categories
.iter()
.enumerate()
.filter(|(_, value)| **value == target)
.for_each(|(bit, _)| bits.set(BitPosition::new(bit as u32)));
bits.to_ewah(categories.len())
};
Ok(TypeBits {
commits: select(CAT_COMMIT)?,
trees: select(CAT_TREE)?,
blobs: select(CAT_BLOB)?,
tags: select(CAT_TAG)?,
})
}
pub(super) fn categories_in_bit_order<R: Order + Sync>(
packs: &Packs,
rev: &R,
previous: Option<&Previous>,
) -> Result<Vec<u8>, GitError> {
let known = previous
.and_then(|previous| previous.categories(rev.len()).ok())
.unwrap_or_else(|| vec![CAT_UNKNOWN; rev.len()]);
let mut kinds: Vec<_> = known
.iter()
.map(|category| match *category {
CAT_COMMIT => Some(gix::object::Kind::Commit),
CAT_TREE => Some(gix::object::Kind::Tree),
CAT_BLOB => Some(gix::object::Kind::Blob),
CAT_TAG => Some(gix::object::Kind::Tag),
_ => None,
})
.collect();
packs.kinds(rev, &mut kinds)?;
Ok(kinds
.into_iter()
.map(|kind| match kind {
Some(gix::object::Kind::Commit) => CAT_COMMIT,
Some(gix::object::Kind::Tree) => CAT_TREE,
Some(gix::object::Kind::Blob) => CAT_BLOB,
Some(gix::object::Kind::Tag) => CAT_TAG,
None => CAT_UNKNOWN,
})
.collect())
}
pub(super) fn selected_entries<R: Order + Sync>(
repo: &Repo,
rev: &R,
packs: &Packs,
categories: &[u8],
previous: Option<&Previous>,
) -> Result<Vec<Selected>, GitError> {
let history = History::new(repo);
let repo = &history;
let tips: HashSet<Oid> = repo
.references()?
.into_iter()
.filter_map(|record| repo.peel_to_commit(record.target).ok())
.filter(|commit| rev.index_of(*commit).is_some())
.collect();
let commits: Vec<Oid> = categories
.iter()
.enumerate()
.filter(|(_, category)| **category == CAT_COMMIT)
.map(|(bit, _)| rev.oid_at_bit(BitPosition::new(bit as u32)))
.collect();
let chosen = sample_history(repo, commits, &tips)?;
let mut tips: Vec<(UnixSeconds, IndexPosition, Oid)> = chosen
.into_iter()
.filter_map(|commit| rev.index_of(commit).map(|position| (position, commit)))
.map(|(position, commit)| Ok((repo.commit_time(commit.object_id())?, position, commit)))
.collect::<Result<_, GitError>>()?;
tips.sort_by_key(|(time, position, _)| (*time, *position));
let mut reader = Reader::new(packs, rev);
let mut built: HashMap<Oid, Ewah> = HashMap::new();
let mut recent: VecDeque<Bitset> = VecDeque::new();
let mut entries = Vec::new();
for (_, commit_pos, commit) in tips {
let bits = closure_bits(repo, &mut reader, commit, &built, previous)?;
let full = bits.to_ewah(rev.len())?;
let (xor_offset, write_as) = recent.iter().rev().zip(1u8..).try_fold(
(0, full.clone()),
|best, (base, offset)| {
let candidate = bits.xor(base).to_ewah(rev.len())?;
Ok::<_, GitError>(if candidate.word_count() < best.1.word_count() {
(offset, candidate)
} else {
best
})
},
)?;
entries.push(Selected {
commit_pos,
xor_offset,
bits: write_as,
});
built.insert(commit, full);
recent.push_back(bits);
if recent.len() > MAX_XOR_OFFSET_SEARCH {
recent.pop_front();
}
}
Ok(entries)
}
fn sample_history(
repo: &History<'_>,
commits: Vec<Oid>,
tips: &HashSet<Oid>,
) -> Result<Vec<Oid>, GitError> {
let mut dated: Vec<(UnixSeconds, Oid)> = commits
.into_iter()
.map(|commit| Ok((repo.commit_time(commit.object_id())?, commit)))
.collect::<Result<_, GitError>>()?;
dated.sort_by_key(|(time, _)| std::cmp::Reverse(*time));
if dated.len() < MUST_REGION {
return Ok(dated.into_iter().map(|(_, commit)| commit).collect());
}
let mut chosen = Vec::new();
let mut at = 0;
loop {
let next = next_commit_index(at);
if at + next >= dated.len() {
break;
}
let pick = match next {
0 => dated[at].1,
_ => preferred_in(repo, &dated[at..=at + next], tips)?,
};
chosen.push(pick);
at += next + 1;
}
Ok(chosen)
}
fn preferred_in(
repo: &History<'_>,
window: &[(UnixSeconds, Oid)],
tips: &HashSet<Oid>,
) -> Result<Oid, GitError> {
let mut pick = window[window.len() - 1].1;
for (_, commit) in window {
if tips.contains(commit) {
return Ok(*commit);
}
if repo.commit_tree_and_parents(*commit)?.1.len() > 1 {
pick = *commit;
}
}
Ok(pick)
}
fn next_commit_index(at: usize) -> usize {
if at <= MUST_REGION {
return 0;
}
if at <= MIN_REGION {
return (at - MUST_REGION).min(MIN_COMMITS);
}
(at - MIN_REGION).clamp(MIN_COMMITS, MAX_COMMITS)
}
fn closure_bits<R: Order + Sync>(
repo: &History<'_>,
reader: &mut Reader<'_, R>,
tip: Oid,
built: &HashMap<Oid, Ewah>,
previous: Option<&Previous>,
) -> Result<Bitset, GitError> {
let rev = reader.rev();
let mut bits = Bitset::zeros(rev.len());
let mut commits = vec![tip];
let mut trees = Vec::new();
while let Some(commit) = commits.pop() {
let bit = bit_of(rev, commit)?;
if bits.get(bit) {
continue;
}
if let Some(ancestor) = built.get(&commit) {
bits.union_ewah(ancestor, rev.len())?;
continue;
}
if let Some(old) = previous.and_then(|previous| previous.bits(commit, rev.len())) {
bits.union_with(&old);
continue;
}
bits.set(bit);
let (tree, parents) = repo.commit_tree_and_parents(commit)?;
trees.push(tree);
commits.extend(parents.into_iter().map(Oid::from));
}
let workers = std::thread::available_parallelism()
.map(usize::from)
.unwrap_or(1)
.min(4);
if workers > 1 && trees.len() >= 128 {
parallel::fill(reader, trees, &mut bits, workers)?;
} else {
let mut fill = Fill::new(&mut bits);
for tree in trees {
if let Some(bit) = child_bit(rev, &tree)? {
fill_tree(reader, &mut fill, bit, ROOT_PATH, MAX_TREE_DEPTH)?;
}
}
}
Ok(bits)
}
pub(super) const ROOT_PATH: u64 = 0;
/// a collision only costs work, the bytes are compared.
pub(super) fn path_of(parent: u64, name: &[u8]) -> u64 {
name.iter()
.fold(parent ^ 0xcbf2_9ce4_8422_2325, |hash, byte| {
(hash ^ u64::from(*byte)).wrapping_mul(0x0100_0000_01b3)
})
}
/// `last` only holds trees whose every entry this fill set itself.
/// a tree whose bit was already set can't be recorded, the set may not have its entries.
pub(super) struct Fill<'b> {
bits: &'b mut Bitset,
last: HashMap<u64, Vec<u8>>,
spare: Vec<Vec<u8>>,
}
impl<'b> Fill<'b> {
pub(super) fn new(bits: &'b mut Bitset) -> Self {
Self {
bits,
last: HashMap::new(),
spare: Vec::new(),
}
}
}
pub(super) fn fill_tree<R: Order>(
reader: &mut Reader<'_, R>,
fill: &mut Fill<'_>,
bit: BitPosition,
path: u64,
nesting: usize,
) -> Result<(), GitError> {
if nesting == 0 {
return Err(GitError::DepthExceeded("tree nesting"));
}
if fill.bits.get(bit) {
return Ok(());
}
fill.bits.set(bit);
let rev = reader.rev();
let kind = reader.kind();
let mut tree = fill.spare.pop().unwrap_or_default();
reader.tree(bit, &mut tree)?;
let last = fill.last.remove(&path).unwrap_or_default();
for entry in Changed::new(&tree, &last, kind) {
let entry = entry?;
match entry.mode.kind() {
gix::objs::tree::EntryKind::Tree => {
if let Some(child) = child_bit(rev, entry.oid)? {
let child_path = path_of(path, entry.filename);
fill_tree(reader, fill, child, child_path, nesting - 1)?;
}
}
gix::objs::tree::EntryKind::Commit => {}
_ => fill.bits.set(bit_of(rev, Oid::from(entry.oid.to_owned()))?),
}
}
fill.spare.push(last);
fill.last.insert(path, tree);
Ok(())
}
pub(super) struct Changed<'a> {
tree: &'a [u8],
last: &'a [u8],
kind: gix::hash::Kind,
}
impl<'a> Changed<'a> {
pub(super) fn new(tree: &'a [u8], last: &'a [u8], kind: gix::hash::Kind) -> Self {
Self { tree, last, kind }
}
fn split(&self, bytes: &'a [u8]) -> Option<Result<(&'a [u8], &'a [u8]), GitError>> {
if bytes.is_empty() {
return None;
}
let end = bytes
.iter()
.position(|byte| *byte == 0)
.map(|nul| nul + 1 + self.kind.len_in_bytes())
.filter(|end| *end <= bytes.len());
Some(
end.map(|end| bytes.split_at(end))
.ok_or_else(|| GitError::Decode("a tree entry past the tree's end".to_string())),
)
}
fn parse(&self, raw: &'a [u8]) -> Option<gix::objs::tree::EntryRef<'a>> {
gix::objs::TreeRefIter::from_bytes(raw, self.kind)
.next()?
.ok()
}
}
impl<'a> Iterator for Changed<'a> {
type Item = Result<gix::objs::tree::EntryRef<'a>, GitError>;
fn next(&mut self) -> Option<Self::Item> {
'entries: loop {
let (raw, rest) = match self.split(self.tree)? {
Ok(split) => split,
Err(error) => {
self.tree = &[];
return Some(Err(error));
}
};
self.tree = rest;
if let Some(Ok((old, older))) = self.split(self.last)
&& old == raw
{
self.last = older;
continue;
}
let Some(entry) = self.parse(raw) else {
self.tree = &[];
return Some(Err(GitError::Decode(
"a tree entry that doesn't parse".to_string(),
)));
};
while let Some(Ok((old, older))) = self.split(self.last) {
if old == raw {
self.last = older;
continue 'entries;
}
if !self.parse(old).is_some_and(|old| old < entry) {
break;
}
self.last = older;
}
return Some(Ok(entry));
}
}
}
/// the empty tree isn't in any pack and has no bit
pub(super) fn child_bit(
rev: &impl Order,
child: &gix::hash::oid,
) -> Result<Option<BitPosition>, GitError> {
let child = child.to_owned();
if child == gix::ObjectId::empty_tree(child.kind()) && rev.index_of(Oid::from(child)).is_none()
{
return Ok(None);
}
bit_of(rev, Oid::from(child)).map(Some)
}
fn bit_of(rev: &impl Order, oid: Oid) -> Result<BitPosition, GitError> {
rev.index_of(oid)
.map(|position| rev.bit_at_index(position))
.ok_or_else(|| {
GitError::Backend(format!(
"closure object {oid} is absent from the pack bitmap"
))
})
}
pub(super) fn assemble(
kind: gix::hash::Kind,
checksum: &gix::hash::ObjectId,
types: &TypeBits,
selected: &[Selected],
) -> Result<Vec<u8>, GitError> {
let flags: u16 = OPT_FULL_DAG | OPT_LOOKUP_TABLE;
let mut out = Vec::new();
out.extend_from_slice(b"BITM");
out.extend_from_slice(&1u16.to_be_bytes());
out.extend_from_slice(&flags.to_be_bytes());
out.extend_from_slice(&(selected.len() as u32).to_be_bytes());
out.extend_from_slice(checksum.as_slice());
[&types.commits, &types.trees, &types.blobs, &types.tags]
.into_iter()
.for_each(|bits| bits.write_to(&mut out));
let offsets: Vec<BitmapEntryOffset> = selected
.iter()
.map(|entry| {
let at = BitmapEntryOffset::new(out.len() as u64);
out.extend_from_slice(&entry.commit_pos.get().to_be_bytes());
out.push(entry.xor_offset);
out.push(0);
entry.bits.write_to(&mut out);
at
})
.collect();
let mut rows: Vec<usize> = (0..selected.len()).collect();
rows.sort_by_key(|index| selected[*index].commit_pos);
let mut row_of = vec![0u32; selected.len()];
rows.iter()
.enumerate()
.for_each(|(row, index)| row_of[*index] = row as u32);
rows.iter().for_each(|index| {
let entry = &selected[*index];
let xor_row = match entry.xor_offset {
0 => u32::MAX,
offset => row_of[index - offset as usize],
};
out.extend_from_slice(&entry.commit_pos.get().to_be_bytes());
out.extend_from_slice(&offsets[*index].get().to_be_bytes());
out.extend_from_slice(&xor_row.to_be_bytes());
});
let mut hasher = gix::hash::hasher(kind);
hasher.update(&out);
let digest = hasher
.try_finalize()
.map_err(|error| GitError::Backend(format!("bitmap checksum: {error}")))?;
out.extend_from_slice(digest.as_slice());
Ok(out)
}
pub(super) fn install(path: &Path, bytes: &[u8]) -> Result<(), GitError> {
crate::datastore::write::publish(path, bytes, crate::datastore::Durability::Rename).map_err(
|error| GitError::Maintenance(format!("write bitmap {}: {error:#}", path.display())),
)
}
use super::parallel;