Find every element a CSS selector matches

Your component library's test helpers look up elements with CSS selectors in a saved page snapshot, without a browser. The snapshot is a tree of elements, each with a tag and some classes.

Write select_all(tree, selector) that returns the positions of the elements the selector matches.

Input and output:

• tree: 1 to 2,000 elements. Each is [parent, tag, classes]: the position of its parent in tree, its tag name, and its list of class names. The root comes first and has parent -1. Every other element's parent comes earlier in the list. Elements are nested at most 100 deep.
• Children of the same parent are siblings, ordered as they appear in tree.
• Tag and class names are made of lowercase letters, digits and hyphens.
• selector: 1 to 20 compound selectors joined by combinators. A compound is a tag name or *, optionally followed by classes such as .card.active, or classes alone, such as .card. A combinator is one or more spaces (descendant), > (child), + (next sibling) or ~ (later sibling). There may be spaces around >, + and ~, and at either end of the selector.
• Returns the matching positions in increasing order.

Rules:

• A compound matches an element when its tag is *, absent, or equal to the element's tag, and the element has every class the compound lists.
• The selector matches an element when you can pick one element for each compound so that every picked element matches its compound. The element itself is picked for the last compound.
• Each picked element must also stand in its combinator's relation to the element picked for the compound after it:
  • For spaces, it is one of that element's ancestors: its parent, its parent's parent, and so on.
  • For >, it is that element's parent.
  • For +, it is the sibling right before that element.
  • For ~, it is any sibling before that element.