ITreeGenerator.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / Orcas / NetFXw7 / ndp / fx / src / DataEntity / System / Data / Query / PlanCompiler / ITreeGenerator.cs / 1 / ITreeGenerator.cs

                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....], [....]
//--------------------------------------------------------------------- 
 
using System;
using System.Collections.Generic; 
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Text;

using System.Data; 
using System.Data.Common;
using System.Data.Metadata.Edm; 
using System.Data.Common.CommandTrees; 
using System.Data.Common.CommandTrees.Internal;
using System.Data.Query.InternalTrees; 

namespace System.Data.Query.PlanCompiler
{
    internal class ITreeGenerator : DbExpressionVisitor 
    {
        #region Nested Types 
        ///  
        /// Abstract base class for both DbExpressionBinding and LambdaFunction scopes
        ///  
        private abstract class CqtVariableScope
        {
            internal abstract bool Contains(string varName);
            internal abstract Node this[string varName] { get; } 
        }
 
        ///  
        /// Represents a variable scope introduced by a CQT DbExpressionBinding, and therefore contains a single variable.
        ///  
        private class ExpressionBindingScope : CqtVariableScope
        {
            private Command _tree;
            private string _varName; 
            private Var _var;
 
            internal ExpressionBindingScope(Command iqtTree, string name, Var iqtVar) 
            {
                _tree = iqtTree; 
                _varName = name;
                _var = iqtVar;
            }
 
            internal override bool Contains(string name) { return (_varName == name); }
            internal override Node this[string name] 
            { 
                get
                { 
                    PlanCompiler.Assert(name == _varName,"huh?");
                    return _tree.CreateNode(_tree.CreateVarRefOp(_var));
                }
            } 

            internal Var ScopeVar { get { return _var; } } 
        } 

        ///  
        /// Represents a variable scope introduced by a LambdaFunction.
        /// 
        private class LambdaScope : CqtVariableScope
        { 
            private ITreeGenerator _treeGen;
            private Command _command; 
            private Dictionary _arguments; 
            private Dictionary _referencedArgs;
 
            internal LambdaScope(ITreeGenerator treeGen, Command command, Dictionary args)
            {
                _treeGen = treeGen;
                _command = command; 
                _arguments = args;
                _referencedArgs = new Dictionary(_arguments.Count); 
            } 

            internal override bool Contains(string name) { return (_arguments.ContainsKey(name)); } 
            internal override Node this[string name]
            {
                get
                { 
                    PlanCompiler.Assert(_arguments.ContainsKey(name), "LambdaScope indexer called for invalid Var");
 
                    Node argNode = _arguments[name]; 
                    if (_referencedArgs.ContainsKey(argNode))
                    { 
                        // The specified argument has already been substituted into the
                        // IQT and so this substitution requires a copy of the argument.
                        VarMap mappedVars = null;
 
                        // This is a 'deep copy' operation that clones the entire subtree rooted at the node.
                        Node argCopy = OpCopier.Copy(_command, argNode, out mappedVars); 
 
                        // If any Nodes in the copy of the argument produce Vars then the
                        // Node --> Var map must be updated to include them. 
                        if (mappedVars.Count > 0)
                        {
                            List sources = new List(1);
                            sources.Add(argNode); 

                            List copies = new List(1); 
                            copies.Add(argCopy); 

                            MapCopiedNodeVars(sources, copies, mappedVars); 
                        }

                        argNode = argCopy;
                    } 
                    else
                    { 
                        // This is the first reference of the lambda argument, so the Node itself 
                        // can be returned rather than a copy, but the dictionary that tracks
                        // whether or not an argument has been referenced needs to be updated. 
                        _referencedArgs[argNode] = true;
                    }

                    return argNode; 
                }
            } 
 
            private void MapCopiedNodeVars(IList sources, IList copies, Dictionary varMappings)
            { 
                PlanCompiler.Assert(sources.Count == copies.Count, "Source/Copy Node count mismatch");

                //
                // For each Source/Copy Node in the two lists: 
                // - Recursively update the Node --> Var map for any child nodes
                // - If the Source Node is mapped to a Var, then retrieve the new Var 
                //   produced by the Op copier that corresponds to that Source Var, and 
                //   add an entry to the Node --> Var map that maps the Copy Node to the
                //   new Var. 
                //
                for (int idx = 0; idx < sources.Count; idx++)
                {
                    Node sourceNode = sources[idx]; 
                    Node copyNode = copies[idx];
 
                    if (sourceNode.Children.Count > 0) 
                    {
                        MapCopiedNodeVars(sourceNode.Children, copyNode.Children, varMappings); 
                    }

                    Var sourceVar = null;
                    if (_treeGen.VarMap.TryGetValue(sourceNode, out sourceVar)) 
                    {
                        PlanCompiler.Assert(varMappings.ContainsKey(sourceVar), "No mapping found for Var in Var to Var map from OpCopier"); 
                        this._treeGen.VarMap[copyNode] = varMappings[sourceVar]; 
                    }
                } 
            }
        }
        #endregion
 
        private static Dictionary s_opMap = InitializeExpressionKindToOpTypeMap();
 
        private readonly Command _iqtCommand; 
        private readonly Stack _varScopes = new Stack();
        private readonly Dictionary _varMap = new Dictionary(); 

        // leverage discriminator metadata in the top-level project when translating query mapping views...
        private readonly System.Data.Mapping.ViewGeneration.DiscriminatorMap _discriminatorMap;
        private readonly DbProjectExpression _discriminatedViewTopProject; 

 
        ///  
        /// Initialize the DbExpressionKind --> OpType mappings for DbComparisonExpression and DbArithmeticExpression
        ///  
        private static Dictionary InitializeExpressionKindToOpTypeMap()
        {
            Dictionary opMap = new Dictionary(12);
 
            //
            // Arithmetic operators 
            // 
            opMap[DbExpressionKind.Plus] = OpType.Plus;
            opMap[DbExpressionKind.Minus] = OpType.Minus; 
            opMap[DbExpressionKind.Multiply] = OpType.Multiply;
            opMap[DbExpressionKind.Divide] = OpType.Divide;
            opMap[DbExpressionKind.Modulo] = OpType.Modulo;
            opMap[DbExpressionKind.UnaryMinus] = OpType.UnaryMinus; 

            // 
            // Comparison operators 
            //
            opMap[DbExpressionKind.Equals] = OpType.EQ; 
            opMap[DbExpressionKind.NotEquals] = OpType.NE;
            opMap[DbExpressionKind.LessThan] = OpType.LT;
            opMap[DbExpressionKind.GreaterThan] = OpType.GT;
            opMap[DbExpressionKind.LessThanOrEquals] = OpType.LE; 
            opMap[DbExpressionKind.GreaterThanOrEquals] = OpType.GE;
 
            return opMap; 
        }
 
        internal Dictionary VarMap { get { return _varMap; } }

        public static Command Generate(DbQueryCommandTree ctree)
        { 
            return Generate(ctree, null);
        } 
 
        /// 
        /// Generate an IQT given a query command tree and discriminator metadata (available for certain query mapping views) 
        /// 
        internal static Command Generate(DbQueryCommandTree ctree, System.Data.Mapping.ViewGeneration.DiscriminatorMap discriminatorMap)
        {
            ITreeGenerator treeGenerator = new ITreeGenerator(ctree, discriminatorMap); 
            return treeGenerator._iqtCommand;
        } 
 
        private ITreeGenerator(DbQueryCommandTree ctree, System.Data.Mapping.ViewGeneration.DiscriminatorMap discriminatorMap)
        { 
            //
            // Create a new IQT Command instance that uses the same metadata workspace and data space as the incoming command tree
            //
            _iqtCommand = new Command(ctree.MetadataWorkspace, ctree.DataSpace); 

            // 
            // When translating a query mapping view matching the TPH discrimination pattern, remember the top level discriminator map 
            // (leveraged to produced a DiscriminatedNewInstanceOp for the top-level projection in the view)
            // 
            if (null != discriminatorMap)
            {
                _discriminatorMap = discriminatorMap;
                // see System.Data.Mapping.ViewGeneration.DiscriminatorMap 
                PlanCompiler.Assert(ctree.Query.ExpressionKind == DbExpressionKind.Project,
                    "top level QMV expression must be project to match discriminator pattern"); 
                _discriminatedViewTopProject = (DbProjectExpression)ctree.Query; 
            }
 
            //
            // for each Parameter declared by the command tree, add a ParameterVar to the set of parameter vars maintained by the conversion visitor.
            // Each ParameterVar has the same name and type as the corresponding parameter on the command tree.
            // 
            foreach (KeyValuePair paramInfo in ctree.Parameters)
            { 
                _iqtCommand.CreateParameterVar(paramInfo.Key, paramInfo.Value); 
            }
 
            // Convert into an ITree
            _iqtCommand.Root = VisitExpr(ctree.Query);

            // 
            // If the root of the tree is not a relop, build up a fake project over a
            // a singlerowtableOp. 
            //   "s" => Project(SingleRowTableOp, "s") 
            //
            if (!_iqtCommand.Root.Op.IsRelOp) 
            {
                Node scalarExpr = ConvertToScalarOpTree(_iqtCommand.Root, ctree.Query);
                Node singletonTableNode = _iqtCommand.CreateNode(_iqtCommand.CreateSingleRowTableOp());
                Var newVar; 
                Node varDefListNode = _iqtCommand.CreateVarDefListNode(scalarExpr, out newVar);
                ProjectOp projectOp = _iqtCommand.CreateProjectOp(newVar); 
 

                Node newRoot = _iqtCommand.CreateNode(projectOp, singletonTableNode, varDefListNode); 

                if (TypeSemantics.IsCollectionType(_iqtCommand.Root.Op.Type))
                {
                    UnnestOp unnestOp = _iqtCommand.CreateUnnestOp(newVar); 
                    newRoot = _iqtCommand.CreateNode(unnestOp, varDefListNode.Child0);
                    newVar = unnestOp.Table.Columns[0]; 
                } 

                _iqtCommand.Root = newRoot; 
                _varMap[_iqtCommand.Root] = newVar;

            }
 

            // 
            // Ensure that the topmost portion of the query is capped by a 
            // PhysicalProject expression
            // 
            _iqtCommand.Root = CapWithPhysicalProject(_iqtCommand.Root);
        }

        #region DbExpressionVisitor Helpers 

        private static RowType ExtractElementRowType(TypeUsage typeUsage) 
        { 
            return TypeHelpers.GetEdmType(TypeHelpers.GetEdmType(typeUsage).TypeUsage);
        } 

#if DEBUG
        private static bool IsCollectionOfRecord(TypeUsage typeUsage)
        { 
            CollectionType collectionType;
            return (TypeHelpers.TryGetEdmType(typeUsage, out collectionType) && 
                    collectionType != null && 
                    TypeSemantics.IsRowType(collectionType.TypeUsage));
        } 
#endif

        /// 
        /// Is the current expression a predicate? 
        /// 
        /// expr to check 
        /// true, if the expression is a predicate 
        private bool IsPredicate(DbExpression expr)
        { 
            if (TypeSemantics.IsPrimitiveType(expr.ResultType, PrimitiveTypeKind.Boolean))
            {
                switch (expr.ExpressionKind)
                { 
                    case DbExpressionKind.Equals:
                    case DbExpressionKind.NotEquals: 
                    case DbExpressionKind.LessThan: 
                    case DbExpressionKind.LessThanOrEquals:
                    case DbExpressionKind.GreaterThan: 
                    case DbExpressionKind.GreaterThanOrEquals:
                    case DbExpressionKind.And:
                    case DbExpressionKind.Or:
                    case DbExpressionKind.Not: 
                    case DbExpressionKind.Like:
                    case DbExpressionKind.IsEmpty: 
                    case DbExpressionKind.IsNull: 
                    case DbExpressionKind.IsOf:
                    case DbExpressionKind.IsOfOnly: 
                    case DbExpressionKind.Any:
                    case DbExpressionKind.All:
                        return true;
                    case DbExpressionKind.Function: 
                        //
                        DbFunctionExpression fe = expr as DbFunctionExpression; 
                        return (null != fe && fe.IsLambda) ? IsPredicate(fe.LambdaBody) : false; 
                    default:
                        return false; 
                }
            }
            else
            { 
                return false;
            } 
        } 

        ///  
        /// Callback to process an expression
        /// 
        /// The expression to convert
        ///  
        private delegate Node VisitExprDelegate(DbExpression e);
 
        private Node VisitExpr(DbExpression e) 
        {
            if (e == null) 
            {
                return null;
            }
            else 
            {
                return e.Accept(this); 
            } 
        }
 
        /// 
        /// Convert this expression into a "scalar value" ITree expression. There are two main
        /// 
        ///  
        /// 
        private Node VisitExprAsScalar(DbExpression expr) 
        { 
            if (expr == null)
            { 
                return null;
            }

            Node node = VisitExpr(expr); // the real work 
            node = ConvertToScalarOpTree(node, expr);
            return node; 
        } 

        ///  
        /// Convert an Itree node into a scalar op tree
        /// 
        /// the subtree
        /// the original CQT expression 
        /// the converted subtree
        private Node ConvertToScalarOpTree(Node node, DbExpression expr) 
        { 
            //
            // If the current expression is a collection, and we've simply produced a RelOp 
            // then we need to add a CollectOp above a PhysicalProjectOp above the RelOp
            //
            if (node.Op.IsRelOp)
            { 
                PlanCompiler.Assert(TypeSemantics.IsCollectionType(expr.ResultType), "RelOp with non-Collection result type");
                CollectOp collectOp = _iqtCommand.CreateCollectOp(expr.ResultType); 
                // 
                // I'm not thrilled about having to build a PhysicalProjectOp here - this
                // is definitely something I will need to revisit soon 
                //
                Node projectNode = CapWithPhysicalProject(node);
                node = _iqtCommand.CreateNode(collectOp, projectNode);
            } 
            //
            // If the current expression is a boolean, and it is really a predicate, then 
            // scalarize the predicate (ie) convert it into a "case when  then 'true' else 'false' end" expression 
            // SQLBUDT #431406: handle 3-valued logic for all predicates except IsNull
            // Convert boolean predicate p into 
            //    case when p then true when not(p) then false else null end
            //
            else if (IsPredicate(expr))
            { 
                CaseOp caseOp = _iqtCommand.CreateCaseOp(_iqtCommand.BooleanType);
 
                //For 2-valued logic there are 3 arguments, for 3-valued there are 5 
                List arguments = new List((expr.ExpressionKind == DbExpressionKind.IsNull) ? 3 : 5);
 
                //Add the original as the first when
                arguments.Add(node);

                //Add the first then, the true node 
                arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, true)));
 
                //If the expression has 3-valued logic, add a second when 
                if (expr.ExpressionKind != DbExpressionKind.IsNull)
                { 
                    Node predCopy = VisitExpr(expr);
                    arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateConditionalOp(OpType.Not), predCopy));
                }
 
                //Add the false node: for 3 valued logic this is the second then, for 2 valued the else
                arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, false))); 
 
                //The null node, it is the else-clause for 3-valued logic
                if (expr.ExpressionKind != DbExpressionKind.IsNull) 
                {
                    arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.BooleanType)));
                }
 
                node = _iqtCommand.CreateNode(caseOp, arguments);
            } 
 
            return node;
        } 

        /// 
        /// Convert an expression into an iqt predicate
        ///  
        /// the expression to process
        ///  
        private Node VisitExprAsPredicate(DbExpression expr) 
        {
            if (expr == null) 
            {
                return null;
            }
 
            Node node = VisitExpr(expr);
 
            // 
            // If the current expression is not a predicate, then we need to make it one, by
            // comparing it with the constant 'true' 
            //
            if (!IsPredicate(expr))
            {
                ComparisonOp comparisonOp = _iqtCommand.CreateComparisonOp(OpType.EQ); 
                Node trueNode = _iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, true));
                node = _iqtCommand.CreateNode(comparisonOp, node, trueNode); 
            } 
            else
            { 
                PlanCompiler.Assert(!node.Op.IsRelOp, "unexpected relOp as predicate?");
            }

            return node; 
        }
 
        ///  
        /// Process a list of expressions, and apply the delegate to each of the expressions
        ///  
        /// list of cqt expressions to process
        /// the callback to apply
        /// a list of IQT expressions
        private static IList VisitExpr(IList exprs, VisitExprDelegate exprDelegate) 
        {
            List nodeList = new List(); 
            for(int idx = 0; idx < exprs.Count; idx++) 
            {
                nodeList.Add(exprDelegate(exprs[idx])); 
            }
            return nodeList;
        }
 
        /// 
        /// Process a set of cqt expressions - and convert them into scalar iqt expressions 
        ///  
        /// list of cqt expressions
        /// list of iqt expressions 
        private IList VisitExprAsScalar(IList exprs)
        {
            return VisitExpr(exprs, VisitExprAsScalar);
        } 

        private Node VisitUnary(DbUnaryExpression e, Op op, VisitExprDelegate exprDelegate) 
        { 
            return _iqtCommand.CreateNode(op, exprDelegate(e.Argument));
        } 

        private Node VisitBinary(DbBinaryExpression e, Op op, VisitExprDelegate exprDelegate)
        {
            return _iqtCommand.CreateNode(op, exprDelegate(e.Left), exprDelegate(e.Right)); 
        }
 
        ///  
        /// Ensures that an input op is a RelOp. If the specified Node's Op is not a RelOp then it is wrapped in an Unnest to create a synthetic RelOp. This is only possible if the input Op produces a collection.
        ///  
        /// The input Node/Op pair
        /// A Node with an Op that is guaranteed to be a RelOp (this may be the original Node or a new Node created to perform the Unnest)
        private Node EnsureRelOp(Node inputNode)
        { 
            //
            // Input node = N1 
            // 
            Op inputOp = inputNode.Op;
 
            //
            // If the Op is already a RelOp then simply return its Node
            //
            if (inputOp.IsRelOp) 
            {
                return inputNode; 
            } 

            // 
            // Assert that the input is a ScalarOp (CQT expressions should only ever produce RelOps or ScalarOps)
            //
            ScalarOp scalar = inputOp as ScalarOp;
            PlanCompiler.Assert(scalar != null, "An expression in a CQT produced a non-ScalarOp and non-RelOp output Op"); 

            // 
            // Assert that the ScalarOp has a collection result type. EnsureRelOp is called to ensure that arguments to 
            // RelOps are either also RelOps or are ScalarOps that produce a collection, which can be wrapped in an
            // unnest to produce a RelOp. 
            //
            PlanCompiler.Assert(TypeSemantics.IsCollectionType(scalar.Type), "An expression used as a RelOp argument was neither a RelOp or a collection");

            // 
            // If the ScalarOp represents the nesting of an existing RelOp, simply return that RelOp instead.
            // CollectOp(PhysicalProjectOp(x)) => x 
            // 
            CollectOp collect = inputOp as CollectOp;
            if (collect != null) 
            {
                PlanCompiler.Assert(inputNode.HasChild0, "CollectOp without argument");
                if (inputNode.Child0.Op as PhysicalProjectOp != null)
                { 
                    PlanCompiler.Assert(inputNode.Child0.HasChild0, "PhysicalProjectOp without argument");
                    PlanCompiler.Assert(inputNode.Child0.Child0.Op.IsRelOp, "PhysicalProjectOp applied to non-RelOp input"); 
 
                    //
                    // The structure of the Input is Collect(PhysicalProject(x)), so return x 
                    //
                    return inputNode.Child0.Child0;
                }
            } 

            // 
            // Create a new VarDefOp that defines the computed var that represents the ScalarOp collection. 
            // This var is the input to the UnnestOp.
            // varDefNode = N2 
            //
            Var inputCollectionVar;
            Node varDefNode = _iqtCommand.CreateVarDefNode(inputNode, out inputCollectionVar);
 
            //
            // Create an UnnestOp that references the computed var created above. The VarDefOp that defines the var 
            // using the original input Node/Op pair becomes a child of the UnnestOp. 
            //
            UnnestOp unnest = _iqtCommand.CreateUnnestOp(inputCollectionVar); 
            PlanCompiler.Assert(unnest.Table.Columns.Count == 1, "Unnest of collection ScalarOp produced unexpected number of columns (1 expected)");

            //
            // Create the unnest node, N3 
            // The UnnestOp produces a new Var, the single ColumnVar produced by the table that results from the Unnest.
            // 
            Node unnestNode = _iqtCommand.CreateNode(unnest, varDefNode); 
            _varMap[unnestNode] = unnest.Table.Columns[0];
 
            //
            // Create a Project node above the Unnest, so we can simplify the work to eliminate
            // the Unnest later.  That means we need to create a VarRef to the column var in the
            // table, a VarDef to define it, and a VarDefList to hold it, then a Project node, N4, 
            // which we return.
            // 
            Var projectVar; 
            Node varRefNode = _iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(unnest.Table.Columns[0]));
            Node varDefListNode = _iqtCommand.CreateVarDefListNode(varRefNode, out projectVar); 

            ProjectOp projectOp = _iqtCommand.CreateProjectOp(projectVar);
            Node projectNode = _iqtCommand.CreateNode(projectOp, unnestNode, varDefListNode);
 
            _varMap[projectNode] = projectVar;
 
            return projectNode; 
        }
 
        /// 
        /// Cap a RelOp with a ProjectOp. The output var of the Project is the
        /// output var from the input
        ///  
        /// the input relop tree
        /// the relop tree with a projectNode at the root 
        private Node CapWithProject(Node input) 
        {
            PlanCompiler.Assert(input.Op.IsRelOp, "unexpected non-RelOp?"); 
            if (input.Op.OpType == OpType.Project)
            {
                return input;
            } 

            // Get the Var from the input; and build up a Project above it 
            Var inputVar = _varMap[input]; 
            ProjectOp projectOp = _iqtCommand.CreateProjectOp(inputVar);
            Node projectNode = _iqtCommand.CreateNode(projectOp, input, 
               _iqtCommand.CreateNode(_iqtCommand.CreateVarDefListOp()));
            _varMap[projectNode] = inputVar;

            return projectNode; 
        }
 
        ///  
        /// Cap a relop tree with a PhysicalProjectOp. The Vars of the PhysicalProjectOp
        /// are the vars from the RelOp tree 
        /// 
        /// the input relop tree
        /// relop tree capped by a PhysicalProjectOp
        private Node CapWithPhysicalProject(Node input) 
        {
            PlanCompiler.Assert(input.Op.IsRelOp, "unexpected non-RelOp?"); 
 
            // Get the Var from the input; and build up a Project above it
            Var inputVar = _varMap[input]; 
            PhysicalProjectOp projectOp = _iqtCommand.CreatePhysicalProjectOp(inputVar);
            Node projectNode = _iqtCommand.CreateNode(projectOp, input);

            return projectNode; 
        }
 
        ///  
        /// Creates a new variable scope that is based on a CQT DbExpressionBinding and pushes it onto the variable scope stack. The scope defines a single variable based on the DbExpressionBinding's VarName and DbExpression.
        ///  
        /// The DbExpressionBinding that defines the scope
        /// The Node produced by converting the binding's DbExpression
        private Node EnterExpressionBinding(DbExpressionBinding binding)
        { 
            return PushBindingScope(binding.Expression, binding.VariableName);
        } 
 
        /// 
        /// Creates a new variable scope that is based on a CQT DbGroupExpressionBinding and pushes it onto the variable scope stack. The scope defines a single variable based on the DbExpressionBinding's VarName and DbExpression. 
        /// This method does not bring the GroupVarName into scope. Note that ExitExpressionBinding and NOT ExitGroupExpressionBinding should be used to remove this scope from the stack.
        /// 
        /// The DbGroupExpressionBinding that defines the scope
        /// The Node produced by converting the binding's DbExpression 
        private Node EnterGroupExpressionBinding(DbGroupExpressionBinding binding)
        { 
            return PushBindingScope(binding.Expression, binding.VariableName); 
        }
 
        /// 
        /// Common implementation method called by both EnterExpressionBinding and EnterGroupExpressionBinding
        /// 
        /// The DbExpression that defines the binding 
        /// The name of the binding variable
        ///  
        private Node PushBindingScope(DbExpression boundExpression, string bindingName) 
        {
            // 
            // Visit the DbExpressionBinding's DbExpression to convert it to a Node/Op pair
            //
            Node inputNode = VisitExpr(boundExpression);
            PlanCompiler.Assert(inputNode != null, "DbExpressionBinding.Expression produced null conversion"); 

            // 
            // Call EnsureRelOp on the converted Node and set inputNode equal to the result 
            //
            inputNode = EnsureRelOp(inputNode); 

            //
            // Retrieve the Var produced by the RelOp from the Node --> Var map
            // 
            Var boundVar = _varMap[inputNode];
            PlanCompiler.Assert(boundVar != null, "No Var found for Input Op"); 
 
            //
            // Create a new ExpressionBindingScope using the VarName from the DbExpressionBinding and 
            // the Var associated with the Input RelOp, and push the new scope onto the variable scope stack.
            //
            _varScopes.Push(new ExpressionBindingScope(_iqtCommand, bindingName, boundVar));
 
            //
            // Return the IQT conversion of the DbExpressionBinding's DbExpression. 
            // 
            return inputNode;
        } 

        /// 
        /// Removes a variable scope created based on a DbExpressionBinding from the top of the variable scope stack, verifying that it is in fact an ExpressionBindingScope.
        ///  
        /// The removed ExpressionBindingScope
        private ExpressionBindingScope ExitExpressionBinding() 
        { 
            //
            // Pop the scope from the variable scope stack, assert that it is a DbExpressionBinding scope, and return it. 
            //
            ExpressionBindingScope retScope = _varScopes.Pop() as ExpressionBindingScope;
            PlanCompiler.Assert(retScope != null, "ExitExpressionBinding called without ExpressionBindingScope on top of scope stack");
            return retScope; 
        }
 
        ///  
        /// Removes a variable scope created based on a DbGroupExpressionBinding from the top of the variable scope stack, verifying that it is in fact an ExpressionBindingScope.
        /// Should only be called after visiting the Aggregates of a DbGroupByExpression in Visit(DbGroupByExpression). 
        /// The sequence (in Visit(GroupExpression e) is:
        /// 1. EnterGroupExpressionBinding
        /// 2.     Visit e.Keys
        /// 3. ExitExpressionBinding 
        /// 4. (Push new scope with GroupVarName instead of VarName)
        /// 5.     Visit e.Aggregates 
        /// 6. ExitGroupExpressionBinding 
        /// 
        private void ExitGroupExpressionBinding() 
        {
            ExpressionBindingScope retScope = _varScopes.Pop() as ExpressionBindingScope;
            PlanCompiler.Assert(retScope != null, "ExitGroupExpressionBinding called without ExpressionBindingScope on top of scope stack");
        } 

        ///  
        /// Creates a new variable scope that is based on a CQT Lambda function and pushes it onto the variable scope stack. 
        /// 
        /// The Lambda function that defines the scope 
        /// A list of Nodes produced by converting the CQT Expressions that provide the arguments to the Lambda function
        private void EnterLambdaFunction(EdmFunction function, List argumentValues)
        {
            IList lambdaParams = function.Parameters; 
            if (lambdaParams.Count > 0)
            { 
                Dictionary args = new Dictionary(); 
                int idx = 0;
                foreach (Node argumentValue in argumentValues) 
                {
                    args.Add(lambdaParams[idx].Name, argumentValue);
                    idx++;
                } 

                _varScopes.Push(new LambdaScope(this, _iqtCommand, args)); 
            } 
        }
 
        /// 
        /// Removes a variable scope created based on a Lambda function from the top of the variable scope stack, verifying that it is in fact a LambdaScope.
        /// 
        ///  
        private LambdaScope ExitLambdaFunction()
        { 
            // 
            // Pop the scope from the variable scope stack, assert that it is a Lambda scope, and return it.
            // 
            LambdaScope retScope = _varScopes.Pop() as LambdaScope;
            PlanCompiler.Assert(retScope != null, "ExitLambdaFunction called without LambdaScope on top of scope stack");
            return retScope;
        } 

        ///  
        /// Constructs a NewRecordOp on top of a multi-Var-producing Op, resulting in a RelOp that produces a single Var. 
        /// 
        /// The Node that references the multi-Var-producing Op. This Node will become the first child node of the new ProjectOp's Node 
        /// Type metadata that describes the output record type
        /// A list of Vars that provide the output columns of the projection
        /// A new ProjectOp that projects a new record of the specified type from the specified Vars over the original input Op/Node
        private Node ProjectNewRecord(Node inputNode, RowType recType, IEnumerable colVars) 
        {
            // 
            // Create a list of VarRefOp Nodes that provide the column values for the new record 
            //
            List recordColumns = new List(); 
            foreach (Var colVar in colVars)
            {
                recordColumns.Add(_iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(colVar)));
            } 

            // 
            // Create the NewRecordOp Node using the record column nodes as its child nodes 
            //
            Node newRecordNode = _iqtCommand.CreateNode(_iqtCommand.CreateNewRecordOp(recType), recordColumns); 

            //
            // Create a new ComputedVar and a VarDefOp that uses the NewRecordOp Node to define it
            // 
            Var newRecordVar;
            Node varDefNode = _iqtCommand.CreateVarDefListNode(newRecordNode, out newRecordVar); 
 
            //
            // Create a ProjectOp with the single Computed Var defined by the new record construction 
            //
            ProjectOp projection = _iqtCommand.CreateProjectOp(newRecordVar);
            Node projectionNode = _iqtCommand.CreateNode(projection, inputNode, varDefNode);
            _varMap[projectionNode] = newRecordVar; 

            return projectionNode; 
        } 
        #endregion
 
        #region DbExpressionVisitor Members

        public override Node Visit(DbExpression e)
        { 
            throw EntityUtil.NotSupported(System.Data.Entity.Strings.Cqt_General_UnsupportedExpression(e.GetType().FullName));
        } 
 
        public override Node Visit(DbConstantExpression e)
        { 
            // Don't use CreateInternalConstantOp - respect user-intent
            ConstantBaseOp op = _iqtCommand.CreateConstantOp(e.ResultType, e.Value);
            return _iqtCommand.CreateNode(op);
        } 

        public override Node Visit(DbNullExpression e) 
        { 
            NullOp op = _iqtCommand.CreateNullOp(e.ResultType);
            return _iqtCommand.CreateNode(op); 
        }

        public override Node Visit(DbVariableReferenceExpression e)
        { 
            //
            // Search the stack of variables scopes, top-down, 
            // until the first one is found that defines a variable with the specified name. 
            //
            Node varNode = null; 
            foreach (CqtVariableScope scope in _varScopes)
            {
                if (scope.Contains(e.VariableName))
                { 
                    varNode = scope[e.VariableName];
                    break; 
                } 
            }
 
            //
            // If the variable name was not resolved then either:
            // 1. The original CQT was invalid (should not be allowed into the ITreeGenerator).
            // 2. The variable scope stack itself is invalid. 
            //
            PlanCompiler.Assert(varNode != null, "CQT VarRef could not be resolved in the variable scope stack"); 
 
            return varNode;
        } 

        public override Node Visit(DbParameterReferenceExpression e)
        {
            Op op = _iqtCommand.CreateVarRefOp(_iqtCommand.GetParameter(e.ParameterName)); 
            return _iqtCommand.CreateNode(op);
        } 
 
        public override Node Visit(DbFunctionExpression e)
        { 
            Node retNode = null;

            List argNodes = new List(e.Arguments.Count);
            int idx = 0; 
            foreach (DbExpression argExpr in e.Arguments)
            { 
                if (e.IsLambda) 
                {
                    // #484709: Lambda function parameters should not have enclosing SoftCastOps. 
                    argNodes.Add(VisitExpr(argExpr));
                }
                else
                { 
                    // Ensure that any argument with a result type that does not exactly match the type of
                    // the corresponding function parameter is enclosed in a SoftCastOp. 
                    argNodes.Add(BuildSoftCast(VisitExprAsScalar(argExpr), e.Function.Parameters[idx].TypeUsage)); 
                }
                idx++; 
            }

            if (e.LambdaBody != null)
            { 
                EnterLambdaFunction(e.Function, argNodes);
                retNode = VisitExpr(e.LambdaBody); 
                ExitLambdaFunction(); 
            }
            else 
            {
                retNode = _iqtCommand.CreateNode(_iqtCommand.CreateFunctionOp(e.Function), argNodes);
            }
 
            return retNode;
        } 
 
#if METHOD_EXPRESSION
        public override Node Visit(MethodExpression e) 
        {
            throw EntityUtil.NotSupported();
        }
#endif 
        #region SoftCast Helpers
        ///  
        /// This method builds a "soft"Cast operator over the input node (if necessary) to (soft) 
        /// cast it to the desired type (targetType)
        /// 
        /// If the input is a scalarOp, then we simply add on the SoftCastOp
        /// directly (if it is needed, of course). If the input is a RelOp, we create a
        /// new ProjectOp above the input, add a SoftCast above the Var of the
        /// input, and then return the new ProjectOp 
        ///
        /// The "need to cast" is determined by the Command.EqualTypes function. All type 
        /// equivalence in the plan compiler is determined by this function 
        /// 
        /// the expression to soft-cast 
        /// the desired type to cast to
        /// 
        private Node BuildSoftCast(Node node, TypeUsage targetType)
        { 
            //
            // If the input is a RelOp (say X), and the Var of the input is "x", 
            // we convert this into 
            //   Project(X, softCast(x, t))
            // where t is the element type of the desired target type 
            //
            if (node.Op.IsRelOp)
            {
                CollectionType targetCollectionType = TypeHelpers.GetEdmType(targetType); 
                targetType = targetCollectionType.TypeUsage;
 
                Var nodeVar = _varMap[node]; 
                // Do we need a cast at all?
                if (Command.EqualTypes(targetType, nodeVar.Type)) 
                {
                    return node;
                }
 
                // Build up the projectOp
                Var projectVar; 
                Node varRefNode = _iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(nodeVar)); 
                Node castNode = _iqtCommand.CreateNode(_iqtCommand.CreateSoftCastOp(targetType), varRefNode);
                Node varDefListNode = _iqtCommand.CreateVarDefListNode(castNode, out projectVar); 

                ProjectOp projectOp = _iqtCommand.CreateProjectOp(projectVar);
                Node projectNode = _iqtCommand.CreateNode(projectOp, node, varDefListNode);
 
                _varMap[projectNode] = projectVar;
                return projectNode; 
            } 
            else
            { 
                PlanCompiler.Assert(node.Op.IsScalarOp, "I want a scalar op");
                if (Command.EqualTypes(node.Op.Type, targetType))
                {
                    return node; 
                }
                else 
                { 
                    SoftCastOp castOp = _iqtCommand.CreateSoftCastOp(targetType);
                    return _iqtCommand.CreateNode(castOp, node); 
                }
            }
        }
 
        /// 
        /// A variant of the function above. Works with an EdmType instead 
        /// of a TypeUsage, but leverages all the work above 
        /// 
        /// the node to "cast" 
        /// the desired type
        /// the transformed expression
        private Node BuildSoftCast(Node node, EdmType targetType)
        { 
            return BuildSoftCast(node, TypeUsage.Create(targetType));
        } 
 
        private Node BuildEntityRef(Node arg, TypeUsage entityType)
        { 
            TypeUsage refType = TypeHelpers.CreateReferenceTypeUsage((EntityType)entityType.EdmType);
            return _iqtCommand.CreateNode(_iqtCommand.CreateGetEntityRefOp(refType), arg);
        }
 
        #endregion
 
        public override Node Visit(DbPropertyExpression e) 
        {
            // Only Properties, Relationship End and NavigationProperty members are supported. 
            if (BuiltInTypeKind.EdmProperty != e.Property.BuiltInTypeKind &&
                BuiltInTypeKind.AssociationEndMember != e.Property.BuiltInTypeKind &&
                BuiltInTypeKind.NavigationProperty != e.Property.BuiltInTypeKind)
            { 
                throw EntityUtil.NotSupported();
            } 
 
            Node retNode = null;
            Op op = _iqtCommand.CreatePropertyOp(e.Property); 
            if (null == e.Instance)
            {
                retNode = _iqtCommand.CreateNode(op);
            } 
            else
            { 
                Node instance = VisitExpr(e.Instance); 

                // 
                // Retrieving a property from a new instance constructor can be
                // simplified to just the node that provides the corresponding property.
                // For example, Property(Row(A = x, B = y), 'A') => x
                // All structured types (including association types) are considered. 
                //
                if (e.Instance.ExpressionKind == DbExpressionKind.NewInstance && 
                    Helper.IsStructuralType(e.Instance.ResultType.EdmType)) 
                {
                    // Retrieve the 'structural' members of the instance's type. 
                    // For Association types this should be only Association End members,
                    // while for Complex, Entity or Row types is should be only Properties.
                    System.Collections.IList propertyOrEndMembers = Helper.GetAllStructuralMembers(e.Instance.ResultType.EdmType);
 
                    // Find the position of the member with the same name as the retrieved
                    // member in the list of structural members. 
                    int memberIdx = -1; 
                    for (int idx = 0; idx < propertyOrEndMembers.Count; idx++)
                    { 
                        if (string.Equals(e.Property.Name, ((EdmMember)propertyOrEndMembers[idx]).Name, StringComparison.Ordinal))
                        {
                            memberIdx = idx;
                            break; 
                        }
                    } 
 
                    PlanCompiler.Assert(memberIdx > -1, "The specified property was not found");
 
                    // If the member was found, return the corresponding argument value
                    // to the new instance op.
                    retNode = instance.Children[memberIdx];
 
                    // Make sure the argument value has been "cast" to the return type
                    // of the property, if necessary. 
                    retNode = BuildSoftCast(retNode, e.ResultType); 
                }
                else 
                {
                    // Make sure that the input has been "cast" to the right type
                    instance = BuildSoftCast(instance, e.Property.DeclaringType);
                    retNode = _iqtCommand.CreateNode(op, instance); 
                }
            } 
 
            return retNode;
        } 

        public override Node Visit(DbComparisonExpression e)
        {
            Op op = _iqtCommand.CreateComparisonOp(s_opMap[e.ExpressionKind]); 

            Node leftArg = VisitExprAsScalar(e.Left); 
            Node rightArg = VisitExprAsScalar(e.Right); 

            TypeUsage commonType = TypeHelpers.GetCommonTypeUsage(e.Left.ResultType, e.Right.ResultType); 

            // Make sure that the inputs have been cast to the right types
            if (!Command.EqualTypes(e.Left.ResultType, e.Right.ResultType))
            { 
                leftArg = BuildSoftCast(leftArg, commonType);
                rightArg = BuildSoftCast(rightArg, commonType); 
            } 

            if (TypeSemantics.IsEntityType(commonType) && 
                (e.ExpressionKind == DbExpressionKind.Equals || e.ExpressionKind == DbExpressionKind.NotEquals))
            {
                // Entity (in)equality is implemented as ref (in)equality
                leftArg = BuildEntityRef(leftArg, commonType); 
                rightArg = BuildEntityRef(rightArg, commonType);
            } 
 
            return _iqtCommand.CreateNode(op, leftArg, rightArg);
        } 

        public override Node Visit(DbLikeExpression e)
        {
            return _iqtCommand.CreateNode( 
                _iqtCommand.CreateLikeOp(),
                VisitExpr(e.Argument), 
                VisitExpr(e.Pattern), 
                VisitExpr(e.Escape)
            ); 
        }

        private Node CreateLimitNode(Node inputNode, Node limitNode, bool withTies)
        { 
            //
            // Limit(Skip(x)) - which becomes ConstrainedSortOp - and Limit(Sort(x)) are special cases 
            // 
            Node retNode = null;
            if (OpType.ConstrainedSort == inputNode.Op.OpType && 
                OpType.Null == inputNode.Child2.Op.OpType)
            {
                //
                // The input was a DbSkipExpression which is now represented 
                // as a ConstrainedSortOp with a NullOp Limit. The Limit from
                // this DbLimitExpression can be merged into the input ConstrainedSortOp 
                // rather than creating a new ConstrainedSortOp. 
                //
                inputNode.Child2 = limitNode; 

                // If this DbLimitExpression specifies WithTies, the input ConstrainedSortOp must be
                // updated to reflect this (DbSkipExpression always produces a ConstrainedSortOp with
                // WithTies equal to false). 
                if (withTies)
                { 
                    ((ConstrainedSortOp)inputNode.Op).WithTies = true; 
                }
 
                retNode = inputNode;
            }
            else if (OpType.Sort == inputNode.Op.OpType)
            { 
                //
                // This DbLimitExpression is applying a limit to a DbSortExpression. 
                // The two expressions can be merged into a single ConstrainedSortOp 
                // rather than creating a new ConstrainedSortOp over the input SortOp.
                // 
                // The new ConstrainedSortOp has the same SortKeys as the input SortOp.
                // The returned Node will have the following children:
                // - The input to the Sort
                // - A NullOp to indicate no Skip operation is specified 
                // - The limit Node from the DbLimitExpression
                // 
                retNode = 
                    _iqtCommand.CreateNode(
                        _iqtCommand.CreateConstrainedSortOp(((SortOp)inputNode.Op).Keys, withTies), 
                        inputNode.Child0,
                        _iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.IntegerType)),
                        limitNode
                    ); 
            }
            else 
            { 
                //
                // The input to the Limit is neither ConstrainedSortOp or SortOp. 
                // A new ConstrainedSortOp must be created with an empty list of keys
                // and the following children:
                // - The input to the DbLimitExpression
                // - a NullOp to indicate that no Skip operation is specified 
                // - The limit Node from the DbLimitExpression
                // 
                retNode = 
                    _iqtCommand.CreateNode(
                        _iqtCommand.CreateConstrainedSortOp(new List(), withTies), 
                        inputNode,
                        _iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.IntegerType)),
                        limitNode
                    ); 
            }
 
            return retNode; 
        }
 
        public override Node Visit(DbLimitExpression expression)
        {
            //
            // Visit the Argument and retrieve its Var 
            //
            Node inputNode = EnsureRelOp(VisitExpr(expression.Argument)); 
            Var inputVar = _varMap[inputNode]; 

            // 
            // Visit the Limit ensuring that it is a scalar
            //
            Node limitNode = VisitExprAsScalar(expression.Limit);
 
            Node retNode;
            if(OpType.Project == inputNode.Op.OpType) 
            { 
                //
                // If the input to the DbLimitExpression is a projection, then apply the Limit operation to the 
                // input to the ProjectOp instead. This allows  Limit(Project(Skip(x))) and Limit(Project(Sort(x)))
                // to be treated in the same way as Limit(Skip(x)) and Limit(Sort(x)).
                // Note that even if the input to the projection is not a ConstrainedSortOp or SortOp, the
                // Limit operation is still pushed under the Project. 
                //
                inputNode.Child0 = CreateLimitNode(inputNode.Child0, limitNode, expression.WithTies); 
                retNode = inputNode; 
            }
            else 
            {
                //
                // Otherwise, apply the Limit operation directly to the input.
                // 
                retNode = CreateLimitNode(inputNode, limitNode, expression.WithTies);
            } 
 
            //
            // The output Var of the resulting Node is the same as the output Var of its input Node. 
            // If the input node is being returned (either because the Limit was pushed under a Project
            // or because the input was a ConstrainedSortOp that was simply updated with the Limit value)
            // then the Node -> Var map does not need to be updated.
            // 
            if(!object.ReferenceEquals(retNode, inputNode))
            { 
                _varMap[retNode] = inputVar; 
            }
 
            return retNode;
        }

        public override Node Visit(DbIsNullExpression e) 
        {
            // SQLBUDT #484294: We need to recognize and simplify IsNull - IsNull and IsNull - Not - IsNull 
            // This is the latest point where such patterns can be easily recognized. 
            // After this the input predicate would get translated into a case statement.
            bool isAlwaysFalse = false;  //true if IsNull - IsNull and IsNull - Not - IsNull is recognized 

            if (e.Argument.ExpressionKind == DbExpressionKind.IsNull)
            {
                isAlwaysFalse = true; 
            }
            else if (e.Argument.ExpressionKind == DbExpressionKind.Not) 
            { 
                DbNotExpression notExpression = (DbNotExpression)e.Argument;
                if (notExpression.Argument.ExpressionKind == DbExpressionKind.IsNull) 
                {
                    isAlwaysFalse = true;
                }
            } 

            Op op = _iqtCommand.CreateConditionalOp(OpType.IsNull); 
 
            //If we have recognized that the result is always false, return IsNull(true), to still have predicate as output.
            //This gets further simplified by transformation rules. 
            if (isAlwaysFalse)
            {
                return _iqtCommand.CreateNode(op, _iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, true)));
            } 

            Node argNode = VisitExprAsScalar(e.Argument); 
            if (TypeSemantics.IsEntityType(e.Argument.ResultType)) 
            {
                argNode = BuildEntityRef(argNode, e.Argument.ResultType); 
            }

            return _iqtCommand.CreateNode(op, argNode);
        } 

        public override Node Visit(DbArithmeticExpression e) 
        { 
            Op op = _iqtCommand.CreateArithmeticOp(s_opMap[e.ExpressionKind], e.ResultType);
            // Make sure that the inputs have been "cast" to the result type 
            // Assumption: The input type must be the same as the result type. Is this always true?
            List children = new List();
            foreach (DbExpression arg in e.Arguments)
            { 
                Node child = VisitExprAsScalar(arg);
                children.Add(BuildSoftCast(child, e.ResultType)); 
            } 
            return _iqtCommand.CreateNode(op, children);
        } 

        public override Node Visit(DbAndExpression e)
        {
            Op op = _iqtCommand.CreateConditionalOp(OpType.And); 
            return VisitBinary(e, op, VisitExprAsPredicate);
        } 
 
        public override Node Visit(DbOrExpression e)
        { 
            Op op = _iqtCommand.CreateConditionalOp(OpType.Or);
            return VisitBinary(e, op, VisitExprAsPredicate);
        }
 
        public override Node Visit(DbNotExpression e)
        { 
            Op op = _iqtCommand.CreateConditionalOp(OpType.Not); 
            return VisitUnary(e, op, VisitExprAsPredicate);
        } 

        public override Node Visit(DbDistinctExpression e)
        {
            Node inputSetNode = EnsureRelOp(VisitExpr(e.Argument)); 
            Var inputVar = _varMap[inputSetNode];
            Op distinctOp = _iqtCommand.CreateDistinctOp(inputVar); 
            Node distinctNode = _iqtCommand.CreateNode(distinctOp, inputSetNode); 
            _varMap[distinctNode] = inputVar;
            return distinctNode; 
        }

        public override Node Visit(DbElementExpression e)
        { 
            Op elementOp = _iqtCommand.CreateElementOp(e.ResultType);
            Node inputSetNode = EnsureRelOp(VisitExpr(e.Argument)); 
            Var inputVar = _varMap[inputSetNode]; 

            // 
            // Add a singleRowOp enforcer, as we are not guaranteed that the input
            // collection produces at most one row
            //
            inputSetNode = _iqtCommand.CreateNode(_iqtCommand.CreateSingleRowOp(), inputSetNode); 
            _varMap[inputSetNode] = inputVar;
 
            // add a fake projectNode 
            inputSetNode = CapWithProject(inputSetNode);
            return _iqtCommand.CreateNode(elementOp, inputSetNode); 
        }

        public override Node Visit(DbIsEmptyExpression e)
        { 
            //
            // IsEmpty(input set) --> Not(Exists(input set)) 
            // 
            Op existsOp = _iqtCommand.CreateExistsOp();
            Node inputSetNode = EnsureRelOp(VisitExpr(e.Argument)); 

            return _iqtCommand.CreateNode(
                _iqtCommand.CreateConditionalOp(OpType.Not),
                _iqtCommand.CreateNode(existsOp, inputSetNode) 
            );
        } 
 
        /// 
        /// Encapsulates the logic required to convert a SetOp (Except, Intersect, UnionAll) expression 
        /// into an IQT Node/Op pair.
        /// 
        /// The DbExceptExpression, DbIntersectExpression or DbUnionAllExpression to convert, as an instance of DbBinaryExpression
        /// A new IQT Node that references the ExceptOp, IntersectOp or UnionAllOp created based on the expression 
        private Node VisitSetOpExpression(DbBinaryExpression expression)
        { 
            PlanCompiler.Assert(DbExpressionKind.Except == expression.ExpressionKind || 
                         DbExpressionKind.Intersect == expression.ExpressionKind ||
                         DbExpressionKind.UnionAll == expression.ExpressionKind, 
                         "Non-SetOp DbExpression used as argument to VisitSetOpExpression");

            PlanCompiler.Assert(TypeSemantics.IsCollectionType(expression.ResultType), "SetOp DbExpression does not have collection result type?");
 
            // Visit the left and right collection arguments
            Node leftNode = EnsureRelOp(VisitExpr(expression.Left)); 
            Node rightNode = EnsureRelOp(VisitExpr(expression.Right)); 

            // 
            // Now the hard part. "Normalize" the left and right sides to
            // match the result type.
            //
            leftNode = BuildSoftCast(leftNode, expression.ResultType); 
            rightNode = BuildSoftCast(rightNode, expression.ResultType);
 
            // The SetOp produces a single Var of the same type as the element type of the expression's collection result type 
            Var outputVar = _iqtCommand.CreateSetOpVar(TypeHelpers.GetEdmType(expression.ResultType).TypeUsage);
 
            // Create VarMaps for the left and right arguments that map the output Var to the Var produced by the corresponding argument
            VarMap leftMap = new VarMap();
            leftMap.Add(outputVar, _varMap[leftNode]);
 
            VarMap rightMap = new VarMap();
            rightMap.Add(outputVar, _varMap[rightNode]); 
 
            // Create a SetOp that corresponds to the operation specified by the expression's DbExpressionKind
            Op setOp = null; 
            switch(expression.ExpressionKind)
            {
                case DbExpressionKind.Except:
                    setOp = _iqtCommand.CreateExceptOp(leftMap, rightMap); 
                    break;
 
                case DbExpressionKind.Intersect: 
                    setOp = _iqtCommand.CreateIntersectOp(leftMap, rightMap);
                    break; 

                case DbExpressionKind.UnionAll:
                    setOp = _iqtCommand.CreateUnionAllOp(leftMap, rightMap);
                    break; 
            }
 
            // Create a new Node that references the SetOp 
            Node setOpNode = _iqtCommand.CreateNode(setOp, leftNode, rightNode);
 
            // Update the Node => Var map with an entry that maps the new Node to the output Var
            _varMap[setOpNode] = outputVar;

            // Return the newly created SetOp Node 
            return setOpNode;
        } 
 
        public override Node Visit(DbUnionAllExpression e)
        { 
            return VisitSetOpExpression(e);
        }

        public override Node Visit(DbIntersectExpression e) 
        {
            return VisitSetOpExpression(e); 
        } 

        public override Node Visit(DbExceptExpression e) 
        {
            return VisitSetOpExpression(e);
        }
 
        public override Node Visit(DbTreatExpression e)
        { 
            Op op = _iqtCommand.CreateTreatOp(e.ResultType); 
            return VisitUnary(e, op, VisitExprAsScalar);
        } 

        public override Node Visit(DbIsOfExpression e)
        {
            Op op = null; 
            if (DbExpressionKind.IsOfOnly == e.ExpressionKind)
            { 
                op = _iqtCommand.CreateIsOfOnlyOp(e.OfType); 
            }
            else 
            {
                op = _iqtCommand.CreateIsOfOp(e.OfType);
            }
            return VisitUnary(e, op, VisitExprAsScalar); 
        }
 
        public override Node Visit(DbCastExpression e) 
        {
            Op op = _iqtCommand.CreateCastOp(e.ResultType); 
            return VisitUnary(e, op, VisitExprAsScalar);
        }

        public override Node Visit(DbCaseExpression e) 
        {
            List childNodes = new List(); 
            for (int idx = 0; idx < e.When.Count; idx++) 
            {
                childNodes.Add(VisitExprAsPredicate(e.When[idx])); 
                // Make sure that each then-clause is the same type as the result
                childNodes.Add(BuildSoftCast(VisitExprAsScalar(e.Then[idx]), e.ResultType));
            }
 
            // Make sure that the else-clause is the same type as the result
            childNodes.Add(BuildSoftCast(VisitExprAsScalar(e.Else), e.ResultType)); 
            return _iqtCommand.CreateNode(_iqtCommand.CreateCaseOp(e.ResultType), childNodes); 
        }
 
        public override Node Visit(DbOfTypeExpression e)
        {
            //
            // The argument to OfType must be a collection 
            //
            PlanCompiler.Assert(TypeSemantics.IsCollectionType(e.Argument.ResultType), "Non-Collection Type Argument in DbOfTypeExpression"); 
 
            //
            // Visit the collection argument and ensure that it is a RelOp suitable for subsequent use in the Filter/Project used to convert OfType. 
            //
            Node inputNode = EnsureRelOp(VisitExpr(e.Argument));

            // 
            // Retrieve the Var produced by the RelOp input.
            // 
            Var inputVar = _varMap[inputNode]; 

            // 
            // Build the OfType expression tree
            //
            bool isOfOnly = (DbExpressionKind.OfTypeOnly == e.ExpressionKind);
            Node resultNode; 
            Var resultVar;
            _iqtCommand.BuildOfTypeTree(inputNode, inputVar, e.OfType, !isOfOnly /* include subtypes */, out resultNode, out resultVar); 
 
            //
            // Add the node-var mapping, and return 
            //
            _varMap[resultNode] = resultVar;
            return resultNode;
        } 

        public override Node Visit(DbNewInstanceExpression e) 
        { 
            Op newInstOp = null;
            List relPropertyExprs = null; 
            if (TypeSemantics.IsCollectionType(e.ResultType))
            {
                newInstOp = _iqtCommand.CreateNewMultisetOp(e.ResultType);
            } 
            else if (TypeSemantics.IsRowType(e.ResultType))
            { 
                newInstOp = _iqtCommand.CreateNewRecordOp(e.ResultType); 
            }
            else if (TypeSemantics.IsEntityType(e.ResultType)) 
            {
                List relPropertyList = new List();
                relPropertyExprs = new List();
                if (e.HasRelatedEntityReferences) 
                {
                    foreach (DbRelatedEntityRef targetRef in e.RelatedEntityReferences) 
                    { 
                        RelProperty relProperty = new RelProperty((RelationshipType)targetRef.TargetEnd.DeclaringType, targetRef.SourceEnd, targetRef.TargetEnd);
                        relPropertyList.Add(relProperty); 
                        Node relPropertyNode = VisitExprAsScalar(targetRef.TargetEntityReference);
                        relPropertyExprs.Add(relPropertyNode);
                    }
                } 
                newInstOp = _iqtCommand.CreateNewEntityOp(e.ResultType, relPropertyList);
            } 
            else 
            {
                newInstOp = _iqtCommand.CreateNewInstanceOp(e.ResultType); 
            }

            //
            // Build up the list of arguments. Make sure that they match 
            // the expected types (and add "soft" casts, if needed)
            // 
            List newArgs = new List(); 
            if (TypeSemantics.IsStructuralType(e.ResultType))
            { 
                StructuralType resultType = TypeHelpers.GetEdmType(e.ResultType);
                int i = 0;
                foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(resultType))
                { 
                    Node newArg = BuildSoftCast(VisitExprAsScalar(e.Arguments[i]), Helper.GetModelTypeUsage(m));
                    newArgs.Add(newArg); 
                    i++; 
                }
            } 
            else
            {
                CollectionType resultType = TypeHelpers.GetEdmType(e.ResultType);
                TypeUsage elementTypeUsage = resultType.TypeUsage; 
                foreach (DbExpression arg in e.Arguments)
                { 
                    Node newArg = BuildSoftCast(VisitExprAsScalar(arg), elementTypeUsage); 
                    newArgs.Add(newArg);
                } 
            }

            if (relPropertyExprs != null)
            { 
                newArgs.AddRange(relPropertyExprs);
            } 
            Node node = _iqtCommand.CreateNode(newInstOp, newArgs); 

            return node; 
        }

        public override Node Visit(DbRefExpression e)
        { 
            // SQLBUDT #502617: Creating a collection of refs throws an Assert
            // A SoftCastOp may be required if the argument to the RefExpression is only promotable 
            // to the row type produced from the key properties of the referenced Entity type. Since 
            // this row type is not actually represented anywhere in the tree it must be built here in
            // order to determine whether or not the SoftCastOp should be applied. 
            //
            Op op = _iqtCommand.CreateRefOp(e.EntitySet, e.ResultType);
            Node newArg = BuildSoftCast(VisitExprAsScalar(e.Argument), TypeHelpers.CreateKeyRowType(e.EntitySet.ElementType, _iqtCommand.MetadataWorkspace));
            return _iqtCommand.CreateNode(op, newArg); 
        }
 
        public override Node Visit(DbRelationshipNavigationExpression e) 
        {
            RelProperty relProperty = new RelProperty(e.Relationship, e.NavigateFrom, e.NavigateTo); 
            Op op = _iqtCommand.CreateNavigateOp(e.ResultType, relProperty);
            Node arg = VisitExprAsScalar(e.NavigationSource);
            return _iqtCommand.CreateNode(op, arg);
        } 

        public override Node Visit(DbDerefExpression e) 
        { 
            Op op = _iqtCommand.CreateDerefOp(e.ResultType);
            return VisitUnary(e, op, VisitExprAsScalar); 
        }

        public override Node Visit(DbRefKeyExpression e)
        { 
            Op op = _iqtCommand.CreateGetRefKeyOp(e.ResultType);
            return VisitUnary(e, op, VisitExprAsScalar); 
        } 

        public override Node Visit(DbEntityRefExpression e) 
        {
            Op op = _iqtCommand.CreateGetEntityRefOp(e.ResultType);
            return VisitUnary(e, op, VisitExprAsScalar);
        } 

        public override Node Visit(DbScanExpression e) 
        { 
            // Create a new table definition
            TableMD tableMetadata = Command.CreateTableDefinition(e.Target); 

            // Create a scan table operator
            ScanTableOp op = _iqtCommand.CreateScanTableOp(tableMetadata);
 
            // Map the ScanTableOp to the ColumnVar of the Table's single column of the Extent's element type
            Node node = _iqtCommand.CreateNode(op); 
            Var singleColumn = op.Table.Columns[0]; 
            _varMap[node] = singleColumn;
 
            return node;
        }

        public override Node Visit(DbFilterExpression e) 
        {
            // 
            // Visit the Predicate with the Input binding's variable in scope 
            //
            Node inputSetNode = EnterExpressionBinding(e.Input); 
            Node predicateNode = VisitExprAsPredicate(e.Predicate);
            ExitExpressionBinding();

            Op filtOp = _iqtCommand.CreateFilterOp(); 

            // Update the Node --> Var mapping. Filter maps to the same Var as its input. 
            Node filtNode = _iqtCommand.CreateNode(filtOp, inputSetNode, predicateNode); 
            _varMap[filtNode] = _varMap[inputSetNode];
 
            return filtNode;
        }

        public override Node Visit(DbProjectExpression e) 
        {
            // check if this is the discriminated projection for a query mapping view 
            if (e == this._discriminatedViewTopProject) 
            {
                return GenerateDiscriminatedProject(e); 
            }
            else
            {
                return GenerateStandardProject(e); 
            }
        } 
 
        private Node GenerateDiscriminatedProject(DbProjectExpression e)
        { 
            PlanCompiler.Assert(null != _discriminatedViewTopProject, "if a project matches the pattern, there must be a corresponding discriminator map");

            // convert the input to the top level projection
            Node source = EnterExpressionBinding(e.Input); 

            List relPropertyList = new List(); 
            List relPropertyExprs = new List(); 
            foreach (KeyValuePair kv in _discriminatorMap.RelPropertyMap)
            { 
                relPropertyList.Add(kv.Key);
                relPropertyExprs.Add(VisitExprAsScalar(kv.Value));
            }
 
            // construct a DiscriminatedNewInstanceOp
            DiscriminatedNewEntityOp newInstOp = _iqtCommand.CreateDiscriminatedNewEntityOp(e.Projection.ResultType, 
                new ExplicitDiscriminatorMap(_discriminatorMap), _discriminatorMap.EntitySet, relPropertyList); 

            // args include all projected properties and discriminator and the relProperties 
            List newArgs = new List(_discriminatorMap.PropertyMap.Count + 1);
            newArgs.Add(CreateNewInstanceArgument(_discriminatorMap.Discriminator.Property, _discriminatorMap.Discriminator));
            foreach (var propertyMap in _discriminatorMap.PropertyMap)
            { 
                DbExpression value = propertyMap.Value;
                EdmProperty property = propertyMap.Key; 
                Node newArg = CreateNewInstanceArgument(property, value); 
                newArgs.Add(newArg);
            } 
            newArgs.AddRange(relPropertyExprs);

            Node newInstNode = _iqtCommand.CreateNode(newInstOp, newArgs);
            ExitExpressionBinding(); 

            Var sourceVar; 
            Node varDefListNode = _iqtCommand.CreateVarDefListNode(newInstNode, out sourceVar); 

            ProjectOp projOp = _iqtCommand.CreateProjectOp(sourceVar); 
            Node projNode = _iqtCommand.CreateNode(projOp, source, varDefListNode);
            _varMap[projNode] = sourceVar;

            return projNode; 
        }
 
        private Node CreateNewInstanceArgument(EdmMember property, DbExpression value) 
        {
            Node newArg = BuildSoftCast(VisitExprAsScalar(value), Helper.GetModelTypeUsage(property)); 
            return newArg;
        }

        private Node GenerateStandardProject(DbProjectExpression e) 
        {
            Node projectedSetNode = EnterExpressionBinding(e.Input); 
            Node projectionNode = VisitExprAsScalar(e.Projection); 
            ExitExpressionBinding();
 
            Var projectionVar;
            Node varDefListNode = _iqtCommand.CreateVarDefListNode(projectionNode, out projectionVar);

            ProjectOp projOp = _iqtCommand.CreateProjectOp(projectionVar); 
            Node projNode = _iqtCommand.CreateNode(projOp, projectedSetNode, varDefListNode);
            _varMap[projNode] = projectionVar; 
 
            return projNode;
        } 

        public override Node Visit(DbCrossJoinExpression e)
        {
            return VisitJoin(e, e.Inputs, null); 
        }
 
        public override Node Visit(DbJoinExpression e) 
        {
            List inputs = new List(); 
            inputs.Add(e.Left);
            inputs.Add(e.Right);

            return VisitJoin(e, inputs, e.JoinCondition); 
        }
 
        private Node VisitJoin(DbExpression e, IList inputs, DbExpression joinCond) 
        {
            // 
            // Assert that the JoinType is covered. If JoinTypes are added to CQT then the
            // switch statement that constructs the JoinOp must be updated, along with this assert.
            //
            PlanCompiler.Assert(DbExpressionKind.CrossJoin == e.ExpressionKind || 
                            DbExpressionKind.InnerJoin == e.ExpressionKind ||
                            DbExpressionKind.LeftOuterJoin == e.ExpressionKind || 
                            DbExpressionKind.FullOuterJoin == e.ExpressionKind, 
                            "Unrecognized JoinType specified in DbJoinExpression");
 
#if DEBUG
            //
            // Assert that the DbJoinExpression is producing a collection result with a record element type.
            // !!! IsCollectionOfRecord() is defined only in DEBUG  !!! 
            PlanCompiler.Assert(IsCollectionOfRecord(e.ResultType), "Invalid Type returned by DbJoinExpression");
#endif 
 
            //
            // Bring the variables for the Join inputs into scope, track their nodes and vars, and visit the Join condition, if present. 
            //
            List inputNodes = new List();
            List inputVars = new List();
 
            for(int idx = 0; idx < inputs.Count; idx++)
            { 
                Node inputNode = EnterExpressionBinding(inputs[idx]); 
                inputNodes.Add(inputNode);
                inputVars.Add(_varMap[inputNode]); 
            }

            Node joinCondNode = VisitExprAsPredicate(joinCond);
 
            //
            // Remove the input variables from scope after visiting the Join condition. 
            // 
            for (int scopeCount = 0; scopeCount < inputNodes.Count; scopeCount++)
            { 
                ExitExpressionBinding();
            }

            // 
            // Create an appropriate JoinOp based on the JoinType specified in the DbJoinExpression.
            // 
            JoinBaseOp joinOp = null; 
            switch (e.ExpressionKind)
            { 
                case DbExpressionKind.CrossJoin:
                    {
                        joinOp = _iqtCommand.CreateCrossJoinOp();
                    } 
                    break;
 
                case DbExpressionKind.InnerJoin: 
                    {
                        joinOp = _iqtCommand.CreateInnerJoinOp(); 
                    }
                    break;

                case DbExpressionKind.LeftOuterJoin: 
                    {
                        joinOp = _iqtCommand.CreateLeftOuterJoinOp(); 
                    } 
                    break;
 
                case DbExpressionKind.FullOuterJoin:
                    {
                        joinOp = _iqtCommand.CreateFullOuterJoinOp();
                    } 
                    break;
            } 
 
            //
            // Assert that a JoinOp was produced. This check is again in case a new JoinType is introduced to CQT and this method is not updated. 
            //
            PlanCompiler.Assert(joinOp != null, "Unrecognized JoinOp specified in DbJoinExpression, no JoinOp was produced");

            // 
            // If the Join condition was present then add its converted form to the list of child nodes for the new Join node.
            // 
            if (e.ExpressionKind != DbExpressionKind.CrossJoin) 
            {
                PlanCompiler.Assert(joinCondNode != null, "Non CrossJoinOps must specify a join condition"); 
                inputNodes.Add(joinCondNode);
            }

            // 
            // Create and return a new projection that unifies the multiple vars produced by the Join columns into a single record constructor.
            // 
            return ProjectNewRecord( 
                _iqtCommand.CreateNode(joinOp, inputNodes),
                ExtractElementRowType(e.ResultType), 
                inputVars
            );
        }
 
        public override Node Visit(DbApplyExpression e)
        { 
#if DEBUG 
            //
            // Assert that the DbJoinExpression is producing a collection result with a record element type. 
            // !!! IsCollectionOfRecord() is defined only in DEBUG  !!!
            PlanCompiler.Assert(IsCollectionOfRecord(e.ResultType), "Invalid Type returned by DbApplyExpression");
#endif
 
            //
            // Bring the Input set's variable into scope 
            // 
            Node inputNode = EnterExpressionBinding(e.Input);
 
            //
            // Visit the Apply expression with the Input's variable in scope.
            // This is done via EnterExpressionBinding, which is allowable only because
            // it will only bring the Apply variable into scope *after* visiting the Apply expression 
            // (which means that the Apply expression cannot validly reference its own binding variable)
            // 
            Node applyNode = EnterExpressionBinding(e.Apply); 

            // 
            // Remove the Apply and Input variables from scope
            //
            ExitExpressionBinding(); // for the Apply
            ExitExpressionBinding(); // for the Input 

            // 
            // The ApplyType should only be either CrossApply or OuterApply. 
            //
            PlanCompiler.Assert(DbExpressionKind.CrossApply == e.ExpressionKind || DbExpressionKind.OuterApply == e.ExpressionKind, "Unrecognized DbExpressionKind specified in DbApplyExpression"); 

            //
            // Create a new Node with the correct ApplyOp as its Op and the input and apply nodes as its child nodes.
            // 
            ApplyBaseOp applyOp = null;
            if (DbExpressionKind.CrossApply == e.ExpressionKind) 
            { 
                applyOp = _iqtCommand.CreateCrossApplyOp();
            } 
            else
            {
                applyOp = _iqtCommand.CreateOuterApplyOp();
            } 

            Node retNode = _iqtCommand.CreateNode(applyOp, inputNode, applyNode); 
 
            //
            // Create and return a new projection that unifies the vars produced by the input and apply columns into a single record constructor. 
            //
            return ProjectNewRecord(
                retNode,
                ExtractElementRowType(e.ResultType), 
                new Var[] { _varMap[inputNode], _varMap[applyNode] }
            ); 
        } 

        public override Node Visit(DbGroupByExpression e) 
        {
#if DEBUG
            // !!! IsCollectionOfRecord() is defined only in DEBUG  !!!
            PlanCompiler.Assert(IsCollectionOfRecord(e.ResultType), "DbGroupByExpression has invalid result Type (not record collection)"); 
#endif
 
            VarVec keyVarSet = _iqtCommand.CreateVarVec(); 
            VarVec outputVarSet = _iqtCommand.CreateVarVec();
 
            //
            // Bring the Input variable from the DbGroupByExpression into scope
            //
            Node inputNode = EnterGroupExpressionBinding(e.Input); 

            // 
            // Process the Keys: For each Key, produce the corresponding IQT conversion. 
            // The converted Node is then used as the child node of a VarDefOp Node that is
            // added to a list of Key VarDefs. The Var defined by the converted Key expression 
            // is added to both the overall list of Vars produced by the GroupBy and the list of Key vars produced by the GroupBy.
            //
            List keyVarDefNodes = new List();
            for(int idx = 0; idx < e.Keys.Count; idx++) 
            {
                DbExpression keyExpr = e.Keys[idx]; 
 
                Node keyNode = VisitExprAsScalar(keyExpr);
                ScalarOp keyOp = keyNode.Op as ScalarOp; 

                //
                // In a valid CQT, each group key expressions will result in a ScalarOp since they
                // must be of an equality comparable type. 
                //
                PlanCompiler.Assert(keyOp != null, "GroupBy Key is not a ScalarOp"); 
 
                //
                // Create a ComputedVar with the same type as the Key and add it to both the set of output Vars produced by the GroupBy and the set of Key vars. 
                //
                Var keyVar;
                //
                // Create a VarDefOp that uses the converted form of the Key to define the ComputedVar and add it to the list of Key VarDefs. 
                //
                keyVarDefNodes.Add(_iqtCommand.CreateVarDefNode(keyNode, out keyVar)); 
                outputVarSet.Set(keyVar); 
                keyVarSet.Set(keyVar);
            } 

            //
            // Before the Aggregates are processed, the Input variable must be taken out of scope and the 'group' variable introduced into scope in its place
            // This is done as follows: 
            // 1. Pop the current ExpressionBindingScope from the stack
            // 2. Create a new ExpressionBindingScope using the same Var but the name of the 'group' variable from the DbGroupByExpression's DbGroupExpressionBinding 
            // 3. Push this new scope onto the variable scope stack. 
            //
            ExpressionBindingScope scope = ExitExpressionBinding(); 
            scope = new ExpressionBindingScope(_iqtCommand, e.Input.GroupVariableName, scope.ScopeVar);
            _varScopes.Push(scope);

            // 
            // Process the Aggregates: For each DbAggregate, produce the corresponding IQT conversion depending on whether the DbAggregate is a DbFunctionAggregate or NestAggregate.
            // The converted Node is then used as the child node of a VarDefOp Node that is added to a list of Aggregate VarDefs. 
            // The Var defined by the converted DbAggregate is added only to the overall list of Vars produced by the GroupBy (not the list of Keys). 
            //
            List aggVarDefNodes = new List(); 
            for(int idx = 0; idx < e.Aggregates.Count; idx++)
            {
                DbAggregate agg = e.Aggregates[idx];
 
                //
                // Produce the converted form of the Arguments to the aggregate 
                // 
                IList argNodes = VisitExprAsScalar(agg.Arguments);
 
                Node aggNode = null;
                TypeUsage aggType = null;

                // 
                // Currently only DbFunctionAggregate is supported
                // 
                DbFunctionAggregate funcAgg = agg as DbFunctionAggregate; 
                PlanCompiler.Assert(funcAgg != null, "Unrecognized DbAggregate used in DbGroupByExpression");
 
                //
                // Convert the aggregate according to its type
                //
                aggType = funcAgg.Function.ReturnParameter.TypeUsage; 
                aggNode = _iqtCommand.CreateNode(
                    _iqtCommand.CreateAggregateOp(funcAgg.Function, funcAgg.Distinct), 
                    argNodes 
                );
 
                //
                // Create a ComputedVar with the same type as the output Type of the DbAggregate and add it only to the set of output Vars produced by the GroupBy
                //
                Var aggVar; 
                //
                // Create a VarDefOp that uses the converted form of the DbAggregate to define the ComputedVar and add it to the list of DbAggregate VarDefs. 
                // 
                aggVarDefNodes.Add(_iqtCommand.CreateVarDefNode(aggNode, out aggVar));
                outputVarSet.Set(aggVar); 
            }

            //
            // The Aggregates have now been processed, so remove the group variable from scope. 
            //
            ExitGroupExpressionBinding(); 
 
            //
            // Construct the GroupBy. This consists of a GroupByOp Node with 3 children: 
            // 1. The Node produced from the Input set
            // 2. A VarDefListOp Node that uses the Key VarDefs to define the Key Vars (created above)
            // 3. A VarDefListOp Node that uses the Aggregate VarDefs to define the Aggregate Vars (created above)
            // 
            Node groupByNode = _iqtCommand.CreateNode(
                _iqtCommand.CreateGroupByOp(keyVarSet, outputVarSet), 
 
                // The Node produced from the Input set
                inputNode, 

                // The Key VarDefs
                _iqtCommand.CreateNode(
                    _iqtCommand.CreateVarDefListOp(), 
                    keyVarDefNodes
                ), 
 
                // The Aggregate VarDefs
                _iqtCommand.CreateNode( 
                    _iqtCommand.CreateVarDefListOp(),
                    aggVarDefNodes
                )
            ); 

            // 
            // Create and return a projection that unifies the multiple output vars of the GroupBy into a single record constructor. 
            //
            return ProjectNewRecord( 
                groupByNode,
                ExtractElementRowType(e.ResultType),
                outputVarSet
            ); 
        }
 
        ///  
        /// Common processing for the identical input and sort order arguments to the unrelated
        /// DbSkipExpression and DbSortExpression types. 
        /// 
        /// The input DbExpressionBinding from the DbSkipExpression or DbSortExpression
        /// The list of SortClauses from the DbSkipExpression or DbSortExpression
        /// A list to contain the converted SortKeys produced from the SortClauses 
        /// The Var produced by the input to the DbSkipExpression or DbSortExpression
        ///  
        ///     The converted form of the input to the DbSkipExpression or DbSortExpression, capped by a 
        ///     ProjectOp that defines and Vars referenced by the SortKeys.
        ///  
        private Node VisitSortArguments(DbExpressionBinding input, IList sortOrder, List sortKeys, out Var inputVar)
        {
            //
            // Skip/DbSortExpression conversion first produces a ProjectOp over the original input. 
            // This is done to ensure that the new (Constrained)SortOp itself does not
            // contain any local variable definitions (in the form of a VarDefList child node) 
            // which makes it simpler to pull SortOps over ProjectOps later in the PlanCompiler 
            // (specifically the PreProcessor).
            // The new ProjectOp projects the output Var of the input along with any Vars referenced 
            // by the SortKeys, and its VarDefList child defines those Vars.

            //
            // Bring the variable defined by the DbSortExpression's input set into scope 
            // and retrieve it from the Node => Var map for later use.
            // 
            Node inputNode = EnterExpressionBinding(input); 
            inputVar = _varMap[inputNode];
 
            //
            // Convert the SortClauses, building a new VarDefOp Node for each one.
            //
            VarVec projectedVars = _iqtCommand.CreateVarVec(); 
            projectedVars.Set(inputVar);
 
            List sortVarDefs = new List(); 
            PlanCompiler.Assert(sortKeys.Count == 0, "Non-empty SortKey list before adding converted SortClauses");
            for (int idx = 0; idx < sortOrder.Count; idx++) 
            {
                DbSortClause clause = sortOrder[idx];

                // 
                // Convert the DbSortClause DbExpression to a Node/Op pair
                // 
                Node exprNode = VisitExprAsScalar(clause.Expression); 

                // 
                // In a valid CQT, DbSortClause expressions must have a result of an OrderComparable Type,
                // and such expressions will always convert to ScalarOps.
                //
                ScalarOp specOp = exprNode.Op as ScalarOp; 
                PlanCompiler.Assert(specOp != null, "DbSortClause Expression converted to non-ScalarOp");
 
                // 
                // Create a new ComputedVar with the same Type as the result Type of the DbSortClause DbExpression
                // 
                Var specVar;

                //
                // Create a new VarDefOp Node that defines the ComputedVar and add it both to the 
                // list of VarDefs and the VarVec of produced Vars that will be used to create a
                // SortKey-defining ProjectOp over the Sort input. 
                // 
                sortVarDefs.Add(_iqtCommand.CreateVarDefNode(exprNode, out specVar));
                projectedVars.Set(specVar); 

                //
                // Create a new IQT SortKey that references the ComputedVar and has the same
                // Ascending and Collation as the original DbSortClause, then add it to the list of SortKeys. 
                //
                SortKey sortKey = null; 
                if (string.IsNullOrEmpty(clause.Collation)) 
                {
                    sortKey = Command.CreateSortKey(specVar, clause.Ascending); 
                }
                else
                {
                    sortKey = Command.CreateSortKey(specVar, clause.Ascending, clause.Collation); 
                }
                sortKeys.Add(sortKey); 
            } 

            // 
            // Now that the SortClauses have been converted, remove the Input set's variable from scope.
            //
            ExitExpressionBinding();
 
            //
            // Cap the Input with a ProjectOp that pushes the sort key VarDefs down to that projection. 
            // 
            inputNode =
                _iqtCommand.CreateNode( 
                    _iqtCommand.CreateProjectOp(projectedVars),
                    inputNode,
                    _iqtCommand.CreateNode(
                        _iqtCommand.CreateVarDefListOp(), 
                        sortVarDefs
                    ) 
                ); 

            return inputNode; 
        }

        public override Node Visit(DbSkipExpression expression)
        { 
            //
            // Invoke common processing of Skip/DbSortExpression arguments. 
            // 
            Var inputVar;
            List sortKeys = new List(); 
            Node inputNode = VisitSortArguments(expression.Input, expression.SortOrder, sortKeys, out inputVar);

            //
            // Visit the Skip Count 
            //
            Node countNode = VisitExprAsScalar(expression.Count); 
 
            //
            // Create a new Node that has a new ConstrainedSortOp based on the SortKeys as its Op 
            // and the following children:
            // - The Input node from VisitSortArguments
            // - The converted form of the skip count
            // - A NullOp of type Int64 to indicate that no limit operation is applied 
            //
            Node skipNode = 
                _iqtCommand.CreateNode( 
                    _iqtCommand.CreateConstrainedSortOp(sortKeys),
                    inputNode, 
                    countNode,
                    _iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.IntegerType))
                );
 
            // Update the Node --> Var mapping for the new ConstrainedSort Node.
            // ConstrainedSortOp maps to the same Op that its RelOp input maps to. 
            _varMap[skipNode] = inputVar; 

            return skipNode; 
        }

        public override Node Visit(DbSortExpression e)
        { 
            //
            // Invoke common processing of Skip/DbSortExpression arguments. 
            // 
            Var inputVar;
            List sortKeys = new List(); 
            Node inputNode = VisitSortArguments(e.Input, e.SortOrder, sortKeys, out inputVar);

            //
            // Create a new SortOp that uses the constructed SortKeys. 
            //
            SortOp newSortOp = _iqtCommand.CreateSortOp(sortKeys); 
 
            //
            // Create a new SortOp Node that has the new SortOp as its Op the Key-defining ProjectOp Node as its only child. 
            //
            Node newSortNode = _iqtCommand.CreateNode(newSortOp, inputNode);

            // Update the Node --> Var mapping for the new Sort Node. 
            // SortOp maps to the same Op that its RelOp input maps to.
            _varMap[newSortNode] = inputVar; 
 
            return newSortNode;
        } 

        public override Node Visit(DbQuantifierExpression e)
        {
            Node retNode = null; 

            // 
            // Any converts to Exists(Filter(Input, Predicate)) 
            // All converts to Not(Exists(Filter(Input, Or(Not(Predicate), IsNull(Predicate)))))
            // 
            PlanCompiler.Assert(DbExpressionKind.Any == e.ExpressionKind || DbExpressionKind.All == e.ExpressionKind, "Invalid DbExpressionKind in DbQuantifierExpression");

            //
            // Bring the input's variable into scope 
            //
            Node inputNode = EnterExpressionBinding(e.Input); 
 
            //
            // Convert the predicate 
            //
            Node predicateNode = VisitExprAsPredicate(e.Predicate);

            // 
            // If the quantifier is All then the predicate must become 'Not(Predicate) Or IsNull(Predicate)',
            // since the converted form of the predicate should exclude a member of the input set if and only if 
            // the predicate evaluates to False - filtering only with the negated predicate would also exclude members 
            // for which that negated predicate evaluates to null, possibly resulting in an erroneous empty result set
            // and causing the quantifier to produce a false positive result. 
            //
            if (DbExpressionKind.All == e.ExpressionKind)
            {
                // Create the 'Not(Predicate)' branch of the Or. 
                predicateNode = _iqtCommand.CreateNode(
                    _iqtCommand.CreateConditionalOp(OpType.Not), 
                    predicateNode 
                );
 
                // Visit the original predicate for use in the 'IsNull(Predicate)' branch of the Or.
                // Note that this is treated as a scalar value rather than a Boolean predicate.
                Node predicateCopy = VisitExprAsScalar(e.Predicate);
 
                // Create the 'IsNull(Predicate)' branch of the Or.
                predicateCopy = _iqtCommand.CreateNode( 
                    _iqtCommand.CreateConditionalOp(OpType.IsNull), 
                    predicateCopy
                ); 

                // Finally, combine the branches with a Boolean 'Or' Op to create the updated predicate node.
                predicateNode = _iqtCommand.CreateNode(
                    _iqtCommand.CreateConditionalOp(OpType.Or), 
                    predicateNode,
                    predicateCopy 
                ); 
            }
 
            //
            // Remove the input's variable from scope
            //
            ExitExpressionBinding(); 

            // 
            // Create a FilterOp around the original input set and map the FilterOp to the Var produced by the original input set. 
            //
            Var inputVar = _varMap[inputNode]; 
            inputNode = _iqtCommand.CreateNode(_iqtCommand.CreateFilterOp(), inputNode, predicateNode);
            _varMap[inputNode] = inputVar;

            // 
            // Create an ExistsOp around the filtered set to perform the quantifier operation.
            // 
            retNode = _iqtCommand.CreateNode(_iqtCommand.CreateExistsOp(), inputNode); 

            // 
            // For All, the exists operation as currently built must now be negated.
            //
            if (DbExpressionKind.All == e.ExpressionKind)
            { 
                retNode = _iqtCommand.CreateNode(_iqtCommand.CreateConditionalOp(OpType.Not), retNode);
            } 
 
            return retNode;
        } 

        #endregion
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....], [....]
//--------------------------------------------------------------------- 
 
using System;
using System.Collections.Generic; 
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Text;

using System.Data; 
using System.Data.Common;
using System.Data.Metadata.Edm; 
using System.Data.Common.CommandTrees; 
using System.Data.Common.CommandTrees.Internal;
using System.Data.Query.InternalTrees; 

namespace System.Data.Query.PlanCompiler
{
    internal class ITreeGenerator : DbExpressionVisitor 
    {
        #region Nested Types 
        ///  
        /// Abstract base class for both DbExpressionBinding and LambdaFunction scopes
        ///  
        private abstract class CqtVariableScope
        {
            internal abstract bool Contains(string varName);
            internal abstract Node this[string varName] { get; } 
        }
 
        ///  
        /// Represents a variable scope introduced by a CQT DbExpressionBinding, and therefore contains a single variable.
        ///  
        private class ExpressionBindingScope : CqtVariableScope
        {
            private Command _tree;
            private string _varName; 
            private Var _var;
 
            internal ExpressionBindingScope(Command iqtTree, string name, Var iqtVar) 
            {
                _tree = iqtTree; 
                _varName = name;
                _var = iqtVar;
            }
 
            internal override bool Contains(string name) { return (_varName == name); }
            internal override Node this[string name] 
            { 
                get
                { 
                    PlanCompiler.Assert(name == _varName,"huh?");
                    return _tree.CreateNode(_tree.CreateVarRefOp(_var));
                }
            } 

            internal Var ScopeVar { get { return _var; } } 
        } 

        ///  
        /// Represents a variable scope introduced by a LambdaFunction.
        /// 
        private class LambdaScope : CqtVariableScope
        { 
            private ITreeGenerator _treeGen;
            private Command _command; 
            private Dictionary _arguments; 
            private Dictionary _referencedArgs;
 
            internal LambdaScope(ITreeGenerator treeGen, Command command, Dictionary args)
            {
                _treeGen = treeGen;
                _command = command; 
                _arguments = args;
                _referencedArgs = new Dictionary(_arguments.Count); 
            } 

            internal override bool Contains(string name) { return (_arguments.ContainsKey(name)); } 
            internal override Node this[string name]
            {
                get
                { 
                    PlanCompiler.Assert(_arguments.ContainsKey(name), "LambdaScope indexer called for invalid Var");
 
                    Node argNode = _arguments[name]; 
                    if (_referencedArgs.ContainsKey(argNode))
                    { 
                        // The specified argument has already been substituted into the
                        // IQT and so this substitution requires a copy of the argument.
                        VarMap mappedVars = null;
 
                        // This is a 'deep copy' operation that clones the entire subtree rooted at the node.
                        Node argCopy = OpCopier.Copy(_command, argNode, out mappedVars); 
 
                        // If any Nodes in the copy of the argument produce Vars then the
                        // Node --> Var map must be updated to include them. 
                        if (mappedVars.Count > 0)
                        {
                            List sources = new List(1);
                            sources.Add(argNode); 

                            List copies = new List(1); 
                            copies.Add(argCopy); 

                            MapCopiedNodeVars(sources, copies, mappedVars); 
                        }

                        argNode = argCopy;
                    } 
                    else
                    { 
                        // This is the first reference of the lambda argument, so the Node itself 
                        // can be returned rather than a copy, but the dictionary that tracks
                        // whether or not an argument has been referenced needs to be updated. 
                        _referencedArgs[argNode] = true;
                    }

                    return argNode; 
                }
            } 
 
            private void MapCopiedNodeVars(IList sources, IList copies, Dictionary varMappings)
            { 
                PlanCompiler.Assert(sources.Count == copies.Count, "Source/Copy Node count mismatch");

                //
                // For each Source/Copy Node in the two lists: 
                // - Recursively update the Node --> Var map for any child nodes
                // - If the Source Node is mapped to a Var, then retrieve the new Var 
                //   produced by the Op copier that corresponds to that Source Var, and 
                //   add an entry to the Node --> Var map that maps the Copy Node to the
                //   new Var. 
                //
                for (int idx = 0; idx < sources.Count; idx++)
                {
                    Node sourceNode = sources[idx]; 
                    Node copyNode = copies[idx];
 
                    if (sourceNode.Children.Count > 0) 
                    {
                        MapCopiedNodeVars(sourceNode.Children, copyNode.Children, varMappings); 
                    }

                    Var sourceVar = null;
                    if (_treeGen.VarMap.TryGetValue(sourceNode, out sourceVar)) 
                    {
                        PlanCompiler.Assert(varMappings.ContainsKey(sourceVar), "No mapping found for Var in Var to Var map from OpCopier"); 
                        this._treeGen.VarMap[copyNode] = varMappings[sourceVar]; 
                    }
                } 
            }
        }
        #endregion
 
        private static Dictionary s_opMap = InitializeExpressionKindToOpTypeMap();
 
        private readonly Command _iqtCommand; 
        private readonly Stack _varScopes = new Stack();
        private readonly Dictionary _varMap = new Dictionary(); 

        // leverage discriminator metadata in the top-level project when translating query mapping views...
        private readonly System.Data.Mapping.ViewGeneration.DiscriminatorMap _discriminatorMap;
        private readonly DbProjectExpression _discriminatedViewTopProject; 

 
        ///  
        /// Initialize the DbExpressionKind --> OpType mappings for DbComparisonExpression and DbArithmeticExpression
        ///  
        private static Dictionary InitializeExpressionKindToOpTypeMap()
        {
            Dictionary opMap = new Dictionary(12);
 
            //
            // Arithmetic operators 
            // 
            opMap[DbExpressionKind.Plus] = OpType.Plus;
            opMap[DbExpressionKind.Minus] = OpType.Minus; 
            opMap[DbExpressionKind.Multiply] = OpType.Multiply;
            opMap[DbExpressionKind.Divide] = OpType.Divide;
            opMap[DbExpressionKind.Modulo] = OpType.Modulo;
            opMap[DbExpressionKind.UnaryMinus] = OpType.UnaryMinus; 

            // 
            // Comparison operators 
            //
            opMap[DbExpressionKind.Equals] = OpType.EQ; 
            opMap[DbExpressionKind.NotEquals] = OpType.NE;
            opMap[DbExpressionKind.LessThan] = OpType.LT;
            opMap[DbExpressionKind.GreaterThan] = OpType.GT;
            opMap[DbExpressionKind.LessThanOrEquals] = OpType.LE; 
            opMap[DbExpressionKind.GreaterThanOrEquals] = OpType.GE;
 
            return opMap; 
        }
 
        internal Dictionary VarMap { get { return _varMap; } }

        public static Command Generate(DbQueryCommandTree ctree)
        { 
            return Generate(ctree, null);
        } 
 
        /// 
        /// Generate an IQT given a query command tree and discriminator metadata (available for certain query mapping views) 
        /// 
        internal static Command Generate(DbQueryCommandTree ctree, System.Data.Mapping.ViewGeneration.DiscriminatorMap discriminatorMap)
        {
            ITreeGenerator treeGenerator = new ITreeGenerator(ctree, discriminatorMap); 
            return treeGenerator._iqtCommand;
        } 
 
        private ITreeGenerator(DbQueryCommandTree ctree, System.Data.Mapping.ViewGeneration.DiscriminatorMap discriminatorMap)
        { 
            //
            // Create a new IQT Command instance that uses the same metadata workspace and data space as the incoming command tree
            //
            _iqtCommand = new Command(ctree.MetadataWorkspace, ctree.DataSpace); 

            // 
            // When translating a query mapping view matching the TPH discrimination pattern, remember the top level discriminator map 
            // (leveraged to produced a DiscriminatedNewInstanceOp for the top-level projection in the view)
            // 
            if (null != discriminatorMap)
            {
                _discriminatorMap = discriminatorMap;
                // see System.Data.Mapping.ViewGeneration.DiscriminatorMap 
                PlanCompiler.Assert(ctree.Query.ExpressionKind == DbExpressionKind.Project,
                    "top level QMV expression must be project to match discriminator pattern"); 
                _discriminatedViewTopProject = (DbProjectExpression)ctree.Query; 
            }
 
            //
            // for each Parameter declared by the command tree, add a ParameterVar to the set of parameter vars maintained by the conversion visitor.
            // Each ParameterVar has the same name and type as the corresponding parameter on the command tree.
            // 
            foreach (KeyValuePair paramInfo in ctree.Parameters)
            { 
                _iqtCommand.CreateParameterVar(paramInfo.Key, paramInfo.Value); 
            }
 
            // Convert into an ITree
            _iqtCommand.Root = VisitExpr(ctree.Query);

            // 
            // If the root of the tree is not a relop, build up a fake project over a
            // a singlerowtableOp. 
            //   "s" => Project(SingleRowTableOp, "s") 
            //
            if (!_iqtCommand.Root.Op.IsRelOp) 
            {
                Node scalarExpr = ConvertToScalarOpTree(_iqtCommand.Root, ctree.Query);
                Node singletonTableNode = _iqtCommand.CreateNode(_iqtCommand.CreateSingleRowTableOp());
                Var newVar; 
                Node varDefListNode = _iqtCommand.CreateVarDefListNode(scalarExpr, out newVar);
                ProjectOp projectOp = _iqtCommand.CreateProjectOp(newVar); 
 

                Node newRoot = _iqtCommand.CreateNode(projectOp, singletonTableNode, varDefListNode); 

                if (TypeSemantics.IsCollectionType(_iqtCommand.Root.Op.Type))
                {
                    UnnestOp unnestOp = _iqtCommand.CreateUnnestOp(newVar); 
                    newRoot = _iqtCommand.CreateNode(unnestOp, varDefListNode.Child0);
                    newVar = unnestOp.Table.Columns[0]; 
                } 

                _iqtCommand.Root = newRoot; 
                _varMap[_iqtCommand.Root] = newVar;

            }
 

            // 
            // Ensure that the topmost portion of the query is capped by a 
            // PhysicalProject expression
            // 
            _iqtCommand.Root = CapWithPhysicalProject(_iqtCommand.Root);
        }

        #region DbExpressionVisitor Helpers 

        private static RowType ExtractElementRowType(TypeUsage typeUsage) 
        { 
            return TypeHelpers.GetEdmType(TypeHelpers.GetEdmType(typeUsage).TypeUsage);
        } 

#if DEBUG
        private static bool IsCollectionOfRecord(TypeUsage typeUsage)
        { 
            CollectionType collectionType;
            return (TypeHelpers.TryGetEdmType(typeUsage, out collectionType) && 
                    collectionType != null && 
                    TypeSemantics.IsRowType(collectionType.TypeUsage));
        } 
#endif

        /// 
        /// Is the current expression a predicate? 
        /// 
        /// expr to check 
        /// true, if the expression is a predicate 
        private bool IsPredicate(DbExpression expr)
        { 
            if (TypeSemantics.IsPrimitiveType(expr.ResultType, PrimitiveTypeKind.Boolean))
            {
                switch (expr.ExpressionKind)
                { 
                    case DbExpressionKind.Equals:
                    case DbExpressionKind.NotEquals: 
                    case DbExpressionKind.LessThan: 
                    case DbExpressionKind.LessThanOrEquals:
                    case DbExpressionKind.GreaterThan: 
                    case DbExpressionKind.GreaterThanOrEquals:
                    case DbExpressionKind.And:
                    case DbExpressionKind.Or:
                    case DbExpressionKind.Not: 
                    case DbExpressionKind.Like:
                    case DbExpressionKind.IsEmpty: 
                    case DbExpressionKind.IsNull: 
                    case DbExpressionKind.IsOf:
                    case DbExpressionKind.IsOfOnly: 
                    case DbExpressionKind.Any:
                    case DbExpressionKind.All:
                        return true;
                    case DbExpressionKind.Function: 
                        //
                        DbFunctionExpression fe = expr as DbFunctionExpression; 
                        return (null != fe && fe.IsLambda) ? IsPredicate(fe.LambdaBody) : false; 
                    default:
                        return false; 
                }
            }
            else
            { 
                return false;
            } 
        } 

        ///  
        /// Callback to process an expression
        /// 
        /// The expression to convert
        ///  
        private delegate Node VisitExprDelegate(DbExpression e);
 
        private Node VisitExpr(DbExpression e) 
        {
            if (e == null) 
            {
                return null;
            }
            else 
            {
                return e.Accept(this); 
            } 
        }
 
        /// 
        /// Convert this expression into a "scalar value" ITree expression. There are two main
        /// 
        ///  
        /// 
        private Node VisitExprAsScalar(DbExpression expr) 
        { 
            if (expr == null)
            { 
                return null;
            }

            Node node = VisitExpr(expr); // the real work 
            node = ConvertToScalarOpTree(node, expr);
            return node; 
        } 

        ///  
        /// Convert an Itree node into a scalar op tree
        /// 
        /// the subtree
        /// the original CQT expression 
        /// the converted subtree
        private Node ConvertToScalarOpTree(Node node, DbExpression expr) 
        { 
            //
            // If the current expression is a collection, and we've simply produced a RelOp 
            // then we need to add a CollectOp above a PhysicalProjectOp above the RelOp
            //
            if (node.Op.IsRelOp)
            { 
                PlanCompiler.Assert(TypeSemantics.IsCollectionType(expr.ResultType), "RelOp with non-Collection result type");
                CollectOp collectOp = _iqtCommand.CreateCollectOp(expr.ResultType); 
                // 
                // I'm not thrilled about having to build a PhysicalProjectOp here - this
                // is definitely something I will need to revisit soon 
                //
                Node projectNode = CapWithPhysicalProject(node);
                node = _iqtCommand.CreateNode(collectOp, projectNode);
            } 
            //
            // If the current expression is a boolean, and it is really a predicate, then 
            // scalarize the predicate (ie) convert it into a "case when  then 'true' else 'false' end" expression 
            // SQLBUDT #431406: handle 3-valued logic for all predicates except IsNull
            // Convert boolean predicate p into 
            //    case when p then true when not(p) then false else null end
            //
            else if (IsPredicate(expr))
            { 
                CaseOp caseOp = _iqtCommand.CreateCaseOp(_iqtCommand.BooleanType);
 
                //For 2-valued logic there are 3 arguments, for 3-valued there are 5 
                List arguments = new List((expr.ExpressionKind == DbExpressionKind.IsNull) ? 3 : 5);
 
                //Add the original as the first when
                arguments.Add(node);

                //Add the first then, the true node 
                arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, true)));
 
                //If the expression has 3-valued logic, add a second when 
                if (expr.ExpressionKind != DbExpressionKind.IsNull)
                { 
                    Node predCopy = VisitExpr(expr);
                    arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateConditionalOp(OpType.Not), predCopy));
                }
 
                //Add the false node: for 3 valued logic this is the second then, for 2 valued the else
                arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, false))); 
 
                //The null node, it is the else-clause for 3-valued logic
                if (expr.ExpressionKind != DbExpressionKind.IsNull) 
                {
                    arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.BooleanType)));
                }
 
                node = _iqtCommand.CreateNode(caseOp, arguments);
            } 
 
            return node;
        } 

        /// 
        /// Convert an expression into an iqt predicate
        ///  
        /// the expression to process
        ///  
        private Node VisitExprAsPredicate(DbExpression expr) 
        {
            if (expr == null) 
            {
                return null;
            }
 
            Node node = VisitExpr(expr);
 
            // 
            // If the current expression is not a predicate, then we need to make it one, by
            // comparing it with the constant 'true' 
            //
            if (!IsPredicate(expr))
            {
                ComparisonOp comparisonOp = _iqtCommand.CreateComparisonOp(OpType.EQ); 
                Node trueNode = _iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, true));
                node = _iqtCommand.CreateNode(comparisonOp, node, trueNode); 
            } 
            else
            { 
                PlanCompiler.Assert(!node.Op.IsRelOp, "unexpected relOp as predicate?");
            }

            return node; 
        }
 
        ///  
        /// Process a list of expressions, and apply the delegate to each of the expressions
        ///  
        /// list of cqt expressions to process
        /// the callback to apply
        /// a list of IQT expressions
        private static IList VisitExpr(IList exprs, VisitExprDelegate exprDelegate) 
        {
            List nodeList = new List(); 
            for(int idx = 0; idx < exprs.Count; idx++) 
            {
                nodeList.Add(exprDelegate(exprs[idx])); 
            }
            return nodeList;
        }
 
        /// 
        /// Process a set of cqt expressions - and convert them into scalar iqt expressions 
        ///  
        /// list of cqt expressions
        /// list of iqt expressions 
        private IList VisitExprAsScalar(IList exprs)
        {
            return VisitExpr(exprs, VisitExprAsScalar);
        } 

        private Node VisitUnary(DbUnaryExpression e, Op op, VisitExprDelegate exprDelegate) 
        { 
            return _iqtCommand.CreateNode(op, exprDelegate(e.Argument));
        } 

        private Node VisitBinary(DbBinaryExpression e, Op op, VisitExprDelegate exprDelegate)
        {
            return _iqtCommand.CreateNode(op, exprDelegate(e.Left), exprDelegate(e.Right)); 
        }
 
        ///  
        /// Ensures that an input op is a RelOp. If the specified Node's Op is not a RelOp then it is wrapped in an Unnest to create a synthetic RelOp. This is only possible if the input Op produces a collection.
        ///  
        /// The input Node/Op pair
        /// A Node with an Op that is guaranteed to be a RelOp (this may be the original Node or a new Node created to perform the Unnest)
        private Node EnsureRelOp(Node inputNode)
        { 
            //
            // Input node = N1 
            // 
            Op inputOp = inputNode.Op;
 
            //
            // If the Op is already a RelOp then simply return its Node
            //
            if (inputOp.IsRelOp) 
            {
                return inputNode; 
            } 

            // 
            // Assert that the input is a ScalarOp (CQT expressions should only ever produce RelOps or ScalarOps)
            //
            ScalarOp scalar = inputOp as ScalarOp;
            PlanCompiler.Assert(scalar != null, "An expression in a CQT produced a non-ScalarOp and non-RelOp output Op"); 

            // 
            // Assert that the ScalarOp has a collection result type. EnsureRelOp is called to ensure that arguments to 
            // RelOps are either also RelOps or are ScalarOps that produce a collection, which can be wrapped in an
            // unnest to produce a RelOp. 
            //
            PlanCompiler.Assert(TypeSemantics.IsCollectionType(scalar.Type), "An expression used as a RelOp argument was neither a RelOp or a collection");

            // 
            // If the ScalarOp represents the nesting of an existing RelOp, simply return that RelOp instead.
            // CollectOp(PhysicalProjectOp(x)) => x 
            // 
            CollectOp collect = inputOp as CollectOp;
            if (collect != null) 
            {
                PlanCompiler.Assert(inputNode.HasChild0, "CollectOp without argument");
                if (inputNode.Child0.Op as PhysicalProjectOp != null)
                { 
                    PlanCompiler.Assert(inputNode.Child0.HasChild0, "PhysicalProjectOp without argument");
                    PlanCompiler.Assert(inputNode.Child0.Child0.Op.IsRelOp, "PhysicalProjectOp applied to non-RelOp input"); 
 
                    //
                    // The structure of the Input is Collect(PhysicalProject(x)), so return x 
                    //
                    return inputNode.Child0.Child0;
                }
            } 

            // 
            // Create a new VarDefOp that defines the computed var that represents the ScalarOp collection. 
            // This var is the input to the UnnestOp.
            // varDefNode = N2 
            //
            Var inputCollectionVar;
            Node varDefNode = _iqtCommand.CreateVarDefNode(inputNode, out inputCollectionVar);
 
            //
            // Create an UnnestOp that references the computed var created above. The VarDefOp that defines the var 
            // using the original input Node/Op pair becomes a child of the UnnestOp. 
            //
            UnnestOp unnest = _iqtCommand.CreateUnnestOp(inputCollectionVar); 
            PlanCompiler.Assert(unnest.Table.Columns.Count == 1, "Unnest of collection ScalarOp produced unexpected number of columns (1 expected)");

            //
            // Create the unnest node, N3 
            // The UnnestOp produces a new Var, the single ColumnVar produced by the table that results from the Unnest.
            // 
            Node unnestNode = _iqtCommand.CreateNode(unnest, varDefNode); 
            _varMap[unnestNode] = unnest.Table.Columns[0];
 
            //
            // Create a Project node above the Unnest, so we can simplify the work to eliminate
            // the Unnest later.  That means we need to create a VarRef to the column var in the
            // table, a VarDef to define it, and a VarDefList to hold it, then a Project node, N4, 
            // which we return.
            // 
            Var projectVar; 
            Node varRefNode = _iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(unnest.Table.Columns[0]));
            Node varDefListNode = _iqtCommand.CreateVarDefListNode(varRefNode, out projectVar); 

            ProjectOp projectOp = _iqtCommand.CreateProjectOp(projectVar);
            Node projectNode = _iqtCommand.CreateNode(projectOp, unnestNode, varDefListNode);
 
            _varMap[projectNode] = projectVar;
 
            return projectNode; 
        }
 
        /// 
        /// Cap a RelOp with a ProjectOp. The output var of the Project is the
        /// output var from the input
        ///  
        /// the input relop tree
        /// the relop tree with a projectNode at the root 
        private Node CapWithProject(Node input) 
        {
            PlanCompiler.Assert(input.Op.IsRelOp, "unexpected non-RelOp?"); 
            if (input.Op.OpType == OpType.Project)
            {
                return input;
            } 

            // Get the Var from the input; and build up a Project above it 
            Var inputVar = _varMap[input]; 
            ProjectOp projectOp = _iqtCommand.CreateProjectOp(inputVar);
            Node projectNode = _iqtCommand.CreateNode(projectOp, input, 
               _iqtCommand.CreateNode(_iqtCommand.CreateVarDefListOp()));
            _varMap[projectNode] = inputVar;

            return projectNode; 
        }
 
        ///  
        /// Cap a relop tree with a PhysicalProjectOp. The Vars of the PhysicalProjectOp
        /// are the vars from the RelOp tree 
        /// 
        /// the input relop tree
        /// relop tree capped by a PhysicalProjectOp
        private Node CapWithPhysicalProject(Node input) 
        {
            PlanCompiler.Assert(input.Op.IsRelOp, "unexpected non-RelOp?"); 
 
            // Get the Var from the input; and build up a Project above it
            Var inputVar = _varMap[input]; 
            PhysicalProjectOp projectOp = _iqtCommand.CreatePhysicalProjectOp(inputVar);
            Node projectNode = _iqtCommand.CreateNode(projectOp, input);

            return projectNode; 
        }
 
        ///  
        /// Creates a new variable scope that is based on a CQT DbExpressionBinding and pushes it onto the variable scope stack. The scope defines a single variable based on the DbExpressionBinding's VarName and DbExpression.
        ///  
        /// The DbExpressionBinding that defines the scope
        /// The Node produced by converting the binding's DbExpression
        private Node EnterExpressionBinding(DbExpressionBinding binding)
        { 
            return PushBindingScope(binding.Expression, binding.VariableName);
        } 
 
        /// 
        /// Creates a new variable scope that is based on a CQT DbGroupExpressionBinding and pushes it onto the variable scope stack. The scope defines a single variable based on the DbExpressionBinding's VarName and DbExpression. 
        /// This method does not bring the GroupVarName into scope. Note that ExitExpressionBinding and NOT ExitGroupExpressionBinding should be used to remove this scope from the stack.
        /// 
        /// The DbGroupExpressionBinding that defines the scope
        /// The Node produced by converting the binding's DbExpression 
        private Node EnterGroupExpressionBinding(DbGroupExpressionBinding binding)
        { 
            return PushBindingScope(binding.Expression, binding.VariableName); 
        }
 
        /// 
        /// Common implementation method called by both EnterExpressionBinding and EnterGroupExpressionBinding
        /// 
        /// The DbExpression that defines the binding 
        /// The name of the binding variable
        ///  
        private Node PushBindingScope(DbExpression boundExpression, string bindingName) 
        {
            // 
            // Visit the DbExpressionBinding's DbExpression to convert it to a Node/Op pair
            //
            Node inputNode = VisitExpr(boundExpression);
            PlanCompiler.Assert(inputNode != null, "DbExpressionBinding.Expression produced null conversion"); 

            // 
            // Call EnsureRelOp on the converted Node and set inputNode equal to the result 
            //
            inputNode = EnsureRelOp(inputNode); 

            //
            // Retrieve the Var produced by the RelOp from the Node --> Var map
            // 
            Var boundVar = _varMap[inputNode];
            PlanCompiler.Assert(boundVar != null, "No Var found for Input Op"); 
 
            //
            // Create a new ExpressionBindingScope using the VarName from the DbExpressionBinding and 
            // the Var associated with the Input RelOp, and push the new scope onto the variable scope stack.
            //
            _varScopes.Push(new ExpressionBindingScope(_iqtCommand, bindingName, boundVar));
 
            //
            // Return the IQT conversion of the DbExpressionBinding's DbExpression. 
            // 
            return inputNode;
        } 

        /// 
        /// Removes a variable scope created based on a DbExpressionBinding from the top of the variable scope stack, verifying that it is in fact an ExpressionBindingScope.
        ///  
        /// The removed ExpressionBindingScope
        private ExpressionBindingScope ExitExpressionBinding() 
        { 
            //
            // Pop the scope from the variable scope stack, assert that it is a DbExpressionBinding scope, and return it. 
            //
            ExpressionBindingScope retScope = _varScopes.Pop() as ExpressionBindingScope;
            PlanCompiler.Assert(retScope != null, "ExitExpressionBinding called without ExpressionBindingScope on top of scope stack");
            return retScope; 
        }
 
        ///  
        /// Removes a variable scope created based on a DbGroupExpressionBinding from the top of the variable scope stack, verifying that it is in fact an ExpressionBindingScope.
        /// Should only be called after visiting the Aggregates of a DbGroupByExpression in Visit(DbGroupByExpression). 
        /// The sequence (in Visit(GroupExpression e) is:
        /// 1. EnterGroupExpressionBinding
        /// 2.     Visit e.Keys
        /// 3. ExitExpressionBinding 
        /// 4. (Push new scope with GroupVarName instead of VarName)
        /// 5.     Visit e.Aggregates 
        /// 6. ExitGroupExpressionBinding 
        /// 
        private void ExitGroupExpressionBinding() 
        {
            ExpressionBindingScope retScope = _varScopes.Pop() as ExpressionBindingScope;
            PlanCompiler.Assert(retScope != null, "ExitGroupExpressionBinding called without ExpressionBindingScope on top of scope stack");
        } 

        ///  
        /// Creates a new variable scope that is based on a CQT Lambda function and pushes it onto the variable scope stack. 
        /// 
        /// The Lambda function that defines the scope 
        /// A list of Nodes produced by converting the CQT Expressions that provide the arguments to the Lambda function
        private void EnterLambdaFunction(EdmFunction function, List argumentValues)
        {
            IList lambdaParams = function.Parameters; 
            if (lambdaParams.Count > 0)
            { 
                Dictionary args = new Dictionary(); 
                int idx = 0;
                foreach (Node argumentValue in argumentValues) 
                {
                    args.Add(lambdaParams[idx].Name, argumentValue);
                    idx++;
                } 

                _varScopes.Push(new LambdaScope(this, _iqtCommand, args)); 
            } 
        }
 
        /// 
        /// Removes a variable scope created based on a Lambda function from the top of the variable scope stack, verifying that it is in fact a LambdaScope.
        /// 
        ///  
        private LambdaScope ExitLambdaFunction()
        { 
            // 
            // Pop the scope from the variable scope stack, assert that it is a Lambda scope, and return it.
            // 
            LambdaScope retScope = _varScopes.Pop() as LambdaScope;
            PlanCompiler.Assert(retScope != null, "ExitLambdaFunction called without LambdaScope on top of scope stack");
            return retScope;
        } 

        ///  
        /// Constructs a NewRecordOp on top of a multi-Var-producing Op, resulting in a RelOp that produces a single Var. 
        /// 
        /// The Node that references the multi-Var-producing Op. This Node will become the first child node of the new ProjectOp's Node 
        /// Type metadata that describes the output record type
        /// A list of Vars that provide the output columns of the projection
        /// A new ProjectOp that projects a new record of the specified type from the specified Vars over the original input Op/Node
        private Node ProjectNewRecord(Node inputNode, RowType recType, IEnumerable colVars) 
        {
            // 
            // Create a list of VarRefOp Nodes that provide the column values for the new record 
            //
            List recordColumns = new List(); 
            foreach (Var colVar in colVars)
            {
                recordColumns.Add(_iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(colVar)));
            } 

            // 
            // Create the NewRecordOp Node using the record column nodes as its child nodes 
            //
            Node newRecordNode = _iqtCommand.CreateNode(_iqtCommand.CreateNewRecordOp(recType), recordColumns); 

            //
            // Create a new ComputedVar and a VarDefOp that uses the NewRecordOp Node to define it
            // 
            Var newRecordVar;
            Node varDefNode = _iqtCommand.CreateVarDefListNode(newRecordNode, out newRecordVar); 
 
            //
            // Create a ProjectOp with the single Computed Var defined by the new record construction 
            //
            ProjectOp projection = _iqtCommand.CreateProjectOp(newRecordVar);
            Node projectionNode = _iqtCommand.CreateNode(projection, inputNode, varDefNode);
            _varMap[projectionNode] = newRecordVar; 

            return projectionNode; 
        } 
        #endregion
 
        #region DbExpressionVisitor Members

        public override Node Visit(DbExpression e)
        { 
            throw EntityUtil.NotSupported(System.Data.Entity.Strings.Cqt_General_UnsupportedExpression(e.GetType().FullName));
        } 
 
        public override Node Visit(DbConstantExpression e)
        { 
            // Don't use CreateInternalConstantOp - respect user-intent
            ConstantBaseOp op = _iqtCommand.CreateConstantOp(e.ResultType, e.Value);
            return _iqtCommand.CreateNode(op);
        } 

        public override Node Visit(DbNullExpression e) 
        { 
            NullOp op = _iqtCommand.CreateNullOp(e.ResultType);
            return _iqtCommand.CreateNode(op); 
        }

        public override Node Visit(DbVariableReferenceExpression e)
        { 
            //
            // Search the stack of variables scopes, top-down, 
            // until the first one is found that defines a variable with the specified name. 
            //
            Node varNode = null; 
            foreach (CqtVariableScope scope in _varScopes)
            {
                if (scope.Contains(e.VariableName))
                { 
                    varNode = scope[e.VariableName];
                    break; 
                } 
            }
 
            //
            // If the variable name was not resolved then either:
            // 1. The original CQT was invalid (should not be allowed into the ITreeGenerator).
            // 2. The variable scope stack itself is invalid. 
            //
            PlanCompiler.Assert(varNode != null, "CQT VarRef could not be resolved in the variable scope stack"); 
 
            return varNode;
        } 

        public override Node Visit(DbParameterReferenceExpression e)
        {
            Op op = _iqtCommand.CreateVarRefOp(_iqtCommand.GetParameter(e.ParameterName)); 
            return _iqtCommand.CreateNode(op);
        } 
 
        public override Node Visit(DbFunctionExpression e)
        { 
            Node retNode = null;

            List argNodes = new List(e.Arguments.Count);
            int idx = 0; 
            foreach (DbExpression argExpr in e.Arguments)
            { 
                if (e.IsLambda) 
                {
                    // #484709: Lambda function parameters should not have enclosing SoftCastOps. 
                    argNodes.Add(VisitExpr(argExpr));
                }
                else
                { 
                    // Ensure that any argument with a result type that does not exactly match the type of
                    // the corresponding function parameter is enclosed in a SoftCastOp. 
                    argNodes.Add(BuildSoftCast(VisitExprAsScalar(argExpr), e.Function.Parameters[idx].TypeUsage)); 
                }
                idx++; 
            }

            if (e.LambdaBody != null)
            { 
                EnterLambdaFunction(e.Function, argNodes);
                retNode = VisitExpr(e.LambdaBody); 
                ExitLambdaFunction(); 
            }
            else 
            {
                retNode = _iqtCommand.CreateNode(_iqtCommand.CreateFunctionOp(e.Function), argNodes);
            }
 
            return retNode;
        } 
 
#if METHOD_EXPRESSION
        public override Node Visit(MethodExpression e) 
        {
            throw EntityUtil.NotSupported();
        }
#endif 
        #region SoftCast Helpers
        ///  
        /// This method builds a "soft"Cast operator over the input node (if necessary) to (soft) 
        /// cast it to the desired type (targetType)
        /// 
        /// If the input is a scalarOp, then we simply add on the SoftCastOp
        /// directly (if it is needed, of course). If the input is a RelOp, we create a
        /// new ProjectOp above the input, add a SoftCast above the Var of the
        /// input, and then return the new ProjectOp 
        ///
        /// The "need to cast" is determined by the Command.EqualTypes function. All type 
        /// equivalence in the plan compiler is determined by this function 
        /// 
        /// the expression to soft-cast 
        /// the desired type to cast to
        /// 
        private Node BuildSoftCast(Node node, TypeUsage targetType)
        { 
            //
            // If the input is a RelOp (say X), and the Var of the input is "x", 
            // we convert this into 
            //   Project(X, softCast(x, t))
            // where t is the element type of the desired target type 
            //
            if (node.Op.IsRelOp)
            {
                CollectionType targetCollectionType = TypeHelpers.GetEdmType(targetType); 
                targetType = targetCollectionType.TypeUsage;
 
                Var nodeVar = _varMap[node]; 
                // Do we need a cast at all?
                if (Command.EqualTypes(targetType, nodeVar.Type)) 
                {
                    return node;
                }
 
                // Build up the projectOp
                Var projectVar; 
                Node varRefNode = _iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(nodeVar)); 
                Node castNode = _iqtCommand.CreateNode(_iqtCommand.CreateSoftCastOp(targetType), varRefNode);
                Node varDefListNode = _iqtCommand.CreateVarDefListNode(castNode, out projectVar); 

                ProjectOp projectOp = _iqtCommand.CreateProjectOp(projectVar);
                Node projectNode = _iqtCommand.CreateNode(projectOp, node, varDefListNode);
 
                _varMap[projectNode] = projectVar;
                return projectNode; 
            } 
            else
            { 
                PlanCompiler.Assert(node.Op.IsScalarOp, "I want a scalar op");
                if (Command.EqualTypes(node.Op.Type, targetType))
                {
                    return node; 
                }
                else 
                { 
                    SoftCastOp castOp = _iqtCommand.CreateSoftCastOp(targetType);
                    return _iqtCommand.CreateNode(castOp, node); 
                }
            }
        }
 
        /// 
        /// A variant of the function above. Works with an EdmType instead 
        /// of a TypeUsage, but leverages all the work above 
        /// 
        /// the node to "cast" 
        /// the desired type
        /// the transformed expression
        private Node BuildSoftCast(Node node, EdmType targetType)
        { 
            return BuildSoftCast(node, TypeUsage.Create(targetType));
        } 
 
        private Node BuildEntityRef(Node arg, TypeUsage entityType)
        { 
            TypeUsage refType = TypeHelpers.CreateReferenceTypeUsage((EntityType)entityType.EdmType);
            return _iqtCommand.CreateNode(_iqtCommand.CreateGetEntityRefOp(refType), arg);
        }
 
        #endregion
 
        public override Node Visit(DbPropertyExpression e) 
        {
            // Only Properties, Relationship End and NavigationProperty members are supported. 
            if (BuiltInTypeKind.EdmProperty != e.Property.BuiltInTypeKind &&
                BuiltInTypeKind.AssociationEndMember != e.Property.BuiltInTypeKind &&
                BuiltInTypeKind.NavigationProperty != e.Property.BuiltInTypeKind)
            { 
                throw EntityUtil.NotSupported();
            } 
 
            Node retNode = null;
            Op op = _iqtCommand.CreatePropertyOp(e.Property); 
            if (null == e.Instance)
            {
                retNode = _iqtCommand.CreateNode(op);
            } 
            else
            { 
                Node instance = VisitExpr(e.Instance); 

                // 
                // Retrieving a property from a new instance constructor can be
                // simplified to just the node that provides the corresponding property.
                // For example, Property(Row(A = x, B = y), 'A') => x
                // All structured types (including association types) are considered. 
                //
                if (e.Instance.ExpressionKind == DbExpressionKind.NewInstance && 
                    Helper.IsStructuralType(e.Instance.ResultType.EdmType)) 
                {
                    // Retrieve the 'structural' members of the instance's type. 
                    // For Association types this should be only Association End members,
                    // while for Complex, Entity or Row types is should be only Properties.
                    System.Collections.IList propertyOrEndMembers = Helper.GetAllStructuralMembers(e.Instance.ResultType.EdmType);
 
                    // Find the position of the member with the same name as the retrieved
                    // member in the list of structural members. 
                    int memberIdx = -1; 
                    for (int idx = 0; idx < propertyOrEndMembers.Count; idx++)
                    { 
                        if (string.Equals(e.Property.Name, ((EdmMember)propertyOrEndMembers[idx]).Name, StringComparison.Ordinal))
                        {
                            memberIdx = idx;
                            break; 
                        }
                    } 
 
                    PlanCompiler.Assert(memberIdx > -1, "The specified property was not found");
 
                    // If the member was found, return the corresponding argument value
                    // to the new instance op.
                    retNode = instance.Children[memberIdx];
 
                    // Make sure the argument value has been "cast" to the return type
                    // of the property, if necessary. 
                    retNode = BuildSoftCast(retNode, e.ResultType); 
                }
                else 
                {
                    // Make sure that the input has been "cast" to the right type
                    instance = BuildSoftCast(instance, e.Property.DeclaringType);
                    retNode = _iqtCommand.CreateNode(op, instance); 
                }
            } 
 
            return retNode;
        } 

        public override Node Visit(DbComparisonExpression e)
        {
            Op op = _iqtCommand.CreateComparisonOp(s_opMap[e.ExpressionKind]); 

            Node leftArg = VisitExprAsScalar(e.Left); 
            Node rightArg = VisitExprAsScalar(e.Right); 

            TypeUsage commonType = TypeHelpers.GetCommonTypeUsage(e.Left.ResultType, e.Right.ResultType); 

            // Make sure that the inputs have been cast to the right types
            if (!Command.EqualTypes(e.Left.ResultType, e.Right.ResultType))
            { 
                leftArg = BuildSoftCast(leftArg, commonType);
                rightArg = BuildSoftCast(rightArg, commonType); 
            } 

            if (TypeSemantics.IsEntityType(commonType) && 
                (e.ExpressionKind == DbExpressionKind.Equals || e.ExpressionKind == DbExpressionKind.NotEquals))
            {
                // Entity (in)equality is implemented as ref (in)equality
                leftArg = BuildEntityRef(leftArg, commonType); 
                rightArg = BuildEntityRef(rightArg, commonType);
            } 
 
            return _iqtCommand.CreateNode(op, leftArg, rightArg);
        } 

        public override Node Visit(DbLikeExpression e)
        {
            return _iqtCommand.CreateNode( 
                _iqtCommand.CreateLikeOp(),
                VisitExpr(e.Argument), 
                VisitExpr(e.Pattern), 
                VisitExpr(e.Escape)
            ); 
        }

        private Node CreateLimitNode(Node inputNode, Node limitNode, bool withTies)
        { 
            //
            // Limit(Skip(x)) - which becomes ConstrainedSortOp - and Limit(Sort(x)) are special cases 
            // 
            Node retNode = null;
            if (OpType.ConstrainedSort == inputNode.Op.OpType && 
                OpType.Null == inputNode.Child2.Op.OpType)
            {
                //
                // The input was a DbSkipExpression which is now represented 
                // as a ConstrainedSortOp with a NullOp Limit. The Limit from
                // this DbLimitExpression can be merged into the input ConstrainedSortOp 
                // rather than creating a new ConstrainedSortOp. 
                //
                inputNode.Child2 = limitNode; 

                // If this DbLimitExpression specifies WithTies, the input ConstrainedSortOp must be
                // updated to reflect this (DbSkipExpression always produces a ConstrainedSortOp with
                // WithTies equal to false). 
                if (withTies)
                { 
                    ((ConstrainedSortOp)inputNode.Op).WithTies = true; 
                }
 
                retNode = inputNode;
            }
            else if (OpType.Sort == inputNode.Op.OpType)
            { 
                //
                // This DbLimitExpression is applying a limit to a DbSortExpression. 
                // The two expressions can be merged into a single ConstrainedSortOp 
                // rather than creating a new ConstrainedSortOp over the input SortOp.
                // 
                // The new ConstrainedSortOp has the same SortKeys as the input SortOp.
                // The returned Node will have the following children:
                // - The input to the Sort
                // - A NullOp to indicate no Skip operation is specified 
                // - The limit Node from the DbLimitExpression
                // 
                retNode = 
                    _iqtCommand.CreateNode(
                        _iqtCommand.CreateConstrainedSortOp(((SortOp)inputNode.Op).Keys, withTies), 
                        inputNode.Child0,
                        _iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.IntegerType)),
                        limitNode
                    ); 
            }
            else 
            { 
                //
                // The input to the Limit is neither ConstrainedSortOp or SortOp. 
                // A new ConstrainedSortOp must be created with an empty list of keys
                // and the following children:
                // - The input to the DbLimitExpression
                // - a NullOp to indicate that no Skip operation is specified 
                // - The limit Node from the DbLimitExpression
                // 
                retNode = 
                    _iqtCommand.CreateNode(
                        _iqtCommand.CreateConstrainedSortOp(new List(), withTies), 
                        inputNode,
                        _iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.IntegerType)),
                        limitNode
                    ); 
            }
 
            return retNode; 
        }
 
        public override Node Visit(DbLimitExpression expression)
        {
            //
            // Visit the Argument and retrieve its Var 
            //
            Node inputNode = EnsureRelOp(VisitExpr(expression.Argument)); 
            Var inputVar = _varMap[inputNode]; 

            // 
            // Visit the Limit ensuring that it is a scalar
            //
            Node limitNode = VisitExprAsScalar(expression.Limit);
 
            Node retNode;
            if(OpType.Project == inputNode.Op.OpType) 
            { 
                //
                // If the input to the DbLimitExpression is a projection, then apply the Limit operation to the 
                // input to the ProjectOp instead. This allows  Limit(Project(Skip(x))) and Limit(Project(Sort(x)))
                // to be treated in the same way as Limit(Skip(x)) and Limit(Sort(x)).
                // Note that even if the input to the projection is not a ConstrainedSortOp or SortOp, the
                // Limit operation is still pushed under the Project. 
                //
                inputNode.Child0 = CreateLimitNode(inputNode.Child0, limitNode, expression.WithTies); 
                retNode = inputNode; 
            }
            else 
            {
                //
                // Otherwise, apply the Limit operation directly to the input.
                // 
                retNode = CreateLimitNode(inputNode, limitNode, expression.WithTies);
            } 
 
            //
            // The output Var of the resulting Node is the same as the output Var of its input Node. 
            // If the input node is being returned (either because the Limit was pushed under a Project
            // or because the input was a ConstrainedSortOp that was simply updated with the Limit value)
            // then the Node -> Var map does not need to be updated.
            // 
            if(!object.ReferenceEquals(retNode, inputNode))
            { 
                _varMap[retNode] = inputVar; 
            }
 
            return retNode;
        }

        public override Node Visit(DbIsNullExpression e) 
        {
            // SQLBUDT #484294: We need to recognize and simplify IsNull - IsNull and IsNull - Not - IsNull 
            // This is the latest point where such patterns can be easily recognized. 
            // After this the input predicate would get translated into a case statement.
            bool isAlwaysFalse = false;  //true if IsNull - IsNull and IsNull - Not - IsNull is recognized 

            if (e.Argument.ExpressionKind == DbExpressionKind.IsNull)
            {
                isAlwaysFalse = true; 
            }
            else if (e.Argument.ExpressionKind == DbExpressionKind.Not) 
            { 
                DbNotExpression notExpression = (DbNotExpression)e.Argument;
                if (notExpression.Argument.ExpressionKind == DbExpressionKind.IsNull) 
                {
                    isAlwaysFalse = true;
                }
            } 

            Op op = _iqtCommand.CreateConditionalOp(OpType.IsNull); 
 
            //If we have recognized that the result is always false, return IsNull(true), to still have predicate as output.
            //This gets further simplified by transformation rules. 
            if (isAlwaysFalse)
            {
                return _iqtCommand.CreateNode(op, _iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, true)));
            } 

            Node argNode = VisitExprAsScalar(e.Argument); 
            if (TypeSemantics.IsEntityType(e.Argument.ResultType)) 
            {
                argNode = BuildEntityRef(argNode, e.Argument.ResultType); 
            }

            return _iqtCommand.CreateNode(op, argNode);
        } 

        public override Node Visit(DbArithmeticExpression e) 
        { 
            Op op = _iqtCommand.CreateArithmeticOp(s_opMap[e.ExpressionKind], e.ResultType);
            // Make sure that the inputs have been "cast" to the result type 
            // Assumption: The input type must be the same as the result type. Is this always true?
            List children = new List();
            foreach (DbExpression arg in e.Arguments)
            { 
                Node child = VisitExprAsScalar(arg);
                children.Add(BuildSoftCast(child, e.ResultType)); 
            } 
            return _iqtCommand.CreateNode(op, children);
        } 

        public override Node Visit(DbAndExpression e)
        {
            Op op = _iqtCommand.CreateConditionalOp(OpType.And); 
            return VisitBinary(e, op, VisitExprAsPredicate);
        } 
 
        public override Node Visit(DbOrExpression e)
        { 
            Op op = _iqtCommand.CreateConditionalOp(OpType.Or);
            return VisitBinary(e, op, VisitExprAsPredicate);
        }
 
        public override Node Visit(DbNotExpression e)
        { 
            Op op = _iqtCommand.CreateConditionalOp(OpType.Not); 
            return VisitUnary(e, op, VisitExprAsPredicate);
        } 

        public override Node Visit(DbDistinctExpression e)
        {
            Node inputSetNode = EnsureRelOp(VisitExpr(e.Argument)); 
            Var inputVar = _varMap[inputSetNode];
            Op distinctOp = _iqtCommand.CreateDistinctOp(inputVar); 
            Node distinctNode = _iqtCommand.CreateNode(distinctOp, inputSetNode); 
            _varMap[distinctNode] = inputVar;
            return distinctNode; 
        }

        public override Node Visit(DbElementExpression e)
        { 
            Op elementOp = _iqtCommand.CreateElementOp(e.ResultType);
            Node inputSetNode = EnsureRelOp(VisitExpr(e.Argument)); 
            Var inputVar = _varMap[inputSetNode]; 

            // 
            // Add a singleRowOp enforcer, as we are not guaranteed that the input
            // collection produces at most one row
            //
            inputSetNode = _iqtCommand.CreateNode(_iqtCommand.CreateSingleRowOp(), inputSetNode); 
            _varMap[inputSetNode] = inputVar;
 
            // add a fake projectNode 
            inputSetNode = CapWithProject(inputSetNode);
            return _iqtCommand.CreateNode(elementOp, inputSetNode); 
        }

        public override Node Visit(DbIsEmptyExpression e)
        { 
            //
            // IsEmpty(input set) --> Not(Exists(input set)) 
            // 
            Op existsOp = _iqtCommand.CreateExistsOp();
            Node inputSetNode = EnsureRelOp(VisitExpr(e.Argument)); 

            return _iqtCommand.CreateNode(
                _iqtCommand.CreateConditionalOp(OpType.Not),
                _iqtCommand.CreateNode(existsOp, inputSetNode) 
            );
        } 
 
        /// 
        /// Encapsulates the logic required to convert a SetOp (Except, Intersect, UnionAll) expression 
        /// into an IQT Node/Op pair.
        /// 
        /// The DbExceptExpression, DbIntersectExpression or DbUnionAllExpression to convert, as an instance of DbBinaryExpression
        /// A new IQT Node that references the ExceptOp, IntersectOp or UnionAllOp created based on the expression 
        private Node VisitSetOpExpression(DbBinaryExpression expression)
        { 
            PlanCompiler.Assert(DbExpressionKind.Except == expression.ExpressionKind || 
                         DbExpressionKind.Intersect == expression.ExpressionKind ||
                         DbExpressionKind.UnionAll == expression.ExpressionKind, 
                         "Non-SetOp DbExpression used as argument to VisitSetOpExpression");

            PlanCompiler.Assert(TypeSemantics.IsCollectionType(expression.ResultType), "SetOp DbExpression does not have collection result type?");
 
            // Visit the left and right collection arguments
            Node leftNode = EnsureRelOp(VisitExpr(expression.Left)); 
            Node rightNode = EnsureRelOp(VisitExpr(expression.Right)); 

            // 
            // Now the hard part. "Normalize" the left and right sides to
            // match the result type.
            //
            leftNode = BuildSoftCast(leftNode, expression.ResultType); 
            rightNode = BuildSoftCast(rightNode, expression.ResultType);
 
            // The SetOp produces a single Var of the same type as the element type of the expression's collection result type 
            Var outputVar = _iqtCommand.CreateSetOpVar(TypeHelpers.GetEdmType(expression.ResultType).TypeUsage);
 
            // Create VarMaps for the left and right arguments that map the output Var to the Var produced by the corresponding argument
            VarMap leftMap = new VarMap();
            leftMap.Add(outputVar, _varMap[leftNode]);
 
            VarMap rightMap = new VarMap();
            rightMap.Add(outputVar, _varMap[rightNode]); 
 
            // Create a SetOp that corresponds to the operation specified by the expression's DbExpressionKind
            Op setOp = null; 
            switch(expression.ExpressionKind)
            {
                case DbExpressionKind.Except:
                    setOp = _iqtCommand.CreateExceptOp(leftMap, rightMap); 
                    break;
 
                case DbExpressionKind.Intersect: 
                    setOp = _iqtCommand.CreateIntersectOp(leftMap, rightMap);
                    break; 

                case DbExpressionKind.UnionAll:
                    setOp = _iqtCommand.CreateUnionAllOp(leftMap, rightMap);
                    break; 
            }
 
            // Create a new Node that references the SetOp 
            Node setOpNode = _iqtCommand.CreateNode(setOp, leftNode, rightNode);
 
            // Update the Node => Var map with an entry that maps the new Node to the output Var
            _varMap[setOpNode] = outputVar;

            // Return the newly created SetOp Node 
            return setOpNode;
        } 
 
        public override Node Visit(DbUnionAllExpression e)
        { 
            return VisitSetOpExpression(e);
        }

        public override Node Visit(DbIntersectExpression e) 
        {
            return VisitSetOpExpression(e); 
        } 

        public override Node Visit(DbExceptExpression e) 
        {
            return VisitSetOpExpression(e);
        }
 
        public override Node Visit(DbTreatExpression e)
        { 
            Op op = _iqtCommand.CreateTreatOp(e.ResultType); 
            return VisitUnary(e, op, VisitExprAsScalar);
        } 

        public override Node Visit(DbIsOfExpression e)
        {
            Op op = null; 
            if (DbExpressionKind.IsOfOnly == e.ExpressionKind)
            { 
                op = _iqtCommand.CreateIsOfOnlyOp(e.OfType); 
            }
            else 
            {
                op = _iqtCommand.CreateIsOfOp(e.OfType);
            }
            return VisitUnary(e, op, VisitExprAsScalar); 
        }
 
        public override Node Visit(DbCastExpression e) 
        {
            Op op = _iqtCommand.CreateCastOp(e.ResultType); 
            return VisitUnary(e, op, VisitExprAsScalar);
        }

        public override Node Visit(DbCaseExpression e) 
        {
            List childNodes = new List(); 
            for (int idx = 0; idx < e.When.Count; idx++) 
            {
                childNodes.Add(VisitExprAsPredicate(e.When[idx])); 
                // Make sure that each then-clause is the same type as the result
                childNodes.Add(BuildSoftCast(VisitExprAsScalar(e.Then[idx]), e.ResultType));
            }
 
            // Make sure that the else-clause is the same type as the result
            childNodes.Add(BuildSoftCast(VisitExprAsScalar(e.Else), e.ResultType)); 
            return _iqtCommand.CreateNode(_iqtCommand.CreateCaseOp(e.ResultType), childNodes); 
        }
 
        public override Node Visit(DbOfTypeExpression e)
        {
            //
            // The argument to OfType must be a collection 
            //
            PlanCompiler.Assert(TypeSemantics.IsCollectionType(e.Argument.ResultType), "Non-Collection Type Argument in DbOfTypeExpression"); 
 
            //
            // Visit the collection argument and ensure that it is a RelOp suitable for subsequent use in the Filter/Project used to convert OfType. 
            //
            Node inputNode = EnsureRelOp(VisitExpr(e.Argument));

            // 
            // Retrieve the Var produced by the RelOp input.
            // 
            Var inputVar = _varMap[inputNode]; 

            // 
            // Build the OfType expression tree
            //
            bool isOfOnly = (DbExpressionKind.OfTypeOnly == e.ExpressionKind);
            Node resultNode; 
            Var resultVar;
            _iqtCommand.BuildOfTypeTree(inputNode, inputVar, e.OfType, !isOfOnly /* include subtypes */, out resultNode, out resultVar); 
 
            //
            // Add the node-var mapping, and return 
            //
            _varMap[resultNode] = resultVar;
            return resultNode;
        } 

        public override Node Visit(DbNewInstanceExpression e) 
        { 
            Op newInstOp = null;
            List relPropertyExprs = null; 
            if (TypeSemantics.IsCollectionType(e.ResultType))
            {
                newInstOp = _iqtCommand.CreateNewMultisetOp(e.ResultType);
            } 
            else if (TypeSemantics.IsRowType(e.ResultType))
            { 
                newInstOp = _iqtCommand.CreateNewRecordOp(e.ResultType); 
            }
            else if (TypeSemantics.IsEntityType(e.ResultType)) 
            {
                List relPropertyList = new List();
                relPropertyExprs = new List();
                if (e.HasRelatedEntityReferences) 
                {
                    foreach (DbRelatedEntityRef targetRef in e.RelatedEntityReferences) 
                    { 
                        RelProperty relProperty = new RelProperty((RelationshipType)targetRef.TargetEnd.DeclaringType, targetRef.SourceEnd, targetRef.TargetEnd);
                        relPropertyList.Add(relProperty); 
                        Node relPropertyNode = VisitExprAsScalar(targetRef.TargetEntityReference);
                        relPropertyExprs.Add(relPropertyNode);
                    }
                } 
                newInstOp = _iqtCommand.CreateNewEntityOp(e.ResultType, relPropertyList);
            } 
            else 
            {
                newInstOp = _iqtCommand.CreateNewInstanceOp(e.ResultType); 
            }

            //
            // Build up the list of arguments. Make sure that they match 
            // the expected types (and add "soft" casts, if needed)
            // 
            List newArgs = new List(); 
            if (TypeSemantics.IsStructuralType(e.ResultType))
            { 
                StructuralType resultType = TypeHelpers.GetEdmType(e.ResultType);
                int i = 0;
                foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(resultType))
                { 
                    Node newArg = BuildSoftCast(VisitExprAsScalar(e.Arguments[i]), Helper.GetModelTypeUsage(m));
                    newArgs.Add(newArg); 
                    i++; 
                }
            } 
            else
            {
                CollectionType resultType = TypeHelpers.GetEdmType(e.ResultType);
                TypeUsage elementTypeUsage = resultType.TypeUsage; 
                foreach (DbExpression arg in e.Arguments)
                { 
                    Node newArg = BuildSoftCast(VisitExprAsScalar(arg), elementTypeUsage); 
                    newArgs.Add(newArg);
                } 
            }

            if (relPropertyExprs != null)
            { 
                newArgs.AddRange(relPropertyExprs);
            } 
            Node node = _iqtCommand.CreateNode(newInstOp, newArgs); 

            return node; 
        }

        public override Node Visit(DbRefExpression e)
        { 
            // SQLBUDT #502617: Creating a collection of refs throws an Assert
            // A SoftCastOp may be required if the argument to the RefExpression is only promotable 
            // to the row type produced from the key properties of the referenced Entity type. Since 
            // this row type is not actually represented anywhere in the tree it must be built here in
            // order to determine whether or not the SoftCastOp should be applied. 
            //
            Op op = _iqtCommand.CreateRefOp(e.EntitySet, e.ResultType);
            Node newArg = BuildSoftCast(VisitExprAsScalar(e.Argument), TypeHelpers.CreateKeyRowType(e.EntitySet.ElementType, _iqtCommand.MetadataWorkspace));
            return _iqtCommand.CreateNode(op, newArg); 
        }
 
        public override Node Visit(DbRelationshipNavigationExpression e) 
        {
            RelProperty relProperty = new RelProperty(e.Relationship, e.NavigateFrom, e.NavigateTo); 
            Op op = _iqtCommand.CreateNavigateOp(e.ResultType, relProperty);
            Node arg = VisitExprAsScalar(e.NavigationSource);
            return _iqtCommand.CreateNode(op, arg);
        } 

        public override Node Visit(DbDerefExpression e) 
        { 
            Op op = _iqtCommand.CreateDerefOp(e.ResultType);
            return VisitUnary(e, op, VisitExprAsScalar); 
        }

        public override Node Visit(DbRefKeyExpression e)
        { 
            Op op = _iqtCommand.CreateGetRefKeyOp(e.ResultType);
            return VisitUnary(e, op, VisitExprAsScalar); 
        } 

        public override Node Visit(DbEntityRefExpression e) 
        {
            Op op = _iqtCommand.CreateGetEntityRefOp(e.ResultType);
            return VisitUnary(e, op, VisitExprAsScalar);
        } 

        public override Node Visit(DbScanExpression e) 
        { 
            // Create a new table definition
            TableMD tableMetadata = Command.CreateTableDefinition(e.Target); 

            // Create a scan table operator
            ScanTableOp op = _iqtCommand.CreateScanTableOp(tableMetadata);
 
            // Map the ScanTableOp to the ColumnVar of the Table's single column of the Extent's element type
            Node node = _iqtCommand.CreateNode(op); 
            Var singleColumn = op.Table.Columns[0]; 
            _varMap[node] = singleColumn;
 
            return node;
        }

        public override Node Visit(DbFilterExpression e) 
        {
            // 
            // Visit the Predicate with the Input binding's variable in scope 
            //
            Node inputSetNode = EnterExpressionBinding(e.Input); 
            Node predicateNode = VisitExprAsPredicate(e.Predicate);
            ExitExpressionBinding();

            Op filtOp = _iqtCommand.CreateFilterOp(); 

            // Update the Node --> Var mapping. Filter maps to the same Var as its input. 
            Node filtNode = _iqtCommand.CreateNode(filtOp, inputSetNode, predicateNode); 
            _varMap[filtNode] = _varMap[inputSetNode];
 
            return filtNode;
        }

        public override Node Visit(DbProjectExpression e) 
        {
            // check if this is the discriminated projection for a query mapping view 
            if (e == this._discriminatedViewTopProject) 
            {
                return GenerateDiscriminatedProject(e); 
            }
            else
            {
                return GenerateStandardProject(e); 
            }
        } 
 
        private Node GenerateDiscriminatedProject(DbProjectExpression e)
        { 
            PlanCompiler.Assert(null != _discriminatedViewTopProject, "if a project matches the pattern, there must be a corresponding discriminator map");

            // convert the input to the top level projection
            Node source = EnterExpressionBinding(e.Input); 

            List relPropertyList = new List(); 
            List relPropertyExprs = new List(); 
            foreach (KeyValuePair kv in _discriminatorMap.RelPropertyMap)
            { 
                relPropertyList.Add(kv.Key);
                relPropertyExprs.Add(VisitExprAsScalar(kv.Value));
            }
 
            // construct a DiscriminatedNewInstanceOp
            DiscriminatedNewEntityOp newInstOp = _iqtCommand.CreateDiscriminatedNewEntityOp(e.Projection.ResultType, 
                new ExplicitDiscriminatorMap(_discriminatorMap), _discriminatorMap.EntitySet, relPropertyList); 

            // args include all projected properties and discriminator and the relProperties 
            List newArgs = new List(_discriminatorMap.PropertyMap.Count + 1);
            newArgs.Add(CreateNewInstanceArgument(_discriminatorMap.Discriminator.Property, _discriminatorMap.Discriminator));
            foreach (var propertyMap in _discriminatorMap.PropertyMap)
            { 
                DbExpression value = propertyMap.Value;
                EdmProperty property = propertyMap.Key; 
                Node newArg = CreateNewInstanceArgument(property, value); 
                newArgs.Add(newArg);
            } 
            newArgs.AddRange(relPropertyExprs);

            Node newInstNode = _iqtCommand.CreateNode(newInstOp, newArgs);
            ExitExpressionBinding(); 

            Var sourceVar; 
            Node varDefListNode = _iqtCommand.CreateVarDefListNode(newInstNode, out sourceVar); 

            ProjectOp projOp = _iqtCommand.CreateProjectOp(sourceVar); 
            Node projNode = _iqtCommand.CreateNode(projOp, source, varDefListNode);
            _varMap[projNode] = sourceVar;

            return projNode; 
        }
 
        private Node CreateNewInstanceArgument(EdmMember property, DbExpression value) 
        {
            Node newArg = BuildSoftCast(VisitExprAsScalar(value), Helper.GetModelTypeUsage(property)); 
            return newArg;
        }

        private Node GenerateStandardProject(DbProjectExpression e) 
        {
            Node projectedSetNode = EnterExpressionBinding(e.Input); 
            Node projectionNode = VisitExprAsScalar(e.Projection); 
            ExitExpressionBinding();
 
            Var projectionVar;
            Node varDefListNode = _iqtCommand.CreateVarDefListNode(projectionNode, out projectionVar);

            ProjectOp projOp = _iqtCommand.CreateProjectOp(projectionVar); 
            Node projNode = _iqtCommand.CreateNode(projOp, projectedSetNode, varDefListNode);
            _varMap[projNode] = projectionVar; 
 
            return projNode;
        } 

        public override Node Visit(DbCrossJoinExpression e)
        {
            return VisitJoin(e, e.Inputs, null); 
        }
 
        public override Node Visit(DbJoinExpression e) 
        {
            List inputs = new List(); 
            inputs.Add(e.Left);
            inputs.Add(e.Right);

            return VisitJoin(e, inputs, e.JoinCondition); 
        }
 
        private Node VisitJoin(DbExpression e, IList inputs, DbExpression joinCond) 
        {
            // 
            // Assert that the JoinType is covered. If JoinTypes are added to CQT then the
            // switch statement that constructs the JoinOp must be updated, along with this assert.
            //
            PlanCompiler.Assert(DbExpressionKind.CrossJoin == e.ExpressionKind || 
                            DbExpressionKind.InnerJoin == e.ExpressionKind ||
                            DbExpressionKind.LeftOuterJoin == e.ExpressionKind || 
                            DbExpressionKind.FullOuterJoin == e.ExpressionKind, 
                            "Unrecognized JoinType specified in DbJoinExpression");
 
#if DEBUG
            //
            // Assert that the DbJoinExpression is producing a collection result with a record element type.
            // !!! IsCollectionOfRecord() is defined only in DEBUG  !!! 
            PlanCompiler.Assert(IsCollectionOfRecord(e.ResultType), "Invalid Type returned by DbJoinExpression");
#endif 
 
            //
            // Bring the variables for the Join inputs into scope, track their nodes and vars, and visit the Join condition, if present. 
            //
            List inputNodes = new List();
            List inputVars = new List();
 
            for(int idx = 0; idx < inputs.Count; idx++)
            { 
                Node inputNode = EnterExpressionBinding(inputs[idx]); 
                inputNodes.Add(inputNode);
                inputVars.Add(_varMap[inputNode]); 
            }

            Node joinCondNode = VisitExprAsPredicate(joinCond);
 
            //
            // Remove the input variables from scope after visiting the Join condition. 
            // 
            for (int scopeCount = 0; scopeCount < inputNodes.Count; scopeCount++)
            { 
                ExitExpressionBinding();
            }

            // 
            // Create an appropriate JoinOp based on the JoinType specified in the DbJoinExpression.
            // 
            JoinBaseOp joinOp = null; 
            switch (e.ExpressionKind)
            { 
                case DbExpressionKind.CrossJoin:
                    {
                        joinOp = _iqtCommand.CreateCrossJoinOp();
                    } 
                    break;
 
                case DbExpressionKind.InnerJoin: 
                    {
                        joinOp = _iqtCommand.CreateInnerJoinOp(); 
                    }
                    break;

                case DbExpressionKind.LeftOuterJoin: 
                    {
                        joinOp = _iqtCommand.CreateLeftOuterJoinOp(); 
                    } 
                    break;
 
                case DbExpressionKind.FullOuterJoin:
                    {
                        joinOp = _iqtCommand.CreateFullOuterJoinOp();
                    } 
                    break;
            } 
 
            //
            // Assert that a JoinOp was produced. This check is again in case a new JoinType is introduced to CQT and this method is not updated. 
            //
            PlanCompiler.Assert(joinOp != null, "Unrecognized JoinOp specified in DbJoinExpression, no JoinOp was produced");

            // 
            // If the Join condition was present then add its converted form to the list of child nodes for the new Join node.
            // 
            if (e.ExpressionKind != DbExpressionKind.CrossJoin) 
            {
                PlanCompiler.Assert(joinCondNode != null, "Non CrossJoinOps must specify a join condition"); 
                inputNodes.Add(joinCondNode);
            }

            // 
            // Create and return a new projection that unifies the multiple vars produced by the Join columns into a single record constructor.
            // 
            return ProjectNewRecord( 
                _iqtCommand.CreateNode(joinOp, inputNodes),
                ExtractElementRowType(e.ResultType), 
                inputVars
            );
        }
 
        public override Node Visit(DbApplyExpression e)
        { 
#if DEBUG 
            //
            // Assert that the DbJoinExpression is producing a collection result with a record element type. 
            // !!! IsCollectionOfRecord() is defined only in DEBUG  !!!
            PlanCompiler.Assert(IsCollectionOfRecord(e.ResultType), "Invalid Type returned by DbApplyExpression");
#endif
 
            //
            // Bring the Input set's variable into scope 
            // 
            Node inputNode = EnterExpressionBinding(e.Input);
 
            //
            // Visit the Apply expression with the Input's variable in scope.
            // This is done via EnterExpressionBinding, which is allowable only because
            // it will only bring the Apply variable into scope *after* visiting the Apply expression 
            // (which means that the Apply expression cannot validly reference its own binding variable)
            // 
            Node applyNode = EnterExpressionBinding(e.Apply); 

            // 
            // Remove the Apply and Input variables from scope
            //
            ExitExpressionBinding(); // for the Apply
            ExitExpressionBinding(); // for the Input 

            // 
            // The ApplyType should only be either CrossApply or OuterApply. 
            //
            PlanCompiler.Assert(DbExpressionKind.CrossApply == e.ExpressionKind || DbExpressionKind.OuterApply == e.ExpressionKind, "Unrecognized DbExpressionKind specified in DbApplyExpression"); 

            //
            // Create a new Node with the correct ApplyOp as its Op and the input and apply nodes as its child nodes.
            // 
            ApplyBaseOp applyOp = null;
            if (DbExpressionKind.CrossApply == e.ExpressionKind) 
            { 
                applyOp = _iqtCommand.CreateCrossApplyOp();
            } 
            else
            {
                applyOp = _iqtCommand.CreateOuterApplyOp();
            } 

            Node retNode = _iqtCommand.CreateNode(applyOp, inputNode, applyNode); 
 
            //
            // Create and return a new projection that unifies the vars produced by the input and apply columns into a single record constructor. 
            //
            return ProjectNewRecord(
                retNode,
                ExtractElementRowType(e.ResultType), 
                new Var[] { _varMap[inputNode], _varMap[applyNode] }
            ); 
        } 

        public override Node Visit(DbGroupByExpression e) 
        {
#if DEBUG
            // !!! IsCollectionOfRecord() is defined only in DEBUG  !!!
            PlanCompiler.Assert(IsCollectionOfRecord(e.ResultType), "DbGroupByExpression has invalid result Type (not record collection)"); 
#endif
 
            VarVec keyVarSet = _iqtCommand.CreateVarVec(); 
            VarVec outputVarSet = _iqtCommand.CreateVarVec();
 
            //
            // Bring the Input variable from the DbGroupByExpression into scope
            //
            Node inputNode = EnterGroupExpressionBinding(e.Input); 

            // 
            // Process the Keys: For each Key, produce the corresponding IQT conversion. 
            // The converted Node is then used as the child node of a VarDefOp Node that is
            // added to a list of Key VarDefs. The Var defined by the converted Key expression 
            // is added to both the overall list of Vars produced by the GroupBy and the list of Key vars produced by the GroupBy.
            //
            List keyVarDefNodes = new List();
            for(int idx = 0; idx < e.Keys.Count; idx++) 
            {
                DbExpression keyExpr = e.Keys[idx]; 
 
                Node keyNode = VisitExprAsScalar(keyExpr);
                ScalarOp keyOp = keyNode.Op as ScalarOp; 

                //
                // In a valid CQT, each group key expressions will result in a ScalarOp since they
                // must be of an equality comparable type. 
                //
                PlanCompiler.Assert(keyOp != null, "GroupBy Key is not a ScalarOp"); 
 
                //
                // Create a ComputedVar with the same type as the Key and add it to both the set of output Vars produced by the GroupBy and the set of Key vars. 
                //
                Var keyVar;
                //
                // Create a VarDefOp that uses the converted form of the Key to define the ComputedVar and add it to the list of Key VarDefs. 
                //
                keyVarDefNodes.Add(_iqtCommand.CreateVarDefNode(keyNode, out keyVar)); 
                outputVarSet.Set(keyVar); 
                keyVarSet.Set(keyVar);
            } 

            //
            // Before the Aggregates are processed, the Input variable must be taken out of scope and the 'group' variable introduced into scope in its place
            // This is done as follows: 
            // 1. Pop the current ExpressionBindingScope from the stack
            // 2. Create a new ExpressionBindingScope using the same Var but the name of the 'group' variable from the DbGroupByExpression's DbGroupExpressionBinding 
            // 3. Push this new scope onto the variable scope stack. 
            //
            ExpressionBindingScope scope = ExitExpressionBinding(); 
            scope = new ExpressionBindingScope(_iqtCommand, e.Input.GroupVariableName, scope.ScopeVar);
            _varScopes.Push(scope);

            // 
            // Process the Aggregates: For each DbAggregate, produce the corresponding IQT conversion depending on whether the DbAggregate is a DbFunctionAggregate or NestAggregate.
            // The converted Node is then used as the child node of a VarDefOp Node that is added to a list of Aggregate VarDefs. 
            // The Var defined by the converted DbAggregate is added only to the overall list of Vars produced by the GroupBy (not the list of Keys). 
            //
            List aggVarDefNodes = new List(); 
            for(int idx = 0; idx < e.Aggregates.Count; idx++)
            {
                DbAggregate agg = e.Aggregates[idx];
 
                //
                // Produce the converted form of the Arguments to the aggregate 
                // 
                IList argNodes = VisitExprAsScalar(agg.Arguments);
 
                Node aggNode = null;
                TypeUsage aggType = null;

                // 
                // Currently only DbFunctionAggregate is supported
                // 
                DbFunctionAggregate funcAgg = agg as DbFunctionAggregate; 
                PlanCompiler.Assert(funcAgg != null, "Unrecognized DbAggregate used in DbGroupByExpression");
 
                //
                // Convert the aggregate according to its type
                //
                aggType = funcAgg.Function.ReturnParameter.TypeUsage; 
                aggNode = _iqtCommand.CreateNode(
                    _iqtCommand.CreateAggregateOp(funcAgg.Function, funcAgg.Distinct), 
                    argNodes 
                );
 
                //
                // Create a ComputedVar with the same type as the output Type of the DbAggregate and add it only to the set of output Vars produced by the GroupBy
                //
                Var aggVar; 
                //
                // Create a VarDefOp that uses the converted form of the DbAggregate to define the ComputedVar and add it to the list of DbAggregate VarDefs. 
                // 
                aggVarDefNodes.Add(_iqtCommand.CreateVarDefNode(aggNode, out aggVar));
                outputVarSet.Set(aggVar); 
            }

            //
            // The Aggregates have now been processed, so remove the group variable from scope. 
            //
            ExitGroupExpressionBinding(); 
 
            //
            // Construct the GroupBy. This consists of a GroupByOp Node with 3 children: 
            // 1. The Node produced from the Input set
            // 2. A VarDefListOp Node that uses the Key VarDefs to define the Key Vars (created above)
            // 3. A VarDefListOp Node that uses the Aggregate VarDefs to define the Aggregate Vars (created above)
            // 
            Node groupByNode = _iqtCommand.CreateNode(
                _iqtCommand.CreateGroupByOp(keyVarSet, outputVarSet), 
 
                // The Node produced from the Input set
                inputNode, 

                // The Key VarDefs
                _iqtCommand.CreateNode(
                    _iqtCommand.CreateVarDefListOp(), 
                    keyVarDefNodes
                ), 
 
                // The Aggregate VarDefs
                _iqtCommand.CreateNode( 
                    _iqtCommand.CreateVarDefListOp(),
                    aggVarDefNodes
                )
            ); 

            // 
            // Create and return a projection that unifies the multiple output vars of the GroupBy into a single record constructor. 
            //
            return ProjectNewRecord( 
                groupByNode,
                ExtractElementRowType(e.ResultType),
                outputVarSet
            ); 
        }
 
        ///  
        /// Common processing for the identical input and sort order arguments to the unrelated
        /// DbSkipExpression and DbSortExpression types. 
        /// 
        /// The input DbExpressionBinding from the DbSkipExpression or DbSortExpression
        /// The list of SortClauses from the DbSkipExpression or DbSortExpression
        /// A list to contain the converted SortKeys produced from the SortClauses 
        /// The Var produced by the input to the DbSkipExpression or DbSortExpression
        ///  
        ///     The converted form of the input to the DbSkipExpression or DbSortExpression, capped by a 
        ///     ProjectOp that defines and Vars referenced by the SortKeys.
        ///  
        private Node VisitSortArguments(DbExpressionBinding input, IList sortOrder, List sortKeys, out Var inputVar)
        {
            //
            // Skip/DbSortExpression conversion first produces a ProjectOp over the original input. 
            // This is done to ensure that the new (Constrained)SortOp itself does not
            // contain any local variable definitions (in the form of a VarDefList child node) 
            // which makes it simpler to pull SortOps over ProjectOps later in the PlanCompiler 
            // (specifically the PreProcessor).
            // The new ProjectOp projects the output Var of the input along with any Vars referenced 
            // by the SortKeys, and its VarDefList child defines those Vars.

            //
            // Bring the variable defined by the DbSortExpression's input set into scope 
            // and retrieve it from the Node => Var map for later use.
            // 
            Node inputNode = EnterExpressionBinding(input); 
            inputVar = _varMap[inputNode];
 
            //
            // Convert the SortClauses, building a new VarDefOp Node for each one.
            //
            VarVec projectedVars = _iqtCommand.CreateVarVec(); 
            projectedVars.Set(inputVar);
 
            List sortVarDefs = new List(); 
            PlanCompiler.Assert(sortKeys.Count == 0, "Non-empty SortKey list before adding converted SortClauses");
            for (int idx = 0; idx < sortOrder.Count; idx++) 
            {
                DbSortClause clause = sortOrder[idx];

                // 
                // Convert the DbSortClause DbExpression to a Node/Op pair
                // 
                Node exprNode = VisitExprAsScalar(clause.Expression); 

                // 
                // In a valid CQT, DbSortClause expressions must have a result of an OrderComparable Type,
                // and such expressions will always convert to ScalarOps.
                //
                ScalarOp specOp = exprNode.Op as ScalarOp; 
                PlanCompiler.Assert(specOp != null, "DbSortClause Expression converted to non-ScalarOp");
 
                // 
                // Create a new ComputedVar with the same Type as the result Type of the DbSortClause DbExpression
                // 
                Var specVar;

                //
                // Create a new VarDefOp Node that defines the ComputedVar and add it both to the 
                // list of VarDefs and the VarVec of produced Vars that will be used to create a
                // SortKey-defining ProjectOp over the Sort input. 
                // 
                sortVarDefs.Add(_iqtCommand.CreateVarDefNode(exprNode, out specVar));
                projectedVars.Set(specVar); 

                //
                // Create a new IQT SortKey that references the ComputedVar and has the same
                // Ascending and Collation as the original DbSortClause, then add it to the list of SortKeys. 
                //
                SortKey sortKey = null; 
                if (string.IsNullOrEmpty(clause.Collation)) 
                {
                    sortKey = Command.CreateSortKey(specVar, clause.Ascending); 
                }
                else
                {
                    sortKey = Command.CreateSortKey(specVar, clause.Ascending, clause.Collation); 
                }
                sortKeys.Add(sortKey); 
            } 

            // 
            // Now that the SortClauses have been converted, remove the Input set's variable from scope.
            //
            ExitExpressionBinding();
 
            //
            // Cap the Input with a ProjectOp that pushes the sort key VarDefs down to that projection. 
            // 
            inputNode =
                _iqtCommand.CreateNode( 
                    _iqtCommand.CreateProjectOp(projectedVars),
                    inputNode,
                    _iqtCommand.CreateNode(
                        _iqtCommand.CreateVarDefListOp(), 
                        sortVarDefs
                    ) 
                ); 

            return inputNode; 
        }

        public override Node Visit(DbSkipExpression expression)
        { 
            //
            // Invoke common processing of Skip/DbSortExpression arguments. 
            // 
            Var inputVar;
            List sortKeys = new List(); 
            Node inputNode = VisitSortArguments(expression.Input, expression.SortOrder, sortKeys, out inputVar);

            //
            // Visit the Skip Count 
            //
            Node countNode = VisitExprAsScalar(expression.Count); 
 
            //
            // Create a new Node that has a new ConstrainedSortOp based on the SortKeys as its Op 
            // and the following children:
            // - The Input node from VisitSortArguments
            // - The converted form of the skip count
            // - A NullOp of type Int64 to indicate that no limit operation is applied 
            //
            Node skipNode = 
                _iqtCommand.CreateNode( 
                    _iqtCommand.CreateConstrainedSortOp(sortKeys),
                    inputNode, 
                    countNode,
                    _iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.IntegerType))
                );
 
            // Update the Node --> Var mapping for the new ConstrainedSort Node.
            // ConstrainedSortOp maps to the same Op that its RelOp input maps to. 
            _varMap[skipNode] = inputVar; 

            return skipNode; 
        }

        public override Node Visit(DbSortExpression e)
        { 
            //
            // Invoke common processing of Skip/DbSortExpression arguments. 
            // 
            Var inputVar;
            List sortKeys = new List(); 
            Node inputNode = VisitSortArguments(e.Input, e.SortOrder, sortKeys, out inputVar);

            //
            // Create a new SortOp that uses the constructed SortKeys. 
            //
            SortOp newSortOp = _iqtCommand.CreateSortOp(sortKeys); 
 
            //
            // Create a new SortOp Node that has the new SortOp as its Op the Key-defining ProjectOp Node as its only child. 
            //
            Node newSortNode = _iqtCommand.CreateNode(newSortOp, inputNode);

            // Update the Node --> Var mapping for the new Sort Node. 
            // SortOp maps to the same Op that its RelOp input maps to.
            _varMap[newSortNode] = inputVar; 
 
            return newSortNode;
        } 

        public override Node Visit(DbQuantifierExpression e)
        {
            Node retNode = null; 

            // 
            // Any converts to Exists(Filter(Input, Predicate)) 
            // All converts to Not(Exists(Filter(Input, Or(Not(Predicate), IsNull(Predicate)))))
            // 
            PlanCompiler.Assert(DbExpressionKind.Any == e.ExpressionKind || DbExpressionKind.All == e.ExpressionKind, "Invalid DbExpressionKind in DbQuantifierExpression");

            //
            // Bring the input's variable into scope 
            //
            Node inputNode = EnterExpressionBinding(e.Input); 
 
            //
            // Convert the predicate 
            //
            Node predicateNode = VisitExprAsPredicate(e.Predicate);

            // 
            // If the quantifier is All then the predicate must become 'Not(Predicate) Or IsNull(Predicate)',
            // since the converted form of the predicate should exclude a member of the input set if and only if 
            // the predicate evaluates to False - filtering only with the negated predicate would also exclude members 
            // for which that negated predicate evaluates to null, possibly resulting in an erroneous empty result set
            // and causing the quantifier to produce a false positive result. 
            //
            if (DbExpressionKind.All == e.ExpressionKind)
            {
                // Create the 'Not(Predicate)' branch of the Or. 
                predicateNode = _iqtCommand.CreateNode(
                    _iqtCommand.CreateConditionalOp(OpType.Not), 
                    predicateNode 
                );
 
                // Visit the original predicate for use in the 'IsNull(Predicate)' branch of the Or.
                // Note that this is treated as a scalar value rather than a Boolean predicate.
                Node predicateCopy = VisitExprAsScalar(e.Predicate);
 
                // Create the 'IsNull(Predicate)' branch of the Or.
                predicateCopy = _iqtCommand.CreateNode( 
                    _iqtCommand.CreateConditionalOp(OpType.IsNull), 
                    predicateCopy
                ); 

                // Finally, combine the branches with a Boolean 'Or' Op to create the updated predicate node.
                predicateNode = _iqtCommand.CreateNode(
                    _iqtCommand.CreateConditionalOp(OpType.Or), 
                    predicateNode,
                    predicateCopy 
                ); 
            }
 
            //
            // Remove the input's variable from scope
            //
            ExitExpressionBinding(); 

            // 
            // Create a FilterOp around the original input set and map the FilterOp to the Var produced by the original input set. 
            //
            Var inputVar = _varMap[inputNode]; 
            inputNode = _iqtCommand.CreateNode(_iqtCommand.CreateFilterOp(), inputNode, predicateNode);
            _varMap[inputNode] = inputVar;

            // 
            // Create an ExistsOp around the filtered set to perform the quantifier operation.
            // 
            retNode = _iqtCommand.CreateNode(_iqtCommand.CreateExistsOp(), inputNode); 

            // 
            // For All, the exists operation as currently built must now be negated.
            //
            if (DbExpressionKind.All == e.ExpressionKind)
            { 
                retNode = _iqtCommand.CreateNode(_iqtCommand.CreateConditionalOp(OpType.Not), retNode);
            } 
 
            return retNode;
        } 

        #endregion
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK