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.Diagnostics; 7 using System.Xml.Xsl.Qil; 8 9 namespace System.Xml.Xsl.IlGen 10 { 11 internal enum OptimizerPatternName 12 { 13 None, 14 DodReverse, // (Dod $reverse-axis:*) 15 EqualityIndex, // ILGen will build an equality index when this pattern is recognized 16 FilterAttributeKind, // (Filter $iter:(Content *) (IsType $iter Attribute)) 17 FilterContentKind, // (Filter $iter:* (IsType $iter $kind:*)) 18 FilterElements, // (Filter $iter:* (And (IsType $iter Element) (NameOf $iter (LiteralQName * * *)))) 19 IsDocOrderDistinct, // True if the annotated expression always returns nodes in document order, with no duplicates 20 IsPositional, // True if the annotated iterator should track current position during iteration 21 JoinAndDod, // (Dod (Loop $path1:* $path2:*)), where $path2.ContextNode = $path1 22 MaxPosition, // True if the position range of the annoted iterator or length expression has a maximum 23 SameDepth, // True if the annotated expression always returns nodes at the same depth in the tree 24 Step, // True if the annotated expression returns nodes from one of the simple axis operators, or from a union of Content operators 25 SingleTextRtf, // (RtfCtor (TextCtor *) *) 26 Axis, // (AnyAxis *) 27 MaybeSideEffects, // True if annotated expression might have side effects 28 TailCall, // (Invoke * *) True if invocation can be compiled as using .tailcall 29 DodMerge, // (Dod (Loop * (Invoke * *))), where invoked function returns nodes in document order 30 IsReferenced, // True if the annotated global iterator is referenced at least once 31 } 32 33 internal enum OptimizerPatternArgument 34 { 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 { 58 private static readonly int s_patternCount = Enum.GetValues(typeof(OptimizerPatternName)).Length; 59 60 private int _patterns; // Set of patterns that the annotated Qil node and its subtree matches 61 private bool _isReadOnly; // True if setters are disabled in the case of singleton OptimizerPatterns 62 private object _arg0, _arg1, _arg2; // Arguments to the matching patterns 63 64 private static volatile OptimizerPatterns s_zeroOrOneDefault; 65 private static volatile OptimizerPatterns s_maybeManyDefault; 66 private static volatile OptimizerPatterns s_dodDefault; 67 68 /// <summary> 69 /// Get OptimizerPatterns annotation for the specified node. Lazily create if necessary. 70 /// </summary> Read(QilNode nd)71 public static OptimizerPatterns Read(QilNode nd) 72 { 73 XmlILAnnotation ann = nd.Annotation as XmlILAnnotation; 74 OptimizerPatterns optPatt = (ann != null) ? ann.Patterns : null; 75 76 if (optPatt == null) 77 { 78 if (!nd.XmlType.MaybeMany) 79 { 80 // Expressions with ZeroOrOne cardinality should always report IsDocOrderDistinct and NoContainedNodes 81 if (s_zeroOrOneDefault == null) 82 { 83 optPatt = new OptimizerPatterns(); 84 optPatt.AddPattern(OptimizerPatternName.IsDocOrderDistinct); 85 optPatt.AddPattern(OptimizerPatternName.SameDepth); 86 optPatt._isReadOnly = true; 87 88 s_zeroOrOneDefault = optPatt; 89 } 90 else 91 { 92 optPatt = s_zeroOrOneDefault; 93 } 94 } 95 else if (nd.XmlType.IsDod) 96 { 97 if (s_dodDefault == null) 98 { 99 optPatt = new OptimizerPatterns(); 100 optPatt.AddPattern(OptimizerPatternName.IsDocOrderDistinct); 101 optPatt._isReadOnly = true; 102 103 s_dodDefault = optPatt; 104 } 105 else 106 { 107 optPatt = s_dodDefault; 108 } 109 } 110 else 111 { 112 if (s_maybeManyDefault == null) 113 { 114 optPatt = new OptimizerPatterns(); 115 optPatt._isReadOnly = true; 116 117 s_maybeManyDefault = optPatt; 118 } 119 else 120 { 121 optPatt = s_maybeManyDefault; 122 } 123 } 124 } 125 126 return optPatt; 127 } 128 129 /// <summary> 130 /// Create and initialize OptimizerPatterns annotation for the specified node. 131 /// </summary> Write(QilNode nd)132 public static OptimizerPatterns Write(QilNode nd) 133 { 134 XmlILAnnotation ann = XmlILAnnotation.Write(nd); 135 OptimizerPatterns optPatt = ann.Patterns; 136 137 if (optPatt == null || optPatt._isReadOnly) 138 { 139 optPatt = new OptimizerPatterns(); 140 ann.Patterns = optPatt; 141 142 if (!nd.XmlType.MaybeMany) 143 { 144 optPatt.AddPattern(OptimizerPatternName.IsDocOrderDistinct); 145 optPatt.AddPattern(OptimizerPatternName.SameDepth); 146 } 147 else if (nd.XmlType.IsDod) 148 { 149 optPatt.AddPattern(OptimizerPatternName.IsDocOrderDistinct); 150 } 151 } 152 153 return optPatt; 154 } 155 156 /// <summary> 157 /// Create and initialize OptimizerPatterns annotation for the specified node. 158 /// </summary> Inherit(QilNode ndSrc, QilNode ndDst, OptimizerPatternName pattern)159 public static void Inherit(QilNode ndSrc, QilNode ndDst, OptimizerPatternName pattern) 160 { 161 OptimizerPatterns annSrc = OptimizerPatterns.Read(ndSrc); 162 163 if (annSrc.MatchesPattern(pattern)) 164 { 165 OptimizerPatterns annDst = OptimizerPatterns.Write(ndDst); 166 annDst.AddPattern(pattern); 167 168 // Inherit pattern arguments 169 switch (pattern) 170 { 171 case OptimizerPatternName.Step: 172 annDst.AddArgument(OptimizerPatternArgument.StepNode, annSrc.GetArgument(OptimizerPatternArgument.StepNode)); 173 annDst.AddArgument(OptimizerPatternArgument.StepInput, annSrc.GetArgument(OptimizerPatternArgument.StepInput)); 174 break; 175 176 case OptimizerPatternName.FilterElements: 177 annDst.AddArgument(OptimizerPatternArgument.ElementQName, annSrc.GetArgument(OptimizerPatternArgument.ElementQName)); 178 break; 179 180 case OptimizerPatternName.FilterContentKind: 181 annDst.AddArgument(OptimizerPatternArgument.KindTestType, annSrc.GetArgument(OptimizerPatternArgument.KindTestType)); 182 break; 183 184 case OptimizerPatternName.EqualityIndex: 185 annDst.AddArgument(OptimizerPatternArgument.IndexedNodes, annSrc.GetArgument(OptimizerPatternArgument.IndexedNodes)); 186 annDst.AddArgument(OptimizerPatternArgument.KeyExpression, annSrc.GetArgument(OptimizerPatternArgument.KeyExpression)); 187 break; 188 189 case OptimizerPatternName.DodReverse: 190 case OptimizerPatternName.JoinAndDod: 191 annDst.AddArgument(OptimizerPatternArgument.DodStep, annSrc.GetArgument(OptimizerPatternArgument.DodStep)); 192 break; 193 194 case OptimizerPatternName.MaxPosition: 195 annDst.AddArgument(OptimizerPatternArgument.MaxPosition, annSrc.GetArgument(OptimizerPatternArgument.MaxPosition)); 196 break; 197 198 case OptimizerPatternName.SingleTextRtf: 199 annDst.AddArgument(OptimizerPatternArgument.RtfText, annSrc.GetArgument(OptimizerPatternArgument.RtfText)); 200 break; 201 } 202 } 203 } 204 205 /// <summary> 206 /// Add an argument to one of the matching patterns. 207 /// </summary> AddArgument(OptimizerPatternArgument argId, object arg)208 public void AddArgument(OptimizerPatternArgument argId, object arg) 209 { 210 Debug.Assert(!_isReadOnly, "This OptimizerPatterns instance is read-only."); 211 212 switch ((int)argId) 213 { 214 case 0: _arg0 = arg; break; 215 case 1: _arg1 = arg; break; 216 case 2: _arg2 = arg; break; 217 default: 218 Debug.Assert(false, "Cannot handle more than 2 arguments."); 219 break; 220 } 221 } 222 223 /// <summary> 224 /// Get an argument of one of the matching patterns. 225 /// </summary> GetArgument(OptimizerPatternArgument argNum)226 public object GetArgument(OptimizerPatternArgument argNum) 227 { 228 object arg = null; 229 230 switch ((int)argNum) 231 { 232 case 0: arg = _arg0; break; 233 case 1: arg = _arg1; break; 234 case 2: arg = _arg2; break; 235 } 236 237 Debug.Assert(arg != null, "There is no '" + argNum + "' argument."); 238 return arg; 239 } 240 241 /// <summary> 242 /// Add a pattern to the list of patterns that the annotated node matches. 243 /// </summary> AddPattern(OptimizerPatternName pattern)244 public void AddPattern(OptimizerPatternName pattern) 245 { 246 Debug.Assert(Enum.IsDefined(typeof(OptimizerPatternName), pattern)); 247 Debug.Assert((int)pattern < 32); 248 Debug.Assert(!_isReadOnly, "This OptimizerPatterns instance is read-only."); 249 _patterns |= (1 << (int)pattern); 250 } 251 252 /// <summary> 253 /// Return true if the annotated node matches the specified pattern. 254 /// </summary> MatchesPattern(OptimizerPatternName pattern)255 public bool MatchesPattern(OptimizerPatternName pattern) 256 { 257 Debug.Assert(Enum.IsDefined(typeof(OptimizerPatternName), pattern)); 258 return (_patterns & (1 << (int)pattern)) != 0; 259 } 260 261 /// <summary> 262 /// Return name of this annotation. 263 /// </summary> 264 public virtual string Name 265 { 266 get { return "Patterns"; } 267 } 268 269 /// <summary> 270 /// Return string representation of this annotation. 271 /// </summary> ToString()272 public override string ToString() 273 { 274 string s = ""; 275 276 for (int pattNum = 0; pattNum < s_patternCount; pattNum++) 277 { 278 if (MatchesPattern((OptimizerPatternName)pattNum)) 279 { 280 if (s.Length != 0) 281 s += ", "; 282 283 s += ((OptimizerPatternName)pattNum).ToString(); 284 } 285 } 286 287 return s; 288 } 289 } 290 } 291 292