New tests.
[mono.git] / mcs / mcs / linq.cs
1 //
2 // linq.cs: support for query expressions
3 //
4 // Authors: Marek Safar (marek.safar@gmail.com)
5 //
6 // Dual licensed under the terms of the MIT X11 or GNU GPL
7 //
8 // Copyright 2007-2008 Novell, Inc
9 //
10
11 using System;
12 using System.Reflection;
13 using System.Collections.Generic;
14
15 namespace Mono.CSharp.Linq
16 {
17         // NOTES:
18         // Expression should be IExpression to save some memory and make a few things
19         // easier to read
20         //
21         //
22
23         class QueryExpression : AQueryClause
24         {
25                 public QueryExpression (Block block, AQueryClause query)
26                         : base (null, null, query.Location)
27                 {
28                         this.next = query;
29                 }
30
31                 public override Expression BuildQueryClause (ResolveContext ec, Expression lSide)
32                 {
33                         return next.BuildQueryClause (ec, lSide);
34                 }
35
36                 protected override Expression DoResolve (ResolveContext ec)
37                 {
38                         int counter = QueryBlock.TransparentParameter.Counter;
39
40                         Expression e = BuildQueryClause (ec, null);
41                         if (e != null)
42                                 e = e.Resolve (ec);
43
44                         //
45                         // Reset counter in probing mode to ensure that all transparent
46                         // identifier anonymous types are created only once
47                         //
48                         if (ec.IsInProbingMode)
49                                 QueryBlock.TransparentParameter.Counter = counter;
50
51                         return e;
52                 }
53
54                 protected override string MethodName {
55                         get { throw new NotSupportedException (); }
56                 }
57         }
58
59         abstract class AQueryClause : ShimExpression
60         {
61                 class QueryExpressionAccess : MemberAccess
62                 {
63                         public QueryExpressionAccess (Expression expr, string methodName, Location loc)
64                                 : base (expr, methodName, loc)
65                         {
66                         }
67
68                         public QueryExpressionAccess (Expression expr, string methodName, TypeArguments typeArguments, Location loc)
69                                 : base (expr, methodName, typeArguments, loc)
70                         {
71                         }
72
73                         protected override Expression Error_MemberLookupFailed (ResolveContext ec, TypeSpec container_type, TypeSpec qualifier_type,
74                                 TypeSpec queried_type, string name, int arity, string class_name, MemberKind mt, BindingRestriction bf)
75                         {
76                                 ec.Report.Error (1935, loc, "An implementation of `{0}' query expression pattern could not be found. " +
77                                         "Are you missing `System.Linq' using directive or `System.Core.dll' assembly reference?",
78                                         name);
79                                 return null;
80                         }
81                 }
82
83                 class QueryExpressionInvocation : Invocation, MethodGroupExpr.IErrorHandler
84                 {
85                         public QueryExpressionInvocation (QueryExpressionAccess expr, Arguments arguments)
86                                 : base (expr, arguments)
87                         {
88                         }
89
90                         protected override MethodGroupExpr DoResolveOverload (ResolveContext ec)
91                         {
92                                 mg.CustomErrorHandler = this;
93                                 MethodGroupExpr rmg = mg.OverloadResolve (ec, ref arguments, false, loc);
94                                 return rmg;
95                         }
96
97                         public bool AmbiguousCall (ResolveContext ec, MethodSpec ambiguous)
98                         {
99                                 ec.Report.SymbolRelatedToPreviousError (mg.BestCandidate);
100                                 ec.Report.SymbolRelatedToPreviousError (ambiguous);
101                                 ec.Report.Error (1940, loc, "Ambiguous implementation of the query pattern `{0}' for source type `{1}'",
102                                         mg.Name, mg.InstanceExpression.GetSignatureForError ());
103                                 return true;
104                         }
105
106                         public bool NoExactMatch (ResolveContext ec, MethodSpec method)
107                         {
108                                 var pd = method.Parameters;
109                                 TypeSpec source_type = pd.ExtensionMethodType;
110                                 if (source_type != null) {
111                                         Argument a = arguments [0];
112
113                                         if (TypeManager.IsGenericType (source_type) && TypeManager.ContainsGenericParameters (source_type)) {
114                                                 TypeInferenceContext tic = new TypeInferenceContext (source_type.TypeArguments);
115                                                 tic.OutputTypeInference (ec, a.Expr, source_type);
116                                                 if (tic.FixAllTypes (ec)) {
117                                                         source_type = source_type.GetDefinition ().MakeGenericType (tic.InferredTypeArguments);
118                                                 }
119                                         }
120
121                                         if (!Convert.ImplicitConversionExists (ec, a.Expr, source_type)) {
122                                                 ec.Report.Error (1936, loc, "An implementation of `{0}' query expression pattern for source type `{1}' could not be found",
123                                                         mg.Name, TypeManager.CSharpName (a.Type));
124                                                 return true;
125                                         }
126                                 }
127
128                                 if (!method.IsGeneric)
129                                         return false;
130
131                                 if (mg.Name == "SelectMany") {
132                                         ec.Report.Error (1943, loc,
133                                                 "An expression type is incorrect in a subsequent `from' clause in a query expression with source type `{0}'",
134                                                 arguments [0].GetSignatureForError ());
135                                 } else {
136                                         ec.Report.Error (1942, loc,
137                                                 "An expression type in `{0}' clause is incorrect. Type inference failed in the call to `{1}'",
138                                                 mg.Name.ToLower (), mg.Name);
139                                 }
140
141                                 return true;
142                         }
143                 }
144
145                 // TODO: protected
146                 public AQueryClause next;
147                 protected ToplevelBlock block;
148
149                 protected AQueryClause (ToplevelBlock block, Expression expr, Location loc)
150                          : base (expr)
151                 {
152                         this.block = block;
153                         this.loc = loc;
154                 }
155                 
156                 protected override void CloneTo (CloneContext clonectx, Expression target)
157                 {
158                         base.CloneTo (clonectx, target);
159
160                         AQueryClause t = (AQueryClause) target;
161
162                         if (block != null)
163                                 t.block = (ToplevelBlock) block.Clone (clonectx);
164
165                         if (next != null)
166                                 t.next = (AQueryClause) next.Clone (clonectx);
167                 }
168
169                 protected override Expression DoResolve (ResolveContext ec)
170                 {
171                         return expr.Resolve (ec);
172                 }
173
174                 public virtual Expression BuildQueryClause (ResolveContext ec, Expression lSide)
175                 {
176                         Arguments args;
177                         CreateArguments (ec, out args);
178                         lSide = CreateQueryExpression (lSide, args);
179                         if (next != null) {
180                                 Select s = next as Select;
181                                 if (s == null || s.IsRequired)
182                                         return next.BuildQueryClause (ec, lSide);
183                                         
184                                 // Skip transparent select clause if any clause follows
185                                 if (next.next != null)
186                                         return next.next.BuildQueryClause (ec, lSide);
187                         }
188
189                         return lSide;
190                 }
191
192                 protected virtual void CreateArguments (ResolveContext ec, out Arguments args)
193                 {
194                         args = new Arguments (2);
195
196                         LambdaExpression selector = new LambdaExpression (loc);
197                         selector.Block = block;
198                         selector.Block.AddStatement (new ContextualReturn (expr));
199
200                         args.Add (new Argument (selector));
201                 }
202
203                 protected Invocation CreateQueryExpression (Expression lSide, Arguments arguments)
204                 {
205                         return new QueryExpressionInvocation (
206                                 new QueryExpressionAccess (lSide, MethodName, loc), arguments);
207                 }
208
209                 protected Invocation CreateQueryExpression (Expression lSide, TypeArguments typeArguments, Arguments arguments)
210                 {
211                         return new QueryExpressionInvocation (
212                                 new QueryExpressionAccess (lSide, MethodName, typeArguments, loc), arguments);
213                 }
214
215                 protected abstract string MethodName { get; }
216
217                 public virtual AQueryClause Next {
218                         set {
219                                 next = value;
220                         }
221                 }
222
223                 public AQueryClause Tail {
224                         get {
225                                 return next == null ? this : next.Tail;
226                         }
227                 }
228         }
229
230         //
231         // A query clause with an identifier (range variable)
232         //
233         abstract class ARangeVariableQueryClause : AQueryClause
234         {
235                 sealed class RangeAnonymousTypeParameter : AnonymousTypeParameter
236                 {
237                         public RangeAnonymousTypeParameter (Expression initializer, SimpleMemberName parameter)
238                                 : base (initializer, parameter.Value, parameter.Location)
239                         {
240                         }
241
242                         protected override void Error_InvalidInitializer (ResolveContext ec, string initializer)
243                         {
244                                 ec.Report.Error (1932, loc, "A range variable `{0}' cannot be initialized with `{1}'",
245                                         Name, initializer);
246                         }
247                 }
248
249                 protected ARangeVariableQueryClause (ToplevelBlock block, Expression expr)
250                         : base (block, expr, expr.Location)
251                 {
252                 }
253
254                 protected static Expression CreateRangeVariableType (ToplevelBlock block, TypeContainer container, SimpleMemberName name, Expression init)
255                 {
256                         var args = new List<AnonymousTypeParameter> (2);
257                         args.Add (new AnonymousTypeParameter (block.Parameters [0]));
258                         args.Add (new RangeAnonymousTypeParameter (init, name));
259                         return new NewAnonymousType (args, container, name.Location);
260                 }
261         }
262
263         class QueryStartClause : AQueryClause
264         {
265                 public QueryStartClause (Expression expr)
266                         : base (null, expr, expr.Location)
267                 {
268                 }
269
270                 public override Expression BuildQueryClause (ResolveContext ec, Expression lSide)
271                 {
272                         expr = expr.Resolve (ec);
273                         if (expr == null)
274                                 return null;
275
276                         if (expr.Type == InternalType.Dynamic || expr.Type == TypeManager.void_type) {
277                                 ec.Report.Error (1979, expr.Location,
278                                         "Query expression with a source or join sequence of type `{0}' is not allowed",
279                                         TypeManager.CSharpName (expr.Type));
280                                 return null;
281                         }
282
283                         return next.BuildQueryClause (ec, expr);
284                 }
285
286                 protected override Expression DoResolve (ResolveContext ec)
287                 {
288                         Expression e = BuildQueryClause (ec, null);
289                         return e.Resolve (ec);
290                 }
291
292                 protected override string MethodName {
293                         get { throw new NotSupportedException (); }
294                 }
295         }
296
297         class Cast : QueryStartClause
298         {
299                 // We don't have to clone cast type
300                 readonly FullNamedExpression type_expr;
301
302                 public Cast (FullNamedExpression type, Expression expr)
303                         : base (expr)
304                 {
305                         this.type_expr = type;
306                 }
307                 
308                 public override Expression BuildQueryClause (ResolveContext ec, Expression lSide)
309                 {
310                         lSide = CreateQueryExpression (expr, new TypeArguments (type_expr), null);
311                         if (next != null)
312                                 return next.BuildQueryClause (ec, lSide);
313
314                         return lSide;
315                 }
316
317                 protected override string MethodName {
318                         get { return "Cast"; }
319                 }
320         }
321
322         class GroupBy : AQueryClause
323         {
324                 Expression element_selector;
325                 ToplevelBlock element_block;
326                 
327                 public GroupBy (ToplevelBlock block, Expression elementSelector, ToplevelBlock elementBlock, Expression keySelector, Location loc)
328                         : base (block, keySelector, loc)
329                 {
330                         //
331                         // Optimizes clauses like `group A by A'
332                         //
333                         if (!elementSelector.Equals (keySelector)) {
334                                 this.element_selector = elementSelector;
335                                 this.element_block = elementBlock;
336                         }
337                 }
338
339                 protected override void CreateArguments (ResolveContext ec, out Arguments args)
340                 {
341                         base.CreateArguments (ec, out args);
342
343                         if (element_selector != null) {
344                                 LambdaExpression lambda = new LambdaExpression (element_selector.Location);
345                                 lambda.Block = element_block;
346                                 lambda.Block.AddStatement (new ContextualReturn (element_selector));
347                                 args.Add (new Argument (lambda));
348                         }
349                 }
350
351                 protected override void CloneTo (CloneContext clonectx, Expression target)
352                 {
353                         GroupBy t = (GroupBy) target;
354                         if (element_selector != null) {
355                                 t.element_selector = element_selector.Clone (clonectx);
356                                 t.element_block = (ToplevelBlock) element_block.Clone (clonectx);
357                         }
358
359                         base.CloneTo (clonectx, t);
360                 }
361
362                 protected override string MethodName {
363                         get { return "GroupBy"; }
364                 }
365         }
366
367         class Join : ARangeVariableQueryClause
368         {
369                 readonly SimpleMemberName lt;
370                 ToplevelBlock inner_selector, outer_selector;
371
372                 public Join (ToplevelBlock block, SimpleMemberName lt, Expression inner, ToplevelBlock outerSelector, ToplevelBlock innerSelector, Location loc)
373                         : base (block, inner)
374                 {
375                         this.lt = lt;
376                         this.outer_selector = outerSelector;
377                         this.inner_selector = innerSelector;
378                 }
379
380                 protected override void CreateArguments (ResolveContext ec, out Arguments args)
381                 {
382                         args = new Arguments (4);
383
384                         args.Add (new Argument (expr));
385
386                         LambdaExpression lambda = new LambdaExpression (outer_selector.StartLocation);
387                         lambda.Block = outer_selector;
388                         args.Add (new Argument (lambda));
389
390                         lambda = new LambdaExpression (inner_selector.StartLocation);
391                         lambda.Block = inner_selector;
392                         args.Add (new Argument (lambda));
393
394                         Expression result_selector_expr;
395                         SimpleMemberName into_variable = GetIntoVariable ();
396                         //
397                         // When select follows use is as result selector
398                         //
399                         if (next is Select) {
400                                 result_selector_expr = next.Expr;
401                                 next = next.next;
402                         } else {
403                                 result_selector_expr = CreateRangeVariableType (block, ec.MemberContext.CurrentMemberDefinition.Parent, into_variable,
404                                         new SimpleName (into_variable.Value, into_variable.Location));
405                         }
406
407                         LambdaExpression result_selector = new LambdaExpression (lt.Location);
408                         result_selector.Block = new QueryBlock (ec.Compiler, block.Parent, block.Parameters, into_variable, block.StartLocation);
409                         result_selector.Block.AddStatement (new ContextualReturn (result_selector_expr));
410
411                         args.Add (new Argument (result_selector));
412                 }
413
414                 protected virtual SimpleMemberName GetIntoVariable ()
415                 {
416                         return lt;
417                 }
418
419                 protected override void CloneTo (CloneContext clonectx, Expression target)
420                 {
421                         Join t = (Join) target;
422                         t.inner_selector = (ToplevelBlock) inner_selector.Clone (clonectx);
423                         t.outer_selector = (ToplevelBlock) outer_selector.Clone (clonectx);
424                         base.CloneTo (clonectx, t);
425                 }       
426
427                 protected override string MethodName {
428                         get { return "Join"; }
429                 }
430         }
431
432         class GroupJoin : Join
433         {
434                 readonly SimpleMemberName into;
435
436                 public GroupJoin (ToplevelBlock block, SimpleMemberName lt, Expression inner,
437                         ToplevelBlock outerSelector, ToplevelBlock innerSelector, SimpleMemberName into, Location loc)
438                         : base (block, lt, inner, outerSelector, innerSelector, loc)
439                 {
440                         this.into = into;
441                 }
442
443                 protected override SimpleMemberName GetIntoVariable ()
444                 {
445                         return into;
446                 }
447
448                 protected override string MethodName {
449                         get { return "GroupJoin"; }
450                 }
451         }
452
453         class Let : ARangeVariableQueryClause
454         {
455                 public Let (ToplevelBlock block, TypeContainer container, SimpleMemberName identifier, Expression expr)
456                         : base (block, CreateRangeVariableType (block, container, identifier, expr))
457                 {
458                 }
459
460                 protected override string MethodName {
461                         get { return "Select"; }
462                 }
463         }
464
465         class Select : AQueryClause
466         {
467                 public Select (ToplevelBlock block, Expression expr, Location loc)
468                         : base (block, expr, loc)
469                 {
470                 }
471                 
472                 //
473                 // For queries like `from a orderby a select a'
474                 // the projection is transparent and select clause can be safely removed 
475                 //
476                 public bool IsRequired {
477                         get {
478                                 SimpleName sn = expr as SimpleName;
479                                 if (sn == null)
480                                         return true;
481
482                                 return sn.Name != block.Parameters.FixedParameters [0].Name;
483                         }
484                 }
485
486                 protected override string MethodName {
487                         get { return "Select"; }
488                 }
489         }
490
491         class SelectMany : ARangeVariableQueryClause
492         {
493                 SimpleMemberName lt;
494
495                 public SelectMany (ToplevelBlock block, SimpleMemberName lt, Expression expr)
496                         : base (block, expr)
497                 {
498                         this.lt = lt;
499                 }
500
501                 protected override void CreateArguments (ResolveContext ec, out Arguments args)
502                 {
503                         base.CreateArguments (ec, out args);
504
505                         Expression result_selector_expr;
506                         //
507                         // When select follow use is as result selector
508                         //
509                         if (next is Select) {
510                                 result_selector_expr = next.Expr;
511                                 next = next.next;
512                         } else {
513                                 result_selector_expr = CreateRangeVariableType (block, ec.MemberContext.CurrentMemberDefinition.Parent, lt, new SimpleName (lt.Value, lt.Location));
514                         }
515
516                         LambdaExpression result_selector = new LambdaExpression (lt.Location);
517                         result_selector.Block = new QueryBlock (ec.Compiler, block.Parent, block.Parameters, lt, block.StartLocation);
518                         result_selector.Block.AddStatement (new ContextualReturn (result_selector_expr));
519
520                         args.Add (new Argument (result_selector));
521                 }
522
523                 protected override string MethodName {
524                         get { return "SelectMany"; }
525                 }
526         }
527
528         class Where : AQueryClause
529         {
530                 public Where (ToplevelBlock block, BooleanExpression expr, Location loc)
531                         : base (block, expr, loc)
532                 {
533                 }
534
535                 protected override string MethodName {
536                         get { return "Where"; }
537                 }
538         }
539
540         class OrderByAscending : AQueryClause
541         {
542                 public OrderByAscending (ToplevelBlock block,Expression expr)
543                         : base (block, expr, expr.Location)
544                 {
545                 }
546
547                 protected override string MethodName {
548                         get { return "OrderBy"; }
549                 }
550         }
551
552         class OrderByDescending : AQueryClause
553         {
554                 public OrderByDescending (ToplevelBlock block, Expression expr)
555                         : base (block, expr, expr.Location)
556                 {
557                 }
558
559                 protected override string MethodName {
560                         get { return "OrderByDescending"; }
561                 }
562         }
563
564         class ThenByAscending : OrderByAscending
565         {
566                 public ThenByAscending (ToplevelBlock block, Expression expr)
567                         : base (block, expr)
568                 {
569                 }
570
571                 protected override string MethodName {
572                         get { return "ThenBy"; }
573                 }
574         }
575
576         class ThenByDescending : OrderByDescending
577         {
578                 public ThenByDescending (ToplevelBlock block, Expression expr)
579                         : base (block, expr)
580                 {
581                 }
582
583                 protected override string MethodName {
584                         get { return "ThenByDescending"; }
585                 }
586         }
587
588         //
589         // Implicit query block
590         //
591         class QueryBlock : ToplevelBlock
592         {
593                 //
594                 // Transparent parameters are used to package up the intermediate results
595                 // and pass them onto next clause
596                 //
597                 public sealed class TransparentParameter : ImplicitLambdaParameter
598                 {
599                         public static int Counter;
600                         const string ParameterNamePrefix = "<>__TranspIdent";
601
602                         public readonly ParametersCompiled Parent;
603                         public readonly string Identifier;
604
605                         public TransparentParameter (ParametersCompiled parent, SimpleMemberName identifier)
606                                 : base (ParameterNamePrefix + Counter++, identifier.Location)
607                         {
608                                 Parent = parent;
609                                 Identifier = identifier.Value;
610                         }
611
612                         public new static void Reset ()
613                         {
614                                 Counter = 0;
615                         }
616                 }
617
618                 public sealed class ImplicitQueryParameter : ImplicitLambdaParameter
619                 {
620                         public ImplicitQueryParameter (string name, Location loc)
621                                 : base (name, loc)
622                         {
623                         }
624                 }
625
626                 public QueryBlock (CompilerContext ctx, Block parent, SimpleMemberName lt, Location start)
627                         : base (ctx, parent, new ParametersCompiled (ctx, new ImplicitQueryParameter (lt.Value, lt.Location)), start)
628                 {
629                         if (parent != null)
630                                 base.CheckParentConflictName (parent.Toplevel, lt.Value, lt.Location);
631                 }
632
633                 public QueryBlock (CompilerContext ctx, Block parent, ParametersCompiled parameters, SimpleMemberName lt, Location start)
634                         : base (ctx, parent, new ParametersCompiled (ctx, parameters [0].Clone (), new ImplicitQueryParameter (lt.Value, lt.Location)), start)
635                 {
636                 }
637
638                 public QueryBlock (CompilerContext ctx, Block parent, Location start)
639                         : base (ctx, parent, parent.Toplevel.Parameters.Clone (), start)
640                 {
641                 }
642
643                 public void AddTransparentParameter (CompilerContext ctx, SimpleMemberName name)
644                 {
645                         base.CheckParentConflictName (this, name.Value, name.Location);
646
647                         parameters = new ParametersCompiled (ctx, new TransparentParameter (parameters, name));
648                 }
649
650                 protected override bool CheckParentConflictName (ToplevelBlock block, string name, Location l)
651                 {
652                         return true;
653                 }
654
655                 // 
656                 // Query parameter reference can include transparent parameters
657                 //
658                 protected override Expression GetParameterReferenceExpression (string name, Location loc)
659                 {
660                         Expression expr = base.GetParameterReferenceExpression (name, loc);
661                         if (expr != null)
662                                 return expr;
663
664                         TransparentParameter tp = parameters [0] as TransparentParameter;
665                         while (tp != null) {
666                                 if (tp.Identifier == name)
667                                         break;
668
669                                 TransparentParameter tp_next = tp.Parent [0] as TransparentParameter;
670                                 if (tp_next == null) {
671                                         if (tp.Parent.GetParameterIndexByName (name) >= 0)
672                                                 break;
673                                 }
674
675                                 tp = tp_next;
676                         }
677
678                         if (tp != null) {
679                                 expr = new SimpleName (parameters[0].Name, loc);
680                                 TransparentParameter tp_cursor = (TransparentParameter) parameters[0];
681                                 while (tp_cursor != tp) {
682                                         tp_cursor = (TransparentParameter) tp_cursor.Parent[0];
683                                         expr = new MemberAccess (expr, tp_cursor.Name);
684                                 }
685
686                                 return new MemberAccess (expr, name);
687                         }
688
689                         return null;
690                 }
691
692                 protected override void Error_AlreadyDeclared (Location loc, string var, string reason)
693                 {
694                         Report.Error (1931, loc, "A range variable `{0}' conflicts with a previous declaration of `{0}'",
695                                 var);
696                 }
697                 
698                 protected override void Error_AlreadyDeclared (Location loc, string var)
699                 {
700                         Report.Error (1930, loc, "A range variable `{0}' has already been declared in this scope",
701                                 var);           
702                 }
703                 
704                 public override void Error_AlreadyDeclaredTypeParameter (Report r, Location loc, string name, string conflict)
705                 {
706                         r.Error (1948, loc, "A range variable `{0}' conflicts with a method type parameter",
707                                 name);
708                 }
709         }
710 }