russell@unturf.com
130e4fb159
New defects from diamond O(2^D) sweep: - cpython-0002/0003/0004: pydoc.allmethods, turtle.__methodDict, idlelib.rpc._getmethods - micronaut-0005/0006/0007: populateTypeHierarchy, populateTypeArgumentsForInterfaces, SuperclassAwareTypeVisitor - quarkus-0004/0005: HierarchyDiscovery.discoverTypes, ConfigMappingUtils.collectInterfacesRec - weld-0004/0005: HierarchyDiscovery.discoverTypes, Services.identifyServiceInterfaces - rails-0019: Digestor#dependency_digest Array#include? O(N²) - spring-0007: AnnotationsScanner.processClassHierarchy O(2^D) - django-0007: migrations.state.flatten_bases O(2^D) - typescript-0005: hasBaseType O(2^D) - hibernate-validator-0003: ClassHierarchyHelper.getImplementedInterfaces O(2^D) - swift-0001: QualifiedLookupRequest::evaluate protocol superclass O(2^D)
77 lines
2.5 KiB
Markdown
77 lines
2.5 KiB
Markdown
# UNDF: UNDF-2026-000000675
|
||
# UNDF: (pending)
|
||
# cpython-0004: idlelib.rpc._getmethods — O(2^D) diamond base traversal
|
||
|
||
## CWE-407 — Algorithmic Complexity: O(2^D) diamond mixin/base traversal
|
||
|
||
| Field | Value |
|
||
|-------|-------|
|
||
| ID | cpython-0004 |
|
||
| Severity | MEDIUM |
|
||
| Ecosystem | cpython |
|
||
| Package | idlelib.rpc |
|
||
| File | `Lib/idlelib/rpc.py` |
|
||
| Lines | 581–590 |
|
||
| Complexity | O(2^D) on diamond inheritance hierarchies |
|
||
| Hot path | Triggered when IDLE debugger calls `__methods__` on a remote object (every debug session inspect) |
|
||
|
||
## Defect
|
||
|
||
```python
|
||
# BEFORE (DEFECT) — O(2^D): no visited guard, unconditional recursion into __bases__
|
||
def _getmethods(obj, methods):
|
||
# Helper to get a list of methods from an object
|
||
# Adds names to dictionary argument 'methods'
|
||
for name in dir(obj):
|
||
attr = getattr(obj, name)
|
||
if callable(attr):
|
||
methods[name] = 1
|
||
if isinstance(obj, type):
|
||
for super in obj.__bases__:
|
||
_getmethods(super, methods) # unconditional — diamond re-traversal
|
||
```
|
||
|
||
Called via IDLE RPC when someone requests `__methods__` (line 179–181):
|
||
```python
|
||
if methodname == "__methods__":
|
||
methods = {}
|
||
_getmethods(obj, methods)
|
||
```
|
||
|
||
With a diamond hierarchy, each shared ancestor is visited 2^D times instead of once.
|
||
`dir(obj)` is called on each visit, making the actual cost O(2^D × M) where M is the
|
||
number of methods per class.
|
||
|
||
## Fix
|
||
|
||
```python
|
||
# AFTER — O(N): pass visited set to prevent re-traversal of shared ancestors
|
||
def _getmethods(obj, methods, _visited=None):
|
||
if _visited is None:
|
||
_visited = set()
|
||
if obj in _visited:
|
||
return
|
||
_visited.add(obj)
|
||
for name in dir(obj):
|
||
attr = getattr(obj, name)
|
||
if callable(attr):
|
||
methods[name] = 1
|
||
if isinstance(obj, type):
|
||
for super in obj.__bases__:
|
||
_getmethods(super, methods, _visited)
|
||
```
|
||
|
||
## Speedup
|
||
|
||
| Diamond depth (D) | `dir()` calls (before) | `dir()` calls (after) | Speedup |
|
||
|------------------|----------------------|----------------------|---------|
|
||
| 5 | 31 | 6 | 5× |
|
||
| 10 | 1,023 | 11 | 93× |
|
||
| 15 | 32,767 | 16 | 2,048× |
|
||
|
||
## Notes
|
||
|
||
`dir()` is an expensive call (it consults `__dict__`, `__dir__`, and all descriptor slots).
|
||
In a deep diamond hierarchy under the IDLE debugger, inspecting a complex object could
|
||
cause the IDLE UI to stall for seconds. The `methods` dict deduplication only prevents
|
||
incorrect output — it does not prevent the exponential traversal cost.
|