tiny.preserves.packed_writer

1//! Writes values as bytes in a binary encoding. A caller that hashes or compares encoded bytes2//! needs equal values to produce equal bytes. A set or dictionary can store its items in any order,3//! and still be equal to one stored in another order. One integer can be written with any number of4//! leading sign bytes. The encoding is the binary syntax of the [Preserves](https://preserves.dev/)5//! data language, which the package keeps. The writer sorts set elements and dictionary entries by6//! their encoded bytes, and writes each integer in its shortest two's-complement form. It refuses7//! what the packed reader could not read back as the same value: repeated set elements or8//! dictionary keys, and discards, captures, binds and rest patterns. It writes an embedded value9//! only when the type of the embedded values supplies `encodePacked`, and `NoEmbedded` and10//! `AnyEmbedded` both lack it.11const std = @import("std");12const Allocator = std.mem.Allocator;13const ArrayList = std.ArrayListUnmanaged(u8);1415const preserves = @import("../root.zig");1617const value_mod = preserves.value;18const integer_mod = preserves.integer_mod;1920const constants = @import("constants.zig");21pub const Tag = constants.Tag;2223/// The errors `encode`, `writeValue` and `writeVarint` return, so the caller can switch on them or24/// fold them into its own error set. `EmbeddedNotSupported` means the value holds an embedded value25/// whose type lacks `encodePacked`. `DuplicateSetElement` and `DuplicateDictionaryKey` mean a set26/// holds two equal elements, or a dictionary two equal keys, by value equality or by equal27/// encodings. `PatternFormNotEncodable` means the value holds a discard, capture, bind or rest28/// pattern. `OutOfMemory` means an allocation failed.29pub const EncodeError = Allocator.Error || error{30    EmbeddedNotSupported,31    DuplicateSetElement,32    DuplicateDictionaryKey,33    PatternFormNotEncodable,34};3536/// Returns the binary encoding of `value` as new bytes allocated with `allocator`, for code that37/// stores, sends or fingerprints a value. The caller owns the bytes and frees them with38/// `allocator`. On any error the call frees everything it allocated. Encoding a value that `decode`39/// returned gives back the bytes `decode` read.40pub fn encode(comptime D: type, allocator: Allocator, value: value_mod.Value(D)) EncodeError![]u8 {41    var buf: ArrayList = .empty;42    errdefer buf.deinit(allocator);43    try writeValue(D, allocator, &buf, value);44    return buf.toOwnedSlice(allocator);45}4647/// Appends the binary encoding of `value` to `out`, growing `out` with `allocator`. `encode` calls48/// it with a fresh buffer, and code that packs more than one value into one buffer can call it49/// directly. On error, the bytes appended before the failure stay in `out`, so the caller discards50/// the buffer. Each set element and each dictionary entry is encoded into its own buffer, then51/// sorted by those bytes before it is appended. A double is written as the tag 0x87, the length 852/// and its eight bytes, big-endian. Strings, byte strings, symbols and integers are written as a53/// tag, a varint length and the payload. Records and sequences are written as a tag, their parts in54/// order and the end marker.55pub fn writeValue(56    comptime D: type,57    allocator: Allocator,58    out: *ArrayList,59    value: value_mod.Value(D),60) EncodeError!void {61    switch (value) {62        .boolean => |b| try out.append(allocator, if (b) Tag.true_.byte() else Tag.false_.byte()),63        .double => |v| try writeDouble(allocator, out, v),64        .signed_integer => |si| try writeSignedInteger(allocator, out, si),65        .string => |s| try writeAtom(allocator, out, .string, s),66        .byte_string => |s| try writeAtom(allocator, out, .byte_string, s),67        .symbol => |s| try writeAtom(allocator, out, .symbol, s),68        .record => |r| {69            try out.append(allocator, Tag.record.byte());70            try writeValue(D, allocator, out, r.label.*);71            for (r.fields) |f| try writeValue(D, allocator, out, f);72            try out.append(allocator, Tag.end.byte());73        },74        .sequence => |s| {75            try out.append(allocator, Tag.sequence.byte());76            for (s) |item| try writeValue(D, allocator, out, item);77            try out.append(allocator, Tag.end.byte());78        },79        .set => |items| try writeSet(D, allocator, out, items),80        .dictionary => |entries| try writeDictionary(D, allocator, out, entries),81        .embedded => |d| {82            if (!@hasDecl(D, "encodePacked")) return error.EmbeddedNotSupported;83            try out.append(allocator, Tag.embedded.byte());84            try D.encodePacked(d, allocator, out);85        },86        .discard, .capture, .bind, .rest_pattern => return error.PatternFormNotEncodable,87    }88}8990/// Appends `value_in` to `out` as a varint: seven bits per byte, low bits first, with the high bit91/// set on every byte but the last. The writer calls it for every length prefix. Zero is written as92/// the single byte 0x00, and 128 as 0x80 0x01. The packed reader's `readVarint` reads this form93/// back. The only error is running out of memory.94pub fn writeVarint(allocator: Allocator, out: *ArrayList, value_in: u64) EncodeError!void {95    var v = value_in;96    while (true) {97        var byte: u8 = @intCast(v & 0x7f);98        v >>= 7;99        if (v != 0) byte |= 0x80;100        try out.append(allocator, byte);101        if (v == 0) return;102    }103}104105fn writeAtom(allocator: Allocator, out: *ArrayList, tag: Tag, payload: []const u8) EncodeError!void {106    try out.append(allocator, tag.byte());107    try writeVarint(allocator, out, @intCast(payload.len));108    try out.appendSlice(allocator, payload);109}110111fn writeDouble(allocator: Allocator, out: *ArrayList, v: f64) EncodeError!void {112    try out.append(allocator, Tag.ieee754.byte());113    try writeVarint(allocator, out, 8);114    const bits: u64 = @bitCast(v);115    var bytes: [8]u8 = undefined;116    std.mem.writeInt(u64, &bytes, bits, .big);117    try out.appendSlice(allocator, &bytes);118}119120fn writeSignedInteger(allocator: Allocator, out: *ArrayList, si: integer_mod.SignedInteger) EncodeError!void {121    const bytes = try si.toCanonicalBytes(allocator);122    defer allocator.free(bytes);123    try writeAtom(allocator, out, .signed_integer, bytes);124}125126fn writeSet(127    comptime D: type,128    allocator: Allocator,129    out: *ArrayList,130    items: []const value_mod.Value(D),131) EncodeError!void {132    if (!value_mod.Value(D).setElementsDistinct(items)) {133        return error.DuplicateSetElement;134    }135    try out.append(allocator, Tag.set.byte());136    const bufs = try allocator.alloc([]u8, items.len);137    var filled: usize = 0;138    defer {139        for (bufs[0..filled]) |b| allocator.free(b);140        allocator.free(bufs);141    }142    for (items) |it| {143        bufs[filled] = try encode(D, allocator, it);144        filled += 1;145    }146    std.mem.sortUnstable([]u8, bufs, {}, lessThanBytes);147    if (bufs.len > 1) {148        for (bufs[1..], bufs[0 .. bufs.len - 1]) |current, previous| {149            if (std.mem.eql(u8, previous, current)) return error.DuplicateSetElement;150        }151    }152    for (bufs) |b| try out.appendSlice(allocator, b);153    try out.append(allocator, Tag.end.byte());154}155156fn writeDictionary(157    comptime D: type,158    allocator: Allocator,159    out: *ArrayList,160    entries: []const value_mod.Value(D).DictionaryEntry,161) EncodeError!void {162    const Pair = struct { key: []u8, value: []u8 };163    if (!value_mod.Value(D).dictionaryKeysDistinct(entries)) {164        return error.DuplicateDictionaryKey;165    }166    try out.append(allocator, Tag.dictionary.byte());167    const pairs = try allocator.alloc(Pair, entries.len);168    var filled: usize = 0;169    defer {170        for (pairs[0..filled]) |p| {171            allocator.free(p.key);172            allocator.free(p.value);173        }174        allocator.free(pairs);175    }176    for (entries) |e| {177        const k = try encode(D, allocator, e.key);178        errdefer allocator.free(k);179        const v = try encode(D, allocator, e.value);180        pairs[filled] = .{ .key = k, .value = v };181        filled += 1;182    }183    const PairLess = struct {184        fn lt(_: void, a: Pair, b: Pair) bool {185            return std.mem.order(u8, a.key, b.key) == .lt;186        }187    };188    std.mem.sortUnstable(Pair, pairs, {}, PairLess.lt);189    if (pairs.len > 1) {190        for (pairs[1..], pairs[0 .. pairs.len - 1]) |current, previous| {191            if (std.mem.eql(u8, previous.key, current.key)) return error.DuplicateDictionaryKey;192        }193    }194    for (pairs) |p| {195        try out.appendSlice(allocator, p.key);196        try out.appendSlice(allocator, p.value);197    }198    try out.append(allocator, Tag.end.byte());199}200201fn lessThanBytes(_: void, a: []u8, b: []u8) bool {202    return std.mem.order(u8, a, b) == .lt;203}204205const SemanticEncodingDomain = struct {206    representation: u8,207208    pub fn eql(a: SemanticEncodingDomain, b: SemanticEncodingDomain) bool {209        return a.representation % 2 == b.representation % 2;210    }211212    pub fn hash(self: SemanticEncodingDomain) u64 {213        return self.representation % 2;214    }215216    pub fn order(a: SemanticEncodingDomain, b: SemanticEncodingDomain) std.math.Order {217        return std.math.order(a.representation % 2, b.representation % 2);218    }219220    pub fn deinit(self: *SemanticEncodingDomain, allocator: Allocator) void {221        _ = self;222        _ = allocator;223    }224225    pub fn clone(226        self: SemanticEncodingDomain,227        allocator: Allocator,228    ) Allocator.Error!SemanticEncodingDomain {229        _ = allocator;230        return self;231    }232233    pub fn encodePacked(234        self: SemanticEncodingDomain,235        allocator: Allocator,236        out: *ArrayList,237    ) Allocator.Error!void {238        try out.append(allocator, self.representation);239    }240};241242test "writeVarint encodes 0 as a single zero byte" {243    const allocator = std.testing.allocator;244    var buf: ArrayList = .empty;245    defer buf.deinit(allocator);246    try writeVarint(allocator, &buf, 0);247    try std.testing.expectEqualSlices(u8, &[_]u8{0x00}, buf.items);248}249250test "writeVarint encodes 128 as two bytes" {251    const allocator = std.testing.allocator;252    var buf: ArrayList = .empty;253    defer buf.deinit(allocator);254    try writeVarint(allocator, &buf, 128);255    try std.testing.expectEqualSlices(u8, &[_]u8{ 0x80, 0x01 }, buf.items);256}257258test "encode bool and end-of-record are single tag bytes" {259    const allocator = std.testing.allocator;260    const V = value_mod.Value(preserves.domain.NoEmbedded);261    const true_bytes = try encode(preserves.domain.NoEmbedded, allocator, V.initBoolean(true));262    defer allocator.free(true_bytes);263    try std.testing.expectEqualSlices(u8, &[_]u8{0x81}, true_bytes);264265    const false_bytes = try encode(preserves.domain.NoEmbedded, allocator, V.initBoolean(false));266    defer allocator.free(false_bytes);267    try std.testing.expectEqualSlices(u8, &[_]u8{0x80}, false_bytes);268}269270test "packed encode rejects semantic duplicates with distinct representations" {271    const allocator = std.testing.allocator;272    const V = value_mod.Value(SemanticEncodingDomain);273    var set_items = [_]V{274        V.initEmbedded(.{ .representation = Tag.true_.byte() }),275        V.initEmbedded(.{ .representation = Tag.string.byte() }),276    };277    var entries = [_]V.DictionaryEntry{278        .{279            .key = V.initEmbedded(.{ .representation = Tag.true_.byte() }),280            .value = V.initBoolean(true),281        },282        .{283            .key = V.initEmbedded(.{ .representation = Tag.string.byte() }),284            .value = V.initBoolean(false),285        },286    };287288    try std.testing.expect(set_items[0].eql(set_items[1]));289    try std.testing.expectError(290        error.DuplicateSetElement,291        encode(SemanticEncodingDomain, allocator, V.initSet(&set_items)),292    );293    try std.testing.expectError(294        error.DuplicateDictionaryKey,295        encode(SemanticEncodingDomain, allocator, V.initDictionary(&entries)),296    );297}

1pub const packed_writer = @"packed".writer;