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