use crate::util::sqrt;use crate::{Algorithm, BasicLineDiffPrinter, Diff, InternedInput, UnifiedDiffConfig};use expect_test::expect; #[test]fn myers_is_even() { let before = "a\nb\nx\nx\ny\n"; let after = "b\na\nx\ny\nx\n"; cov_mark::check!(EVEN_SPLIT); // if the check for is_odd incorrectly always true then we take a fastpath // when we shouldn't, which always leads to infinite iterations/recursion // still we check the number of iterations here in case the search // is buggy in more subtle ways cov_mark::check_count!(SPLIT_SEARCH_ITER, 15); let input = InternedInput::new(before, after); let diff = Diff::compute(Algorithm::Myers, &input); expect![[r#" @@ -1,5 +1,5 @@ -a b -x +a x y +x "#]] .assert_eq( &diff .unified_diff( &BasicLineDiffPrinter(&input.interner), UnifiedDiffConfig::default(), &input, ) .to_string(), );} #[test]fn myers_is_odd() { let before = "a\nb\nx\ny\nx\n"; let after = "b\na\nx\ny\n"; cov_mark::check!(ODD_SPLIT); // if the check for odd doesn't work then // we still find the correct result but the number of search // iterations increases cov_mark::check_count!(SPLIT_SEARCH_ITER, 9); let input = InternedInput::new(before, after); let diff = Diff::compute(Algorithm::Myers, &input); expect![[r#" @@ -1,5 +1,4 @@ -a b +a x y -x "#]] .assert_eq( &diff .unified_diff( &BasicLineDiffPrinter(&input.interner), UnifiedDiffConfig::default(), &input, ) .to_string(), );} /// The frequency limit above which a line becomes a candidate for discarding comes from git's/// `xdl_bogosqrt`, which rounds the halved bit count up. Rounding down halves the limit for every/// odd bit length, so lines git considers ordinary are treated as too frequent to match.#[test]fn the_frequency_limit_rounds_the_way_git_rounds() { // `xdl_bogosqrt`: for (i = 1; n > 0; n >>= 2) i <<= 1; fn bogosqrt(mut n: usize) -> u32 { let mut i = 1u32; while n > 0 { n >>= 2; i <<= 1; } i } // Test that sqrt matches git's bogosqrt for typical values // and values near the top of the `usize` range let mut inputs = vec![0, 1, 2, 3, 4, 16, 24, 69, 277, 345, 450, 1000, 4096, 65_535]; if usize::BITS >= 4 { let hi = 1usize << (usize::BITS - 3); inputs.extend([hi - 1, hi]); } for n in inputs { assert_eq!(sqrt(n), bogosqrt(n), "at {n}"); } // On 64-bit platforms we have to clamp to `u32::MAX` // when the input is >= `1 << 62` to avoid overflow. let edge_inputs = [usize::MAX, 1 << (usize::BITS - 1), 1 << (usize::BITS - 2)]; if usize::BITS >= 64 { for n in edge_inputs { assert_eq!(sqrt(n), u32::MAX, "at {n}"); } } // On platforms with smaller word sizes these values // should still be at parity with bogosqrt. else { for n in edge_inputs { assert_eq!(sqrt(n), bogosqrt(n), "at {n}"); } }}
use crate::util::sqrt;
use crate::{Algorithm, BasicLineDiffPrinter, Diff, InternedInput, UnifiedDiffConfig};
use expect_test::expect;
#[test]
fn myers_is_even() {
let before = "a\nb\nx\nx\ny\n";
let after = "b\na\nx\ny\nx\n";
cov_mark::check!(EVEN_SPLIT);
// if the check for is_odd incorrectly always true then we take a fastpath
// when we shouldn't, which always leads to infinite iterations/recursion
// still we check the number of iterations here in case the search
// is buggy in more subtle ways
cov_mark::check_count!(SPLIT_SEARCH_ITER, 15);
let input = InternedInput::new(before, after);
let diff = Diff::compute(Algorithm::Myers, &input);
expect![[r#"
@@ -1,5 +1,5 @@
-a
b
-x
+a
x
y
+x
"#]]
.assert_eq(
&diff
.unified_diff(
&BasicLineDiffPrinter(&input.interner),
UnifiedDiffConfig::default(),
&input,
)
.to_string(),
);
}
#[test]
fn myers_is_odd() {
let before = "a\nb\nx\ny\nx\n";
let after = "b\na\nx\ny\n";
cov_mark::check!(ODD_SPLIT);
// if the check for odd doesn't work then
// we still find the correct result but the number of search
// iterations increases
cov_mark::check_count!(SPLIT_SEARCH_ITER, 9);
let input = InternedInput::new(before, after);
let diff = Diff::compute(Algorithm::Myers, &input);
expect![[r#"
@@ -1,5 +1,4 @@
-a
b
+a
x
y
-x
"#]]
.assert_eq(
&diff
.unified_diff(
&BasicLineDiffPrinter(&input.interner),
UnifiedDiffConfig::default(),
&input,
)
.to_string(),
);
}
/// The frequency limit above which a line becomes a candidate for discarding comes from git's
/// `xdl_bogosqrt`, which rounds the halved bit count up. Rounding down halves the limit for every
/// odd bit length, so lines git considers ordinary are treated as too frequent to match.
#[test]
fn the_frequency_limit_rounds_the_way_git_rounds() {
// `xdl_bogosqrt`: for (i = 1; n > 0; n >>= 2) i <<= 1;
fn bogosqrt(mut n: usize) -> u32 {
let mut i = 1u32;
while n > 0 {
n >>= 2;
i <<= 1;
}
i
}
// Test that sqrt matches git's bogosqrt for typical values
// and values near the top of the `usize` range
let mut inputs = vec![0, 1, 2, 3, 4, 16, 24, 69, 277, 345, 450, 1000, 4096, 65_535];
if usize::BITS >= 4 {
let hi = 1usize << (usize::BITS - 3);
inputs.extend([hi - 1, hi]);
}
for n in inputs {
assert_eq!(sqrt(n), bogosqrt(n), "at {n}");
}
// On 64-bit platforms we have to clamp to `u32::MAX`
// when the input is >= `1 << 62` to avoid overflow.
let edge_inputs = [usize::MAX, 1 << (usize::BITS - 1), 1 << (usize::BITS - 2)];
if usize::BITS >= 64 {
for n in edge_inputs {
assert_eq!(sqrt(n), u32::MAX, "at {n}");
}
}
// On platforms with smaller word sizes these values
// should still be at parity with bogosqrt.
else {
for n in edge_inputs {
assert_eq!(sqrt(n), bogosqrt(n), "at {n}");
}
}
}