Author: kohsuke
Date: Wed Dec 28 11:55:43 2005
New Revision: 359613
URL: http://svn.apache.org/viewcvs?rev=359613&view=rev
Log:
DFS can use ArrayList better than BFS.
Modified:
jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/Subroutines.java
Modified:
jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/Subroutines.java
URL:
http://svn.apache.org/viewcvs/jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/Subroutines.java?rev=359613&r1=359612&r2=359613&view=diff
==============================================================================
---
jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/Subroutines.java
(original)
+++
jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/Subroutines.java
Wed Dec 28 11:55:43 2005
@@ -86,25 +86,25 @@
/** The instructions that belong to this subroutine. */
private Set instructions;
-
+
/*
* Refer to the Subroutine interface for documentation.
*/
public boolean contains(InstructionHandle inst){
return instructions.contains(inst);
}
-
+
/**
* The JSR or JSR_W instructions that define this
* subroutine by targeting it.
*/
private HashSet theJSRs = new HashSet();
-
+
/**
* The RET instruction that leaves this subroutine.
*/
private InstructionHandle theRET;
-
+
/**
* Returns a String representation of this object, merely
* for debugging purposes.
@@ -114,7 +114,7 @@
*/
public String toString(){
String ret = "Subroutine: Local variable is
'"+localVariable+"', JSRs are '"+theJSRs+"', RET is '"+theRET+"', Instructions:
'"+instructions.toString()+"'.";
-
+
ret += " Accessed local variable slots: '";
int[] alv = getAccessedLocalsIndices();
for (int i=0; i<alv.length; i++){
@@ -131,7 +131,7 @@
return ret;
}
-
+
/**
* Sets the leaving RET instruction. Must be invoked after all
instructions are added.
* Must not be invoked for top-level 'subroutine'.
@@ -161,7 +161,7 @@
}
theRET = ret;
}
-
+
/*
* Refer to the Subroutine interface for documentation.
*/
@@ -172,7 +172,7 @@
InstructionHandle[] jsrs = new
InstructionHandle[theJSRs.size()];
return (InstructionHandle[]) (theJSRs.toArray(jsrs));
}
-
+
/**
* Adds a new JSR or JSR_W that has this subroutine as its
target.
*/
@@ -203,7 +203,7 @@
}
return theRET;
}
-
+
/*
* Refer to the Subroutine interface for documentation.
*/
@@ -211,7 +211,7 @@
InstructionHandle[] ret = new
InstructionHandle[instructions.size()];
return (InstructionHandle[]) instructions.toArray(ret);
}
-
+
/* Satisfies Subroutine.getRecursivelyAccessedLocalsIndices().
*/
public int[] getRecursivelyAccessedLocalsIndices(){
HashSet s = new HashSet();
@@ -276,7 +276,7 @@
}
}
}
-
+
int[] ret = new int[acc.size()];
i = acc.iterator();
int j=-1;
@@ -304,7 +304,7 @@
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.
@@ -319,7 +319,7 @@
localVariable = i;
}
}
-
+
/**
* The default constructor.
*/
@@ -352,7 +352,7 @@
* create the Subroutine objects of.
*/
public Subroutines(MethodGen mg){
-
+
InstructionHandle[] all =
mg.getInstructionList().getInstructionHandles();
CodeExceptionGen[] handlers = mg.getExceptionHandlers();
@@ -367,7 +367,7 @@
sub_leaders.add(((JsrInstruction)
inst).getTarget());
}
}
-
+
// Build up the database.
Iterator iter = sub_leaders.iterator();
while (iter.hasNext()){
@@ -393,8 +393,8 @@
((SubroutineImpl)
getSubroutine(leader)).addEnteringJsrInstruction(all[i]);
}
}
-
- // Now do a BFS from every subroutine leader to find all the
+
+ // Now do a closure computation 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.
@@ -407,7 +407,7 @@
InstructionHandle actual = (InstructionHandle) (iter.next());
// Init Queue
ArrayList Q = new ArrayList();
- Q.add(actual); // add(Obj) adds to the end, remove(0)
removes from the start.
+ Q.add(actual);
/* 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]){
@@ -416,9 +416,9 @@
}
}
/* CONTINUE NORMAL BFS ALGORITHM */
-
+
while (!Q.isEmpty()){
- InstructionHandle u = (InstructionHandle)
Q.remove(0);
+ InstructionHandle u = (InstructionHandle)
Q.remove(Q.size()-1);
if(closure.add(u)) {
InstructionHandle[] successors = getSuccessors(u);
for (int i=0; i<successors.length; i++){
@@ -435,12 +435,12 @@
throw new StructuralCodeConstraintException("Instruction
'"+h+"' is part of more than one subroutine (or of the top level and a
subroutine).");
}
}
-
+
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++){
@@ -458,7 +458,7 @@
_protected = _protected.getNext();
}
}*/
-
+
// Now make sure no subroutine is calling a subroutine
// that uses the same local variable for the RET as themselves
// (recursively).
@@ -485,7 +485,7 @@
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];
@@ -493,11 +493,11 @@
}
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).
@@ -508,7 +508,7 @@
*/
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.");
}
@@ -516,7 +516,7 @@
if (ret == TOPLEVEL){
throw new AssertionViolatedException("TOPLEVEL special
subroutine requested; use getTopLevel().");
}
-
+
return ret;
}
@@ -565,24 +565,24 @@
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();
@@ -611,7 +611,7 @@
}
}
- // default case: Fall through.
+ // default case: Fall through.
single[0] = instruction.getNext();
return single;
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
