mcs/gmcs/linq.cs

   1 //
   2 // linq.cs: support for query expressions
   3 //
   4 // Authors: Marek Safar (marek.safar@gmail.com)
   5 //
   6 // Licensed under the terms of the GNU GPL
   7 //
   8 // (C) 2007 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         public class QueryExpression : ARangeVariableQueryClause
  24         {
  25                 public QueryExpression (Block block, Expression from, AQueryClause query)
  26                         : base (block, from, from.Location)
  27                 {
  28                         this.next = query;
  29                 }
  30
  31                 public override Expression DoResolve (EmitContext ec)
  32                 {
  33                         Expression e = BuildQueryClause (ec, expr, null, null);
  34                         e = e.Resolve (ec);
  35                         return e;
  36                 }
  37
  38                 protected override string MethodName {
  39                         get { throw new NotSupportedException (); }
  40                 }
  41         }
  42
  43         public abstract class ALinqExpression : Expression
  44         {
  45                 // Dictionary of method name -> MethodGroupExpr
  46                 static Hashtable methods = new Hashtable ();
  47                 static Type enumerable_class;
  48
  49                 protected abstract string MethodName { get; }
  50
  51                 protected MethodGroupExpr MethodGroup {
  52                         get {
  53                                 //
  54                                 // Even if C# spec indicates that LINQ methods are context specific
  55                                 // in reality they are hardcoded
  56                                 //
  57                                 MemberList ml = (MemberList)methods [MethodName];
  58                                 if (ml == null) {
  59                                         if (enumerable_class == null)
  60                                                 enumerable_class = TypeManager.CoreLookupType ("System.Linq", "Enumerable");
  61
  62                                         ml = TypeManager.FindMembers (enumerable_class,
  63                                                 MemberTypes.Method, BindingFlags.Static | BindingFlags.Public,
  64                                                 Type.FilterName, MethodName);
  65                                 }
  66
  67                                 return new MethodGroupExpr (ArrayList.Adapter (ml), enumerable_class, loc);
  68                         }
  69                 }
  70         }
  71
  72         public abstract class AQueryClause : ALinqExpression
  73         {
  74                 public AQueryClause next;
  75                 /*protected*/ public Expression expr;
  76
  77                 protected AQueryClause (Expression expr, Location loc)
  78                 {
  79                         this.expr = expr;
  80                         this.loc = loc;
  81                 }
  82
  83                 public override Expression DoResolve (EmitContext ec)
  84                 {
  85                         return expr.DoResolve (ec);
  86                 }
  87
  88                 public override void Emit (EmitContext ec)
  89                 {
  90                         throw new NotSupportedException ();
  91                 }
  92
  93                 public virtual Expression BuildQueryClause (EmitContext ec, Expression from, Parameter parameter, TransparentIdentifiersScope ti)
  94                 {
  95                         ArrayList args = new ArrayList (2);
  96                         args.Add (new Argument (from));
  97                         args.Add (new Argument (CreateSelector (ec, expr, parameter, ti)));
  98                         expr = new Invocation (MethodGroup, args);
  99                         if (next != null)
 100                                 return next.BuildQueryClause (ec, this, parameter, ti);
 101
 102                         return expr;
 103                 }
 104
 105                 protected LambdaExpression CreateSelector (EmitContext ec, Expression expr, Parameter parameter, TransparentIdentifiersScope ti)
 106                 {
 107                         return CreateSelector (ec, expr, new Parameter [] { parameter }, ti);
 108                 }
 109
 110                 protected LambdaExpression CreateSelector (EmitContext ec, Expression expr, Parameter[] parameters, TransparentIdentifiersScope ti)
 111                 {
 112                         Parameters p = new Parameters (parameters);
 113
 114                         LambdaExpression selector = new LambdaExpression (
 115                                 null, null, (TypeContainer) ec.DeclContainer, p, ec.CurrentBlock, loc);
 116                         selector.Block = new SelectorBlock (ec.CurrentBlock, p, ti, loc);
 117                         selector.Block.AddStatement (new Return (expr, loc));
 118
 119                         selector.CreateAnonymousHelpers ();
 120                         selector.RootScope.DefineType ();
 121
 122                         return selector;
 123                 }
 124
 125                 public virtual AQueryClause Next {
 126                         set {
 127                                 next = value;
 128                         }
 129                 }
 130
 131                 public AQueryClause Tail {
 132                         get {
 133                                 return next == null ? this : next.Tail;
 134                         }
 135                 }
 136         }
 137
 138         //
 139         // A query clause with an identifier (range variable)
 140         //
 141         public abstract class ARangeVariableQueryClause : AQueryClause
 142         {
 143                 public readonly Block block;
 144                 protected Expression element_selector;
 145
 146                 protected ARangeVariableQueryClause (Block block, Expression expr, Location loc)
 147                         : base (expr, loc)
 148                 {
 149                         this.block = block;
 150                 }
 151
 152                 protected virtual void AddSelectorArguments (EmitContext ec, ArrayList args, Parameter parentParameter,
 153                         Parameter parameter, TransparentIdentifiersScope ti)
 154                 {
 155                         args.Add (new Argument (CreateSelector (ec, expr, parentParameter, null)));
 156                         args.Add (new Argument (CreateSelector (ec, element_selector,
 157                                 new Parameter [] { parentParameter, parameter }, ti)));
 158                 }
 159
 160                 //
 161                 // Customization for range variables which not only creates a lambda expression but
 162                 // also builds a chain of range varible pairs
 163                 //
 164                 public override Expression BuildQueryClause (EmitContext ec, Expression from, Parameter parentParameter, TransparentIdentifiersScope ti)
 165                 {
 166                         ICollection values = block.Variables.Values;
 167                         if (values.Count != 1)
 168                                 throw new NotImplementedException ("Count != 1");
 169
 170                         IEnumerator enumerator = values.GetEnumerator ();
 171                         enumerator.MoveNext ();
 172                         LocalInfo li = (LocalInfo) enumerator.Current;
 173
 174                         Parameter parameter;
 175                         if (li.Type == ImplicitQueryParameter.ImplicitType.Instance) {
 176                                 parameter = new ImplicitQueryParameter (li);
 177                         } else {
 178                                 parameter = new Parameter (li.Type, li.Name, Parameter.Modifier.NONE, null, li.Location);
 179                         }
 180
 181                         if (parentParameter == null)
 182                                 return next.BuildQueryClause (ec, expr, parameter, ti);
 183
 184                         if (next != null) {
 185                                 //
 186                                 // Builds transparent identifiers, each identifier includes its parent
 187                                 // type at index 0, and new value at index 1. This is not valid for the
 188                                 // first one which includes two values directly.
 189                                 //
 190                                 ArrayList transp_args = new ArrayList (2);
 191                                 transp_args.Add (new AnonymousTypeParameter (parentParameter));
 192                                 transp_args.Add (CreateAnonymousTypeVariable (parameter));
 193                                 element_selector = new AnonymousTypeDeclaration (transp_args, (TypeContainer) ec.DeclContainer, loc);
 194                         }
 195
 196                         ArrayList args = new ArrayList (3);
 197                         args.Add (new Argument (from));
 198                         AddSelectorArguments (ec, args, parentParameter, parameter, ti);
 199
 200                         expr = new Invocation (MethodGroup, args);
 201                         if (next != null) {
 202                                 //
 203                                 // Parameter indentifiers goes to the scope
 204                                 //
 205                                 string[] identifiers;
 206                                 if (ti == null) {
 207                                         identifiers = new string [] { parentParameter.Name, parameter.Name };
 208                                 } else {
 209                                         identifiers = new string [] { parameter.Name };
 210                                 }
 211
 212                                 TransparentParameter tp = new TransparentParameter (loc);
 213                                 return next.BuildQueryClause (ec, this, tp,
 214                                         new TransparentIdentifiersScope (ti, tp, identifiers));
 215                         }
 216
 217                         return expr;
 218                 }
 219
 220                 //
 221                 // For transparent identifiers, creates an instance of variable expression
 222                 //
 223                 protected virtual AnonymousTypeParameter CreateAnonymousTypeVariable (Parameter parameter)
 224                 {
 225                         return new AnonymousTypeParameter (parameter);
 226                 }
 227         }
 228
 229         public class Cast : ALinqExpression
 230         {
 231                 Expression expr;
 232                 readonly Expression cast_type;
 233
 234                 public Cast (Expression type, Expression expr, Location loc)
 235                 {
 236                         this.cast_type = type;
 237                         this.expr = expr;
 238                         this.loc = loc;
 239                 }
 240
 241                 protected override void CloneTo (CloneContext clonectx, Expression target)
 242                 {
 243                         // We don't have to clone cast type
 244                         Cast t = (Cast) target;
 245                         t.expr = expr.Clone (clonectx);
 246                 }
 247
 248                 protected override string MethodName {
 249                         get { return "Cast"; }
 250                 }
 251
 252                 public override Expression DoResolve (EmitContext ec)
 253                 {
 254                         TypeArguments type_arguments = new TypeArguments (loc, cast_type);
 255                         Expression cast = MethodGroup.ResolveGeneric (ec, type_arguments);
 256
 257                         ArrayList args = new ArrayList (1);
 258                         args.Add (new Argument (expr));
 259                         return new Invocation (cast, args).DoResolve (ec);
 260                 }
 261
 262                 public override void Emit (EmitContext ec)
 263                 {
 264                         throw new NotSupportedException ();
 265                 }
 266         }
 267
 268         public class GroupBy : AQueryClause
 269         {
 270                 readonly Expression element_selector;
 271
 272                 public GroupBy (Expression elementSelector, Expression keySelector, Location loc)
 273                         : base (keySelector, loc)
 274                 {
 275                         this.element_selector = elementSelector;
 276                 }
 277
 278                 public override Expression BuildQueryClause (EmitContext ec, Expression from, Parameter parameter, TransparentIdentifiersScope ti)
 279                 {
 280                         ArrayList args = new ArrayList (3);
 281                         args.Add (new Argument (from));
 282                         args.Add (new Argument (CreateSelector (ec, expr, parameter, ti)));
 283
 284                         // A query can be optimized when selector is not group by specific
 285                         if (!element_selector.Equals (from))
 286                                 args.Add (new Argument (CreateSelector (ec, element_selector, parameter, ti)));
 287
 288                         expr = new Invocation (MethodGroup, args);
 289                         if (next != null)
 290                                 return next.BuildQueryClause (ec, this, parameter, ti);
 291
 292                         return expr;
 293                 }
 294
 295                 protected override string MethodName {
 296                         get { return "GroupBy"; }
 297                 }
 298         }
 299
 300         public class Let : ARangeVariableQueryClause
 301         {
 302                 class RangeAnonymousTypeParameter : AnonymousTypeParameter
 303                 {
 304                         readonly Parameter parameter;
 305
 306                         public RangeAnonymousTypeParameter (Expression initializer, Parameter parameter)
 307                                 : base (initializer, parameter.Name, parameter.Location)
 308                         {
 309                                 this.parameter = parameter;
 310                         }
 311
 312                         public override Expression DoResolve (EmitContext ec)
 313                         {
 314                                 Expression e = base.DoResolve (ec);
 315                                 if (e != null) {
 316                                         //
 317                                         // Spread resolved initializer type
 318                                         //
 319                                         parameter.ParameterType = type;
 320                                         parameter.Resolve (ec);
 321                                 }
 322
 323                                 return e;
 324                         }
 325                 }
 326
 327                 public Let (Block block, Expression expr)
 328                         : base (block, expr, expr.Location)
 329                 {
 330                 }
 331
 332                 protected override void AddSelectorArguments (EmitContext ec, ArrayList args, Parameter parentParameter, Parameter parameter,
 333                         TransparentIdentifiersScope ti)
 334                 {
 335                         args.Add (new Argument (CreateSelector (ec, element_selector, parentParameter, ti)));
 336                 }
 337
 338                 protected override AnonymousTypeParameter CreateAnonymousTypeVariable (Parameter parameter)
 339                 {
 340                         return new RangeAnonymousTypeParameter (expr, parameter);
 341                 }
 342
 343                 protected override string MethodName {
 344                         get { return "Select"; }
 345                 }
 346         }
 347
 348         public class Select : AQueryClause
 349         {
 350                 public Select (Expression expr, Location loc)
 351                         : base (expr, loc)
 352                 {
 353                 }
 354
 355                 protected override string MethodName {
 356                         get { return "Select"; }
 357                 }
 358         }
 359
 360         public class SelectMany : ARangeVariableQueryClause
 361         {
 362                 public SelectMany (Block block, Expression expr)
 363                         : base (block, expr, expr.Location)
 364                 {
 365                 }
 366
 367                 protected override string MethodName {
 368                         get { return "SelectMany"; }
 369                 }
 370
 371                 public override AQueryClause Next {
 372                         set {
 373                                 element_selector = value.expr;
 374
 375                                 // Can be optimized as SelectMany element selector
 376                                 if (value is Select)
 377                                         return;
 378
 379                                 next = value;
 380                         }
 381                 }
 382         }
 383
 384         public class Where : AQueryClause
 385         {
 386                 public Where (Expression expr, Location loc)
 387                         : base (expr, loc)
 388                 {
 389                 }
 390
 391                 protected override string MethodName {
 392                         get { return "Where"; }
 393                 }
 394         }
 395
 396         public class OrderByAscending : AQueryClause
 397         {
 398                 public OrderByAscending (Expression expr)
 399                         : base (expr, expr.Location)
 400                 {
 401                 }
 402
 403                 protected override string MethodName {
 404                         get { return "OrderBy"; }
 405                 }
 406         }
 407
 408         public class OrderByDescending : AQueryClause
 409         {
 410                 public OrderByDescending (Expression expr)
 411                         : base (expr, expr.Location)
 412                 {
 413                 }
 414
 415                 protected override string MethodName {
 416                         get { return "OrderByDescending"; }
 417                 }
 418         }
 419
 420         public class ThenByAscending : OrderByAscending
 421         {
 422                 public ThenByAscending (Expression expr)
 423                         : base (expr)
 424                 {
 425                 }
 426
 427                 protected override string MethodName {
 428                         get { return "ThenBy"; }
 429                 }
 430         }
 431
 432         public class ThenByDescending : OrderByDescending
 433         {
 434                 public ThenByDescending (Expression expr)
 435                         : base (expr)
 436                 {
 437                 }
 438
 439                 protected override string MethodName {
 440                         get { return "ThenByDescending"; }
 441                 }
 442         }
 443
 444         class ImplicitQueryParameter : ImplicitLambdaParameter
 445         {
 446                 public sealed class ImplicitType : Expression
 447                 {
 448                         public static ImplicitType Instance = new ImplicitType ();
 449
 450                         private ImplicitType ()
 451                         {
 452                         }
 453
 454                         protected override void CloneTo (CloneContext clonectx, Expression target)
 455                         {
 456                                 // Nothing to clone
 457                         }
 458
 459                         public override Expression DoResolve (EmitContext ec)
 460                         {
 461                                 throw new NotSupportedException ();
 462                         }
 463
 464                         public override void Emit (EmitContext ec)
 465                         {
 466                                 throw new NotSupportedException ();
 467                         }
 468                 }
 469
 470                 readonly LocalInfo variable;
 471
 472                 public ImplicitQueryParameter (LocalInfo variable)
 473                         : base (variable.Name, variable.Location)
 474                 {
 475                         this.variable = variable;
 476                 }
 477
 478                 public override bool Resolve (IResolveContext ec)
 479                 {
 480                         if (!base.Resolve (ec))
 481                                 return false;
 482
 483                         variable.VariableType = parameter_type;
 484                         return true;
 485                 }
 486         }
 487
 488         //
 489         // Transparent parameters are used to package up the intermediate results
 490         // and pass them onto next clause
 491         //
 492         public class TransparentParameter : ImplicitLambdaParameter
 493         {
 494                 static int counter;
 495                 const string ParameterNamePrefix = "<>__TranspIdent";
 496
 497                 public TransparentParameter (Location loc)
 498                         : base (ParameterNamePrefix + counter++, loc)
 499                 {
 500                 }
 501         }
 502
 503         //
 504         // Transparent identifiers are stored in nested anonymous types, each type can contain
 505         // up to 2 identifiers or 1 identifier and parent type.
 506         //
 507         public class TransparentIdentifiersScope
 508         {
 509                 readonly string [] identifiers;
 510                 readonly TransparentIdentifiersScope parent;
 511                 readonly TransparentParameter parameter;
 512
 513                 public TransparentIdentifiersScope (TransparentIdentifiersScope parent,
 514                         TransparentParameter parameter, string [] identifiers)
 515                 {
 516                         this.parent = parent;
 517                         this.parameter = parameter;
 518                         this.identifiers = identifiers;
 519                 }
 520
 521                 public MemberAccess GetIdentifier (string name)
 522                 {
 523                         TransparentIdentifiersScope ident = FindIdentifier (name);
 524                         if (ident == null)
 525                                 return null;
 526
 527                         return new MemberAccess (CreateIndentifierNestingExpression (ident), name);
 528                 }
 529
 530                 TransparentIdentifiersScope FindIdentifier (string name)
 531                 {
 532                         foreach (string s in identifiers) {
 533                                 if (s == name)
 534                                         return this;
 535                         }
 536
 537                         if (parent == null)
 538                                 return null;
 539
 540                         return parent.FindIdentifier (name);
 541                 }
 542
 543                 Expression CreateIndentifierNestingExpression (TransparentIdentifiersScope end)
 544                 {
 545                         Expression expr = new SimpleName (parameter.Name, parameter.Location);
 546                         TransparentIdentifiersScope current = this;
 547                         while (current != end)
 548                         {
 549                                 current = current.parent;
 550                                 expr = new MemberAccess (expr, current.parameter.Name);
 551                         }
 552
 553                         return expr;
 554                 }
 555         }
 556
 557         //
 558         // Lambda expression block which contains transparent identifiers
 559         //
 560         class SelectorBlock : ToplevelBlock
 561         {
 562                 readonly TransparentIdentifiersScope transparent_identifiers;
 563
 564                 public SelectorBlock (Block block, Parameters parameters,
 565                         TransparentIdentifiersScope transparentIdentifiers, Location loc)
 566                         : base (block, parameters, loc)
 567                 {
 568                         this.transparent_identifiers = transparentIdentifiers;
 569                 }
 570
 571                 public override Expression GetTransparentIdentifier (string name)
 572                 {
 573                         if (transparent_identifiers == null)
 574                                 return null;
 575
 576                         return transparent_identifiers.GetIdentifier (name);
 577                 }
 578         }
 579 }