markdown_syntax/

parse.rs

//! Markdown source to AST. The entry point is the free [`parse`] function,
//! which reads the crate's one syntax. Parsing is tolerant: problems are
//! collected as [`Diagnostic`]s rather than aborting.

use alloc::{borrow::Cow, collections::BTreeMap, string::String, vec, vec::Vec};

use crate::{
    ast::*,
    decode::{
        decode_escapes_and_references, decode_selected_escapes_and_references,
        parse_character_reference,
    },
    diagnostic::{Diagnostic, DiagnosticCode, DiagnosticSeverity},
    memo::{
        bracket_walk, path_walk, pattern_starts, BracketMemo, BracketStep, PathMemo, Positions,
        Step,
    },
    span::Span,
    validate::is_directive_name,
};

mod blank_lines;
mod blocks;
mod nul_replacement;
#[cfg(test)]
mod scan_tests;
mod source_map;
mod tags;
mod tokens;

pub(crate) use blocks::{
    html_block_ends_at_blank_line, html_block_left_open, html_block_opens, interrupts_paragraph,
};
use source_map::{DerivedText, Segment, SourceMap};

/// The largest ordered-list item number: a marker holds at most 9 digits.
pub(crate) const MAX_ORDERED_NUMBER: u64 = 999_999_999;

/// The result of a tolerant parse: the document plus any diagnostics gathered
/// along the way (empty on a clean parse).
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct ParseOutput {
    /// The parsed document tree.
    pub document: Document,
    /// Diagnostics collected during parsing.
    pub diagnostics: Vec<Diagnostic>,
}

#[derive(Clone, Debug, Eq, PartialEq)]
struct ParsedLinkResource {
    destination: String,
    destination_kind: LinkDestinationKind,
    title: Option<Title>,
}

/// Where a link's destination and title lie in the input the tail was read
/// from: the destination without its angle brackets, empty where it is
/// omitted, and the title without its delimiters.
#[derive(Clone, Copy)]
struct LinkTailRanges {
    destination: (usize, usize),
    title: Option<(usize, usize)>,
}

const REFERENCE_LABEL_MAX_CHARS: usize = 999;
const WIKILINK_MAX_BYTES: usize = 999;

/// One line of the text a block parser reads. `start`, `end`, and
/// `end_with_eol` are positions in the original input; offsets into `text`
/// translate to the input through `source_start` / `source_end`, since a
/// container's lines are derived from its source lines with prefixes removed.
#[derive(Clone, Copy, Debug)]
struct Line<'a> {
    text: &'a str,
    eol: &'a str,
    start: usize,
    end: usize,
    end_with_eol: usize,
    /// The source-map segments covering `text` and `eol`, in the coordinates of
    /// the string the line was split from, where `text` starts at `text_offset`.
    segments: &'a [Segment],
    text_offset: usize,
    /// The source column `text` starts at, from which its tabs reach their
    /// tab stops (every four columns).
    column: usize,
}

impl<'a> Line<'a> {
    /// A line checked for its shape alone, whose positions are not used.
    fn detached(text: &'a str) -> Self {
        Line {
            text,
            eol: "",
            start: 0,
            end: text.len(),
            end_with_eol: text.len(),
            segments: &[],
            text_offset: 0,
            column: 0,
        }
    }

    /// The source column after `self.text[..offset]`.
    fn column_at(&self, offset: usize) -> usize {
        advance_columns(self.column, &self.text[..offset])
    }

    /// The input position where a node starting at byte `offset` of `text`
    /// starts.
    fn source_start(&self, offset: usize) -> usize {
        source_map::start_of(self.segments, self.text_offset + offset)
    }

    /// The input position where a node ending at byte `offset` of `text` ends.
    fn source_end(&self, offset: usize) -> usize {
        source_map::end_of(self.segments, self.text_offset + offset)
    }

    /// The input range of this line's ending.
    fn eol_source(&self) -> (usize, usize) {
        (self.end, self.end_with_eol)
    }

    /// Records in `map`, from text position `at`, what `text[from..to]` was
    /// read from.
    fn copy_into(&self, map: &mut SourceMap, at: usize, from: usize, to: usize) {
        map.copy(
            at,
            self.segments,
            self.text_offset + from,
            self.text_offset + to,
        );
    }
}

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum HtmlBlockKind {
    RawTag,
    BlockTag,
    Until(&'static str),
    UntilBlank,
}

/// Parse `input`. Infallible and tolerant: problems are reported as
/// diagnostics in the returned [`ParseOutput`].
pub fn parse(input: &str) -> ParseOutput {
    let mut diagnostics = Vec::new();
    // A leading byte order mark is not content; parsing starts after it while
    // spans keep counting from the start of `input`.
    let start = if input.starts_with('\u{feff}') {
        '\u{feff}'.len_utf8()
    } else {
        0
    };
    let source = &input[start..];
    let map = SourceMap::verbatim(source.len(), start);
    let lines = collect_lines(source, &map);
    let mut children = blocks::parse_document(&lines, &mut diagnostics);
    blank_lines::add_blank_lines(input, &mut children);
    let mut document = Document::parsed(
        NodeMeta::new(Some(Span::new(0, input.len()))),
        children,
        input,
    );
    if source.contains('\0') {
        nul_replacement::replace_in_document(&mut document);
    }

    ParseOutput {
        document,
        diagnostics,
    }
}

/// The link reference definitions an inline parse resolves references
/// against: they decide whether `[a][b]`, `[a][]`, and `[a]` are reference
/// links or images.
#[derive(Clone, Debug, Default, Eq, PartialEq)]
pub struct Definitions {
    /// Normalized identifiers, sorted and deduplicated.
    identifiers: Vec<String>,
}

impl Definitions {
    /// The definitions of `document`, at every depth, as `parse` reads them
    /// for the document's own references.
    pub fn of(document: &Document) -> Self {
        fn walk(blocks: &[Block], identifiers: &mut Vec<String>) {
            for block in blocks {
                match block {
                    Block::Definition(node) => identifiers.push(node.identifier.clone()),
                    Block::BlockQuote(node) => walk(&node.children, identifiers),
                    Block::Alert(node) => walk(&node.children, identifiers),
                    Block::List(node) => {
                        for item in &node.children {
                            walk(&item.children, identifiers);
                        }
                    }
                    Block::FootnoteDefinition(node) => walk(&node.children, identifiers),
                    Block::HtmlContainer(node) => {
                        if let HtmlContainerContent::Blocks(children) = &node.content {
                            walk(children, identifiers);
                        }
                    }
                    Block::ContainerDirective(node) => walk(&node.children, identifiers),
                    _ => {}
                }
            }
        }
        let mut identifiers = Vec::new();
        walk(&document.children, &mut identifiers);
        Self::sorted(identifiers)
    }

    /// Definitions with the given labels, as they would be written between
    /// the brackets of a definition.
    pub fn new<I, S>(labels: I) -> Self
    where
        I: IntoIterator<Item = S>,
        S: AsRef<str>,
    {
        Self::sorted(
            labels
                .into_iter()
                .map(|label| identifier(label.as_ref()))
                .collect(),
        )
    }

    fn sorted(mut identifiers: Vec<String>) -> Self {
        identifiers.sort_unstable();
        identifiers.dedup();
        Self { identifiers }
    }

    fn labels(&self) -> Labels<'_> {
        Labels {
            own: &self.identifiers,
        }
    }
}

/// The result of an inline parse: the inlines, the tokens of the text, and
/// any diagnostics.
#[derive(Clone, Debug, Eq, PartialEq)]
#[non_exhaustive]
pub struct InlineOutput {
    /// The inline nodes, with spans that are byte ranges into the text.
    pub inlines: Vec<Inline>,
    /// Runs that tile the text in order, each naming the innermost inline
    /// that holds it and the part of that inline it is.
    pub tokens: Vec<InlineToken>,
    /// Diagnostics collected during parsing.
    pub diagnostics: Vec<Diagnostic>,
}

impl InlineOutput {
    /// The inlines in pre-order through [`Inline::children`]: a link's text,
    /// an image's alt, and a directive's label included. An
    /// [`InlineToken`]'s `node` indexes this list.
    pub fn nodes(&self) -> Vec<&Inline> {
        let mut nodes = Vec::new();
        let mut stack: Vec<&Inline> = self.inlines.iter().rev().collect();
        while let Some(inline) = stack.pop() {
            nodes.push(inline);
            stack.extend(inline.children().iter().rev());
        }
        nodes
    }
}

/// A run of the text of an inline parse: the innermost inline that holds it,
/// as its index in [`InlineOutput::nodes`], and the part of that inline it
/// is.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct InlineToken {
    /// The run, a byte range into the text.
    pub span: Span,
    /// The innermost inline holding the run, as its index in
    /// [`InlineOutput::nodes`].
    pub node: usize,
    /// The part of that inline the run is.
    pub role: TokenRole,
}

/// The part of an inline a token is.
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
#[non_exhaustive]
pub enum TokenRole {
    /// The inline's content: a text node, raw HTML, a soft break, a hard
    /// break's line ending, an escaped character, a character reference
    /// between `&` and `;`, and code or math inside its delimiters apart
    /// from the padding its value drops, which is syntax.
    Text,
    /// A character of the inline's own syntax.
    Syntax,
    /// A link's, image's, or autolink's destination.
    Destination,
    /// A link's or image's title, inside its delimiters.
    Title,
    /// A full reference's second label, a footnote reference's label, or a
    /// wiki link's text after its pipe.
    Label,
    /// A wiki link's target.
    Target,
    /// A directive's, shortcode's, or tag's name.
    Name,
    /// A directive's attributes, inside its braces.
    Attributes,
}

/// Parse `text` as the inline content of one leaf block, with the same
/// syntax as [`parse`] and no block rule: `# a` and `- a` stay text. A
/// reference forms only for a label `definitions` holds. Infallible, like
/// [`parse`]; a leading U+FEFF is content.
pub fn parse_inline(text: &str, definitions: &Definitions) -> InlineOutput {
    read_inline(text, definitions, true)
}

/// What `parse_inline` reads from `text`, without its tokens, for callers
/// that read only the tree.
pub(crate) fn parse_inline_tree(text: &str, definitions: &Definitions) -> InlineOutput {
    read_inline(text, definitions, false)
}

fn read_inline(text: &str, definitions: &Definitions, with_tokens: bool) -> InlineOutput {
    let mut diagnostics = Vec::new();
    // Line endings are read as `\n`, as a block's content is joined, while
    // spans keep counting in `text`.
    let (content, map) = if text.contains('\r') {
        let mut content = String::with_capacity(text.len());
        let mut map = SourceMap::default();
        for line in collect_lines(text, &SourceMap::verbatim(text.len(), 0)) {
            map.push(content.len(), line.text.len(), line.start, line.end);
            content.push_str(line.text);
            if !line.eol.is_empty() {
                map.push(content.len(), 1, line.end, line.end_with_eol);
                content.push('\n');
            }
        }
        (Cow::Owned(content), map)
    } else {
        (Cow::Borrowed(text), SourceMap::verbatim(text.len(), 0))
    };
    let mut tokens = Vec::new();
    let mut inlines = parse_inlines(
        &content,
        &map,
        Some(definitions.labels()),
        &mut diagnostics,
        with_tokens.then_some(&mut tokens),
    );
    if text.contains('\0') {
        nul_replacement::replace_in_inlines(&mut inlines);
    }
    diagnostics.sort_by_key(|diagnostic| diagnostic.span.map(|span| span.start));
    InlineOutput {
        inlines,
        tokens,
        diagnostics,
    }
}

/// The inline content the parser read for one paragraph or heading, from
/// [`Document::inline_source`], with where each of its offsets sits in the
/// document's source.
#[derive(Clone, Debug)]
pub struct InlineSource {
    /// The text the inline pass read: container markers, indentation, and an
    /// ATX heading's opening and closing sequences removed, and lines joined
    /// with `\n`.
    pub text: String,
    map: SourceMap,
}

impl InlineSource {
    /// The source offset of `text[offset..]`; `offset == text.len()` maps to
    /// the end of the leaf's content.
    pub fn to_source(&self, offset: usize) -> usize {
        self.span_to_source(Span::new(offset, offset)).start
    }

    /// The source span of `span`, a span in `text`, as the parser maps the
    /// spans of the inlines it reads from `text`.
    pub fn span_to_source(&self, span: Span) -> Span {
        source_map::translate_span(&self.map, span)
    }
}

/// Maps the spans of `inlines`, read from `source.text`, to the source, as
/// the parser maps a leaf's inlines. The writer uses it; it is public for
/// tests.
#[doc(hidden)]
pub fn inline_spans_to_source(source: &InlineSource, inlines: &mut [Inline]) {
    source_map::translate_inlines(&source.map, inlines, &mut []);
}

impl Document {
    /// The inline content the parser read for the leaf at `path`: a
    /// paragraph, a heading, a table cell (its table's path, its row's index,
    /// and its own), or the label of a leaf or container directive (its
    /// directive's path), read again from the source of the top-level block
    /// holding it, so that the cost is linear in that block. `None` for a
    /// document without a source, or a path that names no such leaf, a
    /// directive without a label, or a node without a span or one the source
    /// does not hold.
    pub fn inline_source(&self, path: &NodePath) -> Option<InlineSource> {
        let source = self.source()?;
        let (&first, rest) = path.0.split_first()?;
        let top = self.children.get(first)?;
        let mut block = top;
        let mut rest = rest.iter();
        let leaf = loop {
            let Some(&index) = rest.next() else {
                break match block {
                    Block::Paragraph(node) => node.meta.span?,
                    Block::Heading(node) => node.meta.span?,
                    Block::LeafDirective(node) => node.meta.span?,
                    Block::ContainerDirective(node) => node.meta.span?,
                    _ => return None,
                };
            };
            block = match block {
                Block::BlockQuote(node) => node.children.get(index)?,
                Block::Alert(node) => node.children.get(index)?,
                Block::FootnoteDefinition(node) => node.children.get(index)?,
                Block::ContainerDirective(node) => node.children.get(index)?,
                Block::HtmlContainer(node) => match &node.content {
                    HtmlContainerContent::Blocks(children) => children.get(index)?,
                    _ => return None,
                },
                Block::List(node) => {
                    let item = node.children.get(index)?;
                    item.children.get(*rest.next()?)?
                }
                Block::Table(node) => {
                    let cell = node.rows.get(index)?.cells.get(*rest.next()?)?;
                    if rest.next().is_some() {
                        return None;
                    }
                    break cell.meta.span?;
                }
                _ => return None,
            };
        };
        let end = top.span()?.end;
        // The top-level block is read with the definitions right before it,
        // which may have opened its paragraph, so that a line reads as a
        // continuation there and not as indented code; and from the start of
        // its line, where it reads as it does in the document.
        let opening = self.children[..first]
            .iter()
            .rev()
            .take_while(|block| matches!(block, Block::Definition(_)))
            .last()
            .unwrap_or(top);
        let start = opening.span()?.start;
        if end > source.len() || start > end || !source.is_char_boundary(start) {
            return None;
        }
        let bytes = source.as_bytes();
        let mut start = start;
        while start > 0 && !matches!(bytes[start - 1], b'\n' | b'\r') {
            start -= 1;
        }
        if start == 0 && source.starts_with('\u{feff}') {
            start = '\u{feff}'.len_utf8().min(end);
        }
        let slice = source.get(start..end)?;
        let map = SourceMap::verbatim(slice.len(), start);
        let lines = collect_lines(slice, &map);
        let (_, text) = blocks::leaf_contents(&lines)
            .into_iter()
            .find(|(span, _)| *span == leaf)?;
        let (text, map) = text.into_parts();
        Some(InlineSource { text, map })
    }

    /// The path and inline source of every leaf of the document, in document
    /// order, each as [`Document::inline_source`] returns it, read in one
    /// pass over the source. Empty for a document without a source.
    pub fn leaf_sources(&self) -> Vec<(NodePath, InlineSource)> {
        let mut found = Vec::new();
        self.each_leaf_source(|path, _, source| found.push((NodePath(path.to_vec()), source)));
        found
    }

    /// Calls `found` with the path, span, and inline source of every leaf of
    /// the document, in document order, as `leaf_sources` returns them.
    pub(crate) fn each_leaf_source(&self, mut found: impl FnMut(&[usize], Span, InlineSource)) {
        let Some(source) = self.source() else {
            return;
        };
        let start = if source.starts_with('\u{feff}') {
            '\u{feff}'.len_utf8()
        } else {
            0
        };
        let map = SourceMap::verbatim(source.len() - start, start);
        let lines = collect_lines(&source[start..], &map);
        let mut contents: Vec<(Span, Option<DerivedText>)> = blocks::leaf_contents(&lines)
            .into_iter()
            .map(|(span, text)| (span, Some(text)))
            .collect();
        // The contents are in document order, so their starts never fall.
        let mut take = |path: &[usize], span: Option<Span>, _: Option<&str>| {
            let Some(span) = span else { return };
            let first = contents.partition_point(|(other, _)| other.start < span.start);
            let entry = contents[first..]
                .iter_mut()
                .take_while(|(other, _)| other.start == span.start)
                .find(|(other, text)| *other == span && text.is_some());
            if let Some((_, text)) = entry {
                let (text, map) = text.take().expect("found unused").into_parts();
                found(path, span, InlineSource { text, map });
            }
        };
        crate::leaves::visit(&self.children, &mut Vec::new(), &mut take);
    }
}

/// CommonMark reads U+0000 as U+FFFD. Character classifications that differ
/// between the two call this; node values are rewritten after parsing by
/// `nul_replacement::replace_in_document`, so spans stay in source coordinates.
fn source_char(char: char) -> char {
    if char == '\0' {
        '\u{FFFD}'
    } else {
        char
    }
}

/// The deepest block-container nesting (block quotes, list items, container
/// directives, footnote definitions, HTML containers) the parser opens. Deeper container markers stay leaf-block text, so recursion
/// and the native stack it uses stay bounded.
pub(crate) const MAX_BLOCK_NESTING: usize = 32;

/// Parses the blocks of a container's derived content.
/// The column `text` reaches from column `column`, with tab stops every four.
fn advance_columns(column: usize, text: &str) -> usize {
    text.chars().fold(column, |column, char| {
        if char == '\t' {
            column + 4 - column % 4
        } else {
            column + 1
        }
    })
}

/// Splits `input` into lines, with positions translated through `map`, the
/// source map of `input`.
fn collect_lines<'a>(input: &'a str, map: &'a SourceMap) -> Vec<Line<'a>> {
    let bytes = input.as_bytes();
    let mut lines = Vec::new();
    let mut segments = LineSegments {
        segments: map.segments(),
        first: 0,
    };
    let mut start = 0;
    let mut index = 0;

    while index < bytes.len() {
        let eol_end = match bytes[index] {
            b'\n' => index + 1,
            b'\r' if bytes.get(index + 1) == Some(&b'\n') => index + 2,
            b'\r' => index + 1,
            _ => {
                index += 1;
                continue;
            }
        };
        lines.push(segments.line(input, start, index, eol_end));
        index = eol_end;
        start = index;
    }

    if start < bytes.len() || input.is_empty() {
        lines.push(segments.line(input, start, bytes.len(), bytes.len()));
    }

    lines
}

/// Hands each line of a split string the segments that cover it, moving
/// forward through the map once.
struct LineSegments<'a> {
    segments: &'a [Segment],
    first: usize,
}

impl<'a> LineSegments<'a> {
    fn line(&mut self, input: &'a str, start: usize, end: usize, eol_end: usize) -> Line<'a> {
        let segments = self.segments;
        while self.first + 1 < segments.len() && segments[self.first].text_end() <= start {
            self.first += 1;
        }
        let mut last = self.first;
        while last + 1 < segments.len() && segments[last + 1].text_start() < eol_end {
            last += 1;
        }
        let covering = if segments.is_empty() {
            segments
        } else {
            &segments[self.first..=last]
        };
        let source_start = source_map::start_of(covering, start);
        let source_end = if end == start {
            source_start
        } else {
            source_map::end_of(covering, end)
        };
        let source_end_with_eol = if eol_end == end {
            source_end
        } else {
            source_map::end_of(covering, eol_end)
        };
        Line {
            text: &input[start..end],
            eol: &input[end..eol_end],
            start: source_start,
            end: source_end,
            end_with_eol: source_end_with_eol,
            segments: covering,
            text_offset: start,
            column: 0,
        }
    }
}

pub(crate) fn frontmatter_fence_kind(line: &str) -> Option<FrontmatterKind> {
    match line.trim_end_matches([' ', '\t']) {
        "---" => Some(FrontmatterKind::Yaml),
        "+++" => Some(FrontmatterKind::Toml),
        _ => None,
    }
}

fn directive_container_opener_prefix(input: &str) -> Option<(usize, &str)> {
    let fence_len = input
        .as_bytes()
        .iter()
        .take_while(|byte| **byte == b':')
        .count();
    if fence_len >= 3 {
        Some((fence_len, &input[fence_len..]))
    } else {
        None
    }
}

fn directive_container_closing_fence(input: &str, min_len: usize) -> Option<usize> {
    let fence_len = input
        .as_bytes()
        .iter()
        .take_while(|byte| **byte == b':')
        .count();
    if fence_len >= min_len && is_blank(&input[fence_len..]) {
        Some(fence_len)
    } else {
        None
    }
}

/// Length of the leading `$` run if `input` (already indent-stripped) is a valid
/// math-flow opener: `>=2` dollars, then an info string with no further `$`.
fn math_block_fence_length(input: &str) -> Option<usize> {
    let length = input
        .as_bytes()
        .iter()
        .take_while(|byte| **byte == b'$')
        .count();
    if length < 2 || input[length..].contains('$') {
        return None;
    }
    Some(length)
}

/// A math-flow closing line (already indent-stripped) is a run of `>=length`
/// dollars and nothing else (trailing whitespace aside).
fn math_block_fence_closes(input: &str, length: usize) -> bool {
    let count = input
        .as_bytes()
        .iter()
        .take_while(|byte| **byte == b'$')
        .count();
    count >= length && is_blank(&input[count..])
}

fn parse_alert_marker(line: &str) -> Option<(AlertKind, Option<String>)> {
    let close = line.find(']')?;
    let marker = line.get(0..close + 1)?;
    if !marker.starts_with("[!") {
        return None;
    }
    let kind = match &marker[2..close].to_ascii_lowercase()[..] {
        "note" => AlertKind::Note,
        "tip" => AlertKind::Tip,
        "important" => AlertKind::Important,
        "warning" => AlertKind::Warning,
        "caution" => AlertKind::Caution,
        _ => return None,
    };
    Some((kind, alert_title(&line[close + 1..])))
}

/// The title an alert marker line gives with `text` after its `]`: the text
/// without the spaces and tabs around it, or none when nothing else is left.
pub(crate) fn alert_title(text: &str) -> Option<String> {
    let title = text.trim_matches([' ', '\t']);
    (!title.is_empty()).then(|| title.into())
}

fn parse_thematic_break(line: Line<'_>) -> Option<Block> {
    let text = trim_up_to_three_spaces(line.text)?;
    let mut marker = None;
    let mut count = 0;
    for char in text.chars() {
        if char == ' ' || char == '\t' {
            continue;
        }
        let current = match char {
            '-' => ThematicBreakMarker::Dash,
            '*' => ThematicBreakMarker::Asterisk,
            '_' => ThematicBreakMarker::Underscore,
            _ => return None,
        };
        if marker.is_some_and(|marker| marker != current) {
            return None;
        }
        marker = Some(current);
        count += 1;
    }
    if count >= 3 {
        Some(Block::ThematicBreak(ThematicBreak {
            meta: NodeMeta::new(Some(Span::new(line.start, line.end))),
            marker: marker?,
        }))
    } else {
        None
    }
}

/// The label of a definition starting paragraph line `index`, followed by
/// `:`: the text of the lines up to the one the label closes on, joined by
/// `\n`, the offset of the label's `]` in it, and that line.
///
/// A label may span lines (CommonMark §4.7), up to its length limit. The
/// walk to its `]` (`find_reference_label_end`) goes on from where the lines
/// before left it, so that a long label is walked once.
fn definition_label(lines: &[Line<'_>], index: usize) -> Option<(String, usize, usize)> {
    let text = trim_ascii_start(lines[index].text);
    if !text.starts_with('[') {
        return None;
    }
    let mut accumulated = String::from(text);
    let mut label_end_line = index;
    let mut cursor = 1;
    loop {
        let bytes = accumulated.as_bytes();
        // The walk has run out of text: it goes on at the `\n` the next line
        // is joined with. A `\` that ended the text escapes that `\n`, and
        // both step to the next line's start.
        if cursor >= bytes.len() {
            let next = label_end_line + 1;
            if next >= lines.len() || accumulated.len() > 4 * REFERENCE_LABEL_MAX_CHARS + 2 {
                return None;
            }
            accumulated.push('\n');
            accumulated.push_str(lines[next].text);
            label_end_line = next;
            continue;
        }
        match reference_label_step(&accumulated, cursor) {
            Step::Next(next) => cursor = next,
            Step::Done(Some(close)) if reference_label_is_within_limit(&accumulated[1..close]) => {
                // A closed label not followed by `:` is not a definition.
                if bytes.get(close + 1) != Some(&b':') {
                    return None;
                }
                return Some((accumulated, close, label_end_line));
            }
            // An unescaped `[`, or a label over the length limit: no line
            // after it makes a definition.
            Step::Done(_) => return None,
        }
    }
}

/// The link reference definition that starts paragraph line `index`, and
/// the line after it. The lines are a paragraph's, each from where the
/// containers around it leave it; the definition's span is left to the
/// caller.
fn parse_definition(lines: &[Line<'_>], index: usize) -> Option<(Definition, usize)> {
    let (accumulated, close, label_end_line) = definition_label(lines, index)?;
    let label = String::from(&accumulated[1..close]);
    if normalize_label(&label).is_empty() {
        return None;
    }
    let mut source = String::from(&accumulated[close + 2..]);
    let mut cursor = label_end_line;
    let mut best_without_title = None;
    // The char that closes a title the source leaves open: a line without
    // it cannot change the parse, so the source is parsed again only once a
    // line holds it, which keeps a long open title linear.
    let mut open_title: Option<char> = None;

    loop {
        let parses =
            open_title.is_none_or(|closer| line_may_close_title(lines[cursor].text, closer));
        if parses {
            match parse_definition_destination_title(&source) {
                Some(resource) => {
                    if resource.title.is_some() {
                        return Some((definition_node(&label, resource), cursor + 1));
                    }
                    best_without_title = Some((resource, cursor + 1));
                    let next = cursor + 1;
                    if next >= lines.len() || !line_can_start_definition_title(lines[next].text) {
                        break;
                    }
                }
                // A destination, or a title once it has closed, that does
                // not parse cannot parse with more lines.
                None if !is_blank(&source) => match open_definition_title(&source) {
                    Some(closer) if open_title.is_none() => open_title = Some(closer),
                    _ => break,
                },
                None => {}
            }
        }
        let next = cursor + 1;
        if next >= lines.len() {
            break;
        }
        source.push('\n');
        source.push_str(lines[next].text);
        cursor = next;
    }

    let (resource, next) = best_without_title?;
    Some((definition_node(&label, resource), next))
}

fn definition_node(label: &str, resource: ParsedLinkResource) -> Definition {
    Definition {
        meta: NodeMeta::default(),
        label: label.into(),
        identifier: normalize_label(label),
        destination: resource.destination,
        destination_kind: resource.destination_kind,
        title: resource.title,
    }
}

#[derive(Clone, Copy, Eq, PartialEq)]
enum HtmlContainerTag {
    Opening,
    Closing,
}

#[derive(Clone, Copy)]
struct HtmlContainerFence {
    marker: FenceMarker,
    length: usize,
}

/// One step of the line walk to an HTML container's closing tag line: a code
/// fence is stepped over whole, and same-name opening and closing tag lines
/// nest.
fn html_container_close_step(lines: &[Line<'_>], cursor: usize, tag: &str) -> BracketStep {
    let Some(line) = lines.get(cursor) else {
        return BracketStep::End;
    };
    if let Some(fence) = html_container_fence_opens(line) {
        let after_fence = (cursor + 1..lines.len())
            .find(|close| html_container_fence_closes(&lines[*close], fence))
            .map_or(lines.len(), |close| close + 1);
        return BracketStep::Pass(after_fence);
    }
    if parse_html_container_tag_line(*line, tag, HtmlContainerTag::Closing).is_some() {
        return BracketStep::Close(cursor + 1);
    }
    if parse_html_container_opening_line(*line, tag).is_some() {
        return BracketStep::Open(cursor + 1);
    }
    BracketStep::Pass(cursor + 1)
}

fn parse_html_container_tag_line(
    line: Line<'_>,
    tag: &str,
    kind: HtmlContainerTag,
) -> Option<HtmlTag> {
    let (trimmed, indent_bytes) = trim_html_container_line(&line)?;
    let (end, name) = parse_html_tag(trimmed, 0)?;
    if !name.eq_ignore_ascii_case(tag) || !is_blank(&trimmed[end..]) {
        return None;
    }

    let closing = html_tag_is_closing(trimmed, 0);
    if (kind == HtmlContainerTag::Opening && closing)
        || (kind == HtmlContainerTag::Closing && !closing)
        || html_tag_is_self_closing(&trimmed[..end])
    {
        return None;
    }

    Some(HtmlTag {
        meta: NodeMeta::new(Some(Span::new(
            line.source_start(indent_bytes),
            line.source_end(indent_bytes + end),
        ))),
        name: tag.into(),
        raw: trimmed[..end].into(),
    })
}

fn parse_html_container_opening_line(line: Line<'_>, tag: &str) -> Option<HtmlTag> {
    let (trimmed, indent_bytes) = trim_html_container_line(&line)?;
    let (end, name) = parse_html_tag(trimmed, 0)?;
    if !name.eq_ignore_ascii_case(tag)
        || html_tag_is_closing(trimmed, 0)
        || html_tag_is_self_closing(&trimmed[..end])
    {
        return None;
    }

    let rest_start = end + leading_ascii_whitespace_len(&trimmed[end..]);
    if !trimmed[rest_start..].is_empty() && !html_container_line_has_summary(&trimmed[rest_start..])
    {
        return None;
    }

    Some(HtmlTag {
        meta: NodeMeta::new(Some(Span::new(
            line.source_start(indent_bytes),
            line.source_end(indent_bytes + end),
        ))),
        name: tag.into(),
        raw: trimmed[..end].into(),
    })
}

fn html_container_line_has_summary(input: &str) -> bool {
    let Some((open_end, name)) = parse_html_tag(input, 0) else {
        return false;
    };
    if !name.eq_ignore_ascii_case("summary")
        || html_tag_is_closing(input, 0)
        || html_tag_is_self_closing(&input[..open_end])
    {
        return false;
    }
    let Some(close_start) = input[open_end..].find("</").map(|offset| open_end + offset) else {
        return false;
    };
    let Some((close_end, close_name)) = parse_html_tag(input, close_start) else {
        return false;
    };
    close_name.eq_ignore_ascii_case("summary")
        && html_tag_is_closing(input, close_start)
        && is_blank(&input[close_end..])
}

/// `line` from its first char other than a space or tab, when its
/// indentation, from the column it starts at, is at most three columns.
fn trim_html_container_line<'a>(line: &Line<'a>) -> Option<(&'a str, usize)> {
    let (columns, bytes) = leading_indent_at(line.text, line.column);
    (columns <= 3).then(|| (&line.text[bytes..], bytes))
}

fn leading_ascii_whitespace_len(input: &str) -> usize {
    input
        .as_bytes()
        .iter()
        .take_while(|byte| byte.is_ascii_whitespace())
        .count()
}

fn html_tag_is_closing(input: &str, index: usize) -> bool {
    input.as_bytes().get(index + 1) == Some(&b'/')
}

fn html_tag_is_self_closing(input: &str) -> bool {
    input.trim_end_matches([' ', '\t']).ends_with("/>")
}

fn html_container_fence_opens(line: &Line<'_>) -> Option<HtmlContainerFence> {
    let (trimmed, _) = trim_html_container_line(line)?;
    let (marker, length) = fence_start(trimmed)?;
    Some(HtmlContainerFence { marker, length })
}

fn html_container_fence_closes(line: &Line<'_>, fence: HtmlContainerFence) -> bool {
    trim_html_container_line(line)
        .is_some_and(|(trimmed, _)| fence_close(trimmed, fence.marker, fence.length))
}

fn html_block_start(input: &str) -> Option<HtmlBlockKind> {
    let trimmed = input.trim_end_matches([' ', '\t']);
    if !trimmed.starts_with('<') {
        return None;
    }

    if raw_html_tag_start(trimmed) {
        return Some(HtmlBlockKind::RawTag);
    }
    if trimmed.starts_with("<!--") {
        return Some(HtmlBlockKind::Until("-->"));
    }
    if trimmed.starts_with("<?") {
        return Some(HtmlBlockKind::Until("?>"));
    }
    if is_declaration_start(trimmed) {
        return Some(HtmlBlockKind::Until(">"));
    }
    if trimmed.starts_with("<![CDATA[") {
        return Some(HtmlBlockKind::Until("]]>"));
    }

    if html_block_tag_start(trimmed) {
        return Some(HtmlBlockKind::BlockTag);
    }

    let Some((end, _tag_name)) = parse_html_tag(trimmed, 0) else {
        return None;
    };
    if is_blank(&trimmed[end..]) {
        Some(HtmlBlockKind::UntilBlank)
    } else {
        None
    }
}

fn raw_html_tag_start(input: &str) -> bool {
    for tag in ["script", "pre", "style", "textarea"] {
        if html_raw_open_tag_prefix(input, tag) {
            return true;
        }
    }
    false
}

fn html_raw_open_tag_prefix(input: &str, tag: &str) -> bool {
    let Some(rest) = input.strip_prefix('<') else {
        return false;
    };
    if rest.starts_with('/') || rest.len() < tag.len() {
        return false;
    }
    let rest_bytes = rest.as_bytes();
    let tag_bytes = tag.as_bytes();
    if !rest_bytes
        .get(..tag_bytes.len())
        .is_some_and(|name| name.eq_ignore_ascii_case(tag_bytes))
    {
        return false;
    }
    match rest_bytes.get(tag.len()) {
        None => true,
        Some(b' ' | b'\t' | b'\n' | b'\r' | b'>') => true,
        Some(b'/') => {
            rest_bytes.get(tag.len() + 1) == Some(&b'>') && rest_bytes.get(tag.len() + 2).is_none()
        }
        _ => false,
    }
}

fn line_contains_raw_closing_tag(input: &str, tag: &str) -> bool {
    let bytes = input.as_bytes();
    let tag_bytes = tag.as_bytes();
    let mut cursor = 0;

    while cursor + 2 + tag_bytes.len() <= bytes.len() {
        let tag_start = cursor + 2;
        let tag_end = tag_start + tag_bytes.len();
        if bytes.get(cursor) == Some(&b'<')
            && bytes.get(cursor + 1) == Some(&b'/')
            && bytes
                .get(tag_start..tag_end)
                .is_some_and(|name| name.eq_ignore_ascii_case(tag_bytes))
        {
            match bytes.get(tag_end) {
                Some(b'>') => return true,
                Some(byte) if byte.is_ascii_whitespace() => {
                    let mut after_space = tag_end;
                    while bytes
                        .get(after_space)
                        .is_some_and(|byte| byte.is_ascii_whitespace())
                    {
                        after_space += 1;
                    }
                    if bytes.get(after_space) == Some(&b'>') {
                        return true;
                    }
                }
                _ => {}
            }
        }
        cursor += 1;
    }

    false
}

fn html_block_tag_start(input: &str) -> bool {
    let bytes = input.as_bytes();
    if bytes.first() != Some(&b'<') {
        return false;
    }

    let mut cursor = 1;
    if bytes.get(cursor) == Some(&b'/') {
        cursor += 1;
    }

    let name_start = cursor;
    if !bytes
        .get(cursor)
        .is_some_and(|byte| byte.is_ascii_alphabetic())
    {
        return false;
    }
    cursor += 1;
    while bytes.get(cursor).is_some_and(|byte| html_name_byte(*byte)) {
        cursor += 1;
    }

    let name = &input[name_start..cursor];
    if !html_block_tag(name) {
        return false;
    }

    match bytes.get(cursor) {
        None | Some(b' ' | b'\t' | b'\n' | b'\r' | b'>') => true,
        Some(b'/') if bytes.get(cursor + 1) == Some(&b'>') => true,
        _ => false,
    }
}

fn html_block_tag(tag: &str) -> bool {
    matches!(
        tag.to_ascii_lowercase().as_str(),
        "address"
            | "article"
            | "aside"
            | "base"
            | "basefont"
            | "blockquote"
            | "body"
            | "caption"
            | "center"
            | "col"
            | "colgroup"
            | "dd"
            | "details"
            | "dialog"
            | "dir"
            | "div"
            | "dl"
            | "dt"
            | "fieldset"
            | "figcaption"
            | "figure"
            | "footer"
            | "form"
            | "frame"
            | "frameset"
            | "h1"
            | "h2"
            | "h3"
            | "h4"
            | "h5"
            | "h6"
            | "head"
            | "header"
            | "hr"
            | "html"
            | "iframe"
            | "legend"
            | "li"
            | "link"
            | "main"
            | "menu"
            | "menuitem"
            | "nav"
            | "noframes"
            | "ol"
            | "optgroup"
            | "option"
            | "p"
            | "param"
            | "search"
            | "section"
            | "summary"
            | "table"
            | "tbody"
            | "td"
            | "tfoot"
            | "th"
            | "thead"
            | "title"
            | "tr"
            | "track"
            | "ul"
    )
}

fn is_declaration_start(input: &str) -> bool {
    input
        .as_bytes()
        .get(2)
        .is_some_and(|byte| input.starts_with("<!") && byte.is_ascii_alphabetic())
}

/// Whether `input`, past its indentation, is a run of `-` and nothing else
/// but trailing spaces and tabs.
fn dashes_alone(input: &str) -> bool {
    trim_up_to_three_spaces(input)
        .map(|rest| rest.trim_end_matches([' ', '\t']))
        .is_some_and(|run| !run.is_empty() && run.bytes().all(|byte| byte == b'-'))
}

/// A delimiter run recorded during the inline scan for later resolution by the
/// delimiter-stack algorithm (`process_emphasis`). A closer pairs with the
/// nearest compatible opener before it, so same-mark spans nest: `*` and `_`
/// (CommonMark), `~~` strikethrough, and `==` highlight.
#[derive(Clone, Copy)]
struct DelimMarker {
    /// Index of the placeholder text node in the flat node list. The text node
    /// holds the as-yet-unmatched delimiter characters; matching trims it from
    /// the appropriate side and matched characters are removed entirely.
    node_index: usize,
    marker: u8,
    /// Remaining unmatched delimiter characters in this run.
    length: usize,
    /// The run's length as scanned. CommonMark's rule of three, and the
    /// `openers_bottom` key that caches its verdicts, read this rather than
    /// what is left after earlier pairings.
    run_length: usize,
    /// Whether the run can open and close; settled by `assign_emphasis_roles`.
    can_open: bool,
    can_close: bool,
    /// How many more times a long `==` run closes, two characters at a time,
    /// after closing with its first two.
    recloses: usize,
    /// The opener of the latest-starting `==` span enclosing this run (see
    /// `assign_emphasis_roles`), or `NIL`.
    enclosed_from: usize,
    /// Offset of the run in the inline input, for adjacency checks.
    position: usize,
}

/// End-of-list marker for the index-linked lists used by `process_emphasis`.
const NIL: usize = usize::MAX;

/// The deepest `Emphasis`/`Strong`/`Delete` nesting one inline pass builds. A
/// delimiter pair that would nest deeper stays literal text, which bounds the
/// tree depth that recursive consumers (text merging, serialization, `Drop`)
/// walk.
const MAX_EMPHASIS_NESTING: usize = 16;

/// How deeply the nodes between two delimiter runs nest: `emphasis` counts
/// `Emphasis`/`Strong`/`Delete` levels since the nearest enclosed mark span,
/// bracket, or directive,
/// and `total` counts every inline container level (emphasis, marks, and
/// formed brackets and directives). `total` counts toward `MAX_INLINE_NESTING`
/// together with the inline passes and open brackets enclosing these nodes;
/// emphasis counts toward `MAX_EMPHASIS_NESTING` within one mark.
#[derive(Clone, Copy, Default)]
struct Nesting {
    emphasis: usize,
    total: usize,
}

impl Nesting {
    fn max(self, other: Self) -> Self {
        Self {
            emphasis: self.emphasis.max(other.emphasis),
            total: self.total.max(other.total),
        }
    }
}

/// The delimiter stack `process_emphasis` works on: live runs form a doubly
/// linked list in source order, and each live run records the deepest nesting
/// among the nodes between it and the next live run.
struct DelimiterLinks {
    prev: Vec<usize>,
    next: Vec<usize>,
    live: Vec<bool>,
    nesting_after: Vec<Nesting>,
}

impl DelimiterLinks {
    fn new(count: usize) -> Self {
        Self {
            prev: (0..count).map(|index| index.wrapping_sub(1)).collect(),
            next: (1..=count)
                .map(|index| if index < count { index } else { NIL })
                .collect(),
            live: alloc::vec![true; count],
            nesting_after: alloc::vec![Nesting::default(); count],
        }
    }

    /// Unlinks `index`; the nodes after it now follow the previous live run.
    fn unlink(&mut self, index: usize) {
        let (before, after) = (self.prev[index], self.next[index]);
        self.live[index] = false;
        if before != NIL {
            self.next[before] = after;
            self.nesting_after[before] = self.nesting_after[before].max(self.nesting_after[index]);
        }
        if after != NIL {
            self.prev[after] = before;
        }
    }

    /// Unlinks every run strictly between `opener` and `closer` and returns the
    /// deepest nesting among the nodes between them.
    fn close_span(&mut self, opener: usize, closer: usize) -> Nesting {
        let mut nesting = self.nesting_after[opener];
        let mut inner = self.next[opener];
        while inner != closer {
            nesting = nesting.max(self.nesting_after[inner]);
            self.live[inner] = false;
            inner = self.next[inner];
        }
        self.next[opener] = closer;
        self.prev[closer] = opener;
        nesting
    }
}

/// The flat inline list `process_emphasis` rewrites, held as a doubly linked
/// list over stable slots. Wrapping a matched span and dropping a consumed
/// delimiter run cost time proportional to the wrapped nodes rather than to the
/// whole list, and delimiter `node_index` values never need re-indexing.
struct InlineList {
    slots: Vec<Option<Inline>>,
    prev: Vec<usize>,
    next: Vec<usize>,
    head: usize,
}

impl InlineList {
    fn new(nodes: Vec<Inline>) -> Self {
        let count = nodes.len();
        Self {
            slots: nodes.into_iter().map(Some).collect(),
            prev: (0..count).map(|slot| slot.wrapping_sub(1)).collect(),
            next: (1..=count)
                .map(|slot| if slot < count { slot } else { NIL })
                .collect(),
            head: if count == 0 { NIL } else { 0 },
        }
    }

    fn node_mut(&mut self, slot: usize) -> &mut Inline {
        self.slots[slot]
            .as_mut()
            .expect("delimiter placeholder slot is live")
    }

    /// Replaces every node strictly between `before` and `after` with the node
    /// `wrap` builds from them (in order).
    fn wrap_between(
        &mut self,
        before: usize,
        after: usize,
        wrap: impl FnOnce(Vec<Inline>) -> Inline,
    ) {
        let mut children = Vec::new();
        let mut cursor = self.next[before];
        while cursor != after {
            children.push(self.slots[cursor].take().expect("linked slot is live"));
            cursor = self.next[cursor];
        }
        let slot = self.slots.len();
        self.slots.push(Some(wrap(children)));
        self.prev.push(before);
        self.next.push(after);
        self.next[before] = slot;
        self.prev[after] = slot;
    }

    fn remove(&mut self, slot: usize) {
        let (prev, next) = (self.prev[slot], self.next[slot]);
        if prev == NIL {
            self.head = next;
        } else {
            self.next[prev] = next;
        }
        if next != NIL {
            self.prev[next] = prev;
        }
        self.slots[slot] = None;
    }

    fn into_vec(mut self) -> Vec<Inline> {
        let mut nodes = Vec::new();
        let mut cursor = self.head;
        while cursor != NIL {
            nodes.push(self.slots[cursor].take().expect("linked slot is live"));
            cursor = self.next[cursor];
        }
        nodes
    }
}

/// Pushes a literal text node for `value` starting at `start` of the block-level
/// inline input.
fn push_text(nodes: &mut Vec<Inline>, start: usize, value: &str) {
    nodes.push(Inline::Text(Text {
        meta: NodeMeta::new(Some(Span::new(start, start + value.len()))),
        value: value.into(),
    }));
}

/// Resolves the `]` at `close` against the innermost open bracket. Returns the
/// end of the construct it forms, or `None` when the `]` stays literal text
/// (the opener's characters then stay literal too).
#[allow(clippy::too_many_arguments)]
fn close_bracket(
    input: &str,
    base_offset: usize,
    close: usize,
    definitions: Option<Labels<'_>>,
    nodes: &mut Vec<Inline>,
    delimiters: &mut Vec<DelimMarker>,
    brackets: &mut Brackets,
    pass: &mut InlinePass,
) -> Option<usize> {
    let mut opener = brackets.openers.pop()?;
    let depth = pass.state.depth + brackets.openers.len();
    // The opener's own stack slot decides whether it may form a link; later
    // openers pushed into that slot start out able to.
    let link_active = brackets.openers.len() >= brackets.link_floor;
    brackets.link_floor = brackets.link_floor.min(brackets.openers.len());

    if opener.kind == BracketKind::InlineFootnote {
        if !input[opener.position + 2..close].trim().is_empty() {
            let (children, marks) = take_label(input, nodes, delimiters, brackets, &opener, depth);
            nodes.truncate(opener.node_index - 1);
            nodes.push(Inline::InlineFootnote(InlineFootnote {
                meta: NodeMeta::new(Some(Span::new(
                    base_offset + opener.position,
                    base_offset + close + 1,
                ))),
                children,
            }));
            brackets.formed.push((nodes.len() - 1, marks + 1));
            return Some(close + 1);
        }
        // An empty inline footnote is a literal `^`, then a plain `[`.
        opener.kind = BracketKind::Link;
        opener.position += 1;
    }

    if opener.kind == BracketKind::Image {
        let target = match_link_target(
            &mut pass.scan,
            input,
            opener.position + 2,
            close,
            definitions,
        );
        if let Some((end, target)) = target {
            let (children, marks) = take_label(input, nodes, delimiters, brackets, &opener, depth);
            nodes.truncate(opener.node_index - 1);
            let span = Span::new(base_offset + opener.position, base_offset + end);
            nodes.push(link_node(target, true, span, children));
            brackets.formed.push((nodes.len() - 1, marks + 1));
            return Some(end);
        }
        // Not an image: the `!` stays text and the `[` may still open a link.
        opener.kind = BracketKind::Link;
        opener.position += 1;
    }

    if link_active {
        let target = match_link_target(
            &mut pass.scan,
            input,
            opener.position + 1,
            close,
            definitions,
        );
        if let Some((end, target)) = target {
            let (children, marks) = take_label(input, nodes, delimiters, brackets, &opener, depth);
            nodes.truncate(opener.node_index);
            let span = Span::new(base_offset + opener.position, base_offset + end);
            nodes.push(link_node(target, false, span, children));
            brackets.formed.push((nodes.len() - 1, marks + 1));
            // Links do not nest: no earlier `[` forms a link around this one.
            brackets.close_links();
            return Some(end);
        }
    }

    // `[^label]` is a footnote reference when the label is plain: no link or
    // image formed inside it.
    let holds_formed = brackets
        .formed
        .last()
        .is_some_and(|&(node, _)| node > opener.node_index);
    if !holds_formed && input[opener.position + 1..].starts_with('^') {
        let label = &input[opener.position + 2..close];
        if is_footnote_label(label) {
            drop_label(nodes, delimiters, brackets, &opener);
            nodes.push(Inline::FootnoteReference(FootnoteReference {
                meta: NodeMeta::new(Some(Span::new(
                    base_offset + opener.position,
                    base_offset + close + 1,
                ))),
                label: label.into(),
                identifier: normalize_label(label),
            }));
            return Some(close + 1);
        }
    }
    None
}

/// Drops `opener`'s `[` and everything recorded after it.
fn drop_label(
    nodes: &mut Vec<Inline>,
    delimiters: &mut Vec<DelimMarker>,
    brackets: &mut Brackets,
    opener: &BracketOpener,
) {
    nodes.truncate(opener.node_index);
    delimiters.truncate(opener.delimiter_bottom);
    let kept = brackets
        .formed
        .partition_point(|&(node, _)| node < opener.node_index);
    brackets.formed.truncate(kept);
}

/// Pushes the `length`-byte run of `marker` at `index` as a literal text node
/// plus a delimiter entry, whose roles `assign_emphasis_roles` settles.
fn push_delimiter(
    nodes: &mut Vec<Inline>,
    delimiters: &mut Vec<DelimMarker>,
    index: usize,
    base_offset: usize,
    marker: u8,
    length: usize,
) {
    let node_index = nodes.len();
    nodes.push(Inline::Text(Text {
        meta: NodeMeta::new(Some(Span::new(
            base_offset + index,
            base_offset + index + length,
        ))),
        value: String::from(marker as char).repeat(length),
    }));
    delimiters.push(DelimMarker {
        node_index,
        marker,
        length,
        run_length: length,
        can_open: false,
        can_close: false,
        recloses: 0,
        enclosed_from: NIL,
        position: index,
    });
}

/// The CommonMark roles of a `*`/`_`/`~~` run, with flanking as the
/// CJK-friendly amendments define it (see `delimiter_flanking_within`).
///
/// Flanking is computed on the whole run (CommonMark treats left/right-flanking
/// as a property of the run, not of an individual delimiter), including the
/// `_` intraword punctuation rules.
///
/// GFM's cross-marker bonus: a `*` run immediately adjacent to a `~` counts as
/// openable/closeable even though `~` is a punctuation character (this is what
/// makes `a*~b~*c` emphasize). A `_` run or a `~` run gets plain CommonMark
/// flanking beside a `~`.
///
/// A side that touches the boundary of an enclosing mark span (`bounded_before`
/// / `bounded_after`) flanks as the end of the span's content.
fn emphasis_roles(
    input: &str,
    index: usize,
    length: usize,
    marker: u8,
    bounded_before: bool,
    bounded_after: bool,
) -> (bool, bool) {
    let flanking = delimiter_flanking_within(input, index, length, bounded_before, bounded_after);
    let (mut can_open, mut can_close) = if marker == b'_' {
        (
            flanking.left && (!flanking.right || flanking.previous_punctuation),
            flanking.right && (!flanking.left || flanking.next_punctuation),
        )
    } else {
        (flanking.left, flanking.right)
    };

    // GFM: a `*` run touching a `~` strikethrough marker may open/close even
    // when ordinary flanking refuses it (the `~` would otherwise be a blocking
    // punctuation neighbour).
    if marker == b'*' {
        if flanking.next == Some('~') {
            can_open = true;
        }
        if flanking.previous == Some('~') {
            can_close = true;
        }
    }
    (can_open, can_close)
}

/// Settles the roles of every recorded run. The `==` runs take theirs first
/// and are paired among themselves; each `*`, `_`, and `~~` run then takes its
/// roles once the `==` spans are known, flanking as the edge of a span's
/// content where it touches the inner side of the span's delimiter.
fn assign_emphasis_roles(input: &str, delimiters: &mut [DelimMarker]) {
    let mut opens_span = alloc::vec![false; delimiters.len()];
    let mut closes_span = alloc::vec![false; delimiters.len()];
    let mut open_marks: Vec<usize> = Vec::new();
    // The run each span opened by a run closes at (a run opens at most one).
    let mut span_close = alloc::vec![NIL; delimiters.len()];
    for (index, run) in delimiters.iter_mut().enumerate() {
        if run.marker != b'=' {
            continue;
        }
        assign_double_mark_roles(input, run);
        let mut closed = 0;
        if run.can_close {
            while closed <= run.recloses {
                let Some(opener) = open_marks.pop() else {
                    break;
                };
                opens_span[opener] = true;
                closes_span[index] = true;
                span_close[opener] = index;
                closed += 1;
            }
        }
        // What is left of the run after closing may still open.
        if run.can_open && run.length >= 2 * closed + 2 {
            open_marks.push(index);
        }
    }

    for index in 0..delimiters.len() {
        let run = delimiters[index];
        if run.marker == b'=' {
            continue;
        }
        let bounded_before = index > 0 && {
            let before = &delimiters[index - 1];
            before.position + before.length == run.position && opens_span[index - 1]
        };
        let bounded_after = index + 1 < delimiters.len() && {
            let after = &delimiters[index + 1];
            after.position == run.position + run.length && closes_span[index + 1]
        };
        let (can_open, can_close) = emphasis_roles(
            input,
            run.position,
            run.length,
            run.marker,
            bounded_before,
            bounded_after,
        );
        delimiters[index].can_open = can_open;
        delimiters[index].can_close = can_close;
    }

    // Each run's latest-starting enclosing mark span. Spans are pushed in
    // opener order, so the top of `open_spans` is the latest-starting one;
    // spans that have ended are dropped when they reach the top.
    let mut open_spans: Vec<usize> = Vec::new();
    for (index, run) in delimiters.iter_mut().enumerate() {
        while open_spans
            .last()
            .is_some_and(|&opener| span_close[opener] <= index)
        {
            open_spans.pop();
        }
        if let Some(&opener) = open_spans.last() {
            run.enclosed_from = opener;
        }
        if span_close[index] != NIL {
            open_spans.push(index);
        }
    }
}

/// Sets the roles of a `==` run: it opens with its last two characters and
/// closes with its first two (and then the next two), each subject to
/// CommonMark flanking of that two-character delimiter. A run right after an
/// escaped character of the same mark never closes.
fn assign_double_mark_roles(input: &str, run: &mut DelimMarker) {
    let (index, length) = (run.position, run.length);
    let after_escaped_mark =
        index > 0 && input.as_bytes()[index - 1] == run.marker && is_escaped_at(input, index - 1);
    run.can_close = !after_escaped_mark && can_close_delimited(input, index, 2);
    run.recloses = if run.can_close {
        (1..length / 2)
            .take_while(|pair| can_close_delimited(input, index + 2 * pair, 2))
            .count()
    } else {
        0
    };
    run.can_open = can_open_delimited(input, index + length - 2, 2);
}

/// Resolves recorded delimiter runs into emphasis and mark nodes using the
/// delimiter-stack algorithm, leaving unmatched runs as text. Closers are taken
/// in source order; when a pair closes, runs strictly between its opener and
/// closer can no longer pair across it.
///
/// `formed` lists the link, image, footnote, and directive nodes already built
/// among `nodes`, with their nesting depth, so spans around them count it.
/// Returns the nodes and the deepest nesting among them.
///
/// `depth` counts the nesting levels enclosing these runs: the inline passes
/// around this one, plus the open brackets around a bracket label.
fn process_emphasis(
    nodes: Vec<Inline>,
    mut delimiters: Vec<DelimMarker>,
    depth: usize,
    formed: &[(usize, usize)],
) -> (Vec<Inline>, usize) {
    let mut deepest = formed.iter().map(|&(_, depth)| depth).max().unwrap_or(0);
    if delimiters.is_empty() {
        let mut nodes = nodes;
        merge_adjacent_text(&mut nodes);
        return (nodes, deepest);
    }
    let mut nodes = InlineList::new(nodes);

    // A run that is consumed, demoted to plain text, or enclosed by a newly
    // closed span is unlinked, so the opener walk below only ever visits live
    // runs.
    let mut links = DelimiterLinks::new(delimiters.len());
    for &(node, depth) in formed {
        let before = delimiters.partition_point(|run| run.node_index < node);
        if before > 0 {
            let gap = &mut links.nesting_after[before - 1].total;
            *gap = (*gap).max(depth);
        }
    }

    // `openers_bottom` records, per (marker, opener-can-also-close, length % 3),
    // the lowest opener index a nested closer is allowed to reach. Closers below
    // this bound for their key have already been proven to have no compatible
    // opener.
    let mut openers_bottom: [Option<usize>; NESTED_MARKERS * 6] = [None; NESTED_MARKERS * 6];
    let mut span_bottom: Vec<Vec<(usize, usize)>> = Vec::new();
    let mut closer_idx = 0;

    // Every run at or after `closer_idx` is still linked: runs are only ever
    // unlinked at or before the current closer.
    while closer_idx < delimiters.len() {
        let closer = delimiters[closer_idx];

        let opener = if closer.can_close {
            nested_opener(
                &delimiters,
                &links,
                &openers_bottom,
                &span_bottom,
                closer_idx,
            )
        } else {
            None
        };

        let Some(opener_idx) = opener else {
            if closer.can_close {
                // No opener found: remember how far we searched so future
                // closers of the same key skip the same dead range.
                let key = openers_bottom_key(&closer);
                match span_floor(&closer) {
                    Some(span) => {
                        if span_bottom.len() <= span {
                            span_bottom.resize_with(span + 1, Vec::new);
                        }
                        match span_bottom[span].iter_mut().find(|(k, _)| *k == key) {
                            Some(bound) => bound.1 = closer_idx,
                            None => span_bottom[span].push((key, closer_idx)),
                        }
                    }
                    None => openers_bottom[key] = Some(closer_idx),
                }
            }
            if !closer.can_open {
                links.unlink(closer_idx);
            }
            closer_idx += 1;
            continue;
        };

        let (used, wrap) = pair_shape(&delimiters[opener_idx], &delimiters[closer_idx]);

        // Drop delimiters strictly between the opener and closer: they could not
        // match outward across this newly closed span.
        let inner = links.close_span(opener_idx, closer_idx);
        let fits = depth + inner.total < MAX_INLINE_NESTING
            && (wrap.is_mark() || inner.emphasis < MAX_EMPHASIS_NESTING);
        if fits {
            apply_emphasis(
                &mut nodes,
                &mut delimiters,
                opener_idx,
                closer_idx,
                used,
                wrap,
            );
            links.nesting_after[opener_idx] = Nesting {
                emphasis: if wrap.is_mark() {
                    0
                } else {
                    inner.emphasis + 1
                },
                total: inner.total + 1,
            };
            deepest = deepest.max(inner.total + 1);
        } else {
            // Too deep to wrap: both runs stay whole in their text nodes as
            // literal text and pair no further. Any span enclosing this one is
            // at least as deep, so it stays literal too.
            delimiters[opener_idx].length = 0;
            delimiters[closer_idx].length = 0;
            links.nesting_after[opener_idx] = inner;
        }
        if closer.marker == b'=' {
            // `==` runs open only with their last two characters, and a long
            // run closes a second time only with its next two characters.
            delimiters[opener_idx].can_open = false;
            let run = &mut delimiters[closer_idx];
            run.can_close = run.recloses > 0;
            run.recloses = run.recloses.saturating_sub(1);
        }

        if delimiters[opener_idx].length == 0 {
            links.unlink(opener_idx);
        }
        if delimiters[closer_idx].length == 0 {
            links.unlink(closer_idx);
            closer_idx += 1;
        }
        // When a closer still has delimiters left it stays the active closer
        // so the leftover can match an earlier opener (e.g. `***foo*` keeps
        // `**`).
    }

    // Adjacent text nodes can appear where unmatched delimiter runs ended up
    // beside literal text (`**foo*bar*` -> `**foo` + emphasis). CommonMark
    // coalesces them as the final step; do the same for the spans we created.
    let mut nodes = nodes.into_vec();
    merge_adjacent_text(&mut nodes);
    (nodes, deepest)
}

/// The markers that pair through nested roles, in `openers_bottom` order.
const NESTED_MARKERS: usize = 4;

/// The nearest live opener before `closer_idx` that the nested closer there can
/// pair with, searching no lower than its `openers_bottom` bound.
///
/// A closer that can also open does not close across a `==` span enclosing it:
/// it searches no lower than that span's opener, bounded per span by
/// `span_bottom` the way `openers_bottom` bounds the whole list.
fn nested_opener(
    delimiters: &[DelimMarker],
    links: &DelimiterLinks,
    openers_bottom: &[Option<usize>],
    span_bottom: &[Vec<(usize, usize)>],
    closer_idx: usize,
) -> Option<usize> {
    let closer = &delimiters[closer_idx];
    let key = openers_bottom_key(closer);
    let mut bottom = openers_bottom[key];
    if let Some(span) = span_floor(closer) {
        let span_floor = span_bottom
            .get(span)
            .and_then(|bounds| bounds.iter().find(|(k, _)| *k == key))
            .map_or(span + 1, |&(_, bound)| bound);
        bottom = bottom.max(Some(span_floor));
    }
    let mut search = links.prev[closer_idx];
    while search != NIL {
        if bottom.is_some_and(|bottom| search < bottom) {
            return None;
        }
        let candidate = &delimiters[search];
        if candidate.marker == closer.marker
            && candidate.can_open
            && emphasis_delimiters_match(candidate, closer)
        {
            return Some(search);
        }
        search = links.prev[search];
    }
    None
}

/// The enclosing mark span a nested closer may not close across: only a run
/// that can also open is held inside it.
fn span_floor(closer: &DelimMarker) -> Option<usize> {
    (closer.can_open && closer.enclosed_from != NIL).then_some(closer.enclosed_from)
}

/// How many characters a pair consumes from each run, and the node it forms.
fn pair_shape(opener: &DelimMarker, closer: &DelimMarker) -> (usize, EmphasisWrap) {
    match closer.marker {
        // Strikethrough consumes the whole `~~` run on each side.
        b'~' => (2, EmphasisWrap::Delete),
        b'=' => (2, EmphasisWrap::Mark),
        marker => {
            let delimiter = if marker == b'_' {
                EmphasisDelimiter::Underscore
            } else {
                EmphasisDelimiter::Asterisk
            };
            if opener.length >= 2 && closer.length >= 2 {
                (2, EmphasisWrap::Strong(delimiter))
            } else {
                (1, EmphasisWrap::Emphasis(delimiter))
            }
        }
    }
}

/// Merges consecutive `Text` nodes in a list, recursing into the emphasis and
/// mark nodes produced at this level. Other containers were already finalized
/// by their own `parse_inlines` pass and are left untouched.
fn merge_adjacent_text(nodes: &mut Vec<Inline>) {
    let mut write = 0;
    for read in 0..nodes.len() {
        if read != write {
            nodes.swap(read, write);
        }
        if write > 0 {
            let (head, tail) = nodes.split_at_mut(write);
            if let (Inline::Text(previous), Inline::Text(current)) =
                (&mut head[write - 1], &tail[0])
            {
                previous.value.push_str(&current.value);
                if let (Some(previous_span), Some(current_span)) =
                    (previous.meta.span.as_mut(), current.meta.span)
                {
                    previous_span.end = current_span.end;
                }
                continue;
            }
        }
        write += 1;
    }
    nodes.truncate(write);

    for node in nodes.iter_mut() {
        match node {
            Inline::Emphasis(node) => merge_adjacent_text(&mut node.children),
            Inline::Strong(node) => merge_adjacent_text(&mut node.children),
            Inline::Delete(node) => merge_adjacent_text(&mut node.children),
            Inline::Mark(node) => merge_adjacent_text(&mut node.children),
            _ => {}
        }
    }
}

/// Index into `openers_bottom` for a nested closer's (marker, both-flags,
/// length % 3) key.
fn openers_bottom_key(closer: &DelimMarker) -> usize {
    let marker = match closer.marker {
        b'_' => 1,
        b'~' => 2,
        b'=' => 3,
        _ => 0,
    };
    let both = usize::from(closer.can_open && closer.can_close);
    // The key holds what `emphasis_delimiters_match` reads of the closer: the
    // whole run's length for the rule of three on `*` / `_`, and what is left
    // of the run for the other marks.
    let length = match closer.marker {
        b'*' | b'_' => closer.run_length,
        _ => closer.length,
    };
    let modulo = length % 3;
    ((marker * 2) + both) * 3 + modulo
}

/// Nested opener/closer compatibility, including CommonMark's rule of three.
fn emphasis_delimiters_match(opener: &DelimMarker, closer: &DelimMarker) -> bool {
    match opener.marker {
        // GFM strikethrough: only runs of exactly two `~` are recorded, and a
        // pair consumes both whole, so any two live runs match. The rule of
        // three does not apply to `~`.
        b'~' => true,
        // `==` pairs two characters from each run.
        b'=' => opener.length >= 2 && closer.length >= 2,
        _ => {
            // Rule of three: if either delimiter can both open and close, the
            // sum of the lengths of the runs containing them must not be a
            // multiple of three, unless both are themselves multiples of three.
            // CommonMark counts whole runs, not what earlier pairings left.
            let opener_both = opener.can_open && opener.can_close;
            let closer_both = closer.can_open && closer.can_close;
            if opener_both || closer_both {
                let (opener_run, closer_run) = (opener.run_length, closer.run_length);
                let sum = opener_run + closer_run;
                if sum % 3 == 0 && !(opener_run % 3 == 0 && closer_run % 3 == 0) {
                    return false;
                }
            }
            true
        }
    }
}

/// The node a matched delimiter pair collapses into.
#[derive(Clone, Copy)]
enum EmphasisWrap {
    Emphasis(EmphasisDelimiter),
    Strong(EmphasisDelimiter),
    Delete,
    Mark,
}

impl EmphasisWrap {
    /// Whether the node counts toward `MAX_INLINE_NESTING` rather than
    /// `MAX_EMPHASIS_NESTING`.
    fn is_mark(self) -> bool {
        matches!(self, Self::Mark)
    }
}

/// Wraps the nodes between two delimiter runs into the node `wrap` names and
/// consumes `used` characters from each side.
fn apply_emphasis(
    nodes: &mut InlineList,
    delimiters: &mut [DelimMarker],
    opener_idx: usize,
    closer_idx: usize,
    used: usize,
    wrap: EmphasisWrap,
) {
    let opener_node = delimiters[opener_idx].node_index;
    let closer_node = delimiters[closer_idx].node_index;

    // A span covers exactly its consumed delimiters and what they enclose: the
    // last `used` characters left in the opener's text node through the first
    // `used` left in the closer's.
    let span_start = nodes
        .node_mut(opener_node)
        .span()
        .map(|span| span.end - used);
    let span_end = nodes
        .node_mut(closer_node)
        .span()
        .map(|span| span.start + used);
    // Trim the consumed characters from the opener's text node (right side) and
    // the closer's text node (left side), updating their recorded lengths/spans.
    trim_delimiter_text_tail(nodes.node_mut(opener_node), used);
    trim_delimiter_text_head(nodes.node_mut(closer_node), used);
    delimiters[opener_idx].length -= used;
    let closer = &mut delimiters[closer_idx];
    closer.length -= used;
    closer.position += used;

    // The wrapped children are the nodes strictly between the opener and closer
    // text nodes.
    let meta = NodeMeta::new(
        span_start
            .zip(span_end)
            .map(|(start, end)| Span::new(start, end)),
    );
    nodes.wrap_between(opener_node, closer_node, |children| match wrap {
        EmphasisWrap::Strong(delimiter) => Inline::Strong(Strong {
            meta,
            delimiter,
            children,
        }),
        EmphasisWrap::Emphasis(delimiter) => Inline::Emphasis(Emphasis {
            meta,
            delimiter,
            children,
        }),
        EmphasisWrap::Delete => Inline::Delete(Delete { meta, children }),
        EmphasisWrap::Mark => Inline::Mark(Mark { meta, children }),
    });

    // Drop any placeholder text node that has been fully consumed so leftover
    // delimiters never survive as literal text.
    if delimiters[closer_idx].length == 0 {
        nodes.remove(closer_node);
    }
    if delimiters[opener_idx].length == 0 {
        nodes.remove(opener_node);
    }
}

/// What a `[`-family opener can become when its `]` arrives.
#[derive(Clone, Copy, PartialEq, Eq)]
enum BracketKind {
    Link,
    Image,
    InlineFootnote,
}

/// A `[`, `![`, or `^[` waiting for its `]`. Its `[` is a placeholder text
/// node; an image's `!` and an inline footnote's `^` sit in the node before it.
struct BracketOpener {
    kind: BracketKind,
    /// The placeholder text node holding the `[`.
    node_index: usize,
    /// Offset of the opener's first character (`!`, `^`, or `[`) in the input.
    position: usize,
    /// `delimiters.len()` when the opener was pushed: later runs are in its
    /// label.
    delimiter_bottom: usize,
}

/// What a `]` resolves a link-kind opener to.
enum LinkTarget {
    Resource(ParsedLinkResource),
    Reference {
        identifier: String,
        kind: ReferenceKind,
    },
}

/// Matches what follows the `]` at `close` of a link or image whose label is
/// `input[label_start..close]`: an inline `(…)` resource, a full or collapsed
/// reference, or a shortcut reference to a defined label. A `(…)` that is not a
/// valid resource leaves the reference forms to try, for images and links
/// alike. Returns the end of the construct and its target.
fn match_link_target(
    scan: &mut InlineScan,
    input: &str,
    label_start: usize,
    close: usize,
    definitions: Option<Labels<'_>>,
) -> Option<(usize, LinkTarget)> {
    let label = &input[label_start..close];
    let after = close + 1;
    if input.as_bytes().get(after) == Some(&b'(') {
        match parse_link_resource(&mut scan.lookups, input, after) {
            Some((end, resource, _)) => return Some((end, LinkTarget::Resource(resource))),
            // A present-but-invalid `(...)` resource is not an inline link or
            // image, but CommonMark still resolves `[label]` as a shortcut
            // reference and leaves the invalid `(...)` as literal text (links
            // 568).
            None => {}
        }
    }
    // A `[` that opens no reference label leaves `[label]` a shortcut
    // reference followed by literal text.
    let reference_close = if input.as_bytes().get(after) == Some(&b'[') {
        scan.reference_label_end(after)
    } else {
        None
    };
    if let Some(reference_close) = reference_close {
        let reference = &input[after + 1..reference_close];
        let identifier = if reference.is_empty() {
            label
        } else {
            reference
        };
        // A present `[...]` second label that resolves to no definition is
        // not a link, and CommonMark does not fall back to treating the first
        // label as a shortcut (`[x][ ]`, `[x][undef]` stay literal).
        return definition_exists(definitions, identifier).then(|| {
            let kind = if reference.is_empty() {
                ReferenceKind::Collapsed
            } else {
                ReferenceKind::Full
            };
            (
                reference_close + 1,
                LinkTarget::Reference {
                    identifier: identifier.into(),
                    kind,
                },
            )
        });
    }
    definition_exists(definitions, label).then(|| {
        (
            after,
            LinkTarget::Reference {
                identifier: label.into(),
                kind: ReferenceKind::Shortcut,
            },
        )
    })
}

/// Builds the link or image node for a matched target over `children`.
fn link_node(target: LinkTarget, image: bool, span: Span, mut children: Vec<Inline>) -> Inline {
    let meta = NodeMeta::new(Some(span));
    if !image {
        demote_links(&mut children);
    }
    match (target, image) {
        (LinkTarget::Resource(resource), false) => Inline::Link(Link {
            meta,
            destination: resource.destination,
            destination_kind: resource.destination_kind,
            title: resource.title,
            children,
        }),
        (LinkTarget::Resource(resource), true) => Inline::Image(Image {
            meta,
            destination: resource.destination,
            destination_kind: resource.destination_kind,
            title: resource.title,
            alt: children,
        }),
        (LinkTarget::Reference { identifier, kind }, false) => {
            Inline::LinkReference(LinkReference {
                meta,
                identifier: normalize_label(&identifier),
                label: identifier,
                kind,
                children,
            })
        }
        (LinkTarget::Reference { identifier, kind }, true) => {
            Inline::ImageReference(ImageReference {
                meta,
                identifier: normalize_label(&identifier),
                label: identifier,
                kind,
                alt: children,
            })
        }
    }
}

/// An autolink written in `form` as `text`, spanning `span`.
fn autolink_node(form: AutolinkForm, span: Span, text: &str) -> Inline {
    Inline::Autolink(Autolink {
        meta: NodeMeta::new(Some(span)),
        form,
        text: text.into(),
    })
}

/// Link text holds no links: autolinks inside it, the only links a formed
/// link's text can hold, read as their text, an angle-bracket autolink
/// without its brackets. Image alt text inside it keeps its own links.
fn demote_links(nodes: &mut Vec<Inline>) {
    for node in nodes.iter_mut() {
        match node {
            Inline::Autolink(autolink) => {
                *node = Inline::Text(Text {
                    meta: autolink.meta.clone(),
                    value: core::mem::take(&mut autolink.text),
                });
            }
            Inline::Emphasis(node) => demote_links(&mut node.children),
            Inline::Strong(node) => demote_links(&mut node.children),
            Inline::Delete(node) => demote_links(&mut node.children),
            Inline::Mark(node) => demote_links(&mut node.children),
            Inline::InlineFootnote(node) => demote_links(&mut node.children),
            Inline::TextDirective(node) => demote_links(&mut node.label),
            Inline::Image(node) => demote_links(&mut node.alt),
            Inline::ImageReference(node) => demote_links(&mut node.alt),
            _ => {}
        }
    }
    merge_adjacent_text(nodes);
}

/// The open brackets of one inline pass and the runs and nodes they enclose.
struct Brackets {
    openers: Vec<BracketOpener>,
    /// Openers below this stack index can no longer form links: a link formed
    /// after them.
    link_floor: usize,
    /// How many `[` were left as text for want of nesting room and are still
    /// open: the next that many `]` close them, as text.
    overflow: usize,
    /// Formed link, image, footnote, and directive nodes with their nesting
    /// depth, by node index, so spans around them count it.
    formed: Vec<(usize, usize)>,
}

impl Brackets {
    fn new() -> Self {
        Self {
            openers: Vec::new(),
            link_floor: 0,
            overflow: 0,
            formed: Vec::new(),
        }
    }

    /// Whether a `[` is open: pushed and not yet closed by a `]`, as a link or
    /// image opener or as text left for want of nesting room. An inline
    /// footnote's `^[` opens no link text. The stack is at most the nesting
    /// limit deep.
    fn open(&self) -> bool {
        self.overflow > 0
            || self
                .openers
                .iter()
                .any(|opener| !matches!(opener.kind, BracketKind::InlineFootnote))
    }

    /// Keeps every open `[` from forming a link around what follows.
    fn close_links(&mut self) {
        self.link_floor = self.openers.len();
    }
}

/// Takes the nodes and runs after `opener` out of the pass, pairs the runs
/// among themselves, and returns the resolved label content with its nesting
/// depth.
fn take_label(
    input: &str,
    nodes: &mut Vec<Inline>,
    delimiters: &mut Vec<DelimMarker>,
    brackets: &mut Brackets,
    opener: &BracketOpener,
    depth: usize,
) -> (Vec<Inline>, usize) {
    let first = opener.node_index + 1;
    let children: Vec<Inline> = nodes.drain(first..).collect();
    let mut runs = delimiters.split_off(opener.delimiter_bottom);
    for run in &mut runs {
        run.node_index -= first;
    }
    let split = brackets.formed.partition_point(|&(node, _)| node < first);
    let formed: Vec<(usize, usize)> = brackets
        .formed
        .split_off(split)
        .into_iter()
        .map(|(node, marks)| (node - first, marks))
        .collect();
    assign_emphasis_roles(input, &mut runs);
    process_emphasis(children, runs, depth, &formed)
}

/// Removes `count` trailing delimiter characters from a placeholder text node.
fn trim_delimiter_text_tail(node: &mut Inline, count: usize) {
    if let Inline::Text(text) = node {
        let new_len = text.value.len().saturating_sub(count);
        text.value.truncate(new_len);
        if let Some(span) = text.meta.span.as_mut() {
            span.end = span.end.saturating_sub(count);
        }
    }
}

/// Removes `count` leading delimiter characters from a placeholder text node.
/// The node holds one repeated marker byte, so dropping from the front leaves
/// the same text as truncating the back.
fn trim_delimiter_text_head(node: &mut Inline, count: usize) {
    if let Inline::Text(text) = node {
        let count = count.min(text.value.len());
        text.value.truncate(text.value.len() - count);
        if let Some(span) = text.meta.span.as_mut() {
            span.start += count;
        }
    }
}

/// Forward lookups the inline scanners ask of one input. `DirectLookups`
/// answers each with a fresh scan, for callers that ask once; `InlineLookups`
/// memoizes the answers for the many questions one inline pass asks. Both
/// answer identically.
trait Lookups {
    /// The first occurrence of `pattern` that starts at or after `from`.
    fn find(&mut self, pattern: &'static str, from: usize) -> Option<usize>;
    /// The first run of exactly `len` backticks at or after `start`, which is
    /// not inside a backtick run.
    fn code_span_close(&mut self, start: usize, len: usize) -> Option<usize>;
    /// The first unescaped `<` or `>`, or line break, at or after `from`.
    fn angle_destination_stop(&mut self, from: usize) -> Option<usize>;
    /// The first `$` not right after a `\` at or after `from`.
    fn unescaped_dollar(&mut self, from: usize) -> Option<usize>;
}

struct DirectLookups<'a> {
    input: &'a str,
}

impl Lookups for DirectLookups<'_> {
    fn find(&mut self, pattern: &'static str, from: usize) -> Option<usize> {
        self.input[from..].find(pattern).map(|offset| from + offset)
    }

    fn code_span_close(&mut self, start: usize, len: usize) -> Option<usize> {
        find_code_span_close(self.input, start, len)
    }

    fn angle_destination_stop(&mut self, from: usize) -> Option<usize> {
        (from..self.input.len()).find(|index| is_angle_destination_stop(self.input, *index))
    }

    fn unescaped_dollar(&mut self, from: usize) -> Option<usize> {
        (from..self.input.len()).find(|index| is_unescaped_dollar(self.input, *index))
    }
}

/// The patterns `InlineLookups::find` keeps position tables for.
const CACHED_PATTERNS: [&str; 8] = [">", "-->", "?>", "]]>", "\"", "'", "`$", "$$"];

/// `Lookups` over one inline input, each answered from a table built on first
/// use.
struct InlineLookups<'a> {
    input: &'a str,
    patterns: [Positions; CACHED_PATTERNS.len()],
    backtick_runs: Option<BTreeMap<usize, Vec<usize>>>,
    angle_destination_stops: Positions,
    unescaped_dollars: Positions,
}

impl<'a> InlineLookups<'a> {
    fn new(input: &'a str) -> Self {
        Self {
            input,
            patterns: Default::default(),
            backtick_runs: None,
            angle_destination_stops: Positions::default(),
            unescaped_dollars: Positions::default(),
        }
    }
}

impl Lookups for InlineLookups<'_> {
    fn find(&mut self, pattern: &'static str, from: usize) -> Option<usize> {
        let input = self.input;
        let Some(slot) = CACHED_PATTERNS.iter().position(|cached| *cached == pattern) else {
            return DirectLookups { input }.find(pattern, from);
        };
        self.patterns[slot].first_at_or_after(from, || pattern_starts(input, pattern))
    }

    fn code_span_close(&mut self, start: usize, len: usize) -> Option<usize> {
        let input = self.input;
        let runs = self
            .backtick_runs
            .get_or_insert_with(|| backtick_runs_by_length(input));
        let starts = runs.get(&len)?;
        starts
            .get(starts.partition_point(|run| *run < start))
            .copied()
    }

    fn angle_destination_stop(&mut self, from: usize) -> Option<usize> {
        let input = self.input;
        self.angle_destination_stops.first_at_or_after(from, || {
            (0..input.len())
                .filter(|index| is_angle_destination_stop(input, *index))
                .collect()
        })
    }

    fn unescaped_dollar(&mut self, from: usize) -> Option<usize> {
        let input = self.input;
        self.unescaped_dollars.first_at_or_after(from, || {
            (0..input.len())
                .filter(|index| is_unescaped_dollar(input, *index))
                .collect()
        })
    }
}

/// Start offsets of every maximal backtick run, grouped by run length.
fn backtick_runs_by_length(input: &str) -> BTreeMap<usize, Vec<usize>> {
    let mut runs: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
    let mut index = 0;
    while index < input.len() {
        if input.as_bytes()[index] == b'`' {
            let len = backtick_run_len(input, index);
            runs.entry(len).or_default().push(index);
            index += len;
        } else {
            index += 1;
        }
    }
    runs
}

fn backtick_run_len(input: &str, index: usize) -> usize {
    input.as_bytes()[index..]
        .iter()
        .take_while(|byte| **byte == b'`')
        .count()
}

/// A `$` that single-dollar math reads as a delimiter: one right after a `\`
/// is content, whether or not that `\` is itself escaped.
fn is_unescaped_dollar(input: &str, index: usize) -> bool {
    let bytes = input.as_bytes();
    bytes[index] == b'$' && (index == 0 || bytes[index - 1] != b'\\')
}

fn is_angle_destination_stop(input: &str, index: usize) -> bool {
    match input.as_bytes()[index] {
        b'<' | b'>' => !is_escaped_at(input, index),
        b'\n' | b'\r' => true,
        _ => false,
    }
}

/// Everything one `parse_inline_content` pass memoizes about its input, so its
/// questions about closing delimiters cost amortized linear time in total.
struct InlineScan<'a> {
    input: &'a str,
    lookups: InlineLookups<'a>,
    label_ends: BracketMemo,
    reference_label_ends: PathMemo,
    wikilink_closes: PathMemo,
    directive_attribute_closes: PathMemo,
    literal_autolinks: LiteralAutolinkScan,
}

impl<'a> InlineScan<'a> {
    fn new(input: &'a str) -> Self {
        Self {
            input,
            lookups: InlineLookups::new(input),
            label_ends: BracketMemo::default(),
            reference_label_ends: PathMemo::default(),
            wikilink_closes: PathMemo::default(),
            directive_attribute_closes: PathMemo::default(),
            literal_autolinks: LiteralAutolinkScan::default(),
        }
    }

    /// `find_link_label_end`, memoized.
    fn link_label_end(&mut self, open: usize) -> Option<usize> {
        let input = self.input;
        if input.as_bytes().get(open) != Some(&b'[') {
            return None;
        }
        let lookups = &mut self.lookups;
        self.label_ends
            .resolve(input.len() + 1, open + 1, |cursor| {
                link_label_step(lookups, input, cursor)
            })
    }

    /// `find_reference_label_end`, memoized.
    fn reference_label_end(&mut self, open: usize) -> Option<usize> {
        let input = self.input;
        if input.as_bytes().get(open) != Some(&b'[') {
            return None;
        }
        let close = self
            .reference_label_ends
            .resolve(input.len() + 1, open + 1, |cursor| {
                reference_label_step(input, cursor)
            })?;
        reference_label_is_within_limit(&input[open + 1..close]).then_some(close)
    }

    /// The `]]` closing the wikilink whose content starts at `start`; it must
    /// be on the same line.
    fn wikilink_close(&mut self, start: usize) -> Option<usize> {
        let input = self.input;
        self.wikilink_closes
            .resolve(input.len() + 1, start, |cursor| {
                wikilink_close_step(input, cursor)
            })
    }

    /// `find_directive_attributes_close`, memoized.
    fn directive_attributes_close(&mut self, open: usize) -> Option<usize> {
        let input = self.input;
        if input.as_bytes().get(open) != Some(&b'{') {
            return None;
        }
        self.directive_attribute_closes.resolve(
            (input.len() + 1) * DIRECTIVE_QUOTE_STATES,
            (open + 1) * DIRECTIVE_QUOTE_STATES,
            |node| directive_attributes_step(input, node),
        )
    }
}

/// Parses the inline content `input`, whose source map is `map`. The inline
/// parser works in `input`'s coordinates; the spans it produces, on nodes and
/// on the diagnostics it pushes, are translated to the input afterwards.
fn parse_inlines(
    input: &str,
    map: &SourceMap,
    definitions: Option<Labels<'_>>,
    diagnostics: &mut Vec<Diagnostic>,
    tokens: Option<&mut Vec<InlineToken>>,
) -> Vec<Inline> {
    // Definitions are collected from the block structure alone.
    if definitions.is_none() {
        return Vec::new();
    }
    let first_diagnostic = diagnostics.len();
    let mut nodes = parse_inlines_with_context(
        input,
        0,
        definitions,
        diagnostics,
        &mut InlineState::default(),
    );
    tags::split_tags(input, &mut nodes);
    if let Some(tokens) = tokens {
        *tokens = tokens::tokens(input, &nodes);
        source_map::translate_tokens(map, tokens);
    }
    source_map::translate_inlines(map, &mut nodes, &mut diagnostics[first_diagnostic..]);
    nodes
}

/// The deepest inline nesting the parser builds. Directive labels parse their
/// content one inline pass deeper; within a pass, open brackets and every
/// emphasis or mark span each add a level. Content past this depth stays
/// literal text, so recursion and the native stack it uses stay bounded.
const MAX_INLINE_NESTING: usize = 32;

/// State shared by every inline parse nested under one block-level inline
/// parse. All nested inputs are slices of that one input, addressed by their
/// start offset in it; `parse_inlines` maps the result to the original input.
#[derive(Default)]
struct InlineState {
    /// How many inline parses enclose the current one.
    depth: usize,
}

/// What one inline pass threads through its construct parsers: the state it
/// shares with enclosing passes and the memoized scans of its own input.
struct InlinePass<'p, 'a> {
    state: &'p mut InlineState,
    scan: InlineScan<'a>,
}

fn parse_inlines_with_context(
    input: &str,
    base_offset: usize,
    definitions: Option<Labels<'_>>,
    diagnostics: &mut Vec<Diagnostic>,
    state: &mut InlineState,
) -> Vec<Inline> {
    if state.depth >= MAX_INLINE_NESTING {
        if input.is_empty() {
            return Vec::new();
        }
        return vec![Inline::Text(Text {
            meta: NodeMeta::new(Some(Span::new(base_offset, base_offset + input.len()))),
            value: input.into(),
        })];
    }
    state.depth += 1;
    let nodes = parse_inline_content(input, base_offset, definitions, diagnostics, state);
    state.depth -= 1;
    nodes
}

fn parse_inline_content(
    input: &str,
    base_offset: usize,
    definitions: Option<Labels<'_>>,
    diagnostics: &mut Vec<Diagnostic>,
    state: &mut InlineState,
) -> Vec<Inline> {
    let bytes = input.as_bytes();
    let mut nodes = Vec::new();
    let mut text_start = 0;
    let mut text = String::new();
    let mut index = 0;
    // Emphasis and mark delimiters are resolved with a delimiter stack after the
    // scan completes. During the scan we emit each candidate delimiter run as a
    // literal text node and record it here so `process_emphasis` can rewrite the
    // flat node list into emphasis and mark nodes (or leave it as text).
    let mut delimiters: Vec<DelimMarker> = Vec::new();
    let mut brackets = Brackets::new();
    let mut pass = InlinePass {
        state,
        scan: InlineScan::new(input),
    };
    // A literal autolink holds `://`, `www.`, or an email's `@`; content
    // without any of them is not scanned for one at each position.
    let literal_autolinks = bytes.contains(&b'@')
        || input.contains("://")
        || bytes
            .windows(4)
            .any(|window| window.eq_ignore_ascii_case(b"www."));

    while index < bytes.len() {
        if bytes[index] == b'\\' {
            if let Some((next_index, char)) = next_char(input, index + 1) {
                if char.is_ascii_punctuation() {
                    flush_text(&mut nodes, &mut text, text_start, base_offset + index);
                    nodes.push(Inline::Escape(Escape {
                        meta: NodeMeta::new(Some(Span::new(
                            base_offset + index,
                            base_offset + next_index,
                        ))),
                        value: char,
                    }));
                    index = next_index;
                    text_start = index;
                    continue;
                }
            }
        }

        if bytes[index] == b'&' {
            if let Some((end, _)) = parse_character_reference(input, index) {
                flush_text(&mut nodes, &mut text, text_start, base_offset + index);
                nodes.push(Inline::CharacterReference(CharacterReference {
                    meta: NodeMeta::new(Some(Span::new(base_offset + index, base_offset + end))),
                    reference: input[index..end].into(),
                }));
                index = end;
                text_start = index;
                continue;
            }
        }

        if bytes[index] == b'\n' {
            // Only a literal backslash, not one an escape or a reference wrote,
            // makes the line ending a hard break.
            if index > 0
                && bytes[index - 1] == b'\\'
                && !is_escaped_at(input, index - 1)
                && text.ends_with('\\')
            {
                text.pop();
                flush_text(
                    &mut nodes,
                    &mut text,
                    text_start,
                    base_offset + index.saturating_sub(1),
                );
                nodes.push(Inline::LineBreak(LineBreak {
                    meta: NodeMeta::new(Some(Span::new(
                        base_offset + index.saturating_sub(1),
                        base_offset + index + 1,
                    ))),
                    kind: LineBreakKind::Backslash,
                }));
                index += 1;
                text_start = index;
                continue;
            }
            // The spaces and tabs ending the line: a hard break or stripped.
            let trailing_spaces = trailing_space_count(&text);
            if is_hard_break_suffix(&text, trailing_spaces) {
                text.truncate(text.len() - trailing_spaces);
                flush_text(
                    &mut nodes,
                    &mut text,
                    text_start,
                    base_offset + index.saturating_sub(trailing_spaces),
                );
                nodes.push(Inline::LineBreak(LineBreak {
                    meta: NodeMeta::new(Some(Span::new(
                        base_offset + index.saturating_sub(trailing_spaces),
                        base_offset + index + 1,
                    ))),
                    kind: LineBreakKind::Spaces,
                }));
                index += 1;
                text_start = index;
                continue;
            }
            // Stripped spaces and tabs that no text holds, as after another
            // inline, are read as part of the soft break.
            let stripped_alone = trailing_spaces > 0 && text.len() == trailing_spaces;
            if trailing_spaces > 0 {
                text.truncate(text.len() - trailing_spaces);
            }
            flush_text(&mut nodes, &mut text, text_start, base_offset + index);
            let start = if stripped_alone {
                index - trailing_spaces
            } else {
                index
            };
            nodes.push(Inline::SoftBreak(SoftBreak {
                meta: NodeMeta::new(Some(Span::new(
                    base_offset + start,
                    base_offset + index + 1,
                ))),
            }));
            index += 1;
            text_start = index;
            continue;
        }

        if bytes[index] == b'`' {
            if let Some((end, value)) = parse_code_span_with(&mut pass.scan.lookups, input, index) {
                flush_text(&mut nodes, &mut text, text_start, base_offset + index);
                nodes.push(Inline::Code(CodeInline {
                    meta: NodeMeta::new(Some(Span::new(base_offset + index, base_offset + end))),
                    value,
                }));
                index = end;
                text_start = index;
                continue;
            } else {
                // No matching-length close for this opening backtick run:
                // CommonMark renders the whole run as literal text. Consume the
                // entire run here so the loop does not advance one byte and retry
                // a shorter sub-run that could spuriously match a shorter close
                // (```foo`` stayed a phantom 2-backtick code span).
                let run = bytes[index..]
                    .iter()
                    .take_while(|byte| **byte == b'`')
                    .count();
                if text.is_empty() {
                    text_start = base_offset + index;
                }
                for _ in 0..run {
                    text.push('`');
                }
                index += run;
                continue;
            }
        }

        if bytes[index] == b'*' && starts_delimiter_run(input, index, b'*') {
            let run_len = delimiter_byte_run_len(input, index, b'*');
            flush_text(&mut nodes, &mut text, text_start, base_offset + index);
            push_delimiter(
                &mut nodes,
                &mut delimiters,
                index,
                base_offset,
                b'*',
                run_len,
            );
            index += run_len;
            text_start = index;
            continue;
        }

        // Core `_` emphasis/strong is resolved by the delimiter stack, just like
        // `*`.
        if bytes[index] == b'_' && starts_delimiter_run(input, index, b'_') {
            // A leading `_` can begin a GFM email local part (`_a@b.c`); try the
            // literal autolink before recording the `_` as an emphasis
            // delimiter, otherwise the `_` would be consumed and the email would
            // wrongly start one char later (where its left boundary fails).
            if literal_autolinks {
                if let Some((end, _)) = parse_literal_autolink(
                    input,
                    index,
                    &mut pass.scan.literal_autolinks,
                    !brackets.open(),
                ) {
                    flush_text(&mut nodes, &mut text, text_start, base_offset + index);
                    nodes.push(autolink_node(
                        AutolinkForm::Literal,
                        Span::new(base_offset + index, base_offset + end),
                        &input[index..end],
                    ));
                    index = end;
                    text_start = index;
                    continue;
                }
            }
            let run_len = delimiter_byte_run_len(input, index, b'_');
            flush_text(&mut nodes, &mut text, text_start, base_offset + index);
            push_delimiter(
                &mut nodes,
                &mut delimiters,
                index,
                base_offset,
                b'_',
                run_len,
            );
            index += run_len;
            text_start = index;
            continue;
        }

        if bytes[index] == b'=' {
            let run_len = delimiter_byte_run_len(input, index, b'=');
            if run_len >= 2 {
                flush_text(&mut nodes, &mut text, text_start, base_offset + index);
                push_delimiter(
                    &mut nodes,
                    &mut delimiters,
                    index,
                    base_offset,
                    b'=',
                    run_len,
                );
                index += run_len;
                text_start = index;
                continue;
            }
        }

        let bracket_room = pass.state.depth - 1 + brackets.openers.len() < MAX_INLINE_NESTING;

        // `^[` opens an inline footnote.
        if bracket_room && bytes[index] == b'^' && bytes.get(index + 1) == Some(&b'[') {
            flush_text(&mut nodes, &mut text, text_start, base_offset + index);
            push_text(&mut nodes, base_offset + index, "^");
            push_text(&mut nodes, base_offset + index + 1, "[");
            brackets.openers.push(BracketOpener {
                kind: BracketKind::InlineFootnote,
                node_index: nodes.len() - 1,
                position: index,
                delimiter_bottom: delimiters.len(),
            });
            index += 2;
            text_start = index;
            continue;
        }

        // A run of exactly two `~` may open or close GFM strikethrough.
        // The run is measured only from its start, so the bytes of a longer
        // run, which go on as text one at a time, are not measured again.
        if bytes[index] == b'~' && starts_delimiter_run(input, index, b'~') {
            let run_len = delimiter_byte_run_len(input, index, b'~');
            if run_len == 2 {
                flush_text(&mut nodes, &mut text, text_start, base_offset + index);
                push_delimiter(
                    &mut nodes,
                    &mut delimiters,
                    index,
                    base_offset,
                    b'~',
                    run_len,
                );
                index += run_len;
                text_start = index;
                continue;
            }
        }

        if bytes[index] == b'!' && bytes.get(index + 1) == Some(&b'[') {
            // A wikilink at the `[` wins over the image, as it wins over a
            // link at a lone `[`, and the `!` makes it an embed; it takes no
            // bracket nesting, so it forms past the limit too.
            if let Some((end, wikilink)) =
                parse_wikilink(input, index + 1, base_offset, &mut pass.scan)
            {
                flush_text(&mut nodes, &mut text, text_start, base_offset + index);
                nodes.push(embed(wikilink, base_offset + index));
                // A wikilink is a link: no open bracket forms a link around it.
                brackets.close_links();
                index = end;
                text_start = index;
                continue;
            }
        }

        if bytes[index] == b'!' && bytes.get(index + 1) == Some(&b'[') && bracket_room {
            flush_text(&mut nodes, &mut text, text_start, base_offset + index);
            push_text(&mut nodes, base_offset + index, "!");
            push_text(&mut nodes, base_offset + index + 1, "[");
            brackets.openers.push(BracketOpener {
                kind: BracketKind::Image,
                node_index: nodes.len() - 1,
                position: index,
                delimiter_bottom: delimiters.len(),
            });
            index += 2;
            text_start = index;
            continue;
        }

        if bytes[index] == b'[' {
            if let Some((end, wikilink)) = parse_wikilink(input, index, base_offset, &mut pass.scan)
            {
                flush_text(&mut nodes, &mut text, text_start, base_offset + index);
                nodes.push(wikilink);
                brackets.close_links();
                index = end;
                text_start = index;
                continue;
            }
            if bracket_room {
                flush_text(&mut nodes, &mut text, text_start, base_offset + index);
                push_text(&mut nodes, base_offset + index, "[");
                brackets.openers.push(BracketOpener {
                    kind: BracketKind::Link,
                    node_index: nodes.len() - 1,
                    position: index,
                    delimiter_bottom: delimiters.len(),
                });
                index += 1;
                text_start = index;
                continue;
            }
            brackets.overflow += 1;
        }

        if bytes[index] == b']' && brackets.overflow > 0 {
            // Closes a `[` left as text past the nesting limit.
            brackets.overflow -= 1;
        } else if bytes[index] == b']' && !brackets.openers.is_empty() {
            flush_text(&mut nodes, &mut text, text_start, base_offset + index);
            if let Some(end) = close_bracket(
                input,
                base_offset,
                index,
                definitions,
                &mut nodes,
                &mut delimiters,
                &mut brackets,
                &mut pass,
            ) {
                index = end;
                text_start = index;
                continue;
            }
        }

        if bytes[index] == b'$' {
            if let Some((end, value, kind)) =
                parse_math_inline(&mut pass.scan.lookups, input, index)
            {
                flush_text(&mut nodes, &mut text, text_start, base_offset + index);
                nodes.push(Inline::Math(MathInline {
                    meta: NodeMeta::new(Some(Span::new(base_offset + index, base_offset + end))),
                    value,
                    kind,
                }));
                index = end;
                text_start = index;
                continue;
            }
            // A dollar run that opens but finds no exact-length close is emitted
            // as literal text in one piece (like a code-span). Skipping the
            // whole run prevents re-opening with a shorter marker inside it, so
            // `$$$foo$$` stays literal rather than matching `$$foo$$`. A lone
            // `$` before a backtick (the code-math form) is a run of 1, so this
            // still advances correctly when that form fails.
            let run = bytes[index..]
                .iter()
                .take_while(|byte| **byte == b'$')
                .count();
            if run > 1 {
                if text.is_empty() {
                    text_start = base_offset + index;
                }
                text.push_str(&input[index..index + run]);
                index += run;
                continue;
            }
        }

        // Inside an open `[` only an email address links; if the bracket
        // forms a link, `demote_links` turns it back into text.
        if literal_autolinks {
            if let Some((end, _)) = parse_literal_autolink(
                input,
                index,
                &mut pass.scan.literal_autolinks,
                !brackets.open(),
            ) {
                flush_text(&mut nodes, &mut text, text_start, base_offset + index);
                nodes.push(autolink_node(
                    AutolinkForm::Literal,
                    Span::new(base_offset + index, base_offset + end),
                    &input[index..end],
                ));
                index = end;
                text_start = index;
                continue;
            }
        }

        if bytes[index] == b'<' {
            if let Some(end) = pass.scan.lookups.find(">", index).map(|close| close + 1) {
                let uri = &input[index + 1..end - 1];
                if is_angle_autolink(uri) {
                    flush_text(&mut nodes, &mut text, text_start, base_offset + index);
                    nodes.push(autolink_node(
                        AutolinkForm::Angle,
                        Span::new(base_offset + index, base_offset + end),
                        uri,
                    ));
                    index = end;
                    text_start = index;
                    continue;
                }
            }
            if let Some(end) = html_inline_end(&mut pass.scan.lookups, input, index) {
                flush_text(&mut nodes, &mut text, text_start, base_offset + index);
                nodes.push(Inline::Html(HtmlInline {
                    meta: NodeMeta::new(Some(Span::new(base_offset + index, base_offset + end))),
                    value: input[index..end].into(),
                }));
                index = end;
                text_start = index;
                continue;
            }
        }

        if bytes[index] == b':' {
            if let Some((end, name)) = parse_shortcode(input, index) {
                flush_text(&mut nodes, &mut text, text_start, base_offset + index);
                nodes.push(Inline::Shortcode(Shortcode {
                    meta: NodeMeta::new(Some(Span::new(base_offset + index, base_offset + end))),
                    name,
                }));
                index = end;
                text_start = index;
                continue;
            }
        }

        // A directive counts one nesting level for itself, on top of the
        // enclosing passes and open brackets.
        if bytes[index] == b':' && pass.state.depth + brackets.openers.len() <= MAX_INLINE_NESTING {
            // The label parses one pass deeper than the open brackets around
            // it.
            pass.state.depth += brackets.openers.len();
            let directive = parse_text_directive(
                input,
                index,
                base_offset,
                definitions,
                diagnostics,
                &mut pass,
            );
            pass.state.depth -= brackets.openers.len();
            if let Some((end, directive)) = directive {
                flush_text(&mut nodes, &mut text, text_start, base_offset + index);
                if let Inline::TextDirective(node) = &directive {
                    // A link inside the directive label keeps open brackets
                    // from forming links around it.
                    if contains_link_inline(&node.label) {
                        brackets.close_links();
                    }
                    let depth = inline_nesting(&node.label) + 1;
                    brackets.formed.push((nodes.len(), depth));
                }
                nodes.push(directive);
                index = end;
                text_start = index;
                continue;
            }
        }

        let (next_index, char) = next_char(input, index).expect("valid UTF-8 byte index");
        if text.is_empty() {
            text_start = base_offset + index;
        }
        text.push(char);
        index = next_index;
    }

    flush_text(&mut nodes, &mut text, text_start, base_offset + input.len());
    assign_emphasis_roles(input, &mut delimiters);
    process_emphasis(nodes, delimiters, pass.state.depth - 1, &brackets.formed).0
}

/// A `:name:` shortcode at `index`: `name` is in the gemoji table, and the
/// source chars directly outside the colons are no Unicode letter or digit,
/// so clock times and words joined by a colon stay text.
fn parse_shortcode(input: &str, index: usize) -> Option<(usize, String)> {
    if input[index..].starts_with("::") {
        return None;
    }
    if input[..index]
        .chars()
        .next_back()
        .is_some_and(char::is_alphanumeric)
    {
        return None;
    }

    let mut cursor = index + 1;
    while let Some((next, char)) = next_char(input, cursor) {
        if char == ':' {
            let name = &input[index + 1..cursor];
            if crate::gemoji::glyph(name).is_none()
                || input[next..]
                    .chars()
                    .next()
                    .is_some_and(char::is_alphanumeric)
            {
                return None;
            }
            return Some((next, name.into()));
        }
        if !(char.is_ascii_alphanumeric() || matches!(char, '_' | '-' | '+')) {
            return None;
        }
        cursor = next;
    }
    None
}

fn parse_wikilink(
    input: &str,
    index: usize,
    base_offset: usize,
    scan: &mut InlineScan,
) -> Option<(usize, Inline)> {
    if input.as_bytes().get(index) != Some(&b'[') || input.as_bytes().get(index + 1) != Some(&b'[')
    {
        return None;
    }

    let close = scan.wikilink_close(index + 2)?;
    let source = &input[index + 2..close];
    if source.is_empty() || source.len() > WIKILINK_MAX_BYTES {
        return None;
    }

    let (target_source, label_source) = match find_wikilink_separator(source) {
        Some(separator) => (&source[..separator], &source[separator + 1..]),
        None => (source, source),
    };

    // Target and label keep their escapes and character references as
    // written.
    if target_source.is_empty() {
        return None;
    }
    let target = String::from(target_source);
    let label = String::from(label_source);
    let end = close + 2;
    Some((
        end,
        Inline::WikiLink(WikiLink {
            meta: NodeMeta::new(Some(Span::new(base_offset + index, base_offset + end))),
            target,
            label,
            embed: false,
        }),
    ))
}

/// `wikilink` marked as an embed by the `!` at `bang`, where its span starts.
fn embed(mut wikilink: Inline, bang: usize) -> Inline {
    if let Inline::WikiLink(node) = &mut wikilink {
        node.embed = true;
        node.meta.span = node.meta.span.map(|span| Span::new(bang, span.end));
    }
    wikilink
}

/// One step of the walk to a wikilink's closing `]]`, which must be on the
/// opener's line. The content holds no unescaped `[` or `]`.
fn wikilink_close_step(input: &str, cursor: usize) -> Step {
    let bytes = input.as_bytes();
    match bytes.get(cursor) {
        None | Some(b'\n' | b'\r' | b'[') => Step::Done(None),
        Some(b'\\') => {
            let escaped = cursor + 1;
            Step::Next(next_char(input, escaped).map_or(escaped, |(after_escape, _)| after_escape))
        }
        Some(b']') if bytes.get(cursor + 1) == Some(&b']') => Step::Done(Some(cursor)),
        Some(b']') => Step::Done(None),
        Some(_) => Step::Next(next_char(input, cursor).map_or(input.len(), |(next, _)| next)),
    }
}

fn find_wikilink_separator(input: &str) -> Option<usize> {
    let bytes = input.as_bytes();
    let mut cursor = 0;
    while cursor < input.len() {
        match bytes[cursor] {
            b'\\' => {
                cursor += 1;
                if cursor < input.len() {
                    cursor = next_char(input, cursor)?.0;
                }
            }
            b'|' => return Some(cursor),
            _ => cursor = next_char(input, cursor)?.0,
        }
    }
    None
}

fn trailing_space_count(input: &str) -> usize {
    input
        .as_bytes()
        .iter()
        .rev()
        .take_while(|byte| matches!(**byte, b' ' | b'\t'))
        .count()
}

fn is_hard_break_suffix(input: &str, trailing: usize) -> bool {
    // A hard line break is two or more spaces immediately before the newline
    // with no intervening tab; a tab anywhere in the trailing whitespace run
    // demotes it to a soft break.
    let bytes = input.as_bytes();
    trailing >= 2
        && bytes[bytes.len() - trailing..]
            .iter()
            .all(|byte| *byte == b' ')
}

/// The walk `InlineScan::reference_label_end` and `definition_label` take in
/// steps, run once from the start; the scan tests hold them to it.
#[cfg(test)]
fn find_reference_label_end(input: &str, open: usize) -> Option<usize> {
    // A reference/definition link label does not nest: it ends at the first
    // unescaped `]`, and an unescaped interior `[` disqualifies it.
    if input.as_bytes().get(open) != Some(&b'[') {
        return None;
    }
    let close = path_walk(open + 1, |cursor| reference_label_step(input, cursor))?;
    reference_label_is_within_limit(&input[open + 1..close]).then_some(close)
}

/// One step of the walk to a reference label's closing `]`.
fn reference_label_step(input: &str, cursor: usize) -> Step {
    let Some((next, char)) = next_char(input, cursor) else {
        return Step::Done(None);
    };
    match char {
        '\\' => Step::Next(next_char(input, next).map_or(next, |(after_escape, _)| after_escape)),
        '[' => Step::Done(None),
        ']' => Step::Done(Some(cursor)),
        _ => Step::Next(next),
    }
}

/// How many container levels `inlines` nest, counting empty containers.
fn inline_nesting(inlines: &[Inline]) -> usize {
    let mut deepest = 0;
    let mut pending = vec![(inlines, 0)];
    while let Some((nodes, depth)) = pending.pop() {
        for node in nodes {
            if is_inline_container(node) {
                deepest = deepest.max(depth + 1);
                pending.push((node.children(), depth + 1));
            }
        }
    }
    deepest
}

fn is_inline_container(inline: &Inline) -> bool {
    matches!(
        inline,
        Inline::Emphasis(_)
            | Inline::Strong(_)
            | Inline::Delete(_)
            | Inline::Mark(_)
            | Inline::Link(_)
            | Inline::Image(_)
            | Inline::LinkReference(_)
            | Inline::ImageReference(_)
            | Inline::InlineFootnote(_)
            | Inline::TextDirective(_)
    )
}

/// Whether `inlines` hold a link formed from brackets, at any depth: an
/// autolink, which keeps open brackets from nothing, does not count.
fn contains_link_inline(inlines: &[Inline]) -> bool {
    inlines.iter().any(|inline| {
        matches!(
            inline,
            Inline::Link(_) | Inline::LinkReference(_) | Inline::WikiLink(_)
        ) || contains_link_inline(inline.children())
    })
}

fn find_link_label_end(input: &str, open: usize) -> Option<usize> {
    if input.as_bytes().get(open) != Some(&b'[') {
        return None;
    }
    let mut lookups = DirectLookups { input };
    bracket_walk(open + 1, |cursor| {
        link_label_step(&mut lookups, input, cursor)
    })
}

/// One step of the walk to a link label's closing `]`: escapes, code spans,
/// autolinks, and inline HTML are stepped over whole, so brackets inside them
/// do not count; other brackets nest.
fn link_label_step(lookups: &mut impl Lookups, input: &str, cursor: usize) -> BracketStep {
    let Some((next, char)) = next_char(input, cursor) else {
        return BracketStep::End;
    };
    match char {
        '\\' => {
            BracketStep::Pass(next_char(input, next).map_or(next, |(after_escape, _)| after_escape))
        }
        '`' => BracketStep::Pass(code_span_end(lookups, input, cursor).unwrap_or(next)),
        '<' => BracketStep::Pass(
            autolink_end(lookups, input, cursor)
                .or_else(|| html_inline_end(lookups, input, cursor))
                .unwrap_or(next),
        ),
        '[' => BracketStep::Open(next),
        ']' => BracketStep::Close(next),
        _ => BracketStep::Pass(next),
    }
}

fn parse_text_directive(
    input: &str,
    index: usize,
    base_offset: usize,
    definitions: Option<Labels<'_>>,
    diagnostics: &mut Vec<Diagnostic>,
    pass: &mut InlinePass,
) -> Option<(usize, Inline)> {
    if input[index..].starts_with("::") {
        return None;
    }
    if index > 0 {
        let previous = input[..index].chars().next_back()?;
        if !previous.is_whitespace() && !matches!(previous, '(' | '[' | '{') {
            return None;
        }
    }
    let opener_offset = index + 1;
    let opener = parse_directive_opener_with(
        &input[opener_offset..],
        |close, open| {
            let found = match close {
                DirectiveClose::Label => pass.scan.link_label_end(opener_offset + open),
                DirectiveClose::Attributes => {
                    pass.scan.directive_attributes_close(opener_offset + open)
                }
            };
            found.map(|position| position - opener_offset)
        },
        |label, attributes, rest| text_directive_ends(label, attributes, rest.bytes().next()),
    );
    let opener = match opener {
        Ok(opener) => opener,
        Err(refused) => {
            // A `[` or `{` left open after a valid name is malformed; a bad
            // name, or an opener refused for what follows it, is plain text.
            if refused == Refused::Unclosed {
                diagnostics.push(Diagnostic::new(
                    DiagnosticSeverity::Error,
                    DiagnosticCode::InvalidDirectiveName,
                    Span::new(base_offset + index, base_offset + input.len()),
                    "text directive opener is malformed",
                ));
            }
            return None;
        }
    };
    let label = opener
        .label
        .map(|source| {
            parse_inlines_with_context(
                source,
                base_offset + index + 1 + opener.name.len() + 1,
                definitions,
                diagnostics,
                pass.state,
            )
        })
        .unwrap_or_default();
    let at = base_offset + opener_offset;
    opener.report_dropped(diagnostics, |start, end| Span::new(at + start, at + end));
    let DirectiveOpener {
        name,
        attributes,
        consumed,
        ..
    } = opener;
    Some((
        index + 1 + consumed,
        Inline::TextDirective(TextDirective {
            meta: NodeMeta::new(Some(Span::new(
                base_offset + index,
                base_offset + index + 1 + consumed,
            ))),
            name,
            label,
            attributes,
        }),
    ))
}

/// Whether a text directive with this label and attribute source ends before
/// `next`: whitespace or the end of the content, or ASCII punctuation when the
/// label is not empty or the attributes hold a non-space char. So `:e[a].` is
/// a directive, while `:word:`, `:a@b.c`, `(:note)`, `:e{}x`, `:e{}.`, and
/// `:e[a]b` stay text. Deciding from the sources keeps a refused opener from
/// parsing its attributes.
fn text_directive_ends(label: Option<&str>, attributes: Option<&str>, next: Option<u8>) -> bool {
    match next {
        None | Some(b' ' | b'\t' | b'\n' | b'\r') => true,
        Some(byte) if byte.is_ascii_punctuation() => {
            label.is_some_and(|label| !label.is_empty())
                || attributes
                    .is_some_and(|source| source.bytes().any(|byte| !byte.is_ascii_whitespace()))
        }
        Some(_) => false,
    }
}

/// A directive's name, label, and attributes, read from the text after its
/// colons.
struct DirectiveOpener<'a> {
    name: String,
    label: Option<&'a str>,
    attributes: Vec<DirectiveAttribute>,
    /// The ranges of the attributes dropped for having no valid name.
    dropped: Vec<(usize, usize)>,
    /// The bytes the opener takes.
    consumed: usize,
}

impl DirectiveOpener<'_> {
    /// A warning for each dropped attribute, spanning `span(start, end)`.
    fn report_dropped(
        &self,
        diagnostics: &mut Vec<Diagnostic>,
        span: impl Fn(usize, usize) -> Span,
    ) {
        for &(start, end) in &self.dropped {
            diagnostics.push(Diagnostic::new(
                DiagnosticSeverity::Warning,
                DiagnosticCode::InvalidDirectiveAttribute,
                span(start, end),
                "directive attribute without a valid name is dropped",
            ));
        }
    }
}

/// Why `parse_directive_opener_with` read no opener.
#[derive(Clone, Copy, PartialEq, Eq)]
enum Refused {
    /// The text after the colons does not start with a valid directive name.
    Name,
    /// The `[` or `{` after the name has no closing `]` or `}`.
    Unclosed,
    /// `accept` refused the opener for its label, attributes, or what follows.
    Follow,
}

/// `parse_directive_opener_with` for a block directive line, finding closing
/// brackets in `input` alone.
fn parse_directive_opener<'a>(
    input: &'a str,
    accept: impl FnOnce(Option<&str>, Option<&str>, &str) -> bool,
) -> Result<DirectiveOpener<'a>, Refused> {
    parse_directive_opener_with(
        input,
        |close, open| match close {
            DirectiveClose::Label => find_link_label_end(input, open),
            DirectiveClose::Attributes => find_directive_attributes_close(input, open),
        },
        accept,
    )
}

/// Which closing position `parse_directive_opener_with` asks its finder for.
#[derive(Clone, Copy)]
enum DirectiveClose {
    /// The `]` closing the `[label]` opening at the given position.
    Label,
    /// The `}` closing the `{attributes}` opening at the given position.
    Attributes,
}

/// Reads the directive opener at the start of `input`, the text after the
/// colons: a name, then an optional `[label]`, then optional `{attributes}`.
/// `find_close` gives the `]` or `}` closing the bracket at a position.
///
/// `accept` sees the label source, the attribute source, and the text after
/// the opener, and runs before the attributes are parsed. That order keeps
/// refused openers linear-time: `:a{` repeated, then `}x`, refuses every
/// opener without parsing the attribute source each one spans to the end.
/// The cost is that acceptance reads the attribute source, not the parsed
/// attributes: `:e{!}.` is a text directive, since its attribute source is not
/// blank, whose invalid attribute is dropped, so it is written `:e.`, which
/// reads back as text.
fn parse_directive_opener_with<'a>(
    input: &'a str,
    mut find_close: impl FnMut(DirectiveClose, usize) -> Option<usize>,
    accept: impl FnOnce(Option<&str>, Option<&str>, &str) -> bool,
) -> Result<DirectiveOpener<'a>, Refused> {
    let mut index = 0;
    while let Some((next, char)) = next_char(input, index) {
        if char.is_ascii_alphanumeric() || char == '_' || char == '-' {
            index = next;
        } else {
            break;
        }
    }
    let name = &input[..index];
    if !is_directive_name(name) {
        return Err(Refused::Name);
    }

    let mut label = None;
    let mut attribute_source = None;
    let mut consumed = index;
    if input.as_bytes().get(consumed) == Some(&b'[') {
        let close = find_close(DirectiveClose::Label, consumed).ok_or(Refused::Unclosed)?;
        label = Some(&input[consumed + 1..close]);
        consumed = close + 1;
    }
    if input.as_bytes().get(consumed) == Some(&b'{') {
        let close = find_close(DirectiveClose::Attributes, consumed).ok_or(Refused::Unclosed)?;
        attribute_source = Some((consumed + 1, &input[consumed + 1..close]));
        consumed = close + 1;
    }
    if !accept(
        label,
        attribute_source.map(|(_, source)| source),
        &input[consumed..],
    ) {
        return Err(Refused::Follow);
    }
    let (attributes, dropped) = match attribute_source {
        Some((start, source)) => {
            let (attributes, mut dropped) = parse_attributes(source);
            for range in &mut dropped {
                *range = (range.0 + start, range.1 + start);
            }
            (attributes, dropped)
        }
        None => (Vec::new(), Vec::new()),
    };

    Ok(DirectiveOpener {
        name: name.into(),
        label,
        attributes,
        dropped,
        consumed,
    })
}

/// Quote states of the walk to a directive's closing `}`: outside quotes,
/// inside `"…"`, inside `'…'`.
const DIRECTIVE_QUOTE_STATES: usize = 3;

fn find_directive_attributes_close(input: &str, open: usize) -> Option<usize> {
    if input.as_bytes().get(open) != Some(&b'{') {
        return None;
    }
    path_walk((open + 1) * DIRECTIVE_QUOTE_STATES, |node| {
        directive_attributes_step(input, node)
    })
}

/// One step of the walk to a directive's closing `}`, over nodes
/// `byte position * DIRECTIVE_QUOTE_STATES + quote state`: a `\` escapes the
/// next byte, and a `}` inside quotes does not close.
fn directive_attributes_step(input: &str, node: usize) -> Step {
    let bytes = input.as_bytes();
    let (cursor, quote) = (node / DIRECTIVE_QUOTE_STATES, node % DIRECTIVE_QUOTE_STATES);
    let at = |position: usize, quote: usize| Step::Next(position * DIRECTIVE_QUOTE_STATES + quote);
    let Some(&byte) = bytes.get(cursor) else {
        return Step::Done(None);
    };
    if byte == b'\\' {
        return at((cursor + 2).min(bytes.len()), quote);
    }
    match (quote, byte) {
        (0, b'"') => at(cursor + 1, 1),
        (0, b'\'') => at(cursor + 1, 2),
        (0, b'}') => Step::Done(Some(cursor)),
        (1, b'"') | (2, b'\'') => at(cursor + 1, 0),
        _ => at(cursor + 1, quote),
    }
}

/// The attributes in `input`, the text between a directive's braces, and the
/// ranges of `input` holding attributes dropped for having no valid name.
fn parse_attributes(input: &str) -> (Vec<DirectiveAttribute>, Vec<(usize, usize)>) {
    let mut attributes = Vec::new();
    let mut dropped = Vec::new();
    let mut cursor = 0;
    while cursor < input.len() {
        cursor = skip_spaces(input, cursor);
        if cursor >= input.len() {
            break;
        }

        if input.as_bytes().get(cursor) == Some(&b'#') {
            let (id, next) = parse_attribute_token(input, cursor + 1);
            if !id.is_empty() {
                attributes.push(DirectiveAttribute {
                    name: "id".into(),
                    value: Some(id.into()),
                });
            }
            cursor = next;
            continue;
        }

        if input.as_bytes().get(cursor) == Some(&b'.') {
            let (class, next) = parse_attribute_token(input, cursor + 1);
            if !class.is_empty() {
                attributes.push(DirectiveAttribute {
                    name: "class".into(),
                    value: Some(class.into()),
                });
            }
            cursor = next;
            continue;
        }

        let token_start = cursor;
        let (name, next) = parse_attribute_name(input, cursor);
        if name.is_empty() {
            dropped.push((token_start, input.trim_end().len().max(token_start)));
            break;
        }
        let mut token_end = next;
        cursor = skip_spaces(input, next);
        let value = if input.as_bytes().get(cursor) == Some(&b'=') {
            cursor = skip_spaces(input, cursor + 1);
            token_end = cursor;
            if let Some((value, next)) = parse_attribute_value(input, cursor) {
                cursor = next;
                token_end = next;
                Some(value)
            } else {
                Some(String::new())
            }
        } else {
            None
        };
        // A token that is no attribute name is dropped, as a malformed value
        // is read leniently: the document keeps only attributes it can write.
        if crate::validate::is_attribute_name(name) {
            attributes.push(DirectiveAttribute {
                name: name.into(),
                value,
            });
        } else {
            dropped.push((token_start, token_end));
        }
    }
    (attributes, dropped)
}

fn parse_attribute_token(input: &str, index: usize) -> (&str, usize) {
    let mut cursor = index;
    while let Some((next, char)) = next_char(input, cursor) {
        if char.is_whitespace() {
            break;
        }
        cursor = next;
    }
    (&input[index..cursor], cursor)
}

fn parse_attribute_name(input: &str, index: usize) -> (&str, usize) {
    let mut cursor = index;
    while let Some((next, char)) = next_char(input, cursor) {
        if char.is_whitespace() || char == '=' {
            break;
        }
        cursor = next;
    }
    (&input[index..cursor], cursor)
}

fn parse_attribute_value(input: &str, index: usize) -> Option<(String, usize)> {
    let quote = input.as_bytes().get(index).copied();
    if matches!(quote, Some(b'"' | b'\'')) {
        let quote = quote?;
        let mut cursor = index + 1;
        while cursor < input.len() {
            let (next, char) = next_char(input, cursor)?;
            if char as u8 == quote && !is_escaped_at(input, cursor) {
                return Some((
                    decode_escapes_and_references(&input[index + 1..cursor]),
                    next,
                ));
            }
            cursor = next;
        }
        return None;
    }

    let (value, next) = parse_attribute_token(input, index);
    Some((
        decode_selected_escapes_and_references(value, |char| matches!(char, '\\' | '&')),
        next,
    ))
}

/// The end and the normalized value of the code span opening at `index`.
fn parse_code_span_with(
    lookups: &mut impl Lookups,
    input: &str,
    index: usize,
) -> Option<(usize, String)> {
    let len = backtick_run_len(input, index);
    let search_start = index + len;
    let close = lookups.code_span_close(search_start, len)?;
    Some((
        close + len,
        normalize_code_span(&input[search_start..close]),
    ))
}

/// The end of the code span opening at `index`, as `parse_code_span` finds it.
fn code_span_end(lookups: &mut impl Lookups, input: &str, index: usize) -> Option<usize> {
    let len = backtick_run_len(input, index);
    Some(lookups.code_span_close(index + len, len)? + len)
}

fn find_code_span_close(input: &str, start: usize, marker_len: usize) -> Option<usize> {
    let bytes = input.as_bytes();
    let mut cursor = start;
    while cursor < bytes.len() {
        if bytes[cursor] != b'`' {
            cursor = next_char(input, cursor)
                .map(|(next, _)| next)
                .unwrap_or(bytes.len());
            continue;
        }
        let run_len = bytes[cursor..]
            .iter()
            .take_while(|byte| **byte == b'`')
            .count();
        if run_len == marker_len {
            return Some(cursor);
        }
        cursor += run_len;
    }
    None
}

fn normalize_code_span(input: &str) -> String {
    let (before, after) = code_padding(input);
    let mut normalized = String::new();
    let content = &input[before..input.len() - after];
    let mut cursor = 0;
    while cursor < content.len() {
        let (next, char) = next_char(content, cursor).expect("valid UTF-8 byte index");
        if char == '\r' {
            if content.as_bytes().get(next) == Some(&b'\n') {
                cursor = next + 1;
            } else {
                cursor = next;
            }
            normalized.push(' ');
            continue;
        }
        if char == '\n' {
            normalized.push(' ');
            cursor = next;
            continue;
        }
        normalized.push(char);
        cursor = next;
    }
    normalized
}

/// The bytes of padding a code span or `$` math drops from each end of
/// `input`, its content: one space or line ending at each end, when both ends
/// hold one and the content is not all spaces and line endings.
pub(crate) fn code_padding(input: &str) -> (usize, usize) {
    let space = |text: &str| -> Option<usize> {
        match text.as_bytes().first()? {
            b' ' | b'\n' => Some(1),
            b'\r' if text.as_bytes().get(1) == Some(&b'\n') => Some(2),
            b'\r' => Some(1),
            _ => None,
        }
    };
    let end_space = |text: &str| -> Option<usize> {
        match text.as_bytes().last()? {
            b' ' | b'\r' => Some(1),
            b'\n' if text.len() >= 2 && text.as_bytes()[text.len() - 2] == b'\r' => Some(2),
            b'\n' => Some(1),
            _ => None,
        }
    };
    match (space(input), end_space(input)) {
        (Some(before), Some(after))
            if input
                .bytes()
                .any(|byte| !matches!(byte, b' ' | b'\n' | b'\r')) =>
        {
            (before, after)
        }
        _ => (0, 0),
    }
}

fn can_open_delimited(input: &str, index: usize, marker_len: usize) -> bool {
    delimiter_flanking(input, index, marker_len).left
}

fn can_close_delimited(input: &str, index: usize, marker_len: usize) -> bool {
    delimiter_flanking(input, index, marker_len).right
}

/// Whether a run of `marker` bytes starts at `index`: the byte before it is
/// not an unescaped `marker`. Only the one byte is looked at, so asking at
/// every byte of a long run stays linear.
fn starts_delimiter_run(input: &str, index: usize, marker: u8) -> bool {
    index == 0 || input.as_bytes()[index - 1] != marker || is_escaped_at(input, index - 1)
}

fn delimiter_byte_run_len(input: &str, index: usize, marker: u8) -> usize {
    let bytes = input.as_bytes();
    let mut cursor = index;
    while bytes.get(cursor) == Some(&marker) {
        cursor += 1;
    }
    cursor - index
}

#[derive(Clone, Copy)]
struct DelimiterFlanking {
    left: bool,
    right: bool,
    previous: Option<char>,
    next: Option<char>,
    /// The char before the run, read past a variation selector, is
    /// punctuation (a "Unicode punctuation sequence").
    previous_punctuation: bool,
    next_punctuation: bool,
}

/// How one side of a delimiter run reads for flanking.
#[derive(Clone, Copy, Default)]
struct FlankingSide {
    whitespace: bool,
    punctuation: bool,
    cjk: bool,
    ideographic_variation_selector: bool,
}

impl FlankingSide {
    fn of(value: Option<char>) -> Self {
        let Some(value) = value else {
            return Self {
                whitespace: true,
                ..Self::default()
            };
        };
        Self {
            whitespace: value.is_whitespace(),
            punctuation: is_flanking_punctuation(value),
            cjk: crate::unicode_cjk::is_cjk(value),
            ideographic_variation_selector: crate::unicode_cjk::is_ideographic_variation_selector(
                value,
            ),
        }
    }

    /// The side before a run whose previous char is `previous` and, before
    /// that, `before_previous`: a general-use variation selector reads as the
    /// char it follows, unless that is whitespace or absent, where it reads as
    /// a plain character (unspecified by the amendments), and `‘’“”` with
    /// U+FE01 read as CJK punctuation, as micromark-extension-cjk-friendly
    /// reads them.
    fn before(previous: Option<char>, before_previous: impl FnOnce() -> Option<char>) -> Self {
        match previous {
            Some(selector) if crate::unicode_cjk::is_general_use_variation_selector(selector) => {
                match before_previous() {
                    Some(base) if !base.is_whitespace() => {
                        if selector == '\u{FE01}' && matches!(base, '‘' | '’' | '“' | '”') {
                            return Self {
                                punctuation: true,
                                cjk: true,
                                ..Self::default()
                            };
                        }
                        Self {
                            ideographic_variation_selector: false,
                            ..Self::of(Some(base))
                        }
                    }
                    _ => Self::default(),
                }
            }
            _ => Self::of(previous),
        }
    }
}

fn delimiter_flanking(input: &str, index: usize, marker_len: usize) -> DelimiterFlanking {
    delimiter_flanking_within(input, index, marker_len, false, false)
}

/// `delimiter_flanking` for a run that may sit right inside a mark span: a
/// bounded side flanks as if the input ended there, the way the span's content
/// reads on its own.
///
/// Left- and right-flanking follow the CommonMark CJK-friendly amendments
/// (<https://github.com/tats-u/markdown-cjk-friendly/blob/5b17173/specification.md>,
/// section 6.2), in the reduced form of the amendments' implementers' tips:
/// a run is left-flanking when not followed by whitespace and either not
/// followed by punctuation, or preceded by whitespace or punctuation, or with
/// a CJK char on either side or an ideographic variation selector before it;
/// right-flanking is the mirror, without the selector.
fn delimiter_flanking_within(
    input: &str,
    index: usize,
    marker_len: usize,
    bounded_before: bool,
    bounded_after: bool,
) -> DelimiterFlanking {
    let previous = if bounded_before {
        None
    } else {
        input[..index].chars().next_back().map(source_char)
    };
    let next = if bounded_after {
        None
    } else {
        input[index + marker_len..].chars().next().map(source_char)
    };

    let before = FlankingSide::before(previous, || {
        let mut chars = input[..index].chars();
        chars.next_back();
        chars.next_back().map(source_char)
    });
    let after = FlankingSide::of(next);

    let left = !after.whitespace
        && (!after.punctuation
            || before.whitespace
            || before.punctuation
            || after.cjk
            || before.cjk
            || before.ideographic_variation_selector);
    let right = !before.whitespace
        && (!before.punctuation
            || after.whitespace
            || after.punctuation
            || before.cjk
            || after.cjk);

    DelimiterFlanking {
        left,
        right,
        previous,
        next,
        previous_punctuation: before.punctuation,
        next_punctuation: after.punctuation,
    }
}

/// Dollar-fenced inline math, GitHub Flavored Markdown dialect.
///
/// A `$` is a flanking delimiter resolved at scan time (math is not pushed onto
/// the emphasis delimiter stack). An opening run of one or two `$` (runs of
/// three or more never form math) scans forward for a matching closing run:
///
/// * single `$`: cannot open if the next char is ASCII whitespace; the closing
///   `$` cannot be preceded by ASCII whitespace nor followed by an ASCII digit;
///   a `\$` inside is skipped (the backslash is kept verbatim, never a
///   delimiter); the close must be a run of exactly one `$`.
/// * double `$$`: no flanking and no digit guard; closes on the next run of two
///   `$`; content is kept verbatim and may span newlines (this is still an
///   inline display span — `$$` flow blocks are handled by `parse_math_block`).
///
/// The closing run is matched greedily (the nearest valid close wins), which is
/// equivalent to emphasis-style "nearest preceding open" because a failed open
/// emits a literal `$`/`$$` and the scan resumes after it. Content for the
/// single-`$` form is normalized like a code span (line endings → spaces, one
/// edge-space strip); the `$$` display form is verbatim. The `` $`…`$ `` code
/// form takes precedence.
fn parse_math_inline(
    lookups: &mut impl Lookups,
    input: &str,
    index: usize,
) -> Option<(usize, String, MathInlineKind)> {
    if let Some((end, value)) = parse_math_code_inline(lookups, input, index) {
        return Some((end, value, MathInlineKind::Code));
    }

    let bytes = input.as_bytes();
    let open_dollars = bytes[index..]
        .iter()
        .take_while(|byte| **byte == b'$')
        .count();
    // The maximum math fence length is 2 dollars: a run of three or more never
    // opens math.
    if open_dollars == 0 || open_dollars > 2 {
        return None;
    }

    let content_start = index + open_dollars;
    let close = scan_to_closing_dollar(lookups, input, content_start, open_dollars)?;
    let content_end = close - open_dollars;
    // The span requires `endpos - startpos >= fence_length * 2 + 1`, i.e. at
    // least one content byte between the open and close fences.
    if content_end <= content_start {
        return None;
    }

    let raw = &input[content_start..content_end];
    let dollars = u8::try_from(open_dollars).unwrap_or(u8::MAX);
    let kind = MathInlineKind::Dollar { dollars };
    let value = if math_is_padded(kind) {
        normalize_math_text(raw)
    } else {
        raw.into()
    };
    Some((close, value, kind))
}

/// Whether math of `kind` follows the code-span content rules: line endings
/// read as spaces, and padding `code_padding` finds is dropped. Only
/// single-dollar math does.
pub(crate) fn math_is_padded(kind: MathInlineKind) -> bool {
    matches!(kind, MathInlineKind::Dollar { dollars: 1 })
}

/// Whether `written`, read alone, is exactly one inline math holding `value`
/// as `kind`: validation's check that dollar math reads back as written.
pub(crate) fn reads_as_inline_math(written: &str, value: &str, kind: MathInlineKind) -> bool {
    parse_math_inline(&mut DirectLookups { input: written }, written, 0).is_some_and(
        |(end, read, read_kind)| end == written.len() && read == value && read_kind == kind,
    )
}

/// Scans for the closing dollar run. `start` is the first content byte
/// (just past the opening run); returns the byte offset just past a matching
/// closing run of exactly `open_dollars` `$`.
fn scan_to_closing_dollar(
    lookups: &mut impl Lookups,
    input: &str,
    start: usize,
    open_dollars: usize,
) -> Option<usize> {
    let bytes = input.as_bytes();
    if open_dollars == 1 {
        // A space immediately after a single opening `$` forbids the open.
        if bytes.get(start).is_some_and(|byte| is_math_space(*byte)) {
            return None;
        }
        // An escaped `\$` is content, not a delimiter (the backslash stays in
        // the content verbatim); the first other `$` closes, unless a space
        // comes before it or an ASCII digit after it. The lookup keeps a run
        // of `\$` from being walked again from each `$` that opens before it.
        let close = lookups.unescaped_dollar(start)?;
        if is_math_space(bytes[close - 1]) || bytes.get(close + 1).is_some_and(u8::is_ascii_digit) {
            return None;
        }
        return Some(close + 1);
    }
    // The display form closes at the first `$$`, even the first two `$` of a
    // longer run.
    lookups.find("$$", start).map(|close| close + 2)
}

/// Math whitespace: ASCII tab, line feed, carriage return, and space.
fn is_math_space(byte: u8) -> bool {
    matches!(byte, b'\t' | b'\n' | b'\r' | b' ')
}

/// Applies the code-span content rules to dollar-fenced math: line endings
/// become single spaces, and the padding `code_padding` finds is dropped.
fn normalize_math_text(input: &str) -> String {
    normalize_code_span(input)
}

fn parse_math_code_inline(
    lookups: &mut impl Lookups,
    input: &str,
    index: usize,
) -> Option<(usize, String)> {
    if !input[index..].starts_with("$`") {
        return None;
    }

    let search_start = index + 2;
    let close = lookups.find("`$", search_start)?;
    if close == search_start {
        return None;
    }

    Some((close + 2, input[search_start..close].into()))
}

fn parse_link_resource(
    lookups: &mut impl Lookups,
    input: &str,
    open: usize,
) -> Option<(usize, ParsedLinkResource, LinkTailRanges)> {
    let bytes = input.as_bytes();
    if bytes.get(open) != Some(&b'(') {
        return None;
    }
    let (mut cursor, initial_space) = skip_link_resource_space_with_info(input, open + 1)?;
    if bytes.get(cursor) == Some(&b')') {
        return Some((
            cursor + 1,
            ParsedLinkResource {
                destination: String::new(),
                destination_kind: LinkDestinationKind::Omitted,
                title: None,
            },
            LinkTailRanges {
                destination: (cursor, cursor),
                title: None,
            },
        ));
    }
    if initial_space && matches!(bytes.get(cursor), Some(b'"' | b'\'' | b'(')) {
        let omitted = cursor;
        let (title, next) = parse_link_title(input, cursor)?;
        let title_range = (cursor + 1, next - 1);
        cursor = skip_link_resource_space(input, next)?;
        if bytes.get(cursor) == Some(&b')') {
            return Some((
                cursor + 1,
                ParsedLinkResource {
                    destination: String::new(),
                    destination_kind: LinkDestinationKind::Omitted,
                    title: Some(title),
                },
                LinkTailRanges {
                    destination: (omitted, omitted),
                    title: Some(title_range),
                },
            ));
        }
        return None;
    }
    let destination_start = cursor;
    let (destination, destination_kind, next) = parse_link_destination(lookups, input, cursor)?;
    let destination_range = match destination_kind {
        LinkDestinationKind::Angle => (destination_start + 1, next - 1),
        _ => (destination_start, next),
    };
    let (after_destination, had_space) = skip_link_resource_space_with_info(input, next)?;
    cursor = after_destination;
    if bytes.get(cursor) == Some(&b')') {
        return Some((
            cursor + 1,
            ParsedLinkResource {
                destination,
                destination_kind,
                title: None,
            },
            LinkTailRanges {
                destination: destination_range,
                title: None,
            },
        ));
    }
    if !had_space {
        return None;
    }

    let (title, next) = parse_link_title(input, cursor)?;
    let title_range = (cursor + 1, next - 1);
    cursor = skip_link_resource_space(input, next)?;
    if bytes.get(cursor) == Some(&b')') {
        Some((
            cursor + 1,
            ParsedLinkResource {
                destination,
                destination_kind,
                title: Some(title),
            },
            LinkTailRanges {
                destination: destination_range,
                title: Some(title_range),
            },
        ))
    } else {
        None
    }
}

fn parse_link_destination(
    lookups: &mut impl Lookups,
    input: &str,
    index: usize,
) -> Option<(String, LinkDestinationKind, usize)> {
    if input.as_bytes().get(index) == Some(&b'<') {
        let stop = lookups.angle_destination_stop(index + 1)?;
        if input.as_bytes()[stop] != b'>' {
            return None;
        }
        return Some((
            decode_escapes_and_references(&input[index + 1..stop]),
            LinkDestinationKind::Angle,
            stop + 1,
        ));
    }

    let mut cursor = index;
    let mut depth = 0usize;
    while cursor < input.len() {
        let (next, char) = next_char(input, cursor)?;
        // A bare destination terminates on ASCII space or an ASCII control
        // character; Unicode whitespace (e.g. U+00A0) is ordinary. A backslash
        // before a space is NOT an escape (only ASCII punctuation is escapable),
        // so `\ ` still terminates the destination → `[a](\ b)` is not a link.
        if char == ' ' || source_char(char).is_ascii_control() {
            break;
        }
        if char == '(' && !is_escaped_at(input, cursor) {
            depth += 1;
            // CommonMark caps balanced parens in a bare destination at depth 32.
            if depth > 32 {
                return None;
            }
        } else if char == ')' && !is_escaped_at(input, cursor) {
            if depth == 0 {
                break;
            }
            depth -= 1;
        }
        cursor = next;
    }

    if cursor == index || depth > 0 {
        None
    } else {
        Some((
            decode_escapes_and_references(&input[index..cursor]),
            LinkDestinationKind::Bare,
            cursor,
        ))
    }
}

fn parse_link_title(input: &str, index: usize) -> Option<(Title, usize)> {
    let opener = input.as_bytes().get(index).copied()?;
    let (closer, title_kind) = match opener {
        b'"' => ('"', LinkTitleKind::DoubleQuote),
        b'\'' => ('\'', LinkTitleKind::SingleQuote),
        b'(' => (')', LinkTitleKind::Paren),
        _ => return None,
    };
    let mut cursor = index + 1;
    while cursor < input.len() {
        let (next, char) = next_char(input, cursor)?;
        if char == closer && !is_escaped_at(input, cursor) {
            if contains_blank_line(&input[index + 1..cursor]) {
                return None;
            }
            let value = decode_escapes_and_references(&input[index + 1..cursor]);
            return Some((Title::new(value, title_kind), next));
        }
        if opener == b'(' && char == '(' && !is_escaped_at(input, cursor) {
            return None;
        }
        cursor = next;
    }
    None
}

fn contains_blank_line(input: &str) -> bool {
    if !input.bytes().any(|byte| matches!(byte, b'\n' | b'\r')) {
        return false;
    }
    // A title that merely begins or ends with an EOL is allowed; only an INTERIOR
    // blank line (a blank line bounded by content on both sides) is rejected. The
    // empty first/last line entries that a leading/trailing newline produces are
    // boundary artifacts, not blank lines in the title content.
    let map = SourceMap::verbatim(input.len(), 0);
    let lines = collect_lines(input, &map);
    let interior = lines.len().saturating_sub(1);
    lines
        .iter()
        .take(interior)
        .skip(1)
        .any(|line| is_blank(line.text))
}

fn skip_link_resource_space(input: &str, index: usize) -> Option<usize> {
    skip_link_resource_space_with_info(input, index).map(|(index, _)| index)
}

fn skip_link_resource_space_with_info(input: &str, mut index: usize) -> Option<(usize, bool)> {
    let mut line_breaks = 0usize;
    let mut had_space = false;
    while input
        .as_bytes()
        .get(index)
        .is_some_and(|byte| matches!(*byte, b' ' | b'\t' | b'\n' | b'\r'))
    {
        had_space = true;
        match input.as_bytes()[index] {
            b'\n' => {
                line_breaks += 1;
                if line_breaks > 1 {
                    return None;
                }
                index += 1;
            }
            b'\r' => {
                line_breaks += 1;
                if line_breaks > 1 {
                    return None;
                }
                if input.as_bytes().get(index + 1) == Some(&b'\n') {
                    index += 2;
                } else {
                    index += 1;
                }
            }
            _ => index += 1,
        }
    }
    Some((index, had_space))
}

pub(crate) fn is_escaped_at(input: &str, index: usize) -> bool {
    let bytes = input.as_bytes();
    let mut cursor = index;
    let mut count = 0;
    while cursor > 0 && bytes[cursor - 1] == b'\\' {
        count += 1;
        cursor -= 1;
    }
    count % 2 == 1
}

fn parse_definition_destination_title(input: &str) -> Option<ParsedLinkResource> {
    let (mut cursor, _) = skip_link_resource_space_with_info(input, 0)?;
    let (destination, destination_kind, next) =
        parse_link_destination(&mut DirectLookups { input }, input, cursor)?;
    cursor = next;

    let (next, had_space) = skip_link_resource_space_with_info(input, cursor)?;
    cursor = next;
    if cursor >= input.len() {
        return Some(ParsedLinkResource {
            destination,
            destination_kind,
            title: None,
        });
    }
    if !had_space {
        return None;
    }

    let (title, next) = parse_link_title(input, cursor)?;
    let after_title = skip_link_resource_space(input, next)?;
    (after_title == input.len()).then_some(ParsedLinkResource {
        destination,
        destination_kind,
        title: Some(title),
    })
}

/// The char that closes the title `source` opens after its destination, when
/// no unescaped one follows the opener yet.
fn open_definition_title(source: &str) -> Option<char> {
    let (cursor, _) = skip_link_resource_space_with_info(source, 0)?;
    let (_, _, next) =
        parse_link_destination(&mut DirectLookups { input: source }, source, cursor)?;
    let (cursor, had_space) = skip_link_resource_space_with_info(source, next)?;
    if !had_space {
        return None;
    }
    let closer = match source.as_bytes().get(cursor)? {
        b'"' => '"',
        b'\'' => '\'',
        b'(' => ')',
        _ => return None,
    };
    (!line_may_close_title(&source[cursor + 1..], closer)).then_some(closer)
}

/// Whether `line` holds an unescaped `closer`, or an unescaped `(` inside a
/// parenthesized title, either of which settles the title. A backslash
/// escape never spans a line ending, so each line is read alone.
fn line_may_close_title(line: &str, closer: char) -> bool {
    line.char_indices().any(|(index, char)| {
        (char == closer || (closer == ')' && char == '(')) && !is_escaped_at(line, index)
    })
}

fn line_can_start_definition_title(input: &str) -> bool {
    let trimmed = trim_ascii_start(input);
    matches!(trimmed.as_bytes().first(), Some(b'"' | b'\'' | b'('))
}

fn push_line(output: &mut String, line: &str) {
    if !output.is_empty() {
        output.push('\n');
    }
    output.push_str(line);
}

/// Ends a code or math block's last line when the input ended without a line
/// ending: every line of such a block's value ends with one. The added ending
/// repeats the value's first line ending, `\n` when it has none.
fn end_last_line(value: &mut String) {
    if value.is_empty() || ends_with_line_ending(value) {
        return;
    }
    value.push_str(value_line_ending(value));
}

/// The line ending a code or math value's lines take: its first one, `\n`
/// when it has none.
fn value_line_ending(value: &str) -> &'static str {
    match value.find(['\r', '\n']) {
        Some(index) if value[index..].starts_with("\r\n") => "\r\n",
        Some(index) if value[index..].starts_with('\r') => "\r",
        _ => "\n",
    }
}

fn ends_with_line_ending(input: &str) -> bool {
    input.ends_with('\n') || input.ends_with('\r')
}

fn flush_text(nodes: &mut Vec<Inline>, text: &mut String, text_start: usize, end: usize) {
    if !text.is_empty() {
        nodes.push(Inline::Text(Text {
            meta: NodeMeta::new(Some(Span::new(text_start, end))),
            value: core::mem::take(text),
        }));
    }
}

fn next_char(input: &str, index: usize) -> Option<(usize, char)> {
    let char = input[index..].chars().next()?;
    Some((index + char.len_utf8(), char))
}

/// A CommonMark "Unicode punctuation character" for emphasis/strong flanking:
/// ASCII punctuation plus the non-ASCII Unicode `P*`/`S*` categories. Only the
/// flanking classification needs the Unicode set; escape/label logic stays
/// ASCII-only via `char::is_ascii_punctuation`.
fn is_flanking_punctuation(value: char) -> bool {
    value.is_ascii_punctuation() || crate::unicode_punctuation::is_unicode_punctuation(value)
}

/// Fold a reference label to its matching identifier. Per CommonMark, two
/// labels match when their RAW source (no backslash unescape, no entity decode)
/// agrees after collapsing internal spaces, tabs, and line endings to a single
/// space, trimming, and Unicode case-folding (`to_uppercase()` then
/// `to_lowercase()`). So `[foo\!]`
/// does NOT match `[foo!]`, and `[&copy;]` does NOT match `[©]`.
///
/// The serializer's `normalize_reference_label` delegates here so the
/// Shortcut/Collapsed omission oracle stays in lockstep with this matcher.
pub(crate) fn normalize_label(label: &str) -> String {
    label
        // Unicode full casefold maps capital sharp S (ẞ, U+1E9E) to "ss"; Rust's
        // `to_uppercase` leaves it unchanged (it is already uppercase), so without
        // this `[ẞ]` would not match a `[SS]: …` definition (links 540). This is
        // the only char where `to_uppercase().to_lowercase()` diverges from the
        // full casefold that matters for label matching.
        .replace('ẞ', "ss")
        .replace('\0', "\u{FFFD}")
        .split([' ', '\t', '\n', '\r'])
        .filter(|word| !word.is_empty())
        .collect::<Vec<_>>()
        .join(" ")
        .to_uppercase()
        .to_lowercase()
}

/// The identifiers a document's references can resolve to: those of its own
/// definitions, sorted and deduplicated so that a lookup is a binary search.
#[derive(Clone, Copy)]
pub(crate) struct Labels<'a> {
    pub(crate) own: &'a [String],
}

fn definition_exists(definitions: Option<Labels<'_>>, label: &str) -> bool {
    if label.is_empty() || !reference_label_is_within_limit(label) {
        return false;
    }
    let Some(definitions) = definitions else {
        return false;
    };
    definitions.own.binary_search(&identifier(label)).is_ok()
}

/// The identifier a reference with `label` resolves to: its normalized form,
/// with U+0000 read as U+FFFD as in the definitions a document holds.
fn identifier(label: &str) -> String {
    let identifier = normalize_label(label);
    if identifier.contains('\0') {
        identifier.replace('\0', "\u{FFFD}")
    } else {
        identifier
    }
}

fn reference_label_is_within_limit(label: &str) -> bool {
    label.chars().take(REFERENCE_LABEL_MAX_CHARS + 1).count() <= REFERENCE_LABEL_MAX_CHARS
}

/// Whether `[label]` reads back as a link reference label holding `label`:
/// the walk to its `]` ends at its own `]`, so the label holds no unescaped
/// bracket and does not escape its close; it is within the length limit, is
/// not blank, and holds no blank line, which would end its paragraph.
pub(crate) fn is_reference_label(label: &str) -> bool {
    let written = alloc::format!("[{label}]");
    path_walk(1, |cursor| reference_label_step(&written, cursor)) == Some(written.len() - 1)
        && reference_label_is_within_limit(label)
        && !normalize_label(label).is_empty()
        && !holds_blank_line(label)
}

/// Whether `[^label]` reads back as a footnote label holding `label`: a
/// footnote label whose `]` it does not escape.
pub(crate) fn is_written_footnote_label(label: &str) -> bool {
    is_footnote_label(label) && !is_escaped_at(&alloc::format!("{label}]"), label.len())
}

/// Whether a line of `text` other than its first and its last, which share
/// their lines with what is written around `text`, is blank.
fn holds_blank_line(text: &str) -> bool {
    let text = text.replace("\r\n", "\n");
    let lines: Vec<&str> = text.split(['\n', '\r']).collect();
    lines.len() > 2 && lines[1..lines.len() - 1].iter().any(|line| is_blank(line))
}

fn trim_up_to_three_spaces(input: &str) -> Option<&str> {
    let (columns, bytes) = leading_indent(input);
    if columns <= 3 {
        Some(&input[bytes..])
    } else {
        None
    }
}

/// The marker and length of the code fence that `input` opens: three or more
/// backticks or tildes, where a backtick fence's info string holds no backtick.
fn fence_start(input: &str) -> Option<(FenceMarker, usize)> {
    let marker = match input.as_bytes().first()? {
        b'`' => FenceMarker::Backtick,
        b'~' => FenceMarker::Tilde,
        _ => return None,
    };
    let byte = match marker {
        FenceMarker::Backtick => b'`',
        FenceMarker::Tilde => b'~',
    };
    let length = input
        .as_bytes()
        .iter()
        .take_while(|item| **item == byte)
        .count();
    let opens = length >= 3 && (byte == b'~' || !input[length..].contains('`'));
    opens.then_some((marker, length))
}

fn fence_close(input: &str, marker: FenceMarker, length: usize) -> bool {
    let byte = match marker {
        FenceMarker::Backtick => b'`',
        FenceMarker::Tilde => b'~',
    };
    let count = input
        .as_bytes()
        .iter()
        .take_while(|item| **item == byte)
        .count();
    count >= length && is_blank(&input[count..])
}

fn trim_closing_hashes(input: &str) -> &str {
    let input = input.trim_end_matches([' ', '\t']);
    let hash_start = input.trim_end_matches('#').len();
    if hash_start == input.len() {
        return input;
    }
    if hash_start == 0 {
        return "";
    }

    let before = &input[..hash_start];
    if before.ends_with(' ') || before.ends_with('\t') {
        before.trim_end_matches([' ', '\t'])
    } else {
        input
    }
}

/// Whether `input` opens with a list item marker, up to three spaces in.
fn opens_list_item(input: &str) -> bool {
    trim_up_to_three_spaces(input).is_some_and(|rest| blocks::list_marker_head(rest).is_some())
}

/// The offset of `slice` inside `text` when it is a borrowed sub-slice of it.
fn slice_offset_in(text: &str, slice: &str) -> Option<usize> {
    let offset = (slice.as_ptr() as usize).checked_sub(text.as_ptr() as usize)?;
    (offset + slice.len() <= text.len()).then_some(offset)
}

fn leading_indent(input: &str) -> (usize, usize) {
    leading_indent_at(input, 0)
}

/// The columns and bytes of `input`'s leading spaces and tabs, its first
/// char at source column `start`, from which tabs reach their stops.
fn leading_indent_at(input: &str, start: usize) -> (usize, usize) {
    let mut column = start;
    let mut bytes = 0usize;
    for byte in input.as_bytes() {
        match *byte {
            b' ' => column += 1,
            b'\t' => column += 4 - (column % 4),
            _ => break,
        }
        bytes += 1;
    }
    (column - start, bytes)
}

fn task_marker_checked(input: &str) -> Option<bool> {
    if input.starts_with("[ ]") {
        Some(false)
    } else if input.starts_with("[x]") || input.starts_with("[X]") {
        Some(true)
    } else {
        None
    }
}

/// Whether `text` holds only spaces and tabs, as a blank line does.
pub(crate) fn is_blank(text: &str) -> bool {
    text.bytes().all(|byte| matches!(byte, b' ' | b'\t'))
}

fn trim_ascii_start(input: &str) -> &str {
    input.trim_start_matches(|char| matches!(char, ' ' | '\t'))
}

fn leading_trim_bytes(input: &str) -> usize {
    input.len() - trim_ascii_start(input).len()
}

fn parse_table_delimiter(input: &str) -> Option<Vec<TableAlignment>> {
    // Every cell trims to colons around dashes, so a row with any other char
    // is no delimiter row, whatever its cells.
    if !input.contains('-')
        || !input
            .chars()
            .all(|char| matches!(char, '|' | '-' | ':' | ' ' | '\t'))
    {
        return None;
    }
    let cells = table_row_cell_ranges(input);
    if cells.is_empty() {
        return None;
    }
    let mut alignments = Vec::new();
    for (start, end) in cells {
        alignments.push(table_delimiter_alignment(
            input[start..end].trim_matches([' ', '\t']),
        )?);
    }
    Some(alignments)
}

// A delimiter cell is `:?` `-`+ `:?` once trimmed: colons only at the
// boundaries, the dashes contiguous, no interior space or colon.
fn table_delimiter_alignment(cell: &str) -> Option<TableAlignment> {
    let bytes = cell.as_bytes();
    let mut cursor = 0;
    let left = bytes.first() == Some(&b':');
    if left {
        cursor += 1;
    }
    let dash_start = cursor;
    while bytes.get(cursor) == Some(&b'-') {
        cursor += 1;
    }
    if cursor == dash_start {
        return None;
    }
    let right = bytes.get(cursor) == Some(&b':');
    if right {
        cursor += 1;
    }
    if cursor != bytes.len() {
        return None;
    }
    Some(match (left, right) {
        (true, true) => TableAlignment::Center,
        (true, false) => TableAlignment::Left,
        (false, true) => TableAlignment::Right,
        (false, false) => TableAlignment::None,
    })
}

/// The cell-delimiter pipes of a table row, in order: every `|` that is not
/// escaped by an odd backslash run. The cell's inline content reads an
/// escaped pipe as `|`.
fn table_row_delimiters(row: &str) -> Vec<usize> {
    let bytes = row.as_bytes();
    let mut delimiters = Vec::new();
    let mut cursor = 0;
    while cursor < bytes.len() {
        match bytes[cursor] {
            b'\\' => {
                let backslashes = delimiter_byte_run_len(row, cursor, b'\\');
                let pipe = cursor + backslashes;
                cursor = if bytes.get(pipe) == Some(&b'|') && backslashes % 2 == 1 {
                    pipe + 1
                } else {
                    pipe
                };
            }
            b'|' => {
                delimiters.push(cursor);
                cursor += 1;
            }
            _ => cursor += 1,
        }
    }
    delimiters
}

/// The byte ranges of `input`'s cells, between the pipes that delimit them.
fn table_row_cell_ranges(input: &str) -> Vec<(usize, usize)> {
    let trimmed = input.trim_matches([' ', '\t']);
    let offset = leading_trim_bytes(input);
    let delimiters = table_row_delimiters(trimmed);
    let mut cells = Vec::new();
    let mut start = 0;
    for &pipe in &delimiters {
        cells.push((offset + start, offset + pipe));
        start = pipe + 1;
    }
    cells.push((offset + start, offset + trimmed.len()));

    // A delimiter at the very start or end (only whitespace after it) is a
    // border, not the edge of an empty cell.
    if delimiters.first() == Some(&0) {
        cells.remove(0);
    }
    if delimiters
        .last()
        .is_some_and(|&pipe| is_blank(&trimmed[pipe + 1..]))
    {
        cells.pop();
    }
    cells
}

/// One table cell's inline input (whitespace trimmed, escaped pipes read as
/// `|`), its source map, and its span.
struct TableCellSource {
    text: DerivedText,
    span: Span,
}

/// The cells of `row`, a slice of `line.text`, as `table_row_cell_ranges`
/// splits it.
fn table_row_cells(line: &Line<'_>, row: &str) -> Vec<TableCellSource> {
    let row_offset = slice_offset_in(line.text, row).unwrap_or(0);
    table_row_cell_ranges(row)
        .into_iter()
        .map(|(start, end)| {
            let raw = &row[start..end];
            let leading = leading_trim_bytes(raw);
            let content = raw.trim_matches([' ', '\t']);
            let offset = row_offset + start + leading;
            let span = Span::new(
                line.source_start(offset),
                line.source_end(offset + content.len()),
            );
            let mut text = DerivedText::default();
            // GitHub/cmark-gfm reads an odd backslash run before `|` as a
            // literal pipe; the run keeps its other backslashes, which the
            // inline parser resolves as written. The `|` read from `\|` maps
            // to both of its bytes.
            let bytes = content.as_bytes();
            let mut copied = 0;
            let mut cursor = 0;
            while cursor < bytes.len() {
                if bytes[cursor] == b'\\' {
                    let pipe = cursor + delimiter_byte_run_len(content, cursor, b'\\');
                    if bytes.get(pipe) == Some(&b'|') && (pipe - cursor) % 2 == 1 {
                        text.append(line, &content[copied..pipe - 1]);
                        text.append_replacing(
                            "|",
                            line.source_start(offset + pipe - 1),
                            line.source_end(offset + pipe + 1),
                        );
                        copied = pipe + 1;
                    }
                    cursor = pipe;
                } else {
                    cursor += 1;
                }
            }
            text.append(line, &content[copied..]);
            TableCellSource { text, span }
        })
        .collect()
}

fn table_has_separator(header: &str, delimiter: &str) -> bool {
    // GFM makes leading/trailing pipes optional, so `parse_table_delimiter` plus
    // the header/alignment column-count check usually suffice. The one exception
    // is a single resolved column with no disambiguating syntax: `a\n-\nb` has
    // matching one-column shapes yet no pipe and no alignment colon, so it is a
    // paragraph, not a table. A single column still forms a table
    // when a pipe appears in the header/delimiter or the delimiter carries an
    // explicit alignment colon (`a\n-:`, `a\n:-:`, …).
    let Some(alignments) = parse_table_delimiter(delimiter) else {
        return true;
    };
    if alignments.len() == 1 {
        return contains_unescaped_pipe(header)
            || contains_unescaped_pipe(delimiter)
            || delimiter.contains(':');
    }
    true
}

// Still used by `block_quote_table_body_row` to detect a table row appearing as
// a block-quote continuation line (which DOES require a pipe).
fn contains_unescaped_pipe(input: &str) -> bool {
    !table_row_delimiters(input).is_empty()
}

// A GFM footnote definition `[^label]:` is a block boundary: it interrupts a
// paragraph and ends a prior footnote's lazy continuation.
/// The end of the `<…>` autolink opening at `index`.
fn autolink_end(lookups: &mut impl Lookups, input: &str, index: usize) -> Option<usize> {
    let end = lookups.find(">", index)? + 1;
    is_angle_autolink(&input[index + 1..end - 1]).then_some(end)
}

/// The end of the inline HTML (comment, processing instruction, CDATA,
/// declaration, or tag) opening at `index`.
fn html_inline_end(lookups: &mut impl Lookups, input: &str, index: usize) -> Option<usize> {
    let rest = &input[index..];
    if rest.starts_with("<!--") {
        return Some(lookups.find("-->", index)? + 3);
    }
    // The `?>` closing a processing instruction follows its `<?`.
    if rest.starts_with("<?") {
        return Some(lookups.find("?>", index + 2)? + 2);
    }
    if rest.starts_with("<![CDATA[") {
        return Some(lookups.find("]]>", index)? + 3);
    }
    if is_declaration_start(rest) {
        return Some(lookups.find(">", index)? + 1);
    }
    parse_html_tag_with(lookups, input, index).map(|(end, _)| end)
}

fn parse_html_tag(input: &str, index: usize) -> Option<(usize, &str)> {
    parse_html_tag_with(&mut DirectLookups { input }, input, index)
}

fn parse_html_tag_with<'a>(
    lookups: &mut impl Lookups,
    input: &'a str,
    index: usize,
) -> Option<(usize, &'a str)> {
    let bytes = input.as_bytes();
    if bytes.get(index) != Some(&b'<') {
        return None;
    }

    let closing = bytes.get(index + 1) == Some(&b'/');
    let name_start = index + if closing { 2 } else { 1 };
    let first = *bytes.get(name_start)?;
    if !first.is_ascii_alphabetic() {
        return None;
    }

    let mut cursor = name_start + 1;
    while bytes.get(cursor).is_some_and(|byte| html_name_byte(*byte)) {
        cursor += 1;
    }
    let name = &input[name_start..cursor];

    if closing {
        cursor = skip_spaces(input, cursor);
        if bytes.get(cursor) == Some(&b'>') {
            return Some((cursor + 1, name));
        }
        return None;
    }

    let mut needs_space = false;
    loop {
        let before_spaces = cursor;
        cursor = skip_spaces(input, cursor);
        let had_space = cursor > before_spaces;
        match bytes.get(cursor) {
            Some(b'>') => return Some((cursor + 1, name)),
            Some(b'/') if bytes.get(cursor + 1) == Some(&b'>') => return Some((cursor + 2, name)),
            Some(byte) if had_space && html_attribute_name_start(*byte) => {
                cursor += 1;
                while bytes
                    .get(cursor)
                    .is_some_and(|byte| html_attribute_name_byte(*byte))
                {
                    cursor += 1;
                }
                let after_name = cursor;
                let after_spaces = skip_spaces(input, cursor);
                if bytes.get(after_spaces) == Some(&b'=') {
                    cursor = skip_spaces(input, after_spaces + 1);
                    cursor = parse_html_attribute_value(lookups, input, cursor)?;
                } else {
                    cursor = after_name;
                }
                needs_space = true;
            }
            Some(_) if needs_space => return None,
            _ => return None,
        }
    }
}

fn parse_html_attribute_value(
    lookups: &mut impl Lookups,
    input: &str,
    index: usize,
) -> Option<usize> {
    let bytes = input.as_bytes();
    match bytes.get(index)? {
        b'"' => Some(lookups.find("\"", index + 1)? + 1),
        b'\'' => Some(lookups.find("'", index + 1)? + 1),
        b'=' | b'<' | b'>' | b'`' => None,
        _ => {
            let mut cursor = index;
            while bytes.get(cursor).is_some_and(|byte| {
                !byte.is_ascii_whitespace()
                    && !matches!(*byte, b'"' | b'\'' | b'=' | b'<' | b'>' | b'`')
            }) {
                cursor += 1;
            }
            if cursor == index {
                None
            } else {
                Some(cursor)
            }
        }
    }
}

fn html_name_byte(byte: u8) -> bool {
    byte.is_ascii_alphanumeric() || byte == b'-'
}

fn html_attribute_name_start(byte: u8) -> bool {
    byte.is_ascii_alphabetic() || byte == b'_' || byte == b':'
}

fn html_attribute_name_byte(byte: u8) -> bool {
    byte.is_ascii_alphanumeric() || matches!(byte, b'_' | b':' | b'.' | b'-')
}

fn skip_spaces(input: &str, mut index: usize) -> usize {
    while input
        .as_bytes()
        .get(index)
        .is_some_and(|byte| matches!(*byte, b' ' | b'\t' | b'\n' | b'\r'))
    {
        index += 1;
    }
    index
}

/// The destination of the angle-bracket autolink `<uri>`, when `uri` writes
/// one: the URI itself, or `mailto:` and an email address.
pub(crate) fn angle_autolink_destination(uri: &str) -> Option<String> {
    if is_uri_autolink(uri) {
        Some(String::from(uri))
    } else if is_email_autolink(uri) {
        Some(alloc::format!("mailto:{uri}"))
    } else {
        None
    }
}

/// Whether `<uri>` is an angle-bracket autolink.
fn is_angle_autolink(uri: &str) -> bool {
    is_uri_autolink(uri) || is_email_autolink(uri)
}

fn is_uri_autolink(input: &str) -> bool {
    // A scheme is at most 32 bytes, so the `:` ending it is within the first 33.
    let Some(colon) = input
        .as_bytes()
        .iter()
        .take(33)
        .position(|byte| *byte == b':')
    else {
        return false;
    };
    let scheme = &input[..colon];
    if scheme.len() < 2 || scheme.len() > 32 {
        return false;
    }
    let mut bytes = scheme.bytes();
    if !bytes.next().is_some_and(|byte| byte.is_ascii_alphabetic()) {
        return false;
    }
    if !bytes.all(|byte| byte.is_ascii_alphanumeric() || matches!(byte, b'+' | b'.' | b'-')) {
        return false;
    }
    input[colon + 1..]
        .chars()
        .map(source_char)
        .all(|char| !matches!(char, '<' | '>' | ' ') && !char.is_ascii_control())
}

fn is_email_autolink(input: &str) -> bool {
    // No email address contains `<`, and stopping at one keeps a run of `<`
    // openers that share one later `>` linear.
    if input
        .chars()
        .any(|char| char.is_whitespace() || char == '<')
    {
        return false;
    }
    let Some(at) = input.find('@') else {
        return false;
    };
    if at == 0 || at + 1 >= input.len() {
        return false;
    }
    // Angle-bracket `<email>` autolinks use the strict CommonMark domain
    // grammar but, unlike the GFM bare form, allow a single (dotless) label.
    is_email_local_part(&input[..at]) && is_email_domain(&input[at + 1..], 1)
}

/// The destination of a literal autolink written as `text`, when `text` is
/// exactly one literal autolink the inline parser can read: the text after the
/// prefix `parse_literal_autolink` gives it.
///
/// Whether a literal autolink forms depends in part on what follows it:
/// cmark-gfm's domain check counts the `.` and `_` in the punctuation trimmed
/// off its end, and `www.` at a line start links `www`. So `text` is read at a
/// line start and followed by what lets the most through, `..` and a space:
/// every literal autolink the parser reads has a destination, and a text the
/// parser would trim never does.
pub(crate) fn literal_autolink_destination(text: &str) -> Option<String> {
    let mut input = String::from(text);
    input.push_str(".. ");
    let (end, prefix) =
        parse_literal_autolink(&input, 0, &mut LiteralAutolinkScan::default(), true)?;
    (end == text.len()).then(|| {
        let mut destination = String::from(prefix);
        destination.push_str(text);
        destination
    })
}

/// A literal autolink starting at `index`, by cmark-gfm's dispatch: it tries,
/// in order, `http(s)://` URLs, `www.` URLs, extended-protocol
/// (`mailto:`/`xmpp:`) emails, and bare emails. Each branch enforces
/// cmark-gfm's per-scheme preceding-character guard and its domain/host
/// rules; the trailing trim is shared (`autolink_delim`). Returns the end and
/// the prefix the destination puts before `input[index..end]`, the visible
/// original: `http://` for a `www.` URL, `mailto:` for a bare email, and
/// nothing otherwise.
///
/// `urls` is false inside an open `[`: as in cmark-gfm, a `http://`,
/// `https://`, or `www.` URL after a `[` no `]` has closed yet stays text, and
/// only an email address links.
fn parse_literal_autolink(
    input: &str,
    index: usize,
    scan: &mut LiteralAutolinkScan,
    urls: bool,
) -> Option<(usize, &'static str)> {
    let rest = &input[index..];
    let www = rest
        .as_bytes()
        .get(..4)
        .is_some_and(|prefix| prefix.eq_ignore_ascii_case(b"www."));
    if !urls {
        // A literal starting `www.` is a URL, linked or not, as outside an
        // open `[`: no email starts there.
        if www {
            return None;
        }
        return parse_literal_email(input, index, scan);
    }

    // `http://` / `https://` URLs. cmark requires the char before the scheme
    // to be non-alphanumeric (so `mmmhttp://…` does not link from `mmmh`).
    if let Some(scheme_len) = rest
        .starts_with("http://")
        .then_some(7)
        .or_else(|| rest.starts_with("https://").then_some(8))
    {
        if !literal_scheme_prefix_ok(input, index) {
            return None;
        }
        // A non-empty domain is additionally required, so `http://`,
        // `http://#`, `http://$`, and a bracketed IPv6 host are not links.
        if !http_literal_host_ok(&input[index + scheme_len..]) {
            return None;
        }
        // The URL extent is scanned from the very start (after `://`) and the
        // trailing trim runs over the whole URL.
        let end = autolink_url_end(input, index + scheme_len);
        if end <= index + scheme_len {
            return None;
        }
        return Some((end, ""));
    }

    // `www.` URLs (synthesize a `http://` href). cmark allows the preceding
    // char to be one of `*_~(` or whitespace (or start of input).
    if www {
        if !literal_www_prefix_ok(input, index) {
            return None;
        }
        if !check_domain(rest, false) {
            return None;
        }
        let end = autolink_url_end(input, index);
        if end <= index || (end <= index + 3 && !literal_starts_line(input, index)) {
            return None;
        }
        return Some((end, "http://"));
    }

    parse_literal_email(input, index, scan)
}

// The char immediately before a `http(s)://` literal must be non-alphabetic.
// An escaped `<` (`\<http://…`) is just literal text before the URL, so the
// literal still forms (the `<` is not treated as an angle-autolink opener).
fn literal_scheme_prefix_ok(input: &str, index: usize) -> bool {
    if index == 0 {
        return true;
    }
    let Some(previous) = input[..index].chars().next_back() else {
        return true;
    };
    !previous.is_ascii_alphabetic()
}

// The char before a `www.` literal must be one of cmark-gfm's accepted ASCII
// delimiters or ordinary Markdown layout whitespace. As on GitHub, other
// Unicode whitespace is not a start delimiter for this branch.
fn literal_www_prefix_ok(input: &str, index: usize) -> bool {
    if index == 0 {
        return true;
    }
    let Some(previous) = input[..index].chars().next_back() else {
        return true;
    };
    if matches!(previous, '*' | '_' | '~' | '(' | '[' | ']') {
        return true;
    }
    matches!(previous, ' ' | '\t' | '\n' | '\r')
}

fn literal_starts_line(input: &str, index: usize) -> bool {
    index == 0
        || input
            .as_bytes()
            .get(index - 1)
            .is_some_and(|byte| matches!(byte, b'\n' | b'\r'))
}

fn http_literal_host_ok(host: &str) -> bool {
    match host.chars().next() {
        Some(char) if char.is_ascii() && char.is_ascii_alphanumeric() => check_domain(host, true),
        Some(char) if !char.is_ascii() && is_valid_hostchar(source_char(char)) => {
            check_domain(host, true)
        }
        _ => false,
    }
}

// Port of cmark-gfm `is_valid_hostchar`: a host char is valid when it is not a
// Unicode space and not a Unicode punctuation character.
fn is_valid_hostchar(char: char) -> bool {
    !char.is_whitespace() && !crate::unicode_punctuation::is_unicode_punctuation(char)
}

// Port of cmark-gfm `check_domain`: whether `data` starts with a valid host.
// Rejects a `_` in either of the last two `.`-separated host segments (unless
// the host has >10 segments — a DoS guard). When `allow_short` is false a dot
// is required (the `www.` rule). The URL extent past the host is determined by
// `autolink_url_end`, so only the verdict matters here.
//
// cmark walks bytes with `is_valid_hostchar` decoding each char; this walks
// chars directly (UTF-8 safe) over the host prefix, which yields the same
// dot/underscore-segment verdict. A `\` escapes the following char, so a host
// can run on over escaped spaces through later `www.` candidates; the walk
// stops at the eleventh dot, which settles the verdict, so that the walks
// from all the candidates of a pass stay linear in total.
fn check_domain(data: &str, allow_short: bool) -> bool {
    let mut np = 0usize;
    let mut uscore1 = 0usize;
    let mut uscore2 = 0usize;

    let mut chars = data.char_indices().peekable();
    while let Some((offset, char)) = chars.next() {
        // cmark's accounting loop runs `for (i = 1; i < size - 1; i++)`: it
        // never inspects the first char (offset 0) nor the final char of the
        // chunk. We replicate that — a trailing `_` (e.g. `http://a_`) is not
        // counted, so the link still forms.
        let account = offset != 0 && chars.peek().is_some();
        match char {
            '\\' => {
                // Escape: consume the next char as a literal host char.
                chars.next();
            }
            '_' if account => uscore2 += 1,
            '.' if account => {
                uscore1 = uscore2;
                uscore2 = 0;
                np += 1;
                if np > 10 {
                    return true;
                }
            }
            '_' | '.' | '-' => {}
            _ => {
                if !is_valid_hostchar(source_char(char)) {
                    break;
                }
            }
        }
    }

    if (uscore1 > 0 || uscore2 > 0) && np <= 10 {
        return false;
    }

    allow_short || np > 0
}

// Forward scan from `start` for the URL extent: Unicode whitespace, `<`, a
// non-ASCII char in CommonMark's Unicode punctuation set (full-width `，` or
// `。`) other than the replacement char, `[[`, or `]` ends the URL. CommonMark allows
// `>` and `[` inside (the renderer percent-encodes them); a `]` is
// additionally treated as a hard URL boundary (autolink-3), so a `]` ends the
// scan and is never part of the link. The trailing trim may reach `start`.
fn autolink_url_end(input: &str, start: usize) -> usize {
    let bytes = input.as_bytes();
    let mut end = start;
    // The extent stops at the first `]` outside backticks unless a `[` came
    // before it in the URL (no balancing).
    let mut strict_has_open_bracket = false;
    let mut strict_inside_backticks = false;
    for (offset, char) in input[start..].char_indices() {
        if char.is_whitespace()
            || char == '<'
            || is_autolink_terminating_control(char)
            || (!char.is_ascii()
                && char != '\u{FFFD}'
                && crate::unicode_punctuation::is_unicode_punctuation(char))
            || input[start + offset..].starts_with("[[")
        {
            break;
        }
        match char {
            '[' => strict_has_open_bracket = true,
            '`' => strict_inside_backticks = !strict_inside_backticks,
            ']' if !strict_has_open_bracket && !strict_inside_backticks => break,
            _ => {}
        }
        // A `\` before ASCII punctuation other than `.` ends the URL. The
        // serializer writes text after a literal autolink with backslash
        // escapes (`\*`, `\_`, `\[`, …); stopping here keeps such a tree
        // writable. cmark-gfm keeps the `\*x` in `www.a.com\*x` inside the
        // URL; this crate deliberately diverges. A `\` before `.` or a
        // non-punctuation char stays part of the URL (`www.x.com/a\.`).
        if char == '\\' {
            if let Some(&next) = bytes.get(start + offset + 1) {
                if next.is_ascii_punctuation() && next != b'.' {
                    break;
                }
            }
        }
        end = start + offset + char.len_utf8();
    }
    autolink_delim(input, start, end)
}

fn is_autolink_terminating_control(char: char) -> bool {
    matches!(char, '\u{2066}'..='\u{2069}')
}

// Port of cmark-gfm `autolink_delim`: trim trailing delimiters from the end of
// the URL. A trailing `) ? ! . , : * _ ~ ' "` is trimmed; `)` only when there
// are more `)` than `(` in the link; a trailing `&` and alphanumerics ending
// in `;` is excluded whole; any other trailing `;` is trimmed alone.
fn autolink_delim(input: &str, start: usize, mut end: usize) -> usize {
    let bytes = input.as_bytes();
    let mut opening = 0usize;
    let mut closing = 0usize;
    for &byte in &bytes[start..end] {
        match byte {
            b'(' => opening += 1,
            b')' => closing += 1,
            _ => {}
        }
    }

    while end > start {
        match bytes[end - 1] {
            b')' => {
                if closing <= opening {
                    break;
                }
                closing -= 1;
                end -= 1;
            }
            b'?' | b'!' | b'.' | b',' | b':' | b'*' | b'_' | b'~' | b'\'' | b'"' => {
                end -= 1;
            }
            b';' => {
                // Walk back over alphanumerics; if they reach a `&`, exclude
                // the whole `&…;` entity run, otherwise trim just the `;`.
                let mut new_end = end - 1;
                while new_end > start && bytes[new_end - 1].is_ascii_alphanumeric() {
                    new_end -= 1;
                }
                if new_end > start && new_end < end - 1 && bytes[new_end - 1] == b'&' {
                    end = new_end - 1;
                } else {
                    end -= 1;
                }
            }
            _ => break,
        }
    }
    end
}

/// Scan state shared by the `parse_literal_autolink` calls of one inline pass.
/// The pass only moves forward, so each piece lets a later start position reuse
/// the bytes already walked for an earlier one instead of rescanning them.
#[derive(Default)]
struct LiteralAutolinkScan {
    /// Runs of email local-part bytes (plus `:` for `mailto:`/`xmpp:`).
    email_local: ByteRun,
    /// What every start before one `@` shares: its last `:` and its domain.
    email_at: EmailAt,
    /// The text before a start, for the `+` boundary check.
    email_prefix: EmailPrefix,
}

/// The facts of one `@` that every email start before it reads: the last `:`
/// in its local-part run at or after `from`, and the domain end for the plain
/// and the `xmpp:` form. A query starting before `from` rescans the run.
#[derive(Default)]
struct EmailAt {
    at: Option<usize>,
    from: usize,
    last_colon: Option<usize>,
    domain_end: [Option<Option<usize>>; 2],
}

impl EmailAt {
    fn update(&mut self, input: &str, index: usize, at: usize) {
        if self.at != Some(at) {
            *self = Self {
                at: Some(at),
                from: usize::MAX,
                ..Self::default()
            };
        }
        if index < self.from {
            self.last_colon = input[index..at].rfind(':').map(|offset| index + offset);
            self.from = index;
        }
    }

    /// The end of the domain after the `@`, trimmed and validated, or `None`.
    fn domain_end(&mut self, input: &str, is_xmpp: bool) -> Option<usize> {
        let at = self.at.expect("updated before use");
        *self.domain_end[usize::from(is_xmpp)].get_or_insert_with(|| {
            let start = at + 1;
            let end = literal_email_domain_end(input, start, is_xmpp)?;
            let trimmed = autolink_delim(input, start, end);
            (trimmed > start && is_gfm_email_domain(&input[start..trimmed], is_xmpp))
                .then_some(trimmed)
        })
    }
}

/// Whether the text before a position ends in a bare email, kept as a pass
/// walks forward: the start of the text after the last whitespace, the first
/// byte there that no local part holds, the last `@`, and after it the first
/// byte no domain holds, the first `.`, and the first `.` opening an empty
/// label. A query before the walked position walks again from the start.
#[derive(Default)]
struct EmailPrefix {
    cursor: usize,
    segment: usize,
    non_local: Option<usize>,
    at: Option<usize>,
    domain_bad: Option<usize>,
    domain_dot: Option<usize>,
    domain_empty_label: Option<usize>,
}

impl EmailPrefix {
    fn advance(&mut self, input: &str, end: usize) {
        if end < self.cursor {
            *self = Self::default();
        }
        let bytes = input.as_bytes();
        let from = self.cursor;
        for (offset, char) in input[from..end].char_indices() {
            let position = from + offset;
            if char.is_whitespace() {
                *self = Self {
                    segment: position + char.len_utf8(),
                    ..Self::default()
                };
                continue;
            }
            let byte = char.is_ascii().then_some(char as u8);
            if self.non_local.is_none() && !byte.is_some_and(is_gfm_email_local_byte) {
                self.non_local = Some(position);
            }
            if char == '@' {
                self.at = Some(position);
                self.domain_bad = None;
                self.domain_dot = None;
                self.domain_empty_label = None;
                continue;
            }
            let Some(at) = self.at else {
                continue;
            };
            match byte {
                Some(b'.') => {
                    self.domain_dot.get_or_insert(position);
                    if position == at + 1 || bytes[position - 1] == b'.' {
                        self.domain_empty_label.get_or_insert(position);
                    }
                }
                Some(byte) if byte.is_ascii_alphanumeric() || matches!(byte, b'-' | b'_') => {}
                _ => {
                    self.domain_bad.get_or_insert(position);
                }
            }
        }
        self.cursor = end;
    }

    /// Whether the text from the last whitespace before `end` to `end` ends
    /// in a bare email: `prefix_ends_with_gfm_email`, walked once per pass.
    fn ends_with_email(&mut self, input: &str, end: usize) -> bool {
        self.advance(input, end);
        let Some(at) = self.at else {
            return false;
        };
        let before = |position: Option<usize>| position.is_some_and(|position| position < end);
        at > self.segment
            && !self.non_local.is_some_and(|position| position < at)
            && end > at + 1
            && !before(self.domain_bad)
            && before(self.domain_dot)
            && !before(self.domain_empty_label)
            && !matches!(input.as_bytes()[end - 1], b'.' | b'-' | b'_')
    }
}

/// The extent of one run of bytes accepted by a fixed predicate: every start
/// position in `start..=end` stops at `end`. Each `ByteRun` is always queried
/// with the same predicate.
#[derive(Default)]
struct ByteRun {
    start: usize,
    end: Option<usize>,
}

impl ByteRun {
    /// Returns the first byte position at or after `index` that `in_run`
    /// rejects, or the input length.
    fn end(&mut self, input: &str, index: usize, in_run: fn(u8) -> bool) -> usize {
        if let Some(end) = self.end {
            if self.start <= index && index <= end {
                return end;
            }
        }
        let end = input.as_bytes()[index..]
            .iter()
            .position(|byte| !in_run(*byte))
            .map_or(input.len(), |offset| index + offset);
        self.start = index;
        self.end = Some(end);
        end
    }
}

fn is_email_local_or_scheme_byte(byte: u8) -> bool {
    is_gfm_email_local_byte(byte) || byte == b':'
}

/// A GFM bare-email literal (and the extended `mailto:`/`xmpp:` protocol
/// forms) starting at `index`, which must be the link start: cmark anchors
/// the email at the left edge found by rewinding from `@` over
/// `[A-Za-z0-9._+-]` (or a `mailto:`/`xmpp:` scheme), so this only succeeds
/// when the char before `index` is not part of that left extent.
fn parse_literal_email(
    input: &str,
    index: usize,
    scan: &mut LiteralAutolinkScan,
) -> Option<(usize, &'static str)> {
    // A valid local part holds only local-part bytes behind an optional
    // `mailto:`/`xmpp:` scheme, so the `@` must be the byte that ends that run.
    let at_index = scan
        .email_local
        .end(input, index, is_email_local_or_scheme_byte);
    if input.as_bytes().get(at_index) != Some(&b'@') || at_index == index {
        return None;
    }

    // Determine whether this `@` is preceded by an extended protocol scheme
    // (`mailto:` / `xmpp:`), which both relaxes the href synthesis and (xmpp)
    // allows `/` in the domain.
    let (auto_mailto, is_xmpp) = classify_email_local(&input[index..at_index]);

    // Left-boundary guard (autolink-1): the char before `index` must not be a
    // local-part continuation char, otherwise the true link starts earlier and
    // this position is interior. After a recognized scheme, the scheme's own
    // preceding-char rule is what matters.
    if !email_left_boundary_ok(input, index, auto_mailto, |end| {
        scan.email_prefix.ends_with_email(input, end)
    }) {
        return None;
    }

    // The run holds only local-part bytes and `:`, so the local part after
    // its scheme is valid when it is not empty and holds no `:`. The facts of
    // the `@` are shared by every start before it, so a run of starts reads
    // them once.
    let body_start = if auto_mailto {
        index
    } else if is_xmpp {
        index + "xmpp:".len()
    } else {
        index + "mailto:".len()
    };
    scan.email_at.update(input, index, at_index);
    if body_start >= at_index
        || scan
            .email_at
            .last_colon
            .is_some_and(|colon| colon >= body_start)
    {
        return None;
    }
    let end = scan.email_at.domain_end(input, is_xmpp)?;
    Some((end, if auto_mailto { "mailto:" } else { "" }))
}

// Classify the local part for the extended-protocol forms. Returns
// `(auto_mailto, is_xmpp)`: `mailto:user` → (false, false); `xmpp:user` →
// (false, true); a bare local part → (true, false). The scheme match is
// case-insensitive.
fn classify_email_local(local: &str) -> (bool, bool) {
    if let Some(rest) = strip_ci_prefix(local, "mailto:") {
        if !rest.is_empty() {
            return (false, false);
        }
    }
    if let Some(rest) = strip_ci_prefix(local, "xmpp:") {
        if !rest.is_empty() {
            return (false, true);
        }
    }
    (true, false)
}

fn strip_ci_prefix<'a>(input: &'a str, prefix: &str) -> Option<&'a str> {
    let bytes = input.as_bytes();
    let plen = prefix.len();
    if bytes.len() >= plen && bytes[..plen].eq_ignore_ascii_case(prefix.as_bytes()) {
        Some(&input[plen..])
    } else {
        None
    }
}

// The left-boundary check for an email literal. The link is anchored at its
// true left edge: the preceding char must not be an ASCII alphanumeric (which
// would extend the local part leftward). For the bare form, a preceding `/` is
// also rejected (`/a@b.c` is not linked), while the extended
// `mailto:`/`xmpp:` form permits `/` before the scheme (so
// `…/mailto:beedrill@…` links).
fn email_left_boundary_ok(
    input: &str,
    index: usize,
    auto_mailto: bool,
    prefix_ends_with_email: impl FnOnce(usize) -> bool,
) -> bool {
    if index == 0 {
        return true;
    }
    let Some(previous) = input[..index].chars().next_back() else {
        return true;
    };
    if previous.is_ascii_alphanumeric() {
        if auto_mailto && input[index..].starts_with('+') && prefix_ends_with_email(index) {
            return true;
        }
        return false;
    }
    if auto_mailto && previous == '/' {
        return false;
    }
    true
}

#[cfg(test)]
fn prefix_ends_with_gfm_email(input: &str, end: usize) -> bool {
    let start = input[..end]
        .char_indices()
        .rev()
        .find(|(_, char)| char.is_whitespace())
        .map_or(0, |(offset, char)| offset + char.len_utf8());
    let candidate = &input[start..end];
    let Some(at) = candidate.rfind('@') else {
        return false;
    };
    email_local_is_valid(&candidate[..at], true) && is_gfm_email_domain(&candidate[at + 1..], false)
}

// Validate the email local part. For the bare form, every char must be a GFM
// email atext byte (`[A-Za-z0-9.+_-]` plus the dot-separated structure). For
// the extended-protocol forms, the part after the scheme is validated.
#[cfg(test)]
fn email_local_is_valid(local: &str, auto_mailto: bool) -> bool {
    let body = if auto_mailto {
        local
    } else if let Some(rest) = strip_ci_prefix(local, "mailto:") {
        rest
    } else if let Some(rest) = strip_ci_prefix(local, "xmpp:") {
        rest
    } else {
        local
    };
    !body.is_empty() && body.bytes().all(is_gfm_email_local_byte)
}

// GFM email local-part charset (autolink-1): a narrower set than RFC atext,
// matching cmark's rewind class `[A-Za-z0-9.+_-]`.
fn is_gfm_email_local_byte(byte: u8) -> bool {
    byte.is_ascii_alphanumeric() || matches!(byte, b'.' | b'+' | b'_' | b'-')
}

fn is_email_local_part(input: &str) -> bool {
    !input.is_empty()
        && input
            .split('.')
            .all(|segment| !segment.is_empty() && segment.bytes().all(is_email_atext))
}

fn is_email_atext(byte: u8) -> bool {
    byte.is_ascii_alphanumeric()
        || matches!(
            byte,
            b'!' | b'#'
                | b'$'
                | b'%'
                | b'&'
                | b'\''
                | b'*'
                | b'+'
                | b'/'
                | b'='
                | b'?'
                | b'^'
                | b'_'
                | b'`'
                | b'{'
                | b'|'
                | b'}'
                | b'~'
                | b'-'
        )
}

// Port of cmark-gfm's email-domain scan (`postprocess_text`). Scans forward
// from `index` over the email domain, accepting alphanumerics, `-`, `_`, and
// `.`; for the `xmpp:` form a `/` is also accepted (path). A dot only counts
// toward the "at least one dot" requirement when it is followed by an
// alphanumeric. The scanned span must be >= 1 byte, contain at least one such
// dot, and end in an alphabetic char or a dot. Returns the domain end offset
// (before trailing trim), or `None` when invalid.
fn literal_email_domain_end(input: &str, index: usize, is_xmpp: bool) -> Option<usize> {
    let bytes = input.as_bytes();
    let mut end = index;
    let mut np = 0usize;
    while end < bytes.len() {
        let byte = bytes[end];
        if byte.is_ascii_alphanumeric() {
            end += 1;
        } else if byte == b'.' && end + 1 < bytes.len() && bytes[end + 1].is_ascii_alphanumeric() {
            np += 1;
            end += 1;
        } else if byte == b'-' || byte == b'_' || (byte == b'/' && is_xmpp) {
            // `-`/`_` always continue the domain; `/` continues only the xmpp
            // path form.
            end += 1;
        } else {
            break;
        }
    }
    if end <= index {
        return None;
    }
    let len = end - index;
    let last = bytes[end - 1];
    if len < 1 || np == 0 || !(last.is_ascii_alphabetic() || last == b'.') {
        return None;
    }
    Some(end)
}

// Final structural validation of the trimmed email domain. The cmark scan
// already enforced the dot/last-char rules; this re-checks them after the
// shared trailing trim removed any delimiters, and rejects a domain ending in
// `-`/`_` (autolink-7: a hyphen in the final label disqualifies the link).
fn is_gfm_email_domain(input: &str, is_xmpp: bool) -> bool {
    if input.is_empty() {
        return false;
    }
    // A `/` path is only legal in the `xmpp:` form; split it off for the host
    // structural checks.
    let host = if is_xmpp {
        input.split('/').next().unwrap_or(input)
    } else {
        input
    };
    if !host.contains('.') {
        return false;
    }
    let last = host.as_bytes()[host.len() - 1];
    // The final label must not end in `-` or `_`, and the trailing label may
    // not be all ASCII digits.
    if matches!(last, b'-' | b'_') {
        return false;
    }
    host.split('.').all(|label| {
        !label.is_empty()
            && label
                .bytes()
                .all(|byte| byte.is_ascii_alphanumeric() || matches!(byte, b'-' | b'_'))
    })
}

fn is_email_domain(input: &str, min_labels: usize) -> bool {
    let mut label_count = 0usize;
    for label in input.split('.') {
        label_count += 1;
        let bytes = label.as_bytes();
        if bytes.is_empty()
            || bytes.len() > 63
            || !bytes
                .first()
                .is_some_and(|byte| byte.is_ascii_alphanumeric())
            || !bytes
                .last()
                .is_some_and(|byte| byte.is_ascii_alphanumeric())
            || !bytes
                .iter()
                .all(|byte| byte.is_ascii_alphanumeric() || *byte == b'-')
        {
            return false;
        }
    }
    label_count >= min_labels
}

/// A footnote label: no space, tab, or line ending and, as in a link label,
/// no unescaped bracket.
pub(crate) fn is_footnote_label(label: &str) -> bool {
    !label.is_empty()
        && reference_label_is_within_limit(label)
        && !label.contains([' ', '\t', '\n', '\r'])
        && !label
            .match_indices(['[', ']'])
            .any(|(index, _)| !is_escaped_at(label, index))
}

fn find_footnote_definition_label_end(input: &str) -> Option<usize> {
    let close = find_footnote_reference_label_end(input, 2)?;
    if input.as_bytes().get(close + 1) == Some(&b':') {
        Some(close)
    } else {
        None
    }
}

fn find_footnote_reference_label_end(input: &str, mut cursor: usize) -> Option<usize> {
    while cursor < input.len() {
        let (next, char) = next_char(input, cursor)?;
        if char == ']' && !is_escaped_at(input, cursor) {
            return Some(cursor);
        }
        cursor = next;
    }
    None
}