// Copyright (c) Microsoft Open Technologies, Inc. All rights reserved. See License.txt in the project root for license information.

namespace System.Linq.Expressions
{
    using System.Collections.Generic;
    using System.Collections.ObjectModel;
    using System.Diagnostics.CodeAnalysis;
    using System.Linq.Expressions.Internal;

    // <summary>
    // Visitor for LINQ expression trees.
    // </summary>
    internal abstract class EntityExpressionVisitor
    {
        internal const ExpressionType CustomExpression = (ExpressionType)(-1);

        [SuppressMessage("Microsoft.Performance", "CA1800:DoNotCastUnnecessarily")]
        internal virtual Expression Visit(Expression exp)
        {
            if (exp == null)
            {
                return exp;
            }
            switch (exp.NodeType)
            {
                case ExpressionType.UnaryPlus:
                case ExpressionType.Negate:
                case ExpressionType.NegateChecked:
                case ExpressionType.Not:
                case ExpressionType.Convert:
                case ExpressionType.ConvertChecked:
                case ExpressionType.ArrayLength:
                case ExpressionType.Quote:
                case ExpressionType.TypeAs:
                    return VisitUnary((UnaryExpression)exp);
                case ExpressionType.Add:
                case ExpressionType.AddChecked:
                case ExpressionType.Subtract:
                case ExpressionType.SubtractChecked:
                case ExpressionType.Multiply:
                case ExpressionType.MultiplyChecked:
                case ExpressionType.Divide:
                case ExpressionType.Modulo:
                case ExpressionType.Power:
                case ExpressionType.And:
                case ExpressionType.AndAlso:
                case ExpressionType.Or:
                case ExpressionType.OrElse:
                case ExpressionType.Coalesce:
                case ExpressionType.ArrayIndex:
                case ExpressionType.RightShift:
                case ExpressionType.LeftShift:
                case ExpressionType.ExclusiveOr:
                    return VisitBinary((BinaryExpression)exp);
                case ExpressionType.LessThan:
                case ExpressionType.LessThanOrEqual:
                case ExpressionType.GreaterThan:
                case ExpressionType.GreaterThanOrEqual:
                case ExpressionType.Equal:
                case ExpressionType.NotEqual:
                    return VisitComparison((BinaryExpression)exp);
                case ExpressionType.TypeIs:
                    return VisitTypeIs((TypeBinaryExpression)exp);
                case ExpressionType.Conditional:
                    return VisitConditional((ConditionalExpression)exp);
                case ExpressionType.Constant:
                    return VisitConstant((ConstantExpression)exp);
                case ExpressionType.Parameter:
                    return VisitParameter((ParameterExpression)exp);
                case ExpressionType.MemberAccess:
                    return VisitMemberAccess((MemberExpression)exp);
                case ExpressionType.Call:
                    return VisitMethodCall((MethodCallExpression)exp);
                case ExpressionType.Lambda:
                    return VisitLambda((LambdaExpression)exp);
                case ExpressionType.New:
                    return VisitNew((NewExpression)exp);
                case ExpressionType.NewArrayInit:
                case ExpressionType.NewArrayBounds:
                    return VisitNewArray((NewArrayExpression)exp);
                case ExpressionType.Invoke:
                    return VisitInvocation((InvocationExpression)exp);
                case ExpressionType.MemberInit:
                    return VisitMemberInit((MemberInitExpression)exp);
                case ExpressionType.ListInit:
                    return VisitListInit((ListInitExpression)exp);
                case CustomExpression:
                    return VisitExtension(exp);
                default:
                    throw Error.UnhandledExpressionType(exp.NodeType);
            }
        }

        internal virtual MemberBinding VisitBinding(MemberBinding binding)
        {
            switch (binding.BindingType)
            {
                case MemberBindingType.Assignment:
                    return VisitMemberAssignment((MemberAssignment)binding);
                case MemberBindingType.MemberBinding:
                    return VisitMemberMemberBinding((MemberMemberBinding)binding);
                case MemberBindingType.ListBinding:
                    return VisitMemberListBinding((MemberListBinding)binding);
                default:
                    throw Error.UnhandledBindingType(binding.BindingType);
            }
        }

        internal virtual ElementInit VisitElementInitializer(ElementInit initializer)
        {
            var arguments = VisitExpressionList(initializer.Arguments);
            if (arguments != initializer.Arguments)
            {
                return Expression.ElementInit(initializer.AddMethod, arguments);
            }
            return initializer;
        }

        internal virtual Expression VisitUnary(UnaryExpression u)
        {
            var operand = Visit(u.Operand);
            if (operand != u.Operand)
            {
                return Expression.MakeUnary(u.NodeType, operand, u.Type, u.Method);
            }
            return u;
        }

        internal virtual Expression VisitBinary(BinaryExpression b)
        {
            var left = Visit(b.Left);
            var right = Visit(b.Right);
            var conversion = Visit(b.Conversion);
            if (left != b.Left
                || right != b.Right
                || conversion != b.Conversion)
            {
                if (b.NodeType == ExpressionType.Coalesce
                    && b.Conversion != null)
                {
                    return Expression.Coalesce(left, right, conversion as LambdaExpression);
                }
                else
                {
                    return Expression.MakeBinary(b.NodeType, left, right, b.IsLiftedToNull, b.Method);
                }
            }
            return b;
        }

        internal virtual Expression VisitComparison(BinaryExpression expression)
        {
            return VisitBinary(RemoveUnnecessaryConverts(expression));
        }

        internal virtual Expression VisitTypeIs(TypeBinaryExpression b)
        {
            var expr = Visit(b.Expression);
            if (expr != b.Expression)
            {
                return Expression.TypeIs(expr, b.TypeOperand);
            }
            return b;
        }

        internal virtual Expression VisitConstant(ConstantExpression c)
        {
            return c;
        }

        internal virtual Expression VisitConditional(ConditionalExpression c)
        {
            var test = Visit(c.Test);
            var ifTrue = Visit(c.IfTrue);
            var ifFalse = Visit(c.IfFalse);
            if (test != c.Test
                || ifTrue != c.IfTrue
                || ifFalse != c.IfFalse)
            {
                return Expression.Condition(test, ifTrue, ifFalse);
            }
            return c;
        }

        internal virtual Expression VisitParameter(ParameterExpression p)
        {
            return p;
        }

        internal virtual Expression VisitMemberAccess(MemberExpression m)
        {
            var exp = Visit(m.Expression);
            if (exp != m.Expression)
            {
                return Expression.MakeMemberAccess(exp, m.Member);
            }
            return m;
        }

        internal virtual Expression VisitMethodCall(MethodCallExpression m)
        {
            var obj = Visit(m.Object);
            IEnumerable<Expression> args = VisitExpressionList(m.Arguments);
            if (obj != m.Object
                || args != m.Arguments)
            {
                return Expression.Call(obj, m.Method, args);
            }
            return m;
        }

        internal virtual ReadOnlyCollection<Expression> VisitExpressionList(ReadOnlyCollection<Expression> original)
        {
            List<Expression> list = null;
            for (int i = 0, n = original.Count; i < n; i++)
            {
                var p = Visit(original[i]);
                if (list != null)
                {
                    list.Add(p);
                }
                else if (p != original[i])
                {
                    list = new List<Expression>(n);
                    for (var j = 0; j < i; j++)
                    {
                        list.Add(original[j]);
                    }
                    list.Add(p);
                }
            }
            if (list != null)
            {
                return list.ToReadOnlyCollection();
            }
            return original;
        }

        internal virtual MemberAssignment VisitMemberAssignment(MemberAssignment assignment)
        {
            var e = Visit(assignment.Expression);
            if (e != assignment.Expression)
            {
                return Expression.Bind(assignment.Member, e);
            }
            return assignment;
        }

        internal virtual MemberMemberBinding VisitMemberMemberBinding(MemberMemberBinding binding)
        {
            var bindings = VisitBindingList(binding.Bindings);
            if (bindings != binding.Bindings)
            {
                return Expression.MemberBind(binding.Member, bindings);
            }
            return binding;
        }

        internal virtual MemberListBinding VisitMemberListBinding(MemberListBinding binding)
        {
            var initializers = VisitElementInitializerList(binding.Initializers);
            if (initializers != binding.Initializers)
            {
                return Expression.ListBind(binding.Member, initializers);
            }
            return binding;
        }

        internal virtual IEnumerable<MemberBinding> VisitBindingList(ReadOnlyCollection<MemberBinding> original)
        {
            List<MemberBinding> list = null;
            for (int i = 0, n = original.Count; i < n; i++)
            {
                var b = VisitBinding(original[i]);
                if (list != null)
                {
                    list.Add(b);
                }
                else if (b != original[i])
                {
                    list = new List<MemberBinding>(n);
                    for (var j = 0; j < i; j++)
                    {
                        list.Add(original[j]);
                    }
                    list.Add(b);
                }
            }
            if (list != null)
            {
                return list;
            }
            return original;
        }

        internal virtual IEnumerable<ElementInit> VisitElementInitializerList(ReadOnlyCollection<ElementInit> original)
        {
            List<ElementInit> list = null;
            for (int i = 0, n = original.Count; i < n; i++)
            {
                var init = VisitElementInitializer(original[i]);
                if (list != null)
                {
                    list.Add(init);
                }
                else if (init != original[i])
                {
                    list = new List<ElementInit>(n);
                    for (var j = 0; j < i; j++)
                    {
                        list.Add(original[j]);
                    }
                    list.Add(init);
                }
            }
            if (list != null)
            {
                return list;
            }
            return original;
        }

        internal virtual Expression VisitLambda(LambdaExpression lambda)
        {
            var body = Visit(lambda.Body);
            if (body != lambda.Body)
            {
                return Expression.Lambda(lambda.Type, body, lambda.Parameters);
            }
            return lambda;
        }

        internal virtual NewExpression VisitNew(NewExpression nex)
        {
            IEnumerable<Expression> args = VisitExpressionList(nex.Arguments);
            if (args != nex.Arguments)
            {
                if (nex.Members != null)
                {
                    return Expression.New(nex.Constructor, args, nex.Members);
                }
                else
                {
                    return Expression.New(nex.Constructor, args);
                }
            }
            return nex;
        }

        internal virtual Expression VisitMemberInit(MemberInitExpression init)
        {
            var n = VisitNew(init.NewExpression);
            var bindings = VisitBindingList(init.Bindings);
            if (n != init.NewExpression
                || bindings != init.Bindings)
            {
                return Expression.MemberInit(n, bindings);
            }
            return init;
        }

        internal virtual Expression VisitListInit(ListInitExpression init)
        {
            var n = VisitNew(init.NewExpression);
            var initializers = VisitElementInitializerList(init.Initializers);
            if (n != init.NewExpression
                || initializers != init.Initializers)
            {
                return Expression.ListInit(n, initializers);
            }
            return init;
        }

        internal virtual Expression VisitNewArray(NewArrayExpression na)
        {
            IEnumerable<Expression> exprs = VisitExpressionList(na.Expressions);
            if (exprs != na.Expressions)
            {
                if (na.NodeType
                    == ExpressionType.NewArrayInit)
                {
                    return Expression.NewArrayInit(na.Type.GetElementType(), exprs);
                }
                else
                {
                    return Expression.NewArrayBounds(na.Type.GetElementType(), exprs);
                }
            }
            return na;
        }

        internal virtual Expression VisitInvocation(InvocationExpression iv)
        {
            IEnumerable<Expression> args = VisitExpressionList(iv.Arguments);
            var expr = Visit(iv.Expression);
            if (args != iv.Arguments
                || expr != iv.Expression)
            {
                return Expression.Invoke(expr, args);
            }
            return iv;
        }

        internal virtual Expression VisitExtension(Expression ext)
        {
            return ext;
        }

        internal static Expression Visit(Expression exp, Func<Expression, Func<Expression, Expression>, Expression> visit)
        {
            var basicVisitor = new BasicExpressionVisitor(visit);
            return basicVisitor.Visit(exp);
        }

        private static BinaryExpression RemoveUnnecessaryConverts(BinaryExpression expression)
        {
            if (expression.Method != null
                || expression.Left.Type != expression.Right.Type)
            {
                return expression;
            }

            switch (expression.Left.NodeType)
            {
                case ExpressionType.Convert:
                {
                    var leftConvert = (UnaryExpression)expression.Left;

                    switch (expression.Right.NodeType)
                    {
                        case ExpressionType.Convert:
                            var rightConvert = (UnaryExpression)expression.Right;

                            if (CanRemoveConverts(leftConvert, rightConvert))
                            {
                                return MakeBinaryExpression(expression.NodeType, leftConvert.Operand, rightConvert.Operand);
                            }
                            break;

                        case ExpressionType.Constant:
                            var constant = (ConstantExpression)expression.Right;

                            if (TryConvertConstant(ref constant, leftConvert.Operand.Type))
                            {
                                return MakeBinaryExpression(expression.NodeType, leftConvert.Operand, constant);
                            }
                            break;
                    }
                    break;
                }

                case ExpressionType.Constant:
                {
                    var constant = (ConstantExpression)expression.Left;

                    if (expression.Right.NodeType == ExpressionType.Convert)
                    {
                        var rightConvert = (UnaryExpression)expression.Right;

                        if (TryConvertConstant(ref constant, rightConvert.Operand.Type))
                        {
                            return MakeBinaryExpression(expression.NodeType, constant, rightConvert.Operand);
                        }
                    }
                    break;
                }
            }

            return expression;
        }

        private static bool CanRemoveConverts(UnaryExpression leftConvert, UnaryExpression rightConvert)
        {
            if (leftConvert.Method != null || rightConvert.Method != null)
            {
                return false;
            }

            if (Type.GetTypeCode(leftConvert.Type) != TypeCode.Int32)
            {
                return false;
            }

            switch (Type.GetTypeCode(leftConvert.Operand.Type))
            {
                case TypeCode.Byte:
                case TypeCode.Int16:
                    break;
                default:
                    return false;
            }

            return leftConvert.Operand.Type == rightConvert.Operand.Type;
        }

        private static bool TryConvertConstant(ref ConstantExpression constant, Type type)
        {
            if (Type.GetTypeCode(constant.Type) != TypeCode.Int32)
            {
                return false;
            }

            var value = (int)constant.Value;

            switch (Type.GetTypeCode(type))
            {
                case TypeCode.Byte:
                    if (value >= Byte.MinValue && value <= Byte.MaxValue)
                    {
                        constant = Expression.Constant((byte)value);
                        return true;
                    }
                    break;

                case TypeCode.Int16:
                    if (value >= Int16.MinValue && value <= Int16.MaxValue)
                    {
                        constant = Expression.Constant((short)value);
                        return true;
                    }
                    break;
            }

            return false;
        }

        private static BinaryExpression MakeBinaryExpression(ExpressionType expressionType, Expression left, Expression right)
        {
            if (left.Type.IsEnum)
            {
                left = Expression.Convert(left, left.Type.GetEnumUnderlyingType());
            }

            if (right.Type.IsEnum)
            {
                right = Expression.Convert(right, right.Type.GetEnumUnderlyingType());
            }

            return Expression.MakeBinary(expressionType, left, right);
        }

        private sealed class BasicExpressionVisitor : EntityExpressionVisitor
        {
            private readonly Func<Expression, Func<Expression, Expression>, Expression> _visit;

            internal BasicExpressionVisitor(Func<Expression, Func<Expression, Expression>, Expression> visit)
            {
                _visit = visit ?? ((exp, baseVisit) => baseVisit(exp));
            }

            internal override Expression Visit(Expression exp)
            {
                return _visit(exp, base.Visit);
            }
        }
    }
}
