tiny.preserves.value

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

1//! One type holds every data value: atoms, compounds and embedded values of the host program. The2//! atoms are booleans, doubles, integers of any size, strings, byte strings and symbols, and the3//! compounds are records, sequences, sets and dictionaries.4//!5//! Two copies of one value have to be equal, order the same and hash alike, so a value can key a6//! hash map and sort the same way everywhere. A program has to know which memory a value owns and7//! which call frees it.8//!9//! A set or dictionary can sit in memory in any order: a program builds it by hand, and a text10//! document lists it in the order its author wrote. Comparing two sets element by element needs11//! both in sorted order, and sorting a copy would allocate memory on every comparison and every12//! hash. A value's leaves can point at bytes it owns or bytes someone else keeps alive, and the13//! value itself records neither.14//!15//! The type holds the values of the [Preserves](https://preserves.dev/) data language, which the16//! package keeps along with its patterns and its text, binary and JSON forms. Preserves gives all17//! values one total order in which sets and dictionaries compare through their elements in18//! ascending order, whatever their storage order.19//!20//! The package builds that one type as a generic tagged union (`Value`). The union takes the type21//! of its embedded values (*domain*) as a compile-time parameter, so each program picks what it22//! embeds. A compile-time check (`assertIsDomain`) tests that type before the union is built. The23//! union also holds four kinds of pattern (*pattern form*) beside the data: a discard, a capture of24//! an inner pattern, a bind that names an inner pattern, and a rest pattern for the items after a25//! sequence prefix. A value's kind (`ValueKind`) names its group (atom, compound, embedded value or26//! pattern) and which member of the group it is. `compare` ranks the kinds in a fixed order,27//! booleans first and patterns last, and within a kind compares contents. Doubles compare and hash28//! by their bits, so every double, `NaN` included, has one place in the order.29//!30//! Equality, order and hash read each set and dictionary in ascending order under `compare`,31//! whatever the order of its storage. That walk allocates nothing: a cursor finds each next element32//! by scanning the whole set, so the cost grows with the square of the set's size. A Lean model33//! proves that sorted copies of two sets are equal exactly when their elements are permutations of34//! each other, and that every observation of a sorted copy gives one answer for all such35//! permutations. The Lean results describe a model, and they check neither this Zig code nor its36//! hash.37//!38//! Whether atom bytes are borrowed or copied depends on the constructor: `initString`,39//! `initByteString` and `initSymbol` copy, and the root's `string` and `symbol` borrow. A value40//! owns a compound's slice only when its creator hands the slice over and later frees the value41//! with the same allocator. `deinit` frees everything a value points to, so it fits a value that42//! owns every byte, such as a decoded value or a copy from `cloneValueDeep`.43const std = @import("std");44const Allocator = std.mem.Allocator;4546const atom_mod = @import("atom.zig");47const integer_mod = @import("integer.zig");48const domain_mod = @import("domain.zig");4950pub const AtomClass = atom_mod.AtomClass;51pub const Atom = atom_mod.Atom;52pub const CowBytes = atom_mod.CowBytes;53pub const CowSignedInteger = atom_mod.CowSignedInteger;54pub const Ownership = atom_mod.Ownership;55pub const SignedInteger = integer_mod.SignedInteger;56pub const NoEmbedded = domain_mod.NoEmbedded;5758/// The four compound kinds, in the order `compare` ranks them: record, sequence, set and59/// dictionary. Code that switches on a compound's kind reads this from `compoundClass`.60/// `compoundClass` returns it for a compound and `null` for any other value.61pub const CompoundClass = enum { record, sequence, set, dictionary };6263/// The four kinds of pattern, in the order `compare` ranks them: discard, capture, bind and rest64/// pattern. Code that switches on a pattern's kind reads this from `patternClass`. `patternClass`65/// returns it for a pattern and `null` for any other value. These kinds rank after every data kind.66pub const PatternFormClass = enum { discard, capture, bind, rest_pattern };6768/// The four groups of kinds: atom, compound, embedded value and pattern. Code that switches on the69/// group of a value's kind reads this from `ValueKind`. This enum tags `ValueKind`.70pub const ValueKindTag = enum { atomic, compound, embedded, pattern };7172/// A value's kind: its group and, for an atom, a compound or a pattern, which one. Code that73/// switches on a value's kind reads this from `kind`. `kind` returns it for any value.74pub const ValueKind = union(ValueKindTag) {75    /// Which of the six atom kinds the value is.76    atomic: AtomClass,77    /// Which of the four compound kinds the value is.78    compound: CompoundClass,79    /// Marks an embedded value, which has no subkind.80    embedded,81    /// Which of the four kinds of pattern the value is.82    pattern: PatternFormClass,8384    /// Returns whether two kinds are in the same group and, within it, the same kind. `Value.eql`85    /// calls it to check two values' kinds before their contents.86    pub fn eql(a: ValueKind, b: ValueKind) bool {87        return switch (a) {88            .atomic => |ac| switch (b) {89                .atomic => |bc| ac == bc,90                else => false,91            },92            .compound => |ac| switch (b) {93                .compound => |bc| ac == bc,94                else => false,95            },96            .embedded => switch (b) {97                .embedded => true,98                else => false,99            },100            .pattern => |ac| switch (b) {101                .pattern => |bc| ac == bc,102                else => false,103            },104        };105    }106};107108/// Returns the tagged union of all values whose embedded values have type `D`. Every program that109/// stores Preserves data calls it once for the type of its embedded values, as the text codec does110/// with `AnyEmbedded`. The function stops compilation unless `D` meets `assertIsDomain`. Whether111/// atom bytes are borrowed or copied depends on the constructor: `initString`, `initByteString` and112/// `initSymbol` copy, and the root's `string` and `symbol` borrow. A value owns a compound's slice113/// only when its creator hands the slice over and later calls `deinit` with the same allocator.114/// Every decoder copies the bytes it reads, so a decoded value owns every byte and `deinit` frees115/// it.116pub fn Value(comptime D: type) type {117    domain_mod.assertIsDomain(D);118    return union(enum) {119        pub const Self = @This();120        /// The type of the embedded values, `D`. Generic code reads it to recover the type of the121        /// embedded values from a value type. `text.decode` and the binary `decode` take that type122        /// as their first parameter, so `Value.Domain` fills it.123        pub const Domain = D;124        /// A slice of values, the storage of a sequence and of a record's fields. Code that builds125        /// a record's fields or a sequence names the slice with this type.126        pub const Sequence = []Self;127        /// A slice of values, the storage of a set, holding each element once in any order. Code128        /// that builds a set names the slice with this type. Equality, order and hash read it in129        /// ascending order under `compare`.130        pub const Set = []Self;131        /// One key and value pair of a dictionary. Code that builds a dictionary names each entry132        /// with this type, as the constructors and the JSON reader do.133        pub const DictionaryEntry = struct {134            /// The entry's key, which appears once in its dictionary.135            key: Self,136            /// The value the key maps to.137            value: Self,138        };139        /// A slice of entries, the storage of a dictionary, in any order. Code that builds a140        /// dictionary names the slice with this type. Equality, order and hash read the entries in141        /// ascending order of key, then value, under `compare`.142        pub const Dictionary = []DictionaryEntry;143        /// The parts of a record: a label and its fields. Code that reads a record names its parts144        /// with this type.145        pub const Record = struct {146            /// A pointer to the label value, kept in its own cell so a record can have any value as147            /// its label. Records compare their labels first.148            label: *Self,149            /// The record's fields, in order. Records with equal labels compare their fields in150            /// order, and a shorter list that matches ranks first.151            fields: Sequence,152        };153        /// The parts of a bind: a name and the pattern it names. Code that reads a bind names its154        /// parts with this type.155        pub const Bind = struct {156            /// The bind's name. Two binds are equal only when their names are equal byte for byte.157            /// `deinit` frees the name, and `freeValue` and `freeValueDeep` leave it.158            name: []const u8,159            /// A pointer to the pattern the bind names, in its own cell.160            pattern: *Self,161        };162        /// The parts of a rest pattern: patterns for the first items of a sequence and one pattern163        /// for the items after them. Code that reads a rest pattern names its parts with this type.164        pub const RestPattern = struct {165            /// The patterns for the first items, in order.166            prefix: []Self,167            /// A pointer to the pattern for the items after the prefix, in its own cell.168            rest: *Self,169        };170171        /// A boolean. `false` orders before `true`.172        boolean: bool,173        /// A 64-bit double. Doubles are equal when their bits are equal, and they order by a total174        /// order over their bits, so `0.0` and `-0.0` differ and a `NaN` has one place.175        double: f64,176        /// An integer of any size. `deinit` frees its heap digits when it has any.177        signed_integer: SignedInteger,178        /// The string's bytes. The text reader rejects invalid UTF-8 bytes. Strings compare byte by179        /// byte.180        string: []const u8,181        /// The byte string's bytes, compared byte by byte.182        byte_string: []const u8,183        /// The symbol's name bytes, compared byte by byte.184        symbol: []const u8,185        /// A record: a label and its fields.186        record: Record,187        /// A sequence: values in order, compared item by item.188        sequence: Sequence,189        /// A set: each element once, stored in any order. Equality, order and hash read it in190        /// ascending order under `compare`, whatever the order of its storage.191        set: Set,192        /// A dictionary: each key once, mapped to a value, stored in any order. Equality, order and193        /// hash read it in ascending order of key, then value, whatever the order of its storage.194        dictionary: Dictionary,195        /// An embedded value of the type `D`, which supplies its equality, order, freeing and196        /// copying.197        embedded: D,198        /// The discard pattern carries no data. All discards are equal.199        discard: void,200        /// A capture: a pointer to its inner pattern, in its own cell.201        capture: *Self,202        /// A bind: a name and the pattern it names.203        bind: Bind,204        /// A rest pattern: patterns for a sequence's first items and one pattern for the rest.205        rest_pattern: RestPattern,206207        /// Returns the value's kind: its group and which member of the group. Code that switches on208        /// a value's kind calls it.209        pub fn kind(self: Self) ValueKind {210            return switch (self) {211                .boolean => .{ .atomic = .boolean },212                .double => .{ .atomic = .double },213                .signed_integer => .{ .atomic = .signed_integer },214                .string => .{ .atomic = .string },215                .byte_string => .{ .atomic = .byte_string },216                .symbol => .{ .atomic = .symbol },217                .record => .{ .compound = .record },218                .sequence => .{ .compound = .sequence },219                .set => .{ .compound = .set },220                .dictionary => .{ .compound = .dictionary },221                .embedded => .embedded,222                .discard => .{ .pattern = .discard },223                .capture => .{ .pattern = .capture },224                .bind => .{ .pattern = .bind },225                .rest_pattern => .{ .pattern = .rest_pattern },226            };227        }228229        /// Returns the atom kind of an atom, and `null` for any other value. Code that handles230        /// atoms calls it to test for one and learn which.231        pub fn atomClass(self: Self) ?AtomClass {232            return switch (self.kind()) {233                .atomic => |a| a,234                else => null,235            };236        }237238        /// Returns the compound kind of a compound, and `null` for any other value. Code that239        /// handles compounds calls it to test for one and learn which.240        pub fn compoundClass(self: Self) ?CompoundClass {241            return switch (self.kind()) {242                .compound => |c| c,243                else => null,244            };245        }246247        /// Returns the kind of pattern, and `null` for any other value. Code that handles patterns248        /// calls it to test for one and learn which.249        pub fn patternClass(self: Self) ?PatternFormClass {250            return switch (self.kind()) {251                .pattern => |p| p,252                else => null,253            };254        }255256        /// Makes a boolean value from `v`, with no allocation. Readers and tests call it for a257        /// boolean value.258        pub fn initBoolean(v: bool) Self {259            return .{ .boolean = v };260        }261262        /// Makes a double value from `v`, with no allocation. The binary and text readers call it263        /// for a double value.264        pub fn initDouble(v: f64) Self {265            return .{ .double = v };266        }267268        /// Makes an integer value from `v`, with no allocation. Readers and constructors call it269        /// for an integer value.270        pub fn initI128(v: i128) Self {271            return .{ .signed_integer = SignedInteger.fromI128(v) };272        }273274        /// Makes an integer value from `v`, stored in 128 signed bits when it fits there, with no275        /// allocation. Code that holds a number above the 128-bit signed range calls it, as the276        /// tests of `text.encode` do.277        pub fn initU128(v: u128) Self {278            return .{ .signed_integer = SignedInteger.fromU128(v) };279        }280281        /// Makes an integer value from `v`. The readers call it for an integer they already parsed.282        /// The value takes `v`'s heap digits, so `deinit` on the value frees them.283        pub fn initSignedInteger(v: SignedInteger) Self {284            return .{ .signed_integer = v };285        }286287        /// Makes a string value holding a copy of `bytes` from `allocator`. Code that builds a288        /// string it must own calls it, as `cloneValueDeep` does. `deinit` with the same allocator289        /// frees the copy.290        pub fn initString(allocator: Allocator, bytes: []const u8) !Self {291            return .{ .string = try allocator.dupe(u8, bytes) };292        }293294        /// Makes a byte-string value holding a copy of `bytes` from `allocator`. Code that builds a295        /// byte string it must own calls it. `deinit` with the same allocator frees the copy.296        pub fn initByteString(allocator: Allocator, bytes: []const u8) !Self {297            return .{ .byte_string = try allocator.dupe(u8, bytes) };298        }299300        /// Makes a symbol value holding a copy of `bytes` from `allocator`. Code that builds a301        /// symbol it must own calls it, as the record builders and `cloneValueDeep` do. `deinit`302        /// with the same allocator frees the copy.303        pub fn initSymbol(allocator: Allocator, bytes: []const u8) !Self {304            return .{ .symbol = try allocator.dupe(u8, bytes) };305        }306307        /// Makes a record from `label` and `fields`, allocating one cell for the label from308        /// `allocator`. The binary and text readers and `cloneValueDeep` call it for a record whose309        /// parts they own. The record takes `fields` as given, with no copy, so `deinit` with the310        /// same allocator frees the slice, the label and every field. On `error.OutOfMemory`311        /// nothing is allocated, and the caller still owns `label` and `fields`.312        pub fn initRecord(allocator: Allocator, label: Self, fields: Sequence) !Self {313            const label_ptr = try allocator.create(Self);314            errdefer allocator.destroy(label_ptr);315            label_ptr.* = label;316            return .{ .record = .{ .label = label_ptr, .fields = fields } };317        }318319        /// Makes a sequence that takes `items` as given, with no copy and no allocation.320        /// `cloneValueDeep` and the embedded copy function call it for a sequence whose slice they321        /// own.322        pub fn initSequence(items: Sequence) Self {323            return .{ .sequence = items };324        }325326        /// Makes a set that takes `items` as given, with no copy, no sort and no allocation.327        /// `cloneValueDeep` and the embedded copy function call it for a copy of a set already held328        /// as a value, so no second check runs. The call does not check for equal elements, so a329        /// caller who has not checked calls `setElementsDistinct` first or uses the `set`330        /// constructor.331        pub fn initSet(items: Set) Self {332            return .{ .set = items };333        }334335        /// Makes a dictionary that takes `entries` as given, with no copy, no sort and no336        /// allocation. `cloneValueDeep` and the embedded copy function call it for a copy of a337        /// dictionary already held as a value, so no second check runs. The call does not check for338        /// equal keys, so a caller who has not checked calls `dictionaryKeysDistinct` first or uses339        /// the `dictionary` constructor.340        pub fn initDictionary(entries: Dictionary) Self {341            return .{ .dictionary = entries };342        }343344        /// Returns whether some item of `items` equals `needle` under `eql`. The binary and text345        /// readers call it with the elements read so far, so each new element that repeats one is346        /// rejected. The call scans every item and allocates nothing.347        pub fn setContainsElement(items: []const Self, needle: Self) bool {348            for (items) |item| {349                if (item.eql(needle)) return true;350            }351            return false;352        }353354        /// Returns whether some entry of `entries` has a key equal to `needle` under `eql`. The355        /// binary and text readers call it with the keys read so far, so each new key that repeats356        /// one is rejected. The call scans every entry and allocates nothing.357        pub fn dictionaryContainsKey(358            entries: []const DictionaryEntry,359            needle: Self,360        ) bool {361            for (entries) |entry| {362                if (entry.key.eql(needle)) return true;363            }364            return false;365        }366367        /// Returns whether no two items of `items` are equal. The `set` constructor and the binary,368        /// text and JSON writers call it to reject duplicate set elements. The call compares each369        /// item with every item before it, so its cost grows with the square of the slice's length,370        /// and it allocates nothing.371        pub fn setElementsDistinct(items: []const Self) bool {372            for (items, 0..) |item, index| {373                if (setContainsElement(items[0..index], item)) return false;374            }375            return true;376        }377378        /// Returns whether no two entries of `entries` have equal keys. The `dictionary`379        /// constructor and the binary, text and JSON writers call it to reject duplicate keys. The380        /// call compares each key with every key before it, so its cost grows with the square of381        /// the slice's length, and it allocates nothing.382        pub fn dictionaryKeysDistinct(entries: []const DictionaryEntry) bool {383            for (entries, 0..) |entry, index| {384                if (dictionaryContainsKey(entries[0..index], entry.key)) return false;385            }386            return true;387        }388389        /// Makes a value holding the embedded value `d`, with no allocation. The text reader and390        /// `cloneValueDeep` call it for an embedded value they built. `deinit` frees `d` through391        /// the type's `deinit`.392        pub fn initEmbedded(d: D) Self {393            return .{ .embedded = d };394        }395396        /// Returns a borrowed copy of the value's atom, and `null` for any other value. Code that397        /// takes one atom out of a value calls it for a copy that records who owns the bytes. The398        /// copy points at the value's own bytes, so the value has to outlive it.399        pub fn asAtom(self: *const Self) ?Atom {400            return switch (self.*) {401                .boolean => |v| Atom.fromBool(v),402                .double => |v| Atom.fromDouble(v),403                .signed_integer => |v| Atom.fromSignedIntegerBorrowed(v),404                .string => |v| Atom.fromStringBorrowed(v),405                .byte_string => |v| Atom.fromByteStringBorrowed(v),406                .symbol => |v| Atom.fromSymbolBorrowed(v),407                .record, .sequence, .set, .dictionary, .embedded => null,408                .discard, .capture, .bind, .rest_pattern => null,409            };410        }411412        /// Frees everything the value points to with `allocator`: atom bytes, integer digits,413        /// compound storage, the cells and names of patterns, and embedded values through the414        /// type's `deinit`. Code that decoded a value, or owns every byte of one, calls it when415        /// done with it. Every byte has to come from `allocator`, so a value that borrows any bytes416        /// goes to `freeValue` or `freeValueDeep`. Copies from `cloneValueDeep` own every byte. The417        /// value is undefined afterward.418        pub fn deinit(self: *Self, allocator: Allocator) void {419            switch (self.*) {420                .boolean, .double => {},421                .signed_integer => |*si| si.deinit(allocator),422                .string => |s| allocator.free(s),423                .byte_string => |s| allocator.free(s),424                .symbol => |s| allocator.free(s),425                .record => |*r| {426                    r.label.deinit(allocator);427                    allocator.destroy(r.label);428                    for (r.fields) |*f| f.deinit(allocator);429                    allocator.free(r.fields);430                },431                .sequence => |s| {432                    for (s) |*item| item.deinit(allocator);433                    allocator.free(s);434                },435                .set => |s| {436                    for (s) |*item| item.deinit(allocator);437                    allocator.free(s);438                },439                .dictionary => |d| {440                    for (d) |*entry| {441                        entry.key.deinit(allocator);442                        entry.value.deinit(allocator);443                    }444                    allocator.free(d);445                },446                .embedded => |*e| D.deinit(e, allocator),447                .discard => {},448                .capture => |p| {449                    p.deinit(allocator);450                    allocator.destroy(p);451                },452                .bind => |*bp| {453                    bp.pattern.deinit(allocator);454                    allocator.destroy(bp.pattern);455                    allocator.free(bp.name);456                },457                .rest_pattern => |*rp| {458                    for (rp.prefix) |*item| item.deinit(allocator);459                    allocator.free(rp.prefix);460                    rp.rest.deinit(allocator);461                    allocator.destroy(rp.rest);462                },463            }464            self.* = undefined;465        }466467        /// Returns whether two values are equal: same kind and equal contents. Hash maps, sets and468        /// every duplicate check call it for value equality. Sets and dictionaries are equal when469        /// they hold the same elements or entries, each as many times, whatever their storage470        /// order. Doubles compare by bits, binds by name and pattern, and embedded values through471        /// the type's `eql`. The call allocates nothing, and its cost on two sets grows with the472        /// square of their size.473        pub fn eql(a: Self, b: Self) bool {474            if (!a.kind().eql(b.kind())) return false;475            return switch (a) {476                .boolean => |v| v == b.boolean,477                .double => |v| @as(u64, @bitCast(v)) == @as(u64, @bitCast(b.double)),478                .signed_integer => |v| v.eql(b.signed_integer),479                .string => |v| std.mem.eql(u8, v, b.string),480                .byte_string => |v| std.mem.eql(u8, v, b.byte_string),481                .symbol => |v| std.mem.eql(u8, v, b.symbol),482                .record => |v| v.label.*.eql(b.record.label.*) and sequenceEql(v.fields, b.record.fields),483                .sequence => |v| sequenceEql(v, b.sequence),484                .set => |v| setEql(v, b.set),485                .dictionary => |v| dictionaryEql(v, b.dictionary),486                .embedded => |v| D.eql(v, b.embedded),487                .discard => true,488                .capture => |p| p.eql(b.capture.*),489                .bind => |bp| std.mem.eql(u8, bp.name, b.bind.name) and bp.pattern.eql(b.bind.pattern.*),490                .rest_pattern => |rp| sequenceEql(rp.prefix, b.rest_pattern.prefix) and rp.rest.eql(b.rest_pattern.rest.*),491            };492        }493494        fn sequenceEql(a: []const Self, b: []const Self) bool {495            if (a.len != b.len) return false;496            for (a, b) |av, bv| if (!av.eql(bv)) return false;497            return true;498        }499500        fn setEql(a: Set, b: Set) bool {501            if (a.len != b.len) return false;502            for (a, 0..) |candidate, i| {503                if (countSetMatches(a[0..i], candidate) != 0) continue;504                if (countSetMatches(a, candidate) != countSetMatches(b, candidate)) return false;505            }506            return true;507        }508509        fn countSetMatches(items: []const Self, needle: Self) usize {510            var count: usize = 0;511            for (items) |item| {512                if (item.eql(needle)) count += 1;513            }514            return count;515        }516517        fn dictionaryEql(a: Dictionary, b: Dictionary) bool {518            if (a.len != b.len) return false;519            for (a, 0..) |candidate, i| {520                if (countDictionaryEntryMatches(a[0..i], candidate) != 0) continue;521                if (countDictionaryEntryMatches(a, candidate) != countDictionaryEntryMatches(b, candidate)) return false;522            }523            return true;524        }525526        fn countDictionaryEntryMatches(entries: Dictionary, needle: DictionaryEntry) usize {527            var count: usize = 0;528            for (entries) |entry| {529                if (entry.key.eql(needle.key) and entry.value.eql(needle.value)) count += 1;530            }531            return count;532        }533534        /// Returns the order of `a` against `b`, a total order over all values. Sorting535        /// constructors and writers call it for the package's one total order. Kinds rank booleans,536        /// doubles, integers, strings, byte strings, symbols, records, sequences, sets,537        /// dictionaries, embedded values, then the four kinds of pattern. Within a kind, records538        /// compare label then fields, sequences item by item, and sets and dictionaries through539        /// their elements in ascending order, with a shorter list that matches ranking first.540        /// Embedded values order through the type's `order`. The call allocates nothing, and its541        /// cost on two sets grows with the square of their size.542        pub fn compare(a: Self, b: Self) std.math.Order {543            const ra = typeRank(a);544            const rb = typeRank(b);545            if (ra != rb) return std.math.order(ra, rb);546            return switch (a) {547                .boolean => |va| std.math.order(@intFromBool(va), @intFromBool(b.boolean)),548                .double => |va| floatTotalOrder(va, b.double),549                .signed_integer => |va| va.order(b.signed_integer),550                .string => |va| std.mem.order(u8, va, b.string),551                .byte_string => |va| std.mem.order(u8, va, b.byte_string),552                .symbol => |va| std.mem.order(u8, va, b.symbol),553                .record => |va| recordCompare(va, b.record),554                .sequence => |va| sliceCompare(va, b.sequence),555                .set => |va| setCompare(va, b.set),556                .dictionary => |va| dictionaryCompare(va, b.dictionary),557                .embedded => |va| D.order(va, b.embedded),558                .discard => .eq,559                .capture => |va| va.compare(b.capture.*),560                .bind => |va| bindCompare(va, b.bind),561                .rest_pattern => |va| restPatternCompare(va, b.rest_pattern),562            };563        }564565        fn typeRank(v: Self) u8 {566            return switch (v) {567                .boolean => 0,568                .double => 1,569                .signed_integer => 2,570                .string => 3,571                .byte_string => 4,572                .symbol => 5,573                .record => 6,574                .sequence => 7,575                .set => 8,576                .dictionary => 9,577                .embedded => 10,578                .discard => 11,579                .capture => 12,580                .bind => 13,581                .rest_pattern => 14,582            };583        }584585        fn recordCompare(a: Record, b: Record) std.math.Order {586            const label_ord = a.label.compare(b.label.*);587            if (label_ord != .eq) return label_ord;588            return sliceCompare(a.fields, b.fields);589        }590591        const ValueCursor = struct {592            items: []const Self,593            after: ?Self = null,594            current: ?Self = null,595            remaining: usize = 0,596597            fn next(cursor: *@This()) Self {598                if (cursor.remaining == 0) {599                    const run = nextValueRun(cursor.items, cursor.after).?;600                    cursor.current = run.value;601                    cursor.after = run.value;602                    cursor.remaining = run.count;603                }604                cursor.remaining -= 1;605                return cursor.current.?;606            }607        };608609        const ValueRun = struct {610            value: Self,611            count: usize,612        };613614        fn nextValueRun(items: []const Self, after: ?Self) ?ValueRun {615            var candidate: ?Self = null;616            for (items) |item| {617                if (after) |previous| {618                    if (item.compare(previous) != .gt) continue;619                }620                if (candidate == null or item.compare(candidate.?) == .lt) {621                    candidate = item;622                }623            }624            const value = candidate orelse return null;625            var count: usize = 0;626            for (items) |item| {627                if (item.compare(value) == .eq) count += 1;628            }629            return .{ .value = value, .count = count };630        }631632        fn setCompare(a: Set, b: Set) std.math.Order {633            var a_cursor = ValueCursor{ .items = a };634            var b_cursor = ValueCursor{ .items = b };635            for (0..@min(a.len, b.len)) |_| {636                const order = a_cursor.next().compare(b_cursor.next());637                if (order != .eq) return order;638            }639            return std.math.order(a.len, b.len);640        }641642        const DictionaryCursor = struct {643            entries: Dictionary,644            after: ?DictionaryEntry = null,645            current: ?DictionaryEntry = null,646            remaining: usize = 0,647648            fn next(cursor: *@This()) DictionaryEntry {649                if (cursor.remaining == 0) {650                    const run = nextDictionaryRun(cursor.entries, cursor.after).?;651                    cursor.current = run.entry;652                    cursor.after = run.entry;653                    cursor.remaining = run.count;654                }655                cursor.remaining -= 1;656                return cursor.current.?;657            }658        };659660        const DictionaryRun = struct {661            entry: DictionaryEntry,662            count: usize,663        };664665        fn dictionaryEntryCompare(a: DictionaryEntry, b: DictionaryEntry) std.math.Order {666            const key_order = a.key.compare(b.key);667            if (key_order != .eq) return key_order;668            return a.value.compare(b.value);669        }670671        fn nextDictionaryRun(entries: Dictionary, after: ?DictionaryEntry) ?DictionaryRun {672            var candidate: ?DictionaryEntry = null;673            for (entries) |entry| {674                if (after) |previous| {675                    if (dictionaryEntryCompare(entry, previous) != .gt) continue;676                }677                if (candidate == null or dictionaryEntryCompare(entry, candidate.?) == .lt) {678                    candidate = entry;679                }680            }681            const selected = candidate orelse return null;682            var count: usize = 0;683            for (entries) |entry| {684                if (dictionaryEntryCompare(entry, selected) == .eq) count += 1;685            }686            return .{ .entry = selected, .count = count };687        }688689        fn dictionaryCompare(a: Dictionary, b: Dictionary) std.math.Order {690            var a_cursor = DictionaryCursor{ .entries = a };691            var b_cursor = DictionaryCursor{ .entries = b };692            for (0..@min(a.len, b.len)) |_| {693                const order = dictionaryEntryCompare(a_cursor.next(), b_cursor.next());694                if (order != .eq) return order;695            }696            return std.math.order(a.len, b.len);697        }698699        fn bindCompare(a: Bind, b: Bind) std.math.Order {700            const no = std.mem.order(u8, a.name, b.name);701            if (no != .eq) return no;702            return a.pattern.compare(b.pattern.*);703        }704705        fn restPatternCompare(a: RestPattern, b: RestPattern) std.math.Order {706            const po = sliceCompare(a.prefix, b.prefix);707            if (po != .eq) return po;708            return a.rest.compare(b.rest.*);709        }710711        fn sliceCompare(a: []const Self, b: []const Self) std.math.Order {712            const len = @min(a.len, b.len);713            for (a[0..len], b[0..len]) |ia, ib| {714                const o = ia.compare(ib);715                if (o != .eq) return o;716            }717            return std.math.order(a.len, b.len);718        }719720        fn floatTotalOrder(a: f64, b: f64) std.math.Order {721            const bits_a = @as(u64, @bitCast(a));722            const bits_b = @as(u64, @bitCast(b));723            const sign_a = bits_a >> 63;724            const sign_b = bits_b >> 63;725            if (sign_a != sign_b) return if (sign_a > sign_b) .lt else .gt;726            if (sign_a == 1) return std.math.order(bits_b, bits_a);727            return std.math.order(bits_a, bits_b);728        }729730        /// Returns a 64-bit Wyhash, seed 0, of the value's kind and contents. Hash maps call it.731        /// Sets and dictionaries feed their elements in ascending order under `compare`, so equal732        /// values hash alike whatever their storage order. An embedded value adds its type's `hash`733        /// when the type declares one, and nothing otherwise. The call allocates nothing, and its734        /// cost on a set grows with the square of the set's size.735        pub fn hash(self: Self) u64 {736            var hasher = std.hash.Wyhash.init(0);737            hashInto(&hasher, self);738            return hasher.final();739        }740741        fn hashInto(hasher: *std.hash.Wyhash, v: Self) void {742            const tag: u8 = typeRank(v);743            hasher.update(&.{tag});744            switch (v) {745                .boolean => |b| hasher.update(&.{@intFromBool(b)}),746                .double => |f| {747                    const bits: u64 = @bitCast(f);748                    hasher.update(std.mem.asBytes(&bits));749                },750                .signed_integer => |si| hashSignedInteger(hasher, si),751                .string => |s| hasher.update(s),752                .byte_string => |b| hasher.update(b),753                .symbol => |s| hasher.update(s),754                .record => |r| {755                    hashInto(hasher, r.label.*);756                    for (r.fields) |field| hashInto(hasher, field);757                },758                .sequence => |s| for (s) |item| hashInto(hasher, item),759                .set => |s| {760                    var cursor = ValueCursor{ .items = s };761                    for (0..s.len) |_| hashInto(hasher, cursor.next());762                },763                .dictionary => |d| {764                    var cursor = DictionaryCursor{ .entries = d };765                    for (0..d.len) |_| {766                        const entry = cursor.next();767                        hashInto(hasher, entry.key);768                        hashInto(hasher, entry.value);769                    }770                },771                .embedded => |e| {772                    if (@hasDecl(D, "hash")) {773                        const h: u64 = D.hash(e);774                        hasher.update(std.mem.asBytes(&h));775                    }776                },777                .discard => {},778                .capture => |p| hashInto(hasher, p.*),779                .bind => |bp| {780                    hasher.update(bp.name);781                    hashInto(hasher, bp.pattern.*);782                },783                .rest_pattern => |rp| {784                    for (rp.prefix) |item| hashInto(hasher, item);785                    hashInto(hasher, rp.rest.*);786                },787            }788        }789790        fn hashSignedInteger(hasher: *std.hash.Wyhash, si: SignedInteger) void {791            switch (si.repr) {792                .i128 => |iv| {793                    hasher.update(&.{0});794                    hasher.update(std.mem.asBytes(&iv));795                },796                .u128 => |uv| {797                    hasher.update(&.{1});798                    hasher.update(std.mem.asBytes(&uv));799                },800                .big => |b| {801                    hasher.update(&.{2});802                    hasher.update(b);803                },804            }805        }806    };807}808809test "Value(NoEmbedded) atoms round-trip through kind" {810    const V = Value(NoEmbedded);811    try std.testing.expectEqual(AtomClass.boolean, V.initBoolean(true).atomClass().?);812    try std.testing.expectEqual(AtomClass.double, V.initDouble(1.5).atomClass().?);813    try std.testing.expectEqual(AtomClass.signed_integer, V.initI128(42).atomClass().?);814}815816test "Value(NoEmbedded) compound smoke" {817    const V = Value(NoEmbedded);818    const allocator = std.testing.allocator;819820    var arena = std.heap.ArenaAllocator.init(allocator);821    defer arena.deinit();822    const arena_alloc = arena.allocator();823824    const sym = try V.initSymbol(arena_alloc, "tag");825    const fields = try arena_alloc.alloc(V, 2);826    fields[0] = V.initI128(1);827    fields[1] = V.initBoolean(false);828    var rec = try V.initRecord(arena_alloc, sym, fields);829    try std.testing.expectEqual(CompoundClass.record, rec.compoundClass().?);830    try std.testing.expect(rec.eql(rec));831    _ = &rec;832}833834test "Value.asAtom produces a borrowed view" {835    const V = Value(NoEmbedded);836    const literal = "hi";837    const v = V{ .string = literal };838    const atom = v.asAtom().?;839    try std.testing.expectEqual(AtomClass.string, atom.class());840    try std.testing.expectEqual(Ownership.borrowed, atom.string.ownership);841    try std.testing.expect(std.mem.eql(u8, atom.string.bytes, literal));842}843844test "Value.eql distinguishes duplicate-bearing sets" {845    const V = Value(NoEmbedded);846    const allocator = std.testing.allocator;847848    var arena = std.heap.ArenaAllocator.init(allocator);849    defer arena.deinit();850    const a = arena.allocator();851852    const duplicate_items = try a.alloc(V, 2);853    duplicate_items[0] = V.initI128(1);854    duplicate_items[1] = V.initI128(1);855856    const canonical_items = try a.alloc(V, 2);857    canonical_items[0] = V.initI128(1);858    canonical_items[1] = V.initI128(2);859860    try std.testing.expect(!V.initSet(duplicate_items).eql(V.initSet(canonical_items)));861}862863test "Value.eql distinguishes duplicate-bearing dictionaries" {864    const V = Value(NoEmbedded);865    const allocator = std.testing.allocator;866867    var arena = std.heap.ArenaAllocator.init(allocator);868    defer arena.deinit();869    const a = arena.allocator();870871    const duplicate_entries = try a.alloc(V.DictionaryEntry, 2);872    duplicate_entries[0] = .{873        .key = try V.initSymbol(a, "dup"),874        .value = V.initI128(1),875    };876    duplicate_entries[1] = .{877        .key = try V.initSymbol(a, "dup"),878        .value = V.initI128(1),879    };880881    const canonical_entries = try a.alloc(V.DictionaryEntry, 2);882    canonical_entries[0] = .{883        .key = try V.initSymbol(a, "dup"),884        .value = V.initI128(1),885    };886    canonical_entries[1] = .{887        .key = try V.initSymbol(a, "other"),888        .value = V.initI128(1),889    };890891    try std.testing.expect(!V.initDictionary(duplicate_entries).eql(V.initDictionary(canonical_entries)));892}893894test "Value pattern-form variants surface their class" {895    const V = Value(NoEmbedded);896    const allocator = std.testing.allocator;897    var arena = std.heap.ArenaAllocator.init(allocator);898    defer arena.deinit();899    const a = arena.allocator();900901    const discard_v: V = .{ .discard = {} };902    try std.testing.expectEqual(PatternFormClass.discard, discard_v.patternClass().?);903    try std.testing.expect(discard_v.atomClass() == null);904    try std.testing.expect(discard_v.compoundClass() == null);905    try std.testing.expect(discard_v.asAtom() == null);906907    const inner = try a.create(V);908    inner.* = V.initI128(7);909    const capture_v: V = .{ .capture = inner };910    try std.testing.expectEqual(PatternFormClass.capture, capture_v.patternClass().?);911912    const bind_inner = try a.create(V);913    bind_inner.* = V.initBoolean(true);914    const bind_v: V = .{ .bind = .{ .name = "x", .pattern = bind_inner } };915    try std.testing.expectEqual(PatternFormClass.bind, bind_v.patternClass().?);916917    const prefix = try a.alloc(V, 1);918    prefix[0] = V.initI128(1);919    const rest = try a.create(V);920    rest.* = .{ .discard = {} };921    const rest_v: V = .{ .rest_pattern = .{ .prefix = prefix, .rest = rest } };922    try std.testing.expectEqual(PatternFormClass.rest_pattern, rest_v.patternClass().?);923924    try std.testing.expect(discard_v.eql(discard_v));925    try std.testing.expect(!discard_v.eql(capture_v));926}927928test "Value.compare total-orders across kind ranks" {929    const V = Value(NoEmbedded);930    const allocator = std.testing.allocator;931    var arena = std.heap.ArenaAllocator.init(allocator);932    defer arena.deinit();933    const a = arena.allocator();934935    try std.testing.expectEqual(std.math.Order.lt, V.compare(V.initBoolean(false), V.initBoolean(true)));936    try std.testing.expectEqual(std.math.Order.eq, V.compare(V.initI128(5), V.initI128(5)));937    try std.testing.expectEqual(std.math.Order.lt, V.compare(V.initDouble(1.0), V.initI128(0)));938    const ss = try V.initString(a, "abc");939    const sb = try V.initString(a, "abd");940    try std.testing.expectEqual(std.math.Order.lt, V.compare(ss, sb));941942    const discard_v: V = .{ .discard = {} };943    try std.testing.expectEqual(std.math.Order.gt, V.compare(discard_v, V.initI128(0)));944    try std.testing.expectEqual(std.math.Order.eq, V.compare(discard_v, discard_v));945}946947test "Value.hash respects equality for canonical values" {948    const V = Value(NoEmbedded);949    const allocator = std.testing.allocator;950    var arena = std.heap.ArenaAllocator.init(allocator);951    defer arena.deinit();952    const a = arena.allocator();953954    const x = V.initI128(42);955    const y = V.initI128(42);956    try std.testing.expectEqual(x.hash(), y.hash());957958    const s1 = try V.initString(a, "hello");959    const s2 = try V.initString(a, "hello");960    try std.testing.expectEqual(s1.hash(), s2.hash());961962    try std.testing.expect(x.hash() != V.initI128(7).hash());963}