mcs/class/Mono.Xml.Ext/Mono.Xml.XPath2/XPathSequence.cs

   1 //
   2 // XPathSequence.cs - represents XPath sequence iterator
   3 //
   4 // Author:
   5 //      Atsushi Enomoto <atsushi@ximian.com>
   6 //
   7 //
   8 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
   9 //
  10 // Permission is hereby granted, free of charge, to any person obtaining
  11 // a copy of this software and associated documentation files (the
  12 // "Software"), to deal in the Software without restriction, including
  13 // without limitation the rights to use, copy, modify, merge, publish,
  14 // distribute, sublicense, and/or sell copies of the Software, and to
  15 // permit persons to whom the Software is furnished to do so, subject to
  16 // the following conditions:
  17 //
  18 // The above copyright notice and this permission notice shall be
  19 // included in all copies or substantial portions of the Software.
  20 //
  21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  22 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  23 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  24 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  25 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  26 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  27 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  28 //
  29
  30 #if NET_2_0
  31 using System;
  32 using System.Collections;
  33 using System.Globalization;
  34 using System.Xml;
  35 using System.Xml.Schema;
  36 using System.Xml.Query;
  37 using System.Xml.XPath;
  38
  39 namespace Mono.Xml.XPath2
  40 {
  41         public abstract class XPathSequence : IEnumerable, ICloneable
  42         {
  43                 XQueryContext ctx;
  44                 int countCache = -1;
  45                 int position = 0;
  46
  47                 internal XPathSequence (XQueryContext ctx)
  48                 {
  49                         this.ctx = ctx;
  50                 }
  51
  52                 internal XPathSequence (XPathSequence original)
  53                 {
  54                         ctx = original.ctx;
  55                         position = original.position;
  56                 }
  57
  58                 internal XQueryContext Context {
  59 //                      get { return ctx; }
  60                         get { return ctx.ContextManager.CurrentContext; }
  61                 }
  62
  63                 public virtual int Count {
  64                         get {
  65                                 if (countCache >= 0)
  66                                         return countCache;
  67                                 XPathSequence clone = Clone ();
  68                                 while (clone.MoveNext ())
  69                                         ;
  70                                 countCache = clone.Position;
  71                                 return countCache;
  72                         }
  73                 }
  74
  75                 public XPathItem Current {
  76                         get {
  77                                 if (Position == 0)
  78                                         throw new InvalidOperationException ("XQuery internal error (should not happen)");
  79                                 return CurrentCore;
  80                         }
  81                 }
  82
  83                 public abstract XPathItem CurrentCore { get; }
  84
  85                 // Returns 0 if not started, otherwise returns XPath positional integer.
  86                 public virtual int Position {
  87                         get { return position; }
  88                 }
  89
  90                 public virtual bool MoveNext ()
  91                 {
  92                         if (!MoveNextCore ())
  93                                 return false;
  94                         position++;
  95                         return true;
  96                 }
  97
  98                 protected abstract bool MoveNextCore ();
  99
 100                 public abstract XPathSequence Clone ();
 101
 102                 object ICloneable.Clone ()
 103                 {
 104                         return this.Clone ();
 105                 }
 106
 107                 public virtual IEnumerator GetEnumerator ()
 108                 {
 109                         while (MoveNext ())
 110                                 yield return CurrentCore;
 111                 }
 112
 113         }
 114
 115         // empty iterator (still required since it contains XQueryContext)
 116         class XPathEmptySequence : XPathSequence
 117         {
 118                 internal XPathEmptySequence (XQueryContext ctx)
 119                         : base (ctx)
 120                 {
 121                 }
 122
 123                 public override int Count {
 124                         get { return 0; }
 125                 }
 126
 127                 protected override bool MoveNextCore ()
 128                 {
 129                         return false;
 130                 }
 131
 132                 public override XPathItem CurrentCore {
 133                         get { throw new InvalidOperationException ("Should not happen. In XPathEmptySequence.Current."); }
 134                 }
 135
 136                 // Don't return clone. It's waste of resource.
 137                 public override XPathSequence Clone ()
 138                 {
 139                         return this;
 140                 }
 141         }
 142
 143         // single item iterator
 144
 145         internal class SingleItemIterator : XPathSequence
 146         {
 147                 XPathItem item;
 148                 XPathItem current;
 149
 150                 // for XQuery execution start point
 151                 internal SingleItemIterator (XPathItem item, XQueryContext ctx)
 152                         : base (ctx)
 153                 {
 154                         this.item = item;
 155                 }
 156
 157                 private SingleItemIterator (SingleItemIterator other)
 158                         : base (other)
 159                 {
 160                         this.item = other.item;
 161                         this.current = other.current;
 162                 }
 163
 164                 public override XPathSequence Clone ()
 165                 {
 166                         return new SingleItemIterator (this);
 167                 }
 168
 169                 protected override bool MoveNextCore ()
 170                 {
 171                         if (current == null) {
 172                                 current = item;
 173                                 return true;
 174                         }
 175                         return false;
 176                 }
 177
 178                 public override XPathItem CurrentCore {
 179                         get {
 180                                 return current;
 181                         }
 182                 }
 183         }
 184
 185         // RangeExpr iterator
 186
 187         internal class IntegerRangeIterator : XPathSequence
 188         {
 189                 static XmlSchemaSimpleType intType = XmlSchemaType.GetBuiltInSimpleType (new XmlQualifiedName ("int", XmlSchema.Namespace));
 190
 191                 int start;
 192                 int end;
 193                 int next;
 194                 XPathItem current;
 195
 196                 public IntegerRangeIterator (XQueryContext ctx, int start, int end)
 197                         : base (ctx)
 198                 {
 199                         this.start = start;
 200                         this.end = end;
 201                 }
 202
 203                 private IntegerRangeIterator (IntegerRangeIterator other)
 204                         : base (other)
 205                 {
 206                         this.start = other.start;
 207                         this.end = other.end;
 208                         this.next = other.next;
 209                         this.current = other.current;
 210                 }
 211
 212                 public override XPathSequence Clone ()
 213                 {
 214                         return new IntegerRangeIterator (this);
 215                 }
 216
 217                 protected override bool MoveNextCore ()
 218                 {
 219                         if (current == null)
 220                                 next = start;
 221                         if (next > end)
 222                                 return false;
 223                         current = new XPathAtomicValue (next++, intType);
 224                         return true;
 225                 }
 226
 227                 public override XPathItem CurrentCore {
 228                         get {
 229                                 return current;
 230                         }
 231                 }
 232         }
 233
 234         // Slash iterator
 235         // <copy original='System.Xml.XPath/Iterator.cs,
 236         //      System.Xml.XPath/XPathComparer.cs'>
 237         internal class PathStepIterator : XPathSequence
 238         {
 239                 XPathSequence left;
 240                 XPathSequence right;
 241                 PathStepExpr step;
 242                 ArrayList nodeStore;
 243                 SortedList storedIterators;
 244                 bool finished;
 245                 XPathSequence nextRight;
 246
 247                 public PathStepIterator (XPathSequence iter, PathStepExpr source)
 248                         : base (iter.Context)
 249                 {
 250                         left = iter;
 251                         step = source;
 252                 }
 253
 254                 private PathStepIterator (PathStepIterator other)
 255                         : base (other)
 256                 {
 257                         left = other.left.Clone ();
 258                         step = other.step;
 259                         if (other.right != null)
 260                                 right = other.right.Clone ();
 261                         if (other.nodeStore != null)
 262                                 nodeStore = (ArrayList) other.nodeStore.Clone ();
 263                         if (other.storedIterators != null)
 264                                 storedIterators = (SortedList) other.storedIterators.Clone ();
 265                         if (other.nextRight != null)
 266                                 nextRight = other.nextRight.Clone ();
 267                 }
 268
 269                 public override XPathSequence Clone ()
 270                 {
 271                         return new PathStepIterator (this);
 272                 }
 273
 274                 protected override bool MoveNextCore ()
 275                 {
 276                         if (finished)
 277                                 return false;
 278                         if (step.RequireSorting) {
 279                                 // Mainly '//' ('/descendant-or-self::node()/')
 280                                 if (nodeStore == null) {
 281                                         CollectResults ();
 282                                         if (nodeStore.Count == 0) {
 283                                                 finished = true;
 284                                                 return false;
 285                                         } else
 286                                                 // Initially it must not go to
 287                                                 // the while loop below
 288                                                 // (.Position -1 is -1).
 289                                                 return true;
 290                                 }
 291                                 if (nodeStore.Count == Position) {
 292                                         finished = true;
 293                                         return false;
 294                                 }
 295                                 while (nodeStore.Count > Position) {
 296                                         if (((XPathNavigator) nodeStore [Position]).ComparePosition (
 297                                                 (XPathNavigator) nodeStore [Position - 1]) == XmlNodeOrder.Same)
 298                                                 nodeStore.RemoveAt (Position);
 299                                         else
 300                                                 break;
 301                                 }
 302
 303                                 return true;
 304                         } else { // Sorting not required
 305                                 if (right == null) { // First time
 306                                         if (!left.MoveNext ())
 307                                                 return false;
 308                                         right = step.Next.Evaluate (left);
 309                                         storedIterators = new SortedList (XPathSequenceComparer.Instance);
 310                                 }
 311
 312                                 while (true) {
 313                                         while (!right.MoveNext ()) {
 314                                                 if (storedIterators.Count > 0) {
 315                                                         int last = storedIterators.Count - 1;
 316                                                         XPathSequence tmpIter = (XPathSequence) storedIterators.GetByIndex (last);
 317                                                         storedIterators.RemoveAt (last);
 318                                                         switch (((XPathNavigator) tmpIter.Current).ComparePosition ((XPathNavigator) right.Current)) {
 319                                                         case XmlNodeOrder.Same:
 320                                                         case XmlNodeOrder.Before:
 321                                                                 right = tmpIter;
 322                                                                 continue;
 323                                                         default:
 324                                                                 right = tmpIter;
 325                                                                 break;
 326                                                         }
 327                                                         break;
 328                                                 } else if (nextRight != null) {
 329                                                         right = nextRight;
 330                                                         nextRight = null;
 331                                                         break;
 332                                                 } else if (!left.MoveNext ()) {
 333                                                         finished = true;
 334                                                         return false;
 335                                                 }
 336                                                 else
 337                                                         right = step.Next.Evaluate (left);
 338                                         }
 339                                         bool loop = true;
 340                                         while (loop) {
 341                                                 loop = false;
 342                                                 if (nextRight == null) {
 343                                                         bool noMoreNext = false;
 344                                                         while (nextRight == null || !nextRight.MoveNext ()) {
 345                                                                 if(left.MoveNext ())
 346                                                                         nextRight = step.Next.Evaluate (left);
 347                                                                 else {
 348                                                                         noMoreNext = true;
 349                                                                         break;
 350                                                                 }
 351                                                         }
 352                                                         if (noMoreNext)
 353                                                                 nextRight = null; // FIXME: More efficient code. Maybe making noMoreNext class scope would be better.
 354                                                 }
 355                                                 if (nextRight != null) {
 356                                                         switch (((XPathNavigator) right.Current).ComparePosition ((XPathNavigator) nextRight.Current)) {
 357                                                         case XmlNodeOrder.After:
 358                                                                 storedIterators.Add (storedIterators.Count, right);
 359                                                                 right = nextRight;
 360                                                                 nextRight = null;
 361                                                                 loop = true;
 362                                                                 break;
 363                                                         case XmlNodeOrder.Same:
 364                                                                 if (!nextRight.MoveNext ())
 365                                                                         nextRight = null;
 366
 367                                                                 else {
 368                                                                         int last = storedIterators.Count;
 369                                                                         if (last > 0) {
 370                                                                                 storedIterators.Add (last, nextRight);
 371                                                                                 nextRight = (XPathSequence) storedIterators.GetByIndex (last);
 372                                                                                 storedIterators.RemoveAt (last);
 373                                                                         }
 374                                                                 }
 375
 376                                                                 loop = true;
 377                                                                 break;
 378                                                         }
 379                                                 }
 380                                         }
 381                                         return true;
 382                                 }
 383                         }
 384                 }
 385
 386                 private void CollectResults ()
 387                 {
 388                         if (nodeStore != null)
 389                                 return;
 390                         nodeStore = new ArrayList ();
 391                         while (true) {
 392                                 while (right == null || !right.MoveNext ()) {
 393                                         if (!left.MoveNext ()) {
 394                                                 nodeStore.Sort (XPathNavigatorComparer2.Instance);
 395                                                 return;
 396                                         }
 397                                         right = step.Next.Evaluate (left);
 398                                 }
 399                                 XPathNavigator nav = (XPathNavigator) right.Current;
 400                                 nodeStore.Add (nav);
 401                         }
 402                 }
 403
 404                 public override XPathItem CurrentCore {
 405                         get {
 406                                 if (Position <= 0) return null;
 407                                 if (step.RequireSorting) {
 408                                         return (XPathNavigator) nodeStore [Position - 1];
 409                                 } else {
 410                                         return right.Current;
 411                                 }
 412                         }
 413                 }
 414
 415                 public override int Count {
 416                         get {
 417                                 if (nodeStore == null)
 418                                         return base.Count;
 419                                 else
 420                                         return nodeStore.Count;
 421                         }
 422                 }
 423
 424
 425                 internal class XPathSequenceComparer : IComparer
 426                 {
 427                         public static XPathSequenceComparer Instance = new XPathSequenceComparer ();
 428                         private XPathSequenceComparer ()
 429                         {
 430                         }
 431
 432                         public int Compare (object o1, object o2)
 433                         {
 434                                 XPathSequence nav1 = o1 as XPathSequence;
 435                                 XPathSequence nav2 = o2 as XPathSequence;
 436                                 if (nav1 == null)
 437                                         return -1;
 438                                 if (nav2 == null)
 439                                         return 1;
 440                                 switch (((XPathNavigator) nav1.Current).ComparePosition ((XPathNavigator) nav2.Current)) {
 441                                 case XmlNodeOrder.Same:
 442                                         return 0;
 443                                 case XmlNodeOrder.After:
 444                                         return -1;
 445                                 default:
 446                                         return 1;
 447                                 }
 448                         }
 449                 }
 450
 451                 internal class XPathNavigatorComparer2 : IComparer
 452                 {
 453                         public static XPathNavigatorComparer2 Instance = new XPathNavigatorComparer2 ();
 454                         private XPathNavigatorComparer2 ()
 455                         {
 456                         }
 457
 458                         public int Compare (object o1, object o2)
 459                         {
 460                                 XPathNavigator nav1 = o1 as XPathNavigator;
 461                                 XPathNavigator nav2 = o2 as XPathNavigator;
 462                                 if (nav1 == null)
 463                                         return -1;
 464                                 if (nav2 == null)
 465                                         return 1;
 466                                 switch (nav1.ComparePosition (nav2)) {
 467                                 case XmlNodeOrder.Same:
 468                                         return 0;
 469                                 case XmlNodeOrder.After:
 470                                         return 1;
 471                                 default:
 472                                         return -1;
 473                                 }
 474                         }
 475                 }
 476         }
 477         // </copy>
 478
 479         // Filter step iterator
 480         internal class FilteredIterator : XPathSequence
 481         {
 482                 XPathSequence left;
 483                 ExprSequence filter;
 484
 485                 public FilteredIterator (XPathSequence iter, FilterStepExpr source)
 486                         : base (iter.Context)
 487                 {
 488                         left = source.Expr.Evaluate (iter);
 489                         filter = source.Predicate;
 490                 }
 491
 492                 private FilteredIterator (FilteredIterator other)
 493                         : base (other)
 494                 {
 495                         left = other.left.Clone ();
 496                         filter = other.filter;
 497                 }
 498
 499                 public override XPathSequence Clone ()
 500                 {
 501                         return new FilteredIterator (this);
 502                 }
 503
 504                 protected override bool MoveNextCore ()
 505                 {
 506                         // FIXME: as for numeric predicates, it is MUCH faster
 507                         // when it skips apparent non-candidates, with possible
 508                         // method implementation "XPathSequence.SkipTo (int)".
 509                         // When it comes true, iteration won't be done first.
 510                         while (left.MoveNext ()) {
 511                                 bool doesntPass = true;
 512                                 // Treat as OK if any of filter expr passed.
 513                                 // FIXME: handle numeric predicate.
 514                                 foreach (ExprSingle single in filter) {
 515                                         XPathAtomicValue av = single.EvaluateAsAtomic (left);
 516                                         if (av == null)
 517                                                 continue;
 518                                         if (SequenceType.IsNumeric (av.XmlType.TypeCode)) {
 519                                                 // numeric filter
 520                                                 if (av.ValueAsInt32 == left.Position) {
 521                                                         doesntPass = false;
 522                                                         break;
 523                                                 }
 524                                         }
 525                                         else if (single.EvaluateAsBoolean (left)) {
 526                                                 doesntPass = false;
 527                                                 break;
 528                                         }
 529                                 }
 530                                 if (doesntPass)
 531                                         continue;
 532                                 return true;
 533                         }
 534                         return false;
 535                 }
 536
 537                 public override XPathItem CurrentCore {
 538                         get { return left.Current; }
 539                 }
 540         }
 541
 542         // AxisIterator
 543         internal class AxisIterator : XPathSequence
 544         {
 545                 NodeIterator iter;
 546                 AxisStepExpr source;
 547
 548                 public AxisIterator (NodeIterator iter, AxisStepExpr source)
 549                         : base (iter.Context)
 550                 {
 551                         this.iter = iter;
 552                         this.source = source;
 553                 }
 554
 555                 private AxisIterator (AxisIterator other)
 556                         : base (other)
 557                 {
 558                         iter = (NodeIterator) other.iter.Clone ();
 559                         source = other.source;
 560                 }
 561
 562                 public override XPathSequence Clone ()
 563                 {
 564                         return new AxisIterator (this);
 565                 }
 566
 567                 protected override bool MoveNextCore ()
 568                 {
 569                         while (iter.MoveNext ()) {
 570                                 if (source.Matches (iter.Current as XPathNavigator))
 571                                         return true;
 572                         }
 573                         return false;
 574                 }
 575
 576                 public override XPathItem CurrentCore {
 577                         get { return iter.Current; }
 578                 }
 579         }
 580
 581         internal abstract class NodeIterator : XPathSequence
 582         {
 583                 XPathNavigator node;
 584                 XPathNavigator current;
 585                 bool emptyInput;
 586
 587                 public NodeIterator (XPathNavigator nav, XQueryContext ctx)
 588                         : base (ctx)
 589                 {
 590                         this.node = nav.Clone ();
 591                 }
 592
 593                 internal NodeIterator (NodeIterator other, bool cloneFlag)
 594                         : base (other)
 595                 {
 596                         if (other.emptyInput)
 597                                 emptyInput = true;
 598                         else
 599                                 node = other.node.Clone ();
 600                 }
 601
 602                 internal XPathNavigator Node {
 603                         get { return node; }
 604                 }
 605
 606                 public override bool MoveNext ()
 607                 {
 608                         if (emptyInput)
 609                                 return false;
 610                         if (!base.MoveNext ())
 611                                 return false;
 612                         current = null;
 613                         return true;
 614                 }
 615
 616                 public override XPathItem CurrentCore {
 617                         get {
 618                                 if (current == null)
 619                                         current = node.Clone ();
 620                                 return current;
 621                         }
 622                 }
 623
 624                 public virtual bool ReverseAxis {
 625                         get { return false; }
 626                 }
 627         }
 628
 629         // <copy original='System.Xml.XPath/Iterator.cs'>
 630
 631         internal class SelfIterator : NodeIterator
 632         {
 633                 public SelfIterator (XPathNavigator nav, XQueryContext ctx)
 634                         : base (nav, ctx)
 635                 {
 636                 }
 637
 638                 private SelfIterator (SelfIterator other, bool cloneFlag)
 639                         : base (other, true)
 640                 {
 641                 }
 642
 643                 public override XPathSequence Clone ()
 644                 {
 645                         return new SelfIterator (this, true);
 646                 }
 647
 648                 protected override bool MoveNextCore ()
 649                 {
 650                         if (Position == 0)
 651                                 return true;
 652                         return false;
 653                 }
 654         }
 655
 656         internal class ParentIterator : NodeIterator
 657         {
 658                 public ParentIterator (XPathNavigator nav, XQueryContext ctx)
 659                         : base (nav, ctx)
 660                 {
 661                 }
 662
 663                 private ParentIterator (ParentIterator other, bool cloneFlag)
 664                         : base (other, true)
 665                 {
 666                 }
 667
 668                 public override XPathSequence Clone ()
 669                 {
 670                         return new ParentIterator (this, true);
 671                 }
 672
 673                 protected override bool MoveNextCore ()
 674                 {
 675                         if (Position == 0 && Node.MoveToParent ())
 676                                 return true;
 677                         return false;
 678                 }
 679
 680                 public override bool ReverseAxis {
 681                         get { return true; }
 682                 }
 683         }
 684
 685         internal class ChildIterator : NodeIterator
 686         {
 687                 public ChildIterator (XPathNavigator nav, XQueryContext ctx)
 688                         : base (nav, ctx)
 689                 {
 690                 }
 691
 692                 private ChildIterator (ChildIterator other, bool cloneFlag)
 693                         : base (other, true)
 694                 {
 695                 }
 696
 697                 public override XPathSequence Clone ()
 698                 {
 699                         return new ChildIterator (this, true);
 700                 }
 701
 702                 protected override bool MoveNextCore ()
 703                 {
 704                         if (Position == 0)
 705                                 return Node.MoveToFirstChild ();
 706                         else
 707                                 return Node.MoveToNext ();
 708                 }
 709         }
 710
 711         internal class FollowingSiblingIterator : NodeIterator
 712         {
 713                 public FollowingSiblingIterator (XPathNavigator nav, XQueryContext ctx)
 714                         : base (nav, ctx)
 715                 {
 716                 }
 717
 718                 private FollowingSiblingIterator (FollowingSiblingIterator other, bool cloneFlag)
 719                         : base (other, true)
 720                 {
 721                 }
 722
 723                 public override XPathSequence Clone ()
 724                 {
 725                         return new FollowingSiblingIterator (this, true);
 726                 }
 727
 728                 protected override bool MoveNextCore ()
 729                 {
 730                         return Node.MoveToNext ();
 731                 }
 732         }
 733
 734         internal class PrecedingSiblingIterator : NodeIterator
 735         {
 736                 bool finished;
 737                 bool started;
 738                 XPathNavigator startPosition;
 739
 740                 public PrecedingSiblingIterator (XPathNavigator nav, XQueryContext ctx)
 741                         : base (nav, ctx)
 742                 {
 743                         startPosition = Node.Clone ();
 744                 }
 745
 746                 private PrecedingSiblingIterator (PrecedingSiblingIterator other, bool cloneFlag)
 747                         : base (other, true)
 748                 {
 749                         startPosition = other.startPosition;
 750                         started = other.started;
 751                         finished = other.finished;
 752                 }
 753
 754                 public override XPathSequence Clone ()
 755                 {
 756                         return new PrecedingSiblingIterator (this, true);
 757                 }
 758
 759                 protected override bool MoveNextCore ()
 760                 {
 761                         if (finished)
 762                                 return false;
 763                         if (!started) {
 764                                 started = true;
 765                                 Node.MoveToFirst ();
 766                         } else {
 767                                 Node.MoveToNext ();
 768                         }
 769                         if (Node.ComparePosition (startPosition) == XmlNodeOrder.Same) {
 770                                 finished = true;
 771                                 return false;
 772                         }
 773                         else
 774                                 return true;
 775                 }
 776
 777                 public override bool ReverseAxis {
 778                         get { return true; }
 779                 }
 780         }
 781
 782         internal class AncestorIterator : NodeIterator
 783         {
 784                 bool finished;
 785                 ArrayList nodes = new ArrayList ();
 786
 787                 public AncestorIterator (XPathNavigator nav, XQueryContext ctx)
 788                         : base (nav, ctx)
 789                 {
 790                 }
 791
 792                 private AncestorIterator (AncestorIterator other, bool cloneFlag)
 793                         : base (other, true)
 794                 {
 795                         finished = other.finished;
 796                         nodes = other.nodes;
 797                 }
 798
 799                 public override XPathSequence Clone ()
 800                 {
 801                         return new AncestorIterator (this, true);
 802                 }
 803
 804                 protected override bool MoveNextCore ()
 805                 {
 806                         if (finished)
 807                                 return false;
 808                         if (nodes != null) {
 809                                 nodes = new ArrayList ();
 810                                 while (Node.MoveToParent () && Node.NodeType != XPathNodeType.Root)
 811                                         nodes.Add (Node.Clone ());
 812                                 nodes.Reverse ();
 813                         }
 814                         if (nodes.Count >= Position)
 815                                 return false;
 816                         Node.MoveTo (nodes [Position] as XPathNavigator);
 817                         return true;
 818                 }
 819
 820                 public override bool ReverseAxis {
 821                         get { return true; }
 822                 }
 823
 824                 public override int Count {
 825                         get {
 826                                 if (Position == 0)
 827                                         return base.Count;
 828                                 return nodes.Count;
 829                         }
 830                 }
 831         }
 832
 833         internal class AncestorOrSelfIterator : NodeIterator
 834         {
 835                 bool finished;
 836                 ArrayList nodes = new ArrayList ();
 837
 838                 public AncestorOrSelfIterator (XPathNavigator nav, XQueryContext ctx)
 839                         : base (nav, ctx)
 840                 {
 841                 }
 842
 843                 private AncestorOrSelfIterator (AncestorOrSelfIterator other, bool cloneFlag)
 844                         : base (other, true)
 845                 {
 846                         finished = other.finished;
 847                         nodes = other.nodes;
 848                 }
 849
 850                 public override XPathSequence Clone ()
 851                 {
 852                         return new AncestorOrSelfIterator (this, true);
 853                 }
 854
 855                 protected override bool MoveNextCore ()
 856                 {
 857                         if (finished)
 858                                 return false;
 859                         if (nodes != null) {
 860                                 nodes = new ArrayList ();
 861                                 do {
 862                                         nodes.Add (Node.Clone ());
 863                                 } while (Node.MoveToParent () && Node.NodeType != XPathNodeType.Root);
 864                                 nodes.Reverse ();
 865                         }
 866                         if (nodes.Count >= Position)
 867                                 return false;
 868                         Node.MoveTo (nodes [Position] as XPathNavigator);
 869                         return true;
 870                 }
 871
 872                 public override bool ReverseAxis {
 873                         get { return true; }
 874                 }
 875
 876                 public override int Count {
 877                         get {
 878                                 if (Position == 0)
 879                                         return base.Count;
 880                                 return nodes.Count;
 881                         }
 882                 }
 883         }
 884
 885         internal class DescendantIterator : NodeIterator
 886         {
 887                 private int depth;
 888                 private bool finished;
 889
 890                 public DescendantIterator (XPathNavigator nav, XQueryContext ctx)
 891                         : base (nav, ctx)
 892                 {
 893                 }
 894
 895                 private DescendantIterator (DescendantIterator other, bool cloneFlag)
 896                         : base (other, true)
 897                 {
 898                         finished = other.finished;
 899                         depth = other.depth;
 900                 }
 901
 902                 public override XPathSequence Clone ()
 903                 {
 904                         return new DescendantIterator (this, true);
 905                 }
 906
 907                 protected override bool MoveNextCore ()
 908                 {
 909                         if (finished)
 910                                 return false;
 911
 912                         if (Node.MoveToFirstChild ()) {
 913                                 depth ++;
 914                                 return true;
 915                         }
 916                         while (depth != 0) {
 917                                 if (Node.MoveToNext ())
 918                                         return true;
 919
 920                                 if (!Node.MoveToParent ())      // should NEVER fail!
 921                                         throw new XmlQueryException ("There seems some bugs on the XPathNavigator implementation class.");
 922                                 depth --;
 923                         }
 924                         finished = true;
 925                         return false;
 926                 }
 927         }
 928
 929         internal class DescendantOrSelfIterator : NodeIterator
 930         {
 931                 protected int depth;
 932                 private bool finished;
 933
 934                 public DescendantOrSelfIterator (XPathNavigator nav, XQueryContext ctx)
 935                         : base (nav, ctx)
 936                 {
 937                 }
 938
 939                 protected DescendantOrSelfIterator (DescendantOrSelfIterator other, bool cloneFlag)
 940                         : base (other, true)
 941                 {
 942                         depth = other.depth;
 943                         finished = other.finished;
 944                 }
 945
 946                 public override XPathSequence Clone ()
 947                 {
 948                         return new DescendantOrSelfIterator (this, true);
 949                 }
 950
 951                 protected override bool MoveNextCore ()
 952                 {
 953                         if (finished)
 954                                 return false;
 955
 956                         if (Position == 0)
 957                                 return true; // Self
 958
 959
 960                         if (Node.MoveToFirstChild ()) {
 961                                 depth ++;
 962                                 return true;
 963                         }
 964                         while (depth != 0) {
 965                                 if (Node.MoveToNext ())
 966                                         return true;
 967
 968                                 if (!Node.MoveToParent ())      // should NEVER fail!
 969                                         throw new XmlQueryException ("There seems some bugs on the XPathNavigator implementation class.");
 970                                 depth --;
 971                         }
 972                         finished = true;
 973                         return false;
 974                 }
 975         }
 976
 977         internal class FollowingIterator : NodeIterator
 978         {
 979                 private bool finished;
 980
 981                 public FollowingIterator (XPathNavigator nav, XQueryContext ctx)
 982                         : base (nav, ctx)
 983                 {
 984                 }
 985
 986                 protected FollowingIterator (FollowingIterator other, bool cloneFlag)
 987                         : base (other, true)
 988                 {
 989                         finished = other.finished;
 990                 }
 991
 992                 public override XPathSequence Clone ()
 993                 {
 994                         return new FollowingIterator (this, true);
 995                 }
 996
 997                 protected override bool MoveNextCore ()
 998                 {
 999                         if (finished)
1000                                 return false;
1001                         if (Position == 0) {
1002                                 // At first, it should not iterate children.
1003                                 if (Node.MoveToNext ())
1004                                         return true;
1005                                 else {
1006                                         while (Node.MoveToParent ())
1007                                                 if (Node.MoveToNext ())
1008                                                         return true;
1009                                 }
1010                         } else {
1011                                 if (Node.MoveToFirstChild ())
1012                                         return true;
1013                                 do {
1014                                         if (Node.MoveToNext ())
1015                                                 return true;
1016                                 } while (Node.MoveToParent ());
1017                         }
1018                         finished = true;
1019                         return false;
1020                 }
1021         }
1022
1023         internal class PrecedingIterator : NodeIterator
1024         {
1025                 bool finished;
1026                 bool started;
1027                 XPathNavigator startPosition;
1028
1029                 public PrecedingIterator (XPathNavigator nav, XQueryContext ctx)
1030                         : base (nav, ctx)
1031                 {
1032                         startPosition = Node.Clone ();
1033                 }
1034
1035                 private PrecedingIterator (PrecedingIterator other, bool cloneFlag)
1036                         : base (other, true)
1037                 {
1038                         startPosition = other.startPosition;
1039                         started = other.started;
1040                         finished = other.finished;
1041                 }
1042
1043                 public override XPathSequence Clone ()
1044                 {
1045                         return new PrecedingIterator (this, true);
1046                 }
1047
1048                 protected override bool MoveNextCore ()
1049                 {
1050                         if (finished)
1051                                 return false;
1052                         if (!started) {
1053                                 started = true;
1054                                 Node.MoveToRoot ();
1055                         }
1056                         bool loop = true;
1057                         while (loop) {
1058                                 while (!Node.MoveToFirstChild ()) {
1059                                         while (!Node.MoveToNext ()) {
1060                                                 if (!Node.MoveToParent ()) { // Should not finish, at least before startPosition.
1061                                                         finished = true;
1062                                                         return false;
1063                                                 }
1064                                         }
1065                                         break;
1066                                 }
1067                                 if (Node.IsDescendant (startPosition))
1068                                         continue;
1069                                 loop = false;
1070                                 break;
1071                         }
1072                         if (Node.ComparePosition (startPosition) != XmlNodeOrder.Before) {
1073                                 // Note that if _nav contains only 1 node, it won't be Same.
1074                                 finished = true;
1075                                 return false;
1076                         }
1077                         else
1078                                 return true;
1079                 }
1080
1081                 public override bool ReverseAxis {
1082                         get { return true; }
1083                 }
1084         }
1085
1086         internal class NamespaceIterator : NodeIterator
1087         {
1088                 public NamespaceIterator (XPathNavigator nav, XQueryContext ctx)
1089                         : base (nav, ctx)
1090                 {
1091                 }
1092
1093                 private NamespaceIterator (NamespaceIterator other, bool cloneFlag)
1094                         : base (other, true)
1095                 {
1096                 }
1097
1098                 public override XPathSequence Clone ()
1099                 {
1100                         return new NamespaceIterator (this, true);
1101                 }
1102
1103                 protected override bool MoveNextCore ()
1104                 {
1105                         if (Position == 0) {
1106                                 if (Node.MoveToFirstNamespace ())
1107                                         return true;
1108                         }
1109                         else if (Node.MoveToNextNamespace ())
1110                                 return true;
1111                         return false;
1112                 }
1113
1114                 public override bool ReverseAxis { get { return true; } }
1115         }
1116
1117         internal class AttributeIterator : NodeIterator
1118         {
1119                 public AttributeIterator (XPathNavigator nav, XQueryContext ctx)
1120                         : base (nav, ctx)
1121                 {
1122                 }
1123
1124                 private AttributeIterator (AttributeIterator other, bool cloneFlag)
1125                         : base (other, true)
1126                 {
1127                 }
1128
1129                 public override XPathSequence Clone ()
1130                 {
1131                         return new AttributeIterator (this, true);
1132                 }
1133
1134                 protected override bool MoveNextCore ()
1135                 {
1136                         if (Position == 0) {
1137                                 if (Node.MoveToFirstAttribute ())
1138                                         return true;
1139                         }
1140                         else if (Node.MoveToNextAttribute ())
1141                                 return true;
1142                         return false;
1143                 }
1144         }
1145
1146         // </copy>
1147
1148         internal class ExprSequenceIterator : XPathSequence
1149         {
1150                 XPathSequence contextSequence;
1151                 XPathSequence iter;
1152                 ExprSequence expr;
1153                 int currentExprIndex;
1154
1155                 public ExprSequenceIterator (XPathSequence iter, ExprSequence expr)
1156                         : base (iter.Context)
1157                 {
1158                         contextSequence = iter;
1159                         this.expr = expr;
1160                 }
1161
1162                 private ExprSequenceIterator (ExprSequenceIterator other)
1163                         : base (other)
1164                 {
1165                         if (other.iter != null)
1166                                 iter = other.iter.Clone ();
1167                         expr = other.expr;
1168                         contextSequence = other.contextSequence;
1169                         currentExprIndex = other.currentExprIndex;
1170                 }
1171
1172                 public override XPathSequence Clone ()
1173                 {
1174                         return new ExprSequenceIterator (this);
1175                 }
1176
1177                 protected override bool MoveNextCore ()
1178                 {
1179                         if (iter != null && iter.MoveNext ())
1180                                 return true;
1181                         while (currentExprIndex < expr.Count) {
1182                                 iter = expr [currentExprIndex++].Evaluate (contextSequence);
1183                                 if (iter.MoveNext ())
1184                                         return true;
1185                         }
1186                         return false;
1187                 }
1188
1189                 public override XPathItem CurrentCore {
1190                         get { return iter.Current; }
1191                 }
1192         }
1193
1194         // FLWOR - Order By
1195         internal class FLWORIterator : XPathSequence
1196         {
1197                 XPathSequence contextSequence;
1198                 FLWORExpr expr;
1199                 ArrayList forStack = new ArrayList ();
1200                 IEnumerator en;
1201                 bool finished;
1202
1203                 public FLWORIterator (XPathSequence iter, FLWORExpr expr)
1204                         : base (iter.Context)
1205                 {
1206                         this.contextSequence = iter;
1207                         this.expr = expr;
1208                 }
1209
1210                 private FLWORIterator (FLWORIterator other)
1211                         : base (other)
1212                 {
1213                         contextSequence = other.contextSequence;
1214                         expr = other.expr;
1215                         forStack = other.forStack.Clone () as ArrayList;
1216                         if (en != null)
1217                                 en = ((ICloneable) other.en).Clone () as IEnumerator;
1218                         finished = other.finished;
1219                 }
1220
1221                 public override XPathSequence Clone ()
1222                 {
1223                         return new FLWORIterator (this);
1224                 }
1225
1226                 protected override bool MoveNextCore ()
1227                 {
1228                         if (en == null)
1229                                 en = GetEnumerator ();
1230                         return en.MoveNext ();
1231                 }
1232
1233                 public override IEnumerator GetEnumerator ()
1234                 {
1235                         return EvaluateRemainingForLet (0);
1236                 }
1237
1238                 private IEnumerator EvaluateRemainingForLet (int flcPosition)
1239                 {
1240                         // Prepare iteration stack
1241                         if (flcPosition < expr.ForLetClauses.Count) {
1242                                 IEnumerator items = EvaluateRemainingSingleItem (flcPosition, 0);
1243                                 while (items.MoveNext ())
1244                                         yield return items.Current;
1245                         } else {
1246                                 bool passedFilter = expr.WhereClause == null;
1247                                 if (!passedFilter)
1248                                         passedFilter = expr.WhereClause.EvaluateAsBoolean (contextSequence);
1249                                 if (passedFilter) {
1250                                         IEnumerator ie = expr.ReturnExpr.Evaluate (contextSequence).GetEnumerator ();
1251                                         while (ie.MoveNext ())
1252                                                 yield return (XPathItem) ie.Current;
1253                                 }
1254                         }
1255                 }
1256
1257                 private IEnumerator EvaluateRemainingSingleItem (int flcPosition, int singlePosition)
1258                 {
1259                         if (singlePosition < expr.ForLetClauses [flcPosition].Count) {
1260                                 ForLetSingleBody sb = expr.ForLetClauses [flcPosition] [singlePosition];
1261                                 ForSingleBody fsb = sb as ForSingleBody;
1262                                 if (fsb != null) {
1263                                         XPathSequence backup = contextSequence;
1264                                         contextSequence = fsb.Expression.Evaluate (Context.CurrentSequence);
1265                                         Context.ContextManager.PushCurrentSequence (contextSequence);
1266                                         while (contextSequence.MoveNext ()) {
1267                                                 XPathItem forItem = (XPathItem) contextSequence.Current;
1268                                                 Context.PushVariable (fsb.PositionalVar, contextSequence.Position);
1269                                                 Context.PushVariable (sb.VarName, forItem);
1270                                                 // recurse here (including following bindings)
1271                                                 IEnumerator items = EvaluateRemainingSingleItem (flcPosition, singlePosition + 1);
1272                                                 while (items.MoveNext ())
1273                                                         yield return (XPathItem) items.Current;
1274                                                 Context.PopVariable ();
1275                                                 Context.PopVariable ();
1276                                         }
1277                                         Context.ContextManager.PopCurrentSequence ();
1278                                         contextSequence = backup;
1279                                 } else {
1280                                         Context.PushVariable (sb.VarName, sb.Expression.Evaluate (contextSequence));
1281                                         // recurse here (including following bindings)
1282                                         IEnumerator items = EvaluateRemainingSingleItem (flcPosition, singlePosition + 1);
1283                                         while (items.MoveNext ())
1284                                                 yield return (XPathItem) items.Current;
1285                                         Context.PopVariable ();
1286                                 }
1287                         } else {
1288                                 // evaluate next binding
1289                                 IEnumerator items = EvaluateRemainingForLet (flcPosition + 1);
1290                                 while (items.MoveNext ())
1291                                         yield return (XPathItem) items.Current;
1292                         }
1293                 }
1294
1295                 public override XPathItem CurrentCore {
1296                         get { return (XPathItem) en.Current; }
1297                 }
1298         }
1299
1300         internal class GroupIterator : XPathSequence
1301         {
1302                 GroupExpr expr;
1303                 XPathSequence lseq;
1304                 XPathSequence rseq;
1305                 bool started;
1306                 bool left;
1307                 bool leftFinished;
1308                 bool rightFinished;
1309
1310                 public GroupIterator (XPathSequence iter, GroupExpr expr)
1311                         : base (iter.Context)
1312                 {
1313                         this.expr = expr;
1314                         left = true;
1315                         lseq = expr.Left.EvaluateOrdered (iter);
1316                         rseq = expr.Right.EvaluateOrdered (iter);
1317                 }
1318
1319                 private GroupIterator (GroupIterator other)
1320                         : base (other)
1321                 {
1322                         this.expr = other.expr;
1323                         this.started = other.started;
1324                         this.left = other.left;
1325                         this.leftFinished = other.leftFinished;
1326                         this.rightFinished = other.rightFinished;
1327                         this.lseq = other.lseq.Clone ();
1328                         this.rseq = other.rseq.Clone ();
1329                 }
1330
1331                 public override XPathSequence Clone ()
1332                 {
1333                         return new GroupIterator (this);
1334                 }
1335
1336                 protected override bool MoveNextCore ()
1337                 {
1338                         if (leftFinished && rightFinished)
1339                                 return false;
1340                         bool proceeded = false;
1341                         if (started) {
1342                                 if (left) {
1343                                         if (!leftFinished && lseq.MoveNext ())
1344                                                 proceeded = true;
1345                                         else
1346                                                 leftFinished = true;
1347                                 } else {
1348                                         if (rightFinished && rseq.MoveNext ())
1349                                                 proceeded = true;
1350                                         else
1351                                                 rightFinished = true;
1352                                 }
1353                         } else {
1354                                 started = true;
1355                                 if (!lseq.MoveNext ()) {
1356                                         leftFinished = true;
1357                                         if (!rseq.MoveNext ()) {
1358                                                 rightFinished = true;
1359                                                 return false;
1360                                         }
1361                                         left = false;
1362                                         return true;
1363                                 }
1364                                 proceeded = true;
1365                                 if (!rseq.MoveNext ()) {
1366                                         rightFinished = true;
1367                                         return true;
1368                                 }
1369                         }
1370                         if (!proceeded) {
1371                                 if (expr.AggregationType == AggregationType.Intersect)
1372                                         return false;
1373                                 left = !leftFinished;
1374                                 return !leftFinished || !rightFinished;
1375                         }
1376
1377                         XPathNavigator lnav = lseq.Current as XPathNavigator;
1378                         XPathNavigator rnav = rseq.Current as XPathNavigator;
1379                         if (lnav == null || rnav == null)
1380                                 throw new XmlQueryException ("XP0006: Evaluation against union, intersect, except expressions must result in nodes.");
1381                         XmlNodeOrder order = lnav.ComparePosition (rnav);
1382                         switch (order) {
1383                         case XmlNodeOrder.Same:
1384                                 switch (expr.AggregationType) {
1385                                 case AggregationType.Union:
1386                                         left = false;
1387                                         if (!lseq.MoveNext ())
1388                                                 leftFinished = true;
1389                                         return true;
1390                                 case AggregationType.Intersect:
1391                                         return true;
1392                                 case AggregationType.Except:
1393                                 default:
1394                                         return MoveNext ();
1395                                 }
1396                         case XmlNodeOrder.Before:
1397                                 left = true;
1398                                 if (expr.AggregationType == AggregationType.Intersect)
1399                                         return MoveNext ();
1400                                 return true;
1401                         default: // After, Unknown
1402                                 left = false;
1403                                 if (expr.AggregationType == AggregationType.Intersect)
1404                                         return MoveNext ();
1405                                 return true;
1406                         }
1407                 }
1408
1409                 public override XPathItem CurrentCore {
1410                         get { return left ? lseq.Current : rseq.Current; }
1411                 }
1412         }
1413
1414         internal class AtomizingIterator : XPathSequence
1415         {
1416                 XPathSequence iter;
1417
1418                 public AtomizingIterator (XPathSequence iter)
1419                         : base (iter.Context)
1420                 {
1421                         this.iter = iter;
1422                 }
1423
1424                 private AtomizingIterator (AtomizingIterator other)
1425                         : base (other)
1426                 {
1427                         iter = other.iter.Clone ();
1428                 }
1429
1430                 public override XPathSequence Clone ()
1431                 {
1432                         return new AtomizingIterator (this);
1433                 }
1434
1435                 protected override bool MoveNextCore ()
1436                 {
1437                         return iter.MoveNext ();
1438                 }
1439
1440                 public override XPathItem CurrentCore {
1441                         get {
1442                                 XPathNavigator nav = iter.Current as XPathNavigator;
1443                                 if (nav == null)
1444                                         return (XPathAtomicValue) iter.Current;
1445                                 if (nav.SchemaInfo != null)
1446                                         return new XPathAtomicValue (
1447                                                 nav.TypedValue,
1448                                                 nav.SchemaInfo.SchemaType);
1449                                 else
1450                                         return new XPathAtomicValue (nav.Value, null);
1451                         }
1452                 }
1453         }
1454
1455         internal class ConvertingIterator : XPathSequence
1456         {
1457                 XPathSequence iter;
1458                 SequenceType type;
1459
1460                 public ConvertingIterator (XPathSequence iter, SequenceType type)
1461                         : base (iter.Context)
1462                 {
1463                         this.iter = iter;
1464                         this.type = type;
1465                 }
1466
1467                 private ConvertingIterator (ConvertingIterator other)
1468                         : base (other)
1469                 {
1470                         iter = other.iter.Clone ();
1471                         type = other.type;
1472                 }
1473
1474                 public override XPathSequence Clone ()
1475                 {
1476                         return new ConvertingIterator (this);
1477                 }
1478
1479                 protected override bool MoveNextCore ()
1480                 {
1481                         return iter.MoveNext ();
1482                 }
1483
1484                 public override XPathItem CurrentCore {
1485                         get { return type.Convert (iter.Current); }
1486                 }
1487         }
1488
1489         internal class TracingIterator : XPathSequence
1490         {
1491                 XPathSequence iter;
1492                 string format;
1493
1494                 public TracingIterator (XPathSequence iter, string format)
1495                         : base (iter.Context)
1496                 {
1497                         this.iter = iter;
1498                         this.format = format;
1499                 }
1500
1501                 private TracingIterator (TracingIterator other)
1502                         : base (other)
1503                 {
1504                         iter = other.iter.Clone ();
1505                         format = other.format;
1506                 }
1507
1508                 public override XPathSequence Clone ()
1509                 {
1510                         return new TracingIterator (this);
1511                 }
1512
1513                 protected override bool MoveNextCore ()
1514                 {
1515                         if (!iter.MoveNext ())
1516                                 return false;
1517                         // FIXME: use OnMessageEvent
1518                         string output = String.Format (format, iter.Current.TypedValue);
1519                         Context.StaticContext.OnMessageEvent (iter.Current, new QueryEventArgs (output));
1520                         return true;
1521                 }
1522
1523                 public override XPathItem CurrentCore {
1524                         get { return iter.Current; }
1525                 }
1526         }
1527
1528         internal class QueryEventArgs
1529         {
1530                 string msg;
1531
1532                 public QueryEventArgs (string msg)
1533                 {
1534                         this.msg = msg;
1535                 }
1536
1537                 public string Message {
1538                         get { return msg; }
1539                 }
1540         }
1541
1542         internal class ListIterator : XPathSequence
1543         {
1544                 IList list;
1545
1546                 public ListIterator (XQueryContext ctx, IList list)
1547                         : base (ctx)
1548                 {
1549                         if (list is ICloneable)
1550                                 this.list = list;
1551                         else
1552                                 throw new InvalidOperationException (String.Format ("XQuery internal error: target list is not cloneable. List is {0}.", list != null ? list.GetType ().ToString () : "null argument"));
1553                 }
1554
1555                 private ListIterator (ListIterator other)
1556                         : base (other)
1557                 {
1558                         this.list = (IList) ((ICloneable) other.list).Clone ();
1559                 }
1560
1561                 public override XPathSequence Clone ()
1562                 {
1563                         return new ListIterator (this);
1564                 }
1565
1566                 protected override bool MoveNextCore ()
1567                 {
1568                         return (Position < list.Count);
1569                 }
1570
1571                 public override XPathItem CurrentCore {
1572                         get { return (XPathItem) list [Position - 1]; }
1573                 }
1574         }
1575
1576         internal class EnumeratorIterator : XPathSequence
1577         {
1578                 IEnumerator list;
1579
1580                 public EnumeratorIterator (XQueryContext ctx, IEnumerable en)
1581                         : base (ctx)
1582                 {
1583                         list = en.GetEnumerator ();
1584                         if (list is ICloneable)
1585                                 this.list = list;
1586                         else
1587                                 throw new InvalidOperationException (String.Format ("XQuery internal error: target list's enumerator is not cloneable. List is {0}.", en != null ? en.GetType ().ToString () : "null argument"));
1588                 }
1589
1590                 private EnumeratorIterator (EnumeratorIterator other)
1591                         : base (other)
1592                 {
1593                         this.list = (IEnumerator) ((ICloneable) other.list).Clone ();
1594                 }
1595
1596                 public override XPathSequence Clone ()
1597                 {
1598                         return new EnumeratorIterator (this);
1599                 }
1600
1601                 protected override bool MoveNextCore ()
1602                 {
1603                         return list.MoveNext ();
1604                 }
1605
1606                 public override XPathItem CurrentCore {
1607                         get { return (XPathItem) list.Current; }
1608                 }
1609         }
1610
1611         internal abstract class WrapperIterator : XPathSequence
1612         {
1613                 XPathSequence source;
1614
1615                 public WrapperIterator (XPathSequence source)
1616                         : base (source.Context)
1617                 {
1618                         this.source = source;
1619                 }
1620
1621                 protected WrapperIterator (WrapperIterator other, bool flag)
1622                         : base (other)
1623                 {
1624                         source = other.source.Clone ();
1625                 }
1626
1627                 public XPathSequence Source {
1628                         get { return source; }
1629                 }
1630
1631                 public override XPathItem CurrentCore {
1632                         get { return source.Current; }
1633                 }
1634         }
1635
1636         internal class RemovalIterator : WrapperIterator
1637         {
1638                 int position;
1639
1640                 public RemovalIterator (XPathSequence source, int position)
1641                         : base (source)
1642                 {
1643                         this.position = position;
1644                 }
1645
1646                 protected RemovalIterator (RemovalIterator other)
1647                         : base (other, true)
1648                 {
1649                         position = other.position;
1650                 }
1651
1652                 public override XPathSequence Clone ()
1653                 {
1654                         return new RemovalIterator (this);
1655                 }
1656
1657                 protected override bool MoveNextCore ()
1658                 {
1659                         if (!Source.MoveNext ())
1660                                 return false;
1661                         else if (Source.Position == position) // skip target
1662                                 return Source.MoveNext ();
1663                         else
1664                                 return true;
1665                 }
1666         }
1667
1668         internal class InsertingIterator : WrapperIterator
1669         {
1670                 int position;
1671                 XPathSequence inserts;
1672                 bool sourceFinished;
1673                 bool insertsFinished;
1674                 XPathSequence currentSequence;
1675
1676                 public InsertingIterator (XPathSequence target, int position, XPathSequence inserts)
1677                         : base (target)
1678                 {
1679                         this.position = position;
1680                         this.inserts = inserts;
1681                         currentSequence = target;
1682                 }
1683
1684                 protected InsertingIterator (InsertingIterator other)
1685                         : base (other)
1686                 {
1687                         position = other.position;
1688                         inserts = other.inserts.Clone ();
1689                         sourceFinished = other.sourceFinished;
1690                         insertsFinished = other.insertsFinished;
1691                         currentSequence =
1692                                 other.inserts == other.currentSequence ?
1693                                 inserts : Source;
1694                 }
1695
1696                 public override XPathSequence Clone ()
1697                 {
1698                         return new InsertingIterator (this);
1699                 }
1700
1701                 protected override bool MoveNextCore ()
1702                 {
1703                         if (insertsFinished && sourceFinished)
1704                                 return false;
1705                         if (sourceFinished) { // position >= source.Count
1706                                 currentSequence = inserts;
1707                                 if (inserts.MoveNext ())
1708                                         return true;
1709                                 insertsFinished = true;
1710                                 return false;
1711                         }
1712                         else if (insertsFinished) { // after insertion
1713                                 if (Source.MoveNext ())
1714                                         return true;
1715                                 sourceFinished = true;
1716                                 return false;
1717                         }
1718                         else if (Position >= position - 1) {
1719                                 currentSequence = inserts;
1720                                 if (inserts.MoveNext ())
1721                                         return true;
1722                                 currentSequence = Source;
1723                                 insertsFinished = true;
1724                         }
1725                         if (Source.MoveNext ())
1726                                 return true;
1727                         sourceFinished = true;
1728                         return MoveNextCore ();
1729                 }
1730
1731                 public override XPathItem CurrentCore {
1732                         get { return currentSequence.Current; }
1733                 }
1734         }
1735
1736         internal class DistinctValueIterator : XPathSequence
1737         {
1738                 XPathSequence items;
1739                 CultureInfo collation;
1740                 Hashtable table = new Hashtable ();
1741
1742                 public DistinctValueIterator (XQueryContext ctx, XPathSequence items, CultureInfo collation)
1743                         : base (ctx)
1744                 {
1745                         this.items = items;
1746                         this.collation = collation;
1747                 }
1748
1749                 protected DistinctValueIterator (DistinctValueIterator other)
1750                         : base (other)
1751                 {
1752                         items = other.items.Clone ();
1753                         collation = other.collation;
1754                         table = (Hashtable) other.table.Clone ();
1755                 }
1756
1757                 public override XPathSequence Clone ()
1758                 {
1759                         return new DistinctValueIterator (this);
1760                 }
1761
1762                 protected override bool MoveNextCore ()
1763                 {
1764                         if (!items.MoveNext ())
1765                                 return false;
1766                         // FIXME: use collations
1767                         // FIXME: check if it really works (esp. Uri et.al)
1768                         if (table.Contains (items.Current.TypedValue))
1769                                 return MoveNextCore ();
1770                         return true;
1771                 }
1772
1773                 public override XPathItem CurrentCore {
1774                         get { return items.Current; }
1775                 }
1776         }
1777 }
1778
1779 #endif