Repository: eslint/eslint (js)

Issue:
require-atomic-updates takes a very long time to run on large files
<!--
    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 here for another reason, please see below:

    1. To propose a new rule: https://eslint.org/docs/developer-guide/contributing/new-rules
    2. To request a rule change: https://eslint.org/docs/developer-guide/contributing/rule-changes
    3. To request a change that is not a bug fix, rule change, or new rule: https://eslint.org/docs/developer-guide/contributing/changes
    4. 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:** 5.6 (though issue starts at 5.3)
* **Node Version:** 10.3.0
* **npm Version:** 6.1.0

**What parser (default, Babel-ESLint, etc.) are you using?**
babel-eslint

**Please show your full configuration:**

<details>
<summary>Configuration</summary>

<!-- Paste your configuration below: -->
```js
{
    "extends": "@spothero",
    "settings": {
        "react": {
            "version": "latest"
        }
    },
    "rules": {
        "require-atomic-updates": 2
    }
}

```

</details>

**What did you do? Please include the actual source code causing the issue, as well as the command that you used to run ESLint.**

<!-- Paste the source code below: -->
```js
import includes from 'lodash/includes';
import moment from 'moment';
import APIUtils from '@spothero/utils/api';
import StorageUtils from '@spothero/utils/storage';
import Config from 'config';
import UserUtils from 'user/user-utils';
import SearchTracking from 'utils/search-tracking';
import SegmentUtils from 'utils/segment';

const ReservationAPI = {
    async add({
        checkoutData,
        selectedRate,
        monthlyStarts = null,
        facility,
        onError,
        stripeToken = false,
        stripePaymentType = 'cc',
        setNewCardAsDefault = false,
        onSuccess = null,
        includeVehicleInResponse = false,
        includeFacilityInResponse = false,
        source = null,
        rentalSourceReferrer = null,
        checkoutStartTime = null
    }) {
        const {
            user,
            promoCode,
            isMonthly,
            eventId,
            paymentRequired,
            purchaseForCustomer,
            purchaseForCustomerReferralSource,
            purchaseForCustomerDescription,
            purchaseOnBehalfOfCustomer,
            affiliate,
            phoneNumberRequired,
            selectedCreditCard,
            licensePlateRequired,
            selectedLicensePlate,
            licensePlateState,
            newLicensePlate,
            newLicensePlateName,
            newLicensePlateIsDefault,
            referralSource,
            smsParkingPass,
            forceRedundantMonthly,
            vehicleMake,
            vehicleModel,
            vehicleYear,
            vehicleColor,
            saveVehicleAsDefault,
            acceptedTerms,
            contractFullName
        } = checkoutData;
        const ratePrice = (selectedRate.price / 100);
        const phoneNumberCleaned = (user.phoneNumber) ? user.phoneNumber.replace(/\D/g, '') : null;
        const isUserSavingNewCard = (user.status === UserUtils.AUTH_STATE.USER && selectedCreditCard === 'new' && !purchaseForCustomer && paymentRequired);
        const isMonthlyRecurringNewCard = (selectedCreditCard === 'new' && isMonthly && selectedRate.recurrable);
        const isPaymentRequired = (selectedCreditCard === 'admin') ? false : paymentRequired;
        const {
            searchUUID,
            actionUUID
        } = SearchTracking.getValues();
        const postData = {
            email: user.email,
            price: parseInt(Math.round(Number(ratePrice) * 100), 10),
            facility: facility.parking_spot_id,
            apply_sh_credit: (user.status === UserUtils.AUTH_STATE.USER),
            search_id: searchUUID,
            action_id: actionUUID
        };
        const config = {};
        const shExperimentVariations = StorageUtils.get('sh-experiment-variations', 'cookie');

        if (includeFacilityInResponse) {
            postData.include = 'facility';
        }

        if (includeVehicleInResponse) {
            if (postData.include) {
                postData.include += ',vehicle_info';
            } else {
                postData.include = 'vehicle_info';
            }
        }

        if (isMonthly) {
            postData.monthly_start_date = moment(monthlyStarts).format(Config.apiDateFormat);
            postData.rule = selectedRate.fullRule;
        } else {
            postData.starts = selectedRate.starts;
            postData.ends = selectedRate.ends;
            postData.rule_group_id = selectedRate.rule_group_id;
        }

        if (eventId) {
            postData.event = eventId;
        }

        if (user.phoneNumber && !phoneNumberCleaned) {
            postData.phone_number = user.phoneNumber;
        } else {
            if (phoneNumberCleaned) {
                postData.phone_number = phoneNumberCleaned;
            }
        }
    },
};

export default ReservationAPI;
```

<!-- Paste the command you used to run ESLint: -->
```bash
eslint test.js
```

**What did you expect to happen?**
ESLint runs quickly on that file and shows all errors.

**What actually happened? Please include the actual, raw output from ESLint.**
The expected behavior happened, however it took WAY longer than it should have on this file. The file is contrived, its just a part of a file in our codebase where I started to see issues when I started to drill down into this.  We just upgraded from ESLint 5.2 to 5.6 on a large codebase and ESLint was stalling. We use our own config (https://github.com/spothero/eslint-config) so I naturally thought it was something I had messed up in the config.

I then created a repo that just had the `test.js` file and the above `.eslintrc` file. Through editing various things, I was finally able to realize that the `require-atomic-updates` rule was the culprit. If you disable it in the config with `0`, the file executes quickly. If you enable it, the file takes MUCH longer to execute. This becomes magnified when you have many files in the codebase and ESLint just seems to hang without ever finishing them and moving on to the next build step.

Pull request description:
Fix: avoid exponential require-atomic-updates traversal (fixes #10893)
<!--
    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
[x] Bug fix (https://github.com/eslint/eslint/issues/10893)
[ ] 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 (https://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)**

Previously, the `require-atomic-updates` rule would traverse over every path in the control flow graph, resulting in a runtime that was exponential in the number of edges in the graph. This commit updates the rule to use a lattice-based [dataflow analysis](https://en.wikipedia.org/wiki/Data-flow_analysis) algorithm, similar to the algorithms used by optimizing compilers.

**Is there anything you'd like reviewers to focus on?**

Nothing in particular

Patch:
diff --git a/lib/rules/one-var.js b/lib/rules/one-var.js
index 13ab72b04..15b664d77 100644
--- a/lib/rules/one-var.js
+++ b/lib/rules/one-var.js
@@ -384,8 +384,13 @@ module.exports = {
             if (nodeIndex > 0) {
                 const previousNode = parent.body[nodeIndex - 1];
                 const isPreviousNodeDeclaration = previousNode.type === "VariableDeclaration";
+                const declarationsWithPrevious = declarations.concat(previousNode.declarations || []);
 
-                if (isPreviousNodeDeclaration && previousNode.kind === type) {
+                if (
+                    isPreviousNodeDeclaration &&
+                    previousNode.kind === type &&
+                    !(declarationsWithPrevious.some(isRequire) && !declarationsWithPrevious.every(isRequire))
+                ) {
                     const previousDeclCounts = countDeclarations(previousNode.declarations);
 
                     if (options[type].initialized === MODE_CONSECUTIVE && options[type].uninitialized === MODE_CONSECUTIVE) {
diff --git a/lib/rules/require-atomic-updates.js b/lib/rules/require-atomic-updates.js
index 5d7d71514..c6cf0d747 100644
--- a/lib/rules/require-atomic-updates.js
+++ b/lib/rules/require-atomic-updates.js
@@ -119,6 +119,66 @@ module.exports = {
             });
         }
 
+        const alreadyReportedAssignments = new WeakSet();
+
+        class AssignmentTrackerState {
+            constructor({ openAssignmentsWithoutReads = new Set(), openAssignmentsWithReads = new Set() } = {}) {
+                this.openAssignmentsWithoutReads = openAssignmentsWithoutReads;
+                this.openAssignmentsWithReads = openAssignmentsWithReads;
+            }
+
+            copy() {
+                return new AssignmentTrackerState({
+                    openAssignmentsWithoutReads: new Set(this.openAssignmentsWithoutReads),
+                    openAssignmentsWithReads: new Set(this.openAssignmentsWithReads)
+                });
+            }
+
+            merge(other) {
+                const initialAssignmentsWithoutReadsCount = this.openAssignmentsWithoutReads.size;
+                const initialAssignmentsWithReadsCount = this.openAssignmentsWithReads.size;
+
+                other.openAssignmentsWithoutReads.forEach(assignment => this.openAssignmentsWithoutReads.add(assignment));
+                other.openAssignmentsWithReads.forEach(assignment => this.openAssignmentsWithReads.add(assignment));
+
+                return this.openAssignmentsWithoutReads.size > initialAssignmentsWithoutReadsCount ||
+                    this.openAssignmentsWithReads.size > initialAssignmentsWithReadsCount;
+            }
+
+            enterAssignment(assignmentExpression) {
+                (assignmentExpression.operator === "=" ? this.openAssignmentsWithoutReads : this.openAssignmentsWithReads).add(assignmentExpression);
+            }
+
+            exitAssignment(assignmentExpression) {
+                this.openAssignmentsWithoutReads.delete(assignmentExpression);
+                this.openAssignmentsWithReads.delete(assignmentExpression);
+            }
+
+            exitAwaitOrYield(node, surroundingFunction) {
+                return [...this.openAssignmentsWithReads]
+                    .filter(assignment => !isLocalVariableWithoutEscape(assignment.left, surroundingFunction))
+                    .forEach(assignment => {
+                        if (!alreadyReportedAssignments.has(assignment)) {
+                            reportAssignment(assignment);
+                            alreadyReportedAssignments.add(assignment);
+                        }
+                    });
+            }
+
+            exitIdentifierOrMemberExpression(node) {
+                [...this.openAssignmentsWithoutReads]
+                    .filter(assignment => (
+                        assignment.left !== node &&
+                        assignment.left.type === node.type &&
+                        astUtils.equalTokens(assignment.left, node, sourceCode)
+                    ))
+                    .forEach(assignment => {
+                        this.openAssignmentsWithoutReads.delete(assignment);
+                        this.openAssignmentsWithReads.add(assignment);
+                    });
+            }
+        }
+
         /**
          * If the control flow graph of a function enters an assignment expression, then does the
          * both of the following steps in order (possibly with other steps in between) before exiting the
@@ -135,54 +195,51 @@ module.exports = {
             codePathSegment,
             surroundingFunction,
             {
-                seenSegments = new Set(),
-                openAssignmentsWithoutReads = new Set(),
-                openAssignmentsWithReads = new Set()
+                stateBySegmentStart = new WeakMap(),
+                stateBySegmentEnd = new WeakMap()
             } = {}
         ) {
-            if (seenSegments.has(codePathSegment)) {
-
-                // An AssignmentExpression can't contain loops, so it's not necessary to reenter them with new state.
-                return;
+            if (!stateBySegmentStart.has(codePathSegment)) {
+                stateBySegmentStart.set(codePathSegment, new AssignmentTrackerState());
             }
 
+            const currentState = stateBySegmentStart.get(codePathSegment).copy();
+
             expressionsByCodePathSegment.get(codePathSegment).forEach(({ entering, node }) => {
                 if (node.type === "AssignmentExpression") {
                     if (entering) {
-                        (node.operator === "=" ? openAssignmentsWithoutReads : openAssignmentsWithReads).add(node);
+                        currentState.enterAssignment(node);
                     } else {
-                        openAssignmentsWithoutReads.delete(node);
-                        openAssignmentsWithReads.delete(node);
+                        currentState.exitAssignment(node);
                     }
                 } else if (!entering && (node.type === "AwaitExpression" || node.type === "YieldExpression")) {
-                    [...openAssignmentsWithReads]
-                        .filter(assignment => !isLocalVariableWithoutEscape(assignment.left, surroundingFunction))
-                        .forEach(reportAssignment);
-
-                    openAssignmentsWithReads.clear();
+                    currentState.exitAwaitOrYield(node, surroundingFunction);
                 } else if (!entering && (node.type === "Identifier" || node.type === "MemberExpression")) {
-                    [...openAssignmentsWithoutReads]
-                        .filter(assignment => (
-                            assignment.left !== node &&
-                            assignment.left.type === node.type &&
-                            astUtils.equalTokens(assignment.left, node, sourceCode)
-                        ))
-                        .forEach(assignment => {
-                            openAssignmentsWithoutReads.delete(assignment);
-                            openAssignmentsWithReads.add(assignment);
-                        });
+                    currentState.exitIdentifierOrMemberExpression(node);
                 }
             });
 
+            stateBySegmentEnd.set(codePathSegment, currentState);
+
             codePathSegment.nextSegments.forEach(nextSegment => {
+                if (stateBySegmentStart.has(nextSegment)) {
+                    if (!stateBySegmentStart.get(nextSegment).merge(currentState)) {
+
+                        /*
+                         * This segment has already been processed with the given set of inputs;
+                         * no need to do it again. After no new state is available to process
+                         * for any control flow segment in the graph, the analysis reaches a fixpoint and
+                         * traversal stops.
+                         */
+                        return;
+                    }
+                } else {
+                    stateBySegmentStart.set(nextSegment, currentState.copy());
+                }
                 findOutdatedReads(
                     nextSegment,
                     surroundingFunction,
-                    {
-                        seenSegments: new Set(seenSegments).add(codePathSegment),
-                        openAssignmentsWithoutReads: new Set(openAssignmentsWithoutReads),
-                        openAssignmentsWithReads: new Set(openAssignmentsWithReads)
-                    }
+                    { stateBySegmentStart, stateBySegmentEnd }
                 );
             });
         }


Test patch:
diff --git a/tests/lib/rules/one-var.js b/tests/lib/rules/one-var.js
index 1f6626ad8..b628f512a 100644
--- a/tests/lib/rules/one-var.js
+++ b/tests/lib/rules/one-var.js
@@ -263,6 +263,13 @@ ruleTester.run("one-var", rule, {
             options: ["consecutive"],
             parserOptions: { ecmaVersion: 6 }
         },
+
+        // https://github.com/eslint/eslint/issues/10784
+        {
+            code: "const foo = require('foo'); const bar = 'bar';",
+            options: [{ const: "consecutive", separateRequires: true }],
+            parserOptions: { ecmaVersion: 6 }
+        },
         {
             code: "var a = 0, b = 1; var c, d;",
             options: [{ initialized: "consecutive", uninitialized: "always" }]
diff --git a/tests/lib/rules/require-atomic-updates.js b/tests/lib/rules/require-atomic-updates.js
index eabd52149..412835777 100644
--- a/tests/lib/rules/require-atomic-updates.js
+++ b/tests/lib/rules/require-atomic-updates.js
@@ -51,7 +51,64 @@ ruleTester.run("require-atomic-updates", rule, {
         "let foo; function* x() { foo = bar + foo; }",
         "async function x() { let foo; bar(() => baz += 1); foo += await amount; }",
         "let foo; async function x() { foo = condition ? foo : await bar; }",
-        "async function x() { let foo; bar(() => { let foo; blah(foo); }); foo += await result; }"
+        "async function x() { let foo; bar(() => { let foo; blah(foo); }); foo += await result; }",
+        "let foo; async function x() { foo = foo + 1; await bar; }",
+
+
+        /*
+         * Ensure rule doesn't take exponential time in the number of branches
+         * (see https://github.com/eslint/eslint/issues/10893)
+         */
+        `
+            async function foo() {
+                if (1);
+                if (2);
+                if (3);
+                if (4);
+                if (5);
+                if (6);
+                if (7);
+                if (8);
+                if (9);
+                if (10);
+                if (11);
+                if (12);
+                if (13);
+                if (14);
+                if (15);
+                if (16);
+                if (17);
+                if (18);
+                if (19);
+                if (20);
+            }
+        `,
+        `
+            async function foo() {
+                return [
+                    1 ? a : b,
+                    2 ? a : b,
+                    3 ? a : b,
+                    4 ? a : b,
+                    5 ? a : b,
+                    6 ? a : b,
+                    7 ? a : b,
+                    8 ? a : b,
+                    9 ? a : b,
+                    10 ? a : b,
+                    11 ? a : b,
+                    12 ? a : b,
+                    13 ? a : b,
+                    14 ? a : b,
+                    15 ? a : b,
+                    16 ? a : b,
+                    17 ? a : b,
+                    18 ? a : b,
+                    19 ? a : b,
+                    20 ? a : b
+                ];
+            }
+        `
     ],
 
     invalid: [
@@ -59,6 +116,10 @@ ruleTester.run("require-atomic-updates", rule, {
             code: "let foo; async function x() { foo += await amount; }",
             errors: [{ messageId: "nonAtomicUpdate", data: { value: "foo" } }]
         },
+        {
+            code: "if (1); let foo; async function x() { foo += await amount; }",
+            errors: [{ messageId: "nonAtomicUpdate", data: { value: "foo" } }]
+        },
         {
             code: "let foo; async function x() { while (condition) { foo += await amount; } }",
             errors: [VARIABLE_ERROR]
@@ -138,6 +199,14 @@ ruleTester.run("require-atomic-updates", rule, {
         {
             code: "async function x() { foo += await bar; }",
             errors: [VARIABLE_ERROR]
+        },
+        {
+            code: "let foo = 0; async function x() { foo = (a ? b : foo) + await bar; if (baz); }",
+            errors: [VARIABLE_ERROR]
+        },
+        {
+            code: "let foo = 0; async function x() { foo = (a ? b ? c ? d ? foo : e : f : g : h) + await bar; if (baz); }",
+            errors: [VARIABLE_ERROR]
         }
     ]
 });