use super::path_node::PathNode;
use crate::algorithm::change::Change;
use crate::algorithm::diff_algorithm_listener::DiffAlgorithmListener;
use crate::algorithm::DiffAlgorithm;
use crate::patch::delta_type::DeltaType;
#[derive(Default)]
pub struct DiffWorkspace {
arena: Vec<PathNode>,
diagonal: Vec<Option<usize>>,
}
impl DiffWorkspace {
pub fn new() -> Self {
Self::default()
}
pub fn clear(&mut self) {
self.arena.clear();
self.diagonal.fill(None);
}
}
pub struct MyersDiff<T> {
equalizer: Option<Box<dyn Fn(&T, &T) -> bool>>,
}
impl<T> Default for MyersDiff<T> {
fn default() -> Self {
Self { equalizer: None }
}
}
impl<T> MyersDiff<T> {
pub fn new() -> Self {
Self::default()
}
pub fn with_equalizer<F>(equalizer: F) -> Self
where
F: Fn(&T, &T) -> bool + 'static,
{
Self {
equalizer: Some(Box::new(equalizer)),
}
}
}
impl<T: PartialEq> DiffAlgorithm<T> for MyersDiff<T> {
fn diff_with_listener(
&self,
source: &[T],
target: &[T],
listener: &mut dyn DiffAlgorithmListener,
) -> Vec<Change> {
if let Some(ref eq) = self.equalizer {
compute_diff_with_listener(source, target, eq, listener)
} else {
compute_diff_with_listener(source, target, |a, b| a == b, listener)
}
}
}
pub fn compute_diff<T: PartialEq>(source: &[T], target: &[T]) -> Vec<Change> {
compute_diff_with(source, target, |a, b| a == b)
}
pub fn compute_diff_with<T, F>(source: &[T], target: &[T], equalizer: F) -> Vec<Change>
where
F: Fn(&T, &T) -> bool,
{
let mut ws = DiffWorkspace::new();
compute_diff_with_workspace_and_listener(source, target, equalizer, &mut ws, None)
}
pub fn compute_diff_with_listener<T, F>(
source: &[T],
target: &[T],
equalizer: F,
listener: &mut dyn DiffAlgorithmListener,
) -> Vec<Change>
where
F: Fn(&T, &T) -> bool,
{
let mut ws = DiffWorkspace::new();
compute_diff_with_workspace_and_listener(source, target, equalizer, &mut ws, Some(listener))
}
pub fn compute_diff_with_workspace<T, F>(
source: &[T],
target: &[T],
equalizer: F,
ws: &mut DiffWorkspace,
) -> Vec<Change>
where
F: Fn(&T, &T) -> bool,
{
compute_diff_with_workspace_and_listener(source, target, equalizer, ws, None)
}
pub fn compute_diff_with_workspace_and_listener<T, F>(
source: &[T],
target: &[T],
equalizer: F,
ws: &mut DiffWorkspace,
mut listener: Option<&mut dyn DiffAlgorithmListener>,
) -> Vec<Change>
where
F: Fn(&T, &T) -> bool,
{
if let Some(ref mut l) = listener {
l.diff_start();
}
if source.is_empty() && target.is_empty() {
if let Some(ref mut l) = listener {
l.diff_end();
}
return Vec::new();
}
ws.clear();
let head_idx = build_path(source, target, &equalizer, ws, listener.as_deref_mut());
let result = if let Some(idx) = head_idx {
build_revision(&ws.arena, idx)
} else {
Vec::new()
};
if let Some(ref mut l) = listener {
l.diff_end();
}
result
}
pub fn build_path<'a, T, F>(
orig: &[T],
rev: &[T],
equalizer: &F,
ws: &mut DiffWorkspace,
mut listener: Option<&'a mut (dyn DiffAlgorithmListener + '_)>,
) -> Option<usize>
where
F: Fn(&T, &T) -> bool,
{
let n = orig.len();
let m = rev.len();
let max = n + m + 1;
let size = 1 + 2 * max;
let middle = max;
ws.arena.clear();
ws.arena.reserve(max * 2);
if ws.diagonal.len() < size {
ws.diagonal.resize(size, None);
} else {
ws.diagonal.fill(None);
}
ws.arena.push(PathNode {
i: 0,
j: -1,
is_snake: true,
is_bootstrap: true,
prev: None,
});
ws.diagonal[middle + 1] = Some(0);
for d in 0..max {
let d_isize = d as isize;
if let Some(ref mut l) = listener {
l.path_node(d, max, d);
}
for k in (-d_isize..=d_isize).step_by(2) {
let kmiddle = (middle as isize + k) as usize;
let kplus = kmiddle + 1;
let kminus = kmiddle - 1;
let (i_start, prev_idx) = if k == -d_isize {
let p = ws.diagonal[kplus].unwrap_or(0);
(ws.arena[p].i, p)
} else if k != d_isize {
let pm = ws.diagonal[kminus];
let pp = ws.diagonal[kplus];
match (pm, pp) {
(Some(pm), Some(pp)) => {
if ws.arena[pm].i < ws.arena[pp].i {
(ws.arena[pp].i, pp)
} else {
(ws.arena[pm].i + 1, pm)
}
}
(None, Some(pp)) => (ws.arena[pp].i, pp),
(Some(pm), None) => (ws.arena[pm].i + 1, pm),
(None, None) => (0, 0),
}
} else {
let p = ws.diagonal[kminus].unwrap_or(0);
(ws.arena[p].i + 1, p)
};
let mut i = i_start;
let mut j = i as isize - k;
let collapsed_prev = PathNode::previous_snake(&ws.arena, prev_idx);
let node_idx = ws.arena.len();
ws.arena.push(PathNode {
i,
j,
is_snake: false,
is_bootstrap: false,
prev: collapsed_prev,
});
while i < n && j >= 0 && (j as usize) < m && equalizer(&orig[i], &rev[j as usize]) {
i += 1;
j += 1;
}
let final_node_idx = if i != ws.arena[node_idx].i {
let snake_idx = ws.arena.len();
ws.arena.push(PathNode {
i,
j,
is_snake: true,
is_bootstrap: false,
prev: Some(node_idx),
});
snake_idx
} else {
node_idx
};
ws.diagonal[kmiddle] = Some(final_node_idx);
if i >= n && j >= 0 && (j as usize) >= m {
return Some(final_node_idx);
}
}
}
None
}
fn build_revision(arena: &[PathNode], head_idx: usize) -> Vec<Change> {
let mut raw_changes = Vec::new();
let mut curr_idx = Some(head_idx);
if let Some(idx) = curr_idx {
if arena[idx].is_snake {
curr_idx = arena[idx].prev;
}
}
loop {
let idx = match curr_idx {
Some(i) => i,
None => break,
};
let node = &arena[idx];
let prev_idx = match node.prev {
Some(p) => p,
None => break,
};
if arena[prev_idx].j < 0 {
break;
}
let i = node.i;
let j = node.j.max(0) as usize;
let path_idx = prev_idx;
let path_node = &arena[path_idx];
let ianchor = path_node.i;
let janchor = path_node.j.max(0) as usize;
let delta_type = match (ianchor == i, janchor == j) {
(true, false) => DeltaType::Insert,
(false, true) => DeltaType::Delete,
_ => DeltaType::Change,
};
raw_changes.push(Change {
delta_type,
start_original: ianchor,
end_original: i,
start_revised: janchor,
end_revised: j,
});
curr_idx = if arena[path_idx].is_snake {
arena[path_idx].prev
} else {
Some(path_idx)
};
}
raw_changes.reverse();
raw_changes
}