W3C home > Mailing lists > Public > public-webapi@w3.org > May 2008

Re: [SelectorsAPI] Analysis of Context-Rooted Queries (was: Thoughts on querySelectorAll)

From: Lachlan Hunt <lachlan.hunt@lachy.id.au>
Date: Mon, 05 May 2008 23:13:49 +0200
Message-ID: <481F788D.3090703@lachy.id.au>
To: John Resig <jresig@mozilla.com>
Cc: public-webapi@w3.org

Hi,
   I've taken the time to analyse the situation regarding support for 
context-rooted queries, considering the use cases and possible 
implementation strategies.

This is a rather long email, and I have divided it into sections.

Table of Contents:

* Introduction
* Use cases
   - Descendants
   - Children
   - Siblings
* Summary of Problems
* Summary of Possible Solutions
* Analysis of Solutions
   - Solution 1
   - Solution 2
   - Solution 2
   - Solution 4
   - Solution 5
* Conclusion
* Appendix


*Introduction*

For all cases where authors are only using a simple selector or a 
sequence of simple selectors (i.e. no combinators), then the result will 
be the same in both the current API and existing JS libraries.  So any 
use cases that don't use a combinator have been ignored in this analysis.

There are 3 types of combinators that need to be considered: descendant 
combinators (" "), child combinators (">") and sibling combinators ("+" 
and "~"), and I have separated into those 3 categories.

For simplicity, I'm only comparing with JQuery and Dojo, but similar 
examples could probably be found using any other JS library that 
supports a similar feature.

All real world examples I've linked to are on google code.  I realise 
this is quite a limited sample and may not be totally representative of 
the code elsewhere on the web, but finding code elsewhere and manually 
inspecting the source code of pages is difficult and time consuming. 
So, it's the best I could reasonably do.

For all examples, assume:

   var foo = document.getElementById("foo");


*Use Cases*

*Descendants*

1. Finding descendants of another element that is also a descendant of
    the context node.
    JQuery: foo.find("div p");
    Dojo:   dojo.query("div p", foo);

Those would match the p element in the following markup:

a. <section id="foo">
      <div>
        <p>...</p>
      </div>
    </section>

But would not match in either of these:

b. <div id="foo">
      <p>...</p>
    </div>

c. <div>
      <section id="foo">
        <p>...</p>
      </section>
    </div>

Examples:
http://www.google.com/codesearch?q=file%3Ajs%24+jquery+\.find\([%27%22][^%27%22%3E%2C]%2B[\+]
http://www.google.com/codesearch?q=file%3Ajs%24+dojo\.query\([%27%22][^%27%22%3E%2C]%2B[\+]

This is not entirely possible with the current API.  With JQuery and 
Dojo, it requires all sequences of simple selectors in the chain to 
match elements that are descendants of the context node.  With the 
current API, all but the last sequence of simple selectors in the chain 
could match any ancestor element.

Using the same selector with the current API would match the p element 
in all 3 markup examples above.

   foo.querySelector("div p");

Achieving the same result as the JS libraries is only possible with the 
current API by explicitly prepending a selector that matches the context 
node itself, but doesn't match any other element.  e.g. Using an ID 
selector would suffice, if the ID is known and assuming no duplicate IDs:

   foo.querySelector("#foo div p");

However, this is currently somewhat problematic where there is no such 
ID nor any other method of easily identifying the context node within 
the selector.

*Children*

2. Finding a child of the context node.
    JQuery: foo.find(">div");
    Dojo:   dojo.query(">div", foo);

Those would match the div element in the following markup:

a. <section id="foo">
      <div>...</div>
    </section>

but does not match in this markup:

b. <section id="foo">
      <article>
        <div>...</div>
      </article>
    </section>

Examples:
http://www.google.com/codesearch?q=file%3Ajs%24+jquery+\.find\([%27%22]%3E
http://www.google.com/codesearch?q=file%3Ajs%24+dojo\.query\([%27%22]%3E

Similarly to the workaround for the descendant combinator above, this 
can only be achieved by prepending a selector that only matches the 
context node, and is subject to the same limitations.

foo.querySelector("#foo>div")


3. Finding a child of an element that is itself a descendant of the
    context node.
    JQuery: foo.find("p>span");
    Dojo:   dojo.query("p > span", foo);

(Dojo seems to be buggy and requires spaces around the '>' combinator.)

Those would match the span element in the following markup examples:

a. <div id="foo">
      <p><span>...</span></p>
    </div>

But would not match in the following:

b. <p id="foo"><span>...</span></p>

Examples:
http://www.google.com/codesearch?q=file%3Ajs%24+jquery+\.find\([%27%22][^%27%22%3E]%2B[%3E]
http://www.google.com/codesearch?q=file%3Ajs%24+dojo\.query\([%27%22][^%27%22%3E]%2B[%3E]
(No examples found using dojo)

With JQuery and Dojo, no selector in the chain can match the context 
node at all, whereas it can in the current API.  The span would be 
matched in both markup examples above.

foo.querySelector("p>span");

To only match in example a, but not in b, would again require prepending 
a selector and descendant combinator that only matches the context node.

foo.querySelector("#foo p>span");


*Siblings*


4. Finding a sibling of the context node.
    JQuery: foo.find("+p");
            foo.find("~p");

Those would match the p element in the following markup:

a. <div id="foo">...</div>
    <p>...</p>


http://www.google.com/codesearch?q=file%3Ajs%24+jquery+\.find\([%27%22][\%2B~]
http://www.google.com/codesearch?q=file%3Ajs%24+dojo\.query\([%27%22][\%2B~]
(No examples found using dojo, I don't think it's supported)

This one is not possible with the current API, since it is defined that 
only descendants of the context node are returned, which automatically 
excludes its siblings.

The only way to get the same result would be by using 
document.querySelectorAll() and prepending a selector that only matches 
the desired context node, which is subject to the same limitations 
mentioned earlier.

e.g.

document.querySelectorAll("#foo+div");


5. Finding a sibling of another element that is also a descendant of the
    context node.
    JQuery: foo.find("h1+p");
    Dojo:   dojo.query("h1 + p", foo);

Those would match the p element in the following markup:

a. <div id="foo">
      <h1>...</h1>
      <p>...</p>
    </div>

http://www.google.com/codesearch?q=file%3Ajs%24+jquery+\.find\([%27%22][^%27%22]%2B[\%2B~]
http://www.google.com/codesearch?q=file%3Ajs%24+dojo\.query\([%27%22][^%27%22]%2B[\%2B~]
(No examples found using dojo, though it is supported.)

It's obviously not as common as the others, though, as I mentioned 
earlier, my search is quite limited.

This one is already possible using the current API, since siblings both 
share the same parent, and thus would automatically be descendants of 
the context node.  So that works the same as the following, without any 
changes to the API.

   foo.querySelectorAll("h1+p");
   foo.querySelectorAll("h1~p");


*Summary of Problems*

This leaves us with a few problems to solve for

1. Finding descendants of another element that is also a descendant of
    the context node.
2. Finding a child of the context node.
3. Finding a child of an element that is itself a descendant of the
    context node.
4. Finding a sibling of the context node.


*Summary of Possible Solutions*

Solution 1. Define a simple selector that always matches the context 
node of the query.

This would most likely be a pseudo-class, and could be called :scope, 
:scope-root, :this, :self, :context-node, :context-root, :context, or 
any other name.  I'll use :scope for now only because that's what has 
been used in previous discussion, not because it is necessarily the best 
name.

Solution 2. Define that selectors are only evaluated in the scope of the 
context node, rather than the whole document, but *excluding* the 
context node itself.  Selectors in the chain can only match descendants 
of the context node, but not the context node itself or its ancestors.

Solution 3. Define that selectors are only evaluated in the scope of the 
context node, rather than the whole document, *including* the context 
node itself.

Solution 4. Define that selectors are only evaluated in the scope of the 
context node *including* the context node itself, but only descendants 
of the node are returned even if the context node matches the selector.

Solution 5. Define the methods to behave as if an implicit :scope 
selector and descendant combinator were prepended to each selector in 
the group.

If either of solutions 2 to 5 are possible, they could also be defined 
using additional methods instead of redefining the current methods.


*Analysis of Solutions*

*Solution 1*

   Define a simple selector that always matches the context node of
   the query.

Implementing this does not require significant modification of selector 
implementations in browsers.  In particular, no changes to the parser 
would be required.  We just need to know whether or not this solution 
adequately addresss the use cases and problems.

1. Finding descendants of another element that is also a descendant of
    the context node.

foo.querySelectorAll(":scope div p");

Correctly matches the p element in use case 1, example a, and not in 
examples b or c.

2. Finding a child of the context node.

foo.querySelector(":scope>div");

Correctly matches the div element in use case 2, example a, and not in 
example b.

3. Finding a child of an element that is itself a descendant of the
    context node.

foo.querySelector(":scope p>span");

Correctly matches the div in use case 3, example a, and not in example b.

4. Finding a sibling of the context node.

foo.querySelector(":scope+p");

This does not match anything because the method is defined to only match 
descendants, not siblings.  So, this raises the question of whether it 
is possible to redefine the methods to also check sibling elements?

The answer is no because the elements that are checked cannot be 
dependant upon the combinators used.  e.g.

foo.querySelector("div p");

That should not match any sibling p elements of foo, so such elements 
should not be checked.  However, this one would have to:

foo.querySelector("div :scope+p");
foo.querySelector("div h1:scope+p"); (assuming <h1 id="foo">)

But then this one would not

foo.querySelector("div h1+p");

Basically, this makes the implementation overly complex since it would 
need to determine whether or not to check descendant elements or sibling 
elements first based on whether the :scope pseudo-class is used and 
followed by a sibling combinator, and then evaluate the selector with 
each element.

However, there may be another solution to address this use case which I 
will discuss later.  See the appendix at the bottom.


*Solution 2*

   Define that selectors are only evaluated in the scope of the
   context node, rather than the whole document, but *excluding*
   the context node itself.  Selectors in the chain can only
   match descendants of the context node, but not the context
   node itself or its ancestors.

This would require modification of existing selector engines in browsers 
to be implemented.  In existing implementations, an element is evaluated 
against a selector in the context of the entire document.  It would 
require implementations to isolate the tree of nodes within the context 
node before evaluating each element.  But if we assume for the moment 
that this is technically possible, in spite of difficulty, we still need 
to determine whether or not it addresses the use cases.

1. Finding descendants of another element that is also a descendant of
    the context node.

foo.querySelector("div p");

Works as expected.

2. Finding a child of the context node.

Not possible, since there is no way to address the context node itself.

3. Finding a child of an element that is itself a descendant of the
    context node.

foo.querySelector("p>span");

Works as expected.

4. Finding a sibling of the context node.

Not possible, since it's still only searching descendants, not siblings.


*Solution 3*

   Define that selectors are only evaluated in the scope of the
   context node *including* the context node itself.

1. Finding descendants of another element that is also a descendant of
    the context node.

This will work in cases where the left most selector in the chain does 
not match context node itself.  e.g.

foo.querySelector("div p");

That would correctly match the p element in use case 1, example, and not 
match in example c.  But it would incorrectly match it in example b. 
This would require the use of a selector that matches the context node 
itself.

2. Finding a child of the context node.

This would also require selector to explicitly match the context node 
itself.

foo.querySelector("#foo>div");

That would work, but doesn't address the existing problem we have now.

3. Finding a child of an element that is itself a descendant of the
    context node.

This is similar to #1, and again, this will also require a selector to 
match the context node.

4. Finding a sibling of the context node.

Not possible because it's still only searching descendants, not siblings.

This solution also introduces another unintended consequence.

<div id="foo"><div>...</div></div>

foo.querySelector("div") == foo;

That doesn't match the behaviour of the existing API, nor of JQuery and 
Dojo.


*Solution 4*

   Define that selectors are only evaluated in the scope of the
   context node *including* the context node itself, but only
   descendants of the node are returned even if the context node
   matches the selector.

This solves the unintended consequence from solution 3, but for all the 
use cases, it still suffers from the same problems.


*Solution 5*

   Define the methods to behave as if an implicit :scope selector
   and descendant combinator were prepended to each selector in
   the group.

This would work by taking the selector and appending the equivalent of 
":scope " to the beginning of it, and then parsing as usual.  :scope 
could be implemented in any way the UA wanted here since it's not 
actually used by the author.

1. Finding descendants of another element that is also a descendant of
    the context node.

foo.querySelector("div p");

This becomes ":scope div p" and works is the same solution 1.

2. Finding a child of the context node.

foo.querySelector(">div");

This becomes ":scope >div" and also works the same as solution 1.

3. Finding a child of an element that is itself a descendant of the
    context node.

foo.querySelector("p>span");

This becomes ":scope p>span" works the same as solution 1.

4. Finding a sibling of the context node.

foo.querySelector("+p");

This becomes "scope +p" and fails for the same reason as solution 1.

While this looks promising on the surface, the real problem lies in the 
implementation of the selector parsing. This requires signifant changes 
to the grammar of selectors, and thus alteration of the selector engines 
in browsers.

Consider the following selector:

">strong, >em"

The expectation would be for this to become:

":scope >strong, :scope >em"

The question is how to parse and convert it.  Since it is invalid 
according to the grammar of selectors, current parsers would reject it 
with a parse error.  Modifying the grammar explicitly for use within 
this API is an unacceptable risk because it significantly increases the 
costs of defining the spec, reimplementing selector parsing; 
significantly increases the chance of introducing bugs and 
interoperability issues.  All browsers have had their fair share of 
selector parsing bugs over the years (it's been the basis of many CSS 
hacks in the past!), and repeating history is really not a good idea.


*Conclusion*

Solutions 1 and 5 both equally solve 3 out of 4 of the use cases, 
whereas 2, 3 and 4 all suffer from problems with them.  The 
implementation issues with solution 5 eliminate it as a possibility, 
leaving solution 1 as the only reasonable choice.

It is thus my firm belief that defining and implementing :scope (or 
whatever it gets called) is the best way to move forward and address 
this problem.  However, as I have stated before, this would belong in a 
separate spec and very likely end up in the next version of Selectors.


*Appendix*

The 4th use case isn't addressed by any of the solutions.  However, I 
mentioned ealier that there may be a separate solution to consider.

If the methods were defined to accept an additional parameter 
representing a context node in addition to introducing the :scope 
selector, it may work.

e.g.
document.querySelectorAll(":scope+p", foo, nsresolver);

Here, :scope would match the foo element and the adjacent sibling p 
element (if present) would be returned.

But it introduces some interesting consequences for use on elements.

var foo = document.getElementById("foo");
var bar = document.getElementById("bar");
foo.querySelector(":scope", bar, nsresolver);

Here, :scope would match the bar element instead of the foo element, 
which would be the default, but still only descendants of foo would be 
matched.

This may suffer from other problems, since I haven't fully evaluated it, 
and it does slightly increase the complexity.  But if the use cases for 
matching siblings of the context node can be deemed significant enough, 
it may be worth investigating further.  But keep in mind that my 
searches revealed very few real world examples attempting to do this, 
and so it may not be worth it.

-- 
Lachlan Hunt - Opera Software
http://lachy.id.au/
http://www.opera.com/
Received on Monday, 5 May 2008 21:14:30 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 5 May 2008 21:14:30 GMT