摘要：生成終極匹配器主要是返回一個匿名函數，在這個函數中，利用方法生成的匹配器，去驗證種子集合，篩選出符合條件的集合。在這個終極匹配器中，會將獲取到的種子元素集合與匹配器進行比對，篩選出符合條件的元素。

讀Sizzle的源碼，分析的Sizzle版本號是2.3.3。

Sizzle的Github主頁

瀏覽器原生支持的元素查詢方法：

在Sizzle中，出于性能考慮，優先考慮使用JS的原生方法進行查詢。上面列出的方法中，除了querySelector方法沒有被用到，其它都在Sizzle中有使用。

對于不可以使用原生方法直接獲取結果的case，Sizzle就需要進行詞法分析，分解這個復雜的CSS選擇器，然后再逐項查詢過濾，獲取最終符合查詢條件的元素。

有以下幾個點是為了提高這種低級別查詢的速度：

從右至左： 傳統的選擇器是從左至右，比如對于選擇器#box .cls a，它的查詢過程是先找到id=box的元素，然后在這個元素后代節點里查找class中包含cls元素；找到后，再查找這個元素下的所有a元素。查找完成后再回到上一層，繼續查找下一個.cls元素，如此往復，直至完成。這樣的做法有一個問題，就是有很多不符合條件元素，在查找也會被遍歷到。而對于從右向左的順序，它是先找到所有a的元素，然后在根據剩下的選擇器#box .cls，篩選出符合這個條件的a元素。這樣一來，等于是限定了查詢范圍，相對而言速度當然會更快。但是需要明確的一點是，并不是所有的選擇器都適合這種從右至左的方式查詢。也并不是所有的從右至左查詢都比從左至右快，只是它覆蓋了絕大多數的查詢情況。

限定種子集合： 如果只有一組選擇器，也就是不存在逗號分隔查詢條件的情況；則先查找最末級的節點，在最末級的節點集合中篩選；

限定查詢范圍： 如果父級節點只是一個ID且不包含其它限制條件，則將查詢范圍縮小到父級節點；#box a；

緩存特定數據 ： 主要分三類，tokenCache, compileCache, classCache；

我們對Sizzle的查詢分為兩類：

簡易流程（沒有位置偽類）

帶位置偽類的查詢

簡易流程在進行查詢時，遵循 從右至左的流程。

梳理一下簡易流程

Sizzle流程圖（簡易版）

簡易流程忽略的東西主要是和位置偽類相關的處理邏輯，比如:nth-child之類的

詞法分析，將字符串的選擇器，解析成一系列的TOKEN。

首先明確一下TOKEN的概念，TOKEN可以看做最小的原子，不可再拆分。在CSS選擇器中，TOKEN的表現形式一般是TAG、ID、CLASS、ATTR等。一個復雜的CSS選擇器，經過詞法分析后，會生成一系列的TOKEN，然后根據這些Token進行最終的查詢和篩選。

下面舉個例子說明一下詞法分析的過程。對于字符串#box .cls a的解析:

/**
 * 下面是Sizzle中詞法解析方法 tokennize 的核心代碼 1670 ~ 1681 行
 * soFar = "#box .cls a"
 * Expr.filter 是Sizzle進行元素過濾的方法集合
 * Object.getOwnPropertyNames(Expr.filter) //  ["TAG", "CLASS", "ATTR", "CHILD", "PSEUDO", "ID"]
*/
for ( type in Expr.filter ) {
    // 拿當前的選擇字符串soFar 取匹配filter的類型，如果能匹配到，則將當前的匹配對象取出，并當做一個Token存儲起來
    // matchExpr中存儲一些列正則，這些正則用于驗證當前選擇字符串是否滿足某一token語法
    if ( (match = matchExpr[ type ].exec( soFar )) && (!preFilters[ type ] ||
        (match = preFilters[ type ]( match ))) ) {
        matched = match.shift();
        tokens.push({
            value: matched,
            type: type,
            matches: match
        });

        // 截取掉匹配到選擇字符串，繼續匹配剩余的字符串(繼續匹配是通過這段代碼外圍的while(soFar)循環實現的)
        // matchExpr中存儲的正則都是元字符“^”開頭，驗證字符串是否以‘xxx’開頭；這也就是說， 詞法分析的過程是從字符串開始位置，從左至右，一下一下地剝離出token
        soFar = soFar.slice( matched.length );
    }
}

經過上述的解析過程后，#box .cls a會被解析成如下形式的數組：
Sizzle: tokens

編譯函數的流程很簡單，首先根據selector去匹配器的緩存中查找對應的匹配器。

如果之前進行過相同selector的查詢并且緩存還在（因為Sizzle換粗數量有限，如果超過數量限制，最早的緩存會被刪掉），則直接返回當前緩存的匹配器。

如果緩存中找不到，則通過matcherFromTokens() 和matcherFromGroupMatchers() 方法生成終極匹配器，并將終極匹配器緩存。

這一步是根據詞法分析產出的tokens，生成matchers（匹配器）。
在Sizzle中，對應的方法是matcherFromTokens。

打個預防針，這個方法讀起來，很費神吶。

在Sizzle源碼（sizzle.js文件）中第 1705 ~ 1765 行，只有60行，卻揉進了好多工廠方法（就僅僅指那種return值是Function類型的方法）。
我們簡化一下這個方法的流程（去掉了偽類選擇器的處理）

function matcherFromTokens( tokens ) {
    var checkContext, matcher, j,
        len = tokens.length,
        leadingRelative = Expr.relative[ tokens[0].type ],
        implicitRelative = leadingRelative || Expr.relative[" "],
        i = leadingRelative ? 1 : 0,

        // The foundational matcher ensures that elements are reachable from top-level context(s)
        matchContext = addCombinator( function( elem ) {
            return elem === checkContext;
        }, implicitRelative, true ),
        matchAnyContext = addCombinator( function( elem ) {
            return indexOf( checkContext, elem ) > -1;
        }, implicitRelative, true ),
        matchers = [ function( elem, context, xml ) {
            var ret = ( !leadingRelative && ( xml || context !== outermostContext ) ) || (
                (checkContext = context).nodeType ?
                    matchContext( elem, context, xml ) :
                    matchAnyContext( elem, context, xml ) );
            // Avoid hanging onto element (issue #299)
            checkContext = null;
            return ret;
        } ];
        
    // 上面的都是變量聲明

    // 這個for循環就是根據tokens 生成matchers 的過程
    for ( ; i < len; i++ ) {

        // 如果碰到 祖先/兄弟 關系（">", " ", "+", "~"），則需要合并之前的matchers；
        if ( (matcher = Expr.relative[ tokens[i].type ]) ) {
            matchers = [ addCombinator(elementMatcher( matchers ), matcher) ];
        } else {
            matcher = Expr.filter[ tokens[i].type ].apply( null, tokens[i].matches );
            matchers.push( matcher );
        }
    }

    // 將所有的matchers 拼合到一起 返回一個匹配器，
    // 所有的matcher返回值都是布爾值，只要有一個條件不滿足，則當前元素不符合，排除掉
    return elementMatcher( matchers );
}

Question：為什么如果碰到 祖先/兄弟 關系（">", " ", "+", "~"），則需要合并之前的matchers？

Answer:目的并不一定要合并，而是為了找到當前節點關聯節點（滿足 祖先/兄弟 關系[">", " ", "+", "~"]），然后利用之前的匹配器驗證這個關聯節點是否滿足匹配器。而在“驗證”這個環節并不一定非要合并之前的matchers，只是合并起來結構會更清晰。舉個例子：

我們需要買汽車，現在有兩個汽車品牌A、B。A下面有四種車型：a1,a2,a3,a4；B下面有兩種車型：b1,b2。那么我們可以的買到所有車就是
[a1,a2,a3,a4,b1,b2]。但是我們也可以這么寫{A:[a1,a2,a3,a4],B:[b1,b2]}。這兩種寫法都可以表示我們可以買到車型。只是第二種相對前者，更清晰列出了車型所屬品牌關系。

同理，在合并后，我們就知道這個合并后的matcher就是為了驗證當前的節點的關聯節點。

主要是返回一個匿名函數，在這個函數中，利用matchersFromToken方法生成的匹配器，去驗證種子集合seed，篩選出符合條件的集合。
先確定種子集合，然后在拿這些種子跟匹配器逐個匹配。在匹配的過程中，從右向左逐個token匹配，只要有一個環節不滿條件，則跳出當前匹配流程，繼續進行下一個種子節點的匹配過程。

通過這樣的一個過程，從而篩選出滿足條件的DOM節點，返回給select方法。

用一個典型的查詢，來說明Sizzle的查詢過程。

以 div.cls input[type="text"] 為例：

解析出的tokens:

[
    [
        { "value": "div", "type": "TAG", "matches": ["div"] }, 
        { "value": ".cls", "type": "CLASS", "matches": ["cls"] }, 
        { "value": " ", "type": " " }, 
        { "value": "input", "type": "TAG", "matches": ["input"] }, 
        { "value": "[type="text"]", "type": "ATTR", "matches": ["type", "=", "text"]}
    ]
]

首先這個選擇器 會篩選出所有的作為種子集合seed，然后在這個集合中尋找符合條件的節點。
在尋找種子節點的過程中，刪掉了token中的第四條{ "value": "input", "type": "TAG", "matches": ["input"] }。

那么會根據剩下的tokens生成匹配器

matcherByTag("div")

matcherByClass(".cls")

碰見父子關系" "，將前面的生成的兩個matcher合并生成一個新的

matcher:

matcherByTag("div"),

matcherByClass(".cls")

這個matcher 是通過addCombinator()方法生成的匿名函數，這個matcher會先根據 父子關系parentNode，取得當前種子的parentNode， 然后再驗證是否滿足前面的兩個匹配器。

碰見第四條 屬性選擇器，生成

matcherByAttr("[type="text"]")

至此，根據tokens已經生成所有的matchers。

終極匹配器

matcher:

matcherByTag("div")

matcherByClass(".cls")

matcherByAttr("[type="text"]")

在matcherFromTokens()方法中的最后一行，還有一步操作，將所有的matchers通過elementMatcher()合并成一個matcher。
elementMatcher這個方法就是將所有的匹配方法，通過while循環都執行一遍，如果碰到不滿足條件的，就直接挑出while循環。
有一點需要說明的就是: elementMatcher方法中的while循環是倒序執行的，即從matchers最后一個matcher開始執行匹配規則。對應上面的這個例子就是，最開始執行的匹配器是matcherByAttr("[type="text"]")。 這樣一來，就過濾出了所有不滿足type="text"的的元素。然后執行下一個匹配條件，

Question: Sizzle中使用了大量閉包函數，有什么作用？出于什么考慮的？
Answer:閉包函數的作用，是為了根據selector動態生成匹配器，并將這個匹配器緩存(cached)。因為使用閉包，匹配器得以保存在內存中，這為緩存機制提供了支持。
這么做的主要目的是提高查詢性能，通過常駐內存的匹配器避免再次消耗大量資源進行詞法分析和匹配器生成。以空間換時間，提高查詢速度。

Question: matcherFromTokens中， 對每個tokens生成匹配器列表時，為什么會有一個初始化的方法？
Answer: 這個初始化的方法是用來驗證元素是否屬于當前context。

Question: matcherFromGroupMatchers的作用？
Answer: 返回一個終極匹配器，并讓編譯函數緩存這個終極匹配器。 在這個終極匹配器中，會將獲取到的種子元素集合與匹配器進行比對，篩選出符合條件的元素。

TODO: 編譯機制也許是Sizzle為了做緩存以便提高性能而做出的選擇？？
是的，詳細答案待補充~~~

TODO: outermostContext的作用
細節問題，還有待研究~~~

帶位置偽類的查詢是 由左至右。

用選擇器.mark li.limark:first.limark2 a span舉例。

在根據tokens生成匹配器（matcherFromTokens）之前的過程，跟簡易查詢沒有任何區別。
不同的地方就在matcherFromTokens()方法中。位置偽類不同于簡易查詢的是，它會根據位置偽類將選擇器分成三個部分。對應上例就是如下

.mark li.limark ： 位置偽類之前的選擇器；

:first ： 位置偽類本身；

.limark2： 跟位置偽類本身相關的選擇器，

a span：位置偽類之后的選擇器；

位置偽類的查詢思路，是先進行位置偽類之前的查詢.mark li.limark，這個查詢過程當然也是利用之前講過的簡易流程(Sizzle(selector))。查詢完成后，再根據位置偽類進行過濾，留下滿足位置偽類的節點。如果存在第三個條件，則利用第三個條件，再進行一次過濾。然后再利用這些滿足位置偽類節點作為context，進行位置偽類之后選擇器 a span的查詢。

上例選擇器中只存在一個位置偽類；如果存在多個，則從左至右，會形成一個一個的層級，逐個層級進行查詢。

下面是對應的是matcherFromTokens()方法中對位置偽類處理。

// 這個matcherFromTokens中這個for循環，之前講過了，但是 有個地方我們跳過沒講
for ( ; i < len; i++ ) {
        if ( (matcher = Expr.relative[ tokens[i].type ]) ) {
            matchers = [ addCombinator(elementMatcher( matchers ), matcher) ];
        } else {
            matcher = Expr.filter[ tokens[i].type ].apply( null, tokens[i].matches );

            // Return special upon seeing a positional matcher
            // 這個就是處理位置偽類的邏輯
            if ( matcher[ expando ] ) {
                // Find the next relative operator (if any) for proper handling
                j = ++i;
                for ( ; j < len; j++ ) { // 尋找下一個關系節點位置，并用j記錄下來
                    if ( Expr.relative[ tokens[j].type ] ) {
                        break;
                    }
                }
                return setMatcher(// setMatcher 是生成位置偽類查詢的工廠方法
                    i > 1 && elementMatcher( matchers ), // 位置偽類之前的matcher
                    i > 1 && toSelector(
                        // If the preceding token was a descendant combinator, insert an implicit any-element `*`
                        tokens.slice( 0, i - 1 ).concat({ value: tokens[ i - 2 ].type === " " ? "*" : "" })
                    ).replace( rtrim, "$1" ), // 位置偽類之前的selector
                    matcher, // 位置偽類本身的matcher
                    i < j && matcherFromTokens( tokens.slice( i, j ) ), // 位置偽類本身的filter
                    j < len && matcherFromTokens( (tokens = tokens.slice( j )) ), // 位置偽類之后的matcher
                    j < len && toSelector( tokens ) // 位置偽類之后的selector
                );
            }
            matchers.push( matcher );
        }
    }

setMatcher()方法的源碼，在這里生成最終的matcher， return給compile()方法。

//第1個參數，preFilter，前置過濾器，相當于偽類token之前`.mark li.limark`的過濾器matcher
//第2個參數，selector，偽類之前的selector (`.mark li.limark`)
//第3個參數，matcher，    當前位置偽類的過濾器matcher `:first`
//第4個參數，postFilter，偽類之后的過濾器 `.limark2`
//第5個參數，postFinder，后置搜索器，相當于在前邊過濾出來的集合里邊再搜索剩下的規則的一個搜索器 ` a span`的matcher
//第6個參數，postSelector，后置搜索器對應的選擇器字符串，相當于` a span`
function setMatcher( preFilter, selector, matcher, postFilter, postFinder, postSelector ) {
    //TODO: setMatcher 會把這倆貨在搞一次setMatcher， 還不太懂
    if ( postFilter && !postFilter[ expando ] ) {
        postFilter = setMatcher( postFilter );
    }
    if ( postFinder && !postFinder[ expando ] ) {
        postFinder = setMatcher( postFinder, postSelector );
    }
    
    return markFunction(function( seed, results, context, xml ) {
        var temp, i, elem,
            preMap = [],
            postMap = [],
            preexisting = results.length,

            // Get initial elements from seed or context
            elems = seed || multipleContexts( selector || "*", context.nodeType ? [ context ] : context, [] ),

            // Prefilter to get matcher input, preserving a map for seed-results synchronization
            matcherIn = preFilter && ( seed || !selector ) ?
                condense( elems, preMap, preFilter, context, xml ) :
                elems,

            matcherOut = matcher ?
                // If we have a postFinder, or filtered seed, or non-seed postFilter or preexisting results,
                postFinder || ( seed ? preFilter : preexisting || postFilter ) ?

                    // ...intermediate processing is necessary
                    [] :

                    // ...otherwise use results directly
                    results :
                matcherIn;

        // Find primary matches
        if ( matcher ) {
            // 這個就是 匹配位置偽類的 邏輯， 將符合位置偽類的節點剔出來
            matcher( matcherIn, matcherOut, context, xml );
        }

        // Apply postFilter
        if ( postFilter ) {
            temp = condense( matcherOut, postMap );
            postFilter( temp, [], context, xml );

            // Un-match failing elements by moving them back to matcherIn
            i = temp.length;
            while ( i-- ) {
                if ( (elem = temp[i]) ) {
                    matcherOut[ postMap[i] ] = !(matcherIn[ postMap[i] ] = elem);
                }
            }
        }

        if ( seed ) {
            if ( postFinder || preFilter ) {
                if ( postFinder ) {
                    // Get the final matcherOut by condensing this intermediate into postFinder contexts
                    temp = [];
                    i = matcherOut.length;
                    while ( i-- ) {
                        if ( (elem = matcherOut[i]) ) {
                            // Restore matcherIn since elem is not yet a final match
                            temp.push( (matcherIn[i] = elem) );
                        }
                    }
                    postFinder( null, (matcherOut = []), temp, xml );
                }

                // Move matched elements from seed to results to keep them synchronized
                i = matcherOut.length;
                while ( i-- ) {
                    if ( (elem = matcherOut[i]) &&
                        (temp = postFinder ? indexOf( seed, elem ) : preMap[i]) > -1 ) {

                        seed[temp] = !(results[temp] = elem);
                    }
                }
            }

        // Add elements to results, through postFinder if defined
        } else {
            matcherOut = condense(
                matcherOut === results ?
                    matcherOut.splice( preexisting, matcherOut.length ) :
                    matcherOut
            );
            if ( postFinder ) {
                postFinder( null, results, matcherOut, xml );
            } else {
                push.apply( results, matcherOut );
            }
        }
    });
}

【參考資料】

IE瀏覽器的兼容性查詢

JQuery - Sizzle選擇器引擎原理分析

jQuery源碼剖析（七）——Sizzle選擇器引擎之詞法分析

jQuery 2.0.3 源碼分析Sizzle引擎 - 詞法解析

Optimize Selectors(選擇器使用的最佳方式)