russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
32 lines
1.1 KiB
Markdown
32 lines
1.1 KiB
Markdown
---
|
|
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
|