//! Expression evaluation (M1-RULE-019, M1-RULE-020). //! //! A result is three-valued: true, false, or unavailable (DESIGN_M1.md 4.1). //! Two requirements decide how the third value moves through the tree. //! //! M1-RULE-019 makes `and` and `or` short-circuit left to right, so a //! predicate in a branch that is never reached cannot produce a row-level //! error. That is what lets the left side of an `or` rescue a row whose amount //! cell is unparseable. //! //! M1-RULE-020 says a *reached* numeric predicate that cannot parse its field //! makes "that rule's result for the row" unavailable. Not unknown in the //! Kleene sense that a later true operand could still rescue -- unavailable, //! for the whole rule. So unavailability propagates outward immediately rather //! than being absorbed. //! //! Regexes are compiled once, when the program is prepared, not once per row, //! and each keeps what it learns while matching. Evaluating a program //! therefore updates it, and a program is for one thread. const std = @import("std"); const diag = @import("../diag.zig"); const Decimal = @import("../Decimal.zig"); const parser = @import("parser.zig"); const regex = @import("regex.zig"); pub const Error = regex.Error; /// One decoded cell, addressed by the alias the profile gave its column. pub const Field = struct { alias: []const u8, value: []const u8, }; pub const Row = struct { fields: []const Field, pub fn get(self: Row, alias: []const u8) ?[]const u8 { for (self.fields) |field| { if (std.mem.eql(u8, field.alias, alias)) return field.value; } return null; } }; /// Why a result is unavailable, so the engine can report it against the row /// (M1-RULE-020, M1-DIAG-001). pub const Failure = struct { /// The cell that could not be used. Empty when the field was absent. cell: []const u8, field: []const u8, }; pub const Outcome = struct { failure: ?Failure = null, /// Null is unavailable. value: ?bool, }; pub const Operand = union(enum) { decimal: Decimal, regex: regex.Compiled, string: []const u8, }; pub const Compare = struct { field: []const u8, operand: Operand, operator: parser.Operator, }; /// Mirrors parser.Expr with regexes already compiled. pub const Node = union(enum) { all_of: []const *Node, any_of: []const *Node, compare: Compare, negate: *Node, }; pub const Program = struct { /// M1-RULE-016: cells use the profile's format; literals always use '.'. amount_format: Decimal.Format, root: *Node, pub fn evaluate(self: Program, row: Row) Outcome { return evaluateNode(self.root, row, self.amount_format); } }; /// Compiles the regexes in an expression so evaluation compiles nothing. pub fn prepare( arena: std.mem.Allocator, expr: *const parser.Expr, amount_format: Decimal.Format, context: parser.Context, diags: *diag.List, ) Error!Program { return .{ .root = try prepareNode(arena, expr, context, diags), .amount_format = amount_format, }; } fn prepareNode( arena: std.mem.Allocator, expr: *const parser.Expr, context: parser.Context, diags: *diag.List, ) Error!*Node { const node = try arena.create(Node); node.* = switch (expr.*) { .comparison => |comparison| .{ .compare = .{ .field = comparison.field, .operator = comparison.operator, .operand = switch (comparison.operand) { .string => |text| .{ .string = text }, .decimal => |value| .{ .decimal = value }, .regex => |literal| .{ .regex = try regex.compile(arena, literal, context, diags), }, }, } }, .negate => |inner| .{ .negate = try prepareNode(arena, inner, context, diags) }, .any_of => |operands| .{ .any_of = try prepareList(arena, operands, context, diags) }, .all_of => |operands| .{ .all_of = try prepareList(arena, operands, context, diags) }, }; return node; } fn prepareList( arena: std.mem.Allocator, operands: []const *const parser.Expr, context: parser.Context, diags: *diag.List, ) Error![]const *Node { const prepared = try arena.alloc(*Node, operands.len); for (operands, 0..) |operand, index| { prepared[index] = try prepareNode(arena, operand, context, diags); } return prepared; } fn evaluateNode(node: *Node, row: Row, amount_format: Decimal.Format) Outcome { return switch (node.*) { .compare => |*comparison| evaluateCompare(comparison, row, amount_format), .negate => |inner| blk: { const outcome = evaluateNode(inner, row, amount_format); const value = outcome.value orelse break :blk outcome; break :blk .{ .value = !value }; }, // M1-RULE-019: stop at the first false; anything after it is unreached // and cannot fail. .all_of => |operands| blk: { for (operands) |operand| { const outcome = evaluateNode(operand, row, amount_format); const value = outcome.value orelse break :blk outcome; if (!value) break :blk .{ .value = false }; } break :blk .{ .value = true }; }, // M1-RULE-019: stop at the first true. .any_of => |operands| blk: { for (operands) |operand| { const outcome = evaluateNode(operand, row, amount_format); const value = outcome.value orelse break :blk outcome; if (value) break :blk .{ .value = true }; } break :blk .{ .value = false }; }, }; } fn evaluateCompare(comparison: *Compare, row: Row, amount_format: Decimal.Format) Outcome { const cell = row.get(comparison.field) orelse return .{ .value = null, .failure = .{ .field = comparison.field, .cell = "" }, }; return switch (comparison.operand) { // M1-RULE-015: exact decoded bytes, no normalization. .string => |text| .{ .value = switch (comparison.operator) { .eq => std.mem.eql(u8, cell, text), .ne => !std.mem.eql(u8, cell, text), // The parser admits no other operator with a string operand. .ge, .gt, .le, .lt, .matches => unreachable, }, }, .decimal => |literal| blk: { // M1-RULE-020: this is the failure the requirement is about. const parsed = Decimal.parse(cell, amount_format) catch break :blk .{ .value = null, .failure = .{ .field = comparison.field, .cell = cell }, }; const ordering = parsed.order(literal); break :blk .{ .value = switch (comparison.operator) { .eq => ordering == .eq, .ne => ordering != .eq, .lt => ordering == .lt, .le => ordering != .gt, .gt => ordering == .gt, .ge => ordering != .lt, .matches => unreachable, } }; }, .regex => |*compiled| blk: { const found = compiled.matches(cell) catch break :blk .{ .value = null, .failure = .{ .field = comparison.field, .cell = cell }, }; break :blk .{ .value = found }; }, }; } // -- tests ------------------------------------------------------------------- const expect = std.testing.expect; const expectEqual = std.testing.expectEqual; const expectEqualStrings = std.testing.expectEqualStrings; fn programOf( arena: *std.heap.ArenaAllocator, source: []const u8, amount_format: Decimal.Format, ) !Program { const alloc = arena.allocator(); const diags = try diag.List.create(alloc); const context: parser.Context = .{ .file = "rules.yaml", .key_path = "rules.r.match" }; const tree = try parser.parse(alloc, source, context, diags); return prepare(alloc, tree, amount_format, context, diags); } fn rowOf(fields: []const Field) Row { return .{ .fields = fields }; } /// Evaluates `source` against one row of alias/value pairs. fn run( arena: *std.heap.ArenaAllocator, source: []const u8, fields: []const Field, ) !Outcome { const program = try programOf(arena, source, .dot); return program.evaluate(rowOf(fields)); } test "M1-RULE-019: or evaluates left to right and stops at the first true" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); // The right operand would fail to parse its field. It is never reached, // so no row-level error is produced. const outcome = try run(&arena, "a == \"1\" or b >= 100", &.{ .{ .alias = "a", .value = "1" }, .{ .alias = "b", .value = "N/A" }, }); try expectEqual(@as(?bool, true), outcome.value); try expect(outcome.failure == null); } test "M1-RULE-019: and evaluates left to right and stops at the first false" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const outcome = try run(&arena, "a == \"0\" and b >= 100", &.{ .{ .alias = "a", .value = "1" }, .{ .alias = "b", .value = "N/A" }, }); try expectEqual(@as(?bool, false), outcome.value); try expect(outcome.failure == null); } test "M1-RULE-020: a reached numeric predicate that cannot parse is unavailable" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const outcome = try run(&arena, "b >= 100", &.{.{ .alias = "b", .value = "N/A" }}); try expect(outcome.value == null); try expectEqualStrings("b", outcome.failure.?.field); try expectEqualStrings("N/A", outcome.failure.?.cell); } test "M1-RULE-020: unavailability propagates through not, and, and or" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const bad: []const Field = &.{ .{ .alias = "a", .value = "N/A" }, .{ .alias = "b", .value = "1" }, }; try expect((try run(&arena, "not a >= 1", bad)).value == null); try expect((try run(&arena, "a >= 1 and b == \"1\"", bad)).value == null); try expect((try run(&arena, "a >= 1 or b == \"1\"", bad)).value == null); } test "M1-RULE-020: an unknown field for this row is unavailable, not false" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const outcome = try run(&arena, "missing == \"1\"", &.{.{ .alias = "a", .value = "1" }}); try expect(outcome.value == null); } test "M1-RULE-015: string equality is exact and case-sensitive" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); try expectEqual(@as(?bool, true), (try run(&arena, "a == \"DE23\"", &.{ .{ .alias = "a", .value = "DE23" }, })).value); try expectEqual(@as(?bool, false), (try run(&arena, "a == \"DE23\"", &.{ .{ .alias = "a", .value = "de23" }, })).value); try expectEqual(@as(?bool, true), (try run(&arena, "a != \"DE23\"", &.{ .{ .alias = "a", .value = "de23" }, })).value); } test "M1-RULE-016: numeric comparison uses exact decimal values" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const row: []const Field = &.{.{ .alias = "amount", .value = "100.00" }}; try expectEqual(@as(?bool, true), (try run(&arena, "amount == 100", row)).value); try expectEqual(@as(?bool, true), (try run(&arena, "amount >= 100", row)).value); try expectEqual(@as(?bool, true), (try run(&arena, "amount <= 100", row)).value); try expectEqual(@as(?bool, false), (try run(&arena, "amount > 100", row)).value); try expectEqual(@as(?bool, false), (try run(&arena, "amount < 100", row)).value); try expectEqual(@as(?bool, false), (try run(&arena, "amount != 100", row)).value); } test "M1-AC-011: cell 100,0 matches literal 100.00 under a comma separator" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const program = try programOf(&arena, "amount == 100.00", .comma); const outcome = program.evaluate(rowOf(&.{.{ .alias = "amount", .value = "100,0" }})); try expectEqual(@as(?bool, true), outcome.value); } const ac011 = "account == \"DE23\" or amount >= 100 and not posting ~= /refund/i"; test "M1-AC-011: DE23 with an unparseable amount still matches by short-circuit" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const outcome = try run(&arena, ac011, &.{ .{ .alias = "account", .value = "DE23" }, .{ .alias = "amount", .value = "N/A" }, .{ .alias = "posting", .value = "REFUND" }, }); try expectEqual(@as(?bool, true), outcome.value); try expect(outcome.failure == null); } test "M1-AC-011: a card refund at 100.00 does not match" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const outcome = try run(&arena, ac011, &.{ .{ .alias = "account", .value = "DE24" }, .{ .alias = "amount", .value = "100.00" }, .{ .alias = "posting", .value = "card refund" }, }); try expectEqual(@as(?bool, false), outcome.value); } test "M1-AC-011: a market purchase at 100.00 matches" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const outcome = try run(&arena, ac011, &.{ .{ .alias = "account", .value = "DE24" }, .{ .alias = "amount", .value = "100.00" }, .{ .alias = "posting", .value = "market" }, }); try expectEqual(@as(?bool, true), outcome.value); } test "M1-AC-011: lowercase de23 at 99 does not match" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const outcome = try run(&arena, ac011, &.{ .{ .alias = "account", .value = "de23" }, .{ .alias = "amount", .value = "99" }, .{ .alias = "posting", .value = "market" }, }); try expectEqual(@as(?bool, false), outcome.value); } test "M1-AC-012: a reached amount >= 100 against N/A reports the conversion error" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const outcome = try run(&arena, "amount >= 100", &.{ .{ .alias = "amount", .value = "N/A" }, }); try expect(outcome.value == null); try expectEqualStrings("amount", outcome.failure.?.field); try expectEqualStrings("N/A", outcome.failure.?.cell); } test "M1-RULE-017: the regex operator searches the cell unanchored" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); try expectEqual(@as(?bool, true), (try run(&arena, "p ~= /refund/i", &.{ .{ .alias = "p", .value = "card REFUND now" }, })).value); try expectEqual(@as(?bool, false), (try run(&arena, "p ~= /refund/", &.{ .{ .alias = "p", .value = "card REFUND now" }, })).value); } test "M1-SAFE-001: the same row and program evaluate the same way twice" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const program = try programOf(&arena, ac011, .dot); const row = rowOf(&.{ .{ .alias = "account", .value = "DE24" }, .{ .alias = "amount", .value = "100.00" }, .{ .alias = "posting", .value = "market" }, }); try expectEqual(program.evaluate(row).value, program.evaluate(row).value); }