Repository: graphql/graphql-js
Pull request #3684 (2022-07-28 16:10:01)

parser: limit maximum number of tokens
Motivation: Parser CPU and memory usage are linear to the number of tokens in a document however, in extreme cases, it becomes quadratic due to memory exhaustion.
On my machine, it happens on queries with 2k tokens.
For example:
```
{ a a <repeat 2k times> a }
```
It takes 741ms on my machine.
But if we create a document of the same size but a smaller number of tokens, it would be a lot faster.
Example:
```
{ a(arg: "a <repeat 2k times> a" }
```
Now it takes only 17ms to process, which is 43 times faster.

If we just limit document size, we should make this limit small since it takes only two bytes to create a token, e.g. ` a`.
But that will create issues for legit documents with long tokens (comments, descriptions, strings, long names, etc.).

That's why this PR adds a mechanism to limit the number of tokens in the parsed document.
Also, exact same mechanism is implemented in graphql-java, see:
https://github.com/graphql-java/graphql-java/pull/2549

I also tried the alternative approach of counting nodes, and it gives
slightly better approximation of how many resources would be consumed.
However, compared to the tokens, AST nodes are an implementation detail of graphql-js
so it's impossible to replicate in other implementations (e.g. to count
this number on a client).

netlify[bot]: ### <span aria-hidden="true">👷</span> Deploy Preview for *compassionate-pike-271cb3* processing.


|  Name | Link |
|---------------------------------|------------------------|
|<span aria-hidden="true">🔨</span> Latest commit | e04ce2eed83a7dc10a7c38698f7909c33b1b950e |
|<span aria-hidden="true">🔍</span> Latest deploy log | https://app.netlify.com/sites/compassionate-pike-271cb3/deploys/62e2b4dbba733b000a43a171 |
github-actions[bot]: Hi @IvanGoncharov, I'm @github-actions bot happy to help you with this PR 👋

<details>
<summary> Supported commands </summary>

Please post this commands in separate comments and only one per comment:
* `@github-actions run-benchmark` - Run benchmark comparing base and merge commits for this PR
* `@github-actions publish-pr-on-npm` - Build package from this PR and publish it on NPM
</details>

saihaj: @github-actions run-benchmark
github-actions[bot]: > @github-actions run-benchmark

@saihaj Please, see benchmark results here: https://github.com/graphql/graphql-js/runs/7580332109?check_suite_focus=true#step:6:1

Patch:
diff --git a/src/language/parser.ts b/src/language/parser.ts
index d74384ef..e37f02b7 100644
--- a/src/language/parser.ts
+++ b/src/language/parser.ts
@@ -82,6 +82,15 @@ export interface ParseOptions {
    */
   noLocation?: boolean | undefined;
 
+  /**
+   * Parser CPU and memory usage is linear to the number of tokens in a document
+   * however in extreme cases it becomes quadratic due to memory exhaustion.
+   * Parsing happens before validation so even invalid queries can burn lots of
+   * CPU time and memory.
+   * To prevent this you can set a maximum number of tokens allowed within a document.
+   */
+  maxTokens?: number | undefined;
+
   /**
    * @deprecated will be removed in the v17.0.0
    *
@@ -206,12 +215,14 @@ export function parseType(
 export class Parser {
   protected _options: ParseOptions;
   protected _lexer: Lexer;
+  protected _tokenCounter: number;
 
   constructor(source: string | Source, options: ParseOptions = {}) {
     const sourceObj = isSource(source) ? source : new Source(source);
 
     this._lexer = new Lexer(sourceObj);
     this._options = options;
+    this._tokenCounter = 0;
   }
 
   /**
@@ -634,13 +645,13 @@ export class Parser {
       case TokenKind.BRACE_L:
         return this.parseObject(isConst);
       case TokenKind.INT:
-        this._lexer.advance();
+        this.advanceLexer();
         return this.node<IntValueNode>(token, {
           kind: Kind.INT,
           value: token.value,
         });
       case TokenKind.FLOAT:
-        this._lexer.advance();
+        this.advanceLexer();
         return this.node<FloatValueNode>(token, {
           kind: Kind.FLOAT,
           value: token.value,
@@ -649,7 +660,7 @@ export class Parser {
       case TokenKind.BLOCK_STRING:
         return this.parseStringLiteral();
       case TokenKind.NAME:
-        this._lexer.advance();
+        this.advanceLexer();
         switch (token.value) {
           case 'true':
             return this.node<BooleanValueNode>(token, {
@@ -695,7 +706,7 @@ export class Parser {
 
   parseStringLiteral(): StringValueNode {
     const token = this._lexer.token;
-    this._lexer.advance();
+    this.advanceLexer();
     return this.node<StringValueNode>(token, {
       kind: Kind.STRING,
       value: token.value,
@@ -1479,7 +1490,7 @@ export class Parser {
   expectToken(kind: TokenKind): Token {
     const token = this._lexer.token;
     if (token.kind === kind) {
-      this._lexer.advance();
+      this.advanceLexer();
       return token;
     }
 
@@ -1497,7 +1508,7 @@ export class Parser {
   expectOptionalToken(kind: TokenKind): boolean {
     const token = this._lexer.token;
     if (token.kind === kind) {
-      this._lexer.advance();
+      this.advanceLexer();
       return true;
     }
     return false;
@@ -1510,7 +1521,7 @@ export class Parser {
   expectKeyword(value: string): void {
     const token = this._lexer.token;
     if (token.kind === TokenKind.NAME && token.value === value) {
-      this._lexer.advance();
+      this.advanceLexer();
     } else {
       throw syntaxError(
         this._lexer.source,
@@ -1527,7 +1538,7 @@ export class Parser {
   expectOptionalKeyword(value: string): boolean {
     const token = this._lexer.token;
     if (token.kind === TokenKind.NAME && token.value === value) {
-      this._lexer.advance();
+      this.advanceLexer();
       return true;
     }
     return false;
@@ -1616,6 +1627,22 @@ export class Parser {
     } while (this.expectOptionalToken(delimiterKind));
     return nodes;
   }
+
+  advanceLexer(): void {
+    const { maxTokens } = this._options;
+    const token = this._lexer.advance();
+
+    if (maxTokens !== undefined && token.kind !== TokenKind.EOF) {
+      ++this._tokenCounter;
+      if (this._tokenCounter > maxTokens) {
+        throw syntaxError(
+          this._lexer.source,
+          token.start,
+          `Document contains more that ${maxTokens} tokens. Parsing aborted.`,
+        );
+      }
+    }
+  }
 }
 
 /**
diff --git a/src/type/validate.ts b/src/type/validate.ts
index ce710a08..73eabed8 100644
--- a/src/type/validate.ts
+++ b/src/type/validate.ts
@@ -618,7 +618,7 @@ function getAllImplementsInterfaceNodes(
 function getUnionMemberTypeNodes(
   union: GraphQLUnionType,
   typeName: string,
-): Maybe<ReadonlyArray<NamedTypeNode>> {
+): ReadonlyArray<NamedTypeNode> {
   const { astNode, extensionASTNodes } = union;
   const nodes: ReadonlyArray<UnionTypeDefinitionNode | UnionTypeExtensionNode> =
     astNode != null ? [astNode, ...extensionASTNodes] : extensionASTNodes;


Test patch:
diff --git a/src/language/__tests__/parser-test.ts b/src/language/__tests__/parser-test.ts
index 651da1ca..cb722204 100644
--- a/src/language/__tests__/parser-test.ts
+++ b/src/language/__tests__/parser-test.ts
@@ -88,6 +88,19 @@ describe('Parser', () => {
     `);
   });
 
+  it('limit maximum number of tokens', () => {
+    expect(() => parse('{ foo }', { maxTokens: 3 })).to.not.throw();
+    expect(() => parse('{ foo }', { maxTokens: 2 })).to.throw(
+      'Syntax Error: Document contains more that 2 tokens. Parsing aborted.',
+    );
+
+    expect(() => parse('{ foo(bar: "baz") }', { maxTokens: 8 })).to.not.throw();
+
+    expect(() => parse('{ foo(bar: "baz") }', { maxTokens: 7 })).to.throw(
+      'Syntax Error: Document contains more that 7 tokens. Parsing aborted.',
+    );
+  });
+
   it('parses variable inline values', () => {
     expect(() =>
       parse('{ field(complex: { a: { b: [ $var ] } }) }'),