mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Ast/Expression.cs

   1 /* ****************************************************************************
   2  *
   3  * Copyright (c) Microsoft Corporation.
   4  *
   5  * This source code is subject to terms and conditions of the Apache License, Version 2.0. A
   6  * copy of the license can be found in the License.html file at the root of this distribution. If
   7  * you cannot locate the  Apache License, Version 2.0, please send an email to
   8  * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound
   9  * by the terms of the Apache License, Version 2.0.
  10  *
  11  * You must not remove this notice, or any other, from this software.
  12  *
  13  *
  14  * ***************************************************************************/
  15
  16 using System;
  17 using System.Collections.Generic;
  18 using System.Collections.ObjectModel;
  19 using System.Dynamic.Utils;
  20 using System.Globalization;
  21 using System.IO;
  22 using System.Reflection;
  23 using System.Runtime.CompilerServices;
  24 using System.Threading;
  25
  26 #if !FEATURE_CORE_DLR
  27 namespace Microsoft.Scripting.Ast {
  28     using Microsoft.Scripting.Utils;
  29 #else
  30 namespace System.Linq.Expressions {
  31 #endif
  32     /// <summary>
  33     /// The base type for all nodes in Expression Trees.
  34     /// </summary>
  35     [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Maintainability", "CA1506:AvoidExcessiveClassCoupling")]
  36     public abstract partial class Expression {
  37         private delegate LambdaExpression LambdaFactory(Expression body, string name, bool tailCall, ReadOnlyCollection<ParameterExpression> parameters);
  38
  39         private static readonly CacheDict<Type, MethodInfo> _LambdaDelegateCache = new CacheDict<Type, MethodInfo>(40);
  40         private static CacheDict<Type, LambdaFactory> _LambdaFactories;
  41
  42         // LINQ protected ctor from 3.5
  43
  44                 // needs ConditionWeakTable in 4.0
  45
  46         // For 4.0, many frequently used Expression nodes have had their memory
  47         // footprint reduced by removing the Type and NodeType fields. This has
  48         // large performance benefits to all users of Expression Trees.
  49         //
  50         // To support the 3.5 protected constructor, we store the fields that
  51         // used to be here in a ConditionalWeakTable.
  52
  53         private class ExtensionInfo {
  54             public ExtensionInfo(ExpressionType nodeType, Type type) {
  55                 NodeType = nodeType;
  56                 Type = type;
  57             }
  58
  59             internal readonly ExpressionType NodeType;
  60             internal readonly Type Type;
  61         }
  62
  63         private static ConditionalWeakTable<Expression, ExtensionInfo> _legacyCtorSupportTable;
  64
  65         /// <summary>
  66         /// Constructs a new instance of <see cref="Expression"/>.
  67         /// </summary>
  68         /// <param name="nodeType">The <see ctype="ExpressionType"/> of the <see cref="Expression"/>.</param>
  69         /// <param name="type">The <see cref="Type"/> of the <see cref="Expression"/>.</param>
  70         [Obsolete("use a different constructor that does not take ExpressionType. Then override NodeType and Type properties to provide the values that would be specified to this constructor.")]
  71         protected Expression(ExpressionType nodeType, Type type) {
  72             // Can't enforce anything that V1 didn't
  73             if (_legacyCtorSupportTable == null) {
  74                 Interlocked.CompareExchange(
  75                     ref _legacyCtorSupportTable,
  76                     new ConditionalWeakTable<Expression, ExtensionInfo>(),
  77                     null
  78                 );
  79             }
  80
  81             _legacyCtorSupportTable.Add(this, new ExtensionInfo(nodeType, type));
  82         }
  83
  84         /// <summary>
  85         /// Constructs a new instance of <see cref="Expression"/>.
  86         /// </summary>
  87         protected Expression() {
  88         }
  89
  90         /// <summary>
  91         /// The <see cref="ExpressionType"/> of the <see cref="Expression"/>.
  92         /// </summary>
  93         public virtual ExpressionType NodeType {
  94             get {
  95                 ExtensionInfo extInfo;
  96                 if (_legacyCtorSupportTable != null && _legacyCtorSupportTable.TryGetValue(this, out extInfo)) {
  97                     return extInfo.NodeType;
  98                 }
  99
 100                 // the extension expression failed to override NodeType
 101                 throw Error.ExtensionNodeMustOverrideProperty("Expression.NodeType");
 102             }
 103         }
 104
 105
 106         /// <summary>
 107         /// The <see cref="Type"/> of the value represented by this <see cref="Expression"/>.
 108         /// </summary>
 109         [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1721:PropertyNamesShouldNotMatchGetMethods")]
 110         public virtual Type Type {
 111             get {
 112                 ExtensionInfo extInfo;
 113                 if (_legacyCtorSupportTable != null && _legacyCtorSupportTable.TryGetValue(this, out extInfo)) {
 114                     return extInfo.Type;
 115                 }
 116
 117                 // the extension expression failed to override Type
 118                 throw Error.ExtensionNodeMustOverrideProperty("Expression.Type");
 119             }
 120         }
 121
 122         /// <summary>
 123         /// Indicates that the node can be reduced to a simpler node. If this
 124         /// returns true, Reduce() can be called to produce the reduced form.
 125         /// </summary>
 126         public virtual bool CanReduce {
 127             get { return false; }
 128         }
 129
 130         /// <summary>
 131         /// Reduces this node to a simpler expression. If CanReduce returns
 132         /// true, this should return a valid expression. This method is
 133         /// allowed to return another node which itself must be reduced.
 134         /// </summary>
 135         /// <returns>The reduced expression.</returns>
 136         public virtual Expression Reduce() {
 137             if (CanReduce) throw Error.ReducibleMustOverrideReduce();
 138             return this;
 139         }
 140
 141         /// <summary>
 142         /// Reduces the node and then calls the visitor delegate on the reduced expression.
 143         /// Throws an exception if the node isn't reducible.
 144         /// </summary>
 145         /// <param name="visitor">An instance of <see cref="Func{Expression, Expression}"/>.</param>
 146         /// <returns>The expression being visited, or an expression which should replace it in the tree.</returns>
 147         /// <remarks>
 148         /// Override this method to provide logic to walk the node's children.
 149         /// A typical implementation will call visitor.Visit on each of its
 150         /// children, and if any of them change, should return a new copy of
 151         /// itself with the modified children.
 152         /// </remarks>
 153         protected internal virtual Expression VisitChildren(ExpressionVisitor visitor) {
 154             if (!CanReduce) throw Error.MustBeReducible();
 155             return visitor.Visit(ReduceAndCheck());
 156         }
 157
 158         /// <summary>
 159         /// Dispatches to the specific visit method for this node type. For
 160         /// example, <see cref="MethodCallExpression" /> will call into
 161         /// <see cref="ExpressionVisitor.VisitMethodCall" />.
 162         /// </summary>
 163         /// <param name="visitor">The visitor to visit this node with.</param>
 164         /// <returns>The result of visiting this node.</returns>
 165         /// <remarks>
 166         /// This default implementation for <see cref="ExpressionType.Extension" />
 167         /// nodes will call <see cref="ExpressionVisitor.VisitExtension" />.
 168         /// Override this method to call into a more specific method on a derived
 169         /// visitor class of ExprressionVisitor. However, it should still
 170         /// support unknown visitors by calling VisitExtension.
 171         /// </remarks>
 172         protected internal virtual Expression Accept(ExpressionVisitor visitor) {
 173             return visitor.VisitExtension(this);
 174         }
 175
 176         /// <summary>
 177         /// Reduces this node to a simpler expression. If CanReduce returns
 178         /// true, this should return a valid expression. This method is
 179         /// allowed to return another node which itself must be reduced.
 180         /// </summary>
 181         /// <returns>The reduced expression.</returns>
 182         /// <remarks >
 183         /// Unlike Reduce, this method checks that the reduced node satisfies
 184         /// certain invariants.
 185         /// </remarks>
 186         public Expression ReduceAndCheck() {
 187             if (!CanReduce) throw Error.MustBeReducible();
 188
 189             var newNode = Reduce();
 190
 191             // 1. Reduction must return a new, non-null node
 192             // 2. Reduction must return a new node whose result type can be assigned to the type of the original node
 193             if (newNode == null || newNode == this) throw Error.MustReduceToDifferent();
 194             if (!TypeUtils.AreReferenceAssignable(Type, newNode.Type)) throw Error.ReducedNotCompatible();
 195             return newNode;
 196         }
 197
 198         /// <summary>
 199         /// Reduces the expression to a known node type (i.e. not an Extension node)
 200         /// or simply returns the expression if it is already a known type.
 201         /// </summary>
 202         /// <returns>The reduced expression.</returns>
 203         public Expression ReduceExtensions() {
 204             var node = this;
 205             while (node.NodeType == ExpressionType.Extension) {
 206                 node = node.ReduceAndCheck();
 207             }
 208             return node;
 209         }
 210
 211
 212         /// <summary>
 213         /// Creates a <see cref="String"/> representation of the Expression.
 214         /// </summary>
 215         /// <returns>A <see cref="String"/> representation of the Expression.</returns>
 216         public override string ToString() {
 217             return ExpressionStringBuilder.ExpressionToString(this);
 218         }
 219
 220 #if !FEATURE_CORE_DLR
 221         /// <summary>
 222         /// Writes a <see cref="String"/> representation of the <see cref="Expression"/> to a <see cref="TextWriter"/>.
 223         /// </summary>
 224         /// <param name="writer">A <see cref="TextWriter"/> that will be used to build the string representation.</param>
 225         public void DumpExpression(TextWriter writer) {
 226             DebugViewWriter.WriteTo(this, writer);
 227         }
 228
 229         /// <summary>
 230         /// Creates a <see cref="String"/> representation of the Expression.
 231         /// </summary>
 232         /// <returns>A <see cref="String"/> representation of the Expression.</returns>
 233         public string DebugView {
 234 #else
 235         private string DebugView {
 236 #endif
 237             get {
 238                 using (System.IO.StringWriter writer = new System.IO.StringWriter(CultureInfo.CurrentCulture)) {
 239                     DebugViewWriter.WriteTo(this, writer);
 240                     return writer.ToString();
 241                 }
 242             }
 243         }
 244
 245         /// <summary>
 246         /// Helper used for ensuring we only return 1 instance of a ReadOnlyCollection of T.
 247         ///
 248         /// This is called from various methods where we internally hold onto an IList of T
 249         /// or a readonly collection of T.  We check to see if we've already returned a
 250         /// readonly collection of T and if so simply return the other one.  Otherwise we do
 251         /// a thread-safe replacement of the list w/ a readonly collection which wraps it.
 252         ///
 253         /// Ultimately this saves us from having to allocate a ReadOnlyCollection for our
 254         /// data types because the compiler is capable of going directly to the IList of T.
 255         /// </summary>
 256         internal static ReadOnlyCollection<T> ReturnReadOnly<T>(ref IList<T> collection) {
 257             IList<T> value = collection;
 258
 259             // if it's already read-only just return it.
 260             ReadOnlyCollection<T> res = value as ReadOnlyCollection<T>;
 261             if (res != null) {
 262                 return res;
 263             }
 264
 265             // otherwise make sure only readonly collection every gets exposed
 266             Interlocked.CompareExchange<IList<T>>(
 267                 ref collection,
 268                 value.ToReadOnly(),
 269                 value
 270             );
 271
 272             // and return it
 273             return (ReadOnlyCollection<T>)collection;
 274         }
 275
 276         /// <summary>
 277         /// Helper used for ensuring we only return 1 instance of a ReadOnlyCollection of T.
 278         ///
 279         /// This is similar to the ReturnReadOnly of T. This version supports nodes which hold
 280         /// onto multiple Expressions where one is typed to object.  That object field holds either
 281         /// an expression or a ReadOnlyCollection of Expressions.  When it holds a ReadOnlyCollection
 282         /// the IList which backs it is a ListArgumentProvider which uses the Expression which
 283         /// implements IArgumentProvider to get 2nd and additional values.  The ListArgumentProvider
 284         /// continues to hold onto the 1st expression.
 285         ///
 286         /// This enables users to get the ReadOnlyCollection w/o it consuming more memory than if
 287         /// it was just an array.  Meanwhile The DLR internally avoids accessing  which would force
 288         /// the readonly collection to be created resulting in a typical memory savings.
 289         /// </summary>
 290         internal static ReadOnlyCollection<Expression> ReturnReadOnly(IArgumentProvider provider, ref object collection) {
 291             Expression tObj = collection as Expression;
 292             if (tObj != null) {
 293                 // otherwise make sure only one readonly collection ever gets exposed
 294                 Interlocked.CompareExchange(
 295                     ref collection,
 296                     new ReadOnlyCollection<Expression>(new ListArgumentProvider(provider, tObj)),
 297                     tObj
 298                 );
 299             }
 300
 301             // and return what is not guaranteed to be a readonly collection
 302             return (ReadOnlyCollection<Expression>)collection;
 303         }
 304
 305         /// <summary>
 306         /// Helper which is used for specialized subtypes which use ReturnReadOnly(ref object, ...).
 307         /// This is the reverse version of ReturnReadOnly which takes an IArgumentProvider.
 308         ///
 309         /// This is used to return the 1st argument.  The 1st argument is typed as object and either
 310         /// contains a ReadOnlyCollection or the Expression.  We check for the Expression and if it's
 311         /// present we return that, otherwise we return the 1st element of the ReadOnlyCollection.
 312         /// </summary>
 313         internal static T ReturnObject<T>(object collectionOrT) where T : class {
 314             T t = collectionOrT as T;
 315             if (t != null) {
 316                 return t;
 317             }
 318
 319             return ((ReadOnlyCollection<T>)collectionOrT)[0];
 320         }
 321
 322         private static void RequiresCanRead(Expression expression, string paramName) {
 323             if (expression == null) {
 324                 throw new ArgumentNullException(paramName);
 325             }
 326
 327             // validate that we can read the node
 328             switch (expression.NodeType) {
 329                 case ExpressionType.Index:
 330                     IndexExpression index = (IndexExpression)expression;
 331                     if (index.Indexer != null && !index.Indexer.CanRead) {
 332                         throw new ArgumentException(Strings.ExpressionMustBeReadable, paramName);
 333                     }
 334                     break;
 335                 case ExpressionType.MemberAccess:
 336                     MemberExpression member = (MemberExpression)expression;
 337                     MemberInfo memberInfo = member.Member;
 338                     if (memberInfo.MemberType == MemberTypes.Property) {
 339                         PropertyInfo prop = (PropertyInfo)memberInfo;
 340                         if (!prop.CanRead) {
 341                             throw new ArgumentException(Strings.ExpressionMustBeReadable, paramName);
 342                         }
 343                     }
 344                     break;
 345             }
 346         }
 347
 348         private static void RequiresCanRead(IEnumerable<Expression> items, string paramName) {
 349             if (items != null) {
 350                 // this is called a lot, avoid allocating an enumerator if we can...
 351                 IList<Expression> listItems = items as IList<Expression>;
 352                 if (listItems != null) {
 353                     for (int i = 0; i < listItems.Count; i++) {
 354                         RequiresCanRead(listItems[i], paramName);
 355                     }
 356                     return;
 357                 }
 358
 359                 foreach (var i in items) {
 360                     RequiresCanRead(i, paramName);
 361                 }
 362             }
 363         }
 364         private static void RequiresCanWrite(Expression expression, string paramName) {
 365             if (expression == null) {
 366                 throw new ArgumentNullException(paramName);
 367             }
 368
 369             bool canWrite = false;
 370             switch (expression.NodeType) {
 371                 case ExpressionType.Index:
 372                     IndexExpression index = (IndexExpression)expression;
 373                     if (index.Indexer != null) {
 374                         canWrite = index.Indexer.CanWrite;
 375                     } else {
 376                         canWrite = true;
 377                     }
 378                     break;
 379                 case ExpressionType.MemberAccess:
 380                     MemberExpression member = (MemberExpression)expression;
 381                     switch (member.Member.MemberType) {
 382                         case MemberTypes.Property:
 383                             PropertyInfo prop = (PropertyInfo)member.Member;
 384                             canWrite = prop.CanWrite;
 385                             break;
 386                         case MemberTypes.Field:
 387                             FieldInfo field = (FieldInfo)member.Member;
 388                             canWrite = !(field.IsInitOnly || field.IsLiteral);
 389                             break;
 390                     }
 391                     break;
 392                 case ExpressionType.Parameter:
 393                     canWrite = true;
 394                     break;
 395             }
 396
 397             if (!canWrite) {
 398                 throw new ArgumentException(Strings.ExpressionMustBeWriteable, paramName);
 399             }
 400         }
 401     }
 402 }