Sunday, July 31, 2005


All right, y'all had plenty of time to implement the imperative tree traversal, so let's compare notes. Here's what my Javascript version looks like--built to work on actual DOM nodes, of course, using real CSS selectors.

The matching function takes an element and an array of selector paths and returns the new array of selector paths, with an extra boolean field elementMatched indicating whether or not the node matched one of the given selector paths. I've elided the data definition for selectors and paths but it should be pretty clear from context. These get constructed from a parser for CSS selector strings.
// matchElement : Element * Array<Path>
// → Array<Path> & { elementMatched : boolean }
function matchElement(element, paths) {
var childPaths = new Array;
childPaths.elementMatched = false;
for (var i = 0; i < paths.length; i++) {
var path = paths[i];
if (path.isSimple()) {
if (path.selector().matches(element)) {
childPaths.elementMatched = true;
else if (path.selector().matches(element)) {
else {
return childPaths;
Then the main select function takes an element (which can be document.documentElement if you want to start at the root of the HTML document) and a single selector path and searches the entire tree for all matching nodes.
function select(element, path) {
var continuation =
new Array(new Task(element, new Array(path)));
var result = new Array;

while (continuation.length > 0) {
var task = continuation.pop();
var childPaths = matchElement(task.element, task.paths);

// Add the element's child nodes to the work list.
var children = task.element.childNodes;
for (var i = children.length - 1; i >= 0; i--) {
continuation.push(new Task(children[i], childPaths));

// If matched, save element in result array.
if (childPaths.elementMatched) {

return result;
I daresay my version is easier to understand than Simon Willison's getElementsBySelector implementation or Dean Edwards' cssQuery function. Mine's not quite as fully featured but the extra features--such as matching of pseudo-elements and arbitrary attributes--shouldn't actually affect the above code. It'll just require additions to the data definition of selector objects.

I've put the code up on my web site; a description page should appear at some point.


Anonymous said...

From one DOM to another. You are so my Hero.

Anonymous said...

what is the license for your js library? I'm hoping to use it for a project, but I need to know if I have the right to.


Dave Herman said...

Would LGPL work for you? The library isn't finished but I'll stick a license on it so you can use it.

Dave Herman said...

BTW, even if you end up modifying it, I'd be curious to hear about how you're using it and what modifications you've made. Would you mind emailing me about it? My address is

Dean Edwards said...

Dave - please note that it is considered pretty bad form to extend Object.prototype:

Anonymous said...

He's not advocating that, plus you can't extend Object OR Element in IE. So the comment is fairly pointless anyway.

Radley Co Tad said...

Hi, Great.. Tutorial is just awesome..It is really helpful for a newbie like me.. I am a regular follower of your blog. Really very informative post you shared here. Kindly keep blogging. If anyone wants to become a Front end developer learn from Javascript Training in Chennai . or Javascript Training in Chennai. Nowadays JavaScript has tons of job opportunities on various vertical industry. ES6 Training in Chennai