aboutsummaryrefslogtreecommitdiff
path: root/diff
diff options
context:
space:
mode:
authorGravatar Runxi Yu2026-03-04 08:26:56 +0800
committerGravatar Runxi Yu2026-03-04 08:59:53 +0800
commitab7501be34032fb9e5c48726a68ae90a917af9eb (patch)
tree20d005647569befea8133e953c3270e8fd2a2a5b /diff
parent*: gofumpt (diff)
signatureNo signature
*: Lint
Diffstat (limited to 'diff')
-rw-r--r--diff/lines/diff.go29
-rw-r--r--diff/lines/diff_test.go7
-rw-r--r--diff/trees/diff.go81
-rw-r--r--diff/trees/diff_test.go28
-rw-r--r--diff/trees/path.go3
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
}