tiny.preserves.Value

1/// Returns the tagged union of all values whose embedded values have type `D`. Every program that2/// stores Preserves data calls it once for the type of its embedded values, as the text codec does3/// with `AnyEmbedded`. The function stops compilation unless `D` meets `assertIsDomain`. Whether4/// atom bytes are borrowed or copied depends on the constructor: `initString`, `initByteString` and5/// `initSymbol` copy, and the root's `string` and `symbol` borrow. A value owns a compound's slice6/// only when its creator hands the slice over and later calls `deinit` with the same allocator.7/// Every decoder copies the bytes it reads, so a decoded value owns every byte and `deinit` frees8/// it.9pub fn Value(comptime D: type) type {10    domain_mod.assertIsDomain(D);11    return union(enum) {12        pub const Self = @This();13        /// The type of the embedded values, `D`. Generic code reads it to recover the type of the14        /// embedded values from a value type. `text.decode` and the binary `decode` take that type15        /// as their first parameter, so `Value.Domain` fills it.16        pub const Domain = D;17        /// A slice of values, the storage of a sequence and of a record's fields. Code that builds18        /// a record's fields or a sequence names the slice with this type.19        pub const Sequence = []Self;20        /// A slice of values, the storage of a set, holding each element once in any order. Code21        /// that builds a set names the slice with this type. Equality, order and hash read it in22        /// ascending order under `compare`.23        pub const Set = []Self;24        /// One key and value pair of a dictionary. Code that builds a dictionary names each entry25        /// with this type, as the constructors and the JSON reader do.26        pub const DictionaryEntry = struct {27            /// The entry's key, which appears once in its dictionary.28            key: Self,29            /// The value the key maps to.30            value: Self,31        };32        /// A slice of entries, the storage of a dictionary, in any order. Code that builds a33        /// dictionary names the slice with this type. Equality, order and hash read the entries in34        /// ascending order of key, then value, under `compare`.35        pub const Dictionary = []DictionaryEntry;36        /// The parts of a record: a label and its fields. Code that reads a record names its parts37        /// with this type.38        pub const Record = struct {39            /// A pointer to the label value, kept in its own cell so a record can have any value as40            /// its label. Records compare their labels first.41            label: *Self,42            /// The record's fields, in order. Records with equal labels compare their fields in43            /// order, and a shorter list that matches ranks first.44            fields: Sequence,45        };46        /// The parts of a bind: a name and the pattern it names. Code that reads a bind names its47        /// parts with this type.48        pub const Bind = struct {49            /// The bind's name. Two binds are equal only when their names are equal byte for byte.50            /// `deinit` frees the name, and `freeValue` and `freeValueDeep` leave it.51            name: []const u8,52            /// A pointer to the pattern the bind names, in its own cell.53            pattern: *Self,54        };55        /// The parts of a rest pattern: patterns for the first items of a sequence and one pattern56        /// for the items after them. Code that reads a rest pattern names its parts with this type.57        pub const RestPattern = struct {58            /// The patterns for the first items, in order.59            prefix: []Self,60            /// A pointer to the pattern for the items after the prefix, in its own cell.61            rest: *Self,62        };6364        /// A boolean. `false` orders before `true`.65        boolean: bool,66        /// A 64-bit double. Doubles are equal when their bits are equal, and they order by a total67        /// order over their bits, so `0.0` and `-0.0` differ and a `NaN` has one place.68        double: f64,69        /// An integer of any size. `deinit` frees its heap digits when it has any.70        signed_integer: SignedInteger,71        /// The string's bytes. The text reader rejects invalid UTF-8 bytes. Strings compare byte by72        /// byte.73        string: []const u8,74        /// The byte string's bytes, compared byte by byte.75        byte_string: []const u8,76        /// The symbol's name bytes, compared byte by byte.77        symbol: []const u8,78        /// A record: a label and its fields.79        record: Record,80        /// A sequence: values in order, compared item by item.81        sequence: Sequence,82        /// A set: each element once, stored in any order. Equality, order and hash read it in83        /// ascending order under `compare`, whatever the order of its storage.84        set: Set,85        /// A dictionary: each key once, mapped to a value, stored in any order. Equality, order and86        /// hash read it in ascending order of key, then value, whatever the order of its storage.87        dictionary: Dictionary,88        /// An embedded value of the type `D`, which supplies its equality, order, freeing and89        /// copying.90        embedded: D,91        /// The discard pattern carries no data. All discards are equal.92        discard: void,93        /// A capture: a pointer to its inner pattern, in its own cell.94        capture: *Self,95        /// A bind: a name and the pattern it names.96        bind: Bind,97        /// A rest pattern: patterns for a sequence's first items and one pattern for the rest.98        rest_pattern: RestPattern,99100        /// Returns the value's kind: its group and which member of the group. Code that switches on101        /// a value's kind calls it.102        pub fn kind(self: Self) ValueKind {103            return switch (self) {104                .boolean => .{ .atomic = .boolean },105                .double => .{ .atomic = .double },106                .signed_integer => .{ .atomic = .signed_integer },107                .string => .{ .atomic = .string },108                .byte_string => .{ .atomic = .byte_string },109                .symbol => .{ .atomic = .symbol },110                .record => .{ .compound = .record },111                .sequence => .{ .compound = .sequence },112                .set => .{ .compound = .set },113                .dictionary => .{ .compound = .dictionary },114                .embedded => .embedded,115                .discard => .{ .pattern = .discard },116                .capture => .{ .pattern = .capture },117                .bind => .{ .pattern = .bind },118                .rest_pattern => .{ .pattern = .rest_pattern },119            };120        }121122        /// Returns the atom kind of an atom, and `null` for any other value. Code that handles123        /// atoms calls it to test for one and learn which.124        pub fn atomClass(self: Self) ?AtomClass {125            return switch (self.kind()) {126                .atomic => |a| a,127                else => null,128            };129        }130131        /// Returns the compound kind of a compound, and `null` for any other value. Code that132        /// handles compounds calls it to test for one and learn which.133        pub fn compoundClass(self: Self) ?CompoundClass {134            return switch (self.kind()) {135                .compound => |c| c,136                else => null,137            };138        }139140        /// Returns the kind of pattern, and `null` for any other value. Code that handles patterns141        /// calls it to test for one and learn which.142        pub fn patternClass(self: Self) ?PatternFormClass {143            return switch (self.kind()) {144                .pattern => |p| p,145                else => null,146            };147        }148149        /// Makes a boolean value from `v`, with no allocation. Readers and tests call it for a150        /// boolean value.151        pub fn initBoolean(v: bool) Self {152            return .{ .boolean = v };153        }154155        /// Makes a double value from `v`, with no allocation. The binary and text readers call it156        /// for a double value.157        pub fn initDouble(v: f64) Self {158            return .{ .double = v };159        }160161        /// Makes an integer value from `v`, with no allocation. Readers and constructors call it162        /// for an integer value.163        pub fn initI128(v: i128) Self {164            return .{ .signed_integer = SignedInteger.fromI128(v) };165        }166167        /// Makes an integer value from `v`, stored in 128 signed bits when it fits there, with no168        /// allocation. Code that holds a number above the 128-bit signed range calls it, as the169        /// tests of `text.encode` do.170        pub fn initU128(v: u128) Self {171            return .{ .signed_integer = SignedInteger.fromU128(v) };172        }173174        /// Makes an integer value from `v`. The readers call it for an integer they already parsed.175        /// The value takes `v`'s heap digits, so `deinit` on the value frees them.176        pub fn initSignedInteger(v: SignedInteger) Self {177            return .{ .signed_integer = v };178        }179180        /// Makes a string value holding a copy of `bytes` from `allocator`. Code that builds a181        /// string it must own calls it, as `cloneValueDeep` does. `deinit` with the same allocator182        /// frees the copy.183        pub fn initString(allocator: Allocator, bytes: []const u8) !Self {184            return .{ .string = try allocator.dupe(u8, bytes) };185        }186187        /// Makes a byte-string value holding a copy of `bytes` from `allocator`. Code that builds a188        /// byte string it must own calls it. `deinit` with the same allocator frees the copy.189        pub fn initByteString(allocator: Allocator, bytes: []const u8) !Self {190            return .{ .byte_string = try allocator.dupe(u8, bytes) };191        }192193        /// Makes a symbol value holding a copy of `bytes` from `allocator`. Code that builds a194        /// symbol it must own calls it, as the record builders and `cloneValueDeep` do. `deinit`195        /// with the same allocator frees the copy.196        pub fn initSymbol(allocator: Allocator, bytes: []const u8) !Self {197            return .{ .symbol = try allocator.dupe(u8, bytes) };198        }199200        /// Makes a record from `label` and `fields`, allocating one cell for the label from201        /// `allocator`. The binary and text readers and `cloneValueDeep` call it for a record whose202        /// parts they own. The record takes `fields` as given, with no copy, so `deinit` with the203        /// same allocator frees the slice, the label and every field. On `error.OutOfMemory`204        /// nothing is allocated, and the caller still owns `label` and `fields`.205        pub fn initRecord(allocator: Allocator, label: Self, fields: Sequence) !Self {206            const label_ptr = try allocator.create(Self);207            errdefer allocator.destroy(label_ptr);208            label_ptr.* = label;209            return .{ .record = .{ .label = label_ptr, .fields = fields } };210        }211212        /// Makes a sequence that takes `items` as given, with no copy and no allocation.213        /// `cloneValueDeep` and the embedded copy function call it for a sequence whose slice they214        /// own.215        pub fn initSequence(items: Sequence) Self {216            return .{ .sequence = items };217        }218219        /// Makes a set that takes `items` as given, with no copy, no sort and no allocation.220        /// `cloneValueDeep` and the embedded copy function call it for a copy of a set already held221        /// as a value, so no second check runs. The call does not check for equal elements, so a222        /// caller who has not checked calls `setElementsDistinct` first or uses the `set`223        /// constructor.224        pub fn initSet(items: Set) Self {225            return .{ .set = items };226        }227228        /// Makes a dictionary that takes `entries` as given, with no copy, no sort and no229        /// allocation. `cloneValueDeep` and the embedded copy function call it for a copy of a230        /// dictionary already held as a value, so no second check runs. The call does not check for231        /// equal keys, so a caller who has not checked calls `dictionaryKeysDistinct` first or uses232        /// the `dictionary` constructor.233        pub fn initDictionary(entries: Dictionary) Self {234            return .{ .dictionary = entries };235        }236237        /// Returns whether some item of `items` equals `needle` under `eql`. The binary and text238        /// readers call it with the elements read so far, so each new element that repeats one is239        /// rejected. The call scans every item and allocates nothing.240        pub fn setContainsElement(items: []const Self, needle: Self) bool {241            for (items) |item| {242                if (item.eql(needle)) return true;243            }244            return false;245        }246247        /// Returns whether some entry of `entries` has a key equal to `needle` under `eql`. The248        /// binary and text readers call it with the keys read so far, so each new key that repeats249        /// one is rejected. The call scans every entry and allocates nothing.250        pub fn dictionaryContainsKey(251            entries: []const DictionaryEntry,252            needle: Self,253        ) bool {254            for (entries) |entry| {255                if (entry.key.eql(needle)) return true;256            }257            return false;258        }259260        /// Returns whether no two items of `items` are equal. The `set` constructor and the binary,261        /// text and JSON writers call it to reject duplicate set elements. The call compares each262        /// item with every item before it, so its cost grows with the square of the slice's length,263        /// and it allocates nothing.264        pub fn setElementsDistinct(items: []const Self) bool {265            for (items, 0..) |item, index| {266                if (setContainsElement(items[0..index], item)) return false;267            }268            return true;269        }270271        /// Returns whether no two entries of `entries` have equal keys. The `dictionary`272        /// constructor and the binary, text and JSON writers call it to reject duplicate keys. The273        /// call compares each key with every key before it, so its cost grows with the square of274        /// the slice's length, and it allocates nothing.275        pub fn dictionaryKeysDistinct(entries: []const DictionaryEntry) bool {276            for (entries, 0..) |entry, index| {277                if (dictionaryContainsKey(entries[0..index], entry.key)) return false;278            }279            return true;280        }281282        /// Makes a value holding the embedded value `d`, with no allocation. The text reader and283        /// `cloneValueDeep` call it for an embedded value they built. `deinit` frees `d` through284        /// the type's `deinit`.285        pub fn initEmbedded(d: D) Self {286            return .{ .embedded = d };287        }288289        /// Returns a borrowed copy of the value's atom, and `null` for any other value. Code that290        /// takes one atom out of a value calls it for a copy that records who owns the bytes. The291        /// copy points at the value's own bytes, so the value has to outlive it.292        pub fn asAtom(self: *const Self) ?Atom {293            return switch (self.*) {294                .boolean => |v| Atom.fromBool(v),295                .double => |v| Atom.fromDouble(v),296                .signed_integer => |v| Atom.fromSignedIntegerBorrowed(v),297                .string => |v| Atom.fromStringBorrowed(v),298                .byte_string => |v| Atom.fromByteStringBorrowed(v),299                .symbol => |v| Atom.fromSymbolBorrowed(v),300                .record, .sequence, .set, .dictionary, .embedded => null,301                .discard, .capture, .bind, .rest_pattern => null,302            };303        }304305        /// Frees everything the value points to with `allocator`: atom bytes, integer digits,306        /// compound storage, the cells and names of patterns, and embedded values through the307        /// type's `deinit`. Code that decoded a value, or owns every byte of one, calls it when308        /// done with it. Every byte has to come from `allocator`, so a value that borrows any bytes309        /// goes to `freeValue` or `freeValueDeep`. Copies from `cloneValueDeep` own every byte. The310        /// value is undefined afterward.311        pub fn deinit(self: *Self, allocator: Allocator) void {312            switch (self.*) {313                .boolean, .double => {},314                .signed_integer => |*si| si.deinit(allocator),315                .string => |s| allocator.free(s),316                .byte_string => |s| allocator.free(s),317                .symbol => |s| allocator.free(s),318                .record => |*r| {319                    r.label.deinit(allocator);320                    allocator.destroy(r.label);321                    for (r.fields) |*f| f.deinit(allocator);322                    allocator.free(r.fields);323                },324                .sequence => |s| {325                    for (s) |*item| item.deinit(allocator);326                    allocator.free(s);327                },328                .set => |s| {329                    for (s) |*item| item.deinit(allocator);330                    allocator.free(s);331                },332                .dictionary => |d| {333                    for (d) |*entry| {334                        entry.key.deinit(allocator);335                        entry.value.deinit(allocator);336                    }337                    allocator.free(d);338                },339                .embedded => |*e| D.deinit(e, allocator),340                .discard => {},341                .capture => |p| {342                    p.deinit(allocator);343                    allocator.destroy(p);344                },345                .bind => |*bp| {346                    bp.pattern.deinit(allocator);347                    allocator.destroy(bp.pattern);348                    allocator.free(bp.name);349                },350                .rest_pattern => |*rp| {351                    for (rp.prefix) |*item| item.deinit(allocator);352                    allocator.free(rp.prefix);353                    rp.rest.deinit(allocator);354                    allocator.destroy(rp.rest);355                },356            }357            self.* = undefined;358        }359360        /// Returns whether two values are equal: same kind and equal contents. Hash maps, sets and361        /// every duplicate check call it for value equality. Sets and dictionaries are equal when362        /// they hold the same elements or entries, each as many times, whatever their storage363        /// order. Doubles compare by bits, binds by name and pattern, and embedded values through364        /// the type's `eql`. The call allocates nothing, and its cost on two sets grows with the365        /// square of their size.366        pub fn eql(a: Self, b: Self) bool {367            if (!a.kind().eql(b.kind())) return false;368            return switch (a) {369                .boolean => |v| v == b.boolean,370                .double => |v| @as(u64, @bitCast(v)) == @as(u64, @bitCast(b.double)),371                .signed_integer => |v| v.eql(b.signed_integer),372                .string => |v| std.mem.eql(u8, v, b.string),373                .byte_string => |v| std.mem.eql(u8, v, b.byte_string),374                .symbol => |v| std.mem.eql(u8, v, b.symbol),375                .record => |v| v.label.*.eql(b.record.label.*) and sequenceEql(v.fields, b.record.fields),376                .sequence => |v| sequenceEql(v, b.sequence),377                .set => |v| setEql(v, b.set),378                .dictionary => |v| dictionaryEql(v, b.dictionary),379                .embedded => |v| D.eql(v, b.embedded),380                .discard => true,381                .capture => |p| p.eql(b.capture.*),382                .bind => |bp| std.mem.eql(u8, bp.name, b.bind.name) and bp.pattern.eql(b.bind.pattern.*),383                .rest_pattern => |rp| sequenceEql(rp.prefix, b.rest_pattern.prefix) and rp.rest.eql(b.rest_pattern.rest.*),384            };385        }386387        fn sequenceEql(a: []const Self, b: []const Self) bool {388            if (a.len != b.len) return false;389            for (a, b) |av, bv| if (!av.eql(bv)) return false;390            return true;391        }392393        fn setEql(a: Set, b: Set) bool {394            if (a.len != b.len) return false;395            for (a, 0..) |candidate, i| {396                if (countSetMatches(a[0..i], candidate) != 0) continue;397                if (countSetMatches(a, candidate) != countSetMatches(b, candidate)) return false;398            }399            return true;400        }401402        fn countSetMatches(items: []const Self, needle: Self) usize {403            var count: usize = 0;404            for (items) |item| {405                if (item.eql(needle)) count += 1;406            }407            return count;408        }409410        fn dictionaryEql(a: Dictionary, b: Dictionary) bool {411            if (a.len != b.len) return false;412            for (a, 0..) |candidate, i| {413                if (countDictionaryEntryMatches(a[0..i], candidate) != 0) continue;414                if (countDictionaryEntryMatches(a, candidate) != countDictionaryEntryMatches(b, candidate)) return false;415            }416            return true;417        }418419        fn countDictionaryEntryMatches(entries: Dictionary, needle: DictionaryEntry) usize {420            var count: usize = 0;421            for (entries) |entry| {422                if (entry.key.eql(needle.key) and entry.value.eql(needle.value)) count += 1;423            }424            return count;425        }426427        /// Returns the order of `a` against `b`, a total order over all values. Sorting428        /// constructors and writers call it for the package's one total order. Kinds rank booleans,429        /// doubles, integers, strings, byte strings, symbols, records, sequences, sets,430        /// dictionaries, embedded values, then the four kinds of pattern. Within a kind, records431        /// compare label then fields, sequences item by item, and sets and dictionaries through432        /// their elements in ascending order, with a shorter list that matches ranking first.433        /// Embedded values order through the type's `order`. The call allocates nothing, and its434        /// cost on two sets grows with the square of their size.435        pub fn compare(a: Self, b: Self) std.math.Order {436            const ra = typeRank(a);437            const rb = typeRank(b);438            if (ra != rb) return std.math.order(ra, rb);439            return switch (a) {440                .boolean => |va| std.math.order(@intFromBool(va), @intFromBool(b.boolean)),441                .double => |va| floatTotalOrder(va, b.double),442                .signed_integer => |va| va.order(b.signed_integer),443                .string => |va| std.mem.order(u8, va, b.string),444                .byte_string => |va| std.mem.order(u8, va, b.byte_string),445                .symbol => |va| std.mem.order(u8, va, b.symbol),446                .record => |va| recordCompare(va, b.record),447                .sequence => |va| sliceCompare(va, b.sequence),448                .set => |va| setCompare(va, b.set),449                .dictionary => |va| dictionaryCompare(va, b.dictionary),450                .embedded => |va| D.order(va, b.embedded),451                .discard => .eq,452                .capture => |va| va.compare(b.capture.*),453                .bind => |va| bindCompare(va, b.bind),454                .rest_pattern => |va| restPatternCompare(va, b.rest_pattern),455            };456        }457458        fn typeRank(v: Self) u8 {459            return switch (v) {460                .boolean => 0,461                .double => 1,462                .signed_integer => 2,463                .string => 3,464                .byte_string => 4,465                .symbol => 5,466                .record => 6,467                .sequence => 7,468                .set => 8,469                .dictionary => 9,470                .embedded => 10,471                .discard => 11,472                .capture => 12,473                .bind => 13,474                .rest_pattern => 14,475            };476        }477478        fn recordCompare(a: Record, b: Record) std.math.Order {479            const label_ord = a.label.compare(b.label.*);480            if (label_ord != .eq) return label_ord;481            return sliceCompare(a.fields, b.fields);482        }483484        const ValueCursor = struct {485            items: []const Self,486            after: ?Self = null,487            current: ?Self = null,488            remaining: usize = 0,489490            fn next(cursor: *@This()) Self {491                if (cursor.remaining == 0) {492                    const run = nextValueRun(cursor.items, cursor.after).?;493                    cursor.current = run.value;494                    cursor.after = run.value;495                    cursor.remaining = run.count;496                }497                cursor.remaining -= 1;498                return cursor.current.?;499            }500        };501502        const ValueRun = struct {503            value: Self,504            count: usize,505        };506507        fn nextValueRun(items: []const Self, after: ?Self) ?ValueRun {508            var candidate: ?Self = null;509            for (items) |item| {510                if (after) |previous| {511                    if (item.compare(previous) != .gt) continue;512                }513                if (candidate == null or item.compare(candidate.?) == .lt) {514                    candidate = item;515                }516            }517            const value = candidate orelse return null;518            var count: usize = 0;519            for (items) |item| {520                if (item.compare(value) == .eq) count += 1;521            }522            return .{ .value = value, .count = count };523        }524525        fn setCompare(a: Set, b: Set) std.math.Order {526            var a_cursor = ValueCursor{ .items = a };527            var b_cursor = ValueCursor{ .items = b };528            for (0..@min(a.len, b.len)) |_| {529                const order = a_cursor.next().compare(b_cursor.next());530                if (order != .eq) return order;531            }532            return std.math.order(a.len, b.len);533        }534535        const DictionaryCursor = struct {536            entries: Dictionary,537            after: ?DictionaryEntry = null,538            current: ?DictionaryEntry = null,539            remaining: usize = 0,540541            fn next(cursor: *@This()) DictionaryEntry {542                if (cursor.remaining == 0) {543                    const run = nextDictionaryRun(cursor.entries, cursor.after).?;544                    cursor.current = run.entry;545                    cursor.after = run.entry;546                    cursor.remaining = run.count;547                }548                cursor.remaining -= 1;549                return cursor.current.?;550            }551        };552553        const DictionaryRun = struct {554            entry: DictionaryEntry,555            count: usize,556        };557558        fn dictionaryEntryCompare(a: DictionaryEntry, b: DictionaryEntry) std.math.Order {559            const key_order = a.key.compare(b.key);560            if (key_order != .eq) return key_order;561            return a.value.compare(b.value);562        }563564        fn nextDictionaryRun(entries: Dictionary, after: ?DictionaryEntry) ?DictionaryRun {565            var candidate: ?DictionaryEntry = null;566            for (entries) |entry| {567                if (after) |previous| {568                    if (dictionaryEntryCompare(entry, previous) != .gt) continue;569                }570                if (candidate == null or dictionaryEntryCompare(entry, candidate.?) == .lt) {571                    candidate = entry;572                }573            }574            const selected = candidate orelse return null;575            var count: usize = 0;576            for (entries) |entry| {577                if (dictionaryEntryCompare(entry, selected) == .eq) count += 1;578            }579            return .{ .entry = selected, .count = count };580        }581582        fn dictionaryCompare(a: Dictionary, b: Dictionary) std.math.Order {583            var a_cursor = DictionaryCursor{ .entries = a };584            var b_cursor = DictionaryCursor{ .entries = b };585            for (0..@min(a.len, b.len)) |_| {586                const order = dictionaryEntryCompare(a_cursor.next(), b_cursor.next());587                if (order != .eq) return order;588            }589            return std.math.order(a.len, b.len);590        }591592        fn bindCompare(a: Bind, b: Bind) std.math.Order {593            const no = std.mem.order(u8, a.name, b.name);594            if (no != .eq) return no;595            return a.pattern.compare(b.pattern.*);596        }597598        fn restPatternCompare(a: RestPattern, b: RestPattern) std.math.Order {599            const po = sliceCompare(a.prefix, b.prefix);600            if (po != .eq) return po;601            return a.rest.compare(b.rest.*);602        }603604        fn sliceCompare(a: []const Self, b: []const Self) std.math.Order {605            const len = @min(a.len, b.len);606            for (a[0..len], b[0..len]) |ia, ib| {607                const o = ia.compare(ib);608                if (o != .eq) return o;609            }610            return std.math.order(a.len, b.len);611        }612613        fn floatTotalOrder(a: f64, b: f64) std.math.Order {614            const bits_a = @as(u64, @bitCast(a));615            const bits_b = @as(u64, @bitCast(b));616            const sign_a = bits_a >> 63;617            const sign_b = bits_b >> 63;618            if (sign_a != sign_b) return if (sign_a > sign_b) .lt else .gt;619            if (sign_a == 1) return std.math.order(bits_b, bits_a);620            return std.math.order(bits_a, bits_b);621        }622623        /// Returns a 64-bit Wyhash, seed 0, of the value's kind and contents. Hash maps call it.624        /// Sets and dictionaries feed their elements in ascending order under `compare`, so equal625        /// values hash alike whatever their storage order. An embedded value adds its type's `hash`626        /// when the type declares one, and nothing otherwise. The call allocates nothing, and its627        /// cost on a set grows with the square of the set's size.628        pub fn hash(self: Self) u64 {629            var hasher = std.hash.Wyhash.init(0);630            hashInto(&hasher, self);631            return hasher.final();632        }633634        fn hashInto(hasher: *std.hash.Wyhash, v: Self) void {635            const tag: u8 = typeRank(v);636            hasher.update(&.{tag});637            switch (v) {638                .boolean => |b| hasher.update(&.{@intFromBool(b)}),639                .double => |f| {640                    const bits: u64 = @bitCast(f);641                    hasher.update(std.mem.asBytes(&bits));642                },643                .signed_integer => |si| hashSignedInteger(hasher, si),644                .string => |s| hasher.update(s),645                .byte_string => |b| hasher.update(b),646                .symbol => |s| hasher.update(s),647                .record => |r| {648                    hashInto(hasher, r.label.*);649                    for (r.fields) |field| hashInto(hasher, field);650                },651                .sequence => |s| for (s) |item| hashInto(hasher, item),652                .set => |s| {653                    var cursor = ValueCursor{ .items = s };654                    for (0..s.len) |_| hashInto(hasher, cursor.next());655                },656                .dictionary => |d| {657                    var cursor = DictionaryCursor{ .entries = d };658                    for (0..d.len) |_| {659                        const entry = cursor.next();660                        hashInto(hasher, entry.key);661                        hashInto(hasher, entry.value);662                    }663                },664                .embedded => |e| {665                    if (@hasDecl(D, "hash")) {666                        const h: u64 = D.hash(e);667                        hasher.update(std.mem.asBytes(&h));668                    }669                },670                .discard => {},671                .capture => |p| hashInto(hasher, p.*),672                .bind => |bp| {673                    hasher.update(bp.name);674                    hashInto(hasher, bp.pattern.*);675                },676                .rest_pattern => |rp| {677                    for (rp.prefix) |item| hashInto(hasher, item);678                    hashInto(hasher, rp.rest.*);679                },680            }681        }682683        fn hashSignedInteger(hasher: *std.hash.Wyhash, si: SignedInteger) void {684            switch (si.repr) {685                .i128 => |iv| {686                    hasher.update(&.{0});687                    hasher.update(std.mem.asBytes(&iv));688                },689                .u128 => |uv| {690                    hasher.update(&.{1});691                    hasher.update(std.mem.asBytes(&uv));692                },693                .big => |b| {694                    hasher.update(&.{2});695                    hasher.update(b);696                },697            }698        }699    };700}

1pub const Value = value.Value;