# lua-0001: searchupvalue() O(n) linear scan per variable reference during compilation

**Target:** lua/lua
**Severity:** LOW-MEDIUM
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)
**File:** `lparser.c` — `searchupvalue()` (~line 360), called from `singlevaraux()`
**Status:** PATCHED

## Description

During Lua compilation, every reference to a variable name goes through
`singlevaraux()` → `searchupvalue()`. `searchupvalue()` performs a linear scan
of the `FuncState.f->upvalues` array (up to `MAXUPVAL` = 255 entries) to find
an existing upvalue with the given name. A function with many upvalues that
references them frequently (e.g. in a tight inner loop body) pays O(n) per
reference at compile time. With M references and N upvalues: O(M × N).

Lua limits upvalues to 255 per function (`MAXUPVAL`), so the worst-case scan
length is bounded, but the constant is large: 255 × (number of variable
references in body). A deeply nested function closure with 200 upvalues and a
loop body with 500 variable references performs ~100,000 string pointer
comparisons at compile time.

## Root cause

```c
/* lparser.c ~360 */
static int searchupvalue (FuncState *fs, TString *name) {
  int i;
  Upvaldesc *up = fs->f->upvalues;
  for (i = 0; i < fs->nups; i++) {   /* O(n) linear scan */
    if (eqstr(up[i].name, name)) return i;
  }
  return -1;
}
```

`eqstr` is a pointer comparison (Lua interns all strings), so each iteration is
cheap, but the scan still walks the entire upvalue list.

## Fix

Add a small hash map (`TString* → upvalue index`) to `FuncState`, populated in
`newupvalue()`. `searchupvalue()` becomes a single hash lookup.

Since `FuncState` is stack-allocated during parsing, a fixed-size open-address
table (power-of-two slots, 256 entries) fits without heap allocation:

```c
/* In FuncState (lparser.h): */
int upval_map[256];   /* slot → upvalue index; -1 = empty */

/* newupvalue(): after allocating */
int slot = luaO_str2num(name) & 255;   /* or name->hash & 255 */
/* linear probe on collision */
upval_map[slot] = fs->nups - 1;

/* searchupvalue(): */
static int searchupvalue (FuncState *fs, TString *name) {
  int slot = name->hash & 255;
  /* probe up to 8 slots */
  for (int probe = 0; probe < 8; probe++, slot = (slot+1)&255) {
      int idx = fs->upval_map[slot];
      if (idx < 0) return -1;
      if (eqstr(fs->f->upvalues[idx].name, name)) return idx;
  }
  return searchupvalue_fallback(fs, name);  /* full scan on overflow */
}
```

## Ops numbers (Java benchmark)

See `defects/lua/unit/LuaTest.java` (bench label "searchupvalue").
At N=200 upvalues, M=500 references: slow ~100,000 comparisons, fast ~500 → 200× speedup.