    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 *  Unless required by applicable law or agreed to in writing, software
    012 *  distributed under the License is distributed on an "AS IS" BASIS,
    013 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 *  See the License for the specific language governing permissions and
    015 *  limitations under the License.
    016 *
    017 */
    018package org.apache.bcel.verifier.structurals;
    019
    020
    021import java.util.ArrayList;
    022import java.util.HashMap;
    023import java.util.List;
    024import java.util.Map;
    025
    026import org.apache.bcel.generic.ATHROW;
    027import org.apache.bcel.generic.BranchInstruction;
    028import org.apache.bcel.generic.GotoInstruction;
    029import org.apache.bcel.generic.Instruction;
    030import org.apache.bcel.generic.InstructionHandle;
    031import org.apache.bcel.generic.JsrInstruction;
    032import org.apache.bcel.generic.MethodGen;
    033import org.apache.bcel.generic.RET;
    034import org.apache.bcel.generic.ReturnInstruction;
    035import org.apache.bcel.generic.Select;
    036import org.apache.bcel.verifier.exc.AssertionViolatedException;
    037import org.apache.bcel.verifier.exc.StructuralCodeConstraintException;
    038
    039/**
    040 * This class represents a control flow graph of a method.
    041 *
    042 * @version $Id$
    043 */
    044public class ControlFlowGraph{
    045
    046    /**
    047     * Objects of this class represent a node in a ControlFlowGraph.
    048     * These nodes are instructions, not basic blocks.
    049     */
    050    private class InstructionContextImpl implements InstructionContext{
    051
    052        /**
    053         * The TAG field is here for external temporary flagging, such
    054         * as graph colouring.
    055         *
    056         * @see #getTag()
    057         * @see #setTag(int)
    058         */
    059        private int TAG;
    060
    061        /**
    062         * The InstructionHandle this InstructionContext is wrapped around.
    063         */
    064        private final InstructionHandle instruction;
    065
    066        /**
    067         * The 'incoming' execution Frames.
    068         */
    069        private final Map<InstructionContext, Frame> inFrames;    // key: the last-executed JSR
    070
    071        /**
    072         * The 'outgoing' execution Frames.
    073         */
    074        private final Map<InstructionContext, Frame> outFrames; // key: the last-executed JSR
    075
    076        /**
    077         * The 'execution predecessors' - a list of type InstructionContext
    078         * of those instances that have been execute()d before in that order.
    079         */
    080        private List<InstructionContext> executionPredecessors = null; // Type: InstructionContext
    081
    082        /**
    083         * Creates an InstructionHandleImpl object from an InstructionHandle.
    084         * Creation of one per InstructionHandle suffices. Don't create more.
    085         */
    086        public InstructionContextImpl(final InstructionHandle inst) {
    087            if (inst == null) {
    088                throw new AssertionViolatedException("Cannot instantiate InstructionContextImpl from NULL.");
    089            }
    090
    091            instruction = inst;
    092            inFrames = new HashMap<>();
    093            outFrames = new HashMap<>();
    094        }
    095
    096        /* Satisfies InstructionContext.getTag(). */
    097        @Override
    098        public int getTag() {
    099            return TAG;
    100        }
    101
    102        /* Satisfies InstructionContext.setTag(int). */
    103        @Override
    104        public void setTag(final int tag) { // part of InstructionContext interface
    105            TAG = tag;
    106        }
    107
    108        /**
    109         * Returns the exception handlers of this instruction.
    110         */
    111        @Override
    112        public ExceptionHandler[] getExceptionHandlers() {
    113            return exceptionhandlers.getExceptionHandlers(getInstruction());
    114        }
    115
    116        /**
    117         * Returns a clone of the "outgoing" frame situation with respect to the given ExecutionChain.
    118         */
    119        @Override
    120        public Frame getOutFrame(final ArrayList<InstructionContext> execChain) {
    121            executionPredecessors = execChain;
    122
    123            Frame org;
    124
    125            final InstructionContext jsr = lastExecutionJSR();
    126
    127            org = outFrames.get(jsr);
    128
    129            if (org == null) {
    130                throw new AssertionViolatedException(
    131                    "outFrame not set! This:\n"+this+"\nExecutionChain: "+getExecutionChain()+"\nOutFrames: '"+outFrames+"'.");
    132            }
    133            return org.getClone();
    134        }
    135
    136    @Override
    137    public Frame getInFrame() {
    138          Frame org;
    139
    140            final InstructionContext jsr = lastExecutionJSR();
    141
    142            org = inFrames.get(jsr);
    143
    144            if (org == null) {
    145                throw new AssertionViolatedException("inFrame not set! This:\n"+this+"\nInFrames: '"+inFrames+"'.");
    146      }
    147      return org.getClone();
    148    }
    149
    150        /**
    151         * "Merges in" (vmspec2, page 146) the "incoming" frame situation;
    152         * executes the instructions symbolically
    153         * and therefore calculates the "outgoing" frame situation.
    154         * Returns: True iff the "incoming" frame situation changed after
    155         * merging with "inFrame".
    156         * The execPreds ArrayList must contain the InstructionContext
    157         * objects executed so far in the correct order. This is just
    158         * one execution path [out of many]. This is needed to correctly
    159         * "merge" in the special case of a RET's successor.
    160         * <B>The InstConstraintVisitor and ExecutionVisitor instances
    161         * must be set up correctly.</B>
    162         * @return true - if and only if the "outgoing" frame situation
    163         * changed from the one before execute()ing.
    164         */
    165        @Override
    166        public boolean execute(final Frame inFrame, final ArrayList<InstructionContext> execPreds, final InstConstraintVisitor icv, final ExecutionVisitor ev) {
    167
    168            @SuppressWarnings("unchecked") // OK because execPreds is compatible type
    169            final List<InstructionContext> clone = (List<InstructionContext>) execPreds.clone();
    170            executionPredecessors = clone;
    171
    172            //sanity check
    173            if ( (lastExecutionJSR() == null) && (subroutines.subroutineOf(getInstruction()) != subroutines.getTopLevel() ) ) {
    174                throw new AssertionViolatedException("Huh?! Am I '"+this+"' part of a subroutine or not?");
    175            }
    176            if ( (lastExecutionJSR() != null) && (subroutines.subroutineOf(getInstruction()) == subroutines.getTopLevel() ) ) {
    177                throw new AssertionViolatedException("Huh?! Am I '"+this+"' part of a subroutine or not?");
    178            }
    179
    180            Frame inF = inFrames.get(lastExecutionJSR());
    181            if (inF == null) {// no incoming frame was set, so set it.
    182                inFrames.put(lastExecutionJSR(), inFrame);
    183                inF = inFrame;
    184            }
    185            else{// if there was an "old" inFrame
    186                if (inF.equals(inFrame)) { //shortcut: no need to merge equal frames.
    187                    return false;
    188                }
    189                if (! mergeInFrames(inFrame)) {
    190                    return false;
    191                }
    192            }
    193
    194            // Now we're sure the inFrame has changed!
    195
    196            // new inFrame is already merged in, see above.
    197            final Frame workingFrame = inF.getClone();
    198
    199            try{
    200                // This verifies the InstructionConstraint for the current
    201                // instruction, but does not modify the workingFrame object.
    202//InstConstraintVisitor icv = InstConstraintVisitor.getInstance(VerifierFactory.getVerifier(method_gen.getClassName()));
    203                icv.setFrame(workingFrame);
    204                getInstruction().accept(icv);
    205            }
    206            catch(final StructuralCodeConstraintException ce) {
    207                ce.extendMessage("","\nInstructionHandle: "+getInstruction()+"\n");
    208                ce.extendMessage("","\nExecution Frame:\n"+workingFrame);
    209                extendMessageWithFlow(ce);
    210                throw ce;
    211            }
    212
    213            // This executes the Instruction.
    214            // Therefore the workingFrame object is modified.
    215//ExecutionVisitor ev = ExecutionVisitor.getInstance(VerifierFactory.getVerifier(method_gen.getClassName()));
    216            ev.setFrame(workingFrame);
    217            getInstruction().accept(ev);
    218            //getInstruction().accept(ExecutionVisitor.withFrame(workingFrame));
    219            outFrames.put(lastExecutionJSR(), workingFrame);
    220
    221            return true;    // new inFrame was different from old inFrame so merging them
    222                                        // yielded a different this.inFrame.
    223        }
    224
    225        /**
    226         * Returns a simple String representation of this InstructionContext.
    227         */
    228        @Override
    229        public String toString() {
    230        //TODO: Put information in the brackets, e.g.
    231        //      Is this an ExceptionHandler? Is this a RET? Is this the start of
    232        //      a subroutine?
    233            final String ret = getInstruction().toString(false)+"\t[InstructionContext]";
    234            return ret;
    235        }
    236
    237        /**
    238         * Does the actual merging (vmspec2, page 146).
    239         * Returns true IFF this.inFrame was changed in course of merging with inFrame.
    240         */
    241        private boolean mergeInFrames(final Frame inFrame) {
    242            // TODO: Can be performance-improved.
    243            final Frame inF = inFrames.get(lastExecutionJSR());
    244            final OperandStack oldstack = inF.getStack().getClone();
    245            final LocalVariables oldlocals = inF.getLocals().getClone();
    246            try {
    247                inF.getStack().merge(inFrame.getStack());
    248                inF.getLocals().merge(inFrame.getLocals());
    249            } catch (final StructuralCodeConstraintException sce) {
    250                extendMessageWithFlow(sce);
    251                throw sce;
    252            }
    253            return !(oldstack.equals(inF.getStack()) && oldlocals.equals(inF.getLocals()));
    254        }
    255
    256        /**
    257         * Returns the control flow execution chain. This is built
    258         * while execute(Frame, ArrayList)-ing the code represented
    259         * by the surrounding ControlFlowGraph.
    260         */
    261        private String getExecutionChain() {
    262            String s = this.toString();
    263            for (int i=executionPredecessors.size()-1; i>=0; i--) {
    264                s = executionPredecessors.get(i)+"\n" + s;
    265            }
    266            return s;
    267        }
    268
    269
    270        /**
    271         * Extends the StructuralCodeConstraintException ("e") object with an at-the-end-extended message.
    272         * This extended message will then reflect the execution flow needed to get to the constraint
    273         * violation that triggered the throwing of the "e" object.
    274         */
    275        private void extendMessageWithFlow(final StructuralCodeConstraintException e) {
    276            final String s = "Execution flow:\n";
    277            e.extendMessage("", s+getExecutionChain());
    278        }
    279
    280        /*
    281         * Fulfils the contract of InstructionContext.getInstruction().
    282         */
    283        @Override
    284        public InstructionHandle getInstruction() {
    285            return instruction;
    286        }
    287
    288        /**
    289         * Returns the InstructionContextImpl with an JSR/JSR_W
    290         * that was last in the ExecutionChain, without
    291         * a corresponding RET, i.e.
    292         * we were called by this one.
    293         * Returns null if we were called from the top level.
    294         */
    295        private InstructionContextImpl lastExecutionJSR() {
    296
    297            final int size = executionPredecessors.size();
    298            int retcount = 0;
    299
    300            for (int i=size-1; i>=0; i--) {
    301                final InstructionContextImpl current = (InstructionContextImpl) (executionPredecessors.get(i));
    302                final Instruction currentlast = current.getInstruction().getInstruction();
    303                if (currentlast instanceof RET) {
    304                    retcount++;
    305                }
    306                if (currentlast instanceof JsrInstruction) {
    307                    retcount--;
    308                    if (retcount == -1) {
    309                        return current;
    310                    }
    311                }
    312            }
    313            return null;
    314        }
    315
    316        /* Satisfies InstructionContext.getSuccessors(). */
    317        @Override
    318        public InstructionContext[] getSuccessors() {
    319            return contextsOf(_getSuccessors());
    320        }
    321
    322        /**
    323         * A utility method that calculates the successors of a given InstructionHandle
    324         * That means, a RET does have successors as defined here.
    325         * A JsrInstruction has its target as its successor
    326         * (opposed to its physical successor) as defined here.
    327         */
    328// TODO: implement caching!
    329        private InstructionHandle[] _getSuccessors() {
    330            final InstructionHandle[] empty = new InstructionHandle[0];
    331            final InstructionHandle[] single = new InstructionHandle[1];
    332
    333            final Instruction inst = getInstruction().getInstruction();
    334
    335            if (inst instanceof RET) {
    336                final Subroutine s = subroutines.subroutineOf(getInstruction());
    337                if (s==null) { //return empty;
    338                    // RET in dead code. "empty" would be the correct answer, but we know something about the surrounding project...
    339                    throw new AssertionViolatedException("Asking for successors of a RET in dead code?!");
    340                }
    341
    342//TODO: remove. Only JustIce must not use it, but foreign users of the ControlFlowGraph
    343//      will want it. Thanks Johannes Wust.
    344//throw new AssertionViolatedException("DID YOU REALLY WANT TO ASK FOR RET'S SUCCS?");
    345
    346                final InstructionHandle[] jsrs = s.getEnteringJsrInstructions();
    347                final InstructionHandle[] ret = new InstructionHandle[jsrs.length];
    348                for (int i=0; i<jsrs.length; i++) {
    349                    ret[i] = jsrs[i].getNext();
    350                }
    351                return ret;
    352            }
    353
    354            // Terminates method normally.
    355            if (inst instanceof ReturnInstruction) {
    356                return empty;
    357            }
    358
    359            // Terminates method abnormally, because JustIce mandates
    360            // subroutines not to be protected by exception handlers.
    361            if (inst instanceof ATHROW) {
    362                return empty;
    363            }
    364
    365            // See method comment.
    366            if (inst instanceof JsrInstruction) {
    367                single[0] = ((JsrInstruction) inst).getTarget();
    368                return single;
    369            }
    370
    371            if (inst instanceof GotoInstruction) {
    372                single[0] = ((GotoInstruction) inst).getTarget();
    373                return single;
    374            }
    375
    376            if (inst instanceof BranchInstruction) {
    377                if (inst instanceof Select) {
    378                    // BCEL's getTargets() returns only the non-default targets,
    379                    // thanks to Eli Tilevich for reporting.
    380                    final InstructionHandle[] matchTargets = ((Select) inst).getTargets();
    381                    final InstructionHandle[] ret = new InstructionHandle[matchTargets.length+1];
    382                    ret[0] = ((Select) inst).getTarget();
    383                    System.arraycopy(matchTargets, 0, ret, 1, matchTargets.length);
    384                    return ret;
    385                }
    386                final InstructionHandle[] pair = new InstructionHandle[2];
    387                pair[0] = getInstruction().getNext();
    388                pair[1] = ((BranchInstruction) inst).getTarget();
    389                return pair;
    390            }
    391
    392            // default case: Fall through.
    393            single[0] = getInstruction().getNext();
    394            return single;
    395        }
    396
    397    } // End Inner InstructionContextImpl Class.
    398
    399    ///** The MethodGen object we're working on. */
    400    //private final MethodGen method_gen;
    401
    402    /** The Subroutines object for the method whose control flow is represented by this ControlFlowGraph. */
    403    private final Subroutines subroutines;
    404
    405    /** The ExceptionHandlers object for the method whose control flow is represented by this ControlFlowGraph. */
    406    private final ExceptionHandlers exceptionhandlers;
    407
    408    /** All InstructionContext instances of this ControlFlowGraph. */
    409    private final Map<InstructionHandle, InstructionContext> instructionContexts = new HashMap<>();
    410
    411    /**
    412     * A Control Flow Graph; with additional JustIce checks
    413     * @param  method_gen the method generator instance
    414     */
    415    public ControlFlowGraph(final MethodGen method_gen) {
    416        this(method_gen, true);
    417    }
    418
    419    /**
    420     * A Control Flow Graph.
    421     * @param  method_gen the method generator instance
    422     * @param enableJustIceCheck if true, additional JustIce checks are performed
    423     * @since 6.0
    424     */
    425    public ControlFlowGraph(final MethodGen method_gen, final boolean enableJustIceCheck) {
    426        subroutines = new Subroutines(method_gen, enableJustIceCheck);
    427        exceptionhandlers = new ExceptionHandlers(method_gen);
    428
    429        final InstructionHandle[] instructionhandles = method_gen.getInstructionList().getInstructionHandles();
    430        for (final InstructionHandle instructionhandle : instructionhandles) {
    431            instructionContexts.put(instructionhandle, new InstructionContextImpl(instructionhandle));
    432        }
    433
    434        //this.method_gen = method_gen;
    435    }
    436
    437    /**
    438     * Returns the InstructionContext of a given instruction.
    439     */
    440    public InstructionContext contextOf(final InstructionHandle inst) {
    441        final InstructionContext ic = instructionContexts.get(inst);
    442        if (ic == null) {
    443            throw new AssertionViolatedException("InstructionContext requested for an InstructionHandle that's not known!");
    444        }
    445        return ic;
    446    }
    447
    448    /**
    449     * Returns the InstructionContext[] of a given InstructionHandle[],
    450     * in a naturally ordered manner.
    451     */
    452    public InstructionContext[] contextsOf(final InstructionHandle[] insts) {
    453        final InstructionContext[] ret = new InstructionContext[insts.length];
    454        for (int i=0; i<insts.length; i++) {
    455            ret[i] = contextOf(insts[i]);
    456        }
    457        return ret;
    458    }
    459
    460    /**
    461     * Returns an InstructionContext[] with all the InstructionContext instances
    462     * for the method whose control flow is represented by this ControlFlowGraph
    463     * <B>(NOT ORDERED!)</B>.
    464     */
    465    public InstructionContext[] getInstructionContexts() {
    466        final InstructionContext[] ret = new InstructionContext[instructionContexts.values().size()];
    467        return instructionContexts.values().toArray(ret);
    468    }
    469
    470    /**
    471     * Returns true, if and only if the said instruction is not reachable; that means,
    472     * if it is not part of this ControlFlowGraph.
    473     */
    474    public boolean isDead(final InstructionHandle i) {
    475        return subroutines.subroutineOf(i) == null;
    476    }
    477}