I don't think this will be supported initially. Maybe no combinators at all, only simple selectors.

These two combinators can probably be supported by the HTML API as long as they non-final selector is an element selector:

• div > .className ✅ supported
• .className > div ⛔️ not supported

Tags can be "seen" via bookmarks, while things like IDs, classes, attributes etc. would require seeking or more advanced internal tracking.

Is the problem that we'd need to keep track of all the attributes requested by the selector in the entire breadcrumbs trail?

Exactly. Either breadcrumbs would need to store all of their attributes or we'd need to seek around the document to check them which would be very costly.

All of the supported selectors are things that can be checked from given tag in the document without any seeking as the HTML API is implemented now.

If we knew the selector upfront, we could always store the attributes needed to match it, e.g. store the class attribute if we know we'll only ever look for div > .className. Only that wouldn't be practical.

However, keeping track of classnames in all the breadcrumbs elements seems okay-ish resource-wise.

Perhaps we could even have a "CSS-enabled" mode where we'd keep track of all the breadcrumbs attributes shorter than, say, 100 bytes? It wouldn't be perfect but should suffice for most attribute-based matches.

There will be ways to support more selectors, one good idea is to set some state to track data for certain selectors as the document is traversed.

One tricky thing with that implementation is that it may be necessary to return to the start of the document depending on the selectors used and scan again from there so that the necessary data is collected during traversal. This probably involves analyzing the selectors, deciding what data needs to be stored, seeking to the beginning if necessary, seeking back to the current location, and then trying to find the selector.

The complexity here is significant. It can be overcome, but I think the set of selectors supported in this PR as it is now is a good starting place with very limited matching complexity. Iteration to improve support can be added in future PRs.

Oh! Everything I said I meant for the future, no need to hold up this work :)

On seeking - sounds reasonable, although it won't combine well with streaming. What would an example of a selector that requires backtracking?

What would an example of a selector that requires backtracking?

This is mostly necessary to support selecting from arbitrary positions in the document. If we knew we were at the start of the document, we could determine what additional state needed to be tracked and start collecting it.

• The sibling combinators + and ~ select based on preceding elements, so it would be necessary to back up to check for matches.
• Support for subclass selectors (ID, class, and attribute) in non-final position, like #my-id div would require backing up to parse some attributes along with breadcrumbs.
• If pseudo-class selectors were added, I'd expect many of them to require more understanding of the document structure.

in earlier work I did I actually proposed a list-interface for selecting elements and that list took all selectors of interest. that’s not a great solution to mandate, but it does allow for up-front analysis of the set of selectors, and then a crawl to find each one in succession.

I was going to make a comment about select_all() and the generator it yields and how I worry it miscommunicates the ability to chain selection at that point. if we start selecting a different selector from within the foreach, we move the underlying HTML Processor and now it will select a different element on the next iteration than it would have (potentially) if we hadn’t called one from inside.

to that end, if the underlying HTML Processor is moving, can we not get select_all() behavior simply by calling select() in succession in while ( $processor->select() )?

then, one thing is more explicit, that if we call select() from inside that loop, we kind of acknowledge we might change the outer loop because the $processor is shared and stateful.

it doesn’t solve the problem of the unknown necessary context from above.

thinking that the FirTree representation might be able to help us by tracking attribute spans, making it faster to re-scan parent nodes, but also we could say someone can register selectors before traversal, and we maintain the relevant attributes as we go, regardless of which select() is running…

here it reads as if null is a sentinel value for “as long as the attribute exists” but without reading the code I would have assumed passing null would mean “only match if the attribute doesn’t exist on the tag”

what do you think about this?

Attribute selectors have the form [attr] (presence) or one of the matching forms like [att=val] (att attribute is an exact match for the value val).

The [attr] form is represented here with a null matcher (there's no matching logic) as well as a null value (there's no value to match). Those must either both be null or there must be both a matcher and a value.

I believe this is interchangeable here in case it's clearer:

if ( null === $this->matcher ) {
	return true;
}

Another option would be to add another matcher value like MATCH_PRESENCE to indicate that type of matcher.

Either way, the null value seems appropriate to me. The selector does not have a value to match. There is no negative attribute selection.

This may be a question of perspective, for example the HTML API returns null if a an unset attribute is requested, true for a boolean attribute, or a string for an attribute with a value. Attribute selectors don't follow the same logic. There's no way to only match a boolean or to match elements without an attribute, so I don't think we should try to align on those types of values. There may or may not be a string value to match.

This should mostly be an internal detail, it's not something users should really be interacting with.

I'm open to discuss this further. Either way, it's likely a good idea to clarify the null value in this property's documentation block.

while this seems fine for now, I suspect that at some point we will prefer to crawl through the attribute value comparing as we go with substr_compare() rather than allocate each substring. we can remember that in some documents we see DoS attacks due to long attribute values.

$this->whitespace_delimited_list() could also return a starting byte offset into the value instead of the substring, which would resolve this without changing much of the calling interface.

not immediately a fan of mutating the offset passed into the function. did you consider some other examples of passing in something like &$bytes_parsed? for example, the HTML decoder does this which leaves the input variables untouched while still communicating &$match_byte_length

see above: would be nice if instead of parse_whitespace we had this function return the length of the whitespace bytes and then this line could use the same variable names as the HTML API with

$at += self::skip_whitespace( $input, $at );

when I explored this long ago, I actually felt like the symbols in use in CSS provided reasonable literal values in the code vs. the use of consts. it didn’t have the same explanatory power in the code, but it provided a more direct correspondence with the CSS, which was nice, plus involved fewer translations/CPU cycles.

I'm open to that, what do you have in mind, a single character?

• =: exact
• *: contains
• etc.