mcs/class/referencesource/System.Data.Entity/System/Data/Objects/ELinq/ExpressionConverter.cs

   1 //---------------------------------------------------------------------
   2 // <copyright file="ExpressionConverter.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner  [....]
   7 //---------------------------------------------------------------------
   8
   9 namespace System.Data.Objects.ELinq
  10 {
  11     using System.Collections;
  12     using System.Collections.Generic;
  13     using System.Data.Common;
  14     using System.Data.Common.CommandTrees;
  15     using System.Data.Common.CommandTrees.ExpressionBuilder;
  16     using System.Data.Common.EntitySql;
  17     using System.Data.Common.Utils;
  18     using System.Data.Entity;
  19     using System.Data.Metadata.Edm;
  20     using System.Diagnostics;
  21     using System.Globalization;
  22     using System.Linq;
  23     using System.Linq.Expressions;
  24     using System.Reflection;
  25     using System.Text;
  26
  27     /// <summary>
  28     /// Class supporting conversion of LINQ expressions to EDM CQT expressions.
  29     /// </summary>
  30     internal sealed partial class ExpressionConverter
  31     {
  32         #region Fields
  33         private readonly Funcletizer _funcletizer;
  34         private readonly Perspective _perspective;
  35         private readonly Expression _expression;
  36         private readonly BindingContext _bindingContext;
  37         private Func<bool> _recompileRequired;
  38         private List<KeyValuePair<ObjectParameter, QueryParameterExpression>> _parameters;
  39         private Dictionary<DbExpression, Span> _spanMappings;
  40         private MergeOption? _mergeOption;
  41         private Dictionary<Type, InitializerMetadata> _initializers;
  42         private Span _span;
  43         private HashSet<ObjectQuery> _inlineEntitySqlQueries;
  44         private int _ignoreInclude;
  45         private readonly AliasGenerator _aliasGenerator = new AliasGenerator("LQ", 0);
  46         private readonly OrderByLifter _orderByLifter;
  47
  48         #region Consts
  49         private const string s_visualBasicAssemblyFullName =
  50             "Microsoft.VisualBasic, Version=10.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a";
  51         private static readonly Dictionary<ExpressionType, Translator> s_translators = InitializeTranslators();
  52
  53         internal const string s_entityCollectionCountPropertyName = "Count";
  54         internal const string s_nullableHasValuePropertyName = "HasValue";
  55         internal const string s_nullableValuePropertyName = "Value";
  56
  57         /// <summary>
  58         /// Gets the name of the key column appearing in ELinq GroupBy projections
  59         /// </summary>
  60         internal const string KeyColumnName = "Key";
  61
  62         /// <summary>
  63         /// Gets the name of the group column appearing in ELinq CQTs (used in GroupBy expressions)
  64         /// </summary>
  65         internal const string GroupColumnName = "Group";
  66
  67         /// <summary>
  68         /// Gets the name of the parent column appearing in ELinq EntityCollection projections
  69         /// </summary>
  70         internal const string EntityCollectionOwnerColumnName = "Owner";
  71
  72         /// <summary>
  73         /// Gets the name of the children column appearing in ELinq EntityCollection projections
  74         /// </summary>
  75         internal const string EntityCollectionElementsColumnName = "Elements";
  76
  77         /// <summary>
  78         /// The Edm namespace name, used for canonical functions
  79         /// </summary>
  80         internal const string EdmNamespaceName = "Edm";
  81         #endregion
  82
  83         #region Canonical Function Names
  84         private const string Concat = "Concat";
  85         private const string IndexOf = "IndexOf";
  86         private const string Length = "Length";
  87         private const string Right = "Right";
  88         private const string Substring = "Substring";
  89         private const string ToUpper = "ToUpper";
  90         private const string ToLower = "ToLower";
  91         private const string Trim = "Trim";
  92         private const string LTrim = "LTrim";
  93         private const string RTrim = "RTrim";
  94         private const string Reverse = "Reverse";
  95         private const string BitwiseAnd = "BitwiseAnd";
  96         private const string BitwiseOr = "BitwiseOr";
  97         private const string BitwiseNot = "BitwiseNot";
  98         private const string BitwiseXor = "BitwiseXor";
  99         private const string CurrentUtcDateTime = "CurrentUtcDateTime";
 100         private const string CurrentDateTimeOffset = "CurrentDateTimeOffset";
 101         private const string CurrentDateTime = "CurrentDateTime";
 102         private const string Year = "Year";
 103         private const string Month = "Month";
 104         private const string Day = "Day";
 105         private const string Hour = "Hour";
 106         private const string Minute = "Minute";
 107         private const string Second = "Second";
 108         private const string Millisecond = "Millisecond";
 109         #endregion
 110
 111         #region Additional Entity function names
 112         private const string AsUnicode = "AsUnicode";
 113         private const string AsNonUnicode = "AsNonUnicode";
 114         #endregion
 115         #endregion
 116
 117         #region Constructors and static initializors
 118         internal ExpressionConverter(Funcletizer funcletizer, Expression expression)
 119         {
 120             EntityUtil.CheckArgumentNull(funcletizer, "funcletizer");
 121             EntityUtil.CheckArgumentNull(expression, "expression");
 122
 123             // Funcletize the expression (identify subexpressions that should be evaluated
 124             // locally)
 125             _funcletizer = funcletizer;
 126             expression = funcletizer.Funcletize(expression, out _recompileRequired);
 127
 128             // Normalize the expression (replace obfuscated parts of the tree with simpler nodes)
 129             LinqExpressionNormalizer normalizer = new LinqExpressionNormalizer();
 130             _expression = normalizer.Visit(expression);
 131
 132             _perspective = funcletizer.RootContext.Perspective;
 133             _bindingContext = new BindingContext();
 134             _ignoreInclude = 0;
 135             _orderByLifter = new OrderByLifter(_aliasGenerator);
 136         }
 137
 138         // initialize translator dictionary (which support identification of translators
 139         // for LINQ expression node types)
 140         private static Dictionary<ExpressionType, Translator> InitializeTranslators()
 141         {
 142             Dictionary<ExpressionType, Translator> translators = new Dictionary<ExpressionType, Translator>();
 143             foreach (Translator translator in GetTranslators())
 144             {
 145                 foreach (ExpressionType nodeType in translator.NodeTypes)
 146                 {
 147                     translators.Add(nodeType, translator);
 148                 }
 149             }
 150
 151             return translators;
 152         }
 153
 154         private static IEnumerable<Translator> GetTranslators()
 155         {
 156             yield return new AndAlsoTranslator();
 157             yield return new OrElseTranslator();
 158             yield return new LessThanTranslator();
 159             yield return new LessThanOrEqualsTranslator();
 160             yield return new GreaterThanTranslator();
 161             yield return new GreaterThanOrEqualsTranslator();
 162             yield return new EqualsTranslator();
 163             yield return new NotEqualsTranslator();
 164             yield return new ConvertTranslator();
 165             yield return new ConstantTranslator();
 166             yield return new NotTranslator();
 167             yield return new MemberAccessTranslator();
 168             yield return new ParameterTranslator();
 169             yield return new MemberInitTranslator();
 170             yield return new NewTranslator();
 171             yield return new AddTranslator();
 172             yield return new ConditionalTranslator();
 173             yield return new DivideTranslator();
 174             yield return new ModuloTranslator();
 175             yield return new SubtractTranslator();
 176             yield return new MultiplyTranslator();
 177             yield return new NegateTranslator();
 178             yield return new UnaryPlusTranslator();
 179             yield return new MethodCallTranslator();
 180             yield return new CoalesceTranslator();
 181             yield return new AsTranslator();
 182             yield return new IsTranslator();
 183             yield return new QuoteTranslator();
 184             yield return new AndTranslator();
 185             yield return new OrTranslator();
 186             yield return new ExclusiveOrTranslator();
 187             yield return new ExtensionTranslator();
 188             yield return new NewArrayInitTranslator();
 189             yield return new ListInitTranslator();
 190             yield return new NotSupportedTranslator(
 191                 ExpressionType.LeftShift,
 192                 ExpressionType.RightShift,
 193                 ExpressionType.ArrayLength,
 194                 ExpressionType.ArrayIndex,
 195                 ExpressionType.Invoke,
 196                 ExpressionType.Lambda,
 197                 ExpressionType.NewArrayBounds,
 198                 ExpressionType.Power);
 199         }
 200         #endregion
 201
 202         #region Properties
 203         private EdmItemCollection EdmItemCollection
 204         {
 205             get
 206             {
 207                 return (EdmItemCollection)_funcletizer.RootContext.MetadataWorkspace.GetItemCollection(DataSpace.CSpace, true);
 208             }
 209         }
 210         internal DbProviderManifest ProviderManifest
 211         {
 212             get
 213             {
 214                 return ((StoreItemCollection)_funcletizer.RootContext.MetadataWorkspace.GetItemCollection(DataSpace.SSpace)).StoreProviderManifest;
 215             }
 216         }
 217         internal System.Collections.ObjectModel.ReadOnlyCollection<KeyValuePair<ObjectParameter, QueryParameterExpression>> GetParameters()
 218         {
 219             if (null != _parameters) { return _parameters.AsReadOnly(); }
 220             return null;
 221         }
 222         internal MergeOption? PropagatedMergeOption { get { return _mergeOption; } }
 223         internal Span PropagatedSpan { get { return _span; } }
 224         internal Func<bool> RecompileRequired { get { return _recompileRequired; } }
 225         internal int IgnoreInclude { get { return _ignoreInclude; } set { _ignoreInclude = value; } }
 226         internal AliasGenerator AliasGenerator { get { return _aliasGenerator; } }
 227         #endregion
 228
 229         #region Internal methods
 230         // Convert the LINQ expression to a CQT expression and (optional) Span information.
 231         // Span information will only be present if ObjectQuery instances that specify Spans
 232         // are referenced from the LINQ expression in a manner consistent with the Span combination
 233         // rules, otherwise the Span for the CQT expression will be null.
 234         internal DbExpression Convert()
 235         {
 236             DbExpression result = this.TranslateExpression(_expression);
 237             if (!TryGetSpan(result, out _span))
 238             {
 239                 _span = null;
 240             }
 241             return result;
 242         }
 243
 244         internal static bool CanFuncletizePropertyInfo(PropertyInfo propertyInfo)
 245         {
 246             return MemberAccessTranslator.CanFuncletizePropertyInfo(propertyInfo);
 247         }
 248
 249         internal bool CanIncludeSpanInfo()
 250         {
 251             return (_ignoreInclude == 0);
 252         }
 253         #endregion
 254
 255         #region Private Methods
 256
 257         private void NotifyMergeOption(MergeOption mergeOption)
 258         {
 259             if (!this._mergeOption.HasValue)
 260             {
 261                 this._mergeOption = mergeOption;
 262             }
 263         }
 264
 265         // Requires: metadata must not be null.
 266         //
 267         // Effects: adds initializer metadata to this query context.
 268         //
 269         // Ensures that the given initializer metadata is valid within the current converter context.
 270         // We do not allow two incompatible structures representing the same type within a query, e.g.,
 271         //
 272         //      outer.Join(inner, o => new Foo { X = o.ID }, i => new Foo { Y = i.ID }, ...
 273         //
 274         // since this introduces a discrepancy between the CLR (where comparisons between Foo are aware
 275         // of both X and Y) and in ELinq (where comparisons are based on the row structure only), resulting
 276         // in the following join predicates:
 277         //
 278         //      Linq: foo1 == foo2 (which presumably amounts to foo1.X == foo2.X && foo1.Y == foo2.Y
 279         //      ELinq: foo1.X == foo2.Y
 280         //
 281         // Similar problems occur with set operations such as Union and Concat, where one of the initialization
 282         // patterns may be ignored.
 283         //
 284         // This method performs an overly strict check, requiring that all initializers for a given type
 285         // are structurally equivalent.
 286         [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Usage", "CA2301", Justification = "metadata.ClrType is not expected to be an Embedded Interop Type.")]
 287         internal void ValidateInitializerMetadata(InitializerMetadata metadata)
 288         {
 289             Debug.Assert(null != metadata);
 290             InitializerMetadata existingMetadata;
 291             if (_initializers != null && _initializers.TryGetValue(metadata.ClrType, out existingMetadata))
 292             {
 293                 // Verify the initializers are compatible.
 294                 if (!metadata.Equals(existingMetadata))
 295                 {
 296                     throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedHeterogeneousInitializers(
 297                         ExpressionConverter.DescribeClrType(metadata.ClrType)));
 298                 }
 299             }
 300             else
 301             {
 302                 // Register the metadata so that subsequent initializers for this type can be verified.
 303                 if (_initializers == null)
 304                 {
 305                     _initializers = new Dictionary<Type, InitializerMetadata>();
 306                 }
 307                 _initializers.Add(metadata.ClrType, metadata);
 308             }
 309         }
 310
 311         private void AddParameter(QueryParameterExpression queryParameter)
 312         {
 313             if (null == _parameters)
 314             {
 315                 _parameters = new List<KeyValuePair<ObjectParameter, QueryParameterExpression>>();
 316             }
 317             if (!_parameters.Select(p => p.Value).Contains(queryParameter))
 318             {
 319                 ObjectParameter parameter = new ObjectParameter(queryParameter.ParameterReference.ParameterName, queryParameter.Type);
 320                 _parameters.Add(new KeyValuePair<ObjectParameter, QueryParameterExpression>(parameter, queryParameter));
 321             }
 322         }
 323
 324         private bool IsQueryRoot(Expression Expression)
 325         {
 326             //
 327             // An expression is the query root if it was the expression used
 328             // when constructing this converter.
 329             //
 330             return object.ReferenceEquals(_expression, Expression);
 331         }
 332
 333         #region Span Mapping maintenance methods
 334
 335         /// <summary>
 336         /// Adds a new mapping from DbExpression => Span information for the specified expression,
 337         /// after first ensuring that the mapping dictionary has been instantiated.
 338         /// </summary>
 339         /// <param name="expression">The expression for which Span information should be added</param>
 340         /// <param name="span">
 341         ///     The Span information, which may be <c>null</c>.
 342         ///     If <c>null</c>, no attempt is made to update the dictionary of span mappings.
 343         /// </param>
 344         /// <returns>The original <paramref name="expression"/> argument, to allow <c>return AddSpanMapping(expression, span)</c> scenarios</returns>
 345         private DbExpression AddSpanMapping(DbExpression expression, Span span)
 346         {
 347             if (span != null && this.CanIncludeSpanInfo())
 348             {
 349                 if (null == _spanMappings)
 350                 {
 351                     _spanMappings = new Dictionary<DbExpression, Span>();
 352                 }
 353                 Span storedSpan = null;
 354                 if (_spanMappings.TryGetValue(expression, out storedSpan))
 355                 {
 356                     foreach (Span.SpanPath sp in span.SpanList)
 357                     {
 358                         storedSpan.AddSpanPath(sp);
 359                     }
 360                     _spanMappings[expression] = storedSpan;
 361                 }
 362                 else
 363                 {
 364                     _spanMappings[expression] = span;
 365                 }
 366             }
 367
 368             return expression;
 369         }
 370
 371         /// <summary>
 372         /// Attempts to retrieve Span information for the specified DbExpression.
 373         /// </summary>
 374         /// <param name="expression">The expression for which Span information should be retrieved.</param>
 375         /// <param name="span">Will contain the Span information for the specified expression if it is present in the Span mapping dictionary.</param>
 376         /// <returns><c>true</c> if Span information was retrieved for the specified expression and <paramref name="span"/> now contains this information; otherwise <c>false</c>.</returns>
 377         private bool TryGetSpan(DbExpression expression, out Span span)
 378         {
 379             if (_spanMappings != null)
 380             {
 381                 return _spanMappings.TryGetValue(expression, out span);
 382             }
 383
 384             span = null;
 385             return false;
 386         }
 387
 388         /// <summary>
 389         /// Removes the Span mapping entry for the specified <paramref name="from"/> expression,
 390         /// and creates a new entry for the specified <paramref name="to"/> expression that maps
 391         /// to the <paramref name="from"/> expression's original Span information. If no Span
 392         /// information is present for the specified <paramref name="from"/> expression then no
 393         /// changes are made to the Span mapping dictionary.
 394         /// </summary>
 395         /// <param name="from">The expression from which to take Span information</param>
 396         /// <param name="to">The expression to which the Span information should be applied</param>
 397         private void ApplySpanMapping(DbExpression from, DbExpression to)
 398         {
 399             Span argumentSpan;
 400             if (TryGetSpan(from, out argumentSpan))
 401             {
 402                 AddSpanMapping(to, argumentSpan);
 403             }
 404         }
 405
 406         /// <summary>
 407         /// Unifies the Span information from the specified <paramref name="left"/> and <paramref name="right"/>
 408         /// expressions, and applies it to the specified <paramref name="to"/> expression. Unification proceeds
 409         /// as follows:
 410         /// - If neither <paramref name="left"/> nor <paramref name="right"/> have Span information, no changes are made
 411         /// - If one of <paramref name="left"/> or <paramref name="right"/> has Span information, that single Span information
 412         ///   entry is removed from the Span mapping dictionary and used to create a new entry that maps from the <paramref name="to"/>
 413         ///   expression to the Span information.
 414         /// - If both <paramref name="left"/> and <paramref name="right"/> have Span information, both entries are removed
 415         ///   from the Span mapping dictionary, a new Span is created that contains the union of the original Spans, and
 416         ///   a new entry is added to the dictionary that maps from <paramref name="to"/> expression to this new Span.
 417         /// </summary>
 418         /// <param name="left">The first expression argument</param>
 419         /// <param name="right">The second expression argument</param>
 420         /// <param name="to">The result expression</param>
 421         private void UnifySpanMappings(DbExpression left, DbExpression right, DbExpression to)
 422         {
 423             Span leftSpan = null;
 424             Span rightSpan = null;
 425
 426             bool hasLeftSpan = TryGetSpan(left, out leftSpan);
 427             bool hasRightSpan = TryGetSpan(right, out rightSpan);
 428             if (!hasLeftSpan && !hasRightSpan)
 429             {
 430                 return;
 431             }
 432
 433             Debug.Assert(leftSpan != null || rightSpan != null, "Span mappings contain null?");
 434             AddSpanMapping(to, Span.CopyUnion(leftSpan, rightSpan));
 435         }
 436         #endregion
 437
 438         // The following methods correspond to query builder methods on ObjectQuery
 439         // and MUST be called by expression translators (instead of calling the equivalent
 440         // CommandTree.CreateXxExpression methods) to ensure that Span information flows
 441         // correctly to the root of the Command Tree as it is constructed by converting
 442         // the LINQ expression tree. Each method correctly maintains a Span mapping (if required)
 443         // for its resulting expression, based on the Span mappings of its argument expression(s).
 444
 445         private DbDistinctExpression Distinct(DbExpression argument)
 446         {
 447             DbDistinctExpression retExpr = argument.Distinct();
 448             ApplySpanMapping(argument, retExpr);
 449             return retExpr;
 450         }
 451
 452         private DbExceptExpression Except(DbExpression left, DbExpression right)
 453         {
 454             DbExceptExpression retExpr = left.Except(right);
 455             ApplySpanMapping(left, retExpr);
 456             return retExpr;
 457         }
 458
 459         private DbExpression Filter(DbExpressionBinding input, DbExpression predicate)
 460         {
 461             DbExpression retExpr = _orderByLifter.Filter(input, predicate);
 462             ApplySpanMapping(input.Expression, retExpr);
 463             return retExpr;
 464         }
 465
 466         private DbIntersectExpression Intersect(DbExpression left, DbExpression right)
 467         {
 468             DbIntersectExpression retExpr = left.Intersect(right);
 469             UnifySpanMappings(left, right, retExpr);
 470             return retExpr;
 471         }
 472
 473         private DbExpression Limit(DbExpression argument, DbExpression limit)
 474         {
 475             DbExpression retExpr = _orderByLifter.Limit(argument, limit);
 476             ApplySpanMapping(argument, retExpr);
 477             return retExpr;
 478         }
 479
 480         private DbExpression OfType(DbExpression argument, TypeUsage ofType)
 481         {
 482             DbExpression retExpr = _orderByLifter.OfType(argument, ofType);
 483             ApplySpanMapping(argument, retExpr);
 484             return retExpr;
 485         }
 486
 487         private DbExpression Project(DbExpressionBinding input, DbExpression projection)
 488         {
 489             DbExpression retExpr = _orderByLifter.Project(input, projection);
 490             // For identity projection only, the Span is preserved
 491             if (projection.ExpressionKind == DbExpressionKind.VariableReference &&
 492                ((DbVariableReferenceExpression)projection).VariableName.Equals(input.VariableName, StringComparison.Ordinal))
 493             {
 494                 ApplySpanMapping(input.Expression, retExpr);
 495             }
 496             return retExpr;
 497         }
 498
 499         private DbSortExpression Sort(DbExpressionBinding input, IList<DbSortClause> keys)
 500         {
 501             DbSortExpression retExpr = input.Sort(keys);
 502             ApplySpanMapping(input.Expression, retExpr);
 503             return retExpr;
 504         }
 505
 506         private DbExpression Skip(DbExpressionBinding input, DbExpression skipCount)
 507         {
 508             DbExpression retExpr = _orderByLifter.Skip(input, skipCount);
 509             ApplySpanMapping(input.Expression, retExpr);
 510             return retExpr;
 511         }
 512
 513         private DbUnionAllExpression UnionAll(DbExpression left, DbExpression right)
 514         {
 515             DbUnionAllExpression retExpr = left.UnionAll(right);
 516             UnifySpanMappings(left, right, retExpr);
 517             return retExpr;
 518         }
 519
 520         /// <summary>
 521         /// Gets the target type for a CQT cast operation.
 522         /// </summary>
 523         /// <returns>Appropriate type usage, or null if this is a "no-op"</returns>
 524         private TypeUsage GetCastTargetType(TypeUsage fromType, Type toClrType, Type fromClrType, bool preserveCastForDateTime)
 525         {
 526             // An inlined ObjectQuery or an IOrderedQueryable expression being cast to IQueryable for use in a sequence method is a no-op.
 527             if(fromClrType != null &&
 528                 fromClrType.IsGenericType && toClrType.IsGenericType &&
 529                 (fromClrType.GetGenericTypeDefinition() == typeof(ObjectQuery<>) || fromClrType.GetGenericTypeDefinition() == typeof(IOrderedQueryable<>)) &&
 530                 (toClrType.GetGenericTypeDefinition() == typeof(IQueryable<>) || toClrType.GetGenericTypeDefinition() == typeof(IOrderedQueryable<>)) &&
 531                 fromClrType.GetGenericArguments()[0] == toClrType.GetGenericArguments()[0])
 532             {
 533                 return null;
 534             }
 535
 536             // If the types are the same or the fromType is assignable to toType, return null
 537             // (indicating no cast is required)
 538             TypeUsage toType;
 539             if (TryGetValueLayerType(toClrType, out toType) && CanOmitCast(fromType, toType, preserveCastForDateTime))
 540             {
 541                 return null;
 542             }
 543
 544             // Check that the cast is supported and adjust the target type as necessary.
 545             toType = ValidateAndAdjustCastTypes(toType, fromType, toClrType, fromClrType);
 546
 547             return toType;
 548         }
 549
 550         /// <summary>
 551         /// Check that the given cast specification is supported and if necessary adjust target type (for instance
 552         /// add precision and scale for Integral -> Decimal casts)
 553         /// </summary>
 554         private static TypeUsage ValidateAndAdjustCastTypes(TypeUsage toType, TypeUsage fromType, Type toClrType, Type fromClrType)
 555         {
 556             // only support primitives if real casting is involved
 557             if (toType == null || !TypeSemantics.IsScalarType(toType) || !TypeSemantics.IsScalarType(fromType))
 558             {
 559                 throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedCast(DescribeClrType(fromClrType), DescribeClrType(toClrType)));
 560             }
 561
 562             PrimitiveTypeKind fromTypeKind = Helper.AsPrimitive(fromType.EdmType).PrimitiveTypeKind;
 563             PrimitiveTypeKind toTypeKind = Helper.AsPrimitive(toType.EdmType).PrimitiveTypeKind;
 564
 565             if (toTypeKind == PrimitiveTypeKind.Decimal)
 566             {
 567                 // Can't figure out the right precision and scale for decimal, so only accept integer types
 568                 switch (fromTypeKind)
 569                 {
 570                     case PrimitiveTypeKind.Byte:
 571                     case PrimitiveTypeKind.Int16:
 572                     case PrimitiveTypeKind.Int32:
 573                     case PrimitiveTypeKind.Int64:
 574                     case PrimitiveTypeKind.SByte:
 575                         // adjust precision and scale to ensure sufficient width
 576                         toType = TypeUsage.CreateDecimalTypeUsage((PrimitiveType)toType.EdmType, 19, 0);
 577                         break;
 578                     default:
 579                         throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedCastToDecimal);
 580                 }
 581             }
 582
 583             return toType;
 584         }
 585
 586         /// <summary>
 587         /// Determines if an instance of fromType can be assigned to an instance of toType using
 588         /// CLR semantics. in case of primitive type, it must rely on identity since unboxing primitive requires
 589         /// exact match. for nominal types, rely on subtyping.
 590         /// </summary>
 591         private static bool CanOmitCast(TypeUsage fromType, TypeUsage toType, bool preserveCastForDateTime)
 592         {
 593             bool isPrimitiveType = TypeSemantics.IsPrimitiveType(fromType);
 594
 595             //SQLBUDT #573573: This is to allow for a workaround on Katmai via explicit casting by the user.
 596             // The issue is that SqlServer's type Date maps to Edm.DateTime, same as SqlServer's DateTime and SmallDateTime.
 597             // However the conversion is not possible for all values of Date.
 598
 599             //Note: we could also call here TypeSemantics.IsPrimitiveType(TypeUsage type, PrimitiveTypeKind primitiveTypeKind),
 600             //  but that checks again whether the type is primitive
 601             if (isPrimitiveType && preserveCastForDateTime && ((PrimitiveType)fromType.EdmType).PrimitiveTypeKind == PrimitiveTypeKind.DateTime)
 602             {
 603                 return false;
 604             }
 605
 606             if (TypeUsageEquals(fromType, toType))
 607             {
 608                 return true;
 609             }
 610
 611             if (isPrimitiveType)
 612             {
 613                 return fromType.EdmType.EdmEquals(toType.EdmType);
 614             }
 615
 616             return TypeSemantics.IsSubTypeOf(fromType, toType);
 617         }
 618
 619         /// <summary>
 620         /// Gets the target type for an Is or As expression.
 621         /// </summary>
 622         /// <param name="fromType">Input type in model metadata.</param>
 623         /// <param name="toClrType">Test or return type.</param>
 624         /// <param name="operationType">Type of operation; used in error reporting.</param>
 625         /// <param name="fromClrType">Input type in CLR metadata.</param>
 626         /// <returns>Appropriate target type usage.</returns>
 627         private TypeUsage GetIsOrAsTargetType(TypeUsage fromType, ExpressionType operationType, Type toClrType, Type fromClrType)
 628         {
 629             Debug.Assert(operationType == ExpressionType.TypeAs || operationType == ExpressionType.TypeIs);
 630
 631             // Interpret all type information
 632             TypeUsage toType;
 633             if (!this.TryGetValueLayerType(toClrType, out toType) ||
 634                 (!TypeSemantics.IsEntityType(toType) &&
 635                  !TypeSemantics.IsComplexType(toType)))
 636             {
 637                 throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedIsOrAs(operationType,
 638                     DescribeClrType(fromClrType), DescribeClrType(toClrType)));
 639             }
 640
 641             return toType;
 642         }
 643
 644         // requires: inlineQuery is not null and inlineQuery is Entity-SQL query
 645         // effects: interprets the given query as an inline query in the current expression and unites
 646         // the current query context with the context for the inline query. If the given query specifies
 647         // span information, then an entry is added to the span mapping dictionary from the CQT expression
 648         // that is the root of the inline query, to the span information that was present in the inline
 649         // query's Span property.
 650         private DbExpression TranslateInlineQueryOfT(ObjectQuery inlineQuery)
 651         {
 652             if (!object.ReferenceEquals(_funcletizer.RootContext, inlineQuery.QueryState.ObjectContext))
 653             {
 654                 throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedDifferentContexts);
 655             }
 656
 657             // Check if the inline query has been encountered so far. If so, we don't need to
 658             // include its parameters again. We do however need to translate it to a new
 659             // DbExpression instance since the expressions may be tagged with span information
 660             // and we don't want to mistakenly apply the directive to the wrong part of the query.
 661             if (null == _inlineEntitySqlQueries)
 662             {
 663                 _inlineEntitySqlQueries = new HashSet<ObjectQuery>();
 664             }
 665             bool isNewInlineQuery = _inlineEntitySqlQueries.Add(inlineQuery);
 666
 667             // The ObjectQuery should be Entity-SQL-based at this point. All other query types are currently
 668             // inlined.
 669             EntitySqlQueryState esqlState = (EntitySqlQueryState)inlineQuery.QueryState;
 670
 671             // We will produce the translated expression by parsing the Entity-SQL query text.
 672             DbExpression resultExpression = null;
 673
 674             // If we are not converting a compiled query, or the referenced Entity-SQL ObjectQuery
 675             // does not have parameters (and so no parameter references can be in the parsed tree)
 676             // then the Entity-SQL can be parsed directly using the conversion command tree.
 677             ObjectParameterCollection objectParameters = inlineQuery.QueryState.Parameters;
 678             if (!_funcletizer.IsCompiledQuery ||
 679                 objectParameters == null ||
 680                 objectParameters.Count == 0)
 681             {
 682                 // Add parameters if they exist and we haven't yet encountered this inline query.
 683                 if (isNewInlineQuery && objectParameters != null)
 684                 {
 685                     // Copy the parameters into the aggregated parameter collection - this will result
 686                     // in an exception if any duplicate parameter names are encountered.
 687                     if (this._parameters == null)
 688                     {
 689                         this._parameters = new List<KeyValuePair<ObjectParameter, QueryParameterExpression>>();
 690                     }
 691                     foreach (ObjectParameter prm in inlineQuery.QueryState.Parameters)
 692                     {
 693                         this._parameters.Add(new KeyValuePair<ObjectParameter, QueryParameterExpression>(prm.ShallowCopy(), null));
 694                     }
 695                 }
 696
 697                 resultExpression = esqlState.Parse();
 698             }
 699             else
 700             {
 701                 // We are converting a compiled query and parameters are present on the referenced ObjectQuery.
 702                 // The set of parameters available to a compiled query is fixed (so that adding/removing parameters
 703                 // to/from a referenced ObjectQuery does not invalidate the compiled query's execution plan), so the
 704                 // referenced ObjectQuery will be fully inlined by replacing each parameter reference with a
 705                 // DbConstantExpression containing the value of the referenced parameter.
 706                 resultExpression = esqlState.Parse();
 707                 resultExpression = ParameterReferenceRemover.RemoveParameterReferences(resultExpression, objectParameters);
 708             }
 709
 710             return resultExpression;
 711         }
 712
 713         private class ParameterReferenceRemover : DefaultExpressionVisitor
 714         {
 715             internal static DbExpression RemoveParameterReferences(DbExpression expression, ObjectParameterCollection availableParameters)
 716             {
 717                 ParameterReferenceRemover remover = new ParameterReferenceRemover(availableParameters);
 718                 return remover.VisitExpression(expression);
 719             }
 720
 721             private readonly ObjectParameterCollection objectParameters;
 722             private ParameterReferenceRemover(ObjectParameterCollection availableParams)
 723                 : base()
 724             {
 725                 Debug.Assert(availableParams != null, "Parameter collection cannot be null");
 726
 727                 this.objectParameters = availableParams;
 728             }
 729
 730             public override DbExpression Visit(DbParameterReferenceExpression expression)
 731             {
 732                 if (this.objectParameters.Contains(expression.ParameterName))
 733                 {
 734                     // A DbNullExpression is required for null values; DbConstantExpression otherwise.
 735                     ObjectParameter objParam = objectParameters[expression.ParameterName];
 736                     if (null == objParam.Value)
 737                     {
 738                         return DbExpressionBuilder.Null(expression.ResultType);
 739                     }
 740                     else
 741                     {
 742                         // This will throw if the value is incompatible with the result type.
 743                         return DbExpressionBuilder.Constant(expression.ResultType, objParam.Value);
 744                     }
 745                 }
 746                 return expression;
 747             }
 748         }
 749
 750         // creates a CQT cast expression given the source and target CLR type
 751         private DbExpression CreateCastExpression(DbExpression source, Type toClrType, Type fromClrType)
 752         {
 753             // see if the source can be normalized as a set
 754             DbExpression setSource = NormalizeSetSource(source);
 755             if (!Object.ReferenceEquals(source, setSource))
 756             {
 757                 // if the resulting cast is a no-op (no either kind is supported
 758                 // for set sources), yield the source
 759                 if (null == GetCastTargetType(setSource.ResultType, toClrType, fromClrType, true))
 760                 {
 761                     return source;
 762                 }
 763             }
 764
 765             // try to find the appropriate target target for the cast
 766             TypeUsage toType = GetCastTargetType(source.ResultType, toClrType, fromClrType, true);
 767             if (null == toType)
 768             {
 769                 // null indicates a no-op cast (from the perspective of the model)
 770                 return source;
 771             }
 772
 773             return source.CastTo(toType);
 774         }
 775
 776         // Utility translator method for lambda expressions. Given a lambda expression and its translated
 777         // inputs, translates the lambda expression, assuming the input is a collection
 778         private DbExpression TranslateLambda(LambdaExpression lambda, DbExpression input, out DbExpressionBinding binding)
 779         {
 780             input = NormalizeSetSource(input);
 781
 782             // create binding context for this lambda expression
 783             binding = input.BindAs(_aliasGenerator.Next());
 784
 785             return TranslateLambda(lambda, binding.Variable);
 786         }
 787
 788         // Utility translator method for lambda expressions. Given a lambda expression and its translated
 789         // inputs, translates the lambda expression, assuming the input is a collection
 790         private DbExpression TranslateLambda(LambdaExpression lambda, DbExpression input, string bindingName, out DbExpressionBinding binding)
 791         {
 792             input = NormalizeSetSource(input);
 793
 794             // create binding context for this lambda expression
 795             binding = input.BindAs(bindingName);
 796
 797             return TranslateLambda(lambda, binding.Variable);
 798         }
 799
 800         // Utility translator method for lambda expressions that are part of group by. Given a lambda expression and its translated
 801         // inputs, translates the lambda expression, assuming the input needs to be used as a grouping input
 802         private DbExpression TranslateLambda(LambdaExpression lambda, DbExpression input, out DbGroupExpressionBinding binding)
 803         {
 804             input = NormalizeSetSource(input);
 805
 806             // create binding context for this lambda expression
 807             string alias = _aliasGenerator.Next();
 808             binding = input.GroupBindAs(alias, string.Format(CultureInfo.InvariantCulture, "Group{0}", alias));
 809
 810             return TranslateLambda(lambda, binding.Variable);
 811         }
 812
 813         // Utility translator method for lambda expressions. Given a lambda expression and its translated
 814         // inputs, translates the lambda expression
 815         private DbExpression TranslateLambda(LambdaExpression lambda, DbExpression input)
 816         {
 817             Binding scopeBinding = new Binding(lambda.Parameters[0], input);
 818
 819             // push the binding scope
 820             _bindingContext.PushBindingScope(scopeBinding);
 821
 822             // translate expression within this binding scope
 823 #if DEBUG
 824             int preValue = _ignoreInclude;
 825 #endif
 826             _ignoreInclude++;
 827             DbExpression result = TranslateExpression(lambda.Body);
 828             _ignoreInclude--;
 829 #if DEBUG
 830             Debug.Assert(preValue == _ignoreInclude);
 831 #endif
 832
 833             // pop binding scope
 834             _bindingContext.PopBindingScope();
 835
 836             return result;
 837         }
 838
 839         // effects: unwraps any "structured" set sources such as IGrouping instances
 840         // (which acts as both a set and a structure containing a property)
 841         private DbExpression NormalizeSetSource(DbExpression input)
 842         {
 843             Debug.Assert(null != input);
 844
 845             // If input looks like "select x from (...) as x", rewrite it as "(...)".
 846             // If input has span information attached to to it then leave it as is, otherwise
 847             // span info will be lost.
 848             Span span;
 849             if (input.ExpressionKind == DbExpressionKind.Project && !TryGetSpan(input, out span))
 850             {
 851                 var project = (DbProjectExpression)input;
 852                 if (project.Projection == project.Input.Variable)
 853                 {
 854                     input = project.Input.Expression;
 855                 }
 856             }
 857
 858             // determine if the lambda input is an IGrouping or EntityCollection that needs to be unwrapped
 859             InitializerMetadata initializerMetadata;
 860             if (InitializerMetadata.TryGetInitializerMetadata(input.ResultType, out initializerMetadata))
 861             {
 862                 if (initializerMetadata.Kind == InitializerMetadataKind.Grouping)
 863                 {
 864                     // for group by, redirect the binding to the group (rather than the property)
 865                     input = input.Property(ExpressionConverter.GroupColumnName);
 866                 }
 867                 else if (initializerMetadata.Kind == InitializerMetadataKind.EntityCollection)
 868                 {
 869                     // for entity collection, redirect the binding to the children
 870                     input = input.Property(ExpressionConverter.EntityCollectionElementsColumnName);
 871                 }
 872             }
 873             return input;
 874         }
 875
 876         // Given a method call expression, returns the given lambda argument (unwrapping quote or closure references where
 877         // necessary)
 878         private LambdaExpression GetLambdaExpression(MethodCallExpression callExpression, int argumentOrdinal)
 879         {
 880             Expression argument = callExpression.Arguments[argumentOrdinal];
 881             return (LambdaExpression)GetLambdaExpression(argument);
 882         }
 883
 884         private Expression GetLambdaExpression(Expression argument)
 885         {
 886             if (ExpressionType.Lambda == argument.NodeType)
 887             {
 888                 return argument;
 889             }
 890             else if (ExpressionType.Quote == argument.NodeType)
 891             {
 892                 return GetLambdaExpression(((UnaryExpression)argument).Operand);
 893             }
 894
 895             throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.UnexpectedLinqLambdaExpressionFormat);
 896         }
 897
 898         // Translate a LINQ expression acting as a set input to a CQT expression
 899         private DbExpression TranslateSet(Expression linq)
 900         {
 901             return NormalizeSetSource(TranslateExpression(linq));
 902         }
 903
 904         // Translate a LINQ expression to a CQT expression.
 905         private DbExpression TranslateExpression(Expression linq)
 906         {
 907             Debug.Assert(null != linq);
 908
 909             DbExpression result;
 910             if (!_bindingContext.TryGetBoundExpression(linq, out result))
 911             {
 912                 // translate to a CQT expression
 913                 Translator translator;
 914                 if (s_translators.TryGetValue(linq.NodeType, out translator))
 915                 {
 916                     result = translator.Translate(this, linq);
 917                 }
 918                 else
 919                 {
 920                     throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.UnknownLinqNodeType, -1,
 921                         linq.NodeType.ToString());
 922                 }
 923             }
 924             return result;
 925         }
 926
 927         // Cast expression to align types between CQT and eLINQ
 928         private DbExpression AlignTypes(DbExpression cqt, Type toClrType)
 929         {
 930             Type fromClrType = null; // not used in this code path
 931             TypeUsage toType = GetCastTargetType(cqt.ResultType, toClrType, fromClrType, false);
 932             if (null != toType)
 933             {
 934                 return cqt.CastTo(toType);
 935             }
 936             else
 937             {
 938                 return cqt;
 939             }
 940         }
 941
 942         // Determines whether the given type is supported for materialization
 943         private void CheckInitializerType(Type type)
 944         {
 945             // nominal types are not supported
 946             TypeUsage typeUsage;
 947             if (_funcletizer.RootContext.Perspective.TryGetType(type, out typeUsage))
 948             {
 949                 BuiltInTypeKind typeKind = typeUsage.EdmType.BuiltInTypeKind;
 950                 if (BuiltInTypeKind.EntityType == typeKind ||
 951                     BuiltInTypeKind.ComplexType == typeKind)
 952                 {
 953                     throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedNominalType(
 954                         typeUsage.EdmType.FullName));
 955                 }
 956             }
 957
 958             // types implementing IEnumerable are not supported
 959             if (TypeSystem.IsSequenceType(type))
 960             {
 961                 throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedEnumerableType(
 962                     DescribeClrType(type)));
 963             }
 964         }
 965
 966
 967         // requires: Left and right are non-null.
 968         // effects: Determines if the given types are equivalent, ignoring facets. In
 969         // the case of primitive types, consider types equivalent if their kinds are
 970         // equivalent.
 971         // comments: This method is useful in cases where the type facets or specific
 972         // store primitive type are not reliably known, e.g. when the EDM type is determined
 973         // from the CLR type
 974         private static bool TypeUsageEquals(TypeUsage left, TypeUsage right)
 975         {
 976             Debug.Assert(null != left);
 977             Debug.Assert(null != right);
 978             if (left.EdmType.EdmEquals(right.EdmType)) { return true; }
 979
 980             // compare element types for collection
 981             if (BuiltInTypeKind.CollectionType == left.EdmType.BuiltInTypeKind &&
 982                 BuiltInTypeKind.CollectionType == right.EdmType.BuiltInTypeKind)
 983             {
 984                 return TypeUsageEquals(
 985                     ((CollectionType)left.EdmType).TypeUsage,
 986                     ((CollectionType)right.EdmType).TypeUsage);
 987             }
 988
 989             // special case for primitive types
 990             if (BuiltInTypeKind.PrimitiveType == left.EdmType.BuiltInTypeKind &&
 991                 BuiltInTypeKind.PrimitiveType == right.EdmType.BuiltInTypeKind)
 992             {
 993                 // since LINQ expressions cannot indicate model types directly, we must
 994                 // consider types equivalent if they match on the given CLR equivalent
 995                 // types (consider the Xml and String primitive types)
 996                 return ((PrimitiveType)left.EdmType).ClrEquivalentType.Equals(
 997                     ((PrimitiveType)right.EdmType).ClrEquivalentType);
 998             }
 999
1000             return false;
1001         }
1002
1003         private TypeUsage GetValueLayerType(Type linqType)
1004         {
1005             TypeUsage type;
1006             if (!TryGetValueLayerType(linqType, out type))
1007             {
1008                 throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnsupportedType(linqType));
1009             }
1010             return type;
1011         }
1012
1013         // Determine C-Space equivalent type for linqType
1014         private bool TryGetValueLayerType(Type linqType, out TypeUsage type)
1015         {
1016             // Remove nullable
1017             Type nonNullableType = TypeSystem.GetNonNullableType(linqType);
1018
1019             // Enum types are only supported for EDM V3 and higher, do not force loading
1020             // enum types for previous versions of EDM
1021             if (nonNullableType.IsEnum && this.EdmItemCollection.EdmVersion < XmlConstants.EdmVersionForV3)
1022             {
1023                 nonNullableType = nonNullableType.GetEnumUnderlyingType();
1024             }
1025
1026             // See if this is a primitive type
1027             PrimitiveTypeKind primitiveTypeKind;
1028             if (ClrProviderManifest.Instance.TryGetPrimitiveTypeKind(nonNullableType, out primitiveTypeKind))
1029             {
1030                 type = EdmProviderManifest.Instance.GetCanonicalModelTypeUsage(primitiveTypeKind);
1031                 return true;
1032             }
1033
1034             // See if this is a collection type (if so, recursively resolve)
1035             Type elementType = TypeSystem.GetElementType(nonNullableType);
1036             if (elementType != nonNullableType)
1037             {
1038                 TypeUsage elementTypeUsage;
1039                 if (TryGetValueLayerType(elementType, out elementTypeUsage))
1040                 {
1041                     type = TypeHelpers.CreateCollectionTypeUsage(elementTypeUsage);
1042                     return true;
1043                 }
1044             }
1045
1046             // Ensure the metadata for this object type is loaded
1047             _perspective.MetadataWorkspace.ImplicitLoadAssemblyForType(linqType, null);
1048
1049             if(!_perspective.TryGetTypeByName(nonNullableType.FullName, false, out type))
1050             {
1051                 // If the user is casting to a type that is not a model type or a primitive type it can be a cast to an enum that
1052                 // is not in the model. In that case we use the underlying enum type.
1053                 // Note that if the underlying type is not any of the EF primitive types we will fail with and InvalidCastException.
1054                 // This is consistent with what we would do when seeing a cast to a primitive type that is not a EF valid primitive
1055                 // type (e.g. ulong).
1056                 if(nonNullableType.IsEnum && ClrProviderManifest.Instance.TryGetPrimitiveTypeKind(nonNullableType.GetEnumUnderlyingType(), out primitiveTypeKind))
1057                 {
1058                     type = EdmProviderManifest.Instance.GetCanonicalModelTypeUsage(primitiveTypeKind);
1059                 }
1060             }
1061
1062             return type != null;
1063         }
1064
1065         /// <summary>
1066         /// Utility method validating type for comparison ops (isNull, equals, etc.).
1067         /// Only primitive types, entity types, and simple row types (no IGrouping/EntityCollection) are
1068         /// supported.
1069         /// </summary>
1070         private static void VerifyTypeSupportedForComparison(Type clrType, TypeUsage edmType, Stack<EdmMember> memberPath)
1071         {
1072             // NOTE: due to bug in null handling for complex types, complex types are currently not supported
1073             // for comparisons (see SQL BU 543956)
1074             switch (edmType.EdmType.BuiltInTypeKind)
1075             {
1076                 case BuiltInTypeKind.PrimitiveType:
1077                 case BuiltInTypeKind.EnumType:
1078                 case BuiltInTypeKind.EntityType:
1079                 case BuiltInTypeKind.RefType:
1080                     return;
1081                 case BuiltInTypeKind.RowType:
1082                     {
1083                         InitializerMetadata initializerMetadata;
1084                         if (!InitializerMetadata.TryGetInitializerMetadata(edmType, out initializerMetadata) ||
1085                             initializerMetadata.Kind == InitializerMetadataKind.ProjectionInitializer ||
1086                             initializerMetadata.Kind == InitializerMetadataKind.ProjectionNew)
1087                         {
1088                             VerifyRowTypeSupportedForComparison(clrType, (RowType)edmType.EdmType, memberPath);
1089                             return;
1090                         }
1091                         break;
1092                     }
1093                 default:
1094                     break;
1095             }
1096             if (null == memberPath)
1097             {
1098                 throw EntityUtil.NotSupported(Strings.ELinq_UnsupportedComparison(DescribeClrType(clrType)));
1099             }
1100             else
1101             {
1102                 // build up description of member path
1103                 StringBuilder memberPathDescription = new StringBuilder();
1104                 foreach (EdmMember member in memberPath)
1105                 {
1106                     memberPathDescription.Append(Strings.ELinq_UnsupportedRowMemberComparison(member.Name));
1107                 }
1108                 memberPathDescription.Append(Strings.ELinq_UnsupportedRowTypeComparison(DescribeClrType(clrType)));
1109                 throw EntityUtil.NotSupported(Strings.ELinq_UnsupportedRowComparison(memberPathDescription.ToString()));
1110             }
1111         }
1112
1113         private static void VerifyRowTypeSupportedForComparison(Type clrType, RowType rowType, Stack<EdmMember> memberPath)
1114         {
1115             foreach (EdmMember member in rowType.Properties)
1116             {
1117                 if (null == memberPath)
1118                 {
1119                     memberPath = new Stack<EdmMember>();
1120                 }
1121                 memberPath.Push(member);
1122                 VerifyTypeSupportedForComparison(clrType, member.TypeUsage, memberPath);
1123                 memberPath.Pop();
1124             }
1125         }
1126
1127         /// <summary>
1128         /// Describe type for exception message.
1129         /// </summary>
1130         internal static string DescribeClrType(Type clrType)
1131         {
1132             string clrTypeName = clrType.Name;
1133             // Yes, this is a heuristic... just a best effort way of getting
1134             // a reasonable exception message
1135             if (IsCSharpGeneratedClass(clrTypeName, "DisplayClass") ||
1136                 IsVBGeneratedClass(clrTypeName, "Closure"))
1137             {
1138                 return Strings.ELinq_ClosureType;
1139             }
1140             if (IsCSharpGeneratedClass(clrTypeName, "AnonymousType") ||
1141                 IsVBGeneratedClass(clrTypeName, "AnonymousType"))
1142             {
1143                 return Strings.ELinq_AnonymousType;
1144             }
1145
1146             string returnName = string.Empty;
1147             if (!String.IsNullOrEmpty(clrType.Namespace))
1148             {
1149                 returnName += clrType.Namespace + ".";
1150             }
1151             returnName += clrType.Name;
1152             return returnName;
1153         }
1154
1155         private static bool IsCSharpGeneratedClass(string typeName, string pattern)
1156         {
1157             return typeName.Contains("<>") && typeName.Contains("__") && typeName.Contains(pattern);
1158         }
1159
1160         private static bool IsVBGeneratedClass(string typeName, string pattern)
1161         {
1162             return typeName.Contains("_") && typeName.Contains("$") && typeName.Contains(pattern);
1163         }
1164
1165         /// <summary>
1166         /// Creates an implementation of IsNull. Throws exception when operand type is not supported.
1167         /// </summary>
1168         private DbExpression CreateIsNullExpression(DbExpression operand, Type operandClrType)
1169         {
1170             VerifyTypeSupportedForComparison(operandClrType, operand.ResultType, null);
1171             return operand.IsNull();
1172         }
1173
1174         /// <summary>
1175         /// Creates an implementation of equals using the given pattern. Throws exception when argument types
1176         /// are not supported for equals comparison.
1177         /// </summary>
1178         private DbExpression CreateEqualsExpression(DbExpression left, DbExpression right, EqualsPattern pattern, Type leftClrType, Type rightClrType)
1179         {
1180             VerifyTypeSupportedForComparison(leftClrType, left.ResultType, null);
1181             VerifyTypeSupportedForComparison(rightClrType, right.ResultType, null);
1182
1183             //For Ref Type comparison, check whether they refer to compatible Entity Types.
1184             TypeUsage leftType = left.ResultType;
1185             TypeUsage rightType = right.ResultType;
1186             if (leftType.EdmType.BuiltInTypeKind == BuiltInTypeKind.RefType && rightType.EdmType.BuiltInTypeKind == BuiltInTypeKind.RefType)
1187             {
1188                 TypeUsage commonType;
1189                 if (!TypeSemantics.TryGetCommonType(leftType, rightType, out commonType))
1190                 {
1191                     RefType leftRefType = left.ResultType.EdmType as RefType;
1192                     RefType rightRefType = right.ResultType.EdmType as RefType;
1193                     throw EntityUtil.NotSupported(Strings.ELinq_UnsupportedRefComparison(leftRefType.ElementType.FullName, rightRefType.ElementType.FullName));
1194                 }
1195             }
1196
1197             return RecursivelyRewriteEqualsExpression(left, right, pattern);
1198         }
1199         private DbExpression RecursivelyRewriteEqualsExpression(DbExpression left, DbExpression right, EqualsPattern pattern)
1200         {
1201             // check if either side is an initializer type
1202             RowType leftType = left.ResultType.EdmType as RowType;
1203             RowType rightType = left.ResultType.EdmType as RowType;
1204
1205             if (null != leftType || null != rightType)
1206             {
1207                 if ((null != leftType && null != rightType) && leftType.EdmEquals(rightType))
1208                 {
1209                     DbExpression shreddedEquals = null;
1210                     // if the types are the same, use struct equivalence semantics
1211                     foreach (EdmProperty property in leftType.Properties)
1212                     {
1213                         DbPropertyExpression leftElement = left.Property(property);
1214                         DbPropertyExpression rightElement = right.Property(property);
1215                         DbExpression elementsEquals = RecursivelyRewriteEqualsExpression(
1216                             leftElement, rightElement, pattern);
1217
1218                         // build up and expression
1219                         if (null == shreddedEquals) { shreddedEquals = elementsEquals; }
1220                         else { shreddedEquals = shreddedEquals.And(elementsEquals); }
1221                     }
1222                     return shreddedEquals;
1223                 }
1224                 else
1225                 {
1226                     // if one or both sides is an initializer and the types are not the same,
1227                     // "equals" always evaluates to false
1228                     return DbExpressionBuilder.False;
1229                 }
1230             }
1231             else
1232             {
1233                 return ImplementEquality(left, right, pattern);
1234             }
1235         }
1236
1237         // For comparisons, where the left and right side are nullable or not nullable,
1238         // here are the (compositionally safe) null equality predicates:
1239         // -- x NOT NULL, y NULL
1240         // x = y AND  NOT (y IS NULL)
1241         // -- x NULL, y NULL
1242         // (x = y AND  (NOT (x IS NULL OR y IS NULL))) OR (x IS NULL AND y IS NULL)
1243         // -- x NOT NULL, y NOT NULL
1244         // x = y
1245         // -- x NULL, y NOT NULL
1246         // x = y AND  NOT (x IS NULL)
1247         private DbExpression ImplementEquality(DbExpression left, DbExpression right, EqualsPattern pattern)
1248         {
1249             switch (left.ExpressionKind)
1250             {
1251                 case DbExpressionKind.Constant:
1252                     switch (right.ExpressionKind)
1253                     {
1254                         case DbExpressionKind.Constant: // constant EQ constant
1255                             return left.Equal(right);
1256                         case DbExpressionKind.Null: // null EQ constant --> false
1257                             return DbExpressionBuilder.False;
1258                         default:
1259                             return ImplementEqualityConstantAndUnknown((System.Data.Common.CommandTrees.DbConstantExpression)left, right, pattern);
1260                     }
1261                 case DbExpressionKind.Null:
1262                     switch (right.ExpressionKind)
1263                     {
1264                         case DbExpressionKind.Constant: // null EQ constant --> false
1265                             return DbExpressionBuilder.False;
1266                         case DbExpressionKind.Null: // null EQ null --> true
1267                             return DbExpressionBuilder.True;
1268                         default: // null EQ right --> right IS NULL
1269                             return right.IsNull();
1270                     }
1271                 default: // unknown
1272                     switch (right.ExpressionKind)
1273                     {
1274                         case DbExpressionKind.Constant:
1275                             return ImplementEqualityConstantAndUnknown((System.Data.Common.CommandTrees.DbConstantExpression)right, left, pattern);
1276                         case DbExpressionKind.Null: //  left EQ null --> left IS NULL
1277                             return left.IsNull();
1278                         default:
1279                             return ImplementEqualityUnknownArguments(left, right, pattern);
1280                     }
1281             }
1282         }
1283
1284         // Generate an equality expression with one unknown operator and
1285         private DbExpression ImplementEqualityConstantAndUnknown(
1286             System.Data.Common.CommandTrees.DbConstantExpression constant, DbExpression unknown, EqualsPattern pattern)
1287         {
1288             switch (pattern)
1289             {
1290                 case EqualsPattern.Store:
1291                 case EqualsPattern.PositiveNullEqualityNonComposable: // for Joins
1292                     return constant.Equal(unknown); // either both are non-null, or one is null and the predicate result is undefined
1293                 case EqualsPattern.PositiveNullEqualityComposable:
1294                     if (!_funcletizer.RootContext.ContextOptions.UseCSharpNullComparisonBehavior)
1295                     {
1296                         return constant.Equal(unknown); // same as EqualsPattern.PositiveNullEqualityNonComposable
1297                     }
1298                     return constant.Equal(unknown).And(unknown.IsNull().Not()); // add more logic to avoid undefined result for true clr semantics
1299                 default:
1300                     Debug.Fail("unknown pattern");
1301                     return null;
1302             }
1303         }
1304
1305         // Generate an equality expression where the values of the left and right operands are completely unknown
1306         private DbExpression ImplementEqualityUnknownArguments(DbExpression left, DbExpression right, EqualsPattern pattern)
1307         {
1308             switch (pattern)
1309             {
1310                 case EqualsPattern.Store: // left EQ right
1311                     return left.Equal(right);
1312                 case EqualsPattern.PositiveNullEqualityNonComposable: // for Joins
1313                     return left.Equal(right).Or(left.IsNull().And(right.IsNull()));
1314                 case EqualsPattern.PositiveNullEqualityComposable:
1315                     {
1316                         var bothNotNull = left.Equal(right);
1317                         var bothNull = left.IsNull().And(right.IsNull());
1318                         if (!_funcletizer.RootContext.ContextOptions.UseCSharpNullComparisonBehavior)
1319                         {
1320                             return bothNotNull.Or(bothNull); // same as EqualsPattern.PositiveNullEqualityNonComposable
1321                         }
1322                         // add more logic to avoid undefined result for true clr semantics, ensuring composability
1323                         // (left EQ right AND NOT (left IS NULL OR right IS NULL)) OR (left IS NULL AND right IS NULL)
1324                         var anyOneIsNull = left.IsNull().Or(right.IsNull());
1325                         return (bothNotNull.And(anyOneIsNull.Not())).Or(bothNull);
1326                     }
1327                 default:
1328                     Debug.Fail("unexpected pattern");
1329                     return null;
1330             }
1331         }
1332
1333         #endregion
1334
1335         #region Helper Methods Shared by Translators
1336         /// <summary>
1337         /// Helper method for String.StartsWith, String.EndsWith and String.Contains
1338         ///
1339         /// object.Method(argument), where Method is one of String.StartsWith, String.EndsWith or
1340         /// String.Contains is translated into:
1341         ///     1) If argument is a constant or parameter and the provider supports escaping:
1342         ///         object like ("%") + argument1 + ("%"), where argument1 is argument escaped by the provider
1343         ///         and ("%") are appended on the begining/end depending on whether
1344         ///         insertPercentAtStart/insertPercentAtEnd are specified
1345         ///     2) Otherwise:
1346         ///           object.Method(argument) ->  defaultTranslator
1347         /// </summary>
1348         /// <param name="call"></param>
1349         /// <param name="insertPercentAtStart">Should '%' be inserted at the begining of the pattern</param>
1350         /// <param name="insertPercentAtEnd">Should '%' be inserted at the end of the pattern</param>
1351         /// <param name="defaultTranslator">The delegate that provides the default translation</param>
1352         /// <returns>The translation</returns>
1353         private DbExpression TranslateFunctionIntoLike(MethodCallExpression call, bool insertPercentAtStart, bool insertPercentAtEnd, Func<ExpressionConverter, MethodCallExpression, DbExpression, DbExpression, DbExpression> defaultTranslator)
1354         {
1355             char escapeChar;
1356             bool providerSupportsEscapingLikeArgument = this.ProviderManifest.SupportsEscapingLikeArgument(out escapeChar);
1357             bool useLikeTranslation = false;
1358             bool specifyEscape = true;
1359
1360             Expression patternExpression = call.Arguments[0];
1361             Expression inputExpression = call.Object;
1362
1363             QueryParameterExpression queryParameterExpression = patternExpression as QueryParameterExpression;
1364             if (providerSupportsEscapingLikeArgument && (queryParameterExpression != null))
1365             {
1366                 useLikeTranslation = true;
1367                 bool specifyEscapeDummy;
1368                 patternExpression = queryParameterExpression.EscapeParameterForLike(input => PreparePattern(input, insertPercentAtStart, insertPercentAtEnd, out specifyEscapeDummy));
1369             }
1370
1371             DbExpression translatedPatternExpression = this.TranslateExpression(patternExpression);
1372             DbExpression translatedInputExpression = this.TranslateExpression(inputExpression);
1373
1374             if (providerSupportsEscapingLikeArgument && translatedPatternExpression.ExpressionKind == DbExpressionKind.Constant)
1375             {
1376                 useLikeTranslation = true;
1377                 DbConstantExpression constantExpression = (DbConstantExpression)translatedPatternExpression;
1378
1379                 string preparedValue = PreparePattern((string)constantExpression.Value, insertPercentAtStart, insertPercentAtEnd, out specifyEscape);
1380                 Debug.Assert(preparedValue != null, "The prepared value should not be null when the input is non-null");
1381
1382                 //Note: the result type needs to be taken from the original expression, as the user may have specified Unicode/Non-Unicode
1383                 translatedPatternExpression = DbExpressionBuilder.Constant(constantExpression.ResultType, preparedValue);
1384             }
1385
1386             DbExpression result;
1387             if (useLikeTranslation)
1388             {
1389                 if (specifyEscape)
1390                 {
1391                     //DevDiv #326720: The constant expression for the escape character should not have unicode set by default
1392                     var escapeExpression = DbExpressionBuilder.Constant(EdmProviderManifest.Instance.GetCanonicalModelTypeUsage(PrimitiveTypeKind.String), new String(new char[] { escapeChar }));
1393                     result = DbExpressionBuilder.Like(translatedInputExpression, translatedPatternExpression, escapeExpression);
1394                 }
1395                 else
1396                 {
1397                     result = DbExpressionBuilder.Like(translatedInputExpression, translatedPatternExpression);
1398                 }
1399             }
1400             else
1401             {
1402                 result = defaultTranslator(this, call, translatedPatternExpression, translatedInputExpression);
1403             }
1404
1405             return result;
1406         }
1407
1408         /// <summary>
1409         /// Prepare the given input patternValue into a pattern to be used in a LIKE expression by
1410         /// first escaping it by the provider and then appending "%" and the beginging/end depending
1411         /// on whether insertPercentAtStart/insertPercentAtEnd is specified.
1412         /// </summary>
1413         private string PreparePattern(string patternValue, bool insertPercentAtStart, bool insertPercentAtEnd, out bool specifyEscape)
1414         {
1415             // Dev10 #800466: The pattern value if originating from a parameter value could be null
1416             if (patternValue == null)
1417             {
1418                 specifyEscape = false;
1419                 return null;
1420             }
1421
1422             string escapedPatternValue = this.ProviderManifest.EscapeLikeArgument(patternValue);
1423
1424             if (escapedPatternValue == null)
1425             {
1426                 throw EntityUtil.ProviderIncompatible(System.Data.Entity.Strings.ProviderEscapeLikeArgumentReturnedNull);
1427             }
1428
1429             specifyEscape = patternValue != escapedPatternValue;
1430
1431             System.Text.StringBuilder patternBuilder = new System.Text.StringBuilder();
1432             if (insertPercentAtStart)
1433             {
1434                 patternBuilder.Append("%");
1435             }
1436             patternBuilder.Append(escapedPatternValue);
1437             if (insertPercentAtEnd)
1438             {
1439                 patternBuilder.Append("%");
1440             }
1441
1442             return  patternBuilder.ToString();
1443         }
1444
1445         /// <summary>
1446         ///  Translates the arguments into DbExpressions
1447         ///   and creates a canonical function with the given functionName and these arguments
1448         /// </summary>
1449         /// <param name="functionName">Should represent a non-aggregate canonical function</param>
1450         /// <param name="Expression">Passed only for error handling purposes</param>
1451         /// <param name="linqArguments"></param>
1452         /// <returns></returns>
1453         private DbFunctionExpression TranslateIntoCanonicalFunction(string functionName, Expression Expression, params Expression[] linqArguments)
1454         {
1455             DbExpression[] translatedArguments = new DbExpression[linqArguments.Length];
1456             for (int i = 0; i < linqArguments.Length; i++)
1457             {
1458                 translatedArguments[i] = TranslateExpression(linqArguments[i]);
1459             }
1460             return CreateCanonicalFunction(functionName, Expression, translatedArguments);
1461         }
1462
1463         /// <summary>
1464         /// Creates a canonical function with the given name and the given arguments
1465         /// </summary>
1466         /// <param name="functionName">Should represent a non-aggregate canonical function</param>
1467         /// <param name="Expression">Passed only for error handling purposes</param>
1468         /// <param name="translatedArguments"></param>
1469         /// <returns></returns>
1470         private DbFunctionExpression CreateCanonicalFunction(string functionName, Expression Expression, params DbExpression[] translatedArguments)
1471         {
1472             List<TypeUsage> translatedArgumentTypes = new List<TypeUsage>(translatedArguments.Length);
1473             foreach (DbExpression translatedArgument in translatedArguments)
1474             {
1475                 translatedArgumentTypes.Add(translatedArgument.ResultType);
1476             }
1477             EdmFunction function = FindCanonicalFunction(functionName, translatedArgumentTypes, false /* isGroupAggregateFunction */, Expression);
1478             return function.Invoke(translatedArguments);
1479         }
1480
1481         /// <summary>
1482         /// Finds a canonical function with the given functionName and argumentTypes
1483         /// </summary>
1484         /// <param name="functionName"></param>
1485         /// <param name="argumentTypes"></param>
1486         /// <param name="isGroupAggregateFunction"></param>
1487         /// <param name="Expression"></param>
1488         /// <returns></returns>
1489         private EdmFunction FindCanonicalFunction(string functionName, IList<TypeUsage> argumentTypes, bool isGroupAggregateFunction, Expression Expression)
1490         {
1491             return FindFunction(EdmNamespaceName, functionName, argumentTypes, isGroupAggregateFunction, Expression);
1492         }
1493
1494         /// <summary>
1495         /// Finds a function with the given namespaceName, functionName and argumentTypes
1496         /// </summary>
1497         /// <param name="namespaceName"></param>
1498         /// <param name="functionName"></param>
1499         /// <param name="argumentTypes"></param>
1500         /// <param name="isGroupAggregateFunction"></param>
1501         /// <param name="Expression"></param>
1502         /// <returns></returns>
1503         private EdmFunction FindFunction(string namespaceName, string functionName, IList<TypeUsage> argumentTypes, bool isGroupAggregateFunction, Expression Expression)
1504         {
1505             // find the function
1506             IList<EdmFunction> candidateFunctions;
1507             if (!_perspective.TryGetFunctionByName(namespaceName, functionName, false /* ignore case */, out candidateFunctions))
1508             {
1509                 ThrowUnresolvableFunction(Expression);
1510             }
1511
1512             Debug.Assert(null != candidateFunctions && candidateFunctions.Count > 0, "provider functions must not be null or empty");
1513
1514             bool isAmbiguous;
1515             EdmFunction function = FunctionOverloadResolver.ResolveFunctionOverloads(candidateFunctions, argumentTypes, isGroupAggregateFunction, out isAmbiguous);
1516             if (isAmbiguous || null == function)
1517             {
1518                 ThrowUnresolvableFunctionOverload(Expression, isAmbiguous);
1519             }
1520             return function;
1521         }
1522
1523         /// <summary>
1524         /// Helper method for FindFunction
1525         /// </summary>
1526         /// <param name="Expression"></param>
1527         private static void ThrowUnresolvableFunction(Expression Expression)
1528         {
1529             if (Expression.NodeType == ExpressionType.Call)
1530             {
1531                 MethodInfo methodInfo = ((MethodCallExpression)Expression).Method;
1532                 throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableFunctionForMethod(methodInfo, methodInfo.DeclaringType));
1533             }
1534             else if (Expression.NodeType == ExpressionType.MemberAccess)
1535             {
1536                 string memberName;
1537                 Type memberType;
1538                 MemberInfo memberInfo = TypeSystem.PropertyOrField(((MemberExpression)Expression).Member, out memberName, out memberType);
1539                 throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableFunctionForMember(memberInfo, memberInfo.DeclaringType));
1540             }
1541             throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableFunctionForExpression(Expression.NodeType));
1542         }
1543
1544         /// <summary>
1545         /// Helper method for FindCanonicalFunction
1546         /// </summary>
1547         /// <param name="Expression"></param>
1548         private static void ThrowUnresolvableFunctionOverload(Expression Expression, bool isAmbiguous)
1549         {
1550             if (Expression.NodeType == ExpressionType.Call)
1551             {
1552                 MethodInfo methodInfo = ((MethodCallExpression)Expression).Method;
1553                 if (isAmbiguous)
1554                 {
1555                     throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableFunctionForMethodAmbiguousMatch(methodInfo, methodInfo.DeclaringType));
1556                 }
1557                 else
1558                 {
1559                     throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableFunctionForMethodNotFound(methodInfo, methodInfo.DeclaringType));
1560                 }
1561             }
1562             else if (Expression.NodeType == ExpressionType.MemberAccess)
1563             {
1564                 string memberName;
1565                 Type memberType;
1566                 MemberInfo memberInfo = TypeSystem.PropertyOrField(((MemberExpression)Expression).Member, out memberName, out memberType);
1567                 throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableStoreFunctionForMember(memberInfo, memberInfo.DeclaringType));
1568             }
1569             throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_UnresolvableStoreFunctionForExpression(Expression.NodeType));
1570         }
1571
1572         private DbNewInstanceExpression CreateNewRowExpression(List<KeyValuePair<string, DbExpression>> columns, InitializerMetadata initializerMetadata)
1573         {
1574             List<DbExpression> propertyValues = new List<DbExpression>(columns.Count);
1575             List<EdmProperty> properties = new List<EdmProperty>(columns.Count);
1576             for (int i = 0; i < columns.Count; i++)
1577             {
1578                 var column = columns[i];
1579                 propertyValues.Add(column.Value);
1580                 properties.Add(new EdmProperty(column.Key, column.Value.ResultType));
1581             }
1582             RowType rowType = new RowType(properties, initializerMetadata);
1583             TypeUsage typeUsage = TypeUsage.Create(rowType);
1584             return typeUsage.New(propertyValues);
1585         }
1586
1587         #endregion
1588
1589         #region Private enums
1590         // Describes different implementation pattern for equality comparisons.
1591         // For all patterns, if one side of the expression is a constant null, converts to an IS NULL
1592         // expression (or resolves to 'true' or 'false' if some constraint is known for the other side).
1593         //
1594         // If neither side is a constant null, the semantics differ:
1595         //
1596         // (1) (left EQ right) => left and right are equal and not null, so return true.
1597         // (2) (left IS NULL AND right IS NULL) => Both left and right are null, so return true.
1598         // (3) NOT (left IS NULL OR right IS NULL) =>
1599         //      If only one of left or right is null, (1) evaluates to "unknown" and (2) evaluates to false. So we get "unknown" from DB which is null in C#.
1600         //      This is not desired as it does not help in composability. Hence, (3) is used to return false instead of "unknown" when only one of the operands is null.
1601         //
1602         // Store: (1)
1603         // PositiveNullEqualityNonComposable: (1) OR (2) - suitable only for Join operators, as they are not composable
1604         // PositiveNullEqualityComposable: (1) OR (2) AND (3)
1605         //
1606         // In the actual implementation (see ImplementEquality), optimizations exist if one or the other
1607         // side is known not to be null.
1608         private enum EqualsPattern
1609         {
1610             Store, // defer to store
1611             PositiveNullEqualityNonComposable, // simulate C# semantics in store, return "null" if left or right is null, but not both. Suitable for joins.
1612             PositiveNullEqualityComposable, // simulate C# semantics in store, always return true or false
1613         }
1614         #endregion
1615     }
1616 }