Classes in this File | Line Coverage | Branch Coverage | Complexity | ||||
Subroutines |
|
| 4.857142857142857;4.857 | ||||
Subroutines$SubroutineImpl |
|
| 4.857142857142857;4.857 |
1 | /* | |
2 | * Licensed to the Apache Software Foundation (ASF) under one or more | |
3 | * contributor license agreements. See the NOTICE file distributed with | |
4 | * this work for additional information regarding copyright ownership. | |
5 | * The ASF licenses this file to You under the Apache License, Version 2.0 | |
6 | * (the "License"); you may not use this file except in compliance with | |
7 | * the License. You may obtain a copy of the License at | |
8 | * | |
9 | * http://www.apache.org/licenses/LICENSE-2.0 | |
10 | * | |
11 | * Unless required by applicable law or agreed to in writing, software | |
12 | * distributed under the License is distributed on an "AS IS" BASIS, | |
13 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
14 | * See the License for the specific language governing permissions and | |
15 | * limitations under the License. | |
16 | */ | |
17 | package org.apache.commons.javaflow.bytecode.transformation.bcel.analyser; | |
18 | ||
19 | import org.apache.bcel.generic.ASTORE; | |
20 | import org.apache.bcel.generic.ATHROW; | |
21 | import org.apache.bcel.generic.BranchInstruction; | |
22 | import org.apache.bcel.generic.CodeExceptionGen; | |
23 | import org.apache.bcel.generic.GotoInstruction; | |
24 | import org.apache.bcel.generic.IndexedInstruction; | |
25 | import org.apache.bcel.generic.Instruction; | |
26 | import org.apache.bcel.generic.InstructionHandle; | |
27 | import org.apache.bcel.generic.JsrInstruction; | |
28 | import org.apache.bcel.generic.LocalVariableInstruction; | |
29 | import org.apache.bcel.generic.MethodGen; | |
30 | import org.apache.bcel.generic.RET; | |
31 | import org.apache.bcel.generic.ReturnInstruction; | |
32 | import org.apache.bcel.generic.Select; | |
33 | import org.apache.bcel.verifier.exc.AssertionViolatedException; | |
34 | import org.apache.bcel.verifier.exc.StructuralCodeConstraintException; | |
35 | ||
36 | import java.util.ArrayList; | |
37 | import java.util.HashSet; | |
38 | import java.util.Hashtable; | |
39 | import java.util.Iterator; | |
40 | import java.util.Set; | |
41 | ||
42 | /** | |
43 | * Instances of this class contain information about the subroutines | |
44 | * found in a code array of a method. | |
45 | * This implementation considers the top-level (the instructions | |
46 | * reachable without a JSR or JSR_W starting off from the first | |
47 | * instruction in a code array of a method) being a special subroutine; | |
48 | * see getTopLevel() for that. | |
49 | * Please note that the definition of subroutines in the Java Virtual | |
50 | * Machine Specification, Second Edition is somewhat incomplete. | |
51 | * Therefore, JustIce uses an own, more rigid notion. | |
52 | * Basically, a subroutine is a piece of code that starts at the target | |
53 | * of a JSR of JSR_W instruction and ends at a corresponding RET | |
54 | * instruction. Note also that the control flow of a subroutine | |
55 | * may be complex and non-linear; and that subroutines may be nested. | |
56 | * | |
57 | * WARNING! These classes are a fork of the bcel verifier. | |
58 | * | |
59 | * @version $Id: Subroutines.java 480487 2006-11-29 08:54:42Z bayard $ | |
60 | * @author <A HREF="http://www.inf.fu-berlin.de/~ehaase"/>Enver Haase</A> | |
61 | * @see #getTopLevel() | |
62 | */ | |
63 | public class Subroutines{ | |
64 | /** | |
65 | * This inner class implements the Subroutine interface. | |
66 | */ | |
67 | 0 | private class SubroutineImpl implements Subroutine{ |
68 | /** | |
69 | * UNSET, a symbol for an uninitialized localVariable | |
70 | * field. This is used for the "top-level" Subroutine; | |
71 | * i.e. no subroutine. | |
72 | */ | |
73 | 0 | private final int UNSET = -1; |
74 | ||
75 | /** | |
76 | * The Local Variable slot where the first | |
77 | * instruction of this subroutine (an ASTORE) stores | |
78 | * the JsrInstruction's ReturnAddress in and | |
79 | * the RET of this subroutine operates on. | |
80 | */ | |
81 | 0 | private int localVariable = UNSET; |
82 | ||
83 | /** The instructions that belong to this subroutine. */ | |
84 | private Set instructions; | |
85 | ||
86 | /* | |
87 | * Refer to the Subroutine interface for documentation. | |
88 | */ | |
89 | public boolean contains(InstructionHandle inst){ | |
90 | 0 | return instructions.contains(inst); |
91 | } | |
92 | ||
93 | /** | |
94 | * The JSR or JSR_W instructions that define this | |
95 | * subroutine by targeting it. | |
96 | */ | |
97 | 0 | private HashSet theJSRs = new HashSet(); |
98 | ||
99 | /** | |
100 | * The RET instruction that leaves this subroutine. | |
101 | */ | |
102 | private InstructionHandle theRET; | |
103 | ||
104 | /** | |
105 | * Returns a String representation of this object, merely | |
106 | * for debugging purposes. | |
107 | * (Internal) Warning: Verbosity on a problematic subroutine may cause | |
108 | * stack overflow errors due to recursive subSubs() calls. | |
109 | * Don't use this, then. | |
110 | */ | |
111 | public String toString(){ | |
112 | 0 | String ret = "Subroutine: Local variable is '"+localVariable+"', JSRs are '"+theJSRs+"', RET is '"+theRET+"', Instructions: '"+instructions.toString()+"'."; |
113 | ||
114 | 0 | ret += " Accessed local variable slots: '"; |
115 | 0 | int[] alv = getAccessedLocalsIndices(); |
116 | 0 | for (int i=0; i<alv.length; i++){ |
117 | 0 | ret += alv[i]+" "; |
118 | } | |
119 | 0 | ret+="'."; |
120 | ||
121 | 0 | ret += " Recursively (via subsub...routines) accessed local variable slots: '"; |
122 | 0 | alv = getRecursivelyAccessedLocalsIndices(); |
123 | 0 | for (int i=0; i<alv.length; i++){ |
124 | 0 | ret += alv[i]+" "; |
125 | } | |
126 | 0 | ret+="'."; |
127 | ||
128 | 0 | return ret; |
129 | } | |
130 | ||
131 | /** | |
132 | * Sets the leaving RET instruction. Must be invoked after all instructions are added. | |
133 | * Must not be invoked for top-level 'subroutine'. | |
134 | */ | |
135 | void setLeavingRET(){ | |
136 | 0 | if (localVariable == UNSET){ |
137 | 0 | throw new AssertionViolatedException("setLeavingRET() called for top-level 'subroutine' or forgot to set local variable first."); |
138 | } | |
139 | 0 | Iterator iter = instructions.iterator(); |
140 | 0 | InstructionHandle ret = null; |
141 | 0 | while(iter.hasNext()){ |
142 | 0 | InstructionHandle actual = (InstructionHandle) iter.next(); |
143 | 0 | if (actual.getInstruction() instanceof RET){ |
144 | 0 | if (ret != null){ |
145 | 0 | throw new StructuralCodeConstraintException("Subroutine with more then one RET detected: '"+ret+"' and '"+actual+"'."); |
146 | } | |
147 | else{ | |
148 | 0 | ret = actual; |
149 | } | |
150 | } | |
151 | 0 | } |
152 | 0 | if (ret == null){ |
153 | 0 | throw new StructuralCodeConstraintException("Subroutine without a RET detected."); |
154 | } | |
155 | 0 | if (((RET) ret.getInstruction()).getIndex() != localVariable){ |
156 | 0 | throw new StructuralCodeConstraintException("Subroutine uses '"+ret+"' which does not match the correct local variable '"+localVariable+"'."); |
157 | } | |
158 | 0 | theRET = ret; |
159 | 0 | } |
160 | ||
161 | /* | |
162 | * Refer to the Subroutine interface for documentation. | |
163 | */ | |
164 | public InstructionHandle[] getEnteringJsrInstructions(){ | |
165 | 0 | if (this == TOPLEVEL) { |
166 | 0 | throw new AssertionViolatedException("getLeavingRET() called on top level pseudo-subroutine."); |
167 | } | |
168 | 0 | InstructionHandle[] jsrs = new InstructionHandle[theJSRs.size()]; |
169 | 0 | return (InstructionHandle[]) (theJSRs.toArray(jsrs)); |
170 | } | |
171 | ||
172 | /** | |
173 | * Adds a new JSR or JSR_W that has this subroutine as its target. | |
174 | */ | |
175 | public void addEnteringJsrInstruction(InstructionHandle jsrInst){ | |
176 | 0 | if ( (jsrInst == null) || (! (jsrInst.getInstruction() instanceof JsrInstruction))){ |
177 | 0 | throw new AssertionViolatedException("Expecting JsrInstruction InstructionHandle."); |
178 | } | |
179 | 0 | if (localVariable == UNSET){ |
180 | 0 | throw new AssertionViolatedException("Set the localVariable first!"); |
181 | } | |
182 | else{ | |
183 | // Something is wrong when an ASTORE is targeted that does not operate on the same local variable than the rest of the | |
184 | // JsrInstruction-targets and the RET. | |
185 | // (We don't know out leader here so we cannot check if we're really targeted!) | |
186 | 0 | if (localVariable != ((ASTORE) (((JsrInstruction) jsrInst.getInstruction()).getTarget().getInstruction())).getIndex()){ |
187 | 0 | throw new AssertionViolatedException("Setting a wrong JsrInstruction."); |
188 | } | |
189 | } | |
190 | 0 | theJSRs.add(jsrInst); |
191 | 0 | } |
192 | ||
193 | /* | |
194 | * Refer to the Subroutine interface for documentation. | |
195 | */ | |
196 | public InstructionHandle getLeavingRET(){ | |
197 | 0 | if (this == TOPLEVEL) { |
198 | 0 | throw new AssertionViolatedException("getLeavingRET() called on top level pseudo-subroutine."); |
199 | } | |
200 | 0 | return theRET; |
201 | } | |
202 | ||
203 | /* | |
204 | * Refer to the Subroutine interface for documentation. | |
205 | */ | |
206 | public InstructionHandle[] getInstructions(){ | |
207 | 0 | InstructionHandle[] ret = new InstructionHandle[instructions.size()]; |
208 | 0 | return (InstructionHandle[]) instructions.toArray(ret); |
209 | } | |
210 | ||
211 | /* Satisfies Subroutine.getRecursivelyAccessedLocalsIndices(). */ | |
212 | public int[] getRecursivelyAccessedLocalsIndices(){ | |
213 | 0 | HashSet s = new HashSet(); |
214 | 0 | int[] lvs = getAccessedLocalsIndices(); |
215 | 0 | for (int j=0; j<lvs.length; j++){ |
216 | 0 | s.add(new Integer(lvs[j])); |
217 | } | |
218 | 0 | _getRecursivelyAccessedLocalsIndicesHelper(s, this.subSubs()); |
219 | 0 | int[] ret = new int[s.size()]; |
220 | 0 | Iterator i = s.iterator(); |
221 | 0 | int j=-1; |
222 | 0 | while (i.hasNext()){ |
223 | 0 | j++; |
224 | 0 | ret[j] = ((Integer) i.next()).intValue(); |
225 | 0 | } |
226 | 0 | return ret; |
227 | } | |
228 | ||
229 | /** | |
230 | * A recursive helper method for getRecursivelyAccessedLocalsIndices(). | |
231 | * @see #getRecursivelyAccessedLocalsIndices() | |
232 | */ | |
233 | private void _getRecursivelyAccessedLocalsIndicesHelper(HashSet s, Subroutine[] subs){ | |
234 | 0 | for (int i=0; i<subs.length; i++){ |
235 | 0 | int[] lvs = subs[i].getAccessedLocalsIndices(); |
236 | 0 | for (int j=0; j<lvs.length; j++){ |
237 | 0 | s.add(new Integer(lvs[j])); |
238 | } | |
239 | 0 | if(subs[i].subSubs().length != 0){ |
240 | 0 | _getRecursivelyAccessedLocalsIndicesHelper(s, subs[i].subSubs()); |
241 | } | |
242 | } | |
243 | 0 | } |
244 | ||
245 | /* | |
246 | * Satisfies Subroutine.getAccessedLocalIndices(). | |
247 | */ | |
248 | public int[] getAccessedLocalsIndices(){ | |
249 | //TODO: Implement caching. | |
250 | 0 | HashSet acc = new HashSet(); |
251 | 0 | if (theRET == null && this != TOPLEVEL){ |
252 | 0 | throw new AssertionViolatedException("This subroutine object must be built up completely before calculating accessed locals."); |
253 | } | |
254 | 0 | Iterator i = instructions.iterator(); |
255 | 0 | while (i.hasNext()){ |
256 | 0 | InstructionHandle ih = (InstructionHandle) i.next(); |
257 | // RET is not a LocalVariableInstruction in the current version of BCEL. | |
258 | 0 | if (ih.getInstruction() instanceof LocalVariableInstruction || ih.getInstruction() instanceof RET){ |
259 | 0 | int idx = ((IndexedInstruction) (ih.getInstruction())).getIndex(); |
260 | 0 | acc.add(new Integer(idx)); |
261 | // LONG? DOUBLE?. | |
262 | try{ | |
263 | // LocalVariableInstruction instances are typed without the need to look into | |
264 | // the constant pool. | |
265 | 0 | if (ih.getInstruction() instanceof LocalVariableInstruction){ |
266 | 0 | int s = ((LocalVariableInstruction) ih.getInstruction()).getType(null).getSize(); |
267 | 0 | if (s==2) acc.add(new Integer(idx+1)); |
268 | } | |
269 | } | |
270 | 0 | catch(RuntimeException re){ |
271 | 0 | throw new AssertionViolatedException("Oops. BCEL did not like NULL as a ConstantPoolGen object."); |
272 | 0 | } |
273 | } | |
274 | 0 | } |
275 | ||
276 | 0 | int[] ret = new int[acc.size()]; |
277 | 0 | i = acc.iterator(); |
278 | 0 | int j=-1; |
279 | 0 | while (i.hasNext()){ |
280 | 0 | j++; |
281 | 0 | ret[j] = ((Integer) i.next()).intValue(); |
282 | 0 | } |
283 | 0 | return ret; |
284 | } | |
285 | ||
286 | /* | |
287 | * Satisfies Subroutine.subSubs(). | |
288 | */ | |
289 | public Subroutine[] subSubs(){ | |
290 | 0 | HashSet h = new HashSet(); |
291 | ||
292 | 0 | Iterator i = instructions.iterator(); |
293 | 0 | while (i.hasNext()){ |
294 | 0 | Instruction inst = ((InstructionHandle) i.next()).getInstruction(); |
295 | 0 | if (inst instanceof JsrInstruction){ |
296 | 0 | InstructionHandle targ = ((JsrInstruction) inst).getTarget(); |
297 | 0 | h.add(getSubroutine(targ)); |
298 | } | |
299 | 0 | } |
300 | 0 | Subroutine[] ret = new Subroutine[h.size()]; |
301 | 0 | return (Subroutine[]) h.toArray(ret); |
302 | } | |
303 | ||
304 | /* | |
305 | * Sets the local variable slot the ASTORE that is targeted | |
306 | * by the JsrInstructions of this subroutine operates on. | |
307 | * This subroutine's RET operates on that same local variable | |
308 | * slot, of course. | |
309 | */ | |
310 | void setLocalVariable(int i){ | |
311 | 0 | if (localVariable != UNSET){ |
312 | 0 | throw new AssertionViolatedException("localVariable set twice."); |
313 | } | |
314 | else{ | |
315 | 0 | localVariable = i; |
316 | } | |
317 | 0 | } |
318 | ||
319 | /** | |
320 | * The default constructor. | |
321 | */ | |
322 | 0 | public SubroutineImpl(){ |
323 | 0 | } |
324 | ||
325 | void setInstructions(Set _instructions) { | |
326 | 0 | this.instructions = _instructions; |
327 | 0 | } |
328 | }// end Inner Class SubrouteImpl | |
329 | ||
330 | /** | |
331 | * The Hashtable containing the subroutines found. | |
332 | * Key: InstructionHandle of the leader of the subroutine. | |
333 | * Elements: SubroutineImpl objects. | |
334 | */ | |
335 | 0 | private Hashtable subroutines = new Hashtable(); |
336 | ||
337 | /** | |
338 | * This is referring to a special subroutine, namely the | |
339 | * top level. This is not really a subroutine but we use | |
340 | * it to distinguish between top level instructions and | |
341 | * unreachable instructions. | |
342 | */ | |
343 | public final Subroutine TOPLEVEL; | |
344 | ||
345 | /** | |
346 | * Constructor. | |
347 | * @param mg A MethodGen object representing method to | |
348 | * create the Subroutine objects of. | |
349 | */ | |
350 | 0 | public Subroutines(MethodGen mg){ |
351 | ||
352 | 0 | InstructionHandle[] all = mg.getInstructionList().getInstructionHandles(); |
353 | 0 | CodeExceptionGen[] handlers = mg.getExceptionHandlers(); |
354 | ||
355 | // Define our "Toplevel" fake subroutine. | |
356 | 0 | TOPLEVEL = new SubroutineImpl(); |
357 | ||
358 | // Calculate "real" subroutines. | |
359 | 0 | HashSet sub_leaders = new HashSet(); // Elements: InstructionHandle |
360 | 0 | for (int i=0; i<all.length; i++){ |
361 | 0 | Instruction inst = all[i].getInstruction(); |
362 | 0 | if (inst instanceof JsrInstruction){ |
363 | 0 | sub_leaders.add(((JsrInstruction) inst).getTarget()); |
364 | } | |
365 | } | |
366 | ||
367 | // Build up the database. | |
368 | 0 | Iterator iter = sub_leaders.iterator(); |
369 | 0 | while (iter.hasNext()){ |
370 | 0 | SubroutineImpl sr = new SubroutineImpl(); |
371 | 0 | InstructionHandle astore = (InstructionHandle) (iter.next()); |
372 | 0 | sr.setLocalVariable( ((ASTORE) (astore.getInstruction())).getIndex() ); |
373 | 0 | subroutines.put(astore, sr); |
374 | 0 | } |
375 | ||
376 | // Fake it a bit. We want a virtual "TopLevel" subroutine. | |
377 | 0 | subroutines.put(all[0], TOPLEVEL); |
378 | 0 | sub_leaders.add(all[0]); |
379 | ||
380 | // Tell the subroutines about their JsrInstructions. | |
381 | // Note that there cannot be a JSR targeting the top-level | |
382 | // since "Jsr 0" is disallowed in Pass 3a. | |
383 | // Instructions shared by a subroutine and the toplevel are | |
384 | // disallowed and checked below, after the BFS. | |
385 | 0 | for (int i=0; i<all.length; i++){ |
386 | 0 | Instruction inst = all[i].getInstruction(); |
387 | 0 | if (inst instanceof JsrInstruction){ |
388 | 0 | InstructionHandle leader = ((JsrInstruction) inst).getTarget(); |
389 | 0 | ((SubroutineImpl) getSubroutine(leader)).addEnteringJsrInstruction(all[i]); |
390 | } | |
391 | } | |
392 | ||
393 | // Now do a closure computation from every subroutine leader to find all the | |
394 | // instructions that belong to a subroutine. | |
395 | 0 | HashSet instructions_assigned = new HashSet(); // we don't want to assign an instruction to two or more Subroutine objects. |
396 | ||
397 | 0 | iter = sub_leaders.iterator(); |
398 | 0 | while (iter.hasNext()){ |
399 | // set of InstructionHandles reachable from the top | |
400 | 0 | Set closure = new HashSet(); |
401 | ||
402 | // Init Queue. Start with the entry point of closure. | |
403 | 0 | InstructionHandle leader = (InstructionHandle) (iter.next()); |
404 | 0 | ArrayList Q = new ArrayList(); |
405 | 0 | Q.add(leader); |
406 | ||
407 | 0 | while (!Q.isEmpty()){ |
408 | 0 | while (!Q.isEmpty()){ |
409 | 0 | InstructionHandle u = (InstructionHandle) Q.remove(Q.size()-1); |
410 | 0 | if(closure.add(u)) { |
411 | 0 | InstructionHandle[] successors = getSuccessors(u); |
412 | 0 | for (int i=0; i<successors.length; i++){ |
413 | 0 | Q.add(successors[i]); |
414 | } | |
415 | } | |
416 | 0 | } |
417 | // check if exception handlers are reachable from the closure computed thus far. | |
418 | // conceptually, an exception handler is a successor of each instruction inside | |
419 | // the protected region, but the computation works faster if we don't implement it | |
420 | // in a straight-forward way. Instead, we occasionally check if the first instruction | |
421 | // of the protected region is in the closure, and if so, we know that the exception | |
422 | // handler should also be in the closure. | |
423 | // | |
424 | // "one instruction must be always in at-most one subroutine" JVM requirement | |
425 | // guarantees that the entire protected region always belongs to the same closure, | |
426 | // so just checking the start instruction is suffice. | |
427 | 0 | for( int i=0; i<handlers.length; i++ ) { |
428 | 0 | if(closure.contains(handlers[i].getStartPC())) { |
429 | 0 | InstructionHandle handlerPC = handlers[i].getHandlerPC(); |
430 | 0 | if(!closure.contains(handlerPC)) { |
431 | 0 | Q.add(handlerPC); |
432 | } | |
433 | } | |
434 | } | |
435 | 0 | } |
436 | // DFS ended above. | |
437 | 0 | ((SubroutineImpl) (leader==all[0]?getTopLevel():getSubroutine(leader))).setInstructions(closure); |
438 | ||
439 | 0 | for (Iterator itr = closure.iterator(); itr.hasNext();) { |
440 | 0 | InstructionHandle h = (InstructionHandle) itr.next(); |
441 | 0 | if(!instructions_assigned.add(h)) { |
442 | 0 | throw new StructuralCodeConstraintException("Instruction '"+h+"' is part of more than one subroutine (or of the top level and a subroutine)."); |
443 | } | |
444 | 0 | } |
445 | ||
446 | 0 | if (leader != all[0]){// If we don't deal with the top-level 'subroutine' |
447 | 0 | ((SubroutineImpl) getSubroutine(leader)).setLeavingRET(); |
448 | } | |
449 | 0 | } |
450 | ||
451 | // Now make sure no subroutine is calling a subroutine | |
452 | // that uses the same local variable for the RET as themselves | |
453 | // (recursively). | |
454 | // This includes that subroutines may not call themselves | |
455 | // recursively, even not through intermediate calls to other | |
456 | // subroutines. | |
457 | 0 | noRecursiveCalls(getTopLevel(), new HashSet()); |
458 | ||
459 | 0 | } |
460 | ||
461 | /** | |
462 | * This (recursive) utility method makes sure that | |
463 | * no subroutine is calling a subroutine | |
464 | * that uses the same local variable for the RET as themselves | |
465 | * (recursively). | |
466 | * This includes that subroutines may not call themselves | |
467 | * recursively, even not through intermediate calls to other | |
468 | * subroutines. | |
469 | * | |
470 | * @throws StructuralCodeConstraintException if the above constraint is not satisfied. | |
471 | */ | |
472 | private void noRecursiveCalls(Subroutine sub, HashSet set){ | |
473 | 0 | Subroutine[] subs = sub.subSubs(); |
474 | ||
475 | 0 | for (int i=0; i<subs.length; i++){ |
476 | 0 | int index = ((RET) (subs[i].getLeavingRET().getInstruction())).getIndex(); |
477 | ||
478 | 0 | if (!set.add(new Integer(index))){ |
479 | // Don't use toString() here because of possibly infinite recursive subSubs() calls then. | |
480 | 0 | SubroutineImpl si = (SubroutineImpl) subs[i]; |
481 | 0 | throw new StructuralCodeConstraintException("Subroutine with local variable '"+si.localVariable+"', JSRs '"+si.theJSRs+"', RET '"+si.theRET+"' is called by a subroutine which uses the same local variable index as itself; maybe even a recursive call? JustIce's clean definition of a subroutine forbids both."); |
482 | } | |
483 | ||
484 | 0 | noRecursiveCalls(subs[i], set); |
485 | ||
486 | 0 | set.remove(new Integer(index)); |
487 | } | |
488 | 0 | } |
489 | ||
490 | /** | |
491 | * Returns the Subroutine object associated with the given | |
492 | * leader (that is, the first instruction of the subroutine). | |
493 | * You must not use this to get the top-level instructions | |
494 | * modeled as a Subroutine object. | |
495 | * | |
496 | * @see #getTopLevel() | |
497 | */ | |
498 | public Subroutine getSubroutine(InstructionHandle leader){ | |
499 | 0 | Subroutine ret = (Subroutine) subroutines.get(leader); |
500 | ||
501 | 0 | if (ret == null){ |
502 | 0 | throw new AssertionViolatedException("Subroutine requested for an InstructionHandle that is not a leader of a subroutine."); |
503 | } | |
504 | ||
505 | 0 | if (ret == TOPLEVEL){ |
506 | 0 | throw new AssertionViolatedException("TOPLEVEL special subroutine requested; use getTopLevel()."); |
507 | } | |
508 | ||
509 | 0 | return ret; |
510 | } | |
511 | ||
512 | /** | |
513 | * Returns the subroutine object associated with the | |
514 | * given instruction. This is a costly operation, you | |
515 | * should consider using getSubroutine(InstructionHandle). | |
516 | * Returns 'null' if the given InstructionHandle lies | |
517 | * in so-called 'dead code', i.e. code that can never | |
518 | * be executed. | |
519 | * | |
520 | * @see #getSubroutine(InstructionHandle) | |
521 | * @see #getTopLevel() | |
522 | */ | |
523 | public Subroutine subroutineOf(InstructionHandle any){ | |
524 | 0 | Iterator i = subroutines.values().iterator(); |
525 | 0 | while (i.hasNext()){ |
526 | 0 | Subroutine s = (Subroutine) i.next(); |
527 | 0 | if (s.contains(any)) return s; |
528 | 0 | } |
529 | 0 | System.err.println("DEBUG: Please verify '"+any+"' lies in dead code."); |
530 | 0 | return null; |
531 | //throw new AssertionViolatedException("No subroutine for InstructionHandle found (DEAD CODE?)."); | |
532 | } | |
533 | ||
534 | /** | |
535 | * For easy handling, the piece of code that is <B>not</B> a | |
536 | * subroutine, the top-level, is also modeled as a Subroutine | |
537 | * object. | |
538 | * It is a special Subroutine object where <B>you must not invoke | |
539 | * getEnteringJsrInstructions() or getLeavingRET()</B>. | |
540 | * | |
541 | * @see Subroutine#getEnteringJsrInstructions() | |
542 | * @see Subroutine#getLeavingRET() | |
543 | */ | |
544 | public Subroutine getTopLevel(){ | |
545 | 0 | return TOPLEVEL; |
546 | } | |
547 | ||
548 | 0 | static final InstructionHandle[] empty = new InstructionHandle[0]; |
549 | ||
550 | /** | |
551 | * A utility method that calculates the successors of a given InstructionHandle | |
552 | * <B>in the same subroutine</B>. That means, a RET does not have any successors | |
553 | * as defined here. A JsrInstruction has its physical successor as its successor | |
554 | * (opposed to its target) as defined here. | |
555 | */ | |
556 | private static InstructionHandle[] getSuccessors(InstructionHandle instruction){ | |
557 | 0 | Instruction inst = instruction.getInstruction(); |
558 | ||
559 | 0 | if (inst instanceof RET){ |
560 | 0 | return empty; |
561 | } | |
562 | ||
563 | // Terminates method normally. | |
564 | 0 | if (inst instanceof ReturnInstruction){ |
565 | 0 | return empty; |
566 | } | |
567 | ||
568 | // Terminates method abnormally, because JustIce mandates | |
569 | // subroutines not to be protected by exception handlers. | |
570 | 0 | if (inst instanceof ATHROW){ |
571 | 0 | return empty; |
572 | } | |
573 | ||
574 | 0 | final InstructionHandle[] single = new InstructionHandle[1]; |
575 | ||
576 | // See method comment. | |
577 | 0 | if (inst instanceof JsrInstruction){ |
578 | 0 | single[0] = instruction.getNext(); |
579 | 0 | return single; |
580 | } | |
581 | ||
582 | 0 | if (inst instanceof GotoInstruction){ |
583 | 0 | single[0] = ((GotoInstruction) inst).getTarget(); |
584 | 0 | return single; |
585 | } | |
586 | ||
587 | 0 | if (inst instanceof BranchInstruction){ |
588 | 0 | if (inst instanceof Select){ |
589 | // BCEL's getTargets() returns only the non-default targets, | |
590 | // thanks to Eli Tilevich for reporting. | |
591 | 0 | InstructionHandle[] matchTargets = ((Select) inst).getTargets(); |
592 | 0 | InstructionHandle[] ret = new InstructionHandle[matchTargets.length+1]; |
593 | 0 | ret[0] = ((Select) inst).getTarget(); |
594 | 0 | System.arraycopy(matchTargets, 0, ret, 1, matchTargets.length); |
595 | 0 | return ret; |
596 | } | |
597 | else{ | |
598 | 0 | final InstructionHandle[] pair = new InstructionHandle[2]; |
599 | 0 | pair[0] = instruction.getNext(); |
600 | 0 | pair[1] = ((BranchInstruction) inst).getTarget(); |
601 | 0 | return pair; |
602 | } | |
603 | } | |
604 | ||
605 | // default case: Fall through. | |
606 | 0 | single[0] = instruction.getNext(); |
607 | 0 | return single; |
608 | } | |
609 | ||
610 | /** | |
611 | * Returns a String representation of this object; merely for debugging puposes. | |
612 | */ | |
613 | public String toString(){ | |
614 | 0 | return "---\n"+subroutines.toString()+"\n---\n"; |
615 | } | |
616 | } |