use std::{borrow::BorrowMut, collections::VecDeque};
use gix_object::{tree::EntryRef, FindExt, TreeRefIter};
use crate::tree::visit::{ChangeId, Relation};
use crate::tree::{visit::Change, Error, State, TreeInfoTuple, Visit};
#[doc(alias = "diff_tree_to_tree", alias = "git2")]
pub fn diff<StateMut>(
lhs: TreeRefIter<'_>,
rhs: TreeRefIter<'_>,
mut state: StateMut,
objects: impl gix_object::Find,
delegate: &mut impl Visit,
) -> Result<(), Error>
where
StateMut: BorrowMut<State>,
{
let state = state.borrow_mut();
state.clear();
let mut lhs_entries = peekable(lhs);
let mut rhs_entries = peekable(rhs);
let mut relation = None;
let mut pop_path = false;
loop {
if pop_path {
delegate.pop_path_component();
}
pop_path = true;
match (lhs_entries.next(), rhs_entries.next()) {
(None, None) => {
match state.trees.pop_front() {
Some((None, Some(rhs), relation_to_propagate)) => {
delegate.pop_front_tracked_path_and_set_current();
relation = relation_to_propagate;
rhs_entries = peekable(objects.find_tree_iter(&rhs, &mut state.buf2)?);
}
Some((Some(lhs), Some(rhs), relation_to_propagate)) => {
delegate.pop_front_tracked_path_and_set_current();
lhs_entries = peekable(objects.find_tree_iter(&lhs, &mut state.buf1)?);
rhs_entries = peekable(objects.find_tree_iter(&rhs, &mut state.buf2)?);
relation = relation_to_propagate;
}
Some((Some(lhs), None, relation_to_propagate)) => {
delegate.pop_front_tracked_path_and_set_current();
lhs_entries = peekable(objects.find_tree_iter(&lhs, &mut state.buf1)?);
relation = relation_to_propagate;
}
Some((None, None, _)) => unreachable!("BUG: it makes no sense to fill the stack with empties"),
None => return Ok(()),
};
pop_path = false;
}
(Some(lhs), Some(rhs)) => {
use std::cmp::Ordering::*;
let (lhs, rhs) = (lhs?, rhs?);
match compare(&lhs, &rhs) {
Equal => handle_lhs_and_rhs_with_equal_filenames(
lhs,
rhs,
&mut state.trees,
&mut state.change_id,
relation,
delegate,
)?,
Less => catchup_lhs_with_rhs(
&mut lhs_entries,
lhs,
rhs,
&mut state.trees,
&mut state.change_id,
relation,
delegate,
)?,
Greater => catchup_rhs_with_lhs(
&mut rhs_entries,
lhs,
rhs,
&mut state.trees,
&mut state.change_id,
relation,
delegate,
)?,
}
}
(Some(lhs), None) => {
let lhs = lhs?;
delete_entry_schedule_recursion(lhs, &mut state.trees, &mut state.change_id, relation, delegate)?;
}
(None, Some(rhs)) => {
let rhs = rhs?;
add_entry_schedule_recursion(rhs, &mut state.trees, &mut state.change_id, relation, delegate)?;
}
}
}
}
fn compare(a: &EntryRef<'_>, b: &EntryRef<'_>) -> std::cmp::Ordering {
let common = a.filename.len().min(b.filename.len());
a.filename[..common].cmp(&b.filename[..common]).then_with(|| {
let a = a.filename.get(common).or_else(|| a.mode.is_tree().then_some(&b'/'));
let b = b.filename.get(common).or_else(|| b.mode.is_tree().then_some(&b'/'));
a.cmp(&b)
})
}
fn delete_entry_schedule_recursion(
entry: EntryRef<'_>,
queue: &mut VecDeque<TreeInfoTuple>,
change_id: &mut ChangeId,
relation_to_propagate: Option<Relation>,
delegate: &mut impl Visit,
) -> Result<(), Error> {
delegate.push_path_component(entry.filename);
let relation = relation_to_propagate.or_else(|| {
entry.mode.is_tree().then(|| {
*change_id += 1;
Relation::Parent(*change_id)
})
});
let is_cancelled = delegate
.visit(Change::Deletion {
entry_mode: entry.mode,
oid: entry.oid.to_owned(),
relation,
})
.cancelled();
if is_cancelled {
return Err(Error::Cancelled);
}
if entry.mode.is_tree() {
delegate.pop_path_component();
delegate.push_back_tracked_path_component(entry.filename);
queue.push_back((Some(entry.oid.to_owned()), None, to_child(relation)));
}
Ok(())
}
fn add_entry_schedule_recursion(
entry: EntryRef<'_>,
queue: &mut VecDeque<TreeInfoTuple>,
change_id: &mut ChangeId,
relation_to_propagate: Option<Relation>,
delegate: &mut impl Visit,
) -> Result<(), Error> {
delegate.push_path_component(entry.filename);
let relation = relation_to_propagate.or_else(|| {
entry.mode.is_tree().then(|| {
*change_id += 1;
Relation::Parent(*change_id)
})
});
if delegate
.visit(Change::Addition {
entry_mode: entry.mode,
oid: entry.oid.to_owned(),
relation,
})
.cancelled()
{
return Err(Error::Cancelled);
}
if entry.mode.is_tree() {
delegate.pop_path_component();
delegate.push_back_tracked_path_component(entry.filename);
queue.push_back((None, Some(entry.oid.to_owned()), to_child(relation)));
}
Ok(())
}
fn catchup_rhs_with_lhs(
rhs_entries: &mut IteratorType<TreeRefIter<'_>>,
lhs: EntryRef<'_>,
rhs: EntryRef<'_>,
queue: &mut VecDeque<TreeInfoTuple>,
change_id: &mut ChangeId,
relation_to_propagate: Option<Relation>,
delegate: &mut impl Visit,
) -> Result<(), Error> {
use std::cmp::Ordering::*;
add_entry_schedule_recursion(rhs, queue, change_id, relation_to_propagate, delegate)?;
loop {
match rhs_entries.peek() {
Some(Ok(rhs)) => match compare(&lhs, rhs) {
Equal => {
let rhs = rhs_entries.next().transpose()?.expect("the peeked item to be present");
delegate.pop_path_component();
handle_lhs_and_rhs_with_equal_filenames(
lhs,
rhs,
queue,
change_id,
relation_to_propagate,
delegate,
)?;
break;
}
Greater => {
let rhs = rhs_entries.next().transpose()?.expect("the peeked item to be present");
delegate.pop_path_component();
add_entry_schedule_recursion(rhs, queue, change_id, relation_to_propagate, delegate)?;
}
Less => {
delegate.pop_path_component();
delete_entry_schedule_recursion(lhs, queue, change_id, relation_to_propagate, delegate)?;
break;
}
},
Some(Err(err)) => return Err(Error::EntriesDecode(err.to_owned())),
None => {
delegate.pop_path_component();
delete_entry_schedule_recursion(lhs, queue, change_id, relation_to_propagate, delegate)?;
break;
}
}
}
Ok(())
}
fn catchup_lhs_with_rhs(
lhs_entries: &mut IteratorType<TreeRefIter<'_>>,
lhs: EntryRef<'_>,
rhs: EntryRef<'_>,
queue: &mut VecDeque<TreeInfoTuple>,
change_id: &mut ChangeId,
relation_to_propagate: Option<Relation>,
delegate: &mut impl Visit,
) -> Result<(), Error> {
use std::cmp::Ordering::*;
delete_entry_schedule_recursion(lhs, queue, change_id, relation_to_propagate, delegate)?;
loop {
match lhs_entries.peek() {
Some(Ok(lhs)) => match compare(lhs, &rhs) {
Equal => {
let lhs = lhs_entries.next().expect("the peeked item to be present")?;
delegate.pop_path_component();
handle_lhs_and_rhs_with_equal_filenames(
lhs,
rhs,
queue,
change_id,
relation_to_propagate,
delegate,
)?;
break;
}
Less => {
let lhs = lhs_entries.next().expect("the peeked item to be present")?;
delegate.pop_path_component();
delete_entry_schedule_recursion(lhs, queue, change_id, relation_to_propagate, delegate)?;
}
Greater => {
delegate.pop_path_component();
add_entry_schedule_recursion(rhs, queue, change_id, relation_to_propagate, delegate)?;
break;
}
},
Some(Err(err)) => return Err(Error::EntriesDecode(err.to_owned())),
None => {
delegate.pop_path_component();
add_entry_schedule_recursion(rhs, queue, change_id, relation_to_propagate, delegate)?;
break;
}
}
}
Ok(())
}
fn handle_lhs_and_rhs_with_equal_filenames(
lhs: EntryRef<'_>,
rhs: EntryRef<'_>,
queue: &mut VecDeque<TreeInfoTuple>,
change_id: &mut ChangeId,
relation_to_propagate: Option<Relation>,
delegate: &mut impl Visit,
) -> Result<(), Error> {
match (lhs.mode.is_tree(), rhs.mode.is_tree()) {
(true, true) => {
delegate.push_back_tracked_path_component(lhs.filename);
if lhs.oid != rhs.oid
&& delegate
.visit(Change::Modification {
previous_entry_mode: lhs.mode,
previous_oid: lhs.oid.to_owned(),
entry_mode: rhs.mode,
oid: rhs.oid.to_owned(),
})
.cancelled()
{
return Err(Error::Cancelled);
}
queue.push_back((
Some(lhs.oid.to_owned()),
Some(rhs.oid.to_owned()),
relation_to_propagate,
));
}
(_, true) => {
delegate.push_back_tracked_path_component(lhs.filename);
if delegate
.visit(Change::Deletion {
entry_mode: lhs.mode,
oid: lhs.oid.to_owned(),
relation: None,
})
.cancelled()
{
return Err(Error::Cancelled);
};
let relation = relation_to_propagate.or_else(|| {
*change_id += 1;
Some(Relation::Parent(*change_id))
});
if delegate
.visit(Change::Addition {
entry_mode: rhs.mode,
oid: rhs.oid.to_owned(),
relation,
})
.cancelled()
{
return Err(Error::Cancelled);
};
queue.push_back((None, Some(rhs.oid.to_owned()), to_child(relation)));
}
(true, _) => {
delegate.push_back_tracked_path_component(lhs.filename);
let relation = relation_to_propagate.or_else(|| {
*change_id += 1;
Some(Relation::Parent(*change_id))
});
if delegate
.visit(Change::Deletion {
entry_mode: lhs.mode,
oid: lhs.oid.to_owned(),
relation,
})
.cancelled()
{
return Err(Error::Cancelled);
}
if delegate
.visit(Change::Addition {
entry_mode: rhs.mode,
oid: rhs.oid.to_owned(),
relation: None,
})
.cancelled()
{
return Err(Error::Cancelled);
};
queue.push_back((Some(lhs.oid.to_owned()), None, to_child(relation)));
}
(false, false) => {
delegate.push_path_component(lhs.filename);
debug_assert!(lhs.mode.is_no_tree() && lhs.mode.is_no_tree());
if lhs.oid != rhs.oid
&& delegate
.visit(Change::Modification {
previous_entry_mode: lhs.mode,
previous_oid: lhs.oid.to_owned(),
entry_mode: rhs.mode,
oid: rhs.oid.to_owned(),
})
.cancelled()
{
return Err(Error::Cancelled);
}
}
};
Ok(())
}
type IteratorType<I> = std::iter::Peekable<I>;
fn to_child(r: Option<Relation>) -> Option<Relation> {
r.map(|r| match r {
Relation::Parent(id) => Relation::ChildOfParent(id),
Relation::ChildOfParent(id) => Relation::ChildOfParent(id),
})
}
fn peekable<I: Iterator>(iter: I) -> IteratorType<I> {
iter.peekable()
}
#[cfg(test)]
mod tests {
use std::cmp::Ordering;
use gix_object::tree::EntryKind;
use super::*;
#[test]
fn compare_select_samples() {
let null = gix_hash::ObjectId::null(gix_hash::Kind::Sha1);
let actual = compare(
&EntryRef {
mode: EntryKind::Blob.into(),
filename: "plumbing-cli.rs".into(),
oid: &null,
},
&EntryRef {
mode: EntryKind::Tree.into(),
filename: "plumbing".into(),
oid: &null,
},
);
assert_eq!(actual, Ordering::Less);
let actual = compare(
&EntryRef {
mode: EntryKind::Tree.into(),
filename: "plumbing-cli.rs".into(),
oid: &null,
},
&EntryRef {
mode: EntryKind::Blob.into(),
filename: "plumbing".into(),
oid: &null,
},
);
assert_eq!(actual, Ordering::Greater);
}
}