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