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