File: System\Data\Query\InternalTrees\RuleProcessor.cs
Project: ndp\fx\src\DataEntity\System.Data.Entity.csproj (System.Data.Entity)
//---------------------------------------------------------------------
// <copyright file="RuleProcessor.cs" company="Microsoft">
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// </copyright>
//
// @owner  Microsoft
// @backupOwner Microsoft
//---------------------------------------------------------------------
 
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Globalization;
using System.Diagnostics;
 
namespace System.Data.Query.InternalTrees
{
    #region RuleProcessor
    /// <summary>
    /// The RuleProcessor helps apply a set of rules to a query tree
    /// </summary>
    internal class RuleProcessor
    {
        #region private state
        /// <summary>
        /// A lookup table for rules.
        /// The lookup table is an array indexed by OpType and each entry has a list of rules.
        /// </summary>
        private Dictionary<SubTreeId, SubTreeId> m_processedNodeMap;
        #endregion
 
        #region constructors
        /// <summary>
        /// Initializes a new RuleProcessor
        /// </summary>
        internal RuleProcessor()
        {
            // Build up the accelerator tables
            m_processedNodeMap = new Dictionary<SubTreeId, SubTreeId>();
        }
        #endregion
 
        #region private methods
 
        private static bool ApplyRulesToNode(RuleProcessingContext context, ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> rules, Node currentNode, out Node newNode)
        {
            newNode = currentNode;
 
            // Apply any pre-rule delegates
            context.PreProcess(currentNode);
 
            foreach (Rule r in rules[(int)currentNode.Op.OpType])
            {
                if (!r.Match(currentNode))
                {
                    continue;
                }
 
                // Did the rule modify the subtree?
                if (r.Apply(context, currentNode, out newNode))
                {
                    // The node has changed; don't try to apply any more rules
                    context.PostProcess(newNode, r);
                    return true;
                }
                else
                {
                    Debug.Assert(newNode == currentNode, "Liar! This rule should have returned 'true'");
                }
            }
 
            context.PostProcess(currentNode, null);
            return false;
        }
 
        /// <summary>
        /// Apply rules to the current subtree in a bottom-up fashion. 
        /// </summary>
        /// <param name="context">Current rule processing context</param>
        /// <param name="rules">The look-up table with the rules to be applied</param>
        /// <param name="subTreeRoot">Current subtree</param>
        /// <param name="parent">Parent node</param>
        /// <param name="childIndexInParent">Index of this child within the parent</param>
        /// <returns>the result of the transformation</returns>
        private Node ApplyRulesToSubtree(RuleProcessingContext context, 
            ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> rules,
            Node subTreeRoot, Node parent, int childIndexInParent)
        {
            int loopCount = 0;
            Dictionary<SubTreeId, SubTreeId> localProcessedMap = new Dictionary<SubTreeId, SubTreeId>();
            SubTreeId subTreeId;
 
            while (true)
            {
                // Am I looping forever
                Debug.Assert(loopCount < 12, "endless loops?");
                loopCount++;
 
                //
                // We may need to update state regardless of whether this subTree has 
                // changed after it has been processed last. For example, it may be 
                // affected by transformation in its siblings due to external references.
                //
                context.PreProcessSubTree(subTreeRoot);
                subTreeId = new SubTreeId(context, subTreeRoot, parent, childIndexInParent);
   
                // Have I seen this subtree already? Just return, if so
                if (m_processedNodeMap.ContainsKey(subTreeId))
                {
                    break;
                }
 
                // Avoid endless loops here - avoid cycles of 2 or more
                if (localProcessedMap.ContainsKey(subTreeId))
                {
                    // mark this subtree as processed
                    m_processedNodeMap[subTreeId] = subTreeId;
                    break;
                }
                // Keep track of this one
                localProcessedMap[subTreeId] = subTreeId;
 
                // Walk my children
                for (int i = 0; i < subTreeRoot.Children.Count; i++)
                {
                    subTreeRoot.Children[i] = ApplyRulesToSubtree(context, rules, subTreeRoot.Children[i], subTreeRoot, i);
                }
 
                // Apply rules to myself. If no transformations were performed, 
                // then mark this subtree as processed, and break out
                Node newSubTreeRoot;
                if (!ApplyRulesToNode(context, rules, subTreeRoot, out newSubTreeRoot))
                {
                    Debug.Assert(subTreeRoot == newSubTreeRoot);
                    // mark this subtree as processed
                    m_processedNodeMap[subTreeId] = subTreeId;
                    break;
                }
                context.PostProcessSubTree(subTreeRoot);
                subTreeRoot = newSubTreeRoot;
            }
 
            context.PostProcessSubTree(subTreeRoot);
            return subTreeRoot;
        }
        #endregion
 
        #region public methods
        /// <summary>
        /// Apply a set of rules to the subtree
        /// </summary>
        /// <param name="context">Rule processing context</param>
        /// <param name="subTreeRoot">current subtree</param>
        /// <returns>transformed subtree</returns>
        internal Node ApplyRulesToSubtree(RuleProcessingContext context, ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> rules, Node subTreeRoot)
        {
            return ApplyRulesToSubtree(context, rules, subTreeRoot, null, 0);
        }
 
        #endregion
    }
    #endregion
 
    #region SubTreeId
    internal class SubTreeId
    {
        #region private state
        public Node m_subTreeRoot;
        private int m_hashCode;
        private Node m_parent;
        private int m_parentHashCode;
        private int m_childIndex;
        #endregion
 
        #region constructors
        internal SubTreeId(RuleProcessingContext context, Node node, Node parent, int childIndex)
        {
            m_subTreeRoot = node;
            m_parent = parent;
            m_childIndex = childIndex;
            m_hashCode = context.GetHashCode(node);
            m_parentHashCode = parent == null ? 0 : context.GetHashCode(parent);
        }
        #endregion
 
        #region public surface
        public override int GetHashCode()
        {
            return m_hashCode;
        }
        public override bool Equals(object obj)
        {
            SubTreeId other = obj as SubTreeId;
            return ((other != null) && (m_hashCode == other.m_hashCode) &&
                ((other.m_subTreeRoot == this.m_subTreeRoot) ||
                  ((other.m_parent == this.m_parent) && (other.m_childIndex == this.m_childIndex))));
        }
        #endregion
    }
    #endregion
 
    #region RuleProcessingContext
 
    /// <summary>
    /// Delegate that describes the processing 
    /// </summary>
    /// <param name="context">RuleProcessing context</param>
    /// <param name="node">Node to process</param>
    internal delegate void OpDelegate(RuleProcessingContext context, Node node);
 
    /// <summary>
    /// A RuleProcessingContext encapsulates information needed by various rules to process
    /// the query tree.
    /// </summary>
    internal abstract class RuleProcessingContext
    {
        #region public surface
        internal Command Command
        {
            get { return m_command; }
        }
 
        /// <summary>
        /// Callback function to be applied to a node before any rules are applied
        /// </summary>
        /// <param name="node">the node</param>
        internal virtual void PreProcess(Node node)
        {
 
        }
 
        /// <summary>
        /// Callback function to be applied to the subtree rooted at the given 
        /// node before any rules are applied
        /// </summary>
        /// <param name="node">the node that is the root of the subtree</param>
        internal virtual void PreProcessSubTree(Node node)
        {
        }
 
        /// <summary>
        /// Callback function to be applied on a node after a rule has been applied
        /// that has modified the node
        /// </summary>
        /// <param name="node">current node</param>
        /// <param name="rule">the rule that modified the node</param>
        internal virtual void PostProcess(Node node, Rule rule)
        {
        }
 
        /// <summary>
        /// Callback function to be applied to the subtree rooted at the given 
        /// node after any rules are applied
        /// </summary>
        /// <param name="node">the node that is the root of the subtree</param>
        internal virtual void PostProcessSubTree(Node node)
        {
        }
 
        /// <summary>
        /// Get the hashcode for this node - to ensure that we don't loop forever
        /// </summary>
        /// <param name="node">current node</param>
        /// <returns>int hashcode</returns>
        internal virtual int GetHashCode(Node node)
        {
            return node.GetHashCode();
        }
        #endregion
 
        #region constructors
        internal RuleProcessingContext(Command command)
        {
            m_command = command;
        }
        #endregion
 
        #region private state
        private Command m_command;
        #endregion
    }
    #endregion
}