全新選擇器引擎 jQuery Sizzle初探
jQuery相比1.2的版本，在內(nèi)部代碼的構(gòu)造上已經(jīng)出現(xiàn)了巨大的變化，其之一便是模塊的分發(fā)。隨著jQuery被用來構(gòu)建web app的場(chǎng)合愈來愈多，它的性能自然受到了大部分開發(fā)者的高度關(guān)注，它的內(nèi)部實(shí)現(xiàn)機(jī)理又是如何，比如選擇器的實(shí)現(xiàn)。
關(guān)于jQuery更多內(nèi)容，歡迎訪問： jQuery從入門到精通
Sizzle，作為一個(gè)獨(dú)立全新的選擇器引擎，出現(xiàn)在jQuery 1.3版本之后，并被John Resig作為一個(gè)開源的項(xiàng)目，可以用于其他框架：Mool, Dojo，YUI等。好了，現(xiàn)在來看為什么Sizzle選擇器如此受歡迎，使它能夠在常用dom匹配上都快于其他選擇器而讓這些框架們都垂青于它。（相關(guān)文章推薦：改變獲取對(duì)象方式 萬能的jQuery選擇器）
概要
一般選擇器的匹配模式（包括jq1.2之前），都是一個(gè)順序的思維方式，在需要遞進(jìn)式匹配時(shí)，比如$(‘div span’) 這樣的匹配時(shí)，執(zhí)行的操作都是先匹配頁面中div然后再匹配它的節(jié)點(diǎn)下的span標(biāo)簽，之后返回結(jié)果。
Sizzle則采取了相反Right To Left的實(shí)現(xiàn)方式，先搜尋頁面中所有的span標(biāo)簽，再其后的操作中才去判斷它的父節(jié)點(diǎn)（包括父節(jié)點(diǎn)以上）是否為div，是則壓入數(shù)組，否則pass，進(jìn)入下一判斷，最后返回該操作序列。另外，在很多細(xì)節(jié)上也進(jìn)行了優(yōu)化。
淺析源碼
當(dāng)我們給$符傳遞進(jìn)一個(gè)參數(shù)（也可能是多個(gè)）時(shí)，此時(shí)它會(huì)根據(jù)參數(shù)的類型（domElement | string | fn | array）進(jìn)入不同的流程，在此，重點(diǎn)看 string 類型的處理，因?yàn)橹挥兴趴梢杂|發(fā)Sizzle。首先調(diào)用正則匹配看是否為創(chuàng)建dom節(jié)點(diǎn)的操作，然后看是否為簡(jiǎn)單id匹配，這一步也由正則匹配完成，否則進(jìn)入jQuery.fn.find()函數(shù)，由此進(jìn)入Sizzle的天地。
當(dāng)進(jìn)入Sizzle時(shí)，一般情況下會(huì)配備三參：所要匹配的選擇符，上下文，匹配的結(jié)果集。調(diào)用正則對(duì)傳入的selector做一次”預(yù)匹配”.
讓我們看一下一個(gè)簡(jiǎn)單選擇器的實(shí)現(xiàn)過程：比如 div > p。我們要先找出符合條件的div[div]，再找出符合條件的p[p]，最后在上下文里[div]過濾出符合條件”>”的p[p];抽象一點(diǎn)的說法就是：在已知的上下文里，根據(jù)關(guān)系找出相應(yīng)的節(jié)點(diǎn)。他們靠關(guān)系聯(lián)系起來。那么對(duì)于選擇器的操作也就是根據(jù)關(guān)系來分組。一次次縮小上下文，直到找出符合條件的節(jié)點(diǎn)?；氐轿覀兊脑掝}，還是先看看這個(gè)令人費(fèi)解的正則，相信你會(huì)有更好的分析方法，但是眼下，我還是一點(diǎn)點(diǎn)的拆分，讓它表達(dá)的更清晰一點(diǎn)。先按照分組拆，即():
- ((?:\((?:\([^()]+\)|[^()]+)+\)|\
- [(?:\[[^\[\]]*\]|['"][^'"]*['"]|
- [^\[\]'"]+)+\]|\\.|[^ >+~,(\[\\]+)+|[>+~])
- (\s*,\s*)?((?:.|\r|\n)*)
第一行還是有點(diǎn)長(zhǎng)，用’|'拆分它:
- 1. (?:\((?:\([^()]+\)
- 2.[^()]+)+\)
- 3. \[(?:\[[^[\]]*\]
- 4. [^[\]]+)+\]|\\.
- 5.[^ >+~,(\[]+)+6.[>+~]
對(duì)于如div > p。會(huì)得到數(shù)組結(jié)果['div','>','p']。對(duì)于更復(fù)雜的選擇器，如div.classname > p.classname。會(huì)得到結(jié)果['div.classname','>','p.classname']。對(duì)于具有合并的‘,’,只是遞歸調(diào)用下獲取結(jié)果再合并而已。過程開始變得簡(jiǎn)單起來。對(duì)于普通的解析過程，我們遵循著從左到右的順序即可完成我們的目標(biāo)。讓我們總結(jié)下步驟：
1.先查找頁面上所有的div
2.循環(huán)所有的div，查找每個(gè)div下的p
3.合并結(jié)果
Sizzle用了截然相反的步驟：
◆先查找頁面上所有的p
◆循環(huán)所有的p，查找每個(gè)p的父元素
◆如果不是div，遍歷上一層。
◆如果已經(jīng)是頂層，排除此p。
◆如果是div，則保存此p元素。
由子元素來查找父元素，能得到更好的效率。打破常規(guī)思維后不僅步驟更簡(jiǎn)單了，而且效率上也得到了些許提升。所有的選擇器都可以這樣解析嗎？不是，采用right -> left的順序是有前提條件的：沒有位置關(guān)系的約束。比如如下這段html：
- <div>p1contentp2content </div>
- <div>p3contentp4content </div>
對(duì)于選擇器：$(“div p:first”)只會(huì)返回["#p1"]。而$(“div p:first-child”)則返回["#p1", "#p3"]。兩者的區(qū)別在于位置filter的結(jié)果依賴于它前面的selector解析的結(jié)果，而其它 filter，只依賴于當(dāng)前元素本身，就可以判斷它是否滿足filter。那Sizzle是通過什么來判定進(jìn)入哪一個(gè)流程呢，答案是origPOS的正則匹配,origPos指向了Expr中match對(duì)象的POS屬性,而POS中存儲(chǔ)了五花八門的位置類約束，如下：
- /:(nth|eq|gt|lt|first|last|even|odd)(?:\((\d*)\))?(?=[^-]|$)/ //POS的值
這樣一來，第一步的流程判斷就已明朗。
當(dāng)處于1的情況時(shí):
首先根據(jù)需要對(duì)當(dāng)前處理的A數(shù)組元素進(jìn)行一系列修正操作（Expr.relative主刀）。然后調(diào)用posProcess函數(shù)對(duì)修復(fù)后的元素進(jìn)行匹配.
其中，還需一層判斷，如果有層級(jí)約束，eg ‘>,’:input’ 會(huì)轉(zhuǎn)化為 ‘> :input’,因?yàn)樵谧畛跽{(diào)用chunker進(jìn)行預(yù)匹配的時(shí)候，這些是會(huì)被分割為單個(gè)數(shù)組元素的，但在這里需要將它們做一次合并，這是由posProcess所處理的數(shù)據(jù)格式所決定的。
- //如果存在偽類選擇符，從selector中移除，并保存在later中
- // 這樣一來，匹配對(duì)象便分離出來：selector（簡(jiǎn)單選擇符存儲(chǔ)器）和later（偽類選擇符存儲(chǔ)器）。
- while ( (match = Expr.match.PSEUDO.exec( selector )) )
- { later += match[0]; selectorselector = selector.replace( Expr.match.PSEUDO, "" ); }
- //構(gòu)造selector，并調(diào)用Sizzle進(jìn)行匹配,將結(jié)果存儲(chǔ)在tmpSet中
- selector = Expr.relative[selector] ? selector + "*" : selector;
- for ( var i = 0, l = root.length; i < ; i++ )
- { Sizzle( selector, root[i], tmpSet ); }
- // 最后便是filter的過濾 return Sizzle.filter( later, tmpSet );
源碼片段b: — 對(duì)預(yù)匹配后的數(shù)組A中元素的處理：
- //這個(gè)為特例，被正則分割的A數(shù)組長(zhǎng)度為2，則合并數(shù)組元素，上下文則原封不動(dòng)為Sizzle傳遞進(jìn)來的context。
- if ( parts.length === 2 && Expr.relative[ parts[0] ] )
- {
- // 完成一次匹配， 由posProcess 內(nèi)部調(diào)用 filter進(jìn)行匹配
- // 但在匹配前，完成了一次連接選擇符的操作
- // 存入set，注 set 當(dāng)前還不是最終的結(jié)果，其這里的set和上面的tmpSet一樣，都是一個(gè)"暫時(shí)性"的結(jié)果集
- set = posProcess( parts[0] + parts[1], context );
源碼片段c: — 如果存在位置約束關(guān)系， 正向匹配。
- set = Expr.relative[ parts[0] ] ?
- [ context ] :
- // 否則對(duì)隊(duì)列首元素進(jìn)行一次簡(jiǎn)單匹配操作
- Sizzle( parts.shift(), context );
分析Expr.relative，可以看出，它包含了4種dom元素間關(guān)系的判斷，分別是 “+”, “>”, “”, “~”。每一輪的匹配，都會(huì)先判斷A數(shù)組的首元素是不是代表tag間關(guān)系符(+,>等) ，而做后續(xù)處理.同時(shí)對(duì)A數(shù)組進(jìn)行循環(huán)，依次做類似的處理。源碼片段d — 對(duì)A數(shù)組(parts)的循環(huán)處理及后續(xù)。
#p#
- while ( parts.length ) {
- // 依次對(duì) 所匹配到的 數(shù)組中元素進(jìn)行 遞進(jìn)匹配
- selector = parts.shift();
- // '>' -> '>input' 的形式
- if ( Expr.relative[ selector ] )
- selector += parts.shift();
- set = posProcess( selector, set );
當(dāng)處于2的情況時(shí)：源碼片段e: — 根據(jù)當(dāng)前流程設(shè)置ret(兩種情況)。
- //為ret綁定正確的返回值 var ret = seed ?
- //seed 為上一次調(diào)用sizzle返回值， 即前文中提到的set|tmpset
- //將預(yù)匹配后的A數(shù)組(parts)中的最后元素設(shè)置為ret的expr屬性，set屬性設(shè)為上一次匹配的結(jié)果集。
- { expr: parts.pop(), set: makeArray(seed) } :
- //如果是第一次調(diào)用，則進(jìn)行匹配操作,調(diào)用find函數(shù)
- // 以parts數(shù)組最末元素為當(dāng)前選擇符，進(jìn)行匹配操作，同時(shí)設(shè)置與之相關(guān)的context
- Sizzle.find( parts.pop(), parts.length === 1 && context.parentNode
- ? context.parentNode : context, isXML(context) );
2的情況為一般邏輯處理，從這小段代碼便可得到Sizzle的匹配機(jī)制，每一次的調(diào)用都以數(shù)組末元素為基準(zhǔn)，以上一次（或預(yù)設(shè)context）為上下文約束關(guān)系以右到左的匹配,最后返回匹配結(jié)果。結(jié)合了DOM結(jié)構(gòu)的特性，性能上也得到了大幅的提升。
我們知道選擇器的類型是有效率差別的，id選擇器效率最高，其次是class、name、tag、最后是最差的*表達(dá)式。在Sizzle.find函數(shù)中，會(huì)按照這個(gè)效率的順序查找元素，如果沒有id就找class，依次下去。當(dāng)然，class的支持需要方法getElementsByClassName。如果沒有，就只好從id跳到name。
- if ( document.getElementsByClassName && document.documentElement.getElementsByClassName ) (function()
- {
- // ... // 如果支持直接獲取，則將獲取class的方法 直接添加進(jìn) Expr.order中
- ['ID', 'NAME', 'TAG'] Expr.order.splice(1, 0, "CLASS");
- //同時(shí)在find中追加對(duì)class的獲取 Expr.find.CLASS = function(match, context, isXML) {
- if ( typeof context.getElementsByClassName !== "undefined" && !isXML )
- { return context.getElementsByClassName(match[1]);
- }
- };})();
在Sizzle.find函數(shù)中，做了一系列的邏輯判斷，來保證返回結(jié)果的正確性，首先在進(jìn)入find時(shí)，保證了expr不為空的，然后根據(jù)表達(dá)式類型(id|name|tag|class?)來選擇與之對(duì)應(yīng)的匹配分支進(jìn)行實(shí)現(xiàn)，最后再做適當(dāng)?shù)氖瘴补ぷ?，將返回結(jié)果定義為對(duì)象，來移交給filter,完成整個(gè)流程。
- //order: [ "ID", "NAME", "TAG" ]
- // 當(dāng)然，如果瀏覽器支持對(duì)class的直接獲取時(shí)，order中就會(huì)出現(xiàn)class的相關(guān)匹配規(guī)則
- for ( var i = 0, l = Expr.order.length; i < l; i++ )
- { var type = Expr.order[i], match;
- // 根據(jù) type 對(duì)所傳進(jìn)來的expr 進(jìn)行正則匹配
- // match中通過正則限制了這三類匹配方式的條件。
- // 1. ID: /#((?:[\w\u00c0-\uFFFF_-]|\\.)+)/,
- // 2. NAME: /\[name=['"]*((?:[\w\u00c0-\uFFFF_-]|\\.)+)['"]*\]/,
- // 3. TAG: /^((?:[\w\u00c0-\uFFFF\*_-]|\\.)+)/,
- if ( (match = Expr.match[ type ].exec( expr )) )
- { var left = RegExp.leftContext;
- //保證返回結(jié)果的正確性，如果存在\，則刪除
- if ( left.substr( left.length - 1 ) !== "\\" )
- { match[1] = (match[1] || "").replace(/\\/g, "");
- // 根據(jù)type調(diào)用 sizzle.selector.find方法獲取結(jié)果集。
- set = Expr.find[ type ]( match, context, isXML );
- if ( set != null ) {
- //如果匹配成功，刪除已經(jīng)匹配的expr
- exprexpr = expr.replace( Expr.match[ type ], "" );
- break;
- }
- }
- } }
- return {set: set, expr: expr}; };
在所返回的對(duì)象中，expr的作用便是為了輔佐filter這把大器所需要完成任務(wù)的工具,到此就可以調(diào)用Sizzle.filter對(duì)ret.set再做一次精確匹配(匹配規(guī)則即ret.expr),以及tag間的位置約束關(guān)系的匹配（這部分同1中類似）。源碼片段g: — 和源碼片段d有類似之處。
實(shí)例
以’div > span p span:last’這個(gè)選擇符為例，看看它的調(diào)用鏈?zhǔn)侨绾雾槾瓮瓿傻?。根?jù)對(duì)源碼的剖析，理解如下：
1. jquery.init -> jquery.prototype.find
2. 進(jìn)入Sizzle(對(duì)xml的判斷) -> 設(shè)置parts數(shù)組等在匹配中所需要的元素 -> 根據(jù)數(shù)組長(zhǎng)度以及調(diào)用origPos進(jìn)行判斷，來決定進(jìn)入哪個(gè)分支，在這個(gè)實(shí)例下進(jìn)入分支1
3. 循環(huán)調(diào)用Sizzle進(jìn)行匹配，將結(jié)果存入set中(因?yàn)樵谶@一過程中是循環(huán)調(diào)用，所以對(duì)Sizzle的判斷也是需要多次，進(jìn)入哪一分支當(dāng)然也會(huì)是不一樣的，比如第二輪循環(huán)判斷則進(jìn)入分支2中進(jìn)行處理) ,對(duì)于>號(hào)的處理，也會(huì)將它合并在其后的span中，構(gòu)成新的選擇符 ‘>span’,然后進(jìn)入Expr.relative進(jìn)行匹配，同時(shí)調(diào)用posProcess。
4. 調(diào)用Sizzle.find 匹配除偽類以外的部分(即這里的選擇器不包含:last),首先會(huì)調(diào)用Expr.find的find方法來判斷是否為哪一類匹配，在這一實(shí)例中，為TAG匹配。
5. 對(duì)從4步中生成的對(duì)象進(jìn)行過濾,匹配’>’(這一步的匹配是由Sizzle.filter觸發(fā)，由Expr.relative完成),而在匹配’span:last’時(shí)則由posProcess來觸發(fā)，設(shè)置later值(:first)以及selector(span)，對(duì)span的匹配和4步驟一樣，重復(fù)匹配，而對(duì):first的匹配則是第5步的重頭戲，也就是調(diào)用Sizzle.filter來完成, 由此便生成了最后的匹配結(jié)果。
對(duì)于有‘,’這樣需要合并的選擇器，Sizzle在獲取結(jié)果后會(huì)按照文檔流進(jìn)行排序。所以，你可能會(huì)遇到這樣的問題：把一個(gè)結(jié)果集append到新的節(jié)點(diǎn)后，新的節(jié)點(diǎn)可能不會(huì)按照你書寫的選擇器的順序出現(xiàn)。以上，可以得出以下結(jié)論：大致通過如下步驟來完成：
1.對(duì)表達(dá)式分組。
2.選擇合適的處理順序。
3.在當(dāng)前的上下文里過濾要找的節(jié)點(diǎn)。并更新上下文。重復(fù)這一過程，直到結(jié)尾。
4.對(duì)結(jié)果排序，如果需要的話。
5.返回結(jié)果數(shù)組。
前向兼容
其實(shí)不止這一處，在Sizzle的API手冊(cè)中Internal部分的find 函數(shù)（與filter構(gòu)成了Sizzle的兩把寶劍），在傳遞進(jìn)該方法的參數(shù)可以用 querySelectorAll() （依賴于當(dāng)前的瀏覽器執(zhí)行環(huán)境） 直接獲取時(shí)，它則直接調(diào)用該方法，既擁有了向前兼容的特性，又達(dá)到了速度的提升。雖然有些環(huán)境實(shí)現(xiàn)了方法querySelectorAll，但是會(huì)有bug。
- //如果當(dāng)前document 支持 querySelectorAll方法,則將瀏覽器可以完成的匹配完全交給瀏覽器
- if ( document.querySelectorAll ) (function(){
- var oldSizzle = Sizzle;
- // 解決Safari bug 略過 ...
- Sizzle = function(query, context, extra, seed)
- { contextcontext = context || document;
- // 因?yàn)閝uerySelectorAll 在domElement 節(jié)點(diǎn)上操作時(shí)，存在bug 所以多了這樣的判斷
- // bug info: http://ejohn.org/blog/thoughts-on-queryselectorall/
- if ( !seed && context.nodeType === 9 && !isXML(context) )
- { return makeArray( context.querySelectorAll(query), extra ); }
- // querySelectorAll 可用則直接返回結(jié)果，否則才調(diào)用
- sizzle return oldSizzle(query, context, extra, seed); };
- // oldSizzle 方法追加進(jìn) 新的 Sizzle 中 })();
對(duì)于任何一個(gè)開發(fā)者，我想，若瀏覽器原生已提供了實(shí)現(xiàn)方法，他都不會(huì)去高效而求繁瑣吧。這一點(diǎn)在Sizzle中得到了充分的體現(xiàn)，總是盡可能的使用相應(yīng)環(huán)境下已實(shí)現(xiàn)的原生方法。所以在IE的低版本中(比如IE6)Sizzle的表現(xiàn)更加出眾，在高級(jí)的瀏覽器中的對(duì)比卻沒有那么大的差別。
#p#
擴(kuò)展
如何定義自己的選擇器呢.如果項(xiàng)目中頻繁使用某些過濾規(guī)則，是不是把它作為一個(gè)選擇器更有效呢。既然javascript的對(duì)象可以任意擴(kuò)充，只要我們?cè)L問得到，那么我們就可以很輕松得創(chuàng)建出自己的選擇器。在jQuery.expr.filter對(duì)象中，有很多內(nèi)置的選擇器，比如 'disabled','text',那我們就擴(kuò)充它,比如，想尋找包含span的div元素。
- // filter的簡(jiǎn)寫 ':'jQuery.expr[":"] = jQuery.expr.filters;$.extend($.expr[':'],
- { hasSpan: function(e) { return $(e).find('span').length > 0; } });
這樣，我們就擁有了 ':hasSpan' 的選擇器，使用當(dāng)然和默認(rèn)的一樣。
- //直接用就可以了
- $('div:hasSpan')....
比較
再拾YUI3，在經(jīng)過大幅度變化，以全新姿態(tài)出現(xiàn)，從選擇器上的執(zhí)行上效率不遜色于Sizzle幾毫，初看YUI時(shí)就一直對(duì)它的模塊細(xì)粒度化贊不絕口，但是從如我這樣的實(shí)用主義者的角度來看，選擇器就應(yīng)該是一個(gè)單獨(dú)的模塊，就如同jQuery分離而出的Sizzle。但在YUI term眼里，為了讓代碼的組織結(jié)構(gòu)看上去更加的理想化，更加具有”YUI3“的特色，將之在代碼結(jié)構(gòu)上又細(xì)分出一二三，比起Sizzle的簡(jiǎn)潔，它顯得太過學(xué)院派。
除此，在選擇器的擴(kuò)展上，sizzle表現(xiàn)勝于YUI3 selector，在實(shí)現(xiàn)css1~css3選擇器的基礎(chǔ)上，又對(duì)常用的功能進(jìn)行了擴(kuò)展。比如對(duì)表單元素快捷操作。據(jù)我所知，開發(fā)者對(duì)這類型選擇器的使用頻率并不是想象中那么低。既然有了模塊的細(xì)分，為什么不將這部分作為一個(gè)可擴(kuò)充性的功能點(diǎn)模塊融入框架中呢。Sizzle于開發(fā)者就如同一塊可口味佳的點(diǎn)心，滿足我們各式各樣的胃口，簡(jiǎn)潔，不失其功能的強(qiáng)勁，這點(diǎn)非常值得稱道。
總得來看，Sizzle與YUI就好象一個(gè)面向?qū)嶋H與理想主義的比較。這里沒有對(duì)錯(cuò)之分，從不同角度來看，都能略窺其各自的禪意。前者從如何為開發(fā)者帶來便利的角度考慮，讓開發(fā)者實(shí)時(shí)覺得它的簡(jiǎn)單可信賴。后者，也寄托了自己對(duì)web的構(gòu)想，如果瀏覽器原生全部支持css3-selector，那豈不是完全不用引入該模塊了，不過我想，真到那時(shí)候，各框架也都會(huì)有很大的變化了，只是我對(duì)這一天的到來抱有比較消極的態(tài)度，這是后話。
總結(jié)
本文從總體上討論了jQuery之Sizzle選擇器的實(shí)現(xiàn)原理，通過一個(gè)初步的流程分析，讓各位讀者對(duì)此有一個(gè)大致印象，毫無疑問，更深層次的匹配，也只是它的遞歸調(diào)用，再匹配而已。
這里，沒有做與其他框架在效率上的比較，如果你還對(duì)它的效率還有所懷疑的話，你可以自行比較。如果你感興趣，更推薦你繼續(xù)去探索在1.4中著重優(yōu)化的api源碼，或許，會(huì)給你更多的啟示。
思考
從jQuery的角度來講，Sizzle的出現(xiàn)隨之也帶來了web上的一些新的局面，在追求效率的同時(shí)，即使是這類單種子模式的庫(kù)也是需要將之分離開來，來設(shè)計(jì)成能夠獨(dú)立使用，獨(dú)立維護(hù)的引擎。
從選擇器的角度來講，Sizzle這次算法的提升，我初步的結(jié)論是它結(jié)合了DOM這一特定的數(shù)據(jù)結(jié)構(gòu)，使其每次的匹配能夠更精準(zhǔn),以此獲得引擎效率上的提升。
我們可否多想想，在思維的開拓上能給我們留下多少財(cái)富。很多問題的解決，在換一種新的思維方式后，是不是常常會(huì)有柳暗花明的感覺呢。
【編輯推薦】
