use std::collections::hash_map::RandomState;
use std::hash::BuildHasher;
use std::path::Path;
use hashbrown::HashTable;
use knot_types::Oid;
use super::{BitPosition, IndexPosition};
use knot_git::GitError;
const RIDX_SIGNATURE: u32 = 0x5249_4458;
const RIDX_HEADER_LEN: usize = 12;
pub(crate) trait Order {
fn len(&self) -> usize;
fn index_of(&self, oid: Oid) -> Option<IndexPosition>;
fn bit_at_index(&self, position: IndexPosition) -> BitPosition;
fn oid_at_bit(&self, bit: BitPosition) -> Oid;
fn placement(&self, position: IndexPosition) -> (u32, u64);
fn placement_at_bit(&self, bit: BitPosition) -> (u32, u64);
}
pub(crate) struct OrderTable {
positions: Positions,
bit_to_index: Vec<IndexPosition>,
index_to_bit: Vec<BitPosition>,
by_oid: HashTable<IndexPosition>,
hasher: RandomState,
}
impl OrderTable {
fn build(positions: Positions) -> Self {
let count = positions.len() as u32;
let placement: Vec<_> = (0..count)
.map(|index| positions.placement(IndexPosition::new(index)))
.collect();
let mut order: Vec<u32> = (0..count).collect();
order.sort_by_key(|position| placement[*position as usize]);
drop(placement);
let bit_to_index: Vec<_> = order.into_iter().map(IndexPosition::new).collect();
let mut index_to_bit = vec![BitPosition::new(0); count as usize];
for (bit, position) in bit_to_index.iter().enumerate() {
index_to_bit[position.get() as usize] = BitPosition::new(bit as u32);
}
let hasher = RandomState::new();
let mut by_oid = HashTable::with_capacity(count as usize);
let hash = |position: IndexPosition| hasher.hash_one(positions.oid_ref(position));
for index in 0..count {
let position = IndexPosition::new(index);
by_oid.insert_unique(hash(position), position, |position| hash(*position));
}
Self {
positions,
bit_to_index,
index_to_bit,
by_oid,
hasher,
}
}
pub(crate) fn from_index(index: gix_pack::index::File) -> Self {
Self::build(Positions::Pack(index))
}
pub(crate) fn from_file(file: gix_pack::multi_index::File) -> Self {
Self::build(Positions::Midx(file))
}
pub(crate) fn index_positions_in_bit_order(&self) -> &[IndexPosition] {
&self.bit_to_index
}
}
impl Order for OrderTable {
fn len(&self) -> usize {
self.positions.len()
}
fn index_of(&self, oid: Oid) -> Option<IndexPosition> {
let oid = oid.object_id();
let oid: &gix::hash::oid = oid.as_ref();
self.by_oid
.find(self.hasher.hash_one(oid), |position| {
self.positions.oid_ref(*position) == oid
})
.copied()
}
fn bit_at_index(&self, position: IndexPosition) -> BitPosition {
self.index_to_bit[position.get() as usize]
}
fn oid_at_bit(&self, bit: BitPosition) -> Oid {
self.positions.oid_at(self.bit_to_index[bit.get() as usize])
}
fn placement(&self, position: IndexPosition) -> (u32, u64) {
self.positions.placement(position)
}
fn placement_at_bit(&self, bit: BitPosition) -> (u32, u64) {
self.placement(self.bit_to_index[bit.get() as usize])
}
}
pub(crate) fn write(
path: &Path,
order: &OrderTable,
kind: gix::hash::Kind,
checksum: &gix::hash::ObjectId,
) -> Result<(), GitError> {
let mut out = Vec::new();
out.extend_from_slice(&RIDX_SIGNATURE.to_be_bytes());
out.extend_from_slice(&1u32.to_be_bytes());
out.extend_from_slice(&hash_id(kind).to_be_bytes());
order
.index_positions_in_bit_order()
.iter()
.for_each(|position| out.extend_from_slice(&position.get().to_be_bytes()));
out.extend_from_slice(checksum.as_slice());
let mut hasher = gix::hash::hasher(kind);
hasher.update(&out);
let digest = hasher
.try_finalize()
.map_err(|error| GitError::Backend(format!("revindex checksum: {error}")))?;
out.extend_from_slice(digest.as_slice());
super::writer::install(path, &out)
}
fn hash_id(kind: gix::hash::Kind) -> u32 {
crate::midx_rev::hash_id(knot_types::ObjectFormat::from_kind(kind))
}
pub(crate) enum Positions {
Pack(gix_pack::index::File),
Midx(gix_pack::multi_index::File),
}
impl Positions {
fn len(&self) -> usize {
match self {
Positions::Pack(index) => index.num_objects() as usize,
Positions::Midx(file) => file.num_objects() as usize,
}
}
fn lookup(&self, oid: Oid) -> Option<IndexPosition> {
match self {
Positions::Pack(index) => index.lookup(oid.object_id()),
Positions::Midx(file) => file.lookup(oid.object_id()),
}
.map(IndexPosition::new)
}
fn oid_at(&self, position: IndexPosition) -> Oid {
Oid::from(self.oid_ref(position).to_owned())
}
fn oid_ref(&self, position: IndexPosition) -> &gix::hash::oid {
match self {
Positions::Pack(index) => index.oid_at_index(position.get()),
Positions::Midx(file) => file.oid_at_index(position.get()),
}
}
fn placement(&self, position: IndexPosition) -> (u32, u64) {
match self {
Positions::Pack(index) => (0, index.pack_offset_at_index(position.get())),
Positions::Midx(file) => file.pack_id_and_pack_offset_at_index(position.get()),
}
}
}
pub(crate) struct RevIndex {
positions: Positions,
map: memmap2::Mmap,
}
impl RevIndex {
pub(crate) fn open(
path: &Path,
positions: Positions,
kind: gix::hash::Kind,
checksum: &gix::hash::ObjectId,
) -> Result<Option<Self>, GitError> {
let Ok(file) = std::fs::File::open(path) else {
return Ok(None);
};
let map = unsafe { memmap2::Mmap::map(&file) }
.map_err(|error| GitError::Backend(format!("map revindex: {error}")))?;
let raw = kind.len_in_bytes();
let entries_end = RIDX_HEADER_LEN + 4 * positions.len();
let valid = map.len() == entries_end + 2 * raw
&& map[..4] == RIDX_SIGNATURE.to_be_bytes()
&& map[4..8] == 1u32.to_be_bytes()
&& map[8..12] == hash_id(kind).to_be_bytes()
&& &map[entries_end..entries_end + raw] == checksum.as_slice();
if !valid {
return Err(GitError::Backend(format!(
"revindex {} doesn't match its pack",
path.display()
)));
}
Ok(Some(Self { positions, map }))
}
pub(crate) fn len(&self) -> usize {
self.positions.len()
}
fn index_at_bit(&self, bit: BitPosition) -> Result<IndexPosition, GitError> {
let at = RIDX_HEADER_LEN + 4 * bit.get() as usize;
let position = u32::from_be_bytes(self.map[at..at + 4].try_into().unwrap());
if position as usize >= self.len() {
return Err(GitError::Backend("revindex entry out of range".to_string()));
}
Ok(IndexPosition::new(position))
}
pub(crate) fn index_of(&self, oid: Oid) -> Option<IndexPosition> {
self.positions.lookup(oid)
}
pub(crate) fn oid_at_bit(&self, bit: BitPosition) -> Result<Oid, GitError> {
Ok(self.positions.oid_at(self.index_at_bit(bit)?))
}
pub(crate) fn locate(
&self,
oid: Oid,
) -> Result<Option<(IndexPosition, BitPosition)>, GitError> {
let Some(position) = self.positions.lookup(oid) else {
return Ok(None);
};
let target = self.positions.placement(position);
let (mut low, mut high) = (0u32, self.len() as u32);
while low < high {
let mid = low + (high - low) / 2;
let at = self
.positions
.placement(self.index_at_bit(BitPosition::new(mid))?);
match at.cmp(&target) {
std::cmp::Ordering::Less => low = mid + 1,
std::cmp::Ordering::Greater => high = mid,
std::cmp::Ordering::Equal => return Ok(Some((position, BitPosition::new(mid)))),
}
}
Err(GitError::Backend(format!(
"{oid} is missing from the revindex"
)))
}
}