lib/markdown/src/table.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 /// Sixteen columns cover dense comparison tables without unbounded descriptors.
4 pub const max_columns: usize = 16;
5
6 /// Sixty-four header and body rows cap one table at 1,024 cell ranges.
7 pub const max_rows: usize = 64;
8
9 pub const max_cells: usize = max_columns * max_rows;
10
11 pub const Alignment = enum {
12 none,
13 left,
14 center,
15 right,
16 };
17
18 pub const SourceRange = struct {
19 start: usize,
20 end: usize,
21
22 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 };
28
29 /// One cell contains a borrowed inline Markdown source range.
30 pub const Cell = struct {
31 source: SourceRange,
32 };
33
34 pub const Row = struct {
35 source: SourceRange,
36 cells: []const Cell,
37 };
38
39 pub const Delimiter = struct {
40 source: SourceRange,
41 alignments: []const Alignment,
42 };
43
44 pub const Table = struct {
45 source: SourceRange,
46 header: Row,
47 delimiter: Delimiter,
48 body: []const Row,
49 };
50
51 /// Callers own this fixed parser storage and retain it while using a table.
52 /// Over-limit candidates reject before rendering and remain paragraphs.
53 pub const Storage = struct {
54 rows: [max_rows]Row = undefined,
55 cells: [max_cells]Cell = undefined,
56 alignments: [max_columns]Alignment = undefined,
57 };
58
59 pub const Rejection = enum {
60 columns,
61 rows,
62 };
63
64 pub const Result = union(enum) {
65 paragraph,
66 rejected: Rejection,
67 table: Table,
68 };
69
70 const Line = struct {
71 content: SourceRange,
72 next: usize,
73 };
74
75 const RowInfo = struct {
76 cells: usize,
77 has_pipe: bool,
78 };
79
80 const DelimiterInfo = struct {
81 cells: usize,
82 has_pipe: bool,
83 valid: bool,
84 };
85
86 pub 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 or
94 delimiter_info.cells != header_info.cells)
95 {
96 return .paragraph;
97 }
98 if (header_info.cells > max_columns) return .{ .rejected = .columns };
99
100 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 };
107
108 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 }
139
140 const RowScanner = struct {
141 source: []const u8,
142 start: usize,
143 end: usize,
144 cursor: usize,
145 has_pipe: bool,
146 done: bool = false,
147
148 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] == '|' and
158 !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 }
171
172 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 };
191
192 fn 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 }
208
209 fn 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 }
239
240 fn 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 }
258
259 fn 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 - 1
268 else
269 raw_end;
270 std.debug.assert(start <= end);
271 std.debug.assert(end <= cursor.*);
272 return .{ .content = .{ .start = start, .end = end }, .next = cursor.* };
273 }
274
275 fn 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 }
284
285 fn 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 }
296
297 fn expectTable(result: Result) !Table {
298 return switch (result) {
299 .table => |table| table,
300 .paragraph, .rejected => error.ExpectedTable,
301 };
302 }
303
304 test "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));
312
313 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 }
327
328 test "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));
335
336 try std.testing.expectEqualSlices(
337 Alignment,
338 &.{ .none, .left, .center, .right },
339 table.delimiter.alignments,
340 );
341 }
342
343 test "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 }
354
355 fn 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 }
369
370 test "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 = .{};
375
376 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);
381
382 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 }
388
389 test "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 = .{};
394
395 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);
400
401 try appendRow(allocator, &source, 2, "overflow");
402 const rejected = parse(&storage, source.items);
403 try std.testing.expectEqual(Result{ .rejected = .rows }, rejected);
404 }