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 Reset()51 private void Reset() { 52 parseDepth = 0; 53 needContext = false; 54 } 55 ProcessAxis(Axis root, Flags flags, out Props props)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 CanBeNumber(Query q)177 private bool CanBeNumber(Query q) { 178 return ( 179 q.StaticType == XPathResultType.Any || 180 q.StaticType == XPathResultType.Number 181 ); 182 } 183 ProcessFilter(Filter root, Flags flags, out Props props)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 ProcessOperator(Operator root, out Props props)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 ProcessVariable(Variable root)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 ProcessFunction(Function root, out Props props)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 ProcessArguments(ArrayList args, out Props props)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 ProcessNode(AstNode root, Flags flags, out Props props)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 Build(AstNode root, string query)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 Build(string query, bool allowVar, bool allowKey)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 Build(string query, out bool needContext)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 BuildPatternQuery(string query, bool allowVar, bool allowKey)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 BuildPatternQuery(string query, out bool needContext)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 } 471