private bool Match(Node pattern, Node original)
 {
     if (pattern.Op.OpType
         == OpType.Leaf)
     {
         return true;
     }
     if (pattern.Op.OpType
         != original.Op.OpType)
     {
         return false;
     }
     if (pattern.Children.Count
         != original.Children.Count)
     {
         return false;
     }
     for (var i = 0; i < pattern.Children.Count; i++)
     {
         if (!Match(pattern.Children[i], original.Children[i]))
         {
             return false;
         }
     }
     return true;
 }

        /// <summary>
        /// We perform the following simple transformation for CaseOps. If every single
        /// then/else expression in the CaseOp is equivalent, then we can simply replace
        /// the Op with the first then/expression. Specifically,
        /// case when w1 then t1 when w2 then t2 ... when wn then tn else e end
        ///   => t1
        /// assuming that t1 is equivalent to t2 is equivalent to ... to e
        /// </summary>
        /// <param name="context">Rule Processing context</param>
        /// <param name="caseOpNode">The current subtree for the CaseOp</param>
        /// <param name="newNode">the (possibly) modified subtree</param>
        /// <returns>true, if we performed any transformations</returns>
        private static bool ProcessSimplifyCase(RuleProcessingContext context, Node caseOpNode, out Node newNode)
        {
            var caseOp = (CaseOp)caseOpNode.Op;
            newNode = caseOpNode;

            //
            // Can I collapse the entire case-expression into a single expression - yes, 
            // if all the then/else clauses are the same expression
            //
            if (ProcessSimplifyCase_Collapse(caseOpNode, out newNode))
            {
                return true;
            }

            //
            // Can I remove any unnecessary when-then pairs ?
            //
            if (ProcessSimplifyCase_EliminateWhenClauses(context, caseOp, caseOpNode, out newNode))
            {
                return true;
            }

            // Nothing else I can think of
            return false;
        }

 /// <summary>
 /// Visit the children of this Node. but in reverse order
 /// </summary>
 /// <param name="n">The current node</param>
 protected virtual void VisitChildrenReverse(Node n)
 {
     for (var i = n.Children.Count - 1; i >= 0; i--)
     {
         VisitNode(n.Children[i]);
     }
 }

 /// <summary>
 /// Visit the children of this Node
 /// </summary>
 /// <param name="n">The Node that references the Op</param>
 protected virtual void VisitChildren(Node n)
 {
     foreach (var chi in n.Children)
     {
         VisitNode(chi);
     }
 }

 internal static Node Copy(Command cmd, Node n, out VarMap varMap)
 {
     OpCopier oc = new OpCopier(cmd);
     Node newNode = oc.CopyNode(n);
     varMap = oc.m_varMap;
     return newNode;
 }

        /// <summary>
        /// Determines whether the var or a property of the var (if the var is defined as a NewRecord) 
        /// is defined exclusively over a single group aggregate. If so, it registers it as such with the
        /// group aggregate var info manager.
        /// </summary>
        /// <param name="op"></param>
        /// <param name="n"></param>
        public override void Visit(VarDefOp op, Node n)
        {
            VisitDefault(n);

            var definingNode = n.Child0;
            var definingNodeOp = definingNode.Op;

            GroupAggregateVarInfo referencedVarInfo;
            Node templateNode;
            bool isUnnested;
            if (GroupAggregateVarComputationTranslator.TryTranslateOverGroupAggregateVar(
                definingNode, true, _command, _groupAggregateVarInfoManager, out referencedVarInfo, out templateNode, out isUnnested))
            {
                _groupAggregateVarInfoManager.Add(op.Var, referencedVarInfo, templateNode, isUnnested);
            }
            else if (definingNodeOp.OpType
                     == OpType.NewRecord)
            {
                var newRecordOp = (NewRecordOp)definingNodeOp;
                for (var i = 0; i < definingNode.Children.Count; i++)
                {
                    var argumentNode = definingNode.Children[i];
                    if (GroupAggregateVarComputationTranslator.TryTranslateOverGroupAggregateVar(
                        argumentNode, true, _command, _groupAggregateVarInfoManager, out referencedVarInfo, out templateNode, out isUnnested))
                    {
                        _groupAggregateVarInfoManager.Add(op.Var, referencedVarInfo, templateNode, isUnnested, newRecordOp.Properties[i]);
                    }
                }
            }
        }

 /// <summary>
 /// Basic constructor
 /// </summary>
 /// <param name="pattern">The pattern to look for</param>
 /// <param name="processDelegate">The callback to invoke when such a pattern is identified</param>
 internal PatternMatchRule(Node pattern, ProcessNodeDelegate processDelegate)
     : base(pattern.Op.OpType, processDelegate)
 {
     Debug.Assert(pattern != null, "null pattern");
     Debug.Assert(pattern.Op != null, "null pattern Op");
     m_pattern = pattern;
 }

        /// <summary>
        /// If the DistinctOp includes all all the keys of the input, than it is unnecessary.
        /// Distinct (X, distinct_keys) -> Project( X, distinct_keys) where distinct_keys includes all keys of X.
        /// </summary>
        /// <param name="context">Rule processing context</param>
        /// <param name="n">current subtree</param>
        /// <param name="newNode">transformed subtree</param>
        /// <returns>transformation status</returns>
        private static bool ProcessDistinctOpOfKeys(RuleProcessingContext context, Node n, out Node newNode)
        {
            var command = context.Command;

            var nodeInfo = command.GetExtendedNodeInfo(n.Child0);

            var op = (DistinctOp)n.Op;

            //If we know the keys of the input and the list of distinct keys includes them all, omit the distinct
            if (!nodeInfo.Keys.NoKeys
                && op.Keys.Subsumes(nodeInfo.Keys.KeyVars))
            {
                var newOp = command.CreateProjectOp(op.Keys);

                //Create empty vardef list
                var varDefListOp = command.CreateVarDefListOp();
                var varDefListNode = command.CreateNode(varDefListOp);

                newNode = command.CreateNode(newOp, n.Child0, varDefListNode);
                return true;
            }

            //Otherwise return the node as is
            newNode = n;
            return false;
        }

        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>
        /// Determines whether any var from a given list of keys is referenced by any of defining node's right relatives, 
        /// with the exception of the relatives brunching at the given targetJoinNode.
        /// </summary>
        /// <param name="keys">A list of vars to check for</param>
        /// <param name="definingNode">The node considered to be the defining node</param>
        /// <param name="targetJoinNode">The relatives branching at this node are skipped</param>
        /// <returns>False, only it can determine that not a single var from a given list of keys is referenced by any 
        /// of defining node's right relatives, with the exception of the relatives brunching at the given targetJoinNode. </returns>
        internal bool HasKeyReferences(VarVec keys, Node definingNode, Node targetJoinNode)
        {
            Node currentChild = definingNode;
            Node parent;
            bool continueUp = true;

            while (continueUp & m_nodeToParentMap.TryGetValue(currentChild, out parent))
            {
                if (parent != targetJoinNode)
                {
                    // Check the parent
                    if (HasVarReferencesShallow(parent, keys, m_nodeToSiblingNumber[currentChild], out continueUp))
                    {
                        return true;
                    }

                    //Check all the siblings to the right
                    for (int i = m_nodeToSiblingNumber[currentChild] + 1; i < parent.Children.Count; i++)
                    {
                        if (parent.Children[i].GetNodeInfo(m_command).ExternalReferences.Overlaps(keys))
                        {
                            return true;
                        }
                    }
                }
                currentChild = parent;
            }
            return false;
        }

 /// <summary>
 /// Compute the hash value for this node
 /// </summary>
 /// <param name="cmd"></param>
 /// <param name="n"></param>
 internal override void ComputeHashValue(Command cmd, Node n)
 {
     base.ComputeHashValue(cmd, n);
     m_hashValue = (m_hashValue << 4) ^ GetHashValue(Definitions);
     m_hashValue = (m_hashValue << 4) ^ GetHashValue(Keys.KeyVars);
     return;
 }

        internal Node ReMap(Node node, Dictionary<Var, Node> varMap)
        {
            PlanCompiler.Assert(node.Op.IsScalarOp, "Expected a scalarOp: Found " + Dump.AutoString.ToString(node.Op.OpType));

            // Replace varRefOps by the corresponding expression in the map, if any
            if (node.Op.OpType
                == OpType.VarRef)
            {
                var varRefOp = node.Op as VarRefOp;
                Node newNode = null;
                if (varMap.TryGetValue(varRefOp.Var, out newNode))
                {
                    newNode = Copy(newNode);
                    return newNode;
                }
                else
                {
                    return node;
                }
            }

            // Simply process the result of the children.
            for (var i = 0; i < node.Children.Count; i++)
            {
                node.Children[i] = ReMap(node.Children[i], varMap);
            }

            // We may have changed something deep down
            Command.RecomputeNodeInfo(node);
            return node;
        }

        /// <summary>
        /// Convert a 
        ///    SingleRowOp(X) => X
        /// if X produces at most one row
        /// </summary>
        /// <param name="context">Rule Processing context</param>
        /// <param name="singleRowNode">Current subtree</param>
        /// <param name="newNode">transformed subtree</param>
        /// <returns>Transformation status</returns>
        private static bool ProcessSingleRowOpOverAnything(RuleProcessingContext context, Node singleRowNode, out Node newNode)
        {
            newNode = singleRowNode;
            var trc = (TransformationRulesContext)context;
            var childNodeInfo = context.Command.GetExtendedNodeInfo(singleRowNode.Child0);

            // If the input to this Op can produce at most one row, then we don't need the
            // singleRowOp - simply return the input
            if (childNodeInfo.MaxRows
                <= RowCount.One)
            {
                newNode = singleRowNode.Child0;
                return true;
            }

            //
            // if the current node is a FilterOp, then try and determine if the FilterOp
            // produces one row at most
            //
            if (singleRowNode.Child0.Op.OpType
                == OpType.Filter)
            {
                var predicate = new Predicate(context.Command, singleRowNode.Child0.Child1);
                if (predicate.SatisfiesKey(childNodeInfo.Keys.KeyVars, childNodeInfo.Definitions))
                {
                    childNodeInfo.MaxRows = RowCount.One;
                    newNode = singleRowNode.Child0;
                    return true;
                }
            }

            // we couldn't do anything
            return false;
        }

        /// <summary>
        /// Utility method that determines whether a given CaseOp subtree can be optimized.
        /// Called by both PreProcessor and NominalTypeEliminator.
        /// 
        /// If the case statement is of the shape:
        ///     case when X then NULL else Y, or
        ///     case when X then Y else NULL,
        /// where Y is of row type, and the types of the input CaseOp, the NULL and Y are the same,
        /// return true
        /// </summary>
        /// <param name="op"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        internal static bool IsRowTypeCaseOpWithNullability(CaseOp op, Node n, out bool thenClauseIsNull)
        {
            thenClauseIsNull = false;  //any default value will do

            if (!TypeSemantics.IsRowType(op.Type))
            {
                return false;
            }
            if (n.Children.Count != 3)
            {
                return false;
            }

            //All three types must be equal
            if (!n.Child1.Op.Type.EdmEquals(op.Type) || !n.Child2.Op.Type.EdmEquals(op.Type))
            {
                return false;
            }

            //At least one of Child1 and Child2 needs to be a null
            if (n.Child1.Op.OpType == OpType.Null)
            {
                thenClauseIsNull = true;
                return true;
            }
            if (n.Child2.Op.OpType == OpType.Null)
            {
                // thenClauseIsNull stays false
                return true;
            }

            return false;
        }

        /// <summary>
        /// Process a SetOp when one of the inputs is an emptyset. 
        /// 
        /// An emptyset is represented by a Filter(X, ConstantPredicate)
        ///    where the ConstantPredicate has a value of "false"
        /// 
        /// The general rules are
        ///    UnionAll(X, EmptySet) => X
        ///    UnionAll(EmptySet, X) => X
        ///    Intersect(EmptySet, X) => EmptySet
        ///    Intersect(X, EmptySet) => EmptySet
        ///    Except(EmptySet, X) => EmptySet
        ///    Except(X, EmptySet) => X
        /// 
        /// These rules then translate into 
        ///    UnionAll: return the non-empty input
        ///    Intersect: return the empty input
        ///    Except: return the "left" input 
        /// </summary>
        /// <param name="context">Rule processing context</param>
        /// <param name="setOpNode">the current setop tree</param>
        /// <param name="filterNodeIndex">Index of the filter node in the setop</param>
        /// <param name="newNode">transformed subtree</param>
        /// <returns>transformation status</returns>
        private static bool ProcessSetOpOverEmptySet(RuleProcessingContext context, Node setOpNode, out Node newNode)
        {
            var leftChildIsEmptySet = context.Command.GetExtendedNodeInfo(setOpNode.Child0).MaxRows == RowCount.Zero;
            var rightChildIsEmptySet = context.Command.GetExtendedNodeInfo(setOpNode.Child1).MaxRows == RowCount.Zero;

            if (!leftChildIsEmptySet
                && !rightChildIsEmptySet)
            {
                newNode = setOpNode;
                return false;
            }

            int indexToReturn;
            var setOp = (SetOp)setOpNode.Op;
            if (!rightChildIsEmptySet && setOp.OpType == OpType.UnionAll
                ||
                !leftChildIsEmptySet && setOp.OpType == OpType.Intersect)
            {
                indexToReturn = 1;
            }
            else
            {
                indexToReturn = 0;
            }

            newNode = setOpNode.Children[indexToReturn];

            var trc = (TransformationRulesContext)context;
            foreach (var kv in setOp.VarMap[indexToReturn])
            {
                trc.AddVarMapping(kv.Key, kv.Value);
            }
            return true;
        }

 /// <summary>
 /// Update vars in just this node (and not the entire subtree) 
 /// Does *not* recompute the nodeinfo - there are at least some consumers of this
 /// function that do not want the recomputation - transformation rules, for example
 /// </summary>
 /// <param name="node">current node</param>
 internal virtual void RemapNode(Node node)
 {
     if (m_varMap.Count == 0)
     {
         return;
     }
     VisitNode(node);
 }

 /// <summary>
 /// Equivalent to OpCopier.Copy, only in addition it keeps track of the defining subtrees
 /// of collection vars defined in the subtree rooted at the copy of the input node n.
 /// </summary>
 /// <param name="cmd"></param>
 /// <param name="n"></param>
 /// <param name="varMap"></param>
 /// <param name="newCollectionVarDefinitions"></param>
 /// <returns></returns>
 internal static Node Copy(Command cmd, Node n, out VarMap varMap, out Dictionary<Var, Node> newCollectionVarDefinitions)
 {
     var oc = new OpCopierTrackingCollectionVars(cmd);
     var newNode = oc.CopyNode(n);
     varMap = oc.m_varMap;
     newCollectionVarDefinitions = oc.m_newCollectionVarDefinitions;
     return newNode;
 }

 protected static void AssertArity(Node n)
 {
     if (n.Op.Arity
         != Op.ArityVarying)
     {
         AssertArity(n, n.Op.Arity);
     }
 }

        // List of columns of this table that are nullable (and must have nulls pruned out)

        #endregion

        #region constructors

        /// <summary>
        /// Basic constructor
        /// </summary>
        /// <param name="id">node id</param>
        /// <param name="node">scan table node</param>
        internal AugmentedTableNode(int id, Node node)
            : base(id, node)
        {
            var scanTableOp = (ScanTableOp)node.Op;
            m_table = scanTableOp.Table;
            LastVisibleId = id;
            m_replacementTable = this;
            m_newLocationId = id;
        }

 /// <summary>
 /// Tracks the information that the given node is a parent of its children (one level only)
 /// </summary>
 /// <param name="parent"></param>
 internal void AddChildren(Node parent)
 {
     for(int i=0; i< parent.Children.Count; i++)
     {                
         //We do not use add on purpose, we may be updating a child's parent after join elimination in a subtree
         m_nodeToParentMap[parent.Children[i]] = parent;
         m_nodeToSiblingNumber[parent.Children[i]] = i;
     }
 }