oneyaml_core/
line_index.rs

1//! [`LineIndex`]: UTF-8 byte offsets to lines and columns.
2
3/// The unit a column is counted in.
4#[non_exhaustive]
5#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
6pub enum ColumnUnit {
7    /// UTF-8 bytes (what [`crate::Span`]s count).
8    Utf8,
9    /// Unicode scalar values (`char`s), as editors usually show them.
10    Char,
11    /// UTF-16 code units (the Language Server Protocol's default).
12    Utf16,
13}
14
15/// A 0-based line and column; the column is in the [`ColumnUnit`] asked
16/// for.
17#[non_exhaustive]
18#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
19pub struct LineCol {
20    /// 0-based line.
21    pub line: usize,
22    /// 0-based column.
23    pub column: usize,
24}
25
26impl LineCol {
27    /// A 0-based line and column (`#[non_exhaustive]`: fields may be
28    /// added, so build it here).
29    #[must_use]
30    pub const fn new(line: usize, column: usize) -> Self {
31        Self { line, column }
32    }
33}
34
35/// A multi-byte character: where it starts, its UTF-8 length, and the
36/// running totals up to and including it of the bytes it has beyond one
37/// `char` and beyond its UTF-16 length.
38#[derive(Clone, Debug, PartialEq, Eq, Hash)]
39struct Wide {
40    at: usize,
41    len: usize,
42    extra_chars: usize,
43    extra_utf16: usize,
44}
45
46/// Line starts of one source text, to turn UTF-8 byte offsets (the unit
47/// of every [`crate::Span`]) into line/column positions in UTF-8 bytes,
48/// `char`s, or UTF-16 code units.
49///
50/// Built once in O(n); each lookup is O(log n) (binary searches over the
51/// line starts and the multi-byte characters), whatever the line length.
52/// Line breaks are `\n`, `\r\n`, and a lone `\r` (YAML 1.2.2 §5.4). An
53/// offset past the end, or inside a multi-byte character, has no position
54/// (`None`); nothing here panics.
55///
56/// ```
57/// use oneyaml_core::{ColumnUnit, LineCol, LineIndex};
58///
59/// let src = "a: 1\nb: \u{e9}\u{1F600}x\n";
60/// let idx = LineIndex::new(src);
61/// let x = src.find('x').unwrap();
62/// assert_eq!(idx.line_col(x, ColumnUnit::Utf8), Some(LineCol::new(1, 9)));
63/// assert_eq!(idx.line_col(x, ColumnUnit::Char), Some(LineCol::new(1, 5)));
64/// assert_eq!(idx.line_col(x, ColumnUnit::Utf16), Some(LineCol::new(1, 6)));
65/// assert_eq!(idx.line_col(x - 1, ColumnUnit::Char), None); // inside the emoji
66/// assert_eq!(idx.line_col(src.len() + 1, ColumnUnit::Char), None);
67/// // A text ending in a line break has an empty last line.
68/// assert_eq!(idx.line_count(), 3);
69/// assert_eq!(idx.line_start(1), Some(5));
70/// assert_eq!(idx.line_start(3), None);
71/// ```
72#[derive(Clone, Debug, PartialEq, Eq, Hash)]
73pub struct LineIndex {
74    /// Byte offset of each line's start; the first is 0.
75    starts: Vec<usize>,
76    /// Every multi-byte character, in order.
77    wide: Vec<Wide>,
78    len: usize,
79}
80
81impl LineIndex {
82    /// Indexes `src`.
83    #[must_use]
84    pub fn new(src: &str) -> Self {
85        let mut starts = vec![0];
86        let mut wide = Vec::new();
87        let (mut extra_chars, mut extra_utf16) = (0usize, 0usize);
88        let mut chars = src.char_indices().peekable();
89        while let Some((at, c)) = chars.next() {
90            let len = c.len_utf8();
91            let next = at.saturating_add(len);
92            match c {
93                '\n' => starts.push(next),
94                '\r' if !matches!(chars.peek(), Some((_, '\n'))) => starts.push(next),
95                _ if len > 1 => {
96                    extra_chars = extra_chars.saturating_add(len.saturating_sub(1));
97                    extra_utf16 = extra_utf16.saturating_add(len.saturating_sub(c.len_utf16()));
98                    wide.push(Wide {
99                        at,
100                        len,
101                        extra_chars,
102                        extra_utf16,
103                    });
104                }
105                _ => {}
106            }
107        }
108        Self {
109            starts,
110            wide,
111            len: src.len(),
112        }
113    }
114
115    /// The length of the indexed text, in bytes.
116    #[must_use]
117    pub fn len(&self) -> usize {
118        self.len
119    }
120
121    /// `true` for an empty text.
122    #[must_use]
123    pub fn is_empty(&self) -> bool {
124        self.len == 0
125    }
126
127    /// The number of lines (a text ending in a line break has an empty
128    /// last line).
129    #[must_use]
130    pub fn line_count(&self) -> usize {
131        self.starts.len()
132    }
133
134    /// The byte offset where 0-based line `line` starts.
135    #[must_use]
136    pub fn line_start(&self, line: usize) -> Option<usize> {
137        self.starts.get(line).copied()
138    }
139
140    /// The running totals of extra bytes (per `char`, per UTF-16 unit) of
141    /// the multi-byte characters that end at or before `offset`; `None`
142    /// when `offset` falls inside one.
143    fn extra_before(&self, offset: usize) -> Option<(usize, usize)> {
144        let n = self.wide.partition_point(|w| w.at < offset);
145        let Some(last) = n.checked_sub(1).and_then(|i| self.wide.get(i)) else {
146            return Some((0, 0));
147        };
148        if offset < last.at.saturating_add(last.len) {
149            return None;
150        }
151        Some((last.extra_chars, last.extra_utf16))
152    }
153
154    /// The position of byte `offset`, its column counted in `unit`;
155    /// `None` past the end or inside a multi-byte character. O(log n).
156    #[must_use]
157    pub fn line_col(&self, offset: usize, unit: ColumnUnit) -> Option<LineCol> {
158        if offset > self.len {
159            return None;
160        }
161        let line = self
162            .starts
163            .partition_point(|s| *s <= offset)
164            .checked_sub(1)?;
165        let start = *self.starts.get(line)?;
166        let bytes = offset.checked_sub(start)?;
167        let (at_chars, at_utf16) = self.extra_before(offset)?;
168        let (start_chars, start_utf16) = self.extra_before(start)?;
169        let column = match unit {
170            ColumnUnit::Char => bytes.checked_sub(at_chars.checked_sub(start_chars)?)?,
171            ColumnUnit::Utf16 => bytes.checked_sub(at_utf16.checked_sub(start_utf16)?)?,
172            ColumnUnit::Utf8 => bytes,
173        };
174        Some(LineCol { line, column })
175    }
176
177    /// The positions of a span's start and end (see
178    /// [`LineIndex::line_col`]).
179    #[must_use]
180    pub fn span(&self, span: crate::Span, unit: ColumnUnit) -> Option<(LineCol, LineCol)> {
181        Some((
182            self.line_col(span.start, unit)?,
183            self.line_col(span.end, unit)?,
184        ))
185    }
186}
187
188#[cfg(test)]
189mod tests {
190    #![allow(
191        clippy::unwrap_used,
192        clippy::expect_used,
193        clippy::indexing_slicing,
194        clippy::arithmetic_side_effects
195    )]
196    use super::*;
197
198    /// The naive answer, by walking the text.
199    fn naive(src: &str, offset: usize, unit: ColumnUnit) -> Option<LineCol> {
200        let before = src.get(..offset)?;
201        let (mut line, mut column) = (0usize, 0usize);
202        let mut prev_cr = false;
203        for c in before.chars() {
204            match c {
205                '\n' if prev_cr => {
206                    column = 0;
207                }
208                '\n' => {
209                    line += 1;
210                    column = 0;
211                }
212                '\r' => {
213                    line += 1;
214                    column = 0;
215                }
216                _ => {
217                    column += match unit {
218                        ColumnUnit::Utf8 => c.len_utf8(),
219                        ColumnUnit::Char => 1,
220                        ColumnUnit::Utf16 => c.len_utf16(),
221                    }
222                }
223            }
224            prev_cr = c == '\r';
225        }
226        Some(LineCol { line, column })
227    }
228
229    #[test]
230    fn agrees_with_a_walk_everywhere() {
231        let src = "a\r\nb\rc\nd\u{e9}x\u{1F600}\u{4e2d}\r\n\n\u{e9}";
232        let idx = LineIndex::new(src);
233        assert_eq!(idx.len(), src.len());
234        assert!(!idx.is_empty());
235        assert_eq!(idx.line_count(), 6);
236        for offset in 0..=src.len() + 2 {
237            for unit in [ColumnUnit::Utf8, ColumnUnit::Char, ColumnUnit::Utf16] {
238                // The `\n` of a `\r\n` belongs to the line it ends.
239                let crlf_nl = src.get(offset..).is_some_and(|r| r.starts_with('\n'))
240                    && src.get(..offset).is_some_and(|r| r.ends_with('\r'));
241                if crlf_nl {
242                    let at = idx.line_col(offset, unit).unwrap();
243                    let before = idx.line_col(offset - 1, unit).unwrap();
244                    assert_eq!(at.line, before.line);
245                    assert_eq!(at.column, before.column + 1);
246                    continue;
247                }
248                assert_eq!(
249                    idx.line_col(offset, unit),
250                    naive(src, offset, unit),
251                    "{offset} {unit:?}"
252                );
253            }
254        }
255        assert_eq!(idx.line_start(1), Some(3));
256        assert_eq!(idx.line_start(99), None);
257        let e = src.find('x').unwrap();
258        assert_eq!(
259            idx.span(crate::Span::new(e, e + 1), ColumnUnit::Char),
260            Some((
261                LineCol { line: 3, column: 2 },
262                LineCol { line: 3, column: 3 }
263            ))
264        );
265        assert_eq!(idx.span(crate::Span::new(0, 999), ColumnUnit::Char), None);
266    }
267
268    #[test]
269    fn empty_and_ascii() {
270        let idx = LineIndex::new("");
271        assert!(idx.is_empty());
272        assert_eq!(
273            idx.line_col(0, ColumnUnit::Utf16),
274            Some(LineCol { line: 0, column: 0 })
275        );
276        assert_eq!(idx.line_col(1, ColumnUnit::Utf16), None);
277        let idx = LineIndex::new("ab\n");
278        assert_eq!(
279            idx.line_col(3, ColumnUnit::Char),
280            Some(LineCol { line: 1, column: 0 })
281        );
282        assert_eq!(idx.line_col(usize::MAX, ColumnUnit::Char), None);
283    }
284}
oneyaml_core/line_index.rs

oneyaml_core/
line_index.rs
