---
id: cpython-0001
repo: cpython
severity: HIGH
status: patched
created: 2026-03-23
---

## Defect

**File:** `Tools/peg_generator/pegen/sccutils.py:73`
**Pattern:** `node in path` where path is a list in DFS cycle detection
**Complexity:** `O(V²)`
**Language:** Python

## Description

The PEG generator's SCC utility performs DFS-based cycle detection and maintains the current DFS path as a Python list. At line 73, the check `node in path` tests whether a node has been visited on the current path, which requires scanning the entire list. Since this check is performed for every edge explored, and the path can be up to V nodes long, the algorithm degrades from O(V+E) to O(V²+VE).

## Fix

**Replace:** `node in path`
**With:** `node in path_set`
**Data structure change:** `path: list → path: list + path_set: set` (maintained in parallel)

## Work required

- [ ] Patch in `defects/cpython/patch/`
- [ ] Unit test — asserts exact operation counts before/after (in `defects/cpython/unit/`)
- [ ] Integration test (in `defects/cpython/integration/`)
- [ ] Benchmark — before/after on V=100,200,400,800 (in `defects/cpython/bench/`)
- [ ] White paper section