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