src/dom/xpathparser.cpp

   1 /**
   2  * Phoebe DOM Implementation.
   3  *
   4  * This is a C++ approximation of the W3C DOM model, which follows
   5  * fairly closely the specifications in the various .idl files, copies of
   6  * which are provided for reference.  Most important is this one:
   7  *
   8  * http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/idl-definitions.html
   9  *
  10  * Authors:
  11  *   Bob Jamison
  12  *
  13  * Copyright (C) 2006-2007 Bob Jamison
  14  *
  15  *  This library is free software; you can redistribute it and/or
  16  *  modify it under the terms of the GNU Lesser General Public
  17  *  License as published by the Free Software Foundation; either
  18  *  version 2.1 of the License, or (at your option) any later version.
  19  *
  20  *  This library is distributed in the hope that it will be useful,
  21  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  22  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  23  *  Lesser General Public License for more details.
  24  *
  25  *  You should have received a copy of the GNU Lesser General Public
  26  *  License along with this library; if not, write to the Free Software
  27  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  28  */
  29
  30
  31 #include "ucd.h"
  32 #include "xpathparser.h"
  33
  34
  35 namespace org
  36 {
  37 namespace w3c
  38 {
  39 namespace dom
  40 {
  41 namespace xpath
  42 {
  43
  44
  45 //#########################################################################
  46 //# M E S S A G E S
  47 //#########################################################################
  48
  49
  50
  51 void XPathParser::trace(const char *fmt, ...)
  52 {
  53     if (!debug)
  54         return;
  55
  56     FILE *f = stdout;
  57
  58     va_list args;
  59     va_start(args, fmt);
  60     fprintf(f, "XPathParser: ");
  61     vfprintf(f, fmt, args);
  62     fprintf(f, "\n");
  63     va_end(args);
  64 }
  65
  66
  67
  68 void XPathParser::error(const char *fmt, ...)
  69 {
  70     FILE *f = stdout;
  71     va_list args;
  72     va_start(args, fmt);
  73     fprintf(f, "XPathParser ERROR: ");
  74     vfprintf(f, fmt, args);
  75     fprintf(f, "\n");
  76     va_end(args);
  77
  78     //Print location in string
  79     fprintf(f, "%s\n", parsebuf);
  80     for (int i=0 ; i<position ; i++)
  81         fprintf(f, " ");
  82     fprintf(f, "^\n");
  83 }
  84
  85
  86
  87 void XPathParser::traceStack(const char *name, int pos, int depth)
  88 {
  89     if (!debug)
  90         return;
  91     return;
  92     int indent = depth;
  93
  94     for (int i=0 ; i<indent ; i++)
  95         fprintf(stdout, " ");
  96     fprintf(stdout, "%d %d %s\n", pos, depth, name);
  97
  98 }
  99
 100
 101 //#########################################################################
 102 //# L E X I C A L    S C A N N I N G
 103 //#########################################################################
 104
 105 void XPathParser::lexTokAdd(int type, int loc)
 106 {
 107     LexTok tok(type, loc);
 108     lexicalTokens.push_back(tok);
 109 }
 110
 111 void XPathParser::lexTokAdd(int type, int loc, const DOMString &val)
 112 {
 113     LexTok tok(type, loc, val);
 114     lexicalTokens.push_back(tok);
 115 }
 116
 117 void XPathParser::lexTokAdd(int type, int loc, double val)
 118 {
 119     LexTok tok(type, loc, val);
 120     lexicalTokens.push_back(tok);
 121 }
 122
 123 void XPathParser::lexTokAdd(int type, int loc, long   val)
 124 {
 125     LexTok tok(type, loc, val);
 126     lexicalTokens.push_back(tok);
 127 }
 128
 129 void XPathParser::lexicalTokenDump()
 130 {
 131     printf("####### LEXICAL TOKENS #######\n");
 132     for (unsigned int i=0 ; i<lexicalTokens.size() ; i++)
 133         {
 134         printf("%d : ", i);
 135         lexicalTokens[i].print();
 136         }
 137     printf("##### END LEXICAL TOKENS #####\n\n");
 138 }
 139
 140
 141
 142 LexTok XPathParser::lexTok(int p)
 143 {
 144     if (p < 0 || p>=(int)lexicalTokens.size())
 145         {
 146         LexTok tok;
 147         return tok;
 148         }
 149     return lexicalTokens[p];
 150 }
 151
 152 int XPathParser::lexTokType(int p)
 153 {
 154     if (p < 0 || p>=(int)lexicalTokens.size())
 155         return -1;
 156     return lexicalTokens[p].getType();
 157 }
 158
 159
 160
 161
 162
 163
 164
 165
 166 int XPathParser::peek(int p)
 167 {
 168     if (p >= parselen)
 169         return -1;
 170     position = p;
 171     return parsebuf[p] ;
 172 }
 173
 174
 175 int XPathParser::get(int p)
 176 {
 177     if (p >= parselen)
 178         return -1;
 179     position = p;
 180     return parsebuf[p];
 181 }
 182
 183 int XPathParser::skipwhite(int p0)
 184 {
 185     int p = p0;
 186
 187     while (p < parselen)
 188         {
 189         int ch = peek(p);
 190         if (!uni_is_space(ch))
 191             break;
 192         ch = get(p++);
 193         }
 194     return p;
 195 }
 196
 197 int XPathParser::getword(int p0, DOMString &str)
 198 {
 199     int p = p0;
 200     while (p < parselen)
 201         {
 202         int ch = peek(p);
 203         if (!uni_is_letter_or_digit(ch))
 204             break;
 205         ch = get(p++);
 206         str.push_back((XMLCh)ch);
 207         }
 208     return p;
 209 }
 210
 211 int XPathParser::match(int p, const char *str)
 212 {
 213     while (*str)
 214         {
 215         if (p >= parselen)
 216             return -1;
 217         if (parsebuf[p] != *str)
 218             return -1;
 219         p++; str++;
 220         }
 221     return p;
 222 }
 223
 224
 225
 226
 227 int XPathParser::getNumber(int p0, double &dresult)
 228 {
 229     int p = p0;
 230     if (p >= parselen)
 231         return p0;/*need at least x*/
 232
 233     bool isdouble = false;
 234     bool negative = false;
 235
 236     int ch = parsebuf[p];
 237     if (ch=='-')
 238         {
 239         p++;
 240         negative = true;
 241         if (p >= parselen) return p0;
 242         }
 243
 244     bool seen_dot    = false;
 245     bool seen_e      = false;
 246     bool seen_eminus = false;
 247
 248     DOMString num;
 249
 250     int i = p;
 251     while (i < parselen)
 252         {
 253         ch = parsebuf[i];
 254         if (ch=='.')
 255             {
 256             if (seen_dot)
 257                 return p0;
 258             seen_dot = true;
 259             isdouble = true;
 260             }
 261         else if (ch=='e' || ch=='E')
 262             {
 263             if (seen_e || !seen_dot)
 264                 return p0;
 265             seen_e = true;
 266             }
 267         else if (ch=='-' && seen_e)
 268             {
 269             if (seen_eminus || !seen_dot)
 270                 return p0;
 271             seen_eminus = true;
 272             }
 273         else if (!uni_is_digit(ch))
 274             break;
 275         num.push_back((XMLCh)ch);
 276         i++;
 277         }
 278
 279     if (i == p)/*no digits*/
 280         return p0;
 281     if (isdouble)
 282         {
 283         const char *begin = num.c_str();
 284         char *end;
 285         dresult = strtod(begin,&end);
 286         if (!end)/*not a number?*/
 287             {
 288             error("Error formatting double: %s\n", num.c_str());
 289             return p0;
 290             }
 291         }
 292     else
 293         {
 294         const char *begin = num.c_str();
 295         char *end;
 296         dresult = (double)strtol(begin,&end,10);
 297         if (!end)/*not a number?*/
 298             {
 299             error("Error formatting integer: %s\n", num.c_str());
 300             return p0;
 301             }
 302         }
 303     p = i;
 304     return p;
 305 }
 306
 307
 308
 309 int XPathParser::getLiteral(int p0, DOMString &result)
 310 {
 311     int p = p0;
 312     int ch = peek(p);
 313     int quotechar = 0;
 314     if (ch == '"' || ch == '\'')
 315         {
 316         quotechar = ch;
 317         }
 318     else
 319         return p0;
 320     p++;
 321     while (true)
 322         {
 323         if (p >= parselen)
 324             {
 325             error("Unterminated literal string");
 326             return -1;
 327             }
 328         ch = peek(p);
 329         if (ch == quotechar)
 330             break;
 331         result.push_back((XMLCh)ch);
 332         p++;
 333         }
 334     p++; //skip over closing "
 335     return p;
 336 }
 337
 338
 339
 340 /**
 341  * NCName is a 'non-colonized' name
 342  */
 343 int XPathParser::getNCName(int p0, DOMString &result)
 344 {
 345     int p = p0;
 346     int ch = peek(p);
 347     if (ch != '_' && !uni_is_letter(ch))
 348         return p0;
 349
 350     result.push_back((XMLCh)ch);
 351     p++;
 352     while (p < parselen)
 353         {
 354         ch = peek(p);
 355         if (   uni_is_letter_or_digit(ch) ||
 356                // isCombiningChar(ch) ||
 357                // isExtender(ch)      ||
 358                ch == '.' || ch == '-' || ch == '_' )
 359            {
 360            result.push_back((XMLCh)ch);
 361            p++;
 362            }
 363        else
 364            break;
 365        }
 366     return p;
 367 }
 368
 369
 370
 371 /**
 372  * Name parsing with post-parsing
 373  */
 374 int XPathParser::getNameTest(int p0, DOMString &result)
 375 {
 376     int p = p0;
 377     int ch = peek(p);
 378     if (ch == '*')
 379         {
 380         result.push_back((XMLCh)ch);
 381         p++;
 382         return p;
 383         }
 384
 385     DOMString ncName;
 386     int p2 = getNCName(p, ncName);
 387     if (p2 <= p)
 388         return p0;
 389
 390     result = ncName;
 391     p = p2;
 392
 393     ch = peek(p);
 394     if (ch != ':' )//short name. we are done
 395         {
 396         return p;
 397         }
 398
 399      if (peek(p+1) == ':')  //was  name::  which is ok
 400         return p;
 401
 402     result.push_back(':');
 403
 404     p++;
 405     ch = peek(p);
 406     if (ch == '*')
 407         {
 408         result.push_back((XMLCh)ch);
 409         p++;
 410         return p;
 411         }
 412
 413     DOMString ncName2;
 414     p2 = getNCName(p, ncName2);
 415     if (p2 <= p)
 416         {
 417         if (peek(p) == ':')  //was  name::  which is ok
 418             return p0;
 419         error("Nothing after ':' in QName");
 420         return -1;
 421         }
 422
 423     result.append(ncName2);
 424
 425     p = p2;
 426
 427     return p;
 428 }
 429
 430
 431
 432 int XPathParser::lexicalScan()
 433 {
 434     lexicalTokens.clear();
 435
 436     int p  = 0;
 437     int p2 = p;
 438
 439     while (p < parselen)
 440         {
 441         p2 = skipwhite(p);
 442         p = p2;
 443
 444         //trace("nextChar:%c", peek(p));
 445         bool selected = false;
 446
 447         //### LITERAL EXPR TOKENS
 448         for (int i=2 ; i<=10 ; i++)
 449             {
 450             p2 = match(p, exprTokenTable[i].sval);
 451             if (p2 > p)
 452                 {
 453                 lexTokAdd(exprTokenTable[i].ival, p);
 454                 p = p2;
 455                 selected = true;
 456                 break;
 457                 }
 458             }
 459         if (selected)
 460             continue;
 461
 462         //### OPERATORS
 463         for (LookupEntry *entry = operatorTable; entry->sval ; entry++)
 464             {
 465             p2 = match(p, entry->sval);
 466             if (p2 > p)
 467                 {
 468                 long op = (long)entry->ival;
 469                 //according to the disambiguating rule for * in the spec
 470                 if (op == MULTIPLY && lexicalTokens.size() > 0)
 471                     {
 472                     int ltyp = lexTokType(lexicalTokens.size()-1);
 473                     if (ltyp != AMPR   && ltyp != DOUBLE_COLON &&
 474                         ltyp != LPAREN && ltyp != RBRACKET     &&
 475                         ltyp != COMMA  && ltyp != OPERATOR        )
 476                         {
 477                         lexTokAdd(OPERATOR, p, (long)entry->ival);
 478                         p = p2;
 479                         selected = true;
 480                         break;
 481                         }
 482                     }
 483                 else
 484                     {
 485                     lexTokAdd(OPERATOR, p, (long)entry->ival);
 486                     p = p2;
 487                     selected = true;
 488                     break;
 489                     }
 490                 }
 491             }
 492         if (selected)
 493             continue;
 494
 495         //### NODE TYPES
 496         for (LookupEntry *entry = nodeTypeTable; entry->sval ; entry++)
 497             {
 498             p2 = match(p, entry->sval);
 499             if (p2 > p)
 500                 {
 501                 lexTokAdd(NODE_TYPE, p, (long)entry->ival);
 502                 p = p2;
 503                 selected = true;
 504                 break;
 505                 }
 506             }
 507         if (selected)
 508             continue;
 509
 510         //### AXIS NAMES
 511         for (LookupEntry *entry = axisNameTable; entry->sval ; entry++)
 512             {
 513             p2 = match(p, entry->sval);
 514             if (p2 > p)
 515                 {
 516                 lexTokAdd(AXIS_NAME, p, (long)entry->ival);
 517                 p = p2;
 518                 selected = true;
 519                 break;
 520                 }
 521             }
 522         if (selected)
 523             continue;
 524
 525         //### NAME TEST
 526         DOMString ntResult;
 527         p2 = getNameTest(p, ntResult);
 528         if (p2 > p)
 529             {
 530             int p3 = skipwhite(p2);
 531             if (peek(p3) == '(')
 532                 lexTokAdd(FUNCTION_NAME, p, ntResult);
 533             else
 534                 lexTokAdd(NAME_TEST, p, ntResult);
 535             p = p2;
 536             selected = true;
 537             }
 538         if (selected)
 539             continue;
 540
 541         //### VARIABLE REFERENCE
 542         if (peek(p) == '$')
 543             {
 544             p++;
 545             DOMString qnResult;
 546             p2 = getNCName(p, qnResult);
 547             if (p2 > p)
 548                 {
 549                 lexTokAdd(VARIABLE_REFERENCE, p, qnResult);
 550                 p = p2;
 551                 selected = true;
 552                 }
 553             else
 554                 {
 555                 error("Variable referenced with '$' requires a qualified name\n");
 556                 return -1;
 557                 }
 558             }
 559         if (selected)
 560             continue;
 561
 562         //### NUMBER
 563         double numval;
 564         p2 = getNumber(p, numval);
 565         if (p2 > p)
 566             {
 567             lexTokAdd(NUMBER, p, numval);
 568             p = p2;
 569             selected = true;
 570             }
 571         if (selected)
 572             continue;
 573
 574         //### LITERAL
 575         DOMString strval;
 576         p2 = getLiteral(p, strval);
 577         if (p2 > p)
 578             {
 579             lexTokAdd(LITERAL, p, strval);
 580             p = p2;
 581             selected = true;
 582             }
 583         if (selected)
 584             continue;
 585
 586         //### CHAR  (default, none of the above)
 587         lexTokAdd(CHAR, p, (long) peek(p));
 588         p++;
 589
 590         }//while p
 591
 592
 593     return p;
 594 }
 595
 596
 597
 598
 599
 600
 601
 602
 603
 604
 605
 606
 607
 608
 609
 610
 611
 612
 613
 614
 615
 616
 617 //#########################################################################
 618 //# X P A T H    G R A M M A R    P A R S I N G
 619 //#########################################################################
 620
 621 //## Various shorthand methods to add a token to the list
 622 void XPathParser::tokAdd(const Token &tok)
 623 {
 624     tokens.add(tok);
 625 }
 626
 627 void XPathParser::tokAdd(int type)
 628 {
 629     tokens.add(Token::create(type));
 630 }
 631
 632 void XPathParser::tokAdd(int type, long val)
 633 {
 634     tokens.add(Token::create(type, val));
 635 }
 636
 637 void XPathParser::tokAdd(int type, double val)
 638 {
 639     tokens.add(Token::create(type, val));
 640 }
 641
 642 void XPathParser::tokAdd(int type, const DOMString &val)
 643 {
 644     tokens.add(Token::create(type, val));
 645 }
 646
 647
 648
 649
 650
 651 //########################################
 652 //# Grammar - specific parsing
 653 //########################################
 654
 655 /**
 656  * [1]  LocationPath ::=
 657  *        RelativeLocationPath
 658  *        | AbsoluteLocationPath
 659  */
 660 int XPathParser::getLocationPath(int p0, int depth)
 661 {
 662     traceStack("getLocationPath", p0, depth);
 663     int p = p0;
 664
 665     p = skipwhite(p);
 666
 667     int p2 = getAbsoluteLocationPath(p, depth+1);
 668     if (p2 > p)
 669         {
 670         tokAdd(Token::TOK_ABSOLUTE);
 671         return p2;
 672         }
 673
 674     p2 = getRelativeLocationPath(p, depth+1);
 675     if (p2 > p)
 676         {
 677         tokAdd(Token::TOK_RELATIVE);
 678         return p2;
 679         }
 680
 681     return p0;
 682 }
 683
 684
 685 /**
 686  * [2]  AbsoluteLocationPath ::=
 687  *        '/' RelativeLocationPath?
 688  *         | AbbreviatedAbsoluteLocationPath
 689  */
 690 int XPathParser::getAbsoluteLocationPath(int p0, int depth)
 691 {
 692     traceStack("getAbsoluteLocationPath", p0, depth);
 693
 694     int p = p0;
 695     LexTok t = lexTok(p);
 696     if (t.getType() == OPERATOR && t.getIntValue()==SLASH)
 697         {
 698         p++;
 699         int p2 = getRelativeLocationPath(p, depth+1);
 700         if (p2 <= p)
 701             {
 702             error("Relative path after '/'");
 703             return -1;
 704             }
 705         p = p2;
 706         return p;
 707         }
 708
 709     //AbbreviatedAbsoluteLocationPath
 710     if (t.getType() == OPERATOR && t.getIntValue()==DOUBLE_SLASH)
 711         {
 712         p++;
 713         int p2 = getRelativeLocationPath(p, depth+1);
 714         if (p2 <= p)
 715             {
 716             error("Relative path after '//'");
 717             return -1;
 718             }
 719         p = p2;
 720         return p;
 721         }
 722
 723
 724     return p0;
 725 }
 726
 727
 728 /**
 729  * [3] RelativeLocationPath ::=
 730  *       Step
 731  *       | RelativeLocationPath '/' Step
 732  *       | AbbreviatedRelativeLocationPath
 733  */
 734 int XPathParser::getRelativeLocationPath(int p0, int depth)
 735 {
 736     traceStack("getRelativeLocationPath", p0, depth);
 737     int p = p0;
 738     int p2 = getStep(p, depth+1);
 739     if (p2 < 0)
 740         return -1;
 741     if (p2 > p)
 742         {
 743         p = p2;
 744         LexTok t = lexTok(p);
 745         if (t.getType() == OPERATOR && t.getIntValue()==SLASH)
 746             {
 747             p++;
 748             p2 = getRelativeLocationPath(p, depth+1);
 749             if (p2 < 0)
 750                 {
 751                 error("Relative path after '/'");
 752                 return -1;
 753                 }
 754             p = p2;
 755             return p;
 756             }
 757         //AbbreviatedRelativeLocationPath
 758         if (t.getType() == OPERATOR && t.getIntValue()==DOUBLE_SLASH)
 759             {
 760             p++;
 761             // a '//' is an abbreviation for /descendant-or-self:node()/
 762             tokAdd(Token::TOK_AXIS_DESCENDANT_OR_SELF);
 763             p2 = getRelativeLocationPath(p, depth+1);
 764             if (p2 < 0)
 765                 {
 766                 error("Relative path after '//'");
 767                 return -1;
 768                 }
 769             p = p2;
 770             return p;
 771             }
 772         return p;
 773         }
 774
 775
 776     return p0;
 777 }
 778
 779
 780 /**
 781  * [4] Step ::=
 782  *       AxisSpecifier NodeTest Predicate*
 783  *       | AbbreviatedStep
 784  */
 785 int XPathParser::getStep(int p0, int depth)
 786 {
 787     traceStack("getStep", p0, depth);
 788
 789     int p = p0;
 790
 791     lexTok(p).print();
 792
 793     //This can be (and usually is) 0-length
 794     int p2 = getAxisSpecifier(p, depth+1);
 795     if (p2 < 0)
 796         {
 797         error("Axis specifier in step section");
 798         return -1;
 799         }
 800     p = p2;
 801     p2 = getNodeTest(p, depth+1);
 802     if (p2 < 0)
 803         {
 804         error("Node test in step section");
 805         return -1;
 806         }
 807
 808     if (p2 > p)
 809         {
 810         p = p2;
 811         p2 = getPredicate(p, depth+1);
 812         if (p2 < 0)
 813             {
 814             error("Predicate in step section");
 815             return -1;
 816             }
 817         p = p2;
 818         return p;
 819         }
 820
 821     //AbbreviatedStep
 822     if (lexTokType(p) == DOT)
 823         {
 824         p++;
 825         return p;
 826         }
 827
 828     //AbbreviatedStep
 829     if (lexTokType(p) == DOUBLE_DOT)
 830         {
 831         p++;
 832         return p;
 833         }
 834
 835     return p0;
 836 }
 837
 838
 839 /**
 840  * [5] AxisSpecifier ::=
 841  *         AxisName '::'
 842  *         | AbbreviatedAxisSpecifier
 843  */
 844 int XPathParser::getAxisSpecifier(int p0, int depth)
 845 {
 846     traceStack("getAxisSpecifier", p0, depth);
 847     int p = p0;
 848     if (lexTokType(p) == AXIS_NAME)
 849         {
 850         LexTok t = lexTok(p);
 851         int axisType = t.getIntValue();
 852         p++;
 853         if (lexTokType(p) != DOUBLE_COLON)
 854             {
 855             error("'::' required after axis name literal");
 856             return -1;
 857             }
 858         p++;
 859         switch (axisType)
 860             {
 861             case ANCESTOR_OR_SELF:
 862                 tokAdd(Token::TOK_AXIS_ANCESTOR_OR_SELF);
 863                 break;
 864             case ANCESTOR:
 865                 tokAdd(Token::TOK_AXIS_ANCESTOR);
 866                 break;
 867             case ATTRIBUTE:
 868                 tokAdd(Token::TOK_AXIS_ATTRIBUTE);
 869                 break;
 870             case CHILD:
 871                 tokAdd(Token::TOK_AXIS_CHILD);
 872                 break;
 873             case DESCENDANT_OR_SELF:
 874                 tokAdd(Token::TOK_AXIS_DESCENDANT_OR_SELF);
 875                 break;
 876             case DESCENDANT:
 877                 tokAdd(Token::TOK_AXIS_DESCENDANT);
 878                 break;
 879             case FOLLOWING_SIBLING:
 880                 tokAdd(Token::TOK_AXIS_FOLLOWING_SIBLING);
 881                 break;
 882             case FOLLOWING:
 883                 tokAdd(Token::TOK_AXIS_FOLLOWING);
 884                 break;
 885             case NAMESPACE:
 886                 tokAdd(Token::TOK_AXIS_NAMESPACE);
 887                 break;
 888             case PARENT:
 889                 tokAdd(Token::TOK_AXIS_PARENT);
 890                 break;
 891             case PRECEDING_SIBLING:
 892                 tokAdd(Token::TOK_AXIS_PRECEDING_SIBLING);
 893                 break;
 894             case PRECEDING:
 895                 tokAdd(Token::TOK_AXIS_PRECEDING);
 896                 break;
 897             case SELF:
 898                 tokAdd(Token::TOK_AXIS_SELF);
 899                 break;
 900             default:
 901                 {
 902                 error("unknown axis type %d", axisType);
 903                 return -1;
 904                 }
 905             }
 906         return p;
 907         }
 908
 909     //AbbreviatedAxisSpecifier
 910     if (lexTokType(p) == AMPR)
 911         {
 912         p++;
 913         return p;
 914         }
 915
 916     return p0;
 917 }
 918
 919
 920 /**
 921  * [6]  AxisName ::=
 922  *         'ancestor'
 923  *         | 'ancestor-or-self'
 924  *         | 'attribute'
 925  *         | 'child'
 926  *         | 'descendant'
 927  *         | 'descendant-or-self'
 928  *         | 'following'
 929  *         | 'following-sibling'
 930  *         | 'namespace'
 931  *         | 'parent'
 932  *         | 'preceding'
 933  *         | 'preceding-sibling'
 934  *         | 'self'
 935  * NOTE: This definition, and those at the bottom, is not
 936  *   needed.  Its functionality is handled by lexical scanning.
 937  *   It is left here for reference.
 938  */
 939 int XPathParser::getAxisName(int p0, int depth)
 940 {
 941     traceStack("getAxisName", p0, depth);
 942     return p0;
 943 }
 944
 945
 946 /**
 947  * [7] NodeTest ::=
 948  *       NameTest
 949  *       | NodeType '(' ')'
 950  *       | 'processing-instruction' '(' Literal ')'
 951  */
 952 int XPathParser::getNodeTest(int p0, int depth)
 953 {
 954     traceStack("getNodeTest", p0, depth);
 955     int p = p0;
 956
 957     LexTok t = lexTok(p);
 958     if (t.getType() == NAME_TEST)
 959         {
 960         p++;
 961         tokAdd(Token::TOK_NAME_TEST, t.getStringValue());
 962         return p;
 963         }
 964     if (t.getType() == NODE_TYPE)
 965         {
 966         if (t.getIntValue() == PROCESSING_INSTRUCTION)
 967             {
 968             if (lexTokType(p)   != LPAREN   ||
 969                 lexTokType(p+1) != LITERAL  ||
 970                 lexTokType(p+2) != RPAREN   )
 971                 {
 972                 error("processing instruction requires (\"literal string\")");
 973                 return -1;
 974                 }
 975             p += 3;
 976             }
 977         else
 978             {
 979             if (lexTokType(p+1) != LPAREN ||
 980                 lexTokType(p+2) != RPAREN )
 981                 {
 982                 error("processing instruction requires ()");
 983                 return -1;
 984                 }
 985             p += 2;
 986             }
 987         return p;
 988         }
 989
 990     return p0;
 991 }
 992
 993
 994 /**
 995  * [8]  Predicate ::=
 996  *         '[' PredicateExpr ']'
 997  */
 998 int XPathParser::getPredicate(int p0, int depth)
 999 {
1000     traceStack("getPredicate", p0, depth);
1001
1002     int p = p0;
1003     if (lexTokType(p) != LBRACKET)
1004         return p0;
1005
1006     p++;
1007     int p2 = getPredicateExpr(p, depth+1);
1008     if (p2 <= p)
1009         {
1010         error("Predicate expression in predicate");
1011         return -1;
1012         }
1013
1014     p = p2;
1015     lexTok(p).print();
1016     if (lexTokType(p) != RBRACKET)
1017         {
1018         error("Predicate expression requires closing ']'");
1019         return -1;
1020         }
1021     p++;
1022     return p;
1023 }
1024
1025
1026 /**
1027  * [9]  PredicateExpr ::=
1028  *         Expr
1029  */
1030 int XPathParser::getPredicateExpr(int p0, int depth)
1031 {
1032     traceStack("getPredicateExpr", p0, depth);
1033     int p = p0;
1034     int p2 = getExpr(p, depth+1);
1035     if (p2 < 0)
1036         {
1037         error("Expression in predicate expression");
1038         return -1;
1039         }
1040     p = p2;
1041     return p;
1042 }
1043
1044
1045 /**
1046  * [10] AbbreviatedAbsoluteLocationPath ::=
1047  *        '//' RelativeLocationPath
1048  * NOTE: not used. handled in getAbsoluteLocationPath()
1049  */
1050 int XPathParser::getAbbreviatedAbsoluteLocationPath(int p0, int depth)
1051 {
1052     traceStack("getAbbreviatedAbsoluteLocationPath", p0, depth);
1053
1054      return p0;
1055 }
1056
1057 /**
1058  * [11] AbbreviatedRelativeLocationPath ::=
1059  *         RelativeLocationPath '//' Step
1060  * NOTE: not used. handled in getRelativeLocationPath()
1061  */
1062 int XPathParser::getAbbreviatedRelativeLocationPath(int p0, int depth)
1063 {
1064     traceStack("getAbbreviatedRelativeLocationPath", p0, depth);
1065     return p0;
1066 }
1067
1068 /**
1069  * [12]  AbbreviatedStep ::=
1070  *           '.'
1071  *           | '..'
1072  * NOTE: not used. handled in getStep()
1073  */
1074 int XPathParser::getAbbreviatedStep(int p0, int depth)
1075 {
1076     traceStack("getAbbreviatedStep", p0, depth);
1077     return p0;
1078 }
1079
1080
1081 /**
1082  * [13] AbbreviatedAxisSpecifier ::=
1083  *        '@'?
1084  * NOTE: not used. handled in getAxisSpecifier()
1085  */
1086 int XPathParser::getAbbreviatedAxisSpecifier(int p0, int depth)
1087 {
1088     traceStack("getAbbreviatedAxisSpecifier", p0, depth);
1089     return p0;
1090 }
1091
1092
1093 /**
1094  * [14] Expr ::=
1095  *         OrExpr
1096  */
1097 int XPathParser::getExpr(int p0, int depth)
1098 {
1099     traceStack("getExpr", p0, depth);
1100
1101     int p = p0;
1102
1103     int p2 = getOrExpr(p, depth+1);
1104     if (p2 < 0)
1105         {
1106         error("OR expression in expression");
1107         return -1;
1108         }
1109     p = p2;
1110
1111     return p;
1112 }
1113
1114
1115 /**
1116  * [15]  PrimaryExpr ::=
1117  *          VariableReference
1118  *          | '(' Expr ')'
1119  *          | Literal
1120  *          | Number
1121  *          | FunctionCall
1122  */
1123 int XPathParser::getPrimaryExpr(int p0, int depth)
1124 {
1125     traceStack("getPrimaryExpr", p0, depth);
1126     int p = p0;
1127     int p2 = p;
1128
1129     if (lexTokType(p) == VARIABLE_REFERENCE)
1130         {
1131         p++;
1132         return p;
1133         }
1134
1135     if (lexTokType(p) == LPAREN)
1136         {
1137         p++;
1138         p2 = getExpr(p, depth+1);
1139         if (p2 <= p)
1140             {
1141             error("Expression in primary expression");
1142             return -1;
1143             }
1144         p += p2;
1145         if (lexTokType(p) != RPAREN)
1146             {
1147             error("Primary expression requires closing ')'");
1148             return -1;
1149             }
1150         }
1151
1152     if (lexTokType(p) == LITERAL)
1153         {
1154         tokAdd(Token::TOK_STR, lexTok(p).getStringValue());
1155         p++;
1156         return p;
1157         }
1158
1159     if (lexTokType(p) == NUMBER)
1160         {
1161         tokAdd(Token::TOK_FLOAT, lexTok(p).getDoubleValue());
1162         p++;
1163         return p;
1164         }
1165
1166     p2 = getFunctionCall(p, depth+1);
1167     if (p2 < 0)
1168         {
1169         error("Function call in primary expression");
1170         return -1;
1171         }
1172     if (p2 > p)
1173         {
1174         p = p2;
1175         return p;
1176         }
1177
1178     return p0;
1179 }
1180
1181
1182 /**
1183  * [16] FunctionCall ::=
1184  *         FunctionName '(' ( Argument ( ',' Argument )* )? ')'
1185  */
1186 int XPathParser::getFunctionCall(int p0, int depth)
1187 {
1188     traceStack("getFunctionCall", p0, depth);
1189     int p = p0;
1190
1191     if (lexTokType(p) != FUNCTION_NAME)
1192         return p0;
1193
1194     DOMString name = lexTok(p).getStringValue();
1195
1196     p++;
1197
1198     if (lexTokType(p) != LPAREN) //this makes a function
1199         return p0;
1200     p++;
1201
1202     int argCount = 0;
1203
1204     int p2 = getArgument(p, depth+1);
1205     if (p2 < 0)
1206         {
1207         error("Error in function argument");
1208         return -1;
1209         }
1210     if (p2 > p)
1211         {
1212         argCount++;
1213         p = p2;
1214         while (lexTokType(p) == COMMA)
1215             {
1216             p++;
1217             p2 = getArgument(p, depth+1);
1218             if (p2 <= p)
1219                 {
1220                 error("Error in function argument");
1221                 return -1;
1222                 }
1223             if (p2 > p)
1224                 argCount++;
1225             //do we add a token here?  i dont think so
1226             p = p2;
1227             }
1228         }
1229
1230     if (lexTokType(p) != RPAREN) //mandatory
1231         {
1232         error("Function requires closing ')'");
1233         return -1;
1234         }
1235     p++;
1236
1237     // Function names from http://www.w3.org/TR/xpath#NT-FunctionName
1238     if (name == "last")
1239         tokAdd(Token::TOK_FUNC_LAST);
1240     else if (name == "position")
1241         tokAdd(Token::TOK_FUNC_POSITION);
1242     else if (name == "count")
1243         tokAdd(Token::TOK_FUNC_COUNT);
1244     else if (name == "id")
1245         tokAdd(Token::TOK_FUNC_ID);
1246     else if (name == "local-name")
1247         tokAdd(Token::TOK_FUNC_LOCAL_NAME);
1248     else if (name == "namespace-uri")
1249         tokAdd(Token::TOK_FUNC_NAMESPACE_URI);
1250     else if (name == "name")
1251         tokAdd(Token::TOK_FUNC_NAME);
1252     else if (name == "string")
1253         tokAdd(Token::TOK_FUNC_STRING);
1254     else if (name == "concat")
1255         tokAdd(Token::TOK_FUNC_CONCAT);
1256     else if (name == "starts-with")
1257         tokAdd(Token::TOK_FUNC_STARTS_WITH);
1258     else if (name == "contains")
1259         tokAdd(Token::TOK_FUNC_CONTAINS);
1260     else if (name == "substring-before")
1261         tokAdd(Token::TOK_FUNC_SUBSTRING_BEFORE);
1262     else if (name == "substring-after")
1263         tokAdd(Token::TOK_FUNC_SUBSTRING_AFTER);
1264     else if (name == "substring")
1265         tokAdd(Token::TOK_FUNC_SUBSTRING);
1266     else if (name == "string-length")
1267         tokAdd(Token::TOK_FUNC_STRING_LENGTH);
1268     else if (name == "normalize-space")
1269         tokAdd(Token::TOK_FUNC_NORMALIZE_SPACE);
1270     else if (name == "translate")
1271         tokAdd(Token::TOK_FUNC_TRANSLATE);
1272     else if (name == "boolean")
1273         tokAdd(Token::TOK_FUNC_BOOLEAN);
1274     else if (name == "not")
1275         tokAdd(Token::TOK_FUNC_NOT);
1276     else if (name == "true")
1277         tokAdd(Token::TOK_FUNC_TRUE);
1278     else if (name == "false")
1279         tokAdd(Token::TOK_FUNC_FALSE);
1280     else if (name == "lang")
1281         tokAdd(Token::TOK_FUNC_LANG);
1282     else if (name == "number")
1283         tokAdd(Token::TOK_FUNC_NUMBER);
1284     else if (name == "sum")
1285         tokAdd(Token::TOK_FUNC_SUM);
1286     else if (name == "floor")
1287         tokAdd(Token::TOK_FUNC_FLOOR);
1288     else if (name == "ceiling")
1289         tokAdd(Token::TOK_FUNC_CEILING);
1290     else if (name == "round")
1291         tokAdd(Token::TOK_FUNC_ROUND);
1292     else
1293         {
1294         error("unknown function name:'%s'", name.c_str());
1295         return -1;
1296         }
1297     return p;
1298 }
1299
1300
1301 /**
1302  * [17] Argument ::=
1303  *         Expr
1304  */
1305 int XPathParser::getArgument(int p0, int depth)
1306 {
1307     traceStack("getArgument", p0, depth);
1308     int p = p0;
1309     int p2 = getExpr(p, depth+1);
1310     if (p2 < 0)
1311         {
1312         error("Argument expression");
1313         return -1;
1314         }
1315     p = p2;
1316     return p;
1317 }
1318
1319
1320 /**
1321  * [18]  UnionExpr ::=
1322  *           PathExpr
1323  *           | UnionExpr '|' PathExpr
1324  */
1325 int XPathParser::getUnionExpr(int p0, int depth)
1326 {
1327     traceStack("getUnionExpr", p0, depth);
1328     int p = p0;
1329     int p2 = getPathExpr(p, depth+1);
1330     if (p2 < 0)
1331         {
1332         error("Path expression for union");
1333         return -1;
1334         }
1335     p = p2;
1336     LexTok t = lexTok(p);
1337     if (t.getType() == OPERATOR && t.getIntValue() == PIPE)
1338         {
1339         p++;
1340         p2 = getUnionExpr(p, depth+1);
1341         if (p2 < 0)
1342             {
1343             error("OR (|) requires union expression on the left");
1344             return -1;
1345             }
1346         tokAdd(Token::TOK_UNION);
1347         p = p2;
1348         }
1349     return p;
1350 }
1351
1352
1353 /**
1354  * [19]  PathExpr ::=
1355  *          LocationPath
1356  *          | FilterExpr
1357  *          | FilterExpr '/' RelativeLocationPath
1358  *          | FilterExpr '//' RelativeLocationPath
1359  */
1360 int XPathParser::getPathExpr(int p0, int depth)
1361 {
1362     traceStack("getPathExpr", p0, depth);
1363     int p = p0;
1364     int p2;
1365
1366     p2 = getLocationPath(p, depth+1);
1367     if (p2 < 0)
1368         {
1369         error("Location path in path expression");
1370         return -1;
1371         }
1372     if (p2 > p)
1373         {
1374         p = p2;
1375         return p;
1376         }
1377
1378     p2 = getFilterExpr(p, depth+1);
1379     if (p2 < 0)
1380         {
1381         error("Filter expression in path expression");
1382         return -1;
1383         }
1384     if (p2 <= p)
1385         return p0;
1386     p = p2;
1387
1388     LexTok t = lexTok(p);
1389     if (t.getType() == OPERATOR && t.getIntValue() == SLASH)
1390         {
1391         p++;
1392         p2 = getRelativeLocationPath(p, depth+1);
1393         if (p2 < 0)
1394             {
1395             error("Relative location after / in path expression");
1396             return -1;
1397             }
1398         p = p2;
1399         return p;
1400         }
1401
1402     if (t.getType() == OPERATOR && t.getIntValue() == DOUBLE_SLASH)
1403         {
1404         p++;
1405         p2 = getRelativeLocationPath(p, depth+1);
1406         if (p2 < 0)
1407             {
1408             error("Relative location after // in path expression");
1409             return -1;
1410             }
1411         p = p2;
1412         return p;
1413         }
1414     return p;
1415 }
1416
1417
1418 /**
1419  * [20] FilterExpr ::=
1420  *         PrimaryExpr
1421  *         | FilterExpr Predicate
1422  */
1423 int XPathParser::getFilterExpr(int p0, int depth)
1424 {
1425     traceStack("getFilterExpr", p0, depth);
1426     int p = p0;
1427
1428     int p2 = getPrimaryExpr(p, depth+1);
1429     if (p2 < 0)
1430         {
1431         error("Primary expression in path expression");
1432         return -1;
1433         }
1434     if (p2 > p)
1435         {
1436         p = p2;
1437         while (true)
1438             {
1439             p2 = getPredicate(p, depth+1);
1440             if (p2 < 0)
1441                 {
1442                 error("Predicate in primary expression");
1443                 return -1;
1444                 }
1445             if (p2 > p)
1446                 {
1447                 p = p2;
1448                 }
1449             else
1450                 break;
1451            }
1452         return p;
1453         }
1454
1455     return p0;
1456 }
1457
1458
1459 /**
1460  * [21]  OrExpr ::=
1461  *           AndExpr
1462  *           | OrExpr 'or' AndExpr
1463  */
1464 int XPathParser::getOrExpr(int p0, int depth)
1465 {
1466     traceStack("getOrExpr", p0, depth);
1467     int p = p0;
1468     int p2 = getAndExpr(p, depth+1);
1469     if (p2 < 0)
1470         {
1471         error("AND expression in OR expression");
1472         return -1;
1473         }
1474     if (p2 > p)
1475         {
1476         p = p2;
1477         LexTok t = lexTok(p);
1478         if (t.getType() == OPERATOR && t.getIntValue() == OR)
1479             {
1480             p++;
1481             p2 = getAndExpr(p, depth+1);
1482             if (p2 <= p)
1483                 {
1484                 error("AND expression in OR expression");
1485                 return -1;
1486                 }
1487             p = p2;
1488             return p;
1489             }
1490         tokAdd(Token::TOK_OR);
1491         return p;
1492         }
1493
1494     return p0;
1495 }
1496
1497
1498 /**
1499  * [22] AndExpr ::=
1500  *         EqualityExpr
1501  *         | AndExpr 'and' EqualityExpr
1502  */
1503 int XPathParser::getAndExpr(int p0, int depth)
1504 {
1505     traceStack("getAndExpr", p0, depth);
1506     int p = p0;
1507     int p2 = getEqualityExpr(p, depth+1);
1508     if (p2 < 0)
1509         {
1510         error("Equality expression in AND expression");
1511         return -1;
1512         }
1513     if (p2 > p)
1514         {
1515         p = p2;
1516         LexTok t = lexTok(p);
1517         if (t.getType() == OPERATOR && t.getIntValue() == AND)
1518             {
1519             p++;
1520             p2 = getAndExpr(p, depth+1);
1521             if (p2 <= p)
1522                 {
1523                 error("AND expression after 'and'");
1524                 return -1;
1525                 }
1526             p = p2;
1527             return p;
1528             }
1529         tokAdd(Token::TOK_AND);
1530         return p;
1531         }
1532
1533     return p0;
1534 }
1535
1536
1537 /**
1538  * [23]  EqualityExpr ::=
1539  *           RelationalExpr
1540  *           | EqualityExpr '=' RelationalExpr
1541  *           | EqualityExpr '!=' RelationalExpr
1542  */
1543 int XPathParser::getEqualityExpr(int p0, int depth)
1544 {
1545     traceStack("getEqualityExpr", p0, depth);
1546     int p = p0;
1547     int p2 = getRelationalExpr(p, depth+1);
1548     if (p2 < 0)
1549         {
1550         error("Relation expression in equality expression");
1551         return -1;
1552         }
1553     if (p2 > p)
1554         {
1555         p = p2;
1556         LexTok t = lexTok(p);
1557         if (t.getType() == OPERATOR && t.getIntValue() == EQUALS)
1558             {
1559             p++;
1560             p2 = getEqualityExpr(p, depth+1);
1561             if (p2 <= p)
1562                 {
1563                 error("Equality expression expected after ==");
1564                 return -1;
1565                 }
1566             tokAdd(Token::TOK_EQUALS);
1567             p = p2;
1568             return p;
1569             }
1570
1571         if (t.getType() == OPERATOR && t.getIntValue() == NOT_EQUALS)
1572             {
1573             p++;
1574             p2 = getEqualityExpr(p, depth+1);
1575             if (p2 <= p)
1576                 {
1577                 error("Equality expression expected after !=");
1578                 return -1;
1579                 }
1580             tokAdd(Token::TOK_NOT_EQUALS);
1581             p = p2;
1582             return p;
1583             }
1584
1585         return p;
1586         }
1587
1588     return p0;
1589 }
1590
1591
1592 /**
1593  * [24] RelationalExpr ::=
1594  *         AdditiveExpr
1595  *         | RelationalExpr '<' AdditiveExpr
1596  *         | RelationalExpr '>' AdditiveExpr
1597  *         | RelationalExpr '<=' AdditiveExpr
1598  *         | RelationalExpr '>=' AdditiveExpr
1599  */
1600 int XPathParser::getRelationalExpr(int p0, int depth)
1601 {
1602     traceStack("getRelationalExpr", p0, depth);
1603     int p = p0;
1604     int p2 = getAdditiveExpr(p, depth+1);
1605     if (p2 < 0)
1606         {
1607         error("Additive expression in relational expression");
1608         return -1;
1609         }
1610     if (p2 > p)
1611         {
1612         p = p2;
1613         LexTok t = lexTok(p);
1614
1615         if (t.getType() == OPERATOR && t.getIntValue() == GREATER_THAN)
1616             {
1617             p++;
1618             p2 = getRelationalExpr(p, depth+1);
1619             if (p2 <= p)
1620                 {
1621                 error("Relational expression after '>'");
1622                 return -1;
1623                 }
1624             tokAdd(Token::TOK_GREATER_THAN);
1625             p = p2;
1626             return p;
1627             }
1628         if (t.getType() == OPERATOR && t.getIntValue() == LESS_THAN)
1629             {
1630             p++;
1631             p2 = getRelationalExpr(p, depth+1);
1632             if (p2 <= p)
1633                 {
1634                 error("Relational expression after '<'");
1635                 return -1;
1636                 }
1637             tokAdd(Token::TOK_LESS_THAN);
1638             p = p2;
1639             return p;
1640             }
1641         if (t.getType() == OPERATOR && t.getIntValue() == GREATER_THAN_EQUALS)
1642             {
1643             p++;
1644             p2 = getRelationalExpr(p, depth+1);
1645             if (p2 <= p)
1646                 {
1647                 error("Relational expression after '>='");
1648                 return -1;
1649                 }
1650             tokAdd(Token::TOK_GREATER_THAN_EQUALS);
1651             p = p2;
1652             return p;
1653             }
1654         if (t.getType() == OPERATOR && t.getIntValue() == LESS_THAN_EQUALS)
1655             {
1656             p++;
1657             p2 = getRelationalExpr(p, depth+1);
1658             if (p2 <= p)
1659                 {
1660                 error("Relational expression after '<='");
1661                 return -1;
1662                 }
1663             tokAdd(Token::TOK_LESS_THAN_EQUALS);
1664             p = p2;
1665             return p;
1666             }
1667
1668
1669         return p;
1670         }
1671
1672     return p0;
1673 }
1674
1675
1676 /**
1677  * [25]  AdditiveExp ::=
1678  *           MultiplicativeExpr
1679  *           | AdditiveExpr '+' MultiplicativeExpr
1680  *           | AdditiveExpr '-' MultiplicativeExpr
1681  */
1682 int XPathParser::getAdditiveExpr(int p0, int depth)
1683 {
1684     traceStack("getAdditiveExpr", p0, depth);
1685     int p = p0;
1686     int p2 = getMultiplicativeExpr(p, depth+1);
1687     if (p2 < 0)
1688         {
1689         error("Multiplicative expression in additive expression");
1690         return -1;
1691         }
1692     if (p2 > p)
1693         {
1694         p = p2;
1695         LexTok t = lexTok(p);
1696
1697         if (t.getType() == OPERATOR && t.getIntValue() == PLUS)
1698             {
1699             p++;
1700             p2 = getAdditiveExpr(p, depth+1);
1701             if (p2 <= p)
1702                 {
1703                 error("Additive expression after '+'");
1704                 return -1;
1705                 }
1706             tokAdd(Token::TOK_MINUS);
1707             p = p2;
1708             return p;
1709             }
1710         if (t.getType() == OPERATOR && t.getIntValue() == MINUS)
1711             {
1712             p++;
1713             p2 = getAdditiveExpr(p, depth+1);
1714             if (p2 <= p)
1715                 {
1716                 error("Additive expression after '-'");
1717                 return -1;
1718                 }
1719             tokAdd(Token::TOK_MINUS);
1720             p = p2;
1721             return p;
1722             }
1723
1724
1725         return p;
1726         }
1727
1728     return p0;
1729 }
1730
1731
1732 /**
1733  * [26]  MultiplicativeExpr ::=
1734  *          UnaryExpr
1735  *          | MultiplicativeExpr MultiplyOperator UnaryExpr
1736  *          | MultiplicativeExpr 'div' UnaryExpr
1737  *          | MultiplicativeExpr 'mod' UnaryExpr
1738  */
1739 int XPathParser::getMultiplicativeExpr(int p0, int depth)
1740 {
1741     traceStack("getMultiplicativeExpr", p0, depth);
1742     int p = p0;
1743     int p2 = getUnaryExpr(p, depth+1);
1744     if (p2 < 0)
1745         {
1746         error("Unary expression in multiplicative expression");
1747         return -1;
1748         }
1749     if (p2 > p)
1750         {
1751         p = p2;
1752         LexTok t = lexTok(p);
1753
1754         if (t.getType() == OPERATOR && t.getIntValue() == MULTIPLY)
1755             {
1756             p++;
1757             p2 = getMultiplicativeExpr(p, depth+1);
1758             if (p2 <= p)
1759                 {
1760                 error("Multiplicative expression after '*'");
1761                 return -1;
1762                 }
1763             tokAdd(Token::TOK_MUL);
1764             p = p2;
1765             return p;
1766             }
1767
1768         if (t.getType() == OPERATOR && t.getIntValue() == DIV)
1769             {
1770             p++;
1771             p2 = getMultiplicativeExpr(p, depth+1);
1772             if (p2 <= p)
1773                 {
1774                 error("Multiplicative expression after 'div'");
1775                 return -1;
1776                 }
1777             tokAdd(Token::TOK_DIV);
1778             p = p2;
1779             return p;
1780             }
1781
1782         if (t.getType() == OPERATOR && t.getIntValue() == MOD)
1783             {
1784             p++;
1785             p2 = getMultiplicativeExpr(p, depth+1);
1786             if (p2 <= p)
1787                 {
1788                 error("Multiplicative expression after 'mod'");
1789                 return -1;
1790                 }
1791             tokAdd(Token::TOK_MOD);
1792             p = p2;
1793             return p;
1794             }
1795
1796
1797         return p;
1798         }
1799
1800     return p0;
1801 }
1802
1803
1804 /**
1805  * [27]  UnaryExpr ::=
1806  *          UnionExpr
1807  *          | '-' UnaryExpr
1808  */
1809 int XPathParser::getUnaryExpr(int p0, int depth)
1810 {
1811     traceStack("getUnaryExpr", p0, depth);
1812     int p = p0;
1813     int p2 = getUnionExpr(p, depth+1);
1814     if (p2 < 0)
1815         {
1816         error("Union expression in unary expression");
1817         return -1;
1818         }
1819     if (p2 > p)
1820         {
1821         p = p2;
1822         return p;
1823         }
1824
1825     if (lexTokType(p) == '-')
1826         {
1827         p++;
1828         p2 = getUnaryExpr(p, depth+1);
1829         if (p2 < 0)
1830             {
1831             error("Unary expression after '-'");
1832             return -1;
1833             }
1834             tokAdd(Token::TOK_NEG);
1835         p = p2;
1836         return p;
1837         }
1838
1839     return p0;
1840 }
1841
1842
1843 //######################################################
1844 //# NOT USED!!!
1845 //## The grammar definitions below are
1846 //## handled by lexical parsing, and will not be used
1847 //######################################################
1848
1849 /**
1850  * [28] ExprToken ::=
1851  *         '(' | ')' | '[' | ']' | '.' | '..' | '@' | ',' | '::'
1852  *         | NameTest
1853  *         | NodeType
1854  *         | Operator
1855  *         | FunctionName
1856  *         | AxisName
1857  *         | Literal
1858  *         | Number
1859  *         | VariableReference
1860  */
1861 int XPathParser::getExprToken(int p0, int depth)
1862 {
1863     traceStack("getExprToken", p0, depth);
1864     return p0;
1865 }
1866
1867
1868 /**
1869  * [29]  Literal ::=
1870  *           '"' [^"]* '"'
1871  *           | "'" [^']* "'"
1872  */
1873 int XPathParser::getLiteral(int p0, int depth)
1874 {
1875     traceStack("getLiteral", p0, depth);
1876     return p0;
1877 }
1878
1879
1880 /**
1881  * [30] Number ::=
1882  *        Digits ('.' Digits?)?
1883  *        | '.' Digits
1884  */
1885 int XPathParser::getNumber(int p0, int depth)
1886 {
1887     traceStack("getNumber", p0, depth);
1888     return p0;
1889 }
1890
1891
1892 /**
1893  * [31] Digits ::=
1894  *         [0-9]+
1895  */
1896 int XPathParser::getDigits(int p0, int depth)
1897 {
1898     traceStack("getDigits", p0, depth);
1899     return p0;
1900 }
1901
1902
1903 /**
1904  * [32] Operator ::=
1905  *         OperatorName
1906  *         | MultiplyOperator
1907  *         | '/' | '//' | '|' | '+' | '-' | '='
1908  *         | '!=' | '<' | '<=' | '>' | '>='
1909  */
1910 int XPathParser::getOperator(int p0, int depth)
1911 {
1912     traceStack("getOperator", p0, depth);
1913     return p0;
1914 }
1915
1916
1917 /**
1918  * [33]  OperatorName ::=
1919  *          'and' | 'or' | 'mod' | 'div'
1920  */
1921 int XPathParser::getOperatorName(int p0, int depth)
1922 {
1923     traceStack("getOperatorName", p0, depth);
1924     return p0;
1925 }
1926
1927
1928 /**
1929  * [34] MultiplyOperator ::=
1930  *          '*'
1931  */
1932 int XPathParser::getMultiplyOperator(int p0, int depth)
1933 {
1934     traceStack("getMultiplyOperator", p0, depth);
1935     return p0;
1936 }
1937
1938
1939 /**
1940  * [35] FunctionName ::=
1941  *          QName - NodeType
1942  */
1943 int XPathParser::getFunctionName(int p0, int depth)
1944 {
1945     traceStack("getFunctionName", p0, depth);
1946     return p0;
1947 }
1948
1949
1950 /**
1951  * [36] VariableReference ::=
1952  *          '$' QName
1953  */
1954 int XPathParser::getVariableReference(int p0, int depth)
1955 {
1956     traceStack("getVariableReference", p0, depth);
1957     return p0;
1958 }
1959
1960
1961 /**
1962  * [37] NameTest ::=
1963  *         '*'
1964  *         | NCName ':' '*'
1965  *         | QName
1966  */
1967 int XPathParser::getNameTest(int p0, int depth)
1968 {
1969     traceStack("getNameTest", p0, depth);
1970     return p0;
1971 }
1972
1973
1974 /**
1975  * [38] NodeType ::=
1976  *         'comment'
1977  *         | 'text'
1978  *         | 'processing-instruction'
1979  *         | 'node'
1980  */
1981 int XPathParser::getNodeType(int p0, int depth)
1982 {
1983     traceStack("getNodeType", p0, depth);
1984     return p0;
1985 }
1986
1987
1988 /**
1989  * [39] ExprWhitespace ::=
1990  *           S
1991  */
1992 int XPathParser::getExprWhitespace(int p0, int depth)
1993 {
1994     traceStack("getExprWhitespace", p0, depth);
1995     return p0;
1996 }
1997
1998
1999
2000
2001
2002 //#########################################################################
2003 //# H I G H    L E V E L    P A R S I N G
2004 //#########################################################################
2005
2006 /**
2007  * Parse a candidate XPath string.  Leave a copy in 'tokens.'
2008  */
2009 bool XPathParser::parse(const DOMString &xpathString)
2010 {
2011     int p0 = 0;
2012
2013     DOMString str = xpathString;
2014
2015     parsebuf = (char *)str.c_str();
2016     parselen = (int)   str.size();
2017     position = 0;
2018
2019     trace("## parsing string: '%s'", parsebuf);
2020
2021     lexicalScan();
2022     lexicalTokenDump();
2023
2024     tokens.clear();//Get ready to store new tokens
2025
2026     int p = getLocationPath(p0, 0);
2027
2028     parsebuf = NULL;
2029     parselen = 0;
2030
2031     if (p <= p0)
2032         {
2033         //return false;
2034         }
2035
2036     return true;
2037 }
2038
2039
2040
2041
2042
2043 //#########################################################################
2044 //# E V A L U A T E
2045 //#########################################################################
2046
2047
2048
2049
2050 /**
2051  * This wraps the two-step call to parse(), then execute() to get a NodeList
2052  * of matching DOM nodes
2053  */
2054 NodeList XPathParser::evaluate(const NodePtr root,
2055                                const DOMString &xpathString)
2056 {
2057     NodeList list;
2058
2059     //### Maybe do caching for speed here
2060
2061     //### Parse and execute
2062     //### Error message can be generated as a side effect
2063     if (!parse(xpathString))
2064         return list;
2065
2066     if (debug)
2067         tokens.dump();
2068
2069     //### Execute the token list
2070     TokenExecutor executor;
2071     NodeList results;
2072     if (!executor.execute(tokens, root, results))
2073         {
2074         //error
2075         }
2076
2077     return results;
2078 }
2079
2080
2081
2082 } // namespace xpath
2083 } // namespace dom
2084 } // namespace w3c
2085 } // namespace org
2086 //#########################################################################
2087 //# E N D    O F    F I L E
2088 //#########################################################################
2089
2090
2091
2092