git.pond.sub.org Git - eow/blob - static/dojo-release-1.1.1/dojo/_base/query.js

   1 if(!dojo._hasResource["dojo._base.query"]){ //_hasResource checks added by build. Do not use _hasResource directly in your code.
   2 dojo._hasResource["dojo._base.query"] = true;
   3 dojo.provide("dojo._base.query");
   4 dojo.require("dojo._base.NodeList");
   5
   6 /*
   7         dojo.query() architectural overview:
   8
   9                 dojo.query is a relatively full-featured CSS3 query library. It is
  10                 designed to take any valid CSS3 selector and return the nodes matching
  11                 the selector. To do this quickly, it processes queries in several
  12                 steps, applying caching where profitable.
  13
  14                 The steps (roughly in reverse order of the way they appear in the code):
  15                         1.) check to see if we already have a "query dispatcher"
  16                                 - if so, use that with the given parameterization. Skip to step 4.
  17                         2.) attempt to determine which branch to dispatch the query to:
  18                                 - JS (optimized DOM iteration)
  19                                 - xpath (for browsers that support it and where it's fast)
  20                                 - native (not available in any browser yet)
  21                         3.) tokenize and convert to executable "query dispatcher"
  22                                 - this is where the lion's share of the complexity in the
  23                                   system lies. In the DOM version, the query dispatcher is
  24                                   assembled as a chain of "yes/no" test functions pertaining to
  25                                   a section of a simple query statement (".blah:nth-child(odd)"
  26                                   but not "div div", which is 2 simple statements). Individual
  27                                   statement dispatchers are cached (to prevent re-definition)
  28                                   as are entire dispatch chains (to make re-execution of the
  29                                   same query fast)
  30                                 - in the xpath path, tokenization yeilds a concatenation of
  31                                   parameterized xpath selectors. As with the DOM version, both
  32                                   simple selector blocks and overall evaluators are cached to
  33                                   prevent re-defintion
  34                         4.) the resulting query dispatcher is called in the passed scope (by default the top-level document)
  35                                 - for DOM queries, this results in a recursive, top-down
  36                                   evaluation of nodes based on each simple query section
  37                                 - xpath queries can, thankfully, be executed in one shot
  38                         5.) matched nodes are pruned to ensure they are unique
  39 */
  40
  41 ;(function(){
  42         // define everything in a closure for compressability reasons. "d" is an
  43         // alias to "dojo" since it's so frequently used. This seems a
  44         // transformation that the build system could perform on a per-file basis.
  45
  46         ////////////////////////////////////////////////////////////////////////
  47         // Utility code
  48         ////////////////////////////////////////////////////////////////////////
  49
  50         var d = dojo;
  51         var childNodesName = dojo.isIE ? "children" : "childNodes";
  52         var caseSensitive = false;
  53
  54         var getQueryParts = function(query){
  55                 // summary: state machine for query tokenization
  56                 if(">~+".indexOf(query.charAt(query.length-1)) >= 0){
  57                         query += " *"
  58                 }
  59                 query += " "; // ensure that we terminate the state machine
  60
  61                 var ts = function(s, e){
  62                         return d.trim(query.slice(s, e));
  63                 }
  64
  65                 // the overall data graph of the full query, as represented by queryPart objects
  66                 var qparts = [];
  67                 // state keeping vars
  68                 var inBrackets = -1;
  69                 var inParens = -1;
  70                 var inMatchFor = -1;
  71                 var inPseudo = -1;
  72                 var inClass = -1;
  73                 var inId = -1;
  74                 var inTag = -1;
  75                 var lc = ""; // the last character
  76                 var cc = ""; // the current character
  77                 var pStart;
  78                 // iteration vars
  79                 var x = 0; // index in the query
  80                 var ql = query.length;
  81                 var currentPart = null; // data structure representing the entire clause
  82                 var _cp = null; // the current pseudo or attr matcher
  83
  84                 var endTag = function(){
  85                         if(inTag >= 0){
  86                                 var tv = (inTag == x) ? null : ts(inTag, x).toLowerCase();
  87                                 currentPart[ (">~+".indexOf(tv) < 0) ? "tag" : "oper" ] = tv;
  88                                 inTag = -1;
  89                         }
  90                 }
  91
  92                 var endId = function(){
  93                         if(inId >= 0){
  94                                 currentPart.id = ts(inId, x).replace(/\\/g, "");
  95                                 inId = -1;
  96                         }
  97                 }
  98
  99                 var endClass = function(){
 100                         if(inClass >= 0){
 101                                 currentPart.classes.push(ts(inClass+1, x).replace(/\\/g, ""));
 102                                 inClass = -1;
 103                         }
 104                 }
 105
 106                 var endAll = function(){
 107                         endId(); endTag(); endClass();
 108                 }
 109
 110                 for(; lc=cc, cc=query.charAt(x),x<ql; x++){
 111                         if(lc == "\\"){ continue; }
 112                         if(!currentPart){
 113                                 // NOTE: I hate all this alloc, but it's shorter than writing tons of if's
 114                                 pStart = x;
 115                                 currentPart = {
 116                                         query: null,
 117                                         pseudos: [],
 118                                         attrs: [],
 119                                         classes: [],
 120                                         tag: null,
 121                                         oper: null,
 122                                         id: null
 123                                 };
 124                                 inTag = x;
 125                         }
 126
 127                         if(inBrackets >= 0){
 128                                 // look for a the close first
 129                                 if(cc == "]"){
 130                                         if(!_cp.attr){
 131                                                 _cp.attr = ts(inBrackets+1, x);
 132                                         }else{
 133                                                 _cp.matchFor = ts((inMatchFor||inBrackets+1), x);
 134                                         }
 135                                         var cmf = _cp.matchFor;
 136                                         if(cmf){
 137                                                 if(     (cmf.charAt(0) == '"') || (cmf.charAt(0)  == "'") ){
 138                                                         _cp.matchFor = cmf.substring(1, cmf.length-1);
 139                                                 }
 140                                         }
 141                                         currentPart.attrs.push(_cp);
 142                                         _cp = null; // necessaray?
 143                                         inBrackets = inMatchFor = -1;
 144                                 }else if(cc == "="){
 145                                         var addToCc = ("|~^$*".indexOf(lc) >=0 ) ? lc : "";
 146                                         _cp.type = addToCc+cc;
 147                                         _cp.attr = ts(inBrackets+1, x-addToCc.length);
 148                                         inMatchFor = x+1;
 149                                 }
 150                                 // now look for other clause parts
 151                         }else if(inParens >= 0){
 152                                 if(cc == ")"){
 153                                         if(inPseudo >= 0){
 154                                                 _cp.value = ts(inParens+1, x);
 155                                         }
 156                                         inPseudo = inParens = -1;
 157                                 }
 158                         }else if(cc == "#"){
 159                                 endAll();
 160                                 inId = x+1;
 161                         }else if(cc == "."){
 162                                 endAll();
 163                                 inClass = x;
 164                         }else if(cc == ":"){
 165                                 endAll();
 166                                 inPseudo = x;
 167                         }else if(cc == "["){
 168                                 endAll();
 169                                 inBrackets = x;
 170                                 _cp = {
 171                                         /*=====
 172                                         attr: null, type: null, matchFor: null
 173                                         =====*/
 174                                 };
 175                         }else if(cc == "("){
 176                                 if(inPseudo >= 0){
 177                                         _cp = {
 178                                                 name: ts(inPseudo+1, x),
 179                                                 value: null
 180                                         }
 181                                         currentPart.pseudos.push(_cp);
 182                                 }
 183                                 inParens = x;
 184                         }else if(cc == " " && lc != cc){
 185                                 // note that we expect the string to be " " terminated
 186                                 endAll();
 187                                 if(inPseudo >= 0){
 188                                         currentPart.pseudos.push({ name: ts(inPseudo+1, x) });
 189                                 }
 190                                 currentPart.hasLoops = (
 191                                                 currentPart.pseudos.length ||
 192                                                 currentPart.attrs.length ||
 193                                                 currentPart.classes.length      );
 194                                 currentPart.query = ts(pStart, x);
 195                                 currentPart.tag = (currentPart["oper"]) ? null : (currentPart.tag || "*");
 196                                 qparts.push(currentPart);
 197                                 currentPart = null;
 198                         }
 199                 }
 200                 return qparts;
 201         };
 202
 203
 204         ////////////////////////////////////////////////////////////////////////
 205         // XPath query code
 206         ////////////////////////////////////////////////////////////////////////
 207
 208         // this array is a lookup used to generate an attribute matching function.
 209         // There is a similar lookup/generator list for the DOM branch with similar
 210         // calling semantics.
 211         var xPathAttrs = {
 212                 "*=": function(attr, value){
 213                         return "[contains(@"+attr+", '"+ value +"')]";
 214                 },
 215                 "^=": function(attr, value){
 216                         return "[starts-with(@"+attr+", '"+ value +"')]";
 217                 },
 218                 "$=": function(attr, value){
 219                         return "[substring(@"+attr+", string-length(@"+attr+")-"+(value.length-1)+")='"+value+"']";
 220                 },
 221                 "~=": function(attr, value){
 222                         return "[contains(concat(' ',@"+attr+",' '), ' "+ value +" ')]";
 223                 },
 224                 "|=": function(attr, value){
 225                         return "[contains(concat(' ',@"+attr+",' '), ' "+ value +"-')]";
 226                 },
 227                 "=": function(attr, value){
 228                         return "[@"+attr+"='"+ value +"']";
 229                 }
 230         };
 231
 232         // takes a list of attribute searches, the overall query, a function to
 233         // generate a default matcher, and a closure-bound method for providing a
 234         // matching function that generates whatever type of yes/no distinguisher
 235         // the query method needs. The method is a bit tortured and hard to read
 236         // because it needs to be used in both the XPath and DOM branches.
 237         var handleAttrs = function(     attrList,
 238                                                                 query,
 239                                                                 getDefault,
 240                                                                 handleMatch){
 241                 d.forEach(query.attrs, function(attr){
 242                         var matcher;
 243                         // type, attr, matchFor
 244                         if(attr.type && attrList[attr.type]){
 245                                 matcher = attrList[attr.type](attr.attr, attr.matchFor);
 246                         }else if(attr.attr.length){
 247                                 matcher = getDefault(attr.attr);
 248                         }
 249                         if(matcher){ handleMatch(matcher); }
 250                 });
 251         }
 252
 253         var buildPath = function(query){
 254                 var xpath = ".";
 255                 var qparts = getQueryParts(d.trim(query));
 256                 while(qparts.length){
 257                         var tqp = qparts.shift();
 258                         var prefix;
 259                         var postfix = "";
 260                         if(tqp.oper == ">"){
 261                                 prefix = "/";
 262                                 // prefix = "/child::*";
 263                                 tqp = qparts.shift();
 264                         }else if(tqp.oper == "~"){
 265                                 prefix = "/following-sibling::"; // get element following siblings
 266                                 tqp = qparts.shift();
 267                         }else if(tqp.oper == "+"){
 268                                 // FIXME:
 269                                 //              fails when selecting subsequent siblings by node type
 270                                 //              because the position() checks the position in the list
 271                                 //              of matching elements and not the localized siblings
 272                                 prefix = "/following-sibling::";
 273                                 postfix = "[position()=1]";
 274                                 tqp = qparts.shift();
 275                         }else{
 276                                 prefix = "//";
 277                                 // prefix = "/descendant::*"
 278                         }
 279
 280                         // get the tag name (if any)
 281
 282                         xpath += prefix + tqp.tag + postfix;
 283
 284                         // check to see if it's got an id. Needs to come first in xpath.
 285                         if(tqp.id){
 286                                 xpath += "[@id='"+tqp.id+"'][1]";
 287                         }
 288
 289                         d.forEach(tqp.classes, function(cn){
 290                                 var cnl = cn.length;
 291                                 var padding = " ";
 292                                 if(cn.charAt(cnl-1) == "*"){
 293                                         padding = ""; cn = cn.substr(0, cnl-1);
 294                                 }
 295                                 xpath +=
 296                                         "[contains(concat(' ',@class,' '), ' "+
 297                                         cn + padding + "')]";
 298                         });
 299
 300                         handleAttrs(xPathAttrs, tqp,
 301                                 function(condition){
 302                                                 return "[@"+condition+"]";
 303                                 },
 304                                 function(matcher){
 305                                         xpath += matcher;
 306                                 }
 307                         );
 308
 309                         // FIXME: need to implement pseudo-class checks!!
 310                 };
 311                 return xpath;
 312         };
 313
 314         var _xpathFuncCache = {};
 315         var getXPathFunc = function(path){
 316                 if(_xpathFuncCache[path]){
 317                         return _xpathFuncCache[path];
 318                 }
 319
 320                 var doc = d.doc;
 321                 // don't need to memoize. The closure scope handles it for us.
 322                 var xpath = buildPath(path);
 323
 324                 var tf = function(parent){
 325                         // XPath query strings are memoized.
 326                         var ret = [];
 327                         var xpathResult;
 328                         try{
 329                                 xpathResult = doc.evaluate(xpath, parent, null,
 330                                                                                                 // XPathResult.UNORDERED_NODE_ITERATOR_TYPE, null);
 331                                                                                                 XPathResult.ANY_TYPE, null);
 332                         }catch(e){
 333                                 console.debug("failure in exprssion:", xpath, "under:", parent);
 334                                 console.debug(e);
 335                         }
 336                         var result = xpathResult.iterateNext();
 337                         while(result){
 338                                 ret.push(result);
 339                                 result = xpathResult.iterateNext();
 340                         }
 341                         return ret;
 342                 }
 343                 return _xpathFuncCache[path] = tf;
 344         };
 345
 346         /*
 347         d.xPathMatch = function(query){
 348                 // XPath based DOM query system. Handles a small subset of CSS
 349                 // selectors, subset is identical to the non-XPath version of this
 350                 // function.
 351
 352                 return getXPathFunc(query)();
 353         }
 354         */
 355
 356         ////////////////////////////////////////////////////////////////////////
 357         // DOM query code
 358         ////////////////////////////////////////////////////////////////////////
 359
 360         var _filtersCache = {};
 361         var _simpleFiltersCache = {};
 362
 363         // the basic building block of the yes/no chaining system. agree(f1, f2)
 364         // generates a new function which returns the boolean results of both of
 365         // the passed functions to a single logical-anded result.
 366         var agree = function(first, second){
 367                 if(!first){ return second; }
 368                 if(!second){ return first; }
 369
 370                 return function(){
 371                         return first.apply(window, arguments) && second.apply(window, arguments);
 372                 }
 373         }
 374
 375         var _childElements = function(root){
 376                 var ret = [];
 377                 var te, x=0, tret = root[childNodesName];
 378                 while(te=tret[x++]){
 379                         if(te.nodeType == 1){ ret.push(te); }
 380                 }
 381                 return ret;
 382         }
 383
 384         var _nextSiblings = function(root, single){
 385                 var ret = [];
 386                 var te = root;
 387                 while(te = te.nextSibling){
 388                         if(te.nodeType == 1){
 389                                 ret.push(te);
 390                                 if(single){ break; }
 391                         }
 392                 }
 393                 return ret;
 394         }
 395
 396         var _filterDown = function(element, queryParts, matchArr, idx){
 397                 // NOTE:
 398                 //              in the fast path! this function is called recursively and for
 399                 //              every run of a query.
 400                 var nidx = idx+1;
 401                 var isFinal = (queryParts.length == nidx);
 402                 var tqp = queryParts[idx];
 403
 404                 // see if we can constrain our next level to direct children
 405                 if(tqp.oper){
 406                         var ecn = (tqp.oper == ">") ?
 407                                 _childElements(element) :
 408                                 _nextSiblings(element, (tqp.oper == "+"));
 409
 410                         if(!ecn || !ecn.length){
 411                                 return;
 412                         }
 413                         nidx++;
 414                         isFinal = (queryParts.length == nidx);
 415                         // kinda janky, too much array alloc
 416                         var tf = getFilterFunc(queryParts[idx+1]);
 417                         // for(var x=ecn.length-1, te; x>=0, te=ecn[x]; x--){
 418                         for(var x=0, ecnl=ecn.length, te; x<ecnl, te=ecn[x]; x++){
 419                                 if(tf(te)){
 420                                         if(isFinal){
 421                                                 matchArr.push(te);
 422                                         }else{
 423                                                 _filterDown(te, queryParts, matchArr, nidx);
 424                                         }
 425                                 }
 426                                 /*
 427                                 if(x==0){
 428                                         break;
 429                                 }
 430                                 */
 431                         }
 432                 }
 433
 434                 // otherwise, keep going down, unless we'er at the end
 435                 var candidates = getElementsFunc(tqp)(element);
 436                 if(isFinal){
 437                         while(candidates.length){
 438                                 matchArr.push(candidates.shift());
 439                         }
 440                         /*
 441                         candidates.unshift(0, matchArr.length-1);
 442                         matchArr.splice.apply(matchArr, candidates);
 443                         */
 444                 }else{
 445                         // if we're not yet at the bottom, keep going!
 446                         while(candidates.length){
 447                                 _filterDown(candidates.shift(), queryParts, matchArr, nidx);
 448                         }
 449                 }
 450         }
 451
 452         var filterDown = function(elements, queryParts){
 453                 var ret = [];
 454
 455                 // for every root, get the elements that match the descendant selector
 456                 // for(var x=elements.length-1, te; x>=0, te=elements[x]; x--){
 457                 var x = elements.length - 1, te;
 458                 while(te = elements[x--]){
 459                         _filterDown(te, queryParts, ret, 0);
 460                 }
 461                 return ret;
 462         }
 463
 464         var getFilterFunc = function(q){
 465                 // note: query can't have spaces!
 466                 if(_filtersCache[q.query]){
 467                         return _filtersCache[q.query];
 468                 }
 469                 var ff = null;
 470
 471                 // does it have a tagName component?
 472                 if(q.tag){
 473                         if(q.tag == "*"){
 474                                 ff = agree(ff,
 475                                         function(elem){
 476                                                 return (elem.nodeType == 1);
 477                                         }
 478                                 );
 479                         }else{
 480                                 // tag name match
 481                                 ff = agree(ff,
 482                                         function(elem){
 483                                                 return (
 484                                                         (elem.nodeType == 1) &&
 485                                                         (q.tag == elem.tagName.toLowerCase())
 486                                                 );
 487                                                 // return isTn;
 488                                         }
 489                                 );
 490                         }
 491                 }
 492
 493                 // does the node have an ID?
 494                 if(q.id){
 495                         ff = agree(ff,
 496                                 function(elem){
 497                                         return (
 498                                                 (elem.nodeType == 1) &&
 499                                                 (elem.id == q.id)
 500                                         );
 501                                 }
 502                         );
 503                 }
 504
 505                 if(q.hasLoops){
 506                         // if we have other query param parts, make sure we add them to the
 507                         // filter chain
 508                         ff = agree(ff, getSimpleFilterFunc(q));
 509                 }
 510
 511                 return _filtersCache[q.query] = ff;
 512         }
 513
 514         var getNodeIndex = function(node){
 515                 // NOTE:
 516                 //              we could have a more accurate caching mechanism by invalidating
 517                 //              caches after the query has finished, but I think that'd lead to
 518                 //              significantly more cache churn than the cache would provide
 519                 //              value for in the common case. Generally, we're more
 520                 //              conservative (and therefore, more accurate) than jQuery and
 521                 //              DomQuery WRT node node indexes, but there may be corner cases
 522                 //              in which we fall down.  How much we care about them is TBD.
 523
 524                 var pn = node.parentNode;
 525                 var pnc = pn.childNodes;
 526
 527                 // check to see if we can trust the cache. If not, re-key the whole
 528                 // thing and return our node match from that.
 529
 530                 var nidx = -1;
 531                 var child = pn.firstChild;
 532                 if(!child){
 533                         return nidx;
 534                 }
 535
 536                 var ci = node["__cachedIndex"];
 537                 var cl = pn["__cachedLength"];
 538
 539                 // only handle cache building if we've gone out of sync
 540                 if(((typeof cl == "number")&&(cl != pnc.length))||(typeof ci != "number")){
 541                         // rip though the whole set, building cache indexes as we go
 542                         pn["__cachedLength"] = pnc.length;
 543                         var idx = 1;
 544                         do{
 545                                 // we only assign indexes for nodes with nodeType == 1, as per:
 546                                 //              http://www.w3.org/TR/css3-selectors/#nth-child-pseudo
 547                                 // only elements are counted in the search order, and they
 548                                 // begin at 1 for the first child's index
 549
 550                                 if(child === node){
 551                                         nidx = idx;
 552                                 }
 553                                 if(child.nodeType == 1){
 554                                         child["__cachedIndex"] = idx;
 555                                         idx++;
 556                                 }
 557                                 child = child.nextSibling;
 558                         }while(child);
 559                 }else{
 560                         // NOTE:
 561                         //              could be incorrect in some cases (node swaps involving the
 562                         //              passed node, etc.), but we ignore those due to the relative
 563                         //              unlikelihood of that occuring
 564                         nidx = ci;
 565                 }
 566                 return nidx;
 567         }
 568
 569         var firedCount = 0;
 570
 571         var blank = "";
 572         var _getAttr = function(elem, attr){
 573                 if(attr == "class"){
 574                         return elem.className || blank;
 575                 }
 576                 if(attr == "for"){
 577                         return elem.htmlFor || blank;
 578                 }
 579                 return elem.getAttribute(attr, 2) || blank;
 580         }
 581
 582         var attrs = {
 583                 "*=": function(attr, value){
 584                         return function(elem){
 585                                 // E[foo*="bar"]
 586                                 //              an E element whose "foo" attribute value contains
 587                                 //              the substring "bar"
 588                                 return (_getAttr(elem, attr).indexOf(value)>=0);
 589                         }
 590                 },
 591                 "^=": function(attr, value){
 592                         // E[foo^="bar"]
 593                         //              an E element whose "foo" attribute value begins exactly
 594                         //              with the string "bar"
 595                         return function(elem){
 596                                 return (_getAttr(elem, attr).indexOf(value)==0);
 597                         }
 598                 },
 599                 "$=": function(attr, value){
 600                         // E[foo$="bar"]
 601                         //              an E element whose "foo" attribute value ends exactly
 602                         //              with the string "bar"
 603                         var tval = " "+value;
 604                         return function(elem){
 605                                 var ea = " "+_getAttr(elem, attr);
 606                                 return (ea.lastIndexOf(value)==(ea.length-value.length));
 607                         }
 608                 },
 609                 "~=": function(attr, value){
 610                         // E[foo~="bar"]
 611                         //              an E element whose "foo" attribute value is a list of
 612                         //              space-separated values, one of which is exactly equal
 613                         //              to "bar"
 614
 615                         // return "[contains(concat(' ',@"+attr+",' '), ' "+ value +" ')]";
 616                         var tval = " "+value+" ";
 617                         return function(elem){
 618                                 var ea = " "+_getAttr(elem, attr)+" ";
 619                                 return (ea.indexOf(tval)>=0);
 620                         }
 621                 },
 622                 "|=": function(attr, value){
 623                         // E[hreflang|="en"]
 624                         //              an E element whose "hreflang" attribute has a
 625                         //              hyphen-separated list of values beginning (from the
 626                         //              left) with "en"
 627                         var valueDash = " "+value+"-";
 628                         return function(elem){
 629                                 var ea = " "+(elem.getAttribute(attr, 2) || "");
 630                                 return (
 631                                         (ea == value) ||
 632                                         (ea.indexOf(valueDash)==0)
 633                                 );
 634                         }
 635                 },
 636                 "=": function(attr, value){
 637                         return function(elem){
 638                                 return (_getAttr(elem, attr) == value);
 639                         }
 640                 }
 641         };
 642
 643         var pseudos = {
 644                 "first-child": function(name, condition){
 645                         return function(elem){
 646                                 if(elem.nodeType != 1){ return false; }
 647                                 // check to see if any of the previous siblings are elements
 648                                 var fc = elem.previousSibling;
 649                                 while(fc && (fc.nodeType != 1)){
 650                                         fc = fc.previousSibling;
 651                                 }
 652                                 return (!fc);
 653                         }
 654                 },
 655                 "last-child": function(name, condition){
 656                         return function(elem){
 657                                 if(elem.nodeType != 1){ return false; }
 658                                 // check to see if any of the next siblings are elements
 659                                 var nc = elem.nextSibling;
 660                                 while(nc && (nc.nodeType != 1)){
 661                                         nc = nc.nextSibling;
 662                                 }
 663                                 return (!nc);
 664                         }
 665                 },
 666                 "empty": function(name, condition){
 667                         return function(elem){
 668                                 // DomQuery and jQuery get this wrong, oddly enough.
 669                                 // The CSS 3 selectors spec is pretty explicit about
 670                                 // it, too.
 671                                 var cn = elem.childNodes;
 672                                 var cnl = elem.childNodes.length;
 673                                 // if(!cnl){ return true; }
 674                                 for(var x=cnl-1; x >= 0; x--){
 675                                         var nt = cn[x].nodeType;
 676                                         if((nt == 1)||(nt == 3)){ return false; }
 677                                 }
 678                                 return true;
 679                         }
 680                 },
 681                 "contains": function(name, condition){
 682                         return function(elem){
 683                                 // FIXME: I dislike this version of "contains", as
 684                                 // whimsical attribute could set it off. An inner-text
 685                                 // based version might be more accurate, but since
 686                                 // jQuery and DomQuery also potentially get this wrong,
 687                                 // I'm leaving it for now.
 688                                 return (elem.innerHTML.indexOf(condition) >= 0);
 689                         }
 690                 },
 691                 "not": function(name, condition){
 692                         var ntf = getFilterFunc(getQueryParts(condition)[0]);
 693                         return function(elem){
 694                                 return (!ntf(elem));
 695                         }
 696                 },
 697                 "nth-child": function(name, condition){
 698                         var pi = parseInt;
 699                         if(condition == "odd"){
 700                                 return function(elem){
 701                                         return (
 702                                                 ((getNodeIndex(elem)) % 2) == 1
 703                                         );
 704                                 }
 705                         }else if((condition == "2n")||
 706                                 (condition == "even")){
 707                                 return function(elem){
 708                                         return ((getNodeIndex(elem) % 2) == 0);
 709                                 }
 710                         }else if(condition.indexOf("0n+") == 0){
 711                                 var ncount = pi(condition.substr(3));
 712                                 return function(elem){
 713                                         return (elem.parentNode[childNodesName][ncount-1] === elem);
 714                                 }
 715                         }else if(       (condition.indexOf("n+") > 0) &&
 716                                                 (condition.length > 3) ){
 717                                 var tparts = condition.split("n+", 2);
 718                                 var pred = pi(tparts[0]);
 719                                 var idx = pi(tparts[1]);
 720                                 return function(elem){
 721                                         return ((getNodeIndex(elem) % pred) == idx);
 722                                 }
 723                         }else if(condition.indexOf("n") == -1){
 724                                 var ncount = pi(condition);
 725                                 return function(elem){
 726                                         return (getNodeIndex(elem) == ncount);
 727                                 }
 728                         }
 729                 }
 730         };
 731
 732         var defaultGetter = (d.isIE) ? function(cond){
 733                 var clc = cond.toLowerCase();
 734                 return function(elem){
 735                         return elem[cond]||elem[clc];
 736                 }
 737         } : function(cond){
 738                 return function(elem){
 739                         return (elem && elem.getAttribute && elem.hasAttribute(cond));
 740                 }
 741         };
 742
 743         var getSimpleFilterFunc = function(query){
 744
 745                 var fcHit = (_simpleFiltersCache[query.query]||_filtersCache[query.query]);
 746                 if(fcHit){ return fcHit; }
 747
 748                 var ff = null;
 749
 750                 // the only case where we'll need the tag name is if we came from an ID query
 751                 if(query.id){ // do we have an ID component?
 752                         if(query.tag != "*"){
 753                                 ff = agree(ff, function(elem){
 754                                         return (elem.tagName.toLowerCase() == query.tag);
 755                                 });
 756                         }
 757                 }
 758
 759                 // if there's a class in our query, generate a match function for it
 760                 d.forEach(query.classes, function(cname, idx, arr){
 761                         // get the class name
 762                         var isWildcard = cname.charAt(cname.length-1) == "*";
 763                         if(isWildcard){
 764                                 cname = cname.substr(0, cname.length-1);
 765                         }
 766                         // I dislike the regex thing, even if memozied in a cache, but it's VERY short
 767                         var re = new RegExp("(?:^|\\s)" + cname + (isWildcard ? ".*" : "") + "(?:\\s|$)");
 768                         ff = agree(ff, function(elem){
 769                                 return re.test(elem.className);
 770                         });
 771                         ff.count = idx;
 772                 });
 773
 774                 d.forEach(query.pseudos, function(pseudo){
 775                         if(pseudos[pseudo.name]){
 776                                 ff = agree(ff, pseudos[pseudo.name](pseudo.name, pseudo.value));
 777                         }
 778                 });
 779
 780                 handleAttrs(attrs, query, defaultGetter,
 781                         function(tmatcher){ ff = agree(ff, tmatcher); }
 782                 );
 783                 if(!ff){
 784                         ff = function(){ return true; };
 785                 }
 786                 return _simpleFiltersCache[query.query] = ff;
 787         }
 788
 789         var _getElementsFuncCache = { };
 790
 791         var getElementsFunc = function(query, root){
 792                 var fHit = _getElementsFuncCache[query.query];
 793                 if(fHit){ return fHit; }
 794
 795                 // NOTE: this function is in the fast path! not memoized!!!
 796
 797                 // the query doesn't contain any spaces, so there's only so many
 798                 // things it could be
 799
 800                 if(query.id && !query.hasLoops && !query.tag){
 801                         // ID-only query. Easy.
 802                         return _getElementsFuncCache[query.query] = function(root){
 803                                 // FIXME: if root != document, check for parenting!
 804                                 return [ d.byId(query.id) ];
 805                         }
 806                 }
 807
 808                 var filterFunc = getSimpleFilterFunc(query);
 809
 810                 var retFunc;
 811                 if(query.tag && query.id && !query.hasLoops){
 812                         // we got a filtered ID search (e.g., "h4#thinger")
 813                         retFunc = function(root){
 814                                 var te = d.byId(query.id);
 815                                 if(filterFunc(te)){
 816                                         return [ te ];
 817                                 }
 818                         }
 819                 }else{
 820                         var tret;
 821
 822                         if(!query.hasLoops){
 823                                 // it's just a plain-ol elements-by-tag-name query from the root
 824                                 retFunc = function(root){
 825                                         var ret = [];
 826                                         var te, x=0, tret = root.getElementsByTagName(query.tag);
 827                                         while(te=tret[x++]){
 828                                                 ret.push(te);
 829                                         }
 830                                         return ret;
 831                                 }
 832                         }else{
 833                                 retFunc = function(root){
 834                                         var ret = [];
 835                                         var te, x=0, tret = root.getElementsByTagName(query.tag);
 836                                         while(te=tret[x++]){
 837                                                 if(filterFunc(te)){
 838                                                         ret.push(te);
 839                                                 }
 840                                         }
 841                                         return ret;
 842                                 }
 843                         }
 844                 }
 845                 return _getElementsFuncCache[query.query] = retFunc;
 846         }
 847
 848         var _partsCache = {};
 849
 850         ////////////////////////////////////////////////////////////////////////
 851         // the query runner
 852         ////////////////////////////////////////////////////////////////////////
 853
 854         // this is the second level of spliting, from full-length queries (e.g.,
 855         // "div.foo .bar") into simple query expressions (e.g., ["div.foo",
 856         // ".bar"])
 857         var _queryFuncCache = {
 858                 "*": d.isIE ?
 859                         function(root){
 860                                         return root.all;
 861                         } :
 862                         function(root){
 863                                  return root.getElementsByTagName("*");
 864                         },
 865                 "~": _nextSiblings,
 866                 "+": function(root){ return _nextSiblings(root, true); },
 867                 ">": _childElements
 868         };
 869
 870         var getStepQueryFunc = function(query){
 871                 // if it's trivial, get a fast-path dispatcher
 872                 var qparts = getQueryParts(d.trim(query));
 873                 // if(query[query.length-1] == ">"){ query += " *"; }
 874                 if(qparts.length == 1){
 875                         var tt = getElementsFunc(qparts[0]);
 876                         tt.nozip = true;
 877                         return tt;
 878                 }
 879
 880                 // otherwise, break it up and return a runner that iterates over the parts recursively
 881                 var sqf = function(root){
 882                         var localQueryParts = qparts.slice(0); // clone the src arr
 883                         var candidates;
 884                         if(localQueryParts[0].oper == ">"){ // FIXME: what if it's + or ~?
 885                                 candidates = [ root ];
 886                                 // root = document;
 887                         }else{
 888                                 candidates = getElementsFunc(localQueryParts.shift())(root);
 889                         }
 890                         return filterDown(candidates, localQueryParts);
 891                 }
 892                 return sqf;
 893         }
 894
 895         // a specialized method that implements our primoridal "query optimizer".
 896         // This allows us to dispatch queries to the fastest subsystem we can get.
 897         var _getQueryFunc = (
 898                 // NOTE:
 899                 //              XPath on the Webkit nighlies is slower than it's DOM iteration
 900                 //              for most test cases
 901                 // FIXME:
 902                 //              we should try to capture some runtime speed data for each query
 903                 //              function to determine on the fly if we should stick w/ the
 904                 //              potentially optimized variant or if we should try something
 905                 //              new.
 906                 (document["evaluate"] && !d.isSafari) ?
 907                 function(query){
 908                         // has xpath support that's faster than DOM
 909                         var qparts = query.split(" ");
 910                         // can we handle it?
 911                         if(     (document["evaluate"])&&
 912                                 (query.indexOf(":") == -1)&&
 913                                 (query.indexOf("+") == -1) // skip direct sibling matches. See line ~344
 914                         ){
 915                                 // dojo.debug(query);
 916                                 // should we handle it?
 917
 918                                 // kind of a lame heuristic, but it works
 919                                 if(
 920                                         // a "div div div" style query
 921                                         ((qparts.length > 2)&&(query.indexOf(">") == -1))||
 922                                         // or something else with moderate complexity. kinda janky
 923                                         (qparts.length > 3)||
 924                                         (query.indexOf("[")>=0)||
 925                                         // or if it's a ".thinger" query
 926                                         ((1 == qparts.length)&&(0 <= query.indexOf(".")))
 927
 928                                 ){
 929                                         // use get and cache a xpath runner for this selector
 930                                         return getXPathFunc(query);
 931                                 }
 932                         }
 933
 934                         // fallthrough
 935                         return getStepQueryFunc(query);
 936                 } : getStepQueryFunc
 937         );
 938         // uncomment to disable XPath for testing and tuning the DOM path
 939         // _getQueryFunc = getStepQueryFunc;
 940
 941         // FIXME: we've got problems w/ the NodeList query()/filter() functions if we go XPath for everything
 942
 943         // uncomment to disable DOM queries for testing and tuning XPath
 944         // _getQueryFunc = getXPathFunc;
 945
 946         // this is the primary caching for full-query results. The query dispatcher
 947         // functions are generated here and then pickled for hash lookup in the
 948         // future
 949         var getQueryFunc = function(query){
 950                 // return a cached version if one is available
 951                 var qcz = query.charAt(0);
 952                 if(d.doc["querySelectorAll"] &&
 953                         ( (!d.isSafari) || (d.isSafari > 3.1) ) && // see #5832
 954                         // as per CSS 3, we can't currently start w/ combinator:
 955                         //              http://www.w3.org/TR/css3-selectors/#w3cselgrammar
 956                         (">+~".indexOf(qcz) == -1)
 957                 ){
 958                         return function(root){
 959                                 var r = root.querySelectorAll(query);
 960                                 r.nozip = true; // skip expensive duplication checks and just wrap in a NodeList
 961                                 return r;
 962                         };
 963                 }
 964                 if(_queryFuncCache[query]){ return _queryFuncCache[query]; }
 965                 if(0 > query.indexOf(",")){
 966                         // if it's not a compound query (e.g., ".foo, .bar"), cache and return a dispatcher
 967                         return _queryFuncCache[query] = _getQueryFunc(query);
 968                 }else{
 969                         // if it's a complex query, break it up into it's constituent parts
 970                         // and return a dispatcher that will merge the parts when run
 971
 972                         // var parts = query.split(", ");
 973                         var parts = query.split(/\s*,\s*/);
 974                         var tf = function(root){
 975                                 var pindex = 0; // avoid array alloc for every invocation
 976                                 var ret = [];
 977                                 var tp;
 978                                 while(tp = parts[pindex++]){
 979                                         ret = ret.concat(_getQueryFunc(tp, tp.indexOf(" "))(root));
 980                                 }
 981                                 return ret;
 982                         }
 983                         // ...cache and return
 984                         return _queryFuncCache[query] = tf;
 985                 }
 986         }
 987
 988         // FIXME:
 989         //              Dean's Base2 uses a system whereby queries themselves note if
 990         //              they'll need duplicate filtering. We need to get on that plan!!
 991
 992         // attempt to efficiently determine if an item in a list is a dupe,
 993         // returning a list of "uniques", hopefully in doucment order
 994         var _zipIdx = 0;
 995         var _zip = function(arr){
 996                 if(arr && arr.nozip){ return d.NodeList._wrap(arr); }
 997                 var ret = new d.NodeList();
 998                 if(!arr){ return ret; }
 999                 if(arr[0]){
1000                         ret.push(arr[0]);
1001                 }
1002                 if(arr.length < 2){ return ret; }
1003                 _zipIdx++;
1004                 arr[0]["_zipIdx"] = _zipIdx;
1005                 for(var x=1, te; te = arr[x]; x++){
1006                         if(arr[x]["_zipIdx"] != _zipIdx){
1007                                 ret.push(te);
1008                         }
1009                         te["_zipIdx"] = _zipIdx;
1010                 }
1011                 // FIXME: should we consider stripping these properties?
1012                 return ret;
1013         }
1014
1015         // the main executor
1016         d.query = function(/*String*/ query, /*String|DOMNode?*/ root){
1017                 //      summary:
1018                 //              Returns nodes which match the given CSS3 selector, searching the
1019                 //              entire document by default but optionally taking a node to scope
1020                 //              the search by. Returns an instance of dojo.NodeList.
1021                 //      description:
1022                 //              dojo.query() is the swiss army knife of DOM node manipulation in
1023                 //              Dojo. Much like Prototype's "$$" (bling-bling) function or JQuery's
1024                 //              "$" function, dojo.query provides robust, high-performance
1025                 //              CSS-based node selector support with the option of scoping searches
1026                 //              to a particular sub-tree of a document.
1027                 //
1028                 //              Supported Selectors:
1029                 //              --------------------
1030                 //
1031                 //              dojo.query() supports a rich set of CSS3 selectors, including:
1032                 //
1033                 //                      * class selectors (e.g., `.foo`)
1034                 //                      * node type selectors like `span`
1035                 //                      * ` ` descendant selectors
1036                 //                      * `>` child element selectors
1037                 //                      * `#foo` style ID selectors
1038                 //                      * `*` universal selector
1039                 //                      * `~`, the immediately preceeded-by sibling selector
1040                 //                      * `+`, the preceeded-by sibling selector
1041                 //                      * attribute queries:
1042                 //                      |       * `[foo]` attribute presence selector
1043                 //                      |       * `[foo='bar']` attribute value exact match
1044                 //                      |       * `[foo~='bar']` attribute value list item match
1045                 //                      |       * `[foo^='bar']` attribute start match
1046                 //                      |       * `[foo$='bar']` attribute end match
1047                 //                      |       * `[foo*='bar']` attribute substring match
1048                 //                      * `:first-child`, `:last-child` positional selectors
1049                 //                      * `:empty` content emtpy selector
1050                 //                      * `:empty` content emtpy selector
1051                 //                      * `:nth-child(n)`, `:nth-child(2n+1)` style positional calculations
1052                 //                      * `:nth-child(even)`, `:nth-child(odd)` positional selectors
1053                 //                      * `:not(...)` negation pseudo selectors
1054                 //
1055                 //              Any legal combination of these selectors will work with
1056                 //              `dojo.query()`, including compound selectors ("," delimited).
1057                 //              Very complex and useful searches can be constructed with this
1058                 //              palette of selectors and when combined with functions for
1059                 //              maniplation presented by dojo.NodeList, many types of DOM
1060                 //              manipulation operations become very straightforward.
1061                 //
1062                 //              Unsupported Selectors:
1063                 //              ----------------------
1064                 //
1065                 //              While dojo.query handles many CSS3 selectors, some fall outside of
1066                 //              what's resaonable for a programmatic node querying engine to
1067                 //              handle. Currently unsupported selectors include:
1068                 //
1069                 //                      * namespace-differentiated selectors of any form
1070                 //                      * all `::` pseduo-element selectors
1071                 //                      * certain pseduo-selectors which don't get a lot of day-to-day use:
1072                 //                      |       * `:root`, `:lang()`, `:target`, `:focus`
1073                 //                      * all visual and state selectors:
1074                 //                      |       * `:root`, `:active`, `:hover`, `:visisted`, `:link`,
1075                 //                                `:enabled`, `:disabled`, `:checked`
1076                 //                      * `:*-of-type` pseudo selectors
1077                 //
1078                 //              dojo.query and XML Documents:
1079                 //              -----------------------------
1080                 //
1081                 //              `dojo.query` currently only supports searching XML documents
1082                 //              whose tags and attributes are 100% lower-case. This is a known
1083                 //              limitation and will [be addressed soon](http://trac.dojotoolkit.org/ticket/3866)
1084                 //              Non-selector Queries:
1085                 //              ---------------------
1086                 //
1087                 //              If something other than a String is passed for the query,
1088                 //              `dojo.query` will return a new `dojo.NodeList` constructed from
1089                 //              that parameter alone and all further processing will stop. This
1090                 //              means that if you have a reference to a node or NodeList, you
1091                 //              can quickly construct a new NodeList from the original by
1092                 //              calling `dojo.query(node)` or `dojo.query(list)`.
1093                 //
1094                 //      query:
1095                 //              The CSS3 expression to match against. For details on the syntax of
1096                 //              CSS3 selectors, see <http://www.w3.org/TR/css3-selectors/#selectors>
1097                 //      root:
1098                 //              A DOMNode (or node id) to scope the search from. Optional.
1099                 //      returns: dojo.NodeList
1100                 //              An instance of `dojo.NodeList`. Many methods are available on
1101                 //              NodeLists for searching, iterating, manipulating, and handling
1102                 //              events on the matched nodes in the returned list.
1103                 //      example:
1104                 //              search the entire document for elements with the class "foo":
1105                 //      |       dojo.query(".foo");
1106                 //              these elements will match:
1107                 //      |       <span class="foo"></span>
1108                 //      |       <span class="foo bar"></span>
1109                 //      |       <p class="thud foo"></p>
1110                 //      example:
1111                 //              search the entire document for elements with the classes "foo" *and* "bar":
1112                 //      |       dojo.query(".foo.bar");
1113                 //              these elements will match:
1114                 //      |       <span class="foo bar"></span>
1115                 //              while these will not:
1116                 //      |       <span class="foo"></span>
1117                 //      |       <p class="thud foo"></p>
1118                 //      example:
1119                 //              find `<span>` elements which are descendants of paragraphs and
1120                 //              which have a "highlighted" class:
1121                 //      |       dojo.query("p span.highlighted");
1122                 //              the innermost span in this fragment matches:
1123                 //      |       <p class="foo">
1124                 //      |               <span>...
1125                 //      |                       <span class="highlighted foo bar">...</span>
1126                 //      |               </span>
1127                 //      |       </p>
1128                 //      example:
1129                 //              set an "odd" class on all odd table rows inside of the table
1130                 //              `#tabular_data`, using the `>` (direct child) selector to avoid
1131                 //              affecting any nested tables:
1132                 //      |       dojo.query("#tabular_data > tbody > tr:nth-child(odd)").addClass("odd");
1133                 //      example:
1134                 //              remove all elements with the class "error" from the document
1135                 //              and store them in a list:
1136                 //      |       var errors = dojo.query(".error").orphan();
1137                 //      example:
1138                 //              add an onclick handler to every submit button in the document
1139                 //              which causes the form to be sent via Ajax instead:
1140                 //      |       dojo.query("input[type='submit']").onclick(function(e){
1141                 //      |               dojo.stopEvent(e); // prevent sending the form
1142                 //      |               var btn = e.target;
1143                 //      |               dojo.xhrPost({
1144                 //      |                       form: btn.form,
1145                 //      |                       load: function(data){
1146                 //      |                               // replace the form with the response
1147                 //      |                               var div = dojo.doc.createElement("div");
1148                 //      |                               dojo.place(div, btn.form, "after");
1149                 //      |                               div.innerHTML = data;
1150                 //      |                               dojo.style(btn.form, "display", "none");
1151                 //      |                       }
1152                 //      |               });
1153                 //      |       });
1154
1155
1156                 // NOTE: elementsById is not currently supported
1157                 // NOTE: ignores xpath-ish queries for now
1158
1159                 if(query.constructor == d.NodeList){
1160                         return query;
1161                 }
1162                 if(!d.isString(query)){
1163                         return new d.NodeList(query); // dojo.NodeList
1164                 }
1165                 if(d.isString(root)){
1166                         root = d.byId(root);
1167                 }
1168
1169                 return _zip(getQueryFunc(query)(root||d.doc)); // dojo.NodeList
1170         }
1171
1172         /*
1173         // exposing this was a mistake
1174         d.query.attrs = attrs;
1175         */
1176         // exposing this because new pseudo matches are only executed through the
1177         // DOM query path (never through the xpath optimizing branch)
1178         d.query.pseudos = pseudos;
1179
1180         // one-off function for filtering a NodeList based on a simple selector
1181         d._filterQueryResult = function(nodeList, simpleFilter){
1182                 var tnl = new d.NodeList();
1183                 var ff = (simpleFilter) ? getFilterFunc(getQueryParts(simpleFilter)[0]) : function(){ return true; };
1184                 for(var x=0, te; te = nodeList[x]; x++){
1185                         if(ff(te)){ tnl.push(te); }
1186                 }
1187                 return tnl;
1188         }
1189 })();
1190
1191 }