diff options
| author | 2026-03-04 08:26:56 +0800 | |
|---|---|---|
| committer | 2026-03-04 08:59:53 +0800 | |
| commit | ab7501be34032fb9e5c48726a68ae90a917af9eb (patch) | |
| tree | 20d005647569befea8133e953c3270e8fd2a2a5b /diff | |
| parent | *: gofumpt (diff) | |
| signature | No signature | |
*: Lint
Diffstat (limited to 'diff')
| -rw-r--r-- | diff/lines/diff.go | 29 | ||||
| -rw-r--r-- | diff/lines/diff_test.go | 7 | ||||
| -rw-r--r-- | diff/trees/diff.go | 81 | ||||
| -rw-r--r-- | diff/trees/diff_test.go | 28 | ||||
| -rw-r--r-- | diff/trees/path.go | 3 |
5 files changed, 122 insertions, 26 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() } diff --git a/diff/trees/diff.go b/diff/trees/diff.go index 836b71cc..9583c939 100644 --- a/diff/trees/diff.go +++ b/diff/trees/diff.go @@ -12,9 +12,12 @@ import ( // reaches directory entries. func Diff(a, b *object.Tree, readTree func(objectid.ObjectID) (*object.Tree, error)) ([]Entry, error) { var out []Entry - if err := diffRecursive(a, b, nil, readTree, &out); err != nil { + + err := diffRecursive(a, b, nil, readTree, &out) + if err != nil { return nil, err } + return out, nil } @@ -27,17 +30,23 @@ func diffRecursive(a, b *object.Tree, prefix []byte, readTree func(objectid.Obje for i := range b.Entries { entry := &b.Entries[i] full := joinPath(prefix, entry.Name) + *out = append(*out, Entry{Path: full, Kind: EntryKindAdded, Old: nil, New: entry}) - if entry.Mode == object.FileModeDir { - sub, err := readTree(entry.ID) - if err != nil { - return err - } - if err := diffRecursive(nil, sub, full, readTree, out); err != nil { - return err - } + if entry.Mode != object.FileModeDir { + continue + } + + sub, err := readTree(entry.ID) + if err != nil { + return err + } + + err = diffRecursive(nil, sub, full, readTree, out) + if err != nil { + return err } } + return nil } @@ -45,25 +54,33 @@ func diffRecursive(a, b *object.Tree, prefix []byte, readTree func(objectid.Obje for i := range a.Entries { entry := &a.Entries[i] full := joinPath(prefix, entry.Name) + *out = append(*out, Entry{Path: full, Kind: EntryKindDeleted, Old: entry, New: nil}) - if entry.Mode == object.FileModeDir { - sub, err := readTree(entry.ID) - if err != nil { - return err - } - if err := diffRecursive(sub, nil, full, readTree, out); err != nil { - return err - } + if entry.Mode != object.FileModeDir { + continue + } + + sub, err := readTree(entry.ID) + if err != nil { + return err + } + + err = diffRecursive(sub, nil, full, readTree, out) + if err != nil { + return err } } + return nil } i := 0 + j := 0 for i < len(a.Entries) && j < len(b.Entries) { left := &a.Entries[i] right := &b.Entries[j] + cmp := object.TreeEntryNameCompare( left.Name, left.Mode, @@ -73,49 +90,63 @@ func diffRecursive(a, b *object.Tree, prefix []byte, readTree func(objectid.Obje switch { case cmp < 0: full := joinPath(prefix, left.Name) + *out = append(*out, Entry{Path: full, Kind: EntryKindDeleted, Old: left, New: nil}) if left.Mode == object.FileModeDir { sub, err := readTree(left.ID) if err != nil { return err } - if err := diffRecursive(sub, nil, full, readTree, out); err != nil { + + err = diffRecursive(sub, nil, full, readTree, out) + if err != nil { return err } } + i++ case cmp > 0: full := joinPath(prefix, right.Name) + *out = append(*out, Entry{Path: full, Kind: EntryKindAdded, Old: nil, New: right}) if right.Mode == object.FileModeDir { sub, err := readTree(right.ID) if err != nil { return err } - if err := diffRecursive(nil, sub, full, readTree, out); err != nil { + + err = diffRecursive(nil, sub, full, readTree, out) + if err != nil { return err } } + j++ default: full := joinPath(prefix, left.Name) + modified := left.Mode != right.Mode || left.ID != right.ID if modified { *out = append(*out, Entry{Path: full, Kind: EntryKindModified, Old: left, New: right}) } + if left.Mode == object.FileModeDir && right.Mode == object.FileModeDir && left.ID != right.ID { leftSub, err := readTree(left.ID) if err != nil { return err } + rightSub, err := readTree(right.ID) if err != nil { return err } - if err := diffRecursive(leftSub, rightSub, full, readTree, out); err != nil { + + err = diffRecursive(leftSub, rightSub, full, readTree, out) + if err != nil { return err } } + i++ j++ } @@ -124,13 +155,16 @@ func diffRecursive(a, b *object.Tree, prefix []byte, readTree func(objectid.Obje for ; i < len(a.Entries); i++ { left := &a.Entries[i] full := joinPath(prefix, left.Name) + *out = append(*out, Entry{Path: full, Kind: EntryKindDeleted, Old: left, New: nil}) if left.Mode == object.FileModeDir { sub, err := readTree(left.ID) if err != nil { return err } - if err := diffRecursive(sub, nil, full, readTree, out); err != nil { + + err = diffRecursive(sub, nil, full, readTree, out) + if err != nil { return err } } @@ -139,13 +173,16 @@ func diffRecursive(a, b *object.Tree, prefix []byte, readTree func(objectid.Obje for ; j < len(b.Entries); j++ { right := &b.Entries[j] full := joinPath(prefix, right.Name) + *out = append(*out, Entry{Path: full, Kind: EntryKindAdded, Old: nil, New: right}) if right.Mode == object.FileModeDir { sub, err := readTree(right.ID) if err != nil { return err } - if err := diffRecursive(nil, sub, full, readTree, out); err != nil { + + err = diffRecursive(nil, sub, full, readTree, out) + if err != nil { return err } } diff --git a/diff/trees/diff_test.go b/diff/trees/diff_test.go index 2fb8540f..1664bdf8 100644 --- a/diff/trees/diff_test.go +++ b/diff/trees/diff_test.go @@ -157,88 +157,112 @@ type diffExpectation struct { func writeTestFile(t *testing.T, path, data string) { t.Helper() - if err := os.MkdirAll(filepath.Dir(path), 0o755); err != nil { + + err := os.MkdirAll(filepath.Dir(path), 0o755) + if err != nil { t.Fatalf("create directory for %s: %v", path, err) } - if err := os.WriteFile(path, []byte(data), 0o644); err != nil { + + err = os.WriteFile(path, []byte(data), 0o644) + if err != nil { t.Fatalf("write %s: %v", path, err) } } func openLooseStore(t *testing.T, objectsPath string, algo objectid.Algorithm) *loose.Store { t.Helper() + root, err := os.OpenRoot(objectsPath) if err != nil { t.Fatalf("OpenRoot(%q): %v", objectsPath, err) } + t.Cleanup(func() { _ = root.Close() }) + store, err := loose.New(root, algo) if err != nil { t.Fatalf("loose.New: %v", err) } + t.Cleanup(func() { _ = store.Close() }) + return store } func makeReadTree(t *testing.T, store *loose.Store, algo objectid.Algorithm) func(objectid.ObjectID) (*object.Tree, error) { t.Helper() + return func(id objectid.ObjectID) (*object.Tree, error) { ty, content, err := store.ReadBytesContent(id) if err != nil { return nil, err } + if ty != objecttype.TypeTree { return nil, errors.New("diff/trees test: object is not a tree") } + return object.ParseTree(content, algo) } } func mustReadTree(t *testing.T, readTree func(objectid.ObjectID) (*object.Tree, error), id objectid.ObjectID) *object.Tree { t.Helper() + tree, err := readTree(id) if err != nil { t.Fatalf("read tree %s: %v", id, err) } + return tree } func parseID(t *testing.T, algo objectid.Algorithm, hex string) objectid.ObjectID { t.Helper() + id, err := objectid.ParseHex(algo, hex) if err != nil { t.Fatalf("parse object id %q: %v", hex, err) } + return id } func checkDiffs(t *testing.T, diffs []trees.Entry, expected map[string]diffExpectation) { t.Helper() + got := make(map[string]trees.Entry, len(diffs)) for _, diff := range diffs { path := string(diff.Path) if _, exists := got[path]; exists { t.Fatalf("duplicate diff path %q", path) } + got[path] = diff } + if len(got) != len(expected) { t.Fatalf("diff count = %d, want %d", len(got), len(expected)) } + for path, want := range expected { diff, ok := got[path] if !ok { t.Fatalf("missing diff for %q", path) } + if diff.Kind != want.kind { t.Errorf("%s kind = %v, want %v", path, diff.Kind, want.kind) } + if (diff.Old == nil) != want.oldNil { t.Errorf("%s old nil = %v, want %v", path, diff.Old == nil, want.oldNil) } + if (diff.New == nil) != want.newNil { t.Errorf("%s new nil = %v, want %v", path, diff.New == nil, want.newNil) } + if diff.Kind == trees.EntryKindModified && diff.Old != nil && diff.New != nil && diff.Old.ID == diff.New.ID { t.Errorf("%s modified entry should change IDs", path) } diff --git a/diff/trees/path.go b/diff/trees/path.go index 0ced379a..e40f3de5 100644 --- a/diff/trees/path.go +++ b/diff/trees/path.go @@ -4,11 +4,14 @@ func joinPath(prefix, name []byte) []byte { if len(prefix) == 0 { out := make([]byte, len(name)) copy(out, name) + return out } + out := make([]byte, len(prefix)+1+len(name)) copy(out, prefix) out[len(prefix)] = '/' copy(out[len(prefix)+1:], name) + return out } |
