# wasmtime-0002: AdapterOptions ancestors Vec<RuntimeComponentInstanceIndex> O(n) scan per trampoline

**Severity:** MEDIUM
**CWE:** CWE-407 (Algorithmic Complexity — linear membership test in compilation path)
**Speedup:** >10x at D=50 nesting depth (deeply nested components)
**Target:** wasmtime (bytecodealliance/wasmtime)
**Files:**
- `crates/environ/src/fact.rs:130` — `ancestors: Vec<RuntimeComponentInstanceIndex>`
- `crates/environ/src/fact/trampoline.rs:121` — `adapter.lower.ancestors.contains(&adapter.lift.instance)`
- `crates/environ/src/fact/trampoline.rs:122` — `adapter.lift.ancestors.contains(&adapter.lower.instance)`
- `crates/environ/src/component/translate/adapt.rs:171` — same field in DFG

## Description

When generating component model adapter trampolines, wasmtime checks for
illegal re-entrancy by testing whether one adapter's instance appears in the
ancestor chain of the other adapter:

```rust
if adapter.lift.instance == adapter.lower.instance
    || adapter.lower.ancestors.contains(&adapter.lift.instance)
    || adapter.lift.ancestors.contains(&adapter.lower.instance)
```

Both `ancestors` fields are `Vec<RuntimeComponentInstanceIndex>`, populated as
the full chain of instantiating component instances (depth-first order).

For a component tree of nesting depth D, the ancestor chain has length D.
The `contains()` call performs a linear scan through all D ancestors.

This runs once per adapter trampoline during compilation. With A adapters in a
deeply nested component (D levels, A adapter functions), total work is
**O(A * D)** in the worst case.

In practice Wasm component ecosystems are developing rapidly — large component
graphs with many adapters and deep nesting are expected in production
(e.g. WASI Preview 2 composites, wasm-compose pipelines).

## Root Cause

The ancestor list is built as a `Vec` at `inline.rs:1583-1588` from a frame
stack. Since element identity (not ordering) is what matters for the
re-entrancy check, this should be a `HashSet` or a sorted `Vec` with binary
search.

## Patch

See `patch/wasmtime-0002.patch`

## Complexity Before

`ancestors.contains()` with D nesting depth: **O(D)** per check
A adapters × 2 checks each: **O(A * D)**

## Complexity After

With `IndexSet<RuntimeComponentInstanceIndex>` (or `HashSet`):
**O(1)** per contains check → **O(A)** total

## Reproduction

```
cd defects/wasmtime/unit && javac -d . *.java && java -ea unit.AncestorsLinearScanTest
```
