tiny.preserves.ownership

1//! Calls that copy a whole value tree and free one, each by the rule that matches how the tree was2//! built. A tree can own every byte, own its structure while borrowing its text, or own only its3//! outermost storage, and each case needs its own free.4//!5//! Nothing in a value records which of its bytes it owns, so the caller has to pick the free that6//! matches how the tree was built. A Lean model of parser results proves that when a borrowed7//! symbol and an owned symbol look the same, no single cleanup frees exactly the owned bytes of8//! both. The same model proves that cleanup is exact when every resource in a result is owned.9//!10//! The package keeps the values of the [Preserves](https://preserves.dev/) data language and11//! changes one thing for this file: the caller owns and frees all storage.12//!13//! `cloneValueDeep` copies a tree into storage that owns every byte, so the copy takes the one full14//! free, `Value.deinit`, whatever the original borrowed. `freeValueDeep` frees the structure of a15//! tree and leaves its text, for trees that own their structure and borrow their strings and16//! symbols. `freeValue` frees one level of storage, the level the root constructors allocate.17//!18//! - *domain*: the type of the embedded values19//! - *pattern form*: one of four value kinds that describe a match20const std = @import("std");21const Allocator = std.mem.Allocator;2223const value_mod = @import("value.zig");24const domain_mod = @import("domain.zig");2526pub const Value = value_mod.Value;27pub const NoEmbedded = domain_mod.NoEmbedded;2829/// Copies `val` all the way down into storage from `alloc`: atom bytes, integer digits, bind names,30/// compound storage and embedded values. Code that keeps a value past the life of its source calls31/// it for a copy that owns every byte, as the text reader and the property tests do. A set or32/// dictionary copy keeps the original's storage order. Each embedded value is copied by its type's33/// `clone`. For `AnyEmbedded` that calls the payload's copy function, shares a payload that has34/// neither a copy nor a free function, and panics on one that has a free function and no copy35/// function. `Value.deinit` with `alloc` frees the result. On `error.OutOfMemory` the call frees36/// every partial copy and leaves `val` unchanged.37pub fn cloneValueDeep(comptime D: type, alloc: Allocator, val: Value(D)) Allocator.Error!Value(D) {38    domain_mod.assertIsDomain(D);39    const V = Value(D);40    return switch (val) {41        .boolean => |v| V.initBoolean(v),42        .double => |v| V.initDouble(v),43        .signed_integer => |si| V.initSignedInteger(try si.clone(alloc)),44        .string => |s| try V.initString(alloc, s),45        .byte_string => |s| try V.initByteString(alloc, s),46        .symbol => |s| try V.initSymbol(alloc, s),47        .record => |record| blk: {48            var label = try cloneValueDeep(D, alloc, record.label.*);49            errdefer label.deinit(alloc);5051            const fields = try alloc.alloc(V, record.fields.len);52            var filled: usize = 0;53            errdefer {54                while (filled > 0) {55                    filled -= 1;56                    fields[filled].deinit(alloc);57                }58                alloc.free(fields);59            }60            while (filled < record.fields.len) : (filled += 1) {61                fields[filled] = try cloneValueDeep(D, alloc, record.fields[filled]);62            }63            break :blk try V.initRecord(alloc, label, fields);64        },65        .sequence => |items| blk: {66            const cloned = try alloc.alloc(V, items.len);67            var filled: usize = 0;68            errdefer {69                while (filled > 0) {70                    filled -= 1;71                    cloned[filled].deinit(alloc);72                }73                alloc.free(cloned);74            }75            while (filled < items.len) : (filled += 1) {76                cloned[filled] = try cloneValueDeep(D, alloc, items[filled]);77            }78            break :blk V.initSequence(cloned);79        },80        .set => |items| blk: {81            const cloned = try alloc.alloc(V, items.len);82            var filled: usize = 0;83            errdefer {84                while (filled > 0) {85                    filled -= 1;86                    cloned[filled].deinit(alloc);87                }88                alloc.free(cloned);89            }90            while (filled < items.len) : (filled += 1) {91                cloned[filled] = try cloneValueDeep(D, alloc, items[filled]);92            }93            break :blk V.initSet(cloned);94        },95        .dictionary => |entries| blk: {96            const cloned = try alloc.alloc(V.DictionaryEntry, entries.len);97            var filled: usize = 0;98            errdefer {99                while (filled > 0) {100                    filled -= 1;101                    cloned[filled].key.deinit(alloc);102                    cloned[filled].value.deinit(alloc);103                }104                alloc.free(cloned);105            }106            while (filled < entries.len) : (filled += 1) {107                var key = try cloneValueDeep(D, alloc, entries[filled].key);108                errdefer key.deinit(alloc);109                cloned[filled].value = try cloneValueDeep(D, alloc, entries[filled].value);110                cloned[filled].key = key;111            }112            break :blk V.initDictionary(cloned);113        },114        .embedded => |embedded| V.initEmbedded(try embedded.clone(alloc)),115        .discard => .{ .discard = {} },116        .capture => |inner| blk: {117            const ptr = try alloc.create(V);118            errdefer alloc.destroy(ptr);119            ptr.* = try cloneValueDeep(D, alloc, inner.*);120            break :blk .{ .capture = ptr };121        },122        .bind => |binding| blk: {123            const ptr = try alloc.create(V);124            errdefer alloc.destroy(ptr);125            ptr.* = try cloneValueDeep(D, alloc, binding.pattern.*);126            errdefer ptr.deinit(alloc);127            break :blk .{128                .bind = .{129                    .name = try alloc.dupe(u8, binding.name),130                    .pattern = ptr,131                },132            };133        },134        .rest_pattern => |rest| blk: {135            const prefix = try alloc.alloc(V, rest.prefix.len);136            var filled: usize = 0;137            errdefer {138                while (filled > 0) {139                    filled -= 1;140                    prefix[filled].deinit(alloc);141                }142                alloc.free(prefix);143            }144            while (filled < rest.prefix.len) : (filled += 1) {145                prefix[filled] = try cloneValueDeep(D, alloc, rest.prefix[filled]);146            }147148            const rest_ptr = try alloc.create(V);149            errdefer alloc.destroy(rest_ptr);150            rest_ptr.* = try cloneValueDeep(D, alloc, rest.rest.*);151            break :blk .{ .rest_pattern = .{ .prefix = prefix, .rest = rest_ptr } };152        },153    };154}155156/// Frees the outer storage of one compound value and nothing below it. Code that built a value with157/// the root constructors calls it at the end, as the README's example does. The outer storage is a158/// record's label cell and field slice, the slice of a sequence, set or dictionary, the inner cell159/// of a capture or bind, and a rest pattern's prefix slice and rest cell. The call matches the root160/// constructors, which allocate that outer storage and borrow everything below it. The call frees161/// no child value, no atom bytes and no embedded payload, and it does nothing to an atom or an162/// embedded value.163pub fn freeValue(comptime D: type, alloc: Allocator, val: Value(D)) void {164    domain_mod.assertIsDomain(D);165    switch (val) {166        .record => |r| {167            alloc.destroy(r.label);168            alloc.free(r.fields);169        },170        .sequence => |s| alloc.free(s),171        .set => |s| alloc.free(s),172        .dictionary => |d| alloc.free(d),173        .capture => |inner| alloc.destroy(inner),174        .bind => |b| alloc.destroy(b.pattern),175        .rest_pattern => |rp| {176            alloc.free(rp.prefix);177            alloc.destroy(rp.rest);178        },179        else => {},180    }181}182183/// Frees a value's compound storage all the way down: records, sequences, sets, dictionaries,184/// captures, binds and rest patterns. The pattern conversions and `toText` call it for trees whose185/// structure they own and whose text they borrow. The call also frees the digits of every integer186/// too large for 128 bits. The call leaves the bytes of strings, byte strings and symbols, the187/// names of binds, and embedded payloads. `Value.deinit` frees all of those as well, so it fits188/// only a tree whose every byte comes from `alloc`.189pub fn freeValueDeep(comptime D: type, alloc: Allocator, val: Value(D)) void {190    domain_mod.assertIsDomain(D);191    switch (val) {192        .signed_integer => |si| {193            var copy = si;194            copy.deinit(alloc);195        },196        .record => |r| {197            freeValueDeep(D, alloc, r.label.*);198            for (r.fields) |f| freeValueDeep(D, alloc, f);199            alloc.destroy(r.label);200            alloc.free(r.fields);201        },202        .sequence => |s| {203            for (s) |item| freeValueDeep(D, alloc, item);204            alloc.free(s);205        },206        .set => |s| {207            for (s) |item| freeValueDeep(D, alloc, item);208            alloc.free(s);209        },210        .dictionary => |d| {211            for (d) |entry| {212                freeValueDeep(D, alloc, entry.key);213                freeValueDeep(D, alloc, entry.value);214            }215            alloc.free(d);216        },217        .capture => |inner| {218            freeValueDeep(D, alloc, inner.*);219            alloc.destroy(inner);220        },221        .bind => |b| {222            freeValueDeep(D, alloc, b.pattern.*);223            alloc.destroy(b.pattern);224        },225        .rest_pattern => |rp| {226            for (rp.prefix) |item| freeValueDeep(D, alloc, item);227            alloc.free(rp.prefix);228            freeValueDeep(D, alloc, rp.rest.*);229            alloc.destroy(rp.rest);230        },231        else => {},232    }233}234235test "freeValue frees outer slice only" {236    const V = Value(NoEmbedded);237    const allocator = std.testing.allocator;238    const fields = try allocator.alloc(V, 2);239    fields[0] = V.initI128(1);240    fields[1] = V.initI128(2);241    const label_ptr = try allocator.create(V);242    label_ptr.* = V.initBoolean(true);243    const r: V = .{ .record = .{ .label = label_ptr, .fields = fields } };244    freeValue(NoEmbedded, allocator, r);245}246247test "cloneValueDeep owns copied atom and compound storage" {248    const V = Value(NoEmbedded);249    const allocator = std.testing.allocator;250    const dict_entries = try allocator.alloc(V.DictionaryEntry, 1);251    errdefer allocator.free(dict_entries);252    dict_entries[0] = .{ .key = V{ .symbol = "key" }, .value = V{ .byte_string = "bytes" } };253254    const fields = try allocator.alloc(V, 2);255    errdefer allocator.free(fields);256    fields[0] = V{ .string = "name" };257    fields[1] = V.initDictionary(dict_entries);258259    const original = try V.initRecord(allocator, V{ .symbol = "shape" }, fields);260    defer {261        allocator.destroy(original.record.label);262        allocator.free(original.record.fields);263        allocator.free(dict_entries);264    }265266    var cloned = try cloneValueDeep(NoEmbedded, allocator, original);267    defer cloned.deinit(allocator);268269    try std.testing.expect(original.eql(cloned));270}271272test "cloneValueDeep owns copied pattern form storage" {273    const V = Value(NoEmbedded);274    const allocator = std.testing.allocator;275276    const name = try allocator.dupe(u8, "slot");277    defer allocator.free(name);278279    const capture_ptr = try allocator.create(V);280    capture_ptr.* = .{ .discard = {} };281282    const bind_ptr = try allocator.create(V);283    bind_ptr.* = .{ .capture = capture_ptr };284285    const prefix = try allocator.alloc(V, 2);286    prefix[0] = V.initI128(1);287    prefix[1] = .{ .bind = .{ .name = name, .pattern = bind_ptr } };288289    const rest_ptr = try allocator.create(V);290    rest_ptr.* = V{ .symbol = "tail" };291292    const original: V = .{ .rest_pattern = .{ .prefix = prefix, .rest = rest_ptr } };293    var cloned = try cloneValueDeep(NoEmbedded, allocator, original);294    defer cloned.deinit(allocator);295296    try std.testing.expect(original.eql(cloned));297    freeValueDeep(NoEmbedded, allocator, original);298    try std.testing.expectEqualStrings("slot", cloned.rest_pattern.prefix[1].bind.name);299}300301test "freeValueDeep frees compound tree but skips string/symbol slices" {302    const V = Value(NoEmbedded);303    const allocator = std.testing.allocator;304    const inner_items = try allocator.alloc(V, 2);305    inner_items[0] = V{ .string = "borrowed-a" };306    inner_items[1] = V{ .symbol = "borrowed-b" };307    const inner_seq = V{ .sequence = inner_items };308309    const outer_items = try allocator.alloc(V, 1);310    outer_items[0] = inner_seq;311    const label_ptr = try allocator.create(V);312    label_ptr.* = V{ .symbol = "Label" };313    const r: V = .{ .record = .{ .label = label_ptr, .fields = outer_items } };314315    freeValueDeep(NoEmbedded, allocator, r);316}

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