Meg's Mirrors

zig

1	//! A Markdown parser producing `Document`s.
2	//!
3	//! The parser operates at two levels: at the outer level, the parser accepts
4	//! the content of an input document line by line and begins building the _block
5	//! structure_ of the document. This creates a stack of currently open blocks.
6	//!
7	//! When the parser detects the end of a block, it closes the block, popping it
8	//! from the open block stack and completing any additional parsing of the
9	//! block's content. For blocks which contain parseable inline content, this
10	//! invokes the inner level of the parser, handling the _inline structure_ of
11	//! the block.
12	//!
13	//! Inline parsing scans through the collected inline content of a block. When
14	//! it encounters a character that could indicate the beginning of an inline, it
15	//! either handles the inline right away (if possible) or adds it to a pending
16	//! inlines stack. When an inline is completed, it is added to a list of
17	//! completed inlines, which (along with any surrounding text nodes) will become
18	//! the children of the parent inline or the block whose inline content is being
19	//! parsed.
20
21	const std = @import("std");
22	const mem = std.mem;
23	const assert = std.debug.assert;
24	const isWhitespace = std.ascii.isWhitespace;
25	const Allocator = mem.Allocator;
26	const expectEqual = std.testing.expectEqual;
27	const Document = @import("Document.zig");
28	const Node = Document.Node;
29	const ExtraIndex = Document.ExtraIndex;
30	const ExtraData = Document.ExtraData;
31	const StringIndex = Document.StringIndex;
32	const ArrayList = std.ArrayList;
33
34	nodes: Node.List = .{},
35	extra: ArrayList(u32) = .empty,
36	scratch_extra: ArrayList(u32) = .empty,
37	string_bytes: ArrayList(u8) = .empty,
38	scratch_string: ArrayList(u8) = .empty,
39	pending_blocks: ArrayList(Block) = .empty,
40	allocator: Allocator,
41
42	const Parser = @This();
43
44	/// An arbitrary limit on the maximum number of columns in a table so that
45	/// table-related metadata maintained by the parser does not require dynamic
46	/// memory allocation.
47	const max_table_columns = 128;
48
49	/// A block element which is still receiving children.
50	const Block = struct {
51	tag: Tag,
52	data: Data,
53	extra_start: usize,
54	string_start: usize,
55
56	const Tag = enum {
57	/// Data is `list`.
58	list,
59	/// Data is `list_item`.
60	list_item,
61	/// Data is `table`.
62	table,
63	/// Data is `none`.
64	table_row,
65	/// Data is `heading`.
66	heading,
67	/// Data is `code_block`.
68	code_block,
69	/// Data is `none`.
70	blockquote,
71	/// Data is `none`.
72	paragraph,
73	/// Data is `none`.
74	thematic_break,
75	};
76
77	const Data = union {
78	none: void,
79	list: struct {
80	marker: ListMarker,
81	/// Between 0 and 999,999,999, inclusive.
82	start: u30,
83	tight: bool,
84	last_line_blank: bool = false,
85	},
86	list_item: struct {
87	continuation_indent: usize,
88	},
89	table: struct {
90	column_alignments_buffer: [max_table_columns]Node.TableCellAlignment,
91	column_alignments_len: usize,
92	},
93	heading: struct {
94	/// Between 1 and 6, inclusive.
95	level: u3,
96	},
97	code_block: struct {
98	tag: StringIndex,
99	fence_len: usize,
100	indent: usize,
101	},
102
103	const ListMarker = enum {
104	@"-",
105	@"*",
106	@"+",
107	number_dot,
108	number_paren,
109	};
110	};
111
112	const ContentType = enum {
113	blocks,
114	inlines,
115	raw_inlines,
116	nothing,
117	};
118
119	fn canAccept(b: Block) ContentType {
120	return switch (b.tag) {
121	.list,
122	.list_item,
123	.table,
124	.blockquote,
125	=> .blocks,
126
127	.heading,
128	.paragraph,
129	=> .inlines,
130
131	.code_block,
132	=> .raw_inlines,
133
134	.table_row,
135	.thematic_break,
136	=> .nothing,
137	};
138	}
139
140	/// Attempts to continue `b` using the contents of `line`. If successful,
141	/// returns the remaining portion of `line` to be considered part of `b`
142	/// (e.g. for a blockquote, this would be everything except the leading
143	/// `>`). If unsuccessful, returns null.
144	fn match(b: Block, line: []const u8) ?[]const u8 {
145	const unindented = mem.trimStart(u8, line, " \t");
146	const indent = line.len - unindented.len;
147	return switch (b.tag) {
148	.list => line,
149	.list_item => if (indent >= b.data.list_item.continuation_indent)
150	line[b.data.list_item.continuation_indent..]
151	else if (unindented.len == 0)
152	// Blank lines should not close list items, since there may be
153	// more indented contents to follow after the blank line.
154	""
155	else
156	null,
157	.table => if (unindented.len > 0) line else null,
158	.table_row => null,
159	.heading => null,
160	.code_block => code_block: {
161	const trimmed = mem.trimEnd(u8, unindented, " \t");
162	if (mem.findNone(u8, trimmed, "`") != null or trimmed.len != b.data.code_block.fence_len) {
163	const effective_indent = @min(indent, b.data.code_block.indent);
164	break :code_block line[effective_indent..];
165	} else {
166	break :code_block null;
167	}
168	},
169	.blockquote => if (mem.startsWith(u8, unindented, ">"))
170	unindented[1..]
171	else
172	null,
173	.paragraph => if (unindented.len > 0) line else null,
174	.thematic_break => null,
175	};
176	}
177	};
178
179	pub fn init(allocator: Allocator) Allocator.Error!Parser {
180	var p: Parser = .{ .allocator = allocator };
181	try p.nodes.append(allocator, .{
182	.tag = .root,
183	.data = undefined,
184	});
185	try p.string_bytes.append(allocator, 0);
186	return p;
187	}
188
189	pub fn deinit(p: *Parser) void {
190	p.nodes.deinit(p.allocator);
191	p.extra.deinit(p.allocator);
192	p.scratch_extra.deinit(p.allocator);
193	p.string_bytes.deinit(p.allocator);
194	p.scratch_string.deinit(p.allocator);
195	p.pending_blocks.deinit(p.allocator);
196	p.* = undefined;
197	}
198
199	/// Accepts a single line of content. `line` should not have a trailing line
200	/// ending character.
201	pub fn feedLine(p: *Parser, line: []const u8) Allocator.Error!void {
202	var rest_line = line;
203	const first_unmatched = for (p.pending_blocks.items, 0..) |b, i| {
204	if (b.match(rest_line)) |rest| {
205	rest_line = rest;
206	} else {
207	break i;
208	}
209	} else p.pending_blocks.items.len;
210
211	const in_code_block = p.pending_blocks.items.len > 0 and
212	p.pending_blocks.last().?.tag == .code_block;
213	const code_block_end = in_code_block and
214	first_unmatched + 1 == p.pending_blocks.items.len;
215	// New blocks cannot be started if we are actively inside a code block or
216	// are just closing one (to avoid interpreting the closing ``` as a new code
217	// block start).
218	var maybe_block_start = if (!in_code_block or first_unmatched + 2 <= p.pending_blocks.items.len)
219	try p.startBlock(rest_line)
220	else
221	null;
222
223	// This is a lazy continuation line if there are no new blocks to open and
224	// the last open block is a paragraph.
225	if (maybe_block_start == null and
226	!isBlank(rest_line) and
227	p.pending_blocks.items.len > 0 and
228	p.pending_blocks.last().?.tag == .paragraph)
229	{
230	try p.addScratchStringLine(mem.trimStart(u8, rest_line, " \t"));
231	return;
232	}
233
234	// If a new block needs to be started, any paragraph needs to be closed,
235	// even though this isn't detected as part of the closing condition for
236	// paragraphs.
237	if (maybe_block_start != null and
238	p.pending_blocks.items.len > 0 and
239	p.pending_blocks.last().?.tag == .paragraph)
240	{
241	try p.closeLastBlock();
242	}
243
244	while (p.pending_blocks.items.len > first_unmatched) {
245	try p.closeLastBlock();
246	}
247
248	while (maybe_block_start) |block_start| : (maybe_block_start = try p.startBlock(rest_line)) {
249	try p.appendBlockStart(block_start);
250	// There may be more blocks to start within the same line.
251	rest_line = block_start.rest;
252	// Headings may only contain inline content.
253	if (block_start.tag == .heading) break;
254	// An opening code fence does not contain any additional block or inline
255	// content to process.
256	if (block_start.tag == .code_block) return;
257	}
258
259	// Do not append the end of a code block (```) as textual content.
260	if (code_block_end) return;
261
262	const can_accept = if (p.pending_blocks.last()) |last_pending_block|
263	last_pending_block.canAccept()
264	else
265	.blocks;
266	const rest_line_trimmed = mem.trimStart(u8, rest_line, " \t");
267	switch (can_accept) {
268	.blocks => {
269	// If we're inside a list item and the rest of the line is blank, it
270	// means that any subsequent child of the list item (or subsequent
271	// item in the list) will cause the containing list to be considered
272	// loose. However, we can't immediately declare that the list is
273	// loose, since we might just be looking at a blank line after the
274	// end of the last item in the list. The final determination will be
275	// made when appending the next child of the list or list item.
276	const maybe_containing_list_index = if (p.pending_blocks.items.len > 0 and p.pending_blocks.last().?.tag == .list_item)
277	p.pending_blocks.items.len - 2
278	else
279	null;
280
281	if (rest_line_trimmed.len > 0) {
282	try p.appendBlockStart(.{
283	.tag = .paragraph,
284	.data = .{ .none = {} },
285	.rest = undefined,
286	});
287	try p.addScratchStringLine(rest_line_trimmed);
288	}
289
290	if (maybe_containing_list_index) |containing_list_index| {
291	p.pending_blocks.items[containing_list_index].data.list.last_line_blank = rest_line_trimmed.len == 0;
292	}
293	},
294	.inlines => try p.addScratchStringLine(rest_line_trimmed),
295	.raw_inlines => try p.addScratchStringLine(rest_line),
296	.nothing => {},
297	}
298	}
299
300	/// Completes processing of the input and returns the parsed document.
301	pub fn endInput(p: *Parser) Allocator.Error!Document {
302	while (p.pending_blocks.items.len > 0) {
303	try p.closeLastBlock();
304	}
305	// There should be no inline content pending after closing the last open
306	// block.
307	assert(p.scratch_string.items.len == 0);
308
309	const children = try p.addExtraChildren(@ptrCast(p.scratch_extra.items));
310	p.nodes.items(.data)[0] = .{ .container = .{ .children = children } };
311	p.scratch_string.items.len = 0;
312	p.scratch_extra.items.len = 0;
313
314	try p.extra.shrinkToLen(p.allocator);
315	try p.string_bytes.shrinkToLen(p.allocator);
316
317	return .{
318	.nodes = p.nodes.toOwnedSlice(),
319	.extra = p.extra.toOwnedSliceAssert(),
320	.string_bytes = p.string_bytes.toOwnedSliceAssert(),
321	};
322	}
323
324	/// Data describing the start of a new block element.
325	const BlockStart = struct {
326	tag: Tag,
327	data: Data,
328	rest: []const u8,
329
330	const Tag = enum {
331	/// Data is `list_item`.
332	list_item,
333	/// Data is `table_row`.
334	table_row,
335	/// Data is `heading`.
336	heading,
337	/// Data is `code_block`.
338	code_block,
339	/// Data is `none`.
340	blockquote,
341	/// Data is `none`.
342	paragraph,
343	/// Data is `none`.
344	thematic_break,
345	};
346
347	const Data = union {
348	none: void,
349	list_item: struct {
350	marker: Block.Data.ListMarker,
351	number: u30,
352	continuation_indent: usize,
353	},
354	table_row: struct {
355	cells_buffer: [max_table_columns][]const u8,
356	cells_len: usize,
357	},
358	heading: struct {
359	/// Between 1 and 6, inclusive.
360	level: u3,
361	},
362	code_block: struct {
363	tag: StringIndex,
364	fence_len: usize,
365	indent: usize,
366	},
367	};
368	};
369
370	fn appendBlockStart(p: *Parser, block_start: BlockStart) !void {
371	if (p.pending_blocks.last()) |last_pending_block| {
372	// Close the last block if it is a list and the new block is not a list item
373	// or not of the same marker type.
374	const should_close_list = last_pending_block.tag == .list and
375	(block_start.tag != .list_item or
376	block_start.data.list_item.marker != last_pending_block.data.list.marker);
377	// The last block should also be closed if the new block is not a table
378	// row, which is the only allowed child of a table.
379	const should_close_table = last_pending_block.tag == .table and
380	block_start.tag != .table_row;
381	if (should_close_list or should_close_table) {
382	try p.closeLastBlock();
383	}
384	}
385
386	if (p.pending_blocks.last()) |last_pending_block| {
387	// If the last block is a list or list item, check for tightness based
388	// on the last line.
389	const maybe_containing_list = switch (last_pending_block.tag) {
390	.list => &p.pending_blocks.items[p.pending_blocks.items.len - 1],
391	.list_item => &p.pending_blocks.items[p.pending_blocks.items.len - 2],
392	else => null,
393	};
394	if (maybe_containing_list) |containing_list| {
395	if (containing_list.data.list.last_line_blank) {
396	containing_list.data.list.tight = false;
397	}
398	}
399	}
400
401	// Start a new list if the new block is a list item and there is no
402	// containing list yet.
403	if (block_start.tag == .list_item and
404	(p.pending_blocks.items.len == 0 or p.pending_blocks.last().?.tag != .list))
405	{
406	try p.pending_blocks.append(p.allocator, .{
407	.tag = .list,
408	.data = .{ .list = .{
409	.marker = block_start.data.list_item.marker,
410	.start = block_start.data.list_item.number,
411	.tight = true,
412	} },
413	.string_start = p.scratch_string.items.len,
414	.extra_start = p.scratch_extra.items.len,
415	});
416	}
417
418	if (block_start.tag == .table_row) {
419	// Likewise, table rows start a table implicitly.
420	if (p.pending_blocks.items.len == 0 or p.pending_blocks.last().?.tag != .table) {
421	try p.pending_blocks.append(p.allocator, .{
422	.tag = .table,
423	.data = .{ .table = .{
424	.column_alignments_buffer = undefined,
425	.column_alignments_len = 0,
426	} },
427	.string_start = p.scratch_string.items.len,
428	.extra_start = p.scratch_extra.items.len,
429	});
430	}
431
432	const current_row = p.scratch_extra.items.len - p.pending_blocks.last().?.extra_start;
433	if (current_row <= 1) {
434	var buffer: [max_table_columns]Node.TableCellAlignment = undefined;
435	const table_row = &block_start.data.table_row;
436	if (parseTableHeaderDelimiter(table_row.cells_buffer[0..table_row.cells_len], &buffer)) |alignments| {
437	const table = &p.pending_blocks.items[p.pending_blocks.items.len - 1].data.table;
438	@memcpy(table.column_alignments_buffer[0..alignments.len], alignments);
439	table.column_alignments_len = alignments.len;
440	if (current_row == 1) {
441	// We need to go back and mark the header row and its column
442	// alignments.
443	const datas = p.nodes.items(.data);
444	const header_data = datas[p.scratch_extra.last().?];
445	for (p.extraChildren(header_data.container.children), 0..) |header_cell, i| {
446	const alignment = if (i < alignments.len) alignments[i] else .unset;
447	const cell_data = &datas[@backingInt(header_cell)].table_cell;
448	cell_data.info.alignment = alignment;
449	cell_data.info.header = true;
450	}
451	}
452	return;
453	}
454	}
455	}
456
457	const tag: Block.Tag, const data: Block.Data = switch (block_start.tag) {
458	.list_item => .{ .list_item, .{ .list_item = .{
459	.continuation_indent = block_start.data.list_item.continuation_indent,
460	} } },
461	.table_row => .{ .table_row, .{ .none = {} } },
462	.heading => .{ .heading, .{ .heading = .{
463	.level = block_start.data.heading.level,
464	} } },
465	.code_block => .{ .code_block, .{ .code_block = .{
466	.tag = block_start.data.code_block.tag,
467	.fence_len = block_start.data.code_block.fence_len,
468	.indent = block_start.data.code_block.indent,
469	} } },
470	.blockquote => .{ .blockquote, .{ .none = {} } },
471	.paragraph => .{ .paragraph, .{ .none = {} } },
472	.thematic_break => .{ .thematic_break, .{ .none = {} } },
473	};
474
475	try p.pending_blocks.append(p.allocator, .{
476	.tag = tag,
477	.data = data,
478	.string_start = p.scratch_string.items.len,
479	.extra_start = p.scratch_extra.items.len,
480	});
481
482	if (tag == .table_row) {
483	// Table rows are unique, since we already have all the children
484	// available in the BlockStart. We can immediately parse and append
485	// these children now.
486	const containing_table = p.pending_blocks.items[p.pending_blocks.items.len - 2];
487	const table = &containing_table.data.table;
488	const column_alignments = table.column_alignments_buffer[0..table.column_alignments_len];
489	const table_row = &block_start.data.table_row;
490	for (table_row.cells_buffer[0..table_row.cells_len], 0..) |cell_content, i| {
491	const cell_children = try p.parseInlines(cell_content);
492	const alignment = if (i < column_alignments.len) column_alignments[i] else .unset;
493	const cell = try p.addNode(.{
494	.tag = .table_cell,
495	.data = .{ .table_cell = .{
496	.info = .{
497	.alignment = alignment,
498	.header = false,
499	},
500	.children = cell_children,
501	} },
502	});
503	try p.addScratchExtraNode(cell);
504	}
505	}
506	}
507
508	fn startBlock(p: *Parser, line: []const u8) !?BlockStart {
509	const unindented = mem.trimStart(u8, line, " \t");
510	const indent = line.len - unindented.len;
511	if (isThematicBreak(line)) {
512	// Thematic breaks take precedence over list items.
513	return .{
514	.tag = .thematic_break,
515	.data = .{ .none = {} },
516	.rest = "",
517	};
518	} else if (startListItem(unindented)) |list_item| {
519	return .{
520	.tag = .list_item,
521	.data = .{ .list_item = .{
522	.marker = list_item.marker,
523	.number = list_item.number,
524	.continuation_indent = indent + list_item.marker_len,
525	} },
526	.rest = list_item.rest,
527	};
528	} else if (startTableRow(unindented)) |table_row| {
529	return .{
530	.tag = .table_row,
531	.data = .{ .table_row = .{
532	.cells_buffer = table_row.cells_buffer,
533	.cells_len = table_row.cells_len,
534	} },
535	.rest = "",
536	};
537	} else if (startHeading(unindented)) |heading| {
538	return .{
539	.tag = .heading,
540	.data = .{ .heading = .{
541	.level = heading.level,
542	} },
543	.rest = heading.rest,
544	};
545	} else if (try p.startCodeBlock(unindented)) |code_block| {
546	return .{
547	.tag = .code_block,
548	.data = .{ .code_block = .{
549	.tag = code_block.tag,
550	.fence_len = code_block.fence_len,
551	.indent = indent,
552	} },
553	.rest = "",
554	};
555	} else if (startBlockquote(unindented)) |rest| {
556	return .{
557	.tag = .blockquote,
558	.data = .{ .none = {} },
559	.rest = rest,
560	};
561	} else {
562	return null;
563	}
564	}
565
566	const ListItemStart = struct {
567	marker: Block.Data.ListMarker,
568	number: u30,
569	marker_len: usize,
570	rest: []const u8,
571	};
572
573	fn startListItem(unindented_line: []const u8) ?ListItemStart {
574	if (mem.startsWith(u8, unindented_line, "- ")) {
575	return .{
576	.marker = .@"-",
577	.number = undefined,
578	.marker_len = 2,
579	.rest = unindented_line[2..],
580	};
581	} else if (mem.startsWith(u8, unindented_line, "* ")) {
582	return .{
583	.marker = .@"*",
584	.number = undefined,
585	.marker_len = 2,
586	.rest = unindented_line[2..],
587	};
588	} else if (mem.startsWith(u8, unindented_line, "+ ")) {
589	return .{
590	.marker = .@"+",
591	.number = undefined,
592	.marker_len = 2,
593	.rest = unindented_line[2..],
594	};
595	}
596
597	const number_end = mem.findNone(u8, unindented_line, "0123456789") orelse return null;
598	const after_number = unindented_line[number_end..];
599	const marker: Block.Data.ListMarker = if (mem.startsWith(u8, after_number, ". "))
600	.number_dot
601	else if (mem.startsWith(u8, after_number, ") "))
602	.number_paren
603	else
604	return null;
605	const number = std.fmt.parseInt(u30, unindented_line[0..number_end], 10) catch return null;
606	if (number > 999_999_999) return null;
607	return .{
608	.marker = marker,
609	.number = number,
610	.marker_len = number_end + 2,
611	.rest = after_number[2..],
612	};
613	}
614
615	const TableRowStart = struct {
616	cells_buffer: [max_table_columns][]const u8,
617	cells_len: usize,
618	};
619
620	fn startTableRow(unindented_line: []const u8) ?TableRowStart {
621	if (unindented_line.len < 2 or
622	!mem.startsWith(u8, unindented_line, "|") or
623	mem.endsWith(u8, unindented_line, "\\|") or
624	!mem.endsWith(u8, unindented_line, "|")) return null;
625
626	var cells_buffer: [max_table_columns][]const u8 = undefined;
627	var cells: ArrayList([]const u8) = .initBuffer(&cells_buffer);
628	const table_row_content = unindented_line[1 .. unindented_line.len - 1];
629	var cell_start: usize = 0;
630	var i: usize = 0;
631	while (i < table_row_content.len) : (i += 1) {
632	switch (table_row_content[i]) {
633	'\\' => i += 1,
634	'|' => {
635	cells.appendBounded(table_row_content[cell_start..i]) catch return null;
636	cell_start = i + 1;
637	},
638	'`' => {
639	// Ignoring pipes in code spans allows table cells to contain
640	// code using ||, for example.
641	const open_start = i;
642	i = mem.findNonePos(u8, table_row_content, i, "`") orelse return null;
643	const open_len = i - open_start;
644	while (mem.findScalarPos(u8, table_row_content, i, '`')) |close_start| {
645	i = mem.findNonePos(u8, table_row_content, close_start, "`") orelse return null;
646	const close_len = i - close_start;
647	if (close_len == open_len) break;
648	} else return null;
649	},
650	else => {},
651	}
652	}
653	cells.appendBounded(table_row_content[cell_start..]) catch return null;
654
655	return .{ .cells_buffer = cells_buffer, .cells_len = cells.items.len };
656	}
657
658	fn parseTableHeaderDelimiter(
659	row_cells: []const []const u8,
660	buffer: []Node.TableCellAlignment,
661	) ?[]Node.TableCellAlignment {
662	var alignments: ArrayList(Node.TableCellAlignment) = .initBuffer(buffer);
663	for (row_cells) |content| {
664	const alignment = parseTableHeaderDelimiterCell(content) orelse return null;
665	alignments.appendAssumeCapacity(alignment);
666	}
667	return alignments.items;
668	}
669
670	fn parseTableHeaderDelimiterCell(content: []const u8) ?Node.TableCellAlignment {
671	var state: enum {
672	before_rule,
673	after_left_anchor,
674	in_rule,
675	after_right_anchor,
676	after_rule,
677	} = .before_rule;
678	var left_anchor = false;
679	var right_anchor = false;
680	for (content) |c| {
681	switch (state) {
682	.before_rule => switch (c) {
683	' ' => {},
684	':' => {
685	left_anchor = true;
686	state = .after_left_anchor;
687	},
688	'-' => state = .in_rule,
689	else => return null,
690	},
691	.after_left_anchor => switch (c) {
692	'-' => state = .in_rule,
693	else => return null,
694	},
695	.in_rule => switch (c) {
696	'-' => {},
697	':' => {
698	right_anchor = true;
699	state = .after_right_anchor;
700	},
701	' ' => state = .after_rule,
702	else => return null,
703	},
704	.after_right_anchor => switch (c) {
705	' ' => state = .after_rule,
706	else => return null,
707	},
708	.after_rule => switch (c) {
709	' ' => {},
710	else => return null,
711	},
712	}
713	}
714
715	switch (state) {
716	.before_rule,
717	.after_left_anchor,
718	=> return null,
719
720	.in_rule,
721	.after_right_anchor,
722	.after_rule,
723	=> {},
724	}
725
726	return if (left_anchor and right_anchor)
727	.center
728	else if (left_anchor)
729	.left
730	else if (right_anchor)
731	.right
732	else
733	.unset;
734	}
735
736	test parseTableHeaderDelimiterCell {
737	try expectEqual(null, parseTableHeaderDelimiterCell(""));
738	try expectEqual(null, parseTableHeaderDelimiterCell(" "));
739	try expectEqual(.unset, parseTableHeaderDelimiterCell("-"));
740	try expectEqual(.unset, parseTableHeaderDelimiterCell(" - "));
741	try expectEqual(.unset, parseTableHeaderDelimiterCell("----"));
742	try expectEqual(.unset, parseTableHeaderDelimiterCell(" ---- "));
743	try expectEqual(null, parseTableHeaderDelimiterCell(":"));
744	try expectEqual(null, parseTableHeaderDelimiterCell("::"));
745	try expectEqual(.left, parseTableHeaderDelimiterCell(":-"));
746	try expectEqual(.left, parseTableHeaderDelimiterCell(" :----"));
747	try expectEqual(.center, parseTableHeaderDelimiterCell(":-:"));
748	try expectEqual(.center, parseTableHeaderDelimiterCell(":----:"));
749	try expectEqual(.center, parseTableHeaderDelimiterCell(" :----: "));
750	try expectEqual(.right, parseTableHeaderDelimiterCell("-:"));
751	try expectEqual(.right, parseTableHeaderDelimiterCell("----:"));
752	try expectEqual(.right, parseTableHeaderDelimiterCell(" ----: "));
753	}
754
755	const HeadingStart = struct {
756	level: u3,
757	rest: []const u8,
758	};
759
760	fn startHeading(unindented_line: []const u8) ?HeadingStart {
761	var level: u3 = 0;
762	return for (unindented_line, 0..) |c, i| {
763	switch (c) {
764	'#' => {
765	if (level == 6) break null;
766	level += 1;
767	},
768	' ' => {
769	// We must have seen at least one # by this point, since
770	// unindented_line has no leading spaces.
771	assert(level > 0);
772	break .{
773	.level = level,
774	.rest = unindented_line[i + 1 ..],
775	};
776	},
777	else => break null,
778	}
779	} else null;
780	}
781
782	const CodeBlockStart = struct {
783	tag: StringIndex,
784	fence_len: usize,
785	};
786
787	fn startCodeBlock(p: *Parser, unindented_line: []const u8) !?CodeBlockStart {
788	var fence_len: usize = 0;
789	const tag_bytes = for (unindented_line, 0..) |c, i| {
790	switch (c) {
791	'`' => fence_len += 1,
792	else => break unindented_line[i..],
793	}
794	} else "";
795	// Code block tags may not contain backticks, since that would create
796	// potential confusion with inline code spans.
797	if (fence_len < 3 or mem.findScalar(u8, tag_bytes, '`') != null) return null;
798	return .{
799	.tag = try p.addString(mem.trim(u8, tag_bytes, " ")),
800	.fence_len = fence_len,
801	};
802	}
803
804	fn startBlockquote(unindented_line: []const u8) ?[]const u8 {
805	return if (mem.startsWith(u8, unindented_line, ">"))
806	unindented_line[1..]
807	else
808	null;
809	}
810
811	fn isThematicBreak(line: []const u8) bool {
812	var char: ?u8 = null;
813	var count: usize = 0;
814	for (line) |c| {
815	switch (c) {
816	' ' => {},
817	'-', '_', '*' => {
818	if (char != null and c != char.?) return false;
819	char = c;
820	count += 1;
821	},
822	else => return false,
823	}
824	}
825	return count >= 3;
826	}
827
828	fn closeLastBlock(p: *Parser) !void {
829	const b = p.pending_blocks.pop().?;
830	const node = switch (b.tag) {
831	.list => list: {
832	assert(b.string_start == p.scratch_string.items.len);
833
834	// Although tightness is parsed as a property of the list, it is
835	// stored at the list item level to make it possible to render each
836	// node without any context from its parents.
837	const list_items = p.scratch_extra.items[b.extra_start..];
838	const node_datas = p.nodes.items(.data);
839	if (!b.data.list.tight) {
840	for (list_items) |list_item| {
841	node_datas[list_item].list_item.tight = false;
842	}
843	}
844
845	const children = try p.addExtraChildren(@ptrCast(list_items));
846	break :list try p.addNode(.{
847	.tag = .list,
848	.data = .{ .list = .{
849	.start = switch (b.data.list.marker) {
850	.number_dot, .number_paren => @fromBackingInt(@intCast(b.data.list.start)),
851	.@"-", .@"*", .@"+" => .unordered,
852	},
853	.children = children,
854	} },
855	});
856	},
857	.list_item => list_item: {
858	assert(b.string_start == p.scratch_string.items.len);
859	const children = try p.addExtraChildren(@ptrCast(p.scratch_extra.items[b.extra_start..]));
860	break :list_item try p.addNode(.{
861	.tag = .list_item,
862	.data = .{ .list_item = .{
863	.tight = true,
864	.children = children,
865	} },
866	});
867	},
868	.table => table: {
869	assert(b.string_start == p.scratch_string.items.len);
870	const children = try p.addExtraChildren(@ptrCast(p.scratch_extra.items[b.extra_start..]));
871	break :table try p.addNode(.{
872	.tag = .table,
873	.data = .{ .container = .{
874	.children = children,
875	} },
876	});
877	},
878	.table_row => table_row: {
879	assert(b.string_start == p.scratch_string.items.len);
880	const children = try p.addExtraChildren(@ptrCast(p.scratch_extra.items[b.extra_start..]));
881	break :table_row try p.addNode(.{
882	.tag = .table_row,
883	.data = .{ .container = .{
884	.children = children,
885	} },
886	});
887	},
888	.heading => heading: {
889	const children = try p.parseInlines(p.scratch_string.items[b.string_start..]);
890	break :heading try p.addNode(.{
891	.tag = .heading,
892	.data = .{ .heading = .{
893	.level = b.data.heading.level,
894	.children = children,
895	} },
896	});
897	},
898	.code_block => code_block: {
899	const content = try p.addString(p.scratch_string.items[b.string_start..]);
900	break :code_block try p.addNode(.{
901	.tag = .code_block,
902	.data = .{ .code_block = .{
903	.tag = b.data.code_block.tag,
904	.content = content,
905	} },
906	});
907	},
908	.blockquote => blockquote: {
909	assert(b.string_start == p.scratch_string.items.len);
910	const children = try p.addExtraChildren(@ptrCast(p.scratch_extra.items[b.extra_start..]));
911	break :blockquote try p.addNode(.{
912	.tag = .blockquote,
913	.data = .{ .container = .{
914	.children = children,
915	} },
916	});
917	},
918	.paragraph => paragraph: {
919	const children = try p.parseInlines(p.scratch_string.items[b.string_start..]);
920	break :paragraph try p.addNode(.{
921	.tag = .paragraph,
922	.data = .{ .container = .{
923	.children = children,
924	} },
925	});
926	},
927	.thematic_break => try p.addNode(.{
928	.tag = .thematic_break,
929	.data = .{ .none = {} },
930	}),
931	};
932	p.scratch_string.items.len = b.string_start;
933	p.scratch_extra.items.len = b.extra_start;
934	try p.addScratchExtraNode(node);
935	}
936
937	const InlineParser = struct {
938	parent: *Parser,
939	content: []const u8,
940	pos: usize = 0,
941	pending_inlines: ArrayList(PendingInline) = .empty,
942	completed_inlines: ArrayList(CompletedInline) = .empty,
943
944	const PendingInline = struct {
945	tag: Tag,
946	data: Data,
947	start: usize,
948
949	const Tag = enum {
950	/// Data is `emphasis`.
951	emphasis,
952	/// Data is `none`.
953	link,
954	/// Data is `none`.
955	image,
956	};
957
958	const Data = union {
959	none: void,
960	emphasis: struct {
961	underscore: bool,
962	run_len: usize,
963	},
964	};
965	};
966
967	const CompletedInline = struct {
968	node: Node.Index,
969	start: usize,
970	len: usize,
971	};
972
973	fn deinit(ip: *InlineParser) void {
974	ip.pending_inlines.deinit(ip.parent.allocator);
975	ip.completed_inlines.deinit(ip.parent.allocator);
976	}
977
978	/// Parses all of `ip.content`, returning the children of the node
979	/// containing the inline content.
980	fn parse(ip: *InlineParser) Allocator.Error!ExtraIndex {
981	while (ip.pos < ip.content.len) : (ip.pos += 1) {
982	switch (ip.content[ip.pos]) {
983	'\\' => ip.pos += 1,
984	'[' => try ip.pending_inlines.append(ip.parent.allocator, .{
985	.tag = .link,
986	.data = .{ .none = {} },
987	.start = ip.pos,
988	}),
989	'!' => if (ip.pos + 1 < ip.content.len and ip.content[ip.pos + 1] == '[') {
990	try ip.pending_inlines.append(ip.parent.allocator, .{
991	.tag = .image,
992	.data = .{ .none = {} },
993	.start = ip.pos,
994	});
995	ip.pos += 1;
996	},
997	']' => try ip.parseLink(),
998	'<' => try ip.parseAutolink(),
999	'*', '_' => try ip.parseEmphasis(),
1000	'`' => try ip.parseCodeSpan(),
1001	'h' => if (ip.pos == 0 or isPreTextAutolink(ip.content[ip.pos - 1])) {
1002	try ip.parseTextAutolink();
1003	},
1004	else => {},
1005	}
1006	}
1007
1008	const children = try ip.encodeChildren(0, ip.content.len);
1009	// There may be pending inlines after parsing (e.g. unclosed emphasis
1010	// runs), but there must not be any completed inlines, since those
1011	// should all be part of `children`.
1012	assert(ip.completed_inlines.items.len == 0);
1013	return children;
1014	}
1015
1016	/// Parses a link, starting at the `]` at the end of the link text. `ip.pos`
1017	/// is left at the closing `)` of the link target or at the closing `]` if
1018	/// there is none.
1019	fn parseLink(ip: *InlineParser) !void {
1020	var i = ip.pending_inlines.items.len;
1021	while (i > 0) {
1022	i -= 1;
1023	if (ip.pending_inlines.items[i].tag == .link or
1024	ip.pending_inlines.items[i].tag == .image) break;
1025	} else return;
1026	const opener = ip.pending_inlines.items[i];
1027	ip.pending_inlines.shrinkRetainingCapacity(i);
1028	const text_start = switch (opener.tag) {
1029	.link => opener.start + 1,
1030	.image => opener.start + 2,
1031	else => unreachable,
1032	};
1033
1034	if (ip.pos + 1 >= ip.content.len or ip.content[ip.pos + 1] != '(') return;
1035	const text_end = ip.pos;
1036
1037	const target_start = text_end + 2;
1038	var target_end = target_start;
1039	var nesting_level: usize = 1;
1040	while (target_end < ip.content.len) : (target_end += 1) {
1041	switch (ip.content[target_end]) {
1042	'\\' => target_end += 1,
1043	'(' => nesting_level += 1,
1044	')' => {
1045	if (nesting_level == 1) break;
1046	nesting_level -= 1;
1047	},
1048	else => {},
1049	}
1050	} else return;
1051	ip.pos = target_end;
1052
1053	const children = try ip.encodeChildren(text_start, text_end);
1054	const target = try ip.encodeLinkTarget(target_start, target_end);
1055
1056	const link = try ip.parent.addNode(.{
1057	.tag = switch (opener.tag) {
1058	.link => .link,
1059	.image => .image,
1060	else => unreachable,
1061	},
1062	.data = .{ .link = .{
1063	.target = target,
1064	.children = children,
1065	} },
1066	});
1067	try ip.completed_inlines.append(ip.parent.allocator, .{
1068	.node = link,
1069	.start = opener.start,
1070	.len = ip.pos - opener.start + 1,
1071	});
1072	}
1073
1074	fn encodeLinkTarget(ip: *InlineParser, start: usize, end: usize) !StringIndex {
1075	// For efficiency, we can encode directly into string_bytes rather than
1076	// creating a temporary string and then encoding it, since this process
1077	// is entirely linear.
1078	const string_top = ip.parent.string_bytes.items.len;
1079	errdefer ip.parent.string_bytes.shrinkRetainingCapacity(string_top);
1080
1081	var text_iter: TextIterator = .{ .content = ip.content[start..end] };
1082	while (text_iter.next()) |content| {
1083	switch (content) {
1084	.char => |c| try ip.parent.string_bytes.append(ip.parent.allocator, c),
1085	.text => |s| try ip.parent.string_bytes.appendSlice(ip.parent.allocator, s),
1086	.line_break => try ip.parent.string_bytes.appendSlice(ip.parent.allocator, "\\\n"),
1087	}
1088	}
1089	try ip.parent.string_bytes.append(ip.parent.allocator, 0);
1090	return @fromBackingInt(@intCast(string_top));
1091	}
1092
1093	/// Parses an autolink, starting at the opening `<`. `ip.pos` is left at the
1094	/// closing `>`, or remains unchanged at the opening `<` if there is none.
1095	fn parseAutolink(ip: *InlineParser) !void {
1096	const start = ip.pos;
1097	ip.pos += 1;
1098	var state: enum {
1099	start,
1100	scheme,
1101	target,
1102	} = .start;
1103	while (ip.pos < ip.content.len) : (ip.pos += 1) {
1104	switch (state) {
1105	.start => switch (ip.content[ip.pos]) {
1106	'A'...'Z', 'a'...'z' => state = .scheme,
1107	else => break,
1108	},
1109	.scheme => switch (ip.content[ip.pos]) {
1110	'A'...'Z', 'a'...'z', '0'...'9', '+', '.', '-' => {},
1111	':' => state = .target,
1112	else => break,
1113	},
1114	.target => switch (ip.content[ip.pos]) {
1115	'<', ' ', '\t', '\n' => break, // Not allowed in autolinks
1116	'>' => {
1117	// Backslash escapes are not recognized in autolink targets.
1118	const target = try ip.parent.addString(ip.content[start + 1 .. ip.pos]);
1119	const node = try ip.parent.addNode(.{
1120	.tag = .autolink,
1121	.data = .{ .text = .{
1122	.content = target,
1123	} },
1124	});
1125	try ip.completed_inlines.append(ip.parent.allocator, .{
1126	.node = node,
1127	.start = start,
1128	.len = ip.pos - start + 1,
1129	});
1130	return;
1131	},
1132	else => {},
1133	},
1134	}
1135	}
1136	ip.pos = start;
1137	}
1138
1139	/// Parses a plain text autolink (not delimited by `<>`), starting at the
1140	/// first character in the link (an `h`). `ip.pos` is left at the last
1141	/// character of the link, or remains unchanged if there is no valid link.
1142	fn parseTextAutolink(ip: *InlineParser) !void {
1143	const start = ip.pos;
1144	var state: union(enum) {
1145	/// Inside `http`. Contains the rest of the text to be matched.
1146	http: []const u8,
1147	after_http,
1148	after_https,
1149	/// Inside `://`. Contains the rest of the text to be matched.
1150	authority: []const u8,
1151	/// Inside link content.
1152	content: struct {
1153	start: usize,
1154	paren_nesting: usize,
1155	},
1156	} = .{ .http = "http" };
1157
1158	while (ip.pos < ip.content.len) : (ip.pos += 1) {
1159	switch (state) {
1160	.http => |rest| {
1161	if (ip.content[ip.pos] != rest[0]) break;
1162	if (rest.len > 1) {
1163	state = .{ .http = rest[1..] };
1164	} else {
1165	state = .after_http;
1166	}
1167	},
1168	.after_http => switch (ip.content[ip.pos]) {
1169	's' => state = .after_https,
1170	':' => state = .{ .authority = "//" },
1171	else => break,
1172	},
1173	.after_https => switch (ip.content[ip.pos]) {
1174	':' => state = .{ .authority = "//" },
1175	else => break,
1176	},
1177	.authority => |rest| {
1178	if (ip.content[ip.pos] != rest[0]) break;
1179	if (rest.len > 1) {
1180	state = .{ .authority = rest[1..] };
1181	} else {
1182	state = .{ .content = .{
1183	.start = ip.pos + 1,
1184	.paren_nesting = 0,
1185	} };
1186	}
1187	},
1188	.content => |*content| switch (ip.content[ip.pos]) {
1189	' ', '\t', '\n' => break,
1190	'(' => content.paren_nesting += 1,
1191	')' => if (content.paren_nesting == 0) {
1192	break;
1193	} else {
1194	content.paren_nesting -= 1;
1195	},
1196	else => {},
1197	},
1198	}
1199	}
1200
1201	switch (state) {
1202	.http, .after_http, .after_https, .authority => {
1203	ip.pos = start;
1204	},
1205	.content => |content| {
1206	while (ip.pos > content.start and isPostTextAutolink(ip.content[ip.pos - 1])) {
1207	ip.pos -= 1;
1208	}
1209	if (ip.pos == content.start) {
1210	ip.pos = start;
1211	return;
1212	}
1213
1214	const target = try ip.parent.addString(ip.content[start..ip.pos]);
1215	const node = try ip.parent.addNode(.{
1216	.tag = .autolink,
1217	.data = .{ .text = .{
1218	.content = target,
1219	} },
1220	});
1221	try ip.completed_inlines.append(ip.parent.allocator, .{
1222	.node = node,
1223	.start = start,
1224	.len = ip.pos - start,
1225	});
1226	ip.pos -= 1;
1227	},
1228	}
1229	}
1230
1231	/// Returns whether `c` may appear before a text autolink is recognized.
1232	fn isPreTextAutolink(c: u8) bool {
1233	return switch (c) {
1234	' ', '\t', '\n', '*', '_', '(' => true,
1235	else => false,
1236	};
1237	}
1238
1239	/// Returns whether `c` is punctuation that may appear after a text autolink
1240	/// and not be considered part of it.
1241	fn isPostTextAutolink(c: u8) bool {
1242	return switch (c) {
1243	'?', '!', '.', ',', ':', '*', '_' => true,
1244	else => false,
1245	};
1246	}
1247
1248	/// Parses emphasis, starting at the beginning of a run of `*` or `_`
1249	/// characters. `ip.pos` is left at the last character in the run after
1250	/// parsing.
1251	fn parseEmphasis(ip: *InlineParser) !void {
1252	const char = ip.content[ip.pos];
1253	var start = ip.pos;
1254	while (ip.pos + 1 < ip.content.len and ip.content[ip.pos + 1] == char) {
1255	ip.pos += 1;
1256	}
1257	var len = ip.pos - start + 1;
1258	const underscore = char == '_';
1259	const space_before = start == 0 or isWhitespace(ip.content[start - 1]);
1260	const space_after = start + len == ip.content.len or isWhitespace(ip.content[start + len]);
1261	const punct_before = start == 0 or isPunctuation(ip.content[start - 1]);
1262	const punct_after = start + len == ip.content.len or isPunctuation(ip.content[start + len]);
1263	// The rules for when emphasis may be closed or opened are stricter for
1264	// underscores to avoid inappropriately interpreting snake_case words as
1265	// containing emphasis markers.
1266	const can_open = if (underscore)
1267	!space_after and (space_before or punct_before)
1268	else
1269	!space_after;
1270	const can_close = if (underscore)
1271	!space_before and (space_after or punct_after)
1272	else
1273	!space_before;
1274
1275	if (can_close and ip.pending_inlines.items.len > 0) {
1276	var i = ip.pending_inlines.items.len;
1277	while (i > 0 and len > 0) {
1278	i -= 1;
1279	const opener = &ip.pending_inlines.items[i];
1280	if (opener.tag != .emphasis or
1281	opener.data.emphasis.underscore != underscore) continue;
1282
1283	const close_len = @min(opener.data.emphasis.run_len, len);
1284	const opener_end = opener.start + opener.data.emphasis.run_len;
1285
1286	const emphasis = try ip.encodeEmphasis(opener_end, start, close_len);
1287	const emphasis_start = opener_end - close_len;
1288	const emphasis_len = start - emphasis_start + close_len;
1289	try ip.completed_inlines.append(ip.parent.allocator, .{
1290	.node = emphasis,
1291	.start = emphasis_start,
1292	.len = emphasis_len,
1293	});
1294
1295	// There may still be other openers further down in the
1296	// stack to close, or part of this run might serve as an
1297	// opener itself.
1298	start += close_len;
1299	len -= close_len;
1300
1301	// Remove any pending inlines above this on the stack, since
1302	// closing this emphasis will prevent them from being closed.
1303	// Additionally, if this opener is completely consumed by
1304	// being closed, it can be removed.
1305	opener.data.emphasis.run_len -= close_len;
1306	if (opener.data.emphasis.run_len == 0) {
1307	ip.pending_inlines.shrinkRetainingCapacity(i);
1308	} else {
1309	ip.pending_inlines.shrinkRetainingCapacity(i + 1);
1310	}
1311	}
1312	}
1313
1314	if (can_open and len > 0) {
1315	try ip.pending_inlines.append(ip.parent.allocator, .{
1316	.tag = .emphasis,
1317	.data = .{ .emphasis = .{
1318	.underscore = underscore,
1319	.run_len = len,
1320	} },
1321	.start = start,
1322	});
1323	}
1324	}
1325
1326	/// Encodes emphasis specified by a run of `run_len` emphasis characters,
1327	/// with `start..end` being the range of content contained within the
1328	/// emphasis.
1329	fn encodeEmphasis(ip: *InlineParser, start: usize, end: usize, run_len: usize) !Node.Index {
1330	const children = try ip.encodeChildren(start, end);
1331	var inner = switch (run_len % 3) {
1332	1 => try ip.parent.addNode(.{
1333	.tag = .emphasis,
1334	.data = .{ .container = .{
1335	.children = children,
1336	} },
1337	}),
1338	2 => try ip.parent.addNode(.{
1339	.tag = .strong,
1340	.data = .{ .container = .{
1341	.children = children,
1342	} },
1343	}),
1344	0 => strong_emphasis: {
1345	const strong = try ip.parent.addNode(.{
1346	.tag = .strong,
1347	.data = .{ .container = .{
1348	.children = children,
1349	} },
1350	});
1351	break :strong_emphasis try ip.parent.addNode(.{
1352	.tag = .emphasis,
1353	.data = .{ .container = .{
1354	.children = try ip.parent.addExtraChildren(&.{strong}),
1355	} },
1356	});
1357	},
1358	else => unreachable,
1359	};
1360
1361	var run_left = run_len;
1362	while (run_left > 3) : (run_left -= 3) {
1363	const strong = try ip.parent.addNode(.{
1364	.tag = .strong,
1365	.data = .{ .container = .{
1366	.children = try ip.parent.addExtraChildren(&.{inner}),
1367	} },
1368	});
1369	inner = try ip.parent.addNode(.{
1370	.tag = .emphasis,
1371	.data = .{ .container = .{
1372	.children = try ip.parent.addExtraChildren(&.{strong}),
1373	} },
1374	});
1375	}
1376
1377	return inner;
1378	}
1379
1380	/// Parses a code span, starting at the beginning of the opening backtick
1381	/// run. `ip.pos` is left at the last character in the closing run after
1382	/// parsing.
1383	fn parseCodeSpan(ip: *InlineParser) !void {
1384	const opener_start = ip.pos;
1385	ip.pos = mem.findNonePos(u8, ip.content, ip.pos, "`") orelse ip.content.len;
1386	const opener_len = ip.pos - opener_start;
1387
1388	const start = ip.pos;
1389	const end = while (mem.findScalarPos(u8, ip.content, ip.pos, '`')) |closer_start| {
1390	ip.pos = mem.findNonePos(u8, ip.content, closer_start, "`") orelse ip.content.len;
1391	const closer_len = ip.pos - closer_start;
1392
1393	if (closer_len == opener_len) break closer_start;
1394	} else unterminated: {
1395	ip.pos = ip.content.len;
1396	break :unterminated ip.content.len;
1397	};
1398
1399	var content = if (start < ip.content.len)
1400	ip.content[start..end]
1401	else
1402	"";
1403	// This single space removal rule allows code spans to be written which
1404	// start or end with backticks.
1405	if (mem.startsWith(u8, content, " `")) content = content[1..];
1406	if (mem.endsWith(u8, content, "` ")) content = content[0 .. content.len - 1];
1407
1408	const text = try ip.parent.addNode(.{
1409	.tag = .code_span,
1410	.data = .{ .text = .{
1411	.content = try ip.parent.addString(content),
1412	} },
1413	});
1414	try ip.completed_inlines.append(ip.parent.allocator, .{
1415	.node = text,
1416	.start = opener_start,
1417	.len = ip.pos - opener_start,
1418	});
1419	// Ensure ip.pos is pointing at the last character of the
1420	// closer, not after it.
1421	ip.pos -= 1;
1422	}
1423
1424	/// Encodes children parsed in the content range `start..end`. The children
1425	/// will be text nodes and any completed inlines within the range.
1426	fn encodeChildren(ip: *InlineParser, start: usize, end: usize) !ExtraIndex {
1427	const scratch_extra_top = ip.parent.scratch_extra.items.len;
1428	defer ip.parent.scratch_extra.shrinkRetainingCapacity(scratch_extra_top);
1429
1430	var child_index = ip.completed_inlines.items.len;
1431	while (child_index > 0 and ip.completed_inlines.items[child_index - 1].start >= start) {
1432	child_index -= 1;
1433	}
1434	const start_child_index = child_index;
1435
1436	var pos = start;
1437	while (child_index < ip.completed_inlines.items.len) : (child_index += 1) {
1438	const child_inline = ip.completed_inlines.items[child_index];
1439	// Completed inlines must be strictly nested within the encodable
1440	// content.
1441	assert(child_inline.start >= pos and child_inline.start + child_inline.len <= end);
1442
1443	if (child_inline.start > pos) {
1444	try ip.encodeTextNode(pos, child_inline.start);
1445	}
1446	try ip.parent.addScratchExtraNode(child_inline.node);
1447
1448	pos = child_inline.start + child_inline.len;
1449	}
1450	ip.completed_inlines.shrinkRetainingCapacity(start_child_index);
1451
1452	if (pos < end) {
1453	try ip.encodeTextNode(pos, end);
1454	}
1455
1456	const children = ip.parent.scratch_extra.items[scratch_extra_top..];
1457	return try ip.parent.addExtraChildren(@ptrCast(children));
1458	}
1459
1460	/// Encodes textual content `ip.content[start..end]` to `scratch_extra`. The
1461	/// encoded content may include both `text` and `line_break` nodes.
1462	fn encodeTextNode(ip: *InlineParser, start: usize, end: usize) !void {
1463	// For efficiency, we can encode directly into string_bytes rather than
1464	// creating a temporary string and then encoding it, since this process
1465	// is entirely linear.
1466	const string_top = ip.parent.string_bytes.items.len;
1467	errdefer ip.parent.string_bytes.shrinkRetainingCapacity(string_top);
1468
1469	var string_start = string_top;
1470	var text_iter: TextIterator = .{ .content = ip.content[start..end] };
1471	while (text_iter.next()) |content| {
1472	switch (content) {
1473	.char => |c| try ip.parent.string_bytes.append(ip.parent.allocator, c),
1474	.text => |s| try ip.parent.string_bytes.appendSlice(ip.parent.allocator, s),
1475	.line_break => {
1476	if (ip.parent.string_bytes.items.len > string_start) {
1477	try ip.parent.string_bytes.append(ip.parent.allocator, 0);
1478	try ip.parent.addScratchExtraNode(try ip.parent.addNode(.{
1479	.tag = .text,
1480	.data = .{ .text = .{
1481	.content = @fromBackingInt(@intCast(string_start)),
1482	} },
1483	}));
1484	string_start = ip.parent.string_bytes.items.len;
1485	}
1486	try ip.parent.addScratchExtraNode(try ip.parent.addNode(.{
1487	.tag = .line_break,
1488	.data = .{ .none = {} },
1489	}));
1490	},
1491	}
1492	}
1493	if (ip.parent.string_bytes.items.len > string_start) {
1494	try ip.parent.string_bytes.append(ip.parent.allocator, 0);
1495	try ip.parent.addScratchExtraNode(try ip.parent.addNode(.{
1496	.tag = .text,
1497	.data = .{ .text = .{
1498	.content = @fromBackingInt(@intCast(string_start)),
1499	} },
1500	}));
1501	}
1502	}
1503
1504	/// An iterator over parts of textual content, handling unescaping of
1505	/// escaped characters and line breaks.
1506	const TextIterator = struct {
1507	content: []const u8,
1508	pos: usize = 0,
1509
1510	const Content = union(enum) {
1511	char: u8,
1512	text: []const u8,
1513	line_break,
1514	};
1515
1516	const replacement = "\u{FFFD}";
1517
1518	fn next(iter: *TextIterator) ?Content {
1519	if (iter.pos >= iter.content.len) return null;
1520	if (iter.content[iter.pos] == '\\') {
1521	iter.pos += 1;
1522	if (iter.pos == iter.content.len) {
1523	return .{ .char = '\\' };
1524	} else if (iter.content[iter.pos] == '\n') {
1525	iter.pos += 1;
1526	return .line_break;
1527	} else if (isPunctuation(iter.content[iter.pos])) {
1528	const c = iter.content[iter.pos];
1529	iter.pos += 1;
1530	return .{ .char = c };
1531	} else {
1532	return .{ .char = '\\' };
1533	}
1534	}
1535	return iter.nextCodepoint();
1536	}
1537
1538	fn nextCodepoint(iter: *TextIterator) ?Content {
1539	switch (iter.content[iter.pos]) {
1540	0 => {
1541	iter.pos += 1;
1542	return .{ .text = replacement };
1543	},
1544	1...127 => |c| {
1545	iter.pos += 1;
1546	return .{ .char = c };
1547	},
1548	else => |b| {
1549	const cp_len = std.unicode.utf8ByteSequenceLength(b) catch {
1550	iter.pos += 1;
1551	return .{ .text = replacement };
1552	};
1553	const is_valid = iter.pos + cp_len <= iter.content.len and
1554	std.unicode.utf8ValidateSlice(iter.content[iter.pos..][0..cp_len]);
1555	const cp_encoded = if (is_valid)
1556	iter.content[iter.pos..][0..cp_len]
1557	else
1558	replacement;
1559	iter.pos += cp_len;
1560	return .{ .text = cp_encoded };
1561	},
1562	}
1563	}
1564	};
1565	};
1566
1567	fn parseInlines(p: *Parser, content: []const u8) !ExtraIndex {
1568	var ip: InlineParser = .{
1569	.parent = p,
1570	.content = mem.trim(u8, content, " \t\n"),
1571	};
1572	defer ip.deinit();
1573	return try ip.parse();
1574	}
1575
1576	pub fn extraData(p: Parser, comptime T: type, index: ExtraIndex) ExtraData(T) {
1577	const info = @typeInfo(T).@"struct";
1578	var i: usize = @backingInt(index);
1579	var result: T = undefined;
1580	inline for (info.field_names, info.field_types) |field_name, field_type| {
1581	@field(result, field_name) = switch (field_type) {
1582	u32 => p.extra.items[i],
1583	else => @compileError("bad field type"),
1584	};
1585	i += 1;
1586	}
1587	return .{ .data = result, .end = i };
1588	}
1589
1590	pub fn extraChildren(p: Parser, index: ExtraIndex) []const Node.Index {
1591	const children = p.extraData(Node.Children, index);
1592	return @ptrCast(p.extra.items[children.end..][0..children.data.len]);
1593	}
1594
1595	fn addNode(p: *Parser, node: Node) !Node.Index {
1596	const index: Node.Index = @fromBackingInt(@intCast(@as(u32, @intCast(p.nodes.len))));
1597	try p.nodes.append(p.allocator, node);
1598	return index;
1599	}
1600
1601	fn addString(p: *Parser, s: []const u8) !StringIndex {
1602	if (s.len == 0) return .empty;
1603
1604	const index: StringIndex = @fromBackingInt(@intCast(@as(u32, @intCast(p.string_bytes.items.len))));
1605	try p.string_bytes.ensureUnusedCapacity(p.allocator, s.len + 1);
1606	p.string_bytes.appendSliceAssumeCapacity(s);
1607	p.string_bytes.appendAssumeCapacity(0);
1608	return index;
1609	}
1610
1611	fn addExtraChildren(p: *Parser, nodes: []const Node.Index) !ExtraIndex {
1612	const index: ExtraIndex = @fromBackingInt(@intCast(@as(u32, @intCast(p.extra.items.len))));
1613	try p.extra.ensureUnusedCapacity(p.allocator, nodes.len + 1);
1614	p.extra.appendAssumeCapacity(@intCast(nodes.len));
1615	p.extra.appendSliceAssumeCapacity(@ptrCast(nodes));
1616	return index;
1617	}
1618
1619	fn addScratchExtraNode(p: *Parser, node: Node.Index) !void {
1620	try p.scratch_extra.append(p.allocator, @backingInt(node));
1621	}
1622
1623	fn addScratchStringLine(p: *Parser, line: []const u8) !void {
1624	try p.scratch_string.ensureUnusedCapacity(p.allocator, line.len + 1);
1625	p.scratch_string.appendSliceAssumeCapacity(line);
1626	p.scratch_string.appendAssumeCapacity('\n');
1627	}
1628
1629	fn isBlank(line: []const u8) bool {
1630	return mem.findNone(u8, line, " \t") == null;
1631	}
1632
1633	fn isPunctuation(c: u8) bool {
1634	return switch (c) {
1635	'!',
1636	'"',
1637	'#',
1638	'$',
1639	'%',
1640	'&',
1641	'\'',
1642	'(',
1643	')',
1644	'*',
1645	'+',
1646	',',
1647	'-',
1648	'.',
1649	'/',
1650	':',
1651	';',
1652	'<',
1653	'=',
1654	'>',
1655	'?',
1656	'@',
1657	'[',
1658	'\\',
1659	']',
1660	'^',
1661	'_',
1662	'`',
1663	'{',
1664	'|',
1665	'}',
1666	'~',
1667	=> true,
1668	else => false,
1669	};
1670	}