# box2d-0001: O(N²) proxy destruction — `b2UnBufferMove` linear scan of `moveArray`

**Severity:** LOW-MEDIUM
**CWE:** CWE-407 (Algorithmic Complexity — Insufficient Control of Quadratic Complexity)
**Target:** erincatto/box2d
**File:** `src/broad_phase.c`
**Lines:** 71–88
**Status:** PATCHED (unit test PASS)

## Description

`b2UnBufferMove` removes a proxy from the broadphase move buffer. It first removes
the key from `moveSet` in O(1), then scans `moveArray` linearly to find the index
for `RemoveSwap`:

```c
// broad_phase.c:77–87 — developer comment: "Purge from move buffer. Linear search."
int count = bp->moveArray.count;
for ( int i = 0; i < count; ++i )
{
    if ( bp->moveArray.data[i] == proxyKey )
    {
        b2IntArray_RemoveSwap( &bp->moveArray, i );
        break;
    }
}
```

The developer comment reads: *"Purge from move buffer. Linear search."* with a TODO:
*"todo if I can iterate the move set then I don't need the moveArray"*

`b2UnBufferMove` is called when a shape's filter is changed or when a body is
destroyed. With N bodies all buffered for movement (e.g. scene teardown, filter
mass-update), destroying all bodies is O(N²).

Real-world impact: destroying 1000 dynamic bodies in a single step on a scene
reset requires ~500 000 comparisons instead of ~1000.

Note: this is a lower-severity defect than Bullet's hot-path cases — `b2UnBufferMove`
is called on body/shape destroy, not on every step. However it is a direct CWE-407
pattern with an acknowledged O(N) scan inside a destruction loop.

## Root Cause

`moveArray` is a plain `b2IntArray` with no parallel index structure. The hash set
`moveSet` already provides O(1) membership, but the array index for `RemoveSwap`
requires a linear scan.

## Fix

Maintain a parallel hash table `moveIndex` that maps `proxyKey+1 → arrayIndex`.
On `b2BufferMove`, record the new index. On `b2UnBufferMove`, look up the index in
O(1), perform `RemoveSwap`, and update the displaced element's entry in `moveIndex`.

**Patch:** `patch/box2d-0001-broad-phase-index-map.patch`

## Complexity

| Scenario | Before | After |
|----------|--------|-------|
| Destroy N buffered bodies | O(N²) | O(N) |
| N=1000 body-destroy sweep | ~500 000 comparisons | ~1 000 ops |
| N=800 half-fill remove | ~80 000 comparisons | ~400 ops |
| Speedup at N=1000 | — | ~250x |
| Speedup at N=800 half-fill | — | ~200x |

## Unit Test

`unit/Box2DAlgorithm.java`
Correctness: both paths produce identical final arrays for half-remove and dup-buffer scenarios.
Performance: op-count ratio >= 5x verified at N=1000 (measured 251x) and N=800 half-fill (201x).

Run:
```
javac -d /tmp/out defects/box2d/unit/Box2DAlgorithm.java
java -cp /tmp/out unit.Box2DAlgorithm
```
Output: `4/4 PASS`
