internal/ir/LexicalContext.java

/*
 * Copyright (c) 2010, 2015, 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.ir;

import java.io.File;
import java.util.Iterator;
import java.util.NoSuchElementException;
import jdk.nashorn.internal.runtime.Debug;
import jdk.nashorn.internal.runtime.Source;

/**
 * A class that tracks the current lexical context of node visitation as a stack
 * of {@link Block} nodes. Has special methods to retrieve useful subsets of the
 * context.
 *
 * This is implemented with a primitive array and a stack pointer, because it
 * really makes a difference performance-wise. None of the collection classes
 * were optimal.
 */
public class LexicalContext {
    private LexicalContextNode[] stack;

    private int[] flags;
    private int sp;

    /**
     * Creates a new empty lexical context.
     */
    public LexicalContext() {
        stack = new LexicalContextNode[16];
        flags = new int[16];
    }

    /**
     * Set the flags for a lexical context node on the stack. Does not
     * replace the flags, but rather adds to them.
     *
     * @param node  node
     * @param flag  new flag to set
     */
    public void setFlag(final LexicalContextNode node, final int flag) {
        if (flag != 0) {
            // Use setBlockNeedsScope() instead
            assert !(flag == Block.NEEDS_SCOPE && node instanceof Block);

            for (int i = sp - 1; i >= 0; i--) {
                if (stack[i] == node) {
                    flags[i] |= flag;
                    return;
                }
            }
        }
        assert false;
    }

    /**
     * Marks the block as one that creates a scope. Note that this method must
     * be used instead of {@link #setFlag(LexicalContextNode, int)} with
     * {@link Block#NEEDS_SCOPE} because it atomically also sets the
     * {@link FunctionNode#HAS_SCOPE_BLOCK} flag on the block's containing
     * function.
     *
     * @param block the block that needs to be marked as creating a scope.
     */
    public void setBlockNeedsScope(final Block block) {
        for (int i = sp - 1; i >= 0; i--) {
            if (stack[i] == block) {
                flags[i] |= Block.NEEDS_SCOPE;
                for(int j = i - 1; j >=0; j --) {
                    if(stack[j] instanceof FunctionNode) {
                        flags[j] |= FunctionNode.HAS_SCOPE_BLOCK;
                        return;
                    }
                }
            }
        }
        assert false;
    }

    /**
     * Get the flags for a lexical context node on the stack.
     *
     * @param node node
     *
     * @return the flags for the node
     */
    public int getFlags(final LexicalContextNode node) {
        for (int i = sp - 1; i >= 0; i--) {
            if (stack[i] == node) {
                return flags[i];
            }
        }
        throw new AssertionError("flag node not on context stack");
    }

    /**
     * Get the function body of a function node on the lexical context
     * stack. This will trigger an assertion if node isn't present.
     *
     * @param functionNode function node
     *
     * @return body of function node
     */
    public Block getFunctionBody(final FunctionNode functionNode) {
        for (int i = sp - 1; i >= 0 ; i--) {
            if (stack[i] == functionNode) {
                return (Block)stack[i + 1];
            }
        }
        throw new AssertionError(functionNode.getName() + " not on context stack");
    }

    /**
     * @return all nodes in the LexicalContext.
     */
    public Iterator<LexicalContextNode> getAllNodes() {
        return new NodeIterator<>(LexicalContextNode.class);
    }

    /**
     * Returns the outermost function in this context. It is either the program,
     * or a lazily compiled function.
     *
     * @return the outermost function in this context.
     */
    public FunctionNode getOutermostFunction() {
        return (FunctionNode)stack[0];
    }

    /**
     * Pushes a new block on top of the context, making it the innermost open
     * block.
     *
     * @param <T> the type of the new node
     * @param node the new node
     *
     * @return the node that was pushed
     */
    public <T extends LexicalContextNode> T push(final T node) {
        assert !contains(node);
        if (sp == stack.length) {
            final LexicalContextNode[] newStack = new LexicalContextNode[sp * 2];
            System.arraycopy(stack, 0, newStack, 0, sp);
            stack = newStack;

            final int[] newFlags = new int[sp * 2];
            System.arraycopy(flags, 0, newFlags, 0, sp);
            flags = newFlags;

        }
        stack[sp] = node;
        flags[sp] = 0;

        sp++;

        return node;
    }

    /**
     * Is the context empty?
     *
     * @return {@code true} if empty
     */
    public boolean isEmpty() {
        return sp == 0;
    }

    /**
     * @return the depth of the lexical context.
     */
    public int size() {
        return sp;
    }

    /**
     * Pops the innermost block off the context and all nodes that has been
     * contributed since it was put there.
     *
     * @param <T> the type of the node to be popped
     * @param node the node expected to be popped, used to detect unbalanced
     *        pushes/pops
     *
     * @return the node that was popped
     */
    @SuppressWarnings("unchecked")
    public <T extends Node> T pop(final T node) {
        --sp;
        final LexicalContextNode popped = stack[sp];
        stack[sp] = null;
        if (popped instanceof Flags) {
            return (T)((Flags<?>)popped).setFlag(this, flags[sp]);
        }

        return (T)popped;
    }

    /**
     * Explicitly apply flags to the topmost element on the stack. This is only
     * valid to use from a {@code NodeVisitor.leaveXxx()} method and only on the
     * node being exited at the time. It is not mandatory to use, as
     * {@link #pop(Node)} will apply the flags automatically, but this method
     * can be used to apply them during the {@code leaveXxx()} method in case
     * its logic depends on the value of the flags.
     *
     * @param <T> the type of the node to apply the flags to.
     * @param node the node to apply the flags to. Must be the topmost node on
     *        the stack.
     *
     * @return the passed in node, or a modified node (if any flags were modified)
     */
    public <T extends LexicalContextNode & Flags<T>> T applyTopFlags(final T node) {
        assert node == peek();
        return node.setFlag(this, flags[sp - 1]);
    }

    /**
     * Return the top element in the context.
     *
     * @return the node that was pushed last
     */
    public LexicalContextNode peek() {
        return stack[sp - 1];
    }

    /**
     * Check if a node is in the lexical context.
     *
     * @param node node to check for
     *
     * @return {@code true} if in the context
     */
    public boolean contains(final LexicalContextNode node) {
        for (int i = 0; i < sp; i++) {
            if (stack[i] == node) {
                return true;
            }
        }
        return false;
    }

    /**
     * Replace a node on the lexical context with a new one. Normally
     * you should try to engineer IR traversals so this isn't needed
     *
     * @param oldNode old node
     * @param newNode new node
     *
     * @return the new node
     */
    public LexicalContextNode replace(final LexicalContextNode oldNode, final LexicalContextNode newNode) {
        for (int i = sp - 1; i >= 0; i--) {
            if (stack[i] == oldNode) {
                assert i == sp - 1 : "violation of contract - we always expect to find the replacement node on top of the lexical context stack: " + newNode + " has " + stack[i + 1].getClass() + " above it";
                stack[i] = newNode;
                break;
            }
         }
        return newNode;
    }

    /**
     * Returns an iterator over all blocks in the context, with the top block
     * (innermost lexical context) first.
     *
     * @return an iterator over all blocks in the context.
     */
    public Iterator<Block> getBlocks() {
        return new NodeIterator<>(Block.class);
    }

    /**
     * Returns an iterator over all functions in the context, with the top
     * (innermost open) function first.
     *
     * @return an iterator over all functions in the context.
     */
    public Iterator<FunctionNode> getFunctions() {
        return new NodeIterator<>(FunctionNode.class);
    }

    /**
     * Get the parent block for the current lexical context block
     *
     * @return parent block
     */
    public Block getParentBlock() {
        final Iterator<Block> iter = new NodeIterator<>(Block.class, getCurrentFunction());
        iter.next();
        return iter.hasNext() ? iter.next() : null;
    }

    /**
     * Gets the label node of the current block.
     *
     * @return the label node of the current block, if it is labeled. Otherwise
     *         returns {@code null}.
     */
    public LabelNode getCurrentBlockLabelNode() {
        assert stack[sp - 1] instanceof Block;
        if(sp < 2) {
            return null;
        }
        final LexicalContextNode parent = stack[sp - 2];
        return parent instanceof LabelNode ? (LabelNode)parent : null;
    }

    /**
     * Returns an iterator over all ancestors block of the given block, with its
     * parent block first.
     *
     * @param block the block whose ancestors are returned
     *
     * @return an iterator over all ancestors block of the given block.
     */
    public Iterator<Block> getAncestorBlocks(final Block block) {
        final Iterator<Block> iter = getBlocks();
        while (iter.hasNext()) {
            final Block b = iter.next();
            if (block == b) {
                return iter;
            }
        }
        throw new AssertionError("Block is not on the current lexical context stack");
    }

    /**
     * Returns an iterator over a block and all its ancestors blocks, with the
     * block first.
     *
     * @param block the block that is the starting point of the iteration.
     *
     * @return an iterator over a block and all its ancestors.
     */
    public Iterator<Block> getBlocks(final Block block) {
        final Iterator<Block> iter = getAncestorBlocks(block);
        return new Iterator<Block>() {
            boolean blockReturned = false;
            @Override
            public boolean hasNext() {
                return iter.hasNext() || !blockReturned;
            }
            @Override
            public Block next() {
                if (blockReturned) {
                    return iter.next();
                }
                blockReturned = true;
                return block;
            }
            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }

    /**
     * Get the function for this block.
     *
     * @param block block for which to get function
     *
     * @return function for block
     */
    public FunctionNode getFunction(final Block block) {
        final Iterator<LexicalContextNode> iter = new NodeIterator<>(LexicalContextNode.class);
        while (iter.hasNext()) {
            final LexicalContextNode next = iter.next();
            if (next == block) {
                while (iter.hasNext()) {
                    final LexicalContextNode next2 = iter.next();
                    if (next2 instanceof FunctionNode) {
                        return (FunctionNode)next2;
                    }
                }
            }
        }
        assert false;
        return null;
    }

    /**
     * @return the innermost block in the context.
     */
    public Block getCurrentBlock() {
        return getBlocks().next();
    }

    /**
     * @return the innermost function in the context.
     */
    public FunctionNode getCurrentFunction() {
        for (int i = sp - 1; i >= 0; i--) {
            if (stack[i] instanceof FunctionNode) {
                return (FunctionNode) stack[i];
            }
        }
        return null;
    }

    /**
     * Get the block in which a symbol is defined.
     *
     * @param symbol symbol
     *
     * @return block in which the symbol is defined, assert if no such block in
     *         context.
     */
    public Block getDefiningBlock(final Symbol symbol) {
        final String name = symbol.getName();
        for (final Iterator<Block> it = getBlocks(); it.hasNext();) {
            final Block next = it.next();
            if (next.getExistingSymbol(name) == symbol) {
                return next;
            }
        }
        throw new AssertionError("Couldn't find symbol " + name + " in the context");
    }

    /**
     * Get the function in which a symbol is defined.
     *
     * @param symbol symbol
     *
     * @return function node in which this symbol is defined, assert if no such
     *         symbol exists in context.
     */
    public FunctionNode getDefiningFunction(final Symbol symbol) {
        final String name = symbol.getName();
        for (final Iterator<LexicalContextNode> iter = new NodeIterator<>(LexicalContextNode.class); iter.hasNext();) {
            final LexicalContextNode next = iter.next();
            if (next instanceof Block && ((Block)next).getExistingSymbol(name) == symbol) {
                while (iter.hasNext()) {
                    final LexicalContextNode next2 = iter.next();
                    if (next2 instanceof FunctionNode) {
                        return (FunctionNode)next2;
                    }
                }
                throw new AssertionError("Defining block for symbol " + name + " has no function in the context");
            }
        }
        throw new AssertionError("Couldn't find symbol " + name + " in the context");
    }

    /**
     * Is the topmost lexical context element a function body?
     *
     * @return {@code true} if function body.
     */
    public boolean isFunctionBody() {
        return getParentBlock() == null;
    }

    /**
     * Is the topmost lexical context element body of a SplitNode?
     *
     * @return {@code true} if it's the body of a split node.
     */
    public boolean isSplitBody() {
        return sp >= 2 && stack[sp - 1] instanceof Block && stack[sp - 2] instanceof SplitNode;
    }

    /**
     * Get the parent function for a function in the lexical context.
     *
     * @param functionNode function for which to get parent
     *
     * @return parent function of functionNode or {@code null} if none (e.g., if
     *         functionNode is the program).
     */
    public FunctionNode getParentFunction(final FunctionNode functionNode) {
        final Iterator<FunctionNode> iter = new NodeIterator<>(FunctionNode.class);
        while (iter.hasNext()) {
            final FunctionNode next = iter.next();
            if (next == functionNode) {
                return iter.hasNext() ? iter.next() : null;
            }
        }
        assert false;
        return null;
    }

    /**
     * Count the number of scopes until a given node. Note that this method is
     * solely used to figure out the number of scopes that need to be explicitly
     * popped in order to perform a break or continue jump within the current
     * bytecode method. For this reason, the method returns 0 if it encounters a
     * {@code SplitNode} between the current location and the break/continue
     * target.
     *
     * @param until node to stop counting at. Must be within the current function.
     *
     * @return number of with scopes encountered in the context.
     */
    public int getScopeNestingLevelTo(final LexicalContextNode until) {
        assert until != null;
        //count the number of with nodes until "until" is hit
        int n = 0;
        for (final Iterator<LexicalContextNode> iter = getAllNodes(); iter.hasNext();) {
            final LexicalContextNode node = iter.next();
            if (node == until) {
                break;
            }
            assert !(node instanceof FunctionNode); // Can't go outside current function
            if (node instanceof WithNode || node instanceof Block && ((Block)node).needsScope()) {
                n++;
            }
        }
        return n;
    }

    private BreakableNode getBreakable() {
        for (final NodeIterator<BreakableNode> iter = new NodeIterator<>(BreakableNode.class, getCurrentFunction()); iter.hasNext(); ) {
            final BreakableNode next = iter.next();
            if (next.isBreakableWithoutLabel()) {
                return next;
            }
        }
        return null;
    }

    /**
     * Check whether the lexical context is currently inside a loop.
     *
     * @return {@code true} if inside a loop
     */
    public boolean inLoop() {
        return getCurrentLoop() != null;
    }

    /**
     * @return the loop header of the current loop, or {@code null} if not
     *         inside a loop.
     */
    public LoopNode getCurrentLoop() {
        final Iterator<LoopNode> iter = new NodeIterator<>(LoopNode.class, getCurrentFunction());
        return iter.hasNext() ? iter.next() : null;
    }

    /**
     * Find the breakable node corresponding to this label.
     *
     * @param labelName name of the label to search for. If {@code null}, the
     *        closest breakable node will be returned unconditionally, e.g., a
     *        while loop with no label.
     *
     * @return closest breakable node.
     */
    public BreakableNode getBreakable(final String labelName) {
        if (labelName != null) {
            final LabelNode foundLabel = findLabel(labelName);
            if (foundLabel != null) {
                // iterate to the nearest breakable to the foundLabel
                BreakableNode breakable = null;
                for (final NodeIterator<BreakableNode> iter = new NodeIterator<>(BreakableNode.class, foundLabel); iter.hasNext(); ) {
                    breakable = iter.next();
                }
                return breakable;
            }
            return null;
        }
        return getBreakable();
    }

    private LoopNode getContinueTo() {
        return getCurrentLoop();
    }

    /**
     * Find the continue target node corresponding to this label.
     *
     * @param labelName label name to search for. If {@code null} the closest
     *        loop node will be returned unconditionally, e.g., a while loop
     *        with no label.
     *
     * @return closest continue target node.
     */
    public LoopNode getContinueTo(final String labelName) {
        if (labelName != null) {
            final LabelNode foundLabel = findLabel(labelName);
            if (foundLabel != null) {
                // iterate to the nearest loop to the foundLabel
                LoopNode loop = null;
                for (final NodeIterator<LoopNode> iter = new NodeIterator<>(LoopNode.class, foundLabel); iter.hasNext(); ) {
                    loop = iter.next();
                }
                return loop;
            }
            return null;
        }
        return getContinueTo();
    }

    /**
     * Find the inlined finally block node corresponding to this label.
     *
     * @param labelName label name to search for. Must not be {@code null}.
     *
     * @return closest inlined finally block with the given label.
     */
    public Block getInlinedFinally(final String labelName) {
        for (final NodeIterator<TryNode> iter = new NodeIterator<>(TryNode.class); iter.hasNext(); ) {
            final Block inlinedFinally = iter.next().getInlinedFinally(labelName);
            if (inlinedFinally != null) {
                return inlinedFinally;
            }
        }
        return null;
    }

    /**
     * Find the try node for an inlined finally block corresponding to this label.
     *
     * @param labelName label name to search for. Must not be {@code null}.
     *
     * @return the try node to which the labelled inlined finally block belongs.
     */
    public TryNode getTryNodeForInlinedFinally(final String labelName) {
        for (final NodeIterator<TryNode> iter = new NodeIterator<>(TryNode.class); iter.hasNext(); ) {
            final TryNode tryNode = iter.next();
            if (tryNode.getInlinedFinally(labelName) != null) {
                return tryNode;
            }
        }
        return null;
    }

    /**
     * Check the lexical context for a given label node by name.
     *
     * @param name name of the label.
     *
     * @return LabelNode if found, {@code null} otherwise.
     */
    private LabelNode findLabel(final String name) {
        for (final Iterator<LabelNode> iter = new NodeIterator<>(LabelNode.class, getCurrentFunction()); iter.hasNext(); ) {
            final LabelNode next = iter.next();
            if (next.getLabelName().equals(name)) {
                return next;
            }
        }
        return null;
    }

    /**
     * Checks whether a given target is a jump destination that lies outside a
     * given split node.
     *
     * @param splitNode the split node.
     * @param target the target node.
     *
     * @return {@code true} if target resides outside the split node.
     */
    public boolean isExternalTarget(final SplitNode splitNode, final BreakableNode target) {
        for (int i = sp; i-- > 0;) {
            final LexicalContextNode next = stack[i];
            if (next == splitNode) {
                return true;
            } else if (next == target) {
                return false;
            } else if (next instanceof TryNode) {
                for(final Block inlinedFinally: ((TryNode)next).getInlinedFinallies()) {
                    if (TryNode.getLabelledInlinedFinallyBlock(inlinedFinally) == target) {
                        return false;
                    }
                }
            }
        }
        throw new AssertionError(target + " was expected in lexical context " + LexicalContext.this + " but wasn't");
    }

    /**
     * Checks whether the current context is inside a switch statement without
     * explicit blocks (curly braces).
     *
     * @return {@code true} if in unprotected switch statement.
     */
    public boolean inUnprotectedSwitchContext() {
        for (int i = sp; i > 0; i--) {
            final LexicalContextNode next = stack[i];
            if (next instanceof Block) {
                return stack[i - 1] instanceof SwitchNode;
            }
        }
        return false;
    }

    @Override
    public String toString() {
        final StringBuffer sb = new StringBuffer();
        sb.append("[ ");
        for (int i = 0; i < sp; i++) {
            final Object node = stack[i];
            sb.append(node.getClass().getSimpleName());
            sb.append('@');
            sb.append(Debug.id(node));
            sb.append(':');
            if (node instanceof FunctionNode) {
                final FunctionNode fn = (FunctionNode)node;
                final Source source = fn.getSource();
                String src = source.toString();
                if (src.contains(File.pathSeparator)) {
                    src = src.substring(src.lastIndexOf(File.pathSeparator));
                }
                src += ' ';
                src += fn.getLineNumber();
                sb.append(src);
            }
            sb.append(' ');
        }
        sb.append(" ==> ]");
        return sb.toString();
    }

    private class NodeIterator <T extends LexicalContextNode> implements Iterator<T> {
        private int index;
        private T next;
        private final Class<T> clazz;
        private LexicalContextNode until;

        NodeIterator(final Class<T> clazz) {
            this(clazz, null);
        }

        NodeIterator(final Class<T> clazz, final LexicalContextNode until) {
            this.index = sp - 1;
            this.clazz = clazz;
            this.until = until;
            this.next  = findNext();
        }

        @Override
        public boolean hasNext() {
            return next != null;
        }

        @Override
        public T next() {
            if (next == null) {
                throw new NoSuchElementException();
            }
            final T lnext = next;
            next = findNext();
            return lnext;
        }

        @SuppressWarnings("unchecked")
        private T findNext() {
            for (int i = index; i >= 0; i--) {
                final Object node = stack[i];
                if (node == until) {
                    return null;
                }
                if (clazz.isAssignableFrom(node.getClass())) {
                    index = i - 1;
                    return (T)node;
                }
            }
            return null;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}