weird edge case

[colin-kiegel]

Steps to reproduce

extern crate difference;
use difference::Changeset;

fn main() {
    let ch = Changeset::new("a b : g",
                            "b a : b b : g g", " ");
    println!("{}", ch);
}

Got

-a
 b
+a
 :
-g
+b b
 : g
+g

Expected

-a
 b
+a
 :
-g
+b b : g g

[colin-kiegel]

I pushed a PR, which adds a testcase for this (plus fuzzy testing) #20 :-)

[colin-kiegel]

The bug is in the LCS algorithm:

// src/lcs.rs
#[test]
fn test_lcs() {
    assert_eq!(lcs("a b : g", "b a : b b : g g", " "), (3, "a b : g ".to_string()));
}

fails with

---- lcs::test_lcs stdout ----
        thread 'lcs::test_lcs' panicked at 'assertion failed: `(left == right)`
  left: `(4, "b : : g ")`,
 right: `(3, "a b : g ")`'

Note that "b : : g " is not a substring of "a b : g" at all.

[colin-kiegel]

@johannhof Is this a common algorithm? If you could paste a link to a proof or explanation of this algorithm, I could try to spot the mistake in the implementation. But without documentation it's a bit hard to understand how this algorithm is supposed to work.

[colin-kiegel]

I'm currently testing a new implementation. I'll let you know if I make any progress.