graphql_tools/parser/
tokenizer.rs

1use std::fmt::{self};
2
3use combine::easy::{Error, Errors, Info};
4use combine::error::StreamError;
5use combine::stream::ResetStream;
6use combine::{Positioned, StreamOnce};
7
8use super::position::Pos;
9
10#[derive(Debug, PartialEq, Eq, Clone, Copy)]
11pub enum Kind {
12    Punctuator,
13    Name,
14    IntValue,
15    FloatValue,
16    StringValue,
17    BlockString,
18}
19
20#[derive(Debug, PartialEq, Eq, Clone, Copy)]
21pub struct Token<'a> {
22    pub kind: Kind,
23    pub value: &'a str,
24}
25
26#[derive(Debug, PartialEq)]
27pub struct TokenStream<'a> {
28    buf: &'a str,
29    position: Pos,
30    off: usize,
31    next_state: Option<(usize, Token<'a>, usize, Pos)>,
32    recursion_limit: usize,
33    token_limit: Option<usize>,
34    token_count: usize,
35}
36
37impl TokenStream<'_> {
38    pub(crate) fn offset(&self) -> usize {
39        self.off
40    }
41}
42
43/// Splits `source` into its tokens, each with the byte range it covers in `source`. A string or a
44/// block string is a single token, so nothing inside one is ever read as a name.
45pub fn spanned_tokens(source: &str) -> Result<Vec<(Kind, std::ops::Range<usize>)>, String> {
46    let mut stream = TokenStream::new(source);
47    let mut tokens = Vec::new();
48    loop {
49        match stream.uncons() {
50            Ok(token) => {
51                // the value is a slice of `source`
52                let start = token.value.as_ptr() as usize - source.as_ptr() as usize;
53                tokens.push((token.kind, start..start + token.value.len()));
54            }
55            Err(ref error) if error == &Error::end_of_input() => return Ok(tokens),
56            Err(error) => return Err(error.to_string()),
57        }
58    }
59}
60
61#[derive(Clone, Debug, PartialEq)]
62pub struct Checkpoint {
63    position: Pos,
64    off: usize,
65}
66
67impl<'a> StreamOnce for TokenStream<'a> {
68    type Token = Token<'a>;
69    type Range = Token<'a>;
70    type Position = Pos;
71    type Error = Errors<Token<'a>, Token<'a>, Pos>;
72
73    fn uncons(&mut self) -> Result<Self::Token, Error<Token<'a>, Token<'a>>> {
74        if let Some((at, tok, off, pos)) = self.next_state {
75            if at == self.off {
76                self.off = off;
77                self.position = pos;
78                return Ok(tok);
79            }
80        }
81        let old_pos = self.off;
82        let (kind, len) = self.take_token()?;
83        let value = &self.buf[self.off - len..self.off];
84        self.skip_whitespace();
85        let token = Token { kind, value };
86        self.next_state = Some((old_pos, token, self.off, self.position));
87        Ok(token)
88    }
89}
90
91impl<'a> Positioned for TokenStream<'a> {
92    fn position(&self) -> Self::Position {
93        self.position
94    }
95}
96
97impl<'a> ResetStream for TokenStream<'a> {
98    type Checkpoint = Checkpoint;
99    fn checkpoint(&self) -> Self::Checkpoint {
100        Checkpoint {
101            position: self.position,
102            off: self.off,
103        }
104    }
105    fn reset(&mut self, checkpoint: Checkpoint) -> Result<(), Self::Error> {
106        self.position = checkpoint.position;
107        self.off = checkpoint.off;
108        Ok(())
109    }
110}
111
112// NOTE: we expect that first character is always digit or minus, as returned
113// by tokenizer
114fn check_int(value: &str) -> bool {
115    value == "0"
116        || value == "-0"
117        || (!value.starts_with('0')
118            && value != "-"
119            && !value.starts_with("-0")
120            && value[1..].chars().all(|x| x.is_ascii_digit()))
121}
122
123fn check_dec(value: &str) -> bool {
124    !value.is_empty() && value.chars().all(|x| x.is_ascii_digit())
125}
126
127fn check_exp(value: &str) -> bool {
128    if value.is_empty() {
129        return false;
130    }
131    let first = value.chars().next().unwrap();
132    if first != '-' && first != '+' && (first <= '0' || first >= '9') {
133        return false;
134    }
135
136    value[1..].chars().all(|x| x.is_ascii_digit())
137}
138
139fn check_float(value: &str, exponent: Option<usize>, real: Option<usize>) -> bool {
140    match (exponent, real) {
141        (Some(e), Some(r)) if e < r => false,
142        (Some(e), Some(r)) => {
143            check_int(&value[..r]) && check_dec(&value[r + 1..e]) && check_exp(&value[e + 1..])
144        }
145        (Some(e), None) => check_int(&value[..e]) && check_exp(&value[e + 1..]),
146        (None, Some(r)) => check_int(&value[..r]) && check_dec(&value[r + 1..]),
147        (None, None) => unreachable!(),
148    }
149}
150
151impl<'a> TokenStream<'a> {
152    pub fn new(s: &'a str) -> TokenStream<'a> {
153        Self::with_recursion_limit(s, 50, None)
154    }
155
156    pub fn new_with_token_limit(s: &'a str, token_limit: usize) -> TokenStream<'a> {
157        Self::with_recursion_limit(s, 50, Some(token_limit))
158    }
159
160    /// Specify a limit to recursive parsing. Note that increasing the limit
161    /// from the default may represent a security issue since a maliciously
162    /// crafted input may cause a stack overflow, crashing the process.
163    pub(crate) fn with_recursion_limit(
164        s: &'a str,
165        recursion_limit: usize,
166        token_limit: Option<usize>,
167    ) -> TokenStream<'a> {
168        let mut me = TokenStream {
169            buf: s,
170            position: Pos { line: 1, column: 1 },
171            off: 0,
172            next_state: None,
173            recursion_limit,
174            token_limit,
175            token_count: 0,
176        };
177        me.skip_whitespace();
178        me
179    }
180
181    /// Convenience for the common case where a token does
182    /// not span multiple lines. Infallible.
183    #[inline]
184    fn advance_token<T>(&mut self, kind: Kind, size: usize) -> Result<(Kind, usize), T> {
185        self.position.column += size;
186        self.off += size;
187        // Should be counted?
188        if self.token_limit.is_some() {
189            self.token_count += 1;
190        }
191        Ok((kind, size))
192    }
193
194    fn take_token(&mut self) -> Result<(Kind, usize), Error<Token<'a>, Token<'a>>> {
195        if let Some(limit) = self.token_limit {
196            if self.token_count >= limit {
197                return Err(Error::message_static_message("Token limit exceeded"));
198            }
199        }
200        use self::Kind::*;
201        let mut iter = self.buf[self.off..].char_indices();
202        let cur_char = match iter.next() {
203            Some((_, x)) => x,
204            None => return Err(Error::end_of_input()),
205        };
206
207        match cur_char {
208            '(' | '[' | '{' => {
209                // Check for recursion limit
210                self.recursion_limit = self
211                    .recursion_limit
212                    .checked_sub(1)
213                    .ok_or_else(|| Error::message_static_message("Recursion limit exceeded"))?;
214
215                self.advance_token(Punctuator, 1)
216            }
217            ')' | ']' | '}' => {
218                // Notes on exceptional cases:
219                // recursion_limit may exceed the original value specified
220                // when constructing the Tokenizer. It may at first
221                // seem like this would be a good place to handle that,
222                // but instead this code allows this token to propagate up
223                // to the parser which is better equipped to make specific
224                // error messages about unmatched pairs.
225                // The case where recursion limit would overflow but instead
226                // saturates is just a specific case of the more general
227                // occurrence above.
228                self.recursion_limit = self.recursion_limit.saturating_add(1);
229                self.advance_token(Punctuator, 1)
230            }
231            '!' | '$' | ':' | '=' | '@' | '|' | '&' => self.advance_token(Punctuator, 1),
232            '.' => {
233                if iter.as_str().starts_with("..") {
234                    self.advance_token(Punctuator, 3)
235                } else {
236                    Err(Error::Unexpected(Info::Owned(
237                        format_args!(
238                            "bare dot {:?} is not supported, \
239                            only \"...\"",
240                            cur_char
241                        )
242                        .to_string(),
243                    )))
244                }
245            }
246            '_' | 'a'..='z' | 'A'..='Z' => {
247                for (idx, cur_char) in iter.by_ref() {
248                    match cur_char {
249                        '_' | 'a'..='z' | 'A'..='Z' | '0'..='9' => continue,
250                        _ => return self.advance_token(Name, idx),
251                    }
252                }
253                let len = self.buf.len() - self.off;
254                self.position.column += len;
255                self.off += len;
256
257                Ok((Name, len))
258            }
259            '-' | '0'..='9' => {
260                let mut exponent = None;
261                let mut real = None;
262                let len = loop {
263                    let (idx, cur_char) = match iter.next() {
264                        Some(pair) => pair,
265                        None => break self.buf.len() - self.off,
266                    };
267                    match cur_char {
268                        // just scan for now, will validate later on
269                        ' ' | '\n' | '\r' | '\t' | ',' | '#' | '!' | '$' | ':' | '=' | '@'
270                        | '|' | '&' | '(' | ')' | '[' | ']' | '{' | '}' => break idx,
271                        '.' => real = Some(idx),
272                        'e' | 'E' => exponent = Some(idx),
273                        _ => {}
274                    }
275                };
276
277                if exponent.is_some() || real.is_some() {
278                    let value = &self.buf[self.off..][..len];
279                    if !check_float(value, exponent, real) {
280                        return Err(Error::Unexpected(Info::Owned(
281                            format_args!("unsupported float {:?}", value).to_string(),
282                        )));
283                    }
284                    self.position.column += len;
285                    self.off += len;
286
287                    Ok((FloatValue, len))
288                } else {
289                    let value = &self.buf[self.off..][..len];
290                    if !check_int(value) {
291                        return Err(Error::Unexpected(Info::Owned(
292                            format_args!("unsupported integer {:?}", value).to_string(),
293                        )));
294                    }
295                    self.advance_token(IntValue, len)
296                }
297            }
298            '"' => {
299                if iter.as_str().starts_with("\"\"") {
300                    let tail = &iter.as_str()[2..];
301                    for (end_idx, _) in tail.match_indices("\"\"\"") {
302                        if !tail[..end_idx].ends_with('\\') {
303                            self.update_position(end_idx + 6);
304                            return Ok((BlockString, end_idx + 6));
305                        }
306                    }
307
308                    Err(Error::Unexpected(Info::Owned(
309                        "unterminated block string value".to_string(),
310                    )))
311                } else {
312                    let mut nchars = 1;
313                    let mut escaped = false;
314                    for (idx, cur_char) in iter {
315                        nchars += 1;
316                        match cur_char {
317                            '"' if escaped => {}
318                            '"' => {
319                                self.position.column += nchars;
320                                self.off += idx + 1;
321                                return Ok((StringValue, idx + 1));
322                            }
323                            '\n' => {
324                                return Err(Error::Unexpected(Info::Owned(
325                                    "unterminated string value".to_string(),
326                                )));
327                            }
328
329                            _ => {}
330                        }
331
332                        // if we aren't escaped and the current char is a \, we are now escaped
333                        escaped = !escaped && cur_char == '\\';
334                    }
335                    Err(Error::Unexpected(Info::Owned(
336                        "unterminated string value".to_string(),
337                    )))
338                }
339            }
340            _ => Err(Error::Unexpected(Info::Owned(
341                format_args!("unexpected character {:?}", cur_char).to_string(),
342            ))),
343        }
344    }
345
346    fn skip_whitespace(&mut self) {
347        let mut iter = self.buf[self.off..].char_indices();
348        let idx = loop {
349            let (idx, cur_char) = match iter.next() {
350                Some(pair) => pair,
351                None => break self.buf.len() - self.off,
352            };
353            match cur_char {
354                '\u{feff}' | '\r' => continue,
355                '\t' => self.position.column += 8,
356                '\n' => {
357                    self.position.column = 1;
358                    self.position.line += 1;
359                }
360                // comma is also entirely ignored in spec
361                ' ' | ',' => {
362                    self.position.column += 1;
363                    continue;
364                }
365                //comment
366                '#' => {
367                    for (_, cur_char) in iter.by_ref() {
368                        // TODO(tailhook) ensure SourceCharacter
369                        if cur_char == '\r' || cur_char == '\n' {
370                            self.position.column = 1;
371                            self.position.line += 1;
372                            break;
373                        }
374                    }
375                    continue;
376                }
377                _ => break idx,
378            }
379        };
380        self.off += idx;
381    }
382
383    fn update_position(&mut self, len: usize) {
384        let val = &self.buf[self.off..][..len];
385        self.off += len;
386        let lines = val.as_bytes().iter().filter(|&&x| x == b'\n').count();
387        self.position.line += lines;
388        if lines > 0 {
389            let line_offset = val.rfind('\n').unwrap() + 1;
390            let num = val[line_offset..].chars().count();
391            self.position.column = num + 1;
392        } else {
393            let num = val.chars().count();
394            self.position.column += num;
395        }
396    }
397}
398
399impl<'a> fmt::Display for Token<'a> {
400    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
401        write!(f, "{}[{:?}]", self.value, self.kind)
402    }
403}
404
405#[cfg(test)]
406mod test {
407    #[test]
408    fn spanned_tokens_cover_whole_tokens() {
409        let source = "query($a:ID){f(s:\"\"\"\n  x$a\n\"\"\" t:\"$a\")}";
410        let tokens = super::spanned_tokens(source).unwrap();
411        let names: Vec<&str> = tokens
412            .iter()
413            .filter(|(kind, _)| *kind == super::Kind::Name)
414            .map(|(_, span)| &source[span.clone()])
415            .collect();
416        // the `$a` inside both strings stays part of the string
417        assert_eq!(names, ["query", "a", "ID", "f", "s", "t"]);
418        let strings: Vec<&str> = tokens
419            .iter()
420            .filter(|(kind, _)| matches!(kind, super::Kind::StringValue | super::Kind::BlockString))
421            .map(|(_, span)| &source[span.clone()])
422            .collect();
423        assert_eq!(strings, ["\"\"\"\n  x$a\n\"\"\"", "\"$a\""]);
424    }
425
426    use super::Kind::*;
427    use super::{Kind, TokenStream};
428    use combine::easy::Error;
429
430    use combine::{Positioned, StreamOnce};
431
432    fn tok_str(s: &str) -> Vec<&str> {
433        let mut r = Vec::new();
434        let mut s = TokenStream::new(s);
435        loop {
436            match s.uncons() {
437                Ok(x) => r.push(x.value),
438                Err(ref e) if e == &Error::end_of_input() => break,
439                Err(e) => panic!("Parse error at {}: {}", s.position(), e),
440            }
441        }
442        r
443    }
444    fn tok_typ(s: &str) -> Vec<Kind> {
445        let mut r = Vec::new();
446        let mut s = TokenStream::new(s);
447        loop {
448            match s.uncons() {
449                Ok(x) => r.push(x.kind),
450                Err(ref e) if e == &Error::end_of_input() => break,
451                Err(e) => panic!("Parse error at {}: {}", s.position(), e),
452            }
453        }
454        r
455    }
456
457    #[test]
458    fn comments_and_commas() {
459        assert_eq!(tok_str("# hello { world }"), &[] as &[&str]);
460        assert_eq!(tok_str("# x\n,,,"), &[] as &[&str]);
461        assert_eq!(tok_str(", ,,  ,,,  # x"), &[] as &[&str]);
462    }
463
464    #[test]
465    fn simple() {
466        assert_eq!(tok_str("a { b }"), ["a", "{", "b", "}"]);
467        assert_eq!(tok_typ("a { b }"), [Name, Punctuator, Name, Punctuator]);
468    }
469
470    #[test]
471    fn query() {
472        assert_eq!(
473            tok_str(
474                "query Query {
475            object { field }
476        }"
477            ),
478            ["query", "Query", "{", "object", "{", "field", "}", "}"]
479        );
480    }
481
482    #[test]
483    fn fragment() {
484        assert_eq!(tok_str("a { ...b }"), ["a", "{", "...", "b", "}"]);
485    }
486
487    #[test]
488    fn int() {
489        assert_eq!(tok_str("0"), ["0"]);
490        assert_eq!(tok_str("0,"), ["0"]);
491        assert_eq!(tok_str("0# x"), ["0"]);
492        assert_eq!(tok_typ("0"), [IntValue]);
493        assert_eq!(tok_str("-0"), ["-0"]);
494        assert_eq!(tok_typ("-0"), [IntValue]);
495        assert_eq!(tok_str("-1"), ["-1"]);
496        assert_eq!(tok_typ("-1"), [IntValue]);
497        assert_eq!(tok_str("-132"), ["-132"]);
498        assert_eq!(tok_typ("-132"), [IntValue]);
499        assert_eq!(tok_str("132"), ["132"]);
500        assert_eq!(tok_typ("132"), [IntValue]);
501        assert_eq!(
502            tok_str("a(x: 10) { b }"),
503            ["a", "(", "x", ":", "10", ")", "{", "b", "}"]
504        );
505        assert_eq!(
506            tok_typ("a(x: 10) { b }"),
507            [
508                Name, Punctuator, Name, Punctuator, IntValue, Punctuator, Punctuator, Name,
509                Punctuator
510            ]
511        );
512    }
513
514    // TODO(tailhook) fix errors in parser and check error message
515    #[test]
516    #[should_panic]
517    fn zero_int() {
518        tok_str("01");
519    }
520    #[test]
521    #[should_panic]
522    fn zero_int4() {
523        tok_str("00001");
524    }
525    #[test]
526    #[should_panic]
527    fn minus_int() {
528        tok_str("-");
529    }
530    #[test]
531    #[should_panic]
532    fn minus_zero_int() {
533        tok_str("-01");
534    }
535    #[test]
536    #[should_panic]
537    fn minus_zero_int4() {
538        tok_str("-00001");
539    }
540    #[test]
541    #[should_panic]
542    fn letters_int() {
543        tok_str("0bbc");
544    }
545
546    #[test]
547    fn float() {
548        assert_eq!(tok_str("0.0"), ["0.0"]);
549        assert_eq!(tok_typ("0.0"), [FloatValue]);
550        assert_eq!(tok_str("-0.0"), ["-0.0"]);
551        assert_eq!(tok_typ("-0.0"), [FloatValue]);
552        assert_eq!(tok_str("-1.0"), ["-1.0"]);
553        assert_eq!(tok_typ("-1.0"), [FloatValue]);
554        assert_eq!(tok_str("-1.023"), ["-1.023"]);
555        assert_eq!(tok_typ("-1.023"), [FloatValue]);
556        assert_eq!(tok_str("-132.0"), ["-132.0"]);
557        assert_eq!(tok_typ("-132.0"), [FloatValue]);
558        assert_eq!(tok_str("132.0"), ["132.0"]);
559        assert_eq!(tok_typ("132.0"), [FloatValue]);
560        assert_eq!(tok_str("0e+0"), ["0e+0"]);
561        assert_eq!(tok_typ("0e+0"), [FloatValue]);
562        assert_eq!(tok_str("0.0e+0"), ["0.0e+0"]);
563        assert_eq!(tok_typ("0.0e+0"), [FloatValue]);
564        assert_eq!(tok_str("-0e+0"), ["-0e+0"]);
565        assert_eq!(tok_typ("-0e+0"), [FloatValue]);
566        assert_eq!(tok_str("-1e+0"), ["-1e+0"]);
567        assert_eq!(tok_typ("-1e+0"), [FloatValue]);
568        assert_eq!(tok_str("-132e+0"), ["-132e+0"]);
569        assert_eq!(tok_typ("-132e+0"), [FloatValue]);
570        assert_eq!(tok_str("132e+0"), ["132e+0"]);
571        assert_eq!(tok_typ("132e+0"), [FloatValue]);
572        assert_eq!(
573            tok_str("a(x: 10.0) { b }"),
574            ["a", "(", "x", ":", "10.0", ")", "{", "b", "}"]
575        );
576        assert_eq!(
577            tok_typ("a(x: 10.0) { b }"),
578            [
579                Name, Punctuator, Name, Punctuator, FloatValue, Punctuator, Punctuator, Name,
580                Punctuator
581            ]
582        );
583        assert_eq!(tok_str("1.23e4"), ["1.23e4"]);
584        assert_eq!(tok_typ("1.23e4"), [FloatValue]);
585    }
586
587    // TODO(tailhook) fix errors in parser and check error message
588    #[test]
589    #[should_panic]
590    fn no_int_float() {
591        tok_str(".0");
592    }
593    #[test]
594    #[should_panic]
595    fn no_int_float1() {
596        tok_str(".1");
597    }
598    #[test]
599    #[should_panic]
600    fn zero_float() {
601        tok_str("01.0");
602    }
603    #[test]
604    #[should_panic]
605    fn zero_float4() {
606        tok_str("00001.0");
607    }
608    #[test]
609    #[should_panic]
610    fn minus_float() {
611        tok_str("-.0");
612    }
613    #[test]
614    #[should_panic]
615    fn minus_zero_float() {
616        tok_str("-01.0");
617    }
618    #[test]
619    #[should_panic]
620    fn minus_zero_float4() {
621        tok_str("-00001.0");
622    }
623    #[test]
624    #[should_panic]
625    fn letters_float() {
626        tok_str("0bbc.0");
627    }
628    #[test]
629    #[should_panic]
630    fn letters_float2() {
631        tok_str("0.bbc");
632    }
633    #[test]
634    #[should_panic]
635    fn letters_float3() {
636        tok_str("0.bbce0");
637    }
638    #[test]
639    #[should_panic]
640    fn no_exp_sign_float() {
641        tok_str("0e0");
642    }
643    #[test]
644    #[should_panic]
645    fn unterminated_string() {
646        tok_str(r#""hello\""#);
647    }
648    #[test]
649    #[should_panic]
650    fn extra_unterminated_string() {
651        tok_str(r#""hello\\\""#);
652    }
653
654    #[test]
655    fn string() {
656        assert_eq!(tok_str(r#""""#), [r#""""#]);
657        assert_eq!(tok_typ(r#""""#), [StringValue]);
658        assert_eq!(tok_str(r#""hello""#), [r#""hello""#]);
659        assert_eq!(tok_str(r#""hello\\""#), [r#""hello\\""#]);
660        assert_eq!(tok_str(r#""hello\\\\""#), [r#""hello\\\\""#]);
661        assert_eq!(tok_str(r#""he\\llo""#), [r#""he\\llo""#]);
662        assert_eq!(tok_typ(r#""hello""#), [StringValue]);
663        assert_eq!(tok_str(r#""my\"quote""#), [r#""my\"quote""#]);
664        assert_eq!(tok_typ(r#""my\"quote""#), [StringValue]);
665    }
666
667    #[test]
668    fn block_string() {
669        assert_eq!(tok_str(r#""""""""#), [r#""""""""#]);
670        assert_eq!(tok_typ(r#""""""""#), [BlockString]);
671        assert_eq!(tok_str(r#""""hello""""#), [r#""""hello""""#]);
672        assert_eq!(tok_typ(r#""""hello""""#), [BlockString]);
673        assert_eq!(tok_str(r#""""my "quote" """"#), [r#""""my "quote" """"#]);
674        assert_eq!(tok_typ(r#""""my "quote" """"#), [BlockString]);
675        assert_eq!(tok_str(r#""""\"""quote" """"#), [r#""""\"""quote" """"#]);
676        assert_eq!(tok_typ(r#""""\"""quote" """"#), [BlockString]);
677    }
678}
graphql_tools/parser/tokenizer.rs

graphql_tools/parser/
tokenizer.rs
