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).
74 lines
2.7 KiB
Python
74 lines
2.7 KiB
Python
#!/usr/bin/env python3
|
|
# UNDF: UNDF-2026-000001276 (playwright-0001)
|
|
#
|
|
# CWE-407: Algorithmic Complexity
|
|
#
|
|
# Defect:
|
|
# playwright-0001: roleUtils.ts getExplicitAriaRole / allowsNameFromContent
|
|
# / hasGlobalAriaAttribute call Array.includes on 20-70
|
|
# element constant arrays per element. For N elements the
|
|
# total cost is O(N*k). ARIA snapshot walks on modern pages
|
|
# hit thousands of elements.
|
|
#
|
|
# Fix:
|
|
# Convert the hot-path constant arrays to Set<string> at module scope; use
|
|
# set.has(role) for O(1) membership lookup. Total cost O(N+k).
|
|
#
|
|
# Complexity gate (from bench/results.txt on this machine):
|
|
# N=10000 elements, k=70 roles: defective=11.5ms, fixed=1.0ms.
|
|
# Fixed must complete in <10ms at N=5000. k-scaling <17.5x.
|
|
|
|
import importlib.util
|
|
import os
|
|
import sys
|
|
import unittest
|
|
|
|
HERE = os.path.dirname(os.path.abspath(__file__))
|
|
BENCH = os.path.join(os.path.dirname(HERE), "bench")
|
|
sys.path.insert(0, BENCH)
|
|
|
|
|
|
def _load(fname):
|
|
path = os.path.join(BENCH, fname)
|
|
spec = importlib.util.spec_from_file_location(fname, path)
|
|
mod = importlib.util.module_from_spec(spec)
|
|
spec.loader.exec_module(mod)
|
|
return mod
|
|
|
|
|
|
_mod = _load("bench-playwright-0001.py")
|
|
|
|
|
|
# ---------------------------------------------------------------------------
|
|
# Correctness: Set.has must return the same truth as Array.includes for every role.
|
|
# ---------------------------------------------------------------------------
|
|
|
|
class TestPlaywright0001Correctness(unittest.TestCase):
|
|
def test_validrole_set_matches_array(self):
|
|
role_set = set(_mod.VALID_ROLES)
|
|
# known-valid roles
|
|
for role in _mod.VALID_ROLES:
|
|
self.assertEqual(role in role_set, role in _mod.VALID_ROLES,
|
|
f"role {role!r} disagreement")
|
|
# known-invalid roles
|
|
for role in ["", "not-a-role", "linkk", "butt0n", "Link"]: # case-sensitive
|
|
self.assertEqual(role in role_set, role in _mod.VALID_ROLES,
|
|
f"role {role!r} disagreement")
|
|
|
|
|
|
class TestPlaywright0001ComplexityGate(unittest.TestCase):
|
|
def test_fixed_wallclock_N5000(self):
|
|
t_s = min(_mod.bench_fixed(5000) for _ in range(3))
|
|
self.assertLess(t_s * 1000, 10.0,
|
|
f"fixed took {t_s*1000:.3f}ms at N=5000, expected <10ms")
|
|
|
|
def test_fixed_scaling_linear(self):
|
|
t_1000 = min(_mod.bench_fixed(1000) for _ in range(3))
|
|
t_5000 = min(_mod.bench_fixed(5000) for _ in range(3))
|
|
ratio = t_5000 / t_1000 if t_1000 > 0 else float("inf")
|
|
self.assertLess(ratio, 17.5,
|
|
f"fixed N=5000/N=1000 ratio {ratio:.2f}x, expected <17.5x (O(N))")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
unittest.main(verbosity=2)
|