lib/preserves/src/text/parser.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const Allocator = std.mem.Allocator;
3
4 const preserves = @import("../root.zig");
5 const value_mod = preserves.value;
6 const embedded_mod = preserves.embedded_mod;
7 const parse_error_mod = preserves.parse_error;
8 const text_reader_mod = @import("reader.zig");
9 const nesting = @import("nesting.zig");
10
11 const AnyEmbedded = embedded_mod.AnyEmbedded;
12 const Value = value_mod.Value(AnyEmbedded);
13 pub const ParseError = parse_error_mod.ParseError;
14
15 /// Returns the one value `text` holds, allocated with `alloc`. Code reading hand-written text calls
16 /// it for a value with comments allowed, sets and dictionaries sorted, and `#:` embedded values
17 /// read in place. The value owns all its memory, so `text` may be freed at once, and the caller
18 /// frees the value with `deinit`. On any error the call frees everything it allocated. Whitespace
19 /// and commas separate values, and a `#` followed by a space or tab starts a comment that runs to
20 /// the end of the line. An annotation `@a v` is read, checked and dropped, so the call returns `v`.
21 /// Sets and dictionaries are sorted by the package's value order after they are read. `#:v` becomes
22 /// an embedded value that owns `v` and compares, hashes, copies and frees through it. A bare token
23 /// becomes an integer only when `looksLikeInteger` accepts its optional sign and digits. `parse`
24 /// tries `parseFloat` to produce a double only when `looksLikeFloat` accepts the token. If
25 /// `parseFloat` fails, `parse` falls through to a symbol. Strings and symbols are checked as UTF-8,
26 /// the shared escape reader accepts `\'`, and a `\u` escape reads one code unit, so surrogate pairs
27 /// fail. The call returns a `ParseError` naming the kind of bad input, and
28 /// `error.NestingLimitExceeded` past 256 levels. Its repeated-item checks compare each element or
29 /// key with every earlier one, so their cost grows with the square of the count.
30 pub fn parse(alloc: Allocator, text: []const u8) ParseError!Value {
31 var parser = Parser{ .text = text, .pos = 0, .alloc = alloc };
32 var value = try parser.readValue(nesting.root);
33 errdefer value.deinit(alloc);
34 parser.skipWhitespace();
35 if (parser.pos < parser.text.len) return ParseError.TrailingContent;
36 return value;
37 }
38
39 const Parser = struct {
40 text: []const u8,
41 pos: usize,
42 alloc: Allocator,
43
44 fn peek(self: *Parser) ?u8 {
45 return if (self.pos < self.text.len) self.text[self.pos] else null;
46 }
47
48 fn expect(self: *Parser, ch: u8) ParseError!void {
49 if (self.pos >= self.text.len or self.text[self.pos] != ch) return ParseError.UnexpectedChar;
50 self.pos += 1;
51 }
52
53 fn skipWhitespace(self: *Parser) void {
54 while (self.pos < self.text.len) {
55 const ch = self.text[self.pos];
56 if (ch == ' ' or ch == '\t' or ch == '\r' or ch == '\n' or ch == ',') {
57 self.pos += 1;
58 } else if (ch == '#' and self.pos + 1 < self.text.len and
59 (self.text[self.pos + 1] == ' ' or self.text[self.pos + 1] == '\t'))
60 {
61 while (self.pos < self.text.len and self.text[self.pos] != '\n') {
62 self.pos += 1;
63 }
64 } else break;
65 }
66 }
67
68 fn readValue(self: *Parser, level: nesting.Level) ParseError!Value {
69 self.skipWhitespace();
70 const ch = self.peek() orelse return ParseError.UnexpectedEnd;
71 return switch (ch) {
72 '<' => self.readRecord(try nesting.descend(level)),
73 '[' => self.readSequence(try nesting.descend(level)),
74 '{' => self.readDictionary(try nesting.descend(level)),
75 '#' => self.readHash(level),
76 '"' => self.readString(),
77 '\'' => self.readQuotedSymbol(),
78 '@' => blk: {
79 const nested = try nesting.descend(level);
80 self.pos += 1;
81 var annotation = try self.readValue(nested);
82 defer annotation.deinit(self.alloc);
83 break :blk try self.readValue(nested);
84 },
85 else => self.readAtom(),
86 };
87 }
88
89 fn readRecord(self: *Parser, level: nesting.Level) ParseError!Value {
90 try self.expect('<');
91 self.skipWhitespace();
92 var label = try self.readValue(level);
93 errdefer label.deinit(self.alloc);
94 var fields: std.ArrayListUnmanaged(Value) = .empty;
95 errdefer {
96 for (fields.items) |*field| field.deinit(self.alloc);
97 fields.deinit(self.alloc);
98 }
99 while (true) {
100 self.skipWhitespace();
101 const p = self.peek() orelse return ParseError.UnterminatedRecord;
102 if (p == '>') {
103 self.pos += 1;
104 const fs = fields.toOwnedSlice(self.alloc) catch return ParseError.OutOfMemory;
105 errdefer {
106 for (fs) |*field| field.deinit(self.alloc);
107 self.alloc.free(fs);
108 }
109 const label_ptr = self.alloc.create(Value) catch return ParseError.OutOfMemory;
110 label_ptr.* = label;
111 return Value{ .record = .{ .label = label_ptr, .fields = fs } };
112 }
113 var field = try self.readValue(level);
114 errdefer field.deinit(self.alloc);
115 fields.append(self.alloc, field) catch return ParseError.OutOfMemory;
116 }
117 }
118
119 fn readSequence(self: *Parser, level: nesting.Level) ParseError!Value {
120 try self.expect('[');
121 var items: std.ArrayListUnmanaged(Value) = .empty;
122 errdefer {
123 for (items.items) |*item| item.deinit(self.alloc);
124 items.deinit(self.alloc);
125 }
126 while (true) {
127 self.skipWhitespace();
128 const p = self.peek() orelse return ParseError.UnterminatedSequence;
129 if (p == ']') {
130 self.pos += 1;
131 const s = items.toOwnedSlice(self.alloc) catch return ParseError.OutOfMemory;
132 return Value{ .sequence = s };
133 }
134 var item = try self.readValue(level);
135 errdefer item.deinit(self.alloc);
136 items.append(self.alloc, item) catch return ParseError.OutOfMemory;
137 }
138 }
139
140 fn readDictionary(self: *Parser, level: nesting.Level) ParseError!Value {
141 try self.expect('{');
142 var entries: std.ArrayListUnmanaged(Value.DictionaryEntry) = .empty;
143 errdefer {
144 for (entries.items) |*entry| {
145 entry.key.deinit(self.alloc);
146 entry.value.deinit(self.alloc);
147 }
148 entries.deinit(self.alloc);
149 }
150 while (true) {
151 self.skipWhitespace();
152 const p = self.peek() orelse return ParseError.UnterminatedDictionary;
153 if (p == '}') {
154 self.pos += 1;
155 const Cmp = struct {
156 fn lt(_: void, a: Value.DictionaryEntry, b: Value.DictionaryEntry) bool {
157 return a.key.compare(b.key) == .lt;
158 }
159 };
160 std.mem.sort(Value.DictionaryEntry, entries.items, {}, Cmp.lt);
161 const es = entries.toOwnedSlice(self.alloc) catch return ParseError.OutOfMemory;
162 return Value{ .dictionary = es };
163 }
164 var key = try self.readValue(level);
165 errdefer key.deinit(self.alloc);
166 self.skipWhitespace();
167 try self.expect(':');
168 var val = try self.readValue(level);
169 errdefer val.deinit(self.alloc);
170 if (Value.dictionaryContainsKey(entries.items, key)) {
171 return ParseError.DuplicateDictionaryKey;
172 }
173 entries.append(self.alloc, .{ .key = key, .value = val }) catch
174 return ParseError.OutOfMemory;
175 }
176 }
177
178 fn readHash(self: *Parser, level: nesting.Level) ParseError!Value {
179 try self.expect('#');
180 const ch = self.peek() orelse return ParseError.UnexpectedEnd;
181 switch (ch) {
182 't' => {
183 self.pos += 1;
184 return Value.initBoolean(true);
185 },
186 'f' => {
187 self.pos += 1;
188 return Value.initBoolean(false);
189 },
190 '{' => return self.readSet(try nesting.descend(level)),
191 ':' => {
192 self.pos += 1;
193 var inner = try self.readValue(try nesting.descend(level));
194 errdefer inner.deinit(self.alloc);
195 const ptr = self.alloc.create(Value) catch return ParseError.OutOfMemory;
196 ptr.* = inner;
197 return Value{ .embedded = .{
198 .value = @ptrCast(ptr),
199 .semantic_ops = embedded_mod.parsedEmbeddedOps(Value),
200 .deinit_fn = embedded_mod.parsedEmbeddedDeinit(Value),
201 .clone_fn = embedded_mod.parsedEmbeddedClone(Value),
202 } };
203 },
204 '"' => return self.readLiteralByteString(),
205 'x' => {
206 self.pos += 1;
207 const ch2 = self.peek() orelse return ParseError.UnexpectedEnd;
208 if (ch2 == '"') return self.readHexByteString();
209 if (ch2 == 'd') return self.readHexDouble();
210 return ParseError.UnknownHashForm;
211 },
212 '[' => return self.readBase64ByteString(),
213 else => return ParseError.UnknownHashForm,
214 }
215 }
216
217 fn readSet(self: *Parser, level: nesting.Level) ParseError!Value {
218 try self.expect('{');
219 var items: std.ArrayListUnmanaged(Value) = .empty;
220 errdefer {
221 for (items.items) |*item| item.deinit(self.alloc);
222 items.deinit(self.alloc);
223 }
224 while (true) {
225 self.skipWhitespace();
226 const p = self.peek() orelse return ParseError.UnterminatedSet;
227 if (p == '}') {
228 self.pos += 1;
229 const Cmp = struct {
230 fn lt(_: void, a: Value, b: Value) bool {
231 return a.compare(b) == .lt;
232 }
233 };
234 std.mem.sort(Value, items.items, {}, Cmp.lt);
235 const s = items.toOwnedSlice(self.alloc) catch return ParseError.OutOfMemory;
236 return Value{ .set = s };
237 }
238 var item = try self.readValue(level);
239 errdefer item.deinit(self.alloc);
240 if (Value.setContainsElement(items.items, item)) {
241 return ParseError.DuplicateSetElement;
242 }
243 items.append(self.alloc, item) catch return ParseError.OutOfMemory;
244 }
245 }
246
247 fn readString(self: *Parser) ParseError!Value {
248 try self.expect('"');
249 var chars: std.ArrayListUnmanaged(u8) = .empty;
250 errdefer chars.deinit(self.alloc);
251 while (true) {
252 if (self.pos >= self.text.len) return ParseError.UnterminatedString;
253 const ch = self.text[self.pos];
254 self.pos += 1;
255 if (ch == '"') {
256 if (!std.unicode.utf8ValidateSlice(chars.items)) return ParseError.InvalidUtf8;
257 const s = chars.toOwnedSlice(self.alloc) catch return ParseError.OutOfMemory;
258 return Value{ .string = s };
259 }
260 if (ch == '\\') {
261 var utf8_buf: [4]u8 = undefined;
262 const n = try self.readStringEscapeUtf8(&utf8_buf);
263 chars.appendSlice(self.alloc, utf8_buf[0..n]) catch return ParseError.OutOfMemory;
264 } else {
265 chars.append(self.alloc, ch) catch return ParseError.OutOfMemory;
266 }
267 }
268 }
269
270 fn readStringEscapeUtf8(self: *Parser, out_buf: []u8) ParseError!u8 {
271 if (self.pos >= self.text.len) return ParseError.UnterminatedEscape;
272 const ch = self.text[self.pos];
273 self.pos += 1;
274 switch (ch) {
275 '"' => {
276 out_buf[0] = '"';
277 return 1;
278 },
279 '\'' => {
280 out_buf[0] = '\'';
281 return 1;
282 },
283 '\\' => {
284 out_buf[0] = '\\';
285 return 1;
286 },
287 '/' => {
288 out_buf[0] = '/';
289 return 1;
290 },
291 'n' => {
292 out_buf[0] = '\n';
293 return 1;
294 },
295 'r' => {
296 out_buf[0] = '\r';
297 return 1;
298 },
299 't' => {
300 out_buf[0] = '\t';
301 return 1;
302 },
303 'b' => {
304 out_buf[0] = 0x08;
305 return 1;
306 },
307 'f' => {
308 out_buf[0] = 0x0C;
309 return 1;
310 },
311 'u' => {
312 if (self.pos + 4 > self.text.len) return ParseError.InvalidUnicodeEscape;
313 const hex = self.text[self.pos .. self.pos + 4];
314 self.pos += 4;
315 const codepoint = std.fmt.parseInt(u21, hex, 16) catch return ParseError.InvalidUnicodeEscape;
316 const len = std.unicode.utf8Encode(codepoint, out_buf[0..4]) catch return ParseError.InvalidUnicodeEscape;
317 return @intCast(len);
318 },
319 else => return ParseError.UnknownEscape,
320 }
321 }
322
323 fn readQuotedSymbol(self: *Parser) ParseError!Value {
324 try self.expect('\'');
325 var chars: std.ArrayListUnmanaged(u8) = .empty;
326 errdefer chars.deinit(self.alloc);
327 while (true) {
328 if (self.pos >= self.text.len) return ParseError.UnterminatedString;
329 const ch = self.text[self.pos];
330 self.pos += 1;
331 if (ch == '\'') {
332 if (!std.unicode.utf8ValidateSlice(chars.items)) return ParseError.InvalidUtf8;
333 const owned = chars.toOwnedSlice(self.alloc) catch return ParseError.OutOfMemory;
334 return Value{ .symbol = owned };
335 }
336 if (ch == '\\') {
337 var utf8_buf: [4]u8 = undefined;
338 const n = try self.readStringEscapeUtf8(&utf8_buf);
339 chars.appendSlice(self.alloc, utf8_buf[0..n]) catch return ParseError.OutOfMemory;
340 } else {
341 chars.append(self.alloc, ch) catch return ParseError.OutOfMemory;
342 }
343 }
344 }
345
346 fn readLiteralByteString(self: *Parser) ParseError!Value {
347 try self.expect('"');
348 var octets: std.ArrayListUnmanaged(u8) = .empty;
349 errdefer octets.deinit(self.alloc);
350 while (true) {
351 if (self.pos >= self.text.len) return ParseError.UnterminatedByteString;
352 const ch = self.text[self.pos];
353 self.pos += 1;
354 if (ch == '"') {
355 const s = octets.toOwnedSlice(self.alloc) catch return ParseError.OutOfMemory;
356 return Value{ .byte_string = s };
357 }
358 if (ch == '\\') {
359 const b = try self.readByteEscape();
360 octets.append(self.alloc, b) catch return ParseError.OutOfMemory;
361 } else {
362 octets.append(self.alloc, ch) catch return ParseError.OutOfMemory;
363 }
364 }
365 }
366
367 fn readByteEscape(self: *Parser) ParseError!u8 {
368 if (self.pos >= self.text.len) return ParseError.UnterminatedEscape;
369 const ch = self.text[self.pos];
370 self.pos += 1;
371 return switch (ch) {
372 'x' => blk: {
373 if (self.pos + 2 > self.text.len) return ParseError.InvalidHexEscape;
374 const hex = self.text[self.pos .. self.pos + 2];
375 self.pos += 2;
376 break :blk std.fmt.parseInt(u8, hex, 16) catch return ParseError.InvalidHexEscape;
377 },
378 '\\' => 0x5C,
379 '"' => 0x22,
380 'n' => 0x0A,
381 'r' => 0x0D,
382 't' => 0x09,
383 else => ParseError.UnknownEscape,
384 };
385 }
386
387 fn readHexByteString(self: *Parser) ParseError!Value {
388 try self.expect('"');
389 var hex_chars: std.ArrayListUnmanaged(u8) = .empty;
390 defer hex_chars.deinit(self.alloc);
391 while (true) {
392 if (self.pos >= self.text.len) return ParseError.UnterminatedByteString;
393 const ch = self.text[self.pos];
394 self.pos += 1;
395 if (ch == '"') {
396 const hex = hex_chars.items;
397 if (hex.len % 2 != 0) return ParseError.InvalidHexEscape;
398 const byte_count = hex.len / 2;
399 const result = self.alloc.alloc(u8, byte_count) catch return ParseError.OutOfMemory;
400 for (0..byte_count) |i| {
401 result[i] = std.fmt.parseInt(u8, hex[i * 2 .. i * 2 + 2], 16) catch {
402 self.alloc.free(result);
403 return ParseError.InvalidHexEscape;
404 };
405 }
406 return Value{ .byte_string = result };
407 }
408 if (ch != ' ' and ch != '\t' and ch != '\r' and ch != '\n') {
409 hex_chars.append(self.alloc, ch) catch return ParseError.OutOfMemory;
410 }
411 }
412 }
413
414 fn readHexDouble(self: *Parser) ParseError!Value {
415 try self.expect('d');
416 try self.expect('"');
417 var hex_chars: std.ArrayListUnmanaged(u8) = .empty;
418 defer hex_chars.deinit(self.alloc);
419 while (true) {
420 if (self.pos >= self.text.len) return ParseError.UnterminatedHexDouble;
421 const ch = self.text[self.pos];
422 self.pos += 1;
423 if (ch == '"') break;
424 if (ch != ' ' and ch != '\t' and ch != '\r' and ch != '\n') {
425 hex_chars.append(self.alloc, ch) catch return ParseError.OutOfMemory;
426 }
427 }
428 const hex = hex_chars.items;
429 if (hex.len != 16) return ParseError.InvalidHexDouble;
430 var bytes: [8]u8 = undefined;
431 for (0..8) |i| {
432 bytes[i] = std.fmt.parseInt(u8, hex[i * 2 .. i * 2 + 2], 16) catch return ParseError.InvalidHexDouble;
433 }
434 const bits = std.mem.readInt(u64, &bytes, .big);
435 return Value.initDouble(@bitCast(bits));
436 }
437
438 fn readBase64ByteString(self: *Parser) ParseError!Value {
439 try self.expect('[');
440 var chars: std.ArrayListUnmanaged(u8) = .empty;
441 defer chars.deinit(self.alloc);
442 while (true) {
443 if (self.pos >= self.text.len) return ParseError.UnterminatedByteString;
444 const ch = self.text[self.pos];
445 self.pos += 1;
446 if (ch == ']') {
447 const encoded = chars.items;
448 const decoder = std.base64.standard_no_pad.Decoder;
449 const decoded_len = decoder.calcSizeForSlice(encoded) catch
450 return ParseError.InvalidHexEscape;
451 const result = self.alloc.alloc(u8, decoded_len) catch return ParseError.OutOfMemory;
452 decoder.decode(result, encoded) catch {
453 self.alloc.free(result);
454 return ParseError.InvalidHexEscape;
455 };
456 return Value{ .byte_string = result };
457 }
458 if (ch == ' ' or ch == '\t' or ch == '\r' or ch == '\n' or ch == '=') continue;
459 const normalized = if (ch == '-')
460 '+'
461 else if (ch == '_')
462 '/'
463 else
464 ch;
465 chars.append(self.alloc, normalized) catch return ParseError.OutOfMemory;
466 }
467 }
468
469 fn readAtom(self: *Parser) ParseError!Value {
470 const start = self.pos;
471 while (self.pos < self.text.len) {
472 const ch = self.text[self.pos];
473 if (isAtomDelimiter(ch)) break;
474 self.pos += 1;
475 }
476 if (self.pos == start) return ParseError.UnexpectedChar;
477 const token = self.text[start..self.pos];
478 if (text_reader_mod.looksLikeInteger(token)) {
479 const si = text_reader_mod.parseDecimalIntoSignedInteger(self.alloc, token) catch |err| switch (err) {
480 error.OutOfMemory => return ParseError.OutOfMemory,
481 else => unreachable,
482 };
483 return Value{ .signed_integer = si };
484 }
485 if (text_reader_mod.looksLikeFloat(token)) {
486 if (std.fmt.parseFloat(f64, token)) |v| {
487 return Value.initDouble(v);
488 } else |_| {}
489 }
490 if (!std.unicode.utf8ValidateSlice(token)) return ParseError.InvalidUtf8;
491 return Value.initSymbol(self.alloc, token) catch return ParseError.OutOfMemory;
492 }
493 };
494
495 fn isAtomDelimiter(ch: u8) bool {
496 return switch (ch) {
497 ' ', '\t', '\r', '\n', ',', '<', '>', '[', ']', '{', '}', '(', ')', '#', ':', '"', '\'', '@', ';' => true,
498 else => false,
499 };
500 }
501
502 fn expectDuplicateWithAllocator(
503 allocator: Allocator,
504 text: []const u8,
505 expected: ParseError,
506 ) !void {
507 if (parse(allocator, text)) |parsed| {
508 var value = parsed;
509 value.deinit(allocator);
510 return error.ExpectedDuplicate;
511 } else |err| {
512 if (err == error.OutOfMemory) return err;
513 if (err == expected) return;
514 return err;
515 }
516 }
517
518 fn checkDuplicateAllocationFailures(allocator: Allocator) !void {
519 try expectDuplicateWithAllocator(
520 allocator,
521 "#{#:[\"owned\" 'quoted'] #:[\"owned\" 'quoted']}",
522 ParseError.DuplicateSetElement,
523 );
524 try expectDuplicateWithAllocator(
525 allocator,
526 "{\"key\": #:<\"label\" 'first'>, \"key\": #:<\"label\" 'second'>}",
527 ParseError.DuplicateDictionaryKey,
528 );
529 try expectDuplicateWithAllocator(
530 allocator,
531 "#{'quoted' 'quoted'}",
532 ParseError.DuplicateSetElement,
533 );
534 }
535
536 test "parse duplicate errors release every allocation failure path" {
537 try std.testing.checkAllAllocationFailures(
538 std.testing.allocator,
539 checkDuplicateAllocationFailures,
540 .{},
541 );
542 }
543
544 fn checkOwnedParseAllocationFailures(allocator: Allocator) !void {
545 var value = try parse(allocator, "<bare 'quoted symbol' #:[nested bare]>");
546 defer value.deinit(allocator);
547
548 try std.testing.expect(value == .record);
549 try std.testing.expectEqualStrings("bare", value.record.label.symbol);
550 try std.testing.expect(value.record.fields[1] == .embedded);
551 }
552
553 test "owned parse releases every allocation failure path" {
554 try std.testing.checkAllAllocationFailures(
555 std.testing.allocator,
556 checkOwnedParseAllocationFailures,
557 .{},
558 );
559 }
560
561 test "parse trailing content releases discarded annotation and embedded values" {
562 const allocator = std.testing.allocator;
563
564 try std.testing.expectError(
565 ParseError.TrailingContent,
566 parse(allocator, "@[\"annotation\"] #:[\"owned\"] trailing"),
567 );
568 }