Review

finding-7

/mubench/checkouts/bcel/24014e5/build/src/main/java/org/apache/commons/bcel6/verifier/structurals/Subroutines.java

Subroutines(MethodGen, boolean)

class Subroutines {
    /**
     * Constructor.
     * @param mg A MethodGen object representing method to
     * create the Subroutine objects of.
     * @param enableJustIceCheck whether to enable additional JustIce checks
     * @since 6.0
     */
    public Subroutines(MethodGen mg, boolean enableJustIceCheck){
        InstructionHandle[] all = mg.getInstructionList().getInstructionHandles();
        CodeExceptionGen[] handlers = mg.getExceptionHandlers();
        // Define our "Toplevel" fake subroutine.
        TOPLEVEL = new SubroutineImpl();
        // Calculate "real" subroutines.
        Set<InstructionHandle> sub_leaders = new HashSet<>(); // Elements: InstructionHandle
        for (InstructionHandle element : all) {
            Instruction inst = element.getInstruction();
            if (inst instanceof JsrInstruction){
                sub_leaders.add(((JsrInstruction) inst).getTarget());
            }
        }
        // Build up the database.
        for (InstructionHandle astore : sub_leaders) {
            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);
        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 (InstructionHandle element : all) {
            Instruction inst = element.getInstruction();
            if (inst instanceof JsrInstruction){
                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.
        Set<InstructionHandle> instructions_assigned = new HashSet<>();
        //Graph colouring. Key: InstructionHandle, Value: ColourConstants enum .
        Map<InstructionHandle, ColourConstants> colors = new HashMap<>();
        List<InstructionHandle> Q = new ArrayList<>();        
        for (InstructionHandle actual : sub_leaders) {
            // Do some BFS with "actual" as the root of the graph.
            // Init colors
            for (InstructionHandle element : all) {
                colors.put(element, ColourConstants.WHITE);
            }
            colors.put(actual, ColourConstants.GRAY);
            // Init Queue
            Q.clear();
            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 (CodeExceptionGen handler : handlers) {
                    colors.put(handler.getHandlerPC(), ColourConstants.GRAY);
                    Q.add(handler.getHandlerPC());
                }
            }
            /* CONTINUE NORMAL BFS ALGORITHM */
            // Loop until Queue is empty
            while (Q.size() != 0){
                InstructionHandle u = Q.remove(0);
                InstructionHandle[] successors = getSuccessors(u);
                for (InstructionHandle successor : successors) {
                    if (colors.get(successor) == ColourConstants.WHITE){
                        colors.put(successor, ColourConstants.GRAY);
                        Q.add(successor);
                    }
                }
                colors.put(u, ColourConstants.BLACK);
            }
            // BFS ended above.
            for (InstructionHandle element : all) {
                if (colors.get(element) == ColourConstants.BLACK){
                    ((SubroutineImpl) (actual==all[0]?getTopLevel():getSubroutine(actual))).addInstruction(element);
                    if (instructions_assigned.contains(element)){
                        throw new StructuralCodeConstraintException("Instruction '"+element+
                            "' is part of more than one subroutine (or of the top level and a subroutine).");
                    }
                    instructions_assigned.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 (CodeExceptionGen handler : handlers) {
                InstructionHandle _protected = handler.getStartPC();
                while (_protected != handler.getEndPC().getNext()){
                    // Note the inclusive/inclusive notation of "generic API" exception handlers!
                    for (Subroutine sub : subroutines.values()) {
                        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, '"+handler+
                                    "'. 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<Integer>());
    }
}