mcs/mcs/membercache.cs

   1 //
   2 // membercache.cs: A container for all member lookups
   3 //
   4 // Author: Miguel de Icaza (miguel@gnu.org)
   5 //         Marek Safar (marek.safar@gmail.com)
   6 //
   7 // Dual licensed under the terms of the MIT X11 or GNU GPL
   8 //
   9 // Copyright 2001 Ximian, Inc (http://www.ximian.com)
  10 // Copyright 2004-2010 Novell, Inc
  11 //
  12 //
  13
  14 using System;
  15 using System.Text;
  16 using System.Collections.Generic;
  17 using System.Globalization;
  18 using System.Reflection.Emit;
  19 using System.Reflection;
  20 using System.Linq;
  21
  22 namespace Mono.CSharp {
  23
  24         [Flags]
  25         public enum MemberKind
  26         {
  27                 Constructor = 1,
  28                 Event = 1 << 1,
  29                 Field = 1 << 2,
  30                 Method = 1 << 3,
  31                 Property = 1 << 4,
  32                 Indexer = 1 << 5,
  33                 Operator = 1 << 6,
  34                 Destructor      = 1 << 7,
  35
  36                 Class           = 1 << 11,
  37                 Struct          = 1 << 12,
  38                 Delegate        = 1 << 13,
  39                 Enum            = 1 << 14,
  40                 Interface       = 1 << 15,
  41                 TypeParameter = 1 << 16,
  42
  43                 ArrayType = 1 << 19,
  44                 PointerType = 1 << 20,
  45                 InternalCompilerType = 1 << 21,
  46
  47                 NestedMask = Class | Struct | Delegate | Enum | Interface,
  48                 GenericMask = Method | Class | Struct | Delegate | Interface,
  49                 MaskType = Constructor | Event | Field | Method | Property | Indexer | Operator | Destructor | NestedMask,
  50                 All = MaskType
  51         }
  52
  53         [Flags]
  54         public enum BindingRestriction
  55         {
  56                 None = 0,
  57
  58                 // Inspect only queried type members
  59                 DeclaredOnly = 1 << 1,
  60
  61                 // Exclude static
  62                 InstanceOnly = 1 << 2,
  63
  64                 NoAccessors = 1 << 3
  65         }
  66
  67         public struct MemberFilter : IEquatable<MemberSpec>
  68         {
  69                 public readonly string Name;
  70                 public readonly MemberKind Kind;
  71                 public readonly AParametersCollection Parameters;
  72                 public readonly TypeSpec MemberType;
  73
  74                 int arity; // -1 to ignore the check
  75
  76                 private MemberFilter (string name, MemberKind kind)
  77                 {
  78                         Name = name;
  79                         Kind = kind;
  80                         Parameters = null;
  81                         MemberType = null;
  82                         arity = -1;
  83                 }
  84
  85                 public MemberFilter (MethodSpec m)
  86                 {
  87                         Name = m.Name;
  88                         Kind = MemberKind.Method;
  89                         Parameters = m.Parameters;
  90                         MemberType = m.ReturnType;
  91                         arity = m.Arity;
  92                 }
  93
  94                 public MemberFilter (string name, int arity, MemberKind kind, AParametersCollection param, TypeSpec type)
  95                 {
  96                         Name = name;
  97                         Kind = kind;
  98                         Parameters = param;
  99                         MemberType = type;
 100                         this.arity = arity;
 101                 }
 102
 103                 public static MemberFilter Constructor (AParametersCollection param)
 104                 {
 105                         return new MemberFilter (System.Reflection.ConstructorInfo.ConstructorName, 0, MemberKind.Constructor, param, null);
 106                 }
 107
 108                 public static MemberFilter Property (string name, TypeSpec type)
 109                 {
 110                         return new MemberFilter (name, 0, MemberKind.Property, null, type);
 111                 }
 112
 113                 public static MemberFilter Field (string name, TypeSpec type)
 114                 {
 115                         return new MemberFilter (name, 0, MemberKind.Field, null, type);
 116                 }
 117
 118                 public static MemberFilter Method (string name, int arity, AParametersCollection param, TypeSpec type)
 119                 {
 120                         return new MemberFilter (name, arity, MemberKind.Method, param, type);
 121                 }
 122
 123                 #region IEquatable<MemberSpec> Members
 124
 125                 public bool Equals (MemberSpec other)
 126                 {
 127                         // Is the member of the correct type ?
 128                         // TODO: Isn't this redundant ?
 129                         if ((other.Kind & Kind & MemberKind.MaskType) == 0)
 130                                 return false;
 131
 132                         // Check arity when not disabled
 133                         if (arity >= 0 && arity != other.Arity)
 134                                 return false;
 135
 136                         if (Parameters != null) {
 137                                 if (other is IParametersMember) {
 138                                         var other_param = ((IParametersMember) other).Parameters;
 139                                         if (!TypeSpecComparer.Override.IsEqual (Parameters, other_param))
 140                                                 return false;
 141                                 } else {
 142                                         return false;
 143                                 }
 144                         }
 145
 146                         if (MemberType != null) {
 147                                 if (other is IInterfaceMemberSpec) {
 148                                         var other_type = ((IInterfaceMemberSpec) other).MemberType;
 149                                         if (!TypeSpecComparer.Override.IsEqual (other_type, MemberType))
 150                                                 return false;
 151                                 } else {
 152                                         return false;
 153                                 }
 154                         }
 155
 156                         return true;
 157                 }
 158
 159                 #endregion
 160         }
 161
 162         //
 163         // The MemberCache is the main members container used by compiler. It contains
 164         // all members imported or defined during compilation using on demand filling
 165         // process. Inflated containers are also using MemberCache to make inflated
 166         // members look like normal definition.
 167         //
 168         // All of the methods are performance and memory sensitive as the MemberCache
 169         // is the underlying engine of all member based operations.
 170         //
 171         public class MemberCache
 172         {
 173                 enum StateFlags
 174                 {
 175                         HasConversionOperator = 1 << 1,
 176                         HasUserOperator = 1 << 2
 177                 }
 178
 179                 readonly Dictionary<string, IList<MemberSpec>> member_hash;
 180                 Dictionary<string, MemberSpec[]> locase_members;
 181                 IList<MethodSpec> missing_abstract;
 182                 StateFlags state;
 183
 184                 public static readonly string IndexerNameAlias = "<this>";
 185
 186                 public static readonly MemberCache Empty = new MemberCache (0);
 187
 188                 public MemberCache ()
 189                         : this (16)
 190                 {
 191                 }
 192
 193                 public MemberCache (int capacity)
 194                 {
 195                         member_hash = new Dictionary<string, IList<MemberSpec>> (capacity);
 196                 }
 197
 198                 public MemberCache (MemberCache cache)
 199                         : this (cache.member_hash.Count)
 200                 {
 201                         this.state = cache.state;
 202                 }
 203
 204                 //
 205                 // Creates a new MemberCache for the given `container'.
 206                 //
 207                 public MemberCache (TypeContainer container)
 208                         : this ()                               // TODO: Optimize the size
 209                 {
 210                 }
 211
 212                 //
 213                 // Member-cache does not contain base members but it does
 214                 // contain all base interface members, so the Lookup code
 215                 // can use simple inheritance rules.
 216                 //
 217                 public void AddInterface (TypeSpec iface)
 218                 {
 219                         var cache = iface.MemberCache;
 220
 221                         IList<MemberSpec> list;
 222                         foreach (var entry in cache.member_hash) {
 223                                 if (!member_hash.TryGetValue (entry.Key, out list)) {
 224                                         if (entry.Value.Count == 1) {
 225                                                 list = entry.Value;
 226                                         } else {
 227                                                 list = new List<MemberSpec> (entry.Value);
 228                                         }
 229
 230                                         member_hash.Add (entry.Key, list);
 231                                         continue;
 232                                 }
 233
 234                                 foreach (var ce in entry.Value) {
 235                                         if (ce.DeclaringType != iface)
 236                                                 break;
 237
 238                                         if (list.Contains (ce))
 239                                                 continue;
 240
 241                                         if (AddInterfaceMember (ce, ref list))
 242                                                 member_hash[entry.Key] = list;
 243                                 }
 244                         }
 245                 }
 246
 247                 public void AddMember (InterfaceMemberBase imb, string exlicitName, MemberSpec ms)
 248                 {
 249                         // Explicit names cannot be looked-up but can be used for
 250                         // collision checking (no name mangling needed)
 251                         if (imb.IsExplicitImpl)
 252                                 AddMember (exlicitName, ms);
 253                         else
 254                                 AddMember (ms);
 255                 }
 256
 257                 //
 258                 // Add non-explicit member to member cache
 259                 //
 260                 public void AddMember (MemberSpec ms)
 261                 {
 262                         AddMember (GetLookupName (ms), ms);
 263                 }
 264
 265                 void AddMember (string name, MemberSpec member)
 266                 {
 267                         if (member.Kind == MemberKind.Operator) {
 268                                 var dt = member.DeclaringType;
 269                                 if (dt == TypeManager.string_type || dt == TypeManager.delegate_type || dt == TypeManager.multicast_delegate_type) {
 270                                         // Some core types have user operators but they cannot be used as normal
 271                                         // user operators as they are predefined and therefore having different
 272                                         // rules (e.g. binary operators) by not setting the flag we hide them for
 273                                         // user conversions
 274                                         // TODO: Should I do this for all core types ?
 275                                 } else if (name == Operator.GetMetadataName (Operator.OpType.Implicit) || name == Operator.GetMetadataName (Operator.OpType.Explicit)) {
 276                                         state |= StateFlags.HasConversionOperator;
 277                                 } else {
 278                                         state |= StateFlags.HasUserOperator;
 279                                 }
 280                         }
 281
 282                         IList<MemberSpec> list;
 283                         if (!member_hash.TryGetValue (name, out list)) {
 284                                 member_hash.Add (name, new MemberSpec[] { member });
 285                                 return;
 286                         }
 287
 288                         if (member.DeclaringType.IsInterface) {
 289                                 if (AddInterfaceMember (member, ref list))
 290                                         member_hash[name] = list;
 291                         } else {
 292                                 if (list is MemberSpec[]) {
 293                                         list = new List<MemberSpec> () { list[0] };
 294                                         member_hash[name] = list;
 295                                 }
 296
 297                                 list.Add (member);
 298                         }
 299                 }
 300
 301                 //
 302                 // Ignores any base interface member which can be hidden
 303                 // by this interface
 304                 //
 305                 static bool AddInterfaceMember (MemberSpec member, ref IList<MemberSpec> existing)
 306                 {
 307                         var member_param = member is IParametersMember ? ((IParametersMember) member).Parameters : ParametersCompiled.EmptyReadOnlyParameters;
 308
 309                         //
 310                         // interface IA : IB { int Prop { set; } }
 311                         // interface IB { bool Prop { get; } }
 312                         //
 313                         // IB.Prop is never accessible from IA interface
 314                         //
 315                         for (int i = 0; i < existing.Count; ++i) {
 316                                 var entry = existing[i];
 317
 318                                 if (entry.Arity != member.Arity)
 319                                         continue;
 320
 321                                 if (entry is IParametersMember) {
 322                                         var entry_param = ((IParametersMember) entry).Parameters;
 323                                         if (!TypeSpecComparer.Override.IsEqual (entry_param, member_param))
 324                                                 continue;
 325                                 }
 326
 327                                 if (member.DeclaringType.ImplementsInterface (entry.DeclaringType)) {
 328                                         if (existing is MemberSpec[]) {
 329                                                 existing = new MemberSpec[] { member };
 330                                                 return true;
 331                                         }
 332
 333                                         existing.RemoveAt (i--);
 334                                         continue;
 335                                 }
 336
 337                                 if ((entry.DeclaringType == member.DeclaringType && entry.IsAccessor == member.IsAccessor) ||
 338                                         entry.DeclaringType.ImplementsInterface (member.DeclaringType))
 339                                         return false;
 340                         }
 341
 342                         if (existing is MemberSpec[]) {
 343                                 existing = new List<MemberSpec> () { existing[0], member };
 344                                 return true;
 345                         }
 346
 347                         existing.Add (member);
 348                         return false;
 349                 }
 350
 351                 public static MemberSpec FindMember (TypeSpec container, MemberFilter filter, BindingRestriction restrictions)
 352                 {
 353                         do {
 354                                 IList<MemberSpec> applicable;
 355                                 if (container.MemberCache.member_hash.TryGetValue (filter.Name, out applicable)) {
 356                                         // Start from the end because interface members are in reverse order
 357                                         for (int i = applicable.Count - 1; i >= 0; i--) {
 358                                                 var entry = applicable [i];
 359
 360                                                 if ((restrictions & BindingRestriction.InstanceOnly) != 0 && entry.IsStatic)
 361                                                         continue;
 362
 363                                                 if ((restrictions & BindingRestriction.NoAccessors) != 0 && entry.IsAccessor)
 364                                                         continue;
 365
 366                                                 if (!filter.Equals (entry))
 367                                                         continue;
 368
 369                                                 if ((restrictions & BindingRestriction.DeclaredOnly) != 0 && container.IsInterface && entry.DeclaringType != container)
 370                                                         continue;
 371
 372                                                 return entry;
 373                                         }
 374                                 }
 375
 376                                 if ((restrictions & BindingRestriction.DeclaredOnly) != 0)
 377                                         break;
 378
 379                                 container = container.BaseType;
 380                         } while (container != null);
 381
 382                         return null;
 383                 }
 384
 385                 //
 386                 // A special method to work with member lookup only. It returns a list of all members named @name
 387                 // starting from @container. It's very performance sensitive
 388                 //
 389                 public static IList<MemberSpec> FindMembers (TypeSpec container, string name, bool declaredOnly)
 390                 {
 391                         IList<MemberSpec> applicable;
 392
 393                         do {
 394                                 if (container.MemberCache.member_hash.TryGetValue (name, out applicable) || declaredOnly)
 395                                         return applicable;
 396
 397                                 container = container.BaseType;
 398                         } while (container != null);
 399
 400                         return null;
 401                 }
 402
 403                 //
 404                 // Finds the nested type in container
 405                 //
 406                 public static TypeSpec FindNestedType (TypeSpec container, string name, int arity)
 407                 {
 408                         IList<MemberSpec> applicable;
 409                         TypeSpec best_match = null;
 410                         do {
 411                                 // TODO: Don't know how to handle this yet
 412                                 // When resolving base type of nested type, parent type must have
 413                                 // base type resolved to scan full hierarchy correctly
 414                                 // Similarly MemberCacheTypes will inflate BaseType and Interfaces
 415                                 // based on type definition
 416                                 var tc = container.MemberDefinition as TypeContainer;
 417                                 if (tc != null)
 418                                         tc.DefineType ();
 419
 420                                 if (container.MemberCacheTypes.member_hash.TryGetValue (name, out applicable)) {
 421                                         for (int i = applicable.Count - 1; i >= 0; i--) {
 422                                                 var entry = applicable[i];
 423                                                 if ((entry.Kind & MemberKind.NestedMask) == 0)
 424                                                         continue;
 425
 426                                                 var ts = (TypeSpec) entry;
 427                                                 if (arity == ts.Arity)
 428                                                         return ts;
 429
 430                                                 if (arity < 0) {
 431                                                         if (best_match == null) {
 432                                                                 best_match = ts;
 433                                                         } else if (System.Math.Abs (ts.Arity + arity) < System.Math.Abs (ts.Arity + arity)) {
 434                                                                 best_match = ts;
 435                                                         }
 436                                                 }
 437                                         }
 438                                 }
 439
 440                                 container = container.BaseType;
 441                         } while (container != null);
 442
 443                         return best_match;
 444                 }
 445
 446                 //
 447                 // Looks for extension methods with defined name and extension type
 448                 //
 449                 public List<MethodSpec> FindExtensionMethods (TypeSpec invocationType, TypeSpec extensionType, string name, int arity)
 450                 {
 451                         IList<MemberSpec> entries;
 452                         if (!member_hash.TryGetValue (name, out entries))
 453                                 return null;
 454
 455                         List<MethodSpec> candidates = null;
 456                         foreach (var entry in entries) {
 457                                 if (entry.Kind != MemberKind.Method || (arity > 0 && entry.Arity != arity))
 458                                         continue;
 459
 460                                 var ms = (MethodSpec) entry;
 461                                 if (!ms.IsExtensionMethod)
 462                                         continue;
 463
 464                                 if (!ms.IsAccessible (invocationType))
 465                                         continue;
 466
 467                                 // TODO: CodeGen.Assembly.Builder
 468                                 if ((ms.DeclaringType.Modifiers & Modifiers.INTERNAL) != 0 &&
 469                                         !TypeManager.IsThisOrFriendAssembly (CodeGen.Assembly.Builder, ms.Assembly))
 470                                         continue;
 471
 472                                 if (candidates == null)
 473                                         candidates = new List<MethodSpec> ();
 474                                 candidates.Add (ms);
 475                         }
 476
 477                         return candidates;
 478                 }
 479
 480                 //
 481                 // Returns base members of @member member if no exact match is found @bestCandidate returns
 482                 // the best match
 483                 //
 484                 public static MemberSpec FindBaseMember (MemberCore member, out MemberSpec bestCandidate)
 485                 {
 486                         bestCandidate = null;
 487                         var container = member.Parent.PartialContainer.Definition;
 488                         if (!container.IsInterface)
 489                                 container = container.BaseType;
 490
 491                         string name = GetLookupName (member);
 492                         IList<MemberSpec> applicable;
 493                         var member_param = member is IParametersMember ? ((IParametersMember) member).Parameters : null;
 494
 495                         var mkind = GetMemberCoreKind (member);
 496                         bool member_with_accessors = mkind == MemberKind.Indexer || mkind == MemberKind.Property;
 497
 498                         do {
 499                                 if (container.MemberCache.member_hash.TryGetValue (name, out applicable)) {
 500                                         for (int i = 0; i < applicable.Count; ++i) {
 501                                                 var entry = applicable [i];
 502
 503                                                 if ((entry.Modifiers & Modifiers.PRIVATE) != 0)
 504                                                         continue;
 505
 506                                                 if ((entry.Modifiers & Modifiers.AccessibilityMask) == Modifiers.INTERNAL) {
 507                                                         if (!TypeManager.IsThisOrFriendAssembly (member.Assembly, entry.Assembly))
 508                                                                 continue;
 509                                                 }
 510
 511                                                 //
 512                                                 // Is the member of the correct type ?
 513                                                 // Destructors are ignored as they cannot be overridden by user
 514                                                 if ((entry.Kind & ~MemberKind.Destructor & mkind & MemberKind.MaskType) == 0) {
 515                                                         if ((entry.Kind & MemberKind.Destructor) == 0 && (member_param == null || !(entry is IParametersMember))) {
 516                                                                 bestCandidate = entry;
 517                                                                 return null;
 518                                                         }
 519
 520                                                         continue;
 521                                                 }
 522
 523                                                 if (entry.Kind != mkind) {
 524                                                         if (bestCandidate == null)
 525                                                                 bestCandidate = entry;
 526
 527                                                         continue;
 528                                                 }
 529
 530                                                 if (member_param != null) {
 531                                                         // Check arity match
 532                                                         int arity = member.MemberName.Arity;
 533                                                         if (arity != entry.Arity)
 534                                                                 continue;
 535
 536                                                         var pm = entry as IParametersMember;
 537                                                         if (pm == null)
 538                                                                 continue;
 539
 540                                                         if (entry.IsAccessor != member is AbstractPropertyEventMethod)
 541                                                                 continue;
 542
 543                                                         if (!TypeSpecComparer.Override.IsEqual (pm.Parameters, member_param))
 544                                                                 continue;
 545                                                 }
 546
 547                                                 //
 548                                                 // Skip override members with accessors they may not fully implement the base member
 549                                                 //
 550                                                 if (member_with_accessors) {
 551                                                         if ((entry.Modifiers & (Modifiers.OVERRIDE | Modifiers.SEALED)) == Modifiers.OVERRIDE) {
 552                                                                 //
 553                                                                 // Set candidate to member override to flag we found an implementation
 554                                                                 //
 555                                                                 bestCandidate = entry;
 556                                                                 continue;
 557                                                         }
 558                                                 } else {
 559                                                         bestCandidate = null;
 560                                                 }
 561
 562                                                 return entry;
 563                                         }
 564                                 }
 565
 566                                 if (container.IsInterface)
 567                                         break;
 568
 569                                 container = container.BaseType;
 570                         } while (container != null);
 571
 572                         return null;
 573                 }
 574
 575                 //
 576                 // Returns inflated version of MemberSpec, it works similarly to
 577                 // SRE TypeBuilder.GetMethod
 578                 //
 579                 public static T GetMember<T> (TypeSpec container, T spec) where T : MemberSpec
 580                 {
 581                         IList<MemberSpec> applicable;
 582                         if (container.MemberCache.member_hash.TryGetValue (GetLookupName (spec), out applicable)) {
 583                                 for (int i = applicable.Count - 1; i >= 0; i--) {
 584                                         var entry = applicable[i];
 585                                         if (entry.MemberDefinition == spec.MemberDefinition)
 586                                                 return (T) entry;
 587                                 }
 588                         }
 589
 590                         throw new InternalErrorException ("Missing member `{0}' on inflated type `{1}'",
 591                                 spec.GetSignatureForError (), container.GetSignatureForError ());
 592                 }
 593
 594                 static MemberKind GetMemberCoreKind (MemberCore member)
 595                 {
 596                         if (member is FieldBase)
 597                                 return MemberKind.Field;
 598                         if (member is Indexer)
 599                                 return MemberKind.Indexer;
 600                         if (member is Class)
 601                                 return MemberKind.Class;
 602                         if (member is Struct)
 603                                 return MemberKind.Struct;
 604                         if (member is Destructor)
 605                                 return MemberKind.Destructor;
 606                         if (member is Method)
 607                                 return MemberKind.Method;
 608                         if (member is Property)
 609                                 return MemberKind.Property;
 610                         if (member is EventField)
 611                                 return MemberKind.Event;
 612                         if (member is Interface)
 613                                 return MemberKind.Interface;
 614                         if (member is EventProperty)
 615                                 return MemberKind.Event;
 616
 617                         throw new NotImplementedException (member.GetType ().ToString ());
 618                 }
 619
 620                 public static IList<MemberSpec> GetCompletitionMembers (TypeSpec container, string name)
 621                 {
 622                         var matches = new List<MemberSpec> ();
 623                         foreach (var entry in container.MemberCache.member_hash) {
 624                                 foreach (var name_entry in entry.Value) {
 625                                         if (name_entry.IsAccessor)
 626                                                 continue;
 627
 628                                         if ((name_entry.Kind & (MemberKind.Constructor | MemberKind.Destructor | MemberKind.Operator)) != 0)
 629                                                 continue;
 630
 631                                         if (!name_entry.IsAccessible (InternalType.FakeInternalType))
 632                                                 continue;
 633
 634                                         if (name == null || name_entry.Name.StartsWith (name)) {
 635                                                 matches.Add (name_entry);
 636                                         }
 637                                 }
 638                         }
 639
 640                         return matches;
 641                 }
 642
 643                 //
 644                 // Returns members of @iface only, base members are ignored
 645                 //
 646                 public static IList<MethodSpec> GetInterfaceMethods (TypeSpec iface)
 647                 {
 648                         //
 649                         // MemberCache flatten interfaces, therefore in cases like this one
 650                         //
 651                         // interface IA : IB {}
 652                         // interface IB { void Foo () }
 653                         //
 654                         // we would return Foo inside IA which is not expected in this case
 655                         //
 656                         var methods = new List<MethodSpec> ();
 657                         foreach (var entry in iface.MemberCache.member_hash.Values) {
 658                                 foreach (var name_entry in entry) {
 659                                         if (iface == name_entry.DeclaringType) {
 660                                                 if (name_entry.Kind == MemberKind.Method) {
 661                                                         methods.Add ((MethodSpec) name_entry);
 662                                                 }
 663                                         }
 664                                 }
 665                         }
 666
 667                         return methods;
 668                 }
 669
 670                 //
 671                 // Returns all not implememted abstract members inside abstract type
 672                 // NOTE: Returned list is shared and must not be modified
 673                 //
 674                 public static IList<MethodSpec> GetNotImplementedAbstractMethods (TypeSpec type)
 675                 {
 676                         if (type.MemberCache.missing_abstract != null)
 677                                 return type.MemberCache.missing_abstract;
 678
 679                         var abstract_methods = new List<MethodSpec> ();
 680                         List<TypeSpec> hierarchy = null;
 681
 682                         //
 683                         // Stage 1: top-to-bottom scan for abstract members
 684                         //
 685                         var abstract_type = type;
 686                         while (true) {
 687                                 foreach (var entry in abstract_type.MemberCache.member_hash) {
 688                                         foreach (var name_entry in entry.Value) {
 689                                                 if ((name_entry.Modifiers & Modifiers.ABSTRACT) == 0)
 690                                                         continue;
 691
 692                                                 if (name_entry.Kind != MemberKind.Method)
 693                                                         continue;
 694
 695                                                 abstract_methods.Add ((MethodSpec) name_entry);
 696                                         }
 697                                 }
 698
 699                                 var base_type = abstract_type.BaseType;
 700                                 if (!base_type.IsAbstract)
 701                                         break;
 702
 703                                 if (hierarchy == null)
 704                                         hierarchy = new List<TypeSpec> ();
 705
 706                                 hierarchy.Add (abstract_type);
 707                                 abstract_type = base_type;
 708                         }
 709
 710                         int not_implemented_count = abstract_methods.Count;
 711                         if (not_implemented_count == 0 || hierarchy == null) {
 712                                 type.MemberCache.missing_abstract = abstract_methods;
 713                                 return type.MemberCache.missing_abstract;
 714                         }
 715
 716                         //
 717                         // Stage 2: Remove already implemented methods
 718                         //
 719                         foreach (var type_up in hierarchy) {
 720                                 var members = type_up.MemberCache.member_hash;
 721                                 if (members.Count == 0)
 722                                         continue;
 723
 724                                 for (int i = 0; i < abstract_methods.Count; ++i) {
 725                                         var candidate = abstract_methods [i];
 726                                         if (candidate == null)
 727                                                 continue;
 728
 729                                         IList<MemberSpec> applicable;
 730                                         if (!members.TryGetValue (candidate.Name, out applicable))
 731                                                 continue;
 732
 733                                         var filter = new MemberFilter (candidate);
 734                                         foreach (var item in applicable) {
 735                                                 if ((item.Modifiers & (Modifiers.OVERRIDE | Modifiers.VIRTUAL)) == 0)
 736                                                         continue;
 737
 738                                                 if (filter.Equals (item)) {
 739                                                         --not_implemented_count;
 740                                                         abstract_methods [i] = null;
 741                                                         break;
 742                                                 }
 743                                         }
 744                                 }
 745                         }
 746
 747                         if (not_implemented_count == abstract_methods.Count) {
 748                                 type.MemberCache.missing_abstract = abstract_methods;
 749                                 return type.MemberCache.missing_abstract;
 750                         }
 751
 752                         var not_implemented = new MethodSpec[not_implemented_count];
 753                         int counter = 0;
 754                         foreach (var m in abstract_methods) {
 755                                 if (m == null)
 756                                         continue;
 757
 758                                 not_implemented[counter++] = m;
 759                         }
 760
 761                         type.MemberCache.missing_abstract = not_implemented;
 762                         return type.MemberCache.missing_abstract;
 763                 }
 764
 765                 static string GetLookupName (MemberSpec ms)
 766                 {
 767                         if (ms.Kind == MemberKind.Indexer)
 768                                 return IndexerNameAlias;
 769
 770                         if (ms.Kind == MemberKind.Constructor) {
 771                                 if (ms.IsStatic)
 772                                         return ConstructorInfo.TypeConstructorName;
 773
 774                                 return ConstructorInfo.ConstructorName;
 775                         }
 776
 777                         return ms.Name;
 778                 }
 779
 780                 static string GetLookupName (MemberCore mc)
 781                 {
 782                         if (mc is Indexer)
 783                                 return IndexerNameAlias;
 784
 785                         if (mc is Constructor)
 786                                 return ConstructorInfo.ConstructorName;
 787
 788                         return mc.MemberName.Name;
 789                 }
 790
 791                 //
 792                 // Returns all operators declared on container and its base types (until declaredOnly is used)
 793                 //
 794                 public static IList<MemberSpec> GetUserOperator (TypeSpec container, Operator.OpType op, bool declaredOnly)
 795                 {
 796                         IList<MemberSpec> found = null;
 797
 798                         IList<MemberSpec> applicable;
 799                         do {
 800                                 var mc = container.MemberCache;
 801
 802                                 if (((op == Operator.OpType.Implicit || op == Operator.OpType.Explicit) && (mc.state & StateFlags.HasConversionOperator) != 0) ||
 803                                          (mc.state & StateFlags.HasUserOperator) != 0) {
 804
 805                                         if (mc.member_hash.TryGetValue (Operator.GetMetadataName (op), out applicable)) {
 806                                                 int match_count = 0;
 807                                                 for (int i = 0; i < applicable.Count; ++i) {
 808                                                         if (applicable[i].Kind == MemberKind.Operator) {
 809                                                                 ++match_count;
 810                                                                 continue;
 811                                                         }
 812
 813                                                         // Handles very rare case where a method exists with same name as operator (op_xxxx)
 814                                                         if (found == null) {
 815                                                                 found = new List<MemberSpec> ();
 816                                                                 found.Add (applicable [i]);
 817                                                         } else {
 818                                                                 var prev = found as List<MemberSpec>;
 819                                                                 if (prev == null) {
 820                                                                         prev = new List<MemberSpec> (found.Count + 1);
 821                                                                         prev.AddRange (found);
 822                                                                 }
 823
 824                                                                 prev.Add (applicable[i]);
 825                                                         }
 826                                                 }
 827
 828                                                 if (match_count > 0 && match_count == applicable.Count) {
 829                                                         if (found == null) {
 830                                                                 found = applicable;
 831                                                         } else {
 832                                                                 var merged = found as List<MemberSpec>;
 833                                                                 if (merged == null) {
 834                                                                         merged = new List<MemberSpec> (found.Count + applicable.Count);
 835                                                                         merged.AddRange (found);
 836                                                                         found = merged;
 837                                                                 }
 838
 839                                                                 merged.AddRange (applicable);
 840                                                         }
 841                                                 }
 842                                         }
 843                                 }
 844
 845                                 // BaseType call can be expensive
 846                                 if (declaredOnly)
 847                                         break;
 848
 849                                 container = container.BaseType;
 850                         } while (container != null);
 851
 852                         return found;
 853                 }
 854
 855                 //
 856                 // Inflates all member cache nested types
 857                 //
 858                 public void InflateTypes (MemberCache inflated_cache, TypeParameterInflator inflator)
 859                 {
 860                         foreach (var item in member_hash) {
 861                                 IList<MemberSpec> inflated_members = null;
 862                                 for (int i = 0; i < item.Value.Count; ++i ) {
 863                                         var member = item.Value[i];
 864
 865                                         // FIXME: When inflating members refering nested types before they are inflated
 866                                         if (member == null)
 867                                                 continue;
 868
 869                                         if ((member.Kind & MemberKind.NestedMask) != 0 &&
 870                                                 (member.Modifiers & Modifiers.COMPILER_GENERATED) == 0) {
 871                                                 if (inflated_members == null) {
 872                                                         inflated_members = new MemberSpec[item.Value.Count];
 873                                                         inflated_cache.member_hash.Add (item.Key, inflated_members);
 874                                                 }
 875
 876                                                 inflated_members [i] = member.InflateMember (inflator);
 877                                         }
 878                                 }
 879                         }
 880                 }
 881
 882                 //
 883                 // Inflates all open type members, requires InflateTypes to be called before
 884                 //
 885                 public void InflateMembers (MemberCache cacheToInflate, TypeSpec inflatedType, TypeParameterInflator inflator)
 886                 {
 887                         var inflated_member_hash = cacheToInflate.member_hash;
 888                         Dictionary<MethodSpec, MethodSpec> accessor_relation = null;
 889                         List<MemberSpec> accessor_members = null;
 890
 891                         // Copy member specific flags when all members were added
 892                         cacheToInflate.state = state;
 893
 894                         foreach (var item in member_hash) {
 895                                 var members = item.Value;
 896                                 IList<MemberSpec> inflated_members = null;
 897                                 for (int i = 0; i < members.Count; ++i ) {
 898                                         var member = members[i];
 899
 900                                         //
 901                                         // All nested types have been inflated earlier except for
 902                                         // compiler types which are created later and could miss InflateTypes
 903                                         //
 904                                         if ((member.Kind & MemberKind.NestedMask) != 0 &&
 905                                                 (member.Modifiers & Modifiers.COMPILER_GENERATED) == 0) {
 906                                                 if (inflated_members == null)
 907                                                         inflated_members = inflated_member_hash[item.Key];
 908
 909                                                 continue;
 910                                         }
 911
 912                                         //
 913                                         // Clone the container first
 914                                         //
 915                                         if (inflated_members == null) {
 916                                                 inflated_members = new MemberSpec [item.Value.Count];
 917                                                 inflated_member_hash.Add (item.Key, inflated_members);
 918                                         }
 919
 920                                         var local_inflator = inflator;
 921
 922                                         if (member.DeclaringType != inflatedType) {
 923                                                 //
 924                                                 // Don't inflate non generic interface members
 925                                                 // merged into generic interface
 926                                                 //
 927                                                 if (!member.DeclaringType.IsGeneric) {
 928                                                         inflated_members [i] = member;
 929                                                         continue;
 930                                                 }
 931
 932                                                 //
 933                                                 // Needed when inflating flatten interfaces. It inflates
 934                                                 // container type only, type parameters are already done
 935                                                 //
 936                                                 // Handles cases like:
 937                                                 //
 938                                                 // interface I<T> {}
 939                                                 // interface I<U, V> : I<U> {}
 940                                                 //
 941                                                 // class C: I<int, bool> {}
 942                                                 //
 943                                                 var inflated_parent = inflator.Inflate (member.DeclaringType);
 944                                                 if (inflated_parent != inflator.TypeInstance)
 945                                                         local_inflator = new TypeParameterInflator (inflator, inflated_parent);
 946                                         }
 947
 948                                         //
 949                                         // Inflate every member, its parent is now different
 950                                         //
 951                                         var inflated = member.InflateMember (local_inflator);
 952                                         inflated_members [i] = inflated;
 953
 954                                         if (member is PropertySpec || member is EventSpec) {
 955                                                 if (accessor_members == null)
 956                                                         accessor_members = new List<MemberSpec> ();
 957
 958                                                 accessor_members.Add (inflated);
 959                                                 continue;
 960                                         }
 961
 962                                         if (member.IsAccessor) {
 963                                                 if (accessor_relation == null)
 964                                                         accessor_relation = new Dictionary<MethodSpec, MethodSpec> ();
 965                                                 accessor_relation.Add ((MethodSpec) member, (MethodSpec) inflated);
 966                                         }
 967                                 }
 968                         }
 969
 970                         if (accessor_members != null) {
 971                                 foreach (var member in accessor_members) {
 972                                         var prop = member as PropertySpec;
 973                                         if (prop != null) {
 974                                                 if (prop.Get != null)
 975                                                         prop.Get = accessor_relation[prop.Get];
 976                                                 if (prop.Set != null)
 977                                                         prop.Set = accessor_relation[prop.Set];
 978
 979                                                 continue;
 980                                         }
 981
 982                                         var ev = (EventSpec) member;
 983                                         ev.AccessorAdd = accessor_relation[ev.AccessorAdd];
 984                                         ev.AccessorRemove = accessor_relation[ev.AccessorRemove];
 985                                 }
 986                         }
 987                 }
 988
 989                 //
 990                 // Checks all appropriate container members for CLS compliance
 991                 //
 992                 public void VerifyClsCompliance (TypeSpec container, Report report)
 993                 {
 994                         if (locase_members != null)
 995                                 return;
 996
 997                         if (container.BaseType == null) {
 998                                 locase_members = new Dictionary<string, MemberSpec[]> (member_hash.Count); // StringComparer.OrdinalIgnoreCase);
 999                         } else {
1000                                 container.BaseType.MemberCache.VerifyClsCompliance (container.BaseType, report);
1001                                 locase_members = new Dictionary<string, MemberSpec[]> (container.BaseType.MemberCache.locase_members); //, StringComparer.OrdinalIgnoreCase);
1002                         }
1003
1004                         var is_imported_type = container.MemberDefinition.IsImported;
1005                         foreach (var entry in container.MemberCache.member_hash) {
1006                                 for (int i = 0; i < entry.Value.Count; ++i ) {
1007                                         var name_entry = entry.Value[i];
1008                                         if ((name_entry.Modifiers & (Modifiers.PUBLIC | Modifiers.PROTECTED)) == 0)
1009                                                 continue;
1010
1011                                         if ((name_entry.Modifiers & (Modifiers.OVERRIDE | Modifiers.COMPILER_GENERATED)) != 0)
1012                                                 continue;
1013
1014                                         if ((name_entry.Kind & MemberKind.MaskType) == 0)
1015                                                 continue;
1016
1017                                         if (name_entry.MemberDefinition.IsNotCLSCompliant ())
1018                                             continue;
1019
1020                                         IParametersMember p_a = name_entry as IParametersMember;
1021                                         if (p_a != null && !name_entry.IsAccessor) {
1022                                                 if (!is_imported_type) {
1023                                                         var p_a_pd = p_a.Parameters;
1024                                                         for (int ii = i + 1; ii < entry.Value.Count; ++ii) {
1025                                                                 var checked_entry = entry.Value[ii];
1026                                                                 IParametersMember p_b = checked_entry as IParametersMember;
1027                                                                 if (p_b == null)
1028                                                                         continue;
1029
1030                                                                 if (p_a_pd.Count != p_b.Parameters.Count)
1031                                                                         continue;
1032
1033                                                                 if (checked_entry.IsAccessor)
1034                                                                         continue;
1035
1036                                                                 var res = ParametersCompiled.IsSameClsSignature (p_a.Parameters, p_b.Parameters);
1037                                                                 if (res != 0) {
1038                                                                         var last = GetLaterDefinedMember (checked_entry, name_entry);
1039                                                                         if (last == checked_entry.MemberDefinition) {
1040                                                                                 report.SymbolRelatedToPreviousError (name_entry);
1041                                                                         } else {
1042                                                                                 report.SymbolRelatedToPreviousError (checked_entry);
1043                                                                         }
1044
1045                                                                         if ((res & 1) != 0) {
1046                                                                                 report.Warning (3006, 1, last.Location,
1047                                                                                                 "Overloaded method `{0}' differing only in ref or out, or in array rank, is not CLS-compliant",
1048                                                                                                 name_entry.GetSignatureForError ());
1049                                                                         }
1050
1051                                                                         if ((res & 2) != 0) {
1052                                                                                 report.Warning (3007, 1, last.Location,
1053                                                                                         "Overloaded method `{0}' differing only by unnamed array types is not CLS-compliant",
1054                                                                                         name_entry.GetSignatureForError ());
1055                                                                         }
1056                                                                 }
1057                                                         }
1058                                                 }
1059                                         }
1060
1061                                         if (i > 0 || name_entry.Kind == MemberKind.Constructor || name_entry.Kind == MemberKind.Indexer)
1062                                                 continue;
1063
1064                                         var name_entry_locase = name_entry.Name.ToLowerInvariant ();
1065
1066                                         MemberSpec[] found;
1067                                         if (!locase_members.TryGetValue (name_entry_locase, out found)) {
1068                                                 found = new MemberSpec[] { name_entry };
1069                                                 locase_members.Add (name_entry_locase, found);
1070                                         } else {
1071                                                 bool same_names_only = true;
1072                                                 foreach (var f in found) {
1073                                                         if (f.Name == name_entry.Name)
1074                                                                 continue;
1075
1076 //                                                      if (f.IsAccessor && name_entry.IsAccessor)
1077 //                                                              continue;
1078
1079                                                         same_names_only = false;
1080                                                         if (!is_imported_type) {
1081                                                                 var last = GetLaterDefinedMember (f, name_entry);
1082                                                                 if (last == f.MemberDefinition) {
1083                                                                         report.SymbolRelatedToPreviousError (name_entry);
1084                                                                 } else {
1085                                                                         report.SymbolRelatedToPreviousError (f);
1086                                                                 }
1087
1088                                                                 report.Warning (3005, 1, last.Location,
1089                                                                         "Identifier `{0}' differing only in case is not CLS-compliant", last.GetSignatureForError ());
1090                                                         }
1091                                                 }
1092
1093                                                 if (!same_names_only) {
1094                                                         Array.Resize (ref found, found.Length + 1);
1095                                                         found[found.Length - 1] = name_entry;
1096                                                         locase_members[name_entry_locase] = found;
1097                                                 }
1098                                         }
1099                                 }
1100                         }
1101                 }
1102
1103                 //
1104                 // Local report helper to issue correctly ordered members stored in hashtable
1105                 //
1106                 static MemberCore GetLaterDefinedMember (MemberSpec a, MemberSpec b)
1107                 {
1108                         var mc_a = a.MemberDefinition as MemberCore;
1109                         var mc_b = b.MemberDefinition as MemberCore;
1110                         if (mc_a == null)
1111                                 return mc_b;
1112
1113                         if (mc_b == null)
1114                                 return mc_a;
1115
1116                         if (mc_a.Location.File != mc_a.Location.File)
1117                                 return mc_b;
1118
1119                         return mc_b.Location.Row > mc_a.Location.Row ? mc_b : mc_a;
1120                 }
1121
1122                 public bool CheckExistingMembersOverloads (MemberCore member, AParametersCollection parameters)
1123                 {
1124                         var name = GetLookupName (member);
1125                         var imb = member as InterfaceMemberBase;
1126                         if (imb != null && imb.IsExplicitImpl) {
1127                                 name = imb.GetFullName (name);
1128                         }
1129
1130                         return CheckExistingMembersOverloads (member, name, parameters);
1131                 }
1132
1133                 public bool CheckExistingMembersOverloads (MemberCore member, string name, AParametersCollection parameters)
1134                 {
1135                         IList<MemberSpec> entries;
1136                         if (!member_hash.TryGetValue (name, out entries))
1137                                 return false;
1138
1139                         var Report = member.Compiler.Report;
1140
1141                         int method_param_count = parameters.Count;
1142                         for (int i = entries.Count - 1; i >= 0; --i) {
1143                                 var ce = entries[i];
1144                                 var pm = ce as IParametersMember;
1145                                 var pd = pm == null ? ParametersCompiled.EmptyReadOnlyParameters : pm.Parameters;
1146                                 if (pd.Count != method_param_count)
1147                                         continue;
1148
1149                                 if (ce.Arity != member.MemberName.Arity)
1150                                         continue;
1151
1152                                 // Ignore merged interface members
1153                                 if (member.Parent.PartialContainer != ce.DeclaringType.MemberDefinition)
1154                                         continue;
1155
1156                                 var p_types = pd.Types;
1157                                 if (method_param_count > 0) {
1158                                         int ii = method_param_count - 1;
1159                                         TypeSpec type_a, type_b;
1160                                         do {
1161                                                 type_a = parameters.Types [ii];
1162                                                 type_b = p_types [ii];
1163
1164                                                 if ((pd.FixedParameters [ii].ModFlags & Parameter.Modifier.ISBYREF) !=
1165                                                         (parameters.FixedParameters [ii].ModFlags & Parameter.Modifier.ISBYREF))
1166                                                         break;
1167
1168                                         } while (TypeSpecComparer.Override.IsEqual (type_a, type_b) && ii-- != 0);
1169
1170                                         if (ii >= 0)
1171                                                 continue;
1172
1173                                         //
1174                                         // Operators can differ in return type only
1175                                         //
1176                                         if (member is Operator && ce.Kind == MemberKind.Operator && ((MethodSpec) ce).ReturnType != ((Operator) member).ReturnType)
1177                                                 continue;
1178
1179                                         //
1180                                         // Report difference in parameter modifiers only
1181                                         //
1182                                         if (pd != null && member is MethodCore) {
1183                                                 ii = method_param_count;
1184                                                 while (ii-- != 0 && parameters.FixedParameters[ii].ModFlags == pd.FixedParameters[ii].ModFlags &&
1185                                                         parameters.ExtensionMethodType == pd.ExtensionMethodType) ;
1186
1187                                                 if (ii >= 0) {
1188                                                         var mc = ce as MethodSpec;
1189                                                         member.Compiler.Report.SymbolRelatedToPreviousError (ce);
1190                                                         if ((member.ModFlags & Modifiers.PARTIAL) != 0 && (mc.Modifiers & Modifiers.PARTIAL) != 0) {
1191                                                                 if (parameters.HasParams || pd.HasParams) {
1192                                                                         Report.Error (758, member.Location,
1193                                                                                 "A partial method declaration and partial method implementation cannot differ on use of `params' modifier");
1194                                                                 } else {
1195                                                                         Report.Error (755, member.Location,
1196                                                                                 "A partial method declaration and partial method implementation must be both an extension method or neither");
1197                                                                 }
1198                                                         } else if (member is Constructor) {
1199                                                                 Report.Error (851, member.Location,
1200                                                                         "Overloaded contructor `{0}' cannot differ on use of parameter modifiers only",
1201                                                                         member.GetSignatureForError ());
1202                                                         } else {
1203                                                                 Report.Error (663, member.Location,
1204                                                                         "Overloaded method `{0}' cannot differ on use of parameter modifiers only",
1205                                                                         member.GetSignatureForError ());
1206                                                         }
1207                                                         return false;
1208                                                 }
1209                                         }
1210                                 }
1211
1212                                 if ((ce.Kind & MemberKind.Method) != 0) {
1213                                         Method method_a = member as Method;
1214                                         Method method_b = ce.MemberDefinition as Method;
1215                                         if (method_a != null && method_b != null && (method_a.ModFlags & method_b.ModFlags & Modifiers.PARTIAL) != 0) {
1216                                                 const Modifiers partial_modifiers = Modifiers.STATIC | Modifiers.UNSAFE;
1217                                                 if (method_a.IsPartialDefinition == method_b.IsPartialImplementation) {
1218                                                         if ((method_a.ModFlags & partial_modifiers) == (method_b.ModFlags & partial_modifiers) ||
1219                                                                 method_a.Parent.IsUnsafe && method_b.Parent.IsUnsafe) {
1220                                                                 if (method_a.IsPartialImplementation) {
1221                                                                         method_a.SetPartialDefinition (method_b);
1222                                                                         if (entries.Count == 1)
1223                                                                                 member_hash.Remove (name);
1224                                                                         else
1225                                                                                 entries.RemoveAt (i);
1226                                                                 } else {
1227                                                                         method_b.SetPartialDefinition (method_a);
1228                                                                         method_a.caching_flags |= MemberCore.Flags.PartialDefinitionExists;
1229                                                                 }
1230                                                                 continue;
1231                                                         }
1232
1233                                                         if (method_a.IsStatic != method_b.IsStatic) {
1234                                                                 Report.SymbolRelatedToPreviousError (ce);
1235                                                                 Report.Error (763, member.Location,
1236                                                                         "A partial method declaration and partial method implementation must be both `static' or neither");
1237                                                         }
1238
1239                                                         Report.SymbolRelatedToPreviousError (ce);
1240                                                         Report.Error (764, member.Location,
1241                                                                 "A partial method declaration and partial method implementation must be both `unsafe' or neither");
1242                                                         return false;
1243                                                 }
1244
1245                                                 Report.SymbolRelatedToPreviousError (ce);
1246                                                 if (method_a.IsPartialDefinition) {
1247                                                         Report.Error (756, member.Location, "A partial method `{0}' declaration is already defined",
1248                                                                 member.GetSignatureForError ());
1249                                                 }
1250
1251                                                 Report.Error (757, member.Location, "A partial method `{0}' implementation is already defined",
1252                                                         member.GetSignatureForError ());
1253                                                 return false;
1254                                         }
1255
1256                                         Report.SymbolRelatedToPreviousError (ce);
1257
1258                                         bool is_reserved_a = member is AbstractPropertyEventMethod || member is Operator;
1259                                         bool is_reserved_b = ((MethodSpec) ce).IsReservedMethod;
1260
1261                                         if (is_reserved_a || is_reserved_b) {
1262                                                 Report.Error (82, member.Location, "A member `{0}' is already reserved",
1263                                                         is_reserved_a ?
1264                                                         ce.GetSignatureForError () :
1265                                                         member.GetSignatureForError ());
1266                                                 return false;
1267                                         }
1268                                 } else {
1269                                         Report.SymbolRelatedToPreviousError (ce);
1270                                 }
1271
1272                                 if (member is Operator && ce.Kind == MemberKind.Operator) {
1273                                         Report.Error (557, member.Location, "Duplicate user-defined conversion in type `{0}'",
1274                                                 member.Parent.GetSignatureForError ());
1275                                         return false;
1276                                 }
1277
1278                                 Report.Error (111, member.Location,
1279                                         "A member `{0}' is already defined. Rename this member or use different parameter types",
1280                                         member.GetSignatureForError ());
1281                                 return false;
1282                         }
1283
1284                         return true;
1285                 }
1286         }
1287 }