Skip to content

Commit d8158d9

Browse files
committed
Read the last token of a selector that ends in a nested pseudo-class (#182)
Before testing candidates, collect() asks reOptimizer for the last simple token of a selector and uses it to fetch the candidates by tag, class or id. The parenthesized part of that pattern is '\x28[^\x29]+(?:\x29|$)', which stops at the first ')', so a final compound holding a nested functional pseudo-class does not match at all — and a selector the optimizer cannot read is answered by walking every element in the context. 'div:not(:nth-of-type(2n))' therefore tests every element in the document instead of the divs, and since ':not()' evaluates its argument through s.match() per element, each of those elements resolves nth-of-type. On a 6300-element page that is 6344 resolutions building 3911 sibling caches over 196312 steps, for a selector whose subject is a div. The parenthesized part now tolerates two levels of nesting, which reaches ':not(:not(:not(span)))'. Deeper than that falls back to the unoptimized scan, as before. Both the old and new patterns stay linear on unbalanced input: 3200 unclosed parentheses match in 0.02ms. div:not(:nth-of-type(2n)) 45.62ms -> 134.92us 338x div:not(:nth-child(3)) 9.42ms -> 123.94us 76x div:is(.example):not(:where(.x)) 2.65ms -> 39.45us 67x div:not(.x) 27.93us -> 27.75us - Results are unchanged; the four above agree with the native engine. References: - Spec: https://drafts.csswg.org/css-syntax/#consume-simple-block — why a parenthesized part has to tolerate nesting - Spec: https://drafts.csswg.org/selectors-4/#matches — the functional pseudo-classes that put parentheses inside a compound
1 parent c9d878d commit d8158d9

5 files changed

Lines changed: 103 additions & 34 deletions

File tree

‎docs/api.md‎

Lines changed: 31 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -11,21 +11,21 @@ Query contexts default to the factory document when omitted. `closest()`, `first
1111

1212
| Method | Result |
1313
| --- | --- |
14-
| [`byClass(cls, context)`](../src/nwsapi.mts#L2972) | Returns elements with the class name. |
15-
| [`byId(id, context)`](../src/nwsapi.mts#L2970) | Returns elements with the ID. Duplicate IDs are allowed by default. |
16-
| [`byTag(tag, context)`](../src/nwsapi.mts#L2971) | Returns elements with the tag name. Use `*` for all elements. |
17-
| [`closest(selectors, element, callback)`](../src/nwsapi.mts#L2978) | Returns the nearest match, starting with the element, or `null`. |
18-
| [`compile(selector, mode, callback)`](../src/nwsapi.mts#L2980) | Compiles a selector into a resolver function. This is an advanced API. |
19-
| [`configure(option, clear)`](../src/nwsapi.mts#L2981) | Reads or changes options. Pass `true` as the second argument to clear compiled selectors. |
20-
| [`emit(message, proto)`](../src/nwsapi.mts#L2983) | Reports an error using the configured error policy. |
21-
| [`first(selectors, context, callback)`](../src/nwsapi.mts#L2974) | Returns the first matching descendant, or `null`. |
22-
| [`install(all)`](../src/nwsapi.mts#L2989) | Replaces native selector methods. Pass `true` to also replace collection methods. |
23-
| [`match(selectors, element, callback)`](../src/nwsapi.mts#L2975) | Returns whether the element matches. |
24-
| [`registerCombinator(combinator, resolver)`](../src/nwsapi.mts#L2996) | Adds a relationship between elements using trusted resolver code. |
25-
| [`registerOperator(operator, resolver)`](../src/nwsapi.mts#L3021) | Adds an attribute operator using a resolver with `p1`, `p2`, and `p3` fields. |
26-
| [`registerSelector(name, rexp, func)`](../src/nwsapi.mts#L3043) | Adds a selector pattern and a compiler callback that returns `source` and `status`. |
27-
| [`select(selectors, context, callback)`](../src/nwsapi.mts#L2976) | Returns an array of matching descendants, or an empty array. |
28-
| [`uninstall()`](../src/nwsapi.mts#L2990) | Restores the native methods saved by `install()`. |
14+
| [`byClass(cls, context)`](../src/nwsapi.mts#L2982) | Returns elements with the class name. |
15+
| [`byId(id, context)`](../src/nwsapi.mts#L2980) | Returns elements with the ID. Duplicate IDs are allowed by default. |
16+
| [`byTag(tag, context)`](../src/nwsapi.mts#L2981) | Returns elements with the tag name. Use `*` for all elements. |
17+
| [`closest(selectors, element, callback)`](../src/nwsapi.mts#L2988) | Returns the nearest match, starting with the element, or `null`. |
18+
| [`compile(selector, mode, callback)`](../src/nwsapi.mts#L2990) | Compiles a selector into a resolver function. This is an advanced API. |
19+
| [`configure(option, clear)`](../src/nwsapi.mts#L2991) | Reads or changes options. Pass `true` as the second argument to clear compiled selectors. |
20+
| [`emit(message, proto)`](../src/nwsapi.mts#L2993) | Reports an error using the configured error policy. |
21+
| [`first(selectors, context, callback)`](../src/nwsapi.mts#L2984) | Returns the first matching descendant, or `null`. |
22+
| [`install(all)`](../src/nwsapi.mts#L2999) | Replaces native selector methods. Pass `true` to also replace collection methods. |
23+
| [`match(selectors, element, callback)`](../src/nwsapi.mts#L2985) | Returns whether the element matches. |
24+
| [`registerCombinator(combinator, resolver)`](../src/nwsapi.mts#L3006) | Adds a relationship between elements using trusted resolver code. |
25+
| [`registerOperator(operator, resolver)`](../src/nwsapi.mts#L3031) | Adds an attribute operator using a resolver with `p1`, `p2`, and `p3` fields. |
26+
| [`registerSelector(name, rexp, func)`](../src/nwsapi.mts#L3053) | Adds a selector pattern and a compiler callback that returns `source` and `status`. |
27+
| [`select(selectors, context, callback)`](../src/nwsapi.mts#L2986) | Returns an array of matching descendants, or an empty array. |
28+
| [`uninstall()`](../src/nwsapi.mts#L3000) | Restores the native methods saved by `install()`. |
2929

3030
<details>
3131
<summary>Configuration</summary>
@@ -60,22 +60,22 @@ These exports support extensions and debugging. Prefer query methods and `config
6060

6161
| Member | Purpose |
6262
| --- | --- |
63-
| [`CFG`](../src/nwsapi.mts#L2958) | Contains the compiler syntax settings. |
64-
| [`Config`](../src/nwsapi.mts#L2984) | Contains the active options. Use `configure()` to change them. |
65-
| [`M_BODY`](../src/nwsapi.mts#L2961) | Contains the matching resolver body template. |
66-
| [`M_TEST`](../src/nwsapi.mts#L2965) | Contains the matching resolver test template. |
67-
| [`matchLambdas`](../src/nwsapi.mts#L2950) | Caches compiled matching functions, not DOM results. |
68-
| [`matchResolvers`](../src/nwsapi.mts#L2953) | Caches matching plans, not DOM results. |
69-
| [`N_BODY`](../src/nwsapi.mts#L2962) | Exposes the matching resolver body template. |
70-
| [`N_TEST`](../src/nwsapi.mts#L2966) | Contains the alternate resolver test template. |
71-
| [`Operators`](../src/nwsapi.mts#L2992) | Contains registered attribute operators. |
72-
| [`S_BODY`](../src/nwsapi.mts#L2960) | Contains the selection resolver body template. |
73-
| [`S_TEST`](../src/nwsapi.mts#L2964) | Contains the selection resolver test template. |
74-
| [`selectLambdas`](../src/nwsapi.mts#L2951) | Caches compiled selection functions, not DOM results. |
75-
| [`Selectors`](../src/nwsapi.mts#L2993) | Contains registered selector extensions. |
76-
| [`selectResolvers`](../src/nwsapi.mts#L2954) | Caches selection plans, not DOM results. |
77-
| [`Snapshot`](../src/nwsapi.mts#L2985) | Contains the document state and helpers used by compiled selectors. |
78-
| [`Version`](../src/nwsapi.mts#L2987) | Contains the engine version string. |
63+
| [`CFG`](../src/nwsapi.mts#L2968) | Contains the compiler syntax settings. |
64+
| [`Config`](../src/nwsapi.mts#L2994) | Contains the active options. Use `configure()` to change them. |
65+
| [`M_BODY`](../src/nwsapi.mts#L2971) | Contains the matching resolver body template. |
66+
| [`M_TEST`](../src/nwsapi.mts#L2975) | Contains the matching resolver test template. |
67+
| [`matchLambdas`](../src/nwsapi.mts#L2960) | Caches compiled matching functions, not DOM results. |
68+
| [`matchResolvers`](../src/nwsapi.mts#L2963) | Caches matching plans, not DOM results. |
69+
| [`N_BODY`](../src/nwsapi.mts#L2972) | Exposes the matching resolver body template. |
70+
| [`N_TEST`](../src/nwsapi.mts#L2976) | Contains the alternate resolver test template. |
71+
| [`Operators`](../src/nwsapi.mts#L3002) | Contains registered attribute operators. |
72+
| [`S_BODY`](../src/nwsapi.mts#L2970) | Contains the selection resolver body template. |
73+
| [`S_TEST`](../src/nwsapi.mts#L2974) | Contains the selection resolver test template. |
74+
| [`selectLambdas`](../src/nwsapi.mts#L2961) | Caches compiled selection functions, not DOM results. |
75+
| [`Selectors`](../src/nwsapi.mts#L3003) | Contains registered selector extensions. |
76+
| [`selectResolvers`](../src/nwsapi.mts#L2964) | Caches selection plans, not DOM results. |
77+
| [`Snapshot`](../src/nwsapi.mts#L2995) | Contains the document state and helpers used by compiled selectors. |
78+
| [`Version`](../src/nwsapi.mts#L2997) | Contains the engine version string. |
7979

8080
</details>
8181

‎package.json‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -120,6 +120,7 @@
120120
"upstream:verify": "node scripts/run.mts scripts/git-partial-submodule.mts verify",
121121
"test:attributes": "node scripts/run.mts node_modules/vitest/vitest.mjs run --config .config/vitest.config.mts test/attribute-parse-error.test.mts",
122122
"test:attributes:browser": "NWSAPI_BROWSER=1 node scripts/run.mts node_modules/vitest/vitest.mjs run --config .config/vitest.config.mts test/attribute-strings-browser.test.mts",
123-
"test:browser": "NWSAPI_BROWSER=1 node scripts/run.mts node_modules/vitest/vitest.mjs run --config .config/vitest.config.mts"
123+
"test:browser": "NWSAPI_BROWSER=1 node scripts/run.mts node_modules/vitest/vitest.mjs run --config .config/vitest.config.mts",
124+
"test:optimizer": "node scripts/run.mts node_modules/vitest/vitest.mjs run --config .config/vitest.config.mts test/optimizer-nesting.test.mts"
124125
}
125126
}

‎src/nwsapi.mts‎

Lines changed: 12 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1212,7 +1212,8 @@
12121212
// pairs, coloring breakage and other editors highlightning problems.
12131213
//
12141214

1215-
var // non-ascii chars
1215+
var parenthesized,
1216+
// non-ascii chars
12161217
noascii = '[^\\x00-\\x9f]',
12171218
// unicode chars
12181219
unicode = '\\\\[0-9a-fA-F]{1,6}',
@@ -1348,6 +1349,15 @@
13481349
// deepest localName in selector strings and then
13491350
// use it to retrieve all possible matching nodes
13501351
// that will be filtered by compiled resolvers
1352+
// The parenthesized part has to tolerate nesting. Written as
1353+
// '\x28[^\x29]+' it stops at the first ')', so a final compound
1354+
// holding a nested functional pseudo-class matches nothing at all, and
1355+
// a selector the optimizer cannot read is answered by testing every
1356+
// element in the context instead of the elements of one tag or class.
1357+
parenthesized = '\\x28[^\\x28\\x29]*(?:\\x29|$)'
1358+
parenthesized = '\\x28(?:[^\\x28\\x29]|' + parenthesized + ')*(?:\\x29|$)'
1359+
parenthesized = '\\x28(?:[^\\x28\\x29]|' + parenthesized + ')*(?:\\x29|$)'
1360+
13511361
reOptimizer = RegExp(
13521362
'(?:([.:#*]?)' +
13531363
'(' +
@@ -1356,7 +1366,7 @@
13561366
'(?:' +
13571367
':[-\\w]+|' +
13581368
'\\[[^\\]]+(?:\\]|$)|' +
1359-
'\\x28[^\\x29]+(?:\\x29|$)' +
1369+
parenthesized +
13601370
')*)$',
13611371
)
13621372

‎test/optimizer-nesting.md‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
# Nested optimizer regression
2+
3+
Run with Node.js ≥ 22:
4+
5+
```sh
6+
pnpm install
7+
pnpm run test:optimizer
8+
```
9+
10+
The tests check strict factory initialization and nested selector results,
11+
including cached queries. jsdom supplies an independent reference engine.

‎test/optimizer-nesting.test.mts‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
const __dirname = import.meta.dirname
2+
import { createRequire } from 'node:module'
3+
const require = createRequire(import.meta.url)
4+
const assert = require('node:assert/strict')
5+
const { readFileSync } = require('node:fs')
6+
const { join } = require('node:path')
7+
import { test } from 'vitest'
8+
const vm = require('node:vm')
9+
const { JSDOM } = require('jsdom')
10+
const source = readFileSync(join(__dirname, '../src/nwsapi.js'), 'utf8')
11+
12+
test('strict factory initialization does not leak parser variables', () => {
13+
const context = {
14+
module: { exports: {} as (host: unknown) => unknown },
15+
exports: {},
16+
}
17+
vm.runInNewContext('"use strict";\n' + source, context)
18+
const { window } = new JSDOM('<!doctype html><div></div>')
19+
try {
20+
assert.doesNotThrow(() => context.module.exports(window))
21+
assert.equal(Object.hasOwn(context, 'parenthesized'), false)
22+
} finally {
23+
window.close()
24+
}
25+
})
26+
27+
for (const selector of [
28+
'div:not(:nth-of-type(2n))',
29+
'div:not(:nth-child(3))',
30+
'div:is(.a):not(:where(.b))',
31+
'div:not(:not(:not(span)))',
32+
'div:has(:is(.a .b))',
33+
]) {
34+
test(selector, () => {
35+
const { window } = new JSDOM(
36+
'<!doctype html><div id=a class=a><span class=a><i class=b></i></span></div><div id=b class=b></div><div id=c class=a></div>',
37+
)
38+
try {
39+
const nw = require('../src/nwsapi')(window)
40+
const expected = [...window.document.querySelectorAll(selector)]
41+
assert.deepEqual(nw.select(selector), expected)
42+
assert.deepEqual(nw.select(selector), expected, 'cached selection')
43+
} finally {
44+
window.close()
45+
}
46+
})
47+
}

0 commit comments

Comments
 (0)