caixa_ast/

span.rs

//! Byte-offset spans — minimal and cheap. Line/column are computed on demand.

use std::fmt;

use serde::{Deserialize, Serialize};

/// A half-open byte range `[start, end)` into some source string.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default, Serialize, Deserialize)]
pub struct Span {
    pub start: u32,
    pub end: u32,
}

impl Span {
    #[must_use]
    pub const fn new(start: u32, end: u32) -> Self {
        Self { start, end }
    }

    #[must_use]
    pub const fn point(offset: u32) -> Self {
        Self {
            start: offset,
            end: offset,
        }
    }

    /// Byte-width of the half-open range `[start, end)`. `pub const fn` —
    /// `u32::saturating_sub` is const-stable since Rust 1.47, well before
    /// this workspace's 1.89 MSRV floor, so the promotion is a body-
    /// preserving type-signature widening. Matches the sibling
    /// [`Self::new`] / [`Self::point`] / [`Self::contains`] /
    /// [`Self::union`] `pub const fn` shape on the same [`Span`] primitive
    /// — every downstream consumer that wants a compile-time span-width
    /// fixture (a `const WIDTH: u32 = SPAN.len();` LSP hover-registry
    /// entry, a per-diagnostic const-context width oracle a future
    /// admission webhook consults, a compile-time span-partition truth
    /// table the caixa-fmt trivia-owner resolver keys off) now reads
    /// through one substrate-primitive const dispatch rather than being
    /// forced onto the runtime code path.
    #[must_use]
    pub const fn len(self) -> u32 {
        self.end.saturating_sub(self.start)
    }

    /// Half-open emptiness predicate — `true` iff `self.start == self.end`.
    /// `pub const fn` — folds onto the sibling [`Self::len`] `pub const
    /// fn` promotion (integer equality is const in Rust since long before
    /// this workspace's 1.89 MSRV floor). Matches every other accessor /
    /// predicate on this [`Span`] primitive's const-eval surface; only
    /// the fundamentally-runtime-only `slice(&str)` method (string-slice
    /// indexing outside const-eval) remains `pub fn`.
    #[must_use]
    pub const fn is_empty(self) -> bool {
        self.len() == 0
    }

    /// The smallest span covering both. Useful for building a list node's
    /// span from its children — every parser code path that composes a
    /// parent span from its immediate child boundaries reads through this
    /// (`open.union(close)` on a delimited list, `head.union(target.span)`
    /// on a quote-form target, and every downstream trivia-owner /
    /// diagnostic-aggregator / fmt-region parent-span builder). `pub const
    /// fn` — the body reaches for `u32::min` / `u32::max`, both const
    /// stable since Rust 1.83 (well before this workspace's 1.89 MSRV
    /// floor), so the promotion is a body-preserving type-signature
    /// widening. Matches the sibling [`Self::new`] / [`Self::point`] /
    /// [`Self::contains`] `pub const fn` shape on the same [`Span`]
    /// primitive — every downstream consumer that wants a compile-time
    /// span-composition fixture (a `const OUTER: Span = INNER1.union(
    /// INNER2);` LSP hover-registry entry, a per-diagnostic const-context
    /// parent-span oracle a future admission webhook consults, a
    /// compile-time span-partition truth table the caixa-fmt trivia-owner
    /// resolver keys off) now reads through one substrate-primitive const
    /// dispatch rather than being forced onto the runtime code path.
    #[must_use]
    pub const fn union(self, other: Span) -> Span {
        // Body-preserving `Ord::min` / `Ord::max` open-coding: the trait
        // dispatch is not yet stable in `const` context (rust-lang/rust
        // #143874), so the pub-const-fn promotion reads through inline
        // `if`/`else` on the same `u32 < u32` / `u32 > u32` comparisons
        // the primitive-integer inherent methods lower to.
        let start = if self.start < other.start {
            self.start
        } else {
            other.start
        };
        let end = if self.end > other.end {
            self.end
        } else {
            other.end
        };
        Span { start, end }
    }

    #[must_use]
    pub fn slice<'a>(self, src: &'a str) -> &'a str {
        let start = self.start as usize;
        let end = self.end as usize;
        if start >= src.len() {
            ""
        } else {
            let end = end.min(src.len());
            &src[start..end]
        }
    }

    /// Byte-offset half-open containment predicate every consumer that
    /// keys off an author-authored source position (LSP hover
    /// span-lookup at the cursor, per-diagnostic span-registry probe,
    /// per-trivia leading/trailing-owner attachment gate) reads through
    /// — returns `true` iff `offset` lies inside the half-open range
    /// `[self.start, self.end)`. `pub const fn` — matches the sibling
    /// [`Self::new`] / [`Self::point`] `pub const fn` shape on the same
    /// [`Span`] primitive's construction axis, extending the const-eval
    /// surface onto the primitive's containment-predicate axis without
    /// a body change (integer comparison is const in Rust since long
    /// before this workspace's 1.89 MSRV floor). Every downstream
    /// consumer that wants a compile-time span-containment fixture —
    /// a `const IS_INSIDE: bool = SPAN.contains(OFFSET);` LSP hover-
    /// registry entry, a per-diagnostic const-context span oracle a
    /// future admission webhook consults, a compile-time span-partition
    /// truth table the caixa-fmt trivia-owner resolver keys off — now
    /// reads through one substrate-primitive const dispatch rather than
    /// being forced onto the runtime code path.
    #[must_use]
    pub const fn contains(self, offset: u32) -> bool {
        offset >= self.start && offset < self.end
    }
}

impl fmt::Display for Span {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}..{}", self.start, self.end)
    }
}

/// 1-indexed line/column pair — what humans see in editors.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct Position {
    pub line: u32,
    pub column: u32,
}

impl Position {
    /// Substrate-primitive constructor every producer of a
    /// 1-indexed line/column pair reads through — folds the two-slot
    /// `Position { line, column }` struct-literal wire-up (the sole
    /// production emitter [`line_column`]'s tail, plus every
    /// per-fixture line/column literal in the sibling test module)
    /// onto one `pub const fn` dispatch. Matches the sibling
    /// [`Span::new`] / [`Span::point`] `pub const fn` shape on the
    /// same caixa-ast source-position primitive family; every
    /// downstream LSP hover-registry / diagnostic emitter / future
    /// position-carrying trivia-registry that wants a compile-time
    /// position fixture (a `const AT: Position = Position::new(1, 4);`
    /// LSP hover-oracle default, a per-diagnostic const-context
    /// leading-position fixture, a compile-time position-partition
    /// truth table the caixa-fmt trivia-owner resolver keys off)
    /// now reaches through one substrate-primitive const dispatch
    /// rather than duplicating the two-slot struct literal at every
    /// construction site.
    #[must_use]
    pub const fn new(line: u32, column: u32) -> Self {
        Self { line, column }
    }

    /// Canonical origin — line 1, column 1, matching the
    /// [`line_column`] convention (both axes 1-indexed). `pub const
    /// fn` — the shape materialises at compile time so a future
    /// const-context consumer (a substrate-wide `const ORIGIN:
    /// Position = Position::origin();` LSP hover-oracle default, a
    /// per-diagnostic const-context leading-position fixture that
    /// today reaches for the `(1, 1)` magic pair inline) reads
    /// through one substrate-primitive const dispatch rather than
    /// duplicating the `(1, 1)` origin literal at every consumer.
    #[must_use]
    pub const fn origin() -> Self {
        Self::new(1, 1)
    }
}

impl fmt::Display for Position {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}:{}", self.line, self.column)
    }
}

/// Compute (line, column) for a byte offset. Line and column are 1-indexed.
/// O(offset); fine for diagnostics, not for hot paths.
///
/// `pub const fn` — closes the const-eval discipline on the caixa-ast
/// source-position primitive family. The pre-lift body iterated
/// [`str::char_indices`], whose iterator methods are not yet const-
/// stable (rust-lang/rust #143874, the same tracking issue [`Span::union`]
/// open-codes `Ord::min` / `Ord::max` around). The const-lift trades the
/// char-boundary iterator for a manual `while` walk over the src's raw
/// [`str::as_bytes`] (`pub const fn` since Rust 1.32, well before this
/// workspace's 1.89 MSRV floor) that keys off two facts every `&str`
/// carries by construction:
///
/// - **`\n` is ASCII.** Byte `0x0A` is a 1-byte UTF-8 codepoint and
///   never appears as a continuation byte of a multi-byte codepoint (a
///   continuation byte lies in `0x80..0xC0`). Every line boundary in a
///   `&str` therefore surfaces as a lone `b'\n'` at exactly one byte
///   position, so the line-count decision matches the pre-lift
///   `char_indices` walk verbatim.
/// - **A char boundary is a non-continuation byte.** Every codepoint
///   start byte lies in `0x00..0x80` (ASCII) or `0xC0..` (multi-byte
///   lead); continuation bytes lie in `0x80..0xC0`. Column-counting
///   therefore matches the pre-lift walk by advancing `col` only on
///   non-continuation bytes.
///
/// Semantic-preserving across every fixture the sibling
/// [`tests::line_column_handles_newlines`] pins on ASCII input, plus
/// the added [`tests::line_column_is_const_across_ascii_and_utf8`]
/// UTF-8 sweep (a 2-byte `é` and a 4-byte `😀` fixture, both of which
/// the byte-role decision correctly folds onto one column advance per
/// codepoint start byte, matching the pre-lift `char_indices` walk).
///
/// The offset clamp mirrors the pre-lift `break` on `i >= offset`: when
/// `offset` falls beyond the src end, the walk stops at the last byte
/// rather than reading past it; when `offset` falls in the middle of a
/// multi-byte codepoint, the walk stops before the codepoint's start
/// byte would be counted, matching the pre-lift arm that consumed no
/// char whose start byte index was `>= offset`.
#[must_use]
pub const fn line_column(src: &str, offset: u32) -> Position {
    let mut line: u32 = 1;
    let mut col: u32 = 1;
    let offset = offset as usize;
    let bytes = src.as_bytes();
    let end = if offset < bytes.len() {
        offset
    } else {
        bytes.len()
    };
    let mut i = 0;
    while i < end {
        let b = bytes[i];
        if b == b'\n' {
            line += 1;
            col = 1;
        } else if b < 0x80 || b >= 0xC0 {
            // ASCII byte (0x00..0x80) or multi-byte codepoint lead
            // (0xC0..) — advances the column by one, matching
            // one char in the pre-lift `char_indices` walk. A
            // continuation byte (0x80..0xC0) belongs to a codepoint
            // that has already been counted at its lead byte and
            // must not re-advance `col`.
            col += 1;
        }
        i += 1;
    }
    Position::new(line, col)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn point_span_is_empty() {
        let s = Span::point(5);
        assert!(s.is_empty());
        assert_eq!(s.len(), 0);
    }

    #[test]
    fn union_widens() {
        let a = Span::new(2, 5);
        let b = Span::new(4, 9);
        let u = a.union(b);
        assert_eq!(u.start, 2);
        assert_eq!(u.end, 9);
    }

    #[test]
    fn union_is_const() {
        // Pin the const-eval surface: the substrate-primitive parent-span
        // builder reaches into `const` context, so a future compile-time
        // parser-fixture / diagnostic-aggregator / fmt-region template
        // can build a `const OUTER: Span = INNER1.union(INNER2);` without
        // being forced onto the runtime code path. The four
        // `const _: () = assert!(…)` bindings resolve the composition at
        // compile time — any regression that drops `pub const fn` back
        // to `pub fn` (a body edit that reaches for a non-const
        // operation) fails this test at compile time rather than at
        // runtime, matching the sibling `Span::new` / `Span::point` /
        // `Span::contains` `pub const fn` shape's const-eval discipline.
        const A: Span = Span::new(2, 5);
        const B: Span = Span::new(4, 9);
        const U: Span = A.union(B);
        const _: () = assert!(U.start == 2);
        const _: () = assert!(U.end == 9);
        // Half-open containment on the const-composed parent span keys
        // through `Span::contains`'s own `pub const fn` promotion — so
        // both const-eval surfaces (composition and containment) resolve
        // in one compile-time expression, matching the [start, end)
        // boundary discipline the sibling `contains_is_const` fixture
        // already pins.
        const _: () = assert!(U.contains(2));
        const _: () = assert!(!U.contains(9));
    }

    #[test]
    fn slice_extracts_substring() {
        let src = "hello world";
        assert_eq!(Span::new(6, 11).slice(src), "world");
    }

    #[test]
    fn line_column_handles_newlines() {
        let src = "abc\ndef\nghi";
        assert_eq!(line_column(src, 0), Position::origin());
        assert_eq!(line_column(src, 4), Position::new(2, 1));
        assert_eq!(line_column(src, 9), Position::new(3, 2));
    }

    #[test]
    fn contains_is_half_open() {
        let s = Span::new(3, 7);
        assert!(!s.contains(2));
        assert!(s.contains(3));
        assert!(s.contains(6));
        assert!(!s.contains(7));
    }

    #[test]
    fn len_and_is_empty_are_const() {
        // Pin the const-eval surface: the substrate-primitive width
        // accessor and emptiness predicate reach into `const` context, so
        // a future compile-time span-registry / LSP hover-oracle /
        // trivia-owner truth-table fixture can key off `Span::len` /
        // `Span::is_empty` without being forced onto the runtime code
        // path. Any regression that drops `pub const fn` back to `pub fn`
        // (a body edit that reaches for a non-const operation) fails this
        // test at compile time rather than at runtime, matching the
        // sibling `Span::new` / `Span::point` / `Span::contains` /
        // `Span::union` `pub const fn` shape's const-eval discipline.
        const RANGE: Span = Span::new(3, 7);
        const POINT: Span = Span::point(5);
        const RANGE_LEN: u32 = RANGE.len();
        const POINT_LEN: u32 = POINT.len();
        const RANGE_EMPTY: bool = RANGE.is_empty();
        const POINT_EMPTY: bool = POINT.is_empty();
        const _: () = assert!(RANGE_LEN == 4);
        const _: () = assert!(POINT_LEN == 0);
        const _: () = assert!(!RANGE_EMPTY);
        const _: () = assert!(POINT_EMPTY);
        // Saturating-sub floor: an inverted (end < start) fixture must
        // clamp to 0 at compile time, matching the runtime
        // `u32::saturating_sub` semantics the pre-lift body carried.
        const INVERTED: Span = Span::new(9, 2);
        const INVERTED_LEN: u32 = INVERTED.len();
        const INVERTED_EMPTY: bool = INVERTED.is_empty();
        const _: () = assert!(INVERTED_LEN == 0);
        const _: () = assert!(INVERTED_EMPTY);
    }

    #[test]
    fn position_new_and_origin_are_const() {
        // Pin the const-eval surface on the substrate-primitive
        // 1-indexed line/column pair: the constructor and canonical
        // origin reach into `const` context, so a future compile-time
        // LSP hover-registry / diagnostic-emitter / trivia-owner
        // truth-table fixture can key off `Position::new` /
        // `Position::origin` without being forced onto the runtime
        // code path. Any regression that drops `pub const fn` back to
        // `pub fn` (a body edit that reaches for a non-const
        // operation) fails this test at compile time rather than at
        // runtime, matching the sibling `Span::new` / `Span::point` /
        // `Span::contains` / `Span::union` / `Span::len` /
        // `Span::is_empty` `pub const fn` shape's const-eval
        // discipline on the same caixa-ast source-position primitive
        // family.
        //
        // Also pins `Position::origin`'s canonical (1, 1) shape at
        // compile time — a future accidental drift (an `origin` that
        // returns `Position::new(0, 0)` on a well-meaning "zero-
        // indexed origin" rewrite that forgets `line_column` emits
        // 1-indexed positions) trips at build time rather than
        // surfacing far from the origin declaration at some
        // downstream diagnostic-emitter's off-by-one row report.
        const AT: Position = Position::new(2, 4);
        const ORIGIN: Position = Position::origin();
        const AT_LINE: u32 = AT.line;
        const AT_COLUMN: u32 = AT.column;
        const ORIGIN_LINE: u32 = ORIGIN.line;
        const ORIGIN_COLUMN: u32 = ORIGIN.column;
        const _: () = assert!(AT_LINE == 2);
        const _: () = assert!(AT_COLUMN == 4);
        const _: () = assert!(ORIGIN_LINE == 1);
        const _: () = assert!(ORIGIN_COLUMN == 1);
    }

    #[test]
    fn line_column_is_const_across_ascii_and_utf8() {
        // Pin the const-eval surface on the last unlifted method of the
        // caixa-ast source-position primitive family: `line_column`
        // reaches into `const` context, so a future compile-time
        // diagnostic-emitter / LSP hover-registry / trivia-owner
        // truth-table fixture can key off `line_column` without being
        // forced onto the runtime code path. Any regression that drops
        // `pub const fn` back to `pub fn` (a body edit that reaches for
        // a non-const iterator like `str::char_indices`) fails this test
        // at compile time rather than at runtime, matching the sibling
        // `Span::new` / `Span::point` / `Span::contains` / `Span::union`
        // / `Span::len` / `Span::is_empty` / `Position::new` /
        // `Position::origin` `pub const fn` shape's const-eval discipline
        // on the same caixa-ast source-position primitive family.
        //
        // The ASCII arm matches the sibling `line_column_handles_newlines`
        // fixture verbatim, resolved at compile time.
        const ASCII: &str = "abc\ndef\nghi";
        const ASCII_ORIGIN: Position = line_column(ASCII, 0);
        const ASCII_ROW_2: Position = line_column(ASCII, 4);
        const ASCII_ROW_3: Position = line_column(ASCII, 9);
        const _: () = assert!(ASCII_ORIGIN.line == 1 && ASCII_ORIGIN.column == 1);
        const _: () = assert!(ASCII_ROW_2.line == 2 && ASCII_ROW_2.column == 1);
        const _: () = assert!(ASCII_ROW_3.line == 3 && ASCII_ROW_3.column == 2);
        // Offset clamp: an offset beyond the src end falls onto the last
        // byte, matching the pre-lift `break` on the exhausted iterator.
        const ASCII_PAST_END: Position = line_column(ASCII, 100);
        const _: () = assert!(ASCII_PAST_END.line == 3 && ASCII_PAST_END.column == 4);

        // UTF-8 arm: the byte-role logic (advance `col` only on non-
        // continuation bytes, `b < 0x80 || b >= 0xC0`) folds every
        // multi-byte codepoint onto exactly one column advance, matching
        // the pre-lift `char_indices` walk. `é` is 2 bytes (`0xC3 0xA9`);
        // `😀` is 4 bytes (`0xF0 0x9F 0x98 0x80`).
        //
        // Fixture: "h" (0x68) at byte 0, "é" (0xC3 0xA9) at bytes 1..3,
        // "l" (0x6C) at byte 3, "l" (0x6C) at byte 4, "o" (0x6F) at byte 5.
        const UTF8_TWO_BYTE: &str = "héllo";
        const UTF8_TWO_BYTE_AFTER_H: Position = line_column(UTF8_TWO_BYTE, 1);
        const UTF8_TWO_BYTE_MID_E_ACUTE: Position = line_column(UTF8_TWO_BYTE, 2);
        const UTF8_TWO_BYTE_AFTER_E_ACUTE: Position = line_column(UTF8_TWO_BYTE, 3);
        const UTF8_TWO_BYTE_END: Position = line_column(UTF8_TWO_BYTE, 100);
        // After "h" (1 codepoint): column 2.
        const _: () = assert!(UTF8_TWO_BYTE_AFTER_H.line == 1 && UTF8_TWO_BYTE_AFTER_H.column == 2);
        // Offset 2 falls one byte after `é`'s lead byte (offset 1),
        // so the codepoint has already been counted at its lead byte
        // — matches the pre-lift `char_indices` arm that consumed
        // every char whose start-index was `< offset`. Column 3
        // = "after h and é" — the mid-codepoint continuation-byte
        // position resolves to the same 1-indexed column the lead-
        // byte-adjacent position would.
        const _: () =
            assert!(UTF8_TWO_BYTE_MID_E_ACUTE.line == 1 && UTF8_TWO_BYTE_MID_E_ACUTE.column == 3);
        // After "hé" (2 codepoints): column 3, byte-equal to the mid-
        // continuation-byte case above — the codepoint boundary at
        // byte 3 lands on the same 1-indexed column the walk reached
        // after crossing `é`'s lead byte at byte 1.
        const _: () = assert!(
            UTF8_TWO_BYTE_AFTER_E_ACUTE.line == 1 && UTF8_TWO_BYTE_AFTER_E_ACUTE.column == 3
        );
        // Past-end clamp on UTF-8 input: 5 codepoints total, column 6.
        const _: () = assert!(UTF8_TWO_BYTE_END.line == 1 && UTF8_TWO_BYTE_END.column == 6);

        // Fixture: "😀" (0xF0 0x9F 0x98 0x80) at bytes 0..4, space at 4,
        // "n" at 5.
        const UTF8_FOUR_BYTE: &str = "😀 nice";
        const UTF8_FOUR_BYTE_AFTER_EMOJI: Position = line_column(UTF8_FOUR_BYTE, 4);
        const UTF8_FOUR_BYTE_AFTER_SPACE: Position = line_column(UTF8_FOUR_BYTE, 5);
        // After "😀" (1 codepoint on a 4-byte sequence): column 2.
        const _: () =
            assert!(UTF8_FOUR_BYTE_AFTER_EMOJI.line == 1 && UTF8_FOUR_BYTE_AFTER_EMOJI.column == 2);
        // After "😀 " (2 codepoints): column 3.
        const _: () =
            assert!(UTF8_FOUR_BYTE_AFTER_SPACE.line == 1 && UTF8_FOUR_BYTE_AFTER_SPACE.column == 3);

        // Newline crossing a multi-byte codepoint boundary: "😀\n😀".
        // Byte layout: 0..4 = 😀, 4 = '\n', 5..9 = 😀. Offset 5 lands at
        // line 2 column 1 (start of the second codepoint).
        const UTF8_ACROSS_NEWLINE: &str = "😀\n😀";
        const UTF8_ACROSS_NEWLINE_ROW_2: Position = line_column(UTF8_ACROSS_NEWLINE, 5);
        const _: () =
            assert!(UTF8_ACROSS_NEWLINE_ROW_2.line == 2 && UTF8_ACROSS_NEWLINE_ROW_2.column == 1);
    }

    #[test]
    fn contains_is_const() {
        // Pin the const-eval surface: the substrate-primitive
        // containment predicate reaches into `const` context, so a
        // future compile-time span-registry / LSP hover-oracle /
        // trivia-owner truth-table fixture can key off `Span::contains`
        // without being forced onto the runtime code path. The four
        // `const _: () = assert!(…)` bindings resolve the predicate at
        // compile time — any regression that drops `pub const fn` back
        // to `pub fn` (a body edit that reaches for a non-const
        // operation) fails this test at compile time rather than at
        // runtime, matching the sibling `Span::new` / `Span::point`
        // `pub const fn` shape's const-eval discipline.
        const SPAN: Span = Span::new(3, 7);
        const _: () = assert!(!SPAN.contains(2));
        const _: () = assert!(SPAN.contains(3));
        const _: () = assert!(SPAN.contains(5));
        const _: () = assert!(!SPAN.contains(7));
    }
}