Simple Dom Css Selector Engine

时间：2010-09-25 来源：燃烧的2B

　　每一个css选择器引擎的核心部分都存在一个纯DOM实现(pure-DOM implementation)，通过对CSS选择器进行简单的解析后，利用一些已有且常见的DOM方法（例如getElementById或者getElementsByTagName)查找并匹配相应元素. 　　采用DOM实现选择器引擎的几个理由:
　　　　1.相比IE8对诸如querySelectorAll的实现，ie6,ie7缺乏对XPath、Selectors API 的支持，所以其选择器必须采用DOM实现. 　　　　2.为了向后兼容，好比说你想对那些不支持Selectors API和XPath(如 Safari 2)的浏览器提供一个平稳退化的方案，那么请用DOM实现你的选择器. 　　　　3.至于速度，有相当一部分选择器采用DOM处理起来会十分迅速（例如通过ID查找元素). 　　出于对以上几点的考虑，这里介绍两种可行的CSS选择器引擎实现方案：自上而下(Top Down ，以下简称TD), 自底向上(Bottom Up, 以下简称 BU) 　　TD引擎，常见于现今大多数JavaScript库，对CSS选择器按照‘从左至右’的顺序逐一解析，并试图根据每一个分割后的CSS选择器片段在文档中查找并匹配元素，是一种较为优良的选择器引擎解决方案. 　　　　举例来说，对给定CSS选择器‘div span', TD引擎会首先在当前页面内查找所有div元素，随后在每个div内部查找span元素. 　　　　在开发一个选择器引擎时有一些事情是要注意的. 　　　　1.在作为匹配结果的元素集合中，元素应该按照在文档中出现的先后顺序排序. 　　　　2.在作为匹配结果的元素集合中，不应该有重复元素出现. 　　有时这些所谓的‘陷阱’在开发一个TD引擎的过程中会变得相当棘手，考虑以下代码，好比说我们想实现一个'div span'选择器引擎.

 1 <div>
 2 　　 <div>
 3 　　　　 <span>Span</span>
 4 　　 </div>
 5  </div>
 6  
 7 window.onload = function(){
 8 　　 function find(selector, root){
 9 　　　　root = root || document;
10 
11　　　　  var parts = selector.split(""),
12 　　　　　　query = parts[0],
13 　　　　　　rest = parts.slice(1).join(""),
14　　　　　　 elems = root.getElementsByTagName( query ),
15 　　　　　　results = [];
16 
17 　　　　 for ( var i = 0; i < elems.length; i++ ) {
18 　　　　　　 if ( rest ) {
19 　　　　　　　　results = results.concat( find(rest, elems[i]) );
20 　　　　　　} else {
21 　　　　　　　　results.push( elems[i] );
22 　　　　　　}
23 　　　　}
24 
25 　　　　 return results;
26 　　}
27 
28 　　 var divs = find("div");
29 　　assert( divs.length === 2, "Correct number of divs found." );
30 
31 　　 var divs = find("div", document.body);
32 　　assert( divs.length === 2, "Correct number of divs found in body." );
33 
34 　　 var divs = find("body div");
35 　　assert( divs.length === 2, "Correct number of divs found in body." );
36 
37 　　 var spans = find("div span");
38 　　assert( spans.length === 2, "A duplicate span was found." );
39 };

　　代码清单1 A simple top down selector engine.
　　在代码清单1中，我们实现了一个简单的TD引擎（尽管它只能根据标签名称匹配元素）,一般来说选择器引擎的工作可以分为4个部分：解析、查找、筛选、递归并整合.
　　解析
　　在上一个例子中我们的解析工作仅仅简化到将一个CSS选择器（’div span')转化为一个包含字符串的数组,因为大多数选择器周围都有额外的空白，这使得我们拆分选择器变得十分容易. 　　　　但是为了应对各种可能出现的选择器表达式，我们需要些可靠的解析规则，好比说利用正则表达式,正则表达式能够对选择器中的部分字符进行捕获随后将它们拆分并分组存放.

 1 var selector = "div.class > span:not(:first-child) a[href]"
 2  var chunker = /((?:\([^\)]+\)|\^\+\]|[^ ,\(\[]+)+)(\s*,\s*)?/g;
 3  var parts = [];
 4 
 5  // Reset the position of the chunker regexp (start from beginning)
 6  chunker.lastIndex = 0;
 7 
 8  // Collect the pieces
 9  while ( (m = chunker.exec(selector)) !== null ) {
10 　　parts.push( m[1] );
11 　　 // Stop if we've countered a comma
12 　　 if ( m[2] ) {
13 　　　　extra = RegExp.rightContext;
14 　　　　 break;
15 　　}
16 }
17 
18 assert( parts.length == 4, "Our selector is broken into 4 unique parts." );
19 assert( parts[0] === "div.class", "div selector" );
20 assert( parts[1] === ">", "child selector" );
21 assert( parts[2] === "span:not(:first-child)", "span selector" );
22 assert( parts[3] === "a[href]", "a selector" );

代码清单2 A regular expression for breaking apart a CSS selector
　　当然，仅仅对选择器分组存放是远远不够的，你还需要为每一个分组中的表达式制定些额外的规则，大多数选择器引擎内部都包含一组正则表达式到函数的映射，当一个选择器中的特定部分被匹配时就会调用与之相关联的函数. 　　

　　查找
　　作为引擎的一部分，通常在页面中查找元素有多很种方法，这些方法在很大程度上取决于浏览器的内部实现. getElementById: 仅能在根节点上使用，按照指定id属性查找并返回页面中第一个相匹配的元素，IE 和 Opera也会返回页面中第一个具有相同name属性名称的元素，所以如果你仅仅想通过id查找元素并返回正确的结果，你可能需要做一些额外的验证工作. 　　　　当然如果你想获取页面中所有具有相同id的元素，这里有两种方法：　　　　1.逐一遍历页面中每一个元素并对其id属性校验从中找到满足条件的节点. 　　　　2.使用document.all['id']，它返回一个由页面中所有相同id元素构成的数组，几乎所有浏览器都支持document.all['id'](其中包括IE Opera 和Safari). 　　getElementsByTagName: 顾名思义，按照指定的标记名称(tag name)对页面进行查找并返回所匹配的元素集合，在根节点(document)或者元素节点上都可以使用它, 它通常被用来处理一些基于属性(attribute-based)而没有提供标签名称的选择器（比如说'.class' 或者 '[attr]') 　　请注意，当使用通配符'*'作为参数查找元素时，IE除了会返回元素节点外还会返回注释节点，所以为了确保返回正确的节点集合你需要做一些基本的元素过滤与筛选. 　　getElementsByName : 通常这种方法只做一件事情，查找并返回指定name属性的元素,因此它也只有在针对像诸如'[name=NAME]'类的选择器时才会派上用场. 　 getElementsByClassName : 这是最近才被一些浏览器实现的方法（Firefox 3 和 Safari 3) ,它根据类名(className)在节点的上下文中查找元素,相比原先程序员自己实现的class-selection方法，它在速度上具有巨大的优势. 　　筛选
　　我们可以把一个css选择器拆分成各个独立的区块，例如选择器'div.2b[burn]'可以拆分为三个部分，div、 .2b 、[burn]，也就是匹配所有具有burn属性且类名为2b的div. 　　第一步首先确定根节点，在代码清单1所示的选择器引擎中，对于'div'这个部分，我们使用getElementsByTagName的方法快速获取页面中所有div元素,随后我们对返回的结果过滤并筛选出具有特定类名和属性名称的元素,几乎每个选择器引擎都实现了筛选功能. 　　筛选的内容主要有属性和位置. 　　按属性筛选: 　　访问并获取Dom元素的属性(通常使用getAttribute方法)，随后对属性值进行校验，其中就包括对类名(className)的处理. 按位置筛选：　　　　诸如像‘:nth-child(even)’、‘:last-child'这样的选择符可被看做为父节点上的一组方法. 　　所有浏览器都实现了.childNodes方法(返回当前元素的一组子节点集合[NodeList]，包括文本节点、注释节点等)，一部分浏览器如IE、 Safari、 Opera、Firefox 3.1还支持.children方法，使用这两种方法能实现各种各样的位置筛选. 　　递归并整合
　　就像在代码清单1中描述的那样，选择器引擎需具备递归调用（查找所有后代子孙元素节点）以及整合查询结果的能力.

　　然而我们刚刚的实现还过于简单，在刚才返回的数组中错误得存在着两个span元素而不是一个.所以为了使选择器引擎返回的结果中没有重复的元素，我们需要做额外的校验，大多数TD选择器为了确保返回结果的唯一性都实现了不同的校验方法.

　　但对于验证元素在集合中的的唯一性,DOM本身没有为我们提供较为便捷的方法，这迫使我们必须自己实现，在这里我们逐一遍历每个元素，为每一个元素添加一个临时的uniqueID作为属性，标记该元素我们先前已处理过.

 1 <div id="test">
 2 　　 <b>Hello</b>, I'm a ninja!
 3  </div>
 4  <div id="test2"></div>
 5  
 6 (function(){
 7 　　 var run = 0;
 8 　　 this.unique = function( array ) {
 9 　　　　 var ret = [];
10 　　　　run++;
11 　　　　 for ( var i = 0, length = array.length; i < length; i++ ) {
12 　　　　　　 var elem = array[ i ];
13 　　　　　　 if ( elem.uniqueID !== run ) {
14 　　　　　　　　elem.uniqueID = run;
15 　　　　　　　　ret.push( array[ i ] );
16 　　　　　　}
17 　　　　}
18 　　　　 return ret;
19 　　};
20 })();
21 
22 window.onload = function(){
23 　　 var divs = unique( document.getElementsByTagName("div") );
24 　　assert( divs.length === 2, "No duplicates removed." );25 　　 var body = unique( [document.body, document.body] );
26 　　assert( body.length === 1, "body duplicate removed." );
27 };

　　代码清单3 Finding the unique elements in an array.

　　此类方法为数组中的每一个元素添加了一个额外的属性，标记他们已经被访问过，返回的结果是一个不包含重复元素的数组，在几乎所有javaScript库中都能找到类似的方法.

　 Buttom up selector Engine

　　如果你觉得验证元素的重复性是一件很麻烦的工作，这里还有另外一套选择器引擎方案.

　　BU（自底向上)引擎，它对css选择器的处理完全与TD引擎相反,举例来说,对给定的css选择器'div span',它会首先在页面中查找所有span元素，随后追溯每一个span元素的祖先元素，并从中查找div元素.

　　这种选择器引擎的应用并没有其他引擎来的广泛，尽管用它对一些简单的选择器处理可能非常快捷.但是由于对元素祖先节点的追溯和确认是一件十分耗时并且难以测量其规模的工作. 但无论怎样，这种简单的选择器引擎还是给我们提供了一套可以考虑的实现方案.

 1 <div>
 2 　　 <div>
 3 　　　　 <span>Span</span>
 4 　　 </div>
 5  </div>
 6  
 7 window.onload = function(){
 8 　　 function find(selector, root){
 9 　　　　root = root || document;
10 　　　　 var parts = selector.split(""),
11 　　　　　　 query = parts[parts.length - 1],
12 　　　　　　 rest = parts.slice(0,-1).join("").toUpperCase(),
13 　　　　　　 elems = root.getElementsByTagName( query ),
14 　　　　　　 results = [];
15 　　　　 for ( var i = 0; i < elems.length; i++ ) {
16 　　　　　　 if ( rest ) {
17 　　　　　　　　 var parent = elems[i].parentNode;
18 　　　　　　　　while ( parent && parent.nodeName != rest ) {
19 　　　　　　　　　　parent = parent.parentNode;
20 　　　　　　　　}
21 　　　　　　　　if ( parent ) {
22 　　　　　　　　　　results.push( elems[i] );
23 　　　　　　　　}
24 　　　　　　} else {
25 　　　　　　　　results.push( elems[i] );
26 　　　　　　}
27 　　　　}
28 　　　　return results;
29 }
30 
31 　　var divs = find("div");
32 　　assert( divs.length === 2, "Correct number of divs found." );
33 　　var divs = find("div", document.body);
34 　　assert( divs.length === 2, "Correct number of divs found in body." );
35 　　var divs = find("body div");
36 　　assert( divs.length === 2, "Correct number of divs found in body." );
37 　　var spans = find("div span");
38 　　assert( spans.length === 1, "No duplicate span was found." );
39 };

　　代码清单4 a simple bottom up selector engine

　　代码清单4显示了一个简单的BU引擎的内部结构,请注意它的祖先节点查询深度仅为1，若想要对DOM树做更为全面而深层次的查找，就必须对当前节点的深度值进行跟踪并记录，这样便需要两个记录状态的数组，其中一个数组保存需要返回的元素集合，另外一个数组则保存与当前测试节点相关的所有元素.

　　原文来自： John Resig - [秘密 of the 被阉割的 javascript 忍者] [Charpter 10 - Css Selector Engine]