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

   1 #region license
   2 // Copyright (c) 2004, 2005, 2006, 2007 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 Boo.Lang.Compiler.Ast;
  30 using System.Collections.Generic;
  31 using System;
  32
  33 namespace Boo.Lang.Compiler.TypeSystem
  34 {
  35         public class GenericsServices : AbstractCompilerComponent
  36         {
  37                 public GenericsServices(CompilerContext context)
  38                 {
  39                         Initialize(context);
  40                 }
  41
  42                 /// <summary>
  43                 /// Constructs an entity from a generic definition and arguments, after ensuring the construction is valid.
  44                 /// </summary>
  45                 /// <param name="definition">The generic definition entity.</param>
  46                 /// <param name="node">The node in which construction occurs.</param>
  47                 /// <param name="argumentNodes">The nodes of the arguments supplied for generic construction.</param>
  48                 /// <returns>The constructed entity.</returns>
  49                 public IEntity ConstructEntity(IEntity definition, Node constructionNode, TypeReferenceCollection argumentNodes)
  50                 {
  51                         // Ambiguous generic constructions are handled separately
  52                         if (definition.EntityType == EntityType.Ambiguous)
  53                         {
  54                                 return ConstructAmbiguousEntity((Ambiguous)definition, constructionNode, argumentNodes);
  55                         }
  56
  57                         // Check that the construction is valid
  58                         if (!CheckGenericConstruction(definition, constructionNode, argumentNodes, Errors))
  59                         {
  60                                 return TypeSystemServices.ErrorEntity;
  61                         }
  62
  63                         // Construct a type or a method according to the definition
  64                         IType[] arguments = Array.ConvertAll<TypeReference, IType>(
  65                                 argumentNodes.ToArray(),
  66                                 delegate(TypeReference tr) { return (IType)tr.Entity; });
  67
  68                         if (IsGenericType(definition))
  69                         {
  70                                 return ((IType)definition).GenericInfo.ConstructType(arguments);
  71                         }
  72                         if (IsGenericMethod(definition))
  73                         {
  74                                 return ((IMethod)definition).GenericInfo.ConstructMethod(arguments);
  75                         }
  76
  77                         // Should never be reached - if definition is neither a generic type nor a generic method,
  78                         // CheckGenericConstruction would've indicated this
  79                         return TypeSystemServices.ErrorEntity;
  80                 }
  81
  82                 /// <summary>
  83                 /// Constructs generic entities out of an ambiguous definition.
  84                 /// </summary>
  85                 private IEntity ConstructAmbiguousEntity(Ambiguous ambiguousDefinition, Node constructionNode, TypeReferenceCollection argumentNodes)
  86                 {
  87                         GenericConstructionChecker checker = new GenericConstructionChecker(
  88                                 TypeSystemServices,
  89                                 constructionNode,
  90                                 argumentNodes,
  91                                 new CompilerErrorCollection());
  92
  93                         List<IEntity> matches = new List<IEntity>(ambiguousDefinition.Entities);
  94
  95                         // Filter matches by genericness, generity and constraints
  96                         Predicate<IEntity>[] filters = new Predicate<IEntity>[] {
  97                                 checker.NotGenericDefinition,
  98                                 checker.IncorrectGenerity,
  99                                 checker.ViolatesParameterConstraints };
 100
 101                         foreach (Predicate<IEntity> filter in filters)
 102                         {
 103                                 checker.Errors.Clear();
 104                                 matches.RemoveAll(filter);
 105
 106                                 // If no matches pass the filter, record the first error only
 107                                 // (providing all the distinct errors that occured would be superfluous)
 108                                 if (matches.Count == 0)
 109                                 {
 110                                         Errors.Add(checker.Errors[0]);
 111                                         return TypeSystemServices.ErrorEntity;
 112                                 }
 113
 114                                 // If only one match passes the filter, continue construction normally
 115                                 if (matches.Count == 1)
 116                                 {
 117                                         return ConstructEntity(matches[0], constructionNode, argumentNodes);
 118                                 }
 119                         }
 120
 121                         // Several matches have passed the filter -
 122                         // construct all of them and return another Ambiguous entity
 123                         IEntity[] constructed = Array.ConvertAll<IEntity, IEntity>(
 124                                 matches.ToArray(),
 125                                 delegate(IEntity def) { return ConstructEntity(def, constructionNode, argumentNodes); });
 126
 127                         return new Ambiguous(constructed);
 128                 }
 129
 130                 /// <summary>
 131                 /// Checks whether a given set of arguments can be used to construct a generic type or method from a specified definition.
 132                 /// </summary>
 133                 public bool CheckGenericConstruction(IEntity definition, Node node, TypeReferenceCollection arguments, CompilerErrorCollection errors)
 134                 {
 135                         // Ensure definition is a valid entity
 136                         if (definition == null || TypeSystemServices.IsError(definition))
 137                         {
 138                                 return false;
 139                         }
 140
 141                         // Ensure definition really is a generic definition
 142                         GenericConstructionChecker checker = new GenericConstructionChecker(
 143                                 TypeSystemServices, node, arguments, Errors);
 144
 145                         return !(
 146                                 checker.NotGenericDefinition(definition) ||
 147                                 checker.IncorrectGenerity(definition) ||
 148                                 checker.ViolatesParameterConstraints(definition));
 149                 }
 150
 151                 public static bool IsGenericMethod(IEntity entity)
 152                 {
 153                         IMethod method = entity as IMethod;
 154                         return (method != null && method.GenericInfo != null);
 155                 }
 156
 157                 public static bool IsGenericType(IEntity entity)
 158                 {
 159                         IType type = entity as IType;
 160                         return (type != null && type.GenericInfo != null);
 161                 }
 162
 163                 /// <summary>
 164                 /// Finds types constructed from the specified definition in the specified type's interfaces and base types.
 165                 /// </summary>
 166                 /// <param name="type">The type in whose hierarchy to search for constructed types.</param>
 167                 /// <param name="definition">The generic type definition whose constructed versions to search for.</param>
 168                 /// <returns>Yields the matching types.</returns>
 169                 public static IEnumerable<IType> FindConstructedTypes(IType type, IType definition)
 170                 {
 171                         while (type != null)
 172                         {
 173                                 // Check if type itself is constructed from the definition
 174                                 if (type.ConstructedInfo != null &&
 175                                         type.ConstructedInfo.GenericDefinition == definition)
 176                                 {
 177                                         yield return type;
 178                                 }
 179
 180                                 // Look in type's immediate interfaces
 181                                 IType[] interfaces = type.GetInterfaces();
 182                                 if (interfaces != null)
 183                                 {
 184                                         foreach (IType interfaceType in interfaces)
 185                                         {
 186                                                 foreach (IType match in FindConstructedTypes(interfaceType, definition))
 187                                                 {
 188                                                         yield return match;
 189                                                 }
 190                                         }
 191                                 }
 192
 193                                 // Move on to the type's base type
 194                                 type = type.BaseType;
 195                         }
 196                 }
 197
 198                 /// <summary>
 199                 /// Determines whether a specified type is an open generic type -
 200                 /// that is, if it contains generic parameters.
 201                 /// </summary>
 202                 public static bool IsOpenGenericType(IType type)
 203                 {
 204                         return (GetTypeGenerity(type) != 0);
 205                 }
 206
 207                 /// <summary>
 208                 /// Gets the generic parameters associated with a generic type or generic method definition.
 209                 /// </summary>
 210                 /// <returns>An array of IGenericParameter objects, or null if the specified entity isn't a generic definition.</returns>
 211                 public static IGenericParameter[] GetGenericParameters(IEntity definition)
 212                 {
 213                         if (IsGenericType(definition))
 214                         {
 215                                 return ((IType)definition).GenericInfo.GenericParameters;
 216                         }
 217                         if (IsGenericMethod(definition))
 218                         {
 219                                 return ((IMethod)definition).GenericInfo.GenericParameters;
 220                         }
 221                         return null;
 222                 }
 223
 224                 /// <summary>
 225                 /// Determines the number of open generic parameters in the specified type.
 226                 /// </summary>
 227                 public static int GetTypeGenerity(IType type)
 228                 {
 229                         // Dive into arrays and refs
 230                         if (type.IsByRef || type.IsArray)
 231                         {
 232                                 return GetTypeGenerity(type.GetElementType());
 233                         }
 234
 235                         // A generic parameter has a generity of one
 236                         if (type is IGenericParameter)
 237                         {
 238                                 return 1;
 239                         }
 240
 241                         // Generic parameters and generic arguments both contribute
 242                         // to a types genrity
 243                         int generity = 0;
 244
 245                         // A generic type gets a generity equals to the number its type parameters
 246                         if (type.GenericInfo != null)
 247                         {
 248                                 generity += type.GenericInfo.GenericParameters.Length;
 249                         }
 250
 251                         // A constructed type gets the accumulated generity of its type arguments
 252                         if (type.ConstructedInfo != null)
 253                         {
 254                                 foreach (IType typeArg in type.ConstructedInfo.GenericArguments)
 255                                 {
 256                                         generity += GetTypeGenerity(typeArg);
 257                                 }
 258                         }
 259
 260                         return generity;
 261                 }
 262         }
 263
 264         /// <summary>
 265         /// Checks a generic construction for several kinds of errors.
 266         /// </summary>
 267         public class GenericConstructionChecker
 268         {
 269                 Node _constructionNode;
 270                 TypeReferenceCollection _argumentNodes;
 271                 CompilerErrorCollection _errors;
 272                 TypeSystemServices _tss;
 273
 274                 public GenericConstructionChecker(TypeSystemServices tss, Node constructionNode, TypeReferenceCollection argumentNodes, CompilerErrorCollection errorCollection)
 275                 {
 276                         _tss = tss;
 277                         _constructionNode = constructionNode;
 278                         _argumentNodes = argumentNodes;
 279                         _errors = errorCollection;
 280                 }
 281
 282                 public TypeReferenceCollection ArgumentNodes
 283                 {
 284                         get { return _argumentNodes; }
 285                 }
 286
 287                 public Node ConstructionNode
 288                 {
 289                         get { return _constructionNode; }
 290                 }
 291
 292                 public CompilerErrorCollection Errors
 293                 {
 294                         get { return _errors; }
 295                 }
 296
 297                 /// <summary>
 298                 /// Checks if a specified entity is not a generic definition.
 299                 /// </summary>
 300                 public bool NotGenericDefinition(IEntity entity)
 301                 {
 302                         if (!(GenericsServices.IsGenericType(entity) || GenericsServices.IsGenericMethod(entity)))
 303                         {
 304                                 Errors.Add(CompilerErrorFactory.NotAGenericDefinition(ConstructionNode, entity.FullName));
 305                                 return true;
 306                         }
 307                         return false;
 308                 }
 309
 310                 /// <summary>
 311                 /// Checks if the number of generic parameters on a specified definition
 312                 /// does not match the number of supplied type arguments.
 313                 /// </summary>
 314                 public bool IncorrectGenerity(IEntity definition)
 315                 {
 316                         int parametersCount = GenericsServices.GetGenericParameters(definition).Length;
 317                         if (parametersCount != ArgumentNodes.Count)
 318                         {
 319                                 Errors.Add(CompilerErrorFactory.GenericDefinitionArgumentCount(ConstructionNode, definition.FullName, parametersCount));
 320                                 return true;
 321                         }
 322                         return false;
 323                 }
 324
 325                 /// <summary>
 326                 /// Checks if the given type arguments violate any constraints
 327                 /// declared on the type parameters of a specified generic definition.
 328                 /// </summary>
 329                 public bool ViolatesParameterConstraints(IEntity definition)
 330                 {
 331                         IGenericParameter[] parameters = GenericsServices.GetGenericParameters(definition);
 332
 333                         bool valid = true;
 334                         for (int i = 0; i < parameters.Length; i++)
 335                         {
 336                                 if (ViolatesParameterConstraints(parameters[i], ArgumentNodes[i]))
 337                                 {
 338                                         valid = false;
 339                                 }
 340                         }
 341
 342                         return !valid;
 343                 }
 344
 345                 /// <summary>
 346                 /// Checks if a specified type argument violates the constraints
 347                 /// declared on a specified type paramter.
 348                 /// </summary>
 349                 public bool ViolatesParameterConstraints(IGenericParameter parameter, TypeReference argumentNode)
 350                 {
 351                         IType argument = TypeSystemServices.GetEntity(argumentNode) as IType;
 352
 353                         // Ensure argument is a valid type
 354                         if (argument == null || TypeSystemServices.IsError(argument))
 355                         {
 356                                 return false;
 357                         }
 358
 359                         bool valid = true;
 360
 361                         // Check type semantics constraints
 362                         if (parameter.IsClass && !argument.IsClass)
 363                         {
 364                                 Errors.Add(CompilerErrorFactory.GenericArgumentMustBeReferenceType(ConstructionNode, parameter, argument));
 365                                 valid = false;
 366                         }
 367
 368                         if (parameter.IsValueType && !argument.IsValueType)
 369                         {
 370                                 Errors.Add(CompilerErrorFactory.GenericArgumentMustBeValueType(argumentNode, parameter, argument));
 371                                 valid = false;
 372                         }
 373
 374                         if (parameter.MustHaveDefaultConstructor && !HasDefaultConstructor(argument))
 375                         {
 376                                 Errors.Add(CompilerErrorFactory.GenericArgumentMustHaveDefaultConstructor(argumentNode, parameter, argument));
 377                                 valid = false;
 378                         }
 379
 380                         // Check base type constraints
 381                         IType[] baseTypes = parameter.GetBaseTypeConstraints();
 382                         if (baseTypes != null)
 383                         {
 384                                 foreach (IType baseType in baseTypes)
 385                                 {
 386                                         // Don't check for System.ValueType supertype constraint
 387                                         // if parameter also has explicit value type constraint
 388                                         if (baseType == _tss.ValueTypeType && parameter.IsValueType)
 389                                                 continue;
 390
 391                                         if (!baseType.IsAssignableFrom(argument))
 392                                         {
 393                                                 Errors.Add(CompilerErrorFactory.GenericArgumentMustHaveBaseType(argumentNode, parameter, argument, baseType));
 394                                                 valid = false;
 395                                         }
 396                                 }
 397                         }
 398
 399                         return !valid;
 400                 }
 401
 402                 /// <summary>
 403                 /// Checks whether a given type has a default (parameterless) consructor.
 404                 /// </summary>
 405                 private static bool HasDefaultConstructor(IType argument)
 406                 {
 407                         if (argument.IsValueType)
 408                         {
 409                                 return true;
 410                         }
 411
 412                         IConstructor[] constructors = argument.GetConstructors();
 413                         foreach (IConstructor ctor in constructors)
 414                         {
 415                                 if (ctor.GetParameters().Length == 0)
 416                                 {
 417                                         return true;
 418                                 }
 419                         }
 420
 421                         return false;
 422                 }
 423
 424         }
 425 }