mcs/class/referencesource/System.Xml/System/Xml/XPath/Internal/Query.cs

   1 //------------------------------------------------------------------------------
   2 // <copyright file="Query.cs" company="Microsoft">
   3 //     Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 // <owner current="true" primary="true">[....]</owner>
   6 //------------------------------------------------------------------------------
   7
   8 namespace MS.Internal.Xml.XPath {
   9     using System;
  10     using System.Xml;
  11     using System.Xml.XPath;
  12     using System.Xml.Xsl;
  13     using System.Diagnostics;
  14     using System.Collections.Generic;
  15
  16     // See comments to QueryBuilder.Props
  17     // Not all of them are used currently
  18     internal enum QueryProps {
  19         None     = 0x00,
  20         Position = 0x01,
  21         Count    = 0x02,
  22         Cached   = 0x04,
  23         Reverse  = 0x08,
  24         Merge    = 0x10,
  25     };
  26
  27
  28     // Turn off DebuggerDisplayAttribute. in subclasses of Query.
  29     // Calls to Current in the XPathNavigator.DebuggerDisplayProxy may change state or throw
  30     [DebuggerDisplay("{ToString()}")]
  31     internal abstract class Query : ResetableIterator {
  32         public Query() { }
  33         protected Query(Query other) : base(other) { }
  34
  35         // -- XPathNodeIterator --
  36         //public abstract XPathNodeIterator Clone();
  37         //public abstract XPathNavigator Current { get; }
  38         //public abstract int CurrentPosition { get; }
  39         public override bool MoveNext() { return Advance() != null; }
  40         public override int Count {
  41             get {
  42                 // Query can be ordered in reverse order. So we can't assume like base.Count that last node has greatest position.
  43                 if (count == -1) {
  44                     Query clone = (Query)this.Clone();
  45                     clone.Reset();
  46                     count = 0;
  47                     while (clone.MoveNext()) count ++;
  48                 }
  49                 return count;
  50             }
  51         }
  52
  53         // ------------- ResetableIterator -----------
  54         // It's importent that Query is resetable. This fact is used in several plases:
  55         // 1. In LogicalExpr: "foo = bar"
  56         // 2. In SelectionOperator.Reset().
  57         // In all this cases Reset() means restart iterate through the same nodes.
  58         // So reset shouldn't clean bufferes in query. This should be done in set context.
  59         //public abstract void Reset();
  60
  61         // -------------------- Query ------------------
  62         public virtual void SetXsltContext(XsltContext context) { }
  63
  64         public abstract object Evaluate(XPathNodeIterator nodeIterator);
  65         public abstract XPathNavigator Advance();
  66
  67         public virtual  XPathNavigator MatchNode(XPathNavigator current) {
  68             throw XPathException.Create(Res.Xp_InvalidPattern);
  69         }
  70
  71         public virtual double XsltDefaultPriority { get { return 0.5; } }
  72         public abstract XPathResultType StaticType { get; }
  73         public virtual QueryProps Properties { get { return QueryProps.Merge; } }
  74
  75         // ----------------- Helper methods -------------
  76         public static Query Clone(Query input) {
  77             if (input != null) {
  78                 return (Query)input.Clone();
  79             }
  80             return null;
  81         }
  82
  83         protected static XPathNodeIterator Clone(XPathNodeIterator input) {
  84             if (input != null) {
  85                 return input.Clone();
  86             }
  87             return null;
  88         }
  89
  90         protected static XPathNavigator Clone(XPathNavigator input) {
  91             if (input != null) {
  92                 return input.Clone();
  93             }
  94             return null;
  95         }
  96
  97         // -----------------------------------------------------
  98         // Set of methods to support insertion to sorted buffer.
  99         // buffer is always sorted here
 100
 101         public bool Insert(List<XPathNavigator> buffer, XPathNavigator nav) {
 102             int l = 0;
 103             int r = buffer.Count;
 104
 105             // In most cases nodes are already sorted.
 106             // This means that nav often will be equal or after then last item in the buffer
 107             // So let's check this first.
 108             if (r != 0) {
 109                 switch (CompareNodes(buffer[r - 1], nav)) {
 110                 case XmlNodeOrder.Same:
 111                     return false;
 112                 case XmlNodeOrder.Before:
 113                     buffer.Add(nav.Clone());
 114                     return true;
 115                 default:
 116                     r --;
 117                     break;
 118                 }
 119             }
 120
 121             while (l < r) {
 122                 int m = GetMedian(l, r);
 123                 switch (CompareNodes(buffer[m], nav)) {
 124                 case XmlNodeOrder.Same:
 125                     return false;
 126                 case XmlNodeOrder.Before:
 127                     l = m + 1;
 128                     break;
 129                 default:
 130                     r = m;
 131                     break;
 132                 }
 133             }
 134             AssertDOD(buffer, nav, l);
 135             buffer.Insert(l, nav.Clone());
 136             return true;
 137         }
 138
 139         private static int GetMedian(int l, int r) {
 140             Debug.Assert(0 <= l && l < r);
 141             return (int) (((uint) l + (uint) r) >> 1);
 142         }
 143
 144         public static XmlNodeOrder CompareNodes(XPathNavigator l, XPathNavigator r) {
 145             XmlNodeOrder cmp = l.ComparePosition(r);
 146             if (cmp == XmlNodeOrder.Unknown) {
 147                 XPathNavigator copy = l.Clone();
 148                 copy.MoveToRoot();
 149                 string baseUriL = copy.BaseURI;
 150                 if (! copy.MoveTo(r)) {
 151                     copy = r.Clone();
 152                 }
 153                 copy.MoveToRoot();
 154                 string baseUriR = copy.BaseURI;
 155                 int cmpBase = string.CompareOrdinal(baseUriL, baseUriR);
 156                 cmp = (
 157                     cmpBase < 0 ? XmlNodeOrder.Before :
 158                     cmpBase > 0 ? XmlNodeOrder.After  :
 159                     /*default*/   XmlNodeOrder.Unknown
 160                 );
 161             }
 162             return cmp;
 163         }
 164
 165         [Conditional("DEBUG")]
 166         private void AssertDOD(List<XPathNavigator> buffer, XPathNavigator nav, int pos) {
 167             if (nav.GetType().ToString() == "Microsoft.VisualStudio.Modeling.StoreNavigator") return;
 168             if (nav.GetType().ToString() == "System.Xml.DataDocumentXPathNavigator") return;
 169             Debug.Assert(0 <= pos && pos <= buffer.Count, "Algorithm error: Insert()");
 170             XmlNodeOrder cmp;
 171             if (0 < pos) {
 172                 cmp = CompareNodes(buffer[pos - 1], nav);
 173                 Debug.Assert(cmp == XmlNodeOrder.Before, "Algorithm error: Insert()");
 174             }
 175             if (pos < buffer.Count) {
 176                 cmp = CompareNodes(nav, buffer[pos]);
 177                 Debug.Assert(cmp == XmlNodeOrder.Before, "Algorithm error: Insert()");
 178             }
 179         }
 180
 181         [Conditional("DEBUG")]
 182         public static void AssertQuery(Query query) {
 183             Debug.Assert(query != null, "AssertQuery(): query == null");
 184             if (query is FunctionQuery) return; // Temp Fix. Functions (as document()) return now unordered sequences
 185             query = Clone(query);
 186             XPathNavigator last = null;
 187             XPathNavigator curr;
 188             int querySize = query.Clone().Count;
 189             int actualSize = 0;
 190             while ((curr = query.Advance()) != null) {
 191                 if (curr.GetType().ToString() == "Microsoft.VisualStudio.Modeling.StoreNavigator") return;
 192                 if (curr.GetType().ToString() == "System.Xml.DataDocumentXPathNavigator") return;
 193                 Debug.Assert(curr == query.Current, "AssertQuery(): query.Advance() != query.Current");
 194                 if (last != null) {
 195                     if (last.NodeType == XPathNodeType.Namespace && curr.NodeType == XPathNodeType.Namespace) {
 196                         // NamespaceQuery reports namsespaces in mixed order.
 197                         // Ignore this for now.
 198                         // It seams that this doesn't breake other queries becasue NS can't have children
 199                     } else {
 200                         XmlNodeOrder cmp = CompareNodes(last, curr);
 201                         Debug.Assert(cmp == XmlNodeOrder.Before, "AssertQuery(): Wrong node order");
 202                     }
 203                 }
 204                 last = curr.Clone();
 205                 actualSize++;
 206             }
 207             Debug.Assert(actualSize == querySize, "AssertQuery(): actualSize != querySize");
 208         }
 209
 210         // =================== XPathResultType_Navigator ======================
 211         // In v.1.0 and v.1.1 XPathResultType.Navigator is defined == to XPathResultType.String
 212         // This is source for multiple bugs or additional type casts.
 213         // To fix all of them in one change in v.2 we internaly use one more value:
 214         public const XPathResultType XPathResultType_Navigator = (XPathResultType) 4;
 215         // The biggest challenge in this change is preserve backward compatibility with v.1.1
 216         // To achive this in all places where we accept from or report to user XPathResultType.
 217         // On my best knowledge this happens only in XsltContext.ResolveFunction() / IXsltContextFunction.ReturnType
 218
 219
 220         protected XPathResultType GetXPathType(object value) {
 221             if (value is XPathNodeIterator) return XPathResultType.NodeSet;
 222             if (value is string           ) return XPathResultType.String;
 223             if (value is double           ) return XPathResultType.Number;
 224             if (value is bool             ) return XPathResultType.Boolean;
 225             Debug.Assert(value is XPathNavigator, "Unknown value type");
 226             return XPathResultType_Navigator;
 227         }
 228
 229         // =================== Serialization ======================
 230         public virtual void PrintQuery(XmlWriter w) {
 231             w.WriteElementString(this.GetType().Name, string.Empty);
 232         }
 233     }
 234 }