cj1128/myers-diff

😍 Golang implementation for myers diff algorithm

Myers Diff

Demonstrate Myers Diff algorithm in Go. Git 是怎样生成 diff 的：Myers 算法。

Usage

# char mode: myers-diff -char src_text dst_text
myers-diff -char ABCABBA CBABAC
# file mode: myers-diff src_file dst_file
myers-diff file1.txt file2.txt

Install

go get -v github.com/cj1128/myers-diff

myers-diff's Issues

printTrace

thanks your implementation helped me to understand the algorithm。

myers-diff/main.go

Line 200 in 9678f9a

func printTrace(trace []map[int]int) {

not all k in [-d, d] will save in trace. if k not in trace x := v[k] x will be zero as default.

may be this is the better

func printTrace(trace []map[int]int) {
	for d := 0; d < len(trace); d++ {
		fmt.Printf("d = %d:\n", d)
		v := trace[d]
		for k, x := range v {
			y := x - k
			fmt.Printf("   k = %2d: (%d, %d)\n", k, x, y)
		}
	}
}

回溯时循环条件好像有点问题

https://github.com/fate-lovely/myers-diff/blob/4613bf7fbf0ba327d5e9069d364e78b721cca17e/main.go#L157
我使用
A B C D E
和
A B D E测试的时候，结果是
-A B C，定位到错误应该是在回溯的时候，这里d==0的时候也应该考虑进去，如果两个文本前面内容相同，需要在d==0的时候执行添加MOV的操作。在https://github.com/pkg/diff/blob/7e42a82532c282d39d727ace02bfdef801c6db2c/myers.go#L71 这个实现里面就有考虑d==0的情况