tiny.zen.math.parse

1const std = @import("std");2const token = @import("token.zig");3const symbol = @import("symbol.zig");45const Allocator = std.mem.Allocator;67pub const Error = error{ InvalidEquation, OutOfMemory };89pub const Diagnostic = struct {10    reason: []const u8 = "",11    offset: usize = 0,12};1314pub const Ident = struct {15    text: []const u8,16    upright: bool = false,17};1819pub const Operator = struct {20    text: []const u8,21    stretchy: bool = false,22    rigid: bool = false,23    movable_word: bool = false,24    prefers_limits: bool = false,25};2627pub const Pair = struct {28    first: *Node,29    second: *Node,30};3132pub const Radical = struct {33    index: ?*Node,34    radicand: *Node,35};3637pub const Scripts = struct {38    base: *Node,39    sub: ?*Node,40    sup: ?*Node,41    limits: bool,42};4344pub const Accent = struct {45    base: *Node,46    mark: []const u8,47};4849pub const Table = struct {50    rows: []const []Node,51    env: symbol.Environment,52};5354pub const Node = union(enum) {55    row: []Node,56    ident: Ident,57    number: []const u8,58    operator: Operator,59    text: []const u8,60    space: []const u8,61    frac: Pair,62    radical: Radical,63    scripts: Scripts,64    accent: Accent,65    table: Table,66};6768pub const Parsed = struct {69    arena: std.heap.ArenaAllocator,70    root: Node,7172    pub fn deinit(self: *Parsed) void {73        self.arena.deinit();74        self.* = undefined;75    }76};7778pub fn parse(backing: Allocator, source: []const u8, diagnostic: ?*Diagnostic) Error!Parsed {79    var arena = std.heap.ArenaAllocator.init(backing);80    errdefer arena.deinit();81    var parser = Parser{82        .allocator = arena.allocator(),83        .tokens = .{ .source = source },84        .diagnostic = diagnostic,85    };86    const items = try parser.sequence(.end);87    if (items.len == 0) return parser.fail("empty equation", 0);88    return .{ .arena = arena, .root = .{ .row = items } };89}9091const Terminator = enum { end, close, right, bracket };9293const Parser = struct {94    allocator: Allocator,95    tokens: token.Tokenizer,96    diagnostic: ?*Diagnostic,97    pending: ?token.Token = null,9899    const CellEnd = enum { column, row, done };100101    fn fail(self: *Parser, reason: []const u8, offset: usize) error{InvalidEquation} {102        if (self.diagnostic) |d| d.* = .{ .reason = reason, .offset = offset };103        return error.InvalidEquation;104    }105106    fn advance(self: *Parser) Error!token.Token {107        if (self.pending) |tok| {108            self.pending = null;109            return tok;110        }111        return self.tokens.next() catch self.fail(self.tokens.reason, self.tokens.start);112    }113114    fn sequence(self: *Parser, terminator: Terminator) Error![]Node {115        var items: std.ArrayList(Node) = .empty;116        while (true) {117            const tok = try self.advance();118            switch (tok) {119                .end => {120                    if (terminator != .end) return self.fail(switch (terminator) {121                        .close => "missing '}'",122                        .right => "missing '\\right'",123                        .bracket => "missing ']'",124                        .end => unreachable,125                    }, self.tokens.start);126                    return try items.toOwnedSlice(self.allocator);127                },128                .close => {129                    if (terminator != .close) return self.fail("unmatched '}'", self.tokens.start);130                    return try items.toOwnedSlice(self.allocator);131                },132                .caret => try self.attachScript(&items, true),133                .underscore => try self.attachScript(&items, false),134                .prime => try self.attachPrime(&items),135                .open => {136                    const inner = try self.sequence(.close);137                    try items.append(self.allocator, .{ .row = inner });138                },139                .command => |name| {140                    if (std.mem.eql(u8, name, "right")) {141                        if (terminator != .right) return self.fail("unmatched '\\right'", self.tokens.start);142                        return try items.toOwnedSlice(self.allocator);143                    }144                    try items.append(self.allocator, try self.command(name));145                },146                .char => |code| {147                    if (terminator == .bracket and code == ']') return try items.toOwnedSlice(self.allocator);148                    try items.append(self.allocator, try self.charNode(code, true));149                },150            }151        }152    }153154    fn attachScript(self: *Parser, items: *std.ArrayList(Node), is_sup: bool) Error!void {155        const mark = self.tokens.start;156        if (items.items.len == 0) {157            return self.fail(if (is_sup) "superscript without a base" else "subscript without a base", mark);158        }159        const arg = try self.heap(try self.argument());160        const last = &items.items[items.items.len - 1];161        if (last.* == .scripts) {162            const scripts = &last.scripts;163            if (is_sup) {164                if (scripts.sup != null) return self.fail("double superscript", mark);165                scripts.sup = arg;166            } else {167                if (scripts.sub != null) return self.fail("double subscript", mark);168                scripts.sub = arg;169            }170            return;171        }172        const base = try self.heap(last.*);173        last.* = .{ .scripts = .{174            .base = base,175            .sub = if (is_sup) null else arg,176            .sup = if (is_sup) arg else null,177            .limits = prefersLimits(base.*),178        } };179    }180181    fn attachPrime(self: *Parser, items: *std.ArrayList(Node)) Error!void {182        if (items.items.len == 0) return self.fail("prime without a base", self.tokens.start);183        const last = &items.items[items.items.len - 1];184        const base = try self.heap(last.*);185        const mark = try self.heap(Node{ .operator = .{ .text = "′" } });186        last.* = .{ .scripts = .{187            .base = base,188            .sub = null,189            .sup = mark,190            .limits = false,191        } };192    }193194    fn argument(self: *Parser) Error!Node {195        const tok = try self.advance();196        return switch (tok) {197            .open => .{ .row = try self.sequence(.close) },198            .command => |name| try self.command(name),199            .char => |code| try self.charNode(code, false),200            else => self.fail("missing argument", self.tokens.start),201        };202    }203204    fn command(self: *Parser, name: []const u8) Error!Node {205        if (std.mem.eql(u8, name, "begin")) return try self.environment();206        if (std.mem.eql(u8, name, "end")) return self.fail("unmatched '\\end'", self.tokens.start);207        if (std.mem.eql(u8, name, "\\")) return self.fail("misplaced '\\\\'", self.tokens.start);208        if (std.mem.eql(u8, name, "frac")) {209            const numerator = try self.heap(try self.argument());210            const denominator = try self.heap(try self.argument());211            return .{ .frac = .{ .first = numerator, .second = denominator } };212        }213        if (std.mem.eql(u8, name, "sqrt")) {214            const tok = try self.advance();215            if (tok == .char and tok.char == '[') {216                const index = try self.heap(Node{ .row = try self.sequence(.bracket) });217                const radicand = try self.heap(try self.argument());218                return .{ .radical = .{ .index = index, .radicand = radicand } };219            }220            self.pending = tok;221            return .{ .radical = .{ .index = null, .radicand = try self.heap(try self.argument()) } };222        }223        if (std.mem.eql(u8, name, "text")) {224            return .{ .text = try self.allocator.dupe(u8, try self.rawGroup()) };225        }226        if (std.mem.eql(u8, name, "mathrm") or std.mem.eql(u8, name, "operatorname")) {227            return .{ .ident = .{ .text = try self.allocator.dupe(u8, try self.rawGroup()), .upright = true } };228        }229        if (std.mem.eql(u8, name, "mathit")) {230            return .{ .ident = .{ .text = try self.allocator.dupe(u8, try self.rawGroup()), .upright = false } };231        }232        if (std.mem.eql(u8, name, "mathbb")) return try self.styledIdent(.bb);233        if (std.mem.eql(u8, name, "mathcal")) return try self.styledIdent(.cal);234        if (std.mem.eql(u8, name, "mathfrak")) return try self.styledIdent(.frak);235        if (std.mem.eql(u8, name, "mathbf")) return try self.styledIdent(.bf);236        if (std.mem.eql(u8, name, "left")) return try self.leftRight();237        if (symbol.commands.get(name)) |entry| {238            return switch (entry.kind) {239                .identifier => .{ .ident = .{ .text = entry.text, .upright = entry.upright } },240                .function => .{ .ident = .{ .text = entry.text, .upright = true } },241                .operator => .{ .operator = .{ .text = entry.text } },242                .fence => .{ .operator = .{ .text = entry.text, .rigid = true } },243                .largeop => .{ .operator = .{ .text = entry.text, .prefers_limits = true } },244                .integral => .{ .operator = .{ .text = entry.text } },245                .movableop => .{ .operator = .{246                    .text = entry.text,247                    .movable_word = true,248                    .prefers_limits = true,249                } },250                .space => .{ .space = entry.text },251                .accent => .{ .accent = .{252                    .base = try self.heap(try self.argument()),253                    .mark = entry.text,254                } },255            };256        }257        return self.fail("unknown command", self.tokens.start);258    }259260    fn environment(self: *Parser) Error!Node {261        const name = try self.rawGroup();262        const name_offset = @intFromPtr(name.ptr) - @intFromPtr(self.tokens.source.ptr);263        const env = symbol.environments.get(name) orelse return self.fail("unknown environment", name_offset);264        var rows: std.ArrayList([]Node) = .empty;265        var cells: std.ArrayList(Node) = .empty;266        while (true) {267            const parsed = try self.cell(name);268            try cells.append(self.allocator, .{ .row = parsed.items });269            switch (parsed.end) {270                .column => continue,271                .row => try rows.append(self.allocator, try cells.toOwnedSlice(self.allocator)),272                .done => {273                    try rows.append(self.allocator, try cells.toOwnedSlice(self.allocator));274                    break;275                },276            }277        }278        const last = rows.items[rows.items.len - 1];279        if (rows.items.len > 1 and last.len == 1 and last[0].row.len == 0) rows.items.len -= 1;280        return .{ .table = .{ .rows = try rows.toOwnedSlice(self.allocator), .env = env } };281    }282283    fn cell(self: *Parser, env_name: []const u8) Error!struct { items: []Node, end: CellEnd } {284        var items: std.ArrayList(Node) = .empty;285        while (true) {286            const tok = try self.advance();287            switch (tok) {288                .end => return self.fail("missing '\\end'", self.tokens.start),289                .close => return self.fail("unmatched '}'", self.tokens.start),290                .caret => try self.attachScript(&items, true),291                .underscore => try self.attachScript(&items, false),292                .prime => try self.attachPrime(&items),293                .open => {294                    const inner = try self.sequence(.close);295                    try items.append(self.allocator, .{ .row = inner });296                },297                .command => |name| {298                    if (std.mem.eql(u8, name, "\\")) {299                        return .{ .items = try items.toOwnedSlice(self.allocator), .end = .row };300                    }301                    if (std.mem.eql(u8, name, "end")) {302                        const mark = self.tokens.start;303                        const found = try self.rawGroup();304                        if (!std.mem.eql(u8, found, env_name)) return self.fail("mismatched '\\end'", mark);305                        return .{ .items = try items.toOwnedSlice(self.allocator), .end = .done };306                    }307                    if (std.mem.eql(u8, name, "right")) return self.fail("unmatched '\\right'", self.tokens.start);308                    try items.append(self.allocator, try self.command(name));309                },310                .char => |code| {311                    if (code == '&') {312                        return .{ .items = try items.toOwnedSlice(self.allocator), .end = .column };313                    }314                    try items.append(self.allocator, try self.charNode(code, true));315                },316            }317        }318    }319320    fn leftRight(self: *Parser) Error!Node {321        const open_text = try self.fenceText();322        const inner = try self.sequence(.right);323        const close_text = try self.fenceText();324        var items: std.ArrayList(Node) = .empty;325        if (open_text) |text| {326            try items.append(self.allocator, .{ .operator = .{ .text = text, .stretchy = true } });327        }328        try items.appendSlice(self.allocator, inner);329        if (close_text) |text| {330            try items.append(self.allocator, .{ .operator = .{ .text = text, .stretchy = true } });331        }332        return .{ .row = try items.toOwnedSlice(self.allocator) };333    }334335    fn fenceText(self: *Parser) Error!?[]const u8 {336        const tok = try self.advance();337        switch (tok) {338            .char => |code| return switch (code) {339                '(' => "(",340                ')' => ")",341                '[' => "[",342                ']' => "]",343                '|' => "|",344                '/' => "/",345                '.' => null,346                else => self.fail("invalid delimiter", self.tokens.start),347            },348            .command => |name| {349                if (symbol.commands.get(name)) |entry| {350                    if (entry.kind == .fence) return entry.text;351                }352                return self.fail("invalid delimiter", self.tokens.start);353            },354            .end => return self.fail("missing delimiter", self.tokens.start),355            else => return self.fail("invalid delimiter", self.tokens.start),356        }357    }358359    fn styledIdent(self: *Parser, style: symbol.Style) Error!Node {360        const raw = try self.rawGroup();361        const base = @intFromPtr(raw.ptr) - @intFromPtr(self.tokens.source.ptr);362        var buffer: std.ArrayList(u8) = .empty;363        for (raw, 0..) |char, index| {364            if (char == ' ' or char == '\t') continue;365            const code = symbol.styled(style, char) orelse return self.fail("unsupported styled letter", base + index);366            var encoded: [4]u8 = undefined;367            const length = std.unicode.utf8Encode(code, &encoded) catch return self.fail("unsupported styled letter", base + index);368            try buffer.appendSlice(self.allocator, encoded[0..length]);369        }370        if (buffer.items.len == 0) return self.fail("empty argument", base);371        return .{ .ident = .{ .text = try buffer.toOwnedSlice(self.allocator) } };372    }373374    fn rawGroup(self: *Parser) Error![]const u8 {375        const source = self.tokens.source;376        var index = self.tokens.index;377        while (index < source.len and (source[index] == ' ' or source[index] == '\t')) index += 1;378        if (index >= source.len or source[index] != '{') return self.fail("expected '{'", index);379        index += 1;380        const start = index;381        var depth: usize = 1;382        while (index < source.len) : (index += 1) {383            if (source[index] == '{') depth += 1;384            if (source[index] == '}') {385                depth -= 1;386                if (depth == 0) break;387            }388        }389        if (depth != 0) return self.fail("missing '}'", source.len);390        self.tokens.index = index + 1;391        return source[start..index];392    }393394    fn charNode(self: *Parser, code: u21, run_numbers: bool) Error!Node {395        if (code < 0x80) {396            const byte: u8 = @intCast(code);397            if (std.ascii.isAlphabetic(byte)) {398                return .{ .ident = .{ .text = try self.allocator.dupe(u8, &.{byte}) } };399            }400            if (std.ascii.isDigit(byte)) {401                if (run_numbers) return try self.numberNode(byte);402                return .{ .number = try self.allocator.dupe(u8, &.{byte}) };403            }404            return switch (byte) {405                '+' => .{ .operator = .{ .text = "+" } },406                '-' => .{ .operator = .{ .text = "−" } },407                '*' => .{ .operator = .{ .text = "∗" } },408                '=' => .{ .operator = .{ .text = "=" } },409                '<' => .{ .operator = .{ .text = "<" } },410                '>' => .{ .operator = .{ .text = ">" } },411                '(' => .{ .operator = .{ .text = "(", .rigid = true } },412                ')' => .{ .operator = .{ .text = ")", .rigid = true } },413                '[' => .{ .operator = .{ .text = "[", .rigid = true } },414                ']' => .{ .operator = .{ .text = "]", .rigid = true } },415                '|' => .{ .operator = .{ .text = "|", .rigid = true } },416                '/' => .{ .operator = .{ .text = "/", .rigid = true } },417                ',' => .{ .operator = .{ .text = "," } },418                ';' => .{ .operator = .{ .text = ";" } },419                ':' => .{ .operator = .{ .text = ":" } },420                '!' => .{ .operator = .{ .text = "!" } },421                '?' => .{ .operator = .{ .text = "?" } },422                '.' => try self.dotNode(run_numbers),423                '&' => self.fail("misplaced '&'", self.tokens.start),424                else => self.fail("unsupported character", self.tokens.start),425            };426        }427        var encoded: [4]u8 = undefined;428        const length = std.unicode.utf8Encode(code, &encoded) catch return self.fail("unsupported character", self.tokens.start);429        return .{ .ident = .{ .text = try self.allocator.dupe(u8, encoded[0..length]) } };430    }431432    fn dotNode(self: *Parser, run_numbers: bool) Error!Node {433        const source = self.tokens.source;434        if (run_numbers and self.tokens.index < source.len and std.ascii.isDigit(source[self.tokens.index])) {435            return try self.numberNode('.');436        }437        return .{ .operator = .{ .text = "." } };438    }439440    fn numberNode(self: *Parser, first: u8) Error!Node {441        var buffer: std.ArrayList(u8) = .empty;442        try buffer.append(self.allocator, first);443        const source = self.tokens.source;444        while (self.tokens.index < source.len) {445            const byte = source[self.tokens.index];446            if (std.ascii.isDigit(byte)) {447                try buffer.append(self.allocator, byte);448                self.tokens.index += 1;449                continue;450            }451            if (byte == '.' and self.tokens.index + 1 < source.len and std.ascii.isDigit(source[self.tokens.index + 1])) {452                try buffer.append(self.allocator, '.');453                self.tokens.index += 1;454                continue;455            }456            break;457        }458        return .{ .number = try buffer.toOwnedSlice(self.allocator) };459    }460461    fn heap(self: *Parser, node: Node) Error!*Node {462        const slot = try self.allocator.create(Node);463        slot.* = node;464        return slot;465    }466};467468fn prefersLimits(node: Node) bool {469    return node == .operator and node.operator.prefers_limits;470}471472fn expectInvalid(source: []const u8, reason: []const u8, offset: usize) !void {473    var diagnostic: Diagnostic = .{};474    try std.testing.expectError(error.InvalidEquation, parse(std.testing.allocator, source, &diagnostic));475    try std.testing.expectEqualStrings(reason, diagnostic.reason);476    try std.testing.expectEqual(offset, diagnostic.offset);477}478479test "parse builds scripts around a shared base" {480    var parsed = try parse(std.testing.allocator, "x_i^2", null);481    defer parsed.deinit();482    const items = parsed.root.row;483    try std.testing.expectEqual(@as(usize, 1), items.len);484    const scripts = items[0].scripts;485    try std.testing.expectEqualStrings("x", scripts.base.ident.text);486    try std.testing.expectEqualStrings("i", scripts.sub.?.ident.text);487    try std.testing.expectEqualStrings("2", scripts.sup.?.number);488    try std.testing.expect(!scripts.limits);489}490491test "parse marks sum scripts as limit placed" {492    var parsed = try parse(std.testing.allocator, "\\sum_{i}^{n}", null);493    defer parsed.deinit();494    const scripts = parsed.root.row[0].scripts;495    try std.testing.expect(scripts.limits);496    try std.testing.expectEqualStrings("∑", scripts.base.operator.text);497}498499test "parse reads numbers fractions radicals and styled letters" {500    var parsed = try parse(std.testing.allocator, "\\frac{3.14}{\\sqrt[3]{x}} \\mathbb{R}", null);501    defer parsed.deinit();502    const items = parsed.root.row;503    try std.testing.expectEqual(@as(usize, 2), items.len);504    try std.testing.expectEqualStrings("3.14", items[0].frac.first.row[0].number);505    const radical = items[0].frac.second.row[0].radical;506    try std.testing.expectEqualStrings("3", radical.index.?.row[0].number);507    try std.testing.expectEqualStrings("x", radical.radicand.row[0].ident.text);508    try std.testing.expectEqualStrings("ℝ", items[1].ident.text);509}510511test "parse builds environment rows and cells" {512    var parsed = try parse(std.testing.allocator, "\\begin{pmatrix} a & b \\\\ c & d \\end{pmatrix}", null);513    defer parsed.deinit();514    const table = parsed.root.row[0].table;515    try std.testing.expectEqualStrings("(", table.env.open.?);516    try std.testing.expectEqualStrings(")", table.env.close.?);517    try std.testing.expectEqual(@as(usize, 2), table.rows.len);518    try std.testing.expectEqual(@as(usize, 2), table.rows[0].len);519    try std.testing.expectEqualStrings("a", table.rows[0][0].row[0].ident.text);520    try std.testing.expectEqualStrings("d", table.rows[1][1].row[0].ident.text);521}522523test "parse drops a trailing empty environment row" {524    var parsed = try parse(std.testing.allocator, "\\begin{cases} x & y \\\\ \\end{cases}", null);525    defer parsed.deinit();526    const table = parsed.root.row[0].table;527    try std.testing.expectEqual(@as(usize, 1), table.rows.len);528    try std.testing.expectEqual(@as(usize, 2), table.rows[0].len);529}530531test "parse keeps empty cells and nests environments" {532    var parsed = try parse(std.testing.allocator, "\\begin{matrix} & \\begin{pmatrix} 1 \\end{pmatrix} \\end{matrix}", null);533    defer parsed.deinit();534    const table = parsed.root.row[0].table;535    try std.testing.expectEqual(@as(usize, 1), table.rows.len);536    try std.testing.expectEqual(@as(usize, 2), table.rows[0].len);537    try std.testing.expectEqual(@as(usize, 0), table.rows[0][0].row.len);538    const inner = table.rows[0][1].row[0].table;539    try std.testing.expectEqualStrings("1", inner.rows[0][0].row[0].number);540}541542test "parse rejects malformed input" {543    try std.testing.expectError(error.InvalidEquation, parse(std.testing.allocator, "", null));544    try std.testing.expectError(error.InvalidEquation, parse(std.testing.allocator, "{x", null));545    try std.testing.expectError(error.InvalidEquation, parse(std.testing.allocator, "^2", null));546    try std.testing.expectError(error.InvalidEquation, parse(std.testing.allocator, "x^2^3", null));547    try std.testing.expectError(error.InvalidEquation, parse(std.testing.allocator, "\\nonesuch", null));548    try std.testing.expectError(error.InvalidEquation, parse(std.testing.allocator, "\\left( x", null));549    try std.testing.expectError(error.InvalidEquation, parse(std.testing.allocator, "\\frac{1}", null));550}551552test "parse names the offending span" {553    try expectInvalid("", "empty equation", 0);554    try expectInvalid("{x", "missing '}'", 2);555    try expectInvalid("}", "unmatched '}'", 0);556    try expectInvalid("^2", "superscript without a base", 0);557    try expectInvalid("x_2_3", "double subscript", 3);558    try expectInvalid("x^2^3", "double superscript", 3);559    try expectInvalid("'", "prime without a base", 0);560    try expectInvalid("\\nonesuch", "unknown command", 0);561    try expectInvalid("\\left( x", "missing '\\right'", 8);562    try expectInvalid("x \\right)", "unmatched '\\right'", 2);563    try expectInvalid("\\left? x \\right)", "invalid delimiter", 5);564    try expectInvalid("\\frac{1}", "missing argument", 8);565    try expectInvalid("\\text x", "expected '{'", 6);566    try expectInvalid("\\mathrm{oops", "missing '}'", 12);567    try expectInvalid("\\mathbb{Ω}", "unsupported styled letter", 8);568    try expectInvalid("\\mathbb{}", "empty argument", 8);569    try expectInvalid("\\sqrt[3{x}", "missing ']'", 10);570    try expectInvalid("x#y", "unsupported character", 1);571    try expectInvalid("x\\", "incomplete command", 1);572}573574test "parse names the offending environment span" {575    try expectInvalid("\\begin pmatrix", "expected '{'", 7);576    try expectInvalid("\\begin{nonesuch} x \\end{nonesuch}", "unknown environment", 7);577    try expectInvalid("\\begin{pmatrix} 1", "missing '\\end'", 17);578    try expectInvalid("\\begin{pmatrix} 1 \\end{cases}", "mismatched '\\end'", 18);579    try expectInvalid("x \\end{pmatrix}", "unmatched '\\end'", 2);580    try expectInvalid("a & b", "misplaced '&'", 2);581    try expectInvalid("a \\\\ b", "misplaced '\\\\'", 2);582    try expectInvalid("\\begin{matrix} {a & b} \\end{matrix}", "misplaced '&'", 18);583    try expectInvalid("\\begin{matrix} \\left( a & b \\right) \\end{matrix}", "misplaced '&'", 24);584}

1pub const parse = @import("parse.zig");