# 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.