subroutines.java

该开源工具主要用于class文件的操作

					h.add(getSubroutine(targ));
				}
			}
			Subroutine[] ret = new Subroutine[h.size()];
			return (Subroutine[]) h.toArray(ret);
		}
		
		/*
		 * Sets the local variable slot the ASTORE that is targeted
		 * by the JsrInstructions of this subroutine operates on.
		 * This subroutine's RET operates on that same local variable
		 * slot, of course.
		 */
		void setLocalVariable(int i){
			if (localVariable != UNSET){
				throw new AssertionViolatedException("localVariable set twice.");
			}
			else{
				localVariable = i;
			}
		}
		
		/**
		 * The default constructor.
		 */
		public SubroutineImpl(){
		}

	}// end Inner Class SubrouteImpl

	/**
	 * The Hashtable containing the subroutines found.
	 * Key: InstructionHandle of the leader of the subroutine.
	 * Elements: SubroutineImpl objects.
	 */
	private Hashtable subroutines = new Hashtable();

	/**
	 * This is referring to a special subroutine, namely the
	 * top level. This is not really a subroutine but we use
	 * it to distinguish between top level instructions and
	 * unreachable instructions.
	 */
	public final Subroutine TOPLEVEL;

	/**
	 * Constructor.
	 * @param il A MethodGen object representing method to
	 * create the Subroutine objects of.
	 */
	public Subroutines(MethodGen mg){
	
		InstructionHandle[] all = mg.getInstructionList().getInstructionHandles();
		CodeExceptionGen[] handlers = mg.getExceptionHandlers();

		// Define our "Toplevel" fake subroutine.
		TOPLEVEL = new SubroutineImpl();

		// Calculate "real" subroutines.
		HashSet sub_leaders = new HashSet(); // Elements: InstructionHandle
		InstructionHandle ih = all[0];
		for (int i=0; i<all.length; i++){
			Instruction inst = all[i].getInstruction();
			if (inst instanceof JsrInstruction){
				sub_leaders.add(((JsrInstruction) inst).getTarget());
			}
		}
 
		// Build up the database.
		Iterator iter = sub_leaders.iterator();
		while (iter.hasNext()){
			SubroutineImpl sr = new SubroutineImpl();
			InstructionHandle astore = (InstructionHandle) (iter.next());
			sr.setLocalVariable( ((ASTORE) (astore.getInstruction())).getIndex() );
			subroutines.put(astore, sr);
		}

		// Fake it a bit. We want a virtual "TopLevel" subroutine.
		subroutines.put(all[0], TOPLEVEL);
		sub_leaders.add(all[0]);

		// Tell the subroutines about their JsrInstructions.
		// Note that there cannot be a JSR targeting the top-level
		// since "Jsr 0" is disallowed in Pass 3a.
		// Instructions shared by a subroutine and the toplevel are
		// disallowed and checked below, after the BFS.
		for (int i=0; i<all.length; i++){
			Instruction inst = all[i].getInstruction();
			if (inst instanceof JsrInstruction){
				InstructionHandle leader = ((JsrInstruction) inst).getTarget();
				((SubroutineImpl) getSubroutine(leader)).addEnteringJsrInstruction(all[i]);
			}
		}
		
		// Now do a BFS from every subroutine leader to find all the
		// instructions that belong to a subroutine.
		HashSet instructions_assigned = new HashSet(); // we don't want to assign an instruction to two or more Subroutine objects.
		
		Hashtable colors = new Hashtable(); //Graph colouring. Key: InstructionHandle, Value: java.awt.Color .
		
		iter = sub_leaders.iterator();
		while (iter.hasNext()){
			// Do some BFS with "actual" as the root of the graph.
			InstructionHandle actual = (InstructionHandle) (iter.next());
			// Init colors
			for (int i=0; i<all.length; i++){
				colors.put(all[i], Color.white);
			}
			colors.put(actual, Color.gray);
			// Init Queue
			ArrayList Q = new ArrayList();
			Q.add(actual); // add(Obj) adds to the end, remove(0) removes from the start.
			
			/* 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.]*/
			if (actual == all[0]){
				for (int j=0; j<handlers.length; j++){
					colors.put(handlers[j].getHandlerPC(), Color.gray);
					Q.add(handlers[j].getHandlerPC());
				}
			}
			/* CONTINUE NORMAL BFS ALGORITHM */
			
			// Loop until Queue is empty
			while (Q.size() != 0){
				InstructionHandle u = (InstructionHandle) Q.remove(0);
				InstructionHandle[] successors = getSuccessors(u);
				for (int i=0; i<successors.length; i++){
					if (((Color) colors.get(successors[i])) == Color.white){
						colors.put(successors[i], Color.gray);
						Q.add(successors[i]);
					}
				}
				colors.put(u, Color.black);
			}
			// BFS ended above.
			for (int i=0; i<all.length; i++){
				if (colors.get(all[i]) == Color.black){
					((SubroutineImpl) (actual==all[0]?getTopLevel():getSubroutine(actual))).addInstruction(all[i]);
					if (instructions_assigned.contains(all[i])){
						throw new StructuralCodeConstraintException("Instruction '"+all[i]+"' is part of more than one subroutine (or of the top level and a subroutine).");
					}
					else{
						instructions_assigned.add(all[i]);
					}
				}
			}
			if (actual != all[0]){// If we don't deal with the top-level 'subroutine'
				((SubroutineImpl) getSubroutine(actual)).setLeavingRET();
			}
		}
		
		// Now make sure no instruction of a Subroutine is protected by exception handling code
		// as is mandated by JustIces notion of subroutines.
		for (int i=0; i<handlers.length; i++){
			InstructionHandle _protected = handlers[i].getStartPC();
			while (_protected != handlers[i].getEndPC().getNext()){// Note the inclusive/inclusive notation of "generic API" exception handlers!
				Enumeration subs = subroutines.elements();
				while (subs.hasMoreElements()){
					Subroutine sub = (Subroutine) subs.nextElement();
					if (sub != subroutines.get(all[0])){	// We don't want to forbid top-level exception handlers.
						if (sub.contains(_protected)){
							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.");
						}
					}
				}
				_protected = _protected.getNext();
			}
		}
		
		// Now make sure no subroutine is calling a subroutine
		// that uses the same local variable for the RET as themselves
		// (recursively).
		// This includes that subroutines may not call themselves
		// recursively, even not through intermediate calls to other
		// subroutines.
		noRecursiveCalls(getTopLevel(), new HashSet());

	}

	/**
	 * This (recursive) utility method makes sure that
	 * no subroutine is calling a subroutine
	 * that uses the same local variable for the RET as themselves
	 * (recursively).
	 * This includes that subroutines may not call themselves
	 * recursively, even not through intermediate calls to other
	 * subroutines.
	 *
	 * @throws StructuralCodeConstraintException if the above constraint is not satisfied.
	 */
	private void noRecursiveCalls(Subroutine sub, HashSet set){
		Subroutine[] subs = sub.subSubs();

		for (int i=0; i<subs.length; i++){
			int index = ((RET) (subs[i].getLeavingRET().getInstruction())).getIndex();
			
			if (!set.add(new Integer(index))){
				// Don't use toString() here because of possibly infinite recursive subSubs() calls then.
				SubroutineImpl si = (SubroutineImpl) subs[i];
				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.");
			}

			noRecursiveCalls(subs[i], set);
			
			set.remove(new Integer(index));
		}
	} 
	
	/**
	 * Returns the Subroutine object associated with the given
	 * leader (that is, the first instruction of the subroutine).
	 * You must not use this to get the top-level instructions
	 * modeled as a Subroutine object.
	 *
	 * @see #getTopLevel()
	 */
	public Subroutine getSubroutine(InstructionHandle leader){
		Subroutine ret = (Subroutine) subroutines.get(leader);
		
		if (ret == null){
			throw new AssertionViolatedException("Subroutine requested for an InstructionHandle that is not a leader of a subroutine.");
		}

		if (ret == TOPLEVEL){
			throw new AssertionViolatedException("TOPLEVEL special subroutine requested; use getTopLevel().");
		}
		
		return ret;
	}

	/**
	 * Returns the subroutine object associated with the
	 * given instruction. This is a costly operation, you
	 * should consider using getSubroutine(InstructionHandle).
	 * Returns 'null' if the given InstructionHandle lies
	 * in so-called 'dead code', i.e. code that can never
	 * be executed.
	 *
	 * @see #getSubroutine(InstructionHandle)
	 * @see #getTopLevel()
	 */
	public Subroutine subroutineOf(InstructionHandle any){
		Iterator i = subroutines.values().iterator();
		while (i.hasNext()){
			Subroutine s = (Subroutine) i.next();
			if (s.contains(any)) return s;
		}
System.err.println("DEBUG: Please verify '"+any+"' lies in dead code.");
		return null;
		//throw new AssertionViolatedException("No subroutine for InstructionHandle found (DEAD CODE?).");
	}

	/**
	 * For easy handling, the piece of code that is <B>not</B> a
	 * subroutine, the top-level, is also modeled as a Subroutine
	 * object.
	 * It is a special Subroutine object where <B>you must not invoke
	 * getEnteringJsrInstructions() or getLeavingRET()</B>.
	 *
	 * @see Subroutine#getEnteringJsrInstructions()
	 * @see Subroutine#getLeavingRET()
	 */
	public Subroutine getTopLevel(){
		return TOPLEVEL;
	}
	/**
	 * A utility method that calculates the successors of a given InstructionHandle
	 * <B>in the same subroutine</B>. That means, a RET does not have any successors
	 * as defined here. A JsrInstruction has its physical successor as its successor
	 * (opposed to its target) as defined here.
	 */
	private static InstructionHandle[] getSuccessors(InstructionHandle instruction){
		final InstructionHandle[] empty = new InstructionHandle[0];
		final InstructionHandle[] single = new InstructionHandle[1];
		final InstructionHandle[] pair = new InstructionHandle[2];
		
		Instruction inst = instruction.getInstruction();
		
		if (inst instanceof RET){
			return empty;
		}
		
		// Terminates method normally.
		if (inst instanceof ReturnInstruction){
			return empty;
		}
		
		// Terminates method abnormally, because JustIce mandates
		// subroutines not to be protected by exception handlers.
		if (inst instanceof ATHROW){
			return empty;
		}
		
		// See method comment.
		if (inst instanceof JsrInstruction){
			single[0] = instruction.getNext();
			return single;
		}

		if (inst instanceof GotoInstruction){
			single[0] = ((GotoInstruction) inst).getTarget();
			return single;
		}

		if (inst instanceof BranchInstruction){
			if (inst instanceof Select){
				// BCEL's getTargets() returns only the non-default targets,
				// thanks to Eli Tilevich for reporting.
				InstructionHandle[] matchTargets = ((Select) inst).getTargets();
				InstructionHandle[] ret = new InstructionHandle[matchTargets.length+1];
				ret[0] = ((Select) inst).getTarget();
				System.arraycopy(matchTargets, 0, ret, 1, matchTargets.length);
				return ret;
			}
			else{
				pair[0] = instruction.getNext();
				pair[1] = ((BranchInstruction) inst).getTarget();
				return pair;
			}
		}

		// default case: Fall through.		
		single[0] = instruction.getNext();
		return single;
	}

	/**
	 * Returns a String representation of this object; merely for debugging puposes.
	 */
	public String toString(){
		return "---\n"+subroutines.toString()+"\n---\n";
	}
}