russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
1.1 KiB
1.1 KiB
| id | repo | severity | status | created |
|---|---|---|---|---|
| cpython-0001 | cpython | HIGH | patched | 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