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