1 //------------------------------------------------------------------------------ 2 // <copyright file="XPathBuilder.cs" company="Microsoft"> 3 // Copyright (c) Microsoft Corporation. All rights reserved. 4 // </copyright> 5 // <owner current="true" primary="true">Microsoft</owner> 6 //------------------------------------------------------------------------------ 7 8 using System.Collections.Generic; 9 using System.Diagnostics; 10 using System.Globalization; 11 using System.Xml.Schema; 12 using System.Xml.XPath; 13 using System.Xml.Xsl.Qil; 14 15 //#define StopMaskOptimisation 16 17 namespace System.Xml.Xsl.XPath { 18 using FunctionInfo = XPathBuilder.FunctionInfo<XPathBuilder.FuncId>; 19 using Res = System.Xml.Utils.Res; 20 using T = XmlQueryTypeFactory; 21 22 internal class XPathBuilder : IXPathBuilder<QilNode>, IXPathEnvironment { 23 private XPathQilFactory f; 24 private IXPathEnvironment environment; 25 private bool inTheBuild; 26 27 // Singleton nodes used as fixup markers 28 protected QilNode fixupCurrent, fixupPosition, fixupLast; 29 30 // Number of unresolved fixup nodes 31 protected int numFixupCurrent, numFixupPosition, numFixupLast; 32 private FixupVisitor fixupVisitor; 33 34 /* ---------------------------------------------------------------------------- 35 IXPathEnvironment interface 36 */ IFocus.GetCurrent()37 QilNode IFocus.GetCurrent() { return GetCurrentNode (); } IFocus.GetPosition()38 QilNode IFocus.GetPosition() { return GetCurrentPosition(); } IFocus.GetLast()39 QilNode IFocus.GetLast() { return GetLastPosition (); } 40 41 XPathQilFactory IXPathEnvironment.Factory { get { return f; } } 42 IXPathEnvironment.ResolveVariable(string prefix, string name)43 QilNode IXPathEnvironment.ResolveVariable(string prefix, string name) { 44 return Variable(prefix, name); 45 } IXPathEnvironment.ResolveFunction(string prefix, string name, IList<QilNode> args, IFocus env)46 QilNode IXPathEnvironment.ResolveFunction(string prefix, string name, IList<QilNode> args, IFocus env) { 47 Debug.Fail("Must not be called"); 48 return null; 49 } IXPathEnvironment.ResolvePrefix(string prefix)50 string IXPathEnvironment.ResolvePrefix(string prefix) { 51 return environment.ResolvePrefix(prefix); 52 } 53 // ---------------------------------------------------------------------------- 54 XPathBuilder(IXPathEnvironment environment)55 public XPathBuilder(IXPathEnvironment environment) { 56 this.environment = environment; 57 this.f = this.environment.Factory; 58 this.fixupCurrent = f.Unknown(T.NodeNotRtf); 59 this.fixupPosition = f.Unknown(T.DoubleX); 60 this.fixupLast = f.Unknown(T.DoubleX); 61 this.fixupVisitor = new FixupVisitor(f, fixupCurrent, fixupPosition, fixupLast); 62 } 63 StartBuild()64 public virtual void StartBuild() { 65 Debug.Assert(! inTheBuild, "XPathBuilder is busy!"); 66 inTheBuild = true; 67 numFixupCurrent = numFixupPosition = numFixupLast = 0; 68 } 69 EndBuild(QilNode result)70 public virtual QilNode EndBuild(QilNode result) { 71 if (result == null) { // special door to clean builder state in exception handlers 72 inTheBuild = false; 73 return result; 74 } 75 Debug.Assert(inTheBuild, "StartBuild() wasn't called"); 76 if (result.XmlType.MaybeMany && result.XmlType.IsNode && result.XmlType.IsNotRtf) { 77 result = f.DocOrderDistinct(result); 78 } 79 result = fixupVisitor.Fixup(result, /*environment:*/this.environment); 80 numFixupCurrent -= fixupVisitor.numCurrent ; 81 numFixupPosition -= fixupVisitor.numPosition; 82 numFixupLast -= fixupVisitor.numLast ; 83 84 // All these variables will be positive for "false() and (. = position() + last())" 85 // since QilPatternFactory eliminates the right operand of 'and' 86 Debug.Assert(numFixupCurrent >= 0, "Context fixup error"); 87 Debug.Assert(numFixupPosition >= 0, "Context fixup error"); 88 Debug.Assert(numFixupLast >= 0, "Context fixup error"); 89 inTheBuild = false; 90 return result; 91 } 92 GetCurrentNode()93 private QilNode GetCurrentNode () { numFixupCurrent ++; return fixupCurrent ; } GetCurrentPosition()94 private QilNode GetCurrentPosition() { numFixupPosition ++; return fixupPosition; } GetLastPosition()95 private QilNode GetLastPosition () { numFixupLast ++; return fixupLast ; } 96 String(string value)97 public virtual QilNode String(string value) { 98 return f.String(value); 99 } 100 Number(double value)101 public virtual QilNode Number(double value) { 102 return f.Double(value); 103 } 104 Operator(XPathOperator op, QilNode left, QilNode right)105 public virtual QilNode Operator(XPathOperator op, QilNode left, QilNode right) { 106 Debug.Assert(op != XPathOperator.Unknown); 107 switch (OperatorGroup[(int)op]) { 108 case XPathOperatorGroup.Logical : return LogicalOperator (op, left, right); 109 case XPathOperatorGroup.Equality : return EqualityOperator (op, left, right); 110 case XPathOperatorGroup.Relational : return RelationalOperator(op, left, right); 111 case XPathOperatorGroup.Arithmetic : return ArithmeticOperator(op, left, right); 112 case XPathOperatorGroup.Negate : return NegateOperator (op, left, right); 113 case XPathOperatorGroup.Union : return UnionOperator (op, left, right); 114 default: 115 Debug.Fail(op + " is not a valid XPathOperator"); 116 return null; 117 } 118 } 119 LogicalOperator(XPathOperator op, QilNode left, QilNode right)120 QilNode LogicalOperator(XPathOperator op, QilNode left, QilNode right) { 121 Debug.Assert(op == XPathOperator.Or || op == XPathOperator.And); 122 left = f.ConvertToBoolean(left ); 123 right = f.ConvertToBoolean(right); 124 return ( 125 op == XPathOperator.Or ? f.Or (left, right) : 126 /*default*/ f.And(left, right) 127 ); 128 } 129 CompareValues(XPathOperator op, QilNode left, QilNode right, XmlTypeCode compType)130 QilNode CompareValues(XPathOperator op, QilNode left, QilNode right, XmlTypeCode compType) { 131 Debug.Assert(compType == XmlTypeCode.Boolean || compType == XmlTypeCode.Double || compType == XmlTypeCode.String); 132 Debug.Assert(compType == XmlTypeCode.Boolean || left.XmlType.IsSingleton && right.XmlType.IsSingleton, "Both comparison operands must be singletons"); 133 left = f.ConvertToType(compType, left ); 134 right = f.ConvertToType(compType, right); 135 136 switch (op) { 137 case XPathOperator.Eq : return f.Eq(left, right); 138 case XPathOperator.Ne : return f.Ne(left, right); 139 case XPathOperator.Lt : return f.Lt(left, right); 140 case XPathOperator.Le : return f.Le(left, right); 141 case XPathOperator.Gt : return f.Gt(left, right); 142 case XPathOperator.Ge : return f.Ge(left, right); 143 default : 144 Debug.Fail("Wrong operator type"); 145 return null; 146 } 147 } 148 CompareNodeSetAndValue(XPathOperator op, QilNode nodeset, QilNode val, XmlTypeCode compType)149 QilNode CompareNodeSetAndValue(XPathOperator op, QilNode nodeset, QilNode val, XmlTypeCode compType) { 150 f.CheckNodeSet(nodeset); 151 Debug.Assert(val.XmlType.IsSingleton); 152 Debug.Assert(compType == XmlTypeCode.Boolean || compType == XmlTypeCode.Double || compType == XmlTypeCode.String, "I don't know what to do with RTF here"); 153 if (compType == XmlTypeCode.Boolean || nodeset.XmlType.IsSingleton) { 154 return CompareValues(op, nodeset, val, compType); 155 } else { 156 QilIterator it = f.For(nodeset); 157 return f.Not(f.IsEmpty(f.Filter(it, CompareValues(op, f.XPathNodeValue(it), val, compType)))); 158 } 159 } 160 161 // Inverts relational operator in order to swap operands of the comparison InvertOp(XPathOperator op)162 static XPathOperator InvertOp(XPathOperator op) { 163 return ( 164 op == XPathOperator.Lt ? XPathOperator.Gt : // '<' --> '>' 165 op == XPathOperator.Le ? XPathOperator.Ge : // '<=' --> '>=' 166 op == XPathOperator.Gt ? XPathOperator.Lt : // '>' --> '<' 167 op == XPathOperator.Ge ? XPathOperator.Le : // '>=' --> '<=' 168 /*default:*/ op 169 ); 170 } 171 CompareNodeSetAndNodeSet(XPathOperator op, QilNode left, QilNode right, XmlTypeCode compType)172 QilNode CompareNodeSetAndNodeSet(XPathOperator op, QilNode left, QilNode right, XmlTypeCode compType) { 173 f.CheckNodeSet(left); 174 f.CheckNodeSet(right); 175 if (right.XmlType.IsSingleton) { 176 return CompareNodeSetAndValue(op, /*nodeset:*/left, /*value:*/right, compType); 177 } 178 if (left.XmlType.IsSingleton) { 179 op = InvertOp(op); 180 return CompareNodeSetAndValue(op, /*nodeset:*/right, /*value:*/left, compType); 181 } 182 QilIterator leftEnd = f.For(left ); 183 QilIterator rightEnd = f.For(right); 184 return f.Not(f.IsEmpty(f.Loop(leftEnd, f.Filter(rightEnd, CompareValues(op, f.XPathNodeValue(leftEnd), f.XPathNodeValue(rightEnd), compType))))); 185 } 186 EqualityOperator(XPathOperator op, QilNode left, QilNode right)187 QilNode EqualityOperator(XPathOperator op, QilNode left, QilNode right) { 188 Debug.Assert(op == XPathOperator.Eq || op == XPathOperator.Ne); 189 XmlQueryType leftType = left.XmlType; 190 XmlQueryType rightType = right.XmlType; 191 192 if (f.IsAnyType(left) || f.IsAnyType(right)) { 193 return f.InvokeEqualityOperator(QilOperator[(int)op], left, right); 194 } else if (leftType.IsNode && rightType.IsNode) { 195 return CompareNodeSetAndNodeSet(op, left, right, XmlTypeCode.String); 196 } else if (leftType.IsNode) { 197 return CompareNodeSetAndValue(op, /*nodeset:*/left, /*val:*/right, rightType.TypeCode); 198 } else if (rightType.IsNode) { 199 return CompareNodeSetAndValue(op, /*nodeset:*/right, /*val:*/left, leftType.TypeCode); 200 } else { 201 XmlTypeCode compType = ( 202 leftType.TypeCode == XmlTypeCode.Boolean || rightType.TypeCode == XmlTypeCode.Boolean ? XmlTypeCode.Boolean : 203 leftType.TypeCode == XmlTypeCode.Double || rightType.TypeCode == XmlTypeCode.Double ? XmlTypeCode.Double : 204 /*default:*/ XmlTypeCode.String 205 ); 206 return CompareValues(op, left, right, compType); 207 } 208 } 209 RelationalOperator(XPathOperator op, QilNode left, QilNode right)210 QilNode RelationalOperator(XPathOperator op, QilNode left, QilNode right) { 211 Debug.Assert(op == XPathOperator.Lt || op == XPathOperator.Le || op == XPathOperator.Gt || op == XPathOperator.Ge); 212 XmlQueryType leftType = left.XmlType; 213 XmlQueryType rightType = right.XmlType; 214 215 if (f.IsAnyType(left) || f.IsAnyType(right)) { 216 return f.InvokeRelationalOperator(QilOperator[(int)op], left, right); 217 } else if (leftType.IsNode && rightType.IsNode) { 218 return CompareNodeSetAndNodeSet(op, left, right, XmlTypeCode.Double); 219 } else if (leftType.IsNode) { 220 XmlTypeCode compType = rightType.TypeCode == XmlTypeCode.Boolean ? XmlTypeCode.Boolean : XmlTypeCode.Double; 221 return CompareNodeSetAndValue(op, /*nodeset:*/left, /*val:*/right, compType); 222 } else if (rightType.IsNode) { 223 XmlTypeCode compType = leftType.TypeCode == XmlTypeCode.Boolean ? XmlTypeCode.Boolean : XmlTypeCode.Double; 224 op = InvertOp(op); 225 return CompareNodeSetAndValue(op, /*nodeset:*/right, /*val:*/left, compType); 226 } else { 227 return CompareValues(op, left, right, XmlTypeCode.Double); 228 } 229 } 230 NegateOperator(XPathOperator op, QilNode left, QilNode right)231 QilNode NegateOperator(XPathOperator op, QilNode left, QilNode right) { 232 Debug.Assert(op == XPathOperator.UnaryMinus); 233 Debug.Assert(right == null); 234 return f.Negate(f.ConvertToNumber(left)); 235 } 236 ArithmeticOperator(XPathOperator op, QilNode left, QilNode right)237 QilNode ArithmeticOperator(XPathOperator op, QilNode left, QilNode right) { 238 left = f.ConvertToNumber(left ); 239 right = f.ConvertToNumber(right); 240 switch (op) { 241 case XPathOperator.Plus : return f.Add( left, right); 242 case XPathOperator.Minus : return f.Subtract(left, right); 243 case XPathOperator.Multiply : return f.Multiply(left, right); 244 case XPathOperator.Divide : return f.Divide( left, right); 245 case XPathOperator.Modulo : return f.Modulo( left, right); 246 default : 247 Debug.Fail("Wrong operator type"); 248 return null; 249 } 250 } 251 UnionOperator(XPathOperator op, QilNode left, QilNode right)252 QilNode UnionOperator(XPathOperator op, QilNode left, QilNode right) { 253 Debug.Assert(op == XPathOperator.Union); 254 if (left == null) { 255 return f.EnsureNodeSet(right); 256 } 257 left = f.EnsureNodeSet(left ); 258 right = f.EnsureNodeSet(right); 259 if (left.NodeType == QilNodeType.Sequence) { 260 // ToDo: drop this logic or move it to QilPatternFactory.Union() 261 ((QilList)left).Add(right); 262 return left; 263 } else { 264 return f.Union(left, right); 265 } 266 } 267 268 // also called by XPathPatternBuilder AxisTypeMask(XmlNodeKindFlags inputTypeMask, XPathNodeType nodeType, XPathAxis xpathAxis)269 public static XmlNodeKindFlags AxisTypeMask(XmlNodeKindFlags inputTypeMask, XPathNodeType nodeType, XPathAxis xpathAxis) { 270 return (XmlNodeKindFlags) ( 271 (int) inputTypeMask & 272 (int) XPathNodeType2QilXmlNodeKind[(int) nodeType] & (int) XPathAxisMask[(int) xpathAxis] 273 ); 274 } 275 BuildAxisFilter(QilNode qilAxis, XPathAxis xpathAxis, XPathNodeType nodeType, string name, string nsUri)276 QilNode BuildAxisFilter(QilNode qilAxis, XPathAxis xpathAxis, XPathNodeType nodeType, string name, string nsUri) { 277 XmlNodeKindFlags original = qilAxis.XmlType.NodeKinds; 278 XmlNodeKindFlags required = AxisTypeMask(original, nodeType, xpathAxis); 279 280 QilIterator itr; 281 282 if (required == 0) { 283 return f.Sequence(); 284 } else if (required == original) { 285 } else { 286 qilAxis = f.Filter(itr = f.For(qilAxis), f.IsType(itr, T.NodeChoice(required))); 287 qilAxis.XmlType = T.PrimeProduct(T.NodeChoice(required), qilAxis.XmlType.Cardinality); 288 289 290 // Without code bellow IlGeneragion gives stack overflow exception for the following passage. 291 //<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"> 292 // <xsl:template match="/"> 293 // <xsl:value-of select="descendant::author/@id | comment()" /> 294 // </xsl:template> 295 //</xsl:stylesheet> 296 297 // ToDo: remove this code when IlGen bug will be fixed. 298 if (qilAxis.NodeType == QilNodeType.Filter) { 299 QilLoop filter = (QilLoop) qilAxis; 300 filter.Body = f.And(filter.Body, 301 name != null && nsUri != null ? f.Eq(f.NameOf(itr), f.QName(name, nsUri)) : // ns:bar || bar 302 nsUri != null ? f.Eq(f.NamespaceUriOf(itr), f.String(nsUri)) : // ns:* 303 name != null ? f.Eq(f.LocalNameOf(itr), f.String(name)) : // *:foo 304 /*name == nsUri == null*/ f.True() // * 305 ); 306 return filter; 307 } 308 } 309 310 return f.Filter(itr = f.For(qilAxis), 311 name != null && nsUri != null ? f.Eq(f.NameOf(itr), f.QName(name, nsUri)) : // ns:bar || bar 312 nsUri != null ? f.Eq(f.NamespaceUriOf(itr), f.String(nsUri)) : // ns:* 313 name != null ? f.Eq(f.LocalNameOf(itr), f.String(name)) : // *:foo 314 /*name == nsUri == null*/ f.True() // * 315 ); 316 } 317 318 // XmlNodeKindFlags from XPathNodeType 319 static XmlNodeKindFlags[] XPathNodeType2QilXmlNodeKind = { 320 /*Root */ XmlNodeKindFlags.Document, 321 /*Element */ XmlNodeKindFlags.Element, 322 /*Attribute */ XmlNodeKindFlags.Attribute, 323 /*Namespace */ XmlNodeKindFlags.Namespace, 324 /*Text */ XmlNodeKindFlags.Text, 325 /*SignificantWhitespace*/ XmlNodeKindFlags.Text, 326 /*Whitespace */ XmlNodeKindFlags.Text, 327 /*ProcessingInstruction*/ XmlNodeKindFlags.PI, 328 /*Comment */ XmlNodeKindFlags.Comment, 329 /*All */ XmlNodeKindFlags.Any 330 }; 331 BuildAxis(XPathAxis xpathAxis, XPathNodeType nodeType, string nsUri, string name)332 QilNode BuildAxis(XPathAxis xpathAxis, XPathNodeType nodeType, string nsUri, string name) { 333 QilNode currentNode = GetCurrentNode(); 334 QilNode qilAxis; 335 336 switch (xpathAxis) { 337 case XPathAxis.Ancestor : qilAxis = f.Ancestor (currentNode); break; 338 case XPathAxis.AncestorOrSelf : qilAxis = f.AncestorOrSelf (currentNode); break; 339 case XPathAxis.Attribute : qilAxis = f.Content (currentNode); break; 340 case XPathAxis.Child : qilAxis = f.Content (currentNode); break; 341 case XPathAxis.Descendant : qilAxis = f.Descendant (currentNode); break; 342 case XPathAxis.DescendantOrSelf : qilAxis = f.DescendantOrSelf (currentNode); break; 343 case XPathAxis.Following : qilAxis = f.XPathFollowing (currentNode); break; 344 case XPathAxis.FollowingSibling : qilAxis = f.FollowingSibling (currentNode); break; 345 case XPathAxis.Namespace : qilAxis = f.XPathNamespace (currentNode); break; 346 case XPathAxis.Parent : qilAxis = f.Parent (currentNode); break; 347 case XPathAxis.Preceding : qilAxis = f.XPathPreceding (currentNode); break; 348 case XPathAxis.PrecedingSibling : qilAxis = f.PrecedingSibling (currentNode); break; 349 case XPathAxis.Self : qilAxis = (currentNode); break; 350 // Can be done using BuildAxisFilter() but f.Root() sets wrong XmlNodeKindFlags 351 case XPathAxis.Root : return f.Root (currentNode); 352 default : 353 qilAxis = null; 354 Debug.Fail("Invalid EnumValue 'XPathAxis'"); 355 break; 356 } 357 358 QilNode result = BuildAxisFilter(qilAxis, xpathAxis, nodeType, name, nsUri); 359 if ( 360 xpathAxis == XPathAxis.Ancestor || xpathAxis == XPathAxis.Preceding || 361 xpathAxis == XPathAxis.AncestorOrSelf || xpathAxis == XPathAxis.PrecedingSibling 362 ) { 363 result = f.BaseFactory.DocOrderDistinct(result); 364 // To make grouping operator NOP we should always return path expressions in DOD. 365 // I can't use Pattern factory here becasue Predicate() depends on fact that DOD() is 366 // outmost node in reverse steps 367 } 368 return result; 369 } 370 Axis(XPathAxis xpathAxis, XPathNodeType nodeType, string prefix, string name)371 public virtual QilNode Axis(XPathAxis xpathAxis, XPathNodeType nodeType, string prefix, string name) { 372 string nsUri = prefix == null ? null : this.environment.ResolvePrefix(prefix); 373 return BuildAxis(xpathAxis, nodeType, nsUri, name); 374 } 375 376 // "left/right" JoinStep(QilNode left, QilNode right)377 public virtual QilNode JoinStep(QilNode left, QilNode right) { 378 f.CheckNodeSet(right); 379 QilIterator leftIt = f.For(f.EnsureNodeSet(left)); 380 // in XPath 1.0 step is always nodetest and as a result it can't contain last(). 381 right = fixupVisitor.Fixup(right, /*current:*/leftIt, /*last:*/null); 382 numFixupCurrent -= fixupVisitor.numCurrent ; 383 numFixupPosition -= fixupVisitor.numPosition; 384 numFixupLast -= fixupVisitor.numLast ; 385 return f.DocOrderDistinct(f.Loop(leftIt, right)); 386 } 387 388 // "nodeset[predicate]" 389 // XPath spec $3.3 (para 5) Predicate(QilNode nodeset, QilNode predicate, bool isReverseStep)390 public virtual QilNode Predicate(QilNode nodeset, QilNode predicate, bool isReverseStep) { 391 if (isReverseStep) { 392 Debug.Assert(nodeset.NodeType == QilNodeType.DocOrderDistinct, 393 "ReverseAxe in Qil is actuly reverse and we compile them here in builder by wrapping to DocOrderDistinct()" 394 ); 395 // The trick here is that we unwarp it back, compile as regular predicate and wrap again. 396 // this way this wat we hold invariant that path expresion are always DOD and make predicates on reverse axe 397 // work as specified in XPath 2.0 FS: http://www.w3.org/TR/xquery-semantics/#id-axis-steps 398 nodeset = ((QilUnary)nodeset).Child; 399 } 400 401 predicate = PredicateToBoolean(predicate, f, this); 402 403 return BuildOnePredicate(nodeset, predicate, isReverseStep, f, fixupVisitor, ref numFixupCurrent, ref numFixupPosition, ref numFixupLast); 404 } 405 406 //also used by XPathPatternBuilder PredicateToBoolean(QilNode predicate, XPathQilFactory f, IXPathEnvironment env)407 public static QilNode PredicateToBoolean(QilNode predicate, XPathQilFactory f, IXPathEnvironment env) { 408 // Prepocess predicate: if (predicate is number) then predicate := (position() == predicate) 409 if (!f.IsAnyType(predicate)) { 410 if (predicate.XmlType.TypeCode == XmlTypeCode.Double) { 411 predicate = f.Eq(env.GetPosition(), predicate); 412 } else { 413 predicate = f.ConvertToBoolean(predicate); 414 } 415 } else { 416 QilIterator i; 417 predicate = f.Loop(i = f.Let(predicate), 418 f.Conditional(f.IsType(i, T.Double), 419 f.Eq(env.GetPosition(), f.TypeAssert(i, T.DoubleX)), 420 f.ConvertToBoolean(i) 421 ) 422 ); 423 } 424 return predicate; 425 } 426 427 //also used by XPathPatternBuilder BuildOnePredicate(QilNode nodeset, QilNode predicate, bool isReverseStep, XPathQilFactory f, FixupVisitor fixupVisitor, ref int numFixupCurrent, ref int numFixupPosition, ref int numFixupLast)428 public static QilNode BuildOnePredicate(QilNode nodeset, QilNode predicate, bool isReverseStep, 429 XPathQilFactory f, FixupVisitor fixupVisitor, 430 ref int numFixupCurrent, ref int numFixupPosition, ref int numFixupLast) { 431 nodeset = f.EnsureNodeSet(nodeset); 432 433 // Mirgeing nodeset and predicate: 434 // 1. Predicate contains 0 last() : 435 // for $i in nodeset 436 // where predicate 437 // return $i 438 // ToDo: Currently we are keepeing old output to minimize diff. 439 // 2. Predicate contains 1 last() 440 // let $cach := nodeset return 441 // for $i in $cach 442 // where predicate(length($cach)) 443 // return $i 444 // ToDo: This is a little optimisation we can do or don't do. 445 // 3. Predicate contains 2+ last() 446 // let $cash := nodeset return 447 // let $size := length($cash) return 448 // for $i in $cash 449 // where predicate($size) 450 // return $i 451 452 QilNode result; 453 if (numFixupLast != 0 && fixupVisitor.CountUnfixedLast(predicate) != 0) { 454 // this subtree has unfixed last() nodes 455 QilIterator cash = f.Let(nodeset); 456 QilIterator size = f.Let(f.XsltConvert(f.Length(cash), T.DoubleX)); 457 QilIterator it = f.For(cash); 458 predicate = fixupVisitor.Fixup(predicate, /*current:*/it, /*last:*/size); 459 numFixupCurrent -= fixupVisitor.numCurrent; 460 numFixupPosition -= fixupVisitor.numPosition; 461 numFixupLast -= fixupVisitor.numLast; 462 result = f.Loop(cash, f.Loop(size, f.Filter(it, predicate))); 463 } else { 464 QilIterator it = f.For(nodeset); 465 predicate = fixupVisitor.Fixup(predicate, /*current:*/it, /*last:*/null); 466 numFixupCurrent -= fixupVisitor.numCurrent; 467 numFixupPosition -= fixupVisitor.numPosition; 468 numFixupLast -= fixupVisitor.numLast; 469 result = f.Filter(it, predicate); 470 } 471 if (isReverseStep) { 472 result = f.DocOrderDistinct(result); 473 } 474 return result; 475 } 476 Variable(string prefix, string name)477 public virtual QilNode Variable(string prefix, string name) { 478 return this.environment.ResolveVariable(prefix, name); 479 } 480 Function(string prefix, string name, IList<QilNode> args)481 public virtual QilNode Function(string prefix, string name, IList<QilNode> args) { 482 Debug.Assert(!args.IsReadOnly, "Writable collection expected"); 483 if (prefix.Length == 0) { 484 FunctionInfo func; 485 if (FunctionTable.TryGetValue(name, out func)) { 486 func.CastArguments(args, name, f); 487 488 switch (func.id) { 489 case FuncId.Not : return f.Not(args[0]); 490 case FuncId.Last : return GetLastPosition(); 491 case FuncId.Position : return GetCurrentPosition(); 492 case FuncId.Count : return f.XsltConvert(f.Length(f.DocOrderDistinct(args[0])), T.DoubleX); 493 case FuncId.LocalName : return args.Count == 0 ? f.LocalNameOf(GetCurrentNode()) : LocalNameOfFirstNode(args[0]); 494 case FuncId.NamespaceUri : return args.Count == 0 ? f.NamespaceUriOf(GetCurrentNode()) : NamespaceOfFirstNode(args[0]); 495 case FuncId.Name : return args.Count == 0 ? NameOf(GetCurrentNode()) : NameOfFirstNode(args[0]); 496 case FuncId.String : return args.Count == 0 ? f.XPathNodeValue(GetCurrentNode()) : f.ConvertToString(args[0]); 497 case FuncId.Number : return args.Count == 0 ? f.XsltConvert(f.XPathNodeValue(GetCurrentNode()), T.DoubleX) : f.ConvertToNumber(args[0]); 498 case FuncId.Boolean : return f.ConvertToBoolean(args[0]); 499 case FuncId.True : return f.True(); 500 case FuncId.False : return f.False(); 501 case FuncId.Id : return f.DocOrderDistinct(f.Id(GetCurrentNode(), args[0])); 502 case FuncId.Concat : return f.StrConcat(args); 503 case FuncId.StartsWith : return f.InvokeStartsWith(args[0], args[1]); 504 case FuncId.Contains : return f.InvokeContains(args[0], args[1]); 505 case FuncId.SubstringBefore : return f.InvokeSubstringBefore(args[0], args[1]); 506 case FuncId.SubstringAfter : return f.InvokeSubstringAfter(args[0], args[1]); 507 case FuncId.Substring : 508 return args.Count == 2 ? f.InvokeSubstring(args[0], args[1]) : f.InvokeSubstring(args[0], args[1], args[2]); 509 case FuncId.StringLength : 510 return f.XsltConvert(f.StrLength(args.Count == 0 ? f.XPathNodeValue(GetCurrentNode()) : args[0]), T.DoubleX); 511 case FuncId.Normalize : 512 return f.InvokeNormalizeSpace(args.Count == 0 ? f.XPathNodeValue(GetCurrentNode()) : args[0]); 513 case FuncId.Translate : return f.InvokeTranslate(args[0], args[1], args[2]); 514 case FuncId.Lang : return f.InvokeLang(args[0], GetCurrentNode()); 515 case FuncId.Sum : return Sum(f.DocOrderDistinct(args[0])); 516 case FuncId.Floor : return f.InvokeFloor(args[0]); 517 case FuncId.Ceiling : return f.InvokeCeiling(args[0]); 518 case FuncId.Round : return f.InvokeRound(args[0]); 519 default: 520 Debug.Fail(func.id + " is present in the function table, but absent from the switch"); 521 return null; 522 } 523 } 524 } 525 526 return this.environment.ResolveFunction(prefix, name, args, (IFocus)this); 527 } 528 LocalNameOfFirstNode(QilNode arg)529 QilNode LocalNameOfFirstNode(QilNode arg) { 530 f.CheckNodeSet(arg); 531 if (arg.XmlType.IsSingleton) { 532 return f.LocalNameOf(arg); 533 } else { 534 QilIterator i; 535 return f.StrConcat(f.Loop(i = f.FirstNode(arg), f.LocalNameOf(i))); 536 } 537 } 538 NamespaceOfFirstNode(QilNode arg)539 QilNode NamespaceOfFirstNode(QilNode arg) { 540 f.CheckNodeSet(arg); 541 if (arg.XmlType.IsSingleton) { 542 return f.NamespaceUriOf(arg); 543 } else { 544 QilIterator i; 545 return f.StrConcat(f.Loop(i = f.FirstNode(arg), f.NamespaceUriOf(i))); 546 } 547 } 548 NameOf(QilNode arg)549 QilNode NameOf(QilNode arg) { 550 f.CheckNodeNotRtf(arg); 551 // ToDo: NameOf QIL node returns QName, so we cannot use it here. 552 // We may want to introduce a new QIL node that returns a string. 553 if (arg is QilIterator) { 554 QilIterator p, ln; 555 return f.Loop(p = f.Let(f.PrefixOf(arg)), f.Loop(ln = f.Let(f.LocalNameOf(arg)), 556 f.Conditional(f.Eq(f.StrLength(p), f.Int32(0)), ln, f.StrConcat(p, f.String(":"), ln) 557 ))); 558 } else { 559 QilIterator let = f.Let(arg); 560 return f.Loop(let, /*recursion:*/NameOf(let)); 561 } 562 } 563 NameOfFirstNode(QilNode arg)564 QilNode NameOfFirstNode(QilNode arg) { 565 f.CheckNodeSet(arg); 566 if (arg.XmlType.IsSingleton) { 567 return NameOf(arg); 568 } else { 569 QilIterator i; 570 return f.StrConcat(f.Loop(i = f.FirstNode(arg), NameOf(i))); 571 } 572 } 573 Sum(QilNode arg)574 QilNode Sum(QilNode arg) { 575 f.CheckNodeSet(arg); 576 QilIterator i; 577 return f.Sum(f.Sequence(f.Double(0d), f.Loop(i = f.For(arg), f.ConvertToNumber(i)))); 578 } 579 580 enum XPathOperatorGroup { 581 Unknown , 582 Logical , 583 Equality , 584 Relational, 585 Arithmetic, 586 Negate , 587 Union , 588 } 589 590 static XPathOperatorGroup[] OperatorGroup = { 591 /*Unknown */ XPathOperatorGroup.Unknown , 592 /*Or */ XPathOperatorGroup.Logical , 593 /*And */ XPathOperatorGroup.Logical , 594 /*Eq */ XPathOperatorGroup.Equality , 595 /*Ne */ XPathOperatorGroup.Equality , 596 /*Lt */ XPathOperatorGroup.Relational, 597 /*Le */ XPathOperatorGroup.Relational, 598 /*Gt */ XPathOperatorGroup.Relational, 599 /*Ge */ XPathOperatorGroup.Relational, 600 /*Plus */ XPathOperatorGroup.Arithmetic, 601 /*Minus */ XPathOperatorGroup.Arithmetic, 602 /*Multiply */ XPathOperatorGroup.Arithmetic, 603 /*Divide */ XPathOperatorGroup.Arithmetic, 604 /*Modulo */ XPathOperatorGroup.Arithmetic, 605 /*UnaryMinus*/ XPathOperatorGroup.Negate , 606 /*Union */ XPathOperatorGroup.Union , 607 }; 608 609 static QilNodeType[] QilOperator = { 610 /*Unknown */ QilNodeType.Unknown , 611 /*Or */ QilNodeType.Or , 612 /*And */ QilNodeType.And , 613 /*Eq */ QilNodeType.Eq , 614 /*Ne */ QilNodeType.Ne , 615 /*Lt */ QilNodeType.Lt , 616 /*Le */ QilNodeType.Le , 617 /*Gt */ QilNodeType.Gt , 618 /*Ge */ QilNodeType.Ge , 619 /*Plus */ QilNodeType.Add , 620 /*Minus */ QilNodeType.Subtract, 621 /*Multiply */ QilNodeType.Multiply, 622 /*Divide */ QilNodeType.Divide , 623 /*Modulo */ QilNodeType.Modulo , 624 /*UnaryMinus */ QilNodeType.Negate , 625 /*Union */ QilNodeType.Sequence, 626 }; 627 628 // XmlNodeType(s) of nodes by XPathAxis 629 static XmlNodeKindFlags[] XPathAxisMask = { 630 /*Unknown */ XmlNodeKindFlags.None, 631 /*Ancestor */ XmlNodeKindFlags.Element | XmlNodeKindFlags.Document, 632 /*AncestorOrSelf */ XmlNodeKindFlags.Any, 633 /*Attribute */ XmlNodeKindFlags.Attribute, 634 /*Child */ XmlNodeKindFlags.Content, 635 /*Descendant */ XmlNodeKindFlags.Content, 636 /*DescendantOrSelf*/ XmlNodeKindFlags.Any, 637 /*Following */ XmlNodeKindFlags.Content, 638 /*FollowingSibling*/ XmlNodeKindFlags.Content, 639 /*Namespace */ XmlNodeKindFlags.Namespace, 640 /*Parent */ XmlNodeKindFlags.Element | XmlNodeKindFlags.Document, 641 /*Preceding */ XmlNodeKindFlags.Content, 642 /*PrecedingSibling*/ XmlNodeKindFlags.Content, 643 /*Self */ XmlNodeKindFlags.Any, 644 /*Root */ XmlNodeKindFlags.Document, 645 }; 646 647 // ---------------------------------------------------------------- 648 internal enum FuncId { 649 Last = 0, 650 Position, 651 Count, 652 LocalName, 653 NamespaceUri, 654 Name, 655 String, 656 Number, 657 Boolean, 658 True, 659 False, 660 Not, 661 Id, 662 Concat, 663 StartsWith, 664 Contains, 665 SubstringBefore, 666 SubstringAfter, 667 Substring, 668 StringLength, 669 Normalize, 670 Translate, 671 Lang, 672 Sum, 673 Floor, 674 Ceiling, 675 Round 676 }; 677 678 public static readonly XmlTypeCode[] argAny = {XmlTypeCode.Item}; 679 public static readonly XmlTypeCode[] argNodeSet = {XmlTypeCode.Node}; 680 public static readonly XmlTypeCode[] argBoolean = {XmlTypeCode.Boolean}; 681 public static readonly XmlTypeCode[] argDouble = {XmlTypeCode.Double}; 682 public static readonly XmlTypeCode[] argString = {XmlTypeCode.String}; 683 public static readonly XmlTypeCode[] argString2 = {XmlTypeCode.String, XmlTypeCode.String}; 684 public static readonly XmlTypeCode[] argString3 = {XmlTypeCode.String, XmlTypeCode.String, XmlTypeCode.String}; 685 public static readonly XmlTypeCode[] argFnSubstr = {XmlTypeCode.String, XmlTypeCode.Double, XmlTypeCode.Double}; 686 687 public static Dictionary<string, FunctionInfo> FunctionTable = CreateFunctionTable(); CreateFunctionTable()688 private static Dictionary<string, FunctionInfo> CreateFunctionTable() { 689 Dictionary<string, FunctionInfo> table = new Dictionary<string, FunctionInfo>(36); 690 table.Add("last" , new FunctionInfo(FuncId.Last , 0, 0, null)); 691 table.Add("position" , new FunctionInfo(FuncId.Position , 0, 0, null)); 692 table.Add("name" , new FunctionInfo(FuncId.Name , 0, 1, argNodeSet)); 693 table.Add("namespace-uri" , new FunctionInfo(FuncId.NamespaceUri , 0, 1, argNodeSet)); 694 table.Add("local-name" , new FunctionInfo(FuncId.LocalName , 0, 1, argNodeSet)); 695 table.Add("count" , new FunctionInfo(FuncId.Count , 1, 1, argNodeSet)); 696 table.Add("id" , new FunctionInfo(FuncId.Id , 1, 1, argAny)); 697 table.Add("string" , new FunctionInfo(FuncId.String , 0, 1, argAny)); 698 table.Add("concat" , new FunctionInfo(FuncId.Concat , 2, FunctionInfo.Infinity, null)); 699 table.Add("starts-with" , new FunctionInfo(FuncId.StartsWith , 2, 2, argString2)); 700 table.Add("contains" , new FunctionInfo(FuncId.Contains , 2, 2, argString2)); 701 table.Add("substring-before" , new FunctionInfo(FuncId.SubstringBefore, 2, 2, argString2)); 702 table.Add("substring-after" , new FunctionInfo(FuncId.SubstringAfter , 2, 2, argString2)); 703 table.Add("substring" , new FunctionInfo(FuncId.Substring , 2, 3, argFnSubstr)); 704 table.Add("string-length" , new FunctionInfo(FuncId.StringLength , 0, 1, argString)); 705 table.Add("normalize-space" , new FunctionInfo(FuncId.Normalize , 0, 1, argString)); 706 table.Add("translate" , new FunctionInfo(FuncId.Translate , 3, 3, argString3)); 707 table.Add("boolean" , new FunctionInfo(FuncId.Boolean , 1, 1, argAny)); 708 table.Add("not" , new FunctionInfo(FuncId.Not , 1, 1, argBoolean)); 709 table.Add("true" , new FunctionInfo(FuncId.True , 0, 0, null)); 710 table.Add("false" , new FunctionInfo(FuncId.False , 0, 0, null)); 711 table.Add("lang" , new FunctionInfo(FuncId.Lang , 1, 1, argString)); 712 table.Add("number" , new FunctionInfo(FuncId.Number , 0, 1, argAny)); 713 table.Add("sum" , new FunctionInfo(FuncId.Sum , 1, 1, argNodeSet)); 714 table.Add("floor" , new FunctionInfo(FuncId.Floor , 1, 1, argDouble)); 715 table.Add("ceiling" , new FunctionInfo(FuncId.Ceiling , 1, 1, argDouble)); 716 table.Add("round" , new FunctionInfo(FuncId.Round , 1, 1, argDouble)); 717 return table; 718 } 719 IsFunctionAvailable(string localName, string nsUri)720 public static bool IsFunctionAvailable(string localName, string nsUri) { 721 if (nsUri.Length != 0) { 722 return false; 723 } 724 return FunctionTable.ContainsKey(localName); 725 } 726 727 internal class FixupVisitor : QilReplaceVisitor { 728 new QilPatternFactory f; 729 QilNode fixupCurrent, fixupPosition, fixupLast; // fixup nodes we are replacing 730 QilIterator current; 731 QilNode last; // expressions we are using to replace fixupNodes 732 bool justCount; // Don't change tree, just count 733 IXPathEnvironment environment; // temp solution 734 public int numCurrent, numPosition, numLast; // here we are counting all replacements we have made 735 FixupVisitor(QilPatternFactory f, QilNode fixupCurrent, QilNode fixupPosition, QilNode fixupLast)736 public FixupVisitor(QilPatternFactory f, QilNode fixupCurrent, QilNode fixupPosition, QilNode fixupLast) : base(f.BaseFactory) { 737 this.f = f; 738 this.fixupCurrent = fixupCurrent; 739 this.fixupPosition = fixupPosition; 740 this.fixupLast = fixupLast ; 741 } 742 Fixup(QilNode inExpr, QilIterator current, QilNode last)743 public QilNode Fixup(QilNode inExpr, QilIterator current, QilNode last) { 744 QilDepthChecker.Check(inExpr); 745 this.current = current ; 746 this.last = last ; 747 Debug.Assert(current != null); 748 this.justCount = false; 749 this.environment = null; 750 numCurrent = numPosition = numLast = 0; 751 inExpr = VisitAssumeReference(inExpr); 752 #if StopMaskOptimisation 753 SetStopVisitMark(inExpr, /*stop*/true); 754 #endif 755 return inExpr; 756 } 757 Fixup(QilNode inExpr, IXPathEnvironment environment)758 public QilNode Fixup(QilNode inExpr, IXPathEnvironment environment) { 759 Debug.Assert(environment != null); 760 QilDepthChecker.Check(inExpr); 761 this.justCount = false; 762 this.current = null; 763 this.environment = environment; 764 numCurrent = numPosition = numLast = 0; 765 inExpr = VisitAssumeReference(inExpr); 766 #if StopMaskOptimisation 767 // Don't need 768 //SetStopVisitMark(inExpr, /*stop*/true); 769 #endif 770 return inExpr; 771 } 772 CountUnfixedLast(QilNode inExpr)773 public int CountUnfixedLast(QilNode inExpr) { 774 this.justCount = true; 775 numCurrent = numPosition = numLast = 0; 776 VisitAssumeReference(inExpr); 777 return numLast; 778 } 779 VisitUnknown(QilNode unknown)780 protected override QilNode VisitUnknown(QilNode unknown) { 781 Debug.Assert(unknown.NodeType == QilNodeType.Unknown); 782 if (unknown == fixupCurrent) { 783 numCurrent ++; 784 if (! justCount) { 785 if (this.environment != null) { 786 unknown = this.environment.GetCurrent(); 787 } else if (this.current != null) { 788 unknown = this.current; 789 } 790 } 791 } else if (unknown == fixupPosition) { 792 numPosition ++; 793 if (! justCount) { 794 if (this.environment != null) { 795 unknown = this.environment.GetPosition(); 796 } else if (this.current != null) { 797 // position can be in predicate only and in predicate current olways an iterator 798 unknown = f.XsltConvert(f.PositionOf((QilIterator)this.current), T.DoubleX); 799 } 800 } 801 } else if (unknown == fixupLast) { 802 numLast ++; 803 if (! justCount) { 804 if (this.environment != null) { 805 unknown = this.environment.GetLast(); 806 } else if (this.current != null) { 807 Debug.Assert(this.last != null); 808 unknown = this.last; 809 } 810 } 811 } 812 Debug.Assert(unknown != null); 813 return unknown; 814 } 815 816 #if StopMaskOptimisation 817 // This optimisation marks subtrees that was fixed already and prevents FixupVisitor from 818 // visiting them again. The logic is brokken, because when unfixed tree is added inside fixed one 819 // it never fixed anymore. 820 // This happens in all cortasian productions now. 821 // Excample "a/b=c". 'c' is added inside 'b' 822 823 // I belive some optimisation is posible and would be nice to have. 824 // We may change the way we generating cortasian product. 825 Visit(QilNode n)826 protected override QilNode Visit(QilNode n) { 827 if (GetStopVisitMark(n)) { 828 // Optimisation: 829 // This subtree was fixed already. No need to go inside it. 830 if (! justCount) { 831 SetStopVisitMark(n, /*stop*/false); // We clean this annotation 832 } 833 return n; 834 } 835 return base.Visit(n); 836 } 837 SetStopVisitMark(QilNode n, bool stop)838 void SetStopVisitMark(QilNode n, bool stop) { 839 if (n.Type != QilNodeType.For && n.Type != QilNodeType.Let) { 840 XsltAnnotation.Write(n)[0] = (stop ? /*any object*/fixupCurrent : null); 841 } else { 842 // we shouldn't alter annotation of "reference" nodes (Iterators, Functions, ...) 843 } 844 } GetStopVisitMark(QilNode n)845 bool GetStopVisitMark(QilNode n) { 846 return XsltAnnotation.Write(n)[0] != null; 847 } 848 #endif 849 } 850 851 internal class FunctionInfo<T> { 852 public T id; 853 public int minArgs; 854 public int maxArgs; 855 public XmlTypeCode[] argTypes; 856 857 public const int Infinity = int.MaxValue; 858 FunctionInfo(T id, int minArgs, int maxArgs, XmlTypeCode[] argTypes)859 public FunctionInfo(T id, int minArgs, int maxArgs, XmlTypeCode[] argTypes) { 860 Debug.Assert(maxArgs == 0 || maxArgs == Infinity || argTypes != null && argTypes.Length == maxArgs); 861 this.id = id; 862 this.minArgs = minArgs; 863 this.maxArgs = maxArgs; 864 this.argTypes = argTypes; 865 } 866 CheckArity(int minArgs, int maxArgs, string name, int numArgs)867 public static void CheckArity(int minArgs, int maxArgs, string name, int numArgs) { 868 if (minArgs <= numArgs && numArgs <= maxArgs) { 869 return; 870 } 871 872 // Possible cases: 873 // [0, 0], [1, 1], [2, 2], [3, 3] 874 // [0, 1], [1, 2], [2, 3], [2, +inf] 875 // [1, 3], [2, 4] 876 string resId; 877 if (minArgs == maxArgs) { 878 resId = Res.XPath_NArgsExpected; 879 } else { 880 if (maxArgs == minArgs + 1) { 881 resId = Res.XPath_NOrMArgsExpected; 882 } else if (numArgs < minArgs) { 883 resId = Res.XPath_AtLeastNArgsExpected; 884 } else { 885 // This case is impossible for standard XPath/XSLT functions 886 Debug.Assert(numArgs > maxArgs); 887 resId = Res.XPath_AtMostMArgsExpected; 888 } 889 } 890 throw new XPathCompileException(resId, name, minArgs.ToString(CultureInfo.InvariantCulture), maxArgs.ToString(CultureInfo.InvariantCulture)); 891 } 892 CastArguments(IList<QilNode> args, string name, XPathQilFactory f)893 public void CastArguments(IList<QilNode> args, string name, XPathQilFactory f) { 894 CheckArity(this.minArgs, this.maxArgs, name, args.Count); 895 896 // Convert arguments to the appropriate types 897 if (maxArgs == Infinity) { 898 // Special case for concat() function 899 for (int i = 0; i < args.Count; i++) { 900 args[i] = f.ConvertToType(XmlTypeCode.String, args[i]); 901 } 902 } else { 903 for (int i = 0; i < args.Count; i++) { 904 if (argTypes[i] == XmlTypeCode.Node && f.CannotBeNodeSet(args[i])) { 905 throw new XPathCompileException(Res.XPath_NodeSetArgumentExpected, name, (i + 1).ToString(CultureInfo.InvariantCulture)); 906 } 907 args[i] = f.ConvertToType(argTypes[i], args[i]); 908 } 909 } 910 } 911 } 912 } 913 } 914