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