TryListBuilder.java revision cb83d271e5485aa85ec7b8b3dc7b6e01417e1e43
1/* 2 * [The "BSD licence"] 3 * Copyright (c) 2009 Ben Gruver 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. The name of the author may not be used to endorse or promote products 15 * derived from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29package org.jf.dexlib.Util; 30 31import org.jf.dexlib.CodeItem; 32import org.jf.dexlib.DexFile; 33import org.jf.dexlib.TypeIdItem; 34 35import java.util.ArrayList; 36import java.util.HashMap; 37import java.util.LinkedList; 38import java.util.List; 39 40public class TryListBuilder 41{ 42 /*TODO: add logic to merge adjacent, identical try blocks, and remove superflous handlers 43 Also provide a "strict" mode, where the above isn't performed, which will be useful to be able to 44 exactly reproduce the original .dex file (for testing/verification purposes)*/ 45 46 47 private TryRange firstTryRange = new TryRange(0,0); 48 private TryRange lastTryRange = new TryRange(0,0); 49 50 public TryListBuilder() { 51 firstTryRange.next = lastTryRange; 52 lastTryRange.previous = firstTryRange; 53 } 54 55 private class TryRange 56 { 57 public TryRange previous = null; 58 public TryRange next = null; 59 60 public int startAddress; 61 public int endAddress; 62 public LinkedList<Handler> handlers; 63 64 public int catchAllHandlerAddress; 65 66 public TryRange(int startAddress, int endAddress) { 67 this.startAddress = startAddress; 68 this.endAddress = endAddress; 69 this.handlers = new LinkedList<Handler>(); 70 this.previous = null; 71 this.next = null; 72 catchAllHandlerAddress = -1; 73 } 74 75 public void append(TryRange tryRange) { 76 /*we use a dummy last item, so this.next will always 77 have a value*/ 78 this.next.previous = tryRange; 79 tryRange.next = this.next; 80 81 this.next = tryRange; 82 tryRange.previous = this; 83 } 84 85 public void prepend(TryRange tryRange){ 86 /*we use a dummy first item, so this.previous will always 87 have a value*/ 88 this.previous.next = tryRange; 89 tryRange.previous = this.previous; 90 91 this.previous = tryRange; 92 tryRange.next = this; 93 } 94 95 /** 96 * This splits the current range into two ranges at the given 97 * address. The existing range will be shortened to the first 98 * half, and a new range will be created and returned for the 99 * 2nd half. 100 * @param address The address to split at 101 * @return The 2nd half of the 102 */ 103 public TryRange split(int address) { 104 //this is a private class, so address is assumed 105 //to be valid 106 107 TryRange tryRange = new TryRange(address, endAddress); 108 tryRange.catchAllHandlerAddress = this.catchAllHandlerAddress; 109 tryRange.handlers.addAll(this.handlers); 110 append(tryRange); 111 112 this.endAddress = address; 113 114 return tryRange; 115 } 116 117 public void appendHandler(Handler handler) { 118 handlers.addLast(handler); 119 } 120 121 public void prependHandler(Handler handler) { 122 handlers.addFirst(handler); 123 } 124 } 125 126 private class Handler 127 { 128 public final TypeIdItem type; 129 public final int handlerAddress; 130 131 public Handler(TypeIdItem type, int handlerAddress) { 132 this.type = type; 133 this.handlerAddress = handlerAddress; 134 } 135 } 136 137 public Pair<List<CodeItem.TryItem>, List<CodeItem.EncodedCatchHandler>> encodeTries(DexFile dexFile) { 138 if (firstTryRange.next == lastTryRange) { 139 return new Pair<List<CodeItem.TryItem>, List<CodeItem.EncodedCatchHandler>>(null, null); 140 } 141 142 ArrayList<CodeItem.TryItem> tries = new ArrayList<CodeItem.TryItem>(); 143 ArrayList<CodeItem.EncodedCatchHandler> handlers = new ArrayList<CodeItem.EncodedCatchHandler>(); 144 145 HashMap<CodeItem.EncodedCatchHandler, CodeItem.EncodedCatchHandler> handlerDict = 146 new HashMap<CodeItem.EncodedCatchHandler, CodeItem.EncodedCatchHandler>(); 147 148 TryRange tryRange = firstTryRange.next; 149 150 while (tryRange != lastTryRange) { 151 ArrayList<CodeItem.EncodedTypeAddrPair> encodedTypeAddrPairs = 152 new ArrayList<CodeItem.EncodedTypeAddrPair>(); 153 154 for (Handler handler: tryRange.handlers) { 155 CodeItem.EncodedTypeAddrPair encodedTypeAddrPair = new CodeItem.EncodedTypeAddrPair( 156 dexFile, 157 handler.type, 158 handler.handlerAddress); 159 encodedTypeAddrPairs.add(encodedTypeAddrPair); 160 } 161 162 163 CodeItem.EncodedCatchHandler encodedCatchHandler = new CodeItem.EncodedCatchHandler( 164 dexFile, 165 encodedTypeAddrPairs, 166 tryRange.catchAllHandlerAddress); 167 CodeItem.EncodedCatchHandler internedEncodedCatchHandler = handlerDict.get(encodedCatchHandler); 168 if (internedEncodedCatchHandler == null) { 169 handlerDict.put(encodedCatchHandler, encodedCatchHandler); 170 handlers.add(encodedCatchHandler); 171 } else { 172 encodedCatchHandler = internedEncodedCatchHandler; 173 } 174 175 CodeItem.TryItem tryItem = new CodeItem.TryItem( 176 tryRange.startAddress, 177 tryRange.endAddress - tryRange.startAddress, 178 encodedCatchHandler); 179 tries.add(tryItem); 180 181 tryRange = tryRange.next; 182 } 183 184 return new Pair<List<CodeItem.TryItem>, List<CodeItem.EncodedCatchHandler>>(tries, handlers); 185 } 186 187 public void addCatchAllHandler(int startAddress, int endAddress, int handlerAddress) { 188 TryRange startRange = null; 189 TryRange endRange = null; 190 191 Pair<TryRange, TryRange> ranges = getBoundingRanges(startAddress, endAddress); 192 startRange = ranges.first; 193 endRange = ranges.second; 194 195 int previousEnd = startAddress; 196 TryRange tryRange = startRange; 197 198 /*Now we have the start and end ranges that exactly match the start and end 199 of the range being added. We need to iterate over all the ranges from the start 200 to end range inclusively, and append the handler to the end of each range's handler 201 list. We also need to create a new range for any "holes" in the existing ranges*/ 202 do 203 { 204 //is there a hole? If so, add a new range to fill the hole 205 if (tryRange.startAddress > previousEnd) { 206 TryRange newRange = new TryRange(previousEnd, tryRange.startAddress); 207 tryRange.prepend(newRange); 208 tryRange = newRange; 209 } 210 211 if (tryRange.catchAllHandlerAddress == -1) { 212 tryRange.catchAllHandlerAddress = handlerAddress; 213 } 214 215 previousEnd = tryRange.endAddress; 216 tryRange = tryRange.next; 217 } while (tryRange.previous != endRange); 218 } 219 220 public Pair<TryRange, TryRange> getBoundingRanges(int startAddress, int endAddress) { 221 TryRange startRange = null; 222 TryRange endRange = null; 223 224 TryRange tryRange = firstTryRange.next; 225 while (tryRange != lastTryRange) { 226 if (startAddress == tryRange.startAddress) { 227 //|-----| 228 //^------ 229 /*Bam. We hit the start of the range right on the head*/ 230 startRange = tryRange; 231 break; 232 } else if (startAddress > tryRange.startAddress && startAddress < tryRange.endAddress) { 233 //|-----| 234 // ^---- 235 /*Almost. The start of the range being added is in the middle 236 of an existing try range. We need to split the existing range 237 at the start address of the range being added*/ 238 startRange = tryRange.split(startAddress); 239 break; 240 }else if (startAddress < tryRange.startAddress) { 241 if (endAddress <= tryRange.startAddress) { 242 // |-----| 243 //^--^ 244 /*Oops, totally too far! The new range doesn't overlap any existing 245 ones, so we just add it and return*/ 246 startRange = new TryRange(startAddress, endAddress); 247 tryRange.prepend(startRange); 248 return new Pair<TryRange, TryRange>(startRange, startRange); 249 } else { 250 // |-----| 251 //^--------- 252 /*Oops, too far! We've passed the start of the range being added, but 253 the new range does overlap this one. We need to add a new range just 254 before this one*/ 255 startRange = new TryRange(startAddress, tryRange.startAddress); 256 tryRange.prepend(startRange); 257 break; 258 } 259 } 260 261 tryRange = tryRange.next; 262 } 263 264 //|-----| 265 // ^----- 266 /*Either the list of tries is blank, or all the tries in the list 267 end before the range being added starts. In either case, we just need 268 to add a new range at the end of the list*/ 269 if (startRange == null) { 270 startRange = new TryRange(startAddress, endAddress); 271 lastTryRange.prepend(startRange); 272 return new Pair<TryRange, TryRange>(startRange, startRange); 273 } 274 275 tryRange = startRange; 276 while (tryRange != lastTryRange) { 277 if (tryRange.endAddress == endAddress) { 278 //|-----| 279 //------^ 280 /*Bam! We hit the end right on the head.*/ 281 endRange = tryRange; 282 break; 283 } else if (tryRange.startAddress < endAddress && tryRange.endAddress > endAddress) { 284 //|-----| 285 //--^ 286 /*Almost. The range being added ends in the middle of an 287 existing range. We need to split the existing range 288 at the end of the range being added.*/ 289 tryRange.split(endAddress); 290 endRange = tryRange; 291 break; 292 } else if (tryRange.startAddress >= endAddress) { 293 //|-----| |-----| 294 //-----------^ 295 /*Oops, too far! The current range starts after the range being added 296 ends. We need to create a new range that starts at the end of the 297 previous range, and ends at the end of the range being added*/ 298 endRange = new TryRange(tryRange.previous.endAddress, endAddress); 299 tryRange.prepend(endRange); 300 break; 301 } 302 tryRange = tryRange.next; 303 } 304 305 //|-----| 306 //--------^ 307 /*The last range in the list ended before the end of the range being added. 308 We need to add a new range that starts at the end of the last range in the 309 list, and ends at the end of the range being added.*/ 310 if (endRange == null) { 311 endRange = new TryRange(lastTryRange.previous.endAddress, endAddress); 312 lastTryRange.prepend(endRange); 313 } 314 315 return new Pair<TryRange, TryRange>(startRange, endRange); 316 } 317 318 public void addHandler(TypeIdItem type, int startAddress, int endAddress, int handlerAddress) { 319 TryRange startRange = null; 320 TryRange endRange = null; 321 322 //TODO: need to check for pre-existing exception types in the handler list? 323 324 Pair<TryRange, TryRange> ranges = getBoundingRanges(startAddress, endAddress); 325 startRange = ranges.first; 326 endRange = ranges.second; 327 Handler handler = new Handler(type, handlerAddress); 328 329 int previousEnd = startAddress; 330 TryRange tryRange = startRange; 331 332 /*Now we have the start and end ranges that exactly match the start and end 333 of the range being added. We need to iterate over all the ranges from the start 334 to end range inclusively, and append the handler to the end of each range's handler 335 list. We also need to create a new range for any "holes" in the existing ranges*/ 336 do 337 { 338 //is there a hole? If so, add a new range to fill the hole 339 if (tryRange.startAddress > previousEnd) { 340 TryRange newRange = new TryRange(previousEnd, tryRange.startAddress); 341 tryRange.prepend(newRange); 342 tryRange = newRange; 343 } 344 345 tryRange.appendHandler(handler); 346 previousEnd = tryRange.endAddress; 347 tryRange = tryRange.next; 348 } while (tryRange.previous != endRange); 349 } 350} 351