Open-ILS/src/javascript/backend/libs/xpath.js

   1 /*
   2  * xpath.js
   3  *
   4  * An XPath 1.0 library for JavaScript.
   5  *
   6  * Cameron McCormack <cam (at) mcc.id.au>
   7  *
   8  * This work is licensed under the Creative Commons Attribution-ShareAlike
   9  * License. To view a copy of this license, visit
  10  *
  11  *   http://creativecommons.org/licenses/by-sa/2.0/
  12  *
  13  * or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford,
  14  * California 94305, USA.
  15  *
  16  * Revision 19: November 29, 2005
  17  *   Nodesets now store their nodes in a height balanced tree, increasing
  18  *   performance for the common case of selecting nodes in document order,
  19  *   thanks to Sébastien Cramatte <contact (at) zeninteractif.com>.
  20  *   AVL tree code adapted from Raimund Neumann <rnova (at) gmx.net>.
  21  *
  22  * Revision 18: October 27, 2005
  23  *   DOM 3 XPath support.  Caveats:
  24  *     - namespace prefixes aren't resolved in XPathEvaluator.createExpression,
  25  *       but in XPathExpression.evaluate.
  26  *     - XPathResult.invalidIteratorState is not implemented.
  27  *
  28  * Revision 17: October 25, 2005
  29  *   Some core XPath function fixes and a patch to avoid crashing certain
  30  *   versions of MSXML in PathExpr.prototype.getOwnerElement, thanks to
  31  *   Sébastien Cramatte <contact (at) zeninteractif.com>.
  32  *
  33  * Revision 16: September 22, 2005
  34  *   Workarounds for some IE 5.5 deficiencies.
  35  *   Fixed problem with prefix node tests on attribute nodes.
  36  *
  37  * Revision 15: May 21, 2005
  38  *   Fixed problem with QName node tests on elements with an xmlns="...".
  39  *
  40  * Revision 14: May 19, 2005
  41  *   Fixed QName node tests on attribute node regression.
  42  *
  43  * Revision 13: May 3, 2005
  44  *   Node tests are case insensitive now if working in an HTML DOM.
  45  *
  46  * Revision 12: April 26, 2005
  47  *   Updated licence.  Slight code changes to enable use of Dean
  48  *   Edwards' script compression, http://dean.edwards.name/packer/ .
  49  *
  50  * Revision 11: April 23, 2005
  51  *   Fixed bug with 'and' and 'or' operators, fix thanks to
  52  *   Sandy McArthur <sandy (at) mcarthur.org>.
  53  *
  54  * Revision 10: April 15, 2005
  55  *   Added support for a virtual root node, supposedly helpful for
  56  *   implementing XForms.  Fixed problem with QName node tests and
  57  *   the parent axis.
  58  *
  59  * Revision 9: March 17, 2005
  60  *   Namespace resolver tweaked so using the document node as the context
  61  *   for namespace lookups is equivalent to using the document element.
  62  *
  63  * Revision 8: February 13, 2005
  64  *   Handle implicit declaration of 'xmlns' namespace prefix.
  65  *   Fixed bug when comparing nodesets.
  66  *   Instance data can now be associated with a FunctionResolver, and
  67  *     workaround for MSXML not supporting 'localName' and 'getElementById',
  68  *     thanks to Grant Gongaware.
  69  *   Fix a few problems when the context node is the root node.
  70  *
  71  * Revision 7: February 11, 2005
  72  *   Default namespace resolver fix from Grant Gongaware
  73  *   <grant (at) gongaware.com>.
  74  *
  75  * Revision 6: February 10, 2005
  76  *   Fixed bug in 'number' function.
  77  *
  78  * Revision 5: February 9, 2005
  79  *   Fixed bug where text nodes not getting converted to string values.
  80  *
  81  * Revision 4: January 21, 2005
  82  *   Bug in 'name' function, fix thanks to Bill Edney.
  83  *   Fixed incorrect processing of namespace nodes.
  84  *   Fixed NamespaceResolver to resolve 'xml' namespace.
  85  *   Implemented union '|' operator.
  86  *
  87  * Revision 3: January 14, 2005
  88  *   Fixed bug with nodeset comparisons, bug lexing < and >.
  89  *
  90  * Revision 2: October 26, 2004
  91  *   QName node test namespace handling fixed.  Few other bug fixes.
  92  *
  93  * Revision 1: August 13, 2004
  94  *   Bug fixes from William J. Edney <bedney (at) technicalpursuit.com>.
  95  *   Added minimal licence.
  96  *
  97  * Initial version: June 14, 2004
  98  */
  99
 100 // XPathParser ///////////////////////////////////////////////////////////////
 101
 102 XPathParser.prototype = new Object();
 103 XPathParser.prototype.constructor = XPathParser;
 104 XPathParser.superclass = Object.prototype;
 105
 106 function XPathParser() {
 107         this.init();
 108 }
 109
 110 XPathParser.prototype.init = function() {
 111         this.reduceActions = [];
 112
 113         this.reduceActions[3] = function(rhs) {
 114                 return new OrOperation(rhs[0], rhs[2]);
 115         };
 116         this.reduceActions[5] = function(rhs) {
 117                 return new AndOperation(rhs[0], rhs[2]);
 118         };
 119         this.reduceActions[7] = function(rhs) {
 120                 return new EqualsOperation(rhs[0], rhs[2]);
 121         };
 122         this.reduceActions[8] = function(rhs) {
 123                 return new NotEqualOperation(rhs[0], rhs[2]);
 124         };
 125         this.reduceActions[10] = function(rhs) {
 126                 return new LessThanOperation(rhs[0], rhs[2]);
 127         };
 128         this.reduceActions[11] = function(rhs) {
 129                 return new GreaterThanOperation(rhs[0], rhs[2]);
 130         };
 131         this.reduceActions[12] = function(rhs) {
 132                 return new LessThanOrEqualOperation(rhs[0], rhs[2]);
 133         };
 134         this.reduceActions[13] = function(rhs) {
 135                 return new GreaterThanOrEqualOperation(rhs[0], rhs[2]);
 136         };
 137         this.reduceActions[15] = function(rhs) {
 138                 return new PlusOperation(rhs[0], rhs[2]);
 139         };
 140         this.reduceActions[16] = function(rhs) {
 141                 return new MinusOperation(rhs[0], rhs[2]);
 142         };
 143         this.reduceActions[18] = function(rhs) {
 144                 return new MultiplyOperation(rhs[0], rhs[2]);
 145         };
 146         this.reduceActions[19] = function(rhs) {
 147                 return new DivOperation(rhs[0], rhs[2]);
 148         };
 149         this.reduceActions[20] = function(rhs) {
 150                 return new ModOperation(rhs[0], rhs[2]);
 151         };
 152         this.reduceActions[22] = function(rhs) {
 153                 return new UnaryMinusOperation(rhs[1]);
 154         };
 155         this.reduceActions[24] = function(rhs) {
 156                 return new BarOperation(rhs[0], rhs[2]);
 157         };
 158         this.reduceActions[25] = function(rhs) {
 159                 return new PathExpr(undefined, undefined, rhs[0]);
 160         };
 161         this.reduceActions[27] = function(rhs) {
 162                 rhs[0].locationPath = rhs[2];
 163                 return rhs[0];
 164         };
 165         this.reduceActions[28] = function(rhs) {
 166                 rhs[0].locationPath = rhs[2];
 167                 rhs[0].locationPath.steps.unshift(new Step(Step.DESCENDANTORSELF, new NodeTest(NodeTest.NODE, undefined), []));
 168                 return rhs[0];
 169         };
 170         this.reduceActions[29] = function(rhs) {
 171                 return new PathExpr(rhs[0], [], undefined);
 172         };
 173         this.reduceActions[30] = function(rhs) {
 174                 if (Utilities.instance_of(rhs[0], PathExpr)) {
 175                         if (rhs[0].filterPredicates == undefined) {
 176                                 rhs[0].filterPredicates = [];
 177                         }
 178                         rhs[0].filterPredicates.push(rhs[1]);
 179                         return rhs[0];
 180                 } else {
 181                         return new PathExpr(rhs[0], [rhs[1]], undefined);
 182                 }
 183         };
 184         this.reduceActions[32] = function(rhs) {
 185                 return rhs[1];
 186         };
 187         this.reduceActions[33] = function(rhs) {
 188                 return new XString(rhs[0]);
 189         };
 190         this.reduceActions[34] = function(rhs) {
 191                 return new XNumber(rhs[0]);
 192         };
 193         this.reduceActions[36] = function(rhs) {
 194                 return new FunctionCall(rhs[0], []);
 195         };
 196         this.reduceActions[37] = function(rhs) {
 197                 return new FunctionCall(rhs[0], rhs[2]);
 198         };
 199         this.reduceActions[38] = function(rhs) {
 200                 return [ rhs[0] ];
 201         };
 202         this.reduceActions[39] = function(rhs) {
 203                 rhs[2].unshift(rhs[0]);
 204                 return rhs[2];
 205         };
 206         this.reduceActions[43] = function(rhs) {
 207                 return new LocationPath(true, []);
 208         };
 209         this.reduceActions[44] = function(rhs) {
 210                 rhs[1].absolute = true;
 211                 return rhs[1];
 212         };
 213         this.reduceActions[46] = function(rhs) {
 214                 return new LocationPath(false, [ rhs[0] ]);
 215         };
 216         this.reduceActions[47] = function(rhs) {
 217                 rhs[0].steps.push(rhs[2]);
 218                 return rhs[0];
 219         };
 220         this.reduceActions[49] = function(rhs) {
 221                 return new Step(rhs[0], rhs[1], []);
 222         };
 223         this.reduceActions[50] = function(rhs) {
 224                 return new Step(Step.CHILD, rhs[0], []);
 225         };
 226         this.reduceActions[51] = function(rhs) {
 227                 return new Step(rhs[0], rhs[1], rhs[2]);
 228         };
 229         this.reduceActions[52] = function(rhs) {
 230                 return new Step(Step.CHILD, rhs[0], rhs[1]);
 231         };
 232         this.reduceActions[54] = function(rhs) {
 233                 return [ rhs[0] ];
 234         };
 235         this.reduceActions[55] = function(rhs) {
 236                 rhs[1].unshift(rhs[0]);
 237                 return rhs[1];
 238         };
 239         this.reduceActions[56] = function(rhs) {
 240                 if (rhs[0] == "ancestor") {
 241                         return Step.ANCESTOR;
 242                 } else if (rhs[0] == "ancestor-or-self") {
 243                         return Step.ANCESTORORSELF;
 244                 } else if (rhs[0] == "attribute") {
 245                         return Step.ATTRIBUTE;
 246                 } else if (rhs[0] == "child") {
 247                         return Step.CHILD;
 248                 } else if (rhs[0] == "descendant") {
 249                         return Step.DESCENDANT;
 250                 } else if (rhs[0] == "descendant-or-self") {
 251                         return Step.DESCENDANTORSELF;
 252                 } else if (rhs[0] == "following") {
 253                         return Step.FOLLOWING;
 254                 } else if (rhs[0] == "following-sibling") {
 255                         return Step.FOLLOWINGSIBLING;
 256                 } else if (rhs[0] == "namespace") {
 257                         return Step.NAMESPACE;
 258                 } else if (rhs[0] == "parent") {
 259                         return Step.PARENT;
 260                 } else if (rhs[0] == "preceding") {
 261                         return Step.PRECEDING;
 262                 } else if (rhs[0] == "preceding-sibling") {
 263                         return Step.PRECEDINGSIBLING;
 264                 } else if (rhs[0] == "self") {
 265                         return Step.SELF;
 266                 }
 267                 return -1;
 268         };
 269         this.reduceActions[57] = function(rhs) {
 270                 return Step.ATTRIBUTE;
 271         };
 272         this.reduceActions[59] = function(rhs) {
 273                 if (rhs[0] == "comment") {
 274                         return new NodeTest(NodeTest.COMMENT, undefined);
 275                 } else if (rhs[0] == "text") {
 276                         return new NodeTest(NodeTest.TEXT, undefined);
 277                 } else if (rhs[0] == "processing-instruction") {
 278                         return new NodeTest(NodeTest.PI, undefined);
 279                 } else if (rhs[0] == "node") {
 280                         return new NodeTest(NodeTest.NODE, undefined);
 281                 }
 282                 return new NodeTest(-1, undefined);
 283         };
 284         this.reduceActions[60] = function(rhs) {
 285                 return new NodeTest(NodeTest.PI, rhs[2]);
 286         };
 287         this.reduceActions[61] = function(rhs) {
 288                 return rhs[1];
 289         };
 290         this.reduceActions[63] = function(rhs) {
 291                 rhs[1].absolute = true;
 292                 rhs[1].steps.unshift(new Step(Step.DESCENDANTORSELF, new NodeTest(NodeTest.NODE, undefined), []));
 293                 return rhs[1];
 294         };
 295         this.reduceActions[64] = function(rhs) {
 296                 rhs[0].steps.push(new Step(Step.DESCENDANTORSELF, new NodeTest(NodeTest.NODE, undefined), []));
 297                 rhs[0].steps.push(rhs[2]);
 298                 return rhs[0];
 299         };
 300         this.reduceActions[65] = function(rhs) {
 301                 return new Step(Step.SELF, new NodeTest(NodeTest.NODE, undefined), []);
 302         };
 303         this.reduceActions[66] = function(rhs) {
 304                 return new Step(Step.PARENT, new NodeTest(NodeTest.NODE, undefined), []);
 305         };
 306         this.reduceActions[67] = function(rhs) {
 307                 return new VariableReference(rhs[1]);
 308         };
 309         this.reduceActions[68] = function(rhs) {
 310                 return new NodeTest(NodeTest.NAMETESTANY, undefined);
 311         };
 312         this.reduceActions[69] = function(rhs) {
 313                 var prefix = rhs[0].substring(0, rhs[0].indexOf(":"));
 314                 return new NodeTest(NodeTest.NAMETESTPREFIXANY, prefix);
 315         };
 316         this.reduceActions[70] = function(rhs) {
 317                 return new NodeTest(NodeTest.NAMETESTQNAME, rhs[0]);
 318         };
 319 };
 320
 321 XPathParser.actionTable = [
 322         " s s        sssssssss    s ss  s  ss",
 323         "                 s                  ",
 324         "r  rrrrrrrrr         rrrrrrr rr  r  ",
 325         "                rrrrr               ",
 326         " s s        sssssssss    s ss  s  ss",
 327         "rs  rrrrrrrr s  sssssrrrrrr  rrs rs ",
 328         " s s        sssssssss    s ss  s  ss",
 329         "                            s       ",
 330         "                            s       ",
 331         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 332         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 333         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 334         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 335         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 336         "  s                                 ",
 337         "                            s       ",
 338         " s           s  sssss          s  s ",
 339         "r  rrrrrrrrr         rrrrrrr rr  r  ",
 340         "a                                   ",
 341         "r       s                    rr  r  ",
 342         "r      sr                    rr  r  ",
 343         "r   s  rr            s       rr  r  ",
 344         "r   rssrr            rss     rr  r  ",
 345         "r   rrrrr            rrrss   rr  r  ",
 346         "r   rrrrrsss         rrrrr   rr  r  ",
 347         "r   rrrrrrrr         rrrrr   rr  r  ",
 348         "r   rrrrrrrr         rrrrrs  rr  r  ",
 349         "r   rrrrrrrr         rrrrrr  rr  r  ",
 350         "r   rrrrrrrr         rrrrrr  rr  r  ",
 351         "r  srrrrrrrr         rrrrrrs rr sr  ",
 352         "r  srrrrrrrr         rrrrrrs rr  r  ",
 353         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 354         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 355         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 356         "r   rrrrrrrr         rrrrrr  rr  r  ",
 357         "r   rrrrrrrr         rrrrrr  rr  r  ",
 358         "r  rrrrrrrrr         rrrrrrr rr  r  ",
 359         "r  rrrrrrrrr         rrrrrrr rr  r  ",
 360         "                sssss               ",
 361         "r  rrrrrrrrr         rrrrrrr rr sr  ",
 362         "r  rrrrrrrrr         rrrrrrr rr  r  ",
 363         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 364         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 365         "                             s      ",
 366         "r  srrrrrrrr         rrrrrrs rr  r  ",
 367         "r   rrrrrrrr         rrrrr   rr  r  ",
 368         "              s                     ",
 369         "                             s      ",
 370         "                rrrrr               ",
 371         " s s        sssssssss    s sss s  ss",
 372         "r  srrrrrrrr         rrrrrrs rr  r  ",
 373         " s s        sssssssss    s ss  s  ss",
 374         " s s        sssssssss    s ss  s  ss",
 375         " s s        sssssssss    s ss  s  ss",
 376         " s s        sssssssss    s ss  s  ss",
 377         " s s        sssssssss    s ss  s  ss",
 378         " s s        sssssssss    s ss  s  ss",
 379         " s s        sssssssss    s ss  s  ss",
 380         " s s        sssssssss    s ss  s  ss",
 381         " s s        sssssssss    s ss  s  ss",
 382         " s s        sssssssss    s ss  s  ss",
 383         " s s        sssssssss    s ss  s  ss",
 384         " s s        sssssssss    s ss  s  ss",
 385         " s s        sssssssss    s ss  s  ss",
 386         " s s        sssssssss      ss  s  ss",
 387         " s s        sssssssss    s ss  s  ss",
 388         " s           s  sssss          s  s ",
 389         " s           s  sssss          s  s ",
 390         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 391         " s           s  sssss          s  s ",
 392         " s           s  sssss          s  s ",
 393         "r  rrrrrrrrr         rrrrrrr rr sr  ",
 394         "r  rrrrrrrrr         rrrrrrr rr sr  ",
 395         "r  rrrrrrrrr         rrrrrrr rr  r  ",
 396         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 397         "                             s      ",
 398         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 399         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 400         "                             rr     ",
 401         "                             s      ",
 402         "                             rs     ",
 403         "r      sr                    rr  r  ",
 404         "r   s  rr            s       rr  r  ",
 405         "r   rssrr            rss     rr  r  ",
 406         "r   rssrr            rss     rr  r  ",
 407         "r   rrrrr            rrrss   rr  r  ",
 408         "r   rrrrr            rrrss   rr  r  ",
 409         "r   rrrrr            rrrss   rr  r  ",
 410         "r   rrrrr            rrrss   rr  r  ",
 411         "r   rrrrrsss         rrrrr   rr  r  ",
 412         "r   rrrrrsss         rrrrr   rr  r  ",
 413         "r   rrrrrrrr         rrrrr   rr  r  ",
 414         "r   rrrrrrrr         rrrrr   rr  r  ",
 415         "r   rrrrrrrr         rrrrr   rr  r  ",
 416         "r   rrrrrrrr         rrrrrr  rr  r  ",
 417         "                                 r  ",
 418         "                                 s  ",
 419         "r  srrrrrrrr         rrrrrrs rr  r  ",
 420         "r  srrrrrrrr         rrrrrrs rr  r  ",
 421         "r  rrrrrrrrr         rrrrrrr rr  r  ",
 422         "r  rrrrrrrrr         rrrrrrr rr  r  ",
 423         "r  rrrrrrrrr         rrrrrrr rr  r  ",
 424         "r  rrrrrrrrr         rrrrrrr rr  r  ",
 425         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 426         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 427         " s s        sssssssss    s ss  s  ss",
 428         "r  rrrrrrrrr         rrrrrrr rr rr  ",
 429         "                             r      "
 430 ];
 431
 432 XPathParser.actionTableNumber = [
 433         " 1 0        /.-,+*)('    & %$  #  \"!",
 434         "                 J                  ",
 435         "a  aaaaaaaaa         aaaaaaa aa  a  ",
 436         "                YYYYY               ",
 437         " 1 0        /.-,+*)('    & %$  #  \"!",
 438         "K1  KKKKKKKK .  +*)('KKKKKK  KK# K\" ",
 439         " 1 0        /.-,+*)('    & %$  #  \"!",
 440         "                            N       ",
 441         "                            O       ",
 442         "e  eeeeeeeee         eeeeeee ee ee  ",
 443         "f  fffffffff         fffffff ff ff  ",
 444         "d  ddddddddd         ddddddd dd dd  ",
 445         "B  BBBBBBBBB         BBBBBBB BB BB  ",
 446         "A  AAAAAAAAA         AAAAAAA AA AA  ",
 447         "  P                                 ",
 448         "                            Q       ",
 449         " 1           .  +*)('          #  \" ",
 450         "b  bbbbbbbbb         bbbbbbb bb  b  ",
 451         "                                    ",
 452         "!       S                    !!  !  ",
 453         "\"      T\"                    \"\"  \"  ",
 454         "$   V  $$            U       $$  $  ",
 455         "&   &ZY&&            &XW     &&  &  ",
 456         ")   )))))            )))\\[   ))  )  ",
 457         ".   ....._^]         .....   ..  .  ",
 458         "1   11111111         11111   11  1  ",
 459         "5   55555555         55555`  55  5  ",
 460         "7   77777777         777777  77  7  ",
 461         "9   99999999         999999  99  9  ",
 462         ":  c::::::::         ::::::b :: a:  ",
 463         "I  fIIIIIIII         IIIIIIe II  I  ",
 464         "=  =========         ======= == ==  ",
 465         "?  ?????????         ??????? ?? ??  ",
 466         "C  CCCCCCCCC         CCCCCCC CC CC  ",
 467         "J   JJJJJJJJ         JJJJJJ  JJ  J  ",
 468         "M   MMMMMMMM         MMMMMM  MM  M  ",
 469         "N  NNNNNNNNN         NNNNNNN NN  N  ",
 470         "P  PPPPPPPPP         PPPPPPP PP  P  ",
 471         "                +*)('               ",
 472         "R  RRRRRRRRR         RRRRRRR RR aR  ",
 473         "U  UUUUUUUUU         UUUUUUU UU  U  ",
 474         "Z  ZZZZZZZZZ         ZZZZZZZ ZZ ZZ  ",
 475         "c  ccccccccc         ccccccc cc cc  ",
 476         "                             j      ",
 477         "L  fLLLLLLLL         LLLLLLe LL  L  ",
 478         "6   66666666         66666   66  6  ",
 479         "              k                     ",
 480         "                             l      ",
 481         "                XXXXX               ",
 482         " 1 0        /.-,+*)('    & %$m #  \"!",
 483         "_  f________         ______e __  _  ",
 484         " 1 0        /.-,+*)('    & %$  #  \"!",
 485         " 1 0        /.-,+*)('    & %$  #  \"!",
 486         " 1 0        /.-,+*)('    & %$  #  \"!",
 487         " 1 0        /.-,+*)('    & %$  #  \"!",
 488         " 1 0        /.-,+*)('    & %$  #  \"!",
 489         " 1 0        /.-,+*)('    & %$  #  \"!",
 490         " 1 0        /.-,+*)('    & %$  #  \"!",
 491         " 1 0        /.-,+*)('    & %$  #  \"!",
 492         " 1 0        /.-,+*)('    & %$  #  \"!",
 493         " 1 0        /.-,+*)('    & %$  #  \"!",
 494         " 1 0        /.-,+*)('    & %$  #  \"!",
 495         " 1 0        /.-,+*)('    & %$  #  \"!",
 496         " 1 0        /.-,+*)('    & %$  #  \"!",
 497         " 1 0        /.-,+*)('      %$  #  \"!",
 498         " 1 0        /.-,+*)('    & %$  #  \"!",
 499         " 1           .  +*)('          #  \" ",
 500         " 1           .  +*)('          #  \" ",
 501         ">  >>>>>>>>>         >>>>>>> >> >>  ",
 502         " 1           .  +*)('          #  \" ",
 503         " 1           .  +*)('          #  \" ",
 504         "Q  QQQQQQQQQ         QQQQQQQ QQ aQ  ",
 505         "V  VVVVVVVVV         VVVVVVV VV aV  ",
 506         "T  TTTTTTTTT         TTTTTTT TT  T  ",
 507         "@  @@@@@@@@@         @@@@@@@ @@ @@  ",
 508         "                             \x87      ",
 509         "[  [[[[[[[[[         [[[[[[[ [[ [[  ",
 510         "D  DDDDDDDDD         DDDDDDD DD DD  ",
 511         "                             HH     ",
 512         "                             \x88      ",
 513         "                             F\x89     ",
 514         "#      T#                    ##  #  ",
 515         "%   V  %%            U       %%  %  ",
 516         "'   'ZY''            'XW     ''  '  ",
 517         "(   (ZY((            (XW     ((  (  ",
 518         "+   +++++            +++\\[   ++  +  ",
 519         "*   *****            ***\\[   **  *  ",
 520         "-   -----            ---\\[   --  -  ",
 521         ",   ,,,,,            ,,,\\[   ,,  ,  ",
 522         "0   00000_^]         00000   00  0  ",
 523         "/   /////_^]         /////   //  /  ",
 524         "2   22222222         22222   22  2  ",
 525         "3   33333333         33333   33  3  ",
 526         "4   44444444         44444   44  4  ",
 527         "8   88888888         888888  88  8  ",
 528         "                                 ^  ",
 529         "                                 \x8a  ",
 530         ";  f;;;;;;;;         ;;;;;;e ;;  ;  ",
 531         "<  f<<<<<<<<         <<<<<<e <<  <  ",
 532         "O  OOOOOOOOO         OOOOOOO OO  O  ",
 533         "`  `````````         ``````` ``  `  ",
 534         "S  SSSSSSSSS         SSSSSSS SS  S  ",
 535         "W  WWWWWWWWW         WWWWWWW WW  W  ",
 536         "\\  \\\\\\\\\\\\\\\\\\         \\\\\\\\\\\\\\ \\\\ \\\\  ",
 537         "E  EEEEEEEEE         EEEEEEE EE EE  ",
 538         " 1 0        /.-,+*)('    & %$  #  \"!",
 539         "]  ]]]]]]]]]         ]]]]]]] ]] ]]  ",
 540         "                             G      "
 541 ];
 542
 543 XPathParser.gotoTable = [
 544         "3456789:;<=>?@ AB  CDEFGH IJ ",
 545         "                             ",
 546         "                             ",
 547         "                             ",
 548         "L456789:;<=>?@ AB  CDEFGH IJ ",
 549         "            M        EFGH IJ ",
 550         "       N;<=>?@ AB  CDEFGH IJ ",
 551         "                             ",
 552         "                             ",
 553         "                             ",
 554         "                             ",
 555         "                             ",
 556         "                             ",
 557         "                             ",
 558         "                             ",
 559         "                             ",
 560         "            S        EFGH IJ ",
 561         "                             ",
 562         "                             ",
 563         "                             ",
 564         "                             ",
 565         "                             ",
 566         "                             ",
 567         "                             ",
 568         "                             ",
 569         "                             ",
 570         "                             ",
 571         "                             ",
 572         "                             ",
 573         "              e              ",
 574         "                             ",
 575         "                             ",
 576         "                             ",
 577         "                             ",
 578         "                             ",
 579         "                             ",
 580         "                             ",
 581         "                             ",
 582         "                        h  J ",
 583         "              i          j   ",
 584         "                             ",
 585         "                             ",
 586         "                             ",
 587         "                             ",
 588         "                             ",
 589         "                             ",
 590         "                             ",
 591         "                             ",
 592         "                             ",
 593         "o456789:;<=>?@ ABpqCDEFGH IJ ",
 594         "                             ",
 595         "  r6789:;<=>?@ AB  CDEFGH IJ ",
 596         "   s789:;<=>?@ AB  CDEFGH IJ ",
 597         "    t89:;<=>?@ AB  CDEFGH IJ ",
 598         "    u89:;<=>?@ AB  CDEFGH IJ ",
 599         "     v9:;<=>?@ AB  CDEFGH IJ ",
 600         "     w9:;<=>?@ AB  CDEFGH IJ ",
 601         "     x9:;<=>?@ AB  CDEFGH IJ ",
 602         "     y9:;<=>?@ AB  CDEFGH IJ ",
 603         "      z:;<=>?@ AB  CDEFGH IJ ",
 604         "      {:;<=>?@ AB  CDEFGH IJ ",
 605         "       |;<=>?@ AB  CDEFGH IJ ",
 606         "       };<=>?@ AB  CDEFGH IJ ",
 607         "       ~;<=>?@ AB  CDEFGH IJ ",
 608         "         \x7f=>?@ AB  CDEFGH IJ ",
 609         "\x80456789:;<=>?@ AB  CDEFGH IJ\x81",
 610         "            \x82        EFGH IJ ",
 611         "            \x83        EFGH IJ ",
 612         "                             ",
 613         "                     \x84 GH IJ ",
 614         "                     \x85 GH IJ ",
 615         "              i          \x86   ",
 616         "              i          \x87   ",
 617         "                             ",
 618         "                             ",
 619         "                             ",
 620         "                             ",
 621         "                             ",
 622         "                             ",
 623         "                             ",
 624         "                             ",
 625         "                             ",
 626         "                             ",
 627         "                             ",
 628         "                             ",
 629         "                             ",
 630         "                             ",
 631         "                             ",
 632         "                             ",
 633         "                             ",
 634         "                             ",
 635         "                             ",
 636         "                             ",
 637         "                             ",
 638         "                             ",
 639         "                             ",
 640         "                             ",
 641         "                             ",
 642         "                             ",
 643         "                             ",
 644         "                             ",
 645         "                             ",
 646         "                             ",
 647         "                             ",
 648         "                             ",
 649         "o456789:;<=>?@ AB\x8cqCDEFGH IJ ",
 650         "                             ",
 651         "                             "
 652 ];
 653
 654 XPathParser.productions = [
 655         [1, 1, 2],
 656         [2, 1, 3],
 657         [3, 1, 4],
 658         [3, 3, 3, -9, 4],
 659         [4, 1, 5],
 660         [4, 3, 4, -8, 5],
 661         [5, 1, 6],
 662         [5, 3, 5, -22, 6],
 663         [5, 3, 5, -5, 6],
 664         [6, 1, 7],
 665         [6, 3, 6, -23, 7],
 666         [6, 3, 6, -24, 7],
 667         [6, 3, 6, -6, 7],
 668         [6, 3, 6, -7, 7],
 669         [7, 1, 8],
 670         [7, 3, 7, -25, 8],
 671         [7, 3, 7, -26, 8],
 672         [8, 1, 9],
 673         [8, 3, 8, -12, 9],
 674         [8, 3, 8, -11, 9],
 675         [8, 3, 8, -10, 9],
 676         [9, 1, 10],
 677         [9, 2, -26, 9],
 678         [10, 1, 11],
 679         [10, 3, 10, -27, 11],
 680         [11, 1, 12],
 681         [11, 1, 13],
 682         [11, 3, 13, -28, 14],
 683         [11, 3, 13, -4, 14],
 684         [13, 1, 15],
 685         [13, 2, 13, 16],
 686         [15, 1, 17],
 687         [15, 3, -29, 2, -30],
 688         [15, 1, -15],
 689         [15, 1, -16],
 690         [15, 1, 18],
 691         [18, 3, -13, -29, -30],
 692         [18, 4, -13, -29, 19, -30],
 693         [19, 1, 20],
 694         [19, 3, 20, -31, 19],
 695         [20, 1, 2],
 696         [12, 1, 14],
 697         [12, 1, 21],
 698         [21, 1, -28],
 699         [21, 2, -28, 14],
 700         [21, 1, 22],
 701         [14, 1, 23],
 702         [14, 3, 14, -28, 23],
 703         [14, 1, 24],
 704         [23, 2, 25, 26],
 705         [23, 1, 26],
 706         [23, 3, 25, 26, 27],
 707         [23, 2, 26, 27],
 708         [23, 1, 28],
 709         [27, 1, 16],
 710         [27, 2, 16, 27],
 711         [25, 2, -14, -3],
 712         [25, 1, -32],
 713         [26, 1, 29],
 714         [26, 3, -20, -29, -30],
 715         [26, 4, -21, -29, -15, -30],
 716         [16, 3, -33, 30, -34],
 717         [30, 1, 2],
 718         [22, 2, -4, 14],
 719         [24, 3, 14, -4, 23],
 720         [28, 1, -35],
 721         [28, 1, -2],
 722         [17, 2, -36, -18],
 723         [29, 1, -17],
 724         [29, 1, -19],
 725         [29, 1, -18]
 726 ];
 727
 728 XPathParser.DOUBLEDOT = 2;
 729 XPathParser.DOUBLECOLON = 3;
 730 XPathParser.DOUBLESLASH = 4;
 731 XPathParser.NOTEQUAL = 5;
 732 XPathParser.LESSTHANOREQUAL = 6;
 733 XPathParser.GREATERTHANOREQUAL = 7;
 734 XPathParser.AND = 8;
 735 XPathParser.OR = 9;
 736 XPathParser.MOD = 10;
 737 XPathParser.DIV = 11;
 738 XPathParser.MULTIPLYOPERATOR = 12;
 739 XPathParser.FUNCTIONNAME = 13;
 740 XPathParser.AXISNAME = 14;
 741 XPathParser.LITERAL = 15;
 742 XPathParser.NUMBER = 16;
 743 XPathParser.ASTERISKNAMETEST = 17;
 744 XPathParser.QNAME = 18;
 745 XPathParser.NCNAMECOLONASTERISK = 19;
 746 XPathParser.NODETYPE = 20;
 747 XPathParser.PROCESSINGINSTRUCTIONWITHLITERAL = 21;
 748 XPathParser.EQUALS = 22;
 749 XPathParser.LESSTHAN = 23;
 750 XPathParser.GREATERTHAN = 24;
 751 XPathParser.PLUS = 25;
 752 XPathParser.MINUS = 26;
 753 XPathParser.BAR = 27;
 754 XPathParser.SLASH = 28;
 755 XPathParser.LEFTPARENTHESIS = 29;
 756 XPathParser.RIGHTPARENTHESIS = 30;
 757 XPathParser.COMMA = 31;
 758 XPathParser.AT = 32;
 759 XPathParser.LEFTBRACKET = 33;
 760 XPathParser.RIGHTBRACKET = 34;
 761 XPathParser.DOT = 35;
 762 XPathParser.DOLLAR = 36;
 763
 764 XPathParser.prototype.tokenize = function(s1) {
 765         var types = [];
 766         var values = [];
 767         var s = s1 + '\0';
 768
 769         var pos = 0;
 770         var c = s.charAt(pos++);
 771         while (1) {
 772                 while (c == ' ' || c == '\t' || c == '\r' || c == '\n') {
 773                         c = s.charAt(pos++);
 774                 }
 775                 if (c == '\0' || pos >= s.length) {
 776                         break;
 777                 }
 778
 779                 if (c == '(') {
 780                         types.push(XPathParser.LEFTPARENTHESIS);
 781                         values.push(c);
 782                         c = s.charAt(pos++);
 783                         continue;
 784                 }
 785                 if (c == ')') {
 786                         types.push(XPathParser.RIGHTPARENTHESIS);
 787                         values.push(c);
 788                         c = s.charAt(pos++);
 789                         continue;
 790                 }
 791                 if (c == '[') {
 792                         types.push(XPathParser.LEFTBRACKET);
 793                         values.push(c);
 794                         c = s.charAt(pos++);
 795                         continue;
 796                 }
 797                 if (c == ']') {
 798                         types.push(XPathParser.RIGHTBRACKET);
 799                         values.push(c);
 800                         c = s.charAt(pos++);
 801                         continue;
 802                 }
 803                 if (c == '@') {
 804                         types.push(XPathParser.AT);
 805                         values.push(c);
 806                         c = s.charAt(pos++);
 807                         continue;
 808                 }
 809                 if (c == ',') {
 810                         types.push(XPathParser.COMMA);
 811                         values.push(c);
 812                         c = s.charAt(pos++);
 813                         continue;
 814                 }
 815                 if (c == '|') {
 816                         types.push(XPathParser.BAR);
 817                         values.push(c);
 818                         c = s.charAt(pos++);
 819                         continue;
 820                 }
 821                 if (c == '+') {
 822                         types.push(XPathParser.PLUS);
 823                         values.push(c);
 824                         c = s.charAt(pos++);
 825                         continue;
 826                 }
 827                 if (c == '-') {
 828                         types.push(XPathParser.MINUS);
 829                         values.push(c);
 830                         c = s.charAt(pos++);
 831                         continue;
 832                 }
 833                 if (c == '=') {
 834                         types.push(XPathParser.EQUALS);
 835                         values.push(c);
 836                         c = s.charAt(pos++);
 837                         continue;
 838                 }
 839                 if (c == '$') {
 840                         types.push(XPathParser.DOLLAR);
 841                         values.push(c);
 842                         c = s.charAt(pos++);
 843                         continue;
 844                 }
 845
 846                 if (c == '.') {
 847                         c = s.charAt(pos++);
 848                         if (c == '.') {
 849                                 types.push(XPathParser.DOUBLEDOT);
 850                                 values.push("..");
 851                                 c = s.charAt(pos++);
 852                                 continue;
 853                         }
 854                         if (c >= '0' && c <= '9') {
 855                                 var number = "." + c;
 856                                 c = s.charAt(pos++);
 857                                 while (c >= '0' && c <= '9') {
 858                                         number += c;
 859                                         c = s.charAt(pos++);
 860                                 }
 861                                 types.push(XPathParser.NUMBER);
 862                                 values.push(number);
 863                                 continue;
 864                         }
 865                         types.push(XPathParser.DOT);
 866                         values.push('.');
 867                         continue;
 868                 }
 869
 870                 if (c == '\'' || c == '"') {
 871                         var delimiter = c;
 872                         var literal = "";
 873                         while ((c = s.charAt(pos++)) != delimiter) {
 874                                 literal += c;
 875                         }
 876                         types.push(XPathParser.LITERAL);
 877                         values.push(literal);
 878                         c = s.charAt(pos++);
 879                         continue;
 880                 }
 881
 882                 if (c >= '0' && c <= '9') {
 883                         var number = c;
 884                         c = s.charAt(pos++);
 885                         while (c >= '0' && c <= '9') {
 886                                 number += c;
 887                                 c = s.charAt(pos++);
 888                         }
 889                         if (c == '.') {
 890                                 if (s.charAt(pos) >= '0' && s.charAt(pos) <= '9') {
 891                                         number += c;
 892                                         number += s.charAt(pos++);
 893                                         c = s.charAt(pos++);
 894                                         while (c >= '0' && c <= '9') {
 895                                                 number += c;
 896                                                 c = s.charAt(pos++);
 897                                         }
 898                                 }
 899                         }
 900                         types.push(XPathParser.NUMBER);
 901                         values.push(number);
 902                         continue;
 903                 }
 904
 905                 if (c == '*') {
 906                         if (types.length > 0) {
 907                                 var last = types[types.length - 1];
 908                                 if (last != XPathParser.AT
 909                                                 && last != XPathParser.DOUBLECOLON
 910                                                 && last != XPathParser.LEFTPARENTHESIS
 911                                                 && last != XPathParser.LEFTBRACKET
 912                                                 && last != XPathParser.AND
 913                                                 && last != XPathParser.OR
 914                                                 && last != XPathParser.MOD
 915                                                 && last != XPathParser.DIV
 916                                                 && last != XPathParser.MULTIPLYOPERATOR
 917                                                 && last != XPathParser.SLASH
 918                                                 && last != XPathParser.DOUBLESLASH
 919                                                 && last != XPathParser.BAR
 920                                                 && last != XPathParser.PLUS
 921                                                 && last != XPathParser.MINUS
 922                                                 && last != XPathParser.EQUALS
 923                                                 && last != XPathParser.NOTEQUAL
 924                                                 && last != XPathParser.LESSTHAN
 925                                                 && last != XPathParser.LESSTHANOREQUAL
 926                                                 && last != XPathParser.GREATERTHAN
 927                                                 && last != XPathParser.GREATERTHANOREQUAL) {
 928                                         types.push(XPathParser.MULTIPLYOPERATOR);
 929                                         values.push(c);
 930                                         c = s.charAt(pos++);
 931                                         continue;
 932                                 }
 933                         }
 934                         types.push(XPathParser.ASTERISKNAMETEST);
 935                         values.push(c);
 936                         c = s.charAt(pos++);
 937                         continue;
 938                 }
 939
 940                 if (c == ':') {
 941                         if (s.charAt(pos) == ':') {
 942                                 types.push(XPathParser.DOUBLECOLON);
 943                                 values.push("::");
 944                                 pos++;
 945                                 c = s.charAt(pos++);
 946                                 continue;
 947                         }
 948                 }
 949
 950                 if (c == '/') {
 951                         c = s.charAt(pos++);
 952                         if (c == '/') {
 953                                 types.push(XPathParser.DOUBLESLASH);
 954                                 values.push("//");
 955                                 c = s.charAt(pos++);
 956                                 continue;
 957                         }
 958                         types.push(XPathParser.SLASH);
 959                         values.push('/');
 960                         continue;
 961                 }
 962
 963                 if (c == '!') {
 964                         if (s.charAt(pos) == '=') {
 965                                 types.push(XPathParser.NOTEQUAL);
 966                                 values.push("!=");
 967                                 pos++;
 968                                 c = s.charAt(pos++);
 969                                 continue;
 970                         }
 971                 }
 972
 973                 if (c == '<') {
 974                         if (s.charAt(pos) == '=') {
 975                                 types.push(XPathParser.LESSTHANOREQUAL);
 976                                 values.push("<=");
 977                                 pos++;
 978                                 c = s.charAt(pos++);
 979                                 continue;
 980                         }
 981                         types.push(XPathParser.LESSTHAN);
 982                         values.push('<');
 983                         c = s.charAt(pos++);
 984                         continue;
 985                 }
 986
 987                 if (c == '>') {
 988                         if (s.charAt(pos) == '=') {
 989                                 types.push(XPathParser.GREATERTHANOREQUAL);
 990                                 values.push(">=");
 991                                 pos++;
 992                                 c = s.charAt(pos++);
 993                                 continue;
 994                         }
 995                         types.push(XPathParser.GREATERTHAN);
 996                         values.push('>');
 997                         c = s.charAt(pos++);
 998                         continue;
 999                 }
1000
1001                 if (c == '_' || Utilities.isLetter(c.charCodeAt(0))) {
1002                         var name = c;
1003                         c = s.charAt(pos++);
1004                         while (Utilities.isNCNameChar(c.charCodeAt(0))) {
1005                                 name += c;
1006                                 c = s.charAt(pos++);
1007                         }
1008                         if (types.length > 0) {
1009                                 var last = types[types.length - 1];
1010                                 if (last != XPathParser.AT
1011                                                 && last != XPathParser.DOUBLECOLON
1012                                                 && last != XPathParser.LEFTPARENTHESIS
1013                                                 && last != XPathParser.LEFTBRACKET
1014                                                 && last != XPathParser.AND
1015                                                 && last != XPathParser.OR
1016                                                 && last != XPathParser.MOD
1017                                                 && last != XPathParser.DIV
1018                                                 && last != XPathParser.MULTIPLYOPERATOR
1019                                                 && last != XPathParser.SLASH
1020                                                 && last != XPathParser.DOUBLESLASH
1021                                                 && last != XPathParser.BAR
1022                                                 && last != XPathParser.PLUS
1023                                                 && last != XPathParser.MINUS
1024                                                 && last != XPathParser.EQUALS
1025                                                 && last != XPathParser.NOTEQUAL
1026                                                 && last != XPathParser.LESSTHAN
1027                                                 && last != XPathParser.LESSTHANOREQUAL
1028                                                 && last != XPathParser.GREATERTHAN
1029                                                 && last != XPathParser.GREATERTHANOREQUAL) {
1030                                         if (name == "and") {
1031                                                 types.push(XPathParser.AND);
1032                                                 values.push(name);
1033                                                 continue;
1034                                         }
1035                                         if (name == "or") {
1036                                                 types.push(XPathParser.OR);
1037                                                 values.push(name);
1038                                                 continue;
1039                                         }
1040                                         if (name == "mod") {
1041                                                 types.push(XPathParser.MOD);
1042                                                 values.push(name);
1043                                                 continue;
1044                                         }
1045                                         if (name == "div") {
1046                                                 types.push(XPathParser.DIV);
1047                                                 values.push(name);
1048                                                 continue;
1049                                         }
1050                                 }
1051                         }
1052                         if (c == ':') {
1053                                 if (s.charAt(pos) == '*') {
1054                                         types.push(XPathParser.NCNAMECOLONASTERISK);
1055                                         values.push(name + ":*");
1056                                         pos++;
1057                                         c = s.charAt(pos++);
1058                                         continue;
1059                                 }
1060                                 if (s.charAt(pos) == '_' || Utilities.isLetter(s.charCodeAt(pos))) {
1061                                         name += ':';
1062                                         c = s.charAt(pos++);
1063                                         while (Utilities.isNCNameChar(c.charCodeAt(0))) {
1064                                                 name += c;
1065                                                 c = s.charAt(pos++);
1066                                         }
1067                                         if (c == '(') {
1068                                                 types.push(XPathParser.FUNCTIONNAME);
1069                                                 values.push(name);
1070                                                 continue;
1071                                         }
1072                                         types.push(XPathParser.QNAME);
1073                                         values.push(name);
1074                                         continue;
1075                                 }
1076                                 if (s.charAt(pos) == ':') {
1077                                         types.push(XPathParser.AXISNAME);
1078                                         values.push(name);
1079                                         continue;
1080                                 }
1081                         }
1082                         if (c == '(') {
1083                                 if (name == "comment" || name == "text" || name == "node") {
1084                                         types.push(XPathParser.NODETYPE);
1085                                         values.push(name);
1086                                         continue;
1087                                 }
1088                                 if (name == "processing-instruction") {
1089                                         if (s.charAt(pos) == ')') {
1090                                                 types.push(XPathParser.NODETYPE);
1091                                         } else {
1092                                                 types.push(XPathParser.PROCESSINGINSTRUCTIONWITHLITERAL);
1093                                         }
1094                                         values.push(name);
1095                                         continue;
1096                                 }
1097                                 types.push(XPathParser.FUNCTIONNAME);
1098                                 values.push(name);
1099                                 continue;
1100                         }
1101                         types.push(XPathParser.QNAME);
1102                         values.push(name);
1103                         continue;
1104                 }
1105
1106                 throw new Error("Unexpected character " + c);
1107         }
1108         types.push(1);
1109         values.push("[EOF]");
1110         return [types, values];
1111 };
1112
1113 XPathParser.SHIFT = 's';
1114 XPathParser.REDUCE = 'r';
1115 XPathParser.ACCEPT = 'a';
1116
1117 XPathParser.prototype.parse = function(s) {
1118         var types;
1119         var values;
1120         var res = this.tokenize(s);
1121         if (res == undefined) {
1122                 return undefined;
1123         }
1124         types = res[0];
1125         values = res[1];
1126         var tokenPos = 0;
1127         var state = [];
1128         var tokenType = [];
1129         var tokenValue = [];
1130         var s;
1131         var a;
1132         var t;
1133
1134         state.push(0);
1135         tokenType.push(1);
1136         tokenValue.push("_S");
1137
1138         a = types[tokenPos];
1139         t = values[tokenPos++];
1140         while (1) {
1141                 s = state[state.length - 1];
1142                 switch (XPathParser.actionTable[s].charAt(a - 1)) {
1143                         case XPathParser.SHIFT:
1144                                 tokenType.push(-a);
1145                                 tokenValue.push(t);
1146                                 state.push(XPathParser.actionTableNumber[s].charCodeAt(a - 1) - 32);
1147                                 a = types[tokenPos];
1148                                 t = values[tokenPos++];
1149                                 break;
1150                         case XPathParser.REDUCE:
1151                                 var num = XPathParser.productions[XPathParser.actionTableNumber[s].charCodeAt(a - 1) - 32][1];
1152                                 var rhs = [];
1153                                 for (var i = 0; i < num; i++) {
1154                                         tokenType.pop();
1155                                         rhs.unshift(tokenValue.pop());
1156                                         state.pop();
1157                                 }
1158                                 var s_ = state[state.length - 1];
1159                                 tokenType.push(XPathParser.productions[XPathParser.actionTableNumber[s].charCodeAt(a - 1) - 32][0]);
1160                                 if (this.reduceActions[XPathParser.actionTableNumber[s].charCodeAt(a - 1) - 32] == undefined) {
1161                                         tokenValue.push(rhs[0]);
1162                                 } else {
1163                                         tokenValue.push(this.reduceActions[XPathParser.actionTableNumber[s].charCodeAt(a - 1) - 32](rhs));
1164                                 }
1165                                 state.push(XPathParser.gotoTable[s_].charCodeAt(XPathParser.productions[XPathParser.actionTableNumber[s].charCodeAt(a - 1) - 32][0] - 2) - 33);
1166                                 break;
1167                         case XPathParser.ACCEPT:
1168                                 return new XPath(tokenValue.pop());
1169                         default:
1170                                 throw new Error("XPath parse error");
1171                 }
1172         }
1173 };
1174
1175 // XPath /////////////////////////////////////////////////////////////////////
1176
1177 XPath.prototype = new Object();
1178 XPath.prototype.constructor = XPath;
1179 XPath.superclass = Object.prototype;
1180
1181 function XPath(e) {
1182         this.expression = e;
1183 }
1184
1185 XPath.prototype.toString = function() {
1186         return this.expression.toString();
1187 };
1188
1189 XPath.prototype.evaluate = function(c) {
1190         c.contextNode = c.expressionContextNode;
1191         c.contextSize = 1;
1192         c.contextPosition = 1;
1193         c.caseInsensitive = false;
1194         if (c.contextNode != null) {
1195                 var doc = c.contextNode;
1196                 if (doc.nodeType != 9 /*Node.DOCUMENT_NODE*/) {
1197                         doc = doc.ownerDocument;
1198                 }
1199                 try {
1200                         c.caseInsensitive = doc.implementation.hasFeature("HTML", "2.0");
1201                 } catch (e) {
1202                         c.caseInsensitive = true;
1203                 }
1204         }
1205         return this.expression.evaluate(c);
1206 };
1207
1208 XPath.XML_NAMESPACE_URI = "http://www.w3.org/XML/1998/namespace";
1209 XPath.XMLNS_NAMESPACE_URI = "http://www.w3.org/2000/xmlns/";
1210
1211 // Expression ////////////////////////////////////////////////////////////////
1212
1213 Expression.prototype = new Object();
1214 Expression.prototype.constructor = Expression;
1215 Expression.superclass = Object.prototype;
1216
1217 function Expression() {
1218 }
1219
1220 Expression.prototype.init = function() {
1221 };
1222
1223 Expression.prototype.toString = function() {
1224         return "<Expression>";
1225 };
1226
1227 Expression.prototype.evaluate = function(c) {
1228         throw new Error("Could not evaluate expression.");
1229 };
1230
1231 // UnaryOperation ////////////////////////////////////////////////////////////
1232
1233 UnaryOperation.prototype = new Expression();
1234 UnaryOperation.prototype.constructor = UnaryOperation;
1235 UnaryOperation.superclass = Expression.prototype;
1236
1237 function UnaryOperation(rhs) {
1238         if (arguments.length > 0) {
1239                 this.init(rhs);
1240         }
1241 }
1242
1243 UnaryOperation.prototype.init = function(rhs) {
1244         this.rhs = rhs;
1245 };
1246
1247 // UnaryMinusOperation ///////////////////////////////////////////////////////
1248
1249 UnaryMinusOperation.prototype = new UnaryOperation();
1250 UnaryMinusOperation.prototype.constructor = UnaryMinusOperation;
1251 UnaryMinusOperation.superclass = UnaryOperation.prototype;
1252
1253 function UnaryMinusOperation(rhs) {
1254         if (arguments.length > 0) {
1255                 this.init(rhs);
1256         }
1257 }
1258
1259 UnaryMinusOperation.prototype.init = function(rhs) {
1260         UnaryMinusOperation.superclass.init.call(this, rhs);
1261 };
1262
1263 UnaryMinusOperation.prototype.evaluate = function(c) {
1264         return this.rhs.evaluate(c).number().negate();
1265 };
1266
1267 UnaryMinusOperation.prototype.toString = function() {
1268         return "-" + this.rhs.toString();
1269 };
1270
1271 // BinaryOperation ///////////////////////////////////////////////////////////
1272
1273 BinaryOperation.prototype = new Expression();
1274 BinaryOperation.prototype.constructor = BinaryOperation;
1275 BinaryOperation.superclass = Expression.prototype;
1276
1277 function BinaryOperation(lhs, rhs) {
1278         if (arguments.length > 0) {
1279                 this.init(lhs, rhs);
1280         }
1281 }
1282
1283 BinaryOperation.prototype.init = function(lhs, rhs) {
1284         this.lhs = lhs;
1285         this.rhs = rhs;
1286 };
1287
1288 // OrOperation ///////////////////////////////////////////////////////////////
1289
1290 OrOperation.prototype = new BinaryOperation();
1291 OrOperation.prototype.constructor = OrOperation;
1292 OrOperation.superclass = BinaryOperation.prototype;
1293
1294 function OrOperation(lhs, rhs) {
1295         if (arguments.length > 0) {
1296                 this.init(lhs, rhs);
1297         }
1298 }
1299
1300 OrOperation.prototype.init = function(lhs, rhs) {
1301         OrOperation.superclass.init.call(this, lhs, rhs);
1302 };
1303
1304 OrOperation.prototype.toString = function() {
1305         return "(" + this.lhs.toString() + " or " + this.rhs.toString() + ")";
1306 };
1307
1308 OrOperation.prototype.evaluate = function(c) {
1309         var b = this.lhs.evaluate(c).bool();
1310         if (b.booleanValue()) {
1311                 return b;
1312         }
1313         return this.rhs.evaluate(c).bool();
1314 };
1315
1316 // AndOperation //////////////////////////////////////////////////////////////
1317
1318 AndOperation.prototype = new BinaryOperation();
1319 AndOperation.prototype.constructor = AndOperation;
1320 AndOperation.superclass = BinaryOperation.prototype;
1321
1322 function AndOperation(lhs, rhs) {
1323         if (arguments.length > 0) {
1324                 this.init(lhs, rhs);
1325         }
1326 }
1327
1328 AndOperation.prototype.init = function(lhs, rhs) {
1329         AndOperation.superclass.init.call(this, lhs, rhs);
1330 };
1331
1332 AndOperation.prototype.toString = function() {
1333         return "(" + this.lhs.toString() + " and " + this.rhs.toString() + ")";
1334 };
1335
1336 AndOperation.prototype.evaluate = function(c) {
1337         var b = this.lhs.evaluate(c).bool();
1338         if (!b.booleanValue()) {
1339                 return b;
1340         }
1341         return this.rhs.evaluate(c).bool();
1342 };
1343
1344 // EqualsOperation ///////////////////////////////////////////////////////////
1345
1346 EqualsOperation.prototype = new BinaryOperation();
1347 EqualsOperation.prototype.constructor = EqualsOperation;
1348 EqualsOperation.superclass = BinaryOperation.prototype;
1349
1350 function EqualsOperation(lhs, rhs) {
1351         if (arguments.length > 0) {
1352                 this.init(lhs, rhs);
1353         }
1354 }
1355
1356 EqualsOperation.prototype.init = function(lhs, rhs) {
1357         EqualsOperation.superclass.init.call(this, lhs, rhs);
1358 };
1359
1360 EqualsOperation.prototype.toString = function() {
1361         return "(" + this.lhs.toString() + " = " + this.rhs.toString() + ")";
1362 };
1363
1364 EqualsOperation.prototype.evaluate = function(c) {
1365         return this.lhs.evaluate(c).equals(this.rhs.evaluate(c));
1366 };
1367
1368 // NotEqualOperation /////////////////////////////////////////////////////////
1369
1370 NotEqualOperation.prototype = new BinaryOperation();
1371 NotEqualOperation.prototype.constructor = NotEqualOperation;
1372 NotEqualOperation.superclass = BinaryOperation.prototype;
1373
1374 function NotEqualOperation(lhs, rhs) {
1375         if (arguments.length > 0) {
1376                 this.init(lhs, rhs);
1377         }
1378 }
1379
1380 NotEqualOperation.prototype.init = function(lhs, rhs) {
1381         NotEqualOperation.superclass.init.call(this, lhs, rhs);
1382 };
1383
1384 NotEqualOperation.prototype.toString = function() {
1385         return "(" + this.lhs.toString() + " != " + this.rhs.toString() + ")";
1386 };
1387
1388 NotEqualOperation.prototype.evaluate = function(c) {
1389         return this.lhs.evaluate(c).notequal(this.rhs.evaluate(c));
1390 };
1391
1392 // LessThanOperation /////////////////////////////////////////////////////////
1393
1394 LessThanOperation.prototype = new BinaryOperation();
1395 LessThanOperation.prototype.constructor = LessThanOperation;
1396 LessThanOperation.superclass = BinaryOperation.prototype;
1397
1398 function LessThanOperation(lhs, rhs) {
1399         if (arguments.length > 0) {
1400                 this.init(lhs, rhs);
1401         }
1402 }
1403
1404 LessThanOperation.prototype.init = function(lhs, rhs) {
1405         LessThanOperation.superclass.init.call(this, lhs, rhs);
1406 };
1407
1408 LessThanOperation.prototype.evaluate = function(c) {
1409         return this.lhs.evaluate(c).lessthan(this.rhs.evaluate(c));
1410 };
1411
1412 LessThanOperation.prototype.toString = function() {
1413         return "(" + this.lhs.toString() + " < " + this.rhs.toString() + ")";
1414 };
1415
1416 // GreaterThanOperation //////////////////////////////////////////////////////
1417
1418 GreaterThanOperation.prototype = new BinaryOperation();
1419 GreaterThanOperation.prototype.constructor = GreaterThanOperation;
1420 GreaterThanOperation.superclass = BinaryOperation.prototype;
1421
1422 function GreaterThanOperation(lhs, rhs) {
1423         if (arguments.length > 0) {
1424                 this.init(lhs, rhs);
1425         }
1426 }
1427
1428 GreaterThanOperation.prototype.init = function(lhs, rhs) {
1429         GreaterThanOperation.superclass.init.call(this, lhs, rhs);
1430 };
1431
1432 GreaterThanOperation.prototype.evaluate = function(c) {
1433         return this.lhs.evaluate(c).greaterthan(this.rhs.evaluate(c));
1434 };
1435
1436 GreaterThanOperation.prototype.toString = function() {
1437         return "(" + this.lhs.toString() + " > " + this.rhs.toString() + ")";
1438 };
1439
1440 // LessThanOrEqualOperation //////////////////////////////////////////////////
1441
1442 LessThanOrEqualOperation.prototype = new BinaryOperation();
1443 LessThanOrEqualOperation.prototype.constructor = LessThanOrEqualOperation;
1444 LessThanOrEqualOperation.superclass = BinaryOperation.prototype;
1445
1446 function LessThanOrEqualOperation(lhs, rhs) {
1447         if (arguments.length > 0) {
1448                 this.init(lhs, rhs);
1449         }
1450 }
1451
1452 LessThanOrEqualOperation.prototype.init = function(lhs, rhs) {
1453         LessThanOrEqualOperation.superclass.init.call(this, lhs, rhs);
1454 };
1455
1456 LessThanOrEqualOperation.prototype.evaluate = function(c) {
1457         return this.lhs.evaluate(c).lessthanorequal(this.rhs.evaluate(c));
1458 };
1459
1460 LessThanOrEqualOperation.prototype.toString = function() {
1461         return "(" + this.lhs.toString() + " <= " + this.rhs.toString() + ")";
1462 };
1463
1464 // GreaterThanOrEqualOperation ///////////////////////////////////////////////
1465
1466 GreaterThanOrEqualOperation.prototype = new BinaryOperation();
1467 GreaterThanOrEqualOperation.prototype.constructor = GreaterThanOrEqualOperation;
1468 GreaterThanOrEqualOperation.superclass = BinaryOperation.prototype;
1469
1470 function GreaterThanOrEqualOperation(lhs, rhs) {
1471         if (arguments.length > 0) {
1472                 this.init(lhs, rhs);
1473         }
1474 }
1475
1476 GreaterThanOrEqualOperation.prototype.init = function(lhs, rhs) {
1477         GreaterThanOrEqualOperation.superclass.init.call(this, lhs, rhs);
1478 };
1479
1480 GreaterThanOrEqualOperation.prototype.evaluate = function(c) {
1481         return this.lhs.evaluate(c).greaterthanorequal(this.rhs.evaluate(c));
1482 };
1483
1484 GreaterThanOrEqualOperation.prototype.toString = function() {
1485         return "(" + this.lhs.toString() + " >= " + this.rhs.toString() + ")";
1486 };
1487
1488 // PlusOperation /////////////////////////////////////////////////////////////
1489
1490 PlusOperation.prototype = new BinaryOperation();
1491 PlusOperation.prototype.constructor = PlusOperation;
1492 PlusOperation.superclass = BinaryOperation.prototype;
1493
1494 function PlusOperation(lhs, rhs) {
1495         if (arguments.length > 0) {
1496                 this.init(lhs, rhs);
1497         }
1498 }
1499
1500 PlusOperation.prototype.init = function(lhs, rhs) {
1501         PlusOperation.superclass.init.call(this, lhs, rhs);
1502 };
1503
1504 PlusOperation.prototype.evaluate = function(c) {
1505         return this.lhs.evaluate(c).number().plus(this.rhs.evaluate(c).number());
1506 };
1507
1508 PlusOperation.prototype.toString = function() {
1509         return "(" + this.lhs.toString() + " + " + this.rhs.toString() + ")";
1510 };
1511
1512 // MinusOperation ////////////////////////////////////////////////////////////
1513
1514 MinusOperation.prototype = new BinaryOperation();
1515 MinusOperation.prototype.constructor = MinusOperation;
1516 MinusOperation.superclass = BinaryOperation.prototype;
1517
1518 function MinusOperation(lhs, rhs) {
1519         if (arguments.length > 0) {
1520                 this.init(lhs, rhs);
1521         }
1522 }
1523
1524 MinusOperation.prototype.init = function(lhs, rhs) {
1525         MinusOperation.superclass.init.call(this, lhs, rhs);
1526 };
1527
1528 MinusOperation.prototype.evaluate = function(c) {
1529         return this.lhs.evaluate(c).number().minus(this.rhs.evaluate(c).number());
1530 };
1531
1532 MinusOperation.prototype.toString = function() {
1533         return "(" + this.lhs.toString() + " - " + this.rhs.toString() + ")";
1534 };
1535
1536 // MultiplyOperation /////////////////////////////////////////////////////////
1537
1538 MultiplyOperation.prototype = new BinaryOperation();
1539 MultiplyOperation.prototype.constructor = MultiplyOperation;
1540 MultiplyOperation.superclass = BinaryOperation.prototype;
1541
1542 function MultiplyOperation(lhs, rhs) {
1543         if (arguments.length > 0) {
1544                 this.init(lhs, rhs);
1545         }
1546 }
1547
1548 MultiplyOperation.prototype.init = function(lhs, rhs) {
1549         MultiplyOperation.superclass.init.call(this, lhs, rhs);
1550 };
1551
1552 MultiplyOperation.prototype.evaluate = function(c) {
1553         return this.lhs.evaluate(c).number().multiply(this.rhs.evaluate(c).number());
1554 };
1555
1556 MultiplyOperation.prototype.toString = function() {
1557         return "(" + this.lhs.toString() + " * " + this.rhs.toString() + ")";
1558 };
1559
1560 // DivOperation //////////////////////////////////////////////////////////////
1561
1562 DivOperation.prototype = new BinaryOperation();
1563 DivOperation.prototype.constructor = DivOperation;
1564 DivOperation.superclass = BinaryOperation.prototype;
1565
1566 function DivOperation(lhs, rhs) {
1567         if (arguments.length > 0) {
1568                 this.init(lhs, rhs);
1569         }
1570 }
1571
1572 DivOperation.prototype.init = function(lhs, rhs) {
1573         DivOperation.superclass.init.call(this, lhs, rhs);
1574 };
1575
1576 DivOperation.prototype.evaluate = function(c) {
1577         return this.lhs.evaluate(c).number().div(this.rhs.evaluate(c).number());
1578 };
1579
1580 DivOperation.prototype.toString = function() {
1581         return "(" + this.lhs.toString() + " div " + this.rhs.toString() + ")";
1582 };
1583
1584 // ModOperation //////////////////////////////////////////////////////////////
1585
1586 ModOperation.prototype = new BinaryOperation();
1587 ModOperation.prototype.constructor = ModOperation;
1588 ModOperation.superclass = BinaryOperation.prototype;
1589
1590 function ModOperation(lhs, rhs) {
1591         if (arguments.length > 0) {
1592                 this.init(lhs, rhs);
1593         }
1594 }
1595
1596 ModOperation.prototype.init = function(lhs, rhs) {
1597         ModOperation.superclass.init.call(this, lhs, rhs);
1598 };
1599
1600 ModOperation.prototype.evaluate = function(c) {
1601         return this.lhs.evaluate(c).number().mod(this.rhs.evaluate(c).number());
1602 };
1603
1604 ModOperation.prototype.toString = function() {
1605         return "(" + this.lhs.toString() + " mod " + this.rhs.toString() + ")";
1606 };
1607
1608 // BarOperation //////////////////////////////////////////////////////////////
1609
1610 BarOperation.prototype = new BinaryOperation();
1611 BarOperation.prototype.constructor = BarOperation;
1612 BarOperation.superclass = BinaryOperation.prototype;
1613
1614 function BarOperation(lhs, rhs) {
1615         if (arguments.length > 0) {
1616                 this.init(lhs, rhs);
1617         }
1618 }
1619
1620 BarOperation.prototype.init = function(lhs, rhs) {
1621         BarOperation.superclass.init.call(this, lhs, rhs);
1622 };
1623
1624 BarOperation.prototype.evaluate = function(c) {
1625         return this.lhs.evaluate(c).nodeset().union(this.rhs.evaluate(c).nodeset());
1626 };
1627
1628 BarOperation.prototype.toString = function() {
1629         return this.lhs.toString() + " | " + this.rhs.toString();
1630 };
1631
1632 // PathExpr //////////////////////////////////////////////////////////////////
1633
1634 PathExpr.prototype = new Expression();
1635 PathExpr.prototype.constructor = PathExpr;
1636 PathExpr.superclass = Expression.prototype;
1637
1638 function PathExpr(filter, filterPreds, locpath) {
1639         if (arguments.length > 0) {
1640                 this.init(filter, filterPreds, locpath);
1641         }
1642 }
1643
1644 PathExpr.prototype.init = function(filter, filterPreds, locpath) {
1645         PathExpr.superclass.init.call(this);
1646         this.filter = filter;
1647         this.filterPredicates = filterPreds;
1648         this.locationPath = locpath;
1649 };
1650
1651 PathExpr.prototype.evaluate = function(c) {
1652         var nodes;
1653         var xpc = new XPathContext();
1654         xpc.variableResolver = c.variableResolver;
1655         xpc.functionResolver = c.functionResolver;
1656         xpc.namespaceResolver = c.namespaceResolver;
1657         xpc.expressionContextNode = c.expressionContextNode;
1658         xpc.virtualRoot = c.virtualRoot;
1659         xpc.caseInsensitive = c.caseInsensitive;
1660         if (this.filter == null) {
1661                 nodes = [ c.contextNode ];
1662         } else {
1663                 var ns = this.filter.evaluate(c);
1664                 if (!Utilities.instance_of(ns, XNodeSet)) {
1665                         if (this.filterPredicates != null && this.filterPredicates.length > 0 || this.locationPath != null) {
1666                                 throw new Error("Path expression filter must evaluate to a nodset if predicates or location path are used");
1667                         }
1668                         return ns;
1669                 }
1670                 nodes = ns.toArray();
1671                 if (this.filterPredicates != null) {
1672                         // apply each of the predicates in turn
1673                         for (var j = 0; j < this.filterPredicates.length; j++) {
1674                                 var pred = this.filterPredicates[j];
1675                                 var newNodes = [];
1676                                 xpc.contextSize = nodes.length;
1677                                 for (xpc.contextPosition = 1; xpc.contextPosition <= xpc.contextSize; xpc.contextPosition++) {
1678                                         xpc.contextNode = nodes[xpc.contextPosition - 1];
1679                                         if (this.predicateMatches(pred, xpc)) {
1680                                                 newNodes.push(xpc.contextNode);
1681                                         }
1682                                 }
1683                                 nodes = newNodes;
1684                         }
1685                 }
1686         }
1687         if (this.locationPath != null) {
1688                 if (this.locationPath.absolute) {
1689                         if (nodes[0].nodeType != 9 /*Node.DOCUMENT_NODE*/) {
1690                                 if (xpc.virtualRoot != null) {
1691                                         nodes = [ xpc.virtualRoot ];
1692                                 } else {
1693                                         if (nodes[0].ownerDocument == null) {
1694                                                 // IE 5.5 doesn't have ownerDocument?
1695                                                 var n = nodes[0];
1696                                                 while (n.parentNode != null) {
1697                                                         n = n.parentNode;
1698                                                 }
1699                                                 nodes = [ n ];
1700                                         } else {
1701                                                 nodes = [ nodes[0].ownerDocument ];
1702                                         }
1703                                 }
1704                         } else {
1705                                 nodes = [ nodes[0] ];
1706                         }
1707                 }
1708                 for (var i = 0; i < this.locationPath.steps.length; i++) {
1709                         var step = this.locationPath.steps[i];
1710                         var newNodes = [];
1711                         for (var j = 0; j < nodes.length; j++) {
1712                                 xpc.contextNode = nodes[j];
1713                                 switch (step.axis) {
1714                                         case Step.ANCESTOR:
1715                                                 // look at all the ancestor nodes
1716                                                 if (xpc.contextNode === xpc.virtualRoot) {
1717                                                         break;
1718                                                 }
1719                                                 var m;
1720                                                 if (xpc.contextNode.nodeType == 2 /*Node.ATTRIBUTE_NODE*/) {
1721                                                         m = this.getOwnerElement(xpc.contextNode);
1722                                                 } else {
1723                                                         m = xpc.contextNode.parentNode;
1724                                                 }
1725                                                 while (m != null) {
1726                                                         if (step.nodeTest.matches(m, xpc)) {
1727                                                                 newNodes.push(m);
1728                                                         }
1729                                                         if (m === xpc.virtualRoot) {
1730                                                                 break;
1731                                                         }
1732                                                         m = m.parentNode;
1733                                                 }
1734                                                 break;
1735
1736                                         case Step.ANCESTORORSELF:
1737                                                 // look at all the ancestor nodes and the current node
1738                                                 for (var m = xpc.contextNode; m != null; m = m.nodeType == 2 /*Node.ATTRIBUTE_NODE*/ ? this.getOwnerElement(m) : m.parentNode) {
1739                                                         if (step.nodeTest.matches(m, xpc)) {
1740                                                                 newNodes.push(m);
1741                                                         }
1742                                                         if (m === xpc.virtualRoot) {
1743                                                                 break;
1744                                                         }
1745                                                 }
1746                                                 break;
1747
1748                                         case Step.ATTRIBUTE:
1749                                                 // look at the attributes
1750                                                 var nnm = xpc.contextNode.attributes;
1751                                                 if (nnm != null) {
1752                                                         for (var k = 0; k < nnm.length; k++) {
1753                                                                 var m = nnm.item(k);
1754                                                                 if (step.nodeTest.matches(m, xpc)) {
1755                                                                         newNodes.push(m);
1756                                                                 }
1757                                                         }
1758                                                 }
1759                                                 break;
1760
1761                                         case Step.CHILD:
1762                                                 // look at all child elements
1763                                                 for (var m = xpc.contextNode.firstChild; m != null; m = m.nextSibling) {
1764                                                         if (step.nodeTest.matches(m, xpc)) {
1765                                                                 newNodes.push(m);
1766                                                         }
1767                                                 }
1768                                                 break;
1769
1770                                         case Step.DESCENDANT:
1771                                                 // look at all descendant nodes
1772                                                 var st = [ xpc.contextNode.firstChild ];
1773                                                 while (st.length > 0) {
1774                                                         for (var m = st.pop(); m != null; ) {
1775                                                                 if (step.nodeTest.matches(m, xpc)) {
1776                                                                         newNodes.push(m);
1777                                                                 }
1778                                                                 if (m.firstChild != null) {
1779                                                                         st.push(m.nextSibling);
1780                                                                         m = m.firstChild;
1781                                                                 } else {
1782                                                                         m = m.nextSibling;
1783                                                                 }
1784                                                         }
1785                                                 }
1786                                                 break;
1787
1788                                         case Step.DESCENDANTORSELF:
1789                                                 // look at self
1790                                                 if (step.nodeTest.matches(xpc.contextNode, xpc)) {
1791                                                         newNodes.push(xpc.contextNode);
1792                                                 }
1793                                                 // look at all descendant nodes
1794                                                 var st = [ xpc.contextNode.firstChild ];
1795                                                 while (st.length > 0) {
1796                                                         for (var m = st.pop(); m != null; ) {
1797                                                                 if (step.nodeTest.matches(m, xpc)) {
1798                                                                         newNodes.push(m);
1799                                                                 }
1800                                                                 if (m.firstChild != null) {
1801                                                                         st.push(m.nextSibling);
1802                                                                         m = m.firstChild;
1803                                                                 } else {
1804                                                                         m = m.nextSibling;
1805                                                                 }
1806                                                         }
1807                                                 }
1808                                                 break;
1809
1810                                         case Step.FOLLOWING:
1811                                                 if (xpc.contextNode === xpc.virtualRoot) {
1812                                                         break;
1813                                                 }
1814                                                 var st = [];
1815                                                 if (xpc.contextNode.firstChild != null) {
1816                                                         st.unshift(xpc.contextNode.firstChild);
1817                                                 } else {
1818                                                         st.unshift(xpc.contextNode.nextSibling);
1819                                                 }
1820                                                 for (var m = xpc.contextNode.parentNode; m != null && m.nodeType != 9 /*Node.DOCUMENT_NODE*/ && m !== xpc.virtualRoot; m = m.parentNode) {
1821                                                         st.unshift(m.nextSibling);
1822                                                 }
1823                                                 do {
1824                                                         for (var m = st.pop(); m != null; ) {
1825                                                                 if (step.nodeTest.matches(m, xpc)) {
1826                                                                         newNodes.push(m);
1827                                                                 }
1828                                                                 if (m.firstChild != null) {
1829                                                                         st.push(m.nextSibling);
1830                                                                         m = m.firstChild;
1831                                                                 } else {
1832                                                                         m = m.nextSibling;
1833                                                                 }
1834                                                         }
1835                                                 } while (st.length > 0);
1836                                                 break;
1837
1838                                         case Step.FOLLOWINGSIBLING:
1839                                                 if (xpc.contextNode === xpc.virtualRoot) {
1840                                                         break;
1841                                                 }
1842                                                 for (var m = xpc.contextNode.nextSibling; m != null; m = m.nextSibling) {
1843                                                         if (step.nodeTest.matches(m, xpc)) {
1844                                                                 newNodes.push(m);
1845                                                         }
1846                                                 }
1847                                                 break;
1848
1849                                         case Step.NAMESPACE:
1850                                                 var n = {};
1851                                                 if (xpc.contextNode.nodeType == 1 /*Node.ELEMENT_NODE*/) {
1852                                                         n["xml"] = XPath.XML_NAMESPACE_URI;
1853                                                         n["xmlns"] = XPath.XMLNS_NAMESPACE_URI;
1854                                                         for (var m = xpc.contextNode; m != null && m.nodeType == 1 /*Node.ELEMENT_NODE*/; m = m.parentNode) {
1855                                                                 for (var k = 0; k < m.attributes.length; k++) {
1856                                                                         var attr = m.attributes.item(k);
1857                                                                         var nm = String(attr.name);
1858                                                                         if (nm == "xmlns") {
1859                                                                                 if (n[""] == undefined) {
1860                                                                                         n[""] = attr.value;
1861                                                                                 }
1862                                                                         } else if (nm.length > 6 && nm.substring(0, 6) == "xmlns:") {
1863                                                                                 var pre = nm.substring(6, nm.length);
1864                                                                                 if (n[pre] == undefined) {
1865                                                                                         n[pre] = attr.value;
1866                                                                                 }
1867                                                                         }
1868                                                                 }
1869                                                         }
1870                                                         for (var pre in n) {
1871                                                                 var nsn = new NamespaceNode(pre, n[pre], xpc.contextNode);
1872                                                                 if (step.nodeTest.matches(nsn, xpc)) {
1873                                                                         newNodes.push(nsn);
1874                                                                 }
1875                                                         }
1876                                                 }
1877                                                 break;
1878
1879                                         case Step.PARENT:
1880                                                 m = null;
1881                                                 if (xpc.contextNode !== xpc.virtualRoot) {
1882                                                         if (xpc.contextNode.nodeType == 2 /*Node.ATTRIBUTE_NODE*/) {
1883                                                                 m = this.getOwnerElement(xpc.contextNode);
1884                                                         } else {
1885                                                                 m = xpc.contextNode.parentNode;
1886                                                         }
1887                                                 }
1888                                                 if (m != null && step.nodeTest.matches(m, xpc)) {
1889                                                         newNodes.push(m);
1890                                                 }
1891                                                 break;
1892
1893                                         case Step.PRECEDING:
1894                                                 var st;
1895                                                 if (xpc.virtualRoot != null) {
1896                                                         st = [ xpc.virtualRoot ];
1897                                                 } else {
1898                                                         st = xpc.contextNode.nodeType == 9 /*Node.DOCUMENT_NODE*/
1899                                                                 ? [ xpc.contextNode ]
1900                                                                 : [ xpc.contextNode.ownerDocument ];
1901                                                 }
1902                                                 outer: while (st.length > 0) {
1903                                                         for (var m = st.pop(); m != null; ) {
1904                                                                 if (m == xpc.contextNode) {
1905                                                                         break outer;
1906                                                                 }
1907                                                                 if (step.nodeTest.matches(m, xpc)) {
1908                                                                         newNodes.unshift(m);
1909                                                                 }
1910                                                                 if (m.firstChild != null) {
1911                                                                         st.push(m.nextSibling);
1912                                                                         m = m.firstChild;
1913                                                                 } else {
1914                                                                         m = m.nextSibling;
1915                                                                 }
1916                                                         }
1917                                                 }
1918                                                 break;
1919
1920                                         case Step.PRECEDINGSIBLING:
1921                                                 if (xpc.contextNode === xpc.virtualRoot) {
1922                                                         break;
1923                                                 }
1924                                                 for (var m = xpc.contextNode.previousSibling; m != null; m = m.previousSibling) {
1925                                                         if (step.nodeTest.matches(m, xpc)) {
1926                                                                 newNodes.push(m);
1927                                                         }
1928                                                 }
1929                                                 break;
1930
1931                                         case Step.SELF:
1932                                                 if (step.nodeTest.matches(xpc.contextNode, xpc)) {
1933                                                         newNodes.push(xpc.contextNode);
1934                                                 }
1935                                                 break;
1936
1937                                         default:
1938                                 }
1939                         }
1940                         nodes = newNodes;
1941                         // apply each of the predicates in turn
1942                         for (var j = 0; j < step.predicates.length; j++) {
1943                                 var pred = step.predicates[j];
1944                                 var newNodes = [];
1945                                 xpc.contextSize = nodes.length;
1946                                 for (xpc.contextPosition = 1; xpc.contextPosition <= xpc.contextSize; xpc.contextPosition++) {
1947                                         xpc.contextNode = nodes[xpc.contextPosition - 1];
1948                                         if (this.predicateMatches(pred, xpc)) {
1949                                                 newNodes.push(xpc.contextNode);
1950                                         } else {
1951                                         }
1952                                 }
1953                                 nodes = newNodes;
1954                         }
1955                 }
1956         }
1957         var ns = new XNodeSet();
1958         ns.addArray(nodes);
1959         return ns;
1960 };
1961
1962 PathExpr.prototype.predicateMatches = function(pred, c) {
1963         var res = pred.evaluate(c);
1964         if (Utilities.instance_of(res, XNumber)) {
1965                 return c.contextPosition == res.numberValue();
1966         }
1967         return res.booleanValue();
1968 };
1969
1970 PathExpr.prototype.toString = function() {
1971         if (this.filter != undefined) {
1972                 var s = this.filter.toString();
1973                 if (Utilities.instance_of(this.filter, XString)) {
1974                         s = "'" + s + "'";
1975                 }
1976                 if (this.filterPredicates != undefined) {
1977                         for (var i = 0; i < this.filterPredicates.length; i++) {
1978                                 s = s + "[" + this.filterPredicates[i].toString() + "]";
1979                         }
1980                 }
1981                 if (this.locationPath != undefined) {
1982                         if (!this.locationPath.absolute) {
1983                                 s += "/";
1984                         }
1985                         s += this.locationPath.toString();
1986                 }
1987                 return s;
1988         }
1989         return this.locationPath.toString();
1990 };
1991
1992 PathExpr.prototype.getOwnerElement = function(n) {
1993         // DOM 2 has ownerElement
1994         if (n.ownerElement) {
1995                 return n.ownerElement;
1996         }
1997         // DOM 1 Internet Explorer can use selectSingleNode (ironically)
1998         try {
1999                 if (n.selectSingleNode) {
2000                         return n.selectSingleNode("..");
2001                 }
2002         } catch (e) {
2003         }
2004         // Other DOM 1 implementations must use this egregious search
2005         var doc = n.nodeType == 9 /*Node.DOCUMENT_NODE*/
2006                         ? n
2007                         : n.ownerDocument;
2008         var elts = doc.getElementsByTagName("*");
2009         for (var i = 0; i < elts.length; i++) {
2010                 var elt = elts.item(i);
2011                 var nnm = elt.attributes;
2012                 for (var j = 0; j < nnm.length; j++) {
2013                         var an = nnm.item(j);
2014                         if (an === n) {
2015                                 return elt;
2016                         }
2017                 }
2018         }
2019         return null;
2020 };
2021
2022 // LocationPath //////////////////////////////////////////////////////////////
2023
2024 LocationPath.prototype = new Object();
2025 LocationPath.prototype.constructor = LocationPath;
2026 LocationPath.superclass = Object.prototype;
2027
2028 function LocationPath(abs, steps) {
2029         if (arguments.length > 0) {
2030                 this.init(abs, steps);
2031         }
2032 }
2033
2034 LocationPath.prototype.init = function(abs, steps) {
2035         this.absolute = abs;
2036         this.steps = steps;
2037 };
2038
2039 LocationPath.prototype.toString = function() {
2040         var s;
2041         if (this.absolute) {
2042                 s = "/";
2043         } else {
2044                 s = "";
2045         }
2046         for (var i = 0; i < this.steps.length; i++) {
2047                 if (i != 0) {
2048                         s += "/";
2049                 }
2050                 s += this.steps[i].toString();
2051         }
2052         return s;
2053 };
2054
2055 // Step //////////////////////////////////////////////////////////////////////
2056
2057 Step.prototype = new Object();
2058 Step.prototype.constructor = Step;
2059 Step.superclass = Object.prototype;
2060
2061 function Step(axis, nodetest, preds) {
2062         if (arguments.length > 0) {
2063                 this.init(axis, nodetest, preds);
2064         }
2065 }
2066
2067 Step.prototype.init = function(axis, nodetest, preds) {
2068         this.axis = axis;
2069         this.nodeTest = nodetest;
2070         this.predicates = preds;
2071 };
2072
2073 Step.prototype.toString = function() {
2074         var s;
2075         switch (this.axis) {
2076                 case Step.ANCESTOR:
2077                         s = "ancestor";
2078                         break;
2079                 case Step.ANCESTORORSELF:
2080                         s = "ancestor-or-self";
2081                         break;
2082                 case Step.ATTRIBUTE:
2083                         s = "attribute";
2084                         break;
2085                 case Step.CHILD:
2086                         s = "child";
2087                         break;
2088                 case Step.DESCENDANT:
2089                         s = "descendant";
2090                         break;
2091                 case Step.DESCENDANTORSELF:
2092                         s = "descendant-or-self";
2093                         break;
2094                 case Step.FOLLOWING:
2095                         s = "following";
2096                         break;
2097                 case Step.FOLLOWINGSIBLING:
2098                         s = "following-sibling";
2099                         break;
2100                 case Step.NAMESPACE:
2101                         s = "namespace";
2102                         break;
2103                 case Step.PARENT:
2104                         s = "parent";
2105                         break;
2106                 case Step.PRECEDING:
2107                         s = "preceding";
2108                         break;
2109                 case Step.PRECEDINGSIBLING:
2110                         s = "preceding-sibling";
2111                         break;
2112                 case Step.SELF:
2113                         s = "self";
2114                         break;
2115         }
2116         s += "::";
2117         s += this.nodeTest.toString();
2118         for (var i = 0; i < this.predicates.length; i++) {
2119                 s += "[" + this.predicates[i].toString() + "]";
2120         }
2121         return s;
2122 };
2123
2124 Step.ANCESTOR = 0;
2125 Step.ANCESTORORSELF = 1;
2126 Step.ATTRIBUTE = 2;
2127 Step.CHILD = 3;
2128 Step.DESCENDANT = 4;
2129 Step.DESCENDANTORSELF = 5;
2130 Step.FOLLOWING = 6;
2131 Step.FOLLOWINGSIBLING = 7;
2132 Step.NAMESPACE = 8;
2133 Step.PARENT = 9;
2134 Step.PRECEDING = 10;
2135 Step.PRECEDINGSIBLING = 11;
2136 Step.SELF = 12;
2137
2138 // NodeTest //////////////////////////////////////////////////////////////////
2139
2140 NodeTest.prototype = new Object();
2141 NodeTest.prototype.constructor = NodeTest;
2142 NodeTest.superclass = Object.prototype;
2143
2144 function NodeTest(type, value) {
2145         if (arguments.length > 0) {
2146                 this.init(type, value);
2147         }
2148 }
2149
2150 NodeTest.prototype.init = function(type, value) {
2151         this.type = type;
2152         this.value = value;
2153 };
2154
2155 NodeTest.prototype.toString = function() {
2156         switch (this.type) {
2157                 case NodeTest.NAMETESTANY:
2158                         return "*";
2159                 case NodeTest.NAMETESTPREFIXANY:
2160                         return this.value + ":*";
2161                 case NodeTest.NAMETESTRESOLVEDANY:
2162                         return "{" + this.value + "}*";
2163                 case NodeTest.NAMETESTQNAME:
2164                         return this.value;
2165                 case NodeTest.NAMETESTRESOLVEDNAME:
2166                         return "{" + this.namespaceURI + "}" + this.value;
2167                 case NodeTest.COMMENT:
2168                         return "comment()";
2169                 case NodeTest.TEXT:
2170                         return "text()";
2171                 case NodeTest.PI:
2172                         if (this.value != undefined) {
2173                                 return "processing-instruction(\"" + this.value + "\")";
2174                         }
2175                         return "processing-instruction()";
2176                 case NodeTest.NODE:
2177                         return "node()";
2178         }
2179         return "<unknown nodetest type>";
2180 };
2181
2182 NodeTest.prototype.matches = function(n, xpc) {
2183         switch (this.type) {
2184                 case NodeTest.NAMETESTANY:
2185                         if (n.nodeType == 2 /*Node.ATTRIBUTE_NODE*/
2186                                         || n.nodeType == 1 /*Node.ELEMENT_NODE*/
2187                                         || n.nodeType == XPathNamespace.XPATH_NAMESPACE_NODE) {
2188                                 return true;
2189                         }
2190                         return false;
2191                 case NodeTest.NAMETESTPREFIXANY:
2192                         if ((n.nodeType == 2 /*Node.ATTRIBUTE_NODE*/ || n.nodeType == 1 /*Node.ELEMENT_NODE*/)) {
2193                                 var ns = xpc.namespaceResolver.getNamespace(this.value, xpc.expressionContextNode);
2194                                 if (ns == null) {
2195                                         throw new Error("Cannot resolve QName " + this.value);
2196                                 }
2197                                 return true;
2198                         }
2199                         return false;
2200                 case NodeTest.NAMETESTQNAME:
2201                         if (n.nodeType == 2 /*Node.ATTRIBUTE_NODE*/
2202                                         || n.nodeType == 1 /*Node.ELEMENT_NODE*/
2203                                         || n.nodeType == XPathNamespace.XPATH_NAMESPACE_NODE) {
2204                                 var test = Utilities.resolveQName(this.value, xpc.namespaceResolver, xpc.expressionContextNode, false);
2205                                 if (test[0] == null) {
2206                                         throw new Error("Cannot resolve QName " + this.value);
2207                                 }
2208                                 test[0] = String(test[0]);
2209                                 test[1] = String(test[1]);
2210                                 if (test[0] == "") {
2211                                         test[0] = null;
2212                                 }
2213                                 var node = Utilities.resolveQName(n.nodeName, xpc.namespaceResolver, n, n.nodeType == 1 /*Node.ELEMENT_NODE*/);
2214                                 node[0] = String(node[0]);
2215                                 node[1] = String(node[1]);
2216                                 if (node[0] == "") {
2217                                         if (n.namespaceURI) {
2218                                                 node[0] = n.namespaceURI;
2219                                         } else {
2220                                                 node[0] = null;
2221                                         }
2222                                 }
2223                                 if (xpc.caseInsensitive) {
2224                                         return test[0] == node[0] && String(test[1]).toLowerCase() == String(node[1]).toLowerCase();
2225                                 }
2226                                 return test[0] == node[0] && test[1] == node[1];
2227                         }
2228                         return false;
2229                 case NodeTest.COMMENT:
2230                         return n.nodeType == 8 /*Node.COMMENT_NODE*/;
2231                 case NodeTest.TEXT:
2232                         return n.nodeType == 3 /*Node.TEXT_NODE*/ || n.nodeType == 4 /*Node.CDATA_SECTION_NODE*/;
2233                 case NodeTest.PI:
2234                         return n.nodeType == 7 /*Node.PROCESSING_INSTRUCTION_NODE*/
2235                                 && (this.value == null || n.nodeName == this.value);
2236                 case NodeTest.NODE:
2237                         return n.nodeType == 9 /*Node.DOCUMENT_NODE*/
2238                                 || n.nodeType == 1 /*Node.ELEMENT_NODE*/
2239                                 || n.nodeType == 2 /*Node.ATTRIBUTE_NODE*/
2240                                 || n.nodeType == 3 /*Node.TEXT_NODE*/
2241                                 || n.nodeType == 4 /*Node.CDATA_SECTION_NODE*/
2242                                 || n.nodeType == 8 /*Node.COMMENT_NODE*/
2243                                 || n.nodeType == 7 /*Node.PROCESSING_INSTRUCTION_NODE*/;
2244         }
2245         return false;
2246 };
2247
2248 NodeTest.NAMETESTANY = 0;
2249 NodeTest.NAMETESTPREFIXANY = 1;
2250 NodeTest.NAMETESTQNAME = 2;
2251 NodeTest.COMMENT = 3;
2252 NodeTest.TEXT = 4;
2253 NodeTest.PI = 5;
2254 NodeTest.NODE = 6;
2255
2256 // VariableReference /////////////////////////////////////////////////////////
2257
2258 VariableReference.prototype = new Expression();
2259 VariableReference.prototype.constructor = VariableReference;
2260 VariableReference.superclass = Expression.prototype;
2261
2262 function VariableReference(v) {
2263         if (arguments.length > 0) {
2264                 this.init(v);
2265         }
2266 }
2267
2268 VariableReference.prototype.init = function(v) {
2269         this.variable = v;
2270 };
2271
2272 VariableReference.prototype.toString = function() {
2273         return "$" + this.variable;
2274 };
2275
2276 VariableReference.prototype.evaluate = function(c) {
2277         return c.variableResolver.getVariable(this.variable, c);
2278 };
2279
2280 // FunctionCall //////////////////////////////////////////////////////////////
2281
2282 FunctionCall.prototype = new Expression();
2283 FunctionCall.prototype.constructor = FunctionCall;
2284 FunctionCall.superclass = Expression.prototype;
2285
2286 function FunctionCall(fn, args) {
2287         if (arguments.length > 0) {
2288                 this.init(fn, args);
2289         }
2290 }
2291
2292 FunctionCall.prototype.init = function(fn, args) {
2293         this.functionName = fn;
2294         this.arguments = args;
2295 };
2296
2297 FunctionCall.prototype.toString = function() {
2298         var s = this.functionName + "(";
2299         for (var i = 0; i < this.arguments.length; i++) {
2300                 if (i > 0) {
2301                         s += ", ";
2302                 }
2303                 s += this.arguments[i].toString();
2304         }
2305         return s + ")";
2306 };
2307
2308 FunctionCall.prototype.evaluate = function(c) {
2309         var f = c.functionResolver.getFunction(this.functionName, c);
2310         if (f == undefined) {
2311                 throw new Error("Unknown function " + this.functionName);
2312         }
2313         var a = [c].concat(this.arguments);
2314         return f.apply(c.functionResolver.thisArg, a);
2315 };
2316
2317 // XString ///////////////////////////////////////////////////////////////////
2318
2319 XString.prototype = new Expression();
2320 XString.prototype.constructor = XString;
2321 XString.superclass = Expression.prototype;
2322
2323 function XString(s) {
2324         if (arguments.length > 0) {
2325                 this.init(s);
2326         }
2327 }
2328
2329 XString.prototype.init = function(s) {
2330         this.str = s;
2331 };
2332
2333 XString.prototype.toString = function() {
2334         return this.str;
2335 };
2336
2337 XString.prototype.evaluate = function(c) {
2338         return this;
2339 };
2340
2341 XString.prototype.string = function() {
2342         return this;
2343 };
2344
2345 XString.prototype.number = function() {
2346         return new XNumber(this.str);
2347 };
2348
2349 XString.prototype.bool = function() {
2350         return new XBoolean(this.str);
2351 };
2352
2353 XString.prototype.nodeset = function() {
2354         throw new Error("Cannot convert string to nodeset");
2355 };
2356
2357 XString.prototype.stringValue = function() {
2358         return this.str;
2359 };
2360
2361 XString.prototype.numberValue = function() {
2362         return this.number().numberValue();
2363 };
2364
2365 XString.prototype.booleanValue = function() {
2366         return this.bool().booleanValue();
2367 };
2368
2369 XString.prototype.equals = function(r) {
2370         if (Utilities.instance_of(r, XBoolean)) {
2371                 return this.bool().equals(r);
2372         }
2373         if (Utilities.instance_of(r, XNumber)) {
2374                 return this.number().equals(r);
2375         }
2376         if (Utilities.instance_of(r, XNodeSet)) {
2377                 return r.compareWithString(this, Operators.equals);
2378         }
2379         return new XBoolean(this.str == r.str);
2380 };
2381
2382 XString.prototype.notequal = function(r) {
2383         if (Utilities.instance_of(r, XBoolean)) {
2384                 return this.bool().notequal(r);
2385         }
2386         if (Utilities.instance_of(r, XNumber)) {
2387                 return this.number().notequal(r);
2388         }
2389         if (Utilities.instance_of(r, XNodeSet)) {
2390                 return r.compareWithString(this, Operators.notequal);
2391         }
2392         return new XBoolean(this.str != r.str);
2393 };
2394
2395 XString.prototype.lessthan = function(r) {
2396         if (Utilities.instance_of(r, XNodeSet)) {
2397                 return r.compareWithNumber(this.number(), Operators.greaterthanorequal);
2398         }
2399         return this.number().lessthan(r.number());
2400 };
2401
2402 XString.prototype.greaterthan = function(r) {
2403         if (Utilities.instance_of(r, XNodeSet)) {
2404                 return r.compareWithNumber(this.number(), Operators.lessthanorequal);
2405         }
2406         return this.number().greaterthan(r.number());
2407 };
2408
2409 XString.prototype.lessthanorequal = function(r) {
2410         if (Utilities.instance_of(r, XNodeSet)) {
2411                 return r.compareWithNumber(this.number(), Operators.greaterthan);
2412         }
2413         return this.number().lessthanorequal(r.number());
2414 };
2415
2416 XString.prototype.greaterthanorequal = function(r) {
2417         if (Utilities.instance_of(r, XNodeSet)) {
2418                 return r.compareWithNumber(this.number(), Operators.lessthan);
2419         }
2420         return this.number().greaterthanorequal(r.number());
2421 };
2422
2423 // XNumber ///////////////////////////////////////////////////////////////////
2424
2425 XNumber.prototype = new Expression();
2426 XNumber.prototype.constructor = XNumber;
2427 XNumber.superclass = Expression.prototype;
2428
2429 function XNumber(n) {
2430         if (arguments.length > 0) {
2431                 this.init(n);
2432         }
2433 }
2434
2435 XNumber.prototype.init = function(n) {
2436         this.num = Number(n);
2437 };
2438
2439 XNumber.prototype.toString = function() {
2440         return this.num;
2441 };
2442
2443 XNumber.prototype.evaluate = function(c) {
2444         return this;
2445 };
2446
2447 XNumber.prototype.string = function() {
2448         return new XString(this.num);
2449 };
2450
2451 XNumber.prototype.number = function() {
2452         return this;
2453 };
2454
2455 XNumber.prototype.bool = function() {
2456         return new XBoolean(this.num);
2457 };
2458
2459 XNumber.prototype.nodeset = function() {
2460         throw new Error("Cannot convert number to nodeset");
2461 };
2462
2463 XNumber.prototype.stringValue = function() {
2464         return this.string().stringValue();
2465 };
2466
2467 XNumber.prototype.numberValue = function() {
2468         return this.num;
2469 };
2470
2471 XNumber.prototype.booleanValue = function() {
2472         return this.bool().booleanValue();
2473 };
2474
2475 XNumber.prototype.negate = function() {
2476         return new XNumber(-this.num);
2477 };
2478
2479 XNumber.prototype.equals = function(r) {
2480         if (Utilities.instance_of(r, XBoolean)) {
2481                 return this.bool().equals(r);
2482         }
2483         if (Utilities.instance_of(r, XString)) {
2484                 return this.equals(r.number());
2485         }
2486         if (Utilities.instance_of(r, XNodeSet)) {
2487                 return r.compareWithNumber(this, Operators.equals);
2488         }
2489         return new XBoolean(this.num == r.num);
2490 };
2491
2492 XNumber.prototype.notequal = function(r) {
2493         if (Utilities.instance_of(r, XBoolean)) {
2494                 return this.bool().notequal(r);
2495         }
2496         if (Utilities.instance_of(r, XString)) {
2497                 return this.notequal(r.number());
2498         }
2499         if (Utilities.instance_of(r, XNodeSet)) {
2500                 return r.compareWithNumber(this, Operators.notequal);
2501         }
2502         return new XBoolean(this.num != r.num);
2503 };
2504
2505 XNumber.prototype.lessthan = function(r) {
2506         if (Utilities.instance_of(r, XNodeSet)) {
2507                 return r.compareWithNumber(this, Operators.greaterthanorequal);
2508         }
2509         if (Utilities.instance_of(r, XBoolean) || Utilities.instance_of(r, XString)) {
2510                 return this.lessthan(r.number());
2511         }
2512         return new XBoolean(this.num < r.num);
2513 };
2514
2515 XNumber.prototype.greaterthan = function(r) {
2516         if (Utilities.instance_of(r, XNodeSet)) {
2517                 return r.compareWithNumber(this, Operators.lessthanorequal);
2518         }
2519         if (Utilities.instance_of(r, XBoolean) || Utilities.instance_of(r, XString)) {
2520                 return this.greaterthan(r.number());
2521         }
2522         return new XBoolean(this.num > r.num);
2523 };
2524
2525 XNumber.prototype.lessthanorequal = function(r) {
2526         if (Utilities.instance_of(r, XNodeSet)) {
2527                 return r.compareWithNumber(this, Operators.greaterthan);
2528         }
2529         if (Utilities.instance_of(r, XBoolean) || Utilities.instance_of(r, XString)) {
2530                 return this.lessthanorequal(r.number());
2531         }
2532         return new XBoolean(this.num <= r.num);
2533 };
2534
2535 XNumber.prototype.greaterthanorequal = function(r) {
2536         if (Utilities.instance_of(r, XNodeSet)) {
2537                 return r.compareWithNumber(this, Operators.lessthan);
2538         }
2539         if (Utilities.instance_of(r, XBoolean) || Utilities.instance_of(r, XString)) {
2540                 return this.greaterthanorequal(r.number());
2541         }
2542         return new XBoolean(this.num >= r.num);
2543 };
2544
2545 XNumber.prototype.plus = function(r) {
2546         return new XNumber(this.num + r.num);
2547 };
2548
2549 XNumber.prototype.minus = function(r) {
2550         return new XNumber(this.num - r.num);
2551 };
2552
2553 XNumber.prototype.multiply = function(r) {
2554         return new XNumber(this.num * r.num);
2555 };
2556
2557 XNumber.prototype.div = function(r) {
2558         return new XNumber(this.num / r.num);
2559 };
2560
2561 XNumber.prototype.mod = function(r) {
2562         return new XNumber(this.num % r.num);
2563 };
2564
2565 // XBoolean //////////////////////////////////////////////////////////////////
2566
2567 XBoolean.prototype = new Expression();
2568 XBoolean.prototype.constructor = XBoolean;
2569 XBoolean.superclass = Expression.prototype;
2570
2571 function XBoolean(b) {
2572         if (arguments.length > 0) {
2573                 this.init(b);
2574         }
2575 }
2576
2577 XBoolean.prototype.init = function(b) {
2578         this.b = Boolean(b);
2579 };
2580
2581 XBoolean.prototype.toString = function() {
2582         return this.b.toString();
2583 };
2584
2585 XBoolean.prototype.evaluate = function(c) {
2586         return this;
2587 };
2588
2589 XBoolean.prototype.string = function() {
2590         return new XString(this.b);
2591 };
2592
2593 XBoolean.prototype.number = function() {
2594         return new XNumber(this.b);
2595 };
2596
2597 XBoolean.prototype.bool = function() {
2598         return this;
2599 };
2600
2601 XBoolean.prototype.nodeset = function() {
2602         throw new Error("Cannot convert boolean to nodeset");
2603 };
2604
2605 XBoolean.prototype.stringValue = function() {
2606         return this.string().stringValue();
2607 };
2608
2609 XBoolean.prototype.numberValue = function() {
2610         return this.num().numberValue();
2611 };
2612
2613 XBoolean.prototype.booleanValue = function() {
2614         return this.b;
2615 };
2616
2617 XBoolean.prototype.not = function() {
2618         return new XBoolean(!this.b);
2619 };
2620
2621 XBoolean.prototype.equals = function(r) {
2622         if (Utilities.instance_of(r, XString) || Utilities.instance_of(r, XNumber)) {
2623                 return this.equals(r.bool());
2624         }
2625         if (Utilities.instance_of(r, XNodeSet)) {
2626                 return r.compareWithBoolean(this, Operators.equals);
2627         }
2628         return new XBoolean(this.b == r.b);
2629 };
2630
2631 XBoolean.prototype.notequal = function(r) {
2632         if (Utilities.instance_of(r, XString) || Utilities.instance_of(r, XNumber)) {
2633                 return this.notequal(r.bool());
2634         }
2635         if (Utilities.instance_of(r, XNodeSet)) {
2636                 return r.compareWithBoolean(this, Operators.notequal);
2637         }
2638         return new XBoolean(this.b != r.b);
2639 };
2640
2641 XBoolean.prototype.lessthan = function(r) {
2642         if (Utilities.instance_of(r, XNodeSet)) {
2643                 return r.compareWithNumber(this.number(), Operators.greaterthanorequal);
2644         }
2645         return this.number().lessthan(r.number());
2646 };
2647
2648 XBoolean.prototype.greaterthan = function(r) {
2649         if (Utilities.instance_of(r, XNodeSet)) {
2650                 return r.compareWithNumber(this.number(), Operators.lessthanorequal);
2651         }
2652         return this.number().greaterthan(r.number());
2653 };
2654
2655 XBoolean.prototype.lessthanorequal = function(r) {
2656         if (Utilities.instance_of(r, XNodeSet)) {
2657                 return r.compareWithNumber(this.number(), Operators.greaterthan);
2658         }
2659         return this.number().lessthanorequal(r.number());
2660 };
2661
2662 XBoolean.prototype.greaterthanorequal = function(r) {
2663         if (Utilities.instance_of(r, XNodeSet)) {
2664                 return r.compareWithNumber(this.number(), Operators.lessthan);
2665         }
2666         return this.number().greaterthanorequal(r.number());
2667 };
2668
2669 // AVLTree ///////////////////////////////////////////////////////////////////
2670
2671 AVLTree.prototype = new Object();
2672 AVLTree.prototype.constructor = AVLTree;
2673 AVLTree.superclass = Object.prototype;
2674
2675 function AVLTree(n) {
2676         this.init(n);
2677 }
2678
2679 AVLTree.prototype.init = function(n) {
2680         this.left = null;
2681     this.right = null;
2682         this.node = n;
2683         this.depth = 1;
2684 };
2685
2686 AVLTree.prototype.balance = function() {
2687     var ldepth = this.left  == null ? 0 : this.left.depth;
2688     var rdepth = this.right == null ? 0 : this.right.depth;
2689
2690         if (ldepth > rdepth + 1) {
2691         // LR or LL rotation
2692         var lldepth = this.left.left  == null ? 0 : this.left.left.depth;
2693         var lrdepth = this.left.right == null ? 0 : this.left.right.depth;
2694
2695         if (lldepth < lrdepth) {
2696             // LR rotation consists of a RR rotation of the left child
2697             this.left.rotateRR();
2698             // plus a LL rotation of this node, which happens anyway
2699         }
2700         this.rotateLL();
2701     } else if (ldepth + 1 < rdepth) {
2702         // RR or RL rorarion
2703                 var rrdepth = this.right.right == null ? 0 : this.right.right.depth;
2704                 var rldepth = this.right.left  == null ? 0 : this.right.left.depth;
2705
2706         if (rldepth > rrdepth) {
2707             // RR rotation consists of a LL rotation of the right child
2708             this.right.rotateLL();
2709             // plus a RR rotation of this node, which happens anyway
2710         }
2711         this.rotateRR();
2712     }
2713 };
2714
2715 AVLTree.prototype.rotateLL = function() {
2716     // the left side is too long => rotate from the left (_not_ leftwards)
2717     var nodeBefore = this.node;
2718     var rightBefore = this.right;
2719     this.node = this.left.node;
2720     this.right = this.left;
2721     this.left = this.left.left;
2722     this.right.left = this.right.right;
2723     this.right.right = rightBefore;
2724     this.right.node = nodeBefore;
2725     this.right.updateInNewLocation();
2726     this.updateInNewLocation();
2727 };
2728
2729 AVLTree.prototype.rotateRR = function() {
2730     // the right side is too long => rotate from the right (_not_ rightwards)
2731     var nodeBefore = this.node;
2732     var leftBefore = this.left;
2733     this.node = this.right.node;
2734     this.left = this.right;
2735     this.right = this.right.right;
2736     this.left.right = this.left.left;
2737     this.left.left = leftBefore;
2738     this.left.node = nodeBefore;
2739     this.left.updateInNewLocation();
2740     this.updateInNewLocation();
2741 };
2742
2743 AVLTree.prototype.updateInNewLocation = function() {
2744     this.getDepthFromChildren();
2745 };
2746
2747 AVLTree.prototype.getDepthFromChildren = function() {
2748     this.depth = this.node == null ? 0 : 1;
2749     if (this.left != null) {
2750         this.depth = this.left.depth + 1;
2751     }
2752     if (this.right != null && this.depth <= this.right.depth) {
2753         this.depth = this.right.depth + 1;
2754     }
2755 };
2756
2757 AVLTree.prototype.order = function(n1, n2) {
2758         if (n1 === n2) {
2759                 return 0;
2760         }
2761         var d1 = 0;
2762         var d2 = 0;
2763         for (var m1 = n1; m1 != null; m1 = m1.parentNode) {
2764                 d1++;
2765         }
2766         for (var m2 = n2; m2 != null; m2 = m2.parentNode) {
2767                 d2++;
2768         }
2769         if (d1 > d2) {
2770                 while (d1 > d2) {
2771                         n1 = n1.parentNode;
2772                         d1--;
2773                 }
2774                 if (n1 == n2) {
2775                         return 1;
2776                 }
2777         } else if (d2 > d1) {
2778                 while (d2 > d1) {
2779                         n2 = n2.parentNode;
2780                         d2--;
2781                 }
2782                 if (n1 == n2) {
2783                         return -1;
2784                 }
2785         }
2786         while (n1.parentNode != n2.parentNode) {
2787                 n1 = n1.parentNode;
2788                 n2 = n2.parentNode;
2789         }
2790         while (n1.previousSibling != null && n2.previousSibling != null) {
2791                 n1 = n1.previousSibling;
2792                 n2 = n2.previousSibling;
2793         }
2794         if (n1.previousSibling == null) {
2795                 return -1;
2796         }
2797         return 1;
2798 };
2799
2800 AVLTree.prototype.add = function(n)  {
2801         if (n === this.node) {
2802         return false;
2803     }
2804
2805         var o = this.order(n, this.node);
2806
2807     var ret = false;
2808     if (o == -1) {
2809         if (this.left == null) {
2810             this.left = new AVLTree(n);
2811             ret = true;
2812         } else {
2813             ret = this.left.add(n);
2814             if (ret) {
2815                 this.balance();
2816             }
2817         }
2818     } else if (o == 1) {
2819         if (this.right == null) {
2820             this.right = new AVLTree(n);
2821             ret = true;
2822         } else {
2823             ret = this.right.add(n);
2824             if (ret) {
2825                 this.balance();
2826             }
2827         }
2828     }
2829
2830     if (ret) {
2831         this.getDepthFromChildren();
2832     }
2833     return ret;
2834 };
2835
2836 // XNodeSet //////////////////////////////////////////////////////////////////
2837
2838 XNodeSet.prototype = new Expression();
2839 XNodeSet.prototype.constructor = XNodeSet;
2840 XNodeSet.superclass = Expression.prototype;
2841
2842 function XNodeSet() {
2843         this.init();
2844 }
2845
2846 XNodeSet.prototype.init = function() {
2847         this.tree = null;
2848         this.size = 0;
2849 };
2850
2851 XNodeSet.prototype.toString = function() {
2852         var p = this.first();
2853         if (p == null) {
2854                 return "";
2855         }
2856         return this.stringForNode(p);
2857 };
2858
2859 XNodeSet.prototype.evaluate = function(c) {
2860         return this;
2861 };
2862
2863 XNodeSet.prototype.string = function() {
2864         return new XString(this.toString());
2865 };
2866
2867 XNodeSet.prototype.stringValue = function() {
2868         return this.toString();
2869 };
2870
2871 XNodeSet.prototype.number = function() {
2872         return new XNumber(this.string());
2873 };
2874
2875 XNodeSet.prototype.numberValue = function() {
2876         return Number(this.string());
2877 };
2878
2879 XNodeSet.prototype.bool = function() {
2880         return new XBoolean(this.tree != null);
2881 };
2882
2883 XNodeSet.prototype.booleanValue = function() {
2884         return this.tree != null;
2885 };
2886
2887 XNodeSet.prototype.nodeset = function() {
2888         return this;
2889 };
2890
2891 XNodeSet.prototype.stringForNode = function(n) {
2892         if (n.nodeType == 9 /*Node.DOCUMENT_NODE*/) {
2893                 n = n.documentElement;
2894         }
2895         if (n.nodeType == 1 /*Node.ELEMENT_NODE*/) {
2896                 return this.stringForNodeRec(n);
2897         }
2898         if (n.isNamespaceNode) {
2899                 return n.namespace;
2900         }
2901         return n.nodeValue;
2902 };
2903
2904 XNodeSet.prototype.stringForNodeRec = function(n) {
2905         var s = "";
2906         for (var n2 = n.firstChild; n2 != null; n2 = n2.nextSibling) {
2907                 if (n2.nodeType == 3 /*Node.TEXT_NODE*/) {
2908                         s += n2.nodeValue;
2909                 } else if (n2.nodeType == 1 /*Node.ELEMENT_NODE*/) {
2910                         s += this.stringForNodeRec(n2);
2911                 }
2912         }
2913         return s;
2914 };
2915
2916 XNodeSet.prototype.first = function() {
2917         var p = this.tree;
2918         if (p == null) {
2919                 return null;
2920         }
2921         while (p.left != null) {
2922                 p = p.left;
2923         }
2924         return p.node;
2925 };
2926
2927 XNodeSet.prototype.add = function(n) {
2928     var added;
2929     if (this.tree == null) {
2930         this.tree = new AVLTree(n);
2931         added = true;
2932     } else {
2933         added = this.tree.add(n);
2934     }
2935     if (added) {
2936         this.size++;
2937     }
2938 };
2939
2940 XNodeSet.prototype.addArray = function(ns) {
2941         for (var i = 0; i < ns.length; i++) {
2942                 this.add(ns[i]);
2943         }
2944 };
2945
2946 XNodeSet.prototype.toArray = function() {
2947         var a = [];
2948         this.toArrayRec(this.tree, a);
2949         return a;
2950 };
2951
2952 XNodeSet.prototype.toArrayRec = function(t, a) {
2953         if (t != null) {
2954                 this.toArrayRec(t.left, a);
2955                 a.push(t.node);
2956                 this.toArrayRec(t.right, a);
2957         }
2958 };
2959
2960 XNodeSet.prototype.compareWithString = function(r, o) {
2961         var a = this.toArray();
2962         for (var i = 0; i < a.length; i++) {
2963                 var n = a[i];
2964                 var l = new XString(this.stringForNode(n));
2965                 var res = o(l, r);
2966                 if (res.booleanValue()) {
2967                         return res;
2968                 }
2969         }
2970         return new XBoolean(false);
2971 };
2972
2973 XNodeSet.prototype.compareWithNumber = function(r, o) {
2974         var a = this.toArray();
2975         for (var i = 0; i < a.length; i++) {
2976                 var n = a[i];
2977                 var l = new XNumber(this.stringForNode(n));
2978                 var res = o(l, r);
2979                 if (res.booleanValue()) {
2980                         return res;
2981                 }
2982         }
2983         return new XBoolean(false);
2984 };
2985
2986 XNodeSet.prototype.compareWithBoolean = function(r, o) {
2987         return o(this.bool(), r);
2988 };
2989
2990 XNodeSet.prototype.compareWithNodeSet = function(r, o) {
2991         var a = this.toArray();
2992         for (var i = 0; i < a.length; i++) {
2993                 var n = a[i];
2994                 var l = new XString(this.stringForNode(n));
2995                 var b = r.toArray();
2996                 for (var j = 0; j < b.length; j++) {
2997                         var n2 = b[j];
2998                         var r = new XString(this.stringForNode(n2));
2999                         var res = o(l, r);
3000                         if (res.booleanValue()) {
3001                                 return res;
3002                         }
3003                 }
3004         }
3005         return new XBoolean(false);
3006 };
3007
3008 XNodeSet.prototype.equals = function(r) {
3009         if (Utilities.instance_of(r, XString)) {
3010                 return this.compareWithString(r, Operators.equals);
3011         }
3012         if (Utilities.instance_of(r, XNumber)) {
3013                 return this.compareWithNumber(r, Operators.equals);
3014         }
3015         if (Utilities.instance_of(r, XBoolean)) {
3016                 return this.compareWithBoolean(r, Operators.equals);
3017         }
3018         return this.compareWithNodeSet(r, Operators.equals);
3019 };
3020
3021 XNodeSet.prototype.notequal = function(r) {
3022         if (Utilities.instance_of(r, XString)) {
3023                 return this.compareWithString(r, Operators.notequal);
3024         }
3025         if (Utilities.instance_of(r, XNumber)) {
3026                 return this.compareWithNumber(r, Operators.notequal);
3027         }
3028         if (Utilities.instance_of(r, XBoolean)) {
3029                 return this.compareWithBoolean(r, Operators.notequal);
3030         }
3031         return this.compareWithNodeSet(r, Operators.notequal);
3032 };
3033
3034 XNodeSet.prototype.lessthan = function(r) {
3035         if (Utilities.instance_of(r, XString)) {
3036                 return this.compareWithNumber(r.number(), Operators.lessthan);
3037         }
3038         if (Utilities.instance_of(r, XNumber)) {
3039                 return this.compareWithNumber(r, Operators.lessthan);
3040         }
3041         if (Utilities.instance_of(r, XBoolean)) {
3042                 return this.compareWithBoolean(r, Operators.lessthan);
3043         }
3044         return this.compareWithNodeSet(r, Operators.lessthan);
3045 };
3046
3047 XNodeSet.prototype.greaterthan = function(r) {
3048         if (Utilities.instance_of(r, XString)) {
3049                 return this.compareWithNumber(r.number(), Operators.greaterthan);
3050         }
3051         if (Utilities.instance_of(r, XNumber)) {
3052                 return this.compareWithNumber(r, Operators.greaterthan);
3053         }
3054         if (Utilities.instance_of(r, XBoolean)) {
3055                 return this.compareWithBoolean(r, Operators.greaterthan);
3056         }
3057         return this.compareWithNodeSet(r, Operators.greaterthan);
3058 };
3059
3060 XNodeSet.prototype.lessthanorequal = function(r) {
3061         if (Utilities.instance_of(r, XString)) {
3062                 return this.compareWithNumber(r.number(), Operators.lessthanorequal);
3063         }
3064         if (Utilities.instance_of(r, XNumber)) {
3065                 return this.compareWithNumber(r, Operators.lessthanorequal);
3066         }
3067         if (Utilities.instance_of(r, XBoolean)) {
3068                 return this.compareWithBoolean(r, Operators.lessthanorequal);
3069         }
3070         return this.compareWithNodeSet(r, Operators.lessthanorequal);
3071 };
3072
3073 XNodeSet.prototype.greaterthanorequal = function(r) {
3074         if (Utilities.instance_of(r, XString)) {
3075                 return this.compareWithNumber(r.number(), Operators.greaterthanorequal);
3076         }
3077         if (Utilities.instance_of(r, XNumber)) {
3078                 return this.compareWithNumber(r, Operators.greaterthanorequal);
3079         }
3080         if (Utilities.instance_of(r, XBoolean)) {
3081                 return this.compareWithBoolean(r, Operators.greaterthanorequal);
3082         }
3083         return this.compareWithNodeSet(r, Operators.greaterthanorequal);
3084 };
3085
3086 XNodeSet.prototype.union = function(r) {
3087         var ns = new XNodeSet();
3088         ns.tree = this.tree;
3089         ns.size = this.size;
3090         ns.addArray(r.toArray());
3091         return ns;
3092 };
3093
3094 // XPathNamespace ////////////////////////////////////////////////////////////
3095
3096 XPathNamespace.prototype = new Object();
3097 XPathNamespace.prototype.constructor = XPathNamespace;
3098 XPathNamespace.superclass = Object.prototype;
3099
3100 function XPathNamespace(pre, ns, p) {
3101         this.isXPathNamespace = true;
3102         this.ownerDocument = p.ownerDocument;
3103         this.nodeName = "#namespace";
3104         this.prefix = pre;
3105         this.localName = pre;
3106         this.namespaceURI = ns;
3107         this.nodeValue = ns;
3108         this.ownerElement = p;
3109         this.nodeType = XPathNamespace.XPATH_NAMESPACE_NODE;
3110 }
3111
3112 XPathNamespace.prototype.toString = function() {
3113         return "{ \"" + this.prefix + "\", \"" + this.namespaceURI + "\" }";
3114 };
3115
3116 // Operators /////////////////////////////////////////////////////////////////
3117
3118 var Operators = new Object();
3119
3120 Operators.equals = function(l, r) {
3121         return l.equals(r);
3122 };
3123
3124 Operators.notequal = function(l, r) {
3125         return l.notequal(r);
3126 };
3127
3128 Operators.lessthan = function(l, r) {
3129         return l.lessthan(r);
3130 };
3131
3132 Operators.greaterthan = function(l, r) {
3133         return l.greaterthan(r);
3134 };
3135
3136 Operators.lessthanorequal = function(l, r) {
3137         return l.lessthanorequal(r);
3138 };
3139
3140 Operators.greaterthanorequal = function(l, r) {
3141         return l.greaterthanorequal(r);
3142 };
3143
3144 // XPathContext //////////////////////////////////////////////////////////////
3145
3146 XPathContext.prototype = new Object();
3147 XPathContext.prototype.constructor = XPathContext;
3148 XPathContext.superclass = Object.prototype;
3149
3150 function XPathContext(vr, nr, fr) {
3151         this.variableResolver = vr != null ? vr : new VariableResolver();
3152         this.namespaceResolver = nr != null ? nr : new NamespaceResolver();
3153         this.functionResolver = fr != null ? fr : new FunctionResolver();
3154 }
3155
3156 // VariableResolver //////////////////////////////////////////////////////////
3157
3158 VariableResolver.prototype = new Object();
3159 VariableResolver.prototype.constructor = VariableResolver;
3160 VariableResolver.superclass = Object.prototype;
3161
3162 function VariableResolver() {
3163 }
3164
3165 VariableResolver.prototype.getVariable = function(vn, c) {
3166         var parts = Utilities.splitQName(vn);
3167         if (parts[0] != null) {
3168                 parts[0] = c.namespaceResolver.getNamespace(parts[0], c.expressionContextNode);
3169         if (parts[0] == null) {
3170             throw new Error("Cannot resolve QName " + fn);
3171         }
3172         }
3173         return this.getVariableWithName(parts[0], parts[1], c.expressionContextNode);
3174 };
3175
3176 VariableResolver.prototype.getVariableWithName = function(ns, ln, c) {
3177         return null;
3178 };
3179
3180 // FunctionResolver //////////////////////////////////////////////////////////
3181
3182 FunctionResolver.prototype = new Object();
3183 FunctionResolver.prototype.constructor = FunctionResolver;
3184 FunctionResolver.superclass = Object.prototype;
3185
3186 function FunctionResolver(thisArg) {
3187         this.thisArg = thisArg != null ? thisArg : Functions;
3188         this.functions = new Object();
3189         this.addStandardFunctions();
3190 }
3191
3192 FunctionResolver.prototype.addStandardFunctions = function() {
3193         this.functions["{}last"] = Functions.last;
3194         this.functions["{}position"] = Functions.position;
3195         this.functions["{}count"] = Functions.count;
3196         this.functions["{}id"] = Functions.id;
3197         this.functions["{}local-name"] = Functions.localName;
3198         this.functions["{}namespace-uri"] = Functions.namespaceURI;
3199         this.functions["{}name"] = Functions.name;
3200         this.functions["{}string"] = Functions.string;
3201         this.functions["{}concat"] = Functions.concat;
3202         this.functions["{}starts-with"] = Functions.startsWith;
3203         this.functions["{}contains"] = Functions.contains;
3204         this.functions["{}substring-before"] = Functions.substringBefore;
3205         this.functions["{}substring-after"] = Functions.substringAfter;
3206         this.functions["{}substring"] = Functions.substring;
3207         this.functions["{}string-length"] = Functions.stringLength;
3208         this.functions["{}normalize-space"] = Functions.normalizeSpace;
3209         this.functions["{}translate"] = Functions.translate;
3210         this.functions["{}boolean"] = Functions.boolean_;
3211         this.functions["{}not"] = Functions.not;
3212         this.functions["{}true"] = Functions.true_;
3213         this.functions["{}false"] = Functions.false_;
3214         this.functions["{}lang"] = Functions.lang;
3215         this.functions["{}number"] = Functions.number;
3216         this.functions["{}sum"] = Functions.sum;
3217         this.functions["{}floor"] = Functions.floor;
3218         this.functions["{}ceiling"] = Functions.ceiling;
3219         this.functions["{}round"] = Functions.round;
3220 };
3221
3222 FunctionResolver.prototype.addFunction = function(ns, ln, f) {
3223         this.functions["{" + ns + "}" + ln] = f;
3224 };
3225
3226 FunctionResolver.prototype.getFunction = function(fn, c) {
3227         var parts = Utilities.resolveQName(fn, c.namespaceResolver, c.contextNode, false);
3228     if (parts[0] == null) {
3229         throw new Error("Cannot resolve QName " + fn);
3230     }
3231         return this.getFunctionWithName(parts[0], parts[1], c.contextNode);
3232 };
3233
3234 FunctionResolver.prototype.getFunctionWithName = function(ns, ln, c) {
3235         return this.functions["{" + ns + "}" + ln];
3236 };
3237
3238 // NamespaceResolver /////////////////////////////////////////////////////////
3239
3240 NamespaceResolver.prototype = new Object();
3241 NamespaceResolver.prototype.constructor = NamespaceResolver;
3242 NamespaceResolver.superclass = Object.prototype;
3243
3244 function NamespaceResolver() {
3245 }
3246
3247 NamespaceResolver.prototype.getNamespace = function(prefix, n) {
3248         if (prefix == "xml") {
3249                 return XPath.XML_NAMESPACE_URI;
3250         } else if (prefix == "xmlns") {
3251                 return XPath.XMLNS_NAMESPACE_URI;
3252         }
3253         if (n.nodeType == 9 /*Node.DOCUMENT_NODE*/) {
3254                 n = n.documentElement;
3255         } else if (n.nodeType == 2 /*Node.ATTRIBUTE_NODE*/) {
3256                 n = PathExpr.prototype.getOwnerElement(n);
3257         } else if (n.nodeType != 1 /*Node.ELEMENT_NODE*/) {
3258                 n = n.parentNode;
3259         }
3260         while (n != null && n.nodeType == 1 /*Node.ELEMENT_NODE*/) {
3261                 var nnm = n.attributes;
3262                 for (var i = 0; i < nnm.length; i++) {
3263                         var a = nnm.item(i);
3264                         var aname = a.nodeName;
3265                         if (aname == "xmlns" && prefix == ""
3266                                         || aname == "xmlns:" + prefix) {
3267                                 return String(a.nodeValue);
3268                         }
3269                 }
3270                 n = n.parentNode;
3271         }
3272         return null;
3273 };
3274
3275 // Functions /////////////////////////////////////////////////////////////////
3276
3277 Functions = new Object();
3278
3279 Functions.last = function() {
3280         var c = arguments[0];
3281         if (arguments.length != 1) {
3282                 throw new Error("Function last expects ()");
3283         }
3284         return new XNumber(c.contextSize);
3285 };
3286
3287 Functions.position = function() {
3288         var c = arguments[0];
3289         if (arguments.length != 1) {
3290                 throw new Error("Function position expects ()");
3291         }
3292         return new XNumber(c.contextPosition);
3293 };
3294
3295 Functions.count = function() {
3296         var c = arguments[0];
3297         var ns;
3298         if (arguments.length != 2 || !Utilities.instance_of(ns = arguments[1].evaluate(c), XNodeSet)) {
3299                 throw new Error("Function count expects (node-set)");
3300         }
3301         return new XNumber(ns.size);
3302 };
3303
3304 Functions.id = function() {
3305         var c = arguments[0];
3306         var id;
3307         if (arguments.length != 2) {
3308                 throw new Error("Function id expects (object)");
3309         }
3310         id = arguments[1].evaluate(c);
3311         if (Utilities.instance_of(id, XNodeSet)) {
3312                 id = id.toArray().join(" ");
3313         } else {
3314                 id = id.stringValue();
3315         }
3316         var ids = id.split(/[\x0d\x0a\x09\x20]+/);
3317         var count = 0;
3318         var ns = new XNodeSet();
3319         var doc = c.contextNode.nodeType == 9 /*Node.DOCUMENT_NODE*/
3320                         ? c.contextNode
3321                         : c.contextNode.ownerDocument;
3322         for (var i = 0; i < ids.length; i++) {
3323                 var n;
3324                 if (doc.getElementById) {
3325                         n = doc.getElementById(ids[i]);
3326                 } else {
3327                         n = Utilities.getElementById(doc, ids[i]);
3328                 }
3329                 if (n != null) {
3330                         ns.add(n);
3331                         count++;
3332                 }
3333         }
3334         return ns;
3335 };
3336
3337 Functions.localName = function() {
3338         var c = arguments[0];
3339         var n;
3340         if (arguments.length == 1) {
3341                 n = c.contextNode;
3342         } else if (arguments.length == 2) {
3343                 n = arguments[1].evaluate(c).first();
3344         } else {
3345                 throw new Error("Function local-name expects (node-set?)");
3346         }
3347         if (n == null) {
3348                 return new XString("");
3349         }
3350         return new XString(n.localName ? n.localName : n.baseName);
3351 };
3352
3353 Functions.namespaceURI = function() {
3354         var c = arguments[0];
3355         var n;
3356         if (arguments.length == 1) {
3357                 n = c.contextNode;
3358         } else if (arguments.length == 2) {
3359                 n = arguments[1].evaluate(c).first();
3360         } else {
3361                 throw new Error("Function namespace-uri expects (node-set?)");
3362         }
3363         if (n == null) {
3364                 return new XString("");
3365         }
3366         return new XString(n.namespaceURI);
3367 };
3368
3369 Functions.name = function() {
3370         var c = arguments[0];
3371         var n;
3372         if (arguments.length == 1) {
3373                 n = c.contextNode;
3374         } else if (arguments.length == 2) {
3375                 n = arguments[1].evaluate(c).first();
3376         } else {
3377                 throw new Error("Function name expects (node-set?)");
3378         }
3379         if (n == null) {
3380                 return new XString("");
3381         }
3382         if (n.nodeType == 1 /*Node.ELEMENT_NODE*/ || n.nodeType == 2 /*Node.ATTRIBUTE_NODE*/) {
3383                 return new XString(n.nodeName);
3384         } else if (n.localName == null) {
3385                 return new XString("");
3386         } else {
3387                 return new XString(n.localName);
3388         }
3389 };
3390
3391 Functions.string = function() {
3392         var c = arguments[0];
3393         if (arguments.length == 1) {
3394                 return XNodeSet.prototype.stringForNode(c.contextNode);
3395         } else if (arguments.length == 2) {
3396                 return arguments[1].evaluate(c).string();
3397         }
3398         throw new Error("Function string expects (object?)");
3399 };
3400
3401 Functions.concat = function() {
3402         var c = arguments[0];
3403         if (arguments.length < 3) {
3404                 throw new Error("Function concat expects (string, string, string*)");
3405         }
3406         var s = "";
3407         for (var i = 1; i < arguments.length; i++) {
3408                 s += arguments[i].evaluate(c).stringValue();
3409         }
3410         return new XString(s);
3411 };
3412
3413 Functions.startsWith = function() {
3414         var c = arguments[0];
3415         if (arguments.length != 3) {
3416                 throw new Error("Function startsWith expects (string, string)");
3417         }
3418         var s1 = arguments[1].evaluate(c).stringValue();
3419         var s2 = arguments[2].evaluate(c).stringValue();
3420         return new XBoolean(s1.substring(0, s2.length) == s2);
3421 };
3422
3423 Functions.contains = function() {
3424         var c = arguments[0];
3425         if (arguments.length != 3) {
3426                 throw new Error("Function contains expects (string, string)");
3427         }
3428         var s1 = arguments[1].evaluate(c).stringValue();
3429         var s2 = arguments[2].evaluate(c).stringValue();
3430         return new XBoolean(s1.indexOf(s2) != -1);
3431 };
3432
3433 Functions.substringBefore = function() {
3434         var c = arguments[0];
3435         if (arguments.length != 3) {
3436                 throw new Error("Function substring-before expects (string, string)");
3437         }
3438         var s1 = arguments[1].evaluate(c).stringValue();
3439         var s2 = arguments[2].evaluate(c).stringValue();
3440         return new XString(s1.substring(0, s1.indexOf(s2)));
3441 };
3442
3443 Functions.substringAfter = function() {
3444         var c = arguments[0];
3445         if (arguments.length != 3) {
3446                 throw new Error("Function substring-after expects (string, string)");
3447         }
3448         var s1 = arguments[1].evaluate(c).stringValue();
3449         var s2 = arguments[2].evaluate(c).stringValue();
3450         if (s2.length == 0) {
3451                 return new XString(s1);
3452         }
3453         var i = s1.indexOf(s2);
3454         if (i == -1) {
3455                 return new XString("");
3456         }
3457         return new XString(s1.substring(s1.indexOf(s2) + 1));
3458 };
3459
3460 Functions.substring = function() {
3461         var c = arguments[0];
3462         if (!(arguments.length == 3 || arguments.length == 4)) {
3463                 throw new Error("Function substring expects (string, number, number?)");
3464         }
3465         var s = arguments[1].evaluate(c).stringValue();
3466         var n1 = Math.round(arguments[2].evaluate(c).numberValue()) - 1;
3467         var n2 = arguments.length == 4 ? n1 + Math.round(arguments[3].evaluate(c).numberValue()) : undefined;
3468         return new XString(s.substring(n1, n2));
3469 };
3470
3471 Functions.stringLength = function() {
3472         var c = arguments[0];
3473         var s;
3474         if (arguments.length == 1) {
3475                 s = XNodeSet.prototype.stringForNode(c.contextNode);
3476         } else if (arguments.length == 2) {
3477                 s = arguments[1].evaluate(c).stringValue();
3478         } else {
3479                 throw new Error("Function string-length expects (string?)");
3480         }
3481         return new XNumber(s.length);
3482 };
3483
3484 Functions.normalizeSpace = function() {
3485         var c = arguments[0];
3486         var s;
3487         if (arguments.length == 1) {
3488                 s = XNodeSet.prototype.stringForNode(c.contextNode);
3489         } else if (arguments.length == 2) {
3490                 s = arguments[1].evaluate(c).stringValue();
3491         } else {
3492                 throw new Error("Function normalize-space expects (string?)");
3493         }
3494         var i = 0;
3495         var j = s.length - 1;
3496         while (Utilities.isSpace(s.charCodeAt(j))) {
3497                 j--;
3498         }
3499         var t = "";
3500         while (i <= j && Utilities.isSpace(s.charCodeAt(i))) {
3501                 i++;
3502         }
3503         while (i <= j) {
3504                 if (Utilities.isSpace(s.charCodeAt(i))) {
3505                         t += " ";
3506                         while (i <= j && Utilities.isSpace(s.charCodeAt(i))) {
3507                                 i++;
3508                         }
3509                 } else {
3510                         t += s.charAt(i);
3511                         i++;
3512                 }
3513         }
3514         return new XString(t);
3515 };
3516
3517 Functions.translate = function() {
3518         var c = arguments[0];
3519         if (arguments.length != 4) {
3520                 throw new Error("Function translate expects (string, string, string)");
3521         }
3522         var s1 = arguments[1].evaluate(c).stringValue();
3523         var s2 = arguments[2].evaluate(c).stringValue();
3524         var s3 = arguments[3].evaluate(c).stringValue();
3525         var map = [];
3526         for (var i = 0; i < s2.length; i++) {
3527                 var j = s2.charCodeAt(i);
3528                 if (map[j] == undefined) {
3529                         var k = i > s3.length ? "" : s3.charAt(i);
3530                         map[j] = k;
3531                 }
3532         }
3533         var t = "";
3534         for (var i = 0; i < s1.length; i++) {
3535                 var c = s1.charCodeAt(i);
3536                 var r = map[c];
3537                 if (r == undefined) {
3538                         t += s1.charAt(i);
3539                 } else {
3540                         t += r;
3541                 }
3542         }
3543         return new XString(t);
3544 };
3545
3546 Functions.boolean_ = function() {
3547         var c = arguments[0];
3548         if (arguments.length != 2) {
3549                 throw new Error("Function boolean expects (object)");
3550         }
3551         return arguments[1].evaluate(c).bool();
3552 };
3553
3554 Functions.not = function() {
3555         var c = arguments[0];
3556         if (arguments.length != 2) {
3557                 throw new Error("Function not expects (object)");
3558         }
3559         return arguments[1].evaluate(c).bool().not();
3560 };
3561
3562 Functions.true_ = function() {
3563         if (arguments.length != 1) {
3564                 throw new Error("Function true expects ()");
3565         }
3566         return new XBoolean(true);
3567 };
3568
3569 Functions.false_ = function() {
3570         if (arguments.length != 1) {
3571                 throw new Error("Function false expects ()");
3572         }
3573         return new XBoolean(false);
3574 };
3575
3576 Functions.lang = function() {
3577         var c = arguments[0];
3578         if (arguments.length != 2) {
3579                 throw new Error("Function lang expects (string)");
3580         }
3581         var lang;
3582         for (var n = c.contextNode; n != null && n.nodeType != 9 /*Node.DOCUMENT_NODE*/; n = n.parentNode) {
3583                 var a = n.getAttributeNS(XPath.XML_NAMESPACE_URI, "lang");
3584                 if (a != null) {
3585                         lang = String(a);
3586                         break;
3587                 }
3588         }
3589         if (lang == null) {
3590                 return new XBoolean(false);
3591         }
3592         var s = arguments[1].evaluate(c).stringValue();
3593         return new XBoolean(lang.substring(0, s.length) == s
3594                                 && (lang.length == s.length || lang.charAt(s.length) == '-'));
3595 };
3596
3597 Functions.number = function() {
3598         var c = arguments[0];
3599         if (!(arguments.length == 1 || arguments.length == 2)) {
3600                 throw new Error("Function number expects (object?)");
3601         }
3602         if (arguments.length == 1) {
3603                 return new XNumber(XNodeSet.prototype.stringForNode(c.contextNode));
3604         }
3605         return arguments[1].evaluate(c).number();
3606 };
3607
3608 Functions.sum = function() {
3609         var c = arguments[0];
3610         var ns;
3611         if (arguments.length != 2 || !Utilities.instance_of((ns = arguments[1].evaluate(c)), XNodeSet)) {
3612                 throw new Error("Function sum expects (node-set)");
3613         }
3614         ns = ns.toArray();
3615         var n = 0;
3616         for (var i = 0; i < ns.length; i++) {
3617                 n += new XNumber(XNodeSet.prototype.stringForNode(ns[i])).numberValue();
3618         }
3619         return new XNumber(n);
3620 };
3621
3622 Functions.floor = function() {
3623         var c = arguments[0];
3624         if (arguments.length != 2) {
3625                 throw new Error("Function floor expects (number)");
3626         }
3627         return new XNumber(Math.floor(arguments[1].evaluate(c).numberValue()));
3628 };
3629
3630 Functions.ceiling = function() {
3631         var c = arguments[0];
3632         if (arguments.length != 2) {
3633                 throw new Error("Function ceiling expects (number)");
3634         }
3635         return new XNumber(Math.ceil(arguments[1].evaluate(c).numberValue()));
3636 };
3637
3638 Functions.round = function() {
3639         var c = arguments[0];
3640         if (arguments.length != 2) {
3641                 throw new Error("Function round expects (number)");
3642         }
3643         return new XNumber(Math.round(arguments[1].evaluate(c).numberValue()));
3644 };
3645
3646 // Utilities /////////////////////////////////////////////////////////////////
3647
3648 Utilities = new Object();
3649
3650 Utilities.splitQName = function(qn) {
3651         var i = qn.indexOf(":");
3652         if (i == -1) {
3653                 return [ null, qn ];
3654         }
3655         return [ qn.substring(0, i), qn.substring(i + 1) ];
3656 };
3657
3658 Utilities.resolveQName = function(qn, nr, n, useDefault) {
3659         var parts = Utilities.splitQName(qn);
3660         if (parts[0] != null) {
3661                 parts[0] = nr.getNamespace(parts[0], n);
3662         } else {
3663                 if (useDefault) {
3664                         parts[0] = nr.getNamespace("", n);
3665                         if (parts[0] == null) {
3666                                 parts[0] = "";
3667                         }
3668                 } else {
3669                         parts[0] = "";
3670                 }
3671         }
3672         return parts;
3673 };
3674
3675 Utilities.isSpace = function(c) {
3676         return c == 0x9 || c == 0xd || c == 0xa || c == 0x20;
3677 };
3678
3679 Utilities.isLetter = function(c) {
3680         return c >= 0x0041 && c <= 0x005A ||
3681                 c >= 0x0061 && c <= 0x007A ||
3682                 c >= 0x00C0 && c <= 0x00D6 ||
3683                 c >= 0x00D8 && c <= 0x00F6 ||
3684                 c >= 0x00F8 && c <= 0x00FF ||
3685                 c >= 0x0100 && c <= 0x0131 ||
3686                 c >= 0x0134 && c <= 0x013E ||
3687                 c >= 0x0141 && c <= 0x0148 ||
3688                 c >= 0x014A && c <= 0x017E ||
3689                 c >= 0x0180 && c <= 0x01C3 ||
3690                 c >= 0x01CD && c <= 0x01F0 ||
3691                 c >= 0x01F4 && c <= 0x01F5 ||
3692                 c >= 0x01FA && c <= 0x0217 ||
3693                 c >= 0x0250 && c <= 0x02A8 ||
3694                 c >= 0x02BB && c <= 0x02C1 ||
3695                 c == 0x0386 ||
3696                 c >= 0x0388 && c <= 0x038A ||
3697                 c == 0x038C ||
3698                 c >= 0x038E && c <= 0x03A1 ||
3699                 c >= 0x03A3 && c <= 0x03CE ||
3700                 c >= 0x03D0 && c <= 0x03D6 ||
3701                 c == 0x03DA ||
3702                 c == 0x03DC ||
3703                 c == 0x03DE ||
3704                 c == 0x03E0 ||
3705                 c >= 0x03E2 && c <= 0x03F3 ||
3706                 c >= 0x0401 && c <= 0x040C ||
3707                 c >= 0x040E && c <= 0x044F ||
3708                 c >= 0x0451 && c <= 0x045C ||
3709                 c >= 0x045E && c <= 0x0481 ||
3710                 c >= 0x0490 && c <= 0x04C4 ||
3711                 c >= 0x04C7 && c <= 0x04C8 ||
3712                 c >= 0x04CB && c <= 0x04CC ||
3713                 c >= 0x04D0 && c <= 0x04EB ||
3714                 c >= 0x04EE && c <= 0x04F5 ||
3715                 c >= 0x04F8 && c <= 0x04F9 ||
3716                 c >= 0x0531 && c <= 0x0556 ||
3717                 c == 0x0559 ||
3718                 c >= 0x0561 && c <= 0x0586 ||
3719                 c >= 0x05D0 && c <= 0x05EA ||
3720                 c >= 0x05F0 && c <= 0x05F2 ||
3721                 c >= 0x0621 && c <= 0x063A ||
3722                 c >= 0x0641 && c <= 0x064A ||
3723                 c >= 0x0671 && c <= 0x06B7 ||
3724                 c >= 0x06BA && c <= 0x06BE ||
3725                 c >= 0x06C0 && c <= 0x06CE ||
3726                 c >= 0x06D0 && c <= 0x06D3 ||
3727                 c == 0x06D5 ||
3728                 c >= 0x06E5 && c <= 0x06E6 ||
3729                 c >= 0x0905 && c <= 0x0939 ||
3730                 c == 0x093D ||
3731                 c >= 0x0958 && c <= 0x0961 ||
3732                 c >= 0x0985 && c <= 0x098C ||
3733                 c >= 0x098F && c <= 0x0990 ||
3734                 c >= 0x0993 && c <= 0x09A8 ||
3735                 c >= 0x09AA && c <= 0x09B0 ||
3736                 c == 0x09B2 ||
3737                 c >= 0x09B6 && c <= 0x09B9 ||
3738                 c >= 0x09DC && c <= 0x09DD ||
3739                 c >= 0x09DF && c <= 0x09E1 ||
3740                 c >= 0x09F0 && c <= 0x09F1 ||
3741                 c >= 0x0A05 && c <= 0x0A0A ||
3742                 c >= 0x0A0F && c <= 0x0A10 ||
3743                 c >= 0x0A13 && c <= 0x0A28 ||
3744                 c >= 0x0A2A && c <= 0x0A30 ||
3745                 c >= 0x0A32 && c <= 0x0A33 ||
3746                 c >= 0x0A35 && c <= 0x0A36 ||
3747                 c >= 0x0A38 && c <= 0x0A39 ||
3748                 c >= 0x0A59 && c <= 0x0A5C ||
3749                 c == 0x0A5E ||
3750                 c >= 0x0A72 && c <= 0x0A74 ||
3751                 c >= 0x0A85 && c <= 0x0A8B ||
3752                 c == 0x0A8D ||
3753                 c >= 0x0A8F && c <= 0x0A91 ||
3754                 c >= 0x0A93 && c <= 0x0AA8 ||
3755                 c >= 0x0AAA && c <= 0x0AB0 ||
3756                 c >= 0x0AB2 && c <= 0x0AB3 ||
3757                 c >= 0x0AB5 && c <= 0x0AB9 ||
3758                 c == 0x0ABD ||
3759                 c == 0x0AE0 ||
3760                 c >= 0x0B05 && c <= 0x0B0C ||
3761                 c >= 0x0B0F && c <= 0x0B10 ||
3762                 c >= 0x0B13 && c <= 0x0B28 ||
3763                 c >= 0x0B2A && c <= 0x0B30 ||
3764                 c >= 0x0B32 && c <= 0x0B33 ||
3765                 c >= 0x0B36 && c <= 0x0B39 ||
3766                 c == 0x0B3D ||
3767                 c >= 0x0B5C && c <= 0x0B5D ||
3768                 c >= 0x0B5F && c <= 0x0B61 ||
3769                 c >= 0x0B85 && c <= 0x0B8A ||
3770                 c >= 0x0B8E && c <= 0x0B90 ||
3771                 c >= 0x0B92 && c <= 0x0B95 ||
3772                 c >= 0x0B99 && c <= 0x0B9A ||
3773                 c == 0x0B9C ||
3774                 c >= 0x0B9E && c <= 0x0B9F ||
3775                 c >= 0x0BA3 && c <= 0x0BA4 ||
3776                 c >= 0x0BA8 && c <= 0x0BAA ||
3777                 c >= 0x0BAE && c <= 0x0BB5 ||
3778                 c >= 0x0BB7 && c <= 0x0BB9 ||
3779                 c >= 0x0C05 && c <= 0x0C0C ||
3780                 c >= 0x0C0E && c <= 0x0C10 ||
3781                 c >= 0x0C12 && c <= 0x0C28 ||
3782                 c >= 0x0C2A && c <= 0x0C33 ||
3783                 c >= 0x0C35 && c <= 0x0C39 ||
3784                 c >= 0x0C60 && c <= 0x0C61 ||
3785                 c >= 0x0C85 && c <= 0x0C8C ||
3786                 c >= 0x0C8E && c <= 0x0C90 ||
3787                 c >= 0x0C92 && c <= 0x0CA8 ||
3788                 c >= 0x0CAA && c <= 0x0CB3 ||
3789                 c >= 0x0CB5 && c <= 0x0CB9 ||
3790                 c == 0x0CDE ||
3791                 c >= 0x0CE0 && c <= 0x0CE1 ||
3792                 c >= 0x0D05 && c <= 0x0D0C ||
3793                 c >= 0x0D0E && c <= 0x0D10 ||
3794                 c >= 0x0D12 && c <= 0x0D28 ||
3795                 c >= 0x0D2A && c <= 0x0D39 ||
3796                 c >= 0x0D60 && c <= 0x0D61 ||
3797                 c >= 0x0E01 && c <= 0x0E2E ||
3798                 c == 0x0E30 ||
3799                 c >= 0x0E32 && c <= 0x0E33 ||
3800                 c >= 0x0E40 && c <= 0x0E45 ||
3801                 c >= 0x0E81 && c <= 0x0E82 ||
3802                 c == 0x0E84 ||
3803                 c >= 0x0E87 && c <= 0x0E88 ||
3804                 c == 0x0E8A ||
3805                 c == 0x0E8D ||
3806                 c >= 0x0E94 && c <= 0x0E97 ||
3807                 c >= 0x0E99 && c <= 0x0E9F ||
3808                 c >= 0x0EA1 && c <= 0x0EA3 ||
3809                 c == 0x0EA5 ||
3810                 c == 0x0EA7 ||
3811                 c >= 0x0EAA && c <= 0x0EAB ||
3812                 c >= 0x0EAD && c <= 0x0EAE ||
3813                 c == 0x0EB0 ||
3814                 c >= 0x0EB2 && c <= 0x0EB3 ||
3815                 c == 0x0EBD ||
3816                 c >= 0x0EC0 && c <= 0x0EC4 ||
3817                 c >= 0x0F40 && c <= 0x0F47 ||
3818                 c >= 0x0F49 && c <= 0x0F69 ||
3819                 c >= 0x10A0 && c <= 0x10C5 ||
3820                 c >= 0x10D0 && c <= 0x10F6 ||
3821                 c == 0x1100 ||
3822                 c >= 0x1102 && c <= 0x1103 ||
3823                 c >= 0x1105 && c <= 0x1107 ||
3824                 c == 0x1109 ||
3825                 c >= 0x110B && c <= 0x110C ||
3826                 c >= 0x110E && c <= 0x1112 ||
3827                 c == 0x113C ||
3828                 c == 0x113E ||
3829                 c == 0x1140 ||
3830                 c == 0x114C ||
3831                 c == 0x114E ||
3832                 c == 0x1150 ||
3833                 c >= 0x1154 && c <= 0x1155 ||
3834                 c == 0x1159 ||
3835                 c >= 0x115F && c <= 0x1161 ||
3836                 c == 0x1163 ||
3837                 c == 0x1165 ||
3838                 c == 0x1167 ||
3839                 c == 0x1169 ||
3840                 c >= 0x116D && c <= 0x116E ||
3841                 c >= 0x1172 && c <= 0x1173 ||
3842                 c == 0x1175 ||
3843                 c == 0x119E ||
3844                 c == 0x11A8 ||
3845                 c == 0x11AB ||
3846                 c >= 0x11AE && c <= 0x11AF ||
3847                 c >= 0x11B7 && c <= 0x11B8 ||
3848                 c == 0x11BA ||
3849                 c >= 0x11BC && c <= 0x11C2 ||
3850                 c == 0x11EB ||
3851                 c == 0x11F0 ||
3852                 c == 0x11F9 ||
3853                 c >= 0x1E00 && c <= 0x1E9B ||
3854                 c >= 0x1EA0 && c <= 0x1EF9 ||
3855                 c >= 0x1F00 && c <= 0x1F15 ||
3856                 c >= 0x1F18 && c <= 0x1F1D ||
3857                 c >= 0x1F20 && c <= 0x1F45 ||
3858                 c >= 0x1F48 && c <= 0x1F4D ||
3859                 c >= 0x1F50 && c <= 0x1F57 ||
3860                 c == 0x1F59 ||
3861                 c == 0x1F5B ||
3862                 c == 0x1F5D ||
3863                 c >= 0x1F5F && c <= 0x1F7D ||
3864                 c >= 0x1F80 && c <= 0x1FB4 ||
3865                 c >= 0x1FB6 && c <= 0x1FBC ||
3866                 c == 0x1FBE ||
3867                 c >= 0x1FC2 && c <= 0x1FC4 ||
3868                 c >= 0x1FC6 && c <= 0x1FCC ||
3869                 c >= 0x1FD0 && c <= 0x1FD3 ||
3870                 c >= 0x1FD6 && c <= 0x1FDB ||
3871                 c >= 0x1FE0 && c <= 0x1FEC ||
3872                 c >= 0x1FF2 && c <= 0x1FF4 ||
3873                 c >= 0x1FF6 && c <= 0x1FFC ||
3874                 c == 0x2126 ||
3875                 c >= 0x212A && c <= 0x212B ||
3876                 c == 0x212E ||
3877                 c >= 0x2180 && c <= 0x2182 ||
3878                 c >= 0x3041 && c <= 0x3094 ||
3879                 c >= 0x30A1 && c <= 0x30FA ||
3880                 c >= 0x3105 && c <= 0x312C ||
3881                 c >= 0xAC00 && c <= 0xD7A3 ||
3882                 c >= 0x4E00 && c <= 0x9FA5 ||
3883                 c == 0x3007 ||
3884                 c >= 0x3021 && c <= 0x3029;
3885 };
3886
3887 Utilities.isNCNameChar = function(c) {
3888         return c >= 0x0030 && c <= 0x0039
3889                 || c >= 0x0660 && c <= 0x0669
3890                 || c >= 0x06F0 && c <= 0x06F9
3891                 || c >= 0x0966 && c <= 0x096F
3892                 || c >= 0x09E6 && c <= 0x09EF
3893                 || c >= 0x0A66 && c <= 0x0A6F
3894                 || c >= 0x0AE6 && c <= 0x0AEF
3895                 || c >= 0x0B66 && c <= 0x0B6F
3896                 || c >= 0x0BE7 && c <= 0x0BEF
3897                 || c >= 0x0C66 && c <= 0x0C6F
3898                 || c >= 0x0CE6 && c <= 0x0CEF
3899                 || c >= 0x0D66 && c <= 0x0D6F
3900                 || c >= 0x0E50 && c <= 0x0E59
3901                 || c >= 0x0ED0 && c <= 0x0ED9
3902                 || c >= 0x0F20 && c <= 0x0F29
3903                 || c == 0x002E
3904                 || c == 0x002D
3905                 || c == 0x005F
3906                 || Utilities.isLetter(c)
3907                 || c >= 0x0300 && c <= 0x0345
3908                 || c >= 0x0360 && c <= 0x0361
3909                 || c >= 0x0483 && c <= 0x0486
3910                 || c >= 0x0591 && c <= 0x05A1
3911                 || c >= 0x05A3 && c <= 0x05B9
3912                 || c >= 0x05BB && c <= 0x05BD
3913                 || c == 0x05BF
3914                 || c >= 0x05C1 && c <= 0x05C2
3915                 || c == 0x05C4
3916                 || c >= 0x064B && c <= 0x0652
3917                 || c == 0x0670
3918                 || c >= 0x06D6 && c <= 0x06DC
3919                 || c >= 0x06DD && c <= 0x06DF
3920                 || c >= 0x06E0 && c <= 0x06E4
3921                 || c >= 0x06E7 && c <= 0x06E8
3922                 || c >= 0x06EA && c <= 0x06ED
3923                 || c >= 0x0901 && c <= 0x0903
3924                 || c == 0x093C
3925                 || c >= 0x093E && c <= 0x094C
3926                 || c == 0x094D
3927                 || c >= 0x0951 && c <= 0x0954
3928                 || c >= 0x0962 && c <= 0x0963
3929                 || c >= 0x0981 && c <= 0x0983
3930                 || c == 0x09BC
3931                 || c == 0x09BE
3932                 || c == 0x09BF
3933                 || c >= 0x09C0 && c <= 0x09C4
3934                 || c >= 0x09C7 && c <= 0x09C8
3935                 || c >= 0x09CB && c <= 0x09CD
3936                 || c == 0x09D7
3937                 || c >= 0x09E2 && c <= 0x09E3
3938                 || c == 0x0A02
3939                 || c == 0x0A3C
3940                 || c == 0x0A3E
3941                 || c == 0x0A3F
3942                 || c >= 0x0A40 && c <= 0x0A42
3943                 || c >= 0x0A47 && c <= 0x0A48
3944                 || c >= 0x0A4B && c <= 0x0A4D
3945                 || c >= 0x0A70 && c <= 0x0A71
3946                 || c >= 0x0A81 && c <= 0x0A83
3947                 || c == 0x0ABC
3948                 || c >= 0x0ABE && c <= 0x0AC5
3949                 || c >= 0x0AC7 && c <= 0x0AC9
3950                 || c >= 0x0ACB && c <= 0x0ACD
3951                 || c >= 0x0B01 && c <= 0x0B03
3952                 || c == 0x0B3C
3953                 || c >= 0x0B3E && c <= 0x0B43
3954                 || c >= 0x0B47 && c <= 0x0B48
3955                 || c >= 0x0B4B && c <= 0x0B4D
3956                 || c >= 0x0B56 && c <= 0x0B57
3957                 || c >= 0x0B82 && c <= 0x0B83
3958                 || c >= 0x0BBE && c <= 0x0BC2
3959                 || c >= 0x0BC6 && c <= 0x0BC8
3960                 || c >= 0x0BCA && c <= 0x0BCD
3961                 || c == 0x0BD7
3962                 || c >= 0x0C01 && c <= 0x0C03
3963                 || c >= 0x0C3E && c <= 0x0C44
3964                 || c >= 0x0C46 && c <= 0x0C48
3965                 || c >= 0x0C4A && c <= 0x0C4D
3966                 || c >= 0x0C55 && c <= 0x0C56
3967                 || c >= 0x0C82 && c <= 0x0C83
3968                 || c >= 0x0CBE && c <= 0x0CC4
3969                 || c >= 0x0CC6 && c <= 0x0CC8
3970                 || c >= 0x0CCA && c <= 0x0CCD
3971                 || c >= 0x0CD5 && c <= 0x0CD6
3972                 || c >= 0x0D02 && c <= 0x0D03
3973                 || c >= 0x0D3E && c <= 0x0D43
3974                 || c >= 0x0D46 && c <= 0x0D48
3975                 || c >= 0x0D4A && c <= 0x0D4D
3976                 || c == 0x0D57
3977                 || c == 0x0E31
3978                 || c >= 0x0E34 && c <= 0x0E3A
3979                 || c >= 0x0E47 && c <= 0x0E4E
3980                 || c == 0x0EB1
3981                 || c >= 0x0EB4 && c <= 0x0EB9
3982                 || c >= 0x0EBB && c <= 0x0EBC
3983                 || c >= 0x0EC8 && c <= 0x0ECD
3984                 || c >= 0x0F18 && c <= 0x0F19
3985                 || c == 0x0F35
3986                 || c == 0x0F37
3987                 || c == 0x0F39
3988                 || c == 0x0F3E
3989                 || c == 0x0F3F
3990                 || c >= 0x0F71 && c <= 0x0F84
3991                 || c >= 0x0F86 && c <= 0x0F8B
3992                 || c >= 0x0F90 && c <= 0x0F95
3993                 || c == 0x0F97
3994                 || c >= 0x0F99 && c <= 0x0FAD
3995                 || c >= 0x0FB1 && c <= 0x0FB7
3996                 || c == 0x0FB9
3997                 || c >= 0x20D0 && c <= 0x20DC
3998                 || c == 0x20E1
3999                 || c >= 0x302A && c <= 0x302F
4000                 || c == 0x3099
4001                 || c == 0x309A
4002                 || c == 0x00B7
4003                 || c == 0x02D0
4004                 || c == 0x02D1
4005                 || c == 0x0387
4006                 || c == 0x0640
4007                 || c == 0x0E46
4008                 || c == 0x0EC6
4009                 || c == 0x3005
4010                 || c >= 0x3031 && c <= 0x3035
4011                 || c >= 0x309D && c <= 0x309E
4012                 || c >= 0x30FC && c <= 0x30FE;
4013 };
4014
4015 Utilities.coalesceText = function(n) {
4016         for (var m = n.firstChild; m != null; m = m.nextSibling) {
4017                 if (m.nodeType == 3 /*Node.TEXT_NODE*/ || m.nodeType == 4 /*Node.CDATA_SECTION_NODE*/) {
4018                         var s = m.nodeValue;
4019                         var first = m;
4020                         m = m.nextSibling;
4021                         while (m != null && (m.nodeType == 3 /*Node.TEXT_NODE*/ || m.nodeType == 4 /*Node.CDATA_SECTION_NODE*/)) {
4022                                 s += m.nodeValue;
4023                                 var del = m;
4024                                 m = m.nextSibling;
4025                                 del.parentNode.removeChild(del);
4026                         }
4027                         if (first.nodeType == 4 /*Node.CDATA_SECTION_NODE*/) {
4028                                 var p = first.parentNode;
4029                                 if (first.nextSibling == null) {
4030                                         p.removeChild(first);
4031                                         p.appendChild(p.ownerDocument.createTextNode(s));
4032                                 } else {
4033                                         var next = first.nextSibling;
4034                                         p.removeChild(first);
4035                                         p.insertBefore(p.ownerDocument.createTextNode(s), next);
4036                                 }
4037                         } else {
4038                                 first.nodeValue = s;
4039                         }
4040                         if (m == null) {
4041                                 break;
4042                         }
4043                 } else if (m.nodeType == 1 /*Node.ELEMENT_NODE*/) {
4044                         Utilities.coalesceText(m);
4045                 }
4046         }
4047 };
4048
4049 Utilities.instance_of = function(o, c) {
4050         while (o != null) {
4051                 if (o.constructor === c) {
4052                         return true;
4053                 }
4054                 if (o === Object) {
4055                         return false;
4056                 }
4057                 o = o.constructor.superclass;
4058         }
4059         return false;
4060 };
4061
4062 Utilities.getElementById = function(n, id) {
4063         // Note that this does not check the DTD to check for actual
4064         // attributes of type ID, so this may be a bit wrong.
4065         if (n.nodeType == 1 /*Node.ELEMENT_NODE*/) {
4066                 if (n.getAttribute("id") == id
4067                                 || n.getAttributeNS(null, "id") == id) {
4068                         return n;
4069                 }
4070         }
4071         for (var m = n.firstChild; m != null; m = m.nextSibling) {
4072                 var res = Utilities.getElementById(m, id);
4073                 if (res != null) {
4074                         return res;
4075                 }
4076         }
4077         return null;
4078 };
4079
4080 // XPathException ////////////////////////////////////////////////////////////
4081
4082 XPathException.prototype = {};
4083 XPathException.prototype.constructor = XPathException;
4084 XPathException.superclass = Object.prototype;
4085
4086 function XPathException(c, e) {
4087         this.code = c;
4088         this.exception = e;
4089 }
4090
4091 XPathException.prototype.toString = function() {
4092         var msg = this.exception ? ": " + this.exception.toString() : "";
4093         switch (this.code) {
4094                 case XPathException.INVALID_EXPRESSION_ERR:
4095                         return "Invalid expression" + msg;
4096                 case XPathException.TYPE_ERR:
4097                         return "Type error" + msg;
4098         }
4099 };
4100
4101 XPathException.INVALID_EXPRESSION_ERR = 51;
4102 XPathException.TYPE_ERR = 52;
4103
4104 // XPathExpression ///////////////////////////////////////////////////////////
4105
4106 XPathExpression.prototype = {};
4107 XPathExpression.prototype.constructor = XPathExpression;
4108 XPathExpression.superclass = Object.prototype;
4109
4110 function XPathExpression(e, r, p) {
4111         this.xpath = p.parse(e);
4112         this.context = new XPathContext();
4113         this.context.namespaceResolver = new XPathNSResolverWrapper(r);
4114 }
4115
4116 XPathExpression.prototype.evaluate = function(n, t, res) {
4117         this.context.expressionContextNode = n;
4118         var result = this.xpath.evaluate(this.context);
4119         return new XPathResult(result, t);
4120 }
4121
4122 // XPathNSResolverWrapper ////////////////////////////////////////////////////
4123
4124 XPathNSResolverWrapper.prototype = {};
4125 XPathNSResolverWrapper.prototype.constructor = XPathNSResolverWrapper;
4126 XPathNSResolverWrapper.superclass = Object.prototype;
4127
4128 function XPathNSResolverWrapper(r) {
4129         this.xpathNSResolver = r;
4130 }
4131
4132 XPathNSResolverWrapper.prototype.getNamespace = function(prefix, n) {
4133     if (this.xpathNSResolver == null) {
4134         return null;
4135     }
4136         return this.xpathNSResolver.lookupNamespaceURI(prefix);
4137 };
4138
4139 // NodeXPathNSResolver ///////////////////////////////////////////////////////
4140
4141 NodeXPathNSResolver.prototype = {};
4142 NodeXPathNSResolver.prototype.constructor = NodeXPathNSResolver;
4143 NodeXPathNSResolver.superclass = Object.prototype;
4144
4145 function NodeXPathNSResolver(n) {
4146         this.node = n;
4147         this.namespaceResolver = new NamespaceResolver();
4148 }
4149
4150 NodeXPathNSResolver.prototype.lookupNamespaceURI = function(prefix) {
4151         return this.namespaceResolver.getNamespace(prefix, this.node);
4152 };
4153
4154 // XPathResult ///////////////////////////////////////////////////////////////
4155
4156 XPathResult.prototype = {};
4157 XPathResult.prototype.constructor = XPathResult;
4158 XPathResult.superclass = Object.prototype;
4159
4160 function XPathResult(v, t) {
4161         if (t == XPathResult.ANY_TYPE) {
4162                 if (v.constructor === XString) {
4163                         t = XPathResult.STRING_TYPE;
4164                 } else if (v.constructor === XNumber) {
4165                         t = XPathResult.NUMBER_TYPE;
4166                 } else if (v.constructor === XBoolean) {
4167                         t = XPathResult.BOOLEAN_TYPE;
4168                 } else if (v.constructor === XNodeSet) {
4169                         t = XPathResult.UNORDERED_NODE_ITERATOR_TYPE;
4170                 }
4171         }
4172         this.resultType = t;
4173         switch (t) {
4174                 case XPathResult.NUMBER_TYPE:
4175                         this.numberValue = v.numberValue();
4176                         return;
4177                 case XPathResult.STRING_TYPE:
4178                         this.stringValue = v.stringValue();
4179                         return;
4180                 case XPathResult.BOOLEAN_TYPE:
4181                         this.booleanValue = v.booleanValue();
4182                         return;
4183                 case XPathResult.ANY_UNORDERED_NODE_TYPE:
4184                 case XPathResult.FIRST_UNORDERED_NODE_TYPE:
4185                         if (v.constructor === XNodeSet) {
4186                                 this.singleNodeValue = v.first();
4187                                 return;
4188                         }
4189                         break;
4190                 case XPathResult.UNORDERED_NODE_ITERATOR_TYPE:
4191                 case XPathResult.ORDERED_NODE_ITERATOR_TYPE:
4192                         if (v.constructor === XNodeSet) {
4193                                 this.invalidIteratorState = false;
4194                                 this.nodes = v.toArray();
4195                                 this.iteratorIndex = 0;
4196                                 return;
4197                         }
4198                         break;
4199                 case XPathResult.UNORDERED_NODE_SNAPSHOT_TYPE:
4200                 case XPathResult.ORDERED_NODE_SNAPSHOT_TYPE:
4201                         if (v.constructor === XNodeSet) {
4202                                 this.nodes = v.toArray();
4203                                 this.snapshotLength = this.nodes.length;
4204                                 return;
4205                         }
4206                         break;
4207         }
4208         throw new XPathException(XPathException.TYPE_ERR);
4209 };
4210
4211 XPathResult.prototype.iterateNext = function() {
4212         if (this.resultType != XPathResult.UNORDERED_NODE_ITERATOR_TYPE
4213                         && this.resultType != XPathResult.ORDERED_NODE_ITERATOR_TYPE) {
4214                 throw new XPathException(XPathException.TYPE_ERR);
4215         }
4216         return this.nodes[this.iteratorIndex++];
4217 };
4218
4219 XPathResult.prototype.snapshotItem = function(i) {
4220         if (this.resultType != XPathResult.UNORDERED_NODE_SNAPSHOT_TYPE
4221                         && this.resultType != XPathResult.ORDERED_NODE_SNAPSHOT_TYPE) {
4222                 throw new XPathException(XPathException.TYPE_ERR);
4223         }
4224         return this.nodes[i];
4225 };
4226
4227 XPathResult.ANY_TYPE = 0;
4228 XPathResult.NUMBER_TYPE = 1;
4229 XPathResult.STRING_TYPE = 2;
4230 XPathResult.BOOLEAN_TYPE = 3;
4231 XPathResult.UNORDERED_NODE_ITERATOR_TYPE = 4;
4232 XPathResult.ORDERED_NODE_ITERATOR_TYPE = 5;
4233 XPathResult.UNORDERED_NODE_SNAPSHOT_TYPE = 6;
4234 XPathResult.ORDERED_NODE_SNAPSHOT_TYPE = 7;
4235 XPathResult.ANY_UNORDERED_NODE_TYPE = 8;
4236 XPathResult.FIRST_ORDERED_NODE_TYPE = 9;
4237
4238 // DOM 3 XPath support ///////////////////////////////////////////////////////
4239
4240 function installDOM3XPathSupport(doc, p) {
4241         doc.createExpression = function(e, r) {
4242                 try {
4243                         return new XPathExpression(e, r, p);
4244                 } catch (e) {
4245                         throw new XPathException(XPathException.INVALID_EXPRESSION_ERR, e);
4246                 }
4247         };
4248         doc.createNSResolver = function(n) {
4249                 return new NodeXPathNSResolver(n);
4250         };
4251         doc.evaluate = function(e, cn, r, t, res) {
4252                 if (!cn) cn = doc;
4253                 if (t < 0 || t > 9) {
4254                         throw { code: 0, toString: function() { return "Request type not supported"; } };
4255                 }
4256                 return doc.createExpression(e, r, p).evaluate(cn, t, res);
4257         };
4258 };
4259
4260 // ---------------------------------------------------------------------------
4261
4262 // Install DOM 3 XPath support for the current document.
4263 try {
4264         var shouldInstall = true;
4265         try {
4266                 if (document.implementation
4267                                 && document.implementation.hasFeature
4268                                 && document.implementation.hasFeature("XPath", null)) {
4269                         shouldInstall = false;
4270                 }
4271         } catch (e) {
4272         }
4273         if (shouldInstall) {
4274                 installDOM3XPathSupport(document, new XPathParser());
4275         }
4276 } catch (e) {
4277 }