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