links_notation/

parser.rs

use crate::quotes::{DelimitedReferences, QUOTES, Reading, read_reference};
use nom::{
    IResult, Parser,
    branch::alt,
    bytes::complete::{tag, take_while, take_while1},
    character::complete::{char, line_ending},
    combinator::eof,
    multi::{many0, many1},
    sequence::{preceded, terminated},
};
use std::cell::{Cell, OnceCell, RefCell};
use std::collections::HashMap;
use std::ops::Range;

#[derive(Debug, Clone, PartialEq)]
pub struct Link {
    pub id: Option<String>,
    pub values: Vec<Link>,
    pub children: Vec<Link>,
    pub is_indented_id: bool,
    /// Body of a parenthesized group, kept unflattened until the whole document
    /// is transformed. `None` for every link that is not a parenthesized group.
    pub nested: Option<Vec<Link>>,
    /// Where the ID was written: the byte range of the reference, quotes,
    /// escapes and literal syntax included, in the document that was parsed.
    /// The parser reads a copy of the document with its comments blanked, which
    /// keeps every byte where it was, so the range also locates the ID in the
    /// document as the caller wrote it. `None` when the link has no ID.
    pub id_span: Option<Range<usize>>,
}

impl Link {
    pub fn new_singlet(id: String) -> Self {
        Link {
            id: Some(id),
            values: vec![],
            children: vec![],
            is_indented_id: false,
            nested: None,
            id_span: None,
        }
    }

    pub fn new_indented_id(id: String) -> Self {
        Link {
            id: Some(id),
            values: vec![],
            children: vec![],
            is_indented_id: true,
            nested: None,
            id_span: None,
        }
    }

    pub fn new_value(values: Vec<Link>) -> Self {
        Link {
            id: None,
            values,
            children: vec![],
            is_indented_id: false,
            nested: None,
            id_span: None,
        }
    }

    pub fn new_link(id: Option<String>, values: Vec<Link>) -> Self {
        Link {
            id,
            values,
            children: vec![],
            is_indented_id: false,
            nested: None,
            id_span: None,
        }
    }

    /// Creates a link that stands for a parenthesized group, keeping the links
    /// parsed inside the parentheses as they were written.
    pub fn new_nested(body: Vec<Link>) -> Self {
        Link {
            id: None,
            values: vec![],
            children: vec![],
            is_indented_id: false,
            nested: Some(body),
            id_span: None,
        }
    }

    pub fn with_children(mut self, children: Vec<Link>) -> Self {
        self.children = children;
        self
    }

    /// The same link, recording where its ID was written.
    pub fn with_id_span(mut self, span: Range<usize>) -> Self {
        self.id_span = Some(span);
        self
    }
}

/// How deep links may nest when nothing says otherwise.
///
/// Every level of nesting is a level of recursion, so the limit is what keeps a
/// deeply nested document from overflowing the stack, which aborts the process
/// instead of returning an error. It is set well below what fits: in a debug
/// build a group written where a value goes, as in `(a (a (a b)))`, costs about
/// 24 KB of stack a level, so a spawned thread's 2 MiB holds only 86 of them.
/// The same limit applies in every Links Notation implementation.
pub const DEFAULT_MAX_DEPTH: usize = 64;

pub struct ParserState {
    indentation_stack: RefCell<Vec<usize>>,
    base_indentation: RefCell<Option<usize>>,
    nested_depth: RefCell<usize>,
    /// Nesting depth of the level-zero lines of the current context: the number
    /// of groups and indentation levels that enclose it.
    context_depth: RefCell<usize>,
    max_depth: usize,
    /// Where the document first nested deeper than `max_depth`, as an address
    /// into the document being parsed.
    too_deep: RefCell<Option<usize>>,
    furthest: RefCell<FurthestFailure>,
    unreadable_lines: RefCell<HashMap<LineKey, LineFailure>>,
    /// The delimited references of the document being parsed, listed from the
    /// document as written.
    references: OnceCell<DelimitedReferences>,
    /// The document as written, when the one being parsed has its comments
    /// blanked. Blanking keeps every byte where it was, and delimited
    /// references are read here, so blanking a comment never changes what a
    /// reference holds or how far it reaches (issue #377).
    source: Option<Box<str>>,
    /// Address of the first byte of the document being parsed, which turns the
    /// part of the document a reference was read from into a byte range.
    document_start: Cell<usize>,
}

/// Where a line starts, as an address into the document, and whether it is
/// inside a parenthesized group. Reading a line depends on nothing else: a group
/// starts a fresh indentation context, and indentation only decides which lines
/// become children, so a line that could not be read once never can be.
type LineKey = (usize, bool);

/// How far past the start of an unreadable line the parser failed, and the
/// `nom` error kind it failed with.
type LineFailure = (usize, nom::error::ErrorKind);

/// The furthest position any alternative reached before failing, and what could
/// have continued the document there.
///
/// The parser backtracks, so the position the last alternative happens to fail
/// at says little about where the document stops making sense: a defect in the
/// middle of line two is reported by `nom` as "expected end of input" at the
/// start of line two, because that is where the document last parsed cleanly.
/// The furthest position reached is what a PEG parser points at, and it is what
/// the JavaScript port reports.
#[derive(Debug, Clone, Default)]
struct FurthestFailure {
    /// Address of the furthest failing position, as a pointer into the document
    /// being parsed. Turned into an offset once the document is at hand again.
    address: Option<usize>,
    expected: Vec<&'static str>,
}

/// Where the parser stopped, and what it could have accepted there.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ParseFailure {
    /// Byte offset into the document the parser stopped at.
    pub offset: usize,
    /// What could have continued the document at `offset`, in the wording used
    /// by the error message. Empty when the failure came from a place that
    /// names no expectation.
    pub expected: Vec<&'static str>,
    /// The `nom` error kind. An internal detail of this parser: it says which
    /// combinator gave up, not what is wrong with the document, so it is kept
    /// out of the error message and reachable only through `Debug`.
    pub kind: Option<nom::error::ErrorKind>,
    /// The maximum nesting depth when the document nests deeper than it, which
    /// `offset` then points at; `None` for every other failure.
    pub max_depth_exceeded: Option<usize>,
}

/// Indentation state of the context a parenthesized group was opened in.
pub struct SavedContext {
    indentation_stack: Vec<usize>,
    base_indentation: Option<usize>,
    context_depth: usize,
}

impl Default for ParserState {
    fn default() -> Self {
        Self::new()
    }
}

impl ParserState {
    pub fn new() -> Self {
        Self::with_max_depth(DEFAULT_MAX_DEPTH)
    }

    /// A parser state that refuses links nested deeper than `max_depth`.
    pub fn with_max_depth(max_depth: usize) -> Self {
        ParserState {
            indentation_stack: RefCell::new(vec![0]),
            base_indentation: RefCell::new(None),
            nested_depth: RefCell::new(0),
            context_depth: RefCell::new(0),
            max_depth,
            too_deep: RefCell::new(None),
            furthest: RefCell::new(FurthestFailure::default()),
            unreadable_lines: RefCell::new(HashMap::new()),
            references: OnceCell::new(),
            source: None,
            document_start: Cell::new(0),
        }
    }

    /// `input`, a part of the document being parsed that runs to its end, in
    /// the document as written when it opens a delimited reference.
    ///
    /// A delimiter is never blanked, so where `input` opens with one the
    /// document as written has the same delimiter at the same byte.
    fn written<'s>(&'s self, input: &'s str) -> &'s str {
        match &self.source {
            Some(source) if input.as_bytes().first().is_some_and(|b| QUOTES.contains(b)) => source
                .len()
                .checked_sub(input.len())
                .and_then(|start| source.get(start..))
                .unwrap_or(input),
            _ => input,
        }
    }

    /// The delimited references of the document being parsed, listed from the
    /// document as written; `input` is that document when it has no comments
    /// blanked.
    fn references(&self, input: &str) -> &DelimitedReferences {
        self.references
            .get_or_init(|| DelimitedReferences::new(self.source.as_deref().unwrap_or(input)))
    }

    pub fn set_base_indentation(&self, indent: usize) {
        let mut base = self.base_indentation.borrow_mut();
        if base.is_none() {
            *base = Some(indent);
        }
    }

    pub fn get_base_indentation(&self) -> usize {
        self.base_indentation.borrow().unwrap_or(0)
    }

    pub fn normalize_indentation(&self, indent: usize) -> usize {
        let base = self.get_base_indentation();
        indent.saturating_sub(base)
    }

    pub fn push_indentation(&self, indent: usize) {
        self.indentation_stack.borrow_mut().push(indent);
    }

    pub fn pop_indentation(&self) {
        let mut stack = self.indentation_stack.borrow_mut();
        if stack.len() > 1 {
            stack.pop();
        }
    }

    pub fn current_indentation(&self) -> usize {
        *self.indentation_stack.borrow().last().unwrap_or(&0)
    }

    pub fn check_indentation(&self, indent: usize) -> bool {
        indent >= self.current_indentation()
    }

    /// Opens a nested context: the group body starts fresh at indentation level
    /// zero and follows the same rules as the root document.
    pub fn enter_nested_context(&self) -> SavedContext {
        let depth = self.depth() + 1;
        let saved = SavedContext {
            indentation_stack: self.indentation_stack.replace(vec![0]),
            base_indentation: self.base_indentation.replace(None),
            context_depth: self.context_depth.replace(depth),
        };
        *self.nested_depth.borrow_mut() += 1;
        saved
    }

    /// Restores the context the parenthesized group was opened in.
    pub fn exit_nested_context(&self, saved: SavedContext) {
        *self.indentation_stack.borrow_mut() = saved.indentation_stack;
        *self.base_indentation.borrow_mut() = saved.base_indentation;
        *self.context_depth.borrow_mut() = saved.context_depth;
        let mut depth = self.nested_depth.borrow_mut();
        if *depth > 0 {
            *depth -= 1;
        }
    }

    pub fn is_inside_nested_context(&self) -> bool {
        *self.nested_depth.borrow() > 0
    }

    /// Nesting depth of the line being parsed: every enclosing parenthesized
    /// group and every indentation level counts as one.
    pub fn depth(&self) -> usize {
        *self.context_depth.borrow() + self.indentation_stack.borrow().len() - 1
    }

    /// Fails for good when `depth` is deeper than the parser allows, so that
    /// no alternative goes on to recurse any further. `at` is where the level
    /// that is one too deep opens.
    fn check_depth<'a>(&self, at: &'a str, depth: usize) -> IResult<&'a str, ()> {
        if depth <= self.max_depth {
            return Ok((at, ()));
        }
        self.too_deep
            .borrow_mut()
            .get_or_insert(at.as_ptr() as usize);
        Err(nom::Err::Failure(nom::error::Error::new(
            at,
            nom::error::ErrorKind::TooLarge,
        )))
    }

    /// Records that `what` could have continued the document at `at`, and that
    /// nothing there did. Only the furthest such position is kept; every
    /// expectation recorded at that same position is kept alongside it.
    fn expected_at(&self, at: &str, what: &'static str) {
        let address = at.as_ptr() as usize;
        let mut furthest = self.furthest.borrow_mut();
        match furthest.address {
            Some(recorded) if recorded > address => {}
            Some(recorded) if recorded == address => {
                if !furthest.expected.contains(&what) {
                    furthest.expected.push(what);
                }
            }
            _ => {
                furthest.address = Some(address);
                furthest.expected = vec![what];
            }
        }
    }

    /// Turns everything recorded during a failed parse into a position in
    /// `document`.
    ///
    /// `nom`'s own error position is the fallback and the floor: the parser
    /// reached at least that far, whatever the tracked alternatives say.
    fn failure(&self, document: &str, error: &nom::Err<nom::error::Error<&str>>) -> ParseFailure {
        let base = document.as_ptr() as usize;
        let (nom_offset, kind) = match error {
            nom::Err::Error(e) | nom::Err::Failure(e) => (
                (e.input.as_ptr() as usize).saturating_sub(base),
                Some(e.code),
            ),
            nom::Err::Incomplete(_) => (document.len(), None),
        };
        if let Some(address) = *self.too_deep.borrow() {
            return ParseFailure {
                offset: address.saturating_sub(base).min(document.len()),
                expected: Vec::new(),
                kind,
                max_depth_exceeded: Some(self.max_depth),
            };
        }
        let furthest = self.furthest.borrow();
        let tracked = furthest
            .address
            .map(|address| address.saturating_sub(base))
            .unwrap_or(0);
        let offset = tracked.max(nom_offset).min(document.len());
        let expected = if tracked == offset {
            furthest.expected.clone()
        } else {
            // The tracked expectations belong to an earlier position, so they
            // do not describe the place being reported.
            Vec::new()
        };
        ParseFailure {
            offset,
            expected,
            kind,
            max_depth_exceeded: None,
        }
    }
}

/// Fails the way `nom` does, after recording what was expected at `input`.
fn expected<'a, T>(
    input: &'a str,
    state: &ParserState,
    what: &'static str,
    kind: nom::error::ErrorKind,
) -> IResult<&'a str, T> {
    state.expected_at(input, what);
    Err(nom::Err::Error(nom::error::Error::new(input, kind)))
}

pub(crate) fn is_whitespace_char(c: char) -> bool {
    c == ' ' || c == '\t' || c == '\n' || c == '\r'
}

fn is_horizontal_whitespace(c: char) -> bool {
    c == ' ' || c == '\t'
}

fn is_reference_char(c: char) -> bool {
    !is_whitespace_char(c) && c != '(' && c != ':' && c != ')'
}

fn horizontal_whitespace(input: &str) -> IResult<&str, &str> {
    take_while(is_horizontal_whitespace)(input)
}

fn whitespace(input: &str) -> IResult<&str, &str> {
    take_while(is_whitespace_char)(input)
}

fn simple_reference(input: &str) -> IResult<&str, String> {
    take_while1(is_reference_char)
        .map(|s: &str| s.to_string())
        .parse(input)
}

/// The offset just past the delimited reference that starts at `start`, or
/// `None` when nothing that far into `document` opens one.
///
/// Comment stripping needs to know how far a delimited reference reaches so
/// that a `#` written inside one stays content, and it has to agree with the
/// parser about it, which is why both read references the same way.
pub fn quoted_reference_end(document: &str, start: usize) -> Option<usize> {
    let reading = read_reference(document.get(start..)?)?;
    Some(start + reading.length)
}

/// A delimited reference with any number of delimiters. A run of an even
/// number of delimiters that does not open a reference with a substantive body
/// is the empty reference.
///
/// The reference is read in the document as written: blanking a comment keeps
/// every byte where it was, but may change what an even run encloses, and so
/// whether it is the empty reference (issue #377).
fn delimited_reference<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, String> {
    match state.references(input).read(state.written(input)) {
        Some(Reading { value, length, .. }) => Ok((&input[length..], value)),
        None => Err(nom::Err::Error(nom::error::Error::new(
            input,
            nom::error::ErrorKind::Tag,
        ))),
    }
}

fn reference<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, String> {
    if let Some(prefix) = crate::reference_literal::prefix_end(input) {
        if let Some(closing) = input[prefix..].find('}') {
            let length = prefix + closing + 1;
            if let Ok(value) = crate::decode_reference_literal(&input[..length]) {
                return Ok((&input[length..], value));
            }
        }
        state.expected_at(input, "a valid version 1 reference literal");
        return Err(nom::Err::Failure(nom::error::Error::new(
            input,
            nom::error::ErrorKind::Tag,
        )));
    }
    // Try quoted strings with dynamic quote detection (supports any N quotes)
    // Then fall back to simple unquoted reference
    let parsed = alt((|i| delimited_reference(i, state), simple_reference)).parse(input);
    if parsed.is_err() {
        state.expected_at(input, "a reference");
    }
    parsed
}

/// A reference together with the byte range it was written at, so that a link
/// can say how its ID was written.
fn spanned_reference<'a>(
    input: &'a str,
    state: &ParserState,
) -> IResult<&'a str, (String, Range<usize>)> {
    let (rest, value) = reference(input, state)?;
    let start = (input.as_ptr() as usize).saturating_sub(state.document_start.get());
    let end = start + (input.len() - rest.len());
    Ok((rest, (value, start..end)))
}

fn eol<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, &'a str> {
    let parsed = alt((
        preceded(horizontal_whitespace, alt((line_ending, tag("\r")))),
        preceded(horizontal_whitespace, eof),
        |i| nested_group_end(i, state),
    ))
    .parse(input);
    if parsed.is_err() {
        state.expected_at(input, "end of line");
    }
    parsed
}

/// Inside a parenthesized group the closing parenthesis ends the last line,
/// just like a line break does at the root.
fn nested_group_end<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, &'a str> {
    if !state.is_inside_nested_context() {
        return Err(nom::Err::Error(nom::error::Error::new(
            input,
            nom::error::ErrorKind::Verify,
        )));
    }
    let (rest, _) = horizontal_whitespace(input)?;
    if rest.starts_with(')') {
        Ok((rest, ""))
    } else {
        expected(rest, state, "\")\"", nom::error::ErrorKind::Char)
    }
}

/// Skips the line breaks and blank lines that separate `(` from the first line
/// of the group body.
fn skip_empty_lines(input: &str) -> &str {
    let mut rest = input;
    loop {
        let line_start = rest.trim_start_matches(is_horizontal_whitespace);
        match strip_line_ending(line_start) {
            Some(next) => rest = next,
            None => return rest,
        }
    }
}

fn strip_line_ending(input: &str) -> Option<&str> {
    input
        .strip_prefix("\r\n")
        .or_else(|| input.strip_prefix('\n'))
        .or_else(|| input.strip_prefix('\r'))
}

fn reference_or_link<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, Link> {
    alt((
        |i| nested_group(i, state),
        (|i| spanned_reference(i, state))
            .map(|(id, span)| Link::new_singlet(id).with_id_span(span)),
    ))
    .parse(input)
}

fn single_line_value_and_whitespace<'a>(
    input: &'a str,
    state: &ParserState,
) -> IResult<&'a str, Link> {
    preceded(horizontal_whitespace, |i| reference_or_link(i, state)).parse(input)
}

fn single_line_values<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, Vec<Link>> {
    many1(|i| single_line_value_and_whitespace(i, state)).parse(input)
}

fn single_line_link<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, Link> {
    let (input, _) = horizontal_whitespace(input)?;
    let (input, (id, span)) = spanned_reference(input, state)?;
    let (input, _) = horizontal_whitespace(input)?;
    let (input, _) = colon(input, state)?;
    let (input, values) = single_line_values(input, state)?;
    Ok((input, Link::new_link(Some(id), values).with_id_span(span)))
}

/// The colon that separates an identifier from its values.
fn colon<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, char> {
    character(':', input, state, "\":\"")
}

/// Matches one character, recording what was expected when it is not there.
fn character<'a>(
    wanted: char,
    input: &'a str,
    state: &ParserState,
    what: &'static str,
) -> IResult<&'a str, char> {
    let parsed: IResult<&'a str, char> = char(wanted).parse(input);
    match parsed {
        Ok(parsed) => Ok(parsed),
        Err(_) => expected(input, state, what, nom::error::ErrorKind::Char),
    }
}

fn single_line_value_link<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, Link> {
    (|i| single_line_values(i, state))
        .map(Link::new_value)
        .parse(input)
}

fn indented_id_link<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, Link> {
    let (input, (id, span)) = spanned_reference(input, state)?;
    let (input, _) = horizontal_whitespace(input)?;
    let (input, _) = colon(input, state)?;
    let (input, _) = eol(input, state)?;
    Ok((input, Link::new_indented_id(id).with_id_span(span)))
}

/// A parenthesized group opens a nested context: its body starts fresh at
/// indentation level zero and is parsed with the same rules as the root
/// document, so indentation is structural inside parentheses as well.
fn nested_group<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, Link> {
    let (body_input, _) = character('(', input, state, "\"(\"")?;
    state.check_depth(input, state.depth() + 1)?;
    let saved = state.enter_nested_context();
    let result = nested_group_body(body_input, state);
    state.exit_nested_context(saved);
    result
}

fn nested_group_body<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, Link> {
    match links(skip_empty_lines(input), state) {
        Ok((rest, body)) => {
            let (rest, _) = whitespace(rest)?;
            let (rest, _) = closing_parenthesis(rest, state)?;
            return Ok((rest, Link::new_nested(body)));
        }
        Err(failure @ nom::Err::Failure(_)) => return Err(failure),
        Err(_) => {}
    }
    let (rest, _) = whitespace(input)?;
    let (rest, _) = closing_parenthesis(rest, state)?;
    Ok((rest, Link::new_nested(vec![])))
}

/// The parenthesis that closes a group.
fn closing_parenthesis<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, char> {
    character(')', input, state, "\")\"")
}

fn single_line_any_link<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, Link> {
    alt((
        terminated(|i| single_line_link(i, state), |i| eol(i, state)),
        terminated(|i| single_line_value_link(i, state), |i| eol(i, state)),
    ))
    .parse(input)
}

/// Reads one line, or fails at once when the line was already found unreadable.
///
/// A line that does not parse as the first child of the line above it is tried
/// again as a sibling at every enclosing indentation level. When the line holds
/// a group, each of those attempts reads the whole group again, so without this
/// the work doubles with every indented level (issue #314).
fn any_link<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, Link> {
    let key = (input.as_ptr() as usize, state.is_inside_nested_context());
    if let Some(&(offset, kind)) = state.unreadable_lines.borrow().get(&key) {
        return Err(nom::Err::Error(nom::error::Error::new(
            &input[offset..],
            kind,
        )));
    }
    let parsed = read_any_link(input, state);
    if let Err(nom::Err::Error(error)) = &parsed {
        let offset = error.input.as_ptr() as usize - input.as_ptr() as usize;
        state
            .unreadable_lines
            .borrow_mut()
            .insert(key, (offset, error.code));
    }
    parsed
}

/// A line that starts with a parenthesized group reads that group once and then
/// branches on what follows it: the end of the line makes the group the whole
/// link, and more values make it the first value of a value link.
///
/// Every other alternative would have to read the group again, which doubles
/// the work at each level of nesting and makes a few dozen bytes take seconds
/// ([#314](https://github.com/link-foundation/links-notation/issues/314)).
fn read_any_link<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, Link> {
    let (rest, group) = match nested_group(input, state) {
        Ok(parsed) => parsed,
        // Neither an indented ID nor a single-line link can start with a
        // parenthesis, and a value link would begin with this same group, so
        // nothing else can read a line that opens one. Report it the way the
        // single-line value link does, as a missing reference.
        Err(_) if input.starts_with('(') => {
            return spanned_reference(input, state)
                .map(|(rest, (id, span))| (rest, Link::new_singlet(id).with_id_span(span)));
        }
        Err(_) => {
            return alt((
                |i| indented_id_link(i, state),
                |i| single_line_any_link(i, state),
            ))
            .parse(input);
        }
    };
    if let Ok((rest, _)) = eol(rest, state) {
        return Ok((rest, group));
    }
    let (rest, more) = many0(|i| single_line_value_and_whitespace(i, state)).parse(rest)?;
    let (rest, _) = eol(rest, state)?;
    let mut values = Vec::with_capacity(more.len() + 1);
    values.push(group);
    values.extend(more);
    Ok((rest, Link::new_value(values)))
}

fn count_indentation(input: &str) -> IResult<&str, usize> {
    take_while(|c| c == ' ').map(|s: &str| s.len()).parse(input)
}

fn push_indentation<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, ()> {
    let (input, spaces) = count_indentation(skip_empty_lines(input))?;
    let normalized_spaces = state.normalize_indentation(spaces);
    let current = state.current_indentation();

    if normalized_spaces > current {
        state.push_indentation(normalized_spaces);
        Ok((input, ()))
    } else {
        Err(nom::Err::Error(nom::error::Error::new(
            input,
            nom::error::ErrorKind::Verify,
        )))
    }
}

fn check_indentation<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, ()> {
    let (input, spaces) = count_indentation(input)?;
    let normalized_spaces = state.normalize_indentation(spaces);

    if state.check_indentation(normalized_spaces) {
        Ok((input, ()))
    } else {
        Err(nom::Err::Error(nom::error::Error::new(
            input,
            nom::error::ErrorKind::Verify,
        )))
    }
}

fn element<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, Link> {
    let start = input;
    let (input, link) = any_link(input, state)?;
    // Only a line that parsed counts, so trailing spaces indented past the limit
    // are still read as the whitespace they are.
    state.check_depth(start, state.depth())?;

    let indentation = state.indentation_stack.borrow().clone();
    if let Ok((child_input, _)) = push_indentation(input, state) {
        match links(child_input, state) {
            Ok((rest, children)) => return Ok((rest, link.with_children(children))),
            Err(failure @ nom::Err::Failure(_)) => return Err(failure),
            Err(_) => {}
        }
        // No child line followed the indentation. Backtrack to the link so
        // the document can consume the remaining spaces as whitespace.
        state.indentation_stack.replace(indentation);
    }
    Ok((input, link))
}

fn first_line<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, Link> {
    // Set base indentation from the first line and consume it, so that the first
    // line is parsed exactly like every following line.
    let (input, spaces) = count_indentation(input)?;
    state.set_base_indentation(spaces);
    element(input, state)
}

fn line<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, Link> {
    // Blank lines do not break a document, they are simply skipped
    preceded(|i| check_indentation(i, state), |i| element(i, state)).parse(skip_empty_lines(input))
}

fn links<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, Vec<Link>> {
    let (input, first) = first_line(input, state)?;
    let (input, rest) = many0(|i| line(i, state)).parse(input)?;

    state.pop_indentation();

    let mut result = vec![first];
    result.extend(rest);
    Ok((input, result))
}

pub fn parse_document(input: &str) -> IResult<&str, Vec<Link>> {
    let state = ParserState::new();
    document(input, &state)
}

/// Parses a document and, when it does not parse, says where it stopped.
///
/// `parse_document` reports a failure the way `nom` does: with the whole
/// unconsumed remainder of the input and the combinator that gave up. Neither
/// tells a reader which line to look at, and the remainder grows with the size
/// of the document. This is the entry point the library uses.
pub fn parse_document_with_diagnostics(input: &str) -> Result<Vec<Link>, ParseFailure> {
    parse_document_with_max_depth(input, DEFAULT_MAX_DEPTH)
}

/// Parses a document the way [`parse_document_with_diagnostics`] does, refusing
/// links nested deeper than `max_depth`. Every parenthesized group and every
/// indentation level is one level of nesting.
pub fn parse_document_with_max_depth(
    input: &str,
    max_depth: usize,
) -> Result<Vec<Link>, ParseFailure> {
    let state = ParserState::with_max_depth(max_depth);
    match document(input, &state) {
        Ok((_, links)) => Ok(links),
        Err(error) => Err(state.failure(input, &error)),
    }
}

/// Parses `prepared`, the document `source` with its comments blanked, the way
/// [`parse_document_with_max_depth`] does, reading delimited references in
/// `source`: the document as written.
pub(crate) fn parse_prepared_document(
    prepared: &str,
    source: &str,
    max_depth: usize,
) -> Result<Vec<Link>, ParseFailure> {
    debug_assert_eq!(prepared.len(), source.len());
    let mut state = ParserState::with_max_depth(max_depth);
    if prepared != source {
        state.source = Some(source.into());
    }
    match document(prepared, &state) {
        Ok((_, links)) => Ok(links),
        Err(error) => Err(state.failure(prepared, &error)),
    }
}

fn document<'a>(input: &'a str, state: &ParserState) -> IResult<&'a str, Vec<Link>> {
    // Every reference is read from a part of this document, so the runs of
    // delimiters are listed from all of it.
    state.references(input);
    state.document_start.set(input.as_ptr() as usize);

    // Skip leading blank lines but preserve the line structure
    let document = skip_empty_lines(input);

    // Handle empty or whitespace-only documents
    if document.trim_matches(is_whitespace_char).is_empty() {
        return Ok(("", vec![]));
    }

    let (rest, result) = links(document, state)?;
    let (rest, _) = whitespace(rest)?;
    let end: IResult<&'a str, &'a str> = eof(rest);
    let (rest, _) = match end {
        Ok(parsed) => parsed,
        Err(_) => return expected(rest, state, "end of input", nom::error::ErrorKind::Eof),
    };

    Ok((rest, result))
}