1 //---------------------------------------------------------------------
2 // <copyright file="RuleProcessor.cs" company="Microsoft">
3 // Copyright (c) Microsoft Corporation. All rights reserved.
7 // @backupOwner Microsoft
8 //---------------------------------------------------------------------
11 using System
.Collections
.Generic
;
12 using System
.Collections
.ObjectModel
;
13 using System
.Globalization
;
14 using System
.Diagnostics
;
16 namespace System
.Data
.Query
.InternalTrees
20 /// The RuleProcessor helps apply a set of rules to a query tree
22 internal class RuleProcessor
26 /// A lookup table for rules.
27 /// The lookup table is an array indexed by OpType and each entry has a list of rules.
29 private Dictionary
<SubTreeId
, SubTreeId
> m_processedNodeMap
;
34 /// Initializes a new RuleProcessor
36 internal RuleProcessor()
38 // Build up the accelerator tables
39 m_processedNodeMap
= new Dictionary
<SubTreeId
, SubTreeId
>();
43 #region private methods
45 private static bool ApplyRulesToNode(RuleProcessingContext context
, ReadOnlyCollection
<ReadOnlyCollection
<InternalTrees
.Rule
>> rules
, Node currentNode
, out Node newNode
)
47 newNode
= currentNode
;
49 // Apply any pre-rule delegates
50 context
.PreProcess(currentNode
);
52 foreach (Rule r
in rules
[(int)currentNode
.Op
.OpType
])
54 if (!r
.Match(currentNode
))
59 // Did the rule modify the subtree?
60 if (r
.Apply(context
, currentNode
, out newNode
))
62 // The node has changed; don't try to apply any more rules
63 context
.PostProcess(newNode
, r
);
68 Debug
.Assert(newNode
== currentNode
, "Liar! This rule should have returned 'true'");
72 context
.PostProcess(currentNode
, null);
77 /// Apply rules to the current subtree in a bottom-up fashion.
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
)
90 Dictionary
<SubTreeId
, SubTreeId
> localProcessedMap
= new Dictionary
<SubTreeId
, SubTreeId
>();
95 // Am I looping forever
96 Debug
.Assert(loopCount
< 12, "endless loops?");
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.
104 context
.PreProcessSubTree(subTreeRoot
);
105 subTreeId
= new SubTreeId(context
, subTreeRoot
, parent
, childIndexInParent
);
107 // Have I seen this subtree already? Just return, if so
108 if (m_processedNodeMap
.ContainsKey(subTreeId
))
113 // Avoid endless loops here - avoid cycles of 2 or more
114 if (localProcessedMap
.ContainsKey(subTreeId
))
116 // mark this subtree as processed
117 m_processedNodeMap
[subTreeId
] = subTreeId
;
120 // Keep track of this one
121 localProcessedMap
[subTreeId
] = subTreeId
;
124 for (int i
= 0; i
< subTreeRoot
.Children
.Count
; i
++)
126 subTreeRoot
.Children
[i
] = ApplyRulesToSubtree(context
, rules
, subTreeRoot
.Children
[i
], subTreeRoot
, i
);
129 // Apply rules to myself. If no transformations were performed,
130 // then mark this subtree as processed, and break out
132 if (!ApplyRulesToNode(context
, rules
, subTreeRoot
, out newSubTreeRoot
))
134 Debug
.Assert(subTreeRoot
== newSubTreeRoot
);
135 // mark this subtree as processed
136 m_processedNodeMap
[subTreeId
] = subTreeId
;
139 context
.PostProcessSubTree(subTreeRoot
);
140 subTreeRoot
= newSubTreeRoot
;
143 context
.PostProcessSubTree(subTreeRoot
);
148 #region public methods
150 /// Apply a set of rules to the subtree
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
)
157 return ApplyRulesToSubtree(context
, rules
, subTreeRoot
, null, 0);
165 internal class SubTreeId
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
;
176 internal SubTreeId(RuleProcessingContext context
, Node node
, Node parent
, int childIndex
)
178 m_subTreeRoot
= node
;
180 m_childIndex
= childIndex
;
181 m_hashCode
= context
.GetHashCode(node
);
182 m_parentHashCode
= parent
== null ? 0 : context
.GetHashCode(parent
);
186 #region public surface
187 public override int GetHashCode()
191 public override bool Equals(object obj
)
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
))));
202 #region RuleProcessingContext
205 /// Delegate that describes the processing
207 /// <param name="context">RuleProcessing context</param>
208 /// <param name="node">Node to process</param>
209 internal delegate void OpDelegate(RuleProcessingContext context
, Node node
);
212 /// A RuleProcessingContext encapsulates information needed by various rules to process
215 internal abstract class RuleProcessingContext
217 #region public surface
218 internal Command Command
220 get { return m_command; }
224 /// Callback function to be applied to a node before any rules are applied
226 /// <param name="node">the node</param>
227 internal virtual void PreProcess(Node node
)
233 /// Callback function to be applied to the subtree rooted at the given
234 /// node before any rules are applied
236 /// <param name="node">the node that is the root of the subtree</param>
237 internal virtual void PreProcessSubTree(Node node
)
242 /// Callback function to be applied on a node after a rule has been applied
243 /// that has modified the node
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
)
252 /// Callback function to be applied to the subtree rooted at the given
253 /// node after any rules are applied
255 /// <param name="node">the node that is the root of the subtree</param>
256 internal virtual void PostProcessSubTree(Node node
)
261 /// Get the hashcode for this node - to ensure that we don't loop forever
263 /// <param name="node">current node</param>
264 /// <returns>int hashcode</returns>
265 internal virtual int GetHashCode(Node node
)
267 return node
.GetHashCode();
272 internal RuleProcessingContext(Command command
)
278 #region private state
279 private Command m_command
;