toml_parser/lexer/
mod.rs

1//! Lex TOML tokens
2//!
3//! To get started, see [`Source::lex`][crate::Source::lex]
4
5#[cfg(test)]
6#[cfg(feature = "std")]
7mod test;
8mod token;
9
10#[cfg(feature = "alloc")]
11use alloc::vec::Vec;
12
13use winnow::stream::AsBStr as _;
14use winnow::stream::ContainsToken as _;
15use winnow::stream::FindSlice as _;
16use winnow::stream::Location;
17use winnow::stream::Stream as _;
18
19use crate::Span;
20
21pub use token::Token;
22pub use token::TokenKind;
23
24/// Lex TOML [tokens][Token]
25///
26/// To get started, see [`Source::lex`][crate::Source::lex]
27pub struct Lexer<'i> {
28    stream: Stream<'i>,
29    eof: bool,
30}
31
32impl<'i> Lexer<'i> {
33    pub(crate) fn new(input: &'i str) -> Self {
34        let mut stream = Stream::new(input);
35        if input.as_bytes().starts_with(BOM) {
36            let offset = BOM.len();
37            #[cfg(feature = "unsafe")] // SAFETY: only called when next character is ASCII
38            unsafe {
39                stream.next_slice_unchecked(offset)
40            };
41            #[cfg(not(feature = "unsafe"))]
42            stream.next_slice(offset);
43        }
44        Lexer { stream, eof: false }
45    }
46
47    #[cfg(feature = "alloc")]
48    pub fn into_vec(self) -> Vec<Token> {
49        let len = self.stream.len();
50        // The 2/7 ratio was determined by looking packaged manifests under a representative set of
51        // packages determined by dependencies of several large, popular projects.
52        //
53        // Divide before multiplying to avoid overflowing for very large inputs.
54        let estimate = (len / 7) * 2;
55        let addressable_limit = isize::MAX as usize / size_of::<Token>();
56        let capacity = estimate.min(addressable_limit);
57        let mut vec = Vec::with_capacity(capacity);
58        vec.extend(self);
59        vec
60    }
61}
62
63impl Iterator for Lexer<'_> {
64    type Item = Token;
65
66    fn next(&mut self) -> Option<Self::Item> {
67        let Some(peek_byte) = self.stream.as_bstr().first() else {
68            if self.eof {
69                return None;
70            } else {
71                self.eof = true;
72                let start = self.stream.current_token_start();
73                let span = Span::new_unchecked(start, start);
74                return Some(Token::new(TokenKind::Eof, span));
75            }
76        };
77        Some(process_token(*peek_byte, &mut self.stream))
78    }
79}
80
81const BOM: &[u8] = b"\xEF\xBB\xBF";
82
83pub(crate) type Stream<'i> = winnow::stream::LocatingSlice<&'i str>;
84
85fn process_token(peek_byte: u8, stream: &mut Stream<'_>) -> Token {
86    let token = match peek_byte {
87        b'.' => lex_ascii_char(stream, TokenKind::Dot),
88        b'=' => lex_ascii_char(stream, TokenKind::Equals),
89        b',' => lex_ascii_char(stream, TokenKind::Comma),
90        b'[' => lex_ascii_char(stream, TokenKind::LeftSquareBracket),
91        b']' => lex_ascii_char(stream, TokenKind::RightSquareBracket),
92        b'{' => lex_ascii_char(stream, TokenKind::LeftCurlyBracket),
93        b'}' => lex_ascii_char(stream, TokenKind::RightCurlyBracket),
94        b' ' => lex_whitespace(stream),
95        b'\t' => lex_whitespace(stream),
96        b'#' => lex_comment(stream),
97        b'\r' => lex_crlf(stream),
98        b'\n' => lex_ascii_char(stream, TokenKind::Newline),
99        b'\'' => {
100            if stream.starts_with(ML_LITERAL_STRING_DELIM) {
101                lex_ml_literal_string(stream)
102            } else {
103                lex_literal_string(stream)
104            }
105        }
106        b'"' => {
107            if stream.starts_with(ML_BASIC_STRING_DELIM) {
108                lex_ml_basic_string(stream)
109            } else {
110                lex_basic_string(stream)
111            }
112        }
113        _ => lex_atom(stream),
114    };
115    token
116}
117
118/// Process an ASCII character token
119///
120/// # Safety
121///
122/// - `stream` must be UTF-8
123/// - `stream` must be non-empty
124/// - `stream[0]` must be ASCII
125fn lex_ascii_char(stream: &mut Stream<'_>, kind: TokenKind) -> Token {
126    debug_assert!(!stream.is_empty());
127    let start = stream.current_token_start();
128
129    let offset = 1; // an ascii character
130    #[cfg(feature = "unsafe")] // SAFETY: only called when next character is ASCII
131    unsafe {
132        stream.next_slice_unchecked(offset)
133    };
134    #[cfg(not(feature = "unsafe"))]
135    stream.next_slice(offset);
136
137    let end = stream.previous_token_end();
138    let span = Span::new_unchecked(start, end);
139    Token::new(kind, span)
140}
141
142/// Process Whitespace
143///
144/// ```abnf
145/// ;; Whitespace
146///
147/// ws = *wschar
148/// wschar =  %x20  ; Space
149/// wschar =/ %x09  ; Horizontal tab
150/// ```
151///
152/// # Safety
153///
154/// - `stream` must be UTF-8
155/// - `stream` must be non-empty
156fn lex_whitespace(stream: &mut Stream<'_>) -> Token {
157    debug_assert!(!stream.is_empty());
158    let start = stream.current_token_start();
159
160    let offset = stream
161        .as_bstr()
162        .offset_for(|b| !WSCHAR.contains_token(b))
163        .unwrap_or(stream.eof_offset());
164    #[cfg(feature = "unsafe")] // SAFETY: WSCHAR ensures `offset` will be at UTF-8 boundary
165    unsafe {
166        stream.next_slice_unchecked(offset)
167    };
168    #[cfg(not(feature = "unsafe"))]
169    stream.next_slice(offset);
170
171    let end = stream.previous_token_end();
172    let span = Span::new_unchecked(start, end);
173    Token::new(TokenKind::Whitespace, span)
174}
175
176/// ```abnf
177/// wschar =  %x20  ; Space
178/// wschar =/ %x09  ; Horizontal tab
179/// ```
180pub(crate) const WSCHAR: (u8, u8) = (b' ', b'\t');
181
182/// Process Comment
183///
184/// ```abnf
185/// ;; Comment
186///
187/// comment-start-symbol = %x23 ; #
188/// non-ascii = %x80-D7FF / %xE000-10FFFF
189/// non-eol = %x09 / %x20-7E / non-ascii
190///
191/// comment = comment-start-symbol *non-eol
192/// ```
193///
194/// # Safety
195///
196/// - `stream` must be UTF-8
197/// - `stream[0] == b'#'`
198fn lex_comment(stream: &mut Stream<'_>) -> Token {
199    let start = stream.current_token_start();
200
201    let offset = stream
202        .as_bytes()
203        .find_slice((b'\r', b'\n'))
204        .map(|s| s.start)
205        .unwrap_or_else(|| stream.eof_offset());
206    #[cfg(feature = "unsafe")] // SAFETY: newlines ensure `offset` is along UTF-8 boundary
207    unsafe {
208        stream.next_slice_unchecked(offset)
209    };
210    #[cfg(not(feature = "unsafe"))]
211    stream.next_slice(offset);
212
213    let end = stream.previous_token_end();
214    let span = Span::new_unchecked(start, end);
215    Token::new(TokenKind::Comment, span)
216}
217
218/// ```abnf
219/// comment-start-symbol = %x23 ; #
220/// ```
221pub(crate) const COMMENT_START_SYMBOL: u8 = b'#';
222
223/// Process Newline
224///
225/// ```abnf
226/// ;; Newline
227///
228/// newline =  %x0A     ; LF
229/// newline =/ %x0D.0A  ; CRLF
230/// ```
231///
232/// # Safety
233///
234/// - `stream` must be UTF-8
235/// - `stream[0] == b'\r'`
236fn lex_crlf(stream: &mut Stream<'_>) -> Token {
237    let start = stream.current_token_start();
238
239    let mut offset = '\r'.len_utf8();
240    let has_lf = stream.as_bstr().get(1) == Some(&b'\n');
241    if has_lf {
242        offset += '\n'.len_utf8();
243    }
244
245    #[cfg(feature = "unsafe")] // SAFETY: newlines ensure `offset` is along UTF-8 boundary
246    unsafe {
247        stream.next_slice_unchecked(offset)
248    };
249    #[cfg(not(feature = "unsafe"))]
250    stream.next_slice(offset);
251    let end = stream.previous_token_end();
252    let span = Span::new_unchecked(start, end);
253
254    Token::new(TokenKind::Newline, span)
255}
256
257/// Process literal string
258///
259/// ```abnf
260/// ;; Literal String
261///
262/// literal-string = apostrophe *literal-char apostrophe
263///
264/// apostrophe = %x27 ; ' apostrophe
265///
266/// literal-char = %x09 / %x20-26 / %x28-7E / non-ascii
267/// ```
268///
269/// # Safety
270///
271/// - `stream` must be UTF-8
272/// - `stream[0] == b'\''`
273fn lex_literal_string(stream: &mut Stream<'_>) -> Token {
274    let start = stream.current_token_start();
275
276    let offset = 1; // APOSTROPHE
277    #[cfg(feature = "unsafe")] // SAFETY: only called when next character is ASCII
278    unsafe {
279        stream.next_slice_unchecked(offset)
280    };
281    #[cfg(not(feature = "unsafe"))]
282    stream.next_slice(offset);
283
284    let offset = match stream.as_bstr().find_slice((APOSTROPHE, b'\n')) {
285        Some(span) => {
286            if stream.as_bstr()[span.start] == APOSTROPHE {
287                span.end
288            } else {
289                span.start
290            }
291        }
292        None => stream.eof_offset(),
293    };
294    #[cfg(feature = "unsafe")]
295    // SAFETY: `APOSTROPHE`/newline ensure `offset` is along UTF-8 boundary
296    unsafe {
297        stream.next_slice_unchecked(offset)
298    };
299    #[cfg(not(feature = "unsafe"))]
300    stream.next_slice(offset);
301
302    let end = stream.previous_token_end();
303    let span = Span::new_unchecked(start, end);
304    Token::new(TokenKind::LiteralString, span)
305}
306
307/// ```abnf
308/// apostrophe = %x27 ; ' apostrophe
309/// ```
310pub(crate) const APOSTROPHE: u8 = b'\'';
311
312/// Process multi-line literal string
313///
314/// ```abnf
315/// ;; Multiline Literal String
316///
317/// ml-literal-string = ml-literal-string-delim [ newline ] ml-literal-body
318///                     ml-literal-string-delim
319/// ml-literal-string-delim = 3apostrophe
320/// ml-literal-body = *mll-content *( mll-quotes 1*mll-content ) [ mll-quotes ]
321///
322/// mll-content = literal-char / newline
323/// mll-quotes = 1*2apostrophe
324/// ```
325///
326/// # Safety
327///
328/// - `stream` must be UTF-8
329/// - `stream.starts_with(ML_LITERAL_STRING_DELIM)`
330fn lex_ml_literal_string(stream: &mut Stream<'_>) -> Token {
331    let start = stream.current_token_start();
332
333    let offset = ML_LITERAL_STRING_DELIM.len();
334    #[cfg(feature = "unsafe")] // SAFETY: only called when next character is ASCII
335    unsafe {
336        stream.next_slice_unchecked(offset)
337    };
338    #[cfg(not(feature = "unsafe"))]
339    stream.next_slice(offset);
340
341    let offset = match stream.as_bstr().find_slice(ML_LITERAL_STRING_DELIM) {
342        Some(span) => span.end,
343        None => stream.eof_offset(),
344    };
345    #[cfg(feature = "unsafe")]
346    // SAFETY: `ML_LITERAL_STRING_DELIM` ensure `offset` is along UTF-8 boundary
347    unsafe {
348        stream.next_slice_unchecked(offset)
349    };
350    #[cfg(not(feature = "unsafe"))]
351    stream.next_slice(offset);
352
353    if stream.as_bstr().peek_token() == Some(APOSTROPHE) {
354        let offset = 1;
355        #[cfg(feature = "unsafe")] // SAFETY: `APOSTROPHE` ensure `offset` is along UTF-8 boundary
356        unsafe {
357            stream.next_slice_unchecked(offset)
358        };
359        #[cfg(not(feature = "unsafe"))]
360        stream.next_slice(offset);
361
362        if stream.as_bstr().peek_token() == Some(APOSTROPHE) {
363            let offset = 1;
364            #[cfg(feature = "unsafe")]
365            // SAFETY: `APOSTROPHE` ensure `offset` is along UTF-8 boundary
366            unsafe {
367                stream.next_slice_unchecked(offset)
368            };
369            #[cfg(not(feature = "unsafe"))]
370            stream.next_slice(offset);
371        }
372    }
373
374    let end = stream.previous_token_end();
375    let span = Span::new_unchecked(start, end);
376    Token::new(TokenKind::MlLiteralString, span)
377}
378
379/// ```abnf
380/// ml-literal-string-delim = 3apostrophe
381/// ```
382pub(crate) const ML_LITERAL_STRING_DELIM: &str = "'''";
383
384/// Process basic string
385///
386/// ```abnf
387/// ;; Basic String
388///
389/// basic-string = quotation-mark *basic-char quotation-mark
390///
391/// quotation-mark = %x22            ; "
392///
393/// basic-char = basic-unescaped / escaped
394/// basic-unescaped = wschar / %x21 / %x23-5B / %x5D-7E / non-ascii
395/// escaped = escape escape-seq-char
396///
397/// escape = %x5C                   ; \
398/// escape-seq-char =  %x22         ; "    quotation mark  U+0022
399/// escape-seq-char =/ %x5C         ; \    reverse solidus U+005C
400/// escape-seq-char =/ %x62         ; b    backspace       U+0008
401/// escape-seq-char =/ %x65         ; e    escape          U+001B
402/// escape-seq-char =/ %x66         ; f    form feed       U+000C
403/// escape-seq-char =/ %x6E         ; n    line feed       U+000A
404/// escape-seq-char =/ %x72         ; r    carriage return U+000D
405/// escape-seq-char =/ %x74         ; t    tab             U+0009
406/// escape-seq-char =/ %x78 2HEXDIG ; xHH                  U+00HH
407/// escape-seq-char =/ %x75 4HEXDIG ; uHHHH                U+HHHH
408/// escape-seq-char =/ %x55 8HEXDIG ; UHHHHHHHH            U+HHHHHHHH
409/// ```
410///
411/// # Safety
412///
413/// - `stream` must be UTF-8
414/// - `stream[0] == b'"'`
415fn lex_basic_string(stream: &mut Stream<'_>) -> Token {
416    let start = stream.current_token_start();
417
418    let offset = 1; // QUOTATION_MARK
419    #[cfg(feature = "unsafe")] // SAFETY: only called when next character is ASCII
420    unsafe {
421        stream.next_slice_unchecked(offset)
422    };
423    #[cfg(not(feature = "unsafe"))]
424    stream.next_slice(offset);
425
426    loop {
427        // newline is present for error recovery
428        match stream.as_bstr().find_slice((QUOTATION_MARK, ESCAPE, b'\n')) {
429            Some(span) => {
430                let found = stream.as_bstr()[span.start];
431                if found == QUOTATION_MARK {
432                    let offset = span.end;
433                    #[cfg(feature = "unsafe")]
434                    // SAFETY: `QUOTATION_MARK` ensure `offset` is along UTF-8 boundary
435                    unsafe {
436                        stream.next_slice_unchecked(offset)
437                    };
438                    #[cfg(not(feature = "unsafe"))]
439                    stream.next_slice(offset);
440                    break;
441                } else if found == ESCAPE {
442                    let offset = span.end;
443                    #[cfg(feature = "unsafe")]
444                    // SAFETY: `ESCAPE` / newline ensure `offset` is along UTF-8 boundary
445                    unsafe {
446                        stream.next_slice_unchecked(offset)
447                    };
448                    #[cfg(not(feature = "unsafe"))]
449                    stream.next_slice(offset);
450
451                    let peek = stream.as_bstr().peek_token();
452                    match peek {
453                        Some(ESCAPE) | Some(QUOTATION_MARK) => {
454                            let offset = 1; // ESCAPE / QUOTATION_MARK
455                            #[cfg(feature = "unsafe")]
456                            #[cfg(feature = "unsafe")]
457                            // SAFETY: `ESCAPE` / newline ensure `offset` is along UTF-8 boundary
458                            unsafe {
459                                stream.next_slice_unchecked(offset)
460                            };
461                            #[cfg(not(feature = "unsafe"))]
462                            stream.next_slice(offset);
463                        }
464                        _ => {}
465                    }
466                    continue;
467                } else if found == b'\n' {
468                    let offset = span.start;
469                    #[cfg(feature = "unsafe")]
470                    // SAFETY: newline ensure `offset` is along UTF-8 boundary
471                    unsafe {
472                        stream.next_slice_unchecked(offset)
473                    };
474                    #[cfg(not(feature = "unsafe"))]
475                    stream.next_slice(offset);
476                    break;
477                } else {
478                    unreachable!("found `{found}`");
479                }
480            }
481            None => {
482                stream.finish();
483                break;
484            }
485        }
486    }
487
488    let end = stream.previous_token_end();
489    let span = Span::new_unchecked(start, end);
490    Token::new(TokenKind::BasicString, span)
491}
492
493/// ```abnf
494/// quotation-mark = %x22            ; "
495/// ```
496pub(crate) const QUOTATION_MARK: u8 = b'"';
497
498/// ```abnf
499/// escape = %x5C                   ; \
500/// ```
501pub(crate) const ESCAPE: u8 = b'\\';
502
503/// Process multi-line basic string
504///
505/// ```abnf
506/// ;; Multiline Basic String
507///
508/// ml-basic-string = ml-basic-string-delim [ newline ] ml-basic-body
509///                   ml-basic-string-delim
510/// ml-basic-string-delim = 3quotation-mark
511/// ml-basic-body = *mlb-content *( mlb-quotes 1*mlb-content ) [ mlb-quotes ]
512///
513/// mlb-content = basic-char / newline / mlb-escaped-nl
514/// mlb-quotes = 1*2quotation-mark
515/// mlb-escaped-nl = escape ws newline *( wschar / newline )
516/// ```
517///
518/// # Safety
519///
520/// - `stream` must be UTF-8
521/// - `stream.starts_with(ML_BASIC_STRING_DELIM)`
522fn lex_ml_basic_string(stream: &mut Stream<'_>) -> Token {
523    let start = stream.current_token_start();
524
525    let offset = ML_BASIC_STRING_DELIM.len();
526    #[cfg(feature = "unsafe")] // SAFETY: only called when next character is ASCII
527    unsafe {
528        stream.next_slice_unchecked(offset)
529    };
530    #[cfg(not(feature = "unsafe"))]
531    stream.next_slice(offset);
532
533    loop {
534        // newline is present for error recovery
535        match stream.as_bstr().find_slice((ML_BASIC_STRING_DELIM, "\\")) {
536            Some(span) => {
537                let found = stream.as_bstr()[span.start];
538                if found == QUOTATION_MARK {
539                    let offset = span.end;
540                    #[cfg(feature = "unsafe")]
541                    // SAFETY: `QUOTATION_MARK` ensure `offset` is along UTF-8 boundary
542                    unsafe {
543                        stream.next_slice_unchecked(offset)
544                    };
545                    #[cfg(not(feature = "unsafe"))]
546                    stream.next_slice(offset);
547                    break;
548                } else if found == ESCAPE {
549                    let offset = span.end;
550                    #[cfg(feature = "unsafe")]
551                    // SAFETY: `ESCAPE` ensure `offset` is along UTF-8 boundary
552                    unsafe {
553                        stream.next_slice_unchecked(offset)
554                    };
555                    #[cfg(not(feature = "unsafe"))]
556                    stream.next_slice(offset);
557
558                    let peek = stream.as_bstr().peek_token();
559                    match peek {
560                        Some(ESCAPE) | Some(QUOTATION_MARK) => {
561                            let offset = 1; // ESCAPE / QUOTATION_MARK
562                            #[cfg(feature = "unsafe")]
563                            // SAFETY: `QUOTATION_MARK`/`ESCAPE` ensure `offset` is along UTF-8 boundary
564                            unsafe {
565                                stream.next_slice_unchecked(offset)
566                            };
567                            #[cfg(not(feature = "unsafe"))]
568                            stream.next_slice(offset);
569                        }
570                        _ => {}
571                    }
572                    continue;
573                } else {
574                    unreachable!("found `{found}`");
575                }
576            }
577            None => {
578                stream.finish();
579                break;
580            }
581        }
582    }
583    if stream.as_bstr().peek_token() == Some(QUOTATION_MARK) {
584        let offset = 1;
585        #[cfg(feature = "unsafe")]
586        // SAFETY: `QUOTATION_MARK` ensure `offset` is along UTF-8 boundary
587        unsafe {
588            stream.next_slice_unchecked(offset)
589        };
590        #[cfg(not(feature = "unsafe"))]
591        stream.next_slice(offset);
592        if stream.as_bstr().peek_token() == Some(QUOTATION_MARK) {
593            let offset = 1;
594            #[cfg(feature = "unsafe")]
595            // SAFETY: `QUOTATION_MARK` ensure `offset` is along UTF-8 boundary
596            unsafe {
597                stream.next_slice_unchecked(offset)
598            };
599            #[cfg(not(feature = "unsafe"))]
600            stream.next_slice(offset);
601        }
602    }
603
604    let end = stream.previous_token_end();
605    let span = Span::new_unchecked(start, end);
606    Token::new(TokenKind::MlBasicString, span)
607}
608
609/// ```abnf
610/// ml-basic-string-delim = 3quotation-mark
611/// ```
612pub(crate) const ML_BASIC_STRING_DELIM: &str = "\"\"\"";
613
614/// Process Atom
615///
616/// This is everything else
617///
618/// # Safety
619///
620/// - `stream` must be UTF-8
621/// - `stream` must be non-empty
622fn lex_atom(stream: &mut Stream<'_>) -> Token {
623    let start = stream.current_token_start();
624
625    // Intentionally leaves off quotes in case the opening quote was missing
626    const TOKEN_START: &[u8] = b".=,[]{} \t#\r\n";
627    let offset = stream
628        .as_bstr()
629        .offset_for(|b| TOKEN_START.contains_token(b))
630        .unwrap_or_else(|| stream.eof_offset());
631    #[cfg(feature = "unsafe")] // SAFETY: `TOKEN_START` ensure `offset` is along UTF-8 boundary
632    unsafe {
633        stream.next_slice_unchecked(offset)
634    };
635    #[cfg(not(feature = "unsafe"))]
636    stream.next_slice(offset);
637
638    let end = stream.previous_token_end();
639    let span = Span::new_unchecked(start, end);
640    Token::new(TokenKind::Atom, span)
641}
toml_parser/lexer/mod.rs

toml_parser/lexer/
mod.rs
