Selector: Backport jQuery selection context logic to selector-native

This makes:
```js
$div.find("div > *")
```
no longer matching children of `$div`.

Also, leading combinators now work, e.g.:
```js
$div.find( "> *" );
```
returns children of `$div`.

As a result of that, a number of tests are no longer skipped in the
`selector-native` mode.

Also, rename `rcombinators` to `rleadingCombinator`.

Fixes gh-5185
Closes gh-5186
Ref gh-5085

18 files changed, 325 insertions, 0 deletions

diff --git a/src/selector/createCache.js b/src/selector/createCache.js
new file mode 100644
index 000000000..18e255d0f
--- /dev/null
+++ b/src/selector/createCache.js
@@ -0,0 +1,26 @@
+import jQuery from "../core.js";
+
+/**
+ * Create key-value caches of limited size
+ * @returns {function(string, object)} Returns the Object data after storing it on itself with
+ *	property name the (space-suffixed) string and (if the cache is larger than Expr.cacheLength)
+ *	deleting the oldest entry
+ */
+function createCache() {
+	var keys = [];
+
+	function cache( key, value ) {
+
+		// Use (key + " ") to avoid collision with native prototype properties
+		// (see https://github.com/jquery/sizzle/issues/157)
+		if ( keys.push( key + " " ) > jQuery.expr.cacheLength ) {
+
+			// Only keep the most recent entries
+			delete cache[ keys.shift() ];
+		}
+		return ( cache[ key + " " ] = value );
+	}
+	return cache;
+}
+
+export default createCache;
diff --git a/src/selector/filterMatchExpr.js b/src/selector/filterMatchExpr.js
new file mode 100644
index 000000000..17056a555
--- /dev/null
+++ b/src/selector/filterMatchExpr.js
@@ -0,0 +1,18 @@
+import whitespace from "../var/whitespace.js";
+import identifier from "./var/identifier.js";
+import attributes from "./var/attributes.js";
+import pseudos from "./var/pseudos.js";
+
+var filterMatchExpr = {
+	ID: new RegExp( "^#(" + identifier + ")" ),
+	CLASS: new RegExp( "^\\.(" + identifier + ")" ),
+	TAG: new RegExp( "^(" + identifier + "|[*])" ),
+	ATTR: new RegExp( "^" + attributes ),
+	PSEUDO: new RegExp( "^" + pseudos ),
+	CHILD: new RegExp(
+		"^:(only|first|last|nth|nth-last)-(child|of-type)(?:\\(" +
+		whitespace + "*(even|odd|(([+-]|)(\\d*)n|)" + whitespace + "*(?:([+-]|)" +
+		whitespace + "*(\\d+)|))" + whitespace + "*\\)|)", "i" )
+};
+
+export default filterMatchExpr;
diff --git a/src/selector/preFilter.js b/src/selector/preFilter.js
new file mode 100644
index 000000000..4a2fb489a
--- /dev/null
+++ b/src/selector/preFilter.js
@@ -0,0 +1,90 @@
+import rpseudo from "./var/rpseudo.js";
+import filterMatchExpr from "./filterMatchExpr.js";
+import unescapeSelector from "./unescapeSelector.js";
+import selectorError from "./selectorError.js";
+import tokenize from "./tokenize.js";
+
+var preFilter = {
+	ATTR: function( match ) {
+		match[ 1 ] = unescapeSelector( match[ 1 ] );
+
+		// Move the given value to match[3] whether quoted or unquoted
+		match[ 3 ] = unescapeSelector( match[ 3 ] || match[ 4 ] || match[ 5 ] || "" );
+
+		if ( match[ 2 ] === "~=" ) {
+			match[ 3 ] = " " + match[ 3 ] + " ";
+		}
+
+		return match.slice( 0, 4 );
+	},
+
+	CHILD: function( match ) {
+
+		/* matches from filterMatchExpr["CHILD"]
+			1 type (only|nth|...)
+			2 what (child|of-type)
+			3 argument (even|odd|\d*|\d*n([+-]\d+)?|...)
+			4 xn-component of xn+y argument ([+-]?\d*n|)
+			5 sign of xn-component
+			6 x of xn-component
+			7 sign of y-component
+			8 y of y-component
+		*/
+		match[ 1 ] = match[ 1 ].toLowerCase();
+
+		if ( match[ 1 ].slice( 0, 3 ) === "nth" ) {
+
+			// nth-* requires argument
+			if ( !match[ 3 ] ) {
+				selectorError( match[ 0 ] );
+			}
+
+			// numeric x and y parameters for jQuery.expr.filter.CHILD
+			// remember that false/true cast respectively to 0/1
+			match[ 4 ] = +( match[ 4 ] ?
+				match[ 5 ] + ( match[ 6 ] || 1 ) :
+				2 * ( match[ 3 ] === "even" || match[ 3 ] === "odd" )
+			);
+			match[ 5 ] = +( ( match[ 7 ] + match[ 8 ] ) || match[ 3 ] === "odd" );
+
+		// other types prohibit arguments
+		} else if ( match[ 3 ] ) {
+			selectorError( match[ 0 ] );
+		}
+
+		return match;
+	},
+
+	PSEUDO: function( match ) {
+		var excess,
+			unquoted = !match[ 6 ] && match[ 2 ];
+
+		if ( filterMatchExpr.CHILD.test( match[ 0 ] ) ) {
+			return null;
+		}
+
+		// Accept quoted arguments as-is
+		if ( match[ 3 ] ) {
+			match[ 2 ] = match[ 4 ] || match[ 5 ] || "";
+
+		// Strip excess characters from unquoted arguments
+		} else if ( unquoted && rpseudo.test( unquoted ) &&
+
+			// Get excess from tokenize (recursively)
+			( excess = tokenize( unquoted, true ) ) &&
+
+			// advance to the next closing parenthesis
+			( excess = unquoted.indexOf( ")", unquoted.length - excess ) -
+				unquoted.length ) ) {
+
+			// excess is a negative index
+			match[ 0 ] = match[ 0 ].slice( 0, excess );
+			match[ 2 ] = unquoted.slice( 0, excess );
+		}
+
+		// Return only captures needed by the pseudo filter method (type and argument)
+		return match.slice( 0, 3 );
+	}
+};
+
+export default preFilter;
diff --git a/src/selector/selectorError.js b/src/selector/selectorError.js
new file mode 100644
index 000000000..a02e516da
--- /dev/null
+++ b/src/selector/selectorError.js
@@ -0,0 +1,5 @@
+function selectorError( msg ) {
+	throw new Error( "Syntax error, unrecognized expression: " + msg );
+}
+
+export default selectorError;
diff --git a/src/selector/testContext.js b/src/selector/testContext.js
new file mode 100644
index 000000000..a54351e64
--- /dev/null
+++ b/src/selector/testContext.js
@@ -0,0 +1,10 @@
+/**
+ * Checks a node for validity as a jQuery selector context
+ * @param {Element|Object=} context
+ * @returns {Element|Object|Boolean} The input node if acceptable, otherwise a falsy value
+ */
+function testContext( context ) {
+	return context && typeof context.getElementsByTagName !== "undefined" && context;
+}
+
+export default testContext;
diff --git a/src/selector/toSelector.js b/src/selector/toSelector.js
new file mode 100644
index 000000000..bd0c15f69
--- /dev/null
+++ b/src/selector/toSelector.js
@@ -0,0 +1,11 @@
+function toSelector( tokens ) {
+	var i = 0,
+		len = tokens.length,
+		selector = "";
+	for ( ; i < len; i++ ) {
+		selector += tokens[ i ].value;
+	}
+	return selector;
+}
+
+export default toSelector;
diff --git a/src/selector/tokenize.js b/src/selector/tokenize.js
new file mode 100644
index 000000000..34bc9ad50
--- /dev/null
+++ b/src/selector/tokenize.js
@@ -0,0 +1,83 @@
+import jQuery from "../core.js";
+import rcomma from "./var/rcomma.js";
+import rleadingCombinator from "./var/rleadingCombinator.js";
+import rtrim from "../var/rtrim.js";
+import createCache from "./createCache.js";
+import selectorError from "./selectorError.js";
+import filterMatchExpr from "./filterMatchExpr.js";
+
+var tokenCache = createCache();
+
+function tokenize( selector, parseOnly ) {
+	var matched, match, tokens, type,
+		soFar, groups, preFilters,
+		cached = tokenCache[ selector + " " ];
+
+	if ( cached ) {
+		return parseOnly ? 0 : cached.slice( 0 );
+	}
+
+	soFar = selector;
+	groups = [];
+	preFilters = jQuery.expr.preFilter;
+
+	while ( soFar ) {
+
+		// Comma and first run
+		if ( !matched || ( match = rcomma.exec( soFar ) ) ) {
+			if ( match ) {
+
+				// Don't consume trailing commas as valid
+				soFar = soFar.slice( match[ 0 ].length ) || soFar;
+			}
+			groups.push( ( tokens = [] ) );
+		}
+
+		matched = false;
+
+		// Combinators
+		if ( ( match = rleadingCombinator.exec( soFar ) ) ) {
+			matched = match.shift();
+			tokens.push( {
+				value: matched,
+
+				// Cast descendant combinators to space
+				type: match[ 0 ].replace( rtrim, " " )
+			} );
+			soFar = soFar.slice( matched.length );
+		}
+
+		// Filters
+		for ( type in filterMatchExpr ) {
+			if ( ( match = jQuery.expr.match[ type ].exec( soFar ) ) && ( !preFilters[ type ] ||
+				( match = preFilters[ type ]( match ) ) ) ) {
+				matched = match.shift();
+				tokens.push( {
+					value: matched,
+					type: type,
+					matches: match
+				} );
+				soFar = soFar.slice( matched.length );
+			}
+		}
+
+		if ( !matched ) {
+			break;
+		}
+	}
+
+	// Return the length of the invalid excess
+	// if we're just parsing
+	// Otherwise, throw an error or return tokens
+	if ( parseOnly ) {
+		return soFar.length;
+	}
+
+	return soFar ?
+		selectorError( selector ) :
+
+		// Cache the tokens
+		tokenCache( selector, groups ).slice( 0 );
+}
+
+export default tokenize;
diff --git a/src/selector/unescapeSelector.js b/src/selector/unescapeSelector.js
new file mode 100644
index 000000000..3a01f94bc
--- /dev/null
+++ b/src/selector/unescapeSelector.js
@@ -0,0 +1,29 @@
+// CSS escapes
+// https://www.w3.org/TR/CSS21/syndata.html#escaped-characters
+import whitespace from "../var/whitespace.js";
+
+var runescape = new RegExp( "\\\\[\\da-fA-F]{1,6}" + whitespace +
+	"?|\\\\([^\\r\\n\\f])", "g" ),
+	funescape = function( escape, nonHex ) {
+		var high = "0x" + escape.slice( 1 ) - 0x10000;
+
+		if ( nonHex ) {
+
+			// Strip the backslash prefix from a non-hex escape sequence
+			return nonHex;
+		}
+
+		// Replace a hexadecimal escape sequence with the encoded Unicode code point
+		// Support: IE <=11+
+		// For values outside the Basic Multilingual Plane (BMP), manually construct a
+		// surrogate pair
+		return high < 0 ?
+			String.fromCharCode( high + 0x10000 ) :
+			String.fromCharCode( high >> 10 | 0xD800, high & 0x3FF | 0xDC00 );
+	};
+
+function unescapeSelector( sel ) {
+	return sel.replace( runescape, funescape );
+}
+
+export default unescapeSelector;
diff --git a/src/selector/var/attributes.js b/src/selector/var/attributes.js
new file mode 100644
index 000000000..f9813acec
--- /dev/null
+++ b/src/selector/var/attributes.js
@@ -0,0 +1,12 @@
+import whitespace from "../../var/whitespace.js";
+import identifier from "./identifier.js";
+
+// Attribute selectors: https://www.w3.org/TR/selectors/#attribute-selectors
+export default "\\[" + whitespace + "*(" + identifier + ")(?:" + whitespace +
+
+	// Operator (capture 2)
+	"*([*^$|!~]?=)" + whitespace +
+
+	// "Attribute values must be CSS identifiers [capture 5] or strings [capture 3 or capture 4]"
+	"*(?:'((?:\\\\.|[^\\\\'])*)'|\"((?:\\\\.|[^\\\\\"])*)\"|(" + identifier + "))|)" +
+	whitespace + "*\\]";
diff --git a/src/selector/var/booleans.js b/src/selector/var/booleans.js
new file mode 100644
index 000000000..9dc3c97c7
--- /dev/null
+++ b/src/selector/var/booleans.js
@@ -0,0 +1,2 @@
+export default "checked|selected|async|autofocus|autoplay|controls|defer|disabled|hidden|ismap|" +
+	"loop|multiple|open|readonly|required|scoped";
diff --git a/src/selector/var/identifier.js b/src/selector/var/identifier.js
new file mode 100644
index 000000000..03af0ddf3
--- /dev/null
+++ b/src/selector/var/identifier.js
@@ -0,0 +1,5 @@
+import whitespace from "../../var/whitespace.js";
+
+// https://www.w3.org/TR/css-syntax-3/#ident-token-diagram
+export default "(?:\\\\[\\da-fA-F]{1,6}" + whitespace +
+	"?|\\\\[^\\r\\n\\f]|[\\w-]|[^\0-\\x7f])+";
diff --git a/src/selector/var/matches.js b/src/selector/var/matches.js
new file mode 100644
index 000000000..6f79452a1
--- /dev/null
+++ b/src/selector/var/matches.js
@@ -0,0 +1,5 @@
+import documentElement from "../../var/documentElement.js";
+
+// Support: IE 9 - 11+
+// IE requires a prefix.
+export default documentElement.matches || documentElement.msMatchesSelector;
diff --git a/src/selector/var/pseudos.js b/src/selector/var/pseudos.js
new file mode 100644
index 000000000..fdf288270
--- /dev/null
+++ b/src/selector/var/pseudos.js
@@ -0,0 +1,15 @@
+import identifier from "./identifier.js";
+import attributes from "./attributes.js";
+
+export default ":(" + identifier + ")(?:\\((" +
+
+	// To reduce the number of selectors needing tokenize in the preFilter, prefer arguments:
+	// 1. quoted (capture 3; capture 4 or capture 5)
+	"('((?:\\\\.|[^\\\\'])*)'|\"((?:\\\\.|[^\\\\\"])*)\")|" +
+
+	// 2. simple (capture 6)
+	"((?:\\\\.|[^\\\\()[\\]]|" + attributes + ")*)|" +
+
+	// 3. anything else (capture 2)
+	".*" +
+	")\\)|)";
diff --git a/src/selector/var/rcomma.js b/src/selector/var/rcomma.js
new file mode 100644
index 000000000..f5803f90f
--- /dev/null
+++ b/src/selector/var/rcomma.js
@@ -0,0 +1,3 @@
+import whitespace from "../../var/whitespace.js";
+
+export default new RegExp( "^" + whitespace + "*," + whitespace + "*" );
diff --git a/src/selector/var/rdescend.js b/src/selector/var/rdescend.js
new file mode 100644
index 000000000..bab600901
--- /dev/null
+++ b/src/selector/var/rdescend.js
@@ -0,0 +1,3 @@
+import whitespace from "../../var/whitespace.js";
+
+export default new RegExp( whitespace + "|>" );
diff --git a/src/selector/var/rleadingCombinator.js b/src/selector/var/rleadingCombinator.js
new file mode 100644
index 000000000..f802dc8c0
--- /dev/null
+++ b/src/selector/var/rleadingCombinator.js
@@ -0,0 +1,4 @@
+import whitespace from "../../var/whitespace.js";
+
+export default new RegExp( "^" + whitespace + "*([>+~]|" + whitespace + ")" +
+	whitespace + "*" );
diff --git a/src/selector/var/rpseudo.js b/src/selector/var/rpseudo.js
new file mode 100644
index 000000000..9ed943a5f
--- /dev/null
+++ b/src/selector/var/rpseudo.js
@@ -0,0 +1,3 @@
+import pseudos from "./pseudos.js";
+
+export default new RegExp( pseudos );
diff --git a/src/selector/var/rsibling.js b/src/selector/var/rsibling.js
new file mode 100644
index 000000000..9aa815895
--- /dev/null
+++ b/src/selector/var/rsibling.js
@@ -0,0 +1 @@
+export default /[+~]/;