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