Re: ACTION-87: Selectors API

On Feb 26, 2006, at 1:04 PM, Cameron McCormack wrote:

>
> Cameron McCormack:
>> As for whether these are easy to implement or not, I guess it's a  
>> matter
>> of whether you are building on top of a CSS engine that you can't
>> modify.  The main advantage would be access to selector parsing
>> routines.
>
> *after thinking about it last night*
>
> You also need code that performs the actual selections, too.  This
> should be very similar to that which selects for the stylesheet rules
> anyway, though.

It's not that simple. Selectors for stylesheets are matched by  
examining the element when applying style, and testing what rules  
match. This API would require finding the elements that match a  
selector. The naiive way to do this is to walk the whole document and  
test each element for matching. But this is going to be way slower  
than, say, getElementById which operates in O(1) time in most browsers.

Both live lists and non-live lists have issues with being  
implementable efficiently. For a static list, you have to compute the  
whole list right away to make sure it remains static in teh face of  
changes. That means that even if you want only the first match you  
have to walk the whole document. This means that probably you want a  
selectSingleElement() in addition to selectElements().

Live lists have the problem that any document change forces you to  
recompute the list, so iterating the list while modifying the  
document often has O(N^2) behavior. For a subset of selectors it may  
be possible to avoid this through caching, and detecting exactly what  
changes make a difference, and putting in lots of notifications. But  
I think for at least some selectors this is not feasible.

I also think live lists are a confusing programming model. If you  
really are modifying the document while traversing the list, it is  
likely more annoying than helpful for the list to change. For example:

// severely buggy
function removeAllDivs()
{
     var divs = document.getElementsByTagName("divs");
     for (var i = 0; i < divs.length; i++) {
         var div = divs[i];
         div.parentNode.removeChild(div);
     }
}

This will not remove all divs. Could you even say without thinking  
about it which divs it will remove?

It seems to me that, when modifying the document, you generally do  
not want a live list, and when not modifying the document, it doesn't  
matter which kind you have. Therefore I would recommend against  
propagating the "live list" concept in new APIs.

So, in brief:
- Having an existing style system does not make it trivial to  
implement a DOM API to find elements by selector.
- Static lists are probably more efficiently implementable than live  
lists.
- Static lists would require a single-element version too, so you  
don't have to build the whole list just to get one element.
- Live lists are confusing as a programming model.
- Live lists suck for performance and make it easy to accidentally  
write O(N^2) code.

Regards,
Maciej

Received on Sunday, 26 February 2006 23:03:40 UTC