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