# SPIRV-CROSS-0002: O(n²) access-chain expression tracking — `add_implied_read_expression` linear scan

**Severity:** MEDIUM
**CWE:** CWE-407 (Algorithmic Complexity — Insufficient Control of Quadratic Complexity)
**Target:** KhronosGroup/SPIRV-Cross
**File:** `spirv_cross.cpp` lines 2605–2616, called from `spirv_glsl.cpp` line 12826–12830
**Status:** PATCHED (unit test PASS)

## Description

`Compiler::add_implied_read_expression` deduplicates entries in the
`implied_read_expressions` vector by scanning it linearly:

```cpp
// spirv_cross.cpp:2607
auto itr = find(begin(e.implied_read_expressions), end(e.implied_read_expressions), ID(source));
if (itr == end(e.implied_read_expressions))
    e.implied_read_expressions.push_back(source);
```

This function is called inside the access-chain index loop:

```cpp
// spirv_glsl.cpp:12826
for (uint32_t i = 2; i < length; i++)
{
    inherit_expression_dependencies(ops[1], ops[i]);
    add_implied_read_expression(expr, ops[i]);   // O(i) each call
}
```

For an access chain of depth D the loop body runs D times, and the i-th call
scans i existing entries — total comparisons: 0+1+2+…+(D-1) = O(D²).

A struct-of-array-of-struct access chain in a typical UBO can reach depth 6–10;
a `gl_PerVertex` chain in a geometry shader can reach depth 8.  With heavy
shader generation (e.g., game engines emitting 1 000+ access chains per draw
call) the cost is non-trivial.

## Root Cause

`implied_read_expressions` uses `SmallVector<ID>` as a deduplicated list.  Since
IDs are plain integers, an `unordered_set<uint32_t>` is the natural replacement.

## Fix

Replace the `SmallVector<ID> implied_read_expressions` field in `SPIRExpression`
and `SPIRAccessChain` with `std::unordered_set<uint32_t>`.  The `add_implied_read_expression`
function becomes an unconditional `insert` (set semantics handle dedup).  All
read sites iterate the set instead of the vector (unchanged iteration semantics).

**Patch:** `patch/spirv-cross-0002.patch`

## Complexity

| Depth D | Before | After |
|---------|--------|-------|
| D index levels | O(D²) | O(D) |
| D=8 | 28 comparisons | 8 ops |
| D=32 | 496 comparisons | 32 ops |

## Unit Test

`unit/SpirvcrossImpliedReadAlgorithm.java`

Run: `javac unit/SpirvcrossImpliedReadAlgorithm.java && java -cp unit SpirvcrossImpliedReadAlgorithm`
