mcs/class/referencesource/System.Data.SqlXml/System/Xml/Xsl/XPath/XPathBuilder.cs

   1 //------------------------------------------------------------------------------
   2 // <copyright file="XPathBuilder.cs" company="Microsoft">
   3 //     Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 // <owner current="true" primary="true">[....]</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         */
  37         QilNode IFocus.GetCurrent()  { return GetCurrentNode    (); }
  38         QilNode IFocus.GetPosition() { return GetCurrentPosition(); }
  39         QilNode IFocus.GetLast()     { return GetLastPosition   (); }
  40
  41         XPathQilFactory IXPathEnvironment.Factory   { get { return f; } }
  42
  43         QilNode IXPathEnvironment.ResolveVariable(string prefix, string name) {
  44             return Variable(prefix, name);
  45         }
  46         QilNode IXPathEnvironment.ResolveFunction(string prefix, string name, IList<QilNode> args, IFocus env) {
  47             Debug.Fail("Must not be called");
  48             return null;
  49         }
  50         string  IXPathEnvironment.ResolvePrefix(string prefix) {
  51             return environment.ResolvePrefix(prefix);
  52         }
  53         //  ----------------------------------------------------------------------------
  54
  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
  64         public virtual void StartBuild() {
  65             Debug.Assert(! inTheBuild, "XPathBuilder is busy!");
  66             inTheBuild = true;
  67             numFixupCurrent = numFixupPosition = numFixupLast = 0;
  68         }
  69
  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
  93         private QilNode GetCurrentNode    () { numFixupCurrent  ++; return fixupCurrent ; }
  94         private QilNode GetCurrentPosition() { numFixupPosition ++; return fixupPosition; }
  95         private QilNode GetLastPosition   () { numFixupLast     ++; return fixupLast    ; }
  96
  97         public virtual QilNode String(string value) {
  98             return f.String(value);
  99         }
 100
 101         public virtual QilNode Number(double value) {
 102             return f.Double(value);
 103         }
 104
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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"
 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)
 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
 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
 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
 477         public virtual QilNode Variable(string prefix, string name) {
 478             return this.environment.ResolveVariable(prefix, name);
 479         }
 480
 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
 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
 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
 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
 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
 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();
 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
 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
 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
 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
 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
 773             public int CountUnfixedLast(QilNode inExpr) {
 774                 this.justCount  = true;
 775                 numCurrent = numPosition = numLast = 0;
 776                 VisitAssumeReference(inExpr);
 777                 return numLast;
 778             }
 779
 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
 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
 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             }
 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
 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
 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
 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 }