jQuery源码剖析（八）——Sizzle选择器引擎之解析原理

<div>
  <p>
    <span class="clr">
      <input type="text" />
    </span>
  </p>
  <div class="clr">
    <input type="checkbox" name="readme" />
    <p>Hello World</p>
  </div>
</div>

Expr.relative = {
  ">": { dir: "parentNode", first: true },
  " ": { dir: "parentNode" },
  "+": { dir: "previousSibling", first: true },
  "~": { dir: "previousSibling" }
}

<div id="grandfather">
  <div id="father">
    <div id="child1"></div>
    <div id="child2"></div>
    <div id="child3"></div>
  </div>
</div>

function Sizzle( selector, context, results, seed ) {
  /* 这里一坨代码就不粘出来了 */
  //如果是单条规则的选择器，能通过直接原生接口：getElementById|getElementsByTagName|getElementsByClassName,得到的，那就直接调原生接口
  //如果是多条规则的情况，先看看浏览器有没有原生的querySelectorAll接口
 
  // All others
  //如果是低级浏览器，那没办法了，只能自己处理了。
  return select( selector.replace( rtrim, "$1" ), context, results, seed );
}
//引擎的主要入口函数
function select( selector, context, results, seed ) {
  var i, tokens, token, type, find,
    match = tokenize( selector );//记得上篇文章《jQuery源码剖析（七）——Sizzle选择器引擎之词法分析》吗
 
  if ( !seed ) {//如果外界没有指定初始集合seed了。
 
    // Try to minimize operations if there is only one group
    if ( match.length === 1 ) {//如果只是单个选择器的情况，也即是没有逗号的情况：div, p，可以特殊优化一下
 
      // Take a shortcut and set the context if the root selector is an ID
      tokens = match[0] = match[0].slice( 0 );//取出选择器Token序列
 
      if ( tokens.length > 2 && (token = tokens[0]).type === "ID" &&
          context.nodeType === 9 && !documentIsXML &&
          Expr.relative[ tokens[1].type ] ) {
 
        context = Expr.find["ID"]( token.matches[0].replace( runescape, funescape ), context )[0];
        if ( !context ) {
          return results;
        }
 
        selector = selector.slice( tokens.shift().value.length );
      }
      // Fetch a seed set for right-to-left matching
      //其中： "needsContext"= new RegExp( "^" + whitespace + "*[>+~]|:(even|odd|eq|gt|lt|nth|first|last)(?:\\(" + whitespace + "*((?:-\\d)?\\d*)" + whitespace + "*\\)|)(?=[^-]|$)", "i" )
      //即是表示如果没有一些结构伪类，这些是需要用另一种方式过滤，在之后文章再详细剖析。
      //那么就从最后一条规则开始，先找出seed集合
      i = matchExpr["needsContext"].test( selector ) ? 0 : tokens.length;
      while ( i-- ) {//从后开始向前找！
        token = tokens[i];//找到后边的规则
 
        // Abort if we hit a combinator
        //如果遇到位置规则类型，那就比较郁闷了，只能是整个DOM树节点全部去过滤扫描了
        if ( Expr.relative[ (type = token.type) ] ) {
          break;
        }
        /*
          先看看有没有搜索器find，搜索器就是浏览器一些原生的取DOM接口，简单的表述就是以下对象了
          Expr.find = {
            'ID' : context.getElementById,
            'CLASS' : context.getElementsByClassName,
            'NAME' : context.getElementsByName,
            'TAG' : context.getElementsByTagName
          }
        */
        //如果是:first-child这类伪类就没有对应的搜索器了，此时会向前提取前一条规则token
        if ( (find = Expr.find[ type ]) ) {
 
          // Search, expanding context for leading sibling combinators
          //尝试一下能否通过这个搜索器搜到符合条件的初始集合seed
          if ( (seed = find(
            token.matches[0].replace( runescape, funescape ),
            rsibling.test( tokens[0].type ) && context.parentNode || context
          )) ) {
            //如果真的搜到了
            // If seed is empty or no tokens remain, we can return early
            //把最后一条规则去除掉
            tokens.splice( i, 1 );
            selector = seed.length && toSelector( tokens );
            //看看当前剩余的选择器是否为空
            if ( !selector ) {
              //是的话，提前返回结果了。
              push.apply( results, slice.call( seed, 0 ) );
              return results;
            }
 
            //已经找到了符合条件的seed集合，此时前边还有其他规则，跳出去
            break;
          }
        }
      }
    }
  }
 
  // Compile and execute a filtering function
  // Provide `match` to avoid retokenization if we modified the selector above
  // 交由compile来生成一个称为终极匹配器
  // 通过这个匹配器过滤seed，把符合条件的结果放到results里边
  compile( selector, match )(
    seed,
    context,
    documentIsXML,
    results,
    rsibling.test( selector )
  );
  return results;
}

compile = Sizzle.compile = function( selector, group /* Internal Use Only */ ) {
  var i,
    setMatchers = [],
    elementMatchers = [],
    cached = compilerCache[ selector + " " ];
 
  if ( !cached ) {//依旧看看有没有缓存
    // Generate a function of recursive functions that can be used to check each element
    if ( !group ) {
      group = tokenize( selector );
    }
    i = group.length;//从后开始生成匹配器
    while ( i-- ) {
      //这里用matcherFromTokens来生成对应Token的匹配器
      cached = matcherFromTokens( group[i] );
      if ( cached[ expando ] ) {//什么是setMatchers，这里以后再剖析
        setMatchers.push( cached );
      } else {//普通的那些匹配器都压入了elementMatchers里边
        elementMatchers.push( cached );
      }
    }
 
    // Cache the compiled function
    //这里可以看到，是通过matcherFromGroupMatchers这个函数来生成最终的匹配器
    cached = compilerCache( selector, matcherFromGroupMatchers( elementMatchers, setMatchers ) );
  }
  //把这个终极匹配器返回到select函数中
  return cached;
};

superMatcher = function( seed, context, xml, results, expandContext ) {
  var elem, j, matcher,
    setMatched = [],
    matchedCount = 0,
    i = "0",
    unmatched = seed && [],
    outermost = expandContext != null,
    contextBackup = outermostContext,
    // We must always have either seed elements or context
    //这一步很关键！
    //如果说有初始集合seed，那用它
    //如果没有，那只能把整个DOM树节点取出来过滤了，可以看出选择器最右边应该写一个
    elems = seed || byElement && Expr.find["TAG"]( "*", expandContext && context.parentNode || context ),
    // Use integer dirruns iff this is the outermost matcher
    dirrunsUnique = (dirruns += contextBackup == null ? 1 : Math.random() || 0.1);
 
  //这里的outermost，不了解是做啥用途的，请看懂的同志们告知一下。
  if ( outermost ) {
    outermostContext = context !== document && context;
    cachedruns = matcherCachedRuns;
  }
 
  // Add elements passing elementMatchers directly to results
  // Keep `i` a string if there are no elements so `matchedCount` will be "00" below
  //好，开始过滤这个elems集合了！
  for ( ; (elem = elems[i]) != null; i++ ) {
    if ( byElement && elem ) {
      j = 0;
      //把所有的过滤器拿出来
      //这里的每个匹配器都是上边提到的终极匹配器，既然是终极匹配器，那为什么会有多个呢？
      //因为：div, p实际上是需要两个终极匹配器的（逗号分隔开表示有两个选择器了），:)
      while ( (matcher = elementMatchers[j++]) ) {
        //过滤这个集合的元素elem，如果符合匹配器的规则，那么就添加到结果集里边去
        if ( matcher( elem, context, xml ) ) {
          results.push( elem );
          break;
        }
      }
      if ( outermost ) {
        dirruns = dirrunsUnique;
        cachedruns = ++matcherCachedRuns;
      }
    }
 
    // Track unmatched elements for set filters
    //这里的bySet是为了跟踪setMatchers匹配器，这里以后再剖析
    if ( bySet ) {
      // They will have gone through all possible matchers
      if ( (elem = !matcher && elem) ) {
        matchedCount--;
      }
 
      // Lengthen the array for every element, matched or not
      if ( seed ) {
        unmatched.push( elem );
      }
    }
  }
 
  // Apply set filters to unmatched elements
  // 这里的bySet是为了跟踪setMatchers匹配器，这里以后再剖析
  matchedCount += i;
  if ( bySet && i !== matchedCount ) {
    j = 0;
    while ( (matcher = setMatchers[j++]) ) {
      matcher( unmatched, setMatched, context, xml );
    }
 
    if ( seed ) {
      // Reintegrate element matches to eliminate the need for sorting
      if ( matchedCount > 0 ) {
        while ( i-- ) {
          if ( !(unmatched[i] || setMatched[i]) ) {
            setMatched[i] = pop.call( results );
          }
        }
      }
 
      // Discard index placeholder values to get only actual matches
      setMatched = condense( setMatched );
    }
 
    // Add matches to results
    push.apply( results, setMatched );
 
    // Seedless set matches succeeding multiple successful matchers stipulate sorting
    if ( outermost && !seed && setMatched.length > 0 &&
      ( matchedCount + setMatchers.length ) > 1 ) {
 
      Sizzle.uniqueSort( results );
    }
  }
 
  // Override manipulation of globals by nested matchers
  if ( outermost ) {
    dirruns = dirrunsUnique;
    outermostContext = contextBackup;
  }
 
  return unmatched;
};