# playwright-0001: roleUtils — O(N×k) ARIA role validation in per-element snapshot

**Target:** microsoft/playwright
**Severity:** MEDIUM-HIGH
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)
**MOAD:** MOAD-0001 (A Sedimentary Defect)
**File:** `packages/injected/src/roleUtils.ts:262-268, 499-500, 51-52, 262-268`
**Language:** TypeScript
**Status:** open

## Description

Playwright injects `roleUtils.ts` into every target page to compute accessible
names and ARIA roles. Several frequently-called helpers use `Array.includes` on
constant arrays holding 70+ role strings. When Playwright snapshots a page's
accessibility tree, `getExplicitAriaRole`, `allowsNameFromContent`, and
`hasGlobalAriaAttribute` run once per element — thousands of times on modern
pages.

Each `Array.includes` call is O(k) where k is the array length. Inside a DOM
traversal of N elements, total cost is O(N×k). On a page with 5000 elements
and the 70-entry `validRoles` array, that's 350,000 string comparisons per
snapshot. Converting the arrays to `Set<string>` drops lookup to O(1),
producing O(N+k).

## Root Cause

```typescript
// roleUtils.ts:262-268
const validRoles: AriaRole[] = ['alert', 'alertdialog', 'application', ...70 items];

function getExplicitAriaRole(element: Element): AriaRole | null {
  const roles = (element.getAttribute('role') || '').split(' ').map(...);
  return roles.find(role => validRoles.includes(role as any)) as AriaRole || null;
}

// roleUtils.ts:499-500 (inside allowsNameFromContent — called per element)
const alwaysAllowsNameFromContent = [
  'button', 'cell', 'checkbox', 'columnheader', ...20 items
].includes(role);
const descendantAllowsNameFromContent = targetDescendant && [
  '', 'caption', 'code', ...30 items
].includes(role);

// roleUtils.ts:51-52 (kGlobalAriaAttributes prohibited-list scan inside
//  hasGlobalAriaAttribute, called per element):
!prohibited?.includes(forRole || '')
```

Each `Array.includes` is O(k). Called per-element across thousands of
elements, cost compounds to O(N×k). The arrays are constant and could be
built once as Sets at module load.

## Fix

Convert hot-path constant arrays to `Set<string>` at module scope, use
`set.has(x)` for O(1) lookup:

```typescript
const validRolesSet = new Set<string>(validRoles);

function getExplicitAriaRole(element: Element): AriaRole | null {
  const roles = (element.getAttribute('role') || '').split(' ').map(...);
  return roles.find(role => validRolesSet.has(role)) as AriaRole || null;
}

const alwaysAllowsNameFromContentSet = new Set([
  'button', 'cell', 'checkbox', ...
]);
const descendantAllowsNameFromContentSet = new Set([...]);

function allowsNameFromContent(role: string, targetDescendant: boolean) {
  return alwaysAllowsNameFromContentSet.has(role) ||
         (targetDescendant && descendantAllowsNameFromContentSet.has(role));
}
```

Set construction runs once at module load. Per-element lookups drop to O(1).

## Severity Note

Runs on every accessibility snapshot, every `getByRole` locator, every ARIA
tree traversal. Per-element cost is microseconds, but pages with 5000+
elements compound quickly. Large enterprise apps (dashboards, CRMs, grid
layouts) commonly exceed this element count. Impact amplifies under
`@playwright/test` parallel runs with `toHaveAccessibleName` assertions.

## Complexity Gate

- N=5000 elements, 70-element role arrays: fixed must complete in <10ms
- k-scaling 5×: time ratio must be <17.5× (O(k) ≈5×, not O(k²) ≈25×)