mod bloom;
mod format;
use std::{fs, path::Path};
use crate::{GitError, HashKind, HistoryOptions, ObjectId, Result, error::invalid};
use format::Layer;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum PathBloom {
DefinitelyNot,
Maybe,
}
pub(crate) struct CommitGraph {
hash: HashKind,
layers: Vec<Layer>,
}
pub(crate) struct GraphCommit {
pub(crate) id: ObjectId,
pub(crate) tree: ObjectId,
pub(crate) parents: Vec<ObjectId>,
pub(crate) time: i64,
}
impl CommitGraph {
pub(crate) fn open(common_dir: &Path, hash: HashKind) -> Result<Option<Self>> {
let info = common_dir.join("objects").join("info");
let monolithic = info.join("commit-graph");
if monolithic.is_file() {
let Some(layer) = Layer::open(&monolithic, hash, 0, &[], None)? else {
return Ok(None);
};
return Ok(Some(Self {
hash,
layers: vec![layer],
}));
}
let directory = info.join("commit-graphs");
let chain = match fs::read_to_string(directory.join("commit-graph-chain")) {
Ok(chain) => chain,
Err(error) if error.kind() == std::io::ErrorKind::NotFound => return Ok(None),
Err(error) => return Err(error.into()),
};
let ids = chain
.lines()
.filter(|line| !line.is_empty())
.map(|line| ObjectId::from_hex_for(line, hash))
.collect::<Result<Vec<_>>>()?;
if ids.is_empty() || ids.len() > 64 {
return Err(invalid("commit-graph chain length is invalid"));
}
let mut layers = Vec::with_capacity(ids.len());
let mut base_count = 0;
for (index, id) in ids.iter().enumerate() {
let path = directory.join(format!("graph-{}.graph", id.to_hex()));
let layer = Layer::open(&path, hash, base_count, &ids[..index], Some(*id))?
.ok_or_else(|| invalid("commit-graph chain hash kind mismatch"))?;
base_count = base_count
.checked_add(layer.count())
.ok_or_else(|| invalid("commit-graph chain count overflow"))?;
layers.push(layer);
}
Ok(Some(Self { hash, layers }))
}
pub(crate) fn find(&self, id: ObjectId) -> Result<Option<GraphCommit>> {
if id.kind() != self.hash {
return Ok(None);
}
for (layer_index, layer) in self.layers.iter().enumerate().rev() {
if let Some(position) = layer.find_position(id)? {
return self.entry(layer_index, position).map(Some);
}
}
Ok(None)
}
pub(crate) fn first_parent_ids(
&self,
start: ObjectId,
options: HistoryOptions,
traversal_limit: usize,
) -> Result<Option<Vec<ObjectId>>> {
let Some(mut position) = self.global_position(start)? else {
return Ok(None);
};
let mut result = Vec::with_capacity(options.max_commits.min(1024));
let mut traversed = 0;
loop {
if result.len() == options.max_commits {
break;
}
if traversed == traversal_limit {
return Err(GitError::LimitExceeded {
resource: "history traversal",
limit: traversal_limit,
});
}
traversed += 1;
let (layer, local) = self.layer_at_global(position)?;
let raw = layer.raw_commit(local)?;
if options.since.is_none_or(|time| raw.time >= time)
&& options.until.is_none_or(|time| raw.time <= time)
{
result.push(layer.id(local)?);
}
let Some(parent) = raw.parents.first() else {
break;
};
position = *parent;
}
Ok(Some(result))
}
pub(crate) const fn layer_count(&self) -> usize {
self.layers.len()
}
pub(crate) fn changed_path(&self, id: ObjectId, path: &[u8]) -> Result<Option<PathBloom>> {
if path.is_empty() || path.contains(&0) {
return Err(invalid("Bloom query path is empty or contains NUL"));
}
for layer in self.layers.iter().rev() {
if let Some(position) = layer.find_position(id)? {
return layer.changed_path(position, path);
}
}
Ok(None)
}
fn entry(&self, layer_index: usize, position: usize) -> Result<GraphCommit> {
let layer = &self.layers[layer_index];
let raw = layer.raw_commit(position)?;
let parents = raw
.parents
.into_iter()
.map(|position| self.id_at_global(position))
.collect::<Result<Vec<_>>>()?;
Ok(GraphCommit {
id: layer.id(position)?,
tree: raw.tree,
parents,
time: raw.time,
})
}
fn id_at_global(&self, position: usize) -> Result<ObjectId> {
let (layer, local) = self.layer_at_global(position)?;
layer.id(local)
}
fn global_position(&self, id: ObjectId) -> Result<Option<usize>> {
if id.kind() != self.hash {
return Ok(None);
}
for layer in self.layers.iter().rev() {
if let Some(position) = layer.find_position(id)? {
return Ok(Some(layer.base_count() + position));
}
}
Ok(None)
}
fn layer_at_global(&self, position: usize) -> Result<(&Layer, usize)> {
let layer = self
.layers
.iter()
.find(|layer| {
position >= layer.base_count()
&& position < layer.base_count().saturating_add(layer.count())
})
.ok_or_else(|| invalid("commit-graph parent is out of chain bounds"))?;
Ok((layer, position - layer.base_count()))
}
}