mcs/class/referencesource/System.Data.Entity/System/Data/Query/InternalTrees/RuleProcessor.cs

   1 //---------------------------------------------------------------------
   2 // <copyright file="RuleProcessor.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner  Microsoft
   7 // @backupOwner Microsoft
   8 //---------------------------------------------------------------------
   9
  10 using System;
  11 using System.Collections.Generic;
  12 using System.Collections.ObjectModel;
  13 using System.Globalization;
  14 using System.Diagnostics;
  15
  16 namespace System.Data.Query.InternalTrees
  17 {
  18     #region RuleProcessor
  19     /// <summary>
  20     /// The RuleProcessor helps apply a set of rules to a query tree
  21     /// </summary>
  22     internal class RuleProcessor
  23     {
  24         #region private state
  25         /// <summary>
  26         /// A lookup table for rules.
  27         /// The lookup table is an array indexed by OpType and each entry has a list of rules.
  28         /// </summary>
  29         private Dictionary<SubTreeId, SubTreeId> m_processedNodeMap;
  30         #endregion
  31
  32         #region constructors
  33         /// <summary>
  34         /// Initializes a new RuleProcessor
  35         /// </summary>
  36         internal RuleProcessor()
  37         {
  38             // Build up the accelerator tables
  39             m_processedNodeMap = new Dictionary<SubTreeId, SubTreeId>();
  40         }
  41         #endregion
  42
  43         #region private methods
  44
  45         private static bool ApplyRulesToNode(RuleProcessingContext context, ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> rules, Node currentNode, out Node newNode)
  46         {
  47             newNode = currentNode;
  48
  49             // Apply any pre-rule delegates
  50             context.PreProcess(currentNode);
  51
  52             foreach (Rule r in rules[(int)currentNode.Op.OpType])
  53             {
  54                 if (!r.Match(currentNode))
  55                 {
  56                     continue;
  57                 }
  58
  59                 // Did the rule modify the subtree?
  60                 if (r.Apply(context, currentNode, out newNode))
  61                 {
  62                     // The node has changed; don't try to apply any more rules
  63                     context.PostProcess(newNode, r);
  64                     return true;
  65                 }
  66                 else
  67                 {
  68                     Debug.Assert(newNode == currentNode, "Liar! This rule should have returned 'true'");
  69                 }
  70             }
  71
  72             context.PostProcess(currentNode, null);
  73             return false;
  74         }
  75
  76         /// <summary>
  77         /// Apply rules to the current subtree in a bottom-up fashion.
  78         /// </summary>
  79         /// <param name="context">Current rule processing context</param>
  80         /// <param name="rules">The look-up table with the rules to be applied</param>
  81         /// <param name="subTreeRoot">Current subtree</param>
  82         /// <param name="parent">Parent node</param>
  83         /// <param name="childIndexInParent">Index of this child within the parent</param>
  84         /// <returns>the result of the transformation</returns>
  85         private Node ApplyRulesToSubtree(RuleProcessingContext context,
  86             ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> rules,
  87             Node subTreeRoot, Node parent, int childIndexInParent)
  88         {
  89             int loopCount = 0;
  90             Dictionary<SubTreeId, SubTreeId> localProcessedMap = new Dictionary<SubTreeId, SubTreeId>();
  91             SubTreeId subTreeId;
  92
  93             while (true)
  94             {
  95                 // Am I looping forever
  96                 Debug.Assert(loopCount < 12, "endless loops?");
  97                 loopCount++;
  98
  99                 //
 100                 // We may need to update state regardless of whether this subTree has
 101                 // changed after it has been processed last. For example, it may be
 102                 // affected by transformation in its siblings due to external references.
 103                 //
 104                 context.PreProcessSubTree(subTreeRoot);
 105                 subTreeId = new SubTreeId(context, subTreeRoot, parent, childIndexInParent);
 106
 107                 // Have I seen this subtree already? Just return, if so
 108                 if (m_processedNodeMap.ContainsKey(subTreeId))
 109                 {
 110                     break;
 111                 }
 112
 113                 // Avoid endless loops here - avoid cycles of 2 or more
 114                 if (localProcessedMap.ContainsKey(subTreeId))
 115                 {
 116                     // mark this subtree as processed
 117                     m_processedNodeMap[subTreeId] = subTreeId;
 118                     break;
 119                 }
 120                 // Keep track of this one
 121                 localProcessedMap[subTreeId] = subTreeId;
 122
 123                 // Walk my children
 124                 for (int i = 0; i < subTreeRoot.Children.Count; i++)
 125                 {
 126                     subTreeRoot.Children[i] = ApplyRulesToSubtree(context, rules, subTreeRoot.Children[i], subTreeRoot, i);
 127                 }
 128
 129                 // Apply rules to myself. If no transformations were performed,
 130                 // then mark this subtree as processed, and break out
 131                 Node newSubTreeRoot;
 132                 if (!ApplyRulesToNode(context, rules, subTreeRoot, out newSubTreeRoot))
 133                 {
 134                     Debug.Assert(subTreeRoot == newSubTreeRoot);
 135                     // mark this subtree as processed
 136                     m_processedNodeMap[subTreeId] = subTreeId;
 137                     break;
 138                 }
 139                 context.PostProcessSubTree(subTreeRoot);
 140                 subTreeRoot = newSubTreeRoot;
 141             }
 142
 143             context.PostProcessSubTree(subTreeRoot);
 144             return subTreeRoot;
 145         }
 146         #endregion
 147
 148         #region public methods
 149         /// <summary>
 150         /// Apply a set of rules to the subtree
 151         /// </summary>
 152         /// <param name="context">Rule processing context</param>
 153         /// <param name="subTreeRoot">current subtree</param>
 154         /// <returns>transformed subtree</returns>
 155         internal Node ApplyRulesToSubtree(RuleProcessingContext context, ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> rules, Node subTreeRoot)
 156         {
 157             return ApplyRulesToSubtree(context, rules, subTreeRoot, null, 0);
 158         }
 159
 160         #endregion
 161     }
 162     #endregion
 163
 164     #region SubTreeId
 165     internal class SubTreeId
 166     {
 167         #region private state
 168         public Node m_subTreeRoot;
 169         private int m_hashCode;
 170         private Node m_parent;
 171         private int m_parentHashCode;
 172         private int m_childIndex;
 173         #endregion
 174
 175         #region constructors
 176         internal SubTreeId(RuleProcessingContext context, Node node, Node parent, int childIndex)
 177         {
 178             m_subTreeRoot = node;
 179             m_parent = parent;
 180             m_childIndex = childIndex;
 181             m_hashCode = context.GetHashCode(node);
 182             m_parentHashCode = parent == null ? 0 : context.GetHashCode(parent);
 183         }
 184         #endregion
 185
 186         #region public surface
 187         public override int GetHashCode()
 188         {
 189             return m_hashCode;
 190         }
 191         public override bool Equals(object obj)
 192         {
 193             SubTreeId other = obj as SubTreeId;
 194             return ((other != null) && (m_hashCode == other.m_hashCode) &&
 195                 ((other.m_subTreeRoot == this.m_subTreeRoot) ||
 196                   ((other.m_parent == this.m_parent) && (other.m_childIndex == this.m_childIndex))));
 197         }
 198         #endregion
 199     }
 200     #endregion
 201
 202     #region RuleProcessingContext
 203
 204     /// <summary>
 205     /// Delegate that describes the processing
 206     /// </summary>
 207     /// <param name="context">RuleProcessing context</param>
 208     /// <param name="node">Node to process</param>
 209     internal delegate void OpDelegate(RuleProcessingContext context, Node node);
 210
 211     /// <summary>
 212     /// A RuleProcessingContext encapsulates information needed by various rules to process
 213     /// the query tree.
 214     /// </summary>
 215     internal abstract class RuleProcessingContext
 216     {
 217         #region public surface
 218         internal Command Command
 219         {
 220             get { return m_command; }
 221         }
 222
 223         /// <summary>
 224         /// Callback function to be applied to a node before any rules are applied
 225         /// </summary>
 226         /// <param name="node">the node</param>
 227         internal virtual void PreProcess(Node node)
 228         {
 229
 230         }
 231
 232         /// <summary>
 233         /// Callback function to be applied to the subtree rooted at the given
 234         /// node before any rules are applied
 235         /// </summary>
 236         /// <param name="node">the node that is the root of the subtree</param>
 237         internal virtual void PreProcessSubTree(Node node)
 238         {
 239         }
 240
 241         /// <summary>
 242         /// Callback function to be applied on a node after a rule has been applied
 243         /// that has modified the node
 244         /// </summary>
 245         /// <param name="node">current node</param>
 246         /// <param name="rule">the rule that modified the node</param>
 247         internal virtual void PostProcess(Node node, Rule rule)
 248         {
 249         }
 250
 251         /// <summary>
 252         /// Callback function to be applied to the subtree rooted at the given
 253         /// node after any rules are applied
 254         /// </summary>
 255         /// <param name="node">the node that is the root of the subtree</param>
 256         internal virtual void PostProcessSubTree(Node node)
 257         {
 258         }
 259
 260         /// <summary>
 261         /// Get the hashcode for this node - to ensure that we don't loop forever
 262         /// </summary>
 263         /// <param name="node">current node</param>
 264         /// <returns>int hashcode</returns>
 265         internal virtual int GetHashCode(Node node)
 266         {
 267             return node.GetHashCode();
 268         }
 269         #endregion
 270
 271         #region constructors
 272         internal RuleProcessingContext(Command command)
 273         {
 274             m_command = command;
 275         }
 276         #endregion
 277
 278         #region private state
 279         private Command m_command;
 280         #endregion
 281     }
 282     #endregion
 283 }