Refactor `eval.ts`

[seia-soto]

The current querySelectorAll() behaviour of eval.ts is correct but written in very confusing way. This hugely delays the feature additions and bug fixes because the contributors cannot really estimate the true side-effects of the functions. They end up relying on the unit tests defining the behaviour and keep the internals black-boxed. This writing is to help other contributors understand how extended CSS works (especially about the internal evaluator) and bring the actual improvement regarding the structure.

What are actual basic operations?

The first step would be understanding the implementation requirements.

• matches(): test current element itself
• querySelectorAll(): select descendants under a scope
• traverse(): continue evaluating from an already-selected subject

Those three behaviours are the very basic operations that we need to combine to make higher APIs available, and also the reason the whole structure is very confusing: in short - querySelectorAll and traverse have great overlap in their roles.

When you look at their source-code, you'll have a very natural question: why one of traverse or querySelectorAll couldn't be a single entrypoint? traverse looks like quite universal as it accepts root and iterate itself by having the internal queue traversals. What we need to use and when?

traverse()

for (; index < selectors.length; index++) {
  // ** NOTE: Runs all core "evaluation" tasks by calling both "transpose" and "matches"
  const candidates = transpose(element, selectors[index]);
  const isTransposeOperator = candidates !== null;
  if (isTransposeOperator) {
    traversals.push(...candidates.map((element) => ({ element, index: index + 1 })));
    break;
  } else if (matches(element, selectors[index]) === false) {
    // no maches found - stop processing the branch
    break;
  }
}
// Check if the loop was completed
if (index === selectors.length && !results.includes(element)) {
  results.push(element);
}

querySelectorAll: looks like this function just "destructures" ASTs and the actual task is done by "traverse".

export function querySelectorAll(element: Element, selector: AST): Element[] {
  // Type of `attribute`, `class`, `id`, and `type` are to express simple selectors.
  // e.g. `[attr]` is `attribute` type, `.cls` is `class` type, `#lure` is `id` type, and `div` is `type` type.
  if (
    selector.type === 'id' ||
    selector.type === 'class' ||
    selector.type === 'type' ||
    selector.type === 'attribute'
  ) {
    ...
  }

  // Type of `list` is sets of selector trees.
  // We just join all the results.
  // e.g. `p, span`
  if (selector.type === 'list') {
    ...
  }

  // Type of `compound` is a set of consecutive selectors.
  // They're in chained form like `p:has(span)` and works as logical AND.
  if (selector.type === 'compound') {
    ...
  }

  // Type of `complex` is used to express CSS combinators: ` `, `>`, `+`, `~`.
  // The `branch` function describes the behavior per combinator.
  if (selector.type === 'complex') {
    ...
  }

  if (selector.type === 'pseudo-class') {
    ...
  }

  return [];
}

Why traverse and querySelectorAll are actually different

They're actually overlapping for having conditional branches for each type of AST processing (not directly tho). However, there's a critical difference in compound selector handling.

• querySelectorAll($0) follows descendant selector semantics.
• Compound selectors (e.g. x:y:z) use relatives selection including self for the first selector part, then same-subject continuation for the rest. Therefore, it keeps the initial querySelectorAll behaviour and continues matching for subnodes. (Transposing pseudo-class selectors are special cases)

The same semantics go for pseudo-class selectors. It's an overlapping example but I'm adding to help the understanding of the readers.

Let's assume there's a selector called: a:not([x-attr]). The whole structure looks like it can be somehow "chained" but the reality is that a will look for "descendants" and the rest chain: :not([x-attr]) should look for "relatives".

So the first selector part discovers candidates, while the rest of the compound selector filters or transforms those candidates.

Why querySelectorAll (in eval.ts) cannot select html if it only chooses descendants

From the current implementation, querySelectorAll technically shouldn't be able to select html despite the comments in sources and tests.

It's actually the wrong assumption of the current implementation because document.querySelectorAll and document.documentElement.querySelectorAll are clearly different. Since it runs against document.documentElement which is html, it cannot look for self but all subnodes.

Future plans

The most critical goal would be refactoring the current structure to be easily understandable. It shouldn't be so destroying the existing functions and features but make the whole process more clear. Also, it should have a local state to help reducing visiting same nodes many times as well, to maintain internally managed caches in consistent manner.

The details should be discussed.