/*
 * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package jdk.nashorn.internal.codegen;

import static jdk.nashorn.internal.codegen.CompilerConstants.RETURN;
import static jdk.nashorn.internal.ir.Expression.isAlwaysFalse;
import static jdk.nashorn.internal.ir.Expression.isAlwaysTrue;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import jdk.nashorn.internal.codegen.types.Type;
import jdk.nashorn.internal.ir.AccessNode;
import jdk.nashorn.internal.ir.BinaryNode;
import jdk.nashorn.internal.ir.Block;
import jdk.nashorn.internal.ir.BreakNode;
import jdk.nashorn.internal.ir.BreakableNode;
import jdk.nashorn.internal.ir.CallNode;
import jdk.nashorn.internal.ir.CaseNode;
import jdk.nashorn.internal.ir.CatchNode;
import jdk.nashorn.internal.ir.ContinueNode;
import jdk.nashorn.internal.ir.Expression;
import jdk.nashorn.internal.ir.ExpressionStatement;
import jdk.nashorn.internal.ir.ForNode;
import jdk.nashorn.internal.ir.FunctionNode;
import jdk.nashorn.internal.ir.GetSplitState;
import jdk.nashorn.internal.ir.IdentNode;
import jdk.nashorn.internal.ir.IfNode;
import jdk.nashorn.internal.ir.IndexNode;
import jdk.nashorn.internal.ir.JoinPredecessor;
import jdk.nashorn.internal.ir.JoinPredecessorExpression;
import jdk.nashorn.internal.ir.JumpStatement;
import jdk.nashorn.internal.ir.JumpToInlinedFinally;
import jdk.nashorn.internal.ir.LabelNode;
import jdk.nashorn.internal.ir.LexicalContext;
import jdk.nashorn.internal.ir.LexicalContextNode;
import jdk.nashorn.internal.ir.LiteralNode;
import jdk.nashorn.internal.ir.LiteralNode.ArrayLiteralNode;
import jdk.nashorn.internal.ir.LocalVariableConversion;
import jdk.nashorn.internal.ir.LoopNode;
import jdk.nashorn.internal.ir.Node;
import jdk.nashorn.internal.ir.ObjectNode;
import jdk.nashorn.internal.ir.PropertyNode;
import jdk.nashorn.internal.ir.ReturnNode;
import jdk.nashorn.internal.ir.RuntimeNode;
import jdk.nashorn.internal.ir.RuntimeNode.Request;
import jdk.nashorn.internal.ir.SplitReturn;
import jdk.nashorn.internal.ir.Statement;
import jdk.nashorn.internal.ir.SwitchNode;
import jdk.nashorn.internal.ir.Symbol;
import jdk.nashorn.internal.ir.TernaryNode;
import jdk.nashorn.internal.ir.ThrowNode;
import jdk.nashorn.internal.ir.TryNode;
import jdk.nashorn.internal.ir.UnaryNode;
import jdk.nashorn.internal.ir.VarNode;
import jdk.nashorn.internal.ir.WhileNode;
import jdk.nashorn.internal.ir.WithNode;
import jdk.nashorn.internal.ir.visitor.NodeVisitor;
import jdk.nashorn.internal.ir.visitor.SimpleNodeVisitor;
import jdk.nashorn.internal.parser.TokenType;

/**
 * Calculates types for local variables. For purposes of local variable type calculation, the only types used are
 * Undefined, boolean, int, long, double, and Object. The calculation eagerly widens types of local variable to their
 * widest at control flow join points.
 * TODO: investigate a more sophisticated solution that uses use/def information to only widens the type of a local
 * variable to its widest used type after the join point. That would eliminate some widenings of undefined variables to
 * object, most notably those used only in loops. We need a full liveness analysis for that. Currently, we can establish
 * per-type liveness, which eliminates most of unwanted dead widenings.
 * NOTE: the way this class is implemented, it actually processes the AST in two passes. The first pass is top-down and
 * implemented in {@code enterXxx} methods. This pass does not mutate the AST (except for one occurrence, noted below),
 * as being able to find relevant labels for control flow joins is sensitive to their reference identity, and mutated
 * label-carrying nodes will create copies of their labels. A second bottom-up pass applying the changes is implemented
 * in the separate visitor sitting in {@link #leaveFunctionNode(FunctionNode)}. This visitor will also instantiate new
 * instances of the calculator to be run on nested functions (when not lazy compiling).
 *
 */
final class LocalVariableTypesCalculator extends SimpleNodeVisitor {

    private static class JumpOrigin {
        final JoinPredecessor node;
        final Map<Symbol, LvarType> types;

        JumpOrigin(final JoinPredecessor node, final Map<Symbol, LvarType> types) {
            this.node = node;
            this.types = types;
        }
    }

    private static class JumpTarget {
        private final List<JumpOrigin> origins = new LinkedList<>();
        private Map<Symbol, LvarType> types = Collections.emptyMap();

        void addOrigin(final JoinPredecessor originNode, final Map<Symbol, LvarType> originTypes, final LocalVariableTypesCalculator calc) {
            origins.add(new JumpOrigin(originNode, originTypes));
            this.types = calc.getUnionTypes(this.types, originTypes);
        }
    }
    private enum LvarType {
        UNDEFINED(Type.UNDEFINED),
        BOOLEAN(Type.BOOLEAN),
        INT(Type.INT),
        DOUBLE(Type.NUMBER),
        OBJECT(Type.OBJECT);

        private final Type type;
        private final TypeHolderExpression typeExpression;

        private LvarType(final Type type) {
            this.type = type;
            this.typeExpression = new TypeHolderExpression(type);
        }
    }

    /**
     * A bogus Expression subclass that only reports its type. Used to interrogate BinaryNode and UnaryNode about their
     * types by creating temporary copies of them and replacing their operands with instances of these. An alternative
     * solution would be to add BinaryNode.getType(Type lhsType, Type rhsType) and UnaryNode.getType(Type exprType)
     * methods. For the time being though, this is easier to implement and is in fact fairly clean. It does result in
     * generation of higher number of temporary short lived nodes, though.
     */
    private static class TypeHolderExpression extends Expression {
        private static final long serialVersionUID = 1L;

        private final Type type;

        TypeHolderExpression(final Type type) {
            super(0L, 0, 0);
            this.type = type;
        }

        @Override
        public Node accept(final NodeVisitor<? extends LexicalContext> visitor) {
            throw new AssertionError();
        }

        @Override
        public Type getType() {
            return type;
        }

        @Override
        public void toString(final StringBuilder sb, final boolean printType) {
            throw new AssertionError();
        }
    }

    private static final Map<Type, LvarType> TO_LVAR_TYPE = new IdentityHashMap<>();

    static {
        for(final LvarType lvarType: LvarType.values()) {
            TO_LVAR_TYPE.put(lvarType.type, lvarType);
        }
    }

    @SuppressWarnings("unchecked")
    private static HashMap<Symbol, LvarType> cloneMap(final Map<Symbol, LvarType> map) {
        return (HashMap<Symbol, LvarType>)((HashMap<?,?>)map).clone();
    }

    private LocalVariableConversion createConversion(final Symbol symbol, final LvarType branchLvarType,
            final Map<Symbol, LvarType> joinLvarTypes, final LocalVariableConversion next) {
        if (invalidatedSymbols.contains(symbol)) {
            return next;
        }
        final LvarType targetType = joinLvarTypes.get(symbol);
        assert targetType != null;
        if(targetType == branchLvarType) {
            return next;
        }
        // NOTE: we could naively just use symbolIsUsed(symbol, branchLvarType) here, but that'd be wrong. While
        // technically a conversion will read the value of the symbol with that type, but it will also write it to a new
        // type, and that type might be dead (we can't know yet). For this reason, we don't treat conversion reads as
        // real uses until we know their target type is live. If we didn't do this, and just did a symbolIsUsed here,
        // we'd introduce false live variables which could nevertheless turn into dead ones in a subsequent
        // deoptimization, causing a shift in the list of live locals that'd cause erroneous restoration of
        // continuations (since RewriteException's byteCodeSlots carries an array and not a name-value map).

        symbolIsConverted(symbol, branchLvarType, targetType);
        return new LocalVariableConversion(symbol, branchLvarType.type, targetType.type, next);
    }

    private Map<Symbol, LvarType> getUnionTypes(final Map<Symbol, LvarType> types1, final Map<Symbol, LvarType> types2) {
        if(types1 == types2 || types1.isEmpty()) {
            return types2;
        } else if(types2.isEmpty()) {
            return types1;
        }
        final Set<Symbol> commonSymbols = new HashSet<>(types1.keySet());
        commonSymbols.retainAll(types2.keySet());
        // We have a chance of returning an unmodified set if both sets have the same keys and one is strictly wider
        // than the other.
        final int commonSize = commonSymbols.size();
        final int types1Size = types1.size();
        final int types2Size = types2.size();
        if(commonSize == types1Size && commonSize == types2Size) {
            boolean matches1 = true, matches2 = true;
            Map<Symbol, LvarType> union = null;
            for(final Symbol symbol: commonSymbols) {
                final LvarType type1 = types1.get(symbol);
                final LvarType type2 = types2.get(symbol);
                final LvarType widest = widestLvarType(type1, type2);
                if(widest != type1 && matches1) {
                    matches1 = false;
                    if(!matches2) {
                        union = cloneMap(types1);
                    }
                }
                if (widest != type2 && matches2) {
                    matches2 = false;
                    if(!matches1) {
                        union = cloneMap(types2);
                    }
                }
                if(!(matches1 || matches2)) {
                    assert union != null;
                    union.put(symbol, widest);
                }
            }
            return matches1 ? types1 : matches2 ? types2 : union;
        }
        // General case
        final Map<Symbol, LvarType> union;
        if(types1Size > types2Size) {
            union = cloneMap(types1);
            union.putAll(types2);
        } else {
            union = cloneMap(types2);
            union.putAll(types1);
        }
        for(final Symbol symbol: commonSymbols) {
            final LvarType type1 = types1.get(symbol);
            final LvarType type2 = types2.get(symbol);
            union.put(symbol, widestLvarType(type1,  type2));
        }
        // If the two sets of symbols differ, there's a good chance that some of
        // symbols only appearing in one of the sets are lexically invalidated,
        // so we remove them from further consideration.
        // This is not strictly necessary, just a working set size optimization.
        union.keySet().removeAll(invalidatedSymbols);
        return union;
    }

    private static void symbolIsUsed(final Symbol symbol, final LvarType type) {
        if(type != LvarType.UNDEFINED) {
            symbol.setHasSlotFor(type.type);
        }
    }

    private static class SymbolConversions {
        private static final byte I2D = 1 << 0;
        private static final byte I2O = 1 << 1;
        private static final byte D2O = 1 << 2;

        private byte conversions;

        void recordConversion(final LvarType from, final LvarType to) {
            switch (from) {
            case UNDEFINED:
                return;
            case INT:
            case BOOLEAN:
                switch (to) {
                case DOUBLE:
                    recordConversion(I2D);
                    return;
                case OBJECT:
                    recordConversion(I2O);
                    return;
                default:
                    illegalConversion(from, to);
                    return;
                }
            case DOUBLE:
                if(to == LvarType.OBJECT) {
                    recordConversion(D2O);
                }
                return;
            default:
                illegalConversion(from, to);
            }
        }

        private static void illegalConversion(final LvarType from, final LvarType to) {
            throw new AssertionError("Invalid conversion from " + from + " to " + to);
        }

        void recordConversion(final byte convFlag) {
            conversions = (byte)(conversions | convFlag);
        }

        boolean hasConversion(final byte convFlag) {
            return (conversions & convFlag) != 0;
        }

        void calculateTypeLiveness(final Symbol symbol) {
            if(symbol.hasSlotFor(Type.OBJECT)) {
                if(hasConversion(D2O)) {
                    symbol.setHasSlotFor(Type.NUMBER);
                }
                if(hasConversion(I2O)) {
                    symbol.setHasSlotFor(Type.INT);
                }
            }
            if(symbol.hasSlotFor(Type.NUMBER)) {
                if(hasConversion(I2D)) {
                    symbol.setHasSlotFor(Type.INT);
                }
            }
        }
    }

    private void symbolIsConverted(final Symbol symbol, final LvarType from, final LvarType to) {
        SymbolConversions conversions = symbolConversions.get(symbol);
        if(conversions == null) {
            conversions = new SymbolConversions();
            symbolConversions.put(symbol, conversions);
        }
        conversions.recordConversion(from, to);
    }

    private static LvarType toLvarType(final Type type) {
        assert type != null;
        final LvarType lvarType = TO_LVAR_TYPE.get(type);
        if(lvarType != null) {
            return lvarType;
        }
        assert type.isObject() : "Unsupported primitive type: " + type;
        return LvarType.OBJECT;
    }
    private static LvarType widestLvarType(final LvarType t1, final LvarType t2) {
        if(t1 == t2) {
            return t1;
        }
        // Undefined or boolean to anything always widens to object.
        if(t1.ordinal() < LvarType.INT.ordinal() || t2.ordinal() < LvarType.INT.ordinal()) {
            return LvarType.OBJECT;
        }
        return LvarType.values()[Math.max(t1.ordinal(), t2.ordinal())];
    }
    private final Compiler compiler;
    private final Map<Label, JumpTarget> jumpTargets = new IdentityHashMap<>();
    // Local variable type mapping at the currently evaluated point. No map instance is ever modified; setLvarType() always
    // allocates a new map. Immutability of maps allows for cheap snapshots by just keeping the reference to the current
    // value.
    private Map<Symbol, LvarType> localVariableTypes = Collections.emptyMap();
    // Set of symbols whose lexical scope has already ended.
    private final Set<Symbol> invalidatedSymbols = new HashSet<>();

    // Stack for evaluated expression types.
    private final Deque<LvarType> typeStack = new ArrayDeque<>();

    // Whether the current point in the AST is reachable code
    private boolean reachable = true;
    // Return type of the function
    private Type returnType = Type.UNKNOWN;
    // Synthetic return node that we must insert at the end of the function if it's end is reachable.
    private ReturnNode syntheticReturn;

    private boolean alreadyEnteredTopLevelFunction;

    // LvarType and conversion information gathered during the top-down pass; applied to nodes in the bottom-up pass.
    private final Map<JoinPredecessor, LocalVariableConversion> localVariableConversions = new IdentityHashMap<>();

    private final Map<IdentNode, LvarType> identifierLvarTypes = new IdentityHashMap<>();
    private final Map<Symbol, SymbolConversions> symbolConversions = new IdentityHashMap<>();

    // Stack of open labels for starts of catch blocks, one for every currently traversed try block; for inserting
    // control flow edges to them. Note that we currently don't insert actual control flow edges, but instead edges that
    // help us with type calculations. This means that some operations that can result in an exception being thrown
    // aren't considered (function calls, side effecting property getters and setters etc.), while some operations that
    // don't result in control flow transfers do originate an edge to the catch blocks (namely, assignments to local
    // variables).
    private final Deque<Label> catchLabels = new ArrayDeque<>();

    LocalVariableTypesCalculator(final Compiler compiler) {
        this.compiler = compiler;
    }

    private JumpTarget createJumpTarget(final Label label) {
        assert !jumpTargets.containsKey(label);
        final JumpTarget jumpTarget = new JumpTarget();
        jumpTargets.put(label, jumpTarget);
        return jumpTarget;
    }

    private void doesNotContinueSequentially() {
        reachable = false;
        localVariableTypes = Collections.emptyMap();
        assertTypeStackIsEmpty();
    }

    private boolean pushExpressionType(final Expression expr) {
        typeStack.push(toLvarType(expr.getType()));
        return false;
    }

    @Override
    public boolean enterAccessNode(final AccessNode accessNode) {
        visitExpression(accessNode.getBase());
        return pushExpressionType(accessNode);
    }

    @Override
    public boolean enterBinaryNode(final BinaryNode binaryNode) {
        // NOTE: regardless of operator's lexical associativity, lhs is always evaluated first.
        final Expression lhs = binaryNode.lhs();
        final LvarType lhsType;
        if (!(lhs instanceof IdentNode && binaryNode.isTokenType(TokenType.ASSIGN))) {
            lhsType = visitExpression(lhs);
        } else {
            // Can't visit IdentNode on LHS of a simple assignment, as visits imply use, and this is def.
            // The type is irrelevant, as only RHS is used to determine the type anyway.
            lhsType = LvarType.UNDEFINED;
        }

        final boolean isLogical = binaryNode.isLogical();
        final Label joinLabel = isLogical ? new Label("") : null;
        if(isLogical) {
            jumpToLabel((JoinPredecessor)lhs, joinLabel);
        }

        final Expression rhs = binaryNode.rhs();
        final LvarType rhsType = visitExpression(rhs);
        if(isLogical) {
            jumpToLabel((JoinPredecessor)rhs, joinLabel);
        }
        joinOnLabel(joinLabel);

        final LvarType type = toLvarType(binaryNode.setOperands(lhsType.typeExpression, rhsType.typeExpression).getType());

        if(binaryNode.isAssignment() && lhs instanceof IdentNode) {
            if(binaryNode.isSelfModifying()) {
                onSelfAssignment((IdentNode)lhs, type);
            } else {
                onAssignment((IdentNode)lhs, type);
            }
        }
        typeStack.push(type);
        return false;
    }

    @Override
    public boolean enterBlock(final Block block) {
        boolean cloned = false;
        for(final Symbol symbol: block.getSymbols()) {
            if(symbol.isBytecodeLocal()) {
                if (getLocalVariableTypeOrNull(symbol) == null) {
                    if (!cloned) {
                        cloneOrNewLocalVariableTypes();
                        cloned = true;
                    }
                    localVariableTypes.put(symbol, LvarType.UNDEFINED);
                }
                // In case we're repeating analysis of a lexical scope (e.g. it's in a loop),
                // make sure all symbols lexically scoped by the block become valid again.
                invalidatedSymbols.remove(symbol);
            }
        }
        return true;
    }

    @Override
    public boolean enterBreakNode(final BreakNode breakNode) {
        return enterJumpStatement(breakNode);
    }

    @Override
    public boolean enterCallNode(final CallNode callNode) {
        visitExpression(callNode.getFunction());
        visitExpressions(callNode.getArgs());
        final CallNode.EvalArgs evalArgs = callNode.getEvalArgs();
        if (evalArgs != null) {
            visitExpressions(evalArgs.getArgs());
        }
        return pushExpressionType(callNode);
    }

    @Override
    public boolean enterContinueNode(final ContinueNode continueNode) {
        return enterJumpStatement(continueNode);
    }

    private boolean enterJumpStatement(final JumpStatement jump) {
        if(!reachable) {
            return false;
        }
        assertTypeStackIsEmpty();
        jumpToLabel(jump, jump.getTargetLabel(lc), getBreakTargetTypes(jump.getPopScopeLimit(lc)));
        doesNotContinueSequentially();
        return false;
    }

    @Override
    protected boolean enterDefault(final Node node) {
        return reachable;
    }

    private void enterDoWhileLoop(final WhileNode loopNode) {
        assertTypeStackIsEmpty();
        final JoinPredecessorExpression test = loopNode.getTest();
        final Block body = loopNode.getBody();
        final Label continueLabel = loopNode.getContinueLabel();
        final Label breakLabel = loopNode.getBreakLabel();
        final Map<Symbol, LvarType> beforeLoopTypes = localVariableTypes;
        final Label repeatLabel = new Label("");
        for(;;) {
            jumpToLabel(loopNode, repeatLabel, beforeLoopTypes);
            final Map<Symbol, LvarType> beforeRepeatTypes = localVariableTypes;
            body.accept(this);
            if(reachable) {
                jumpToLabel(body, continueLabel);
            }
            joinOnLabel(continueLabel);
            if(!reachable) {
                break;
            }
            visitExpressionOnEmptyStack(test);
            jumpToLabel(test, breakLabel);
            if(isAlwaysFalse(test)) {
                break;
            }
            jumpToLabel(test, repeatLabel);
            joinOnLabel(repeatLabel);
            if(localVariableTypes.equals(beforeRepeatTypes)) {
                break;
            }
            resetJoinPoint(continueLabel);
            resetJoinPoint(breakLabel);
            resetJoinPoint(repeatLabel);
        }

        if(isAlwaysTrue(test)) {
            doesNotContinueSequentially();
        }

        leaveBreakable(loopNode);
    }

    @Override
    public boolean enterExpressionStatement(final ExpressionStatement expressionStatement) {
        if (reachable) {
            visitExpressionOnEmptyStack(expressionStatement.getExpression());
        }
        return false;
    }

    private void assertTypeStackIsEmpty() {
        assert typeStack.isEmpty();
    }

    @Override
    protected Node leaveDefault(final Node node) {
        assert !(node instanceof Expression); // All expressions were handled
        assert !(node instanceof Statement) || typeStack.isEmpty(); // No statements leave with a non-empty stack
        return node;
    }

    private LvarType visitExpressionOnEmptyStack(final Expression expr) {
        assertTypeStackIsEmpty();
        return visitExpression(expr);
    }

    private LvarType visitExpression(final Expression expr) {
        final int stackSize = typeStack.size();
        expr.accept(this);
        assert typeStack.size() == stackSize + 1;
        return typeStack.pop();
    }

    private void visitExpressions(final List<Expression> exprs) {
        for(final Expression expr: exprs) {
            if (expr != null) {
                visitExpression(expr);
            }
        }
    }

    @Override
    public boolean enterForNode(final ForNode forNode) {
        if(!reachable) {
            return false;
        }

        final Expression init = forNode.getInit();
        if(forNode.isForIn()) {
            final JoinPredecessorExpression iterable = forNode.getModify();
            visitExpression(iterable);
            enterTestFirstLoop(forNode, null, init,
                    // If we're iterating over property names, and we can discern from the runtime environment
                    // of the compilation that the object being iterated over must use strings for property
                    // names (e.g., it is a native JS object or array), then we'll not bother trying to treat
                    // the property names optimistically.
                    !compiler.useOptimisticTypes() || (!forNode.isForEach() && compiler.hasStringPropertyIterator(iterable.getExpression())));
        } else {
            if(init != null) {
                visitExpressionOnEmptyStack(init);
            }
            enterTestFirstLoop(forNode, forNode.getModify(), null, false);
        }
        assertTypeStackIsEmpty();
        return false;
    }

    @Override
    public boolean enterFunctionNode(final FunctionNode functionNode) {
        if(alreadyEnteredTopLevelFunction) {
            typeStack.push(LvarType.OBJECT);
            return false;
        }
        int pos = 0;
        if(!functionNode.isVarArg()) {
            for (final IdentNode param : functionNode.getParameters()) {
                final Symbol symbol = param.getSymbol();
                // Parameter is not necessarily bytecode local as it can be scoped due to nested context use, but it
                // must have a slot if we aren't in a function with vararg signature.
                assert symbol.hasSlot();
                final Type callSiteParamType = compiler.getParamType(functionNode, pos);
                final LvarType paramType = callSiteParamType == null ? LvarType.OBJECT : toLvarType(callSiteParamType);
                setType(symbol, paramType);
                // Make sure parameter slot for its incoming value is not marked dead. NOTE: this is a heuristic. Right
                // now, CodeGenerator.expandParameters() relies on the fact that every parameter's final slot width will
                // be at least the same as incoming width, therefore even if a parameter is never read, we'll still keep
                // its slot.
                symbolIsUsed(symbol);
                setIdentifierLvarType(param, paramType);
                pos++;
            }
        }
        setCompilerConstantAsObject(functionNode, CompilerConstants.THIS);

        // TODO: coarse-grained. If we wanted to solve it completely precisely,
        // we'd also need to push/pop its type when handling WithNode (so that
        // it can go back to undefined after a 'with' block.
        if(functionNode.hasScopeBlock() || functionNode.needsParentScope()) {
            setCompilerConstantAsObject(functionNode, CompilerConstants.SCOPE);
        }
        if(functionNode.needsCallee()) {
            setCompilerConstantAsObject(functionNode, CompilerConstants.CALLEE);
        }
        if(functionNode.needsArguments()) {
            setCompilerConstantAsObject(functionNode, CompilerConstants.ARGUMENTS);
        }

        alreadyEnteredTopLevelFunction = true;
        return true;
    }

    @Override
    public boolean enterGetSplitState(final GetSplitState getSplitState) {
        return pushExpressionType(getSplitState);
    }

    @Override
    public boolean enterIdentNode(final IdentNode identNode) {
        final Symbol symbol = identNode.getSymbol();
        if(symbol.isBytecodeLocal()) {
            symbolIsUsed(symbol);
            final LvarType type = getLocalVariableType(symbol);
            setIdentifierLvarType(identNode, type);
            typeStack.push(type);
        } else {
            pushExpressionType(identNode);
        }
        return false;
    }

    @Override
    public boolean enterIfNode(final IfNode ifNode) {
        processIfNode(ifNode);
        return false;
    }

    private void processIfNode(final IfNode ifNode) {
        if(!reachable) {
            return;
        }

        final Expression test = ifNode.getTest();
        final Block pass = ifNode.getPass();
        final Block fail = ifNode.getFail();

        visitExpressionOnEmptyStack(test);

        final Map<Symbol, LvarType> passLvarTypes;
        final boolean reachableFromPass;
        final boolean isTestAlwaysTrue = isAlwaysTrue(test);
        if(isAlwaysFalse(test)) {
            passLvarTypes = null;
            reachableFromPass = false;
        } else {
            final Map<Symbol, LvarType> afterTestLvarTypes = localVariableTypes;
            pass.accept(this);
            assertTypeStackIsEmpty();
            if (isTestAlwaysTrue) {
                return;
            }
            passLvarTypes = localVariableTypes;
            reachableFromPass = reachable;
            localVariableTypes = afterTestLvarTypes;
            reachable = true;
        }

        // If we get here, then we need to consider the case where pass block is not executed
        assert !isTestAlwaysTrue;

        if (fail != null) {
            fail.accept(this);
            assertTypeStackIsEmpty();
        }

        if(reachable) {
            if(reachableFromPass) {
                final Map<Symbol, LvarType> failLvarTypes = localVariableTypes;
                localVariableTypes = getUnionTypes(passLvarTypes, failLvarTypes);
                setConversion(pass, passLvarTypes, localVariableTypes);
                // IfNode itself is associated with conversions that might need to be performed after the test if
                // there's no else branch. E.g.
                // if(x = 1, cond) { x = 1.0 } must widen "x = 1" to a double.
                setConversion(fail != null ? fail : ifNode, failLvarTypes, localVariableTypes);
            }
        } else if (reachableFromPass) {
            assert passLvarTypes != null;
            localVariableTypes = passLvarTypes;
            reachable = true;
        }
    }

    @Override
    public boolean enterIndexNode(final IndexNode indexNode) {
        visitExpression(indexNode.getBase());
        visitExpression(indexNode.getIndex());
        return pushExpressionType(indexNode);
    }

    @Override
    public boolean enterJoinPredecessorExpression(final JoinPredecessorExpression joinExpr) {
        final Expression expr = joinExpr.getExpression();
        if (expr != null) {
            expr.accept(this);
        } else {
            typeStack.push(LvarType.UNDEFINED);
        }
        return false;
    }

    @Override
    public boolean enterJumpToInlinedFinally(final JumpToInlinedFinally jumpToInlinedFinally) {
        return enterJumpStatement(jumpToInlinedFinally);
    }

    @Override
    public boolean enterLiteralNode(final LiteralNode<?> literalNode) {
        if (literalNode instanceof ArrayLiteralNode) {
            final List<Expression> expressions = ((ArrayLiteralNode)literalNode).getElementExpressions();
            if (expressions != null) {
                visitExpressions(expressions);
            }
        }
        pushExpressionType(literalNode);
        return false;
    }

    @Override
    public boolean enterObjectNode(final ObjectNode objectNode) {
        for(final PropertyNode propertyNode: objectNode.getElements()) {
            // Avoid falsely adding property keys to the control flow graph
            final Expression value = propertyNode.getValue();
            if (value != null) {
                visitExpression(value);
            }
        }
        return pushExpressionType(objectNode);
    }

    @Override
    public boolean enterPropertyNode(final PropertyNode propertyNode) {
        // Property nodes are only accessible through object literals, and we handled that case above
        throw new AssertionError();
    }

    @Override
    public boolean enterReturnNode(final ReturnNode returnNode) {
        if(!reachable) {
            return false;
        }

        final Expression returnExpr = returnNode.getExpression();
        final Type returnExprType;
        if(returnExpr != null) {
            returnExprType = visitExpressionOnEmptyStack(returnExpr).type;
        } else {
            assertTypeStackIsEmpty();
            returnExprType = Type.UNDEFINED;
        }
        returnType = Type.widestReturnType(returnType, returnExprType);
        doesNotContinueSequentially();
        return false;
    }

    @Override
    public boolean enterRuntimeNode(final RuntimeNode runtimeNode) {
        visitExpressions(runtimeNode.getArgs());
        return pushExpressionType(runtimeNode);
    }

    @Override
    public boolean enterSplitReturn(final SplitReturn splitReturn) {
        doesNotContinueSequentially();
        return false;
    }

    @Override
    public boolean enterSwitchNode(final SwitchNode switchNode) {
        if(!reachable) {
            return false;
        }

        visitExpressionOnEmptyStack(switchNode.getExpression());

        final List<CaseNode> cases = switchNode.getCases();
        if(cases.isEmpty()) {
            return false;
        }

        // Control flow is different for all-integer cases where we dispatch by switch table, and for all other cases
        // where we do sequential comparison. Note that CaseNode objects act as join points.
        final boolean isInteger = switchNode.isUniqueInteger();
        final Label breakLabel = switchNode.getBreakLabel();
        final boolean hasDefault = switchNode.getDefaultCase() != null;

        boolean tagUsed = false;
        for(final CaseNode caseNode: cases) {
            final Expression test = caseNode.getTest();
            if(!isInteger && test != null) {
                visitExpressionOnEmptyStack(test);
                if(!tagUsed) {
                    symbolIsUsed(switchNode.getTag(), LvarType.OBJECT);
                    tagUsed = true;
                }
            }
            // CaseNode carries the conversions that need to be performed on its entry from the test.
            // CodeGenerator ensures these are only emitted when arriving on the branch and not through a
            // fallthrough.
            jumpToLabel(caseNode, caseNode.getBody().getEntryLabel());
        }
        if(!hasDefault) {
            // No default case means we can arrive at the break label without entering any cases. In that case
            // SwitchNode will carry the conversions that need to be performed before it does that jump.
            jumpToLabel(switchNode, breakLabel);
        }

        // All cases are arrived at through jumps
        doesNotContinueSequentially();

        Block previousBlock = null;
        for(final CaseNode caseNode: cases) {
            final Block body = caseNode.getBody();
            final Label entryLabel = body.getEntryLabel();
            if(previousBlock != null && reachable) {
                jumpToLabel(previousBlock, entryLabel);
            }
            joinOnLabel(entryLabel);
            assert reachable == true;
            body.accept(this);
            previousBlock = body;
        }
        if(previousBlock != null && reachable) {
            jumpToLabel(previousBlock, breakLabel);
        }
        leaveBreakable(switchNode);
        return false;
    }

    @Override
    public boolean enterTernaryNode(final TernaryNode ternaryNode) {
        final Expression test = ternaryNode.getTest();
        final Expression trueExpr = ternaryNode.getTrueExpression();
        final Expression falseExpr = ternaryNode.getFalseExpression();

        visitExpression(test);

        final Map<Symbol, LvarType> testExitLvarTypes = localVariableTypes;
        final LvarType trueType;
        if(!isAlwaysFalse(test)) {
            trueType = visitExpression(trueExpr);
        } else {
            trueType = null;
        }
        final Map<Symbol, LvarType> trueExitLvarTypes = localVariableTypes;
        localVariableTypes = testExitLvarTypes;
        final LvarType falseType;
        if(!isAlwaysTrue(test)) {
            falseType = visitExpression(falseExpr);
        } else {
            falseType = null;
        }
        final Map<Symbol, LvarType> falseExitLvarTypes = localVariableTypes;
        localVariableTypes = getUnionTypes(trueExitLvarTypes, falseExitLvarTypes);
        setConversion((JoinPredecessor)trueExpr, trueExitLvarTypes, localVariableTypes);
        setConversion((JoinPredecessor)falseExpr, falseExitLvarTypes, localVariableTypes);

        typeStack.push(trueType != null ? falseType != null ? widestLvarType(trueType, falseType) : trueType : assertNotNull(falseType));
        return false;
    }

    private static <T> T assertNotNull(final T t) {
        assert t != null;
        return t;
    }

    private void enterTestFirstLoop(final LoopNode loopNode, final JoinPredecessorExpression modify,
            final Expression iteratorValues, final boolean iteratorValuesAreObject) {
        final JoinPredecessorExpression test = loopNode.getTest();
        if(isAlwaysFalse(test)) {
            visitExpressionOnEmptyStack(test);
            return;
        }

        final Label continueLabel = loopNode.getContinueLabel();
        final Label breakLabel = loopNode.getBreakLabel();

        final Label repeatLabel = modify == null ? continueLabel : new Label("");
        final Map<Symbol, LvarType> beforeLoopTypes = localVariableTypes;
        for(;;) {
            jumpToLabel(loopNode, repeatLabel, beforeLoopTypes);
            final Map<Symbol, LvarType> beforeRepeatTypes = localVariableTypes;
            if(test != null) {
                visitExpressionOnEmptyStack(test);
            }
            if(!isAlwaysTrue(test)) {
                jumpToLabel(test, breakLabel);
            }
            if(iteratorValues instanceof IdentNode) {
                final IdentNode ident = (IdentNode)iteratorValues;
                // Receives iterator values; the optimistic type of the iterator values is tracked on the
                // identifier, but we override optimism if it's known that the object being iterated over will
                // never have primitive property names.
                onAssignment(ident, iteratorValuesAreObject ? LvarType.OBJECT :
                    toLvarType(compiler.getOptimisticType(ident)));
            }
            final Block body = loopNode.getBody();
            body.accept(this);
            if(reachable) {
                jumpToLabel(body, continueLabel);
            }
            joinOnLabel(continueLabel);
            if(!reachable) {
                break;
            }
            if(modify != null) {
                visitExpressionOnEmptyStack(modify);
                jumpToLabel(modify, repeatLabel);
                joinOnLabel(repeatLabel);
            }
            if(localVariableTypes.equals(beforeRepeatTypes)) {
                break;
            }
            // Reset the join points and repeat the analysis
            resetJoinPoint(continueLabel);
            resetJoinPoint(breakLabel);
            resetJoinPoint(repeatLabel);
        }

        if(isAlwaysTrue(test) && iteratorValues == null) {
            doesNotContinueSequentially();
        }

        leaveBreakable(loopNode);
    }

    @Override
    public boolean enterThrowNode(final ThrowNode throwNode) {
        if(!reachable) {
            return false;
        }

        visitExpressionOnEmptyStack(throwNode.getExpression());
        jumpToCatchBlock(throwNode);
        doesNotContinueSequentially();
        return false;
    }

    @Override
    public boolean enterTryNode(final TryNode tryNode) {
        if(!reachable) {
            return false;
        }

        // This is the label for the join point at the entry of the catch blocks.
        final Label catchLabel = new Label("");
        catchLabels.push(catchLabel);

        // Presume that even the start of the try block can immediately go to the catch
        jumpToLabel(tryNode, catchLabel);

        final Block body = tryNode.getBody();
        body.accept(this);
        catchLabels.pop();

        // Final exit label for the whole try/catch construct (after the try block and after all catches).
        final Label endLabel = new Label("");

        boolean canExit = false;
        if(reachable) {
            jumpToLabel(body, endLabel);
            canExit = true;
        }
        doesNotContinueSequentially();

        for (final Block inlinedFinally : tryNode.getInlinedFinallies()) {
            final Block finallyBody = TryNode.getLabelledInlinedFinallyBlock(inlinedFinally);
            joinOnLabel(finallyBody.getEntryLabel());
            // NOTE: the jump to inlined finally can end up in dead code, so it is not necessarily reachable.
            if (reachable) {
                finallyBody.accept(this);
                // All inlined finallies end with a jump or a return
                assert !reachable;
            }
        }

        joinOnLabel(catchLabel);
        for(final CatchNode catchNode: tryNode.getCatches()) {
            final IdentNode exception = catchNode.getException();
            onAssignment(exception, LvarType.OBJECT);
            final Expression condition = catchNode.getExceptionCondition();
            if(condition != null) {
                visitExpression(condition);
            }
            final Map<Symbol, LvarType> afterConditionTypes = localVariableTypes;
            final Block catchBody = catchNode.getBody();
            // TODO: currently, we consider that the catch blocks are always reachable from the try block as currently
            // we lack enough analysis to prove that no statement before a break/continue/return in the try block can
            // throw an exception.
            reachable = true;
            catchBody.accept(this);
            if(reachable) {
                jumpToLabel(catchBody, endLabel);
                canExit = true;
            }
            localVariableTypes = afterConditionTypes;
        }
        // NOTE: if we had one or more conditional catch blocks with no unconditional catch block following them, then
        // there will be an unconditional rethrow, so the join point can never be reached from the last
        // conditionExpression.
        doesNotContinueSequentially();

        if(canExit) {
            joinOnLabel(endLabel);
        }

        return false;
    }


    @Override
    public boolean enterUnaryNode(final UnaryNode unaryNode) {
        final Expression expr = unaryNode.getExpression();
        final LvarType unaryType = toLvarType(unaryNode.setExpression(visitExpression(expr).typeExpression).getType());
        if(unaryNode.isSelfModifying() && expr instanceof IdentNode) {
            onSelfAssignment((IdentNode)expr, unaryType);
        }
        typeStack.push(unaryType);
        return false;
    }

    @Override
    public boolean enterVarNode(final VarNode varNode) {
        if (!reachable) {
            return false;
        }
        final Expression init = varNode.getInit();
        if(init != null) {
            onAssignment(varNode.getName(), visitExpression(init));
        }
        return false;
    }

    @Override
    public boolean enterWhileNode(final WhileNode whileNode) {
        if(!reachable) {
            return false;
        }
        if(whileNode.isDoWhile()) {
            enterDoWhileLoop(whileNode);
        } else {
            enterTestFirstLoop(whileNode, null, null, false);
        }
        return false;
    }

    @Override
    public boolean enterWithNode(final WithNode withNode) {
        if (reachable) {
            visitExpression(withNode.getExpression());
            withNode.getBody().accept(this);
        }
        return false;
    };

    private Map<Symbol, LvarType> getBreakTargetTypes(final LexicalContextNode target) {
        // Remove symbols defined in the the blocks that are being broken out of.
        Map<Symbol, LvarType> types = localVariableTypes;
        for(final Iterator<LexicalContextNode> it = lc.getAllNodes(); it.hasNext();) {
            final LexicalContextNode node = it.next();
            if(node instanceof Block) {
                for(final Symbol symbol: ((Block)node).getSymbols()) {
                    if(localVariableTypes.containsKey(symbol)) {
                        if(types == localVariableTypes) {
                            types = cloneMap(localVariableTypes);
                        }
                        types.remove(symbol);
                    }
                }
            }
            if(node == target) {
                break;
            }
        }
        return types;
    }

    /**
     * Returns the current type of the local variable represented by the symbol. This is the most strict of all
     * {@code getLocalVariableType*} methods, as it will throw an assertion if the type is null. Therefore, it is only
     * safe to be invoked on symbols known to be bytecode locals, and only after they have been initialized.
     * Regardless, it is recommended to use this method in majority of cases, as because of its strictness it is the
     * best suited for catching missing type calculation bugs early.
     * @param symbol a symbol representing a bytecode local variable.
     * @return the current type of the local variable represented by the symbol
     */
    private LvarType getLocalVariableType(final Symbol symbol) {
        final LvarType type = getLocalVariableTypeOrNull(symbol);
        assert type != null;
        return type;
    }

    /**
     * Gets the type for a variable represented by a symbol, or null if the type is not know. This is the least strict
     * of all local variable type getters, and as such its use is discouraged except in initialization scenarios (where
     * a just-defined symbol might still be null).
     * @param symbol the symbol
     * @return the current type for the symbol, or null if the type is not known either because the symbol has not been
     * initialized, or because the symbol does not represent a bytecode local variable.
     */
    private LvarType getLocalVariableTypeOrNull(final Symbol symbol) {
        return localVariableTypes.get(symbol);
    }

    private JumpTarget getOrCreateJumpTarget(final Label label) {
        JumpTarget jumpTarget = jumpTargets.get(label);
        if(jumpTarget == null) {
            jumpTarget = createJumpTarget(label);
        }
        return jumpTarget;
    }


    /**
     * If there's a join point associated with a label, insert the join point into the flow.
     * @param label the label to insert a join point for.
     */
    private void joinOnLabel(final Label label) {
        final JumpTarget jumpTarget = jumpTargets.remove(label);
        if(jumpTarget == null) {
            return;
        }
        assert !jumpTarget.origins.isEmpty();
        reachable = true;
        localVariableTypes = getUnionTypes(jumpTarget.types, localVariableTypes);
        for(final JumpOrigin jumpOrigin: jumpTarget.origins) {
            setConversion(jumpOrigin.node, jumpOrigin.types, localVariableTypes);
        }
    }

    /**
     * If we're in a try/catch block, add an edge from the specified node to the try node's pre-catch label.
     */
    private void jumpToCatchBlock(final JoinPredecessor jumpOrigin) {
        final Label currentCatchLabel = catchLabels.peek();
        if(currentCatchLabel != null) {
            jumpToLabel(jumpOrigin, currentCatchLabel);
        }
    }

    private void jumpToLabel(final JoinPredecessor jumpOrigin, final Label label) {
        jumpToLabel(jumpOrigin, label, localVariableTypes);
    }

    private void jumpToLabel(final JoinPredecessor jumpOrigin, final Label label, final Map<Symbol, LvarType> types) {
        getOrCreateJumpTarget(label).addOrigin(jumpOrigin, types, this);
    }

    @Override
    public Node leaveBlock(final Block block) {
        if(lc.isFunctionBody()) {
            if(reachable) {
                // reachable==true means we can reach the end of the function without an explicit return statement. We
                // need to insert a synthetic one then. This logic used to be in Lower.leaveBlock(), but Lower's
                // reachability analysis (through Terminal.isTerminal() flags) is not precise enough so
                // Lower$BlockLexicalContext.afterSetStatements will sometimes think the control flow terminates even
                // when it didn't. Example: function() { switch((z)) { default: {break; } throw x; } }.
                createSyntheticReturn(block);
                assert !reachable;
            }
            // We must calculate the return type here (and not in leaveFunctionNode) as it can affect the liveness of
            // the :return symbol and thus affect conversion type liveness calculations for it.
            calculateReturnType();
        }

        boolean cloned = false;
        for(final Symbol symbol: block.getSymbols()) {
            if(symbol.hasSlot()) {
                // Invalidate the symbol when its defining block ends
                if (symbol.isBytecodeLocal()) {
                    if(localVariableTypes.containsKey(symbol)) {
                        if(!cloned) {
                            localVariableTypes = cloneMap(localVariableTypes);
                            cloned = true;
                        }
                    }
                    invalidateSymbol(symbol);
                }

                final SymbolConversions conversions = symbolConversions.get(symbol);
                if(conversions != null) {
                    // Potentially make some currently dead types live if they're needed as a source of a type
                    // conversion at a join.
                    conversions.calculateTypeLiveness(symbol);
                }
                if(symbol.slotCount() == 0) {
                    // This is a local variable that is never read. It won't need a slot.
                    symbol.setNeedsSlot(false);
                }
            }
        }

        if(reachable) {
            // TODO: this is totally backwards. Block should not be breakable, LabelNode should be breakable.
            final LabelNode labelNode = lc.getCurrentBlockLabelNode();
            if(labelNode != null) {
                jumpToLabel(labelNode, block.getBreakLabel());
            }
        }
        leaveBreakable(block);
        return block;
    }

    private void calculateReturnType() {
        // NOTE: if return type is unknown, then the function does not explicitly return a value. Such a function under
        // ECMAScript rules returns Undefined, which has Type.OBJECT. We might consider an optimization in the future
        // where we can return void functions.
        if(returnType.isUnknown()) {
            returnType = Type.OBJECT;
        }
    }

    private void createSyntheticReturn(final Block body) {
        final FunctionNode functionNode = lc.getCurrentFunction();
        final long token = functionNode.getToken();
        final int finish = functionNode.getFinish();
        final List<Statement> statements = body.getStatements();
        final int lineNumber = statements.isEmpty() ? functionNode.getLineNumber() : statements.get(statements.size() - 1).getLineNumber();
        final IdentNode returnExpr;
        if(functionNode.isProgram()) {
            returnExpr = new IdentNode(token, finish, RETURN.symbolName()).setSymbol(getCompilerConstantSymbol(functionNode, RETURN));
        } else {
            returnExpr = null;
        }
        syntheticReturn = new ReturnNode(lineNumber, token, finish, returnExpr);
        syntheticReturn.accept(this);
    }

    /**
     * Leave a breakable node. If there's a join point associated with its break label (meaning there was at least one
     * break statement to the end of the node), insert the join point into the flow.
     * @param breakable the breakable node being left.
     */
    private void leaveBreakable(final BreakableNode breakable) {
        joinOnLabel(breakable.getBreakLabel());
        assertTypeStackIsEmpty();
    }

    @Override
    public Node leaveFunctionNode(final FunctionNode functionNode) {
        // Sets the return type of the function and also performs the bottom-up pass of applying type and conversion
        // information to nodes as well as doing the calculation on nested functions as required.
        FunctionNode newFunction = functionNode;
        final SimpleNodeVisitor applyChangesVisitor = new SimpleNodeVisitor() {
            private boolean inOuterFunction = true;
            private final Deque<JoinPredecessor> joinPredecessors = new ArrayDeque<>();

            @Override
            protected boolean enterDefault(final Node node) {
                if(!inOuterFunction) {
                    return false;
                }
                if(node instanceof JoinPredecessor) {
                    joinPredecessors.push((JoinPredecessor)node);
                }
                return inOuterFunction;
            }

            @Override
            public boolean enterFunctionNode(final FunctionNode fn) {
                if(compiler.isOnDemandCompilation()) {
                    // Only calculate nested function local variable types if we're doing eager compilation
                    return false;
                }
                inOuterFunction = false;
                return true;
            }

            @SuppressWarnings("fallthrough")
            @Override
            public Node leaveBinaryNode(final BinaryNode binaryNode) {
                if(binaryNode.isComparison()) {
                    final Expression lhs = binaryNode.lhs();
                    final Expression rhs = binaryNode.rhs();

                    final TokenType tt = binaryNode.tokenType();
                    switch (tt) {
                    case EQ_STRICT:
                    case NE_STRICT:
                        // Specialize comparison with undefined
                        final Expression undefinedNode = createIsUndefined(binaryNode, lhs, rhs,
                                tt == TokenType.EQ_STRICT ? Request.IS_UNDEFINED : Request.IS_NOT_UNDEFINED);
                        if(undefinedNode != binaryNode) {
                            return undefinedNode;
                        }
                        // Specialize comparison of boolean with non-boolean
                        if (lhs.getType().isBoolean() != rhs.getType().isBoolean()) {
                            return new RuntimeNode(binaryNode);
                        }
                        // fallthrough
                    default:
                        if (lhs.getType().isObject() && rhs.getType().isObject()) {
                            return new RuntimeNode(binaryNode);
                        }
                    }
                } else if(binaryNode.isOptimisticUndecidedType()) {
                    // At this point, we can assign a static type to the optimistic binary ADD operator as now we know
                    // the types of its operands.
                    return binaryNode.decideType();
                }
                return binaryNode;
            }

            @Override
            protected Node leaveDefault(final Node node) {
                if(node instanceof JoinPredecessor) {
                    final JoinPredecessor original = joinPredecessors.pop();
                    assert original.getClass() == node.getClass() : original.getClass().getName() + "!=" + node.getClass().getName();
                    final JoinPredecessor newNode = setLocalVariableConversion(original, (JoinPredecessor)node);
                    if (newNode instanceof LexicalContextNode) {
                        lc.replace((LexicalContextNode)node, (LexicalContextNode)newNode);
                    }
                    return (Node)newNode;
                }
                return node;
            }

            @Override
            public Node leaveBlock(final Block block) {
                if(inOuterFunction && syntheticReturn != null && lc.isFunctionBody()) {
                    final ArrayList<Statement> stmts = new ArrayList<>(block.getStatements());
                    stmts.add((ReturnNode)syntheticReturn.accept(this));
                    return block.setStatements(lc, stmts);
                }
                return super.leaveBlock(block);
            }

            @Override
            public Node leaveFunctionNode(final FunctionNode nestedFunctionNode) {
                inOuterFunction = true;
                final FunctionNode newNestedFunction = (FunctionNode)nestedFunctionNode.accept(
                        new LocalVariableTypesCalculator(compiler));
                lc.replace(nestedFunctionNode, newNestedFunction);
                return newNestedFunction;
            }

            @Override
            public Node leaveIdentNode(final IdentNode identNode) {
                final IdentNode original = (IdentNode)joinPredecessors.pop();
                final Symbol symbol = identNode.getSymbol();
                if(symbol == null) {
                    assert identNode.isPropertyName();
                    return identNode;
                } else if(symbol.hasSlot()) {
                    assert !symbol.isScope() || symbol.isParam(); // Only params can be slotted and scoped.
                    assert original.getName().equals(identNode.getName());
                    final LvarType lvarType = identifierLvarTypes.remove(original);
                    if(lvarType != null) {
                        return setLocalVariableConversion(original, identNode.setType(lvarType.type));
                    }
                    // If there's no type, then the identifier must've been in unreachable code. In that case, it can't
                    // have assigned conversions either.
                    assert localVariableConversions.get(original) == null;
                } else {
                    assert identIsDeadAndHasNoLiveConversions(original);
                }
                return identNode;
            }

            @Override
            public Node leaveLiteralNode(final LiteralNode<?> literalNode) {
                //for e.g. ArrayLiteralNodes the initial types may have been narrowed due to the
                //introduction of optimistic behavior - hence ensure that all literal nodes are
                //reinitialized
                return literalNode.initialize(lc);
            }

            @Override
            public Node leaveRuntimeNode(final RuntimeNode runtimeNode) {
                final Request request = runtimeNode.getRequest();
                final boolean isEqStrict = request == Request.EQ_STRICT;
                if(isEqStrict || request == Request.NE_STRICT) {
                    return createIsUndefined(runtimeNode, runtimeNode.getArgs().get(0), runtimeNode.getArgs().get(1),
                            isEqStrict ? Request.IS_UNDEFINED : Request.IS_NOT_UNDEFINED);
                }
                return runtimeNode;
            }

            @SuppressWarnings("unchecked")
            private <T extends JoinPredecessor> T setLocalVariableConversion(final JoinPredecessor original, final T jp) {
                // NOTE: can't use Map.remove() as our copy-on-write AST semantics means some nodes appear twice (in
                // finally blocks), so we need to be able to access conversions for them multiple times.
                return (T)jp.setLocalVariableConversion(lc, localVariableConversions.get(original));
            }
        };

        newFunction = newFunction.setBody(lc, (Block)newFunction.getBody().accept(applyChangesVisitor));
        newFunction = newFunction.setReturnType(lc, returnType);


        newFunction = newFunction.setParameters(lc, newFunction.visitParameters(applyChangesVisitor));
        return newFunction;
    }

    private static Expression createIsUndefined(final Expression parent, final Expression lhs, final Expression rhs, final Request request) {
        if (isUndefinedIdent(lhs) || isUndefinedIdent(rhs)) {
            return new RuntimeNode(parent, request, lhs, rhs);
        }
        return parent;
    }

    private static boolean isUndefinedIdent(final Expression expr) {
        return expr instanceof IdentNode && "undefined".equals(((IdentNode)expr).getName());
    }

    private boolean identIsDeadAndHasNoLiveConversions(final IdentNode identNode) {
        final LocalVariableConversion conv = localVariableConversions.get(identNode);
        return conv == null || !conv.isLive();
    }

    private void onAssignment(final IdentNode identNode, final LvarType type) {
        final Symbol symbol = identNode.getSymbol();
        assert symbol != null : identNode.getName();
        if(!symbol.isBytecodeLocal()) {
            return;
        }
        assert type != null;
        final LvarType finalType;
        if(type == LvarType.UNDEFINED && getLocalVariableType(symbol) != LvarType.UNDEFINED) {
            // Explicit assignment of a known undefined local variable to a local variable that is not undefined will
            // materialize that undefined in the assignment target. Note that assigning known undefined to known
            // undefined will *not* initialize the variable, e.g. "var x; var y = x;" compiles to no-op.
            finalType = LvarType.OBJECT;
            symbol.setFlag(Symbol.HAS_OBJECT_VALUE);
        } else {
            finalType = type;
        }
        setType(symbol, finalType);
        // Explicit assignment of an undefined value. Make sure the variable can store an object
        // TODO: if we communicated the fact to codegen with a flag on the IdentNode that the value was already
        // undefined before the assignment, we could just ignore it. In general, we could ignore an assignment if we
        // know that the value assigned is the same as the current value of the variable, but we'd need constant
        // propagation for that.
        setIdentifierLvarType(identNode, finalType);
        // For purposes of type calculation, we consider an assignment to a local variable to be followed by
        // the catch nodes of the current (if any) try block. This will effectively enforce that narrower
        // assignments to a local variable in a try block will also have to store a widened value as well. Code
        // within the try block will be able to keep loading the narrower value, but after the try block only
        // the widest value will remain live.
        // Rationale for this is that if there's an use for that variable in any of the catch blocks, or
        // following the catch blocks, they must use the widest type.
        // Example:
        /*
            Originally:
            ===========
            var x;
            try {
              x = 1; <-- stores into int slot for x
              f(x); <-- loads the int slot for x
              x = 3.14 <-- stores into the double slot for x
              f(x); <-- loads the double slot for x
              x = 1; <-- stores into int slot for x
              f(x); <-- loads the int slot for x
            } finally {
              f(x); <-- loads the double slot for x, but can be reached by a path where x is int, so we need
                           to go back and ensure that double values are also always stored along with int
                           values.
            }

            After correction:
            =================

            var x;
            try {
              x = 1; <-- stores into both int and double slots for x
              f(x); <-- loads the int slot for x
              x = 3.14 <-- stores into the double slot for x
              f(x); <-- loads the double slot for x
              x = 1; <-- stores into both int and double slots for x
              f(x); <-- loads the int slot for x
            } finally {
              f(x); <-- loads the double slot for x
            }
         */
        jumpToCatchBlock(identNode);
    }

    private void onSelfAssignment(final IdentNode identNode, final LvarType type) {
        final Symbol symbol = identNode.getSymbol();
        assert symbol != null : identNode.getName();
        if(!symbol.isBytecodeLocal()) {
            return;
        }
        // Self-assignment never produce either a boolean or undefined
        assert type != null && type != LvarType.UNDEFINED && type != LvarType.BOOLEAN;
        setType(symbol, type);
        jumpToCatchBlock(identNode);
    }

    private void resetJoinPoint(final Label label) {
        jumpTargets.remove(label);
    }

    private void setCompilerConstantAsObject(final FunctionNode functionNode, final CompilerConstants cc) {
        final Symbol symbol = getCompilerConstantSymbol(functionNode, cc);
        setType(symbol, LvarType.OBJECT);
        // never mark compiler constants as dead
        symbolIsUsed(symbol);
    }

    private static Symbol getCompilerConstantSymbol(final FunctionNode functionNode, final CompilerConstants cc) {
        return functionNode.getBody().getExistingSymbol(cc.symbolName());
    }

    private void setConversion(final JoinPredecessor node, final Map<Symbol, LvarType> branchLvarTypes, final Map<Symbol, LvarType> joinLvarTypes) {
        if(node == null) {
            return;
        }
        if(branchLvarTypes.isEmpty() || joinLvarTypes.isEmpty()) {
            localVariableConversions.remove(node);
        }

        LocalVariableConversion conversion = null;
        if(node instanceof IdentNode) {
            // conversions on variable assignment in try block are special cases, as they only apply to the variable
            // being assigned and all other conversions should be ignored.
            final Symbol symbol = ((IdentNode)node).getSymbol();
            conversion = createConversion(symbol, branchLvarTypes.get(symbol), joinLvarTypes, null);
        } else {
            for(final Map.Entry<Symbol, LvarType> entry: branchLvarTypes.entrySet()) {
                final Symbol symbol = entry.getKey();
                final LvarType branchLvarType = entry.getValue();
                conversion = createConversion(symbol, branchLvarType, joinLvarTypes, conversion);
            }
        }
        if(conversion != null) {
            localVariableConversions.put(node, conversion);
        } else {
            localVariableConversions.remove(node);
        }
    }

    private void setIdentifierLvarType(final IdentNode identNode, final LvarType type) {
        assert type != null;
        identifierLvarTypes.put(identNode, type);
    }

    /**
     * Marks a local variable as having a specific type from this point onward. Invoked by stores to local variables.
     * @param symbol the symbol representing the variable
     * @param type the type
     */
    private void setType(final Symbol symbol, final LvarType type) {
        if(getLocalVariableTypeOrNull(symbol) == type) {
            return;
        }
        assert symbol.hasSlot();
        assert !symbol.isGlobal();
        cloneOrNewLocalVariableTypes();
        localVariableTypes.put(symbol, type);
    }

    private void cloneOrNewLocalVariableTypes() {
        localVariableTypes = localVariableTypes.isEmpty() ? new HashMap<Symbol, LvarType>() : cloneMap(localVariableTypes);
    }

    private void invalidateSymbol(final Symbol symbol) {
        localVariableTypes.remove(symbol);
        invalidatedSymbols.add(symbol);
    }

    /**
     * Set a flag in the symbol marking it as needing to be able to store a value of a particular type. Every symbol for
     * a local variable will be assigned between 1 and 6 local variable slots for storing all types it is known to need
     * to store.
     * @param symbol the symbol
     */
    private void symbolIsUsed(final Symbol symbol) {
        symbolIsUsed(symbol, getLocalVariableType(symbol));
    }
}