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#[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 StringLiteralEscapedUnicode {
45 remaining: usize,
46 value: u32,
47 pair_trail: bool,
48 },
49 StringLiteralEscapedUnicodeVariable {
52 value: u32,
53 start: usize,
54 },
55 StringLiteralLeadSurrogate,
58 StringLiteralLeadSurrogateBackslash,
59 StringLiteral,
60 StringLiteralStart,
61 BlockStringLiteral,
62 BlockStringLiteralBackslash,
63 StringLiteralBackslash,
64 LeadingZero,
65 IntegerPart,
66 DecimalPoint,
67 FractionalPart,
68 ExponentIndicator,
69 ExponentSign,
70 ExponentDigit,
71 Whitespace,
72 Comment,
73 SpreadOperator,
74 MinusSign,
75}
76
77impl<'a> Lexer<'a> {
78 pub fn new(input: &'a str) -> Self {
96 Self {
97 cursor: Cursor::new(input),
98 finished: false,
99 limit_tracker: LimitTracker::new(usize::MAX),
100 }
101 }
102
103 pub fn with_limit(mut self, limit: usize) -> Self {
104 self.limit_tracker = LimitTracker::new(limit);
105 self
106 }
107
108 pub fn lex(self) -> (Vec<Token<'a>>, Vec<Error>) {
110 let mut tokens = vec![];
111 let mut errors = vec![];
112
113 for item in self {
114 match item {
115 Ok(token) => tokens.push(token),
116 Err(error) => errors.push(error),
117 }
118 }
119
120 (tokens, errors)
121 }
122}
123
124impl<'a> Iterator for Lexer<'a> {
125 type Item = Result<Token<'a>, Error>;
126
127 fn next(&mut self) -> Option<Self::Item> {
128 if self.finished {
129 return None;
130 }
131
132 if self.limit_tracker.check_and_increment() {
133 self.finished = true;
134 return Some(Err(Error::limit(
135 "token limit reached, aborting lexing",
136 self.cursor.index(),
137 )));
138 }
139
140 match self.cursor.advance() {
141 Ok(token) => {
142 if matches!(token.kind(), TokenKind::Eof) {
143 self.finished = true;
144 }
145
146 Some(Ok(token))
147 }
148 Err(err) => Some(Err(err)),
149 }
150 }
151}
152
153impl<'a> Cursor<'a> {
154 fn advance(&mut self) -> Result<Token<'a>, Error> {
155 let mut state = State::Start;
156 let mut token = Token {
157 kind: TokenKind::Eof,
158 data: "",
159 index: self.index(),
160 };
161
162 loop {
163 let Some(c) = self.bump() else {
164 return self.eof(state, token);
165 };
166 match state {
167 State::Start => {
168 if let Some(t) = lookup::punctuation_kind(c) {
169 token.kind = t;
170 token.data = self.current_str();
171 return Ok(token);
172 }
173
174 if lookup::is_namestart(c) {
175 token.kind = TokenKind::Name;
176 state = State::Ident;
177
178 continue;
179 }
180
181 if c != '0' && c.is_ascii_digit() {
182 token.kind = TokenKind::Int;
183 state = State::IntegerPart;
184
185 continue;
186 }
187
188 match c {
189 '"' => {
190 token.kind = TokenKind::StringValue;
191 state = State::StringLiteralStart;
192 }
193 '#' => {
194 token.kind = TokenKind::Comment;
195 state = State::Comment;
196 }
197 '.' => {
198 token.kind = TokenKind::Spread;
199 state = State::SpreadOperator;
200 }
201 '-' => {
202 token.kind = TokenKind::Int;
203 state = State::MinusSign;
204 }
205 '0' => {
206 token.kind = TokenKind::Int;
207 state = State::LeadingZero;
208 }
209 c if is_whitespace_assimilated(c) => {
210 token.kind = TokenKind::Whitespace;
211 state = State::Whitespace;
212 }
213 c => {
214 return Err(Error::with_loc(
215 format!(r#"Unexpected character "{c}""#),
216 self.current_str().to_string(),
217 token.index,
218 ));
219 }
220 };
221 }
222 State::Ident => match c {
223 curr if is_name_continue(curr) => {}
224 _ => {
225 token.data = self.prev_str();
226 return self.done(token);
227 }
228 },
229 State::Whitespace => match c {
230 curr if is_whitespace_assimilated(curr) => {}
231 _ => {
232 token.data = self.prev_str();
233 return self.done(token);
234 }
235 },
236 State::BlockStringLiteral => match c {
237 '\\' => {
238 state = State::BlockStringLiteralBackslash;
239 }
240 '"'
241 if self.eatc('"') && self.eatc('"') => {
243 token.data = self.current_str();
244 return self.done(token);
245 }
246 _ => {}
247 },
248 State::StringLiteralStart => match c {
249 '"' => {
250 if self.eatc('"') {
251 state = State::BlockStringLiteral;
252
253 continue;
254 }
255
256 if self.is_pending() {
257 token.data = self.prev_str();
258 } else {
259 token.data = self.current_str();
260 }
261 return self.done(token);
262 }
263 '\\' => {
264 state = State::StringLiteralBackslash;
265 }
266 _ => {
267 state = State::StringLiteral;
268
269 continue;
270 }
271 },
272 State::StringLiteralEscapedUnicode {
273 remaining,
274 value,
275 pair_trail,
276 } => match c {
277 '"' => {
278 self.add_err(Error::with_loc(
279 "incomplete unicode escape sequence",
280 c.to_string(),
281 token.index,
282 ));
283 token.data = self.current_str();
284 return self.done(token);
285 }
286 '{' if remaining == 4 && !pair_trail => {
287 state = State::StringLiteralEscapedUnicodeVariable {
288 value: 0,
289 start: self.offset,
290 };
291 }
292 c if !c.is_ascii_hexdigit() => {
293 self.add_err(Error::with_loc(
294 "invalid unicode escape sequence",
295 c.to_string(),
296 0,
297 ));
298 state = State::StringLiteral;
299
300 continue;
301 }
302 _ => {
303 let value = (value << 4) + c.to_digit(16).unwrap();
306 if remaining > 1 {
307 state = State::StringLiteralEscapedUnicode {
308 remaining: remaining - 1,
309 value,
310 pair_trail,
311 };
312 continue;
313 }
314
315 let hex_end = self.offset + 1;
320 if pair_trail {
321 if !(0xDC00..=0xDFFF).contains(&value) {
322 let escape_sequence_start = hex_end - 12; let escape_sequence = &self.source[escape_sequence_start..hex_end];
324 self.add_err(Error::with_loc(
325 "unpaired surrogate in unicode escape sequence",
326 escape_sequence.to_owned(),
327 0,
328 ));
329 }
330 state = State::StringLiteral;
331 } else if (0xD800..=0xDBFF).contains(&value) {
332 state = State::StringLiteralLeadSurrogate;
333 } else if (0xDC00..=0xDFFF).contains(&value) {
334 let escape_sequence_start = hex_end - 6; let escape_sequence = &self.source[escape_sequence_start..hex_end];
336 self.add_err(Error::with_loc(
337 "unpaired surrogate in unicode escape sequence",
338 escape_sequence.to_owned(),
339 0,
340 ));
341 state = State::StringLiteral;
342 } else {
343 state = State::StringLiteral;
344 }
345 }
346 },
347 State::StringLiteralEscapedUnicodeVariable { value, start } => match c {
348 '}' => {
349 let has_digits = self.offset > start + 1;
350 if !has_digits || char::from_u32(value).is_none() {
353 let escape_sequence = &self.source[start - 2..=self.offset];
354 self.add_err(Error::with_loc(
355 "unicode escape sequence must specify a Unicode scalar value",
356 escape_sequence.to_owned(),
357 0,
358 ));
359 }
360 state = State::StringLiteral;
361 }
362 '"' => {
363 self.add_err(Error::with_loc(
364 "incomplete unicode escape sequence",
365 c.to_string(),
366 token.index,
367 ));
368 token.data = self.current_str();
369 return self.done(token);
370 }
371 c if c.is_ascii_hexdigit() => {
372 state = State::StringLiteralEscapedUnicodeVariable {
376 value: value
377 .saturating_mul(16)
378 .saturating_add(c.to_digit(16).unwrap()),
379 start,
380 };
381 }
382 _ => {
383 self.add_err(Error::with_loc(
384 "invalid unicode escape sequence",
385 c.to_string(),
386 0,
387 ));
388 state = State::StringLiteral;
389 }
390 },
391 State::StringLiteralLeadSurrogate => match c {
392 '\\' => {
393 state = State::StringLiteralLeadSurrogateBackslash;
394 }
395 '"' => {
396 self.add_err(Error::with_loc(
397 "unpaired surrogate in unicode escape sequence",
398 c.to_string(),
399 token.index,
400 ));
401 token.data = self.current_str();
402 return self.done(token);
403 }
404 _ => {
405 self.add_err(Error::with_loc(
406 "unpaired surrogate in unicode escape sequence",
407 c.to_string(),
408 0,
409 ));
410 state = State::StringLiteral;
411 }
412 },
413 State::StringLiteralLeadSurrogateBackslash => match c {
414 'u' => {
415 state = State::StringLiteralEscapedUnicode {
416 remaining: 4,
417 value: 0,
418 pair_trail: true,
419 };
420 }
421 _ => {
422 self.add_err(Error::with_loc(
423 "unpaired surrogate in unicode escape sequence",
424 c.to_string(),
425 0,
426 ));
427 state = State::StringLiteral;
428 }
429 },
430 State::StringLiteral => match c {
431 '"' => {
432 token.data = self.current_str();
433 return self.done(token);
434 }
435 curr if is_line_terminator(curr) => {
436 self.add_err(Error::with_loc(
437 "unexpected line terminator",
438 "".to_string(),
439 0,
440 ));
441 }
442 '\\' => {
443 state = State::StringLiteralBackslash;
444 }
445 _ => {}
446 },
447 State::BlockStringLiteralBackslash => match c {
448 '"' => {
449 if self.eatc('"') {
454 self.eatc('"');
455 }
456
457 state = State::BlockStringLiteral;
458 }
459 '\\' => {
460 }
464 _ => {
465 state = State::BlockStringLiteral;
466 }
467 },
468 State::StringLiteralBackslash => match c {
469 curr if is_escaped_char(curr) => {
470 state = State::StringLiteral;
471 }
472 'u' => {
473 state = State::StringLiteralEscapedUnicode {
474 remaining: 4,
475 value: 0,
476 pair_trail: false,
477 };
478 }
479 _ => {
480 self.add_err(Error::with_loc(
481 "unexpected escaped character",
482 c.to_string(),
483 0,
484 ));
485
486 state = State::StringLiteral;
487 }
488 },
489 State::LeadingZero => match c {
490 '.' => {
491 token.kind = TokenKind::Float;
492 state = State::DecimalPoint;
493 }
494 'e' | 'E' => {
495 token.kind = TokenKind::Float;
496 state = State::ExponentIndicator;
497 }
498 _ if c.is_ascii_digit() => {
499 return Err(Error::with_loc(
500 "Numbers must not have non-significant leading zeroes",
501 self.current_str().to_string(),
502 token.index,
503 ));
504 }
505 _ if lookup::is_namestart(c) => {
506 return Err(Error::with_loc(
507 format!("Unexpected character `{c}` as integer suffix"),
508 self.current_str().to_string(),
509 token.index,
510 ));
511 }
512 _ => {
513 token.data = self.prev_str();
514 return self.done(token);
515 }
516 },
517 State::IntegerPart => match c {
518 curr if curr.is_ascii_digit() => {}
519 '.' => {
520 token.kind = TokenKind::Float;
521 state = State::DecimalPoint;
522 }
523 'e' | 'E' => {
524 token.kind = TokenKind::Float;
525 state = State::ExponentIndicator;
526 }
527 _ if lookup::is_namestart(c) => {
528 return Err(Error::with_loc(
529 format!("Unexpected character `{c}` as integer suffix"),
530 self.current_str().to_string(),
531 token.index,
532 ));
533 }
534 _ => {
535 token.data = self.prev_str();
536 return self.done(token);
537 }
538 },
539 State::DecimalPoint => match c {
540 curr if curr.is_ascii_digit() => {
541 state = State::FractionalPart;
542 }
543 _ => {
544 return Err(Error::with_loc(
545 format!("Unexpected character `{c}`, expected fractional digit"),
546 self.current_str().to_string(),
547 token.index,
548 ));
549 }
550 },
551 State::FractionalPart => match c {
552 curr if curr.is_ascii_digit() => {}
553 'e' | 'E' => {
554 state = State::ExponentIndicator;
555 }
556 _ if c == '.' || lookup::is_namestart(c) => {
557 return Err(Error::with_loc(
558 format!("Unexpected character `{c}` as float suffix"),
559 self.current_str().to_string(),
560 token.index,
561 ));
562 }
563 _ => {
564 token.data = self.prev_str();
565 return self.done(token);
566 }
567 },
568 State::ExponentIndicator => match c {
569 _ if c.is_ascii_digit() => {
570 state = State::ExponentDigit;
571 }
572 '+' | '-' => {
573 state = State::ExponentSign;
574 }
575 _ => {
576 return Err(Error::with_loc(
577 format!("Unexpected character `{c}`, expected exponent digit or sign"),
578 self.current_str().to_string(),
579 token.index,
580 ))
581 }
582 },
583 State::ExponentSign => match c {
584 _ if c.is_ascii_digit() => {
585 state = State::ExponentDigit;
586 }
587 _ => {
588 return Err(Error::with_loc(
589 format!("Unexpected character `{c}`, expected exponent digit"),
590 self.current_str().to_string(),
591 token.index,
592 ))
593 }
594 },
595 State::ExponentDigit => match c {
596 _ if c.is_ascii_digit() => {
597 state = State::ExponentDigit;
598 }
599 _ if c == '.' || lookup::is_namestart(c) => {
600 return Err(Error::with_loc(
601 format!("Unexpected character `{c}` as float suffix"),
602 self.current_str().to_string(),
603 token.index,
604 ));
605 }
606 _ => {
607 token.data = self.prev_str();
608 return self.done(token);
609 }
610 },
611 State::SpreadOperator => {
612 if c == '.' && self.eatc('.') {
613 token.data = self.current_str();
614 return Ok(token);
615 }
616 return self.unterminated_spread_operator(&token);
617 }
618 State::MinusSign => match c {
619 '0' => {
620 state = State::LeadingZero;
621 }
622 curr if curr.is_ascii_digit() => {
623 state = State::IntegerPart;
624 }
625 _ => {
626 return Err(Error::with_loc(
627 format!("Unexpected character `{c}`"),
628 self.current_str().to_string(),
629 token.index,
630 ))
631 }
632 },
633 State::Comment => match c {
634 curr if is_line_terminator(curr) => {
635 token.data = self.prev_str();
636 return self.done(token);
637 }
638 _ => {}
639 },
640 }
641 }
642 }
643
644 fn eof(&mut self, state: State, mut token: Token<'a>) -> Result<Token<'a>, Error> {
645 match state {
646 State::Start => {
647 let end = self.source.len();
649 self.offset = end;
650 token.index = end;
651 Ok(token)
652 }
653 State::StringLiteralStart => {
654 let curr = self.current_str();
655
656 Err(Error::with_loc(
657 "unexpected end of data while lexing string value",
658 curr.to_string(),
659 token.index,
660 ))
661 }
662 State::StringLiteral
663 | State::BlockStringLiteral
664 | State::StringLiteralEscapedUnicode { .. }
665 | State::StringLiteralEscapedUnicodeVariable { .. }
666 | State::StringLiteralLeadSurrogate
667 | State::StringLiteralLeadSurrogateBackslash
668 | State::BlockStringLiteralBackslash
669 | State::StringLiteralBackslash => {
670 let curr = self.drain();
671
672 Err(Error::with_loc(
673 "unterminated string value",
674 curr.to_string(),
675 token.index,
676 ))
677 }
678 State::SpreadOperator => self.unterminated_spread_operator(&token),
679 State::MinusSign => Err(Error::with_loc(
680 "Unexpected character \"-\"",
681 self.current_str().to_string(),
682 token.index,
683 )),
684 State::DecimalPoint | State::ExponentIndicator | State::ExponentSign => {
685 Err(Error::with_loc(
686 "Unexpected EOF in float value",
687 self.current_str().to_string(),
688 token.index,
689 ))
690 }
691 State::Ident
692 | State::LeadingZero
693 | State::IntegerPart
694 | State::FractionalPart
695 | State::ExponentDigit
696 | State::Whitespace
697 | State::Comment => {
698 if let Some(mut err) = self.err() {
699 err.set_data(self.current_str().to_string());
700 return Err(err);
701 }
702
703 token.data = self.current_str();
704
705 Ok(token)
706 }
707 }
708 }
709
710 fn unterminated_spread_operator(&mut self, token: &Token<'a>) -> Result<Token<'a>, Error> {
711 let data = if self.is_pending() {
712 self.prev_str()
713 } else {
714 self.current_str()
715 };
716
717 Err(Error::with_loc(
718 "Unterminated spread operator",
719 data.to_string(),
720 token.index,
721 ))
722 }
723
724 fn done(&mut self, token: Token<'a>) -> Result<Token<'a>, Error> {
725 if let Some(mut err) = self.err() {
726 err.set_data(token.data.to_string());
727 err.index = token.index;
728 self.err = None;
729 return Err(err);
730 }
731 Ok(token)
732 }
733}
734
735fn is_whitespace_assimilated(c: char) -> bool {
738 matches!(
739 c,
740 '\u{0009}' | '\u{0020}' | '\u{000A}' | '\u{000D}' | '\u{FEFF}' )
749}
750
751fn is_name_continue(c: char) -> bool {
753 matches!(c, 'a'..='z' | 'A'..='Z' | '0'..='9' | '_')
754}
755
756fn is_line_terminator(c: char) -> bool {
757 matches!(c, '\n' | '\r')
758}
759
760fn is_escaped_char(c: char) -> bool {
763 matches!(c, '"' | '\\' | '/' | 'b' | 'f' | 'n' | 'r' | 't')
764}
765
766#[cfg(test)]
767mod test {
768 use super::*;
769
770 #[test]
771 fn unterminated_string() {
772 let schema = r#"
773type Query {
774 name: String
775 format: String = "Y-m-d\\TH:i:sP"
776}
777 "#;
778 let (tokens, errors) = Lexer::new(schema).lex();
779 dbg!(tokens);
780 dbg!(errors);
781 }
782
783 #[test]
784 fn token_limit() {
785 let lexer = Lexer::new("type Query { a a a a a a a a a }").with_limit(10);
786 let (tokens, errors) = lexer.lex();
787 assert_eq!(tokens.len(), 10);
788 assert_eq!(
789 errors,
790 &[Error::limit("token limit reached, aborting lexing", 17)]
791 );
792 }
793
794 #[test]
795 fn token_limit_exact() {
796 let lexer = Lexer::new("type Query { a a a a a a a a a }").with_limit(26);
797 let (tokens, errors) = lexer.lex();
798 assert_eq!(tokens.len(), 26);
799 assert!(errors.is_empty());
800
801 let lexer = Lexer::new("type Query { a a a a a a a a a }").with_limit(25);
802 let (tokens, errors) = lexer.lex();
803 assert_eq!(tokens.len(), 25);
804 assert_eq!(
805 errors,
806 &[Error::limit("token limit reached, aborting lexing", 31)]
807 );
808 }
809
810 #[test]
811 fn errors_and_token_limit() {
812 let lexer = Lexer::new("type Query { ..a a a a a a a a a }").with_limit(10);
813 let (tokens, errors) = lexer.lex();
814 assert_eq!(tokens.len(), 9);
816 assert_eq!(
817 errors,
818 &[
819 Error::with_loc("Unterminated spread operator", "..".to_string(), 13),
820 Error::limit("token limit reached, aborting lexing", 18),
821 ],
822 );
823 }
824
825 #[test]
826 fn stream_produces_original_input() {
827 let schema = r#"
828type Query {
829 name: String
830 format: String = "Y-m-d\\TH:i:sP"
831}
832 "#;
833
834 let lexer = Lexer::new(schema);
835 let processed_schema = lexer
836 .into_iter()
837 .fold(String::new(), |acc, token| acc + token.unwrap().data());
838
839 assert_eq!(schema, processed_schema);
840 }
841
842 #[test]
843 fn quoted_block_comment() {
844 let input = r#"
845"""
846Not an escape character:
847'/\W/'
848Escape character:
849\"""
850\"""\"""
851Not escape characters:
852\" \""
853Escape character followed by a quote:
854\""""
855"""
856 "#;
857
858 let (tokens, errors) = Lexer::new(input).lex();
859 assert!(errors.is_empty());
860 assert_eq!(
862 tokens[1].data,
863 r#"
864"""
865Not an escape character:
866'/\W/'
867Escape character:
868\"""
869\"""\"""
870Not escape characters:
871\" \""
872Escape character followed by a quote:
873\""""
874"""
875"#
876 .trim(),
877 );
878
879 let input = r#"
880# String contents: """
881"""\""""""
882# Unclosed block string
883"""\"""
884 "#;
885 let (tokens, errors) = Lexer::new(input).lex();
886 assert_eq!(tokens[3].data, r#""""\"""""""#);
887 assert_eq!(
888 errors,
889 &[Error::with_loc(
890 "unterminated string value",
891 r#""""\"""
892 "#
893 .to_string(),
894 59,
895 )]
896 );
897 }
898
899 #[test]
900 fn unexpected_character() {
901 let schema = r#"
902type Query {
903 name: String
904}
905/
906 "#;
907 let (tokens, errors) = Lexer::new(schema).lex();
908 dbg!(tokens);
909 assert_eq!(
910 errors,
911 &[Error::with_loc(
912 "Unexpected character \"/\"",
913 "/".to_string(),
914 33,
915 )]
916 );
917 }
918}