4
\$\begingroup\$

Create a small acceptably efficient JS CSS selector engine.

Please post size of script, and function to call preferable $(selector,context) style.

EDIT: All major browsers support document.querySelectorAll which makes this question irrelevant.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Try to beat jQuery: it is 85,000 bytes. \$\endgroup\$ Commented Apr 24, 2011 at 15:44
  • 4
    \$\begingroup\$ Sizzle, rather. \$\endgroup\$
    – Ry-
    Commented Apr 24, 2011 at 19:23
  • 3
    \$\begingroup\$ Would it hurt to write a requirements spec, or at least link to a description of precisely what is meant by "JS CSS selector engine"? \$\endgroup\$ Commented Apr 27, 2011 at 15:52
  • \$\begingroup\$ @PeterTaylor No it wouldn't hurt. Feel free to propose an edit. \$\endgroup\$
    – William
    Commented Aug 30, 2015 at 3:26
  • \$\begingroup\$ @LiamWilliam You misunderstand: Peter wants you to make the necessary changes yourself \$\endgroup\$
    – Beta Decay
    Commented Aug 30, 2015 at 10:22

1 Answer 1

6
\$\begingroup\$

Funny, I just made one of these. It is quite efficient because it compiles selectors. I don't know if it's IE6-compatible but it should be, I think. It supports CSS3 too - bonus points? :)

if(![].indexOf)Array.prototype.indexOf=function(a,i){i=i||0;while(i<this.length)if(this[i++]===a)return i-1;return-1};
String.prototype.startsWith=function(s){return this.length>=s.length&&this.substring(0,s.length)===s};
String.prototype.endsWith=function(s){return this.length>=s.length&&this.substring(this.length-s.length)===s};

var Sprint = {
    Error: function(m) {
        this.message = m;
        this.toString = function() {
            return this.message;
        };
    },
    getAllElementsIn: function(element) {
        var r = [];
        var f = function recurse(l, arr) {
            from(l).each(function(k, v) {
                if(v.nodeType === 1) {
                    arr.push(v);
                    recurse(v, arr);
                }
            });
        };
        f(element, r);
        return r;
    },
    getAllElements: function() {
        return Sprint.getAllElementsIn(document.documentElement);
    },
    getSiblings: function(element) {
        return element.parentNode ? from(element.parentNode).where(function(k, v) { return v.nodeType === 1; }).toArray() : [element];
    },
    getInfo: function(selector) {
        var r = {ATTR: {}, CLASS: [], PSEUDO: []};

        var quotes = '\'"', nestable = '(){}', inAttribute = false, escaped = false, currentQuotes = null, currentNested = [], nonchar = /^[^a-zA-Z0-9_\-]$/, lastSplitter = null, i = -1, c, s = '';
        while(++i < selector.length) {
            c = selector.charAt(i);
            if(escaped) {
                escaped = false;
            } else if(c === '\\') {
                escaped = true;
                continue;
            } else if(currentQuotes) {
                if(currentQuotes === c) {
                    currentQuotes = null;
                }
            } else if(quotes.indexOf(c) > -1) {
                currentQuotes = c;
            } else if(currentNested.length) {
                if(nestable.indexOf(currentNested[currentNested.length - 1]) + 1 === nestable.indexOf(c)) {
                    currentNested.pop();
                }
            } else if(nestable.indexOf(c) > -1) {
                currentNested.push(c);
            } else if(nonchar.test(c)) {
                if(lastSplitter) {
                    switch(lastSplitter) {
                        case '#':
                            r.ID = s;
                            break;
                        case '.':
                            r.CLASS.push(s);
                            break;
                        case '[':
                        case ',':
                            if(inAttribute) {
                                var j;
                                if((j = s.indexOf('=')) > -1) {
                                    r.ATTR[s.substring(0, j)] = s.substring(j + 1);
                                } else {
                                    r.ATTR[s] = true;
                                }
                            }
                            break;
                        case ':':
                            r.PSEUDO.push(s);
                            break;
                    }
                } else {
                    r.TAG = s;
                }

                if(c === ']') {
                    inAttribute = false;
                } else if(c === '[') {
                    inAttribute = true;
                }

                lastSplitter = c;

                s = '';
                continue;
            }
            s += c;
        }

        if(lastSplitter) {
            switch(lastSplitter) {
                case '#':
                    r.ID = s;
                    break;
                case '.':
                    r.CLASS.push(s);
                    break;
                case '[':
                case ',':
                    if(inAttribute) {
                        var j;
                        if((j = s.indexOf('=')) > -1) {
                            r.ATTR[s.substring(0, j)] = s.substring(j + 1);
                        } else {
                            r.ATTR[s] = true;
                        }
                    }
                    break;
                case ':':
                    r.PSEUDO.push(s);
                    break;
            }
        } else {
            r.TAG = s;
        }

        return r;
    },
    compileSingle: function(info) {
        var f = 'var t=l.nodeName?l.nodeName.toLowerCase():"",i=l.id?l.id.toLowerCase():"",c=l.className?" "+l.className.toLowerCase()+" ":"",s=Sprint.getSiblings(l),ss=from(s).where(function(k,v){return v.nodeName?v.nodeName.toLowerCase()===t:false;}).toArray(),si=s.indexOf(l),ssi=ss.indexOf(l);return ';
        if(info.TAG && info.TAG !== '*') {
            f += 't===\'' + info.TAG.toLowerCase().replace(/[\\']/g, function(x) { return '\\' + x; }) + '\'&&';
        }
        if(info.ID) {
            f += 'i===\'' + info.ID.toLowerCase().replace(/[\\']/g, function(x) { return '\\' + x; }) + '\'&&';
        }
        if(info.CLASS) {
            for(var i = 0; i < info.CLASS.length; i++) {
                f += 'c.indexOf(\' ' + info.CLASS[i].toLowerCase() + ' \')>-1&&';
            }
        }
        if(info.PSEUDO) {
            for(var i = 0; i < info.PSEUDO.length; i++) {
                var p = info.PSEUDO[i], j, v = '';
                if((j = p.indexOf('(')) > -1) {
                    v = p.substring(j + 1, p.length - 1);
                    p = p.substring(0, j);
                }
                switch(p) {
                    case 'first-child':
                        f += '!si';
                        break;
                    case 'first-of-type':
                        f += '!ssi';
                        break;
                    case 'nth-child':
                        // TODO: Implement all nth-*** selectors.
                        break;
                    case 'nth-of-type':

                        break;
                    case 'last-child':
                        f += 'si===s.length-1';
                        break;
                    case 'last-of-type':
                        f += 'ssi===ss.length-1';
                        break;
                    case 'nth-last-child':

                        break;
                    case 'nth-last-of-type':

                        break;
                    case 'only-child':
                        f += 's.length===1';
                        break;
                    case 'only-of-type':
                        f += 'ss.length===1';
                        break;
                    case 'disabled':
                        f += 'l.disabled';
                        break;
                    case 'enabled':
                        f += '!l.disabled';
                        break;
                    case 'checked':
                        f += 'l.checked';
                        break;
                    case 'empty':
                        f += '!l.childNodes.length'; // TODO: Maybe restrict to elements (t 1) only?
                        break;
                    case 'not':
                        f += '!Sprint.isMatch(\'' + v.replace(/\\'/g, function(x) { return '\\' + x; }) + '\')(0,l)';
                        break;
                    default:
                        throw new Sprint.Error("Unrecognized pseudo-class \"" + p + "\".");
                }
                f += '&&';
            }
        }
        if(info.ATTR) {
            from(info.ATTR).each(function(k, v) {
                var c = k.charAt(k.length - 1);
                f += 'l.getAttribute(\'' + ('$^*~|'.indexOf(c) > -1 ? k.substring(0, k.length - 1) : k).replace(/\\'/g, function(x) { return '\\' + x; }) + '\')';
                if(typeof v === 'string') {
                    v = v.replace(/\\'/g, function(x) { return '\\' + x; });
                    switch(c) {
                        case '$':
                            f += '.endsWith(\'' + v + '\')';
                            break;
                        case '^':
                            f += '.startsWith(\'' + v + '\')';
                            break;
                        case '*':
                            f += '.indexOf(\'' + v + '\')+1';
                            break;
                        case '~':
                            f += '.split(\' \').indexOf(\'' + v + '\')+1';
                            break;
                        case '|':
                            f += '.split(\'-\').indexOf(\'' + v + '\')+1';
                            break;
                        default:
                            f += '===\'' + v + '\'';
                    }
                }
                f += '&&';
            });
        }

        if(f.substring(f.length - 2) !== '&&') {
            // It matches anything.
            f = 'return true  ';
        }

        return new Function(['l'], f.substring(0, f.length - 2) + ';');
    },
    compileTree: function(selector) {
        var t = Sprint.tokenizeSelector(selector), i = -1, j, splitters = ', >~+';
        while(++i < t.length) {
            if(splitters.indexOf(t[i]) > -1) {
                j = i;
                while(--j >= 0 && t[j] === ' ') t[j] = null;
                j = i;
                while(++j < t.length && t[j] === ' ') t[j] = null;
            }
        }
        return from(t).where().select(function(k, v) {
            return k % 2 ? v : Sprint.compileSingle(Sprint.getInfo(v));
        }).toArray();
    },
    matchSingleTree: function(element, tree) {
        if(!tree.length) {
            return true;
        }

        if(!tree[tree.length - 1](element)) {
            return false;
        }

        for(var i = tree.length - 3; i >= 0; i -= 2) {
            switch(tree[i + 1] || ' ') {
                case ' ':
                    while(true) {
                        if(!(element = element.parentNode)) {
                            return false;
                        }
                        if(tree[i](element)) {
                            break;
                        }
                    }
                    break;
                case '>':
                    if(!(element = element.parentNode) || !tree[i](element)) {
                        return false;
                    }
                    break;
                case '+':
                    while(true) {
                        if(!(element = element.previousSibling)) {
                            return false;
                        }
                        if(element.nodeType === 1) {
                            if(!tree[i](element)) {
                                return false;
                            } else {
                                break;
                            }
                        }
                    }
                    break;
                case '~':
                    while(true) {
                        if(!(element = element.previousSibling)) {
                            return false;
                        }
                        if(tree[i](element)) {
                            break;
                        }
                    }
                    break;
            }
        }

        return true;
    },
    matchTree: function(element, tree) {
        var c = [];
        for(var i = 0; i < tree.length; i++) {
            if(tree[i] === ',') {
                if(Sprint.matchSingleTree(element, c)) {
                    return true;
                }
                c = [];
            } else {
                c.push(tree[i]);
            }
        }
        return Sprint.matchSingleTree(element, c);
    },
    tokenizeSelector: function(selector) {
        var quotes = '\'"', nestable = '(){}[]', escaped = false, currentQuotes = null, currentNested = [], tokens = [], splitters = ', >~+', i = -1, c, s = '';
        while(++i < selector.length) {
            c = selector.charAt(i);
            if(escaped) {
                escaped = false;
            } else if(c === '\\') {
                escaped = true;
                continue;
            } else if(currentQuotes) {
                if(currentQuotes === c) {
                    currentQuotes = null;
                }
            } else if(quotes.indexOf(c) > -1) {
                currentQuotes = c;
            } else if(currentNested.length) {
                if(nestable.indexOf(currentNested[currentNested.length - 1]) + 1 === nestable.indexOf(c)) {
                    currentNested.pop();
                }
            } else if(nestable.indexOf(c) > -1) {
                currentNested.push(c);
            } else if(splitters.indexOf(c) > -1) {
                tokens.push(s);
                tokens.push(c);
                s = '';
                continue;
            }
            s += c;
        }
        tokens.push(s);

        return tokens;
    },
    isMatch: function(selector) {
        var f = Sprint.compileTree(selector);
        return function(key, element) {
            return Sprint.matchTree(element, f);
        };
    },
    select: function(selector) {
        return from(Sprint.getAllElements()).where(Sprint.isMatch(selector)).toArray();
    },
    selectIn: function(selector, element) {
        return from(Sprint.getAllElementsIn(element)).where(Sprint.isMatch(selector)).toArray();
    }
};

function from(x) {
    if(!x) {
        throw new Sprint.Error("null or undefined passed to Sprint:from().");
    }

    var r = {
        keys: [],
        values: []
    };

    if(x.length) {
        for(var i = 0; i < x.length; i++) {
            r.keys.push(i);
            r.values.push(x[i]);
        }
    } else if(x.childNodes) {
        return from(x.childNodes);
    } else {
        for(var y in x) {
            if(x.hasOwnProperty(y)) {
                r.keys.push(y);
                r.values.push(x[y]);
            }
        }
    }

    r.length = r.keys.length;

    r.where = function(f) {
        if(f) {
            if(typeof f === 'string') return this.where(new Function(['k', 'v'], 'return ' + f + ';'));

            var r = {};
            for(var i = 0; i < this.length; i++) {
                if(f(this.keys[i], this.values[i])) {
                    r[this.keys[i]] = this.values[i];
                }
            }
            return from(r);
        } else {
            return this.where(function(k, v) { return v; });
        }
    };

    r.select = function(f) {
        var r = {};
        for(var i = 0; i < this.length; i++) {
            r[this.keys[i]] = f(this.keys[i], this.values[i]);
        }
        return from(r);
    };

    r.each = function(f) {
        for(var i = 0; i < this.length; i++) {
            f(this.keys[i], this.values[i]);
        }
    };

    r.first = function() {
        return this.values[0];
    };

    r.last = function() {
        return this.values[this.length - 1];
    };

    r.splitBy = function(f) {
        if(typeof f === 'function') {
            var r = [], c = {};
            for(var i = 0; i < this.length; i++) {
                if(f(this.keys[i], this.values[i])) {
                    r.push(c);
                    c = {};
                } else {
                    c[this.keys[i]] = this.values[i];
                }
            }
            r.push(c);
            return from(r);
        } else {
            return this.splitBy(function(x) { return x === f; });
        }
    };

    r.limit = function(f) {
        var r = {}, i = -1;

        if(typeof f === 'function') {
            while(++i < this.length && f(this.keys[i], this.values[i])) {
                r[this.keys[i]] = this.values[i];
            }
        } else {
            while(++i < Math.min(this.length, f)) {
                r[this.keys[i]] = this.values[i];
            }
        }

        return from(r);
    };

    r.after = function(f) {
        var r = {}, i = -1;

        if(typeof f === 'function') {
            while(++i < this.length && !f(this.keys[i], this.values[i])) {
            }
            while(++i < this.length) {
                r[this.keys[i]] = this.values[i];
            }
        } else {
            if(f < this.length) {
                i = f - 1;
                while(++i < this.length) {
                    r[this.keys[i]] = this.values[i];
                }
            }
        }

        return from(r);
    };

    r.toArray = function() {
        return this.values;
    };

    return r;
}

You use it like so:

Sprint.selectIn("mySelector", element);

Or

Sprint.select("mySelector")

. The code is 6.89KB minified and 2.26KB gzipped.

\$\endgroup\$
2
  • 7
    \$\begingroup\$ Please note that all user contributions here are cc-wiki licensed, meaning that you grant everyone the right to use and remix the content. If you don't want your code to be "stolen", then don't post it here. \$\endgroup\$ Commented Apr 24, 2011 at 15:20
  • 2
    \$\begingroup\$ Besides, the minification is trivial to overcome. IE9 even includes a JS formatter in the developer tools. However, it cannot be »stolen« legally; CC-By-SA requires attribution when re-using content. \$\endgroup\$
    – Joey
    Commented Apr 24, 2011 at 15:23

Not the answer you're looking for? Browse other questions tagged or ask your own question.