1package vt
2
3import (
4 "encoding/binary"
5 "errors"
6 "fmt"
7 "math"
8
9 renderer "github.com/bnema/vev-vt/core"
10)
11
12const (
13 historyMagic = "VTC1"
14 historyHeaderBytes = 16
15 historyChunkHeaderBytes = 16
16 historyStoredCellBytes = 9
17 historyStyleBytes = 37
18 historyRowBytes = 13
19 historyBoundBytes = 5
20 maxHistoryChunkRows = 256
21
22 // Aggregate resource ceilings allow wide rows without tying persistence to
23 // a particular terminal geometry. They apply before compact allocation.
24 maxHistoryChunks = 12_000
25 maxHistoryRows = 12_000
26 maxHistoryRowCells = 160
27 maxHistoryCells = maxHistoryRows * maxHistoryRowCells
28 maxHistoryStylesPerChunk = maxHistoryCells + 1
29 maxHistoryDecodeStyles = maxHistoryCells + maxHistoryChunks
30 maxHistoryPayloadBytes = 64 << 20
31 maxHistoryDecodedBytes = maxHistoryCells*renderer.StoredCellLogicalBytes +
32 maxHistoryRows*renderer.RowDescriptorLogicalBytes +
33 maxHistoryDecodeStyles*renderer.StyleRecordLogicalBytes + maxHistoryPayloadBytes
34)
35
36var errInvalidHistory = errors.New("invalid history payload")
37
38type historyDecodeStats struct {
39 chunks, rows, cells, styles, bytes uint64
40 payloadBytes uint64
41}
42
43// MarshalHistory serializes semantic cells with canonical chunk-local style
44// dictionaries. Internal style IDs and page memory never cross this boundary.
45func MarshalHistory(view HistoryView) ([]byte, error) {
46 if view.rows < 0 || view.rows > maxHistoryRows || view.rows != historyViewRowCount(view) || len(view.chunks) > maxHistoryChunks {
47 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
48 }
49 nextID, ok := historyViewNextRowID(view)
50 if !ok {
51 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
52 }
53 type encodedChunk struct {
54 chunk *HistoryChunk
55 styles []renderer.Style
56 ids map[renderer.Style]uint32
57 payloads []renderer.CellPayload
58 payloadIDs map[renderer.CellPayload]uint32
59 }
60 encoded := make([]encodedChunk, 0, len(view.chunks))
61 size := uint64(historyHeaderBytes)
62 stats := historyDecodeStats{chunks: uint64(len(view.chunks))}
63 for _, chunk := range view.chunks {
64 if chunk == nil || chunk.page == nil || chunk.len() == 0 || chunk.len() > maxHistoryChunkRows ||
65 chunk.len() != len(chunk.rowIDs) || chunk.len() != len(chunk.bounds) || chunk.width < 0 ||
66 uint64(chunk.width) > math.MaxUint32 {
67 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
68 }
69 cells := uint64(chunk.width) * uint64(chunk.len())
70 if !addHistoryDecodeBudget(&stats.rows, uint64(chunk.len()), maxHistoryRows) ||
71 !addHistoryDecodeBudget(&stats.cells, cells, maxHistoryCells) {
72 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
73 }
74 frame, err := chunk.page.readFrame(false)
75 if err != nil {
76 return nil, fmt.Errorf("marshal history: %w", err)
77 }
78 if frame.Width != chunk.width || chunk.start < 0 || chunk.start > frame.Height-chunk.count {
79 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
80 }
81 styles := []renderer.Style{renderer.DefaultStyle()}
82 ids := map[renderer.Style]uint32{renderer.DefaultStyle(): 0}
83 var payloads []renderer.CellPayload
84 var payloadIDs map[renderer.CellPayload]uint32
85 var payloadWireBytes uint64
86 for row := range chunk.len() {
87 if !validHistoryBound(chunk.bounds[row], chunk.width) {
88 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
89 }
90 for x := range chunk.width {
91 cell := frame.Cell(x, chunk.start+row)
92 if !validHistoryCell(cell) {
93 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
94 }
95 if !cell.Payload.Empty() {
96 payloadWireBytes += 4 // The handle is present only for exceptional cells.
97 if payloadIDs == nil {
98 payloadIDs = make(map[renderer.CellPayload]uint32)
99 }
100 if _, exists := payloadIDs[cell.Payload]; !exists {
101 n := cell.Payload.LogicalBytes()
102 if !addHistoryDecodeBudget(&stats.payloadBytes, n, maxHistoryPayloadBytes) || !addHistoryDecodeBudget(&stats.bytes, n, maxHistoryDecodedBytes) {
103 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
104 }
105 payloads = append(payloads, cell.Payload)
106 payloadIDs[cell.Payload] = uint32(len(payloads))
107 payloadWireBytes += 8 + uint64(len(cell.Payload.Grapheme())+len(cell.Payload.Hyperlink()))
108 }
109 }
110 style := cell.Style.Canonical()
111 if _, exists := ids[style]; !exists {
112 ids[style] = uint32(len(styles))
113 styles = append(styles, style)
114 }
115 }
116 }
117 if !addHistoryDecodeBudget(&stats.styles, uint64(len(styles)), maxHistoryDecodeStyles) ||
118 !addHistoryLogicalBytes(&stats, cells, uint64(chunk.len()), uint64(len(styles))) {
119 return nil, fmt.Errorf("marshal history: %w", errInvalidHistory)
120 }
121 size += historyChunkHeaderBytes + uint64(len(styles)-1)*historyStyleBytes + uint64(chunk.len())*historyRowBytes + cells*historyStoredCellBytes + payloadWireBytes
122 encoded = append(encoded, encodedChunk{chunk: chunk, styles: styles, ids: ids, payloads: payloads, payloadIDs: payloadIDs})
123 }
124 // Aggregate budgets bound size well below MaxInt even on 32-bit hosts.
125 out := make([]byte, 0, int(size))
126 out = append(out, historyMagic...)
127 out = binary.BigEndian.AppendUint32(out, uint32(len(encoded)))
128 out = binary.BigEndian.AppendUint64(out, uint64(nextID))
129 for _, entry := range encoded {
130 chunk, styles, ids := entry.chunk, entry.styles, entry.ids
131 frame, err := chunk.page.readFrame(false)
132 if err != nil {
133 return nil, fmt.Errorf("marshal history: %w", err)
134 }
135 out = binary.BigEndian.AppendUint32(out, uint32(chunk.width))
136 out = binary.BigEndian.AppendUint32(out, uint32(chunk.len()))
137 out = binary.BigEndian.AppendUint32(out, uint32(len(styles)))
138 out = binary.BigEndian.AppendUint32(out, uint32(len(entry.payloads)))
139 for _, style := range styles[1:] {
140 out = appendHistoryStyle(out, style)
141 }
142 for _, p := range entry.payloads {
143 out = appendHistoryPayload(out, p)
144 }
145 for row, id := range chunk.rowIDs {
146 out = binary.BigEndian.AppendUint64(out, uint64(id))
147 out = appendHistoryBound(out, chunk.bounds[row])
148 }
149 for row := range chunk.len() {
150 for x := range chunk.width {
151 cell := frame.Cell(x, chunk.start+row)
152 out = binary.BigEndian.AppendUint32(out, uint32(cell.Rune))
153 out = binary.BigEndian.AppendUint32(out, ids[cell.Style.Canonical()])
154 flag := byte(0)
155 if cell.Continuation {
156 flag = 1
157 }
158 if !cell.Payload.Empty() {
159 flag |= 2
160 }
161 out = append(out, flag)
162 if !cell.Payload.Empty() {
163 out = binary.BigEndian.AppendUint32(out, entry.payloadIDs[cell.Payload])
164 }
165 }
166 }
167 }
168 return out, nil
169}
170
171func historyViewRowCount(view HistoryView) int {
172 n := 0
173 for _, chunk := range view.chunks {
174 if chunk == nil || chunk.len() > math.MaxInt-n {
175 return -1
176 }
177 n += chunk.len()
178 }
179 return n
180}
181
182func historyViewNextRowID(view HistoryView) (RowID, bool) {
183 seen := make(map[RowID]struct{}, view.rows)
184 var maxID RowID
185 for _, chunk := range view.chunks {
186 if chunk == nil || chunk.len() != len(chunk.rowIDs) {
187 return 0, false
188 }
189 for _, id := range chunk.rowIDs {
190 if id == 0 || id >= ^RowID(0)-1 {
191 return 0, false
192 }
193 if _, duplicate := seen[id]; duplicate {
194 return 0, false
195 }
196 seen[id] = struct{}{}
197 maxID = max(maxID, id)
198 }
199 }
200 next := view.nextRowID
201 if next == 0 {
202 next = maxID + 1
203 }
204 return next, next > maxID && next < ^RowID(0)
205}
206
207// UnmarshalHistory accepts only VTC1. Validation precedes all decoded frame
208// allocations, including validation of later chunks in the same payload.
209func UnmarshalHistory(data []byte) (HistoryView, error) {
210 if _, _, ok := parseHistory(data, false); !ok {
211 return HistoryView{}, fmt.Errorf("unmarshal history: %w", errInvalidHistory)
212 }
213 view, _, ok := parseHistory(data, true)
214 if !ok {
215 return HistoryView{}, fmt.Errorf("unmarshal history: %w", errInvalidHistory)
216 }
217 return view, nil
218}
219
220func preflightHistory(data []byte) (historyDecodeStats, bool) {
221 _, stats, ok := parseHistory(data, false)
222 return stats, ok
223}
224
225func parseHistory(data []byte, populate bool) (HistoryView, historyDecodeStats, bool) {
226 invalid := func() (HistoryView, historyDecodeStats, bool) { return HistoryView{}, historyDecodeStats{}, false }
227 if len(data) < historyHeaderBytes || string(data[:4]) != historyMagic {
228 return invalid()
229 }
230 p := historyParser{data: data[4:]}
231 chunkCount, _ := p.uint32()
232 nextID, _ := p.uint64()
233 if chunkCount > maxHistoryChunks || uint64(chunkCount)*historyChunkHeaderBytes > uint64(len(p.data)) || nextID == 0 || nextID == math.MaxUint64 {
234 return invalid()
235 }
236 stats := historyDecodeStats{chunks: uint64(chunkCount)}
237 var seenIDs rowIDSet
238 var maxID RowID
239 var chunks []*HistoryChunk
240 if populate {
241 chunks = make([]*HistoryChunk, 0, chunkCount)
242 }
243 for range chunkCount {
244 width, wok := p.uint32()
245 rows, rok := p.uint32()
246 nstyles, sok := p.uint32()
247 npayloads, pok := p.uint32()
248 if !wok || !rok || !sok || !pok || rows == 0 || rows > maxHistoryChunkRows || uint64(width) > uint64(math.MaxInt) || nstyles == 0 || nstyles > maxHistoryStylesPerChunk {
249 return invalid()
250 }
251 cells := uint64(width) * uint64(rows)
252 if uint64(nstyles) > cells+1 || uint64(npayloads) > cells ||
253 !addHistoryDecodeBudget(&stats.rows, uint64(rows), maxHistoryRows) ||
254 !addHistoryDecodeBudget(&stats.cells, cells, maxHistoryCells) ||
255 !addHistoryDecodeBudget(&stats.styles, uint64(nstyles), maxHistoryDecodeStyles) ||
256 !addHistoryLogicalBytes(&stats, cells, uint64(rows), uint64(nstyles)) {
257 return invalid()
258 }
259 // Counts have now passed aggregate budgets. This sum cannot overflow.
260 payload := uint64(nstyles-1)*historyStyleBytes + uint64(npayloads)*8 + uint64(rows)*historyRowBytes + cells*historyStoredCellBytes
261 if payload > uint64(len(p.data)) {
262 return invalid()
263 }
264 styles := make([]renderer.Style, nstyles)
265 styles[0] = renderer.DefaultStyle()
266 seenStyles := map[renderer.Style]struct{}{renderer.DefaultStyle(): {}}
267 for id := uint32(1); id < nstyles; id++ {
268 style, ok := p.style()
269 if !ok || style != style.Canonical() || style.UnderlineStyle > renderer.UnderlineDashed {
270 return invalid()
271 }
272 if _, duplicate := seenStyles[style]; duplicate {
273 return invalid()
274 }
275 seenStyles[style] = struct{}{}
276 styles[id] = style
277 }
278 payloads, ok := p.payloadDictionary(npayloads, &stats)
279 if !ok {
280 return invalid()
281 }
282 usedPayloads := make([]bool, npayloads)
283 seenIDs.begin(int(rows))
284 rowIDs := make([]RowID, rows)
285 bounds := make([]LineBound, rows)
286 for row := range rows {
287 id, ok := p.uint64()
288 bound, bok := p.bound()
289 if !ok || !bok || id == 0 || id >= math.MaxUint64-1 || !validHistoryBound(bound, int(width)) {
290 return invalid()
291 }
292 seenIDs.collect(RowID(id))
293 maxID = max(maxID, RowID(id))
294 rowIDs[row], bounds[row] = RowID(id), bound
295 }
296 // Reject duplicate IDs before decoding any cells, as the map did.
297 if !seenIDs.commit() {
298 return invalid()
299 }
300 lastStyleRow := make([]int, nstyles)
301 for i := range lastStyleRow {
302 lastStyleRow[i] = -1
303 }
304 var frame renderer.Frame
305 if populate {
306 frame = renderer.NewFrame(int(width), int(rows))
307 }
308 for row := range rows {
309 for x := range width {
310 r, id, payloadID, continuation, ok := p.storedCell(nstyles, npayloads)
311 if !ok {
312 return invalid()
313 }
314 lastStyleRow[id] = int(row)
315 var value renderer.CellPayload
316 if payloadID != 0 {
317 usedPayloads[payloadID-1] = true
318 value = payloads[payloadID-1]
319 }
320 if populate {
321 frame.Set(int(x), int(row), renderer.Cell{Rune: r, Style: styles[id], Payload: value, Continuation: continuation})
322 }
323 }
324 }
325 for id := uint32(1); id < nstyles; id++ {
326 if lastStyleRow[id] < 0 {
327 return invalid()
328 }
329 }
330 for _, used := range usedPayloads {
331 if !used {
332 return invalid()
333 }
334 }
335 if populate {
336 drops := make([]uint64, rows)
337 for id := uint32(1); id < nstyles; id++ {
338 drops[lastStyleRow[id]]++
339 }
340 chunk := &HistoryChunk{page: newSealedPage(frame), count: int(rows), width: int(width), bounds: bounds, rowIDs: rowIDs, styleDrops: drops, styleCount: uint64(nstyles)}
341 chunk.recordPayloads()
342 chunks = append(chunks, chunk)
343 }
344 }
345 if len(p.data) != 0 || RowID(nextID) <= maxID {
346 return invalid()
347 }
348 return HistoryView{chunks: chunks, rows: int(stats.rows), cells: int(stats.cells), logicalBytes: stats.bytes, nextRowID: RowID(nextID)}, stats, true
349}
350
351func addHistoryLogicalBytes(stats *historyDecodeStats, cells, rows, styles uint64) bool {
352 // Callers first bound all three counts by the aggregate decode ceilings.
353 amount := cells*renderer.StoredCellLogicalBytes + rows*renderer.RowDescriptorLogicalBytes + styles*renderer.StyleRecordLogicalBytes
354 return addHistoryDecodeBudget(&stats.bytes, amount, maxHistoryDecodedBytes)
355}
356
357func addHistoryDecodeBudget(total *uint64, amount, limit uint64) bool {
358 if *total > limit || amount > limit-*total {
359 return false
360 }
361 *total += amount
362 return true
363}
364
365func validHistoryBound(bound LineBound, cells int) bool {
366 return bound.End >= 0 && bound.End <= cells
367}