1/*
2 * Copyright (C) 2007 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.dx.rop.code;
18
19import com.android.dx.util.Hex;
20import com.android.dx.util.IntList;
21
22/**
23 * All of the parts that make up a method at the rop layer.
24 */
25public final class RopMethod {
26    /** {@code non-null;} basic block list of the method */
27    private final BasicBlockList blocks;
28
29    /** {@code >= 0;} label for the block which starts the method */
30    private final int firstLabel;
31
32    /**
33     * {@code null-ok;} array of predecessors for each block, indexed by block
34     * label
35     */
36    private IntList[] predecessors;
37
38    /**
39     * {@code null-ok;} the predecessors for the implicit "exit" block, that is
40     * the labels for the blocks that return, if calculated
41     */
42    private IntList exitPredecessors;
43
44    /**
45     * Constructs an instance.
46     *
47     * @param blocks {@code non-null;} basic block list of the method
48     * @param firstLabel {@code >= 0;} the label of the first block to execute
49     */
50    public RopMethod(BasicBlockList blocks, int firstLabel) {
51        if (blocks == null) {
52            throw new NullPointerException("blocks == null");
53        }
54
55        if (firstLabel < 0) {
56            throw new IllegalArgumentException("firstLabel < 0");
57        }
58
59        this.blocks = blocks;
60        this.firstLabel = firstLabel;
61
62        this.predecessors = null;
63        this.exitPredecessors = null;
64    }
65
66    /**
67     * Gets the basic block list for this method.
68     *
69     * @return {@code non-null;} the list
70     */
71    public BasicBlockList getBlocks() {
72        return blocks;
73    }
74
75    /**
76     * Gets the label for the first block in the method that this list
77     * represents.
78     *
79     * @return {@code >= 0;} the first-block label
80     */
81    public int getFirstLabel() {
82        return firstLabel;
83    }
84
85    /**
86     * Gets the predecessors associated with the given block. This throws
87     * an exception if there is no block with the given label.
88     *
89     * @param label {@code >= 0;} the label of the block in question
90     * @return {@code non-null;} the predecessors of that block
91     */
92    public IntList labelToPredecessors(int label) {
93        if (exitPredecessors == null) {
94            calcPredecessors();
95        }
96
97        IntList result = predecessors[label];
98
99        if (result == null) {
100            throw new RuntimeException("no such block: " + Hex.u2(label));
101        }
102
103        return result;
104    }
105
106    /**
107     * Gets the exit predecessors for this instance.
108     *
109     * @return {@code non-null;} the exit predecessors
110     */
111    public IntList getExitPredecessors() {
112        if (exitPredecessors == null) {
113            calcPredecessors();
114        }
115
116        return exitPredecessors;
117    }
118
119
120    /**
121     * Returns an instance that is identical to this one, except that
122     * the registers in each instruction are offset by the given
123     * amount.
124     *
125     * @param delta the amount to offset register numbers by
126     * @return {@code non-null;} an appropriately-constructed instance
127     */
128    public RopMethod withRegisterOffset(int delta) {
129        RopMethod result = new RopMethod(blocks.withRegisterOffset(delta),
130                                         firstLabel);
131
132        if (exitPredecessors != null) {
133            /*
134             * The predecessors have been calculated. It's safe to
135             * inject these into the new instance, since the
136             * transformation being applied doesn't affect the
137             * predecessors.
138             */
139            result.exitPredecessors = exitPredecessors;
140            result.predecessors = predecessors;
141        }
142
143        return result;
144    }
145
146    /**
147     * Calculates the predecessor sets for each block as well as for the
148     * exit.
149     */
150    private void calcPredecessors() {
151        int maxLabel = blocks.getMaxLabel();
152        IntList[] predecessors = new IntList[maxLabel];
153        IntList exitPredecessors = new IntList(10);
154        int sz = blocks.size();
155
156        /*
157         * For each block, find its successors, and add the block's label to
158         * the successor's predecessors.
159         */
160        for (int i = 0; i < sz; i++) {
161            BasicBlock one = blocks.get(i);
162            int label = one.getLabel();
163            IntList successors = one.getSuccessors();
164            int ssz = successors.size();
165            if (ssz == 0) {
166                // This block exits.
167                exitPredecessors.add(label);
168            } else {
169                for (int j = 0; j < ssz; j++) {
170                    int succLabel = successors.get(j);
171                    IntList succPreds = predecessors[succLabel];
172                    if (succPreds == null) {
173                        succPreds = new IntList(10);
174                        predecessors[succLabel] = succPreds;
175                    }
176                    succPreds.add(label);
177                }
178            }
179        }
180
181        // Sort and immutablize all the predecessor lists.
182        for (int i = 0; i < maxLabel; i++) {
183            IntList preds = predecessors[i];
184            if (preds != null) {
185                preds.sort();
186                preds.setImmutable();
187            }
188        }
189
190        exitPredecessors.sort();
191        exitPredecessors.setImmutable();
192
193        /*
194         * The start label might not ever have had any predecessors
195         * added to it (probably doesn't, because of how Java gets
196         * translated into rop form). So, check for this and rectify
197         * the situation if required.
198         */
199        if (predecessors[firstLabel] == null) {
200            predecessors[firstLabel] = IntList.EMPTY;
201        }
202
203        this.predecessors = predecessors;
204        this.exitPredecessors = exitPredecessors;
205    }
206}
207