lib/preserves/src/ownership.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! Calls that copy a whole value tree and free one, each by the rule that matches how the tree was
2 //! built. A tree can own every byte, own its structure while borrowing its text, or own only its
3 //! outermost storage, and each case needs its own free.
4 //!
5 //! Nothing in a value records which of its bytes it owns, so the caller has to pick the free that
6 //! matches how the tree was built. A Lean model of parser results proves that when a borrowed
7 //! symbol and an owned symbol look the same, no single cleanup frees exactly the owned bytes of
8 //! both. The same model proves that cleanup is exact when every resource in a result is owned.
9 //!
10 //! The package keeps the values of the [Preserves](https://preserves.dev/) data language and
11 //! changes one thing for this file: the caller owns and frees all storage.
12 //!
13 //! `cloneValueDeep` copies a tree into storage that owns every byte, so the copy takes the one full
14 //! free, `Value.deinit`, whatever the original borrowed. `freeValueDeep` frees the structure of a
15 //! tree and leaves its text, for trees that own their structure and borrow their strings and
16 //! symbols. `freeValue` frees one level of storage, the level the root constructors allocate.
17 //!
18 //! - *domain*: the type of the embedded values
19 //! - *pattern form*: one of four value kinds that describe a match
20 const std = @import("std");
21 const Allocator = std.mem.Allocator;
22
23 const value_mod = @import("value.zig");
24 const domain_mod = @import("domain.zig");
25
26 pub const Value = value_mod.Value;
27 pub const NoEmbedded = domain_mod.NoEmbedded;
28
29 /// Copies `val` all the way down into storage from `alloc`: atom bytes, integer digits, bind names,
30 /// compound storage and embedded values. Code that keeps a value past the life of its source calls
31 /// it for a copy that owns every byte, as the text reader and the property tests do. A set or
32 /// dictionary copy keeps the original's storage order. Each embedded value is copied by its type's
33 /// `clone`. For `AnyEmbedded` that calls the payload's copy function, shares a payload that has
34 /// neither a copy nor a free function, and panics on one that has a free function and no copy
35 /// function. `Value.deinit` with `alloc` frees the result. On `error.OutOfMemory` the call frees
36 /// every partial copy and leaves `val` unchanged.
37 pub fn cloneValueDeep(comptime D: type, alloc: Allocator, val: Value(D)) Allocator.Error!Value(D) {
38 domain_mod.assertIsDomain(D);
39 const V = Value(D);
40 return switch (val) {
41 .boolean => |v| V.initBoolean(v),
42 .double => |v| V.initDouble(v),
43 .signed_integer => |si| V.initSignedInteger(try si.clone(alloc)),
44 .string => |s| try V.initString(alloc, s),
45 .byte_string => |s| try V.initByteString(alloc, s),
46 .symbol => |s| try V.initSymbol(alloc, s),
47 .record => |record| blk: {
48 var label = try cloneValueDeep(D, alloc, record.label.*);
49 errdefer label.deinit(alloc);
50
51 const fields = try alloc.alloc(V, record.fields.len);
52 var filled: usize = 0;
53 errdefer {
54 while (filled > 0) {
55 filled -= 1;
56 fields[filled].deinit(alloc);
57 }
58 alloc.free(fields);
59 }
60 while (filled < record.fields.len) : (filled += 1) {
61 fields[filled] = try cloneValueDeep(D, alloc, record.fields[filled]);
62 }
63 break :blk try V.initRecord(alloc, label, fields);
64 },
65 .sequence => |items| blk: {
66 const cloned = try alloc.alloc(V, items.len);
67 var filled: usize = 0;
68 errdefer {
69 while (filled > 0) {
70 filled -= 1;
71 cloned[filled].deinit(alloc);
72 }
73 alloc.free(cloned);
74 }
75 while (filled < items.len) : (filled += 1) {
76 cloned[filled] = try cloneValueDeep(D, alloc, items[filled]);
77 }
78 break :blk V.initSequence(cloned);
79 },
80 .set => |items| blk: {
81 const cloned = try alloc.alloc(V, items.len);
82 var filled: usize = 0;
83 errdefer {
84 while (filled > 0) {
85 filled -= 1;
86 cloned[filled].deinit(alloc);
87 }
88 alloc.free(cloned);
89 }
90 while (filled < items.len) : (filled += 1) {
91 cloned[filled] = try cloneValueDeep(D, alloc, items[filled]);
92 }
93 break :blk V.initSet(cloned);
94 },
95 .dictionary => |entries| blk: {
96 const cloned = try alloc.alloc(V.DictionaryEntry, entries.len);
97 var filled: usize = 0;
98 errdefer {
99 while (filled > 0) {
100 filled -= 1;
101 cloned[filled].key.deinit(alloc);
102 cloned[filled].value.deinit(alloc);
103 }
104 alloc.free(cloned);
105 }
106 while (filled < entries.len) : (filled += 1) {
107 var key = try cloneValueDeep(D, alloc, entries[filled].key);
108 errdefer key.deinit(alloc);
109 cloned[filled].value = try cloneValueDeep(D, alloc, entries[filled].value);
110 cloned[filled].key = key;
111 }
112 break :blk V.initDictionary(cloned);
113 },
114 .embedded => |embedded| V.initEmbedded(try embedded.clone(alloc)),
115 .discard => .{ .discard = {} },
116 .capture => |inner| blk: {
117 const ptr = try alloc.create(V);
118 errdefer alloc.destroy(ptr);
119 ptr.* = try cloneValueDeep(D, alloc, inner.*);
120 break :blk .{ .capture = ptr };
121 },
122 .bind => |binding| blk: {
123 const ptr = try alloc.create(V);
124 errdefer alloc.destroy(ptr);
125 ptr.* = try cloneValueDeep(D, alloc, binding.pattern.*);
126 errdefer ptr.deinit(alloc);
127 break :blk .{
128 .bind = .{
129 .name = try alloc.dupe(u8, binding.name),
130 .pattern = ptr,
131 },
132 };
133 },
134 .rest_pattern => |rest| blk: {
135 const prefix = try alloc.alloc(V, rest.prefix.len);
136 var filled: usize = 0;
137 errdefer {
138 while (filled > 0) {
139 filled -= 1;
140 prefix[filled].deinit(alloc);
141 }
142 alloc.free(prefix);
143 }
144 while (filled < rest.prefix.len) : (filled += 1) {
145 prefix[filled] = try cloneValueDeep(D, alloc, rest.prefix[filled]);
146 }
147
148 const rest_ptr = try alloc.create(V);
149 errdefer alloc.destroy(rest_ptr);
150 rest_ptr.* = try cloneValueDeep(D, alloc, rest.rest.*);
151 break :blk .{ .rest_pattern = .{ .prefix = prefix, .rest = rest_ptr } };
152 },
153 };
154 }
155
156 /// Frees the outer storage of one compound value and nothing below it. Code that built a value with
157 /// the root constructors calls it at the end, as the README's example does. The outer storage is a
158 /// record's label cell and field slice, the slice of a sequence, set or dictionary, the inner cell
159 /// of a capture or bind, and a rest pattern's prefix slice and rest cell. The call matches the root
160 /// constructors, which allocate that outer storage and borrow everything below it. The call frees
161 /// no child value, no atom bytes and no embedded payload, and it does nothing to an atom or an
162 /// embedded value.
163 pub fn freeValue(comptime D: type, alloc: Allocator, val: Value(D)) void {
164 domain_mod.assertIsDomain(D);
165 switch (val) {
166 .record => |r| {
167 alloc.destroy(r.label);
168 alloc.free(r.fields);
169 },
170 .sequence => |s| alloc.free(s),
171 .set => |s| alloc.free(s),
172 .dictionary => |d| alloc.free(d),
173 .capture => |inner| alloc.destroy(inner),
174 .bind => |b| alloc.destroy(b.pattern),
175 .rest_pattern => |rp| {
176 alloc.free(rp.prefix);
177 alloc.destroy(rp.rest);
178 },
179 else => {},
180 }
181 }
182
183 /// Frees a value's compound storage all the way down: records, sequences, sets, dictionaries,
184 /// captures, binds and rest patterns. The pattern conversions and `toText` call it for trees whose
185 /// structure they own and whose text they borrow. The call also frees the digits of every integer
186 /// too large for 128 bits. The call leaves the bytes of strings, byte strings and symbols, the
187 /// names of binds, and embedded payloads. `Value.deinit` frees all of those as well, so it fits
188 /// only a tree whose every byte comes from `alloc`.
189 pub fn freeValueDeep(comptime D: type, alloc: Allocator, val: Value(D)) void {
190 domain_mod.assertIsDomain(D);
191 switch (val) {
192 .signed_integer => |si| {
193 var copy = si;
194 copy.deinit(alloc);
195 },
196 .record => |r| {
197 freeValueDeep(D, alloc, r.label.*);
198 for (r.fields) |f| freeValueDeep(D, alloc, f);
199 alloc.destroy(r.label);
200 alloc.free(r.fields);
201 },
202 .sequence => |s| {
203 for (s) |item| freeValueDeep(D, alloc, item);
204 alloc.free(s);
205 },
206 .set => |s| {
207 for (s) |item| freeValueDeep(D, alloc, item);
208 alloc.free(s);
209 },
210 .dictionary => |d| {
211 for (d) |entry| {
212 freeValueDeep(D, alloc, entry.key);
213 freeValueDeep(D, alloc, entry.value);
214 }
215 alloc.free(d);
216 },
217 .capture => |inner| {
218 freeValueDeep(D, alloc, inner.*);
219 alloc.destroy(inner);
220 },
221 .bind => |b| {
222 freeValueDeep(D, alloc, b.pattern.*);
223 alloc.destroy(b.pattern);
224 },
225 .rest_pattern => |rp| {
226 for (rp.prefix) |item| freeValueDeep(D, alloc, item);
227 alloc.free(rp.prefix);
228 freeValueDeep(D, alloc, rp.rest.*);
229 alloc.destroy(rp.rest);
230 },
231 else => {},
232 }
233 }
234
235 test "freeValue frees outer slice only" {
236 const V = Value(NoEmbedded);
237 const allocator = std.testing.allocator;
238 const fields = try allocator.alloc(V, 2);
239 fields[0] = V.initI128(1);
240 fields[1] = V.initI128(2);
241 const label_ptr = try allocator.create(V);
242 label_ptr.* = V.initBoolean(true);
243 const r: V = .{ .record = .{ .label = label_ptr, .fields = fields } };
244 freeValue(NoEmbedded, allocator, r);
245 }
246
247 test "cloneValueDeep owns copied atom and compound storage" {
248 const V = Value(NoEmbedded);
249 const allocator = std.testing.allocator;
250 const dict_entries = try allocator.alloc(V.DictionaryEntry, 1);
251 errdefer allocator.free(dict_entries);
252 dict_entries[0] = .{ .key = V{ .symbol = "key" }, .value = V{ .byte_string = "bytes" } };
253
254 const fields = try allocator.alloc(V, 2);
255 errdefer allocator.free(fields);
256 fields[0] = V{ .string = "name" };
257 fields[1] = V.initDictionary(dict_entries);
258
259 const original = try V.initRecord(allocator, V{ .symbol = "shape" }, fields);
260 defer {
261 allocator.destroy(original.record.label);
262 allocator.free(original.record.fields);
263 allocator.free(dict_entries);
264 }
265
266 var cloned = try cloneValueDeep(NoEmbedded, allocator, original);
267 defer cloned.deinit(allocator);
268
269 try std.testing.expect(original.eql(cloned));
270 }
271
272 test "cloneValueDeep owns copied pattern form storage" {
273 const V = Value(NoEmbedded);
274 const allocator = std.testing.allocator;
275
276 const name = try allocator.dupe(u8, "slot");
277 defer allocator.free(name);
278
279 const capture_ptr = try allocator.create(V);
280 capture_ptr.* = .{ .discard = {} };
281
282 const bind_ptr = try allocator.create(V);
283 bind_ptr.* = .{ .capture = capture_ptr };
284
285 const prefix = try allocator.alloc(V, 2);
286 prefix[0] = V.initI128(1);
287 prefix[1] = .{ .bind = .{ .name = name, .pattern = bind_ptr } };
288
289 const rest_ptr = try allocator.create(V);
290 rest_ptr.* = V{ .symbol = "tail" };
291
292 const original: V = .{ .rest_pattern = .{ .prefix = prefix, .rest = rest_ptr } };
293 var cloned = try cloneValueDeep(NoEmbedded, allocator, original);
294 defer cloned.deinit(allocator);
295
296 try std.testing.expect(original.eql(cloned));
297 freeValueDeep(NoEmbedded, allocator, original);
298 try std.testing.expectEqualStrings("slot", cloned.rest_pattern.prefix[1].bind.name);
299 }
300
301 test "freeValueDeep frees compound tree but skips string/symbol slices" {
302 const V = Value(NoEmbedded);
303 const allocator = std.testing.allocator;
304 const inner_items = try allocator.alloc(V, 2);
305 inner_items[0] = V{ .string = "borrowed-a" };
306 inner_items[1] = V{ .symbol = "borrowed-b" };
307 const inner_seq = V{ .sequence = inner_items };
308
309 const outer_items = try allocator.alloc(V, 1);
310 outer_items[0] = inner_seq;
311 const label_ptr = try allocator.create(V);
312 label_ptr.* = V{ .symbol = "Label" };
313 const r: V = .{ .record = .{ .label = label_ptr, .fields = outer_items } };
314
315 freeValueDeep(NoEmbedded, allocator, r);
316 }