no-cycle, next.js에서 사이클 0개 발견 (캐시가 말하는 다른 허위)

Source: Dev.to

우리는 import-next/no-cycle을 eslint-plugin-import/no-cycle 및 oxlint의 Rust 포트와 함께 next.js(131K 스타, 14,556 소스 파일)에서 벤치마크했습니다. 두 ESLint 플러그인은 0개의 사이클을 발견했고, oxlint은 17개의 사이클을 발견했습니다.
우리는 그 합의를 믿었습니다. 그 뒤에 같은 레포지토리의 33파일 서브셋(packages/next/src/client/components/router-reducer/**)에 우리 규칙을 테스트했더니 바로 5개 이상의 사이클을 찾았습니다.
같은 규칙, 같은 설정, 같은 파일. 범위만 달랐을 뿐인데 결과가 달랐습니다.

버그는 캐시 레이어 60줄 깊숙이 있었으며, 넓은 범위에서 침묵을 반환한 이유를 설명합니다.

모든 사이클 탐지 알고리즘은 다음과 같은 형태를 가집니다:

1. 린트 스코프에 있는 각 파일 F에 대해
2. 그 파일의 import 그래프를 깊이 제한 DFS로 탐색
3. DFS가 F로 돌아오면 → 사이클 발견
4. 그렇지 않으면 → F는 비순환이며, 다음 번을 위해 기억

4단계가 캐시가 효율을 발휘하는 지점입니다. 파일이 N개이고 평균 그래프 깊이가 D라면, 순수 사이클 탐지는 O(N²·D) 입니다. “비순환임을 알고 있는” 캐시가 있으면 재방문은 O(1) 이 됩니다. 실제 코드베이스에서는 캐시 적중률이 70% 이상이며, 캐시가 없으면 규칙이 CI에서 실행되기엔 너무 느려집니다.

캐시 구조는 다음과 같습니다:

interface FileSystemCache {
  // ...
  nonCyclicFiles: Set<string>; // 사이클에 포함되지 않는 것으로 알려진 파일들
}

그리고 사용 위치는 다음과 같습니다:

function dfs(file: string, depth: number, visited: Set<string>) {
  if (file === sourceFile) {
    allCycles.push([...pathStack, file]);
    return;
  }
  if (depth >= maxDepth) return; // = maxDepth, 사이클을 찾지 못한 채 탐색을 마친 것처럼 반환합니다.
                                 // 호출자는 “모든 것을 탐색했지만 아무것도 못 찾았다”와
                                 // “깊이 10에서 포기했다”를 구분할 수 없습니다.
}

즉, 깊이 12에 사이클이 존재하고 maxDepth=10이라면:

• 깊이 10에서 DFS가 잘려 나갑니다.
• allCycles.length === 0
• cache.nonCyclicFiles.add(targetFile) → 잘못해서 비순환으로 표시됩니다.

이후 그 파일을 통과하는 어떤 DFS도 if (cache.nonCyclicFiles.has(file)) return; 때문에 바로 종료됩니다. 이 “중독”은 연쇄적으로 퍼져, 같은 SCC 하위 트리의 모든 파일이 연관성에 의해 비순환으로 표시됩니다.

작은 린트 스코프에서는 이 연쇄 효과가 눈에 띄지 않습니다—잘못된 캐시 항목을 가릴 파일이 충분히 없기 때문이죠. 하지만 14K 파일 규모에서는 초기 한 번의 “놓친 후 캐시”가 전체 클러스터를 무효화합니다.

다음은 이를 입증한 테스트입니다. 같은 규칙, 같은 설정, --no-cache 플래그(ESLint가 실행 간에 캐시를 사용하지 않음—하지만 프로세스 내 캐시는 여전히 활성화)로 실행했습니다:

# 넓은 스코프: 2,363 파일, packages/ 전체 포함
$ eslint --config flagship.config.mjs 'packages/**/*.{ts,tsx,js}'
# 0 import-next/no-cycle 결과

# 좁은 스코프: 33 파일, router-reducer 디렉터리만
$ eslint --config flagship.config.mjs 'packages/next/src/client/components/router-reducer/**/*.ts'
# 5+ import-next/no-cycle 결과

좁은 실행은 사이클을 찾고, 넓은 실행은 새 프로세스와 새 캐시로 시작하지만, ESLint가 파일을 어떤 순서로 읽든 2,363 파일을 처리하면서 nonCyclicFiles 캐시를 채워갑니다. 사이클에 속한 파일에 도달했을 때는 이미 잘못된 비순환 표시가 되어버린 것이죠.

oxlint는 별도의 프로세스와 구현을 사용하므로 우리의 캐시와 공유되지 않으며, 자체 ModuleGraphVisitorBuilder를 이용해 17개의 사이클을 찾았습니다.

해결 방법

DFS가 잘렸는지 추적하고, 잘린 실행은 캐시하지 않도록 합니다:

let depthLimitHit = false;

function dfs(file: string, depth: number, visited: Set<string>) {
  if (file === sourceFile) {
    allCycles.push([...pathStack, file]);
    return;
  }
  if (depth >= maxDepth) {
    depthLimitHit = true; // <-- 잘림을 기록
    return;
  }
  // ... 나머지는 그대로
}

dfs(targetFile, 1, new Set());

// DFS가 **완전히** 끝났고 사이클을 찾지 못했을 때만 비순환으로 캐시
if (allCycles.length === 0 && !depthLimitHit) {
  cache.nonCyclicFiles.add(targetFile);
}

다섯 줄만 수정하면 됩니다. next.js에 다시 실행해 보면: 0 → 245개의 고유 파일이 사이클에 포함, 914개의 고유 (파일, 라인) 쌍이 발견됩니다. 이제 넓은 스코프와 좁은 스코프의 결과가 일치합니다.

eslint-plugin-import는 다른 방식을 사용합니다. 오래된 no-cycle 규칙은 근본적으로 다른 접근법을 취합니다:

// from eslint-plugin-import/src/rules/no-cycle.js:73
const scc = options.disableScc
  ? {}
  : StronglyConnectedComponentsBuilder.get(myPath, context);

// ...

// 서로 다른 SCC에 있으면 순환 의존성이 있을 수 없습니다.
const hasDependencyCycle =
  options.disableScc || scc[myPath] === scc[imported.path];
if (!hasDependencyCycle) return;

이들은 린트 실행당 한 번 강하게 연결된 컴포넌트(SCC) 그래프를 만든 뒤, 파일별 사이클 검사는 O(1) 로 “두 파일이 같은 SCC에 있는가?”를 확인합니다. SCC 그래프 자체는 Tarjan 알고리즘을 사용해 O(V+E) 로 계산됩니다.

이 방식은 깊이 제한 문제를 완전히 회피합니다. SCC는 “사이클 클러스터가 무엇인가?”에 대한 정확한 답을 제공하므로, 잘림, 근사, 캐시 중독이 없습니다. SCC 결과는 모듈 전체에 캐시되고 Program:exit 시에 초기화됩니다.

oxlint는 더 나아가 파싱 단계에서 명시적인 모듈 그래프를 구축하고, 사이클 방문자는 그 그래프를 직접 탐색합니다. 그래프 자체가 이미 구조화돼 있기 때문에 SCC가 필요 없습니다.

두 접근법이 공유하는 핵심은 정확성입니다. 우리의 DFS‑캐시 접근법은 근사적이었고, 캐시가 일부 계산을 절약해 주지만 정확성을 희생했습니다—우리가 실수로 잘못 구현한 바로 그 부분이죠.

진단에서 얻은 교훈 3가지

1. 캐시는 절대 거짓말을 해서는 안 된다. 캐시 항목은 “증명된” 정보만 담아야 하며, “증명되지 않은” 정보를 담아서는 안 됩니다. 우리의 nonCyclicFiles 캐시는 “DFS가 사이클을 찾지 못했다”를 “사이클이 존재하지 않는다”로 오해했습니다. 두 문장은 다릅니다.
2. 배포할 스코프와 동일한 범위에서 알고리즘을 테스트해야 한다. 우리의 단위 테스트는 작은 고정 픽스처 때문에 통과했지만, 깊이 제한이 적용되는 2K+ 파일 규모에서는 버그가 드러났습니다. 실제 프로덕션을 닮은 스트레스 테스트가 필요합니다.
3. 정확한 알고리즘은 캐시가 초래할 수 있는 일련의 버그를 회피한다. SCC 기반 사이클 탐지(eslint-plugin-import)와 모듈 그래프 탐색(oxlint)은 깊이 제한과 캐시 상호작용을 설계 단계부터 배제합니다. 우리는 DFS 접근법을 유지하고 싶지만, 증명되지 않은 “깊이 제한 + 캐시” 조합은 버그가 발생하기 쉬운 패턴이라는 점을 인식하고, 증분 분석이 그만한 가치가 있는지 재평가해야 합니다.

수정은 packages/eslint-devkit/src/resolver/dependency-analysis.ts에 적용되었습니다. 버그를 드러낸 벤치는 benchmarks/suites/ilb-flagship입니다. 이 벤치는 세 가지 규칙 버그 중 하나를 잡아냈으며, 관련 글은 다음과 같습니다:

• What ground truth caught that unit tests missed (smoke‑gate 부분)
• When entropy isn’t enough (vercel/ai에서 807개의 잘못된 자격 증명 발견)

저는 Ofri Peretz이며, Interlace ESLint 생태계(ESLint와 Oxlint에서 동작하는 JavaScript 정적 분석 카탈로그)를 구축하고 있습니다.

🔗 [Portfolio & live metrics]

📦 [eslint-plugin-import-next on npm]

🐙 GitHub: ofri-peretz/eslint

📈 Live impact dashboard

---

Ofri Peretz

*IC5/M2 Leader @ Snappy US. Revenue API와 AI‑ready ESLint 플러그인 구축. 분산 팀, 확장 가능한 인프라, 장인