russell@unturf.com
9a0253e724
selenium-0001: SessionCapabilitiesMutator list.contains O(NxM) -> LinkedHashSet O(N+M). Grid Node session mutation hot path. Bench: 192x at N=M=1000. selenium-0002: ChromiumOptions merge helpers consolidate four list.contains loops behind addArgumentsUnique/addEncodedExtensionsUnique. Bench: 254x at N=M=1000. playwright-0001: roleUtils validRoles / allowsNameFromContent Array.includes on 20-70 element constant arrays per element. Converted to Set<string> at module load. Bench: 11x at N=10000 elements. webdriverio-0001: xpath-conditions extractOrConditions orMatches.find + values.includes per regex match -> Map<attr, Set<values>>. Bench: 6x at K=V=60 in the 'mobileSelectorPerformanceOptimizer'. Each defect ships: ticket, patch with complexity-gate header, Python benchmark + correctness test, Makefile, outreach brief. All 16 tests pass. UNDF IDs: 1276 (playwright), 1277 (selenium-0001), 1288 (selenium-0002), 1289 (webdriverio).
91 lines
3.4 KiB
Markdown
91 lines
3.4 KiB
Markdown
# 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×)
|