Element.prototype.getElementsBySelector

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;
            }
            childPaths.push(path);
        }
        else if (path.selector().matches(element)) {
            childPaths.push(path.tailPath());
            childPaths.push(path);
        }
        else {
            childPaths.push(path);
        }
    }
    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) {
            result.push(task.element);
        }
    }
 
    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.