in src/main/java/org/apache/bcel/verifier/structurals/Subroutines.java [420:547]
public Subroutines(final MethodGen mg, final boolean enableJustIceCheck) {
final InstructionHandle[] all = mg.getInstructionList().getInstructionHandles();
final CodeExceptionGen[] handlers = mg.getExceptionHandlers();
// Define our "Toplevel" fake subroutine.
TOPLEVEL = new SubroutineImpl();
// Calculate "real" subroutines.
final Set<InstructionHandle> subLeaders = new HashSet<>(); // Elements: InstructionHandle
for (final InstructionHandle element : all) {
final Instruction inst = element.getInstruction();
if (inst instanceof JsrInstruction) {
subLeaders.add(((JsrInstruction) inst).getTarget());
}
}
// Build up the database.
for (final InstructionHandle astore : subLeaders) {
final SubroutineImpl sr = new SubroutineImpl();
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);
subLeaders.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 (final InstructionHandle element : all) {
final Instruction inst = element.getInstruction();
if (inst instanceof JsrInstruction) {
final InstructionHandle leader = ((JsrInstruction) inst).getTarget();
((SubroutineImpl) getSubroutine(leader)).addEnteringJsrInstruction(element);
}
}
// Now do a BFS from every subroutine leader to find all the
// instructions that belong to a subroutine.
// we don't want to assign an instruction to two or more Subroutine objects.
final Set<InstructionHandle> instructionsAssigned = new HashSet<>();
// Graph coloring. Key: InstructionHandle, Value: ColourConstants enum.
final Map<InstructionHandle, ColourConstants> colors = new HashMap<>();
final List<InstructionHandle> qList = new ArrayList<>();
for (final InstructionHandle actual : subLeaders) {
// Do some BFS with "actual" as the root of the graph.
// Init colors
for (final InstructionHandle element : all) {
colors.put(element, ColourConstants.WHITE);
}
colors.put(actual, ColourConstants.GRAY);
// Init Queue
qList.clear();
qList.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 (final CodeExceptionGen handler : handlers) {
colors.put(handler.getHandlerPC(), ColourConstants.GRAY);
qList.add(handler.getHandlerPC());
}
}
/* CONTINUE NORMAL BFS ALGORITHM */
// Loop until Queue is empty
while (!qList.isEmpty()) {
final InstructionHandle u = qList.remove(0);
final InstructionHandle[] successors = getSuccessors(u);
for (final InstructionHandle successor : successors) {
if (colors.get(successor) == ColourConstants.WHITE) {
colors.put(successor, ColourConstants.GRAY);
qList.add(successor);
}
}
colors.put(u, ColourConstants.BLACK);
}
// BFS ended above.
for (final InstructionHandle element : all) {
if (colors.get(element) == ColourConstants.BLACK) {
((SubroutineImpl) (actual == all[0] ? getTopLevel() : getSubroutine(actual))).addInstruction(element);
if (instructionsAssigned.contains(element)) {
throw new StructuralCodeConstraintException(
"Instruction '" + element + "' is part of more than one subroutine (or of the top level and a subroutine).");
}
instructionsAssigned.add(element);
}
}
if (actual != all[0]) { // If we don't deal with the top-level 'subroutine'
((SubroutineImpl) getSubroutine(actual)).setLeavingRET();
}
}
if (enableJustIceCheck) {
// Now make sure no instruction of a Subroutine is protected by exception handling code
// as is mandated by JustIces notion of subroutines.
for (final CodeExceptionGen handler : handlers) {
InstructionHandle protectedIh = handler.getStartPC();
while (protectedIh != handler.getEndPC().getNext()) {
// Note the inclusive/inclusive notation of "generic API" exception handlers!
for (final Subroutine sub : subroutines.values()) {
if (sub != subroutines.get(all[0]) && sub.contains(protectedIh)) {
throw new StructuralCodeConstraintException("Subroutine instruction '" + protectedIh + "' is protected by an exception handler, '"
+ handler + "'. This is forbidden by the JustIce verifier due to its clear definition of subroutines.");
}
}
protectedIh = protectedIh.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<>());
}