| /* |
| * 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.type.Type; |
| import com.android.dx.rop.type.TypeBearer; |
| import com.android.dx.util.ExceptionWithContext; |
| import com.android.dx.util.Hex; |
| import com.android.dx.util.MutabilityControl; |
| |
| /** |
| * Representation of a Java method execution stack. |
| * |
| * <p><b>Note:</b> For the most part, the documentation for this class |
| * ignores the distinction between {@link Type} and {@link |
| * TypeBearer}.</p> |
| */ |
| public final class ExecutionStack extends MutabilityControl { |
| /** non-null; array of stack contents */ |
| private final TypeBearer[] stack; |
| |
| /** |
| * >= 0; stack pointer (points one past the end) / current stack |
| * size |
| */ |
| private int stackPtr; |
| |
| /** |
| * Constructs an instance. |
| * |
| * @param maxStack >= 0; the maximum size of the stack for this |
| * instance |
| */ |
| public ExecutionStack(int maxStack) { |
| super(maxStack != 0); |
| stack = new TypeBearer[maxStack]; |
| stackPtr = 0; |
| } |
| |
| /** |
| * Makes and returns a mutable copy of this instance. |
| * |
| * @return non-null; the copy |
| */ |
| public ExecutionStack copy() { |
| ExecutionStack result = new ExecutionStack(stack.length); |
| |
| System.arraycopy(stack, 0, result.stack, 0, stack.length); |
| result.stackPtr = stackPtr; |
| |
| return result; |
| } |
| |
| /** |
| * Annotates (adds context to) the given exception with information |
| * about this instance. |
| * |
| * @param ex non-null; the exception to annotate |
| */ |
| public void annotate(ExceptionWithContext ex) { |
| int limit = stackPtr - 1; |
| |
| for (int i = 0; i <= limit; i++) { |
| String idx = (i == limit) ? "top0" : Hex.u2(limit - i); |
| |
| ex.addContext("stack[" + idx + "]: " + |
| stackElementString(stack[i])); |
| } |
| } |
| |
| /** |
| * Replaces all the occurrences of the given uninitialized type in |
| * this stack with its initialized equivalent. |
| * |
| * @param type non-null; type to replace |
| */ |
| public void makeInitialized(Type type) { |
| if (stackPtr == 0) { |
| // We have to check for this before checking for immutability. |
| return; |
| } |
| |
| throwIfImmutable(); |
| |
| Type initializedType = type.getInitializedType(); |
| |
| for (int i = 0; i < stackPtr; i++) { |
| if (stack[i] == type) { |
| stack[i] = initializedType; |
| } |
| } |
| } |
| |
| /** |
| * Gets the maximum stack size for this instance. |
| * |
| * @return >= 0; the max stack size |
| */ |
| public int getMaxStack() { |
| return stack.length; |
| } |
| |
| /** |
| * Gets the current stack size. |
| * |
| * @return >= 0, < getMaxStack(); the current stack size |
| */ |
| public int size() { |
| return stackPtr; |
| } |
| |
| /** |
| * Clears the stack. (That is, this method pops everything off.) |
| */ |
| public void clear() { |
| throwIfImmutable(); |
| |
| for (int i = 0; i < stackPtr; i++) { |
| stack[i] = null; |
| } |
| |
| stackPtr = 0; |
| } |
| |
| /** |
| * Pushes a value of the given type onto the stack. |
| * |
| * @param type non-null; type of the value |
| * @throws SimException thrown if there is insufficient room on the |
| * stack for the value |
| */ |
| public void push(TypeBearer type) { |
| throwIfImmutable(); |
| |
| int category; |
| |
| try { |
| type = type.getFrameType(); |
| category = type.getType().getCategory(); |
| } catch (NullPointerException ex) { |
| // Elucidate the exception. |
| throw new NullPointerException("type == null"); |
| } |
| |
| if ((stackPtr + category) > stack.length) { |
| throwSimException("overflow"); |
| return; |
| } |
| |
| if (category == 2) { |
| stack[stackPtr] = null; |
| stackPtr++; |
| } |
| |
| stack[stackPtr] = type; |
| stackPtr++; |
| } |
| |
| /** |
| * Peeks at the <code>n</code>th element down from the top of the stack. |
| * <code>n == 0</code> means to peek at the top of the stack. Note that |
| * this will return <code>null</code> if the indicated element is the |
| * deeper half of a category-2 value. |
| * |
| * @param n >= 0; which element to peek at |
| * @return null-ok; the type of value stored at that element |
| * @throws SimException thrown if <code>n >= size()</code> |
| */ |
| public TypeBearer peek(int n) { |
| if (n < 0) { |
| throw new IllegalArgumentException("n < 0"); |
| } |
| |
| if (n >= stackPtr) { |
| return throwSimException("underflow"); |
| } |
| |
| return stack[stackPtr - n - 1]; |
| } |
| |
| /** |
| * Peeks at the <code>n</code>th element down from the top of the |
| * stack, returning the type per se, as opposed to the |
| * <i>type-bearer</i>. This method is just a convenient shorthand |
| * for <code>peek(n).getType()</code>. |
| * |
| * @see #peek |
| */ |
| public Type peekType(int n) { |
| return peek(n).getType(); |
| } |
| |
| /** |
| * Pops the top element off of the stack. |
| * |
| * @return non-null; the type formerly on the top of the stack |
| * @throws SimException thrown if the stack is empty |
| */ |
| public TypeBearer pop() { |
| throwIfImmutable(); |
| |
| TypeBearer result = peek(0); |
| |
| stack[stackPtr - 1] = null; |
| stackPtr -= result.getType().getCategory(); |
| |
| return result; |
| } |
| |
| /** |
| * Changes an element already on a stack. This method is useful in limited |
| * contexts, particularly when merging two instances. As such, it places |
| * the following restriction on its behavior: You may only replace |
| * values with other values of the same category. |
| * |
| * @param n >= 0; which element to change, where <code>0</code> is |
| * the top element of the stack |
| * @param type non-null; type of the new value |
| * @throws SimException thrown if <code>n >= size()</code> or |
| * the action is otherwise prohibited |
| */ |
| public void change(int n, TypeBearer type) { |
| throwIfImmutable(); |
| |
| try { |
| type = type.getFrameType(); |
| } catch (NullPointerException ex) { |
| // Elucidate the exception. |
| throw new NullPointerException("type == null"); |
| } |
| |
| int idx = stackPtr - n - 1; |
| TypeBearer orig = stack[idx]; |
| |
| if ((orig == null) || |
| (orig.getType().getCategory() != type.getType().getCategory())) { |
| throwSimException("incompatible substitution: " + |
| stackElementString(orig) + " -> " + |
| stackElementString(type)); |
| } |
| |
| stack[idx] = type; |
| } |
| |
| /** |
| * Merges this stack with another stack. A new instance is returned if |
| * this merge results in a change. If no change results, this instance is |
| * returned. See {@link Merger#mergeStack(ExecutionStack,ExecutionStack) |
| * Merger.mergeStack()} |
| * |
| * @param other non-null; a stack to merge with |
| * @return non-null; the result of the merge |
| */ |
| public ExecutionStack merge(ExecutionStack other) { |
| try { |
| return Merger.mergeStack(this, other); |
| } catch (SimException ex) { |
| ex.addContext("underlay stack:"); |
| this.annotate(ex); |
| ex.addContext("overlay stack:"); |
| other.annotate(ex); |
| throw ex; |
| } |
| } |
| |
| /** |
| * Gets the string form for a stack element. This is the same as |
| * <code>toString()</code> except that <code>null</code> is converted |
| * to <code>"<invalid>"</code>. |
| * |
| * @param type null-ok; the stack element |
| * @return non-null; the string form |
| */ |
| private static String stackElementString(TypeBearer type) { |
| if (type == null) { |
| return "<invalid>"; |
| } |
| |
| return type.toString(); |
| } |
| |
| /** |
| * Throws a properly-formatted exception. |
| * |
| * @param msg non-null; useful message |
| * @return never (keeps compiler happy) |
| */ |
| private static TypeBearer throwSimException(String msg) { |
| throw new SimException("stack: " + msg); |
| } |
| } |