Not reporting minimal diff when letter is changed within word about icdiff

[jeffkaufman]

Duplicate of #57; both of these are difflib issues.

[lurch]

I've been having a poke around this afternoon - as #57 points out, icdiff calls difflib._mdiff, which in turn calls difflib.ndiff, so that's what I'm using here. Python2 and Python3 both show the following behaviour (which I can't explain, as I haven't delved too deeply into the internals of difflib's algorithm!)

>>> import difflib
>>> list(difflib.ndiff(['aaa'], ['aaa']))
['  aaa']
>>> list(difflib.ndiff(['aaa'], ['baa']))
['- aaa', '+ baa']
>>> list(difflib.ndiff(['aaa'], ['aba']))
['- aaa', '+ aba']
>>> list(difflib.ndiff(['aaa'], ['aab']))
['- aaa', '+ aab']
>>> list(difflib.ndiff(['aaaa'], ['aaaa']))
['  aaaa']
>>> list(difflib.ndiff(['aaaa'], ['baaa']))
['- aaaa', '?    -\n', '+ baaa', '? +\n']
>>> list(difflib.ndiff(['aaaa'], ['abaa']))
['- aaaa', '+ abaa']
>>> list(difflib.ndiff(['aaaa'], ['aaba']))
['- aaaa', '?    -\n', '+ aaba', '?   +\n']
>>> list(difflib.ndiff(['aaaa'], ['aaab']))
['- aaaa', '?    ^\n', '+ aaab', '?    ^\n']
>>> list(difflib.ndiff(['aaaaa'], ['aaaaa']))
['  aaaaa']
>>> list(difflib.ndiff(['aaaaa'], ['baaaa']))
['- aaaaa', '?     -\n', '+ baaaa', '? +\n']
>>> list(difflib.ndiff(['aaaaa'], ['abaaa']))
['- aaaaa', '+ abaaa']
>>> list(difflib.ndiff(['aaaaa'], ['aabaa']))
['- aaaaa', '?     -\n', '+ aabaa', '?   +\n']
>>> list(difflib.ndiff(['aaaaa'], ['aaaba']))
['- aaaaa', '?     -\n', '+ aaaba', '?    +\n']
>>> list(difflib.ndiff(['aaaaa'], ['aaaab']))
['- aaaaa', '?     ^\n', '+ aaaab', '?     ^\n']
>>> list(difflib.ndiff(['aaaaaa'], ['abaaaa']))
['- aaaaaa', '+ abaaaa']
>>> list(difflib.ndiff(['aaaaaaa'], ['abaaaaaaa']))
['- aaaaaaa', '+ abaaaaaaa', '? ++\n']

So it seems difflib is able to sometimes correctly determine the minimum diff (the output lines above containing ?), but it's somehow sensitive to the length of the matching and non-matching parts of the string and also the position of the non-match?

https://docs.python.org/2/library/difflib.html#difflib.SequenceMatcher sounds like it might be kinda complicated, so perhaps this is already the best that's reasonably possible? shrug