rop/code/RopMethod.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.dx.rop.code;

import com.android.dx.util.Hex;
import com.android.dx.util.IntList;

/**
 * All of the parts that make up a method at the rop layer.
 */
public final class RopMethod {
    /** {@code non-null;} basic block list of the method */
    private final BasicBlockList blocks;

    /** {@code >= 0;} label for the block which starts the method */
    private final int firstLabel;

    /**
     * {@code null-ok;} array of predecessors for each block, indexed by block
     * label
     */
    private IntList[] predecessors;

    /**
     * {@code null-ok;} the predecessors for the implicit "exit" block, that is
     * the labels for the blocks that return, if calculated
     */
    private IntList exitPredecessors;

    /**
     * Constructs an instance.
     *
     * @param blocks {@code non-null;} basic block list of the method
     * @param firstLabel {@code >= 0;} the label of the first block to execute
     */
    public RopMethod(BasicBlockList blocks, int firstLabel) {
        if (blocks == null) {
            throw new NullPointerException("blocks == null");
        }

        if (firstLabel < 0) {
            throw new IllegalArgumentException("firstLabel < 0");
        }

        this.blocks = blocks;
        this.firstLabel = firstLabel;

        this.predecessors = null;
        this.exitPredecessors = null;
    }

    /**
     * Gets the basic block list for this method.
     *
     * @return {@code non-null;} the list
     */
    public BasicBlockList getBlocks() {
        return blocks;
    }

    /**
     * Gets the label for the first block in the method that this list
     * represents.
     *
     * @return {@code >= 0;} the first-block label
     */
    public int getFirstLabel() {
        return firstLabel;
    }

    /**
     * Gets the predecessors associated with the given block. This throws
     * an exception if there is no block with the given label.
     *
     * @param label {@code >= 0;} the label of the block in question
     * @return {@code non-null;} the predecessors of that block
     */
    public IntList labelToPredecessors(int label) {
        if (exitPredecessors == null) {
            calcPredecessors();
        }

        IntList result = predecessors[label];

        if (result == null) {
            throw new RuntimeException("no such block: " + Hex.u2(label));
        }

        return result;
    }

    /**
     * Gets the exit predecessors for this instance.
     *
     * @return {@code non-null;} the exit predecessors
     */
    public IntList getExitPredecessors() {
        if (exitPredecessors == null) {
            calcPredecessors();
        }

        return exitPredecessors;
    }


    /**
     * Returns an instance that is identical to this one, except that
     * the registers in each instruction are offset by the given
     * amount.
     *
     * @param delta the amount to offset register numbers by
     * @return {@code non-null;} an appropriately-constructed instance
     */
    public RopMethod withRegisterOffset(int delta) {
        RopMethod result = new RopMethod(blocks.withRegisterOffset(delta),
                                         firstLabel);

        if (exitPredecessors != null) {
            /*
             * The predecessors have been calculated. It's safe to
             * inject these into the new instance, since the
             * transformation being applied doesn't affect the
             * predecessors.
             */
            result.exitPredecessors = exitPredecessors;
            result.predecessors = predecessors;
        }

        return result;
    }

    /**
     * Calculates the predecessor sets for each block as well as for the
     * exit.
     */
    private void calcPredecessors() {
        int maxLabel = blocks.getMaxLabel();
        IntList[] predecessors = new IntList[maxLabel];
        IntList exitPredecessors = new IntList(10);
        int sz = blocks.size();

        /*
         * For each block, find its successors, and add the block's label to
         * the successor's predecessors.
         */
        for (int i = 0; i < sz; i++) {
            BasicBlock one = blocks.get(i);
            int label = one.getLabel();
            IntList successors = one.getSuccessors();
            int ssz = successors.size();
            if (ssz == 0) {
                // This block exits.
                exitPredecessors.add(label);
            } else {
                for (int j = 0; j < ssz; j++) {
                    int succLabel = successors.get(j);
                    IntList succPreds = predecessors[succLabel];
                    if (succPreds == null) {
                        succPreds = new IntList(10);
                        predecessors[succLabel] = succPreds;
                    }
                    succPreds.add(label);
                }
            }
        }

        // Sort and immutablize all the predecessor lists.
        for (int i = 0; i < maxLabel; i++) {
            IntList preds = predecessors[i];
            if (preds != null) {
                preds.sort();
                preds.setImmutable();
            }
        }

        exitPredecessors.sort();
        exitPredecessors.setImmutable();

        /*
         * The start label might not ever have had any predecessors
         * added to it (probably doesn't, because of how Java gets
         * translated into rop form). So, check for this and rectify
         * the situation if required.
         */
        if (predecessors[firstLabel] == null) {
            predecessors[firstLabel] = IntList.EMPTY;
        }

        this.predecessors = predecessors;
        this.exitPredecessors = exitPredecessors;
    }
}