oxc_graphql_parser/lexer/
mod.rs

1mod cursor;
2mod lookup;
3mod token;
4mod token_kind;
5
6use crate::Error;
7use crate::LimitTracker;
8use crate::lexer::cursor::Cursor;
9use crate::lexer::lookup::ByteClass;
10pub use token::Token;
11pub use token_kind::TokenKind;
12
13/// Parses GraphQL source text into tokens.
14/// ```rust
15/// use oxc_graphql_parser::Lexer;
16///
17/// let query = "
18/// {
19///     animal
20///     ...snackSelection
21///     ... on Pet {
22///       playmates {
23///         count
24///       }
25///     }
26/// }
27/// ";
28/// let (tokens, errors) = Lexer::new(query).lex();
29/// assert_eq!(errors.len(), 0);
30/// ```
31#[derive(Debug)]
32pub struct Lexer<'a> {
33    finished: bool,
34    cursor: Cursor<'a>,
35    pub(crate) limit_tracker: LimitTracker,
36}
37
38/// States of the number token state machine.
39enum NumberState {
40    MinusSign,
41    LeadingZero,
42    IntegerPart,
43    DecimalPoint,
44    FractionalPart,
45    ExponentIndicator,
46    ExponentSign,
47    ExponentDigit,
48}
49
50impl<'a> Lexer<'a> {
51    /// Create a lexer for a GraphQL source text.
52    ///
53    /// The Lexer is an iterator over tokens and errors:
54    /// ```rust
55    /// use oxc_graphql_parser::Lexer;
56    ///
57    /// let query = "# --- GraphQL here ---";
58    ///
59    /// let mut lexer = Lexer::new(query);
60    /// let mut tokens = vec![];
61    /// for token in lexer {
62    ///     match token {
63    ///         Ok(token) => tokens.push(token),
64    ///         Err(error) => panic!("{:?}", error),
65    ///     }
66    /// }
67    /// ```
68    pub fn new(input: &'a str) -> Self {
69        Self {
70            cursor: Cursor::new(input),
71            finished: false,
72            limit_tracker: LimitTracker::new(usize::MAX),
73        }
74    }
75
76    pub fn with_limit(mut self, limit: usize) -> Self {
77        self.limit_tracker = LimitTracker::new(limit);
78        self
79    }
80
81    /// Lex the full source text, consuming the lexer.
82    pub fn lex(self) -> (Vec<Token<'a>>, Vec<Error>) {
83        let mut tokens = vec![];
84        let mut errors = vec![];
85
86        for item in self {
87            match item {
88                Ok(token) => tokens.push(token),
89                Err(error) => errors.push(error),
90            }
91        }
92
93        (tokens, errors)
94    }
95
96    /// Returns the next token, skipping whitespace and comma trivia without
97    /// materializing tokens for them. Comments are returned so the caller can
98    /// record their spans.
99    ///
100    /// Each skipped trivia token still counts toward the token limit, exactly
101    /// as if it had been yielded by the iterator.
102    pub(crate) fn next_significant(&mut self) -> Option<Result<Token<'a>, Error>> {
103        if self.finished {
104            return None;
105        }
106
107        loop {
108            if self.limit_tracker.check_and_increment() {
109                self.finished = true;
110                return Some(Err(Error::limit(
111                    "token limit reached, aborting lexing",
112                    self.cursor.index(),
113                )));
114            }
115
116            if self.cursor.skip_trivia() {
117                continue;
118            }
119
120            return match self.cursor.advance() {
121                Ok(token) => {
122                    if matches!(token.kind(), TokenKind::Eof) {
123                        self.finished = true;
124                    }
125
126                    Some(Ok(token))
127                }
128                Err(err) => Some(Err(err)),
129            };
130        }
131    }
132}
133
134impl<'a> Iterator for Lexer<'a> {
135    type Item = Result<Token<'a>, Error>;
136
137    #[inline]
138    fn next(&mut self) -> Option<Self::Item> {
139        if self.finished {
140            return None;
141        }
142
143        if self.limit_tracker.check_and_increment() {
144            self.finished = true;
145            return Some(Err(Error::limit(
146                "token limit reached, aborting lexing",
147                self.cursor.index(),
148            )));
149        }
150
151        match self.cursor.advance() {
152            Ok(token) => {
153                if matches!(token.kind(), TokenKind::Eof) {
154                    self.finished = true;
155                }
156
157                Some(Ok(token))
158            }
159            Err(err) => Some(Err(err)),
160        }
161    }
162}
163
164impl<'a> Cursor<'a> {
165    fn advance(&mut self) -> Result<Token<'a>, Error> {
166        // A pending error is only ever set and consumed within `lex_string`;
167        // every other token starts with a clean slate.
168        debug_assert!(self.err.is_none());
169
170        let mut token = Token { kind: TokenKind::Eof, data: "", index: self.index() };
171
172        let Some(c) = self.bump() else {
173            // Report EOF at the end of the input rather than one byte past it.
174            let end = self.source.len();
175            self.offset = end;
176            token.index = end;
177            return Ok(token);
178        };
179
180        match lookup::byte_class(c) {
181            ByteClass::Bang => self.punctuation(token, TokenKind::Bang),
182            ByteClass::Dollar => self.punctuation(token, TokenKind::Dollar),
183            ByteClass::Amp => self.punctuation(token, TokenKind::Amp),
184            ByteClass::LParen => self.punctuation(token, TokenKind::LParen),
185            ByteClass::RParen => self.punctuation(token, TokenKind::RParen),
186            ByteClass::Comma => self.punctuation(token, TokenKind::Comma),
187            ByteClass::Colon => self.punctuation(token, TokenKind::Colon),
188            ByteClass::Eq => self.punctuation(token, TokenKind::Eq),
189            ByteClass::At => self.punctuation(token, TokenKind::At),
190            ByteClass::LBracket => self.punctuation(token, TokenKind::LBracket),
191            ByteClass::RBracket => self.punctuation(token, TokenKind::RBracket),
192            ByteClass::LCurly => self.punctuation(token, TokenKind::LCurly),
193            ByteClass::RCurly => self.punctuation(token, TokenKind::RCurly),
194            ByteClass::Pipe => self.punctuation(token, TokenKind::Pipe),
195            ByteClass::Name => {
196                token.kind = TokenKind::Name;
197                token.data = self.consume_name();
198                Ok(token)
199            }
200            ByteClass::Whitespace => {
201                token.kind = TokenKind::Whitespace;
202                token.data = self.consume_whitespace();
203                Ok(token)
204            }
205            ByteClass::Bom => {
206                if self.eat_bom() {
207                    token.kind = TokenKind::Whitespace;
208                    token.data = self.consume_whitespace();
209                    Ok(token)
210                } else {
211                    self.unexpected_character(c, &token)
212                }
213            }
214            ByteClass::Quote => self.lex_string_start(token),
215            ByteClass::Hash => self.lex_comment(token),
216            ByteClass::Dot => self.lex_spread(token),
217            ByteClass::Zero => self.lex_number(NumberState::LeadingZero, token),
218            ByteClass::Digit => self.lex_number(NumberState::IntegerPart, token),
219            ByteClass::Minus => self.lex_number(NumberState::MinusSign, token),
220            ByteClass::Other => self.unexpected_character(c, &token),
221        }
222    }
223
224    /// Skips one trivia token (whitespace run or comma) without materializing
225    /// it. Returns `false` when the next token is significant. Comments are
226    /// not skipped: callers record their spans, so they lex as normal tokens.
227    fn skip_trivia(&mut self) -> bool {
228        let Some(&c) = self.bytes.get(self.next) else {
229            return false;
230        };
231        match lookup::byte_class(c) {
232            ByteClass::Whitespace => {
233                self.bump();
234                self.consume_whitespace();
235                true
236            }
237            ByteClass::Comma => {
238                self.bump();
239                // Update the cursor position exactly like lexing the token would.
240                let _ = self.current_str();
241                true
242            }
243            ByteClass::Bom if self.at_bom() => {
244                self.bump();
245                self.eat_bom();
246                self.consume_whitespace();
247                true
248            }
249            _ => false,
250        }
251    }
252
253    #[inline]
254    fn punctuation(&mut self, mut token: Token<'a>, kind: TokenKind) -> Result<Token<'a>, Error> {
255        token.kind = kind;
256        token.data = self.current_str();
257        Ok(token)
258    }
259
260    fn lex_comment(&mut self, mut token: Token<'a>) -> Result<Token<'a>, Error> {
261        token.kind = TokenKind::Comment;
262        let start = self.index;
263        let end = self.seek_line_end();
264        token.data = &self.source[start..end];
265        Ok(token)
266    }
267
268    fn lex_spread(&mut self, mut token: Token<'a>) -> Result<Token<'a>, Error> {
269        token.kind = TokenKind::Spread;
270        if let Some(c) = self.bump() {
271            if c == b'.' {
272                if self.eatc(b'.') {
273                    token.data = self.current_str();
274                    return Ok(token);
275                }
276            } else if !c.is_ascii() {
277                // Consume the whole character so the error data slices at a
278                // character boundary.
279                self.consume_current_char();
280            }
281        }
282        let data = self.current_str();
283        Err(Error::with_loc("Unterminated spread operator", data.to_string(), token.index))
284    }
285
286    fn lex_string_start(&mut self, mut token: Token<'a>) -> Result<Token<'a>, Error> {
287        token.kind = TokenKind::StringValue;
288
289        if self.eatc(b'"') {
290            if self.eatc(b'"') {
291                return self.lex_block_string(token);
292            }
293
294            // Empty string: `""`.
295            token.data = self.current_str();
296            return Ok(token);
297        }
298
299        if self.next == self.bytes.len() {
300            // A lone `"` at the end of the input.
301            return Err(Error::with_loc(
302                "unexpected end of data while lexing string value",
303                self.current_str().to_string(),
304                token.index,
305            ));
306        }
307
308        self.lex_string(token)
309    }
310
311    fn lex_string(&mut self, mut token: Token<'a>) -> Result<Token<'a>, Error> {
312        loop {
313            let Some(found) = memchr::memchr2(b'"', b'\\', &self.bytes[self.next..]) else {
314                return self.unterminated_string(&token);
315            };
316            let stop = self.next + found;
317
318            if memchr::memchr2(b'\n', b'\r', &self.bytes[self.next..stop]).is_some() {
319                self.add_err(Error::with_loc("unexpected line terminator", String::new(), 0));
320            }
321
322            // Consume through the stop byte.
323            self.offset = stop;
324            self.next = stop + 1;
325
326            if self.bytes[stop] == b'"' {
327                token.data = self.current_str();
328                return self.done(token);
329            }
330
331            // Backslash escape sequence.
332            let Some(c) = self.bump() else {
333                return self.unterminated_string(&token);
334            };
335            if c == b'u' {
336                // `\uXXXX`: four hex digits. A non-hex byte is consumed as
337                // plain string content after recording an error.
338                for remaining in (1..=4usize).rev() {
339                    let Some(c) = self.bump() else {
340                        return self.unterminated_string(&token);
341                    };
342                    if c == b'"' {
343                        self.add_err(Error::with_loc(
344                            "incomplete unicode escape sequence",
345                            char::from(c).to_string(),
346                            token.index,
347                        ));
348                        token.data = self.current_str();
349                        return self.done(token);
350                    }
351                    if !c.is_ascii_hexdigit() {
352                        self.add_err(Error::with_loc(
353                            "invalid unicode escape sequence",
354                            c.to_string(),
355                            0,
356                        ));
357                        break;
358                    }
359                    if remaining == 1 {
360                        let hex_end = self.offset + 1;
361                        let hex_start = hex_end - 4;
362                        let hex = &self.source[hex_start..hex_end];
363                        // `is_ascii_hexdigit()` checks in previous iterations ensures
364                        // this `unwrap()` does not panic:
365                        let code_point = u32::from_str_radix(hex, 16).unwrap();
366                        if char::from_u32(code_point).is_none() {
367                            // TODO: https://github.com/oxc-project/oxc-graphql-parser/issues/657 needs
368                            // changes both here and in `ast/node_ext.rs`
369                            let escape_sequence_start = hex_start - 2; // include "\u"
370                            let escape_sequence = &self.source[escape_sequence_start..hex_end];
371                            self.add_err(Error::with_loc(
372                                "surrogate code point is invalid in unicode escape sequence \
373                                 (paired surrogate not supported yet: \
374                                 https://github.com/oxc-project/oxc-graphql-parser/issues/657)",
375                                escape_sequence.to_owned(),
376                                0,
377                            ));
378                        }
379                    }
380                }
381            } else if !is_escaped_char(c) {
382                let c = self.char_for_error(c);
383                self.add_err(Error::with_loc("unexpected escaped character", c.to_string(), 0));
384            }
385        }
386    }
387
388    fn lex_block_string(&mut self, mut token: Token<'a>) -> Result<Token<'a>, Error> {
389        loop {
390            let Some(found) = memchr::memchr2(b'"', b'\\', &self.bytes[self.next..]) else {
391                return self.unterminated_string(&token);
392            };
393            let stop = self.next + found;
394
395            // Consume through the stop byte.
396            self.offset = stop;
397            self.next = stop + 1;
398
399            if self.bytes[stop] == b'"' {
400                // Require two additional quotes to complete the triple quote;
401                // a lone second quote is consumed as content.
402                if self.eatc(b'"') && self.eatc(b'"') {
403                    token.data = self.current_str();
404                    return self.done(token);
405                }
406                continue;
407            }
408
409            // Backslash. If this is \""", we need to eat 3 in total, and then
410            // continue. The lexer does not un-escape escape sequences so it's
411            // OK if we take this path for \"", even if that is technically not
412            // an escape sequence. It's also legal to write \\\""" with two
413            // literal backslashes and then the escape sequence.
414            loop {
415                let Some(c) = self.bump() else {
416                    return self.unterminated_string(&token);
417                };
418                match c {
419                    b'\\' => {}
420                    b'"' => {
421                        if self.eatc(b'"') {
422                            self.eatc(b'"');
423                        }
424                        break;
425                    }
426                    _ => break,
427                }
428            }
429        }
430    }
431
432    fn lex_number(
433        &mut self,
434        mut state: NumberState,
435        mut token: Token<'a>,
436    ) -> Result<Token<'a>, Error> {
437        token.kind = TokenKind::Int;
438
439        loop {
440            let Some(c) = self.bump() else {
441                return match state {
442                    NumberState::MinusSign => Err(Error::with_loc(
443                        "Unexpected character \"-\"",
444                        self.current_str().to_string(),
445                        token.index,
446                    )),
447                    NumberState::DecimalPoint
448                    | NumberState::ExponentIndicator
449                    | NumberState::ExponentSign => Err(Error::with_loc(
450                        "Unexpected EOF in float value",
451                        self.current_str().to_string(),
452                        token.index,
453                    )),
454                    NumberState::LeadingZero
455                    | NumberState::IntegerPart
456                    | NumberState::FractionalPart
457                    | NumberState::ExponentDigit => {
458                        token.data = self.current_str();
459                        Ok(token)
460                    }
461                };
462            };
463
464            match state {
465                NumberState::MinusSign => match c {
466                    b'0' => {
467                        state = NumberState::LeadingZero;
468                    }
469                    curr if curr.is_ascii_digit() => {
470                        state = NumberState::IntegerPart;
471                    }
472                    _ => {
473                        let c = self.char_for_error(c);
474                        return Err(Error::with_loc(
475                            format!("Unexpected character `{c}`"),
476                            self.current_str().to_string(),
477                            token.index,
478                        ));
479                    }
480                },
481                NumberState::LeadingZero => match c {
482                    b'.' => {
483                        token.kind = TokenKind::Float;
484                        state = NumberState::DecimalPoint;
485                    }
486                    b'e' | b'E' => {
487                        token.kind = TokenKind::Float;
488                        state = NumberState::ExponentIndicator;
489                    }
490                    _ if c.is_ascii_digit() => {
491                        return Err(Error::with_loc(
492                            "Numbers must not have non-significant leading zeroes",
493                            self.current_str().to_string(),
494                            token.index,
495                        ));
496                    }
497                    _ if lookup::is_namestart(c) => {
498                        let c = char::from(c);
499                        return Err(Error::with_loc(
500                            format!("Unexpected character `{c}` as integer suffix"),
501                            self.current_str().to_string(),
502                            token.index,
503                        ));
504                    }
505                    _ => {
506                        token.data = self.prev_str();
507                        return Ok(token);
508                    }
509                },
510                NumberState::IntegerPart => match c {
511                    curr if curr.is_ascii_digit() => {}
512                    b'.' => {
513                        token.kind = TokenKind::Float;
514                        state = NumberState::DecimalPoint;
515                    }
516                    b'e' | b'E' => {
517                        token.kind = TokenKind::Float;
518                        state = NumberState::ExponentIndicator;
519                    }
520                    _ if lookup::is_namestart(c) => {
521                        let c = char::from(c);
522                        return Err(Error::with_loc(
523                            format!("Unexpected character `{c}` as integer suffix"),
524                            self.current_str().to_string(),
525                            token.index,
526                        ));
527                    }
528                    _ => {
529                        token.data = self.prev_str();
530                        return Ok(token);
531                    }
532                },
533                NumberState::DecimalPoint => match c {
534                    curr if curr.is_ascii_digit() => {
535                        state = NumberState::FractionalPart;
536                    }
537                    _ => {
538                        let c = self.char_for_error(c);
539                        return Err(Error::with_loc(
540                            format!("Unexpected character `{c}`, expected fractional digit"),
541                            self.current_str().to_string(),
542                            token.index,
543                        ));
544                    }
545                },
546                NumberState::FractionalPart => match c {
547                    curr if curr.is_ascii_digit() => {}
548                    b'e' | b'E' => {
549                        state = NumberState::ExponentIndicator;
550                    }
551                    _ if c == b'.' || lookup::is_namestart(c) => {
552                        let c = char::from(c);
553                        return Err(Error::with_loc(
554                            format!("Unexpected character `{c}` as float suffix"),
555                            self.current_str().to_string(),
556                            token.index,
557                        ));
558                    }
559                    _ => {
560                        token.data = self.prev_str();
561                        return Ok(token);
562                    }
563                },
564                NumberState::ExponentIndicator => match c {
565                    _ if c.is_ascii_digit() => {
566                        state = NumberState::ExponentDigit;
567                    }
568                    b'+' | b'-' => {
569                        state = NumberState::ExponentSign;
570                    }
571                    _ => {
572                        let c = self.char_for_error(c);
573                        return Err(Error::with_loc(
574                            format!("Unexpected character `{c}`, expected exponent digit or sign"),
575                            self.current_str().to_string(),
576                            token.index,
577                        ));
578                    }
579                },
580                NumberState::ExponentSign => match c {
581                    _ if c.is_ascii_digit() => {
582                        state = NumberState::ExponentDigit;
583                    }
584                    _ => {
585                        let c = self.char_for_error(c);
586                        return Err(Error::with_loc(
587                            format!("Unexpected character `{c}`, expected exponent digit"),
588                            self.current_str().to_string(),
589                            token.index,
590                        ));
591                    }
592                },
593                NumberState::ExponentDigit => match c {
594                    _ if c.is_ascii_digit() => {}
595                    _ if c == b'.' || lookup::is_namestart(c) => {
596                        let c = char::from(c);
597                        return Err(Error::with_loc(
598                            format!("Unexpected character `{c}` as float suffix"),
599                            self.current_str().to_string(),
600                            token.index,
601                        ));
602                    }
603                    _ => {
604                        token.data = self.prev_str();
605                        return Ok(token);
606                    }
607                },
608            }
609        }
610    }
611
612    fn unexpected_character(&mut self, c: u8, token: &Token<'a>) -> Result<Token<'a>, Error> {
613        let c = self.char_for_error(c);
614        Err(Error::with_loc(
615            format!(r#"Unexpected character "{c}""#),
616            self.current_str().to_string(),
617            token.index,
618        ))
619    }
620
621    fn unterminated_string(&mut self, token: &Token<'a>) -> Result<Token<'a>, Error> {
622        // Any pending in-string error is superseded by the unterminated error
623        // (it was never observable: only the EOF token can follow a drain).
624        self.err = None;
625        Err(Error::with_loc("unterminated string value", self.drain().to_string(), token.index))
626    }
627
628    fn char_for_error(&mut self, c: u8) -> char {
629        if c.is_ascii() { char::from(c) } else { self.consume_current_char() }
630    }
631
632    #[inline]
633    fn done(&mut self, token: Token<'a>) -> Result<Token<'a>, Error> {
634        if let Some(mut err) = self.err.take() {
635            err.set_data(token.data.to_string());
636            err.index = token.index;
637            return Err(err);
638        }
639        Ok(token)
640    }
641}
642
643/// Ignored tokens other than comments and commas are assimilated to whitespace
644/// <https://spec.graphql.org/October2021/#Ignored>
645fn is_whitespace_assimilated(c: u8) -> bool {
646    matches!(
647        c,
648        // https://spec.graphql.org/October2021/#WhiteSpace
649        b'\t'
650        | b' '
651        // https://spec.graphql.org/October2021/#LineTerminator
652        | b'\n'
653        | b'\r'
654    )
655}
656
657/// <https://spec.graphql.org/October2021/#NameContinue>
658fn is_name_continue(c: u8) -> bool {
659    matches!(c, b'a'..=b'z' | b'A'..=b'Z' | b'0'..=b'9' | b'_')
660}
661
662// EscapedCharacter
663//     "  \  /  b  f  n  r  t
664fn is_escaped_char(c: u8) -> bool {
665    matches!(c, b'"' | b'\\' | b'/' | b'b' | b'f' | b'n' | b'r' | b't')
666}
oxc_graphql_parser/lexer/mod.rs

oxc_graphql_parser/lexer/
mod.rs
