lib/preserves/src/packed/reader.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! Reads one value back from its binary encoding. A caller decoding bytes from a peer needs the
2 //! decoder's memory, recursion and work bounded by numbers it chooses, whatever the bytes claim. A
3 //! caller that fingerprints encoded bytes needs every accepted input to be the one encoding of its
4 //! value.
5 //!
6 //! Encoded bytes declare their own lengths and nesting, so a short input can claim a huge string or
7 //! nest thousands of levels deep. The encoding is the binary syntax of the
8 //! [Preserves](https://preserves.dev/) data language, which the package keeps.
9 //!
10 //! `decode` takes four limits (`Limits`) and fails as soon as the input would pass one: nesting
11 //! depth, total values, items per collection and retained bytes. It accepts only the one encoding
12 //! of each value: shortest integers and varints, and set elements and dictionary keys in ascending
13 //! byte order with no repeats. It rejects annotations and embedded values. The decoded value copies
14 //! every byte it keeps, so it owns all its memory and borrows nothing from the input.
15 const std = @import("std");
16 const Allocator = std.mem.Allocator;
17
18 const preserves = @import("../root.zig");
19
20 const value_mod = preserves.value;
21 const integer_mod = preserves.integer_mod;
22
23 const constants = @import("constants.zig");
24 pub const Tag = constants.Tag;
25
26 /// The ways `decode` refuses its input, one tag per kind of bad or over-limit bytes. Code that
27 /// reports why bytes were refused switches on these tags, and `DecodeError` adds running out of
28 /// memory.
29 pub const DecodeFailure = error{
30 /// Values nested deeper than `max_depth`, counting the top value as depth 1.
31 DepthLimitExceeded,
32 /// Input holding more than `max_nodes` values in all, counting every nested value, record label
33 /// and dictionary key.
34 NodeLimitExceeded,
35 /// A record, sequence, set or dictionary with more than `max_collection_items` fields, items or
36 /// entries.
37 CollectionLimitExceeded,
38 /// Input whose decoded value would keep more than `max_retained_bytes` bytes.
39 RetainedBytesLimitExceeded,
40 /// Input that ends inside a value: before a tag byte, inside a varint or payload, or before a
41 /// collection's end marker.
42 UnexpectedEof,
43 /// Bytes left over after the first complete value.
44 UnexpectedTrailingBytes,
45 /// A tag byte outside the fourteen tags in `Tag`.
46 UnknownTag,
47 /// The end marker 0x84 at the start of a value, such as right after a record's opening tag or
48 /// at the start of the input.
49 UnexpectedEndMarker,
50 /// A varint of two or more bytes whose last byte is zero.
51 OverlongVarint,
52 /// A varint whose value needs more than 64 bits: its tenth byte is greater than 1.
53 VarintTooWide,
54 /// A length that exceeds `usize`. It can happen only on targets whose `usize` has fewer than 64
55 /// bits, since a varint holds at most 64.
56 LengthOutOfRange,
57 /// A double, tag 0x87, whose length differs from 8.
58 InvalidDoubleLength,
59 /// An integer payload with a redundant leading byte: 0x00 before a byte below 0x80, 0xff before
60 /// a byte of 0x80 or above, or a lone 0x00.
61 NonCanonicalInteger,
62 /// A set whose element encodings fall outside strictly ascending byte order.
63 NonCanonicalSetOrder,
64 /// A dictionary whose key encodings fall outside strictly ascending byte order.
65 NonCanonicalDictionaryOrder,
66 /// A string or symbol whose payload is invalid UTF-8.
67 InvalidUtf8,
68 /// An annotation, tag 0x85, anywhere in the input.
69 AnnotationNotSupported,
70 /// An embedded value, tag 0x86, anywhere in the input, whatever the type of the embedded
71 /// values.
72 EmbeddedNotSupported,
73 /// A set holding two equal elements. The check runs before the order check, so repeated bytes
74 /// report this tag.
75 DuplicateSetElement,
76 /// A dictionary holding two equal keys. The check runs before the order check, so a repeated
77 /// key reports this tag.
78 DuplicateDictionaryKey,
79 };
80
81 /// The errors `decode` returns: every `DecodeFailure` tag and running out of memory. Code that
82 /// decodes packed bytes names this set, for its own error sets.
83 pub const DecodeError = Allocator.Error || DecodeFailure;
84
85 /// The four bounds `decode` enforces while it reads. Code that decodes bytes from a peer sets one
86 /// for each kind of payload it admits. The struct has no defaults, so the caller picks every bound.
87 pub const Limits = struct {
88 /// The deepest nesting `decode` accepts, counting the top value as depth 1. Each record label,
89 /// field, item, key and value sits one level below its container.
90 max_depth: u16,
91 /// The most values `decode` reads in all, counting every nested value.
92 max_nodes: u32,
93 /// The most fields, items or entries one record, sequence, set or dictionary may hold. A
94 /// record's label does not count, and a dictionary entry counts once.
95 max_collection_items: u32,
96 /// The most bytes the decoded value may keep, counted as it is built. The decoder counts every
97 /// string, byte string and symbol payload. It counts an integer's payload only when it is
98 /// longer than 16 bytes and exceeds 128 bits unsigned. It counts each collection's slice at the
99 /// size of its items, and one more value for each record's label.
100 max_retained_bytes: usize,
101 };
102
103 const Admission = struct {
104 limits: Limits,
105 nodes: u32 = 0,
106 retained_bytes: usize = 0,
107
108 fn enter(self: *Admission, depth: u32) DecodeError!void {
109 if (depth > self.limits.max_depth) return error.DepthLimitExceeded;
110 if (self.nodes >= self.limits.max_nodes) return error.NodeLimitExceeded;
111 self.nodes += 1;
112 }
113
114 fn retain(self: *Admission, bytes: usize) DecodeError!void {
115 if (bytes > self.limits.max_retained_bytes -| self.retained_bytes) {
116 return error.RetainedBytesLimitExceeded;
117 }
118 self.retained_bytes += bytes;
119 }
120
121 fn retainItems(self: *Admission, comptime T: type, count: usize) DecodeError!void {
122 const bytes = std.math.mul(usize, @sizeOf(T), count) catch
123 return error.RetainedBytesLimitExceeded;
124 return self.retain(bytes);
125 }
126
127 fn admitItem(self: *Admission, count: usize) DecodeError!void {
128 if (count >= self.limits.max_collection_items) {
129 return error.CollectionLimitExceeded;
130 }
131 }
132 };
133
134 /// Returns the one value that `bytes` encodes, allocated with `allocator`. Code that admits packed
135 /// bytes from a peer calls it, for one owned value within the caller's limits. `D` is the type of
136 /// the result's embedded values, and the decoder rejects embedded values whatever `D` is. The value
137 /// owns all its memory, so `bytes` may be freed at once, and the caller frees the value with
138 /// `deinit`. On any error the call frees everything it allocated. Its duplicate checks compare each
139 /// set element or dictionary key with every earlier one, so their cost grows with the square of the
140 /// count.
141 pub fn decode(
142 comptime D: type,
143 allocator: Allocator,
144 bytes: []const u8,
145 limits: Limits,
146 ) DecodeError!value_mod.Value(D) {
147 var index: usize = 0;
148 var admission = Admission{ .limits = limits };
149 var value = try readValue(D, allocator, bytes, &index, &admission, 1);
150 errdefer value.deinit(allocator);
151 if (index != bytes.len) return error.UnexpectedTrailingBytes;
152 return value;
153 }
154
155 fn readValue(
156 comptime D: type,
157 allocator: Allocator,
158 bytes: []const u8,
159 index: *usize,
160 admission: *Admission,
161 depth: u32,
162 ) DecodeError!value_mod.Value(D) {
163 try admission.enter(depth);
164 if (index.* >= bytes.len) return error.UnexpectedEof;
165 const tag_byte = bytes[index.*];
166 index.* += 1;
167 const tag = Tag.fromByte(tag_byte) orelse return error.UnknownTag;
168 return switch (tag) {
169 .false_ => value_mod.Value(D).initBoolean(false),
170 .true_ => value_mod.Value(D).initBoolean(true),
171 .end => error.UnexpectedEndMarker,
172 .annotation => error.AnnotationNotSupported,
173 .embedded => error.EmbeddedNotSupported,
174 .ieee754 => try readDouble(D, bytes, index),
175 .signed_integer => try readSignedInteger(D, allocator, bytes, index, admission),
176 .string => try readStringLike(D, allocator, bytes, index, admission, .string),
177 .byte_string => try readStringLike(D, allocator, bytes, index, admission, .byte_string),
178 .symbol => try readStringLike(D, allocator, bytes, index, admission, .symbol),
179 .record => try readRecord(D, allocator, bytes, index, admission, depth),
180 .sequence => try readSequence(D, allocator, bytes, index, admission, depth),
181 .set => try readSet(D, allocator, bytes, index, admission, depth),
182 .dictionary => try readDictionary(D, allocator, bytes, index, admission, depth),
183 };
184 }
185
186 /// Reads one varint from `bytes` at `index.*`, advances `index` past it and returns its value. The
187 /// reader calls it for every length prefix, and code that walks packed bytes by hand can call it
188 /// too. The varint holds seven bits per byte, low bits first, with the high bit set on every byte
189 /// but the last. The call returns `error.UnexpectedEof` when the input ends first,
190 /// `error.OverlongVarint` when a later byte is zero, and `error.VarintTooWide` past 64 bits.
191 pub fn readVarint(bytes: []const u8, index: *usize) DecodeError!u64 {
192 var result: u64 = 0;
193 var shift: u6 = 0;
194 for (0..10) |byte_index| {
195 if (index.* >= bytes.len) return error.UnexpectedEof;
196 const b = bytes[index.*];
197 index.* += 1;
198 if (byte_index == 9 and b > 1) return error.VarintTooWide;
199 result |= @as(u64, b & 0x7f) << shift;
200 if ((b & 0x80) == 0) {
201 if (byte_index > 0 and b == 0) return error.OverlongVarint;
202 return result;
203 }
204 if (byte_index == 9) return error.VarintTooWide;
205 shift += 7;
206 }
207 unreachable;
208 }
209
210 fn readDouble(comptime D: type, bytes: []const u8, index: *usize) DecodeError!value_mod.Value(D) {
211 const len = try readVarint(bytes, index);
212 if (len != 8) return error.InvalidDoubleLength;
213 if (bytes.len - index.* < 8) return error.UnexpectedEof;
214 const raw = std.mem.readInt(u64, bytes[index.*..][0..8], .big);
215 index.* += 8;
216 return value_mod.Value(D).initDouble(@bitCast(raw));
217 }
218
219 fn readSignedInteger(
220 comptime D: type,
221 allocator: Allocator,
222 bytes: []const u8,
223 index: *usize,
224 admission: *Admission,
225 ) DecodeError!value_mod.Value(D) {
226 const len = try readVarint(bytes, index);
227 const n = std.math.cast(usize, len) orelse return error.LengthOutOfRange;
228 if (bytes.len - index.* < n) return error.UnexpectedEof;
229 const payload = bytes[index.* .. index.* + n];
230 index.* += n;
231 if (!integer_mod.SignedInteger.isCanonicalBytes(payload)) {
232 return error.NonCanonicalInteger;
233 }
234 try admission.retain(integerRetainedBytes(payload));
235 const si = try integer_mod.SignedInteger.fromCanonicalBytes(allocator, payload);
236 return value_mod.Value(D).initSignedInteger(si);
237 }
238
239 fn integerRetainedBytes(payload: []const u8) usize {
240 if (payload.len <= 16) return 0;
241 if (payload.len == 17 and payload[0] == 0x00 and
242 (payload[1] & 0x80) != 0)
243 {
244 return 0;
245 }
246 return payload.len;
247 }
248
249 fn readStringLike(
250 comptime D: type,
251 allocator: Allocator,
252 bytes: []const u8,
253 index: *usize,
254 admission: *Admission,
255 comptime kind: enum { string, byte_string, symbol },
256 ) DecodeError!value_mod.Value(D) {
257 const len = try readVarint(bytes, index);
258 const n = std.math.cast(usize, len) orelse return error.LengthOutOfRange;
259 if (bytes.len - index.* < n) return error.UnexpectedEof;
260 const payload = bytes[index.* .. index.* + n];
261 index.* += n;
262 switch (kind) {
263 .string, .symbol => if (!std.unicode.utf8ValidateSlice(payload)) return error.InvalidUtf8,
264 .byte_string => {},
265 }
266 try admission.retain(payload.len);
267 const owned = try allocator.dupe(u8, payload);
268 return switch (kind) {
269 .string => .{ .string = owned },
270 .byte_string => .{ .byte_string = owned },
271 .symbol => .{ .symbol = owned },
272 };
273 }
274
275 fn readRecord(
276 comptime D: type,
277 allocator: Allocator,
278 bytes: []const u8,
279 index: *usize,
280 admission: *Admission,
281 depth: u32,
282 ) DecodeError!value_mod.Value(D) {
283 const V = value_mod.Value(D);
284 var label_value = try readValue(D, allocator, bytes, index, admission, depth + 1);
285 errdefer label_value.deinit(allocator);
286
287 var fields: std.ArrayListUnmanaged(V) = .empty;
288 errdefer {
289 for (fields.items) |*f| f.deinit(allocator);
290 fields.deinit(allocator);
291 }
292
293 while (true) {
294 if (index.* >= bytes.len) return error.UnexpectedEof;
295 if (bytes[index.*] == Tag.end.byte()) {
296 index.* += 1;
297 break;
298 }
299 try admission.admitItem(fields.items.len);
300 var field = try readValue(D, allocator, bytes, index, admission, depth + 1);
301 errdefer field.deinit(allocator);
302 try fields.append(allocator, field);
303 }
304
305 try admission.retainItems(V, fields.items.len);
306 const owned = try fields.toOwnedSlice(allocator);
307 errdefer {
308 for (owned) |*field| field.deinit(allocator);
309 allocator.free(owned);
310 }
311 try admission.retainItems(V, 1);
312 return try V.initRecord(allocator, label_value, owned);
313 }
314
315 fn readSequence(
316 comptime D: type,
317 allocator: Allocator,
318 bytes: []const u8,
319 index: *usize,
320 admission: *Admission,
321 depth: u32,
322 ) DecodeError!value_mod.Value(D) {
323 const V = value_mod.Value(D);
324 var items: std.ArrayListUnmanaged(V) = .empty;
325 errdefer {
326 for (items.items) |*it| it.deinit(allocator);
327 items.deinit(allocator);
328 }
329 while (true) {
330 if (index.* >= bytes.len) return error.UnexpectedEof;
331 if (bytes[index.*] == Tag.end.byte()) {
332 index.* += 1;
333 break;
334 }
335 try admission.admitItem(items.items.len);
336 var it = try readValue(D, allocator, bytes, index, admission, depth + 1);
337 errdefer it.deinit(allocator);
338 try items.append(allocator, it);
339 }
340 try admission.retainItems(V, items.items.len);
341 return .{ .sequence = try items.toOwnedSlice(allocator) };
342 }
343
344 fn readSet(
345 comptime D: type,
346 allocator: Allocator,
347 bytes: []const u8,
348 index: *usize,
349 admission: *Admission,
350 depth: u32,
351 ) DecodeError!value_mod.Value(D) {
352 const V = value_mod.Value(D);
353 var items: std.ArrayListUnmanaged(V) = .empty;
354 var previous_encoding: ?[]const u8 = null;
355 errdefer {
356 for (items.items) |*it| it.deinit(allocator);
357 items.deinit(allocator);
358 }
359 while (true) {
360 if (index.* >= bytes.len) return error.UnexpectedEof;
361 if (bytes[index.*] == Tag.end.byte()) {
362 index.* += 1;
363 break;
364 }
365 try admission.admitItem(items.items.len);
366 const start = index.*;
367 var it = try readValue(D, allocator, bytes, index, admission, depth + 1);
368 errdefer it.deinit(allocator);
369 if (V.setContainsElement(items.items, it)) return error.DuplicateSetElement;
370 const encoding = bytes[start..index.*];
371 if (previous_encoding) |previous| {
372 if (std.mem.order(u8, previous, encoding) != .lt) {
373 return error.NonCanonicalSetOrder;
374 }
375 }
376 try items.append(allocator, it);
377 previous_encoding = encoding;
378 }
379 try admission.retainItems(V, items.items.len);
380 return .{ .set = try items.toOwnedSlice(allocator) };
381 }
382
383 fn readDictionary(
384 comptime D: type,
385 allocator: Allocator,
386 bytes: []const u8,
387 index: *usize,
388 admission: *Admission,
389 depth: u32,
390 ) DecodeError!value_mod.Value(D) {
391 const V = value_mod.Value(D);
392 var entries: std.ArrayListUnmanaged(V.DictionaryEntry) = .empty;
393 var previous_key_encoding: ?[]const u8 = null;
394 errdefer {
395 for (entries.items) |*e| {
396 e.key.deinit(allocator);
397 e.value.deinit(allocator);
398 }
399 entries.deinit(allocator);
400 }
401 while (true) {
402 if (index.* >= bytes.len) return error.UnexpectedEof;
403 if (bytes[index.*] == Tag.end.byte()) {
404 index.* += 1;
405 break;
406 }
407 try admission.admitItem(entries.items.len);
408 const key_start = index.*;
409 var key = try readValue(D, allocator, bytes, index, admission, depth + 1);
410 errdefer key.deinit(allocator);
411 if (V.dictionaryContainsKey(entries.items, key)) return error.DuplicateDictionaryKey;
412 const key_encoding = bytes[key_start..index.*];
413 if (previous_key_encoding) |previous| {
414 if (std.mem.order(u8, previous, key_encoding) != .lt) {
415 return error.NonCanonicalDictionaryOrder;
416 }
417 }
418 var val = try readValue(D, allocator, bytes, index, admission, depth + 1);
419 errdefer val.deinit(allocator);
420 try entries.append(allocator, .{ .key = key, .value = val });
421 previous_key_encoding = key_encoding;
422 }
423 try admission.retainItems(V.DictionaryEntry, entries.items.len);
424 return .{ .dictionary = try entries.toOwnedSlice(allocator) };
425 }
426
427 const test_limits: Limits = .{
428 .max_depth = 64,
429 .max_nodes = 1024,
430 .max_collection_items = 256,
431 .max_retained_bytes = 1024 * 1024,
432 };
433
434 test "readVarint parses single-byte" {
435 var idx: usize = 0;
436 const got = try readVarint(&[_]u8{0x7f}, &idx);
437 try std.testing.expectEqual(@as(u64, 0x7f), got);
438 try std.testing.expectEqual(@as(usize, 1), idx);
439 }
440
441 test "readVarint parses multi-byte" {
442 var idx: usize = 0;
443 const got = try readVarint(&[_]u8{ 0x80, 0x01 }, &idx);
444 try std.testing.expectEqual(@as(u64, 128), got);
445 try std.testing.expectEqual(@as(usize, 2), idx);
446 }
447
448 test "readVarint rejects overlong" {
449 var idx: usize = 0;
450 try std.testing.expectError(error.OverlongVarint, readVarint(&[_]u8{ 0x80, 0x00 }, &idx));
451 }
452
453 test "decode boolean" {
454 const allocator = std.testing.allocator;
455 const V = value_mod.Value(preserves.domain.NoEmbedded);
456 var t = try decode(preserves.domain.NoEmbedded, allocator, &[_]u8{0x81}, test_limits);
457 defer t.deinit(allocator);
458 try std.testing.expectEqual(V.initBoolean(true), t);
459
460 var f = try decode(preserves.domain.NoEmbedded, allocator, &[_]u8{0x80}, test_limits);
461 defer f.deinit(allocator);
462 try std.testing.expectEqual(V.initBoolean(false), f);
463 }
464
465 test "decode rejects trailing bytes" {
466 const allocator = std.testing.allocator;
467 try std.testing.expectError(
468 error.UnexpectedTrailingBytes,
469 decode(preserves.domain.NoEmbedded, allocator, &[_]u8{ 0x80, 0x80 }, test_limits),
470 );
471 }
472
473 fn checkRecordAllocationFailures(allocator: Allocator) !void {
474 const bytes = [_]u8{
475 0xb4,
476 0xb1,
477 0x05,
478 'l',
479 'a',
480 'b',
481 'e',
482 'l',
483 0xb1,
484 0x05,
485 'o',
486 'w',
487 'n',
488 'e',
489 'd',
490 0x84,
491 };
492 var value = try decode(preserves.domain.NoEmbedded, allocator, &bytes, test_limits);
493 defer value.deinit(allocator);
494 try std.testing.expect(value == .record);
495 }
496
497 test "packed record releases every allocation failure path" {
498 try std.testing.checkAllAllocationFailures(
499 std.testing.allocator,
500 checkRecordAllocationFailures,
501 .{},
502 );
503 }
504
505 test "packed admission rejects every exhausted budget" {
506 const allocator = std.testing.allocator;
507 const nested = [_]u8{ 0xb5, 0xb5, 0x80, 0x84, 0x84 };
508 const nodes = [_]u8{ 0xb5, 0x80, 0x81, 0x84 };
509 const retained = [_]u8{ 0xb1, 0x02, 'a', 'b' };
510 try std.testing.expectError(error.DepthLimitExceeded, decode(
511 preserves.NoEmbedded,
512 allocator,
513 &nested,
514 .{ .max_depth = 2, .max_nodes = 8, .max_collection_items = 8, .max_retained_bytes = 8 },
515 ));
516 try std.testing.expectError(error.NodeLimitExceeded, decode(
517 preserves.NoEmbedded,
518 allocator,
519 &nodes,
520 .{ .max_depth = 4, .max_nodes = 2, .max_collection_items = 8, .max_retained_bytes = 8 },
521 ));
522 try std.testing.expectError(error.CollectionLimitExceeded, decode(
523 preserves.NoEmbedded,
524 allocator,
525 &nodes,
526 .{ .max_depth = 4, .max_nodes = 8, .max_collection_items = 1, .max_retained_bytes = 128 },
527 ));
528 try std.testing.expectError(error.RetainedBytesLimitExceeded, decode(
529 preserves.NoEmbedded,
530 allocator,
531 &retained,
532 .{ .max_depth = 1, .max_nodes = 1, .max_collection_items = 0, .max_retained_bytes = 1 },
533 ));
534 }
535
536 test "packed admission accepts every exact budget boundary" {
537 const allocator = std.testing.allocator;
538 const nested = [_]u8{ 0xb5, 0xb5, 0x80, 0x84, 0x84 };
539 const nodes = [_]u8{ 0xb5, 0x80, 0x81, 0x84 };
540 const retained = [_]u8{ 0xb1, 0x02, 'a', 'b' };
541 var depth_value = try decode(
542 preserves.NoEmbedded,
543 allocator,
544 &nested,
545 .{ .max_depth = 3, .max_nodes = 8, .max_collection_items = 8, .max_retained_bytes = 256 },
546 );
547 defer depth_value.deinit(allocator);
548 var node_value = try decode(
549 preserves.NoEmbedded,
550 allocator,
551 &nodes,
552 .{ .max_depth = 2, .max_nodes = 3, .max_collection_items = 2, .max_retained_bytes = 256 },
553 );
554 defer node_value.deinit(allocator);
555 var retained_value = try decode(
556 preserves.NoEmbedded,
557 allocator,
558 &retained,
559 .{ .max_depth = 1, .max_nodes = 1, .max_collection_items = 0, .max_retained_bytes = 2 },
560 );
561 defer retained_value.deinit(allocator);
562 }
563
564 test "packed admission rejects noncanonical unordered collections" {
565 const allocator = std.testing.allocator;
566 const set = [_]u8{ 0xb6, 0xb1, 0x01, 'b', 0xb1, 0x01, 'a', 0x84 };
567 const dictionary = [_]u8{
568 0xb7, 0xb1, 0x01, 'b', 0x80, 0xb1, 0x01, 'a', 0x81, 0x84,
569 };
570 try std.testing.expectError(
571 error.NonCanonicalSetOrder,
572 decode(preserves.NoEmbedded, allocator, &set, test_limits),
573 );
574 try std.testing.expectError(
575 error.NonCanonicalDictionaryOrder,
576 decode(preserves.NoEmbedded, allocator, &dictionary, test_limits),
577 );
578 }
579
580 test "packed admission rejects annotations and embedded values" {
581 const allocator = std.testing.allocator;
582 try std.testing.expectError(
583 error.AnnotationNotSupported,
584 decode(preserves.NoEmbedded, allocator, &.{ 0x85, 0x80, 0x81 }, test_limits),
585 );
586 try std.testing.expectError(
587 error.EmbeddedNotSupported,
588 decode(preserves.NoEmbedded, allocator, &.{ 0x86, 0x80 }, test_limits),
589 );
590 }