reed_parser/lexer/
mod.rs

1mod cursor;
2mod lookup;
3mod token;
4mod token_kind;
5
6use crate::lexer::cursor::Cursor;
7use crate::Error;
8use crate::LimitTracker;
9pub use token::Token;
10pub use token_kind::TokenKind;
11
12/// Parses GraphQL source text into tokens.
13/// ```rust
14/// use reed_parser::Lexer;
15///
16/// let query = "
17/// {
18///     animal
19///     ...snackSelection
20///     ... on Pet {
21///       playmates {
22///         count
23///       }
24///     }
25/// }
26/// ";
27/// let (tokens, errors) = Lexer::new(query).lex();
28/// assert_eq!(errors.len(), 0);
29/// ```
30#[derive(Clone, Debug)]
31pub struct Lexer<'a> {
32    finished: bool,
33    cursor: Cursor<'a>,
34    pub(crate) limit_tracker: LimitTracker,
35}
36
37#[derive(Debug)]
38enum State {
39    Start,
40    Ident,
41    StringLiteral,
42    StringLiteralStart,
43    BlockStringLiteral,
44    BlockStringLiteralBackslash,
45    StringLiteralBackslash,
46    LeadingZero,
47    IntegerPart,
48    DecimalPoint,
49    FractionalPart,
50    ExponentIndicator,
51    ExponentSign,
52    ExponentDigit,
53    Whitespace,
54    Comment,
55    SpreadOperator,
56    MinusSign,
57}
58
59impl<'a> Lexer<'a> {
60    /// Create a lexer for a GraphQL source text.
61    ///
62    /// The Lexer is an iterator over tokens and errors:
63    /// ```rust
64    /// use reed_parser::Lexer;
65    ///
66    /// let query = "# --- GraphQL here ---";
67    ///
68    /// let mut lexer = Lexer::new(query);
69    /// let mut tokens = vec![];
70    /// for token in lexer {
71    ///     match token {
72    ///         Ok(token) => tokens.push(token),
73    ///         Err(error) => panic!("{:?}", error),
74    ///     }
75    /// }
76    /// ```
77    pub fn new(input: &'a str) -> Self {
78        Self {
79            cursor: Cursor::new(input),
80            finished: false,
81            limit_tracker: LimitTracker::new(usize::MAX),
82        }
83    }
84
85    pub fn with_limit(mut self, limit: usize) -> Self {
86        self.limit_tracker = LimitTracker::new(limit);
87        self
88    }
89
90    /// Lex the full source text, consuming the lexer.
91    pub fn lex(self) -> (Vec<Token<'a>>, Vec<Error>) {
92        let mut tokens = vec![];
93        let mut errors = vec![];
94
95        for item in self {
96            match item {
97                Ok(token) => tokens.push(token),
98                Err(error) => errors.push(error),
99            }
100        }
101
102        (tokens, errors)
103    }
104}
105
106impl<'a> Iterator for Lexer<'a> {
107    type Item = Result<Token<'a>, Error>;
108
109    fn next(&mut self) -> Option<Self::Item> {
110        if self.finished {
111            return None;
112        }
113
114        if self.limit_tracker.check_and_increment() {
115            self.finished = true;
116            return Some(Err(Error::limit(
117                "token limit reached, aborting lexing",
118                self.cursor.index(),
119            )));
120        }
121
122        match self.cursor.advance() {
123            Ok(token) => {
124                if matches!(token.kind(), TokenKind::Eof) {
125                    self.finished = true;
126                }
127
128                Some(Ok(token))
129            }
130            Err(err) => Some(Err(err)),
131        }
132    }
133}
134
135impl<'a> Cursor<'a> {
136    fn advance(&mut self) -> Result<Token<'a>, Error> {
137        let mut state = State::Start;
138        let mut token = Token {
139            kind: TokenKind::Eof,
140            data: "",
141            index: self.index(),
142        };
143
144        loop {
145            let Some(c) = self.bump() else {
146                return self.eof(state, token);
147            };
148            match state {
149                State::Start => {
150                    if let Some(t) = lookup::punctuation_kind(c) {
151                        token.kind = t;
152                        token.data = self.current_str();
153                        return Ok(token);
154                    }
155
156                    if lookup::is_namestart(c) {
157                        token.kind = TokenKind::Name;
158                        state = State::Ident;
159
160                        continue;
161                    }
162
163                    if c != '0' && c.is_ascii_digit() {
164                        token.kind = TokenKind::Int;
165                        state = State::IntegerPart;
166
167                        continue;
168                    }
169
170                    match c {
171                        '"' => {
172                            token.kind = TokenKind::StringValue;
173                            state = State::StringLiteralStart;
174                        }
175                        '#' => {
176                            token.kind = TokenKind::Comment;
177                            state = State::Comment;
178                        }
179                        '.' => {
180                            token.kind = TokenKind::Spread;
181                            state = State::SpreadOperator;
182                        }
183                        '-' => {
184                            token.kind = TokenKind::Int;
185                            state = State::MinusSign;
186                        }
187                        '0' => {
188                            token.kind = TokenKind::Int;
189                            state = State::LeadingZero;
190                        }
191                        c if is_whitespace_assimilated(c) => {
192                            token.kind = TokenKind::Whitespace;
193                            state = State::Whitespace;
194                        }
195                        c => {
196                            return Err(Error::with_loc(
197                                format!(r#"Unexpected character "{c}""#),
198                                self.current_str().to_string(),
199                                token.index,
200                            ));
201                        }
202                    };
203                }
204                State::Ident => match c {
205                    curr if is_name_continue(curr) => {}
206                    _ => {
207                        token.data = self.prev_str();
208                        return self.done(token);
209                    }
210                },
211                State::Whitespace => match c {
212                    curr if is_whitespace_assimilated(curr) => {}
213                    _ => {
214                        token.data = self.prev_str();
215                        return self.done(token);
216                    }
217                },
218                State::BlockStringLiteral => match c {
219                    '\\' => {
220                        state = State::BlockStringLiteralBackslash;
221                    }
222                    '"'
223                        // Require two additional quotes to complete the triple quote.
224                        if self.eatc('"') && self.eatc('"') => {
225                            token.data = self.current_str();
226                            return self.done(token);
227                        }
228                    _ => {}
229                },
230                State::StringLiteralStart => match c {
231                    '"' => {
232                        if self.eatc('"') {
233                            state = State::BlockStringLiteral;
234
235                            continue;
236                        }
237
238                        if self.is_pending() {
239                            token.data = self.prev_str();
240                        } else {
241                            token.data = self.current_str();
242                        }
243                        return self.done(token);
244                    }
245                    '\\' => {
246                        state = State::StringLiteralBackslash;
247                    }
248                    _ => {
249                        state = State::StringLiteral;
250
251                        continue;
252                    }
253                },
254                State::StringLiteral => match c {
255                    '"' => {
256                        token.data = self.current_str();
257                        return self.done(token);
258                    }
259                    curr if is_line_terminator(curr) => {
260                        self.add_err(Error::with_loc(
261                            "unexpected line terminator",
262                            "".to_string(),
263                            0,
264                        ));
265                    }
266                    '\\' => {
267                        state = State::StringLiteralBackslash;
268                    }
269                    _ => {}
270                },
271                State::BlockStringLiteralBackslash => match c {
272                    '"' => {
273                        // If this is \""", we need to eat 3 in total, and then continue parsing.
274                        // The lexer does not un-escape escape sequences so it's OK
275                        // if we take this path for \"", even if that is technically not an escape
276                        // sequence.
277                        if self.eatc('"') {
278                            self.eatc('"');
279                        }
280
281                        state = State::BlockStringLiteral;
282                    }
283                    '\\' => {
284                        // We need to stay in the backslash state:
285                        // it's legal to write \\\""" with two literal backslashes
286                        // and then the escape sequence.
287                    }
288                    _ => {
289                        state = State::BlockStringLiteral;
290                    }
291                },
292                State::StringLiteralBackslash => match c {
293                    curr if is_escaped_char(curr) => {
294                        state = State::StringLiteral;
295                    }
296                    'u' => {
297                        if let Some((_, length)) = unicode_escape(&self.source[self.offset + 1..]) {
298                            for _ in 0..length {
299                                self.bump();
300                            }
301                        } else {
302                            self.add_err(Error::with_loc(
303                                "invalid unicode escape sequence",
304                                "".to_owned(),
305                                self.offset,
306                            ));
307                        }
308                        state = State::StringLiteral;
309                    }
310                    _ => {
311                        self.add_err(Error::with_loc(
312                            "unexpected escaped character",
313                            c.to_string(),
314                            0,
315                        ));
316
317                        state = State::StringLiteral;
318                    }
319                },
320                State::LeadingZero => match c {
321                    '.' => {
322                        token.kind = TokenKind::Float;
323                        state = State::DecimalPoint;
324                    }
325                    'e' | 'E' => {
326                        token.kind = TokenKind::Float;
327                        state = State::ExponentIndicator;
328                    }
329                    _ if c.is_ascii_digit() => {
330                        return Err(Error::with_loc(
331                            "Numbers must not have non-significant leading zeroes",
332                            self.current_str().to_string(),
333                            token.index,
334                        ));
335                    }
336                    _ if lookup::is_namestart(c) => {
337                        return Err(Error::with_loc(
338                            format!("Unexpected character `{c}` as integer suffix"),
339                            self.current_str().to_string(),
340                            token.index,
341                        ));
342                    }
343                    _ => {
344                        token.data = self.prev_str();
345                        return self.done(token);
346                    }
347                },
348                State::IntegerPart => match c {
349                    curr if curr.is_ascii_digit() => {}
350                    '.' => {
351                        token.kind = TokenKind::Float;
352                        state = State::DecimalPoint;
353                    }
354                    'e' | 'E' => {
355                        token.kind = TokenKind::Float;
356                        state = State::ExponentIndicator;
357                    }
358                    _ if lookup::is_namestart(c) => {
359                        return Err(Error::with_loc(
360                            format!("Unexpected character `{c}` as integer suffix"),
361                            self.current_str().to_string(),
362                            token.index,
363                        ));
364                    }
365                    _ => {
366                        token.data = self.prev_str();
367                        return self.done(token);
368                    }
369                },
370                State::DecimalPoint => match c {
371                    curr if curr.is_ascii_digit() => {
372                        state = State::FractionalPart;
373                    }
374                    _ => {
375                        return Err(Error::with_loc(
376                            format!("Unexpected character `{c}`, expected fractional digit"),
377                            self.current_str().to_string(),
378                            token.index,
379                        ));
380                    }
381                },
382                State::FractionalPart => match c {
383                    curr if curr.is_ascii_digit() => {}
384                    'e' | 'E' => {
385                        state = State::ExponentIndicator;
386                    }
387                    _ if c == '.' || lookup::is_namestart(c) => {
388                        return Err(Error::with_loc(
389                            format!("Unexpected character `{c}` as float suffix"),
390                            self.current_str().to_string(),
391                            token.index,
392                        ));
393                    }
394                    _ => {
395                        token.data = self.prev_str();
396                        return self.done(token);
397                    }
398                },
399                State::ExponentIndicator => match c {
400                    _ if c.is_ascii_digit() => {
401                        state = State::ExponentDigit;
402                    }
403                    '+' | '-' => {
404                        state = State::ExponentSign;
405                    }
406                    _ => {
407                        return Err(Error::with_loc(
408                            format!("Unexpected character `{c}`, expected exponent digit or sign"),
409                            self.current_str().to_string(),
410                            token.index,
411                        ))
412                    }
413                },
414                State::ExponentSign => match c {
415                    _ if c.is_ascii_digit() => {
416                        state = State::ExponentDigit;
417                    }
418                    _ => {
419                        return Err(Error::with_loc(
420                            format!("Unexpected character `{c}`, expected exponent digit"),
421                            self.current_str().to_string(),
422                            token.index,
423                        ))
424                    }
425                },
426                State::ExponentDigit => match c {
427                    _ if c.is_ascii_digit() => {
428                        state = State::ExponentDigit;
429                    }
430                    _ if c == '.' || lookup::is_namestart(c) => {
431                        return Err(Error::with_loc(
432                            format!("Unexpected character `{c}` as float suffix"),
433                            self.current_str().to_string(),
434                            token.index,
435                        ));
436                    }
437                    _ => {
438                        token.data = self.prev_str();
439                        return self.done(token);
440                    }
441                },
442                State::SpreadOperator => {
443                    if c == '.' && self.eatc('.') {
444                        token.data = self.current_str();
445                        return Ok(token);
446                    }
447                    return self.unterminated_spread_operator(&token);
448                }
449                State::MinusSign => match c {
450                    '0' => {
451                        state = State::LeadingZero;
452                    }
453                    curr if curr.is_ascii_digit() => {
454                        state = State::IntegerPart;
455                    }
456                    _ => {
457                        return Err(Error::with_loc(
458                            format!("Unexpected character `{c}`"),
459                            self.current_str().to_string(),
460                            token.index,
461                        ))
462                    }
463                },
464                State::Comment => match c {
465                    curr if is_line_terminator(curr) => {
466                        token.data = self.prev_str();
467                        return self.done(token);
468                    }
469                    _ => {}
470                },
471            }
472        }
473    }
474
475    fn eof(&mut self, state: State, mut token: Token<'a>) -> Result<Token<'a>, Error> {
476        match state {
477            State::Start => {
478                // Report EOF at the end of the input rather than one byte past it.
479                let end = self.source.len();
480                self.offset = end;
481                token.index = end;
482                Ok(token)
483            }
484            State::StringLiteralStart => {
485                let curr = self.current_str();
486
487                Err(Error::with_loc(
488                    "unexpected end of data while lexing string value",
489                    curr.to_string(),
490                    token.index,
491                ))
492            }
493            State::StringLiteral
494            | State::BlockStringLiteral
495            | State::BlockStringLiteralBackslash
496            | State::StringLiteralBackslash => {
497                let curr = self.drain();
498
499                Err(Error::with_loc(
500                    "unterminated string value",
501                    curr.to_string(),
502                    token.index,
503                ))
504            }
505            State::SpreadOperator => self.unterminated_spread_operator(&token),
506            State::MinusSign => Err(Error::with_loc(
507                "Unexpected character \"-\"",
508                self.current_str().to_string(),
509                token.index,
510            )),
511            State::DecimalPoint | State::ExponentIndicator | State::ExponentSign => {
512                Err(Error::with_loc(
513                    "Unexpected EOF in float value",
514                    self.current_str().to_string(),
515                    token.index,
516                ))
517            }
518            State::Ident
519            | State::LeadingZero
520            | State::IntegerPart
521            | State::FractionalPart
522            | State::ExponentDigit
523            | State::Whitespace
524            | State::Comment => {
525                if let Some(mut err) = self.err() {
526                    err.set_data(self.current_str().to_string());
527                    return Err(err);
528                }
529
530                token.data = self.current_str();
531
532                Ok(token)
533            }
534        }
535    }
536
537    fn unterminated_spread_operator(&mut self, token: &Token<'a>) -> Result<Token<'a>, Error> {
538        let data = if self.is_pending() {
539            self.prev_str()
540        } else {
541            self.current_str()
542        };
543
544        Err(Error::with_loc(
545            "Unterminated spread operator",
546            data.to_string(),
547            token.index,
548        ))
549    }
550
551    fn done(&mut self, token: Token<'a>) -> Result<Token<'a>, Error> {
552        if let Some(mut err) = self.err() {
553            err.set_data(token.data.to_string());
554            err.index = token.index;
555            self.err = None;
556            return Err(err);
557        }
558        Ok(token)
559    }
560}
561
562/// Ignored tokens other than comments and commas are assimilated to whitespace
563/// <https://spec.graphql.org/October2021/#Ignored>
564fn is_whitespace_assimilated(c: char) -> bool {
565    matches!(
566        c,
567        // https://spec.graphql.org/October2021/#WhiteSpace
568        '\u{0009}'   // \t
569        | '\u{0020}' // space
570        // https://spec.graphql.org/October2021/#LineTerminator
571        | '\u{000A}' // \n
572        | '\u{000D}' // \r
573        // https://spec.graphql.org/October2021/#UnicodeBOM
574        | '\u{FEFF}' // Unicode BOM (Byte Order Mark)
575    )
576}
577
578/// <https://spec.graphql.org/October2021/#NameContinue>
579fn is_name_continue(c: char) -> bool {
580    matches!(c, 'a'..='z' | 'A'..='Z' | '0'..='9' | '_')
581}
582
583fn is_line_terminator(c: char) -> bool {
584    matches!(c, '\n' | '\r')
585}
586
587// EscapedCharacter
588//     "  \  /  b  f  n  r  t
589fn is_escaped_char(c: char) -> bool {
590    matches!(c, '"' | '\\' | '/' | 'b' | 'f' | 'n' | 'r' | 't')
591}
592
593// Shared by lexing and CST decoding so accepted escapes have identical values.
594pub(crate) fn unicode_escape(input: &str) -> Option<(char, usize)> {
595    let (value, length) = if input.starts_with('{') {
596        let end = input.find('}')?;
597        let digits = &input[1..end];
598        if digits.is_empty() || !digits.bytes().all(|c| c.is_ascii_hexdigit()) {
599            return None;
600        }
601        (u32::from_str_radix(digits, 16).ok()?, end + 1)
602    } else {
603        let digits = input.get(..4)?;
604        if !digits.bytes().all(|c| c.is_ascii_hexdigit()) {
605            return None;
606        }
607        let high = u32::from_str_radix(digits, 16).ok()?;
608        if (0xD800..=0xDBFF).contains(&high) {
609            if input.get(4..6)? != "\\u" {
610                return None;
611            }
612            let low = input.get(6..10)?;
613            if !low.bytes().all(|c| c.is_ascii_hexdigit()) {
614                return None;
615            }
616            let low = u32::from_str_radix(low, 16).ok()?;
617            if !(0xDC00..=0xDFFF).contains(&low) {
618                return None;
619            }
620            (0x10000 + ((high - 0xD800) << 10) + low - 0xDC00, 10)
621        } else {
622            (high, 4)
623        }
624    };
625    Some((char::from_u32(value)?, length))
626}
627
628#[cfg(test)]
629mod test {
630    use super::*;
631
632    #[test]
633    fn unterminated_string() {
634        let schema = r#"
635type Query {
636    name: String
637    format: String = "Y-m-d\\TH:i:sP"
638}
639        "#;
640        let (tokens, errors) = Lexer::new(schema).lex();
641        dbg!(tokens);
642        dbg!(errors);
643    }
644
645    #[test]
646    fn token_limit() {
647        let lexer = Lexer::new("type Query { a a a a a a a a a }").with_limit(10);
648        let (tokens, errors) = lexer.lex();
649        assert_eq!(tokens.len(), 10);
650        assert_eq!(
651            errors,
652            &[Error::limit("token limit reached, aborting lexing", 17)]
653        );
654    }
655
656    #[test]
657    fn token_limit_exact() {
658        let lexer = Lexer::new("type Query { a a a a a a a a a }").with_limit(26);
659        let (tokens, errors) = lexer.lex();
660        assert_eq!(tokens.len(), 26);
661        assert!(errors.is_empty());
662
663        let lexer = Lexer::new("type Query { a a a a a a a a a }").with_limit(25);
664        let (tokens, errors) = lexer.lex();
665        assert_eq!(tokens.len(), 25);
666        assert_eq!(
667            errors,
668            &[Error::limit("token limit reached, aborting lexing", 31)]
669        );
670    }
671
672    #[test]
673    fn errors_and_token_limit() {
674        let lexer = Lexer::new("type Query { ..a a a a a a a a a }").with_limit(10);
675        let (tokens, errors) = lexer.lex();
676        // Errors contribute to the token limit
677        assert_eq!(tokens.len(), 9);
678        assert_eq!(
679            errors,
680            &[
681                Error::with_loc("Unterminated spread operator", "..".to_string(), 13),
682                Error::limit("token limit reached, aborting lexing", 18),
683            ],
684        );
685    }
686
687    #[test]
688    fn stream_produces_original_input() {
689        let schema = r#"
690type Query {
691    name: String
692    format: String = "Y-m-d\\TH:i:sP"
693}
694        "#;
695
696        let lexer = Lexer::new(schema);
697        let processed_schema = lexer
698            .into_iter()
699            .fold(String::new(), |acc, token| acc + token.unwrap().data());
700
701        assert_eq!(schema, processed_schema);
702    }
703
704    #[test]
705    fn quoted_block_comment() {
706        let input = r#"
707"""
708Not an escape character:
709'/\W/'
710Escape character:
711\"""
712\"""\"""
713Not escape characters:
714\" \""
715Escape character followed by a quote:
716\""""
717"""
718        "#;
719
720        let (tokens, errors) = Lexer::new(input).lex();
721        assert!(errors.is_empty());
722        // The token data should be literally the source text.
723        assert_eq!(
724            tokens[1].data,
725            r#"
726"""
727Not an escape character:
728'/\W/'
729Escape character:
730\"""
731\"""\"""
732Not escape characters:
733\" \""
734Escape character followed by a quote:
735\""""
736"""
737"#
738            .trim(),
739        );
740
741        let input = r#"
742# String contents: """
743"""\""""""
744# Unclosed block string
745"""\"""
746        "#;
747        let (tokens, errors) = Lexer::new(input).lex();
748        assert_eq!(tokens[3].data, r#""""\"""""""#);
749        assert_eq!(
750            errors,
751            &[Error::with_loc(
752                "unterminated string value",
753                r#""""\"""
754        "#
755                .to_string(),
756                59,
757            )]
758        );
759    }
760
761    #[test]
762    fn unexpected_character() {
763        let schema = r#"
764type Query {
765    name: String
766}
767/
768        "#;
769        let (tokens, errors) = Lexer::new(schema).lex();
770        dbg!(tokens);
771        assert_eq!(
772            errors,
773            &[Error::with_loc(
774                "Unexpected character \"/\"",
775                "/".to_string(),
776                33,
777            )]
778        );
779    }
780}
reed_parser/lexer/mod.rs

reed_parser/lexer/
mod.rs
