java-topology/docs/tickets/playwright-0001-roleutils-validroles-array-includes.md

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

// 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:

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×)