| /* |
| * 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.dx.rop.cst.CstType; |
| import com.android.dx.rop.type.StdTypeList; |
| import com.android.dx.rop.type.Type; |
| import com.android.dx.util.ExceptionWithContext; |
| 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); |
| } |
| } |