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