1package vt
2
3import (
4 "fmt"
5 "math/rand"
6 "testing"
7
8 renderer "github.com/bnema/vev-vt/core"
9 "github.com/stretchr/testify/require"
10)
11
12func styledRow(text string, fg int) []renderer.Cell {
13 row := historyRow(text)
14 for i := range row {
15 row[i].Style = renderer.Style{Bold: true, Foreground: fg}
16 }
17 return row
18}
19
20func rangeTexts(t *testing.T, v HistoryView) []string {
21 t.Helper()
22 var out []string
23 require.NoError(t, v.Range(func(row []renderer.Cell) bool {
24 out = append(out, rowText(row))
25 return true
26 }))
27 return out
28}
29
30// Sealing recycles the private tail storage. No previously handed-out view,
31// snapshot tail or Range row may observe later appends or seals.
32func TestHistoryTailStorageReuseKeepsViewsStable(t *testing.T) {
33 h := NewHistory(HistoryConfig{MaxRows: 64, MaxBytes: 1 << 20, ChunkRows: 4})
34 appendRow := func(i int) {
35 require.NoError(t, h.Append(styledRow(fmt.Sprintf("r%03d", i), i%5+1), LineBound{End: 4}))
36 }
37 for i := range 2 {
38 appendRow(i)
39 }
40 partial := h.View()
41 snap := h.SnapshotView()
42 var ranged [][]renderer.Cell
43 require.NoError(t, partial.Range(func(row []renderer.Cell) bool { ranged = append(ranged, row); return true }))
44
45 for i := 2; i < 14; i++ { // seals three times, reusing storage each time
46 appendRow(i)
47 }
48 sealedView := h.SealAndView()
49 appendRow(14)
50 appendRow(15)
51
52 require.Equal(t, []string{"r000", "r001"}, rangeTexts(t, partial))
53 require.Equal(t, []string{"r000", "r001"}, rangeTexts(t, snap.Tail()))
54 require.Equal(t, "r000", rowText(ranged[0]))
55 require.Equal(t, "r001", rowText(ranged[1]))
56 require.Equal(t, 14, sealedView.Len())
57 texts := rangeTexts(t, sealedView)
58 for i, got := range texts {
59 require.Equal(t, fmt.Sprintf("r%03d", i), got)
60 }
61 live := rangeTexts(t, h.View())
62 require.Len(t, live, 16)
63 require.Equal(t, "r015", live[15])
64 for _, c := range h.chunks {
65 require.NoError(t, c.CheckInvariants())
66 }
67}
68
69func TestHistoryTailStorageIsRecycledAcrossSeals(t *testing.T) {
70 h := NewHistory(HistoryConfig{MaxRows: 64, MaxBytes: 1 << 20, ChunkRows: 4})
71 for i := range 4 {
72 require.NoError(t, h.Append(historyRow(fmt.Sprintf("r%03d", i)), LineBound{End: 4}))
73 }
74 require.Empty(t, h.tail)
75 require.Zero(t, len(h.tailCells))
76 require.NotZero(t, cap(h.tailCells), "seal must keep tail storage for the next chunk")
77 first := &h.tailCells[:1][0]
78 for i := 4; i < 8; i++ {
79 require.NoError(t, h.Append(historyRow(fmt.Sprintf("r%03d", i)), LineBound{End: 4}))
80 }
81 require.Same(t, first, &h.tailCells[:1][0], "storage reallocated across seals")
82 // A reused backing array must not pin payload strings of sealed rows.
83 payload, err := renderer.NewCellPayload("é\u0301", "https://example.test")
84 require.NoError(t, err)
85 row := historyRow("abcd")
86 row[0].Payload = payload
87 for range 4 {
88 require.NoError(t, h.Append(row, LineBound{End: 4}))
89 }
90 for _, c := range h.tailCells[:cap(h.tailCells)] {
91 require.True(t, c.Payload.Empty())
92 }
93 require.NoError(t, h.chunks[len(h.chunks)-1].CheckInvariants())
94}
95
96// Default chunks of wide terminals (256 rows × 200 columns) must recycle their
97// tail storage too.
98func TestHistoryTailStorageIsRecycledForWideTerminals(t *testing.T) {
99 const width = 200
100 h := NewHistory(HistoryConfig{MaxRows: 4096, MaxBytes: 1 << 30})
101 row := make([]renderer.Cell, width)
102 for i := range row {
103 row[i] = renderer.Cell{Rune: 'w', Style: renderer.DefaultStyle()}
104 }
105 for range 256 {
106 require.NoError(t, h.Append(row, LineBound{End: width}))
107 }
108 require.Empty(t, h.tail)
109 require.GreaterOrEqual(t, cap(h.tailCells), 256*width, "seal released wide-terminal tail storage")
110}
111
112// Eviction from a partial tail must not leave the evicted rows' payload
113// strings pinned in the recycled backing array's prefix.
114func TestHistoryTailEvictionClearsEvictedPrefix(t *testing.T) {
115 payload, err := renderer.NewCellPayload("é\u0301", "https://example.test")
116 require.NoError(t, err)
117 rowFor := func(i int) []renderer.Cell {
118 row := historyRow("abcd")
119 row[i%4].Payload = payload
120 return row
121 }
122 // The byte budget evicts from the tail (ChunkRows is large, so it never
123 // seals); the 400-cell preallocation leaves room for many evictions in
124 // one backing array before it would be reallocated.
125 h := NewHistory(HistoryConfig{MaxRows: 100, MaxBytes: 1500, ChunkRows: 100})
126 require.NoError(t, h.Append(rowFor(0), LineBound{End: 4}))
127 orig := h.tailCells[:cap(h.tailCells)] // full original backing array
128 evicted := 0
129 for i := 1; i < 40 && len(h.chunks) == 0; i++ {
130 before := h.Len()
131 require.NoError(t, h.Append(rowFor(i), LineBound{End: 4}))
132 if cap(h.tailCells) > len(orig) || len(h.tailCells) == 0 {
133 break
134 }
135 liveStart := len(orig) - cap(h.tailCells)
136 if &orig[liveStart] != &h.tailCells[:1][0] {
137 break // storage was reallocated; the old array is no longer ours
138 }
139 if h.Len() <= before {
140 evicted++
141 }
142 liveEnd := liveStart + len(h.tailCells)
143 for j, c := range orig {
144 if j < liveStart || j >= liveEnd {
145 require.True(t, c.Payload.Empty(), "cell %d outside live window [%d,%d) pins payload", j, liveStart, liveEnd)
146 }
147 }
148 }
149 require.GreaterOrEqual(t, evicted, 2, "test did not exercise tail eviction")
150}
151
152// checkHistoryAccounting compares the incrementally maintained LogicalBytes
153// with (1) the sum of the live chunks' own metadata and (2) an independent
154// recomputation: every live chunk is rebuilt from its decoded rows with a
155// fresh newHistoryChunks call (no recycled scratch state). Logical bytes depend
156// on the page layout, so the reference keeps each chunk's boundaries.
157func checkHistoryAccounting(t *testing.T, h *History) {
158 t.Helper()
159 view := h.View()
160 require.Equal(t, historyChunksLogicalBytes(view.chunks), h.LogicalBytes(), "rows=%d", h.Len())
161 require.Equal(t, h.Len(), view.Len())
162 var rebuilt uint64
163 for _, c := range view.chunks {
164 rows := make([][]renderer.Cell, c.len())
165 for i := range rows {
166 rows[i] = c.row(i)
167 }
168 rebuilt += historyChunksLogicalBytes(newHistoryChunks(rows, c.bounds, c.rowIDs))
169 }
170 require.Equal(t, rebuilt, h.LogicalBytes(), "independent rebuild rows=%d", h.Len())
171}
172
173// Accounting must stay exact after seals recycle the style and payload sets,
174// through eviction, SetLimits shrinking, payload rows, width changes and pages
175// with more than maxRetainedStyleScratch distinct styles.
176func TestHistoryLogicalBytesIndependentOfSetReuse(t *testing.T) {
177 payload, err := renderer.NewCellPayload("x", "https://example.test")
178 require.NoError(t, err)
179 payload2, err := renderer.NewCellPayload("y", "")
180 require.NoError(t, err)
181 manyStyles := func(i int) []renderer.Cell { // 1100 distinct styles in one row
182 row := make([]renderer.Cell, 1100)
183 for x := range row {
184 row[x] = renderer.Cell{Rune: 'z', Style: renderer.Style{HasForegroundRGB: true, ForegroundRGB: renderer.RGB{R: uint8(x), G: uint8(x >> 8), B: uint8(i)}}}
185 }
186 return row
187 }
188 rowFor := func(i int) []renderer.Cell {
189 switch {
190 case i%11 == 5:
191 return manyStyles(i)
192 case i%4 == 0:
193 row := styledRow("abcd", i%7+1)
194 row[1].Payload = payload
195 row[2].Payload = payload2
196 return row
197 case i%3 == 0:
198 return styledRow("abcdef", i%5+1) // width change forces a new page
199 }
200 return styledRow("abcd", i%7+1)
201 }
202 for _, tc := range []struct {
203 name string
204 cfg HistoryConfig
205 }{
206 {"non-divisible chunks", HistoryConfig{MaxRows: 200, MaxBytes: 1 << 30, ChunkRows: 7}},
207 {"row eviction", HistoryConfig{MaxRows: 9, MaxBytes: 1 << 30, ChunkRows: 4}},
208 {"byte eviction", HistoryConfig{MaxRows: 200, MaxBytes: 30 << 10, ChunkRows: 5}},
209 {"tiny bytes", HistoryConfig{MaxRows: 200, MaxBytes: 1500, ChunkRows: 3}},
210 } {
211 t.Run(tc.name, func(t *testing.T) {
212 h := NewHistory(tc.cfg)
213 appendAt := func(i int) {
214 row := rowFor(i)
215 if err := h.Append(row, LineBound{End: len(row)}); err != nil {
216 require.ErrorIs(t, err, ErrHistoryRowTooLarge)
217 }
218 checkHistoryAccounting(t, h)
219 }
220 for i := range 60 {
221 appendAt(i)
222 }
223 shrunk := HistoryConfig{MaxRows: 5, MaxBytes: tc.cfg.MaxBytes, ChunkRows: 2}
224 require.NoError(t, h.SetLimits(shrunk))
225 checkHistoryAccounting(t, h)
226 for i := 60; i < 75; i++ {
227 appendAt(i)
228 }
229 })
230 }
231}
232
233// rowIDSet must accept and reject exactly what a plain map would, including
234// out-of-order IDs and duplicates across commits.
235func TestRowIDSetMatchesMap(t *testing.T) {
236 rng := rand.New(rand.NewSource(1))
237 for iter := 0; iter < 5000; iter++ {
238 var set rowIDSet
239 ref := map[RowID]struct{}{}
240 for commit := 0; commit < 1+rng.Intn(4); commit++ {
241 n := rng.Intn(6)
242 ids := make([]RowID, n)
243 base := RowID(rng.Intn(30))
244 for i := range ids {
245 if rng.Intn(3) == 0 {
246 ids[i] = RowID(1 + rng.Intn(30))
247 } else {
248 ids[i] = base + RowID(i) + 1
249 }
250 }
251 if rng.Intn(4) == 0 && n > 1 {
252 ids[0], ids[n-1] = ids[n-1], ids[0]
253 }
254 want := true
255 seen := map[RowID]struct{}{}
256 for _, id := range ids {
257 if _, dup := ref[id]; dup {
258 want = false
259 }
260 if _, dup := seen[id]; dup {
261 want = false
262 }
263 seen[id] = struct{}{}
264 }
265 set.reserve(n)
266 for _, id := range ids {
267 set.collect(id)
268 }
269 require.Equal(t, want, set.commit(), "iter %d ids %v", iter, ids)
270 if !want {
271 break
272 }
273 for _, id := range ids {
274 ref[id] = struct{}{}
275 }
276 }
277 }
278}
279
280func TestRestoreAcceptsOutOfOrderDistinctRowIDsAcrossBlobs(t *testing.T) {
281 src := NewHistory(HistoryConfig{MaxRows: 16, ChunkRows: 2})
282 for _, id := range []RowID{100, 7, 8, 9} {
283 require.NoError(t, src.AppendWithID(historyRow("abcd"), LineBound{End: 4}, id))
284 }
285 sealed, tail, err := MarshalSealedHistory(src.SealAndView())
286 require.NoError(t, err)
287 restored, err := HistoryFromBlobs(HistoryConfig{MaxRows: 16, ChunkRows: 2}, sealed, tail)
288 require.NoError(t, err)
289 require.Equal(t, 4, restored.Len())
290 // Same IDs in two blobs are still rejected, in either order.
291 _, err = HistoryFromBlobs(HistoryConfig{MaxRows: 16, ChunkRows: 2}, [][]byte{sealed[0], sealed[0]}, tail)
292 require.Error(t, err)
293 _, err = HistoryFromBlobs(HistoryConfig{MaxRows: 16, ChunkRows: 2}, [][]byte{sealed[1], sealed[0], sealed[1]}, tail)
294 require.Error(t, err)
295}
296
297// A chunk with more than maxRetainedStyleScratch styles must not leave its
298// large scratch map pinned, whether it is the last or an earlier chunk.
299func TestHistoryStyleScratchDroppedAfterHighCardinalityChunk(t *testing.T) {
300 row := make([]renderer.Cell, 1100)
301 for x := range row {
302 row[x] = renderer.Cell{Rune: 'z', Style: renderer.Style{HasForegroundRGB: true, ForegroundRGB: renderer.RGB{R: uint8(x), G: uint8(x >> 8), B: 1}}}
303 }
304 h := NewHistory(HistoryConfig{MaxRows: 100, MaxBytes: 1 << 30, ChunkRows: 4})
305 for range 4 { // seals one high-cardinality chunk
306 require.NoError(t, h.Append(row, LineBound{End: len(row)}))
307 }
308 require.LessOrEqual(t, len(h.styleRowScratch), maxRetainedStyleScratch)
309 require.LessOrEqual(t, len(h.tailPageStyles), maxRetainedStyleScratch+1)
310 for range 3 {
311 require.NoError(t, h.Append(historyRow("abcd"), LineBound{End: 4}))
312 }
313 _ = h.View()
314 require.LessOrEqual(t, len(h.styleRowScratch), maxRetainedStyleScratch)
315}
316
317// Early false returns from validation must not leak collected IDs into a later
318// commit.
319func TestRowIDSetBeginDiscardsUncommittedIDs(t *testing.T) {
320 var set rowIDSet
321 set.begin(0)
322 set.collect(1)
323 set.collect(2) // abandoned without commit, as on an early invalid return
324 set.begin(0)
325 set.collect(2)
326 require.True(t, set.commit())
327 set.begin(0)
328 set.collect(1)
329 require.True(t, set.commit())
330}