Something went wrong. Try again.
Convert CSV banking statements to hledger journals
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537//! 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);}