jQuery核心Sizzle的“编译”原理

jQuery核心Sizzle的“编译”原理

Sizzle，是jQuery作者John Resig写的DOM选择器引擎，速度号称业界第一。作为一个独立全新的选择器引擎，出现在jQuery 1.3版本之后，并被John Resig作为一个开源的项目。Sizzle是独立的一部分，不依赖任何库，如果你不想用jQuery，可以只用Sizzle，也可以用于其他框架如：Mool, Dojo，YUI等。

前几天在准备一个关于jQuery的分享PPT，问同事关于jQuery除了使用方法之外还有没有其他特别想了解一下的，有人提到了想了解下它的选择器是怎么实现的，也有人提到jQuery的查询速度跟其他框架比怎么样。关于速度，sizzle的官方网站上可以下载测试的例子，速度确实很有优势。但是它为什么会有这样高效的运行速度，就跟这里想探讨的实现原理有关系了。

在了解Sizzle之前必须要先了解它的选择器是怎么回事，这里有一个简单的例子，熟悉jQuery的同学也一定很熟悉这样的选择器格式：

tag #id .class , a:first

它基本上是从左到右层层深入过滤去查找匹配的dom元素，这个语句还不算复杂。假设我们自己来实现这一条查询语句的话，也不难。但是，查询语句只有基本的规则，没有固定的选择符个数和顺序，我们自己写代码怎样能适应这种随意的排列组合？Sizzle就能做到各种情况的正常解析、执行。

Sizzle的源码确实错综复杂不容易理清楚它的思路。先抛开外面层层的包裹，直接看看我个人认为整个实现里很核心的三个方法：

第一个核心方法。源码第1052行有一个tokenize函数：

function tokenize(selector, parSEOnly ) { }

第二个参数parseOnly为false的意思是只做token序列化操作，不返回结果，这个情况下序列化的结果会被缓存起来备用。Selector就是查询语句了。

经过这个函数处理后，比如selector="#idtag.class , a:first"传进去，可以得到一个格式类似于下面的结果：

[

[

{matches:" id ",type:"ID"},

{matches:" tag ",type:"TAG"},

{matches:" class ",type:"CLASS"},

...

],

[

{matches:" a",type:"TAG"},

...

],

[…],

…

]

看到tokenize这个函数的命名和它的作用，让我很容易就联想起“编译原理”这个词了。这里就有点像是词法分析了，不过这个词法分析比程序编译时做的词法分析简单。

tokenize方法会根据selector里面的逗号，空格和关系选择符的正则表达式做“分词”，得到一个二维数组(请允许我冒用这个不是很准确的称呼)，其中第一维数组是根据逗号分隔出来的，在源代码里面被称作groups。

我们再看源代码第405行开始有一个ExPR = Sizzle.selectors = {}的定义，其中到567行的时候有一个filter的定义，这里我们能找到基本的过滤类型："ID"、"TAG"、"CLASS"、"ATTR"、"CHILD"、"PSEUDO"，tokenize最终分类出来的type也就是这几种。

“分词”完成之后，依旧看在405行定义的Expr= Sizzle.selectors = {}。这里面能找到我们熟悉的所有选择符，每个选择符对应一个方法定义。到这里应该想到Sizzle其实是不是就是通过对selector做“分词”，打散之后再分别从Expr里面去找对应的方法来执行具体的查询或者过滤的操作?

答案基本是肯定的。但是Sizzle有更具体和巧妙的做法。再来看我认为很核心的第二个方法：

源代码1293行有一个matcherFromTokens函数：

function matcherFromTokens(tokens) { }

传入的参数正是从tokenize方法得到的。Matcher可以理解成是“匹配程序”的意思，光从字面上看这个函数起的作用就是通过tokens生成匹配程序。事实上确实如此。限于篇幅，这篇文章暂且只分享我理解到的一些Sizzle的实现原理，不贴源码。后面有时间我或者再整理一篇更详尽的源码分析的文章。

matcherFromTokens方法证实了前面的设想，它充当了selector“分词”与Expr中定义的匹配方法的串联与纽带的作用，可以说选择符的各种排列组合都是能适应的了。Sizzle巧妙的就是它没有直接将拿到的“分词”结果与Expr中的方法逐个匹配逐个执行，而是先根据规则组合出一个大的匹配方法，最后一步执行。但是组合之后怎么执行的，还得再看关键的第三个方法：

源代码1350行有一个superMatcher方法：

superMatcher = function( seed, context, xml, results, expandContext ) { }

这个方法并不是一个直接定义的方法，而是通过1345行的matcherFromGroupMatchers( elementMatchers, setMatchers )方法return出来的，但是最后执行起重要作用的是它。

superMatcher方法会根据参数seed、expandContext和context确定一个起始的查询范围，有可能是直接从seed中查询过滤，也有可能在context或者context的父节点范围内。如果不是从seed开始，那么它会先执行Expr.find["TAG"]( "*", expandContext && context.parentNode || context )这句代码等到一个elems集合（数组）。然后对elems做一个遍历，对里面的元素逐个使用预先生成的matcher方法做匹配，如果结果为true的则直接将元素堆入返回结果集里面。

好吧，看到这里matcher方法原来运行的结果都是bool值，我们再返回405行看一下Expr里面filter包含的方法，都是返回bool值的。包括PSEUDO（伪类）对应的更多的伪类方法都一样。似乎有点颠覆我最初的设想，它原来不是一层一层往下查，却有点倒回去向上做匹配、过滤的意思。Expr里面只有find和preFilter返回的是集合。

尽管到这里暂时还带着一点疑问，就是最后它为什么用的是逐个匹配、过滤的方