use std::{cmp::Ordering, fs, path::Path};
use crate::{HashKind, ObjectId, Result, error::invalid};
use super::{PathBloom, bloom::Bloom};
const NO_PARENT: u32 = 0x7000_0000;
const EDGE_LIST: u32 = 0x8000_0000;
pub(super) struct Layer {
data: Vec<u8>,
hash: HashKind,
ids: Chunk,
commits: Chunk,
edges: Option<Chunk>,
bloom: Option<Bloom>,
base_count: usize,
count: usize,
}
pub(super) struct RawCommit {
pub(super) tree: ObjectId,
pub(super) parents: Vec<usize>,
pub(super) time: i64,
}
#[derive(Clone, Copy)]
pub(super) struct Chunk {
pub(super) start: usize,
pub(super) end: usize,
}
impl Layer {
pub(super) fn open(
path: &Path,
hash: HashKind,
base_count: usize,
expected_bases: &[ObjectId],
expected_checksum: Option<ObjectId>,
) -> Result<Option<Self>> {
let data = fs::read(path)?;
if data.get(..4) != Some(b"CGPH") || data.get(4) != Some(&1) {
return Err(invalid("invalid commit-graph header"));
}
let file_hash = match data.get(5) {
Some(1) => HashKind::Sha1,
Some(2) => HashKind::Sha256,
_ => return Err(invalid("unsupported commit-graph hash version")),
};
if file_hash != hash {
return Ok(None);
}
let chunk_count = usize::from(*data.get(6).ok_or_else(|| invalid("truncated graph"))?);
let base_graphs = usize::from(*data.get(7).ok_or_else(|| invalid("truncated graph"))?);
if base_graphs != expected_bases.len() {
return Err(invalid("commit-graph BASE count differs from chain"));
}
let chunks = chunks(&data, chunk_count)?;
validate_bases(&data, &chunks, expected_bases, hash)?;
validate_checksum(&data, expected_checksum, hash)?;
let fanout = required(&chunks, *b"OIDF")?;
if fanout.end - fanout.start != 256 * 4 {
return Err(invalid("invalid commit-graph fanout length"));
}
let count = usize::try_from(read_u32(&data, fanout.end - 4)?)
.map_err(|_| invalid("commit-graph count overflow"))?;
let ids = required(&chunks, *b"OIDL")?;
let commits = required(&chunks, *b"CDAT")?;
let hash_len = hash.bytes();
if ids.end - ids.start != count * hash_len
|| commits.end - commits.start != count * (hash_len + 16)
{
return Err(invalid("commit-graph chunk length mismatch"));
}
let bloom = match (optional(&chunks, *b"BIDX"), optional(&chunks, *b"BDAT")) {
(Some(index), Some(bloom_data)) => Some(Bloom::new(&data, index, bloom_data, count)?),
(None, None) => None,
_ => return Err(invalid("commit-graph Bloom chunks are incomplete")),
};
Ok(Some(Self {
data,
hash,
ids,
commits,
edges: optional(&chunks, *b"EDGE"),
bloom,
base_count,
count,
}))
}
pub(super) const fn count(&self) -> usize {
self.count
}
pub(super) const fn base_count(&self) -> usize {
self.base_count
}
pub(super) fn find_position(&self, id: ObjectId) -> Result<Option<usize>> {
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)
}
pub(super) fn id(&self, position: usize) -> Result<ObjectId> {
if position >= self.count {
return Err(invalid("commit-graph position is out of bounds"));
}
ObjectId::from_bytes(self.id_bytes(position)?)
}
pub(super) fn raw_commit(&self, position: usize) -> Result<RawCommit> {
let hash_len = self.hash.bytes();
let start = self.commits.start + position * (hash_len + 16);
let tree = ObjectId::from_bytes(slice(&self.data, start, hash_len)?)?;
let first = read_u32(&self.data, start + hash_len)?;
let second = read_u32(&self.data, start + hash_len + 4)?;
let mut parents = Vec::new();
push_parent(first, &mut parents)?;
if second & EDGE_LIST != 0 {
self.extra_parents(second & !EDGE_LIST, &mut parents)?;
} else {
push_parent(second, &mut parents)?;
}
let high = read_u32(&self.data, start + hash_len + 8)?;
let low = read_u32(&self.data, start + hash_len + 12)?;
let time = i64::try_from((u64::from(high & 3) << 32) | u64::from(low))
.map_err(|_| invalid("commit time overflow"))?;
Ok(RawCommit {
tree,
parents,
time,
})
}
pub(super) fn changed_path(&self, position: usize, path: &[u8]) -> Result<Option<PathBloom>> {
self.bloom
.as_ref()
.map(|bloom| bloom.query(&self.data, position, path))
.transpose()
}
fn extra_parents(&self, index: u32, output: &mut Vec<usize>) -> Result<()> {
let edges = self
.edges
.ok_or_else(|| invalid("commit-graph has no extra-edge chunk"))?;
let mut position = usize::try_from(index).expect("u32 fits usize");
loop {
let offset = edges.start + position * 4;
if offset >= edges.end {
return Err(invalid("commit-graph edge index is out of bounds"));
}
let value = read_u32(&self.data, offset)?;
push_parent(value & !EDGE_LIST, output)?;
if value & EDGE_LIST != 0 {
return Ok(());
}
position += 1;
}
}
fn id_bytes(&self, position: usize) -> Result<&[u8]> {
slice(
&self.data,
self.ids.start + position * self.hash.bytes(),
self.hash.bytes(),
)
}
}
fn validate_bases(
data: &[u8],
chunks: &[([u8; 4], Chunk)],
bases: &[ObjectId],
hash: HashKind,
) -> Result<()> {
let chunk = optional(chunks, *b"BASE");
if bases.is_empty() {
if chunk.is_some() {
return Err(invalid("commit-graph unexpectedly has a BASE chunk"));
}
return Ok(());
}
let chunk = chunk.ok_or_else(|| invalid("commit-graph BASE chunk is missing"))?;
if chunk.end - chunk.start != bases.len() * hash.bytes() {
return Err(invalid("commit-graph BASE chunk length mismatch"));
}
for (index, base) in bases.iter().enumerate() {
let at = chunk.start + index * hash.bytes();
if slice(data, at, hash.bytes())? != base.as_bytes() {
return Err(invalid("commit-graph BASE hash differs from chain"));
}
}
Ok(())
}
fn validate_checksum(data: &[u8], expected: Option<ObjectId>, hash: HashKind) -> Result<()> {
if let Some(expected) = expected
&& (data.len() < hash.bytes() || &data[data.len() - hash.bytes()..] != expected.as_bytes())
{
return Err(invalid("commit-graph checksum differs from chain name"));
}
Ok(())
}
fn push_parent(position: u32, output: &mut Vec<usize>) -> Result<()> {
if position != NO_PARENT {
output
.push(usize::try_from(position).map_err(|_| invalid("commit-graph parent overflow"))?);
}
Ok(())
}
fn chunks(data: &[u8], count: usize) -> Result<Vec<([u8; 4], Chunk)>> {
let table_end = 8 + (count + 1) * 12;
if data.len() < table_end {
return Err(invalid("truncated commit-graph chunk table"));
}
let mut entries = Vec::with_capacity(count + 1);
for index in 0..=count {
let start = 8 + index * 12;
let id = data[start..start + 4].try_into().expect("four bytes");
let offset = usize::try_from(read_u64(data, start + 4)?)
.map_err(|_| invalid("commit-graph chunk offset overflow"))?;
entries.push((id, offset));
}
if entries.last().map(|entry| entry.0) != Some([0; 4]) {
return Err(invalid("commit-graph 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 commit-graph 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 commit-graph 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 commit-graph 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"),
))
}