1package vt
2
3import (
4 "errors"
5 "fmt"
6 "math"
7 "slices"
8
9 renderer "github.com/bnema/vev-vt/core"
10)
11
12// ErrHistoryRowTooLarge is returned when one row cannot fit within the
13// configured logical-byte budget or compact page bounds. History is unchanged.
14var ErrHistoryRowTooLarge = errors.New("history row exceeds logical byte capacity")
15
16var errInvalidHistoryRowID = errors.New("invalid history row ID")
17
18const maxTailPreallocCells = 32 * 1024
19
20// maxRetainedTailCells bounds tail storage recycled across seals. It covers a
21// full default chunk of terminals up to 512 columns, so wide terminals reuse
22// their tail too, while rare very wide rows are still released.
23const maxRetainedTailCells = 4 * maxTailPreallocCells
24
25// History stores terminal rows in immutable chunks. It is intended to be
26// mutated by the owner of a Screen; views are safe to retain after later
27// appends.
28type History struct {
29 maxRows int
30 rowCeiling int
31 maxBytes uint64
32 byteCeiling uint64
33 chunkRows int
34 chunks []*HistoryChunk
35 tail [][]renderer.Cell
36 cachedTail []*HistoryChunk
37 tailCells []renderer.Cell
38 tailBounds []LineBound
39 tailIDs []RowID
40 tailBytes uint64
41 tailPageWidth int
42 tailPageRows int
43 tailPageStyles map[renderer.Style]struct{}
44 styleScratch styleSet
45 payloadScratch map[renderer.CellPayload]struct{}
46 tailPagePayloads map[renderer.CellPayload]struct{}
47 styleRowScratch map[renderer.Style]int
48 rows int
49 cells int
50 logicalBytes uint64
51 nextRowID RowID
52 compressionCursor int
53 // privateHead is the oldest sealed chunk's wrapper when it was created by
54 // eviction and no view has captured it since. Eviction may then advance it
55 // in place instead of allocating a new wrapper per evicted row.
56 privateHead *HistoryChunk
57}
58
59// HistoryChunk is an immutable compact slab of equal-width history rows. Its
60// identity is stable and can be used by consumers to reuse unchanged chunks.
61type HistoryChunk struct {
62 page *sealedPage
63 start int
64 count int
65 width int
66 bounds []LineBound
67 rowIDs []RowID
68 styleDrops []uint64
69 styleCount uint64
70 payloadDrops []uint64
71 payloadBytes uint64
72}
73
74func newHistoryChunks(rows [][]renderer.Cell, bounds []LineBound, rowIDs []RowID) []*HistoryChunk {
75 return newHistoryChunksScratch(rows, bounds, rowIDs, nil)
76}
77
78// maxRetainedStyleScratch bounds the style-set capacity kept between uses so
79// one pathological high-cardinality page cannot pin a large map forever.
80const maxRetainedStyleScratch = 1024
81
82// newHistoryChunksScratch is newHistoryChunks with an optional caller-owned
83// map (scratch may be nil) reused, cleared, across chunks instead of allocating
84// one per chunk. The map is replaced before any reuse if the previous chunk
85// grew it past maxRetainedStyleScratch, and dropped on return if the last one
86// did, so one high-cardinality chunk cannot pin a large map.
87func newHistoryChunksScratch(rows [][]renderer.Cell, bounds []LineBound, rowIDs []RowID, scratch *map[renderer.Style]int) []*HistoryChunk {
88 var local map[renderer.Style]int
89 if scratch == nil {
90 scratch = &local
91 }
92 defer func() {
93 if len(*scratch) > maxRetainedStyleScratch {
94 *scratch = nil
95 }
96 }()
97 bounds = growBounds(bounds, len(rows))
98 rowIDs = growRowIDs(rowIDs, len(rows))
99 var chunks []*HistoryChunk
100 for start := 0; start < len(rows); {
101 width := len(rows[start])
102 limit := start + min(len(rows)-start, maxHistorySlabRows(width))
103 end := start + 1
104 for end < limit && len(rows[end]) == width {
105 end++
106 }
107 frame := renderer.NewFrame(width, end-start)
108 if *scratch == nil || len(*scratch) > maxRetainedStyleScratch {
109 *scratch = make(map[renderer.Style]int)
110 } else {
111 clear(*scratch)
112 }
113 lastStyleRow := *scratch
114 defaultStyle := renderer.DefaultStyle()
115 for i := start; i < end; i++ {
116 frame.WriteRow(i-start, 0, rows[i])
117 // A run of identical raw styles canonicalizes identically and is
118 // already recorded for this row, so only the first cell of a run
119 // pays for Canonical and the map write.
120 var previous renderer.Style
121 for j, cell := range rows[i] {
122 if j > 0 && cell.Style == previous {
123 continue
124 }
125 previous = cell.Style
126 style := cell.Style.Canonical()
127 if style != defaultStyle {
128 lastStyleRow[style] = i - start
129 }
130 }
131 }
132 styleDrops := make([]uint64, end-start)
133 for _, row := range lastStyleRow {
134 styleDrops[row]++
135 }
136 chunks = append(chunks, &HistoryChunk{
137 page: newSealedPage(frame),
138 count: end - start,
139 width: width,
140 bounds: append([]LineBound(nil), bounds[start:end]...),
141 rowIDs: append([]RowID(nil), rowIDs[start:end]...),
142 styleDrops: styleDrops,
143 styleCount: uint64(len(lastStyleRow)) + 1,
144 })
145 chunks[len(chunks)-1].recordPayloads()
146 start = end
147 }
148 return chunks
149}
150
151func maxHistorySlabRows(width int) int {
152 if width <= 0 {
153 return math.MaxInt
154 }
155 rows := min(uint64(math.MaxUint32)/uint64(width), uint64(math.MaxInt))
156 return max(int(rows), 1)
157}
158
159func (c *HistoryChunk) len() int {
160 if c == nil {
161 return 0
162 }
163 return c.count
164}
165
166func (c *HistoryChunk) row(i int) []renderer.Cell {
167 if c == nil || i < 0 || i >= c.count {
168 return nil
169 }
170 return c.frameView().Row(c.start + i)
171}
172
173func (c *HistoryChunk) cell(row, column int) renderer.Cell {
174 return c.frameView().Cell(column, c.start+row)
175}
176
177func (c *HistoryChunk) cells() int { return c.count * c.width }
178
179// CheckInvariants validates one compact immutable history slab.
180func (c *HistoryChunk) CheckInvariants() error {
181 if c == nil || c.page == nil {
182 return fmt.Errorf("nil history chunk backing")
183 }
184 frame, err := c.page.readFrame(true)
185 if err != nil {
186 return err
187 }
188 if c.start < 0 || c.count <= 0 || c.width < 0 || c.start > frame.Height-c.count {
189 return fmt.Errorf("invalid history chunk range start=%d count=%d", c.start, c.count)
190 }
191 if frame.Width != c.width || len(c.bounds) != c.count || len(c.rowIDs) != c.count || len(c.styleDrops) != frame.Height {
192 return fmt.Errorf("history chunk metadata is not parallel")
193 }
194 styles := uint64(1)
195 for _, dropped := range c.styleDrops[c.start:] {
196 styles += dropped
197 }
198 if c.styleCount != styles {
199 return fmt.Errorf("history chunk style count = %d want %d", c.styleCount, styles)
200 }
201 var payloadBytes uint64
202 if len(c.payloadDrops) != 0 {
203 if len(c.payloadDrops) != frame.Height {
204 return fmt.Errorf("history payload metadata is not parallel")
205 }
206 for _, dropped := range c.payloadDrops[c.start:] {
207 payloadBytes += dropped
208 }
209 }
210 if payloadBytes != c.payloadBytes {
211 return fmt.Errorf("history payload accounting mismatch")
212 }
213 if err := frame.CheckInvariants(); err != nil {
214 return fmt.Errorf("history chunk frame: %w", err)
215 }
216 for i, id := range c.rowIDs {
217 if id == 0 || id >= ^RowID(0)-1 {
218 return fmt.Errorf("history row %d has invalid ID %d", i, id)
219 }
220 if !validHistoryBound(c.bounds[i], c.width) {
221 return fmt.Errorf("history row %d has invalid bound", i)
222 }
223 }
224 return nil
225}
226
227// HistoryView is an immutable snapshot of history. Row returns a copy so the
228// storage behind a sealed chunk remains owned by VT.
229type HistoryView struct {
230 chunks []*HistoryChunk
231 rows int
232 cells int
233 logicalBytes uint64
234 nextRowID RowID
235}
236
237// HistorySnapshotView captures sealed history chunks and the mutable tail
238// independently. Sealed chunks are shared by identity; Tail is owned by the
239// view and can be serialized without rotating the live tail into a chunk.
240type HistorySnapshotView struct {
241 chunks []*HistoryChunk
242 tail HistoryView
243 rows int
244 cells int
245 logicalBytes uint64
246 nextRowID RowID
247}
248
249func historyRowBaseLogicalBytes(width int) uint64 {
250 return uint64(width)*renderer.StoredCellLogicalBytes + renderer.RowDescriptorLogicalBytes
251}
252
253func addLogicalBytes(total, value uint64) uint64 {
254 if value > math.MaxUint64-total {
255 return math.MaxUint64
256 }
257 return total + value
258}
259
260func historyChunkLogicalBytes(chunk *HistoryChunk) uint64 {
261 if chunk == nil {
262 return 0
263 }
264 return uint64(chunk.len())*historyRowBaseLogicalBytes(chunk.width) + chunk.styleCount*renderer.StyleRecordLogicalBytes + chunk.payloadBytes
265}
266
267func historyChunksLogicalBytes(chunks []*HistoryChunk) uint64 {
268 var total uint64
269 for _, chunk := range chunks {
270 total = addLogicalBytes(total, historyChunkLogicalBytes(chunk))
271 }
272 return total
273}
274
275func (h *History) prepareRowStyles(row []renderer.Cell) uint64 {
276 clear(h.payloadScratch)
277 h.styleScratch.reset()
278 defaultStyle := renderer.DefaultStyle()
279 // A run of identical raw styles canonicalizes identically, so only the
280 // first cell of each run pays for Canonical and the set insert.
281 var previous renderer.Style
282 for i, cell := range row {
283 h.recordPayloadScratch(cell.Payload)
284 if i > 0 && cell.Style == previous {
285 continue
286 }
287 previous = cell.Style
288 if style := cell.Style.Canonical(); style != defaultStyle {
289 h.styleScratch.add(style)
290 }
291 }
292 return historyRowBaseLogicalBytes(len(row)) + renderer.StyleRecordLogicalBytes + uint64(h.styleScratch.len())*renderer.StyleRecordLogicalBytes + h.rowPayloadBytes()
293}
294
295func (h *History) prepareChunkRowStyles(chunk *HistoryChunk, row int) uint64 {
296 clear(h.payloadScratch)
297 h.styleScratch.reset()
298 defaultStyle := renderer.DefaultStyle()
299 for column := range chunk.width {
300 cell := chunk.cell(row, column)
301 h.recordPayloadScratch(cell.Payload)
302 if style := cell.Style.Canonical(); style != defaultStyle {
303 h.styleScratch.add(style)
304 }
305 }
306 return historyRowBaseLogicalBytes(chunk.width) + renderer.StyleRecordLogicalBytes + uint64(h.styleScratch.len())*renderer.StyleRecordLogicalBytes + h.rowPayloadBytes()
307}
308
309func (h *History) tailAppendDelta(width int) uint64 {
310 newPage := h.tailPageRows == 0 || h.tailPageWidth != width || h.tailPageRows >= maxHistorySlabRows(width)
311 delta := historyRowBaseLogicalBytes(width)
312 if newPage {
313 return delta + renderer.StyleRecordLogicalBytes + uint64(h.styleScratch.len())*renderer.StyleRecordLogicalBytes + h.rowPayloadBytes()
314 }
315 for style := range h.styleScratch.all() {
316 if _, ok := h.tailPageStyles[style]; !ok {
317 delta += renderer.StyleRecordLogicalBytes
318 }
319 }
320 for p := range h.payloadScratch {
321 if _, ok := h.tailPagePayloads[p]; !ok {
322 delta += p.LogicalBytes()
323 }
324 }
325 return delta
326}
327
328func (h *History) recordTailRowStyles(width int) {
329 if h.tailPageRows == 0 || h.tailPageWidth != width || h.tailPageRows >= maxHistorySlabRows(width) {
330 h.tailPageWidth = width
331 h.tailPageRows = 0
332 h.resetTailPageSets()
333 h.tailPageStyles[renderer.DefaultStyle()] = struct{}{}
334 }
335 for p := range h.payloadScratch {
336 if h.tailPagePayloads == nil {
337 h.tailPagePayloads = make(map[renderer.CellPayload]struct{})
338 }
339 h.tailPagePayloads[p] = struct{}{}
340 }
341 for style := range h.styleScratch.all() {
342 h.tailPageStyles[style] = struct{}{}
343 }
344 h.tailPageRows++
345}
346
347// resetTailPageSets empties the per-page style and payload sets, keeping their
348// storage for the next page unless a pathological page grew them past
349// maxRetainedStyleScratch. The style set is always non-nil afterwards.
350func (h *History) resetTailPageSets() {
351 if h.tailPageStyles == nil || len(h.tailPageStyles) > maxRetainedStyleScratch {
352 h.tailPageStyles = make(map[renderer.Style]struct{})
353 } else {
354 clear(h.tailPageStyles)
355 }
356 if len(h.tailPagePayloads) > maxRetainedStyleScratch {
357 h.tailPagePayloads = nil
358 } else {
359 clear(h.tailPagePayloads)
360 }
361}
362
363func (h *History) rebuildTailAccounting() {
364 old := h.tailBytes
365 h.tailBytes = 0
366 h.tailPageWidth = 0
367 h.tailPageRows = 0
368 h.resetTailPageSets()
369 for _, row := range h.tail {
370 h.prepareRowStyles(row)
371 delta := h.tailAppendDelta(len(row))
372 h.tailBytes += delta
373 h.recordTailRowStyles(len(row))
374 }
375 h.logicalBytes = h.logicalBytes - old + h.tailBytes
376}
377
378// Append records a copy of row along with its logical extent and an
379// automatically allocated nonzero ID. Once a chunk is full it is sealed
380// forever. Rows larger than the logical-byte capacity are rejected without
381// mutation.
382func (h *History) Append(row []renderer.Cell, bound LineBound) error {
383 if h == nil || h.maxRows == 0 {
384 return nil
385 }
386 defer func() { clear(h.payloadScratch) }()
387 if uint64(len(row)) > uint64(math.MaxUint32) || historyRowBaseLogicalBytes(len(row))+renderer.StyleRecordLogicalBytes > h.maxBytes || h.prepareRowStyles(row) > h.maxBytes {
388 return ErrHistoryRowTooLarge
389 }
390 id, err := h.allocateRowID()
391 if err != nil {
392 return err
393 }
394 return h.appendRow(row, bound, id)
395}
396
397// AppendWithID records a copy of row with an explicit persisted identity.
398// Unlike Append, malformed identities are rejected rather than synthesized.
399func (h *History) AppendWithID(row []renderer.Cell, bound LineBound, id RowID) error {
400 if id == 0 || id >= ^RowID(0)-1 {
401 return errInvalidHistoryRowID
402 }
403 if h == nil || h.maxRows == 0 {
404 return nil
405 }
406 defer func() { clear(h.payloadScratch) }()
407 if uint64(len(row)) > uint64(math.MaxUint32) || historyRowBaseLogicalBytes(len(row))+renderer.StyleRecordLogicalBytes > h.maxBytes || h.prepareRowStyles(row) > h.maxBytes {
408 return ErrHistoryRowTooLarge
409 }
410 if h.hasRowID(id) {
411 return errInvalidHistoryRowID
412 }
413 return h.appendRow(row, bound, id)
414}
415
416func (h *History) appendRow(row []renderer.Cell, bound LineBound, id RowID) error {
417 if h.nextRowID == ^RowID(0) {
418 return errInvalidHistoryRowID
419 }
420 if id >= ^RowID(0)-1 {
421 return errInvalidHistoryRowID
422 }
423 if id >= h.nextRowID {
424 h.nextRowID = id + 1
425 }
426 // Make room before adding so accounting cannot overflow even when the
427 // configured capacities use their maximum values.
428 h.evictFor(row)
429 delta := h.tailAppendDelta(len(row))
430 h.appendTailRow(row)
431 h.recordTailRowStyles(len(row))
432 h.tailBytes += delta
433 h.logicalBytes += delta
434 h.tailBounds = append(h.tailBounds, clampBound(bound, len(row)))
435 h.tailIDs = append(h.tailIDs, id)
436 h.rows++
437 h.cells += len(row)
438 if len(h.tail) == h.chunkRows {
439 h.sealTail()
440 }
441 return nil
442}
443
444// allocateRowID relies on appendRow advancing nextRowID above every accepted
445// explicit ID; automatic IDs therefore never need to scan retained rows.
446func (h *History) allocateRowID() (RowID, error) {
447 if h.nextRowID == 0 {
448 h.nextRowID = 1
449 }
450 if h.nextRowID >= ^RowID(0)-1 {
451 return 0, errInvalidHistoryRowID
452 }
453 id := h.nextRowID
454 h.nextRowID++
455 return id, nil
456}
457
458// hasRowID reports whether id is retained. Every retained ID is below
459// nextRowID (appendRow advances it and restore validates it), so the newest-ID
460// case used by screen eviction answers without scanning retained rows.
461func (h *History) hasRowID(id RowID) bool {
462 if id >= h.nextRowID {
463 return false
464 }
465 for _, chunk := range h.chunks {
466 if slices.Contains(chunk.rowIDs, id) {
467 return true
468 }
469 }
470 return slices.Contains(h.tailIDs, id)
471}
472
473// clampBound keeps End inside the row it describes so a persisted bound can be
474// validated without consulting its row again.
475func clampBound(b LineBound, cells int) LineBound {
476 b.End = min(max(b.End, 0), cells)
477 return b
478}
479
480// growBounds returns bounds sized to rows, padding with zero values. It keeps
481// the parallel-slice invariant when a chunk arrives with fewer bounds than rows.
482func growBounds(bounds []LineBound, rows int) []LineBound {
483 if len(bounds) == rows {
484 return bounds
485 }
486 out := make([]LineBound, rows)
487 copy(out, bounds)
488 return out
489}
490
491func growRowIDs(ids []RowID, rows int) []RowID {
492 if len(ids) == rows {
493 return ids
494 }
495 out := make([]RowID, rows)
496 copy(out, ids)
497 return out
498}
499
500func (h *History) reserveTailRow(width int) (start, end int) {
501 h.cachedTail = nil
502 start = len(h.tailCells)
503 end = start + width
504 if end > cap(h.tailCells) {
505 capacity := end
506 if cap(h.tailCells) <= (math.MaxInt-1)/2 {
507 capacity = max(capacity, cap(h.tailCells)*2)
508 }
509 if len(h.tailCells) == 0 {
510 prealloc := uint64(maxTailPreallocCells)
511 prealloc = min(prealloc, h.maxBytes/renderer.StoredCellLogicalBytes, uint64(width)*uint64(h.chunkRows))
512 capacity = max(capacity, max(width, int(prealloc)))
513 }
514 h.rebaseTail(capacity)
515 }
516 h.tailCells = h.tailCells[:end]
517 return start, end
518}
519
520// rebaseTail moves the mutable tail rows into fresh storage of the given
521// capacity (at least the used length) and re-slices every row into it.
522func (h *History) rebaseTail(capacity int) {
523 cells := make([]renderer.Cell, len(h.tailCells), capacity)
524 copy(cells, h.tailCells)
525 h.tailCells = cells
526 offset := 0
527 for i := range h.tail {
528 rowWidth := len(h.tail[i])
529 h.tail[i] = h.tailCells[offset : offset+rowWidth : offset+rowWidth]
530 offset += rowWidth
531 }
532}
533
534// trimIdleTail releases mutable-tail capacity beyond the rows it holds. Tail
535// cells use the wide semantic layout, so preallocated or recycled capacity is
536// the largest idle cost of a pane; the next append regrows it on demand.
537func (h *History) trimIdleTail() {
538 if cap(h.tailCells) == len(h.tailCells) {
539 return
540 }
541 if len(h.tailCells) == 0 {
542 h.tailCells = nil
543 return
544 }
545 h.rebaseTail(len(h.tailCells))
546}
547
548func (h *History) appendTailRow(row []renderer.Cell) {
549 start, end := h.reserveTailRow(len(row))
550 copy(h.tailCells[start:end], row)
551 h.tail = append(h.tail, h.tailCells[start:end:end])
552}
553
554func (h *History) appendTailChunkRow(chunk *HistoryChunk, row int) {
555 start, end := h.reserveTailRow(chunk.width)
556 for x := range chunk.width {
557 h.tailCells[start+x] = chunk.cell(row, x)
558 }
559 h.tail = append(h.tail, h.tailCells[start:end:end])
560}
561
562func (h *History) sealTail() {
563 if len(h.tail) == 0 {
564 return
565 }
566 chunks := h.tailViewChunks()
567 h.chunks = append(h.chunks, chunks...)
568 h.logicalBytes = h.logicalBytes - h.tailBytes + historyChunksLogicalBytes(chunks)
569 h.cachedTail = nil
570 // The sealed chunks hold compact copies (newHistoryChunks and the bounds and
571 // ID slices are copied), and no view, snapshot or callback ever receives
572 // h.tail rows or h.tailCells. The mutable-tail storage is therefore private
573 // and can be recycled for the next chunk instead of reallocated. Cells are
574 // cleared so recycled storage does not pin payload strings. Oversized
575 // storage (wide rows) is released as before.
576 clear(h.tail)
577 h.tail = h.tail[:0]
578 if cap(h.tailCells) > maxRetainedTailCells {
579 h.tailCells = nil
580 } else {
581 clear(h.tailCells)
582 h.tailCells = h.tailCells[:0]
583 }
584 h.tailBounds = h.tailBounds[:0]
585 h.tailIDs = h.tailIDs[:0]
586 h.tailBytes = 0
587 h.tailPageWidth = 0
588 h.tailPageRows = 0
589 // Sets are cleared lazily by the next page; release oversized ones now.
590 if len(h.tailPageStyles) > maxRetainedStyleScratch {
591 h.tailPageStyles = nil
592 }
593 if len(h.tailPagePayloads) > maxRetainedStyleScratch {
594 h.tailPagePayloads = nil
595 }
596}
597
598// evictFor discards oldest rows until row can fit both retention budgets.
599func (h *History) evictFor(row []renderer.Cell) {
600 for {
601 delta := h.tailAppendDelta(len(row))
602 if h.rows <= h.maxRows-1 && h.logicalBytes <= h.maxBytes-delta {
603 return
604 }
605 // Only a tail eviction rebuilds tail accounting, which reuses the row
606 // scratch; sealed-chunk eviction leaves this row's styles intact.
607 if h.evictOldest() {
608 h.prepareRowStyles(row)
609 }
610 }
611}
612
613// evictOldest drops the oldest retained row. It reports whether it rebuilt
614// tail accounting, which overwrites the row style and payload scratch.
615func (h *History) evictOldest() (scratchClobbered bool) {
616 if h.rows == 0 {
617 return false
618 }
619 if len(h.chunks) > 0 {
620 chunk := h.chunks[0]
621 oldBytes := historyChunkLogicalBytes(chunk)
622 h.rows--
623 h.cells -= chunk.width
624 if chunk.count == 1 {
625 if chunk == h.privateHead {
626 h.privateHead = nil
627 }
628 h.logicalBytes -= oldBytes
629 copy(h.chunks, h.chunks[1:])
630 h.chunks[len(h.chunks)-1] = nil
631 h.chunks = h.chunks[:len(h.chunks)-1]
632 } else {
633 // Preserve cell storage while replacing only the chunk wrapper: a
634 // retained view may still refer to the original immutable chunk. The
635 // wrapper tracks only styles still used by its retained suffix. A
636 // wrapper no view has seen is advanced in place.
637 if chunk == h.privateHead {
638 chunk.dropFirstRow()
639 } else {
640 h.chunks[0] = chunk.withoutFirstRow()
641 h.privateHead = h.chunks[0]
642 }
643 h.logicalBytes -= oldBytes - historyChunkLogicalBytes(h.chunks[0])
644 }
645 return false
646 }
647 if len(h.tail) == 0 {
648 return false
649 }
650 h.cachedTail = nil
651 row := h.tail[0]
652 h.rows--
653 h.cells -= len(row)
654 h.tail[0] = nil
655 h.tail = h.tail[1:]
656 // The evicted prefix stays in the recycled backing array; clear it so its
657 // payload strings are not pinned until the next seal.
658 clear(row)
659 h.tailCells = h.tailCells[len(row):]
660 h.tailBounds = growBounds(h.tailBounds, len(h.tail)+1)[1:]
661 h.tailIDs = growRowIDs(h.tailIDs, len(h.tail)+1)[1:]
662 h.rebuildTailAccounting()
663 return true
664}
665
666// SealAndView rotates the mutable tail into an immutable chunk, then captures
667// the sealed chunks by identity. Callers must synchronize access to History.
668func (h *History) SealAndView() HistoryView {
669 if h != nil {
670 h.sealTail()
671 }
672 return h.View()
673}
674
675func (h *History) tailViewChunks() []*HistoryChunk {
676 if h.cachedTail == nil && len(h.tail) > 0 {
677 h.cachedTail = newHistoryChunksScratch(h.tail, h.tailBounds, h.tailIDs, &h.styleRowScratch)
678 }
679 return h.cachedTail
680}
681
682// View captures the current history. Sealed chunks are shared by identity;
683// the immutable tail copy is reused until the mutable tail changes.
684func (h *History) View() HistoryView {
685 if h == nil {
686 return HistoryView{}
687 }
688 if h.rows == 0 {
689 return HistoryView{nextRowID: h.nextRowID}
690 }
691 h.privateHead = nil
692 chunks := make([]*HistoryChunk, len(h.chunks), len(h.chunks)+1)
693 copy(chunks, h.chunks)
694 if len(h.tail) > 0 {
695 chunks = append(chunks, h.tailViewChunks()...)
696 }
697 return HistoryView{chunks: chunks, rows: h.rows, cells: h.cells, logicalBytes: h.logicalBytes, nextRowID: h.nextRowID}
698}
699
700// SnapshotView captures history for persistence without sealing the mutable
701// tail. Sealed chunks are shared by identity and the tail is deeply copied.
702func (h *History) SnapshotView() HistorySnapshotView {
703 if h == nil {
704 return HistorySnapshotView{}
705 }
706 if h.rows == 0 {
707 return HistorySnapshotView{nextRowID: h.nextRowID}
708 }
709 h.privateHead = nil
710 tailChunks := newHistoryChunks(h.tail, h.tailBounds, h.tailIDs)
711 return HistorySnapshotView{
712 chunks: append([]*HistoryChunk(nil), h.chunks...),
713 tail: HistoryView{
714 chunks: tailChunks,
715 rows: len(h.tail),
716 cells: historyRowsCells(h.tail),
717 logicalBytes: historyChunksLogicalBytes(tailChunks),
718 nextRowID: h.nextRowID,
719 },
720 rows: h.rows,
721 cells: h.cells,
722 logicalBytes: h.logicalBytes,
723 nextRowID: h.nextRowID,
724 }
725}
726
727// Len returns the currently retained history row count.
728func (h *History) Len() int {
729 if h == nil {
730 return 0
731 }
732 return h.rows
733}
734
735// Cells returns the currently retained history cell count.
736func (h *History) Cells() int {
737 if h == nil {
738 return 0
739 }
740 return h.cells
741}
742
743// LogicalBytes returns deterministic uncompressed bytes retained by history.
744// It excludes the live primary and alternate screens and has no page allowance.
745func (h *History) LogicalBytes() uint64 {
746 if h == nil {
747 return 0
748 }
749 return h.logicalBytes
750}
751
752// NextRowID returns the next identity allocated by this history.
753func (h *History) NextRowID() RowID {
754 if h == nil || h.nextRowID == 0 {
755 return 1
756 }
757 return h.nextRowID
758}
759
760// Cap returns the configured row ceiling; zero means no independent row
761// ceiling, or disabled history when ByteCap is also zero.
762func (h *History) Cap() int {
763 if h == nil {
764 return 0
765 }
766 return h.rowCeiling
767}
768
769// ByteCap returns the configured uncompressed byte ceiling. Zero means no
770// independent byte ceiling, or disabled history when Cap is also zero.
771func (h *History) ByteCap() uint64 {
772 if h == nil {
773 return 0
774 }
775 return h.byteCeiling
776}
777
778func (v HistoryView) Len() int { return v.rows }
779func (v HistoryView) Cells() int { return v.cells }
780func (v HistoryView) LogicalBytes() uint64 {
781 if v.logicalBytes != 0 || len(v.chunks) == 0 {
782 return v.logicalBytes
783 }
784 return historyChunksLogicalBytes(v.chunks)
785}
786func (v HistoryView) ChunkCount() int { return len(v.chunks) }
787
788// NextRowID returns the next identity recorded by this view.
789func (v HistoryView) NextRowID() RowID {
790 if v.nextRowID == 0 {
791 next, ok := historyViewNextRowID(v)
792 if !ok {
793 return 1
794 }
795 return next
796 }
797 return v.nextRowID
798}
799
800// Chunk returns the immutable chunk at i, or nil when i is out of range.
801func (v HistoryView) Chunk(i int) *HistoryChunk {
802 if i < 0 || i >= len(v.chunks) {
803 return nil
804 }
805 return v.chunks[i]
806}
807
808// Range calls yield with a decoded owned row in oldest-first order. Returning
809// false stops iteration successfully; a backing restore failure returns an error.
810func (v HistoryView) Range(yield func([]renderer.Cell) bool) error {
811 for _, chunk := range v.chunks {
812 // Streaming search restores at most one transient page at a time and
813 // does not populate the random-access cache of every cold page.
814 frame, err := chunk.page.readFrame(false)
815 if err != nil {
816 return err
817 }
818 for i := range chunk.len() {
819 if !yield(frame.Row(chunk.start + i)) {
820 return nil
821 }
822 }
823 }
824 return nil
825}
826
827// Row returns a decoded owned copy of the row at i, or nil when out of range.
828func (v HistoryView) Row(i int) []renderer.Cell {
829 chunk, row := v.locateRow(i)
830 if chunk == nil {
831 return nil
832 }
833 return chunk.row(row)
834}
835
836// RowID returns the identity of the row at i, or zero when i is out of range.
837func (v HistoryView) RowID(i int) RowID {
838 if i < 0 {
839 return 0
840 }
841 for _, chunk := range v.chunks {
842 if i < chunk.len() {
843 if i < len(chunk.rowIDs) {
844 return chunk.rowIDs[i]
845 }
846 return 0
847 }
848 i -= chunk.len()
849 }
850 return 0
851}
852
853// FindRowID returns the oldest-first index of id, or -1 when id is absent.
854func (v HistoryView) FindRowID(id RowID) int {
855 if id == 0 {
856 return -1
857 }
858 index := 0
859 for _, chunk := range v.chunks {
860 for row := range chunk.len() {
861 if row < len(chunk.rowIDs) && chunk.rowIDs[row] == id {
862 return index
863 }
864 index++
865 }
866 }
867 return -1
868}
869
870// RowID returns the identity of the row within an immutable chunk.
871func (c *HistoryChunk) RowID(i int) RowID {
872 if c == nil || i < 0 || i >= len(c.rowIDs) {
873 return 0
874 }
875 return c.rowIDs[i]
876}
877
878// Bound returns the logical extent of the row at i, or the zero value when i is
879// out of range. A zero value describes a hard row whose End is not meaningful.
880func (v HistoryView) Bound(i int) LineBound {
881 if i < 0 {
882 return LineBound{}
883 }
884 for _, chunk := range v.chunks {
885 if i < chunk.len() {
886 if i < len(chunk.bounds) {
887 return chunk.bounds[i]
888 }
889 return LineBound{}
890 }
891 i -= chunk.len()
892 }
893 return LineBound{}
894}
895
896func (v HistorySnapshotView) Len() int { return v.rows }
897func (v HistorySnapshotView) Cells() int { return v.cells }
898func (v HistorySnapshotView) LogicalBytes() uint64 {
899 if v.logicalBytes != 0 || v.rows == 0 {
900 return v.logicalBytes
901 }
902 return addLogicalBytes(historyChunksLogicalBytes(v.chunks), v.tail.LogicalBytes())
903}
904func (v HistorySnapshotView) ChunkCount() int { return len(v.chunks) }
905
906// NextRowID returns the next identity recorded by this snapshot.
907func (v HistorySnapshotView) NextRowID() RowID {
908 if v.nextRowID == 0 {
909 return v.Tail().NextRowID()
910 }
911 return v.nextRowID
912}
913
914// Chunk returns a sealed immutable chunk at i, or nil when i is out of range.
915func (v HistorySnapshotView) Chunk(i int) *HistoryChunk {
916 if i < 0 || i >= len(v.chunks) {
917 return nil
918 }
919 return v.chunks[i]
920}
921
922// Tail returns an immutable view of the copied mutable tail.
923func (v HistorySnapshotView) Tail() HistoryView {
924 tail := v.tail
925 tail.nextRowID = v.nextRowID
926 return tail
927}
928
929func historyRowsCells(rows [][]renderer.Cell) int {
930 cells := 0
931 for _, row := range rows {
932 cells += len(row)
933 }
934 return cells
935}