XML DOM, XPath and XMLHttpRequest support for O::U::SpiderMonkey
[Evergreen.git] / Open-ILS / src / javascript / backend / libs / xpath.js
1 /*
2  * xpath.js
3  *
4  * An XPath 1.0 library for JavaScript.
5  *
6  * Cameron McCormack <cam (at) mcc.id.au>
7  *
8  * This work is licensed under the Creative Commons Attribution-ShareAlike
9  * License. To view a copy of this license, visit
10  * 
11  *   http://creativecommons.org/licenses/by-sa/2.0/
12  *
13  * or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford,
14  * California 94305, USA.
15  *
16  * Revision 19: November 29, 2005
17  *   Nodesets now store their nodes in a height balanced tree, increasing
18  *   performance for the common case of selecting nodes in document order,
19  *   thanks to S├ębastien Cramatte <contact (at) zeninteractif.com>.
20  *   AVL tree code adapted from Raimund Neumann <rnova (at) gmx.net>.
21  *
22  * Revision 18: October 27, 2005
23  *   DOM 3 XPath support.  Caveats:
24  *     - namespace prefixes aren't resolved in XPathEvaluator.createExpression,
25  *       but in XPathExpression.evaluate.
26  *     - XPathResult.invalidIteratorState is not implemented.
27  *
28  * Revision 17: October 25, 2005
29  *   Some core XPath function fixes and a patch to avoid crashing certain
30  *   versions of MSXML in PathExpr.prototype.getOwnerElement, thanks to
31  *   S├ębastien Cramatte <contact (at) zeninteractif.com>.
32  *
33  * Revision 16: September 22, 2005
34  *   Workarounds for some IE 5.5 deficiencies.
35  *   Fixed problem with prefix node tests on attribute nodes.
36  *
37  * Revision 15: May 21, 2005
38  *   Fixed problem with QName node tests on elements with an xmlns="...".
39  *
40  * Revision 14: May 19, 2005
41  *   Fixed QName node tests on attribute node regression.
42  *
43  * Revision 13: May 3, 2005
44  *   Node tests are case insensitive now if working in an HTML DOM.
45  *
46  * Revision 12: April 26, 2005
47  *   Updated licence.  Slight code changes to enable use of Dean
48  *   Edwards' script compression, http://dean.edwards.name/packer/ .
49  *
50  * Revision 11: April 23, 2005
51  *   Fixed bug with 'and' and 'or' operators, fix thanks to
52  *   Sandy McArthur <sandy (at) mcarthur.org>.
53  *
54  * Revision 10: April 15, 2005
55  *   Added support for a virtual root node, supposedly helpful for
56  *   implementing XForms.  Fixed problem with QName node tests and
57  *   the parent axis.
58  *
59  * Revision 9: March 17, 2005
60  *   Namespace resolver tweaked so using the document node as the context
61  *   for namespace lookups is equivalent to using the document element.
62  *
63  * Revision 8: February 13, 2005
64  *   Handle implicit declaration of 'xmlns' namespace prefix.
65  *   Fixed bug when comparing nodesets.
66  *   Instance data can now be associated with a FunctionResolver, and
67  *     workaround for MSXML not supporting 'localName' and 'getElementById',
68  *     thanks to Grant Gongaware.
69  *   Fix a few problems when the context node is the root node.
70  *   
71  * Revision 7: February 11, 2005
72  *   Default namespace resolver fix from Grant Gongaware
73  *   <grant (at) gongaware.com>.
74  *
75  * Revision 6: February 10, 2005
76  *   Fixed bug in 'number' function.
77  *
78  * Revision 5: February 9, 2005
79  *   Fixed bug where text nodes not getting converted to string values.
80  *
81  * Revision 4: January 21, 2005
82  *   Bug in 'name' function, fix thanks to Bill Edney.
83  *   Fixed incorrect processing of namespace nodes.
84  *   Fixed NamespaceResolver to resolve 'xml' namespace.
85  *   Implemented union '|' operator.
86  *
87  * Revision 3: January 14, 2005
88  *   Fixed bug with nodeset comparisons, bug lexing < and >.
89  *
90  * Revision 2: October 26, 2004
91  *   QName node test namespace handling fixed.  Few other bug fixes.
92  *   
93  * Revision 1: August 13, 2004
94  *   Bug fixes from William J. Edney <bedney (at) technicalpursuit.com>.
95  *   Added minimal licence.
96  *
97  * Initial version: June 14, 2004
98  */
99
100 // XPathParser ///////////////////////////////////////////////////////////////
101
102 XPathParser.prototype = new Object();
103 XPathParser.prototype.constructor = XPathParser;
104 XPathParser.superclass = Object.prototype;
105
106 function XPathParser() {
107         this.init();
108 }
109
110 XPathParser.prototype.init = function() {
111         this.reduceActions = [];
112
113         this.reduceActions[3] = function(rhs) {
114                 return new OrOperation(rhs[0], rhs[2]);
115         };
116         this.reduceActions[5] = function(rhs) {
117                 return new AndOperation(rhs[0], rhs[2]);
118         };
119         this.reduceActions[7] = function(rhs) {
120                 return new EqualsOperation(rhs[0], rhs[2]);
121         };
122         this.reduceActions[8] = function(rhs) {
123                 return new NotEqualOperation(rhs[0], rhs[2]);
124         };
125         this.reduceActions[10] = function(rhs) {
126                 return new LessThanOperation(rhs[0], rhs[2]);
127         };
128         this.reduceActions[11] = function(rhs) {
129                 return new GreaterThanOperation(rhs[0], rhs[2]);
130         };
131         this.reduceActions[12] = function(rhs) {
132                 return new LessThanOrEqualOperation(rhs[0], rhs[2]);
133         };
134         this.reduceActions[13] = function(rhs) {
135                 return new GreaterThanOrEqualOperation(rhs[0], rhs[2]);
136         };
137         this.reduceActions[15] = function(rhs) {
138                 return new PlusOperation(rhs[0], rhs[2]);
139         };
140         this.reduceActions[16] = function(rhs) {
141                 return new MinusOperation(rhs[0], rhs[2]);
142         };
143         this.reduceActions[18] = function(rhs) {
144                 return new MultiplyOperation(rhs[0], rhs[2]);
145         };
146         this.reduceActions[19] = function(rhs) {
147                 return new DivOperation(rhs[0], rhs[2]);
148         };
149         this.reduceActions[20] = function(rhs) {
150                 return new ModOperation(rhs[0], rhs[2]);
151         };
152         this.reduceActions[22] = function(rhs) {
153                 return new UnaryMinusOperation(rhs[1]);
154         };
155         this.reduceActions[24] = function(rhs) {
156                 return new BarOperation(rhs[0], rhs[2]);
157         };
158         this.reduceActions[25] = function(rhs) {
159                 return new PathExpr(undefined, undefined, rhs[0]);
160         };
161         this.reduceActions[27] = function(rhs) {
162                 rhs[0].locationPath = rhs[2];
163                 return rhs[0];
164         };
165         this.reduceActions[28] = function(rhs) {
166                 rhs[0].locationPath = rhs[2];
167                 rhs[0].locationPath.steps.unshift(new Step(Step.DESCENDANTORSELF, new NodeTest(NodeTest.NODE, undefined), []));
168                 return rhs[0];
169         };
170         this.reduceActions[29] = function(rhs) {
171                 return new PathExpr(rhs[0], [], undefined);
172         };
173         this.reduceActions[30] = function(rhs) {
174                 if (Utilities.instance_of(rhs[0], PathExpr)) {
175                         if (rhs[0].filterPredicates == undefined) {
176                                 rhs[0].filterPredicates = [];
177                         }
178                         rhs[0].filterPredicates.push(rhs[1]);
179                         return rhs[0];
180                 } else {
181                         return new PathExpr(rhs[0], [rhs[1]], undefined);
182                 }
183         };
184         this.reduceActions[32] = function(rhs) {
185                 return rhs[1];
186         };
187         this.reduceActions[33] = function(rhs) {
188                 return new XString(rhs[0]);
189         };
190         this.reduceActions[34] = function(rhs) {
191                 return new XNumber(rhs[0]);
192         };
193         this.reduceActions[36] = function(rhs) {
194                 return new FunctionCall(rhs[0], []);
195         };
196         this.reduceActions[37] = function(rhs) {
197                 return new FunctionCall(rhs[0], rhs[2]);
198         };
199         this.reduceActions[38] = function(rhs) {
200                 return [ rhs[0] ];
201         };
202         this.reduceActions[39] = function(rhs) {
203                 rhs[2].unshift(rhs[0]);
204                 return rhs[2];
205         };
206         this.reduceActions[43] = function(rhs) {
207                 return new LocationPath(true, []);
208         };
209         this.reduceActions[44] = function(rhs) {
210                 rhs[1].absolute = true;
211                 return rhs[1];
212         };
213         this.reduceActions[46] = function(rhs) {
214                 return new LocationPath(false, [ rhs[0] ]);
215         };
216         this.reduceActions[47] = function(rhs) {
217                 rhs[0].steps.push(rhs[2]);
218                 return rhs[0];
219         };
220         this.reduceActions[49] = function(rhs) {
221                 return new Step(rhs[0], rhs[1], []);
222         };
223         this.reduceActions[50] = function(rhs) {
224                 return new Step(Step.CHILD, rhs[0], []);
225         };
226         this.reduceActions[51] = function(rhs) {
227                 return new Step(rhs[0], rhs[1], rhs[2]);
228         };
229         this.reduceActions[52] = function(rhs) {
230                 return new Step(Step.CHILD, rhs[0], rhs[1]);
231         };
232         this.reduceActions[54] = function(rhs) {
233                 return [ rhs[0] ];
234         };
235         this.reduceActions[55] = function(rhs) {
236                 rhs[1].unshift(rhs[0]);
237                 return rhs[1];
238         };
239         this.reduceActions[56] = function(rhs) {
240                 if (rhs[0] == "ancestor") {
241                         return Step.ANCESTOR;
242                 } else if (rhs[0] == "ancestor-or-self") {
243                         return Step.ANCESTORORSELF;
244                 } else if (rhs[0] == "attribute") {
245                         return Step.ATTRIBUTE;
246                 } else if (rhs[0] == "child") {
247                         return Step.CHILD;
248                 } else if (rhs[0] == "descendant") {
249                         return Step.DESCENDANT;
250                 } else if (rhs[0] == "descendant-or-self") {
251                         return Step.DESCENDANTORSELF;
252                 } else if (rhs[0] == "following") {
253                         return Step.FOLLOWING;
254                 } else if (rhs[0] == "following-sibling") {
255                         return Step.FOLLOWINGSIBLING;
256                 } else if (rhs[0] == "namespace") {
257                         return Step.NAMESPACE;
258                 } else if (rhs[0] == "parent") {
259                         return Step.PARENT;
260                 } else if (rhs[0] == "preceding") {
261                         return Step.PRECEDING;
262                 } else if (rhs[0] == "preceding-sibling") {
263                         return Step.PRECEDINGSIBLING;
264                 } else if (rhs[0] == "self") {
265                         return Step.SELF;
266                 }
267                 return -1;
268         };
269         this.reduceActions[57] = function(rhs) {
270                 return Step.ATTRIBUTE;
271         };
272         this.reduceActions[59] = function(rhs) {
273                 if (rhs[0] == "comment") {
274                         return new NodeTest(NodeTest.COMMENT, undefined);
275                 } else if (rhs[0] == "text") {
276                         return new NodeTest(NodeTest.TEXT, undefined);
277                 } else if (rhs[0] == "processing-instruction") {
278                         return new NodeTest(NodeTest.PI, undefined);
279                 } else if (rhs[0] == "node") {
280                         return new NodeTest(NodeTest.NODE, undefined);
281                 }
282                 return new NodeTest(-1, undefined);
283         };
284         this.reduceActions[60] = function(rhs) {
285                 return new NodeTest(NodeTest.PI, rhs[2]);
286         };
287         this.reduceActions[61] = function(rhs) {
288                 return rhs[1];
289         };
290         this.reduceActions[63] = function(rhs) {
291                 rhs[1].absolute = true;
292                 rhs[1].steps.unshift(new Step(Step.DESCENDANTORSELF, new NodeTest(NodeTest.NODE, undefined), []));
293                 return rhs[1];
294         };
295         this.reduceActions[64] = function(rhs) {
296                 rhs[0].steps.push(new Step(Step.DESCENDANTORSELF, new NodeTest(NodeTest.NODE, undefined), []));
297                 rhs[0].steps.push(rhs[2]);
298                 return rhs[0];
299         };
300         this.reduceActions[65] = function(rhs) {
301                 return new Step(Step.SELF, new NodeTest(NodeTest.NODE, undefined), []);
302         };
303         this.reduceActions[66] = function(rhs) {
304                 return new Step(Step.PARENT, new NodeTest(NodeTest.NODE, undefined), []);
305         };
306         this.reduceActions[67] = function(rhs) {
307                 return new VariableReference(rhs[1]);
308         };
309         this.reduceActions[68] = function(rhs) {
310                 return new NodeTest(NodeTest.NAMETESTANY, undefined);
311         };
312         this.reduceActions[69] = function(rhs) {
313                 var prefix = rhs[0].substring(0, rhs[0].indexOf(":"));
314                 return new NodeTest(NodeTest.NAMETESTPREFIXANY, prefix);
315         };
316         this.reduceActions[70] = function(rhs) {
317                 return new NodeTest(NodeTest.NAMETESTQNAME, rhs[0]);
318         };
319 };
320
321 XPathParser.actionTable = [
322         " s s        sssssssss    s ss  s  ss",
323         "                 s                  ",
324         "r  rrrrrrrrr         rrrrrrr rr  r  ",
325         "                rrrrr               ",
326         " s s        sssssssss    s ss  s  ss",
327         "rs  rrrrrrrr s  sssssrrrrrr  rrs rs ",
328         " s s        sssssssss    s ss  s  ss",
329         "                            s       ",
330         "                            s       ",
331         "r  rrrrrrrrr         rrrrrrr rr rr  ",
332         "r  rrrrrrrrr         rrrrrrr rr rr  ",
333         "r  rrrrrrrrr         rrrrrrr rr rr  ",
334         "r  rrrrrrrrr         rrrrrrr rr rr  ",
335         "r  rrrrrrrrr         rrrrrrr rr rr  ",
336         "  s                                 ",
337         "                            s       ",
338         " s           s  sssss          s  s ",
339         "r  rrrrrrrrr         rrrrrrr rr  r  ",
340         "a                                   ",
341         "r       s                    rr  r  ",
342         "r      sr                    rr  r  ",
343         "r   s  rr            s       rr  r  ",
344         "r   rssrr            rss     rr  r  ",
345         "r   rrrrr            rrrss   rr  r  ",
346         "r   rrrrrsss         rrrrr   rr  r  ",
347         "r   rrrrrrrr         rrrrr   rr  r  ",
348         "r   rrrrrrrr         rrrrrs  rr  r  ",
349         "r   rrrrrrrr         rrrrrr  rr  r  ",
350         "r   rrrrrrrr         rrrrrr  rr  r  ",
351         "r  srrrrrrrr         rrrrrrs rr sr  ",
352         "r  srrrrrrrr         rrrrrrs rr  r  ",
353         "r  rrrrrrrrr         rrrrrrr rr rr  ",
354         "r  rrrrrrrrr         rrrrrrr rr rr  ",
355         "r  rrrrrrrrr         rrrrrrr rr rr  ",
356         "r   rrrrrrrr         rrrrrr  rr  r  ",
357         "r   rrrrrrrr         rrrrrr  rr  r  ",
358         "r  rrrrrrrrr         rrrrrrr rr  r  ",
359         "r  rrrrrrrrr         rrrrrrr rr  r  ",
360         "                sssss               ",
361         "r  rrrrrrrrr         rrrrrrr rr sr  ",
362         "r  rrrrrrrrr         rrrrrrr rr  r  ",
363         "r  rrrrrrrrr         rrrrrrr rr rr  ",
364         "r  rrrrrrrrr         rrrrrrr rr rr  ",
365         "                             s      ",
366         "r  srrrrrrrr         rrrrrrs rr  r  ",
367         "r   rrrrrrrr         rrrrr   rr  r  ",
368         "              s                     ",
369         "                             s      ",
370         "                rrrrr               ",
371         " s s        sssssssss    s sss s  ss",
372         "r  srrrrrrrr         rrrrrrs rr  r  ",
373         " s s        sssssssss    s ss  s  ss",
374         " s s        sssssssss    s ss  s  ss",
375         " s s        sssssssss    s ss  s  ss",
376         " s s        sssssssss    s ss  s  ss",
377         " s s        sssssssss    s ss  s  ss",
378         " s s        sssssssss    s ss  s  ss",
379         " s s        sssssssss    s ss  s  ss",
380         " s s        sssssssss    s ss  s  ss",
381         " s s        sssssssss    s ss  s  ss",
382         " s s        sssssssss    s ss  s  ss",
383         " s s        sssssssss    s ss  s  ss",
384         " s s        sssssssss    s ss  s  ss",
385         " s s        sssssssss    s ss  s  ss",
386         " s s        sssssssss      ss  s  ss",
387         " s s        sssssssss    s ss  s  ss",
388         " s           s  sssss          s  s ",
389         " s           s  sssss          s  s ",
390         "r  rrrrrrrrr         rrrrrrr rr rr  ",
391         " s           s  sssss          s  s ",
392         " s           s  sssss          s  s ",
393         "r  rrrrrrrrr         rrrrrrr rr sr  ",
394         "r  rrrrrrrrr         rrrrrrr rr sr  ",
395         "r  rrrrrrrrr         rrrrrrr rr  r  ",
396         "r  rrrrrrrrr         rrrrrrr rr rr  ",
397         "                             s      ",
398         "r  rrrrrrrrr         rrrrrrr rr rr  ",
399         "r  rrrrrrrrr         rrrrrrr rr rr  ",
400         "                             rr     ",
401         "                             s      ",
402         "                             rs     ",
403         "r      sr                    rr  r  ",
404         "r   s  rr            s       rr  r  ",
405         "r   rssrr            rss     rr  r  ",
406         "r   rssrr            rss     rr  r  ",
407         "r   rrrrr            rrrss   rr  r  ",
408         "r   rrrrr            rrrss   rr  r  ",
409         "r   rrrrr            rrrss   rr  r  ",
410         "r   rrrrr            rrrss   rr  r  ",
411         "r   rrrrrsss         rrrrr   rr  r  ",
412         "r   rrrrrsss         rrrrr   rr  r  ",
413         "r   rrrrrrrr         rrrrr   rr  r  ",
414         "r   rrrrrrrr         rrrrr   rr  r  ",
415         "r   rrrrrrrr         rrrrr   rr  r  ",
416         "r   rrrrrrrr         rrrrrr  rr  r  ",
417         "                                 r  ",
418         "                                 s  ",
419         "r  srrrrrrrr         rrrrrrs rr  r  ",
420         "r  srrrrrrrr         rrrrrrs rr  r  ",
421         "r  rrrrrrrrr         rrrrrrr rr  r  ",
422         "r  rrrrrrrrr         rrrrrrr rr  r  ",
423         "r  rrrrrrrrr         rrrrrrr rr  r  ",
424         "r  rrrrrrrrr         rrrrrrr rr  r  ",
425         "r  rrrrrrrrr         rrrrrrr rr rr  ",
426         "r  rrrrrrrrr         rrrrrrr rr rr  ",
427         " s s        sssssssss    s ss  s  ss",
428         "r  rrrrrrrrr         rrrrrrr rr rr  ",
429         "                             r      "
430 ];
431
432 XPathParser.actionTableNumber = [
433         " 1 0        /.-,+*)('    & %$  #  \"!",
434         "                 J                  ",
435         "a  aaaaaaaaa         aaaaaaa aa  a  ",
436         "                YYYYY               ",
437         " 1 0        /.-,+*)('    & %$  #  \"!",
438         "K1  KKKKKKKK .  +*)('KKKKKK  KK# K\" ",
439         " 1 0        /.-,+*)('    & %$  #  \"!",
440         "                            N       ",
441         "                            O       ",
442         "e  eeeeeeeee         eeeeeee ee ee  ",
443         "f  fffffffff         fffffff ff ff  ",
444         "d  ddddddddd         ddddddd dd dd  ",
445         "B  BBBBBBBBB         BBBBBBB BB BB  ",
446         "A  AAAAAAAAA         AAAAAAA AA AA  ",
447         "  P                                 ",
448         "                            Q       ",
449         " 1           .  +*)('          #  \" ",
450         "b  bbbbbbbbb         bbbbbbb bb  b  ",
451         "                                    ",
452         "!       S                    !!  !  ",
453         "\"      T\"                    \"\"  \"  ",
454         "$   V  $$            U       $$  $  ",
455         "&   &ZY&&            &XW     &&  &  ",
456         ")   )))))            )))\\[   ))  )  ",
457         ".   ....._^]         .....   ..  .  ",
458         "1   11111111         11111   11  1  ",
459         "5   55555555         55555`  55  5  ",
460         "7   77777777         777777  77  7  ",
461         "9   99999999         999999  99  9  ",
462         ":  c::::::::         ::::::b :: a:  ",
463         "I  fIIIIIIII         IIIIIIe II  I  ",
464         "=  =========         ======= == ==  ",
465         "?  ?????????         ??????? ?? ??  ",
466         "C  CCCCCCCCC         CCCCCCC CC CC  ",
467         "J   JJJJJJJJ         JJJJJJ  JJ  J  ",
468         "M   MMMMMMMM         MMMMMM  MM  M  ",
469         "N  NNNNNNNNN         NNNNNNN NN  N  ",
470         "P  PPPPPPPPP         PPPPPPP PP  P  ",
471         "                +*)('               ",
472         "R  RRRRRRRRR         RRRRRRR RR aR  ",
473         "U  UUUUUUUUU         UUUUUUU UU  U  ",
474         "Z  ZZZZZZZZZ         ZZZZZZZ ZZ ZZ  ",
475         "c  ccccccccc         ccccccc cc cc  ",
476         "                             j      ",
477         "L  fLLLLLLLL         LLLLLLe LL  L  ",
478         "6   66666666         66666   66  6  ",
479         "              k                     ",
480         "                             l      ",
481         "                XXXXX               ",
482         " 1 0        /.-,+*)('    & %$m #  \"!",
483         "_  f________         ______e __  _  ",
484         " 1 0        /.-,+*)('    & %$  #  \"!",
485         " 1 0        /.-,+*)('    & %$  #  \"!",
486         " 1 0        /.-,+*)('    & %$  #  \"!",
487         " 1 0        /.-,+*)('    & %$  #  \"!",
488         " 1 0        /.-,+*)('    & %$  #  \"!",
489         " 1 0        /.-,+*)('    & %$  #  \"!",
490         " 1 0        /.-,+*)('    & %$  #  \"!",
491         " 1 0        /.-,+*)('    & %$  #  \"!",
492         " 1 0        /.-,+*)('    & %$  #  \"!",
493         " 1 0        /.-,+*)('    & %$  #  \"!",
494         " 1 0        /.-,+*)('    & %$  #  \"!",
495         " 1 0        /.-,+*)('    & %$  #  \"!",
496         " 1 0        /.-,+*)('    & %$  #  \"!",
497         " 1 0        /.-,+*)('      %$  #  \"!",
498         " 1 0        /.-,+*)('    & %$  #  \"!",
499         " 1           .  +*)('          #  \" ",
500         " 1           .  +*)('          #  \" ",
501         ">  >>>>>>>>>         >>>>>>> >> >>  ",
502         " 1           .  +*)('          #  \" ",
503         " 1           .  +*)('          #  \" ",
504         "Q  QQQQQQQQQ         QQQQQQQ QQ aQ  ",
505         "V  VVVVVVVVV         VVVVVVV VV aV  ",
506         "T  TTTTTTTTT         TTTTTTT TT  T  ",
507         "@  @@@@@@@@@         @@@@@@@ @@ @@  ",
508         "                             \x87      ",
509         "[  [[[[[[[[[         [[[[[[[ [[ [[  ",
510         "D  DDDDDDDDD         DDDDDDD DD DD  ",
511         "                             HH     ",
512         "                             \x88      ",
513         "                             F\x89     ",
514         "#      T#                    ##  #  ",
515         "%   V  %%            U       %%  %  ",
516         "'   'ZY''            'XW     ''  '  ",
517         "(   (ZY((            (XW     ((  (  ",
518         "+   +++++            +++\\[   ++  +  ",
519         "*   *****            ***\\[   **  *  ",
520         "-   -----            ---\\[   --  -  ",
521         ",   ,,,,,            ,,,\\[   ,,  ,  ",
522         "0   00000_^]         00000   00  0  ",
523         "/   /////_^]         /////   //  /  ",
524         "2   22222222         22222   22  2  ",
525         "3   33333333         33333   33  3  ",
526         "4   44444444         44444   44  4  ",
527         "8   88888888         888888  88  8  ",
528         "                                 ^  ",
529         "                                 \x8a  ",
530         ";  f;;;;;;;;         ;;;;;;e ;;  ;  ",
531         "<  f<<<<<<<<         <<<<<<e <<  <  ",
532         "O  OOOOOOOOO         OOOOOOO OO  O  ",
533         "`  `````````         ``````` ``  `  ",
534         "S  SSSSSSSSS         SSSSSSS SS  S  ",
535         "W  WWWWWWWWW         WWWWWWW WW  W  ",
536         "\\  \\\\\\\\\\\\\\\\\\         \\\\\\\\\\\\\\ \\\\ \\\\  ",
537         "E  EEEEEEEEE         EEEEEEE EE EE  ",
538         " 1 0        /.-,+*)('    & %$  #  \"!",
539         "]  ]]]]]]]]]         ]]]]]]] ]] ]]  ",
540         "                             G      "
541 ];
542
543 XPathParser.gotoTable = [
544         "3456789:;<=>?@ AB  CDEFGH IJ ",
545         "                             ",
546         "                             ",
547         "                             ",
548         "L456789:;<=>?@ AB  CDEFGH IJ ",
549         "            M        EFGH IJ ",
550         "       N;<=>?@ AB  CDEFGH IJ ",
551         "                             ",
552         "                             ",
553         "                             ",
554         "                             ",
555         "                             ",
556         "                             ",
557         "                             ",
558         "                             ",
559         "                             ",
560         "            S        EFGH IJ ",
561         "                             ",
562         "                             ",
563         "                             ",
564         "                             ",
565         "                             ",
566         "                             ",
567         "                             ",
568         "                             ",
569         "                             ",
570         "                             ",
571         "                             ",
572         "                             ",
573         "              e              ",
574         "                             ",
575         "                             ",
576         "                             ",
577         "                             ",
578         "                             ",
579         "                             ",
580         "                             ",
581         "                             ",
582         "                        h  J ",
583         "              i          j   ",
584         "                             ",
585         "                             ",
586         "                             ",
587         "                             ",
588         "                             ",
589         "                             ",
590         "                             ",
591         "                             ",
592         "                             ",
593         "o456789:;<=>?@ ABpqCDEFGH IJ ",
594         "                             ",
595         "  r6789:;<=>?@ AB  CDEFGH IJ ",
596         "   s789:;<=>?@ AB  CDEFGH IJ ",
597         "    t89:;<=>?@ AB  CDEFGH IJ ",
598         "    u89:;<=>?@ AB  CDEFGH IJ ",
599         "     v9:;<=>?@ AB  CDEFGH IJ ",
600         "     w9:;<=>?@ AB  CDEFGH IJ ",
601         "     x9:;<=>?@ AB  CDEFGH IJ ",
602         "     y9:;<=>?@ AB  CDEFGH IJ ",
603         "      z:;<=>?@ AB  CDEFGH IJ ",
604         "      {:;<=>?@ AB  CDEFGH IJ ",
605         "       |;<=>?@ AB  CDEFGH IJ ",
606         "       };<=>?@ AB  CDEFGH IJ ",
607         "       ~;<=>?@ AB  CDEFGH IJ ",
608         "         \x7f=>?@ AB  CDEFGH IJ ",
609         "\x80456789:;<=>?@ AB  CDEFGH IJ\x81",
610         "            \x82        EFGH IJ ",
611         "            \x83        EFGH IJ ",
612         "                             ",
613         "                     \x84 GH IJ ",
614         "                     \x85 GH IJ ",
615         "              i          \x86   ",
616         "              i          \x87   ",
617         "                             ",
618         "                             ",
619         "                             ",
620         "                             ",
621         "                             ",
622         "                             ",
623         "                             ",
624         "                             ",
625         "                             ",
626         "                             ",
627         "                             ",
628         "                             ",
629         "                             ",
630         "                             ",
631         "                             ",
632         "                             ",
633         "                             ",
634         "                             ",
635         "                             ",
636         "                             ",
637         "                             ",
638         "                             ",
639         "                             ",
640         "                             ",
641         "                             ",
642         "                             ",
643         "                             ",
644         "                             ",
645         "                             ",
646         "                             ",
647         "                             ",
648         "                             ",
649         "o456789:;<=>?@ AB\x8cqCDEFGH IJ ",
650         "                             ",
651         "                             "
652 ];
653
654 XPathParser.productions = [
655         [1, 1, 2],
656         [2, 1, 3],
657         [3, 1, 4],
658         [3, 3, 3, -9, 4],
659         [4, 1, 5],
660         [4, 3, 4, -8, 5],
661         [5, 1, 6],
662         [5, 3, 5, -22, 6],
663         [5, 3, 5, -5, 6],
664         [6, 1, 7],
665         [6, 3, 6, -23, 7],
666         [6, 3, 6, -24, 7],
667         [6, 3, 6, -6, 7],
668         [6, 3, 6, -7, 7],
669         [7, 1, 8],
670         [7, 3, 7, -25, 8],
671         [7, 3, 7, -26, 8],
672         [8, 1, 9],
673         [8, 3, 8, -12, 9],
674         [8, 3, 8, -11, 9],
675         [8, 3, 8, -10, 9],
676         [9, 1, 10],
677         [9, 2, -26, 9],
678         [10, 1, 11],
679         [10, 3, 10, -27, 11],
680         [11, 1, 12],
681         [11, 1, 13],
682         [11, 3, 13, -28, 14],
683         [11, 3, 13, -4, 14],
684         [13, 1, 15],
685         [13, 2, 13, 16],
686         [15, 1, 17],
687         [15, 3, -29, 2, -30],
688         [15, 1, -15],
689         [15, 1, -16],
690         [15, 1, 18],
691         [18, 3, -13, -29, -30],
692         [18, 4, -13, -29, 19, -30],
693         [19, 1, 20],
694         [19, 3, 20, -31, 19],
695         [20, 1, 2],
696         [12, 1, 14],
697         [12, 1, 21],
698         [21, 1, -28],
699         [21, 2, -28, 14],
700         [21, 1, 22],
701         [14, 1, 23],
702         [14, 3, 14, -28, 23],
703         [14, 1, 24],
704         [23, 2, 25, 26],
705         [23, 1, 26],
706         [23, 3, 25, 26, 27],
707         [23, 2, 26, 27],
708         [23, 1, 28],
709         [27, 1, 16],
710         [27, 2, 16, 27],
711         [25, 2, -14, -3],
712         [25, 1, -32],
713         [26, 1, 29],
714         [26, 3, -20, -29, -30],
715         [26, 4, -21, -29, -15, -30],
716         [16, 3, -33, 30, -34],
717         [30, 1, 2],
718         [22, 2, -4, 14],
719         [24, 3, 14, -4, 23],
720         [28, 1, -35],
721         [28, 1, -2],
722         [17, 2, -36, -18],
723         [29, 1, -17],
724         [29, 1, -19],
725         [29, 1, -18]
726 ];
727
728 XPathParser.DOUBLEDOT = 2;
729 XPathParser.DOUBLECOLON = 3;
730 XPathParser.DOUBLESLASH = 4;
731 XPathParser.NOTEQUAL = 5;
732 XPathParser.LESSTHANOREQUAL = 6;
733 XPathParser.GREATERTHANOREQUAL = 7;
734 XPathParser.AND = 8;
735 XPathParser.OR = 9;
736 XPathParser.MOD = 10;
737 XPathParser.DIV = 11;
738 XPathParser.MULTIPLYOPERATOR = 12;
739 XPathParser.FUNCTIONNAME = 13;
740 XPathParser.AXISNAME = 14;
741 XPathParser.LITERAL = 15;
742 XPathParser.NUMBER = 16;
743 XPathParser.ASTERISKNAMETEST = 17;
744 XPathParser.QNAME = 18;
745 XPathParser.NCNAMECOLONASTERISK = 19;
746 XPathParser.NODETYPE = 20;
747 XPathParser.PROCESSINGINSTRUCTIONWITHLITERAL = 21;
748 XPathParser.EQUALS = 22;
749 XPathParser.LESSTHAN = 23;
750 XPathParser.GREATERTHAN = 24;
751 XPathParser.PLUS = 25;
752 XPathParser.MINUS = 26;
753 XPathParser.BAR = 27;
754 XPathParser.SLASH = 28;
755 XPathParser.LEFTPARENTHESIS = 29;
756 XPathParser.RIGHTPARENTHESIS = 30;
757 XPathParser.COMMA = 31;
758 XPathParser.AT = 32;
759 XPathParser.LEFTBRACKET = 33;
760 XPathParser.RIGHTBRACKET = 34;
761 XPathParser.DOT = 35;
762 XPathParser.DOLLAR = 36;
763
764 XPathParser.prototype.tokenize = function(s1) {
765         var types = [];
766         var values = [];
767         var s = s1 + '\0';
768
769         var pos = 0;
770         var c = s.charAt(pos++);
771         while (1) {
772                 while (c == ' ' || c == '\t' || c == '\r' || c == '\n') {
773                         c = s.charAt(pos++);
774                 }
775                 if (c == '\0' || pos >= s.length) {
776                         break;
777                 }
778
779                 if (c == '(') {
780                         types.push(XPathParser.LEFTPARENTHESIS);
781                         values.push(c);
782                         c = s.charAt(pos++);
783                         continue;
784                 }
785                 if (c == ')') {
786                         types.push(XPathParser.RIGHTPARENTHESIS);
787                         values.push(c);
788                         c = s.charAt(pos++);
789                         continue;
790                 }
791                 if (c == '[') {
792                         types.push(XPathParser.LEFTBRACKET);
793                         values.push(c);
794                         c = s.charAt(pos++);
795                         continue;
796                 }
797                 if (c == ']') {
798                         types.push(XPathParser.RIGHTBRACKET);
799                         values.push(c);
800                         c = s.charAt(pos++);
801                         continue;
802                 }
803                 if (c == '@') {
804                         types.push(XPathParser.AT);
805                         values.push(c);
806                         c = s.charAt(pos++);
807                         continue;
808                 }
809                 if (c == ',') {
810                         types.push(XPathParser.COMMA);
811                         values.push(c);
812                         c = s.charAt(pos++);
813                         continue;
814                 }
815                 if (c == '|') {
816                         types.push(XPathParser.BAR);
817                         values.push(c);
818                         c = s.charAt(pos++);
819                         continue;
820                 }
821                 if (c == '+') {
822                         types.push(XPathParser.PLUS);
823                         values.push(c);
824                         c = s.charAt(pos++);
825                         continue;
826                 }
827                 if (c == '-') {
828                         types.push(XPathParser.MINUS);
829                         values.push(c);
830                         c = s.charAt(pos++);
831                         continue;
832                 }
833                 if (c == '=') {
834                         types.push(XPathParser.EQUALS);
835                         values.push(c);
836                         c = s.charAt(pos++);
837                         continue;
838                 }
839                 if (c == '$') {
840                         types.push(XPathParser.DOLLAR);
841                         values.push(c);
842                         c = s.charAt(pos++);
843                         continue;
844                 }
845                 
846                 if (c == '.') {
847                         c = s.charAt(pos++);
848                         if (c == '.') {
849                                 types.push(XPathParser.DOUBLEDOT);
850                                 values.push("..");
851                                 c = s.charAt(pos++);
852                                 continue;
853                         }
854                         if (c >= '0' && c <= '9') {
855                                 var number = "." + c;
856                                 c = s.charAt(pos++);
857                                 while (c >= '0' && c <= '9') {
858                                         number += c;
859                                         c = s.charAt(pos++);
860                                 }
861                                 types.push(XPathParser.NUMBER);
862                                 values.push(number);
863                                 continue;
864                         }
865                         types.push(XPathParser.DOT);
866                         values.push('.');
867                         continue;
868                 }
869
870                 if (c == '\'' || c == '"') {
871                         var delimiter = c;
872                         var literal = "";
873                         while ((c = s.charAt(pos++)) != delimiter) {
874                                 literal += c;
875                         }
876                         types.push(XPathParser.LITERAL);
877                         values.push(literal);
878                         c = s.charAt(pos++);
879                         continue;
880                 }
881
882                 if (c >= '0' && c <= '9') {
883                         var number = c;
884                         c = s.charAt(pos++);
885                         while (c >= '0' && c <= '9') {
886                                 number += c;
887                                 c = s.charAt(pos++);
888                         }
889                         if (c == '.') {
890                                 if (s.charAt(pos) >= '0' && s.charAt(pos) <= '9') {
891                                         number += c;
892                                         number += s.charAt(pos++);
893                                         c = s.charAt(pos++);
894                                         while (c >= '0' && c <= '9') {
895                                                 number += c;
896                                                 c = s.charAt(pos++);
897                                         }
898                                 }
899                         }
900                         types.push(XPathParser.NUMBER);
901                         values.push(number);
902                         continue;
903                 }
904
905                 if (c == '*') {
906                         if (types.length > 0) {
907                                 var last = types[types.length - 1];
908                                 if (last != XPathParser.AT
909                                                 && last != XPathParser.DOUBLECOLON
910                                                 && last != XPathParser.LEFTPARENTHESIS
911                                                 && last != XPathParser.LEFTBRACKET
912                                                 && last != XPathParser.AND
913                                                 && last != XPathParser.OR
914                                                 && last != XPathParser.MOD
915                                                 && last != XPathParser.DIV
916                                                 && last != XPathParser.MULTIPLYOPERATOR
917                                                 && last != XPathParser.SLASH
918                                                 && last != XPathParser.DOUBLESLASH
919                                                 && last != XPathParser.BAR
920                                                 && last != XPathParser.PLUS
921                                                 && last != XPathParser.MINUS
922                                                 && last != XPathParser.EQUALS
923                                                 && last != XPathParser.NOTEQUAL
924                                                 && last != XPathParser.LESSTHAN
925                                                 && last != XPathParser.LESSTHANOREQUAL
926                                                 && last != XPathParser.GREATERTHAN
927                                                 && last != XPathParser.GREATERTHANOREQUAL) {
928                                         types.push(XPathParser.MULTIPLYOPERATOR);
929                                         values.push(c);
930                                         c = s.charAt(pos++);
931                                         continue;
932                                 }
933                         }
934                         types.push(XPathParser.ASTERISKNAMETEST);
935                         values.push(c);
936                         c = s.charAt(pos++);
937                         continue;
938                 }
939
940                 if (c == ':') {
941                         if (s.charAt(pos) == ':') {
942                                 types.push(XPathParser.DOUBLECOLON);
943                                 values.push("::");
944                                 pos++;
945                                 c = s.charAt(pos++);
946                                 continue;
947                         }
948                 }
949
950                 if (c == '/') {
951                         c = s.charAt(pos++);
952                         if (c == '/') {
953                                 types.push(XPathParser.DOUBLESLASH);
954                                 values.push("//");
955                                 c = s.charAt(pos++);
956                                 continue;
957                         }
958                         types.push(XPathParser.SLASH);
959                         values.push('/');
960                         continue;
961                 }
962
963                 if (c == '!') {
964                         if (s.charAt(pos) == '=') {
965                                 types.push(XPathParser.NOTEQUAL);
966                                 values.push("!=");
967                                 pos++;
968                                 c = s.charAt(pos++);
969                                 continue;
970                         }
971                 }
972
973                 if (c == '<') {
974                         if (s.charAt(pos) == '=') {
975                                 types.push(XPathParser.LESSTHANOREQUAL);
976                                 values.push("<=");
977                                 pos++;
978                                 c = s.charAt(pos++);
979                                 continue;
980                         }
981                         types.push(XPathParser.LESSTHAN);
982                         values.push('<');
983                         c = s.charAt(pos++);
984                         continue;
985                 }
986
987                 if (c == '>') {
988                         if (s.charAt(pos) == '=') {
989                                 types.push(XPathParser.GREATERTHANOREQUAL);
990                                 values.push(">=");
991                                 pos++;
992                                 c = s.charAt(pos++);
993                                 continue;
994                         }
995                         types.push(XPathParser.GREATERTHAN);
996                         values.push('>');
997                         c = s.charAt(pos++);
998                         continue;
999                 }
1000
1001                 if (c == '_' || Utilities.isLetter(c.charCodeAt(0))) {
1002                         var name = c;
1003                         c = s.charAt(pos++);
1004                         while (Utilities.isNCNameChar(c.charCodeAt(0))) {
1005                                 name += c;
1006                                 c = s.charAt(pos++);
1007                         }
1008                         if (types.length > 0) {
1009                                 var last = types[types.length - 1];
1010                                 if (last != XPathParser.AT
1011                                                 && last != XPathParser.DOUBLECOLON
1012                                                 && last != XPathParser.LEFTPARENTHESIS
1013                                                 && last != XPathParser.LEFTBRACKET
1014                                                 && last != XPathParser.AND
1015                                                 && last != XPathParser.OR
1016                                                 && last != XPathParser.MOD
1017                                                 && last != XPathParser.DIV
1018                                                 && last != XPathParser.MULTIPLYOPERATOR
1019                                                 && last != XPathParser.SLASH
1020                                                 && last != XPathParser.DOUBLESLASH
1021                                                 && last != XPathParser.BAR
1022                                                 && last != XPathParser.PLUS
1023                                                 && last != XPathParser.MINUS
1024                                                 && last != XPathParser.EQUALS
1025                                                 && last != XPathParser.NOTEQUAL
1026                                                 && last != XPathParser.LESSTHAN
1027                                                 && last != XPathParser.LESSTHANOREQUAL
1028                                                 && last != XPathParser.GREATERTHAN
1029                                                 && last != XPathParser.GREATERTHANOREQUAL) {
1030                                         if (name == "and") {
1031                                                 types.push(XPathParser.AND);
1032                                                 values.push(name);
1033                                                 continue;
1034                                         }
1035                                         if (name == "or") {
1036                                                 types.push(XPathParser.OR);
1037                                                 values.push(name);
1038                                                 continue;
1039                                         }
1040                                         if (name == "mod") {
1041                                                 types.push(XPathParser.MOD);
1042                                                 values.push(name);
1043                                                 continue;
1044                                         }
1045                                         if (name == "div") {
1046                                                 types.push(XPathParser.DIV);
1047                                                 values.push(name);
1048                                                 continue;
1049                                         }
1050                                 }
1051                         }
1052                         if (c == ':') {
1053                                 if (s.charAt(pos) == '*') {
1054                                         types.push(XPathParser.NCNAMECOLONASTERISK);
1055                                         values.push(name + ":*");
1056                                         pos++;
1057                                         c = s.charAt(pos++);
1058                                         continue;
1059                                 }
1060                                 if (s.charAt(pos) == '_' || Utilities.isLetter(s.charCodeAt(pos))) {
1061                                         name += ':';
1062                                         c = s.charAt(pos++);
1063                                         while (Utilities.isNCNameChar(c.charCodeAt(0))) {
1064                                                 name += c;
1065                                                 c = s.charAt(pos++);
1066                                         }
1067                                         if (c == '(') {
1068                                                 types.push(XPathParser.FUNCTIONNAME);
1069                                                 values.push(name);
1070                                                 continue;
1071                                         }
1072                                         types.push(XPathParser.QNAME);
1073                                         values.push(name);
1074                                         continue;
1075                                 }
1076                                 if (s.charAt(pos) == ':') {
1077                                         types.push(XPathParser.AXISNAME);
1078                                         values.push(name);
1079                                         continue;
1080                                 }
1081                         }
1082                         if (c == '(') {
1083                                 if (name == "comment" || name == "text" || name == "node") {
1084                                         types.push(XPathParser.NODETYPE);
1085                                         values.push(name);
1086                                         continue;
1087                                 }
1088                                 if (name == "processing-instruction") {
1089                                         if (s.charAt(pos) == ')') {
1090                                                 types.push(XPathParser.NODETYPE);
1091                                         } else {
1092                                                 types.push(XPathParser.PROCESSINGINSTRUCTIONWITHLITERAL);
1093                                         }
1094                                         values.push(name);
1095                                         continue;
1096                                 }
1097                                 types.push(XPathParser.FUNCTIONNAME);
1098                                 values.push(name);
1099                                 continue;
1100                         }
1101                         types.push(XPathParser.QNAME);
1102                         values.push(name);
1103                         continue;
1104                 }
1105
1106                 throw new Error("Unexpected character " + c);
1107         }
1108         types.push(1);
1109         values.push("[EOF]");
1110         return [types, values];
1111 };
1112
1113 XPathParser.SHIFT = 's';
1114 XPathParser.REDUCE = 'r';
1115 XPathParser.ACCEPT = 'a';
1116
1117 XPathParser.prototype.parse = function(s) {
1118         var types;
1119         var values;
1120         var res = this.tokenize(s);
1121         if (res == undefined) {
1122                 return undefined;
1123         }
1124         types = res[0];
1125         values = res[1];
1126         var tokenPos = 0;
1127         var state = [];
1128         var tokenType = [];
1129         var tokenValue = [];
1130         var s;
1131         var a;
1132         var t;
1133
1134         state.push(0);
1135         tokenType.push(1);
1136         tokenValue.push("_S");
1137
1138         a = types[tokenPos];
1139         t = values[tokenPos++];
1140         while (1) {
1141                 s = state[state.length - 1];
1142                 switch (XPathParser.actionTable[s].charAt(a - 1)) {
1143                         case XPathParser.SHIFT:
1144                                 tokenType.push(-a);
1145                                 tokenValue.push(t);
1146                                 state.push(XPathParser.actionTableNumber[s].charCodeAt(a - 1) - 32);
1147                                 a = types[tokenPos];
1148                                 t = values[tokenPos++];
1149                                 break;
1150                         case XPathParser.REDUCE:
1151                                 var num = XPathParser.productions[XPathParser.actionTableNumber[s].charCodeAt(a - 1) - 32][1];
1152                                 var rhs = [];
1153                                 for (var i = 0; i < num; i++) {
1154                                         tokenType.pop();
1155                                         rhs.unshift(tokenValue.pop());
1156                                         state.pop();
1157                                 }
1158                                 var s_ = state[state.length - 1];
1159                                 tokenType.push(XPathParser.productions[XPathParser.actionTableNumber[s].charCodeAt(a - 1) - 32][0]);
1160                                 if (this.reduceActions[XPathParser.actionTableNumber[s].charCodeAt(a - 1) - 32] == undefined) {
1161                                         tokenValue.push(rhs[0]);
1162                                 } else {
1163                                         tokenValue.push(this.reduceActions[XPathParser.actionTableNumber[s].charCodeAt(a - 1) - 32](rhs));
1164                                 }
1165                                 state.push(XPathParser.gotoTable[s_].charCodeAt(XPathParser.productions[XPathParser.actionTableNumber[s].charCodeAt(a - 1) - 32][0] - 2) - 33);
1166                                 break;
1167                         case XPathParser.ACCEPT:
1168                                 return new XPath(tokenValue.pop());
1169                         default:
1170                                 throw new Error("XPath parse error");
1171                 }
1172         }
1173 };
1174
1175 // XPath /////////////////////////////////////////////////////////////////////
1176
1177 XPath.prototype = new Object();
1178 XPath.prototype.constructor = XPath;
1179 XPath.superclass = Object.prototype;
1180
1181 function XPath(e) {
1182         this.expression = e;
1183 }
1184
1185 XPath.prototype.toString = function() {
1186         return this.expression.toString();
1187 };
1188
1189 XPath.prototype.evaluate = function(c) {
1190         c.contextNode = c.expressionContextNode;
1191         c.contextSize = 1;
1192         c.contextPosition = 1;
1193         c.caseInsensitive = false;
1194         if (c.contextNode != null) {
1195                 var doc = c.contextNode;
1196                 if (doc.nodeType != 9 /*Node.DOCUMENT_NODE*/) {
1197                         doc = doc.ownerDocument;
1198                 }
1199                 try {
1200                         c.caseInsensitive = doc.implementation.hasFeature("HTML", "2.0");
1201                 } catch (e) {
1202                         c.caseInsensitive = true;
1203                 }
1204         }
1205         return this.expression.evaluate(c);
1206 };
1207
1208 XPath.XML_NAMESPACE_URI = "http://www.w3.org/XML/1998/namespace";
1209 XPath.XMLNS_NAMESPACE_URI = "http://www.w3.org/2000/xmlns/";
1210
1211 // Expression ////////////////////////////////////////////////////////////////
1212
1213 Expression.prototype = new Object();
1214 Expression.prototype.constructor = Expression;
1215 Expression.superclass = Object.prototype;
1216
1217 function Expression() {
1218 }
1219
1220 Expression.prototype.init = function() {
1221 };
1222
1223 Expression.prototype.toString = function() {
1224         return "<Expression>";
1225 };
1226
1227 Expression.prototype.evaluate = function(c) {
1228         throw new Error("Could not evaluate expression.");
1229 };
1230
1231 // UnaryOperation ////////////////////////////////////////////////////////////
1232
1233 UnaryOperation.prototype = new Expression();
1234 UnaryOperation.prototype.constructor = UnaryOperation;
1235 UnaryOperation.superclass = Expression.prototype;
1236
1237 function UnaryOperation(rhs) {
1238         if (arguments.length > 0) {
1239                 this.init(rhs);
1240         }
1241 }
1242
1243 UnaryOperation.prototype.init = function(rhs) {
1244         this.rhs = rhs;
1245 };
1246
1247 // UnaryMinusOperation ///////////////////////////////////////////////////////
1248
1249 UnaryMinusOperation.prototype = new UnaryOperation();
1250 UnaryMinusOperation.prototype.constructor = UnaryMinusOperation;
1251 UnaryMinusOperation.superclass = UnaryOperation.prototype;
1252
1253 function UnaryMinusOperation(rhs) {
1254         if (arguments.length > 0) {
1255                 this.init(rhs);
1256         }
1257 }
1258
1259 UnaryMinusOperation.prototype.init = function(rhs) {
1260         UnaryMinusOperation.superclass.init.call(this, rhs);
1261 };
1262
1263 UnaryMinusOperation.prototype.evaluate = function(c) {
1264         return this.rhs.evaluate(c).number().negate();
1265 };
1266
1267 UnaryMinusOperation.prototype.toString = function() {
1268         return "-" + this.rhs.toString();
1269 };
1270
1271 // BinaryOperation ///////////////////////////////////////////////////////////
1272
1273 BinaryOperation.prototype = new Expression();
1274 BinaryOperation.prototype.constructor = BinaryOperation;
1275 BinaryOperation.superclass = Expression.prototype;
1276
1277 function BinaryOperation(lhs, rhs) {
1278         if (arguments.length > 0) {
1279                 this.init(lhs, rhs);
1280         }
1281 }
1282
1283 BinaryOperation.prototype.init = function(lhs, rhs) {
1284         this.lhs = lhs;
1285         this.rhs = rhs;
1286 };
1287
1288 // OrOperation ///////////////////////////////////////////////////////////////
1289
1290 OrOperation.prototype = new BinaryOperation();
1291 OrOperation.prototype.constructor = OrOperation;
1292 OrOperation.superclass = BinaryOperation.prototype;
1293
1294 function OrOperation(lhs, rhs) {
1295         if (arguments.length > 0) {
1296                 this.init(lhs, rhs);
1297         }
1298 }
1299
1300 OrOperation.prototype.init = function(lhs, rhs) {
1301         OrOperation.superclass.init.call(this, lhs, rhs);
1302 };
1303
1304 OrOperation.prototype.toString = function() {
1305         return "(" + this.lhs.toString() + " or " + this.rhs.toString() + ")";
1306 };
1307
1308 OrOperation.prototype.evaluate = function(c) {
1309         var b = this.lhs.evaluate(c).bool();
1310         if (b.booleanValue()) {
1311                 return b;
1312         }
1313         return this.rhs.evaluate(c).bool();
1314 };
1315
1316 // AndOperation //////////////////////////////////////////////////////////////
1317
1318 AndOperation.prototype = new BinaryOperation();
1319 AndOperation.prototype.constructor = AndOperation;
1320 AndOperation.superclass = BinaryOperation.prototype;
1321
1322 function AndOperation(lhs, rhs) {
1323         if (arguments.length > 0) {
1324                 this.init(lhs, rhs);
1325         }
1326 }
1327
1328 AndOperation.prototype.init = function(lhs, rhs) {
1329         AndOperation.superclass.init.call(this, lhs, rhs);
1330 };
1331
1332 AndOperation.prototype.toString = function() {
1333         return "(" + this.lhs.toString() + " and " + this.rhs.toString() + ")";
1334 };
1335
1336 AndOperation.prototype.evaluate = function(c) {
1337         var b = this.lhs.evaluate(c).bool();
1338         if (!b.booleanValue()) {
1339                 return b;
1340         }
1341         return this.rhs.evaluate(c).bool();
1342 };
1343
1344 // EqualsOperation ///////////////////////////////////////////////////////////
1345
1346 EqualsOperation.prototype = new BinaryOperation();
1347 EqualsOperation.prototype.constructor = EqualsOperation;
1348 EqualsOperation.superclass = BinaryOperation.prototype;
1349
1350 function EqualsOperation(lhs, rhs) {
1351         if (arguments.length > 0) {
1352                 this.init(lhs, rhs);
1353         }
1354 }
1355
1356 EqualsOperation.prototype.init = function(lhs, rhs) {
1357         EqualsOperation.superclass.init.call(this, lhs, rhs);
1358 };
1359
1360 EqualsOperation.prototype.toString = function() {
1361         return "(" + this.lhs.toString() + " = " + this.rhs.toString() + ")";
1362 };
1363
1364 EqualsOperation.prototype.evaluate = function(c) {
1365         return this.lhs.evaluate(c).equals(this.rhs.evaluate(c));
1366 };
1367
1368 // NotEqualOperation /////////////////////////////////////////////////////////
1369
1370 NotEqualOperation.prototype = new BinaryOperation();
1371 NotEqualOperation.prototype.constructor = NotEqualOperation;
1372 NotEqualOperation.superclass = BinaryOperation.prototype;
1373
1374 function NotEqualOperation(lhs, rhs) {
1375         if (arguments.length > 0) {
1376                 this.init(lhs, rhs);
1377         }
1378 }
1379
1380 NotEqualOperation.prototype.init = function(lhs, rhs) {
1381         NotEqualOperation.superclass.init.call(this, lhs, rhs);
1382 };
1383
1384 NotEqualOperation.prototype.toString = function() {
1385         return "(" + this.lhs.toString() + " != " + this.rhs.toString() + ")";
1386 };
1387
1388 NotEqualOperation.prototype.evaluate = function(c) {
1389         return this.lhs.evaluate(c).notequal(this.rhs.evaluate(c));
1390 };
1391
1392 // LessThanOperation /////////////////////////////////////////////////////////
1393
1394 LessThanOperation.prototype = new BinaryOperation();
1395 LessThanOperation.prototype.constructor = LessThanOperation;
1396 LessThanOperation.superclass = BinaryOperation.prototype;
1397
1398 function LessThanOperation(lhs, rhs) {
1399         if (arguments.length > 0) {
1400                 this.init(lhs, rhs);
1401         }
1402 }
1403
1404 LessThanOperation.prototype.init = function(lhs, rhs) {
1405         LessThanOperation.superclass.init.call(this, lhs, rhs);
1406 };
1407
1408 LessThanOperation.prototype.evaluate = function(c) {
1409         return this.lhs.evaluate(c).lessthan(this.rhs.evaluate(c));
1410 };
1411
1412 LessThanOperation.prototype.toString = function() {
1413         return "(" + this.lhs.toString() + " < " + this.rhs.toString() + ")";
1414 };
1415
1416 // GreaterThanOperation //////////////////////////////////////////////////////
1417
1418 GreaterThanOperation.prototype = new BinaryOperation();
1419 GreaterThanOperation.prototype.constructor = GreaterThanOperation;
1420 GreaterThanOperation.superclass = BinaryOperation.prototype;
1421
1422 function GreaterThanOperation(lhs, rhs) {
1423         if (arguments.length > 0) {
1424                 this.init(lhs, rhs);
1425         }
1426 }
1427
1428 GreaterThanOperation.prototype.init = function(lhs, rhs) {
1429         GreaterThanOperation.superclass.init.call(this, lhs, rhs);
1430 };
1431
1432 GreaterThanOperation.prototype.evaluate = function(c) {
1433         return this.lhs.evaluate(c).greaterthan(this.rhs.evaluate(c));
1434 };
1435
1436 GreaterThanOperation.prototype.toString = function() {
1437         return "(" + this.lhs.toString() + " > " + this.rhs.toString() + ")";
1438 };
1439
1440 // LessThanOrEqualOperation //////////////////////////////////////////////////
1441
1442 LessThanOrEqualOperation.prototype = new BinaryOperation();
1443 LessThanOrEqualOperation.prototype.constructor = LessThanOrEqualOperation;
1444 LessThanOrEqualOperation.superclass = BinaryOperation.prototype;
1445
1446 function LessThanOrEqualOperation(lhs, rhs) {
1447         if (arguments.length > 0) {
1448                 this.init(lhs, rhs);
1449         }
1450 }
1451
1452 LessThanOrEqualOperation.prototype.init = function(lhs, rhs) {
1453         LessThanOrEqualOperation.superclass.init.call(this, lhs, rhs);
1454 };
1455
1456 LessThanOrEqualOperation.prototype.evaluate = function(c) {
1457         return this.lhs.evaluate(c).lessthanorequal(this.rhs.evaluate(c));
1458 };
1459
1460 LessThanOrEqualOperation.prototype.toString = function() {
1461         return "(" + this.lhs.toString() + " <= " + this.rhs.toString() + ")";
1462 };
1463
1464 // GreaterThanOrEqualOperation ///////////////////////////////////////////////
1465
1466 GreaterThanOrEqualOperation.prototype = new BinaryOperation();
1467 GreaterThanOrEqualOperation.prototype.constructor = GreaterThanOrEqualOperation;
1468 GreaterThanOrEqualOperation.superclass = BinaryOperation.prototype;
1469
1470 function GreaterThanOrEqualOperation(lhs, rhs) {
1471         if (arguments.length > 0) {
1472                 this.init(lhs, rhs);
1473         }
1474 }
1475
1476 GreaterThanOrEqualOperation.prototype.init = function(lhs, rhs) {
1477         GreaterThanOrEqualOperation.superclass.init.call(this, lhs, rhs);
1478 };
1479
1480 GreaterThanOrEqualOperation.prototype.evaluate = function(c) {
1481         return this.lhs.evaluate(c).greaterthanorequal(this.rhs.evaluate(c));
1482 };
1483
1484 GreaterThanOrEqualOperation.prototype.toString = function() {
1485         return "(" + this.lhs.toString() + " >= " + this.rhs.toString() + ")";
1486 };
1487
1488 // PlusOperation /////////////////////////////////////////////////////////////
1489
1490 PlusOperation.prototype = new BinaryOperation();
1491 PlusOperation.prototype.constructor = PlusOperation;
1492 PlusOperation.superclass = BinaryOperation.prototype;
1493
1494 function PlusOperation(lhs, rhs) {
1495         if (arguments.length > 0) {
1496                 this.init(lhs, rhs);
1497         }
1498 }
1499
1500 PlusOperation.prototype.init = function(lhs, rhs) {
1501         PlusOperation.superclass.init.call(this, lhs, rhs);
1502 };
1503
1504 PlusOperation.prototype.evaluate = function(c) {
1505         return this.lhs.evaluate(c).number().plus(this.rhs.evaluate(c).number());
1506 };
1507
1508 PlusOperation.prototype.toString = function() {
1509         return "(" + this.lhs.toString() + " + " + this.rhs.toString() + ")";
1510 };
1511
1512 // MinusOperation ////////////////////////////////////////////////////////////
1513
1514 MinusOperation.prototype = new BinaryOperation();
1515 MinusOperation.prototype.constructor = MinusOperation;
1516 MinusOperation.superclass = BinaryOperation.prototype;
1517
1518 function MinusOperation(lhs, rhs) {
1519         if (arguments.length > 0) {
1520                 this.init(lhs, rhs);
1521         }
1522 }
1523
1524 MinusOperation.prototype.init = function(lhs, rhs) {
1525         MinusOperation.superclass.init.call(this, lhs, rhs);
1526 };
1527
1528 MinusOperation.prototype.evaluate = function(c) {
1529         return this.lhs.evaluate(c).number().minus(this.rhs.evaluate(c).number());
1530 };
1531
1532 MinusOperation.prototype.toString = function() {
1533         return "(" + this.lhs.toString() + " - " + this.rhs.toString() + ")";
1534 };
1535
1536 // MultiplyOperation /////////////////////////////////////////////////////////
1537
1538 MultiplyOperation.prototype = new BinaryOperation();
1539 MultiplyOperation.prototype.constructor = MultiplyOperation;
1540 MultiplyOperation.superclass = BinaryOperation.prototype;
1541
1542 function MultiplyOperation(lhs, rhs) {
1543         if (arguments.length > 0) {
1544                 this.init(lhs, rhs);
1545         }
1546 }
1547
1548 MultiplyOperation.prototype.init = function(lhs, rhs) {
1549         MultiplyOperation.superclass.init.call(this, lhs, rhs);
1550 };
1551
1552 MultiplyOperation.prototype.evaluate = function(c) {
1553         return this.lhs.evaluate(c).number().multiply(this.rhs.evaluate(c).number());
1554 };
1555
1556 MultiplyOperation.prototype.toString = function() {
1557         return "(" + this.lhs.toString() + " * " + this.rhs.toString() + ")";
1558 };
1559
1560 // DivOperation //////////////////////////////////////////////////////////////
1561
1562 DivOperation.prototype = new BinaryOperation();
1563 DivOperation.prototype.constructor = DivOperation;
1564 DivOperation.superclass = BinaryOperation.prototype;
1565
1566 function DivOperation(lhs, rhs) {
1567         if (arguments.length > 0) {
1568                 this.init(lhs, rhs);
1569         }
1570 }
1571
1572 DivOperation.prototype.init = function(lhs, rhs) {
1573         DivOperation.superclass.init.call(this, lhs, rhs);
1574 };
1575
1576 DivOperation.prototype.evaluate = function(c) {
1577         return this.lhs.evaluate(c).number().div(this.rhs.evaluate(c).number());
1578 };
1579
1580 DivOperation.prototype.toString = function() {
1581         return "(" + this.lhs.toString() + " div " + this.rhs.toString() + ")";
1582 };
1583
1584 // ModOperation //////////////////////////////////////////////////////////////
1585
1586 ModOperation.prototype = new BinaryOperation();
1587 ModOperation.prototype.constructor = ModOperation;
1588 ModOperation.superclass = BinaryOperation.prototype;
1589
1590 function ModOperation(lhs, rhs) {
1591         if (arguments.length > 0) {
1592                 this.init(lhs, rhs);
1593         }
1594 }
1595
1596 ModOperation.prototype.init = function(lhs, rhs) {
1597         ModOperation.superclass.init.call(this, lhs, rhs);
1598 };
1599
1600 ModOperation.prototype.evaluate = function(c) {
1601         return this.lhs.evaluate(c).number().mod(this.rhs.evaluate(c).number());
1602 };
1603
1604 ModOperation.prototype.toString = function() {
1605         return "(" + this.lhs.toString() + " mod " + this.rhs.toString() + ")";
1606 };
1607
1608 // BarOperation //////////////////////////////////////////////////////////////
1609
1610 BarOperation.prototype = new BinaryOperation();
1611 BarOperation.prototype.constructor = BarOperation;
1612 BarOperation.superclass = BinaryOperation.prototype;
1613
1614 function BarOperation(lhs, rhs) {
1615         if (arguments.length > 0) {
1616                 this.init(lhs, rhs);
1617         }
1618 }
1619
1620 BarOperation.prototype.init = function(lhs, rhs) {
1621         BarOperation.superclass.init.call(this, lhs, rhs);
1622 };
1623
1624 BarOperation.prototype.evaluate = function(c) {
1625         return this.lhs.evaluate(c).nodeset().union(this.rhs.evaluate(c).nodeset());
1626 };
1627
1628 BarOperation.prototype.toString = function() {
1629         return this.lhs.toString() + " | " + this.rhs.toString();
1630 };
1631
1632 // PathExpr //////////////////////////////////////////////////////////////////
1633
1634 PathExpr.prototype = new Expression();
1635 PathExpr.prototype.constructor = PathExpr;
1636 PathExpr.superclass = Expression.prototype;
1637
1638 function PathExpr(filter, filterPreds, locpath) {
1639         if (arguments.length > 0) {
1640                 this.init(filter, filterPreds, locpath);
1641         }
1642 }
1643
1644 PathExpr.prototype.init = function(filter, filterPreds, locpath) {
1645         PathExpr.superclass.init.call(this);
1646         this.filter = filter;
1647         this.filterPredicates = filterPreds;
1648         this.locationPath = locpath;
1649 };
1650
1651 PathExpr.prototype.evaluate = function(c) {
1652         var nodes;
1653         var xpc = new XPathContext();
1654         xpc.variableResolver = c.variableResolver;
1655         xpc.functionResolver = c.functionResolver;
1656         xpc.namespaceResolver = c.namespaceResolver;
1657         xpc.expressionContextNode = c.expressionContextNode;
1658         xpc.virtualRoot = c.virtualRoot;
1659         xpc.caseInsensitive = c.caseInsensitive;
1660         if (this.filter == null) {
1661                 nodes = [ c.contextNode ];
1662         } else {
1663                 var ns = this.filter.evaluate(c);
1664                 if (!Utilities.instance_of(ns, XNodeSet)) {
1665                         if (this.filterPredicates != null && this.filterPredicates.length > 0 || this.locationPath != null) {
1666                                 throw new Error("Path expression filter must evaluate to a nodset if predicates or location path are used");
1667                         }
1668                         return ns;
1669                 }
1670                 nodes = ns.toArray();
1671                 if (this.filterPredicates != null) {
1672                         // apply each of the predicates in turn
1673                         for (var j = 0; j < this.filterPredicates.length; j++) {
1674                                 var pred = this.filterPredicates[j];
1675                                 var newNodes = [];
1676                                 xpc.contextSize = nodes.length;
1677                                 for (xpc.contextPosition = 1; xpc.contextPosition <= xpc.contextSize; xpc.contextPosition++) {
1678                                         xpc.contextNode = nodes[xpc.contextPosition - 1];
1679                                         if (this.predicateMatches(pred, xpc)) {
1680                                                 newNodes.push(xpc.contextNode);
1681                                         }
1682                                 }
1683                                 nodes = newNodes;
1684                         }
1685                 }
1686         }
1687         if (this.locationPath != null) {
1688                 if (this.locationPath.absolute) {
1689                         if (nodes[0].nodeType != 9 /*Node.DOCUMENT_NODE*/) {
1690                                 if (xpc.virtualRoot != null) {
1691                                         nodes = [ xpc.virtualRoot ];
1692                                 } else {
1693                                         if (nodes[0].ownerDocument == null) {
1694                                                 // IE 5.5 doesn't have ownerDocument?
1695                                                 var n = nodes[0];
1696                                                 while (n.parentNode != null) {
1697                                                         n = n.parentNode;
1698                                                 }
1699                                                 nodes = [ n ];
1700                                         } else {
1701                                                 nodes = [ nodes[0].ownerDocument ];
1702                                         }
1703                                 }
1704                         } else {
1705                                 nodes = [ nodes[0] ];
1706                         }
1707                 }
1708                 for (var i = 0; i < this.locationPath.steps.length; i++) {
1709                         var step = this.locationPath.steps[i];
1710                         var newNodes = [];
1711                         for (var j = 0; j < nodes.length; j++) {
1712                                 xpc.contextNode = nodes[j];
1713                                 switch (step.axis) {
1714                                         case Step.ANCESTOR:
1715                                                 // look at all the ancestor nodes
1716                                                 if (xpc.contextNode === xpc.virtualRoot) {
1717                                                         break;
1718                                                 }
1719                                                 var m;
1720                                                 if (xpc.contextNode.nodeType == 2 /*Node.ATTRIBUTE_NODE*/) {
1721                                                         m = this.getOwnerElement(xpc.contextNode);
1722                                                 } else {
1723                                                         m = xpc.contextNode.parentNode;
1724                                                 }
1725                                                 while (m != null) {
1726                                                         if (step.nodeTest.matches(m, xpc)) {
1727                                                                 newNodes.push(m);
1728                                                         }
1729                                                         if (m === xpc.virtualRoot) {
1730                                                                 break;
1731                                                         }
1732                                                         m = m.parentNode;
1733                                                 }
1734                                                 break;
1735
1736                                         case Step.ANCESTORORSELF:
1737                                                 // look at all the ancestor nodes and the current node
1738                                                 for (var m = xpc.contextNode; m != null; m = m.nodeType == 2 /*Node.ATTRIBUTE_NODE*/ ? this.getOwnerElement(m) : m.parentNode) {
1739                                                         if (step.nodeTest.matches(m, xpc)) {
1740                                                                 newNodes.push(m);
1741                                                         }
1742                                                         if (m === xpc.virtualRoot) {
1743                                                                 break;
1744                                                         }
1745                                                 }
1746                                                 break;
1747
1748                                         case Step.ATTRIBUTE:
1749                                                 // look at the attributes
1750                                                 var nnm = xpc.contextNode.attributes;
1751                                                 if (nnm != null) {
1752                                                         for (var k = 0; k < nnm.length; k++) {
1753                                                                 var m = nnm.item(k);
1754                                                                 if (step.nodeTest.matches(m, xpc)) {
1755                                                                         newNodes.push(m);
1756                                                                 }
1757                                                         }
1758                                                 }
1759                                                 break;
1760
1761                                         case Step.CHILD:
1762                                                 // look at all child elements
1763                                                 for (var m = xpc.contextNode.firstChild; m != null; m = m.nextSibling) {
1764                                                         if (step.nodeTest.matches(m, xpc)) {
1765                                                                 newNodes.push(m);
1766                                                         }
1767                                                 }
1768                                                 break;
1769
1770                                         case Step.DESCENDANT:
1771                                                 // look at all descendant nodes
1772                                                 var st = [ xpc.contextNode.firstChild ];
1773                                                 while (st.length > 0) {
1774                                                         for (var m = st.pop(); m != null; ) {
1775                                                                 if (step.nodeTest.matches(m, xpc)) {
1776                                                                         newNodes.push(m);
1777                                                                 }
1778                                                                 if (m.firstChild != null) {
1779                                                                         st.push(m.nextSibling);
1780                                                                         m = m.firstChild;
1781                                                                 } else {
1782                                                                         m = m.nextSibling;
1783                                                                 }
1784                                                         }
1785                                                 }
1786                                                 break;
1787
1788                                         case Step.DESCENDANTORSELF:
1789                                                 // look at self
1790                                                 if (step.nodeTest.matches(xpc.contextNode, xpc)) {
1791                                                         newNodes.push(xpc.contextNode);
1792                                                 }
1793                                                 // look at all descendant nodes
1794                                                 var st = [ xpc.contextNode.firstChild ];
1795                                                 while (st.length > 0) {
1796                                                         for (var m = st.pop(); m != null; ) {
1797                                                                 if (step.nodeTest.matches(m, xpc)) {
1798                                                                         newNodes.push(m);
1799                                                                 }
1800                                                                 if (m.firstChild != null) {
1801                                                                         st.push(m.nextSibling);
1802                                                                         m = m.firstChild;
1803                                                                 } else {
1804                                                                         m = m.nextSibling;
1805                                                                 }
1806                                                         }
1807                                                 }
1808                                                 break;
1809
1810                                         case Step.FOLLOWING:
1811                                                 if (xpc.contextNode === xpc.virtualRoot) {
1812                                                         break;
1813                                                 }
1814                                                 var st = [];
1815                                                 if (xpc.contextNode.firstChild != null) {
1816                                                         st.unshift(xpc.contextNode.firstChild);
1817                                                 } else {
1818                                                         st.unshift(xpc.contextNode.nextSibling);
1819                                                 }
1820                                                 for (var m = xpc.contextNode.parentNode; m != null && m.nodeType != 9 /*Node.DOCUMENT_NODE*/ && m !== xpc.virtualRoot; m = m.parentNode) {
1821                                                         st.unshift(m.nextSibling);
1822                                                 }
1823                                                 do {
1824                                                         for (var m = st.pop(); m != null; ) {
1825                                                                 if (step.nodeTest.matches(m, xpc)) {
1826                                                                         newNodes.push(m);
1827                                                                 }
1828                                                                 if (m.firstChild != null) {
1829                                                                         st.push(m.nextSibling);
1830                                                                         m = m.firstChild;
1831                                                                 } else {
1832                                                                         m = m.nextSibling;
1833                                                                 }
1834                                                         }
1835                                                 } while (st.length > 0);
1836                                                 break;
1837                                                 
1838                                         case Step.FOLLOWINGSIBLING:
1839                                                 if (xpc.contextNode === xpc.virtualRoot) {
1840                                                         break;
1841                                                 }
1842                                                 for (var m = xpc.contextNode.nextSibling; m != null; m = m.nextSibling) {
1843                                                         if (step.nodeTest.matches(m, xpc)) {
1844                                                                 newNodes.push(m);
1845                                                         }
1846                                                 }
1847                                                 break;
1848
1849                                         case Step.NAMESPACE:
1850                                                 var n = {};
1851                                                 if (xpc.contextNode.nodeType == 1 /*Node.ELEMENT_NODE*/) {
1852                                                         n["xml"] = XPath.XML_NAMESPACE_URI;
1853                                                         n["xmlns"] = XPath.XMLNS_NAMESPACE_URI;
1854                                                         for (var m = xpc.contextNode; m != null && m.nodeType == 1 /*Node.ELEMENT_NODE*/; m = m.parentNode) {
1855                                                                 for (var k = 0; k < m.attributes.length; k++) {
1856                                                                         var attr = m.attributes.item(k);
1857                                                                         var nm = String(attr.name);
1858                                                                         if (nm == "xmlns") {
1859                                                                                 if (n[""] == undefined) {
1860                                                                                         n[""] = attr.value;
1861                                                                                 }
1862                                                                         } else if (nm.length > 6 && nm.substring(0, 6) == "xmlns:") {
1863                                                                                 var pre = nm.substring(6, nm.length);
1864                                                                                 if (n[pre] == undefined) {
1865                                                                                         n[pre] = attr.value;
1866                                                                                 }
1867                                                                         }
1868                                                                 }
1869                                                         }
1870                                                         for (var pre in n) {
1871                                                                 var nsn = new NamespaceNode(pre, n[pre], xpc.contextNode);
1872                                                                 if (step.nodeTest.matches(nsn, xpc)) {
1873                                                                         newNodes.push(nsn);
1874                                                                 }
1875                                                         }
1876                                                 }
1877                                                 break;
1878
1879                                         case Step.PARENT:
1880                                                 m = null;
1881                                                 if (xpc.contextNode !== xpc.virtualRoot) {
1882                                                         if (xpc.contextNode.nodeType == 2 /*Node.ATTRIBUTE_NODE*/) {
1883                                                                 m = this.getOwnerElement(xpc.contextNode);
1884                                                         } else {
1885                                                                 m = xpc.contextNode.parentNode;
1886                                                         }
1887                                                 }
1888                                                 if (m != null && step.nodeTest.matches(m, xpc)) {
1889                                                         newNodes.push(m);
1890                                                 }
1891                                                 break;
1892
1893                                         case Step.PRECEDING:
1894                                                 var st;
1895                                                 if (xpc.virtualRoot != null) {
1896                                                         st = [ xpc.virtualRoot ];
1897                                                 } else {
1898                                                         st = xpc.contextNode.nodeType == 9 /*Node.DOCUMENT_NODE*/
1899                                                                 ? [ xpc.contextNode ]
1900                                                                 : [ xpc.contextNode.ownerDocument ];
1901                                                 }
1902                                                 outer: while (st.length > 0) {
1903                                                         for (var m = st.pop(); m != null; ) {
1904                                                                 if (m == xpc.contextNode) {
1905                                                                         break outer;
1906                                                                 }
1907                                                                 if (step.nodeTest.matches(m, xpc)) {
1908                                                                         newNodes.unshift(m);
1909                                                                 }
1910                                                                 if (m.firstChild != null) {
1911                                                                         st.push(m.nextSibling);
1912                                                                         m = m.firstChild;
1913                                                                 } else {
1914                                                                         m = m.nextSibling;
1915                                                                 }
1916                                                         }
1917                                                 }
1918                                                 break;
1919
1920                                         case Step.PRECEDINGSIBLING:
1921                                                 if (xpc.contextNode === xpc.virtualRoot) {
1922                                                         break;
1923                                                 }
1924                                                 for (var m = xpc.contextNode.previousSibling; m != null; m = m.previousSibling) {
1925                                                         if (step.nodeTest.matches(m, xpc)) {
1926                                                                 newNodes.push(m);
1927                                                         }
1928                                                 }
1929                                                 break;
1930
1931                                         case Step.SELF:
1932                                                 if (step.nodeTest.matches(xpc.contextNode, xpc)) {
1933                                                         newNodes.push(xpc.contextNode);
1934                                                 }
1935                                                 break;
1936
1937                                         default:
1938                                 }
1939                         }
1940                         nodes = newNodes;
1941                         // apply each of the predicates in turn
1942                         for (var j = 0; j < step.predicates.length; j++) {
1943                                 var pred = step.predicates[j];
1944                                 var newNodes = [];
1945                                 xpc.contextSize = nodes.length;
1946                                 for (xpc.contextPosition = 1; xpc.contextPosition <= xpc.contextSize; xpc.contextPosition++) {
1947                                         xpc.contextNode = nodes[xpc.contextPosition - 1];
1948                                         if (this.predicateMatches(pred, xpc)) {
1949                                                 newNodes.push(xpc.contextNode);
1950                                         } else {
1951                                         }
1952                                 }
1953                                 nodes = newNodes;
1954                         }
1955                 }
1956         }
1957         var ns = new XNodeSet();
1958         ns.addArray(nodes);
1959         return ns;
1960 };
1961
1962 PathExpr.prototype.predicateMatches = function(pred, c) {
1963         var res = pred.evaluate(c);
1964         if (Utilities.instance_of(res, XNumber)) {
1965                 return c.contextPosition == res.numberValue();
1966         }
1967         return res.booleanValue();
1968 };
1969
1970 PathExpr.prototype.toString = function() {
1971         if (this.filter != undefined) {
1972                 var s = this.filter.toString();
1973                 if (Utilities.instance_of(this.filter, XString)) {
1974                         s = "'" + s + "'";
1975                 }
1976                 if (this.filterPredicates != undefined) {
1977                         for (var i = 0; i < this.filterPredicates.length; i++) {
1978                                 s = s + "[" + this.filterPredicates[i].toString() + "]";
1979                         }
1980                 }
1981                 if (this.locationPath != undefined) {
1982                         if (!this.locationPath.absolute) {
1983                                 s += "/";
1984                         }
1985                         s += this.locationPath.toString();
1986                 }
1987                 return s;
1988         }
1989         return this.locationPath.toString();
1990 };
1991
1992 PathExpr.prototype.getOwnerElement = function(n) {
1993         // DOM 2 has ownerElement
1994         if (n.ownerElement) {
1995                 return n.ownerElement;
1996         }
1997         // DOM 1 Internet Explorer can use selectSingleNode (ironically)
1998         try {
1999                 if (n.selectSingleNode) {
2000                         return n.selectSingleNode("..");
2001                 }
2002         } catch (e) {
2003         }
2004         // Other DOM 1 implementations must use this egregious search
2005         var doc = n.nodeType == 9 /*Node.DOCUMENT_NODE*/
2006                         ? n
2007                         : n.ownerDocument;
2008         var elts = doc.getElementsByTagName("*");
2009         for (var i = 0; i < elts.length; i++) {
2010                 var elt = elts.item(i);
2011                 var nnm = elt.attributes;
2012                 for (var j = 0; j < nnm.length; j++) {
2013                         var an = nnm.item(j);
2014                         if (an === n) {
2015                                 return elt;
2016                         }
2017                 }
2018         }
2019         return null;
2020 };
2021
2022 // LocationPath //////////////////////////////////////////////////////////////
2023
2024 LocationPath.prototype = new Object();
2025 LocationPath.prototype.constructor = LocationPath;
2026 LocationPath.superclass = Object.prototype;
2027
2028 function LocationPath(abs, steps) {
2029         if (arguments.length > 0) {
2030                 this.init(abs, steps);
2031         }
2032 }
2033
2034 LocationPath.prototype.init = function(abs, steps) {
2035         this.absolute = abs;
2036         this.steps = steps;
2037 };
2038
2039 LocationPath.prototype.toString = function() {
2040         var s;
2041         if (this.absolute) {
2042                 s = "/";
2043         } else {
2044                 s = "";
2045         }
2046         for (var i = 0; i < this.steps.length; i++) {
2047                 if (i != 0) {
2048                         s += "/";
2049                 }
2050                 s += this.steps[i].toString();
2051         }
2052         return s;
2053 };
2054
2055 // Step //////////////////////////////////////////////////////////////////////
2056
2057 Step.prototype = new Object();
2058 Step.prototype.constructor = Step;
2059 Step.superclass = Object.prototype;
2060
2061 function Step(axis, nodetest, preds) {
2062         if (arguments.length > 0) {
2063                 this.init(axis, nodetest, preds);
2064         }
2065 }
2066
2067 Step.prototype.init = function(axis, nodetest, preds) {
2068         this.axis = axis;
2069         this.nodeTest = nodetest;
2070         this.predicates = preds;
2071 };
2072
2073 Step.prototype.toString = function() {
2074         var s;
2075         switch (this.axis) {
2076                 case Step.ANCESTOR:
2077                         s = "ancestor";
2078                         break;
2079                 case Step.ANCESTORORSELF:
2080                         s = "ancestor-or-self";
2081                         break;
2082                 case Step.ATTRIBUTE:
2083                         s = "attribute";
2084                         break;
2085                 case Step.CHILD:
2086                         s = "child";
2087                         break;
2088                 case Step.DESCENDANT:
2089                         s = "descendant";
2090                         break;
2091                 case Step.DESCENDANTORSELF:
2092                         s = "descendant-or-self";
2093                         break;
2094                 case Step.FOLLOWING:
2095                         s = "following";
2096                         break;
2097                 case Step.FOLLOWINGSIBLING:
2098                         s = "following-sibling";
2099                         break;
2100                 case Step.NAMESPACE:
2101                         s = "namespace";
2102                         break;
2103                 case Step.PARENT:
2104                         s = "parent";
2105                         break;
2106                 case Step.PRECEDING:
2107                         s = "preceding";
2108                         break;
2109                 case Step.PRECEDINGSIBLING:
2110                         s = "preceding-sibling";
2111                         break;
2112                 case Step.SELF:
2113                         s = "self";
2114                         break;
2115         }
2116         s += "::";
2117         s += this.nodeTest.toString();
2118         for (var i = 0; i < this.predicates.length; i++) {
2119                 s += "[" + this.predicates[i].toString() + "]";
2120         }
2121         return s;
2122 };
2123
2124 Step.ANCESTOR = 0;
2125 Step.ANCESTORORSELF = 1;
2126 Step.ATTRIBUTE = 2;
2127 Step.CHILD = 3;
2128 Step.DESCENDANT = 4;
2129 Step.DESCENDANTORSELF = 5;
2130 Step.FOLLOWING = 6;
2131 Step.FOLLOWINGSIBLING = 7;
2132 Step.NAMESPACE = 8;
2133 Step.PARENT = 9;
2134 Step.PRECEDING = 10;
2135 Step.PRECEDINGSIBLING = 11;
2136 Step.SELF = 12;
2137
2138 // NodeTest //////////////////////////////////////////////////////////////////
2139
2140 NodeTest.prototype = new Object();
2141 NodeTest.prototype.constructor = NodeTest;
2142 NodeTest.superclass = Object.prototype;
2143
2144 function NodeTest(type, value) {
2145         if (arguments.length > 0) {
2146                 this.init(type, value);
2147         }
2148 }
2149
2150 NodeTest.prototype.init = function(type, value) {
2151         this.type = type;
2152         this.value = value;
2153 };
2154
2155 NodeTest.prototype.toString = function() {
2156         switch (this.type) {
2157                 case NodeTest.NAMETESTANY:
2158                         return "*";
2159                 case NodeTest.NAMETESTPREFIXANY:
2160                         return this.value + ":*";
2161                 case NodeTest.NAMETESTRESOLVEDANY:
2162                         return "{" + this.value + "}*";
2163                 case NodeTest.NAMETESTQNAME:
2164                         return this.value;
2165                 case NodeTest.NAMETESTRESOLVEDNAME:
2166                         return "{" + this.namespaceURI + "}" + this.value;
2167                 case NodeTest.COMMENT:
2168                         return "comment()";
2169                 case NodeTest.TEXT:
2170                         return "text()";
2171                 case NodeTest.PI:
2172                         if (this.value != undefined) {
2173                                 return "processing-instruction(\"" + this.value + "\")";
2174                         }
2175                         return "processing-instruction()";
2176                 case NodeTest.NODE:
2177                         return "node()";
2178         }
2179         return "<unknown nodetest type>";
2180 };
2181
2182 NodeTest.prototype.matches = function(n, xpc) {
2183         switch (this.type) {
2184                 case NodeTest.NAMETESTANY:
2185                         if (n.nodeType == 2 /*Node.ATTRIBUTE_NODE*/
2186                                         || n.nodeType == 1 /*Node.ELEMENT_NODE*/
2187                                         || n.nodeType == XPathNamespace.XPATH_NAMESPACE_NODE) {
2188                                 return true;
2189                         }
2190                         return false;
2191                 case NodeTest.NAMETESTPREFIXANY:
2192                         if ((n.nodeType == 2 /*Node.ATTRIBUTE_NODE*/ || n.nodeType == 1 /*Node.ELEMENT_NODE*/)) {
2193                                 var ns = xpc.namespaceResolver.getNamespace(this.value, xpc.expressionContextNode);
2194                                 if (ns == null) {
2195                                         throw new Error("Cannot resolve QName " + this.value);
2196                                 }
2197                                 return true;    
2198                         }
2199                         return false;
2200                 case NodeTest.NAMETESTQNAME:
2201                         if (n.nodeType == 2 /*Node.ATTRIBUTE_NODE*/
2202                                         || n.nodeType == 1 /*Node.ELEMENT_NODE*/
2203                                         || n.nodeType == XPathNamespace.XPATH_NAMESPACE_NODE) {
2204                                 var test = Utilities.resolveQName(this.value, xpc.namespaceResolver, xpc.expressionContextNode, false);
2205                                 if (test[0] == null) {
2206                                         throw new Error("Cannot resolve QName " + this.value);
2207                                 }
2208                                 test[0] = String(test[0]);
2209                                 test[1] = String(test[1]);
2210                                 if (test[0] == "") {
2211                                         test[0] = null;
2212                                 }
2213                                 var node = Utilities.resolveQName(n.nodeName, xpc.namespaceResolver, n, n.nodeType == 1 /*Node.ELEMENT_NODE*/);
2214                                 node[0] = String(node[0]);
2215                                 node[1] = String(node[1]);
2216                                 if (node[0] == "") {
2217                                         if (n.namespaceURI) {
2218                                                 node[0] = n.namespaceURI;
2219                                         } else {
2220                                                 node[0] = null;
2221                                         }
2222                                 }
2223                                 if (xpc.caseInsensitive) {
2224                                         return test[0] == node[0] && String(test[1]).toLowerCase() == String(node[1]).toLowerCase();
2225                                 }
2226                                 return test[0] == node[0] && test[1] == node[1];
2227                         }
2228                         return false;
2229                 case NodeTest.COMMENT:
2230                         return n.nodeType == 8 /*Node.COMMENT_NODE*/;
2231                 case NodeTest.TEXT:
2232                         return n.nodeType == 3 /*Node.TEXT_NODE*/ || n.nodeType == 4 /*Node.CDATA_SECTION_NODE*/;
2233                 case NodeTest.PI:
2234                         return n.nodeType == 7 /*Node.PROCESSING_INSTRUCTION_NODE*/
2235                                 && (this.value == null || n.nodeName == this.value);
2236                 case NodeTest.NODE:
2237                         return n.nodeType == 9 /*Node.DOCUMENT_NODE*/
2238                                 || n.nodeType == 1 /*Node.ELEMENT_NODE*/
2239                                 || n.nodeType == 2 /*Node.ATTRIBUTE_NODE*/
2240                                 || n.nodeType == 3 /*Node.TEXT_NODE*/
2241                                 || n.nodeType == 4 /*Node.CDATA_SECTION_NODE*/
2242                                 || n.nodeType == 8 /*Node.COMMENT_NODE*/
2243                                 || n.nodeType == 7 /*Node.PROCESSING_INSTRUCTION_NODE*/;
2244         }
2245         return false;
2246 };
2247
2248 NodeTest.NAMETESTANY = 0;
2249 NodeTest.NAMETESTPREFIXANY = 1;
2250 NodeTest.NAMETESTQNAME = 2;
2251 NodeTest.COMMENT = 3;
2252 NodeTest.TEXT = 4;
2253 NodeTest.PI = 5;
2254 NodeTest.NODE = 6;
2255
2256 // VariableReference /////////////////////////////////////////////////////////
2257
2258 VariableReference.prototype = new Expression();
2259 VariableReference.prototype.constructor = VariableReference;
2260 VariableReference.superclass = Expression.prototype;
2261
2262 function VariableReference(v) {
2263         if (arguments.length > 0) {
2264                 this.init(v);
2265         }
2266 }
2267
2268 VariableReference.prototype.init = function(v) {
2269         this.variable = v;
2270 };
2271
2272 VariableReference.prototype.toString = function() {
2273         return "$" + this.variable;
2274 };
2275
2276 VariableReference.prototype.evaluate = function(c) {
2277         return c.variableResolver.getVariable(this.variable, c);
2278 };
2279
2280 // FunctionCall //////////////////////////////////////////////////////////////
2281
2282 FunctionCall.prototype = new Expression();
2283 FunctionCall.prototype.constructor = FunctionCall;
2284 FunctionCall.superclass = Expression.prototype;
2285
2286 function FunctionCall(fn, args) {
2287         if (arguments.length > 0) {
2288                 this.init(fn, args);
2289         }
2290 }
2291
2292 FunctionCall.prototype.init = function(fn, args) {
2293         this.functionName = fn;
2294         this.arguments = args;
2295 };
2296
2297 FunctionCall.prototype.toString = function() {
2298         var s = this.functionName + "(";
2299         for (var i = 0; i < this.arguments.length; i++) {
2300                 if (i > 0) {
2301                         s += ", ";
2302                 }
2303                 s += this.arguments[i].toString();
2304         }
2305         return s + ")";
2306 };
2307
2308 FunctionCall.prototype.evaluate = function(c) {
2309         var f = c.functionResolver.getFunction(this.functionName, c);
2310         if (f == undefined) {
2311                 throw new Error("Unknown function " + this.functionName);
2312         }
2313         var a = [c].concat(this.arguments);
2314         return f.apply(c.functionResolver.thisArg, a);
2315 };
2316
2317 // XString ///////////////////////////////////////////////////////////////////
2318
2319 XString.prototype = new Expression();
2320 XString.prototype.constructor = XString;
2321 XString.superclass = Expression.prototype;
2322
2323 function XString(s) {
2324         if (arguments.length > 0) {
2325                 this.init(s);
2326         }
2327 }
2328
2329 XString.prototype.init = function(s) {
2330         this.str = s;
2331 };
2332
2333 XString.prototype.toString = function() {
2334         return this.str;
2335 };
2336
2337 XString.prototype.evaluate = function(c) {
2338         return this;
2339 };
2340
2341 XString.prototype.string = function() {
2342         return this;
2343 };
2344
2345 XString.prototype.number = function() {
2346         return new XNumber(this.str);
2347 };
2348
2349 XString.prototype.bool = function() {
2350         return new XBoolean(this.str);
2351 };
2352
2353 XString.prototype.nodeset = function() {
2354         throw new Error("Cannot convert string to nodeset");
2355 };
2356
2357 XString.prototype.stringValue = function() {
2358         return this.str;
2359 };
2360
2361 XString.prototype.numberValue = function() {
2362         return this.number().numberValue();
2363 };
2364
2365 XString.prototype.booleanValue = function() {
2366         return this.bool().booleanValue();
2367 };
2368
2369 XString.prototype.equals = function(r) {
2370         if (Utilities.instance_of(r, XBoolean)) {
2371                 return this.bool().equals(r);
2372         }
2373         if (Utilities.instance_of(r, XNumber)) {
2374                 return this.number().equals(r);
2375         }
2376         if (Utilities.instance_of(r, XNodeSet)) {
2377                 return r.compareWithString(this, Operators.equals);
2378         }
2379         return new XBoolean(this.str == r.str);
2380 };
2381
2382 XString.prototype.notequal = function(r) {
2383         if (Utilities.instance_of(r, XBoolean)) {
2384                 return this.bool().notequal(r);
2385         }
2386         if (Utilities.instance_of(r, XNumber)) {
2387                 return this.number().notequal(r);
2388         }
2389         if (Utilities.instance_of(r, XNodeSet)) {
2390                 return r.compareWithString(this, Operators.notequal);
2391         }
2392         return new XBoolean(this.str != r.str);
2393 };
2394
2395 XString.prototype.lessthan = function(r) {
2396         if (Utilities.instance_of(r, XNodeSet)) {
2397                 return r.compareWithNumber(this.number(), Operators.greaterthanorequal);
2398         }
2399         return this.number().lessthan(r.number());
2400 };
2401
2402 XString.prototype.greaterthan = function(r) {
2403         if (Utilities.instance_of(r, XNodeSet)) {
2404                 return r.compareWithNumber(this.number(), Operators.lessthanorequal);
2405         }
2406         return this.number().greaterthan(r.number());
2407 };
2408
2409 XString.prototype.lessthanorequal = function(r) {
2410         if (Utilities.instance_of(r, XNodeSet)) {
2411                 return r.compareWithNumber(this.number(), Operators.greaterthan);
2412         }
2413         return this.number().lessthanorequal(r.number());
2414 };
2415
2416 XString.prototype.greaterthanorequal = function(r) {
2417         if (Utilities.instance_of(r, XNodeSet)) {
2418                 return r.compareWithNumber(this.number(), Operators.lessthan);
2419         }
2420         return this.number().greaterthanorequal(r.number());
2421 };
2422
2423 // XNumber ///////////////////////////////////////////////////////////////////
2424
2425 XNumber.prototype = new Expression();
2426 XNumber.prototype.constructor = XNumber;
2427 XNumber.superclass = Expression.prototype;
2428
2429 function XNumber(n) {
2430         if (arguments.length > 0) {
2431                 this.init(n);
2432         }
2433 }
2434
2435 XNumber.prototype.init = function(n) {
2436         this.num = Number(n);
2437 };
2438
2439 XNumber.prototype.toString = function() {
2440         return this.num;
2441 };
2442
2443 XNumber.prototype.evaluate = function(c) {
2444         return this;
2445 };
2446
2447 XNumber.prototype.string = function() {
2448         return new XString(this.num);
2449 };
2450
2451 XNumber.prototype.number = function() {
2452         return this;
2453 };
2454
2455 XNumber.prototype.bool = function() {
2456         return new XBoolean(this.num);
2457 };
2458
2459 XNumber.prototype.nodeset = function() {
2460         throw new Error("Cannot convert number to nodeset");
2461 };
2462
2463 XNumber.prototype.stringValue = function() {
2464         return this.string().stringValue();
2465 };
2466
2467 XNumber.prototype.numberValue = function() {
2468         return this.num;
2469 };
2470
2471 XNumber.prototype.booleanValue = function() {
2472         return this.bool().booleanValue();
2473 };
2474
2475 XNumber.prototype.negate = function() {
2476         return new XNumber(-this.num);
2477 };
2478
2479 XNumber.prototype.equals = function(r) {
2480         if (Utilities.instance_of(r, XBoolean)) {
2481                 return this.bool().equals(r);
2482         }
2483         if (Utilities.instance_of(r, XString)) {
2484                 return this.equals(r.number());
2485         }
2486         if (Utilities.instance_of(r, XNodeSet)) {
2487                 return r.compareWithNumber(this, Operators.equals);
2488         }
2489         return new XBoolean(this.num == r.num);
2490 };
2491
2492 XNumber.prototype.notequal = function(r) {
2493         if (Utilities.instance_of(r, XBoolean)) {
2494                 return this.bool().notequal(r);
2495         }
2496         if (Utilities.instance_of(r, XString)) {
2497                 return this.notequal(r.number());
2498         }
2499         if (Utilities.instance_of(r, XNodeSet)) {
2500                 return r.compareWithNumber(this, Operators.notequal);
2501         }
2502         return new XBoolean(this.num != r.num);
2503 };
2504
2505 XNumber.prototype.lessthan = function(r) {
2506         if (Utilities.instance_of(r, XNodeSet)) {
2507                 return r.compareWithNumber(this, Operators.greaterthanorequal);
2508         }
2509         if (Utilities.instance_of(r, XBoolean) || Utilities.instance_of(r, XString)) {
2510                 return this.lessthan(r.number());
2511         }
2512         return new XBoolean(this.num < r.num);
2513 };
2514
2515 XNumber.prototype.greaterthan = function(r) {
2516         if (Utilities.instance_of(r, XNodeSet)) {
2517                 return r.compareWithNumber(this, Operators.lessthanorequal);
2518         }
2519         if (Utilities.instance_of(r, XBoolean) || Utilities.instance_of(r, XString)) {
2520                 return this.greaterthan(r.number());
2521         }
2522         return new XBoolean(this.num > r.num);
2523 };
2524
2525 XNumber.prototype.lessthanorequal = function(r) {
2526         if (Utilities.instance_of(r, XNodeSet)) {
2527                 return r.compareWithNumber(this, Operators.greaterthan);
2528         }
2529         if (Utilities.instance_of(r, XBoolean) || Utilities.instance_of(r, XString)) {
2530                 return this.lessthanorequal(r.number());
2531         }
2532         return new XBoolean(this.num <= r.num);
2533 };
2534
2535 XNumber.prototype.greaterthanorequal = function(r) {
2536         if (Utilities.instance_of(r, XNodeSet)) {
2537                 return r.compareWithNumber(this, Operators.lessthan);
2538         }
2539         if (Utilities.instance_of(r, XBoolean) || Utilities.instance_of(r, XString)) {
2540                 return this.greaterthanorequal(r.number());
2541         }
2542         return new XBoolean(this.num >= r.num);
2543 };
2544
2545 XNumber.prototype.plus = function(r) {
2546         return new XNumber(this.num + r.num);
2547 };
2548
2549 XNumber.prototype.minus = function(r) {
2550         return new XNumber(this.num - r.num);
2551 };
2552
2553 XNumber.prototype.multiply = function(r) {
2554         return new XNumber(this.num * r.num);
2555 };
2556
2557 XNumber.prototype.div = function(r) {
2558         return new XNumber(this.num / r.num);
2559 };
2560
2561 XNumber.prototype.mod = function(r) {
2562         return new XNumber(this.num % r.num);
2563 };
2564
2565 // XBoolean //////////////////////////////////////////////////////////////////
2566
2567 XBoolean.prototype = new Expression();
2568 XBoolean.prototype.constructor = XBoolean;
2569 XBoolean.superclass = Expression.prototype;
2570
2571 function XBoolean(b) {
2572         if (arguments.length > 0) {
2573                 this.init(b);
2574         }
2575 }
2576
2577 XBoolean.prototype.init = function(b) {
2578         this.b = Boolean(b);
2579 };
2580
2581 XBoolean.prototype.toString = function() {
2582         return this.b.toString();
2583 };
2584
2585 XBoolean.prototype.evaluate = function(c) {
2586         return this;
2587 };
2588
2589 XBoolean.prototype.string = function() {
2590         return new XString(this.b);
2591 };
2592
2593 XBoolean.prototype.number = function() {
2594         return new XNumber(this.b);
2595 };
2596
2597 XBoolean.prototype.bool = function() {
2598         return this;
2599 };
2600
2601 XBoolean.prototype.nodeset = function() {
2602         throw new Error("Cannot convert boolean to nodeset");
2603 };
2604
2605 XBoolean.prototype.stringValue = function() {
2606         return this.string().stringValue();
2607 };
2608
2609 XBoolean.prototype.numberValue = function() {
2610         return this.num().numberValue();
2611 };
2612
2613 XBoolean.prototype.booleanValue = function() {
2614         return this.b;
2615 };
2616
2617 XBoolean.prototype.not = function() {
2618         return new XBoolean(!this.b);
2619 };
2620
2621 XBoolean.prototype.equals = function(r) {
2622         if (Utilities.instance_of(r, XString) || Utilities.instance_of(r, XNumber)) {
2623                 return this.equals(r.bool());
2624         }
2625         if (Utilities.instance_of(r, XNodeSet)) {
2626                 return r.compareWithBoolean(this, Operators.equals);
2627         }
2628         return new XBoolean(this.b == r.b);
2629 };
2630
2631 XBoolean.prototype.notequal = function(r) {
2632         if (Utilities.instance_of(r, XString) || Utilities.instance_of(r, XNumber)) {
2633                 return this.notequal(r.bool());
2634         }
2635         if (Utilities.instance_of(r, XNodeSet)) {
2636                 return r.compareWithBoolean(this, Operators.notequal);
2637         }
2638         return new XBoolean(this.b != r.b);
2639 };
2640
2641 XBoolean.prototype.lessthan = function(r) {
2642         if (Utilities.instance_of(r, XNodeSet)) {
2643                 return r.compareWithNumber(this.number(), Operators.greaterthanorequal);
2644         }
2645         return this.number().lessthan(r.number());
2646 };
2647
2648 XBoolean.prototype.greaterthan = function(r) {
2649         if (Utilities.instance_of(r, XNodeSet)) {
2650                 return r.compareWithNumber(this.number(), Operators.lessthanorequal);
2651         }
2652         return this.number().greaterthan(r.number());
2653 };
2654
2655 XBoolean.prototype.lessthanorequal = function(r) {
2656         if (Utilities.instance_of(r, XNodeSet)) {
2657                 return r.compareWithNumber(this.number(), Operators.greaterthan);
2658         }
2659         return this.number().lessthanorequal(r.number());
2660 };
2661
2662 XBoolean.prototype.greaterthanorequal = function(r) {
2663         if (Utilities.instance_of(r, XNodeSet)) {
2664                 return r.compareWithNumber(this.number(), Operators.lessthan);
2665         }
2666         return this.number().greaterthanorequal(r.number());
2667 };
2668
2669 // AVLTree ///////////////////////////////////////////////////////////////////
2670
2671 AVLTree.prototype = new Object();
2672 AVLTree.prototype.constructor = AVLTree;
2673 AVLTree.superclass = Object.prototype;
2674
2675 function AVLTree(n) {
2676         this.init(n);
2677 }
2678
2679 AVLTree.prototype.init = function(n) {
2680         this.left = null;
2681     this.right = null;
2682         this.node = n;
2683         this.depth = 1;
2684 };
2685
2686 AVLTree.prototype.balance = function() {
2687     var ldepth = this.left  == null ? 0 : this.left.depth;
2688     var rdepth = this.right == null ? 0 : this.right.depth;
2689
2690         if (ldepth > rdepth + 1) {
2691         // LR or LL rotation
2692         var lldepth = this.left.left  == null ? 0 : this.left.left.depth;
2693         var lrdepth = this.left.right == null ? 0 : this.left.right.depth;
2694
2695         if (lldepth < lrdepth) {
2696             // LR rotation consists of a RR rotation of the left child
2697             this.left.rotateRR();
2698             // plus a LL rotation of this node, which happens anyway 
2699         }
2700         this.rotateLL();       
2701     } else if (ldepth + 1 < rdepth) {
2702         // RR or RL rorarion
2703                 var rrdepth = this.right.right == null ? 0 : this.right.right.depth;
2704                 var rldepth = this.right.left  == null ? 0 : this.right.left.depth;
2705          
2706         if (rldepth > rrdepth) {
2707             // RR rotation consists of a LL rotation of the right child
2708             this.right.rotateLL();
2709             // plus a RR rotation of this node, which happens anyway 
2710         }
2711         this.rotateRR();
2712     }        
2713 };
2714
2715 AVLTree.prototype.rotateLL = function() {
2716     // the left side is too long => rotate from the left (_not_ leftwards)
2717     var nodeBefore = this.node;
2718     var rightBefore = this.right;
2719     this.node = this.left.node;
2720     this.right = this.left;
2721     this.left = this.left.left;
2722     this.right.left = this.right.right;
2723     this.right.right = rightBefore;
2724     this.right.node = nodeBefore;
2725     this.right.updateInNewLocation();
2726     this.updateInNewLocation();
2727 };
2728
2729 AVLTree.prototype.rotateRR = function() {
2730     // the right side is too long => rotate from the right (_not_ rightwards)
2731     var nodeBefore = this.node;
2732     var leftBefore = this.left;
2733     this.node = this.right.node;
2734     this.left = this.right;
2735     this.right = this.right.right;
2736     this.left.right = this.left.left;
2737     this.left.left = leftBefore;
2738     this.left.node = nodeBefore;
2739     this.left.updateInNewLocation();
2740     this.updateInNewLocation();
2741 }; 
2742         
2743 AVLTree.prototype.updateInNewLocation = function() {
2744     this.getDepthFromChildren();
2745 };
2746
2747 AVLTree.prototype.getDepthFromChildren = function() {
2748     this.depth = this.node == null ? 0 : 1;
2749     if (this.left != null) {
2750         this.depth = this.left.depth + 1;
2751     }
2752     if (this.right != null && this.depth <= this.right.depth) {
2753         this.depth = this.right.depth + 1;
2754     }
2755 };
2756
2757 AVLTree.prototype.order = function(n1, n2) {
2758         if (n1 === n2) {
2759                 return 0;
2760         }
2761         var d1 = 0;
2762         var d2 = 0;
2763         for (var m1 = n1; m1 != null; m1 = m1.parentNode) {
2764                 d1++;
2765         }
2766         for (var m2 = n2; m2 != null; m2 = m2.parentNode) {
2767                 d2++;
2768         }
2769         if (d1 > d2) {
2770                 while (d1 > d2) {
2771                         n1 = n1.parentNode;
2772                         d1--;
2773                 }
2774                 if (n1 == n2) {
2775                         return 1;
2776                 }
2777         } else if (d2 > d1) {
2778                 while (d2 > d1) {
2779                         n2 = n2.parentNode;
2780                         d2--;
2781                 }
2782                 if (n1 == n2) {
2783                         return -1;
2784                 }
2785         }
2786         while (n1.parentNode != n2.parentNode) {
2787                 n1 = n1.parentNode;
2788                 n2 = n2.parentNode;
2789         }
2790         while (n1.previousSibling != null && n2.previousSibling != null) {
2791                 n1 = n1.previousSibling;
2792                 n2 = n2.previousSibling;
2793         }
2794         if (n1.previousSibling == null) {
2795                 return -1;
2796         }
2797         return 1;
2798 };
2799
2800 AVLTree.prototype.add = function(n)  {
2801         if (n === this.node) {
2802         return false;
2803     }
2804         
2805         var o = this.order(n, this.node);
2806         
2807     var ret = false;
2808     if (o == -1) {
2809         if (this.left == null) {
2810             this.left = new AVLTree(n);
2811             ret = true;
2812         } else {
2813             ret = this.left.add(n);
2814             if (ret) {
2815                 this.balance();
2816             }
2817         }
2818     } else if (o == 1) {
2819         if (this.right == null) {
2820             this.right = new AVLTree(n);
2821             ret = true;
2822         } else {
2823             ret = this.right.add(n);
2824             if (ret) {
2825                 this.balance();
2826             }
2827         }
2828     }
2829         
2830     if (ret) {
2831         this.getDepthFromChildren();
2832     }
2833     return ret;
2834 };
2835