3

Given a CSS selector like

ul > li a

Would it be easier/faster to evaluate it from left to right, or right to left? (I realize the answers for "easy" and "faster" might be different.. I want the answer to both). I'm about to embark down one of these paths and I don't want to get half way there and then realize I chose the wrong path :)

LTR: Iterate over all the elements in the document, pick out the ones that are ul, then check all their children for li, and then look at their descendants for a.

RTL: Iterate over all the elements in the document, find all the a, filter out the ones that don't have an ancestor that is an li, if it does have an li ancestor, check if its parent is a ul, if not, drop that a.

Also, there isn't really any other way to do this than iterating over all the elements is there?

I'm thinking in the context of finding elements, as jQuery does, not in the context of applying styles.

Yangshun Tay
  • 49,270
  • 33
  • 114
  • 141
mpen
  • 272,448
  • 266
  • 850
  • 1,236
  • It's just a plain ol' CSS2 selector. Nothing 3 about it. Just saying :P – BoltClock Nov 09 '10 at 02:48
  • @BoltClock: Woops... good point. I plan on supporting CSS3, but I guess thats not relevant to this specific question. – mpen Nov 09 '10 at 02:58

2 Answers2

4

Browsers, and the Sizzle selector JS engine (what is used in jQuery and other frameworks) use right to left matching.

Right to left works out to be the most optimal traversing solution in most situations.

Sizzle optimizes selectors that start with an ID. It resolves the element with the ID first. It then uses that as context for further traversing.

So if you have the selector

#myID > ul a

Sizzle will find the element with #myID first, assuming that in this case, left to right is more optimal.

BoltClock
  • 700,868
  • 160
  • 1,392
  • 1,356
Dan Herbert
  • 99,428
  • 48
  • 189
  • 219
  • 1
    Ick.. if it finds #myID first, then it kinda mixes LTR and RTL and that's..just confusing. I could load all the #IDs into a dict first, and then do RTL parsing but for #IDs skip the traversal and check the dict. – mpen Nov 09 '10 at 03:08
  • What's the name of this algorithm? Would you mind sharing an url? – Abdullah Numan Jun 23 '22 at 04:21
2

This is one of those questions repeated on every design and programming forum. A common example is also the one given by the original poster on this thread:

ul > li a

if you traverse ltr you find all uls and then all lis of those uls and then all a tags in those lis. Consider the fact that the markup may look like:

<ul>
    <li>
        <a href="#">Click Here</a>
    </li>
</ul>

or it may look like:

<ul>
    <li>
        <span>
            <p>
                <div class="someuselessclass">
                    <span class="JunkClass">
                        <a href="#">Click Here</a>
                    </span>
                </div>
            </p>
        </span>
    </li>
</ul>

The fact is, you don't know how deep the traversal will have to go and there may be thousands of such links in thousands of such LIs. Seems to me that through experience, the browser builders that be have come to the conclusion that it is faster to parse Right To Left.

That's my two cents.

Paul Perrick
  • 496
  • 9
  • 22
  • Really? It comes up that often? I'd imagine the only people interested in this are those writing libraries such as jQuery or a layout engine. But anyway... I was thinking there could be just as many a's as ul's. But let's suppose for a moment, that the number of ul's and a's are the same, RTL would have to check all the way up to the root if it has no ancestor li, whereas going LTR, from the UL it would only have to check down a few levels to either find the A or a leaf node. Which distance is further... still not sure. – mpen Oct 18 '11 at 01:29
  • But I guess what you're saying is that LTR it has to parse through all the ULs and LIs even if there is no A at the end of it, whereas RTL it only considers ones that we know to have an A? But I think it's the same problem going that way too...You're looping through all the As, then finding ancestor LIs and may or may not have a parent UL. – mpen Oct 18 '11 at 01:31
  • I also forgot to add a third code example with dozens of other nodes within the li which demonstrates that if you do a LTR traversal you have to cover thousands of nodes more than if you did RTL – Paul Perrick Oct 18 '11 at 01:33
  • I did however end up going with RTL.... I think I found it easier. http://code.google.com/p/sharp-query/source/browse/trunk/XCSS3SE/XCSS3SE/SharpQuery.cs#265 – mpen Oct 18 '11 at 01:34