diff options
| author | 2026-03-04 08:26:56 +0800 | |
|---|---|---|
| committer | 2026-03-04 08:59:53 +0800 | |
| commit | ab7501be34032fb9e5c48726a68ae90a917af9eb (patch) | |
| tree | 20d005647569befea8133e953c3270e8fd2a2a5b /diff/lines | |
| parent | *: gofumpt (diff) | |
| signature | No signature | |
*: Lint
Diffstat (limited to 'diff/lines')
| -rw-r--r-- | diff/lines/diff.go | 29 | ||||
| -rw-r--r-- | diff/lines/diff_test.go | 7 |
2 files changed, 34 insertions, 2 deletions
diff --git a/diff/lines/diff.go b/diff/lines/diff.go index bdcb4d93..ca34f371 100644 --- a/diff/lines/diff.go +++ b/diff/lines/diff.go @@ -5,7 +5,7 @@ import "bytes" // Diff performs a line-based diff. // Lines are bytes up to and including '\n' (final line may lack '\n'). -func Diff(oldB, newB []byte) ([]Chunk, error) { +func Diff(oldB, newB []byte) ([]Chunk, error) { //nolint:maintidx type lineRef struct { base []byte start int @@ -16,17 +16,22 @@ func Diff(oldB, newB []byte) ([]Chunk, error) { if len(b) == 0 { return nil } + var res []lineRef + start := 0 + for i := range b { if b[i] == '\n' { res = append(res, lineRef{base: b, start: start, end: i + 1}) start = i + 1 } } + if start < len(b) { res = append(res, lineRef{base: b, start: start, end: len(b)}) } + return res } @@ -34,6 +39,7 @@ func Diff(oldB, newB []byte) ([]Chunk, error) { newLines := split(newB) n := len(oldLines) + m := len(newLines) if n == 0 && m == 0 { return nil, nil @@ -42,25 +48,32 @@ func Diff(oldB, newB []byte) ([]Chunk, error) { idOf := make(map[string]int) nextID := 0 oldIDs := make([]int, n) + for i, ln := range oldLines { key := string(ln.base[ln.start:ln.end]) + id, ok := idOf[key] if !ok { id = nextID idOf[key] = id nextID++ } + oldIDs[i] = id } + newIDs := make([]int, m) + for i, ln := range newLines { key := string(ln.base[ln.start:ln.end]) + id, ok := idOf[key] if !ok { id = nextID idOf[key] = id nextID++ } + newIDs[i] = id } @@ -74,11 +87,13 @@ func Diff(oldB, newB []byte) ([]Chunk, error) { } x0 := 0 + y0 := 0 for x0 < n && y0 < m && oldIDs[x0] == newIDs[y0] { x0++ y0++ } + Vprev[offset+0] = x0 trace = append(trace, append([]int(nil), Vprev...)) @@ -97,17 +112,20 @@ func Diff(oldB, newB []byte) ([]Chunk, error) { } else { x = Vprev[offset+(k-1)] + 1 } + y := x - k for x < n && y < m && oldIDs[x] == newIDs[y] { x++ y++ } + V[offset+k] = x if x >= n && y >= m { trace = append(trace, V) found = true + break } } @@ -122,9 +140,11 @@ func Diff(oldB, newB []byte) ([]Chunk, error) { kind ChunkKind lineref lineRef } + revEdits := make([]edit, 0, n+m) x := n + y := m for D := len(trace) - 1; D >= 0; D-- { k := x - y @@ -134,6 +154,7 @@ func Diff(oldB, newB []byte) ([]Chunk, error) { prevX int prevY int ) + if D > 0 { prevV := trace[D-1] if k == -D || (k != D && prevV[offset+(k-1)] < prevV[offset+(k+1)]) { @@ -141,6 +162,7 @@ func Diff(oldB, newB []byte) ([]Chunk, error) { } else { prevK = k - 1 } + prevX = prevV[offset+prevK] prevY = prevX - prevK } @@ -148,6 +170,7 @@ func Diff(oldB, newB []byte) ([]Chunk, error) { for x > prevX && y > prevY { x-- y-- + revEdits = append(revEdits, edit{kind: ChunkKindUnchanged, lineref: oldLines[x]}) } @@ -169,11 +192,13 @@ func Diff(oldB, newB []byte) ([]Chunk, error) { } var out []Chunk + type meta struct { base []byte start int end int } + var metas []meta for _, e := range revEdits { @@ -184,6 +209,7 @@ func Diff(oldB, newB []byte) ([]Chunk, error) { if len(out) == 0 || out[len(out)-1].Kind != e.kind { out = append(out, Chunk{Kind: e.kind, Data: curBase[curStart:curEnd]}) metas = append(metas, meta{base: curBase, start: curStart, end: curEnd}) + continue } @@ -193,6 +219,7 @@ func Diff(oldB, newB []byte) ([]Chunk, error) { if bytes.Equal(lastMeta.base, curBase) && lastMeta.end == curStart { metas[lastIdx].end = curEnd out[lastIdx].Data = curBase[metas[lastIdx].start:metas[lastIdx].end] + continue } diff --git a/diff/lines/diff_test.go b/diff/lines/diff_test.go index 7ff2c386..c5d5be9f 100644 --- a/diff/lines/diff_test.go +++ b/diff/lines/diff_test.go @@ -9,7 +9,7 @@ import ( "codeberg.org/lindenii/furgit/diff/lines" ) -func TestDiff(t *testing.T) { +func TestDiff(t *testing.T) { //nolint:maintidx t.Parallel() tests := []struct { @@ -291,6 +291,7 @@ func TestDiff(t *testing.T) { if chunks[i].Kind != tt.expected[i].Kind { t.Fatalf("chunk %d kind mismatch: got %v, want %v; chunks: %s", i, chunks[i].Kind, tt.expected[i].Kind, formatChunks(chunks)) } + if !bytes.Equal(chunks[i].Data, tt.expected[i].Data) { t.Fatalf("chunk %d data mismatch: got %q, want %q; chunks: %s", i, string(chunks[i].Data), string(tt.expected[i].Data), formatChunks(chunks)) } @@ -302,15 +303,19 @@ func TestDiff(t *testing.T) { func formatChunks(chunks []lines.Chunk) string { var b strings.Builder b.WriteByte('[') + for i, chunk := range chunks { if i > 0 { b.WriteString(", ") } + b.WriteString(chunkKindName(chunk.Kind)) b.WriteByte(':') b.WriteString(strconv.Quote(string(chunk.Data))) } + b.WriteByte(']') + return b.String() } |
