lib/preserves/src/embedded.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! An embedded value points to a payload of the host program and carries optional functions to
2 //! compare, hash, free and copy it. Values that hold such payloads still need equality, a total
3 //! order and a hash that agrees with equality, so sets, dictionaries and hash maps work over them.
4 //! Freeing or copying a tree has to free or copy each payload the tree owns.
5 //!
6 //! The package never sees the payload's type, so it has no way to compare, hash, free or copy the
7 //! payload by itself. Equality from one source and hashing from another can disagree, and then two
8 //! equal payloads land in different hash-map slots. Some payloads belong to the tree and die with
9 //! it, and others belong to the host program and outlive it.
10 //!
11 //! The [Preserves](https://preserves.dev/) data language lets a host program place its own values
12 //! inside Preserves data as embedded values, and the package keeps them.
13 //!
14 //! The package's value type uses a struct as the type of its embedded values (*domain*) for the
15 //! text parser, the JSON codec and every function at the package root. The struct (`AnyEmbedded`)
16 //! holds an untyped pointer to the payload and three optional parts: a table of functions, a free
17 //! function and a copy function. Equality, hash and order come together as one table of functions
18 //! (`SemanticOps`), so one owner supplies all three. Two payloads are equal only when they share
19 //! one table and that table's equality holds, and payloads with different tables order by the
20 //! table's address. The table's order must be total, its equality must hold exactly when the order
21 //! returns `.eq`, and equal payloads must hash equally. A payload with no table compares, orders
22 //! and hashes by its address, and it orders before every payload with a table. Freeing calls the
23 //! free function when there is one, and a payload without one is borrowed and left alone. Copying
24 //! calls the copy function. A payload with neither function stays shared with the copy. Copying
25 //! panics on a payload that has a free function and no copy function, because two trees would then
26 //! free one payload.
27 //!
28 //! Three functions (`parsedEmbeddedOps`, `parsedEmbeddedDeinit` and `parsedEmbeddedClone`) supply
29 //! the table and the free and copy functions for a payload that is itself a value in its own heap
30 //! cell. The text parser builds such a payload from `#:v`, the JSON reader from an `__embedded__`
31 //! member, and the function `observeRecord` from an observer yet to be embedded. The function
32 //! `toText` prints such a payload as `#:` followed by the value, and any other payload as `#:`
33 //! followed by its address in decimal. The binary reader rejects every embedded value, and the
34 //! binary writer rejects one whose type declares no `encodePacked` function, as this struct
35 //! declares none.
36 const std = @import("std");
37 const Allocator = std.mem.Allocator;
38
39 /// One table of equality, hash and order functions over untyped payload pointers. Code that embeds
40 /// its own objects fills one table per object kind, so equality, order and hash agree. Two embedded
41 /// values use the table only when both point to the same table. The table's order must be total,
42 /// its equality must hold exactly when the order returns `.eq`, and equal payloads must hash
43 /// equally. Tables are compared by address, so one table serves every payload of one kind.
44 pub const SemanticOps = struct {
45 /// Returns whether two payloads are equal. The function must return `true` exactly when `order`
46 /// returns `.eq`.
47 eql: *const fn (*anyopaque, *anyopaque) bool,
48 /// Returns the 64-bit hash of one payload. Equal payloads must hash equally.
49 hash: *const fn (*anyopaque) u64,
50 /// Returns the order of one payload against another. The order must be total.
51 order: *const fn (*anyopaque, *anyopaque) std.math.Order,
52 };
53
54 /// An embedded value that points to a payload of the host program, with optional functions to
55 /// compare, hash, free and copy it. Code that places host objects inside values uses this type, as
56 /// the text parser, the JSON codec and every function at the package root do. Every optional part
57 /// defaults to `null`, so `.{ .value = ptr }` is a borrowed payload that compares by address.
58 pub const AnyEmbedded = struct {
59 /// An untyped pointer to the payload.
60 value: *anyopaque,
61 /// The payload's table of equality, hash and order functions, or `null` to compare, order and
62 /// hash by address.
63 semantic_ops: ?*const SemanticOps = null,
64 /// The function that frees the payload, or `null` for a payload the tree borrows. `deinit`
65 /// calls it with the payload and the allocator.
66 deinit_fn: ?*const fn (*anyopaque, Allocator) void = null,
67 /// The function that copies the payload with an allocator and returns a pointer to the copy, or
68 /// `null`. A payload with a free function and no copy function makes `clone` panic.
69 clone_fn: ?*const fn (*anyopaque, Allocator) Allocator.Error!*anyopaque = null,
70
71 /// Returns whether two embedded values are equal. `Value.eql` calls it for two embedded values.
72 /// Two values with no table are equal when they point to the same payload. A value with a table
73 /// never equals one without a table or one with a different table. Two values with the same
74 /// table are equal when the table's equality says so.
75 pub fn eql(a: AnyEmbedded, b: AnyEmbedded) bool {
76 const a_ops = a.semantic_ops orelse {
77 if (b.semantic_ops != null) return false;
78 return a.value == b.value;
79 };
80 const b_ops = b.semantic_ops orelse return false;
81 if (a_ops != b_ops) return false;
82 return a_ops.eql(a.value, b.value);
83 }
84
85 /// Returns the order of one embedded value against another. `Value.compare` calls it for two
86 /// embedded values. A value with no table orders before one with a table, and two values with
87 /// no table order by payload address. Values with different tables order by the tables'
88 /// addresses, and values with the same table order by that table's order. The order is total
89 /// whenever each table's order is.
90 pub fn order(a: AnyEmbedded, b: AnyEmbedded) std.math.Order {
91 const a_ops = a.semantic_ops orelse {
92 if (b.semantic_ops != null) return .lt;
93 return std.math.order(@intFromPtr(a.value), @intFromPtr(b.value));
94 };
95 const b_ops = b.semantic_ops orelse return .gt;
96 if (a_ops != b_ops) {
97 return std.math.order(@intFromPtr(a_ops), @intFromPtr(b_ops));
98 }
99 return a_ops.order(a.value, b.value);
100 }
101
102 /// Returns the table's hash of the payload, or the payload's address when there is no table.
103 /// `Value.hash` calls it for an embedded value.
104 pub fn hash(self: AnyEmbedded) u64 {
105 if (self.semantic_ops) |ops| return ops.hash(self.value);
106 return @intFromPtr(self.value);
107 }
108
109 /// Calls the free function with the payload and `allocator` when there is one, and does nothing
110 /// otherwise. `Value.deinit` calls it for an embedded value.
111 pub fn deinit(self: *AnyEmbedded, allocator: Allocator) void {
112 if (self.deinit_fn) |deinit_payload| deinit_payload(self.value, allocator);
113 }
114
115 /// Returns a copy that keeps the same table and functions. `cloneValueDeep` calls it for an
116 /// embedded value. With a copy function, the copy points to a new payload from that function.
117 /// With no copy function and no free function, the copy points to the same payload. With a free
118 /// function and no copy function, the call panics, because two trees would then free one
119 /// payload.
120 pub fn clone(self: AnyEmbedded, allocator: Allocator) Allocator.Error!AnyEmbedded {
121 var cloned = self;
122 if (self.clone_fn) |clone_payload| {
123 cloned.value = try clone_payload(self.value, allocator);
124 return cloned;
125 }
126 if (self.deinit_fn != null) @panic("owned embedded value missing clone hook");
127 return cloned;
128 }
129 };
130
131 /// Returns one table whose equality, hash and order read each payload as a pointer to a `Value` and
132 /// call `eql`, `hash` and `compare` on it. The text parser, the JSON reader and `observeRecord`
133 /// call it when they wrap a value as an embedded payload. The table is one constant per `Value`
134 /// type, so payloads built by the text parser, the JSON reader and `observeRecord` compare with
135 /// each other. `toText` checks for this table to print the payload as a value.
136 pub fn parsedEmbeddedOps(comptime Value: type) *const SemanticOps {
137 const Impl = struct {
138 fn eql(a: *anyopaque, b: *anyopaque) bool {
139 const va: *const Value = @ptrCast(@alignCast(a));
140 const vb: *const Value = @ptrCast(@alignCast(b));
141 return va.*.eql(vb.*);
142 }
143
144 fn hash(ptr: *anyopaque) u64 {
145 const v: *const Value = @ptrCast(@alignCast(ptr));
146 return v.*.hash();
147 }
148
149 fn order(a: *anyopaque, b: *anyopaque) std.math.Order {
150 const va: *const Value = @ptrCast(@alignCast(a));
151 const vb: *const Value = @ptrCast(@alignCast(b));
152 return va.*.compare(vb.*);
153 }
154
155 const ops: SemanticOps = .{
156 .eql = &eql,
157 .hash = &hash,
158 .order = &order,
159 };
160 };
161 return &Impl.ops;
162 }
163
164 /// Returns a function that frees a payload that is a `Value` in its own heap cell: it calls
165 /// `deinit` on the value and then frees the cell. The text parser, the JSON reader and
166 /// `observeRecord` call it for the free function of a payload they wrap. The value has to own every
167 /// byte, and the cell and the value have to come from the allocator the function is given.
168 pub fn parsedEmbeddedDeinit(comptime Value: type) *const fn (*anyopaque, Allocator) void {
169 const Impl = struct {
170 fn call(ptr: *anyopaque, allocator: Allocator) void {
171 const value: *Value = @ptrCast(@alignCast(ptr));
172 value.deinit(allocator);
173 allocator.destroy(value);
174 }
175 };
176 return &Impl.call;
177 }
178
179 /// Returns a function that copies a payload that is a `Value` in its own heap cell into a new cell.
180 /// The text parser, the JSON reader and `observeRecord` call it for the copy function of a payload
181 /// they wrap. The copy owns every byte: atom bytes, integer digits, bind names, compound storage,
182 /// and nested payloads through their own copy functions. On `error.OutOfMemory` the function frees
183 /// every partial copy.
184 pub fn parsedEmbeddedClone(comptime Value: type) *const fn (*anyopaque, Allocator) Allocator.Error!*anyopaque {
185 const Impl = struct {
186 fn cloneSlice(allocator: Allocator, values: []const Value) Allocator.Error![]Value {
187 const cloned = try allocator.alloc(Value, values.len);
188 var index: usize = 0;
189 errdefer {
190 for (cloned[0..index]) |*value| value.deinit(allocator);
191 allocator.free(cloned);
192 }
193 while (index < values.len) : (index += 1) {
194 cloned[index] = try cloneValue(allocator, values[index]);
195 }
196 return cloned;
197 }
198
199 fn cloneValue(allocator: Allocator, value: Value) Allocator.Error!Value {
200 return switch (value) {
201 .boolean => |v| Value.initBoolean(v),
202 .double => |v| Value.initDouble(v),
203 .signed_integer => |v| Value.initSignedInteger(try v.clone(allocator)),
204 .string => |v| try Value.initString(allocator, v),
205 .byte_string => |v| try Value.initByteString(allocator, v),
206 .symbol => |v| try Value.initSymbol(allocator, v),
207 .record => |record| blk: {
208 const label = try cloneValue(allocator, record.label.*);
209 errdefer {
210 var owned = label;
211 owned.deinit(allocator);
212 }
213 const fields = try cloneSlice(allocator, record.fields);
214 errdefer {
215 for (fields) |*field| field.deinit(allocator);
216 allocator.free(fields);
217 }
218 break :blk try Value.initRecord(allocator, label, fields);
219 },
220 .sequence => |items| Value.initSequence(try cloneSlice(allocator, items)),
221 .set => |items| Value.initSet(try cloneSlice(allocator, items)),
222 .dictionary => |entries| blk: {
223 const cloned = try allocator.alloc(Value.DictionaryEntry, entries.len);
224 var index: usize = 0;
225 errdefer {
226 for (cloned[0..index]) |*entry| {
227 entry.key.deinit(allocator);
228 entry.value.deinit(allocator);
229 }
230 allocator.free(cloned);
231 }
232 while (index < entries.len) : (index += 1) {
233 var key = try cloneValue(allocator, entries[index].key);
234 var key_owned = true;
235 errdefer if (key_owned) key.deinit(allocator);
236
237 cloned[index] = .{
238 .key = key,
239 .value = try cloneValue(allocator, entries[index].value),
240 };
241 key_owned = false;
242 }
243 break :blk Value.initDictionary(cloned);
244 },
245 .embedded => |embedded| Value.initEmbedded(try embedded.clone(allocator)),
246 .discard => .{ .discard = {} },
247 .capture => |inner| blk: {
248 const cloned = try allocator.create(Value);
249 errdefer allocator.destroy(cloned);
250 cloned.* = try cloneValue(allocator, inner.*);
251 break :blk .{ .capture = cloned };
252 },
253 .bind => |bind| blk: {
254 const pattern = try allocator.create(Value);
255 errdefer allocator.destroy(pattern);
256 pattern.* = try cloneValue(allocator, bind.pattern.*);
257 errdefer pattern.deinit(allocator);
258 const name = try allocator.dupe(u8, bind.name);
259 break :blk .{ .bind = .{ .name = name, .pattern = pattern } };
260 },
261 .rest_pattern => |rest| blk: {
262 const prefix = try cloneSlice(allocator, rest.prefix);
263 errdefer {
264 for (prefix) |*item| item.deinit(allocator);
265 allocator.free(prefix);
266 }
267 const rest_clone = try allocator.create(Value);
268 errdefer allocator.destroy(rest_clone);
269 rest_clone.* = try cloneValue(allocator, rest.rest.*);
270 break :blk .{ .rest_pattern = .{ .prefix = prefix, .rest = rest_clone } };
271 },
272 };
273 }
274
275 fn call(ptr: *anyopaque, allocator: Allocator) Allocator.Error!*anyopaque {
276 const original: *const Value = @ptrCast(@alignCast(ptr));
277 const cloned = try allocator.create(Value);
278 errdefer allocator.destroy(cloned);
279 cloned.* = try cloneValue(allocator, original.*);
280 return @ptrCast(cloned);
281 }
282 };
283 return &Impl.call;
284 }
285
286 const domain_mod = @import("domain.zig");
287 const value_mod = @import("value.zig");
288 const containers_mod = @import("containers.zig");
289
290 const ExactU32 = struct {
291 fn eql(a: *anyopaque, b: *anyopaque) bool {
292 const left: *const u32 = @ptrCast(@alignCast(a));
293 const right: *const u32 = @ptrCast(@alignCast(b));
294 return left.* == right.*;
295 }
296
297 fn hash(value: *anyopaque) u64 {
298 const payload: *const u32 = @ptrCast(@alignCast(value));
299 return payload.*;
300 }
301
302 fn order(a: *anyopaque, b: *anyopaque) std.math.Order {
303 const left: *const u32 = @ptrCast(@alignCast(a));
304 const right: *const u32 = @ptrCast(@alignCast(b));
305 return std.math.order(left.*, right.*);
306 }
307
308 const ops: SemanticOps = .{
309 .eql = &eql,
310 .hash = &hash,
311 .order = &order,
312 };
313 };
314
315 const ParityU32 = struct {
316 fn eql(a: *anyopaque, b: *anyopaque) bool {
317 const left: *const u32 = @ptrCast(@alignCast(a));
318 const right: *const u32 = @ptrCast(@alignCast(b));
319 return left.* % 2 == right.* % 2;
320 }
321
322 fn hash(value: *anyopaque) u64 {
323 const payload: *const u32 = @ptrCast(@alignCast(value));
324 return payload.* % 2;
325 }
326
327 fn order(a: *anyopaque, b: *anyopaque) std.math.Order {
328 const left: *const u32 = @ptrCast(@alignCast(a));
329 const right: *const u32 = @ptrCast(@alignCast(b));
330 return std.math.order(left.* % 2, right.* % 2);
331 }
332
333 const ops: SemanticOps = .{
334 .eql = &eql,
335 .hash = &hash,
336 .order = &order,
337 };
338 };
339
340 test "AnyEmbedded satisfies the Domain contract" {
341 comptime domain_mod.assertIsDomain(AnyEmbedded);
342 }
343
344 test "AnyEmbedded falls back to pointer identity" {
345 var a: u32 = 1;
346 var b: u32 = 2;
347 const ea: AnyEmbedded = .{ .value = &a };
348 const eb: AnyEmbedded = .{ .value = &b };
349 const ea2: AnyEmbedded = .{ .value = &a };
350
351 try std.testing.expect(ea.eql(ea2));
352 try std.testing.expect(!ea.eql(eb));
353 try std.testing.expectEqual(ea.hash(), ea2.hash());
354 try std.testing.expect(ea.hash() != eb.hash());
355 const ord = ea.order(eb);
356 try std.testing.expect(ord != .eq);
357 }
358
359 test "AnyEmbedded semantic operations are structurally bundled" {
360 try std.testing.expect(@hasField(AnyEmbedded, "semantic_ops"));
361 try std.testing.expect(!@hasField(AnyEmbedded, "eql_fn"));
362 try std.testing.expect(!@hasField(AnyEmbedded, "hash_fn"));
363 try std.testing.expect(!@hasField(AnyEmbedded, "order_fn"));
364 try std.testing.expect(@hasField(SemanticOps, "eql"));
365 try std.testing.expect(@hasField(SemanticOps, "hash"));
366 try std.testing.expect(@hasField(SemanticOps, "order"));
367 }
368
369 test "AnyEmbedded dispatches through one semantic bundle" {
370 var payload_a: u32 = 5;
371 var payload_b: u32 = 5;
372 const ea: AnyEmbedded = .{
373 .value = &payload_a,
374 .semantic_ops = &ExactU32.ops,
375 };
376 const eb: AnyEmbedded = .{
377 .value = &payload_b,
378 .semantic_ops = &ExactU32.ops,
379 };
380 try std.testing.expect(ea.eql(eb));
381 try std.testing.expectEqual(@as(u64, 5), ea.hash());
382 try std.testing.expectEqual(ea.hash(), eb.hash());
383 try std.testing.expectEqual(std.math.Order.eq, ea.order(eb));
384 }
385
386 test "AnyEmbedded keeps different semantic bundles disjoint and symmetric" {
387 var exact_payload: u32 = 2;
388 var parity_payload: u32 = 4;
389 const exact = AnyEmbedded{ .value = &exact_payload, .semantic_ops = &ExactU32.ops };
390 const parity = AnyEmbedded{ .value = &parity_payload, .semantic_ops = &ParityU32.ops };
391
392 try std.testing.expect(!exact.eql(parity));
393 try std.testing.expect(!parity.eql(exact));
394 const forward = exact.order(parity);
395 const reverse = parity.order(exact);
396 try std.testing.expect(forward != .eq);
397 try std.testing.expect(reverse != .eq);
398 try std.testing.expectEqual(forward == .lt, reverse == .gt);
399
400 const opaque_value = AnyEmbedded{ .value = &exact_payload };
401 try std.testing.expect(!opaque_value.eql(exact));
402 try std.testing.expect(!exact.eql(opaque_value));
403 try std.testing.expectEqual(std.math.Order.lt, opaque_value.order(exact));
404 try std.testing.expectEqual(std.math.Order.gt, exact.order(opaque_value));
405 }
406
407 test "parsed embedded clone and deinit own nested values" {
408 const V = value_mod.Value(AnyEmbedded);
409 const allocator = std.testing.allocator;
410
411 const original_payload = try allocator.create(V);
412 original_payload.* = try V.initString(allocator, "payload");
413 var embedded = AnyEmbedded{
414 .value = @ptrCast(original_payload),
415 .semantic_ops = parsedEmbeddedOps(V),
416 .deinit_fn = parsedEmbeddedDeinit(V),
417 .clone_fn = parsedEmbeddedClone(V),
418 };
419 defer embedded.deinit(allocator);
420
421 var cloned = try embedded.clone(allocator);
422 defer cloned.deinit(allocator);
423
424 try std.testing.expect(embedded.value != cloned.value);
425 const cloned_payload: *const V = @ptrCast(@alignCast(cloned.value));
426 try std.testing.expect(cloned_payload.* == .string);
427 try std.testing.expectEqualStrings("payload", cloned_payload.string);
428 }
429
430 fn checkParsedEmbeddedBindCloneAllocationFailures(allocator: Allocator) !void {
431 const V = value_mod.Value(AnyEmbedded);
432 var pattern = V{ .string = "pattern" };
433 var source_value = V{ .bind = .{ .name = "name", .pattern = &pattern } };
434 const source = AnyEmbedded{
435 .value = &source_value,
436 .semantic_ops = parsedEmbeddedOps(V),
437 .deinit_fn = parsedEmbeddedDeinit(V),
438 .clone_fn = parsedEmbeddedClone(V),
439 };
440 var cloned = try source.clone(allocator);
441 defer cloned.deinit(allocator);
442
443 const cloned_value: *const V = @ptrCast(@alignCast(cloned.value));
444 try std.testing.expect(cloned_value.* == .bind);
445 try std.testing.expectEqualStrings("name", cloned_value.bind.name);
446 try std.testing.expectEqualStrings("pattern", cloned_value.bind.pattern.string);
447 }
448
449 test "parsed embedded bind clone releases every allocation failure path" {
450 try std.testing.checkAllAllocationFailures(
451 std.testing.allocator,
452 checkParsedEmbeddedBindCloneAllocationFailures,
453 .{},
454 );
455 }
456
457 test "semantic embedded values remain lawful through nested sets and maps" {
458 const V = value_mod.Value(AnyEmbedded);
459 const Map = containers_mod.ValueHashMap(AnyEmbedded);
460 const allocator = std.testing.allocator;
461 var left_payloads = [_]u32{ 1, 2 };
462 var right_payloads = [_]u32{ 2, 1 };
463 var left_items = [_]V{
464 V.initEmbedded(.{ .value = &left_payloads[0], .semantic_ops = &ExactU32.ops }),
465 V.initEmbedded(.{ .value = &left_payloads[1], .semantic_ops = &ExactU32.ops }),
466 };
467 var right_items = [_]V{
468 V.initEmbedded(.{ .value = &right_payloads[0], .semantic_ops = &ExactU32.ops }),
469 V.initEmbedded(.{ .value = &right_payloads[1], .semantic_ops = &ExactU32.ops }),
470 };
471 const left = V.initSet(&left_items);
472 const right = V.initSet(&right_items);
473
474 try std.testing.expect(left.eql(right));
475 try std.testing.expectEqual(std.math.Order.eq, left.compare(right));
476 try std.testing.expectEqual(left.hash(), right.hash());
477
478 var map: Map = .{};
479 defer map.deinit(allocator);
480 try map.put(allocator, left, V.initBoolean(true));
481 try std.testing.expect(map.get(right).?.eql(V.initBoolean(true)));
482 }