tiny.preserves.embedded_mod

1//! An embedded value points to a payload of the host program and carries optional functions to2//! compare, hash, free and copy it. Values that hold such payloads still need equality, a total3//! 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 the7//! payload by itself. Equality from one source and hashing from another can disagree, and then two8//! equal payloads land in different hash-map slots. Some payloads belong to the tree and die with9//! 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 values12//! 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 the15//! 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 free17//! function and a copy function. Equality, hash and order come together as one table of functions18//! (`SemanticOps`), so one owner supplies all three. Two payloads are equal only when they share19//! one table and that table's equality holds, and payloads with different tables order by the20//! table's address. The table's order must be total, its equality must hold exactly when the order21//! returns `.eq`, and equal payloads must hash equally. A payload with no table compares, orders22//! and hashes by its address, and it orders before every payload with a table. Freeing calls the23//! free function when there is one, and a payload without one is borrowed and left alone. Copying24//! calls the copy function. A payload with neither function stays shared with the copy. Copying25//! panics on a payload that has a free function and no copy function, because two trees would then26//! free one payload.27//!28//! Three functions (`parsedEmbeddedOps`, `parsedEmbeddedDeinit` and `parsedEmbeddedClone`) supply29//! the table and the free and copy functions for a payload that is itself a value in its own heap30//! 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 function32//! `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 the34//! binary writer rejects one whose type declares no `encodePacked` function, as this struct35//! declares none.36const std = @import("std");37const Allocator = std.mem.Allocator;3839/// One table of equality, hash and order functions over untyped payload pointers. Code that embeds40/// its own objects fills one table per object kind, so equality, order and hash agree. Two embedded41/// 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 hash43/// equally. Tables are compared by address, so one table serves every payload of one kind.44pub 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};5354/// An embedded value that points to a payload of the host program, with optional functions to55/// compare, hash, free and copy it. Code that places host objects inside values uses this type, as56/// the text parser, the JSON codec and every function at the package root do. Every optional part57/// defaults to `null`, so `.{ .value = ptr }` is a borrowed payload that compares by address.58pub 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 and62    /// 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, or68    /// `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,7071    /// 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 table73    /// never equals one without a table or one with a different table. Two values with the same74    /// 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    }8485    /// Returns the order of one embedded value against another. `Value.compare` calls it for two86    /// embedded values. A value with no table orders before one with a table, and two values with87    /// 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 total89    /// 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    }101102    /// 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    }108109    /// Calls the free function with the payload and `allocator` when there is one, and does nothing110    /// 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    }114115    /// Returns a copy that keeps the same table and functions. `cloneValueDeep` calls it for an116    /// 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 free118    /// function and no copy function, the call panics, because two trees would then free one119    /// 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};130131/// Returns one table whose equality, hash and order read each payload as a pointer to a `Value` and132/// 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 with135/// each other. `toText` checks for this table to print the payload as a value.136pub 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        }143144        fn hash(ptr: *anyopaque) u64 {145            const v: *const Value = @ptrCast(@alignCast(ptr));146            return v.*.hash();147        }148149        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        }154155        const ops: SemanticOps = .{156            .eql = &eql,157            .hash = &hash,158            .order = &order,159        };160    };161    return &Impl.ops;162}163164/// Returns a function that frees a payload that is a `Value` in its own heap cell: it calls165/// `deinit` on the value and then frees the cell. The text parser, the JSON reader and166/// `observeRecord` call it for the free function of a payload they wrap. The value has to own every167/// byte, and the cell and the value have to come from the allocator the function is given.168pub 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}178179/// 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 payload181/// 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 frees183/// every partial copy.184pub 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        }198199        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);236237                        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        }274275        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}285286const domain_mod = @import("domain.zig");287const value_mod = @import("value.zig");288const containers_mod = @import("containers.zig");289290const 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    }296297    fn hash(value: *anyopaque) u64 {298        const payload: *const u32 = @ptrCast(@alignCast(value));299        return payload.*;300    }301302    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    }307308    const ops: SemanticOps = .{309        .eql = &eql,310        .hash = &hash,311        .order = &order,312    };313};314315const 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    }321322    fn hash(value: *anyopaque) u64 {323        const payload: *const u32 = @ptrCast(@alignCast(value));324        return payload.* % 2;325    }326327    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    }332333    const ops: SemanticOps = .{334        .eql = &eql,335        .hash = &hash,336        .order = &order,337    };338};339340test "AnyEmbedded satisfies the Domain contract" {341    comptime domain_mod.assertIsDomain(AnyEmbedded);342}343344test "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 };350351    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}358359test "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}368369test "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}385386test "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 };391392    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);399400    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}406407test "parsed embedded clone and deinit own nested values" {408    const V = value_mod.Value(AnyEmbedded);409    const allocator = std.testing.allocator;410411    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);420421    var cloned = try embedded.clone(allocator);422    defer cloned.deinit(allocator);423424    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}429430fn 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);442443    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}448449test "parsed embedded bind clone releases every allocation failure path" {450    try std.testing.checkAllAllocationFailures(451        std.testing.allocator,452        checkParsedEmbeddedBindCloneAllocationFailures,453        .{},454    );455}456457test "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);473474    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());477478    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}

1pub const embedded_mod = @import("embedded.zig");