Repository: eslint/eslint (js)

Issue:
Maximum call stack size exceeded
<!--
    ESLint adheres to the [JS Foundation Code of Conduct](https://js.foundation/community/code-of-conduct).

    This template is for bug reports. If you are reporting a bug, please continue on. If you are here for another reason, please see below:

    1. To propose a new rule: http://eslint.org/docs/developer-guide/contributing/new-rules
    2. To request a change: http://eslint.org/docs/developer-guide/contributing/changes
    3. If you have any questions, please stop by our chatroom: https://gitter.im/eslint/eslint

    Note that leaving sections blank will make it difficult for us to troubleshoot and we may have to close the issue.
-->

**Tell us about your environment**

* **ESLint Version:**
^4.7.0
* **Node Version:**
6.4.0
* **npm Version:**
3.10.1

**Please show your full configuration:**

<details>
<summary>Configuration</summary>

<!-- Paste your configuration below: -->
```js
{
    "env": {
        "browser": true,
        "node": true
    },
    "globals": {
        "Promise": true
    },
    "parserOptions": {
        "ecmaVersion": 6,
        "ecmaFeatures": {
            "jsx": true,
            "impliedStrict": true
        },
        "sourceType": "module"
    },
    "rules": {
        "arrow-body-style": ["error", "as-needed"],
        "block-scoped-var": "error",
        "camelcase": ["error", {"properties": "never"}],
        "complexity": "error",
        "consistent-this": ["error", "me"],
        "consistent-return": "error",
        "curly": "error",
        "dot-notation": "error",
        "lodash/chaining": "off",
        "lodash/import-scope": "off",
        "lodash/prefer-constant": "off",
        "lodash/prefer-includes": "error",
        "lodash/prefer-lodash-chain": "off",
        "lodash/prefer-lodash-method": "off",
        "lodash/path-style": ["error", "as-needed"],
        "max-len": ["error", {"code": 120}],
        "max-lines": ["error", 300],
        "max-params": ["error", 8],
        "max-statements": ["error", 25],
        "max-statements-per-line": ["error", {"max": 2}],
        "new-cap": "error",
        "no-alert": "error",
        "no-console": ["error", {"allow": ["error"]}],
        "no-constant-condition": ["error", {"checkLoops": false}],
        "no-eq-null": "error",
        "no-eval": "error",
        "no-extra-label": "error",
        "no-extra-bind": "error",
        "no-extend-native": "error",
        "no-fallthrough": "error",
        "no-invalid-this": "error",
        "no-lone-blocks": "error",
        "no-lonely-if": "error",
        "no-mixed-spaces-and-tabs": "off",
        "no-negated-condition": "error",
        "no-return-assign": "error",
        "no-restricted-globals": ["error", "fetch", "self", "module"],
        "no-self-compare": "error",
        "no-sequences": "error",
        "no-unused-expressions": "error",
        "no-unused-vars": ["error", {"args": "all", "argsIgnorePattern": "^_"}],
        "no-useless-computed-key": "error",
        "no-useless-escape": "error",
        "no-use-before-define": "error",
        "no-unreachable": "error",
        "no-useless-call": "error",
        "no-useless-concat": "error",
        "no-void": "error",
        "no-with": "error",
        "prefer-const": ["error", {"destructuring": "all"}],
        "prefer-rest-params": "error",
        "prefer-spread": "error",
        "prettier/prettier": ["error", {"trailingComma": "es5", "printWidth": 120, "jsxBracketSameLine": true}],
        "promise/catch-or-return": "error",
        "react/no-unused-prop-types": "error",
        "react/jsx-key": "error",
        "strict": "error",
        "tape/no-ignored-test-files": ["error", {"files": ["static/__tests__/**/*test.js", "static/__tests__/**/*test.jsx"]}]
    },
    "plugins": [
        "lodash",
        "promise",
        "react",
        "tape",
        "prettier"
    ],
    "extends": [
        "eslint:recommended",
        "plugin:lodash/recommended",
        "plugin:react/recommended",
        "plugin:tape/recommended",
        "prettier"
    ]
}


```

</details>

**What did you do? Please include the actual source code causing the issue.**

I tried to run the following command (which worked up until eslint@4.6.1):

npm run eslint static *.js --ext .js --ext .jsx -f node_modules/eslint-clang-formatter


**What actually happened? Please include the actual, raw output from ESLint.**
The command fails with this exception:

Maximum call stack size exceeded
RangeError: Maximum call stack size exceeded
    at cloneOf (/NImounts/NiNoSnapUsers/aschonfeld/dev/git/grail/node_modules/espurify/lib/clone-ast.js:54:22)
    at cloneObject (/NImounts/NiNoSnapUsers/aschonfeld/dev/git/grail/node_modules/espurify/lib/clone-ast.js:49:            26)
    at cloneNodeOrObject (/NImounts/NiNoSnapUsers/aschonfeld/dev/git/grail/node_modules/espurify/lib/clone-ast.            js:21:20)
    at cloneOf (/NImounts/NiNoSnapUsers/aschonfeld/dev/git/grail/node_modules/espurify/lib/clone-ast.js:61:24)
    at cloneObject (/NImounts/NiNoSnapUsers/aschonfeld/dev/git/grail/node_modules/espurify/lib/clone-ast.js:49:            26)
    at cloneNodeOrObject (/NImounts/NiNoSnapUsers/aschonfeld/dev/git/grail/node_modules/espurify/lib/clone-ast.            js:21:20)
    at cloneOf (/NImounts/NiNoSnapUsers/aschonfeld/dev/git/grail/node_modules/espurify/lib/clone-ast.js:61:24)
    at cloneObject (/NImounts/NiNoSnapUsers/aschonfeld/dev/git/grail/node_modules/espurify/lib/clone-ast.js:49:            26)
    at cloneNodeOrObject (/NImounts/NiNoSnapUsers/aschonfeld/dev/git/grail/node_modules/espurify/lib/clone-ast.            js:21:20)
    at cloneOf (/NImounts/NiNoSnapUsers/aschonfeld/dev/git/grail/node_modules/espurify/lib/clone-ast.js:61:24)


Pull request description:
Fix: Revert setting node.parent early (fixes #9331)
<!--
    ESLint adheres to the [JS Foundation Code of Conduct](https://js.foundation/community/code-of-conduct).
-->

**What is the purpose of this pull request? (put an "X" next to item)**

[ ] Documentation update
[ ] Bug fix ([template](https://raw.githubusercontent.com/eslint/eslint/master/templates/bug-report.md))
[ ] New rule ([template](https://raw.githubusercontent.com/eslint/eslint/master/templates/rule-proposal.md))
[ ] Changes an existing rule ([template](https://raw.githubusercontent.com/eslint/eslint/master/templates/rule-change-proposal.md))
[ ] Add autofixing to a rule
[ ] Add a CLI option
[ ] Add something to the core
[ ] Other, please explain:

<!--
    If the item you've checked above has a template, please paste the template questions below and answer them. (If this pull request is addressing an issue, you can just paste a link to the issue here instead.)
-->

<!--
    Please ensure your pull request is ready:

    - Read the pull request guide (http://eslint.org/docs/developer-guide/contributing/pull-requests)
    - Include tests for this change
    - Update documentation for this change (if appropriate)
-->

<!--
    The following is required for all pull requests:
-->

**What changes did you make? (Give an overview)**

This reverts commit 1488b511f3be3220d6f187f48c8b22075c6bbd30. Some rules
from plugins were relying on the behavior that a a `node.parent`
property is only sometines present, and other rules were relying on the
behavior that the AST contains no cycles when rules are created.

I think we should plan to make this change next major release, since I still think it's an improvement over the existing rule API.

**Is there anything you'd like reviewers to focus on?**

Nothing in particular

Patch:
diff --git a/docs/developer-guide/working-with-plugins.md b/docs/developer-guide/working-with-plugins.md
index 859f2a818..5cf63b7ee 100644
--- a/docs/developer-guide/working-with-plugins.md
+++ b/docs/developer-guide/working-with-plugins.md
@@ -204,7 +204,7 @@ All nodes must have `range` property.
 * `range` (`number[]`) is an array of two numbers. Both numbers are a 0-based index which is the position in the array of source code characters. The first is the start position of the node, the second is the end position of the node. `code.slice(node.range[0], node.range[1])` must be the text of the node. This range does not include spaces/parentheses which are around the node.
 * `loc` (`SourceLocation`) must not be `null`. [The `loc` property is defined as nullable by ESTree](https://github.com/estree/estree/blob/25834f7247d44d3156030f8e8a2d07644d771fdb/es5.md#node-objects), but ESLint requires this property. On the other hand, `SourceLocation#source` property can be `undefined`. ESLint does not use the `SourceLocation#source` property.
 
-The `parent` property of all nodes must be rewriteable. ESLint sets each node's `parent` property to its parent node while traversing, before any rules have access to the AST.
+The `parent` property of all nodes must be rewriteable. ESLint sets each node's parent properties to its parent node while traversing.
 
 #### The `Program` node:
 
diff --git a/lib/linter.js b/lib/linter.js
index b03ef2002..2172cb24e 100755
--- a/lib/linter.js
+++ b/lib/linter.js
@@ -660,22 +660,6 @@ function markVariableAsUsed(scopeManager, currentNode, parserOptions, name) {
     return false;
 }
 
-/**
- * Gets all the ancestors of a given node
- * @param {ASTNode} node The node
- * @returns {ASTNode[]} All the ancestor nodes in the AST, not including the provided node, starting
- * from the root node and going inwards to the parent node.
- */
-function getAncestors(node) {
-    if (node.parent) {
-        const parentAncestors = getAncestors(node.parent);
-
-        parentAncestors.push(node.parent);
-        return parentAncestors;
-    }
-    return [];
-}
-
 // methods that exist on SourceCode object
 const DEPRECATED_SOURCECODE_PASSTHROUGHS = {
     getSource: "getText",
@@ -835,6 +819,7 @@ module.exports = class Linter {
         }
 
         const emitter = new EventEmitter().setMaxListeners(Infinity);
+        const traverser = new Traverser();
         const ecmaFeatures = config.parserOptions.ecmaFeatures || {};
         const ecmaVersion = config.parserOptions.ecmaVersion || 5;
         const scopeManager = eslintScope.analyze(sourceCode.ast, {
@@ -846,19 +831,6 @@ module.exports = class Linter {
             fallback: Traverser.getKeys
         });
 
-        let currentNode = sourceCode.ast;
-        const nodeQueue = [];
-
-        new Traverser().traverse(sourceCode.ast, {
-            enter(node, parent) {
-                node.parent = parent;
-                nodeQueue.push({ isEntering: true, node });
-            },
-            leave(node) {
-                nodeQueue.push({ isEntering: false, node });
-            }
-        });
-
         /*
          * Create a frozen object with the ruleContext properties and methods that are shared by all rules.
          * All rule contexts will inherit from this object. This avoids the performance penalty of copying all the
@@ -868,12 +840,12 @@ module.exports = class Linter {
             Object.assign(
                 Object.create(BASE_TRAVERSAL_CONTEXT),
                 {
-                    getAncestors: () => getAncestors(currentNode),
+                    getAncestors: () => traverser.parents(),
                     getDeclaredVariables: scopeManager.getDeclaredVariables.bind(scopeManager),
                     getFilename: () => filename,
-                    getScope: () => getScope(scopeManager, currentNode, config.parserOptions.ecmaVersion),
+                    getScope: () => getScope(scopeManager, traverser.current(), config.parserOptions.ecmaVersion),
                     getSourceCode: () => sourceCode,
-                    markVariableAsUsed: name => markVariableAsUsed(scopeManager, currentNode, config.parserOptions, name),
+                    markVariableAsUsed: name => markVariableAsUsed(scopeManager, traverser.current(), config.parserOptions, name),
                     parserOptions: config.parserOptions,
                     parserPath: config.parser,
                     parserServices,
@@ -978,13 +950,19 @@ module.exports = class Linter {
 
         const eventGenerator = new CodePathAnalyzer(new NodeEventGenerator(emitter));
 
-        nodeQueue.forEach(traversalInfo => {
-            currentNode = traversalInfo.node;
-
-            if (traversalInfo.isEntering) {
-                eventGenerator.enterNode(currentNode);
-            } else {
-                eventGenerator.leaveNode(currentNode);
+        /*
+         * Each node has a type property. Whenever a particular type of
+         * node is found, an event is fired. This allows any listeners to
+         * automatically be informed that this type of node has been found
+         * and react accordingly.
+         */
+        traverser.traverse(sourceCode.ast, {
+            enter(node, parent) {
+                node.parent = parent;
+                eventGenerator.enterNode(node);
+            },
+            leave(node) {
+                eventGenerator.leaveNode(node);
             }
         });
 
diff --git a/lib/util/source-code.js b/lib/util/source-code.js
index 1c6620ed7..af01ff3fa 100644
--- a/lib/util/source-code.js
+++ b/lib/util/source-code.js
@@ -349,13 +349,15 @@ class SourceCode extends TokenStore {
      * @returns {ASTNode} The node if found or null if not found.
      */
     getNodeByRangeIndex(index) {
-        let result = null;
+        let result = null,
+            resultParent = null;
         const traverser = new Traverser();
 
         traverser.traverse(this.ast, {
-            enter(node) {
+            enter(node, parent) {
                 if (node.range[0] <= index && index < node.range[1]) {
                     result = node;
+                    resultParent = parent;
                 } else {
                     this.skip();
                 }
@@ -367,7 +369,7 @@ class SourceCode extends TokenStore {
             }
         });
 
-        return result;
+        return result ? Object.assign({ parent: resultParent }, result) : null;
     }
 
     /**


Test patch:
diff --git a/tests/lib/linter.js b/tests/lib/linter.js
index 00f9e83d7..eda0bd571 100644
--- a/tests/lib/linter.js
+++ b/tests/lib/linter.js
@@ -100,21 +100,6 @@ describe("Linter", () => {
                 linter.verify(code, config, filename, true);
             }, "Intentional error.");
         });
-
-        it("has all the `parent` properties on nodes when the rule listeners are created", () => {
-            linter.defineRule("checker", context => {
-                const ast = context.getSourceCode().ast;
-
-                assert.strictEqual(ast.body[0].parent, ast);
-                assert.strictEqual(ast.body[0].expression.parent, ast.body[0]);
-                assert.strictEqual(ast.body[0].expression.left.parent, ast.body[0].expression);
-                assert.strictEqual(ast.body[0].expression.right.parent, ast.body[0].expression);
-
-                return {};
-            });
-
-            linter.verify("foo + bar", { rules: { checker: "error" } });
-        });
     });
 
     describe("context.getSourceLines()", () => {
@@ -447,6 +432,43 @@ describe("Linter", () => {
             linter.verify(code, config);
             assert(spy.calledOnce);
         });
+
+        it("should attach the node's parent", () => {
+            const config = { rules: { checker: "error" } };
+            const spy = sandbox.spy(context => {
+                const node = context.getNodeByRangeIndex(14);
+
+                assert.property(node, "parent");
+                assert.equal(node.parent.type, "VariableDeclarator");
+                return {};
+            });
+
+            linter.defineRule("checker", spy);
+            linter.verify(code, config);
+            assert(spy.calledOnce);
+        });
+
+        it("should not modify the node when attaching the parent", () => {
+            const config = { rules: { checker: "error" } };
+            const spy = sandbox.spy(context => {
+                const node1 = context.getNodeByRangeIndex(10);
+
+                assert.equal(node1.type, "VariableDeclarator");
+
+                const node2 = context.getNodeByRangeIndex(4);
+
+                assert.equal(node2.type, "Identifier");
+                assert.property(node2, "parent");
+                assert.equal(node2.parent.type, "VariableDeclarator");
+                assert.notProperty(node2.parent, "parent");
+                return {};
+            });
+
+            linter.defineRule("checker", spy);
+            linter.verify(code, config);
+            assert(spy.calledOnce);
+        });
+
     });
 
 
diff --git a/tests/lib/util/source-code.js b/tests/lib/util/source-code.js
index b902bd2a1..ac0cfa79d 100644
--- a/tests/lib/util/source-code.js
+++ b/tests/lib/util/source-code.js
@@ -1775,6 +1775,25 @@ describe("SourceCode", () => {
             node = sourceCode.getNodeByRangeIndex(-99);
             assert.isNull(node);
         });
+
+        it("should attach the node's parent", () => {
+            const node = sourceCode.getNodeByRangeIndex(14);
+
+            assert.property(node, "parent");
+            assert.equal(node.parent.type, "VariableDeclarator");
+        });
+
+        it("should not modify the node when attaching the parent", () => {
+            let node = sourceCode.getNodeByRangeIndex(10);
+
+            assert.equal(node.type, "VariableDeclarator");
+            node = sourceCode.getNodeByRangeIndex(4);
+            assert.equal(node.type, "Identifier");
+            assert.property(node, "parent");
+            assert.equal(node.parent.type, "VariableDeclarator");
+            assert.notProperty(node.parent, "parent");
+        });
+
     });
 
     describe("isSpaceBetweenTokens()", () => {