Re: [selectors-4] selector matching being specified from left to right

On Tue, Aug 11, 2015 at 11:34 AM, fantasai
<fantasai.lists@inkedblade.net> wrote:
> On 08/11/2015 01:39 PM, Tab Atkins Jr. wrote:
>> On Tue, Aug 11, 2015 at 10:31 AM, fantasai
>> <fantasai.lists@inkedblade.net> wrote:
>>>
>>> Tab, why is this section in the spec? What is it providing that's
>>> not otherwise provided?
>>
>> It provides a basis for me to actually define combinators in a
>> rigorous way, which is necessary when we have more complex combinators
>> like the shadow-piercing ones (tho we're changing them).  When you're
>> crossing between contexts and have to define in what context each part
>> of the selector is actually evaluated in, having a good description of
>> the process makes it much easier and less error-prone.
>
> I'm not entirely convinced here, can you point me at an example of where
> you are needing this section to exist in its current form?
>
> Fwiw, I definitely think we should be writing the definitions about
> matching an individual selector against an individual element (and
> giving a match/not-match result), not creating a tree-filtering
> algorithm. That's absolutely not necessary to put in the spec.

The spec's algorithm is currently written as an operation that takes,
at minimum, a selector and one or more root elements that define the
trees to start the search in, and returns a list of matched elements.

You're asking for it to instead be defined as a predicate on an
element.  From IRC convo, you're imagining that the operation would
take a selector and an element, and return a bool.  But this is
incorrect!  The operation has to take a selector, an element, *and*
one or more root elements that define the trees to start the search
in.  You don't get to skip the "what contexts am I starting in" step
just because you're asking about a specific element!

The distinction is irrelevant when you're only operating over one
tree, but as soon as you get more complicated, like the
shadow-piercing combinators and pseudo-elements did, it becomes *very*
important to be clear about where you're beginning the evaluation of
the selector.  "foo::shadow bar", for example, will *never* match an
element in the same tree as where it starts; it has to be started in a
parent tree, where it can find a "foo" element and descend into its
shadow tree!

So the predicate form is *strictly more complicated* to define than
the filtering form.  This becomes very important when you're trying to
write clear, rigorous text in specs.  If you have the filtering form
and you want to use it as a predicate, you can just say "find all
elements matching selector starting from the document root. If element
is in the returned list, ...".  It's a tiny addition for the change in
purpose.

On the other hand, if you have the predicate form and you want to use
it to find everything that matches, you have to *explicitly enumerate
every tree that might be searched by the selector* in order to get the
list of possible elements you're going to filter.  You have to say
something like "Return all elements in the tree, and those that are in
nested shadow trees, recursively, which match the following selector,
when evaluated starting from the elements in this tree", and that's
assuming that shadow trees are the only trees we'll ever have to worry
about!  (If we gain further alternate-tree concepts, every bit of spec
text that doesn't mention them will need to be updated to be correct.)
 What's worse, the knowledge of which trees you might search *is
already embedded in the selector*, in the form of the
combinators/pseudo-elements used, so you're repeating yourself.

I discovered the difficulties here when trying to write the
shadow-piercing combinators.  Keeping this as a tree-search is, I
think, necessary for sanity.

This is also why the algorithm is written as evaluating selectors
left-to-right, rather than right-to-left as browsers actually do.
Right-to-left is similar to the predicate form; you have to start by
providing the list of elements that might be returned, and then
afterwards check that the matching process for a given element had at
least one path that ended in the correct starting tree.  It's strictly
more complicated and fragile to talk about in spec terms.  We could
possibly work around this in the spec text by first preprocessing the
selector, paying attention only to the combinators and doing a
left-to-right walk from the starting context to find the trees we
should be searching, then doing a right-to-left match on those
elements with the full selector.  That would make the algorithm
longer, and probably require all combinators to be described twice,
once as an ltr tree transformer and once as an rtl matcher, but hey, I
guess it's possible.

~TJ

Received on Tuesday, 11 August 2015 22:07:09 UTC