tiny.markdown.table

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

1const std = @import("std");23/// Sixteen columns cover dense comparison tables without unbounded descriptors.4pub const max_columns: usize = 16;56/// Sixty-four header and body rows cap one table at 1,024 cell ranges.7pub const max_rows: usize = 64;89pub const max_cells: usize = max_columns * max_rows;1011pub const Alignment = enum {12    none,13    left,14    center,15    right,16};1718pub const SourceRange = struct {19    start: usize,20    end: usize,2122    pub fn bytes(self: SourceRange, source: []const u8) []const u8 {23        std.debug.assert(self.start <= self.end);24        std.debug.assert(self.end <= source.len);25        return source[self.start..self.end];26    }27};2829/// One cell contains a borrowed inline Markdown source range.30pub const Cell = struct {31    source: SourceRange,32};3334pub const Row = struct {35    source: SourceRange,36    cells: []const Cell,37};3839pub const Delimiter = struct {40    source: SourceRange,41    alignments: []const Alignment,42};4344pub const Table = struct {45    source: SourceRange,46    header: Row,47    delimiter: Delimiter,48    body: []const Row,49};5051/// Callers own this fixed parser storage and retain it while using a table.52/// Over-limit candidates reject before rendering and remain paragraphs.53pub const Storage = struct {54    rows: [max_rows]Row = undefined,55    cells: [max_cells]Cell = undefined,56    alignments: [max_columns]Alignment = undefined,57};5859pub const Rejection = enum {60    columns,61    rows,62};6364pub const Result = union(enum) {65    paragraph,66    rejected: Rejection,67    table: Table,68};6970const Line = struct {71    content: SourceRange,72    next: usize,73};7475const RowInfo = struct {76    cells: usize,77    has_pipe: bool,78};7980const DelimiterInfo = struct {81    cells: usize,82    has_pipe: bool,83    valid: bool,84};8586pub fn parse(storage: *Storage, source: []const u8) Result {87    var cursor: usize = 0;88    const header_line = nextLine(source, &cursor) orelse return .paragraph;89    const delimiter_line = nextLine(source, &cursor) orelse return .paragraph;90    const header_info = scanRow(source, header_line.content, null);91    if (!header_info.has_pipe or header_info.cells == 0) return .paragraph;92    const delimiter_info = scanDelimiter(source, delimiter_line.content, null);93    if (!delimiter_info.has_pipe or !delimiter_info.valid or94        delimiter_info.cells != header_info.cells)95    {96        return .paragraph;97    }98    if (header_info.cells > max_columns) return .{ .rejected = .columns };99100    const columns = header_info.cells;101    _ = scanRow(source, header_line.content, storage.cells[0..columns]);102    _ = scanDelimiter(source, delimiter_line.content, storage.alignments[0..columns]);103    storage.rows[0] = .{104        .source = header_line.content,105        .cells = storage.cells[0..columns],106    };107108    var row_count: usize = 1;109    var cell_count = columns;110    var table_end = delimiter_line.next;111    while (nextLine(source, &cursor)) |line| {112        const trimmed = trimRange(source, line.content);113        if (trimmed.start == trimmed.end) break;114        const info = scanRow(source, line.content, null);115        if (!info.has_pipe) break;116        if (info.cells > max_columns) return .{ .rejected = .columns };117        if (info.cells != columns) return .paragraph;118        if (row_count == max_rows) return .{ .rejected = .rows };119        std.debug.assert(cell_count <= max_cells - columns);120        const cells = storage.cells[cell_count..][0..columns];121        _ = scanRow(source, line.content, cells);122        storage.rows[row_count] = .{ .source = line.content, .cells = cells };123        row_count += 1;124        cell_count += columns;125        table_end = line.next;126    }127    std.debug.assert(row_count <= max_rows);128    std.debug.assert(cell_count == row_count * columns);129    return .{ .table = .{130        .source = .{ .start = 0, .end = table_end },131        .header = storage.rows[0],132        .delimiter = .{133            .source = delimiter_line.content,134            .alignments = storage.alignments[0..columns],135        },136        .body = storage.rows[1..row_count],137    } };138}139140const RowScanner = struct {141    source: []const u8,142    start: usize,143    end: usize,144    cursor: usize,145    has_pipe: bool,146    done: bool = false,147148    fn init(source: []const u8, line: SourceRange) RowScanner {149        std.debug.assert(line.start <= line.end);150        std.debug.assert(line.end <= source.len);151        var content = trimRange(source, line);152        var has_pipe = false;153        if (content.start < content.end and source[content.start] == '|') {154            content.start += 1;155            has_pipe = true;156        }157        if (content.start < content.end and source[content.end - 1] == '|' and158            !escapedPipe(source, content.end - 1, content.start))159        {160            content.end -= 1;161            has_pipe = true;162        }163        return .{164            .source = source,165            .start = content.start,166            .end = content.end,167            .cursor = content.start,168            .has_pipe = has_pipe,169        };170    }171172    fn next(self: *RowScanner) ?SourceRange {173        std.debug.assert(self.start <= self.cursor);174        std.debug.assert(self.cursor <= self.end);175        std.debug.assert(self.end <= self.source.len);176        if (self.done) return null;177        const cell_start = self.cursor;178        var index = self.cursor;179        while (index < self.end) : (index += 1) {180            if (self.source[index] != '|') continue;181            if (escapedPipe(self.source, index, self.start)) continue;182            self.has_pipe = true;183            self.cursor = index + 1;184            return trimRange(self.source, .{ .start = cell_start, .end = index });185        }186        self.done = true;187        self.cursor = self.end;188        return trimRange(self.source, .{ .start = cell_start, .end = self.end });189    }190};191192fn scanRow(source: []const u8, line: SourceRange, output: ?[]Cell) RowInfo {193    std.debug.assert(line.start <= line.end);194    std.debug.assert(line.end <= source.len);195    if (output) |cells| std.debug.assert(cells.len <= max_columns);196    var scanner = RowScanner.init(source, line);197    var count: usize = 0;198    while (scanner.next()) |inline_source| {199        if (output) |cells| {200            std.debug.assert(count < cells.len);201            cells[count] = .{ .source = inline_source };202        }203        count += 1;204    }205    if (output) |cells| std.debug.assert(count == cells.len);206    return .{ .cells = count, .has_pipe = scanner.has_pipe };207}208209fn scanDelimiter(210    source: []const u8,211    line: SourceRange,212    output: ?[]Alignment,213) DelimiterInfo {214    std.debug.assert(line.start <= line.end);215    std.debug.assert(line.end <= source.len);216    if (output) |alignments| std.debug.assert(alignments.len <= max_columns);217    var scanner = RowScanner.init(source, line);218    var count: usize = 0;219    var valid = true;220    while (scanner.next()) |cell| {221        const alignment = parseAlignment(source, cell) orelse {222            valid = false;223            count += 1;224            continue;225        };226        if (output) |alignments| {227            std.debug.assert(count < alignments.len);228            alignments[count] = alignment;229        }230        count += 1;231    }232    if (output) |alignments| std.debug.assert(count == alignments.len);233    return .{234        .cells = count,235        .has_pipe = scanner.has_pipe,236        .valid = valid,237    };238}239240fn parseAlignment(source: []const u8, range: SourceRange) ?Alignment {241    std.debug.assert(range.start <= range.end);242    std.debug.assert(range.end <= source.len);243    var start = range.start;244    var end = range.end;245    const left = start < end and source[start] == ':';246    if (left) start += 1;247    const right = start < end and source[end - 1] == ':';248    if (right) end -= 1;249    if (end - start < 3) return null;250    for (source[start..end]) |byte| {251        if (byte != '-') return null;252    }253    if (left and right) return .center;254    if (left) return .left;255    if (right) return .right;256    return .none;257}258259fn nextLine(source: []const u8, cursor: *usize) ?Line {260    std.debug.assert(cursor.* <= source.len);261    if (cursor.* >= source.len) return null;262    const start = cursor.*;263    const newline = std.mem.indexOfScalarPos(u8, source, start, '\n');264    const raw_end = newline orelse source.len;265    cursor.* = if (newline != null) raw_end + 1 else raw_end;266    const end = if (raw_end > start and source[raw_end - 1] == '\r')267        raw_end - 1268    else269        raw_end;270    std.debug.assert(start <= end);271    std.debug.assert(end <= cursor.*);272    return .{ .content = .{ .start = start, .end = end }, .next = cursor.* };273}274275fn trimRange(source: []const u8, range: SourceRange) SourceRange {276    std.debug.assert(range.start <= range.end);277    std.debug.assert(range.end <= source.len);278    var start = range.start;279    var end = range.end;280    while (start < end and (source[start] == ' ' or source[start] == '\t')) start += 1;281    while (end > start and (source[end - 1] == ' ' or source[end - 1] == '\t')) end -= 1;282    return .{ .start = start, .end = end };283}284285fn escapedPipe(source: []const u8, pipe: usize, lower: usize) bool {286    std.debug.assert(lower <= pipe);287    std.debug.assert(pipe < source.len);288    var slash_count: usize = 0;289    var cursor = pipe;290    while (cursor > lower and source[cursor - 1] == '\\') {291        slash_count += 1;292        cursor -= 1;293    }294    return slash_count % 2 == 1;295}296297fn expectTable(result: Result) !Table {298    return switch (result) {299        .table => |table| table,300        .paragraph, .rejected => error.ExpectedTable,301    };302}303304test "pipe table classifies header delimiter body and inline source" {305    const source =306        "| Name | Detail |\n" ++307        "| --- | --- |\n" ++308        "| **fast** | [docs](/docs) and `code` |\n" ++309        "\nAfter";310    var storage: Storage = .{};311    const table = try expectTable(parse(&storage, source));312313    try std.testing.expectEqual(@as(usize, 2), table.header.cells.len);314    try std.testing.expectEqualStrings("Name", table.header.cells[0].source.bytes(source));315    try std.testing.expectEqualStrings("| --- | --- |", table.delimiter.source.bytes(source));316    try std.testing.expectEqual(@as(usize, 1), table.body.len);317    try std.testing.expectEqualStrings("**fast**", table.body[0].cells[0].source.bytes(source));318    try std.testing.expectEqualStrings(319        "[docs](/docs) and `code`",320        table.body[0].cells[1].source.bytes(source),321    );322    try std.testing.expectEqualStrings(323        source[0..table.source.end],324        table.source.bytes(source),325    );326}327328test "pipe table classifies delimiter alignment colons" {329    const source =330        "| Default | Left | Center | Right |\n" ++331        "| --- | :--- | :---: | ---: |\n" ++332        "| a | b | c | d |\n";333    var storage: Storage = .{};334    const table = try expectTable(parse(&storage, source));335336    try std.testing.expectEqualSlices(337        Alignment,338        &.{ .none, .left, .center, .right },339        table.delimiter.alignments,340    );341}342343test "pipe table keeps degenerate candidates as paragraphs" {344    var storage: Storage = .{};345    const lone = parse(&storage, "| lone |\n");346    try std.testing.expectEqual(.paragraph, std.meta.activeTag(lone));347    const delimiter_first = parse(&storage, "| --- | --- |\n| a | b |\n");348    try std.testing.expectEqual(.paragraph, std.meta.activeTag(delimiter_first));349    const malformed = parse(&storage, "| a | b |\n| -- | --- |\n");350    try std.testing.expectEqual(.paragraph, std.meta.activeTag(malformed));351    const mismatched = parse(&storage, "| a | b |\n| --- | --- |\n| only one |\n");352    try std.testing.expectEqual(.paragraph, std.meta.activeTag(mismatched));353}354355fn appendRow(356    allocator: std.mem.Allocator,357    output: *std.ArrayList(u8),358    columns: usize,359    value: []const u8,360) !void {361    try output.append(allocator, '|');362    for (0..columns) |_| {363        try output.append(allocator, ' ');364        try output.appendSlice(allocator, value);365        try output.appendSlice(allocator, " |");366    }367    try output.append(allocator, '\n');368}369370test "pipe table accepts maximum columns and rejects maximum plus one" {371    const allocator = std.testing.allocator;372    var source: std.ArrayList(u8) = .empty;373    defer source.deinit(allocator);374    var storage: Storage = .{};375376    try appendRow(allocator, &source, max_columns, "head");377    try appendRow(allocator, &source, max_columns, "---");378    try appendRow(allocator, &source, max_columns, "body");379    const table = try expectTable(parse(&storage, source.items));380    try std.testing.expectEqual(max_columns, table.header.cells.len);381382    source.clearRetainingCapacity();383    try appendRow(allocator, &source, max_columns + 1, "head");384    try appendRow(allocator, &source, max_columns + 1, "---");385    const rejected = parse(&storage, source.items);386    try std.testing.expectEqual(Result{ .rejected = .columns }, rejected);387}388389test "pipe table accepts maximum rows and rejects maximum plus one" {390    const allocator = std.testing.allocator;391    var source: std.ArrayList(u8) = .empty;392    defer source.deinit(allocator);393    var storage: Storage = .{};394395    try appendRow(allocator, &source, 2, "head");396    try appendRow(allocator, &source, 2, "---");397    for (0..max_rows - 1) |_| try appendRow(allocator, &source, 2, "body");398    const table = try expectTable(parse(&storage, source.items));399    try std.testing.expectEqual(max_rows - 1, table.body.len);400401    try appendRow(allocator, &source, 2, "overflow");402    const rejected = parse(&storage, source.items);403    try std.testing.expectEqual(Result{ .rejected = .rows }, rejected);404}