Match a compound selector against a tree

Writing this once demystifies querySelectorAll completely. There are two halves: turning a selector string into a structure, and testing that structure against a node.

A node is a plain object { tag, attrs, children }, where attrs and children may be missing and a child may be a plain string of text. Implement matchAll(root, selector) returning an array of the matching **nodes** in document order — that is, depth-first pre-order, with the root itself as a candidate. String children are text and never match.

The selector is a single compound selector with no combinators: an optional leading tag name followed by any number of #id, .class and attribute parts. A node matches only when every part matches.

Tag names are compared case-insensitively, so div matches a node whose tag is "DIV". An #id part matches when attrs.id is exactly equal. A .class part treats attrs.class as a whitespace-separated list and requires the class as a whole token, so .item does not match class="itemized". Attribute parts are [attr] for presence with any value, and [attr="v"], [attr^="v"], [attr$="v"] and [attr*="v"] for exact, prefix, suffix and substring comparison against String(attrs[attr]); the value may be wrapped in double quotes, single quotes, or neither. Return an empty array when nothing matches.

const tree = { tag: "DIV", attrs: { class: "page" }, children: [
  { tag: "ul", attrs: { class: "list" }, children: [
    { tag: "li", attrs: { id: "a", class: "item active" }, children: ["A"] },
    { tag: "li", attrs: { id: "b", class: "item" }, children: ["B"] },
    { tag: "li", attrs: { id: "c", class: "itemized" }, children: ["C"] }
  ] }
] };
matchAll(tree, "li.item").map((n) => n.attrs.id);
// => ["a", "b"]

const tree = { tag: "div", attrs: {}, children: [
  { tag: "A", attrs: { id: "x", href: "https://aniui.test/docs" } },
  { tag: "A", attrs: { id: "y", href: "/local" } }
] };
matchAll(tree, 'a[href^="https"]').map((n) => n.attrs.id);
// => ["x"]

matchAll({ tag: "div", attrs: {}, children: ["only text"] }, "li.missing");
// => []