Repository: un-ts/eslint-plugin-import-x
Pull request #118 (2024-07-23 02:14:34)

revert(#111): remove scc
Reverts un-ts/eslint-plugin-import-x#111

See also #113 

The introduction of SCC causes extra overhead that overcomes the early return it introduced.

-----

Instead of doing SCC, I am implementing the `no-cycle-next` rule using the graph. It won't be backward compatible with the current rule `no-cycle`. The current `no-cycle` rule will become `no-cycle-legacy` in the next major version.

changeset-bot[bot]: ###  ⚠️  No Changeset found

Latest commit: abb28cbc514be71d196bb3cb1d3799a4d1580b24

Merging this PR will not cause a version bump for any packages. If these changes should not result in a new version, you're good to go. **If these changes should result in a version bump, you need to add a changeset.**

<details><summary>This PR includes no changesets</summary>

  When changesets are added to this PR, you'll see the packages that this PR includes changesets for and the associated semver types

</details>

[Click here to learn what changesets are, and how to add one](https://github.com/changesets/changesets/blob/main/docs/adding-a-changeset.md).

[Click here if you're a maintainer who wants to add a changeset to this PR](https://github.com/un-ts/eslint-plugin-import-x/new/revert-111-perf-no-cycle?filename=.changeset/fifty-dodos-greet.md&value=---%0A%22eslint-plugin-import-x%22%3A%20patch%0A---%0A%0Arevert(%23111)%3A%20remove%20scc%0A)


codesandbox-ci[bot]: This pull request is automatically built and testable in [CodeSandbox](https://codesandbox.io).

  To see build info of the built libraries, click [here](https://ci.codesandbox.io/status/un-ts/eslint-plugin-import-x/pr/118/builds/525156) or the icon next to each commit SHA.

Patch:
diff --git a/.changeset/hungry-clocks-pretend.md b/.changeset/hungry-clocks-pretend.md
new file mode 100644
index 00000000..f1cd3a04
--- /dev/null
+++ b/.changeset/hungry-clocks-pretend.md
@@ -0,0 +1,7 @@
+---
+"eslint-plugin-import-x": patch
+---
+
+Reverts #111. The introduction of SCC causes extra overhead that overcomes the early return it introduced.
+
+A new `no-cycle-next` rule is being implemented using the graph. It won't be backward compatible with the current rule `no-cycle`. The current `no-cycle` rule will become `no-cycle-legacy` in the next major version.
diff --git a/package.json b/package.json
index 6f6cb97f..14c4d8a6 100644
--- a/package.json
+++ b/package.json
@@ -48,7 +48,6 @@
     "eslint": "^8.56.0 || ^9.0.0-0"
   },
   "dependencies": {
-    "@rtsao/scc": "^1.1.0",
     "@typescript-eslint/utils": "^7.4.0",
     "debug": "^4.3.4",
     "doctrine": "^3.0.0",
diff --git a/src/rules/no-cycle.ts b/src/rules/no-cycle.ts
index ef9199f2..8090fe45 100644
--- a/src/rules/no-cycle.ts
+++ b/src/rules/no-cycle.ts
@@ -5,7 +5,6 @@
 import type { DeclarationMetadata, ModuleOptions } from '../utils'
 import {
   ExportMap,
-  StronglyConnectedComponents,
   isExternalModule,
   createRule,
   moduleVisitor,
@@ -89,8 +88,6 @@ export = createRule<[Options?], MessageId>({
           isExternalModule(name, resolve(name, context)!, context)
       : () => false
 
-    const scc = StronglyConnectedComponents.get(filename, context)
-
     return {
       ...moduleVisitor(function checkSourceValue(sourceNode, importer) {
         if (ignoreModule(sourceNode.value)) {
@@ -130,18 +127,6 @@ export = createRule<[Options?], MessageId>({
           return // no-self-import territory
         }
 
-        /* If we're in the same Strongly Connected Component,
-         * Then there exists a path from each node in the SCC to every other node in the SCC,
-         * Then there exists at least one path from them to us and from us to them,
-         * Then we have a cycle between us.
-         */
-        if (scc) {
-          const hasDependencyCycle = scc[filename] === scc[imported.path]
-          if (!hasDependencyCycle) {
-            return
-          }
-        }
-
         const untraversed: Traverser[] = [{ mget: () => imported, route: [] }]
 
         function detectCycle({ mget, route }: Traverser) {
diff --git a/src/utils/export-map.ts b/src/utils/export-map.ts
index 951bbbb8..2153458e 100644
--- a/src/utils/export-map.ts
+++ b/src/utils/export-map.ts
@@ -1094,7 +1094,7 @@ export function recursivePatternCapture(
  * don't hold full context object in memory, just grab what we need.
  * also calculate a cacheKey, where parts of the cacheKey hash are memoized
  */
-export function childContext(
+function childContext(
   path: string,
   context: RuleContext | ChildContext,
 ): ChildContext {
diff --git a/src/utils/index.ts b/src/utils/index.ts
index cbf25f25..6e0b8c98 100644
--- a/src/utils/index.ts
+++ b/src/utils/index.ts
@@ -17,7 +17,6 @@ export * from './pkg-dir'
 export * from './pkg-up'
 export * from './read-pkg-up'
 export * from './resolve'
-export * from './scc'
 export * from './static-require'
 export * from './unambiguous'
 export * from './visit'
diff --git a/src/utils/scc.ts b/src/utils/scc.ts
deleted file mode 100644
index 2d4b7114..00000000
--- a/src/utils/scc.ts
+++ /dev/null
@@ -1,91 +0,0 @@
-import calculateScc from '@rtsao/scc'
-
-import type { ChildContext, RuleContext } from '../types'
-
-import { ExportMap, childContext } from './export-map'
-import { resolve } from './resolve'
-
-const cache = new Map<string, Record<string, number>>()
-
-export const StronglyConnectedComponents = {
-  clearCache() {
-    cache.clear()
-  },
-
-  get(source: string, context: RuleContext) {
-    const path = resolve(source, context)
-    if (path == null) {
-      return null
-    }
-    return StronglyConnectedComponents.for(childContext(path, context))
-  },
-
-  for(context: ChildContext) {
-    const cacheKey = context.cacheKey
-    if (cache.has(cacheKey)) {
-      return cache.get(cacheKey)!
-    }
-    const scc = StronglyConnectedComponents.calculate(context)
-    cache.set(cacheKey, scc)
-    return scc
-  },
-
-  calculate(context: ChildContext) {
-    const exportMap = ExportMap.for(context)
-    const adjacencyList =
-      StronglyConnectedComponents.exportMapToAdjacencyList(exportMap)
-    const calculatedScc = calculateScc(adjacencyList)
-    return StronglyConnectedComponents.calculatedSccToPlainObject(calculatedScc)
-  },
-
-  exportMapToAdjacencyList(initialExportMap: ExportMap | null) {
-    /** for each dep, what are its direct deps */
-    const adjacencyList = new Map<string, Set<string>>()
-    // BFS
-    function visitNode(exportMap: ExportMap | null) {
-      if (!exportMap) {
-        return
-      }
-      for (const [importedPath, v] of exportMap.imports.entries()) {
-        const from = exportMap.path
-        const to = importedPath
-
-        if (!adjacencyList.has(from)) {
-          adjacencyList.set(from, new Set())
-        }
-
-        const set = adjacencyList.get(from)!
-
-        if (set.has(to)) {
-          continue // prevent endless loop
-        }
-        set.add(to)
-        visitNode(v.getter())
-      }
-    }
-    visitNode(initialExportMap)
-    // Fill gaps
-    // eslint-disable-next-line unicorn/no-array-for-each -- Map.forEach, and it is way faster
-    adjacencyList.forEach(values => {
-      // eslint-disable-next-line unicorn/no-array-for-each -- Set.forEach
-      values.forEach(value => {
-        if (!adjacencyList.has(value)) {
-          adjacencyList.set(value, new Set())
-        }
-      })
-    })
-
-    return adjacencyList
-  },
-
-  calculatedSccToPlainObject(sccs: Array<Set<string>>) {
-    /** for each key, its SCC's index */
-    const obj: Record<string, number> = {}
-    for (const [index, scc] of sccs.entries()) {
-      for (const node of scc) {
-        obj[node] = index
-      }
-    }
-    return obj
-  },
-}
diff --git a/yarn.lock b/yarn.lock
index 2a185b9c..760e281b 100644
--- a/yarn.lock
+++ b/yarn.lock
@@ -1886,11 +1886,6 @@
   dependencies:
     "@xml-tools/parser" "^1.0.11"
 
-"@rtsao/scc@^1.1.0":
-  version "1.1.0"
-  resolved "https://registry.yarnpkg.com/@rtsao/scc/-/scc-1.1.0.tgz#927dd2fae9bc3361403ac2c7a00c32ddce9ad7e8"
-  integrity sha512-zt6OdqaDoOnJ1ZYsCYGt9YmWzDXl4vQdKTyJev62gFhRGKdx7mcT54V9KIjg+d2wi9EXsPvAPKe7i7WjfVWB8g==
-
 "@sinclair/typebox@^0.27.8":
   version "0.27.8"
   resolved "https://registry.yarnpkg.com/@sinclair/typebox/-/typebox-0.27.8.tgz#6667fac16c436b5434a387a34dedb013198f6e6e"


Test patch:
diff --git a/test/utils/scc.spec.ts b/test/utils/scc.spec.ts
deleted file mode 100644
index 150575ae..00000000
--- a/test/utils/scc.spec.ts
+++ /dev/null
@@ -1,193 +0,0 @@
-// import sinon from 'sinon';
-import { testContext } from '../utils'
-
-import {
-  StronglyConnectedComponents,
-  ExportMap,
-  childContext as buildChildContext,
-} from 'eslint-plugin-import-x/utils'
-
-function exportMapFixtureBuilder(
-  path: string,
-  imports: ExportMap[],
-): ExportMap {
-  return {
-    path,
-    imports: new Map(
-      imports.map(imp => [
-        imp.path,
-        { getter: () => imp, declarations: new Set() },
-      ]),
-    ),
-  } as ExportMap
-}
-
-describe('Strongly Connected Components Builder', () => {
-  afterEach(() => StronglyConnectedComponents.clearCache())
-
-  describe('When getting an SCC', () => {
-    const source = ''
-    const ruleContext = testContext({})
-    const childContext = buildChildContext(source, ruleContext)
-
-    describe('Given two files', () => {
-      describe("When they don't cycle", () => {
-        it('Should return foreign SCCs', () => {
-          jest
-            .spyOn(ExportMap, 'for')
-            .mockReturnValue(
-              exportMapFixtureBuilder('foo.js', [
-                exportMapFixtureBuilder('bar.js', []),
-              ]),
-            )
-          const actual = StronglyConnectedComponents.for(childContext)
-          expect(actual).toEqual({ 'foo.js': 1, 'bar.js': 0 })
-        })
-      })
-
-      describe.skip('When they do cycle', () => {
-        it('Should return same SCC', () => {
-          jest
-            .spyOn(ExportMap, 'for')
-            .mockReturnValue(
-              exportMapFixtureBuilder('foo.js', [
-                exportMapFixtureBuilder('bar.js', [
-                  exportMapFixtureBuilder('foo.js', []),
-                ]),
-              ]),
-            )
-          const actual = StronglyConnectedComponents.get(source, ruleContext)
-          expect(actual).toEqual({ 'foo.js': 0, 'bar.js': 0 })
-        })
-      })
-    })
-
-    describe('Given three files', () => {
-      describe('When they form a line', () => {
-        describe('When A -> B -> C', () => {
-          it('Should return foreign SCCs', () => {
-            jest
-              .spyOn(ExportMap, 'for')
-              .mockReturnValue(
-                exportMapFixtureBuilder('foo.js', [
-                  exportMapFixtureBuilder('bar.js', [
-                    exportMapFixtureBuilder('buzz.js', []),
-                  ]),
-                ]),
-              )
-            const actual = StronglyConnectedComponents.for(childContext)
-            expect(actual).toEqual({ 'foo.js': 2, 'bar.js': 1, 'buzz.js': 0 })
-          })
-        })
-
-        describe('When A -> B <-> C', () => {
-          it('Should return 2 SCCs, A on its own', () => {
-            jest
-              .spyOn(ExportMap, 'for')
-              .mockReturnValue(
-                exportMapFixtureBuilder('foo.js', [
-                  exportMapFixtureBuilder('bar.js', [
-                    exportMapFixtureBuilder('buzz.js', [
-                      exportMapFixtureBuilder('bar.js', []),
-                    ]),
-                  ]),
-                ]),
-              )
-            const actual = StronglyConnectedComponents.for(childContext)
-            expect(actual).toEqual({ 'foo.js': 1, 'bar.js': 0, 'buzz.js': 0 })
-          })
-        })
-
-        describe('When A <-> B -> C', () => {
-          it('Should return 2 SCCs, C on its own', () => {
-            jest
-              .spyOn(ExportMap, 'for')
-              .mockReturnValue(
-                exportMapFixtureBuilder('foo.js', [
-                  exportMapFixtureBuilder('bar.js', [
-                    exportMapFixtureBuilder('buzz.js', []),
-                    exportMapFixtureBuilder('foo.js', []),
-                  ]),
-                ]),
-              )
-            const actual = StronglyConnectedComponents.for(childContext)
-            expect(actual).toEqual({ 'foo.js': 1, 'bar.js': 1, 'buzz.js': 0 })
-          })
-        })
-
-        describe('When A <-> B <-> C', () => {
-          it('Should return same SCC', () => {
-            jest
-              .spyOn(ExportMap, 'for')
-              .mockReturnValue(
-                exportMapFixtureBuilder('foo.js', [
-                  exportMapFixtureBuilder('bar.js', [
-                    exportMapFixtureBuilder('foo.js', []),
-                    exportMapFixtureBuilder('buzz.js', [
-                      exportMapFixtureBuilder('bar.js', []),
-                    ]),
-                  ]),
-                ]),
-              )
-            const actual = StronglyConnectedComponents.for(childContext)
-            expect(actual).toEqual({ 'foo.js': 0, 'bar.js': 0, 'buzz.js': 0 })
-          })
-        })
-      })
-
-      describe('When they form a loop', () => {
-        it('Should return same SCC', () => {
-          jest
-            .spyOn(ExportMap, 'for')
-            .mockReturnValue(
-              exportMapFixtureBuilder('foo.js', [
-                exportMapFixtureBuilder('bar.js', [
-                  exportMapFixtureBuilder('buzz.js', [
-                    exportMapFixtureBuilder('foo.js', []),
-                  ]),
-                ]),
-              ]),
-            )
-          const actual = StronglyConnectedComponents.for(childContext)
-          expect(actual).toEqual({ 'foo.js': 0, 'bar.js': 0, 'buzz.js': 0 })
-        })
-      })
-
-      describe('When they form a Y', () => {
-        it('Should return 3 distinct SCCs', () => {
-          jest
-            .spyOn(ExportMap, 'for')
-            .mockReturnValue(
-              exportMapFixtureBuilder('foo.js', [
-                exportMapFixtureBuilder('bar.js', []),
-                exportMapFixtureBuilder('buzz.js', []),
-              ]),
-            )
-          const actual = StronglyConnectedComponents.for(childContext)
-          expect(actual).toEqual({ 'foo.js': 2, 'bar.js': 0, 'buzz.js': 1 })
-        })
-      })
-
-      describe('When they form a Mercedes', () => {
-        it('Should return 1 SCC', () => {
-          jest
-            .spyOn(ExportMap, 'for')
-            .mockReturnValue(
-              exportMapFixtureBuilder('foo.js', [
-                exportMapFixtureBuilder('bar.js', [
-                  exportMapFixtureBuilder('foo.js', []),
-                  exportMapFixtureBuilder('buzz.js', []),
-                ]),
-                exportMapFixtureBuilder('buzz.js', [
-                  exportMapFixtureBuilder('foo.js', []),
-                  exportMapFixtureBuilder('bar.js', []),
-                ]),
-              ]),
-            )
-          const actual = StronglyConnectedComponents.for(childContext)
-          expect(actual).toEqual({ 'foo.js': 0, 'bar.js': 0, 'buzz.js': 0 })
-        })
-      })
-    })
-  })
-})