//! Expression grammar (M1-RULE-003, M1-RULE-004, M1-RULE-005). //! //! Recursive descent in exactly the shape M1-RULE-003 writes it, which is what //! gives M1-RULE-005 its precedence: or calls and, and calls unary, and unary //! calls itself through `not`. So `not` binds tightest and `or` loosest, and //! parentheses re-enter at the top. //! //! M1-RULE-004 is enforced when a comparison is built: the left side is always //! an identifier, and each operator admits only its own literal kinds. There is //! no production that would accept a literal on the left or a field on the //! right, so field-to-field comparison cannot be written. const std = @import("std"); const diag = @import("../diag.zig"); const Decimal = @import("../Decimal.zig"); const lexer = @import("lexer.zig"); pub const Error = lexer.Error; /// Where the expression came from, for diagnostics (M1-DIAG-002). pub const Context = struct { file: []const u8, /// e.g. "rules.groceries.match" key_path: []const u8, }; pub const Operator = enum { eq, ge, gt, le, lt, matches, ne, pub fn format(self: Operator, writer: *std.Io.Writer) std.Io.Writer.Error!void { return writer.writeAll(switch (self) { .eq => "==", .ne => "!=", .lt => "<", .le => "<=", .gt => ">", .ge => ">=", .matches => "~=", }); } }; pub const Operand = union(enum) { decimal: Decimal, /// Still uncompiled; M1-RULE-017 and M1-RULE-018 belong to the regex module. regex: lexer.RegexLiteral, string: []const u8, pub fn format(self: Operand, writer: *std.Io.Writer) std.Io.Writer.Error!void { switch (self) { .string => |text| { try writer.print("\"{s}\"", .{text}); }, .decimal => |value| { try writer.print("{f}", .{value}); }, .regex => |value| { try writer.print("/{s}/", .{value.pattern}); if (value.flags.case_insensitive) try writer.writeAll("i"); if (value.flags.multiline) try writer.writeAll("m"); if (value.flags.dot_all) try writer.writeAll("s"); }, } } }; pub const Comparison = struct { /// A field alias, always (M1-RULE-004, M1-CSV-015). field: []const u8, operand: Operand, operator: Operator, pub fn format(self: *const Comparison, writer: *std.Io.Writer) std.Io.Writer.Error!void { try writer.print("({f} {s} {f})", .{ self.operator, self.field, self.operand }); } }; pub const Expr = union(enum) { /// "and" operands, likewise. all_of: []const *const Expr, /// "or" operands in source order, which M1-RULE-019 evaluates left to right. any_of: []const *const Expr, comparison: Comparison, negate: *const Expr, /// A canonical parenthesised form. Used by the tests to state precedence /// compactly, and usable in diagnostics. pub fn format(self: *const Expr, writer: *std.Io.Writer) std.Io.Writer.Error!void { switch (self.*) { .comparison => |comparison| { try writer.print("{f}", .{comparison}); }, .negate => |inner| { try writer.print("(not {f})", .{inner}); }, .any_of => |operands| try formatOperands("or", operands, writer), .all_of => |operands| try formatOperands("and", operands, writer), } } fn formatOperands(keyword: []const u8, operands: []const *const Expr, writer: *std.Io.Writer) !void { try writer.print("({s}", .{keyword}); for (operands) |operand| { try writer.print(" {f}", .{operand}); } try writer.writeAll(")"); } }; pub fn parse( arena: std.mem.Allocator, source: []const u8, context: Context, diags: *diag.List, ) Error!*const Expr { var tokens: std.ArrayList(lexer.Token) = .empty; var scanner = lexer.Lexer.init(arena, source); while (true) { const token = scanner.next() catch |err| switch (err) { error.InvalidExpression => { reportAt(diags, context, "invalid token at byte {d}", .{scanner.token_start}); return error.InvalidExpression; }, else => return err, } orelse break; try tokens.append(arena, token); } var parser: Parser = .{ .arena = arena, .tokens = tokens.items, .index = 0, .context = context, .diags = diags, }; const tree = try parser.parseOr(); if (parser.index != parser.tokens.len) { return parser.fail("unexpected input after the end of the expression", .{}); } return tree; } /// Appends every field alias the expression mentions, in source order. Used to /// check aliases against the profile (M1-CSV-015). pub fn collectFields( arena: std.mem.Allocator, expr: *const Expr, out: *std.ArrayList([]const u8), ) Error!void { switch (expr.*) { .comparison => |comparison| try out.append(arena, comparison.field), .negate => |inner| try collectFields(arena, inner, out), .any_of, .all_of => |operands| { for (operands) |operand| try collectFields(arena, operand, out); }, } } /// How deeply `not` and parentheses may nest. /// /// The grammar is recursive descent, so nesting costs stack, and enough of it /// overflows the stack and kills the process -- which in interactive mode /// would take an unsaved draft with it. M1-SAFE-004 asks for a safe failure, /// and a limit is the only way a recursive parser gets one. The bound is far /// beyond any rule a person would write and far below where the stack runs /// out: nesting in the tens of thousands is what crashes. pub const max_depth = 128; const Parser = struct { arena: std.mem.Allocator, context: Context, depth: usize = 0, diags: *diag.List, index: usize, tokens: []const lexer.Token, /// Entering a nested expression, or refusing to. fn descend(self: *Parser) Error!void { self.depth += 1; if (self.depth > max_depth) { return self.fail("expression nests deeper than {d} levels", .{max_depth}); } } fn ascend(self: *Parser) void { self.depth -= 1; } fn peek(self: *Parser) ?lexer.Token { if (self.index >= self.tokens.len) return null; return self.tokens[self.index]; } fn advance(self: *Parser) ?lexer.Token { const token = self.peek() orelse return null; self.index += 1; return token; } fn eat(self: *Parser, comptime tag: std.meta.Tag(lexer.Token)) bool { const token = self.peek() orelse return false; if (std.meta.activeTag(token) != tag) return false; self.index += 1; return true; } fn node(self: *Parser, value: Expr) Error!*const Expr { const created = try self.arena.create(Expr); created.* = value; return created; } /// or_expression := and_expression ("or" and_expression)* fn parseOr(self: *Parser) Error!*const Expr { var operands: std.ArrayList(*const Expr) = .empty; try operands.append(self.arena, try self.parseAnd()); while (self.eat(.keyword_or)) { try operands.append(self.arena, try self.parseAnd()); } if (operands.items.len == 1) return operands.items[0]; return self.node(.{ .any_of = operands.items }); } /// and_expression := unary_expression ("and" unary_expression)* fn parseAnd(self: *Parser) Error!*const Expr { var operands: std.ArrayList(*const Expr) = .empty; try operands.append(self.arena, try self.parseUnary()); while (self.eat(.keyword_and)) { try operands.append(self.arena, try self.parseUnary()); } if (operands.items.len == 1) return operands.items[0]; return self.node(.{ .all_of = operands.items }); } /// unary_expression := "not" unary_expression | "(" expression ")" | comparison fn parseUnary(self: *Parser) Error!*const Expr { if (self.eat(.keyword_not)) { try self.descend(); defer self.ascend(); return self.node(.{ .negate = try self.parseUnary() }); } if (self.eat(.lparen)) { try self.descend(); defer self.ascend(); const inner = try self.parseOr(); if (!self.eat(.rparen)) return self.fail("expected ')'", .{}); return inner; } return self.parseComparison(); } fn parseComparison(self: *Parser) Error!*const Expr { const left = self.advance() orelse return self.fail("expected a comparison", .{}); const field = switch (left) { .identifier => |name| name, // M1-RULE-004: nothing else may stand on the left. else => return self.fail("the left side of a comparison must be a field alias", .{}), }; const operator_token = self.advance() orelse return self.fail("expected a comparison operator after '{s}'", .{field}); const operator: Operator = switch (operator_token) { .eq => .eq, .ne => .ne, .lt => .lt, .le => .le, .gt => .gt, .ge => .ge, .matches => .matches, else => return self.fail("expected a comparison operator after '{s}'", .{field}), }; const literal = self.advance() orelse return self.fail("expected a literal after '{f}'", .{operator}); const operand: Operand = switch (operator) { .eq, .ne => switch (literal) { .string => |text| .{ .string = text }, .decimal => |text| .{ .decimal = try self.decimalOf(text) }, else => return self.fail("'{f}' takes a string or a decimal", .{operator}), }, .lt, .le, .gt, .ge => switch (literal) { .decimal => |text| .{ .decimal = try self.decimalOf(text) }, else => return self.fail("'{f}' takes a decimal", .{operator}), }, .matches => switch (literal) { .regex => |value| .{ .regex = value }, else => return self.fail("'~=' takes a regex literal", .{}), }, }; return self.node(.{ .comparison = .{ .field = field, .operator = operator, .operand = operand, } }); } /// M1-RULE-016: literals always use '.', whatever the profile configures. fn decimalOf(self: *Parser, text: []const u8) Error!Decimal { return Decimal.parseLiteral(text) catch self.fail("'{s}' is not a usable decimal literal", .{text}); } fn fail(self: *Parser, comptime fmt: []const u8, args: anytype) Error { reportAt(self.diags, self.context, fmt, args); return error.InvalidExpression; } }; fn reportAt(diags: *diag.List, context: Context, comptime fmt: []const u8, args: anytype) void { // zlinter-disable-next-line no_swallow_error - infallible by design: an unrecordable diagnostic is dropped diags.addConfig(.{ .file = context.file, .key_path = context.key_path }, fmt, args) catch {}; } // -- tests ------------------------------------------------------------------- const expect = std.testing.expect; const expectEqualStrings = std.testing.expectEqualStrings; const expectError = std.testing.expectError; fn shapeOf(arena: *std.heap.ArenaAllocator, source: []const u8) Error![]const u8 { const alloc = arena.allocator(); const diags = diag.List.create(alloc) catch return error.OutOfMemory; const tree = try parse(alloc, source, .{ .file = "rules.yaml", .key_path = "rules.r.match" }, diags); return alloc.print("{f}", .{tree}); } fn expectShape(source: []const u8, shape: []const u8) !void { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); try expectEqualStrings(shape, try shapeOf(&arena, source)); } fn expectRejected(source: []const u8) !void { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); try expectError(error.InvalidExpression, shapeOf(&arena, source)); } test "M1-RULE-003: every comparison form parses" { try expectShape("a == \"x\"", "(== a \"x\")"); try expectShape("a != \"x\"", "(!= a \"x\")"); try expectShape("a == 1", "(== a 1)"); try expectShape("a != -1.50", "(!= a -1.50)"); try expectShape("a < 1", "(< a 1)"); try expectShape("a <= 1", "(<= a 1)"); try expectShape("a > 1", "(> a 1)"); try expectShape("a >= 1", "(>= a 1)"); try expectShape("a ~= /x/", "(~= a /x/)"); try expectShape("a ~= /x/ims", "(~= a /x/ims)"); } test "M1-RULE-004: the left operand is always a field alias" { // Each of these is valid on both sides *except* for what stands on the // left, so they isolate the left-operand rule rather than failing because // the right side is also wrong. try expectRejected("\"x\" == \"y\""); try expectRejected("1 == 1"); try expectRejected("1 < 2"); try expectRejected("/x/ ~= /y/"); // And the mixed cases. try expectRejected("1 == \"x\""); try expectRejected("\"x\" == a"); try expectRejected("/x/ ~= a"); } test "M1-RULE-004: field-to-field comparison is not supported" { try expectRejected("a == b"); try expectRejected("a < b"); } test "M1-RULE-004: each operator admits only its own literal kinds" { // Ordering operators take decimals only. try expectRejected("a < \"x\""); try expectRejected("a >= /x/"); // The regex operator takes regexes only. try expectRejected("a ~= \"x\""); try expectRejected("a ~= 1"); // Equality takes strings or decimals, never regexes. try expectRejected("a == /x/"); try expectRejected("a != /x/"); } test "M1-RULE-005: and binds more tightly than or" { try expectShape( "a == \"1\" or b == \"2\" and c == \"3\"", "(or (== a \"1\") (and (== b \"2\") (== c \"3\")))", ); try expectShape( "a == \"1\" and b == \"2\" or c == \"3\"", "(or (and (== a \"1\") (== b \"2\")) (== c \"3\"))", ); } test "M1-RULE-005: not binds more tightly than and" { try expectShape( "not a == \"1\" and b == \"2\"", "(and (not (== a \"1\")) (== b \"2\"))", ); try expectShape("not not a == \"1\"", "(not (not (== a \"1\")))"); } test "M1-RULE-005: parentheses override precedence and nest" { try expectShape( "(a == \"1\" or b == \"2\") and c == \"3\"", "(and (or (== a \"1\") (== b \"2\")) (== c \"3\"))", ); try expectShape( "not (a == \"1\" or b == \"2\")", "(not (or (== a \"1\") (== b \"2\")))", ); try expectShape("((a == \"1\"))", "(== a \"1\")"); } test "M1-RULE-005: a chain of the same operator stays flat and ordered" { try expectShape( "a == \"1\" or b == \"2\" or c == \"3\"", "(or (== a \"1\") (== b \"2\") (== c \"3\"))", ); try expectShape( "a == \"1\" and b == \"2\" and c == \"3\"", "(and (== a \"1\") (== b \"2\") (== c \"3\"))", ); } test "M1-AC-011: the worked example parses with the stated precedence" { try expectShape( "account == \"DE23\" or amount >= 100 and not posting ~= /refund/i", "(or (== account \"DE23\") (and (>= amount 100) (not (~= posting /refund/i))))", ); } test "M1-RULE-003: malformed expressions are rejected" { try expectRejected(""); try expectRejected(" "); try expectRejected("a =="); try expectRejected("a == \"1\" and"); try expectRejected("(a == \"1\""); try expectRejected("a == \"1\")"); try expectRejected("a == \"1\" b == \"2\""); try expectRejected("and"); try expectRejected("not"); } test "M1-RULE-014: an expression cannot use a keyword as a field" { try expectRejected("and == \"1\""); try expectRejected("not == \"1\""); // But an identifier merely containing one is fine. try expectShape("android == \"1\"", "(== android \"1\")"); } test "M1-RULE-016: decimal literals keep their exact value" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const alloc = arena.allocator(); const diags = try diag.List.create(alloc); const tree = try parse(alloc, "amount == 100.00", .{ .file = "rules.yaml", .key_path = "rules.r.match", }, diags); const literal = tree.comparison.operand.decimal; try expect(literal.eql(try Decimal.parseLiteral("100"))); } test "M1-DIAG-002: a syntax error names the file and the rule's key path" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const alloc = arena.allocator(); const diags = try diag.List.create(alloc); _ = parse(alloc, "a ==", .{ .file = "rules.yaml", .key_path = "rules.groceries.match", }, diags) catch {}; try expect(!diags.isEmpty()); try expectEqualStrings("rules.yaml", diags.items.items[0].file.?); try expectEqualStrings("rules.groceries.match", diags.items.items[0].key_path.?); } test "fields used by an expression can be collected for alias checking" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const alloc = arena.allocator(); const diags = try diag.List.create(alloc); const tree = try parse(alloc, "x == \"1\" and not y ~= /z/", .{ .file = "rules.yaml", .key_path = "rules.r.match", }, diags); var names: std.ArrayList([]const u8) = .empty; try collectFields(alloc, tree, &names); try expectEqualStrings("x", names.items[0]); try expectEqualStrings("y", names.items[1]); } test "M1-SAFE-004: nesting beyond the limit is a diagnostic, not a crash" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const alloc = arena.allocator(); // Deep enough to overflow the stack if nothing stopped it. var source: std.ArrayList(u8) = .empty; try source.appendNTimes(alloc, '(', 50_000); try source.appendSlice(alloc, "x == \"1\""); try source.appendNTimes(alloc, ')', 50_000); var diags = diag.List.init(alloc); try std.testing.expectError( error.InvalidExpression, parse(alloc, source.items, .{ .file = "rules.yaml", .key_path = "r.match" }, &diags), ); try std.testing.expect(std.mem.find(u8, diags.items.items[0].message, "nests deeper") != null); } test "M1-SAFE-004: nesting up to the limit is accepted" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const alloc = arena.allocator(); // The limit is a safety valve, not a grammar restriction: everything a // person would plausibly write stays well inside it. var source: std.ArrayList(u8) = .empty; try source.appendNTimes(alloc, '(', max_depth); try source.appendSlice(alloc, "x == \"1\""); try source.appendNTimes(alloc, ')', max_depth); var diags = diag.List.init(alloc); _ = try parse(alloc, source.items, .{ .file = "rules.yaml", .key_path = "r.match" }, &diags); }