src/dom/xpathparser.h

   1 #ifndef __XPATHPARSER_H__
   2 #define __XPATHPARSER_H__
   3
   4 /**
   5  * Phoebe DOM Implementation.
   6  *
   7  * This is a C++ approximation of the W3C DOM model, which follows
   8  * fairly closely the specifications in the various .idl files, copies of
   9  * which are provided for reference.  Most important is this one:
  10  *
  11  * http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/idl-definitions.html
  12  *
  13  * Authors:
  14  *   Bob Jamison
  15  *
  16  * Copyright (C) 2005 Bob Jamison
  17  *
  18  *  This library is free software; you can redistribute it and/or
  19  *  modify it under the terms of the GNU Lesser General Public
  20  *  License as published by the Free Software Foundation; either
  21  *  version 2.1 of the License, or (at your option) any later version.
  22  *
  23  *  This library is distributed in the hope that it will be useful,
  24  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  25  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  26  *  Lesser General Public License for more details.
  27  *
  28  *  You should have received a copy of the GNU Lesser General Public
  29  *  License along with this library; if not, write to the Free Software
  30  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  31  */
  32
  33
  34 #include <stdio.h>
  35 #include <stdarg.h>
  36
  37 #include <string>
  38 #include <vector>
  39
  40 #include "dom.h"
  41 #include "xpathtoken.h"
  42
  43 namespace org
  44 {
  45 namespace w3c
  46 {
  47 namespace dom
  48 {
  49 namespace xpath
  50 {
  51
  52 typedef dom::DOMString DOMString;
  53 typedef dom::Node Node;
  54 typedef dom::NodeList  NodeList;
  55
  56
  57
  58 //########################################################################
  59 //# L E X I C A L    D E F I N I T I O N S
  60 //########################################################################
  61
  62
  63 typedef struct
  64 {
  65    int   ival;
  66    char *sval;
  67 } LookupEntry;
  68
  69
  70
  71 //Note:  in the following definitions, where the starts of
  72 //strings are similar, put the longer definitions first
  73
  74 /**
  75  *
  76  */
  77 typedef enum
  78 {
  79     COMMENT,
  80     TEXT,
  81     PROCESSING_INSTRUCTION,
  82     NODE
  83 } NodeType;
  84
  85
  86 static LookupEntry nodeTypeTable [] =
  87 {
  88     {  COMMENT,                "comment"                },
  89     {  TEXT,                   "text"                   },
  90     {  PROCESSING_INSTRUCTION, "processing-instruction" },
  91     {  NODE,                   "node"                   },
  92     { -1,                      NULL                     }
  93 };
  94
  95
  96 /**
  97  *
  98  */
  99 typedef enum
 100 {
 101     ANCESTOR_OR_SELF,
 102     ANCESTOR,
 103     ATTRIBUTE,
 104     CHILD,
 105     DESCENDANT_OR_SELF,
 106     DESCENDANT,
 107     FOLLOWING_SIBLING,
 108     FOLLOWING,
 109     NAMESPACE,
 110     PARENT,
 111     PRECEDING_SIBLING,
 112     PRECEDING,
 113     SELF
 114 } AxisNameType;
 115
 116
 117 static LookupEntry axisNameTable [] =
 118 {
 119     {  ANCESTOR_OR_SELF,    "ancestor-or-self"  },
 120     {  ANCESTOR,            "ancestor"          },
 121     {  ATTRIBUTE,           "attribute"         },
 122     {  CHILD,               "child"             },
 123     {  DESCENDANT_OR_SELF,  "descendant-or-self"},
 124     {  DESCENDANT,          "descendant"        },
 125     {  FOLLOWING_SIBLING,   "following-sibling" },
 126     {  FOLLOWING,           "following"         },
 127     {  NAMESPACE,           "namespace"         },
 128     {  PARENT,              "parent"            },
 129     {  PRECEDING_SIBLING,   "preceding-sibling" },
 130     {  PRECEDING,           "preceding"         },
 131     {  SELF,                "self"              },
 132     { -1,                   NULL                }
 133 };
 134
 135
 136 /**
 137  *
 138  */
 139 typedef enum
 140 {
 141     NONE = 0,
 142     CHAR, //default if none of the below
 143     //Expr tokens
 144     LPAREN,
 145     RPAREN,
 146     LBRACKET,
 147     RBRACKET,
 148     DOUBLE_DOT,
 149     DOT,
 150     AMPR,
 151     COMMA,
 152     DOUBLE_COLON,
 153     NAME_TEST,
 154     NODE_TYPE,
 155     OPERATOR,
 156     FUNCTION_NAME,
 157     AXIS_NAME,
 158     LITERAL,
 159     NUMBER,
 160     VARIABLE_REFERENCE,
 161     //Operator tokens
 162     AND,
 163     OR,
 164     MOD,
 165     DIV,
 166     MULTIPLY,
 167     DOUBLE_SLASH,
 168     SLASH,
 169     PIPE,
 170     PLUS,
 171     MINUS,
 172     EQUALS,
 173     NOT_EQUALS,
 174     LESS_THAN_EQUALS,
 175     LESS_THAN,
 176     GREATER_THAN_EQUALS,
 177     GREATER_THAN
 178 } LexTokType;
 179
 180
 181 /*
 182 * Be VERY careful that this table matches the LexicalTokenType enum
 183 * declaration above.
 184 */
 185 static LookupEntry exprTokenTable [] =
 186 {
 187     {  NONE,                "xxNONExx"          },
 188     {  CHAR,                "CHAR"              },
 189     //Expr tokens
 190     {  LPAREN,              "("                 },
 191     {  RPAREN,              ")"                 },
 192     {  LBRACKET,            "["                 },
 193     {  RBRACKET,            "]"                 },
 194     {  DOUBLE_DOT,          ".."                },
 195     {  DOT,                 "."                 },
 196     {  AMPR,                "@"                 },
 197     {  COMMA,               ","                 },
 198     {  DOUBLE_COLON,        "::"                },
 199     {  NAME_TEST,           "NameTest"          },
 200     {  NODE_TYPE,           "NodeType"          },
 201     {  OPERATOR,            "Operator"          },
 202     {  FUNCTION_NAME,       "FunctionName"      },
 203     {  AXIS_NAME,           "AxisName"          },
 204     {  LITERAL,             "Literal"           },
 205     {  NUMBER,              "Number"            },
 206     {  VARIABLE_REFERENCE,  "VariableReference" },
 207     { -1,                   NULL                }
 208 };
 209
 210 static LookupEntry operatorTable [] =
 211 {
 212     {  NONE,                "xxNONExx"          },
 213     //Operator tokens
 214     {  AND,                 "and"               },
 215     {  OR,                  "or"                },
 216     {  MOD,                 "mod"               },
 217     {  DIV,                 "div"               },
 218     {  MULTIPLY,            "*"                 },
 219     {  DOUBLE_SLASH,        "//"                },
 220     {  SLASH,               "/"                 },
 221     {  PIPE,                "|"                 },
 222     {  PLUS,                "+"                 },
 223     {  MINUS,               "-"                 },
 224     {  EQUALS,              "="                 },
 225     {  NOT_EQUALS,          "!="                },
 226     {  LESS_THAN_EQUALS,    "<="                },
 227     {  LESS_THAN,           "<"                 },
 228     {  GREATER_THAN_EQUALS, ">="                },
 229     {  GREATER_THAN,        ">"                 },
 230     { -1,                   NULL                }
 231 };
 232
 233
 234 /**
 235  *
 236  */
 237 class LexTok
 238 {
 239 public:
 240     LexTok(const LexTok &tok)
 241         {
 242         type     = tok.type;
 243         location = tok.location;
 244         sval     = tok.sval;
 245         dval     = tok.dval;
 246         ival     = tok.ival;
 247         }
 248     LexTok()
 249         { init(); }
 250     LexTok(int theType, int loc)
 251         { init(); type = theType; location = loc;}
 252     LexTok(int theType, int loc, const DOMString &val)
 253         { init(); type = theType; location = loc; sval = val; }
 254     LexTok(int theType, int loc, double val)
 255         { init(); type = theType; location = loc; dval = val; }
 256     LexTok(int theType, int loc, long val)
 257         { init(); type = theType; location = loc; ival = val; }
 258
 259     void print()
 260         {
 261         if (type == OPERATOR)
 262             {
 263             char *tokenStr = "unknown";
 264             for (LookupEntry *entry = operatorTable; entry->sval ; entry++)
 265                 {
 266                 if (entry->ival == ival)
 267                     {
 268                     tokenStr = entry->sval;
 269                     break;
 270                     }
 271                 }
 272             printf("(%s)\n", tokenStr);
 273             }
 274         else if (type == NODE_TYPE)
 275             {
 276             char *tokenStr = "unknown";
 277             for (LookupEntry *entry = nodeTypeTable; entry->sval ; entry++)
 278                 {
 279                 if (entry->ival == ival)
 280                     {
 281                     tokenStr = entry->sval;
 282                     break;
 283                     }
 284                 }
 285             printf("{{%s}}\n", tokenStr);
 286             }
 287         else if (type == AXIS_NAME)
 288             {
 289             char *tokenStr = "unknown";
 290             for (LookupEntry *entry = axisNameTable; entry->sval ; entry++)
 291                 {
 292                 if (entry->ival == ival)
 293                     {
 294                     tokenStr = entry->sval;
 295                     break;
 296                     }
 297                 }
 298             printf("{%s}\n", tokenStr);
 299             }
 300         else if (type == CHAR)
 301             printf("'%c'\n", (char)ival);
 302         else if (type == NAME_TEST)
 303             printf("\"%s\"\n", sval.c_str());
 304         else if (type == LITERAL)
 305             printf("L'%s'\n", sval.c_str());
 306         else if (type == FUNCTION_NAME)
 307             printf("%s()\n", sval.c_str());
 308         else if (type == NUMBER)
 309             printf("#%f\n", dval);
 310         else
 311             {
 312             char *tokenStr = "unknown";
 313             for (LookupEntry *entry = exprTokenTable; entry->sval ; entry++)
 314                 {
 315                 if (entry->ival == type)
 316                     {
 317                     tokenStr = entry->sval;
 318                     break;
 319                     }
 320                 }
 321             printf("%s\n", tokenStr);
 322             //printf("%s [%s/%f/%ld]\n", tokenStr, sval.c_str(), dval, ival);
 323             }
 324         }
 325
 326     int getType()
 327         { return type; }
 328     int getLocation()
 329         { return location; }
 330     DOMString &getStringValue()
 331         { return sval; }
 332     double getDoubleValue()
 333         { return dval; }
 334     long getIntValue()
 335         { return ival; }
 336
 337 private:
 338     void  init()
 339         {
 340         type     = NONE;
 341         location = 0;
 342         dval     = 0.0;
 343         ival     = 0;
 344         }
 345
 346     int       type;
 347     int       location;
 348     DOMString sval;
 349     double    dval;
 350     long      ival;
 351 };
 352
 353
 354
 355
 356
 357 //########################################################################
 358 //# P A R S E R
 359 //########################################################################
 360
 361 class XPathParser
 362 {
 363 public:
 364
 365     //#################################
 366     //# CONSTRUCTOR
 367     //#################################
 368
 369     /**
 370      *
 371      */
 372     XPathParser()
 373         {
 374         debug = false;
 375         }
 376
 377     /**
 378      *
 379      */
 380     ~XPathParser() {}
 381
 382     /**
 383      *
 384      */
 385     bool getDebug()
 386         { return debug; }
 387
 388     /**
 389      *
 390      */
 391     void setDebug(bool val)
 392         { debug = val; }
 393
 394
 395
 396     /**
 397      *  Normally not called directly unless for string parsing testing
 398      */
 399     bool parse(const DOMString &str);
 400
 401     /**
 402      * This is the big one. Called by the xpath-dom api to fetch
 403      * nodes from a DOM tree.
 404      */
 405     NodeList evaluate(const Node *root, const DOMString &str);
 406
 407
 408
 409 private:
 410
 411     //#################################
 412     //# MESSAGES
 413     //#################################
 414
 415     /**
 416      *
 417      */
 418     void trace(const char *fmt, ...);
 419
 420     /**
 421      *
 422      */
 423     void traceStack(const char *name, int pos, int depth);
 424
 425     /**
 426      *
 427      */
 428     void error(const char *fmt, ...);
 429
 430     //#################################
 431     //# LEXICAL  SCANNING
 432     //#################################
 433
 434     /**
 435      *  Add a lexical token of a given type to the list
 436      */
 437     void lexTokAdd(int type, int loc);
 438     void lexTokAdd(int type, int loc, const DOMString &val);
 439     void lexTokAdd(int type, int loc, double val);
 440     void lexTokAdd(int type, int loc, long   val);
 441
 442     /**
 443      *
 444      */
 445     void lexicalTokenDump();
 446
 447     /**
 448      *
 449      */
 450     LexTok lexTok(int p);
 451
 452     /**
 453      *
 454      */
 455     int lexTokType(int p);
 456
 457     /**
 458      *
 459      */
 460     int peek(int p);
 461
 462     /**
 463      *
 464      */
 465     int get(int p);
 466
 467     /**
 468      *
 469      */
 470     int getword(int p, DOMString &str);
 471
 472     /**
 473      *
 474      */
 475     int match(int p, const char *str);
 476
 477     /**
 478      *
 479      */
 480     int skipwhite(int p);
 481
 482     /**
 483      *
 484      */
 485     int getNumber(int p, double &dresult);
 486
 487     /**
 488      *
 489      */
 490     int getLiteral(int p, DOMString &result);
 491
 492     /**
 493      *
 494      */
 495     int getNameTest(int p0, DOMString &result);
 496
 497     /**
 498      *
 499      */
 500     int getNCName(int p0, DOMString &result);
 501
 502
 503
 504
 505     /**
 506      *
 507      */
 508     int lexicalScan();
 509
 510
 511     //#################################
 512     //# GRAMMAR  PARSING
 513     //#################################
 514
 515     /**
 516      * Add a newly derived token to the token list;
 517      */
 518     void tokAdd(Token *token);
 519
 520     /**
 521      * The grammar definitions marked [1]-[39] are directly
 522      * from the W3C XPath grammar spacification.
 523      */
 524
 525     /**
 526      * [1]
 527      */
 528     int getLocationPath(int p0, int depth);
 529
 530     /**
 531      * [2]
 532      */
 533     int getAbsoluteLocationPath(int p0, int depth);
 534
 535     /**
 536      * [3]
 537      */
 538     int getRelativeLocationPath(int p0, int depth);
 539
 540     /**
 541      * [4]
 542      */
 543     int getStep(int p0, int depth);
 544
 545     /**
 546      * [5]
 547      */
 548     int getAxisSpecifier(int p0, int depth);
 549
 550     /**
 551      * [6]
 552      */
 553     int getAxisName(int p0, int depth);
 554
 555     /**
 556      * [7]
 557      */
 558     int getNodeTest(int p0, int depth);
 559
 560     /**
 561      * [8]
 562      */
 563     int getPredicate(int p0, int depth);
 564
 565     /**
 566      * [9]
 567      */
 568     int getPredicateExpr(int p0, int depth);
 569
 570     /**
 571      * [10]
 572      */
 573     int getAbbreviatedAbsoluteLocationPath(int p0, int depth);
 574     /**
 575      * [11]
 576      */
 577     int getAbbreviatedRelativeLocationPath(int p0, int depth);
 578     /**
 579      * [12]
 580      */
 581     int getAbbreviatedStep(int p0, int depth);
 582
 583     /**
 584      * [13]
 585      */
 586     int getAbbreviatedAxisSpecifier(int p0, int depth);
 587
 588     /**
 589      * [14]
 590      */
 591     int getExpr(int p0, int depth);
 592
 593     /**
 594      * [15]
 595      */
 596     int getPrimaryExpr(int p0, int depth);
 597
 598     /**
 599      * [16]
 600      */
 601     int getFunctionCall(int p0, int depth);
 602
 603     /**
 604      * [17]
 605      */
 606     int getArgument(int p0, int depth);
 607
 608     /**
 609      * [18]
 610      */
 611     int getUnionExpr(int p0, int depth);
 612
 613     /**
 614      * [19]
 615      */
 616     int getPathExpr(int p0, int depth);
 617
 618     /**
 619      * [20]
 620      */
 621     int getFilterExpr(int p0, int depth);
 622
 623     /**
 624      * [21]
 625      */
 626     int getOrExpr(int p0, int depth);
 627
 628     /**
 629      * [22]
 630      */
 631     int getAndExpr(int p0, int depth);
 632
 633     /**
 634      * [23]
 635      */
 636     int getEqualityExpr(int p0, int depth);
 637
 638     /**
 639      * [24]
 640      */
 641     int getRelationalExpr(int p0, int depth);
 642
 643     /**
 644      * [25]
 645      */
 646     int getAdditiveExpr(int p0, int depth);
 647
 648     /**
 649      * [26]
 650      */
 651     int getMultiplicativeExpr(int p0, int depth);
 652
 653     /**
 654      * [27]
 655      */
 656     int getUnaryExpr(int p0, int depth);
 657
 658     /**
 659      * [28]
 660      */
 661     int getExprToken(int p0, int depth);
 662
 663     /**
 664      * [29]
 665      */
 666     int getLiteral(int p0, int depth);
 667
 668     /**
 669      * [30]
 670      */
 671     int getNumber(int p0, int depth);
 672
 673     /**
 674      * [31]
 675      */
 676     int getDigits(int p0, int depth);
 677
 678     /**
 679      * [32]
 680      */
 681     int getOperator(int p0, int depth);
 682
 683     /**
 684      * [33]
 685      */
 686     int getOperatorName(int p0, int depth);
 687
 688     /**
 689      * [34]
 690      */
 691     int getMultiplyOperator(int p0, int depth);
 692
 693     /**
 694      * [35]
 695      */
 696     int getFunctionName(int p0, int depth);
 697
 698     /**
 699      * [36]
 700      */
 701     int getVariableReference(int p0, int depth);
 702
 703     /**
 704      * [37]
 705      */
 706     int getNameTest(int p0, int depth);
 707
 708     /**
 709      * [38]
 710      */
 711     int getNodeType(int p0, int depth);
 712
 713     /**
 714      * [39]
 715      */
 716     int getExprWhitespace(int p0, int depth);
 717
 718
 719
 720     //#################################
 721     //# DATA ITEMS
 722     //#################################
 723
 724     /**
 725      *
 726      */
 727     bool debug;
 728
 729     /**
 730      *
 731      */
 732     char *parsebuf;
 733
 734     /**
 735      *
 736      */
 737     int parselen;
 738
 739     /**
 740      *
 741      */
 742     int position;
 743
 744     /**
 745      *
 746      */
 747     DOMString numberString;
 748
 749     /**
 750      *
 751      */
 752     double number;
 753
 754
 755     /**
 756      *  The result of the first lexical scan
 757      */
 758     std::vector<LexTok> lexicalTokens;
 759
 760     /**
 761      *  The result of parsing.  If parsing was successful, then
 762      *  this is executable via execute()
 763      */
 764     TokenList tokens;
 765
 766
 767
 768
 769 };
 770
 771
 772
 773
 774
 775
 776 } // namespace xpath
 777 } // namespace dom
 778 } // namespace w3c
 779 } // namespace org
 780 #endif /* __XPATHPARSER_H__ */
 781 //#########################################################################
 782 //# E N D    O F    F I L E
 783 //#########################################################################
 784
 785
 786
 787
 788
 789
 790
 791