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)
86 lines
2.8 KiB
Markdown
86 lines
2.8 KiB
Markdown
# UNDF: UNDF-2026-000000674
|
||
# UNDF: (pending)
|
||
# cpython-0003: turtle.__methodDict — O(2^D) diamond base traversal
|
||
|
||
## CWE-407 — Algorithmic Complexity: O(2^D) diamond mixin/base traversal
|
||
|
||
| Field | Value |
|
||
|-------|-------|
|
||
| ID | cpython-0003 |
|
||
| Severity | MEDIUM |
|
||
| Ecosystem | cpython |
|
||
| Package | turtle |
|
||
| File | `Lib/turtle.py` |
|
||
| Lines | 286–293 |
|
||
| Complexity | O(2^D) on diamond inheritance hierarchies |
|
||
| Hot path | Called at module import time via `__forwardmethods(ScrolledCanvas, TK.Canvas, '_canvas')` |
|
||
|
||
## Defect
|
||
|
||
```python
|
||
# BEFORE (DEFECT) — O(2^D): no visited guard, unconditional recursion into __bases__
|
||
def __methodDict(cls, _dict):
|
||
"""helper function for Scrolled Canvas"""
|
||
baseList = list(cls.__bases__)
|
||
baseList.reverse()
|
||
for _super in baseList:
|
||
__methodDict(_super, _dict) # unconditional — diamond re-traversal
|
||
for key, value in cls.__dict__.items():
|
||
if type(value) == types.FunctionType:
|
||
_dict[key] = value
|
||
```
|
||
|
||
Called at module import time (line 426):
|
||
```python
|
||
__forwardmethods(ScrolledCanvas, TK.Canvas, '_canvas')
|
||
```
|
||
|
||
`__forwardmethods` calls `__methodDict(toClass, _dict_1)` where `toClass` is `TK.Canvas`.
|
||
If `TK.Canvas` participates in a diamond MRO (common in Tkinter/ttk widget hierarchies),
|
||
the traversal visits shared ancestors exponentially many times.
|
||
|
||
## Fix
|
||
|
||
```python
|
||
# AFTER — O(N): pass visited set to prevent re-traversal of shared ancestors
|
||
def __methodDict(cls, _dict, _visited=None):
|
||
"""helper function for Scrolled Canvas"""
|
||
if _visited is None:
|
||
_visited = set()
|
||
if cls in _visited:
|
||
return
|
||
_visited.add(cls)
|
||
baseList = list(cls.__bases__)
|
||
baseList.reverse()
|
||
for _super in baseList:
|
||
__methodDict(_super, _dict, _visited)
|
||
for key, value in cls.__dict__.items():
|
||
if type(value) == types.FunctionType:
|
||
_dict[key] = value
|
||
```
|
||
|
||
Alternatively, use `cls.__mro__` directly:
|
||
|
||
```python
|
||
# SIMPLER FIX: iterate MRO (linearized, no duplicates)
|
||
def __methodDict(cls, _dict):
|
||
"""helper function for Scrolled Canvas"""
|
||
for klass in reversed(cls.__mro__):
|
||
for key, value in klass.__dict__.items():
|
||
if type(value) == types.FunctionType:
|
||
_dict[key] = value
|
||
```
|
||
|
||
## Speedup
|
||
|
||
| Diamond depth (D) | Nodes visited (before) | Nodes visited (after) | Speedup |
|
||
|------------------|----------------------|----------------------|---------|
|
||
| 5 | 31 | 6 | 5× |
|
||
| 10 | 1,023 | 11 | 93× |
|
||
| 15 | 32,767 | 16 | 2,048× |
|
||
|
||
## Notes
|
||
|
||
This fires at every `import turtle` since `__forwardmethods` is called unconditionally at
|
||
module level. For typical Tkinter class hierarchies the depth is bounded, limiting practical
|
||
impact — but ttk widgets add multiple inheritance layers that could trigger exponential behavior.
|