mcs/class/referencesource/System.ServiceModel/System/ServiceModel/Dispatcher/QueryNode.cs

   1 //------------------------------------------------------------
   2 // Copyright (c) Microsoft Corporation.  All rights reserved.
   3 //------------------------------------------------------------
   4 namespace System.ServiceModel.Dispatcher
   5 {
   6     using System;
   7     using System.Collections;
   8     using System.Collections.Generic;
   9     using System.Runtime;
  10     using System.Threading;
  11     using System.Xml;
  12     using System.Xml.XPath;
  13
  14     /// <summary>
  15     /// A navigator is a cursor over the nodes in a DOM, where each node is assigned a unique position.
  16     /// A node is a (navigator, position) pair.
  17     /// </summary>
  18     internal struct QueryNode
  19     {
  20         SeekableXPathNavigator node;
  21         long nodePosition;
  22
  23         /// <summary>
  24         /// Create a query node from the given navigator and its current position
  25         /// </summary>
  26         /// <param name="node"></param>
  27         internal QueryNode(SeekableXPathNavigator node)
  28         {
  29             this.node = node;
  30             this.nodePosition = node.CurrentPosition;
  31         }
  32
  33         /// <summary>
  34         /// Initialize using the given (node, position) pair
  35         /// </summary>
  36 #if NO
  37         internal QueryNode(SeekableXPathNavigator node, long nodePosition)
  38         {
  39             this.node = node;
  40             this.nodePosition = nodePosition;
  41         }
  42 #endif
  43         internal string LocalName
  44         {
  45             get
  46             {
  47                 return this.node.GetLocalName(this.nodePosition);
  48             }
  49         }
  50
  51         /// <summary>
  52         /// Return the node's name
  53         /// </summary>
  54         internal string Name
  55         {
  56             get
  57             {
  58                 return this.node.GetName(this.nodePosition);
  59             }
  60         }
  61         /// <summary>
  62         /// Return the node's namespace
  63         /// </summary>
  64         internal string Namespace
  65         {
  66             get
  67             {
  68                 return this.node.GetNamespace(this.nodePosition);
  69             }
  70         }
  71         /// <summary>
  72         /// Return this query node's underlying Node
  73         /// </summary>
  74         internal SeekableXPathNavigator Node
  75         {
  76             get
  77             {
  78                 return this.node;
  79             }
  80         }
  81         /// <summary>
  82         ///
  83         /// </summary>
  84         internal long Position
  85         {
  86             get
  87             {
  88
  89                 return this.nodePosition;
  90             }
  91         }
  92 #if NO
  93         /// <summary>
  94         /// This node's type
  95         /// </summary>
  96         internal QueryNodeType Type
  97         {
  98             get
  99             {
 100                 return QueryDataModel.GetNodeType(this.node.GetNodeType(this.nodePosition));
 101             }
 102         }
 103 #endif
 104         /// <summary>
 105         /// This node's string value
 106         /// </summary>
 107         internal string Value
 108         {
 109             get
 110             {
 111                 return this.node.GetValue(this.nodePosition);
 112             }
 113         }
 114 #if NO
 115         /// <summary>
 116         /// Raw xpath node type
 117         /// </summary>
 118         internal XPathNodeType XPathNodeType
 119         {
 120             get
 121             {
 122                 return this.node.GetNodeType(this.nodePosition);
 123             }
 124         }
 125 #endif
 126         /// <summary>
 127         /// Move this node's navigator to its position
 128         /// </summary>
 129         /// <returns></returns>
 130         internal SeekableXPathNavigator MoveTo()
 131         {
 132             this.node.CurrentPosition = this.nodePosition;
 133             return this.node;
 134         }
 135     }
 136
 137     internal enum NodeSequenceItemFlags : byte
 138     {
 139         None = 0x00,
 140         NodesetLast = 0x01,
 141     }
 142
 143     // PERF, [....], Remove when generic sort works
 144     // Used to sort in document order
 145 #if NO
 146     internal class NodeSequenceItemObjectComparer : IComparer
 147     {
 148         internal NodeSequenceItemObjectComparer()
 149         {
 150         }
 151
 152         public int Compare(object obj1, object obj2)
 153         {
 154             NodeSequenceItem item1 = (NodeSequenceItem)obj1;
 155             NodeSequenceItem item2 = (NodeSequenceItem)obj2;
 156
 157             XmlNodeOrder order = item1.Node.Node.ComparePosition(item1.Node.Position, item2.Node.Position);
 158             int ret;
 159             switch(order)
 160             {
 161                 case XmlNodeOrder.Before:
 162                     ret = -1;
 163                     break;
 164
 165                 case XmlNodeOrder.Same:
 166                     ret = 0;
 167                     break;
 168
 169                 case XmlNodeOrder.After:
 170                     ret = 1;
 171                     break;
 172
 173                 case XmlNodeOrder.Unknown:
 174                 default:
 175                     throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new XPathException(SR.GetString(SR.QueryNotSortable)), TraceEventType.Critical);
 176             }
 177
 178             return ret;
 179         }
 180     }
 181
 182     // Used to sort in document order
 183     internal class NodeSequenceItemComparer : IComparer<NodeSequenceItem>
 184     {
 185         internal NodeSequenceItemComparer()
 186         {
 187         }
 188
 189         public int Compare(NodeSequenceItem item1, NodeSequenceItem item2)
 190         {
 191             XmlNodeOrder order = item1.Node.Node.ComparePosition(item1.Node.Position, item2.Node.Position);
 192             int ret;
 193             switch(order)
 194             {
 195                 case XmlNodeOrder.Before:
 196                     ret = -1;
 197                     break;
 198
 199                 case XmlNodeOrder.Same:
 200                     ret = 0;
 201                     break;
 202
 203                 case XmlNodeOrder.After:
 204                     ret = 1;
 205                     break;
 206
 207                 case XmlNodeOrder.Unknown:
 208                 default:
 209                     throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new XPathException(SR.GetString(SR.QueryNotSortable)), TraceEventType.Critical);
 210             }
 211
 212             return ret;
 213         }
 214
 215         public bool Equals(NodeSequenceItem item1, NodeSequenceItem item2)
 216         {
 217             return Compare(item1, item2) == 0;
 218         }
 219
 220         public int GetHashCode(NodeSequenceItem item)
 221         {
 222             return item.GetHashCode();
 223         }
 224     }
 225 #endif
 226     // Used to sort in document order
 227     internal class QueryNodeComparer : IComparer<QueryNode>
 228     {
 229         public QueryNodeComparer()
 230         {
 231         }
 232
 233         public int Compare(QueryNode item1, QueryNode item2)
 234         {
 235             XmlNodeOrder order = item1.Node.ComparePosition(item1.Position, item2.Position);
 236             int ret;
 237             switch (order)
 238             {
 239                 case XmlNodeOrder.Before:
 240                     ret = -1;
 241                     break;
 242
 243                 case XmlNodeOrder.Same:
 244                     ret = 0;
 245                     break;
 246
 247                 case XmlNodeOrder.After:
 248                     ret = 1;
 249                     break;
 250
 251                 case XmlNodeOrder.Unknown:
 252                 default:
 253                     throw DiagnosticUtility.ExceptionUtility.ThrowHelperCritical(new XPathException(SR.GetString(SR.QueryNotSortable)));
 254             }
 255
 256             return ret;
 257         }
 258
 259         public bool Equals(QueryNode item1, QueryNode item2)
 260         {
 261             return Compare(item1, item2) == 0;
 262         }
 263
 264         public int GetHashCode(QueryNode item)
 265         {
 266             return item.GetHashCode();
 267         }
 268     }
 269
 270     internal struct NodeSequenceItem
 271     {
 272         NodeSequenceItemFlags flags;
 273         QueryNode node;
 274         int position;
 275         int size;
 276
 277         internal NodeSequenceItemFlags Flags
 278         {
 279             get
 280             {
 281                 return this.flags;
 282             }
 283             set
 284             {
 285                 this.flags = value;
 286             }
 287         }
 288
 289         internal bool Last
 290         {
 291             get
 292             {
 293                 return (0 != (NodeSequenceItemFlags.NodesetLast & this.flags));
 294             }
 295             set
 296             {
 297                 if (value)
 298                 {
 299                     this.flags |= NodeSequenceItemFlags.NodesetLast;
 300                 }
 301                 else
 302                 {
 303                     this.flags &= ~(NodeSequenceItemFlags.NodesetLast);
 304                 }
 305             }
 306         }
 307
 308         internal string LocalName
 309         {
 310             get
 311             {
 312                 return this.node.LocalName;
 313             }
 314         }
 315
 316         internal string Name
 317         {
 318             get
 319             {
 320                 return this.node.Name;
 321             }
 322         }
 323
 324         internal string Namespace
 325         {
 326             get
 327             {
 328                 return this.node.Namespace;
 329             }
 330         }
 331
 332         internal QueryNode Node
 333         {
 334             get
 335             {
 336                 return this.node;
 337             }
 338 #if NO
 339             set
 340             {
 341                 this.node = value;
 342             }
 343 #endif
 344         }
 345
 346         internal int Position
 347         {
 348             get
 349             {
 350                 return this.position;
 351             }
 352 #if NO
 353             set
 354             {
 355                 this.position = value;
 356             }
 357 #endif
 358         }
 359
 360         internal int Size
 361         {
 362             get
 363             {
 364                 return this.size;
 365             }
 366             set
 367             {
 368                 this.size = value;
 369             }
 370         }
 371
 372         internal bool Compare(double dblVal, RelationOperator op)
 373         {
 374             return QueryValueModel.Compare(this.NumberValue(), dblVal, op);
 375         }
 376
 377         internal bool Compare(string strVal, RelationOperator op)
 378         {
 379             return QueryValueModel.Compare(this.StringValue(), strVal, op);
 380         }
 381
 382         internal bool Compare(ref NodeSequenceItem item, RelationOperator op)
 383         {
 384             return QueryValueModel.Compare(this.StringValue(), item.StringValue(), op);
 385         }
 386
 387         internal bool Equals(string literal)
 388         {
 389             return QueryValueModel.Equals(this.StringValue(), literal);
 390         }
 391
 392         internal bool Equals(double literal)
 393         {
 394             return (this.NumberValue() == literal);
 395         }
 396
 397         internal SeekableXPathNavigator GetNavigator()
 398         {
 399             return this.node.MoveTo();
 400         }
 401
 402         internal long GetNavigatorPosition()
 403         {
 404             return this.node.Position;
 405         }
 406
 407         internal double NumberValue()
 408         {
 409             return QueryValueModel.Double(this.StringValue());
 410         }
 411
 412         internal void Set(SeekableXPathNavigator node, int position, int size)
 413         {
 414             Fx.Assert(position > 0, "");
 415             Fx.Assert(null != node, "");
 416
 417             this.node = new QueryNode(node);
 418             this.position = position;
 419             this.size = size;
 420             this.flags = NodeSequenceItemFlags.None;
 421         }
 422
 423         internal void Set(QueryNode node, int position, int size)
 424         {
 425             Fx.Assert(position > 0, "");
 426
 427             this.node = node;
 428             this.position = position;
 429             this.size = size;
 430             this.flags = NodeSequenceItemFlags.None;
 431         }
 432
 433         internal void Set(ref NodeSequenceItem item, int position, int size)
 434         {
 435             Fx.Assert(position > 0, "");
 436
 437             this.node = item.node;
 438             this.position = position;
 439             this.size = size;
 440             this.flags = item.flags;
 441         }
 442
 443         internal void SetPositionAndSize(int position, int size)
 444         {
 445             this.position = position;
 446             this.size = size;
 447             this.flags &= ~NodeSequenceItemFlags.NodesetLast;
 448         }
 449
 450         internal void SetSizeAndLast()
 451         {
 452             this.size = 1;
 453             this.flags |= NodeSequenceItemFlags.NodesetLast;
 454         }
 455
 456         // This is not optimized right now
 457         // We may want to CACHE string values once they are computed
 458         internal string StringValue()
 459         {
 460             return this.node.Value;
 461         }
 462     }
 463
 464     internal class NodeSequence
 465     {
 466 #if DEBUG
 467         // debugging aid. Because C# references do not have displayble numeric values, hard to deduce the
 468         // graph structure to see what opcode is connected to what
 469         static long nextUniqueId = 0;
 470         internal long uniqueID;
 471 #endif
 472         int count;
 473         internal static NodeSequence Empty = new NodeSequence(0);
 474         NodeSequenceItem[] items;
 475         NodeSequence next;
 476         ProcessingContext ownerContext;
 477         int position;
 478         internal int refCount;
 479         int sizePosition;
 480
 481         static readonly QueryNodeComparer staticQueryNodeComparerInstance = new QueryNodeComparer();
 482
 483         internal NodeSequence()
 484             : this(8, null)
 485         {
 486         }
 487
 488         internal NodeSequence(int capacity)
 489             : this(capacity, null)
 490         {
 491         }
 492
 493         internal NodeSequence(int capacity, ProcessingContext ownerContext)
 494         {
 495             this.items = new NodeSequenceItem[capacity];
 496             this.ownerContext = ownerContext;
 497 #if DEBUG
 498             this.uniqueID = Interlocked.Increment(ref NodeSequence.nextUniqueId);
 499 #endif
 500         }
 501
 502 #if NO
 503         internal NodeSequence(int capacity, ProcessingContext ownerContext, XPathNodeIterator iter)
 504             : this(capacity, ownerContext)
 505         {
 506             while(iter.MoveNext())
 507             {
 508                 SeekableXPathNavigator nav = iter.Current as SeekableXPathNavigator;
 509                 if(nav != null)
 510                 {
 511                     Add(nav);
 512                 }
 513                 else
 514                 {
 515                     throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new QueryProcessingException(QueryProcessingError.Unexpected, SR.GetString(SR.QueryMustBeSeekable)), TraceEventType.Critical);
 516                 }
 517             }
 518         }
 519 #endif
 520         internal int Count
 521         {
 522             get
 523             {
 524                 return this.count;
 525             }
 526 #if NO
 527             set
 528             {
 529                 Fx.Assert(value >= 0 && value <= this.count, "");
 530                 this.count = value;
 531             }
 532 #endif
 533         }
 534
 535         internal NodeSequenceItem this[int index]
 536         {
 537             get
 538             {
 539                 return this.items[index];
 540             }
 541         }
 542
 543         internal NodeSequenceItem[] Items
 544         {
 545             get
 546             {
 547                 return this.items;
 548             }
 549         }
 550
 551         internal bool IsNotEmpty
 552         {
 553             get
 554             {
 555                 return (this.count > 0);
 556             }
 557         }
 558
 559         internal string LocalName
 560         {
 561             get
 562             {
 563                 if (this.count > 0)
 564                 {
 565                     return this.items[0].LocalName;
 566                 }
 567
 568                 return string.Empty;
 569             }
 570         }
 571
 572         internal string Name
 573         {
 574             get
 575             {
 576                 if (this.count > 0)
 577                 {
 578                     return this.items[0].Name;
 579                 }
 580
 581                 return string.Empty;
 582             }
 583         }
 584
 585         internal string Namespace
 586         {
 587             get
 588             {
 589                 if (this.count > 0)
 590                 {
 591                     return this.items[0].Namespace;
 592                 }
 593
 594                 return string.Empty;
 595             }
 596         }
 597
 598         internal NodeSequence Next
 599         {
 600             get
 601             {
 602                 return this.next;
 603             }
 604             set
 605             {
 606                 this.next = value;
 607             }
 608         }
 609
 610         internal ProcessingContext OwnerContext
 611         {
 612             get
 613             {
 614                 return this.ownerContext;
 615             }
 616             set
 617             {
 618                 this.ownerContext = value;
 619             }
 620         }
 621 #if NO
 622         internal int NodesetStartAt
 623         {
 624             get
 625             {
 626                 return -this.sizePosition;
 627             }
 628         }
 629 #endif
 630         internal void Add(XPathNodeIterator iter)
 631         {
 632             while (iter.MoveNext())
 633             {
 634                 SeekableXPathNavigator nav = iter.Current as SeekableXPathNavigator;
 635                 if (nav != null)
 636                 {
 637                     this.Add(nav);
 638                 }
 639                 else
 640                 {
 641                     throw DiagnosticUtility.ExceptionUtility.ThrowHelperCritical(new QueryProcessingException(QueryProcessingError.Unexpected, SR.GetString(SR.QueryMustBeSeekable)));
 642                 }
 643             }
 644         }
 645
 646         internal void Add(SeekableXPathNavigator node)
 647         {
 648             Fx.Assert(this.items.Length > 0, "");
 649             if (this.count == this.items.Length)
 650             {
 651                 this.Grow(this.items.Length * 2);
 652             }
 653             this.position++;
 654             this.items[this.count++].Set(node, this.position, this.sizePosition);
 655         }
 656
 657         internal void Add(QueryNode node)
 658         {
 659             Fx.Assert(this.items.Length > 0, "");
 660             if (this.count == this.items.Length)
 661             {
 662                 this.Grow(this.items.Length * 2);
 663             }
 664
 665             this.position++;
 666             this.items[this.count++].Set(node, this.position, this.sizePosition);
 667         }
 668
 669         internal void Add(ref NodeSequenceItem item)
 670         {
 671             Fx.Assert(this.items.Length > 0, "");
 672             if (this.count == this.items.Length)
 673             {
 674                 this.Grow(this.items.Length * 2);
 675             }
 676
 677             this.position++;
 678             this.items[this.count++].Set(ref item, this.position, this.sizePosition);
 679         }
 680
 681         internal void AddCopy(ref NodeSequenceItem item, int size)
 682         {
 683             Fx.Assert(this.items.Length > 0, "");
 684             if (this.count == this.items.Length)
 685             {
 686                 this.Grow(this.items.Length * 2);
 687             }
 688
 689             this.items[this.count] = item;
 690             this.items[this.count++].Size = size;
 691         }
 692
 693         internal void AddCopy(ref NodeSequenceItem item)
 694         {
 695             Fx.Assert(this.items.Length > 0, "");
 696             if (this.count == this.items.Length)
 697             {
 698                 this.Grow(this.items.Length * 2);
 699             }
 700
 701             this.items[this.count++] = item;
 702         }
 703 #if NO
 704         internal void Add(NodeSequence seq)
 705         {
 706             int newCount = this.count + seq.count;
 707             if (newCount > this.items.Length)
 708             {
 709                 // We are going to need room. Grow the array
 710                 int growTo = this.items.Length * 2;
 711                 this.Grow(newCount > growTo ? newCount : growTo);
 712             }
 713             Array.Copy(seq.items, 0, this.items, this.count, seq.count);
 714             this.count += seq.count;
 715         }
 716 #endif
 717         internal bool CanReuse(ProcessingContext context)
 718         {
 719             return (this.count == 1 && this.ownerContext == context && this.refCount == 1);
 720         }
 721
 722         internal void Clear()
 723         {
 724             this.count = 0;
 725         }
 726
 727         internal void Reset(NodeSequence nextSeq)
 728         {
 729             this.count = 0;
 730             this.refCount = 0;
 731             this.next = nextSeq;
 732         }
 733
 734         internal bool Compare(double val, RelationOperator op)
 735         {
 736             for (int i = 0; i < this.count; ++i)
 737             {
 738                 if (this.items[i].Compare(val, op))
 739                 {
 740                     return true;
 741                 }
 742             }
 743             return false;
 744         }
 745
 746         internal bool Compare(string val, RelationOperator op)
 747         {
 748             Fx.Assert(null != val, "");
 749             for (int i = 0; i < this.count; ++i)
 750             {
 751                 if (this.items[i].Compare(val, op))
 752                 {
 753                     return true;
 754                 }
 755             }
 756             return false;
 757         }
 758
 759         internal bool Compare(ref NodeSequenceItem item, RelationOperator op)
 760         {
 761             for (int i = 0; i < this.count; ++i)
 762             {
 763                 if (this.items[i].Compare(ref item, op))
 764                 {
 765                     return true;
 766                 }
 767             }
 768             return false;
 769         }
 770
 771         internal bool Compare(NodeSequence sequence, RelationOperator op)
 772         {
 773             Fx.Assert(null != sequence, "");
 774             for (int i = 0; i < sequence.count; ++i)
 775             {
 776                 if (this.Compare(ref sequence.items[i], op))
 777                 {
 778                     return true;
 779                 }
 780             }
 781             return false;
 782         }
 783 #if NO
 784         void EnsureCapacity()
 785         {
 786             if (this.count == this.items.Length)
 787             {
 788                 this.Grow(this.items.Length * 2);
 789             }
 790         }
 791
 792         void EnsureCapacity(int capacity)
 793         {
 794             if (capacity > this.items.Length)
 795             {
 796                 int newSize = this.items.Length * 2;
 797                 this.Grow(newSize > capacity ? newSize : capacity);
 798             }
 799         }
 800 #endif
 801         internal bool Equals(string val)
 802         {
 803             Fx.Assert(null != val, "");
 804             for (int i = 0; i < this.count; ++i)
 805             {
 806                 if (this.items[i].Equals(val))
 807                 {
 808                     return true;
 809                 }
 810             }
 811             return false;
 812         }
 813
 814         internal bool Equals(double val)
 815         {
 816             for (int i = 0; i < this.count; ++i)
 817             {
 818                 if (this.items[i].Equals(val))
 819                 {
 820                     return true;
 821                 }
 822             }
 823             return false;
 824         }
 825
 826         internal static int GetContextSize(NodeSequence sequence, int itemIndex)
 827         {
 828             Fx.Assert(null != sequence, "");
 829             int size = sequence.items[itemIndex].Size;
 830             if (size <= 0)
 831             {
 832                 return sequence.items[-size].Size;
 833             }
 834             return size;
 835         }
 836
 837         void Grow(int newSize)
 838         {
 839             NodeSequenceItem[] newItems = new NodeSequenceItem[newSize];
 840             if (this.items != null)
 841             {
 842                 Array.Copy(this.items, newItems, this.items.Length);
 843             }
 844             this.items = newItems;
 845         }
 846
 847         /// <summary>
 848         /// Merge all nodesets in this sequence... turning it into a sequence with a single nodeset
 849         /// This is done by simply renumbering all positions.. and clearing the nodeset flag
 850         /// </summary>
 851         internal void Merge()
 852         {
 853             Merge(true);
 854         }
 855
 856         internal void Merge(bool renumber)
 857         {
 858             if (this.count == 0)
 859             {
 860                 return;
 861             }
 862
 863             if (renumber)
 864             {
 865                 RenumberItems();
 866             }
 867         }
 868 #if NO
 869         // Assumes list is flat and sorted
 870         internal void RemoveDuplicates()
 871         {
 872             if(this.count < 2)
 873             {
 874                 return;
 875             }
 876
 877             int last = 0;
 878             for(int next = 1; next < this.count; ++next)
 879             {
 880                 if(Comparer.Compare(this.items[last], this.items[next]) != 0)
 881                 {
 882                     ++last;
 883                     if(last != next)
 884                     {
 885                         this.items[last] = this.items[next];
 886                     }
 887                 }
 888             }
 889
 890             this.count = last + 1;
 891
 892             RenumberItems();
 893         }
 894 #endif
 895         void RenumberItems()
 896         {
 897             if (this.count > 0)
 898             {
 899                 for (int i = 0; i < this.count; ++i)
 900                 {
 901                     this.items[i].SetPositionAndSize(i + 1, this.count);
 902                 }
 903                 this.items[this.count - 1].Flags |= NodeSequenceItemFlags.NodesetLast;
 904             }
 905         }
 906 #if NO
 907         internal void SortNodes()
 908         {
 909             this.Merge(false);
 910
 911             // PERF, [....], make this work
 912             //Array.Sort<NodeSequenceItem>(this.items, 0, this.count, NodeSequence.Comparer);
 913             Array.Sort(this.items, 0, this.count, NodeSequence.ObjectComparer);
 914
 915             RenumberItems();
 916         }
 917 #endif
 918         internal void StartNodeset()
 919         {
 920             this.position = 0;
 921             this.sizePosition = -this.count;
 922         }
 923
 924         internal void StopNodeset()
 925         {
 926             switch (this.position)
 927             {
 928                 default:
 929                     int sizePos = -this.sizePosition;
 930                     this.items[sizePos].Size = this.position;
 931                     this.items[sizePos + this.position - 1].Last = true;
 932                     break;
 933
 934                 case 0:
 935                     break;
 936
 937                 case 1:
 938                     this.items[-this.sizePosition].SetSizeAndLast();
 939                     break;
 940             }
 941         }
 942
 943         internal string StringValue()
 944         {
 945             if (this.count > 0)
 946             {
 947                 return this.items[0].StringValue();
 948             }
 949
 950             return string.Empty;
 951         }
 952
 953         /// <summary>
 954         /// Union algorithm:
 955         /// 1. Add both sequences of items to a newly created sequence
 956         /// 2. Sort the items based on document position
 957         /// 3. Renumber positions in this new unionized sequence
 958         /// </summary>
 959         internal NodeSequence Union(ProcessingContext context, NodeSequence otherSeq)
 960         {
 961             NodeSequence seq = context.CreateSequence();
 962
 963             SortedBuffer<QueryNode, QueryNodeComparer> buff = new SortedBuffer<QueryNode, QueryNodeComparer>(staticQueryNodeComparerInstance);
 964             for (int i = 0; i < this.count; ++i)
 965                 buff.Add(this.items[i].Node);
 966
 967             for (int i = 0; i < otherSeq.count; ++i)
 968                 buff.Add(otherSeq.items[i].Node);
 969
 970             for (int i = 0; i < buff.Count; ++i)
 971                 seq.Add(buff[i]);
 972
 973             seq.RenumberItems();
 974             return seq;
 975
 976             /*
 977             // PERF, [....], I think we can do the merge ourselves and avoid the sort.
 978             //               Need to verify that the sequences are always in document order.
 979             for(int i = 0; i < this.count; ++i)
 980             {
 981                 seq.AddCopy(ref this.items[i]);
 982             }
 983
 984             for(int i = 0; i < otherSeq.count; ++i)
 985             {
 986                 seq.AddCopy(ref otherSeq.items[i]);
 987             }
 988
 989             seq.SortNodes();
 990             seq.RemoveDuplicates();
 991
 992             return seq;
 993             */
 994         }
 995
 996         #region IQueryBufferPool Members
 997 #if NO
 998         public void Reset()
 999         {
1000             this.count = 0;
1001             this.Trim();
1002         }
1003
1004         public void Trim()
1005         {
1006             if (this.count == 0)
1007             {
1008                 this.items = null;
1009             }
1010             else if (this.count < this.items.Length)
1011             {
1012                 NodeSequenceItem[] newItems = new NodeSequenceItem[this.count];
1013                 Array.Copy(this.items, newItems, this.count);
1014                 this.items = newItems;
1015             }
1016         }
1017 #endif
1018         #endregion
1019     }
1020
1021     internal class NodeSequenceIterator : XPathNodeIterator
1022     {
1023         // Shared
1024         NodeSequence seq;
1025
1026         // Instance
1027         NodeSequenceIterator data;
1028         int index;
1029         SeekableXPathNavigator nav; // the navigator that will be used by this iterator
1030
1031         internal NodeSequenceIterator(NodeSequence seq)
1032             : base()
1033         {
1034             this.data = this;
1035             this.seq = seq;
1036         }
1037
1038         internal NodeSequenceIterator(NodeSequenceIterator iter)
1039         {
1040             this.data = iter.data;
1041             this.index = iter.index;
1042         }
1043
1044         public override int Count
1045         {
1046             get
1047             {
1048                 return this.data.seq.Count;
1049             }
1050         }
1051
1052         public override XPathNavigator Current
1053         {
1054             get
1055             {
1056                 if (this.index == 0)
1057                 {
1058 #pragma warning suppress 56503 // [....], postponing the public change
1059                     throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new QueryProcessingException(QueryProcessingError.Unexpected, SR.GetString(SR.QueryContextNotSupportedInSequences)));
1060                 }
1061
1062                 if (this.index > this.data.seq.Count)
1063                 {
1064 #pragma warning suppress 56503 // [....], postponing the public change
1065                     throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.GetString(SR.QueryAfterNodes)));
1066                 }
1067                 //
1068                 // From MSDN - the public contract of .Current
1069                 // You can use the properties of the XPathNavigator to return information on the current node.
1070                 // However, the XPathNavigator cannot be used to move away from the selected node set.
1071                 // Doing so could invalidate the state of the navigator. Alternatively, you can clone the XPathNavigator.
1072                 // The cloned XPathNavigator can then be moved away from the selected node set. This is an application level decision.
1073                 // Providing this functionality may effect the performance of the XPath query.
1074                 //
1075                 // Return the navigator as is - where it is positioned. If the user moved the navigator, then the user is
1076                 // hosed. We will make no guarantees - and are not required to. Doing so would force cloning, which is expensive.
1077                 //
1078                 // NOTE: .Current can get called repeatedly, so its activity should be relative CHEAP.
1079                 // No cloning, copying etc. All that work should be done in MoveNext()
1080                 return this.nav;
1081             }
1082         }
1083
1084         public override int CurrentPosition
1085         {
1086             get
1087             {
1088                 return this.index;
1089             }
1090         }
1091
1092         internal void Clear()
1093         {
1094             this.data.seq = null;
1095             this.nav = null;
1096         }
1097
1098         public override XPathNodeIterator Clone()
1099         {
1100             return new NodeSequenceIterator(this);
1101         }
1102
1103         public override IEnumerator GetEnumerator()
1104         {
1105             return new NodeSequenceEnumerator(this);
1106         }
1107
1108         public override bool MoveNext()
1109         {
1110             if (null == this.data.seq)
1111             {
1112                 // User is trying to use an iterator that is  out of scope.
1113                 throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.GetString(SR.QueryIteratorOutOfScope)));
1114             }
1115
1116             if (this.index < this.data.seq.Count)
1117             {
1118                 if (null == this.nav)
1119                 {
1120                     // We haven't aquired the navigator we will use for this iterator yet.
1121                     this.nav = (SeekableXPathNavigator)this.data.seq[this.index].GetNavigator().Clone();
1122                 }
1123                 else
1124                 {
1125                     this.nav.CurrentPosition = this.data.seq[this.index].GetNavigatorPosition();
1126                 }
1127                 this.index++;
1128                 return true;
1129             }
1130
1131             this.index++;
1132             this.nav = null;
1133             return false;
1134         }
1135
1136         public void Reset()
1137         {
1138             this.nav = null;
1139             this.index = 0;
1140         }
1141     }
1142
1143     internal class NodeSequenceEnumerator : IEnumerator
1144     {
1145         NodeSequenceIterator iter;
1146
1147         internal NodeSequenceEnumerator(NodeSequenceIterator iter)
1148         {
1149             this.iter = new NodeSequenceIterator(iter);
1150             Reset();
1151         }
1152
1153         public object Current
1154         {
1155             get
1156             {
1157                 if (this.iter.CurrentPosition == 0)
1158                 {
1159 #pragma warning suppress 56503 // [....], postponing the public change
1160                     throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.GetString(SR.QueryBeforeNodes)));
1161                 }
1162
1163                 if (this.iter.CurrentPosition > this.iter.Count)
1164                 {
1165 #pragma warning suppress 56503 // [....], postponing the public change
1166                     throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.GetString(SR.QueryAfterNodes)));
1167                 }
1168
1169                 return this.iter.Current;
1170             }
1171         }
1172
1173         public bool MoveNext()
1174         {
1175             return iter.MoveNext();
1176         }
1177
1178         public void Reset()
1179         {
1180             this.iter.Reset();
1181         }
1182     }
1183
1184     internal class SafeNodeSequenceIterator : NodeSequenceIterator, IDisposable
1185     {
1186         ProcessingContext context;
1187         int disposed;
1188         NodeSequence seq;
1189
1190         public SafeNodeSequenceIterator(NodeSequence seq, ProcessingContext context)
1191             : base(seq)
1192         {
1193             this.context = context;
1194             this.seq = seq;
1195             Interlocked.Increment(ref this.seq.refCount);
1196             this.context.Processor.AddRef();
1197         }
1198
1199         public override XPathNodeIterator Clone()
1200         {
1201             return new SafeNodeSequenceIterator(this.seq, this.context);
1202         }
1203
1204         public void Dispose()
1205         {
1206             if (Interlocked.CompareExchange(ref this.disposed, 1, 0) == 0)
1207             {
1208                 QueryProcessor processor = this.context.Processor;
1209                 this.context.ReleaseSequence(this.seq);
1210                 this.context.Processor.Matcher.ReleaseProcessor(processor);
1211             }
1212         }
1213     }
1214
1215     internal struct NodesetIterator
1216     {
1217         int index;
1218         int indexStart;
1219         NodeSequence sequence;
1220         NodeSequenceItem[] items;
1221
1222         internal NodesetIterator(NodeSequence sequence)
1223         {
1224             Fx.Assert(null != sequence, "");
1225             this.sequence = sequence;
1226             this.items = sequence.Items;
1227             this.index = -1;
1228             this.indexStart = -1;
1229         }
1230
1231         internal int Index
1232         {
1233             get
1234             {
1235                 return this.index;
1236             }
1237         }
1238
1239         internal bool NextItem()
1240         {
1241             if (-1 == this.index)
1242             {
1243                 this.index = this.indexStart;
1244                 return true;
1245             }
1246
1247             if (this.items[this.index].Last)
1248             {
1249                 return false;
1250             }
1251
1252             this.index++;
1253             return true;
1254         }
1255
1256         internal bool NextNodeset()
1257         {
1258             this.indexStart = this.index + 1;
1259             this.index = -1;
1260             return (this.indexStart < this.sequence.Count);
1261         }
1262     }
1263
1264     internal struct NodeSequenceBuilder
1265     {
1266         ProcessingContext context;
1267         NodeSequence sequence;
1268
1269         internal NodeSequenceBuilder(ProcessingContext context, NodeSequence sequence)
1270         {
1271             this.context = context;
1272             this.sequence = sequence;
1273         }
1274
1275         internal NodeSequenceBuilder(ProcessingContext context)
1276             : this(context, null)
1277         {
1278         }
1279 #if NO
1280         internal NodeSequenceBuilder(NodeSequence sequence)
1281             : this(sequence.OwnerContext, sequence)
1282         {
1283         }
1284 #endif
1285         internal NodeSequence Sequence
1286         {
1287             get
1288             {
1289                 return (null != this.sequence) ? this.sequence : NodeSequence.Empty;
1290             }
1291             set
1292             {
1293                 this.sequence = value;
1294             }
1295         }
1296
1297         internal void Add(ref NodeSequenceItem item)
1298         {
1299             if (null == this.sequence)
1300             {
1301                 this.sequence = this.context.CreateSequence();
1302                 this.sequence.StartNodeset();
1303             }
1304
1305             this.sequence.Add(ref item);
1306         }
1307
1308         internal void EndNodeset()
1309         {
1310             if (null != this.sequence)
1311             {
1312                 this.sequence.StopNodeset();
1313             }
1314         }
1315
1316         internal void StartNodeset()
1317         {
1318             if (null != this.sequence)
1319             {
1320                 this.sequence.StartNodeset();
1321             }
1322         }
1323     }
1324 }