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