1package vt
2
3import (
4 "errors"
5 "math"
6 "slices"
7
8 renderer "github.com/bnema/vev-vt/core"
9)
10
11// ErrHistoryRowTooWide is returned when a row cannot fit within the configured
12// cell budget. The history is not modified when this error is returned.
13var ErrHistoryRowTooWide = errors.New("history row exceeds cell capacity")
14
15var errInvalidHistoryRowID = errors.New("invalid history row ID")
16
17// HistoryConfig controls the bounded terminal history retained by a Screen.
18type HistoryConfig struct {
19 MaxRows int
20 MaxCells int
21 ChunkRows int
22}
23
24// History stores terminal rows in immutable chunks. It is intended to be
25// mutated by the owner of a Screen; views are safe to retain after later
26// appends.
27type History struct {
28 maxRows int
29 maxCells int
30 chunkRows int
31 chunks []*HistoryChunk
32 tail [][]renderer.Cell
33 tailBounds []LineBound
34 tailIDs []RowID
35 rows int
36 cells int
37 nextRowID RowID
38}
39
40// HistoryChunk is an immutable group of history rows. Its identity is stable
41// and can be used by consumers to avoid copying unchanged sealed chunks.
42// bounds is parallel to rows and always has the same length.
43type HistoryChunk struct {
44 rows [][]renderer.Cell
45 bounds []LineBound
46 rowIDs []RowID
47}
48
49// HistoryView is an immutable snapshot of history. Row returns a copy so the
50// storage behind a sealed chunk remains owned by VT.
51type HistoryView struct {
52 chunks []*HistoryChunk
53 rows int
54 cells int
55 nextRowID RowID
56}
57
58// HistorySnapshotView captures sealed history chunks and the mutable tail
59// independently. Sealed chunks are shared by identity; Tail is owned by the
60// view and can be serialized without rotating the live tail into a chunk.
61type HistorySnapshotView struct {
62 chunks []*HistoryChunk
63 tail [][]renderer.Cell
64 tailBounds []LineBound
65 tailIDs []RowID
66 rows int
67 cells int
68 nextRowID RowID
69}
70
71func NewHistory(config HistoryConfig) *History {
72 if config.MaxRows <= 0 {
73 return &History{}
74 }
75 chunkRows := config.ChunkRows
76 if chunkRows <= 0 {
77 chunkRows = 256
78 }
79 chunkRows = min(chunkRows, 256)
80 chunkRows = min(chunkRows, config.MaxRows)
81 maxCells := config.MaxCells
82 if maxCells <= 0 {
83 maxCells = defaultHistoryMaxCells(config.MaxRows)
84 }
85 return &History{maxRows: config.MaxRows, maxCells: maxCells, chunkRows: chunkRows, nextRowID: 1}
86}
87
88func defaultHistoryMaxCells(maxRows int) int {
89 if maxRows > math.MaxInt/160 {
90 return math.MaxInt
91 }
92 return maxRows * 160
93}
94
95// Append records a copy of row along with its logical extent and an
96// automatically allocated nonzero ID. Once a chunk is full it is sealed
97// forever. Rows wider than the total cell capacity are rejected without
98// mutation.
99func (h *History) Append(row []renderer.Cell, bound LineBound) error {
100 if h == nil || h.maxRows == 0 {
101 return nil
102 }
103 if len(row) > h.maxCells {
104 return ErrHistoryRowTooWide
105 }
106 id, err := h.allocateRowID()
107 if err != nil {
108 return err
109 }
110 return h.appendRow(row, bound, id)
111}
112
113// AppendWithID records a copy of row with an explicit persisted identity.
114// Unlike Append, malformed identities are rejected rather than synthesized.
115func (h *History) AppendWithID(row []renderer.Cell, bound LineBound, id RowID) error {
116 if id == 0 || id >= ^RowID(0)-1 {
117 return errInvalidHistoryRowID
118 }
119 if h == nil || h.maxRows == 0 {
120 return nil
121 }
122 if len(row) > h.maxCells {
123 return ErrHistoryRowTooWide
124 }
125 if h.hasRowID(id) {
126 return errInvalidHistoryRowID
127 }
128 return h.appendRow(row, bound, id)
129}
130
131func (h *History) appendRow(row []renderer.Cell, bound LineBound, id RowID) error {
132 if h.nextRowID == ^RowID(0) {
133 return errInvalidHistoryRowID
134 }
135 if len(row) > h.maxCells {
136 return ErrHistoryRowTooWide
137 }
138 if id >= ^RowID(0)-1 {
139 return errInvalidHistoryRowID
140 }
141 if id >= h.nextRowID {
142 h.nextRowID = id + 1
143 }
144 // Make room before adding so Cells cannot overflow even when the default
145 // capacity is MaxInt.
146 h.evictFor(len(row))
147 h.tail = append(h.tail, append([]renderer.Cell(nil), row...))
148 h.tailBounds = append(h.tailBounds, clampBound(bound, len(row)))
149 h.tailIDs = append(h.tailIDs, id)
150 h.rows++
151 h.cells += len(row)
152 if len(h.tail) == h.chunkRows {
153 h.sealTail()
154 }
155 return nil
156}
157
158// allocateRowID relies on appendRow advancing nextRowID above every accepted
159// explicit ID; automatic IDs therefore never need to scan retained rows.
160func (h *History) allocateRowID() (RowID, error) {
161 if h.nextRowID == 0 {
162 h.nextRowID = 1
163 }
164 if h.nextRowID >= ^RowID(0)-1 {
165 return 0, errInvalidHistoryRowID
166 }
167 id := h.nextRowID
168 h.nextRowID++
169 return id, nil
170}
171
172func (h *History) hasRowID(id RowID) bool {
173 for _, chunk := range h.chunks {
174 if slices.Contains(chunk.rowIDs, id) {
175 return true
176 }
177 }
178 return slices.Contains(h.tailIDs, id)
179}
180
181// clampBound keeps End inside the row it describes so a persisted bound can be
182// validated without consulting its row again.
183func clampBound(b LineBound, cells int) LineBound {
184 b.End = min(max(b.End, 0), cells)
185 return b
186}
187
188// growBounds returns bounds sized to rows, padding with zero values. It keeps
189// the parallel-slice invariant when a chunk arrives with fewer bounds than rows.
190func growBounds(bounds []LineBound, rows int) []LineBound {
191 if len(bounds) == rows {
192 return bounds
193 }
194 out := make([]LineBound, rows)
195 copy(out, bounds)
196 return out
197}
198
199func growRowIDs(ids []RowID, rows int) []RowID {
200 if len(ids) == rows {
201 return ids
202 }
203 out := make([]RowID, rows)
204 copy(out, ids)
205 return out
206}
207
208func cloneRowIDs(ids []RowID, rows int) []RowID {
209 out := make([]RowID, rows)
210 copy(out, ids)
211 return out
212}
213
214func (h *History) sealTail() {
215 if len(h.tail) == 0 {
216 return
217 }
218 h.chunks = append(h.chunks, &HistoryChunk{
219 rows: h.tail,
220 bounds: growBounds(h.tailBounds, len(h.tail)),
221 rowIDs: h.tailIDs,
222 })
223 h.tail = nil
224 h.tailBounds = nil
225 h.tailIDs = nil
226}
227
228// normalizeTail seals complete chunks so the mutable tail remains shorter than
229// chunkRows. Restored snapshots may have been written with a different chunk
230// size than the current history configuration.
231func (h *History) normalizeTail() {
232 h.tailIDs = growRowIDs(h.tailIDs, len(h.tail))
233 for h.chunkRows > 0 && len(h.tail) >= h.chunkRows {
234 bounds := growBounds(h.tailBounds, len(h.tail))
235 h.chunks = append(h.chunks, &HistoryChunk{
236 rows: h.tail[:h.chunkRows],
237 bounds: bounds[:h.chunkRows],
238 rowIDs: h.tailIDs[:h.chunkRows],
239 })
240 h.tail = h.tail[h.chunkRows:]
241 h.tailBounds = bounds[h.chunkRows:]
242 h.tailIDs = h.tailIDs[h.chunkRows:]
243 }
244}
245
246func (h *History) evict() {
247 h.evictUntil(0, 0)
248}
249
250// evictFor discards oldest rows until another row using cellCount cells can fit.
251func (h *History) evictFor(cellCount int) {
252 h.evictUntil(1, cellCount)
253}
254
255// evictUntil makes room for rowCount rows and cellCount cells without
256// overflowing either accounting total.
257func (h *History) evictUntil(rowCount, cellCount int) {
258 for h.rows > h.maxRows-rowCount || h.cells > h.maxCells-cellCount {
259 if len(h.chunks) > 0 {
260 chunk := h.chunks[0]
261 row := chunk.rows[0]
262 h.rows--
263 h.cells -= len(row)
264 if len(chunk.rows) == 1 {
265 copy(h.chunks, h.chunks[1:])
266 h.chunks[len(h.chunks)-1] = nil
267 h.chunks = h.chunks[:len(h.chunks)-1]
268 } else {
269 // Preserve cell storage while replacing only the chunk wrapper: a
270 // retained view may still refer to the original immutable chunk.
271 bounds := growBounds(chunk.bounds, len(chunk.rows))
272 rowIDs := growRowIDs(chunk.rowIDs, len(chunk.rows))
273 h.chunks[0] = &HistoryChunk{
274 rows: chunk.rows[1:],
275 bounds: bounds[1:],
276 rowIDs: rowIDs[1:],
277 }
278 }
279 continue
280 }
281 if len(h.tail) == 0 {
282 return
283 }
284 row := h.tail[0]
285 h.rows--
286 h.cells -= len(row)
287 h.tail[0] = nil
288 h.tail = h.tail[1:]
289 h.tailBounds = growBounds(h.tailBounds, len(h.tail)+1)[1:]
290 h.tailIDs = growRowIDs(h.tailIDs, len(h.tail)+1)[1:]
291 }
292}
293
294// SealAndView rotates the mutable tail into an immutable chunk, then captures
295// the sealed chunks by identity. Callers must synchronize access to History.
296func (h *History) SealAndView() HistoryView {
297 if h != nil {
298 h.sealTail()
299 }
300 return h.View()
301}
302
303// View captures the current history. Sealed chunks are shared by identity; a
304// partially-filled tail is copied into a new immutable chunk for this view.
305func (h *History) View() HistoryView {
306 if h == nil {
307 return HistoryView{}
308 }
309 if h.rows == 0 {
310 return HistoryView{nextRowID: h.nextRowID}
311 }
312 chunks := make([]*HistoryChunk, len(h.chunks), len(h.chunks)+1)
313 copy(chunks, h.chunks)
314 if len(h.tail) > 0 {
315 chunks = append(chunks, &HistoryChunk{
316 rows: cloneHistoryRows(h.tail),
317 bounds: append([]LineBound(nil), growBounds(h.tailBounds, len(h.tail))...),
318 rowIDs: cloneRowIDs(h.tailIDs, len(h.tail)),
319 })
320 }
321 return HistoryView{chunks: chunks, rows: h.rows, cells: h.cells, nextRowID: h.nextRowID}
322}
323
324// SnapshotView captures history for persistence without sealing the mutable
325// tail. Sealed chunks are shared by identity and the tail is deeply copied.
326func (h *History) SnapshotView() HistorySnapshotView {
327 if h == nil {
328 return HistorySnapshotView{}
329 }
330 if h.rows == 0 {
331 return HistorySnapshotView{nextRowID: h.nextRowID}
332 }
333 return HistorySnapshotView{
334 chunks: append([]*HistoryChunk(nil), h.chunks...),
335 tail: cloneHistoryRows(h.tail),
336 tailBounds: append([]LineBound(nil), growBounds(h.tailBounds, len(h.tail))...),
337 tailIDs: cloneRowIDs(h.tailIDs, len(h.tail)),
338 rows: h.rows,
339 cells: h.cells,
340 nextRowID: h.nextRowID,
341 }
342}
343
344func cloneHistoryRows(rows [][]renderer.Cell) [][]renderer.Cell {
345 if len(rows) == 0 {
346 return nil
347 }
348 copyRows := make([][]renderer.Cell, len(rows))
349 for i, row := range rows {
350 copyRows[i] = append([]renderer.Cell(nil), row...)
351 }
352 return copyRows
353}
354
355// Len returns the currently retained history row count.
356func (h *History) Len() int {
357 if h == nil {
358 return 0
359 }
360 return h.rows
361}
362
363// Cells returns the currently retained history cell count.
364func (h *History) Cells() int {
365 if h == nil {
366 return 0
367 }
368 return h.cells
369}
370
371// NextRowID returns the next identity allocated by this history.
372func (h *History) NextRowID() RowID {
373 if h == nil || h.nextRowID == 0 {
374 return 1
375 }
376 return h.nextRowID
377}
378
379// Cap returns the configured bounded row capacity.
380func (h *History) Cap() int {
381 if h == nil {
382 return 0
383 }
384 return h.maxRows
385}
386
387// CellCap returns the configured bounded cell capacity.
388func (h *History) CellCap() int {
389 if h == nil {
390 return 0
391 }
392 return h.maxCells
393}
394
395func (v HistoryView) Len() int { return v.rows }
396func (v HistoryView) Cells() int { return v.cells }
397func (v HistoryView) ChunkCount() int { return len(v.chunks) }
398
399// NextRowID returns the next identity recorded by this view.
400func (v HistoryView) NextRowID() RowID {
401 if v.nextRowID == 0 {
402 next, ok := historyViewNextRowID(v)
403 if !ok {
404 return 1
405 }
406 return next
407 }
408 return v.nextRowID
409}
410
411// Chunk returns the immutable chunk at i, or nil when i is out of range.
412func (v HistoryView) Chunk(i int) *HistoryChunk {
413 if i < 0 || i >= len(v.chunks) {
414 return nil
415 }
416 return v.chunks[i]
417}
418
419// Range calls yield for each row in oldest-first order. The row is borrowed
420// immutable storage: yield must not mutate or retain it after returning.
421func (v HistoryView) Range(yield func([]renderer.Cell) bool) {
422 for _, chunk := range v.chunks {
423 for _, row := range chunk.rows {
424 if !yield(row) {
425 return
426 }
427 }
428 }
429}
430
431// Row returns a copy of the row at i, or nil when i is out of range.
432func (v HistoryView) Row(i int) []renderer.Cell {
433 return append([]renderer.Cell(nil), v.BorrowedRow(i)...)
434}
435
436// BorrowedRow returns immutable storage for the row at i, or nil when i is out
437// of range. The caller must not mutate or retain the result after it no longer
438// retains v. Consumers that need ownership should use Row instead.
439func (v HistoryView) BorrowedRow(i int) []renderer.Cell {
440 if i < 0 {
441 return nil
442 }
443 for _, chunk := range v.chunks {
444 if i < len(chunk.rows) {
445 return chunk.rows[i]
446 }
447 i -= len(chunk.rows)
448 }
449 return nil
450}
451
452// RowID returns the identity of the row at i, or zero when i is out of range.
453func (v HistoryView) RowID(i int) RowID {
454 if i < 0 {
455 return 0
456 }
457 for _, chunk := range v.chunks {
458 if i < len(chunk.rows) {
459 if i < len(chunk.rowIDs) {
460 return chunk.rowIDs[i]
461 }
462 return 0
463 }
464 i -= len(chunk.rows)
465 }
466 return 0
467}
468
469// FindRowID returns the oldest-first index of id, or -1 when id is absent.
470func (v HistoryView) FindRowID(id RowID) int {
471 if id == 0 {
472 return -1
473 }
474 index := 0
475 for _, chunk := range v.chunks {
476 for row := range chunk.rows {
477 if row < len(chunk.rowIDs) && chunk.rowIDs[row] == id {
478 return index
479 }
480 index++
481 }
482 }
483 return -1
484}
485
486// RowID returns the identity of the row within an immutable chunk.
487func (c *HistoryChunk) RowID(i int) RowID {
488 if c == nil || i < 0 || i >= len(c.rowIDs) {
489 return 0
490 }
491 return c.rowIDs[i]
492}
493
494// Bound returns the logical extent of the row at i, or the zero value when i is
495// out of range. A zero value describes a hard row whose End is not meaningful.
496func (v HistoryView) Bound(i int) LineBound {
497 if i < 0 {
498 return LineBound{}
499 }
500 for _, chunk := range v.chunks {
501 if i < len(chunk.rows) {
502 if i < len(chunk.bounds) {
503 return chunk.bounds[i]
504 }
505 return LineBound{}
506 }
507 i -= len(chunk.rows)
508 }
509 return LineBound{}
510}
511
512func (v HistorySnapshotView) Len() int { return v.rows }
513func (v HistorySnapshotView) Cells() int { return v.cells }
514func (v HistorySnapshotView) ChunkCount() int { return len(v.chunks) }
515
516// NextRowID returns the next identity recorded by this snapshot.
517func (v HistorySnapshotView) NextRowID() RowID {
518 if v.nextRowID == 0 {
519 return v.Tail().NextRowID()
520 }
521 return v.nextRowID
522}
523
524// Chunk returns a sealed immutable chunk at i, or nil when i is out of range.
525func (v HistorySnapshotView) Chunk(i int) *HistoryChunk {
526 if i < 0 || i >= len(v.chunks) {
527 return nil
528 }
529 return v.chunks[i]
530}
531
532// Tail returns an immutable view of the copied mutable tail.
533func (v HistorySnapshotView) Tail() HistoryView {
534 if len(v.tail) == 0 {
535 return HistoryView{nextRowID: v.nextRowID}
536 }
537 return HistoryView{
538 chunks: []*HistoryChunk{{rows: v.tail, bounds: growBounds(v.tailBounds, len(v.tail)), rowIDs: growRowIDs(v.tailIDs, len(v.tail))}},
539 rows: len(v.tail),
540 cells: historyRowsCells(v.tail),
541 nextRowID: v.nextRowID,
542 }
543}
544
545func historyRowsCells(rows [][]renderer.Cell) int {
546 cells := 0
547 for _, row := range rows {
548 cells += len(row)
549 }
550 return cells
551}