use crate::format::{Entry, Kind, Target, MAX_FOLDER_DEPTH};
use crate::hash::Root;
use crate::read::{folder_of, record_of};
use crate::store::Store;
use crate::{Error, Result};
use std::cmp::Ordering;
#[derive(Clone, Debug, Eq, PartialEq)]
pub enum Change {
Added { path: String, entry: Entry },
Removed { path: String, entry: Entry },
Changed {
path: String,
old: Entry,
new: Entry,
},
}
impl Change {
pub fn path(&self) -> &str {
match self {
Self::Added { path, .. } | Self::Removed { path, .. } | Self::Changed { path, .. } => {
path
}
}
}
}
pub const DEFAULT_MAX_CHANGES: usize = 1_000_000;
fn too_many(most: usize, found: usize) -> Error {
Error::LimitExceeded {
what: "the changes between two trees",
limit: most as u64,
requested: found as u64,
}
}
pub fn diff(store: &dyn Store, old: &Root, new: &Root) -> Result<Vec<Change>> {
diff_within(store, old, new, DEFAULT_MAX_CHANGES)
}
pub fn diff_within(store: &dyn Store, old: &Root, new: &Root, most: usize) -> Result<Vec<Change>> {
let changes = find_changes(store, old, new, most)?;
if changes.len() > most {
return Err(too_many(most, changes.len()));
}
Ok(changes)
}
fn find_changes(store: &dyn Store, old: &Root, new: &Root, most: usize) -> Result<Vec<Change>> {
let old_top = record_of(store, old)?.top();
let new_top = record_of(store, new)?.top();
if old_top == new_top {
return Ok(Vec::new());
}
if old_top.kind != Kind::Folder || new_top.kind != Kind::Folder {
return Err(Error::InvalidData {
detail: "a tree with a file on top has no entries to compare".to_owned(),
});
}
let mut changes = Vec::new();
let mut pending: Vec<(Target, Target, String, usize)> =
vec![(old_top, new_top, String::new(), 1)];
while let Some((old_folder, new_folder, prefix, depth)) = pending.pop() {
if changes.len() > most {
return Err(too_many(most, changes.len()));
}
if depth > MAX_FOLDER_DEPTH {
return Err(Error::TooDeep {
limit: MAX_FOLDER_DEPTH,
});
}
let old_list = folder_of(store, &old_folder)?;
let new_list = folder_of(store, &new_folder)?;
let (olds, news) = (old_list.entries(), new_list.entries());
let (mut left, mut right) = (0, 0);
let at = |name: &str| format!("{prefix}{name}");
loop {
let order = match (olds.get(left), news.get(right)) {
(Some(old), Some(new)) => old.name().as_bytes().cmp(new.name().as_bytes()),
(Some(_), None) => Ordering::Less,
(None, Some(_)) => Ordering::Greater,
(None, None) => break,
};
match order {
Ordering::Less => {
changes.push(Change::Removed {
path: at(olds[left].name()),
entry: olds[left].clone(),
});
left += 1;
}
Ordering::Greater => {
changes.push(Change::Added {
path: at(news[right].name()),
entry: news[right].clone(),
});
right += 1;
}
Ordering::Equal => {
let (old, new) = (&olds[left], &news[right]);
let path = at(old.name());
if old.kind() != new.kind() {
changes.push(Change::Removed {
path: path.clone(),
entry: old.clone(),
});
changes.push(Change::Added {
path,
entry: new.clone(),
});
} else if old.kind() == Kind::File {
if old != new {
changes.push(Change::Changed {
path,
old: old.clone(),
new: new.clone(),
});
}
} else {
if old.hash() != new.hash() {
pending.push((
old.target(),
new.target(),
format!("{path}/"),
depth + 1,
));
}
if old.extra() != new.extra() {
changes.push(Change::Changed {
path,
old: old.clone(),
new: new.clone(),
});
}
}
left += 1;
right += 1;
}
}
}
}
changes.sort_by(|left, right| left.path().cmp(right.path()));
Ok(changes)
}