import * as lang from './lang';
import global from './global';
import * as dom from './dom';

let window: Window = global;
let trim = String.prototype.trim ?
	function(str) { return str.trim(); } :
	function(str) { return str.replace(/^\s\s*/, '').replace(/\s\s*$/, ''); };

let getDoc = function() { return window.document; };
let cssCaseBug = (getDoc().compatMode) == "BackCompat";
let specials = ">~+";
let caseSensitive = false;

let yesman = function() { return true; };
let getQueryParts = function(query) {

	if (specials.indexOf(query.slice(-1)) >= 0) {
		query += " * ";
	} else {
		query += " ";
	}

	let ts = function(/*Integer*/ s, /*Integer*/ e) {
		return trim(query.slice(s, e));
	};

	let queryParts = [];


	let inBrackets = -1, inParens = -1, inMatchFor = -1,
		inPseudo = -1, inClass = -1, inId = -1, inTag = -1, currentQuoteChar,
		lc = "", cc = "", pStart;

	// iteration lets
	let x = 0, // index in the query
		ql = query.length,
		currentPart = null, // data structure representing the entire clause
		_cp = null; // the current pseudo or attr matcher
	let endTag = function() {
		if (inTag >= 0) {
			let tv = (inTag == x) ? null : ts(inTag, x); // .toLowerCase();
			currentPart[(specials.indexOf(tv) < 0) ? "tag" : "oper"] = tv;
			inTag = -1;
		}
	};

	let endId = function() {
		if (inId >= 0) {
			currentPart.id = ts(inId, x).replace(/\\/g, "");
			inId = -1;
		}
	};

	let endClass = function() {
		if (inClass >= 0) {
			currentPart.classes.push(ts(inClass + 1, x).replace(/\\/g, ""));
			inClass = -1;
		}
	};

	let endAll = function() {
		// at the end of a simple fragment, so wall off the matches
		endId();
		endTag();
		endClass();
	};

	let endPart = function() {
		endAll();
		if (inPseudo >= 0) {
			currentPart.pseudos.push({ name: ts(inPseudo + 1, x) });
		}
		currentPart.loops = (
			currentPart.pseudos.length ||
			currentPart.attrs.length ||
			currentPart.classes.length);

		currentPart.oquery = currentPart.query = ts(pStart, x); // save the full expression as a string


		currentPart.otag = currentPart.tag = (currentPart["oper"]) ? null : (currentPart.tag || "*");

		if (currentPart.tag) {
			currentPart.tag = currentPart.tag.toUpperCase();
		}

		// add the part to the list
		if (queryParts.length && (queryParts[queryParts.length - 1].oper)) {
			currentPart.infixOper = queryParts.pop();
			currentPart.query = currentPart.infixOper.query + " " + currentPart.query;
		}
		queryParts.push(currentPart);

		currentPart = null;
	};

	for (; lc = cc, cc = query.charAt(x), x < ql; x++) {
		if (lc == "\\") { continue; }
		if (!currentPart) { // a part was just ended or none has yet been created
			// NOTE: I hate all this alloc, but it's shorter than writing tons of if's
			pStart = x;
			currentPart = {
				query: null, // the full text of the part's rule
				pseudos: [], // CSS supports multiple pseud-class matches in a single rule
				attrs: [],	// CSS supports multi-attribute match, so we need an array
				classes: [], // class matches may be additive, e.g.: .thinger.blah.howdy
				tag: null,	// only one tag...
				oper: null, // ...or operator per component. Note that these wind up being exclusive.
				id: null,	// the id component of a rule
				getTag: function() {
					return caseSensitive ? this.otag : this.tag;
				}
			};
			inTag = x;
		}
		if (currentQuoteChar) {
			if (cc == currentQuoteChar) {
				currentQuoteChar = null;
			}
			continue;
		} else if (cc == "'" || cc == '"') {
			currentQuoteChar = cc;
			continue;
		}

		if (inBrackets >= 0) {
			// look for a the close first
			if (cc == "]") { // if we're in a [...] clause and we end, do assignment
				if (!_cp.attr) {
					// no attribute match was previously begun, so we
					// assume this is an attribute existence match in the
					// form of [someAttributeName]
					_cp.attr = ts(inBrackets + 1, x);
				} else {
					// we had an attribute already, so we know that we're
					// matching some sort of value, as in [attrName=howdy]
					_cp.matchFor = ts((inMatchFor || inBrackets + 1), x);
				}
				let cmf = _cp.matchFor;
				if (cmf) {
					// try to strip quotes from the matchFor value. We want
					// [attrName=howdy] to match the same
					//	as [attrName = 'howdy' ]
					if ((cmf.charAt(0) == '"') || (cmf.charAt(0) == "'")) {
						_cp.matchFor = cmf.slice(1, -1);
					}
				}
				// remove backslash escapes from an attribute match, since DOM
				// querying will get attribute values without backslashes
				if (_cp.matchFor) {
					_cp.matchFor = _cp.matchFor.replace(/\\/g, "");
				}

				// end the attribute by adding it to the list of attributes.
				currentPart.attrs.push(_cp);
				_cp = null; // necessary?
				inBrackets = inMatchFor = -1;
			} else if (cc == "=") {
				// if the last char was an operator prefix, make sure we
				// record it along with the "=" operator.
				let addToCc = ("|~^$*".indexOf(lc) >= 0) ? lc : "";
				_cp.type = addToCc + cc;
				_cp.attr = ts(inBrackets + 1, x - addToCc.length);
				inMatchFor = x + 1;
			}
			// now look for other clause parts
		} else if (inParens >= 0) {
			// if we're in a parenthetical expression, we need to figure
			// out if it's attached to a pseudo-selector rule like
			// :nth-child(1)
			if (cc == ")") {
				if (inPseudo >= 0) {
					_cp.value = ts(inParens + 1, x);
				}
				inPseudo = inParens = -1;
			}
		} else if (cc == "#") {
			// start of an ID match
			endAll();
			inId = x + 1;
		} else if (cc == ".") {
			// start of a class match
			endAll();
			inClass = x;
		} else if (cc == ":") {
			// start of a pseudo-selector match
			endAll();
			inPseudo = x;
		} else if (cc == "[") {
			// start of an attribute match.
			endAll();
			inBrackets = x;
			// provide a new structure for the attribute match to fill-in
			_cp = {
				/*=====
				attr: null, type: null, matchFor: null
				=====*/
			};
		} else if (cc == "(") {
			// we really only care if we've entered a parenthetical
			// expression if we're already inside a pseudo-selector match
			if (inPseudo >= 0) {
				// provide a new structure for the pseudo match to fill-in
				_cp = {
					name: ts(inPseudo + 1, x),
					value: null
				};
				currentPart.pseudos.push(_cp);
			}
			inParens = x;
		} else if (
			(cc == " ") &&
			// if it's a space char and the last char is too, consume the
			// current one without doing more work
			(lc != cc)
		) {
			endPart();
		}
	}
	return queryParts;
};

let agree = function(first, second) {
	// the basic building block of the yes/no chaining system. agree(f1,
	// f2) generates a new function which returns the boolean results of
	// both of the passed functions to a single logical-anded result. If
	// either are not passed, the other is used exclusively.
	if (!first) { return second; }
	if (!second) { return first; }

	return function() {
		return first.apply(window, arguments) && second.apply(window, arguments);
	};
};

let getArr = function(i, arr?) {
	// helps us avoid array alloc when we don't need it
	let r = arr || []; // FIXME: should this be 'new d._NodeListCtor()' ?
	if (i) { r.push(i); }
	return r;
};

let _isElement = function(n) { return (1 == n.nodeType); };

let blank = "";
let _getAttr = function(elem, attr) {
	if (!elem) { return blank; }
	if (attr == "class") {
		return elem.className || blank;
	}
	if (attr == "for") {
		return elem.htmlFor || blank;
	}
	if (attr == "style") {
		return elem.style.cssText || blank;
	}
	return (caseSensitive ? elem.getAttribute(attr) : elem.getAttribute(attr, 2)) || blank;
};

let attrs = {
	"*=": function(attr, value) {
		return function(elem) {
			// E[foo*="bar"]
			//		an E element whose "foo" attribute value contains
			//		the substring "bar"
			return (_getAttr(elem, attr).indexOf(value) >= 0);
		};
	},
	"^=": function(attr, value) {
		// E[foo^="bar"]
		//		an E element whose "foo" attribute value begins exactly
		//		with the string "bar"
		return function(elem) {
			return (_getAttr(elem, attr).indexOf(value) == 0);
		};
	},
	"$=": function(attr, value) {
		// E[foo$="bar"]
		//		an E element whose "foo" attribute value ends exactly
		//		with the string "bar"
		return function(elem) {
			let ea = " " + _getAttr(elem, attr);
			let lastIndex = ea.lastIndexOf(value);
			return lastIndex > -1 && (lastIndex == (ea.length - value.length));
		};
	},
	"~=": function(attr, value) {
		// E[foo~="bar"]
		//		an E element whose "foo" attribute value is a list of
		//		space-separated values, one of which is exactly equal
		//		to "bar"

		// return "[contains(concat(' ',@"+attr+",' '), ' "+ value +" ')]";
		let tval = " " + value + " ";
		return function(elem) {
			let ea = " " + _getAttr(elem, attr) + " ";
			return (ea.indexOf(tval) >= 0);
		};
	},
	"|=": function(attr, value) {
		// E[hreflang|="en"]
		//		an E element whose "hreflang" attribute has a
		//		hyphen-separated list of values beginning (from the
		//		left) with "en"
		let valueDash = value + "-";
		return function(elem) {
			let ea = _getAttr(elem, attr);
			return (
				(ea == value) ||
				(ea.indexOf(valueDash) == 0)
			);
		};
	},
	"=": function(attr, value) {
		return function(elem) {
			return (_getAttr(elem, attr) == value);
		};
	}
};

// avoid testing for node type if we can. Defining this in the negative
// here to avoid negation in the fast path.
let _noNES = (typeof (<HTMLElement>(getDoc().firstChild)).nextElementSibling == "undefined");
let _ns = !_noNES ? "nextElementSibling" : "nextSibling";
let _ps = !_noNES ? "previousElementSibling" : "previousSibling";
let _simpleNodeTest = (_noNES ? _isElement : yesman);

let _lookLeft = function(node) {
	// look left
	while (node = node[_ps]) {
		if (_simpleNodeTest(node)) { return false; }
	}
	return true;
};

let _lookRight = function(node) {
	// look right
	while (node = node[_ns]) {
		if (_simpleNodeTest(node)) { return false; }
	}
	return true;
};

let getNodeIndex = function(node) {
	let root = node.parentNode;
	root = root.nodeType != 7 ? root : root.nextSibling; // PROCESSING_INSTRUCTION_NODE
	let i = 0,
		tret = root.children || root.childNodes,
		ci = (node["_i"] || node.getAttribute("_i") || -1),
		cl = (root["_l"] || (typeof root.getAttribute !== "undefined" ? root.getAttribute("_l") : -1));

	if (!tret) { return -1; }
	let l = tret.length;

	// we calculate the parent length as a cheap way to invalidate the
	// cache. It's not 100% accurate, but it's much more honest than what
	// other libraries do
	if (cl == l && ci >= 0 && cl >= 0) {
		// if it's legit, tag and release
		return ci;
	}

	// else re-key things
	root["_l"] = l;
	ci = -1;
	for (let te = root["firstElementChild"] || root["firstChild"]; te; te = te[_ns]) {
		if (_simpleNodeTest(te)) {
			te["_i"] = ++i;
			if (node === te) {
				// NOTE:
				//	shortcutting the return at this step in indexing works
				//	very well for benchmarking but we avoid it here since
				//	it leads to potential O(n^2) behavior in sequential
				//	getNodexIndex operations on a previously un-indexed
				//	parent. We may revisit this at a later time, but for
				//	now we just want to get the right answer more often
				//	than not.
				ci = i;
			}
		}
	}
	return ci;
};

let isEven = function(elem) {
	return !((getNodeIndex(elem)) % 2);
};

let isOdd = function(elem) {
	return ((getNodeIndex(elem)) % 2);
};

let pseudos = {
	"checked": function(name, condition) {
		return function(elem) {
			return !!("checked" in elem ? elem.checked : elem.selected);
		};
	},
	"disabled": function(name, condition) {
		return function(elem) {
			return elem.disabled;
		};
	},
	"enabled": function(name, condition) {
		return function(elem) {
			return !elem.disabled;
		};
	},
	"first-child": function() { return _lookLeft; },
	"last-child": function() { return _lookRight; },
	"only-child": function(name, condition) {
		return function(node) {
			return _lookLeft(node) && _lookRight(node);
		};
	},
	"empty": function(name, condition) {
		return function(elem) {
			// DomQuery and jQuery get this wrong, oddly enough.
			// The CSS 3 selectors spec is pretty explicit about it, too.
			let cn = elem.childNodes;
			let cnl = elem.childNodes.length;
			// if(!cnl){ return true; }
			for (let x = cnl - 1; x >= 0; x--) {
				let nt = cn[x].nodeType;
				if ((nt === 1) || (nt == 3)) { return false; }
			}
			return true;
		};
	},
	"contains": function(name, condition) {
		let cz = condition.charAt(0);
		if (cz == '"' || cz == "'") { //remove quote
			condition = condition.slice(1, -1);
		}
		return function(elem) {
			return (elem.innerHTML.indexOf(condition) >= 0);
		};
	},
	"not": function(name, condition) {
		let p = getQueryParts(condition)[0];
		let ignores: { el: number, tag?: number, classes?: number } = { el: 1 };
		if (p.tag != "*") {
			ignores.tag = 1;
		}
		if (!p.classes.length) {
			ignores.classes = 1;
		}
		let ntf = getSimpleFilterFunc(p, ignores);
		return function(elem) {
			return (!ntf(elem));
		};
	},
	"nth-child": function(name, condition): any {
		let pi = parseInt;
		// avoid re-defining function objects if we can
		if (condition == "odd") {
			return isOdd;
		} else if (condition == "even") {
			return isEven;
		}
		// FIXME: can we shorten this?
		if (condition.indexOf("n") != -1) {
			let tparts = condition.split("n", 2);
			let pred = tparts[0] ? ((tparts[0] == '-') ? -1 : pi(tparts[0])) : 1;
			let idx = tparts[1] ? pi(tparts[1]) : 0;
			let lb = 0, ub = -1;
			if (pred > 0) {
				if (idx < 0) {
					idx = (idx % pred) && (pred + (idx % pred));
				} else if (idx > 0) {
					if (idx >= pred) {
						lb = idx - idx % pred;
					}
					idx = idx % pred;
				}
			} else if (pred < 0) {
				pred *= -1;
				// idx has to be greater than 0 when pred is negative;
				// shall we throw an error here?
				if (idx > 0) {
					ub = idx;
					idx = idx % pred;
				}
			}
			if (pred > 0) {
				return function(elem) {
					let i = getNodeIndex(elem);
					return (i >= lb) && (ub < 0 || i <= ub) && ((i % pred) == idx);
				};
			} else {
				condition = idx;
			}
		}
		let ncount = pi(condition);
		return function(elem) {
			return (getNodeIndex(elem) == ncount);
		};
	}
};

let defaultGetter = function(cond) {
	return function(elem) {
		return (elem && elem.getAttribute && elem.hasAttribute(cond));
	};
};

let getSimpleFilterFunc = function(query, ignores) {
	// generates a node tester function based on the passed query part. The
	// query part is one of the structures generated by the query parser
	// when it creates the query AST. The "ignores" object specifies which
	// (if any) tests to skip, allowing the system to avoid duplicating
	// work where it may have already been taken into account by other
	// factors such as how the nodes to test were fetched in the first
	// place
	if (!query) { return yesman; }
	ignores = ignores || {};

	let ff = null;

	if (!("el" in ignores)) {
		ff = agree(ff, _isElement);
	}

	if (!("tag" in ignores)) {
		if (query.tag != "*") {
			ff = agree(ff, function(elem) {
				return (elem && ((caseSensitive ? elem.tagName : elem.tagName.toUpperCase()) == query.getTag()));
			});
		}
	}

	if (!("classes" in ignores)) {
		query.classes.forEach(function(cname, idx, arr) {
			// get the class name
			/*
			let isWildcard = cname.charAt(cname.length-1) == "*";
			if(isWildcard){
				cname = cname.substr(0, cname.length-1);
			}
			// I dislike the regex thing, even if memoized in a cache, but it's VERY short
			let re = new RegExp("(?:^|\\s)" + cname + (isWildcard ? ".*" : "") + "(?:\\s|$)");
			*/
			let re = new RegExp("(?:^|\\s)" + cname + "(?:\\s|$)");
			ff = agree(ff, function(elem) {
				return re.test(elem.className);
			});
			ff.count = idx;
		});
	}

	if (!("attrs" in ignores)) {
		query.attrs && query.attrs.forEach(function(attr) {
			let matcher;
			let a = attr.attr;
			// type, attr, matchFor
			if (attr.type && attrs[attr.type]) {
				matcher = attrs[attr.type](a, attr.matchFor);
			} else if (a.length) {
				matcher = defaultGetter(a);
			}
			if (matcher) {
				ff = agree(ff, matcher);
			}
		});
	}

	if (!("id" in ignores)) {
		if (query.id) {
			ff = agree(ff, function(elem) {
				return (!!elem && (elem.id == query.id));
			});
		}
	}

	if (!ff) {
		if (!("default" in ignores)) {
			ff = yesman;
		}
	}
	return ff;
};

let _nextSibling = function(filterFunc) {
	return function(node, ret, bag) {
		while (node = node[_ns]) {
			if (_noNES && (!_isElement(node))) { continue; }
			if (
				(!bag || _isUnique(node, bag)) &&
				filterFunc(node)
			) {
				ret.push(node);
			}
			break;
		}
		return ret;
	};
};

let _nextSiblings = function(filterFunc) {
	return function(root, ret, bag) {
		let te = root[_ns];
		while (te) {
			if (_simpleNodeTest(te)) {
				if (bag && !_isUnique(te, bag)) {
					break;
				}
				if (filterFunc(te)) {
					ret.push(te);
				}
			}
			te = te[_ns];
		}
		return ret;
	};
};

// get an array of child *elements*, skipping text and comment nodes
let _childElements = function(filterFunc) {
	filterFunc = filterFunc || yesman;
	return function(root, ret, bag) {
		// get an array of child elements, skipping text and comment nodes
		let te, x = 0, tret = root.children || root.childNodes;
		while (te = tret[x++]) {
			if (
				_simpleNodeTest(te) &&
				(!bag || _isUnique(te, bag)) &&
				(filterFunc(te, x))
			) {
				ret.push(te);
			}
		}
		return ret;
	};
};

// test to see if node is below root
let _isDescendant = function(node, root) {
	let pn = node.parentNode;
	while (pn) {
		if (pn == root) {
			break;
		}
		pn = pn.parentNode;
	}
	return !!pn;
};

let _getElementsFuncCache = {};

let getElementsFunc = function(query) {
	let retFunc = _getElementsFuncCache[query.query];
	// if we've got a cached dispatcher, just use that
	if (retFunc) { return retFunc; }
	let io = query.infixOper;
	let oper = (io ? io.oper : "");
	let filterFunc = getSimpleFilterFunc(query, { el: 1 });
	let qt = query.tag;
	let wildcardTag = ("*" == qt);
	let ecs = getDoc()["getElementsByClassName"];

	if (!oper) {
		if (query.id) {
			filterFunc = (!query.loops && wildcardTag) ?
				yesman :
				getSimpleFilterFunc(query, { el: 1, id: 1 });

			retFunc = function(root, arr) {
				let te = dom.by_id(query.id);
				if (!te || !filterFunc(te)) { return; }
				if (9 == root.nodeType) { // if root's a doc, we just return directly
					return getArr(te, arr);
				} else { // otherwise check ancestry
					if (_isDescendant(te, root)) {
						return getArr(te, arr);
					}
				}
			};
		} else if (
			ecs &&
			/\{\s*\[native code\]\s*\}/.test(String(ecs)) &&
			query.classes.length &&
			!cssCaseBug
		) {
			filterFunc = getSimpleFilterFunc(query, { el: 1, classes: 1, id: 1 });
			let classesString = query.classes.join(" ");
			retFunc = function(root, arr, bag) {
				let ret = getArr(0, arr), te, x = 0;
				let tret = root.getElementsByClassName(classesString);
				while ((te = tret[x++])) {
					if (filterFunc(te, root) && _isUnique(te, bag)) {
						ret.push(te);
					}
				}
				return ret;
			};

		} else if (!wildcardTag && !query.loops) {
			// it's tag only. Fast-path it.
			retFunc = function(root, arr, bag) {
				let ret = getArr(0, arr), te, x = 0;
				let tag = query.getTag(),
					tret = tag ? root.getElementsByTagName(tag) : [];
				while ((te = tret[x++])) {
					if (_isUnique(te, bag)) {
						ret.push(te);
					}
				}
				return ret;
			};
		} else {
			filterFunc = getSimpleFilterFunc(query, { el: 1, tag: 1, id: 1 });
			retFunc = function(root, arr, bag) {
				let ret = getArr(0, arr), te, x = 0;
				let tag = query.getTag(),
					tret = tag ? root.getElementsByTagName(tag) : [];
				while ((te = tret[x++])) {
					if (filterFunc(te, root) && _isUnique(te, bag)) {
						ret.push(te);
					}
				}
				return ret;
			};
		}
	} else {
		// the query is scoped in some way. Instead of querying by tag we
		// use some other collection to find candidate nodes
		let skipFilters: { el: number, tag?: number } = { el: 1 };
		if (wildcardTag) {
			skipFilters.tag = 1;
		}
		filterFunc = getSimpleFilterFunc(query, skipFilters);
		if ("+" == oper) {
			retFunc = _nextSibling(filterFunc);
		} else if ("~" == oper) {
			retFunc = _nextSiblings(filterFunc);
		} else if (">" == oper) {
			retFunc = _childElements(filterFunc);
		}
	}
	// cache it and return
	return _getElementsFuncCache[query.query] = retFunc;
};

let filterDown = function(root, queryParts) {
	let candidates = getArr(root), qp, x, te, qpl = queryParts.length, bag, ret;

	for (let i = 0; i < qpl; i++) {
		ret = [];
		qp = queryParts[i];
		x = candidates.length - 1;
		if (x > 0) {
			bag = {};
			ret.nozip = true;
		}
		let gef = getElementsFunc(qp);
		for (let j = 0; (te = candidates[j]); j++) {
			gef(te, ret, bag);
		}
		if (!ret.length) { break; }
		candidates = ret;
	}
	return ret;
};

let _queryFuncCacheDOM = {},
	_queryFuncCacheQSA = {};

let getStepQueryFunc = function(query) {
	let qparts = getQueryParts(trim(query));

	if (qparts.length == 1) {
		let tef = getElementsFunc(qparts[0]);
		return function(root) {
			let r = tef(root, []);
			if (r) { r.nozip = true; }
			return r;
		};
	}

	return function(root) {
		return filterDown(root, qparts);
	};
};

let noZip = "nozip";

let qsa = "querySelectorAll";
let qsaAvail = !!getDoc()[qsa];

//Don't bother with n+3 type of matches, IE complains if we modify those.
let infixSpaceRe = /\\[>~+]|n\+\d|([^ \\])?([>~+])([^ =])?/g;
let infixSpaceFunc = function(match, pre, ch, post) {
	return ch ? (pre ? pre + " " : "") + ch + (post ? " " + post : "") : /*n+3*/ match;
};

//Don't apply the infixSpaceRe to attribute value selectors
let attRe = /([^[]*)([^\]]*])?/g;
let attFunc = function(match, nonAtt, att) {
	return nonAtt.replace(infixSpaceRe, infixSpaceFunc) + (att || "");
};
let getQueryFunc = function(query, forceDOM?) {
	//Normalize query. The CSS3 selectors spec allows for omitting spaces around
	//infix operators, >, ~ and +
	//Do the work here since detection for spaces is used as a simple "not use QSA"
	//test below.
	query = query.replace(attRe, attFunc);

	if (qsaAvail) {
		// if we've got a cached letiant and we think we can do it, run it!
		let qsaCached = _queryFuncCacheQSA[query];
		if (qsaCached && !forceDOM) { return qsaCached; }
	}

	// else if we've got a DOM cached letiant, assume that we already know
	// all we need to and use it
	let domCached = _queryFuncCacheDOM[query];
	if (domCached) { return domCached; }

	// TODO:
	//		today we're caching DOM and QSA branches separately so we
	//		recalc useQSA every time. If we had a way to tag root+query
	//		efficiently, we'd be in good shape to do a global cache.

	let qcz = query.charAt(0);
	let nospace = (-1 == query.indexOf(" "));

	// byId searches are wicked fast compared to QSA, even when filtering
	// is required
	if ((query.indexOf("#") >= 0) && (nospace)) {
		forceDOM = true;
	}

	let useQSA = (
		qsaAvail && (!forceDOM) &&
		(specials.indexOf(qcz) == -1) &&
		(query.indexOf(":") == -1) &&
		(!(cssCaseBug && (query.indexOf(".") >= 0))) &&
		(query.indexOf(":contains") == -1) && (query.indexOf(":checked") == -1) &&
		(query.indexOf("|=") == -1)
	);

	if (useQSA) {
		let tq = (specials.indexOf(query.charAt(query.length - 1)) >= 0) ?
			(query + " *") : query;
		return _queryFuncCacheQSA[query] = function(root) {
			try {
				if (!((9 == root.nodeType) || nospace)) { throw ""; }
				let r = root[qsa](tq);
				// skip expensive duplication checks and just wrap in a NodeList
				r[noZip] = true;
				return r;
			} catch (e) {
				// else run the DOM branch on this query, ensuring that we
				// default that way in the future
				return getQueryFunc(query, true)(root);
			}
		};
	} else {
		// DOM branch
		let parts = query.match(/([^\s,](?:"(?:\\.|[^"])+"|'(?:\\.|[^'])+'|[^,])*)/g);
		return _queryFuncCacheDOM[query] = ((parts.length < 2) ?
			// if not a compound query (e.g., ".foo, .bar"), cache and return a dispatcher
			getStepQueryFunc(query) :
			// if it *is* a complex query, break it up into its
			// constituent parts and return a dispatcher that will
			// merge the parts when run
			function(root) {
				let pindex = 0, // avoid array alloc for every invocation
					ret = [],
					tp;
				while ((tp = parts[pindex++])) {
					ret = ret.concat(getStepQueryFunc(tp)(root));
				}
				return ret;
			}
		);
	}
};

let _zipIdx = 0;

// NOTE:
//		this function is Moo inspired, but our own impl to deal correctly
let _nodeUID = function(node) {
	return (node._uid || node.uniqueID || (node._uid = ++_zipIdx));
};

// determine if a node in is unique in a "bag". In this case we don't want
// to flatten a list of unique items, but rather just tell if the item in
// question is already in the bag. Normally we'd just use hash lookup to do
// this for us but IE's DOM is busted so we can't really count on that. On
// the upside, it gives us a built in unique ID function.
let _isUnique = function(node, bag) {
	if (!bag) { return 1; }
	let id = _nodeUID(node);
	if (!bag[id]) { return bag[id] = 1; }
	return 0;
};

// attempt to efficiently determine if an item in a list is a dupe,
// returning a list of "uniques", hopefully in document order
let _zipIdxName = "_zipIdx";
let _zip = function(arr) {
	if (arr && arr.nozip) { return arr; }

	if (!arr || !arr.length) { return []; }
	if (arr.length < 2) { return [arr[0]]; }

	let ret = [];

	_zipIdx++;

	// we have to fork here for IE and XML docs because we can't set
	// expandos on their nodes (apparently). *sigh*
	let te;
	for (let x = 0; x < arr.length; x++) {
		if ((te = arr[x]) && te[_zipIdxName] != _zipIdx) {
			ret.push(te);
			te[_zipIdxName] = _zipIdx;
		}
	}
	return ret;
};

// the main executor
let query = function(/*String*/ query, /*String|DOMNode?*/ root) {
	root = root || getDoc();

	// throw the big case sensitivity switch
	let od = root.ownerDocument || root;	// root is either Document or a node inside the document
	caseSensitive = (od.createElement("div").tagName === "div");

	// NOTE:
	//		adding "true" as the 2nd argument to getQueryFunc is useful for
	//		testing the DOM branch without worrying about the
	//		behavior/performance of the QSA branch.
	let r = getQueryFunc(query)(root);

	// FIXME:
	//		need to investigate this branch WRT #8074 and #8075
	if (r && r.nozip) {
		return r;
	}
	return _zip(r); // dojo/NodeList
};
export = query;