CSS :nth-child() and friends are O(n²) on sibling-list width #84

Description of the bug

:nth-child() and its siblings are O(n²) on the width of the sibling list. Each candidate node
recomputes its own position by walking previousSibling to the start of the list, so a selector
tested against n siblings performs n²/2 pointer hops.

On a table of 4000 rows, tr:nth-child(2n) takes 75× longer than tr, and the gap grows with
every row added.

Measurements

<table> containing n × <tr><td>x</td></tr>, PHP 8.3.16, main @ e23fbb0:

tr is linear; :nth-child quadruples for each doubling of the row count. At 20 000 rows the same
selector takes ~12 seconds.

Which selectors are affected

Only the four :nth-* families. Measured at 2000 rows:

:first-child, :last-child, :only-child and :empty take a different path and are fine.

Root cause

src/CSS/DOMTraverser/PseudoClass.php:377 — nodePositionFromStart() walks the whole preceding
sibling chain for one node:

protected function nodePositionFromStart($node, $byType = false): int
{
    $i   = 1;
    $tag = $node->tagName;
    while (isset($node->previousSibling)) {
        $node = $node->previousSibling;
        if ($node->nodeType === XML_ELEMENT_NODE && (! $byType || $node->tagName === $tag)) {
            ++$i;
        }
    }

    return $i;
}

nodePositionFromEnd() (:399) is the mirror image. isNthChild() (:438) calls one of them per
node, so the cost for a full sibling list is 1 + 2 + … + n.

The :nth-of-type variants are slower still because $byType adds a tagName comparison at every
step of every walk.

Secondary: isNthChild() re-parses the an+b expression on every node —
Util::parseAnB($value) at :440 — for a value that is fixed for the whole query.

Suggested fix

Index the parent's child list once and reuse it, rather than re-deriving each node's position.
The same technique is already used elsewhere in the codebase for document-order sorting
(Util::siblingOffset()), where a SplObjectStorage memo scoped to a single call replaced exactly
this quadratic walk and made a 4000-wide sort go from 253 ms to 33 ms.

Sketch:

• On the first position request for a given parent, walk childNodes once and record each element
  child's 1-based index (and its index among same-tag siblings, for $byType).
• Memoize in an SplObjectStorage scoped to the query, not stored on the handler — this library
  mutates DOMs constantly (append(), remove(), wrap()), so a cache that outlives a single
  traversal would go stale.
• nodePositionFromEnd() is then count - index + 1 off the same table, with no second walk.
• Hoist Util::parseAnB() out of the per-node path.

That makes the whole sibling list cost one pass instead of one pass per node.

Notes

• Not a regression — main and every currently open branch behave identically here.
• Fix jQuery positional pseudo-classes to index the matched set #70 converts the jQuery positional pseudo-classes (:eq, :first, :lt, :gt, :odd,
  :even) into set-level filters and deliberately leaves the CSS structural ones alone, so it
  neither causes nor fixes this.
• Correctness is not in question; this is purely about cost.

Repro

<?php
require 'vendor/autoload.php';

foreach ([500, 1000, 2000, 4000] as $n) {
    $xml = '<?xml version="1.0"?><table>' . str_repeat('<tr><td>x</td></tr>', $n) . '</table>';

    $t = microtime(true); qp($xml, 'tr:nth-child(2n)')->count(); $nth = (microtime(true) - $t) * 1000;
    $t = microtime(true); qp($xml, 'tr')->count();               $plain = (microtime(true) - $t) * 1000;

    printf("rows %5d | tr %7.1f ms | tr:nth-child(2n) %9.1f ms | %3.0fx\n", $n, $plain, $nth, $nth / $plain);
}

QueryPath version

main @ e23fbb0

PHP Version and environment

PHP 8.3.16 (cli), macOS. Not version-specific.