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