lib/preserves/src/atom.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! A copy of one atom, taken out of a value, records whether its holder owns the bytes behind it.
2 //! An atom is a boolean, a double, an integer, a string, a byte string or a symbol.
3 //!
4 //! A program that keeps atoms apart from the tree they came from has to know, for each one, whether
5 //! freeing its bytes is the program's job.
6 //!
7 //! Atom bytes come from two places: memory that some other owner keeps alive, and memory the holder
8 //! allocated itself. A value tree stores its text as bare slices and records neither case, so one
9 //! free call over the tree is wrong for one of the two. A Lean model of parser results proves that
10 //! when a borrowed symbol and an owned symbol look the same, no single cleanup frees exactly the
11 //! owned bytes of both.
12 //!
13 //! The six atom kinds are the atoms of the [Preserves](https://preserves.dev/) data language, which
14 //! the package keeps along with its compounds and embedded values.
15 //!
16 //! Each copy carries a two-state tag (`Ownership`). The tag says whether the holder owns the copy's
17 //! bytes or borrows them. A byte slice with that tag (`CowBytes`) holds the text of a string, byte
18 //! string or symbol. An integer with that tag (`CowSignedInteger`) holds a number whose digits may
19 //! live on the heap. The union of all six kinds (`Atom`) holds booleans and doubles directly, since
20 //! they own no storage. Freeing a copy frees only what it owns, and promoting a borrowed copy
21 //! copies its bytes into storage its holder owns. Two copies of one atom compare equal whatever
22 //! their ownership tags. `Value.asAtom` returns a borrowed copy of one atom of a value, and `null`
23 //! for any other kind. The codecs and the free calls of the package never read these types, and a
24 //! value never stores them.
25 const std = @import("std");
26 const Allocator = std.mem.Allocator;
27
28 const integer = @import("integer.zig");
29 pub const SignedInteger = integer.SignedInteger;
30
31 /// The six kinds of atom, in the order `Value` ranks them: boolean, double, integer, string, byte
32 /// string and symbol. Code that switches on an atom's kind reads this, from `Value.atomClass` or
33 /// `Atom.class`. `Value.atomClass` returns it for an atom and `null` for any other value. It tags
34 /// the union `Atom`.
35 pub const AtomClass = enum(u8) {
36 boolean,
37 double,
38 signed_integer,
39 string,
40 byte_string,
41 symbol,
42 };
43
44 /// Whether the holder of some bytes owns them, and frees them with its own `deinit`, or borrows
45 /// them from an owner that keeps them alive. Code that holds atom bytes apart from their value
46 /// reads this to decide whether `deinit` frees them.
47 pub const Ownership = enum { borrowed, owned };
48
49 /// A byte slice with a tag that says whether its holder owns the bytes. Code that keeps a string,
50 /// byte string or symbol apart from its value holds it in this type, so its ownership travels with
51 /// it. A new one borrows its bytes unless its builder says otherwise.
52 pub const CowBytes = struct {
53 /// The bytes of the string, byte string or symbol.
54 bytes: []const u8,
55 /// Whether the holder owns `bytes`. It defaults to borrowed, so a struct written by hand never
56 /// frees bytes it did not allocate.
57 ownership: Ownership = .borrowed,
58
59 /// Wraps `bytes` as borrowed. Code that wraps bytes it keeps alive elsewhere calls it. `deinit`
60 /// leaves the bytes alone, so they have to outlive the result.
61 pub fn borrow(bytes: []const u8) CowBytes {
62 return .{ .bytes = bytes, .ownership = .borrowed };
63 }
64
65 /// Wraps `bytes` as owned. Code that wraps bytes it allocated calls it. `deinit` frees them
66 /// with the allocator it is given, so they have to come from that allocator.
67 pub fn own(bytes: []const u8) CowBytes {
68 return .{ .bytes = bytes, .ownership = .owned };
69 }
70
71 /// Frees the bytes with `allocator` when they are owned, and leaves them when they are
72 /// borrowed. Code that holds the bytes calls it when it is done with them. The struct is
73 /// undefined afterward.
74 pub fn deinit(self: *CowBytes, allocator: Allocator) void {
75 if (self.ownership == .owned) allocator.free(self.bytes);
76 self.* = undefined;
77 }
78
79 /// Returns a copy that owns its bytes. Code that must keep the bytes after their owner goes
80 /// calls it. Borrowed bytes are copied into storage from `allocator`. Owned bytes come back as
81 /// the same struct with no copy, so the result and the original share them and only one of the
82 /// two may be freed. The call can fail only with `error.OutOfMemory`.
83 pub fn intoOwned(self: CowBytes, allocator: Allocator) !CowBytes {
84 return switch (self.ownership) {
85 .owned => self,
86 .borrowed => CowBytes.own(try allocator.dupe(u8, self.bytes)),
87 };
88 }
89 };
90
91 /// An integer with a tag that says whether its holder owns the integer's heap digits. Code that
92 /// keeps an integer apart from its value holds it in this type, so the ownership of its digits
93 /// travels with it. A new one borrows unless its builder says otherwise.
94 pub const CowSignedInteger = struct {
95 /// The integer.
96 value: SignedInteger,
97 /// Whether the holder owns the digits of `value`. It defaults to borrowed, so a struct written
98 /// by hand never frees digits it did not allocate.
99 ownership: Ownership = .borrowed,
100
101 /// Wraps `value` as borrowed. Code that wraps an integer whose digits live elsewhere calls it.
102 /// `deinit` leaves its digits alone.
103 pub fn borrow(value: SignedInteger) CowSignedInteger {
104 return .{ .value = value, .ownership = .borrowed };
105 }
106
107 /// Wraps `value` as owned. Code that wraps an integer it built calls it. `deinit` frees its
108 /// digits with the allocator it is given, so they have to come from that allocator.
109 pub fn own(value: SignedInteger) CowSignedInteger {
110 return .{ .value = value, .ownership = .owned };
111 }
112
113 /// Frees the integer's heap digits with `allocator` when they are owned, and leaves them when
114 /// they are borrowed. Code that holds the integer calls it when it is done with it. Only an
115 /// integer too large for 128 bits has heap digits. The struct is undefined afterward.
116 pub fn deinit(self: *CowSignedInteger, allocator: Allocator) void {
117 if (self.ownership == .owned) self.value.deinit(allocator);
118 self.* = undefined;
119 }
120
121 /// Returns a copy that owns its digits. Code that must keep the integer after its owner goes
122 /// calls it. A borrowed integer is copied into storage from `allocator`. An owned integer comes
123 /// back as the same struct with no copy, so the result and the original share its digits and
124 /// only one of the two may be freed.
125 pub fn intoOwned(self: CowSignedInteger, allocator: Allocator) !CowSignedInteger {
126 return switch (self.ownership) {
127 .owned => self,
128 .borrowed => CowSignedInteger.own(try self.value.clone(allocator)),
129 };
130 }
131 };
132
133 /// A copy of one atom, tagged by its kind. Code that takes one atom out of a value holds it in this
134 /// type, as `Value.asAtom` returns it. Booleans and doubles are stored directly. Strings, byte
135 /// strings and symbols are stored as bytes with an ownership tag, and integers as an integer with
136 /// one. `Value.asAtom` builds one that borrows from a value.
137 pub const Atom = union(AtomClass) {
138 /// The boolean.
139 boolean: bool,
140 /// The double.
141 double: f64,
142 /// The integer, with whether its holder owns its digits.
143 signed_integer: CowSignedInteger,
144 /// The string's bytes, with whether its holder owns them.
145 string: CowBytes,
146 /// The byte string's bytes, with whether its holder owns them.
147 byte_string: CowBytes,
148 /// The symbol's name bytes, with whether its holder owns them.
149 symbol: CowBytes,
150
151 /// Returns the atom's kind. Code that switches on an atom's kind calls it.
152 pub fn class(self: Atom) AtomClass {
153 return @as(AtomClass, self);
154 }
155
156 /// Makes a boolean atom from `v`. `Value.asAtom` calls it for a boolean atom.
157 pub fn fromBool(v: bool) Atom {
158 return .{ .boolean = v };
159 }
160
161 /// Makes a double atom from `v`. `Value.asAtom` calls it for a double atom.
162 pub fn fromDouble(v: f64) Atom {
163 return .{ .double = v };
164 }
165
166 /// Makes an integer atom that borrows `v`'s digits. `Value.asAtom` calls it for an integer atom
167 /// over the value's own digits.
168 pub fn fromSignedIntegerBorrowed(v: SignedInteger) Atom {
169 return .{ .signed_integer = CowSignedInteger.borrow(v) };
170 }
171
172 /// Makes an integer atom that owns `v`'s digits, so its `deinit` frees them. Code that hands an
173 /// integer's digits to the atom calls it.
174 pub fn fromSignedIntegerOwned(v: SignedInteger) Atom {
175 return .{ .signed_integer = CowSignedInteger.own(v) };
176 }
177
178 /// Makes a string atom that borrows `bytes`. `Value.asAtom` calls it for a string atom over the
179 /// value's own bytes.
180 pub fn fromStringBorrowed(bytes: []const u8) Atom {
181 return .{ .string = CowBytes.borrow(bytes) };
182 }
183
184 /// Makes a string atom that owns `bytes`, so its `deinit` frees them. Code that hands a
185 /// string's bytes to the atom calls it.
186 pub fn fromStringOwned(bytes: []const u8) Atom {
187 return .{ .string = CowBytes.own(bytes) };
188 }
189
190 /// Makes a byte-string atom that borrows `bytes`. `Value.asAtom` calls it for a byte-string
191 /// atom over the value's own bytes.
192 pub fn fromByteStringBorrowed(bytes: []const u8) Atom {
193 return .{ .byte_string = CowBytes.borrow(bytes) };
194 }
195
196 /// Makes a byte-string atom that owns `bytes`, so its `deinit` frees them. Code that hands a
197 /// byte string's bytes to the atom calls it.
198 pub fn fromByteStringOwned(bytes: []const u8) Atom {
199 return .{ .byte_string = CowBytes.own(bytes) };
200 }
201
202 /// Makes a symbol atom that borrows `bytes`. `Value.asAtom` calls it for a symbol atom over the
203 /// value's own bytes.
204 pub fn fromSymbolBorrowed(bytes: []const u8) Atom {
205 return .{ .symbol = CowBytes.borrow(bytes) };
206 }
207
208 /// Makes a symbol atom that owns `bytes`, so its `deinit` frees them. Code that hands a
209 /// symbol's bytes to the atom calls it.
210 pub fn fromSymbolOwned(bytes: []const u8) Atom {
211 return .{ .symbol = CowBytes.own(bytes) };
212 }
213
214 /// Frees the atom's bytes or digits with `allocator` when it owns them. Code that holds the
215 /// atom calls it when it is done with it. Booleans and doubles need nothing. The atom is
216 /// undefined afterward.
217 pub fn deinit(self: *Atom, allocator: Allocator) void {
218 switch (self.*) {
219 .boolean, .double => {},
220 .signed_integer => |*c| c.deinit(allocator),
221 .string => |*c| c.deinit(allocator),
222 .byte_string => |*c| c.deinit(allocator),
223 .symbol => |*c| c.deinit(allocator),
224 }
225 self.* = undefined;
226 }
227
228 /// Returns a copy of the atom that owns its bytes or digits, copying borrowed ones into storage
229 /// from `allocator`. Code that keeps an atom calls it so the atom outlives the value it came
230 /// from. Parts that are already owned come back with no copy, so the result shares them with
231 /// the original and only one of the two may be freed.
232 pub fn intoOwned(self: Atom, allocator: Allocator) !Atom {
233 return switch (self) {
234 .boolean, .double => self,
235 .signed_integer => |c| .{ .signed_integer = try c.intoOwned(allocator) },
236 .string => |c| .{ .string = try c.intoOwned(allocator) },
237 .byte_string => |c| .{ .byte_string = try c.intoOwned(allocator) },
238 .symbol => |c| .{ .symbol = try c.intoOwned(allocator) },
239 };
240 }
241
242 /// Returns whether two atoms have the same kind and the same contents, whatever their ownership
243 /// tags. Code that compares atoms from different owners calls it, so ownership plays no part.
244 /// Doubles are equal when their bit patterns are equal, so a `NaN` equals a `NaN` with the same
245 /// bits and `0.0` differs from `-0.0`. Integers compare with `SignedInteger.eql`.
246 pub fn eql(a: Atom, b: Atom) bool {
247 if (a.class() != b.class()) return false;
248 return switch (a) {
249 .boolean => |v| v == b.boolean,
250 .double => |v| @as(u64, @bitCast(v)) == @as(u64, @bitCast(b.double)),
251 .signed_integer => |c| c.value.eql(b.signed_integer.value),
252 .string => |c| std.mem.eql(u8, c.bytes, b.string.bytes),
253 .byte_string => |c| std.mem.eql(u8, c.bytes, b.byte_string.bytes),
254 .symbol => |c| std.mem.eql(u8, c.bytes, b.symbol.bytes),
255 };
256 }
257 };
258
259 test "Atom borrowed slice does not free on deinit" {
260 var bytes = [_]u8{ 'h', 'i' };
261 var atom = Atom.fromStringBorrowed(&bytes);
262 atom.deinit(std.testing.allocator);
263 }
264
265 test "Atom owned slice frees on deinit" {
266 const allocator = std.testing.allocator;
267 const buf = try allocator.dupe(u8, "hello");
268 var atom = Atom.fromStringOwned(buf);
269 atom.deinit(allocator);
270 }
271
272 test "Atom intoOwned promotes borrowed payload" {
273 const allocator = std.testing.allocator;
274 const literal = "abc";
275 const borrowed = Atom.fromSymbolBorrowed(literal);
276 var owned = try borrowed.intoOwned(allocator);
277 defer owned.deinit(allocator);
278 try std.testing.expectEqual(Ownership.owned, owned.symbol.ownership);
279 try std.testing.expect(std.mem.eql(u8, owned.symbol.bytes, literal));
280 }
281
282 test "Atom eql compares across ownership tags" {
283 var buf = [_]u8{'x'};
284 const borrowed = Atom.fromStringBorrowed(&buf);
285 const allocator = std.testing.allocator;
286 const owned_bytes = try allocator.dupe(u8, "x");
287 var owned = Atom.fromStringOwned(owned_bytes);
288 defer owned.deinit(allocator);
289 try std.testing.expect(Atom.eql(borrowed, owned));
290 }