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