SCSS/LESS selector, property, and atrule patterns have O(n^2) polynomial backtracking (masked by a suppressed scslre Move report)

Summary

The SCSS and LESS selector, property, and atrule patterns have polynomial (O(n^2)) backtracking. A small, realistic unterminated-selector input makes Prism.highlight() take seconds, and the growth is quadratic in input length. The reason it has not been caught is that the pattern test explicitly suppresses the scslre report type that flags this exact class.

Reproduce

import { createInstance } from './tests/helper/prism-loader.js';
const scss = await createInstance('scss');

for (const N of [2000, 4000, 8000]) {
  const code = '.' + 'a-b-'.repeat(N); // unterminated selector, no `{`
  const t0 = performance.now();
  scss.highlight(code, 'scss');
  console.log(N, code.length, (performance.now() - t0).toFixed(0) + 'ms');
}

Measured (full highlight() pipeline, Node):

N=2000  len= 8001   309 ms
N=4000  len=16001  1223 ms   (2x length -> ~4x time)
N=8000  len=32001  4916 ms   (2x length -> ~4x time)
N=16000 len=64001  ~24700 ms

Time grows about 4x per input-doubling, which is quadratic. A well-formed input of the same size (.x{a:1;...}) stays linear (about 6 to 12 ms), which isolates the cost to the unterminated-selector backtracking.

Root cause

The SCSS selector pattern (src/languages/scss.js) matches a run of selector characters with a + quantifier and then requires a trailing lookahead:

/(?=\S)[^@;{}()]?(?:[^@;{}()\s]|\s+(?!\s)|#\{\$[-\w]+\})+(?=\s*\{(?:\}|\s|[^}][^:{}]*[:{][^}]))/

On input with no {, the engine matches the whole run, then backtracks the + one character at a time, re-testing the always-failing lookahead at each step (O(n) per start position). The tokenizer runs the pattern forward from every position, so the total is O(n^2). The SCSS property and atrule patterns, and the LESS selector/atrule/property patterns, share the same "quantified run before a required lookahead" idiom and are equally quadratic.

Why CI does not catch it

tests/pattern-tests.js runs scslre, but calls checkPolynomialBacktracking with reportTypes: { 'Move': false }. scslre.analyse(selector) and .analyse(property) for these patterns each return a { type: 'Move', exponential: false } polynomial report, which is exactly the type being suppressed, so the suite stays green despite the live quadratic behavior.

Suggested direction

Re-enabling the Move report in the pattern test is the systemic fix that would surface the whole family, but it will also flag other grammars, so it needs to be paired with repairs. Per pattern, the fix is to remove the retry-per-position backtracking, for example by making the character run possessive (atomic-group emulation such as (?=(RUN))\1) combined with a cheap leading guard so a run that can never satisfy the (?=\s*\{) lookahead fails in O(1). The selector pattern is annotated in-source as one to edit carefully, so the exact rewrite should lean on the language test suite as the oracle.

This is a report only, filed so the maintainers can decide the scope. Not covered by any existing advisory, PR, or issue.

Start with the SCSS patterns in src/languages/scss.js and the related pattern definitions for LESS, then run the reproduction through Prism.highlight(). Read tests/pattern-tests.js, especially its scslre reportTypes configuration, and use the language test suite as the compatibility oracle. Done means the affected patterns avoid quadratic behavior on unterminated selectors, the relevant Move reports are handled, and the tests pass.