// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie // SPDX-License-Identifier: MIT //! Turns source into a tree, resolving every name as it goes. //! //! Recursive descent, one function per level of precedence, which follows //! Zig's own: from loosest to tightest, `or`, `and`, the comparisons, //! `orelse`, `+ - ++`, `* / %`, then the prefix operators. As in Zig an `if` //! is a primary expression whose branches extend as far right as they can, //! so `1 + if (a) 2 else 3 * 4` is `1 + (if (a) 2 else (3 * 4))`. //! //! Every name is looked up when it is parsed. A `let` is only in scope after //! its own `;`, which is the whole of why a program cannot recurse: nothing //! can refer to itself, or to anything defined after it. //! //! `@include("path")` is done here too, not when evaluating: the host reads //! the file, it is parsed where it is named, and its value becomes a slot of //! its own, as if it were a `let` with no name. Files are named by `file:` //! URIs, and the path in an `@include` is a URI reference resolved against //! the URI of the file it is written in. Each file is parsed once //! however often it is included, and a file that includes itself, however //! indirectly, is an error, so includes cannot recurse either. const std = @import("std"); const Allocator = std.mem.Allocator; const ast = @import("ast.zig"); const Node = ast.Node; const Builtin = ast.Builtin; const Diagnostic = @import("Diagnostic.zig"); const Tokenizer = @import("Tokenizer.zig"); const Token = Tokenizer.Token; const Tag = Tokenizer.Tag; const Function = @import("eval.zig").Function; const Uri = @import("uri").Uri; const Parser = @This(); pub const Error = error{ OutOfMemory, Syntax, /// A file named by `@include` could not be read. The diagnostic names /// the file, and the error the host returned. Include, /// The program's filename is not a `file:` URI naming a file on this /// machine. The diagnostic says why. InvalidFilename, }; /// How a host reads the files a program names with `@include`. pub const Include = struct { /// What the host wants handed back to it, as `read`'s `context`. context: ?*anyopaque = null, /// Return the contents of the file named by `file_uri`, or an error. /// /// `file_uri` is always a `file:` URI naming a file on this machine, in /// one spelling: `file:///path`, with an empty host and no query or /// fragment, and `.` and `..` resolved. It is what the program wrote, /// resolved against the URI of the file that includes it. Anything /// further, such as refusing a path outside some directory, is for the /// host to decide. /// /// What it returns must live as long as the program, which is so of /// anything allocated from `arena`: that belongs to the program, and is /// freed with it. read: *const fn (context: ?*anyopaque, arena: Allocator, file_uri: []const u8) anyerror![]const u8, }; pub const Config = struct { /// The `file:` URI of the file the source was read from, for /// diagnostics and for resolving the files it includes against. name: ?[]const u8 = null, functions: []const Function = &.{}, /// Null when the host does not support `@include`. include: ?Include = null, max_depth: u32 = 64, max_includes: u32 = 256, }; /// A parsed program. pub const Tree = struct { /// The program's file and every file it includes, in order of `base`. sources: []const Diagnostic.Source, root: *const Node, /// One per `let` and per `if` capture, in the order they were defined. /// A `let` has the expression it is bound to; a capture has null, and is /// filled in when its `if` is evaluated. slots: []const ?*const Node, }; const Name = struct { name: []const u8, slot: u32 }; /// Names that mean something already and cannot be bound by `let` or `|x|`. const reserved = std.StaticStringMap(void).initComptime(.{ .{"ctx"}, .{"inf"}, .{"nan"}, }); arena: Allocator, source: []const u8, tok: Tokenizer, cur: Token, diag: *Diagnostic, depth: u32 = 0, max_depth: u32, scope: std.ArrayList(Name) = .empty, slots: std.ArrayList(?*const Node) = .empty, functions: []const Function, /// The name of the file being parsed, which `source` holds: the text of /// `uri`. name: ?[]const u8 = null, uri: ?Uri = null, /// Where `source` starts among the offsets of all of the program's files. /// The tokenizer works in offsets into `source`, and the tree in offsets /// into the whole program, so every position put into a node has this added. base: u32 = 0, sources: std.ArrayList(Diagnostic.Source) = .empty, include: ?Include, max_includes: u32, /// Every file included so far, and the slot that holds its value: null /// while the file is still being parsed, which is how a cycle is noticed. files: std.StringHashMapUnmanaged(?u32) = .empty, /// Parse `source`. Everything allocated, the tree included, belongs to /// `arena`, and the tree points into `source`, which must outlive it. pub fn parse(arena: Allocator, source: []const u8, config: Config, diag: *Diagnostic) Error!Tree { var p: Parser = .{ .arena = arena, .source = source, .tok = .init(source), .cur = undefined, .diag = diag, .max_depth = config.max_depth, .functions = config.functions, .include = config.include, .max_includes = config.max_includes, }; if (config.name) |name| { const u = Uri.parse(arena, name) catch |err| switch (err) { error.OutOfMemory => return error.OutOfMemory, else => { diag.set(.{}, "the filename '{s}' is not a URI", .{name}); return error.InvalidFilename; }, }; p.uri = localFile(arena, u) catch |err| switch (err) { error.OutOfMemory => return error.OutOfMemory, else => |e| { diag.set(.{}, "the filename '{s}' {s}", .{ name, notLocal(e) }); return error.InvalidFilename; }, }; p.name = try p.uri.?.toText(arena, .{}); try p.files.put(arena, p.name.?, null); } if (source.len >= std.math.maxInt(u32)) { diag.setIn(p.name, .{}, "program too large", .{}); return error.Syntax; } try p.sources.append(arena, .{ .name = p.name, .text = source, .base = 0 }); const root = try p.parseFile(); return .{ .sources = p.sources.items, .root = root, .slots = p.slots.items }; } /// `let`s and then an expression: the whole of a file. fn parseFile(self: *Parser) Error!*const Node { try self.advance(); while (self.cur.tag == .keyword_let) try self.parseLet(); const root = try self.parseExpr(); if (self.cur.tag != .eof) return self.unexpected("an operator or the end of the program"); return root; } // -- tokens ------------------------------------------------------------------- fn fail(self: *Parser, pos: u32, comptime fmt: []const u8, args: anytype) error{Syntax} { self.diag.setIn(self.name, .of(self.source, pos), fmt, args); return error.Syntax; } fn unexpected(self: *Parser, comptime wanted: []const u8) error{Syntax} { return self.fail(self.cur.start, "expected " ++ wanted ++ ", found {s}", .{self.cur.tag.describe()}); } fn advance(self: *Parser) error{Syntax}!void { self.cur = self.tok.next(); if (self.cur.tag != .invalid) return; const c = self.source[self.cur.start]; return switch (c) { '"' => self.fail(self.cur.start, "unterminated string", .{}), '\'' => self.fail(self.cur.start, "unterminated character literal", .{}), '@' => self.fail(self.cur.start, "expected a builtin name or a quoted identifier after '@'", .{}), else => if (std.ascii.isPrint(c)) self.fail(self.cur.start, "unexpected character '{c}'", .{c}) else self.fail(self.cur.start, "unexpected byte 0x{x:0>2}", .{c}), }; } fn expect(self: *Parser, tag: Tag) Error!Token { if (self.cur.tag != tag) { return self.fail(self.cur.start, "expected {s}, found {s}", .{ tag.describe(), self.cur.tag.describe() }); } const t = self.cur; try self.advance(); return t; } fn text(self: *const Parser, t: Token) []const u8 { return self.source[t.start..t.end]; } fn node(self: *Parser, pos: u32, data: ast.Data) Error!*const Node { const n = try self.arena.create(Node); n.* = .{ .pos = self.base + pos, .data = data }; return n; } fn enter(self: *Parser) error{Syntax}!void { self.depth += 1; if (self.depth > self.max_depth) return self.fail(self.cur.start, "expression nested too deeply", .{}); } fn leave(self: *Parser) void { self.depth -= 1; } // -- names -------------------------------------------------------------------- /// An identifier token's name: as written, or decoded from `@"..."`. fn identName(self: *Parser, t: Token) Error![]const u8 { return switch (t.tag) { .identifier => self.text(t), .quoted_identifier => self.decodeString(t.start + 2, t.end - 1), else => self.fail(t.start, "expected an identifier, found {s}", .{t.tag.describe()}), }; } fn expectName(self: *Parser) Error!struct { []const u8, u32 } { const t = self.cur; const name = try self.identName(t); try self.advance(); return .{ name, t.start }; } /// Make `name` a new slot. Zig does not allow shadowing, and neither does /// this: a name that is already bound is an error, not a new binding. fn bind(self: *Parser, name: []const u8, pos: u32, value: ?*const Node) Error!u32 { if (reserved.has(name)) return self.fail(pos, "'{s}' is reserved and cannot be redefined", .{name}); for (self.scope.items) |n| { if (std.mem.eql(u8, n.name, name)) return self.fail(pos, "'{s}' is already defined", .{name}); } const slot: u32 = @intCast(self.slots.items.len); try self.slots.append(self.arena, value); try self.scope.append(self.arena, .{ .name = name, .slot = slot }); return slot; } fn resolve(self: *Parser, name: []const u8, pos: u32) Error!*const Node { if (std.mem.eql(u8, name, "ctx")) return self.node(pos, .ctx); if (std.mem.eql(u8, name, "inf")) return self.node(pos, .{ .float = std.math.inf(f64) }); if (std.mem.eql(u8, name, "nan")) return self.node(pos, .{ .float = std.math.nan(f64) }); var i = self.scope.items.len; while (i > 0) { i -= 1; const n = self.scope.items[i]; if (std.mem.eql(u8, n.name, name)) return self.node(pos, .{ .slot = n.slot }); } return self.fail(pos, "unknown name '{s}'", .{name}); } // -- statements --------------------------------------------------------------- fn parseLet(self: *Parser) Error!void { try self.advance(); const name, const pos = try self.expectName(); _ = try self.expect(.equal); const value = try self.parseExpr(); _ = try self.expect(.semicolon); _ = try self.bind(name, pos, value); } // -- expressions -------------------------------------------------------------- fn parseExpr(self: *Parser) Error!*const Node { try self.enter(); defer self.leave(); return self.parseOr(); } fn binary(self: *Parser, op: ast.BinaryOp, pos: u32, lhs: *const Node, rhs: *const Node) Error!*const Node { return self.node(pos, .{ .binary = .{ .op = op, .lhs = lhs, .rhs = rhs } }); } fn parseOr(self: *Parser) Error!*const Node { var lhs = try self.parseAnd(); while (self.cur.tag == .keyword_or) { const pos = self.cur.start; try self.advance(); lhs = try self.binary(.@"or", pos, lhs, try self.parseAnd()); } return lhs; } fn parseAnd(self: *Parser) Error!*const Node { var lhs = try self.parseCompare(); while (self.cur.tag == .keyword_and) { const pos = self.cur.start; try self.advance(); lhs = try self.binary(.@"and", pos, lhs, try self.parseCompare()); } return lhs; } fn compareOp(tag: Tag) ?ast.BinaryOp { return switch (tag) { .equal_equal => .eq, .bang_equal => .ne, .angle_bracket_left => .lt, .angle_bracket_left_equal => .le, .angle_bracket_right => .gt, .angle_bracket_right_equal => .ge, else => null, }; } /// Comparisons do not chain, as in Zig: `a < b < c` is an error rather than /// a comparison of a bool with `c`. fn parseCompare(self: *Parser) Error!*const Node { const lhs = try self.parseOrelse(); const op = compareOp(self.cur.tag) orelse return lhs; const pos = self.cur.start; try self.advance(); const result = try self.binary(op, pos, lhs, try self.parseOrelse()); if (compareOp(self.cur.tag) != null) return self.fail(self.cur.start, "comparisons cannot be chained", .{}); return result; } fn parseOrelse(self: *Parser) Error!*const Node { var lhs = try self.parseAdditive(); while (self.cur.tag == .keyword_orelse) { const pos = self.cur.start; try self.advance(); lhs = try self.binary(.@"orelse", pos, lhs, try self.parseAdditive()); } return lhs; } fn parseAdditive(self: *Parser) Error!*const Node { var lhs = try self.parseMultiplicative(); while (true) { const op: ast.BinaryOp = switch (self.cur.tag) { .plus => .add, .minus => .sub, .plus_plus => .concat, else => return lhs, }; const pos = self.cur.start; try self.advance(); lhs = try self.binary(op, pos, lhs, try self.parseMultiplicative()); } } fn parseMultiplicative(self: *Parser) Error!*const Node { var lhs = try self.parseUnary(); while (true) { const op: ast.BinaryOp = switch (self.cur.tag) { .asterisk => .mul, .slash => .div, .percent => .rem, else => return lhs, }; const pos = self.cur.start; try self.advance(); lhs = try self.binary(op, pos, lhs, try self.parseUnary()); } } fn parseUnary(self: *Parser) Error!*const Node { const op: ast.UnaryOp = switch (self.cur.tag) { .bang => .not, .minus => .negate, else => return self.parsePostfix(), }; try self.enter(); defer self.leave(); const pos = self.cur.start; try self.advance(); // A negative literal is read as one, so that the most negative `i64`, // whose magnitude does not fit in one, can be written. if (op == .negate and self.cur.tag == .number) { const t = self.cur; try self.advance(); return self.parsePostfixOf(try self.number(t, true, pos)); } return self.node(pos, .{ .unary = .{ .op = op, .operand = try self.parseUnary() } }); } fn parsePostfix(self: *Parser) Error!*const Node { return self.parsePostfixOf(try self.parsePrimary()); } fn parsePostfixOf(self: *Parser, primary: *const Node) Error!*const Node { var n = primary; while (true) { const pos = self.cur.start; switch (self.cur.tag) { .period => { try self.advance(); const name, _ = try self.expectName(); n = try self.node(pos, .{ .field = .{ .object = n, .name = name } }); }, .period_question => { try self.advance(); n = try self.node(pos, .{ .unwrap = n }); }, .l_bracket => { try self.advance(); const index = try self.parseExpr(); _ = try self.expect(.r_bracket); n = try self.node(pos, .{ .index = .{ .object = n, .index = index } }); }, else => return n, } } } fn parsePrimary(self: *Parser) Error!*const Node { const t = self.cur; switch (t.tag) { .number => { try self.advance(); return self.number(t, false, t.start); }, .char_literal => { try self.advance(); return self.node(t.start, .{ .int = try self.charLiteral(t) }); }, .string => { const n = try self.stringLiteral(t); try self.advance(); return n; }, .multiline_string_line => return self.multilineString(), .keyword_true, .keyword_false => { try self.advance(); return self.node(t.start, .{ .bool = t.tag == .keyword_true }); }, .keyword_null => { try self.advance(); return self.node(t.start, .null); }, .identifier, .quoted_identifier => { const name, const pos = try self.expectName(); return self.resolve(name, pos); }, .builtin => return self.parseCall(), .period => { try self.advance(); const name, _ = try self.expectName(); return self.node(t.start, .{ .enum_literal = name }); }, .period_brace => return self.parseLiteral(), .l_paren => { try self.advance(); const n = try self.parseExpr(); _ = try self.expect(.r_paren); return n; }, .keyword_if => return self.parseIf(false), .keyword_switch => return self.parseSwitch(), else => return self.unexpected("an expression"), } } /// `if (cond) a else b`, or `if (optional) |x| a else b`. `allow_no_else` is /// for a field's value and a list's item, where a missing `else` means "leave /// it out"; it carries into an `else if` chain and into nested branches. fn parseIf(self: *Parser, allow_no_else: bool) Error!*const Node { try self.enter(); defer self.leave(); const pos = self.cur.start; try self.advance(); _ = try self.expect(.l_paren); const cond = try self.parseExpr(); _ = try self.expect(.r_paren); var capture: ?u32 = null; if (self.cur.tag == .pipe) { try self.advance(); const name, const name_pos = try self.expectName(); _ = try self.expect(.pipe); capture = try self.bind(name, name_pos, null); } const then = try self.parseBranch(allow_no_else); // The capture is in scope for the `then` branch only. if (capture != null) _ = self.scope.pop(); var otherwise: ?*const Node = null; if (self.cur.tag == .keyword_else) { try self.advance(); otherwise = try self.parseBranch(allow_no_else); } else if (!allow_no_else) { if (self.cur.tag == .eof or self.cur.tag == .comma or self.cur.tag == .r_brace or self.cur.tag == .semicolon or self.cur.tag == .r_paren) { return self.fail(pos, "an 'if' without 'else' can only be a struct field's value or a list item", .{}); } return self.unexpected("'else'"); } return self.node(pos, .{ .@"if" = .{ .cond = cond, .capture = capture, .then = then, .@"else" = otherwise } }); } /// `switch (subject) { cases => value, ..., else => value }`, where a prong's /// cases are values and `lo...hi` ranges, separated by commas, and a prong /// may capture with `|name|` after its `=>`, as in Zig. fn parseSwitch(self: *Parser) Error!*const Node { try self.enter(); defer self.leave(); const pos = self.cur.start; try self.advance(); _ = try self.expect(.l_paren); const subject = try self.parseExpr(); _ = try self.expect(.r_paren); _ = try self.expect(.l_brace); var prongs: std.ArrayList(ast.Prong) = .empty; var otherwise: ?ast.Prong = null; // Every case that is a literal, to find one written twice. var literals: std.ArrayList(*const Node) = .empty; while (self.cur.tag != .r_brace) { var cases: std.ArrayList(ast.Case) = .empty; if (self.cur.tag == .keyword_else) { if (otherwise != null) return self.fail(self.cur.start, "a switch can have only one 'else'", .{}); try self.advance(); } else while (true) { const case_pos = self.cur.start; const lo = try self.parseExpr(); if (self.cur.tag == .ellipsis3) { try self.advance(); try cases.append(self.arena, .{ .range = .{ .lo = lo, .hi = try self.parseExpr() } }); } else { if (literal(lo)) { for (literals.items) |prev| { if (sameLiteral(prev, lo)) return self.fail(case_pos, "duplicate switch case", .{}); } try literals.append(self.arena, lo); } try cases.append(self.arena, .{ .value = lo }); } if (self.cur.tag != .comma) break; try self.advance(); // `a, b, => x` is allowed, as Zig allows it. if (self.cur.tag == .equal_angle_bracket_right) break; } _ = try self.expect(.equal_angle_bracket_right); var capture: ?u32 = null; if (self.cur.tag == .pipe) { try self.advance(); const name, const name_pos = try self.expectName(); _ = try self.expect(.pipe); capture = try self.bind(name, name_pos, null); } const value = try self.parseExpr(); // The capture is in scope for its own prong only. if (capture != null) _ = self.scope.pop(); const prong: ast.Prong = .{ .cases = cases.items, .capture = capture, .value = value }; if (cases.items.len == 0) otherwise = prong else try prongs.append(self.arena, prong); if (self.cur.tag == .comma) { try self.advance(); } else if (self.cur.tag != .r_brace) { return self.unexpected("',' or '}}'"); } } try self.advance(); if (prongs.items.len == 0 and otherwise == null) return self.fail(pos, "a switch needs at least one prong", .{}); return self.node(pos, .{ .@"switch" = .{ .subject = subject, .prongs = prongs.items, .@"else" = otherwise } }); } /// Whether `n` is a value written out, which two cases cannot both be. fn literal(n: *const Node) bool { return switch (n.data) { .null, .bool, .int, .string, .enum_literal => true, else => false, }; } fn sameLiteral(a: *const Node, b: *const Node) bool { if (std.meta.activeTag(a.data) != std.meta.activeTag(b.data)) return false; return switch (a.data) { .null => true, .bool => |x| x == b.data.bool, .int => |x| x == b.data.int, .string => |x| std.mem.eql(u8, x, b.data.string), .enum_literal => |x| std.mem.eql(u8, x, b.data.enum_literal), else => false, }; } fn parseBranch(self: *Parser, allow_no_else: bool) Error!*const Node { if (allow_no_else and self.cur.tag == .keyword_if) return self.parseIf(true); return self.parseExpr(); } /// A field's value or a list's item: an expression, or an `if` that need not /// have an `else`. fn parseItem(self: *Parser) Error!*const Node { if (self.cur.tag == .keyword_if) return self.parseIf(true); return self.parseExpr(); } /// `.{ ... }`: a struct if it starts `.name =`, a list otherwise, and empty /// -- which decodes as either -- if it is `.{}`. fn parseLiteral(self: *Parser) Error!*const Node { try self.enter(); defer self.leave(); const pos = self.cur.start; try self.advance(); if (self.cur.tag == .r_brace) { try self.advance(); return self.node(pos, .{ .record = &.{} }); } const is_record = blk: { if (self.cur.tag != .period) break :blk false; var look = self.tok; const name = look.next(); if (name.tag != .identifier and name.tag != .quoted_identifier) break :blk false; break :blk look.next().tag == .equal; }; if (is_record) { var fields: std.ArrayList(ast.Field) = .empty; while (true) { if (self.cur.tag != .period) return self.unexpected("'.name = value' or '}}'"); try self.advance(); const name, const name_pos = try self.expectName(); for (fields.items) |f| { if (std.mem.eql(u8, f.name, name)) return self.fail(name_pos, "duplicate field '{s}'", .{name}); } _ = try self.expect(.equal); const value = try self.parseItem(); try fields.append(self.arena, .{ .name = name, .pos = self.base + name_pos, .value = value }); if (try self.endOfList()) break; } return self.node(pos, .{ .record = fields.items }); } var list: std.ArrayList(ast.Item) = .empty; while (true) { try list.append(self.arena, try self.parseItem()); if (try self.endOfList()) break; } return self.node(pos, .{ .list = list.items }); } /// After an item of a list: `,` and maybe `}`, or just `}`. True at the end. fn endOfList(self: *Parser) Error!bool { switch (self.cur.tag) { .comma => { try self.advance(); if (self.cur.tag != .r_brace) return false; try self.advance(); return true; }, .r_brace => { try self.advance(); return true; }, else => return self.unexpected("',' or '}}'"), } } fn parseCall(self: *Parser) Error!*const Node { try self.enter(); defer self.leave(); const t = self.cur; const name = self.source[t.start + 1 .. t.end]; const is_include = std.mem.eql(u8, name, "include"); const func: ast.Func, const min: usize, const max: usize = blk: { if (is_include) { if (self.include == null) return self.fail(t.start, "@include is not supported here", .{}); break :blk .{ undefined, 1, 1 }; } if (std.meta.stringToEnum(Builtin, name)) |b| { const arity = b.arity(); break :blk .{ .{ .builtin = b }, arity.min, arity.max }; } for (self.functions, 0..) |f, i| { if (std.mem.eql(u8, f.name, name)) break :blk .{ .{ .host = @intCast(i) }, f.min_args, f.max_args }; } return self.fail(t.start, "unknown function '@{s}'", .{name}); }; try self.advance(); _ = try self.expect(.l_paren); // Where the first argument starts, which its node may not: `a.b` is // where its `.` is. const first_arg = self.cur.start; var args: std.ArrayList(*const Node) = .empty; while (self.cur.tag != .r_paren) { try args.append(self.arena, try self.parseExpr()); if (self.cur.tag == .comma) { try self.advance(); } else if (self.cur.tag != .r_paren) { return self.unexpected("',' or ')'"); } } try self.advance(); if (args.items.len < min or args.items.len > max) { if (min == max) return self.fail(t.start, "@{s} takes {d} argument{s}, not {d}", .{ name, min, if (min == 1) "" else "s", args.items.len }); if (args.items.len < min) return self.fail(t.start, "@{s} takes at least {d} argument{s}, not {d}", .{ name, min, if (min == 1) "" else "s", args.items.len }); return self.fail(t.start, "@{s} takes at most {d} argument{s}, not {d}", .{ name, max, if (max == 1) "" else "s", args.items.len }); } if (is_include) return self.includeFile(t.start, first_arg, args.items[0]); return self.node(t.start, .{ .call = .{ .func = func, .args = args.items } }); } // -- includes ----------------------------------------------------------------- const LocalError = error{ OutOfMemory, NotFile, NotLocal, NotAbsolute }; /// `u`, which must be a `file:` URI naming a file on this machine, in the /// one spelling every such URI is given here: `file:///path`, with dot /// segments resolved, the host empty rather than `localhost`, and no query /// or fragment, neither of which names anything on a filesystem. fn localFile(arena: Allocator, u: Uri) LocalError!Uri { const scheme = u.scheme orelse return error.NotFile; if (!std.ascii.eqlIgnoreCase(scheme, "file")) return error.NotFile; if (u.host) |host| switch (host) { .hostname => |h| if (h.len != 0 and !std.ascii.eqlIgnoreCase(h, "localhost")) return error.NotLocal, .ipv4, .ipv6 => return error.NotLocal, }; if (u.username != null or u.password != null or u.port != null) return error.NotLocal; if (!u.rooted) return error.NotAbsolute; var c = (try u.normalize(arena, .{})).parts(); c.host = .{ .hostname = "" }; c.query = &.{}; c.fragment = null; return Uri.init(arena, c); } /// What is wrong with a URI that `localFile` refused, to follow its text. fn notLocal(err: LocalError) []const u8 { return switch (err) { error.NotFile => "is not a file: URI", error.NotLocal => "names a file on another machine", error.NotAbsolute => "has no absolute path", error.OutOfMemory => unreachable, }; } /// The `file:` URI that `path`, written in the file being parsed, names. fn resolveInclude(self: *Parser, pos: u32, path: []const u8) Error!Uri { const ref = Uri.parse(self.arena, path) catch |err| switch (err) { error.OutOfMemory => return error.OutOfMemory, else => return self.fail(pos, "'{s}' is not a URI reference", .{path}), }; // With no URI of its own, a program can still include an absolute path, // and a URI, but has nothing to resolve a relative path against. const base = self.uri orelse blk: { if (ref.scheme == null and ref.host == null and !ref.rooted) { return self.fail(pos, "'{s}' is relative, and this program has no filename to resolve it against", .{path}); } break :blk Uri.parse(self.arena, "file:///") catch |err| switch (err) { error.OutOfMemory => return error.OutOfMemory, else => unreachable, }; }; const target = base.clickUri(self.arena, ref) catch |err| switch (err) { error.OutOfMemory => return error.OutOfMemory, else => return self.fail(pos, "'{s}' cannot be resolved", .{path}), }; return localFile(self.arena, target) catch |err| switch (err) { error.OutOfMemory => return error.OutOfMemory, else => |e| self.fail(pos, "'{s}' {s}", .{ path, notLocal(e) }), }; } /// `@include(path)`, at `pos`, with `path` starting at `arg_pos`: parse the /// file and stand a slot in for it. fn includeFile(self: *Parser, pos: u32, arg_pos: u32, arg: *const Node) Error!*const Node { const include = self.include.?; const path = switch (arg.data) { .string => |s| s, else => return self.fail(arg_pos, "@include takes a string literal", .{}), }; const file_uri = try self.resolveInclude(arg_pos, path); const name = try file_uri.toText(self.arena, .{}); if (self.files.get(name)) |state| { const slot = state orelse return self.fail(pos, "'{s}' includes itself", .{name}); return self.node(pos, .{ .slot = slot }); } if (self.files.count() >= self.max_includes) { return self.fail(pos, "more than {d} files included", .{self.max_includes}); } try self.files.put(self.arena, name, null); const contents = include.read(include.context, self.arena, name) catch |err| switch (err) { error.OutOfMemory => return error.OutOfMemory, else => { self.diag.setIn(self.name, .of(self.source, pos), "cannot include '{s}': {s}", .{ name, @errorName(err) }); return error.Include; }, }; const last = self.sources.items[self.sources.items.len - 1]; // One past the end of the file before, so that the end of one file is // not the start of the next. const base = @as(u64, last.base) + last.text.len + 1; if (base + contents.len >= std.math.maxInt(u32)) return self.fail(pos, "program too large", .{}); try self.sources.append(self.arena, .{ .name = name, .text = contents, .base = @intCast(base) }); // The file is parsed with this parser, but as a program of its own: its // `let`s are not seen by the file that includes it, nor that file's by // it. Nesting carries on counting, which bounds how deeply includes nest. const saved = .{ self.source, self.tok, self.cur, self.name, self.uri, self.base, self.scope }; self.source = contents; self.tok = .init(contents); self.name = name; self.uri = file_uri; self.base = @intCast(base); self.scope = .empty; const root = try self.parseFile(); self.source, self.tok, self.cur, self.name, self.uri, self.base, self.scope = saved; const slot: u32 = @intCast(self.slots.items.len); try self.slots.append(self.arena, root); try self.files.put(self.arena, name, slot); return self.node(pos, .{ .slot = slot }); } // -- literals ----------------------------------------------------------------- fn number(self: *Parser, t: Token, negative: bool, pos: u32) Error!*const Node { const bytes = self.text(t); switch (std.zig.parseNumberLiteral(bytes)) { .int => |u| { const limit: u64 = if (negative) 1 << 63 else std.math.maxInt(i64); if (u > limit) return self.fail(pos, "integer literal does not fit in an i64", .{}); const i: i64 = if (negative) @intCast(-@as(i128, u)) else @intCast(u); return self.node(pos, .{ .int = i }); }, .big_int => return self.fail(pos, "integer literal does not fit in an i64", .{}), .float => { const f = std.fmt.parseFloat(f64, bytes) catch return self.fail(t.start, "invalid number literal", .{}); return self.node(pos, .{ .float = if (negative) -f else f }); }, .failure => return self.fail(t.start, "invalid number literal '{s}'", .{bytes}), } } fn charLiteral(self: *Parser, t: Token) Error!i64 { const content = self.source[t.start + 1 .. t.end - 1]; if (content.len == 0) return self.fail(t.start, "empty character literal", .{}); var buf: std.ArrayList(u8) = .empty; var i: usize = 0; if (content[0] == '\\') { i = try self.escape(&buf, t.start + 1); if (i != content.len) return self.fail(t.start, "a character literal holds one character", .{}); const cp = std.unicode.utf8Decode(buf.items) catch return @intCast(buf.items[0]); return cp; } const n = std.unicode.utf8ByteSequenceLength(content[0]) catch return self.fail(t.start + 1, "invalid UTF-8", .{}); if (n != content.len) return self.fail(t.start, "a character literal holds one character", .{}); return std.unicode.utf8Decode(content) catch self.fail(t.start + 1, "invalid UTF-8", .{}); } /// Decode the escape sequence at `source[at]` (the backslash) onto `buf`, and /// return how many bytes of source it took. fn escape(self: *Parser, buf: *std.ArrayList(u8), at: u32) Error!u32 { const s = self.source; if (at + 1 >= s.len) return self.fail(at, "unterminated escape sequence", .{}); const c = s[at + 1]; const simple: ?u8 = switch (c) { 'n' => '\n', 'r' => '\r', 't' => '\t', '\\' => '\\', '\'' => '\'', '"' => '"', '$' => '$', else => null, }; if (simple) |b| { try buf.append(self.arena, b); return 2; } switch (c) { 'x' => { if (at + 4 > s.len) return self.fail(at, "invalid escape sequence", .{}); const b = std.fmt.parseInt(u8, s[at + 2 .. at + 4], 16) catch return self.fail(at, "invalid escape sequence", .{}); try buf.append(self.arena, b); return 4; }, 'u' => { if (at + 2 >= s.len or s[at + 2] != '{') return self.fail(at, "invalid escape sequence", .{}); const close = std.mem.findScalarPos(u8, s, at + 3, '}') orelse return self.fail(at, "invalid escape sequence", .{}); const cp = std.fmt.parseInt(u21, s[at + 3 .. close], 16) catch return self.fail(at, "invalid escape sequence", .{}); var enc: [4]u8 = undefined; const n = std.unicode.utf8Encode(cp, &enc) catch return self.fail(at, "invalid Unicode code point", .{}); try buf.appendSlice(self.arena, enc[0..n]); return @intCast(close + 1 - at); }, else => return self.fail(at, "invalid escape sequence '\\{c}'", .{c}), } } /// The bytes of a string without interpolation, escapes decoded. fn decodeString(self: *Parser, start: u32, end: u32) Error![]const u8 { if (std.mem.findScalar(u8, self.source[start..end], '\\') == null) return self.source[start..end]; var buf: std.ArrayList(u8) = .empty; var i = start; while (i < end) { if (self.source[i] == '\\') { i += try self.escape(&buf, i); } else { try buf.append(self.arena, self.source[i]); i += 1; } } return buf.items; } /// Collects the pieces of a string that may have `${ }` in it. const Template = struct { parts: std.ArrayList(ast.Part) = .empty, buf: std.ArrayList(u8) = .empty, fn flush(self: *Template, arena: Allocator) Error!void { if (self.buf.items.len == 0) return; try self.parts.append(arena, .{ .text = self.buf.items }); self.buf = .empty; } fn finish(self: *Template, p: *Parser, pos: u32) Error!*const Node { if (self.parts.items.len == 0) return p.node(pos, .{ .string = self.buf.items }); try self.flush(p.arena); return p.node(pos, .{ .template = self.parts.items }); } }; /// Read `source[start..end]` into `t`: one string's content, or one line of /// a multiline string, which has no escapes. fn templateContent(self: *Parser, t: *Template, start: u32, end: u32, escapes: bool) Error!void { var i = start; while (i < end) { const c = self.source[i]; if (c == '\\' and escapes) { i += try self.escape(&t.buf, i); } else if (c == '$' and i + 1 < end and self.source[i + 1] == '{') { const close = Tokenizer.skipInterpolation(self.source, i + 2, end, 0) orelse return self.fail(i, "unterminated interpolation", .{}); try t.flush(self.arena); try t.parts.append(self.arena, .{ .expr = try self.interpolation(i, close) }); i = close + 1; } else { try t.buf.append(self.arena, c); i += 1; } } } /// Parse what is inside `${ }`, by pointing a second tokenizer at it. fn interpolation(self: *Parser, dollar: u32, close: u32) Error!*const Node { const saved_tok = self.tok; const saved_cur = self.cur; self.tok = .{ .source = self.source, .index = dollar + 2, .limit = close }; try self.advance(); if (self.cur.tag == .eof) return self.fail(dollar, "empty interpolation", .{}); const n = try self.parseExpr(); if (self.cur.tag != .eof) return self.unexpected("'}}'"); self.tok = saved_tok; self.cur = saved_cur; return n; } fn stringLiteral(self: *Parser, t: Token) Error!*const Node { var tmpl: Template = .{}; try self.templateContent(&tmpl, t.start + 1, t.end - 1, true); return tmpl.finish(self, t.start); } /// Consecutive `\\` lines are one string, joined with newlines, as in Zig. fn multilineString(self: *Parser) Error!*const Node { const pos = self.cur.start; var tmpl: Template = .{}; var first = true; while (self.cur.tag == .multiline_string_line) { if (!first) try tmpl.buf.append(self.arena, '\n'); first = false; var end = self.cur.end; if (end > self.cur.start + 2 and self.source[end - 1] == '\r') end -= 1; try self.templateContent(&tmpl, self.cur.start + 2, end, false); try self.advance(); } return tmpl.finish(self, pos); } // -- tests -------------------------------------------------------------------- const testing = std.testing; fn parseTest(arena: Allocator, source: []const u8, diag: *Diagnostic) Error!Tree { return parse(arena, source, .{}, diag); } fn expectSyntaxError(source: []const u8, line: u32, column: u32, message: []const u8) !void { var arena: std.heap.ArenaAllocator = .init(testing.allocator); defer arena.deinit(); var d: Diagnostic = .{}; if (parseTest(arena.allocator(), source, &d)) |_| { std.debug.print("parsed, but expected: {s}\n", .{message}); return error.TestUnexpectedSuccess; } else |err| try testing.expectEqual(error.Syntax, err); testing.expectEqualStrings(message, d.message()) catch |err| { std.debug.print("source: {s}\n", .{source}); return err; }; try testing.expectEqual(Diagnostic.Pos{ .line = line, .column = column }, d.pos); } test "plain ZON parses" { var arena: std.heap.ArenaAllocator = .init(testing.allocator); defer arena.deinit(); var d: Diagnostic = .{}; const tree = try parseTest(arena.allocator(), \\.{ \\ .name = .struthio, \\ .version = "0.1.0", \\ .fingerprint = 0x1234, \\ .@"min zig" = -1.5e3, \\ .paths = .{ "build.zig", "src", }, \\ .deps = .{}, \\ .c = 'é', \\} , &d); const r = tree.root.data.record; try testing.expectEqual(@as(usize, 7), r.len); try testing.expectEqualStrings("struthio", r[0].value.data.enum_literal); try testing.expectEqual(@as(i64, 0x1234), r[2].value.data.int); try testing.expectEqualStrings("min zig", r[3].name); try testing.expectEqual(@as(f64, -1500), r[3].value.data.float); try testing.expectEqual(@as(usize, 2), r[4].value.data.list.len); try testing.expectEqual(@as(i64, 0xe9), r[6].value.data.int); } test "precedence follows Zig" { var arena: std.heap.ArenaAllocator = .init(testing.allocator); defer arena.deinit(); var d: Diagnostic = .{}; // or < and < == < orelse < + < * const tree = try parseTest(arena.allocator(), "let a = null; a orelse 1 + 2 * 3 == 7 and true or false", &d); const top = tree.root.data.binary; try testing.expectEqual(ast.BinaryOp.@"or", top.op); const and_ = top.lhs.data.binary; try testing.expectEqual(ast.BinaryOp.@"and", and_.op); const eq = and_.lhs.data.binary; try testing.expectEqual(ast.BinaryOp.eq, eq.op); const orelse_ = eq.lhs.data.binary; try testing.expectEqual(ast.BinaryOp.@"orelse", orelse_.op); try testing.expectEqual(ast.BinaryOp.add, orelse_.rhs.data.binary.op); } test "templates split into parts" { var arena: std.heap.ArenaAllocator = .init(testing.allocator); defer arena.deinit(); var d: Diagnostic = .{}; const tree = try parseTest(arena.allocator(), "\"a\\${b}${ctx.x}c${@join(ctx.y, \"}\")}\"", &d); const parts = tree.root.data.template; try testing.expectEqual(@as(usize, 4), parts.len); try testing.expectEqualStrings("a${b}", parts[0].text); try testing.expectEqualStrings("x", parts[1].expr.data.field.name); try testing.expectEqualStrings("c", parts[2].text); try testing.expectEqual(Builtin.join, parts[3].expr.data.call.func.builtin); } test "the most negative integer can be written" { var arena: std.heap.ArenaAllocator = .init(testing.allocator); defer arena.deinit(); var d: Diagnostic = .{}; const tree = try parseTest(arena.allocator(), "-9223372036854775808", &d); try testing.expectEqual(@as(i64, std.math.minInt(i64)), tree.root.data.int); } test "syntax errors say where" { try expectSyntaxError("let x = 1; y", 1, 12, "unknown name 'y'"); try expectSyntaxError("let x = x; x", 1, 9, "unknown name 'x'"); try expectSyntaxError("let x = 1;\nlet x = 2; x", 2, 5, "'x' is already defined"); try expectSyntaxError("let ctx = 1; 2", 1, 5, "'ctx' is reserved and cannot be redefined"); try expectSyntaxError(".{ .a = 1, .a = 2 }", 1, 13, "duplicate field 'a'"); try expectSyntaxError("if (true) 1", 1, 1, "an 'if' without 'else' can only be a struct field's value or a list item"); try expectSyntaxError("1 < 2 < 3", 1, 7, "comparisons cannot be chained"); try expectSyntaxError("\"abc", 1, 1, "unterminated string"); try expectSyntaxError("\"a${}\"", 1, 3, "empty interpolation"); try expectSyntaxError("\"a${1 2}\"", 1, 7, "expected '}', found a number"); try expectSyntaxError("\"\\q\"", 1, 2, "invalid escape sequence '\\q'"); try expectSyntaxError("@nope(1)", 1, 1, "unknown function '@nope'"); try expectSyntaxError("switch (1) {}", 1, 1, "a switch needs at least one prong"); try expectSyntaxError("switch (1) { .a, .b => 1, .a => 2 }", 1, 27, "duplicate switch case"); try expectSyntaxError("switch (1) { else => 1, else => 2 }", 1, 25, "a switch can have only one 'else'"); try expectSyntaxError("switch (1) { 1 => 1 2 }", 1, 21, "expected ',' or '}', found a number"); try expectSyntaxError("switch (1) { 1, 2 }", 1, 19, "expected '=>', found '}'"); try expectSyntaxError("switch (ctx.a) { .b => |v| v, else => v }", 1, 39, "unknown name 'v'"); try expectSyntaxError("@include(\"x\")", 1, 1, "@include is not supported here"); try expectSyntaxError("@lower()", 1, 1, "@lower takes 1 argument, not 0"); try expectSyntaxError(".{ 1 2 }", 1, 6, "expected ',' or '}', found a number"); try expectSyntaxError("99999999999999999999", 1, 1, "integer literal does not fit in an i64"); try expectSyntaxError("1 #", 1, 3, "unexpected character '#'"); try expectSyntaxError("if (ctx.a) |v| v else v", 1, 23, "unknown name 'v'"); } test "nesting is bounded" { var src: std.ArrayList(u8) = .empty; defer src.deinit(testing.allocator); for (0..100) |_| try src.appendSlice(testing.allocator, "("); try src.appendSlice(testing.allocator, "1"); for (0..100) |_| try src.appendSlice(testing.allocator, ")"); var arena: std.heap.ArenaAllocator = .init(testing.allocator); defer arena.deinit(); var d: Diagnostic = .{}; try testing.expectError(error.Syntax, parseTest(arena.allocator(), src.items, &d)); try testing.expectEqualStrings("expression nested too deeply", d.message()); }