lib/preserves/src/text/writer.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! Writes values as text, whatever the type of their embedded values. A caller writing a value for
2 //! people to read, or for a program to read back, needs a spelling each text reader accepts. A
3 //! double that is infinite or NaN has no decimal spelling. A symbol can look like a number or hold
4 //! characters that end a bare token.
5 //!
6 //! Special doubles are written as their bits, `#xd"…"`, and every other double carries a `.` or
7 //! exponent so it reads back as a double. A symbol is written bare only when every character is a
8 //! letter, digit or one of `-~!$%^&*?_=+/.|` and it does not look like a number, and the symbol is
9 //! quoted with `'` otherwise. Sets and dictionaries are written in the order they are stored, so
10 //! equal values stored in different orders give different text. The writer refuses discards,
11 //! captures, binds and rest patterns, repeated set elements or dictionary keys, and embedded values
12 //! whose type lacks `encodeText`, as `NoEmbedded` and `AnyEmbedded` both do.
13 const std = @import("std");
14 const Allocator = std.mem.Allocator;
15 const ArrayList = std.ArrayListUnmanaged(u8);
16
17 const preserves = @import("../root.zig");
18
19 const value_mod = preserves.value;
20 const integer_mod = preserves.integer_mod;
21
22 /// The errors `encode` and `writeValue` return. Code that calls `encode` or `writeValue` switches
23 /// on these errors. `EmbeddedNotSupported`: the value holds an embedded value whose type lacks
24 /// `encodeText`. `DuplicateSetElement` and `DuplicateDictionaryKey`: a set with two equal elements,
25 /// or a dictionary with two equal keys. `PatternFormNotEncodable`: the value holds a discard,
26 /// capture, bind or rest pattern. `OutOfMemory`: an allocation failed.
27 pub const EncodeError = Allocator.Error || error{
28 EmbeddedNotSupported,
29 DuplicateSetElement,
30 DuplicateDictionaryKey,
31 PatternFormNotEncodable,
32 };
33
34 /// Returns the text of `value` as new bytes allocated with `allocator`. Code that saves or prints a
35 /// value calls it for new text the caller owns. The caller owns the bytes and frees them with
36 /// `allocator`. On any error the call frees what it wrote.
37 pub fn encode(comptime D: type, allocator: Allocator, value: value_mod.Value(D)) EncodeError![]u8 {
38 var buf: ArrayList = .empty;
39 errdefer buf.deinit(allocator);
40 try writeValue(D, allocator, &buf, value);
41 return buf.toOwnedSlice(allocator);
42 }
43
44 /// Appends the text of `value` to `out`, growing `out` with `allocator`. `toText` calls it for each
45 /// atom, and code that builds one text from more than one value calls it for each. On error, the
46 /// text appended before the failure stays in `out`. Booleans are `#t` and `#f`, and integers are
47 /// decimal at any width. Strings are quoted with `"`, with backslash escapes for quotes,
48 /// backslashes and control characters. Byte strings are written as unpadded base64 in `#[…]`.
49 /// Record fields and sequence and set items are separated by spaces, and dictionary entries by
50 /// `, `. A quoted symbol escapes a `'` as `\'`, which `parse` accepts. A bare symbol can contain
51 /// `_`, so a symbol such as `1_000` is written bare and `parse` reads it as a symbol.
52 pub fn writeValue(
53 comptime D: type,
54 allocator: Allocator,
55 out: *ArrayList,
56 value: value_mod.Value(D),
57 ) EncodeError!void {
58 switch (value) {
59 .boolean => |b| try out.appendSlice(allocator, if (b) "#t" else "#f"),
60 .double => |v| try writeDouble(allocator, out, v),
61 .signed_integer => |si| try writeSignedInteger(allocator, out, si),
62 .string => |s| try writeQuotedString(allocator, out, s),
63 .byte_string => |s| try writeByteString(allocator, out, s),
64 .symbol => |s| try writeSymbol(allocator, out, s),
65 .record => |r| {
66 try out.append(allocator, '<');
67 try writeValue(D, allocator, out, r.label.*);
68 for (r.fields) |f| {
69 try out.append(allocator, ' ');
70 try writeValue(D, allocator, out, f);
71 }
72 try out.append(allocator, '>');
73 },
74 .sequence => |items| {
75 try out.append(allocator, '[');
76 for (items, 0..) |item, i| {
77 if (i > 0) try out.append(allocator, ' ');
78 try writeValue(D, allocator, out, item);
79 }
80 try out.append(allocator, ']');
81 },
82 .set => |items| {
83 if (!value_mod.Value(D).setElementsDistinct(items)) {
84 return error.DuplicateSetElement;
85 }
86 try out.appendSlice(allocator, "#{");
87 for (items, 0..) |item, i| {
88 if (i > 0) try out.append(allocator, ' ');
89 try writeValue(D, allocator, out, item);
90 }
91 try out.append(allocator, '}');
92 },
93 .dictionary => |entries| {
94 if (!value_mod.Value(D).dictionaryKeysDistinct(entries)) {
95 return error.DuplicateDictionaryKey;
96 }
97 try out.append(allocator, '{');
98 for (entries, 0..) |e, i| {
99 if (i > 0) try out.appendSlice(allocator, ", ");
100 try writeValue(D, allocator, out, e.key);
101 try out.appendSlice(allocator, ": ");
102 try writeValue(D, allocator, out, e.value);
103 }
104 try out.append(allocator, '}');
105 },
106 .embedded => |d| {
107 if (!@hasDecl(D, "encodeText")) return error.EmbeddedNotSupported;
108 try out.appendSlice(allocator, "#:");
109 try D.encodeText(d, allocator, out);
110 },
111 .discard, .capture, .bind, .rest_pattern => return error.PatternFormNotEncodable,
112 }
113 }
114
115 fn writeDouble(allocator: Allocator, out: *ArrayList, v: f64) EncodeError!void {
116 if (std.math.isNan(v) or std.math.isInf(v)) {
117 const bits: u64 = @bitCast(v);
118 try out.appendSlice(allocator, "#xd\"");
119 var hex: [16]u8 = undefined;
120 _ = std.fmt.bufPrint(&hex, "{x:0>16}", .{bits}) catch unreachable;
121 try out.appendSlice(allocator, &hex);
122 try out.append(allocator, '"');
123 return;
124 }
125 var tmp: [384]u8 = undefined;
126 const s = std.fmt.bufPrint(&tmp, "{d}", .{v}) catch unreachable;
127 try out.appendSlice(allocator, s);
128 if (std.mem.indexOfScalar(u8, s, '.') == null and
129 std.mem.indexOfAny(u8, s, "eE") == null)
130 {
131 try out.appendSlice(allocator, ".0");
132 }
133 }
134
135 fn writeSignedInteger(
136 allocator: Allocator,
137 out: *ArrayList,
138 si: integer_mod.SignedInteger,
139 ) EncodeError!void {
140 switch (si.repr) {
141 .i128 => |v| {
142 var tmp: [48]u8 = undefined;
143 const s = std.fmt.bufPrint(&tmp, "{d}", .{v}) catch unreachable;
144 try out.appendSlice(allocator, s);
145 },
146 .u128 => |v| {
147 var tmp: [48]u8 = undefined;
148 const s = std.fmt.bufPrint(&tmp, "{d}", .{v}) catch unreachable;
149 try out.appendSlice(allocator, s);
150 },
151 .big => |bytes| try writeBigDecimal(allocator, out, bytes),
152 }
153 }
154
155 fn writeBigDecimal(allocator: Allocator, out: *ArrayList, bytes: []const u8) EncodeError!void {
156 if (bytes.len == 0) {
157 try out.append(allocator, '0');
158 return;
159 }
160 const is_negative = (bytes[0] & 0x80) != 0;
161
162 var mag = try allocator.alloc(u8, bytes.len);
163 defer allocator.free(mag);
164 if (is_negative) {
165 var carry: u16 = 1;
166 var i: usize = bytes.len;
167 while (i > 0) {
168 i -= 1;
169 const inv: u16 = @as(u16, ~bytes[i]) & 0xff;
170 const sum = inv + carry;
171 mag[i] = @intCast(sum & 0xff);
172 carry = sum >> 8;
173 }
174 } else {
175 @memcpy(mag, bytes);
176 }
177
178 var digits: std.ArrayListUnmanaged(u8) = .empty;
179 defer digits.deinit(allocator);
180
181 const remaining = try allocator.dupe(u8, mag);
182 defer allocator.free(remaining);
183
184 while (true) {
185 var all_zero = true;
186 var rem: u16 = 0;
187 for (remaining) |*b| {
188 const cur = (rem << 8) | @as(u16, b.*);
189 const q: u8 = @intCast(cur / 10);
190 rem = cur % 10;
191 b.* = q;
192 if (q != 0) all_zero = false;
193 }
194 try digits.append(allocator, @intCast(rem + '0'));
195 if (all_zero) break;
196 }
197
198 if (is_negative) try out.append(allocator, '-');
199 var j: usize = digits.items.len;
200 while (j > 0) {
201 j -= 1;
202 try out.append(allocator, digits.items[j]);
203 }
204 }
205
206 fn writeQuotedString(allocator: Allocator, out: *ArrayList, s: []const u8) EncodeError!void {
207 try out.append(allocator, '"');
208 for (s) |ch| {
209 switch (ch) {
210 '"' => try out.appendSlice(allocator, "\\\""),
211 '\\' => try out.appendSlice(allocator, "\\\\"),
212 '\n' => try out.appendSlice(allocator, "\\n"),
213 '\r' => try out.appendSlice(allocator, "\\r"),
214 '\t' => try out.appendSlice(allocator, "\\t"),
215 0x08 => try out.appendSlice(allocator, "\\b"),
216 0x0c => try out.appendSlice(allocator, "\\f"),
217 else => {
218 if (ch < 0x20) {
219 try out.appendSlice(allocator, "\\u");
220 var hex: [4]u8 = undefined;
221 _ = std.fmt.bufPrint(&hex, "{x:0>4}", .{ch}) catch unreachable;
222 try out.appendSlice(allocator, &hex);
223 } else {
224 try out.append(allocator, ch);
225 }
226 },
227 }
228 }
229 try out.append(allocator, '"');
230 }
231
232 fn writeByteString(allocator: Allocator, out: *ArrayList, bytes: []const u8) EncodeError!void {
233 try out.append(allocator, '#');
234 try out.append(allocator, '[');
235 const enc = std.base64.standard_no_pad.Encoder;
236 const needed = enc.calcSize(bytes.len);
237 const dst = try allocator.alloc(u8, needed);
238 defer allocator.free(dst);
239 _ = enc.encode(dst, bytes);
240 try out.appendSlice(allocator, dst);
241 try out.append(allocator, ']');
242 }
243
244 fn writeSymbol(allocator: Allocator, out: *ArrayList, s: []const u8) EncodeError!void {
245 if (s.len > 0 and isBareSymbol(s) and !looksLikeNumber(s)) {
246 try out.appendSlice(allocator, s);
247 } else {
248 try out.append(allocator, '\'');
249 for (s) |ch| {
250 switch (ch) {
251 '\'' => try out.appendSlice(allocator, "\\'"),
252 '\\' => try out.appendSlice(allocator, "\\\\"),
253 '\n' => try out.appendSlice(allocator, "\\n"),
254 '\r' => try out.appendSlice(allocator, "\\r"),
255 '\t' => try out.appendSlice(allocator, "\\t"),
256 else => {
257 if (ch < 0x20) {
258 try out.appendSlice(allocator, "\\u");
259 var hex: [4]u8 = undefined;
260 _ = std.fmt.bufPrint(&hex, "{x:0>4}", .{ch}) catch unreachable;
261 try out.appendSlice(allocator, &hex);
262 } else {
263 try out.append(allocator, ch);
264 }
265 },
266 }
267 }
268 try out.append(allocator, '\'');
269 }
270 }
271
272 fn isBareSymbol(s: []const u8) bool {
273 for (s) |c| {
274 if (!isBareSymbolChar(c)) return false;
275 }
276 return true;
277 }
278
279 fn isBareSymbolChar(c: u8) bool {
280 return switch (c) {
281 'a'...'z', 'A'...'Z', '0'...'9' => true,
282 '-', '~', '!', '$', '%', '^', '&', '*', '?', '_', '=', '+', '/', '.', '|' => true,
283 else => false,
284 };
285 }
286
287 fn looksLikeNumber(s: []const u8) bool {
288 if (s.len == 0) return false;
289 var i: usize = 0;
290 if (s[i] == '-' or s[i] == '+') i += 1;
291 if (i >= s.len or !isDigit(s[i])) return false;
292 const int_start = i;
293 while (i < s.len and isDigit(s[i])) i += 1;
294 if (i == int_start) return false;
295 if (i == s.len) return true;
296
297 if (s[i] == '.') {
298 i += 1;
299 const frac_start = i;
300 while (i < s.len and isDigit(s[i])) i += 1;
301 if (i == frac_start) return false;
302 }
303 if (i < s.len and (s[i] == 'e' or s[i] == 'E')) {
304 i += 1;
305 if (i < s.len and (s[i] == '-' or s[i] == '+')) i += 1;
306 const exp_start = i;
307 while (i < s.len and isDigit(s[i])) i += 1;
308 if (i == exp_start) return false;
309 }
310 return i == s.len;
311 }
312
313 fn isDigit(c: u8) bool {
314 return c >= '0' and c <= '9';
315 }
316
317 test "text encode primitives" {
318 const allocator = std.testing.allocator;
319 const NE = preserves.domain.NoEmbedded;
320 const V = value_mod.Value(NE);
321
322 const t = try encode(NE, allocator, V.initBoolean(true));
323 defer allocator.free(t);
324 try std.testing.expectEqualStrings("#t", t);
325
326 const n = try encode(NE, allocator, V.initI128(-42));
327 defer allocator.free(n);
328 try std.testing.expectEqualStrings("-42", n);
329
330 const s = try encode(NE, allocator, V{ .string = "hi" });
331 defer allocator.free(s);
332 try std.testing.expectEqualStrings("\"hi\"", s);
333
334 const sym = try encode(NE, allocator, V{ .symbol = "hello" });
335 defer allocator.free(sym);
336 try std.testing.expectEqualStrings("hello", sym);
337 }
338
339 test "symbol that looks like a number is quoted" {
340 const allocator = std.testing.allocator;
341 const NE = preserves.domain.NoEmbedded;
342 const V = value_mod.Value(NE);
343 const out = try encode(NE, allocator, V{ .symbol = "123" });
344 defer allocator.free(out);
345 try std.testing.expectEqualStrings("'123'", out);
346 }
347
348 test "u128 and big integer decimal" {
349 const allocator = std.testing.allocator;
350 const NE = preserves.domain.NoEmbedded;
351 const V = value_mod.Value(NE);
352 const above: u128 = @as(u128, @intCast(std.math.maxInt(i128))) + 1;
353 const big = V.initU128(above);
354 const out = try encode(NE, allocator, big);
355 defer allocator.free(out);
356 try std.testing.expectEqualStrings("170141183460469231731687303715884105728", out);
357 }
358
359 test "text encode rejects duplicate set elements and dictionary keys" {
360 const allocator = std.testing.allocator;
361 const NE = preserves.domain.NoEmbedded;
362 const V = value_mod.Value(NE);
363 var set_items = [_]V{ V.initI128(1), V.initI128(1) };
364 var entries = [_]V.DictionaryEntry{
365 .{ .key = V.initI128(1), .value = V.initBoolean(true) },
366 .{ .key = V.initI128(1), .value = V.initBoolean(false) },
367 };
368
369 try std.testing.expectError(
370 error.DuplicateSetElement,
371 encode(NE, allocator, V.initSet(&set_items)),
372 );
373 try std.testing.expectError(
374 error.DuplicateDictionaryKey,
375 encode(NE, allocator, V.initDictionary(&entries)),
376 );
377 }