# UNDF: (pending)
# django-0006: migrations.state.flatten_bases — O(2^D) diamond abstract model traversal

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

| Field | Value |
|-------|-------|
| ID | django-0006 |
| Severity | MEDIUM |
| Ecosystem | django |
| Package | django.db.migrations.state |
| File | `django/db/migrations/state.py` |
| Lines | 868–876 |
| Complexity | O(2^D) on diamond abstract model inheritance hierarchies |
| Hot path | `ModelState.from_model()` — called for every model during `makemigrations` and migration state rebuild |

## Defect

```python
# BEFORE (DEFECT) — O(2^D): no visited guard on recursive __bases__ traversal
def flatten_bases(model):
    bases = []
    for base in model.__bases__:
        if hasattr(base, "_meta") and base._meta.abstract:
            bases.extend(flatten_bases(base))   # unconditional recursion
        else:
            bases.append(base)
    return bases

# We can't rely on __mro__ directly because we only want to flatten
# abstract models and not the whole tree. However by recursing on
# __bases__ we may end up with duplicates and ordering issues, we
# therefore discard any duplicates and reorder the bases according
# to their index in the MRO.
flattened_bases = sorted(
    set(flatten_bases(model)), key=lambda x: model.__mro__.index(x)
)
```

The comment itself acknowledges "we may end up with duplicates" — a symptom of the
diamond traversal defect. With a diamond abstract model hierarchy:

```python
class TimestampMixin(models.Model):   # abstract
    class Meta: abstract = True

class AuditMixin(TimestampMixin):     # abstract
    class Meta: abstract = True

class PermissionMixin(TimestampMixin): # abstract
    class Meta: abstract = True

class MyModel(AuditMixin, PermissionMixin):  # concrete
    pass
```

`flatten_bases(MyModel)` visits `TimestampMixin` twice (once via `AuditMixin`, once via
`PermissionMixin`). At depth D, `TimestampMixin` is visited `2^(D-1)` times.

## Fix

```python
# AFTER — O(N): pass visited set to prevent re-traversal of shared abstract ancestors
def flatten_bases(model, _visited=None):
    if _visited is None:
        _visited = set()
    bases = []
    for base in model.__bases__:
        if base in _visited:
            continue
        if hasattr(base, "_meta") and base._meta.abstract:
            _visited.add(base)
            bases.extend(flatten_bases(base, _visited))
        else:
            bases.append(base)
    return bases
```

The `set(...)` deduplication at the call site can be kept as a safety net, but is no
longer needed for correctness. The `sorted(..., key=lambda x: model.__mro__.index(x))`
ordering is unchanged.

## Speedup

| Diamond depth (D) | flatten_bases calls (before) | flatten_bases calls (after) | Speedup |
|------------------|-----------------------------|-----------------------------|---------|
| 3 | 7 | 4 | 1.75× |
| 5 | 31 | 6 | 5× |
| 10 | 1,023 | 11 | 93× |
| 15 | 32,767 | 16 | 2,048× |

## Notes

Django's abstract model mixin pattern is extremely common in large applications — many
projects use `TimestampedModel`, `SoftDeleteModel`, `AuditedModel` mixins that all share
a common abstract base. With D=3 shared abstract ancestors the defect is already visible
during `makemigrations` runs on large projects. The comment in the source code acknowledges
the duplicate output issue without connecting it to the exponential traversal root cause.
