tiny.preserves.patterns_mod

1//! Converts patterns between their in-memory form and a wire form made of plain records, reads the2//! pattern and the observer out of a record that asks to observe a pattern, and walks the embedded3//! values in a value.4//!5//! A pattern that travels between peers has to be written as a plain value and read back as the6//! same pattern. A caller also needs to know which parts of a converted value it frees. The binary7//! syntax has no tag for an in-memory pattern, and the packed writer refuses one.8//!9//! The package keeps the patterns of the [Preserves](https://preserves.dev/) data language, which10//! comes from the Syndicate ecosystem. Each in-memory pattern becomes a record: `<_>` for the11//! discard, `<bind P>` for a capture, `<lit v>` for an atom or set, and `<group <rec L> {…}>`,12//! `<group <arr> {…}>` or `<group <dict> {…}>` for a record, sequence or dictionary whose items are13//! patterns. `patternToPreserves` writes that wire form, `preservesToPattern` reads it back, and14//! `preservePattern` reads it too and never reports a failure. The conversions allocate new15//! records, sequences, dictionaries and pattern cells, and leave strings, symbols, byte strings and16//! bind names pointing into their input. A bind loses its name on the wire, because17//! `patternToPreserves` writes it as `<bind P>`, which reads back as a capture.18const std = @import("std");19const Allocator = std.mem.Allocator;2021const value_mod = @import("value.zig");22const domain_mod = @import("domain.zig");23const symbols_mod = @import("symbols.zig");24const constructors_mod = @import("constructors.zig");25const ownership = @import("ownership.zig");26const predicates_mod = @import("predicates.zig");27const embedded_mod = @import("embedded.zig");2829pub const Value = value_mod.Value;30pub const NoEmbedded = domain_mod.NoEmbedded;31pub const AnyEmbedded = embedded_mod.AnyEmbedded;3233/// Returns a namespace of pattern conversions for `Value(D)`. Code whose values hold embedded34/// values of one type calls it once at compile time, for every pattern conversion over those35/// values. The type `D` has to provide `eql`, `order`, `deinit` and `clone`, or the call is a36/// compile error. `conversions` and `any_conversions` are its two instances.37pub fn Conversions(comptime D: type) type {38    domain_mod.assertIsDomain(D);39    const V = Value(D);40    const H = constructors_mod.Constructors(D);41    return struct {42        const Self = @This();4344        /// Returns `value` unchanged. The call allocates nothing.45        pub fn preserve(alloc: Allocator, value: V) V {46            _ = alloc;47            return value;48        }4950        /// Returns the in-memory pattern that the wire value `pattern` spells, allocated with51        /// `alloc`. Code receiving a pattern in wire form calls it for an in-memory pattern. The52        /// symbol `_` and the record `<_>` become the discard pattern. `<bind P>` becomes a capture53        /// of `P`, and `<lit v>` becomes `v` itself. `<group <rec L> {…}>` becomes a record labeled54        /// `L`, and `<group <arr> {…}>` a sequence, each item taken in key order from the55        /// dictionary. `<group <dict> {…}>` becomes a dictionary with the same keys. Other records,56        /// sequences and dictionaries keep their shape, and their parts are converted in turn. The57        /// result shares atoms and `<lit>` contents with `pattern`, so `pattern` has to outlive it.58        /// When an allocation fails, the call returns the unconverted input at that level and keeps59        /// what it already allocated. The package's tests build its result in an arena and free the60        /// arena whole.61        pub fn preservePattern(alloc: Allocator, pattern: V) V {62            switch (pattern) {63                .discard => return pattern,64                .capture => |inner| {65                    const new = alloc.create(V) catch return pattern;66                    new.* = Self.preservePattern(alloc, inner.*);67                    return .{ .capture = new };68                },69                .bind => |b| {70                    const new_pat = alloc.create(V) catch return pattern;71                    new_pat.* = Self.preservePattern(alloc, b.pattern.*);72                    return .{ .bind = .{ .name = b.name, .pattern = new_pat } };73                },74                .rest_pattern => |rp| {75                    const new_prefix = alloc.alloc(V, rp.prefix.len) catch return pattern;76                    for (rp.prefix, 0..) |item, i| {77                        new_prefix[i] = Self.preservePattern(alloc, item);78                    }79                    const new_rest = alloc.create(V) catch return pattern;80                    new_rest.* = Self.preservePattern(alloc, rp.rest.*);81                    return .{ .rest_pattern = .{ .prefix = new_prefix, .rest = new_rest } };82                },83                .record => |r| return Self.preservePatternRecord(alloc, pattern, r),84                .symbol => |s| {85                    if (std.mem.eql(u8, s, symbols_mod.SYM_DISCARD.name)) return .{ .discard = {} };86                    return pattern;87                },88                .dictionary => |d| {89                    const new_entries = alloc.alloc(V.DictionaryEntry, d.len) catch return pattern;90                    for (d, 0..) |entry, i| {91                        new_entries[i] = .{92                            .key = Self.preservePattern(alloc, entry.key),93                            .value = Self.preservePattern(alloc, entry.value),94                        };95                    }96                    return .{ .dictionary = new_entries };97                },98                .sequence => |s| {99                    const new_items = alloc.alloc(V, s.len) catch return pattern;100                    for (s, 0..) |item, i| {101                        new_items[i] = Self.preservePattern(alloc, item);102                    }103                    return .{ .sequence = new_items };104                },105                else => return pattern,106            }107        }108109        fn preservePatternRecord(alloc: Allocator, fallback: V, r: V.Record) V {110            if (r.label.* == .symbol) {111                const lname = r.label.*.symbol;112                if (std.mem.eql(u8, lname, symbols_mod.SYM_DISCARD.name) and r.fields.len == 0) {113                    return .{ .discard = {} };114                }115                if (std.mem.eql(u8, lname, symbols_mod.SYM_BIND_PAT.name) and r.fields.len == 1) {116                    const inner = alloc.create(V) catch return fallback;117                    inner.* = Self.preservePattern(alloc, r.fields[0]);118                    return .{ .capture = inner };119                }120                if (std.mem.eql(u8, lname, symbols_mod.SYM_LIT.name) and r.fields.len == 1) {121                    return r.fields[0];122                }123                if (std.mem.eql(u8, lname, symbols_mod.SYM_GROUP.name) and r.fields.len == 2) {124                    if (Self.preserveGroup(alloc, r.fields[0], r.fields[1], fallback)) |g| return g;125                }126            }127            const new_label = alloc.create(V) catch return fallback;128            new_label.* = Self.preserve(alloc, r.label.*);129            const new_fields = alloc.alloc(V, r.fields.len) catch return fallback;130            for (r.fields, 0..) |field, i| {131                new_fields[i] = Self.preservePattern(alloc, field);132            }133            return .{ .record = .{ .label = new_label, .fields = new_fields } };134        }135136        fn preserveGroup(alloc: Allocator, group_type: V, entries_val: V, fallback: V) ?V {137            const gt = switch (group_type) {138                .record => |gtr| gtr,139                else => return null,140            };141            if (gt.label.* != .symbol) return null;142            const gs = gt.label.*.symbol;143            if (std.mem.eql(u8, gs, symbols_mod.SYM_REC.name)) {144                const rec_label = if (gt.fields.len > 0) gt.fields[0] else V{ .symbol = "" };145                const fields = Self.entriesToIndexed(alloc, entries_val) catch return fallback;146                defer alloc.free(fields);147                const new_fields = alloc.alloc(V, fields.len) catch return fallback;148                for (fields, 0..) |f, i| {149                    new_fields[i] = Self.preservePattern(alloc, f);150                }151                const new_label = alloc.create(V) catch return fallback;152                new_label.* = rec_label;153                return V{ .record = .{ .label = new_label, .fields = new_fields } };154            }155            if (std.mem.eql(u8, gs, symbols_mod.SYM_ARR.name)) {156                const fields = Self.entriesToIndexed(alloc, entries_val) catch return fallback;157                defer alloc.free(fields);158                const new_items = alloc.alloc(V, fields.len) catch return fallback;159                for (fields, 0..) |f, i| {160                    new_items[i] = Self.preservePattern(alloc, f);161                }162                return V{ .sequence = new_items };163            }164            if (std.mem.eql(u8, gs, symbols_mod.SYM_DICT.name)) {165                switch (entries_val) {166                    .dictionary => |d| {167                        const new_entries = alloc.alloc(V.DictionaryEntry, d.len) catch return fallback;168                        for (d, 0..) |entry, i| {169                            new_entries[i] = .{170                                .key = entry.key,171                                .value = Self.preservePattern(alloc, entry.value),172                            };173                        }174                        return V{ .dictionary = new_entries };175                    },176                    else => {},177                }178            }179            return null;180        }181182        /// Returns the wire form of `pattern`, allocated with `alloc`. The text formatter calls it183        /// for the wire spelling of captures and binds, and code sending a pattern calls it, for a184        /// plain value the codecs can write. The discard pattern becomes `<_>`, and a capture or185        /// bind becomes `<bind P>` around its converted pattern. An atom or a set becomes186        /// `<lit v>`, and an embedded value stays as it is. A record becomes187        /// `<group <rec L> {0: …, 1: …}>`, and a sequence `<group <arr> {…}>`, keyed by position. A188        /// dictionary becomes `<group <dict> {…}>` with the same keys. A rest pattern becomes an189        /// array group of its prefix, then `<lit .>`, then its rest. The result shares atoms,190        /// labels and dictionary keys with `pattern`, so `pattern` has to outlive it. A bind's name191        /// does not appear in the result. The only error is running out of memory, and the call192        /// does not free what it built before the failure.193        pub fn patternToPreserves(alloc: Allocator, pattern: V) !V {194            return switch (pattern) {195                .discard => H.record(alloc, V{ .symbol = symbols_mod.SYM_DISCARD.name }, &.{}),196                .capture => |inner| blk: {197                    const converted = try Self.patternToPreserves(alloc, inner.*);198                    break :blk H.record(alloc, V{ .symbol = symbols_mod.SYM_BIND_PAT.name }, &.{converted});199                },200                .bind => |b| blk: {201                    const converted = try Self.patternToPreserves(alloc, b.pattern.*);202                    break :blk H.record(alloc, V{ .symbol = symbols_mod.SYM_BIND_PAT.name }, &.{converted});203                },204                .boolean,205                .double,206                .signed_integer,207                .string,208                .byte_string,209                .symbol,210                => H.record(alloc, V{ .symbol = symbols_mod.SYM_LIT.name }, &.{pattern}),211                .embedded => pattern,212                .record => |r| blk: {213                    const group_type = try H.record(alloc, V{ .symbol = symbols_mod.SYM_REC.name }, &.{r.label.*});214                    const entries = try alloc.alloc(V.DictionaryEntry, r.fields.len);215                    for (r.fields, 0..) |field, i| {216                        entries[i] = .{217                            .key = V.initI128(@as(i128, @intCast(i))),218                            .value = try Self.patternToPreserves(alloc, field),219                        };220                    }221                    const dict = V{ .dictionary = entries };222                    break :blk H.record(alloc, V{ .symbol = symbols_mod.SYM_GROUP.name }, &.{ group_type, dict });223                },224                .sequence => |items| blk: {225                    const group_type = try H.record(alloc, V{ .symbol = symbols_mod.SYM_ARR.name }, &.{});226                    const entries = try alloc.alloc(V.DictionaryEntry, items.len);227                    for (items, 0..) |item, i| {228                        entries[i] = .{229                            .key = V.initI128(@as(i128, @intCast(i))),230                            .value = try Self.patternToPreserves(alloc, item),231                        };232                    }233                    const dict = V{ .dictionary = entries };234                    break :blk H.record(alloc, V{ .symbol = symbols_mod.SYM_GROUP.name }, &.{ group_type, dict });235                },236                .dictionary => |d| blk: {237                    const group_type = try H.record(alloc, V{ .symbol = symbols_mod.SYM_DICT.name }, &.{});238                    const entries = try alloc.alloc(V.DictionaryEntry, d.len);239                    for (d, 0..) |entry, i| {240                        entries[i] = .{241                            .key = entry.key,242                            .value = try Self.patternToPreserves(alloc, entry.value),243                        };244                    }245                    const dict = V{ .dictionary = entries };246                    break :blk H.record(alloc, V{ .symbol = symbols_mod.SYM_GROUP.name }, &.{ group_type, dict });247                },248                .rest_pattern => |rp| blk: {249                    const items = try alloc.alloc(V, rp.prefix.len + 2);250                    defer alloc.free(items);251                    for (rp.prefix, 0..) |item, i| {252                        items[i] = item;253                    }254                    items[rp.prefix.len] = V{ .symbol = "." };255                    items[rp.prefix.len + 1] = rp.rest.*;256                    break :blk try Self.patternToPreserves(alloc, V{ .sequence = items });257                },258                .set => H.record(alloc, V{ .symbol = symbols_mod.SYM_LIT.name }, &.{pattern}),259            };260        }261262        /// Returns the in-memory pattern that the wire value `value` spells, allocated with263        /// `alloc`. Code receiving a pattern in wire form calls it for an in-memory pattern, with264        /// allocation failure reported. The call reads the same spellings as `preservePattern`: `_`265        /// and `<_>`, `<bind P>`, `<lit v>` and the three `<group>` forms. A `<lit v>` gets a copy266        /// of `v`'s compound storage. Other records, sequences, dictionaries and in-memory patterns267        /// keep their shape, and their parts are converted in turn. Strings, symbols, byte strings268        /// and bind names in the result point into `value`, and sets, integers and embedded values269        /// come back as they are, sharing storage with `value`. The package's test frees a result270        /// with `freeValueDeep`, which frees shared sets and integers too. The call returns271        /// `error.OutOfMemory` when an allocation fails. On failure, most arms free what they272        /// built, and the `<group>` arms and the `<bind P>` arm leak it.273        pub fn preservesToPattern(alloc: Allocator, value: V) Allocator.Error!V {274            switch (value) {275                .symbol => |s| {276                    if (std.mem.eql(u8, s, symbols_mod.SYM_DISCARD.name)) {277                        return .{ .discard = {} };278                    }279                },280                .record => |r| {281                    switch (r.label.*) {282                        .symbol => |s| {283                            if (std.mem.eql(u8, s, symbols_mod.SYM_DISCARD.name) and r.fields.len == 0) {284                                return .{ .discard = {} };285                            }286                            if (std.mem.eql(u8, s, symbols_mod.SYM_BIND_PAT.name) and r.fields.len == 1) {287                                const inner = try Self.preservesToPattern(alloc, r.fields[0]);288                                return H.capture(alloc, inner);289                            }290                            if (std.mem.eql(u8, s, symbols_mod.SYM_LIT.name) and r.fields.len == 1) {291                                return try Self.cloneValueOwned(alloc, r.fields[0]);292                            }293                            if (std.mem.eql(u8, s, symbols_mod.SYM_GROUP.name) and r.fields.len == 2) {294                                if (try Self.preservesToGroup(alloc, r.fields[0], r.fields[1])) |g| return g;295                            }296                        },297                        else => {},298                    }299                    return try Self.plainRecordToPattern(alloc, r);300                },301                .sequence => |items| {302                    const converted = try alloc.alloc(V, items.len);303                    var filled: usize = 0;304                    errdefer {305                        for (converted[0..filled]) |item| {306                            ownership.freeValueDeep(D, alloc, item);307                        }308                        alloc.free(converted);309                    }310                    while (filled < items.len) : (filled += 1) {311                        converted[filled] = try Self.preservesToPattern(alloc, items[filled]);312                    }313                    return .{ .sequence = converted };314                },315                .dictionary => |entries| {316                    const converted = try alloc.alloc(V.DictionaryEntry, entries.len);317                    var filled: usize = 0;318                    errdefer {319                        for (converted[0..filled]) |entry| {320                            ownership.freeValueDeep(D, alloc, entry.key);321                            ownership.freeValueDeep(D, alloc, entry.value);322                        }323                        alloc.free(converted);324                    }325                    while (filled < entries.len) : (filled += 1) {326                        const key = try Self.cloneValueOwned(alloc, entries[filled].key);327                        errdefer ownership.freeValueDeep(D, alloc, key);328                        converted[filled] = .{329                            .key = key,330                            .value = try Self.preservesToPattern(alloc, entries[filled].value),331                        };332                    }333                    return .{ .dictionary = converted };334                },335                .capture => |inner| {336                    const converted = try Self.preservesToPattern(alloc, inner.*);337                    return H.capture(alloc, converted);338                },339                .bind => |binding| {340                    const pattern = try alloc.create(V);341                    errdefer alloc.destroy(pattern);342                    pattern.* = try Self.preservesToPattern(alloc, binding.pattern.*);343                    return .{ .bind = .{344                        .name = binding.name,345                        .pattern = pattern,346                    } };347                },348                .rest_pattern => |rest| {349                    const prefix = try alloc.alloc(V, rest.prefix.len);350                    var filled: usize = 0;351                    errdefer {352                        for (prefix[0..filled]) |item| {353                            ownership.freeValueDeep(D, alloc, item);354                        }355                        alloc.free(prefix);356                    }357                    while (filled < rest.prefix.len) : (filled += 1) {358                        prefix[filled] = try Self.preservesToPattern(alloc, rest.prefix[filled]);359                    }360                    const rest_ptr = try alloc.create(V);361                    errdefer alloc.destroy(rest_ptr);362                    rest_ptr.* = try Self.preservesToPattern(alloc, rest.rest.*);363                    return .{ .rest_pattern = .{ .prefix = prefix, .rest = rest_ptr } };364                },365                else => {},366            }367            return value;368        }369370        fn plainRecordToPattern(alloc: Allocator, r: V.Record) Allocator.Error!V {371            const label = try alloc.create(V);372            errdefer alloc.destroy(label);373            label.* = try Self.cloneValueOwned(alloc, r.label.*);374            errdefer ownership.freeValueDeep(D, alloc, label.*);375376            const fields = try alloc.alloc(V, r.fields.len);377            var filled: usize = 0;378            errdefer {379                for (fields[0..filled]) |field| {380                    ownership.freeValueDeep(D, alloc, field);381                }382                alloc.free(fields);383            }384            while (filled < r.fields.len) : (filled += 1) {385                fields[filled] = try Self.preservesToPattern(alloc, r.fields[filled]);386            }387388            return .{ .record = .{389                .label = label,390                .fields = fields,391            } };392        }393394        fn cloneValueOwned(alloc: Allocator, value: V) Allocator.Error!V {395            return switch (value) {396                .boolean, .double, .string, .byte_string, .symbol, .discard => value,397                .signed_integer => |si| .{ .signed_integer = try si.clone(alloc) },398                .record => |record| blk: {399                    const label = try alloc.create(V);400                    errdefer alloc.destroy(label);401                    label.* = try Self.cloneValueOwned(alloc, record.label.*);402                    errdefer ownership.freeValueDeep(D, alloc, label.*);403                    break :blk .{ .record = .{404                        .label = label,405                        .fields = try Self.cloneValueSliceOwned(alloc, record.fields),406                    } };407                },408                .sequence => |items| .{ .sequence = try Self.cloneValueSliceOwned(alloc, items) },409                .set => |items| .{ .set = try Self.cloneValueSliceOwned(alloc, items) },410                .dictionary => |entries| .{ .dictionary = try Self.cloneDictionaryOwned(alloc, entries) },411                .embedded => |embedded| .{ .embedded = try embedded.clone(alloc) },412                .capture => |inner| blk: {413                    const cloned = try alloc.create(V);414                    errdefer alloc.destroy(cloned);415                    cloned.* = try Self.cloneValueOwned(alloc, inner.*);416                    break :blk .{ .capture = cloned };417                },418                .bind => |binding| blk: {419                    const cloned = try alloc.create(V);420                    errdefer alloc.destroy(cloned);421                    cloned.* = try Self.cloneValueOwned(alloc, binding.pattern.*);422                    break :blk .{ .bind = .{423                        .name = binding.name,424                        .pattern = cloned,425                    } };426                },427                .rest_pattern => |rest| blk: {428                    const prefix = try Self.cloneValueSliceOwned(alloc, rest.prefix);429                    errdefer {430                        for (prefix) |item| ownership.freeValueDeep(D, alloc, item);431                        alloc.free(prefix);432                    }433                    const rest_ptr = try alloc.create(V);434                    errdefer alloc.destroy(rest_ptr);435                    rest_ptr.* = try Self.cloneValueOwned(alloc, rest.rest.*);436                    break :blk .{ .rest_pattern = .{ .prefix = prefix, .rest = rest_ptr } };437                },438            };439        }440441        fn cloneValueSliceOwned(alloc: Allocator, items: []const V) Allocator.Error![]V {442            const cloned = try alloc.alloc(V, items.len);443            var filled: usize = 0;444            errdefer {445                for (cloned[0..filled]) |item| {446                    ownership.freeValueDeep(D, alloc, item);447                }448                alloc.free(cloned);449            }450            while (filled < items.len) : (filled += 1) {451                cloned[filled] = try Self.cloneValueOwned(alloc, items[filled]);452            }453            return cloned;454        }455456        fn cloneDictionaryOwned(alloc: Allocator, entries: []const V.DictionaryEntry) Allocator.Error![]V.DictionaryEntry {457            const cloned = try alloc.alloc(V.DictionaryEntry, entries.len);458            var filled: usize = 0;459            errdefer {460                for (cloned[0..filled]) |entry| {461                    ownership.freeValueDeep(D, alloc, entry.key);462                    ownership.freeValueDeep(D, alloc, entry.value);463                }464                alloc.free(cloned);465            }466            while (filled < entries.len) : (filled += 1) {467                const key = try Self.cloneValueOwned(alloc, entries[filled].key);468                errdefer ownership.freeValueDeep(D, alloc, key);469                cloned[filled] = .{470                    .key = key,471                    .value = try Self.cloneValueOwned(alloc, entries[filled].value),472                };473            }474            return cloned;475        }476477        fn preservesToGroup(alloc: Allocator, group_type: V, entries_val: V) Allocator.Error!?V {478            const gt = switch (group_type) {479                .record => |gtr| gtr,480                else => return null,481            };482            const gs = switch (gt.label.*) {483                .symbol => |s| s,484                else => return null,485            };486            if (std.mem.eql(u8, gs, symbols_mod.SYM_REC.name)) {487                const rec_label = if (gt.fields.len > 0) gt.fields[0] else V{ .symbol = "" };488                const fields = try Self.entriesToIndexed(alloc, entries_val);489                defer alloc.free(fields);490                const converted = try alloc.alloc(V, fields.len);491                defer alloc.free(converted);492                for (fields, 0..) |f, i| {493                    converted[i] = try Self.preservesToPattern(alloc, f);494                }495                return try H.record(alloc, rec_label, converted);496            }497            if (std.mem.eql(u8, gs, symbols_mod.SYM_ARR.name)) {498                const fields = try Self.entriesToIndexed(alloc, entries_val);499                defer alloc.free(fields);500                const converted = try alloc.alloc(V, fields.len);501                for (fields, 0..) |f, i| {502                    converted[i] = try Self.preservesToPattern(alloc, f);503                }504                return V{ .sequence = converted };505            }506            if (std.mem.eql(u8, gs, symbols_mod.SYM_DICT.name)) {507                switch (entries_val) {508                    .dictionary => |d| {509                        const converted = try alloc.alloc(V.DictionaryEntry, d.len);510                        for (d, 0..) |entry, i| {511                            converted[i] = .{512                                .key = entry.key,513                                .value = try Self.preservesToPattern(alloc, entry.value),514                            };515                        }516                        return V{ .dictionary = converted };517                    },518                    else => {},519                }520            }521            return null;522        }523524        fn entriesToIndexed(alloc: Allocator, entries_val: V) Allocator.Error![]V {525            switch (entries_val) {526                .dictionary => |d| {527                    const sorted = try alloc.dupe(V.DictionaryEntry, d);528                    defer alloc.free(sorted);529                    const Cmp = struct {530                        fn lt(_: void, a: V.DictionaryEntry, b: V.DictionaryEntry) bool {531                            return a.key.compare(b.key) == .lt;532                        }533                    };534                    std.mem.sort(V.DictionaryEntry, sorted, {}, Cmp.lt);535                    const result = try alloc.alloc(V, sorted.len);536                    for (sorted, 0..) |entry, i| {537                        result[i] = entry.value;538                    }539                    return result;540                },541                else => return try alloc.alloc(V, 0),542            }543        }544545        /// Returns the observer, the second field of an `<Observe pattern observer>` record. The546        /// call returns null unless `value` is a record labeled `Observe` with two fields. The547        /// result shares storage with `value`, and the call allocates nothing.548        pub fn observeObserver(value: V) ?V {549            if (!predicates_mod.isRecord(D, value, symbols_mod.SYM_OBSERVE.name, 2)) return null;550            return value.record.fields[1];551        }552553        /// Returns the pattern, the first field of an `<Observe pattern observer>` record. The call554        /// returns null unless `value` is a record labeled `Observe` with two fields. The result555        /// shares storage with `value`, and the call allocates nothing.556        pub fn observePattern(value: V) ?V {557            if (!predicates_mod.isRecord(D, value, symbols_mod.SYM_OBSERVE.name, 2)) return null;558            return value.record.fields[0];559        }560561        /// Calls `callback(context, e)` for each embedded value `e` in `value`, depth first. Code562        /// holding references through embedded values calls it, for one visit to each, such as a563        /// count or a retain. The call visits record labels and fields, sequence and set items,564        /// dictionary keys and values, and the parts of in-memory patterns. The call allocates565        /// nothing and returns nothing.566        pub fn foreachEmbedded(value: V, context: anytype, callback: anytype) void {567            switch (value) {568                .embedded => |e| callback(context, e),569                .record => |r| {570                    Self.foreachEmbedded(r.label.*, context, callback);571                    for (r.fields) |field| Self.foreachEmbedded(field, context, callback);572                },573                .sequence => |s| for (s) |item| Self.foreachEmbedded(item, context, callback),574                .set => |s| for (s) |item| Self.foreachEmbedded(item, context, callback),575                .dictionary => |d| for (d) |entry| {576                    Self.foreachEmbedded(entry.key, context, callback);577                    Self.foreachEmbedded(entry.value, context, callback);578                },579                .capture => |p| Self.foreachEmbedded(p.*, context, callback),580                .bind => |b| Self.foreachEmbedded(b.pattern.*, context, callback),581                .rest_pattern => |rp| {582                    for (rp.prefix) |item| Self.foreachEmbedded(item, context, callback);583                    Self.foreachEmbedded(rp.rest.*, context, callback);584                },585                else => {},586            }587        }588589        /// Returns a copy of `value` in which each embedded value `e` is replaced by590        /// `map_fn(context, alloc, e)`. Code that moves a value to another type of embedded value,591        /// or swaps each embedded value for another value, calls it for the rewritten copy. The592        /// call copies records, sequences, sets, dictionaries and in-memory patterns with `alloc`,593        /// and returns atoms as they are. The call returns any error `map_fn` returns, and594        /// `error.OutOfMemory`. On failure the call does not free what it built before.595        pub fn mapEmbedded(596            alloc: Allocator,597            value: V,598            context: anytype,599            map_fn: anytype,600        ) !V {601            switch (value) {602                .embedded => |e| return map_fn(context, alloc, e),603                .record => |r| {604                    const new_label = try alloc.create(V);605                    new_label.* = try Self.mapEmbedded(alloc, r.label.*, context, map_fn);606                    const new_fields = try alloc.alloc(V, r.fields.len);607                    for (r.fields, 0..) |field, i| {608                        new_fields[i] = try Self.mapEmbedded(alloc, field, context, map_fn);609                    }610                    return V{ .record = .{ .label = new_label, .fields = new_fields } };611                },612                .sequence => |s| {613                    const new_items = try alloc.alloc(V, s.len);614                    for (s, 0..) |item, i| {615                        new_items[i] = try Self.mapEmbedded(alloc, item, context, map_fn);616                    }617                    return V{ .sequence = new_items };618                },619                .set => |s| {620                    const new_items = try alloc.alloc(V, s.len);621                    for (s, 0..) |item, i| {622                        new_items[i] = try Self.mapEmbedded(alloc, item, context, map_fn);623                    }624                    return V{ .set = new_items };625                },626                .dictionary => |d| {627                    const new_entries = try alloc.alloc(V.DictionaryEntry, d.len);628                    for (d, 0..) |entry, i| {629                        new_entries[i] = .{630                            .key = try Self.mapEmbedded(alloc, entry.key, context, map_fn),631                            .value = try Self.mapEmbedded(alloc, entry.value, context, map_fn),632                        };633                    }634                    return V{ .dictionary = new_entries };635                },636                .capture => |p| {637                    const new_ptr = try alloc.create(V);638                    new_ptr.* = try Self.mapEmbedded(alloc, p.*, context, map_fn);639                    return V{ .capture = new_ptr };640                },641                .bind => |b| {642                    const new_pat = try alloc.create(V);643                    new_pat.* = try Self.mapEmbedded(alloc, b.pattern.*, context, map_fn);644                    return V{ .bind = .{ .name = b.name, .pattern = new_pat } };645                },646                .rest_pattern => |rp| {647                    const new_prefix = try alloc.alloc(V, rp.prefix.len);648                    for (rp.prefix, 0..) |item, i| {649                        new_prefix[i] = try Self.mapEmbedded(alloc, item, context, map_fn);650                    }651                    const new_rest = try alloc.create(V);652                    new_rest.* = try Self.mapEmbedded(alloc, rp.rest.*, context, map_fn);653                    return V{ .rest_pattern = .{ .prefix = new_prefix, .rest = new_rest } };654                },655                else => return value,656            }657        }658    };659}660661/// The pattern conversions for `Value(NoEmbedded)`. Code whose values are `Value(NoEmbedded)` calls662/// these conversions, for a namespace fixed to that type. The top-level functions of this file call663/// it.664pub const conversions = Conversions(NoEmbedded);665/// The pattern conversions for values whose embedded values hold any pointer (`AnyEmbedded`). The666/// package root's pattern functions are these, so a caller of `preserves.patternToPreserves` calls667/// this instance. The package root and the text formatter use it.668pub const any_conversions = Conversions(AnyEmbedded);669670/// Returns `value` unchanged, the same as `conversions.preserve`.671pub fn preserve(alloc: Allocator, value: Value(NoEmbedded)) Value(NoEmbedded) {672    return conversions.preserve(alloc, value);673}674675/// Returns the in-memory pattern spelled by `pattern`, the same as `conversions.preservePattern`.676pub fn preservePattern(alloc: Allocator, pattern: Value(NoEmbedded)) Value(NoEmbedded) {677    return conversions.preservePattern(alloc, pattern);678}679680/// Returns the wire form of `pattern`, the same as `conversions.patternToPreserves`.681pub fn patternToPreserves(alloc: Allocator, pattern: Value(NoEmbedded)) !Value(NoEmbedded) {682    return conversions.patternToPreserves(alloc, pattern);683}684685/// Returns the in-memory pattern spelled by `value`, the same as `conversions.preservesToPattern`.686pub fn preservesToPattern(alloc: Allocator, value: Value(NoEmbedded)) !Value(NoEmbedded) {687    return conversions.preservesToPattern(alloc, value);688}689690/// Returns the observer of an `Observe` record, the same as `conversions.observeObserver`.691pub fn observeObserver(value: Value(NoEmbedded)) ?Value(NoEmbedded) {692    return conversions.observeObserver(value);693}694695/// Returns the pattern of an `Observe` record, the same as `conversions.observePattern`.696pub fn observePattern(value: Value(NoEmbedded)) ?Value(NoEmbedded) {697    return conversions.observePattern(value);698}699700/// Calls `callback` for each embedded value in `value`, the same as `conversions.foreachEmbedded`.701pub fn foreachEmbedded(value: Value(NoEmbedded), context: anytype, callback: anytype) void {702    conversions.foreachEmbedded(value, context, callback);703}704705/// Returns a copy of `value` with each embedded value mapped, the same as706/// `conversions.mapEmbedded`.707pub fn mapEmbedded(708    alloc: Allocator,709    value: Value(NoEmbedded),710    context: anytype,711    map_fn: anytype,712) !Value(NoEmbedded) {713    return conversions.mapEmbedded(alloc, value, context, map_fn);714}715716test "preserve is identity" {717    const V = Value(NoEmbedded);718    const allocator = std.testing.allocator;719    const v = V.initI128(42);720    const r = preserve(allocator, v);721    try std.testing.expect(r.eql(v));722}723724test "patternToPreserves discard → <_>" {725    const V = Value(NoEmbedded);726    const allocator = std.testing.allocator;727    var arena = std.heap.ArenaAllocator.init(allocator);728    defer arena.deinit();729    const a = arena.allocator();730731    const wire = try patternToPreserves(a, V{ .discard = {} });732    try std.testing.expectEqual(value_mod.CompoundClass.record, wire.compoundClass().?);733    try std.testing.expect(std.mem.eql(u8, wire.record.label.*.symbol, symbols_mod.SYM_DISCARD.name));734    try std.testing.expectEqual(@as(usize, 0), wire.record.fields.len);735}736737test "patternToPreserves literal → <lit v>" {738    const V = Value(NoEmbedded);739    const allocator = std.testing.allocator;740    var arena = std.heap.ArenaAllocator.init(allocator);741    defer arena.deinit();742    const a = arena.allocator();743744    const wire = try patternToPreserves(a, V.initI128(42));745    try std.testing.expect(std.mem.eql(u8, wire.record.label.*.symbol, symbols_mod.SYM_LIT.name));746    try std.testing.expectEqual(@as(usize, 1), wire.record.fields.len);747    try std.testing.expectEqual(@as(i128, 42), try wire.record.fields[0].signed_integer.toI128());748}749750test "patternToPreserves capture → <bind inner>" {751    const V = Value(NoEmbedded);752    const allocator = std.testing.allocator;753    var arena = std.heap.ArenaAllocator.init(allocator);754    defer arena.deinit();755    const a = arena.allocator();756757    const inner = try a.create(V);758    inner.* = V{ .discard = {} };759    const cap: V = .{ .capture = inner };760    const wire = try patternToPreserves(a, cap);761    try std.testing.expect(std.mem.eql(u8, wire.record.label.*.symbol, symbols_mod.SYM_BIND_PAT.name));762    try std.testing.expectEqual(@as(usize, 1), wire.record.fields.len);763    try std.testing.expect(std.mem.eql(u8, wire.record.fields[0].record.label.*.symbol, symbols_mod.SYM_DISCARD.name));764}765766test "preservesToPattern round-trip through discard, literal, capture" {767    const V = Value(NoEmbedded);768    const allocator = std.testing.allocator;769    var arena = std.heap.ArenaAllocator.init(allocator);770    defer arena.deinit();771    const a = arena.allocator();772773    const d: V = .{ .discard = {} };774    const d_wire = try patternToPreserves(a, d);775    const d_back = try preservesToPattern(a, d_wire);776    try std.testing.expectEqual(value_mod.PatternFormClass.discard, d_back.patternClass().?);777778    const lit = V.initI128(7);779    const lit_wire = try patternToPreserves(a, lit);780    const lit_back = try preservesToPattern(a, lit_wire);781    try std.testing.expectEqual(@as(i128, 7), try lit_back.signed_integer.toI128());782783    const inner = try a.create(V);784    inner.* = V{ .discard = {} };785    const cap: V = .{ .capture = inner };786    const cap_wire = try patternToPreserves(a, cap);787    const cap_back = try preservesToPattern(a, cap_wire);788    try std.testing.expectEqual(value_mod.PatternFormClass.capture, cap_back.patternClass().?);789    try std.testing.expectEqual(value_mod.PatternFormClass.discard, cap_back.capture.*.patternClass().?);790}791792test "preservesToPattern round-trip through record group" {793    const V = Value(NoEmbedded);794    const allocator = std.testing.allocator;795    var arena = std.heap.ArenaAllocator.init(allocator);796    defer arena.deinit();797    const a = arena.allocator();798799    const inner_fields = try a.alloc(V, 2);800    inner_fields[0] = V{ .discard = {} };801    inner_fields[1] = V.initI128(1);802    const label = try V.initSymbol(a, "Foo");803    const rec = try V.initRecord(a, label, inner_fields);804805    const wire = try patternToPreserves(a, rec);806    try std.testing.expect(std.mem.eql(u8, wire.record.label.*.symbol, symbols_mod.SYM_GROUP.name));807808    const back = try preservesToPattern(a, wire);809    try std.testing.expectEqual(value_mod.CompoundClass.record, back.compoundClass().?);810    try std.testing.expect(std.mem.eql(u8, back.record.label.*.symbol, "Foo"));811    try std.testing.expectEqual(@as(usize, 2), back.record.fields.len);812    try std.testing.expectEqual(value_mod.PatternFormClass.discard, back.record.fields[0].patternClass().?);813    try std.testing.expectEqual(@as(i128, 1), try back.record.fields[1].signed_integer.toI128());814}815816test "preservePattern lowers <_> symbol to .discard" {817    const V = Value(NoEmbedded);818    const allocator = std.testing.allocator;819    var arena = std.heap.ArenaAllocator.init(allocator);820    defer arena.deinit();821    const a = arena.allocator();822823    const sym_underscore: V = V{ .symbol = symbols_mod.SYM_DISCARD.name };824    const got = preservePattern(a, sym_underscore);825    try std.testing.expectEqual(value_mod.PatternFormClass.discard, got.patternClass().?);826}827828test "preservesToPattern lowers recursive plain-record wildcards" {829    const V = Value(NoEmbedded);830    const allocator = std.testing.allocator;831    var arena = std.heap.ArenaAllocator.init(allocator);832    defer arena.deinit();833    const a = arena.allocator();834835    const fields = try a.alloc(V, 2);836    fields[0] = V{ .symbol = symbols_mod.SYM_DISCARD.name };837    fields[1] = V.initI128(1);838    const label = try V.initSymbol(a, "Note");839    const rec = try V.initRecord(a, label, fields);840841    const got = try preservesToPattern(allocator, rec);842    defer ownership.freeValueDeep(NoEmbedded, allocator, got);843844    try std.testing.expectEqual(value_mod.CompoundClass.record, got.compoundClass().?);845    try std.testing.expect(std.mem.eql(u8, got.record.label.*.symbol, "Note"));846    try std.testing.expectEqual(@as(usize, 2), got.record.fields.len);847    try std.testing.expectEqual(value_mod.PatternFormClass.discard, got.record.fields[0].patternClass().?);848    try std.testing.expectEqual(@as(i128, 1), try got.record.fields[1].signed_integer.toI128());849}850851test "preservePattern lowers <bind P> wire record to .capture" {852    const V = Value(NoEmbedded);853    const allocator = std.testing.allocator;854    var arena = std.heap.ArenaAllocator.init(allocator);855    defer arena.deinit();856    const a = arena.allocator();857858    const bind_fields = try a.alloc(V, 1);859    bind_fields[0] = V.initI128(9);860    const label = try V.initSymbol(a, symbols_mod.SYM_BIND_PAT.name);861    const wire = try V.initRecord(a, label, bind_fields);862    const got = preservePattern(a, wire);863    try std.testing.expectEqual(value_mod.PatternFormClass.capture, got.patternClass().?);864    try std.testing.expectEqual(@as(i128, 9), try got.capture.*.signed_integer.toI128());865}866867test "observeObserver and observePattern extract fields from <Observe p o>" {868    const V = Value(NoEmbedded);869    const allocator = std.testing.allocator;870    var arena = std.heap.ArenaAllocator.init(allocator);871    defer arena.deinit();872    const a = arena.allocator();873874    const fields = try a.alloc(V, 2);875    fields[0] = V{ .discard = {} };876    fields[1] = V.initBoolean(true);877    const label = try V.initSymbol(a, symbols_mod.SYM_OBSERVE.name);878    const rec = try V.initRecord(a, label, fields);879880    try std.testing.expectEqual(value_mod.PatternFormClass.discard, observePattern(rec).?.patternClass().?);881    try std.testing.expect(observeObserver(rec).?.boolean);882    try std.testing.expect(observePattern(V.initI128(0)) == null);883    try std.testing.expect(observeObserver(V.initI128(0)) == null);884}885886test "foreachEmbedded walks a tree with AnyEmbedded values" {887    const V = Value(AnyEmbedded);888    const allocator = std.testing.allocator;889    var arena = std.heap.ArenaAllocator.init(allocator);890    defer arena.deinit();891    const a = arena.allocator();892893    var payload_a: u32 = 1;894    var payload_b: u32 = 2;895    const fields = try a.alloc(V, 2);896    fields[0] = V{ .embedded = AnyEmbedded{ .value = &payload_a } };897    fields[1] = V{ .embedded = AnyEmbedded{ .value = &payload_b } };898    const label = try V.initSymbol(a, "Pair");899    const rec = try V.initRecord(a, label, fields);900901    const Counter = struct {902        count: *usize,903        fn visit(self: *const @This(), e: AnyEmbedded) void {904            _ = e;905            self.count.* += 1;906        }907    };908    var count: usize = 0;909    const ctx = Counter{ .count = &count };910    any_conversions.foreachEmbedded(rec, &ctx, Counter.visit);911    try std.testing.expectEqual(@as(usize, 2), count);912}913914test "mapEmbedded transforms every embedded node" {915    const V = Value(AnyEmbedded);916    const allocator = std.testing.allocator;917    var arena = std.heap.ArenaAllocator.init(allocator);918    defer arena.deinit();919    const a = arena.allocator();920921    var payload: u32 = 7;922    const fields = try a.alloc(V, 1);923    fields[0] = V{ .embedded = AnyEmbedded{ .value = &payload } };924    const label = try V.initSymbol(a, "Wrap");925    const rec = try V.initRecord(a, label, fields);926927    const Mapper = struct {928        fn transform(_: *const @This(), alloc: Allocator, e: AnyEmbedded) !V {929            _ = alloc;930            _ = e;931            return V.initI128(99);932        }933    };934    const ctx = Mapper{};935    const mapped = try any_conversions.mapEmbedded(a, rec, &ctx, Mapper.transform);936    try std.testing.expectEqual(value_mod.CompoundClass.record, mapped.compoundClass().?);937    try std.testing.expectEqual(@as(i128, 99), try mapped.record.fields[0].signed_integer.toI128());938}

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