← Back to branch summary

~halega/+junk/sharpdevelop

« back to all changes in this revision

Viewing changes to src/Main/ICSharpCode.SharpDevelop.Dom/Project/Src/CSharp/OverloadResolution.cs

  • Committer: sk
  • Date: 2011-09-10 05:17:57 UTC
  • Revision ID: halega@halega.com-20110910051757-qfouz1llya9m6boy
4.1.0.7915 Release Candidate 1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/Main/ICSharpCode.SharpDevelop.Dom/Project/Src/CSharp/OverloadResolution.cs
 
1
// Copyright (c) AlphaSierraPapa for the SharpDevelop Team (for details please see \doc\copyright.txt)
 
2
// This code is distributed under the GNU LGPL (for details please see \doc\license.txt)
 
3
 
 
4
using System;
 
5
using System.Linq;
 
6
using System.Collections.Generic;
 
7
 
 
8
namespace ICSharpCode.SharpDevelop.Dom.CSharp
 
9
{
 
10
        /// <summary>
 
11
        /// Implements C# 3.0 overload resolution.
 
12
        /// </summary>
 
13
        public sealed class OverloadResolution
 
14
        {
 
15
                private OverloadResolution() {}
 
16
                
 
17
                public static IMethodOrProperty FindOverload(IEnumerable<IMethodOrProperty> list,
 
18
                                                             IReturnType[] arguments,
 
19
                                                             bool allowAdditionalArguments,
 
20
                                                             bool substituteInferredTypes,
 
21
                                                             out bool acceptableMatch)
 
22
                {
 
23
                        OverloadResolution or = new OverloadResolution();
 
24
                        or.candidates = list.Select(m => new Candidate(m)).ToList();
 
25
                        or.arguments = arguments;
 
26
                        or.allowAdditionalArguments = allowAdditionalArguments;
 
27
                        
 
28
                        if (or.candidates.Count == 0)
 
29
                                throw new ArgumentException("at least one candidate is required");
 
30
                        
 
31
                        MemberLookupHelper.Log("OverloadResolution");
 
32
                        MemberLookupHelper.Log("  arguments = ", arguments);
 
33
                        
 
34
                        or.ConstructExpandedForms();
 
35
                        or.InferTypeArguments();
 
36
                        or.CheckApplicability();
 
37
                        
 
38
                        Candidate result = or.FindBestCandidate();
 
39
                        MemberLookupHelper.Log("Overload resolution finished. Winning candidate = " + result);
 
40
                        acceptableMatch = result.Status == CandidateStatus.Success;
 
41
                        if (substituteInferredTypes)
 
42
                                return result.Method;
 
43
                        else
 
44
                                return result.OriginalMethod;
 
45
                }
 
46
                
 
47
                enum CandidateStatus
 
48
                {
 
49
                        Success,
 
50
                        WrongParameterCount,
 
51
                        TypeInferenceFailed,
 
52
                        NotApplicable
 
53
                }
 
54
                
 
55
                sealed class Candidate
 
56
                {
 
57
                        public bool IsExpanded;
 
58
                        public IMethodOrProperty Method;
 
59
                        public IMethodOrProperty OriginalMethod;
 
60
                        public CandidateStatus Status = CandidateStatus.Success;
 
61
                        public int ApplicableArgumentCount;
 
62
                        
 
63
                        public IList<IParameter> Parameters {
 
64
                                get { return Method.Parameters; }
 
65
                        }
 
66
                        
 
67
                        public int TypeParameterCount {
 
68
                                get {
 
69
                                        IMethod m = Method as IMethod;
 
70
                                        if (m != null)
 
71
                                                return m.TypeParameters.Count;
 
72
                                        else
 
73
                                                return 0;
 
74
                                }
 
75
                        }
 
76
                        
 
77
                        public Candidate(IMethodOrProperty method)
 
78
                        {
 
79
                                if (method == null)
 
80
                                        throw new ArgumentNullException("method");
 
81
                                this.Method = method;
 
82
                                this.OriginalMethod = method;
 
83
                        }
 
84
                        
 
85
                        public override string ToString()
 
86
                        {
 
87
                                return "[Candidate: " + Method + ", Status=" + Status + "]";
 
88
                        }
 
89
                }
 
90
                
 
91
                List<Candidate> candidates;
 
92
                IList<IReturnType> arguments;
 
93
                bool allowAdditionalArguments;
 
94
                
 
95
                /// <summary>
 
96
                /// For methods having a params-array as last parameter, expand the params array to
 
97
                /// n parameters of the element type and add those as new candidates.
 
98
                /// Mark candidates with the wrong parameter count as Status.WrongParameterCount.
 
99
                /// </summary>
 
100
                void ConstructExpandedForms()
 
101
                {
 
102
                        LogStep("Step 1 (Construct expanded forms)");
 
103
                        foreach (Candidate candidate in candidates.ToArray()) {
 
104
                                if (candidate.Status == CandidateStatus.Success) {
 
105
                                        if (candidate.Parameters.Count > 0 && arguments.Count >= candidate.Parameters.Count - 1) {
 
106
                                                IParameter lastParameter = candidate.Parameters[candidate.Parameters.Count - 1];
 
107
                                                if (lastParameter.IsParams && lastParameter.ReturnType != null && lastParameter.ReturnType.IsArrayReturnType) {
 
108
                                                        // try to construct an expanded form with the correct parameter count
 
109
                                                        IReturnType elementType = lastParameter.ReturnType.CastToArrayReturnType().ArrayElementType;
 
110
                                                        IMethodOrProperty expanded = (IMethodOrProperty)candidate.Method.CreateSpecializedMember();
 
111
                                                        expanded.Parameters.RemoveAt(candidate.Parameters.Count - 1);
 
112
                                                        int index = 0;
 
113
                                                        while (expanded.Parameters.Count < arguments.Count) {
 
114
                                                                expanded.Parameters.Add(new DefaultParameter(lastParameter.Name + (index++), elementType, lastParameter.Region));
 
115
                                                        }
 
116
                                                        candidates.Add(new Candidate(expanded) {
 
117
                                                                        IsExpanded = true,
 
118
                                                                        OriginalMethod = candidate.Method
 
119
                                                                       });
 
120
                                                }
 
121
                                        }
 
122
                                        
 
123
                                        if (allowAdditionalArguments) {
 
124
                                                if (candidate.Parameters.Count < arguments.Count) {
 
125
                                                        candidate.Status = CandidateStatus.WrongParameterCount;
 
126
                                                }
 
127
                                        } else {
 
128
                                                if (candidate.Parameters.Count != arguments.Count) {
 
129
                                                        candidate.Status = CandidateStatus.WrongParameterCount;
 
130
                                                }
 
131
                                        }
 
132
                                }
 
133
                        }
 
134
                }
 
135
                
 
136
                /// <summary>
 
137
                /// Infer the type arguments for generic methods.
 
138
                /// </summary>
 
139
                void InferTypeArguments()
 
140
                {
 
141
                        LogStep("Step 2 (Infer type arguments)");
 
142
                        foreach (Candidate candidate in candidates) {
 
143
                                IMethod method = candidate.Method as IMethod;
 
144
                                if (method != null && method.TypeParameters.Count > 0
 
145
                                    && candidate.Status == CandidateStatus.Success)
 
146
                                {
 
147
                                        bool success;
 
148
                                        IReturnType[] typeArguments = TypeInference.InferTypeArguments(method, arguments, out success);
 
149
                                        if (!success) {
 
150
                                                candidate.Status = CandidateStatus.TypeInferenceFailed;
 
151
                                        }
 
152
                                        candidate.Method = ApplyTypeArgumentsToMethod(method, typeArguments);
 
153
                                }
 
154
                        }
 
155
                }
 
156
                
 
157
                static IMethod ApplyTypeArgumentsToMethod(IMethod genericMethod, IList<IReturnType> typeArguments)
 
158
                {
 
159
                        if (typeArguments != null && typeArguments.Count > 0) {
 
160
                                // apply inferred type arguments
 
161
                                IMethod method = (IMethod)genericMethod.CreateSpecializedMember();
 
162
                                method.ReturnType = ConstructedReturnType.TranslateType(method.ReturnType, typeArguments, true);
 
163
                                for (int i = 0; i < method.Parameters.Count; ++i) {
 
164
                                        method.Parameters[i].ReturnType = ConstructedReturnType.TranslateType(method.Parameters[i].ReturnType, typeArguments, true);
 
165
                                }
 
166
                                for (int i = 0; i < Math.Min(typeArguments.Count, method.TypeParameters.Count); i++) {
 
167
                                        var tp = new BoundTypeParameter(method.TypeParameters[i], method.DeclaringType, method);
 
168
                                        tp.BoundTo = typeArguments[i];
 
169
                                        method.TypeParameters[i] = tp;
 
170
                                }
 
171
                                return method;
 
172
                        } else {
 
173
                                return genericMethod;
 
174
                        }
 
175
                }
 
176
                
 
177
                void CheckApplicability()
 
178
                {
 
179
                        LogStep("Step 3 (CheckApplicability)");
 
180
                        foreach (Candidate candidate in candidates) {
 
181
                                int c = Math.Min(arguments.Count, candidate.Parameters.Count);
 
182
                                for (int i = 0; i < c; i++) {
 
183
                                        if (MemberLookupHelper.IsApplicable(arguments[i], candidate.Parameters[i], candidate.Method as IMethod))
 
184
                                                candidate.ApplicableArgumentCount++;
 
185
                                }
 
186
                                if (candidate.Status == CandidateStatus.Success && candidate.ApplicableArgumentCount < arguments.Count) {
 
187
                                        candidate.Status = CandidateStatus.NotApplicable;
 
188
                                }
 
189
                        }
 
190
                }
 
191
                
 
192
                Candidate FindBestCandidate()
 
193
                {
 
194
                        LogStep("Step 4 (FindBestCandidate)");
 
195
                        
 
196
                        // Find a candidate that is better than all other candidates
 
197
                        Candidate best = null;
 
198
                        foreach (Candidate candidate in candidates) {
 
199
                                if (candidate.Status == CandidateStatus.Success) {
 
200
                                        if (best == null || GetBetterFunctionMember(best, candidate) == 2) {
 
201
                                                best = candidate;
 
202
                                        }
 
203
                                }
 
204
                        }
 
205
                        
 
206
                        if (best != null)
 
207
                                return best;
 
208
                        
 
209
                        // no successful candidate found:
 
210
                        // find the candidate that is nearest to being applicable
 
211
                        // first try only candidates with the correct parameter count
 
212
                        foreach (Candidate candidate in candidates) {
 
213
                                if (candidate.Status != CandidateStatus.WrongParameterCount) {
 
214
                                        if (best == null || candidate.ApplicableArgumentCount > best.ApplicableArgumentCount)
 
215
                                                best = candidate;
 
216
                                }
 
217
                        }
 
218
                        if (best != null)
 
219
                                return best;
 
220
                        // if all candidates have the wrong parameter count, return the candidate
 
221
                        // with the most applicable parameters.
 
222
                        best = candidates[0];
 
223
                        foreach (Candidate candidate in candidates) {
 
224
                                if (candidate.ApplicableArgumentCount > best.ApplicableArgumentCount)
 
225
                                        best = candidate;
 
226
                        }
 
227
                        return best;
 
228
                }
 
229
                
 
230
                /// <summary>
 
231
                /// Gets which function member is better. (§ 14.4.2.2)
 
232
                /// </summary>
 
233
                /// <returns>0 if neither method is better. 1 if c1 is better. 2 if c2 is better.</returns>
 
234
                int GetBetterFunctionMember(Candidate c1, Candidate c2)
 
235
                {
 
236
                        int length = Math.Min(Math.Min(c1.Parameters.Count, c2.Parameters.Count), arguments.Count);
 
237
                        bool foundBetterParamIn1 = false;
 
238
                        bool foundBetterParamIn2 = false;
 
239
                        for (int i = 0; i < length; i++) {
 
240
                                if (arguments[i] == null)
 
241
                                        continue;
 
242
                                int res = MemberLookupHelper.GetBetterConversion(arguments[i], c1.Parameters[i].ReturnType, c2.Parameters[i].ReturnType);
 
243
                                if (res == 1) foundBetterParamIn1 = true;
 
244
                                if (res == 2) foundBetterParamIn2 = true;
 
245
                        }
 
246
                        if (foundBetterParamIn1 && !foundBetterParamIn2)
 
247
                                return 1;
 
248
                        if (foundBetterParamIn2 && !foundBetterParamIn1)
 
249
                                return 2;
 
250
                        if (foundBetterParamIn1 && foundBetterParamIn2)
 
251
                                return 0; // ambigous
 
252
                        // If none conversion is better than any other, it is possible that the
 
253
                        // expanded parameter lists are the same:
 
254
                        for (int i = 0; i < length; i++) {
 
255
                                if (!object.Equals(c1.Parameters[i].ReturnType, c2.Parameters[i].ReturnType)) {
 
256
                                        // if expanded parameters are not the same, neither function member is better
 
257
                                        return 0;
 
258
                                }
 
259
                        }
 
260
                        
 
261
                        // the expanded parameters are the same, apply the tie-breaking rules from the spec:
 
262
                        
 
263
                        // if one method is generic and the other non-generic, the non-generic is better
 
264
                        bool m1IsGeneric = c1.TypeParameterCount > 0;
 
265
                        bool m2IsGeneric = c2.TypeParameterCount > 0;
 
266
                        if (m1IsGeneric && !m2IsGeneric) return 2;
 
267
                        if (m2IsGeneric && !m1IsGeneric) return 1;
 
268
                        
 
269
                        // for params parameters: non-expanded calls are better
 
270
                        if (c1.IsExpanded && !c2.IsExpanded) return 2;
 
271
                        if (c2.IsExpanded && !c1.IsExpanded) return 1;
 
272
                        
 
273
                        // if the number of parameters is different, the one with more parameters is better
 
274
                        // this occurs when only when both methods are expanded
 
275
                        if (c1.OriginalMethod.Parameters.Count > c2.OriginalMethod.Parameters.Count) return 1;
 
276
                        if (c2.OriginalMethod.Parameters.Count > c1.OriginalMethod.Parameters.Count) return 2;
 
277
                        
 
278
                        IReturnType[] m1ParamTypes = new IReturnType[c1.Parameters.Count];
 
279
                        IReturnType[] m2ParamTypes = new IReturnType[c2.Parameters.Count];
 
280
                        for (int i = 0; i < m1ParamTypes.Length; i++) {
 
281
                                m1ParamTypes[i] = c1.Parameters[i].ReturnType;
 
282
                                m2ParamTypes[i] = c2.Parameters[i].ReturnType;
 
283
                        }
 
284
                        return GetMoreSpecific(m1ParamTypes, m2ParamTypes);
 
285
                }
 
286
                
 
287
                
 
288
                /// <summary>
 
289
                /// Gets which return type list is more specific.
 
290
                /// § 14.4.2.2: types with generic arguments are less specific than types with fixed arguments
 
291
                /// </summary>
 
292
                /// <returns>0 if both are equally specific, 1 if <paramref name="r"/> is more specific,
 
293
                /// 2 if <paramref name="s"/> is more specific.</returns>
 
294
                static int GetMoreSpecific(IList<IReturnType> r, IList<IReturnType> s)
 
295
                {
 
296
                        bool foundMoreSpecificParamIn1 = false;
 
297
                        bool foundMoreSpecificParamIn2 = false;
 
298
                        int length = Math.Min(r.Count, s.Count);
 
299
                        for (int i = 0; i < length; i++) {
 
300
                                int res = GetMoreSpecific(r[i], s[i]);
 
301
                                if (res == 1) foundMoreSpecificParamIn1 = true;
 
302
                                if (res == 2) foundMoreSpecificParamIn2 = true;
 
303
                        }
 
304
                        if (foundMoreSpecificParamIn1 && !foundMoreSpecificParamIn2)
 
305
                                return 1;
 
306
                        if (foundMoreSpecificParamIn2 && !foundMoreSpecificParamIn1)
 
307
                                return 2;
 
308
                        return 0;
 
309
                }
 
310
                
 
311
                static int GetMoreSpecific(IReturnType r, IReturnType s)
 
312
                {
 
313
                        if (r == null && s == null) return 0;
 
314
                        if (r == null) return 2;
 
315
                        if (s == null) return 1;
 
316
                        if (r.IsGenericReturnType && !(s.IsGenericReturnType))
 
317
                                return 2;
 
318
                        if (s.IsGenericReturnType && !(r.IsGenericReturnType))
 
319
                                return 1;
 
320
                        if (r.IsArrayReturnType && s.IsArrayReturnType)
 
321
                                return GetMoreSpecific(r.CastToArrayReturnType().ArrayElementType, s.CastToArrayReturnType().ArrayElementType);
 
322
                        if (r.IsConstructedReturnType && s.IsConstructedReturnType)
 
323
                                return GetMoreSpecific(r.CastToConstructedReturnType().TypeArguments, s.CastToConstructedReturnType().TypeArguments);
 
324
                        return 0;
 
325
                }
 
326
                
 
327
                [System.Diagnostics.ConditionalAttribute("DEBUG")]
 
328
                void LogStep(string title)
 
329
                {
 
330
                        MemberLookupHelper.Log("  candidates = ", candidates);
 
331
                        MemberLookupHelper.Log("Overload resolution (" + title + ")");
 
332
                }
 
333
                
 
334
                [System.Diagnostics.ConditionalAttribute("DEBUG")]
 
335
                void Log(string text)
 
336
                {
 
337
                        MemberLookupHelper.Log(text);
 
338
                }
 
339
        }
 
340
}