compiler/rustc_errors/src/markdown/parse.rs

use std::{iter, mem, str};

use crate::markdown::{MdStream, MdTree};

/// Short aliases that we can use in match patterns. If an end pattern is not
/// included, this type may be variable
const ANC_E: &[u8] = b">";
const ANC_S: &[u8] = b"<";
const BRK: &[u8] = b"---";
const CBK: &[u8] = b"```";
const CIL: &[u8] = b"`";
const CMT_E: &[u8] = b"-->";
const CMT_S: &[u8] = b"<!--";
const EMP_U: &[u8] = b"_";
const EMP_A: &[u8] = b"*";
const HDG: &[u8] = b"#";
const LNK_CHARS: &str = "$-_.+!*'()/&?=:%";
const LNK_E: &[u8] = b"]";
const LNK_S: &[u8] = b"[";
const STG_U: &[u8] = b"__";
const STG_A: &[u8] = b"**";
const STK: &[u8] = b"~~";

/// Pattern replacements
const REPLACEMENTS: &[(&str, &str)] = &[
    ("(c)", "©"),
    ("(C)", "©"),
    ("(r)", "®"),
    ("(R)", "®"),
    ("(tm)", "™"),
    ("(TM)", "™"),
    (":crab:", "🦀"),
    ("\n", " "),
];

/// `(extracted, remaining)`
type Parsed<'a> = (MdTree<'a>, &'a [u8]);
/// Output of a parse function
type ParseResult<'a> = Option<Parsed<'a>>;

/// Parsing context
#[derive(Clone, Copy, Debug, PartialEq)]
// The default values are the most common setting for non top-level parsing: not top block, not at
// line start (yes leading whitespace, not escaped).
struct Context {
    /// If true, we are at a the topmost level (not recursing a nested tt)
    top_block: bool = false,
    /// Previous character
    prev: Prev = Prev::Whitespace,
}

/// Character class preceding this one
#[derive(Clone, Copy, Debug, PartialEq)]
enum Prev {
    Newline,
    /// Whitespace that is not a newline
    Whitespace,
    Escape,
    Any,
}

/// Flags to simple parser function
#[derive(Clone, Copy, Debug, PartialEq)]
enum ParseOpt {
    /// Ignore escapes before closing pattern, trim content
    TrimNoEsc,
    None,
}

/// Parse a buffer
pub(crate) fn entrypoint(txt: &str) -> MdStream<'_> {
    let ctx = Context { top_block: true, prev: Prev::Newline };
    normalize(parse_recursive(txt.trim().as_bytes(), ctx), &mut Vec::new())
}

/// Parse a buffer with specified context
fn parse_recursive<'a>(buf: &'a [u8], ctx: Context) -> MdStream<'a> {
    use ParseOpt as Po;
    use Prev::{Escape, Newline, Whitespace};

    let mut stream: Vec<MdTree<'a>> = Vec::new();
    let Context { top_block: top_blk, mut prev } = ctx;

    // wip_buf is our entire unprocessed (unpushed) buffer, loop_buf is our to
    // check buffer that shrinks with each loop
    let mut wip_buf = buf;
    let mut loop_buf = wip_buf;

    while !loop_buf.is_empty() {
        let next_prev = match loop_buf[0] {
            b'\n' => Newline,
            b'\\' => Escape,
            x if x.is_ascii_whitespace() => Whitespace,
            _ => Prev::Any,
        };

        let res: ParseResult<'_> = match (top_blk, prev) {
            _ if loop_buf.starts_with(CMT_S) => {
                parse_simple_pat(loop_buf, CMT_S, CMT_E, Po::TrimNoEsc, MdTree::Comment)
            }
            (true, Newline) if loop_buf.starts_with(CBK) => Some(parse_codeblock(loop_buf)),
            _ if loop_buf.starts_with(CIL) => parse_codeinline(loop_buf),
            (true, Newline | Whitespace) if loop_buf.starts_with(HDG) => parse_heading(loop_buf),
            (true, Newline) if loop_buf.starts_with(BRK) => {
                Some((MdTree::HorizontalRule, parse_to_newline(loop_buf).1))
            }
            (_, Newline) if unordered_list_start(loop_buf) => Some(parse_unordered_li(loop_buf)),
            (_, Newline | Whitespace) if loop_buf.starts_with(STG_U) => {
                parse_simple_pat(loop_buf, STG_U, STG_U, Po::None, MdTree::Strong)
            }
            _ if loop_buf.starts_with(STG_A) => {
                parse_simple_pat(loop_buf, STG_A, STG_A, Po::None, MdTree::Strong)
            }
            (_, Newline | Whitespace) if loop_buf.starts_with(EMP_U) => {
                parse_simple_pat(loop_buf, EMP_U, EMP_U, Po::None, MdTree::Emphasis)
            }
            _ if loop_buf.starts_with(EMP_A) => {
                parse_simple_pat(loop_buf, EMP_A, EMP_A, Po::None, MdTree::Emphasis)
            }
            _ if loop_buf.starts_with(STK) => {
                parse_simple_pat(loop_buf, STK, STK, Po::None, MdTree::Strikethrough)
            }
            (_, Newline | Whitespace) if loop_buf.starts_with(ANC_S) => {
                let tt_fn = |link| MdTree::Link { disp: link, link };
                let ret = parse_simple_pat(loop_buf, ANC_S, ANC_E, Po::None, tt_fn);
                match ret {
                    Some((MdTree::Link { disp, .. }, _))
                        if disp.chars().all(|ch| LNK_CHARS.contains(ch)) =>
                    {
                        ret
                    }
                    _ => None,
                }
            }
            (_, Newline) if ord_list_start(loop_buf).is_some() => Some(parse_ordered_li(loop_buf)),
            _ if loop_buf.starts_with(LNK_S) => {
                parse_any_link(loop_buf, top_blk && prev == Prev::Newline)
            }
            (_, Escape | _) => None,
        };

        if let Some((tree, rest)) = res {
            // We found something: push our WIP and then push the found tree
            let prev_buf = &wip_buf[..(wip_buf.len() - loop_buf.len())];
            if !prev_buf.is_empty() {
                let prev_str = str::from_utf8(prev_buf).unwrap();
                stream.push(MdTree::PlainText(prev_str));
            }
            stream.push(tree);

            wip_buf = rest;
            loop_buf = rest;
        } else {
            // Just move on to the next character
            loop_buf = &loop_buf[1..];
            // If we are at the end and haven't found anything, just push plain text
            if loop_buf.is_empty() && !wip_buf.is_empty() {
                let final_str = str::from_utf8(wip_buf).unwrap();
                stream.push(MdTree::PlainText(final_str));
            }
        };

        prev = next_prev;
    }

    MdStream(stream)
}

/// The simplest kind of patterns: data within start and end patterns
fn parse_simple_pat<'a, F>(
    buf: &'a [u8],
    start_pat: &[u8],
    end_pat: &[u8],
    opts: ParseOpt,
    create_tt: F,
) -> ParseResult<'a>
where
    F: FnOnce(&'a str) -> MdTree<'a>,
{
    let ignore_esc = matches!(opts, ParseOpt::TrimNoEsc);
    let trim = matches!(opts, ParseOpt::TrimNoEsc);
    let (txt, rest) = parse_with_end_pat(&buf[start_pat.len()..], end_pat, ignore_esc)?;
    let mut txt = str::from_utf8(txt).unwrap();
    if trim {
        txt = txt.trim();
    }
    Some((create_tt(txt), rest))
}

/// Parse backtick-wrapped inline code. Accounts for >1 backtick sets
fn parse_codeinline(buf: &[u8]) -> ParseResult<'_> {
    let seps = buf.iter().take_while(|ch| **ch == b'`').count();
    let (txt, rest) = parse_with_end_pat(&buf[seps..], &buf[..seps], true)?;
    Some((MdTree::CodeInline(str::from_utf8(txt).unwrap()), rest))
}

/// Parse a codeblock. Accounts for >3 backticks and language specification
fn parse_codeblock(buf: &[u8]) -> Parsed<'_> {
    // account for ````code```` style
    let seps = buf.iter().take_while(|ch| **ch == b'`').count();
    let end_sep = &buf[..seps];
    let mut working = &buf[seps..];

    // Handle "````rust" style language specifications
    let next_ws_idx = working.iter().take_while(|ch| !ch.is_ascii_whitespace()).count();

    let lang = if next_ws_idx > 0 {
        // Munch the lang
        let tmp = str::from_utf8(&working[..next_ws_idx]).unwrap();
        working = &working[next_ws_idx..];
        Some(tmp)
    } else {
        None
    };

    let mut end_pat = vec![b'\n'];
    end_pat.extend(end_sep);

    // Find first end pattern with nothing else on its line
    let mut found = None;
    for idx in (0..working.len()).filter(|idx| working[*idx..].starts_with(&end_pat)) {
        let (eol_txt, rest) = parse_to_newline(&working[(idx + end_pat.len())..]);
        if eol_txt.iter().all(u8::is_ascii_whitespace) {
            found = Some((&working[..idx], rest));
            break;
        }
    }

    let (txt, rest) = found.unwrap_or((working, &[]));
    let txt = str::from_utf8(txt).unwrap().trim_matches('\n');

    (MdTree::CodeBlock { txt, lang }, rest)
}

fn parse_heading(buf: &[u8]) -> ParseResult<'_> {
    let level = buf.iter().take_while(|ch| **ch == b'#').count();
    let buf = &buf[level..];

    if level > 6 || (buf.len() > 1 && !buf[0].is_ascii_whitespace()) {
        // Enforce max 6 levels and whitespace following the `##` pattern
        return None;
    }

    let (txt, rest) = parse_to_newline(&buf[1..]);
    let ctx = Context { .. };
    let stream = parse_recursive(txt, ctx);

    Some((MdTree::Heading(level.try_into().unwrap(), stream), rest))
}

/// Bulleted list
fn parse_unordered_li(buf: &[u8]) -> Parsed<'_> {
    let (txt, rest) = get_indented_section(&buf[2..]);
    let ctx = Context { .. };
    let stream = parse_recursive(txt.trim_ascii_start(), ctx);
    (MdTree::UnorderedListItem(stream), rest)
}

/// Numbered list
fn parse_ordered_li(buf: &[u8]) -> Parsed<'_> {
    let (num, pos) = ord_list_start(buf).unwrap(); // success tested in caller
    let (txt, rest) = get_indented_section(&buf[pos..]);
    let ctx = Context { .. };
    let stream = parse_recursive(txt.trim_ascii_start(), ctx);
    (MdTree::OrderedListItem(num, stream), rest)
}

fn get_indented_section(buf: &[u8]) -> (&[u8], &[u8]) {
    let mut lines = buf.split(|&byte| byte == b'\n');
    let mut end = lines.next().map_or(0, |line| line.len());
    for line in lines {
        if let Some(first) = line.first() {
            if unordered_list_start(line) || !first.is_ascii_whitespace() {
                break;
            }
        }
        end += line.len() + 1;
    }

    (&buf[..end], &buf[end..])
}

fn unordered_list_start(mut buf: &[u8]) -> bool {
    while let [b' ', rest @ ..] = buf {
        buf = rest;
    }
    matches!(buf, [b'*' | b'-', b' ', ..])
}

/// Verify a valid ordered list start (e.g. `1.`) and parse it. Returns the
/// parsed number and offset of character after the dot.
fn ord_list_start(buf: &[u8]) -> Option<(u16, usize)> {
    let pos = buf.iter().take(10).position(|ch| *ch == b'.')?;
    let n = str::from_utf8(&buf[..pos]).ok()?;
    if !buf.get(pos + 1)?.is_ascii_whitespace() {
        return None;
    }
    n.parse::<u16>().ok().map(|v| (v, pos + 2))
}

/// Parse links. `can_be_def` indicates that a link definition is possible (top
/// level, located at the start of a line)
fn parse_any_link(buf: &[u8], can_be_def: bool) -> ParseResult<'_> {
    let (bracketed, rest) = parse_with_end_pat(&buf[1..], LNK_E, true)?;
    if rest.is_empty() {
        return None;
    }

    let disp = str::from_utf8(bracketed).unwrap();
    match (can_be_def, rest[0]) {
        (true, b':') => {
            let (link, tmp) = parse_to_newline(&rest[1..]);
            let link = str::from_utf8(link).unwrap().trim();
            Some((MdTree::LinkDef { id: disp, link }, tmp))
        }
        (_, b'(') => parse_simple_pat(rest, b"(", b")", ParseOpt::TrimNoEsc, |link| MdTree::Link {
            disp,
            link,
        }),
        (_, b'[') => parse_simple_pat(rest, b"[", b"]", ParseOpt::TrimNoEsc, |id| {
            MdTree::RefLink { disp, id: Some(id) }
        }),
        _ => Some((MdTree::RefLink { disp, id: None }, rest)),
    }
}

/// Find and consume an end pattern, return `(match, residual)`
fn parse_with_end_pat<'a>(
    buf: &'a [u8],
    end_sep: &[u8],
    ignore_esc: bool,
) -> Option<(&'a [u8], &'a [u8])> {
    // Find positions that start with the end separator
    for idx in (0..buf.len()).filter(|idx| buf[*idx..].starts_with(end_sep)) {
        if !ignore_esc && idx > 0 && buf[idx - 1] == b'\\' {
            continue;
        }
        return Some((&buf[..idx], &buf[idx + end_sep.len()..]));
    }
    None
}

/// Return `(match, residual)` to end of line. The EOL is returned with the
/// residual.
fn parse_to_newline(buf: &[u8]) -> (&[u8], &[u8]) {
    buf.iter().position(|ch| *ch == b'\n').map_or((buf, &[]), |pos| buf.split_at(pos))
}

/// Take a parsed stream and fix the little things
fn normalize<'a>(MdStream(stream): MdStream<'a>, linkdefs: &mut Vec<MdTree<'a>>) -> MdStream<'a> {
    let mut new_stream = Vec::with_capacity(stream.len());
    let new_defs = stream.iter().filter(|tt| matches!(tt, MdTree::LinkDef { .. }));
    linkdefs.extend(new_defs.cloned());

    // Run plaintext expansions on types that need it, call this function on nested types
    for item in stream {
        match item {
            MdTree::PlainText(txt) => expand_plaintext(txt, &mut new_stream, MdTree::PlainText),
            MdTree::Strong(txt) => expand_plaintext(txt, &mut new_stream, MdTree::Strong),
            MdTree::Emphasis(txt) => expand_plaintext(txt, &mut new_stream, MdTree::Emphasis),
            MdTree::Strikethrough(txt) => {
                expand_plaintext(txt, &mut new_stream, MdTree::Strikethrough);
            }
            MdTree::RefLink { disp, id } => new_stream.push(match_reflink(linkdefs, disp, id)),
            MdTree::OrderedListItem(n, st) => {
                new_stream.push(MdTree::OrderedListItem(n, normalize(st, linkdefs)));
            }
            MdTree::UnorderedListItem(st) => {
                new_stream.push(MdTree::UnorderedListItem(normalize(st, linkdefs)));
            }
            MdTree::Heading(n, st) => new_stream.push(MdTree::Heading(n, normalize(st, linkdefs))),
            _ => new_stream.push(item),
        }
    }

    // Remove non printing types, duplicate paragraph breaks, and breaks at start/end
    new_stream.retain(|x| !matches!(x, MdTree::Comment(_) | MdTree::LinkDef { .. }));
    new_stream.dedup_by(|r, l| matches!((r, l), (MdTree::ParagraphBreak, MdTree::ParagraphBreak)));

    if new_stream.first().is_some_and(is_break_ty) {
        new_stream.remove(0);
    }
    if new_stream.last().is_some_and(is_break_ty) {
        new_stream.pop();
    }

    // Remove paragraph breaks that shouldn't be there. w[1] is what will be
    // removed in these cases. Note that these are the items to keep, not delete
    // (for `retain`)
    let to_keep: Vec<bool> = new_stream
        .windows(3)
        .map(|w| {
            !((matches!(&w[1], MdTree::ParagraphBreak)
                && matches!(should_break(&w[0], &w[2]), BreakRule::Always(1) | BreakRule::Never))
                || (matches!(&w[1], MdTree::PlainText(txt) if txt.trim().is_empty())
                    && matches!(
                        should_break(&w[0], &w[2]),
                        BreakRule::Always(_) | BreakRule::Never
                    )))
        })
        .collect();
    let mut iter = iter::once(true).chain(to_keep).chain(iter::once(true));
    new_stream.retain(|_| iter.next().unwrap());

    // Insert line or paragraph breaks where there should be some
    let mut insertions = 0;
    let to_insert: Vec<(usize, MdTree<'_>)> = new_stream
        .windows(2)
        .enumerate()
        .filter_map(|(idx, w)| match should_break(&w[0], &w[1]) {
            BreakRule::Always(1) => Some((idx, MdTree::LineBreak)),
            BreakRule::Always(2) => Some((idx, MdTree::ParagraphBreak)),
            _ => None,
        })
        .map(|(idx, tt)| {
            insertions += 1;
            (idx + insertions, tt)
        })
        .collect();
    to_insert.into_iter().for_each(|(idx, tt)| new_stream.insert(idx, tt));

    MdStream(new_stream)
}

/// Whether two types should or shouldn't have a paragraph break between them
#[derive(Clone, Copy, Debug, PartialEq)]
enum BreakRule {
    Always(u8),
    Never,
    Optional,
}

/// Blocks that automatically handle their own text wrapping
fn should_break(left: &MdTree<'_>, right: &MdTree<'_>) -> BreakRule {
    use MdTree::*;

    match (left, right) {
        // Separate these types with a single line
        (HorizontalRule, _)
        | (_, HorizontalRule)
        | (OrderedListItem(_, _), OrderedListItem(_, _))
        | (UnorderedListItem(_), UnorderedListItem(_)) => BreakRule::Always(1),
        // Condensed types shouldn't have an extra break on either side
        (Comment(_) | ParagraphBreak | Heading(_, _), _) | (_, Comment(_) | ParagraphBreak) => {
            BreakRule::Never
        }
        // Block types should always be separated by full breaks
        (CodeBlock { .. } | OrderedListItem(_, _) | UnorderedListItem(_), _)
        | (_, CodeBlock { .. } | Heading(_, _) | OrderedListItem(_, _) | UnorderedListItem(_)) => {
            BreakRule::Always(2)
        }
        // Text types may or may not be separated by a break
        (
            CodeInline(_)
            | Strong(_)
            | Emphasis(_)
            | Strikethrough(_)
            | PlainText(_)
            | Link { .. }
            | RefLink { .. }
            | LinkDef { .. },
            CodeInline(_)
            | Strong(_)
            | Emphasis(_)
            | Strikethrough(_)
            | PlainText(_)
            | Link { .. }
            | RefLink { .. }
            | LinkDef { .. },
        ) => BreakRule::Optional,
        (LineBreak, _) | (_, LineBreak) => {
            unreachable!("should have been removed during deduplication")
        }
    }
}

/// Types that indicate some form of break
fn is_break_ty(val: &MdTree<'_>) -> bool {
    matches!(val, MdTree::ParagraphBreak | MdTree::LineBreak)
        // >1 break between paragraphs acts as a break
        || matches!(val, MdTree::PlainText(txt) if txt.trim().is_empty())
}

/// Perform transformations to text. This splits paragraphs, replaces patterns,
/// and corrects newlines.
///
/// To avoid allocating strings (and using a different heavier tt type), our
/// replace method means split into three and append each. For this reason, any
/// viewer should treat consecutive `PlainText` types as belonging to the same
/// paragraph.
fn expand_plaintext<'a>(
    txt: &'a str,
    stream: &mut Vec<MdTree<'a>>,
    mut f: fn(&'a str) -> MdTree<'a>,
) {
    if txt.is_empty() {
        return;
    } else if txt == "\n" {
        if let Some(tt) = stream.last() {
            let tmp = MdTree::PlainText(" ");
            if should_break(tt, &tmp) == BreakRule::Optional {
                stream.push(tmp);
            }
        }
        return;
    }
    let mut queue1 = Vec::new();
    let mut queue2 = Vec::new();
    let stream_start_len = stream.len();
    for paragraph in txt.split("\n\n") {
        if paragraph.is_empty() {
            stream.push(MdTree::ParagraphBreak);
            continue;
        }
        let paragraph = trim_extra_ws(paragraph);

        queue1.clear();
        queue1.push(paragraph);

        for (from, to) in REPLACEMENTS {
            queue2.clear();
            for item in &queue1 {
                for s in item.split(from) {
                    queue2.extend(&[s, to]);
                }
                if queue2.len() > 1 {
                    let _ = queue2.pop(); // remove last unnecessary intersperse
                }
            }
            mem::swap(&mut queue1, &mut queue2);
        }

        // Make sure we don't double whitespace
        queue1.retain(|s| !s.is_empty());
        for idx in 0..queue1.len() {
            queue1[idx] = trim_extra_ws(queue1[idx]);
            if idx < queue1.len() - 1
                && queue1[idx].ends_with(char::is_whitespace)
                && queue1[idx + 1].starts_with(char::is_whitespace)
            {
                queue1[idx] = queue1[idx].trim_end();
            }
        }
        stream.extend(queue1.iter().copied().filter(|txt| !txt.is_empty()).map(&mut f));
        stream.push(MdTree::ParagraphBreak);
    }

    if stream.len() - stream_start_len > 1 {
        let _ = stream.pop(); // remove last unnecessary intersperse
    }
}

/// Turn reflinks (links with reference IDs) into normal standalone links using
/// listed link definitions
fn match_reflink<'a>(linkdefs: &[MdTree<'a>], disp: &'a str, match_id: Option<&str>) -> MdTree<'a> {
    let to_match = match_id.unwrap_or(disp); // Match with the display name if there isn't an id
    for def in linkdefs {
        if let MdTree::LinkDef { id, link } = def {
            if *id == to_match {
                return MdTree::Link { disp, link };
            }
        }
    }
    MdTree::Link { disp, link: "" } // link not found
}

/// If there is more than one whitespace char at start or end, trim the extras
fn trim_extra_ws(mut txt: &str) -> &str {
    let start_ws =
        txt.bytes().position(|ch| !ch.is_ascii_whitespace()).unwrap_or(txt.len()).saturating_sub(1);
    txt = &txt[start_ws..];
    let end_ws = txt
        .bytes()
        .rev()
        .position(|ch| !ch.is_ascii_whitespace())
        .unwrap_or(txt.len())
        .saturating_sub(1);
    &txt[..txt.len() - end_ws]
}

#[cfg(test)]
#[path = "tests/parse.rs"]
mod tests;