【jq 源码解析2-Sizzle】

支持高级api的浏览器直接使用原生的 querySelectorAll 方法，降级处理会走 sizzle 这套解析，等于 querySelectorAll 模拟实现，通过从右往左的查找方式，最终匹配出结果。

词法解析

不支持原生 api 的浏览器，进入 tokenize 方法进行词法解析，将 $('.test span') 命令进行拆分解析，生成一个数组，生成结构如下：

对应代码大体结构：

function tokenize( selector, parseOnly ) {
    ...
    while ( soFar ) {

        // 对于 $('.test span, .test a') 进行逗号的分组
        if ( !matched || ( match = rcomma.exec( soFar ) ) ) {
            ...
        }
        // 一个聪明的变量 控制下面没有匹配时直接终止这个词法解析的过程
        matched = false;

        // >, +,  ' ', ~  解析
        if ( ( match = rcombinators.exec( soFar ) ) ) {
            matched = match.shift();
            tokens.push( {
                value: matched,
                type: match[ 0 ].replace( rtrim, " " )
            } );
            soFar = soFar.slice( matched.length );
        }

        // class tag id 等类型解析
        for ( type in Expr.filter ) {
           ....
            tokens.push( {
                value: matched,
                type: type,
                matches: match
            });
            soFar = soFar.slice( matched.length );
            ...
        }

        if ( !matched ) {
            break;
        }
    }

    ...
    // 最终返回这个结果 并存入缓存
    return tokenCache( selector, groups ).slice( 0 );
}

过滤器

拿到 token 之后进行筛选过滤处理，进入 select 函数解析出 seed （通过原生api选择出dom），剔除 select css规则的最后一项（这一项通过原生api选择dom，存入 seed） ，match匹配数组剔除最后一项，进入编译。

举例：$('.test span em')，经过词法解析后进入过滤处理，这一步处理完的数据结构如下图

对应代码：

function select( selector, context, results, seed ) {
    var i, tokens, token, type, find,
        compiled = typeof selector === "function" && selector,
        // 这里拿到第一步处理后的 token
        match = !seed && tokenize( ( selector = compiled.selector || selector ) );

    results = results || [];

    // 只有一组规则的情况 $('.test span em') $('.test span, .test em')加逗号的不会进入
    // 属于提前优化的一种处理
    if ( match.length === 1 ) {

        // id选择
        tokens = match[ 0 ] = match[ 0 ].slice( 0 );
        if ( tokens.length > 2 && ( token = tokens[ 0 ] ).type === "ID" &&
                context.nodeType === 9 && documentIsHTML && Expr.relative[ tokens[ 1 ].type ] ) {
            ...
            // 将 id 剔除
            selector = selector.slice( tokens.shift().value.length );
        }

        // 选择最后一个选择器 就是em
        while ( i-- ) {
            token = tokens[ i ];

            // 关系符 终止 + | ~ | ' ' | >
            if ( Expr.relative[ ( type = token.type ) ] ) {
                break;
            }
            if ( ( find = Expr.find[ type ] ) ) {

                // 寻找 Expr指令中的 id class tag  原生api获取dom
                if ( ( seed = find(
                    token.matches[ 0 ].replace( runescape, funescape ),
                    rsibling.test( tokens[ 0 ].type ) &&
                        testContext( context.parentNode ) || context
                ) ) ) {
                    ...
                    break;
                }
            }
        }
    }

    // 进入编译的过程
    ( compiled || compile( selector, match ) )(...);
    return results;
}

编译

编译的部分比较抽象，这里的编译不是编译原理中的那样，为了提高匹配效率使用了缓存和大量的闭包来设计这个算法。

匹配的时候是按照从右至左的顺序进行选择，和 css 的渲染规则一致，类似迷宫图从出口反着走很快就能知道整个路线。

这部分由于代码量庞大且 case 复杂，直接贴出来简化后的代码，实现 tag 选择器：$('div p span em')

//假设一个 div p span em 层级嵌套的结构

// 经过前面的两个过程之后，产生了token 和 seed 这个结果直接模拟给出相应的数据结构

// 编译函数
function compile() {
    let elementMatchers = [];
    elementMatchers.push(matcherFromTokens(match));
    // 这个是超级匹配方法，最后一步实现，源码中这里加了缓存处理
    return matcherFromGroupMatchers(elementMatchers)
}

// token 这里直接模拟数据结构
let match = [{
    matches: ["div"],
    type: "TAG",
    value: "div"
}, {
    type: " ",
    value: " "
}, {
    matches: ["p"],
    type: "TAG",
    value: "p"
},{
    type: " ",
    value: " "
},{
    matches: ["span"],
    type: "TAG",
    value: "span"
}, {
    type: " ",
    value: " "
},]
// 经过第二步获得的 seed 
const seed = document.querySelectorAll('em');

// 执行编译
compile(match)(seed);

matcherFromTokens 方法对 token 进行拆解和 Expr 指令中 filter 方法去关联：

function matcherFromTokens(tokens) {
    let matcher, matchers = [];
    tokens.map(item => {
        if (item.type === " ") {
            // 存在关系:div p 这种，一个让人头大的设计  层层闭包
            matchers = [addCombinator(elementMatcher(matchers))];
        } else {
            // 去指令集判断当前元素和选择器中给的标识是否一致，这里暂时不执行，等到最后一口气执行完
            matcher = filter[item.type].apply(null, item.matches);
            matchers.push(matcher);
        }
    })
    return elementMatcher(matchers);
}

function addCombinator(matcher) {
    return (elem) => {
        while ((elem = elem['parentNode'])) {
            if (elem.nodeType === 1) {
                // 往上查找 即根据选择器从右往左查  matcher此时是elementMatcher中返回的函数
                return matcher(elem);
            }
        }
    }
}

function elementMatcher(matchers) {
    return matchers.length > 1 ?
        //多个匹配器，需要elem符合全部匹配器规则
        function(elem, context, xml) {
            let i = matchers.length;
            //从右到左开始匹配
            while (i--) {
                //如果有一个没匹配中，那就说明该节点elem不符合规则
                if (!matchers[i](elem, context, xml)) {
                    return false;
                }
            }
            return true;
        } :
        //单个匹配器 filter
        matchers[0];
}

得到编译后的一个结果：elementMatchers，存储着普通选择器的闭包，源码中还有一个伪类选择集合 setMatchers 这里省略...

匹配

经过编译之后拿到的是一堆闭包，最后一步开始执行：

function matcherFromGroupMatchers(elementMatchers) {
    return (seed) => {
        // 存放最终匹配的结果 dom
        let results = [];
        // 遍历最后一个选择器节点，因为页面上存在多个
        [...seed].map(item => {
            let j = 0;
            // 多组选择器 有逗号的情况，本次实现只有一组
            while ( ( matcher = elementMatchers[ j++ ] ) ) {
                // 开始执行 一直回溯  所有的方法都在闭包中了 
                if (matcher(item)) {
                    results.push(item);
                    break;
                }
            }
        })
        return results;
    };
}

// 匹配结果
let res = compile(match)(seed); // [em, em]dom集合