ExpressionConverter.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Dotnetfx_Vista_SP2 / Dotnetfx_Vista_SP2 / 8.0.50727.4016 / DEVDIV / depot / DevDiv / releases / Orcas / QFE / ndp / fx / src / DataEntity / System / Data / Objects / ELinq / ExpressionConverter.cs / 2 / ExpressionConverter.cs

                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....]
//--------------------------------------------------------------------- 
 
using CqtExpression = System.Data.Common.CommandTrees.DbExpression;
using LinqExpression = System.Linq.Expressions.Expression; 
using System.Linq.Expressions;
using System.Collections.ObjectModel;
using System.Linq;
using System.Collections.Generic; 
using System.Data.Common.CommandTrees;
using System.Data.Metadata.Edm; 
using System.Reflection; 
using System.Data.Common.EntitySql;
using System.Diagnostics; 
using System.Data.Common;
using System.Globalization;
using System.Data.Common.Utils;
using System.Data.Objects.DataClasses; 
using System.Data.Objects.Internal;
using System.Collections; 
using System.Data.Entity; 
using System.Text;
using System.Data.Common.CommandTrees.Internal; 

namespace System.Data.Objects.ELinq
{
    ///  
    /// Class supporting conversion of LINQ expressions to EDM CQT expressions.
    ///  
    internal sealed partial class ExpressionConverter 
    {
        #region Fields 
        private readonly ObjectContext _context;
        private readonly DbCommandTree _commandTree;
        private readonly TypeResolver _typeResolver;
        private readonly BindingContext _bindingContext; 
        private readonly Dictionary _groupByDefaultToOptimizedTranslationMap;
        private readonly Dictionary _variableNameToInputExpression; 
        private readonly Dictionary> _aggregateDefaultTranslationToOptimizedTranslationInfoMap; 
        private readonly Expression _expression;
        private readonly Expression _innerExpression; 
        private readonly HashSet _closureCandidates = new HashSet();
        private readonly Stack _linqExpressionStack = new Stack();
        private Dictionary _spanMappings;
        private MergeOption? _mergeOption; 
        private List _closureBindings;
        private Dictionary _initializers; 
        private ObjectParameterCollection _parameters; 
        private Span _span;
 
        private const string s_visualBasicAssemblyFullName =
            "Microsoft.VisualBasic, Version=8.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a";
        private static readonly Dictionary s_translators = InitializeTranslators();
 
        internal const string s_entityCollectionCountPropertyName = "Count";
        internal const string s_nullableHasValuePropertyName = "HasValue"; 
        internal const string s_nullableValuePropertyName = "Value"; 

        ///  
        /// Gets the name of the key column appearing in ELinq GroupBy projections
        /// 
        internal const string KeyColumnName = "Key";
 
        /// 
        /// Gets the name of the group column appearing in ELinq CQTs (used in GroupBy expressions) 
        ///  
        internal const string GroupColumnName = "Group";
 
        /// 
        /// Gets the name of the parent column appearing in ELinq EntityCollection projections
        /// 
        internal const string EntityCollectionOwnerColumnName = "Owner"; 

        ///  
        /// Gets the name of the children column appearing in ELinq EntityCollection projections 
        /// 
        internal const string EntityCollectionElementsColumnName = "Elements"; 

        /// 
        /// The Edm namespace name, used for canonical functions
        ///  
        internal const string EdmNamespaceName = "Edm";
 
        #region Canonical Function Names 
        private const string Concat = "Concat";
        private const string IndexOf = "IndexOf"; 
        private const string Length = "Length";
        private const string Right = "Right";
        private const string Substring = "Substring";
        private const string ToUpper = "ToUpper"; 
        private const string ToLower = "ToLower";
        private const string LTrim = "LTrim"; 
        private const string RTrim = "RTrim"; 
        private const string BitwiseAnd = "BitwiseAnd";
        private const string BitwiseOr = "BitwiseOr"; 
        private const string BitwiseNot = "BitwiseNot";
        private const string BitwiseXor = "BitwiseXor";
        private const string CurrentUtcDateTime = "CurrentUtcDateTime";
        private const string CurrentDateTimeOffset = "CurrentDateTimeOffset"; 
        private const string CurrentDateTime = "CurrentDateTime";
        private const string Year = "Year"; 
        private const string Month = "Month"; 
        private const string Day = "Day";
        private const string Hour = "Hour"; 
        private const string Minute = "Minute";
        private const string Second = "Second";
        private const string Millisecond = "Millisecond";
        #endregion 

        #endregion 
 
        #region Constructors and static initializors
        internal ExpressionConverter(ObjectContext objectContext, BindingContext bindingContext, DbCommandTree commandTree, Expression toConvert, ObjectParameterCollection sourceParams) 
        {
            Debug.Assert(objectContext != null, "A binding context is required");
            Debug.Assert(bindingContext != null, "A binding context is required");
            Debug.Assert(commandTree != null, "A command tree is required"); 
            Debug.Assert(toConvert != null, "An expression is required");
 
            _bindingContext = bindingContext; 
            _context = objectContext;
            _commandTree = commandTree; 
            if (sourceParams != null)
            {
                foreach (ObjectParameter sourceParam in sourceParams)
                { 
                    this.AddParameter(sourceParam);
                } 
            } 

            // Normalize the expression 
            _expression = NormalizeExpression(toConvert);

            if (_expression.NodeType == ExpressionType.Lambda)
            { 
                _innerExpression = ((LambdaExpression)_expression).Body;
            } 
            else 
            {
                _innerExpression = _expression; 
            }

            _typeResolver = new TypeResolver(_context.Perspective, StringComparer.Ordinal);
            _groupByDefaultToOptimizedTranslationMap = new Dictionary(); 
            _aggregateDefaultTranslationToOptimizedTranslationInfoMap = new Dictionary>();
            _variableNameToInputExpression = new Dictionary(); 
        } 

        // initialize translator dictionary (which support identification of translators 
        // for LINQ expression node types)
        private static Dictionary InitializeTranslators()
        {
            Dictionary translators = new Dictionary(); 
            foreach (Translator translator in GetTranslators())
            { 
                foreach (ExpressionType nodeType in translator.NodeTypes) 
                {
                    translators.Add(nodeType, translator); 
                }
            }

            return translators; 
        }
 
        private static IEnumerable GetTranslators() 
        {
            yield return new AndAlsoTranslator(); 
            yield return new OrElseTranslator();
            yield return new LessThanTranslator();
            yield return new LessThanOrEqualsTranslator();
            yield return new GreaterThanTranslator(); 
            yield return new GreaterThanOrEqualsTranslator();
            yield return new EqualsTranslator(); 
            yield return new NotEqualsTranslator(); 
            yield return new ConvertTranslator();
            yield return new ConstantTranslator(); 
            yield return new NotTranslator();
            yield return new MemberAccessTranslator();
            yield return new ParameterTranslator();
            yield return new MemberInitTranslator(); 
            yield return new NewTranslator();
            yield return new AddTranslator(); 
            yield return new ConditionalTranslator(); 
            yield return new DivideTranslator();
            yield return new ModuloTranslator(); 
            yield return new SubtractTranslator();
            yield return new MultiplyTranslator();
            yield return new NegateTranslator();
            yield return new UnaryPlusTranslator(); 
            yield return new MethodCallTranslator();
            yield return new CoalesceTranslator(); 
            yield return new AsTranslator(); 
            yield return new IsTranslator();
            yield return new QuoteTranslator(); 
            yield return new AndTranslator();
            yield return new OrTranslator();
            yield return new ExclusiveOrTranslator();
            yield return new NotSupportedTranslator( 
                ExpressionType.LeftShift,
                ExpressionType.RightShift, 
                ExpressionType.ArrayLength, 
                ExpressionType.ArrayIndex,
                ExpressionType.Invoke, 
                ExpressionType.Lambda,
                ExpressionType.ListInit,
                ExpressionType.NewArrayInit,
                ExpressionType.NewArrayBounds, 
                ExpressionType.Power);
        } 
        #endregion 

        #region Properties 
        private EdmItemCollection EdmItemCollection
        {
            get
            { 
                return (EdmItemCollection)_commandTree.MetadataWorkspace.GetItemCollection(DataSpace.CSpace, true);
            } 
        } 

        private bool IsCompiledQueryMode { get { return _bindingContext.ObjectContext != null; } } 

        internal List ClosureBindings { get { return _closureBindings; } }
        internal ObjectParameterCollection Parameters { get { return _parameters; } }
        internal MergeOption? PropagatedMergeOption { get { return _mergeOption; } } 
        internal Span PropagatedSpan { get { return _span; } }
 
        #endregion 

        #region Internal methods 
        // Convert the LINQ expression to a CQT expression and (optional) Span information.
        // Span information will only be present if ObjectQuery instances that specify Spans
        // are referenced from the LINQ expression in a manner consistent with the Span combination
        // rules, otherwise the Span for the CQT expression will be null. 
        internal CqtExpression Convert()
        { 
            CqtExpression result = this.TranslateExpression(_expression); 
            if (!TryGetSpan(result, out _span))
            { 
                _span = null;
            }
            return result;
        } 

        internal static bool CanTranslatePropertyInfo(PropertyInfo propertyInfo) 
        { 
            return MemberAccessTranslator.CanTranslatePropertyInfo(propertyInfo);
        } 
        #endregion

        #region Private Methods
 
        private LinqExpression NormalizeExpression(LinqExpression expression)
        { 
            HashSet clientEvaluationCandidates = new HashSet(); 
            LinqMaximalSubtreeNominator.Nominate(expression, clientEvaluationCandidates, ExpressionEvaluator.IsExpressionNodeClientEvaluatable);
            expression = LinqTreeNodeEvaluator.Evaluate(expression, clientEvaluationCandidates); 

            // find all the nodes in the closure branches, storing them in _closureCandidates
            LinqMaximalSubtreeNominator.Nominate(expression, _closureCandidates,
                         e => ExpressionEvaluator.IsExpressionNodeClientEvaluatable(e) || ExpressionEvaluator.IsExpressionNodeAClosure(e)); 

            // normalize the expression (eliminate/rewrite compiler or CLR specific expressions). 
            LinqExpressionNormalizer normalizer = new LinqExpressionNormalizer(); 
            expression = normalizer.Visit(expression);
 
            return expression;
        }

        ///  
        /// Adds the specified closure binding, optionally adding the associated
        /// ObjectParameter (if any) to the Parameters collection. Parameters 
        /// have already been copied over if this method is called from 
        /// ApplyLinqStateTo, which goes through AddClosureBindingWithoutParameter to get here.
        /// to copy query state from one Linq ObjectQuery to another, and so 
        /// ClosureBinding parameters need not be added here in that case.
        /// 
        /// The ClosureBinding to add to the set of ClosureBindings
        ///  
        /// Specifies whether the ClosureBinding's ObjectParameter (for a ParameterBinding)
        /// should be added to the Parameters collection. 
        ///  
        private void AddClosureBinding(ClosureBinding binding, bool addParam)
        { 
            Debug.Assert(null != binding, "Closure binding cannot be null");
            if (_closureBindings == null)
            {
                _closureBindings = new List(); 
            }
 
            _closureBindings.Add(binding); 
            if (addParam && null != binding.Parameter)
            { 
                AddParameter(binding.Parameter);
            }
        }
 
        /// 
        /// Adds a new closure parameter to the query context. 
        ///  
        /// 
        ///     Binding to add to the context. 
        /// 
        internal void AddClosureBinding(ClosureBinding binding)
        {
            AddClosureBinding(binding, true); 
        }
 
        // Requires: metadata must not be null. 
        //
        // Effects: adds initializer metadata to this query context. 
        //
        // Ensures that the given initializer metadata is valid within the current converter context.
        // We do not allow two incompatible structures representing the same type within a query, e.g.,
        // 
        //      outer.Join(inner, o => new Foo { X = o.ID }, i => new Foo { Y = i.ID }, ...
        // 
        // since this introduces a discrepancy between the CLR (where comparisons between Foo are aware 
        // of both X and Y) and in ELinq (where comparisons are based on the row structure only), resulting
        // in the following join predicates: 
        //
        //      Linq: foo1 == foo2 (which presumably amounts to foo1.X == foo2.X && foo1.Y == foo2.Y
        //      ELinq: foo1.X == foo2.Y
        // 
        // Similar problems occur with set operations such as Union and Concat, where one of the initialization
        // patterns may be ignored. 
        // 
        // This method performs an overly strict check, requiring that all initializers for a given type
        // are structurally equivalent. 
        internal void ValidateInitializerMetadata(InitializerMetadata metadata)
        {
            Debug.Assert(null != metadata);
            InitializerMetadata existingMetadata; 
            if (_initializers != null && _initializers.TryGetValue(metadata.ClrType, out existingMetadata))
            { 
                // Verify the initializers are compatible. 
                if (!metadata.Equals(existingMetadata))
                { 
                    throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedHeterogeneousInitializers(
                        ExpressionConverter.DescribeClrType(metadata.ClrType)));
                }
            } 
            else
            { 
                // Register the metadata so that subsequent initializers for this type can be verified. 
                if (_initializers == null)
                { 
                    _initializers = new Dictionary();
                }
                _initializers.Add(metadata.ClrType, metadata);
            } 
        }
 
        private void AddParameter(ObjectParameter newParam) 
        {
            if (_parameters == null) 
            {
                _parameters = new ObjectParameterCollection(_context.Perspective);
            }
 
            _parameters.Add(newParam);
        } 
 
        private bool IsQueryRoot(Expression linqExpression)
        { 
            //
            // An expression is the query root if it was the expression used
            // when constructing this converter or, if the root is a LambdaExpression,
            // the Body of the expression used when constructing this converter. 
            //
            return (object.ReferenceEquals(_expression, linqExpression) || 
                    object.ReferenceEquals(_innerExpression, linqExpression)); 
        }
 
        #region Span Mapping maintenance methods

        /// 
        /// Adds a new mapping from DbExpression => Span information for the specified expression, 
        /// after first ensuring that the mapping dictionary has been instantiated.
        ///  
        /// The expression for which Span information should be added 
        /// 
        ///     The Span information, which may be null. 
        ///     If null, no attempt is made to update the dictionary of span mappings.
        /// 
        /// The original  argument, to allow return AddSpanMapping(expression, span) scenarios
        private CqtExpression AddSpanMapping(CqtExpression expression, Span span) 
        {
            if (span != null) 
            { 
                if (null == _spanMappings)
                { 
                    _spanMappings = new Dictionary();
                }

                _spanMappings[expression] = span; 
            }
 
            return expression; 
        }
 
        /// 
        /// Attempts to retrieve Span information for the specified DbExpression.
        /// 
        /// The expression for which Span information should be retrieved. 
        /// Will contain the Span information for the specified expression if it is present in the Span mapping dictionary.
        /// true if Span information was retrieved for the specified expression and  now contains this information; otherwise false. 
        private bool TryGetSpan(CqtExpression expression, out Span span) 
        {
            if (_spanMappings != null) 
            {
                return _spanMappings.TryGetValue(expression, out span);
            }
 
            span = null;
            return false; 
        } 

        ///  
        /// Removes the Span mapping entry for the specified  expression,
        /// and creates a new entry for the specified  expression that maps
        /// to the  expression's original Span information. If no Span
        /// information is present for the specified  expression then no 
        /// changes are made to the Span mapping dictionary.
        ///  
        /// The expression from which to take Span information 
        /// The expression to which the Span information should be applied
        private void ApplySpanMapping(CqtExpression from, CqtExpression to) 
        {
            Span argumentSpan;
            if (TryGetSpan(from, out argumentSpan))
            { 
                AddSpanMapping(to, argumentSpan);
            } 
        } 

        ///  
        /// Unifies the Span information from the specified  and 
        /// expressions, and applies it to the specified  expression. Unification proceeds
        /// as follows:
        /// - If neither  nor  have Span information, no changes are made 
        /// - If one of  or  has Span information, that single Span information
        ///   entry is removed from the Span mapping dictionary and used to create a new entry that maps from the  
        ///   expression to the Span information. 
        /// - If both  and  have Span information, both entries are removed
        ///   from the Span mapping dictionary, a new Span is created that contains the union of the original Spans, and 
        ///   a new entry is added to the dictionary that maps from  expression to this new Span.
        /// 
        /// The first expression argument
        /// The second expression argument 
        /// The result expression
        private void UnifySpanMappings(CqtExpression left, CqtExpression right, CqtExpression to) 
        { 
            Span leftSpan = null;
            Span rightSpan = null; 

            bool hasLeftSpan = TryGetSpan(left, out leftSpan);
            bool hasRightSpan = TryGetSpan(right, out rightSpan);
            if (!hasLeftSpan && !hasRightSpan) 
            {
                return; 
            } 

            Debug.Assert(leftSpan != null || rightSpan != null, "Span mappings contain null?"); 
            AddSpanMapping(to, Span.CopyUnion(leftSpan, rightSpan));
        }
        #endregion
 
        // The following methods correspond to query builder methods on ObjectQuery
        // and MUST be called by expression translators (instead of calling the equivalent 
        // CommandTree.CreateXxExpression methods) to ensure that Span information flows 
        // correctly to the root of the Command Tree as it is constructed by converting
        // the LINQ expression tree. Each method correctly maintains a Span mapping (if required) 
        // for its resulting expression, based on the Span mappings of its argument expression(s).

        private DbDistinctExpression Distinct(CqtExpression argument)
        { 
            DbDistinctExpression retExpr = _commandTree.CreateDistinctExpression(argument);
            ApplySpanMapping(argument, retExpr); 
            return retExpr; 
        }
 
        private DbExceptExpression Except(CqtExpression left, CqtExpression right)
        {
            DbExceptExpression retExpr = _commandTree.CreateExceptExpression(left, right);
            ApplySpanMapping(left, retExpr); 
            return retExpr;
        } 
 
        private DbFilterExpression Filter(DbExpressionBinding input, CqtExpression predicate)
        { 
            DbFilterExpression retExpr = _commandTree.CreateFilterExpression(input, predicate);
            ApplySpanMapping(input.Expression, retExpr);
            return retExpr;
        } 

        private DbIntersectExpression Intersect(CqtExpression left, CqtExpression right) 
        { 
            DbIntersectExpression retExpr = _commandTree.CreateIntersectExpression(left, right);
            UnifySpanMappings(left, right, retExpr); 
            return retExpr;
        }

        private DbLimitExpression Limit(CqtExpression argument, CqtExpression limit) 
        {
            DbLimitExpression retExpr = _commandTree.CreateLimitExpression(argument, limit); 
            ApplySpanMapping(argument, retExpr); 
            return retExpr;
        } 

        private DbOfTypeExpression OfType(CqtExpression argument, TypeUsage ofType)
        {
            DbOfTypeExpression retExpr = _commandTree.CreateOfTypeExpression(argument, ofType); 
            ApplySpanMapping(argument, retExpr);
            return retExpr; 
        } 

        private DbProjectExpression Project(DbExpressionBinding input, CqtExpression projection) 
        {
            DbProjectExpression retExpr = _commandTree.CreateProjectExpression(input, projection);
            // For identity projection only, the Span is preserved
            if (projection.ExpressionKind == DbExpressionKind.VariableReference && 
               ((DbVariableReferenceExpression)projection).VariableName.Equals(input.VariableName, StringComparison.Ordinal))
            { 
                ApplySpanMapping(input.Expression, retExpr); 
            }
            return retExpr; 
        }

        private DbSortExpression Sort(DbExpressionBinding input, IList keys)
        { 
            DbSortExpression retExpr = _commandTree.CreateSortExpression(input, keys);
            ApplySpanMapping(input.Expression, retExpr); 
            return retExpr; 
        }
 
        private DbSkipExpression Skip(DbExpressionBinding input, IList keys, CqtExpression skipCount)
        {
            DbSkipExpression retExpr = _commandTree.CreateSkipExpression(input, keys, skipCount);
            ApplySpanMapping(input.Expression, retExpr); 
            return retExpr;
        } 
 
        private DbUnionAllExpression UnionAll(CqtExpression left, CqtExpression right)
        { 
            DbUnionAllExpression retExpr = _commandTree.CreateUnionAllExpression(left, right);
            UnifySpanMappings(left, right, retExpr);
            return retExpr;
        } 

        ///  
        /// Gets the target type for a CQT cast operation. 
        /// 
        /// Appropriate type usage, or null if this is a "no-op" 
        private TypeUsage GetCastTargetType(TypeUsage fromType, Type toClrType, Type fromClrType, bool preserveCastForDateTime)
        {
            // If the types are the same or the fromType is assignable to toType, return null
            // (indicating no cast is required) 
            TypeUsage toType;
            if (TryGetValueLayerType(toClrType, out toType) && CanOmitCast(fromType, toType, preserveCastForDateTime)) 
            { 
                return null;
            } 

            // Check that the cast is supported and adjust the target type as necessary.
            toType = ValidateAndAdjustCastTypes(toType, fromType, toClrType, fromClrType);
 
            return toType;
        } 
 
        /// 
        /// Check that the given cast specification is supported and if necessary adjust target type (for instance 
        /// add precision and scale for Integral -> Decimal casts)
        /// 
        private static TypeUsage ValidateAndAdjustCastTypes(TypeUsage toType, TypeUsage fromType, Type toClrType, Type fromClrType)
        { 
            // only support primitives if real casting is involved
            if (toType == null || 
                !(TypeSemantics.IsPrimitiveType(toType)) || 
                !(TypeSemantics.IsPrimitiveType(fromType)))
            { 
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedCast(DescribeClrType(fromClrType), DescribeClrType(toClrType)));
            }

            PrimitiveTypeKind fromTypeKind = ((PrimitiveType)fromType.EdmType).PrimitiveTypeKind; 
            PrimitiveTypeKind toTypeKind = ((PrimitiveType)toType.EdmType).PrimitiveTypeKind;
 
            if (toTypeKind == PrimitiveTypeKind.Decimal) 
            {
                // Can't figure out the right precision and scale for decimal, so only accept integer types 
                switch (fromTypeKind)
                {
                    case PrimitiveTypeKind.Byte:
                    case PrimitiveTypeKind.Int16: 
                    case PrimitiveTypeKind.Int32:
                    case PrimitiveTypeKind.Int64: 
                    case PrimitiveTypeKind.SByte: 
                        // adjust precision and scale to ensure sufficient width
                        toType = TypeUsage.CreateDecimalTypeUsage((PrimitiveType)toType.EdmType, 19, 0); 
                        break;
                    default:
                        throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedCastToDecimal);
                } 
            }
 
            return toType; 
        }
 
        /// 
        /// Determines if an instance of fromType can be assigned to an instance of toType using
        /// CLR semantics. in case of primitive type, it must rely on identity since unboxing primitive requires
        /// exact match. for nominal types, rely on subtyping. 
        /// 
        private static bool CanOmitCast(TypeUsage fromType, TypeUsage toType, bool preserveCastForDateTime) 
        { 
            bool isPrimitiveType = TypeSemantics.IsPrimitiveType(fromType);
 
            //SQLBUDT #573573: This is to allow for a workaround on Katmai via explicit casting by the user.
            // The issue is that SqlServer's type Date maps to Edm.DateTime, same as SqlServer's DateTime and SmallDateTime.
            // However the conversion is not possible for all values of Date.
 
            //Note: we could also call here TypeSemantics.IsPrimitiveType(TypeUsage type, PrimitiveTypeKind primitiveTypeKind),
            //  but that checks again whether the type is primitive 
            if (isPrimitiveType && preserveCastForDateTime && ((PrimitiveType)fromType.EdmType).PrimitiveTypeKind == PrimitiveTypeKind.DateTime) 
            {
                return false; 
            }

            if (TypeUsageEquals(fromType, toType))
            { 
                return true;
            } 
 
            if (isPrimitiveType)
            { 
                return fromType.EdmType.EdmEquals(toType.EdmType);
            }

            return TypeSemantics.IsSubTypeOf(fromType, toType); 
        }
 
        ///  
        /// Gets the target type for an Is or As expression.
        ///  
        /// Input type in model metadata.
        /// Test or return type.
        /// Type of operation; used in error reporting.
        /// Input type in CLR metadata. 
        /// Appropriate target type usage.
        private TypeUsage GetIsOrAsTargetType(TypeUsage fromType, ExpressionType operationType, Type toClrType, Type fromClrType) 
        { 
            Debug.Assert(operationType == ExpressionType.TypeAs || operationType == ExpressionType.TypeIs);
 
            // Interpret all type information
            TypeUsage toType;
            if (!this.TryGetValueLayerType(toClrType, out toType) ||
                (!TypeSemantics.IsEntityType(toType) && 
                 !TypeSemantics.IsComplexType(toType)))
            { 
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedIsOrAs(operationType, 
                    DescribeClrType(fromClrType), DescribeClrType(toClrType)));
            } 

            return toType;
        }
 
        // requires: inlineQuery is not null
        // effects: interprets the given query as an inline query in the current expression and unites 
        // the current query context with the context for the inline query. If the given query specifies 
        // span information, then an entry is added to the span mapping dictionary from the CQT expression
        // that is the root of the inline query, to the span information that was present in the inline 
        // query's Span property.
        private CqtExpression TranslateInlineQueryOfT(ObjectQuery inlineQuery)
        {
            if (!object.ReferenceEquals(_context, inlineQuery.QueryState.ObjectContext)) 
            {
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedDifferentContexts); 
            } 

            // if the propagated merge option have not been set, use the MergeOption from this inline query 
            if (!_mergeOption.HasValue &&
               inlineQuery.QueryState.UserSpecifiedMergeOption.HasValue)
            {
                _mergeOption = inlineQuery.QueryState.UserSpecifiedMergeOption.Value; 
            }
 
            LinqExpression queryExpression; 
            if (inlineQuery.QueryState.TryGetExpression(out queryExpression))
            { 
                // This inline query is backed by a LINQ expression, which can be inlined into the translation pass
                // (after suitable normalization). Note that no span merging is required between the Span on the
                // inline ObjectQuery and the Span produced from the translation of its expression because eLINQ
                // ObjectQuery instances cannot have a non-null Span (their Span is modeled as a method call in the 
                // LINQ expression tree).
                queryExpression = NormalizeExpression(queryExpression); 
                return TranslateExpression(queryExpression); 
            }
            else 
            {
                // The ObjectQuery should be Entity-SQL-based at this point
                EntitySqlQueryState esqlState = (EntitySqlQueryState)inlineQuery.QueryState;
 
                // We will produce the translated expression by parsing the Entity-SQL query text.
                DbExpression resultExpression = null; 
 
                // If we are not converting a compiled query, or the referenced Entity-SQL ObjectQuery
                // does not have parameters (and so no parameter references can be in the parsed tree) 
                // then the Entity-SQL can be parsed directly using the conversion command tree.
                ObjectParameterCollection objectParameters = inlineQuery.QueryState.Parameters;
                if (!this.IsCompiledQueryMode ||
                    objectParameters == null || 
                    objectParameters.Count == 0)
                { 
                    // Copy the parameters into the aggregated parameter collection - this will result 
                    // in an exception if any duplicate parameter names are encountered.
                    if (objectParameters != null) 
                    {
                        foreach (ObjectParameter prm in inlineQuery.QueryState.Parameters)
                        {
                            this.AddParameter(prm.ShallowCopy()); 
                        }
                    } 
 
                    resultExpression = esqlState.Parse(_commandTree);
                } 
                else
                {
                    // We are converting a compiled query and parameters are present on the referenced ObjectQuery.
                    // The set of parameters available to a compiled query is fixed (so that adding/removing parameters 
                    // to/from a referenced ObjectQuery does not invalidate the compiled query's execution plan), so the
                    // referenced ObjectQuery will be fully inlined by replacing each parameter reference with a 
                    // DbConstantExpression containing the value of the referenced parameter. 
                    // So that the parameters are never added to the conversion command tree, the referenced ObjectQuery
                    // is parsed using a different query command tree. 
                    DbQueryCommandTree replacedTree = new DbQueryCommandTree(_commandTree.MetadataWorkspace, _commandTree.DataSpace);
                    replacedTree.Query = esqlState.Parse(replacedTree);
                    replacedTree.Replace((ExpressionReplacement replacement) =>
                        { 
                            // Only parameter references are being replaced
                            if (replacement.Current.ExpressionKind != DbExpressionKind.ParameterReference) 
                            { 
                                return;
                            } 
                            DbParameterReferenceExpression paramRef = (DbParameterReferenceExpression)replacement.Current;

                            if (objectParameters.Contains(paramRef.ParameterName))
                            { 
                                // A DbNullExpression is required for null values; DbConstantExpression otherwise.
                                ObjectParameter objParam = objectParameters[paramRef.ParameterName]; 
                                if (null == objParam.Value) 
                                {
                                    replacement.Replacement = replacement.Current.CommandTree.CreateNullExpression(replacement.Current.ResultType); 
                                }
                                else
                                {
                                    // This will throw if the value is incompatible with the result type. 
                                    replacement.Replacement = replacement.Current.CommandTree.CreateConstantExpression(objParam.Value, replacement.Current.ResultType);
                                } 
                            } 
                        }
                    ); 

                    resultExpression = _commandTree.Import(replacedTree.Query);
                }
 
                // The Span produced by the converted DbExpression is any Span that was assigned to the referened Entity-SQL ObjectQuery.
                return AddSpanMapping(resultExpression, inlineQuery.QueryState.Span); 
            } 
        }
 
        // creates a CQT cast expression given the source and target CLR type
        private CqtExpression CreateCastExpression(CqtExpression source, Type toClrType, Type fromClrType)
        {
            // see if the source can be normalized as a set 
            CqtExpression setSource = NormalizeSetSource(source);
            if (!Object.ReferenceEquals(source, setSource)) 
            { 
                // if the resulting cast is a no-op (no either kind is supported
                // for set sources), yield the source 
                if (null == GetCastTargetType(setSource.ResultType, toClrType, fromClrType, true))
                {
                    return source;
                } 
            }
 
            // try to find the appropriate target target for the cast 
            TypeUsage toType = GetCastTargetType(source.ResultType, toClrType, fromClrType, true);
            if (null == toType) 
            {
                // null indicates a no-op cast (from the perspective of the model)
                return source;
            } 

            return _commandTree.CreateCastExpression(source, toType); 
        } 

        // Utility translator method for lambda expressions. Given a lambda expression and its translated 
        // inputs, translates the lambda expression, assuming the input is a collection
        private CqtExpression TranslateLambda(LambdaExpression lambda, CqtExpression input, out DbExpressionBinding binding)
        {
            input = NormalizeSetSource(input); 

            // create binding context for this lambda expression 
            binding = _commandTree.CreateExpressionBinding(input); 

            // figure out the binding variable 
            DbVariableReferenceExpression bindingVariable = binding.Variable;

            _variableNameToInputExpression.Add(bindingVariable.VariableName, input);
 
            return TranslateLambda(lambda, bindingVariable);
        } 
 
        // Utility translator method for lambda expressions that are part of group by. Given a lambda expression and its translated
        // inputs, translates the lambda expression, assuming the input needs to be used as a grouping input 
        private CqtExpression TranslateLambda(LambdaExpression lambda, CqtExpression input, out DbGroupExpressionBinding binding)
        {
            input = NormalizeSetSource(input);
 
            // create binding context for this lambda expression
            binding = _commandTree.CreateGroupExpressionBinding(input); 
 
            // figure out the binding variable
            DbVariableReferenceExpression bindingVariable = binding.Variable; 

            return TranslateLambda(lambda, bindingVariable);
        }
 
        // Utility translator method for lambda expressions. Given a lambda expression and its translated
        // inputs, translates the lambda expression 
        private CqtExpression TranslateLambda(LambdaExpression lambda, CqtExpression input) 
        {
            Binding scopeBinding = new Binding(lambda.Parameters[0], input); 

            // push the binding scope
            _bindingContext.PushBindingScope(scopeBinding);
 
            // translate expression within this binding scope
            CqtExpression result = TranslateExpression(lambda.Body); 
 
            // pop binding scope
            _bindingContext.PopBindingScope(); 

            return result;
        }
 
        // effects: unwraps any "structured" set sources such as IGrouping instances
        // (which acts as both a set and a structure containing a property) 
        private CqtExpression NormalizeSetSource(CqtExpression input) 
        {
            Debug.Assert(null != input); 

            // determine if the lambda input is an IGrouping or EntityCollection that needs to be unwrapped
            InitializerMetadata initializerMetadata;
            if (InitializerMetadata.TryGetInitializerMetadata(input.ResultType, out initializerMetadata)) 
            {
                if (initializerMetadata.Kind == InitializerMetadataKind.Grouping) 
                { 
                    // for group by, redirect the binding to the group (rather than the property)
                    input = _commandTree.CreatePropertyExpression(ExpressionConverter.GroupColumnName, input); 
                }
                else if (initializerMetadata.Kind == InitializerMetadataKind.EntityCollection)
                {
                    // for entity collection, redirect the binding to the children 
                    input = _commandTree.CreatePropertyExpression(ExpressionConverter.EntityCollectionElementsColumnName, input);
                } 
            } 
            return input;
        } 

        // Given a method call expression, returns the given lambda argument (unwrapping quote or closure references where
        // necessary)
        private LambdaExpression GetLambdaExpression(MethodCallExpression callExpression, int argumentOrdinal) 
        {
            LinqExpression argument = callExpression.Arguments[argumentOrdinal]; 
            return (LambdaExpression)GetLambdaExpression(argument); 
        }
 
        private LinqExpression GetLambdaExpression(LinqExpression argument)
        {
            if (ExpressionType.Lambda == argument.NodeType)
            { 
                return argument;
            } 
            else if (ExpressionType.Quote == argument.NodeType) 
            {
                return GetLambdaExpression(((System.Linq.Expressions.UnaryExpression)argument).Operand); 
            }

            // see if this can be computed as a closure binding (resolving to an expression)
            ClosureBinding binding; 
            TypeUsage typeUsage;
            bool allowLambda = true; 
            if (ClosureBinding.TryCreateClosureBinding(argument, _context.Perspective, allowLambda, _closureCandidates, out binding, out typeUsage) && 
                null != binding.Expression)
            { 
                AddClosureBinding(binding);
                return GetLambdaExpression(binding.Expression);
            }
 
            throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.UnexpectedLinqLambdaExpressionFormat);
        } 
 
        // Translate a LINQ expression acting as a set input to a CQT expression
        private CqtExpression TranslateSet(LinqExpression linq) 
        {
            return NormalizeSetSource(TranslateExpression(linq));
        }
 
        // If the given input source is a GroupBy, tries to produce an optimized translation
        // The default translation is to 'manually' do group by, the optimized is translating into a 
        // DbGroupByExpression 
        private bool TryRewrite(CqtExpression source, DbExpressionBinding sourceBinding, CqtExpression lambda, out CqtExpression result)
        { 
            result = null;

            DbGroupByTemplate optimizedTranslationTemplate;
            if (_groupByDefaultToOptimizedTranslationMap.TryGetValue(source, out optimizedTranslationTemplate)) 
            {
                //Create the group by expression 
                DbGroupByExpression optimizedTranslation = _commandTree.CreateGroupByExpression(optimizedTranslationTemplate.Input, optimizedTranslationTemplate.GroupKeys, optimizedTranslationTemplate.Aggregates); 

                DbExpressionBinding optimizedSourceBinding = _commandTree.CreateExpressionBinding(optimizedTranslation); 

                CqtExpression rewrittenLambda;
                if (GroupByExpressionRewriter.TryRewrite(this, lambda, sourceBinding.VariableName, optimizedSourceBinding.Variable, optimizedTranslationTemplate, out rewrittenLambda))
                { 
                    result = Project(optimizedSourceBinding, rewrittenLambda);
                    return true; 
                } 
            }
            return false; 
        }


        // Translate a LINQ expression to a CQT expression. 
        private CqtExpression TranslateExpression(LinqExpression linq)
        { 
            Debug.Assert(null != linq); 

            if (_linqExpressionStack.Contains(linq)) 
            {
                throw EntityUtil.InvalidOperation(Strings.ELinq_CycleDetected);
            }
 
            _linqExpressionStack.Push(linq);
            try 
            { 
                ClosureBinding binding;
                TypeUsage bindingType; 
                bool allowLambda = false;
                CqtExpression result;

                if (_bindingContext.TryGetBoundExpression(linq, out result)) 
                {
                    // see if the LINQ expression has been bound to some CQT expression already 
                    // (e.g. parameter expressions and compiled query parameters) 
                    return result;
                } 
                else if (ClosureBinding.TryCreateClosureBinding(linq, _context.Perspective, allowLambda, _closureCandidates,
                    out binding, out bindingType))
                {
                    // see if the expression is a closure binding 
                    if (!IsCompiledQueryMode)
                    { 
                        AddClosureBinding(binding); 
                    }
 
                    if (null != binding.Parameter)
                    {
                        if (IsCompiledQueryMode)
                        { 
                            // pretend it was a constant expression that we found
                            ConstantExpression constant = Expression.Constant(binding.Parameter.Value, binding.Parameter.ParameterType); 
                            return TranslateExpression(constant); 
                        }
                        else 
                        {
                            // Note that parameters are independently added to the command tree, not just
                            // the query context. This is because a CQT expression tree is invalid if
                            // its parameters are not known, and a valid tree is required (in addition to 
                            // the query context) to construct an ObjectQuery instance.
                            _commandTree.AddParameter(binding.Parameter.Name, bindingType); 
 
                            // return parameter taking the closure value
                            return _commandTree.CreateParameterReferenceExpression(binding.Parameter.Name); 
                        }
                    }
                    else
                    { 
                        Debug.Assert(null != binding.Query, "binding must be either to a query, expression (handled by TranslateLambda), or a parameter");
                        return TranslateInlineQueryOfT(binding.Query); 
                    } 
                }
 
                ObjectQuery queryOfT;
                if (ExpressionEvaluator.TryEvaluateRootQuery(_bindingContext, linq, out queryOfT))
                {
                    return TranslateInlineQueryOfT(queryOfT); 
                }
 
                // translate to a CQT expression 
                Translator translator;
                if (s_translators.TryGetValue(linq.NodeType, out translator)) 
                {
                    return translator.Translate(this, linq);
                }
                else 
                {
                    throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.UnknownLinqNodeType, -1, 
                        linq.NodeType.ToString()); 
                }
            } 
            finally
            {
                _linqExpressionStack.Pop();
            } 
        }
 
        // Cast expression to align types between CQT and eLINQ 
        private CqtExpression AlignTypes(CqtExpression cqt, Type toClrType)
        { 
            Type fromClrType = null; // not used in this code path
            TypeUsage toType = GetCastTargetType(cqt.ResultType, toClrType, fromClrType, false);
            if (null != toType)
            { 
                return _commandTree.CreateCastExpression(cqt, toType);
            } 
            else 
            {
                return cqt; 
            }
        }

        // Determines whether the given type is supported for materialization 
        private void CheckInitializerType(Type type)
        { 
            // nominal types are not supported 
            TypeUsage typeUsage;
            if (_context.Perspective.TryGetType(type, out typeUsage)) 
            {
                BuiltInTypeKind typeKind = typeUsage.EdmType.BuiltInTypeKind;
                if (BuiltInTypeKind.EntityType == typeKind ||
                    BuiltInTypeKind.ComplexType == typeKind) 
                {
                    throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedNominalType( 
                        typeUsage.EdmType.FullName)); 
                }
            } 

            // types implementing IEnumerable are not supported
            if (TypeSystem.IsSequenceType(type))
            { 
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedEnumerableType(
                    DescribeClrType(type))); 
            } 
        }
 

        // requires: Left and right are non-null.
        // effects: Determines if the given types are equivalent, ignoring facets. In
        // the case of primitive types, consider types equivalent if their kinds are 
        // equivalent.
        // comments: This method is useful in cases where the type facets or specific 
        // store primitive type are not reliably known, e.g. when the EDM type is determined 
        // from the CLR type
        private static bool TypeUsageEquals(TypeUsage left, TypeUsage right) 
        {
            Debug.Assert(null != left);
            Debug.Assert(null != right);
            if (left.EdmType.EdmEquals(right.EdmType)) { return true; } 

            // compare element types for collection 
            if (BuiltInTypeKind.CollectionType == left.EdmType.BuiltInTypeKind && 
                BuiltInTypeKind.CollectionType == right.EdmType.BuiltInTypeKind)
            { 
                return TypeUsageEquals(
                    ((CollectionType)left.EdmType).TypeUsage,
                    ((CollectionType)right.EdmType).TypeUsage);
            } 

            // special case for primitive types 
            if (BuiltInTypeKind.PrimitiveType == left.EdmType.BuiltInTypeKind && 
                BuiltInTypeKind.PrimitiveType == right.EdmType.BuiltInTypeKind)
            { 
                // since LINQ expressions cannot indicate model types directly, we must
                // consider types equivalent if they match on the given CLR equivalent
                // types (consider the Xml and String primitive types)
                return ((PrimitiveType)left.EdmType).ClrEquivalentType.Equals( 
                    ((PrimitiveType)right.EdmType).ClrEquivalentType);
            } 
 
            return false;
        } 

        private TypeUsage GetValueLayerType(Type linqType)
        {
            TypeUsage type; 
            if (!TryGetValueLayerType(linqType, out type))
            { 
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedType(linqType)); 
            }
            return type; 
        }

        // Determine C-Space equivalent type for linqType
        private bool TryGetValueLayerType(Type linqType, out TypeUsage type) 
        {
            // Ensure the metadata for this object type is loaded 
            _commandTree.MetadataWorkspace.LoadAssemblyForType(linqType, 
                System.Reflection.Assembly.GetCallingAssembly());
 
            // Remove nullable
            Type nonNullableType = TypeSystem.GetNonNullableType(linqType);

            // See if this is a collection type (if so, recursively resolve) 
            Type elementType = TypeSystem.GetElementType(nonNullableType);
            if (elementType != nonNullableType) 
            { 
                TypeUsage elementTypeUsage;
                if (TryGetValueLayerType(elementType, out elementTypeUsage)) 
                {
                    type = TypeHelpers.CreateCollectionTypeUsage(elementTypeUsage);
                    return true;
                } 
            }
 
            // Retrieve type from map 
            return _context.Perspective.TryGetTypeByName(
                nonNullableType.FullName, 
                false, // ignoreCase
                out type);
        }
 
        /// 
        /// Utility method validating type for comparison ops (isNull, equals, etc.). 
        /// Only primitive types, entity types, and simple row types (no IGrouping/EntityCollection) are 
        /// supported.
        ///  
        private static void VerifyTypeSupportedForComparison(Type clrType, TypeUsage edmType, Stack memberPath)
        {
            // NOTE: due to bug in null handling for complex types, complex types are currently not supported
            // for comparisons (see SQL BU 543956) 
            switch (edmType.EdmType.BuiltInTypeKind)
            { 
                case BuiltInTypeKind.PrimitiveType: 
                case BuiltInTypeKind.EntityType:
                    return; 
                case BuiltInTypeKind.RowType:
                    {
                        InitializerMetadata initializerMetadata;
                        if (!InitializerMetadata.TryGetInitializerMetadata(edmType, out initializerMetadata) || 
                            initializerMetadata.Kind == InitializerMetadataKind.ProjectionInitializer ||
                            initializerMetadata.Kind == InitializerMetadataKind.ProjectionNew) 
                        { 
                            VerifyRowTypeSupportedForComparison(clrType, (RowType)edmType.EdmType, memberPath);
                            return; 
                        }
                        break;
                    }
                default: 
                    break;
            } 
            if (null == memberPath) 
            {
                throw EntityUtil.NotSupported(Strings.ELinq_UnsupportedComparison(DescribeClrType(clrType), Strings.ELinq_PrimitiveTypesSample)); 
            }
            else
            {
                // build up description of member path 
                StringBuilder memberPathDescription = new StringBuilder();
                foreach (EdmMember member in memberPath) 
                { 
                    memberPathDescription.Append(Strings.ELinq_UnsupportedRowMemberComparison(member.Name));
                } 
                memberPathDescription.Append(Strings.ELinq_UnsupportedRowTypeComparison(DescribeClrType(clrType)));
                throw EntityUtil.NotSupported(Strings.ELinq_UnsupportedRowComparison(memberPathDescription.ToString(), Strings.ELinq_PrimitiveTypesSample));
            }
        } 

        private static void VerifyRowTypeSupportedForComparison(Type clrType, RowType rowType, Stack memberPath) 
        { 
            foreach (EdmMember member in rowType.Properties)
            { 
                if (null == memberPath)
                {
                    memberPath = new Stack();
                } 
                memberPath.Push(member);
                VerifyTypeSupportedForComparison(clrType, member.TypeUsage, memberPath); 
                memberPath.Pop(); 
            }
        } 

        /// 
        /// Describe type for exception message.
        ///  
        internal static string DescribeClrType(Type clrType)
        { 
            string clrTypeName = clrType.Name; 
            // Yes, this is a heuristic... just a best effort way of getting
            // a reasonable exception message 
            if (IsCSharpGeneratedClass(clrTypeName, "DisplayClass") ||
                IsVBGeneratedClass(clrTypeName, "Closure"))
            {
                return Strings.ELinq_ClosureType; 
            }
            if (IsCSharpGeneratedClass(clrTypeName, "AnonymousType") || 
                IsVBGeneratedClass(clrTypeName, "AnonymousType")) 
            {
                return Strings.ELinq_AnonymousType; 
            }

            string returnName = string.Empty;
            if (!String.IsNullOrEmpty(clrType.Namespace)) 
            {
                returnName += clrType.Namespace + "."; 
            } 
            returnName += clrType.Name;
            return returnName; 
        }

        private static bool IsCSharpGeneratedClass(string typeName, string pattern)
        { 
            return typeName.Contains("<>") && typeName.Contains("__") && typeName.Contains(pattern);
        } 
 
        private static bool IsVBGeneratedClass(string typeName, string pattern)
        { 
            return typeName.Contains("_") && typeName.Contains("$") && typeName.Contains(pattern);
        }

        ///  
        /// Creates an implementation of IsNull. Throws exception when operand type is not supported.
        ///  
        private CqtExpression CreateIsNullExpression(CqtExpression operand, Type operandClrType) 
        {
            VerifyTypeSupportedForComparison(operandClrType, operand.ResultType, null); 
            return _commandTree.CreateIsNullExpression(operand);
        }

        ///  
        /// Creates an implementation of equals using the given pattern. Throws exception when argument types
        /// are not supported for equals comparison. 
        ///  
        private CqtExpression CreateEqualsExpression(CqtExpression left, CqtExpression right, EqualsPattern pattern, Type leftClrType, Type rightClrType)
        { 
            VerifyTypeSupportedForComparison(leftClrType, left.ResultType, null);
            VerifyTypeSupportedForComparison(rightClrType, right.ResultType, null);
            return RecursivelyRewriteEqualsExpression(left, right, pattern);
        } 
        private CqtExpression RecursivelyRewriteEqualsExpression(CqtExpression left, CqtExpression right, EqualsPattern pattern)
        { 
            // check if either side is an initializer type 
            RowType leftType = left.ResultType.EdmType as RowType;
            RowType rightType = left.ResultType.EdmType as RowType; 

            if (null != leftType || null != rightType)
            {
                if ((null != leftType && null != rightType) && leftType.EdmEquals(rightType)) 
                {
                    CqtExpression shreddedEquals = null; 
                    // if the types are the same, use struct equivalence semantics 
                    foreach (EdmProperty property in leftType.Properties)
                    { 
                        DbPropertyExpression leftElement = _commandTree.CreatePropertyExpression(
                            property, left);
                        DbPropertyExpression rightElement = _commandTree.CreatePropertyExpression(
                            property, right); 
                        CqtExpression elementsEquals = RecursivelyRewriteEqualsExpression(
                            leftElement, rightElement, pattern); 
 
                        // build up and expression
                        if (null == shreddedEquals) { shreddedEquals = elementsEquals; } 
                        else { shreddedEquals = _commandTree.CreateAndExpression(shreddedEquals, elementsEquals); }
                    }
                    return shreddedEquals;
                } 
                else
                { 
                    // if one or both sides is an initializer and the types are not the same, 
                    // "equals" always evaluates to false
                    return _commandTree.CreateFalseExpression(); 
                }
            }
            else
            { 
                return ImplementEquality(left, right, pattern);
            } 
        } 

        // For comparisons, where the left and right side are nullable or not nullable, 
        // here are the (compositionally safe) null equality predicates:
        // -- x NOT NULL, y NULL
        // x = y AND  NOT (y IS NULL)
        // -- x NULL, y NULL 
        // (x = y AND  (NOT (x IS NULL OR y IS NULL))) OR (x IS NULL AND y IS NULL)
        // -- x NOT NULL, y NOT NULL 
        // x = y 
        // -- x NULL, y NOT NULL
        // x = y AND  NOT (x IS NULL) 
        private CqtExpression ImplementEquality(CqtExpression left, CqtExpression right, EqualsPattern pattern)
        {
            switch (left.ExpressionKind)
            { 
                case DbExpressionKind.Constant:
                    switch (right.ExpressionKind) 
                    { 
                        case DbExpressionKind.Constant: // constant EQ constant
                            return _commandTree.CreateEqualsExpression(left, right); 
                        case DbExpressionKind.Null: // null EQ constant --> false
                            return _commandTree.CreateFalseExpression();
                        default:
                            return ImplementEqualityConstantAndUnknown((System.Data.Common.CommandTrees.DbConstantExpression)left, right, pattern); 
                    }
                case DbExpressionKind.Null: 
                    switch (right.ExpressionKind) 
                    {
                        case DbExpressionKind.Constant: // null EQ constant --> false 
                            return _commandTree.CreateFalseExpression();
                        case DbExpressionKind.Null: // null EQ null --> true
                            return _commandTree.CreateTrueExpression();
                        default: // null EQ right --> right IS NULL 
                            return _commandTree.CreateIsNullExpression(right);
                    } 
                default: // unknown 
                    switch (right.ExpressionKind)
                    { 
                        case DbExpressionKind.Constant:
                            return ImplementEqualityConstantAndUnknown((System.Data.Common.CommandTrees.DbConstantExpression)right, left, pattern);
                        case DbExpressionKind.Null: //  left EQ null --> left IS NULL
                            return _commandTree.CreateIsNullExpression(left); 
                        default:
                            return ImplementEqualityUnknownArguments(left, right, pattern); 
                    } 
            }
        } 

        // Generate an equality expression with one unknown operator and
        private CqtExpression ImplementEqualityConstantAndUnknown(
            System.Data.Common.CommandTrees.DbConstantExpression constant, CqtExpression unknown, EqualsPattern pattern) 
        {
            switch (pattern) 
            { 
                case EqualsPattern.Store:
                case EqualsPattern.PositiveNullEquality: 
                    // either both are non-null, or one is null and the predicate result is undefined
                    return _commandTree.CreateEqualsExpression(constant, unknown);
                default:
                    Debug.Fail("unknown pattern"); 
                    return null;
            } 
        } 

        // Generate an equality expression where the values of the left and right operands are completely unknown 
        private CqtExpression ImplementEqualityUnknownArguments(CqtExpression left, CqtExpression right, EqualsPattern pattern)
        {
            switch (pattern)
            { 
                case EqualsPattern.Store: // left EQ right
                    return _commandTree.CreateEqualsExpression(left, right); 
                case EqualsPattern.PositiveNullEquality: // left EQ right OR (left IS NULL AND right IS NULL) 
                    {
                        CqtExpression leftIsNull = _commandTree.CreateIsNullExpression(left); 
                        CqtExpression rightIsNull = _commandTree.CreateIsNullExpression(right);
                        CqtExpression equals = _commandTree.CreateEqualsExpression(left, right);
                        return _commandTree.CreateOrExpression(equals,
                            _commandTree.CreateAndExpression(leftIsNull, rightIsNull)); 
                    }
                default: 
                    Debug.Fail("unexpected pattern"); 
                    return null;
            } 
        }

        #endregion
 
        #region Helper Methods Shared by Translators
 
        ///  
        ///  Translates the arguments into CqtExpressions
        ///   and creates a canonical function with the given functionName and these arguments 
        /// 
        /// Should represent a non-aggregate canonical function
        /// Passed only for error handling purposes
        ///  
        /// 
        private DbFunctionExpression TranslateIntoCanonicalFunction(string functionName, LinqExpression linqExpression, params LinqExpression[] linqArguments) 
        { 
            DbExpression[] translatedArguments = new DbExpression[linqArguments.Length];
            for (int i = 0; i < linqArguments.Length; i++) 
            {
                translatedArguments[i] = TranslateExpression(linqArguments[i]);
            }
            return CreateCanonicalFunction(functionName, linqExpression, translatedArguments); 
        }
 
        ///  
        /// Creates a canonical function with the given name and the given arguments
        ///  
        /// Should represent a non-aggregate canonical function
        /// Passed only for error handling purposes
        /// 
        ///  
        private DbFunctionExpression CreateCanonicalFunction(string functionName, LinqExpression linqExpression, params CqtExpression[] translatedArguments)
        { 
            List translatedArgumentTypes = new List(translatedArguments.Length); 
            foreach (CqtExpression translatedArgument in translatedArguments)
            { 
                translatedArgumentTypes.Add(translatedArgument.ResultType);
            }
            EdmFunction function = FindCanonicalFunction(functionName, translatedArgumentTypes, false /* isGroupAggregateFunction */, linqExpression);
            return _commandTree.CreateFunctionExpression(function, translatedArguments); 
        }
 
        ///  
        /// Finds a canonical function wiht the given functionName and argumentTypes
        ///  
        /// 
        /// 
        /// 
        ///  
        /// 
        private EdmFunction FindCanonicalFunction(string functionName, IList argumentTypes, bool isGroupAggregateFunction, LinqExpression linqExpression) 
        { 
            // find the function
            IList functions; 

            if (!_typeResolver.TryGetFunctionFromMetadata(functionName, EdmNamespaceName, true /*ignoreCase*/, out functions))
            {
                ThrowUnresolvableCanonicalFunction(linqExpression); 
            }
 
            Debug.Assert(null != functions && functions.Count > 0, "provider functions must not be null or empty"); 

            bool isAmbiguous; 
            EdmFunction function = TypeResolver.ResolveFunctionOverloads(functions, argumentTypes, isGroupAggregateFunction, out isAmbiguous);
            if (isAmbiguous || null == function)
            {
                ThrowUnresolvableStoreFunction(linqExpression); 
            }
            return function; 
        } 

        ///  
        /// Helper method for FindCanonicalFunction
        /// 
        /// 
        private static void ThrowUnresolvableCanonicalFunction(LinqExpression linqExpression) 
        {
            if (linqExpression.NodeType == ExpressionType.Call) 
            { 
                MethodInfo methodInfo = ((MethodCallExpression)linqExpression).Method;
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableCanonicalFunctionForMethod(methodInfo, methodInfo.DeclaringType)); 
            }
            else if (linqExpression.NodeType == ExpressionType.MemberAccess)
            {
                string memberName; 
                Type memberType;
                MemberInfo memberInfo = TypeSystem.PropertyOrField(((MemberExpression)linqExpression).Member, out memberName, out memberType); 
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableCanonicalFunctionForMember(memberInfo, memberInfo.DeclaringType)); 
            }
            throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableCanonicalFunctionForExpression(linqExpression.NodeType)); 
        }

        /// 
        /// Helper method for FindCanonicalFunction 
        /// 
        ///  
        private static void ThrowUnresolvableStoreFunction(LinqExpression linqExpression) 
        {
            if (linqExpression.NodeType == ExpressionType.Call) 
            {
                MethodInfo methodInfo = ((MethodCallExpression)linqExpression).Method;
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableStoreFunctionForMethod(methodInfo, methodInfo.DeclaringType));
            } 
            else if (linqExpression.NodeType == ExpressionType.MemberAccess)
            { 
                string memberName; 
                Type memberType;
                MemberInfo memberInfo = TypeSystem.PropertyOrField(((MemberExpression)linqExpression).Member, out memberName, out memberType); 
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableStoreFunctionForMember(memberInfo, memberInfo.DeclaringType));
            }
            throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableStoreFunctionForExpression(linqExpression.NodeType));
        } 

        private DbNewInstanceExpression CreateNewRowExpression(List> columns, InitializerMetadata initializerMetadata) 
        { 
            List propertyValues = new List(columns.Count);
            List properties = new List(columns.Count); 
            for (int i = 0; i < columns.Count; i++)
            {
                var column = columns[i];
                propertyValues.Add(column.Value); 
                properties.Add(new EdmProperty(column.Key, column.Value.ResultType));
            } 
            RowType rowType = new RowType(properties, initializerMetadata); 
            TypeUsage typeUsage = TypeUsage.Create(rowType);
            return _commandTree.CreateNewInstanceExpression(typeUsage, propertyValues); 
        }

        #endregion
 
        #region Helper Structures
 
        // Mirrors the structure of DbGroupByExpression 
        // It is used for incrementally constructing a DbGroupByExpression
        // (the actual DbGroupByExpression cannot be used for this purpose because it is immutable) 
        private class DbGroupByTemplate
        {
            private DbGroupExpressionBinding _input;
            private List> _groupKeys; 
            private List> _aggregates;
 
            public DbGroupByTemplate(DbGroupExpressionBinding input) 
            {
                _input = input; 
                _groupKeys = new List>();
                _aggregates = new List>();
            }
 
            public List> GroupKeys
            { 
                get { return _groupKeys; } 
            }
 
            public List> Aggregates
            {
                get { return _aggregates; }
            } 

            public DbGroupExpressionBinding Input 
            { 
                get { return _input; }
            } 
        }
        #endregion

        #region Private enums 
        // Describes different implementation pattern for equality comparisons.
        // For all patterns, if one side of the expression is a constant null, converts to an IS NULL 
        // expression (or resolves to 'true' or 'false' if some constraint is known for the other side). 
        //
        // If neither side is a constant null, the semantics differ: 
        //
        // Store: left EQ right
        // NullEquality: left EQ right OR (left IS NULL AND right IS NULL)
        // PositiveEquality: left EQ right 
        //
        // In the actual implementation (see ImplementEquality), optimizations exist if one or the other 
        // side is known not to be null. 
        private enum EqualsPattern
        { 
            Store, // defer to store
            PositiveNullEquality, // null == null is 'true', null == (not null) us undefined
        }
        #endregion 
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....]
//--------------------------------------------------------------------- 
 
using CqtExpression = System.Data.Common.CommandTrees.DbExpression;
using LinqExpression = System.Linq.Expressions.Expression; 
using System.Linq.Expressions;
using System.Collections.ObjectModel;
using System.Linq;
using System.Collections.Generic; 
using System.Data.Common.CommandTrees;
using System.Data.Metadata.Edm; 
using System.Reflection; 
using System.Data.Common.EntitySql;
using System.Diagnostics; 
using System.Data.Common;
using System.Globalization;
using System.Data.Common.Utils;
using System.Data.Objects.DataClasses; 
using System.Data.Objects.Internal;
using System.Collections; 
using System.Data.Entity; 
using System.Text;
using System.Data.Common.CommandTrees.Internal; 

namespace System.Data.Objects.ELinq
{
    ///  
    /// Class supporting conversion of LINQ expressions to EDM CQT expressions.
    ///  
    internal sealed partial class ExpressionConverter 
    {
        #region Fields 
        private readonly ObjectContext _context;
        private readonly DbCommandTree _commandTree;
        private readonly TypeResolver _typeResolver;
        private readonly BindingContext _bindingContext; 
        private readonly Dictionary _groupByDefaultToOptimizedTranslationMap;
        private readonly Dictionary _variableNameToInputExpression; 
        private readonly Dictionary> _aggregateDefaultTranslationToOptimizedTranslationInfoMap; 
        private readonly Expression _expression;
        private readonly Expression _innerExpression; 
        private readonly HashSet _closureCandidates = new HashSet();
        private readonly Stack _linqExpressionStack = new Stack();
        private Dictionary _spanMappings;
        private MergeOption? _mergeOption; 
        private List _closureBindings;
        private Dictionary _initializers; 
        private ObjectParameterCollection _parameters; 
        private Span _span;
 
        private const string s_visualBasicAssemblyFullName =
            "Microsoft.VisualBasic, Version=8.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a";
        private static readonly Dictionary s_translators = InitializeTranslators();
 
        internal const string s_entityCollectionCountPropertyName = "Count";
        internal const string s_nullableHasValuePropertyName = "HasValue"; 
        internal const string s_nullableValuePropertyName = "Value"; 

        ///  
        /// Gets the name of the key column appearing in ELinq GroupBy projections
        /// 
        internal const string KeyColumnName = "Key";
 
        /// 
        /// Gets the name of the group column appearing in ELinq CQTs (used in GroupBy expressions) 
        ///  
        internal const string GroupColumnName = "Group";
 
        /// 
        /// Gets the name of the parent column appearing in ELinq EntityCollection projections
        /// 
        internal const string EntityCollectionOwnerColumnName = "Owner"; 

        ///  
        /// Gets the name of the children column appearing in ELinq EntityCollection projections 
        /// 
        internal const string EntityCollectionElementsColumnName = "Elements"; 

        /// 
        /// The Edm namespace name, used for canonical functions
        ///  
        internal const string EdmNamespaceName = "Edm";
 
        #region Canonical Function Names 
        private const string Concat = "Concat";
        private const string IndexOf = "IndexOf"; 
        private const string Length = "Length";
        private const string Right = "Right";
        private const string Substring = "Substring";
        private const string ToUpper = "ToUpper"; 
        private const string ToLower = "ToLower";
        private const string LTrim = "LTrim"; 
        private const string RTrim = "RTrim"; 
        private const string BitwiseAnd = "BitwiseAnd";
        private const string BitwiseOr = "BitwiseOr"; 
        private const string BitwiseNot = "BitwiseNot";
        private const string BitwiseXor = "BitwiseXor";
        private const string CurrentUtcDateTime = "CurrentUtcDateTime";
        private const string CurrentDateTimeOffset = "CurrentDateTimeOffset"; 
        private const string CurrentDateTime = "CurrentDateTime";
        private const string Year = "Year"; 
        private const string Month = "Month"; 
        private const string Day = "Day";
        private const string Hour = "Hour"; 
        private const string Minute = "Minute";
        private const string Second = "Second";
        private const string Millisecond = "Millisecond";
        #endregion 

        #endregion 
 
        #region Constructors and static initializors
        internal ExpressionConverter(ObjectContext objectContext, BindingContext bindingContext, DbCommandTree commandTree, Expression toConvert, ObjectParameterCollection sourceParams) 
        {
            Debug.Assert(objectContext != null, "A binding context is required");
            Debug.Assert(bindingContext != null, "A binding context is required");
            Debug.Assert(commandTree != null, "A command tree is required"); 
            Debug.Assert(toConvert != null, "An expression is required");
 
            _bindingContext = bindingContext; 
            _context = objectContext;
            _commandTree = commandTree; 
            if (sourceParams != null)
            {
                foreach (ObjectParameter sourceParam in sourceParams)
                { 
                    this.AddParameter(sourceParam);
                } 
            } 

            // Normalize the expression 
            _expression = NormalizeExpression(toConvert);

            if (_expression.NodeType == ExpressionType.Lambda)
            { 
                _innerExpression = ((LambdaExpression)_expression).Body;
            } 
            else 
            {
                _innerExpression = _expression; 
            }

            _typeResolver = new TypeResolver(_context.Perspective, StringComparer.Ordinal);
            _groupByDefaultToOptimizedTranslationMap = new Dictionary(); 
            _aggregateDefaultTranslationToOptimizedTranslationInfoMap = new Dictionary>();
            _variableNameToInputExpression = new Dictionary(); 
        } 

        // initialize translator dictionary (which support identification of translators 
        // for LINQ expression node types)
        private static Dictionary InitializeTranslators()
        {
            Dictionary translators = new Dictionary(); 
            foreach (Translator translator in GetTranslators())
            { 
                foreach (ExpressionType nodeType in translator.NodeTypes) 
                {
                    translators.Add(nodeType, translator); 
                }
            }

            return translators; 
        }
 
        private static IEnumerable GetTranslators() 
        {
            yield return new AndAlsoTranslator(); 
            yield return new OrElseTranslator();
            yield return new LessThanTranslator();
            yield return new LessThanOrEqualsTranslator();
            yield return new GreaterThanTranslator(); 
            yield return new GreaterThanOrEqualsTranslator();
            yield return new EqualsTranslator(); 
            yield return new NotEqualsTranslator(); 
            yield return new ConvertTranslator();
            yield return new ConstantTranslator(); 
            yield return new NotTranslator();
            yield return new MemberAccessTranslator();
            yield return new ParameterTranslator();
            yield return new MemberInitTranslator(); 
            yield return new NewTranslator();
            yield return new AddTranslator(); 
            yield return new ConditionalTranslator(); 
            yield return new DivideTranslator();
            yield return new ModuloTranslator(); 
            yield return new SubtractTranslator();
            yield return new MultiplyTranslator();
            yield return new NegateTranslator();
            yield return new UnaryPlusTranslator(); 
            yield return new MethodCallTranslator();
            yield return new CoalesceTranslator(); 
            yield return new AsTranslator(); 
            yield return new IsTranslator();
            yield return new QuoteTranslator(); 
            yield return new AndTranslator();
            yield return new OrTranslator();
            yield return new ExclusiveOrTranslator();
            yield return new NotSupportedTranslator( 
                ExpressionType.LeftShift,
                ExpressionType.RightShift, 
                ExpressionType.ArrayLength, 
                ExpressionType.ArrayIndex,
                ExpressionType.Invoke, 
                ExpressionType.Lambda,
                ExpressionType.ListInit,
                ExpressionType.NewArrayInit,
                ExpressionType.NewArrayBounds, 
                ExpressionType.Power);
        } 
        #endregion 

        #region Properties 
        private EdmItemCollection EdmItemCollection
        {
            get
            { 
                return (EdmItemCollection)_commandTree.MetadataWorkspace.GetItemCollection(DataSpace.CSpace, true);
            } 
        } 

        private bool IsCompiledQueryMode { get { return _bindingContext.ObjectContext != null; } } 

        internal List ClosureBindings { get { return _closureBindings; } }
        internal ObjectParameterCollection Parameters { get { return _parameters; } }
        internal MergeOption? PropagatedMergeOption { get { return _mergeOption; } } 
        internal Span PropagatedSpan { get { return _span; } }
 
        #endregion 

        #region Internal methods 
        // Convert the LINQ expression to a CQT expression and (optional) Span information.
        // Span information will only be present if ObjectQuery instances that specify Spans
        // are referenced from the LINQ expression in a manner consistent with the Span combination
        // rules, otherwise the Span for the CQT expression will be null. 
        internal CqtExpression Convert()
        { 
            CqtExpression result = this.TranslateExpression(_expression); 
            if (!TryGetSpan(result, out _span))
            { 
                _span = null;
            }
            return result;
        } 

        internal static bool CanTranslatePropertyInfo(PropertyInfo propertyInfo) 
        { 
            return MemberAccessTranslator.CanTranslatePropertyInfo(propertyInfo);
        } 
        #endregion

        #region Private Methods
 
        private LinqExpression NormalizeExpression(LinqExpression expression)
        { 
            HashSet clientEvaluationCandidates = new HashSet(); 
            LinqMaximalSubtreeNominator.Nominate(expression, clientEvaluationCandidates, ExpressionEvaluator.IsExpressionNodeClientEvaluatable);
            expression = LinqTreeNodeEvaluator.Evaluate(expression, clientEvaluationCandidates); 

            // find all the nodes in the closure branches, storing them in _closureCandidates
            LinqMaximalSubtreeNominator.Nominate(expression, _closureCandidates,
                         e => ExpressionEvaluator.IsExpressionNodeClientEvaluatable(e) || ExpressionEvaluator.IsExpressionNodeAClosure(e)); 

            // normalize the expression (eliminate/rewrite compiler or CLR specific expressions). 
            LinqExpressionNormalizer normalizer = new LinqExpressionNormalizer(); 
            expression = normalizer.Visit(expression);
 
            return expression;
        }

        ///  
        /// Adds the specified closure binding, optionally adding the associated
        /// ObjectParameter (if any) to the Parameters collection. Parameters 
        /// have already been copied over if this method is called from 
        /// ApplyLinqStateTo, which goes through AddClosureBindingWithoutParameter to get here.
        /// to copy query state from one Linq ObjectQuery to another, and so 
        /// ClosureBinding parameters need not be added here in that case.
        /// 
        /// The ClosureBinding to add to the set of ClosureBindings
        ///  
        /// Specifies whether the ClosureBinding's ObjectParameter (for a ParameterBinding)
        /// should be added to the Parameters collection. 
        ///  
        private void AddClosureBinding(ClosureBinding binding, bool addParam)
        { 
            Debug.Assert(null != binding, "Closure binding cannot be null");
            if (_closureBindings == null)
            {
                _closureBindings = new List(); 
            }
 
            _closureBindings.Add(binding); 
            if (addParam && null != binding.Parameter)
            { 
                AddParameter(binding.Parameter);
            }
        }
 
        /// 
        /// Adds a new closure parameter to the query context. 
        ///  
        /// 
        ///     Binding to add to the context. 
        /// 
        internal void AddClosureBinding(ClosureBinding binding)
        {
            AddClosureBinding(binding, true); 
        }
 
        // Requires: metadata must not be null. 
        //
        // Effects: adds initializer metadata to this query context. 
        //
        // Ensures that the given initializer metadata is valid within the current converter context.
        // We do not allow two incompatible structures representing the same type within a query, e.g.,
        // 
        //      outer.Join(inner, o => new Foo { X = o.ID }, i => new Foo { Y = i.ID }, ...
        // 
        // since this introduces a discrepancy between the CLR (where comparisons between Foo are aware 
        // of both X and Y) and in ELinq (where comparisons are based on the row structure only), resulting
        // in the following join predicates: 
        //
        //      Linq: foo1 == foo2 (which presumably amounts to foo1.X == foo2.X && foo1.Y == foo2.Y
        //      ELinq: foo1.X == foo2.Y
        // 
        // Similar problems occur with set operations such as Union and Concat, where one of the initialization
        // patterns may be ignored. 
        // 
        // This method performs an overly strict check, requiring that all initializers for a given type
        // are structurally equivalent. 
        internal void ValidateInitializerMetadata(InitializerMetadata metadata)
        {
            Debug.Assert(null != metadata);
            InitializerMetadata existingMetadata; 
            if (_initializers != null && _initializers.TryGetValue(metadata.ClrType, out existingMetadata))
            { 
                // Verify the initializers are compatible. 
                if (!metadata.Equals(existingMetadata))
                { 
                    throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedHeterogeneousInitializers(
                        ExpressionConverter.DescribeClrType(metadata.ClrType)));
                }
            } 
            else
            { 
                // Register the metadata so that subsequent initializers for this type can be verified. 
                if (_initializers == null)
                { 
                    _initializers = new Dictionary();
                }
                _initializers.Add(metadata.ClrType, metadata);
            } 
        }
 
        private void AddParameter(ObjectParameter newParam) 
        {
            if (_parameters == null) 
            {
                _parameters = new ObjectParameterCollection(_context.Perspective);
            }
 
            _parameters.Add(newParam);
        } 
 
        private bool IsQueryRoot(Expression linqExpression)
        { 
            //
            // An expression is the query root if it was the expression used
            // when constructing this converter or, if the root is a LambdaExpression,
            // the Body of the expression used when constructing this converter. 
            //
            return (object.ReferenceEquals(_expression, linqExpression) || 
                    object.ReferenceEquals(_innerExpression, linqExpression)); 
        }
 
        #region Span Mapping maintenance methods

        /// 
        /// Adds a new mapping from DbExpression => Span information for the specified expression, 
        /// after first ensuring that the mapping dictionary has been instantiated.
        ///  
        /// The expression for which Span information should be added 
        /// 
        ///     The Span information, which may be null. 
        ///     If null, no attempt is made to update the dictionary of span mappings.
        /// 
        /// The original  argument, to allow return AddSpanMapping(expression, span) scenarios
        private CqtExpression AddSpanMapping(CqtExpression expression, Span span) 
        {
            if (span != null) 
            { 
                if (null == _spanMappings)
                { 
                    _spanMappings = new Dictionary();
                }

                _spanMappings[expression] = span; 
            }
 
            return expression; 
        }
 
        /// 
        /// Attempts to retrieve Span information for the specified DbExpression.
        /// 
        /// The expression for which Span information should be retrieved. 
        /// Will contain the Span information for the specified expression if it is present in the Span mapping dictionary.
        /// true if Span information was retrieved for the specified expression and  now contains this information; otherwise false. 
        private bool TryGetSpan(CqtExpression expression, out Span span) 
        {
            if (_spanMappings != null) 
            {
                return _spanMappings.TryGetValue(expression, out span);
            }
 
            span = null;
            return false; 
        } 

        ///  
        /// Removes the Span mapping entry for the specified  expression,
        /// and creates a new entry for the specified  expression that maps
        /// to the  expression's original Span information. If no Span
        /// information is present for the specified  expression then no 
        /// changes are made to the Span mapping dictionary.
        ///  
        /// The expression from which to take Span information 
        /// The expression to which the Span information should be applied
        private void ApplySpanMapping(CqtExpression from, CqtExpression to) 
        {
            Span argumentSpan;
            if (TryGetSpan(from, out argumentSpan))
            { 
                AddSpanMapping(to, argumentSpan);
            } 
        } 

        ///  
        /// Unifies the Span information from the specified  and 
        /// expressions, and applies it to the specified  expression. Unification proceeds
        /// as follows:
        /// - If neither  nor  have Span information, no changes are made 
        /// - If one of  or  has Span information, that single Span information
        ///   entry is removed from the Span mapping dictionary and used to create a new entry that maps from the  
        ///   expression to the Span information. 
        /// - If both  and  have Span information, both entries are removed
        ///   from the Span mapping dictionary, a new Span is created that contains the union of the original Spans, and 
        ///   a new entry is added to the dictionary that maps from  expression to this new Span.
        /// 
        /// The first expression argument
        /// The second expression argument 
        /// The result expression
        private void UnifySpanMappings(CqtExpression left, CqtExpression right, CqtExpression to) 
        { 
            Span leftSpan = null;
            Span rightSpan = null; 

            bool hasLeftSpan = TryGetSpan(left, out leftSpan);
            bool hasRightSpan = TryGetSpan(right, out rightSpan);
            if (!hasLeftSpan && !hasRightSpan) 
            {
                return; 
            } 

            Debug.Assert(leftSpan != null || rightSpan != null, "Span mappings contain null?"); 
            AddSpanMapping(to, Span.CopyUnion(leftSpan, rightSpan));
        }
        #endregion
 
        // The following methods correspond to query builder methods on ObjectQuery
        // and MUST be called by expression translators (instead of calling the equivalent 
        // CommandTree.CreateXxExpression methods) to ensure that Span information flows 
        // correctly to the root of the Command Tree as it is constructed by converting
        // the LINQ expression tree. Each method correctly maintains a Span mapping (if required) 
        // for its resulting expression, based on the Span mappings of its argument expression(s).

        private DbDistinctExpression Distinct(CqtExpression argument)
        { 
            DbDistinctExpression retExpr = _commandTree.CreateDistinctExpression(argument);
            ApplySpanMapping(argument, retExpr); 
            return retExpr; 
        }
 
        private DbExceptExpression Except(CqtExpression left, CqtExpression right)
        {
            DbExceptExpression retExpr = _commandTree.CreateExceptExpression(left, right);
            ApplySpanMapping(left, retExpr); 
            return retExpr;
        } 
 
        private DbFilterExpression Filter(DbExpressionBinding input, CqtExpression predicate)
        { 
            DbFilterExpression retExpr = _commandTree.CreateFilterExpression(input, predicate);
            ApplySpanMapping(input.Expression, retExpr);
            return retExpr;
        } 

        private DbIntersectExpression Intersect(CqtExpression left, CqtExpression right) 
        { 
            DbIntersectExpression retExpr = _commandTree.CreateIntersectExpression(left, right);
            UnifySpanMappings(left, right, retExpr); 
            return retExpr;
        }

        private DbLimitExpression Limit(CqtExpression argument, CqtExpression limit) 
        {
            DbLimitExpression retExpr = _commandTree.CreateLimitExpression(argument, limit); 
            ApplySpanMapping(argument, retExpr); 
            return retExpr;
        } 

        private DbOfTypeExpression OfType(CqtExpression argument, TypeUsage ofType)
        {
            DbOfTypeExpression retExpr = _commandTree.CreateOfTypeExpression(argument, ofType); 
            ApplySpanMapping(argument, retExpr);
            return retExpr; 
        } 

        private DbProjectExpression Project(DbExpressionBinding input, CqtExpression projection) 
        {
            DbProjectExpression retExpr = _commandTree.CreateProjectExpression(input, projection);
            // For identity projection only, the Span is preserved
            if (projection.ExpressionKind == DbExpressionKind.VariableReference && 
               ((DbVariableReferenceExpression)projection).VariableName.Equals(input.VariableName, StringComparison.Ordinal))
            { 
                ApplySpanMapping(input.Expression, retExpr); 
            }
            return retExpr; 
        }

        private DbSortExpression Sort(DbExpressionBinding input, IList keys)
        { 
            DbSortExpression retExpr = _commandTree.CreateSortExpression(input, keys);
            ApplySpanMapping(input.Expression, retExpr); 
            return retExpr; 
        }
 
        private DbSkipExpression Skip(DbExpressionBinding input, IList keys, CqtExpression skipCount)
        {
            DbSkipExpression retExpr = _commandTree.CreateSkipExpression(input, keys, skipCount);
            ApplySpanMapping(input.Expression, retExpr); 
            return retExpr;
        } 
 
        private DbUnionAllExpression UnionAll(CqtExpression left, CqtExpression right)
        { 
            DbUnionAllExpression retExpr = _commandTree.CreateUnionAllExpression(left, right);
            UnifySpanMappings(left, right, retExpr);
            return retExpr;
        } 

        ///  
        /// Gets the target type for a CQT cast operation. 
        /// 
        /// Appropriate type usage, or null if this is a "no-op" 
        private TypeUsage GetCastTargetType(TypeUsage fromType, Type toClrType, Type fromClrType, bool preserveCastForDateTime)
        {
            // If the types are the same or the fromType is assignable to toType, return null
            // (indicating no cast is required) 
            TypeUsage toType;
            if (TryGetValueLayerType(toClrType, out toType) && CanOmitCast(fromType, toType, preserveCastForDateTime)) 
            { 
                return null;
            } 

            // Check that the cast is supported and adjust the target type as necessary.
            toType = ValidateAndAdjustCastTypes(toType, fromType, toClrType, fromClrType);
 
            return toType;
        } 
 
        /// 
        /// Check that the given cast specification is supported and if necessary adjust target type (for instance 
        /// add precision and scale for Integral -> Decimal casts)
        /// 
        private static TypeUsage ValidateAndAdjustCastTypes(TypeUsage toType, TypeUsage fromType, Type toClrType, Type fromClrType)
        { 
            // only support primitives if real casting is involved
            if (toType == null || 
                !(TypeSemantics.IsPrimitiveType(toType)) || 
                !(TypeSemantics.IsPrimitiveType(fromType)))
            { 
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedCast(DescribeClrType(fromClrType), DescribeClrType(toClrType)));
            }

            PrimitiveTypeKind fromTypeKind = ((PrimitiveType)fromType.EdmType).PrimitiveTypeKind; 
            PrimitiveTypeKind toTypeKind = ((PrimitiveType)toType.EdmType).PrimitiveTypeKind;
 
            if (toTypeKind == PrimitiveTypeKind.Decimal) 
            {
                // Can't figure out the right precision and scale for decimal, so only accept integer types 
                switch (fromTypeKind)
                {
                    case PrimitiveTypeKind.Byte:
                    case PrimitiveTypeKind.Int16: 
                    case PrimitiveTypeKind.Int32:
                    case PrimitiveTypeKind.Int64: 
                    case PrimitiveTypeKind.SByte: 
                        // adjust precision and scale to ensure sufficient width
                        toType = TypeUsage.CreateDecimalTypeUsage((PrimitiveType)toType.EdmType, 19, 0); 
                        break;
                    default:
                        throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedCastToDecimal);
                } 
            }
 
            return toType; 
        }
 
        /// 
        /// Determines if an instance of fromType can be assigned to an instance of toType using
        /// CLR semantics. in case of primitive type, it must rely on identity since unboxing primitive requires
        /// exact match. for nominal types, rely on subtyping. 
        /// 
        private static bool CanOmitCast(TypeUsage fromType, TypeUsage toType, bool preserveCastForDateTime) 
        { 
            bool isPrimitiveType = TypeSemantics.IsPrimitiveType(fromType);
 
            //SQLBUDT #573573: This is to allow for a workaround on Katmai via explicit casting by the user.
            // The issue is that SqlServer's type Date maps to Edm.DateTime, same as SqlServer's DateTime and SmallDateTime.
            // However the conversion is not possible for all values of Date.
 
            //Note: we could also call here TypeSemantics.IsPrimitiveType(TypeUsage type, PrimitiveTypeKind primitiveTypeKind),
            //  but that checks again whether the type is primitive 
            if (isPrimitiveType && preserveCastForDateTime && ((PrimitiveType)fromType.EdmType).PrimitiveTypeKind == PrimitiveTypeKind.DateTime) 
            {
                return false; 
            }

            if (TypeUsageEquals(fromType, toType))
            { 
                return true;
            } 
 
            if (isPrimitiveType)
            { 
                return fromType.EdmType.EdmEquals(toType.EdmType);
            }

            return TypeSemantics.IsSubTypeOf(fromType, toType); 
        }
 
        ///  
        /// Gets the target type for an Is or As expression.
        ///  
        /// Input type in model metadata.
        /// Test or return type.
        /// Type of operation; used in error reporting.
        /// Input type in CLR metadata. 
        /// Appropriate target type usage.
        private TypeUsage GetIsOrAsTargetType(TypeUsage fromType, ExpressionType operationType, Type toClrType, Type fromClrType) 
        { 
            Debug.Assert(operationType == ExpressionType.TypeAs || operationType == ExpressionType.TypeIs);
 
            // Interpret all type information
            TypeUsage toType;
            if (!this.TryGetValueLayerType(toClrType, out toType) ||
                (!TypeSemantics.IsEntityType(toType) && 
                 !TypeSemantics.IsComplexType(toType)))
            { 
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedIsOrAs(operationType, 
                    DescribeClrType(fromClrType), DescribeClrType(toClrType)));
            } 

            return toType;
        }
 
        // requires: inlineQuery is not null
        // effects: interprets the given query as an inline query in the current expression and unites 
        // the current query context with the context for the inline query. If the given query specifies 
        // span information, then an entry is added to the span mapping dictionary from the CQT expression
        // that is the root of the inline query, to the span information that was present in the inline 
        // query's Span property.
        private CqtExpression TranslateInlineQueryOfT(ObjectQuery inlineQuery)
        {
            if (!object.ReferenceEquals(_context, inlineQuery.QueryState.ObjectContext)) 
            {
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedDifferentContexts); 
            } 

            // if the propagated merge option have not been set, use the MergeOption from this inline query 
            if (!_mergeOption.HasValue &&
               inlineQuery.QueryState.UserSpecifiedMergeOption.HasValue)
            {
                _mergeOption = inlineQuery.QueryState.UserSpecifiedMergeOption.Value; 
            }
 
            LinqExpression queryExpression; 
            if (inlineQuery.QueryState.TryGetExpression(out queryExpression))
            { 
                // This inline query is backed by a LINQ expression, which can be inlined into the translation pass
                // (after suitable normalization). Note that no span merging is required between the Span on the
                // inline ObjectQuery and the Span produced from the translation of its expression because eLINQ
                // ObjectQuery instances cannot have a non-null Span (their Span is modeled as a method call in the 
                // LINQ expression tree).
                queryExpression = NormalizeExpression(queryExpression); 
                return TranslateExpression(queryExpression); 
            }
            else 
            {
                // The ObjectQuery should be Entity-SQL-based at this point
                EntitySqlQueryState esqlState = (EntitySqlQueryState)inlineQuery.QueryState;
 
                // We will produce the translated expression by parsing the Entity-SQL query text.
                DbExpression resultExpression = null; 
 
                // If we are not converting a compiled query, or the referenced Entity-SQL ObjectQuery
                // does not have parameters (and so no parameter references can be in the parsed tree) 
                // then the Entity-SQL can be parsed directly using the conversion command tree.
                ObjectParameterCollection objectParameters = inlineQuery.QueryState.Parameters;
                if (!this.IsCompiledQueryMode ||
                    objectParameters == null || 
                    objectParameters.Count == 0)
                { 
                    // Copy the parameters into the aggregated parameter collection - this will result 
                    // in an exception if any duplicate parameter names are encountered.
                    if (objectParameters != null) 
                    {
                        foreach (ObjectParameter prm in inlineQuery.QueryState.Parameters)
                        {
                            this.AddParameter(prm.ShallowCopy()); 
                        }
                    } 
 
                    resultExpression = esqlState.Parse(_commandTree);
                } 
                else
                {
                    // We are converting a compiled query and parameters are present on the referenced ObjectQuery.
                    // The set of parameters available to a compiled query is fixed (so that adding/removing parameters 
                    // to/from a referenced ObjectQuery does not invalidate the compiled query's execution plan), so the
                    // referenced ObjectQuery will be fully inlined by replacing each parameter reference with a 
                    // DbConstantExpression containing the value of the referenced parameter. 
                    // So that the parameters are never added to the conversion command tree, the referenced ObjectQuery
                    // is parsed using a different query command tree. 
                    DbQueryCommandTree replacedTree = new DbQueryCommandTree(_commandTree.MetadataWorkspace, _commandTree.DataSpace);
                    replacedTree.Query = esqlState.Parse(replacedTree);
                    replacedTree.Replace((ExpressionReplacement replacement) =>
                        { 
                            // Only parameter references are being replaced
                            if (replacement.Current.ExpressionKind != DbExpressionKind.ParameterReference) 
                            { 
                                return;
                            } 
                            DbParameterReferenceExpression paramRef = (DbParameterReferenceExpression)replacement.Current;

                            if (objectParameters.Contains(paramRef.ParameterName))
                            { 
                                // A DbNullExpression is required for null values; DbConstantExpression otherwise.
                                ObjectParameter objParam = objectParameters[paramRef.ParameterName]; 
                                if (null == objParam.Value) 
                                {
                                    replacement.Replacement = replacement.Current.CommandTree.CreateNullExpression(replacement.Current.ResultType); 
                                }
                                else
                                {
                                    // This will throw if the value is incompatible with the result type. 
                                    replacement.Replacement = replacement.Current.CommandTree.CreateConstantExpression(objParam.Value, replacement.Current.ResultType);
                                } 
                            } 
                        }
                    ); 

                    resultExpression = _commandTree.Import(replacedTree.Query);
                }
 
                // The Span produced by the converted DbExpression is any Span that was assigned to the referened Entity-SQL ObjectQuery.
                return AddSpanMapping(resultExpression, inlineQuery.QueryState.Span); 
            } 
        }
 
        // creates a CQT cast expression given the source and target CLR type
        private CqtExpression CreateCastExpression(CqtExpression source, Type toClrType, Type fromClrType)
        {
            // see if the source can be normalized as a set 
            CqtExpression setSource = NormalizeSetSource(source);
            if (!Object.ReferenceEquals(source, setSource)) 
            { 
                // if the resulting cast is a no-op (no either kind is supported
                // for set sources), yield the source 
                if (null == GetCastTargetType(setSource.ResultType, toClrType, fromClrType, true))
                {
                    return source;
                } 
            }
 
            // try to find the appropriate target target for the cast 
            TypeUsage toType = GetCastTargetType(source.ResultType, toClrType, fromClrType, true);
            if (null == toType) 
            {
                // null indicates a no-op cast (from the perspective of the model)
                return source;
            } 

            return _commandTree.CreateCastExpression(source, toType); 
        } 

        // Utility translator method for lambda expressions. Given a lambda expression and its translated 
        // inputs, translates the lambda expression, assuming the input is a collection
        private CqtExpression TranslateLambda(LambdaExpression lambda, CqtExpression input, out DbExpressionBinding binding)
        {
            input = NormalizeSetSource(input); 

            // create binding context for this lambda expression 
            binding = _commandTree.CreateExpressionBinding(input); 

            // figure out the binding variable 
            DbVariableReferenceExpression bindingVariable = binding.Variable;

            _variableNameToInputExpression.Add(bindingVariable.VariableName, input);
 
            return TranslateLambda(lambda, bindingVariable);
        } 
 
        // Utility translator method for lambda expressions that are part of group by. Given a lambda expression and its translated
        // inputs, translates the lambda expression, assuming the input needs to be used as a grouping input 
        private CqtExpression TranslateLambda(LambdaExpression lambda, CqtExpression input, out DbGroupExpressionBinding binding)
        {
            input = NormalizeSetSource(input);
 
            // create binding context for this lambda expression
            binding = _commandTree.CreateGroupExpressionBinding(input); 
 
            // figure out the binding variable
            DbVariableReferenceExpression bindingVariable = binding.Variable; 

            return TranslateLambda(lambda, bindingVariable);
        }
 
        // Utility translator method for lambda expressions. Given a lambda expression and its translated
        // inputs, translates the lambda expression 
        private CqtExpression TranslateLambda(LambdaExpression lambda, CqtExpression input) 
        {
            Binding scopeBinding = new Binding(lambda.Parameters[0], input); 

            // push the binding scope
            _bindingContext.PushBindingScope(scopeBinding);
 
            // translate expression within this binding scope
            CqtExpression result = TranslateExpression(lambda.Body); 
 
            // pop binding scope
            _bindingContext.PopBindingScope(); 

            return result;
        }
 
        // effects: unwraps any "structured" set sources such as IGrouping instances
        // (which acts as both a set and a structure containing a property) 
        private CqtExpression NormalizeSetSource(CqtExpression input) 
        {
            Debug.Assert(null != input); 

            // determine if the lambda input is an IGrouping or EntityCollection that needs to be unwrapped
            InitializerMetadata initializerMetadata;
            if (InitializerMetadata.TryGetInitializerMetadata(input.ResultType, out initializerMetadata)) 
            {
                if (initializerMetadata.Kind == InitializerMetadataKind.Grouping) 
                { 
                    // for group by, redirect the binding to the group (rather than the property)
                    input = _commandTree.CreatePropertyExpression(ExpressionConverter.GroupColumnName, input); 
                }
                else if (initializerMetadata.Kind == InitializerMetadataKind.EntityCollection)
                {
                    // for entity collection, redirect the binding to the children 
                    input = _commandTree.CreatePropertyExpression(ExpressionConverter.EntityCollectionElementsColumnName, input);
                } 
            } 
            return input;
        } 

        // Given a method call expression, returns the given lambda argument (unwrapping quote or closure references where
        // necessary)
        private LambdaExpression GetLambdaExpression(MethodCallExpression callExpression, int argumentOrdinal) 
        {
            LinqExpression argument = callExpression.Arguments[argumentOrdinal]; 
            return (LambdaExpression)GetLambdaExpression(argument); 
        }
 
        private LinqExpression GetLambdaExpression(LinqExpression argument)
        {
            if (ExpressionType.Lambda == argument.NodeType)
            { 
                return argument;
            } 
            else if (ExpressionType.Quote == argument.NodeType) 
            {
                return GetLambdaExpression(((System.Linq.Expressions.UnaryExpression)argument).Operand); 
            }

            // see if this can be computed as a closure binding (resolving to an expression)
            ClosureBinding binding; 
            TypeUsage typeUsage;
            bool allowLambda = true; 
            if (ClosureBinding.TryCreateClosureBinding(argument, _context.Perspective, allowLambda, _closureCandidates, out binding, out typeUsage) && 
                null != binding.Expression)
            { 
                AddClosureBinding(binding);
                return GetLambdaExpression(binding.Expression);
            }
 
            throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.UnexpectedLinqLambdaExpressionFormat);
        } 
 
        // Translate a LINQ expression acting as a set input to a CQT expression
        private CqtExpression TranslateSet(LinqExpression linq) 
        {
            return NormalizeSetSource(TranslateExpression(linq));
        }
 
        // If the given input source is a GroupBy, tries to produce an optimized translation
        // The default translation is to 'manually' do group by, the optimized is translating into a 
        // DbGroupByExpression 
        private bool TryRewrite(CqtExpression source, DbExpressionBinding sourceBinding, CqtExpression lambda, out CqtExpression result)
        { 
            result = null;

            DbGroupByTemplate optimizedTranslationTemplate;
            if (_groupByDefaultToOptimizedTranslationMap.TryGetValue(source, out optimizedTranslationTemplate)) 
            {
                //Create the group by expression 
                DbGroupByExpression optimizedTranslation = _commandTree.CreateGroupByExpression(optimizedTranslationTemplate.Input, optimizedTranslationTemplate.GroupKeys, optimizedTranslationTemplate.Aggregates); 

                DbExpressionBinding optimizedSourceBinding = _commandTree.CreateExpressionBinding(optimizedTranslation); 

                CqtExpression rewrittenLambda;
                if (GroupByExpressionRewriter.TryRewrite(this, lambda, sourceBinding.VariableName, optimizedSourceBinding.Variable, optimizedTranslationTemplate, out rewrittenLambda))
                { 
                    result = Project(optimizedSourceBinding, rewrittenLambda);
                    return true; 
                } 
            }
            return false; 
        }


        // Translate a LINQ expression to a CQT expression. 
        private CqtExpression TranslateExpression(LinqExpression linq)
        { 
            Debug.Assert(null != linq); 

            if (_linqExpressionStack.Contains(linq)) 
            {
                throw EntityUtil.InvalidOperation(Strings.ELinq_CycleDetected);
            }
 
            _linqExpressionStack.Push(linq);
            try 
            { 
                ClosureBinding binding;
                TypeUsage bindingType; 
                bool allowLambda = false;
                CqtExpression result;

                if (_bindingContext.TryGetBoundExpression(linq, out result)) 
                {
                    // see if the LINQ expression has been bound to some CQT expression already 
                    // (e.g. parameter expressions and compiled query parameters) 
                    return result;
                } 
                else if (ClosureBinding.TryCreateClosureBinding(linq, _context.Perspective, allowLambda, _closureCandidates,
                    out binding, out bindingType))
                {
                    // see if the expression is a closure binding 
                    if (!IsCompiledQueryMode)
                    { 
                        AddClosureBinding(binding); 
                    }
 
                    if (null != binding.Parameter)
                    {
                        if (IsCompiledQueryMode)
                        { 
                            // pretend it was a constant expression that we found
                            ConstantExpression constant = Expression.Constant(binding.Parameter.Value, binding.Parameter.ParameterType); 
                            return TranslateExpression(constant); 
                        }
                        else 
                        {
                            // Note that parameters are independently added to the command tree, not just
                            // the query context. This is because a CQT expression tree is invalid if
                            // its parameters are not known, and a valid tree is required (in addition to 
                            // the query context) to construct an ObjectQuery instance.
                            _commandTree.AddParameter(binding.Parameter.Name, bindingType); 
 
                            // return parameter taking the closure value
                            return _commandTree.CreateParameterReferenceExpression(binding.Parameter.Name); 
                        }
                    }
                    else
                    { 
                        Debug.Assert(null != binding.Query, "binding must be either to a query, expression (handled by TranslateLambda), or a parameter");
                        return TranslateInlineQueryOfT(binding.Query); 
                    } 
                }
 
                ObjectQuery queryOfT;
                if (ExpressionEvaluator.TryEvaluateRootQuery(_bindingContext, linq, out queryOfT))
                {
                    return TranslateInlineQueryOfT(queryOfT); 
                }
 
                // translate to a CQT expression 
                Translator translator;
                if (s_translators.TryGetValue(linq.NodeType, out translator)) 
                {
                    return translator.Translate(this, linq);
                }
                else 
                {
                    throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.UnknownLinqNodeType, -1, 
                        linq.NodeType.ToString()); 
                }
            } 
            finally
            {
                _linqExpressionStack.Pop();
            } 
        }
 
        // Cast expression to align types between CQT and eLINQ 
        private CqtExpression AlignTypes(CqtExpression cqt, Type toClrType)
        { 
            Type fromClrType = null; // not used in this code path
            TypeUsage toType = GetCastTargetType(cqt.ResultType, toClrType, fromClrType, false);
            if (null != toType)
            { 
                return _commandTree.CreateCastExpression(cqt, toType);
            } 
            else 
            {
                return cqt; 
            }
        }

        // Determines whether the given type is supported for materialization 
        private void CheckInitializerType(Type type)
        { 
            // nominal types are not supported 
            TypeUsage typeUsage;
            if (_context.Perspective.TryGetType(type, out typeUsage)) 
            {
                BuiltInTypeKind typeKind = typeUsage.EdmType.BuiltInTypeKind;
                if (BuiltInTypeKind.EntityType == typeKind ||
                    BuiltInTypeKind.ComplexType == typeKind) 
                {
                    throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedNominalType( 
                        typeUsage.EdmType.FullName)); 
                }
            } 

            // types implementing IEnumerable are not supported
            if (TypeSystem.IsSequenceType(type))
            { 
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedEnumerableType(
                    DescribeClrType(type))); 
            } 
        }
 

        // requires: Left and right are non-null.
        // effects: Determines if the given types are equivalent, ignoring facets. In
        // the case of primitive types, consider types equivalent if their kinds are 
        // equivalent.
        // comments: This method is useful in cases where the type facets or specific 
        // store primitive type are not reliably known, e.g. when the EDM type is determined 
        // from the CLR type
        private static bool TypeUsageEquals(TypeUsage left, TypeUsage right) 
        {
            Debug.Assert(null != left);
            Debug.Assert(null != right);
            if (left.EdmType.EdmEquals(right.EdmType)) { return true; } 

            // compare element types for collection 
            if (BuiltInTypeKind.CollectionType == left.EdmType.BuiltInTypeKind && 
                BuiltInTypeKind.CollectionType == right.EdmType.BuiltInTypeKind)
            { 
                return TypeUsageEquals(
                    ((CollectionType)left.EdmType).TypeUsage,
                    ((CollectionType)right.EdmType).TypeUsage);
            } 

            // special case for primitive types 
            if (BuiltInTypeKind.PrimitiveType == left.EdmType.BuiltInTypeKind && 
                BuiltInTypeKind.PrimitiveType == right.EdmType.BuiltInTypeKind)
            { 
                // since LINQ expressions cannot indicate model types directly, we must
                // consider types equivalent if they match on the given CLR equivalent
                // types (consider the Xml and String primitive types)
                return ((PrimitiveType)left.EdmType).ClrEquivalentType.Equals( 
                    ((PrimitiveType)right.EdmType).ClrEquivalentType);
            } 
 
            return false;
        } 

        private TypeUsage GetValueLayerType(Type linqType)
        {
            TypeUsage type; 
            if (!TryGetValueLayerType(linqType, out type))
            { 
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedType(linqType)); 
            }
            return type; 
        }

        // Determine C-Space equivalent type for linqType
        private bool TryGetValueLayerType(Type linqType, out TypeUsage type) 
        {
            // Ensure the metadata for this object type is loaded 
            _commandTree.MetadataWorkspace.LoadAssemblyForType(linqType, 
                System.Reflection.Assembly.GetCallingAssembly());
 
            // Remove nullable
            Type nonNullableType = TypeSystem.GetNonNullableType(linqType);

            // See if this is a collection type (if so, recursively resolve) 
            Type elementType = TypeSystem.GetElementType(nonNullableType);
            if (elementType != nonNullableType) 
            { 
                TypeUsage elementTypeUsage;
                if (TryGetValueLayerType(elementType, out elementTypeUsage)) 
                {
                    type = TypeHelpers.CreateCollectionTypeUsage(elementTypeUsage);
                    return true;
                } 
            }
 
            // Retrieve type from map 
            return _context.Perspective.TryGetTypeByName(
                nonNullableType.FullName, 
                false, // ignoreCase
                out type);
        }
 
        /// 
        /// Utility method validating type for comparison ops (isNull, equals, etc.). 
        /// Only primitive types, entity types, and simple row types (no IGrouping/EntityCollection) are 
        /// supported.
        ///  
        private static void VerifyTypeSupportedForComparison(Type clrType, TypeUsage edmType, Stack memberPath)
        {
            // NOTE: due to bug in null handling for complex types, complex types are currently not supported
            // for comparisons (see SQL BU 543956) 
            switch (edmType.EdmType.BuiltInTypeKind)
            { 
                case BuiltInTypeKind.PrimitiveType: 
                case BuiltInTypeKind.EntityType:
                    return; 
                case BuiltInTypeKind.RowType:
                    {
                        InitializerMetadata initializerMetadata;
                        if (!InitializerMetadata.TryGetInitializerMetadata(edmType, out initializerMetadata) || 
                            initializerMetadata.Kind == InitializerMetadataKind.ProjectionInitializer ||
                            initializerMetadata.Kind == InitializerMetadataKind.ProjectionNew) 
                        { 
                            VerifyRowTypeSupportedForComparison(clrType, (RowType)edmType.EdmType, memberPath);
                            return; 
                        }
                        break;
                    }
                default: 
                    break;
            } 
            if (null == memberPath) 
            {
                throw EntityUtil.NotSupported(Strings.ELinq_UnsupportedComparison(DescribeClrType(clrType), Strings.ELinq_PrimitiveTypesSample)); 
            }
            else
            {
                // build up description of member path 
                StringBuilder memberPathDescription = new StringBuilder();
                foreach (EdmMember member in memberPath) 
                { 
                    memberPathDescription.Append(Strings.ELinq_UnsupportedRowMemberComparison(member.Name));
                } 
                memberPathDescription.Append(Strings.ELinq_UnsupportedRowTypeComparison(DescribeClrType(clrType)));
                throw EntityUtil.NotSupported(Strings.ELinq_UnsupportedRowComparison(memberPathDescription.ToString(), Strings.ELinq_PrimitiveTypesSample));
            }
        } 

        private static void VerifyRowTypeSupportedForComparison(Type clrType, RowType rowType, Stack memberPath) 
        { 
            foreach (EdmMember member in rowType.Properties)
            { 
                if (null == memberPath)
                {
                    memberPath = new Stack();
                } 
                memberPath.Push(member);
                VerifyTypeSupportedForComparison(clrType, member.TypeUsage, memberPath); 
                memberPath.Pop(); 
            }
        } 

        /// 
        /// Describe type for exception message.
        ///  
        internal static string DescribeClrType(Type clrType)
        { 
            string clrTypeName = clrType.Name; 
            // Yes, this is a heuristic... just a best effort way of getting
            // a reasonable exception message 
            if (IsCSharpGeneratedClass(clrTypeName, "DisplayClass") ||
                IsVBGeneratedClass(clrTypeName, "Closure"))
            {
                return Strings.ELinq_ClosureType; 
            }
            if (IsCSharpGeneratedClass(clrTypeName, "AnonymousType") || 
                IsVBGeneratedClass(clrTypeName, "AnonymousType")) 
            {
                return Strings.ELinq_AnonymousType; 
            }

            string returnName = string.Empty;
            if (!String.IsNullOrEmpty(clrType.Namespace)) 
            {
                returnName += clrType.Namespace + "."; 
            } 
            returnName += clrType.Name;
            return returnName; 
        }

        private static bool IsCSharpGeneratedClass(string typeName, string pattern)
        { 
            return typeName.Contains("<>") && typeName.Contains("__") && typeName.Contains(pattern);
        } 
 
        private static bool IsVBGeneratedClass(string typeName, string pattern)
        { 
            return typeName.Contains("_") && typeName.Contains("$") && typeName.Contains(pattern);
        }

        ///  
        /// Creates an implementation of IsNull. Throws exception when operand type is not supported.
        ///  
        private CqtExpression CreateIsNullExpression(CqtExpression operand, Type operandClrType) 
        {
            VerifyTypeSupportedForComparison(operandClrType, operand.ResultType, null); 
            return _commandTree.CreateIsNullExpression(operand);
        }

        ///  
        /// Creates an implementation of equals using the given pattern. Throws exception when argument types
        /// are not supported for equals comparison. 
        ///  
        private CqtExpression CreateEqualsExpression(CqtExpression left, CqtExpression right, EqualsPattern pattern, Type leftClrType, Type rightClrType)
        { 
            VerifyTypeSupportedForComparison(leftClrType, left.ResultType, null);
            VerifyTypeSupportedForComparison(rightClrType, right.ResultType, null);
            return RecursivelyRewriteEqualsExpression(left, right, pattern);
        } 
        private CqtExpression RecursivelyRewriteEqualsExpression(CqtExpression left, CqtExpression right, EqualsPattern pattern)
        { 
            // check if either side is an initializer type 
            RowType leftType = left.ResultType.EdmType as RowType;
            RowType rightType = left.ResultType.EdmType as RowType; 

            if (null != leftType || null != rightType)
            {
                if ((null != leftType && null != rightType) && leftType.EdmEquals(rightType)) 
                {
                    CqtExpression shreddedEquals = null; 
                    // if the types are the same, use struct equivalence semantics 
                    foreach (EdmProperty property in leftType.Properties)
                    { 
                        DbPropertyExpression leftElement = _commandTree.CreatePropertyExpression(
                            property, left);
                        DbPropertyExpression rightElement = _commandTree.CreatePropertyExpression(
                            property, right); 
                        CqtExpression elementsEquals = RecursivelyRewriteEqualsExpression(
                            leftElement, rightElement, pattern); 
 
                        // build up and expression
                        if (null == shreddedEquals) { shreddedEquals = elementsEquals; } 
                        else { shreddedEquals = _commandTree.CreateAndExpression(shreddedEquals, elementsEquals); }
                    }
                    return shreddedEquals;
                } 
                else
                { 
                    // if one or both sides is an initializer and the types are not the same, 
                    // "equals" always evaluates to false
                    return _commandTree.CreateFalseExpression(); 
                }
            }
            else
            { 
                return ImplementEquality(left, right, pattern);
            } 
        } 

        // For comparisons, where the left and right side are nullable or not nullable, 
        // here are the (compositionally safe) null equality predicates:
        // -- x NOT NULL, y NULL
        // x = y AND  NOT (y IS NULL)
        // -- x NULL, y NULL 
        // (x = y AND  (NOT (x IS NULL OR y IS NULL))) OR (x IS NULL AND y IS NULL)
        // -- x NOT NULL, y NOT NULL 
        // x = y 
        // -- x NULL, y NOT NULL
        // x = y AND  NOT (x IS NULL) 
        private CqtExpression ImplementEquality(CqtExpression left, CqtExpression right, EqualsPattern pattern)
        {
            switch (left.ExpressionKind)
            { 
                case DbExpressionKind.Constant:
                    switch (right.ExpressionKind) 
                    { 
                        case DbExpressionKind.Constant: // constant EQ constant
                            return _commandTree.CreateEqualsExpression(left, right); 
                        case DbExpressionKind.Null: // null EQ constant --> false
                            return _commandTree.CreateFalseExpression();
                        default:
                            return ImplementEqualityConstantAndUnknown((System.Data.Common.CommandTrees.DbConstantExpression)left, right, pattern); 
                    }
                case DbExpressionKind.Null: 
                    switch (right.ExpressionKind) 
                    {
                        case DbExpressionKind.Constant: // null EQ constant --> false 
                            return _commandTree.CreateFalseExpression();
                        case DbExpressionKind.Null: // null EQ null --> true
                            return _commandTree.CreateTrueExpression();
                        default: // null EQ right --> right IS NULL 
                            return _commandTree.CreateIsNullExpression(right);
                    } 
                default: // unknown 
                    switch (right.ExpressionKind)
                    { 
                        case DbExpressionKind.Constant:
                            return ImplementEqualityConstantAndUnknown((System.Data.Common.CommandTrees.DbConstantExpression)right, left, pattern);
                        case DbExpressionKind.Null: //  left EQ null --> left IS NULL
                            return _commandTree.CreateIsNullExpression(left); 
                        default:
                            return ImplementEqualityUnknownArguments(left, right, pattern); 
                    } 
            }
        } 

        // Generate an equality expression with one unknown operator and
        private CqtExpression ImplementEqualityConstantAndUnknown(
            System.Data.Common.CommandTrees.DbConstantExpression constant, CqtExpression unknown, EqualsPattern pattern) 
        {
            switch (pattern) 
            { 
                case EqualsPattern.Store:
                case EqualsPattern.PositiveNullEquality: 
                    // either both are non-null, or one is null and the predicate result is undefined
                    return _commandTree.CreateEqualsExpression(constant, unknown);
                default:
                    Debug.Fail("unknown pattern"); 
                    return null;
            } 
        } 

        // Generate an equality expression where the values of the left and right operands are completely unknown 
        private CqtExpression ImplementEqualityUnknownArguments(CqtExpression left, CqtExpression right, EqualsPattern pattern)
        {
            switch (pattern)
            { 
                case EqualsPattern.Store: // left EQ right
                    return _commandTree.CreateEqualsExpression(left, right); 
                case EqualsPattern.PositiveNullEquality: // left EQ right OR (left IS NULL AND right IS NULL) 
                    {
                        CqtExpression leftIsNull = _commandTree.CreateIsNullExpression(left); 
                        CqtExpression rightIsNull = _commandTree.CreateIsNullExpression(right);
                        CqtExpression equals = _commandTree.CreateEqualsExpression(left, right);
                        return _commandTree.CreateOrExpression(equals,
                            _commandTree.CreateAndExpression(leftIsNull, rightIsNull)); 
                    }
                default: 
                    Debug.Fail("unexpected pattern"); 
                    return null;
            } 
        }

        #endregion
 
        #region Helper Methods Shared by Translators
 
        ///  
        ///  Translates the arguments into CqtExpressions
        ///   and creates a canonical function with the given functionName and these arguments 
        /// 
        /// Should represent a non-aggregate canonical function
        /// Passed only for error handling purposes
        ///  
        /// 
        private DbFunctionExpression TranslateIntoCanonicalFunction(string functionName, LinqExpression linqExpression, params LinqExpression[] linqArguments) 
        { 
            DbExpression[] translatedArguments = new DbExpression[linqArguments.Length];
            for (int i = 0; i < linqArguments.Length; i++) 
            {
                translatedArguments[i] = TranslateExpression(linqArguments[i]);
            }
            return CreateCanonicalFunction(functionName, linqExpression, translatedArguments); 
        }
 
        ///  
        /// Creates a canonical function with the given name and the given arguments
        ///  
        /// Should represent a non-aggregate canonical function
        /// Passed only for error handling purposes
        /// 
        ///  
        private DbFunctionExpression CreateCanonicalFunction(string functionName, LinqExpression linqExpression, params CqtExpression[] translatedArguments)
        { 
            List translatedArgumentTypes = new List(translatedArguments.Length); 
            foreach (CqtExpression translatedArgument in translatedArguments)
            { 
                translatedArgumentTypes.Add(translatedArgument.ResultType);
            }
            EdmFunction function = FindCanonicalFunction(functionName, translatedArgumentTypes, false /* isGroupAggregateFunction */, linqExpression);
            return _commandTree.CreateFunctionExpression(function, translatedArguments); 
        }
 
        ///  
        /// Finds a canonical function wiht the given functionName and argumentTypes
        ///  
        /// 
        /// 
        /// 
        ///  
        /// 
        private EdmFunction FindCanonicalFunction(string functionName, IList argumentTypes, bool isGroupAggregateFunction, LinqExpression linqExpression) 
        { 
            // find the function
            IList functions; 

            if (!_typeResolver.TryGetFunctionFromMetadata(functionName, EdmNamespaceName, true /*ignoreCase*/, out functions))
            {
                ThrowUnresolvableCanonicalFunction(linqExpression); 
            }
 
            Debug.Assert(null != functions && functions.Count > 0, "provider functions must not be null or empty"); 

            bool isAmbiguous; 
            EdmFunction function = TypeResolver.ResolveFunctionOverloads(functions, argumentTypes, isGroupAggregateFunction, out isAmbiguous);
            if (isAmbiguous || null == function)
            {
                ThrowUnresolvableStoreFunction(linqExpression); 
            }
            return function; 
        } 

        ///  
        /// Helper method for FindCanonicalFunction
        /// 
        /// 
        private static void ThrowUnresolvableCanonicalFunction(LinqExpression linqExpression) 
        {
            if (linqExpression.NodeType == ExpressionType.Call) 
            { 
                MethodInfo methodInfo = ((MethodCallExpression)linqExpression).Method;
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableCanonicalFunctionForMethod(methodInfo, methodInfo.DeclaringType)); 
            }
            else if (linqExpression.NodeType == ExpressionType.MemberAccess)
            {
                string memberName; 
                Type memberType;
                MemberInfo memberInfo = TypeSystem.PropertyOrField(((MemberExpression)linqExpression).Member, out memberName, out memberType); 
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableCanonicalFunctionForMember(memberInfo, memberInfo.DeclaringType)); 
            }
            throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableCanonicalFunctionForExpression(linqExpression.NodeType)); 
        }

        /// 
        /// Helper method for FindCanonicalFunction 
        /// 
        ///  
        private static void ThrowUnresolvableStoreFunction(LinqExpression linqExpression) 
        {
            if (linqExpression.NodeType == ExpressionType.Call) 
            {
                MethodInfo methodInfo = ((MethodCallExpression)linqExpression).Method;
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableStoreFunctionForMethod(methodInfo, methodInfo.DeclaringType));
            } 
            else if (linqExpression.NodeType == ExpressionType.MemberAccess)
            { 
                string memberName; 
                Type memberType;
                MemberInfo memberInfo = TypeSystem.PropertyOrField(((MemberExpression)linqExpression).Member, out memberName, out memberType); 
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableStoreFunctionForMember(memberInfo, memberInfo.DeclaringType));
            }
            throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableStoreFunctionForExpression(linqExpression.NodeType));
        } 

        private DbNewInstanceExpression CreateNewRowExpression(List> columns, InitializerMetadata initializerMetadata) 
        { 
            List propertyValues = new List(columns.Count);
            List properties = new List(columns.Count); 
            for (int i = 0; i < columns.Count; i++)
            {
                var column = columns[i];
                propertyValues.Add(column.Value); 
                properties.Add(new EdmProperty(column.Key, column.Value.ResultType));
            } 
            RowType rowType = new RowType(properties, initializerMetadata); 
            TypeUsage typeUsage = TypeUsage.Create(rowType);
            return _commandTree.CreateNewInstanceExpression(typeUsage, propertyValues); 
        }

        #endregion
 
        #region Helper Structures
 
        // Mirrors the structure of DbGroupByExpression 
        // It is used for incrementally constructing a DbGroupByExpression
        // (the actual DbGroupByExpression cannot be used for this purpose because it is immutable) 
        private class DbGroupByTemplate
        {
            private DbGroupExpressionBinding _input;
            private List> _groupKeys; 
            private List> _aggregates;
 
            public DbGroupByTemplate(DbGroupExpressionBinding input) 
            {
                _input = input; 
                _groupKeys = new List>();
                _aggregates = new List>();
            }
 
            public List> GroupKeys
            { 
                get { return _groupKeys; } 
            }
 
            public List> Aggregates
            {
                get { return _aggregates; }
            } 

            public DbGroupExpressionBinding Input 
            { 
                get { return _input; }
            } 
        }
        #endregion

        #region Private enums 
        // Describes different implementation pattern for equality comparisons.
        // For all patterns, if one side of the expression is a constant null, converts to an IS NULL 
        // expression (or resolves to 'true' or 'false' if some constraint is known for the other side). 
        //
        // If neither side is a constant null, the semantics differ: 
        //
        // Store: left EQ right
        // NullEquality: left EQ right OR (left IS NULL AND right IS NULL)
        // PositiveEquality: left EQ right 
        //
        // In the actual implementation (see ImplementEquality), optimizations exist if one or the other 
        // side is known not to be null. 
        private enum EqualsPattern
        { 
            Store, // defer to store
            PositiveNullEquality, // null == null is 'true', null == (not null) us undefined
        }
        #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