1 /* 2 * Copyright (C) 2008 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.dx.dex.code; 18 19 import com.android.dx.rop.code.BasicBlock; 20 import com.android.dx.rop.code.BasicBlockList; 21 import com.android.dx.rop.code.RopMethod; 22 import com.android.dx.rop.cst.CstType; 23 import com.android.dx.rop.type.Type; 24 import com.android.dx.rop.type.TypeList; 25 import com.android.dx.util.IntList; 26 27 import java.util.ArrayList; 28 import java.util.HashSet; 29 30 /** 31 * Constructor of {@link CatchTable} instances from {@link RopMethod} 32 * and associated data. 33 */ 34 public final class StdCatchBuilder implements CatchBuilder { 35 /** the maximum range of a single catch handler, in code units */ 36 private static final int MAX_CATCH_RANGE = 65535; 37 38 /** {@code non-null;} method to build the list for */ 39 private final RopMethod method; 40 41 /** {@code non-null;} block output order */ 42 private final int[] order; 43 44 /** {@code non-null;} address objects for each block */ 45 private final BlockAddresses addresses; 46 47 /** 48 * Constructs an instance. It merely holds onto its parameters for 49 * a subsequent call to {@link #build}. 50 * 51 * @param method {@code non-null;} method to build the list for 52 * @param order {@code non-null;} block output order 53 * @param addresses {@code non-null;} address objects for each block 54 */ 55 public StdCatchBuilder(RopMethod method, int[] order, 56 BlockAddresses addresses) { 57 if (method == null) { 58 throw new NullPointerException("method == null"); 59 } 60 61 if (order == null) { 62 throw new NullPointerException("order == null"); 63 } 64 65 if (addresses == null) { 66 throw new NullPointerException("addresses == null"); 67 } 68 69 this.method = method; 70 this.order = order; 71 this.addresses = addresses; 72 } 73 74 /** {@inheritDoc} */ 75 public CatchTable build() { 76 return build(method, order, addresses); 77 } 78 79 /** {@inheritDoc} */ 80 public boolean hasAnyCatches() { 81 BasicBlockList blocks = method.getBlocks(); 82 int size = blocks.size(); 83 84 for (int i = 0; i < size; i++) { 85 BasicBlock block = blocks.get(i); 86 TypeList catches = block.getLastInsn().getCatches(); 87 if (catches.size() != 0) { 88 return true; 89 } 90 } 91 92 return false; 93 } 94 95 /** {@inheritDoc} */ 96 public HashSet<Type> getCatchTypes() { 97 HashSet<Type> result = new HashSet<Type>(20); 98 BasicBlockList blocks = method.getBlocks(); 99 int size = blocks.size(); 100 101 for (int i = 0; i < size; i++) { 102 BasicBlock block = blocks.get(i); 103 TypeList catches = block.getLastInsn().getCatches(); 104 int catchSize = catches.size(); 105 106 for (int j = 0; j < catchSize; j++) { 107 result.add(catches.getType(j)); 108 } 109 } 110 111 return result; 112 } 113 114 /** 115 * Builds and returns the catch table for a given method. 116 * 117 * @param method {@code non-null;} method to build the list for 118 * @param order {@code non-null;} block output order 119 * @param addresses {@code non-null;} address objects for each block 120 * @return {@code non-null;} the constructed table 121 */ 122 public static CatchTable build(RopMethod method, int[] order, 123 BlockAddresses addresses) { 124 int len = order.length; 125 BasicBlockList blocks = method.getBlocks(); 126 ArrayList<CatchTable.Entry> resultList = 127 new ArrayList<CatchTable.Entry>(len); 128 CatchHandlerList currentHandlers = CatchHandlerList.EMPTY; 129 BasicBlock currentStartBlock = null; 130 BasicBlock currentEndBlock = null; 131 132 for (int i = 0; i < len; i++) { 133 BasicBlock block = blocks.labelToBlock(order[i]); 134 135 if (!block.canThrow()) { 136 /* 137 * There is no need to concern ourselves with the 138 * placement of blocks that can't throw with respect 139 * to the blocks that *can* throw. 140 */ 141 continue; 142 } 143 144 CatchHandlerList handlers = handlersFor(block, addresses); 145 146 if (currentHandlers.size() == 0) { 147 // This is the start of a new catch range. 148 currentStartBlock = block; 149 currentEndBlock = block; 150 currentHandlers = handlers; 151 continue; 152 } 153 154 if (currentHandlers.equals(handlers) 155 && rangeIsValid(currentStartBlock, block, addresses)) { 156 /* 157 * The block we are looking at now has the same handlers 158 * as the block that started the currently open catch 159 * range, and adding it to the currently open range won't 160 * cause it to be too long. 161 */ 162 currentEndBlock = block; 163 continue; 164 } 165 166 /* 167 * The block we are looking at now has incompatible handlers, 168 * so we need to finish off the last entry and start a new 169 * one. Note: We only emit an entry if it has associated handlers. 170 */ 171 if (currentHandlers.size() != 0) { 172 CatchTable.Entry entry = 173 makeEntry(currentStartBlock, currentEndBlock, 174 currentHandlers, addresses); 175 resultList.add(entry); 176 } 177 178 currentStartBlock = block; 179 currentEndBlock = block; 180 currentHandlers = handlers; 181 } 182 183 if (currentHandlers.size() != 0) { 184 // Emit an entry for the range that was left hanging. 185 CatchTable.Entry entry = 186 makeEntry(currentStartBlock, currentEndBlock, 187 currentHandlers, addresses); 188 resultList.add(entry); 189 } 190 191 // Construct the final result. 192 193 int resultSz = resultList.size(); 194 195 if (resultSz == 0) { 196 return CatchTable.EMPTY; 197 } 198 199 CatchTable result = new CatchTable(resultSz); 200 201 for (int i = 0; i < resultSz; i++) { 202 result.set(i, resultList.get(i)); 203 } 204 205 result.setImmutable(); 206 return result; 207 } 208 209 /** 210 * Makes the {@link CatchHandlerList} for the given basic block. 211 * 212 * @param block {@code non-null;} block to get entries for 213 * @param addresses {@code non-null;} address objects for each block 214 * @return {@code non-null;} array of entries 215 */ 216 private static CatchHandlerList handlersFor(BasicBlock block, 217 BlockAddresses addresses) { 218 IntList successors = block.getSuccessors(); 219 int succSize = successors.size(); 220 int primary = block.getPrimarySuccessor(); 221 TypeList catches = block.getLastInsn().getCatches(); 222 int catchSize = catches.size(); 223 224 if (catchSize == 0) { 225 return CatchHandlerList.EMPTY; 226 } 227 228 if (((primary == -1) && (succSize != catchSize)) 229 || ((primary != -1) && 230 ((succSize != (catchSize + 1)) 231 || (primary != successors.get(catchSize))))) { 232 /* 233 * Blocks that throw are supposed to list their primary 234 * successor -- if any -- last in the successors list, but 235 * that constraint appears to be violated here. 236 */ 237 throw new RuntimeException( 238 "shouldn't happen: weird successors list"); 239 } 240 241 /* 242 * Reduce the effective catchSize if we spot a catch-all that 243 * isn't at the end. 244 */ 245 for (int i = 0; i < catchSize; i++) { 246 Type type = catches.getType(i); 247 if (type.equals(Type.OBJECT)) { 248 catchSize = i + 1; 249 break; 250 } 251 } 252 253 CatchHandlerList result = new CatchHandlerList(catchSize); 254 255 for (int i = 0; i < catchSize; i++) { 256 CstType oneType = new CstType(catches.getType(i)); 257 CodeAddress oneHandler = addresses.getStart(successors.get(i)); 258 result.set(i, oneType, oneHandler.getAddress()); 259 } 260 261 result.setImmutable(); 262 return result; 263 } 264 265 /** 266 * Makes a {@link CatchTable#Entry} for the given block range and 267 * handlers. 268 * 269 * @param start {@code non-null;} the start block for the range (inclusive) 270 * @param end {@code non-null;} the start block for the range (also inclusive) 271 * @param handlers {@code non-null;} the handlers for the range 272 * @param addresses {@code non-null;} address objects for each block 273 */ 274 private static CatchTable.Entry makeEntry(BasicBlock start, 275 BasicBlock end, CatchHandlerList handlers, 276 BlockAddresses addresses) { 277 /* 278 * We start at the *last* instruction of the start block, since 279 * that's the instruction that can throw... 280 */ 281 CodeAddress startAddress = addresses.getLast(start); 282 283 // ...And we end *after* the last instruction of the end block. 284 CodeAddress endAddress = addresses.getEnd(end); 285 286 return new CatchTable.Entry(startAddress.getAddress(), 287 endAddress.getAddress(), handlers); 288 } 289 290 /** 291 * Gets whether the address range for the given two blocks is valid 292 * for a catch handler. This is true as long as the covered range is 293 * under 65536 code units. 294 * 295 * @param start {@code non-null;} the start block for the range (inclusive) 296 * @param end {@code non-null;} the start block for the range (also inclusive) 297 * @param addresses {@code non-null;} address objects for each block 298 * @return {@code true} if the range is valid as a catch range 299 */ 300 private static boolean rangeIsValid(BasicBlock start, BasicBlock end, 301 BlockAddresses addresses) { 302 if (start == null) { 303 throw new NullPointerException("start == null"); 304 } 305 306 if (end == null) { 307 throw new NullPointerException("end == null"); 308 } 309 310 // See above about selection of instructions. 311 int startAddress = addresses.getLast(start).getAddress(); 312 int endAddress = addresses.getEnd(end).getAddress(); 313 314 return (endAddress - startAddress) <= MAX_CATCH_RANGE; 315 } 316 } 317