1package vt
2
3import (
4 "encoding/binary"
5 "errors"
6 "fmt"
7 "math"
8 "slices"
9 "unicode/utf8"
10
11 renderer "github.com/bnema/vev-vt/core"
12)
13
14const (
15 historyMagic = "VTH1"
16 historyVersion = 3
17 historyCellBytes = 41
18 historyBoundBytes = 5
19 maxHistoryChunkRows = 256
20
21 // The daemon retains 10,000 history rows. Support a 20% row margin and
22 // 160-cell rows, which leaves headroom above the representative 10k×120
23 // terminal while bounding snapshot allocation.
24 maxHistoryChunks = 12_000
25 maxHistoryRows = 12_000
26 maxHistoryRowCells = 160
27 maxHistoryCells = maxHistoryRows * maxHistoryRowCells
28
29 maxHistoryDecodeStyles = maxHistoryCells
30 maxHistoryDecodedBytes = maxHistoryCells * historyCellBytes
31)
32
33var errInvalidHistory = errors.New("invalid history payload")
34
35// MarshalHistory encodes a HistoryView in a deterministic, self-contained
36// format. It preserves chunk boundaries as well as every Cell and Style field.
37func MarshalHistory(view HistoryView) ([]byte, error) {
38 if view.rows < 0 || view.rows != historyViewRowCount(view) || uint64(len(view.chunks)) > math.MaxUint32 || uint64(len(view.chunks)) > maxHistoryChunks {
39 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
40 }
41 nextRowID, ok := historyViewNextRowID(view)
42 if !ok {
43 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
44 }
45 stats := historyDecodeStats{}
46 seen := make(map[RowID]struct{}, view.rows)
47 for _, chunk := range view.chunks {
48 if chunk == nil || len(chunk.rows) == 0 || len(chunk.rows) != len(chunk.rowIDs) || len(chunk.rows) > maxHistoryChunkRows ||
49 !addHistoryDecodeBudget(&stats.rows, uint64(len(chunk.rows)), maxHistoryRows) {
50 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
51 }
52 for i, row := range chunk.rows {
53 if uint64(len(row)) > math.MaxUint32 {
54 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
55 }
56 id := chunk.rowIDs[i]
57 if id == 0 || id >= ^RowID(0)-1 {
58 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
59 }
60 if _, duplicate := seen[id]; duplicate {
61 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
62 }
63 seen[id] = struct{}{}
64 cellCount := uint64(len(row))
65 cellBytes, ok := historyCellByteCount(cellCount)
66 if !ok ||
67 !addHistoryDecodeBudget(&stats.cells, cellCount, maxHistoryCells) ||
68 !addHistoryDecodeBudget(&stats.styles, cellCount, maxHistoryDecodeStyles) ||
69 !addHistoryDecodeBudget(&stats.bytes, cellBytes, maxHistoryDecodedBytes) {
70 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
71 }
72 bound := chunkBound(chunk, i)
73 if !validHistoryBound(bound, len(row)) {
74 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
75 }
76 for _, cell := range row {
77 if !validHistoryCell(cell) {
78 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
79 }
80 }
81 }
82 }
83 if nextRowID <= maxHistoryRowID(seen) {
84 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
85 }
86
87 out := make([]byte, 0, 17)
88 out = append(out, historyMagic...)
89 out = append(out, historyVersion)
90 out = appendUint32(out, uint32(len(view.chunks)))
91 out = binary.BigEndian.AppendUint64(out, uint64(nextRowID))
92 for _, chunk := range view.chunks {
93 out = appendUint32(out, uint32(len(chunk.rows)))
94 for i, row := range chunk.rows {
95 out = binary.BigEndian.AppendUint64(out, uint64(chunk.rowIDs[i]))
96 out = appendUint32(out, uint32(len(row)))
97 for _, cell := range row {
98 out = appendHistoryCell(out, cell)
99 }
100 out = appendHistoryBound(out, chunkBound(chunk, i))
101 }
102 }
103 return out, nil
104}
105
106func historyViewNextRowID(view HistoryView) (RowID, bool) {
107 seen := make(map[RowID]struct{}, view.rows)
108 for _, chunk := range view.chunks {
109 if chunk == nil || len(chunk.rows) != len(chunk.rowIDs) {
110 return 0, false
111 }
112 for _, id := range chunk.rowIDs {
113 if id == 0 || id >= ^RowID(0)-1 {
114 return 0, false
115 }
116 if _, duplicate := seen[id]; duplicate {
117 return 0, false
118 }
119 seen[id] = struct{}{}
120 }
121 }
122 next := view.nextRowID
123 if next == 0 {
124 maxID := maxHistoryRowID(seen)
125 if maxID == ^RowID(0) {
126 return 0, false
127 }
128 next = maxID + 1
129 }
130 if next == 0 || next == ^RowID(0) || next <= maxHistoryRowID(seen) {
131 return 0, false
132 }
133 return next, true
134}
135
136func maxHistoryRowID(ids map[RowID]struct{}) RowID {
137 var maxID RowID
138 for id := range ids {
139 if id > maxID {
140 maxID = id
141 }
142 }
143 return maxID
144}
145
146func historyViewRowCount(view HistoryView) int {
147 n := 0
148 for _, chunk := range view.chunks {
149 if chunk != nil && len(chunk.rows) <= math.MaxInt-n {
150 n += len(chunk.rows)
151 continue
152 }
153 return -1
154 }
155 return n
156}
157
158func appendUint32(dst []byte, v uint32) []byte {
159 return binary.BigEndian.AppendUint32(dst, v)
160}
161
162func appendHistoryCell(dst []byte, cell renderer.Cell) []byte {
163 style := cell.Style
164 dst = binary.BigEndian.AppendUint32(dst, uint32(cell.Rune))
165 flags := byte(0)
166 if cell.Continuation {
167 flags |= 1 << 0
168 }
169 if style.Bold {
170 flags |= 1 << 1
171 }
172 if style.Italic {
173 flags |= 1 << 2
174 }
175 if style.Inverse {
176 flags |= 1 << 3
177 }
178 if style.HasForegroundRGB {
179 flags |= 1 << 4
180 }
181 if style.HasBackgroundRGB {
182 flags |= 1 << 5
183 }
184 if style.HasUnderlineColor {
185 flags |= 1 << 6
186 }
187 if style.HasUnderlineColorRGB {
188 flags |= 1 << 7
189 }
190 dst = append(dst, flags)
191 dst = binary.BigEndian.AppendUint16(dst, uint16(style.Attrs))
192 dst = binary.BigEndian.AppendUint64(dst, uint64(int64(style.Foreground)))
193 dst = binary.BigEndian.AppendUint64(dst, uint64(int64(style.Background)))
194 dst = append(dst, style.ForegroundRGB.R, style.ForegroundRGB.G, style.ForegroundRGB.B)
195 dst = append(dst, style.BackgroundRGB.R, style.BackgroundRGB.G, style.BackgroundRGB.B)
196 dst = append(dst, byte(style.UnderlineStyle))
197 dst = binary.BigEndian.AppendUint64(dst, uint64(int64(style.UnderlineColor)))
198 return append(dst, style.UnderlineColorRGB.R, style.UnderlineColorRGB.G, style.UnderlineColorRGB.B)
199}
200
201func chunkBound(chunk *HistoryChunk, i int) LineBound {
202 if i < 0 || i >= len(chunk.bounds) {
203 return LineBound{}
204 }
205 return chunk.bounds[i]
206}
207
208func appendHistoryBound(dst []byte, b LineBound) []byte {
209 dst = binary.BigEndian.AppendUint32(dst, uint32(b.End))
210 if b.Soft {
211 return append(dst, 1)
212 }
213 return append(dst, 0)
214}
215
216// validHistoryBound rejects extents that cannot describe their own row.
217func validHistoryBound(b LineBound, cells int) bool {
218 return b.End >= 0 && b.End <= cells
219}
220
221// UnmarshalHistory strictly decodes a MarshalHistory payload. It rejects
222// malformed declarations, cells, truncated data, and trailing bytes.
223func UnmarshalHistory(data []byte) (HistoryView, error) {
224 view, _, ok := parseHistory(data, true)
225 if !ok {
226 return HistoryView{}, fmt.Errorf("unmarshal history: %w", errInvalidHistory)
227 }
228 return view, nil
229}
230
231type historyDecodeStats struct {
232 chunks uint64
233 rows uint64
234 cells uint64
235 styles uint64
236 bytes uint64
237}
238
239// preflightHistory validates a history blob without allocating decoded rows.
240// It shares parseHistory with UnmarshalHistory so both paths enforce the same
241// structural, cell, and aggregate-budget constraints.
242func preflightHistory(data []byte) (historyDecodeStats, bool) {
243 _, stats, ok := parseHistory(data, false)
244 return stats, ok
245}
246
247// parseHistory is the authoritative history payload validation path. populate
248// controls whether validated cells are retained in a HistoryView.
249func parseHistory(data []byte, populate bool) (HistoryView, historyDecodeStats, bool) {
250 if len(data) < 17 || string(data[:4]) != historyMagic || data[4] != historyVersion {
251 return HistoryView{}, historyDecodeStats{}, false
252 }
253
254 p := historyParser{data: data[5:]}
255 chunkCount, ok := p.uint32()
256 if !ok || uint64(chunkCount) > maxHistoryChunks || uint64(chunkCount) > uint64(len(p.data))/4 {
257 return HistoryView{}, historyDecodeStats{}, false
258 }
259 nextRowID, ok := p.uint64()
260 if !ok || nextRowID == 0 || nextRowID == uint64(^RowID(0)) {
261 return HistoryView{}, historyDecodeStats{}, false
262 }
263 stats := historyDecodeStats{chunks: uint64(chunkCount)}
264 var seenIDs [maxHistoryRows]RowID
265 seenCount := 0
266 var maxID RowID
267 var chunks []*HistoryChunk
268 if populate {
269 chunks = make([]*HistoryChunk, 0, chunkCount)
270 }
271 for range chunkCount {
272 rowCount, ok := p.uint32()
273 if !ok || rowCount == 0 || rowCount > maxHistoryChunkRows ||
274 uint64(rowCount) > uint64(len(p.data))/(8+4+historyBoundBytes) ||
275 !addHistoryDecodeBudget(&stats.rows, uint64(rowCount), maxHistoryRows) {
276 return HistoryView{}, historyDecodeStats{}, false
277 }
278
279 var rows [][]renderer.Cell
280 var bounds []LineBound
281 var rowIDs []RowID
282 if populate {
283 rows = make([][]renderer.Cell, 0, rowCount)
284 bounds = make([]LineBound, 0, rowCount)
285 rowIDs = make([]RowID, 0, rowCount)
286 }
287 for range rowCount {
288 id, ok := p.uint64()
289 if !ok || id == 0 || id >= uint64(^RowID(0)-1) {
290 return HistoryView{}, historyDecodeStats{}, false
291 }
292 rowID := RowID(id)
293 seenIDs[seenCount] = rowID
294 seenCount++
295 if rowID > maxID {
296 maxID = rowID
297 }
298 cellCount, ok := p.uint32()
299 cellBytes, validCellBytes := historyCellByteCount(uint64(cellCount))
300 if !ok || !validCellBytes ||
301 !addHistoryDecodeBudget(&stats.cells, uint64(cellCount), maxHistoryCells) ||
302 !addHistoryDecodeBudget(&stats.styles, uint64(cellCount), maxHistoryDecodeStyles) ||
303 !addHistoryDecodeBudget(&stats.bytes, cellBytes, maxHistoryDecodedBytes) ||
304 uint64(cellCount) > uint64(len(p.data))/historyCellBytes {
305 return HistoryView{}, historyDecodeStats{}, false
306 }
307
308 var row []renderer.Cell
309 if populate {
310 row = make([]renderer.Cell, cellCount)
311 }
312 for i := range cellCount {
313 cell, ok := p.cell()
314 if !ok || !validHistoryCell(cell) {
315 return HistoryView{}, historyDecodeStats{}, false
316 }
317 if populate {
318 row[i] = cell
319 }
320 }
321 bound, ok := p.bound()
322 if !ok || !validHistoryBound(bound, int(cellCount)) {
323 return HistoryView{}, historyDecodeStats{}, false
324 }
325 if populate {
326 rows = append(rows, row)
327 bounds = append(bounds, bound)
328 rowIDs = append(rowIDs, rowID)
329 }
330 }
331 if populate {
332 chunks = append(chunks, &HistoryChunk{rows: rows, bounds: bounds, rowIDs: rowIDs})
333 }
334 }
335 slices.Sort(seenIDs[:seenCount])
336 for i := 1; i < seenCount; i++ {
337 if seenIDs[i] == seenIDs[i-1] {
338 return HistoryView{}, historyDecodeStats{}, false
339 }
340 }
341 if len(p.data) != 0 || RowID(nextRowID) <= maxID {
342 return HistoryView{}, historyDecodeStats{}, false
343 }
344 return HistoryView{chunks: chunks, rows: int(stats.rows), cells: int(stats.cells), nextRowID: RowID(nextRowID)}, stats, true
345}
346
347func historyCellByteCount(cellCount uint64) (uint64, bool) {
348 if cellCount > math.MaxUint64/historyCellBytes {
349 return 0, false
350 }
351 return cellCount * historyCellBytes, true
352}
353
354func addHistoryDecodeBudget(total *uint64, amount, limit uint64) bool {
355 if *total > limit || amount > limit-*total {
356 return false
357 }
358 *total += amount
359 return true
360}
361
362type historyParser struct{ data []byte }
363
364func (p *historyParser) uint32() (uint32, bool) {
365 if len(p.data) < 4 {
366 return 0, false
367 }
368 v := binary.BigEndian.Uint32(p.data)
369 p.data = p.data[4:]
370 return v, true
371}
372
373func (p *historyParser) uint64() (uint64, bool) {
374 if len(p.data) < 8 {
375 return 0, false
376 }
377 v := binary.BigEndian.Uint64(p.data)
378 p.data = p.data[8:]
379 return v, true
380}
381
382func (p *historyParser) cell() (renderer.Cell, bool) {
383 if len(p.data) < historyCellBytes {
384 return renderer.Cell{}, false
385 }
386 b := p.data[:historyCellBytes]
387 p.data = p.data[historyCellBytes:]
388 foreground, ok := historyInt(binary.BigEndian.Uint64(b[7:15]))
389 if !ok {
390 return renderer.Cell{}, false
391 }
392 background, ok := historyInt(binary.BigEndian.Uint64(b[15:23]))
393 if !ok {
394 return renderer.Cell{}, false
395 }
396 underlineColor, ok := historyInt(binary.BigEndian.Uint64(b[30:38]))
397 if !ok {
398 return renderer.Cell{}, false
399 }
400 flags := b[4]
401 return renderer.Cell{
402 Rune: rune(binary.BigEndian.Uint32(b[0:4])),
403 Continuation: flags&1 != 0,
404 Style: renderer.Style{
405 Bold: flags&(1<<1) != 0,
406 Italic: flags&(1<<2) != 0,
407 Inverse: flags&(1<<3) != 0,
408 Attrs: renderer.StyleAttrs(binary.BigEndian.Uint16(b[5:7])),
409 Foreground: foreground,
410 Background: background,
411 HasForegroundRGB: flags&(1<<4) != 0,
412 ForegroundRGB: renderer.RGB{R: b[23], G: b[24], B: b[25]},
413 HasBackgroundRGB: flags&(1<<5) != 0,
414 BackgroundRGB: renderer.RGB{R: b[26], G: b[27], B: b[28]},
415 UnderlineStyle: renderer.UnderlineStyle(b[29]),
416 HasUnderlineColor: flags&(1<<6) != 0,
417 UnderlineColor: underlineColor,
418 HasUnderlineColorRGB: flags&(1<<7) != 0,
419 UnderlineColorRGB: renderer.RGB{R: b[38], G: b[39], B: b[40]},
420 },
421 }, true
422}
423
424func (p *historyParser) bound() (LineBound, bool) {
425 if len(p.data) < historyBoundBytes {
426 return LineBound{}, false
427 }
428 end := binary.BigEndian.Uint32(p.data[:4])
429 flag := p.data[4]
430 p.data = p.data[historyBoundBytes:]
431 if flag > 1 || uint64(end) > math.MaxInt32 {
432 return LineBound{}, false
433 }
434 return LineBound{End: int(end), Soft: flag == 1}, true
435}
436
437func historyInt(raw uint64) (int, bool) {
438 v := int64(raw)
439 if int64(int(v)) != v {
440 return 0, false
441 }
442 return int(v), true
443}
444
445func validHistoryCell(cell renderer.Cell) bool {
446 return utf8.ValidRune(cell.Rune) && cell.Style.UnderlineStyle <= renderer.UnderlineDashed
447}