use std::path::{Path, PathBuf};
use knot_git::{GitError, Haves, Repo, Wants};
use knot_types::Oid;
mod bitset;
mod count;
mod ewah;
#[cfg(test)]
mod fuzz;
mod history;
mod midx;
mod packs;
mod parallel;
mod reach;
mod reader;
mod revindex;
mod writer;
use bitset::Bitset;
use revindex::{Positions, RevIndex};
knot_types::scalar_newtype! {
pub(crate) struct BitPosition(u32);
pub(crate) struct IndexPosition(u32) => ordered;
pub(crate) struct BitmapEntryOffset(u64);
}
pub fn write_bitmap(
repo: &Repo,
pack_idx: &Path,
previous: Option<&BitmapIndex>,
) -> Result<bool, GitError> {
writer::write(repo, pack_idx, previous)
}
pub fn write_midx_bitmap(repo: &Repo, previous: Option<&BitmapIndex>) -> Result<bool, GitError> {
midx::write(repo, previous)
}
pub fn open_bitmap_index(repo: &Repo) -> Result<Option<BitmapIndex>, GitError> {
match single_pack(repo)? {
Some(loaded) => Ok(Some(loaded)),
None => midx::open(repo),
}
}
pub fn reachable_via_bitmap(
repo: &Repo,
wants: Wants<'_>,
haves: Haves<'_>,
) -> Result<Option<Vec<Oid>>, GitError> {
let Some(loaded) = open_bitmap_index(repo)? else {
return Ok(None);
};
Ok(loaded.resolve(repo, wants, haves)?.map(|mut resolved| {
resolved.in_bitmap.extend(resolved.outside);
resolved.in_bitmap
}))
}
pub fn unreachable_via_bitmap(
repo: &Repo,
roots: &[Oid],
candidates: &[Oid],
) -> Result<Option<Vec<Oid>>, GitError> {
let Some(loaded) = open_bitmap_index(repo)? else {
return Ok(None);
};
let maps = reader::parse(&loaded.bytes, repo.object_format().kind(), loaded.rev.len())?;
let reached = reach::reach(repo, &loaded.rev, &maps, roots, None)?;
let mut unreachable = Vec::new();
for &candidate in candidates {
let bit = loaded.rev.locate(candidate)?.map(|(_, bit)| bit);
if !reached.has(bit, candidate) {
unreachable.push(candidate);
}
}
Ok(Some(unreachable))
}
pub fn count_commits(
repo: &Repo,
tip: Oid,
deadline: std::time::Instant,
) -> Result<Option<u64>, GitError> {
let Some(loaded) = open_bitmap_index(repo)? else {
return count::count(repo, tip, deadline, None);
};
let maps = reader::parse(&loaded.bytes, repo.object_format().kind(), loaded.rev.len())?;
let indexed = count::Indexed {
rev: &loaded.rev,
maps: &maps,
};
count::count(repo, tip, deadline, Some(indexed))
}
pub struct BitmapIndex {
rev: RevIndex,
bytes: memmap2::Mmap,
}
impl BitmapIndex {
fn resolve(
&self,
repo: &Repo,
wants: Wants<'_>,
haves: Haves<'_>,
) -> Result<Option<reach::Resolved>, GitError> {
if !wants.as_slice().iter().all(|want| repo.contains(*want)) {
return Ok(None);
}
let maps = reader::parse(&self.bytes, repo.object_format().kind(), self.rev.len())?;
let haves: Vec<Oid> = haves
.as_slice()
.iter()
.copied()
.filter(|have| repo.contains(*have))
.collect();
let have = reach::reach(repo, &self.rev, &maps, &haves, None)?;
let want = reach::reach(repo, &self.rev, &maps, wants.as_slice(), Some(&have))?;
want.minus(&have, &self.rev).map(Some)
}
}
fn single_pack(repo: &Repo) -> Result<Option<BitmapIndex>, GitError> {
let kind = repo.object_format().kind();
let Some(pack_idx) = bitmapped_pack(&repo.objects_dir()) else {
return Ok(None);
};
let Some(bytes) = map_file(&pack_idx.with_extension("bitmap")) else {
return Ok(None);
};
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();
Ok(RevIndex::open(
&pack_idx.with_extension("rev"),
Positions::Pack(index),
kind,
&checksum,
)?
.map(|rev| BitmapIndex { rev, bytes }))
}
fn map_file(path: &Path) -> Option<memmap2::Mmap> {
let file = std::fs::File::open(path).ok()?;
unsafe { memmap2::Mmap::map(&file) }.ok()
}
pub fn verbatim_clone_pack(
repo: &Repo,
wants: Wants<'_>,
) -> Result<Option<std::fs::File>, GitError> {
let Some(pack_idx) = bitmapped_pack(&repo.objects_dir()) else {
return Ok(None);
};
let Some(loaded) = single_pack(repo)? else {
return Ok(None);
};
let Some(resolved) = loaded.resolve(repo, wants, Haves::new(&[]))? else {
return Ok(None);
};
if !resolved.outside.is_empty() || resolved.in_bitmap.len() != loaded.rev.len() {
return Ok(None);
}
Ok(std::fs::File::open(pack_idx.with_extension("pack")).ok())
}
fn bitmapped_pack(objects_dir: &Path) -> Option<PathBuf> {
let pack_dir = objects_dir.join("pack");
let mut idxs: Vec<PathBuf> = std::fs::read_dir(&pack_dir)
.ok()?
.filter_map(Result::ok)
.map(|entry| entry.path())
.filter(|path| path.extension().is_some_and(|ext| ext == "idx"))
.collect();
idxs.sort();
idxs.into_iter()
.find(|idx| idx.with_extension("bitmap").exists())
}
#[cfg(test)]
mod tests {
use super::*;
use crate::midx_rev::tests::{git, push};
use std::collections::BTreeSet;
/// the history has to be long enough for git to xor bitmap entries together.
#[test]
fn git_bitmaps_work_with_and_without_optional_extensions() {
for format in ["sha1", "sha256"] {
for midx in [false, true] {
for lookup in [false, true] {
for cache in [false, true] {
reach_through_gits_bitmap(format, midx, lookup, cache);
}
}
}
}
}
fn reach_through_gits_bitmap(format: &str, midx: bool, lookup: bool, cache: bool) {
let dir = tempfile::tempdir().unwrap();
let path = dir.path();
let object_format = format!("--object-format={format}");
git(
path,
&["init", "--bare", "-q", "-b", "main", &object_format],
"",
);
let history: String = (0..400)
.map(|n| {
let from = if n == 0 {
String::new()
} else {
format!("from :{n}\n")
};
format!(
"commit refs/heads/main\nmark :{}\ncommitter a <a@a> {} +0000\n\
data 0\n{from}M 100644 inline f{}\ndata <<END\n{n}\nEND\n",
n + 1,
1_000_000_000 + n,
n % 16
)
})
.collect();
git(path, &["fast-import", "--quiet"], &history);
for (key, value) in [
("pack.writeBitmapLookupTable", lookup),
("pack.writeBitmapHashCache", cache),
("pack.writeReverseIndex", true),
] {
git(path, &["config", key, &value.to_string()], "");
}
git(path, &["repack", if midx { "-adq" } else { "-adbq" }], "");
let repo = Repo::open(path).unwrap();
if midx {
git(path, &["multi-pack-index", "write", "--bitmap"], "");
crate::midx_rev::complete(&repo.objects_dir().join("pack"), repo.object_format())
.unwrap();
}
for tip in git(path, &["rev-list", "--all"], "").lines().step_by(23) {
let oid = Oid::from(gix::ObjectId::from_hex(tip.as_bytes()).unwrap());
let reached: BTreeSet<_> =
reachable_via_bitmap(&repo, Wants::new(&[oid]), Haves::new(&[]))
.unwrap()
.unwrap()
.into_iter()
.map(|oid| oid.to_string())
.collect();
let walked: BTreeSet<_> = git(
path,
&["rev-list", "--objects", "--no-object-names", tip],
"",
)
.lines()
.map(str::to_owned)
.collect();
assert_eq!(
reached, walked,
"{format} midx={midx} lookup={lookup} cache={cache} tip={tip}"
);
}
}
#[test]
fn owned_bitmaps_match_upstream_and_gits_walk() {
for format in ["sha1", "sha256"] {
let dir = tempfile::tempdir().unwrap();
git(
dir.path(),
&[
"init",
"--bare",
"-q",
"-b",
"main",
&format!("--object-format={format}"),
],
"",
);
for name in ["a", "b", "c", "d"] {
push(dir.path(), "refs/heads/main", name);
}
git(dir.path(), &["multi-pack-index", "write"], "");
let repo = Repo::open(dir.path()).unwrap();
assert!(knot_git::write_midx_bitmap(&repo, None).unwrap());
let path = std::fs::read_dir(repo.objects_dir().join("pack"))
.unwrap()
.map(|entry| entry.unwrap().path())
.find(|path| path.extension().is_some_and(|ext| ext == "bitmap"))
.unwrap();
let upstream = std::fs::read(&path).unwrap();
assert!(write_midx_bitmap(&repo, None).unwrap());
assert_eq!(std::fs::read(&path).unwrap(), upstream, "{format}");
let tip = Oid::from(
gix::ObjectId::from_hex(git(dir.path(), &["rev-parse", "main"], "").as_bytes())
.unwrap(),
);
let reached: BTreeSet<_> =
reachable_via_bitmap(&repo, Wants::new(&[tip]), Haves::new(&[]))
.unwrap()
.unwrap()
.into_iter()
.map(|oid| oid.to_string())
.collect();
let walked: BTreeSet<_> = git(
dir.path(),
&["rev-list", "--objects", "--no-object-names", "main"],
"",
)
.lines()
.map(str::to_owned)
.collect();
assert_eq!(reached, walked, "{format}");
let previous = open_bitmap_index(&repo).unwrap().unwrap();
assert!(write_midx_bitmap(&repo, Some(&previous)).unwrap());
assert_eq!(
std::fs::read(path).unwrap(),
upstream,
"incremental {format}"
);
}
}
}