search

ocharles / diff3

3-way diff algorithm for Haskell
Other
7 stars 1 forks source link

Made conflicts shorter #2

Closed sth closed 7 years ago

sth commented 8 years ago

Conflicts sometimes include more elements than necessary:

GHCi> diff3 "14567" "1234567" "1567"
[Unchanged "1",Conflict "456" "23456" "56",Unchanged "7"]

56 shouldn't be included in the conflict.

This patch fixes the issue by only including additional elements for the diff that is "behind", instead of both diffs. It advances only the minimal amount necessary to bring both diffs in sync when searching for the end of a conflict.

This way less items are included in the conflict:

GHCi> diff3 "14567" "1234567" "1567"
[Unchanged "1",Conflict "4" "234" "",Unchanged "567"]
ocharles commented 8 years ago

Excellent. Again, do you think this could be encoded as a property?

sth commented 8 years ago

I'm not sure how this would best be encoded. I tried a check to make sure that conflicts never start or end with the same character, but this is a too strong property. There are reasonable conflicts that end up this way:

GHCi> diff3 "a" "aa" "ba"
[Conflict "a" "aa" "ba"]

While the conflict could be shorter with [Conflict "" "a" "b", Unchanged "a"], the longer conflict is a result of the two underlying diffs and not easily avoided:

GHCi> getDiff "a" "aa"
[Both 'a' 'a',Second 'a']
GHCi> getDiff "ba" "aa"
[First 'b',Both 'a' 'a',Second 'a']