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