8
\$\begingroup\$

A few months ago, I wrote a query selector that seems to outperform the query selectors in the popular GP libraries by a pretty hefty margin. I'm wondering if I overlooked something. It seems odd that with all the manpower behind these other projects. It's this easy to come up with something that outperforms them.

The "trick" behind it is instead of parsing the query string every time, it will cache each query as a series of commands ("command pattern") to avoid parsing it again. Note that the results aren't cached, just the series of commands to be performed to get the results.

There are also some minor optimizations. For example, I assume that there isn't more than one head, title, or body tag in the document.

This supports CSS1 only (tag name, class name, id), but I think adding features from later CSS-es shouldn't affect the performance of the current code much at all, thanks to the "command-caching" design.

Have I overlooked something important? Is this fast because it's failing to do something critical? Is there something inherently wrong with this design, or is it possible the GP library authors have simply not considered this sort of design?

/**

    A simple, fast query selector.

    @fileOverview 

*/
/**

Perform a simple query selection.

@param {String} query

@param {Node} root 
    Optional root node, defaults to qs.global.document. 

@returns {Array|NodeList}
    DOM nodes matching the query.

@namespace The root qs namespace.

*/
function qs(query, root) {
  var doc = root ? root.ownerDocument || root :
      (root = qs.global.document);
  return qs.run(qs.cache[query] || qs.compile(query), {
    root: root,
    doc: doc
  }).nodes;
}
/**

A reference to the global object.
@type Object

*/
qs.global = (function () {
  return this || [eval][0]('this');
}());
/**

Holds command arrays, keyed by query string.
@type Object

*/
qs.cache = {};
/**

Various regexen.
@type Object

@private

*/
qs.rx = {
  singletons: /^(?:body|head|title)$/i,
  className: /\.[^\s\.#]+/g,
  id: /#[^\s\.#]+/g,
  tagName: /^[^\s\.#]+/g,
  lTrim: /^\s\s*/,
  rTrim: /\s\s*$/,
  comma: /\s*,\s*/,
  space: /\s+/
};
/**

Check whether a DOM node has a css class.

@param {Node} node 

@param {String} className

@returns {Boolean} true if success, else false.

*/
qs.hasClass = function (node, className) {
  return (' ' + node.className + ' ')
      .indexOf(' ' + className + ' ') > -1;
};
/**

@param {String} text
@returns {String}

*/
qs.trim = function (text) {
  return text.replace(qs.rx.lTrim, '').replace(qs.rx.rTrim, '');
};
/**

Check a DOM node against a qs.Compound object.

@param {Node} node
    The DOM node to check. 

@param {qs.Compound} compound
    An object constructed by qs.Compound, or an equivalent object.

@returns {Boolean} true if success, else false.

*/
qs.check = function (node, compound) {
  var className, i = -1;
  if ((compound.tagName && (compound.tagName !== node.tagName)) ||
      (compound.id && (compound.id !== node.id)) ||
      (!compound.className)) {
    return false;
  }
  while ((className = compound.className[++i])) {
    if (!qs.hasClass(node, className)) {
      return false;
    }
  }
  return true;
};
/**

Create an array of commands, store it in the cache, and return it.

@param {String} queryString

@returns {Array} 
    qs.Command objects to run for this queryString.

*/
qs.compile = function (queryString) {
  var result = [], query = new qs.Query(queryString),
      selectors = query.compounds,
      selector = selectors[0],
      compound, prevChain, i = -1,
      isLast, isSingleton;

  /*  If the normalized query is already cached, create a new 
      reference to the command array in the cache using this
      version of the queryString as the key.

  */
  if (qs.cache[query]) {
    return (qs.cache[queryString] = qs.cache[query]);
  }

  // FIXME: handle groups of selectors (recursive qs call)
  // if (selectors.length > 1) { }

  prevChain = 0;
  while ((compound = selector[++i])) {
    isLast = i === selector.length - 1;
    isSingleton = qs.rx.singletons.test(compound.tagName);
    if (compound.id || isSingleton || isLast) {
      result = result.concat(qs.compoundToChain(
        compound, selector.slice(prevChain, i)
      ));
      prevChain = i + 1;
    }
  }

  return (qs.cache[queryString] = qs.cache[query] = result);
};
/**

Called by qs.compile. Creates an array of commands from a
qs.Compound object.

@param {qs.Compound} compound

@param {Array} ancestorChecks

@returns {Array}
    Array of command objects.

*/
qs.compoundToChain = function (compound, ancestorChecks) {

  var result = [], hasId, hasAncestorChecks, className;

  compound = compound.copy();

  if (qs.rx.singletons.test(compound.tagName)) { 
    result.push({ 
      fn: qs.cmd.getByTag, 
      args: [compound.tagName, true] 
    });
    compound.tagName = false;
  }
  else if (compound.id) { 
    result.push({ 
      fn: qs.cmd.getById, 
      args: [compound.id] 
    });
    hasId = true;
    compound.id = false;
  }
  else if (compound.className[0]) { 
    className = compound.className.shift();
    result.push({ 
      fn: qs.cmd.getByClass, 
      args: [className] 
    });
  }
  else if (compound.tagName) { 
    result.push({ 
      fn: qs.cmd.getByTag, 
      args: [compound.tagName] 
    });
    compound.tagName = false;
  }

  if (compound.id || compound.tagName || 
      (compound.className && compound.className[0])) {
    result.push({ 
      fn: qs.cmd.filter, 
      args: [compound] 
    });
  }
  if (ancestorChecks.length) {
    result.push({ 
      fn: qs.cmd.checkAncestors, 
      args: ancestorChecks 
    });
    hasAncestorChecks = true;
  }
  if (hasId) {
    result.push({ 
      fn: qs.cmd.checkIdRoot 
    });
  }
  return result;

};
/**

Run a set of commands in a given context.

@param {Array} commands
    List of commands to run.

@param {Object} context
    Shared object referenced by `this` in each command.

@returns {Object} context.

*/
qs.run = function (commands, context) {
  var command, i = -1;
  if (!context) {
    context = {};
  }
  while ((command = commands[++i])) {
    if (command.fn.apply(context, command.args)) {
      return context;
    }
  }
  return context;
};
/**

@namespace 

Predefined commands for manipulating a collection of DOM nodes.

@description

*/
qs.cmd = {
  /**

  Get an element by id from the context document,
  and set the context nodes to an array containing the result,
  or an empty array.

  @param {String} id

  @return {Boolean} 
      true if no more commands should be processed, else false.

  */
  getById: function (id) { // getById
    var e = this.doc.getElementById(id);
    this.nodes = e ? [e] : [];
    return !e;
  },
  /**

  Get a NodeList by class name from the context root,
  and set the context nodes to the result.

  @param {String} className

  @return {Boolean} 
      true if no more commands should be processed, else false.

  */
  getByClass: function (className) {  // getByClass
    this.nodes = this.root.getElementsByClassName(className);
    return !this.nodes.length;
  },
  /**

  Get a NodeList by tag name from the context root,
  and set the context nodes to the result.

  @param {String} tagName

  @param {Boolean} setRoot
      If true, set the context root to the first found node.

  @return {Boolean} 
      true if no more commands should be processed, else false.

  */
  getByTag: function (tagName, setRoot) { // getByTag
    this.nodes = this.root.getElementsByTagName(tagName);
    if (setRoot) {
      this.root = this.nodes[0];
    }
    return !this.nodes.length;
  },
  /**

  Filter the context nodes.

  @param {qs.Compound} compound

  @return {Boolean} 
      true if no more commands should be processed, else false.

  */
  filter: function (compound) { // filter
    var nodes = this.nodes, node, i = -1, result = [];
    while ((node = nodes[++i])) {
      if (qs.check(node, compound)) {
        result.push(node);
      }
    }
    this.nodes = result;
    return !result.length;
  },
  /**

  Check whether the context nodes' ancestors match a chain of 
  compound selectors.

  @param {qs.Compound} compound...
      One argument for each ancestor in the chain. The "oldest"
      ancestor should be the first argument, and the "youngest"
      should be the last.

  @return {Boolean} 
      true if no more commands should be processed, else false.

  */
  checkAncestors: function (/*...*/) { // checkAncestors
    var root = this.root, nodes = this.nodes, node, result = [],
        check, len = arguments.length, checkIndex = len, i = -1,
        ancestor, topAncestor;
    while ((node = nodes[++i])) {
      ancestor = node;
      check = arguments[--checkIndex];
      while ((ancestor = ancestor.parentNode) && 
            (ancestor !== root)) {
        if (!qs.check(ancestor, check)) {
          continue;
        }
        check = arguments[--checkIndex];
        if (checkIndex < 0) {
          topAncestor = ancestor;
          result.push(node); 
          break;
        }
      }
      checkIndex = len;
    }
    this.topAncestor = topAncestor;
    this.nodes = result;
    return !result.length;
  },
  /**

  Check whether the context node is contained by the root node. 

  This command should be run if the *getById* command has been run. 
  It should run after any *filter* or *checkAncestors* commands 
  immediately following each *getById* command.

  @return {Boolean} 
      true if no more commands should be processed, else false.

  */
  checkIdRoot: function () { // checkIdRoot
    var root = this.root, 
        node = this.topAncestor || this.nodes[0];
    if (!root.ownerDocument) {
      root = this.nodes[0];
      return false;
    }
    while ((node = node.parentNode)) {
      if (node === root) { 
        root = this.nodes[0];
        return false;
      }
    }
    return true;
  }

};
/**

@class 

Stores a compound selector in object form.

@see <a href="http://www.w3.org/TR/selectors4/#structure">
Selectors Level 4: Structure and Terminology
</a>

@param {String} text
    Normalized compound selector text.

*/
qs.Compound = function (text) {
  /**

  CSS class to match.
  @type String

  */
  this.className = (text.match(qs.rx.className) || [])
      .join('').substring(1).split('.');
  /**

  Tag name to match.
  @type String

  */
  this.tagName = ((text.match(qs.rx.tagName) || [])[0] || '')
      .toUpperCase();
  /**

  Id attribute to match.
  @type String

  */
  this.id = ((text.match(qs.rx.id) || [])[0] || '')
      .substring(1);
  this.className.sort();
};

qs.Compound.prototype = {
  /**

  Create a plain object copy of the current object.

  @returns {Object}

  */
  copy: function () { 
    return { 
      id: this.id,
      className: this.className.slice(),  
      tagName: this.tagName
    };
  },
  /**

  Get the normalized version of the compound selector.

  @returns {String} 
      The normalized compound selector.

  */
  toString: function () { 

    return this.normalized ||
        (this.normalized = this.tagName + 
        (this.id ? '#' + this.id  : '') + 
        (this.className[0] ? '.' + this.className.join('.') : ''));
  }
};
/**

@class 

Stores information about a query selector.

@constructor

@param {String} text
    Query selector text.

*/
qs.Query = function (text) {
  var compoundStrings = text.split(qs.rx.comma),
      compound, compounds, i = -1, j,
      original = text;
  while ((text = compoundStrings[++i])) {
    compounds = qs.trim(text).split(qs.rx.space);
    j = -1;
    while ((compound = compounds[++j])) {
      compounds[j] = new qs.Compound(compound);
    }
    compoundStrings[i] = compounds;
  }
  compounds = compoundStrings;
  /**

  The original (non-normalized) query string.
  @type String

  */
  this.original = original;
  /**

  Compound selectors composing the query.
  @type Array

  */
  this.compounds = compounds.sort();
  /**

  Normalized version of the query.
  @type String

  */
  this.normalized = '';
};
/**

Get the normalized version of the original query selector.

@returns {String} 
    The normalized query selector.

*/
qs.Query.prototype.toString = function () { 
  if (this.normalized) { 
    return this.normalized;
  } 
  var compounds = this.compounds, selector, i = -1, result = '';
  while ((selector = compounds[++i])) {
    result += (i ? ', ' : '') + selector.join(' ');
  }
  return (this.normalized = result);
};

Usage should look just like jQuery's $ query selector; just use qs instead of $.

Please let me know if I've overlooked something, or if there are further improvements that can be made.

Performance test vs GP libraries

\$\endgroup\$
  • 1
    \$\begingroup\$ It could be that the addition of the succeeding CSS revisions could have made libraries perform more complex parsing and additional filtering. Some libraries also use the native querySelectorAll if supported by the browser, which is a lot slower than your normal "gather and filter" method. Try adding up to CSS3 and check the performance. \$\endgroup\$ – Joseph Apr 24 '13 at 22:23
  • \$\begingroup\$ @JosephtheDreamer the thing is, it shouldn't affect the performance of queries without CSS3 stuff significantly at all due to the design... you'd have alternate versions of qs.compoundToChain and qs.check, and you'd only use them if you found certain symbols in the selector, otherwise the execution path should be pretty much identical, other than one extra if. \$\endgroup\$ – Dagg Apr 24 '13 at 22:24
  • \$\begingroup\$ as for the internal qSA, this does seem to be faster in many cases, which also confuses me. I may add features from CSS2 and beyond, but generally I'm of the mindset that you shouldn't need complex queries like that in a properly designed web app... 99% of the time, class names, ids, and tag names should be enough. \$\endgroup\$ – Dagg Apr 24 '13 at 22:26
5
\$\begingroup\$

My 2 cents,

  • Well commented
  • Naming is never confusing
  • Quite readable

for my edification * why [eval][0]('this') instead of eval('this'), to trick lint?

As far as I can tell, your library is fast because you optimized for the test case. You ought to generate a DOM structure with a thousand elements and query each one ( rendering your cache useless ), will your library still be faster? Most JavaScript authors cache the lookups for efficiency and will not repeat queries unless the DOM changed.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The eval indirection was supposed to be a more linter-friendly version of (1,eval)('this'), but I found out later that some browser got this style of eval indirection wrong. Don't remember which one, may be fixed by now. stackoverflow.com/questions/9642491 \$\endgroup\$ – Dagg Dec 6 '13 at 21:25
  • 1
    \$\begingroup\$ It's not really optimized for the test case in particular, but it is optimized for cases where people use the same selector over and over, reason being, that's the kind of code I see people write a lot. I've tried it with larger documents and even disabling the "command cache," it still outperforms others, but not by ridiculous margins like the ones in this test. \$\endgroup\$ – Dagg Dec 6 '13 at 21:33
  • \$\begingroup\$ Instead of eval('this'), why not Function('return this')()? \$\endgroup\$ – Ismael Miguel Dec 3 '15 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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