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