yaml_rt_core/
source.rs

1use crate::{Diagnostic, DiagnosticKind, YamlError};
2
3/// YAML version targeted by this workspace.
4pub const TARGET_YAML_VERSION: &str = "1.2.2";
5
6/// Identifier for a node stored inside a [`crate::YamlDoc`].
7#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
8pub struct NodeId(pub u32);
9
10impl NodeId {
11    /// Creates a node ID from a vector index.
12    ///
13    /// # Panics
14    ///
15    /// Panics when `index` cannot fit in the u32-backed node ID.
16    #[must_use]
17    pub fn from_usize(index: usize) -> Self {
18        Self(u32::try_from(index).expect("node arena is too large for u32-based node IDs"))
19    }
20
21    /// Returns this node ID as a vector index.
22    #[must_use]
23    pub const fn as_usize(self) -> usize {
24        self.0 as usize
25    }
26}
27
28/// A byte span inside a [`Source`].
29#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
30pub struct Span {
31    /// Inclusive start byte offset.
32    pub start: u32,
33    /// Exclusive end byte offset.
34    pub end: u32,
35}
36
37impl Span {
38    /// Creates a new byte span.
39    #[must_use]
40    pub const fn new(start: u32, end: u32) -> Self {
41        Self { start, end }
42    }
43
44    /// Creates a span from usize byte offsets.
45    ///
46    /// # Panics
47    ///
48    /// Panics when either offset cannot fit in the u32-backed span.
49    #[must_use]
50    pub fn from_usize(start: usize, end: usize) -> Self {
51        Self::try_from((start, end)).expect("YAML source is too large for u32-based spans")
52    }
53
54    /// Returns an empty span at `offset`.
55    #[must_use]
56    pub const fn empty(offset: u32) -> Self {
57        Self {
58            start: offset,
59            end: offset,
60        }
61    }
62
63    pub(crate) fn usize_to_u32(offset: usize) -> u32 {
64        u32::try_from(offset).expect("YAML source is too large for u32-based spans")
65    }
66
67    pub(crate) fn offset_from_usize(base: u32, offset: usize) -> u32 {
68        base.checked_add(Self::usize_to_u32(offset))
69            .expect("YAML source is too large for u32-based spans")
70    }
71
72    /// Returns an empty span at `offset`.
73    #[must_use]
74    pub fn empty_from_usize(offset: usize) -> Self {
75        Self::empty(Self::usize_to_u32(offset))
76    }
77
78    /// Returns the span length in bytes.
79    #[must_use]
80    pub const fn len(self) -> u32 {
81        self.end.saturating_sub(self.start)
82    }
83
84    /// Returns true when this span covers no bytes.
85    #[must_use]
86    pub const fn is_empty(self) -> bool {
87        self.start == self.end
88    }
89
90    /// Returns true when `offset` is inside this span.
91    #[must_use]
92    pub const fn contains(self, offset: u32) -> bool {
93        self.start <= offset && offset < self.end
94    }
95}
96
97impl TryFrom<(usize, usize)> for Span {
98    type Error = std::num::TryFromIntError;
99
100    fn try_from((start, end): (usize, usize)) -> Result<Self, Self::Error> {
101        Ok(Self {
102            start: Self::usize_to_u32(start),
103            end: Self::usize_to_u32(end),
104        })
105    }
106}
107/// One-based line and column location.
108#[derive(Debug, Clone, Copy, PartialEq, Eq)]
109pub struct LineCol {
110    /// One-based line number.
111    pub line: usize,
112    /// One-based column number in bytes for the current bootstrap model.
113    pub column: usize,
114}
115
116/// Original YAML input plus line-start metadata.
117#[derive(Debug, Clone, PartialEq, Eq)]
118pub struct Source {
119    text: String,
120    line_starts: Vec<u32>,
121    line_facts: Vec<LineFacts>,
122}
123
124const NO_LINE_OFFSET: u16 = u16::MAX;
125const LINE_BLANK: u16 = 1 << 0;
126const LINE_SIMPLE_MAPPING: u16 = 1 << 1;
127const LINE_OFFSET_OVERFLOW: u16 = 1 << 2;
128const LINE_FACTS_MIN_SOURCE_BYTES: usize = 1024;
129
130/// Compact facts for the common block-line parser path.
131///
132/// Offsets are relative to the start of the line. Exceptionally long lines use
133/// the existing full scanners instead of retaining wider offsets for every
134/// ordinary line.
135#[derive(Debug, Clone, Copy, PartialEq, Eq)]
136pub(crate) struct LineFacts {
137    indent: u16,
138    mapping_colon: u16,
139    value_start: u16,
140    flags: u16,
141}
142
143impl LineFacts {
144    const FALLBACK: Self = Self {
145        indent: NO_LINE_OFFSET,
146        mapping_colon: NO_LINE_OFFSET,
147        value_start: NO_LINE_OFFSET,
148        flags: LINE_OFFSET_OVERFLOW,
149    };
150
151    pub(crate) fn indent(self) -> Option<usize> {
152        (!self.has(LINE_OFFSET_OVERFLOW)).then_some(self.indent as usize)
153    }
154
155    pub(crate) fn simple_mapping(self) -> Option<(usize, usize)> {
156        self.has(LINE_SIMPLE_MAPPING)
157            .then_some((self.mapping_colon as usize, self.value_start as usize))
158    }
159
160    pub(crate) fn mapping_colon(self) -> Option<usize> {
161        (self.mapping_colon != NO_LINE_OFFSET).then_some(self.mapping_colon as usize)
162    }
163
164    pub(crate) const fn is_blank(self) -> bool {
165        self.has(LINE_BLANK)
166    }
167
168    const fn has(self, flag: u16) -> bool {
169        self.flags & flag != 0
170    }
171}
172
173impl Source {
174    /// Builds a source buffer, validates YAML 1.2.2 printable characters, and
175    /// records all line starts.
176    ///
177    /// # Errors
178    ///
179    /// Returns an error when `text` contains characters that are not valid in a
180    /// YAML 1.2.2 stream.
181    pub fn new(text: String) -> Result<Self, YamlError> {
182        let mut line_starts = Vec::with_capacity(text.len() / 32 + 1);
183        line_starts.push(0);
184        if text.is_ascii() {
185            for (offset, byte) in text.bytes().enumerate() {
186                if !matches!(byte, b'\t' | b'\n' | b'\r' | b' '..=b'~') {
187                    return Err(invalid_yaml_character(offset, char::from(byte)));
188                }
189                if byte == b'\n' {
190                    line_starts.push(Span::usize_to_u32(offset + 1));
191                }
192            }
193        } else {
194            for (offset, character) in text.char_indices() {
195                if !is_yaml_printable(character) {
196                    return Err(invalid_yaml_character(offset, character));
197                }
198                if character == '\n' {
199                    line_starts.push(Span::usize_to_u32(offset + 1));
200                }
201            }
202        }
203        let line_facts = if text.len() >= LINE_FACTS_MIN_SOURCE_BYTES {
204            build_line_facts(&text, &line_starts)
205        } else {
206            Vec::new()
207        };
208
209        Ok(Self {
210            text,
211            line_starts,
212            line_facts,
213        })
214    }
215
216    /// Returns the original input text.
217    #[must_use]
218    pub fn as_str(&self) -> &str {
219        &self.text
220    }
221
222    /// Returns the source length in bytes.
223    #[must_use]
224    pub fn len(&self) -> usize {
225        self.text.len()
226    }
227
228    /// Returns true when the source is empty.
229    #[must_use]
230    pub fn is_empty(&self) -> bool {
231        self.text.is_empty()
232    }
233
234    /// Returns the recorded line-start byte offsets.
235    #[must_use]
236    pub fn line_starts(&self) -> &[u32] {
237        &self.line_starts
238    }
239
240    pub(crate) fn line_facts(&self, index: usize) -> LineFacts {
241        self.line_facts
242            .get(index)
243            .copied()
244            .unwrap_or(LineFacts::FALLBACK)
245    }
246
247    /// Returns the source slice for `span`.
248    ///
249    /// # Panics
250    ///
251    /// Panics if `span` is outside the source or does not fall on UTF-8
252    /// boundaries. Use [`Source::try_slice`] when handling user-provided spans.
253    #[must_use]
254    pub fn slice(&self, span: Span) -> &str {
255        self.try_slice(span)
256            .expect("span must be in bounds and on UTF-8 boundaries")
257    }
258
259    /// Returns the source slice for `span`, or a span-rich error when invalid.
260    ///
261    /// # Errors
262    ///
263    /// Returns an error when `span` is outside the source text or does not fall
264    /// on UTF-8 boundaries.
265    pub fn try_slice(&self, span: Span) -> Result<&str, YamlError> {
266        let start = span.start as usize;
267        let end = span.end as usize;
268
269        if start > end || end > self.text.len() {
270            return Err(YamlError::new(Diagnostic::new(
271                DiagnosticKind::Source,
272                "span is outside the source text",
273                span,
274            )));
275        }
276
277        self.text.get(start..end).ok_or_else(|| {
278            YamlError::new(Diagnostic::new(
279                DiagnosticKind::Source,
280                "span does not align with UTF-8 character boundaries",
281                span,
282            ))
283        })
284    }
285
286    /// Converts a byte offset into a one-based line/column pair.
287    #[must_use]
288    pub fn line_col(&self, offset: usize) -> LineCol {
289        let offset = Span::usize_to_u32(offset.min(self.text.len()));
290        let line_index = match self.line_starts.binary_search(&offset) {
291            Ok(index) => index,
292            Err(index) => index.saturating_sub(1),
293        };
294        let line_start = self.line_starts[line_index];
295
296        LineCol {
297            line: line_index + 1,
298            column: (offset - line_start) as usize + 1,
299        }
300    }
301
302    /// Returns the line/column pair for a diagnostic's primary span.
303    #[must_use]
304    pub fn diagnostic_position(&self, diagnostic: &Diagnostic) -> LineCol {
305        self.line_col(diagnostic.span.start as usize)
306    }
307}
308
309fn build_line_facts(text: &str, line_starts: &[u32]) -> Vec<LineFacts> {
310    let mut facts = Vec::with_capacity(line_starts.len());
311    for (index, &start) in line_starts.iter().enumerate() {
312        let start = start as usize;
313        let mut end = line_starts
314            .get(index + 1)
315            .map_or(text.len(), |next| *next as usize);
316        if end > start && text.as_bytes()[end - 1] == b'\n' {
317            end -= 1;
318            if end > start && text.as_bytes()[end - 1] == b'\r' {
319                end -= 1;
320            }
321        } else if end > start && text.as_bytes()[end - 1] == b'\r' {
322            end -= 1;
323        }
324        facts.push(analyze_line(&text.as_bytes()[start..end]));
325    }
326    facts
327}
328
329fn analyze_line(line: &[u8]) -> LineFacts {
330    let indent = line.iter().take_while(|byte| **byte == b' ').count();
331    let mut flags = 0;
332    if line[indent..].is_empty() {
333        flags |= LINE_BLANK;
334    }
335
336    if line.len() >= NO_LINE_OFFSET as usize {
337        return LineFacts {
338            flags: flags | LINE_OFFSET_OVERFLOW,
339            ..LineFacts::FALLBACK
340        };
341    }
342
343    let Some(indent) = u16::try_from(indent)
344        .ok()
345        .filter(|value| *value != NO_LINE_OFFSET)
346    else {
347        return LineFacts {
348            indent: NO_LINE_OFFSET,
349            mapping_colon: NO_LINE_OFFSET,
350            value_start: NO_LINE_OFFSET,
351            flags: flags | LINE_OFFSET_OVERFLOW,
352        };
353    };
354
355    let body = &line[indent as usize..];
356    if let Some((colon, value_start)) = plain_key_mapping_offsets(body)
357        && let Ok(colon) = u16::try_from(colon)
358        && colon != NO_LINE_OFFSET
359    {
360        let value_start = value_start
361            .and_then(|offset| u16::try_from(offset).ok())
362            .filter(|offset| *offset != NO_LINE_OFFSET);
363        if value_start.is_some() {
364            flags |= LINE_SIMPLE_MAPPING;
365        }
366        return LineFacts {
367            indent,
368            mapping_colon: colon,
369            value_start: value_start.unwrap_or(NO_LINE_OFFSET),
370            flags,
371        };
372    }
373
374    LineFacts {
375        indent,
376        mapping_colon: NO_LINE_OFFSET,
377        value_start: NO_LINE_OFFSET,
378        flags,
379    }
380}
381
382fn plain_key_mapping_offsets(body: &[u8]) -> Option<(usize, Option<usize>)> {
383    let mut colon = 0;
384    while colon < body.len() && body[colon] != b':' {
385        if !is_simple_plain_byte(body[colon]) {
386            return None;
387        }
388        colon += 1;
389    }
390    if colon == 0 || colon == body.len() {
391        return None;
392    }
393
394    let mut value_start = colon + 1;
395    if value_start == body.len() {
396        return Some((colon, None));
397    }
398    if body.get(value_start) != Some(&b' ') {
399        return None;
400    }
401    while body.get(value_start) == Some(&b' ') {
402        value_start += 1;
403    }
404    if value_start == body.len() || &body[value_start..] == b"-" {
405        return Some((colon, None));
406    }
407    for &byte in &body[value_start..] {
408        if !is_simple_plain_byte(byte) {
409            return Some((colon, None));
410        }
411    }
412    Some((colon, Some(value_start)))
413}
414
415const fn is_simple_plain_byte(byte: u8) -> bool {
416    byte.is_ascii_alphanumeric() || matches!(byte, b'_' | b'-' | b'.' | b'/')
417}
418
419fn invalid_yaml_character(offset: usize, character: char) -> YamlError {
420    let span = Span::from_usize(offset, offset + character.len_utf8());
421    YamlError::new(
422        Diagnostic::new(
423            DiagnosticKind::Source,
424            format!("invalid YAML 1.2.2 character U+{:04X}", character as u32),
425            span,
426        )
427        .with_note(
428            "YAML streams may contain tab, line feeds, carriage returns, printable Unicode characters, and non-breaking spaces",
429        ),
430    )
431}
432
433pub(crate) fn validate_yaml_chars(text: &str) -> Result<(), YamlError> {
434    for (offset, character) in text.char_indices() {
435        if !is_yaml_printable(character) {
436            let span = Span::from_usize(offset, offset + character.len_utf8());
437            return Err(YamlError::new(
438                Diagnostic::new(
439                    DiagnosticKind::Source,
440                    format!(
441                        "invalid YAML 1.2.2 character U+{:04X}",
442                        character as u32
443                    ),
444                    span,
445                )
446                .with_note(
447                    "YAML streams may contain tab, line feeds, carriage returns, printable Unicode characters, and non-breaking spaces",
448                ),
449            ));
450        }
451    }
452
453    Ok(())
454}
455
456const fn is_yaml_printable(character: char) -> bool {
457    matches!(
458        character as u32,
459        0x09 | 0x0A | 0x0D | 0x20..=0x7E | 0x85 | 0xA0..=0xD7FF | 0xE000..=0xFFFD | 0x001_0000..=0x0010_FFFF
460    )
461}
462
463#[cfg(test)]
464mod line_facts_tests {
465    use std::fmt::Write;
466
467    use super::*;
468    use crate::YamlDoc;
469
470    #[test]
471    fn caches_common_lines_and_leaves_complex_lines_on_the_fallback_path() {
472        let source = Source::new(
473            "alpha: beta\r\nunicode: café\n\tbad: tab\n\"quoted\": value\n&anchor key: value\nflow: [one, two]\nkey: value # comment\n# comment\nliteral: |\n  text\n"
474                .to_owned(),
475        )
476        .expect("fixture is printable YAML");
477
478        let facts = build_line_facts(source.as_str(), source.line_starts());
479        assert_eq!(facts[0].simple_mapping(), Some((5, 7)));
480        assert_eq!(facts[1].mapping_colon(), Some(7));
481        assert_eq!(facts[1].simple_mapping(), None);
482        assert_eq!(facts[2].mapping_colon(), None);
483        assert_eq!(facts[3].mapping_colon(), None);
484        assert_eq!(facts[4].mapping_colon(), None);
485        assert_eq!(facts[5].mapping_colon(), Some(4));
486        assert_eq!(facts[5].simple_mapping(), None);
487        assert_eq!(facts[6].mapping_colon(), Some(3));
488        assert_eq!(facts[6].simple_mapping(), None);
489        assert_eq!(facts[7].mapping_colon(), None);
490        assert_eq!(facts[8].mapping_colon(), Some(7));
491        assert_eq!(facts[9].indent(), Some(2));
492    }
493
494    #[test]
495    fn cached_common_mapping_path_preserves_the_complete_source() {
496        let mut input = String::new();
497        for index in 0..100 {
498            writeln!(input, "key_{index:04}: value_{index:04}")
499                .expect("writing to a String cannot fail");
500        }
501        let source = Source::new(input.clone()).expect("generated mapping is printable YAML");
502        assert_eq!(source.line_facts(0).simple_mapping(), Some((8, 10)));
503
504        let doc = YamlDoc::parse(&input).expect("cached mapping should parse");
505        assert_eq!(doc.to_string(), input);
506    }
507
508    #[test]
509    fn long_line_offsets_fall_back_without_changing_parse_behavior() {
510        let key = "k".repeat(u16::MAX as usize);
511        let input = format!("{key}: value\n");
512        let source = Source::new(input.clone()).expect("long fixture is printable YAML");
513        assert_eq!(source.line_facts(0).mapping_colon(), None);
514
515        let doc = YamlDoc::parse(&input).expect("long mapping key should use the full scanner");
516        assert_eq!(doc.to_string(), input);
517    }
518}
yaml_rt_core/source.rs

yaml_rt_core/
source.rs
