mcs/class/referencesource/System.Data.SqlXml/System/Xml/Xsl/IlGen/OptimizerPatterns.cs

   1 //------------------------------------------------------------------------------
   2 // <copyright file="OptimizerPatterns.cs" company="Microsoft">
   3 //     Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 // <owner current="true" primary="true">Microsoft</owner>
   6 //------------------------------------------------------------------------------
   7 using System;
   8 using System.Diagnostics;
   9 using System.Xml.Xsl.Qil;
  10
  11 namespace System.Xml.Xsl.IlGen {
  12
  13     internal enum OptimizerPatternName {
  14         None,
  15         DodReverse,                         // (Dod $reverse-axis:*)
  16         EqualityIndex,                      // ILGen will build an equality index when this pattern is recognized
  17         FilterAttributeKind,                // (Filter $iter:(Content *) (IsType $iter Attribute))
  18         FilterContentKind,                  // (Filter $iter:* (IsType $iter $kind:*))
  19         FilterElements,                     // (Filter $iter:* (And (IsType $iter Element) (NameOf $iter (LiteralQName * * *))))
  20         IsDocOrderDistinct,                 // True if the annotated expression always returns nodes in document order, with no duplicates
  21         IsPositional,                       // True if the annotated iterator should track current position during iteration
  22         JoinAndDod,                         // (Dod (Loop $path1:* $path2:*)), where $path2.ContextNode = $path1
  23         MaxPosition,                        // True if the position range of the annoted iterator or length expression has a maximum
  24         SameDepth,                          // True if the annotated expression always returns nodes at the same depth in the tree
  25         Step,                               // True if the annotated expression returns nodes from one of the simple axis operators, or from a union of Content operators
  26         SingleTextRtf,                      // (RtfCtor (TextCtor *) *)
  27         Axis,                               // (AnyAxis *)
  28         MaybeSideEffects,                   // True if annotated expression might have side effects
  29         TailCall,                           // (Invoke * *) True if invocation can be compiled as using .tailcall
  30         DodMerge,                           // (Dod (Loop * (Invoke * *))), where invoked function returns nodes in document order
  31         IsReferenced,                       // True if the annotated global iterator is referenced at least once
  32     }
  33
  34     internal enum OptimizerPatternArgument {
  35         StepNode = 0,                       // Step, QilNode: The QilNode of the inner step expression (Content, DescendantOrSelf, XPathFollowing, Union, etc.)
  36         StepInput = 1,                      // Step, QilNode: The expression from which navigation begins
  37
  38         ElementQName = 2,                   // FilterElements, QilLiteral: All but elements of this QName are filtered by FilterElements expression
  39
  40         KindTestType = 2,                   // FilterContentKind, XmlType: All but nodes of this XmlType are filtered by FilterContentKind expression
  41
  42         IndexedNodes = 0,                   // EqualityIndex, QilNode: Expression that returns the nodes to be indexed
  43         KeyExpression = 1,                  // EqualityIndex, QilNode: Expression that returns the keys for the index
  44
  45         DodStep = 2,                        // JoinAndDod | DodReverse, QilNode: Last step in a JoinAndDod expression, or only step in DodReverse expression
  46
  47         MaxPosition = 2,                    // MaxPosition, int: Maximum position of the annotated iterator or length expression
  48
  49         RtfText = 2,                        // SingleTextRtf, QilNode: Expression that constructs the text of the simple text Rtf
  50     }
  51
  52     /// <summary>
  53     /// As the Qil graph is traversed, patterns are identified.  Subtrees that match these patterns are
  54     /// annotated with this class, which identifies the matching patterns and their arguments.
  55     /// </summary>
  56     internal class OptimizerPatterns : IQilAnnotation {
  57         private static readonly int PatternCount = Enum.GetValues(typeof(OptimizerPatternName)).Length;
  58
  59         private int patterns;               // Set of patterns that the annotated Qil node and its subtree matches
  60         private bool isReadOnly;            // True if setters are disabled in the case of singleton OptimizerPatterns
  61         private object arg0, arg1, arg2;    // Arguments to the matching patterns
  62
  63         private static volatile OptimizerPatterns ZeroOrOneDefault;
  64         private static volatile OptimizerPatterns MaybeManyDefault;
  65         private static volatile OptimizerPatterns DodDefault;
  66
  67         /// <summary>
  68         /// Get OptimizerPatterns annotation for the specified node.  Lazily create if necessary.
  69         /// </summary>
  70         public static OptimizerPatterns Read(QilNode nd) {
  71             XmlILAnnotation ann = nd.Annotation as XmlILAnnotation;
  72             OptimizerPatterns optPatt = (ann != null) ? ann.Patterns : null;
  73
  74             if (optPatt == null) {
  75                 if (!nd.XmlType.MaybeMany) {
  76                     // Expressions with ZeroOrOne cardinality should always report IsDocOrderDistinct and NoContainedNodes
  77                     if (ZeroOrOneDefault == null) {
  78                         optPatt = new OptimizerPatterns();
  79                         optPatt.AddPattern(OptimizerPatternName.IsDocOrderDistinct);
  80                         optPatt.AddPattern(OptimizerPatternName.SameDepth);
  81                         optPatt.isReadOnly = true;
  82
  83                         ZeroOrOneDefault = optPatt;
  84                     }
  85                     else {
  86                         optPatt = ZeroOrOneDefault;
  87                     }
  88                 }
  89                 else if (nd.XmlType.IsDod) {
  90                     if (DodDefault == null) {
  91                         optPatt = new OptimizerPatterns();
  92                         optPatt.AddPattern(OptimizerPatternName.IsDocOrderDistinct);
  93                         optPatt.isReadOnly = true;
  94
  95                         DodDefault = optPatt;
  96                     }
  97                     else {
  98                         optPatt = DodDefault;
  99                     }
 100                 }
 101                 else {
 102                     if (MaybeManyDefault == null) {
 103                         optPatt = new OptimizerPatterns();
 104                         optPatt.isReadOnly = true;
 105
 106                         MaybeManyDefault = optPatt;
 107                     }
 108                     else {
 109                         optPatt = MaybeManyDefault;
 110                     }
 111                 }
 112             }
 113
 114             return optPatt;
 115         }
 116
 117         /// <summary>
 118         /// Create and initialize OptimizerPatterns annotation for the specified node.
 119         /// </summary>
 120         public static OptimizerPatterns Write(QilNode nd) {
 121             XmlILAnnotation ann = XmlILAnnotation.Write(nd);
 122             OptimizerPatterns optPatt = ann.Patterns;
 123
 124             if (optPatt == null || optPatt.isReadOnly) {
 125                 optPatt = new OptimizerPatterns();
 126                 ann.Patterns = optPatt;
 127
 128                 if (!nd.XmlType.MaybeMany) {
 129                     optPatt.AddPattern(OptimizerPatternName.IsDocOrderDistinct);
 130                     optPatt.AddPattern(OptimizerPatternName.SameDepth);
 131                 }
 132                 else if (nd.XmlType.IsDod) {
 133                     optPatt.AddPattern(OptimizerPatternName.IsDocOrderDistinct);
 134                 }
 135             }
 136
 137             return optPatt;
 138         }
 139
 140         /// <summary>
 141         /// Create and initialize OptimizerPatterns annotation for the specified node.
 142         /// </summary>
 143         public static void Inherit(QilNode ndSrc, QilNode ndDst, OptimizerPatternName pattern) {
 144             OptimizerPatterns annSrc = OptimizerPatterns.Read(ndSrc);
 145
 146             if (annSrc.MatchesPattern(pattern)) {
 147                 OptimizerPatterns annDst = OptimizerPatterns.Write(ndDst);
 148                 annDst.AddPattern(pattern);
 149
 150                 // Inherit pattern arguments
 151                 switch (pattern) {
 152                     case OptimizerPatternName.Step:
 153                         annDst.AddArgument(OptimizerPatternArgument.StepNode, annSrc.GetArgument(OptimizerPatternArgument.StepNode));
 154                         annDst.AddArgument(OptimizerPatternArgument.StepInput, annSrc.GetArgument(OptimizerPatternArgument.StepInput));
 155                         break;
 156
 157                     case OptimizerPatternName.FilterElements:
 158                         annDst.AddArgument(OptimizerPatternArgument.ElementQName, annSrc.GetArgument(OptimizerPatternArgument.ElementQName));
 159                         break;
 160
 161                     case OptimizerPatternName.FilterContentKind:
 162                         annDst.AddArgument(OptimizerPatternArgument.KindTestType, annSrc.GetArgument(OptimizerPatternArgument.KindTestType));
 163                         break;
 164
 165                     case OptimizerPatternName.EqualityIndex:
 166                         annDst.AddArgument(OptimizerPatternArgument.IndexedNodes, annSrc.GetArgument(OptimizerPatternArgument.IndexedNodes));
 167                         annDst.AddArgument(OptimizerPatternArgument.KeyExpression, annSrc.GetArgument(OptimizerPatternArgument.KeyExpression));
 168                         break;
 169
 170                     case OptimizerPatternName.DodReverse:
 171                     case OptimizerPatternName.JoinAndDod:
 172                         annDst.AddArgument(OptimizerPatternArgument.DodStep, annSrc.GetArgument(OptimizerPatternArgument.DodStep));
 173                         break;
 174
 175                     case OptimizerPatternName.MaxPosition:
 176                         annDst.AddArgument(OptimizerPatternArgument.MaxPosition, annSrc.GetArgument(OptimizerPatternArgument.MaxPosition));
 177                         break;
 178
 179                     case OptimizerPatternName.SingleTextRtf:
 180                         annDst.AddArgument(OptimizerPatternArgument.RtfText, annSrc.GetArgument(OptimizerPatternArgument.RtfText));
 181                         break;
 182                 }
 183             }
 184         }
 185
 186         /// <summary>
 187         /// Add an argument to one of the matching patterns.
 188         /// </summary>
 189         public void AddArgument(OptimizerPatternArgument argId, object arg) {
 190             Debug.Assert(!this.isReadOnly, "This OptimizerPatterns instance is read-only.");
 191
 192             switch ((int) argId) {
 193                 case 0: this.arg0 = arg; break;
 194                 case 1: this.arg1 = arg; break;
 195                 case 2: this.arg2 = arg; break;
 196                 default:
 197                     Debug.Assert(false, "Cannot handle more than 2 arguments.");
 198                     break;
 199             }
 200         }
 201
 202         /// <summary>
 203         /// Get an argument of one of the matching patterns.
 204         /// </summary>
 205         public object GetArgument(OptimizerPatternArgument argNum) {
 206             object arg = null;
 207
 208             switch ((int) argNum) {
 209                 case 0: arg = this.arg0; break;
 210                 case 1: arg = this.arg1; break;
 211                 case 2: arg = this.arg2; break;
 212             }
 213
 214             Debug.Assert(arg != null, "There is no '" + argNum + "' argument.");
 215             return arg;
 216         }
 217
 218         /// <summary>
 219         /// Add a pattern to the list of patterns that the annotated node matches.
 220         /// </summary>
 221         public void AddPattern(OptimizerPatternName pattern) {
 222             Debug.Assert(Enum.IsDefined(typeof(OptimizerPatternName), pattern));
 223             Debug.Assert((int) pattern < 32);
 224             Debug.Assert(!this.isReadOnly, "This OptimizerPatterns instance is read-only.");
 225             this.patterns |= (1 << (int) pattern);
 226         }
 227
 228         /// <summary>
 229         /// Return true if the annotated node matches the specified pattern.
 230         /// </summary>
 231         public bool MatchesPattern(OptimizerPatternName pattern) {
 232             Debug.Assert(Enum.IsDefined(typeof(OptimizerPatternName), pattern));
 233             return (this.patterns & (1 << (int) pattern)) != 0;
 234         }
 235
 236         /// <summary>
 237         /// Return name of this annotation.
 238         /// </summary>
 239         public virtual string Name {
 240             get { return "Patterns"; }
 241         }
 242
 243         /// <summary>
 244         /// Return string representation of this annotation.
 245         /// </summary>
 246         public override string ToString() {
 247             string s = "";
 248
 249             for (int pattNum = 0; pattNum < PatternCount; pattNum++) {
 250                 if (MatchesPattern((OptimizerPatternName) pattNum)) {
 251                     if (s.Length != 0)
 252                         s += ", ";
 253
 254                     s += ((OptimizerPatternName) pattNum).ToString();
 255                 }
 256             }
 257
 258             return s;
 259         }
 260     }
 261 }
 262