mcs/class/referencesource/System.Xml/System/Xml/XPath/Internal/XPathParser.cs

   1 //------------------------------------------------------------------------------
   2 // <copyright file="XPathParser.cs" company="Microsoft">
   3 //     Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 // <owner current="true" primary="true">[....]</owner>
   6 //------------------------------------------------------------------------------
   7
   8 namespace MS.Internal.Xml.XPath {
   9     using System;
  10     using System.Xml;
  11     using System.Xml.XPath;
  12     using System.Diagnostics;
  13     using System.Globalization;
  14     using System.Runtime.InteropServices;
  15     using System.Collections;
  16
  17     internal class XPathParser {
  18         XPathScanner scanner;
  19
  20                 private XPathParser(XPathScanner scanner) {
  21             this.scanner = scanner;
  22                 }
  23
  24                 public static AstNode ParseXPathExpresion(string xpathExpresion) {
  25                         XPathScanner scanner = new XPathScanner(xpathExpresion);
  26                         XPathParser  parser  = new XPathParser(scanner);
  27             AstNode result = parser.ParseExpresion(null);
  28             if (scanner.Kind != XPathScanner.LexKind.Eof) {
  29                 throw XPathException.Create(Res.Xp_InvalidToken, scanner.SourceText);
  30             }
  31                         return result;
  32                 }
  33
  34                 public static AstNode ParseXPathPattern(string xpathPattern) {
  35                         XPathScanner scanner = new XPathScanner(xpathPattern);
  36                         XPathParser  parser  = new XPathParser(scanner);
  37             AstNode result = parser.ParsePattern(null);
  38             if (scanner.Kind != XPathScanner.LexKind.Eof) {
  39                 throw XPathException.Create(Res.Xp_InvalidToken, scanner.SourceText);
  40             }
  41                         return result;
  42                 }
  43
  44         // --------------- Expresion Parsing ----------------------
  45
  46
  47         //The recursive is like
  48         //ParseOrExpr->ParseAndExpr->ParseEqualityExpr->ParseRelationalExpr...->ParseFilterExpr->ParsePredicate->ParseExpresion
  49         //So put 200 limitation here will max cause about 2000~3000 depth stack.
  50         private int parseDepth = 0;
  51         private const int MaxParseDepth = 200;
  52
  53         private AstNode ParseExpresion(AstNode qyInput) {
  54             if (++parseDepth > MaxParseDepth) {
  55                 throw XPathException.Create(Res.Xp_QueryTooComplex);
  56             }
  57             AstNode result = ParseOrExpr(qyInput);
  58             --parseDepth;
  59             return result;
  60         }
  61
  62         //>> OrExpr ::= ( OrExpr 'or' )? AndExpr
  63         private AstNode ParseOrExpr(AstNode qyInput) {
  64             AstNode opnd = ParseAndExpr(qyInput);
  65
  66             do {
  67                 if (! TestOp("or")) {
  68                     return opnd;
  69                 }
  70                 NextLex();
  71                 opnd = new Operator(Operator.Op.OR, opnd, ParseAndExpr(qyInput));
  72             }while (true);
  73         }
  74
  75         //>> AndExpr ::= ( AndExpr 'and' )? EqualityExpr
  76         private AstNode ParseAndExpr(AstNode qyInput) {
  77             AstNode opnd = ParseEqualityExpr(qyInput);
  78
  79             do {
  80                 if (! TestOp("and")) {
  81                     return opnd;
  82                 }
  83                 NextLex();
  84                 opnd = new Operator(Operator.Op.AND, opnd, ParseEqualityExpr(qyInput));
  85             }while (true);
  86         }
  87
  88         //>> EqualityOp ::= '=' | '!='
  89         //>> EqualityExpr    ::= ( EqualityExpr EqualityOp )? RelationalExpr
  90         private AstNode ParseEqualityExpr(AstNode  qyInput) {
  91             AstNode opnd = ParseRelationalExpr(qyInput);
  92
  93             do {
  94                 Operator.Op op = (
  95                     this.scanner.Kind == XPathScanner.LexKind.Eq ? Operator.Op.EQ :
  96                     this.scanner.Kind == XPathScanner.LexKind.Ne ? Operator.Op.NE :
  97                     /*default :*/                                  Operator.Op.INVALID
  98                 );
  99                 if (op == Operator.Op.INVALID) {
 100                     return opnd;
 101                 }
 102                 NextLex();
 103                 opnd = new Operator(op, opnd, ParseRelationalExpr(qyInput));
 104             }while (true);
 105         }
 106
 107         //>> RelationalOp ::= '<' | '>' | '<=' | '>='
 108         //>> RelationalExpr    ::= ( RelationalExpr RelationalOp )? AdditiveExpr
 109         private AstNode ParseRelationalExpr(AstNode  qyInput) {
 110             AstNode  opnd = ParseAdditiveExpr(qyInput);
 111
 112             do {
 113                 Operator.Op op = (
 114                     this.scanner.Kind == XPathScanner.LexKind.Lt ? Operator.Op.LT :
 115                     this.scanner.Kind == XPathScanner.LexKind.Le ? Operator.Op.LE :
 116                     this.scanner.Kind == XPathScanner.LexKind.Gt ? Operator.Op.GT :
 117                     this.scanner.Kind == XPathScanner.LexKind.Ge ? Operator.Op.GE :
 118                     /*default :*/                                  Operator.Op.INVALID
 119                 );
 120                 if (op == Operator.Op.INVALID) {
 121                     return opnd;
 122                 }
 123                 NextLex();
 124                 opnd = new Operator(op, opnd, ParseAdditiveExpr(qyInput));
 125             }while (true);
 126         }
 127
 128         //>> AdditiveOp   ::= '+' | '-'
 129         //>> AdditiveExpr ::= ( AdditiveExpr AdditiveOp )? MultiplicativeExpr
 130         private AstNode ParseAdditiveExpr(AstNode  qyInput) {
 131             AstNode  opnd = ParseMultiplicativeExpr(qyInput);
 132
 133             do {
 134                 Operator.Op op = (
 135                     this.scanner.Kind == XPathScanner.LexKind.Plus  ? Operator.Op.PLUS  :
 136                     this.scanner.Kind == XPathScanner.LexKind.Minus ? Operator.Op.MINUS :
 137                     /*default :*/                                     Operator.Op.INVALID
 138                 );
 139                 if (op == Operator.Op.INVALID) {
 140                     return opnd;
 141                 }
 142                 NextLex();
 143                 opnd = new Operator(op, opnd, ParseMultiplicativeExpr(qyInput));
 144             }while (true);
 145         }
 146
 147         //>> MultiplicativeOp   ::= '*' | 'div' | 'mod'
 148         //>> MultiplicativeExpr ::= ( MultiplicativeExpr MultiplicativeOp )? UnaryExpr
 149         private AstNode ParseMultiplicativeExpr(AstNode  qyInput) {
 150             AstNode  opnd = ParseUnaryExpr(qyInput);
 151
 152             do {
 153                 Operator.Op op = (
 154                     this.scanner.Kind == XPathScanner.LexKind.Star  ? Operator.Op.MUL :
 155                     TestOp("div")                                   ? Operator.Op.DIV :
 156                     TestOp("mod")                                   ? Operator.Op.MOD :
 157                     /*default :*/                                     Operator.Op.INVALID
 158                 );
 159                 if (op == Operator.Op.INVALID) {
 160                     return opnd;
 161                 }
 162                 NextLex();
 163                 opnd = new Operator(op, opnd, ParseUnaryExpr(qyInput));
 164             }while (true);
 165         }
 166
 167         //>> UnaryExpr    ::= UnionExpr | '-' UnaryExpr
 168         private AstNode ParseUnaryExpr(AstNode  qyInput) {
 169             bool minus = false;
 170             while (this.scanner.Kind == XPathScanner.LexKind.Minus) {
 171                 NextLex();
 172                 minus = !minus;
 173             }
 174
 175             if (minus) {
 176                 return new Operator(Operator.Op.MUL, ParseUnionExpr(qyInput), new Operand(-1));
 177             }
 178             else {
 179                 return ParseUnionExpr(qyInput);
 180             }
 181         }
 182
 183         //>> UnionExpr ::= ( UnionExpr '|' )? PathExpr
 184         private AstNode ParseUnionExpr(AstNode  qyInput) {
 185             AstNode opnd = ParsePathExpr(qyInput);
 186
 187             do {
 188                 if (this.scanner.Kind != XPathScanner.LexKind.Union) {
 189                     return opnd;
 190                 }
 191                 NextLex();
 192                 AstNode opnd2 = ParsePathExpr(qyInput);
 193                 CheckNodeSet(opnd.ReturnType);
 194                 CheckNodeSet(opnd2.ReturnType);
 195                 opnd = new Operator(Operator.Op.UNION, opnd, opnd2);
 196             }while (true);
 197         }
 198
 199         private static bool IsNodeType(XPathScanner scaner) {
 200             return (
 201                 scaner.Prefix.Length == 0 && (
 202                     scaner.Name == "node"                   ||
 203                     scaner.Name == "text"                   ||
 204                     scaner.Name == "processing-instruction" ||
 205                     scaner.Name == "comment"
 206                 )
 207             );
 208         }
 209
 210         //>> PathOp   ::= '/' | '//'
 211         //>> PathExpr ::= LocationPath |
 212         //>>              FilterExpr ( PathOp  RelativeLocationPath )?
 213         private AstNode ParsePathExpr(AstNode qyInput) {
 214                         AstNode opnd;
 215                         if (IsPrimaryExpr(this.scanner)) { // in this moment we shoud distinct LocationPas vs FilterExpr (which starts from is PrimaryExpr)
 216                             opnd = ParseFilterExpr(qyInput);
 217                                 if (this.scanner.Kind == XPathScanner.LexKind.Slash) {
 218                                         NextLex();
 219                                         opnd = ParseRelativeLocationPath(opnd);
 220                                 }
 221                                 else if (this.scanner.Kind == XPathScanner.LexKind.SlashSlash) {
 222                                         NextLex();
 223                                         opnd = ParseRelativeLocationPath(new Axis(Axis.AxisType.DescendantOrSelf, opnd));
 224                                 }
 225                         }
 226                         else {
 227                 opnd = ParseLocationPath(null);
 228             }
 229
 230             return opnd;
 231         }
 232
 233         //>> FilterExpr ::= PrimaryExpr | FilterExpr Predicate
 234         private AstNode ParseFilterExpr(AstNode  qyInput) {
 235             AstNode  opnd = ParsePrimaryExpr(qyInput);
 236             while (this.scanner.Kind == XPathScanner.LexKind.LBracket) {
 237                 // opnd must be a query
 238                 opnd = new Filter(opnd, ParsePredicate(opnd));
 239             }
 240             return opnd;
 241         }
 242
 243         //>> Predicate ::= '[' Expr ']'
 244         private AstNode ParsePredicate(AstNode  qyInput) {
 245             AstNode  opnd;
 246
 247             // we have predicates. Check that input type is NodeSet
 248             CheckNodeSet(qyInput.ReturnType);
 249
 250             PassToken(XPathScanner.LexKind.LBracket);
 251             opnd = ParseExpresion(qyInput);
 252             PassToken(XPathScanner.LexKind.RBracket);
 253
 254             return opnd;
 255         }
 256
 257         //>> LocationPath ::= RelativeLocationPath | AbsoluteLocationPath
 258         private AstNode ParseLocationPath(AstNode qyInput) {
 259             if (this.scanner.Kind == XPathScanner.LexKind.Slash) {
 260                 NextLex();
 261                 AstNode opnd = new Root();
 262
 263                 if (IsStep(this.scanner.Kind)) {
 264                     opnd = ParseRelativeLocationPath(opnd);
 265                 }
 266                 return opnd;
 267             }
 268             else if (this.scanner.Kind == XPathScanner.LexKind.SlashSlash) {
 269                 NextLex();
 270                 return ParseRelativeLocationPath(new Axis(Axis.AxisType.DescendantOrSelf, new Root()));
 271             }
 272             else {
 273                 return  ParseRelativeLocationPath(qyInput);
 274             }
 275         } // ParseLocationPath
 276
 277         //>> PathOp   ::= '/' | '//'
 278         //>> RelativeLocationPath ::= ( RelativeLocationPath PathOp )? Step
 279         private AstNode ParseRelativeLocationPath(AstNode  qyInput) {
 280             AstNode opnd = qyInput;
 281             do {
 282                 opnd = ParseStep(opnd);
 283                 if (XPathScanner.LexKind.SlashSlash == this.scanner.Kind) {
 284                     NextLex();
 285                     opnd = new Axis(Axis.AxisType.DescendantOrSelf, opnd);
 286                 }
 287                 else if (XPathScanner.LexKind.Slash == this.scanner.Kind) {
 288                     NextLex();
 289                 }
 290                 else {
 291                     break;
 292                 }
 293             }
 294             while (true);
 295
 296             return opnd;
 297         }
 298
 299                 private static bool IsStep(XPathScanner.LexKind lexKind) {
 300                         return (
 301                                 lexKind == XPathScanner.LexKind.Dot    ||
 302                                 lexKind == XPathScanner.LexKind.DotDot ||
 303                                 lexKind == XPathScanner.LexKind.At     ||
 304                                 lexKind == XPathScanner.LexKind.Axe    ||
 305                                 lexKind == XPathScanner.LexKind.Star   ||
 306                                 lexKind == XPathScanner.LexKind.Name          // NodeTest is also Name
 307                         );
 308                 }
 309
 310         //>> Step ::= '.' | '..' | ( AxisName '::' | '@' )? NodeTest Predicate*
 311         private AstNode ParseStep(AstNode  qyInput) {
 312             AstNode  opnd;
 313             if (XPathScanner.LexKind.Dot == this.scanner.Kind) {         //>> '.'
 314                 NextLex();
 315                 opnd = new Axis(Axis.AxisType.Self, qyInput);
 316             }
 317             else if (XPathScanner.LexKind.DotDot == this.scanner.Kind) { //>> '..'
 318                 NextLex();
 319                 opnd = new Axis(Axis.AxisType.Parent, qyInput);
 320             }
 321             else {                                                          //>> ( AxisName '::' | '@' )? NodeTest Predicate*
 322                 Axis.AxisType axisType = Axis.AxisType.Child;
 323                 switch (this.scanner.Kind) {
 324                 case XPathScanner.LexKind.At:                               //>> '@'
 325                     axisType = Axis.AxisType.Attribute;
 326                     NextLex();
 327                     break;
 328                 case XPathScanner.LexKind.Axe:                              //>> AxisName '::'
 329                     axisType = GetAxis(this.scanner);
 330                     NextLex();
 331                     break;
 332                 }
 333                 XPathNodeType nodeType = (
 334                     axisType == Axis.AxisType.Attribute ? XPathNodeType.Attribute :
 335 //                    axisType == Axis.AxisType.Namespace ? XPathNodeType.Namespace : // No Idea why it's this way but othervise Axes doesn't work
 336                     /* default: */                        XPathNodeType.Element
 337                 );
 338
 339                 opnd = ParseNodeTest(qyInput, axisType, nodeType);
 340
 341                 while (XPathScanner.LexKind.LBracket == this.scanner.Kind) {
 342                     opnd = new Filter(opnd, ParsePredicate(opnd));
 343                 }
 344             }
 345             return opnd;
 346         }
 347
 348         //>> NodeTest ::= NameTest | 'comment ()' | 'text ()' | 'node ()' | 'processing-instruction ('  Literal ? ')'
 349         private AstNode ParseNodeTest(AstNode qyInput, Axis.AxisType axisType, XPathNodeType nodeType) {
 350             string        nodeName, nodePrefix;
 351
 352             switch (this.scanner.Kind) {
 353             case XPathScanner.LexKind.Name :
 354                 if (this.scanner.CanBeFunction && IsNodeType(this.scanner)) {
 355                     nodePrefix = string.Empty;
 356                     nodeName   = string.Empty;
 357                     nodeType = (
 358                         this.scanner.Name == "comment"                ? XPathNodeType.Comment :
 359                         this.scanner.Name == "text"                   ? XPathNodeType.Text :
 360                         this.scanner.Name == "node"                   ? XPathNodeType.All :
 361                         this.scanner.Name == "processing-instruction" ? XPathNodeType.ProcessingInstruction :
 362                         /* default: */ XPathNodeType.Root
 363                     );
 364                     Debug.Assert(nodeType != XPathNodeType.Root);
 365                     NextLex();
 366
 367                     PassToken(XPathScanner.LexKind.LParens);
 368
 369                     if (nodeType == XPathNodeType.ProcessingInstruction) {
 370                         if (this.scanner.Kind != XPathScanner.LexKind.RParens) { //>> 'processing-instruction (' Literal ')'
 371                             CheckToken(XPathScanner.LexKind.String);
 372                             nodeName = this.scanner.StringValue;
 373                             NextLex();
 374                         }
 375                     }
 376
 377                     PassToken(XPathScanner.LexKind.RParens);
 378                 }
 379                 else {
 380                     nodePrefix = this.scanner.Prefix;
 381                     nodeName   = this.scanner.Name;
 382                         NextLex();
 383                     if (nodeName == "*") {
 384                         nodeName = string.Empty;
 385                     }
 386                 }
 387                 break;
 388             case XPathScanner.LexKind.Star :
 389                 nodePrefix = string.Empty;
 390                 nodeName   = string.Empty;
 391                 NextLex();
 392                 break;
 393             default :
 394                     throw XPathException.Create(Res.Xp_NodeSetExpected, this.scanner.SourceText);
 395             }
 396             return new Axis(axisType, qyInput, nodePrefix, nodeName, nodeType);
 397         }
 398
 399                 private static bool IsPrimaryExpr(XPathScanner scanner) {
 400                         return (
 401                                 scanner.Kind == XPathScanner.LexKind.String  ||
 402                                 scanner.Kind == XPathScanner.LexKind.Number  ||
 403                                 scanner.Kind == XPathScanner.LexKind.Dollar  ||
 404                                 scanner.Kind == XPathScanner.LexKind.LParens ||
 405                                 scanner.Kind == XPathScanner.LexKind.Name && scanner.CanBeFunction && ! IsNodeType(scanner)
 406                         );
 407                 }
 408
 409         //>> PrimaryExpr ::= Literal | Number | VariableReference | '(' Expr ')' | FunctionCall
 410         private AstNode ParsePrimaryExpr(AstNode  qyInput) {
 411             Debug.Assert(IsPrimaryExpr(this.scanner));
 412             AstNode  opnd = null;
 413             switch (this.scanner.Kind) {
 414             case XPathScanner.LexKind.String:
 415                 opnd = new Operand(this.scanner.StringValue);
 416                 NextLex();
 417                 break;
 418             case XPathScanner.LexKind.Number:
 419                 opnd = new Operand(this.scanner.NumberValue);
 420                 NextLex();
 421                 break;
 422             case XPathScanner.LexKind.Dollar:
 423                 NextLex();
 424                 CheckToken(XPathScanner.LexKind.Name);
 425                 opnd = new Variable(this.scanner.Name, this.scanner.Prefix);
 426                 NextLex();
 427                 break;
 428             case XPathScanner.LexKind.LParens:
 429                 NextLex();
 430                 opnd = ParseExpresion(qyInput);
 431                 if (opnd.Type != AstNode.AstType.ConstantOperand) {
 432                     opnd = new Group(opnd);
 433                 }
 434                 PassToken(XPathScanner.LexKind.RParens);
 435                 break;
 436             case XPathScanner.LexKind.Name :
 437                 if (this.scanner.CanBeFunction && ! IsNodeType(this.scanner)) {
 438                     opnd = ParseMethod(null);
 439                 }
 440                 break;
 441             }
 442                         Debug.Assert(opnd != null, "IsPrimaryExpr() was true. We should recognize this lex.");
 443             return opnd;
 444         }
 445
 446         private AstNode ParseMethod(AstNode qyInput) {
 447             ArrayList argList = new ArrayList();
 448             string name   = this.scanner.Name;
 449             string prefix = this.scanner.Prefix;
 450             PassToken(XPathScanner.LexKind.Name);
 451             PassToken(XPathScanner.LexKind.LParens);
 452             if (this.scanner.Kind != XPathScanner.LexKind.RParens) {
 453                 do {
 454                     argList.Add(ParseExpresion(qyInput));
 455                     if (this.scanner.Kind == XPathScanner.LexKind.RParens) {
 456                         break;
 457                     }
 458                     PassToken(XPathScanner.LexKind.Comma);
 459                 }while (true);
 460             }
 461             PassToken(XPathScanner.LexKind.RParens);
 462             if (prefix.Length == 0) {
 463                 ParamInfo pi = (ParamInfo) functionTable[name];
 464                 if (pi != null) {
 465                     int argCount = argList.Count;
 466                     if (argCount < pi.Minargs) {
 467                         throw XPathException.Create(Res.Xp_InvalidNumArgs, name, this.scanner.SourceText);
 468                     }
 469                     if (pi.FType == Function.FunctionType.FuncConcat) {
 470                         for (int i = 0; i < argCount; i ++) {
 471                             AstNode arg = (AstNode)argList[i];
 472                             if (arg.ReturnType != XPathResultType.String) {
 473                                 arg = new Function(Function.FunctionType.FuncString, arg);
 474                             }
 475                             argList[i] = arg;
 476                         }
 477                     }
 478                     else {
 479                         if (pi.Maxargs < argCount) {
 480                             throw XPathException.Create(Res.Xp_InvalidNumArgs, name, this.scanner.SourceText);
 481                         }
 482                         if (pi.ArgTypes.Length < argCount) {
 483                             argCount = pi.ArgTypes.Length;    // argument we have the type specified (can be < pi.Minargs)
 484                         }
 485                         for (int i = 0; i < argCount; i ++) {
 486                             AstNode arg = (AstNode)argList[i];
 487                             if (
 488                                 pi.ArgTypes[i] != XPathResultType.Any &&
 489                                 pi.ArgTypes[i] != arg.ReturnType
 490                             ) {
 491                                 switch (pi.ArgTypes[i]) {
 492                                 case  XPathResultType.NodeSet :
 493                                     if (!(arg is Variable) && !(arg is Function && arg.ReturnType == XPathResultType.Any) ) {
 494                                         throw XPathException.Create(Res.Xp_InvalidArgumentType, name, this.scanner.SourceText);
 495                                     }
 496                                     break;
 497                                 case  XPathResultType.String :
 498                                     arg = new Function(Function.FunctionType.FuncString, arg);
 499                                     break;
 500                                 case  XPathResultType.Number :
 501                                     arg = new Function(Function.FunctionType.FuncNumber, arg);
 502                                     break;
 503                                 case  XPathResultType.Boolean :
 504                                     arg = new Function(Function.FunctionType.FuncBoolean, arg);
 505                                     break;
 506                                 }
 507                                 argList[i] = arg;
 508                             }
 509                         }
 510                     }
 511                                         return new Function(pi.FType, argList);
 512                 }
 513             }
 514             return new Function(prefix, name, argList);
 515         }
 516
 517         // --------------- Pattern Parsing ----------------------
 518
 519         //>> Pattern ::= ( Pattern '|' )? LocationPathPattern
 520         private AstNode ParsePattern(AstNode  qyInput) {
 521             AstNode opnd = ParseLocationPathPattern(qyInput);
 522
 523             do {
 524                 if (this.scanner.Kind != XPathScanner.LexKind.Union) {
 525                     return opnd;
 526                 }
 527                 NextLex();
 528                 opnd = new Operator(Operator.Op.UNION, opnd, ParseLocationPathPattern(qyInput));
 529             }while (true);
 530         }
 531
 532         //>> LocationPathPattern ::= '/' | RelativePathPattern | '//' RelativePathPattern  |  '/' RelativePathPattern
 533         //>>                       | IdKeyPattern (('/' | '//') RelativePathPattern)?
 534         private AstNode ParseLocationPathPattern(AstNode qyInput) {
 535             AstNode opnd = null;
 536             switch (this.scanner.Kind) {
 537             case XPathScanner.LexKind.Slash :
 538                 NextLex();
 539                 opnd = new Root();
 540                 if (this.scanner.Kind == XPathScanner.LexKind.Eof || this.scanner.Kind == XPathScanner.LexKind.Union) {
 541                     return opnd;
 542                 }
 543                 break;
 544             case XPathScanner.LexKind.SlashSlash :
 545                 NextLex();
 546                 opnd = new Axis(Axis.AxisType.DescendantOrSelf, new Root());
 547                 break;
 548             case XPathScanner.LexKind.Name :
 549                 if (this.scanner.CanBeFunction) {
 550                     opnd = ParseIdKeyPattern(qyInput);
 551                     if (opnd != null) {
 552                         switch (this.scanner.Kind) {
 553                         case XPathScanner.LexKind.Slash :
 554                             NextLex();
 555                             break;
 556                         case XPathScanner.LexKind.SlashSlash :
 557                             NextLex();
 558                             opnd = new Axis(Axis.AxisType.DescendantOrSelf, opnd);
 559                             break;
 560                         default :
 561                             return opnd;
 562                         }
 563                     }
 564                 }
 565                 break;
 566             }
 567             return ParseRelativePathPattern(opnd);
 568         }
 569
 570         //>> IdKeyPattern ::= 'id' '(' Literal ')' | 'key' '(' Literal ',' Literal ')'
 571         private AstNode ParseIdKeyPattern(AstNode qyInput) {
 572             Debug.Assert(this.scanner.CanBeFunction);
 573             ArrayList argList = new ArrayList();
 574             if (this.scanner.Prefix.Length == 0) {
 575                 if (this.scanner.Name == "id") {
 576                     ParamInfo pi = (ParamInfo) functionTable["id"];
 577                     NextLex();;
 578                     PassToken(XPathScanner.LexKind.LParens);
 579                     CheckToken(XPathScanner.LexKind.String);
 580                     argList.Add(new Operand(this.scanner.StringValue));
 581                     NextLex();
 582                     PassToken(XPathScanner.LexKind.RParens);
 583                                         return new Function(pi.FType, argList);
 584                 }
 585                 if (this.scanner.Name == "key") {
 586                     NextLex();
 587                     PassToken(XPathScanner.LexKind.LParens);
 588                     CheckToken(XPathScanner.LexKind.String);
 589                     argList.Add(new Operand(this.scanner.StringValue));
 590                     NextLex();
 591                     PassToken(XPathScanner.LexKind.Comma);
 592                     CheckToken(XPathScanner.LexKind.String);
 593                     argList.Add(new Operand(this.scanner.StringValue));
 594                     NextLex();
 595                     PassToken(XPathScanner.LexKind.RParens);
 596                                         return new Function("", "key", argList);
 597                 }
 598             }
 599             return null;
 600         }
 601
 602         //>> PathOp   ::= '/' | '//'
 603         //>> RelativePathPattern ::= ( RelativePathPattern PathOp )? StepPattern
 604         private AstNode ParseRelativePathPattern(AstNode qyInput) {
 605             AstNode  opnd = ParseStepPattern(qyInput);
 606             if (XPathScanner.LexKind.SlashSlash == this.scanner.Kind) {
 607                 NextLex();
 608                 opnd = ParseRelativePathPattern(new Axis(Axis.AxisType.DescendantOrSelf, opnd));
 609             }
 610                         else if (XPathScanner.LexKind.Slash == this.scanner.Kind) {
 611                 NextLex();
 612                 opnd = ParseRelativePathPattern(opnd);
 613             }
 614             return opnd;
 615         }
 616
 617         //>> StepPattern    ::=    ChildOrAttributeAxisSpecifier NodeTest Predicate*
 618         //>> ChildOrAttributeAxisSpecifier    ::=    @ ? | ('child' | 'attribute') '::'
 619         private AstNode ParseStepPattern(AstNode qyInput) {
 620             AstNode  opnd;
 621             Axis.AxisType axisType = Axis.AxisType.Child;
 622             switch (this.scanner.Kind) {
 623             case XPathScanner.LexKind.At:                               //>> '@'
 624                 axisType = Axis.AxisType.Attribute;
 625                 NextLex();
 626                 break;
 627             case XPathScanner.LexKind.Axe:                              //>> AxisName '::'
 628                 axisType = GetAxis(this.scanner);
 629                 if (axisType != Axis.AxisType.Child && axisType != Axis.AxisType.Attribute) {
 630                     throw XPathException.Create(Res.Xp_InvalidToken, scanner.SourceText);
 631                 }
 632                 NextLex();
 633                 break;
 634             }
 635             XPathNodeType nodeType = (
 636                 axisType == Axis.AxisType.Attribute ? XPathNodeType.Attribute :
 637                 /* default: */                        XPathNodeType.Element
 638             );
 639
 640             opnd = ParseNodeTest(qyInput, axisType, nodeType);
 641
 642             while (XPathScanner.LexKind.LBracket == this.scanner.Kind) {
 643                 opnd = new Filter(opnd, ParsePredicate(opnd));
 644             }
 645             return opnd;
 646         }
 647
 648         // --------------- Helper methods ----------------------
 649
 650         void CheckToken(XPathScanner.LexKind t) {
 651             if (this.scanner.Kind != t) {
 652                 throw XPathException.Create(Res.Xp_InvalidToken, this.scanner.SourceText);
 653             }
 654         }
 655
 656         void PassToken(XPathScanner.LexKind t) {
 657             CheckToken(t);
 658             NextLex();
 659         }
 660
 661         void NextLex() {
 662             this.scanner.NextLex();
 663         }
 664
 665         private bool TestOp(string op) {
 666             return (
 667                 this.scanner.Kind == XPathScanner.LexKind.Name &&
 668                 this.scanner.Prefix.Length == 0 &&
 669                 this.scanner.Name.Equals(op)
 670             );
 671         }
 672
 673         void CheckNodeSet(XPathResultType t) {
 674             if (t != XPathResultType.NodeSet && t != XPathResultType.Any) {
 675                 throw XPathException.Create(Res.Xp_NodeSetExpected, this.scanner.SourceText);
 676             }
 677         }
 678
 679         // ----------------------------------------------------------------
 680         static readonly XPathResultType[] temparray1 = {};
 681         static readonly XPathResultType[] temparray2 = {XPathResultType.NodeSet};
 682         static readonly XPathResultType[] temparray3 = {XPathResultType.Any};
 683         static readonly XPathResultType[] temparray4 = {XPathResultType.String};
 684         static readonly XPathResultType[] temparray5 = {XPathResultType.String, XPathResultType.String};
 685         static readonly XPathResultType[] temparray6 = {XPathResultType.String, XPathResultType.Number, XPathResultType.Number};
 686         static readonly XPathResultType[] temparray7 = {XPathResultType.String, XPathResultType.String, XPathResultType.String};
 687         static readonly XPathResultType[] temparray8 = {XPathResultType.Boolean};
 688         static readonly XPathResultType[] temparray9 = {XPathResultType.Number};
 689
 690         private class ParamInfo {
 691             private Function.FunctionType ftype;
 692             private int                   minargs;
 693             private int                   maxargs;
 694             private XPathResultType[]     argTypes;
 695
 696             public Function.FunctionType FType    { get { return this.ftype;    } }
 697             public int                   Minargs  { get { return this.minargs;  } }
 698             public int                   Maxargs  { get { return this.maxargs;  } }
 699             public XPathResultType[]     ArgTypes { get { return this.argTypes; } }
 700
 701             internal ParamInfo(Function.FunctionType ftype, int minargs,  int maxargs, XPathResultType[] argTypes) {
 702                 this.ftype   = ftype;
 703                 this.minargs = minargs;
 704                 this.maxargs = maxargs;
 705                 this.argTypes = argTypes;
 706             }
 707         } //ParamInfo
 708
 709         private static Hashtable functionTable = CreateFunctionTable();
 710         private static Hashtable CreateFunctionTable(){
 711             Hashtable table = new Hashtable(36);
 712             table.Add("last"               , new ParamInfo(Function.FunctionType.FuncLast           , 0, 0, temparray1));
 713             table.Add("position"           , new ParamInfo(Function.FunctionType.FuncPosition       , 0, 0, temparray1));
 714             table.Add("name"               , new ParamInfo(Function.FunctionType.FuncName           , 0, 1, temparray2));
 715             table.Add("namespace-uri"      , new ParamInfo(Function.FunctionType.FuncNameSpaceUri   , 0, 1, temparray2));
 716             table.Add("local-name"         , new ParamInfo(Function.FunctionType.FuncLocalName      , 0, 1, temparray2));
 717             table.Add("count"              , new ParamInfo(Function.FunctionType.FuncCount          , 1, 1, temparray2));
 718             table.Add("id"                 , new ParamInfo(Function.FunctionType.FuncID             , 1, 1, temparray3));
 719             table.Add("string"             , new ParamInfo(Function.FunctionType.FuncString         , 0, 1, temparray3));
 720             table.Add("concat"             , new ParamInfo(Function.FunctionType.FuncConcat         , 2, 100, temparray4));
 721             table.Add("starts-with"        , new ParamInfo(Function.FunctionType.FuncStartsWith     , 2, 2, temparray5));
 722             table.Add("contains"           , new ParamInfo(Function.FunctionType.FuncContains       , 2, 2, temparray5));
 723             table.Add("substring-before"   , new ParamInfo(Function.FunctionType.FuncSubstringBefore, 2, 2, temparray5));
 724             table.Add("substring-after"    , new ParamInfo(Function.FunctionType.FuncSubstringAfter , 2, 2, temparray5));
 725             table.Add("substring"          , new ParamInfo(Function.FunctionType.FuncSubstring      , 2, 3, temparray6));
 726             table.Add("string-length"      , new ParamInfo(Function.FunctionType.FuncStringLength   , 0, 1, temparray4));
 727             table.Add("normalize-space"    , new ParamInfo(Function.FunctionType.FuncNormalize      , 0, 1, temparray4));
 728             table.Add("translate"          , new ParamInfo(Function.FunctionType.FuncTranslate      , 3, 3, temparray7));
 729             table.Add("boolean"            , new ParamInfo(Function.FunctionType.FuncBoolean        , 1, 1, temparray3));
 730             table.Add("not"                , new ParamInfo(Function.FunctionType.FuncNot            , 1, 1, temparray8));
 731             table.Add("true"               , new ParamInfo(Function.FunctionType.FuncTrue           , 0, 0 ,temparray8));
 732             table.Add("false"              , new ParamInfo(Function.FunctionType.FuncFalse          , 0, 0, temparray8));
 733             table.Add("lang"               , new ParamInfo(Function.FunctionType.FuncLang           , 1, 1, temparray4));
 734             table.Add("number"             , new ParamInfo(Function.FunctionType.FuncNumber         , 0, 1, temparray3));
 735             table.Add("sum"                , new ParamInfo(Function.FunctionType.FuncSum            , 1, 1, temparray2));
 736             table.Add("floor"              , new ParamInfo(Function.FunctionType.FuncFloor          , 1, 1, temparray9));
 737             table.Add("ceiling"            , new ParamInfo(Function.FunctionType.FuncCeiling        , 1, 1, temparray9));
 738             table.Add("round"              , new ParamInfo(Function.FunctionType.FuncRound          , 1, 1, temparray9));
 739             return table;
 740         }
 741
 742         private static Hashtable AxesTable = CreateAxesTable();
 743         private static Hashtable CreateAxesTable() {
 744             Hashtable table = new Hashtable(13);
 745             table.Add("ancestor"          , Axis.AxisType.Ancestor         );
 746             table.Add("ancestor-or-self"  , Axis.AxisType.AncestorOrSelf   );
 747             table.Add("attribute"         , Axis.AxisType.Attribute        );
 748             table.Add("child"             , Axis.AxisType.Child            );
 749             table.Add("descendant"        , Axis.AxisType.Descendant       );
 750             table.Add("descendant-or-self", Axis.AxisType.DescendantOrSelf );
 751             table.Add("following"         , Axis.AxisType.Following        );
 752             table.Add("following-sibling" , Axis.AxisType.FollowingSibling );
 753             table.Add("namespace"         , Axis.AxisType.Namespace        );
 754             table.Add("parent"            , Axis.AxisType.Parent           );
 755             table.Add("preceding"         , Axis.AxisType.Preceding        );
 756             table.Add("preceding-sibling" , Axis.AxisType.PrecedingSibling );
 757             table.Add("self"              , Axis.AxisType.Self             );
 758             return table;
 759         }
 760
 761         private Axis.AxisType GetAxis(XPathScanner scaner) {
 762             Debug.Assert(scaner.Kind == XPathScanner.LexKind.Axe);
 763             object axis = AxesTable[scaner.Name];
 764             if (axis == null) {
 765                 throw XPathException.Create(Res.Xp_InvalidToken, scanner.SourceText);
 766             }
 767             return (Axis.AxisType) axis;
 768         }
 769
 770     }
 771 }