tiny.preserves.packed_reader

1//! Reads one value back from its binary encoding. A caller decoding bytes from a peer needs the2//! decoder's memory, recursion and work bounded by numbers it chooses, whatever the bytes claim. A3//! caller that fingerprints encoded bytes needs every accepted input to be the one encoding of its4//! value.5//!6//! Encoded bytes declare their own lengths and nesting, so a short input can claim a huge string or7//! nest thousands of levels deep. The encoding is the binary syntax of the8//! [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: nesting11//! depth, total values, items per collection and retained bytes. It accepts only the one encoding12//! of each value: shortest integers and varints, and set elements and dictionary keys in ascending13//! byte order with no repeats. It rejects annotations and embedded values. The decoded value copies14//! every byte it keeps, so it owns all its memory and borrows nothing from the input.15const std = @import("std");16const Allocator = std.mem.Allocator;1718const preserves = @import("../root.zig");1920const value_mod = preserves.value;21const integer_mod = preserves.integer_mod;2223const constants = @import("constants.zig");24pub const Tag = constants.Tag;2526/// The ways `decode` refuses its input, one tag per kind of bad or over-limit bytes. Code that27/// reports why bytes were refused switches on these tags, and `DecodeError` adds running out of28/// memory.29pub 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 label33    /// and dictionary key.34    NodeLimitExceeded,35    /// A record, sequence, set or dictionary with more than `max_collection_items` fields, items or36    /// 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 a41    /// 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 or48    /// 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 6455    /// 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 before60    /// 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 embedded71    /// values.72    EmbeddedNotSupported,73    /// A set holding two equal elements. The check runs before the order check, so repeated bytes74    /// report this tag.75    DuplicateSetElement,76    /// A dictionary holding two equal keys. The check runs before the order check, so a repeated77    /// key reports this tag.78    DuplicateDictionaryKey,79};8081/// The errors `decode` returns: every `DecodeFailure` tag and running out of memory. Code that82/// decodes packed bytes names this set, for its own error sets.83pub const DecodeError = Allocator.Error || DecodeFailure;8485/// The four bounds `decode` enforces while it reads. Code that decodes bytes from a peer sets one86/// for each kind of payload it admits. The struct has no defaults, so the caller picks every bound.87pub 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. A94    /// 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 every97    /// string, byte string and symbol payload. It counts an integer's payload only when it is98    /// longer than 16 bytes and exceeds 128 bits unsigned. It counts each collection's slice at the99    /// size of its items, and one more value for each record's label.100    max_retained_bytes: usize,101};102103const Admission = struct {104    limits: Limits,105    nodes: u32 = 0,106    retained_bytes: usize = 0,107108    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    }113114    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    }120121    fn retainItems(self: *Admission, comptime T: type, count: usize) DecodeError!void {122        const bytes = std.math.mul(usize, @sizeOf(T), count) catch123            return error.RetainedBytesLimitExceeded;124        return self.retain(bytes);125    }126127    fn admitItem(self: *Admission, count: usize) DecodeError!void {128        if (count >= self.limits.max_collection_items) {129            return error.CollectionLimitExceeded;130        }131    }132};133134/// Returns the one value that `bytes` encodes, allocated with `allocator`. Code that admits packed135/// bytes from a peer calls it, for one owned value within the caller's limits. `D` is the type of136/// the result's embedded values, and the decoder rejects embedded values whatever `D` is. The value137/// owns all its memory, so `bytes` may be freed at once, and the caller frees the value with138/// `deinit`. On any error the call frees everything it allocated. Its duplicate checks compare each139/// set element or dictionary key with every earlier one, so their cost grows with the square of the140/// count.141pub 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}154155fn 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}185186/// Reads one varint from `bytes` at `index.*`, advances `index` past it and returns its value. The187/// reader calls it for every length prefix, and code that walks packed bytes by hand can call it188/// too. The varint holds seven bits per byte, low bits first, with the high bit set on every byte189/// 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.191pub 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}209210fn 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}218219fn 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}238239fn integerRetainedBytes(payload: []const u8) usize {240    if (payload.len <= 16) return 0;241    if (payload.len == 17 and payload[0] == 0x00 and242        (payload[1] & 0x80) != 0)243    {244        return 0;245    }246    return payload.len;247}248249fn 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}274275fn 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);286287    var fields: std.ArrayListUnmanaged(V) = .empty;288    errdefer {289        for (fields.items) |*f| f.deinit(allocator);290        fields.deinit(allocator);291    }292293    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    }304305    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}314315fn 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}343344fn 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}382383fn 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}426427const test_limits: Limits = .{428    .max_depth = 64,429    .max_nodes = 1024,430    .max_collection_items = 256,431    .max_retained_bytes = 1024 * 1024,432};433434test "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}440441test "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}447448test "readVarint rejects overlong" {449    var idx: usize = 0;450    try std.testing.expectError(error.OverlongVarint, readVarint(&[_]u8{ 0x80, 0x00 }, &idx));451}452453test "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);459460    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}464465test "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}472473fn 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}496497test "packed record releases every allocation failure path" {498    try std.testing.checkAllAllocationFailures(499        std.testing.allocator,500        checkRecordAllocationFailures,501        .{},502    );503}504505test "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}535536test "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}563564test "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}579580test "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}

1pub const packed_reader = @"packed".reader;