Repository: apollographql/apollo-rs
Pull request #115 (2021-11-18 16:44:21)

feat(parser): Stream tokens from the lexer
this is an exploration of streaming the lexer. The current parser first allocates the list of tokens, then reverses it, then transforms to a syntax tree.

With the benchmark I added, on current main ( 6e8e8a8 ) we're at:
```
test bench_peek_n ... bench:      11,620 ns/iter (+/- 344)
test bench_supergraph ... bench:     418,199 ns/iter (+/- 6,446)
```

Here's the flamegraph when parsing the supergraph:

![Screenshot from 2021-11-18 17-23-02](https://user-images.githubusercontent.com/119296/142454982-fdf7fbf8-dcef-4ff5-9968-5d5cebaad691.png)

We can see that a large part of the time is spent in allocations in the lexing phase.

In 57647fe963b4c830d70a125cd4a52af47854bce9 we see that we can avoid reversing by replacing the token Vec with a VecDeque (I think the errors will be generated in the wrong order here though).

Then we can remove that vec entirely in 81f94f4731ed2f8afbb67040137ccc2b8ae63a33 by transforming the Lexer into an iterator of Token or Error. The interesting thing here is that it's actually slower:

```
test bench_peek_n ... bench:      23,392 ns/iter (+/- 636)
test bench_supergraph ... bench:     725,191 ns/iter (+/- 27,976)
```

We can see in the global graph that we removed all allocations in the lexer:
![Screenshot from 2021-11-18 17-25-55](https://user-images.githubusercontent.com/119296/142455660-474b25a0-6b95-4527-bd74-72013381f5f8.png)

But if we zoom in, we see that the peek function is called very often:

![Screenshot from 2021-11-18 17-26-40](https://user-images.githubusercontent.com/119296/142455744-a3858f7a-a4b2-4731-8b38-7928948febf7.png)

The parser is calling that function regularly to make a decision when parsing the rest of the input. When tokens were preallocated, looking at the next one was nearly free but now we're reparsing it often.

So in e743184085414ca1a080ed06573f1c45ee3d31a8 we will store in `Parser` the next token when it is requested, to avoid reparsing it. The cost for that is fixed, it's only enough memory for one token, and we get better performance:

```
test bench_peek_n ... bench:       9,144 ns/iter (+/- 152)
test bench_supergraph ... bench:     297,023 ns/iter (+/- 11,814)
```

The graphs get smaller and we don't call peek as often.

![Screenshot from 2021-11-18 17-38-43](https://user-images.githubusercontent.com/119296/142457861-ab355df9-8585-4002-9006-82045e107d9d.png)

![Screenshot from 2021-11-18 17-39-24](https://user-images.githubusercontent.com/119296/142458031-ddd1cff9-41e6-44dc-8ebe-d39b0f4f6871.png)

To sump up: less allocations, between 20 and 30% improvement, no change in the syntax tree creation code, I feel good about that :)

lrlna: thanks for this @Geal ! I will take a look and review early next week.
Geal: > I also think the Lexer is becoming a bit bulky. There is now a LexerIterator, LexerResult and a Cursor. I'd like to see if we can simplify this a bit and make it more readable. Using Read and Write directly is likely going to help with this.

I think I can replace the `LexerResult` with a std `Result`. Also, `LexerIterator` can be renamed `Lexer`, and I'll add a `Collect()` method that produces vecs of tokens and errors
Geal: rebased over main
Geal: > I would also like to see if the parser "navigation" functions, i.e. peek_token, peek_n, pop can be simplified a bit. I think the iteration can be done outside of the individual functions, e.g. parser.parse().
I'm looking at it, there are ways to simplify them. I'm not sure iterating should be done outside though, since we'd lose the benefit of streaming: iteration is driven by the needs of the tree builder

Patch:
diff --git a/.circleci/config.yml b/.circleci/config.yml
index 3617d21..9133b2a 100644
--- a/.circleci/config.yml
+++ b/.circleci/config.yml
@@ -70,6 +70,9 @@ jobs:
       - run:
           name: Run cargo clippy
           command: cargo clippy --all-targets --all-features -- -D warnings && cargo clippy --benches
+      - run:
+          name: Run cargo fmt check
+          command: rustup component add rustfmt && cargo fmt --all -- --check
 
   test:
     parameters:
diff --git a/crates/apollo-compiler/CHANGELOG.md b/crates/apollo-compiler/CHANGELOG.md
index 3d6b030..d9c9ab6 100644
--- a/crates/apollo-compiler/CHANGELOG.md
+++ b/crates/apollo-compiler/CHANGELOG.md
@@ -17,6 +17,211 @@ This project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.htm
 ## Maintenance
 
 ## Documentation -->
+# [0.3.0](https://crates.io/crates/apollo-compiler/0.3.0) - 2022-11-02
+## Breaking
+- **compiler.parse is renamed to compiler.ast - [lrlna], [pull/290]**
+
+  `compiler.ast()` returns the `SyntaxTree` produced by the parser and is much
+  clearer method than `compiler.parse()`.
+
+  [lrlna]: https://github.com/lrlna
+  [pull/290]: https://github.com/apollographql/apollo-rs/pull/290
+
+- **selection.ty(db) now expects a `db` parameter - [lrlna], [pull/290]**
+
+  As byproduct of separating compiler's query_groups into individual components.
+  Selection's type can now be accessed like so:
+
+    ```rust
+    let ctx = ApolloCompiler::new(input);
+    let top_product_fields: Vec<String> = top_products
+      .iter()
+      .filter_map(|field| Some(field.ty(&ctx.db)?.name()))
+      .collect();
+    ```
+
+  [lrlna]: https://github.com/lrlna
+  [pull/290]: https://github.com/apollographql/apollo-rs/pull/290
+
+- **removes db.definitions() API - [lrlna], [pull/295]**
+
+  `db.definitions()` returned a `!Send` value that is no longer possible with
+  the `ParallelDatabase` implementation.
+
+  To access HIR definitions, use `db.db_definitions()` and `db.type_system_definitions`.
+
+  [lrlna]: https://github.com/lrlna
+  [pull/295]: https://github.com/apollographql/apollo-rs/pull/295
+
+## Features
+- **add subtype_map and is_subtype queries - [lrlna]/[SimonSapin], [pull/333]**
+
+  This allows users to check whether a particular type is a subtype of another
+  type. For example, in a UnionDefinition such as `union SearchResult = Photo |
+  Person`, `Person` is a suptype of `SearchResult`. In an InterfaceDefinition such
+  as `type Business implements NamedEntity & ValuedEntity { # fields }`,
+  `Business` is a subtype of `NamedEntity`.
+
+  [lrlna]: https://github.com/lrlna
+  [SimonSapin]: https://github.com/SimonSapin
+  [pull/333]: https://github.com/apollographql/apollo-rs/pull/333
+
+- **pub compiler storage - allow database composition - [lrlna], [pull/328]**
+
+  This allows for internal query_groups to be exported, and allows users to
+  compose various databases from compiler's existing dbs and their queries.
+
+  This is how you'd create a database with storage from apollo-compiler:
+    ```rust
+    use apollo_compiler::{database::{AstStorage, DocumentStorage}};
+
+    #[salsa::database(AstStorage, DoumentStorage)]
+    pub struct AnotherDatabase {
+        pub storage: salsa::Storage<AnotherDatabase>,
+    }
+    ```
+
+  You can also see a more detailed linting example in [examples] dir.
+
+  [lrlna]: https://github.com/lrlna
+  [pull/328]: https://github.com/apollographql/apollo-rs/pull/328
+  [examples]: ./examples/extend_db.rs
+
+- **validate argument name uniqueness - [goto-bus-stop], [pull/317]**
+
+  It's an error to declare or provide multiple arguments by the same name, eg:
+
+    ```graphql
+    type Query {
+      things(offset: Int!, offset: Int!): [Thing]
+      # ERR: duplicate argument definition: offset
+    }
+    ```
+
+    ```graphql
+    query GetThings {
+      things(offset: 10, offset: 20) { id }
+      # ERR: duplicate argument values: offset
+    }
+    ```
+
+  This adds `UniqueArgument` diagnostics and checks for argument duplications in:
+  field definitions, fields, directives, interfaces and directive definitions.
+
+  [goto-bus-stop]: https://github.com/goto-bus-stop
+  [pull/317]: https://github.com/apollographql/apollo-rs/pull/317
+
+- **getter for directives in HIR FragmentSpread - [allancalix], [pull/315]**
+
+  Allow accessing directives in a given FragmentSpread node in a high-level
+  intermediate representation of the compiler.
+
+  [allancalix]: https://github.com/allancalix
+  [pull/315]: https://github.com/apollographql/apollo-rs/pull/315
+
+- **create validation database - [lrlna], [pull/303]**
+
+  All validation now happens in its own database, which can be accessed with
+  `ValidationDatabase` and `ValidationStorage`.
+
+  [lrlna]: https://github.com/lrlna
+  [pull/303]: https://github.com/apollographql/apollo-rs/pull/303
+
+- **thread-safe compiler: introduce snapshots - [lrlna], [pull/295] + [pull/332]**
+
+  Implements `ParallelDatabase` for `RootDatabase` of the compiler. This allows
+  us to create snapshots that can allow users to query the database from
+  multiple threads. For example:
+
+    ```rust
+    let input = r#"
+    type Query {
+      website: URL,
+      amount: Int
+    }
+
+    scalar URL @specifiedBy(url: "https://tools.ietf.org/html/rfc3986")
+    "#;
+
+    let ctx = ApolloCompiler::new(input);
+    let diagnostics = ctx.validate();
+    for diagnostic in &diagnostics {
+        println!("{}", diagnostic);
+    }
+
+    assert!(diagnostics.is_empty());
+
+    let snapshot = ctx.snapshot();
+    let snapshot2 = ctx.snapshot();
+
+    let thread1 = std::thread::spawn(move || snapshot.find_object_type_by_name("Query".into()));
+    let thread2 = std::thread::spawn(move || snapshot2.scalars());
+
+    thread1.join().expect("object_type_by_name panicked");
+    thread2.join().expect("scalars failed");
+    ```
+
+  [lrlna]: https://github.com/lrlna
+  [pull/295]: https://github.com/apollographql/apollo-rs/pull/295
+  [pull/332]: https://github.com/apollographql/apollo-rs/pull/332
+
+- **add description getters to compiler's HIR nodes - [aschaeffer], [pull/289]**
+
+  Expose getters for descriptions that can be accessed for any definitions that
+  support them. For example:
+    ```rust
+    let input = r#"
+    "Books in a given libary"
+    type Book {
+      id: ID!
+    }
+    "#;
+
+    let ctx = ApolloCompiler::new(input);
+
+    let desc = ctx.db.find_object_type_by_name("Book".to_string()).unwrap().description();
+    ```
+  [aschaeffer]: https://github.com/aschaeffer
+  [pull/289]: https://github.com/apollographql/apollo-rs/pull/289
+
+## Fixes
+- **update parser version - [goto-bus-stop], [pull/331]**
+
+  [goto-bus-stop]: https://github.com/goto-bus-stop
+  [pull/331]: https://github.com/apollographql/apollo-rs/pull/331
+
+- **unused variables return an error diagnostic - [lrlna], [pull/314]**
+
+  We were previously returning a warning for any unused variables, it is now
+  reported as an error.
+
+  [lrlna]: https://github.com/lrlna
+  [pull/314]: https://github.com/apollographql/apollo-rs/pull/314
+## Maintenance
+- **split up db into several components - [lrlna], [pull/290]**
+
+  We are splitting up the single `query_group` we had in our db into several
+  `query_group`s that currently just build upon each other, and eventually could
+  support more complex relationships between one another. The current structure:
+
+  `Inputs` --> `DocumentParser` --> `Definitions` --> `Document`
+
+  All of these `query_group`s make up the `RootDatabase`, i.e. `salsa::database`.
+
+  This also allows external users to build out their own databases with
+  compiler's query groups.
+
+  [lrlna]: https://github.com/lrlna
+  [pull/290]: https://github.com/apollographql/apollo-rs/pull/290
+
+- **support wasm compiler target - [allancalix], [pull/287], [issue/288]**
+
+  `apollo-compiler` can now compile to a Wasm target with `cargo check --target wasm32-unknown-unknown`.
+
+  [allancalix]: https://github.com/allancalix
+  [pull/287]: https://github.com/apollographql/apollo-rs/pull/287
+  [issue/288]: https://github.com/apollographql/apollo-rs/issues/288
+
 # [0.2.0](https://crates.io/crates/apollo-compiler/0.2.0) - 2022-08-16
 
 ## Breaking
diff --git a/crates/apollo-compiler/Cargo.toml b/crates/apollo-compiler/Cargo.toml
index 1b6b5ba..205a733 100644
--- a/crates/apollo-compiler/Cargo.toml
+++ b/crates/apollo-compiler/Cargo.toml
@@ -1,6 +1,6 @@
 [package]
 name = "apollo-compiler"
-version = "0.2.0"
+version = "0.3.0"
 authors = ["Irina Shestak <shestak.irina@gmail.com>"]
 license = "MIT OR Apache-2.0"
 repository = "https://github.com/apollographql/apollo-rs"
diff --git a/crates/apollo-compiler/README.md b/crates/apollo-compiler/README.md
index 24235d1..74b8131 100644
--- a/crates/apollo-compiler/README.md
+++ b/crates/apollo-compiler/README.md
@@ -27,7 +27,7 @@ Add this to your `Cargo.toml` to start using `apollo-compiler`:
 ```toml
 # Just an example, change to the necessary package version.
 [dependencies]
-apollo-compiler= "0.2.0"
+apollo-compiler = "0.3.0"
 ```
 
 Or using [cargo-edit]:
diff --git a/crates/apollo-parser/Cargo.toml b/crates/apollo-parser/Cargo.toml
index cca4375..3f77e92 100644
--- a/crates/apollo-parser/Cargo.toml
+++ b/crates/apollo-parser/Cargo.toml
@@ -29,6 +29,11 @@ unindent = "0.1.7"
 criterion = "0.3.0"
 
 [[bench]]
-name = "benches"
-path = "benches/benches.rs"
+name = "query"
+path = "benches/query.rs"
+harness = false
+
+[[bench]]
+name = "supergraph"
+path = "benches/supergraph.rs"
 harness = false
diff --git a/crates/apollo-parser/benches/benches.rs b/crates/apollo-parser/benches/query.rs
similarity index 59%
rename from crates/apollo-parser/benches/benches.rs
rename to crates/apollo-parser/benches/query.rs
index dae28b5..915d64b 100644
--- a/crates/apollo-parser/benches/benches.rs
+++ b/crates/apollo-parser/benches/query.rs
@@ -1,4 +1,4 @@
-use apollo_parser::ast;
+use apollo_parser::{ast, Lexer};
 use criterion::*;
 
 fn parse_query(query: &str) {
@@ -24,11 +24,25 @@ fn parse_query(query: &str) {
     }
 }
 
-fn bench_parser_peek_n(c: &mut Criterion) {
+fn bench_query_parser(c: &mut Criterion) {
     let query = "query ExampleQuery($topProductsFirst: Int) {\n  me { \n    id\n  }\n  topProducts(first:  $topProductsFirst) {\n    name\n    price\n    inStock\n weight\n test test test test test test test test test test test test }\n}";
 
-    c.bench_function("parser_peek_n", move |b| b.iter(|| parse_query(query)));
+    c.bench_function("query_parser", move |b| b.iter(|| parse_query(query)));
 }
 
-criterion_group!(benches, bench_parser_peek_n);
+fn bench_query_lexer(c: &mut Criterion) {
+    let query = "query ExampleQuery($topProductsFirst: Int) {\n  me { \n    id\n  }\n  topProducts(first:  $topProductsFirst) {\n    name\n    price\n    inStock\n weight\n test test test test test test test test test test test test }\n}";
+
+    c.bench_function("query_lexer", move |b| {
+        b.iter(|| {
+            let lexer = Lexer::new(query);
+
+            for token_res in lexer {
+                let _ = token_res;
+            }
+        })
+    });
+}
+
+criterion_group!(benches, bench_query_lexer, bench_query_parser);
 criterion_main!(benches);
diff --git a/crates/apollo-parser/benches/supergraph.rs b/crates/apollo-parser/benches/supergraph.rs
new file mode 100644
index 0000000..c0904ca
--- /dev/null
+++ b/crates/apollo-parser/benches/supergraph.rs
@@ -0,0 +1,52 @@
+use apollo_parser::{ast, Lexer};
+use criterion::*;
+
+fn parse_schema(schema: &str) {
+    let parser = apollo_parser::Parser::new(schema);
+    let tree = parser.parse();
+    let errors = tree.errors().collect::<Vec<_>>();
+
+    if !errors.is_empty() {
+        panic!("error parsing query: {:?}", errors);
+    }
+
+    let document = tree.document();
+
+    for definition in document.definitions() {
+        if let ast::Definition::OperationDefinition(operation) = definition {
+            let selection_set = operation
+                .selection_set()
+                .expect("the node SelectionSet is not optional in the spec; qed");
+            for selection in selection_set.selections() {
+                if let ast::Selection::Field(field) = selection {
+                    let _selection_set = field.selection_set();
+                }
+            }
+        }
+    }
+}
+
+fn bench_supergraph_parser(c: &mut Criterion) {
+    let schema = include_str!("../test_data/parser/ok/0032_supergraph.graphql");
+
+    c.bench_function("supergraph_parser", move |b| {
+        b.iter(|| parse_schema(schema))
+    });
+}
+
+fn bench_supergraph_lexer(c: &mut Criterion) {
+    let schema = include_str!("../test_data/parser/ok/0032_supergraph.graphql");
+
+    c.bench_function("supergraph_lexer", move |b| {
+        b.iter(|| {
+            let lexer = Lexer::new(schema);
+
+            for token_res in lexer {
+                let _ = token_res;
+            }
+        })
+    });
+}
+
+criterion_group!(benches, bench_supergraph_lexer, bench_supergraph_parser);
+criterion_main!(benches);
diff --git a/crates/apollo-parser/src/lexer/mod.rs b/crates/apollo-parser/src/lexer/mod.rs
index 45d7ea5..cf4d296 100644
--- a/crates/apollo-parser/src/lexer/mod.rs
+++ b/crates/apollo-parser/src/lexer/mod.rs
@@ -2,13 +2,12 @@ mod cursor;
 mod token;
 mod token_kind;
 
-use std::slice::Iter;
-
 use crate::{lexer::cursor::Cursor, Error};
 
 pub use token::Token;
 pub use token_kind::TokenKind;
-/// Parses tokens into text.
+
+/// Parses GraphQL source text into tokens.
 /// ```rust
 /// use apollo_parser::Lexer;
 ///
@@ -23,70 +22,92 @@ pub use token_kind::TokenKind;
 ///     }
 /// }
 /// ";
-/// let lexer = Lexer::new(query);
-/// assert_eq!(lexer.errors().len(), 0);
-///
-/// let tokens = lexer.tokens();
+/// let (tokens, errors) = Lexer::new(query).lex();
+/// assert_eq!(errors.len(), 0);
 /// ```
-pub struct Lexer {
-    tokens: Vec<Token>,
-    errors: Vec<Error>,
+#[derive(Clone, Debug)]
+pub struct Lexer<'a> {
+    input: &'a str,
+    index: usize,
+    finished: bool,
 }
 
-impl Lexer {
-    /// Create a new instance of `Lexer`.
-    pub fn new(mut input: &str) -> Self {
-        let mut tokens = Vec::new();
-        let mut errors = Vec::new();
-
-        let mut index = 0;
+impl<'a> Lexer<'a> {
+    /// Create a lexer for a GraphQL source text.
+    ///
+    /// The Lexer is an iterator over tokens and errors:
+    /// ```rust
+    /// use apollo_parser::Lexer;
+    ///
+    /// let query = "# --- GraphQL here ---";
+    ///
+    /// let mut lexer = Lexer::new(query);
+    /// let mut tokens = vec![];
+    /// for token in lexer {
+    ///     match token {
+    ///         Ok(token) => tokens.push(token),
+    ///         Err(error) => panic!("{:?}", error),
+    ///     }
+    /// }
+    /// ```
+    pub fn new(input: &'a str) -> Self {
+        Self {
+            input,
+            index: 0,
+            finished: false,
+        }
+    }
 
-        while !input.is_empty() {
-            let old_input = input;
+    /// Lex the full source text, consuming the lexer.
+    pub fn lex(self) -> (Vec<Token>, Vec<Error>) {
+        let mut tokens = vec![];
+        let mut errors = vec![];
 
-            if old_input.len() == input.len() {
-                let mut c = Cursor::new(input);
-                let r = c.advance();
+        for item in self {
+            match item {
+                Ok(token) => tokens.push(token),
+                Err(error) => errors.push(error),
+            }
+        }
 
-                match r {
-                    Ok(mut token) => {
-                        token.index = index;
-                        index += token.data.len();
+        (tokens, errors)
+    }
+}
 
-                        input = &input[token.data.len()..];
-                        tokens.push(token);
-                    }
-                    Err(mut err) => {
-                        err.index = index;
-                        index += err.data.len();
+impl<'a> Iterator for Lexer<'a> {
+    type Item = Result<Token, Error>;
 
-                        input = &input[err.data.len()..];
-                        errors.push(err);
-                    }
-                }
-            }
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.finished {
+            return None;
         }
+        if self.input.is_empty() {
+            let mut eof = Token::new(TokenKind::Eof, String::from("EOF"));
+            eof.index = self.index;
 
-        let mut eof = Token::new(TokenKind::Eof, String::from("EOF"));
-        eof.index = index;
-        tokens.push(eof);
+            self.finished = true;
+            return Some(Ok(eof));
+        }
 
-        Self { tokens, errors }
-    }
+        let mut c = Cursor::new(self.input);
+        let r = c.advance();
 
-    /// Get a reference to the lexer's tokens.
-    pub fn tokens(&self) -> &[Token] {
-        self.tokens.as_slice()
-    }
+        match r {
+            Ok(mut token) => {
+                token.index = self.index;
+                self.index += token.data.len();
 
-    /// Get a reference to the lexer's errors.
-    pub fn errors(&self) -> Iter<'_, Error> {
-        self.errors.iter()
-    }
+                self.input = &self.input[token.data.len()..];
+                Some(Ok(token))
+            }
+            Err(mut err) => {
+                err.index = self.index;
+                self.index += err.data.len();
 
-    /// Consume the lexer and return the tokens and errors.
-    pub fn into_parts(self) -> (Vec<Token>, Vec<Error>) {
-        (self.tokens, self.errors)
+                self.input = &self.input[err.data.len()..];
+                Some(Err(err))
+            }
+        }
     }
 }
 
@@ -427,8 +448,8 @@ mod test {
     #[test]
     fn tests() {
         let gql_1 = "\"\nhello";
-        let lexer_1 = Lexer::new(gql_1);
-        dbg!(lexer_1.tokens);
-        dbg!(lexer_1.errors);
+        let (tokens, errors) = Lexer::new(gql_1).lex();
+        dbg!(tokens);
+        dbg!(errors);
     }
 }
diff --git a/crates/apollo-parser/src/parser/mod.rs b/crates/apollo-parser/src/parser/mod.rs
index 9e312af..1b7abcd 100644
--- a/crates/apollo-parser/src/parser/mod.rs
+++ b/crates/apollo-parser/src/parser/mod.rs
@@ -70,9 +70,10 @@ pub(crate) use token_text::TokenText;
 /// let document = ast.document();
 /// ```
 #[derive(Debug)]
-pub struct Parser {
-    /// Input tokens, including whitespace, in *reverse* order.
-    tokens: Vec<Token>,
+pub struct Parser<'a> {
+    lexer: Lexer<'a>,
+    /// Store one lookahead token so we don't need to reparse things as much.
+    current_token: Option<Token>,
     /// The in-progress tree.
     builder: Rc<RefCell<SyntaxTreeBuilder>>,
     /// The list of syntax errors we've accumulated so far.
@@ -83,18 +84,16 @@ pub struct Parser {
     accept_errors: bool,
 }
 
-impl Parser {
+impl<'a> Parser<'a> {
     /// Create a new instance of a parser given an input string.
-    pub fn new(input: &str) -> Self {
-        let (mut tokens, mut errors) = Lexer::new(input).into_parts();
-
-        tokens.reverse();
-        errors.reverse();
+    pub fn new(input: &'a str) -> Self {
+        let lexer = Lexer::new(input);
 
         Self {
-            tokens,
+            lexer,
+            current_token: None,
             builder: Rc::new(RefCell::new(SyntaxTreeBuilder::new())),
-            errors,
+            errors: Vec::new(),
             recursion_limit: Default::default(),
             accept_errors: true,
         }
@@ -102,7 +101,7 @@ impl Parser {
 
     /// Create a new resource limited instance of a parser given an input string
     /// and a recursion limit.
-    pub fn with_recursion_limit(input: &str, recursion_limit: usize) -> Self {
+    pub fn with_recursion_limit(input: &'a str, recursion_limit: usize) -> Self {
         let mut parser = Parser::new(input);
         parser.recursion_limit = LimitTracker::new(recursion_limit);
         parser
@@ -160,10 +159,7 @@ impl Parser {
 
     /// Consume a token from the lexer and add it to the AST.
     fn eat(&mut self, kind: SyntaxKind) {
-        let token = self
-            .tokens
-            .pop()
-            .expect("Could not eat a token from the AST");
+        let token = self.pop();
         self.builder.borrow_mut().token(kind, token.data());
     }
 
@@ -232,11 +228,30 @@ impl Parser {
         }
     }
 
+    /// Gets the next token from the lexer.
+    fn next_token(&mut self) -> Option<Token> {
+        for res in &mut self.lexer {
+            match res {
+                Err(e) => {
+                    self.errors.push(e);
+                }
+                Ok(token) => {
+                    return Some(token);
+                }
+            }
+        }
+
+        None
+    }
+
     /// Consume a token from the lexer.
     pub(crate) fn pop(&mut self) -> Token {
-        self.tokens
-            .pop()
-            .expect("Could not pop a token from the AST")
+        if let Some(token) = self.current_token.take() {
+            return token;
+        }
+
+        self.next_token()
+            .expect("Could not pop a token from the lexer")
     }
 
     /// Insert a token into the AST.
@@ -259,47 +274,43 @@ impl Parser {
     }
 
     /// Peek the next Token and return its TokenKind.
-    pub(crate) fn peek(&self) -> Option<TokenKind> {
-        self.tokens.last().map(|token| token.kind())
+    pub(crate) fn peek(&mut self) -> Option<TokenKind> {
+        self.peek_token().map(|token| token.kind())
     }
 
     /// Peek the next Token and return it.
-    pub(crate) fn peek_token(&self) -> Option<&Token> {
-        self.tokens.last()
+    pub(crate) fn peek_token(&mut self) -> Option<&Token> {
+        if self.current_token.is_none() {
+            self.current_token = self.next_token();
+        }
+        self.current_token.as_ref()
     }
 
     /// Peek Token `n` and return it.
-    pub(crate) fn peek_token_n(&self, n: usize) -> Option<&Token> {
-        self.tokens
+    pub(crate) fn peek_token_n(&self, n: usize) -> Option<Token> {
+        self.current_token
             .iter()
-            .rev()
+            .cloned()
+            .map(Result::Ok)
+            .chain(self.lexer.clone())
+            .filter_map(Result::ok)
             .filter(|token| !matches!(token.kind(), TokenKind::Whitespace | TokenKind::Comment))
             .nth(n - 1)
     }
 
     /// Peek Token `n` and return its TokenKind.
     pub(crate) fn peek_n(&self, n: usize) -> Option<TokenKind> {
-        self.tokens
-            .iter()
-            .rev()
-            .filter(|token| !matches!(token.kind(), TokenKind::Whitespace | TokenKind::Comment))
-            .nth(n - 1)
-            .map(|token| token.kind())
+        self.peek_token_n(n).map(|token| token.kind())
     }
 
     /// Peek next Token's `data` property.
-    pub(crate) fn peek_data(&self) -> Option<String> {
-        self.tokens.last().map(|token| token.data().to_string())
+    pub(crate) fn peek_data(&mut self) -> Option<String> {
+        self.peek_token().map(|token| token.data().to_string())
     }
 
     /// Peek `n` Token's `data` property.
     pub(crate) fn peek_data_n(&self, n: usize) -> Option<String> {
-        self.tokens
-            .iter()
-            .rev()
-            .filter(|token| !matches!(token.kind(), TokenKind::Whitespace | TokenKind::Comment))
-            .nth(n - 1)
-            .map(|token| token.data().to_string())
+        self.peek_token_n(n).map(|token| token.data().to_string())
     }
 }
 
diff --git a/fuzz/fuzz_targets/lexer.rs b/fuzz/fuzz_targets/lexer.rs
index 9d3a36b..7116d4d 100644
--- a/fuzz/fuzz_targets/lexer.rs
+++ b/fuzz/fuzz_targets/lexer.rs
@@ -13,9 +13,9 @@ fuzz_target!(|data: &[u8]| {
         }
     };
 
-    let lexer = panic::catch_unwind(|| Lexer::new(&doc_generated));
+    let lexer = panic::catch_unwind(|| Lexer::new(&doc_generated).lex());
 
-    let lexer = match lexer {
+    let (_tokens, errors) = match lexer {
         Err(err) => {
             panic!("error {:?}", err);
         }
@@ -27,10 +27,10 @@ fuzz_target!(|data: &[u8]| {
 
     // early return if the lexer detected an error
     let mut should_panic = false;
-    if lexer.errors().len() > 0 {
+    if !errors.is_empty() {
         should_panic = true;
-        let errors = lexer
-            .errors()
+        let errors = errors
+            .iter()
             .map(|err| err.message())
             .collect::<Vec<&str>>()
             .join("\n");


Test patch:
diff --git a/crates/apollo-compiler/src/tests.rs b/crates/apollo-compiler/src/tests.rs
index 0c3497e..fcf3b96 100644
--- a/crates/apollo-compiler/src/tests.rs
+++ b/crates/apollo-compiler/src/tests.rs
@@ -97,7 +97,7 @@ fn collect_graphql_files(root_dir: &Path, paths: &[&str]) -> Vec<(PathBuf, Strin
 /// Collects paths to all `.graphql` files from `dir` in a sorted `Vec<PathBuf>`.
 fn graphql_files_in_dir(dir: &Path) -> Vec<PathBuf> {
     let mut acc = Vec::new();
-    for file in fs::read_dir(&dir).unwrap() {
+    for file in fs::read_dir(dir).unwrap() {
         let file = file.unwrap();
         let path = file.path();
         if path.extension().unwrap_or_default() == "graphql" {
diff --git a/crates/apollo-parser/src/tests.rs b/crates/apollo-parser/src/tests.rs
index 047af0a..856a78e 100644
--- a/crates/apollo-parser/src/tests.rs
+++ b/crates/apollo-parser/src/tests.rs
@@ -6,7 +6,6 @@ use std::{
     fmt::Write,
     fs,
     path::{Path, PathBuf},
-    slice::Iter,
 };
 
 use expect_test::expect_file;
@@ -24,15 +23,15 @@ use crate::{Error, Lexer, Parser, Token};
 #[test]
 fn lexer_tests() {
     dir_tests(&test_data_dir(), &["lexer/ok"], "txt", |text, path| {
-        let tokens = Lexer::new(text);
-        assert_errors_are_absent(tokens.errors(), path);
-        dump_tokens_and_errors(tokens.tokens(), tokens.errors())
+        let (tokens, errors) = Lexer::new(text).lex();
+        assert_errors_are_absent(&errors, path);
+        dump_tokens_and_errors(&tokens, &errors)
     });
 
     dir_tests(&test_data_dir(), &["lexer/err"], "txt", |text, path| {
-        let tokens = Lexer::new(text);
-        assert_errors_are_present(tokens.errors(), path);
-        dump_tokens_and_errors(tokens.tokens(), tokens.errors())
+        let (tokens, errors) = Lexer::new(text).lex();
+        assert_errors_are_present(&errors, path);
+        dump_tokens_and_errors(&tokens, &errors)
     });
 }
 
@@ -41,31 +40,32 @@ fn parser_tests() {
     dir_tests(&test_data_dir(), &["parser/ok"], "txt", |text, path| {
         let parser = Parser::new(text);
         let ast = parser.parse();
-        assert_errors_are_absent(ast.errors(), path);
+        assert_errors_are_absent(&ast.errors().cloned().collect::<Vec<_>>(), path);
         format!("{:?}", ast)
     });
 
     dir_tests(&test_data_dir(), &["parser/err"], "txt", |text, path| {
         let parser = Parser::new(text);
         let ast = parser.parse();
-        assert_errors_are_present(ast.errors(), path);
+        assert_errors_are_present(&ast.errors().cloned().collect::<Vec<_>>(), path);
         format!("{:?}", ast)
     });
 }
 
-fn assert_errors_are_present(errors: Iter<'_, Error>, path: &Path) {
+fn assert_errors_are_present(errors: &[Error], path: &Path) {
     assert!(
-        errors.len() != 0,
+        !errors.is_empty(),
         "There should be errors in the file {:?}",
         path.display()
     );
 }
 
-fn assert_errors_are_absent(errors: Iter<'_, Error>, path: &Path) {
-    if errors.len() > 0 {
+fn assert_errors_are_absent(errors: &[Error], path: &Path) {
+    if !errors.is_empty() {
         println!(
             "errors: {}",
             errors
+                .iter()
                 .map(|e| e.message())
                 .collect::<Vec<&str>>()
                 .join("\n")
@@ -75,7 +75,7 @@ fn assert_errors_are_absent(errors: Iter<'_, Error>, path: &Path) {
 }
 
 /// Concatenate tokens and errors.
-fn dump_tokens_and_errors(tokens: &[Token], errors: Iter<'_, Error>) -> String {
+fn dump_tokens_and_errors(tokens: &[Token], errors: &[Error]) -> String {
     let mut acc = String::new();
     for token in tokens {
         writeln!(acc, "{:?}", token).unwrap();
@@ -123,7 +123,7 @@ fn collect_graphql_files(root_dir: &Path, paths: &[&str]) -> Vec<(PathBuf, Strin
 /// Collects paths to all `.graphql` files from `dir` in a sorted `Vec<PathBuf>`.
 fn graphql_files_in_dir(dir: &Path) -> Vec<PathBuf> {
     let mut acc = Vec::new();
-    for file in fs::read_dir(&dir).unwrap() {
+    for file in fs::read_dir(dir).unwrap() {
         let file = file.unwrap();
         let path = file.path();
         if path.extension().unwrap_or_default() == "graphql" {
diff --git a/crates/apollo-parser/test_data/parser/err/0034_unterminated_string_value_in_list.txt b/crates/apollo-parser/test_data/parser/err/0034_unterminated_string_value_in_list.txt
index 8123495..6564f0c 100644
--- a/crates/apollo-parser/test_data/parser/err/0034_unterminated_string_value_in_list.txt
+++ b/crates/apollo-parser/test_data/parser/err/0034_unterminated_string_value_in_list.txt
@@ -34,6 +34,10 @@
                             - ENUM_VALUE@96..98
                                 - NAME@96..98
                                     - IDENT@96..98 "id"
+- ERROR@96:138 "unexpected line terminator" "@external])
+
+
+type Vehicle @key(fields: "
 - ERROR@140:237 "unterminated string value" ") {
   id: ID!,
   type: String,
@@ -42,9 +46,5 @@
   launchDate: String
 }
 
-- ERROR@96:138 "unexpected line terminator" "@external])
-
-
-type Vehicle @key(fields: "
 - ERROR@237:237 "expected R_PAREN, got EOF" EOF
 recursion limit: 4096, high: 0
\ No newline at end of file
diff --git a/crates/apollo-parser/test_data/parser/err/0035_unterminated_string_value_in_object_value.txt b/crates/apollo-parser/test_data/parser/err/0035_unterminated_string_value_in_object_value.txt
index 1422631..3770bcf 100644
--- a/crates/apollo-parser/test_data/parser/err/0035_unterminated_string_value_in_object_value.txt
+++ b/crates/apollo-parser/test_data/parser/err/0035_unterminated_string_value_in_object_value.txt
@@ -46,12 +46,12 @@
                                             - ENUM_VALUE@68..70
                                                 - NAME@68..70
                                                     - IDENT@68..70 "en"
-- ERROR@108:116 "unterminated string value" ")
-  }
-}
 - ERROR@68:106 "unexpected line terminator" "my store }]
   }) {
     name(locale: "
+- ERROR@108:116 "unterminated string value" ")
+  }
+}
 - ERROR@116:116 "expected }" EOF
 - ERROR@116:116 "expected }" EOF
 - ERROR@116:116 "expected R_PAREN, got EOF" EOF