Debian Codegraph @

closure-library/third_party/closure/goog/dojo/dom/query.js

raw
1 // Copyright 2005-2009, The Dojo Foundation
2 // Modifications Copyright 2008 The Closure Library Authors.
3 // All Rights Reserved.
4
5 /**
6 * @license Portions of this code are from the Dojo Toolkit, received by
7 * The Closure Library Authors under the BSD license. All other code is
8 * Copyright 2005-2009 The Closure Library Authors. All Rights Reserved.
9
10 The "New" BSD License:
11
12 Copyright (c) 2005-2009, The Dojo Foundation
13 All rights reserved.
14
15 Redistribution and use in source and binary forms, with or without
16 modification, are permitted provided that the following conditions are met:
17
18 * Redistributions of source code must retain the above copyright notice, this
19 list of conditions and the following disclaimer.
20 * Redistributions in binary form must reproduce the above copyright notice,
21 this list of conditions and the following disclaimer in the documentation
22 and/or other materials provided with the distribution.
23 * Neither the name of the Dojo Foundation nor the names of its contributors
24 may be used to endorse or promote products derived from this software
25 without specific prior written permission.
26
27 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
28 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
29 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
30 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
31 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
33 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
34 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
35 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
36 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 */
38
39 /**
40 * @fileoverview This code was ported from the Dojo Toolkit
41 http://dojotoolkit.org and modified slightly for Closure.
42 *
43 * goog.dom.query is a relatively full-featured CSS3 query function. It is
44 * designed to take any valid CSS3 selector and return the nodes matching
45 * the selector. To do this quickly, it processes queries in several
46 * steps, applying caching where profitable.
47 * The steps (roughly in reverse order of the way they appear in the code):
48 * 1.) check to see if we already have a "query dispatcher"
49 * - if so, use that with the given parameterization. Skip to step 4.
50 * 2.) attempt to determine which branch to dispatch the query to:
51 * - JS (optimized DOM iteration)
52 * - native (FF3.1, Safari 3.2+, Chrome, some IE 8 doctypes). If native,
53 * skip to step 4, using a stub dispatcher for QSA queries.
54 * 3.) tokenize and convert to executable "query dispatcher"
55 * assembled as a chain of "yes/no" test functions pertaining to
56 * a section of a simple query statement (".blah:nth-child(odd)"
57 * but not "div div", which is 2 simple statements).
58 * 4.) the resulting query dispatcher is called in the passed scope
59 * (by default the top-level document)
60 * - for DOM queries, this results in a recursive, top-down
61 * evaluation of nodes based on each simple query section
62 * - querySelectorAll is used instead of DOM where possible. If a query
63 * fails in this mode, it is re-run against the DOM evaluator and all
64 * future queries using the same selector evaluate against the DOM branch
65 * too.
66 * 5.) matched nodes are pruned to ensure they are unique
67 * @deprecated This is an all-software query selector. When developing for
68 * recent browsers, use document.querySelector. See information at
69 * http://caniuse.com/queryselector and
70 * https://developer.mozilla.org/en-US/docs/DOM/Document.querySelector .
71 */
72
73 goog.provide('goog.dom.query');
74
75 goog.require('goog.array');
76 goog.require('goog.dom');
77 goog.require('goog.functions');
78 goog.require('goog.string');
79 goog.require('goog.userAgent');
80
81 /**
82 * Returns nodes which match the given CSS3 selector, searching the
83 * entire document by default but optionally taking a node to scope
84 * the search by.
85 *
86 * dojo.query() is the swiss army knife of DOM node manipulation in
87 * Dojo. Much like Prototype's "$$" (bling-bling) function or JQuery's
88 * "$" function, dojo.query provides robust, high-performance
89 * CSS-based node selector support with the option of scoping searches
90 * to a particular sub-tree of a document.
91 *
92 * Supported Selectors:
93 * --------------------
94 *
95 * dojo.query() supports a rich set of CSS3 selectors, including:
96 *
97 * * class selectors (e.g., `.foo`)
98 * * node type selectors like `span`
99 * * ` ` descendant selectors
100 * * `>` child element selectors
101 * * `#foo` style ID selectors
102 * * `*` universal selector
103 * * `~`, the immediately preceded-by sibling selector
104 * * `+`, the preceded-by sibling selector
105 * * attribute queries:
106 * * `[foo]` attribute presence selector
107 * * `[foo='bar']` attribute value exact match
108 * * `[foo~='bar']` attribute value list item match
109 * * `[foo^='bar']` attribute start match
110 * * `[foo$='bar']` attribute end match
111 * * `[foo*='bar']` attribute substring match
112 * * `:first-child`, `:last-child` positional selectors
113 * * `:empty` content empty selector
114 * * `:empty` content empty selector
115 * * `:nth-child(n)`, `:nth-child(2n+1)` style positional calculations
116 * * `:nth-child(even)`, `:nth-child(odd)` positional selectors
117 * * `:not(...)` negation pseudo selectors
118 *
119 * Any legal combination of these selectors will work with
120 * `dojo.query()`, including compound selectors ("," delimited).
121 * Very complex and useful searches can be constructed with this
122 * palette of selectors.
123 *
124 * Unsupported Selectors:
125 * ----------------------
126 *
127 * While dojo.query handles many CSS3 selectors, some fall outside of
128 * what's reasonable for a programmatic node querying engine to
129 * handle. Currently unsupported selectors include:
130 *
131 * * namespace-differentiated selectors of any form
132 * * all `::` pseudo-element selectors
133 * * certain pseudo-selectors which don't get a lot of day-to-day use:
134 * * `:root`, `:lang()`, `:target`, `:focus`
135 * * all visual and state selectors:
136 * * `:root`, `:active`, `:hover`, `:visited`, `:link`,
137 * `:enabled`, `:disabled`, `:checked`
138 * * `:*-of-type` pseudo selectors
139 *
140 * dojo.query and XML Documents:
141 * -----------------------------
142 *
143 * `dojo.query` currently only supports searching XML documents
144 * whose tags and attributes are 100% lower-case. This is a known
145 * limitation and will [be addressed soon]
146 * (http://trac.dojotoolkit.org/ticket/3866)
147 *
148 * Non-selector Queries:
149 * ---------------------
150 *
151 * If something other than a String is passed for the query,
152 * `dojo.query` will return a new array constructed from
153 * that parameter alone and all further processing will stop. This
154 * means that if you have a reference to a node or array or nodes, you
155 * can quickly construct a new array of nodes from the original by
156 * calling `dojo.query(node)` or `dojo.query(array)`.
157 *
158 * __Example:__ search the entire document for elements with the class "foo":
159 *
160 * dojo.query(".foo");
161 *
162 * these elements will match:
163 *
164 * <span class="foo"></span>
165 * <span class="foo bar"></span>
166 * <p class="thud foo"></p>
167 *
168 * __Example:__ search the entire document for elements with the classes "foo"
169 * _and_ "bar":
170 *
171 * dojo.query(".foo.bar");
172 *
173 * these elements will match:
174 *
175 * <span class="foo bar"></span>
176 *
177 * while these will not:
178 *
179 * <span class="foo"></span>
180 * <p class="thud foo"></p>
181 *
182 * __Example:__ find `<span>` elements which are descendants of paragraphs and
183 * which have a "highlighted" class:
184 *
185 * dojo.query("p span.highlighted");
186 *
187 * the innermost span in this fragment matches:
188 *
189 * <p class="foo">
190 * <span>...
191 * <span class="highlighted foo bar">...</span>
192 * </span>
193 * </p>
194 *
195 * __Example:__ find all odd table rows inside of the table `#tabular_data`,
196 * using the `>` (direct child) selector to avoid affecting any nested tables:
197 *
198 * dojo.query("#tabular_data > tbody > tr:nth-child(odd)");
199 *
200 * @param {string|Array} query The CSS3 expression to match against.
201 * For details on the syntax of CSS3 selectors, see
202 * http://www.w3.org/TR/css3-selectors/#selectors.
203 * @param {(string|Node)=} opt_root A Node (or node id) to scope the search
204 * from (optional).
205 * @return { {length: number} } The elements that matched the query.
206 *
207 * @deprecated This is an all-software query selector. Use
208 * document.querySelector. See
209 * https://developer.mozilla.org/en-US/docs/DOM/Document.querySelector .
210 */
211 goog.dom.query = (function() {
212 ////////////////////////////////////////////////////////////////////////
213 // Global utilities
214 ////////////////////////////////////////////////////////////////////////
215
216 var cssCaseBug = (goog.userAgent.WEBKIT &&
217 ((goog.dom.getDocument().compatMode) == 'BackCompat')
218 );
219
220 var legacyIE = goog.userAgent.IE && !goog.userAgent.isVersionOrHigher('9');
221
222 // On browsers that support the "children" collection we can avoid a lot of
223 // iteration on chaff (non-element) nodes.
224 var childNodesName =
225 goog.dom.getDocument().firstChild['children'] ? 'children' : 'childNodes';
226
227 var specials = '>~+';
228
229 // Global thunk to determine whether we should treat the current query as
230 // case sensitive or not. This switch is flipped by the query evaluator based
231 // on the document passed as the context to search.
232 var caseSensitive = false;
233
234
235 ////////////////////////////////////////////////////////////////////////
236 // Tokenizer
237 ////////////////////////////////////////////////////////////////////////
238
239 var getQueryParts = function(query) {
240 // summary:
241 // state machine for query tokenization
242 // description:
243 // instead of using a brittle and slow regex-based CSS parser,
244 // dojo.query implements an AST-style query representation. This
245 // representation is only generated once per query. For example,
246 // the same query run multiple times or under different root nodes
247 // does not re-parse the selector expression but instead uses the
248 // cached data structure. The state machine implemented here
249 // terminates on the last " " (space) character and returns an
250 // ordered array of query component structures (or "parts"). Each
251 // part represents an operator or a simple CSS filtering
252 // expression. The structure for parts is documented in the code
253 // below.
254
255
256 // NOTE:
257 // this code is designed to run fast and compress well. Sacrifices
258 // to readability and maintainability have been made.
259 if (specials.indexOf(query.slice(-1)) >= 0) {
260 // If we end with a ">", "+", or "~", that means we're implicitly
261 // searching all children, so make it explicit.
262 query += ' * ';
263 } else {
264 // if you have not provided a terminator, one will be provided for
265 // you...
266 query += ' ';
267 }
268
269 var ts = function(/*Integer*/ s, /*Integer*/ e) {
270 // trim and slice.
271
272 // take an index to start a string slice from and an end position
273 // and return a trimmed copy of that sub-string
274 return goog.string.trim(query.slice(s, e));
275 };
276
277 // The overall data graph of the full query, as represented by queryPart
278 // objects.
279 var queryParts = [];
280
281
282 // state keeping vars
283 var inBrackets = -1,
284 inParens = -1,
285 inMatchFor = -1,
286 inPseudo = -1,
287 inClass = -1,
288 inId = -1,
289 inTag = -1,
290 lc = '',
291 cc = '',
292 pStart;
293
294 // iteration vars
295 var x = 0, // index in the query
296 ql = query.length,
297 currentPart = null, // data structure representing the entire clause
298 cp = null; // the current pseudo or attr matcher
299
300 // several temporary variables are assigned to this structure during a
301 // potential sub-expression match:
302 // attr:
303 // a string representing the current full attribute match in a
304 // bracket expression
305 // type:
306 // if there's an operator in a bracket expression, this is
307 // used to keep track of it
308 // value:
309 // the internals of parenthetical expression for a pseudo. for
310 // :nth-child(2n+1), value might be '2n+1'
311
312 var endTag = function() {
313 // called when the tokenizer hits the end of a particular tag name.
314 // Re-sets state variables for tag matching and sets up the matcher
315 // to handle the next type of token (tag or operator).
316 if (inTag >= 0) {
317 var tv = (inTag == x) ? null : ts(inTag, x);
318 if (specials.indexOf(tv) < 0) {
319 currentPart.tag = tv;
320 } else {
321 currentPart.oper = tv;
322 }
323 inTag = -1;
324 }
325 };
326
327 var endId = function() {
328 // Called when the tokenizer might be at the end of an ID portion of a
329 // match.
330 if (inId >= 0) {
331 currentPart.id = ts(inId, x).replace(/\\/g, '');
332 inId = -1;
333 }
334 };
335
336 var endClass = function() {
337 // Called when the tokenizer might be at the end of a class name
338 // match. CSS allows for multiple classes, so we augment the
339 // current item with another class in its list.
340 if (inClass >= 0) {
341 currentPart.classes.push(ts(inClass + 1, x).replace(/\\/g, ''));
342 inClass = -1;
343 }
344 };
345
346 var endAll = function() {
347 // at the end of a simple fragment, so wall off the matches
348 endId(); endTag(); endClass();
349 };
350
351 var endPart = function() {
352 endAll();
353 if (inPseudo >= 0) {
354 currentPart.pseudos.push({ name: ts(inPseudo + 1, x) });
355 }
356 // Hint to the selector engine to tell it whether or not it
357 // needs to do any iteration. Many simple selectors don't, and
358 // we can avoid significant construction-time work by advising
359 // the system to skip them.
360 currentPart.loops = currentPart.pseudos.length ||
361 currentPart.attrs.length ||
362 currentPart.classes.length;
363
364 // save the full expression as a string
365 currentPart.oquery = currentPart.query = ts(pStart, x);
366
367
368 // otag/tag are hints to suggest to the system whether or not
369 // it's an operator or a tag. We save a copy of otag since the
370 // tag name is cast to upper-case in regular HTML matches. The
371 // system has a global switch to figure out if the current
372 // expression needs to be case sensitive or not and it will use
373 // otag or tag accordingly
374 currentPart.otag = currentPart.tag = (currentPart.oper) ?
375 null :
376 (currentPart.tag || '*');
377
378 if (currentPart.tag) {
379 // if we're in a case-insensitive HTML doc, we likely want
380 // the toUpperCase when matching on element.tagName. If we
381 // do it here, we can skip the string op per node
382 // comparison
383 currentPart.tag = currentPart.tag.toUpperCase();
384 }
385
386 // add the part to the list
387 if (queryParts.length && (queryParts[queryParts.length - 1].oper)) {
388 // operators are always infix, so we remove them from the
389 // list and attach them to the next match. The evaluator is
390 // responsible for sorting out how to handle them.
391 currentPart.infixOper = queryParts.pop();
392 currentPart.query = currentPart.infixOper.query + ' ' +
393 currentPart.query;
394 }
395 queryParts.push(currentPart);
396
397 currentPart = null;
398 };
399
400 // iterate over the query, character by character, building up a
401 // list of query part objects
402 for (; lc = cc, cc = query.charAt(x), x < ql; x++) {
403 // cc: the current character in the match
404 // lc: the last character (if any)
405
406 // someone is trying to escape something, so don't try to match any
407 // fragments. We assume we're inside a literal.
408 if (lc == '\\') {
409 continue;
410 }
411 if (!currentPart) { // a part was just ended or none has yet been created
412 // NOTE: I hate all this alloc, but it's shorter than writing tons of
413 // if's
414 pStart = x;
415 // rules describe full CSS sub-expressions, like:
416 // #someId
417 // .className:first-child
418 // but not:
419 // thinger > div.howdy[type=thinger]
420 // the individual components of the previous query would be
421 // split into 3 parts that would be represented a structure
422 // like:
423 // [
424 // {
425 // query: 'thinger',
426 // tag: 'thinger',
427 // },
428 // {
429 // query: 'div.howdy[type=thinger]',
430 // classes: ['howdy'],
431 // infixOper: {
432 // query: '>',
433 // oper: '>',
434 // }
435 // },
436 // ]
437 currentPart = {
438 query: null, // the full text of the part's rule
439 pseudos: [], // CSS supports multiple pseudo-class matches in a single
440 // rule
441 attrs: [], // CSS supports multi-attribute match, so we need an array
442 classes: [], // class matches may be additive,
443 // e.g.: .thinger.blah.howdy
444 tag: null, // only one tag...
445 oper: null, // ...or operator per component. Note that these wind up
446 // being exclusive.
447 id: null, // the id component of a rule
448 getTag: function() {
449 return (caseSensitive) ? this.otag : this.tag;
450 }
451 };
452
453 // if we don't have a part, we assume we're going to start at
454 // the beginning of a match, which should be a tag name. This
455 // might fault a little later on, but we detect that and this
456 // iteration will still be fine.
457 inTag = x;
458 }
459
460 if (inBrackets >= 0) {
461 // look for a the close first
462 if (cc == ']') { // if we're in a [...] clause and we end, do assignment
463 if (!cp.attr) {
464 // no attribute match was previously begun, so we
465 // assume this is an attribute existence match in the
466 // form of [someAttributeName]
467 cp.attr = ts(inBrackets + 1, x);
468 } else {
469 // we had an attribute already, so we know that we're
470 // matching some sort of value, as in [attrName=howdy]
471 cp.matchFor = ts((inMatchFor || inBrackets + 1), x);
472 }
473 var cmf = cp.matchFor;
474 if (cmf) {
475 // try to strip quotes from the matchFor value. We want
476 // [attrName=howdy] to match the same
477 // as [attrName = 'howdy' ]
478 if ((cmf.charAt(0) == '"') || (cmf.charAt(0) == "'")) {
479 cp.matchFor = cmf.slice(1, -1);
480 }
481 }
482 // end the attribute by adding it to the list of attributes.
483 currentPart.attrs.push(cp);
484 cp = null; // necessary?
485 inBrackets = inMatchFor = -1;
486 } else if (cc == '=') {
487 // if the last char was an operator prefix, make sure we
488 // record it along with the '=' operator.
489 var addToCc = ('|~^$*'.indexOf(lc) >= 0) ? lc : '';
490 cp.type = addToCc + cc;
491 cp.attr = ts(inBrackets + 1, x - addToCc.length);
492 inMatchFor = x + 1;
493 }
494 // now look for other clause parts
495 } else if (inParens >= 0) {
496 // if we're in a parenthetical expression, we need to figure
497 // out if it's attached to a pseudo-selector rule like
498 // :nth-child(1)
499 if (cc == ')') {
500 if (inPseudo >= 0) {
501 cp.value = ts(inParens + 1, x);
502 }
503 inPseudo = inParens = -1;
504 }
505 } else if (cc == '#') {
506 // start of an ID match
507 endAll();
508 inId = x + 1;
509 } else if (cc == '.') {
510 // start of a class match
511 endAll();
512 inClass = x;
513 } else if (cc == ':') {
514 // start of a pseudo-selector match
515 endAll();
516 inPseudo = x;
517 } else if (cc == '[') {
518 // start of an attribute match.
519 endAll();
520 inBrackets = x;
521 // provide a new structure for the attribute match to fill-in
522 cp = {
523 /*=====
524 attr: null, type: null, matchFor: null
525 =====*/
526 };
527 } else if (cc == '(') {
528 // we really only care if we've entered a parenthetical
529 // expression if we're already inside a pseudo-selector match
530 if (inPseudo >= 0) {
531 // provide a new structure for the pseudo match to fill-in
532 cp = {name: ts(inPseudo + 1, x), value: null};
533 currentPart.pseudos.push(cp);
534 }
535 inParens = x;
536 } else if (
537 (cc == ' ') &&
538 // if it's a space char and the last char is too, consume the
539 // current one without doing more work
540 (lc != cc)
541 ) {
542 endPart();
543 }
544 }
545 return queryParts;
546 };
547
548
549 ////////////////////////////////////////////////////////////////////////
550 // DOM query infrastructure
551 ////////////////////////////////////////////////////////////////////////
552
553 var agree = function(first, second) {
554 // the basic building block of the yes/no chaining system. agree(f1,
555 // f2) generates a new function which returns the boolean results of
556 // both of the passed functions to a single logical-anded result. If
557 // either are not passed, the other is used exclusively.
558 if (!first) {
559 return second;
560 }
561 if (!second) {
562 return first;
563 }
564
565 return function() {
566 return first.apply(window, arguments) && second.apply(window, arguments);
567 }
568 };
569
570 /**
571 * @param {(number|string|Node)} i
572 * @param {Array=} opt_arr
573 */
574 function getArr(i, opt_arr) {
575 // helps us avoid array alloc when we don't need it
576 var r = opt_arr || [];
577 if (i) {
578 r.push(i);
579 }
580 return r;
581 }
582
583 var isElement = function(n) {
584 return (1 == n.nodeType);
585 };
586
587 // FIXME: need to coalesce getAttr with defaultGetter
588 var blank = '';
589 var getAttr = function(elem, attr) {
590 if (!elem) {
591 return blank;
592 }
593 if (attr == 'class') {
594 return elem.className || blank;
595 }
596 if (attr == 'for') {
597 return elem.htmlFor || blank;
598 }
599 if (attr == 'style') {
600 return elem.style.cssText || blank;
601 }
602 return (caseSensitive ? elem.getAttribute(attr) :
603 elem.getAttribute(attr, 2)) || blank;
604 };
605
606 var attrs = {
607 '*=': function(attr, value) {
608 return function(elem) {
609 // E[foo*="bar"]
610 // an E element whose "foo" attribute value contains
611 // the substring "bar"
612 return (getAttr(elem, attr).indexOf(value) >= 0);
613 }
614 },
615 '^=': function(attr, value) {
616 // E[foo^="bar"]
617 // an E element whose "foo" attribute value begins exactly
618 // with the string "bar"
619 return function(elem) {
620 return (getAttr(elem, attr).indexOf(value) == 0);
621 }
622 },
623 '$=': function(attr, value) {
624 // E[foo$="bar"]
625 // an E element whose "foo" attribute value ends exactly
626 // with the string "bar"
627 var tval = ' ' + value;
628 return function(elem) {
629 var ea = ' ' + getAttr(elem, attr);
630 return (ea.lastIndexOf(tval) == (ea.length - tval.length));
631 }
632 },
633 '~=': function(attr, value) {
634 // E[foo~="bar"]
635 // an E element whose "foo" attribute value is a list of
636 // space-separated values, one of which is exactly equal
637 // to "bar"
638
639 var tval = ' ' + value + ' ';
640 return function(elem) {
641 var ea = ' ' + getAttr(elem, attr) + ' ';
642 return (ea.indexOf(tval) >= 0);
643 }
644 },
645 '|=': function(attr, value) {
646 // E[hreflang|="en"]
647 // an E element whose "hreflang" attribute has a
648 // hyphen-separated list of values beginning (from the
649 // left) with "en"
650 value = ' ' + value;
651 return function(elem) {
652 var ea = ' ' + getAttr(elem, attr);
653 return (
654 (ea == value) ||
655 (ea.indexOf(value + '-') == 0)
656 );
657 }
658 },
659 '=': function(attr, value) {
660 return function(elem) {
661 return (getAttr(elem, attr) == value);
662 }
663 }
664 };
665
666 // avoid testing for node type if we can. Defining this in the negative
667 // here to avoid negation in the fast path.
668 var noNextElementSibling = (
669 typeof goog.dom.getDocument().firstChild.nextElementSibling == 'undefined'
670 );
671 var nSibling = !noNextElementSibling ? 'nextElementSibling' : 'nextSibling';
672 var pSibling = !noNextElementSibling ?
673 'previousElementSibling' :
674 'previousSibling';
675 var simpleNodeTest = (noNextElementSibling ? isElement : goog.functions.TRUE);
676
677 var _lookLeft = function(node) {
678 while (node = node[pSibling]) {
679 if (simpleNodeTest(node)) {
680 return false;
681 }
682 }
683 return true;
684 };
685
686 var _lookRight = function(node) {
687 while (node = node[nSibling]) {
688 if (simpleNodeTest(node)) {
689 return false;
690 }
691 }
692 return true;
693 };
694
695 var getNodeIndex = function(node) {
696 var root = node.parentNode;
697 var i = 0,
698 tret = root[childNodesName],
699 ci = (node['_i'] || -1),
700 cl = (root['_l'] || -1);
701
702 if (!tret) {
703 return -1;
704 }
705 var l = tret.length;
706
707 // we calculate the parent length as a cheap way to invalidate the
708 // cache. It's not 100% accurate, but it's much more honest than what
709 // other libraries do
710 if (cl == l && ci >= 0 && cl >= 0) {
711 // if it's legit, tag and release
712 return ci;
713 }
714
715 // else re-key things
716 root['_l'] = l;
717 ci = -1;
718 var te = root['firstElementChild'] || root['firstChild'];
719 for (; te; te = te[nSibling]) {
720 if (simpleNodeTest(te)) {
721 te['_i'] = ++i;
722 if (node === te) {
723 // NOTE:
724 // shortcutting the return at this step in indexing works
725 // very well for benchmarking but we avoid it here since
726 // it leads to potential O(n^2) behavior in sequential
727 // getNodexIndex operations on a previously un-indexed
728 // parent. We may revisit this at a later time, but for
729 // now we just want to get the right answer more often
730 // than not.
731 ci = i;
732 }
733 }
734 }
735 return ci;
736 };
737
738 var isEven = function(elem) {
739 return !((getNodeIndex(elem)) % 2);
740 };
741
742 var isOdd = function(elem) {
743 return (getNodeIndex(elem)) % 2;
744 };
745
746 var pseudos = {
747 'checked': function(name, condition) {
748 return function(elem) {
749 return elem.checked || elem.attributes['checked'];
750 }
751 },
752 'first-child': function() {
753 return _lookLeft;
754 },
755 'last-child': function() {
756 return _lookRight;
757 },
758 'only-child': function(name, condition) {
759 return function(node) {
760 if (!_lookLeft(node)) {
761 return false;
762 }
763 if (!_lookRight(node)) {
764 return false;
765 }
766 return true;
767 };
768 },
769 'empty': function(name, condition) {
770 return function(elem) {
771 // DomQuery and jQuery get this wrong, oddly enough.
772 // The CSS 3 selectors spec is pretty explicit about it, too.
773 var cn = elem.childNodes;
774 var cnl = elem.childNodes.length;
775 // if(!cnl) { return true; }
776 for (var x = cnl - 1; x >= 0; x--) {
777 var nt = cn[x].nodeType;
778 if ((nt === 1) || (nt == 3)) {
779 return false;
780 }
781 }
782 return true;
783 }
784 },
785 'contains': function(name, condition) {
786 var cz = condition.charAt(0);
787 if (cz == '"' || cz == "'") { // Remove quotes.
788 condition = condition.slice(1, -1);
789 }
790 return function(elem) {
791 return (elem.innerHTML.indexOf(condition) >= 0);
792 }
793 },
794 'not': function(name, condition) {
795 var p = getQueryParts(condition)[0];
796 var ignores = { el: 1 };
797 if (p.tag != '*') {
798 ignores.tag = 1;
799 }
800 if (!p.classes.length) {
801 ignores.classes = 1;
802 }
803 var ntf = getSimpleFilterFunc(p, ignores);
804 return function(elem) {
805 return !ntf(elem);
806 }
807 },
808 'nth-child': function(name, condition) {
809 function pi(n) {
810 return parseInt(n, 10);
811 }
812 // avoid re-defining function objects if we can
813 if (condition == 'odd') {
814 return isOdd;
815 } else if (condition == 'even') {
816 return isEven;
817 }
818 // FIXME: can we shorten this?
819 if (condition.indexOf('n') != -1) {
820 var tparts = condition.split('n', 2);
821 var pred = tparts[0] ? ((tparts[0] == '-') ? -1 : pi(tparts[0])) : 1;
822 var idx = tparts[1] ? pi(tparts[1]) : 0;
823 var lb = 0, ub = -1;
824 if (pred > 0) {
825 if (idx < 0) {
826 idx = (idx % pred) && (pred + (idx % pred));
827 } else if (idx > 0) {
828 if (idx >= pred) {
829 lb = idx - idx % pred;
830 }
831 idx = idx % pred;
832 }
833 } else if (pred < 0) {
834 pred *= -1;
835 // idx has to be greater than 0 when pred is negative;
836 // shall we throw an error here?
837 if (idx > 0) {
838 ub = idx;
839 idx = idx % pred;
840 }
841 }
842 if (pred > 0) {
843 return function(elem) {
844 var i = getNodeIndex(elem);
845 return (i >= lb) && (ub < 0 || i <= ub) && ((i % pred) == idx);
846 }
847 } else {
848 condition = idx;
849 }
850 }
851 var ncount = pi(condition);
852 return function(elem) {
853 return (getNodeIndex(elem) == ncount);
854 }
855 }
856 };
857
858 var defaultGetter = (legacyIE) ? function(cond) {
859 var clc = cond.toLowerCase();
860 if (clc == 'class') {
861 cond = 'className';
862 }
863 return function(elem) {
864 return caseSensitive ? elem.getAttribute(cond) : elem[cond] || elem[clc];
865 }
866 } : function(cond) {
867 return function(elem) {
868 return elem && elem.getAttribute && elem.hasAttribute(cond);
869 }
870 };
871
872 var getSimpleFilterFunc = function(query, ignores) {
873 // Generates a node tester function based on the passed query part. The
874 // query part is one of the structures generated by the query parser when it
875 // creates the query AST. The 'ignores' object specifies which (if any)
876 // tests to skip, allowing the system to avoid duplicating work where it
877 // may have already been taken into account by other factors such as how
878 // the nodes to test were fetched in the first place.
879 if (!query) {
880 return goog.functions.TRUE;
881 }
882 ignores = ignores || {};
883
884 var ff = null;
885
886 if (!ignores.el) {
887 ff = agree(ff, isElement);
888 }
889
890 if (!ignores.tag) {
891 if (query.tag != '*') {
892 ff = agree(ff, function(elem) {
893 return (elem && (elem.tagName == query.getTag()));
894 });
895 }
896 }
897
898 if (!ignores.classes) {
899 goog.array.forEach(query.classes, function(cname, idx, arr) {
900 // Get the class name.
901 var re = new RegExp('(?:^|\\s)' + cname + '(?:\\s|$)');
902 ff = agree(ff, function(elem) {
903 return re.test(elem.className);
904 });
905 ff.count = idx;
906 });
907 }
908
909 if (!ignores.pseudos) {
910 goog.array.forEach(query.pseudos, function(pseudo) {
911 var pn = pseudo.name;
912 if (pseudos[pn]) {
913 ff = agree(ff, pseudos[pn](pn, pseudo.value));
914 }
915 });
916 }
917
918 if (!ignores.attrs) {
919 goog.array.forEach(query.attrs, function(attr) {
920 var matcher;
921 var a = attr.attr;
922 // type, attr, matchFor
923 if (attr.type && attrs[attr.type]) {
924 matcher = attrs[attr.type](a, attr.matchFor);
925 } else if (a.length) {
926 matcher = defaultGetter(a);
927 }
928 if (matcher) {
929 ff = agree(ff, matcher);
930 }
931 });
932 }
933
934 if (!ignores.id) {
935 if (query.id) {
936 ff = agree(ff, function(elem) {
937 return (!!elem && (elem.id == query.id));
938 });
939 }
940 }
941
942 if (!ff) {
943 if (!('default' in ignores)) {
944 ff = goog.functions.TRUE;
945 }
946 }
947 return ff;
948 };
949
950 var nextSiblingIterator = function(filterFunc) {
951 return function(node, ret, bag) {
952 while (node = node[nSibling]) {
953 if (noNextElementSibling && (!isElement(node))) {
954 continue;
955 }
956 if (
957 (!bag || _isUnique(node, bag)) &&
958 filterFunc(node)
959 ) {
960 ret.push(node);
961 }
962 break;
963 }
964 return ret;
965 };
966 };
967
968 var nextSiblingsIterator = function(filterFunc) {
969 return function(root, ret, bag) {
970 var te = root[nSibling];
971 while (te) {
972 if (simpleNodeTest(te)) {
973 if (bag && !_isUnique(te, bag)) {
974 break;
975 }
976 if (filterFunc(te)) {
977 ret.push(te);
978 }
979 }
980 te = te[nSibling];
981 }
982 return ret;
983 };
984 };
985
986 // Get an array of child *elements*, skipping text and comment nodes
987 var _childElements = function(filterFunc) {
988 filterFunc = filterFunc || goog.functions.TRUE;
989 return function(root, ret, bag) {
990 var te, x = 0, tret = root[childNodesName];
991 while (te = tret[x++]) {
992 if (
993 simpleNodeTest(te) &&
994 (!bag || _isUnique(te, bag)) &&
995 (filterFunc(te, x))
996 ) {
997 ret.push(te);
998 }
999 }
1000 return ret;
1001 };
1002 };
1003
1004 // test to see if node is below root
1005 var _isDescendant = function(node, root) {
1006 var pn = node.parentNode;
1007 while (pn) {
1008 if (pn == root) {
1009 break;
1010 }
1011 pn = pn.parentNode;
1012 }
1013 return !!pn;
1014 };
1015
1016 var _getElementsFuncCache = {};
1017
1018 var getElementsFunc = function(query) {
1019 var retFunc = _getElementsFuncCache[query.query];
1020 // If we've got a cached dispatcher, just use that.
1021 if (retFunc) {
1022 return retFunc;
1023 }
1024 // Else, generate a new one.
1025
1026 // NOTE:
1027 // This function returns a function that searches for nodes and
1028 // filters them. The search may be specialized by infix operators
1029 // (">", "~", or "+") else it will default to searching all
1030 // descendants (the " " selector). Once a group of children is
1031 // found, a test function is applied to weed out the ones we
1032 // don't want. Many common cases can be fast-pathed. We spend a
1033 // lot of cycles to create a dispatcher that doesn't do more work
1034 // than necessary at any point since, unlike this function, the
1035 // dispatchers will be called every time. The logic of generating
1036 // efficient dispatchers looks like this in pseudo code:
1037 //
1038 // # if it's a purely descendant query (no ">", "+", or "~" modifiers)
1039 // if infixOperator == " ":
1040 // if only(id):
1041 // return def(root):
1042 // return d.byId(id, root);
1043 //
1044 // elif id:
1045 // return def(root):
1046 // return filter(d.byId(id, root));
1047 //
1048 // elif cssClass && getElementsByClassName:
1049 // return def(root):
1050 // return filter(root.getElementsByClassName(cssClass));
1051 //
1052 // elif only(tag):
1053 // return def(root):
1054 // return root.getElementsByTagName(tagName);
1055 //
1056 // else:
1057 // # search by tag name, then filter
1058 // return def(root):
1059 // return filter(root.getElementsByTagName(tagName||"*"));
1060 //
1061 // elif infixOperator == ">":
1062 // # search direct children
1063 // return def(root):
1064 // return filter(root.children);
1065 //
1066 // elif infixOperator == "+":
1067 // # search next sibling
1068 // return def(root):
1069 // return filter(root.nextElementSibling);
1070 //
1071 // elif infixOperator == "~":
1072 // # search rightward siblings
1073 // return def(root):
1074 // return filter(nextSiblings(root));
1075
1076 var io = query.infixOper;
1077 var oper = (io ? io.oper : '');
1078 // The default filter func which tests for all conditions in the query
1079 // part. This is potentially inefficient, so some optimized paths may
1080 // re-define it to test fewer things.
1081 var filterFunc = getSimpleFilterFunc(query, { el: 1 });
1082 var qt = query.tag;
1083 var wildcardTag = ('*' == qt);
1084 var ecs = goog.dom.getDocument()['getElementsByClassName'];
1085
1086 if (!oper) {
1087 // If there's no infix operator, then it's a descendant query. ID
1088 // and "elements by class name" variants can be accelerated so we
1089 // call them out explicitly:
1090 if (query.id) {
1091 // Testing shows that the overhead of goog.functions.TRUE() is
1092 // acceptable and can save us some bytes vs. re-defining the function
1093 // everywhere.
1094 filterFunc = (!query.loops && wildcardTag) ?
1095 goog.functions.TRUE :
1096 getSimpleFilterFunc(query, { el: 1, id: 1 });
1097
1098 retFunc = function(root, arr) {
1099 var te = goog.dom.getDomHelper(root).getElement(query.id);
1100 if (!te || !filterFunc(te)) {
1101 return;
1102 }
1103 if (9 == root.nodeType) { // If root's a doc, we just return directly.
1104 return getArr(te, arr);
1105 } else { // otherwise check ancestry
1106 if (_isDescendant(te, root)) {
1107 return getArr(te, arr);
1108 }
1109 }
1110 };
1111 } else if (
1112 ecs &&
1113 // isAlien check. Workaround for Prototype.js being totally evil/dumb.
1114 /\{\s*\[native code\]\s*\}/.test(String(ecs)) &&
1115 query.classes.length &&
1116 // WebKit bug where quirks-mode docs select by class w/o case
1117 // sensitivity.
1118 !cssCaseBug
1119 ) {
1120 // it's a class-based query and we've got a fast way to run it.
1121
1122 // ignore class and ID filters since we will have handled both
1123 filterFunc = getSimpleFilterFunc(query, { el: 1, classes: 1, id: 1 });
1124 var classesString = query.classes.join(' ');
1125 retFunc = function(root, arr) {
1126 var ret = getArr(0, arr), te, x = 0;
1127 var tret = root.getElementsByClassName(classesString);
1128 while ((te = tret[x++])) {
1129 if (filterFunc(te, root)) {
1130 ret.push(te);
1131 }
1132 }
1133 return ret;
1134 };
1135
1136 } else if (!wildcardTag && !query.loops) {
1137 // it's tag only. Fast-path it.
1138 retFunc = function(root, arr) {
1139 var ret = getArr(0, arr), te, x = 0;
1140 var tret = root.getElementsByTagName(query.getTag());
1141 while ((te = tret[x++])) {
1142 ret.push(te);
1143 }
1144 return ret;
1145 };
1146 } else {
1147 // the common case:
1148 // a descendant selector without a fast path. By now it's got
1149 // to have a tag selector, even if it's just "*" so we query
1150 // by that and filter
1151 filterFunc = getSimpleFilterFunc(query, { el: 1, tag: 1, id: 1 });
1152 retFunc = function(root, arr) {
1153 var ret = getArr(0, arr), te, x = 0;
1154 // we use getTag() to avoid case sensitivity issues
1155 var tret = root.getElementsByTagName(query.getTag());
1156 while (te = tret[x++]) {
1157 if (filterFunc(te, root)) {
1158 ret.push(te);
1159 }
1160 }
1161 return ret;
1162 };
1163 }
1164 } else {
1165 // the query is scoped in some way. Instead of querying by tag we
1166 // use some other collection to find candidate nodes
1167 var skipFilters = { el: 1 };
1168 if (wildcardTag) {
1169 skipFilters.tag = 1;
1170 }
1171 filterFunc = getSimpleFilterFunc(query, skipFilters);
1172 if ('+' == oper) {
1173 retFunc = nextSiblingIterator(filterFunc);
1174 } else if ('~' == oper) {
1175 retFunc = nextSiblingsIterator(filterFunc);
1176 } else if ('>' == oper) {
1177 retFunc = _childElements(filterFunc);
1178 }
1179 }
1180 // cache it and return
1181 return _getElementsFuncCache[query.query] = retFunc;
1182 };
1183
1184 var filterDown = function(root, queryParts) {
1185 // NOTE:
1186 // this is the guts of the DOM query system. It takes a list of
1187 // parsed query parts and a root and finds children which match
1188 // the selector represented by the parts
1189 var candidates = getArr(root), qp, x, te, qpl = queryParts.length, bag, ret;
1190
1191 for (var i = 0; i < qpl; i++) {
1192 ret = [];
1193 qp = queryParts[i];
1194 x = candidates.length - 1;
1195 if (x > 0) {
1196 // if we have more than one root at this level, provide a new
1197 // hash to use for checking group membership but tell the
1198 // system not to post-filter us since we will already have been
1199 // guaranteed to be unique
1200 bag = {};
1201 ret.nozip = true;
1202 }
1203 var gef = getElementsFunc(qp);
1204 for (var j = 0; te = candidates[j]; j++) {
1205 // for every root, get the elements that match the descendant
1206 // selector, adding them to the 'ret' array and filtering them
1207 // via membership in this level's bag. If there are more query
1208 // parts, then this level's return will be used as the next
1209 // level's candidates
1210 gef(te, ret, bag);
1211 }
1212 if (!ret.length) { break; }
1213 candidates = ret;
1214 }
1215 return ret;
1216 };
1217
1218 ////////////////////////////////////////////////////////////////////////
1219 // the query runner
1220 ////////////////////////////////////////////////////////////////////////
1221
1222 // these are the primary caches for full-query results. The query
1223 // dispatcher functions are generated then stored here for hash lookup in
1224 // the future
1225 var _queryFuncCacheDOM = {},
1226 _queryFuncCacheQSA = {};
1227
1228 // this is the second level of splitting, from full-length queries (e.g.,
1229 // 'div.foo .bar') into simple query expressions (e.g., ['div.foo',
1230 // '.bar'])
1231 var getStepQueryFunc = function(query) {
1232 var qparts = getQueryParts(goog.string.trim(query));
1233
1234 // if it's trivial, avoid iteration and zipping costs
1235 if (qparts.length == 1) {
1236 // We optimize this case here to prevent dispatch further down the
1237 // chain, potentially slowing things down. We could more elegantly
1238 // handle this in filterDown(), but it's slower for simple things
1239 // that need to be fast (e.g., '#someId').
1240 var tef = getElementsFunc(qparts[0]);
1241 return function(root) {
1242 var r = tef(root, []);
1243 if (r) { r.nozip = true; }
1244 return r;
1245 }
1246 }
1247
1248 // otherwise, break it up and return a runner that iterates over the parts
1249 // recursively
1250 return function(root) {
1251 return filterDown(root, qparts);
1252 }
1253 };
1254
1255 // NOTES:
1256 // * we can't trust QSA for anything but document-rooted queries, so
1257 // caching is split into DOM query evaluators and QSA query evaluators
1258 // * caching query results is dirty and leak-prone (or, at a minimum,
1259 // prone to unbounded growth). Other toolkits may go this route, but
1260 // they totally destroy their own ability to manage their memory
1261 // footprint. If we implement it, it should only ever be with a fixed
1262 // total element reference # limit and an LRU-style algorithm since JS
1263 // has no weakref support. Caching compiled query evaluators is also
1264 // potentially problematic, but even on large documents the size of the
1265 // query evaluators is often < 100 function objects per evaluator (and
1266 // LRU can be applied if it's ever shown to be an issue).
1267 // * since IE's QSA support is currently only for HTML documents and even
1268 // then only in IE 8's 'standards mode', we have to detect our dispatch
1269 // route at query time and keep 2 separate caches. Ugg.
1270
1271 var qsa = 'querySelectorAll';
1272
1273 // some versions of Safari provided QSA, but it was buggy and crash-prone.
1274 // We need to detect the right 'internal' webkit version to make this work.
1275 var qsaAvail = (
1276 !!goog.dom.getDocument()[qsa] &&
1277 // see #5832
1278 (!goog.userAgent.WEBKIT || goog.userAgent.isVersionOrHigher('526'))
1279 );
1280
1281 /**
1282 * @param {(string|Array)} query
1283 * @param {boolean=} opt_forceDOM
1284 * @return {function((string|Node)): !Array}
1285 */
1286 var getQueryFunc = function(query, opt_forceDOM) {
1287
1288 if (qsaAvail) {
1289 // if we've got a cached variant and we think we can do it, run it!
1290 var qsaCached = _queryFuncCacheQSA[query];
1291 if (qsaCached && !opt_forceDOM) {
1292 return qsaCached;
1293 }
1294 }
1295
1296 // else if we've got a DOM cached variant, assume that we already know
1297 // all we need to and use it
1298 var domCached = _queryFuncCacheDOM[query];
1299 if (domCached) {
1300 return domCached;
1301 }
1302
1303 // TODO:
1304 // today we're caching DOM and QSA branches separately so we
1305 // recalc useQSA every time. If we had a way to tag root+query
1306 // efficiently, we'd be in good shape to do a global cache.
1307
1308 var qcz = query.charAt(0);
1309 var nospace = (-1 == query.indexOf(' '));
1310
1311 // byId searches are wicked fast compared to QSA, even when filtering
1312 // is required
1313 if ((query.indexOf('#') >= 0) && (nospace)) {
1314 opt_forceDOM = true;
1315 }
1316
1317 var useQSA = (
1318 qsaAvail && (!opt_forceDOM) &&
1319 // as per CSS 3, we can't currently start w/ combinator:
1320 // http://www.w3.org/TR/css3-selectors/#w3cselgrammar
1321 (specials.indexOf(qcz) == -1) &&
1322 // IE's QSA impl sucks on pseudos
1323 (!legacyIE || (query.indexOf(':') == -1)) &&
1324
1325 (!(cssCaseBug && (query.indexOf('.') >= 0))) &&
1326
1327 // FIXME:
1328 // need to tighten up browser rules on ':contains' and '|=' to
1329 // figure out which aren't good
1330 (query.indexOf(':contains') == -1) &&
1331 (query.indexOf('|=') == -1) // some browsers don't understand it
1332 );
1333
1334 // TODO:
1335 // if we've got a descendant query (e.g., '> .thinger' instead of
1336 // just '.thinger') in a QSA-able doc, but are passed a child as a
1337 // root, it should be possible to give the item a synthetic ID and
1338 // trivially rewrite the query to the form '#synid > .thinger' to
1339 // use the QSA branch
1340
1341
1342 if (useQSA) {
1343 var tq = (specials.indexOf(query.charAt(query.length - 1)) >= 0) ?
1344 (query + ' *') : query;
1345 return _queryFuncCacheQSA[query] = function(root) {
1346 try {
1347 // the QSA system contains an egregious spec bug which
1348 // limits us, effectively, to only running QSA queries over
1349 // entire documents. See:
1350 // http://ejohn.org/blog/thoughts-on-queryselectorall/
1351 // despite this, we can also handle QSA runs on simple
1352 // selectors, but we don't want detection to be expensive
1353 // so we're just checking for the presence of a space char
1354 // right now. Not elegant, but it's cheaper than running
1355 // the query parser when we might not need to
1356 if (!((9 == root.nodeType) || nospace)) {
1357 throw new Error('');
1358 }
1359 var r = root[qsa](tq);
1360 // IE QSA queries may incorrectly include comment nodes, so we throw
1361 // the zipping function into 'remove' comments mode instead of the
1362 // normal 'skip it' which every other QSA-clued browser enjoys
1363 // skip expensive duplication checks and just wrap in an array.
1364 if (legacyIE) {
1365 r.commentStrip = true;
1366 } else {
1367 r.nozip = true;
1368 }
1369 return r;
1370 } catch (e) {
1371 // else run the DOM branch on this query, ensuring that we
1372 // default that way in the future
1373 return getQueryFunc(query, true)(root);
1374 }
1375 };
1376 } else {
1377 // DOM branch
1378 var parts = query.split(/\s*,\s*/);
1379 return _queryFuncCacheDOM[query] =
1380 ((parts.length < 2) ?
1381 // if not a compound query (e.g., '.foo, .bar'), cache and
1382 // return a dispatcher
1383 getStepQueryFunc(query) :
1384 // if it *is* a complex query, break it up into its
1385 // constituent parts and return a dispatcher that will
1386 // merge the parts when run
1387 function(root) {
1388 var pindex =
1389 0, // avoid array alloc for every invocation
1390 ret = [],
1391 tp;
1392 while (tp = parts[pindex++]) {
1393 ret = ret.concat(getStepQueryFunc(tp)(root));
1394 }
1395 return ret;
1396 });
1397 }
1398 };
1399
1400 var _zipIdx = 0;
1401
1402 // NOTE:
1403 // this function is Moo inspired, but our own impl to deal correctly
1404 // with XML in IE
1405 var _nodeUID = legacyIE ? function(node) {
1406 if (caseSensitive) {
1407 // XML docs don't have uniqueID on their nodes
1408 return node.getAttribute('_uid') ||
1409 node.setAttribute('_uid', ++_zipIdx) || _zipIdx;
1410
1411 } else {
1412 return node.uniqueID;
1413 }
1414 } :
1415 function(node) {
1416 return (node['_uid'] || (node['_uid'] = ++_zipIdx));
1417 };
1418
1419 // determine if a node in is unique in a 'bag'. In this case we don't want
1420 // to flatten a list of unique items, but rather just tell if the item in
1421 // question is already in the bag. Normally we'd just use hash lookup to do
1422 // this for us but IE's DOM is busted so we can't really count on that. On
1423 // the upside, it gives us a built in unique ID function.
1424 var _isUnique = function(node, bag) {
1425 if (!bag) {
1426 return 1;
1427 }
1428 var id = _nodeUID(node);
1429 if (!bag[id]) {
1430 return bag[id] = 1;
1431 }
1432 return 0;
1433 };
1434
1435 // attempt to efficiently determine if an item in a list is a dupe,
1436 // returning a list of 'uniques', hopefully in document order
1437 var _zipIdxName = '_zipIdx';
1438 var _zip = function(arr) {
1439 if (arr && arr.nozip) {
1440 return arr;
1441 }
1442 var ret = [];
1443 if (!arr || !arr.length) {
1444 return ret;
1445 }
1446 if (arr[0]) {
1447 ret.push(arr[0]);
1448 }
1449 if (arr.length < 2) {
1450 return ret;
1451 }
1452
1453 _zipIdx++;
1454
1455 // we have to fork here for IE and XML docs because we can't set
1456 // expandos on their nodes (apparently). *sigh*
1457 if (legacyIE && caseSensitive) {
1458 var szidx = _zipIdx + '';
1459 arr[0].setAttribute(_zipIdxName, szidx);
1460 for (var x = 1, te; te = arr[x]; x++) {
1461 if (arr[x].getAttribute(_zipIdxName) != szidx) {
1462 ret.push(te);
1463 }
1464 te.setAttribute(_zipIdxName, szidx);
1465 }
1466 } else if (legacyIE && arr.commentStrip) {
1467 try {
1468 for (var x = 1, te; te = arr[x]; x++) {
1469 if (isElement(te)) {
1470 ret.push(te);
1471 }
1472 }
1473 } catch (e) { /* squelch */ }
1474 } else {
1475 if (arr[0]) {
1476 arr[0][_zipIdxName] = _zipIdx;
1477 }
1478 for (var x = 1, te; te = arr[x]; x++) {
1479 if (arr[x][_zipIdxName] != _zipIdx) {
1480 ret.push(te);
1481 }
1482 te[_zipIdxName] = _zipIdx;
1483 }
1484 }
1485 return ret;
1486 };
1487
1488 /**
1489 * The main executor. Type specification from above.
1490 * @param {string|Array} query The query.
1491 * @param {(string|Node)=} opt_root The root.
1492 * @return {!Array} The elements that matched the query.
1493 */
1494 var query = function(query, opt_root) {
1495 // NOTE: elementsById is not currently supported
1496 // NOTE: ignores xpath-ish queries for now
1497
1498 //Set list constructor to desired value. This can change
1499 //between calls, so always re-assign here.
1500
1501 if (!query) {
1502 return [];
1503 }
1504
1505 if (query.constructor == Array) {
1506 return /** @type {!Array} */ (query);
1507 }
1508
1509 if (!goog.isString(query)) {
1510 return [query];
1511 }
1512
1513 var root = opt_root;
1514 if (goog.isString(root)) {
1515 root = goog.dom.getElement(root);
1516 if (!root) {
1517 return [];
1518 }
1519 }
1520
1521 root = root || goog.dom.getDocument();
1522 var od = root.ownerDocument || root.documentElement;
1523
1524 // throw the big case sensitivity switch
1525
1526 // NOTE:
1527 // Opera in XHTML mode doesn't detect case-sensitivity correctly
1528 // and it's not clear that there's any way to test for it
1529 caseSensitive =
1530 root.contentType && root.contentType == 'application/xml' ||
1531 goog.userAgent.OPERA &&
1532 (root.doctype || od.toString() == '[object XMLDocument]') ||
1533 !!od &&
1534 (legacyIE ? od.xml : (root.xmlVersion || od.xmlVersion));
1535
1536 // NOTE:
1537 // adding 'true' as the 2nd argument to getQueryFunc is useful for
1538 // testing the DOM branch without worrying about the
1539 // behavior/performance of the QSA branch.
1540 var r = getQueryFunc(query)(root);
1541
1542 // FIXME(slightlyoff):
1543 // need to investigate this branch WRT dojo:#8074 and dojo:#8075
1544 if (r && r.nozip) {
1545 return r;
1546 }
1547 return _zip(r);
1548 };
1549
1550 // FIXME: need to add infrastructure for post-filtering pseudos, ala :last
1551 query.pseudos = pseudos;
1552
1553 return query;
1554 })();
1555
1556 // TODO(arv): Please don't export here since it clobbers dead code elimination.
1557 goog.exportSymbol('goog.dom.query', goog.dom.query);
1558 goog.exportSymbol('goog.dom.query.pseudos', goog.dom.query.pseudos);