asciidoc_parser/parser/

source_map.rs

use std::fmt;

use crate::Span;

/// Generated by the preprocessor: a map from a line number in the preprocessed,
/// unified source ([`Span`]) back to the original input file and line it came
/// from. This lets a consumer work backwards from a parsed element's [`Span`]
/// to the file and line the author actually wrote.
///
/// The map is stored as a sparse, sorted list of segments. Each segment anchors
/// one preprocessed line to an origin (file, line); the lines that follow it
/// map by simple offset until the next segment. A segment also records the
/// [`Fidelity`] of the preprocessed line relative to its origin – whether the
/// preprocessor rewrote the line content (so a column can no longer be mapped
/// back faithfully) or left it verbatim. All line numbers are 1-based.
///
/// Origin file names are interned: a file included many times, or re-anchored
/// many times, stores its path only once.
///
/// [`Span`]: crate::Span
#[derive(Clone, Default, Eq, PartialEq)]
pub struct SourceMap {
    /// Interned origin file names. A [`Segment::file`] of `Some(i)` indexes
    /// here; `None` means the root document passed to `Parser::parse`.
    files: Vec<String>,

    /// The anchor segments, sorted by [`Segment::output_line`].
    segments: Vec<Segment>,
}

/// A single anchor in a [`SourceMap`]: the preprocessed line
/// [`output_line`](Self::output_line) came from origin line
/// [`source_line`](Self::source_line) of [`file`](Self::file), with the given
/// [`fidelity`](Self::fidelity). Preprocessed lines after it map by offset
/// (`source_line + n` for `output_line + n`) until the next segment.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
struct Segment {
    output_line: usize,
    file: Option<u32>,
    source_line: usize,
    fidelity: Fidelity,
}

/// A `SourceLine` represents the original file and line number where a line of
/// AsciiDoc text was found before [include file] and [conditional]
/// pre-processing occurred.
///
/// The first member is the file name as specified on the [include file]
/// directive. The second member is the 1-based line number.
///
/// [include file]: https://docs.asciidoctor.org/asciidoc/latest/directives/include/
/// [conditional]: https://docs.asciidoctor.org/asciidoc/latest/directives/conditionals/
#[derive(Clone, Debug, Default, Eq, PartialEq)]
pub struct SourceLine(pub Option<String>, pub usize);

/// The origin of a position in the preprocessed source: the input file, line,
/// and (where recoverable) column the author actually wrote, together with the
/// [`Fidelity`] of the mapping.
///
/// Returned by [`SourceMap::origin_at`], [`SourceMap::origin_of`], and
/// [`Document::origin_of`](crate::Document::origin_of).
///
/// The `file` is the name as written on the [include file] directive that
/// pulled it in, or `None` for the root document passed to `Parser::parse`.
///
/// `line` and `col` are 1-based. `col` counts **Unicode scalar values** from
/// the start of the line (matching [`Span::col`]), not grapheme clusters or
/// UTF-16 code units; an editor that counts grapheme clusters may report a
/// different column for a line containing multi-scalar graphemes. `col` is
/// `Some` only when [`fidelity`](Self::fidelity) is [`Fidelity::Verbatim`]: on
/// a line the preprocessor rewrote, the column can no longer be mapped back to
/// the origin, so it is reported as `None`.
///
/// [include file]: https://docs.asciidoctor.org/asciidoc/latest/directives/include/
/// [`Span::col`]: crate::Span::col
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct Origin<'a> {
    /// The origin file, or `None` for the root document.
    pub file: Option<&'a str>,

    /// 1-based line within `file`.
    pub line: usize,

    /// 1-based column (Unicode scalar values) within the origin line, or `None`
    /// when the preprocessor rewrote the line so the column cannot be mapped
    /// back. See the type-level documentation.
    pub col: Option<usize>,

    /// How the preprocessed line relates to its origin line.
    pub fidelity: Fidelity,
}

/// Describes how a preprocessed line relates to the origin line it maps to, so
/// a consumer can tell whether a column (and the line content itself) can be
/// trusted to match the original file.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum Fidelity {
    /// The preprocessed line is byte-for-byte identical to the origin line. Its
    /// line and column map straight back to the original file.
    Verbatim,

    /// The preprocessed line corresponds to a real origin line, but the
    /// preprocessor changed its content (the named [`Transform`]), so the line
    /// still maps but the column does not.
    Transformed(Transform),

    /// The preprocessed line has no verbatim origin line: the preprocessor
    /// generated it (the named [`Transform`]). The reported line points at the
    /// directive that produced it, as a best-effort anchor.
    Synthetic(Transform),
}

/// Identifies which preprocessor transform is responsible for a non-verbatim
/// line. Informational: it tells a consumer *why* a column is unavailable.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum Transform {
    /// Tabs were expanded to spaces per the `tabsize` attribute.
    TabExpansion,

    /// Leading indentation was normalized per the `indent` attribute.
    Reindent,

    /// A synthetic `:leveloffset:` attribute entry wrapping an include.
    LevelOffsetWrapper,

    /// A rewrite of an `include::` directive into a `link:` macro: applied to
    /// every target at `SafeMode::Secure` and above, and to a remote (URI)
    /// target below secure when `allow-uri-read` is unset.
    SecureLinkRewrite,

    /// A synthetic "Unresolved directive" line replacing an include that could
    /// not be resolved.
    UnresolvedDirective,

    /// The line was otherwise rewritten so its columns no longer align with the
    /// origin: an escaped directive with its leading backslash removed, or the
    /// spliced-in content of a single-line conditional.
    Rewritten,
}

impl SourceMap {
    pub(crate) fn append(
        &mut self,
        output_line: usize,
        file: Option<&str>,
        source_line: usize,
        fidelity: Fidelity,
    ) {
        let file = self.intern(file);

        // Segments must be appended in non-decreasing `output_line` order:
        // `resolve` binary-searches `segments` by `output_line`, which silently
        // returns garbage on an unsorted slice. Lock that invariant here so an
        // out-of-order call site fails loudly in debug builds rather than
        // corrupting every downstream origin lookup.
        debug_assert!(
            self.segments
                .last()
                .is_none_or(|last| output_line >= last.output_line),
            "SourceMap::append called out of order: output_line {output_line} follows {}",
            self.segments.last().map_or(0, |last| last.output_line),
        );

        self.segments.push(Segment {
            output_line,
            file,
            source_line,
            fidelity,
        });
    }

    /// Intern an origin file name, returning its id. `None` (the root document)
    /// is represented directly and interns nothing.
    fn intern(&mut self, file: Option<&str>) -> Option<u32> {
        let name = file?;

        if let Some(i) = self.files.iter().position(|f| f == name) {
            return Some(i as u32);
        }

        let id = self.files.len() as u32;
        self.files.push(name.to_owned());
        Some(id)
    }

    /// Resolve the segment covering preprocessed line `key`, returning the
    /// origin file id, origin line, and fidelity. A `key` before the first
    /// segment (or an empty map) maps to the root document, verbatim, at the
    /// same line number.
    fn resolve(&self, key: usize) -> (Option<u32>, usize, Fidelity) {
        // The exact match and the segment-before-`key` cases share one formula
        // (`source_line + key - output_line`, which is `source_line` on an exact
        // match). A `key` before the first segment has no governing segment.
        let segment = match self.segments.binary_search_by_key(&key, |s| s.output_line) {
            Ok(i) => self.segments.get(i),
            Err(0) => None,
            Err(i) => self.segments.get(i - 1),
        };

        match segment {
            Some(s) => (s.file, s.source_line + key - s.output_line, s.fidelity),
            None => (None, key, Fidelity::Verbatim),
        }
    }

    /// Reconstruct the anchor segments as `(output_line, file, source_line)`
    /// tuples, in order. Used by the test fixtures to compare an observed map
    /// against an expected one (fidelity is not compared there).
    #[cfg(test)]
    pub(crate) fn anchors(&self) -> impl Iterator<Item = (usize, Option<&str>, usize)> {
        self.segments
            .iter()
            .map(|s| (s.output_line, self.file_name(s.file), s.source_line))
    }

    /// Resolve an interned file id to its name.
    fn file_name(&self, id: Option<u32>) -> Option<&str> {
        id.and_then(|i| self.files.get(i as usize))
            .map(String::as_str)
    }

    /// Given a 1-based line number in the preprocessed source file, translate
    /// that to a file name and line number as original inputs to the parsing
    /// process.
    ///
    /// This is line-granular only; use [`origin_at`](Self::origin_at) or
    /// [`origin_of`](Self::origin_of) to also recover a column (on verbatim
    /// lines) and the [`Fidelity`] of the mapping.
    pub fn original_file_and_line(&self, key: usize) -> Option<SourceLine> {
        let (file, source_line, _) = self.resolve(key);
        Some(SourceLine(
            self.file_name(file).map(str::to_owned),
            source_line,
        ))
    }

    /// Translate a 1-based (line, column) position in the preprocessed source
    /// back to its [`Origin`] in the original input files.
    ///
    /// `col` counts Unicode scalar values, as [`Span::col`] does. It is carried
    /// through to [`Origin::col`] only when the line is [`Fidelity::Verbatim`];
    /// otherwise [`Origin::col`] is `None`. See [`Origin`] for the column-unit
    /// contract.
    ///
    /// [`Span::col`]: crate::Span::col
    pub fn origin_at(&self, line: usize, col: usize) -> Origin<'_> {
        let (file, source_line, fidelity) = self.resolve(line);

        Origin {
            file: self.file_name(file),
            line: source_line,
            col: matches!(fidelity, Fidelity::Verbatim).then_some(col),
            fidelity,
        }
    }

    /// Translate the start of `span` back to its [`Origin`] in the original
    /// input files. Convenience for `origin_at(span.line(), span.col())`.
    pub fn origin_of(&self, span: Span<'_>) -> Origin<'_> {
        self.origin_at(span.line(), span.col())
    }
}

impl fmt::Debug for SourceMap {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("SourceMap(&")?;
        f.debug_list()
            .entries(self.segments.iter().map(|s| {
                (
                    s.output_line,
                    SourceLine(self.file_name(s.file).map(str::to_owned), s.source_line),
                    s.fidelity,
                )
            }))
            .finish()?;
        f.write_str(")")
    }
}

#[cfg(test)]
mod tests {
    #![allow(clippy::unwrap_used)]

    use crate::parser::{
        SourceLine, SourceMap,
        source_map::{Fidelity, Transform},
    };

    fn append(sm: &mut SourceMap, output_line: usize, file: Option<&str>, source_line: usize) {
        sm.append(output_line, file, source_line, Fidelity::Verbatim);
    }

    #[test]
    fn empty() {
        let sm = SourceMap::default();
        assert_eq!(sm.original_file_and_line(1), Some(SourceLine(None, 1)));
    }

    #[test]
    fn one_entry() {
        let mut sm = SourceMap::default();
        append(&mut sm, 1, None, 1);

        assert_eq!(sm.original_file_and_line(0), Some(SourceLine(None, 0)));
        assert_eq!(sm.original_file_and_line(1), Some(SourceLine(None, 1)));
        assert_eq!(sm.original_file_and_line(4), Some(SourceLine(None, 4)));

        assert_eq!(
            sm.original_file_and_line(4000),
            Some(SourceLine(None, 4000))
        );
    }

    #[test]
    fn multiple_entries() {
        let mut sm = SourceMap::default();
        append(&mut sm, 1, None, 1);
        append(&mut sm, 10, Some("foo.adoc"), 1);
        append(&mut sm, 20, Some("bar.adoc"), 18);
        append(&mut sm, 30, None, 11);

        assert_eq!(sm.original_file_and_line(1), Some(SourceLine(None, 1)));
        assert_eq!(sm.original_file_and_line(4), Some(SourceLine(None, 4)));

        assert_eq!(
            sm.original_file_and_line(10),
            Some(SourceLine(Some("foo.adoc".to_owned()), 1))
        );
        assert_eq!(
            sm.original_file_and_line(19),
            Some(SourceLine(Some("foo.adoc".to_owned()), 10))
        );

        assert_eq!(
            sm.original_file_and_line(20),
            Some(SourceLine(Some("bar.adoc".to_owned()), 18))
        );
        assert_eq!(
            sm.original_file_and_line(21),
            Some(SourceLine(Some("bar.adoc".to_owned()), 19))
        );
        assert_eq!(
            sm.original_file_and_line(29),
            Some(SourceLine(Some("bar.adoc".to_owned()), 27))
        );

        assert_eq!(sm.original_file_and_line(30), Some(SourceLine(None, 11)));
        assert_eq!(sm.original_file_and_line(40), Some(SourceLine(None, 21)));
    }

    #[test]
    fn interns_repeated_file_names() {
        let mut sm = SourceMap::default();
        append(&mut sm, 1, Some("foo.adoc"), 1);
        append(&mut sm, 5, Some("foo.adoc"), 10);
        append(&mut sm, 9, Some("foo.adoc"), 20);

        // The same file name is stored once regardless of how many segments
        // reference it.
        assert_eq!(sm.files, vec!["foo.adoc".to_owned()]);

        assert_eq!(
            sm.original_file_and_line(6),
            Some(SourceLine(Some("foo.adoc".to_owned()), 11))
        );
    }

    #[test]
    fn origin_at_reports_column_only_when_verbatim() {
        let mut sm = SourceMap::default();
        sm.append(1, None, 1, Fidelity::Verbatim);
        sm.append(
            2,
            Some("inc.adoc"),
            4,
            Fidelity::Transformed(Transform::TabExpansion),
        );
        sm.append(3, Some("inc.adoc"), 5, Fidelity::Verbatim);

        let verbatim = sm.origin_at(1, 7);
        assert_eq!(verbatim.file, None);
        assert_eq!(verbatim.line, 1);
        assert_eq!(verbatim.col, Some(7));
        assert_eq!(verbatim.fidelity, Fidelity::Verbatim);

        let transformed = sm.origin_at(2, 7);
        assert_eq!(transformed.file, Some("inc.adoc"));
        assert_eq!(transformed.line, 4);
        assert_eq!(transformed.col, None);
        assert_eq!(
            transformed.fidelity,
            Fidelity::Transformed(Transform::TabExpansion)
        );

        let after = sm.origin_at(3, 2);
        assert_eq!(after.file, Some("inc.adoc"));
        assert_eq!(after.line, 5);
        assert_eq!(after.col, Some(2));
    }

    #[test]
    #[cfg(debug_assertions)]
    #[should_panic(expected = "SourceMap::append called out of order")]
    fn append_out_of_order_panics_in_debug() {
        let mut sm = SourceMap::default();
        append(&mut sm, 10, None, 1);

        // An earlier `output_line` than the last segment breaks the ordering
        // that `resolve`'s binary search relies on, so it must fail loudly.
        append(&mut sm, 5, None, 1);
    }

    #[test]
    fn append_equal_output_line_is_allowed() {
        let mut sm = SourceMap::default();
        append(&mut sm, 1, None, 1);

        // Equal `output_line` keeps the slice sorted, so it is permitted.
        sm.append(1, None, 1, Fidelity::Verbatim);
    }

    #[test]
    fn impl_debug() {
        let mut sm = SourceMap::default();
        append(&mut sm, 1, None, 1);

        assert_eq!(
            format!("{sm:#?}"),
            "SourceMap(&[\n    (\n        1,\n        SourceLine(\n            None,\n            1,\n        ),\n        Verbatim,\n    ),\n])"
        );
    }
}