node_modules/jsdom/lib/jsdom/selectors/sizzle.js

   1 /*!
   2  * Sizzle CSS Selector Engine
   3  *  Copyright 2011, The Dojo Foundation
   4  *  Released under the MIT, BSD, and GPL Licenses.
   5  *  More information: http://sizzlejs.com/
   6  */
   7 // Patch for jsdom
   8 module.exports = function(document){
   9
  10 var chunker = /((?:\((?:\([^()]+\)|[^()]+)+\)|\[(?:\[[^\[\]]*\]|['"][^'"]*['"]|[^\[\]'"]+)+\]|\\.|[^ >+~,(\[\\]+)+|[>+~])(\s*,\s*)?((?:.|\r|\n)*)/g,
  11         expando = "sizcache" + (Math.random() + '').replace('.', ''),
  12         done = 0,
  13         toString = Object.prototype.toString,
  14         hasDuplicate = false,
  15         baseHasDuplicate = true,
  16         rBackslash = /\\/g,
  17         rReturn = /\r\n/g,
  18         rNonWord = /\W/;
  19
  20
  21 // Here we check if the JavaScript engine is using some sort of
  22 // optimization where it does not always call our comparision
  23 // function. If that is the case, discard the hasDuplicate value.
  24 //   Thus far that includes Google Chrome.
  25 [0, 0].sort(function() {
  26         baseHasDuplicate = false;
  27         return 0;
  28 });
  29
  30 var Sizzle = function( selector, context, results, seed ) {
  31         results = results || [];
  32         // PATCH for jsdom
  33         // context = context || document;
  34         // See: https://github.com/tmpvar/jsdom/issues/375
  35         context = context || seed[0].ownerDocument;
  36         var origContext = context;
  37
  38         if ( context.nodeType !== 1 && context.nodeType !== 9 ) {
  39                 return [];
  40         }
  41
  42         if ( !selector || typeof selector !== "string" ) {
  43                 return results;
  44         }
  45
  46         var m, set, checkSet, extra, ret, cur, pop, i,
  47                 prune = true,
  48                 contextXML = Sizzle.isXML( context ),
  49                 parts = [],
  50                 soFar = selector;
  51
  52         // Reset the position of the chunker regexp (start from head)
  53         do {
  54                 chunker.exec( "" );
  55                 m = chunker.exec( soFar );
  56
  57                 if ( m ) {
  58                         soFar = m[3];
  59
  60                         parts.push( m[1] );
  61
  62                         if ( m[2] ) {
  63                                 extra = m[3];
  64                                 break;
  65                         }
  66                 }
  67         } while ( m );
  68
  69         if ( parts.length > 1 && origPOS.exec( selector ) ) {
  70
  71                 if ( parts.length === 2 && Expr.relative[ parts[0] ] ) {
  72                         set = posProcess( parts[0] + parts[1], context, seed );
  73
  74                 } else {
  75                         set = Expr.relative[ parts[0] ] ?
  76                                 [ context ] :
  77                                 Sizzle( parts.shift(), context );
  78
  79                         while ( parts.length ) {
  80                                 selector = parts.shift();
  81
  82                                 if ( Expr.relative[ selector ] ) {
  83                                         selector += parts.shift();
  84                                 }
  85
  86                                 set = posProcess( selector, set, seed );
  87                         }
  88                 }
  89
  90         } else {
  91                 // Take a shortcut and set the context if the root selector is an ID
  92                 // (but not if it'll be faster if the inner selector is an ID)
  93                 if ( !seed && parts.length > 1 && context.nodeType === 9 && !contextXML &&
  94                                 Expr.match.ID.test(parts[0]) && !Expr.match.ID.test(parts[parts.length - 1]) ) {
  95
  96                         ret = Sizzle.find( parts.shift(), context, contextXML );
  97                         context = ret.expr ?
  98                                 Sizzle.filter( ret.expr, ret.set )[0] :
  99                                 ret.set[0];
 100                 }
 101
 102                 if ( context ) {
 103                         ret = seed ?
 104                                 { expr: parts.pop(), set: makeArray(seed) } :
 105                                 Sizzle.find( parts.pop(), parts.length === 1 && (parts[0] === "~" || parts[0] === "+") && context.parentNode ? context.parentNode : context, contextXML );
 106
 107                         set = ret.expr ?
 108                                 Sizzle.filter( ret.expr, ret.set ) :
 109                                 ret.set;
 110
 111                         if ( parts.length > 0 ) {
 112                                 checkSet = makeArray( set );
 113
 114                         } else {
 115                                 prune = false;
 116                         }
 117
 118                         while ( parts.length ) {
 119                                 cur = parts.pop();
 120                                 pop = cur;
 121
 122                                 if ( !Expr.relative[ cur ] ) {
 123                                         cur = "";
 124                                 } else {
 125                                         pop = parts.pop();
 126                                 }
 127
 128                                 if ( pop == null ) {
 129                                         pop = context;
 130                                 }
 131
 132                                 Expr.relative[ cur ]( checkSet, pop, contextXML );
 133                         }
 134
 135                 } else {
 136                         checkSet = parts = [];
 137                 }
 138         }
 139
 140         if ( !checkSet ) {
 141                 checkSet = set;
 142         }
 143
 144         if ( !checkSet ) {
 145                 Sizzle.error( cur || selector );
 146         }
 147
 148         if ( toString.call(checkSet) === "[object Array]" ) {
 149                 if ( !prune ) {
 150                         results.push.apply( results, checkSet );
 151
 152                 } else if ( context && context.nodeType === 1 ) {
 153                         for ( i = 0; checkSet[i] != null; i++ ) {
 154                                 if ( checkSet[i] && (checkSet[i] === true || checkSet[i].nodeType === 1 && Sizzle.contains(context, checkSet[i])) ) {
 155                                         results.push( set[i] );
 156                                 }
 157                         }
 158
 159                 } else {
 160                         for ( i = 0; checkSet[i] != null; i++ ) {
 161                                 if ( checkSet[i] && checkSet[i].nodeType === 1 ) {
 162                                         results.push( set[i] );
 163                                 }
 164                         }
 165                 }
 166
 167         } else {
 168                 makeArray( checkSet, results );
 169         }
 170
 171         if ( extra ) {
 172                 Sizzle( extra, origContext, results, seed );
 173                 Sizzle.uniqueSort( results );
 174         }
 175
 176         return results;
 177 };
 178
 179 Sizzle.uniqueSort = function( results ) {
 180         if ( sortOrder ) {
 181                 hasDuplicate = baseHasDuplicate;
 182                 results.sort( sortOrder );
 183
 184                 if ( hasDuplicate ) {
 185                         for ( var i = 1; i < results.length; i++ ) {
 186                                 if ( results[i] === results[ i - 1 ] ) {
 187                                         results.splice( i--, 1 );
 188                                 }
 189                         }
 190                 }
 191         }
 192
 193         return results;
 194 };
 195
 196 Sizzle.matches = function( expr, set ) {
 197         return Sizzle( expr, null, null, set );
 198 };
 199
 200 Sizzle.matchesSelector = function( node, expr ) {
 201         return Sizzle( expr, null, null, [node] ).length > 0;
 202 };
 203
 204 Sizzle.find = function( expr, context, isXML ) {
 205         var set, i, len, match, type, left;
 206
 207         if ( !expr ) {
 208                 return [];
 209         }
 210
 211         for ( i = 0, len = Expr.order.length; i < len; i++ ) {
 212                 type = Expr.order[i];
 213
 214                 if ( (match = Expr.leftMatch[ type ].exec( expr )) ) {
 215                         left = match[1];
 216                         match.splice( 1, 1 );
 217
 218                         if ( left.substr( left.length - 1 ) !== "\\" ) {
 219                                 match[1] = (match[1] || "").replace( rBackslash, "" );
 220                                 set = Expr.find[ type ]( match, context, isXML );
 221
 222                                 if ( set != null ) {
 223                                         expr = expr.replace( Expr.match[ type ], "" );
 224                                         break;
 225                                 }
 226                         }
 227                 }
 228         }
 229
 230         if ( !set ) {
 231                 set = typeof context.getElementsByTagName !== "undefined" ?
 232                         context.getElementsByTagName( "*" ) :
 233                         [];
 234         }
 235
 236         return { set: set, expr: expr };
 237 };
 238
 239 Sizzle.filter = function( expr, set, inplace, not ) {
 240         var match, anyFound,
 241                 type, found, item, filter, left,
 242                 i, pass,
 243                 old = expr,
 244                 result = [],
 245                 curLoop = set,
 246                 isXMLFilter = set && set[0] && Sizzle.isXML( set[0] );
 247
 248         while ( expr && set.length ) {
 249                 for ( type in Expr.filter ) {
 250                         if ( (match = Expr.leftMatch[ type ].exec( expr )) != null && match[2] ) {
 251                                 filter = Expr.filter[ type ];
 252                                 left = match[1];
 253
 254                                 anyFound = false;
 255
 256                                 match.splice(1,1);
 257
 258                                 if ( left.substr( left.length - 1 ) === "\\" ) {
 259                                         continue;
 260                                 }
 261
 262                                 if ( curLoop === result ) {
 263                                         result = [];
 264                                 }
 265
 266                                 if ( Expr.preFilter[ type ] ) {
 267                                         match = Expr.preFilter[ type ]( match, curLoop, inplace, result, not, isXMLFilter );
 268
 269                                         if ( !match ) {
 270                                                 anyFound = found = true;
 271
 272                                         } else if ( match === true ) {
 273                                                 continue;
 274                                         }
 275                                 }
 276
 277                                 if ( match ) {
 278                                         for ( i = 0; (item = curLoop[i]) != null; i++ ) {
 279                                                 if ( item ) {
 280                                                         found = filter( item, match, i, curLoop );
 281                                                         pass = not ^ found;
 282
 283                                                         if ( inplace && found != null ) {
 284                                                                 if ( pass ) {
 285                                                                         anyFound = true;
 286
 287                                                                 } else {
 288                                                                         curLoop[i] = false;
 289                                                                 }
 290
 291                                                         } else if ( pass ) {
 292                                                                 result.push( item );
 293                                                                 anyFound = true;
 294                                                         }
 295                                                 }
 296                                         }
 297                                 }
 298
 299                                 if ( found !== undefined ) {
 300                                         if ( !inplace ) {
 301                                                 curLoop = result;
 302                                         }
 303
 304                                         expr = expr.replace( Expr.match[ type ], "" );
 305
 306                                         if ( !anyFound ) {
 307                                                 return [];
 308                                         }
 309
 310                                         break;
 311                                 }
 312                         }
 313                 }
 314
 315                 // Improper expression
 316                 if ( expr === old ) {
 317                         if ( anyFound == null ) {
 318                                 Sizzle.error( expr );
 319
 320                         } else {
 321                                 break;
 322                         }
 323                 }
 324
 325                 old = expr;
 326         }
 327
 328         return curLoop;
 329 };
 330
 331 Sizzle.error = function( msg ) {
 332         throw new Error( "Syntax error, unrecognized expression: " + msg );
 333 };
 334
 335 /**
 336  * Utility function for retreiving the text value of an array of DOM nodes
 337  * @param {Array|Element} elem
 338  */
 339 var getText = Sizzle.getText = function( elem ) {
 340     var i, node,
 341                 nodeType = elem.nodeType,
 342                 ret = "";
 343
 344         if ( nodeType ) {
 345                 if ( nodeType === 1 || nodeType === 9 || nodeType === 11 ) {
 346                         // Use textContent || innerText for elements
 347                         if ( typeof elem.textContent === 'string' ) {
 348                                 return elem.textContent;
 349                         } else if ( typeof elem.innerText === 'string' ) {
 350                                 // Replace IE's carriage returns
 351                                 return elem.innerText.replace( rReturn, '' );
 352                         } else {
 353                                 // Traverse it's children
 354                                 for ( elem = elem.firstChild; elem; elem = elem.nextSibling) {
 355                                         ret += getText( elem );
 356                                 }
 357                         }
 358                 } else if ( nodeType === 3 || nodeType === 4 ) {
 359                         return elem.nodeValue;
 360                 }
 361         } else {
 362
 363                 // If no nodeType, this is expected to be an array
 364                 for ( i = 0; (node = elem[i]); i++ ) {
 365                         // Do not traverse comment nodes
 366                         if ( node.nodeType !== 8 ) {
 367                                 ret += getText( node );
 368                         }
 369                 }
 370         }
 371         return ret;
 372 };
 373
 374 var Expr = Sizzle.selectors = {
 375         order: [ "ID", "NAME", "TAG" ],
 376
 377         match: {
 378                 ID: /#((?:[\w\u00c0-\uFFFF\-]|\\.)+)/,
 379                 CLASS: /\.((?:[\w\u00c0-\uFFFF\-]|\\.)+)/,
 380                 NAME: /\[name=['"]*((?:[\w\u00c0-\uFFFF\-]|\\.)+)['"]*\]/,
 381                 ATTR: /\[\s*((?:[\w\u00c0-\uFFFF\-]|\\.)+)\s*(?:(\S?=)\s*(?:(['"])(.*?)\3|(#?(?:[\w\u00c0-\uFFFF\-]|\\.)*)|)|)\s*\]/,
 382                 TAG: /^((?:[\w\u00c0-\uFFFF\*\-]|\\.)+)/,
 383                 CHILD: /:(only|nth|last|first)-child(?:\(\s*(even|odd|(?:[+\-]?\d+|(?:[+\-]?\d*)?n\s*(?:[+\-]\s*\d+)?))\s*\))?/,
 384                 POS: /:(nth|eq|gt|lt|first|last|even|odd)(?:\((\d*)\))?(?=[^\-]|$)/,
 385                 PSEUDO: /:((?:[\w\u00c0-\uFFFF\-]|\\.)+)(?:\((['"]?)((?:\([^\)]+\)|[^\(\)]*)+)\2\))?/
 386         },
 387
 388         leftMatch: {},
 389
 390         attrMap: {
 391                 "class": "className",
 392                 "for": "htmlFor"
 393         },
 394
 395         attrHandle: {
 396                 href: function( elem ) {
 397                         return elem.getAttribute( "href" );
 398                 },
 399                 type: function( elem ) {
 400                         return elem.getAttribute( "type" );
 401                 }
 402         },
 403
 404         relative: {
 405                 "+": function(checkSet, part){
 406                         var isPartStr = typeof part === "string",
 407                                 isTag = isPartStr && !rNonWord.test( part ),
 408                                 isPartStrNotTag = isPartStr && !isTag;
 409
 410                         if ( isTag ) {
 411                                 part = part.toLowerCase();
 412                         }
 413
 414                         for ( var i = 0, l = checkSet.length, elem; i < l; i++ ) {
 415                                 if ( (elem = checkSet[i]) ) {
 416                                         while ( (elem = elem.previousSibling) && elem.nodeType !== 1 ) {}
 417
 418                                         checkSet[i] = isPartStrNotTag || elem && elem.nodeName.toLowerCase() === part ?
 419                                                 elem || false :
 420                                                 elem === part;
 421                                 }
 422                         }
 423
 424                         if ( isPartStrNotTag ) {
 425                                 Sizzle.filter( part, checkSet, true );
 426                         }
 427                 },
 428
 429                 ">": function( checkSet, part ) {
 430                         var elem,
 431                                 isPartStr = typeof part === "string",
 432                                 i = 0,
 433                                 l = checkSet.length;
 434
 435                         if ( isPartStr && !rNonWord.test( part ) ) {
 436                                 part = part.toLowerCase();
 437
 438                                 for ( ; i < l; i++ ) {
 439                                         elem = checkSet[i];
 440
 441                                         if ( elem ) {
 442                                                 var parent = elem.parentNode;
 443                                                 checkSet[i] = parent.nodeName.toLowerCase() === part ? parent : false;
 444                                         }
 445                                 }
 446
 447                         } else {
 448                                 for ( ; i < l; i++ ) {
 449                                         elem = checkSet[i];
 450
 451                                         if ( elem ) {
 452                                                 checkSet[i] = isPartStr ?
 453                                                         elem.parentNode :
 454                                                         elem.parentNode === part;
 455                                         }
 456                                 }
 457
 458                                 if ( isPartStr ) {
 459                                         Sizzle.filter( part, checkSet, true );
 460                                 }
 461                         }
 462                 },
 463
 464                 "": function(checkSet, part, isXML){
 465                         var nodeCheck,
 466                                 doneName = done++,
 467                                 checkFn = dirCheck;
 468
 469                         if ( typeof part === "string" && !rNonWord.test( part ) ) {
 470                                 part = part.toLowerCase();
 471                                 nodeCheck = part;
 472                                 checkFn = dirNodeCheck;
 473                         }
 474
 475                         checkFn( "parentNode", part, doneName, checkSet, nodeCheck, isXML );
 476                 },
 477
 478                 "~": function( checkSet, part, isXML ) {
 479                         var nodeCheck,
 480                                 doneName = done++,
 481                                 checkFn = dirCheck;
 482
 483                         if ( typeof part === "string" && !rNonWord.test( part ) ) {
 484                                 part = part.toLowerCase();
 485                                 nodeCheck = part;
 486                                 checkFn = dirNodeCheck;
 487                         }
 488
 489                         checkFn( "previousSibling", part, doneName, checkSet, nodeCheck, isXML );
 490                 }
 491         },
 492
 493         find: {
 494                 ID: function( match, context, isXML ) {
 495                         if ( typeof context.getElementById !== "undefined" && !isXML ) {
 496                                 var m = context.getElementById(match[1]);
 497                                 // Check parentNode to catch when Blackberry 4.6 returns
 498                                 // nodes that are no longer in the document #6963
 499                                 return m && m.parentNode ? [m] : [];
 500                         }
 501                 },
 502
 503                 NAME: function( match, context ) {
 504                         if ( typeof context.getElementsByName !== "undefined" ) {
 505                                 var ret = [],
 506                                         results = context.getElementsByName( match[1] );
 507
 508                                 for ( var i = 0, l = results.length; i < l; i++ ) {
 509                                         if ( results[i].getAttribute("name") === match[1] ) {
 510                                                 ret.push( results[i] );
 511                                         }
 512                                 }
 513
 514                                 return ret.length === 0 ? null : ret;
 515                         }
 516                 },
 517
 518                 TAG: function( match, context ) {
 519                         if ( typeof context.getElementsByTagName !== "undefined" ) {
 520                                 return context.getElementsByTagName( match[1] );
 521                         }
 522                 }
 523         },
 524         preFilter: {
 525                 CLASS: function( match, curLoop, inplace, result, not, isXML ) {
 526                         match = " " + match[1].replace( rBackslash, "" ) + " ";
 527
 528                         if ( isXML ) {
 529                                 return match;
 530                         }
 531
 532                         for ( var i = 0, elem; (elem = curLoop[i]) != null; i++ ) {
 533                                 if ( elem ) {
 534                                         if ( not ^ (elem.className && (" " + elem.className + " ").replace(/[\t\n\r]/g, " ").indexOf(match) >= 0) ) {
 535                                                 if ( !inplace ) {
 536                                                         result.push( elem );
 537                                                 }
 538
 539                                         } else if ( inplace ) {
 540                                                 curLoop[i] = false;
 541                                         }
 542                                 }
 543                         }
 544
 545                         return false;
 546                 },
 547
 548                 ID: function( match ) {
 549                         return match[1].replace( rBackslash, "" );
 550                 },
 551
 552                 TAG: function( match, curLoop ) {
 553                         return match[1].replace( rBackslash, "" ).toLowerCase();
 554                 },
 555
 556                 CHILD: function( match ) {
 557                         if ( match[1] === "nth" ) {
 558                                 if ( !match[2] ) {
 559                                         Sizzle.error( match[0] );
 560                                 }
 561
 562                                 match[2] = match[2].replace(/^\+|\s*/g, '');
 563
 564                                 // parse equations like 'even', 'odd', '5', '2n', '3n+2', '4n-1', '-n+6'
 565                                 var test = /(-?)(\d*)(?:n([+\-]?\d*))?/.exec(
 566                                         match[2] === "even" && "2n" || match[2] === "odd" && "2n+1" ||
 567                                         !/\D/.test( match[2] ) && "0n+" + match[2] || match[2]);
 568
 569                                 // calculate the numbers (first)n+(last) including if they are negative
 570                                 match[2] = (test[1] + (test[2] || 1)) - 0;
 571                                 match[3] = test[3] - 0;
 572                         }
 573                         else if ( match[2] ) {
 574                                 Sizzle.error( match[0] );
 575                         }
 576
 577                         // TODO: Move to normal caching system
 578                         match[0] = done++;
 579
 580                         return match;
 581                 },
 582
 583                 ATTR: function( match, curLoop, inplace, result, not, isXML ) {
 584                         var name = match[1] = match[1].replace( rBackslash, "" );
 585
 586                         if ( !isXML && Expr.attrMap[name] ) {
 587                                 match[1] = Expr.attrMap[name];
 588                         }
 589
 590                         // Handle if an un-quoted value was used
 591                         match[4] = ( match[4] || match[5] || "" ).replace( rBackslash, "" );
 592
 593                         if ( match[2] === "~=" ) {
 594                                 match[4] = " " + match[4] + " ";
 595                         }
 596
 597                         return match;
 598                 },
 599
 600                 PSEUDO: function( match, curLoop, inplace, result, not ) {
 601                         if ( match[1] === "not" ) {
 602                                 // If we're dealing with a complex expression, or a simple one
 603                                 if ( ( chunker.exec(match[3]) || "" ).length > 1 || /^\w/.test(match[3]) ) {
 604                                         match[3] = Sizzle(match[3], null, null, curLoop);
 605
 606                                 } else {
 607                                         var ret = Sizzle.filter(match[3], curLoop, inplace, true ^ not);
 608
 609                                         if ( !inplace ) {
 610                                                 result.push.apply( result, ret );
 611                                         }
 612
 613                                         return false;
 614                                 }
 615
 616                         } else if ( Expr.match.POS.test( match[0] ) || Expr.match.CHILD.test( match[0] ) ) {
 617                                 return true;
 618                         }
 619
 620                         return match;
 621                 },
 622
 623                 POS: function( match ) {
 624                         match.unshift( true );
 625
 626                         return match;
 627                 }
 628         },
 629
 630         filters: {
 631                 enabled: function( elem ) {
 632                         return elem.disabled === false && elem.type !== "hidden";
 633                 },
 634
 635                 disabled: function( elem ) {
 636                         return elem.disabled === true;
 637                 },
 638
 639                 checked: function( elem ) {
 640                         return elem.checked === true;
 641                 },
 642
 643                 selected: function( elem ) {
 644                         // Accessing this property makes selected-by-default
 645                         // options in Safari work properly
 646                         if ( elem.parentNode ) {
 647                                 elem.parentNode.selectedIndex;
 648                         }
 649
 650                         return elem.selected === true;
 651                 },
 652
 653                 parent: function( elem ) {
 654                         return !!elem.firstChild;
 655                 },
 656
 657                 empty: function( elem ) {
 658                         return !elem.firstChild;
 659                 },
 660
 661                 has: function( elem, i, match ) {
 662                         return !!Sizzle( match[3], elem ).length;
 663                 },
 664
 665                 header: function( elem ) {
 666                         return (/h\d/i).test( elem.nodeName );
 667                 },
 668
 669                 text: function( elem ) {
 670                         var attr = elem.getAttribute( "type" ), type = elem.type;
 671                         // IE6 and 7 will map elem.type to 'text' for new HTML5 types (search, etc)
 672                         // use getAttribute instead to test this case
 673                         return elem.nodeName.toLowerCase() === "input" && "text" === type && ( attr === type || attr === null );
 674                 },
 675
 676                 radio: function( elem ) {
 677                         return elem.nodeName.toLowerCase() === "input" && "radio" === elem.type;
 678                 },
 679
 680                 checkbox: function( elem ) {
 681                         return elem.nodeName.toLowerCase() === "input" && "checkbox" === elem.type;
 682                 },
 683
 684                 file: function( elem ) {
 685                         return elem.nodeName.toLowerCase() === "input" && "file" === elem.type;
 686                 },
 687
 688                 password: function( elem ) {
 689                         return elem.nodeName.toLowerCase() === "input" && "password" === elem.type;
 690                 },
 691
 692                 submit: function( elem ) {
 693                         var name = elem.nodeName.toLowerCase();
 694                         return (name === "input" || name === "button") && "submit" === elem.type;
 695                 },
 696
 697                 image: function( elem ) {
 698                         return elem.nodeName.toLowerCase() === "input" && "image" === elem.type;
 699                 },
 700
 701                 reset: function( elem ) {
 702                         var name = elem.nodeName.toLowerCase();
 703                         return (name === "input" || name === "button") && "reset" === elem.type;
 704                 },
 705
 706                 button: function( elem ) {
 707                         var name = elem.nodeName.toLowerCase();
 708                         return name === "input" && "button" === elem.type || name === "button";
 709                 },
 710
 711                 input: function( elem ) {
 712                         return (/input|select|textarea|button/i).test( elem.nodeName );
 713                 },
 714
 715                 focus: function( elem ) {
 716                         return elem === elem.ownerDocument.activeElement;
 717                 }
 718         },
 719         setFilters: {
 720                 first: function( elem, i ) {
 721                         return i === 0;
 722                 },
 723
 724                 last: function( elem, i, match, array ) {
 725                         return i === array.length - 1;
 726                 },
 727
 728                 even: function( elem, i ) {
 729                         return i % 2 === 0;
 730                 },
 731
 732                 odd: function( elem, i ) {
 733                         return i % 2 === 1;
 734                 },
 735
 736                 lt: function( elem, i, match ) {
 737                         return i < match[3] - 0;
 738                 },
 739
 740                 gt: function( elem, i, match ) {
 741                         return i > match[3] - 0;
 742                 },
 743
 744                 nth: function( elem, i, match ) {
 745                         return match[3] - 0 === i;
 746                 },
 747
 748                 eq: function( elem, i, match ) {
 749                         return match[3] - 0 === i;
 750                 }
 751         },
 752         filter: {
 753                 PSEUDO: function( elem, match, i, array ) {
 754                         var name = match[1],
 755                                 filter = Expr.filters[ name ];
 756
 757                         if ( filter ) {
 758                                 return filter( elem, i, match, array );
 759
 760                         } else if ( name === "contains" ) {
 761                                 return (elem.textContent || elem.innerText || getText([ elem ]) || "").indexOf(match[3]) >= 0;
 762
 763                         } else if ( name === "not" ) {
 764                                 var not = match[3];
 765
 766                                 for ( var j = 0, l = not.length; j < l; j++ ) {
 767                                         if ( not[j] === elem ) {
 768                                                 return false;
 769                                         }
 770                                 }
 771
 772                                 return true;
 773
 774                         } else {
 775                                 Sizzle.error( name );
 776                         }
 777                 },
 778
 779                 CHILD: function( elem, match ) {
 780                         var first, last,
 781                                 doneName, parent, cache,
 782                                 count, diff,
 783                                 type = match[1],
 784                                 node = elem;
 785
 786                         switch ( type ) {
 787                                 case "only":
 788                                 case "first":
 789                                         while ( (node = node.previousSibling) ) {
 790                                                 if ( node.nodeType === 1 ) {
 791                                                         return false;
 792                                                 }
 793                                         }
 794
 795                                         if ( type === "first" ) {
 796                                                 return true;
 797                                         }
 798
 799                                         node = elem;
 800
 801                                         /* falls through */
 802                                 case "last":
 803                                         while ( (node = node.nextSibling) ) {
 804                                                 if ( node.nodeType === 1 ) {
 805                                                         return false;
 806                                                 }
 807                                         }
 808
 809                                         return true;
 810
 811                                 case "nth":
 812                                         first = match[2];
 813                                         last = match[3];
 814
 815                                         if ( first === 1 && last === 0 ) {
 816                                                 return true;
 817                                         }
 818
 819                                         doneName = match[0];
 820                                         parent = elem.parentNode;
 821
 822                                         if ( parent && (parent[ expando ] !== doneName || !elem.nodeIndex) ) {
 823                                                 count = 0;
 824
 825                                                 for ( node = parent.firstChild; node; node = node.nextSibling ) {
 826                                                         if ( node.nodeType === 1 ) {
 827                                                                 node.nodeIndex = ++count;
 828                                                         }
 829                                                 }
 830
 831                                                 parent[ expando ] = doneName;
 832                                         }
 833
 834                                         diff = elem.nodeIndex - last;
 835
 836                                         if ( first === 0 ) {
 837                                                 return diff === 0;
 838
 839                                         } else {
 840                                                 return ( diff % first === 0 && diff / first >= 0 );
 841                                         }
 842                         }
 843                 },
 844
 845                 ID: function( elem, match ) {
 846                         return elem.nodeType === 1 && elem.getAttribute("id") === match;
 847                 },
 848
 849                 TAG: function( elem, match ) {
 850                         return (match === "*" && elem.nodeType === 1) || !!elem.nodeName && elem.nodeName.toLowerCase() === match;
 851                 },
 852
 853                 CLASS: function( elem, match ) {
 854                         return (" " + (elem.className || elem.getAttribute("class")) + " ")
 855                                 .indexOf( match ) > -1;
 856                 },
 857
 858                 ATTR: function( elem, match ) {
 859                         var name = match[1],
 860                                 result = Sizzle.attr ?
 861                                         Sizzle.attr( elem, name ) :
 862                                         Expr.attrHandle[ name ] ?
 863                                         Expr.attrHandle[ name ]( elem ) :
 864                                         elem[ name ] != null ?
 865                                                 elem[ name ] :
 866                                                 elem.getAttribute( name ),
 867                                 value = result + "",
 868                                 type = match[2],
 869                                 check = match[4];
 870
 871                         return result == null ?
 872                                 type === "!=" :
 873                                 !type && Sizzle.attr ?
 874                                 result != null :
 875                                 type === "=" ?
 876                                 value === check :
 877                                 type === "*=" ?
 878                                 value.indexOf(check) >= 0 :
 879                                 type === "~=" ?
 880                                 (" " + value + " ").indexOf(check) >= 0 :
 881                                 !check ?
 882                                 value && result !== false :
 883                                 type === "!=" ?
 884                                 value !== check :
 885                                 type === "^=" ?
 886                                 value.indexOf(check) === 0 :
 887                                 type === "$=" ?
 888                                 value.substr(value.length - check.length) === check :
 889                                 type === "|=" ?
 890                                 value === check || value.substr(0, check.length + 1) === check + "-" :
 891                                 false;
 892                 },
 893
 894                 POS: function( elem, match, i, array ) {
 895                         var name = match[2],
 896                                 filter = Expr.setFilters[ name ];
 897
 898                         if ( filter ) {
 899                                 return filter( elem, i, match, array );
 900                         }
 901                 }
 902         }
 903 };
 904
 905 var origPOS = Expr.match.POS,
 906         fescape = function(all, num){
 907                 return "\\" + (num - 0 + 1);
 908         };
 909
 910 for ( var type in Expr.match ) {
 911         Expr.match[ type ] = new RegExp( Expr.match[ type ].source + (/(?![^\[]*\])(?![^\(]*\))/.source) );
 912         Expr.leftMatch[ type ] = new RegExp( /(^(?:.|\r|\n)*?)/.source + Expr.match[ type ].source.replace(/\\(\d+)/g, fescape) );
 913 }
 914 // Expose origPOS
 915 // "global" as in regardless of relation to brackets/parens
 916 Expr.match.globalPOS = origPOS;
 917
 918 var makeArray = function( array, results ) {
 919         array = Array.prototype.slice.call( array, 0 );
 920
 921         if ( results ) {
 922                 results.push.apply( results, array );
 923                 return results;
 924         }
 925
 926         return array;
 927 };
 928
 929 // Perform a simple check to determine if the browser is capable of
 930 // converting a NodeList to an array using builtin methods.
 931 // Also verifies that the returned array holds DOM nodes
 932 // (which is not the case in the Blackberry browser)
 933 try {
 934         Array.prototype.slice.call( document.documentElement.childNodes, 0 )[0].nodeType;
 935
 936 // Provide a fallback method if it does not work
 937 } catch( e ) {
 938         makeArray = function( array, results ) {
 939                 var i = 0,
 940                         ret = results || [];
 941
 942                 if ( toString.call(array) === "[object Array]" ) {
 943                         Array.prototype.push.apply( ret, array );
 944
 945                 } else {
 946                         if ( typeof array.length === "number" ) {
 947                                 for ( var l = array.length; i < l; i++ ) {
 948                                         ret.push( array[i] );
 949                                 }
 950
 951                         } else {
 952                                 for ( ; array[i]; i++ ) {
 953                                         ret.push( array[i] );
 954                                 }
 955                         }
 956                 }
 957
 958                 return ret;
 959         };
 960 }
 961
 962 var sortOrder, siblingCheck;
 963
 964 if ( document.documentElement.compareDocumentPosition ) {
 965         sortOrder = function( a, b ) {
 966                 if ( a === b ) {
 967                         hasDuplicate = true;
 968                         return 0;
 969                 }
 970
 971                 if ( !a.compareDocumentPosition || !b.compareDocumentPosition ) {
 972                         return a.compareDocumentPosition ? -1 : 1;
 973                 }
 974
 975                 return a.compareDocumentPosition(b) & 4 ? -1 : 1;
 976         };
 977
 978 } else {
 979         sortOrder = function( a, b ) {
 980                 // The nodes are identical, we can exit early
 981                 if ( a === b ) {
 982                         hasDuplicate = true;
 983                         return 0;
 984
 985                 // Fallback to using sourceIndex (in IE) if it's available on both nodes
 986                 } else if ( a.sourceIndex && b.sourceIndex ) {
 987                         return a.sourceIndex - b.sourceIndex;
 988                 }
 989
 990                 var al, bl,
 991                         ap = [],
 992                         bp = [],
 993                         aup = a.parentNode,
 994                         bup = b.parentNode,
 995                         cur = aup;
 996
 997                 // If the nodes are siblings (or identical) we can do a quick check
 998                 if ( aup === bup ) {
 999                         return siblingCheck( a, b );
1000
1001                 // If no parents were found then the nodes are disconnected
1002                 } else if ( !aup ) {
1003                         return -1;
1004
1005                 } else if ( !bup ) {
1006                         return 1;
1007                 }
1008
1009                 // Otherwise they're somewhere else in the tree so we need
1010                 // to build up a full list of the parentNodes for comparison
1011                 while ( cur ) {
1012                         ap.unshift( cur );
1013                         cur = cur.parentNode;
1014                 }
1015
1016                 cur = bup;
1017
1018                 while ( cur ) {
1019                         bp.unshift( cur );
1020                         cur = cur.parentNode;
1021                 }
1022
1023                 al = ap.length;
1024                 bl = bp.length;
1025
1026                 // Start walking down the tree looking for a discrepancy
1027                 for ( var i = 0; i < al && i < bl; i++ ) {
1028                         if ( ap[i] !== bp[i] ) {
1029                                 return siblingCheck( ap[i], bp[i] );
1030                         }
1031                 }
1032
1033                 // We ended someplace up the tree so do a sibling check
1034                 return i === al ?
1035                         siblingCheck( a, bp[i], -1 ) :
1036                         siblingCheck( ap[i], b, 1 );
1037         };
1038
1039         siblingCheck = function( a, b, ret ) {
1040                 if ( a === b ) {
1041                         return ret;
1042                 }
1043
1044                 var cur = a.nextSibling;
1045
1046                 while ( cur ) {
1047                         if ( cur === b ) {
1048                                 return -1;
1049                         }
1050
1051                         cur = cur.nextSibling;
1052                 }
1053
1054                 return 1;
1055         };
1056 }
1057
1058 // Check to see if the browser returns elements by name when
1059 // querying by getElementById (and provide a workaround)
1060 (function(){
1061         // We're going to inject a fake input element with a specified name
1062         var form = document.createElement("div"),
1063                 id = "script" + (new Date()).getTime(),
1064                 root = document.documentElement;
1065
1066         form.innerHTML = "<a name='" + id + "'/>";
1067
1068         // Inject it into the root element, check its status, and remove it quickly
1069         root.insertBefore( form, root.firstChild );
1070
1071         // The workaround has to do additional checks after a getElementById
1072         // Which slows things down for other browsers (hence the branching)
1073         if ( document.getElementById( id ) ) {
1074                 Expr.find.ID = function( match, context, isXML ) {
1075                         if ( typeof context.getElementById !== "undefined" && !isXML ) {
1076                                 var m = context.getElementById(match[1]);
1077
1078                                 return m ?
1079                                         m.id === match[1] || typeof m.getAttributeNode !== "undefined" && m.getAttributeNode("id").nodeValue === match[1] ?
1080                                                 [m] :
1081                                                 undefined :
1082                                         [];
1083                         }
1084                 };
1085
1086                 Expr.filter.ID = function( elem, match ) {
1087                         var node = typeof elem.getAttributeNode !== "undefined" && elem.getAttributeNode("id");
1088
1089                         return elem.nodeType === 1 && node && node.nodeValue === match;
1090                 };
1091         }
1092
1093         root.removeChild( form );
1094
1095         // release memory in IE
1096         root = form = null;
1097 })();
1098
1099 (function(){
1100         // Check to see if the browser returns only elements
1101         // when doing getElementsByTagName("*")
1102
1103         // Create a fake element
1104         var div = document.createElement("div");
1105         div.appendChild( document.createComment("") );
1106
1107         // Make sure no comments are found
1108         if ( div.getElementsByTagName("*").length > 0 ) {
1109                 Expr.find.TAG = function( match, context ) {
1110                         var results = context.getElementsByTagName( match[1] );
1111
1112                         // Filter out possible comments
1113                         if ( match[1] === "*" ) {
1114                                 var tmp = [];
1115
1116                                 for ( var i = 0; results[i]; i++ ) {
1117                                         if ( results[i].nodeType === 1 ) {
1118                                                 tmp.push( results[i] );
1119                                         }
1120                                 }
1121
1122                                 results = tmp;
1123                         }
1124
1125                         return results;
1126                 };
1127         }
1128
1129         // Check to see if an attribute returns normalized href attributes
1130         div.innerHTML = "<a href='#'></a>";
1131
1132         if ( div.firstChild && typeof div.firstChild.getAttribute !== "undefined" &&
1133                         div.firstChild.getAttribute("href") !== "#" ) {
1134
1135                 Expr.attrHandle.href = function( elem ) {
1136                         return elem.getAttribute( "href", 2 );
1137                 };
1138         }
1139
1140         // release memory in IE
1141         div = null;
1142 })();
1143
1144 // Patch for jsdom
1145 if ( document.querySelectorAll && false ) {
1146         (function(){
1147                 var oldSizzle = Sizzle,
1148                         div = document.createElement("div"),
1149                         id = "__sizzle__";
1150
1151                 div.innerHTML = "<p class='TEST'></p>";
1152
1153                 // Safari can't handle uppercase or unicode characters when
1154                 // in quirks mode.
1155                 if ( div.querySelectorAll && div.querySelectorAll(".TEST").length === 0 ) {
1156                         return;
1157                 }
1158
1159                 Sizzle = function( query, context, extra, seed ) {
1160                         context = context || document;
1161
1162                         // Only use querySelectorAll on non-XML documents
1163                         // (ID selectors don't work in non-HTML documents)
1164                         if ( !seed && !Sizzle.isXML(context) ) {
1165                                 // See if we find a selector to speed up
1166                                 var match = /^(\w+$)|^\.([\w\-]+$)|^#([\w\-]+$)/.exec( query );
1167
1168                                 if ( match && (context.nodeType === 1 || context.nodeType === 9) ) {
1169                                         // Speed-up: Sizzle("TAG")
1170                                         if ( match[1] ) {
1171                                                 return makeArray( context.getElementsByTagName( query ), extra );
1172
1173                                         // Speed-up: Sizzle(".CLASS")
1174                                         } else if ( match[2] && Expr.find.CLASS && context.getElementsByClassName ) {
1175                                                 return makeArray( context.getElementsByClassName( match[2] ), extra );
1176                                         }
1177                                 }
1178
1179                                 if ( context.nodeType === 9 ) {
1180                                         // Speed-up: Sizzle("body")
1181                                         // The body element only exists once, optimize finding it
1182                                         if ( query === "body" && context.body ) {
1183                                                 return makeArray( [ context.body ], extra );
1184
1185                                         // Speed-up: Sizzle("#ID")
1186                                         } else if ( match && match[3] ) {
1187                                                 var elem = context.getElementById( match[3] );
1188
1189                                                 // Check parentNode to catch when Blackberry 4.6 returns
1190                                                 // nodes that are no longer in the document #6963
1191                                                 if ( elem && elem.parentNode ) {
1192                                                         // Handle the case where IE and Opera return items
1193                                                         // by name instead of ID
1194                                                         if ( elem.id === match[3] ) {
1195                                                                 return makeArray( [ elem ], extra );
1196                                                         }
1197
1198                                                 } else {
1199                                                         return makeArray( [], extra );
1200                                                 }
1201                                         }
1202
1203                                         try {
1204                                                 return makeArray( context.querySelectorAll(query), extra );
1205                                         } catch(qsaError) {}
1206
1207                                 // qSA works strangely on Element-rooted queries
1208                                 // We can work around this by specifying an extra ID on the root
1209                                 // and working up from there (Thanks to Andrew Dupont for the technique)
1210                                 // IE 8 doesn't work on object elements
1211                                 } else if ( context.nodeType === 1 && context.nodeName.toLowerCase() !== "object" ) {
1212                                         var oldContext = context,
1213                                                 old = context.getAttribute( "id" ),
1214                                                 nid = old || id,
1215                                                 hasParent = context.parentNode,
1216                                                 relativeHierarchySelector = /^\s*[+~]/.test( query );
1217
1218                                         if ( !old ) {
1219                                                 context.setAttribute( "id", nid );
1220                                         } else {
1221                                                 nid = nid.replace( /'/g, "\\$&" );
1222                                         }
1223                                         if ( relativeHierarchySelector && hasParent ) {
1224                                                 context = context.parentNode;
1225                                         }
1226
1227                                         try {
1228                                                 if ( !relativeHierarchySelector || hasParent ) {
1229                                                         return makeArray( context.querySelectorAll( "[id='" + nid + "'] " + query ), extra );
1230                                                 }
1231
1232                                         } catch(pseudoError) {
1233                                         } finally {
1234                                                 if ( !old ) {
1235                                                         oldContext.removeAttribute( "id" );
1236                                                 }
1237                                         }
1238                                 }
1239                         }
1240
1241                         return oldSizzle(query, context, extra, seed);
1242                 };
1243
1244                 for ( var prop in oldSizzle ) {
1245                         Sizzle[ prop ] = oldSizzle[ prop ];
1246                 }
1247
1248                 // release memory in IE
1249                 div = null;
1250         })();
1251 }
1252
1253 (function(){
1254         var html = document.documentElement,
1255                 matches = html.matchesSelector || html.mozMatchesSelector || html.webkitMatchesSelector || html.msMatchesSelector;
1256
1257         if ( matches ) {
1258                 // Check to see if it's possible to do matchesSelector
1259                 // on a disconnected node (IE 9 fails this)
1260                 var disconnectedMatch = !matches.call( document.createElement( "div" ), "div" ),
1261                         pseudoWorks = false;
1262
1263                 try {
1264                         // This should fail with an exception
1265                         // Gecko does not error, returns false instead
1266                         matches.call( document.documentElement, "[test!='']:sizzle" );
1267
1268                 } catch( pseudoError ) {
1269                         pseudoWorks = true;
1270                 }
1271
1272                 Sizzle.matchesSelector = function( node, expr ) {
1273                         // Make sure that attribute selectors are quoted
1274                         expr = expr.replace(/\=\s*([^'"\]]*)\s*\]/g, "='$1']");
1275
1276                         if ( !Sizzle.isXML( node ) ) {
1277                                 try {
1278                                         if ( pseudoWorks || !Expr.match.PSEUDO.test( expr ) && !/!=/.test( expr ) ) {
1279                                                 var ret = matches.call( node, expr );
1280
1281                                                 // IE 9's matchesSelector returns false on disconnected nodes
1282                                                 if ( ret || !disconnectedMatch ||
1283                                                                 // As well, disconnected nodes are said to be in a document
1284                                                                 // fragment in IE 9, so check for that
1285                                                                 node.document && node.document.nodeType !== 11 ) {
1286                                                         return ret;
1287                                                 }
1288                                         }
1289                                 } catch(e) {}
1290                         }
1291
1292                         return Sizzle(expr, null, null, [node]).length > 0;
1293                 };
1294         }
1295 })();
1296
1297 (function(){
1298         var div = document.createElement("div");
1299
1300         div.innerHTML = "<div class='test e'></div><div class='test'></div>";
1301
1302         // Opera can't find a second classname (in 9.6)
1303         // Also, make sure that getElementsByClassName actually exists
1304         if ( !div.getElementsByClassName || div.getElementsByClassName("e").length === 0 ) {
1305                 return;
1306         }
1307
1308         // Safari caches class attributes, doesn't catch changes (in 3.2)
1309         div.lastChild.className = "e";
1310
1311         if ( div.getElementsByClassName("e").length === 1 ) {
1312                 return;
1313         }
1314
1315         Expr.order.splice(1, 0, "CLASS");
1316         Expr.find.CLASS = function( match, context, isXML ) {
1317                 if ( typeof context.getElementsByClassName !== "undefined" && !isXML ) {
1318                         return context.getElementsByClassName(match[1]);
1319                 }
1320         };
1321
1322         // release memory in IE
1323         div = null;
1324 })();
1325
1326 function dirNodeCheck( dir, cur, doneName, checkSet, nodeCheck, isXML ) {
1327         for ( var i = 0, l = checkSet.length; i < l; i++ ) {
1328                 var elem = checkSet[i];
1329
1330                 if ( elem ) {
1331                         var match = false;
1332
1333                         elem = elem[dir];
1334
1335                         while ( elem ) {
1336                                 if ( elem[ expando ] === doneName ) {
1337                                         match = checkSet[elem.sizset];
1338                                         break;
1339                                 }
1340
1341                                 if ( elem.nodeType === 1 && !isXML ){
1342                                         elem[ expando ] = doneName;
1343                                         elem.sizset = i;
1344                                 }
1345
1346                                 if ( elem.nodeName.toLowerCase() === cur ) {
1347                                         match = elem;
1348                                         break;
1349                                 }
1350
1351                                 elem = elem[dir];
1352                         }
1353
1354                         checkSet[i] = match;
1355                 }
1356         }
1357 }
1358
1359 function dirCheck( dir, cur, doneName, checkSet, nodeCheck, isXML ) {
1360         for ( var i = 0, l = checkSet.length; i < l; i++ ) {
1361                 var elem = checkSet[i];
1362
1363                 if ( elem ) {
1364                         var match = false;
1365
1366                         elem = elem[dir];
1367
1368                         while ( elem ) {
1369                                 if ( elem[ expando ] === doneName ) {
1370                                         match = checkSet[elem.sizset];
1371                                         break;
1372                                 }
1373
1374                                 if ( elem.nodeType === 1 ) {
1375                                         if ( !isXML ) {
1376                                                 elem[ expando ] = doneName;
1377                                                 elem.sizset = i;
1378                                         }
1379
1380                                         if ( typeof cur !== "string" ) {
1381                                                 if ( elem === cur ) {
1382                                                         match = true;
1383                                                         break;
1384                                                 }
1385
1386                                         } else if ( Sizzle.filter( cur, [elem] ).length > 0 ) {
1387                                                 match = elem;
1388                                                 break;
1389                                         }
1390                                 }
1391
1392                                 elem = elem[dir];
1393                         }
1394
1395                         checkSet[i] = match;
1396                 }
1397         }
1398 }
1399
1400 if ( document.documentElement.contains ) {
1401         Sizzle.contains = function( a, b ) {
1402                 return a !== b && (a.contains ? a.contains(b) : true);
1403         };
1404
1405 } else if ( document.documentElement.compareDocumentPosition ) {
1406         Sizzle.contains = function( a, b ) {
1407                 return !!(a.compareDocumentPosition(b) & 16);
1408         };
1409
1410 } else {
1411         Sizzle.contains = function() {
1412                 return false;
1413         };
1414 }
1415
1416 Sizzle.isXML = function( elem ) {
1417         // documentElement is verified for cases where it doesn't yet exist
1418         // (such as loading iframes in IE - #4833)
1419         var documentElement = (elem ? elem.ownerDocument || elem : 0).documentElement;
1420
1421         return documentElement ? documentElement.nodeName !== "HTML" : false;
1422 };
1423
1424 var posProcess = function( selector, context, seed ) {
1425         var match,
1426                 tmpSet = [],
1427                 later = "",
1428                 root = context.nodeType ? [context] : context;
1429
1430         // Position selectors must be done after the filter
1431         // And so must :not(positional) so we move all PSEUDOs to the end
1432         while ( (match = Expr.match.PSEUDO.exec( selector )) ) {
1433                 later += match[0];
1434                 selector = selector.replace( Expr.match.PSEUDO, "" );
1435         }
1436
1437         selector = Expr.relative[selector] ? selector + "*" : selector;
1438
1439         for ( var i = 0, l = root.length; i < l; i++ ) {
1440                 Sizzle( selector, root[i], tmpSet, seed );
1441         }
1442
1443         return Sizzle.filter( later, tmpSet );
1444 };
1445
1446 // EXPOSE
1447 return Sizzle;
1448
1449 };