InlineParser

const InlineParser = struct

File

Code

const InlineParser = struct {
    parent: *Parser,
    content: []const u8,
    pos: usize = 0,
    pending_inlines: ArrayList(PendingInline) = .empty,
    completed_inlines: ArrayList(CompletedInline) = .empty,

    const PendingInline = struct {
        tag: Tag,
        data: Data,
        start: usize,

        const Tag = enum {
            /// Data is `emphasis`.
            emphasis,
            /// Data is `none`.
            link,
            /// Data is `none`.
            image,
        };

        const Data = union {
            none: void,
            emphasis: struct {
                underscore: bool,
                run_len: usize,
            },
        };
    };

    const CompletedInline = struct {
        node: Node.Index,
        start: usize,
        len: usize,
    };

    fn deinit(ip: *InlineParser) void {
        ip.pending_inlines.deinit(ip.parent.allocator);
        ip.completed_inlines.deinit(ip.parent.allocator);
    }

    /// Parses all of `ip.content`, returning the children of the node
    /// containing the inline content.
    fn parse(ip: *InlineParser) Allocator.Error!ExtraIndex {
        while (ip.pos < ip.content.len) : (ip.pos += 1) {
            switch (ip.content[ip.pos]) {
                '\\' => ip.pos += 1,
                '[' => try ip.pending_inlines.append(ip.parent.allocator, .{
                    .tag = .link,
                    .data = .{ .none = {} },
                    .start = ip.pos,
                }),
                '!' => if (ip.pos + 1 < ip.content.len and ip.content[ip.pos + 1] == '[') {
                    try ip.pending_inlines.append(ip.parent.allocator, .{
                        .tag = .image,
                        .data = .{ .none = {} },
                        .start = ip.pos,
                    });
                    ip.pos += 1;
                },
                ']' => try ip.parseLink(),
                '<' => try ip.parseAutolink(),
                '*', '_' => try ip.parseEmphasis(),
                '`' => try ip.parseCodeSpan(),
                'h' => if (ip.pos == 0 or isPreTextAutolink(ip.content[ip.pos - 1])) {
                    try ip.parseTextAutolink();
                },
                else => {},
            }
        }

        const children = try ip.encodeChildren(0, ip.content.len);
        // There may be pending inlines after parsing (e.g. unclosed emphasis
        // runs), but there must not be any completed inlines, since those
        // should all be part of `children`.
        assert(ip.completed_inlines.items.len == 0);
        return children;
    }

    /// Parses a link, starting at the `]` at the end of the link text. `ip.pos`
    /// is left at the closing `)` of the link target or at the closing `]` if
    /// there is none.
    fn parseLink(ip: *InlineParser) !void {
        var i = ip.pending_inlines.items.len;
        while (i > 0) {
            i -= 1;
            if (ip.pending_inlines.items[i].tag == .link or
                ip.pending_inlines.items[i].tag == .image) break;
        } else return;
        const opener = ip.pending_inlines.items[i];
        ip.pending_inlines.shrinkRetainingCapacity(i);
        const text_start = switch (opener.tag) {
            .link => opener.start + 1,
            .image => opener.start + 2,
            else => unreachable,
        };

        if (ip.pos + 1 >= ip.content.len or ip.content[ip.pos + 1] != '(') return;
        const text_end = ip.pos;

        const target_start = text_end + 2;
        var target_end = target_start;
        var nesting_level: usize = 1;
        while (target_end < ip.content.len) : (target_end += 1) {
            switch (ip.content[target_end]) {
                '\\' => target_end += 1,
                '(' => nesting_level += 1,
                ')' => {
                    if (nesting_level == 1) break;
                    nesting_level -= 1;
                },
                else => {},
            }
        } else return;
        ip.pos = target_end;

        const children = try ip.encodeChildren(text_start, text_end);
        const target = try ip.encodeLinkTarget(target_start, target_end);

        const link = try ip.parent.addNode(.{
            .tag = switch (opener.tag) {
                .link => .link,
                .image => .image,
                else => unreachable,
            },
            .data = .{ .link = .{
                .target = target,
                .children = children,
            } },
        });
        try ip.completed_inlines.append(ip.parent.allocator, .{
            .node = link,
            .start = opener.start,
            .len = ip.pos - opener.start + 1,
        });
    }

    fn encodeLinkTarget(ip: *InlineParser, start: usize, end: usize) !StringIndex {
        // For efficiency, we can encode directly into string_bytes rather than
        // creating a temporary string and then encoding it, since this process
        // is entirely linear.
        const string_top = ip.parent.string_bytes.items.len;
        errdefer ip.parent.string_bytes.shrinkRetainingCapacity(string_top);

        var text_iter: TextIterator = .{ .content = ip.content[start..end] };
        while (text_iter.next()) |content| {
            switch (content) {
                .char => |c| try ip.parent.string_bytes.append(ip.parent.allocator, c),
                .text => |s| try ip.parent.string_bytes.appendSlice(ip.parent.allocator, s),
                .line_break => try ip.parent.string_bytes.appendSlice(ip.parent.allocator, "\\\n"),
            }
        }
        try ip.parent.string_bytes.append(ip.parent.allocator, 0);
        return @fromBackingInt(@intCast(string_top));
    }

    /// Parses an autolink, starting at the opening `<`. `ip.pos` is left at the
    /// closing `>`, or remains unchanged at the opening `<` if there is none.
    fn parseAutolink(ip: *InlineParser) !void {
        const start = ip.pos;
        ip.pos += 1;
        var state: enum {
            start,
            scheme,
            target,
        } = .start;
        while (ip.pos < ip.content.len) : (ip.pos += 1) {
            switch (state) {
                .start => switch (ip.content[ip.pos]) {
                    'A'...'Z', 'a'...'z' => state = .scheme,
                    else => break,
                },
                .scheme => switch (ip.content[ip.pos]) {
                    'A'...'Z', 'a'...'z', '0'...'9', '+', '.', '-' => {},
                    ':' => state = .target,
                    else => break,
                },
                .target => switch (ip.content[ip.pos]) {
                    '<', ' ', '\t', '\n' => break, // Not allowed in autolinks
                    '>' => {
                        // Backslash escapes are not recognized in autolink targets.
                        const target = try ip.parent.addString(ip.content[start + 1 .. ip.pos]);
                        const node = try ip.parent.addNode(.{
                            .tag = .autolink,
                            .data = .{ .text = .{
                                .content = target,
                            } },
                        });
                        try ip.completed_inlines.append(ip.parent.allocator, .{
                            .node = node,
                            .start = start,
                            .len = ip.pos - start + 1,
                        });
                        return;
                    },
                    else => {},
                },
            }
        }
        ip.pos = start;
    }

    /// Parses a plain text autolink (not delimited by `<>`), starting at the
    /// first character in the link (an `h`). `ip.pos` is left at the last
    /// character of the link, or remains unchanged if there is no valid link.
    fn parseTextAutolink(ip: *InlineParser) !void {
        const start = ip.pos;
        var state: union(enum) {
            /// Inside `http`. Contains the rest of the text to be matched.
            http: []const u8,
            after_http,
            after_https,
            /// Inside `://`. Contains the rest of the text to be matched.
            authority: []const u8,
            /// Inside link content.
            content: struct {
                start: usize,
                paren_nesting: usize,
            },
        } = .{ .http = "http" };

        while (ip.pos < ip.content.len) : (ip.pos += 1) {
            switch (state) {
                .http => |rest| {
                    if (ip.content[ip.pos] != rest[0]) break;
                    if (rest.len > 1) {
                        state = .{ .http = rest[1..] };
                    } else {
                        state = .after_http;
                    }
                },
                .after_http => switch (ip.content[ip.pos]) {
                    's' => state = .after_https,
                    ':' => state = .{ .authority = "//" },
                    else => break,
                },
                .after_https => switch (ip.content[ip.pos]) {
                    ':' => state = .{ .authority = "//" },
                    else => break,
                },
                .authority => |rest| {
                    if (ip.content[ip.pos] != rest[0]) break;
                    if (rest.len > 1) {
                        state = .{ .authority = rest[1..] };
                    } else {
                        state = .{ .content = .{
                            .start = ip.pos + 1,
                            .paren_nesting = 0,
                        } };
                    }
                },
                .content => |*content| switch (ip.content[ip.pos]) {
                    ' ', '\t', '\n' => break,
                    '(' => content.paren_nesting += 1,
                    ')' => if (content.paren_nesting == 0) {
                        break;
                    } else {
                        content.paren_nesting -= 1;
                    },
                    else => {},
                },
            }
        }

        switch (state) {
            .http, .after_http, .after_https, .authority => {
                ip.pos = start;
            },
            .content => |content| {
                while (ip.pos > content.start and isPostTextAutolink(ip.content[ip.pos - 1])) {
                    ip.pos -= 1;
                }
                if (ip.pos == content.start) {
                    ip.pos = start;
                    return;
                }

                const target = try ip.parent.addString(ip.content[start..ip.pos]);
                const node = try ip.parent.addNode(.{
                    .tag = .autolink,
                    .data = .{ .text = .{
                        .content = target,
                    } },
                });
                try ip.completed_inlines.append(ip.parent.allocator, .{
                    .node = node,
                    .start = start,
                    .len = ip.pos - start,
                });
                ip.pos -= 1;
            },
        }
    }

    /// Returns whether `c` may appear before a text autolink is recognized.
    fn isPreTextAutolink(c: u8) bool {
        return switch (c) {
            ' ', '\t', '\n', '*', '_', '(' => true,
            else => false,
        };
    }

    /// Returns whether `c` is punctuation that may appear after a text autolink
    /// and not be considered part of it.
    fn isPostTextAutolink(c: u8) bool {
        return switch (c) {
            '?', '!', '.', ',', ':', '*', '_' => true,
            else => false,
        };
    }

    /// Parses emphasis, starting at the beginning of a run of `*` or `_`
    /// characters. `ip.pos` is left at the last character in the run after
    /// parsing.
    fn parseEmphasis(ip: *InlineParser) !void {
        const char = ip.content[ip.pos];
        var start = ip.pos;
        while (ip.pos + 1 < ip.content.len and ip.content[ip.pos + 1] == char) {
            ip.pos += 1;
        }
        var len = ip.pos - start + 1;
        const underscore = char == '_';
        const space_before = start == 0 or isWhitespace(ip.content[start - 1]);
        const space_after = start + len == ip.content.len or isWhitespace(ip.content[start + len]);
        const punct_before = start == 0 or isPunctuation(ip.content[start - 1]);
        const punct_after = start + len == ip.content.len or isPunctuation(ip.content[start + len]);
        // The rules for when emphasis may be closed or opened are stricter for
        // underscores to avoid inappropriately interpreting snake_case words as
        // containing emphasis markers.
        const can_open = if (underscore)
            !space_after and (space_before or punct_before)
        else
            !space_after;
        const can_close = if (underscore)
            !space_before and (space_after or punct_after)
        else
            !space_before;

        if (can_close and ip.pending_inlines.items.len > 0) {
            var i = ip.pending_inlines.items.len;
            while (i > 0 and len > 0) {
                i -= 1;
                const opener = &ip.pending_inlines.items[i];
                if (opener.tag != .emphasis or
                    opener.data.emphasis.underscore != underscore) continue;

                const close_len = @min(opener.data.emphasis.run_len, len);
                const opener_end = opener.start + opener.data.emphasis.run_len;

                const emphasis = try ip.encodeEmphasis(opener_end, start, close_len);
                const emphasis_start = opener_end - close_len;
                const emphasis_len = start - emphasis_start + close_len;
                try ip.completed_inlines.append(ip.parent.allocator, .{
                    .node = emphasis,
                    .start = emphasis_start,
                    .len = emphasis_len,
                });

                // There may still be other openers further down in the
                // stack to close, or part of this run might serve as an
                // opener itself.
                start += close_len;
                len -= close_len;

                // Remove any pending inlines above this on the stack, since
                // closing this emphasis will prevent them from being closed.
                // Additionally, if this opener is completely consumed by
                // being closed, it can be removed.
                opener.data.emphasis.run_len -= close_len;
                if (opener.data.emphasis.run_len == 0) {
                    ip.pending_inlines.shrinkRetainingCapacity(i);
                } else {
                    ip.pending_inlines.shrinkRetainingCapacity(i + 1);
                }
            }
        }

        if (can_open and len > 0) {
            try ip.pending_inlines.append(ip.parent.allocator, .{
                .tag = .emphasis,
                .data = .{ .emphasis = .{
                    .underscore = underscore,
                    .run_len = len,
                } },
                .start = start,
            });
        }
    }

    /// Encodes emphasis specified by a run of `run_len` emphasis characters,
    /// with `start..end` being the range of content contained within the
    /// emphasis.
    fn encodeEmphasis(ip: *InlineParser, start: usize, end: usize, run_len: usize) !Node.Index {
        const children = try ip.encodeChildren(start, end);
        var inner = switch (run_len % 3) {
            1 => try ip.parent.addNode(.{
                .tag = .emphasis,
                .data = .{ .container = .{
                    .children = children,
                } },
            }),
            2 => try ip.parent.addNode(.{
                .tag = .strong,
                .data = .{ .container = .{
                    .children = children,
                } },
            }),
            0 => strong_emphasis: {
                const strong = try ip.parent.addNode(.{
                    .tag = .strong,
                    .data = .{ .container = .{
                        .children = children,
                    } },
                });
                break :strong_emphasis try ip.parent.addNode(.{
                    .tag = .emphasis,
                    .data = .{ .container = .{
                        .children = try ip.parent.addExtraChildren(&.{strong}),
                    } },
                });
            },
            else => unreachable,
        };

        var run_left = run_len;
        while (run_left > 3) : (run_left -= 3) {
            const strong = try ip.parent.addNode(.{
                .tag = .strong,
                .data = .{ .container = .{
                    .children = try ip.parent.addExtraChildren(&.{inner}),
                } },
            });
            inner = try ip.parent.addNode(.{
                .tag = .emphasis,
                .data = .{ .container = .{
                    .children = try ip.parent.addExtraChildren(&.{strong}),
                } },
            });
        }

        return inner;
    }

    /// Parses a code span, starting at the beginning of the opening backtick
    /// run. `ip.pos` is left at the last character in the closing run after
    /// parsing.
    fn parseCodeSpan(ip: *InlineParser) !void {
        const opener_start = ip.pos;
        ip.pos = mem.indexOfNonePos(u8, ip.content, ip.pos, "`") orelse ip.content.len;
        const opener_len = ip.pos - opener_start;

        const start = ip.pos;
        const end = while (mem.indexOfScalarPos(u8, ip.content, ip.pos, '`')) |closer_start| {
            ip.pos = mem.indexOfNonePos(u8, ip.content, closer_start, "`") orelse ip.content.len;
            const closer_len = ip.pos - closer_start;

            if (closer_len == opener_len) break closer_start;
        } else unterminated: {
            ip.pos = ip.content.len;
            break :unterminated ip.content.len;
        };

        var content = if (start < ip.content.len)
            ip.content[start..end]
        else
            "";
        // This single space removal rule allows code spans to be written which
        // start or end with backticks.
        if (mem.startsWith(u8, content, " `")) content = content[1..];
        if (mem.endsWith(u8, content, "` ")) content = content[0 .. content.len - 1];

        const text = try ip.parent.addNode(.{
            .tag = .code_span,
            .data = .{ .text = .{
                .content = try ip.parent.addString(content),
            } },
        });
        try ip.completed_inlines.append(ip.parent.allocator, .{
            .node = text,
            .start = opener_start,
            .len = ip.pos - opener_start,
        });
        // Ensure ip.pos is pointing at the last character of the
        // closer, not after it.
        ip.pos -= 1;
    }

    /// Encodes children parsed in the content range `start..end`. The children
    /// will be text nodes and any completed inlines within the range.
    fn encodeChildren(ip: *InlineParser, start: usize, end: usize) !ExtraIndex {
        const scratch_extra_top = ip.parent.scratch_extra.items.len;
        defer ip.parent.scratch_extra.shrinkRetainingCapacity(scratch_extra_top);

        var child_index = ip.completed_inlines.items.len;
        while (child_index > 0 and ip.completed_inlines.items[child_index - 1].start >= start) {
            child_index -= 1;
        }
        const start_child_index = child_index;

        var pos = start;
        while (child_index < ip.completed_inlines.items.len) : (child_index += 1) {
            const child_inline = ip.completed_inlines.items[child_index];
            // Completed inlines must be strictly nested within the encodable
            // content.
            assert(child_inline.start >= pos and child_inline.start + child_inline.len <= end);

            if (child_inline.start > pos) {
                try ip.encodeTextNode(pos, child_inline.start);
            }
            try ip.parent.addScratchExtraNode(child_inline.node);

            pos = child_inline.start + child_inline.len;
        }
        ip.completed_inlines.shrinkRetainingCapacity(start_child_index);

        if (pos < end) {
            try ip.encodeTextNode(pos, end);
        }

        const children = ip.parent.scratch_extra.items[scratch_extra_top..];
        return try ip.parent.addExtraChildren(@ptrCast(children));
    }

    /// Encodes textual content `ip.content[start..end]` to `scratch_extra`. The
    /// encoded content may include both `text` and `line_break` nodes.
    fn encodeTextNode(ip: *InlineParser, start: usize, end: usize) !void {
        // For efficiency, we can encode directly into string_bytes rather than
        // creating a temporary string and then encoding it, since this process
        // is entirely linear.
        const string_top = ip.parent.string_bytes.items.len;
        errdefer ip.parent.string_bytes.shrinkRetainingCapacity(string_top);

        var string_start = string_top;
        var text_iter: TextIterator = .{ .content = ip.content[start..end] };
        while (text_iter.next()) |content| {
            switch (content) {
                .char => |c| try ip.parent.string_bytes.append(ip.parent.allocator, c),
                .text => |s| try ip.parent.string_bytes.appendSlice(ip.parent.allocator, s),
                .line_break => {
                    if (ip.parent.string_bytes.items.len > string_start) {
                        try ip.parent.string_bytes.append(ip.parent.allocator, 0);
                        try ip.parent.addScratchExtraNode(try ip.parent.addNode(.{
                            .tag = .text,
                            .data = .{ .text = .{
                                .content = @fromBackingInt(@intCast(string_start)),
                            } },
                        }));
                        string_start = ip.parent.string_bytes.items.len;
                    }
                    try ip.parent.addScratchExtraNode(try ip.parent.addNode(.{
                        .tag = .line_break,
                        .data = .{ .none = {} },
                    }));
                },
            }
        }
        if (ip.parent.string_bytes.items.len > string_start) {
            try ip.parent.string_bytes.append(ip.parent.allocator, 0);
            try ip.parent.addScratchExtraNode(try ip.parent.addNode(.{
                .tag = .text,
                .data = .{ .text = .{
                    .content = @fromBackingInt(@intCast(string_start)),
                } },
            }));
        }
    }

    /// An iterator over parts of textual content, handling unescaping of
    /// escaped characters and line breaks.
    const TextIterator = struct {
        content: []const u8,
        pos: usize = 0,

        const Content = union(enum) {
            char: u8,
            text: []const u8,
            line_break,
        };

        const replacement = "\u{FFFD}";

        fn next(iter: *TextIterator) ?Content {
            if (iter.pos >= iter.content.len) return null;
            if (iter.content[iter.pos] == '\\') {
                iter.pos += 1;
                if (iter.pos == iter.content.len) {
                    return .{ .char = '\\' };
                } else if (iter.content[iter.pos] == '\n') {
                    iter.pos += 1;
                    return .line_break;
                } else if (isPunctuation(iter.content[iter.pos])) {
                    const c = iter.content[iter.pos];
                    iter.pos += 1;
                    return .{ .char = c };
                } else {
                    return .{ .char = '\\' };
                }
            }
            return iter.nextCodepoint();
        }

        fn nextCodepoint(iter: *TextIterator) ?Content {
            switch (iter.content[iter.pos]) {
                0 => {
                    iter.pos += 1;
                    return .{ .text = replacement };
                },
                1...127 => |c| {
                    iter.pos += 1;
                    return .{ .char = c };
                },
                else => |b| {
                    const cp_len = std.unicode.utf8ByteSequenceLength(b) catch {
                        iter.pos += 1;
                        return .{ .text = replacement };
                    };
                    const is_valid = iter.pos + cp_len <= iter.content.len and
                        std.unicode.utf8ValidateSlice(iter.content[iter.pos..][0..cp_len]);
                    const cp_encoded = if (is_valid)
                        iter.content[iter.pos..][0..cp_len]
                    else
                        replacement;
                    iter.pos += cp_len;
                    return .{ .text = cp_encoded };
                },
            }
        }
    };
}