use std::{cmp::Ordering, fs, path::Path};
use crate::{HashKind, ObjectId, Result, bitmap::BitmapIndex, error::invalid};
pub(crate) struct MultiPackIndex {
data: Vec<u8>,
hash: HashKind,
ids: Chunk,
offsets: Chunk,
large: Option<Chunk>,
reverse: Option<Chunk>,
names: Vec<String>,
count: usize,
bitmap: Option<BitmapIndex>,
}
pub(crate) struct MidxLocation<'a> {
pub(crate) pack: &'a str,
pub(crate) offset: u64,
}
#[derive(Clone, Copy)]
struct Chunk {
start: usize,
end: usize,
}
impl MultiPackIndex {
pub(crate) fn open(pack_dir: &Path, hash: HashKind) -> Result<Option<Self>> {
let data = match fs::read(pack_dir.join("multi-pack-index")) {
Ok(data) => data,
Err(error) if error.kind() == std::io::ErrorKind::NotFound => return Ok(None),
Err(error) => return Err(error.into()),
};
if data.get(..4) != Some(b"MIDX") || data.get(4) != Some(&1) {
return Err(invalid("invalid multi-pack-index header"));
}
let file_hash = match data.get(5) {
Some(1) => HashKind::Sha1,
Some(2) => HashKind::Sha256,
_ => return Err(invalid("unsupported multi-pack-index hash version")),
};
if file_hash != hash {
return Ok(None);
}
if data.get(7) != Some(&0) {
return Err(crate::GitError::Unsupported(
"incremental multi-pack-index chains".to_owned(),
));
}
let chunk_count = usize::from(*data.get(6).ok_or_else(|| invalid("truncated MIDX"))?);
let pack_count = usize::try_from(read_u32(&data, 8)?)
.map_err(|_| invalid("MIDX pack count overflow"))?;
let chunks = chunks(&data, 12, chunk_count)?;
let names = parse_names(&data, required(&chunks, *b"PNAM")?, pack_count)?;
let fanout = required(&chunks, *b"OIDF")?;
if fanout.end - fanout.start != 256 * 4 {
return Err(invalid("invalid MIDX fanout length"));
}
let count = usize::try_from(read_u32(&data, fanout.end - 4)?)
.map_err(|_| invalid("MIDX object count overflow"))?;
let ids = required(&chunks, *b"OIDL")?;
let offsets = required(&chunks, *b"OOFF")?;
if ids.end - ids.start != count * hash.bytes() || offsets.end - offsets.start != count * 8 {
return Err(invalid("MIDX chunk length mismatch"));
}
let checksum = ObjectId::from_bytes(
data.get(data.len().saturating_sub(hash.bytes())..)
.ok_or_else(|| invalid("truncated MIDX checksum"))?,
)?;
let bitmap_path = pack_dir.join(format!("multi-pack-index-{}.bitmap", checksum.to_hex()));
let bitmap = BitmapIndex::open(&bitmap_path, hash)?;
Ok(Some(Self {
data,
hash,
ids,
offsets,
large: optional(&chunks, *b"LOFF"),
reverse: optional(&chunks, *b"RIDX"),
names,
count,
bitmap,
}))
}
pub(crate) fn find(&self, id: ObjectId) -> Result<Option<MidxLocation<'_>>> {
if id.kind() != self.hash {
return Ok(None);
}
let mut low = 0;
let mut high = self.count;
while low < high {
let middle = low + (high - low) / 2;
match self.id_bytes(middle)?.cmp(id.as_bytes()) {
Ordering::Less => low = middle + 1,
Ordering::Greater => high = middle,
Ordering::Equal => return self.location(middle).map(Some),
}
}
Ok(None)
}
pub(crate) fn bitmap_reachable(
&self,
id: ObjectId,
max_objects: usize,
) -> Result<Option<Vec<ObjectId>>> {
let Some(bitmap) = &self.bitmap else {
return Ok(None);
};
let Some(position) = self.find_position(id)? else {
return Ok(None);
};
bitmap.reachable(position, &self.bitmap_order()?, max_objects)
}
fn find_position(&self, id: ObjectId) -> Result<Option<usize>> {
if id.kind() != self.hash {
return Ok(None);
}
let mut low = 0;
let mut high = self.count;
while low < high {
let middle = low + (high - low) / 2;
match self.id_bytes(middle)?.cmp(id.as_bytes()) {
Ordering::Less => low = middle + 1,
Ordering::Greater => high = middle,
Ordering::Equal => return Ok(Some(middle)),
}
}
Ok(None)
}
fn bitmap_order(&self) -> Result<Vec<ObjectId>> {
let reverse = self
.reverse
.ok_or_else(|| invalid("MIDX bitmap has no reverse-index chunk"))?;
if reverse.end - reverse.start != self.count * 4 {
return Err(invalid("MIDX reverse-index length mismatch"));
}
(0..self.count)
.map(|position| {
let midx_position =
usize::try_from(read_u32(&self.data, reverse.start + position * 4)?)
.map_err(|_| invalid("MIDX reverse position overflow"))?;
ObjectId::from_bytes(self.id_bytes(midx_position)?)
})
.collect()
}
fn location(&self, position: usize) -> Result<MidxLocation<'_>> {
let start = self.offsets.start + position * 8;
let pack = usize::try_from(read_u32(&self.data, start)?)
.map_err(|_| invalid("MIDX pack index overflow"))?;
let raw = read_u32(&self.data, start + 4)?;
let offset = if raw & 0x8000_0000 == 0 {
u64::from(raw)
} else {
let large = self
.large
.ok_or_else(|| invalid("MIDX large offset chunk is missing"))?;
let slot = usize::try_from(raw & 0x7fff_ffff).expect("u32 fits usize");
let at = large
.start
.checked_add(slot * 8)
.ok_or_else(|| invalid("MIDX large offset overflow"))?;
if at + 8 > large.end {
return Err(invalid("MIDX large offset is out of bounds"));
}
read_u64(&self.data, at)?
};
Ok(MidxLocation {
pack: self
.names
.get(pack)
.ok_or_else(|| invalid("MIDX pack index is out of bounds"))?,
offset,
})
}
fn id_bytes(&self, position: usize) -> Result<&[u8]> {
slice(
&self.data,
self.ids.start + position * self.hash.bytes(),
self.hash.bytes(),
)
}
}
fn parse_names(data: &[u8], chunk: Chunk, count: usize) -> Result<Vec<String>> {
let mut names = Vec::with_capacity(count);
let mut cursor = chunk.start;
while cursor < chunk.end && names.len() < count {
let end = data[cursor..chunk.end]
.iter()
.position(|byte| *byte == 0)
.map(|offset| cursor + offset)
.ok_or_else(|| invalid("unterminated MIDX pack name"))?;
let name = std::str::from_utf8(&data[cursor..end])
.map_err(|_| invalid("MIDX pack name is not UTF-8"))?;
if !name.starts_with("pack-")
|| !Path::new(name)
.extension()
.is_some_and(|extension| extension.eq_ignore_ascii_case("idx"))
{
return Err(invalid("invalid MIDX pack name"));
}
names.push(name.to_owned());
cursor = end + 1;
}
if names.len() != count || !names.windows(2).all(|pair| pair[0] < pair[1]) {
return Err(invalid("MIDX pack names are incomplete or unsorted"));
}
Ok(names)
}
fn chunks(data: &[u8], start: usize, count: usize) -> Result<Vec<([u8; 4], Chunk)>> {
let table_end = start + (count + 1) * 12;
if data.len() < table_end {
return Err(invalid("truncated MIDX chunk table"));
}
let mut entries = Vec::with_capacity(count + 1);
for index in 0..=count {
let at = start + index * 12;
let id = data[at..at + 4].try_into().expect("four bytes");
let offset = usize::try_from(read_u64(data, at + 4)?)
.map_err(|_| invalid("MIDX chunk offset overflow"))?;
entries.push((id, offset));
}
if entries.last().map(|entry| entry.0) != Some([0; 4]) {
return Err(invalid("MIDX chunk table has no terminator"));
}
entries
.windows(2)
.map(|pair| {
if pair[0].1 > pair[1].1 || pair[1].1 > data.len() {
return Err(invalid("invalid MIDX chunk bounds"));
}
Ok((
pair[0].0,
Chunk {
start: pair[0].1,
end: pair[1].1,
},
))
})
.collect()
}
fn required(chunks: &[([u8; 4], Chunk)], id: [u8; 4]) -> Result<Chunk> {
optional(chunks, id).ok_or_else(|| invalid("required MIDX chunk is missing"))
}
fn optional(chunks: &[([u8; 4], Chunk)], id: [u8; 4]) -> Option<Chunk> {
chunks
.iter()
.find_map(|entry| (entry.0 == id).then_some(entry.1))
}
fn slice(input: &[u8], start: usize, length: usize) -> Result<&[u8]> {
input
.get(start..start + length)
.ok_or_else(|| invalid("truncated MIDX data"))
}
fn read_u32(input: &[u8], offset: usize) -> Result<u32> {
Ok(u32::from_be_bytes(
slice(input, offset, 4)?.try_into().expect("four bytes"),
))
}
fn read_u64(input: &[u8], offset: usize) -> Result<u64> {
Ok(u64::from_be_bytes(
slice(input, offset, 8)?.try_into().expect("eight bytes"),
))
}