# UNDF: UNDF-2026-000000673
# UNDF: (pending)
# cpython-0002: pydoc.allmethods — O(2^D) diamond base traversal

## CWE-407 — Algorithmic Complexity: O(2^D) diamond mixin/base traversal

| Field | Value |
|-------|-------|
| ID | cpython-0002 |
| Severity | MEDIUM |
| Ecosystem | cpython |
| Package | pydoc |
| File | `Lib/pydoc.py` |
| Lines | 232–240 |
| Complexity | O(2^D) on diamond inheritance hierarchies |
| Hot path | `pydoc.allmethods(cl)` — collect all methods across inheritance tree |

## Defect

```python
# BEFORE (DEFECT) — O(2^D): no visited guard, unconditional recursion
def allmethods(cl):
    methods = {}
    for key, value in inspect.getmembers(cl, inspect.isroutine):
        methods[key] = 1
    for base in cl.__bases__:
        methods.update(allmethods(base))  # all your base are belong to us
    for key in methods.keys():
        methods[key] = getattr(cl, key)
    return methods
```

With a diamond hierarchy `D → B, C → A` (A shared), `allmethods(D)` recurses into both
`B` and `C`, each of which recurses into `A`, visiting it twice. At depth D the traversal
visits `2^D` nodes instead of the O(D) unique classes.

## Fix

```python
# AFTER — O(N): guard at entry prevents re-visiting shared ancestors
def allmethods(cl, _visited=None):
    if _visited is None:
        _visited = set()
    if cl in _visited:
        return {}
    _visited.add(cl)
    methods = {}
    for key, value in inspect.getmembers(cl, inspect.isroutine):
        methods[key] = 1
    for base in cl.__bases__:
        methods.update(allmethods(base, _visited))
    for key in methods.keys():
        methods[key] = getattr(cl, key)
    return methods
```

Note: `inspect.getmro(cl)` already returns the linearized MRO and could replace the
recursive traversal entirely:

```python
# SIMPLER FIX: use MRO directly (already handles diamond)
def allmethods(cl):
    methods = {}
    for klass in reversed(inspect.getmro(cl)):
        for key, value in inspect.getmembers(klass, inspect.isroutine):
            methods[key] = 1
    for key in methods.keys():
        methods[key] = getattr(cl, key)
    return methods
```

## 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× |
| 20 | 1,048,575 | 21 | 49,932× |

## Notes

`allmethods` is defined in `pydoc.py` but is no longer called from the main doc-rendering
paths (which use `__mro__` directly). However, it remains exported as part of the module's
public API and is available for external callers. The defect is present and latent.