mcs/class/System.Core/System.Linq.jvm/ExpressionInterpreter.cs

   1 //
   2 // ExpressionInterpreter.cs
   3 //
   4 // (C) 2008 Mainsoft, Inc. (http://www.mainsoft.com)
   5 // (C) 2008 db4objects, Inc. (http://www.db4o.com)
   6 // (C) 2010 Novell, Inc. (http://www.novell.com)
   7 //
   8 // Permission is hereby granted, free of charge, to any person obtaining
   9 // a copy of this software and associated documentation files (the
  10 // "Software"), to deal in the Software without restriction, including
  11 // without limitation the rights to use, copy, modify, merge, publish,
  12 // distribute, sublicense, and/or sell copies of the Software, and to
  13 // permit persons to whom the Software is furnished to do so, subject to
  14 // the following conditions:
  15 //
  16 // The above copyright notice and this permission notice shall be
  17 // included in all copies or substantial portions of the Software.
  18 //
  19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  20 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  21 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  22 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  23 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  24 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  25 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  26 //
  27
  28 using System.Collections.Generic;
  29 using System.Collections.ObjectModel;
  30 using System.Linq.Expressions;
  31 using System.Reflection;
  32
  33 namespace System.Linq.jvm {
  34
  35         struct LambdaInfo {
  36                 public readonly LambdaExpression Lambda;
  37                 public readonly object [] Arguments;
  38
  39                 public LambdaInfo (LambdaExpression lambda, object [] arguments)
  40                 {
  41                         this.Lambda = lambda;
  42                         this.Arguments = arguments;
  43                 }
  44         }
  45
  46         class HoistedVariableDetector : ExpressionVisitor {
  47
  48                 readonly Dictionary<ParameterExpression, LambdaExpression> parameter_to_lambda =
  49                         new Dictionary<ParameterExpression, LambdaExpression> ();
  50
  51                 Dictionary<LambdaExpression, List<ParameterExpression>> hoisted_map;
  52
  53                 LambdaExpression lambda;
  54
  55                 public Dictionary<LambdaExpression, List<ParameterExpression>> Process (LambdaExpression lambda)
  56                 {
  57                         Visit (lambda);
  58                         return hoisted_map;
  59                 }
  60
  61                 protected override void VisitLambda (LambdaExpression lambda)
  62                 {
  63                         this.lambda = lambda;
  64                         foreach (var parameter in lambda.Parameters)
  65                                 parameter_to_lambda [parameter] = lambda;
  66                         base.VisitLambda (lambda);
  67                 }
  68
  69                 protected override void VisitParameter (ParameterExpression parameter)
  70                 {
  71                         if (lambda.Parameters.Contains (parameter))
  72                                 return;
  73
  74                         Hoist (parameter);
  75                 }
  76
  77                 void Hoist (ParameterExpression parameter)
  78                 {
  79                         LambdaExpression lambda;
  80                         if (!parameter_to_lambda.TryGetValue (parameter, out lambda))
  81                                 return;
  82
  83                         if (hoisted_map == null)
  84                                 hoisted_map = new Dictionary<LambdaExpression, List<ParameterExpression>> ();
  85
  86                         List<ParameterExpression> hoisted;
  87                         if (!hoisted_map.TryGetValue (lambda, out hoisted)) {
  88                                 hoisted = new List<ParameterExpression> ();
  89                                 hoisted_map [lambda] = hoisted;
  90                         }
  91
  92                         hoisted.Add (parameter);
  93                 }
  94         }
  95
  96
  97         class ExpressionInterpreter : ExpressionVisitor {
  98
  99                 readonly Stack<LambdaInfo> lambdas = new Stack<LambdaInfo> ();
 100                 readonly Stack<object> stack = new Stack<object> ();
 101
 102                 readonly Dictionary<LambdaExpression, List<ParameterExpression>> hoisted_map;
 103                 readonly Dictionary<ParameterExpression, object> hoisted_values;
 104
 105                 void Push (object value)
 106                 {
 107                         stack.Push (value);
 108                 }
 109
 110                 object Pop ()
 111                 {
 112                         return stack.Pop ();
 113                 }
 114
 115                 public ExpressionInterpreter (LambdaExpression lambda)
 116                 {
 117                         hoisted_map = new HoistedVariableDetector ().Process (lambda);
 118
 119                         if (hoisted_map != null)
 120                                 hoisted_values = new Dictionary<ParameterExpression, object> ();
 121                 }
 122
 123                 private void VisitCoalesce (BinaryExpression binary)
 124                 {
 125                         Visit (binary.Left);
 126
 127                         var left = Pop ();
 128
 129                         if (left == null) {
 130                                 Visit (binary.Right);
 131                                 return;
 132                         }
 133
 134                         if (binary.Conversion == null) {
 135                                 Push (left);
 136                                 return;
 137                         }
 138
 139                         Push (Invoke (binary.Conversion.Compile (this), new [] { left }));
 140                 }
 141
 142                 void VisitAndAlso (BinaryExpression binary)
 143                 {
 144                         object left = null;
 145                         object right = null;
 146
 147                         Visit (binary.Left);
 148
 149                         left = Pop ();
 150
 151                         if (left == null || ((bool) left)) {
 152                                 Visit (binary.Right);
 153                                 right = Pop ();
 154                         }
 155
 156                         Push (Math.And (left, right));
 157                 }
 158
 159                 void VisitUserDefinedAndAlso (BinaryExpression binary)
 160                 {
 161                         object left = null;
 162                         object right = null;
 163
 164                         Visit (binary.Left);
 165
 166                         left = Pop ();
 167
 168                         if (InvokeFalseOperator (binary, left)) {
 169                                 Push (left);
 170                                 return;
 171                         }
 172
 173                         Visit (binary.Right);
 174                         right = Pop ();
 175
 176                         if (binary.IsLiftedToNull && right == null) {
 177                                 Push (null);
 178                                 return;
 179                         }
 180
 181                         Push (InvokeMethod (binary.Method, null, new [] { left, right }));
 182                 }
 183
 184                 static bool InvokeTrueOperator (BinaryExpression binary, object target)
 185                 {
 186                         return (bool) InvokeMethod (GetTrueOperator (binary), null, new [] { target });
 187                 }
 188
 189                 static bool InvokeFalseOperator (BinaryExpression binary, object target)
 190                 {
 191                         return (bool) InvokeMethod (GetFalseOperator (binary), null, new [] { target });
 192                 }
 193
 194                 static MethodInfo GetFalseOperator (BinaryExpression binary)
 195                 {
 196                         return Expression.GetFalseOperator (binary.Left.Type.GetNotNullableType ());
 197                 }
 198
 199                 static MethodInfo GetTrueOperator (BinaryExpression binary)
 200                 {
 201                         return Expression.GetTrueOperator (binary.Left.Type.GetNotNullableType ());
 202                 }
 203
 204                 void VisitOrElse (BinaryExpression binary)
 205                 {
 206                         object left = null;
 207                         object right = null;
 208
 209                         Visit (binary.Left);
 210                         left = Pop ();
 211
 212                         if (left == null || !((bool) left)) {
 213                                 Visit (binary.Right);
 214                                 right = Pop ();
 215                         }
 216
 217                         Push (Math.Or (left, right));
 218                 }
 219
 220                 void VisitUserDefinedOrElse (BinaryExpression binary)
 221                 {
 222                         object left = null;
 223                         object right = null;
 224
 225                         Visit (binary.Left);
 226                         left = Pop ();
 227
 228                         if (InvokeTrueOperator (binary, left)) {
 229                                 Push (left);
 230                                 return;
 231                         }
 232
 233                         Visit (binary.Right);
 234                         right = Pop ();
 235
 236                         if (binary.IsLiftedToNull && right == null) {
 237                                 Push (null);
 238                                 return;
 239                         }
 240
 241                         Push (InvokeMethod (binary.Method, null, new [] { left, right }));
 242                 }
 243
 244                 void VisitLogicalBinary (BinaryExpression binary)
 245                 {
 246                         Visit (binary.Left);
 247                         Visit (binary.Right);
 248
 249                         var right = Pop ();
 250                         var left = Pop ();
 251
 252                         Push (Math.Evaluate (left, right, binary.Type, binary.NodeType));
 253                 }
 254
 255                 void VisitArithmeticBinary (BinaryExpression binary)
 256                 {
 257                         Visit (binary.Left);
 258                         Visit (binary.Right);
 259
 260                         if (IsNullBinaryLifting (binary))
 261                                 return;
 262
 263                         var right = Pop ();
 264                         var left = Pop ();
 265
 266                         switch (binary.NodeType) {
 267                         case ExpressionType.RightShift:
 268                                 Push (Math.RightShift (left, Convert.ToInt32 (right), Type.GetTypeCode (binary.Type.GetNotNullableType ())));
 269                                 return;
 270                         case ExpressionType.LeftShift:
 271                                 Push (Math.LeftShift (left, Convert.ToInt32 (right), Type.GetTypeCode (binary.Type.GetNotNullableType ())));
 272                                 return;
 273                         default:
 274                                 Push (Math.Evaluate (left, right, binary.Type, binary.NodeType));
 275                                 break;
 276                         }
 277                 }
 278
 279                 bool IsNullRelationalBinaryLifting (BinaryExpression binary)
 280                 {
 281                         var right = Pop ();
 282                         var left = Pop ();
 283
 284                         if (binary.IsLifted && (left == null || right == null)) {
 285                                 if (binary.IsLiftedToNull) {
 286                                         Push (null);
 287                                         return true;
 288                                 }
 289
 290                                 switch (binary.NodeType) {
 291                                 case ExpressionType.Equal:
 292                                         Push (BinaryEqual (binary, left, right));
 293                                         break;
 294                                 case ExpressionType.NotEqual:
 295                                         Push (BinaryNotEqual (binary, left, right));
 296                                         break;
 297                                 default:
 298                                         Push (false);
 299                                         break;
 300                                 }
 301
 302                                 return true;
 303                         }
 304
 305                         Push (left);
 306                         Push (right);
 307
 308                         return false;
 309                 }
 310
 311                 void VisitRelationalBinary (BinaryExpression binary)
 312                 {
 313                         Visit (binary.Left);
 314                         Visit (binary.Right);
 315
 316                         if (IsNullRelationalBinaryLifting (binary))
 317                                 return;
 318
 319                         var right = Pop ();
 320                         var left = Pop ();
 321
 322                         switch (binary.NodeType) {
 323                         case ExpressionType.Equal:
 324                                 Push (BinaryEqual (binary, left, right));
 325                                 return;
 326                         case ExpressionType.NotEqual:
 327                                 Push (BinaryNotEqual (binary, left, right));
 328                                 return;
 329                         case ExpressionType.LessThan:
 330                                 Push (Comparer<object>.Default.Compare (left, right) < 0);
 331                                 return;
 332                         case ExpressionType.LessThanOrEqual:
 333                                 Push (Comparer<object>.Default.Compare (left, right) <= 0);
 334                                 return;
 335                         case ExpressionType.GreaterThan:
 336                                 Push (Comparer<object>.Default.Compare (left, right) > 0);
 337                                 return;
 338                         case ExpressionType.GreaterThanOrEqual:
 339                                 Push (Comparer<object>.Default.Compare (left, right) >= 0);
 340                                 return;
 341                         }
 342                 }
 343
 344                 void VisitLogicalShortCircuitBinary (BinaryExpression binary)
 345                 {
 346                         switch (binary.NodeType) {
 347                         case ExpressionType.AndAlso:
 348                                 VisitAndAlso (binary);
 349                                 return;
 350                         case ExpressionType.OrElse:
 351                                 VisitOrElse (binary);
 352                                 return;
 353                         }
 354                 }
 355
 356                 void VisitArrayIndex (BinaryExpression binary)
 357                 {
 358                         Visit (binary.Left);
 359                         var left = Pop ();
 360                         Visit (binary.Right);
 361                         var right = Pop ();
 362
 363                         Push (((Array) left).GetValue ((int) right));
 364                 }
 365
 366                 bool IsNullBinaryLifting (BinaryExpression binary)
 367                 {
 368                         var right = Pop ();
 369                         var left = Pop ();
 370
 371                         if (binary.IsLifted && (right == null || left == null)) {
 372                                 if (binary.IsLiftedToNull)
 373                                         Push (null);
 374                                 else
 375                                         Push (GetDefaultValue (binary.Type));
 376
 377                                 return true;
 378                         }
 379
 380                         Push (left);
 381                         Push (right);
 382
 383                         return false;
 384                 }
 385
 386                 static object GetDefaultValue (Type type)
 387                 {
 388                         var array = (Array) Array.CreateInstance (type, 1);
 389                         return array.GetValue (0);
 390                 }
 391
 392                 void VisitUserDefinedBinary (BinaryExpression binary)
 393                 {
 394                         switch (binary.NodeType) {
 395                         case ExpressionType.AndAlso:
 396                         case ExpressionType.OrElse:
 397                                 VisitUserDefinedLogicalShortCircuitBinary (binary);
 398                                 return;
 399                         case ExpressionType.Equal:
 400                         case ExpressionType.NotEqual:
 401                                 VisitUserDefinedRelationalBinary (binary);
 402                                 return;
 403                         default:
 404                                 VisitUserDefinedCommonBinary (binary);
 405                                 return;
 406                         }
 407                 }
 408
 409                 void VisitUserDefinedLogicalShortCircuitBinary (BinaryExpression binary)
 410                 {
 411                         switch (binary.NodeType) {
 412                         case ExpressionType.AndAlso:
 413                                 VisitUserDefinedAndAlso (binary);
 414                                 return;
 415                         case ExpressionType.OrElse:
 416                                 VisitUserDefinedOrElse (binary);
 417                                 return;
 418                         }
 419                 }
 420
 421                 void VisitUserDefinedRelationalBinary (BinaryExpression binary)
 422                 {
 423                         Visit (binary.Left);
 424                         Visit (binary.Right);
 425
 426                         if (IsNullRelationalBinaryLifting (binary))
 427                                 return;
 428
 429                         var right = Pop ();
 430                         var left = Pop ();
 431
 432                         Push (InvokeBinary (binary, left, right));
 433                 }
 434
 435                 void VisitUserDefinedCommonBinary (BinaryExpression binary)
 436                 {
 437                         Visit (binary.Left);
 438                         Visit (binary.Right);
 439
 440                         if (IsNullBinaryLifting (binary))
 441                                 return;
 442
 443                         var right = Pop ();
 444                         var left = Pop ();
 445
 446                         Push (InvokeBinary (binary, left, right));
 447                 }
 448
 449                 object InvokeBinary (BinaryExpression binary, object left, object right)
 450                 {
 451                         return InvokeMethod (binary.Method, null, new [] { left, right });
 452                 }
 453
 454                 bool BinaryEqual (BinaryExpression binary, object left, object right)
 455                 {
 456                         if (typeof (ValueType).IsAssignableFrom (binary.Right.Type))
 457                                 return ValueType.Equals (left, right);
 458                         else
 459                                 return left == right;
 460                 }
 461
 462                 bool BinaryNotEqual (BinaryExpression binary, object left, object right)
 463                 {
 464                         if (typeof (ValueType).IsAssignableFrom (binary.Right.Type))
 465                                 return !ValueType.Equals (left, right);
 466                         else
 467                                 return left != right;
 468                 }
 469
 470                 protected override void VisitBinary (BinaryExpression binary)
 471                 {
 472                         if (binary.Method != null) {
 473                                 VisitUserDefinedBinary (binary);
 474                                 return;
 475                         }
 476
 477                         switch (binary.NodeType) {
 478                         case ExpressionType.ArrayIndex:
 479                                 VisitArrayIndex (binary);
 480                                 return;
 481                         case ExpressionType.Coalesce:
 482                                 VisitCoalesce (binary);
 483                                 return;
 484                         case ExpressionType.AndAlso:
 485                         case ExpressionType.OrElse:
 486                                 VisitLogicalShortCircuitBinary (binary);
 487                                 return;
 488                         case ExpressionType.Equal:
 489                         case ExpressionType.NotEqual:
 490                         case ExpressionType.GreaterThan:
 491                         case ExpressionType.GreaterThanOrEqual:
 492                         case ExpressionType.LessThan:
 493                         case ExpressionType.LessThanOrEqual:
 494                                 VisitRelationalBinary (binary);
 495                                 return;
 496                         case ExpressionType.And:
 497                         case ExpressionType.Or:
 498                                 VisitLogicalBinary (binary);
 499                                 return;
 500                         case ExpressionType.Power:
 501                         case ExpressionType.Add:
 502                         case ExpressionType.AddChecked:
 503                         case ExpressionType.Divide:
 504                         case ExpressionType.ExclusiveOr:
 505                         case ExpressionType.LeftShift:
 506                         case ExpressionType.Modulo:
 507                         case ExpressionType.Multiply:
 508                         case ExpressionType.MultiplyChecked:
 509                         case ExpressionType.RightShift:
 510                         case ExpressionType.Subtract:
 511                         case ExpressionType.SubtractChecked:
 512                                 VisitArithmeticBinary (binary);
 513                                 return;
 514                         }
 515                 }
 516
 517                 void VisitTypeAs (UnaryExpression unary)
 518                 {
 519                         Visit (unary.Operand);
 520
 521                         var value = Pop ();
 522                         if (value == null || !Math.IsType (unary.Type, value))
 523                                 Push (null);
 524                         else
 525                                 Push (value);
 526                 }
 527
 528                 void VisitArrayLength (UnaryExpression unary)
 529                 {
 530                         Visit (unary.Operand);
 531
 532                         var array = (Array) Pop ();
 533                         Push (array.Length);
 534                 }
 535
 536                 void VisitConvert (UnaryExpression unary)
 537                 {
 538                         if (unary.NodeType == ExpressionType.ConvertChecked)
 539                                 VisitConvertChecked (unary);
 540                         else
 541                                 VisitConvertUnchecked (unary);
 542                 }
 543
 544                 void VisitConvertChecked (UnaryExpression unary)
 545                 {
 546                         VisitConvert (unary, Math.ConvertToTypeChecked);
 547                 }
 548
 549                 void VisitConvertUnchecked (UnaryExpression unary)
 550                 {
 551                         VisitConvert (unary, Math.ConvertToTypeUnchecked);
 552                 }
 553
 554                 void VisitConvert (UnaryExpression unary, Func<object, Type, Type, object> converter)
 555                 {
 556                         Visit (unary.Operand);
 557                         Push (converter (Pop (), unary.Operand.Type, unary.Type));
 558                 }
 559
 560                 bool IsNullUnaryLifting (UnaryExpression unary)
 561                 {
 562                         var value = Pop ();
 563
 564                         if (unary.IsLifted && value == null) {
 565                                 if (unary.IsLiftedToNull) {
 566                                         Push (null);
 567                                         return true;
 568                                 } else {
 569                                         throw new InvalidOperationException ();
 570                                 }
 571                         }
 572
 573                         Push (value);
 574                         return false;
 575                 }
 576
 577                 void VisitQuote (UnaryExpression unary)
 578                 {
 579                         Push (unary.Operand);
 580                 }
 581
 582                 void VisitUserDefinedUnary (UnaryExpression unary)
 583                 {
 584                         Visit (unary.Operand);
 585
 586                         if (IsNullUnaryLifting (unary))
 587                                 return;
 588
 589                         var value = Pop ();
 590
 591                         Push (InvokeUnary (unary, value));
 592                 }
 593
 594                 object InvokeUnary (UnaryExpression unary, object value)
 595                 {
 596                         return InvokeMethod (unary.Method, null, new [] { value });
 597                 }
 598
 599                 void VisitArithmeticUnary (UnaryExpression unary)
 600                 {
 601                         Visit (unary.Operand);
 602
 603                         if (IsNullUnaryLifting (unary))
 604                                 return;
 605
 606                         var value = Pop ();
 607
 608                         switch (unary.NodeType) {
 609                         case ExpressionType.Not:
 610                                 if (unary.Type.GetNotNullableType () == typeof (bool))
 611                                         Push (!Convert.ToBoolean (value));
 612                                 else
 613                                         Push (~Convert.ToInt32 (value));
 614                                 return;
 615                         case ExpressionType.Negate:
 616                                 Push (Math.Negate (value, Type.GetTypeCode (unary.Type.GetNotNullableType ())));
 617                                 return;
 618                         case ExpressionType.NegateChecked:
 619                                 Push (Math.NegateChecked (value, Type.GetTypeCode (unary.Type.GetNotNullableType ())));
 620                                 return;
 621                         case ExpressionType.UnaryPlus:
 622                                 Push (value);
 623                                 return;
 624                         }
 625                 }
 626
 627                 protected override void VisitUnary (UnaryExpression unary)
 628                 {
 629                         if (unary.Method != null) {
 630                                 VisitUserDefinedUnary (unary);
 631                                 return;
 632                         }
 633
 634                         switch (unary.NodeType) {
 635                         case ExpressionType.Quote:
 636                                 VisitQuote (unary);
 637                                 return;
 638                         case ExpressionType.TypeAs:
 639                                 VisitTypeAs (unary);
 640                                 return;
 641                         case ExpressionType.ArrayLength:
 642                                 VisitArrayLength (unary);
 643                                 return;
 644                         case ExpressionType.Convert:
 645                         case ExpressionType.ConvertChecked:
 646                                 VisitConvert (unary);
 647                                 return;
 648                         case ExpressionType.Negate:
 649                         case ExpressionType.NegateChecked:
 650                         case ExpressionType.Not:
 651                         case ExpressionType.UnaryPlus:
 652                                 VisitArithmeticUnary (unary);
 653                                 return;
 654                         default:
 655                                 throw new NotImplementedException (unary.NodeType.ToString ());
 656                         }
 657                 }
 658
 659                 protected override void VisitNew (NewExpression nex)
 660                 {
 661                         if (nex.Constructor == null)
 662                                 Push (Activator.CreateInstance (nex.Type));
 663                         else
 664                                 Push (InvokeConstructor (nex.Constructor, VisitListExpressions (nex.Arguments)));
 665                 }
 666
 667                 static object InvokeConstructor (ConstructorInfo constructor, object [] arguments)
 668                 {
 669                         try {
 670                                 return constructor.Invoke (arguments);
 671                         } catch (TargetInvocationException e) {
 672                                 throw e.InnerException;
 673                         }
 674                 }
 675
 676                 protected override void VisitTypeIs (TypeBinaryExpression type)
 677                 {
 678                         Visit (type.Expression);
 679                         Push (Math.IsType (type.TypeOperand, Pop ()));
 680                 }
 681
 682                 void VisitMemberInfo (MemberInfo mi)
 683                 {
 684                         mi.OnFieldOrProperty (
 685                                 field => {
 686                                         object target = null;
 687                                         if (!field.IsStatic)
 688                                                 target = Pop ();
 689
 690                                         Push (field.GetValue (target));
 691                                 },
 692                                 property => {
 693                                         object target = null;
 694                                         var getter = property.GetGetMethod (true);
 695                                         if (!getter.IsStatic)
 696                                                 target = Pop ();
 697
 698                                         Push (property.GetValue (target, null));
 699                                 });
 700                 }
 701
 702                 protected override void VisitMemberAccess (MemberExpression member)
 703                 {
 704                         Visit (member.Expression);
 705                         VisitMemberInfo (member.Member);
 706                 }
 707
 708                 protected override void VisitNewArray (NewArrayExpression newArray)
 709                 {
 710                         switch (newArray.NodeType) {
 711                         case ExpressionType.NewArrayInit:
 712                                 VisitNewArrayInit (newArray);
 713                                 return;
 714                         case ExpressionType.NewArrayBounds:
 715                                 VisitNewArrayBounds (newArray);
 716                                 return;
 717                         }
 718
 719                         throw new NotSupportedException ();
 720                 }
 721
 722                 void VisitNewArrayBounds (NewArrayExpression newArray)
 723                 {
 724                         var lengths = new int [newArray.Expressions.Count];
 725                         for (int i = 0; i < lengths.Length; i++) {
 726                                 Visit (newArray.Expressions [i]);
 727                                 lengths [i] = (int) Pop ();
 728                         }
 729
 730                         Push (Array.CreateInstance (newArray.Type.GetElementType (), lengths));
 731                 }
 732
 733                 void VisitNewArrayInit (NewArrayExpression newArray)
 734                 {
 735                         var array = Array.CreateInstance (
 736                                 newArray.Type.GetElementType (),
 737                                 newArray.Expressions.Count);
 738
 739                         for (int i = 0; i < array.Length; i++) {
 740                                 Visit (newArray.Expressions [i]);
 741                                 array.SetValue (Pop (), i);
 742                         }
 743
 744                         Push (array);
 745                 }
 746
 747                 protected override void VisitConditional (ConditionalExpression conditional)
 748                 {
 749                         Visit (conditional.Test);
 750
 751                         if ((bool) Pop ())
 752                                 Visit (conditional.IfTrue);
 753                         else
 754                                 Visit (conditional.IfFalse);
 755                 }
 756
 757                 protected override void VisitMethodCall (MethodCallExpression call)
 758                 {
 759                         object instance = null;
 760                         if (call.Object != null) {
 761                                 Visit (call.Object);
 762                                 instance = Pop ();
 763                         }
 764
 765                         Push (InvokeMethod (call.Method, instance, VisitListExpressions (call.Arguments)));
 766                 }
 767
 768                 protected override void VisitParameter (ParameterExpression parameter)
 769                 {
 770                         var info = lambdas.Peek ();
 771
 772                         var lambda = info.Lambda;
 773                         var arguments = info.Arguments;
 774
 775                         var index = GetParameterIndex (lambda, parameter);
 776                         if (index >= 0) {
 777                                 Push (arguments [index]);
 778                                 return;
 779                         }
 780
 781                         object value;
 782                         if (hoisted_values.TryGetValue (parameter, out value)) {
 783                                 Push (value);
 784                                 return;
 785                         }
 786
 787                         throw new ArgumentException ();
 788                 }
 789
 790                 protected override void VisitConstant (ConstantExpression constant)
 791                 {
 792                         Push (constant.Value);
 793                 }
 794
 795                 protected override void VisitInvocation (InvocationExpression invocation)
 796                 {
 797                         Visit (invocation.Expression);
 798                         Push (Invoke ((Delegate) Pop (), VisitListExpressions (invocation.Arguments)));
 799                 }
 800
 801                 static object Invoke (Delegate dlg, object [] arguments)
 802                 {
 803                         return InvokeMethod (dlg.Method, dlg.Target, arguments);
 804                 }
 805
 806                 static object InvokeMethod (MethodBase method, object obj, object [] arguments)
 807                 {
 808                         try {
 809                                 return method.Invoke (obj, arguments);
 810                         } catch (TargetInvocationException e) {
 811                                 throw e.InnerException;
 812                         }
 813                 }
 814
 815                 protected override void VisitMemberListBinding (MemberListBinding binding)
 816                 {
 817                         var value = Pop ();
 818                         Push (value);
 819                         VisitMemberInfo (binding.Member);
 820                         VisitElementInitializerList (binding.Initializers);
 821                         Pop (); // pop the member
 822                         Push (value); // push the original target
 823                 }
 824
 825                 protected override void VisitElementInitializer (ElementInit initializer)
 826                 {
 827                         object target = null;
 828                         if (!initializer.AddMethod.IsStatic)
 829                                 target = Pop ();
 830
 831                         var arguments = VisitListExpressions (initializer.Arguments);
 832                         InvokeMethod (initializer.AddMethod, target, arguments);
 833
 834                         if (!initializer.AddMethod.IsStatic)
 835                                 Push (target);
 836                 }
 837
 838                 protected override void VisitMemberMemberBinding (MemberMemberBinding binding)
 839                 {
 840                         var value = Pop ();
 841                         Push (value);
 842                         VisitMemberInfo (binding.Member);
 843                         VisitBindingList (binding.Bindings);
 844                         Pop ();
 845                         Push (value);
 846                 }
 847
 848                 protected override void VisitMemberAssignment (MemberAssignment assignment)
 849                 {
 850                         Visit (assignment.Expression);
 851
 852                         var value = Pop ();
 853
 854                         assignment.Member.OnFieldOrProperty (
 855                                 field => {
 856                                         object target = null;
 857                                         if (!field.IsStatic)
 858                                                 target = Pop ();
 859
 860                                         field.SetValue (target, value);
 861
 862                                         if (!field.IsStatic)
 863                                                 Push (target);
 864                                 },
 865                                 property => {
 866                                         object target = null;
 867                                         var getter = property.GetGetMethod (true);
 868                                         if (!getter.IsStatic)
 869                                                 target = Pop ();
 870
 871                                         property.SetValue (target, value, null);
 872
 873                                         if (!getter.IsStatic)
 874                                                 Push (target);
 875                                 });
 876                 }
 877
 878                 protected override void VisitLambda (LambdaExpression lambda)
 879                 {
 880                         Push (lambda.Compile (this));
 881                 }
 882
 883                 private object [] VisitListExpressions (ReadOnlyCollection<Expression> collection)
 884                 {
 885                         object [] results = new object [collection.Count];
 886                         for (int i = 0; i < results.Length; i++) {
 887                                 Visit (collection [i]);
 888                                 results [i] = Pop ();
 889                         }
 890
 891                         return results;
 892                 }
 893
 894                 void StoreHoistedVariables (LambdaExpression lambda, object [] arguments)
 895                 {
 896                         if (hoisted_map == null)
 897                                 return;
 898
 899                         List<ParameterExpression> variables;
 900                         if (!hoisted_map.TryGetValue (lambda, out variables))
 901                                 return;
 902
 903                         foreach (var variable in variables)
 904                                 StoreHoistedVariable (variable, lambda, arguments);
 905                 }
 906
 907                 void StoreHoistedVariable (ParameterExpression variable, LambdaExpression lambda, object [] arguments)
 908                 {
 909                         var index = GetParameterIndex (lambda, variable);
 910                         if (index < 0)
 911                                 return;
 912
 913                         hoisted_values [variable] = arguments [index];
 914                 }
 915
 916                 static int GetParameterIndex (LambdaExpression lambda, ParameterExpression parameter)
 917                 {
 918                         return lambda.Parameters.IndexOf (parameter);
 919                 }
 920
 921                 public object Interpret (LambdaExpression lambda, object [] arguments)
 922                 {
 923                         lambdas.Push (new LambdaInfo (lambda, arguments));
 924
 925                         StoreHoistedVariables (lambda, arguments);
 926
 927                         Visit (lambda.Body);
 928
 929                         lambdas.Pop ();
 930
 931                         if (lambda.GetReturnType () != typeof (void))
 932                                 return Pop ();
 933
 934                         return null;
 935                 }
 936         }
 937 }