writer/util/TryListBuilder.java

/*
 * Copyright 2013, Google Inc.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package org.jf.dexlib2.writer.util;

import com.google.common.collect.Lists;
import org.jf.dexlib2.base.BaseTryBlock;
import org.jf.dexlib2.iface.ExceptionHandler;
import org.jf.dexlib2.iface.TryBlock;
import org.jf.util.ExceptionWithContext;

import javax.annotation.Nonnull;
import javax.annotation.Nullable;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class TryListBuilder<EH extends ExceptionHandler>
{
    // Linked list sentinels that don't represent an actual try block
    // Their values are never modified, only their links
    private final MutableTryBlock<EH> listStart;
    private final MutableTryBlock<EH> listEnd;

    public TryListBuilder() {
        listStart = new MutableTryBlock<EH>(0, 0);
        listEnd = new MutableTryBlock<EH>(0, 0);
        listStart.next = listEnd;
        listEnd.prev = listStart;
    }

    public static <EH extends ExceptionHandler> List<TryBlock<EH>> massageTryBlocks(
            List<? extends TryBlock<? extends EH>> tryBlocks) {
        TryListBuilder<EH> tlb = new TryListBuilder<EH>();

        for (TryBlock<? extends EH> tryBlock: tryBlocks) {
            int startAddress = tryBlock.getStartCodeAddress();
            int endAddress = startAddress + tryBlock.getCodeUnitCount();

            for (EH exceptionHandler: tryBlock.getExceptionHandlers()) {
                tlb.addHandler(startAddress, endAddress, exceptionHandler);
            }
        }
        return tlb.getTryBlocks();
    }

    private static class TryBounds<EH extends ExceptionHandler> {
        @Nonnull public final MutableTryBlock<EH> start;
        @Nonnull public final MutableTryBlock<EH> end;

        public TryBounds(@Nonnull MutableTryBlock<EH> start, @Nonnull MutableTryBlock<EH> end) {
            this.start = start;
            this.end = end;
        }
    }

    public static class InvalidTryException extends ExceptionWithContext {
        public InvalidTryException(Throwable cause) {
            super(cause);
        }

        public InvalidTryException(Throwable cause, String message, Object... formatArgs) {
            super(cause, message, formatArgs);
        }

        public InvalidTryException(String message, Object... formatArgs) {
            super(message, formatArgs);
        }
    }

    private static class MutableTryBlock<EH extends ExceptionHandler> extends BaseTryBlock<EH> {
        public MutableTryBlock<EH> prev = null;
        public MutableTryBlock<EH> next = null;

        public int startCodeAddress;
        public int endCodeAddress;
        @Nonnull public List<EH> exceptionHandlers = Lists.newArrayList();

        public MutableTryBlock(int startCodeAddress, int endCodeAddress) {
            this.startCodeAddress = startCodeAddress;
            this.endCodeAddress = endCodeAddress;
        }

        public MutableTryBlock(int startCodeAddress, int endCodeAddress,
                               @Nonnull List<EH> exceptionHandlers) {
            this.startCodeAddress = startCodeAddress;
            this.endCodeAddress = endCodeAddress;
            this.exceptionHandlers = Lists.newArrayList(exceptionHandlers);
        }

        @Override public int getStartCodeAddress() {
            return startCodeAddress;
        }

        @Override public int getCodeUnitCount() {
            return endCodeAddress - startCodeAddress;
        }

        @Nonnull @Override public List<EH> getExceptionHandlers() {
            return exceptionHandlers;
        }

        @Nonnull
        public MutableTryBlock<EH> split(int splitAddress) {
            MutableTryBlock<EH> newTryBlock = new MutableTryBlock<EH>(splitAddress, endCodeAddress, exceptionHandlers);
            endCodeAddress = splitAddress;
            append(newTryBlock);
            return newTryBlock;
        }

        public void delete() {
            next.prev = prev;
            prev.next = next;
        }

        public void mergeNext() {
            //assert next.startCodeAddress == this.endCodeAddress;
            this.endCodeAddress = next.endCodeAddress;
            next.delete();
        }

        public void append(@Nonnull MutableTryBlock<EH> tryBlock) {
            next.prev = tryBlock;
            tryBlock.next = next;
            tryBlock.prev = this;
            next = tryBlock;
        }

        public void prepend(@Nonnull MutableTryBlock<EH> tryBlock) {
            prev.next = tryBlock;
            tryBlock.prev = prev;
            tryBlock.next = this;
            prev = tryBlock;
        }

        public void addHandler(@Nonnull EH handler) {
            for (ExceptionHandler existingHandler: exceptionHandlers) {
                String existingType = existingHandler.getExceptionType();
                String newType = handler.getExceptionType();

                if (existingType == null) {
                    if (newType == null) {
                        if (existingHandler.getHandlerCodeAddress() != handler.getHandlerCodeAddress()) {
                            throw new InvalidTryException(
                                    "Multiple overlapping catch all handlers with different handlers");
                        }
                        return;
                    }
                } else if (existingType.equals(newType)) {
                    // dalvik doesn't reject cases when there are multiple catches with the same exception
                    // but different handlers. In practice, the first handler "wins". Since the later
                    // handler will never be used, we don't add it.
                    return;
                }
            }

            exceptionHandlers.add(handler);
        }
    }

    private TryBounds<EH> getBoundingRanges(int startAddress, int endAddress) {
        MutableTryBlock<EH> startBlock = null;

        MutableTryBlock<EH> tryBlock = listStart.next;
        while (tryBlock != listEnd) {
            int currentStartAddress = tryBlock.startCodeAddress;
            int currentEndAddress = tryBlock.endCodeAddress;

            if (startAddress == currentStartAddress) {
                //|-----|
                //^------
                /*Bam. We hit the start of the range right on the head*/
                startBlock = tryBlock;
                break;
            } else if (startAddress > currentStartAddress && startAddress < currentEndAddress) {
                //|-----|
                //  ^----
                /*Almost. The start of the range being added is in the middle
                of an existing try range. We need to split the existing range
                at the start address of the range being added*/
                startBlock = tryBlock.split(startAddress);
                break;
            }else if (startAddress < currentStartAddress) {
                if (endAddress <= currentStartAddress) {
                    //      |-----|
                    //^--^
                    /*Oops, totally too far! The new range doesn't overlap any existing
                    ones, so we just add it and return*/
                    startBlock = new MutableTryBlock<EH>(startAddress, endAddress);
                    tryBlock.prepend(startBlock);
                    return new TryBounds<EH>(startBlock, startBlock);
                } else {
                    //   |-----|
                    //^---------
                    /*Oops, too far! We've passed the start of the range being added, but
                     the new range does overlap this one. We need to add a new range just
                     before this one*/
                    startBlock = new MutableTryBlock<EH>(startAddress, currentStartAddress);
                    tryBlock.prepend(startBlock);
                    break;
                }
            }

            tryBlock = tryBlock.next;
        }

        //|-----|
        //        ^-----
        /*Either the list of tries is blank, or all the tries in the list
        end before the range being added starts. In either case, we just need
        to add a new range at the end of the list*/
        if (startBlock == null) {
            startBlock = new MutableTryBlock<EH>(startAddress, endAddress);
            listEnd.prepend(startBlock);
            return new TryBounds<EH>(startBlock, startBlock);
        }

        tryBlock = startBlock;
        while (tryBlock != listEnd) {
            int currentStartAddress = tryBlock.startCodeAddress;
            int currentEndAddress = tryBlock.endCodeAddress;

            if (endAddress == currentEndAddress) {
                //|-----|
                //------^
                /*Bam! We hit the end right on the head... err, tail.*/
                return new TryBounds<EH>(startBlock, tryBlock);
            } else if (endAddress > currentStartAddress && endAddress < currentEndAddress) {
                //|-----|
                //--^
                /*Almost. The range being added ends in the middle of an
                existing range. We need to split the existing range
                at the end of the range being added.*/
                tryBlock.split(endAddress);
                return new TryBounds<EH>(startBlock, tryBlock);
            } else if (endAddress <= currentStartAddress) {
                //|-----|       |-----|
                //-----------^
                /*Oops, too far! The current range starts after the range being added
                ends. We need to create a new range that starts at the end of the
                previous range, and ends at the end of the range being added*/
                MutableTryBlock<EH> endBlock = new MutableTryBlock<EH>(tryBlock.prev.endCodeAddress, endAddress);
                tryBlock.prepend(endBlock);
                return new TryBounds<EH>(startBlock, endBlock);
            }
            tryBlock = tryBlock.next;
        }

        //|-----|
        //--------^
        /*The last range in the list ended before the end of the range being added.
        We need to add a new range that starts at the end of the last range in the
        list, and ends at the end of the range being added.*/
        MutableTryBlock<EH> endBlock = new MutableTryBlock<EH>(listEnd.prev.endCodeAddress, endAddress);
        listEnd.prepend(endBlock);
        return new TryBounds<EH>(startBlock, endBlock);
    }

    public void addHandler(int startAddress, int endAddress, EH handler) {
        TryBounds<EH> bounds = getBoundingRanges(startAddress, endAddress);

        MutableTryBlock<EH> startBlock = bounds.start;
        MutableTryBlock<EH> endBlock = bounds.end;

        int previousEnd = startAddress;
        MutableTryBlock<EH> tryBlock = startBlock;

        /*Now we have the start and end ranges that exactly match the start and end
        of the range being added. We need to iterate over all the ranges from the start
        to end range inclusively, and append the handler to the end of each range's handler
        list. We also need to create a new range for any "holes" in the existing ranges*/
        do
        {
            //is there a hole? If so, add a new range to fill the hole
            if (tryBlock.startCodeAddress > previousEnd) {
                MutableTryBlock<EH> newBlock = new MutableTryBlock<EH>(previousEnd, tryBlock.startCodeAddress);
                tryBlock.prepend(newBlock);
                tryBlock = newBlock;
            }

            tryBlock.addHandler(handler);
            previousEnd = tryBlock.endCodeAddress;
            tryBlock = tryBlock.next;
        } while (tryBlock.prev != endBlock);
    }

    public List<TryBlock<EH>> getTryBlocks() {
        return Lists.newArrayList(new Iterator<TryBlock<EH>>() {
            // The next TryBlock to return. This has already been merged, if needed.
            @Nullable private MutableTryBlock<EH> next;

            {
                next = listStart;
                next = readNextItem();
            }

            /**
             * Read the item that comes after the current value of the next field.
             * @return The next item, or null if there is no next item
             */
            @Nullable protected MutableTryBlock<EH> readNextItem() {
                // We can assume that next is not null, due to the way iteration happens
                MutableTryBlock<EH> ret = next.next;

                if (ret == listEnd) {
                    return null;
                }

                while (ret.next != listEnd) {
                    if (ret.endCodeAddress == ret.next.startCodeAddress &&
                            ret.getExceptionHandlers().equals(ret.next.getExceptionHandlers())) {
                        ret.mergeNext();
                    } else {
                        break;
                    }
                }
                return ret;
            }

            @Override public boolean hasNext() {
                return next != null;
            }

            @Override @Nonnull public TryBlock<EH> next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                TryBlock<EH> ret = next;
                next = readNextItem();
                // ret can't be null (ret=next and hasNext returned true)
                return ret;
            }

            @Override public void remove() {
                throw new UnsupportedOperationException();
            }
        });
    }
}