dex/code/LocalList.java

/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dexgen.dex.code;

import com.android.dexgen.rop.code.RegisterSpec;
import com.android.dexgen.rop.code.RegisterSpecSet;
import com.android.dexgen.rop.cst.CstType;
import com.android.dexgen.rop.cst.CstUtf8;
import com.android.dexgen.rop.type.Type;
import com.android.dexgen.util.FixedSizeList;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;

/**
 * List of local variables. Each local variable entry indicates a
 * range of code which it is valid for, a register number, a name,
 * and a type.
 */
public final class LocalList extends FixedSizeList {
    /** {@code non-null;} empty instance */
    public static final LocalList EMPTY = new LocalList(0);

    /** whether to run the self-check code */
    private static final boolean DEBUG = false;

    /**
     * Constructs an instance. All indices initially contain {@code null}.
     *
     * @param size {@code >= 0;} the size of the list
     */
    public LocalList(int size) {
        super(size);
    }

    /**
     * Gets the element at the given index. It is an error to call
     * this with the index for an element which was never set; if you
     * do that, this will throw {@code NullPointerException}.
     *
     * @param n {@code >= 0, < size();} which index
     * @return {@code non-null;} element at that index
     */
    public Entry get(int n) {
        return (Entry) get0(n);
    }

    /**
     * Sets the entry at the given index.
     *
     * @param n {@code >= 0, < size();} which index
     * @param entry {@code non-null;} the entry to set at {@code n}
     */
    public void set(int n, Entry entry) {
        set0(n, entry);
    }

    /**
     * Does a human-friendly dump of this instance.
     *
     * @param out {@code non-null;} where to dump
     * @param prefix {@code non-null;} prefix to attach to each line of output
     */
    public void debugPrint(PrintStream out, String prefix) {
        int sz = size();

        for (int i = 0; i < sz; i++) {
            out.print(prefix);
            out.println(get(i));
        }
    }

    /**
     * Disposition of a local entry.
     */
    public static enum Disposition {
        /** local started (introduced) */
        START,

        /** local ended without being replaced */
        END_SIMPLY,

        /** local ended because it was directly replaced */
        END_REPLACED,

        /** local ended because it was moved to a different register */
        END_MOVED,

        /**
         * local ended because the previous local clobbered this one
         * (because it is category-2)
         */
        END_CLOBBERED_BY_PREV,

        /**
         * local ended because the next local clobbered this one
         * (because this one is a category-2)
         */
        END_CLOBBERED_BY_NEXT;
    }

    /**
     * Entry in a local list.
     */
    public static class Entry implements Comparable<Entry> {
        /** {@code >= 0;} address */
        private final int address;

        /** {@code non-null;} disposition of the local */
        private final Disposition disposition;

        /** {@code non-null;} register spec representing the variable */
        private final RegisterSpec spec;

        /** {@code non-null;} variable type (derived from {@code spec}) */
        private final CstType type;

        /**
         * Constructs an instance.
         *
         * @param address {@code >= 0;} address
         * @param disposition {@code non-null;} disposition of the local
         * @param spec {@code non-null;} register spec representing
         * the variable
         */
        public Entry(int address, Disposition disposition, RegisterSpec spec) {
            if (address < 0) {
                throw new IllegalArgumentException("address < 0");
            }

            if (disposition == null) {
                throw new NullPointerException("disposition == null");
            }

            try {
                if (spec.getLocalItem() == null) {
                    throw new NullPointerException(
                            "spec.getLocalItem() == null");
                }
            } catch (NullPointerException ex) {
                // Elucidate the exception.
                throw new NullPointerException("spec == null");
            }

            this.address = address;
            this.disposition = disposition;
            this.spec = spec;
            this.type = CstType.intern(spec.getType());
        }

        /** {@inheritDoc} */
        public String toString() {
            return Integer.toHexString(address) + " " + disposition + " " +
                spec;
        }

        /** {@inheritDoc} */
        public boolean equals(Object other) {
            if (!(other instanceof Entry)) {
                return false;
            }

            return (compareTo((Entry) other) == 0);
        }

        /**
         * Compares by (in priority order) address, end then start
         * disposition (variants of end are all consistered
         * equivalent), and spec.
         *
         * @param other {@code non-null;} entry to compare to
         * @return {@code -1..1;} standard result of comparison
         */
        public int compareTo(Entry other) {
            if (address < other.address) {
                return -1;
            } else if (address > other.address) {
                return 1;
            }

            boolean thisIsStart = isStart();
            boolean otherIsStart = other.isStart();

            if (thisIsStart != otherIsStart) {
                return thisIsStart ? 1 : -1;
            }

            return spec.compareTo(other.spec);
        }

        /**
         * Gets the address.
         *
         * @return {@code >= 0;} the address
         */
        public int getAddress() {
            return address;
        }

        /**
         * Gets the disposition.
         *
         * @return {@code non-null;} the disposition
         */
        public Disposition getDisposition() {
            return disposition;
        }

        /**
         * Gets whether this is a local start. This is just shorthand for
         * {@code getDisposition() == Disposition.START}.
         *
         * @return {@code true} iff this is a start
         */
        public boolean isStart() {
            return disposition == Disposition.START;
        }

        /**
         * Gets the variable name.
         *
         * @return {@code null-ok;} the variable name
         */
        public CstUtf8 getName() {
            return spec.getLocalItem().getName();
        }

        /**
         * Gets the variable signature.
         *
         * @return {@code null-ok;} the variable signature
         */
        public CstUtf8 getSignature() {
            return spec.getLocalItem().getSignature();
        }

        /**
         * Gets the variable's type.
         *
         * @return {@code non-null;} the type
         */
        public CstType getType() {
            return type;
        }

        /**
         * Gets the number of the register holding the variable.
         *
         * @return {@code >= 0;} the number of the register holding
         * the variable
         */
        public int getRegister() {
            return spec.getReg();
        }

        /**
         * Gets the RegisterSpec of the register holding the variable.
         *
         * @return {@code non-null;} RegisterSpec of the holding register.
         */
        public RegisterSpec getRegisterSpec() {
            return spec;
        }

        /**
         * Returns whether or not this instance matches the given spec.
         *
         * @param otherSpec {@code non-null;} the spec in question
         * @return {@code true} iff this instance matches
         * {@code spec}
         */
        public boolean matches(RegisterSpec otherSpec) {
            return spec.equalsUsingSimpleType(otherSpec);
        }

        /**
         * Returns whether or not this instance matches the spec in
         * the given instance.
         *
         * @param other {@code non-null;} another entry
         * @return {@code true} iff this instance's spec matches
         * {@code other}
         */
        public boolean matches(Entry other) {
            return matches(other.spec);
        }

        /**
         * Returns an instance just like this one but with the disposition
         * set as given.
         *
         * @param disposition {@code non-null;} the new disposition
         * @return {@code non-null;} an appropriately-constructed instance
         */
        public Entry withDisposition(Disposition disposition) {
            if (disposition == this.disposition) {
                return this;
            }

            return new Entry(address, disposition, spec);
        }
    }

    /**
     * Constructs an instance for the given method, based on the given
     * block order and intermediate local information.
     *
     * @param insns {@code non-null;} instructions to convert
     * @return {@code non-null;} the constructed list
     */
    public static LocalList make(DalvInsnList insns) {
        int sz = insns.size();

        /*
         * Go through the insn list, looking for all the local
         * variable pseudoinstructions, splitting out LocalSnapshots
         * into separate per-variable starts, adding explicit ends
         * wherever a variable is replaced or moved, and collecting
         * these and all the other local variable "activity"
         * together into an output list (without the other insns).
         *
         * Note: As of this writing, this method won't be handed any
         * insn lists that contain local ends, but I (danfuzz) expect
         * that to change at some point, when we start feeding that
         * info explicitly into the rop layer rather than only trying
         * to infer it. So, given that expectation, this code is
         * written to deal with them.
         */

        MakeState state = new MakeState(sz);

        for (int i = 0; i < sz; i++) {
            DalvInsn insn = insns.get(i);

            if (insn instanceof LocalSnapshot) {
                RegisterSpecSet snapshot =
                    ((LocalSnapshot) insn).getLocals();
                state.snapshot(insn.getAddress(), snapshot);
            } else if (insn instanceof LocalStart) {
                RegisterSpec local = ((LocalStart) insn).getLocal();
                state.startLocal(insn.getAddress(), local);
            } else if (insn instanceof LocalEnd) {
                RegisterSpec local = ((LocalEnd) insn).getLocal();
                state.endLocal(insn.getAddress(), local);
            }
        }

        LocalList result = state.finish();

        if (DEBUG) {
            debugVerify(result);
        }

        return result;
    }

    /**
     * Debugging helper that verifies the constraint that a list doesn't
     * contain any redundant local starts and that local ends that are
     * due to replacements are properly annotated.
     */
    private static void debugVerify(LocalList locals) {
        try {
            debugVerify0(locals);
        } catch (RuntimeException ex) {
            int sz = locals.size();
            for (int i = 0; i < sz; i++) {
                System.err.println(locals.get(i));
            }
            throw ex;
        }

    }

    /**
     * Helper for {@link #debugVerify} which does most of the work.
     */
    private static void debugVerify0(LocalList locals) {
        int sz = locals.size();
        Entry[] active = new Entry[65536];

        for (int i = 0; i < sz; i++) {
            Entry e = locals.get(i);
            int reg = e.getRegister();

            if (e.isStart()) {
                Entry already = active[reg];

                if ((already != null) && e.matches(already)) {
                    throw new RuntimeException("redundant start at " +
                            Integer.toHexString(e.getAddress()) + ": got " +
                            e + "; had " + already);
                }

                active[reg] = e;
            } else {
                if (active[reg] == null) {
                    throw new RuntimeException("redundant end at " +
                            Integer.toHexString(e.getAddress()));
                }

                int addr = e.getAddress();
                boolean foundStart = false;

                for (int j = i + 1; j < sz; j++) {
                    Entry test = locals.get(j);
                    if (test.getAddress() != addr) {
                        break;
                    }
                    if (test.getRegisterSpec().getReg() == reg) {
                        if (test.isStart()) {
                            if (e.getDisposition()
                                    != Disposition.END_REPLACED) {
                                throw new RuntimeException(
                                        "improperly marked end at " +
                                        Integer.toHexString(addr));
                            }
                            foundStart = true;
                        } else {
                            throw new RuntimeException(
                                    "redundant end at " +
                                    Integer.toHexString(addr));
                        }
                    }
                }

                if (!foundStart &&
                        (e.getDisposition() == Disposition.END_REPLACED)) {
                    throw new RuntimeException(
                            "improper end replacement claim at " +
                            Integer.toHexString(addr));
                }

                active[reg] = null;
            }
        }
    }

    /**
     * Intermediate state when constructing a local list.
     */
    public static class MakeState {
        /** {@code non-null;} result being collected */
        private final ArrayList<Entry> result;

        /**
         * {@code >= 0;} running count of nulled result entries, to help with
         * sizing the final list
         */
        private int nullResultCount;

        /** {@code null-ok;} current register mappings */
        private RegisterSpecSet regs;

        /** {@code null-ok;} result indices where local ends are stored */
        private int[] endIndices;

        /** {@code >= 0;} last address seen */
        private int lastAddress;

        /**
         * Constructs an instance.
         */
        public MakeState(int initialSize) {
            result = new ArrayList<Entry>(initialSize);
            nullResultCount = 0;
            regs = null;
            endIndices = null;
            lastAddress = 0;
        }

        /**
         * Checks the address and other vitals as a prerequisite to
         * further processing.
         *
         * @param address {@code >= 0;} address about to be processed
         * @param reg {@code >= 0;} register number about to be processed
         */
        private void aboutToProcess(int address, int reg) {
            boolean first = (endIndices == null);

            if ((address == lastAddress) && !first) {
                return;
            }

            if (address < lastAddress) {
                throw new RuntimeException("shouldn't happen");
            }

            if (first || (reg >= endIndices.length)) {
                /*
                 * This is the first allocation of the state set and
                 * index array, or we need to grow. (The latter doesn't
                 * happen much; in fact, we have only ever observed
                 * it happening in test cases, never in "real" code.)
                 */
                int newSz = reg + 1;
                RegisterSpecSet newRegs = new RegisterSpecSet(newSz);
                int[] newEnds = new int[newSz];
                Arrays.fill(newEnds, -1);

                if (!first) {
                    newRegs.putAll(regs);
                    System.arraycopy(endIndices, 0, newEnds, 0,
                            endIndices.length);
                }

                regs = newRegs;
                endIndices = newEnds;
            }
        }

        /**
         * Sets the local state at the given address to the given snapshot.
         * The first call on this instance must be to this method, so that
         * the register state can be properly sized.
         *
         * @param address {@code >= 0;} the address
         * @param specs {@code non-null;} spec set representing the locals
         */
        public void snapshot(int address, RegisterSpecSet specs) {
            if (DEBUG) {
                System.err.printf("%04x snapshot %s\n", address, specs);
            }

            int sz = specs.getMaxSize();
            aboutToProcess(address, sz - 1);

            for (int i = 0; i < sz; i++) {
                RegisterSpec oldSpec = regs.get(i);
                RegisterSpec newSpec = filterSpec(specs.get(i));

                if (oldSpec == null) {
                    if (newSpec != null) {
                        startLocal(address, newSpec);
                    }
                } else if (newSpec == null) {
                    endLocal(address, oldSpec);
                } else if (! newSpec.equalsUsingSimpleType(oldSpec)) {
                    endLocal(address, oldSpec);
                    startLocal(address, newSpec);
                }
            }

            if (DEBUG) {
                System.err.printf("%04x snapshot done\n", address);
            }
        }

        /**
         * Starts a local at the given address.
         *
         * @param address {@code >= 0;} the address
         * @param startedLocal {@code non-null;} spec representing the
         * started local
         */
        public void startLocal(int address, RegisterSpec startedLocal) {
            if (DEBUG) {
                System.err.printf("%04x start %s\n", address, startedLocal);
            }

            int regNum = startedLocal.getReg();

            startedLocal = filterSpec(startedLocal);
            aboutToProcess(address, regNum);

            RegisterSpec existingLocal = regs.get(regNum);

            if (startedLocal.equalsUsingSimpleType(existingLocal)) {
                // Silently ignore a redundant start.
                return;
            }

            RegisterSpec movedLocal = regs.findMatchingLocal(startedLocal);
            if (movedLocal != null) {
                /*
                 * The same variable was moved from one register to another.
                 * So add an end for its old location.
                 */
                addOrUpdateEnd(address, Disposition.END_MOVED, movedLocal);
            }

            int endAt = endIndices[regNum];

            if (existingLocal != null) {
                /*
                 * There is an existing (but non-matching) local.
                 * Add an explicit end for it.
                 */
                add(address, Disposition.END_REPLACED, existingLocal);
            } else if (endAt >= 0) {
                /*
                 * Look for an end local for the same register at the
                 * same address. If found, then update it or delete
                 * it, depending on whether or not it represents the
                 * same variable as the one being started.
                 */
                Entry endEntry = result.get(endAt);
                if (endEntry.getAddress() == address) {
                    if (endEntry.matches(startedLocal)) {
                        /*
                         * There was already an end local for the same
                         * variable at the same address. This turns
                         * out to be superfluous, as we are starting
                         * up the exact same local. This situation can
                         * happen when a single local variable got
                         * somehow "split up" during intermediate
                         * processing. In any case, rather than represent
                         * the end-then-start, just remove the old end.
                         */
                        result.set(endAt, null);
                        nullResultCount++;
                        regs.put(startedLocal);
                        endIndices[regNum] = -1;
                        return;
                    } else {
                        /*
                         * There was a different variable ended at the
                         * same address. Update it to indicate that
                         * it was ended due to a replacement (rather than
                         * ending for no particular reason).
                         */
                        endEntry = endEntry.withDisposition(
                                Disposition.END_REPLACED);
                        result.set(endAt, endEntry);
                    }
                }
            }

            /*
             * The code above didn't find and remove an unnecessary
             * local end, so we now have to add one or more entries to
             * the output to capture the transition.
             */

            /*
             * If the local just below (in the register set at reg-1)
             * is of category-2, then it is ended by this new start.
             */
            if (regNum > 0) {
                RegisterSpec justBelow = regs.get(regNum - 1);
                if ((justBelow != null) && justBelow.isCategory2()) {
                    addOrUpdateEnd(address,
                            Disposition.END_CLOBBERED_BY_NEXT,
                            justBelow);
                }
            }

            /*
             * Similarly, if this local is category-2, then the local
             * just above (if any) is ended by the start now being
             * emitted.
             */
            if (startedLocal.isCategory2()) {
                RegisterSpec justAbove = regs.get(regNum + 1);
                if (justAbove != null) {
                    addOrUpdateEnd(address,
                            Disposition.END_CLOBBERED_BY_PREV,
                            justAbove);
                }
            }

            /*
             * TODO: Add an end for the same local in a different reg,
             * if any (that is, if the local migrates from vX to vY,
             * we should note that as a local end in vX).
             */

            add(address, Disposition.START, startedLocal);
        }

        /**
         * Ends a local at the given address, using the disposition
         * {@code END_SIMPLY}.
         *
         * @param address {@code >= 0;} the address
         * @param endedLocal {@code non-null;} spec representing the
         * local being ended
         */
        public void endLocal(int address, RegisterSpec endedLocal) {
            endLocal(address, endedLocal, Disposition.END_SIMPLY);
        }

        /**
         * Ends a local at the given address.
         *
         * @param address {@code >= 0;} the address
         * @param endedLocal {@code non-null;} spec representing the
         * local being ended
         * @param disposition reason for the end
         */
        public void endLocal(int address, RegisterSpec endedLocal,
                Disposition disposition) {
            if (DEBUG) {
                System.err.printf("%04x end %s\n", address, endedLocal);
            }

            int regNum = endedLocal.getReg();

            endedLocal = filterSpec(endedLocal);
            aboutToProcess(address, regNum);

            int endAt = endIndices[regNum];

            if (endAt >= 0) {
                /*
                 * The local in the given register is already ended.
                 * Silently return without adding anything to the result.
                 */
                return;
            }

            // Check for start and end at the same address.
            if (checkForEmptyRange(address, endedLocal)) {
                return;
            }

            add(address, disposition, endedLocal);
        }

        /**
         * Helper for {@link #endLocal}, which handles the cases where
         * and end local is issued at the same address as a start local
         * for the same register. If this case is found, then this
         * method will remove the start (as the local was never actually
         * active), update the {@link #endIndices} to be accurate, and
         * if needed update the newly-active end to reflect an altered
         * disposition.
         *
         * @param address {@code >= 0;} the address
         * @param endedLocal {@code non-null;} spec representing the
         * local being ended
         * @return {@code true} iff this method found the case in question
         * and adjusted things accordingly
         */
        private boolean checkForEmptyRange(int address,
                RegisterSpec endedLocal) {
            int at = result.size() - 1;
            Entry entry;

            // Look for a previous entry at the same address.
            for (/*at*/; at >= 0; at--) {
                entry = result.get(at);

                if (entry == null) {
                    continue;
                }

                if (entry.getAddress() != address) {
                    // We didn't find any match at the same address.
                    return false;
                }

                if (entry.matches(endedLocal)) {
                    break;
                }
            }

            /*
             * In fact, we found that the endedLocal had started at the
             * same address, so do all the requisite cleanup.
             */

            regs.remove(endedLocal);
            result.set(at, null);
            nullResultCount++;

            int regNum = endedLocal.getReg();
            boolean found = false;
            entry = null;

            // Now look back further to update where the register ended.
            for (at--; at >= 0; at--) {
                entry = result.get(at);

                if (entry == null) {
                    continue;
                }

                if (entry.getRegisterSpec().getReg() == regNum) {
                    found = true;
                    break;
                }
            }

            if (found) {
                // We found an end for the same register.
                endIndices[regNum] = at;

                if (entry.getAddress() == address) {
                    /*
                     * It's still the same address, so update the
                     * disposition.
                     */
                    result.set(at,
                            entry.withDisposition(Disposition.END_SIMPLY));
                }
            }

            return true;
        }

        /**
         * Converts a given spec into the form acceptable for use in a
         * local list. This, in particular, transforms the "known
         * null" type into simply {@code Object}. This method needs to
         * be called for any spec that is on its way into a locals
         * list.
         *
         * <p>This isn't necessarily the cleanest way to achieve the
         * goal of not representing known nulls in a locals list, but
         * it gets the job done.</p>
         *
         * @param orig {@code null-ok;} the original spec
         * @return {@code null-ok;} an appropriately modified spec, or the
         * original if nothing needs to be done
         */
        private static RegisterSpec filterSpec(RegisterSpec orig) {
            if ((orig != null) && (orig.getType() == Type.KNOWN_NULL)) {
                return orig.withType(Type.OBJECT);
            }

            return orig;
        }

        /**
         * Adds an entry to the result, updating the adjunct tables
         * accordingly.
         *
         * @param address {@code >= 0;} the address
         * @param disposition {@code non-null;} the disposition
         * @param spec {@code non-null;} spec representing the local
         */
        private void add(int address, Disposition disposition,
                RegisterSpec spec) {
            int regNum = spec.getReg();

            result.add(new Entry(address, disposition, spec));

            if (disposition == Disposition.START) {
                regs.put(spec);
                endIndices[regNum] = -1;
            } else {
                regs.remove(spec);
                endIndices[regNum] = result.size() - 1;
            }
        }

        /**
         * Adds or updates an end local (changing its disposition). If
         * this would cause an empty range for a local, this instead
         * removes the local entirely.
         *
         * @param address {@code >= 0;} the address
         * @param disposition {@code non-null;} the disposition
         * @param spec {@code non-null;} spec representing the local
         */
        private void addOrUpdateEnd(int address, Disposition disposition,
                RegisterSpec spec) {
            if (disposition == Disposition.START) {
                throw new RuntimeException("shouldn't happen");
            }

            int regNum = spec.getReg();
            int endAt = endIndices[regNum];

            if (endAt >= 0) {
                // There is a previous end.
                Entry endEntry = result.get(endAt);
                if ((endEntry.getAddress() == address) &&
                        endEntry.getRegisterSpec().equals(spec)) {
                    /*
                     * The end is for the right address and variable, so
                     * update it.
                     */
                    result.set(endAt, endEntry.withDisposition(disposition));
                    regs.remove(spec); // TODO: Is this line superfluous?
                    return;
                }
            }

            endLocal(address, spec, disposition);
        }

        /**
         * Finishes processing altogether and gets the result.
         *
         * @return {@code non-null;} the result list
         */
        public LocalList finish() {
            aboutToProcess(Integer.MAX_VALUE, 0);

            int resultSz = result.size();
            int finalSz = resultSz - nullResultCount;

            if (finalSz == 0) {
                return EMPTY;
            }

            /*
             * Collect an array of only the non-null entries, and then
             * sort it to get a consistent order for everything: Local
             * ends and starts for a given address could come in any
             * order, but we want ends before starts as well as
             * registers in order (within ends or starts).
             */

            Entry[] resultArr = new Entry[finalSz];

            if (resultSz == finalSz) {
                result.toArray(resultArr);
            } else {
                int at = 0;
                for (Entry e : result) {
                    if (e != null) {
                        resultArr[at++] = e;
                    }
                }
            }

            Arrays.sort(resultArr);

            LocalList resultList = new LocalList(finalSz);

            for (int i = 0; i < finalSz; i++) {
                resultList.set(i, resultArr[i]);
            }

            resultList.setImmutable();
            return resultList;
        }
    }
}