| 1 | package diff |
| 2 | |
| 3 | import ( |
| 4 | "fmt" |
| 5 | "runtime" |
| 6 | "strings" |
| 7 | "testing" |
| 8 | "time" |
| 9 | ) |
| 10 | |
| 11 | // TestLargeRewriteBoundedCost proves a full rewrite of a large file no longer |
| 12 | // pays O(N²): the edit-distance cap skips the line-by-line render, so memory and |
| 13 | // time stay bounded while the tallies and an omitted-diff marker still report the |
| 14 | // change. Before the cap this allocated ~565 MB for 3000 lines (≈6 GB at 10k). |
| 15 | func TestLargeRewriteBoundedCost(t *testing.T) { |
| 16 | var oldB, newB strings.Builder |
| 17 | const n = 6000 |
| 18 | for i := 0; i < n; i++ { |
| 19 | fmt.Fprintf(&oldB, "old line %d\n", i) |
| 20 | fmt.Fprintf(&newB, "totally different new line %d\n", i) |
| 21 | } |
| 22 | var m0, m1 runtime.MemStats |
| 23 | runtime.GC() |
| 24 | runtime.ReadMemStats(&m0) |
| 25 | start := time.Now() |
| 26 | c := Build("big.txt", oldB.String(), newB.String(), Modify) |
| 27 | elapsed := time.Since(start) |
| 28 | runtime.ReadMemStats(&m1) |
| 29 | allocMB := float64(m1.TotalAlloc-m0.TotalAlloc) / (1 << 20) |
| 30 | t.Logf("2×%d-line rewrite: %v, %.1f MB, +%d/-%d", n, elapsed, allocMB, c.Added, c.Removed) |
| 31 | |
| 32 | if allocMB > 150 { |
| 33 | t.Errorf("allocated %.1f MB — the edit-distance cap should bound this", allocMB) |
| 34 | } |
| 35 | if elapsed > time.Second { |
| 36 | t.Errorf("took %v — should be bounded", elapsed) |
| 37 | } |
| 38 | if c.Added != n || c.Removed != n { |
| 39 | t.Errorf("tallies wrong: +%d/-%d, want +%d/-%d", c.Added, c.Removed, n, n) |
| 40 | } |
| 41 | if !strings.Contains(c.Diff, "too large") { |
| 42 | t.Errorf("expected an omitted-diff marker, got %q", c.Diff) |
| 43 | } |
| 44 | } |
| 45 | |
| 46 | // TestSmallEditOnLargeFileStillDiffs proves the cap doesn't punish the common |
| 47 | // case: a tiny edit in a big file converges far below the cap, so it keeps a real |
| 48 | // line-by-line diff regardless of file size. |
| 49 | func TestSmallEditOnLargeFileStillDiffs(t *testing.T) { |
| 50 | var oldB strings.Builder |
| 51 | const n = 8000 |
| 52 | for i := 0; i < n; i++ { |
| 53 | fmt.Fprintf(&oldB, "line %d\n", i) |
| 54 | } |
| 55 | old := oldB.String() |
| 56 | updated := strings.Replace(old, "line 4000\n", "line 4000 EDITED\n", 1) |
| 57 | c := Build("big.txt", old, updated, Modify) |
| 58 | if c.Added != 1 || c.Removed != 1 { |
| 59 | t.Errorf("tallies = +%d/-%d, want +1/-1", c.Added, c.Removed) |
| 60 | } |
| 61 | if !strings.Contains(c.Diff, "line 4000 EDITED") || strings.Contains(c.Diff, "too large") { |
| 62 | t.Errorf("small edit on a large file should keep a real diff, got %q", firstN(c.Diff, 200)) |
| 63 | } |
| 64 | } |
| 65 | |
| 66 | func firstN(s string, n int) string { |
| 67 | if len(s) > n { |
| 68 | return s[:n] |
| 69 | } |
| 70 | return s |
| 71 | } |
| 72 |