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

   1 //------------------------------------------------------------------------------
   2 // <copyright file="querybuilder.cs" company="Microsoft">
   3 //     Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 // <owner current="true" primary="true">Microsoft</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.Collections;
  14     using System.Collections.Generic;
  15     using FT = Function.FunctionType;
  16
  17     internal sealed class QueryBuilder {
  18         // Note: Up->Doun, Down->Up:
  19         //       For operators order is normal: 1 + 2 --> Operator+(1, 2)
  20         //       For pathes order is reversed: a/b -> ChildQuery_B(input: ChildQuery_A(input: ContextQuery()))
  21         // Input flags. We pass them Up->Down.
  22         // Using them upper query set states wich controls how inner query will be built.
  23         enum Flags {
  24             None      = 0x00,
  25             SmartDesc = 0x01,
  26             PosFilter = 0x02,  // Node has this flag set when it has position predicate applied to it
  27             Filter    = 0x04,  // Subtree we compiling will be filtered. i.e. Flag not set on rightmost filter.
  28         }
  29         // Output props. We return them Down->Up.
  30         // These are properties of Query tree we have built already.
  31         // These properties are closely related to QueryProps exposed by Query node itself.
  32         // They have the following difference:
  33         //      QueryProps describe property of node they are (belong like Reverse)
  34         //      these Props describe acumulated properties of the tree (like nonFlat)
  35         enum Props {
  36             None        = 0x00,
  37             PosFilter   = 0x01,  // This filter or inner filter was positional: foo[1] or foo[1][true()]
  38             HasPosition = 0x02,  // Expression may ask position() of the context
  39             HasLast     = 0x04,  // Expression may ask last() of the context
  40             NonFlat     = 0x08,  // Some nodes may be descendent of otheres
  41         }
  42
  43         // comment are aproximate. This is my best understanding:
  44         private string query;
  45         private bool allowVar;
  46         private bool allowKey;
  47         private bool allowCurrent;
  48         private bool needContext;
  49         private BaseAxisQuery firstInput; // Input of the leftmost predicate. Set by leftmost predicate, used in rightmost one
  50
  51         private void Reset() {
  52             parseDepth = 0;
  53             needContext = false;
  54         }
  55
  56         private Query ProcessAxis(Axis root, Flags flags, out Props props) {
  57             Query result = null;
  58             if (root.Prefix.Length > 0) {
  59                 needContext = true;
  60             }
  61             firstInput = null;
  62             Query qyInput; {
  63                 if (root.Input != null) {
  64                     Flags inputFlags = Flags.None;
  65                     if ((flags & Flags.PosFilter) == 0) {
  66                         Axis input = root.Input as Axis;
  67                         if (input != null) {
  68                             if (
  69                                 root.TypeOfAxis == Axis.AxisType.Child &&
  70                                 input.TypeOfAxis == Axis.AxisType.DescendantOrSelf && input.NodeType == XPathNodeType.All
  71                             ) {
  72                                 Query qyGrandInput;
  73                                 if (input.Input != null) {
  74                                     qyGrandInput = ProcessNode(input.Input, Flags.SmartDesc, out props);
  75                                 } else {
  76                                     qyGrandInput = new ContextQuery();
  77                                     props = Props.None;
  78                                 }
  79                                 result = new DescendantQuery(qyGrandInput, root.Name, root.Prefix, root.NodeType, false, input.AbbrAxis);
  80                                 if ((props & Props.NonFlat) != 0) {
  81                                     result = new DocumentOrderQuery(result);
  82                                 }
  83                                 props |= Props.NonFlat;
  84                                 return result;
  85                             }
  86                         }
  87                         if (root.TypeOfAxis == Axis.AxisType.Descendant || root.TypeOfAxis == Axis.AxisType.DescendantOrSelf)  {
  88                             inputFlags |= Flags.SmartDesc;
  89                         }
  90                     }
  91
  92                     qyInput = ProcessNode(root.Input, inputFlags, out props);
  93                 } else {
  94                     qyInput = new ContextQuery();
  95                     props = Props.None;
  96                 }
  97             }
  98
  99             switch (root.TypeOfAxis) {
 100             case Axis.AxisType.Ancestor:
 101                 result = new XPathAncestorQuery(qyInput , root.Name, root.Prefix, root.NodeType, false);
 102                 props |= Props.NonFlat;
 103                 break;
 104             case Axis.AxisType.AncestorOrSelf:
 105                 result = new XPathAncestorQuery(qyInput, root.Name, root.Prefix, root.NodeType, true);
 106                 props |= Props.NonFlat;
 107                 break;
 108             case Axis.AxisType.Child:
 109                 if ((props & Props.NonFlat) != 0) {
 110                     result = new CacheChildrenQuery(qyInput, root.Name, root.Prefix, root.NodeType);
 111                 } else {
 112                     result = new ChildrenQuery(qyInput, root.Name, root.Prefix, root.NodeType);
 113                 }
 114                 break;
 115             case Axis.AxisType.Parent:
 116                 result = new ParentQuery(qyInput, root.Name, root.Prefix, root.NodeType);
 117                 break;
 118             case Axis.AxisType.Descendant:
 119                 if ((flags & Flags.SmartDesc) != 0) {
 120                     result = new DescendantOverDescendantQuery(qyInput, false, root.Name, root.Prefix, root.NodeType, /*abbrAxis:*/false);
 121                 } else {
 122                     result = new DescendantQuery(qyInput, root.Name, root.Prefix, root.NodeType, false, /*abbrAxis:*/false);
 123                     if ((props & Props.NonFlat) != 0) {
 124                         result = new DocumentOrderQuery(result);
 125                     }
 126                 }
 127                 props |= Props.NonFlat;
 128                 break;
 129             case Axis.AxisType.DescendantOrSelf:
 130                 if ((flags & Flags.SmartDesc) != 0) {
 131                     result = new DescendantOverDescendantQuery(qyInput, true, root.Name, root.Prefix, root.NodeType, root.AbbrAxis);
 132                 } else {
 133                     result = new DescendantQuery(qyInput, root.Name, root.Prefix, root.NodeType, true, root.AbbrAxis);
 134                     if ((props & Props.NonFlat) != 0) {
 135                         result = new DocumentOrderQuery(result);
 136                     }
 137                 }
 138                 props |= Props.NonFlat;
 139                 break;
 140             case Axis.AxisType.Preceding:
 141                 result = new PrecedingQuery(qyInput, root.Name, root.Prefix, root.NodeType);
 142                 props |= Props.NonFlat;
 143                 break;
 144             case Axis.AxisType.Following:
 145                 result = new FollowingQuery(qyInput, root.Name, root.Prefix, root.NodeType);
 146                 props |= Props.NonFlat;
 147                 break;
 148             case Axis.AxisType.FollowingSibling:
 149                 result = new FollSiblingQuery(qyInput, root.Name, root.Prefix, root.NodeType);
 150                 if ((props & Props.NonFlat) != 0) {
 151                     result = new DocumentOrderQuery(result);
 152                 }
 153                 break;
 154             case Axis.AxisType.PrecedingSibling:
 155                 result = new PreSiblingQuery(qyInput, root.Name, root.Prefix, root.NodeType);
 156                 break;
 157             case Axis.AxisType.Attribute:
 158                 result = new AttributeQuery(qyInput, root.Name, root.Prefix, root.NodeType);
 159                 break;
 160             case Axis.AxisType.Self:
 161                 result = new XPathSelfQuery(qyInput, root.Name, root.Prefix, root.NodeType);
 162                 break;
 163             case Axis.AxisType.Namespace:
 164                 if ((root.NodeType == XPathNodeType.All || root.NodeType == XPathNodeType.Element || root.NodeType == XPathNodeType.Attribute) && root.Prefix.Length == 0) {
 165                     result = new NamespaceQuery(qyInput, root.Name, root.Prefix, root.NodeType);
 166                 } else {
 167                     result = new EmptyQuery();
 168                 }
 169                 break;
 170             default:
 171                 throw XPathException.Create(Res.Xp_NotSupported, query);
 172             }
 173
 174             return result;
 175         }
 176
 177         private bool CanBeNumber(Query q) {
 178             return (
 179                 q.StaticType == XPathResultType.Any ||
 180                 q.StaticType == XPathResultType.Number
 181             );
 182         }
 183
 184         private Query ProcessFilter(Filter root, Flags flags, out Props props) {
 185             bool first = ((flags & Flags.Filter) == 0);
 186
 187             Props propsCond;
 188             Query cond = ProcessNode(root.Condition, Flags.None, out propsCond);
 189
 190             if (
 191                 CanBeNumber(cond) ||
 192                 (propsCond & (Props.HasPosition | Props.HasLast)) != 0
 193             ) {
 194                 propsCond |= Props.HasPosition;
 195                 flags |= Flags.PosFilter;
 196             }
 197
 198             // We don't want DescendantOverDescendant pattern to be recognized here (in case descendent::foo[expr]/descendant::bar)
 199             // So we clean this flag here:
 200             flags &= ~Flags.SmartDesc;
 201             // ToDo: Instead it would be nice to wrap descendent::foo[expr] into special query that will flatten it -- i.e.
 202             //       remove all nodes that are descendant of other nodes. This is very easy becuase for sorted nodesets all children
 203             //       follow its parent. One step caching. This can be easyly done by rightmost DescendantQuery itsef.
 204             //       Interesting note! Can we garatee that DescendantOverDescendant returns flat nodeset? This defenetely true if it's input is flat.
 205
 206             Query qyInput = ProcessNode(root.Input, flags | Flags.Filter, out props);
 207
 208             if (root.Input.Type != AstNode.AstType.Filter) {
 209                 // Props.PosFilter is for nested filters only.
 210                 // We clean it here to avoid cleaning it in all other ast nodes.
 211                 props &= ~Props.PosFilter;
 212             }
 213             if ((propsCond & Props.HasPosition) != 0) {
 214                 // this condition is positional rightmost filter should be avare of this.
 215                 props |= Props.PosFilter;
 216             }
 217
 218             /*merging predicates*/ {
 219                 FilterQuery qyFilter = qyInput as FilterQuery;
 220                 if (qyFilter != null && (propsCond & Props.HasPosition) == 0 && qyFilter.Condition.StaticType != XPathResultType.Any) {
 221                     Query prevCond = qyFilter.Condition;
 222                     if (prevCond.StaticType == XPathResultType.Number) {
 223                         prevCond = new LogicalExpr(Operator.Op.EQ, new NodeFunctions(FT.FuncPosition, null), prevCond);
 224                     }
 225                     cond = new BooleanExpr(Operator.Op.AND, prevCond, cond);
 226                     qyInput = qyFilter.qyInput;
 227                 }
 228             }
 229
 230             if ((props & Props.PosFilter) != 0 && qyInput is DocumentOrderQuery) {
 231                 qyInput = ((DocumentOrderQuery)qyInput).input;
 232             }
 233             if (firstInput == null) {
 234                 firstInput = qyInput as BaseAxisQuery;
 235             }
 236
 237             bool merge   = (qyInput.Properties & QueryProps.Merge  ) != 0;
 238             bool reverse = (qyInput.Properties & QueryProps.Reverse) != 0;
 239             if ((propsCond & Props.HasPosition) != 0) {
 240                 if (reverse) {
 241                     qyInput = new ReversePositionQuery(qyInput);
 242                 } else if ((propsCond & Props.HasLast) != 0) {
 243                     qyInput = new ForwardPositionQuery(qyInput);
 244                 }
 245             }
 246
 247             if (first && firstInput != null) {
 248                 if (merge && (props & Props.PosFilter) != 0) {
 249                     qyInput = new FilterQuery(qyInput, cond, /*noPosition:*/false);
 250                     Query parent = firstInput.qyInput;
 251                     if (! (parent is ContextQuery)) { // we don't need to wrap filter with MergeFilterQuery when cardinality is parent <: ?
 252                         firstInput.qyInput = new ContextQuery();
 253                         firstInput = null;
 254                         return new MergeFilterQuery(parent, qyInput);
 255                     }
 256                     firstInput = null;
 257                     return qyInput;
 258                 }
 259                 firstInput = null;
 260             }
 261             return new FilterQuery(qyInput, cond, /*noPosition:*/(propsCond & Props.HasPosition) == 0);
 262         }
 263
 264         private Query ProcessOperator(Operator root, out Props props) {
 265             Props props1, props2;
 266             Query op1 = ProcessNode(root.Operand1, Flags.None, out props1);
 267             Query op2 = ProcessNode(root.Operand2, Flags.None, out props2);
 268             props = props1 | props2;
 269             switch (root.OperatorType) {
 270             case Operator.Op.PLUS   :
 271             case Operator.Op.MINUS  :
 272             case Operator.Op.MUL    :
 273             case Operator.Op.MOD    :
 274             case Operator.Op.DIV:
 275                 return new NumericExpr(root.OperatorType, op1, op2);
 276             case Operator.Op.LT     :
 277             case Operator.Op.GT     :
 278             case Operator.Op.LE     :
 279             case Operator.Op.GE     :
 280             case Operator.Op.EQ     :
 281             case Operator.Op.NE     :
 282                 return new LogicalExpr(root.OperatorType, op1, op2);
 283             case Operator.Op.OR     :
 284             case Operator.Op.AND    :
 285                 return new BooleanExpr(root.OperatorType, op1, op2);
 286             case Operator.Op.UNION  :
 287                 props |= Props.NonFlat;
 288                 return new UnionExpr(op1, op2);
 289             default : return null;
 290             }
 291         }
 292
 293         private Query ProcessVariable(Variable root) {
 294             needContext = true;
 295             if (! allowVar) {
 296                 throw XPathException.Create(Res.Xp_InvalidKeyPattern, query);
 297             }
 298             return new VariableQuery(root.Localname, root.Prefix);
 299         }
 300
 301         private Query ProcessFunction(Function root, out Props props) {
 302             props = Props.None;
 303             Query qy = null;
 304             switch (root.TypeOfFunction) {
 305             case FT.FuncLast:
 306                 qy = new NodeFunctions(root.TypeOfFunction, null);
 307                 props |= Props.HasLast;
 308                 return qy;
 309             case FT.FuncPosition:
 310                 qy = new NodeFunctions(root.TypeOfFunction, null);
 311                 props |= Props.HasPosition;
 312                 return qy;
 313             case FT.FuncCount:
 314                 return new NodeFunctions(FT.FuncCount,
 315                     ProcessNode((AstNode)(root.ArgumentList[0]), Flags.None, out props)
 316                 );
 317             case FT.FuncID:
 318                 qy = new IDQuery(ProcessNode((AstNode)(root.ArgumentList[0]), Flags.None, out props));
 319                 props |= Props.NonFlat;
 320                 return qy;
 321             case FT.FuncLocalName:
 322             case FT.FuncNameSpaceUri:
 323             case FT.FuncName:
 324                 if (root.ArgumentList != null && root.ArgumentList.Count > 0) {
 325                     return new NodeFunctions(root.TypeOfFunction,
 326                         ProcessNode((AstNode)(root.ArgumentList[0]), Flags.None, out props)
 327                     );
 328                 } else {
 329                     return new NodeFunctions(root.TypeOfFunction, null);
 330                 }
 331             case FT.FuncString:
 332             case FT.FuncConcat:
 333             case FT.FuncStartsWith:
 334             case FT.FuncContains:
 335             case FT.FuncSubstringBefore:
 336             case FT.FuncSubstringAfter:
 337             case FT.FuncSubstring:
 338             case FT.FuncStringLength:
 339             case FT.FuncNormalize:
 340             case FT.FuncTranslate:
 341                 return new StringFunctions(root.TypeOfFunction, ProcessArguments(root.ArgumentList, out props));
 342             case FT.FuncNumber:
 343             case FT.FuncSum:
 344             case FT.FuncFloor:
 345             case FT.FuncCeiling:
 346             case FT.FuncRound:
 347                 if (root.ArgumentList != null && root.ArgumentList.Count > 0) {
 348                     return new NumberFunctions(root.TypeOfFunction,
 349                         ProcessNode((AstNode)root.ArgumentList[0], Flags.None, out props)
 350                     );
 351                 } else {
 352                     return new NumberFunctions(Function.FunctionType.FuncNumber, null);
 353                 }
 354             case FT.FuncTrue:
 355             case FT.FuncFalse:
 356                 return new BooleanFunctions(root.TypeOfFunction, null);
 357             case FT.FuncNot:
 358             case FT.FuncLang:
 359             case FT.FuncBoolean:
 360                 return new BooleanFunctions(root.TypeOfFunction,
 361                     ProcessNode((AstNode)root.ArgumentList[0], Flags.None, out props)
 362                 );
 363             case FT.FuncUserDefined:
 364                 needContext = true;
 365                 if (! allowCurrent && root.Name == "current" && root.Prefix.Length == 0) {
 366                     throw XPathException.Create(Res.Xp_CurrentNotAllowed);
 367                 }
 368                 if (! allowKey && root.Name == "key" && root.Prefix.Length == 0) {
 369                     throw XPathException.Create(Res.Xp_InvalidKeyPattern, query);
 370                 }
 371                 qy = new FunctionQuery(root.Prefix, root.Name, ProcessArguments(root.ArgumentList, out props));
 372                 props |= Props.NonFlat;
 373                 return qy;
 374             default:
 375                 throw XPathException.Create(Res.Xp_NotSupported, query);
 376             }
 377         }
 378
 379         List<Query> ProcessArguments(ArrayList args, out Props props) {
 380             int numArgs = args != null ? args.Count : 0;
 381             List<Query> argList = new List<Query>(numArgs);
 382             props = Props.None;
 383             for (int count = 0; count < numArgs; count++) {
 384                 Props argProps;
 385                 argList.Add(ProcessNode((AstNode)args[count], Flags.None, out argProps));
 386                 props |= argProps;
 387             }
 388             return argList;
 389         }
 390
 391         private int parseDepth = 0;
 392         private const int MaxParseDepth = 1024;
 393
 394         private Query ProcessNode(AstNode root, Flags flags, out Props props) {
 395
 396             if (++parseDepth > MaxParseDepth) {
 397                 throw XPathException.Create(Res.Xp_QueryTooComplex);
 398             }
 399
 400             Debug.Assert(root != null, "root != null");
 401             Query result = null;
 402             props = Props.None;
 403             switch (root.Type) {
 404             case AstNode.AstType.Axis:
 405                 result = ProcessAxis((Axis)root, flags, out props);
 406                 break;
 407             case AstNode.AstType.Operator:
 408                 result = ProcessOperator((Operator)root, out props);
 409                 break;
 410             case AstNode.AstType.Filter:
 411                 result = ProcessFilter((Filter)root, flags, out props);
 412                 break;
 413             case AstNode.AstType.ConstantOperand:
 414                 result = new OperandQuery(((Operand)root).OperandValue);
 415                 break;
 416             case AstNode.AstType.Variable:
 417                 result = ProcessVariable((Variable)root);
 418                 break;
 419             case AstNode.AstType.Function:
 420                 result = ProcessFunction((Function)root, out props);
 421                 break;
 422             case AstNode.AstType.Group:
 423                 result = new GroupQuery(ProcessNode(((Group)root).GroupNode, Flags.None, out props));
 424                 break;
 425             case AstNode.AstType.Root:
 426                 result = new AbsoluteQuery();
 427                 break;
 428             default:
 429                 Debug.Assert(false, "Unknown QueryType encountered!!");
 430                 break;
 431             }
 432             --parseDepth;
 433             return result;
 434         }
 435
 436         private Query Build(AstNode root, string query) {
 437             Reset();
 438             Props props;
 439             this.query = query;
 440             Query result = ProcessNode(root, Flags.None, out props);
 441             return result;
 442         }
 443
 444         internal Query Build(string query, bool allowVar, bool allowKey) {
 445             this.allowVar = allowVar;
 446             this.allowKey = allowKey;
 447             this.allowCurrent = true;
 448             return Build(XPathParser.ParseXPathExpresion(query), query);
 449         }
 450
 451         internal Query Build(string query, out bool needContext) {
 452             Query result =  Build(query, true, true);
 453             needContext = this.needContext;
 454             return result;
 455         }
 456
 457         internal Query BuildPatternQuery(string query, bool allowVar, bool allowKey) {
 458             this.allowVar = allowVar;
 459             this.allowKey = allowKey;
 460             this.allowCurrent = false;
 461             return Build(XPathParser.ParseXPathPattern(query), query);
 462         }
 463
 464         internal Query BuildPatternQuery(string query, out bool needContext) {
 465             Query result =  BuildPatternQuery(query, true, true);
 466             needContext = this.needContext;
 467             return result;
 468         }
 469     }
 470 }