no-cycle hangs since v2.23.0

[alumni]

With both v2.23.0 and v2.23.1, running eslint on the entire project hangs. Also, it will make vscode eslint plugin hang as well when saving a file (with fix on save enabled).

.eslintrc:

{
  "parser": "@typescript-eslint/parser",
  "parserOptions": {
    "project": "tsconfig.json"
  },
  "rules": {
    "import/no-cycle": ["error", { "ignoreExternal": true, "maxDepth": 7 }]
  },
  "settings": {
    "import/parsers": {
      "@typescript-eslint/parser": [".ts", ".tsx"]
    },
    "import/resolver": {
      "typescript": {
        "project": "tsconfig.json"
      }
    }
  }
}

tsconfig.json:

{
    "compilerOptions": {
        "paths": {
            "@common": ["src/app/common"],
        }
    }
}

[ljharb]

I suspect this might be due to #2077, but I'll leave this open pending confirmation that it's still an issue with v0.23.2 (not yet released).

Either way, does the issue still occur with no-cycle disabled?

[alumni]

Either way, does the issue still occur with no-cycle disabled?

It's fine with no-cycle disabled. We had it anyway disabled in the pre-commit hook to speed things up.

In v2.32.2 eslint --rule 'import/no-cycle: 0' will finish in a reasonable amount of time (without cache <1min), but simply running eslint will not finish even after 10min.

[ljharb]

Does it hang running on the CLI, or only in vscode?

[alumni]

As mentioned above, both the eslint cli and the vscode extension hang. What I noticed:

• eslint cli hangs when run for the entire project
• eslint cli doesn't hang when no-cycle is disabled
• vscode doesn't hang when a single file is opened (might be a bit slower than before though, not sure if it felt faster before because of caching)
• vscode hangs when a file is saved and fix on save is enabled

[SRachamim]

This is a critical issue. Can we please fix or revert?

[ljharb]

Does this still occur with v2.23.4?

I’d love to fix it, but without a repro repo, it’s very difficult to debug.

[alumni]

Haven't checked 2.23.4 yet, but the issue was still present in 2.23.3.

Later edit: 2.23.4 is also affected.

[ezpuzz]

Also having issue. Eslint hangs after printing warnings and errors. Mine is caused by import/order rule

[nicolashenry]

It seems that on one of my project the import/no-cycle rule takes around 30 minutes to run with 2.23.4 (if I keep only "import/no-cycle": ["warn", { "ignoreExternal": true }]). It was really faster before on 2.22.1, around 3 minutes to run (note that it was already the slowest rule in my configuration).

[SRachamim]

Does this still occur with v2.23.4?

I’d love to fix it, but without a repro repo, it’s very difficult to debug.

Yes. I can't publish my repo, and can't really reproduce it outside my repo. But it works well on 2.22.1 and below. We're actually stuck on this version.

[alumni]

Possibly related to #1408.

Running eslint --debug would output for each file:

eslintrc:ignore-pattern Check {
    filePath: '<ROOT>\\<PATH>\\<FILE>',
    dot: false,
    relativePath: '<PATH>/<FILE>',
    result: false
} +6s
eslint:file-enumerator Yield: <FILE> +6s
eslintrc:cascading-config-array-factory Load config files for <ROOT>\<PATH>. +6s     
eslintrc:cascading-config-array-factory Cache hit: <ROOT>\<PATH>. +0ms
eslint:cli-engine Lint <ROOT>\<PATH>\<FILE> +6s
eslint:linter Linting code for <ROOT>\<PATH>\<FILE> (pass 1) +5ms 
eslint:linter Verify +0ms
eslint:linter With ConfigArray: <ROOT>\<PATH>\<FILE> +0ms

And after a long pause:

eslint:linter Generating fixed text for <ROOT>\<PATH>\<FILE> (pass 1) +7s
eslint:source-code-fixer Applying fixes +7s
eslint:source-code-fixer shouldFix parameter was false, not attempting fixes +0ms

[walkerburgin]

We recently tried to upgrade a large codebase from v2.21.2 to 2.24.2 and saw our lint time jump from ~30 seconds to ~14 minutes.

After profiling, it looks like almost all of the time is being spent here:

And if I change our config from this:

"import/no-cycle": [
    "error",
    {
        ignoreExternal: true,
        maxDepth: 2,
    },
],

to this:

"import/no-cycle": [
    "error",
    {
        ignoreExternal: false,
        maxDepth: 2,
    },
],

Short circuiting the call to resolve() here, the performance improves significantly.

We similarly can't publish the codebase, but I'd be happy to test out any proposed changes and report back.

[ljharb]

@walkerburgin thanks, that's very helpful. is there any chance you could confirm on your codebase what the value of name and context.getPhysicalFilename() are at the time resolve is called there? In particular, I'm wondering if there's an excessive number of repeated calls, such that there'd be a performance win from memoizing that result.

[walkerburgin]

@ljharb I logged this out to the console and then counted duplicates in the output:

console.log("" + name + "@" + context.getPhysicalFilename());

Here were the top 10 counts (I dropped the context file names):

    184 lodash-es@...
    149 lodash-es@...
    135 lodash-es@...
    117 lodash-es@...
    115 reselect@...
    103 lodash-es@...
     98 lodash-es@...
     87 lodash-es@...
     83 lodash-es@...
     82 react@...

There were 384,783 unique calls, the max count was 184, and the median was 1.

If I drop the context file path and just log out the name I get 6,103 unique calls, a max count of 8,741, and a median count of 32.

  8741 lodash-es
   4859 reselect
   4695 redoodle

[ljharb]

I suspect the filename is required, because of the potential for repeated dependencies, but that does suggest that memoizing based on both would provide some improvement.

[styu]

any update here? In trying to upgrade to ESLint 8 internally, it looks like the first version of this plugin that supports ESLint 8 is 2.23.0, but because of this issue we are unable to upgrade.

[ljharb]

@styu no, there's no update, or it'd be posted on the issue, like everywhere on github.

I'd be happy to review a PR that included the memoization mentioned here.

[alumni]

@styu if you need to update eslint quickly, you can disable the no-cycle rule, upgrade the import plugin if you're using other rules (there were some breaking changes with the import order for me) and use external tools instead. I was actually using madge for cycle detection before replacing it with no-cycle and now I switched to dependency-cruiser (2x-3x slower than madge but I think I had other issues with madge).

[ljharb]

@alumni if there's a tool like madge that could replace our ExportMap, and do it faster - or even just be used in no-cycle - i'd consider a PR adding that as well.

[alumni]

@ljharb madge is using dependency-tree, which does its own memoization (the visited property): https://github.com/pahen/madge/blob/aa49a0a94fd966be25141c92c75f97d90ad73dc6/lib/tree.js#L109

I'm not sure things like captureJsDoc would be possible with it. I'm also not sure what would be the effect in case of different configurations (typescript/babel/swc/esbuild/webpack etc.). Maybe the option you suggested initially would be better, to improve the memoization in ExportMap 🤷🏻‍♂️

[Rogdham]

For what it's worth, applying some simple caching (patch below) top of v2.25.4 makes quite a difference. There are probably some unexpected side-effects though.

Timing measured with TIMING=1 yarn eslint ... for the no-cycle rule on a private repo:

• without patch: did not finish in 30min
• with patch: 15s

Note that this patch already improved things a lot on v2.22.1 (57s → 10s).

diff --git a/src/rules/no-cycle.js b/src/rules/no-cycle.js
index e61c3be..d338a79 100644
--- a/src/rules/no-cycle.js
+++ b/src/rules/no-cycle.js
@@ -11,2 +11,5 @@ import docsUrl from '../docsUrl';
 
+const traversed = new Set();
 // todo: cache cycles / deep relationships for faster repeat evaluation
@@ -77,3 +80,2 @@ module.exports = {
       const untraversed = [{ mget: () => imported, route:[] }];
-      const traversed = new Set();
       function detectCycle({ mget, route }) {

[ljharb]

@Rogdham hm, interesting. That makes sense, and seems like a good change, but it might break editor/eslintd integrations that sometimes do long-running eslint runs.

[Rogdham]

Yes I agree. If for example in later runs, the traversed is not reset so no cycle will be detected on modified files.

But at the same times, the time improvements show that adding caching to avoid scanning the same files again and again is a good optimisation. Maybe this means that performing cycle checks at the rule level is not the good place to do it in eslint (where rules seems to be made to work on a file independently of others), but I am not familiar with eslint enough to offer a better solution.

In any case, this discussion may be better suited for an other ticket, I only wanted to mention something that seemed to solve the current issue (although creating other problems) to help people that know better with making a proper fix.

[ljharb]

Post-install patches or forks aren’t a solution, so if the change works, it’s worth trying to upstream it. Would you be willing to make a PR?

[Rogdham]

After some thinking, I don't feel confident enough to make a PR, I don't know the codebase at all and this is no simple issue.

Here are some thoughts for the next person that works on it:

• To avoid visiting the same files again and again, some caching must be put in place;
• My patch above may have a false negative in the following case: (assume A>B, B>C, C>B imports)
  1. Visit A (so visit B and C), no error since no cycle going back to A
  2. Visit B (fast skip since already visited) ◀️ false negative
  3. Visit C (fast skip since already visited) ◀️ false negative
• Maybe look what is done on rule import/no-unused-modules in the case unusedExports, some code may be reused/factored from it

---

And again, maybe an eslint rule is not the best place to do the no-cycle check as I explained in my last comment. But I'm not familiar with eslint internals enough to tell.

Best of luck!

[DHedgecock]

I'm wondering if there's an excessive number of repeated calls, such that there'd be a performance win from memoizing that result.

Thanks for the tips @walkerburgin and @ljharb - This matches exactly what I found doing some digging in a medium sized repo of ~2k modules. Saw total lint times cut from 5m to 2m 15s by. Opened #2612

[soryy708]

Here's an idea for how to make import/no-cycle faster:
#2937

[soryy708]

An optimization to no-cycle was released in v 2.30.0, so try that

[ljharb]

Closing; please file a new issue if you're still seeing perf issues in v2.30+.

[alumni]

I can confirm it no longer hangs. 🎉

Note: Adding the rule increases the runtime of eslint from 7s to 47s. This might not be related to the "no-cycle" rule in particular though, as I've noticed in the past a similar increase when enabling just the "namespace" rule or just "no-duplicates".

[ljharb]

that’s still not bad - I’ve seen a large codebase take 20 minutes to lint, but reduced it to 2 with jest-eslint-runner - but if your TIMING output implicates a rule (and disabling that rule doesn’t just shift the slowness to another rule), please file an issue.