gix_revision/
merge_base.rsbitflags::bitflags! {
#[derive(Debug, Default, Copy, Clone, Eq, PartialEq)]
pub struct Flags: u8 {
const COMMIT1 = 1 << 0;
const COMMIT2 = 1 << 1;
const STALE = 1 << 2;
const RESULT = 1 << 3;
}
}
#[derive(Debug, thiserror::Error)]
#[allow(missing_docs)]
pub enum Error {
#[error("A commit could not be inserted into the graph")]
InsertCommit(#[from] gix_revwalk::graph::get_or_insert_default::Error),
}
pub(crate) mod function {
use super::Error;
use crate::{merge_base::Flags, Graph, PriorityQueue};
use gix_hash::ObjectId;
use gix_revwalk::graph;
use std::cmp::Ordering;
pub fn merge_base(
first: ObjectId,
others: &[ObjectId],
graph: &mut Graph<'_, '_, graph::Commit<Flags>>,
) -> Result<Option<Vec<ObjectId>>, Error> {
let _span = gix_trace::coarse!("gix_revision::merge_base()", ?first, ?others);
if others.is_empty() || others.contains(&first) {
return Ok(Some(vec![first]));
}
graph.clear_commit_data(|f| *f = Flags::empty());
let bases = paint_down_to_common(first, others, graph)?;
let bases = remove_redundant(&bases, graph)?;
Ok((!bases.is_empty()).then_some(bases))
}
fn remove_redundant(
commits: &[(ObjectId, GenThenTime)],
graph: &mut Graph<'_, '_, graph::Commit<Flags>>,
) -> Result<Vec<ObjectId>, Error> {
if commits.is_empty() {
return Ok(Vec::new());
}
graph.clear_commit_data(|f| *f = Flags::empty());
let _span = gix_trace::detail!("gix_revision::remove_redundant()", num_commits = %commits.len());
let sorted_commits = {
let mut v = commits.to_vec();
v.sort_by(|a, b| a.1.cmp(&b.1));
v
};
let mut min_gen_pos = 0;
let mut min_gen = sorted_commits[min_gen_pos].1.generation;
let mut walk_start = Vec::with_capacity(commits.len());
for (id, _) in commits {
let commit = graph.get_mut(id).expect("previously added");
commit.data |= Flags::RESULT;
for parent_id in commit.parents.clone() {
graph.get_or_insert_full_commit(parent_id, |parent| {
if !parent.data.contains(Flags::STALE) {
parent.data |= Flags::STALE;
walk_start.push((parent_id, GenThenTime::from(&*parent)));
}
})?;
}
}
walk_start.sort_by(|a, b| a.0.cmp(&b.0));
walk_start
.iter_mut()
.for_each(|(id, _)| graph.get_mut(id).expect("added previously").data.remove(Flags::STALE));
let mut count_still_independent = commits.len();
let mut stack = Vec::new();
while let Some((commit_id, commit_info)) = walk_start.pop().filter(|_| count_still_independent > 1) {
stack.clear();
graph.get_mut(&commit_id).expect("added").data |= Flags::STALE;
stack.push((commit_id, commit_info));
while let Some((commit_id, commit_info)) = stack.last().copied() {
let commit = graph.get_mut(&commit_id).expect("all commits have been added");
let commit_parents = commit.parents.clone();
if commit.data.contains(Flags::RESULT) {
commit.data.remove(Flags::RESULT);
count_still_independent -= 1;
if count_still_independent <= 1 {
break;
}
if *commit_id == *sorted_commits[min_gen_pos].0 {
while min_gen_pos < commits.len() - 1
&& graph
.get(&sorted_commits[min_gen_pos].0)
.expect("already added")
.data
.contains(Flags::STALE)
{
min_gen_pos += 1;
}
min_gen = sorted_commits[min_gen_pos].1.generation;
}
}
if commit_info.generation < min_gen {
stack.pop();
continue;
}
let previous_len = stack.len();
for parent_id in &commit_parents {
if graph
.get_or_insert_full_commit(*parent_id, |parent| {
if !parent.data.contains(Flags::STALE) {
parent.data |= Flags::STALE;
stack.push((*parent_id, GenThenTime::from(&*parent)));
}
})?
.is_some()
{
break;
}
}
if previous_len == stack.len() {
stack.pop();
}
}
}
Ok(commits
.iter()
.filter_map(|(id, _info)| {
graph
.get(id)
.filter(|commit| !commit.data.contains(Flags::STALE))
.map(|_| *id)
})
.collect())
}
fn paint_down_to_common(
first: ObjectId,
others: &[ObjectId],
graph: &mut Graph<'_, '_, graph::Commit<Flags>>,
) -> Result<Vec<(ObjectId, GenThenTime)>, Error> {
let mut queue = PriorityQueue::<GenThenTime, ObjectId>::new();
graph.get_or_insert_full_commit(first, |commit| {
commit.data |= Flags::COMMIT1;
queue.insert(GenThenTime::from(&*commit), first);
})?;
for other in others {
graph.get_or_insert_full_commit(*other, |commit| {
commit.data |= Flags::COMMIT2;
queue.insert(GenThenTime::from(&*commit), *other);
})?;
}
let mut out = Vec::new();
while queue.iter_unordered().any(|id| {
graph
.get(id)
.map_or(false, |commit| !commit.data.contains(Flags::STALE))
}) {
let (info, commit_id) = queue.pop().expect("we have non-stale");
let commit = graph.get_mut(&commit_id).expect("everything queued is in graph");
let mut flags_without_result = commit.data & (Flags::COMMIT1 | Flags::COMMIT2 | Flags::STALE);
if flags_without_result == (Flags::COMMIT1 | Flags::COMMIT2) {
if !commit.data.contains(Flags::RESULT) {
commit.data |= Flags::RESULT;
out.push((commit_id, info));
}
flags_without_result |= Flags::STALE;
}
for parent_id in commit.parents.clone() {
graph.get_or_insert_full_commit(parent_id, |parent| {
if (parent.data & flags_without_result) != flags_without_result {
parent.data |= flags_without_result;
queue.insert(GenThenTime::from(&*parent), parent_id);
}
})?;
}
}
Ok(out)
}
#[derive(Debug, Clone, Copy)]
struct GenThenTime {
generation: gix_revwalk::graph::Generation,
time: gix_date::SecondsSinceUnixEpoch,
}
impl From<&graph::Commit<Flags>> for GenThenTime {
fn from(commit: &graph::Commit<Flags>) -> Self {
GenThenTime {
generation: commit.generation.unwrap_or(gix_commitgraph::GENERATION_NUMBER_INFINITY),
time: commit.commit_time,
}
}
}
impl Eq for GenThenTime {}
impl PartialEq<Self> for GenThenTime {
fn eq(&self, other: &Self) -> bool {
self.cmp(other).is_eq()
}
}
impl PartialOrd<Self> for GenThenTime {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for GenThenTime {
fn cmp(&self, other: &Self) -> Ordering {
self.generation.cmp(&other.generation).then(self.time.cmp(&other.time))
}
}
}