1/*
2 * Javassist, a Java-bytecode translator toolkit.
3 * Copyright (C) 1999-2007 Shigeru Chiba, and others. All Rights Reserved.
4 *
5 * The contents of this file are subject to the Mozilla Public License Version
6 * 1.1 (the "License"); you may not use this file except in compliance with
7 * the License.  Alternatively, the contents of this file may be used under
8 * the terms of the GNU Lesser General Public License Version 2.1 or later.
9 *
10 * Software distributed under the License is distributed on an "AS IS" basis,
11 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12 * for the specific language governing rights and limitations under the
13 * License.
14 */
15package javassist.bytecode.analysis;
16
17import java.util.HashMap;
18import java.util.HashSet;
19import java.util.Map;
20import java.util.Set;
21
22import javassist.bytecode.BadBytecode;
23import javassist.bytecode.CodeAttribute;
24import javassist.bytecode.CodeIterator;
25import javassist.bytecode.ExceptionTable;
26import javassist.bytecode.MethodInfo;
27import javassist.bytecode.Opcode;
28
29/**
30 * Discovers the subroutines in a method, and tracks all callers.
31 *
32 * @author Jason T. Greene
33 */
34public class SubroutineScanner implements Opcode {
35
36    private Subroutine[] subroutines;
37    Map subTable = new HashMap();
38    Set done = new HashSet();
39
40
41    public Subroutine[] scan(MethodInfo method) throws BadBytecode {
42        CodeAttribute code = method.getCodeAttribute();
43        CodeIterator iter = code.iterator();
44
45        subroutines = new Subroutine[code.getCodeLength()];
46        subTable.clear();
47        done.clear();
48
49        scan(0, iter, null);
50
51        ExceptionTable exceptions = code.getExceptionTable();
52        for (int i = 0; i < exceptions.size(); i++) {
53            int handler = exceptions.handlerPc(i);
54            // If an exception is thrown in subroutine, the handler
55            // is part of the same subroutine.
56            scan(handler, iter, subroutines[exceptions.startPc(i)]);
57        }
58
59        return subroutines;
60    }
61
62    private void scan(int pos, CodeIterator iter, Subroutine sub) throws BadBytecode {
63        // Skip already processed blocks
64        if (done.contains(new Integer(pos)))
65            return;
66
67        done.add(new Integer(pos));
68
69        int old = iter.lookAhead();
70        iter.move(pos);
71
72        boolean next;
73        do {
74            pos = iter.next();
75            next = scanOp(pos, iter, sub) && iter.hasNext();
76        } while (next);
77
78        iter.move(old);
79    }
80
81    private boolean scanOp(int pos, CodeIterator iter, Subroutine sub) throws BadBytecode {
82        subroutines[pos] = sub;
83
84        int opcode = iter.byteAt(pos);
85
86        if (opcode == TABLESWITCH) {
87            scanTableSwitch(pos, iter, sub);
88
89            return false;
90        }
91
92        if (opcode == LOOKUPSWITCH) {
93            scanLookupSwitch(pos, iter, sub);
94
95            return false;
96        }
97
98        // All forms of return and throw end current code flow
99        if (Util.isReturn(opcode) || opcode == RET || opcode == ATHROW)
100            return false;
101
102        if (Util.isJumpInstruction(opcode)) {
103            int target = Util.getJumpTarget(pos, iter);
104            if (opcode == JSR || opcode == JSR_W) {
105                Subroutine s = (Subroutine) subTable.get(new Integer(target));
106                if (s == null) {
107                    s = new Subroutine(target, pos);
108                    subTable.put(new Integer(target), s);
109                    scan(target, iter, s);
110                } else {
111                    s.addCaller(pos);
112                }
113            } else {
114                scan(target, iter, sub);
115
116                // GOTO ends current code flow
117                if (Util.isGoto(opcode))
118                    return false;
119            }
120        }
121
122        return true;
123    }
124
125    private void scanLookupSwitch(int pos, CodeIterator iter, Subroutine sub) throws BadBytecode {
126        int index = (pos & ~3) + 4;
127        // default
128        scan(pos + iter.s32bitAt(index), iter, sub);
129        int npairs = iter.s32bitAt(index += 4);
130        int end = npairs * 8 + (index += 4);
131
132        // skip "match"
133        for (index += 4; index < end; index += 8) {
134            int target = iter.s32bitAt(index) + pos;
135            scan(target, iter, sub);
136        }
137    }
138
139    private void scanTableSwitch(int pos, CodeIterator iter, Subroutine sub) throws BadBytecode {
140        // Skip 4 byte alignment padding
141        int index = (pos & ~3) + 4;
142        // default
143        scan(pos + iter.s32bitAt(index), iter, sub);
144        int low = iter.s32bitAt(index += 4);
145        int high = iter.s32bitAt(index += 4);
146        int end = (high - low + 1) * 4 + (index += 4);
147
148        // Offset table
149        for (; index < end; index += 4) {
150            int target = iter.s32bitAt(index) + pos;
151            scan(target, iter, sub);
152        }
153    }
154
155
156}
157