lib/preserves/src/value.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! One type holds every data value: atoms, compounds and embedded values of the host program. The
2 //! atoms are booleans, doubles, integers of any size, strings, byte strings and symbols, and the
3 //! 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 a
6 //! hash map and sort the same way everywhere. A program has to know which memory a value owns and
7 //! 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 text
10 //! document lists it in the order its author wrote. Comparing two sets element by element needs
11 //! both in sorted order, and sorting a copy would allocate memory on every comparison and every
12 //! hash. A value's leaves can point at bytes it owns or bytes someone else keeps alive, and the
13 //! value itself records neither.
14 //!
15 //! The type holds the values of the [Preserves](https://preserves.dev/) data language, which the
16 //! package keeps along with its patterns and its text, binary and JSON forms. Preserves gives all
17 //! values one total order in which sets and dictionaries compare through their elements in
18 //! ascending order, whatever their storage order.
19 //!
20 //! The package builds that one type as a generic tagged union (`Value`). The union takes the type
21 //! of its embedded values (*domain*) as a compile-time parameter, so each program picks what it
22 //! embeds. A compile-time check (`assertIsDomain`) tests that type before the union is built. The
23 //! union also holds four kinds of pattern (*pattern form*) beside the data: a discard, a capture of
24 //! an inner pattern, a bind that names an inner pattern, and a rest pattern for the items after a
25 //! sequence prefix. A value's kind (`ValueKind`) names its group (atom, compound, embedded value or
26 //! 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 hash
28 //! 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 element
32 //! by scanning the whole set, so the cost grows with the square of the set's size. A Lean model
33 //! proves that sorted copies of two sets are equal exactly when their elements are permutations of
34 //! each other, and that every observation of a sorted copy gives one answer for all such
35 //! permutations. The Lean results describe a model, and they check neither this Zig code nor its
36 //! 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 value
40 //! owns a compound's slice only when its creator hands the slice over and later frees the value
41 //! with the same allocator. `deinit` frees everything a value points to, so it fits a value that
42 //! owns every byte, such as a decoded value or a copy from `cloneValueDeep`.
43 const std = @import("std");
44 const Allocator = std.mem.Allocator;
45
46 const atom_mod = @import("atom.zig");
47 const integer_mod = @import("integer.zig");
48 const domain_mod = @import("domain.zig");
49
50 pub const AtomClass = atom_mod.AtomClass;
51 pub const Atom = atom_mod.Atom;
52 pub const CowBytes = atom_mod.CowBytes;
53 pub const CowSignedInteger = atom_mod.CowSignedInteger;
54 pub const Ownership = atom_mod.Ownership;
55 pub const SignedInteger = integer_mod.SignedInteger;
56 pub const NoEmbedded = domain_mod.NoEmbedded;
57
58 /// The four compound kinds, in the order `compare` ranks them: record, sequence, set and
59 /// 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.
61 pub const CompoundClass = enum { record, sequence, set, dictionary };
62
63 /// The four kinds of pattern, in the order `compare` ranks them: discard, capture, bind and rest
64 /// 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.
66 pub const PatternFormClass = enum { discard, capture, bind, rest_pattern };
67
68 /// The four groups of kinds: atom, compound, embedded value and pattern. Code that switches on the
69 /// group of a value's kind reads this from `ValueKind`. This enum tags `ValueKind`.
70 pub const ValueKindTag = enum { atomic, compound, embedded, pattern };
71
72 /// A value's kind: its group and, for an atom, a compound or a pattern, which one. Code that
73 /// switches on a value's kind reads this from `kind`. `kind` returns it for any value.
74 pub 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,
83
84 /// 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 };
107
108 /// Returns the tagged union of all values whose embedded values have type `D`. Every program that
109 /// stores Preserves data calls it once for the type of its embedded values, as the text codec does
110 /// with `AnyEmbedded`. The function stops compilation unless `D` meets `assertIsDomain`. Whether
111 /// atom bytes are borrowed or copied depends on the constructor: `initString`, `initByteString` and
112 /// `initSymbol` copy, and the root's `string` and `symbol` borrow. A value owns a compound's slice
113 /// 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` frees
115 /// it.
116 pub 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 the
121 /// embedded values from a value type. `text.decode` and the binary `decode` take that type
122 /// 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 builds
125 /// 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. Code
128 /// that builds a set names the slice with this type. Equality, order and hash read it in
129 /// 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 entry
132 /// 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 a
140 /// dictionary names the slice with this type. Equality, order and hash read the entries in
141 /// 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 parts
144 /// 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 as
147 /// its label. Records compare their labels first.
148 label: *Self,
149 /// The record's fields, in order. Records with equal labels compare their fields in
150 /// 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 its
154 /// 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 pattern
163 /// 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 };
170
171 /// 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 total
174 /// 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 by
179 /// 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 in
190 /// 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 and
193 /// 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 and
196 /// 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,
206
207 /// Returns the value's kind: its group and which member of the group. Code that switches on
208 /// 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 }
228
229 /// Returns the atom kind of an atom, and `null` for any other value. Code that handles
230 /// 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 }
237
238 /// Returns the compound kind of a compound, and `null` for any other value. Code that
239 /// 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 }
246
247 /// Returns the kind of pattern, and `null` for any other value. Code that handles patterns
248 /// 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 }
255
256 /// Makes a boolean value from `v`, with no allocation. Readers and tests call it for a
257 /// boolean value.
258 pub fn initBoolean(v: bool) Self {
259 return .{ .boolean = v };
260 }
261
262 /// Makes a double value from `v`, with no allocation. The binary and text readers call it
263 /// for a double value.
264 pub fn initDouble(v: f64) Self {
265 return .{ .double = v };
266 }
267
268 /// Makes an integer value from `v`, with no allocation. Readers and constructors call it
269 /// for an integer value.
270 pub fn initI128(v: i128) Self {
271 return .{ .signed_integer = SignedInteger.fromI128(v) };
272 }
273
274 /// Makes an integer value from `v`, stored in 128 signed bits when it fits there, with no
275 /// allocation. Code that holds a number above the 128-bit signed range calls it, as the
276 /// tests of `text.encode` do.
277 pub fn initU128(v: u128) Self {
278 return .{ .signed_integer = SignedInteger.fromU128(v) };
279 }
280
281 /// 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 }
286
287 /// Makes a string value holding a copy of `bytes` from `allocator`. Code that builds a
288 /// string it must own calls it, as `cloneValueDeep` does. `deinit` with the same allocator
289 /// frees the copy.
290 pub fn initString(allocator: Allocator, bytes: []const u8) !Self {
291 return .{ .string = try allocator.dupe(u8, bytes) };
292 }
293
294 /// Makes a byte-string value holding a copy of `bytes` from `allocator`. Code that builds a
295 /// 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 }
299
300 /// Makes a symbol value holding a copy of `bytes` from `allocator`. Code that builds a
301 /// 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 }
306
307 /// Makes a record from `label` and `fields`, allocating one cell for the label from
308 /// `allocator`. The binary and text readers and `cloneValueDeep` call it for a record whose
309 /// parts they own. The record takes `fields` as given, with no copy, so `deinit` with the
310 /// 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 }
318
319 /// 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 they
321 /// own.
322 pub fn initSequence(items: Sequence) Self {
323 return .{ .sequence = items };
324 }
325
326 /// 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 held
328 /// as a value, so no second check runs. The call does not check for equal elements, so a
329 /// 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 }
334
335 /// Makes a dictionary that takes `entries` as given, with no copy, no sort and no
336 /// allocation. `cloneValueDeep` and the embedded copy function call it for a copy of a
337 /// dictionary already held as a value, so no second check runs. The call does not check for
338 /// equal keys, so a caller who has not checked calls `dictionaryKeysDistinct` first or uses
339 /// the `dictionary` constructor.
340 pub fn initDictionary(entries: Dictionary) Self {
341 return .{ .dictionary = entries };
342 }
343
344 /// Returns whether some item of `items` equals `needle` under `eql`. The binary and text
345 /// readers call it with the elements read so far, so each new element that repeats one is
346 /// 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 }
353
354 /// Returns whether some entry of `entries` has a key equal to `needle` under `eql`. The
355 /// binary and text readers call it with the keys read so far, so each new key that repeats
356 /// 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 }
366
367 /// 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 each
369 /// 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 }
377
378 /// 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. The
380 /// call compares each key with every key before it, so its cost grows with the square of
381 /// 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 }
388
389 /// Makes a value holding the embedded value `d`, with no allocation. The text reader and
390 /// `cloneValueDeep` call it for an embedded value they built. `deinit` frees `d` through
391 /// the type's `deinit`.
392 pub fn initEmbedded(d: D) Self {
393 return .{ .embedded = d };
394 }
395
396 /// Returns a borrowed copy of the value's atom, and `null` for any other value. Code that
397 /// takes one atom out of a value calls it for a copy that records who owns the bytes. The
398 /// 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 }
411
412 /// 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 the
414 /// type's `deinit`. Code that decoded a value, or owns every byte of one, calls it when
415 /// done with it. Every byte has to come from `allocator`, so a value that borrows any bytes
416 /// goes to `freeValue` or `freeValueDeep`. Copies from `cloneValueDeep` own every byte. The
417 /// 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 }
466
467 /// Returns whether two values are equal: same kind and equal contents. Hash maps, sets and
468 /// every duplicate check call it for value equality. Sets and dictionaries are equal when
469 /// they hold the same elements or entries, each as many times, whatever their storage
470 /// order. Doubles compare by bits, binds by name and pattern, and embedded values through
471 /// the type's `eql`. The call allocates nothing, and its cost on two sets grows with the
472 /// 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 }
493
494 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 }
499
500 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 }
508
509 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 }
516
517 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 }
525
526 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 }
533
534 /// Returns the order of `a` against `b`, a total order over all values. Sorting
535 /// 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, records
538 /// compare label then fields, sequences item by item, and sets and dictionaries through
539 /// 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 its
541 /// 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 }
564
565 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 }
584
585 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 }
590
591 const ValueCursor = struct {
592 items: []const Self,
593 after: ?Self = null,
594 current: ?Self = null,
595 remaining: usize = 0,
596
597 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 };
608
609 const ValueRun = struct {
610 value: Self,
611 count: usize,
612 };
613
614 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 }
631
632 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 }
641
642 const DictionaryCursor = struct {
643 entries: Dictionary,
644 after: ?DictionaryEntry = null,
645 current: ?DictionaryEntry = null,
646 remaining: usize = 0,
647
648 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 };
659
660 const DictionaryRun = struct {
661 entry: DictionaryEntry,
662 count: usize,
663 };
664
665 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 }
670
671 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 }
688
689 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 }
698
699 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 }
704
705 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 }
710
711 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 }
719
720 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 }
729
730 /// 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 equal
732 /// 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 its
734 /// 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 }
740
741 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 }
789
790 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 }
808
809 test "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 }
815
816 test "Value(NoEmbedded) compound smoke" {
817 const V = Value(NoEmbedded);
818 const allocator = std.testing.allocator;
819
820 var arena = std.heap.ArenaAllocator.init(allocator);
821 defer arena.deinit();
822 const arena_alloc = arena.allocator();
823
824 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 }
833
834 test "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 }
843
844 test "Value.eql distinguishes duplicate-bearing sets" {
845 const V = Value(NoEmbedded);
846 const allocator = std.testing.allocator;
847
848 var arena = std.heap.ArenaAllocator.init(allocator);
849 defer arena.deinit();
850 const a = arena.allocator();
851
852 const duplicate_items = try a.alloc(V, 2);
853 duplicate_items[0] = V.initI128(1);
854 duplicate_items[1] = V.initI128(1);
855
856 const canonical_items = try a.alloc(V, 2);
857 canonical_items[0] = V.initI128(1);
858 canonical_items[1] = V.initI128(2);
859
860 try std.testing.expect(!V.initSet(duplicate_items).eql(V.initSet(canonical_items)));
861 }
862
863 test "Value.eql distinguishes duplicate-bearing dictionaries" {
864 const V = Value(NoEmbedded);
865 const allocator = std.testing.allocator;
866
867 var arena = std.heap.ArenaAllocator.init(allocator);
868 defer arena.deinit();
869 const a = arena.allocator();
870
871 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 };
880
881 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 };
890
891 try std.testing.expect(!V.initDictionary(duplicate_entries).eql(V.initDictionary(canonical_entries)));
892 }
893
894 test "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();
900
901 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);
906
907 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().?);
911
912 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().?);
916
917 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().?);
923
924 try std.testing.expect(discard_v.eql(discard_v));
925 try std.testing.expect(!discard_v.eql(capture_v));
926 }
927
928 test "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();
934
935 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));
941
942 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 }
946
947 test "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();
953
954 const x = V.initI128(42);
955 const y = V.initI128(42);
956 try std.testing.expectEqual(x.hash(), y.hash());
957
958 const s1 = try V.initString(a, "hello");
959 const s2 = try V.initString(a, "hello");
960 try std.testing.expectEqual(s1.hash(), s2.hash());
961
962 try std.testing.expect(x.hash() != V.initI128(7).hash());
963 }