StdCatchBuilder.java revision 579d7739c53a2707ad711a2d2cae46d7d782f061 
1/*
2 * Copyright (C) 2008 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.dex.code;
18
19import com.android.dx.rop.code.BasicBlock;
20import com.android.dx.rop.code.BasicBlockList;
21import com.android.dx.rop.code.RopMethod;
22import com.android.dx.rop.cst.CstType;
23import com.android.dx.rop.type.Type;
24import com.android.dx.rop.type.TypeList;
25import com.android.dx.util.IntList;
26
27import java.util.ArrayList;
28import java.util.HashSet;
29
30/**
31 * Constructor of {@link CatchTable} instances from {@link RopMethod}
32 * and associated data.
33 */
34public final class StdCatchBuilder implements CatchBuilder {
35    /** the maximum range of a single catch handler, in code units */
36    private static final int MAX_CATCH_RANGE = 65535;
37
38    /** {@code non-null;} method to build the list for */
39    private final RopMethod method;
40
41    /** {@code non-null;} block output order */
42    private final int[] order;
43
44    /** {@code non-null;} address objects for each block */
45    private final BlockAddresses addresses;
46
47    /**
48     * Constructs an instance. It merely holds onto its parameters for
49     * a subsequent call to {@link #build}.
50     *
51     * @param method {@code non-null;} method to build the list for
52     * @param order {@code non-null;} block output order
53     * @param addresses {@code non-null;} address objects for each block
54     */
55    public StdCatchBuilder(RopMethod method, int[] order,
56            BlockAddresses addresses) {
57        if (method == null) {
58            throw new NullPointerException("method == null");
59        }
60
61        if (order == null) {
62            throw new NullPointerException("order == null");
63        }
64
65        if (addresses == null) {
66            throw new NullPointerException("addresses == null");
67        }
68
69        this.method = method;
70        this.order = order;
71        this.addresses = addresses;
72    }
73
74    /** {@inheritDoc} */
75    public CatchTable build() {
76        return build(method, order, addresses);
77    }
78
79    /** {@inheritDoc} */
80    public boolean hasAnyCatches() {
81        BasicBlockList blocks = method.getBlocks();
82        int size = blocks.size();
83
84        for (int i = 0; i < size; i++) {
85            BasicBlock block = blocks.get(i);
86            TypeList catches = block.getLastInsn().getCatches();
87            if (catches.size() != 0) {
88                return true;
89            }
90        }
91
92        return false;
93    }
94
95    /** {@inheritDoc} */
96    public HashSet<Type> getCatchTypes() {
97        HashSet<Type> result = new HashSet<Type>(20);
98        BasicBlockList blocks = method.getBlocks();
99        int size = blocks.size();
100
101        for (int i = 0; i < size; i++) {
102            BasicBlock block = blocks.get(i);
103            TypeList catches = block.getLastInsn().getCatches();
104            int catchSize = catches.size();
105
106            for (int j = 0; j < catchSize; j++) {
107                result.add(catches.getType(j));
108            }
109        }
110
111        return result;
112    }
113
114    /**
115     * Builds and returns the catch table for a given method.
116     *
117     * @param method {@code non-null;} method to build the list for
118     * @param order {@code non-null;} block output order
119     * @param addresses {@code non-null;} address objects for each block
120     * @return {@code non-null;} the constructed table
121     */
122    public static CatchTable build(RopMethod method, int[] order,
123            BlockAddresses addresses) {
124        int len = order.length;
125        BasicBlockList blocks = method.getBlocks();
126        ArrayList<CatchTable.Entry> resultList =
127            new ArrayList<CatchTable.Entry>(len);
128        CatchHandlerList currentHandlers = CatchHandlerList.EMPTY;
129        BasicBlock currentStartBlock = null;
130        BasicBlock currentEndBlock = null;
131
132        for (int i = 0; i < len; i++) {
133            BasicBlock block = blocks.labelToBlock(order[i]);
134
135            if (!block.canThrow()) {
136                /*
137                 * There is no need to concern ourselves with the
138                 * placement of blocks that can't throw with respect
139                 * to the blocks that *can* throw.
140                 */
141                continue;
142            }
143
144            CatchHandlerList handlers = handlersFor(block, addresses);
145
146            if (currentHandlers.size() == 0) {
147                // This is the start of a new catch range.
148                currentStartBlock = block;
149                currentEndBlock = block;
150                currentHandlers = handlers;
151                continue;
152            }
153
154            if (currentHandlers.equals(handlers)
155                    && rangeIsValid(currentStartBlock, block, addresses)) {
156                /*
157                 * The block we are looking at now has the same handlers
158                 * as the block that started the currently open catch
159                 * range, and adding it to the currently open range won't
160                 * cause it to be too long.
161                 */
162                currentEndBlock = block;
163                continue;
164            }
165
166            /*
167             * The block we are looking at now has incompatible handlers,
168             * so we need to finish off the last entry and start a new
169             * one. Note: We only emit an entry if it has associated handlers.
170             */
171            if (currentHandlers.size() != 0) {
172                CatchTable.Entry entry =
173                    makeEntry(currentStartBlock, currentEndBlock,
174                            currentHandlers, addresses);
175                resultList.add(entry);
176            }
177
178            currentStartBlock = block;
179            currentEndBlock = block;
180            currentHandlers = handlers;
181        }
182
183        if (currentHandlers.size() != 0) {
184            // Emit an entry for the range that was left hanging.
185            CatchTable.Entry entry =
186                makeEntry(currentStartBlock, currentEndBlock,
187                        currentHandlers, addresses);
188            resultList.add(entry);
189        }
190
191        // Construct the final result.
192
193        int resultSz = resultList.size();
194
195        if (resultSz == 0) {
196            return CatchTable.EMPTY;
197        }
198
199        CatchTable result = new CatchTable(resultSz);
200
201        for (int i = 0; i < resultSz; i++) {
202            result.set(i, resultList.get(i));
203        }
204
205        result.setImmutable();
206        return result;
207    }
208
209    /**
210     * Makes the {@link CatchHandlerList} for the given basic block.
211     *
212     * @param block {@code non-null;} block to get entries for
213     * @param addresses {@code non-null;} address objects for each block
214     * @return {@code non-null;} array of entries
215     */
216    private static CatchHandlerList handlersFor(BasicBlock block,
217            BlockAddresses addresses) {
218        IntList successors = block.getSuccessors();
219        int succSize = successors.size();
220        int primary = block.getPrimarySuccessor();
221        TypeList catches = block.getLastInsn().getCatches();
222        int catchSize = catches.size();
223
224        if (catchSize == 0) {
225            return CatchHandlerList.EMPTY;
226        }
227
228        if (((primary == -1) && (succSize != catchSize))
229                || ((primary != -1) &&
230                        ((succSize != (catchSize + 1))
231                                || (primary != successors.get(catchSize))))) {
232            /*
233             * Blocks that throw are supposed to list their primary
234             * successor -- if any -- last in the successors list, but
235             * that constraint appears to be violated here.
236             */
237            throw new RuntimeException(
238                    "shouldn't happen: weird successors list");
239        }
240
241        /*
242         * Reduce the effective catchSize if we spot a catch-all that
243         * isn't at the end.
244         */
245        for (int i = 0; i < catchSize; i++) {
246            Type type = catches.getType(i);
247            if (type.equals(Type.OBJECT)) {
248                catchSize = i + 1;
249                break;
250            }
251        }
252
253        CatchHandlerList result = new CatchHandlerList(catchSize);
254
255        for (int i = 0; i < catchSize; i++) {
256            CstType oneType = new CstType(catches.getType(i));
257            CodeAddress oneHandler = addresses.getStart(successors.get(i));
258            result.set(i, oneType, oneHandler.getAddress());
259        }
260
261        result.setImmutable();
262        return result;
263    }
264
265    /**
266     * Makes a {@link CatchTable#Entry} for the given block range and
267     * handlers.
268     *
269     * @param start {@code non-null;} the start block for the range (inclusive)
270     * @param end {@code non-null;} the start block for the range (also inclusive)
271     * @param handlers {@code non-null;} the handlers for the range
272     * @param addresses {@code non-null;} address objects for each block
273     */
274    private static CatchTable.Entry makeEntry(BasicBlock start,
275            BasicBlock end, CatchHandlerList handlers,
276            BlockAddresses addresses) {
277        /*
278         * We start at the *last* instruction of the start block, since
279         * that's the instruction that can throw...
280         */
281        CodeAddress startAddress = addresses.getLast(start);
282
283        // ...And we end *after* the last instruction of the end block.
284        CodeAddress endAddress = addresses.getEnd(end);
285
286        return new CatchTable.Entry(startAddress.getAddress(),
287                endAddress.getAddress(), handlers);
288    }
289
290    /**
291     * Gets whether the address range for the given two blocks is valid
292     * for a catch handler. This is true as long as the covered range is
293     * under 65536 code units.
294     *
295     * @param start {@code non-null;} the start block for the range (inclusive)
296     * @param end {@code non-null;} the start block for the range (also inclusive)
297     * @param addresses {@code non-null;} address objects for each block
298     * @return {@code true} if the range is valid as a catch range
299     */
300    private static boolean rangeIsValid(BasicBlock start, BasicBlock end,
301            BlockAddresses addresses) {
302        if (start == null) {
303            throw new NullPointerException("start == null");
304        }
305
306        if (end == null) {
307            throw new NullPointerException("end == null");
308        }
309
310        // See above about selection of instructions.
311        int startAddress = addresses.getLast(start).getAddress();
312        int endAddress = addresses.getEnd(end).getAddress();
313
314        return (endAddress - startAddress) <= MAX_CATCH_RANGE;
315    }
316}
317