cf/code/Frame.java

/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.cf.code;

import com.android.dex.util.ExceptionWithContext;
import com.android.dx.rop.cst.CstType;
import com.android.dx.rop.type.StdTypeList;
import com.android.dx.rop.type.Type;
import com.android.dx.util.IntList;

/**
 * Representation of a Java method execution frame. A frame consists
 * of a set of locals and a value stack, and it can be told to act on
 * them to load and store values between them and an "arguments /
 * results" area.
 */
public final class Frame {
    /** {@code non-null;} the locals */
    private final LocalsArray locals;

    /** {@code non-null;} the stack */
    private final ExecutionStack stack;

    /** {@code null-ok;} stack of labels of subroutines that this block is nested in */
    private final IntList subroutines;

    /**
     * Constructs an instance.
     *
     * @param locals {@code non-null;} the locals array to use
     * @param stack {@code non-null;} the execution stack to use
     */
    private Frame(LocalsArray locals, ExecutionStack stack) {
        this(locals, stack, IntList.EMPTY);
    }

    /**
     * Constructs an instance.
     *
     * @param locals {@code non-null;} the locals array to use
     * @param stack {@code non-null;} the execution stack to use
     * @param subroutines {@code non-null;} list of subroutine start labels for
     * subroutines this frame is nested in
     */
    private Frame(LocalsArray locals,
            ExecutionStack stack, IntList subroutines) {
        if (locals == null) {
            throw new NullPointerException("locals == null");
        }

        if (stack == null) {
            throw new NullPointerException("stack == null");
        }

        subroutines.throwIfMutable();

        this.locals = locals;
        this.stack = stack;
        this.subroutines = subroutines;
    }

    /**
     * Constructs an instance. The locals array initially consists of
     * all-uninitialized values (represented as {@code null}s) and
     * the stack starts out empty.
     *
     * @param maxLocals {@code >= 0;} the maximum number of locals this instance
     * can refer to
     * @param maxStack {@code >= 0;} the maximum size of the stack for this
     * instance
     */
    public Frame(int maxLocals, int maxStack) {
        this(new OneLocalsArray(maxLocals), new ExecutionStack(maxStack));
    }

    /**
     * Makes and returns a mutable copy of this instance. The copy
     * contains copies of the locals and stack (that is, it doesn't
     * share them with the original).
     *
     * @return {@code non-null;} the copy
     */
    public Frame copy() {
        return new Frame(locals.copy(), stack.copy(), subroutines);
    }

    /**
     * Makes this instance immutable.
     */
    public void setImmutable() {
        locals.setImmutable();
        stack.setImmutable();
        // "subroutines" is always immutable
    }

    /**
     * Replaces all the occurrences of the given uninitialized type in
     * this frame with its initialized equivalent.
     *
     * @param type {@code non-null;} type to replace
     */
    public void makeInitialized(Type type) {
        locals.makeInitialized(type);
        stack.makeInitialized(type);
    }

    /**
     * Gets the locals array for this instance.
     *
     * @return {@code non-null;} the locals array
     */
    public LocalsArray getLocals() {
        return locals;
    }

    /**
     * Gets the execution stack for this instance.
     *
     * @return {@code non-null;} the execution stack
     */
    public ExecutionStack getStack() {
        return stack;
    }

    /**
     * Returns the largest subroutine nesting this block may be in. An
     * empty list is returned if this block is not in any subroutine.
     * Subroutines are identified by the label of their start block. The
     * list is ordered such that the deepest nesting (the actual subroutine
     * this block is in) is the last label in the list.
     *
     * @return {@code non-null;} list as noted above
     */
    public IntList getSubroutines() {
        return subroutines;
    }

    /**
     * Initialize this frame with the method's parameters. Used for the first
     * frame.
     *
     * @param params Type list of method parameters.
     */
    public void initializeWithParameters(StdTypeList params) {
        int at = 0;
        int sz = params.size();

        for (int i = 0; i < sz; i++) {
             Type one = params.get(i);
             locals.set(at, one);
             at += one.getCategory();
        }
    }

    /**
     * Returns a Frame instance representing the frame state that should
     * be used when returning from a subroutine. The stack state of all
     * subroutine invocations is identical, but the locals state may differ.
     *
     * @param startLabel {@code >=0;} The label of the returning subroutine's
     * start block
     * @param subLabel {@code >=0;} A calling label of a subroutine
     * @return {@code null-ok;} an appropriatly-constructed instance, or null
     * if label is not in the set
     */
    public Frame subFrameForLabel(int startLabel, int subLabel) {
        LocalsArray subLocals = null;

        if (locals instanceof LocalsArraySet) {
            subLocals = ((LocalsArraySet)locals).subArrayForLabel(subLabel);
        }

        IntList newSubroutines;
        try {
            newSubroutines = subroutines.mutableCopy();

            if (newSubroutines.pop() != startLabel) {
                throw new RuntimeException("returning from invalid subroutine");
            }
            newSubroutines.setImmutable();
        } catch (IndexOutOfBoundsException ex) {
            throw new RuntimeException("returning from invalid subroutine");
        } catch (NullPointerException ex) {
            throw new NullPointerException("can't return from non-subroutine");
        }

        return (subLocals == null) ? null
                : new Frame(subLocals, stack, newSubroutines);
    }

    /**
     * Merges two frames. If the merged result is the same as this frame,
     * then this instance is returned.
     *
     * @param other {@code non-null;} another frame
     * @return {@code non-null;} the result of merging the two frames
     */
    public Frame mergeWith(Frame other) {
        LocalsArray resultLocals;
        ExecutionStack resultStack;
        IntList resultSubroutines;

        resultLocals = getLocals().merge(other.getLocals());
        resultStack = getStack().merge(other.getStack());
        resultSubroutines = mergeSubroutineLists(other.subroutines);

        resultLocals = adjustLocalsForSubroutines(
                resultLocals, resultSubroutines);

        if ((resultLocals == getLocals())
                && (resultStack == getStack())
                && subroutines == resultSubroutines) {
            return this;
        }

        return new Frame(resultLocals, resultStack, resultSubroutines);
    }

    /**
     * Merges this frame's subroutine lists with another. The result
     * is the deepest common nesting (effectively, the common prefix of the
     * two lists).
     *
     * @param otherSubroutines label list of subroutine start blocks, from
     * least-nested to most-nested.
     * @return {@code non-null;} merged subroutine nest list as described above
     */
    private IntList mergeSubroutineLists(IntList otherSubroutines) {
        if (subroutines.equals(otherSubroutines)) {
            return subroutines;
        }

        IntList resultSubroutines = new IntList();

        int szSubroutines = subroutines.size();
        int szOthers = otherSubroutines.size();
        for (int i = 0; i < szSubroutines && i < szOthers
                && (subroutines.get(i) == otherSubroutines.get(i)); i++) {
            resultSubroutines.add(i);
        }

        resultSubroutines.setImmutable();

        return resultSubroutines;
    }

    /**
     * Adjusts a locals array to account for a merged subroutines list.
     * If a frame merge results in, effectively, a subroutine return through
     * a throw then the current locals will be a LocalsArraySet that will
     * need to be trimmed of all OneLocalsArray elements that relevent to
     * the subroutine that is returning.
     *
     * @param locals {@code non-null;} LocalsArray from before a merge
     * @param subroutines {@code non-null;} a label list of subroutine start blocks
     * representing the subroutine nesting of the block being merged into.
     * @return {@code non-null;} locals set appropriate for merge
     */
    private static LocalsArray adjustLocalsForSubroutines(
            LocalsArray locals, IntList subroutines) {
        if (! (locals instanceof LocalsArraySet)) {
            // nothing to see here
            return locals;
        }

        LocalsArraySet laSet = (LocalsArraySet)locals;

        if (subroutines.size() == 0) {
            /*
             * We've merged from a subroutine context to a non-subroutine
             * context, likely via a throw. Our successor will only need
             * to consider the primary locals state, not the state of
             * all possible subroutine paths.
             */

            return laSet.getPrimary();
        }

        /*
         * It's unclear to me if the locals set needs to be trimmed here.
         * If it does, then I believe it is all of the calling blocks
         * in the subroutine at the end of "subroutines" passed into
         * this method that should be removed.
         */
        return laSet;
    }

    /**
     * Merges this frame with the frame of a subroutine caller at
     * {@code predLabel}. Only called on the frame at the first
     * block of a subroutine.
     *
     * @param other {@code non-null;} another frame
     * @param subLabel label of subroutine start block
     * @param predLabel label of calling block
     * @return {@code non-null;} the result of merging the two frames
     */
    public Frame mergeWithSubroutineCaller(Frame other, int subLabel,
            int predLabel) {
        LocalsArray resultLocals;
        ExecutionStack resultStack;

        resultLocals = getLocals().mergeWithSubroutineCaller(
                other.getLocals(), predLabel);
        resultStack = getStack().merge(other.getStack());

        IntList newOtherSubroutines = other.subroutines.mutableCopy();
        newOtherSubroutines.add(subLabel);
        newOtherSubroutines.setImmutable();

        if ((resultLocals == getLocals())
                && (resultStack == getStack())
                && subroutines.equals(newOtherSubroutines)) {
            return this;
        }

        IntList resultSubroutines;

        if (subroutines.equals(newOtherSubroutines)) {
            resultSubroutines = subroutines;
        } else {
            /*
             * The new subroutines list should be the deepest of the two
             * lists being merged, but the postfix of the resultant list
             * must be equal to the shorter list.
             */
            IntList nonResultSubroutines;

            if (subroutines.size() > newOtherSubroutines.size()) {
                resultSubroutines = subroutines;
                nonResultSubroutines = newOtherSubroutines;
            } else {
                resultSubroutines = newOtherSubroutines;
                nonResultSubroutines = subroutines;
            }

            int szResult = resultSubroutines.size();
            int szNonResult = nonResultSubroutines.size();

            for (int i = szNonResult - 1; i >=0; i-- ) {
                if (nonResultSubroutines.get(i)
                        != resultSubroutines.get(
                        i + (szResult - szNonResult))) {
                    throw new
                            RuntimeException("Incompatible merged subroutines");
                }
            }

        }

        return new Frame(resultLocals, resultStack, resultSubroutines);
    }

    /**
     * Makes a frame for a subroutine start block, given that this is the
     * ending frame of one of the subroutine's calling blocks. Subroutine
     * calls may be nested and thus may have nested locals state, so we
     * start with an initial state as seen by the subroutine, but keep track
     * of the individual locals states that will be expected when the individual
     * subroutine calls return.
     *
     * @param subLabel label of subroutine start block
     * @param callerLabel {@code >=0;} label of the caller block where this frame
     * came from.
     * @return a new instance to begin a called subroutine.
     */
    public Frame makeNewSubroutineStartFrame(int subLabel, int callerLabel) {
        IntList newSubroutines = subroutines.mutableCopy();
        newSubroutines.add(subLabel);
        Frame newFrame = new Frame(locals.getPrimary(), stack,
                IntList.makeImmutable(subLabel));
        return newFrame.mergeWithSubroutineCaller(this, subLabel, callerLabel);
    }

    /**
     * Makes a new frame for an exception handler block invoked from this
     * frame.
     *
     * @param exceptionClass exception that the handler block will handle
     * @return new frame
     */
    public Frame makeExceptionHandlerStartFrame(CstType exceptionClass) {
        ExecutionStack newStack = getStack().copy();

        newStack.clear();
        newStack.push(exceptionClass);

        return new Frame(getLocals(), newStack, subroutines);
    }

    /**
     * Annotates (adds context to) the given exception with information
     * about this frame.
     *
     * @param ex {@code non-null;} the exception to annotate
     */
    public void annotate(ExceptionWithContext ex) {
        locals.annotate(ex);
        stack.annotate(ex);
    }
}