lib/preserves/src/packed/writer.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! Writes values as bytes in a binary encoding. A caller that hashes or compares encoded bytes
2 //! 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 of
4 //! 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 by
6 //! their encoded bytes, and writes each integer in its shortest two's-complement form. It refuses
7 //! what the packed reader could not read back as the same value: repeated set elements or
8 //! dictionary keys, and discards, captures, binds and rest patterns. It writes an embedded value
9 //! only when the type of the embedded values supplies `encodePacked`, and `NoEmbedded` and
10 //! `AnyEmbedded` both lack it.
11 const std = @import("std");
12 const Allocator = std.mem.Allocator;
13 const ArrayList = std.ArrayListUnmanaged(u8);
14
15 const preserves = @import("../root.zig");
16
17 const value_mod = preserves.value;
18 const integer_mod = preserves.integer_mod;
19
20 const constants = @import("constants.zig");
21 pub const Tag = constants.Tag;
22
23 /// The errors `encode`, `writeValue` and `writeVarint` return, so the caller can switch on them or
24 /// fold them into its own error set. `EmbeddedNotSupported` means the value holds an embedded value
25 /// whose type lacks `encodePacked`. `DuplicateSetElement` and `DuplicateDictionaryKey` mean a set
26 /// holds two equal elements, or a dictionary two equal keys, by value equality or by equal
27 /// encodings. `PatternFormNotEncodable` means the value holds a discard, capture, bind or rest
28 /// pattern. `OutOfMemory` means an allocation failed.
29 pub const EncodeError = Allocator.Error || error{
30 EmbeddedNotSupported,
31 DuplicateSetElement,
32 DuplicateDictionaryKey,
33 PatternFormNotEncodable,
34 };
35
36 /// Returns the binary encoding of `value` as new bytes allocated with `allocator`, for code that
37 /// stores, sends or fingerprints a value. The caller owns the bytes and frees them with
38 /// `allocator`. On any error the call frees everything it allocated. Encoding a value that `decode`
39 /// returned gives back the bytes `decode` read.
40 pub 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 }
46
47 /// Appends the binary encoding of `value` to `out`, growing `out` with `allocator`. `encode` calls
48 /// it with a fresh buffer, and code that packs more than one value into one buffer can call it
49 /// directly. On error, the bytes appended before the failure stay in `out`, so the caller discards
50 /// the buffer. Each set element and each dictionary entry is encoded into its own buffer, then
51 /// sorted by those bytes before it is appended. A double is written as the tag 0x87, the length 8
52 /// and its eight bytes, big-endian. Strings, byte strings, symbols and integers are written as a
53 /// tag, a varint length and the payload. Records and sequences are written as a tag, their parts in
54 /// order and the end marker.
55 pub 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 }
89
90 /// Appends `value_in` to `out` as a varint: seven bits per byte, low bits first, with the high bit
91 /// set on every byte but the last. The writer calls it for every length prefix. Zero is written as
92 /// the single byte 0x00, and 128 as 0x80 0x01. The packed reader's `readVarint` reads this form
93 /// back. The only error is running out of memory.
94 pub 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 }
104
105 fn 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 }
110
111 fn 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 }
119
120 fn 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 }
125
126 fn 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 }
155
156 fn 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 }
200
201 fn lessThanBytes(_: void, a: []u8, b: []u8) bool {
202 return std.mem.order(u8, a, b) == .lt;
203 }
204
205 const SemanticEncodingDomain = struct {
206 representation: u8,
207
208 pub fn eql(a: SemanticEncodingDomain, b: SemanticEncodingDomain) bool {
209 return a.representation % 2 == b.representation % 2;
210 }
211
212 pub fn hash(self: SemanticEncodingDomain) u64 {
213 return self.representation % 2;
214 }
215
216 pub fn order(a: SemanticEncodingDomain, b: SemanticEncodingDomain) std.math.Order {
217 return std.math.order(a.representation % 2, b.representation % 2);
218 }
219
220 pub fn deinit(self: *SemanticEncodingDomain, allocator: Allocator) void {
221 _ = self;
222 _ = allocator;
223 }
224
225 pub fn clone(
226 self: SemanticEncodingDomain,
227 allocator: Allocator,
228 ) Allocator.Error!SemanticEncodingDomain {
229 _ = allocator;
230 return self;
231 }
232
233 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 };
241
242 test "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 }
249
250 test "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 }
257
258 test "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);
264
265 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 }
269
270 test "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 };
287
288 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 }