TryListBuilder.java revision 8c3d16b7ee368c14e805077d047162f3bb434193
1/* 2 * Copyright 2013, Google Inc. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * * Redistributions in binary form must reproduce the above 12 * copyright notice, this list of conditions and the following disclaimer 13 * in the documentation and/or other materials provided with the 14 * distribution. 15 * * Neither the name of Google Inc. nor the names of its 16 * contributors may be used to endorse or promote products derived from 17 * this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32package org.jf.dexlib2.writer.util; 33 34import com.google.common.collect.Lists; 35import org.jf.dexlib2.base.BaseTryBlock; 36import org.jf.dexlib2.iface.ExceptionHandler; 37import org.jf.dexlib2.iface.TryBlock; 38import org.jf.dexlib2.immutable.ImmutableExceptionHandler; 39import org.jf.util.ExceptionWithContext; 40 41import javax.annotation.Nonnull; 42import javax.annotation.Nullable; 43import java.util.Iterator; 44import java.util.List; 45import java.util.NoSuchElementException; 46 47public class TryListBuilder 48{ 49 /*TODO: add logic to merge adjacent, identical try blocks, and remove superflous handlers 50 Also provide a "strict" mode, where the above isn't performed, which will be useful to be able to 51 exactly reproduce the original .dex file (for testing/verification purposes)*/ 52 53 // Linked list sentinels that don't represent an actual try block 54 // Their values are never modified, only their links 55 private final MutableTryBlock listStart; 56 private final MutableTryBlock listEnd; 57 58 public TryListBuilder() { 59 listStart = new MutableTryBlock(0, 0); 60 listEnd = new MutableTryBlock(0, 0); 61 listStart.next = listEnd; 62 listEnd.prev = listStart; 63 } 64 65 private static class TryBounds { 66 @Nonnull public final MutableTryBlock start; 67 @Nonnull public final MutableTryBlock end; 68 69 public TryBounds(@Nonnull MutableTryBlock start, @Nonnull MutableTryBlock end) { 70 this.start = start; 71 this.end = end; 72 } 73 } 74 75 public static class InvalidTryException extends ExceptionWithContext { 76 public InvalidTryException(Throwable cause) { 77 super(cause); 78 } 79 80 public InvalidTryException(Throwable cause, String message, Object... formatArgs) { 81 super(cause, message, formatArgs); 82 } 83 84 public InvalidTryException(String message, Object... formatArgs) { 85 super(message, formatArgs); 86 } 87 } 88 89 private static class MutableTryBlock extends BaseTryBlock implements TryBlock { 90 public MutableTryBlock prev = null; 91 public MutableTryBlock next = null; 92 93 public int startCodeAddress; 94 public int endCodeAddress; 95 @Nonnull public List<ExceptionHandler> exceptionHandlers = Lists.newArrayList(); 96 97 public MutableTryBlock(int startCodeAddress, int endCodeAddress) { 98 this.startCodeAddress = startCodeAddress; 99 this.endCodeAddress = endCodeAddress; 100 } 101 102 public MutableTryBlock(int startCodeAddress, int endCodeAddress, 103 @Nonnull List<? extends ExceptionHandler> exceptionHandlers) { 104 this.startCodeAddress = startCodeAddress; 105 this.endCodeAddress = endCodeAddress; 106 this.exceptionHandlers = Lists.newArrayList(exceptionHandlers); 107 } 108 109 @Override public int getStartCodeAddress() { 110 return startCodeAddress; 111 } 112 113 @Override public int getCodeUnitCount() { 114 return endCodeAddress - startCodeAddress; 115 } 116 117 @Nonnull @Override public List<? extends ExceptionHandler> getExceptionHandlers() { 118 return exceptionHandlers; 119 } 120 121 @Nonnull 122 public MutableTryBlock split(int splitAddress) { 123 MutableTryBlock newTryBlock = new MutableTryBlock(splitAddress, endCodeAddress, exceptionHandlers); 124 endCodeAddress = splitAddress; 125 append(newTryBlock); 126 return newTryBlock; 127 } 128 129 public void delete() { 130 next.prev = prev; 131 prev.next = next; 132 } 133 134 public void mergeNext() { 135 //assert next.startCodeAddress == this.endCodeAddress; 136 this.endCodeAddress = next.endCodeAddress; 137 next.delete(); 138 } 139 140 public void append(@Nonnull MutableTryBlock tryBlock) { 141 next.prev = tryBlock; 142 tryBlock.next = next; 143 tryBlock.prev = this; 144 next = tryBlock; 145 } 146 147 public void prepend(@Nonnull MutableTryBlock tryBlock) { 148 prev.next = tryBlock; 149 tryBlock.prev = prev; 150 tryBlock.next = this; 151 prev = tryBlock; 152 } 153 154 public void addHandler(@Nonnull ExceptionHandler handler) { 155 for (ExceptionHandler existingHandler: exceptionHandlers) { 156 String existingType = existingHandler.getExceptionType(); 157 String newType = handler.getExceptionType(); 158 159 // Don't add it if we already have a handler of the same type 160 if (existingType == null) { 161 if (newType == null) { 162 if (existingHandler.getHandlerCodeAddress() != handler.getHandlerCodeAddress()) { 163 throw new InvalidTryException( 164 "Multiple overlapping catch all handlers with different handlers"); 165 } 166 return; 167 } 168 } else if (existingType.equals(newType)) { 169 if (existingHandler.getHandlerCodeAddress() != handler.getHandlerCodeAddress()) { 170 throw new InvalidTryException( 171 "Multiple overlapping catches for %s with different handlers", existingType); 172 } 173 return; 174 } 175 } 176 177 exceptionHandlers.add(handler); 178 } 179 } 180 181 private TryBounds getBoundingRanges(int startAddress, int endAddress) { 182 MutableTryBlock startBlock = null; 183 184 MutableTryBlock tryBlock = listStart.next; 185 while (tryBlock != listEnd) { 186 int currentStartAddress = tryBlock.startCodeAddress; 187 int currentEndAddress = tryBlock.endCodeAddress; 188 189 if (startAddress == currentStartAddress) { 190 //|-----| 191 //^------ 192 /*Bam. We hit the start of the range right on the head*/ 193 startBlock = tryBlock; 194 break; 195 } else if (startAddress > currentStartAddress && startAddress < currentEndAddress) { 196 //|-----| 197 // ^---- 198 /*Almost. The start of the range being added is in the middle 199 of an existing try range. We need to split the existing range 200 at the start address of the range being added*/ 201 startBlock = tryBlock.split(startAddress); 202 break; 203 }else if (startAddress < currentStartAddress) { 204 if (endAddress <= currentStartAddress) { 205 // |-----| 206 //^--^ 207 /*Oops, totally too far! The new range doesn't overlap any existing 208 ones, so we just add it and return*/ 209 startBlock = new MutableTryBlock(startAddress, endAddress); 210 tryBlock.prepend(startBlock); 211 return new TryBounds(startBlock, startBlock); 212 } else { 213 // |-----| 214 //^--------- 215 /*Oops, too far! We've passed the start of the range being added, but 216 the new range does overlap this one. We need to add a new range just 217 before this one*/ 218 startBlock = new MutableTryBlock(startAddress, currentStartAddress); 219 tryBlock.prepend(startBlock); 220 break; 221 } 222 } 223 224 tryBlock = tryBlock.next; 225 } 226 227 //|-----| 228 // ^----- 229 /*Either the list of tries is blank, or all the tries in the list 230 end before the range being added starts. In either case, we just need 231 to add a new range at the end of the list*/ 232 if (startBlock == null) { 233 startBlock = new MutableTryBlock(startAddress, endAddress); 234 listEnd.prepend(startBlock); 235 return new TryBounds(startBlock, startBlock); 236 } 237 238 tryBlock = startBlock; 239 while (tryBlock != listEnd) { 240 int currentStartAddress = tryBlock.startCodeAddress; 241 int currentEndAddress = tryBlock.endCodeAddress; 242 243 if (endAddress == currentEndAddress) { 244 //|-----| 245 //------^ 246 /*Bam! We hit the end right on the head... err, tail.*/ 247 return new TryBounds(startBlock, tryBlock); 248 } else if (endAddress > currentStartAddress && endAddress < currentEndAddress) { 249 //|-----| 250 //--^ 251 /*Almost. The range being added ends in the middle of an 252 existing range. We need to split the existing range 253 at the end of the range being added.*/ 254 tryBlock.split(endAddress); 255 return new TryBounds(startBlock, tryBlock); 256 } else if (endAddress <= currentStartAddress) { 257 //|-----| |-----| 258 //-----------^ 259 /*Oops, too far! The current range starts after the range being added 260 ends. We need to create a new range that starts at the end of the 261 previous range, and ends at the end of the range being added*/ 262 MutableTryBlock endBlock = new MutableTryBlock(tryBlock.prev.endCodeAddress, endAddress); 263 tryBlock.prepend(endBlock); 264 return new TryBounds(startBlock, endBlock); 265 } 266 tryBlock = tryBlock.next; 267 } 268 269 //|-----| 270 //--------^ 271 /*The last range in the list ended before the end of the range being added. 272 We need to add a new range that starts at the end of the last range in the 273 list, and ends at the end of the range being added.*/ 274 MutableTryBlock endBlock = new MutableTryBlock(listEnd.prev.endCodeAddress, endAddress); 275 listEnd.prepend(endBlock); 276 return new TryBounds(startBlock, endBlock); 277 } 278 279 public void addHandler(String type, int startAddress, int endAddress, int handlerAddress) { 280 TryBounds bounds = getBoundingRanges(startAddress, endAddress); 281 282 MutableTryBlock startBlock = bounds.start; 283 MutableTryBlock endBlock = bounds.end; 284 285 ExceptionHandler handler = new ImmutableExceptionHandler(type, handlerAddress); 286 287 int previousEnd = startAddress; 288 MutableTryBlock tryBlock = startBlock; 289 290 /*Now we have the start and end ranges that exactly match the start and end 291 of the range being added. We need to iterate over all the ranges from the start 292 to end range inclusively, and append the handler to the end of each range's handler 293 list. We also need to create a new range for any "holes" in the existing ranges*/ 294 do 295 { 296 //is there a hole? If so, add a new range to fill the hole 297 if (tryBlock.startCodeAddress > previousEnd) { 298 MutableTryBlock newBlock = new MutableTryBlock(previousEnd, tryBlock.startCodeAddress); 299 tryBlock.prepend(newBlock); 300 tryBlock = newBlock; 301 } 302 303 tryBlock.addHandler(handler); 304 previousEnd = tryBlock.endCodeAddress; 305 tryBlock = tryBlock.next; 306 } while (tryBlock.prev != endBlock); 307 } 308 309 public List<TryBlock> getTryBlocks() { 310 return Lists.newArrayList(new Iterator<TryBlock>() { 311 // The next TryBlock to return. This has already been merged, if needed. 312 @Nullable private MutableTryBlock next; 313 314 { 315 next = listStart; 316 next = readNextItem(); 317 } 318 319 /** 320 * Read the item that comes after the current value of the next field. 321 * @return The next item, or null if there is no next item 322 */ 323 @Nullable protected MutableTryBlock readNextItem() { 324 // We can assume that next is not null 325 MutableTryBlock ret = next.next; 326 327 if (ret == listEnd) { 328 return null; 329 } 330 331 while (ret.next != listEnd) { 332 if (ret.endCodeAddress == ret.next.startCodeAddress && 333 ret.getExceptionHandlers().equals(ret.next.getExceptionHandlers())) { 334 ret.mergeNext(); 335 } else { 336 break; 337 } 338 } 339 return ret; 340 } 341 342 @Override public boolean hasNext() { 343 return next != null; 344 } 345 346 @Override public TryBlock next() { 347 if (!hasNext()) { 348 throw new NoSuchElementException(); 349 } 350 TryBlock ret = next; 351 next = readNextItem(); 352 return ret; 353 } 354 355 @Override public void remove() { 356 throw new UnsupportedOperationException(); 357 } 358 }); 359 } 360} 361