notescraft/crates/markdown/src/scanning/footnotes.rs

//! Footnotes: `[^label]` references, `[^label]:` definition markers and
//! `^[..]` inline footnotes (Obsidian basics, SPEC 5).
//!
//! The pass runs after the `CommonMark` and comment passes and before the
//! Obsidian body scan, and the ranges it finds join the skip set, so no
//! later scanner reports a construct inside a footnote. Openers never sit in
//! code, math, HTML, comments, frontmatter, wikilinks or markdown links; an
//! inline footnote body may cross a code span but never the start of another
//! item, so a footnote can only sit inside a heading or a highlight, the way
//! an inline tag sits inside a heading. A reference whose label has no
//! definition anywhere is still reported: the view decides.
//!
//! Bounded work: label, body, `[[..]]` and `](..)` probes charge a byte
//! budget; a document made of unclosed probes stops the pass early instead
//! of running quadratic time. Items never change the source, so parsing
//! stays lossless.

use std::ops::Range;

use crate::scanning::math_scan::Covered;
use crate::scanning::scan::{char_len, content_start, is, link_span, parens_end};
use crate::{Item, ItemKind, MAX_NESTING_DEPTH};

/// A footnote label holds at most this many characters.
const MAX_LABEL_CHARS: usize = 100;
/// An inline footnote body holds at most this many bytes.
const MAX_INLINE_BYTES: usize = 2_000;
/// Probe budget charged per source byte.
const BUDGET_PER_BYTE: usize = 32;
/// Budget floor, so small notes are never starved.
const BUDGET_FLOOR: usize = 4_096;

/// The footnote items of `src`, in source order.
///
/// `skip` are the spans where nothing may be recognised (code, HTML, math,
/// comments, frontmatter) and `items` the constructs already taken; a
/// footnote never starts inside either.
#[must_use]
pub(crate) fn scan(src: &str, skip: &[Range<usize>], items: &[Item]) -> Vec<Item> {
    // A markdown link owns its label and its destination, so nothing inside
    // one is a footnote.
    let covered = Covered::new({
        let mut ranges = skip.to_vec();
        ranges.extend(items.iter().filter(|item| matches!(item.kind, ItemKind::Link { .. })).map(|item| item.range.clone()));
        ranges
    });
    // Sorted starts of the items a footnote body may never cross.
    let mut starts: Vec<usize> = items.iter().map(|item| item.range.start).collect();
    starts.sort_unstable();
    let budget = src.len().saturating_mul(BUDGET_PER_BYTE).saturating_add(BUDGET_FLOOR);
    let mut pass = Pass { src, bytes: src.as_bytes(), covered, starts, budget, out: Vec::new() };
    pass.run();
    pass.out
}

/// One forward pass over the source.
struct Pass<'a> {
    /// The note being scanned.
    src: &'a str,
    /// `src` as raw bytes.
    bytes: &'a [u8],
    /// Spans where no opener may sit: `skip` plus markdown links.
    covered: Covered,
    /// Sorted starts of the items a footnote body may not cross.
    starts: Vec<usize>,
    /// Bytes of probe budget left.
    budget: usize,
    /// The items found so far.
    out: Vec<Item>,
}

impl Pass<'_> {
    /// Walk the source once, left to right.
    fn run(&mut self) {
        let len = self.bytes.len();
        let mut at = 0;
        while at < len {
            if let Some(after) = self.covered.jump(at) {
                at = after;
                continue;
            }
            let Some(&b) = self.bytes.get(at) else { break };
            let next = self.bytes.get(at + 1).copied();
            at = match b {
                // `\^` is an escaped caret, so `\^[` never opens; `\\` is
                // an escaped backslash, so the `^[` after it stays live. A
                // backslash before `[` is left to the body scanner, which
                // does not treat it as an escape either.
                b'\\' if is(next, b'\\') || is(next, b'^') => self.step(at, 2),
                b'\\' => self.step(at, 1),
                b'!' if is(next, b'[') && is(self.bytes.get(at + 2).copied(), b'[') => self.wiki_jump(at, 1),
                b'[' if is(next, b'[') => self.wiki_jump(at, 0),
                b']' if is(next, b'(') => self.parens_jump(at),
                b'[' if is(next, b'^') => self.reference(at),
                b'^' if is(next, b'[') => self.inline_footnote(at),
                _ => self.step(at, char_len(self.src, at)),
            };
        }
    }

    /// Jump over a wikilink (`bang == 0`) or an embed (`bang == 1`) so
    /// nothing inside it is reported.
    fn wiki_jump(&mut self, at: usize, bang: usize) -> usize {
        let end = line_end(self.src, at);
        match link_span(self.src, at + bang, end) {
            Some((_, close)) if self.charge(close - at) => close.min(end),
            _ => self.step(at, 1),
        }
    }

    /// Jump over a link destination: `]( ... )`.
    fn parens_jump(&mut self, at: usize) -> usize {
        let after = parens_end(self.src, at + 1).clamp(at + 1, line_end(self.src, at));
        if !self.charge(after - at) {
            return self.src.len();
        }
        after
    }

    /// A `[^label]` reference or a `[^label]:` definition marker at `at`.
    fn reference(&mut self, at: usize) -> usize {
        match self.reference_probe(at) {
            Some((item, after)) => {
                self.out.push(item);
                after
            }
            None => self.step(at, 1),
        }
    }

    /// The item and the offset past it, or nothing.
    fn reference_probe(&mut self, at: usize) -> Option<(Item, usize)> {
        if self.covered.jump(at + 1).is_some() {
            return None;
        }
        // The label is any run without whitespace or `]`, capped.
        let mut pos = at + 2;
        let mut chars = 0usize;
        loop {
            // A label never runs through code, math or any other taken span.
            if self.covered.jump(pos).is_some() {
                return None;
            }
            let rest = self.src.get(pos..)?;
            let head = rest.chars().next()?;
            if head == ']' || head.is_whitespace() {
                break;
            }
            chars += 1;
            if chars > MAX_LABEL_CHARS {
                return None;
            }
            pos += head.len_utf8();
            if !self.charge(head.len_utf8()) {
                return None;
            }
        }
        if self.bytes.get(pos) != Some(&b']') || chars == 0 {
            return None;
        }
        let label = self.src.get(at + 2..pos)?.to_string();
        let close = pos + 1;
        let def = self.bytes.get(close) == Some(&b':') && self.at_content_start(at);
        let (kind, end) = if def { (ItemKind::FootnoteDef { label }, close + 1) } else { (ItemKind::Footnote { label }, close) };
        Some((Item { kind, range: at..end }, end))
    }

    /// Whether `open` is the content start of its line, after container
    /// prefixes, so a `[^..]:` there is a definition marker.
    fn at_content_start(&mut self, open: usize) -> bool {
        let Some(head) = self.src.get(..open) else { return false };
        let line_start = head.rfind('\n').map_or(0, |at| at + 1);
        if !self.charge(open - line_start) {
            return false;
        }
        content_start(self.src, line_start, line_end(self.src, open), MAX_NESTING_DEPTH) == open
    }

    /// An inline footnote `^[..]` opening at the `^` at `at`.
    fn inline_footnote(&mut self, at: usize) -> usize {
        match self.body_probe(at) {
            Some(end) => {
                self.out.push(Item { kind: ItemKind::InlineFootnote, range: at..end });
                end
            }
            None => self.step(at, 1),
        }
    }

    /// The offset past the closing `]` of the body, or nothing. The body
    /// balances `[` and `]`, stops at a blank line, is capped and never
    /// crosses the start of another item.
    fn body_probe(&mut self, at: usize) -> Option<usize> {
        if self.covered.jump(at + 1).is_some() {
            return None;
        }
        let next_start = self.starts.partition_point(|&start| start <= at + 1);
        let bytes = self.bytes;
        let mut pos = at + 2;
        let mut depth = 1usize;
        let mut size = 0usize;
        loop {
            if let Some(after) = self.covered.jump(pos) {
                // A body may cross code and other skip spans, but never the
                // start of an item hiding inside them (math, comments).
                if self.starts.get(next_start).is_some_and(|&start| start < after) {
                    return None;
                }
                let crossed = after - pos;
                if !self.charge(crossed) {
                    return None;
                }
                pos = after;
                size += crossed;
                if size > MAX_INLINE_BYTES {
                    return None;
                }
                continue;
            }
            if self.starts.get(next_start).is_some_and(|&start| start <= pos) {
                return None; // the body would swallow another item
            }
            let &b = bytes.get(pos)?;
            if b == b'\n' || b == b'\r' {
                let break_len = 1 + usize::from(b == b'\r' && bytes.get(pos + 1) == Some(&b'\n'));
                if blank_after(bytes, pos + break_len) {
                    return None; // an inline footnote never crosses a blank line
                }
                if !self.charge(break_len) {
                    return None;
                }
                pos += break_len;
                size += break_len;
                if size > MAX_INLINE_BYTES {
                    return None;
                }
                continue;
            }
            if b == b'[' {
                depth += 1;
            } else if b == b']' {
                depth = depth.checked_sub(1)?;
                if depth == 0 {
                    return Some(pos + 1);
                }
            }
            let advance = char_len(self.src, pos);
            if !self.charge(advance) {
                return None;
            }
            pos += advance;
            size += advance;
            if size > MAX_INLINE_BYTES {
                return None;
            }
        }
    }

    /// Advance `advance` bytes, charging the budget; the source length when
    /// the budget is gone, which ends the pass.
    fn step(&mut self, at: usize, advance: usize) -> usize {
        if !self.charge(advance) {
            return self.src.len();
        }
        at + advance
    }

    /// Spend `n` bytes of budget; false when the pass must stop.
    fn charge(&mut self, n: usize) -> bool {
        if self.budget <= n {
            self.budget = 0;
            return false;
        }
        self.budget -= n;
        true
    }
}

/// The content end of the line holding `from`, before the line ending.
fn line_end(src: &str, from: usize) -> usize {
    let Some(rest) = src.get(from..) else { return from };
    match rest.find('\n') {
        Some(nl) => {
            let absolute = from + nl;
            if nl > 0 && src.as_bytes().get(absolute - 1) == Some(&b'\r') { absolute - 1 } else { absolute }
        }
        None => src.len(),
    }
}

/// Whether the line after the break ending at `from` is blank: only spaces
/// and tabs, then another break.
fn blank_after(bytes: &[u8], from: usize) -> bool {
    let mut at = from;
    while matches!(bytes.get(at), Some(b' ' | b'\t')) {
        at += 1;
    }
    matches!(bytes.get(at), Some(b'\n' | b'\r'))
}