Repository: eslint/eslint (js)

Issue:
upgrade 3.19 to 4.3.0 - no-multi-spaces -  incredibly slow
```
Rule                     |  Time (ms) | Relative
:------------------------|-----------:|--------:
no-multi-spaces          | 128895.239 |    98.8%
indent                   |    572.412 |     0.4%
comma-style              |     87.177 |     0.1%
comma-spacing            |     62.077 |     0.0%
no-regex-spaces          |     51.506 |     0.0%
keyword-spacing          |     50.365 |     0.0%
mocha/no-identical-title |     47.103 |     0.0%
no-control-regex         |     42.972 |     0.0%
key-spacing              |     41.282 |     0.0%
no-useless-escape        |     38.029 |     0.0%
```
**Tell us about your environment**

* ESLint Version:*4.3*
* Node Version:*8.1.4*
* npm Version:*5.3.0*

**What parser (default, Babel-ESLint, etc.) are you using?**

**Please show your full configuration:**
```json
{
  "root": true,
  "extends": "eslint:recommended",

  "rules": {

    "curly": ["error", "all"],
    "eqeqeq": "error",
    "no-eq-null": "error",
    "vars-on-top": "error",
    "wrap-iife": ["error", "any"],
    "max-params": ["warn", { "max": 5 }],
    "no-console": "error",
    "no-unused-vars": ["error", {
      "vars": "all",
      "args": "none"
    }],
    "semi": ["error", "always"],


    // Structure

    "block-spacing": ["warn", "always"],
    "brace-style": ["warn", "1tbs", { "allowSingleLine": true }],
    "comma-dangle": ["warn", "only-multiline"],
    "comma-spacing": ["warn", { "before": false, "after": true }],
    "comma-style": ["warn", "last"],
    "dot-location": ["warn", "property"],
    "indent": ["warn", "tab"],
    "key-spacing": ["warn", {
      "beforeColon": false,
      "afterColon": true,
      "mode": "minimum"
    }],
    "keyword-spacing": ["warn", { "before": true, "after": true }],
    "linebreak-style": ["warn", "unix"],
    "quotes": ["warn", "double", "avoid-escape"],
    "space-infix-ops": "warn",
    "space-unary-ops": ["warn", { "words": true, "nonwords": false }],


    // Other whitespace

    "eol-last": ["warn", "unix"],
    "newline-after-var": ["warn", "always"],
    "newline-before-return": "warn",
    "no-mixed-spaces-and-tabs": ["warn", "smart-tabs"],
    "no-multiple-empty-lines": ["warn", { "max": 2 }],
    "no-multi-spaces": ["warn"],
    "no-trailing-spaces": ["warn", { "skipBlankLines": true }],
    "padded-blocks": [0, "never"],
    "space-before-blocks": ["warn", "always"],
    "space-before-function-paren": ["warn", { "anonymous": "always", "named": "never" }],
    "space-in-parens": ["warn", "never"],
    "spaced-comment": ["warn", "always"],


    // Misc

    "valid-jsdoc": ["warn", {
      "prefer": {
        "return": "returns"
      },
      "requireReturn": false,
      "requireReturnDescription": false
    }],

	"mocha/no-exclusive-tests": "error",
	"mocha/no-identical-title": "error"
  },

  "parserOptions": {
	"ecmaVersion": 8,
	"sourceType": "module",
	"ecmaFeatures": {
	  "experimentalObjectRestSpread": true
	}
  },

  "env": {
    "node": true
  },

  "globals" : {
    "Promise": true
  },

  "plugins": [
	"mocha"
  ]
}
```
<details>
<summary>Configuration</summary>

<!-- Paste your configuration below: -->
```js



```

</details>

**What did you do? Please include the actual source code causing the issue.**

<!-- Paste the source code below: -->
```js
eslint src test
```

**What did you expect to happen?**

As with eslint 3.19 completing within few seconds

**What actually happened? Please include the actual, raw output from ESLint.**



Pull request description:
Fix: refactor no-multi-spaces to avoid regex backtracking (fixes #9001)
<!--
    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)**

[x] Bug fix (https://github.com/eslint/eslint/issues/9001)

<!--
    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 refactors the `no-multi-spaces` rule to compare spacing between tokens, rather than matching a regex against the source text. This prevents performance issues resulting from quadratic-time regex matching (https://github.com/eslint/eslint/issues/9001). This also allows the rule to be simpler because by only evaluating spacing between tokens, it no longer needs to specifically exclude spacing in comments.

**Is there anything you'd like reviewers to focus on?**

Nothing in particular

Patch:
diff --git a/lib/rule-context.js b/lib/rule-context.js
index 66987b867..0a2dc188d 100644
--- a/lib/rule-context.js
+++ b/lib/rule-context.js
@@ -20,6 +20,7 @@ const PASSTHROUGHS = [
     "getDeclaredVariables",
     "getFilename",
     "getScope",
+    "getSourceCode",
     "markVariableAsUsed",
 
     // DEPRECATED
@@ -58,7 +59,7 @@ const PASSTHROUGHS = [
  */
 
 //------------------------------------------------------------------------------
-// Rule Definition
+// Module Definition
 //------------------------------------------------------------------------------
 
 /**
@@ -132,13 +133,13 @@ function getFix(descriptor, sourceCode) {
 
 /**
  * Rule context class
- * Acts as an abstraction layer between rules and the main eslint object.
+ * Acts as an abstraction layer between rules and the main linter object.
  */
 class RuleContext {
 
     /**
      * @param {string} ruleId The ID of the rule using this object.
-     * @param {eslint} eslint The eslint object.
+     * @param {Linter} linter The linter object.
      * @param {number} severity The configured severity level of the rule.
      * @param {Array} options The configuration information to be added to the rule.
      * @param {Object} settings The configuration settings passed from the config file.
@@ -147,7 +148,7 @@ class RuleContext {
      * @param {Object} meta The metadata of the rule
      * @param {Object} parserServices The parser services for the rule.
      */
-    constructor(ruleId, eslint, severity, options, settings, parserOptions, parserPath, meta, parserServices) {
+    constructor(ruleId, linter, severity, options, settings, parserOptions, parserPath, meta, parserServices) {
 
         // public.
         this.id = ruleId;
@@ -161,22 +162,14 @@ class RuleContext {
         this.parserServices = Object.freeze(Object.assign({}, parserServices));
 
         // private.
-        this.eslint = eslint;
-        this.severity = severity;
+        this._linter = linter;
+        this._severity = severity;
 
         Object.freeze(this);
     }
 
     /**
-     * Passthrough to eslint.getSourceCode().
-     * @returns {SourceCode} The SourceCode object for the code.
-     */
-    getSourceCode() {
-        return this.eslint.getSourceCode();
-    }
-
-    /**
-     * Passthrough to eslint.report() that automatically assigns the rule ID and severity.
+     * Passthrough to Linter#report() that automatically assigns the rule ID and severity.
      * @param {ASTNode|MessageDescriptor} nodeOrDescriptor The AST node related to the message or a message
      *      descriptor.
      * @param {Object=} location The location of the error.
@@ -192,38 +185,57 @@ class RuleContext {
             const descriptor = nodeOrDescriptor;
             const fix = getFix(descriptor, this.getSourceCode());
 
-            this.eslint.report(
+            if (descriptor.loc) {
+                this._linter.report(
+                    this.id,
+                    this._severity,
+                    descriptor.node,
+                    descriptor.loc,
+                    descriptor.message,
+                    descriptor.data,
+                    fix,
+                    this.meta
+                );
+            } else {
+                this._linter.report(
+                    this.id,
+                    this._severity,
+                    descriptor.node,
+
+                    /* loc not provided */
+                    descriptor.message,
+                    descriptor.data,
+                    fix,
+                    this.meta
+                );
+            }
+
+        } else {
+
+            // old style call
+            this._linter.report(
                 this.id,
-                this.severity,
-                descriptor.node,
-                descriptor.loc || descriptor.node.loc.start,
-                descriptor.message,
-                descriptor.data,
-                fix,
+                this._severity,
+                nodeOrDescriptor,
+                location,
+                message,
+                opts,
                 this.meta
             );
-
-            return;
         }
-
-        // old style call
-        this.eslint.report(
-            this.id,
-            this.severity,
-            nodeOrDescriptor,
-            location,
-            message,
-            opts,
-            this.meta
-        );
     }
 }
 
-// Copy over passthrough methods. All functions will have 5 or fewer parameters.
-PASSTHROUGHS.forEach(function(name) {
-    this[name] = function(a, b, c, d, e) {
-        return this.eslint[name](a, b, c, d, e);
-    };
-}, RuleContext.prototype);
+// Copy over passthrough methods.
+PASSTHROUGHS.forEach(name => {
+    Object.defineProperty(RuleContext.prototype, name, {
+        value() {
+            return this._linter[name].apply(this._linter, arguments);
+        },
+        configurable: true,
+        writable: true,
+        enumerable: false
+    });
+});
 
 module.exports = RuleContext;
diff --git a/lib/rules/no-multi-spaces.js b/lib/rules/no-multi-spaces.js
index fb4e017fd..73e514335 100644
--- a/lib/rules/no-multi-spaces.js
+++ b/lib/rules/no-multi-spaces.js
@@ -44,68 +44,11 @@ module.exports = {
     },
 
     create(context) {
-
-        // the index of the last comment that was checked
-        const sourceCode = context.getSourceCode(),
-            exceptions = { Property: true },
-            options = context.options[0] || {},
-            ignoreEOLComments = options.ignoreEOLComments;
-        let hasExceptions = true,
-            lastCommentIndex = 0;
-
-        if (options && options.exceptions) {
-            Object.keys(options.exceptions).forEach(key => {
-                if (options.exceptions[key]) {
-                    exceptions[key] = true;
-                } else {
-                    delete exceptions[key];
-                }
-            });
-            hasExceptions = Object.keys(exceptions).length > 0;
-        }
-
-        /**
-         * Checks if a given token is the last token of the line or not.
-         * @param {Token} token The token to check.
-         * @returns {boolean} Whether or not a token is at the end of the line it occurs in.
-         * @private
-         */
-        function isLastTokenOfLine(token) {
-            const nextToken = sourceCode.getTokenAfter(token, { includeComments: true });
-
-            // nextToken is null if the comment is the last token in the program.
-            if (!nextToken) {
-                return true;
-            }
-
-            return !astUtils.isTokenOnSameLine(token, nextToken);
-        }
-
-        /**
-         * Determines if a given source index is in a comment or not by checking
-         * the index against the comment range. Since the check goes straight
-         * through the file, once an index is passed a certain comment, we can
-         * go to the next comment to check that.
-         * @param {int} index The source index to check.
-         * @param {ASTNode[]} comments An array of comment nodes.
-         * @returns {boolean} True if the index is within a comment, false if not.
-         * @private
-         */
-        function isIndexInComment(index, comments) {
-            while (lastCommentIndex < comments.length) {
-                const comment = comments[lastCommentIndex];
-
-                if (comment.range[0] < index && index < comment.range[1]) {
-                    return true;
-                } else if (index > comment.range[1]) {
-                    lastCommentIndex++;
-                } else {
-                    break;
-                }
-            }
-
-            return false;
-        }
+        const sourceCode = context.getSourceCode();
+        const options = context.options[0] || {};
+        const ignoreEOLComments = options.ignoreEOLComments;
+        const exceptions = Object.assign({ Property: true }, options.exceptions);
+        const hasExceptions = Object.keys(exceptions).filter(key => exceptions[key]).length > 0;
 
         /**
          * Formats value of given comment token for error message by truncating its length.
@@ -121,70 +64,62 @@ module.exports = {
             return valueLines.length === 1 && value.length <= 12 ? value : formattedValue;
         }
 
-        /**
-         * Creates a fix function that removes the multiple spaces between the two tokens
-         * @param {Token} leftToken left token
-         * @param {Token} rightToken right token
-         * @returns {Function} fix function
-         * @private
-         */
-        function createFix(leftToken, rightToken) {
-            return function(fixer) {
-                return fixer.replaceTextRange([leftToken.range[1], rightToken.range[0]], " ");
-            };
-        }
-
         //--------------------------------------------------------------------------
         // Public
         //--------------------------------------------------------------------------
 
         return {
             Program() {
+                sourceCode.tokensAndComments.forEach((leftToken, leftIndex, tokensAndComments) => {
+                    if (leftIndex === tokensAndComments.length - 1) {
+                        return;
+                    }
+                    const rightToken = tokensAndComments[leftIndex + 1];
 
-                const source = sourceCode.getText(),
-                    allComments = sourceCode.getAllComments(),
-                    pattern = /[^\s].*? {2,}/g;
-                let parent;
-
-                while (pattern.test(source)) {
-
-                    // do not flag anything inside of comments
-                    if (!isIndexInComment(pattern.lastIndex, allComments)) {
-
-                        const token = sourceCode.getTokenByRangeStart(pattern.lastIndex, { includeComments: true });
-
-                        if (token) {
-                            if (ignoreEOLComments && astUtils.isCommentToken(token) && isLastTokenOfLine(token)) {
-                                return;
-                            }
+                    // Ignore tokens that have less than 2 spaces between them or are on different lines
+                    if (leftToken.range[1] + 2 > rightToken.range[0] || leftToken.loc.end.line < rightToken.loc.start.line) {
+                        return;
+                    }
 
-                            const previousToken = sourceCode.getTokenBefore(token, { includeComments: true });
+                    // Ignore comments that are the last token on their line if `ignoreEOLComments` is active.
+                    if (
+                        ignoreEOLComments &&
+                        astUtils.isCommentToken(rightToken) &&
+                        (
+                            leftIndex === tokensAndComments.length - 2 ||
+                            rightToken.loc.end.line < tokensAndComments[leftIndex + 2].loc.start.line
+                        )
+                    ) {
+                        return;
+                    }
 
-                            if (hasExceptions) {
-                                parent = sourceCode.getNodeByRangeIndex(pattern.lastIndex - 1);
-                            }
+                    // Ignore tokens that are in a node in the "exceptions" object
+                    if (hasExceptions) {
+                        const parentNode = sourceCode.getNodeByRangeIndex(rightToken.range[0] - 1);
 
-                            if (!parent || !exceptions[parent.type]) {
-                                let value = token.value;
-
-                                if (token.type === "Block") {
-                                    value = `/*${formatReportedCommentValue(token)}*/`;
-                                } else if (token.type === "Line") {
-                                    value = `//${formatReportedCommentValue(token)}`;
-                                }
-
-                                context.report({
-                                    node: token,
-                                    loc: token.loc.start,
-                                    message: "Multiple spaces found before '{{value}}'.",
-                                    data: { value },
-                                    fix: createFix(previousToken, token)
-                                });
-                            }
+                        if (parentNode && exceptions[parentNode.type]) {
+                            return;
                         }
+                    }
 
+                    let displayValue;
+
+                    if (rightToken.type === "Block") {
+                        displayValue = `/*${formatReportedCommentValue(rightToken)}*/`;
+                    } else if (rightToken.type === "Line") {
+                        displayValue = `//${formatReportedCommentValue(rightToken)}`;
+                    } else {
+                        displayValue = rightToken.value;
                     }
-                }
+
+                    context.report({
+                        node: rightToken,
+                        loc: rightToken.loc.start,
+                        message: "Multiple spaces found before '{{displayValue}}'.",
+                        data: { displayValue },
+                        fix: fixer => fixer.replaceTextRange([leftToken.range[1], rightToken.range[0]], " ")
+                    });
+                });
             }
         };
 


Test patch:
diff --git a/tests/lib/cli-engine.js b/tests/lib/cli-engine.js
index 7529d8edf..104118888 100644
--- a/tests/lib/cli-engine.js
+++ b/tests/lib/cli-engine.js
@@ -355,6 +355,8 @@ describe("CLIEngine", () => {
                                 message: "'foo' is not defined.",
                                 line: 1,
                                 column: 11,
+                                endLine: 1,
+                                endColumn: 14,
                                 nodeType: "Identifier",
                                 source: "var bar = foo"
                             }
@@ -1413,6 +1415,8 @@ describe("CLIEngine", () => {
                                 {
                                     column: 18,
                                     line: 1,
+                                    endColumn: 21,
+                                    endLine: 1,
                                     message: "'foo' is not defined.",
                                     nodeType: "Identifier",
                                     ruleId: "no-undef",
diff --git a/tests/lib/linter.js b/tests/lib/linter.js
index d9244bde1..672088c71 100644
--- a/tests/lib/linter.js
+++ b/tests/lib/linter.js
@@ -1105,7 +1105,7 @@ describe("Linter", () => {
             assert.strictEqual(messages[0].endColumn, 2);
         });
 
-        it("should not have 'endLine' and 'endColumn' when 'loc' property doe not have 'end' property.", () => {
+        it("should not have 'endLine' and 'endColumn' when 'loc' property does not have 'end' property.", () => {
             linter.on("Program", node => {
                 linter.report(
                     "test-rule",
@@ -1122,6 +1122,13 @@ describe("Linter", () => {
             assert.strictEqual(messages[0].endColumn, void 0);
         });
 
+        it("should infer an 'endLine' and 'endColumn' property when using the object-based context.report API", () => {
+            const messages = linter.verify("foo", { rules: { "no-undef": "error" } });
+
+            assert.strictEqual(messages.length, 1);
+            assert.strictEqual(messages[0].endLine, 1);
+            assert.strictEqual(messages[0].endColumn, 4);
+        });
     });
 
     describe("when evaluating code", () => {
diff --git a/tests/lib/rules/no-multi-spaces.js b/tests/lib/rules/no-multi-spaces.js
index b983430a4..d3dcf61f5 100644
--- a/tests/lib/rules/no-multi-spaces.js
+++ b/tests/lib/rules/no-multi-spaces.js
@@ -98,7 +98,10 @@ ruleTester.run("no-multi-spaces", rule, {
 
         "foo\n\f  bar",
         "foo\n\u2003  bar",
-        "foo\n \f  bar"
+        "foo\n \f  bar",
+
+        // https://github.com/eslint/eslint/issues/9001
+        "a".repeat(2e5)
     ],
 
     invalid: [