mcs/class/referencesource/System.Data.SqlXml/System/Xml/Xsl/Runtime/TreeIterators.cs

   1 //------------------------------------------------------------------------------
   2 // <copyright file="TreeIterators.cs" company="Microsoft">
   3 //     Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 // <owner current="true" primary="true">Microsoft</owner>
   6 //------------------------------------------------------------------------------
   7
   8 using System.ComponentModel;
   9 using System.Diagnostics;
  10 using System.Xml.XPath;
  11
  12 namespace System.Xml.Xsl.Runtime {
  13
  14     /// <summary>
  15     /// Iterate over all descendant content nodes according to XPath descendant axis rules.
  16     /// </summary>
  17     [EditorBrowsable(EditorBrowsableState.Never)]
  18     public struct DescendantIterator {
  19         private XmlNavigatorFilter filter;
  20         private XPathNavigator navCurrent, navEnd;
  21         private bool hasFirst;
  22
  23         /// <summary>
  24         /// Initialize the DescendantIterator (no possibility of duplicates).
  25         /// </summary>
  26         public void Create(XPathNavigator input, XmlNavigatorFilter filter, bool orSelf) {
  27             // Save input node as current node
  28             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, input);
  29             this.filter = filter;
  30
  31             // Position navEnd to the node at which the descendant scan should terminate
  32             if (input.NodeType == XPathNodeType.Root) {
  33                 this.navEnd = null;
  34             }
  35             else {
  36                 this.navEnd = XmlQueryRuntime.SyncToNavigator(this.navEnd, input);
  37                 this.navEnd.MoveToNonDescendant();
  38             }
  39
  40             // If self node matches, then return it first
  41             this.hasFirst = (orSelf && !this.filter.IsFiltered(this.navCurrent));
  42         }
  43
  44         /// <summary>
  45         /// Position this iterator to the next descendant node.  Return false if there are no more descendant nodes.
  46         /// Return true if the Current property is set to the next node in the iteration.
  47         /// </summary>
  48         public bool MoveNext() {
  49             if (this.hasFirst) {
  50                 this.hasFirst = false;
  51                 return true;
  52             }
  53             return (this.filter.MoveToFollowing(this.navCurrent, this.navEnd));
  54         }
  55
  56         /// <summary>
  57         /// Return the current result navigator.  This is only defined after MoveNext() has returned true.
  58         /// </summary>
  59         public XPathNavigator Current {
  60             get { return this.navCurrent; }
  61         }
  62     }
  63
  64
  65     /// <summary>
  66     /// Iterate over all descendant content nodes according to XPath descendant axis rules.  Eliminate duplicates by not
  67     /// querying over nodes that are contained in the subtree of the previous node.
  68     /// </summary>
  69     [EditorBrowsable(EditorBrowsableState.Never)]
  70     public struct DescendantMergeIterator {
  71         private XmlNavigatorFilter filter;
  72         private XPathNavigator navCurrent, navRoot, navEnd;
  73         private IteratorState state;
  74         private bool orSelf;
  75
  76         private enum IteratorState {
  77             NoPrevious = 0,
  78             NeedCurrent,
  79             NeedDescendant,
  80         }
  81
  82         /// <summary>
  83         /// Initialize the DescendantIterator (merge multiple sets of descendant nodes in document order and remove duplicates).
  84         /// </summary>
  85         public void Create(XmlNavigatorFilter filter, bool orSelf) {
  86             this.filter = filter;
  87             this.state = IteratorState.NoPrevious;
  88             this.orSelf = orSelf;
  89         }
  90
  91         /// <summary>
  92         /// Position this iterator to the next descendant node.  Return IteratorResult.NoMoreNodes if there are no more
  93         /// descendant nodes.  Return IteratorResult.NeedInputNode if the next input node needs to be fetched.
  94         /// Return IteratorResult.HaveCurrent if the Current property is set to the next node in the iteration.
  95         /// </summary>
  96         public IteratorResult MoveNext(XPathNavigator input) {
  97             if (this.state != IteratorState.NeedDescendant) {
  98                 if (input == null)
  99                     return IteratorResult.NoMoreNodes;
 100
 101                 // Descendants of the input node will be duplicates if the input node is in the subtree
 102                 // of the previous root.
 103                 if (this.state != IteratorState.NoPrevious && this.navRoot.IsDescendant(input))
 104                     return IteratorResult.NeedInputNode;
 105
 106                 // Save input node as current node and end of input's tree in navEnd
 107                 this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, input);
 108                 this.navRoot = XmlQueryRuntime.SyncToNavigator(this.navRoot, input);
 109                 this.navEnd = XmlQueryRuntime.SyncToNavigator(this.navEnd, input);
 110                 this.navEnd.MoveToNonDescendant();
 111
 112                 this.state = IteratorState.NeedDescendant;
 113
 114                 // If self node matches, then return it
 115                 if (this.orSelf && !this.filter.IsFiltered(input))
 116                     return IteratorResult.HaveCurrentNode;
 117             }
 118
 119             if (this.filter.MoveToFollowing(this.navCurrent, this.navEnd))
 120                 return IteratorResult.HaveCurrentNode;
 121
 122             // No more descendants, so transition to NeedCurrent state and get the next input node
 123             this.state = IteratorState.NeedCurrent;
 124             return IteratorResult.NeedInputNode;
 125         }
 126
 127         /// <summary>
 128         /// Return the current result navigator.  This is only defined after MoveNext() has returned true or IteratorResult.HaveCurrentNode.
 129         /// </summary>
 130         public XPathNavigator Current {
 131             get { return this.navCurrent; }
 132         }
 133     }
 134
 135
 136     /// <summary>
 137     /// Iterate over matching parent node according to XPath parent axis rules.
 138     /// </summary>
 139     [EditorBrowsable(EditorBrowsableState.Never)]
 140     public struct ParentIterator {
 141         private XPathNavigator navCurrent;
 142         private bool haveCurrent;
 143
 144         /// <summary>
 145         /// Initialize the ParentIterator.
 146         /// </summary>
 147         public void Create(XPathNavigator context, XmlNavigatorFilter filter) {
 148             // Save context node as current node
 149             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, context);
 150
 151             // Attempt to find a matching parent node
 152             this.haveCurrent = (this.navCurrent.MoveToParent()) && (!filter.IsFiltered(this.navCurrent));
 153         }
 154
 155         /// <summary>
 156         /// Return true if a matching parent node exists and set Current property.  Otherwise, return false
 157         /// (Current property is undefined).
 158         /// </summary>
 159         public bool MoveNext() {
 160             if (this.haveCurrent) {
 161                 this.haveCurrent = false;
 162                 return true;
 163             }
 164
 165             // Iteration is complete
 166             return false;
 167         }
 168
 169         /// <summary>
 170         /// Return the current result navigator.  This is only defined after MoveNext() has returned true.
 171         /// </summary>
 172         public XPathNavigator Current {
 173             get { return this.navCurrent; }
 174         }
 175     }
 176
 177
 178     /// <summary>
 179     /// Iterate over all ancestor nodes according to XPath ancestor axis rules, returning nodes in reverse
 180     /// document order.
 181     /// </summary>
 182     [EditorBrowsable(EditorBrowsableState.Never)]
 183     public struct AncestorIterator {
 184         private XmlNavigatorFilter filter;
 185         private XPathNavigator navCurrent;
 186         private bool haveCurrent;
 187
 188         /// <summary>
 189         /// Initialize the AncestorIterator.
 190         /// </summary>
 191         public void Create(XPathNavigator context, XmlNavigatorFilter filter, bool orSelf) {
 192             this.filter = filter;
 193
 194             // Save context node as current node
 195             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, context);
 196
 197             // If self node matches, then next call to MoveNext() should return it
 198             // Otherwise, MoveNext() will fetch next ancestor
 199             this.haveCurrent = (orSelf && !this.filter.IsFiltered(this.navCurrent));
 200         }
 201
 202         /// <summary>
 203         /// Position the iterator on the next matching ancestor node.  Return true if such a node exists and
 204         /// set Current property.  Otherwise, return false (Current property is undefined).
 205         /// </summary>
 206         public bool MoveNext() {
 207             if (this.haveCurrent) {
 208                 this.haveCurrent = false;
 209                 return true;
 210             }
 211
 212             while (this.navCurrent.MoveToParent()) {
 213                 if (!this.filter.IsFiltered(this.navCurrent))
 214                     return true;
 215             }
 216
 217             // Iteration is complete
 218             return false;
 219         }
 220
 221         /// <summary>
 222         /// Return the current result navigator.  This is only defined after MoveNext() has returned true.
 223         /// </summary>
 224         public XPathNavigator Current {
 225             get { return this.navCurrent; }
 226         }
 227     }
 228
 229
 230     /// <summary>
 231     /// Iterate over all ancestor nodes according to XPath ancestor axis rules, but return the nodes in document order.
 232     /// </summary>
 233     [EditorBrowsable(EditorBrowsableState.Never)]
 234     public struct AncestorDocOrderIterator {
 235         private XmlNavigatorStack stack;
 236         private XPathNavigator navCurrent;
 237
 238         /// <summary>
 239         /// Initialize the AncestorDocOrderIterator (return ancestor nodes in document order, no possibility of duplicates).
 240         /// </summary>
 241         public void Create(XPathNavigator context, XmlNavigatorFilter filter, bool orSelf) {
 242             AncestorIterator wrapped = new AncestorIterator();
 243             wrapped.Create(context, filter, orSelf);
 244             this.stack.Reset();
 245
 246             // Fetch all ancestor nodes in reverse document order and push them onto the stack
 247             while (wrapped.MoveNext())
 248                 this.stack.Push(wrapped.Current.Clone());
 249         }
 250
 251         /// <summary>
 252         /// Return true if the Current property is set to the next Ancestor node in document order.
 253         /// </summary>
 254         public bool MoveNext() {
 255             if (this.stack.IsEmpty)
 256                 return false;
 257
 258             this.navCurrent = this.stack.Pop();
 259             return true;
 260         }
 261
 262         /// <summary>
 263         /// Return the current result navigator.  This is only defined after MoveNext() has returned true.
 264         /// </summary>
 265         public XPathNavigator Current {
 266             get { return this.navCurrent; }
 267         }
 268     }
 269
 270
 271     /// <summary>
 272     /// Iterate over all following nodes according to XPath following axis rules.  These rules specify that
 273     /// descendants are not included, even though they follow the starting node in document order.  For the
 274     /// "true" following axis, see FollowingIterator.
 275     /// </summary>
 276     [EditorBrowsable(EditorBrowsableState.Never)]
 277     public struct XPathFollowingIterator {
 278         private XmlNavigatorFilter filter;
 279         private XPathNavigator navCurrent;
 280         bool needFirst;
 281
 282         /// <summary>
 283         /// Initialize the XPathFollowingIterator (no possibility of duplicates).
 284         /// </summary>
 285         public void Create(XPathNavigator input, XmlNavigatorFilter filter) {
 286             // Save input node as current node
 287             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, input);
 288             this.filter = filter;
 289             this.needFirst = true;
 290         }
 291
 292         /// <summary>
 293         /// Position this iterator to the next following node.  Return false if there are no more following nodes.
 294         /// Return true if the Current property is set to the next node in the iteration.
 295         /// </summary>
 296         public bool MoveNext() {
 297             if (this.needFirst) {
 298                 if (!MoveFirst(this.filter, this.navCurrent))
 299                     return false;
 300
 301                 this.needFirst = false;
 302                 return true;
 303             }
 304
 305             return this.filter.MoveToFollowing(this.navCurrent, null);
 306         }
 307
 308         /// <summary>
 309         /// Return the current result navigator.  This is only defined after MoveNext() has returned true.
 310         /// </summary>
 311         public XPathNavigator Current {
 312             get { return this.navCurrent; }
 313         }
 314
 315         /// <summary>
 316         /// Position "nav" to the matching node which follows it in document order but is not a descendant node.
 317         /// Return false if this is no such matching node.
 318         /// </summary>
 319         internal static bool MoveFirst(XmlNavigatorFilter filter, XPathNavigator nav) {
 320             // Attributes and namespace nodes include descendants of their owner element in the set of following nodes
 321             if (nav.NodeType == XPathNodeType.Attribute || nav.NodeType == XPathNodeType.Namespace) {
 322                 if (!nav.MoveToParent()) {
 323                     // Floating attribute or namespace node that has no following nodes
 324                     return false;
 325                 }
 326
 327                 if (!filter.MoveToFollowing(nav, null)) {
 328                     // No matching following nodes
 329                     return false;
 330                 }
 331             }
 332             else {
 333                 // XPath spec doesn't include descendants of the input node in the following axis
 334                 if (!nav.MoveToNonDescendant())
 335                     // No following nodes
 336                     return false;
 337
 338                 // If the sibling does not match the node-test, find the next following node that does
 339                 if (filter.IsFiltered(nav)) {
 340                     if (!filter.MoveToFollowing(nav, null)) {
 341                         // No matching following nodes
 342                         return false;
 343                     }
 344                 }
 345             }
 346
 347             // Success
 348             return true;
 349         }
 350     }
 351
 352
 353     /// <summary>
 354     /// Iterate over all following nodes according to XPath following axis rules.  Merge multiple sets of following nodes
 355     /// in document order and remove duplicates.
 356     /// </summary>
 357     [EditorBrowsable(EditorBrowsableState.Never)]
 358     public struct XPathFollowingMergeIterator {
 359         private XmlNavigatorFilter filter;
 360         private IteratorState state;
 361         private XPathNavigator navCurrent, navNext;
 362
 363         private enum IteratorState {
 364             NeedCandidateCurrent = 0,
 365             HaveCandidateCurrent,
 366             HaveCurrentNeedNext,
 367             HaveCurrentHaveNext,
 368             HaveCurrentNoNext,
 369         };
 370
 371         /// <summary>
 372         /// Initialize the XPathFollowingMergeIterator (merge multiple sets of following nodes in document order and remove duplicates).
 373         /// </summary>
 374         public void Create(XmlNavigatorFilter filter) {
 375             this.filter = filter;
 376             this.state = IteratorState.NeedCandidateCurrent;
 377         }
 378
 379         /// <summary>
 380         /// Position this iterator to the next following node.  Prune by finding the first input node in
 381         /// document order that has no other input nodes in its subtree.  All other input nodes should be
 382         /// discarded.  Return IteratorResult.NeedInputNode if the next input node needs to be fetched
 383         /// first.  Return IteratorResult.HaveCurrent if the Current property is set to the next node in the
 384         /// iteration.
 385         /// </summary>
 386         public IteratorResult MoveNext(XPathNavigator input) {
 387             switch (this.state) {
 388                 case IteratorState.NeedCandidateCurrent:
 389                     // If there are no more input nodes, then iteration is complete
 390                     if (input == null)
 391                         return IteratorResult.NoMoreNodes;
 392
 393                     // Save input node as current node
 394                     this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, input);
 395
 396                     // Still must check next input node to see if is a descendant of this one
 397                     this.state = IteratorState.HaveCandidateCurrent;
 398                     return IteratorResult.NeedInputNode;
 399
 400                 case IteratorState.HaveCandidateCurrent:
 401                     // If there are no more input nodes,
 402                     if (input == null) {
 403                         // Then candidate node has been selected, and there are no further input nodes
 404                         this.state = IteratorState.HaveCurrentNoNext;
 405                         return MoveFirst();
 406                     }
 407
 408                     // If input node is in the subtree of the candidate node, then use the input node instead
 409                     if (this.navCurrent.IsDescendant(input))
 410                         goto case IteratorState.NeedCandidateCurrent;
 411
 412                     // Found node on which to perform following scan.  Now skip past all input nodes in the same document.
 413                     this.state = IteratorState.HaveCurrentNeedNext;
 414                     goto case IteratorState.HaveCurrentNeedNext;
 415
 416                 case IteratorState.HaveCurrentNeedNext:
 417                     // If there are no more input nodes,
 418                     if (input == null) {
 419                         // Then candidate node has been selected, and there are no further input nodes
 420                         this.state = IteratorState.HaveCurrentNoNext;
 421                         return MoveFirst();
 422                     }
 423
 424                     // Skip input node unless it's in a different document than the node on which the following scan was performed
 425                     if (this.navCurrent.ComparePosition(input) != XmlNodeOrder.Unknown)
 426                         return IteratorResult.NeedInputNode;
 427
 428                     // Next node is in a different document, so save it
 429                     this.navNext = XmlQueryRuntime.SyncToNavigator(this.navNext, input);
 430                     this.state = IteratorState.HaveCurrentHaveNext;
 431                     return MoveFirst();
 432             }
 433
 434             if (!this.filter.MoveToFollowing(this.navCurrent, null))
 435                 return MoveFailed();
 436
 437             return IteratorResult.HaveCurrentNode;
 438         }
 439
 440         /// <summary>
 441         /// Return the current result navigator.  This is only defined after MoveNext() has returned true or IteratorResult.HaveCurrentNode.
 442         /// </summary>
 443         public XPathNavigator Current {
 444             get { return this.navCurrent; }
 445         }
 446
 447         /// <summary>
 448         /// Called when an attempt to move to a following node failed.  If a Next node exists, then make that the new
 449         /// candidate current node.  Otherwise, iteration is complete.
 450         /// </summary>
 451         private IteratorResult MoveFailed() {
 452             XPathNavigator navTemp;
 453             Debug.Assert(this.state == IteratorState.HaveCurrentHaveNext || this.state == IteratorState.HaveCurrentNoNext);
 454
 455             if (this.state == IteratorState.HaveCurrentNoNext) {
 456                 // No more nodes, so iteration is complete
 457                 this.state = IteratorState.NeedCandidateCurrent;
 458                 return IteratorResult.NoMoreNodes;
 459             }
 460
 461             // Make next node the new candidate node
 462             this.state = IteratorState.HaveCandidateCurrent;
 463
 464             // Swap navigators in order to sometimes avoid creating clones
 465             navTemp = this.navCurrent;
 466             this.navCurrent = this.navNext;
 467             this.navNext = navTemp;
 468
 469             return IteratorResult.NeedInputNode;
 470         }
 471
 472         /// <summary>
 473         /// Position this.navCurrent to the node which follows it in document order but is not a descendant node.
 474         /// </summary>
 475         private IteratorResult MoveFirst() {
 476             Debug.Assert(this.state == IteratorState.HaveCurrentHaveNext || this.state == IteratorState.HaveCurrentNoNext);
 477
 478             if (!XPathFollowingIterator.MoveFirst(this.filter, this.navCurrent))
 479                 return MoveFailed();
 480
 481             return IteratorResult.HaveCurrentNode;
 482         }
 483     }
 484
 485
 486     /// <summary>
 487     /// Iterate over all content-typed nodes which precede the starting node in document order.  Return nodes
 488     /// in reverse document order.
 489     /// </summary>
 490     [EditorBrowsable(EditorBrowsableState.Never)]
 491     public struct PrecedingIterator {
 492         private XmlNavigatorStack stack;
 493         private XPathNavigator navCurrent;
 494
 495         /// <summary>
 496         /// Initialize the PrecedingIterator (no possibility of duplicates).
 497         /// </summary>
 498         public void Create(XPathNavigator context, XmlNavigatorFilter filter) {
 499             // Start at root, which is always first node in the document
 500             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, context);
 501             this.navCurrent.MoveToRoot();
 502             this.stack.Reset();
 503
 504             // If root node is not the ending node,
 505             if (!this.navCurrent.IsSamePosition(context)) {
 506                 // Push root onto the stack if it is not filtered
 507                 if (!filter.IsFiltered(this.navCurrent))
 508                     this.stack.Push(this.navCurrent.Clone());
 509
 510                 // Push all matching nodes onto stack
 511                 while (filter.MoveToFollowing(this.navCurrent, context))
 512                     this.stack.Push(this.navCurrent.Clone());
 513             }
 514         }
 515
 516         /// <summary>
 517         /// Return true if the Current property is set to the next Preceding node in reverse document order.
 518         /// </summary>
 519         public bool MoveNext() {
 520             if (this.stack.IsEmpty)
 521                 return false;
 522
 523             this.navCurrent = this.stack.Pop();
 524             return true;
 525         }
 526
 527         /// <summary>
 528         /// Return the current result navigator.  This is only defined after MoveNext() has returned true.
 529         /// </summary>
 530         public XPathNavigator Current {
 531             get { return this.navCurrent; }
 532         }
 533     }
 534
 535
 536     /// <summary>
 537     /// Iterate over all preceding nodes according to XPath preceding axis rules, returning nodes in reverse
 538     /// document order.  These rules specify that ancestors are not included, even though they precede the
 539     /// starting node in document order.  For the "true" preceding axis, see PrecedingIterator.
 540     /// </summary>
 541     [EditorBrowsable(EditorBrowsableState.Never)]
 542     public struct XPathPrecedingIterator {
 543         private XmlNavigatorStack stack;
 544         private XPathNavigator navCurrent;
 545
 546         /// <summary>
 547         /// Initialize the XPathPrecedingIterator (no possibility of duplicates).
 548         /// </summary>
 549         public void Create(XPathNavigator context, XmlNavigatorFilter filter) {
 550             XPathPrecedingDocOrderIterator wrapped = new XPathPrecedingDocOrderIterator();
 551             wrapped.Create(context, filter);
 552             this.stack.Reset();
 553
 554             // Fetch all preceding nodes in document order and push them onto the stack
 555             while (wrapped.MoveNext())
 556                 this.stack.Push(wrapped.Current.Clone());
 557         }
 558
 559         /// <summary>
 560         /// Return true if the Current property is set to the next Preceding node in reverse document order.
 561         /// </summary>
 562         public bool MoveNext() {
 563             if (this.stack.IsEmpty)
 564                 return false;
 565
 566             this.navCurrent = this.stack.Pop();
 567             return true;
 568         }
 569
 570         /// <summary>
 571         /// Return the current result navigator.  This is only defined after MoveNext() has returned true.
 572         /// </summary>
 573         public XPathNavigator Current {
 574             get { return this.navCurrent; }
 575         }
 576     }
 577
 578
 579     /// <summary>
 580     /// Iterate over all preceding nodes according to XPath preceding axis rules, returning nodes in document order.
 581     /// </summary>
 582     [EditorBrowsable(EditorBrowsableState.Never)]
 583     public struct XPathPrecedingDocOrderIterator {
 584         private XmlNavigatorFilter filter;
 585         private XPathNavigator navCurrent;
 586         private XmlNavigatorStack navStack;
 587
 588         /// <summary>
 589         /// Initialize the XPathPrecedingDocOrderIterator (return preceding nodes in document order, no possibility of duplicates).
 590         /// </summary>
 591         public void Create(XPathNavigator input, XmlNavigatorFilter filter) {
 592             // Save input node as current node
 593             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, input);
 594             this.filter = filter;
 595             PushAncestors();
 596         }
 597
 598         /// <summary>
 599         /// Position this iterator to the next preceding node.  Return false if there are no more preceding nodes.
 600         /// Return true if the Current property is set to the next node in the iteration.
 601         /// </summary>
 602         public bool MoveNext() {
 603             if (!this.navStack.IsEmpty) {
 604                 while (true) {
 605                     // Move to the next matching node that is before the top node on the stack in document order
 606                     if (this.filter.MoveToFollowing(this.navCurrent, this.navStack.Peek()))
 607                         // Found match
 608                         return true;
 609
 610                     // Do not include ancestor nodes as part of the preceding axis
 611                     this.navCurrent.MoveTo(this.navStack.Pop());
 612
 613                     // No more preceding matches possible
 614                     if (this.navStack.IsEmpty)
 615                         break;
 616                 }
 617             }
 618
 619             return false;
 620         }
 621
 622         /// <summary>
 623         /// Return the current result navigator.  This is only defined after MoveNext() has returned true or
 624         /// IteratorResult.HaveCurrentNode.
 625         /// </summary>
 626         public XPathNavigator Current {
 627             get { return this.navCurrent; }
 628         }
 629
 630         /// <summary>
 631         /// Push all ancestors of this.navCurrent onto a stack.  The set of preceding nodes should not contain any of these
 632         /// ancestors.
 633         /// </summary>
 634         private void PushAncestors() {
 635             this.navStack.Reset();
 636             do {
 637                 this.navStack.Push(this.navCurrent.Clone());
 638             }
 639             while (this.navCurrent.MoveToParent());
 640
 641             // Pop the root of the tree, since MoveToFollowing calls will never return it
 642             this.navStack.Pop();
 643         }
 644     }
 645
 646
 647     /// <summary>
 648     /// Iterate over all preceding nodes according to XPath preceding axis rules, except that nodes are always
 649     /// returned in document order.  Merge multiple sets of preceding nodes in document order and remove duplicates.
 650     /// </summary>
 651     [EditorBrowsable(EditorBrowsableState.Never)]
 652     public struct XPathPrecedingMergeIterator {
 653         private XmlNavigatorFilter filter;
 654         private IteratorState state;
 655         private XPathNavigator navCurrent, navNext;
 656         private XmlNavigatorStack navStack;
 657
 658         private enum IteratorState {
 659             NeedCandidateCurrent = 0,
 660             HaveCandidateCurrent,
 661             HaveCurrentHaveNext,
 662             HaveCurrentNoNext,
 663         }
 664
 665         /// <summary>
 666         /// Initialize the XPathPrecedingMergeIterator (merge multiple sets of preceding nodes in document order and remove duplicates).
 667         /// </summary>
 668         public void Create(XmlNavigatorFilter filter) {
 669             this.filter = filter;
 670             this.state = IteratorState.NeedCandidateCurrent;
 671         }
 672
 673         /// <summary>
 674         /// Position this iterator to the next preceding node in document order.  Discard all input nodes
 675         /// that are followed by another input node in the same document.  This leaves one node per document from
 676         /// which the complete set of preceding nodes can be derived without possibility of duplicates.
 677         /// Return IteratorResult.NeedInputNode if the next input node needs to be fetched first.  Return
 678         /// IteratorResult.HaveCurrent if the Current property is set to the next node in the iteration.
 679         /// </summary>
 680         public IteratorResult MoveNext(XPathNavigator input) {
 681             switch (this.state) {
 682                 case IteratorState.NeedCandidateCurrent:
 683                     // If there are no more input nodes, then iteration is complete
 684                     if (input == null)
 685                         return IteratorResult.NoMoreNodes;
 686
 687                     // Save input node as current node
 688                     this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, input);
 689
 690                     // Scan for additional input nodes within the same document (since they are after navCurrent in docorder)
 691                     this.state = IteratorState.HaveCandidateCurrent;
 692                     return IteratorResult.NeedInputNode;
 693
 694                 case IteratorState.HaveCandidateCurrent:
 695                     // If there are no more input nodes,
 696                     if (input == null) {
 697                         // Then candidate node has been selected, and there are no further input nodes
 698                         this.state = IteratorState.HaveCurrentNoNext;
 699                     }
 700                     else {
 701                         // If the input node is in the same document as the current node,
 702                         if (this.navCurrent.ComparePosition(input) != XmlNodeOrder.Unknown) {
 703                             // Then update the current node and get the next input node
 704                             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, input);
 705                             return IteratorResult.NeedInputNode;
 706                         }
 707
 708                         // Save the input node as navNext
 709                         this.navNext = XmlQueryRuntime.SyncToNavigator(this.navNext, input);
 710                         this.state = IteratorState.HaveCurrentHaveNext;
 711                     }
 712                     PushAncestors();
 713                     break;
 714             }
 715
 716             if (!this.navStack.IsEmpty) {
 717                 while (true) {
 718                     // Move to the next matching node that is before the top node on the stack in document order
 719                     if (this.filter.MoveToFollowing(this.navCurrent, this.navStack.Peek()))
 720                         // Found match
 721                         return IteratorResult.HaveCurrentNode;
 722
 723                     // Do not include ancestor nodes as part of the preceding axis
 724                     this.navCurrent.MoveTo(this.navStack.Pop());
 725
 726                     // No more preceding matches possible
 727                     if (this.navStack.IsEmpty)
 728                         break;
 729                 }
 730             }
 731
 732             if (this.state == IteratorState.HaveCurrentNoNext) {
 733                 // No more nodes, so iteration is complete
 734                 this.state = IteratorState.NeedCandidateCurrent;
 735                 return IteratorResult.NoMoreNodes;
 736             }
 737
 738             // Make next node the current node and start trying to find input node greatest in docorder
 739             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, this.navNext);
 740             this.state = IteratorState.HaveCandidateCurrent;
 741             return IteratorResult.HaveCurrentNode;
 742         }
 743
 744         /// <summary>
 745         /// Return the current result navigator.  This is only defined after MoveNext() has returned true or
 746         /// IteratorResult.HaveCurrentNode.
 747         /// </summary>
 748         public XPathNavigator Current {
 749             get { return this.navCurrent; }
 750         }
 751
 752         /// <summary>
 753         /// Push all ancestors of this.navCurrent onto a stack.  The set of preceding nodes should not contain any of these
 754         /// ancestors.
 755         /// </summary>
 756         private void PushAncestors() {
 757             Debug.Assert(this.state == IteratorState.HaveCurrentHaveNext || this.state == IteratorState.HaveCurrentNoNext);
 758
 759             this.navStack.Reset();
 760             do {
 761                 this.navStack.Push(this.navCurrent.Clone());
 762             }
 763             while (this.navCurrent.MoveToParent());
 764
 765             // Pop the root of the tree, since MoveToFollowing calls will never return it
 766             this.navStack.Pop();
 767         }
 768     }
 769
 770
 771     /// <summary>
 772     /// Iterate over these nodes in document order (filtering out those that do not match the filter test):
 773     ///   1. Starting node
 774     ///   2. All content-typed nodes which follow the starting node until the ending node is reached
 775     ///   3. Ending node
 776     ///
 777     /// If the starting node is the same node as the ending node, iterate over the singleton node.
 778     /// If the starting node is after the ending node, or is in a different document, iterate to the
 779     /// end of the document.
 780     /// </summary>
 781     [EditorBrowsable(EditorBrowsableState.Never)]
 782     public struct NodeRangeIterator {
 783         private XmlNavigatorFilter filter;
 784         private XPathNavigator navCurrent, navEnd;
 785         private IteratorState state;
 786
 787         private enum IteratorState {
 788             HaveCurrent,
 789             NeedCurrent,
 790             HaveCurrentNoNext,
 791             NoNext,
 792         }
 793
 794         /// <summary>
 795         /// Initialize the NodeRangeIterator (no possibility of duplicates).
 796         /// </summary>
 797         public void Create(XPathNavigator start, XmlNavigatorFilter filter, XPathNavigator end) {
 798             // Save start node as current node and save ending node
 799             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, start);
 800             this.navEnd = XmlQueryRuntime.SyncToNavigator(this.navEnd, end);
 801             this.filter = filter;
 802
 803             if (start.IsSamePosition(end)) {
 804                 // Start is end, so only return node if it is not filtered
 805                 this.state = !filter.IsFiltered(start) ? IteratorState.HaveCurrentNoNext : IteratorState.NoNext;
 806             }
 807             else {
 808                 // Return nodes until end is reached
 809                 this.state = !filter.IsFiltered(start) ? IteratorState.HaveCurrent : IteratorState.NeedCurrent;
 810             }
 811         }
 812
 813         /// <summary>
 814         /// Position this iterator to the next following node.  Return false if there are no more following nodes,
 815         /// or if the end node has been reached.  Return true if the Current property is set to the next node in
 816         /// the iteration.
 817         /// </summary>
 818         public bool MoveNext() {
 819             switch (this.state) {
 820                 case IteratorState.HaveCurrent:
 821                     this.state = IteratorState.NeedCurrent;
 822                     return true;
 823
 824                 case IteratorState.NeedCurrent:
 825                     // Move to next following node which matches
 826                     if (!this.filter.MoveToFollowing(this.navCurrent, this.navEnd)) {
 827                         // No more nodes unless ending node matches
 828                         if (filter.IsFiltered(this.navEnd)) {
 829                             this.state = IteratorState.NoNext;
 830                             return false;
 831                         }
 832
 833                         this.navCurrent.MoveTo(this.navEnd);
 834                         this.state = IteratorState.NoNext;
 835                     }
 836                     return true;
 837
 838                 case IteratorState.HaveCurrentNoNext:
 839                     this.state = IteratorState.NoNext;
 840                     return true;
 841             }
 842
 843             Debug.Assert(this.state == IteratorState.NoNext, "Illegal state: " + this.state);
 844             return false;
 845         }
 846
 847         /// <summary>
 848         /// Return the current result navigator.  This is only defined after MoveNext() has returned true.
 849         /// </summary>
 850         public XPathNavigator Current {
 851             get { return this.navCurrent; }
 852         }
 853     }
 854 }