// Copyright © Microsoft Corporation.
// This source file is subject to the Microsoft Permissive License.
// See http://www.microsoft.com/resources/sharedsource/licensingbasics/sharedsourcelicenses.mspx.
// All other rights reserved.

#if !MinimalReader || !NoWriter
using System;
using System.Collections;
using System.Diagnostics;

#if CCINamespace
namespace Microsoft.Cci{
#else
namespace System.Compiler
{
#endif
    /// <summary>
    /// Walks a normalized IR, removing push, pop and dup instructions, replacing them with references to local variables.
    /// Requires all Blocks to be basic blocks. I.e. any transfer statement is always the last statement in a block.
    /// (This precondition is established by Reader but not by Normalizer.)
    /// </summary>
    public class Unstacker : StandardVisitor
    {
        private TrivialHashtable/*!*/ SucessorBlock = new TrivialHashtable();
        private TrivialHashtable/*!*/ StackLocalsAtEntry = new TrivialHashtable();
        private LocalsStack/*!*/ localsStack = new LocalsStack();

        public Unstacker()
        {
            //^ base();
        }

        public override Statement VisitAssignmentStatement(AssignmentStatement assignment)
        {
            if (assignment == null) return null;
            assignment.Source = this.VisitExpression(assignment.Source);
            assignment.Target = this.VisitTargetExpression(assignment.Target);
            return assignment;
        }
        public override Expression VisitBinaryExpression(BinaryExpression binaryExpression)
        {
            if (binaryExpression == null) return null;
            binaryExpression.Operand2 = this.VisitExpression(binaryExpression.Operand2);
            binaryExpression.Operand1 = this.VisitExpression(binaryExpression.Operand1);
            if (binaryExpression.Type == null) binaryExpression.Type = binaryExpression.Operand1.Type; //Hack: need proper inferencing
            return binaryExpression;
        }
        public override Block VisitBlock(Block block)
        {
            if (block == null) return null;
            LocalsStack stackLocalsAtEntry = (LocalsStack)this.StackLocalsAtEntry[block.UniqueKey];
            if (stackLocalsAtEntry == null)
            {
                //Unreachable code, or the very first block
                stackLocalsAtEntry = new LocalsStack();
            }
            this.localsStack = stackLocalsAtEntry.Clone();
            base.VisitBlock(block);
            Block successor = (Block)this.SucessorBlock[block.UniqueKey];
            if (successor != null)
            {
                //Dropping off into successor.
                LocalsStack targetStack = (LocalsStack)this.StackLocalsAtEntry[successor.UniqueKey];
                if (targetStack != null && targetStack.top >= 0)
                {
                    //Another predecessor block has already decided what the stack for the successor block is going to look like.
                    //Reconcile the stack from this block with the stack expected by the successor block.
                    this.localsStack.Transfer(targetStack, block.Statements);
                }
                else
                {
                    this.StackLocalsAtEntry[successor.UniqueKey] = this.localsStack;
                }
            }
            return block;
        }
        public override Statement VisitBranch(Branch branch)
        {
            if (branch == null) return null;
            if (branch.Target == null) return null;
            branch.Condition = this.VisitExpression(branch.Condition);
            int n = this.localsStack.top + 1;
            LocalsStack targetStack = (LocalsStack)this.StackLocalsAtEntry[branch.Target.UniqueKey];
            if (targetStack == null)
            {
                this.StackLocalsAtEntry[branch.Target.UniqueKey] = this.localsStack.Clone();
                return branch;
            }
            //Target block has an entry stack that is different from the current stack. Need to copy stack before branching.
            if (n <= 0) return branch; //Empty stack, no need to copy
            StatementList statements = new StatementList(n + 1);
            this.localsStack.Transfer(targetStack, statements);
            statements.Add(branch);
            return new Block(statements);
        }
        public override Statement VisitSwitchInstruction(SwitchInstruction switchInstruction)
        {
            if (switchInstruction == null) return null;
            switchInstruction.Expression = this.VisitExpression(switchInstruction.Expression);
            for (int i = 0, n = switchInstruction.Targets == null ? 0 : switchInstruction.Targets.Count; i < n; i++)
            {
                Block target = switchInstruction.Targets[i];
                if (target == null) continue;
                this.StackLocalsAtEntry[target.UniqueKey] = this.localsStack.Clone();
            }
            return switchInstruction;
        }
        public override ExpressionList VisitExpressionList(ExpressionList expressions)
        {
            if (expressions == null) return null;
            for (int i = expressions.Count - 1; i >= 0; i--)
                expressions[i] = this.VisitExpression(expressions[i]);
            return expressions;
        }
        public override Statement VisitExpressionStatement(ExpressionStatement statement)
        {
            if (statement == null) return null;
            Expression e = statement.Expression = this.VisitExpression(statement.Expression);
            if (e == null || e.Type == CoreSystemTypes.Void) return statement;
            if (e.NodeType == NodeType.Dup) return this.localsStack.Dup();
            return this.localsStack.Push(e);
        }
        public override Expression VisitExpression(Expression expression)
        {
            if (expression == null) return null;
            switch (expression.NodeType)
            {
                case NodeType.Dup:
                case NodeType.Arglist:
                    return expression;
                case NodeType.Pop:
                    UnaryExpression uex = expression as UnaryExpression;
                    if (uex != null)
                    {
                        Expression e = uex.Operand = this.VisitExpression(uex.Operand);
                        if (e == null) return null;
                        uex.Type = CoreSystemTypes.Void;
                        return uex;
                    }
                    return this.localsStack.Pop();
                default:
                    return (Expression)this.Visit(expression);
            }
        }
        public override Expression VisitIndexer(Indexer indexer)
        {
            if (indexer == null) return null;
            indexer.Operands = this.VisitExpressionList(indexer.Operands);
            indexer.Object = this.VisitExpression(indexer.Object);
            return indexer;
        }
        public override Method VisitMethod(Method method)
        {
            // body might not have been materialized, so make sure we do that first!
            Block body = method.Body;

            if (method == null) return null;
            BlockSorter blockSorter = new BlockSorter();
            BlockList sortedBlocks = blockSorter.SortedBlocks;
            this.SucessorBlock = blockSorter.SuccessorBlock;
            this.StackLocalsAtEntry = new TrivialHashtable();
            this.localsStack = new LocalsStack();
            ExceptionHandlerList ehandlers = method.ExceptionHandlers;
            for (int i = 0, n = ehandlers == null ? 0 : ehandlers.Count; i < n; i++)
            {
                ExceptionHandler ehandler = ehandlers[i];
                if (ehandler == null) continue;
                Block handlerStart = ehandler.HandlerStartBlock;
                if (handlerStart == null) continue;
                LocalsStack lstack = new LocalsStack();
                this.StackLocalsAtEntry[handlerStart.UniqueKey] = lstack;
                if (ehandler.HandlerType == NodeType.Catch)
                {
                    lstack.exceptionHandlerType = CoreSystemTypes.Object;
                    if (ehandler.FilterType != null) lstack.exceptionHandlerType = ehandler.FilterType;
                }
                else if (ehandler.HandlerType == NodeType.Filter)
                {
                    lstack.exceptionHandlerType = CoreSystemTypes.Object;
                    if (ehandler.FilterExpression != null)
                    {
                        lstack = new LocalsStack();
                        lstack.exceptionHandlerType = CoreSystemTypes.Object;
                        this.StackLocalsAtEntry[ehandler.FilterExpression.UniqueKey] = lstack;
                    }
                }
            }
            blockSorter.VisitMethodBody(body);
            for (int i = 0, n = sortedBlocks.Count; i < n; i++)
            {
                Block b = sortedBlocks[i];
                if (b == null) { Debug.Assert(false); continue; }
                this.VisitBlock(b);
            }
            return method;
        }
        public override Expression VisitMethodCall(MethodCall call)
        {
            if (call == null) return null;
            call.Operands = this.VisitExpressionList(call.Operands);
            call.Callee = this.VisitExpression(call.Callee);
            return call;
        }
        public override Expression VisitTernaryExpression(TernaryExpression expression)
        {
            if (expression == null) return null;
            expression.Operand3 = this.VisitExpression(expression.Operand3);
            expression.Operand2 = this.VisitExpression(expression.Operand2);
            expression.Operand1 = this.VisitExpression(expression.Operand1);
            return expression;
        }

        private class LocalsStack
        {
            private Local[]/*!*/ elements;
            internal int top = -1;
            internal TypeNode exceptionHandlerType;

            private void Grow()
            {
                int n = this.elements.Length;
                Local[] newElements = new Local[n + 8];
                for (int i = 0; i < n; i++) newElements[i] = this.elements[i];
                this.elements = newElements;
            }
            internal LocalsStack()
            {
                this.elements = new Local[8];
                //^ base();
            }
            private LocalsStack(LocalsStack/*!*/ other)
            {
                this.top = other.top;
                this.exceptionHandlerType = other.exceptionHandlerType;
                Local[] otherElements = other.elements;
                int n = otherElements.Length;
                Local[] elements = this.elements = new Local[n];
                //^ base();
                n = this.top + 1;
                for (int i = 0; i < n; i++)
                    elements[i] = otherElements[i];
            }
            internal LocalsStack/*!*/ Clone()
            {
                return new LocalsStack(this);
            }
            internal AssignmentStatement Dup()
            {
                int i = this.top;
                Expression topVal;
                if (this.top == -1 && this.exceptionHandlerType != null)
                {
                    topVal = new Expression(NodeType.Dup, this.exceptionHandlerType);
                }
                else
                {
                    Debug.Assert(i >= 0 && i < this.elements.Length);
                    topVal = this.elements[i];
                    //^ assume topVal != null;
                }
                Local dup = new Local(topVal.Type);
                if ((i = ++this.top) >= this.elements.Length) this.Grow();
                this.elements[i] = dup;
                return new AssignmentStatement(dup, topVal);
            }
            internal AssignmentStatement Push(Expression/*!*/ expr)
            {
                //Debug.Assert(expr != null && expr.Type != null);
                int i = ++this.top;
                Debug.Assert(i >= 0);
                if (i >= this.elements.Length) this.Grow();
                Local loc = this.elements[i];
                if (loc == null || loc.Type != expr.Type)
                    this.elements[i] = loc = new Local(expr.Type);
                return new AssignmentStatement(loc, expr);
            }
            internal Expression Pop()
            {
                if (this.top == -1 && this.exceptionHandlerType != null)
                {
                    TypeNode t = this.exceptionHandlerType;
                    this.exceptionHandlerType = null;
                    return new Expression(NodeType.Pop, t);
                }
                int i = this.top--;
                Debug.Assert(i >= 0 && i < this.elements.Length);
                return this.elements[i];
            }
            internal void Transfer(LocalsStack/*!*/ targetStack, StatementList/*!*/ statements)
            {
                Debug.Assert(targetStack != null);
                if (targetStack == this) return;
                int n = this.top;
                Debug.Assert(n == targetStack.top);
                for (int i = 0; i <= n; i++)
                {
                    Local sloc = this.elements[i];
                    Local tloc = targetStack.elements[i];
                    if (sloc == tloc) continue;
                    Debug.Assert(sloc != null && tloc != null);
                    statements.Add(new AssignmentStatement(tloc, sloc));
                }
            }
        }
        private class BlockSorter : StandardVisitor
        {
            private TrivialHashtable/*!*/ VisitedBlocks = new TrivialHashtable();
            private TrivialHashtable/*!*/ BlocksThatDropThrough = new TrivialHashtable();
            private bool lastBranchWasUnconditional = false;
            internal BlockList/*!*/ SortedBlocks = new BlockList();
            internal TrivialHashtable/*!*/ SuccessorBlock = new TrivialHashtable();

            internal BlockSorter()
            {
                //^ base();
            }

            internal void VisitMethodBody(Block body)
            {
                if (body == null) return;
                StatementList statements = body.Statements;
                Block previousBlock = null;
                for (int i = 0, n = statements.Count; i < n; i++)
                {
                    Block b = statements[i] as Block;
                    if (b == null) { Debug.Assert(false); continue; }
                    if (previousBlock != null && this.BlocksThatDropThrough[previousBlock.UniqueKey] != null)
                    {
                        this.SuccessorBlock[previousBlock.UniqueKey] = b;
                    }
                    this.VisitBlock(b);
                    previousBlock = b;
                }
            }
            public override Block VisitBlock(Block block)
            {
                if (block == null) return null;
                if (this.VisitedBlocks[block.UniqueKey] != null)
                {
                    return block;
                }
                this.VisitedBlocks[block.UniqueKey] = block;
                this.SortedBlocks.Add(block);
                this.lastBranchWasUnconditional = false;
                base.VisitBlock(block);
                if (!this.lastBranchWasUnconditional)
                    this.BlocksThatDropThrough[block.UniqueKey] = block;
                return block;
            }
            public override Statement VisitBranch(Branch branch)
            {
                if (branch == null) return null;
                if (branch.Target == null) return null;
                this.VisitBlock(branch.Target);
                this.lastBranchWasUnconditional = branch.Condition == null;
                return branch;
            }
            public override Statement VisitReturn(Return ret)
            {
                this.lastBranchWasUnconditional = true;
                return ret;
            }
            public override Statement VisitSwitchInstruction(SwitchInstruction switchInstruction)
            {
                if (switchInstruction == null) return null;
                switchInstruction.Expression = this.VisitExpression(switchInstruction.Expression);
                for (int i = 0, n = switchInstruction.Targets == null ? 0 : switchInstruction.Targets.Count; i < n; i++)
                {
                    Block target = switchInstruction.Targets[i];
                    if (target == null) continue;
                    this.VisitBlock(target);
                }
                return switchInstruction;
            }
            public override Statement VisitThrow(Throw Throw)
            {
                this.lastBranchWasUnconditional = true;
                return Throw;
            }
        }
    }
}
#endif