View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   *  Unless required by applicable law or agreed to in writing, software
12   *  distributed under the License is distributed on an "AS IS" BASIS,
13   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   *  See the License for the specific language governing permissions and
15   *  limitations under the License.
16   *
17   */
18  package org.apache.bcel.verifier.structurals;
19  
20  
21  import java.util.ArrayList;
22  import java.util.HashMap;
23  import java.util.List;
24  import java.util.Map;
25  
26  import org.apache.bcel.generic.ATHROW;
27  import org.apache.bcel.generic.BranchInstruction;
28  import org.apache.bcel.generic.GotoInstruction;
29  import org.apache.bcel.generic.Instruction;
30  import org.apache.bcel.generic.InstructionHandle;
31  import org.apache.bcel.generic.JsrInstruction;
32  import org.apache.bcel.generic.MethodGen;
33  import org.apache.bcel.generic.RET;
34  import org.apache.bcel.generic.ReturnInstruction;
35  import org.apache.bcel.generic.Select;
36  import org.apache.bcel.verifier.exc.AssertionViolatedException;
37  import org.apache.bcel.verifier.exc.StructuralCodeConstraintException;
38  
39  /**
40   * This class represents a control flow graph of a method.
41   *
42   * @version $Id: ControlFlowGraph.html 1018313 2017-09-18 09:03:04Z britter $
43   */
44  public class ControlFlowGraph{
45  
46      /**
47       * Objects of this class represent a node in a ControlFlowGraph.
48       * These nodes are instructions, not basic blocks.
49       */
50      private class InstructionContextImpl implements InstructionContext{
51  
52          /**
53           * The TAG field is here for external temporary flagging, such
54           * as graph colouring.
55           *
56           * @see #getTag()
57           * @see #setTag(int)
58           */
59          private int TAG;
60  
61          /**
62           * The InstructionHandle this InstructionContext is wrapped around.
63           */
64          private final InstructionHandle instruction;
65  
66          /**
67           * The 'incoming' execution Frames.
68           */
69          private final Map<InstructionContext, Frame> inFrames;    // key: the last-executed JSR
70  
71          /**
72           * The 'outgoing' execution Frames.
73           */
74          private final Map<InstructionContext, Frame> outFrames; // key: the last-executed JSR
75  
76          /**
77           * The 'execution predecessors' - a list of type InstructionContext
78           * of those instances that have been execute()d before in that order.
79           */
80          private List<InstructionContext> executionPredecessors = null; // Type: InstructionContext
81  
82          /**
83           * Creates an InstructionHandleImpl object from an InstructionHandle.
84           * Creation of one per InstructionHandle suffices. Don't create more.
85           */
86          public InstructionContextImpl(final InstructionHandle inst) {
87              if (inst == null) {
88                  throw new AssertionViolatedException("Cannot instantiate InstructionContextImpl from NULL.");
89              }
90  
91              instruction = inst;
92              inFrames = new HashMap<>();
93              outFrames = new HashMap<>();
94          }
95  
96          /* Satisfies InstructionContext.getTag(). */
97          @Override
98          public int getTag() {
99              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 }