use std::collections::HashSet;
use knot_types::Oid;
use super::bitset::Bitset;
use super::history::{History, MAX_TAG_DEPTH, Peeled};
use super::reader::Bitmaps;
use super::revindex::RevIndex;
use super::{BitPosition, IndexPosition};
use knot_git::GitError;
use knot_git::MAX_TREE_DEPTH;
use knot_git::Repo;
pub(super) struct Resolved {
pub(super) in_bitmap: Vec<Oid>,
pub(super) outside: Vec<Oid>,
}
pub(super) struct Reach {
bits: Bitset,
outside: HashSet<Oid>,
}
impl Reach {
pub(super) fn has(&self, bit: Option<BitPosition>, oid: Oid) -> bool {
match bit {
Some(bit) => self.bits.get(bit),
None => self.outside.contains(&oid),
}
}
pub(super) fn minus(self, haves: &Reach, rev: &RevIndex) -> Result<Resolved, GitError> {
let in_bitmap = self
.bits
.difference_indices(&haves.bits)
.map(|bit| rev.oid_at_bit(bit))
.collect::<Result<_, _>>()?;
Ok(Resolved {
in_bitmap,
outside: self.outside.into_iter().collect(),
})
}
}
struct Walk<'a> {
repo: &'a History<'a>,
rev: &'a RevIndex,
maps: &'a Bitmaps<'a>,
seen: Option<&'a Reach>,
out: Reach,
}
pub(super) fn reach(
repo: &Repo,
rev: &RevIndex,
maps: &Bitmaps<'_>,
roots: &[Oid],
seen: Option<&Reach>,
) -> Result<Reach, GitError> {
let history = History::new(repo);
let mut walk = Walk {
repo: &history,
rev,
maps,
seen,
out: Reach {
bits: Bitset::zeros(rev.len()),
outside: HashSet::new(),
},
};
let mut commits = Vec::new();
let mut trees = Vec::new();
roots.iter().try_for_each(|root| {
let mut tags = Vec::new();
let peeled = history.peel(root.object_id(), &mut tags, MAX_TAG_DEPTH)?;
tags.into_iter()
.try_for_each(|tag| walk.mark(tag).map(drop))?;
match peeled {
Peeled::Commit(commit) => commits.push(Oid::from(commit)),
Peeled::Direct(direct) => match object_kind(repo, direct)? {
gix::object::Kind::Tree => trees.push(direct),
_ => {
walk.mark(Oid::from(direct))?;
}
},
}
Ok::<_, GitError>(())
})?;
while let Some(commit) = commits.pop() {
let located = rev.locate(commit)?;
if walk.marked(located.map(|(_, bit)| bit), commit) {
continue;
}
if let Some((position, _)) = located
&& walk.union_bitmap(position)?
{
continue;
}
walk.set(located.map(|(_, bit)| bit), commit);
let (tree, parents) = history.commit_tree_and_parents(commit)?;
trees.push(tree);
commits.extend(parents.into_iter().map(Oid::from));
}
trees
.into_iter()
.try_for_each(|tree| walk.fill_tree(tree, MAX_TREE_DEPTH))?;
Ok(walk.out)
}
impl Walk<'_> {
fn marked(&self, bit: Option<BitPosition>, oid: Oid) -> bool {
self.out.has(bit, oid) || self.seen.is_some_and(|seen| seen.has(bit, oid))
}
fn set(&mut self, bit: Option<BitPosition>, oid: Oid) {
match bit {
Some(bit) => self.out.bits.set(bit),
None => {
self.out.outside.insert(oid);
}
}
}
fn mark(&mut self, oid: Oid) -> Result<bool, GitError> {
let bit = self.rev.locate(oid)?.map(|(_, bit)| bit);
if self.marked(bit, oid) {
return Ok(false);
}
self.set(bit, oid);
Ok(true)
}
fn union_bitmap(&mut self, position: IndexPosition) -> Result<bool, GitError> {
let Some(bits) = self.maps.bitmap(position)? else {
return Ok(false);
};
self.out.bits.union_with(&bits);
Ok(true)
}
fn fill_tree(&mut self, tree: gix::ObjectId, nesting: usize) -> Result<(), GitError> {
if nesting == 0 {
return Err(GitError::DepthExceeded("tree nesting"));
}
let oid = Oid::from(tree);
let bit = self.rev.locate(oid)?.map(|(_, bit)| bit);
if bit.is_none() && tree == gix::ObjectId::empty_tree(tree.kind()) {
return Ok(());
}
if self.marked(bit, oid) {
return Ok(());
}
self.set(bit, oid);
let object = self
.repo
.git()
.find_tree(tree)
.map_err(|error| GitError::Corrupt {
oid,
message: error.to_string(),
})?;
object.iter().try_for_each(|entry| {
let entry = entry.map_err(|error| GitError::Decode(error.to_string()))?;
match entry.mode().kind() {
gix::objs::tree::EntryKind::Tree => self.fill_tree(entry.object_id(), nesting - 1),
gix::objs::tree::EntryKind::Commit => Ok(()),
_ => self.mark(Oid::from(entry.object_id())).map(drop),
}
})
}
}
fn object_kind(repo: &Repo, oid: gix::ObjectId) -> Result<gix::object::Kind, GitError> {
repo.git()
.find_header(oid)
.map(|header| header.kind())
.map_err(|error| GitError::Corrupt {
oid: Oid::from(oid),
message: error.to_string(),
})
}