15916df99999ae58f707d829792ef3997546628fdBen Gruver/* 25916df99999ae58f707d829792ef3997546628fdBen Gruver * Copyright 2013, Google Inc. 35916df99999ae58f707d829792ef3997546628fdBen Gruver * All rights reserved. 45916df99999ae58f707d829792ef3997546628fdBen Gruver * 55916df99999ae58f707d829792ef3997546628fdBen Gruver * Redistribution and use in source and binary forms, with or without 65916df99999ae58f707d829792ef3997546628fdBen Gruver * modification, are permitted provided that the following conditions are 75916df99999ae58f707d829792ef3997546628fdBen Gruver * met: 85916df99999ae58f707d829792ef3997546628fdBen Gruver * 95916df99999ae58f707d829792ef3997546628fdBen Gruver * * Redistributions of source code must retain the above copyright 105916df99999ae58f707d829792ef3997546628fdBen Gruver * notice, this list of conditions and the following disclaimer. 115916df99999ae58f707d829792ef3997546628fdBen Gruver * * Redistributions in binary form must reproduce the above 125916df99999ae58f707d829792ef3997546628fdBen Gruver * copyright notice, this list of conditions and the following disclaimer 135916df99999ae58f707d829792ef3997546628fdBen Gruver * in the documentation and/or other materials provided with the 145916df99999ae58f707d829792ef3997546628fdBen Gruver * distribution. 155916df99999ae58f707d829792ef3997546628fdBen Gruver * * Neither the name of Google Inc. nor the names of its 165916df99999ae58f707d829792ef3997546628fdBen Gruver * contributors may be used to endorse or promote products derived from 175916df99999ae58f707d829792ef3997546628fdBen Gruver * this software without specific prior written permission. 185916df99999ae58f707d829792ef3997546628fdBen Gruver * 195916df99999ae58f707d829792ef3997546628fdBen Gruver * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 205916df99999ae58f707d829792ef3997546628fdBen Gruver * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 215916df99999ae58f707d829792ef3997546628fdBen Gruver * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 225916df99999ae58f707d829792ef3997546628fdBen Gruver * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 235916df99999ae58f707d829792ef3997546628fdBen Gruver * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 245916df99999ae58f707d829792ef3997546628fdBen Gruver * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 255916df99999ae58f707d829792ef3997546628fdBen Gruver * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 265916df99999ae58f707d829792ef3997546628fdBen Gruver * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 275916df99999ae58f707d829792ef3997546628fdBen Gruver * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 285916df99999ae58f707d829792ef3997546628fdBen Gruver * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 295916df99999ae58f707d829792ef3997546628fdBen Gruver * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 305916df99999ae58f707d829792ef3997546628fdBen Gruver */ 315916df99999ae58f707d829792ef3997546628fdBen Gruver 325916df99999ae58f707d829792ef3997546628fdBen Gruverpackage org.jf.dexlib2.writer.util; 335916df99999ae58f707d829792ef3997546628fdBen Gruver 345916df99999ae58f707d829792ef3997546628fdBen Gruverimport com.google.common.collect.Lists; 355916df99999ae58f707d829792ef3997546628fdBen Gruverimport org.jf.dexlib2.base.BaseTryBlock; 365916df99999ae58f707d829792ef3997546628fdBen Gruverimport org.jf.dexlib2.iface.ExceptionHandler; 375916df99999ae58f707d829792ef3997546628fdBen Gruverimport org.jf.dexlib2.iface.TryBlock; 385916df99999ae58f707d829792ef3997546628fdBen Gruverimport org.jf.util.ExceptionWithContext; 395916df99999ae58f707d829792ef3997546628fdBen Gruver 405916df99999ae58f707d829792ef3997546628fdBen Gruverimport javax.annotation.Nonnull; 418c3d16b7ee368c14e805077d047162f3bb434193Ben Gruverimport javax.annotation.Nullable; 425916df99999ae58f707d829792ef3997546628fdBen Gruverimport java.util.Iterator; 435916df99999ae58f707d829792ef3997546628fdBen Gruverimport java.util.List; 445916df99999ae58f707d829792ef3997546628fdBen Gruverimport java.util.NoSuchElementException; 455916df99999ae58f707d829792ef3997546628fdBen Gruver 461bf6f2324541df184689fdb2c0d8188af5221784Ben Gruverpublic class TryListBuilder<EH extends ExceptionHandler> 475916df99999ae58f707d829792ef3997546628fdBen Gruver{ 485916df99999ae58f707d829792ef3997546628fdBen Gruver // Linked list sentinels that don't represent an actual try block 495916df99999ae58f707d829792ef3997546628fdBen Gruver // Their values are never modified, only their links 501bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver private final MutableTryBlock<EH> listStart; 511bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver private final MutableTryBlock<EH> listEnd; 525916df99999ae58f707d829792ef3997546628fdBen Gruver 535916df99999ae58f707d829792ef3997546628fdBen Gruver public TryListBuilder() { 541bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver listStart = new MutableTryBlock<EH>(0, 0); 551bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver listEnd = new MutableTryBlock<EH>(0, 0); 565916df99999ae58f707d829792ef3997546628fdBen Gruver listStart.next = listEnd; 575916df99999ae58f707d829792ef3997546628fdBen Gruver listEnd.prev = listStart; 585916df99999ae58f707d829792ef3997546628fdBen Gruver } 595916df99999ae58f707d829792ef3997546628fdBen Gruver 601bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver public static <EH extends ExceptionHandler> List<TryBlock<EH>> massageTryBlocks( 611bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver List<? extends TryBlock<? extends EH>> tryBlocks) { 621bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver TryListBuilder<EH> tlb = new TryListBuilder<EH>(); 631bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver 641bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver for (TryBlock<? extends EH> tryBlock: tryBlocks) { 65ab73502b60fadc966ba3ace0aa4b62592cf2ae86Ben Gruver int startAddress = tryBlock.getStartCodeAddress(); 66ab73502b60fadc966ba3ace0aa4b62592cf2ae86Ben Gruver int endAddress = startAddress + tryBlock.getCodeUnitCount(); 67ab73502b60fadc966ba3ace0aa4b62592cf2ae86Ben Gruver 681bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver for (EH exceptionHandler: tryBlock.getExceptionHandlers()) { 691bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver tlb.addHandler(startAddress, endAddress, exceptionHandler); 70ab73502b60fadc966ba3ace0aa4b62592cf2ae86Ben Gruver } 71ab73502b60fadc966ba3ace0aa4b62592cf2ae86Ben Gruver } 72ab73502b60fadc966ba3ace0aa4b62592cf2ae86Ben Gruver return tlb.getTryBlocks(); 73ab73502b60fadc966ba3ace0aa4b62592cf2ae86Ben Gruver } 74ab73502b60fadc966ba3ace0aa4b62592cf2ae86Ben Gruver 751bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver private static class TryBounds<EH extends ExceptionHandler> { 761bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver @Nonnull public final MutableTryBlock<EH> start; 771bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver @Nonnull public final MutableTryBlock<EH> end; 785916df99999ae58f707d829792ef3997546628fdBen Gruver 791bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver public TryBounds(@Nonnull MutableTryBlock<EH> start, @Nonnull MutableTryBlock<EH> end) { 805916df99999ae58f707d829792ef3997546628fdBen Gruver this.start = start; 815916df99999ae58f707d829792ef3997546628fdBen Gruver this.end = end; 825916df99999ae58f707d829792ef3997546628fdBen Gruver } 835916df99999ae58f707d829792ef3997546628fdBen Gruver } 845916df99999ae58f707d829792ef3997546628fdBen Gruver 855916df99999ae58f707d829792ef3997546628fdBen Gruver public static class InvalidTryException extends ExceptionWithContext { 865916df99999ae58f707d829792ef3997546628fdBen Gruver public InvalidTryException(Throwable cause) { 875916df99999ae58f707d829792ef3997546628fdBen Gruver super(cause); 885916df99999ae58f707d829792ef3997546628fdBen Gruver } 895916df99999ae58f707d829792ef3997546628fdBen Gruver 905916df99999ae58f707d829792ef3997546628fdBen Gruver public InvalidTryException(Throwable cause, String message, Object... formatArgs) { 915916df99999ae58f707d829792ef3997546628fdBen Gruver super(cause, message, formatArgs); 925916df99999ae58f707d829792ef3997546628fdBen Gruver } 935916df99999ae58f707d829792ef3997546628fdBen Gruver 945916df99999ae58f707d829792ef3997546628fdBen Gruver public InvalidTryException(String message, Object... formatArgs) { 955916df99999ae58f707d829792ef3997546628fdBen Gruver super(message, formatArgs); 965916df99999ae58f707d829792ef3997546628fdBen Gruver } 975916df99999ae58f707d829792ef3997546628fdBen Gruver } 985916df99999ae58f707d829792ef3997546628fdBen Gruver 991bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver private static class MutableTryBlock<EH extends ExceptionHandler> extends BaseTryBlock<EH> { 1001bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver public MutableTryBlock<EH> prev = null; 1011bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver public MutableTryBlock<EH> next = null; 1025916df99999ae58f707d829792ef3997546628fdBen Gruver 1035916df99999ae58f707d829792ef3997546628fdBen Gruver public int startCodeAddress; 1045916df99999ae58f707d829792ef3997546628fdBen Gruver public int endCodeAddress; 1051bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver @Nonnull public List<EH> exceptionHandlers = Lists.newArrayList(); 1065916df99999ae58f707d829792ef3997546628fdBen Gruver 1075916df99999ae58f707d829792ef3997546628fdBen Gruver public MutableTryBlock(int startCodeAddress, int endCodeAddress) { 1085916df99999ae58f707d829792ef3997546628fdBen Gruver this.startCodeAddress = startCodeAddress; 1095916df99999ae58f707d829792ef3997546628fdBen Gruver this.endCodeAddress = endCodeAddress; 1105916df99999ae58f707d829792ef3997546628fdBen Gruver } 1115916df99999ae58f707d829792ef3997546628fdBen Gruver 1125916df99999ae58f707d829792ef3997546628fdBen Gruver public MutableTryBlock(int startCodeAddress, int endCodeAddress, 1131bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver @Nonnull List<EH> exceptionHandlers) { 1145916df99999ae58f707d829792ef3997546628fdBen Gruver this.startCodeAddress = startCodeAddress; 1155916df99999ae58f707d829792ef3997546628fdBen Gruver this.endCodeAddress = endCodeAddress; 1165916df99999ae58f707d829792ef3997546628fdBen Gruver this.exceptionHandlers = Lists.newArrayList(exceptionHandlers); 1175916df99999ae58f707d829792ef3997546628fdBen Gruver } 1185916df99999ae58f707d829792ef3997546628fdBen Gruver 1195916df99999ae58f707d829792ef3997546628fdBen Gruver @Override public int getStartCodeAddress() { 1205916df99999ae58f707d829792ef3997546628fdBen Gruver return startCodeAddress; 1215916df99999ae58f707d829792ef3997546628fdBen Gruver } 1225916df99999ae58f707d829792ef3997546628fdBen Gruver 1235916df99999ae58f707d829792ef3997546628fdBen Gruver @Override public int getCodeUnitCount() { 1245916df99999ae58f707d829792ef3997546628fdBen Gruver return endCodeAddress - startCodeAddress; 1255916df99999ae58f707d829792ef3997546628fdBen Gruver } 1265916df99999ae58f707d829792ef3997546628fdBen Gruver 1271bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver @Nonnull @Override public List<EH> getExceptionHandlers() { 1285916df99999ae58f707d829792ef3997546628fdBen Gruver return exceptionHandlers; 1295916df99999ae58f707d829792ef3997546628fdBen Gruver } 1305916df99999ae58f707d829792ef3997546628fdBen Gruver 1315916df99999ae58f707d829792ef3997546628fdBen Gruver @Nonnull 1321bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver public MutableTryBlock<EH> split(int splitAddress) { 1331bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver MutableTryBlock<EH> newTryBlock = new MutableTryBlock<EH>(splitAddress, endCodeAddress, exceptionHandlers); 1345916df99999ae58f707d829792ef3997546628fdBen Gruver endCodeAddress = splitAddress; 1355916df99999ae58f707d829792ef3997546628fdBen Gruver append(newTryBlock); 1365916df99999ae58f707d829792ef3997546628fdBen Gruver return newTryBlock; 1375916df99999ae58f707d829792ef3997546628fdBen Gruver } 1385916df99999ae58f707d829792ef3997546628fdBen Gruver 1398c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver public void delete() { 1408c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver next.prev = prev; 1418c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver prev.next = next; 1428c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver } 1438c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver 1448c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver public void mergeNext() { 1458c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver //assert next.startCodeAddress == this.endCodeAddress; 1468c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver this.endCodeAddress = next.endCodeAddress; 1478c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver next.delete(); 1488c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver } 1498c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver 1501bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver public void append(@Nonnull MutableTryBlock<EH> tryBlock) { 1515916df99999ae58f707d829792ef3997546628fdBen Gruver next.prev = tryBlock; 1525916df99999ae58f707d829792ef3997546628fdBen Gruver tryBlock.next = next; 1535916df99999ae58f707d829792ef3997546628fdBen Gruver tryBlock.prev = this; 1545916df99999ae58f707d829792ef3997546628fdBen Gruver next = tryBlock; 1555916df99999ae58f707d829792ef3997546628fdBen Gruver } 1565916df99999ae58f707d829792ef3997546628fdBen Gruver 1571bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver public void prepend(@Nonnull MutableTryBlock<EH> tryBlock) { 1585916df99999ae58f707d829792ef3997546628fdBen Gruver prev.next = tryBlock; 1595916df99999ae58f707d829792ef3997546628fdBen Gruver tryBlock.prev = prev; 1605916df99999ae58f707d829792ef3997546628fdBen Gruver tryBlock.next = this; 1615916df99999ae58f707d829792ef3997546628fdBen Gruver prev = tryBlock; 1625916df99999ae58f707d829792ef3997546628fdBen Gruver } 1635916df99999ae58f707d829792ef3997546628fdBen Gruver 1641bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver public void addHandler(@Nonnull EH handler) { 1655916df99999ae58f707d829792ef3997546628fdBen Gruver for (ExceptionHandler existingHandler: exceptionHandlers) { 1665916df99999ae58f707d829792ef3997546628fdBen Gruver String existingType = existingHandler.getExceptionType(); 1675916df99999ae58f707d829792ef3997546628fdBen Gruver String newType = handler.getExceptionType(); 1685916df99999ae58f707d829792ef3997546628fdBen Gruver 1695916df99999ae58f707d829792ef3997546628fdBen Gruver if (existingType == null) { 1705916df99999ae58f707d829792ef3997546628fdBen Gruver if (newType == null) { 1715916df99999ae58f707d829792ef3997546628fdBen Gruver if (existingHandler.getHandlerCodeAddress() != handler.getHandlerCodeAddress()) { 1725916df99999ae58f707d829792ef3997546628fdBen Gruver throw new InvalidTryException( 1735916df99999ae58f707d829792ef3997546628fdBen Gruver "Multiple overlapping catch all handlers with different handlers"); 1745916df99999ae58f707d829792ef3997546628fdBen Gruver } 1755916df99999ae58f707d829792ef3997546628fdBen Gruver return; 1765916df99999ae58f707d829792ef3997546628fdBen Gruver } 1775916df99999ae58f707d829792ef3997546628fdBen Gruver } else if (existingType.equals(newType)) { 1780d8418ff1f253471dc5f579ec5b4976c08649a09Ben Gruver // dalvik doesn't reject cases when there are multiple catches with the same exception 1790d8418ff1f253471dc5f579ec5b4976c08649a09Ben Gruver // but different handlers. In practice, the first handler "wins". Since the later 1800d8418ff1f253471dc5f579ec5b4976c08649a09Ben Gruver // handler will never be used, we don't add it. 1815916df99999ae58f707d829792ef3997546628fdBen Gruver return; 1825916df99999ae58f707d829792ef3997546628fdBen Gruver } 1835916df99999ae58f707d829792ef3997546628fdBen Gruver } 1845916df99999ae58f707d829792ef3997546628fdBen Gruver 1855916df99999ae58f707d829792ef3997546628fdBen Gruver exceptionHandlers.add(handler); 1865916df99999ae58f707d829792ef3997546628fdBen Gruver } 1875916df99999ae58f707d829792ef3997546628fdBen Gruver } 1885916df99999ae58f707d829792ef3997546628fdBen Gruver 1891bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver private TryBounds<EH> getBoundingRanges(int startAddress, int endAddress) { 1901bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver MutableTryBlock<EH> startBlock = null; 1915916df99999ae58f707d829792ef3997546628fdBen Gruver 1921bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver MutableTryBlock<EH> tryBlock = listStart.next; 1935916df99999ae58f707d829792ef3997546628fdBen Gruver while (tryBlock != listEnd) { 1945916df99999ae58f707d829792ef3997546628fdBen Gruver int currentStartAddress = tryBlock.startCodeAddress; 1955916df99999ae58f707d829792ef3997546628fdBen Gruver int currentEndAddress = tryBlock.endCodeAddress; 1965916df99999ae58f707d829792ef3997546628fdBen Gruver 1975916df99999ae58f707d829792ef3997546628fdBen Gruver if (startAddress == currentStartAddress) { 1985916df99999ae58f707d829792ef3997546628fdBen Gruver //|-----| 1995916df99999ae58f707d829792ef3997546628fdBen Gruver //^------ 2005916df99999ae58f707d829792ef3997546628fdBen Gruver /*Bam. We hit the start of the range right on the head*/ 2015916df99999ae58f707d829792ef3997546628fdBen Gruver startBlock = tryBlock; 2025916df99999ae58f707d829792ef3997546628fdBen Gruver break; 2035916df99999ae58f707d829792ef3997546628fdBen Gruver } else if (startAddress > currentStartAddress && startAddress < currentEndAddress) { 2045916df99999ae58f707d829792ef3997546628fdBen Gruver //|-----| 2055916df99999ae58f707d829792ef3997546628fdBen Gruver // ^---- 2065916df99999ae58f707d829792ef3997546628fdBen Gruver /*Almost. The start of the range being added is in the middle 2075916df99999ae58f707d829792ef3997546628fdBen Gruver of an existing try range. We need to split the existing range 2085916df99999ae58f707d829792ef3997546628fdBen Gruver at the start address of the range being added*/ 2095916df99999ae58f707d829792ef3997546628fdBen Gruver startBlock = tryBlock.split(startAddress); 2105916df99999ae58f707d829792ef3997546628fdBen Gruver break; 2115916df99999ae58f707d829792ef3997546628fdBen Gruver }else if (startAddress < currentStartAddress) { 2125916df99999ae58f707d829792ef3997546628fdBen Gruver if (endAddress <= currentStartAddress) { 2135916df99999ae58f707d829792ef3997546628fdBen Gruver // |-----| 2145916df99999ae58f707d829792ef3997546628fdBen Gruver //^--^ 2155916df99999ae58f707d829792ef3997546628fdBen Gruver /*Oops, totally too far! The new range doesn't overlap any existing 2165916df99999ae58f707d829792ef3997546628fdBen Gruver ones, so we just add it and return*/ 2171bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver startBlock = new MutableTryBlock<EH>(startAddress, endAddress); 2185916df99999ae58f707d829792ef3997546628fdBen Gruver tryBlock.prepend(startBlock); 2191bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver return new TryBounds<EH>(startBlock, startBlock); 2205916df99999ae58f707d829792ef3997546628fdBen Gruver } else { 2215916df99999ae58f707d829792ef3997546628fdBen Gruver // |-----| 2225916df99999ae58f707d829792ef3997546628fdBen Gruver //^--------- 2235916df99999ae58f707d829792ef3997546628fdBen Gruver /*Oops, too far! We've passed the start of the range being added, but 2245916df99999ae58f707d829792ef3997546628fdBen Gruver the new range does overlap this one. We need to add a new range just 2255916df99999ae58f707d829792ef3997546628fdBen Gruver before this one*/ 2261bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver startBlock = new MutableTryBlock<EH>(startAddress, currentStartAddress); 2275916df99999ae58f707d829792ef3997546628fdBen Gruver tryBlock.prepend(startBlock); 2285916df99999ae58f707d829792ef3997546628fdBen Gruver break; 2295916df99999ae58f707d829792ef3997546628fdBen Gruver } 2305916df99999ae58f707d829792ef3997546628fdBen Gruver } 2315916df99999ae58f707d829792ef3997546628fdBen Gruver 2325916df99999ae58f707d829792ef3997546628fdBen Gruver tryBlock = tryBlock.next; 2335916df99999ae58f707d829792ef3997546628fdBen Gruver } 2345916df99999ae58f707d829792ef3997546628fdBen Gruver 2355916df99999ae58f707d829792ef3997546628fdBen Gruver //|-----| 2365916df99999ae58f707d829792ef3997546628fdBen Gruver // ^----- 2375916df99999ae58f707d829792ef3997546628fdBen Gruver /*Either the list of tries is blank, or all the tries in the list 2385916df99999ae58f707d829792ef3997546628fdBen Gruver end before the range being added starts. In either case, we just need 2395916df99999ae58f707d829792ef3997546628fdBen Gruver to add a new range at the end of the list*/ 2405916df99999ae58f707d829792ef3997546628fdBen Gruver if (startBlock == null) { 2411bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver startBlock = new MutableTryBlock<EH>(startAddress, endAddress); 2425916df99999ae58f707d829792ef3997546628fdBen Gruver listEnd.prepend(startBlock); 2431bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver return new TryBounds<EH>(startBlock, startBlock); 2445916df99999ae58f707d829792ef3997546628fdBen Gruver } 2455916df99999ae58f707d829792ef3997546628fdBen Gruver 2465916df99999ae58f707d829792ef3997546628fdBen Gruver tryBlock = startBlock; 2475916df99999ae58f707d829792ef3997546628fdBen Gruver while (tryBlock != listEnd) { 2485916df99999ae58f707d829792ef3997546628fdBen Gruver int currentStartAddress = tryBlock.startCodeAddress; 2495916df99999ae58f707d829792ef3997546628fdBen Gruver int currentEndAddress = tryBlock.endCodeAddress; 2505916df99999ae58f707d829792ef3997546628fdBen Gruver 2515916df99999ae58f707d829792ef3997546628fdBen Gruver if (endAddress == currentEndAddress) { 2525916df99999ae58f707d829792ef3997546628fdBen Gruver //|-----| 2535916df99999ae58f707d829792ef3997546628fdBen Gruver //------^ 2545916df99999ae58f707d829792ef3997546628fdBen Gruver /*Bam! We hit the end right on the head... err, tail.*/ 2551bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver return new TryBounds<EH>(startBlock, tryBlock); 2565916df99999ae58f707d829792ef3997546628fdBen Gruver } else if (endAddress > currentStartAddress && endAddress < currentEndAddress) { 2575916df99999ae58f707d829792ef3997546628fdBen Gruver //|-----| 2585916df99999ae58f707d829792ef3997546628fdBen Gruver //--^ 2595916df99999ae58f707d829792ef3997546628fdBen Gruver /*Almost. The range being added ends in the middle of an 2605916df99999ae58f707d829792ef3997546628fdBen Gruver existing range. We need to split the existing range 2615916df99999ae58f707d829792ef3997546628fdBen Gruver at the end of the range being added.*/ 2625916df99999ae58f707d829792ef3997546628fdBen Gruver tryBlock.split(endAddress); 2631bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver return new TryBounds<EH>(startBlock, tryBlock); 2645916df99999ae58f707d829792ef3997546628fdBen Gruver } else if (endAddress <= currentStartAddress) { 2655916df99999ae58f707d829792ef3997546628fdBen Gruver //|-----| |-----| 2665916df99999ae58f707d829792ef3997546628fdBen Gruver //-----------^ 2675916df99999ae58f707d829792ef3997546628fdBen Gruver /*Oops, too far! The current range starts after the range being added 2685916df99999ae58f707d829792ef3997546628fdBen Gruver ends. We need to create a new range that starts at the end of the 2695916df99999ae58f707d829792ef3997546628fdBen Gruver previous range, and ends at the end of the range being added*/ 2701bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver MutableTryBlock<EH> endBlock = new MutableTryBlock<EH>(tryBlock.prev.endCodeAddress, endAddress); 2715916df99999ae58f707d829792ef3997546628fdBen Gruver tryBlock.prepend(endBlock); 2721bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver return new TryBounds<EH>(startBlock, endBlock); 2735916df99999ae58f707d829792ef3997546628fdBen Gruver } 2745916df99999ae58f707d829792ef3997546628fdBen Gruver tryBlock = tryBlock.next; 2755916df99999ae58f707d829792ef3997546628fdBen Gruver } 2765916df99999ae58f707d829792ef3997546628fdBen Gruver 2775916df99999ae58f707d829792ef3997546628fdBen Gruver //|-----| 2785916df99999ae58f707d829792ef3997546628fdBen Gruver //--------^ 2795916df99999ae58f707d829792ef3997546628fdBen Gruver /*The last range in the list ended before the end of the range being added. 2805916df99999ae58f707d829792ef3997546628fdBen Gruver We need to add a new range that starts at the end of the last range in the 2815916df99999ae58f707d829792ef3997546628fdBen Gruver list, and ends at the end of the range being added.*/ 2821bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver MutableTryBlock<EH> endBlock = new MutableTryBlock<EH>(listEnd.prev.endCodeAddress, endAddress); 2835916df99999ae58f707d829792ef3997546628fdBen Gruver listEnd.prepend(endBlock); 2841bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver return new TryBounds<EH>(startBlock, endBlock); 2855916df99999ae58f707d829792ef3997546628fdBen Gruver } 2865916df99999ae58f707d829792ef3997546628fdBen Gruver 2871bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver public void addHandler(int startAddress, int endAddress, EH handler) { 2881bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver TryBounds<EH> bounds = getBoundingRanges(startAddress, endAddress); 2895916df99999ae58f707d829792ef3997546628fdBen Gruver 2901bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver MutableTryBlock<EH> startBlock = bounds.start; 2911bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver MutableTryBlock<EH> endBlock = bounds.end; 2925916df99999ae58f707d829792ef3997546628fdBen Gruver 2935916df99999ae58f707d829792ef3997546628fdBen Gruver int previousEnd = startAddress; 2941bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver MutableTryBlock<EH> tryBlock = startBlock; 2955916df99999ae58f707d829792ef3997546628fdBen Gruver 2965916df99999ae58f707d829792ef3997546628fdBen Gruver /*Now we have the start and end ranges that exactly match the start and end 2975916df99999ae58f707d829792ef3997546628fdBen Gruver of the range being added. We need to iterate over all the ranges from the start 2985916df99999ae58f707d829792ef3997546628fdBen Gruver to end range inclusively, and append the handler to the end of each range's handler 2995916df99999ae58f707d829792ef3997546628fdBen Gruver list. We also need to create a new range for any "holes" in the existing ranges*/ 3005916df99999ae58f707d829792ef3997546628fdBen Gruver do 3015916df99999ae58f707d829792ef3997546628fdBen Gruver { 3025916df99999ae58f707d829792ef3997546628fdBen Gruver //is there a hole? If so, add a new range to fill the hole 3035916df99999ae58f707d829792ef3997546628fdBen Gruver if (tryBlock.startCodeAddress > previousEnd) { 3041bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver MutableTryBlock<EH> newBlock = new MutableTryBlock<EH>(previousEnd, tryBlock.startCodeAddress); 3055916df99999ae58f707d829792ef3997546628fdBen Gruver tryBlock.prepend(newBlock); 3065916df99999ae58f707d829792ef3997546628fdBen Gruver tryBlock = newBlock; 3075916df99999ae58f707d829792ef3997546628fdBen Gruver } 3085916df99999ae58f707d829792ef3997546628fdBen Gruver 3095916df99999ae58f707d829792ef3997546628fdBen Gruver tryBlock.addHandler(handler); 3105916df99999ae58f707d829792ef3997546628fdBen Gruver previousEnd = tryBlock.endCodeAddress; 3115916df99999ae58f707d829792ef3997546628fdBen Gruver tryBlock = tryBlock.next; 3125916df99999ae58f707d829792ef3997546628fdBen Gruver } while (tryBlock.prev != endBlock); 3135916df99999ae58f707d829792ef3997546628fdBen Gruver } 3145916df99999ae58f707d829792ef3997546628fdBen Gruver 3151bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver public List<TryBlock<EH>> getTryBlocks() { 3161bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver return Lists.newArrayList(new Iterator<TryBlock<EH>>() { 3178c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver // The next TryBlock to return. This has already been merged, if needed. 3181bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver @Nullable private MutableTryBlock<EH> next; 3198c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver 3208c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver { 3218c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver next = listStart; 3228c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver next = readNextItem(); 3238c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver } 3248c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver 3258c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver /** 3268c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver * Read the item that comes after the current value of the next field. 3278c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver * @return The next item, or null if there is no next item 3288c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver */ 3291bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver @Nullable protected MutableTryBlock<EH> readNextItem() { 3301bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver // We can assume that next is not null, due to the way iteration happens 3311bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver MutableTryBlock<EH> ret = next.next; 3328c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver 3338c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver if (ret == listEnd) { 3348c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver return null; 3358c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver } 3368c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver 3378c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver while (ret.next != listEnd) { 3388c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver if (ret.endCodeAddress == ret.next.startCodeAddress && 3398c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver ret.getExceptionHandlers().equals(ret.next.getExceptionHandlers())) { 3408c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver ret.mergeNext(); 3418c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver } else { 3428c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver break; 3438c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver } 3448c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver } 3458c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver return ret; 3468c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver } 3475916df99999ae58f707d829792ef3997546628fdBen Gruver 3485916df99999ae58f707d829792ef3997546628fdBen Gruver @Override public boolean hasNext() { 3498c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver return next != null; 3505916df99999ae58f707d829792ef3997546628fdBen Gruver } 3515916df99999ae58f707d829792ef3997546628fdBen Gruver 3521bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver @Override @Nonnull public TryBlock<EH> next() { 3535916df99999ae58f707d829792ef3997546628fdBen Gruver if (!hasNext()) { 3545916df99999ae58f707d829792ef3997546628fdBen Gruver throw new NoSuchElementException(); 3555916df99999ae58f707d829792ef3997546628fdBen Gruver } 3561bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver TryBlock<EH> ret = next; 3578c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver next = readNextItem(); 3581bf6f2324541df184689fdb2c0d8188af5221784Ben Gruver // ret can't be null (ret=next and hasNext returned true) 3598c3d16b7ee368c14e805077d047162f3bb434193Ben Gruver return ret; 3605916df99999ae58f707d829792ef3997546628fdBen Gruver } 3615916df99999ae58f707d829792ef3997546628fdBen Gruver 3625916df99999ae58f707d829792ef3997546628fdBen Gruver @Override public void remove() { 3635916df99999ae58f707d829792ef3997546628fdBen Gruver throw new UnsupportedOperationException(); 3645916df99999ae58f707d829792ef3997546628fdBen Gruver } 3655916df99999ae58f707d829792ef3997546628fdBen Gruver }); 3665916df99999ae58f707d829792ef3997546628fdBen Gruver } 3675916df99999ae58f707d829792ef3997546628fdBen Gruver} 368