Subroutines xref

View Javadoc

    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 }