Something went wrong. Try again.
changelog generator & diff tool stormlightlabs.github.io/git-storm
changelog changeset markdown golang git
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681package diff
import ( _ "embed" "strings" "testing")
type algorithmFactory struct { name string new func() Diff}
var diffAlgorithms = []algorithmFactory{ {name: "LCS", new: func() Diff { return &LCS{} }}, {name: "Myers", new: func() Diff { return &Myers{} }},}
//go:embed fixtures/diffs_original.mdvar fixtureOriginal string
//go:embed fixtures/diffs_updated.mdvar fixtureUpdated string
func TestDiff_Compute_EmptySequences(t *testing.T) { for _, alg := range diffAlgorithms { alg := alg t.Run(alg.name, func(t *testing.T) { m := alg.new()
t.Run("both empty", func(t *testing.T) { edits, err := m.Compute([]string{}, []string{}) if err != nil { t.Fatalf("unexpected error: %v", err) } if len(edits) != 0 { t.Errorf("expected 0 edits, got %d", len(edits)) } })
t.Run("a empty, b has content", func(t *testing.T) { b := []string{"line1", "line2"} edits, err := m.Compute([]string{}, b) if err != nil { t.Fatalf("unexpected error: %v", err) } if len(edits) != 2 { t.Fatalf("expected 2 edits, got %d", len(edits)) } for i, edit := range edits { if edit.Kind != Insert { t.Errorf("edit %d: expected Insert, got %v", i, edit.Kind) } if edit.Content != b[i] { t.Errorf("edit %d: expected content %q, got %q", i, b[i], edit.Content) } } })
t.Run("b empty, a has content", func(t *testing.T) { a := []string{"line1", "line2"} edits, err := m.Compute(a, []string{}) if err != nil { t.Fatalf("unexpected error: %v", err) } if len(edits) != 2 { t.Fatalf("expected 2 edits, got %d", len(edits)) } for i, edit := range edits { if edit.Kind != Delete { t.Errorf("edit %d: expected Delete, got %v", i, edit.Kind) } if edit.Content != a[i] { t.Errorf("edit %d: expected content %q, got %q", i, a[i], edit.Content) } } }) }) }}
func TestDiff_Compute_IdenticalSequences(t *testing.T) { a := []string{"line1", "line2", "line3"} b := []string{"line1", "line2", "line3"}
for _, alg := range diffAlgorithms { alg := alg t.Run(alg.name, func(t *testing.T) { m := alg.new() edits, err := m.Compute(a, b) if err != nil { t.Fatalf("unexpected error: %v", err) }
if len(edits) != 3 { t.Fatalf("expected 3 edits, got %d", len(edits)) }
for i, edit := range edits { if edit.Kind != Equal { t.Errorf("edit %d: expected Equal, got %v", i, edit.Kind) } if edit.AIndex != i || edit.BIndex != i { t.Errorf("edit %d: expected indices (%d,%d), got (%d,%d)", i, i, i, edit.AIndex, edit.BIndex) } } }) }}
func TestDiff_Compute_SimpleInsert(t *testing.T) { a := []string{"line1", "line3"} b := []string{"line1", "line2", "line3"}
for _, alg := range diffAlgorithms { alg := alg t.Run(alg.name, func(t *testing.T) { m := alg.new() edits, err := m.Compute(a, b) if err != nil { t.Fatalf("unexpected error: %v", err) }
// Verify structure: Equal(line1), Insert(line2), Equal(line3) if len(edits) != 3 { t.Fatalf("expected 3 edits, got %d", len(edits)) }
if edits[0].Kind != Equal || edits[0].Content != "line1" { t.Errorf("edit 0: expected Equal(line1), got %v(%s)", edits[0].Kind, edits[0].Content) } if edits[1].Kind != Insert || edits[1].Content != "line2" { t.Errorf("edit 1: expected Insert(line2), got %v(%s)", edits[1].Kind, edits[1].Content) } if edits[2].Kind != Equal || edits[2].Content != "line3" { t.Errorf("edit 2: expected Equal(line3), got %v(%s)", edits[2].Kind, edits[2].Content) } }) }}
func TestDiff_Compute_SimpleDelete(t *testing.T) { a := []string{"line1", "line2", "line3"} b := []string{"line1", "line3"}
for _, alg := range diffAlgorithms { alg := alg t.Run(alg.name, func(t *testing.T) { m := alg.new() edits, err := m.Compute(a, b) if err != nil { t.Fatalf("unexpected error: %v", err) }
// Verify structure: Equal(line1), Delete(line2), Equal(line3) if len(edits) != 3 { t.Fatalf("expected 3 edits, got %d", len(edits)) }
if edits[0].Kind != Equal || edits[0].Content != "line1" { t.Errorf("edit 0: expected Equal(line1), got %v(%s)", edits[0].Kind, edits[0].Content) } if edits[1].Kind != Delete || edits[1].Content != "line2" { t.Errorf("edit 1: expected Delete(line2), got %v(%s)", edits[1].Kind, edits[1].Content) } if edits[2].Kind != Equal || edits[2].Content != "line3" { t.Errorf("edit 2: expected Equal(line3), got %v(%s)", edits[2].Kind, edits[2].Content) } }) }}
func TestDiff_Compute_CompleteReplacement(t *testing.T) { a := []string{"old1", "old2"} b := []string{"new1", "new2"}
for _, alg := range diffAlgorithms { alg := alg t.Run(alg.name, func(t *testing.T) { m := alg.new() edits, err := m.Compute(a, b) if err != nil { t.Fatalf("unexpected error: %v", err) }
// Should be all deletes followed by all inserts (or interleaved) deleteCount := 0 insertCount := 0 for _, edit := range edits { switch edit.Kind { case Delete: deleteCount++ case Insert: insertCount++ case Equal: t.Errorf("unexpected Equal edit when sequences are completely different") } }
if deleteCount != 2 { t.Errorf("expected 2 deletes, got %d", deleteCount) } if insertCount != 2 { t.Errorf("expected 2 inserts, got %d", insertCount) } }) }}
func TestDiff_Compute_Fixtures(t *testing.T) { original := strings.Split(strings.TrimSpace(fixtureOriginal), "\n") updated := strings.Split(strings.TrimSpace(fixtureUpdated), "\n")
for _, alg := range diffAlgorithms { alg := alg t.Run(alg.name, func(t *testing.T) { m := alg.new() edits, err := m.Compute(original, updated) if err != nil { t.Fatalf("unexpected error: %v", err) }
if len(edits) == 0 { t.Fatal("expected non-empty edit list") }
reconstructed := ApplyEdits(original, edits) if len(reconstructed) != len(updated) { t.Fatalf("reconstructed length %d != updated length %d", len(reconstructed), len(updated)) } for i := range reconstructed { if reconstructed[i] != updated[i] { t.Errorf("line %d: reconstructed %q != updated %q", i, reconstructed[i], updated[i]) } }
counts := CountEditKinds(edits) if counts[Equal] == 0 { t.Error("expected some Equal edits (files share common lines like blank lines)") } if counts[Insert] == 0 { t.Error("expected some Insert edits") } if counts[Delete] == 0 { t.Error("expected some Delete edits") }
t.Logf("Edit statistics: Equal=%d, Insert=%d, Delete=%d, Total=%d", counts[Equal], counts[Insert], counts[Delete], len(edits)) }) }}
func TestDiff_Name(t *testing.T) { for _, alg := range diffAlgorithms { alg := alg t.Run(alg.name, func(t *testing.T) { m := alg.new() if m.Name() != alg.name { t.Errorf("expected name %q, got %q", alg.name, m.Name()) } }) }}
func TestAreSimilarLines(t *testing.T) { tests := []struct { name string a string b string expected bool }{ { name: "identical lines", a: "github.com/foo/bar v1.0.0", b: "github.com/foo/bar v1.0.0", expected: true, }, { name: "similar package different version", a: "github.com/charmbracelet/x/ansi v0.10.1 // indirect", b: "github.com/charmbracelet/x/ansi v0.10.3 // indirect", expected: true, }, { name: "different packages", a: "github.com/charmbracelet/x/term v0.2.1 // indirect", b: "github.com/charmbracelet/x/exp/teatest v0.0.0-20251", expected: false, }, { name: "empty strings", a: "", b: "", expected: true, }, { name: "one empty", a: "some content", b: "", expected: false, }, { name: "completely different", a: "package main", b: "import fmt", expected: false, }, { name: "short common prefix", a: "github.com/foo/bar", b: "github.com/baz/qux", expected: false, }, }
for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { result := areSimilarLines(tt.a, tt.b) if result != tt.expected { t.Errorf("areSimilarLines(%q, %q) = %v, want %v", tt.a, tt.b, result, tt.expected) } }) }}
func TestMergeReplacements(t *testing.T) { tests := []struct { name string input []Edit expected []Edit }{ { name: "empty edits", input: []Edit{}, expected: []Edit{}, }, { name: "single edit", input: []Edit{ {Kind: Equal, AIndex: 0, BIndex: 0, Content: "line1"}, }, expected: []Edit{ {Kind: Equal, AIndex: 0, BIndex: 0, Content: "line1"}, }, }, { name: "merge similar delete and insert", input: []Edit{ {Kind: Delete, AIndex: 0, BIndex: -1, Content: "github.com/foo/bar v1.0.0"}, {Kind: Insert, AIndex: -1, BIndex: 0, Content: "github.com/foo/bar v2.0.0"}, }, expected: []Edit{ {Kind: Replace, AIndex: 0, BIndex: 0, Content: "github.com/foo/bar v1.0.0", NewContent: "github.com/foo/bar v2.0.0"}, }, }, { name: "don't merge dissimilar delete and insert", input: []Edit{ {Kind: Delete, AIndex: 0, BIndex: -1, Content: "github.com/foo/bar v1.0.0"}, {Kind: Insert, AIndex: -1, BIndex: 0, Content: "import fmt"}, }, expected: []Edit{ {Kind: Delete, AIndex: 0, BIndex: -1, Content: "github.com/foo/bar v1.0.0"}, {Kind: Insert, AIndex: -1, BIndex: 0, Content: "import fmt"}, }, }, { name: "merge insert and delete (reversed order)", input: []Edit{ {Kind: Insert, AIndex: -1, BIndex: 0, Content: "github.com/foo/bar v2.0.0"}, {Kind: Delete, AIndex: 0, BIndex: -1, Content: "github.com/foo/bar v1.0.0"}, }, expected: []Edit{ {Kind: Replace, AIndex: 0, BIndex: 0, Content: "github.com/foo/bar v1.0.0", NewContent: "github.com/foo/bar v2.0.0"}, }, }, { name: "mixed operations with merge", input: []Edit{ {Kind: Equal, AIndex: 0, BIndex: 0, Content: "line1"}, {Kind: Delete, AIndex: 1, BIndex: -1, Content: "github.com/foo/bar v1.0.0"}, {Kind: Insert, AIndex: -1, BIndex: 1, Content: "github.com/foo/bar v2.0.0"}, {Kind: Equal, AIndex: 2, BIndex: 2, Content: "line3"}, }, expected: []Edit{ {Kind: Equal, AIndex: 0, BIndex: 0, Content: "line1"}, {Kind: Replace, AIndex: 1, BIndex: 1, Content: "github.com/foo/bar v1.0.0", NewContent: "github.com/foo/bar v2.0.0"}, {Kind: Equal, AIndex: 2, BIndex: 2, Content: "line3"}, }, }, { name: "multiple inserts and deletes without merge", input: []Edit{ {Kind: Delete, AIndex: 0, BIndex: -1, Content: "deleted line 1"}, {Kind: Insert, AIndex: -1, BIndex: 0, Content: "new content A"}, {Kind: Insert, AIndex: -1, BIndex: 1, Content: "new content B"}, }, expected: []Edit{ {Kind: Delete, AIndex: 0, BIndex: -1, Content: "deleted line 1"}, {Kind: Insert, AIndex: -1, BIndex: 0, Content: "new content A"}, {Kind: Insert, AIndex: -1, BIndex: 1, Content: "new content B"}, }, }, }
for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { result := MergeReplacements(tt.input)
if len(result) != len(tt.expected) { t.Fatalf("expected %d edits, got %d", len(tt.expected), len(result)) }
for i := range result { if result[i].Kind != tt.expected[i].Kind { t.Errorf("edit %d: expected Kind %v, got %v", i, tt.expected[i].Kind, result[i].Kind) } if result[i].AIndex != tt.expected[i].AIndex { t.Errorf("edit %d: expected AIndex %d, got %d", i, tt.expected[i].AIndex, result[i].AIndex) } if result[i].BIndex != tt.expected[i].BIndex { t.Errorf("edit %d: expected BIndex %d, got %d", i, tt.expected[i].BIndex, result[i].BIndex) } if result[i].Content != tt.expected[i].Content { t.Errorf("edit %d: expected Content %q, got %q", i, tt.expected[i].Content, result[i].Content) } if result[i].NewContent != tt.expected[i].NewContent { t.Errorf("edit %d: expected NewContent %q, got %q", i, tt.expected[i].NewContent, result[i].NewContent) } } }) }}
func TestDiff_Compute_Unicode(t *testing.T) { a := []string{"Emoji 🚀", "Regular text"} b := []string{"Emoji 🎉", "Regular text"}
for _, alg := range diffAlgorithms { t.Run(alg.name, func(t *testing.T) { m := alg.new() edits, err := m.Compute(a, b) if err != nil { t.Fatalf("unexpected error with unicode: %v", err) }
reconstructed := ApplyEdits(a, edits) if len(reconstructed) != len(b) { t.Fatalf("reconstructed length %d != expected %d", len(reconstructed), len(b)) } for i := range reconstructed { if reconstructed[i] != b[i] { t.Errorf("line %d: %q != %q", i, reconstructed[i], b[i]) } } }) }}
func TestDiff_Compute_VeryLongLines(t *testing.T) { longLine1 := strings.Repeat("a", 5000) longLine2 := strings.Repeat("b", 5000) longLine3 := strings.Repeat("c", 5000)
a := []string{longLine1, longLine2} b := []string{longLine1, longLine3}
for _, alg := range diffAlgorithms { t.Run(alg.name, func(t *testing.T) { m := alg.new() edits, err := m.Compute(a, b) if err != nil { t.Fatalf("unexpected error with long lines: %v", err) }
reconstructed := ApplyEdits(a, edits) if len(reconstructed) != len(b) { t.Fatalf("reconstructed length %d != expected %d", len(reconstructed), len(b)) } for i := range reconstructed { if reconstructed[i] != b[i] { t.Errorf("line %d: lengths %d != %d", i, len(reconstructed[i]), len(b[i])) } } }) }}
func TestDiff_Compute_WhitespaceOnly(t *testing.T) { a := []string{"line1", " ", "line3"} b := []string{"line1", " ", "line3"}
for _, alg := range diffAlgorithms { t.Run(alg.name, func(t *testing.T) { m := alg.new() edits, err := m.Compute(a, b) if err != nil { t.Fatalf("unexpected error: %v", err) }
reconstructed := ApplyEdits(a, edits) if len(reconstructed) != len(b) { t.Fatalf("reconstructed length %d != expected %d", len(reconstructed), len(b)) } for i := range reconstructed { if reconstructed[i] != b[i] { t.Errorf("line %d: %q != %q", i, reconstructed[i], b[i]) } } }) }}
func TestDiff_Compute_AlternatingLines(t *testing.T) { a := []string{"a1", "a2", "a3", "a4", "a5"} b := []string{"b1", "b2", "b3", "b4", "b5"}
for _, alg := range diffAlgorithms { t.Run(alg.name, func(t *testing.T) { m := alg.new() edits, err := m.Compute(a, b) if err != nil { t.Fatalf("unexpected error: %v", err) }
reconstructed := ApplyEdits(a, edits) if len(reconstructed) != len(b) { t.Fatalf("reconstructed length %d != expected %d", len(reconstructed), len(b)) } for i := range reconstructed { if reconstructed[i] != b[i] { t.Errorf("line %d: %q != %q", i, reconstructed[i], b[i]) } } }) }}
func TestDiff_CrossValidation(t *testing.T) { testCases := []struct { name string a []string b []string }{ {"simple", []string{"a", "b", "c"}, []string{"a", "x", "c"}}, {"complex", []string{"1", "2", "3", "4"}, []string{"1", "x", "y", "4"}}, {"empty to content", []string{}, []string{"a", "b", "c"}}, {"content to empty", []string{"a", "b", "c"}, []string{}}, }
for _, tc := range testCases { t.Run(tc.name, func(t *testing.T) { lcs := &LCS{} myers := &Myers{}
lcsEdits, err := lcs.Compute(tc.a, tc.b) if err != nil { t.Fatalf("LCS error: %v", err) }
myersEdits, err := myers.Compute(tc.a, tc.b) if err != nil { t.Fatalf("Myers error: %v", err) }
lcsResult := ApplyEdits(tc.a, lcsEdits) myersResult := ApplyEdits(tc.a, myersEdits)
if len(lcsResult) != len(tc.b) { t.Errorf("LCS reconstruction length mismatch: %d != %d", len(lcsResult), len(tc.b)) } if len(myersResult) != len(tc.b) { t.Errorf("Myers reconstruction length mismatch: %d != %d", len(myersResult), len(tc.b)) }
for i := range tc.b { if i < len(lcsResult) && lcsResult[i] != tc.b[i] { t.Errorf("LCS line %d: %q != %q", i, lcsResult[i], tc.b[i]) } if i < len(myersResult) && myersResult[i] != tc.b[i] { t.Errorf("Myers line %d: %q != %q", i, myersResult[i], tc.b[i]) } } }) }}
func TestDiff_EditIndicesValid(t *testing.T) { a := []string{"line1", "line2", "line3"} b := []string{"line1", "modified", "line3", "line4"}
for _, alg := range diffAlgorithms { t.Run(alg.name, func(t *testing.T) { m := alg.new() edits, err := m.Compute(a, b) if err != nil { t.Fatalf("unexpected error: %v", err) }
for i, edit := range edits { switch edit.Kind { case Equal: if edit.AIndex < 0 || edit.AIndex >= len(a) { t.Errorf("edit %d: invalid AIndex %d (len(a)=%d)", i, edit.AIndex, len(a)) } if edit.BIndex < 0 || edit.BIndex >= len(b) { t.Errorf("edit %d: invalid BIndex %d (len(b)=%d)", i, edit.BIndex, len(b)) } case Delete: if edit.AIndex < 0 || edit.AIndex >= len(a) { t.Errorf("edit %d: invalid AIndex %d for Delete", i, edit.AIndex) } case Insert: if edit.BIndex < 0 || edit.BIndex >= len(b) { t.Errorf("edit %d: invalid BIndex %d for Insert", i, edit.BIndex) } } } }) }}
func BenchmarkLCS_SmallInput(b *testing.B) { a := []string{"line1", "line2", "line3", "line4", "line5"} c := []string{"line1", "modified", "line3", "line4", "added"} lcs := &LCS{}
for b.Loop() { _, _ = lcs.Compute(a, c) }}
func BenchmarkMyers_SmallInput(b *testing.B) { a := []string{"line1", "line2", "line3", "line4", "line5"} c := []string{"line1", "modified", "line3", "line4", "added"} myers := &Myers{}
for b.Loop() { _, _ = myers.Compute(a, c) }}
func BenchmarkLCS_MediumInput(b *testing.B) { a := make([]string, 50) c := make([]string, 50) for i := range 50 { a[i] = "line" + strings.Repeat("x", i) if i%5 == 0 { c[i] = "modified" + strings.Repeat("y", i) } else { c[i] = a[i] } }
lcs := &LCS{}
for b.Loop() { _, _ = lcs.Compute(a, c) }}
func BenchmarkMyers_MediumInput(b *testing.B) { a := make([]string, 50) c := make([]string, 50) for i := range 50 { a[i] = "line" + strings.Repeat("x", i) if i%5 == 0 { c[i] = "modified" + strings.Repeat("y", i) } else { c[i] = a[i] } }
myers := &Myers{}
for b.Loop() { _, _ = myers.Compute(a, c) }}