mcs/class/referencesource/System.Data.SqlXml/System/Xml/Xsl/IlGen/XmlIlVisitor.cs

   1 //------------------------------------------------------------------------------
   2 // <copyright file="XmlIlVisitor.cs" company="Microsoft">
   3 //     Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 // <owner current="true" primary="true">Microsoft</owner>
   6 //------------------------------------------------------------------------------
   7 using System;
   8 using System.Xml;
   9 using System.Xml.XPath;
  10 using System.Xml.Schema;
  11 using System.Globalization;
  12 using System.Collections;
  13 using System.Collections.Generic;
  14 using System.Diagnostics;
  15 using System.Reflection;
  16 using System.Reflection.Emit;
  17 using System.Xml.Xsl;
  18 using System.Xml.Xsl.Qil;
  19 using System.Xml.Xsl.Runtime;
  20
  21 namespace System.Xml.Xsl.IlGen {
  22     using TypeFactory   = System.Xml.Xsl.XmlQueryTypeFactory;
  23     using Res           = System.Xml.Utils.Res;
  24
  25     /// <summary>
  26     /// Creates Msil code for an entire QilExpression graph.  Code is generated in one of two modes: push or
  27     /// pull.  In push mode, code is generated to push the values in an iterator to the XmlWriter
  28     /// interface.  In pull mode, the values in an iterator are stored in a physical location such as
  29     /// the stack or a local variable by an iterator.  The iterator is passive, and will just wait for
  30     /// a caller to pull the data and/or instruct the iterator to enumerate the next value.
  31     /// </summary>
  32     internal class XmlILVisitor : QilVisitor {
  33         private QilExpression qil;
  34         private GenerateHelper helper;
  35         private IteratorDescriptor iterCurr, iterNested;
  36         private int indexId;
  37
  38
  39         //-----------------------------------------------
  40         // Entry
  41         //-----------------------------------------------
  42
  43         /// <summary>
  44         /// Visits the specified QilExpression graph and generates MSIL code.
  45         /// </summary>
  46         public void Visit(QilExpression qil, GenerateHelper helper, MethodInfo methRoot) {
  47             this.qil = qil;
  48             this.helper = helper;
  49             this.iterNested = null;
  50             this.indexId = 0;
  51
  52             // Prepare each global parameter and global variable to be visited
  53             PrepareGlobalValues(qil.GlobalParameterList);
  54             PrepareGlobalValues(qil.GlobalVariableList);
  55
  56             // Visit each global parameter and global variable
  57             VisitGlobalValues(qil.GlobalParameterList);
  58             VisitGlobalValues(qil.GlobalVariableList);
  59
  60             // Build each function
  61             foreach (QilFunction ndFunc in qil.FunctionList) {
  62                 // Visit each parameter and the function body
  63                 Function(ndFunc);
  64             }
  65
  66             // Build the root expression
  67             this.helper.MethodBegin(methRoot, null, true);
  68             StartNestedIterator(qil.Root);
  69             Visit(qil.Root);
  70             Debug.Assert(this.iterCurr.Storage.Location == ItemLocation.None, "Root expression should have been pushed to the writer.");
  71             EndNestedIterator(qil.Root);
  72             this.helper.MethodEnd();
  73         }
  74
  75         /// <summary>
  76         /// Create IteratorDescriptor for each global value.  This pre-visit is necessary because a global early
  77         /// in the list may reference a global later in the list and therefore expect its IteratorDescriptor to already
  78         /// be initialized.
  79         /// </summary>
  80         private void PrepareGlobalValues(QilList globalIterators) {
  81             MethodInfo methGlobal;
  82             IteratorDescriptor iterInfo;
  83
  84             foreach (QilIterator iter in globalIterators) {
  85                 Debug.Assert(iter.NodeType == QilNodeType.Let || iter.NodeType == QilNodeType.Parameter);
  86
  87                 // Get metadata for method which computes this global's value
  88                 methGlobal = XmlILAnnotation.Write(iter).FunctionBinding;
  89                 Debug.Assert(methGlobal != null, "Metadata for global value should have already been computed");
  90
  91                 // Create an IteratorDescriptor for this global value
  92                 iterInfo = new IteratorDescriptor(this.helper);
  93
  94                 // Iterator items will be stored in a global location
  95                 iterInfo.Storage = StorageDescriptor.Global(methGlobal, GetItemStorageType(iter), !iter.XmlType.IsSingleton);
  96
  97                 // Associate IteratorDescriptor with parameter
  98                 XmlILAnnotation.Write(iter).CachedIteratorDescriptor = iterInfo;
  99             }
 100         }
 101
 102         /// <summary>
 103         /// Visit each global variable or parameter.  Create a IteratorDescriptor for each global value.  Generate code for
 104         /// default values.
 105         /// </summary>
 106         private void VisitGlobalValues(QilList globalIterators) {
 107             MethodInfo methGlobal;
 108             Label lblGetGlobal, lblComputeGlobal;
 109             bool isCached;
 110             int idxValue;
 111
 112             foreach (QilIterator iter in globalIterators) {
 113                 QilParameter param = iter as QilParameter;
 114
 115                 // Get MethodInfo for method that computes the value of this global
 116                 methGlobal = XmlILAnnotation.Write(iter).CachedIteratorDescriptor.Storage.GlobalLocation;
 117                 isCached = !iter.XmlType.IsSingleton;
 118
 119                 // Notify the StaticDataManager of the new global value
 120                 idxValue = this.helper.StaticData.DeclareGlobalValue(iter.DebugName);
 121
 122                 // Generate code for this method
 123                 this.helper.MethodBegin(methGlobal, iter.SourceLine, false);
 124
 125                 lblGetGlobal = this.helper.DefineLabel();
 126                 lblComputeGlobal = this.helper.DefineLabel();
 127
 128                 // if (runtime.IsGlobalComputed(idx)) goto LabelGetGlobal;
 129                 this.helper.LoadQueryRuntime();
 130                 this.helper.LoadInteger(idxValue);
 131                 this.helper.Call(XmlILMethods.GlobalComputed);
 132                 this.helper.Emit(OpCodes.Brtrue, lblGetGlobal);
 133
 134                 // Compute value of global value
 135                 StartNestedIterator(iter);
 136
 137                 if (param != null) {
 138                     Debug.Assert(iter.XmlType == TypeFactory.ItemS, "IlGen currently only supports parameters of type item*.");
 139
 140                     // param = runtime.ExternalContext.GetParameter(localName, namespaceUri);
 141                     // if (param == null) goto LabelComputeGlobal;
 142                     LocalBuilder locParam = this.helper.DeclareLocal("$$$param", typeof(object));
 143                     this.helper.CallGetParameter(param.Name.LocalName, param.Name.NamespaceUri);
 144                     this.helper.Emit(OpCodes.Stloc, locParam);
 145                     this.helper.Emit(OpCodes.Ldloc, locParam);
 146                     this.helper.Emit(OpCodes.Brfalse, lblComputeGlobal);
 147
 148                     // runtime.SetGlobalValue(idxValue, runtime.ChangeTypeXsltResult(idxType, value));
 149                     // Ensure that the storage type of the parameter corresponds to static type
 150                     this.helper.LoadQueryRuntime();
 151                     this.helper.LoadInteger(idxValue);
 152
 153                     this.helper.LoadQueryRuntime();
 154                     this.helper.LoadInteger(this.helper.StaticData.DeclareXmlType(XmlQueryTypeFactory.ItemS));
 155                     this.helper.Emit(OpCodes.Ldloc, locParam);
 156                     this.helper.Call(XmlILMethods.ChangeTypeXsltResult);
 157
 158                     this.helper.CallSetGlobalValue(typeof(object));
 159
 160                     // goto LabelGetGlobal;
 161                     this.helper.EmitUnconditionalBranch(OpCodes.Br, lblGetGlobal);
 162                 }
 163
 164                 // LabelComputeGlobal:
 165                 this.helper.MarkLabel(lblComputeGlobal);
 166
 167                 if (iter.Binding != null) {
 168                     // runtime.SetGlobalValue(idxValue, (object) value);
 169                     this.helper.LoadQueryRuntime();
 170                     this.helper.LoadInteger(idxValue);
 171
 172                     // Compute value of global value
 173                     NestedVisitEnsureStack(iter.Binding, GetItemStorageType(iter), isCached);
 174
 175                     this.helper.CallSetGlobalValue(GetStorageType(iter));
 176                 }
 177                 else {
 178                     // Throw exception, as there is no default value for this parameter
 179                     // XmlQueryRuntime.ThrowException("...");
 180                     Debug.Assert(iter.NodeType == QilNodeType.Parameter, "Only parameters may not have a default value");
 181                     this.helper.LoadQueryRuntime();
 182                     this.helper.Emit(OpCodes.Ldstr, Res.GetString(Res.XmlIl_UnknownParam, new string[] {param.Name.LocalName, param.Name.NamespaceUri}));
 183                     this.helper.Call(XmlILMethods.ThrowException);
 184                 }
 185
 186                 EndNestedIterator(iter);
 187
 188                 // LabelGetGlobal:
 189                 // return (T) runtime.GetGlobalValue(idxValue);
 190                 this.helper.MarkLabel(lblGetGlobal);
 191                 this.helper.CallGetGlobalValue(idxValue, GetStorageType(iter));
 192
 193                 this.helper.MethodEnd();
 194             }
 195         }
 196
 197         /// <summary>
 198         /// Generate code for the specified function.
 199         /// </summary>
 200         private void Function(QilFunction ndFunc) {
 201             MethodInfo methFunc;
 202             int paramId;
 203             IteratorDescriptor iterInfo;
 204             bool useWriter;
 205
 206             // Annotate each function parameter with a IteratorDescriptor
 207             foreach (QilIterator iter in ndFunc.Arguments) {
 208                 Debug.Assert(iter.NodeType == QilNodeType.Parameter);
 209
 210                 // Create an IteratorDescriptor for this parameter
 211                 iterInfo = new IteratorDescriptor(this.helper);
 212
 213                 // Add one to parameter index, as 0th parameter is always "this"
 214                 paramId = XmlILAnnotation.Write(iter).ArgumentPosition + 1;
 215
 216                 // The ParameterInfo for each argument should be set as its location
 217                 iterInfo.Storage = StorageDescriptor.Parameter(paramId, GetItemStorageType(iter), !iter.XmlType.IsSingleton);
 218
 219                 // Associate IteratorDescriptor with Let iterator
 220                 XmlILAnnotation.Write(iter).CachedIteratorDescriptor = iterInfo;
 221             }
 222
 223             methFunc = XmlILAnnotation.Write(ndFunc).FunctionBinding;
 224             useWriter = (XmlILConstructInfo.Read(ndFunc).ConstructMethod == XmlILConstructMethod.Writer);
 225
 226             // Generate query code from QilExpression tree
 227             this.helper.MethodBegin(methFunc, ndFunc.SourceLine, useWriter);
 228
 229             foreach (QilIterator iter in ndFunc.Arguments) {
 230                 // DebugInfo: Sequence point just before generating code for the bound expression
 231                 if (this.qil.IsDebug && iter.SourceLine != null)
 232                     this.helper.DebugSequencePoint(iter.SourceLine);
 233
 234                 // Calculate default value of this parameter
 235                 if (iter.Binding != null) {
 236                     Debug.Assert(iter.XmlType == TypeFactory.ItemS, "IlGen currently only supports default values in parameters of type item*.");
 237                     paramId = (iter.Annotation as XmlILAnnotation).ArgumentPosition + 1;
 238
 239                     // runtime.MatchesXmlType(param, XmlTypeCode.QName);
 240                     Label lblLocalComputed = this.helper.DefineLabel();
 241                     this.helper.LoadQueryRuntime();
 242                     this.helper.LoadParameter(paramId);
 243                     this.helper.LoadInteger((int)XmlTypeCode.QName);
 244                     this.helper.Call(XmlILMethods.SeqMatchesCode);
 245
 246                     this.helper.Emit(OpCodes.Brfalse, lblLocalComputed);
 247
 248                     // Compute default value of this parameter
 249                     StartNestedIterator(iter);
 250                     NestedVisitEnsureStack(iter.Binding, GetItemStorageType(iter), /*isCached:*/!iter.XmlType.IsSingleton);
 251                     EndNestedIterator(iter);
 252
 253                     this.helper.SetParameter(paramId);
 254                     this.helper.MarkLabel(lblLocalComputed);
 255                 }
 256             }
 257
 258             StartNestedIterator(ndFunc);
 259
 260             // If function did not push results to writer, then function will return value(s) (rather than void)
 261             if (useWriter)
 262                 NestedVisit(ndFunc.Definition);
 263             else
 264                 NestedVisitEnsureStack(ndFunc.Definition, GetItemStorageType(ndFunc), !ndFunc.XmlType.IsSingleton);
 265
 266             EndNestedIterator(ndFunc);
 267
 268             this.helper.MethodEnd();
 269         }
 270
 271         //-----------------------------------------------
 272         // QilVisitor
 273         //-----------------------------------------------
 274
 275         /// <summary>
 276         /// Generate a query plan for the QilExpression subgraph.
 277         /// </summary>
 278         protected override QilNode Visit(QilNode nd) {
 279             if (nd == null)
 280                 return null;
 281
 282             // DebugInfo: Sequence point just before generating code for this expression
 283             if (this.qil.IsDebug && nd.SourceLine != null && !(nd is QilIterator))
 284                 this.helper.DebugSequencePoint(nd.SourceLine);
 285
 286             // Expressions are constructed using one of several possible methods
 287             switch (XmlILConstructInfo.Read(nd).ConstructMethod) {
 288                 case XmlILConstructMethod.WriterThenIterator:
 289                     // Push results of expression to cached writer; then iterate over cached results
 290                     NestedConstruction(nd);
 291                     break;
 292
 293                 case XmlILConstructMethod.IteratorThenWriter:
 294                     // Iterate over items in the sequence; send items to writer
 295                     CopySequence(nd);
 296                     break;
 297
 298                 case XmlILConstructMethod.Iterator:
 299                     Debug.Assert(nd.XmlType.IsSingleton || CachesResult(nd) || this.iterCurr.HasLabelNext,
 300                                  "When generating code for a non-singleton expression, LabelNext must be defined.");
 301                     goto default;
 302
 303                 default:
 304                     // Allow base internal class to dispatch to correct Visit method
 305                     base.Visit(nd);
 306                     break;
 307             }
 308
 309             return nd;
 310         }
 311
 312         /// <summary>
 313         /// VisitChildren should never be called.
 314         /// </summary>
 315         protected override QilNode VisitChildren(QilNode parent) {
 316             Debug.Fail("Visit" + parent.NodeType + " should never be called");
 317             return parent;
 318         }
 319
 320         /// <summary>
 321         /// Generate code to cache a sequence of items that are pushed to output.
 322         /// </summary>
 323         private void NestedConstruction(QilNode nd) {
 324             // Start nested construction of a sequence of items
 325             this.helper.CallStartSequenceConstruction();
 326
 327             // Allow base internal class to dispatch to correct Visit method
 328             base.Visit(nd);
 329
 330             // Get the result sequence
 331             this.helper.CallEndSequenceConstruction();
 332             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(XPathItem), true);
 333         }
 334
 335         /// <summary>
 336         /// Iterate over items produced by the "nd" expression and copy each item to output.
 337         /// </summary>
 338         private void CopySequence(QilNode nd) {
 339             XmlQueryType typ = nd.XmlType;
 340             bool hasOnEnd;
 341             Label lblOnEnd;
 342
 343             StartWriterLoop(nd, out hasOnEnd, out lblOnEnd);
 344
 345             if (typ.IsSingleton) {
 346                 // Always write atomic values via XmlQueryOutput
 347                 this.helper.LoadQueryOutput();
 348
 349                 // Allow base internal class to dispatch to correct Visit method
 350                 base.Visit(nd);
 351                 this.iterCurr.EnsureItemStorageType(nd.XmlType, typeof(XPathItem));
 352             }
 353             else {
 354                 // Allow base internal class to dispatch to correct Visit method
 355                 base.Visit(nd);
 356                 this.iterCurr.EnsureItemStorageType(nd.XmlType, typeof(XPathItem));
 357
 358                 // Save any stack values in a temporary local
 359                 this.iterCurr.EnsureNoStackNoCache("$$$copyTemp");
 360
 361                 this.helper.LoadQueryOutput();
 362             }
 363
 364             // Write value to output
 365             this.iterCurr.EnsureStackNoCache();
 366             this.helper.Call(XmlILMethods.WriteItem);
 367
 368             EndWriterLoop(nd, hasOnEnd, lblOnEnd);
 369         }
 370
 371         /// <summary>
 372         /// Generate code for QilNodeType.DataSource.
 373         /// </summary>
 374         /// <remarks>
 375         /// Generates code to retrieve a document using the XmlResolver.
 376         /// </remarks>
 377         protected override QilNode VisitDataSource(QilDataSource ndSrc) {
 378             LocalBuilder locNav;
 379
 380             // XPathNavigator navDoc = runtime.ExternalContext.GetEntity(uri)
 381             this.helper.LoadQueryContext();
 382             NestedVisitEnsureStack(ndSrc.Name);
 383             NestedVisitEnsureStack(ndSrc.BaseUri);
 384             this.helper.Call(XmlILMethods.GetDataSource);
 385
 386             locNav = this.helper.DeclareLocal("$$$navDoc", typeof(XPathNavigator));
 387             this.helper.Emit(OpCodes.Stloc, locNav);
 388
 389             // if (navDoc == null) goto LabelNextCtxt;
 390             this.helper.Emit(OpCodes.Ldloc, locNav);
 391             this.helper.Emit(OpCodes.Brfalse, this.iterCurr.GetLabelNext());
 392
 393             this.iterCurr.Storage = StorageDescriptor.Local(locNav, typeof(XPathNavigator), false);
 394
 395             return ndSrc;
 396         }
 397
 398         /// <summary>
 399         /// Generate code for QilNodeType.Nop.
 400         /// </summary>
 401         protected override QilNode VisitNop(QilUnary ndNop) {
 402             return Visit(ndNop.Child);
 403         }
 404
 405         /// <summary>
 406         /// Generate code for QilNodeType.OptimizeBarrier.
 407         /// </summary>
 408         protected override QilNode VisitOptimizeBarrier(QilUnary ndBarrier) {
 409             return Visit(ndBarrier.Child);
 410         }
 411
 412         /// <summary>
 413         /// Generate code for QilNodeType.Error.
 414         /// </summary>
 415         protected override QilNode VisitError(QilUnary ndErr) {
 416             // XmlQueryRuntime.ThrowException(strErr);
 417             this.helper.LoadQueryRuntime();
 418             NestedVisitEnsureStack(ndErr.Child);
 419             this.helper.Call(XmlILMethods.ThrowException);
 420
 421             if (XmlILConstructInfo.Read(ndErr).ConstructMethod == XmlILConstructMethod.Writer) {
 422                 this.iterCurr.Storage = StorageDescriptor.None();
 423             }
 424             else {
 425                 // Push dummy value so that Location is not None and IL rules are met
 426                 this.helper.Emit(OpCodes.Ldnull);
 427                 this.iterCurr.Storage = StorageDescriptor.Stack(typeof(XPathItem), false);
 428             }
 429
 430             return ndErr;
 431         }
 432
 433         /// <summary>
 434         /// Generate code for QilNodeType.Warning.
 435         /// </summary>
 436         protected override QilNode VisitWarning(QilUnary ndWarning) {
 437             // runtime.SendMessage(strWarning);
 438             this.helper.LoadQueryRuntime();
 439             NestedVisitEnsureStack(ndWarning.Child);
 440             this.helper.Call(XmlILMethods.SendMessage);
 441
 442             if (XmlILConstructInfo.Read(ndWarning).ConstructMethod == XmlILConstructMethod.Writer)
 443                 this.iterCurr.Storage = StorageDescriptor.None();
 444             else
 445                 VisitEmpty(ndWarning);
 446
 447             return ndWarning;
 448         }
 449
 450         /// <summary>
 451         /// Generate code for QilNodeType.True.
 452         /// </summary>
 453         /// <remarks>
 454         /// BranchingContext.OnFalse context: [nothing]
 455         /// BranchingContext.OnTrue context:  goto LabelParent;
 456         /// BranchingContext.None context:  push true();
 457         /// </remarks>
 458         protected override QilNode VisitTrue(QilNode ndTrue) {
 459             if (this.iterCurr.CurrentBranchingContext != BranchingContext.None) {
 460                 // Make sure there's an IL code path to both the true and false branches in order to avoid dead
 461                 // code which can cause IL verification errors.
 462                 this.helper.EmitUnconditionalBranch(this.iterCurr.CurrentBranchingContext == BranchingContext.OnTrue ?
 463                         OpCodes.Brtrue : OpCodes.Brfalse, this.iterCurr.LabelBranch);
 464
 465                 this.iterCurr.Storage = StorageDescriptor.None();
 466             }
 467             else {
 468                 // Push boolean result onto the stack
 469                 this.helper.LoadBoolean(true);
 470                 this.iterCurr.Storage = StorageDescriptor.Stack(typeof(bool), false);
 471             }
 472
 473             return ndTrue;
 474         }
 475
 476         /// <summary>
 477         /// Generate code for QilNodeType.False.
 478         /// </summary>
 479         /// <remarks>
 480         /// BranchingContext.OnFalse context: goto LabelParent;
 481         /// BranchingContext.OnTrue context:  [nothing]
 482         /// BranchingContext.None context:  push false();
 483         /// </remarks>
 484         protected override QilNode VisitFalse(QilNode ndFalse) {
 485             if (this.iterCurr.CurrentBranchingContext != BranchingContext.None) {
 486                 // Make sure there's an IL code path to both the true and false branches in order to avoid dead
 487                 // code which can cause IL verification errors.
 488                 this.helper.EmitUnconditionalBranch(this.iterCurr.CurrentBranchingContext == BranchingContext.OnFalse ?
 489                         OpCodes.Brtrue : OpCodes.Brfalse, this.iterCurr.LabelBranch);
 490
 491                 this.iterCurr.Storage = StorageDescriptor.None();
 492             }
 493             else {
 494                 // Push boolean result onto the stack
 495                 this.helper.LoadBoolean(false);
 496                 this.iterCurr.Storage = StorageDescriptor.Stack(typeof(bool), false);
 497             }
 498
 499             return ndFalse;
 500         }
 501
 502         /// <summary>
 503         /// Generate code for QilNodeType.LiteralString.
 504         /// </summary>
 505         protected override QilNode VisitLiteralString(QilLiteral ndStr) {
 506             this.helper.Emit(OpCodes.Ldstr, (string) ndStr);
 507             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(string), false);
 508             return ndStr;
 509         }
 510
 511         /// <summary>
 512         /// Generate code for QilNodeType.LiteralInt32.
 513         /// </summary>
 514         protected override QilNode VisitLiteralInt32(QilLiteral ndInt) {
 515             this.helper.LoadInteger((int) ndInt);
 516             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(int), false);
 517             return ndInt;
 518         }
 519
 520         /// <summary>
 521         /// Generate code for QilNodeType.LiteralInt64.
 522         /// </summary>
 523         protected override QilNode VisitLiteralInt64(QilLiteral ndLong) {
 524             this.helper.Emit(OpCodes.Ldc_I8, (long) ndLong);
 525             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(long), false);
 526             return ndLong;
 527         }
 528
 529         /// <summary>
 530         /// Generate code for QilNodeType.LiteralDouble.
 531         /// </summary>
 532         protected override QilNode VisitLiteralDouble(QilLiteral ndDbl) {
 533             this.helper.Emit(OpCodes.Ldc_R8, (double) ndDbl);
 534             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(double), false);
 535             return ndDbl;
 536         }
 537
 538         /// <summary>
 539         /// Generate code for QilNodeType.LiteralDecimal.
 540         /// </summary>
 541         protected override QilNode VisitLiteralDecimal(QilLiteral ndDec) {
 542             this.helper.ConstructLiteralDecimal((decimal) ndDec);
 543             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(decimal), false);
 544             return ndDec;
 545         }
 546
 547         /// <summary>
 548         /// Generate code for QilNodeType.LiteralQName.
 549         /// </summary>
 550         protected override QilNode VisitLiteralQName(QilName ndQName) {
 551             this.helper.ConstructLiteralQName(ndQName.LocalName, ndQName.NamespaceUri);
 552             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(XmlQualifiedName), false);
 553             return ndQName;
 554         }
 555
 556         /// <summary>
 557         /// Generate code for QilNodeType.And.
 558         /// </summary>
 559         /// <remarks>
 560         /// BranchingContext.OnFalse context: (expr1) and (expr2)
 561         /// ==> if (!expr1) goto LabelParent;
 562         ///     if (!expr2) goto LabelParent;
 563         ///
 564         /// BranchingContext.OnTrue context: (expr1) and (expr2)
 565         /// ==> if (!expr1) goto LabelTemp;
 566         ///     if (expr1) goto LabelParent;
 567         ///     LabelTemp:
 568         ///
 569         /// BranchingContext.None context: (expr1) and (expr2)
 570         /// ==> if (!expr1) goto LabelTemp;
 571         ///     if (!expr1) goto LabelTemp;
 572         ///     push true();
 573         ///     goto LabelSkip;
 574         ///     LabelTemp:
 575         ///     push false();
 576         ///     LabelSkip:
 577         ///
 578         /// </remarks>
 579         protected override QilNode VisitAnd(QilBinary ndAnd) {
 580             IteratorDescriptor iterParent = this.iterCurr;
 581             Label lblOnFalse;
 582
 583             // Visit left branch
 584             StartNestedIterator(ndAnd.Left);
 585             lblOnFalse = StartConjunctiveTests(iterParent.CurrentBranchingContext, iterParent.LabelBranch);
 586             Visit(ndAnd.Left);
 587             EndNestedIterator(ndAnd.Left);
 588
 589             // Visit right branch
 590             StartNestedIterator(ndAnd.Right);
 591             StartLastConjunctiveTest(iterParent.CurrentBranchingContext, iterParent.LabelBranch, lblOnFalse);
 592             Visit(ndAnd.Right);
 593             EndNestedIterator(ndAnd.Right);
 594
 595             // End And expression
 596             EndConjunctiveTests(iterParent.CurrentBranchingContext, iterParent.LabelBranch, lblOnFalse);
 597
 598             return ndAnd;
 599         }
 600
 601         /// <summary>
 602         /// Fixup branching context for all but the last test in a conjunctive (Logical And) expression.
 603         /// Return a temporary label which will be passed to StartLastAndBranch() and EndAndBranch().
 604         /// </summary>
 605         private Label StartConjunctiveTests(BranchingContext brctxt, Label lblBranch) {
 606             Label lblOnFalse;
 607
 608             switch (brctxt) {
 609                 case BranchingContext.OnFalse:
 610                     // If condition evaluates to false, branch to false label
 611                     this.iterCurr.SetBranching(BranchingContext.OnFalse, lblBranch);
 612                     return lblBranch;
 613
 614                 default:
 615                     // If condition evaluates to false:
 616                     //   1. Jump to new false label that will be fixed just beyond the second condition
 617                     //   2. Or, jump to code that pushes "false"
 618                     lblOnFalse = this.helper.DefineLabel();
 619                     this.iterCurr.SetBranching(BranchingContext.OnFalse, lblOnFalse);
 620                     return lblOnFalse;
 621             }
 622         }
 623
 624         /// <summary>
 625         /// Fixup branching context for the last test in a conjunctive (Logical And) expression.
 626         /// </summary>
 627         private void StartLastConjunctiveTest(BranchingContext brctxt, Label lblBranch, Label lblOnFalse) {
 628             switch (brctxt) {
 629                 case BranchingContext.OnTrue:
 630                     // If last condition evaluates to true, branch to true label
 631                     this.iterCurr.SetBranching(BranchingContext.OnTrue, lblBranch);
 632                     break;
 633
 634                 default:
 635                     // If last condition evalutes to false, branch to false label
 636                     // Else fall through to true code path
 637                     this.iterCurr.SetBranching(BranchingContext.OnFalse, lblOnFalse);
 638                     break;
 639             }
 640         }
 641
 642         /// <summary>
 643         /// Anchor any remaining labels.
 644         /// </summary>
 645         private void EndConjunctiveTests(BranchingContext brctxt, Label lblBranch, Label lblOnFalse) {
 646             switch (brctxt) {
 647                 case BranchingContext.OnTrue:
 648                     // Anchor false label
 649                     this.helper.MarkLabel(lblOnFalse);
 650                     goto case BranchingContext.OnFalse;
 651
 652                 case BranchingContext.OnFalse:
 653                     this.iterCurr.Storage = StorageDescriptor.None();
 654                     break;
 655
 656                 case BranchingContext.None:
 657                     // Convert branch targets into push of true/false
 658                     this.helper.ConvBranchToBool(lblOnFalse, false);
 659                     this.iterCurr.Storage = StorageDescriptor.Stack(typeof(bool), false);
 660                     break;
 661             }
 662         }
 663
 664         /// <summary>
 665         /// Generate code for QilNodeType.Or.
 666         /// </summary>
 667         /// <remarks>
 668         /// BranchingContext.OnFalse context: (expr1) or (expr2)
 669         /// ==> if (expr1) goto LabelTemp;
 670         ///     if (!expr2) goto LabelParent;
 671         ///     LabelTemp:
 672         ///
 673         /// BranchingContext.OnTrue context: (expr1) or (expr2)
 674         /// ==> if (expr1) goto LabelParent;
 675         ///     if (expr1) goto LabelParent;
 676         ///
 677         /// BranchingContext.None context: (expr1) or (expr2)
 678         /// ==> if (expr1) goto LabelTemp;
 679         ///     if (expr1) goto LabelTemp;
 680         ///     push false();
 681         ///     goto LabelSkip;
 682         ///     LabelTemp:
 683         ///     push true();
 684         ///     LabelSkip:
 685         ///
 686         /// </remarks>
 687         protected override QilNode VisitOr(QilBinary ndOr) {
 688             Label lblTemp = new Label();
 689
 690             // Visit left branch
 691             switch (this.iterCurr.CurrentBranchingContext) {
 692                 case BranchingContext.OnFalse:
 693                     // If left condition evaluates to true, jump to new label that will be fixed
 694                     // just beyond the second condition
 695                     lblTemp = this.helper.DefineLabel();
 696                     NestedVisitWithBranch(ndOr.Left, BranchingContext.OnTrue, lblTemp);
 697                     break;
 698
 699                 case BranchingContext.OnTrue:
 700                     // If left condition evaluates to true, branch to true label
 701                     NestedVisitWithBranch(ndOr.Left, BranchingContext.OnTrue, this.iterCurr.LabelBranch);
 702                     break;
 703
 704                 default:
 705                     // If left condition evalutes to true, jump to code that pushes "true"
 706                     Debug.Assert(this.iterCurr.CurrentBranchingContext == BranchingContext.None);
 707                     lblTemp = this.helper.DefineLabel();
 708                     NestedVisitWithBranch(ndOr.Left, BranchingContext.OnTrue, lblTemp);
 709                     break;
 710             }
 711
 712             // Visit right branch
 713             switch (this.iterCurr.CurrentBranchingContext) {
 714                 case BranchingContext.OnFalse:
 715                     // If right condition evaluates to false, branch to false label
 716                     NestedVisitWithBranch(ndOr.Right, BranchingContext.OnFalse, this.iterCurr.LabelBranch);
 717                     break;
 718
 719                 case BranchingContext.OnTrue:
 720                     // If right condition evaluates to true, branch to true label
 721                     NestedVisitWithBranch(ndOr.Right, BranchingContext.OnTrue, this.iterCurr.LabelBranch);
 722                     break;
 723
 724                 default:
 725                     // If right condition evalutes to true, jump to code that pushes "true".
 726                     // Otherwise, if both conditions evaluate to false, fall through code path
 727                     // will push "false".
 728                     NestedVisitWithBranch(ndOr.Right, BranchingContext.OnTrue, lblTemp);
 729                     break;
 730             }
 731
 732             switch (this.iterCurr.CurrentBranchingContext) {
 733                 case BranchingContext.OnFalse:
 734                     // Anchor true label
 735                     this.helper.MarkLabel(lblTemp);
 736                     goto case BranchingContext.OnTrue;
 737
 738                 case BranchingContext.OnTrue:
 739                     this.iterCurr.Storage = StorageDescriptor.None();
 740                     break;
 741
 742                 case BranchingContext.None:
 743                     // Convert branch targets into push of true/false
 744                     this.helper.ConvBranchToBool(lblTemp, true);
 745                     this.iterCurr.Storage = StorageDescriptor.Stack(typeof(bool), false);
 746                     break;
 747             }
 748
 749             return ndOr;
 750         }
 751
 752         /// <summary>
 753         /// Generate code for QilNodeType.Not.
 754         /// </summary>
 755         /// <remarks>
 756         /// BranchingContext.OnFalse context: not(expr1)
 757         /// ==> if (expr1) goto LabelParent;
 758         ///
 759         /// BranchingContext.OnTrue context: not(expr1)
 760         /// ==> if (!expr1) goto LabelParent;
 761         ///
 762         /// BranchingContext.None context: not(expr1)
 763         /// ==> if (expr1) goto LabelTemp;
 764         ///     push false();
 765         ///     goto LabelSkip;
 766         ///     LabelTemp:
 767         ///     push true();
 768         ///     LabelSkip:
 769         ///
 770         /// </remarks>
 771         protected override QilNode VisitNot(QilUnary ndNot) {
 772             Label lblTemp = new Label();
 773
 774             // Visit operand
 775             // Reverse branch types
 776             switch (this.iterCurr.CurrentBranchingContext) {
 777                 case BranchingContext.OnFalse:
 778                     NestedVisitWithBranch(ndNot.Child, BranchingContext.OnTrue, this.iterCurr.LabelBranch);
 779                     break;
 780
 781                 case BranchingContext.OnTrue:
 782                     NestedVisitWithBranch(ndNot.Child, BranchingContext.OnFalse, this.iterCurr.LabelBranch);
 783                     break;
 784
 785                 default:
 786                     // Replace boolean argument on top of stack with its inverse
 787                     Debug.Assert(this.iterCurr.CurrentBranchingContext == BranchingContext.None);
 788                     lblTemp = this.helper.DefineLabel();
 789                     NestedVisitWithBranch(ndNot.Child, BranchingContext.OnTrue, lblTemp);
 790                     break;
 791             }
 792
 793             if (this.iterCurr.CurrentBranchingContext == BranchingContext.None) {
 794                 // If condition evaluates to true, then jump to code that pushes false
 795                 this.helper.ConvBranchToBool(lblTemp, false);
 796                 this.iterCurr.Storage = StorageDescriptor.Stack(typeof(bool), false);
 797             }
 798             else {
 799                 this.iterCurr.Storage = StorageDescriptor.None();
 800             }
 801
 802             return ndNot;
 803         }
 804
 805         /// <summary>
 806         /// Generate code for QilNodeType.Conditional.
 807         /// </summary>
 808         protected override QilNode VisitConditional(QilTernary ndCond) {
 809             XmlILConstructInfo info = XmlILConstructInfo.Read(ndCond);
 810
 811             if (info.ConstructMethod == XmlILConstructMethod.Writer) {
 812                 Label lblFalse, lblDone;
 813
 814                 // Evaluate if test
 815                 lblFalse = this.helper.DefineLabel();
 816                 NestedVisitWithBranch(ndCond.Left, BranchingContext.OnFalse, lblFalse);
 817
 818                 // Generate true branch code
 819                 NestedVisit(ndCond.Center);
 820
 821                 // Generate false branch code.  If false branch is the empty list,
 822                 if (ndCond.Right.NodeType == QilNodeType.Sequence && ndCond.Right.Count == 0) {
 823                     // Then generate simplified code that doesn't contain a false branch
 824                     this.helper.MarkLabel(lblFalse);
 825                     NestedVisit(ndCond.Right);
 826                 }
 827                 else {
 828                     // Jump past false branch
 829                     lblDone = this.helper.DefineLabel();
 830                     this.helper.EmitUnconditionalBranch(OpCodes.Br, lblDone);
 831
 832                     // Generate false branch code
 833                     this.helper.MarkLabel(lblFalse);
 834                     NestedVisit(ndCond.Right);
 835
 836                     this.helper.MarkLabel(lblDone);
 837                 }
 838
 839                 this.iterCurr.Storage = StorageDescriptor.None();
 840             }
 841             else {
 842                 IteratorDescriptor iterInfoTrue;
 843                 LocalBuilder locBool = null, locCond = null;
 844                 Label lblFalse, lblDone, lblNext;
 845                 Type itemStorageType = GetItemStorageType(ndCond);
 846                 Debug.Assert(info.ConstructMethod == XmlILConstructMethod.Iterator);
 847
 848                 // Evaluate conditional test -- save boolean result in boolResult
 849                 Debug.Assert(ndCond.Left.XmlType.TypeCode == XmlTypeCode.Boolean);
 850                 lblFalse = this.helper.DefineLabel();
 851
 852                 if (ndCond.XmlType.IsSingleton) {
 853                     // if (!bool-expr) goto LabelFalse;
 854                     NestedVisitWithBranch(ndCond.Left, BranchingContext.OnFalse, lblFalse);
 855                 }
 856                 else {
 857                     // CondType itemCond;
 858                     // int boolResult = bool-expr;
 859                     locCond = this.helper.DeclareLocal("$$$cond", itemStorageType);
 860                     locBool = this.helper.DeclareLocal("$$$boolResult", typeof(bool));
 861                     NestedVisitEnsureLocal(ndCond.Left, locBool);
 862
 863                     // if (!boolResult) goto LabelFalse;
 864                     this.helper.Emit(OpCodes.Ldloc, locBool);
 865                     this.helper.Emit(OpCodes.Brfalse, lblFalse);
 866                 }
 867
 868                 // Generate code for true branch
 869                 ConditionalBranch(ndCond.Center, itemStorageType, locCond);
 870                 iterInfoTrue = this.iterNested;
 871
 872                 // goto LabelDone;
 873                 lblDone = this.helper.DefineLabel();
 874                 this.helper.EmitUnconditionalBranch(OpCodes.Br, lblDone);
 875
 876                 // Generate code for false branch
 877                 // LabelFalse:
 878                 this.helper.MarkLabel(lblFalse);
 879                 ConditionalBranch(ndCond.Right, itemStorageType, locCond);
 880
 881                 // If conditional is not cardinality one, then need to iterate through all values
 882                 if (!ndCond.XmlType.IsSingleton) {
 883                     Debug.Assert(!ndCond.Center.XmlType.IsSingleton || !ndCond.Right.XmlType.IsSingleton);
 884
 885                     // IL's rules do not allow OpCodes.Br here
 886                     // goto LabelDone;
 887                     this.helper.EmitUnconditionalBranch(OpCodes.Brtrue, lblDone);
 888
 889                     // LabelNext:
 890                     lblNext = this.helper.DefineLabel();
 891                     this.helper.MarkLabel(lblNext);
 892
 893                     // if (boolResult) goto LabelNextTrue else goto LabelNextFalse;
 894                     this.helper.Emit(OpCodes.Ldloc, locBool);
 895                     this.helper.Emit(OpCodes.Brtrue, iterInfoTrue.GetLabelNext());
 896                     this.helper.EmitUnconditionalBranch(OpCodes.Br, this.iterNested.GetLabelNext());
 897
 898                     this.iterCurr.SetIterator(lblNext, StorageDescriptor.Local(locCond, itemStorageType, false));
 899                 }
 900
 901                 // LabelDone:
 902                 this.helper.MarkLabel(lblDone);
 903             }
 904
 905             return ndCond;
 906         }
 907
 908         /// <summary>
 909         /// Generate code for one of the branches of QilNodeType.Conditional.
 910         /// </summary>
 911         private void ConditionalBranch(QilNode ndBranch, Type itemStorageType, LocalBuilder locResult) {
 912             if (locResult == null) {
 913                 Debug.Assert(ndBranch.XmlType.IsSingleton, "Conditional must produce a singleton");
 914
 915                 // If in a branching context, then inherit branch target from parent context
 916                 if (this.iterCurr.IsBranching) {
 917                     Debug.Assert(itemStorageType == typeof(bool));
 918                     NestedVisitWithBranch(ndBranch, this.iterCurr.CurrentBranchingContext, this.iterCurr.LabelBranch);
 919                 }
 920                 else {
 921                     NestedVisitEnsureStack(ndBranch, itemStorageType, false);
 922                 }
 923             }
 924             else {
 925                 // Link nested iterator to parent conditional's iterator
 926                 NestedVisit(ndBranch, this.iterCurr.GetLabelNext());
 927                 this.iterCurr.EnsureItemStorageType(ndBranch.XmlType, itemStorageType);
 928                 this.iterCurr.EnsureLocalNoCache(locResult);
 929             }
 930         }
 931
 932         /// <summary>
 933         /// Generate code for QilNodeType.Choice.
 934         /// </summary>
 935         protected override QilNode VisitChoice(QilChoice ndChoice) {
 936             QilNode ndBranches;
 937             Label[] switchLabels;
 938             Label lblOtherwise, lblDone;
 939             int regBranches, idx;
 940             Debug.Assert(XmlILConstructInfo.Read(ndChoice).PushToWriterFirst);
 941
 942             // Evaluate the expression
 943             NestedVisit(ndChoice.Expression);
 944
 945             // Generate switching code
 946             ndBranches = ndChoice.Branches;
 947             regBranches = ndBranches.Count - 1;
 948             switchLabels = new Label[regBranches];
 949             for (idx = 0; idx < regBranches; idx++)
 950                 switchLabels[idx] = this.helper.DefineLabel();
 951
 952             lblOtherwise = this.helper.DefineLabel();
 953             lblDone = this.helper.DefineLabel();
 954
 955             // switch (value)
 956             //   case 0: goto Label[0];
 957             //   ...
 958             //   case N-1: goto Label[N-1];
 959             //   default: goto LabelOtherwise;
 960             this.helper.Emit(OpCodes.Switch, switchLabels);
 961             this.helper.EmitUnconditionalBranch(OpCodes.Br, lblOtherwise);
 962
 963             for (idx = 0; idx < regBranches; idx++) {
 964                 // Label[i]:
 965                 this.helper.MarkLabel(switchLabels[idx]);
 966
 967                 // Generate regular branch code
 968                 NestedVisit(ndBranches[idx]);
 969
 970                 // goto LabelDone
 971                 this.helper.EmitUnconditionalBranch(OpCodes.Br, lblDone);
 972             }
 973
 974             // LabelOtherwise:
 975             this.helper.MarkLabel(lblOtherwise);
 976
 977             // Generate otherwise branch code
 978             NestedVisit(ndBranches[idx]);
 979
 980             // LabelDone:
 981             this.helper.MarkLabel(lblDone);
 982
 983             this.iterCurr.Storage = StorageDescriptor.None();
 984
 985             return ndChoice;
 986         }
 987
 988         /// <summary>
 989         /// Generate code for QilNodeType.Length.
 990         /// </summary>
 991         /// <remarks>
 992         /// int length = 0;
 993         /// foreach (item in expr)
 994         ///   length++;
 995         /// </remarks>
 996         protected override QilNode VisitLength(QilUnary ndSetLen) {
 997             Label lblOnEnd = this.helper.DefineLabel();
 998             OptimizerPatterns patt = OptimizerPatterns.Read(ndSetLen);
 999
1000             if (CachesResult(ndSetLen.Child)) {
1001                 NestedVisitEnsureStack(ndSetLen.Child);
1002                 this.helper.CallCacheCount(this.iterNested.Storage.ItemStorageType);
1003             }
1004             else {
1005                 // length = 0;
1006                 this.helper.Emit(OpCodes.Ldc_I4_0);
1007
1008                 StartNestedIterator(ndSetLen.Child, lblOnEnd);
1009
1010                 // foreach (item in expr) {
1011                 Visit(ndSetLen.Child);
1012
1013                 // Pop values of SetLength expression from the stack if necessary
1014                 this.iterCurr.EnsureNoCache();
1015                 this.iterCurr.DiscardStack();
1016
1017                 // length++;
1018                 this.helper.Emit(OpCodes.Ldc_I4_1);
1019                 this.helper.Emit(OpCodes.Add);
1020
1021                 if (patt.MatchesPattern(OptimizerPatternName.MaxPosition)) {
1022                     // Short-circuit rest of loop if max position has been exceeded
1023                     this.helper.Emit(OpCodes.Dup);
1024                     this.helper.LoadInteger((int) patt.GetArgument(OptimizerPatternArgument.MaxPosition));
1025                     this.helper.Emit(OpCodes.Bgt, lblOnEnd);
1026                 }
1027
1028                 // }
1029                 this.iterCurr.LoopToEnd(lblOnEnd);
1030
1031                 EndNestedIterator(ndSetLen.Child);
1032             }
1033
1034             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(int), false);
1035
1036             return ndSetLen;
1037         }
1038
1039         /// <summary>
1040         /// Find physical query plan for QilNodeType.Sequence.
1041         /// </summary>
1042         protected override QilNode VisitSequence(QilList ndSeq) {
1043             if (XmlILConstructInfo.Read(ndSeq).ConstructMethod == XmlILConstructMethod.Writer) {
1044                 // Push each item in the list to output
1045                 foreach (QilNode nd in ndSeq)
1046                     NestedVisit(nd);
1047             }
1048             else {
1049                 // Empty sequence is special case
1050                 if (ndSeq.Count == 0)
1051                     VisitEmpty(ndSeq);
1052                 else
1053                     Sequence(ndSeq);
1054             }
1055
1056             return ndSeq;
1057         }
1058
1059         /// <summary>
1060         /// Generate code for the empty sequence.
1061         /// </summary>
1062         private void VisitEmpty(QilNode nd) {
1063             Debug.Assert(XmlILConstructInfo.Read(nd).PullFromIteratorFirst, "VisitEmpty should only be called if items are iterated");
1064
1065             // IL's rules prevent OpCodes.Br here
1066             // Empty sequence
1067             this.helper.EmitUnconditionalBranch(OpCodes.Brtrue, this.iterCurr.GetLabelNext());
1068
1069             // Push dummy value so that Location is not None and IL rules are met
1070             this.helper.Emit(OpCodes.Ldnull);
1071             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(XPathItem), false);
1072         }
1073
1074         /// <summary>
1075         /// Generate code for QilNodeType.Sequence, when sort-merging to retain document order is not necessary.
1076         /// </summary>
1077         private void Sequence(QilList ndSeq) {
1078             LocalBuilder locIdx, locList;
1079             Label lblStart, lblNext, lblOnEnd = new Label();
1080             Label[] arrSwitchLabels;
1081             int i;
1082             Type itemStorageType = GetItemStorageType(ndSeq);
1083             Debug.Assert(XmlILConstructInfo.Read(ndSeq).ConstructMethod == XmlILConstructMethod.Iterator, "This method should only be called if items in list are pulled from a code iterator.");
1084
1085             // Singleton list is a special case if in addition to the singleton there are warnings or errors which should be executed
1086             if (ndSeq.XmlType.IsSingleton) {
1087                 foreach (QilNode nd in ndSeq) {
1088                     // Generate nested iterator's code
1089                     if (nd.XmlType.IsSingleton) {
1090                         NestedVisitEnsureStack(nd);
1091                     }
1092                     else {
1093                         lblOnEnd = this.helper.DefineLabel();
1094                         NestedVisit(nd, lblOnEnd);
1095                         this.iterCurr.DiscardStack();
1096                         this.helper.MarkLabel(lblOnEnd);
1097                     }
1098                 }
1099                 this.iterCurr.Storage = StorageDescriptor.Stack(itemStorageType, false);
1100             }
1101             else {
1102                 // Type itemList;
1103                 // int idxList;
1104                 locList = this.helper.DeclareLocal("$$$itemList", itemStorageType);
1105                 locIdx = this.helper.DeclareLocal("$$$idxList", typeof(int));
1106
1107                 arrSwitchLabels = new Label[ndSeq.Count];
1108                 lblStart = this.helper.DefineLabel();
1109
1110                 for (i = 0; i < ndSeq.Count; i++) {
1111                     // LabelOnEnd[i - 1]:
1112                     // When previous nested iterator is exhausted, it should jump to this (the next) iterator
1113                     if (i != 0)
1114                         this.helper.MarkLabel(lblOnEnd);
1115
1116                     // Create new LabelOnEnd for all but the last iterator, which jumps back to parent iterator when exhausted
1117                     if (i == ndSeq.Count - 1)
1118                         lblOnEnd = this.iterCurr.GetLabelNext();
1119                     else
1120                         lblOnEnd = this.helper.DefineLabel();
1121
1122                     // idxList = [i];
1123                     this.helper.LoadInteger(i);
1124                     this.helper.Emit(OpCodes.Stloc, locIdx);
1125
1126                     // Generate nested iterator's code
1127                     NestedVisit(ndSeq[i], lblOnEnd);
1128
1129                     // Result of list should be saved to a common type and location
1130                     this.iterCurr.EnsureItemStorageType(ndSeq[i].XmlType, itemStorageType);
1131                     this.iterCurr.EnsureLocalNoCache(locList);
1132
1133                     // Switch statement will jump to nested iterator's LabelNext
1134                     arrSwitchLabels[i] = this.iterNested.GetLabelNext();
1135
1136                     // IL's rules prevent OpCodes.Br here
1137                     // goto LabelStart;
1138                     this.helper.EmitUnconditionalBranch(OpCodes.Brtrue, lblStart);
1139                 }
1140
1141                 // LabelNext:
1142                 lblNext = this.helper.DefineLabel();
1143                 this.helper.MarkLabel(lblNext);
1144
1145                 // switch (idxList)
1146                 //   case 0: goto LabelNext1;
1147                 //   ...
1148                 //   case N-1: goto LabelNext[N];
1149                 this.helper.Emit(OpCodes.Ldloc, locIdx);
1150                 this.helper.Emit(OpCodes.Switch, arrSwitchLabels);
1151
1152                 // LabelStart:
1153                 this.helper.MarkLabel(lblStart);
1154
1155                 this.iterCurr.SetIterator(lblNext, StorageDescriptor.Local(locList, itemStorageType, false));
1156             }
1157         }
1158
1159         /// <summary>
1160         /// Generate code for QilNodeType.Union.
1161         /// </summary>
1162         protected override QilNode VisitUnion(QilBinary ndUnion) {
1163             return CreateSetIterator(ndUnion, "$$$iterUnion", typeof(UnionIterator), XmlILMethods.UnionCreate, XmlILMethods.UnionNext);
1164         }
1165
1166         /// <summary>
1167         /// Generate code for QilNodeType.Intersection.
1168         /// </summary>
1169         protected override QilNode VisitIntersection(QilBinary ndInter) {
1170             return CreateSetIterator(ndInter, "$$$iterInter", typeof(IntersectIterator), XmlILMethods.InterCreate, XmlILMethods.InterNext);
1171         }
1172
1173         /// <summary>
1174         /// Generate code for QilNodeType.Difference.
1175         /// </summary>
1176         protected override QilNode VisitDifference(QilBinary ndDiff) {
1177             return CreateSetIterator(ndDiff, "$$$iterDiff", typeof(DifferenceIterator), XmlILMethods.DiffCreate, XmlILMethods.DiffNext);
1178         }
1179
1180         /// <summary>
1181         /// Generate code to combine nodes from two nested iterators using Union, Intersection, or Difference semantics.
1182         /// </summary>
1183         private QilNode CreateSetIterator(QilBinary ndSet, string iterName, Type iterType, MethodInfo methCreate, MethodInfo methNext) {
1184             LocalBuilder locIter, locNav;
1185             Label lblNext, lblCall, lblNextLeft, lblNextRight, lblInitRight;
1186
1187             // SetIterator iterSet;
1188             // XPathNavigator navSet;
1189             locIter = this.helper.DeclareLocal(iterName, iterType);
1190             locNav = this.helper.DeclareLocal("$$$navSet", typeof(XPathNavigator));
1191
1192             // iterSet.Create(runtime);
1193             this.helper.Emit(OpCodes.Ldloca, locIter);
1194             this.helper.LoadQueryRuntime();
1195             this.helper.Call(methCreate);
1196
1197             // Define labels that will be used
1198             lblNext = this.helper.DefineLabel();
1199             lblCall = this.helper.DefineLabel();
1200             lblInitRight = this.helper.DefineLabel();
1201
1202             // Generate left nested iterator.  When it is empty, it will branch to lblNext.
1203             // goto LabelCall;
1204             NestedVisit(ndSet.Left, lblNext);
1205             lblNextLeft = this.iterNested.GetLabelNext();
1206             this.iterCurr.EnsureLocal(locNav);
1207             this.helper.EmitUnconditionalBranch(OpCodes.Brtrue, lblCall);
1208
1209             // Generate right nested iterator.  When it is empty, it will branch to lblNext.
1210             // LabelInitRight:
1211             // goto LabelCall;
1212             this.helper.MarkLabel(lblInitRight);
1213             NestedVisit(ndSet.Right, lblNext);
1214             lblNextRight = this.iterNested.GetLabelNext();
1215             this.iterCurr.EnsureLocal(locNav);
1216             this.helper.EmitUnconditionalBranch(OpCodes.Brtrue, lblCall);
1217
1218             // LabelNext:
1219             this.helper.MarkLabel(lblNext);
1220             this.helper.Emit(OpCodes.Ldnull);
1221             this.helper.Emit(OpCodes.Stloc, locNav);
1222
1223             // LabelCall:
1224             // switch (iterSet.MoveNext(nestedNested)) {
1225             //      case SetIteratorResult.NoMoreNodes: goto LabelNextCtxt;
1226             //      case SetIteratorResult.InitRightIterator: goto LabelInitRight;
1227             //      case SetIteratorResult.NeedLeftNode: goto LabelNextLeft;
1228             //      case SetIteratorResult.NeedRightNode: goto LabelNextRight;
1229             // }
1230             this.helper.MarkLabel(lblCall);
1231             this.helper.Emit(OpCodes.Ldloca, locIter);
1232             this.helper.Emit(OpCodes.Ldloc, locNav);
1233             this.helper.Call(methNext);
1234
1235             // If this iterator always returns a single node, then NoMoreNodes will never be returned
1236             // Don't expose Next label if this iterator always returns a single node
1237             if (ndSet.XmlType.IsSingleton) {
1238                 this.helper.Emit(OpCodes.Switch, new Label[] {lblInitRight, lblNextLeft, lblNextRight});
1239                 this.iterCurr.Storage = StorageDescriptor.Current(locIter, typeof(XPathNavigator));
1240             }
1241             else {
1242                 this.helper.Emit(OpCodes.Switch, new Label[] {this.iterCurr.GetLabelNext(), lblInitRight, lblNextLeft, lblNextRight});
1243                 this.iterCurr.SetIterator(lblNext, StorageDescriptor.Current(locIter, typeof(XPathNavigator)));
1244             }
1245
1246             return ndSet;
1247         }
1248
1249         /// <summary>
1250         /// Generate code for QilNodeType.Average.
1251         /// </summary>
1252         protected override QilNode VisitAverage(QilUnary ndAvg) {
1253             XmlILStorageMethods meths = XmlILMethods.StorageMethods[GetItemStorageType(ndAvg)];
1254             return CreateAggregator(ndAvg, "$$$aggAvg", meths, meths.AggAvg, meths.AggAvgResult);
1255         }
1256
1257         /// <summary>
1258         /// Generate code for QilNodeType.Sum.
1259         /// </summary>
1260         protected override QilNode VisitSum(QilUnary ndSum) {
1261             XmlILStorageMethods meths = XmlILMethods.StorageMethods[GetItemStorageType(ndSum)];
1262             return CreateAggregator(ndSum, "$$$aggSum", meths, meths.AggSum, meths.AggSumResult);
1263         }
1264
1265         /// <summary>
1266         /// Generate code for QilNodeType.Minimum.
1267         /// </summary>
1268         protected override QilNode VisitMinimum(QilUnary ndMin) {
1269             XmlILStorageMethods meths = XmlILMethods.StorageMethods[GetItemStorageType(ndMin)];
1270             return CreateAggregator(ndMin, "$$$aggMin", meths, meths.AggMin, meths.AggMinResult);
1271         }
1272
1273         /// <summary>
1274         /// Generate code for QilNodeType.Maximum.
1275         /// </summary>
1276         protected override QilNode VisitMaximum(QilUnary ndMax) {
1277             XmlILStorageMethods meths = XmlILMethods.StorageMethods[GetItemStorageType(ndMax)];
1278             return CreateAggregator(ndMax, "$$$aggMax", meths, meths.AggMax, meths.AggMaxResult);
1279         }
1280
1281         /// <summary>
1282         /// Generate code for QilNodeType.Sum, QilNodeType.Average, QilNodeType.Minimum, and QilNodeType.Maximum.
1283         /// </summary>
1284         private QilNode CreateAggregator(QilUnary ndAgg, string aggName, XmlILStorageMethods methods, MethodInfo methAgg, MethodInfo methResult) {
1285             Label lblOnEnd = this.helper.DefineLabel();
1286             Type typAgg = methAgg.DeclaringType;
1287             LocalBuilder locAgg;
1288
1289             // Aggregate agg;
1290             // agg.Create();
1291             locAgg = this.helper.DeclareLocal(aggName, typAgg);
1292             this.helper.Emit(OpCodes.Ldloca, locAgg);
1293             this.helper.Call(methods.AggCreate);
1294
1295             // foreach (num in expr) {
1296             StartNestedIterator(ndAgg.Child, lblOnEnd);
1297             this.helper.Emit(OpCodes.Ldloca, locAgg);
1298             Visit(ndAgg.Child);
1299
1300             //   agg.Aggregate(num);
1301             this.iterCurr.EnsureStackNoCache();
1302             this.iterCurr.EnsureItemStorageType(ndAgg.XmlType, GetItemStorageType(ndAgg));
1303             this.helper.Call(methAgg);
1304             this.helper.Emit(OpCodes.Ldloca, locAgg);
1305
1306             // }
1307             this.iterCurr.LoopToEnd(lblOnEnd);
1308
1309             // End nested iterator
1310             EndNestedIterator(ndAgg.Child);
1311
1312             // If aggregate might be empty sequence, then generate code to handle this possibility
1313             if (ndAgg.XmlType.MaybeEmpty) {
1314                 // if (agg.IsEmpty) goto LabelNextCtxt;
1315                 this.helper.Call(methods.AggIsEmpty);
1316                 this.helper.Emit(OpCodes.Brtrue, this.iterCurr.GetLabelNext());
1317                 this.helper.Emit(OpCodes.Ldloca, locAgg);
1318             }
1319
1320             // result = agg.Result;
1321             this.helper.Call(methResult);
1322             this.iterCurr.Storage = StorageDescriptor.Stack(GetItemStorageType(ndAgg), false);
1323
1324             return ndAgg;
1325         }
1326
1327         /// <summary>
1328         /// Generate code for QilNodeType.Negate.
1329         /// </summary>
1330         protected override QilNode VisitNegate(QilUnary ndNeg) {
1331             NestedVisitEnsureStack(ndNeg.Child);
1332             this.helper.CallArithmeticOp(QilNodeType.Negate, ndNeg.XmlType.TypeCode);
1333             this.iterCurr.Storage = StorageDescriptor.Stack(GetItemStorageType(ndNeg), false);
1334             return ndNeg;
1335         }
1336
1337         /// <summary>
1338         /// Generate code for QilNodeType.Add.
1339         /// </summary>
1340         protected override QilNode VisitAdd(QilBinary ndPlus) {
1341             return ArithmeticOp(ndPlus);
1342         }
1343
1344         /// <summary>
1345         /// Generate code for QilNodeType.Subtract.
1346         /// </summary>
1347         protected override QilNode VisitSubtract(QilBinary ndMinus) {
1348             return ArithmeticOp(ndMinus);
1349         }
1350
1351         /// <summary>
1352         /// Generate code for QilNodeType.Multiply.
1353         /// </summary>
1354         protected override QilNode VisitMultiply(QilBinary ndMul) {
1355             return ArithmeticOp(ndMul);
1356         }
1357
1358         /// <summary>
1359         /// Generate code for QilNodeType.Divide.
1360         /// </summary>
1361         protected override QilNode VisitDivide(QilBinary ndDiv) {
1362             return ArithmeticOp(ndDiv);
1363         }
1364
1365         /// <summary>
1366         /// Generate code for QilNodeType.Modulo.
1367         /// </summary>
1368         protected override QilNode VisitModulo(QilBinary ndMod) {
1369             return ArithmeticOp(ndMod);
1370         }
1371
1372         /// <summary>
1373         /// Generate code for two-argument arithmetic operations.
1374         /// </summary>
1375         private QilNode ArithmeticOp(QilBinary ndOp) {
1376             NestedVisitEnsureStack(ndOp.Left, ndOp.Right);
1377             this.helper.CallArithmeticOp(ndOp.NodeType, ndOp.XmlType.TypeCode);
1378             this.iterCurr.Storage = StorageDescriptor.Stack(GetItemStorageType(ndOp), false);
1379             return ndOp;
1380         }
1381
1382         /// <summary>
1383         /// Generate code for QilNodeType.StrLength.
1384         /// </summary>
1385         protected override QilNode VisitStrLength(QilUnary ndLen) {
1386             NestedVisitEnsureStack(ndLen.Child);
1387             this.helper.Call(XmlILMethods.StrLen);
1388             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(int), false);
1389             return ndLen;
1390         }
1391
1392         /// <summary>
1393         /// Generate code for QilNodeType.StrConcat.
1394         /// </summary>
1395         protected override QilNode VisitStrConcat(QilStrConcat ndStrConcat) {
1396             LocalBuilder locStringConcat;
1397             bool fasterConcat;
1398             QilNode delimiter;
1399             QilNode listStrings;
1400             Debug.Assert(!ndStrConcat.Values.XmlType.IsSingleton, "Optimizer should have folded StrConcat of a singleton value");
1401
1402             // Get delimiter (assuming it's not the empty string)
1403             delimiter = ndStrConcat.Delimiter;
1404             if (delimiter.NodeType == QilNodeType.LiteralString && ((string) (QilLiteral) delimiter).Length == 0) {
1405                 delimiter = null;
1406             }
1407
1408             listStrings = ndStrConcat.Values;
1409             if (listStrings.NodeType == QilNodeType.Sequence && listStrings.Count < 5) {
1410                 // Faster concat possible only if cardinality can be guaranteed at compile-time and there's no delimiter
1411                 fasterConcat = true;
1412                 foreach (QilNode ndStr in listStrings) {
1413                     if (!ndStr.XmlType.IsSingleton)
1414                         fasterConcat = false;
1415                 }
1416             }
1417             else {
1418                 // If more than 4 strings, array will need to be built
1419                 fasterConcat = false;
1420             }
1421
1422             if (fasterConcat) {
1423                 foreach (QilNode ndStr in listStrings)
1424                     NestedVisitEnsureStack(ndStr);
1425
1426                 this.helper.CallConcatStrings(listStrings.Count);
1427             }
1428             else {
1429                 // Create StringConcat helper internal class
1430                 locStringConcat = this.helper.DeclareLocal("$$$strcat", typeof(StringConcat));
1431                 this.helper.Emit(OpCodes.Ldloca, locStringConcat);
1432                 this.helper.Call(XmlILMethods.StrCatClear);
1433
1434                 // Set delimiter, if it's not empty string
1435                 if (delimiter != null) {
1436                     this.helper.Emit(OpCodes.Ldloca, locStringConcat);
1437                     NestedVisitEnsureStack(delimiter);
1438                     this.helper.Call(XmlILMethods.StrCatDelim);
1439                 }
1440
1441                 this.helper.Emit(OpCodes.Ldloca, locStringConcat);
1442
1443                 if (listStrings.NodeType == QilNodeType.Sequence) {
1444                     foreach (QilNode ndStr in listStrings)
1445                         GenerateConcat(ndStr, locStringConcat);
1446                 }
1447                 else {
1448                     GenerateConcat(listStrings, locStringConcat);
1449                 }
1450
1451                 // Push resulting string onto stack
1452                 this.helper.Call(XmlILMethods.StrCatResult);
1453             }
1454
1455             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(string), false);
1456
1457             return ndStrConcat;
1458         }
1459
1460         /// <summary>
1461         /// Generate code to concatenate string values returned by expression "ndStr" using the StringConcat helper class.
1462         /// </summary>
1463         private void GenerateConcat(QilNode ndStr, LocalBuilder locStringConcat) {
1464             Label lblOnEnd;
1465
1466             // str = each string;
1467             lblOnEnd = this.helper.DefineLabel();
1468             StartNestedIterator(ndStr, lblOnEnd);
1469             Visit(ndStr);
1470
1471             // strcat.Concat(str);
1472             this.iterCurr.EnsureStackNoCache();
1473             this.iterCurr.EnsureItemStorageType(ndStr.XmlType, typeof(string));
1474             this.helper.Call(XmlILMethods.StrCatCat);
1475             this.helper.Emit(OpCodes.Ldloca, locStringConcat);
1476
1477             // Get next string
1478             // goto LabelNext;
1479             // LabelOnEnd:
1480             this.iterCurr.LoopToEnd(lblOnEnd);
1481
1482             // End nested iterator
1483             EndNestedIterator(ndStr);
1484         }
1485
1486         /// <summary>
1487         /// Generate code for QilNodeType.StrParseQName.
1488         /// </summary>
1489         protected override QilNode VisitStrParseQName(QilBinary ndParsedTagName) {
1490             VisitStrParseQName(ndParsedTagName, false);
1491             return ndParsedTagName;
1492         }
1493
1494         /// <summary>
1495         /// Generate code for QilNodeType.StrParseQName.
1496         /// </summary>
1497         private void VisitStrParseQName(QilBinary ndParsedTagName, bool preservePrefix) {
1498             // If QName prefix should be preserved, then don't create an XmlQualifiedName, which discards the prefix
1499             if (!preservePrefix)
1500                 this.helper.LoadQueryRuntime();
1501
1502             // Push (possibly computed) tag name onto the stack
1503             NestedVisitEnsureStack(ndParsedTagName.Left);
1504
1505             // If type of second parameter is string,
1506             if (ndParsedTagName.Right.XmlType.TypeCode == XmlTypeCode.String) {
1507                 // Then push (possibly computed) namespace onto the stack
1508                 Debug.Assert(ndParsedTagName.Right.XmlType.IsSingleton);
1509                 NestedVisitEnsureStack(ndParsedTagName.Right);
1510
1511                 if (!preservePrefix)
1512                     this.helper.CallParseTagName(GenerateNameType.TagNameAndNamespace);
1513             }
1514             else {
1515                 // Else push index of set of prefix mappings to use in resolving the prefix
1516                 if (ndParsedTagName.Right.NodeType == QilNodeType.Sequence)
1517                     this.helper.LoadInteger(this.helper.StaticData.DeclarePrefixMappings(ndParsedTagName.Right));
1518                 else
1519                     this.helper.LoadInteger(this.helper.StaticData.DeclarePrefixMappings(new QilNode[] {ndParsedTagName.Right}));
1520
1521                 // If QName prefix should be preserved, then don't create an XmlQualifiedName, which discards the prefix
1522                 if (!preservePrefix)
1523                     this.helper.CallParseTagName(GenerateNameType.TagNameAndMappings);
1524             }
1525
1526             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(XmlQualifiedName), false);
1527         }
1528
1529         /// <summary>
1530         /// Generate code for QilNodeType.Ne.
1531         /// </summary>
1532         protected override QilNode VisitNe(QilBinary ndNe) {
1533             Compare(ndNe);
1534             return ndNe;
1535         }
1536
1537         /// <summary>
1538         /// Generate code for QilNodeType.Eq.
1539         /// </summary>
1540         protected override QilNode VisitEq(QilBinary ndEq) {
1541             Compare(ndEq);
1542             return ndEq;
1543         }
1544
1545         /// <summary>
1546         /// Generate code for QilNodeType.Gt.
1547         /// </summary>
1548         protected override QilNode VisitGt(QilBinary ndGt) {
1549             Compare(ndGt);
1550             return ndGt;
1551         }
1552
1553         /// <summary>
1554         /// Generate code for QilNodeType.Ne.
1555         /// </summary>
1556         protected override QilNode VisitGe(QilBinary ndGe) {
1557             Compare(ndGe);
1558             return ndGe;
1559         }
1560
1561         /// <summary>
1562         /// Generate code for QilNodeType.Lt.
1563         /// </summary>
1564         protected override QilNode VisitLt(QilBinary ndLt) {
1565             Compare(ndLt);
1566             return ndLt;
1567         }
1568
1569         /// <summary>
1570         /// Generate code for QilNodeType.Le.
1571         /// </summary>
1572         protected override QilNode VisitLe(QilBinary ndLe) {
1573             Compare(ndLe);
1574             return ndLe;
1575         }
1576
1577         /// <summary>
1578         /// Generate code for comparison operations.
1579         /// </summary>
1580         private void Compare(QilBinary ndComp) {
1581             QilNodeType relOp = ndComp.NodeType;
1582             XmlTypeCode code;
1583             Debug.Assert(ndComp.Left.XmlType.IsAtomicValue && ndComp.Right.XmlType.IsAtomicValue, "Operands to compare must be atomic values.");
1584             Debug.Assert(ndComp.Left.XmlType.IsSingleton && ndComp.Right.XmlType.IsSingleton, "Operands to compare must be cardinality one.");
1585             Debug.Assert(ndComp.Left.XmlType == ndComp.Right.XmlType, "Operands to compare may not be heterogenous.");
1586
1587             if (relOp == QilNodeType.Eq || relOp == QilNodeType.Ne) {
1588                 // Generate better code for certain special cases
1589                 if (TryZeroCompare(relOp, ndComp.Left, ndComp.Right))
1590                     return;
1591
1592                 if (TryZeroCompare(relOp, ndComp.Right, ndComp.Left))
1593                     return;
1594
1595                 if (TryNameCompare(relOp, ndComp.Left, ndComp.Right))
1596                     return;
1597
1598                 if (TryNameCompare(relOp, ndComp.Right, ndComp.Left))
1599                     return;
1600             }
1601
1602             // Push two operands onto the stack
1603             NestedVisitEnsureStack(ndComp.Left, ndComp.Right);
1604
1605             // Perform comparison
1606             code = ndComp.Left.XmlType.TypeCode;
1607             switch (code) {
1608                 case XmlTypeCode.String:
1609                 case XmlTypeCode.Decimal:
1610                 case XmlTypeCode.QName:
1611                     if (relOp == QilNodeType.Eq || relOp == QilNodeType.Ne) {
1612                         this.helper.CallCompareEquals(code);
1613
1614                         // If relOp is Eq, then branch to true label or push "true" if Equals function returns true (non-zero)
1615                         // If relOp is Ne, then branch to true label or push "true" if Equals function returns false (zero)
1616                         ZeroCompare((relOp == QilNodeType.Eq) ? QilNodeType.Ne : QilNodeType.Eq, true);
1617                     }
1618                     else {
1619                         Debug.Assert(code != XmlTypeCode.QName, "QName values do not support the " + relOp + " operation");
1620
1621                         // Push -1, 0, or 1 onto the stack depending upon the result of the comparison
1622                         this.helper.CallCompare(code);
1623
1624                         // Compare result to 0 (e.g. Ge is >= 0)
1625                         this.helper.Emit(OpCodes.Ldc_I4_0);
1626                         ClrCompare(relOp, code);
1627                     }
1628                     break;
1629
1630                 case XmlTypeCode.Integer:
1631                 case XmlTypeCode.Int:
1632                 case XmlTypeCode.Boolean:
1633                 case XmlTypeCode.Double:
1634                     ClrCompare(relOp, code);
1635                     break;
1636
1637                 default:
1638                     Debug.Fail("Comparisons for datatype " + code + " are invalid.");
1639                     break;
1640             }
1641         }
1642
1643         /// <summary>
1644         /// Generate code for QilNodeType.VisitIs.
1645         /// </summary>
1646         protected override QilNode VisitIs(QilBinary ndIs) {
1647             // Generate code to push arguments onto stack
1648             NestedVisitEnsureStack(ndIs.Left, ndIs.Right);
1649             this.helper.Call(XmlILMethods.NavSamePos);
1650
1651             // navThis.IsSamePosition(navThat);
1652             ZeroCompare(QilNodeType.Ne, true);
1653             return ndIs;
1654         }
1655
1656         /// <summary>
1657         /// Generate code for QilNodeType.VisitBefore.
1658         /// </summary>
1659         protected override QilNode VisitBefore(QilBinary ndBefore) {
1660             ComparePosition(ndBefore);
1661             return ndBefore;
1662         }
1663
1664         /// <summary>
1665         /// Generate code for QilNodeType.VisitAfter.
1666         /// </summary>
1667         protected override QilNode VisitAfter(QilBinary ndAfter) {
1668             ComparePosition(ndAfter);
1669             return ndAfter;
1670         }
1671
1672         /// <summary>
1673         /// Generate code for QilNodeType.VisitBefore and QilNodeType.VisitAfter.
1674         /// </summary>
1675         private void ComparePosition(QilBinary ndComp) {
1676             // Generate code to push arguments onto stack
1677             this.helper.LoadQueryRuntime();
1678             NestedVisitEnsureStack(ndComp.Left, ndComp.Right);
1679             this.helper.Call(XmlILMethods.CompPos);
1680
1681             // XmlQueryRuntime.ComparePosition(navThis, navThat) < 0;
1682             this.helper.LoadInteger(0);
1683             ClrCompare(ndComp.NodeType == QilNodeType.Before ? QilNodeType.Lt : QilNodeType.Gt, XmlTypeCode.String);
1684         }
1685
1686         /// <summary>
1687         /// Generate code for a QilNodeType.For.
1688         /// </summary>
1689         protected override QilNode VisitFor(QilIterator ndFor) {
1690             IteratorDescriptor iterInfo;
1691
1692             // Reference saved location
1693             iterInfo = XmlILAnnotation.Write(ndFor).CachedIteratorDescriptor;
1694             this.iterCurr.Storage = iterInfo.Storage;
1695
1696             // If the iterator is a reference to a global variable or parameter,
1697             if (this.iterCurr.Storage.Location == ItemLocation.Global) {
1698                 // Then compute global value and push it onto the stack
1699                 this.iterCurr.EnsureStack();
1700             }
1701
1702             return ndFor;
1703         }
1704
1705         /// <summary>
1706         /// Generate code for a QilNodeType.Let.
1707         /// </summary>
1708         protected override QilNode VisitLet(QilIterator ndLet) {
1709             // Same as For
1710             return VisitFor(ndLet);
1711         }
1712
1713         /// <summary>
1714         /// Generate code for a QilNodeType.Parameter.
1715         /// </summary>
1716         protected override QilNode VisitParameter(QilParameter ndParameter) {
1717             // Same as For
1718             return VisitFor(ndParameter);
1719         }
1720
1721         /// <summary>
1722         /// Generate code for a QilNodeType.Loop.
1723         /// </summary>
1724         protected override QilNode VisitLoop(QilLoop ndLoop) {
1725             bool hasOnEnd;
1726             Label lblOnEnd;
1727
1728             StartWriterLoop(ndLoop, out hasOnEnd, out lblOnEnd);
1729
1730             StartBinding(ndLoop.Variable);
1731
1732             // Unnest loop body as part of the current iterator
1733             Visit(ndLoop.Body);
1734
1735             EndBinding(ndLoop.Variable);
1736
1737             EndWriterLoop(ndLoop, hasOnEnd, lblOnEnd);
1738
1739             return ndLoop;
1740         }
1741
1742         /// <summary>
1743         /// Generate code for a QilNodeType.Filter.
1744         /// </summary>
1745         protected override QilNode VisitFilter(QilLoop ndFilter) {
1746             // Handle any special-case patterns that are rooted at Filter
1747             if (HandleFilterPatterns(ndFilter))
1748                 return ndFilter;
1749
1750             StartBinding(ndFilter.Variable);
1751
1752             // Result of filter is the sequence bound to the iterator
1753             this.iterCurr.SetIterator(this.iterNested);
1754
1755             // If filter is false, skip the current item
1756             StartNestedIterator(ndFilter.Body);
1757             this.iterCurr.SetBranching(BranchingContext.OnFalse, this.iterCurr.ParentIterator.GetLabelNext());
1758             Visit(ndFilter.Body);
1759             EndNestedIterator(ndFilter.Body);
1760
1761             EndBinding(ndFilter.Variable);
1762
1763             return ndFilter;
1764         }
1765
1766         /// <summary>
1767         /// There are a number of path patterns that can be rooted at Filter nodes.  Determine whether one of these patterns
1768         /// has been previously matched on "ndFilter".  If so, generate code for the pattern and return true.  Otherwise, just
1769         /// return false.
1770         /// </summary>
1771         private bool HandleFilterPatterns(QilLoop ndFilter) {
1772             OptimizerPatterns patt = OptimizerPatterns.Read(ndFilter);
1773             LocalBuilder locIter;
1774             XmlNodeKindFlags kinds;
1775             QilName name;
1776             QilNode input, step;
1777             bool isFilterElements;
1778
1779             // Handle FilterElements and FilterContentKind patterns
1780             isFilterElements = patt.MatchesPattern(OptimizerPatternName.FilterElements);
1781             if (isFilterElements || patt.MatchesPattern(OptimizerPatternName.FilterContentKind)) {
1782                 if (isFilterElements) {
1783                     // FilterElements pattern, so Kind = Element and Name = Argument
1784                     kinds = XmlNodeKindFlags.Element;
1785                     name = (QilName) patt.GetArgument(OptimizerPatternArgument.ElementQName);
1786                 }
1787                 else {
1788                     // FilterKindTest pattern, so Kind = Argument and Name = null
1789                     kinds = ((XmlQueryType) patt.GetArgument(OptimizerPatternArgument.KindTestType)).NodeKinds;
1790                     name = null;
1791                 }
1792
1793                 step = (QilNode) patt.GetArgument(OptimizerPatternArgument.StepNode);
1794                 input = (QilNode) patt.GetArgument(OptimizerPatternArgument.StepInput);
1795                 switch (step.NodeType) {
1796                     case QilNodeType.Content:
1797                         if (isFilterElements) {
1798                             // Iterator iter;
1799                             locIter = this.helper.DeclareLocal("$$$iterElemContent", typeof(ElementContentIterator));
1800
1801                             // iter.Create(navCtxt, locName, ns);
1802                             this.helper.Emit(OpCodes.Ldloca, locIter);
1803                             NestedVisitEnsureStack(input);
1804                             this.helper.CallGetAtomizedName(this.helper.StaticData.DeclareName(name.LocalName));
1805                             this.helper.CallGetAtomizedName(this.helper.StaticData.DeclareName(name.NamespaceUri));
1806                             this.helper.Call(XmlILMethods.ElemContentCreate);
1807
1808                             GenerateSimpleIterator(typeof(XPathNavigator), locIter, XmlILMethods.ElemContentNext);
1809                         }
1810                         else {
1811                             if (kinds == XmlNodeKindFlags.Content) {
1812                                 CreateSimpleIterator(input, "$$$iterContent", typeof(ContentIterator), XmlILMethods.ContentCreate, XmlILMethods.ContentNext);
1813                             }
1814                             else {
1815                                 // Iterator iter;
1816                                 locIter = this.helper.DeclareLocal("$$$iterContent", typeof(NodeKindContentIterator));
1817
1818                                 // iter.Create(navCtxt, nodeType);
1819                                 this.helper.Emit(OpCodes.Ldloca, locIter);
1820                                 NestedVisitEnsureStack(input);
1821                                 this.helper.LoadInteger((int) QilXmlToXPathNodeType(kinds));
1822                                 this.helper.Call(XmlILMethods.KindContentCreate);
1823
1824                                 GenerateSimpleIterator(typeof(XPathNavigator), locIter, XmlILMethods.KindContentNext);
1825                             }
1826                         }
1827                         return true;
1828
1829                     case QilNodeType.Parent:
1830                         CreateFilteredIterator(input, "$$$iterPar", typeof(ParentIterator), XmlILMethods.ParentCreate, XmlILMethods.ParentNext,
1831                                                kinds, name, TriState.Unknown, null);
1832                         return true;
1833
1834                     case QilNodeType.Ancestor:
1835                     case QilNodeType.AncestorOrSelf:
1836                         CreateFilteredIterator(input, "$$$iterAnc", typeof(AncestorIterator), XmlILMethods.AncCreate, XmlILMethods.AncNext,
1837                                                kinds, name, (step.NodeType == QilNodeType.Ancestor) ? TriState.False : TriState.True, null);
1838                         return true;
1839
1840                     case QilNodeType.Descendant:
1841                     case QilNodeType.DescendantOrSelf:
1842                         CreateFilteredIterator(input, "$$$iterDesc", typeof(DescendantIterator), XmlILMethods.DescCreate, XmlILMethods.DescNext,
1843                                                kinds, name, (step.NodeType == QilNodeType.Descendant) ? TriState.False : TriState.True, null);
1844                         return true;
1845
1846                     case QilNodeType.Preceding:
1847                         CreateFilteredIterator(input, "$$$iterPrec", typeof(PrecedingIterator), XmlILMethods.PrecCreate, XmlILMethods.PrecNext,
1848                                                kinds, name, TriState.Unknown, null);
1849                         return true;
1850
1851                     case QilNodeType.FollowingSibling:
1852                         CreateFilteredIterator(input, "$$$iterFollSib", typeof(FollowingSiblingIterator), XmlILMethods.FollSibCreate, XmlILMethods.FollSibNext,
1853                                                kinds, name, TriState.Unknown, null);
1854                         return true;
1855
1856                     case QilNodeType.PrecedingSibling:
1857                         CreateFilteredIterator(input, "$$$iterPreSib", typeof(PrecedingSiblingIterator), XmlILMethods.PreSibCreate, XmlILMethods.PreSibNext,
1858                                                kinds, name, TriState.Unknown, null);
1859                         return true;
1860
1861                     case QilNodeType.NodeRange:
1862                         CreateFilteredIterator(input, "$$$iterRange", typeof(NodeRangeIterator), XmlILMethods.NodeRangeCreate, XmlILMethods.NodeRangeNext,
1863                                                kinds, name, TriState.Unknown, ((QilBinary) step).Right);
1864                         return true;
1865
1866                     case QilNodeType.XPathFollowing:
1867                         CreateFilteredIterator(input, "$$$iterFoll", typeof(XPathFollowingIterator), XmlILMethods.XPFollCreate, XmlILMethods.XPFollNext,
1868                                                kinds, name, TriState.Unknown, null);
1869                         return true;
1870
1871                     case QilNodeType.XPathPreceding:
1872                         CreateFilteredIterator(input, "$$$iterPrec", typeof(XPathPrecedingIterator), XmlILMethods.XPPrecCreate, XmlILMethods.XPPrecNext,
1873                                                kinds, name, TriState.Unknown, null);
1874                         return true;
1875
1876                     default:
1877                         Debug.Assert(false, "Pattern " + step.NodeType + " should have been handled.");
1878                         break;
1879                 }
1880             }
1881             else if (patt.MatchesPattern(OptimizerPatternName.FilterAttributeKind)) {
1882                 // Handle FilterAttributeKind pattern
1883                 input = (QilNode) patt.GetArgument(OptimizerPatternArgument.StepInput);
1884                 CreateSimpleIterator(input, "$$$iterAttr", typeof(AttributeIterator), XmlILMethods.AttrCreate, XmlILMethods.AttrNext);
1885                 return true;
1886             }
1887             else if (patt.MatchesPattern(OptimizerPatternName.EqualityIndex)) {
1888                 // Handle EqualityIndex pattern
1889                 Label lblOnEnd = this.helper.DefineLabel();
1890                 Label lblLookup = this.helper.DefineLabel();
1891                 QilIterator nodes = (QilIterator) patt.GetArgument(OptimizerPatternArgument.IndexedNodes);
1892                 QilNode keys = (QilNode) patt.GetArgument(OptimizerPatternArgument.KeyExpression);
1893
1894                 // XmlILIndex index;
1895                 // if (runtime.FindIndex(navCtxt, indexId, out index)) goto LabelLookup;
1896                 LocalBuilder locIndex = this.helper.DeclareLocal("$$$index", typeof(XmlILIndex));
1897                 this.helper.LoadQueryRuntime();
1898                 this.helper.Emit(OpCodes.Ldarg_1);
1899                 this.helper.LoadInteger(this.indexId);
1900                 this.helper.Emit(OpCodes.Ldloca, locIndex);
1901                 this.helper.Call(XmlILMethods.FindIndex);
1902                 this.helper.Emit(OpCodes.Brtrue, lblLookup);
1903
1904                 // runtime.AddNewIndex(navCtxt, indexId, [build index]);
1905                 this.helper.LoadQueryRuntime();
1906                 this.helper.Emit(OpCodes.Ldarg_1);
1907                 this.helper.LoadInteger(this.indexId);
1908                 this.helper.Emit(OpCodes.Ldloc, locIndex);
1909
1910                 // Generate code to iterate over the the nodes which are being indexed ($iterNodes in the pattern)
1911                 StartNestedIterator(nodes, lblOnEnd);
1912                 StartBinding(nodes);
1913
1914                 // Generate code to iterate over the keys for each node ($bindingKeys in the pattern)
1915                 Visit(keys);
1916
1917                 // index.Add(key, value);
1918                 this.iterCurr.EnsureStackNoCache();
1919                 VisitFor(nodes);
1920                 this.iterCurr.EnsureStackNoCache();
1921                 this.iterCurr.EnsureItemStorageType(nodes.XmlType, typeof(XPathNavigator));
1922                 this.helper.Call(XmlILMethods.IndexAdd);
1923                 this.helper.Emit(OpCodes.Ldloc, locIndex);
1924
1925                 // LabelOnEnd:
1926                 this.iterCurr.LoopToEnd(lblOnEnd);
1927                 EndBinding(nodes);
1928                 EndNestedIterator(nodes);
1929
1930                 // runtime.AddNewIndex(navCtxt, indexId, [build index]);
1931                 this.helper.Call(XmlILMethods.AddNewIndex);
1932
1933                 // LabelLookup:
1934                 // results = index.Lookup(keyValue);
1935                 this.helper.MarkLabel(lblLookup);
1936                 this.helper.Emit(OpCodes.Ldloc, locIndex);
1937                 this.helper.Emit(OpCodes.Ldarg_2);
1938                 this.helper.Call(XmlILMethods.IndexLookup);
1939                 this.iterCurr.Storage = StorageDescriptor.Stack(typeof(XPathNavigator), true);
1940
1941                 this.indexId++;
1942
1943                 return true;
1944             }
1945
1946             return false;
1947         }
1948
1949         /// <summary>
1950         /// Generate code for a Let, For, or Parameter iterator.  Bind iterated value to a variable.
1951         /// </summary>
1952         private void StartBinding(QilIterator ndIter) {
1953             OptimizerPatterns patt = OptimizerPatterns.Read(ndIter);
1954             Debug.Assert(ndIter != null);
1955
1956             // DebugInfo: Sequence point just before generating code for the bound expression
1957             if (this.qil.IsDebug && ndIter.SourceLine != null)
1958                 this.helper.DebugSequencePoint(ndIter.SourceLine);
1959
1960             // Treat cardinality one Let iterators as if they were For iterators (no nesting necessary)
1961             if (ndIter.NodeType == QilNodeType.For || ndIter.XmlType.IsSingleton) {
1962                 StartForBinding(ndIter, patt);
1963             }
1964             else {
1965                 Debug.Assert(ndIter.NodeType == QilNodeType.Let || ndIter.NodeType == QilNodeType.Parameter);
1966                 Debug.Assert(!patt.MatchesPattern(OptimizerPatternName.IsPositional));
1967
1968                 // Bind Let values (nested iterator) to variable
1969                 StartLetBinding(ndIter);
1970             }
1971
1972             // Attach IteratorDescriptor to the iterator
1973             XmlILAnnotation.Write(ndIter).CachedIteratorDescriptor = this.iterNested;
1974         }
1975
1976         /// <summary>
1977         /// Bind values produced by the "ndFor" expression to a non-stack location that can later
1978         /// be referenced.
1979         /// </summary>
1980         private void StartForBinding(QilIterator ndFor, OptimizerPatterns patt) {
1981             LocalBuilder locPos = null;
1982             Debug.Assert(ndFor.XmlType.IsSingleton);
1983
1984             // For expression iterator will be unnested as part of parent iterator
1985             if (this.iterCurr.HasLabelNext)
1986                 StartNestedIterator(ndFor.Binding, this.iterCurr.GetLabelNext());
1987             else
1988                 StartNestedIterator(ndFor.Binding);
1989
1990             if (patt.MatchesPattern(OptimizerPatternName.IsPositional)) {
1991                 // Need to track loop index so initialize it to 0 before starting loop
1992                 locPos = this.helper.DeclareLocal("$$$pos", typeof(int));
1993                 this.helper.Emit(OpCodes.Ldc_I4_0);
1994                 this.helper.Emit(OpCodes.Stloc, locPos);
1995             }
1996
1997             // Allow base internal class to dispatch based on QilExpression node type
1998             Visit(ndFor.Binding);
1999
2000             // DebugInfo: Open variable scope
2001             // DebugInfo: Ensure that for variable is stored in a local and tag it with the user-defined name
2002             if (this.qil.IsDebug && ndFor.DebugName != null) {
2003                 this.helper.DebugStartScope();
2004
2005                 // Ensure that values are stored in a local variable with a user-defined name
2006                 this.iterCurr.EnsureLocalNoCache("$$$for");
2007                 this.iterCurr.Storage.LocalLocation.SetLocalSymInfo(ndFor.DebugName);
2008             }
2009             else {
2010                 // Ensure that values are not stored on the stack
2011                 this.iterCurr.EnsureNoStackNoCache("$$$for");
2012             }
2013
2014             if (patt.MatchesPattern(OptimizerPatternName.IsPositional)) {
2015                 // Increment position
2016                 this.helper.Emit(OpCodes.Ldloc, locPos);
2017                 this.helper.Emit(OpCodes.Ldc_I4_1);
2018                 this.helper.Emit(OpCodes.Add);
2019                 this.helper.Emit(OpCodes.Stloc, locPos);
2020
2021                 if (patt.MatchesPattern(OptimizerPatternName.MaxPosition)) {
2022                     // Short-circuit rest of loop if max position has already been reached
2023                     this.helper.Emit(OpCodes.Ldloc, locPos);
2024                     this.helper.LoadInteger((int) patt.GetArgument(OptimizerPatternArgument.MaxPosition));
2025                     this.helper.Emit(OpCodes.Bgt, this.iterCurr.ParentIterator.GetLabelNext());
2026                 }
2027
2028                 this.iterCurr.LocalPosition = locPos;
2029             }
2030
2031             EndNestedIterator(ndFor.Binding);
2032             this.iterCurr.SetIterator(this.iterNested);
2033         }
2034
2035         /// <summary>
2036         /// Bind values in the "ndLet" expression to a non-stack location that can later be referenced.
2037         /// </summary>
2038         public void StartLetBinding(QilIterator ndLet) {
2039             Debug.Assert(!ndLet.XmlType.IsSingleton);
2040
2041             // Construct nested iterator
2042             StartNestedIterator(ndLet);
2043
2044             // Allow base internal class to dispatch based on QilExpression node type
2045             NestedVisit(ndLet.Binding, GetItemStorageType(ndLet), !ndLet.XmlType.IsSingleton);
2046
2047             // DebugInfo: Open variable scope
2048             // DebugInfo: Ensure that for variable is stored in a local and tag it with the user-defined name
2049             if (this.qil.IsDebug && ndLet.DebugName != null) {
2050                 this.helper.DebugStartScope();
2051
2052                 // Ensure that cache is stored in a local variable with a user-defined name
2053                 this.iterCurr.EnsureLocal("$$$cache");
2054                 this.iterCurr.Storage.LocalLocation.SetLocalSymInfo(ndLet.DebugName);
2055             }
2056             else {
2057                 // Ensure that cache is not stored on the stack
2058                 this.iterCurr.EnsureNoStack("$$$cache");
2059             }
2060
2061             EndNestedIterator(ndLet);
2062         }
2063
2064         /// <summary>
2065         /// Mark iterator variables as out-of-scope.
2066         /// </summary>
2067         private void EndBinding(QilIterator ndIter) {
2068             Debug.Assert(ndIter != null);
2069
2070             // Variables go out of scope here
2071             if (this.qil.IsDebug && ndIter.DebugName != null)
2072                 this.helper.DebugEndScope();
2073         }
2074
2075         /// <summary>
2076         /// Generate code for QilNodeType.PositionOf.
2077         /// </summary>
2078         protected override QilNode VisitPositionOf(QilUnary ndPos) {
2079             QilIterator ndIter = ndPos.Child as QilIterator;
2080             LocalBuilder locPos;
2081             Debug.Assert(ndIter.NodeType == QilNodeType.For);
2082
2083             locPos = XmlILAnnotation.Write(ndIter).CachedIteratorDescriptor.LocalPosition;
2084             Debug.Assert(locPos != null);
2085             this.iterCurr.Storage = StorageDescriptor.Local(locPos, typeof(int), false);
2086
2087             return ndPos;
2088         }
2089
2090         /// <summary>
2091         /// Generate code for QilNodeType.Sort.
2092         /// </summary>
2093         protected override QilNode VisitSort(QilLoop ndSort) {
2094             Type itemStorageType = GetItemStorageType(ndSort);
2095             LocalBuilder locCache, locKeys;
2096             Label lblOnEndSort = this.helper.DefineLabel();
2097             Debug.Assert(ndSort.Variable.NodeType == QilNodeType.For);
2098
2099             // XmlQuerySequence<T> cache;
2100             // cache = XmlQuerySequence.CreateOrReuse(cache);
2101             XmlILStorageMethods methods = XmlILMethods.StorageMethods[itemStorageType];
2102             locCache = this.helper.DeclareLocal("$$$cache", methods.SeqType);
2103             this.helper.Emit(OpCodes.Ldloc, locCache);
2104             this.helper.CallToken(methods.SeqReuse);
2105             this.helper.Emit(OpCodes.Stloc, locCache);
2106             this.helper.Emit(OpCodes.Ldloc, locCache);
2107
2108             // XmlSortKeyAccumulator keys;
2109             // keys.Create(runtime);
2110             locKeys = this.helper.DeclareLocal("$$$keys", typeof(XmlSortKeyAccumulator));
2111             this.helper.Emit(OpCodes.Ldloca, locKeys);
2112             this.helper.Call(XmlILMethods.SortKeyCreate);
2113
2114             // Construct nested iterator
2115             // foreach (item in sort-expr) {
2116             StartNestedIterator(ndSort.Variable, lblOnEndSort);
2117             StartBinding(ndSort.Variable);
2118             Debug.Assert(!this.iterNested.Storage.IsCached);
2119
2120             // cache.Add(item);
2121             this.iterCurr.EnsureStackNoCache();
2122             this.iterCurr.EnsureItemStorageType(ndSort.Variable.XmlType, GetItemStorageType(ndSort.Variable));
2123             this.helper.Call(methods.SeqAdd);
2124
2125             this.helper.Emit(OpCodes.Ldloca, locKeys);
2126
2127             // Add keys to accumulator (there may be several keys)
2128             foreach (QilSortKey ndKey in ndSort.Body)
2129                 VisitSortKey(ndKey, locKeys);
2130
2131             // keys.FinishSortKeys();
2132             this.helper.Call(XmlILMethods.SortKeyFinish);
2133
2134             // }
2135             this.helper.Emit(OpCodes.Ldloc, locCache);
2136             this.iterCurr.LoopToEnd(lblOnEndSort);
2137
2138             // Remove cache reference from stack
2139             this.helper.Emit(OpCodes.Pop);
2140
2141             // cache.SortByKeys(keys.Keys);
2142             this.helper.Emit(OpCodes.Ldloc, locCache);
2143             this.helper.Emit(OpCodes.Ldloca, locKeys);
2144             this.helper.Call(XmlILMethods.SortKeyKeys);
2145             this.helper.Call(methods.SeqSortByKeys);
2146
2147             // End nested iterator
2148             this.iterCurr.Storage = StorageDescriptor.Local(locCache, itemStorageType, true);
2149             EndBinding(ndSort.Variable);
2150             EndNestedIterator(ndSort.Variable);
2151             this.iterCurr.SetIterator(this.iterNested);
2152
2153             return ndSort;
2154         }
2155
2156         /// <summary>
2157         /// Generate code to add a (value, collation) sort key to the XmlSortKeyAccumulator.
2158         /// </summary>
2159         private void VisitSortKey(QilSortKey ndKey, LocalBuilder locKeys) {
2160             Label lblOnEndKey;
2161             Debug.Assert(ndKey.Key.XmlType.IsAtomicValue, "Sort key must be an atomic value.");
2162
2163             // Push collation onto the stack
2164             this.helper.Emit(OpCodes.Ldloca, locKeys);
2165             if (ndKey.Collation.NodeType == QilNodeType.LiteralString) {
2166                 // collation = runtime.GetCollation(idx);
2167                 this.helper.CallGetCollation(this.helper.StaticData.DeclareCollation((string) (QilLiteral) ndKey.Collation));
2168             }
2169             else {
2170                 // collation = runtime.CreateCollation(str);
2171                 this.helper.LoadQueryRuntime();
2172                 NestedVisitEnsureStack(ndKey.Collation);
2173                 this.helper.Call(XmlILMethods.CreateCollation);
2174             }
2175
2176             if (ndKey.XmlType.IsSingleton) {
2177                 NestedVisitEnsureStack(ndKey.Key);
2178
2179                 // keys.AddSortKey(collation, value);
2180                 this.helper.AddSortKey(ndKey.Key.XmlType);
2181             }
2182             else {
2183                 lblOnEndKey = this.helper.DefineLabel();
2184                 StartNestedIterator(ndKey.Key, lblOnEndKey);
2185                 Visit(ndKey.Key);
2186                 this.iterCurr.EnsureStackNoCache();
2187                 this.iterCurr.EnsureItemStorageType(ndKey.Key.XmlType, GetItemStorageType(ndKey.Key));
2188
2189                 // Non-empty sort key
2190                 // keys.AddSortKey(collation, value);
2191                 this.helper.AddSortKey(ndKey.Key.XmlType);
2192
2193                 // goto LabelDone;
2194                 // LabelOnEnd:
2195                 Label lblDone = this.helper.DefineLabel();
2196                 this.helper.EmitUnconditionalBranch(OpCodes.Br_S, lblDone);
2197                 this.helper.MarkLabel(lblOnEndKey);
2198
2199                 // Empty sequence key
2200                 // keys.AddSortKey(collation);
2201                 this.helper.AddSortKey(null);
2202
2203                 this.helper.MarkLabel(lblDone);
2204
2205                 EndNestedIterator(ndKey.Key);
2206             }
2207         }
2208
2209         /// <summary>
2210         /// Generate code for for QilNodeType.DocOrderDistinct.
2211         /// </summary>
2212         protected override QilNode VisitDocOrderDistinct(QilUnary ndDod) {
2213             // DocOrderDistinct applied to a singleton is a no-op
2214             if (ndDod.XmlType.IsSingleton)
2215                 return Visit(ndDod.Child);
2216
2217             // Handle any special-case patterns that are rooted at DocOrderDistinct
2218             if (HandleDodPatterns(ndDod))
2219                 return ndDod;
2220
2221             // Sort results of child expression by document order and remove duplicate nodes
2222             // cache = runtime.DocOrderDistinct(cache);
2223             this.helper.LoadQueryRuntime();
2224             NestedVisitEnsureCache(ndDod.Child, typeof(XPathNavigator));
2225             this.iterCurr.EnsureStack();
2226             this.helper.Call(XmlILMethods.DocOrder);
2227             return ndDod;
2228         }
2229
2230         /// <summary>
2231         /// There are a number of path patterns that can be rooted at DocOrderDistinct nodes.  Determine whether one of these
2232         /// patterns has been previously matched on "ndDod".  If so, generate code for the pattern and return true.  Otherwise,
2233         /// just return false.
2234         /// </summary>
2235         private bool HandleDodPatterns(QilUnary ndDod) {
2236             OptimizerPatterns pattDod = OptimizerPatterns.Read(ndDod);
2237             XmlNodeKindFlags kinds;
2238             QilName name;
2239             QilNode input, step;
2240             bool isJoinAndDod;
2241
2242             // Handle JoinAndDod and DodReverse patterns
2243             isJoinAndDod = pattDod.MatchesPattern(OptimizerPatternName.JoinAndDod);
2244             if (isJoinAndDod || pattDod.MatchesPattern(OptimizerPatternName.DodReverse)) {
2245                 OptimizerPatterns pattStep = OptimizerPatterns.Read((QilNode) pattDod.GetArgument(OptimizerPatternArgument.DodStep));
2246
2247                 if (pattStep.MatchesPattern(OptimizerPatternName.FilterElements)) {
2248                     // FilterElements pattern, so Kind = Element and Name = Argument
2249                     kinds = XmlNodeKindFlags.Element;
2250                     name = (QilName) pattStep.GetArgument(OptimizerPatternArgument.ElementQName);
2251                 }
2252                 else if (pattStep.MatchesPattern(OptimizerPatternName.FilterContentKind)) {
2253                     // FilterKindTest pattern, so Kind = Argument and Name = null
2254                     kinds = ((XmlQueryType) pattStep.GetArgument(OptimizerPatternArgument.KindTestType)).NodeKinds;
2255                     name = null;
2256                 }
2257                 else {
2258                     Debug.Assert(pattStep.MatchesPattern(OptimizerPatternName.Axis), "Dod patterns should only match if step is FilterElements or FilterKindTest or Axis");
2259                     kinds = ((ndDod.XmlType.NodeKinds & XmlNodeKindFlags.Attribute) != 0) ? XmlNodeKindFlags.Any : XmlNodeKindFlags.Content;
2260                     name = null;
2261                 }
2262
2263                 step = (QilNode) pattStep.GetArgument(OptimizerPatternArgument.StepNode);
2264                 if (isJoinAndDod) {
2265                     switch (step.NodeType) {
2266                         case QilNodeType.Content:
2267                             CreateContainerIterator(ndDod, "$$$iterContent", typeof(ContentMergeIterator), XmlILMethods.ContentMergeCreate, XmlILMethods.ContentMergeNext,
2268                                                     kinds, name, TriState.Unknown);
2269                             return true;
2270
2271                         case QilNodeType.Descendant:
2272                         case QilNodeType.DescendantOrSelf:
2273                             CreateContainerIterator(ndDod, "$$$iterDesc", typeof(DescendantMergeIterator), XmlILMethods.DescMergeCreate, XmlILMethods.DescMergeNext,
2274                                                     kinds, name, (step.NodeType == QilNodeType.Descendant) ? TriState.False : TriState.True);
2275                             return true;
2276
2277                         case QilNodeType.XPathFollowing:
2278                             CreateContainerIterator(ndDod, "$$$iterFoll", typeof(XPathFollowingMergeIterator), XmlILMethods.XPFollMergeCreate, XmlILMethods.XPFollMergeNext,
2279                                                     kinds, name, TriState.Unknown);
2280                             return true;
2281
2282                         case QilNodeType.FollowingSibling:
2283                             CreateContainerIterator(ndDod, "$$$iterFollSib", typeof(FollowingSiblingMergeIterator), XmlILMethods.FollSibMergeCreate, XmlILMethods.FollSibMergeNext,
2284                                                     kinds, name, TriState.Unknown);
2285                             return true;
2286
2287                         case QilNodeType.XPathPreceding:
2288                             CreateContainerIterator(ndDod, "$$$iterPrec", typeof(XPathPrecedingMergeIterator), XmlILMethods.XPPrecMergeCreate, XmlILMethods.XPPrecMergeNext,
2289                                                     kinds, name, TriState.Unknown);
2290                             return true;
2291
2292                         default:
2293                             Debug.Assert(false, "Pattern " + step.NodeType + " should have been handled.");
2294                             break;
2295                     }
2296                 }
2297                 else {
2298                     input = (QilNode) pattStep.GetArgument(OptimizerPatternArgument.StepInput);
2299                     switch (step.NodeType) {
2300                         case QilNodeType.Ancestor:
2301                         case QilNodeType.AncestorOrSelf:
2302                             CreateFilteredIterator(input, "$$$iterAnc", typeof(AncestorDocOrderIterator), XmlILMethods.AncDOCreate, XmlILMethods.AncDONext,
2303                                                    kinds, name, (step.NodeType == QilNodeType.Ancestor) ? TriState.False : TriState.True, null);
2304                             return true;
2305
2306                         case QilNodeType.PrecedingSibling:
2307                             CreateFilteredIterator(input, "$$$iterPreSib", typeof(PrecedingSiblingDocOrderIterator), XmlILMethods.PreSibDOCreate, XmlILMethods.PreSibDONext,
2308                                                    kinds, name, TriState.Unknown, null);
2309                             return true;
2310
2311                         case QilNodeType.XPathPreceding:
2312                             CreateFilteredIterator(input, "$$$iterPrec", typeof(XPathPrecedingDocOrderIterator), XmlILMethods.XPPrecDOCreate, XmlILMethods.XPPrecDONext,
2313                                                    kinds, name, TriState.Unknown, null);
2314                             return true;
2315
2316                         default:
2317                             Debug.Assert(false, "Pattern " + step.NodeType + " should have been handled.");
2318                             break;
2319                     }
2320                 }
2321             }
2322             else if (pattDod.MatchesPattern(OptimizerPatternName.DodMerge)) {
2323                 // DodSequenceMerge dodMerge;
2324                 LocalBuilder locMerge = this.helper.DeclareLocal("$$$dodMerge", typeof(DodSequenceMerge));
2325                 Label lblOnEnd = this.helper.DefineLabel();
2326
2327                 // dodMerge.Create(runtime);
2328                 this.helper.Emit(OpCodes.Ldloca, locMerge);
2329                 this.helper.LoadQueryRuntime();
2330                 this.helper.Call(XmlILMethods.DodMergeCreate);
2331                 this.helper.Emit(OpCodes.Ldloca, locMerge);
2332
2333                 StartNestedIterator(ndDod.Child, lblOnEnd);
2334
2335                 // foreach (seq in expr) {
2336                 Visit(ndDod.Child);
2337
2338                 // dodMerge.AddSequence(seq);
2339                 Debug.Assert(this.iterCurr.Storage.IsCached, "DodMerge pattern should only be matched when cached sequences are returned from loop");
2340                 this.iterCurr.EnsureStack();
2341                 this.helper.Call(XmlILMethods.DodMergeAdd);
2342                 this.helper.Emit(OpCodes.Ldloca, locMerge);
2343
2344                 // }
2345                 this.iterCurr.LoopToEnd(lblOnEnd);
2346
2347                 EndNestedIterator(ndDod.Child);
2348
2349                 // mergedSequence = dodMerge.MergeSequences();
2350                 this.helper.Call(XmlILMethods.DodMergeSeq);
2351
2352                 this.iterCurr.Storage = StorageDescriptor.Stack(typeof(XPathNavigator), true);
2353
2354                 return true;
2355             }
2356
2357             return false;
2358         }
2359
2360         /// <summary>
2361         /// Generate code for for QilNodeType.Invoke.
2362         /// </summary>
2363         protected override QilNode VisitInvoke(QilInvoke ndInvoke) {
2364             QilFunction ndFunc = ndInvoke.Function;
2365             MethodInfo methInfo = XmlILAnnotation.Write(ndFunc).FunctionBinding;
2366             bool useWriter = (XmlILConstructInfo.Read(ndFunc).ConstructMethod == XmlILConstructMethod.Writer);
2367             Debug.Assert(!XmlILConstructInfo.Read(ndInvoke).PushToWriterFirst || useWriter);
2368
2369             // Push XmlQueryRuntime onto the stack as the first parameter
2370             this.helper.LoadQueryRuntime();
2371
2372             // Generate code to push each Invoke argument onto the stack
2373             for (int iArg = 0; iArg < ndInvoke.Arguments.Count; iArg++) {
2374                 QilNode ndActualArg = ndInvoke.Arguments[iArg];
2375                 QilNode ndFormalArg = ndInvoke.Function.Arguments[iArg];
2376                 NestedVisitEnsureStack(ndActualArg, GetItemStorageType(ndFormalArg), !ndFormalArg.XmlType.IsSingleton);
2377             }
2378
2379             // Check whether this call should compiled using the .tailcall instruction
2380             if (OptimizerPatterns.Read(ndInvoke).MatchesPattern(OptimizerPatternName.TailCall))
2381                 this.helper.TailCall(methInfo);
2382             else
2383                 this.helper.Call(methInfo);
2384
2385             // If function's results are not pushed to Writer,
2386             if (!useWriter) {
2387                 // Return value is on the stack; ensure it has the correct storage type
2388                 this.iterCurr.Storage = StorageDescriptor.Stack(GetItemStorageType(ndInvoke), !ndInvoke.XmlType.IsSingleton);
2389             }
2390             else {
2391                 this.iterCurr.Storage = StorageDescriptor.None();
2392             }
2393
2394             return ndInvoke;
2395         }
2396
2397         /// <summary>
2398         /// Generate code for for QilNodeType.Content.
2399         /// </summary>
2400         protected override QilNode VisitContent(QilUnary ndContent) {
2401             CreateSimpleIterator(ndContent.Child, "$$$iterAttrContent", typeof(AttributeContentIterator), XmlILMethods.AttrContentCreate, XmlILMethods.AttrContentNext);
2402             return ndContent;
2403         }
2404
2405         /// <summary>
2406         /// Generate code for for QilNodeType.Attribute.
2407         /// </summary>
2408         protected override QilNode VisitAttribute(QilBinary ndAttr) {
2409             QilName ndName = ndAttr.Right as QilName;
2410             Debug.Assert(ndName != null, "Attribute node must have a literal QName as its second argument");
2411
2412             // XPathNavigator navAttr;
2413             LocalBuilder locNav = this.helper.DeclareLocal("$$$navAttr", typeof(XPathNavigator));
2414
2415             // navAttr = SyncToNavigator(navAttr, navCtxt);
2416             SyncToNavigator(locNav, ndAttr.Left);
2417
2418             // if (!navAttr.MoveToAttribute(localName, namespaceUri)) goto LabelNextCtxt;
2419             this.helper.Emit(OpCodes.Ldloc, locNav);
2420             this.helper.CallGetAtomizedName(this.helper.StaticData.DeclareName(ndName.LocalName));
2421             this.helper.CallGetAtomizedName(this.helper.StaticData.DeclareName(ndName.NamespaceUri));
2422             this.helper.Call(XmlILMethods.NavMoveAttr);
2423             this.helper.Emit(OpCodes.Brfalse, this.iterCurr.GetLabelNext());
2424
2425             this.iterCurr.Storage = StorageDescriptor.Local(locNav, typeof(XPathNavigator), false);
2426             return ndAttr;
2427         }
2428
2429         /// <summary>
2430         /// Generate code for for QilNodeType.Parent.
2431         /// </summary>
2432         protected override QilNode VisitParent(QilUnary ndParent) {
2433             // XPathNavigator navParent;
2434             LocalBuilder locNav = this.helper.DeclareLocal("$$$navParent", typeof(XPathNavigator));
2435
2436             // navParent = SyncToNavigator(navParent, navCtxt);
2437             SyncToNavigator(locNav, ndParent.Child);
2438
2439             // if (!navParent.MoveToParent()) goto LabelNextCtxt;
2440             this.helper.Emit(OpCodes.Ldloc, locNav);
2441             this.helper.Call(XmlILMethods.NavMoveParent);
2442             this.helper.Emit(OpCodes.Brfalse, this.iterCurr.GetLabelNext());
2443
2444             this.iterCurr.Storage = StorageDescriptor.Local(locNav, typeof(XPathNavigator), false);
2445             return ndParent;
2446         }
2447
2448         /// <summary>
2449         /// Generate code for for QilNodeType.Root.
2450         /// </summary>
2451         protected override QilNode VisitRoot(QilUnary ndRoot) {
2452             // XPathNavigator navRoot;
2453             LocalBuilder locNav = this.helper.DeclareLocal("$$$navRoot", typeof(XPathNavigator));
2454
2455             // navRoot = SyncToNavigator(navRoot, navCtxt);
2456             SyncToNavigator(locNav, ndRoot.Child);
2457
2458             // navRoot.MoveToRoot();
2459             this.helper.Emit(OpCodes.Ldloc, locNav);
2460             this.helper.Call(XmlILMethods.NavMoveRoot);
2461
2462             this.iterCurr.Storage = StorageDescriptor.Local(locNav, typeof(XPathNavigator), false);
2463             return ndRoot;
2464         }
2465
2466         /// <summary>
2467         /// Generate code for QilNodeType.XmlContext.
2468         /// </summary>
2469         /// <remarks>
2470         /// Generates code to retrieve the default document using the XmlResolver.
2471         /// </remarks>
2472         protected override QilNode VisitXmlContext(QilNode ndCtxt) {
2473             // runtime.ExternalContext.DefaultDataSource
2474             this.helper.LoadQueryContext();
2475             this.helper.Call(XmlILMethods.GetDefaultDataSource);
2476             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(XPathNavigator), false);
2477             return ndCtxt;
2478         }
2479
2480         /// <summary>
2481         /// Find physical query plan for QilNodeType.Descendant.
2482         /// </summary>
2483         protected override QilNode VisitDescendant(QilUnary ndDesc) {
2484             CreateFilteredIterator(ndDesc.Child, "$$$iterDesc", typeof(DescendantIterator), XmlILMethods.DescCreate, XmlILMethods.DescNext,
2485                                    XmlNodeKindFlags.Any, null, TriState.False, null);
2486             return ndDesc;
2487         }
2488
2489         /// <summary>
2490         /// Generate code for for QilNodeType.DescendantOrSelf.
2491         /// </summary>
2492         protected override QilNode VisitDescendantOrSelf(QilUnary ndDesc) {
2493             CreateFilteredIterator(ndDesc.Child, "$$$iterDesc", typeof(DescendantIterator), XmlILMethods.DescCreate, XmlILMethods.DescNext,
2494                                    XmlNodeKindFlags.Any, null, TriState.True, null);
2495             return ndDesc;
2496         }
2497
2498         /// <summary>
2499         /// Find physical query plan for QilNodeType.Ancestor.
2500         /// </summary>
2501         protected override QilNode VisitAncestor(QilUnary ndAnc) {
2502             CreateFilteredIterator(ndAnc.Child, "$$$iterAnc", typeof(AncestorIterator), XmlILMethods.AncCreate, XmlILMethods.AncNext,
2503                                    XmlNodeKindFlags.Any, null, TriState.False, null);
2504             return ndAnc;
2505         }
2506
2507         /// <summary>
2508         /// Find physical query plan for QilNodeType.AncestorOrSelf.
2509         /// </summary>
2510         protected override QilNode VisitAncestorOrSelf(QilUnary ndAnc) {
2511             CreateFilteredIterator(ndAnc.Child, "$$$iterAnc", typeof(AncestorIterator), XmlILMethods.AncCreate, XmlILMethods.AncNext,
2512                                    XmlNodeKindFlags.Any, null, TriState.True, null);
2513             return ndAnc;
2514         }
2515
2516         /// <summary>
2517         /// Find physical query plan for QilNodeType.Preceding.
2518         /// </summary>
2519         protected override QilNode VisitPreceding(QilUnary ndPrec) {
2520             CreateFilteredIterator(ndPrec.Child, "$$$iterPrec", typeof(PrecedingIterator), XmlILMethods.PrecCreate, XmlILMethods.PrecNext,
2521                                    XmlNodeKindFlags.Any, null, TriState.Unknown, null);
2522             return ndPrec;
2523         }
2524
2525         /// <summary>
2526         /// Find physical query plan for QilNodeType.FollowingSibling.
2527         /// </summary>
2528         protected override QilNode VisitFollowingSibling(QilUnary ndFollSib) {
2529             CreateFilteredIterator(ndFollSib.Child, "$$$iterFollSib", typeof(FollowingSiblingIterator), XmlILMethods.FollSibCreate, XmlILMethods.FollSibNext,
2530                                    XmlNodeKindFlags.Any, null, TriState.Unknown, null);
2531             return ndFollSib;
2532         }
2533
2534         /// <summary>
2535         /// Find physical query plan for QilNodeType.PrecedingSibling.
2536         /// </summary>
2537         protected override QilNode VisitPrecedingSibling(QilUnary ndPreSib) {
2538             CreateFilteredIterator(ndPreSib.Child, "$$$iterPreSib", typeof(PrecedingSiblingIterator), XmlILMethods.PreSibCreate, XmlILMethods.PreSibNext,
2539                                    XmlNodeKindFlags.Any, null, TriState.Unknown, null);
2540             return ndPreSib;
2541         }
2542
2543         /// <summary>
2544         /// Find physical query plan for QilNodeType.NodeRange.
2545         /// </summary>
2546         protected override QilNode VisitNodeRange(QilBinary ndRange) {
2547             CreateFilteredIterator(ndRange.Left, "$$$iterRange", typeof(NodeRangeIterator), XmlILMethods.NodeRangeCreate, XmlILMethods.NodeRangeNext,
2548                                    XmlNodeKindFlags.Any, null, TriState.Unknown, ndRange.Right);
2549             return ndRange;
2550         }
2551
2552         /// <summary>
2553         /// Generate code for for QilNodeType.Deref.
2554         /// </summary>
2555         protected override QilNode VisitDeref(QilBinary ndDeref) {
2556             // IdIterator iterId;
2557             LocalBuilder locIter = this.helper.DeclareLocal("$$$iterId", typeof(IdIterator));
2558
2559             // iterId.Create(navCtxt, value);
2560             this.helper.Emit(OpCodes.Ldloca, locIter);
2561             NestedVisitEnsureStack(ndDeref.Left);
2562             NestedVisitEnsureStack(ndDeref.Right);
2563             this.helper.Call(XmlILMethods.IdCreate);
2564
2565             GenerateSimpleIterator(typeof(XPathNavigator), locIter, XmlILMethods.IdNext);
2566
2567             return ndDeref;
2568         }
2569
2570         /// <summary>
2571         /// Generate code for QilNodeType.ElementCtor.
2572         /// </summary>
2573         protected override QilNode VisitElementCtor(QilBinary ndElem) {
2574             XmlILConstructInfo info = XmlILConstructInfo.Read(ndElem);
2575             bool callChk;
2576             GenerateNameType nameType;
2577             Debug.Assert(XmlILConstructInfo.Read(ndElem).PushToWriterFirst, "Element contruction should always be pushed to writer.");
2578
2579             // Runtime checks must be made in the following cases:
2580             //   1. Xml state is not known at compile-time, or is illegal
2581             //   2. Element's namespace must be declared
2582             //   3. Element's attributes might be duplicates of one another, or namespaces might follow attributes
2583             callChk = CheckWithinContent(info) || !info.IsNamespaceInScope || ElementCachesAttributes(info);
2584
2585             // If it is not known whether element content was output, then make this check at run-time
2586             if (XmlILConstructInfo.Read(ndElem.Right).FinalStates == PossibleXmlStates.Any)
2587                 callChk = true;
2588
2589             // If runtime state after EndElement is called is not known, then call XmlQueryOutput.WriteEndElementChk
2590             if (info.FinalStates == PossibleXmlStates.Any)
2591                 callChk = true;
2592
2593             // If WriteStartElementChk will *not* be called, then code must be generated to ensure valid state transitions
2594             if (!callChk)
2595                 BeforeStartChecks(ndElem);
2596
2597             // Generate call to WriteStartElement
2598             nameType = LoadNameAndType(XPathNodeType.Element, ndElem.Left, true, callChk);
2599             this.helper.CallWriteStartElement(nameType, callChk);
2600
2601             // Recursively construct content
2602             NestedVisit(ndElem.Right);
2603
2604             // If runtime state is guaranteed to be EnumAttrs, and an element is being constructed, call XmlQueryOutput.StartElementContent
2605             if (XmlILConstructInfo.Read(ndElem.Right).FinalStates == PossibleXmlStates.EnumAttrs && !callChk)
2606                 this.helper.CallStartElementContent();
2607
2608             // Generate call to WriteEndElement
2609             nameType = LoadNameAndType(XPathNodeType.Element, ndElem.Left, false, callChk);
2610             this.helper.CallWriteEndElement(nameType, callChk);
2611
2612             if (!callChk)
2613                 AfterEndChecks(ndElem);
2614
2615             this.iterCurr.Storage = StorageDescriptor.None();
2616             return ndElem;
2617         }
2618
2619         /// <summary>
2620         /// Generate code for QilNodeType.AttributeCtor.
2621         /// </summary>
2622         protected override QilNode VisitAttributeCtor(QilBinary ndAttr) {
2623             XmlILConstructInfo info = XmlILConstructInfo.Read(ndAttr);
2624             bool callChk;
2625             GenerateNameType nameType;
2626             Debug.Assert(XmlILConstructInfo.Read(ndAttr).PushToWriterFirst, "Attribute construction should always be pushed to writer.");
2627
2628             // Runtime checks must be made in the following cases:
2629             //   1. Xml state is not known at compile-time, or is illegal
2630             //   2. Attribute's namespace must be declared
2631             callChk = CheckEnumAttrs(info) || !info.IsNamespaceInScope;
2632
2633             // If WriteStartAttributeChk will *not* be called, then code must be generated to ensure well-formedness
2634             // and track namespace scope.
2635             if (!callChk)
2636                 BeforeStartChecks(ndAttr);
2637
2638             // Generate call to WriteStartAttribute
2639             nameType = LoadNameAndType(XPathNodeType.Attribute, ndAttr.Left, true, callChk);
2640             this.helper.CallWriteStartAttribute(nameType, callChk);
2641
2642             // Recursively construct content
2643             NestedVisit(ndAttr.Right);
2644
2645             // Generate call to WriteEndAttribute
2646             this.helper.CallWriteEndAttribute(callChk);
2647
2648             if (!callChk)
2649                 AfterEndChecks(ndAttr);
2650
2651             this.iterCurr.Storage = StorageDescriptor.None();
2652             return ndAttr;
2653         }
2654
2655         /// <summary>
2656         /// Generate code for QilNodeType.CommentCtor.
2657         /// </summary>
2658         protected override QilNode VisitCommentCtor(QilUnary ndComment) {
2659             Debug.Assert(XmlILConstructInfo.Read(ndComment).PushToWriterFirst, "Comment construction should always be pushed to writer.");
2660
2661             // Always call XmlQueryOutput.WriteStartComment
2662             this.helper.CallWriteStartComment();
2663
2664             // Recursively construct content
2665             NestedVisit(ndComment.Child);
2666
2667             // Always call XmlQueryOutput.WriteEndComment
2668             this.helper.CallWriteEndComment();
2669
2670             this.iterCurr.Storage = StorageDescriptor.None();
2671             return ndComment;
2672         }
2673
2674         /// <summary>
2675         /// Generate code for QilNodeType.PICtor.
2676         /// </summary>
2677         protected override QilNode VisitPICtor(QilBinary ndPI) {
2678             Debug.Assert(XmlILConstructInfo.Read(ndPI).PushToWriterFirst, "PI construction should always be pushed to writer.");
2679
2680             // Always call XmlQueryOutput.WriteStartPI
2681             this.helper.LoadQueryOutput();
2682             NestedVisitEnsureStack(ndPI.Left);
2683             this.helper.CallWriteStartPI();
2684
2685             // Recursively construct content
2686             NestedVisit(ndPI.Right);
2687
2688             // Always call XmlQueryOutput.WriteEndPI
2689             this.helper.CallWriteEndPI();
2690
2691             this.iterCurr.Storage = StorageDescriptor.None();
2692             return ndPI;
2693         }
2694
2695         /// <summary>
2696         /// Generate code for QilNodeType.TextCtor.
2697         /// </summary>
2698         protected override QilNode VisitTextCtor(QilUnary ndText) {
2699             return VisitTextCtor(ndText, false);
2700         }
2701
2702         /// <summary>
2703         /// Generate code for QilNodeType.RawTextCtor.
2704         /// </summary>
2705         protected override QilNode VisitRawTextCtor(QilUnary ndText) {
2706             return VisitTextCtor(ndText, true);
2707         }
2708
2709         /// <summary>
2710         /// Generate code for QilNodeType.TextCtor and QilNodeType.RawTextCtor.
2711         /// </summary>
2712         private QilNode VisitTextCtor(QilUnary ndText, bool disableOutputEscaping) {
2713             XmlILConstructInfo info = XmlILConstructInfo.Read(ndText);
2714             bool callChk;
2715             Debug.Assert(info.PushToWriterFirst, "Text construction should always be pushed to writer.");
2716
2717             // Write out text in different contexts (within attribute, within element, within comment, etc.)
2718             switch (info.InitialStates) {
2719                 case PossibleXmlStates.WithinAttr:
2720                 case PossibleXmlStates.WithinComment:
2721                 case PossibleXmlStates.WithinPI:
2722                     callChk = false;
2723                     break;
2724
2725                 default:
2726                     callChk = CheckWithinContent(info);
2727                     break;
2728             }
2729
2730             if (!callChk)
2731                 BeforeStartChecks(ndText);
2732
2733             this.helper.LoadQueryOutput();
2734
2735             // Push string value of text onto IL stack
2736             NestedVisitEnsureStack(ndText.Child);
2737
2738             // Write out text in different contexts (within attribute, within element, within comment, etc.)
2739             switch (info.InitialStates) {
2740                 case PossibleXmlStates.WithinAttr:
2741                     // Ignore hints when writing out attribute text
2742                     this.helper.CallWriteString(false, callChk);
2743                     break;
2744
2745                 case PossibleXmlStates.WithinComment:
2746                     // Call XmlQueryOutput.WriteCommentString
2747                     this.helper.Call(XmlILMethods.CommentText);
2748                     break;
2749
2750                 case PossibleXmlStates.WithinPI:
2751                     // Call XmlQueryOutput.WriteProcessingInstructionString
2752                     this.helper.Call(XmlILMethods.PIText);
2753                     break;
2754
2755                 default:
2756                     // Call XmlQueryOutput.WriteTextBlockChk, XmlQueryOutput.WriteTextBlockNoEntities, or XmlQueryOutput.WriteTextBlock
2757                     this.helper.CallWriteString(disableOutputEscaping, callChk);
2758                     break;
2759             }
2760
2761             if (!callChk)
2762                 AfterEndChecks(ndText);
2763
2764             this.iterCurr.Storage = StorageDescriptor.None();
2765             return ndText;
2766         }
2767
2768         /// <summary>
2769         /// Generate code for QilNodeType.DocumentCtor.
2770         /// </summary>
2771         protected override QilNode VisitDocumentCtor(QilUnary ndDoc) {
2772             Debug.Assert(XmlILConstructInfo.Read(ndDoc).PushToWriterFirst, "Document root construction should always be pushed to writer.");
2773
2774             // Generate call to XmlQueryOutput.WriteStartRootChk
2775             this.helper.CallWriteStartRoot();
2776
2777             // Recursively construct content
2778             NestedVisit(ndDoc.Child);
2779
2780             // Generate call to XmlQueryOutput.WriteEndRootChk
2781             this.helper.CallWriteEndRoot();
2782
2783             this.iterCurr.Storage = StorageDescriptor.None();
2784
2785             return ndDoc;
2786         }
2787
2788         /// <summary>
2789         /// Generate code for QilNodeType.NamespaceDecl.
2790         /// </summary>
2791         protected override QilNode VisitNamespaceDecl(QilBinary ndNmsp) {
2792             XmlILConstructInfo info = XmlILConstructInfo.Read(ndNmsp);
2793             bool callChk;
2794             Debug.Assert(info.PushToWriterFirst, "Namespace construction should always be pushed to writer.");
2795
2796             // Runtime checks must be made in the following cases:
2797             //   1. Xml state is not known at compile-time, or is illegal
2798             //   2. Namespaces might be added to element after attributes have already been added
2799             callChk = CheckEnumAttrs(info) || MightHaveNamespacesAfterAttributes(info);
2800
2801             // If WriteNamespaceDeclarationChk will *not* be called, then code must be generated to ensure well-formedness
2802             // and track namespace scope.
2803             if (!callChk)
2804                 BeforeStartChecks(ndNmsp);
2805
2806             this.helper.LoadQueryOutput();
2807
2808             // Recursively construct prefix and ns
2809             NestedVisitEnsureStack(ndNmsp.Left);
2810             NestedVisitEnsureStack(ndNmsp.Right);
2811
2812             // Generate call to WriteNamespaceDecl
2813             this.helper.CallWriteNamespaceDecl(callChk);
2814
2815             if (!callChk)
2816                 AfterEndChecks(ndNmsp);
2817
2818             this.iterCurr.Storage = StorageDescriptor.None();
2819             return ndNmsp;
2820         }
2821
2822         /// <summary>
2823         /// Generate code for for QilNodeType.RtfCtor.
2824         /// </summary>
2825         protected override QilNode VisitRtfCtor(QilBinary ndRtf) {
2826             OptimizerPatterns patt = OptimizerPatterns.Read(ndRtf);
2827             string baseUri = (string) (QilLiteral) ndRtf.Right;
2828
2829             if (patt.MatchesPattern(OptimizerPatternName.SingleTextRtf)) {
2830                 // Special-case Rtf containing a root node and a single text node child
2831                 this.helper.LoadQueryRuntime();
2832                 NestedVisitEnsureStack((QilNode) patt.GetArgument(OptimizerPatternArgument.RtfText));
2833                 this.helper.Emit(OpCodes.Ldstr, baseUri);
2834                 this.helper.Call(XmlILMethods.RtfConstr);
2835             }
2836             else {
2837                 // Start nested construction of an Rtf
2838                 this.helper.CallStartRtfConstruction(baseUri);
2839
2840                 // Write content of Rtf to writer
2841                 NestedVisit(ndRtf.Left);
2842
2843                 // Get the result Rtf
2844                 this.helper.CallEndRtfConstruction();
2845             }
2846
2847             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(XPathNavigator), false);
2848             return ndRtf;
2849         }
2850
2851         /// <summary>
2852         /// Generate code for QilNodeType.NameOf.
2853         /// </summary>
2854         protected override QilNode VisitNameOf(QilUnary ndName) {
2855             return VisitNodeProperty(ndName);
2856         }
2857
2858         /// <summary>
2859         /// Generate code for QilNodeType.LocalNameOf.
2860         /// </summary>
2861         protected override QilNode VisitLocalNameOf(QilUnary ndName) {
2862             return VisitNodeProperty(ndName);
2863         }
2864
2865         /// <summary>
2866         /// Generate code for QilNodeType.NamespaceUriOf.
2867         /// </summary>
2868         protected override QilNode VisitNamespaceUriOf(QilUnary ndName) {
2869             return VisitNodeProperty(ndName);
2870         }
2871
2872         /// <summary>
2873         /// Generate code for QilNodeType.PrefixOf.
2874         /// </summary>
2875         protected override QilNode VisitPrefixOf(QilUnary ndName) {
2876             return VisitNodeProperty(ndName);
2877         }
2878
2879         /// <summary>
2880         /// Generate code to push the local name, namespace uri, or qname of the context navigator.
2881         /// </summary>
2882         private QilNode VisitNodeProperty(QilUnary ndProp) {
2883             // Generate code to push argument onto stack
2884             NestedVisitEnsureStack(ndProp.Child);
2885
2886             switch (ndProp.NodeType) {
2887                 case QilNodeType.NameOf:
2888                     // push new XmlQualifiedName(navigator.LocalName, navigator.NamespaceURI);
2889                     this.helper.Emit(OpCodes.Dup);
2890                     this.helper.Call(XmlILMethods.NavLocalName);
2891                     this.helper.Call(XmlILMethods.NavNmsp);
2892                     this.helper.Construct(XmlILConstructors.QName);
2893                     this.iterCurr.Storage = StorageDescriptor.Stack(typeof(XmlQualifiedName), false);
2894                     break;
2895
2896                 case QilNodeType.LocalNameOf:
2897                     // push navigator.Name;
2898                     this.helper.Call(XmlILMethods.NavLocalName);
2899                     this.iterCurr.Storage = StorageDescriptor.Stack(typeof(string), false);
2900                     break;
2901
2902                 case QilNodeType.NamespaceUriOf:
2903                     // push navigator.NamespaceURI;
2904                     this.helper.Call(XmlILMethods.NavNmsp);
2905                     this.iterCurr.Storage = StorageDescriptor.Stack(typeof(string), false);
2906                     break;
2907
2908                 case QilNodeType.PrefixOf:
2909                     // push navigator.Prefix;
2910                     this.helper.Call(XmlILMethods.NavPrefix);
2911                     this.iterCurr.Storage = StorageDescriptor.Stack(typeof(string), false);
2912                     break;
2913
2914                 default:
2915                     Debug.Assert(false);
2916                     break;
2917             }
2918
2919             return ndProp;
2920         }
2921
2922         /// <summary>
2923         /// Find physical query plan for QilNodeType.TypeAssert.
2924         /// </summary>
2925         protected override QilNode VisitTypeAssert(QilTargetType ndTypeAssert) {
2926             if (!ndTypeAssert.Source.XmlType.IsSingleton && ndTypeAssert.XmlType.IsSingleton && !this.iterCurr.HasLabelNext) {
2927                 // This case occurs when a non-singleton expression is treated as cardinality One.
2928                 // The trouble is that the expression will branch to an end label when it's done iterating, so
2929                 // an end label must be provided.  But there is no next label in the current iteration context,
2930                 // so we've got to create a dummy label instead (IL requires it).  This creates an infinite loop,
2931                 // but since it's known statically that the expression is cardinality One, this branch will never
2932                 // be taken.
2933                 Label lblDummy = this.helper.DefineLabel();
2934                 this.helper.MarkLabel(lblDummy);
2935                 NestedVisit(ndTypeAssert.Source, lblDummy);
2936             }
2937             else {
2938                 // Generate code for child expression
2939                 Visit(ndTypeAssert.Source);
2940             }
2941
2942             this.iterCurr.EnsureItemStorageType(ndTypeAssert.Source.XmlType, GetItemStorageType(ndTypeAssert));
2943             return ndTypeAssert;
2944         }
2945
2946         /// <summary>
2947         /// Generate code for QilNodeType.IsType.
2948         /// </summary>
2949         protected override QilNode VisitIsType(QilTargetType ndIsType) {
2950             XmlQueryType typDerived, typBase;
2951             XmlTypeCode codeBase;
2952
2953             typDerived = ndIsType.Source.XmlType;
2954             typBase = ndIsType.TargetType;
2955             Debug.Assert(!typDerived.NeverSubtypeOf(typBase), "Normalizer should have eliminated IsType where source can never be a subtype of destination type.");
2956
2957             // Special Case: Test whether singleton item is a Node
2958             if (typDerived.IsSingleton && (object) typBase == (object) TypeFactory.Node) {
2959                 NestedVisitEnsureStack(ndIsType.Source);
2960                 Debug.Assert(this.iterCurr.Storage.ItemStorageType == typeof(XPathItem), "If !IsNode, then storage type should be Item");
2961
2962                 // if (item.IsNode op true) goto LabelBranch;
2963                 this.helper.Call(XmlILMethods.ItemIsNode);
2964                 ZeroCompare(QilNodeType.Ne, true);
2965
2966                 return ndIsType;
2967             }
2968
2969             // Special Case: Source value is a singleton Node, and we're testing whether it is an Element, Attribute, PI, etc.
2970             if (MatchesNodeKinds(ndIsType, typDerived, typBase))
2971                 return ndIsType;
2972
2973             // Special Case: XmlTypeCode is sufficient to describe destination type
2974             if ((object) typBase == (object) TypeFactory.Double) codeBase = XmlTypeCode.Double;
2975             else if ((object) typBase == (object) TypeFactory.String) codeBase = XmlTypeCode.String;
2976             else if ((object) typBase == (object) TypeFactory.Boolean) codeBase = XmlTypeCode.Boolean;
2977             else if ((object) typBase == (object) TypeFactory.Node) codeBase = XmlTypeCode.Node;
2978             else codeBase = XmlTypeCode.None;
2979
2980             if (codeBase != XmlTypeCode.None) {
2981                 // if (runtime.MatchesXmlType(value, code) op true) goto LabelBranch;
2982                 this.helper.LoadQueryRuntime();
2983                 NestedVisitEnsureStack(ndIsType.Source, typeof(XPathItem), !typDerived.IsSingleton);
2984                 this.helper.LoadInteger((int) codeBase);
2985                 this.helper.Call(typDerived.IsSingleton ? XmlILMethods.ItemMatchesCode : XmlILMethods.SeqMatchesCode);
2986                 ZeroCompare(QilNodeType.Ne, true);
2987
2988                 return ndIsType;
2989             }
2990
2991             // if (runtime.MatchesXmlType(value, idxType) op true) goto LabelBranch;
2992             this.helper.LoadQueryRuntime();
2993             NestedVisitEnsureStack(ndIsType.Source, typeof(XPathItem), !typDerived.IsSingleton);
2994             this.helper.LoadInteger(this.helper.StaticData.DeclareXmlType(typBase));
2995             this.helper.Call(typDerived.IsSingleton ? XmlILMethods.ItemMatchesType : XmlILMethods.SeqMatchesType);
2996             ZeroCompare(QilNodeType.Ne, true);
2997
2998             return ndIsType;
2999         }
3000
3001         /// <summary>
3002         /// Faster code can be generated if type test is just a node kind test.  If this special case is detected, then generate code and return true.
3003         /// Otherwise, return false, and a call to MatchesXmlType will be generated instead.
3004         /// </summary>
3005         private bool MatchesNodeKinds(QilTargetType ndIsType, XmlQueryType typDerived, XmlQueryType typBase) {
3006             XmlNodeKindFlags kinds;
3007             bool allowKinds = true;
3008             XPathNodeType kindsRuntime;
3009             int kindsUnion;
3010
3011             // If not checking whether typDerived is some kind of singleton node, then fallback to MatchesXmlType
3012             if (!typBase.IsNode || !typBase.IsSingleton)
3013                 return false;
3014
3015             // If typDerived is not statically guaranteed to be a singleton node (and not an rtf), then fallback to MatchesXmlType
3016             if (!typDerived.IsNode || !typDerived.IsSingleton || !typDerived.IsNotRtf)
3017                 return false;
3018
3019             // Now we are guaranteed that typDerived is a node, and typBase is a node, so check node kinds
3020             // Ensure that typBase is only composed of kind-test prime types (no name-test, no schema-test, etc.)
3021             kinds = XmlNodeKindFlags.None;
3022             foreach (XmlQueryType typItem in typBase) {
3023                 if ((object) typItem == (object) TypeFactory.Element) kinds |= XmlNodeKindFlags.Element;
3024                 else if ((object) typItem == (object) TypeFactory.Attribute) kinds |= XmlNodeKindFlags.Attribute;
3025                 else if ((object) typItem == (object) TypeFactory.Text) kinds |= XmlNodeKindFlags.Text;
3026                 else if ((object) typItem == (object) TypeFactory.Document) kinds |= XmlNodeKindFlags.Document;
3027                 else if ((object) typItem == (object) TypeFactory.Comment) kinds |= XmlNodeKindFlags.Comment;
3028                 else if ((object) typItem == (object) TypeFactory.PI) kinds |= XmlNodeKindFlags.PI;
3029                 else if ((object) typItem == (object) TypeFactory.Namespace) kinds |= XmlNodeKindFlags.Namespace;
3030                 else return false;
3031             }
3032
3033             Debug.Assert((typDerived.NodeKinds & kinds) != XmlNodeKindFlags.None, "Normalizer should have taken care of case where node kinds are disjoint.");
3034
3035             kinds = typDerived.NodeKinds & kinds;
3036
3037             // Attempt to allow or disallow exactly one kind
3038             if (!Bits.ExactlyOne((uint) kinds)) {
3039                 // Not possible to allow one kind, so try to disallow one kind
3040                 kinds = ~kinds & XmlNodeKindFlags.Any;
3041                 allowKinds = !allowKinds;
3042             }
3043
3044             switch (kinds) {
3045                 case XmlNodeKindFlags.Element: kindsRuntime = XPathNodeType.Element; break;
3046                 case XmlNodeKindFlags.Attribute: kindsRuntime = XPathNodeType.Attribute; break;
3047                 case XmlNodeKindFlags.Namespace: kindsRuntime = XPathNodeType.Namespace; break;
3048                 case XmlNodeKindFlags.PI: kindsRuntime = XPathNodeType.ProcessingInstruction; break;
3049                 case XmlNodeKindFlags.Comment: kindsRuntime = XPathNodeType.Comment; break;
3050                 case XmlNodeKindFlags.Document: kindsRuntime = XPathNodeType.Root; break;
3051
3052                 default:
3053                     // Union of several types (when testing for Text, we need to test for Whitespace as well)
3054
3055                     // if (((1 << navigator.NodeType) & nodesDisallow) op 0) goto LabelBranch;
3056                     this.helper.Emit(OpCodes.Ldc_I4_1);
3057                     kindsRuntime = XPathNodeType.All;
3058                     break;
3059             }
3060
3061             // Push navigator.NodeType onto the stack
3062             NestedVisitEnsureStack(ndIsType.Source);
3063             this.helper.Call(XmlILMethods.NavType);
3064
3065             if (kindsRuntime == XPathNodeType.All) {
3066                 // if (((1 << navigator.NodeType) & kindsUnion) op 0) goto LabelBranch;
3067                 this.helper.Emit(OpCodes.Shl);
3068
3069                 kindsUnion = 0;
3070                 if ((kinds & XmlNodeKindFlags.Document) != 0) kindsUnion |= (1 << (int) XPathNodeType.Root);
3071                 if ((kinds & XmlNodeKindFlags.Element) != 0) kindsUnion |= (1 << (int) XPathNodeType.Element);
3072                 if ((kinds & XmlNodeKindFlags.Attribute) != 0) kindsUnion |= (1 << (int) XPathNodeType.Attribute);
3073                 if ((kinds & XmlNodeKindFlags.Text) != 0) kindsUnion |= (1 << (int) (int) XPathNodeType.Text) |
3074                                                                       (1 << (int) (int) XPathNodeType.SignificantWhitespace) |
3075                                                                       (1 << (int) (int) XPathNodeType.Whitespace);
3076                 if ((kinds & XmlNodeKindFlags.Comment) != 0) kindsUnion |= (1 << (int) XPathNodeType.Comment);
3077                 if ((kinds & XmlNodeKindFlags.PI) != 0) kindsUnion |= (1 << (int) XPathNodeType.ProcessingInstruction);
3078                 if ((kinds & XmlNodeKindFlags.Namespace) != 0) kindsUnion |= (1 << (int) XPathNodeType.Namespace);
3079
3080                 this.helper.LoadInteger(kindsUnion);
3081                 this.helper.Emit(OpCodes.And);
3082                 ZeroCompare(allowKinds ? QilNodeType.Ne : QilNodeType.Eq, false);
3083             }
3084             else {
3085                 // if (navigator.NodeType op runtimeItem) goto LabelBranch;
3086                 this.helper.LoadInteger((int) kindsRuntime);
3087                 ClrCompare(allowKinds ? QilNodeType.Eq : QilNodeType.Ne, XmlTypeCode.Int);
3088             }
3089
3090             return true;
3091         }
3092
3093         /// <summary>
3094         /// Generate code for QilNodeType.IsEmpty.
3095         /// </summary>
3096         /// <remarks>
3097         /// BranchingContext.OnFalse context: is-empty(expr)
3098         /// ==> foreach (item in expr)
3099         ///         goto LabelBranch;
3100         ///
3101         /// BranchingContext.OnTrue context: is-empty(expr)
3102         /// ==> foreach (item in expr)
3103         ///         break;
3104         ///     ...
3105         ///     LabelOnEnd: (called if foreach is empty)
3106         ///     goto LabelBranch;
3107         ///
3108         /// BranchingContext.None context: is-empty(expr)
3109         /// ==> foreach (item in expr)
3110         ///         break;
3111         ///     push true();
3112         ///     ...
3113         ///     LabelOnEnd: (called if foreach is empty)
3114         ///     push false();
3115         /// </remarks>
3116         protected override QilNode VisitIsEmpty(QilUnary ndIsEmpty) {
3117             Label lblTrue;
3118
3119             // If the child expression returns a cached result,
3120             if (CachesResult(ndIsEmpty.Child)) {
3121                 // Then get the count directly from the cache
3122                 NestedVisitEnsureStack(ndIsEmpty.Child);
3123                 this.helper.CallCacheCount(this.iterNested.Storage.ItemStorageType);
3124
3125                 switch (this.iterCurr.CurrentBranchingContext) {
3126                     case BranchingContext.OnFalse:
3127                         // Take false path if count != 0
3128                         this.helper.TestAndBranch(0, this.iterCurr.LabelBranch, OpCodes.Bne_Un);
3129                         break;
3130
3131                     case BranchingContext.OnTrue:
3132                         // Take true path if count == 0
3133                         this.helper.TestAndBranch(0, this.iterCurr.LabelBranch, OpCodes.Beq);
3134                         break;
3135
3136                     default:
3137                         Debug.Assert(this.iterCurr.CurrentBranchingContext == BranchingContext.None);
3138
3139                         // if (count == 0) goto LabelTrue;
3140                         lblTrue = this.helper.DefineLabel();
3141                         this.helper.Emit(OpCodes.Brfalse_S, lblTrue);
3142
3143                         // Convert branch targets into push of true/false
3144                         this.helper.ConvBranchToBool(lblTrue, true);
3145                         break;
3146                 }
3147             }
3148             else {
3149                 Label lblOnEnd = this.helper.DefineLabel();
3150                 IteratorDescriptor iterParent = this.iterCurr;
3151
3152                 // Forward any LabelOnEnd jumps to LabelBranch if BranchingContext.OnTrue
3153                 if (iterParent.CurrentBranchingContext == BranchingContext.OnTrue)
3154                     StartNestedIterator(ndIsEmpty.Child, this.iterCurr.LabelBranch);
3155                 else
3156                     StartNestedIterator(ndIsEmpty.Child, lblOnEnd);
3157
3158                 Visit(ndIsEmpty.Child);
3159
3160                 // Pop value of IsEmpty expression from the stack if necessary
3161                 this.iterCurr.EnsureNoCache();
3162                 this.iterCurr.DiscardStack();
3163
3164                 switch (iterParent.CurrentBranchingContext) {
3165                     case BranchingContext.OnFalse:
3166                         // Reverse polarity of iterator
3167                         this.helper.EmitUnconditionalBranch(OpCodes.Br, iterParent.LabelBranch);
3168                         this.helper.MarkLabel(lblOnEnd);
3169                         break;
3170
3171                     case BranchingContext.OnTrue:
3172                         // Nothing to do
3173                         break;
3174
3175                     case BranchingContext.None:
3176                         // Convert branch targets into push of true/false
3177                         this.helper.ConvBranchToBool(lblOnEnd, true);
3178                         break;
3179                 }
3180
3181                 // End nested iterator
3182                 EndNestedIterator(ndIsEmpty.Child);
3183             }
3184
3185             if (this.iterCurr.IsBranching)
3186                 this.iterCurr.Storage = StorageDescriptor.None();
3187             else
3188                 this.iterCurr.Storage = StorageDescriptor.Stack(typeof(bool), false);
3189
3190             return ndIsEmpty;
3191         }
3192
3193         /// <summary>
3194         /// Generate code for QilNodeType.XPathNodeValue.
3195         /// </summary>
3196         protected override QilNode VisitXPathNodeValue(QilUnary ndVal) {
3197             Label lblOnEnd, lblDone;
3198             Debug.Assert(ndVal.Child.XmlType.IsNode, "XPathNodeValue node may only be applied to a sequence of Nodes.");
3199
3200             // If the expression is a singleton,
3201             if (ndVal.Child.XmlType.IsSingleton) {
3202                 // Then generate code to push expresion result onto the stack
3203                 NestedVisitEnsureStack(ndVal.Child, typeof(XPathNavigator), false);
3204
3205                 // navigator.Value;
3206                 this.helper.Call(XmlILMethods.Value);
3207             }
3208             else {
3209                 lblOnEnd = this.helper.DefineLabel();
3210
3211                 // Construct nested iterator and iterate over results
3212                 StartNestedIterator(ndVal.Child, lblOnEnd);
3213                 Visit(ndVal.Child);
3214                 this.iterCurr.EnsureStackNoCache();
3215
3216                 // navigator.Value;
3217                 this.helper.Call(XmlILMethods.Value);
3218
3219                 // Handle empty sequence by pushing empty string onto the stack
3220                 lblDone = this.helper.DefineLabel();
3221                 this.helper.EmitUnconditionalBranch(OpCodes.Br, lblDone);
3222                 this.helper.MarkLabel(lblOnEnd);
3223                 this.helper.Emit(OpCodes.Ldstr, "");
3224                 this.helper.MarkLabel(lblDone);
3225
3226                 // End nested iterator
3227                 EndNestedIterator(ndVal.Child);
3228             }
3229
3230             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(string), false);
3231
3232             return ndVal;
3233         }
3234
3235         /// <summary>
3236         /// Find physical query plan for QilNodeType.XPathFollowing.
3237         /// </summary>
3238         protected override QilNode VisitXPathFollowing(QilUnary ndFoll) {
3239             CreateFilteredIterator(ndFoll.Child, "$$$iterFoll", typeof(XPathFollowingIterator), XmlILMethods.XPFollCreate, XmlILMethods.XPFollNext,
3240                                    XmlNodeKindFlags.Any, null, TriState.Unknown, null);
3241             return ndFoll;
3242         }
3243
3244         /// <summary>
3245         /// Find physical query plan for QilNodeType.XPathPreceding.
3246         /// </summary>
3247         protected override QilNode VisitXPathPreceding(QilUnary ndPrec) {
3248             CreateFilteredIterator(ndPrec.Child, "$$$iterPrec", typeof(XPathPrecedingIterator), XmlILMethods.XPPrecCreate, XmlILMethods.XPPrecNext,
3249                                    XmlNodeKindFlags.Any, null, TriState.Unknown, null);
3250             return ndPrec;
3251         }
3252
3253         /// <summary>
3254         /// Find physical query plan for QilNodeType.XPathNamespace.
3255         /// </summary>
3256         protected override QilNode VisitXPathNamespace(QilUnary ndNmsp) {
3257             CreateSimpleIterator(ndNmsp.Child, "$$$iterNmsp", typeof(NamespaceIterator), XmlILMethods.NmspCreate, XmlILMethods.NmspNext);
3258             return ndNmsp;
3259         }
3260
3261         /// <summary>
3262         /// Generate code for QilNodeType.XsltGenerateId.
3263         /// </summary>
3264         protected override QilNode VisitXsltGenerateId(QilUnary ndGenId) {
3265             Label lblOnEnd, lblDone;
3266
3267             this.helper.LoadQueryRuntime();
3268
3269             // If the expression is a singleton,
3270             if (ndGenId.Child.XmlType.IsSingleton) {
3271                 // Then generate code to push expresion result onto the stack
3272                 NestedVisitEnsureStack(ndGenId.Child, typeof(XPathNavigator), false);
3273
3274                 // runtime.GenerateId(value);
3275                 this.helper.Call(XmlILMethods.GenId);
3276             }
3277             else {
3278                 lblOnEnd = this.helper.DefineLabel();
3279
3280                 // Construct nested iterator and iterate over results
3281                 StartNestedIterator(ndGenId.Child, lblOnEnd);
3282                 Visit(ndGenId.Child);
3283                 this.iterCurr.EnsureStackNoCache();
3284                 this.iterCurr.EnsureItemStorageType(ndGenId.Child.XmlType, typeof(XPathNavigator));
3285
3286                 // runtime.GenerateId(value);
3287                 this.helper.Call(XmlILMethods.GenId);
3288
3289                 // Handle empty sequence by pushing empty string onto the stack
3290                 lblDone = this.helper.DefineLabel();
3291                 this.helper.EmitUnconditionalBranch(OpCodes.Br, lblDone);
3292                 this.helper.MarkLabel(lblOnEnd);
3293                 this.helper.Emit(OpCodes.Pop);
3294                 this.helper.Emit(OpCodes.Ldstr, "");
3295                 this.helper.MarkLabel(lblDone);
3296
3297                 // End nested iterator
3298                 EndNestedIterator(ndGenId.Child);
3299             }
3300
3301             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(string), false);
3302
3303             return ndGenId;
3304         }
3305
3306         /// <summary>
3307         /// Generate code for for QilNodeType.XsltInvokeLateBound.
3308         /// </summary>
3309         protected override QilNode VisitXsltInvokeLateBound(QilInvokeLateBound ndInvoke) {
3310             LocalBuilder locArgs = this.helper.DeclareLocal("$$$args", typeof(IList<XPathItem>[]));
3311             QilName ndName = (QilName) ndInvoke.Name;
3312             Debug.Assert(XmlILConstructInfo.Read(ndInvoke).ConstructMethod != XmlILConstructMethod.Writer);
3313
3314             // runtime.ExternalContext.InvokeXsltLateBoundFunction(name, ns, args);
3315             this.helper.LoadQueryContext();
3316             this.helper.Emit(OpCodes.Ldstr, ndName.LocalName);
3317             this.helper.Emit(OpCodes.Ldstr, ndName.NamespaceUri);
3318
3319             // args = new IList<XPathItem>[argCount];
3320             this.helper.LoadInteger(ndInvoke.Arguments.Count);
3321             this.helper.Emit(OpCodes.Newarr, typeof(IList<XPathItem>));
3322             this.helper.Emit(OpCodes.Stloc, locArgs);
3323
3324             for (int iArg = 0; iArg < ndInvoke.Arguments.Count; iArg++) {
3325                 QilNode ndArg = ndInvoke.Arguments[iArg];
3326
3327                 // args[0] = arg0;
3328                 // ...
3329                 // args[N] = argN;
3330                 this.helper.Emit(OpCodes.Ldloc, locArgs);
3331                 this.helper.LoadInteger(iArg);
3332                 this.helper.Emit(OpCodes.Ldelema, typeof(IList<XPathItem>));
3333
3334                 NestedVisitEnsureCache(ndArg, typeof(XPathItem));
3335                 this.iterCurr.EnsureStack();
3336
3337                 this.helper.Emit(OpCodes.Stobj, typeof(IList<XPathItem>));
3338             }
3339
3340             this.helper.Emit(OpCodes.Ldloc, locArgs);
3341
3342             this.helper.Call(XmlILMethods.InvokeXsltLate);
3343
3344             // Returned item sequence is on the stack
3345             this.iterCurr.Storage = StorageDescriptor.Stack(typeof(XPathItem), true);
3346
3347             return ndInvoke;
3348         }
3349
3350         /// <summary>
3351         /// Generate code for for QilNodeType.XsltInvokeEarlyBound.
3352         /// </summary>
3353         protected override QilNode VisitXsltInvokeEarlyBound(QilInvokeEarlyBound ndInvoke) {
3354             QilName ndName = ndInvoke.Name;
3355             XmlExtensionFunction extFunc;
3356             Type clrTypeRetSrc, clrTypeRetDst;
3357
3358             // Retrieve metadata from the extension function
3359             extFunc = new XmlExtensionFunction(ndName.LocalName, ndName.NamespaceUri, ndInvoke.ClrMethod);
3360             clrTypeRetSrc = extFunc.ClrReturnType;
3361             clrTypeRetDst = GetStorageType(ndInvoke);
3362
3363             // Prepare to call runtime.ChangeTypeXsltResult
3364             if (clrTypeRetSrc != clrTypeRetDst && !ndInvoke.XmlType.IsEmpty) {
3365                 this.helper.LoadQueryRuntime();
3366                 this.helper.LoadInteger(this.helper.StaticData.DeclareXmlType(ndInvoke.XmlType));
3367             }
3368
3369             // If this is not a static method, then get the instance object
3370             if (!extFunc.Method.IsStatic) {
3371                 // Special-case the XsltLibrary object
3372                 if (ndName.NamespaceUri.Length == 0)
3373                     this.helper.LoadXsltLibrary();
3374                 else
3375                     this.helper.CallGetEarlyBoundObject(this.helper.StaticData.DeclareEarlyBound(ndName.NamespaceUri, extFunc.Method.DeclaringType), extFunc.Method.DeclaringType);
3376             }
3377
3378             // Generate code to push each Invoke argument onto the stack
3379             for (int iArg = 0; iArg < ndInvoke.Arguments.Count; iArg++) {
3380                 QilNode ndActualArg;
3381                 XmlQueryType xmlTypeFormalArg;
3382                 Type clrTypeActualArg, clrTypeFormalArg;
3383
3384                 ndActualArg = ndInvoke.Arguments[iArg];
3385
3386                 // Infer Xml type and Clr type of formal argument
3387                 xmlTypeFormalArg = extFunc.GetXmlArgumentType(iArg);
3388                 clrTypeFormalArg = extFunc.GetClrArgumentType(iArg);
3389
3390                 Debug.Assert(ndActualArg.XmlType.IsSubtypeOf(xmlTypeFormalArg), "Xml type of actual arg must be a subtype of the Xml type of the formal arg");
3391
3392                 // Use different conversion rules for internal Xslt libraries.  If the actual argument is
3393                 // stored using Clr type T, then library must use type T, XPathItem, IList<T>, or IList<XPathItem>.
3394                 // If the actual argument is stored using Clr type IList<T>, then library must use type
3395                 // IList<T> or IList<XPathItem>.  This is to ensure that there will not be unnecessary
3396                 // conversions that take place when calling into an internal library.
3397                 if (ndName.NamespaceUri.Length == 0) {
3398                     Type itemType = GetItemStorageType(ndActualArg);
3399
3400                     if (clrTypeFormalArg == XmlILMethods.StorageMethods[itemType].IListType) {
3401                         // Formal type is IList<T>
3402                         NestedVisitEnsureStack(ndActualArg, itemType, true);
3403                     }
3404                     else if (clrTypeFormalArg == XmlILMethods.StorageMethods[typeof(XPathItem)].IListType) {
3405                         // Formal type is IList<XPathItem>
3406                         NestedVisitEnsureStack(ndActualArg, typeof(XPathItem), true);
3407                     }
3408                     else if ((ndActualArg.XmlType.IsSingleton && clrTypeFormalArg == itemType) || ndActualArg.XmlType.TypeCode == XmlTypeCode.None) {
3409                         // Formal type is T
3410                         NestedVisitEnsureStack(ndActualArg, clrTypeFormalArg, false);
3411                     }
3412                     else if (ndActualArg.XmlType.IsSingleton && clrTypeFormalArg == typeof(XPathItem)) {
3413                         // Formal type is XPathItem
3414                         NestedVisitEnsureStack(ndActualArg, typeof(XPathItem), false);
3415                     }
3416                     else
3417                         Debug.Fail("Internal Xslt library may not use parameters of type " + clrTypeFormalArg);
3418                 }
3419                 else {
3420                     // There is an implicit upcast to the Xml type of the formal argument.  This can change the Clr storage type.
3421                     clrTypeActualArg = GetStorageType(xmlTypeFormalArg);
3422
3423                     // If the formal Clr type is typeof(object) or if it is not a supertype of the actual Clr type, then call ChangeTypeXsltArgument
3424                     if (xmlTypeFormalArg.TypeCode == XmlTypeCode.Item || !clrTypeFormalArg.IsAssignableFrom(clrTypeActualArg)) {
3425                         // (clrTypeFormalArg) runtime.ChangeTypeXsltArgument(xmlTypeFormalArg, (object) value, clrTypeFormalArg);
3426                         this.helper.LoadQueryRuntime();
3427                         this.helper.LoadInteger(this.helper.StaticData.DeclareXmlType(xmlTypeFormalArg));
3428                         NestedVisitEnsureStack(ndActualArg, GetItemStorageType(xmlTypeFormalArg), !xmlTypeFormalArg.IsSingleton);
3429                         this.helper.TreatAs(clrTypeActualArg, typeof(object));
3430                         this.helper.LoadType(clrTypeFormalArg);
3431                         this.helper.Call(XmlILMethods.ChangeTypeXsltArg);
3432                         this.helper.TreatAs(typeof(object), clrTypeFormalArg);
3433                     }
3434                     else {
3435                         NestedVisitEnsureStack(ndActualArg, GetItemStorageType(xmlTypeFormalArg), !xmlTypeFormalArg.IsSingleton);
3436                     }
3437                 }
3438             }
3439
3440             // Invoke the target method
3441             this.helper.Call(extFunc.Method);
3442
3443             // Return value is on the stack; convert it to canonical ILGen storage type
3444             if (ndInvoke.XmlType.IsEmpty) {
3445                 this.helper.Emit(OpCodes.Ldsfld, XmlILMethods.StorageMethods[typeof(XPathItem)].SeqEmpty);
3446             }
3447             else if (clrTypeRetSrc != clrTypeRetDst) {
3448                 // (T) runtime.ChangeTypeXsltResult(idxType, (object) value);
3449                 this.helper.TreatAs(clrTypeRetSrc, typeof(object));
3450                 this.helper.Call(XmlILMethods.ChangeTypeXsltResult);
3451                 this.helper.TreatAs(typeof(object), clrTypeRetDst);
3452             }
3453             else if (ndName.NamespaceUri.Length != 0 && !clrTypeRetSrc.IsValueType){
3454                 // Check for null if a user-defined extension function returns a reference type
3455                 Label lblSkip = this.helper.DefineLabel();
3456                 this.helper.Emit(OpCodes.Dup);
3457                 this.helper.Emit(OpCodes.Brtrue, lblSkip);
3458                 this.helper.LoadQueryRuntime();
3459                 this.helper.Emit(OpCodes.Ldstr, Res.GetString(Res.Xslt_ItemNull));
3460                 this.helper.Call(XmlILMethods.ThrowException);
3461                 this.helper.MarkLabel(lblSkip);
3462             }
3463
3464             this.iterCurr.Storage = StorageDescriptor.Stack(GetItemStorageType(ndInvoke), !ndInvoke.XmlType.IsSingleton);
3465
3466             return ndInvoke;
3467         }
3468
3469         /// <summary>
3470         /// Generate code for QilNodeType.XsltCopy.
3471         /// </summary>
3472         protected override QilNode VisitXsltCopy(QilBinary ndCopy) {
3473             Label lblSkipContent = this.helper.DefineLabel();
3474             Debug.Assert(XmlILConstructInfo.Read(ndCopy).PushToWriterFirst);
3475
3476             // if (!xwrtChk.StartCopyChk(navCopy)) goto LabelSkipContent;
3477             this.helper.LoadQueryOutput();
3478
3479             NestedVisitEnsureStack(ndCopy.Left);
3480             Debug.Assert(ndCopy.Left.XmlType.IsNode);
3481
3482             this.helper.Call(XmlILMethods.StartCopy);
3483             this.helper.Emit(OpCodes.Brfalse, lblSkipContent);
3484
3485             // Recursively construct content
3486             NestedVisit(ndCopy.Right);
3487
3488             // xwrtChk.EndCopyChk(navCopy);
3489             this.helper.LoadQueryOutput();
3490
3491             NestedVisitEnsureStack(ndCopy.Left);
3492             Debug.Assert(ndCopy.Left.XmlType.IsNode);
3493
3494             this.helper.Call(XmlILMethods.EndCopy);
3495
3496             // LabelSkipContent:
3497             this.helper.MarkLabel(lblSkipContent);
3498
3499             this.iterCurr.Storage = StorageDescriptor.None();
3500             return ndCopy;
3501         }
3502
3503         /// <summary>
3504         /// Generate code for QilNodeType.XsltCopyOf.
3505         /// </summary>
3506         protected override QilNode VisitXsltCopyOf(QilUnary ndCopyOf) {
3507             Debug.Assert(XmlILConstructInfo.Read(ndCopyOf).PushToWriterFirst, "XsltCopyOf should always be pushed to writer.");
3508
3509             this.helper.LoadQueryOutput();
3510
3511             // XmlQueryOutput.XsltCopyOf(navigator);
3512             NestedVisitEnsureStack(ndCopyOf.Child);
3513             this.helper.Call(XmlILMethods.CopyOf);
3514
3515             this.iterCurr.Storage = StorageDescriptor.None();
3516             return ndCopyOf;
3517         }
3518
3519         /// <summary>
3520         /// Generate code for QilNodeType.XsltConvert.
3521         /// </summary>
3522         protected override QilNode VisitXsltConvert(QilTargetType ndConv) {
3523             XmlQueryType typSrc, typDst;
3524             MethodInfo meth;
3525
3526             typSrc = ndConv.Source.XmlType;
3527             typDst = ndConv.TargetType;
3528
3529             if (GetXsltConvertMethod(typSrc, typDst, out meth)) {
3530                 NestedVisitEnsureStack(ndConv.Source);
3531             }
3532             else {
3533                 // If a conversion could not be found, then convert the source expression to item or item* and try again
3534                 NestedVisitEnsureStack(ndConv.Source, typeof(XPathItem), !typSrc.IsSingleton);
3535                 if (!GetXsltConvertMethod(typSrc.IsSingleton ? TypeFactory.Item : TypeFactory.ItemS, typDst, out meth))
3536                     Debug.Fail("Conversion from " + ndConv.Source.XmlType + " to " + ndConv.TargetType + " is not supported.");
3537             }
3538
3539             // XsltConvert.XXXToYYY(value);
3540             if (meth != null)
3541                 this.helper.Call(meth);
3542
3543             this.iterCurr.Storage = StorageDescriptor.Stack(GetItemStorageType(typDst), !typDst.IsSingleton);
3544             return ndConv;
3545         }
3546
3547         /// <summary>
3548         /// Get the XsltConvert method that converts from "typSrc" to "typDst".  Return false if no
3549         /// such method exists.  This conversion matrix should match the one in XsltConvert.ExternalValueToExternalValue.
3550         /// </summary>
3551         private bool GetXsltConvertMethod(XmlQueryType typSrc, XmlQueryType typDst, out MethodInfo meth) {
3552             meth = null;
3553
3554             // Note, Ref.Equals is OK to use here, since we will always fall back to Item or Item* in the
3555             // case where the source or destination types do not match the static types exposed on the
3556             // XmlQueryTypeFactory.  This is bad for perf if it accidentally occurs, but the results
3557             // should still be correct.
3558
3559             // => xs:boolean
3560             if ((object) typDst == (object) TypeFactory.BooleanX) {
3561                 if ((object) typSrc == (object) TypeFactory.Item)               meth = XmlILMethods.ItemToBool;
3562                 else if ((object) typSrc == (object) TypeFactory.ItemS)         meth = XmlILMethods.ItemsToBool;
3563             }
3564             // => xs:dateTime
3565             else if ((object) typDst == (object) TypeFactory.DateTimeX) {
3566                 if ((object) typSrc == (object) TypeFactory.StringX)            meth = XmlILMethods.StrToDT;
3567             }
3568             // => xs:decimal
3569             else if ((object) typDst == (object) TypeFactory.DecimalX) {
3570                 if ((object) typSrc == (object) TypeFactory.DoubleX)            meth = XmlILMethods.DblToDec;
3571             }
3572             // => xs:double
3573             else if ((object) typDst == (object) TypeFactory.DoubleX) {
3574                 if ((object) typSrc == (object) TypeFactory.DecimalX)           meth = XmlILMethods.DecToDbl;
3575                 else if ((object) typSrc == (object) TypeFactory.IntX)          meth = XmlILMethods.IntToDbl;
3576                 else if ((object) typSrc == (object) TypeFactory.Item)          meth = XmlILMethods.ItemToDbl;
3577                 else if ((object) typSrc == (object) TypeFactory.ItemS)         meth = XmlILMethods.ItemsToDbl;
3578                 else if ((object) typSrc == (object) TypeFactory.LongX)         meth = XmlILMethods.LngToDbl;
3579                 else if ((object) typSrc == (object) TypeFactory.StringX)       meth = XmlILMethods.StrToDbl;
3580             }
3581             // => xs:int
3582             else if ((object) typDst == (object) TypeFactory.IntX) {
3583                 if ((object) typSrc == (object) TypeFactory.DoubleX)            meth = XmlILMethods.DblToInt;
3584             }
3585             // => xs:long
3586             else if ((object) typDst == (object) TypeFactory.LongX) {
3587                 if ((object) typSrc == (object) TypeFactory.DoubleX)            meth = XmlILMethods.DblToLng;
3588             }
3589             // => node
3590             else if ((object) typDst == (object) TypeFactory.NodeNotRtf) {
3591                 if ((object) typSrc == (object) TypeFactory.Item)               meth = XmlILMethods.ItemToNode;
3592                 else if ((object) typSrc == (object) TypeFactory.ItemS)         meth = XmlILMethods.ItemsToNode;
3593             }
3594             // => node*
3595             else if ((object) typDst == (object) TypeFactory.NodeSDod ||
3596                      (object) typDst == (object) TypeFactory.NodeNotRtfS) {
3597                 if ((object) typSrc == (object) TypeFactory.Item)               meth = XmlILMethods.ItemToNodes;
3598                 else if ((object) typSrc == (object) TypeFactory.ItemS)         meth = XmlILMethods.ItemsToNodes;
3599             }
3600             // => xs:string
3601             else if ((object) typDst == (object) TypeFactory.StringX) {
3602                 if ((object) typSrc == (object) TypeFactory.DateTimeX)          meth = XmlILMethods.DTToStr;
3603                 else if ((object) typSrc == (object) TypeFactory.DoubleX)       meth = XmlILMethods.DblToStr;
3604                 else if ((object) typSrc == (object) TypeFactory.Item)          meth = XmlILMethods.ItemToStr;
3605                 else if ((object) typSrc == (object) TypeFactory.ItemS)         meth = XmlILMethods.ItemsToStr;
3606             }
3607
3608             return meth != null;
3609         }
3610
3611
3612         //-----------------------------------------------
3613         // Helper methods
3614         //-----------------------------------------------
3615
3616         /// <summary>
3617         /// Ensure that the "locNav" navigator is positioned to the context node "ndCtxt".
3618         /// </summary>
3619         private void SyncToNavigator(LocalBuilder locNav, QilNode ndCtxt) {
3620             this.helper.Emit(OpCodes.Ldloc, locNav);
3621             NestedVisitEnsureStack(ndCtxt);
3622             this.helper.CallSyncToNavigator();
3623             this.helper.Emit(OpCodes.Stloc, locNav);
3624         }
3625
3626         /// <summary>
3627         /// Generate boiler-plate code to create a simple Xml iterator.
3628         /// </summary>
3629         /// <remarks>
3630         ///     Iterator iter;
3631         ///     iter.Create(navCtxt);
3632         /// LabelNext:
3633         ///     if (!iter.MoveNext())
3634         ///         goto LabelNextCtxt;
3635         /// </remarks>
3636         private void CreateSimpleIterator(QilNode ndCtxt, string iterName, Type iterType, MethodInfo methCreate, MethodInfo methNext) {
3637             // Iterator iter;
3638             LocalBuilder locIter = this.helper.DeclareLocal(iterName, iterType);
3639
3640             // iter.Create(navCtxt);
3641             this.helper.Emit(OpCodes.Ldloca, locIter);
3642             NestedVisitEnsureStack(ndCtxt);
3643             this.helper.Call(methCreate);
3644
3645             GenerateSimpleIterator(typeof(XPathNavigator), locIter, methNext);
3646         }
3647
3648         /// <summary>
3649         /// Generate boiler-plate code to create an Xml iterator that uses an XmlNavigatorFilter to filter items.
3650         /// </summary>
3651         /// <remarks>
3652         ///     Iterator iter;
3653         ///     iter.Create(navCtxt, filter [, orSelf] [, navEnd]);
3654         /// LabelNext:
3655         ///     if (!iter.MoveNext())
3656         ///         goto LabelNextCtxt;
3657         /// </remarks>
3658         private void CreateFilteredIterator(QilNode ndCtxt, string iterName, Type iterType, MethodInfo methCreate, MethodInfo methNext,
3659                                                 XmlNodeKindFlags kinds, QilName ndName, TriState orSelf, QilNode ndEnd) {
3660             // Iterator iter;
3661             LocalBuilder locIter = this.helper.DeclareLocal(iterName, iterType);
3662
3663             // iter.Create(navCtxt, filter [, orSelf], [, navEnd]);
3664             this.helper.Emit(OpCodes.Ldloca, locIter);
3665             NestedVisitEnsureStack(ndCtxt);
3666             LoadSelectFilter(kinds, ndName);
3667             if (orSelf != TriState.Unknown)
3668                 this.helper.LoadBoolean(orSelf == TriState.True);
3669             if (ndEnd != null)
3670                 NestedVisitEnsureStack(ndEnd);
3671             this.helper.Call(methCreate);
3672
3673             GenerateSimpleIterator(typeof(XPathNavigator), locIter, methNext);
3674         }
3675
3676         /// <summary>
3677         /// Generate boiler-plate code to create an Xml iterator that controls a nested iterator.
3678         /// </summary>
3679         /// <remarks>
3680         ///     Iterator iter;
3681         ///     iter.Create(filter [, orSelf]);
3682         ///         ...nested iterator...
3683         ///     navInput = nestedNested;
3684         ///     goto LabelCall;
3685         /// LabelNext:
3686         ///     navInput = null;
3687         /// LabelCall:
3688         ///     switch (iter.MoveNext(navInput)) {
3689         ///         case IteratorState.NoMoreNodes: goto LabelNextCtxt;
3690         ///         case IteratorState.NextInputNode: goto LabelNextNested;
3691         ///     }
3692         /// </remarks>
3693         private void CreateContainerIterator(QilUnary ndDod, string iterName, Type iterType, MethodInfo methCreate, MethodInfo methNext,
3694                                                    XmlNodeKindFlags kinds, QilName ndName, TriState orSelf) {
3695             // Iterator iter;
3696             LocalBuilder locIter = this.helper.DeclareLocal(iterName, iterType);
3697             Label lblOnEndNested;
3698             QilLoop ndLoop = (QilLoop) ndDod.Child;
3699             Debug.Assert(ndDod.NodeType == QilNodeType.DocOrderDistinct && ndLoop != null);
3700
3701             // iter.Create(filter [, orSelf]);
3702             this.helper.Emit(OpCodes.Ldloca, locIter);
3703             LoadSelectFilter(kinds, ndName);
3704             if (orSelf != TriState.Unknown)
3705                 this.helper.LoadBoolean(orSelf == TriState.True);
3706             this.helper.Call(methCreate);
3707
3708             // Generate nested iterator (branch to lblOnEndNested when iteration is complete)
3709             lblOnEndNested = this.helper.DefineLabel();
3710             StartNestedIterator(ndLoop, lblOnEndNested);
3711             StartBinding(ndLoop.Variable);
3712             EndBinding(ndLoop.Variable);
3713             EndNestedIterator(ndLoop.Variable);
3714             this.iterCurr.Storage = this.iterNested.Storage;
3715
3716             GenerateContainerIterator(ndDod, locIter, lblOnEndNested, methNext, typeof(XPathNavigator));
3717         }
3718
3719         /// <summary>
3720         /// Generate boiler-plate code that calls MoveNext on a simple Xml iterator.  Iterator should have already been
3721         /// created by calling code.
3722         /// </summary>
3723         /// <remarks>
3724         ///     ...
3725         /// LabelNext:
3726         ///     if (!iter.MoveNext())
3727         ///         goto LabelNextCtxt;
3728         /// </remarks>
3729         private void GenerateSimpleIterator(Type itemStorageType, LocalBuilder locIter, MethodInfo methNext) {
3730             Label lblNext;
3731
3732             // LabelNext:
3733             lblNext = this.helper.DefineLabel();
3734             this.helper.MarkLabel(lblNext);
3735
3736             // if (!iter.MoveNext()) goto LabelNextCtxt;
3737             this.helper.Emit(OpCodes.Ldloca, locIter);
3738             this.helper.Call(methNext);
3739             this.helper.Emit(OpCodes.Brfalse, this.iterCurr.GetLabelNext());
3740
3741             this.iterCurr.SetIterator(lblNext, StorageDescriptor.Current(locIter, itemStorageType));
3742         }
3743
3744         /// <summary>
3745         /// Generate boiler-plate code that calls MoveNext on an Xml iterator that controls a nested iterator.  Iterator should
3746         /// have already been created by calling code.
3747         /// </summary>
3748         /// <remarks>
3749         ///     ...
3750         ///     goto LabelCall;
3751         /// LabelNext:
3752         ///     navCtxt = null;
3753         /// LabelCall:
3754         ///     switch (iter.MoveNext(navCtxt)) {
3755         ///         case IteratorState.NoMoreNodes: goto LabelNextCtxt;
3756         ///         case IteratorState.NextInputNode: goto LabelNextNested;
3757         ///     }
3758         /// </remarks>
3759         private void GenerateContainerIterator(QilNode nd, LocalBuilder locIter, Label lblOnEndNested,
3760                                                        MethodInfo methNext, Type itemStorageType) {
3761             Label lblCall;
3762
3763             // Define labels that will be used
3764             lblCall = this.helper.DefineLabel();
3765
3766             // iter.MoveNext(input);
3767             // goto LabelCall;
3768             this.iterCurr.EnsureNoStackNoCache(nd.XmlType.IsNode ? "$$$navInput" : "$$$itemInput");
3769             this.helper.Emit(OpCodes.Ldloca, locIter);
3770             this.iterCurr.PushValue();
3771             this.helper.EmitUnconditionalBranch(OpCodes.Br, lblCall);
3772
3773             // LabelNext:
3774             // iterSet.MoveNext(null);
3775             this.helper.MarkLabel(lblOnEndNested);
3776             this.helper.Emit(OpCodes.Ldloca, locIter);
3777             this.helper.Emit(OpCodes.Ldnull);
3778
3779             // LabelCall:
3780             // result = iter.MoveNext(input);
3781             this.helper.MarkLabel(lblCall);
3782             this.helper.Call(methNext);
3783
3784             // If this iterator always returns a single node, then NoMoreNodes will never be returned
3785             if (nd.XmlType.IsSingleton) {
3786                 // if (result == IteratorResult.NeedInputNode) goto LabelNextInput;
3787                 this.helper.LoadInteger((int) IteratorResult.NeedInputNode);
3788                 this.helper.Emit(OpCodes.Beq, this.iterNested.GetLabelNext());
3789
3790                 this.iterCurr.Storage = StorageDescriptor.Current(locIter, itemStorageType);
3791             }
3792             else {
3793                 // switch (iter.MoveNext(input)) {
3794                 //      case IteratorResult.NoMoreNodes: goto LabelNextCtxt;
3795                 //      case IteratorResult.NeedInputNode: goto LabelNextInput;
3796                 // }
3797                 this.helper.Emit(OpCodes.Switch, new Label[] {this.iterCurr.GetLabelNext(), this.iterNested.GetLabelNext()});
3798
3799                 this.iterCurr.SetIterator(lblOnEndNested, StorageDescriptor.Current(locIter, itemStorageType));
3800             }
3801         }
3802
3803         /// <summary>
3804         /// Load XmlQueryOutput, load a name (computed or literal) and load an index to an Xml schema type.
3805         /// Return an enumeration that specifies what kind of name was loaded.
3806         /// </summary>
3807         private GenerateNameType LoadNameAndType(XPathNodeType nodeType, QilNode ndName, bool isStart, bool callChk) {
3808             QilName ndLiteralName;
3809             string prefix, localName, ns;
3810             GenerateNameType nameType;
3811             Debug.Assert(ndName.XmlType.TypeCode == XmlTypeCode.QName, "Element or attribute name must have QName type.");
3812
3813             this.helper.LoadQueryOutput();
3814
3815             // 0. Default is to pop names off stack
3816             nameType = GenerateNameType.StackName;
3817
3818             // 1. Literal names
3819             if (ndName.NodeType == QilNodeType.LiteralQName) {
3820                 // If checks need to be made on End construction, then always pop names from stack
3821                 if (isStart || !callChk) {
3822                     ndLiteralName = ndName as QilName;
3823                     prefix = ndLiteralName.Prefix;
3824                     localName = ndLiteralName.LocalName;
3825                     ns = ndLiteralName.NamespaceUri;
3826
3827                     // Check local name, namespace parts in debug code
3828                     Debug.Assert(ValidateNames.ValidateName(prefix, localName, ns, nodeType, ValidateNames.Flags.AllExceptPrefixMapping));
3829
3830                     // If the namespace is empty,
3831                     if (ndLiteralName.NamespaceUri.Length == 0) {
3832                         // Then always call method on XmlQueryOutput
3833                         this.helper.Emit(OpCodes.Ldstr, ndLiteralName.LocalName);
3834                         return GenerateNameType.LiteralLocalName;
3835                     }
3836
3837                     // If prefix is not valid for the node type,
3838                     if (!ValidateNames.ValidateName(prefix, localName, ns, nodeType, ValidateNames.Flags.CheckPrefixMapping)) {
3839                         // Then construct a new prefix at run-time
3840                         if (isStart) {
3841                             this.helper.Emit(OpCodes.Ldstr, localName);
3842                             this.helper.Emit(OpCodes.Ldstr, ns);
3843                             this.helper.Construct(XmlILConstructors.QName);
3844
3845                             nameType = GenerateNameType.QName;
3846                         }
3847                     }
3848                     else {
3849                         // Push string parts
3850                         this.helper.Emit(OpCodes.Ldstr, prefix);
3851                         this.helper.Emit(OpCodes.Ldstr, localName);
3852                         this.helper.Emit(OpCodes.Ldstr, ns);
3853
3854                         nameType = GenerateNameType.LiteralName;
3855                     }
3856                 }
3857             }
3858             else {
3859                 if (isStart) {
3860                     // 2. Copied names
3861                     if (ndName.NodeType == QilNodeType.NameOf) {
3862                         // Preserve prefix of source node, so just push navigator onto stack
3863                         NestedVisitEnsureStack((ndName as QilUnary).Child);
3864                         nameType = GenerateNameType.CopiedName;
3865                     }
3866                     // 3. Parsed tag names (foo:bar)
3867                     else if (ndName.NodeType == QilNodeType.StrParseQName) {
3868                         // Preserve prefix from parsed tag name
3869                         VisitStrParseQName(ndName as QilBinary, true);
3870
3871                         // Type of name depends upon data-type of name argument
3872                         if ((ndName as QilBinary).Right.XmlType.TypeCode == XmlTypeCode.String)
3873                             nameType = GenerateNameType.TagNameAndNamespace;
3874                         else
3875                             nameType = GenerateNameType.TagNameAndMappings;
3876                     }
3877                     // 4. Other computed qnames
3878                     else {
3879                         // Push XmlQualifiedName onto the stack
3880                         NestedVisitEnsureStack(ndName);
3881                         nameType = GenerateNameType.QName;
3882                     }
3883                 }
3884             }
3885
3886             return nameType;
3887         }
3888
3889         /// <summary>
3890         /// If the first argument is a constant value that evaluates to zero, then a more optimal instruction sequence
3891         /// can be generated that does not have to push the zero onto the stack.  Instead, a Brfalse or Brtrue instruction
3892         /// can be used.
3893         /// </summary>
3894         private bool TryZeroCompare(QilNodeType relOp, QilNode ndFirst, QilNode ndSecond) {
3895             Debug.Assert(relOp == QilNodeType.Eq || relOp == QilNodeType.Ne);
3896
3897             switch (ndFirst.NodeType) {
3898                 case QilNodeType.LiteralInt64:
3899                     if ((int) (QilLiteral) ndFirst != 0) return false;
3900                     break;
3901
3902                 case QilNodeType.LiteralInt32:
3903                     if ((int) (QilLiteral) ndFirst != 0) return false;
3904                     break;
3905
3906                 case QilNodeType.False:
3907                     break;
3908
3909                 case QilNodeType.True:
3910                     // Inverse of QilNodeType.False
3911                     relOp = (relOp == QilNodeType.Eq) ? QilNodeType.Ne : QilNodeType.Eq;
3912                     break;
3913
3914                 default:
3915                     return false;
3916             }
3917
3918             // Generate code to push second argument on stack
3919             NestedVisitEnsureStack(ndSecond);
3920
3921             // Generate comparison code -- op == 0 or op != 0
3922             ZeroCompare(relOp, ndSecond.XmlType.TypeCode == XmlTypeCode.Boolean);
3923
3924             return true;
3925         }
3926
3927         /// <summary>
3928         /// If the comparison involves a qname, then perform comparison using atoms and return true.
3929         /// Otherwise, return false (caller will perform comparison).
3930         /// </summary>
3931         private bool TryNameCompare(QilNodeType relOp, QilNode ndFirst, QilNode ndSecond) {
3932             Debug.Assert(relOp == QilNodeType.Eq || relOp == QilNodeType.Ne);
3933
3934             if (ndFirst.NodeType == QilNodeType.NameOf) {
3935                 switch (ndSecond.NodeType) {
3936                     case QilNodeType.NameOf:
3937                     case QilNodeType.LiteralQName: {
3938                         this.helper.LoadQueryRuntime();
3939
3940                         // Push left navigator onto the stack
3941                         NestedVisitEnsureStack((ndFirst as QilUnary).Child);
3942
3943                         // Push the local name and namespace uri of the right argument onto the stack
3944                         if (ndSecond.NodeType == QilNodeType.LiteralQName) {
3945                             QilName ndName = ndSecond as QilName;
3946                             this.helper.LoadInteger(this.helper.StaticData.DeclareName(ndName.LocalName));
3947                             this.helper.LoadInteger(this.helper.StaticData.DeclareName(ndName.NamespaceUri));
3948
3949                             // push runtime.IsQNameEqual(navigator, localName, namespaceUri)
3950                             this.helper.Call(XmlILMethods.QNameEqualLit);
3951                         }
3952                         else {
3953                             // Generate code to locate the navigator argument of NameOf operator
3954                             Debug.Assert(ndSecond.NodeType == QilNodeType.NameOf);
3955                             NestedVisitEnsureStack(ndSecond);
3956
3957                             // push runtime.IsQNameEqual(nav1, nav2)
3958                             this.helper.Call(XmlILMethods.QNameEqualNav);
3959                         }
3960
3961                         // Branch based on boolean result or push boolean value
3962                         ZeroCompare((relOp == QilNodeType.Eq) ? QilNodeType.Ne : QilNodeType.Eq, true);
3963                         return true;
3964                     }
3965                 }
3966             }
3967
3968             // Caller must perform comparison
3969             return false;
3970         }
3971
3972         /// <summary>
3973         /// For QilExpression types that map directly to CLR primitive types, the built-in CLR comparison operators can
3974         /// be used to perform the specified relational operation.
3975         /// </summary>
3976         private void ClrCompare(QilNodeType relOp, XmlTypeCode code) {
3977             OpCode opcode;
3978             Label lblTrue;
3979
3980             switch (this.iterCurr.CurrentBranchingContext) {
3981                 case BranchingContext.OnFalse:
3982                     // Reverse the comparison operator
3983                     // Use Bxx_Un OpCodes to handle NaN case for double and single types
3984                     if (code == XmlTypeCode.Double || code == XmlTypeCode.Float) {
3985                         switch (relOp) {
3986                             case QilNodeType.Gt: opcode = OpCodes.Ble_Un; break;
3987                             case QilNodeType.Ge: opcode = OpCodes.Blt_Un; break;
3988                             case QilNodeType.Lt: opcode = OpCodes.Bge_Un; break;
3989                             case QilNodeType.Le: opcode = OpCodes.Bgt_Un; break;
3990                             case QilNodeType.Eq: opcode = OpCodes.Bne_Un; break;
3991                             case QilNodeType.Ne: opcode = OpCodes.Beq; break;
3992                             default: Debug.Assert(false); opcode = OpCodes.Nop; break;
3993                         }
3994                     }
3995                     else {
3996                         switch (relOp)
3997                         {
3998                             case QilNodeType.Gt: opcode = OpCodes.Ble; break;
3999                             case QilNodeType.Ge: opcode = OpCodes.Blt; break;
4000                             case QilNodeType.Lt: opcode = OpCodes.Bge; break;
4001                             case QilNodeType.Le: opcode = OpCodes.Bgt; break;
4002                             case QilNodeType.Eq: opcode = OpCodes.Bne_Un; break;
4003                             case QilNodeType.Ne: opcode = OpCodes.Beq; break;
4004                             default: Debug.Assert(false); opcode = OpCodes.Nop; break;
4005                         }
4006                     }
4007                     this.helper.Emit(opcode, this.iterCurr.LabelBranch);
4008                     this.iterCurr.Storage = StorageDescriptor.None();
4009                     break;
4010
4011                 case BranchingContext.OnTrue:
4012                     switch (relOp) {
4013                         case QilNodeType.Gt: opcode = OpCodes.Bgt; break;
4014                         case QilNodeType.Ge: opcode = OpCodes.Bge; break;
4015                         case QilNodeType.Lt: opcode = OpCodes.Blt; break;
4016                         case QilNodeType.Le: opcode = OpCodes.Ble; break;
4017                         case QilNodeType.Eq: opcode = OpCodes.Beq; break;
4018                         case QilNodeType.Ne: opcode = OpCodes.Bne_Un; break;
4019                         default: Debug.Assert(false); opcode = OpCodes.Nop; break;
4020                     }
4021                     this.helper.Emit(opcode, this.iterCurr.LabelBranch);
4022                     this.iterCurr.Storage = StorageDescriptor.None();
4023                     break;
4024
4025                 default:
4026                     Debug.Assert(this.iterCurr.CurrentBranchingContext == BranchingContext.None);
4027                     switch (relOp) {
4028                         case QilNodeType.Gt: this.helper.Emit(OpCodes.Cgt); break;
4029                         case QilNodeType.Lt: this.helper.Emit(OpCodes.Clt); break;
4030                         case QilNodeType.Eq: this.helper.Emit(OpCodes.Ceq); break;
4031                         default:
4032                             switch (relOp) {
4033                                 case QilNodeType.Ge: opcode = OpCodes.Bge_S; break;
4034                                 case QilNodeType.Le: opcode = OpCodes.Ble_S; break;
4035                                 case QilNodeType.Ne: opcode = OpCodes.Bne_Un_S; break;
4036                                 default: Debug.Assert(false); opcode = OpCodes.Nop; break;
4037                             }
4038
4039                             // Push "true" if comparison succeeds, "false" otherwise
4040                             lblTrue = this.helper.DefineLabel();
4041                             this.helper.Emit(opcode, lblTrue);
4042                             this.helper.ConvBranchToBool(lblTrue, true);
4043                             break;
4044                     }
4045                     this.iterCurr.Storage = StorageDescriptor.Stack(typeof(bool), false);
4046                     break;
4047             }
4048         }
4049
4050         /// <summary>
4051         /// Generate code to compare the top stack value to 0 by using the Brfalse or Brtrue instructions,
4052         /// which avoid pushing zero onto the stack.  Both of these instructions test for null/zero/false.
4053         /// </summary>
4054         private void ZeroCompare(QilNodeType relOp, bool isBoolVal) {
4055             Label lblTrue;
4056             Debug.Assert(relOp == QilNodeType.Eq || relOp == QilNodeType.Ne);
4057
4058             // Test to determine if top stack value is zero (if relOp is Eq) or is not zero (if relOp is Ne)
4059             switch (this.iterCurr.CurrentBranchingContext) {
4060                 case BranchingContext.OnTrue:
4061                     // If relOp is Eq, jump to true label if top value is zero (Brfalse)
4062                     // If relOp is Ne, jump to true label if top value is non-zero (Brtrue)
4063                     this.helper.Emit((relOp == QilNodeType.Eq) ? OpCodes.Brfalse : OpCodes.Brtrue, this.iterCurr.LabelBranch);
4064                     this.iterCurr.Storage = StorageDescriptor.None();
4065                     break;
4066
4067                 case BranchingContext.OnFalse:
4068                     // If relOp is Eq, jump to false label if top value is non-zero (Brtrue)
4069                     // If relOp is Ne, jump to false label if top value is zero (Brfalse)
4070                     this.helper.Emit((relOp == QilNodeType.Eq) ? OpCodes.Brtrue : OpCodes.Brfalse, this.iterCurr.LabelBranch);
4071                     this.iterCurr.Storage = StorageDescriptor.None();
4072                     break;
4073
4074                 default:
4075                     Debug.Assert(this.iterCurr.CurrentBranchingContext == BranchingContext.None);
4076
4077                     // Since (boolval != 0) = boolval, value on top of the stack is already correct
4078                     if (!isBoolVal || relOp == QilNodeType.Eq) {
4079                         // If relOp is Eq, push "true" if top value is zero, "false" otherwise
4080                         // If relOp is Ne, push "true" if top value is non-zero, "false" otherwise
4081                         lblTrue = this.helper.DefineLabel();
4082                         this.helper.Emit((relOp == QilNodeType.Eq) ? OpCodes.Brfalse : OpCodes.Brtrue, lblTrue);
4083                         this.helper.ConvBranchToBool(lblTrue, true);
4084                     }
4085
4086                     this.iterCurr.Storage = StorageDescriptor.Stack(typeof(bool), false);
4087                     break;
4088             }
4089         }
4090
4091         /// <summary>
4092         /// Construction within a loop is starting.  If transition from non-Any to Any state occurs, then ensure
4093         /// that runtime state will be set.
4094         /// </summary>
4095         private void StartWriterLoop(QilNode nd, out bool hasOnEnd, out Label lblOnEnd) {
4096             XmlILConstructInfo info = XmlILConstructInfo.Read(nd);
4097
4098             // By default, do not create a new iteration label
4099             hasOnEnd = false;
4100             lblOnEnd = new Label();
4101
4102             // If loop is not involved in Xml construction, or if loop returns exactly one value, then do nothing
4103             if (!info.PushToWriterLast || nd.XmlType.IsSingleton)
4104                 return;
4105
4106             if (!this.iterCurr.HasLabelNext) {
4107                 // Iterate until all items are constructed
4108                 hasOnEnd = true;
4109                 lblOnEnd = this.helper.DefineLabel();
4110                 this.iterCurr.SetIterator(lblOnEnd, StorageDescriptor.None());
4111             }
4112         }
4113
4114         /// <summary>
4115         /// Construction within a loop is ending.  If transition from non-Any to Any state occurs, then ensure that
4116         /// runtime state will be set.
4117         /// </summary>
4118         private void EndWriterLoop(QilNode nd, bool hasOnEnd, Label lblOnEnd) {
4119             XmlILConstructInfo info = XmlILConstructInfo.Read(nd);
4120
4121             // If loop is not involved in Xml construction, then do nothing
4122             if (!info.PushToWriterLast)
4123                 return;
4124
4125             // Since results of construction were pushed to writer, there are no values to return
4126             this.iterCurr.Storage = StorageDescriptor.None();
4127
4128             // If loop returns exactly one value, then do nothing further
4129             if (nd.XmlType.IsSingleton)
4130                 return;
4131
4132             if (hasOnEnd) {
4133                 // Loop over all items in the list, sending each to the output writer
4134                 this.iterCurr.LoopToEnd(lblOnEnd);
4135             }
4136         }
4137
4138         /// <summary>
4139         /// Returns true if the specified node's owner element might have local namespaces added to it
4140         /// after attributes have already been added.
4141         /// </summary>
4142         private bool MightHaveNamespacesAfterAttributes(XmlILConstructInfo info) {
4143             // Get parent element
4144             if (info != null)
4145                 info = info.ParentElementInfo;
4146
4147             // If a parent element has not been statically identified, then assume that the runtime
4148             // element will have namespaces added after attributes.
4149             if (info == null)
4150                 return true;
4151
4152             return info.MightHaveNamespacesAfterAttributes;
4153         }
4154
4155         /// <summary>
4156         /// Returns true if the specified element should cache attributes.
4157         /// </summary>
4158         private bool ElementCachesAttributes(XmlILConstructInfo info) {
4159             // Attributes will be cached if namespaces might be constructed after the attributes
4160             return info.MightHaveDuplicateAttributes || info.MightHaveNamespacesAfterAttributes;
4161         }
4162
4163         /// <summary>
4164         /// This method is called before calling any WriteEnd??? method.  It generates code to perform runtime
4165         /// construction checks separately.  This should only be called if the XmlQueryOutput::StartElementChk
4166         /// method will *not* be called.
4167         /// </summary>
4168         private void BeforeStartChecks(QilNode ndCtor) {
4169             switch (XmlILConstructInfo.Read(ndCtor).InitialStates) {
4170                 case PossibleXmlStates.WithinSequence:
4171                     // If runtime state is guaranteed to be WithinSequence, then call XmlQueryOutput.StartTree
4172                     this.helper.CallStartTree(QilConstructorToNodeType(ndCtor.NodeType));
4173                     break;
4174
4175                 case PossibleXmlStates.EnumAttrs:
4176                     switch (ndCtor.NodeType) {
4177                         case QilNodeType.ElementCtor:
4178                         case QilNodeType.TextCtor:
4179                         case QilNodeType.RawTextCtor:
4180                         case QilNodeType.PICtor:
4181                         case QilNodeType.CommentCtor:
4182                             // If runtime state is guaranteed to be EnumAttrs, and content is being constructed, call
4183                             // XmlQueryOutput.StartElementContent
4184                             this.helper.CallStartElementContent();
4185                             break;
4186                     }
4187                     break;
4188             }
4189         }
4190
4191         /// <summary>
4192         /// This method is called after calling any WriteEnd??? method.  It generates code to perform runtime
4193         /// construction checks separately.  This should only be called if the XmlQueryOutput::EndElementChk
4194         /// method will *not* be called.
4195         /// </summary>
4196         private void AfterEndChecks(QilNode ndCtor) {
4197             if (XmlILConstructInfo.Read(ndCtor).FinalStates == PossibleXmlStates.WithinSequence) {
4198                 // If final runtime state is guaranteed to be WithinSequence, then call XmlQueryOutput.StartTree
4199                 this.helper.CallEndTree();
4200             }
4201         }
4202
4203         /// <summary>
4204         /// Return true if a runtime check needs to be made in order to transition into the WithinContent state.
4205         /// </summary>
4206         private bool CheckWithinContent(XmlILConstructInfo info) {
4207             switch (info.InitialStates) {
4208                 case PossibleXmlStates.WithinSequence:
4209                 case PossibleXmlStates.EnumAttrs:
4210                 case PossibleXmlStates.WithinContent:
4211                     // Transition to WithinContent can be ensured at compile-time
4212                     return false;
4213             }
4214
4215             return true;
4216         }
4217
4218         /// <summary>
4219         /// Return true if a runtime check needs to be made in order to transition into the EnumAttrs state.
4220         /// </summary>
4221         private bool CheckEnumAttrs(XmlILConstructInfo info) {
4222             switch (info.InitialStates) {
4223                 case PossibleXmlStates.WithinSequence:
4224                 case PossibleXmlStates.EnumAttrs:
4225                     // Transition to EnumAttrs can be ensured at compile-time
4226                     return false;
4227             }
4228
4229             return true;
4230         }
4231
4232         /// <summary>
4233         /// Map the XmlNodeKindFlags enumeration into the XPathNodeType enumeration.
4234         /// </summary>
4235         private XPathNodeType QilXmlToXPathNodeType(XmlNodeKindFlags xmlTypes) {
4236             switch (xmlTypes) {
4237                 case XmlNodeKindFlags.Element: return XPathNodeType.Element;
4238                 case XmlNodeKindFlags.Attribute: return XPathNodeType.Attribute;
4239                 case XmlNodeKindFlags.Text: return XPathNodeType.Text;
4240                 case XmlNodeKindFlags.Comment: return XPathNodeType.Comment;
4241             }
4242             Debug.Assert(xmlTypes == XmlNodeKindFlags.PI);
4243             return XPathNodeType.ProcessingInstruction;
4244         }
4245
4246         /// <summary>
4247         /// Map a QilExpression constructor type into the XPathNodeType enumeration.
4248         /// </summary>
4249         private XPathNodeType QilConstructorToNodeType(QilNodeType typ) {
4250             switch (typ) {
4251                 case QilNodeType.DocumentCtor: return XPathNodeType.Root;
4252                 case QilNodeType.ElementCtor: return XPathNodeType.Element;
4253                 case QilNodeType.TextCtor: return XPathNodeType.Text;
4254                 case QilNodeType.RawTextCtor: return XPathNodeType.Text;
4255                 case QilNodeType.PICtor: return XPathNodeType.ProcessingInstruction;
4256                 case QilNodeType.CommentCtor: return XPathNodeType.Comment;
4257                 case QilNodeType.AttributeCtor: return XPathNodeType.Attribute;
4258                 case QilNodeType.NamespaceDecl: return XPathNodeType.Namespace;
4259             }
4260
4261             Debug.Assert(false, "Cannot map QilNodeType " + typ + " to an XPathNodeType");
4262             return XPathNodeType.All;
4263         }
4264
4265         /// <summary>
4266         /// Load an XmlNavigatorFilter that matches only the specified name and types onto the stack.
4267         /// </summary>
4268         private void LoadSelectFilter(XmlNodeKindFlags xmlTypes, QilName ndName) {
4269             if (ndName != null) {
4270                 // Push NameFilter
4271                 Debug.Assert(xmlTypes == XmlNodeKindFlags.Element);
4272                 this.helper.CallGetNameFilter(this.helper.StaticData.DeclareNameFilter(ndName.LocalName, ndName.NamespaceUri));
4273             }
4274             else {
4275                 // Either type cannot be a union, or else it must be >= union of all Content types
4276                 bool isXmlTypeUnion = IsNodeTypeUnion(xmlTypes);
4277                 Debug.Assert(!isXmlTypeUnion || (xmlTypes & XmlNodeKindFlags.Content) == XmlNodeKindFlags.Content);
4278
4279                 if (isXmlTypeUnion) {
4280                     if ((xmlTypes & XmlNodeKindFlags.Attribute) != 0) {
4281                         // Union includes attributes, so allow all node kinds
4282                         this.helper.CallGetTypeFilter(XPathNodeType.All);
4283                     }
4284                     else {
4285                         // Filter attributes
4286                         this.helper.CallGetTypeFilter(XPathNodeType.Attribute);
4287                     }
4288                 }
4289                 else {
4290                     // Filter nodes of all but one type
4291                     this.helper.CallGetTypeFilter(QilXmlToXPathNodeType(xmlTypes));
4292                 }
4293             }
4294         }
4295
4296         /// <summary>
4297         /// Return true if more than one node type is set.
4298         /// </summary>
4299         private static bool IsNodeTypeUnion(XmlNodeKindFlags xmlTypes) {
4300             return ((int) xmlTypes & ((int) xmlTypes - 1)) != 0;
4301         }
4302
4303         /// <summary>
4304         /// Start construction of a new nested iterator.  If this.iterCurr == null, then the new iterator
4305         /// is a top-level, or root iterator.  Otherwise, the new iterator will be nested within the
4306         /// current iterator.
4307         /// </summary>
4308         private void StartNestedIterator(QilNode nd) {
4309             IteratorDescriptor iterParent = this.iterCurr;
4310
4311             // Create a new, nested iterator
4312             if (iterParent == null) {
4313                 // Create a "root" iterator info that has no parernt
4314                 this.iterCurr = new IteratorDescriptor(this.helper);
4315             }
4316             else {
4317                 // Create a nested iterator
4318                 this.iterCurr = new IteratorDescriptor(iterParent);
4319             }
4320
4321             this.iterNested = null;
4322         }
4323
4324         /// <summary>
4325         /// Calls StartNestedIterator(nd) and also sets up the nested iterator to branch to "lblOnEnd" when iteration
4326         /// is complete.
4327         /// </summary>
4328         private void StartNestedIterator(QilNode nd, Label lblOnEnd) {
4329             StartNestedIterator(nd);
4330             this.iterCurr.SetIterator(lblOnEnd, StorageDescriptor.None());
4331         }
4332
4333         /// <summary>
4334         /// End construction of the current iterator.
4335         /// </summary>
4336         private void EndNestedIterator(QilNode nd) {
4337             Debug.Assert(this.iterCurr.Storage.Location == ItemLocation.None ||
4338                          this.iterCurr.Storage.ItemStorageType == GetItemStorageType(nd) ||
4339                          this.iterCurr.Storage.ItemStorageType == typeof(XPathItem) ||
4340                          nd.XmlType.TypeCode == XmlTypeCode.None,
4341                          "QilNodeType " + nd.NodeType + " cannot be stored using type " + this.iterCurr.Storage.ItemStorageType + ".");
4342
4343             // If the nested iterator was constructed in branching mode,
4344             if (this.iterCurr.IsBranching) {
4345                 // Then if branching hasn't already taken place, do so now
4346                 if (this.iterCurr.Storage.Location != ItemLocation.None) {
4347                     this.iterCurr.EnsureItemStorageType(nd.XmlType, typeof(bool));
4348                     this.iterCurr.EnsureStackNoCache();
4349
4350                     if (this.iterCurr.CurrentBranchingContext == BranchingContext.OnTrue)
4351                         this.helper.Emit(OpCodes.Brtrue, this.iterCurr.LabelBranch);
4352                     else
4353                         this.helper.Emit(OpCodes.Brfalse, this.iterCurr.LabelBranch);
4354
4355                     this.iterCurr.Storage = StorageDescriptor.None();
4356                 }
4357             }
4358
4359             // Save current iterator as nested iterator
4360             this.iterNested = this.iterCurr;
4361
4362             // Update current iterator to be parent iterator
4363             this.iterCurr = this.iterCurr.ParentIterator;
4364         }
4365
4366         /// <summary>
4367         /// Recursively generate code to iterate over the results of the "nd" expression.  If "nd" is pushed
4368         /// to the writer, then there are no results.  If "nd" is a singleton expression and isCached is false,
4369         /// then generate code to construct the singleton.  Otherwise, cache the sequence in an XmlQuerySequence
4370         /// object.  Ensure that all items are converted to the specified "itemStorageType".
4371         /// </summary>
4372         private void NestedVisit(QilNode nd, Type itemStorageType, bool isCached) {
4373             if (XmlILConstructInfo.Read(nd).PushToWriterLast) {
4374                 // Push results to output, so nothing is left to store
4375                 StartNestedIterator(nd);
4376                 Visit(nd);
4377                 EndNestedIterator(nd);
4378                 this.iterCurr.Storage = StorageDescriptor.None();
4379             }
4380             else if (!isCached && nd.XmlType.IsSingleton) {
4381                 // Storage of result will be a non-cached singleton
4382                 StartNestedIterator(nd);
4383                 Visit(nd);
4384                 this.iterCurr.EnsureNoCache();
4385                 this.iterCurr.EnsureItemStorageType(nd.XmlType, itemStorageType);
4386                 EndNestedIterator(nd);
4387                 this.iterCurr.Storage = this.iterNested.Storage;
4388             }
4389             else {
4390                 NestedVisitEnsureCache(nd, itemStorageType);
4391             }
4392         }
4393
4394         /// <summary>
4395         /// Calls NestedVisit(QilNode, Type, bool), storing result in the default storage type for "nd".
4396         /// </summary>
4397         private void NestedVisit(QilNode nd) {
4398             NestedVisit(nd, GetItemStorageType(nd), !nd.XmlType.IsSingleton);
4399         }
4400
4401         /// <summary>
4402         /// Recursively generate code to iterate over the results of the "nd" expression.  When the expression
4403         /// has been fully iterated, it will jump to "lblOnEnd".
4404         /// </summary>
4405         private void NestedVisit(QilNode nd, Label lblOnEnd) {
4406             Debug.Assert(!XmlILConstructInfo.Read(nd).PushToWriterLast);
4407             StartNestedIterator(nd, lblOnEnd);
4408             Visit(nd);
4409             this.iterCurr.EnsureNoCache();
4410             this.iterCurr.EnsureItemStorageType(nd.XmlType, GetItemStorageType(nd));
4411             EndNestedIterator(nd);
4412             this.iterCurr.Storage = this.iterNested.Storage;
4413         }
4414
4415         /// <summary>
4416         /// Call NestedVisit(QilNode) and ensure that result is pushed onto the IL stack.
4417         /// </summary>
4418         private void NestedVisitEnsureStack(QilNode nd) {
4419             Debug.Assert(!XmlILConstructInfo.Read(nd).PushToWriterLast);
4420             NestedVisit(nd);
4421             this.iterCurr.EnsureStack();
4422         }
4423
4424         /// <summary>
4425         /// Generate code for both QilExpression nodes and ensure that each result is pushed onto the IL stack.
4426         /// </summary>
4427         private void NestedVisitEnsureStack(QilNode ndLeft, QilNode ndRight) {
4428             NestedVisitEnsureStack(ndLeft);
4429             NestedVisitEnsureStack(ndRight);
4430         }
4431
4432         /// <summary>
4433         /// Call NestedVisit(QilNode, Type, bool) and ensure that result is pushed onto the IL stack.
4434         /// </summary>
4435         private void NestedVisitEnsureStack(QilNode nd, Type itemStorageType, bool isCached) {
4436             Debug.Assert(!XmlILConstructInfo.Read(nd).PushToWriterLast);
4437             NestedVisit(nd, itemStorageType, isCached);
4438             this.iterCurr.EnsureStack();
4439         }
4440
4441         /// <summary>
4442         /// Call NestedVisit(QilNode) and ensure that result is stored in local variable "loc".
4443         /// </summary>
4444         private void NestedVisitEnsureLocal(QilNode nd, LocalBuilder loc) {
4445             Debug.Assert(!XmlILConstructInfo.Read(nd).PushToWriterLast);
4446             NestedVisit(nd);
4447             this.iterCurr.EnsureLocal(loc);
4448         }
4449
4450         /// <summary>
4451         /// Start a nested iterator in a branching context and recursively generate code for the specified QilExpression node.
4452         /// </summary>
4453         private void NestedVisitWithBranch(QilNode nd, BranchingContext brctxt, Label lblBranch) {
4454             Debug.Assert(nd.XmlType.IsSingleton && !XmlILConstructInfo.Read(nd).PushToWriterLast);
4455             StartNestedIterator(nd);
4456             this.iterCurr.SetBranching(brctxt, lblBranch);
4457             Visit(nd);
4458             EndNestedIterator(nd);
4459             this.iterCurr.Storage = StorageDescriptor.None();
4460         }
4461
4462         /// <summary>
4463         /// Generate code for the QilExpression node and ensure that results are fully cached as an XmlQuerySequence.  All results
4464         /// should be converted to "itemStorageType" before being added to the cache.
4465         /// </summary>
4466         private void NestedVisitEnsureCache(QilNode nd, Type itemStorageType) {
4467             Debug.Assert(!XmlILConstructInfo.Read(nd).PushToWriterLast);
4468             bool cachesResult = CachesResult(nd);
4469             LocalBuilder locCache;
4470             Label lblOnEnd = this.helper.DefineLabel();
4471             Type cacheType;
4472             XmlILStorageMethods methods;
4473
4474             // If bound expression will already be cached correctly, then don't create an XmlQuerySequence
4475             if (cachesResult) {
4476                 StartNestedIterator(nd);
4477                 Visit(nd);
4478                 EndNestedIterator(nd);
4479                 this.iterCurr.Storage = this.iterNested.Storage;
4480                 Debug.Assert(this.iterCurr.Storage.IsCached, "Expression result should be cached.  CachesResult() might have a bug in it.");
4481
4482                 // If type of items in the cache matches "itemStorageType", then done
4483                 if (this.iterCurr.Storage.ItemStorageType == itemStorageType)
4484                     return;
4485
4486                 // If the cache has navigators in it, or if converting to a cache of navigators, then EnsureItemStorageType
4487                 // can directly convert without needing to create a new cache.
4488                 if (this.iterCurr.Storage.ItemStorageType == typeof(XPathNavigator) || itemStorageType == typeof(XPathNavigator)) {
4489                     this.iterCurr.EnsureItemStorageType(nd.XmlType, itemStorageType);
4490                     return;
4491                 }
4492
4493                 this.iterCurr.EnsureNoStack("$$$cacheResult");
4494             }
4495
4496             // Always store navigators in XmlQueryNodeSequence (which implements IList<XPathItem>)
4497             cacheType = (GetItemStorageType(nd) == typeof(XPathNavigator)) ? typeof(XPathNavigator) : itemStorageType;
4498
4499             // XmlQuerySequence<T> cache;
4500             methods = XmlILMethods.StorageMethods[cacheType];
4501             locCache = this.helper.DeclareLocal("$$$cache", methods.SeqType);
4502             this.helper.Emit(OpCodes.Ldloc, locCache);
4503
4504             // Special case non-navigator singletons to use overload of CreateOrReuse
4505             if (nd.XmlType.IsSingleton) {
4506                 // cache = XmlQuerySequence.CreateOrReuse(cache, item);
4507                 NestedVisitEnsureStack(nd, cacheType, false);
4508                 this.helper.CallToken(methods.SeqReuseSgl);
4509                 this.helper.Emit(OpCodes.Stloc, locCache);
4510             }
4511             else {
4512                 // XmlQuerySequence<T> cache;
4513                 // cache = XmlQuerySequence.CreateOrReuse(cache);
4514                 this.helper.CallToken(methods.SeqReuse);
4515                 this.helper.Emit(OpCodes.Stloc, locCache);
4516                 this.helper.Emit(OpCodes.Ldloc, locCache);
4517
4518                 StartNestedIterator(nd, lblOnEnd);
4519
4520                 if (cachesResult)
4521                     this.iterCurr.Storage = this.iterCurr.ParentIterator.Storage;
4522                 else
4523                     Visit(nd);
4524
4525                 // cache.Add(item);
4526                 this.iterCurr.EnsureItemStorageType(nd.XmlType, cacheType);
4527                 this.iterCurr.EnsureStackNoCache();
4528                 this.helper.Call(methods.SeqAdd);
4529                 this.helper.Emit(OpCodes.Ldloc, locCache);
4530
4531                 // }
4532                 this.iterCurr.LoopToEnd(lblOnEnd);
4533
4534                 EndNestedIterator(nd);
4535
4536                 // Remove cache reference from stack
4537                 this.helper.Emit(OpCodes.Pop);
4538             }
4539
4540             this.iterCurr.Storage = StorageDescriptor.Local(locCache, itemStorageType, true);
4541         }
4542
4543         /// <summary>
4544         /// Returns true if the specified QilExpression node type is *guaranteed* to cache its results in an XmlQuerySequence,
4545         /// where items in the cache are stored using the default storage type.
4546         /// </summary>
4547         private bool CachesResult(QilNode nd) {
4548             OptimizerPatterns patt;
4549
4550             switch (nd.NodeType) {
4551                 case QilNodeType.Let:
4552                 case QilNodeType.Parameter:
4553                 case QilNodeType.Invoke:
4554                 case QilNodeType.XsltInvokeLateBound:
4555                 case QilNodeType.XsltInvokeEarlyBound:
4556                     return !nd.XmlType.IsSingleton;
4557
4558                 case QilNodeType.Filter:
4559                     // EqualityIndex pattern caches results
4560                     patt = OptimizerPatterns.Read(nd);
4561                     return patt.MatchesPattern(OptimizerPatternName.EqualityIndex);
4562
4563                 case QilNodeType.DocOrderDistinct:
4564                     if (nd.XmlType.IsSingleton)
4565                         return false;
4566
4567                     // JoinAndDod and DodReverse patterns don't cache results
4568                     patt = OptimizerPatterns.Read(nd);
4569                     return !patt.MatchesPattern(OptimizerPatternName.JoinAndDod) && !patt.MatchesPattern(OptimizerPatternName.DodReverse);
4570
4571                 case QilNodeType.TypeAssert:
4572                     QilTargetType ndTypeAssert = (QilTargetType) nd;
4573                     // Check if TypeAssert would be no-op
4574                     return CachesResult(ndTypeAssert.Source) && GetItemStorageType(ndTypeAssert.Source) == GetItemStorageType(ndTypeAssert);
4575             }
4576
4577             return false;
4578         }
4579
4580         /// <summary>
4581         /// Shortcut call to XmlILTypeHelper.GetStorageType.
4582         /// </summary>
4583         private Type GetStorageType(QilNode nd) {
4584             return XmlILTypeHelper.GetStorageType(nd.XmlType);
4585         }
4586
4587         /// <summary>
4588         /// Shortcut call to XmlILTypeHelper.GetStorageType.
4589         /// </summary>
4590         private Type GetStorageType(XmlQueryType typ) {
4591             return XmlILTypeHelper.GetStorageType(typ);
4592         }
4593
4594         /// <summary>
4595         /// Shortcut call to XmlILTypeHelper.GetStorageType, using an expression's prime type.
4596         /// </summary>
4597         private Type GetItemStorageType(QilNode nd) {
4598             return XmlILTypeHelper.GetStorageType(nd.XmlType.Prime);
4599         }
4600
4601         /// <summary>
4602         /// Shortcut call to XmlILTypeHelper.GetStorageType, using the prime type.
4603         /// </summary>
4604         private Type GetItemStorageType(XmlQueryType typ) {
4605             return XmlILTypeHelper.GetStorageType(typ.Prime);
4606         }
4607     }
4608 }