mcs/class/referencesource/System.Data.Entity/System/Data/Common/EntitySql/FunctionOverloadResolver.cs

   1 //---------------------------------------------------------------------
   2 // <copyright file="FunctionOverloadResolver.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner  [....]
   7 // @backupOwner [....]
   8 //---------------------------------------------------------------------
   9
  10 namespace System.Data.Common.EntitySql
  11 {
  12     using System;
  13     using System.Collections.Generic;
  14     using System.Data.Entity;
  15     using System.Data.Metadata.Edm;
  16     using System.Diagnostics;
  17     using System.Linq;
  18
  19     /// <summary>
  20     /// Represents function overload resolution mechanism, used by L2E and eSQL frontends.
  21     /// </summary>
  22     internal static class FunctionOverloadResolver
  23     {
  24         /// <summary>
  25         /// Resolves <paramref name="argTypes"/> against the list of function signatures.
  26         /// </summary>
  27         /// <returns>Funciton metadata</returns>
  28         internal static EdmFunction ResolveFunctionOverloads(IList<EdmFunction> functionsMetadata,
  29                                                              IList<TypeUsage> argTypes,
  30                                                              bool isGroupAggregateFunction,
  31                                                              out bool isAmbiguous)
  32         {
  33             return ResolveFunctionOverloads(
  34                 functionsMetadata,
  35                 argTypes,
  36                 (edmFunction) => edmFunction.Parameters,
  37                 (functionParameter) => functionParameter.TypeUsage,
  38                 (functionParameter) => functionParameter.Mode,
  39                 (argType) => TypeSemantics.FlattenType(argType),
  40                 (paramType, argType) => TypeSemantics.FlattenType(paramType),
  41                 (fromType, toType) => TypeSemantics.IsPromotableTo(fromType, toType),
  42                 (fromType, toType) => TypeSemantics.IsStructurallyEqual(fromType, toType),
  43                 isGroupAggregateFunction,
  44                 out isAmbiguous);
  45         }
  46
  47         /// <summary>
  48         /// Resolves <paramref name="argTypes"/> against the list of function signatures.
  49         /// </summary>
  50         /// <returns>Funciton metadata</returns>
  51         internal static EdmFunction ResolveFunctionOverloads(IList<EdmFunction> functionsMetadata,
  52                                                              IList<TypeUsage> argTypes,
  53                                                              Func<TypeUsage, IEnumerable<TypeUsage>> flattenArgumentType,
  54                                                              Func<TypeUsage, TypeUsage, IEnumerable<TypeUsage>> flattenParameterType,
  55                                                              Func<TypeUsage, TypeUsage, bool> isPromotableTo,
  56                                                              Func<TypeUsage, TypeUsage, bool> isStructurallyEqual,
  57                                                              bool isGroupAggregateFunction,
  58                                                              out bool isAmbiguous)
  59         {
  60             return ResolveFunctionOverloads(
  61                 functionsMetadata,
  62                 argTypes,
  63                 (edmFunction) => edmFunction.Parameters,
  64                 (functionParameter) => functionParameter.TypeUsage,
  65                 (functionParameter) => functionParameter.Mode,
  66                 flattenArgumentType,
  67                 flattenParameterType,
  68                 isPromotableTo,
  69                 isStructurallyEqual,
  70                 isGroupAggregateFunction,
  71                 out isAmbiguous);
  72         }
  73
  74         /// <summary>
  75         /// Resolves <paramref name="argTypes"/> against the list of function signatures.
  76         /// </summary>
  77         /// <param name="getSignatureParams">function formal signature getter</param>
  78         /// <param name="getParameterTypeUsage">TypeUsage getter for a signature param</param>
  79         /// <param name="getParameterMode">ParameterMode getter for a signature param</param>
  80         /// <returns>Funciton metadata</returns>
  81         internal static TFunctionMetadata ResolveFunctionOverloads<TFunctionMetadata, TFunctionParameterMetadata>(
  82             IList<TFunctionMetadata> functionsMetadata,
  83             IList<TypeUsage> argTypes,
  84             Func<TFunctionMetadata, IList<TFunctionParameterMetadata>> getSignatureParams,
  85             Func<TFunctionParameterMetadata, TypeUsage> getParameterTypeUsage,
  86             Func<TFunctionParameterMetadata, ParameterMode> getParameterMode,
  87             Func<TypeUsage, IEnumerable<TypeUsage>> flattenArgumentType,
  88             Func<TypeUsage, TypeUsage, IEnumerable<TypeUsage>> flattenParameterType,
  89             Func<TypeUsage, TypeUsage, bool> isPromotableTo,
  90             Func<TypeUsage, TypeUsage, bool> isStructurallyEqual,
  91             bool isGroupAggregateFunction,
  92             out bool isAmbiguous) where TFunctionMetadata : class
  93         {
  94             //
  95             // Flatten argument list
  96             //
  97             List<TypeUsage> argTypesFlat = new List<TypeUsage>(argTypes.Count);
  98             foreach (TypeUsage argType in argTypes)
  99             {
 100                 argTypesFlat.AddRange(flattenArgumentType(argType));
 101             }
 102
 103             //
 104             // Find a candidate overload with the best total rank, remember the candidate and its composite rank.
 105             //
 106             TFunctionMetadata bestCandidate = null;
 107             isAmbiguous = false;
 108             List<int[]> ranks = new List<int[]>(functionsMetadata.Count);
 109             int[] bestCandidateRank = null;
 110             for (int i = 0, maxTotalRank = int.MinValue; i < functionsMetadata.Count; i++)
 111             {
 112                 int totalRank;
 113                 int[] rank;
 114                 if (TryRankFunctionParameters(argTypes,
 115                                               argTypesFlat,
 116                                               getSignatureParams(functionsMetadata[i]),
 117                                               getParameterTypeUsage,
 118                                               getParameterMode,
 119                                               flattenParameterType,
 120                                               isPromotableTo,
 121                                               isStructurallyEqual,
 122                                               isGroupAggregateFunction,
 123                                               out totalRank, out rank))
 124                 {
 125                     if (totalRank == maxTotalRank)
 126                     {
 127                         isAmbiguous = true;
 128                     }
 129                     else if (totalRank > maxTotalRank)
 130                     {
 131                         isAmbiguous = false;
 132                         maxTotalRank = totalRank;
 133                         bestCandidate = functionsMetadata[i];
 134                         bestCandidateRank = rank;
 135                     }
 136
 137                     Debug.Assert(argTypesFlat.Count == rank.Length, "argTypesFlat.Count == rank.Length");
 138
 139                     ranks.Add(rank);
 140                 }
 141             }
 142
 143             //
 144             // If there is a best candidate, check it for ambiguity against composite ranks of other candidates
 145             //
 146             if (bestCandidate != null &&
 147                 !isAmbiguous &&
 148                 argTypesFlat.Count > 1 && // best candidate may be ambiguous only in the case of 2 or more arguments
 149                 ranks.Count > 1)
 150             {
 151                 Debug.Assert(bestCandidateRank != null);
 152
 153                 //
 154                 // Search collection of composite ranks to see if there is an overload that would render the best candidate ambiguous
 155                 //
 156                 isAmbiguous = ranks.Any(rank =>
 157                 {
 158                     Debug.Assert(rank.Length == bestCandidateRank.Length, "composite ranks have different number of elements");
 159
 160                     if (!Object.ReferenceEquals(bestCandidateRank, rank)) // do not compare best cadnidate against itself
 161                     {
 162                         // All individual ranks of the best candidate must equal or better than the ranks of all other candidates,
 163                         // otherwise we consider it ambigous, even though it has an unambigously best total rank.
 164                         for (int i = 0; i < rank.Length; ++i)
 165                         {
 166                             if (bestCandidateRank[i] < rank[i])
 167                             {
 168                                 return true;
 169                             }
 170                         }
 171                     }
 172
 173                     return false;
 174                 });
 175             }
 176
 177             return isAmbiguous ? null : bestCandidate;
 178         }
 179
 180         /// <summary>
 181         /// Check promotability, returns true if argument list is promotable to the overload and overload was successfully ranked, otherwise false.
 182         /// Ranks the overload parameter types against the argument list.
 183         /// </summary>
 184         /// <param name="argumentList">list of argument types</param>
 185         /// <param name="flatArgumentList">flattened list of argument types</param>
 186         /// <param name="overloadParamList1">list of overload parameter types</param>
 187         /// <param name="getParameterTypeUsage">TypeUsage getter for the overload parameters</param>
 188         /// <param name="getParameterMode">ParameterMode getter for the overload parameters</param>
 189         /// <param name="totalRank">returns total promotion rank of the overload, 0 if no arguments</param>
 190         /// <param name="parameterRanks">returns individual promotion ranks of the overload parameters, empty array if no arguments</param>
 191         private static bool TryRankFunctionParameters<TFunctionParameterMetadata>(IList<TypeUsage> argumentList,
 192                                                                                   IList<TypeUsage> flatArgumentList,
 193                                                                                   IList<TFunctionParameterMetadata> overloadParamList,
 194                                                                                   Func<TFunctionParameterMetadata, TypeUsage> getParameterTypeUsage,
 195                                                                                   Func<TFunctionParameterMetadata, ParameterMode> getParameterMode,
 196                                                                                   Func<TypeUsage, TypeUsage, IEnumerable<TypeUsage>> flattenParameterType,
 197                                                                                   Func<TypeUsage, TypeUsage, bool> isPromotableTo,
 198                                                                                   Func<TypeUsage, TypeUsage, bool> isStructurallyEqual,
 199                                                                                   bool isGroupAggregateFunction,
 200                                                                                   out int totalRank,
 201                                                                                   out int[] parameterRanks)
 202         {
 203             totalRank = 0;
 204             parameterRanks = null;
 205
 206             if (argumentList.Count != overloadParamList.Count)
 207             {
 208                 return false;
 209             }
 210
 211             //
 212             // Check promotability and flatten the parameter types
 213             //
 214             List<TypeUsage> flatOverloadParamList = new List<TypeUsage>(flatArgumentList.Count);
 215             for (int i = 0; i < overloadParamList.Count; ++i)
 216             {
 217                 TypeUsage argumentType = argumentList[i];
 218                 TypeUsage parameterType = getParameterTypeUsage(overloadParamList[i]);
 219
 220                 //
 221                 // Parameter mode must match.
 222                 //
 223                 ParameterMode parameterMode = getParameterMode(overloadParamList[i]);
 224                 if (parameterMode != ParameterMode.In && parameterMode != ParameterMode.InOut)
 225                 {
 226                     return false;
 227                 }
 228
 229                 //
 230                 // If function being ranked is a group aggregate, consider the element type.
 231                 //
 232                 if (isGroupAggregateFunction)
 233                 {
 234                     if (!TypeSemantics.IsCollectionType(parameterType))
 235                     {
 236                         //
 237                         // Even though it is the job of metadata to ensure that the provider manifest is consistent.
 238                         // Ensure that if a function is marked as aggregate, then the argument type must be of collection{GivenType}.
 239                         //
 240                         throw EntityUtil.EntitySqlError(Strings.InvalidArgumentTypeForAggregateFunction);
 241                     }
 242                     parameterType = TypeHelpers.GetElementTypeUsage(parameterType);
 243                 }
 244
 245                 //
 246                 // If argument is not promotable - reject the overload.
 247                 //
 248                 if (!isPromotableTo(argumentType, parameterType))
 249                 {
 250                     return false;
 251                 }
 252
 253                 //
 254                 // Flatten the parameter type.
 255                 //
 256                 flatOverloadParamList.AddRange(flattenParameterType(parameterType, argumentType));
 257             }
 258
 259             Debug.Assert(flatArgumentList.Count == flatOverloadParamList.Count, "flatArgumentList.Count == flatOverloadParamList.Count");
 260
 261             //
 262             // Rank argument promotions
 263             //
 264             parameterRanks = new int[flatOverloadParamList.Count];
 265             for (int i = 0; i < parameterRanks.Length; ++i)
 266             {
 267                 int rank = GetPromotionRank(flatArgumentList[i], flatOverloadParamList[i], isPromotableTo, isStructurallyEqual);
 268                 totalRank += rank;
 269                 parameterRanks[i] = rank;
 270             }
 271
 272             return true;
 273         }
 274
 275         /// <summary>
 276         /// Ranks the <paramref name="fromType"/> -> <paramref name="toType"/> promotion.
 277         /// Range of values: 0 to negative infinity, with 0 as the best rank (promotion to self).
 278         /// <paramref name="fromType"/> must be promotable to <paramref name="toType"/>, otherwise internal error is thrown.
 279         /// </summary>
 280         private static int GetPromotionRank(TypeUsage fromType,
 281                                             TypeUsage toType,
 282                                             Func<TypeUsage, TypeUsage, bool> isPromotableTo,
 283                                             Func<TypeUsage, TypeUsage, bool> isStructurallyEqual)
 284         {
 285             //
 286             // Only promotable types are allowed at this point.
 287             //
 288             Debug.Assert(isPromotableTo(fromType, toType), "isPromotableTo(fromType, toType)");
 289
 290             //
 291             // If both types are the same return rank 0 - the best match.
 292             //
 293             if (isStructurallyEqual(fromType, toType))
 294             {
 295                 return 0;
 296             }
 297
 298             //
 299             // In the case of eSQL untyped null will float up to the point of isStructurallyEqual(...) above.
 300             // Below it eveything should be normal.
 301             //
 302             Debug.Assert(fromType != null, "fromType != null");
 303             Debug.Assert(toType != null, "toType != null");
 304
 305             //
 306             // Handle primitive types
 307             //
 308             PrimitiveType primitiveFromType = fromType.EdmType as PrimitiveType;
 309             PrimitiveType primitiveToType = toType.EdmType as PrimitiveType;
 310             if (primitiveFromType != null && primitiveToType != null)
 311             {
 312                 if (Helper.AreSameSpatialUnionType(primitiveFromType, primitiveToType))
 313                 {
 314                     return 0;
 315                 }
 316
 317                 IList<PrimitiveType> promotions = EdmProviderManifest.Instance.GetPromotionTypes(primitiveFromType);
 318
 319                 int promotionIndex = promotions.IndexOf(primitiveToType);
 320
 321                 if (promotionIndex < 0)
 322                 {
 323                     throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.FailedToGeneratePromotionRank, 1);
 324                 }
 325
 326                 return -promotionIndex;
 327             }
 328
 329             //
 330             // Handle entity/relship types
 331             //
 332             EntityTypeBase entityBaseFromType = fromType.EdmType as EntityTypeBase;
 333             EntityTypeBase entityBaseToType = toType.EdmType as EntityTypeBase;
 334             if (entityBaseFromType != null && entityBaseToType != null)
 335             {
 336                 int promotionIndex = 0;
 337                 EdmType t;
 338                 for (t = entityBaseFromType; t != entityBaseToType && t != null; t = t.BaseType, ++promotionIndex);
 339
 340                 if (t == null)
 341                 {
 342                     throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.FailedToGeneratePromotionRank, 2);
 343                 }
 344
 345                 return -promotionIndex;
 346             }
 347
 348             throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.FailedToGeneratePromotionRank, 3);
 349         }
 350     }
 351 }