1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project 3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you may not use this file except in compliance with the License. 6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * You may obtain a copy of the License at 7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See the License for the specific language governing permissions and 14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * limitations under the License. 15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpackage com.android.dx.cf.code; 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 19fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dex.util.ExceptionWithContext; 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.cst.CstType; 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.type.StdTypeList; 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.type.Type; 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntList; 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Representation of a Java method execution frame. A frame consists 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * of a set of locals and a value stack, and it can be told to act on 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * them to load and store values between them and an "arguments / 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * results" area. 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic final class Frame { 3299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} the locals */ 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final LocalsArray locals; 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 3599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} the stack */ 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ExecutionStack stack; 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 3899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code null-ok;} stack of labels of subroutines that this block is nested in */ 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final IntList subroutines; 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs an instance. 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param locals {@code non-null;} the locals array to use 4599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param stack {@code non-null;} the execution stack to use 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private Frame(LocalsArray locals, ExecutionStack stack) { 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this(locals, stack, IntList.EMPTY); 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs an instance. 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 5499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param locals {@code non-null;} the locals array to use 5599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param stack {@code non-null;} the execution stack to use 5699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param subroutines {@code non-null;} list of subroutine start labels for 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * subroutines this frame is nested in 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private Frame(LocalsArray locals, 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ExecutionStack stack, IntList subroutines) { 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (locals == null) { 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException("locals == null"); 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (stack == null) { 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException("stack == null"); 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutines.throwIfMutable(); 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.locals = locals; 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.stack = stack; 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.subroutines = subroutines; 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs an instance. The locals array initially consists of 7899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * all-uninitialized values (represented as {@code null}s) and 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the stack starts out empty. 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param maxLocals {@code >= 0;} the maximum number of locals this instance 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * can refer to 8399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param maxStack {@code >= 0;} the maximum size of the stack for this 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instance 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public Frame(int maxLocals, int maxStack) { 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this(new OneLocalsArray(maxLocals), new ExecutionStack(maxStack)); 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Makes and returns a mutable copy of this instance. The copy 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * contains copies of the locals and stack (that is, it doesn't 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * share them with the original). 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 9599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the copy 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public Frame copy() { 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return new Frame(locals.copy(), stack.copy(), subroutines); 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Makes this instance immutable. 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void setImmutable() { 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project locals.setImmutable(); 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project stack.setImmutable(); 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // "subroutines" is always immutable 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Replaces all the occurrences of the given uninitialized type in 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * this frame with its initialized equivalent. 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 11499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param type {@code non-null;} type to replace 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void makeInitialized(Type type) { 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project locals.makeInitialized(type); 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project stack.makeInitialized(type); 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the locals array for this instance. 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 12499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the locals array 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public LocalsArray getLocals() { 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return locals; 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the execution stack for this instance. 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 13399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the execution stack 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public ExecutionStack getStack() { 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return stack; 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns the largest subroutine nesting this block may be in. An 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * empty list is returned if this block is not in any subroutine. 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Subroutines are identified by the label of their start block. The 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * list is ordered such that the deepest nesting (the actual subroutine 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * this block is in) is the last label in the list. 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 14699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} list as noted above 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public IntList getSubroutines() { 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return subroutines; 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Initialize this frame with the method's parameters. Used for the first 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * frame. 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param params Type list of method parameters. 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void initializeWithParameters(StdTypeList params) { 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int at = 0; 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = params.size(); 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Type one = params.get(i); 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project locals.set(at, one); 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project at += one.getCategory(); 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns a Frame instance representing the frame state that should 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * be used when returning from a subroutine. The stack state of all 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * subroutine invocations is identical, but the locals state may differ. 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 17499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param startLabel {@code >=0;} The label of the returning subroutine's 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * start block 17699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param subLabel {@code >=0;} A calling label of a subroutine 17799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code null-ok;} an appropriatly-constructed instance, or null 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * if label is not in the set 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public Frame subFrameForLabel(int startLabel, int subLabel) { 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalsArray subLocals = null; 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (locals instanceof LocalsArraySet) { 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subLocals = ((LocalsArraySet)locals).subArrayForLabel(subLabel); 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList newSubroutines; 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSubroutines = subroutines.mutableCopy(); 190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (newSubroutines.pop() != startLabel) { 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException("returning from invalid subroutine"); 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSubroutines.setImmutable(); 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (IndexOutOfBoundsException ex) { 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException("returning from invalid subroutine"); 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (NullPointerException ex) { 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException("can't return from non-subroutine"); 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 200de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (subLocals == null) ? null 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project : new Frame(subLocals, stack, newSubroutines); 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Merges two frames. If the merged result is the same as this frame, 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * then this instance is returned. 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 20999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param other {@code non-null;} another frame 21099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the result of merging the two frames 211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public Frame mergeWith(Frame other) { 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalsArray resultLocals; 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ExecutionStack resultStack; 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList resultSubroutines; 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultLocals = getLocals().merge(other.getLocals()); 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultStack = getStack().merge(other.getStack()); 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines = mergeSubroutineLists(other.subroutines); 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultLocals = adjustLocalsForSubroutines( 222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultLocals, resultSubroutines); 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((resultLocals == getLocals()) 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && (resultStack == getStack()) 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && subroutines == resultSubroutines) { 227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return this; 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return new Frame(resultLocals, resultStack, resultSubroutines); 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Merges this frame's subroutine lists with another. The result 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is the deepest common nesting (effectively, the common prefix of the 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * two lists). 237de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param otherSubroutines label list of subroutine start blocks, from 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * least-nested to most-nested. 24099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} merged subroutine nest list as described above 241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private IntList mergeSubroutineLists(IntList otherSubroutines) { 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subroutines.equals(otherSubroutines)) { 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return subroutines; 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList resultSubroutines = new IntList(); 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSubroutines = subroutines.size(); 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szOthers = otherSubroutines.size(); 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSubroutines && i < szOthers 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && (subroutines.get(i) == otherSubroutines.get(i)); i++) { 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines.add(i); 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines.setImmutable(); 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return resultSubroutines; 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adjusts a locals array to account for a merged subroutines list. 263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If a frame merge results in, effectively, a subroutine return through 264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * a throw then the current locals will be a LocalsArraySet that will 265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * need to be trimmed of all OneLocalsArray elements that relevent to 266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the subroutine that is returning. 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 26899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param locals {@code non-null;} LocalsArray from before a merge 26999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param subroutines {@code non-null;} a label list of subroutine start blocks 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * representing the subroutine nesting of the block being merged into. 27199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} locals set appropriate for merge 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static LocalsArray adjustLocalsForSubroutines( 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalsArray locals, IntList subroutines) { 275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (! (locals instanceof LocalsArraySet)) { 276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // nothing to see here 277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return locals; 278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 279f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalsArraySet laSet = (LocalsArraySet)locals; 281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subroutines.size() == 0) { 283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * We've merged from a subroutine context to a non-subroutine 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * context, likely via a throw. Our successor will only need 286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to consider the primary locals state, not the state of 287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * all possible subroutine paths. 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return laSet.getPrimary(); 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * It's unclear to me if the locals set needs to be trimmed here. 295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If it does, then I believe it is all of the calling blocks 296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in the subroutine at the end of "subroutines" passed into 297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * this method that should be removed. 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return laSet; 300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Merges this frame with the frame of a subroutine caller at 30499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code predLabel}. Only called on the frame at the first 305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * block of a subroutine. 306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 30799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param other {@code non-null;} another frame 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param subLabel label of subroutine start block 309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param predLabel label of calling block 31099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the result of merging the two frames 311f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 312f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public Frame mergeWithSubroutineCaller(Frame other, int subLabel, 313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int predLabel) { 314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalsArray resultLocals; 315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ExecutionStack resultStack; 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultLocals = getLocals().mergeWithSubroutineCaller( 318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project other.getLocals(), predLabel); 319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultStack = getStack().merge(other.getStack()); 320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList newOtherSubroutines = other.subroutines.mutableCopy(); 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newOtherSubroutines.add(subLabel); 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newOtherSubroutines.setImmutable(); 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((resultLocals == getLocals()) 326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && (resultStack == getStack()) 327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && subroutines.equals(newOtherSubroutines)) { 328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return this; 329f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList resultSubroutines; 332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subroutines.equals(newOtherSubroutines)) { 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines = subroutines; 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The new subroutines list should be the deepest of the two 338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * lists being merged, but the postfix of the resultant list 339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * must be equal to the shorter list. 340f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 341f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList nonResultSubroutines; 342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subroutines.size() > newOtherSubroutines.size()) { 344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines = subroutines; 345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project nonResultSubroutines = newOtherSubroutines; 346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines = newOtherSubroutines; 348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project nonResultSubroutines = subroutines; 349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szResult = resultSubroutines.size(); 352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szNonResult = nonResultSubroutines.size(); 353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = szNonResult - 1; i >=0; i-- ) { 355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (nonResultSubroutines.get(i) 356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project != resultSubroutines.get( 357f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i + (szResult - szNonResult))) { 358f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new 359f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RuntimeException("Incompatible merged subroutines"); 360f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 361f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 362de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 363f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 364f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 365f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return new Frame(resultLocals, resultStack, resultSubroutines); 366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 367f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 368f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 369f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Makes a frame for a subroutine start block, given that this is the 370f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * ending frame of one of the subroutine's calling blocks. Subroutine 371f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * calls may be nested and thus may have nested locals state, so we 372f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * start with an initial state as seen by the subroutine, but keep track 373f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * of the individual locals states that will be expected when the individual 374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * subroutine calls return. 375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param subLabel label of subroutine start block 37799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param callerLabel {@code >=0;} label of the caller block where this frame 378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * came from. 379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return a new instance to begin a called subroutine. 380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public Frame makeNewSubroutineStartFrame(int subLabel, int callerLabel) { 382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList newSubroutines = subroutines.mutableCopy(); 383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSubroutines.add(subLabel); 384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Frame newFrame = new Frame(locals.getPrimary(), stack, 385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList.makeImmutable(subLabel)); 386f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return newFrame.mergeWithSubroutineCaller(this, subLabel, callerLabel); 387f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 390f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Makes a new frame for an exception handler block invoked from this 391f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * frame. 392f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 393f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param exceptionClass exception that the handler block will handle 394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return new frame 395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public Frame makeExceptionHandlerStartFrame(CstType exceptionClass) { 397f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ExecutionStack newStack = getStack().copy(); 398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newStack.clear(); 400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newStack.push(exceptionClass); 401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 402f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return new Frame(getLocals(), newStack, subroutines); 403f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 405f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Annotates (adds context to) the given exception with information 407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * about this frame. 408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 40999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ex {@code non-null;} the exception to annotate 410f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 411f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void annotate(ExceptionWithContext ex) { 412f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project locals.annotate(ex); 413f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project stack.annotate(ex); 414f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 416