Add imara histogram diff algorithm

hardy7cc

Mar 12, 2025, 7:06 PM

RVAOC2N4FQURWBSK75RFOSMIOZU2BOMSLS6Z5CMZXBJD64DPCABAC

Dependencies

[2] GA3P7FOM Nicer conflict markers
[3] OY3CGEHQ Early stop in the diff algorithms for diff --short
[4] SXEYMYF7 Fixing the bad changes in history (unfortunately, by rebooting).

Change contents

edit in libpijul/src/diff/diff.rs at line 7

[3.801683]

[3.801683]

ImaraHistogram,
replacement in libpijul/src/diff/diff.rs at line 22

[2.5624]→[3.582:623](∅→∅),[3.582]→[3.582:623](∅→∅)

let mut dd = diffs::Replace::new(D {

[2.5624]

[3.623]

let result = D {
replacement in libpijul/src/diff/diff.rs at line 25

[3.705]→[3.705:713](∅→∅),[3.713]→[3.801952:802185](∅→∅),[3.801952]→[3.801952:802185](∅→∅),[3.802185]→[3.714:738](∅→∅),[3.738]→[3.802204:802409](∅→∅),[3.802204]→[3.802204:802409](∅→∅),[3.802409]→[2.5625:5649](∅→∅),[3.767]→[3.802428:802454](∅→∅),[2.5649]→[3.802428:802454](∅→∅),[3.802428]→[3.802428:802454](∅→∅)

});
match algorithm {
Algorithm::Patience => diffs::patience::diff(
&mut dd,
lines_a,
0,
lines_a.len(),
lines_b,
0,
lines_b.len(),
)
.unwrap_or(()),
Algorithm::Myers => diffs::myers::diff(
&mut dd,
lines_a,
0,
lines_a.len(),
lines_b,
0,
lines_b.len(),
)
.unwrap_or(()),
}
dd.into_inner()

[3.705]

[3.802454]

};
return match algorithm {
Algorithm::Patience => {
let mut dd = diffs::Replace::new(result);
diffs::patience::diff(
&mut dd,
lines_a,
0,
lines_a.len(),
lines_b,
0,
lines_b.len(),
)
.unwrap_or(());
dd.into_inner()
}
Algorithm::Myers => {
let mut dd = diffs::Replace::new(result);
diffs::myers::diff(
&mut dd,
lines_a,
0,
lines_a.len(),
lines_b,
0,
lines_b.len(),
)
.unwrap_or(());
dd.into_inner()
}
Algorithm::ImaraHistogram => {
let source = imara_diff::intern::InternedInput::new(&Lines(lines_a), &Lines(lines_b));
imara_diff::diff(imara_diff::Algorithm::Histogram, &source, result)
}
};
edit in libpijul/src/diff/diff.rs at line 152

[3.804257]

[3.804312]

/// struct used for imara interning see InternedInput
struct Lines<'a>(&'a [Line<'a>]);

impl<'a> imara_diff::intern::TokenSource for &Lines<'a> {
type Token = &'a Line<'a>;
type Tokenizer = core::slice::Iter<'a, Line<'a>>;

fn tokenize(&self) -> Self::Tokenizer {
self.0.iter()
}
fn estimate_tokens(&self) -> u32 {
self.0.len() as u32
}
}

impl imara_diff::Sink for D {
type Out = D;

fn process_change(&mut self, before: std::ops::Range<u32>, after: std::ops::Range<u32>) {
debug!(
"Process change: old:{:?}-{:?} new:{:?}-{:?}",
before.start, before.end, after.start, after.end
);
self.r.push(Replacement {
old: before.start as usize,
old_len: before.len(),
new: after.start as usize,
new_len: after.len(),
is_cyclic: false,
});
}

fn finish(self) -> Self::Out {
self
}
}