/*

* Copyright (C) 2007-2018 Diego Perini
* All rights reserved.
*
* nwmatcher.js - A fast CSS selector engine and matcher
*
* Author: Diego Perini <diego.perini at gmail com>
* Version: 1.4.4
* Created: 20070722
* Release: 20180305
*
* License:
*  http://javascript.nwbox.com/NWMatcher/MIT-LICENSE
* Download:
*  http://javascript.nwbox.com/NWMatcher/nwmatcher.js
*/

(function(global, factory) {

if (typeof module == 'object' && typeof exports == 'object') {
  module.exports = factory;
} else if (typeof define === 'function' && define["amd"]) {
  define(factory);
} else {
  global.NW || (global.NW = { });
  global.NW.Dom = factory(global);
}

})(this, function(global) {

var version = 'nwmatcher-1.4.4',

// processing context & root element
doc = global.document,
root = doc.documentElement,

// save utility methods references
slice = [ ].slice,

// persist previous parsed data
isSingleMatch,
isSingleSelect,

lastSlice,
lastContext,
lastPosition,

lastMatcher,
lastSelector,

lastPartsMatch,
lastPartsSelect,

// accepted prefix identifiers
// (id, class & pseudo-class)
prefixes = '(?:[#.:]|::)?',

// accepted attribute operators
operators = '([~*^$|!]?={1})',

// accepted whitespace characters
whitespace = '[\\x20\\t\\n\\r\\f]',

// 4 combinators F E, F>E, F+E, F~E
combinators = '\\x20|[>+~](?=[^>+~])',

// an+b format params for pseudo-classes
pseudoparms = '(?:[-+]?\\d*n)?[-+]?\\d*',

// skip [ ], ( ), { } brackets groups
skip_groups = '\\[.*\\]|\\(.*\\)|\\{.*\\}',

// any escaped char
any_esc_chr = '\\\\.',
// alpha chars & low dash
alphalodash = '[_a-zA-Z]',
// non-ascii chars (utf-8)
non_asc_chr = '[^\\x00-\\x9f]',
// escape sequences in strings
escaped_chr = '\\\\[^\\n\\r\\f0-9a-fA-F]',
// Unicode chars including trailing whitespace
unicode_chr = '\\\\[0-9a-fA-F]{1,6}(?:\\r\\n|' + whitespace + ')?',

// CSS quoted string values
quotedvalue = '"[^"\\\\]*(?:\\\\.[^"\\\\]*)*"' + "|'[^'\\\\]*(?:\\\\.[^'\\\\]*)*'",

// regular expression used to skip single/nested brackets groups (round, square, curly)
// used to split comma groups excluding commas inside quotes '' "" or brackets () [] {}
reSplitGroup = /([^,\\()[\]]+|\[[^[\]]*\]|\[.*\]|\([^()]+\)|\(.*\)|\{[^{}]+\}|\{.*\}|\\.)+/g,

// regular expression to trim extra leading/trailing whitespace in selector strings
// whitespace is any combination of these 5 character [\x20\t\n\r\f]
// http://www.w3.org/TR/css3-selectors/#selector-syntax
reTrimSpaces = RegExp('[\\n\\r\\f]|^' + whitespace + '+|' + whitespace + '+$', 'g'),

// regular expression used in convertEscapes and unescapeIdentifier
reEscapedChars = /\\([0-9a-fA-F]{1,6}[\x20\t\n\r\f]?|.)|([\x22\x27])/g,

// for in excess whitespace removal
reWhiteSpace = /[\x20\t\n\r\f]+/g,

standardValidator, extendedValidator, reValidator,

attrcheck, attributes, attrmatcher, pseudoclass,

reOptimizeSelector, reSimpleNot, reSplitToken,

Optimize, reClass, reSimpleSelector,

// http://www.w3.org/TR/css3-syntax/#characters
// unicode/ISO 10646 characters \xA0 and higher
// NOTE: Safari 2.0.x crashes with escaped (\\)
// Unicode ranges in regular expressions so we
// use a negated character range class instead
// now assigned at runtime from config options
identifier,

// placeholder for extensions
extensions = '.+',

// precompiled Regular Expressions
Patterns = {
  // structural pseudo-classes and child selectors
  spseudos: /^\:(root|empty|(?:first|last|only)(?:-child|-of-type)|nth(?:-last)?(?:-child|-of-type)\(\s?(even|odd|(?:[-+]{0,1}\d*n\s?)?[-+]{0,1}\s?\d*)\s?\))?(.*)/i,
  // uistates + dynamic + negation pseudo-classes
  dpseudos: /^\:(link|visited|target|active|focus|hover|checked|disabled|enabled|selected|lang\(([-\w]{2,})\)|(?:matches|not)\(\s?(:nth(?:-last)?(?:-child|-of-type)\(\s?(?:even|odd|(?:[-+]{0,1}\d*n\s?)?[-+]{0,1}\s?\d*)\s?\)|[^()]*)\s?\))?(.*)/i,
  // pseudo-elements selectors
  epseudos: /^((?:[:]{1,2}(?:after|before|first-letter|first-line))|(?:[:]{2,2}(?:selection|backdrop|placeholder)))?(.*)/i,
  // E > F
  children: RegExp('^' + whitespace + '?\\>' + whitespace + '?(.*)'),
  // E + F
  adjacent: RegExp('^' + whitespace + '?\\+' + whitespace + '?(.*)'),
  // E ~ F
  relative: RegExp('^' + whitespace + '?\\~' + whitespace + '?(.*)'),
  // E F
  ancestor: RegExp('^' + whitespace + '+(.*)'),
  // all
  universal: RegExp('^\\*(.*)')
},

Tokens = {
  prefixes: prefixes,
  identifier: identifier,
  attributes: attributes
},

/*----------------------------- FEATURE TESTING ----------------------------*/

// detect native methods
isNative = (function() {
  var re = / \w+\(/,
  isnative = String(({ }).toString).replace(re, ' (');
  return function(method) {
    return method && typeof method != 'string' &&
      isnative == String(method).replace(re, ' (');
  };
})(),

// NATIVE_XXXXX true if method exist and is callable
// detect if DOM methods are native in browsers
NATIVE_FOCUS = isNative(doc.hasFocus),
NATIVE_QSAPI = isNative(doc.querySelector),
NATIVE_GEBID = isNative(doc.getElementById),
NATIVE_GEBTN = isNative(root.getElementsByTagName),
NATIVE_GEBCN = isNative(root.getElementsByClassName),

// detect native getAttribute/hasAttribute methods,
// frameworks extend these to elements, but it seems
// this does not work for XML namespaced attributes,
// used to check both getAttribute/hasAttribute in IE
NATIVE_GET_ATTRIBUTE = isNative(root.getAttribute),
NATIVE_HAS_ATTRIBUTE = isNative(root.hasAttribute),

// check if slice() can convert nodelist to array
// see http://yura.thinkweb2.com/cft/
NATIVE_SLICE_PROTO =
  (function() {
    var isBuggy = false;
    try {
      isBuggy = !!slice.call(doc.childNodes, 0)[0];
    } catch(e) { }
    return isBuggy;
  })(),

// supports the new traversal API
NATIVE_TRAVERSAL_API =
  'nextElementSibling' in root && 'previousElementSibling' in root,

// BUGGY_XXXXX true if method is feature tested and has known bugs
// detect buggy gEBID
BUGGY_GEBID = NATIVE_GEBID ?
  (function() {
    var isBuggy = true, x = 'x' + String(+new Date),
      a = doc.createElementNS ? 'a' : '<a name="' + x + '">';
    (a = doc.createElement(a)).name = x;
    root.insertBefore(a, root.firstChild);
    isBuggy = !!doc.getElementById(x);
    root.removeChild(a);
    return isBuggy;
  })() :
  true,

// detect IE gEBTN comment nodes bug
BUGGY_GEBTN = NATIVE_GEBTN ?
  (function() {
    var div = doc.createElement('div');
    div.appendChild(doc.createComment(''));
    return !!div.getElementsByTagName('*')[0];
  })() :
  true,

// detect Opera gEBCN second class and/or UTF8 bugs as well as Safari 3.2
// caching class name results and not detecting when changed,
// tests are based on the jQuery selector test suite
BUGGY_GEBCN = NATIVE_GEBCN ?
  (function() {
    var isBuggy, div = doc.createElement('div'), test = '\u53f0\u5317';

    // Opera tests
    div.appendChild(doc.createElement('span')).
      setAttribute('class', test + 'abc ' + test);
    div.appendChild(doc.createElement('span')).
      setAttribute('class', 'x');

    isBuggy = !div.getElementsByClassName(test)[0];

    // Safari test
    div.lastChild.className = test;
    return isBuggy || div.getElementsByClassName(test).length != 2;
  })() :
  true,

// detect IE bug with dynamic attributes
BUGGY_GET_ATTRIBUTE = NATIVE_GET_ATTRIBUTE ?
  (function() {
    var input = doc.createElement('input');
    input.setAttribute('value', 5);
    return input.defaultValue != 5;
  })() :
  true,

// detect IE bug with non-standard boolean attributes
BUGGY_HAS_ATTRIBUTE = NATIVE_HAS_ATTRIBUTE ?
  (function() {
    var option = doc.createElement('option');
    option.setAttribute('selected', 'selected');
    return !option.hasAttribute('selected');
  })() :
  true,

// detect Safari bug with selected option elements
BUGGY_SELECTED =
  (function() {
    var select = doc.createElement('select');
    select.appendChild(doc.createElement('option'));
    return !select.firstChild.selected;
  })(),

// initialized with the loading context
// and reset for each different context
BUGGY_QUIRKS_GEBCN,
BUGGY_QUIRKS_QSAPI,

QUIRKS_MODE,
XML_DOCUMENT,

// detect Opera browser
OPERA = typeof global.opera != 'undefined' &&
  (/opera/i).test(({ }).toString.call(global.opera)),

// skip simple selector optimizations for Opera >= 11
OPERA_QSAPI = OPERA && parseFloat(global.opera.version()) >= 11,

// check Selector API implementations
RE_BUGGY_QSAPI = NATIVE_QSAPI ?
  (function() {
    var pattern = [ ], context, element,

    expect = function(selector, element, n) {
      var result = false;
      context.appendChild(element);
      try { result = context.querySelectorAll(selector).length == n; } catch(e) { }
      while (context.firstChild) { context.removeChild(context.firstChild); }
      return result;
    };

    // certain bugs can only be detected in standard documents
    // to avoid writing a live loading document create a fake one
    if (doc.implementation && doc.implementation.createDocument) {
      // use a shadow document body as context
      context = doc.implementation.createDocument('', '', null).
        appendChild(doc.createElement('html')).
        appendChild(doc.createElement('head')).parentNode.
        appendChild(doc.createElement('body'));
    } else {
      // use an unattached div node as context
      context = doc.createElement('div');
    }

    // fix for Safari 8.x and other engines that
    // fail querying filtered sibling combinators
    element = doc.createElement('div');
    element.innerHTML = '<p id="a"></p><br>';
    expect('p#a+*', element, 0) &&
      pattern.push('\\w+#\\w+.*[+~]');

    // ^= $= *= operators bugs with empty values (Opera 10 / IE8)
    element = doc.createElement('p');
    element.setAttribute('class', '');
    expect('[class^=""]', element, 1) &&
      pattern.push('[*^$]=[\\x20\\t\\n\\r\\f]*(?:""|' + "'')");

    // :checked bug with option elements (Firefox 3.6.x)
    // it wrongly includes 'selected' options elements
    // HTML5 rules says selected options also match
    element = doc.createElement('option');
    element.setAttribute('selected', 'selected');
    expect(':checked', element, 0) &&
      pattern.push(':checked');

    // :enabled :disabled bugs with hidden fields (Firefox 3.5)
    // http://www.w3.org/TR/html5/links.html#selector-enabled
    // http://www.w3.org/TR/css3-selectors/#enableddisabled
    // not supported by IE8 Query Selector
    element = doc.createElement('input');
    element.setAttribute('type', 'hidden');
    expect(':enabled', element, 0) &&
      pattern.push(':enabled', ':disabled');

    // :link bugs with hyperlinks matching (Firefox/Safari)
    element = doc.createElement('link');
    element.setAttribute('href', 'x');
    expect(':link', element, 1) ||
      pattern.push(':link');

    // avoid attribute selectors for IE QSA
    if (BUGGY_HAS_ATTRIBUTE) {
      // IE fails in reading:
      // - original values for input/textarea
      // - original boolean values for controls
      pattern.push('\\[[\\x20\\t\\n\\r\\f]*(?:checked|disabled|ismap|multiple|readonly|selected|value)');
    }

    return pattern.length ?
      RegExp(pattern.join('|')) :
      { 'test': function() { return false; } };

  })() :
  true,

/*----------------------------- LOOKUP OBJECTS -----------------------------*/

IE_LT_9 = typeof doc.addEventListener != 'function',

LINK_NODES = { 'a': 1, 'A': 1, 'area': 1, 'AREA': 1, 'link': 1, 'LINK': 1 },

// boolean attributes should return attribute name instead of true/false
ATTR_BOOLEAN = {
  'checked': 1, 'disabled': 1, 'ismap': 1,
  'multiple': 1, 'readonly': 1, 'selected': 1
},

// dynamic attributes that needs to be checked against original HTML value
ATTR_DEFAULT = {
  'value': 'defaultValue',
  'checked': 'defaultChecked',
  'selected': 'defaultSelected'
},

// attributes referencing URI data values need special treatment in IE
ATTR_URIDATA = {
  'action': 2, 'cite': 2, 'codebase': 2, 'data': 2, 'href': 2,
  'longdesc': 2, 'lowsrc': 2, 'src': 2, 'usemap': 2
},

// HTML 5 draft specifications
// http://www.whatwg.org/specs/web-apps/current-work/#selectors
HTML_TABLE = {
  // NOTE: class name attribute selectors must always be treated using a
  // case-sensitive match, this has changed from previous specifications
  'accept': 1, 'accept-charset': 1, 'align': 1, 'alink': 1, 'axis': 1,
  'bgcolor': 1, 'charset': 1, 'checked': 1, 'clear': 1, 'codetype': 1, 'color': 1,
  'compact': 1, 'declare': 1, 'defer': 1, 'dir': 1, 'direction': 1, 'disabled': 1,
  'enctype': 1, 'face': 1, 'frame': 1, 'hreflang': 1, 'http-equiv': 1, 'lang': 1,
  'language': 1, 'link': 1, 'media': 1, 'method': 1, 'multiple': 1, 'nohref': 1,
  'noresize': 1, 'noshade': 1, 'nowrap': 1, 'readonly': 1, 'rel': 1, 'rev': 1,
  'rules': 1, 'scope': 1, 'scrolling': 1, 'selected': 1, 'shape': 1, 'target': 1,
  'text': 1, 'type': 1, 'valign': 1, 'valuetype': 1, 'vlink': 1
},

/*-------------------------- REGULAR EXPRESSIONS ---------------------------*/

// placeholder to add functionalities
Selectors = {
  // as a simple example this will check
  // for chars not in standard ascii table
  //
  // 'mySpecialSelector': {
  //  'Expression': /\u0080-\uffff/,
  //  'Callback': mySelectorCallback
  // }
  //
  // 'mySelectorCallback' will be invoked
  // only after passing all other standard
  // checks and only if none of them worked
},

// attribute operators
Operators = {
   '=': "n=='%m'",
  '^=': "n.indexOf('%m')==0",
  '*=': "n.indexOf('%m')>-1",
  '|=': "(n+'-').indexOf('%m-')==0",
  '~=': "(' '+n+' ').indexOf(' %m ')>-1",
  '$=': "n.substr(n.length-'%m'.length)=='%m'"
},

/*------------------------------ UTIL METHODS ------------------------------*/

// concat elements to data
concatList =
  function(data, elements) {
    var i = -1, element;
    if (!data.length && Array.slice)
      return Array.slice(elements);
    while ((element = elements[++i]))
      data[data.length] = element;
    return data;
  },

// concat elements to data and callback
concatCall =
  function(data, elements, callback) {
    var i = -1, element;
    while ((element = elements[++i])) {
      if (false === callback(data[data.length] = element)) { break; }
    }
    return data;
  },

// change context specific variables
switchContext =
  function(from, force) {
    var div, oldDoc = doc;
    // save passed context
    lastContext = from;
    // set new context document
    doc = from.ownerDocument || from;
    if (force || oldDoc !== doc) {
      // set document root
      root = doc.documentElement;
      // set host environment flags
      XML_DOCUMENT = doc.createElement('DiV').nodeName == 'DiV';

      // In quirks mode css class names are case insensitive.
      // In standards mode they are case sensitive. See docs:
      // https://developer.mozilla.org/en/Mozilla_Quirks_Mode_Behavior
      // http://www.whatwg.org/specs/web-apps/current-work/#selectors
      QUIRKS_MODE = !XML_DOCUMENT &&
        typeof doc.compatMode == 'string' ?
        doc.compatMode.indexOf('CSS') < 0 :
        (function() {
          var style = doc.createElement('div').style;
          return style && (style.width = 1) && style.width == '1px';
        })();

      div = doc.createElement('div');
      div.appendChild(doc.createElement('p')).setAttribute('class', 'xXx');
      div.appendChild(doc.createElement('p')).setAttribute('class', 'xxx');

      // GEBCN buggy in quirks mode, match count is:
      // Firefox 3.0+ [xxx = 1, xXx = 1]
      // Opera 10.63+ [xxx = 0, xXx = 2]
      BUGGY_QUIRKS_GEBCN =
        !XML_DOCUMENT && NATIVE_GEBCN && QUIRKS_MODE &&
        (div.getElementsByClassName('xxx').length != 2 ||
        div.getElementsByClassName('xXx').length != 2);

      // QSAPI buggy in quirks mode, match count is:
      // At least Chrome 4+, Firefox 3.5+, Opera 10.x+, Safari 4+ [xxx = 1, xXx = 2]
      // Safari 3.2 QSA doesn't work with mixedcase in quirksmode [xxx = 1, xXx = 0]
      // https://bugs.webkit.org/show_bug.cgi?id=19047
      // must test the attribute selector '[class~=xxx]'
      // before '.xXx' or the bug may not present itself
      BUGGY_QUIRKS_QSAPI =
        !XML_DOCUMENT && NATIVE_QSAPI && QUIRKS_MODE &&
        (div.querySelectorAll('[class~=xxx]').length != 2 ||
        div.querySelectorAll('.xXx').length != 2);

      Config.CACHING && Dom.setCache(true, doc);
    }
  },

// convert single codepoint to UTF-16 encoding
codePointToUTF16 =
  function(codePoint) {
    // out of range, use replacement character
    if (codePoint < 1 || codePoint > 0x10ffff ||
      (codePoint > 0xd7ff && codePoint < 0xe000)) {
      return '\\ufffd';
    }
    // javascript strings are UTF-16 encoded
    if (codePoint < 0x10000) {
      var lowHex = '000' + codePoint.toString(16);
      return '\\u' + lowHex.substr(lowHex.length - 4);
    }
    // supplementary high + low surrogates
    return '\\u' + (((codePoint - 0x10000) >> 0x0a) + 0xd800).toString(16) +
           '\\u' + (((codePoint - 0x10000) % 0x400) + 0xdc00).toString(16);
  },

// convert single codepoint to string
stringFromCodePoint =
  function(codePoint) {
    // out of range, use replacement character
    if (codePoint < 1 || codePoint > 0x10ffff ||
      (codePoint > 0xd7ff && codePoint < 0xe000)) {
      return '\ufffd';
    }
    if (codePoint < 0x10000) {
      return String.fromCharCode(codePoint);
    }
    return String.fromCodePoint ?
      String.fromCodePoint(codePoint) :
      String.fromCharCode(
        ((codePoint - 0x10000) >> 0x0a) + 0xd800,
        ((codePoint - 0x10000) % 0x400) + 0xdc00);
  },

// convert escape sequence in a CSS string or identifier
// to javascript string with javascript escape sequences
convertEscapes =
  function(str) {
    return str.replace(reEscapedChars,
        function(substring, p1, p2) {
          // unescaped " or '
          return p2 ? '\\' + p2 :
            // javascript strings are UTF-16 encoded
            (/^[0-9a-fA-F]/).test(p1) ? codePointToUTF16(parseInt(p1, 16)) :
            // \' \"
            (/^[\\\x22\x27]/).test(p1) ? substring :
            // \g \h \. \# etc
            p1;
        }
      );
  },

// convert escape sequence in a CSS string or identifier
// to javascript string with characters representations
unescapeIdentifier =
  function(str) {
    return str.replace(reEscapedChars,
        function(substring, p1, p2) {
          // unescaped " or '
          return p2 ? p2 :
            // javascript strings are UTF-16 encoded
            (/^[0-9a-fA-F]/).test(p1) ? stringFromCodePoint(parseInt(p1, 16)) :
            // \' \"
            (/^[\\\x22\x27]/).test(p1) ? substring :
            // \g \h \. \# etc
            p1;
        }
      );
  },

/*------------------------------ DOM METHODS -------------------------------*/

// element by id (raw)
// @return reference or null
byIdRaw =
  function(id, elements) {
    var i = -1, element;
    while ((element = elements[++i])) {
      if (element.getAttribute('id') == id) {
        break;
      }
    }
    return element || null;
  },

// element by id
// @return reference or null
_byId = !BUGGY_GEBID ?
  function(id, from) {
    id = (/\\/).test(id) ? unescapeIdentifier(id) : id;
    return from.getElementById && from.getElementById(id) ||
      byIdRaw(id, from.getElementsByTagName('*'));
  } :
  function(id, from) {
    var element = null;
    id = (/\\/).test(id) ? unescapeIdentifier(id) : id;
    if (XML_DOCUMENT || from.nodeType != 9) {
      return byIdRaw(id, from.getElementsByTagName('*'));
    }
    if ((element = from.getElementById(id)) &&
      element.name == id && from.getElementsByName) {
      return byIdRaw(id, from.getElementsByName(id));
    }
    return element;
  },

// publicly exposed byId
// @return reference or null
byId =
  function(id, from) {
    from || (from = doc);
    if (lastContext !== from) { switchContext(from); }
    return _byId(id, from);
  },

// elements by tag (raw)
// @return array
byTagRaw =
  function(tag, from) {
    var any = tag == '*', element = from, elements = [ ], next = element.firstChild;
    any || (tag = tag.toUpperCase());
    while ((element = next)) {
      if (element.tagName > '@' && (any || element.tagName.toUpperCase() == tag)) {
        elements[elements.length] = element;
      }
      if ((next = element.firstChild || element.nextSibling)) continue;
      while (!next && (element = element.parentNode) && element !== from) {
        next = element.nextSibling;
      }
    }
    return elements;
  },

// elements by tag
// @return array
_byTag = !BUGGY_GEBTN && NATIVE_SLICE_PROTO ?
  function(tag, from) {
    return XML_DOCUMENT || from.nodeType == 11 ? byTagRaw(tag, from) :
      slice.call(from.getElementsByTagName(tag), 0);
  } :
  function(tag, from) {
    var i = -1, j = i, data = [ ], element,
      elements = XML_DOCUMENT || from.nodeType == 11 ?
      byTagRaw(tag, from) : from.getElementsByTagName(tag);
    if (tag == '*') {
      while ((element = elements[++i])) {
        if (element.nodeName > '@') {
          data[++j] = element;
        }
      }
    } else {
      while ((element = elements[++i])) {
        data[i] = element;
      }
    }
    return data;
  },

// publicly exposed byTag
// @return array
byTag =
  function(tag, from) {
    from || (from = doc);
    if (lastContext !== from) { switchContext(from); }
    return _byTag(tag, from);
  },

// publicly exposed byName
// @return array
byName =
  function(name, from) {
    return select('[name="' + name.replace(/\\([^\\]{1})/g, '$1') + '"]', from);
  },

// elements by class (raw)
// @return array
byClassRaw =
  function(name, from) {
    var i = -1, j = i, data = [ ], element, elements = _byTag('*', from), n;
    name = ' ' + (QUIRKS_MODE ? name.toLowerCase() : name) + ' ';
    while ((element = elements[++i])) {
      n = XML_DOCUMENT ? element.getAttribute('class') : element.className;
      if (n && n.length && (' ' + (QUIRKS_MODE ? n.toLowerCase() : n).
        replace(reWhiteSpace, ' ') + ' ').indexOf(name) > -1) {
        data[++j] = element;
      }
    }
    return data;
  },

// elements by class
// @return array
_byClass =
  function(name, from) {
    name = QUIRKS_MODE ? name.toLowerCase() : name;
    name = (/\\/).test(name) ? unescapeIdentifier(name) : name;
    return (BUGGY_GEBCN || BUGGY_QUIRKS_GEBCN || XML_DOCUMENT || !from.getElementsByClassName) ?
      byClassRaw(name, from) : slice.call(from.getElementsByClassName(name));
  },

// publicly exposed byClass
// @return array
byClass =
  function(name, from) {
    from || (from = doc);
    if (lastContext !== from) { switchContext(from); }
    return _byClass(name, from);
  },

// check element is descendant of container
// @return boolean
contains = 'compareDocumentPosition' in root ?
  function(container, element) {
    return (container.compareDocumentPosition(element) & 16) == 16;
  } : 'contains' in root ?
  function(container, element) {
    return container !== element && container.contains(element);
  } :
  function(container, element) {
    while ((element = element.parentNode)) {
      if (element === container) return true;
    }
    return false;
  },

// attribute value
// @return string
getAttribute = !BUGGY_GET_ATTRIBUTE && !IE_LT_9 ?
  function(node, attribute) {
    return node.getAttribute(attribute);
  } :
  function(node, attribute) {
    attribute = attribute.toLowerCase();
    if (typeof node[attribute] == 'object') {
      return node.attributes[attribute] &&
        node.attributes[attribute].value;
    }
    return (
      // 'type' can only be read by using native getAttribute
      attribute == 'type' ? node.getAttribute(attribute) :
      // specific URI data attributes (parameter 2 to fix IE bug)
      ATTR_URIDATA[attribute] ? node.getAttribute(attribute, 2) :
      // boolean attributes should return name instead of true/false
      ATTR_BOOLEAN[attribute] ? node.getAttribute(attribute) ? attribute : 'false' :
        (node = node.getAttributeNode(attribute)) && node.value);
  },

// attribute presence
// @return boolean
hasAttribute = !BUGGY_HAS_ATTRIBUTE && !IE_LT_9 ?
  function(node, attribute) {
    return XML_DOCUMENT ?
      !!node.getAttribute(attribute) :
      node.hasAttribute(attribute);
  } :
  function(node, attribute) {
    // read the node attribute object
    var obj = node.getAttributeNode(attribute = attribute.toLowerCase());
    return ATTR_DEFAULT[attribute] && attribute != 'value' ?
      node[ATTR_DEFAULT[attribute]] : obj && obj.specified;
  },

// check node emptyness
// @return boolean
isEmpty =
  function(node) {
    node = node.firstChild;
    while (node) {
      if (node.nodeType == 3 || node.nodeName > '@') return false;
      node = node.nextSibling;
    }
    return true;
  },

// check if element matches the :link pseudo
// @return boolean
isLink =
  function(element) {
    return hasAttribute(element,'href') && LINK_NODES[element.nodeName];
  },

// child position by nodeType
// @return number
nthElement =
  function(element, last) {
    var count = 1, succ = last ? 'nextSibling' : 'previousSibling';
    while ((element = element[succ])) {
      if (element.nodeName > '@') ++count;
    }
    return count;
  },

// child position by nodeName
// @return number
nthOfType =
  function(element, last) {
    var count = 1, succ = last ? 'nextSibling' : 'previousSibling', type = element.nodeName;
    while ((element = element[succ])) {
      if (element.nodeName == type) ++count;
    }
    return count;
  },

/*------------------------------- DEBUGGING --------------------------------*/

// get/set (string/object) working modes
configure =
  function(option) {
    if (typeof option == 'string') { return !!Config[option]; }
    if (typeof option != 'object') { return Config; }
    for (var i in option) {
      Config[i] = !!option[i];
      if (i == 'SIMPLENOT') {
        matchContexts = { };
        matchResolvers = { };
        selectContexts = { };
        selectResolvers = { };
        if (!Config[i]) { Config['USE_QSAPI'] = false; }
      } else if (i == 'USE_QSAPI') {
        Config[i] = !!option[i] && NATIVE_QSAPI;
      }
    }
    setIdentifierSyntax();
    reValidator = RegExp(Config.SIMPLENOT ?
      standardValidator : extendedValidator);
    return true;
  },

// control user notifications
emit =
  function(message) {
    if (Config.VERBOSITY) { throw Error(message); }
    if (Config.LOGERRORS && console && console.log) {
      console.log(message);
    }
  },

Config = {

  // true to enable caching of result sets, false to disable
  CACHING: false,

  // true to allow CSS escaped identifiers, false to disallow
  ESCAPECHR: true,

  // true to allow identifiers containing non-ASCII (utf-8) chars
  NON_ASCII: true,

  // switch syntax RE, true to use Level 3, false to use Level 2
  SELECTOR3: true,

  // true to allow identifiers containing Unicode (utf-16) chars
  UNICODE16: true,

  // by default do not add missing left/right context
  // to mangled selector strings like "+div" or "ul>"
  // callable Dom.shortcuts method has to be available
  SHORTCUTS: false,

  // true to disable complex selectors nested in
  // ':not()' pseudo-classes as for specifications
  SIMPLENOT: true,

  // true to match lowercase tag names of SVG elements in HTML
  SVG_LCASE: false,

  // strict QSA match all non-unique IDs (false)
  // speed & libs compat match unique ID (true)
  UNIQUE_ID: true,

  // true to follow HTML5 specs handling of ":checked"
  // pseudo-class and similar UI states (indeterminate)
  USE_HTML5: true,

  // true to use browsers native Query Selector API if available
  USE_QSAPI: NATIVE_QSAPI,

  // true to throw exceptions, false to skip throwing exceptions
  VERBOSITY: true,

  // true to print console errors or warnings, false to mute them
  LOGERRORS: true

},

/*---------------------------- COMPILER METHODS ----------------------------*/

// init REs and context
initialize =
  function(doc) {
    setIdentifierSyntax();
    switchContext(doc, true);
  },

// set/reset default identifier syntax
// based on user configuration options
// rebuild the validator and other REs
setIdentifierSyntax =
  function() {

    var syntax = '', start = Config['SELECTOR3'] ? '-{2}|' : '';

    Config['NON_ASCII'] && (syntax += '|' + non_asc_chr);
    Config['UNICODE16'] && (syntax += '|' + unicode_chr);
    Config['ESCAPECHR'] && (syntax += '|' + escaped_chr);

    syntax += (Config['UNICODE16'] || Config['ESCAPECHR']) ? '' : '|' + any_esc_chr;

    identifier = '-?(?:' + start + alphalodash + syntax + ')(?:-|[0-9]|' + alphalodash + syntax + ')*';

    // build attribute string
    attrcheck = '(' + quotedvalue + '|' + identifier + ')';
    attributes = whitespace + '*(' + identifier + '(?::' + identifier + ')?)' +
      whitespace + '*(?:' + operators + whitespace + '*' + attrcheck + ')?' + whitespace + '*' + '(i)?' + whitespace + '*';
    attrmatcher = attributes.replace(attrcheck, '([\\x22\\x27]*)((?:\\\\?.)*?)\\3');

    // build pseudoclass string
    pseudoclass = '((?:' +
      // an+b parameters or quoted string
      pseudoparms + '|' + quotedvalue + '|' +
      // id, class, pseudo-class selector
      prefixes + identifier + '|' +
      // nested HTML attribute selector
      '\\[' + attributes + '\\]|' +
      // nested pseudo-class selector
      '\\(.+\\)|' + whitespace + '*|' +
      // nested pseudos/separators
      ',)+)';

    // CSS3: syntax scanner and
    // one pass validation only
    // using regular expression
    standardValidator =
      // discard start
      '(?=[\\x20\\t\\n\\r\\f]*[^>+~(){}<>])' +
      // open match group
      '(' +
      //universal selector
      '\\*' +
      // id/class/tag/pseudo-class identifier
      '|(?:' + prefixes + identifier + ')' +
      // combinator selector
      '|' + combinators +
      // HTML attribute selector
      '|\\[' + attributes + '\\]' +
      // pseudo-classes parameters
      '|\\(' + pseudoclass + '\\)' +
      // dom properties selector (extension)
      '|\\{' + extensions + '\\}' +
      // selector group separator (comma)
      '|(?:,|' + whitespace + '*)' +
      // close match group
      ')+';

    // only allow simple selectors nested in ':not()' pseudo-classes
    reSimpleNot = RegExp('^(' +
      '(?!:not)' +
      '(' + prefixes + identifier +
      '|\\([^()]*\\))+' +
      '|\\[' + attributes + '\\]' +
      ')$');

    // split last, right most, selector group token
    reSplitToken = RegExp('(' +
      prefixes + identifier + '|' +
      '\\[' + attributes + '\\]|' +
      '\\(' + pseudoclass + '\\)|' +
      '\\\\.|[^\\x20\\t\\n\\r\\f>+~])+', 'g');

    reOptimizeSelector = RegExp(identifier + '|^$');

    reSimpleSelector = RegExp(
      BUGGY_GEBTN && BUGGY_GEBCN || OPERA ?
        '^#?' + identifier + '$' : BUGGY_GEBTN ?
        '^[.#]?' + identifier + '$' : BUGGY_GEBCN ?
        '^(?:\\*|#' + identifier + ')$' :
        '^(?:\\*|[.#]?' + identifier + ')$');

    // matches class selectors
    reClass = RegExp('(?:\\[[\\x20\\t\\n\\r\\f]*class\\b|\\.' + identifier + ')');

    Optimize = {
      ID: RegExp('^\\*?#(' + identifier + ')|' + skip_groups),
      TAG: RegExp('^(' + identifier + ')|' + skip_groups),
      CLASS: RegExp('^\\.(' + identifier + '$)|' + skip_groups)
    };

    Patterns.id = RegExp('^#(' + identifier + ')(.*)');
    Patterns.tagName = RegExp('^(' + identifier + ')(.*)');
    Patterns.className = RegExp('^\\.(' + identifier + ')(.*)');
    Patterns.attribute = RegExp('^\\[' + attrmatcher + '\\](.*)');

    Tokens.identifier = identifier;
    Tokens.attributes = attributes;

    // validator for complex selectors in ':not()' pseudo-classes
    extendedValidator = standardValidator.replace(pseudoclass, '.*');

    // validator for standard selectors as default
    reValidator = RegExp(standardValidator);
  },

// code string reused to build compiled functions
ACCEPT_NODE = 'r[r.length]=c[k];if(f&&false===f(c[k]))break main;else continue main;',

// compile a comma separated group of selector
// @mode boolean true for select, false for match
// return a compiled function
compile =
  function(selector, source, mode) {

    var parts = typeof selector == 'string' ? selector.match(reSplitGroup) : selector;

    // ensures that source is a string
    typeof source == 'string' || (source = '');

    if (parts.length == 1) {
      source += compileSelector(parts[0], mode ? ACCEPT_NODE : 'f&&f(k);return true;', mode);
    } else {
      // for each selector in the group
      var i = -1, seen = { }, token;
      while ((token = parts[++i])) {
        token = token.replace(reTrimSpaces, '');
        // avoid repeating the same token
        // in comma separated group (p, p)
        if (!seen[token] && (seen[token] = true)) {
          source += compileSelector(token, mode ? ACCEPT_NODE : 'f&&f(k);return true;', mode);
        }
      }
    }

    if (mode) {
      // for select method
      return Function('c,s,d,h,g,f',
        'var N,n,x=0,k=-1,e,r=[];main:while((e=c[++k])){' + source + '}return r;');
    } else {
      // for match method
      return Function('e,s,d,h,g,f',
        'var N,n,x=0,k=e;' + source + 'return false;');
    }
  },

// compile a CSS3 string selector into ad-hoc javascript matching function
// @return string (to be compiled)
compileSelector =
  function(selector, source, mode) {

    var a, b, n, k = 0, expr, match, result, status, test, type;

    while (selector) {

      k++;

      // *** Universal selector
      // * match all (empty block, do not remove)
      if ((match = selector.match(Patterns.universal))) {
        // do nothing, handled in the compiler where
        // BUGGY_GEBTN return comment nodes (ex: IE)
        expr = '';
      }

      // *** ID selector
      // #Foo Id case sensitive
      else if ((match = selector.match(Patterns.id))) {
        // document can contain conflicting elements (id/name)
        // prototype selector unit need this method to recover bad HTML forms
        match[1] = (/\\/).test(match[1]) ? convertEscapes(match[1]) : match[1];
        source = 'if(' + (XML_DOCUMENT ?
          's.getAttribute(e,"id")' :
          '(e.submit?s.getAttribute(e,"id"):e.id)') +
          '=="' + match[1] + '"' +
          '){' + source + '}';
      }

      // *** Type selector
      // Foo Tag (case insensitive)
      else if ((match = selector.match(Patterns.tagName))) {
        // both tagName and nodeName properties may be upper/lower case
        // depending on their creation NAMESPACE in createElementNS()
        test = Config.SVG_LCASE ? '||e.nodeName=="' + match[1].toLowerCase() + '"' : '';
        source = 'if(e.nodeName' + (XML_DOCUMENT ?
          '=="' + match[1] + '"' : '.toUpperCase()' +
          '=="' + match[1].toUpperCase() + '"' + test) +
          '){' + source + '}';
      }

      // *** Class selector
      // .Foo Class (case sensitive)
      else if ((match = selector.match(Patterns.className))) {
        // W3C CSS3 specs: element whose "class" attribute has been assigned a
        // list of whitespace-separated values, see section 6.4 Class selectors
        // and notes at the bottom; explicitly non-normative in this specification.
        match[1] = (/\\/).test(match[1]) ? convertEscapes(match[1]) : match[1];
        match[1] = QUIRKS_MODE ? match[1].toLowerCase() : match[1];
        source = 'if((n=' + (XML_DOCUMENT ?
          's.getAttribute(e,"class")' : 'e.className') +
          ')&&n.length&&(" "+' + (QUIRKS_MODE ? 'n.toLowerCase()' : 'n') +
          '.replace(/' + whitespace + '+/g," ")+" ").indexOf(" ' + match[1] + ' ")>-1' +
          '){' + source + '}';
      }

      // *** Attribute selector
      // [attr] [attr=value] [attr="value"] [attr='value'] and !=, *=, ~=, |=, ^=, $=
      // case sensitivity is treated differently depending on the document type (see map)
      else if ((match = selector.match(Patterns.attribute))) {

        // xml namespaced attribute ?
        expr = match[1].split(':');
        expr = expr.length == 2 ? expr[1] : expr[0] + '';

        if (match[2] && !Operators[match[2]]) {
          emit('Unsupported operator in attribute selectors "' + selector + '"');
          return '';
        }

        test = 'false';

        // replace Operators parameter if needed
        if (match[2] && match[4] && (test = Operators[match[2]])) {
          match[4] = (/\\/).test(match[4]) ? convertEscapes(match[4]) : match[4];
          // case treatment depends on document type
          type = match[5] == 'i' || HTML_TABLE[expr.toLowerCase()];
          test = test.replace(/\%m/g, type ? match[4].toLowerCase() : match[4]);
        } else if (match[2] == '!=' || match[2] == '=') {
          test = 'n' + match[2] + '=""';
        }

        source = 'if(n=s.hasAttribute(e,"' + match[1] + '")){' +
          (match[2] ? 'n=s.getAttribute(e,"' + match[1] + '")' : '') +
          (type && match[2] ? '.toLowerCase();' : ';') +
          'if(' + (match[2] ? test : 'n') + '){' + source + '}}';

      }

      // *** Adjacent sibling combinator
      // E + F (F adiacent sibling of E)
      else if ((match = selector.match(Patterns.adjacent))) {
        source = NATIVE_TRAVERSAL_API ?
          'var N' + k + '=e;if((e=e.previousElementSibling)){' + source + '}e=N' + k + ';' :
          'var N' + k + '=e;while((e=e.previousSibling)){if(e.nodeType==1){' + source + 'break;}}e=N' + k + ';';
      }

      // *** General sibling combinator
      // E ~ F (F relative sibling of E)
      else if ((match = selector.match(Patterns.relative))) {
        source = NATIVE_TRAVERSAL_API ?
          'var N' + k + '=e;while((e=e.previousElementSibling)){' + source + '}e=N' + k + ';' :
          'var N' + k + '=e;while((e=e.previousSibling)){if(e.nodeType==1){' + source + '}}e=N' + k + ';';
      }

      // *** Child combinator
      // E > F (F children of E)
      else if ((match = selector.match(Patterns.children))) {
        source = 'var N' + k + '=e;if((e=e.parentNode)&&e.nodeType==1){' + source + '}e=N' + k + ';';
      }

      // *** Descendant combinator
      // E F (E ancestor of F)
      else if ((match = selector.match(Patterns.ancestor))) {
        source = 'var N' + k + '=e;while((e=e.parentNode)&&e.nodeType==1){' + source + '}e=N' + k + ';';
      }

      // *** Structural pseudo-classes
      // :root, :empty,
      // :first-child, :last-child, :only-child,
      // :first-of-type, :last-of-type, :only-of-type,
      // :nth-child(), :nth-last-child(), :nth-of-type(), :nth-last-of-type()
      else if ((match = selector.match(Patterns.spseudos)) && match[1]) {

        switch (match[1]) {
          case 'root':
            // element root of the document
            if (match[3]) {
              source = 'if(e===h||s.contains(h,e)){' + source + '}';
            } else {
              source = 'if(e===h){' + source + '}';
            }
            break;

          case 'empty':
            // element that has no children
            source = 'if(s.isEmpty(e)){' + source + '}';
            break;

          default:
            if (match[1] && match[2]) {
              if (match[2] == 'n') {
                source = 'if(e!==h){' + source + '}';
                break;
              } else if (match[2] == 'even') {
                a = 2;
                b = 0;
              } else if (match[2] == 'odd') {
                a = 2;
                b = 1;
              } else {
                // assumes correct "an+b" format, "b" before "a" to keep "n" values
                b = ((n = match[2].match(/(-?\d+)$/)) ? parseInt(n[1], 10) : 0);
                a = ((n = match[2].match(/(-?\d*)n/i)) ? parseInt(n[1], 10) : 0);
                if (n && n[1] == '-') a = -1;
              }

              // build test expression out of structural pseudo (an+b) parameters
              // see here: http://www.w3.org/TR/css3-selectors/#nth-child-pseudo
              test = a > 1 ?
                (/last/i.test(match[1])) ? '(n-(' + b + '))%' + a + '==0' :
                'n>=' + b + '&&(n-(' + b + '))%' + a + '==0' : a < -1 ?
                (/last/i.test(match[1])) ? '(n-(' + b + '))%' + a + '==0' :
                'n<=' + b + '&&(n-(' + b + '))%' + a + '==0' : a === 0 ?
                'n==' + b : a == -1 ? 'n<=' + b : 'n>=' + b;

              // 4 cases: 1 (nth) x 4 (child, of-type, last-child, last-of-type)
              source =
                'if(e!==h){' +
                  'n=s[' + (/-of-type/i.test(match[1]) ? '"nthOfType"' : '"nthElement"') + ']' +
                    '(e,' + (/last/i.test(match[1]) ? 'true' : 'false') + ');' +
                  'if(' + test + '){' + source + '}' +
                '}';

            } else {
              // 6 cases: 3 (first, last, only) x 1 (child) x 2 (-of-type)
              a = /first/i.test(match[1]) ? 'previous' : 'next';
              n = /only/i.test(match[1]) ? 'previous' : 'next';
              b = /first|last/i.test(match[1]);

              type = /-of-type/i.test(match[1]) ? '&&n.nodeName!=e.nodeName' : '&&n.nodeName<"@"';

              source = 'if(e!==h){' +
                ( 'n=e;while((n=n.' + a + 'Sibling)' + type + ');if(!n){' + (b ? source :
                  'n=e;while((n=n.' + n + 'Sibling)' + type + ');if(!n){' + source + '}') + '}' ) + '}';
            }
            break;
        }

      }

      // *** negation, user action and target pseudo-classes
      // *** UI element states and dynamic pseudo-classes
      // CSS4 :matches 
      // CSS3 :not, :checked, :enabled, :disabled, :target
      // CSS3 :active, :hover, :focus
      // CSS3 :link, :visited
      else if ((match = selector.match(Patterns.dpseudos)) && match[1]) {

        switch (match[1].match(/^\w+/)[0]) {
          // CSS4 matches pseudo-class
          case 'matches':
            expr = match[3].replace(reTrimSpaces, '');
            source = 'if(s.match(e, "' + expr.replace(/\x22/g, '\\"') + '",g)){' + source +'}';
            break;

          // CSS3 negation pseudo-class
          case 'not':
            // compile nested selectors, DO NOT pass the callback parameter
            // SIMPLENOT allow disabling complex selectors nested
            // in ':not()' pseudo-classes, breaks some test units
            expr = match[3].replace(reTrimSpaces, '');

            if (Config.SIMPLENOT && !reSimpleNot.test(expr)) {
              // see above, log error but continue execution
              emit('Negation pseudo-class only accepts simple selectors "' + selector + '"');
              return '';
            } else {
              if ('compatMode' in doc) {
                source = 'if(!' + compile(expr, '', false) + '(e,s,d,h,g)){' + source + '}';
              } else {
                source = 'if(!s.match(e, "' + expr.replace(/\x22/g, '\\"') + '",g)){' + source +'}';
              }
            }
            break;

          // CSS3 UI element states
          case 'checked':
            // for radio buttons checkboxes (HTML4) and options (HTML5)
            source = 'if((typeof e.form!=="undefined"&&(/^(?:radio|checkbox)$/i).test(e.type)&&e.checked)' +
              (Config.USE_HTML5 ? '||(/^option$/i.test(e.nodeName)&&(e.selected||e.checked))' : '') +
              '){' + source + '}';
            break;
          case 'disabled':
            // does not consider hidden input fields
            source = 'if(((typeof e.form!=="undefined"' +
              (Config.USE_HTML5 ? '' : '&&!(/^hidden$/i).test(e.type)') +
              ')||s.isLink(e))&&e.disabled===true){' + source + '}';
            break;
          case 'enabled':
            // does not consider hidden input fields
            source = 'if(((typeof e.form!=="undefined"' +
              (Config.USE_HTML5 ? '' : '&&!(/^hidden$/i).test(e.type)') +
              ')||s.isLink(e))&&e.disabled===false){' + source + '}';
            break;

          // CSS3 lang pseudo-class
          case 'lang':
            test = '';
            if (match[2]) test = match[2].substr(0, 2) + '-';
            source = 'do{(n=e.lang||"").toLowerCase();' +
              'if((n==""&&h.lang=="' + match[2].toLowerCase() + '")||' +
              '(n&&(n=="' + match[2].toLowerCase() +
              '"||n.substr(0,3)=="' + test.toLowerCase() + '")))' +
              '{' + source + 'break;}}while((e=e.parentNode)&&e!==g);';
            break;

          // CSS3 target pseudo-class
          case 'target':
            source = 'if(e.id==d.location.hash.slice(1)){' + source + '}';
            break;

          // CSS3 dynamic pseudo-classes
          case 'link':
            source = 'if(s.isLink(e)&&!e.visited){' + source + '}';
            break;
          case 'visited':
            source = 'if(s.isLink(e)&&e.visited){' + source + '}';
            break;

          // CSS3 user action pseudo-classes IE & FF3 have native support
          // these capabilities may be emulated by some event managers
          case 'active':
            if (XML_DOCUMENT) break;
            source = 'if(e===d.activeElement){' + source + '}';
            break;
          case 'hover':
            if (XML_DOCUMENT) break;
            source = 'if(e===d.hoverElement){' + source + '}';
            break;
          case 'focus':
            if (XML_DOCUMENT) break;
            source = NATIVE_FOCUS ?
              'if(e===d.activeElement&&d.hasFocus()&&(e.type||e.href||typeof e.tabIndex=="number")){' + source + '}' :
              'if(e===d.activeElement&&(e.type||e.href)){' + source + '}';
            break;

          // CSS2 selected pseudo-classes, not part of current CSS3 drafts
          // the 'selected' property is only available for option elements
          case 'selected':
            // fix Safari selectedIndex property bug
            expr = BUGGY_SELECTED ? '||(n=e.parentNode)&&n.options[n.selectedIndex]===e' : '';
            source = 'if(/^option$/i.test(e.nodeName)&&(e.selected||e.checked' + expr + ')){' + source + '}';
            break;

          default:
            break;
        }

      }

      else if ((match = selector.match(Patterns.epseudos)) && match[1]) {
        source = 'if(!(/1|11/).test(e.nodeType)){' + source + '}';
      }

      else {

        // this is where external extensions are
        // invoked if expressions match selectors
        expr = false;
        status = false;
        for (expr in Selectors) {
          if ((match = selector.match(Selectors[expr].Expression)) && match[1]) {
            result = Selectors[expr].Callback(match, source);
            if ('match' in result) { match = result.match; }
            source = result.source;
            status = result.status;
            if (status) { break; }
          }
        }

        // if an extension fails to parse the selector
        // it must return a false boolean in "status"
        if (!status) {
          // log error but continue execution, don't throw real exceptions
          // because blocking following processes maybe is not a good idea
          emit('Unknown pseudo-class selector "' + selector + '"');
          return '';
        }

        if (!expr) {
          // see above, log error but continue execution
          emit('Unknown token in selector "' + selector + '"');
          return '';
        }

      }

      // error if no matches found by the pattern scan
      if (!match) {
        emit('Invalid syntax in selector "' + selector + '"');
        return '';
      }

      // ensure "match" is not null or empty since
      // we do not throw real DOMExceptions above
      selector = match && match[match.length - 1];
    }

    return source;
  },

/*----------------------------- QUERY METHODS ------------------------------*/

// match element with selector
// @return boolean
match =
  function(element, selector, from, callback) {

    var parts;

    if (!(element && element.nodeType == 1)) {
      emit('Invalid element argument');
      return false;
    } else if (typeof selector != 'string') {
      emit('Invalid selector argument');
      return false;
    } else if (from && from.nodeType == 1 && !contains(from, element)) {
      return false;
    } else if (lastContext !== from) {
      // reset context data when it changes
      // and ensure context is set to a default
      switchContext(from || (from = element.ownerDocument));
    }

    // normalize the selector string, remove [\n\r\f]
    // whitespace, replace codepoints 0 with '\ufffd'
    // trim non-relevant leading/trailing whitespaces
    selector = selector.
      replace(reTrimSpaces, '').
      replace(/\x00|\\$/g, '\ufffd');

    Config.SHORTCUTS && (selector = Dom.shortcuts(selector, element, from));

    if (lastMatcher != selector) {
      // process valid selector strings
      if ((parts = selector.match(reValidator)) && parts[0] == selector) {
        isSingleMatch = (parts = selector.match(reSplitGroup)).length < 2;
        // save passed selector
        lastMatcher = selector;
        lastPartsMatch = parts;
      } else {
        emit('The string "' + selector + '", is not a valid CSS selector');
        return false;
      }
    } else parts = lastPartsMatch;

    // compile matcher resolvers if necessary
    if (!matchResolvers[selector] || matchContexts[selector] !== from) {
      matchResolvers[selector] = compile(isSingleMatch ? [selector] : parts, '', false);
      matchContexts[selector] = from;
    }

    return matchResolvers[selector](element, Snapshot, doc, root, from, callback);
  },

// select only the first element
// matching selector (document ordered)
first =
  function(selector, from) {
    return select(selector, from, function() { return false; })[0] || null;
  },

// select elements matching selector
// using new Query Selector API
// or cross-browser client API
// @return array
select =
  function(selector, from, callback) {

    var i, changed, element, elements, parts, token, original = selector;

    if (arguments.length === 0) {
      emit('Not enough arguments');
      return [ ];
    } else if (typeof selector != 'string') {
      return [ ];
    } else if (from && !(/1|9|11/).test(from.nodeType)) {
      emit('Invalid or illegal context element');
      return [ ];
    } else if (lastContext !== from) {
      // reset context data when it changes
      // and ensure context is set to a default
      switchContext(from || (from = doc));
    }

    if (Config.CACHING && (elements = Dom.loadResults(original, from, doc, root))) {
      return callback ? concatCall([ ], elements, callback) : elements;
    }

    // normalize the selector string, remove [\n\r\f]
    // whitespace, replace codepoints 0 with '\ufffd'
    // trim non-relevant leading/trailing whitespaces
    selector = selector.
      replace(reTrimSpaces, '').
      replace(/\x00|\\$/g, '\ufffd');

    if (!OPERA_QSAPI && reSimpleSelector.test(selector)) {
      switch (selector.charAt(0)) {
        case '#':
          if (Config.UNIQUE_ID) {
            elements = (element = _byId(selector.slice(1), from)) ? [ element ] : [ ];
          }
          break;
        case '.':
          elements = _byClass(selector.slice(1), from);
          break;
        default:
          elements = _byTag(selector, from);
          break;
      }
    }

    else if (!XML_DOCUMENT && Config.USE_QSAPI &&
      !(BUGGY_QUIRKS_QSAPI && reClass.test(selector)) &&
      !RE_BUGGY_QSAPI.test(selector)) {
      try {
        elements = from.querySelectorAll(selector);
      } catch(e) { }
    }

    if (elements) {
      elements = callback ? concatCall([ ], elements, callback) :
        NATIVE_SLICE_PROTO ? slice.call(elements) : concatList([ ], elements);
      Config.CACHING && Dom.saveResults(original, from, doc, elements);
      return elements;
    }

    Config.SHORTCUTS && (selector = Dom.shortcuts(selector, from));

    if ((changed = lastSelector != selector)) {
      // process valid selector strings
      if ((parts = selector.match(reValidator)) && parts[0] == selector) {
        isSingleSelect = (parts = selector.match(reSplitGroup)).length < 2;
        // save passed selector
        lastSelector = selector;
        lastPartsSelect = parts;
      } else {
        emit('The string "' + selector + '", is not a valid CSS selector');
        return [ ];
      }
    } else parts = lastPartsSelect;

    // commas separators are treated sequentially to maintain order
    if (from.nodeType == 11) {

      elements = byTagRaw('*', from);

    } else if (!XML_DOCUMENT && isSingleSelect) {

      if (changed) {
        // get right most selector token
        parts = selector.match(reSplitToken);
        token = parts[parts.length - 1];

        // only last slice before :not rules
        lastSlice = token.split(':not');
        lastSlice = lastSlice[lastSlice.length - 1];

        // position where token was found
        lastPosition = selector.length - token.length;
      }

      // ID optimization RTL, to reduce number of elements to visit
      if (Config.UNIQUE_ID && lastSlice && (parts = lastSlice.match(Optimize.ID)) && (token = parts[1])) {
        if ((element = _byId(token, from))) {
          if (match(element, selector)) {
            callback && callback(element);
            elements = [element];
          } else elements = [ ];
        }
      }

      // ID optimization LTR, to reduce selection context searches
      else if (Config.UNIQUE_ID && (parts = selector.match(Optimize.ID)) && (token = parts[1])) {
        if ((element = _byId(token, doc))) {
          if ('#' + token == selector) {
            callback && callback(element);
            elements = [element];
          } else if (/[>+~]/.test(selector)) {
            from = element.parentNode;
          } else {
            from = element;
          }
        } else elements = [ ];
      }

      if (elements) {
        Config.CACHING && Dom.saveResults(original, from, doc, elements);
        return elements;
      }

      if (!NATIVE_GEBCN && lastSlice && (parts = lastSlice.match(Optimize.TAG)) && (token = parts[1])) {
        if ((elements = _byTag(token, from)).length === 0) { return [ ]; }
        selector = selector.slice(0, lastPosition) + selector.slice(lastPosition).replace(token, '*');
      }

      else if (lastSlice && (parts = lastSlice.match(Optimize.CLASS)) && (token = parts[1])) {
        if ((elements = _byClass(token, from)).length === 0) { return [ ]; }
        selector = selector.slice(0, lastPosition) + selector.slice(lastPosition).replace('.' + token,
          reOptimizeSelector.test(selector.charAt(selector.indexOf(token) - 1)) ? '' : '*');
      }

      else if ((parts = selector.match(Optimize.CLASS)) && (token = parts[1])) {
        if ((elements = _byClass(token, from)).length === 0) { return [ ]; }
        for (i = 0, els = [ ]; elements.length > i; ++i) {
          els = concatList(els, elements[i].getElementsByTagName('*'));
        }
        elements = els;
        selector = selector.slice(0, lastPosition) + selector.slice(lastPosition).replace('.' + token,
          reOptimizeSelector.test(selector.charAt(selector.indexOf(token) - 1)) ? '' : '*');
      }

      else if (NATIVE_GEBCN && lastSlice && (parts = lastSlice.match(Optimize.TAG)) && (token = parts[1])) {
        if ((elements = _byTag(token, from)).length === 0) { return [ ]; }
        selector = selector.slice(0, lastPosition) + selector.slice(lastPosition).replace(token, '*');
      }

    }

    if (!elements) {
      if (IE_LT_9) {
        elements = /^(?:applet|object)$/i.test(from.nodeName) ? from.children : byTagRaw('*', from);
      } else {
        elements = from.getElementsByTagName('*');
      }
    }
    // end of prefiltering pass

    // compile selector resolver if necessary
    if (!selectResolvers[selector] || selectContexts[selector] !== from) {
      selectResolvers[selector] = compile(isSingleSelect ? [selector] : parts, '', true);
      selectContexts[selector] = from;
    }

    elements = selectResolvers[selector](elements, Snapshot, doc, root, from, callback);

    Config.CACHING && Dom.saveResults(original, from, doc, elements);

    return elements;
  },

/*-------------------------------- STORAGE ---------------------------------*/

// empty function handler
FN = function(x) { return x; },

// compiled match functions returning booleans
matchContexts = { },
matchResolvers = { },

// compiled select functions returning collections
selectContexts = { },
selectResolvers = { },

// used to pass methods to compiled functions
Snapshot = {

  // element indexing methods
  nthElement: nthElement,
  nthOfType: nthOfType,

  // element inspection methods
  getAttribute: getAttribute,
  hasAttribute: hasAttribute,

  // element selection methods
  byClass: _byClass,
  byName: byName,
  byTag: _byTag,
  byId: _byId,

  // helper/check methods
  contains: contains,
  isEmpty: isEmpty,
  isLink: isLink,

  // selection/matching
  select: select,
  match: match
},

/*------------------------------- PUBLIC API -------------------------------*/

// code referenced by extensions
Dom = {

  ACCEPT_NODE: ACCEPT_NODE,

  // retrieve element by id attr
  byId: byId,

  // retrieve elements by tag name
  byTag: byTag,

  // retrieve elements by name attr
  byName: byName,

  // retrieve elements by class name
  byClass: byClass,

  // read the value of the attribute
  // as was in the original HTML code
  getAttribute: getAttribute,

  // check for the attribute presence
  // as was in the original HTML code
  hasAttribute: hasAttribute,

  // element match selector, return boolean true/false
  match: match,

  // first element match only, return element or null
  first: first,

  // elements matching selector, starting from element
  select: select,

  // compile selector into ad-hoc javascript resolver
  compile: compile,

  // check that two elements are ancestor/descendant
  contains: contains,

  // handle selector engine configuration settings
  configure: configure,

  // initialize caching for each document
  setCache: FN,

  // load previously collected result set
  loadResults: FN,

  // save previously collected result set
  saveResults: FN,

  // handle missing context in selector strings
  shortcuts: FN,

  // log resolvers errors/warnings
  emit: emit,

  // options enabing specific engine functionality
  Config: Config,

  // pass methods references to compiled resolvers
  Snapshot: Snapshot,

  // operators descriptor
  // for attribute operators extensions
  Operators: Operators,

  // selectors descriptor
  // for pseudo-class selectors extensions
  Selectors: Selectors,

  // export validators REs
  Tokens: Tokens,

  // export version string
  Version: version,

  // add or overwrite user defined operators
  registerOperator:
    function(symbol, resolver) {
      Operators[symbol] || (Operators[symbol] = resolver);
    },

  // add selector patterns for user defined callbacks
  registerSelector:
    function(name, rexp, func) {
      Selectors[name] || (Selectors[name] = {
        Expression: rexp,
        Callback: func
      });
    }

};

/*---------------------------------- INIT ----------------------------------*/

// init context specific variables
initialize(doc);

return Dom;

});