1 // Licensed to the .NET Foundation under one or more agreements. 2 // The .NET Foundation licenses this file to you under the MIT license. 3 // See the LICENSE file in the project root for more information. 4 5 using System; 6 using System.Collections; 7 using System.Collections.Generic; 8 using System.Xml; 9 using System.Xml.XPath; 10 using System.Diagnostics; 11 12 namespace System.Xml.Xsl.Runtime 13 { 14 /// <summary> 15 /// IComparer implementation that orders navigators based on ComparePosition. When ComparePosition returns 16 /// XmlNodeOrder.Unknown, a stable order between documents is maintained by an ordered list mapping each root node 17 /// to an ordering index. 18 /// </summary> 19 internal class DocumentOrderComparer : IComparer<XPathNavigator> 20 { 21 private List<XPathNavigator> _roots; 22 23 /// <summary> 24 /// Return: 25 /// -1 if navThis is positioned before navThat 26 /// 0 if navThis has the same position as navThat 27 /// 1 if navThis is positioned after navThat 28 /// </summary> Compare(XPathNavigator navThis, XPathNavigator navThat)29 public int Compare(XPathNavigator navThis, XPathNavigator navThat) 30 { 31 switch (navThis.ComparePosition(navThat)) 32 { 33 case XmlNodeOrder.Before: return -1; 34 case XmlNodeOrder.Same: return 0; 35 case XmlNodeOrder.After: return 1; 36 } 37 38 // Use this.roots to impose stable ordering 39 if (_roots == null) 40 _roots = new List<XPathNavigator>(); 41 42 Debug.Assert(GetDocumentIndex(navThis) != GetDocumentIndex(navThat)); 43 return GetDocumentIndex(navThis) < GetDocumentIndex(navThat) ? -1 : 1; 44 } 45 46 /// <summary> 47 /// Map navigator's document to a unique index. 48 /// When consecutive calls are made to GetIndexOfNavigator for navThis and navThat, it is not possible 49 /// for them to return the same index. navThis compared to navThat is always XmlNodeOrder.Unknown. 50 /// Therefore, no matter where navThis is inserted in the list, navThat will never be inserted just 51 /// before navThis, and therefore will never have the same index. 52 /// </summary> GetDocumentIndex(XPathNavigator nav)53 public int GetDocumentIndex(XPathNavigator nav) 54 { 55 XPathNavigator navRoot; 56 57 // Use this.roots to impose stable ordering 58 if (_roots == null) 59 _roots = new List<XPathNavigator>(); 60 61 // Position navigator to root 62 navRoot = nav.Clone(); 63 navRoot.MoveToRoot(); 64 65 for (int idx = 0; idx < _roots.Count; idx++) 66 { 67 if (navRoot.IsSamePosition(_roots[idx])) 68 { 69 // navigator's document was previously mapped to a unique index 70 return idx; 71 } 72 } 73 74 // Add navigator to this.roots mapping 75 _roots.Add(navRoot); 76 77 return _roots.Count - 1; 78 } 79 } 80 } 81