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.values().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}