mcs/mcs/generic.cs

   1 //
   2 // generic.cs: Generics support
   3 //
   4 // Authors: Martin Baulig (martin@ximian.com)
   5 //          Miguel de Icaza (miguel@ximian.com)
   6 //          Marek Safar (marek.safar@gmail.com)
   7 //
   8 // Dual licensed under the terms of the MIT X11 or GNU GPL
   9 //
  10 // Copyright 2001, 2002, 2003 Ximian, Inc (http://www.ximian.com)
  11 // Copyright 2004-2008 Novell, Inc
  12 //
  13 using System;
  14 using System.Reflection;
  15 using System.Reflection.Emit;
  16 using System.Globalization;
  17 using System.Collections.Generic;
  18 using System.Text;
  19 using System.Linq;
  20
  21 namespace Mono.CSharp {
  22         public enum Variance
  23         {
  24                 //
  25                 // Don't add or modify internal values, they are used as -/+ calculation signs
  26                 //
  27                 None                    = 0,
  28                 Covariant               = 1,
  29                 Contravariant   = -1
  30         }
  31
  32         [Flags]
  33         public enum SpecialConstraint
  34         {
  35                 None            = 0,
  36                 Constructor = 1 << 2,
  37                 Class           = 1 << 3,
  38                 Struct          = 1 << 4
  39         }
  40
  41         public class SpecialContraintExpr : FullNamedExpression
  42         {
  43                 public SpecialContraintExpr (SpecialConstraint constraint, Location loc)
  44                 {
  45                         this.loc = loc;
  46                         this.Constraint = constraint;
  47                 }
  48
  49                 public SpecialConstraint Constraint { get; private set; }
  50
  51                 protected override Expression DoResolve (ResolveContext rc)
  52                 {
  53                         throw new NotImplementedException ();
  54                 }
  55         }
  56
  57         //
  58         // A set of parsed constraints for a type parameter
  59         //
  60         public class Constraints
  61         {
  62                 SimpleMemberName tparam;
  63                 List<FullNamedExpression> constraints;
  64                 Location loc;
  65                 bool resolved;
  66                 bool resolving;
  67
  68                 public Constraints (SimpleMemberName tparam, List<FullNamedExpression> constraints, Location loc)
  69                 {
  70                         this.tparam = tparam;
  71                         this.constraints = constraints;
  72                         this.loc = loc;
  73                 }
  74
  75                 #region Properties
  76
  77                 public Location Location {
  78                         get {
  79                                 return loc;
  80                         }
  81                 }
  82
  83                 public SimpleMemberName TypeParameter {
  84                         get {
  85                                 return tparam;
  86                         }
  87                 }
  88
  89                 #endregion
  90
  91                 public static bool CheckConflictingInheritedConstraint (TypeParameterSpec spec, TypeSpec bb, IMemberContext context, Location loc)
  92                 {
  93                         if (spec.HasSpecialClass && bb.IsStruct) {
  94                                 context.Compiler.Report.Error (455, loc,
  95                                         "Type parameter `{0}' inherits conflicting constraints `{1}' and `{2}'",
  96                                         spec.Name, "class", bb.GetSignatureForError ());
  97
  98                                 return false;
  99                         }
 100
 101                         return CheckConflictingInheritedConstraint (spec, spec.BaseType, bb, context, loc);
 102                 }
 103
 104                 static bool CheckConflictingInheritedConstraint (TypeParameterSpec spec, TypeSpec ba, TypeSpec bb, IMemberContext context, Location loc)
 105                 {
 106                         if (ba == bb)
 107                                 return true;
 108
 109                         if (TypeSpec.IsBaseClass (ba, bb, false) || TypeSpec.IsBaseClass (bb, ba, false))
 110                                 return true;
 111
 112                         context.Compiler.Report.Error (455, loc,
 113                                 "Type parameter `{0}' inherits conflicting constraints `{1}' and `{2}'",
 114                                 spec.Name, ba.GetSignatureForError (), bb.GetSignatureForError ());
 115                         return false;
 116                 }
 117
 118                 public void CheckGenericConstraints (IMemberContext context)
 119                 {
 120                         foreach (var c in constraints) {
 121                                 var ge = c as GenericTypeExpr;
 122                                 if (ge != null)
 123                                         ge.CheckConstraints (context);
 124                         }
 125                 }
 126
 127                 //
 128                 // Resolve the constraints types with only possible early checks, return
 129                 // value `false' is reserved for recursive failure
 130                 //
 131                 public bool Resolve (IMemberContext context, TypeParameter tp)
 132                 {
 133                         if (resolved)
 134                                 return true;
 135
 136                         if (resolving)
 137                                 return false;
 138
 139                         resolving = true;
 140                         var spec = tp.Type;
 141                         List<TypeParameterSpec> tparam_types = null;
 142                         bool iface_found = false;
 143
 144                         spec.BaseType = TypeManager.object_type;
 145
 146                         for (int i = 0; i < constraints.Count; ++i) {
 147                                 var constraint = constraints[i];
 148
 149                                 if (constraint is SpecialContraintExpr) {
 150                                         spec.SpecialConstraint |= ((SpecialContraintExpr) constraint).Constraint;
 151                                         if (spec.HasSpecialStruct)
 152                                                 spec.BaseType = TypeManager.value_type;
 153
 154                                         // Set to null as it does not have a type
 155                                         constraints[i] = null;
 156                                         continue;
 157                                 }
 158
 159                                 var type_expr = constraints[i] = constraint.ResolveAsTypeTerminal (context, false);
 160                                 if (type_expr == null)
 161                                         continue;
 162
 163                                 var gexpr = type_expr as GenericTypeExpr;
 164                                 if (gexpr != null && gexpr.HasDynamicArguments ()) {
 165                                         context.Compiler.Report.Error (1968, constraint.Location,
 166                                                 "A constraint cannot be the dynamic type `{0}'", gexpr.GetSignatureForError ());
 167                                         continue;
 168                                 }
 169
 170                                 var type = type_expr.Type;
 171
 172                                 if (!context.CurrentMemberDefinition.IsAccessibleAs (type)) {
 173                                         context.Compiler.Report.SymbolRelatedToPreviousError (type);
 174                                         context.Compiler.Report.Error (703, loc,
 175                                                 "Inconsistent accessibility: constraint type `{0}' is less accessible than `{1}'",
 176                                                 type.GetSignatureForError (), context.GetSignatureForError ());
 177                                 }
 178
 179                                 if (type.IsInterface) {
 180                                         if (!spec.AddInterface (type)) {
 181                                                 context.Compiler.Report.Error (405, constraint.Location,
 182                                                         "Duplicate constraint `{0}' for type parameter `{1}'", type.GetSignatureForError (), tparam.Value);
 183                                         }
 184
 185                                         iface_found = true;
 186                                         continue;
 187                                 }
 188
 189
 190                                 var constraint_tp = type as TypeParameterSpec;
 191                                 if (constraint_tp != null) {
 192                                         if (tparam_types == null) {
 193                                                 tparam_types = new List<TypeParameterSpec> (2);
 194                                         } else if (tparam_types.Contains (constraint_tp)) {
 195                                                 context.Compiler.Report.Error (405, constraint.Location,
 196                                                         "Duplicate constraint `{0}' for type parameter `{1}'", type.GetSignatureForError (), tparam.Value);
 197                                                 continue;
 198                                         }
 199
 200                                         //
 201                                         // Checks whether each generic method parameter constraint type
 202                                         // is valid with respect to T
 203                                         //
 204                                         if (tp.IsMethodTypeParameter) {
 205                                                 TypeManager.CheckTypeVariance (type, Variance.Contravariant, context);
 206                                         }
 207
 208                                         var tp_def = constraint_tp.MemberDefinition as TypeParameter;
 209                                         if (tp_def != null && !tp_def.ResolveConstraints (context)) {
 210                                                 context.Compiler.Report.Error (454, constraint.Location,
 211                                                         "Circular constraint dependency involving `{0}' and `{1}'",
 212                                                         constraint_tp.GetSignatureForError (), tp.GetSignatureForError ());
 213                                                 continue;
 214                                         }
 215
 216                                         //
 217                                         // Checks whether there are no conflicts between type parameter constraints
 218                                         //
 219                                         // class Foo<T, U>
 220                                         //      where T : A
 221                                         //      where U : B, T
 222                                         //
 223                                         // A and B are not convertible and only 1 class constraint is allowed
 224                                         //
 225                                         if (constraint_tp.HasTypeConstraint) {
 226                                                 if (spec.HasTypeConstraint || spec.HasSpecialStruct) {
 227                                                         if (!CheckConflictingInheritedConstraint (spec, constraint_tp.BaseType, context, constraint.Location))
 228                                                                 continue;
 229                                                 } else {
 230                                                         for (int ii = 0; ii < tparam_types.Count; ++ii) {
 231                                                                 if (!tparam_types[ii].HasTypeConstraint)
 232                                                                         continue;
 233
 234                                                                 if (!CheckConflictingInheritedConstraint (spec, tparam_types[ii].BaseType, constraint_tp.BaseType, context, constraint.Location))
 235                                                                         break;
 236                                                         }
 237                                                 }
 238                                         }
 239
 240                                         if (constraint_tp.HasSpecialStruct) {
 241                                                 context.Compiler.Report.Error (456, constraint.Location,
 242                                                         "Type parameter `{0}' has the `struct' constraint, so it cannot be used as a constraint for `{1}'",
 243                                                         constraint_tp.GetSignatureForError (), tp.GetSignatureForError ());
 244                                                 continue;
 245                                         }
 246
 247                                         tparam_types.Add (constraint_tp);
 248                                         continue;
 249                                 }
 250
 251                                 if (iface_found || spec.HasTypeConstraint) {
 252                                         context.Compiler.Report.Error (406, constraint.Location,
 253                                                 "The class type constraint `{0}' must be listed before any other constraints. Consider moving type constraint to the beginning of the constraint list",
 254                                                 type.GetSignatureForError ());
 255                                 }
 256
 257                                 if (spec.HasSpecialStruct || spec.HasSpecialClass) {
 258                                         context.Compiler.Report.Error (450, type_expr.Location,
 259                                                 "`{0}': cannot specify both a constraint class and the `class' or `struct' constraint",
 260                                                 type.GetSignatureForError ());
 261                                 }
 262
 263                                 if (type == InternalType.Dynamic) {
 264                                         context.Compiler.Report.Error (1967, constraint.Location, "A constraint cannot be the dynamic type");
 265                                         continue;
 266                                 }
 267
 268                                 if (type.IsSealed || !type.IsClass) {
 269                                         context.Compiler.Report.Error (701, loc,
 270                                                 "`{0}' is not a valid constraint. A constraint must be an interface, a non-sealed class or a type parameter",
 271                                                 TypeManager.CSharpName (type));
 272                                         continue;
 273                                 }
 274
 275                                 if (type.IsStatic) {
 276                                         context.Compiler.Report.Error (717, constraint.Location,
 277                                                 "`{0}' is not a valid constraint. Static classes cannot be used as constraints",
 278                                                 type.GetSignatureForError ());
 279                                 } else if (type == TypeManager.array_type || type == TypeManager.delegate_type ||
 280                                                         type == TypeManager.enum_type || type == TypeManager.value_type ||
 281                                                         type == TypeManager.object_type || type == TypeManager.multicast_delegate_type) {
 282                                         context.Compiler.Report.Error (702, constraint.Location,
 283                                                 "A constraint cannot be special class `{0}'", type.GetSignatureForError ());
 284                                         continue;
 285                                 }
 286
 287                                 spec.BaseType = type;
 288                         }
 289
 290                         if (tparam_types != null)
 291                                 spec.TypeArguments = tparam_types.ToArray ();
 292
 293                         resolving = false;
 294                         resolved = true;
 295                         return true;
 296                 }
 297
 298                 public void VerifyClsCompliance (Report report)
 299                 {
 300                         foreach (var c in constraints)
 301                         {
 302                                 if (c == null)
 303                                         continue;
 304
 305                                 if (!c.Type.IsCLSCompliant ()) {
 306                                         report.SymbolRelatedToPreviousError (c.Type);
 307                                         report.Warning (3024, 1, loc, "Constraint type `{0}' is not CLS-compliant",
 308                                                 c.Type.GetSignatureForError ());
 309                                 }
 310                         }
 311                 }
 312         }
 313
 314         //
 315         // A type parameter for a generic type or generic method definition
 316         //
 317         public class TypeParameter : MemberCore, ITypeDefinition
 318         {
 319                 static readonly string[] attribute_target = new string [] { "type parameter" };
 320
 321                 Constraints constraints;
 322                 GenericTypeParameterBuilder builder;
 323                 TypeParameterSpec spec;
 324
 325                 public TypeParameter (DeclSpace parent, int index, MemberName name, Constraints constraints, Attributes attrs, Variance variance)
 326                         : base (parent, name, attrs)
 327                 {
 328                         this.constraints = constraints;
 329                         this.spec = new TypeParameterSpec (null, index, this, SpecialConstraint.None, variance, null);
 330                 }
 331
 332                 public TypeParameter (TypeParameterSpec spec, DeclSpace parent, TypeSpec parentSpec, MemberName name, Attributes attrs)
 333                         : base (parent, name, attrs)
 334                 {
 335                         this.spec = new TypeParameterSpec (parentSpec, spec.DeclaredPosition, spec.MemberDefinition, spec.SpecialConstraint, spec.Variance, null) {
 336                                 BaseType = spec.BaseType,
 337                                 InterfacesDefined = spec.InterfacesDefined,
 338                                 TypeArguments = spec.TypeArguments
 339                         };
 340                 }
 341
 342                 #region Properties
 343
 344                 public override AttributeTargets AttributeTargets {
 345                         get {
 346                                 return AttributeTargets.GenericParameter;
 347                         }
 348                 }
 349
 350                 public override string DocCommentHeader {
 351                         get {
 352                                 throw new InvalidOperationException (
 353                                         "Unexpected attempt to get doc comment from " + this.GetType ());
 354                         }
 355                 }
 356
 357                 public bool IsMethodTypeParameter {
 358                         get {
 359                                 return spec.IsMethodOwned;
 360                         }
 361                 }
 362
 363                 public string Namespace {
 364                         get {
 365                                 return null;
 366                         }
 367                 }
 368
 369                 public TypeParameterSpec Type {
 370                         get {
 371                                 return spec;
 372                         }
 373                 }
 374
 375                 public int TypeParametersCount {
 376                         get {
 377                                 return 0;
 378                         }
 379                 }
 380
 381                 public TypeParameterSpec[] TypeParameters {
 382                         get {
 383                                 return null;
 384                         }
 385                 }
 386
 387                 public override string[] ValidAttributeTargets {
 388                         get {
 389                                 return attribute_target;
 390                         }
 391                 }
 392
 393                 public Variance Variance {
 394                         get {
 395                                 return spec.Variance;
 396                         }
 397                 }
 398
 399                 #endregion
 400
 401                 //
 402                 // This is called for each part of a partial generic type definition.
 403                 //
 404                 // If partial type parameters constraints are not null and we don't
 405                 // already have constraints they become our constraints. If we already
 406                 // have constraints, we must check that they're the same.
 407                 //
 408                 public bool AddPartialConstraints (TypeContainer part, TypeParameter tp)
 409                 {
 410                         if (builder == null)
 411                                 throw new InvalidOperationException ();
 412
 413                         var new_constraints = tp.constraints;
 414                         if (new_constraints == null)
 415                                 return true;
 416
 417                         // TODO: could create spec only
 418                         //tp.Define (null, -1, part.Definition);
 419                         tp.spec.DeclaringType = part.Definition;
 420                         if (!tp.ResolveConstraints (part))
 421                                 return false;
 422
 423                         if (constraints != null)
 424                                 return spec.HasSameConstraintsDefinition (tp.Type);
 425
 426                         // Copy constraint from resolved part to partial container
 427                         spec.SpecialConstraint = tp.spec.SpecialConstraint;
 428                         spec.InterfacesDefined = tp.spec.InterfacesDefined;
 429                         spec.TypeArguments = tp.spec.TypeArguments;
 430                         spec.BaseType = tp.spec.BaseType;
 431
 432                         return true;
 433                 }
 434
 435                 public override void ApplyAttributeBuilder (Attribute a, MethodSpec ctor, byte[] cdata, PredefinedAttributes pa)
 436                 {
 437                         builder.SetCustomAttribute ((ConstructorInfo) ctor.GetMetaInfo (), cdata);
 438                 }
 439
 440                 public void CheckGenericConstraints ()
 441                 {
 442                         if (constraints != null)
 443                                 constraints.CheckGenericConstraints (this);
 444                 }
 445
 446                 public TypeParameter CreateHoistedCopy (TypeContainer declaringType, TypeSpec declaringSpec)
 447                 {
 448                         return new TypeParameter (spec, declaringType, declaringSpec, MemberName, null);
 449                 }
 450
 451                 public override bool Define ()
 452                 {
 453                         return true;
 454                 }
 455
 456                 //
 457                 // This is the first method which is called during the resolving
 458                 // process; we're called immediately after creating the type parameters
 459                 // with SRE (by calling `DefineGenericParameters()' on the TypeBuilder /
 460                 // MethodBuilder).
 461                 //
 462                 public void Define (GenericTypeParameterBuilder type, TypeSpec declaringType)
 463                 {
 464                         if (builder != null)
 465                                 throw new InternalErrorException ();
 466
 467                         this.builder = type;
 468                         spec.DeclaringType = declaringType;
 469                         spec.SetMetaInfo (type);
 470                 }
 471
 472                 public void EmitConstraints (GenericTypeParameterBuilder builder)
 473                 {
 474                         var attr = GenericParameterAttributes.None;
 475                         if (spec.Variance == Variance.Contravariant)
 476                                 attr |= GenericParameterAttributes.Contravariant;
 477                         else if (spec.Variance == Variance.Covariant)
 478                                 attr |= GenericParameterAttributes.Covariant;
 479
 480                         if (spec.HasSpecialClass)
 481                                 attr |= GenericParameterAttributes.ReferenceTypeConstraint;
 482                         else if (spec.HasSpecialStruct)
 483                                 attr |= GenericParameterAttributes.NotNullableValueTypeConstraint | GenericParameterAttributes.DefaultConstructorConstraint;
 484
 485                         if (spec.HasSpecialConstructor)
 486                                 attr |= GenericParameterAttributes.DefaultConstructorConstraint;
 487
 488                         if (spec.BaseType != TypeManager.object_type)
 489                                 builder.SetBaseTypeConstraint (spec.BaseType.GetMetaInfo ());
 490
 491                         if (spec.InterfacesDefined != null)
 492                                 builder.SetInterfaceConstraints (spec.InterfacesDefined.Select (l => l.GetMetaInfo ()).ToArray ());
 493
 494                         if (spec.TypeArguments != null)
 495                                 builder.SetInterfaceConstraints (spec.TypeArguments.Select (l => l.GetMetaInfo ()).ToArray ());
 496
 497                         builder.SetGenericParameterAttributes (attr);
 498                 }
 499
 500                 public override void Emit ()
 501                 {
 502                         EmitConstraints (builder);
 503
 504                         if (OptAttributes != null)
 505                                 OptAttributes.Emit ();
 506
 507                         base.Emit ();
 508                 }
 509
 510                 public void ErrorInvalidVariance (IMemberContext mc, Variance expected)
 511                 {
 512                         Report.SymbolRelatedToPreviousError (mc.CurrentMemberDefinition);
 513                         string input_variance = Variance == Variance.Contravariant ? "contravariant" : "covariant";
 514                         string gtype_variance;
 515                         switch (expected) {
 516                         case Variance.Contravariant: gtype_variance = "contravariantly"; break;
 517                         case Variance.Covariant: gtype_variance = "covariantly"; break;
 518                         default: gtype_variance = "invariantly"; break;
 519                         }
 520
 521                         Delegate d = mc as Delegate;
 522                         string parameters = d != null ? d.Parameters.GetSignatureForError () : "";
 523
 524                         Report.Error (1961, Location,
 525                                 "The {2} type parameter `{0}' must be {3} valid on `{1}{4}'",
 526                                         GetSignatureForError (), mc.GetSignatureForError (), input_variance, gtype_variance, parameters);
 527                 }
 528
 529                 public TypeSpec GetAttributeCoClass ()
 530                 {
 531                         return null;
 532                 }
 533
 534                 public string GetAttributeDefaultMember ()
 535                 {
 536                         throw new NotSupportedException ();
 537                 }
 538
 539                 public AttributeUsageAttribute GetAttributeUsage (PredefinedAttribute pa)
 540                 {
 541                         throw new NotSupportedException ();
 542                 }
 543
 544                 public override string GetSignatureForError ()
 545                 {
 546                         return MemberName.Name;
 547                 }
 548
 549                 public void LoadMembers (TypeSpec declaringType, bool onlyTypes, ref MemberCache cache)
 550                 {
 551                         throw new NotSupportedException ("Not supported for compiled definition");
 552                 }
 553
 554                 //
 555                 // Resolves all type parameter constraints
 556                 //
 557                 public bool ResolveConstraints (IMemberContext context)
 558                 {
 559                         if (constraints != null)
 560                                 return constraints.Resolve (context, this);
 561
 562                         if (spec.BaseType == null)
 563                                 spec.BaseType = TypeManager.object_type;
 564
 565                         return true;
 566                 }
 567
 568                 public static TypeParameter FindTypeParameter (TypeParameter[] tparams, string name)
 569                 {
 570                         foreach (var tp in tparams) {
 571                                 if (tp.Name == name)
 572                                         return tp;
 573                         }
 574
 575                         return null;
 576                 }
 577
 578                 public override bool IsClsComplianceRequired ()
 579                 {
 580                         return false;
 581                 }
 582
 583                 public new void VerifyClsCompliance ()
 584                 {
 585                         if (constraints != null)
 586                                 constraints.VerifyClsCompliance (Report);
 587                 }
 588         }
 589
 590         [System.Diagnostics.DebuggerDisplay ("{DisplayDebugInfo()}")]
 591         public class TypeParameterSpec : TypeSpec
 592         {
 593                 public static readonly new TypeParameterSpec[] EmptyTypes = new TypeParameterSpec[0];
 594
 595                 Variance variance;
 596                 SpecialConstraint spec;
 597                 readonly int tp_pos;
 598                 TypeSpec[] targs;
 599                 TypeSpec[] ifaces_defined;
 600
 601                 //
 602                 // Creates type owned type parameter
 603                 //
 604                 public TypeParameterSpec (TypeSpec declaringType, int index, ITypeDefinition definition, SpecialConstraint spec, Variance variance, Type info)
 605                         : base (MemberKind.TypeParameter, declaringType, definition, info, Modifiers.PUBLIC)
 606                 {
 607                         this.variance = variance;
 608                         this.spec = spec;
 609                         state &= ~StateFlags.Obsolete_Undetected;
 610                         tp_pos = index;
 611                 }
 612
 613                 //
 614                 // Creates method owned type parameter
 615                 //
 616                 public TypeParameterSpec (int index, ITypeDefinition definition, SpecialConstraint spec, Variance variance, Type info)
 617                         : this (null, index, definition, spec, variance, info)
 618                 {
 619                 }
 620
 621                 #region Properties
 622
 623                 public int DeclaredPosition {
 624                         get {
 625                                 return tp_pos;
 626                         }
 627                 }
 628
 629                 public bool HasSpecialConstructor {
 630                         get {
 631                                 return (spec & SpecialConstraint.Constructor) != 0;
 632                         }
 633                 }
 634
 635                 public bool HasSpecialClass {
 636                         get {
 637                                 return (spec & SpecialConstraint.Class) != 0;
 638                         }
 639                 }
 640
 641                 public bool HasSpecialStruct {
 642                         get {
 643                                 return (spec & SpecialConstraint.Struct) != 0;
 644                         }
 645                 }
 646
 647                 public bool HasTypeConstraint {
 648                         get {
 649                                 return BaseType != TypeManager.object_type && BaseType != TypeManager.value_type;
 650                         }
 651                 }
 652
 653                 public override IList<TypeSpec> Interfaces {
 654                         get {
 655                                 if ((state & StateFlags.InterfacesExpanded) == 0) {
 656                                         if (ifaces != null) {
 657                                                 for (int i = 0; i < ifaces.Count; ++i ) {
 658                                                         var iface_type = ifaces[i];
 659                                                         if (iface_type.Interfaces != null) {
 660                                                                 if (ifaces_defined == null)
 661                                                                         ifaces_defined = ifaces.ToArray ();
 662
 663                                                                 for (int ii = 0; ii < iface_type.Interfaces.Count; ++ii) {
 664                                                                         var ii_iface_type = iface_type.Interfaces [ii];
 665
 666                                                                         AddInterface (ii_iface_type);
 667                                                                 }
 668                                                         }
 669                                                 }
 670                                         }
 671
 672                                         if (ifaces_defined == null && ifaces != null)
 673                                                 ifaces_defined = ifaces.ToArray ();
 674
 675                                         state |= StateFlags.InterfacesExpanded;
 676                                 }
 677
 678                                 return ifaces;
 679                         }
 680                 }
 681
 682                 //
 683                 // Unexpanded interfaces list
 684                 //
 685                 public TypeSpec[] InterfacesDefined {
 686                         get {
 687                                 if (ifaces_defined == null && ifaces != null)
 688                                         ifaces_defined = ifaces.ToArray ();
 689
 690                                 return ifaces_defined;
 691                         }
 692                         set {
 693                                 ifaces_defined = value;
 694                         }
 695                 }
 696
 697                 public bool IsConstrained {
 698                         get {
 699                                 return spec != SpecialConstraint.None || ifaces != null || targs != null || HasTypeConstraint;
 700                         }
 701                 }
 702
 703                 //
 704                 // Returns whether the type parameter is "known to be a reference type"
 705                 //
 706                 public bool IsReferenceType {
 707                         get {
 708                                 return (spec & SpecialConstraint.Class) != 0 || HasTypeConstraint;
 709                         }
 710                 }
 711
 712                 public bool IsValueType {       // TODO: Do I need this ?
 713                         get {
 714                                 // TODO MemberCache: probably wrong
 715                                 return HasSpecialStruct;
 716                         }
 717                 }
 718
 719                 public override string Name {
 720                         get {
 721                                 return definition.Name;
 722                         }
 723                 }
 724
 725                 public bool IsMethodOwned {
 726                         get {
 727                                 return DeclaringType == null;
 728                         }
 729                 }
 730
 731                 public SpecialConstraint SpecialConstraint {
 732                         get {
 733                                 return spec;
 734                         }
 735                         set {
 736                                 spec = value;
 737                         }
 738                 }
 739
 740                 //
 741                 // Types used to inflate the generic type
 742                 //
 743                 public new TypeSpec[] TypeArguments {
 744                         get {
 745                                 return targs;
 746                         }
 747                         set {
 748                                 targs = value;
 749                         }
 750                 }
 751
 752                 public Variance Variance {
 753                         get {
 754                                 return variance;
 755                         }
 756                 }
 757
 758                 #endregion
 759
 760                 public void ChangeTypeArgumentToBaseType (int index)
 761                 {
 762                         BaseType = targs [index];
 763                         if (targs.Length == 1) {
 764                                 targs = null;
 765                         } else {
 766                                 var copy = new TypeSpec[targs.Length - 1];
 767                                 if (index > 0)
 768                                         Array.Copy (targs, copy, index);
 769
 770                                 Array.Copy (targs, index + 1, copy, index, targs.Length - index - 1);
 771                                 targs = copy;
 772                         }
 773                 }
 774
 775                 public string DisplayDebugInfo ()
 776                 {
 777                         var s = GetSignatureForError ();
 778                         return IsMethodOwned ? s + "!!" : s + "!";
 779                 }
 780
 781                 //
 782                 // Finds effective base class
 783                 //
 784                 public TypeSpec GetEffectiveBase ()
 785                 {
 786                         if (HasSpecialStruct) {
 787                                 return TypeManager.value_type;
 788                         }
 789
 790                         if (BaseType != null && targs == null)
 791                                 return BaseType;
 792
 793                         var types = targs;
 794                         if (HasTypeConstraint) {
 795                                 Array.Resize (ref types, types.Length + 1);
 796                                 types[types.Length - 1] = BaseType;
 797                         }
 798
 799                         if (types != null)
 800                                 return Convert.FindMostEncompassedType (types.Select (l => l.BaseType));
 801
 802                         return TypeManager.object_type;
 803                 }
 804
 805                 public override string GetSignatureForError ()
 806                 {
 807                         return Name;
 808                 }
 809
 810                 //
 811                 // Constraints have to match by definition but not position, used by
 812                 // partial classes or methods
 813                 //
 814                 public bool HasSameConstraintsDefinition (TypeParameterSpec other)
 815                 {
 816                         if (spec != other.spec)
 817                                 return false;
 818
 819                         if (BaseType != other.BaseType)
 820                                 return false;
 821
 822                         if (!TypeSpecComparer.Override.IsSame (InterfacesDefined, other.InterfacesDefined))
 823                                 return false;
 824
 825                         if (!TypeSpecComparer.Override.IsSame (targs, other.targs))
 826                                 return false;
 827
 828                         return true;
 829                 }
 830
 831                 //
 832                 // Constraints have to match by using same set of types, used by
 833                 // implicit interface implementation
 834                 //
 835                 public bool HasSameConstraintsImplementation (TypeParameterSpec other)
 836                 {
 837                         if (spec != other.spec)
 838                                 return false;
 839
 840                         //
 841                         // It can be same base type or inflated type parameter
 842                         //
 843                         // interface I<T> { void Foo<U> where U : T; }
 844                         // class A : I<int> { void Foo<X> where X : int {} }
 845                         //
 846                         bool found;
 847                         if (!TypeSpecComparer.Override.IsEqual (BaseType, other.BaseType)) {
 848                                 if (other.targs == null)
 849                                         return false;
 850
 851                                 found = false;
 852                                 foreach (var otarg in other.targs) {
 853                                         if (TypeSpecComparer.Override.IsEqual (BaseType, otarg)) {
 854                                                 found = true;
 855                                                 break;
 856                                         }
 857                                 }
 858
 859                                 if (!found)
 860                                         return false;
 861                         }
 862
 863                         // Check interfaces implementation -> definition
 864                         if (InterfacesDefined != null) {
 865                                 foreach (var iface in InterfacesDefined) {
 866                                         found = false;
 867                                         if (other.InterfacesDefined != null) {
 868                                                 foreach (var oiface in other.InterfacesDefined) {
 869                                                         if (TypeSpecComparer.Override.IsEqual (iface, oiface)) {
 870                                                                 found = true;
 871                                                                 break;
 872                                                         }
 873                                                 }
 874                                         }
 875
 876                                         if (found)
 877                                                 continue;
 878
 879                                         if (other.targs != null) {
 880                                                 foreach (var otarg in other.targs) {
 881                                                         if (TypeSpecComparer.Override.IsEqual (BaseType, otarg)) {
 882                                                                 found = true;
 883                                                                 break;
 884                                                         }
 885                                                 }
 886                                         }
 887
 888                                         if (!found)
 889                                                 return false;
 890                                 }
 891                         }
 892
 893                         // Check interfaces implementation <- definition
 894                         if (other.InterfacesDefined != null) {
 895                                 if (InterfacesDefined == null)
 896                                         return false;
 897
 898                                 foreach (var oiface in other.InterfacesDefined) {
 899                                         found = false;
 900                                         foreach (var iface in InterfacesDefined) {
 901                                                 if (TypeSpecComparer.Override.IsEqual (iface, oiface)) {
 902                                                         found = true;
 903                                                         break;
 904                                                 }
 905                                         }
 906
 907                                         if (!found)
 908                                                 return false;
 909                                 }
 910                         }
 911
 912                         // Check type parameters implementation -> definition
 913                         if (targs != null) {
 914                                 if (other.targs == null)
 915                                         return false;
 916
 917                                 foreach (var targ in targs) {
 918                                         found = false;
 919                                         foreach (var otarg in other.targs) {
 920                                                 if (TypeSpecComparer.Override.IsEqual (targ, otarg)) {
 921                                                         found = true;
 922                                                         break;
 923                                                 }
 924                                         }
 925
 926                                         if (!found)
 927                                                 return false;
 928                                 }
 929                         }
 930
 931                         // Check type parameters implementation <- definition
 932                         if (other.targs != null) {
 933                                 foreach (var otarg in other.targs) {
 934                                         // Ignore inflated type arguments, were checked above
 935                                         if (!otarg.IsGenericParameter)
 936                                                 continue;
 937
 938                                         if (targs == null)
 939                                                 return false;
 940
 941                                         found = false;
 942                                         foreach (var targ in targs) {
 943                                                 if (TypeSpecComparer.Override.IsEqual (targ, otarg)) {
 944                                                         found = true;
 945                                                         break;
 946                                                 }
 947                                         }
 948
 949                                         if (!found)
 950                                                 return false;
 951                                 }
 952                         }
 953
 954                         return true;
 955                 }
 956
 957                 public static TypeParameterSpec[] InflateConstraints (TypeParameterInflator inflator, TypeParameterSpec[] tparams)
 958                 {
 959                         return InflateConstraints (tparams, l => l, inflator);
 960                 }
 961
 962                 public static TypeParameterSpec[] InflateConstraints<T> (TypeParameterSpec[] tparams, Func<T, TypeParameterInflator> inflatorFactory, T arg)
 963                 {
 964                         TypeParameterSpec[] constraints = null;
 965                         TypeParameterInflator? inflator = null;
 966
 967                         for (int i = 0; i < tparams.Length; ++i) {
 968                                 var tp = tparams[i];
 969                                 if (tp.HasTypeConstraint || tp.Interfaces != null || tp.TypeArguments != null) {
 970                                         if (constraints == null) {
 971                                                 constraints = new TypeParameterSpec[tparams.Length];
 972                                                 Array.Copy (tparams, constraints, constraints.Length);
 973                                         }
 974
 975                                         //
 976                                         // Using a factory to avoid possibly expensive inflator build up
 977                                         //
 978                                         if (inflator == null)
 979                                                 inflator = inflatorFactory (arg);
 980
 981                                         constraints[i] = (TypeParameterSpec) constraints[i].InflateMember (inflator.Value);
 982                                 }
 983                         }
 984
 985                         if (constraints == null)
 986                                 constraints = tparams;
 987
 988                         return constraints;
 989                 }
 990
 991                 public void InflateConstraints (TypeParameterInflator inflator, TypeParameterSpec tps)
 992                 {
 993                         tps.BaseType = inflator.Inflate (BaseType);
 994                         if (ifaces != null) {
 995                                 tps.ifaces = new List<TypeSpec> (ifaces.Count);
 996                                 for (int i = 0; i < ifaces.Count; ++i)
 997                                         tps.ifaces.Add (inflator.Inflate (ifaces[i]));
 998                         }
 999
1000                         if (targs != null) {
1001                                 tps.targs = new TypeSpec[targs.Length];
1002                                 for (int i = 0; i < targs.Length; ++i)
1003                                         tps.targs[i] = inflator.Inflate (targs[i]);
1004                         }
1005                 }
1006
1007                 public override MemberSpec InflateMember (TypeParameterInflator inflator)
1008                 {
1009                         var tps = (TypeParameterSpec) MemberwiseClone ();
1010                         InflateConstraints (inflator, tps);
1011                         return tps;
1012                 }
1013
1014                 //
1015                 // Populates type parameter members using type parameter constraints
1016                 // The trick here is to be called late enough but not too late to
1017                 // populate member cache with all members from other types
1018                 //
1019                 protected override void InitializeMemberCache (bool onlyTypes)
1020                 {
1021                         cache = new MemberCache ();
1022                         if (ifaces != null) {
1023                                 foreach (var iface_type in Interfaces) {
1024                                         cache.AddInterface (iface_type);
1025                                 }
1026                         }
1027                 }
1028
1029                 public bool IsConvertibleToInterface (TypeSpec iface)
1030                 {
1031                         if (Interfaces != null) {
1032                                 foreach (var t in Interfaces) {
1033                                         if (t == iface)
1034                                                 return true;
1035                                 }
1036                         }
1037
1038                         if (TypeArguments != null) {
1039                                 foreach (var t in TypeArguments) {
1040                                         if (((TypeParameterSpec) t).IsConvertibleToInterface (iface))
1041                                                 return true;
1042                                 }
1043                         }
1044
1045                         return false;
1046                 }
1047
1048                 public override TypeSpec Mutate (TypeParameterMutator mutator)
1049                 {
1050                         return mutator.Mutate (this);
1051                 }
1052         }
1053
1054         public struct TypeParameterInflator
1055         {
1056                 readonly TypeSpec type;
1057                 readonly TypeParameterSpec[] tparams;
1058                 readonly TypeSpec[] targs;
1059
1060                 public TypeParameterInflator (TypeParameterInflator nested, TypeSpec type)
1061                         : this (type, nested.tparams, nested.targs)
1062                 {
1063                 }
1064
1065                 public TypeParameterInflator (TypeSpec type, TypeParameterSpec[] tparams, TypeSpec[] targs)
1066                 {
1067                         if (tparams.Length != targs.Length)
1068                                 throw new ArgumentException ("Invalid arguments");
1069
1070                         this.tparams = tparams;
1071                         this.targs = targs;
1072                         this.type = type;
1073                 }
1074
1075                 #region Properties
1076
1077                 public TypeSpec TypeInstance {
1078                         get { return type; }
1079                 }
1080
1081                 //
1082                 // Type parameters to inflate
1083                 //
1084                 public TypeParameterSpec[] TypeParameters {
1085                         get {
1086                                 return tparams;
1087                         }
1088                 }
1089
1090                 #endregion
1091
1092                 public TypeSpec Inflate (TypeSpec type)
1093                 {
1094                         var tp = type as TypeParameterSpec;
1095                         if (tp != null)
1096                                 return Inflate (tp);
1097
1098                         var ac = type as ArrayContainer;
1099                         if (ac != null) {
1100                                 var et = Inflate (ac.Element);
1101                                 if (et != ac.Element)
1102                                         return ArrayContainer.MakeType (et, ac.Rank);
1103
1104                                 return ac;
1105                         }
1106
1107                         //
1108                         // When inflating a nested type, inflate its parent first
1109                         // in case it's using same type parameters (was inflated within the type)
1110                         //
1111                         TypeSpec[] targs;
1112                         int i = 0;
1113                         if (type.IsNested) {
1114                                 var parent = Inflate (type.DeclaringType);
1115
1116                                 //
1117                                 // Keep the inflated type arguments
1118                                 //
1119                                 targs = type.TypeArguments;
1120
1121                                 //
1122                                 // Parent was inflated, find the same type on inflated type
1123                                 // to use same cache for nested types on same generic parent
1124                                 //
1125                                 type = MemberCache.FindNestedType (parent, type.Name, type.Arity);
1126
1127                                 //
1128                                 // Handle the tricky case where parent shares local type arguments
1129                                 // which means inflating inflated type
1130                                 //
1131                                 // class Test<T> {
1132                                 //              public static Nested<T> Foo () { return null; }
1133                                 //
1134                                 //              public class Nested<U> {}
1135                                 //      }
1136                                 //
1137                                 //  return type of Test<string>.Foo() has to be Test<string>.Nested<string>
1138                                 //
1139                                 if (targs.Length > 0) {
1140                                         var inflated_targs = new TypeSpec[targs.Length];
1141                                         for (; i < targs.Length; ++i)
1142                                                 inflated_targs[i] = Inflate (targs[i]);
1143
1144                                         type = type.MakeGenericType (inflated_targs);
1145                                 }
1146
1147                                 return type;
1148                         }
1149
1150                         // Nothing to do for non-generic type
1151                         if (type.Arity == 0)
1152                                 return type;
1153
1154                         targs = new TypeSpec[type.Arity];
1155
1156                         //
1157                         // Inflating using outside type arguments, var v = new Foo<int> (), class Foo<T> {}
1158                         //
1159                         if (type is InflatedTypeSpec) {
1160                                 for (; i < targs.Length; ++i)
1161                                         targs[i] = Inflate (type.TypeArguments[i]);
1162
1163                                 type = type.GetDefinition ();
1164                         } else {
1165                                 //
1166                                 // Inflating parent using inside type arguments, class Foo<T> { ITest<T> foo; }
1167                                 //
1168                                 var args = type.MemberDefinition.TypeParameters;
1169                                 foreach (var ds_tp in args)
1170                                         targs[i++] = Inflate (ds_tp);
1171                         }
1172
1173                         return type.MakeGenericType (targs);
1174                 }
1175
1176                 public TypeSpec Inflate (TypeParameterSpec tp)
1177                 {
1178                         for (int i = 0; i < tparams.Length; ++i)
1179                                 if (tparams [i] == tp)
1180                                         return targs[i];
1181
1182                         // This can happen when inflating nested types
1183                         // without type arguments specified
1184                         return tp;
1185                 }
1186         }
1187
1188         //
1189         // Before emitting any code we have to change all MVAR references to VAR
1190         // when the method is of generic type and has hoisted variables
1191         //
1192         public class TypeParameterMutator
1193         {
1194                 TypeParameter[] mvar;
1195                 TypeParameter[] var;
1196                 Dictionary<TypeSpec, TypeSpec> mutated_typespec = new Dictionary<TypeSpec, TypeSpec> ();
1197
1198                 public TypeParameterMutator (TypeParameter[] mvar, TypeParameter[] var)
1199                 {
1200                         if (mvar.Length != var.Length)
1201                                 throw new ArgumentException ();
1202
1203                         this.mvar = mvar;
1204                         this.var = var;
1205                 }
1206
1207                 #region Properties
1208
1209                 public TypeParameter[] MethodTypeParameters {
1210                         get {
1211                                 return mvar;
1212                         }
1213                 }
1214
1215                 #endregion
1216
1217                 public static TypeSpec GetMemberDeclaringType (TypeSpec type)
1218                 {
1219                         if (type is InflatedTypeSpec) {
1220                                 if (type.DeclaringType == null)
1221                                         return type.GetDefinition ();
1222
1223                                 var parent = GetMemberDeclaringType (type.DeclaringType);
1224                                 type = MemberCache.GetMember<TypeSpec> (parent, type);
1225                         }
1226
1227                         return type;
1228                 }
1229
1230                 public TypeSpec Mutate (TypeSpec ts)
1231                 {
1232                         TypeSpec value;
1233                         if (mutated_typespec.TryGetValue (ts, out value))
1234                                 return value;
1235
1236                         value = ts.Mutate (this);
1237                         mutated_typespec.Add (ts, value);
1238                         return value;
1239                 }
1240
1241                 public TypeParameterSpec Mutate (TypeParameterSpec tp)
1242                 {
1243                         for (int i = 0; i < mvar.Length; ++i) {
1244                                 if (mvar[i].Type == tp)
1245                                         return var[i].Type;
1246                         }
1247
1248                         return tp;
1249                 }
1250
1251                 public TypeSpec[] Mutate (TypeSpec[] targs)
1252                 {
1253                         TypeSpec[] mutated = new TypeSpec[targs.Length];
1254                         bool changed = false;
1255                         for (int i = 0; i < targs.Length; ++i) {
1256                                 mutated[i] = Mutate (targs[i]);
1257                                 changed |= targs[i] != mutated[i];
1258                         }
1259
1260                         return changed ? mutated : targs;
1261                 }
1262         }
1263
1264         /// <summary>
1265         ///   A TypeExpr which already resolved to a type parameter.
1266         /// </summary>
1267         public class TypeParameterExpr : TypeExpr {
1268
1269                 public TypeParameterExpr (TypeParameter type_parameter, Location loc)
1270                 {
1271                         this.type = type_parameter.Type;
1272                         this.eclass = ExprClass.TypeParameter;
1273                         this.loc = loc;
1274                 }
1275
1276                 protected override TypeExpr DoResolveAsTypeStep (IMemberContext ec)
1277                 {
1278                         throw new NotSupportedException ();
1279                 }
1280
1281                 public override FullNamedExpression ResolveAsTypeStep (IMemberContext ec, bool silent)
1282                 {
1283                         return this;
1284                 }
1285
1286                 public override bool CheckAccessLevel (IMemberContext ds)
1287                 {
1288                         return true;
1289                 }
1290         }
1291
1292         public class InflatedTypeSpec : TypeSpec
1293         {
1294                 TypeSpec[] targs;
1295                 TypeParameterSpec[] constraints;
1296                 readonly TypeSpec open_type;
1297
1298                 public InflatedTypeSpec (TypeSpec openType, TypeSpec declaringType, TypeSpec[] targs)
1299                         : base (openType.Kind, declaringType, openType.MemberDefinition, null, openType.Modifiers)
1300                 {
1301                         if (targs == null)
1302                                 throw new ArgumentNullException ("targs");
1303
1304 //                      this.state = openType.state;
1305                         this.open_type = openType;
1306                         this.targs = targs;
1307
1308                         foreach (var arg in targs) {
1309                                 if (arg.HasDynamicElement || arg == InternalType.Dynamic) {
1310                                         state |= StateFlags.HasDynamicElement;
1311                                         break;
1312                                 }
1313                         }
1314                 }
1315
1316                 #region Properties
1317
1318                 public override TypeSpec BaseType {
1319                         get {
1320                                 if (cache == null || (state & StateFlags.PendingBaseTypeInflate) != 0)
1321                                         InitializeMemberCache (true);
1322
1323                                 return base.BaseType;
1324                         }
1325                 }
1326
1327                 //
1328                 // Inflated type parameters with constraints array, mapping with type arguments is based on index
1329                 //
1330                 public TypeParameterSpec[] Constraints {
1331                         get {
1332                                 if (constraints == null) {
1333                                         constraints = TypeParameterSpec.InflateConstraints (MemberDefinition.TypeParameters, l => l.CreateLocalInflator (), this);
1334                                 }
1335
1336                                 return constraints;
1337                         }
1338                 }
1339
1340                 public override IList<TypeSpec> Interfaces {
1341                         get {
1342                                 if (cache == null)
1343                                         InitializeMemberCache (true);
1344
1345                                 return base.Interfaces;
1346                         }
1347                 }
1348
1349                 //
1350                 // Types used to inflate the generic  type
1351                 //
1352                 public override TypeSpec[] TypeArguments {
1353                         get {
1354                                 return targs;
1355                         }
1356                 }
1357
1358                 #endregion
1359
1360                 TypeParameterInflator CreateLocalInflator ()
1361                 {
1362                         TypeParameterSpec[] tparams_full;
1363                         TypeSpec[] targs_full = targs;
1364                         if (IsNested) {
1365                                 //
1366                                 // Special case is needed when we are inflating an open type (nested type definition)
1367                                 // on inflated parent. Consider following case
1368                                 //
1369                                 // Foo<T>.Bar<U> => Foo<string>.Bar<U>
1370                                 //
1371                                 // Any later inflation of Foo<string>.Bar<U> has to also inflate T if used inside Bar<U>
1372                                 //
1373                                 List<TypeSpec> merged_targs = null;
1374                                 List<TypeParameterSpec> merged_tparams = null;
1375
1376                                 var type = DeclaringType;
1377
1378                                 do {
1379                                         if (type.TypeArguments.Length > 0) {
1380                                                 if (merged_targs == null) {
1381                                                         merged_targs = new List<TypeSpec> ();
1382                                                         merged_tparams = new List<TypeParameterSpec> ();
1383                                                         if (targs.Length > 0) {
1384                                                                 merged_targs.AddRange (targs);
1385                                                                 merged_tparams.AddRange (open_type.MemberDefinition.TypeParameters);
1386                                                         }
1387                                                 }
1388                                                 merged_tparams.AddRange (type.MemberDefinition.TypeParameters);
1389                                                 merged_targs.AddRange (type.TypeArguments);
1390                                         }
1391                                         type = type.DeclaringType;
1392                                 } while (type != null);
1393
1394                                 if (merged_targs != null) {
1395                                         // Type arguments are not in the right order but it should not matter in this case
1396                                         targs_full = merged_targs.ToArray ();
1397                                         tparams_full = merged_tparams.ToArray ();
1398                                 } else if (targs.Length == 0) {
1399                                         tparams_full = TypeParameterSpec.EmptyTypes;
1400                                 } else {
1401                                         tparams_full = open_type.MemberDefinition.TypeParameters;
1402                                 }
1403                         } else if (targs.Length == 0) {
1404                                 tparams_full = TypeParameterSpec.EmptyTypes;
1405                         } else {
1406                                 tparams_full = open_type.MemberDefinition.TypeParameters;
1407                         }
1408
1409                         return new TypeParameterInflator (this, tparams_full, targs_full);
1410                 }
1411
1412                 Type CreateMetaInfo (TypeParameterMutator mutator)
1413                 {
1414                         //
1415                         // Converts nested type arguments into right order
1416                         // Foo<string, bool>.Bar<int> => string, bool, int
1417                         //
1418                         var all = new List<Type> ();
1419                         TypeSpec type = this;
1420                         TypeSpec definition = type;
1421                         do {
1422                                 if (type.GetDefinition().IsGeneric) {
1423                                         all.InsertRange (0,
1424                                                 type.TypeArguments != TypeSpec.EmptyTypes ?
1425                                                 type.TypeArguments.Select (l => l.GetMetaInfo ()) :
1426                                                 type.MemberDefinition.TypeParameters.Select (l => l.GetMetaInfo ()));
1427                                 }
1428
1429                                 definition = definition.GetDefinition ();
1430                                 type = type.DeclaringType;
1431                         } while (type != null);
1432
1433                         return definition.GetMetaInfo ().MakeGenericType (all.ToArray ());
1434                 }
1435
1436                 public override ObsoleteAttribute GetAttributeObsolete ()
1437                 {
1438                         return open_type.GetAttributeObsolete ();
1439                 }
1440
1441                 protected override bool IsNotCLSCompliant ()
1442                 {
1443                         if (base.IsNotCLSCompliant ())
1444                                 return true;
1445
1446                         foreach (var ta in TypeArguments) {
1447                                 if (ta.MemberDefinition.IsNotCLSCompliant ())
1448                                         return true;
1449                         }
1450
1451                         return false;
1452                 }
1453
1454                 public override TypeSpec GetDefinition ()
1455                 {
1456                         return open_type;
1457                 }
1458
1459                 public override Type GetMetaInfo ()
1460                 {
1461                         if (info == null)
1462                                 info = CreateMetaInfo (null);
1463
1464                         return info;
1465                 }
1466
1467                 public override string GetSignatureForError ()
1468                 {
1469                         if (TypeManager.IsNullableType (open_type))
1470                                 return targs[0].GetSignatureForError () + "?";
1471
1472                         return base.GetSignatureForError ();
1473                 }
1474
1475                 protected override string GetTypeNameSignature ()
1476                 {
1477                         if (targs.Length == 0 || MemberDefinition is AnonymousTypeClass)
1478                                 return null;
1479
1480                         return "<" + TypeManager.CSharpName (targs) + ">";
1481                 }
1482
1483                 protected override void InitializeMemberCache (bool onlyTypes)
1484                 {
1485                         if (cache == null)
1486                                 cache = new MemberCache (onlyTypes ? open_type.MemberCacheTypes : open_type.MemberCache);
1487
1488                         var inflator = CreateLocalInflator ();
1489
1490                         //
1491                         // Two stage inflate due to possible nested types recursive
1492                         // references
1493                         //
1494                         // class A<T> {
1495                         //    B b;
1496                         //    class B {
1497                         //      T Value;
1498                         //    }
1499                         // }
1500                         //
1501                         // When resolving type of `b' members of `B' cannot be
1502                         // inflated because are not yet available in membercache
1503                         //
1504                         if ((state & StateFlags.PendingMemberCacheMembers) == 0) {
1505                                 open_type.MemberCacheTypes.InflateTypes (cache, inflator);
1506
1507                                 //
1508                                 // Inflate any implemented interfaces
1509                                 //
1510                                 if (open_type.Interfaces != null) {
1511                                         ifaces = new List<TypeSpec> (open_type.Interfaces.Count);
1512                                         foreach (var iface in open_type.Interfaces) {
1513                                                 var iface_inflated = inflator.Inflate (iface);
1514                                                 AddInterface (iface_inflated);
1515                                         }
1516                                 }
1517
1518                                 //
1519                                 // Handles the tricky case of recursive nested base generic type
1520                                 //
1521                                 // class A<T> : Base<A<T>.Nested> {
1522                                 //    class Nested {}
1523                                 // }
1524                                 //
1525                                 // When inflating A<T>. base type is not yet known, secondary
1526                                 // inflation is required (not common case) once base scope
1527                                 // is known
1528                                 //
1529                                 if (open_type.BaseType == null) {
1530                                         if (IsClass)
1531                                                 state |= StateFlags.PendingBaseTypeInflate;
1532                                 } else {
1533                                         BaseType = inflator.Inflate (open_type.BaseType);
1534                                 }
1535                         } else if ((state & StateFlags.PendingBaseTypeInflate) != 0) {
1536                                 BaseType = inflator.Inflate (open_type.BaseType);
1537                                 state &= ~StateFlags.PendingBaseTypeInflate;
1538                         }
1539
1540                         if (onlyTypes) {
1541                                 state |= StateFlags.PendingMemberCacheMembers;
1542                                 return;
1543                         }
1544
1545                         var tc = open_type.MemberDefinition as TypeContainer;
1546                         if (tc != null && !tc.HasMembersDefined)
1547                                 throw new InternalErrorException ("Inflating MemberCache with undefined members");
1548
1549                         if ((state & StateFlags.PendingBaseTypeInflate) != 0) {
1550                                 BaseType = inflator.Inflate (open_type.BaseType);
1551                                 state &= ~StateFlags.PendingBaseTypeInflate;
1552                         }
1553
1554                         state &= ~StateFlags.PendingMemberCacheMembers;
1555                         open_type.MemberCache.InflateMembers (cache, open_type, inflator);
1556                 }
1557
1558                 public override TypeSpec Mutate (TypeParameterMutator mutator)
1559                 {
1560                         var targs = TypeArguments;
1561                         if (targs != null)
1562                                 targs = mutator.Mutate (targs);
1563
1564                         var decl = DeclaringType;
1565                         if (IsNested && DeclaringType.IsGenericOrParentIsGeneric)
1566                                 decl = mutator.Mutate (decl);
1567
1568                         if (targs == TypeArguments && decl == DeclaringType)
1569                                 return this;
1570
1571                         var mutated = (InflatedTypeSpec) MemberwiseClone ();
1572                         if (decl != DeclaringType) {
1573                                 // Gets back MethodInfo in case of metaInfo was inflated
1574                                 //mutated.info = MemberCache.GetMember<TypeSpec> (DeclaringType.GetDefinition (), this).info;
1575
1576                                 mutated.declaringType = decl;
1577                                 mutated.state |= StateFlags.PendingMetaInflate;
1578                         }
1579
1580                         if (targs != null) {
1581                                 mutated.targs = targs;
1582                                 mutated.info = null;
1583                         }
1584
1585                         return mutated;
1586                 }
1587         }
1588
1589
1590         //
1591         // Tracks the type arguments when instantiating a generic type. It's used
1592         // by both type arguments and type parameters
1593         //
1594         public class TypeArguments
1595         {
1596                 List<FullNamedExpression> args;
1597                 TypeSpec[] atypes;
1598
1599                 public TypeArguments (params FullNamedExpression[] types)
1600                 {
1601                         this.args = new List<FullNamedExpression> (types);
1602                 }
1603
1604                 public void Add (FullNamedExpression type)
1605                 {
1606                         args.Add (type);
1607                 }
1608
1609                 // TODO: Kill this monster
1610                 public TypeParameterName[] GetDeclarations ()
1611                 {
1612                         return args.ConvertAll (i => (TypeParameterName) i).ToArray ();
1613                 }
1614
1615                 /// <summary>
1616                 ///   We may only be used after Resolve() is called and return the fully
1617                 ///   resolved types.
1618                 /// </summary>
1619                 // TODO: Not needed, just return type from resolve
1620                 public TypeSpec[] Arguments {
1621                         get {
1622                                 return atypes;
1623                         }
1624                 }
1625
1626                 public int Count {
1627                         get {
1628                                 return args.Count;
1629                         }
1630                 }
1631
1632                 public virtual bool IsEmpty {
1633                         get {
1634                                 return false;
1635                         }
1636                 }
1637
1638                 public string GetSignatureForError()
1639                 {
1640                         StringBuilder sb = new StringBuilder ();
1641                         for (int i = 0; i < Count; ++i) {
1642                                 var expr = args[i];
1643                                 if (expr != null)
1644                                         sb.Append (expr.GetSignatureForError ());
1645
1646                                 if (i + 1 < Count)
1647                                         sb.Append (',');
1648                         }
1649
1650                         return sb.ToString ();
1651                 }
1652
1653                 /// <summary>
1654                 ///   Resolve the type arguments.
1655                 /// </summary>
1656                 public virtual bool Resolve (IMemberContext ec)
1657                 {
1658                         if (atypes != null)
1659                             return atypes.Length != 0;
1660
1661                         int count = args.Count;
1662                         bool ok = true;
1663
1664                         atypes = new TypeSpec [count];
1665
1666                         for (int i = 0; i < count; i++){
1667                                 TypeExpr te = args[i].ResolveAsTypeTerminal (ec, false);
1668                                 if (te == null) {
1669                                         ok = false;
1670                                         continue;
1671                                 }
1672
1673                                 atypes[i] = te.Type;
1674
1675                                 if (te.Type.IsStatic) {
1676                                         ec.Compiler.Report.Error (718, te.Location, "`{0}': static classes cannot be used as generic arguments",
1677                                                 te.GetSignatureForError ());
1678                                         ok = false;
1679                                 }
1680
1681                                 if (te.Type.IsPointer || TypeManager.IsSpecialType (te.Type)) {
1682                                         ec.Compiler.Report.Error (306, te.Location,
1683                                                 "The type `{0}' may not be used as a type argument",
1684                                                 te.GetSignatureForError ());
1685                                         ok = false;
1686                                 }
1687                         }
1688
1689                         if (!ok)
1690                                 atypes = TypeSpec.EmptyTypes;
1691
1692                         return ok;
1693                 }
1694
1695                 public TypeArguments Clone ()
1696                 {
1697                         TypeArguments copy = new TypeArguments ();
1698                         foreach (var ta in args)
1699                                 copy.args.Add (ta);
1700
1701                         return copy;
1702                 }
1703         }
1704
1705         public class UnboundTypeArguments : TypeArguments
1706         {
1707                 public UnboundTypeArguments (int arity)
1708                         : base (new FullNamedExpression[arity])
1709                 {
1710                 }
1711
1712                 public override bool IsEmpty {
1713                         get {
1714                                 return true;
1715                         }
1716                 }
1717
1718                 public override bool Resolve (IMemberContext ec)
1719                 {
1720                         // Nothing to be resolved
1721                         return true;
1722                 }
1723         }
1724
1725         public class TypeParameterName : SimpleName
1726         {
1727                 Attributes attributes;
1728                 Variance variance;
1729
1730                 public TypeParameterName (string name, Attributes attrs, Location loc)
1731                         : this (name, attrs, Variance.None, loc)
1732                 {
1733                 }
1734
1735                 public TypeParameterName (string name, Attributes attrs, Variance variance, Location loc)
1736                         : base (name, loc)
1737                 {
1738                         attributes = attrs;
1739                         this.variance = variance;
1740                 }
1741
1742                 public Attributes OptAttributes {
1743                         get {
1744                                 return attributes;
1745                         }
1746                 }
1747
1748                 public Variance Variance {
1749                         get {
1750                                 return variance;
1751                         }
1752                 }
1753         }
1754
1755         //
1756         // A type expression of generic type with type arguments
1757         //
1758         class GenericTypeExpr : TypeExpr
1759         {
1760                 TypeArguments args;
1761                 TypeSpec open_type;
1762                 bool constraints_checked;
1763
1764                 /// <summary>
1765                 ///   Instantiate the generic type `t' with the type arguments `args'.
1766                 ///   Use this constructor if you already know the fully resolved
1767                 ///   generic type.
1768                 /// </summary>
1769                 public GenericTypeExpr (TypeSpec open_type, TypeArguments args, Location l)
1770                 {
1771                         this.open_type = open_type;
1772                         loc = l;
1773                         this.args = args;
1774                 }
1775
1776                 public TypeArguments TypeArguments {
1777                         get { return args; }
1778                 }
1779
1780                 public override string GetSignatureForError ()
1781                 {
1782                         return TypeManager.CSharpName (type);
1783                 }
1784
1785                 protected override TypeExpr DoResolveAsTypeStep (IMemberContext ec)
1786                 {
1787                         if (!args.Resolve (ec))
1788                                 return null;
1789
1790                         TypeSpec[] atypes = args.Arguments;
1791
1792                         //
1793                         // Now bind the parameters
1794                         //
1795                         type = open_type.MakeGenericType (atypes);
1796
1797                         //
1798                         // Check constraints when context is not method/base type
1799                         //
1800                         if (!ec.HasUnresolvedConstraints)
1801                                 CheckConstraints (ec);
1802
1803                         return this;
1804                 }
1805
1806                 //
1807                 // Checks the constraints of open generic type against type
1808                 // arguments. Has to be called after all members have been defined
1809                 //
1810                 public bool CheckConstraints (IMemberContext ec)
1811                 {
1812                         if (constraints_checked)
1813                                 return true;
1814
1815                         constraints_checked = true;
1816
1817                         var gtype = (InflatedTypeSpec) type;
1818                         var constraints = gtype.Constraints;
1819                         if (constraints == null)
1820                                 return true;
1821
1822                         return new ConstraintChecker(ec).CheckAll (open_type, args.Arguments, constraints, loc);
1823                 }
1824
1825                 public override bool CheckAccessLevel (IMemberContext mc)
1826                 {
1827                         DeclSpace c = mc.CurrentMemberDefinition as DeclSpace;
1828                         if (c == null)
1829                                 c = mc.CurrentMemberDefinition.Parent;
1830
1831                         return c.CheckAccessLevel (open_type);
1832                 }
1833
1834                 public bool HasDynamicArguments ()
1835                 {
1836                         return HasDynamicArguments (args.Arguments);
1837                 }
1838
1839                 static bool HasDynamicArguments (TypeSpec[] args)
1840                 {
1841                         for (int i = 0; i < args.Length; ++i) {
1842                                 var item = args[i];
1843
1844                                 if (item == InternalType.Dynamic)
1845                                         return true;
1846
1847                                 if (TypeManager.IsGenericType (item))
1848                                         return HasDynamicArguments (TypeManager.GetTypeArguments (item));
1849
1850                                 if (item.IsArray) {
1851                                         while (item.IsArray) {
1852                                                 item = ((ArrayContainer) item).Element;
1853                                         }
1854
1855                                         if (item == InternalType.Dynamic)
1856                                                 return true;
1857                                 }
1858                         }
1859
1860                         return false;
1861                 }
1862
1863                 public override bool Equals (object obj)
1864                 {
1865                         GenericTypeExpr cobj = obj as GenericTypeExpr;
1866                         if (cobj == null)
1867                                 return false;
1868
1869                         if ((type == null) || (cobj.type == null))
1870                                 return false;
1871
1872                         return type == cobj.type;
1873                 }
1874
1875                 public override int GetHashCode ()
1876                 {
1877                         return base.GetHashCode ();
1878                 }
1879         }
1880
1881         //
1882         // Generic type with unbound type arguments, used for typeof (G<,,>)
1883         //
1884         class GenericOpenTypeExpr : TypeExpr
1885         {
1886                 public GenericOpenTypeExpr (TypeSpec type, /*UnboundTypeArguments args,*/ Location loc)
1887                 {
1888                         this.type = type.GetDefinition ();
1889                         this.loc = loc;
1890                 }
1891
1892                 protected override TypeExpr DoResolveAsTypeStep (IMemberContext ec)
1893                 {
1894                         return this;
1895                 }
1896         }
1897
1898         struct ConstraintChecker
1899         {
1900                 IMemberContext mc;
1901                 bool ignore_inferred_dynamic;
1902
1903                 public ConstraintChecker (IMemberContext ctx)
1904                 {
1905                         this.mc = ctx;
1906                         ignore_inferred_dynamic = false;
1907                 }
1908
1909                 #region Properties
1910
1911                 public bool IgnoreInferredDynamic {
1912                         get {
1913                                 return ignore_inferred_dynamic;
1914                         }
1915                         set {
1916                                 ignore_inferred_dynamic = value;
1917                         }
1918                 }
1919
1920                 #endregion
1921
1922                 //
1923                 // Checks all type arguments againts type parameters constraints
1924                 // NOTE: It can run in probing mode when `mc' is null
1925                 //
1926                 public bool CheckAll (MemberSpec context, TypeSpec[] targs, TypeParameterSpec[] tparams, Location loc)
1927                 {
1928                         for (int i = 0; i < tparams.Length; i++) {
1929                                 if (ignore_inferred_dynamic && targs[i] == InternalType.Dynamic)
1930                                         continue;
1931
1932                                 if (!CheckConstraint (context, targs [i], tparams [i], loc))
1933                                         return false;
1934                         }
1935
1936                         return true;
1937                 }
1938
1939                 bool CheckConstraint (MemberSpec context, TypeSpec atype, TypeParameterSpec tparam, Location loc)
1940                 {
1941                         //
1942                         // First, check the `class' and `struct' constraints.
1943                         //
1944                         if (tparam.HasSpecialClass && !TypeManager.IsReferenceType (atype)) {
1945                                 if (mc != null) {
1946                                         mc.Compiler.Report.Error (452, loc,
1947                                                 "The type `{0}' must be a reference type in order to use it as type parameter `{1}' in the generic type or method `{2}'",
1948                                                 TypeManager.CSharpName (atype), tparam.GetSignatureForError (), context.GetSignatureForError ());
1949                                 }
1950
1951                                 return false;
1952                         }
1953
1954                         if (tparam.HasSpecialStruct && (!TypeManager.IsValueType (atype) || TypeManager.IsNullableType (atype))) {
1955                                 if (mc != null) {
1956                                         mc.Compiler.Report.Error (453, loc,
1957                                                 "The type `{0}' must be a non-nullable value type in order to use it as type parameter `{1}' in the generic type or method `{2}'",
1958                                                 TypeManager.CSharpName (atype), tparam.GetSignatureForError (), context.GetSignatureForError ());
1959                                 }
1960
1961                                 return false;
1962                         }
1963
1964                         bool ok = true;
1965
1966                         //
1967                         // Check the class constraint
1968                         //
1969                         if (tparam.HasTypeConstraint) {
1970                                 if (!CheckConversion (mc, context, atype, tparam, tparam.BaseType, loc)) {
1971                                         if (mc == null)
1972                                                 return false;
1973
1974                                         ok = false;
1975                                 }
1976                         }
1977
1978                         //
1979                         // Check the interfaces constraints
1980                         //
1981                         if (tparam.Interfaces != null) {
1982                                 if (TypeManager.IsNullableType (atype)) {
1983                                         if (mc == null)
1984                                                 return false;
1985
1986                                         mc.Compiler.Report.Error (313, loc,
1987                                                 "The type `{0}' cannot be used as type parameter `{1}' in the generic type or method `{2}'. The nullable type `{0}' never satisfies interface constraint",
1988                                                 atype.GetSignatureForError (), tparam.GetSignatureForError (), context.GetSignatureForError ());
1989                                         ok = false;
1990                                 } else {
1991                                         foreach (TypeSpec iface in tparam.Interfaces) {
1992                                                 if (!CheckConversion (mc, context, atype, tparam, iface, loc)) {
1993                                                         if (mc == null)
1994                                                                 return false;
1995
1996                                                         ok = false;
1997                                                 }
1998                                         }
1999                                 }
2000                         }
2001
2002                         //
2003                         // Check the type parameter constraint
2004                         //
2005                         if (tparam.TypeArguments != null) {
2006                                 foreach (var ta in tparam.TypeArguments) {
2007                                         if (!CheckConversion (mc, context, atype, tparam, ta, loc)) {
2008                                                 if (mc == null)
2009                                                         return false;
2010
2011                                                 ok = false;
2012                                         }
2013                                 }
2014                         }
2015
2016                         //
2017                         // Finally, check the constructor constraint.
2018                         //
2019                         if (!tparam.HasSpecialConstructor)
2020                                 return ok;
2021
2022                         if (!HasDefaultConstructor (atype)) {
2023                                 if (mc != null) {
2024                                         mc.Compiler.Report.SymbolRelatedToPreviousError (atype);
2025                                         mc.Compiler.Report.Error (310, loc,
2026                                                 "The type `{0}' must have a public parameterless constructor in order to use it as parameter `{1}' in the generic type or method `{2}'",
2027                                                 TypeManager.CSharpName (atype), tparam.GetSignatureForError (), context.GetSignatureForError ());
2028                                 }
2029                                 return false;
2030                         }
2031
2032                         return ok;
2033                 }
2034
2035                 static bool HasDynamicTypeArgument (TypeSpec[] targs)
2036                 {
2037                         for (int i = 0; i < targs.Length; ++i) {
2038                                 var targ = targs [i];
2039                                 if (targ == InternalType.Dynamic)
2040                                         return true;
2041
2042                                 if (HasDynamicTypeArgument (targ.TypeArguments))
2043                                         return true;
2044                         }
2045
2046                         return false;
2047                 }
2048
2049                 bool CheckConversion (IMemberContext mc, MemberSpec context, TypeSpec atype, TypeParameterSpec tparam, TypeSpec ttype, Location loc)
2050                 {
2051                         if (TypeManager.IsValueType (atype)) {
2052                                 if (atype == ttype || Convert.ImplicitBoxingConversion (null, atype, ttype) != null)
2053                                         return true;
2054                         } else {
2055                                 var expr = new EmptyExpression (atype);
2056
2057                                 if (atype.IsGenericParameter) {
2058                                         if (Convert.ImplicitTypeParameterConversion (expr, ttype) != null)
2059                                                 return true;
2060                                 }
2061
2062                                 if (Convert.ImplicitStandardConversionExists (expr, ttype))
2063                                         return true;
2064                         }
2065
2066                         //
2067                         // When partial/full type inference finds a dynamic type argument delay
2068                         // the constraint check to runtime, it can succeed for real underlying
2069                         // dynamic type
2070                         //
2071                         if (ignore_inferred_dynamic && HasDynamicTypeArgument (ttype.TypeArguments))
2072                                 return true;
2073
2074                         if (mc != null) {
2075                                 mc.Compiler.Report.SymbolRelatedToPreviousError (tparam);
2076                                 if (TypeManager.IsValueType (atype)) {
2077                                         mc.Compiler.Report.Error (315, loc,
2078                                                 "The type `{0}' cannot be used as type parameter `{1}' in the generic type or method `{2}'. There is no boxing conversion from `{0}' to `{3}'",
2079                                                 atype.GetSignatureForError (), tparam.GetSignatureForError (), context.GetSignatureForError (), ttype.GetSignatureForError ());
2080                                 } else if (atype.IsGenericParameter) {
2081                                         mc.Compiler.Report.Error (314, loc,
2082                                                 "The type `{0}' cannot be used as type parameter `{1}' in the generic type or method `{2}'. There is no boxing or type parameter conversion from `{0}' to `{3}'",
2083                                                 atype.GetSignatureForError (), tparam.GetSignatureForError (), context.GetSignatureForError (), ttype.GetSignatureForError ());
2084                                 } else {
2085                                         mc.Compiler.Report.Error (311, loc,
2086                                                 "The type `{0}' cannot be used as type parameter `{1}' in the generic type or method `{2}'. There is no implicit reference conversion from `{0}' to `{3}'",
2087                                                 atype.GetSignatureForError (), tparam.GetSignatureForError (), context.GetSignatureForError (), ttype.GetSignatureForError ());
2088                                 }
2089                         }
2090
2091                         return false;
2092                 }
2093
2094                 bool HasDefaultConstructor (TypeSpec atype)
2095                 {
2096                         var tp = atype as TypeParameterSpec;
2097                         if (tp != null) {
2098                                 return tp.HasSpecialConstructor || tp.HasSpecialStruct;
2099                         }
2100
2101                         if (atype.IsStruct || atype.IsEnum)
2102                                 return true;
2103
2104                         if (atype.IsAbstract)
2105                                 return false;
2106
2107                         var tdef = atype.GetDefinition ();
2108
2109                         //
2110                         // In some circumstances MemberCache is not yet populated and members
2111                         // cannot be defined yet (recursive type new constraints)
2112                         //
2113                         // class A<T> where T : B<T>, new () {}
2114                         // class B<T> where T : A<T>, new () {}
2115                         //
2116                         var tc = tdef.MemberDefinition as Class;
2117                         if (tc != null) {
2118                                 if (tc.InstanceConstructors == null) {
2119                                         // Default ctor will be generated later
2120                                         return true;
2121                                 }
2122
2123                                 foreach (var c in tc.InstanceConstructors) {
2124                                         if (c.ParameterInfo.IsEmpty) {
2125                                                 if ((c.ModFlags & Modifiers.PUBLIC) != 0)
2126                                                         return true;
2127                                         }
2128                                 }
2129
2130                                 return false;
2131                         }
2132
2133                         var found = MemberCache.FindMember (tdef,
2134                                 MemberFilter.Constructor (ParametersCompiled.EmptyReadOnlyParameters),
2135                                 BindingRestriction.DeclaredOnly | BindingRestriction.InstanceOnly);
2136
2137                         return found != null && (found.Modifiers & Modifiers.PUBLIC) != 0;
2138                 }
2139         }
2140
2141         /// <summary>
2142         ///   A generic method definition.
2143         /// </summary>
2144         public class GenericMethod : DeclSpace
2145         {
2146                 ParametersCompiled parameters;
2147
2148                 public GenericMethod (NamespaceEntry ns, DeclSpace parent, MemberName name,
2149                                       FullNamedExpression return_type, ParametersCompiled parameters)
2150                         : base (ns, parent, name, null)
2151                 {
2152                         this.parameters = parameters;
2153                 }
2154
2155                 public GenericMethod (NamespaceEntry ns, DeclSpace parent, MemberName name, TypeParameter[] tparams,
2156                                           FullNamedExpression return_type, ParametersCompiled parameters)
2157                         : this (ns, parent, name, return_type, parameters)
2158                 {
2159                         this.type_params = tparams;
2160                 }
2161
2162                 public override TypeParameter[] CurrentTypeParameters {
2163                         get {
2164                                 return base.type_params;
2165                         }
2166                 }
2167
2168                 public override TypeBuilder DefineType ()
2169                 {
2170                         throw new Exception ();
2171                 }
2172
2173                 public override void ApplyAttributeBuilder (Attribute a, MethodSpec ctor, byte[] cdata, PredefinedAttributes pa)
2174                 {
2175                         throw new NotSupportedException ();
2176                 }
2177
2178                 public override bool Define ()
2179                 {
2180                         throw new NotSupportedException ();
2181                 }
2182
2183                 /// <summary>
2184                 ///   Define and resolve the type parameters.
2185                 ///   We're called from Method.Define().
2186                 /// </summary>
2187                 public bool Define (MethodOrOperator m)
2188                 {
2189                         TypeParameterName[] names = MemberName.TypeArguments.GetDeclarations ();
2190                         string[] snames = new string [names.Length];
2191                         var block = m.Block;
2192                         for (int i = 0; i < names.Length; i++) {
2193                                 string type_argument_name = names[i].Name;
2194
2195                                 if (block == null) {
2196                                         int idx = parameters.GetParameterIndexByName (type_argument_name);
2197                                         if (idx >= 0) {
2198                                                 var b = m.Block;
2199                                                 if (b == null)
2200                                                         b = new ToplevelBlock (Compiler, Location);
2201
2202                                                 b.Error_AlreadyDeclaredTypeParameter (type_argument_name, parameters[i].Location);
2203                                         }
2204                                 } else {
2205                                         INamedBlockVariable variable = null;
2206                                         block.GetLocalName (type_argument_name, m.Block, ref variable);
2207                                         if (variable != null)
2208                                                 variable.Block.Error_AlreadyDeclaredTypeParameter (type_argument_name, variable.Location);
2209                                 }
2210
2211                                 snames[i] = type_argument_name;
2212                         }
2213
2214                         GenericTypeParameterBuilder[] gen_params = m.MethodBuilder.DefineGenericParameters (snames);
2215                         for (int i = 0; i < TypeParameters.Length; i++)
2216                                 TypeParameters [i].Define (gen_params [i], null);
2217
2218                         return true;
2219                 }
2220
2221                 public void EmitAttributes ()
2222                 {
2223                         if (OptAttributes != null)
2224                                 OptAttributes.Emit ();
2225                 }
2226
2227                 public override string GetSignatureForError ()
2228                 {
2229                         return base.GetSignatureForError () + parameters.GetSignatureForError ();
2230                 }
2231
2232                 public override AttributeTargets AttributeTargets {
2233                         get {
2234                                 return AttributeTargets.Method | AttributeTargets.ReturnValue;
2235                         }
2236                 }
2237
2238                 public override string DocCommentHeader {
2239                         get { return "M:"; }
2240                 }
2241
2242                 public new void VerifyClsCompliance ()
2243                 {
2244                         foreach (TypeParameter tp in TypeParameters) {
2245                                 tp.VerifyClsCompliance ();
2246                         }
2247                 }
2248         }
2249
2250         public partial class TypeManager
2251         {
2252                 public static Variance CheckTypeVariance (TypeSpec t, Variance expected, IMemberContext member)
2253                 {
2254                         var tp = t as TypeParameterSpec;
2255                         if (tp != null) {
2256                                 Variance v = tp.Variance;
2257                                 if (expected == Variance.None && v != expected ||
2258                                         expected == Variance.Covariant && v == Variance.Contravariant ||
2259                                         expected == Variance.Contravariant && v == Variance.Covariant) {
2260                                         ((TypeParameter)tp.MemberDefinition).ErrorInvalidVariance (member, expected);
2261                                 }
2262
2263                                 return expected;
2264                         }
2265
2266                         if (t.TypeArguments.Length > 0) {
2267                                 var targs_definition = t.MemberDefinition.TypeParameters;
2268                                 TypeSpec[] targs = GetTypeArguments (t);
2269                                 for (int i = 0; i < targs.Length; ++i) {
2270                                         Variance v = targs_definition[i].Variance;
2271                                         CheckTypeVariance (targs[i], (Variance) ((int)v * (int)expected), member);
2272                                 }
2273
2274                                 return expected;
2275                         }
2276
2277                         if (t.IsArray)
2278                                 return CheckTypeVariance (GetElementType (t), expected, member);
2279
2280                         return Variance.None;
2281                 }
2282         }
2283
2284         //
2285         // Implements C# type inference
2286         //
2287         class TypeInference
2288         {
2289                 //
2290                 // Tracks successful rate of type inference
2291                 //
2292                 int score = int.MaxValue;
2293                 readonly Arguments arguments;
2294                 readonly int arg_count;
2295
2296                 public TypeInference (Arguments arguments)
2297                 {
2298                         this.arguments = arguments;
2299                         if (arguments != null)
2300                                 arg_count = arguments.Count;
2301                 }
2302
2303                 public int InferenceScore {
2304                         get {
2305                                 return score;
2306                         }
2307                 }
2308
2309                 public TypeSpec[] InferMethodArguments (ResolveContext ec, MethodSpec method)
2310                 {
2311                         var method_generic_args = method.GenericDefinition.TypeParameters;
2312                         TypeInferenceContext context = new TypeInferenceContext (method_generic_args);
2313                         if (!context.UnfixedVariableExists)
2314                                 return TypeSpec.EmptyTypes;
2315
2316                         AParametersCollection pd = method.Parameters;
2317                         if (!InferInPhases (ec, context, pd))
2318                                 return null;
2319
2320                         return context.InferredTypeArguments;
2321                 }
2322
2323                 //
2324                 // Implements method type arguments inference
2325                 //
2326                 bool InferInPhases (ResolveContext ec, TypeInferenceContext tic, AParametersCollection methodParameters)
2327                 {
2328                         int params_arguments_start;
2329                         if (methodParameters.HasParams) {
2330                                 params_arguments_start = methodParameters.Count - 1;
2331                         } else {
2332                                 params_arguments_start = arg_count;
2333                         }
2334
2335                         TypeSpec [] ptypes = methodParameters.Types;
2336
2337                         //
2338                         // The first inference phase
2339                         //
2340                         TypeSpec method_parameter = null;
2341                         for (int i = 0; i < arg_count; i++) {
2342                                 Argument a = arguments [i];
2343                                 if (a == null)
2344                                         continue;
2345
2346                                 if (i < params_arguments_start) {
2347                                         method_parameter = methodParameters.Types [i];
2348                                 } else if (i == params_arguments_start) {
2349                                         if (arg_count == params_arguments_start + 1 && TypeManager.HasElementType (a.Type))
2350                                                 method_parameter = methodParameters.Types [params_arguments_start];
2351                                         else
2352                                                 method_parameter = TypeManager.GetElementType (methodParameters.Types [params_arguments_start]);
2353
2354                                         ptypes = (TypeSpec[]) ptypes.Clone ();
2355                                         ptypes [i] = method_parameter;
2356                                 }
2357
2358                                 //
2359                                 // When a lambda expression, an anonymous method
2360                                 // is used an explicit argument type inference takes a place
2361                                 //
2362                                 AnonymousMethodExpression am = a.Expr as AnonymousMethodExpression;
2363                                 if (am != null) {
2364                                         if (am.ExplicitTypeInference (ec, tic, method_parameter))
2365                                                 --score;
2366                                         continue;
2367                                 }
2368
2369                                 if (a.IsByRef) {
2370                                         score -= tic.ExactInference (a.Type, method_parameter);
2371                                         continue;
2372                                 }
2373
2374                                 if (a.Expr.Type == InternalType.Null)
2375                                         continue;
2376
2377                                 if (TypeManager.IsValueType (method_parameter)) {
2378                                         score -= tic.LowerBoundInference (a.Type, method_parameter);
2379                                         continue;
2380                                 }
2381
2382                                 //
2383                                 // Otherwise an output type inference is made
2384                                 //
2385                                 score -= tic.OutputTypeInference (ec, a.Expr, method_parameter);
2386                         }
2387
2388                         //
2389                         // Part of the second phase but because it happens only once
2390                         // we don't need to call it in cycle
2391                         //
2392                         bool fixed_any = false;
2393                         if (!tic.FixIndependentTypeArguments (ec, ptypes, ref fixed_any))
2394                                 return false;
2395
2396                         return DoSecondPhase (ec, tic, ptypes, !fixed_any);
2397                 }
2398
2399                 bool DoSecondPhase (ResolveContext ec, TypeInferenceContext tic, TypeSpec[] methodParameters, bool fixDependent)
2400                 {
2401                         bool fixed_any = false;
2402                         if (fixDependent && !tic.FixDependentTypes (ec, ref fixed_any))
2403                                 return false;
2404
2405                         // If no further unfixed type variables exist, type inference succeeds
2406                         if (!tic.UnfixedVariableExists)
2407                                 return true;
2408
2409                         if (!fixed_any && fixDependent)
2410                                 return false;
2411
2412                         // For all arguments where the corresponding argument output types
2413                         // contain unfixed type variables but the input types do not,
2414                         // an output type inference is made
2415                         for (int i = 0; i < arg_count; i++) {
2416
2417                                 // Align params arguments
2418                                 TypeSpec t_i = methodParameters [i >= methodParameters.Length ? methodParameters.Length - 1: i];
2419
2420                                 if (!TypeManager.IsDelegateType (t_i)) {
2421                                         if (t_i.GetDefinition () != TypeManager.expression_type)
2422                                                 continue;
2423
2424                                         t_i = TypeManager.GetTypeArguments (t_i) [0];
2425                                 }
2426
2427                                 var mi = Delegate.GetInvokeMethod (ec.Compiler, t_i);
2428                                 TypeSpec rtype = mi.ReturnType;
2429
2430                                 if (tic.IsReturnTypeNonDependent (ec, mi, rtype))
2431                                         score -= tic.OutputTypeInference (ec, arguments [i].Expr, t_i);
2432                         }
2433
2434
2435                         return DoSecondPhase (ec, tic, methodParameters, true);
2436                 }
2437         }
2438
2439         public class TypeInferenceContext
2440         {
2441                 enum BoundKind
2442                 {
2443                         Exact   = 0,
2444                         Lower   = 1,
2445                         Upper   = 2
2446                 }
2447
2448                 class BoundInfo : IEquatable<BoundInfo>
2449                 {
2450                         public readonly TypeSpec Type;
2451                         public readonly BoundKind Kind;
2452
2453                         public BoundInfo (TypeSpec type, BoundKind kind)
2454                         {
2455                                 this.Type = type;
2456                                 this.Kind = kind;
2457                         }
2458
2459                         public override int GetHashCode ()
2460                         {
2461                                 return Type.GetHashCode ();
2462                         }
2463
2464                         #region IEquatable<BoundInfo> Members
2465
2466                         public bool Equals (BoundInfo other)
2467                         {
2468                                 return Type == other.Type && Kind == other.Kind;
2469                         }
2470
2471                         #endregion
2472                 }
2473
2474                 readonly TypeSpec[] tp_args;
2475                 readonly TypeSpec[] fixed_types;
2476                 readonly List<BoundInfo>[] bounds;
2477                 bool failed;
2478
2479                 // TODO MemberCache: Could it be TypeParameterSpec[] ??
2480                 public TypeInferenceContext (TypeSpec[] typeArguments)
2481                 {
2482                         if (typeArguments.Length == 0)
2483                                 throw new ArgumentException ("Empty generic arguments");
2484
2485                         fixed_types = new TypeSpec [typeArguments.Length];
2486                         for (int i = 0; i < typeArguments.Length; ++i) {
2487                                 if (typeArguments [i].IsGenericParameter) {
2488                                         if (bounds == null) {
2489                                                 bounds = new List<BoundInfo> [typeArguments.Length];
2490                                                 tp_args = new TypeSpec [typeArguments.Length];
2491                                         }
2492                                         tp_args [i] = typeArguments [i];
2493                                 } else {
2494                                         fixed_types [i] = typeArguments [i];
2495                                 }
2496                         }
2497                 }
2498
2499                 //
2500                 // Used together with AddCommonTypeBound fo implement
2501                 // 7.4.2.13 Finding the best common type of a set of expressions
2502                 //
2503                 public TypeInferenceContext ()
2504                 {
2505                         fixed_types = new TypeSpec [1];
2506                         tp_args = new TypeSpec [1];
2507                         tp_args[0] = InternalType.Arglist; // it can be any internal type
2508                         bounds = new List<BoundInfo> [1];
2509                 }
2510
2511                 public TypeSpec[] InferredTypeArguments {
2512                         get {
2513                                 return fixed_types;
2514                         }
2515                 }
2516
2517                 public void AddCommonTypeBound (TypeSpec type)
2518                 {
2519                         AddToBounds (new BoundInfo (type, BoundKind.Lower), 0);
2520                 }
2521
2522                 void AddToBounds (BoundInfo bound, int index)
2523                 {
2524                         //
2525                         // Some types cannot be used as type arguments
2526                         //
2527                         if (bound.Type == TypeManager.void_type || bound.Type.IsPointer)
2528                                 return;
2529
2530                         var a = bounds [index];
2531                         if (a == null) {
2532                                 a = new List<BoundInfo> (2);
2533                                 a.Add (bound);
2534                                 bounds [index] = a;
2535                                 return;
2536                         }
2537
2538                         if (a.Contains (bound))
2539                                 return;
2540
2541                         a.Add (bound);
2542                 }
2543
2544                 bool AllTypesAreFixed (TypeSpec[] types)
2545                 {
2546                         foreach (TypeSpec t in types) {
2547                                 if (t.IsGenericParameter) {
2548                                         if (!IsFixed (t))
2549                                                 return false;
2550                                         continue;
2551                                 }
2552
2553                                 if (TypeManager.IsGenericType (t))
2554                                         return AllTypesAreFixed (TypeManager.GetTypeArguments (t));
2555                         }
2556
2557                         return true;
2558                 }
2559
2560                 //
2561                 // 26.3.3.8 Exact Inference
2562                 //
2563                 public int ExactInference (TypeSpec u, TypeSpec v)
2564                 {
2565                         // If V is an array type
2566                         if (v.IsArray) {
2567                                 if (!u.IsArray)
2568                                         return 0;
2569
2570                                 // TODO MemberCache: GetMetaInfo ()
2571                                 if (u.GetMetaInfo ().GetArrayRank () != v.GetMetaInfo ().GetArrayRank ())
2572                                         return 0;
2573
2574                                 return ExactInference (TypeManager.GetElementType (u), TypeManager.GetElementType (v));
2575                         }
2576
2577                         // If V is constructed type and U is constructed type
2578                         if (TypeManager.IsGenericType (v)) {
2579                                 if (!TypeManager.IsGenericType (u))
2580                                         return 0;
2581
2582                                 TypeSpec [] ga_u = TypeManager.GetTypeArguments (u);
2583                                 TypeSpec [] ga_v = TypeManager.GetTypeArguments (v);
2584                                 if (ga_u.Length != ga_v.Length)
2585                                         return 0;
2586
2587                                 int score = 0;
2588                                 for (int i = 0; i < ga_u.Length; ++i)
2589                                         score += ExactInference (ga_u [i], ga_v [i]);
2590
2591                                 return score > 0 ? 1 : 0;
2592                         }
2593
2594                         // If V is one of the unfixed type arguments
2595                         int pos = IsUnfixed (v);
2596                         if (pos == -1)
2597                                 return 0;
2598
2599                         AddToBounds (new BoundInfo (u, BoundKind.Exact), pos);
2600                         return 1;
2601                 }
2602
2603                 public bool FixAllTypes (ResolveContext ec)
2604                 {
2605                         for (int i = 0; i < tp_args.Length; ++i) {
2606                                 if (!FixType (ec, i))
2607                                         return false;
2608                         }
2609                         return true;
2610                 }
2611
2612                 //
2613                 // All unfixed type variables Xi are fixed for which all of the following hold:
2614                 // a, There is at least one type variable Xj that depends on Xi
2615                 // b, Xi has a non-empty set of bounds
2616                 //
2617                 public bool FixDependentTypes (ResolveContext ec, ref bool fixed_any)
2618                 {
2619                         for (int i = 0; i < tp_args.Length; ++i) {
2620                                 if (fixed_types[i] != null)
2621                                         continue;
2622
2623                                 if (bounds[i] == null)
2624                                         continue;
2625
2626                                 if (!FixType (ec, i))
2627                                         return false;
2628
2629                                 fixed_any = true;
2630                         }
2631
2632                         return true;
2633                 }
2634
2635                 //
2636                 // All unfixed type variables Xi which depend on no Xj are fixed
2637                 //
2638                 public bool FixIndependentTypeArguments (ResolveContext ec, TypeSpec[] methodParameters, ref bool fixed_any)
2639                 {
2640                         var types_to_fix = new List<TypeSpec> (tp_args);
2641                         for (int i = 0; i < methodParameters.Length; ++i) {
2642                                 TypeSpec t = methodParameters[i];
2643
2644                                 if (!TypeManager.IsDelegateType (t)) {
2645                                         if (TypeManager.expression_type == null || t.MemberDefinition != TypeManager.expression_type.MemberDefinition)
2646                                                 continue;
2647
2648                                         t =  TypeManager.GetTypeArguments (t) [0];
2649                                 }
2650
2651                                 if (t.IsGenericParameter)
2652                                         continue;
2653
2654                                 var invoke = Delegate.GetInvokeMethod (ec.Compiler, t);
2655                                 TypeSpec rtype = invoke.ReturnType;
2656                                 if (!rtype.IsGenericParameter && !TypeManager.IsGenericType (rtype))
2657                                         continue;
2658
2659                                 // Remove dependent types, they cannot be fixed yet
2660                                 RemoveDependentTypes (types_to_fix, rtype);
2661                         }
2662
2663                         foreach (TypeSpec t in types_to_fix) {
2664                                 if (t == null)
2665                                         continue;
2666
2667                                 int idx = IsUnfixed (t);
2668                                 if (idx >= 0 && !FixType (ec, idx)) {
2669                                         return false;
2670                                 }
2671                         }
2672
2673                         fixed_any = types_to_fix.Count > 0;
2674                         return true;
2675                 }
2676
2677                 //
2678                 // 26.3.3.10 Fixing
2679                 //
2680                 public bool FixType (ResolveContext ec, int i)
2681                 {
2682                         // It's already fixed
2683                         if (fixed_types[i] != null)
2684                                 throw new InternalErrorException ("Type argument has been already fixed");
2685
2686                         if (failed)
2687                                 return false;
2688
2689                         var candidates = bounds [i];
2690                         if (candidates == null)
2691                                 return false;
2692
2693                         if (candidates.Count == 1) {
2694                                 TypeSpec t = candidates[0].Type;
2695                                 if (t == InternalType.Null)
2696                                         return false;
2697
2698                                 fixed_types [i] = t;
2699                                 return true;
2700                         }
2701
2702                         //
2703                         // Determines a unique type from which there is
2704                         // a standard implicit conversion to all the other
2705                         // candidate types.
2706                         //
2707                         TypeSpec best_candidate = null;
2708                         int cii;
2709                         int candidates_count = candidates.Count;
2710                         for (int ci = 0; ci < candidates_count; ++ci) {
2711                                 BoundInfo bound = candidates [ci];
2712                                 for (cii = 0; cii < candidates_count; ++cii) {
2713                                         if (cii == ci)
2714                                                 continue;
2715
2716                                         BoundInfo cbound = candidates[cii];
2717
2718                                         // Same type parameters with different bounds
2719                                         if (cbound.Type == bound.Type) {
2720                                                 if (bound.Kind != BoundKind.Exact)
2721                                                         bound = cbound;
2722
2723                                                 continue;
2724                                         }
2725
2726                                         if (bound.Kind == BoundKind.Exact || cbound.Kind == BoundKind.Exact) {
2727                                                 if (cbound.Kind == BoundKind.Lower) {
2728                                                         if (!Convert.ImplicitConversionExists (ec, new TypeExpression (cbound.Type, Location.Null), bound.Type)) {
2729                                                                 break;
2730                                                         }
2731
2732                                                         continue;
2733                                                 }
2734                                                 if (cbound.Kind == BoundKind.Upper) {
2735                                                         if (!Convert.ImplicitConversionExists (ec, new TypeExpression (bound.Type, Location.Null), cbound.Type)) {
2736                                                                 break;
2737                                                         }
2738
2739                                                         continue;
2740                                                 }
2741
2742                                                 if (bound.Kind != BoundKind.Exact) {
2743                                                         if (!Convert.ImplicitConversionExists (ec, new TypeExpression (bound.Type, Location.Null), cbound.Type)) {
2744                                                                 break;
2745                                                         }
2746
2747                                                         bound = cbound;
2748                                                         continue;
2749                                                 }
2750
2751                                                 break;
2752                                         }
2753
2754                                         if (bound.Kind == BoundKind.Lower) {
2755                                                 if (cbound.Kind == BoundKind.Lower) {
2756                                                         if (!Convert.ImplicitConversionExists (ec, new TypeExpression (cbound.Type, Location.Null), bound.Type)) {
2757                                                                 break;
2758                                                         }
2759                                                 } else {
2760                                                         if (!Convert.ImplicitConversionExists (ec, new TypeExpression (bound.Type, Location.Null), cbound.Type)) {
2761                                                                 break;
2762                                                         }
2763
2764                                                         bound = cbound;
2765                                                 }
2766
2767                                                 continue;
2768                                         }
2769
2770                                         if (bound.Kind == BoundKind.Upper) {
2771                                                 if (!Convert.ImplicitConversionExists (ec, new TypeExpression (bound.Type, Location.Null), cbound.Type)) {
2772                                                         break;
2773                                                 }
2774                                         } else {
2775                                                 throw new NotImplementedException ("variance conversion");
2776                                         }
2777                                 }
2778
2779                                 if (cii != candidates_count)
2780                                         continue;
2781
2782                                 //
2783                                 // We already have the best candidate, break if thet are different
2784                                 //
2785                                 // Dynamic is never ambiguous as we prefer dynamic over other best candidate types
2786                                 //
2787                                 if (best_candidate != null) {
2788
2789                                         if (best_candidate == InternalType.Dynamic)
2790                                                 continue;
2791
2792                                         if (bound.Type != InternalType.Dynamic && best_candidate != bound.Type)
2793                                                 return false;
2794                                 }
2795
2796                                 best_candidate = bound.Type;
2797                         }
2798
2799                         if (best_candidate == null)
2800                                 return false;
2801
2802                         fixed_types[i] = best_candidate;
2803                         return true;
2804                 }
2805
2806                 //
2807                 // Uses inferred or partially infered types to inflate delegate type argument. Returns
2808                 // null when type parameter has not been fixed
2809                 //
2810                 public TypeSpec InflateGenericArgument (TypeSpec parameter)
2811                 {
2812                         var tp = parameter as TypeParameterSpec;
2813                         if (tp != null) {
2814                                 //
2815                                 // Type inference works on generic arguments (MVAR) only
2816                                 //
2817                                 if (!tp.IsMethodOwned)
2818                                         return parameter;
2819
2820                                 //
2821                                 // Ensure the type parameter belongs to same container
2822                                 //
2823                                 if (tp.DeclaredPosition < tp_args.Length && tp_args[tp.DeclaredPosition] == parameter)
2824                                         return fixed_types[tp.DeclaredPosition] ?? parameter;
2825
2826                                 return parameter;
2827                         }
2828
2829                         var gt = parameter as InflatedTypeSpec;
2830                         if (gt != null) {
2831                                 var inflated_targs = new TypeSpec [gt.TypeArguments.Length];
2832                                 for (int ii = 0; ii < inflated_targs.Length; ++ii) {
2833                                         var inflated = InflateGenericArgument (gt.TypeArguments [ii]);
2834                                         if (inflated == null)
2835                                                 return null;
2836
2837                                         inflated_targs[ii] = inflated;
2838                                 }
2839
2840                                 return gt.GetDefinition ().MakeGenericType (inflated_targs);
2841                         }
2842
2843                         return parameter;
2844                 }
2845
2846                 //
2847                 // Tests whether all delegate input arguments are fixed and generic output type
2848                 // requires output type inference
2849                 //
2850                 public bool IsReturnTypeNonDependent (ResolveContext ec, MethodSpec invoke, TypeSpec returnType)
2851                 {
2852                         if (returnType.IsGenericParameter) {
2853                                 if (IsFixed (returnType))
2854                                     return false;
2855                         } else if (TypeManager.IsGenericType (returnType)) {
2856                                 if (TypeManager.IsDelegateType (returnType)) {
2857                                         invoke = Delegate.GetInvokeMethod (ec.Compiler, returnType);
2858                                         return IsReturnTypeNonDependent (ec, invoke, invoke.ReturnType);
2859                                 }
2860
2861                                 TypeSpec[] g_args = TypeManager.GetTypeArguments (returnType);
2862
2863                                 // At least one unfixed return type has to exist
2864                                 if (AllTypesAreFixed (g_args))
2865                                         return false;
2866                         } else {
2867                                 return false;
2868                         }
2869
2870                         // All generic input arguments have to be fixed
2871                         AParametersCollection d_parameters = invoke.Parameters;
2872                         return AllTypesAreFixed (d_parameters.Types);
2873                 }
2874
2875                 bool IsFixed (TypeSpec type)
2876                 {
2877                         return IsUnfixed (type) == -1;
2878                 }
2879
2880                 int IsUnfixed (TypeSpec type)
2881                 {
2882                         if (!type.IsGenericParameter)
2883                                 return -1;
2884
2885                         for (int i = 0; i < tp_args.Length; ++i) {
2886                                 if (tp_args[i] == type) {
2887                                         if (fixed_types[i] != null)
2888                                                 break;
2889
2890                                         return i;
2891                                 }
2892                         }
2893
2894                         return -1;
2895                 }
2896
2897                 //
2898                 // 26.3.3.9 Lower-bound Inference
2899                 //
2900                 public int LowerBoundInference (TypeSpec u, TypeSpec v)
2901                 {
2902                         return LowerBoundInference (u, v, false);
2903                 }
2904
2905                 //
2906                 // Lower-bound (false) or Upper-bound (true) inference based on inversed argument
2907                 //
2908                 int LowerBoundInference (TypeSpec u, TypeSpec v, bool inversed)
2909                 {
2910                         // If V is one of the unfixed type arguments
2911                         int pos = IsUnfixed (v);
2912                         if (pos != -1) {
2913                                 AddToBounds (new BoundInfo (u, inversed ? BoundKind.Upper : BoundKind.Lower), pos);
2914                                 return 1;
2915                         }
2916
2917                         // If U is an array type
2918                         var u_ac = u as ArrayContainer;
2919                         if (u_ac != null) {
2920                                 var v_ac = v as ArrayContainer;
2921                                 if (v_ac != null) {
2922                                         if (u_ac.Rank != v_ac.Rank)
2923                                                 return 0;
2924
2925                                         if (TypeManager.IsValueType (u_ac.Element))
2926                                                 return ExactInference (u_ac.Element, v_ac.Element);
2927
2928                                         return LowerBoundInference (u_ac.Element, v_ac.Element, inversed);
2929                                 }
2930
2931                                 if (u_ac.Rank != 1)
2932                                         return 0;
2933
2934                                 if (TypeManager.IsGenericType (v)) {
2935                                         TypeSpec g_v = v.GetDefinition ();
2936                                         if (g_v != TypeManager.generic_ilist_type &&
2937                                                 g_v != TypeManager.generic_icollection_type &&
2938                                                 g_v != TypeManager.generic_ienumerable_type)
2939                                                 return 0;
2940
2941                                         var v_i = TypeManager.GetTypeArguments (v) [0];
2942                                         if (TypeManager.IsValueType (u_ac.Element))
2943                                                 return ExactInference (u_ac.Element, v_i);
2944
2945                                         return LowerBoundInference (u_ac.Element, v_i);
2946                                 }
2947                         } else if (TypeManager.IsGenericType (v)) {
2948                                 //
2949                                 // if V is a constructed type C<V1..Vk> and there is a unique type C<U1..Uk>
2950                                 // such that U is identical to, inherits from (directly or indirectly),
2951                                 // or implements (directly or indirectly) C<U1..Uk>
2952                                 //
2953                                 var u_candidates = new List<TypeSpec> ();
2954                                 var open_v = v.MemberDefinition;
2955
2956                                 for (TypeSpec t = u; t != null; t = t.BaseType) {
2957                                         if (open_v == t.MemberDefinition)
2958                                                 u_candidates.Add (t);
2959
2960                                         //
2961                                         // Using this trick for dynamic type inference, the spec says the type arguments are "unknown" but
2962                                         // that would complicate the process a lot, instead I treat them as dynamic
2963                                         //
2964                                         if (t == InternalType.Dynamic)
2965                                                 u_candidates.Add (t);
2966
2967                                         if (t.Interfaces != null) {
2968                                                 foreach (var iface in t.Interfaces) {
2969                                                         if (open_v == iface.MemberDefinition)
2970                                                                 u_candidates.Add (iface);
2971                                                 }
2972                                         }
2973                                 }
2974
2975                                 TypeSpec [] unique_candidate_targs = null;
2976                                 TypeSpec[] ga_v = TypeManager.GetTypeArguments (v);
2977                                 foreach (TypeSpec u_candidate in u_candidates) {
2978                                         //
2979                                         // The unique set of types U1..Uk means that if we have an interface I<T>,
2980                                         // class U : I<int>, I<long> then no type inference is made when inferring
2981                                         // type I<T> by applying type U because T could be int or long
2982                                         //
2983                                         if (unique_candidate_targs != null) {
2984                                                 TypeSpec[] second_unique_candidate_targs = TypeManager.GetTypeArguments (u_candidate);
2985                                                 if (TypeSpecComparer.Equals (unique_candidate_targs, second_unique_candidate_targs)) {
2986                                                         unique_candidate_targs = second_unique_candidate_targs;
2987                                                         continue;
2988                                                 }
2989
2990                                                 //
2991                                                 // This should always cause type inference failure
2992                                                 //
2993                                                 failed = true;
2994                                                 return 1;
2995                                         }
2996
2997                                         //
2998                                         // A candidate is dynamic type expression, to simplify things use dynamic
2999                                         // for all type parameter of this type. For methods like this one
3000                                         //
3001                                         // void M<T, U> (IList<T>, IList<U[]>)
3002                                         //
3003                                         // dynamic becomes both T and U when the arguments are of dynamic type
3004                                         //
3005                                         if (u_candidate == InternalType.Dynamic) {
3006                                                 unique_candidate_targs = new TypeSpec[ga_v.Length];
3007                                                 for (int i = 0; i < unique_candidate_targs.Length; ++i)
3008                                                         unique_candidate_targs[i] = u_candidate;
3009                                         } else {
3010                                                 unique_candidate_targs = TypeManager.GetTypeArguments (u_candidate);
3011                                         }
3012                                 }
3013
3014                                 if (unique_candidate_targs != null) {
3015                                         var ga_open_v = open_v.TypeParameters;
3016                                         int score = 0;
3017                                         for (int i = 0; i < unique_candidate_targs.Length; ++i) {
3018                                                 Variance variance = ga_open_v [i].Variance;
3019
3020                                                 TypeSpec u_i = unique_candidate_targs [i];
3021                                                 if (variance == Variance.None || TypeManager.IsValueType (u_i)) {
3022                                                         if (ExactInference (u_i, ga_v [i]) == 0)
3023                                                                 ++score;
3024                                                 } else {
3025                                                         bool upper_bound = (variance == Variance.Contravariant && !inversed) ||
3026                                                                 (variance == Variance.Covariant && inversed);
3027
3028                                                         if (LowerBoundInference (u_i, ga_v [i], upper_bound) == 0)
3029                                                                 ++score;
3030                                                 }
3031                                         }
3032                                         return score;
3033                                 }
3034                         }
3035
3036                         return 0;
3037                 }
3038
3039                 //
3040                 // 26.3.3.6 Output Type Inference
3041                 //
3042                 public int OutputTypeInference (ResolveContext ec, Expression e, TypeSpec t)
3043                 {
3044                         // If e is a lambda or anonymous method with inferred return type
3045                         AnonymousMethodExpression ame = e as AnonymousMethodExpression;
3046                         if (ame != null) {
3047                                 TypeSpec rt = ame.InferReturnType (ec, this, t);
3048                                 var invoke = Delegate.GetInvokeMethod (ec.Compiler, t);
3049
3050                                 if (rt == null) {
3051                                         AParametersCollection pd = invoke.Parameters;
3052                                         return ame.Parameters.Count == pd.Count ? 1 : 0;
3053                                 }
3054
3055                                 TypeSpec rtype = invoke.ReturnType;
3056                                 return LowerBoundInference (rt, rtype) + 1;
3057                         }
3058
3059                         //
3060                         // if E is a method group and T is a delegate type or expression tree type
3061                         // return type Tb with parameter types T1..Tk and return type Tb, and overload
3062                         // resolution of E with the types T1..Tk yields a single method with return type U,
3063                         // then a lower-bound inference is made from U for Tb.
3064                         //
3065                         if (e is MethodGroupExpr) {
3066                                 if (!TypeManager.IsDelegateType (t)) {
3067                                         if (TypeManager.expression_type == null || t.MemberDefinition != TypeManager.expression_type.MemberDefinition)
3068                                                 return 0;
3069
3070                                         t = TypeManager.GetTypeArguments (t)[0];
3071                                 }
3072
3073                                 var invoke = Delegate.GetInvokeMethod (ec.Compiler, t);
3074                                 TypeSpec rtype = invoke.ReturnType;
3075
3076                                 if (!rtype.IsGenericParameter && !TypeManager.IsGenericType (rtype))
3077                                         return 0;
3078
3079                                 // LAMESPEC: Standard does not specify that all methodgroup arguments
3080                                 // has to be fixed but it does not specify how to do recursive type inference
3081                                 // either. We choose the simple option and infer return type only
3082                                 // if all delegate generic arguments are fixed.
3083                                 TypeSpec[] param_types = new TypeSpec [invoke.Parameters.Count];
3084                                 for (int i = 0; i < param_types.Length; ++i) {
3085                                         var inflated = InflateGenericArgument (invoke.Parameters.Types[i]);
3086                                         if (inflated == null)
3087                                                 return 0;
3088
3089                                         if (IsUnfixed (inflated) >= 0)
3090                                                 return 0;
3091
3092                                         param_types[i] = inflated;
3093                                 }
3094
3095                                 MethodGroupExpr mg = (MethodGroupExpr) e;
3096                                 Arguments args = DelegateCreation.CreateDelegateMethodArguments (invoke.Parameters, param_types, e.Location);
3097                                 mg = mg.OverloadResolve (ec, ref args, null, OverloadResolver.Restrictions.CovariantDelegate | OverloadResolver.Restrictions.ProbingOnly);
3098                                 if (mg == null)
3099                                         return 0;
3100
3101                                 return LowerBoundInference (mg.BestCandidateReturnType, rtype) + 1;
3102                         }
3103
3104                         //
3105                         // if e is an expression with type U, then
3106                         // a lower-bound inference is made from U for T
3107                         //
3108                         return LowerBoundInference (e.Type, t) * 2;
3109                 }
3110
3111                 void RemoveDependentTypes (List<TypeSpec> types, TypeSpec returnType)
3112                 {
3113                         int idx = IsUnfixed (returnType);
3114                         if (idx >= 0) {
3115                                 types [idx] = null;
3116                                 return;
3117                         }
3118
3119                         if (TypeManager.IsGenericType (returnType)) {
3120                                 foreach (TypeSpec t in TypeManager.GetTypeArguments (returnType)) {
3121                                         RemoveDependentTypes (types, t);
3122                                 }
3123                         }
3124                 }
3125
3126                 public bool UnfixedVariableExists {
3127                         get {
3128                                 foreach (TypeSpec ut in fixed_types) {
3129                                         if (ut == null)
3130                                                 return true;
3131                                 }
3132
3133                                 return false;
3134                         }
3135                 }
3136         }
3137 }