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

This page was automatically generated by Maven