src/Boo.Lang.Compiler/TypeSystem/CallableResolutionService.cs

   1 #region license
   2 // Copyright (c) 2003, 2004, 2005 Rodrigo B. de Oliveira (rbo@acm.org)
   3 // All rights reserved.
   4 //
   5 // Redistribution and use in source and binary forms, with or without modification,
   6 // are permitted provided that the following conditions are met:
   7 //
   8 //     * Redistributions of source code must retain the above copyright notice,
   9 //     this list of conditions and the following disclaimer.
  10 //     * Redistributions in binary form must reproduce the above copyright notice,
  11 //     this list of conditions and the following disclaimer in the documentation
  12 //     and/or other materials provided with the distribution.
  13 //     * Neither the name of Rodrigo B. de Oliveira nor the names of its
  14 //     contributors may be used to endorse or promote products derived from this
  15 //     software without specific prior written permission.
  16 //
  17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  18 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  19 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  20 // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
  21 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  23 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  24 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  25 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27 #endregion
  28
  29 using System;
  30
  31 using Boo.Lang.Compiler.Ast;
  32
  33 namespace Boo.Lang.Compiler.TypeSystem
  34 {
  35         /// <summary>
  36         /// Overload resolution service.
  37         /// </summary>
  38         public class CallableResolutionService : AbstractCompilerComponent
  39         {
  40                 private const int CallableExactMatchScore = 10;
  41                 private const int CallableUpCastScore = 9;
  42                 private const int CallableImplicitConversionScore = 8;
  43                 private const int ExactMatchScore = 8;
  44                 private const int UpCastScore = 7;
  45                 private const int WideningPromotion = 6;
  46                 private const int ImplicitConversionScore = 5;
  47                 private const int NarrowingPromotion = 4;
  48                 private const int DowncastScore = 3;
  49
  50                 private List _candidates = new List();
  51                 private ExpressionCollection _arguments;
  52
  53                 private Expression GetArgument(int index)
  54                 {
  55                         return _arguments[index];
  56                 }
  57
  58                 public List ValidCandidates
  59                 {
  60                         get { return _candidates; }
  61                 }
  62
  63                 public override void Dispose()
  64                 {
  65                         _candidates.Clear();
  66                         base.Dispose();
  67                 }
  68
  69                 public class Candidate
  70                 {
  71                         public IMethod Method;
  72                         private CallableResolutionService _crs;
  73                         int[] _scores = null;
  74                         bool _expanded = false;
  75
  76                         public Candidate(CallableResolutionService crs, IMethod entity)
  77                         {
  78                                 _crs = crs;
  79                                 Method = entity;
  80                                 _scores = new int[crs._arguments.Count];
  81                         }
  82
  83                         public IParameter[] Parameters
  84                         {
  85                                 get { return Method.GetParameters();  }
  86                         }
  87
  88                         public int[] ArgumentScores
  89                         {
  90                                 get
  91                                 {
  92                                         return _scores;
  93                                 }
  94                         }
  95
  96                         public bool Expanded
  97                         {
  98                                 get { return _expanded; }
  99                                 set { _expanded = value; }
 100                         }
 101
 102                         public int Score(int argumentIndex)
 103                         {
 104                                 _scores[argumentIndex] = _crs.CalculateArgumentScore(
 105                                         Parameters[argumentIndex],
 106                                         Parameters[argumentIndex].Type,
 107                                         _crs.GetArgument(argumentIndex));
 108
 109                                 return _scores[argumentIndex];
 110                         }
 111
 112                         public int ScoreVarArgs(int argumentIndex)
 113                         {
 114                                 IParameter parameter = Parameters[Parameters.Length-1];
 115                                 _scores[argumentIndex] = _crs.CalculateArgumentScore(
 116                                         parameter,
 117                                         parameter.Type.GetElementType(),
 118                                         _crs.GetArgument(argumentIndex));
 119
 120                                 return _scores[argumentIndex];
 121                         }
 122
 123                         override public int GetHashCode()
 124                         {
 125                                 return Method.GetHashCode();
 126                         }
 127
 128                         override public bool Equals(object other)
 129                         {
 130                                 Candidate score = other as Candidate;
 131                                 return null == score
 132                                         ? false
 133                                         : Method == score.Method;
 134                         }
 135
 136                         override public string ToString()
 137                         {
 138                                 return Method.ToString();
 139                         }
 140                 }
 141
 142                 public int GetLogicalTypeDepth(IType type)
 143                 {
 144                         int depth = type.GetTypeDepth();
 145                         if (type.IsValueType) return depth - 1;
 146                         return depth;
 147                 }
 148
 149                 IType GetExpressionTypeOrEntityType(Node node)
 150                 {
 151                         Expression e = node as Expression;
 152                         return null != e
 153                                 ? TypeSystemServices.GetExpressionType(e)
 154                                 : TypeSystem.TypeSystemServices.GetType(node);
 155                 }
 156
 157                 public bool IsValidByRefArg(IParameter param, IType parameterType, IType argType, Node arg)
 158                 {
 159                         if ((parameterType.IsByRef &&
 160                                 argType == parameterType.GetElementType()))
 161                         {
 162                                 return CanLoadAddress(arg);
 163                         }
 164                         else if (param.IsByRef &&
 165                                 argType == parameterType)
 166                         {
 167                                 return CanLoadAddress(arg);
 168                         }
 169                         return false;
 170                 }
 171
 172                 static bool CanLoadAddress(Node node)
 173                 {
 174                         IEntity entity = node.Entity;
 175
 176                         if (null == entity) return true;
 177
 178                         switch (entity.EntityType)
 179                         {
 180                                 case EntityType.Local:
 181                                 {
 182                                         return !((InternalLocal)entity).IsPrivateScope;
 183                                 }
 184
 185                                 case EntityType.Parameter:
 186                                 {
 187                                         return true;
 188                                 }
 189
 190                                 case EntityType.Field:
 191                                 {
 192                                         return !TypeSystemServices.IsReadOnlyField((IField)entity);
 193                                 }
 194                         }
 195                         return false;
 196                 }
 197
 198                 public IEntity ResolveCallableReference(ExpressionCollection args, IEntity[] candidates)
 199                 {
 200                         Reset(args);
 201                         FindApplicableCandidates(candidates);
 202                         if (ValidCandidates.Count == 0) return null;
 203                         if (ValidCandidates.Count == 1) return ((Candidate)ValidCandidates[0]).Method;
 204
 205                         List dataPreserving = ValidCandidates.Collect(DoesNotRequireConversions);
 206                         if (dataPreserving.Count > 0)
 207                         {
 208                                 if (dataPreserving.Count == 1) return ((Candidate)dataPreserving[0]).Method;
 209                                 IEntity found = BestMethod(dataPreserving);
 210                                 if (null != found) return found;
 211                         }
 212                         return BestCandidate();
 213                 }
 214
 215                 private static bool DoesNotRequireConversions(object candidate)
 216                 {
 217                         return !Array.Exists(((Candidate) candidate).ArgumentScores, RequiresConversion);
 218                 }
 219
 220                 private static bool RequiresConversion(int score)
 221                 {
 222                         return score < WideningPromotion;
 223                 }
 224
 225                 private IEntity BestCandidate()
 226                 {
 227                         return BestMethod(_candidates);
 228                 }
 229
 230                 private IEntity BestMethod(List candidates)
 231                 {
 232                         candidates.Sort(new Comparer(BetterCandidate));
 233
 234                         if (BetterCandidate(candidates[-1], candidates[-2]) == 0)
 235                         {
 236                                 object pivot = candidates[-2];
 237
 238                                 candidates.RemoveAll(delegate(object item)
 239                                                         {
 240                                                                 return 0 != BetterCandidate(item, pivot);
 241                                                         });
 242                                 // Ambiguous match
 243                                 return null;
 244                         }
 245
 246                         // SUCCESS: _candidates[-1] is the winner
 247                         return ((Candidate)candidates[-1]).Method;
 248                 }
 249
 250                 private int BetterCandidate(object lhs, object rhs)
 251                 {
 252                         return BetterCandidate((Candidate) lhs, (Candidate) rhs);
 253                 }
 254
 255                 private bool ApplicableCandidate(Candidate candidate)
 256                 {
 257                         // Figure out whether method should be varargs-expanded
 258                         bool expand =
 259                                 candidate.Method.AcceptVarArgs &&
 260                                 (_arguments.Count == 0 || (_arguments.Count > 0 &&
 261                                 !AstUtil.IsExplodeExpression(_arguments[-1])));
 262
 263                         // Determine number of fixed (non-varargs) parameters
 264                         int fixedParams =
 265                                 (expand ? candidate.Parameters.Length - 1 : candidate.Parameters.Length);
 266
 267                         // Validate number of parameters against number of arguments
 268                         if (_arguments.Count < fixedParams) return false;
 269                         if (_arguments.Count > fixedParams && !expand) return false;
 270
 271                         // Score each argument against a fixed parameter
 272                         for (int i = 0; i < fixedParams; i++)
 273                         {
 274                                 if (candidate.Score(i) < 0)
 275                                 {
 276                                         return false;
 277                                 }
 278                         }
 279
 280                         // If method should be expanded, match remaining arguments against
 281                         // last parameter
 282                         if (expand)
 283                         {
 284                                 candidate.Expanded = true;
 285                                 for (int i = fixedParams; i < _arguments.Count; i++)
 286                                 {
 287                                         if (candidate.ScoreVarArgs(i) < 0)
 288                                         {
 289                                                 return false;
 290                                         }
 291                                 }
 292                         }
 293
 294                         return true;
 295                 }
 296
 297                 private int TotalScore(Candidate c1)
 298                 {
 299                         int total = 0;
 300                         foreach (int score in c1.ArgumentScores)
 301                         {
 302                                 total += score;
 303                         }
 304                         return total;
 305                 }
 306
 307                 private int BetterCandidate(Candidate c1, Candidate c2)
 308                 {
 309                         int result = Math.Sign(TotalScore(c1) - TotalScore(c2));
 310 //                      int result = 0;
 311                         /*
 312                         if (false)
 313                         {
 314                                 for (int i = 0; i < _arguments.Count; i++)
 315                                 {
 316                                         // Compare methods based on their score for the current argument
 317                                         int better = Math.Sign(c1.ArgumentScores[i] - c2.ArgumentScores[i]);
 318                                         if (better == 0) continue;
 319
 320                                         // If neither method has been selecteed yet, select one
 321                                         // based on this argument
 322                                         if (result == 0)
 323                                         {
 324                                                 result = better;
 325                                         }
 326                                                 // If this argument comparison is in conflict with previous selection,
 327                                                 // neither method is better
 328                                         else if (result != better)
 329                                         {
 330                                                 return 0;
 331                                         }
 332                                 }
 333                         }
 334                         */
 335
 336                         if (result != 0)
 337                         {
 338                                 return result;
 339                         }
 340
 341                         result = c1.Method.DeclaringType.GetTypeDepth() - c2.Method.DeclaringType.GetTypeDepth();
 342                         if (result != 0)
 343                         {
 344                                 return result;
 345                         }
 346
 347                         // --- Tie breaking mode! ---
 348
 349                         // Non-generic methods are better than generic ones
 350
 351                         // Commented out since current syntax distinguishes between invoking
 352                         // a generic method and a non generic one
 353                         /*
 354                         IGenericMethodInfo generic1 = c1.Method.GenericMethodInfo;
 355                         IGenericMethodInfo generic2 = c2.Method.GenericMethodInfo;
 356                         if (generic1 == null && generic2 != null)
 357                         {
 358                                 return 1;
 359                         }
 360                         else if (generic1 != null && generic2 == null)
 361                         {
 362                                 return -1;
 363                         }
 364                         */
 365
 366                         // Non-expanded methods are better than expanded ones
 367                         if (!c1.Expanded && c2.Expanded)
 368                         {
 369                                 return 1;
 370                         }
 371                         else if (c1.Expanded && !c2.Expanded)
 372                         {
 373                                 return -1;
 374                         }
 375
 376                         // An expanded method with more fixed parameters is better
 377                         result = c1.Parameters.Length - c2.Parameters.Length;
 378                         if (result != 0) return result;
 379
 380                         // As a last means of breaking this desparate tie, we select the
 381                         // "more specific" candidate, if one exists
 382                         return MoreSpecific(c1, c2);
 383                 }
 384
 385                 private int MoreSpecific(Candidate c1, Candidate c2)
 386                 {
 387                         int result = 0;
 388                         for (int i = 0; i < _arguments.Count && i < c1.Parameters.Length; ++i)
 389                         {
 390                                 if (c1.ArgumentScores[i] <= DowncastScore) continue;
 391
 392                                 // Select the most specific of the parameters' types,
 393                                 // taking into account generic mapped parameters
 394                                 int better = MoreSpecific(
 395                                         GetParameterTypeTemplate(c1, i),
 396                                         GetParameterTypeTemplate(c2, i));
 397
 398                                 // Skip parameters that are the same for both candidates
 399                                 if (better == 0)
 400                                 {
 401                                         continue;
 402                                 }
 403
 404                                 // Keep the first result that is not a tie
 405                                 if (result == 0)
 406                                 {
 407                                         result = better;
 408                                 }
 409                                 // If a further result contradicts the initial result, neither candidate is more specific
 410                                 else if (result != better)
 411                                 {
 412                                         return 0;
 413                                 }
 414                         }
 415                         return result;
 416                 }
 417
 418                 private IType GetParameterTypeTemplate(Candidate candidate, int position)
 419                 {
 420                         // Get the method this candidate represents, or its generic template
 421                         IMethod method = candidate.Method;
 422                         if (candidate.Method.DeclaringType.ConstructedInfo != null)
 423                         {
 424                                 method = candidate.Method.DeclaringType.ConstructedInfo.GetMethodTemplate(method);
 425                         }
 426
 427                         // If the parameter is the varargs parameter, use its element type
 428                         IParameter[] parameters = method.GetParameters();
 429                         if (candidate.Expanded && position >= parameters.Length)
 430                         {
 431                                 return parameters[parameters.Length - 1].Type.GetElementType();
 432                         }
 433
 434                         // Otherwise use the parameter's original type
 435                         return parameters[position].Type;
 436                 }
 437
 438                 private int MoreSpecific(IType t1, IType t2)
 439                 {
 440                         // Dive into array types and ref types
 441                         if (t1.IsArray && t2.IsArray || t1.IsByRef && t2.IsByRef)
 442                         {
 443                                 return MoreSpecific(t1.GetElementType(), t2.GetElementType());
 444                         }
 445
 446                         // The less-generic type is more specific
 447                         int result = GenericsServices.GetTypeGenerity(t2) - GenericsServices.GetTypeGenerity(t1);
 448                         if (result != 0) return result;
 449
 450                         // If both types have the same genrity, the deeper-nested type is more specific
 451                         return GetLogicalTypeDepth(t1) - GetLogicalTypeDepth(t2);
 452                 }
 453
 454                 private void FindApplicableCandidates(IEntity[] candidates)
 455                 {
 456                         foreach (IEntity entity in candidates)
 457                         {
 458                                 IMethod method = entity as IMethod;
 459                                 if (null == method) continue;
 460
 461                                 Candidate candidate = new Candidate(this, method);
 462
 463                                 if (!ApplicableCandidate(candidate)) continue;
 464
 465                                 _candidates.Add(candidate);
 466                         }
 467                 }
 468
 469                 private void Reset(ExpressionCollection arguments)
 470                 {
 471                         _arguments = arguments;
 472                         _candidates.Clear();
 473                 }
 474
 475                 public bool IsValidVargsInvocation(IParameter[] parameters, ExpressionCollection args)
 476                 {
 477                         int lastIndex = parameters.Length - 1;
 478                         if (args.Count < lastIndex) return false;
 479
 480                         IType lastParameterType = parameters[lastIndex].Type;
 481                         if (!lastParameterType.IsArray) return false;
 482
 483                         if (!IsValidInvocation(parameters, args, lastIndex)) return false;
 484
 485                         if (args.Count > 0)
 486                         {
 487                                 Node lastArg = args[-1];
 488                                 if (AstUtil.IsExplodeExpression(lastArg))
 489                                 {
 490                                         return CalculateArgumentScore(parameters[lastIndex], lastParameterType, lastArg) > 0;
 491                                 }
 492                                 else
 493                                 {
 494                                         IType varArgType = lastParameterType.GetElementType();
 495                                         for (int i = lastIndex; i < args.Count; ++i)
 496                                         {
 497                                                 int argumentScore = CalculateArgumentScore(parameters[lastIndex], varArgType, args[i]);
 498                                                 if (argumentScore < 0) return false;
 499                                         }
 500                                 }
 501                         }
 502                         return true;
 503                 }
 504
 505                 private bool IsValidInvocation(IParameter[] parameters, ExpressionCollection args, int count)
 506                 {
 507                         for (int i = 0; i < count; ++i)
 508                         {
 509                                 IParameter parameter = parameters[i];
 510                                 IType parameterType = parameter.Type;
 511                                 int argumentScore = CalculateArgumentScore(parameter, parameterType, args[i]);
 512                                 if (argumentScore < 0) return false;
 513                         }
 514                         return true;
 515                 }
 516
 517
 518                 private int CalculateArgumentScore(IParameter param, IType parameterType, Node arg)
 519                 {
 520                         IType argumentType = GetExpressionTypeOrEntityType(arg);
 521                         if (param.IsByRef)
 522                         {
 523                                 if (IsValidByRefArg(param, parameterType, argumentType, arg))
 524                                 {
 525                                         return ExactMatchScore;
 526                                 }
 527                                 return -1;
 528                         }
 529                         else if (parameterType == argumentType
 530                                 || (TypeSystemServices.IsSystemObject(argumentType) &&
 531                                         TypeSystemServices.IsSystemObject(parameterType)))
 532                         {
 533                                 return parameterType is ICallableType
 534                                         ? CallableExactMatchScore
 535                                         : ExactMatchScore;
 536                         }
 537                         else if (parameterType.IsAssignableFrom(argumentType))
 538                         {
 539                                 ICallableType callableType = parameterType as ICallableType;
 540                                 ICallableType callableArg = argumentType as ICallableType;
 541                                 if (callableType != null && callableArg != null)
 542                                 {
 543                                         return CalculateCallableScore(callableType, callableArg);
 544                                 }
 545                                 return UpCastScore;
 546                         }
 547                         else if (TypeSystemServices.FindImplicitConversionOperator(argumentType, parameterType) != null)
 548                         {
 549                                 return ImplicitConversionScore;
 550                         }
 551                         else if (TypeSystemServices.CanBeReachedByPromotion(parameterType, argumentType))
 552                         {
 553                                 if (IsWideningPromotion(parameterType, argumentType)) return WideningPromotion;
 554                                 return NarrowingPromotion;
 555                         }
 556                         else if (TypeSystemServices.CanBeReachedByDowncast(parameterType, argumentType))
 557                         {
 558                                 return DowncastScore;
 559                         }
 560                         return -1;
 561                 }
 562
 563                 private bool IsWideningPromotion(IType paramType, IType argumentType)
 564                 {
 565                         ExternalType expected = paramType as ExternalType;
 566                         if (null == expected) return false;
 567                         ExternalType actual = argumentType as ExternalType;
 568                         if (null == actual) return false;
 569                         return Boo.Lang.Runtime.NumericTypes.IsWideningPromotion(expected.ActualType, actual.ActualType);
 570                 }
 571
 572                 private static int CalculateCallableScore(ICallableType parameterType, ICallableType argType)
 573                 {
 574                         // upcast
 575                         // parameterType == ICallableType, "ThreadStart"
 576                         // argumentType == ICallableType, "Anonymous Closure"
 577                         // RULES:
 578                         // Number of arguments for argumentType && parameterType == same
 579                         // Either: all arguments "IsAssignableFrom"
 580                         //                      OR
 581                         //                      all arguments == exactly (best case scenario)
 582                         // ExactMatch -- (best case)
 583                         // UpCast -- "not exact match, but very close" (this is OK)
 584                         // ImplicitConversion -- "assignable, but wrong number of parameters / whatever" (boo does the normal thing)
 585
 586                         CallableSignature siggyType = parameterType.GetSignature();
 587                         CallableSignature siggyArg = argType.GetSignature();
 588                         // Ensuring that these callables have same number of arguments.
 589                         // def foo(a, b,c) == { a, b, c| print foobar }
 590                         if (siggyType.Parameters.Length != siggyArg.Parameters.Length)
 591                         {
 592                                 return CallableUpCastScore;
 593                         }
 594                         for (int i = 0; i < siggyType.Parameters.Length; i++)
 595                         {
 596                                 if (siggyType.Parameters[i].Type != siggyArg.Parameters[i].Type)
 597                                 {
 598                                         return CallableImplicitConversionScore;
 599                                 }
 600                         }
 601                         return siggyType.ReturnType == siggyArg.ReturnType
 602                                 ? CallableExactMatchScore : CallableUpCastScore;
 603                 }
 604         }
 605 }