ExceptionalUnitGraph


1   /* Soot - a J*va Optimization Framework
2    * Copyright (C) 1999 Patrice Pominville, Raja Vallee-Rai
3    *
4    * This library is free software; you can redistribute it and/or
5    * modify it under the terms of the GNU Lesser General Public
6    * License as published by the Free Software Foundation; either
7    * version 2.1 of the License, or (at your option) any later version.
8    *
9    * This library is distributed in the hope that it will be useful,
10   * but WITHOUT ANY WARRANTY; without even the implied warranty of
11   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12   * Lesser General Public License for more details.
13   *
14   * You should have received a copy of the GNU Lesser General Public
15   * License along with this library; if not, write to the
16   * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17   * Boston, MA 02111-1307, USA.
18   */
19  
20  /*
21   * Modified by the Sable Research Group and others 1997-2004.  
22   * See the 'credits' file distributed with Soot for the complete list of
23   * contributors.  (Soot is distributed at http://www.sable.mcgill.ca/soot)
24   */
25  
26  
27   
28  
29  
30  
31  package soot.toolkits.graph;
32  
33  import soot.*;
34  import soot.util.*;
35  import java.util.*;
36  import soot.options.Options;
37  import soot.toolkits.exceptions.ThrowAnalysis;
38  import soot.toolkits.exceptions.UnitThrowAnalysis;
39  import soot.toolkits.exceptions.ThrowableSet;
40  import soot.baf.Inst;
41  import soot.baf.NewInst;
42  import soot.baf.StaticPutInst;
43  import soot.baf.StaticGetInst;
44  import soot.baf.ThrowInst;
45  import soot.jimple.Stmt;
46  import soot.jimple.ThrowStmt;
47  import soot.jimple.StaticFieldRef;
48  import soot.jimple.InvokeExpr;
49  import soot.jimple.NewExpr;
50  
51  
52  /**
53   *  <p>Represents a control flow graph for a {@link Body} instance
54   *  where the nodes are {@link Unit} instances, and where control flow
55   *  associated with exceptions is taken into account.</p>
56   *
57   *  <p>To describe precisely the circumstances under which exceptional
58   *  edges are added to the graph, we need to distinguish the
59   *  exceptions thrown explicitly by a <code>throw</code> instruction
60   *  from the exceptions which are thrown implicitly by the VM to
61   *  signal an error it encounters in the course of executing
62   *  an instruction, which need not be a <code>throw</code>.</p>
63   *  
64   *  <p>For every {@link ThrowInst} or {@link ThrowStmt}
65   *  <code>Unit</code> which may explicitly throw an exception that
66   *  would be caught by a {@link Trap} in the <code>Body</code>, there
67   *  will be an edge from the <code>throw</code> <code>Unit</code> to
68   *  the <code>Trap</code> handler's first <code>Unit</code>.</p>
69   *
70   *  <p>For every <code>Unit</code> which may implicitly throw an
71   *  exception that could be caught by a <code>Trap</code> in the
72   *  <code>Body</code>, there will be an edge from each of the
73   *  excepting <code>Unit</code>'s predecessors to the
74   *  <code>Trap</code> handler's first <code>Unit</code> (since any of
75   *  those predecessors may have been the last <code>Unit</code> to
76   *  complete execution before the handler starts execution). If the
77   *  excepting <code>Unit</code> might have the side effect of changing
78   *  some field, then there will definitely be an edge from the excepting
79   *  <code>Unit</code> itself to its handlers, since the side effect
80   *  might occur before the exception is raised. If the excepting
81   *  <code>Unit</code> has no side effects, then parameters passed to
82   *  the <code>ExceptionalUnitGraph</code> constructor determine
83   *  whether or not there is an edge from the excepting
84   *  <code>Unit</code> itself to the handler <code>Unit</code>.</p>
85   */
86  public class ExceptionalUnitGraph extends UnitGraph implements ExceptionalGraph
87  {
88      protected Map unitToUnexceptionalSuccs; // If there are no Traps within
89      protected Map unitToUnexceptionalPreds; // the method, these will be the
90                          // same maps as unitToSuccs and
91                          // unitToPreds.
92  
93      protected Map unitToExceptionalSuccs;
94      protected Map unitToExceptionalPreds;
95      protected Map unitToExceptionDests;
96  
97      protected ThrowAnalysis throwAnalysis; // Cached reference to the
98                         // analysis used to generate this
99                         // graph, for generating responses
100                        // to getExceptionDests() on the
101                        // fly for nodes from which all
102                        // exceptions escape the method.
103 
104 
105     /**
106      *  Constructs the graph for a given Body instance, using the
107      *  <code>ThrowAnalysis</code> and <code>omitExceptingUnitEdges</code>
108      *  value that are passed as parameters.
109      *
110      *  @param body the <code>Body</code> from which to build a graph.
111      *
112      *  @param throwAnalysis the source of information about the exceptions
113      *                       which each {@link Unit} may throw.
114      *
115      *  @param omitExceptingUnitEdges indicates whether the CFG should
116      *               omit edges to a handler from trapped
117      *               <code>Unit</code>s which may implicitly throw an
118      *               exception which the handler catches but
119      *               which have no potential side effects.
120      *               The CFG will contain edges to the handler
121      *               from all predecessors of 
122      *               <code>Unit</code>s which may implicitly throw
123      *               a caught exception regardless of the setting for
124      *               this parameter. If this parameter is
125      *               <code>false</code>, there will also be
126      *               edges to the handler from all the
127      *               potentially excepting <code>Unit</code>s
128      *               themselves. If this parameter is
129      *               <code>true</code>, there will be edges to
130      *               the handler from the excepting
131      *               <code>Unit</code>s themselves only if they
132      *               have potential side effects (or if they 
133      *               are themselves the predecessors of other
134      *               potentially excepting <code>Unit</code>s).
135      *               A setting of <code>true</code> produces
136      *               CFGs which allow for more precise
137      *               analyses, since a <code>Unit</code> without
138      *               side effects has no effect on the
139      *               computational state when it throws an
140      *               exception.  Use settings of
141      *               <code>false</code> for compatibility with
142      *               more conservative analyses, or to cater
143      *               to conservative bytecode verifiers.
144      */
145     public ExceptionalUnitGraph(Body body, ThrowAnalysis throwAnalysis,
146                 boolean omitExceptingUnitEdges) {
147     super(body);
148     initialize(throwAnalysis, omitExceptingUnitEdges);
149     }
150 
151 
152     /**
153      *  Constructs the graph from a given Body instance using the
154      *  passed {@link ThrowAnalysis} and a default value, provided by
155      *  the {@link Options} class, for the
156      *  <code>omitExceptingUnitEdges</code> parameter.
157      *
158      *  @param body the {@link Body} from which to build a graph.
159      *
160      *  @param throwAnalysis the source of information about the exceptions
161      *                       which each {@link Unit} may throw.
162      *
163      */
164     public ExceptionalUnitGraph(Body body, ThrowAnalysis throwAnalysis) {
165     this(body, throwAnalysis, Options.v().omit_excepting_unit_edges());
166     }
167 
168 
169     /**
170      *  Constructs the graph from a given Body instance, using the
171      *  {@link Scene}'s default {@link ThrowAnalysis} to estimate the
172      *  set of exceptions that each {@link Unit} might throw and a
173      *  default value, provided by the {@link Options} class, for the
174      *  <code>omitExceptingUnitEdges</code> parameter.
175      *
176      *  @param body the <code>Body</code> from which to build a graph.
177      *
178      */
179     public ExceptionalUnitGraph(Body body) {
180     this(body, Scene.v().getDefaultThrowAnalysis(),
181          Options.v().omit_excepting_unit_edges());
182     }
183 
184 
185     /**
186      *  <p>Allocates an <code>ExceptionalUnitGraph</code> object
187      *  without initializing it.  This &ldquo;partial
188      *  constructor&rdquo; is provided for the benefit of subclasses
189      *  whose constructors need to perform some subclass-specific
190      *  processing before actually creating the graph edges (because,
191      *  for example, the subclass overrides a utility method like
192      *  {@link #buildExceptionDests(ThrowAnalysis)} or {@link
193      *  #buildExceptionalEdges(ThrowAnalysis, Map, Map, Map, boolean)}
194      *  with a replacement method that depends on additional
195      *  parameters passed to the subclass's constructor).  The
196      *  subclass constructor is responsible for calling {@link
197      *  #initialize(ThrowAnalysis, boolean)}, or otherwise performing
198      *  the initialization required to implement
199      *  <code>ExceptionalUnitGraph</code>'s interface.</p>
200      *
201      *  <p>Clients who opt to extend <code>ExceptionalUnitGraph</code>
202      *  should be warned that the class has not been carefully
203      *  designed for inheritance; code that uses the
204      *  <code>protected</code> members of this class may need to be
205      *  rewritten for each new Soot release.</p>
206      *
207      *  @param body the <code>Body</code> from which to build a graph.
208      *
209      *  @param ignoredBogusParameter a meaningless placeholder, which exists
210      *                           solely to distinguish this
211      *                           constructor from the public
212      *                           {@link #ExceptionalUnitGraph(Body)}
213      *                           constructor.
214      */
215     protected ExceptionalUnitGraph(Body body, boolean ignoredBogusParameter) {
216     super(body);
217     }
218 
219 
220     /**
221      *  Performs the real work of constructing an
222      *  <code>ExceptionalUnitGraph</code>, factored out of the
223      *  constructors so that subclasses have the option to delay
224      *  creating the graph's edges until after they have performed
225      *  some subclass-specific initialization.
226      *
227      *  @param throwAnalysis the source of information about the exceptions
228      *                       which each {@link Unit} may throw.
229      *
230      *  @param omitExceptingUnitEdges indicates whether the CFG should
231      *               omit edges to a handler from trapped
232      *               <code>Unit</code>s which may throw an
233      *               exception which the handler catches but
234      *               which have no potential side effects.
235      */
236     protected void initialize(ThrowAnalysis throwAnalysis, 
237                   boolean omitExceptingUnitEdges) {
238     int size = unitChain.size();
239     Set trapsThatAreHeads = Collections.EMPTY_SET;
240         
241         if(Options.v().time())
242             Timers.v().graphTimer.start();
243         
244     unitToUnexceptionalSuccs = new HashMap(size * 2 + 1, 0.7f);
245     unitToUnexceptionalPreds = new HashMap(size * 2 + 1, 0.7f);
246     buildUnexceptionalEdges(unitToUnexceptionalSuccs, 
247                 unitToUnexceptionalPreds);
248     makeMappedListsUnmodifiable(unitToUnexceptionalSuccs);
249     makeMappedListsUnmodifiable(unitToUnexceptionalPreds);
250     this.throwAnalysis = throwAnalysis;
251 
252     if (body.getTraps().size() == 0) {
253         // No handlers, so all exceptional control flow exits the
254         // method.
255             unitToExceptionDests = Collections.EMPTY_MAP;
256         unitToExceptionalSuccs = Collections.EMPTY_MAP;
257         unitToExceptionalPreds = Collections.EMPTY_MAP;
258         unitToSuccs = unitToUnexceptionalSuccs;
259         unitToPreds = unitToUnexceptionalPreds;
260 
261     } else {
262         unitToExceptionDests = buildExceptionDests(throwAnalysis);
263         unitToExceptionalSuccs = 
264         new HashMap(unitToExceptionDests.size() * 2 + 1, 0.7f);
265         unitToExceptionalPreds = 
266         new HashMap(body.getTraps().size() * 2 + 1, 0.7f);
267         trapsThatAreHeads = buildExceptionalEdges(throwAnalysis,
268                               unitToExceptionDests,
269                               unitToExceptionalSuccs, 
270                               unitToExceptionalPreds,
271                               omitExceptingUnitEdges);
272         makeMappedListsUnmodifiable(unitToExceptionalSuccs);
273         makeMappedListsUnmodifiable(unitToExceptionalPreds);
274 
275         // We'll need separate maps for the combined 
276         // exceptional and unexceptional edges:
277         unitToSuccs = combineMapValues(unitToUnexceptionalSuccs, 
278                        unitToExceptionalSuccs);
279         unitToPreds = combineMapValues(unitToUnexceptionalPreds, 
280                        unitToExceptionalPreds);
281     }
282 
283     buildHeadsAndTails(trapsThatAreHeads);
284 
285         if(Options.v().time())
286             Timers.v().graphTimer.end();        
287 
288     soot.util.PhaseDumper.v().dumpGraph(this);
289     }
290 
291 
292     /**
293      * <p>Utility method used in the construction of 
294      * {@link soot.toolkits.graph.UnitGraph UnitGraph}
295      * variants which include exceptional control flow. It determines
296      * which {@link Unit}s may throw exceptions that would be caught
297      * by {@link Trap}s within the method.</p>
298      *
299      * @param throwAnalysis The source of information about which
300      *              exceptions each <code>Unit</code> may throw.
301      *
302      * @return <code>null</code> if no <code>Unit</code>s in the method throw
303      *         any exceptions caught within the method. Otherwise, a
304      *         {@link Map} from <code>Unit</code>s to {@link
305      *         Collection}s of {@link ExceptionDest}s. 
306      *
307      *         <p>The returned map has an idiosyncracy which is hidden
308      *         from most client code, but which is exposed to
309      *         subclasses extending <code>ExceptionalUnitGraph</code>.
310      *         If a <code>Unit</code> throws one or more exceptions
311      *         which are caught within the method, it will be mapped
312      *         to a <code>Collection</code> of
313      *         <code>ExceptionDest</code>s describing the sets of
314      *         exceptions that the <code>Unit</code> might throw to
315      *         each {@link Trap}. But if all of a <code>Unit</code>'s
316      *         exceptions escape the method, it will be mapped to
317      *         <code>null</code, rather than to a
318      *         <code>Collection</code> containing a single
319      *         <code>ExceptionDest</code> with a <code>null</code>
320      *         trap. (The special case for <code>Unit</code>s with
321      *         no caught exceptions allows
322      *         <code>buildExceptionDests()</code> to ignore completely
323      *         <code>Unit</code>s which are outside the scope of all
324      *         <code>Trap</code>s.)</p>
325      */
326     protected Map buildExceptionDests(ThrowAnalysis throwAnalysis) {
327     Chain units = body.getUnits();
328     Map unitToUncaughtThrowables = new HashMap(units.size());
329     Map result = null;
330     FastHierarchy hier = Scene.v().getOrMakeFastHierarchy();
331 
332     // Record the caught exceptions.
333     for (Iterator trapIt = body.getTraps().iterator(); trapIt.hasNext(); ) {
334         Trap trap = (Trap) trapIt.next();
335         RefType catcher = trap.getException().getType();
336         for (Iterator unitIt = units.iterator(trap.getBeginUnit(), 
337                           units.getPredOf(trap.getEndUnit()));
338          unitIt.hasNext(); ) {
339         Unit unit = (Unit) unitIt.next();
340         ThrowableSet thrownSet = (ThrowableSet) unitToUncaughtThrowables.get(unit);
341         if (thrownSet == null) {
342             thrownSet = throwAnalysis.mightThrow(unit);
343         }
344         ThrowableSet.Pair catchableAs = thrownSet.whichCatchableAs(catcher);
345         if (catchableAs.getCaught() != ThrowableSet.Manager.v().EMPTY) {
346             result = addDestToMap(result, unit, trap, catchableAs.getCaught());
347             unitToUncaughtThrowables.put(unit, catchableAs.getUncaught());
348         } else {
349             // An assertion check:
350             if (thrownSet != catchableAs.getUncaught()) {
351             throw new IllegalStateException  ("ExceptionalUnitGraph.buildExceptionDests(): catchableAs.caught == EMPTY, but catchableAs.uncaught != thrownSet" 
352                             + System.getProperty("line.separator") + body.getMethod().getSubSignature() + " Unit: " + unit.toString()
353                             + System.getProperty("line.separator") + " catchableAs.getUncaught() == " + catchableAs.getUncaught().toString() 
354                             + System.getProperty("line.separator") + " thrownSet == " + thrownSet.toString());
355             }
356         }
357         }
358     }
359 
360     // Record the escaping exceptions for units that have some
361     // caught exceptions (addDestToMap() screens any units which
362     // had no exceptions caught, despite being in the scope of a trap).
363     for (Iterator entryIt = unitToUncaughtThrowables.entrySet().iterator();
364          entryIt.hasNext(); ) {
365         Map.Entry entry = (Map.Entry) entryIt.next();
366         Unit unit = (Unit) entry.getKey();
367         ThrowableSet escaping = (ThrowableSet) entry.getValue();
368         if (escaping != ThrowableSet.Manager.v().EMPTY) {
369         result = addDestToMap(result, unit, null, escaping);
370         }
371     }
372     if (result == null) {
373         result = Collections.EMPTY_MAP;
374     }
375     return result;
376     }
377 
378 
379     /** 
380      * A utility method for recording the exceptions that a
381      * <code>Unit</code> throws to a particular <code>Trap</code>.
382      * Note that this method relies on the fact that the call to add
383      * escaping exceptions for a <code>Unit</code> will always follow
384      * all calls for its caught exceptions.
385      *
386      * @param map A <code>Map</code> from <code>Unit</code>s to
387      *            <code>Collection</code>s of <code>ExceptionDest</code>s.
388      *        <code>null</code> if no exceptions have been recorded yet.
389      *
390      * @param u The <code>Unit</code> throwing the exceptions.
391      *
392      * @param t The <code>Trap</code> which catches the exceptions, or 
393      *          <code>null</code> if the exceptions escape the method.
394      *
395      * @param caught The set of exception types thrown by <code>u</code> which
396      *               are caught by <code>t</code>.  
397      *
398      * @return a <code>Map</code> which whose contents are equivalent to the
399      *         input <code>map</code>, plus the information that <code>u</code>
400      *         throws <code>caught</code> to <code>t</code>.
401      */
402     private Map addDestToMap(Map map, Unit u, Trap t, ThrowableSet caught) {
403     Collection dests = (map == null ? null : (Collection) map.get(u));
404     if (dests == null) {
405         if (t == null) {
406         // All exceptions from u escape, so don't record any.
407         return map;
408         } else {
409         if (map == null) {
410              map = new HashMap(unitChain.size() * 2 + 1);
411         }
412         dests = new ArrayList(3);
413         map.put(u, dests);
414         }
415     }
416     dests.add(new ExceptionDest(t, caught));
417     return map;
418     }
419 
420 
421     /**
422      * Method to compute the edges corresponding to exceptional
423      * control flow.
424      *
425      * @param throwAnalysis the source of information about the exceptions
426      *                     which each {@link Unit} may throw.
427      *
428      * @param unitToDests A <code>Map</code> from {@link Unit}s to 
429      *                    {@link Collection}s of {@link
430      *                    ExceptionalUnitGraph.ExceptionDest
431      *                    ExceptionDest}s which represent the handlers
432      *                    that might catch exceptions thrown by the
433      *                    <code>Unit</code>. This is an ``in
434      *                    parameter''.
435      *
436      * @param unitToSuccs A <code>Map</code> from <code>Unit</code>s to 
437      *                    {@link List}s of <code>Unit</code>s. This is
438      *                    an ``out parameter'';
439      *                    <code>buildExceptionalEdges</code> will add
440      *                    a mapping from every <code>Unit</code> in
441      *                    the body that may throw an exception that
442      *                    could be caught by a {@link Trap} in the
443      *                    body to a list of its exceptional
444      *                    successors.
445      *
446      * @param unitToPreds A <code>Map</code> from <code>Unit</code>s to 
447      *                    <code>List</code>s of
448      *                    <code>Unit</code>s. This is an ``out
449      *                    parameter'';
450      *                    <code>buildExceptionalEdges</code> will add
451      *                    a mapping from each handler unit that may
452      *                    catch an exception to the list of
453      *                    <code>Unit</code>s whose exceptions it may
454      *                    catch.
455      * @param omitExceptingUnitEdges Indicates whether to omit
456      *            exceptional edges from excepting units which
457      *            lack side effects
458      *
459      * @return a {@link Set} of trap <code>Unit</code>s that might catch 
460      *         exceptions thrown by the first <code>Unit</code> in the
461      *         {@link Body} associated with the graph being
462      *         constructed.  Such trap <code>Unit</code>s may need to
463      *         be added to the list of heads (depending on your
464      *         definition of heads), since they can be the first
465      *         <code>Unit</code> in the <code>Body</code> which
466      *         actually completes execution.
467      */
468     protected Set buildExceptionalEdges(ThrowAnalysis throwAnalysis,
469                     Map unitToDests, 
470                     Map unitToSuccs, Map unitToPreds,
471                     boolean omitExceptingUnitEdges) {
472     Set trapsThatAreHeads = new ArraySet();
473     Unit entryPoint = (Unit) unitChain.getFirst();
474 
475     for (Iterator it = unitToDests.entrySet().iterator();
476          it.hasNext(); ) {
477         Map.Entry entry = (Map.Entry) it.next();
478         Unit thrower = (Unit) entry.getKey();
479         List throwersPreds = getUnexceptionalPredsOf(thrower);
480         Collection dests = (Collection) entry.getValue();
481 
482         // We need to recognize:
483         // - caught exceptions for which we must add edges from the 
484         //   thrower's predecessors to the catcher:
485         //     - all exceptions of non-throw instructions;
486         //     - implicit exceptions of throw instructions.
487         //
488         // - caught exceptions where we must add edges from the 
489         //   thrower itself to the catcher:
490         //     - any exception of non-throw instructions if
491         //       omitExceptingUnitEdges is not set.
492         //     - any exception of non-throw instructions with side effects.
493         //     - explicit exceptions of throw instructions
494         //     - implicit exceptions of throw instructions if 
495         //       omitExceptingUnitEdges is not set.
496         //     - implicit exceptions of throw instructions with possible
497         //       side effects (this is only possible for the grimp
498         //       IR, where the throw's argument may be an
499         //       expression---probably a NewInvokeExpr---which
500         //       might have executed partially before the
501         //       exception arose).
502         //
503         // Note that a throw instruction may be capable of throwing a given
504         // Throwable type both implicitly and explicitly.
505         //
506         // We track these situations using predThrowables and
507         // selfThrowables.  Essentially predThrowables is the set
508         // of Throwable types to whose catchers there should be
509         // edges from predecessors of the thrower, while
510         // selfThrowables is the set of Throwable types to whose
511         // catchers there should be edges from the thrower itself,
512         // but we we take some short cuts to avoid calling
513         // ThrowableSet.catchableAs() when we can avoid it.
514 
515         boolean alwaysAddSelfEdges = ((! omitExceptingUnitEdges) || 
516                       mightHaveSideEffects(thrower));
517         ThrowableSet predThrowables = null;
518         ThrowableSet selfThrowables = null;
519         if (thrower instanceof ThrowInst) {
520         ThrowInst throwInst = (ThrowInst) thrower;
521         predThrowables = throwAnalysis.mightThrowImplicitly(throwInst);
522         selfThrowables = throwAnalysis.mightThrowExplicitly(throwInst);
523         } else if (thrower instanceof ThrowStmt) {
524         ThrowStmt throwStmt = (ThrowStmt) thrower;
525         predThrowables = throwAnalysis.mightThrowImplicitly(throwStmt);
526         selfThrowables = throwAnalysis.mightThrowExplicitly(throwStmt);
527         }
528 
529         for (Iterator destIt = dests.iterator(); destIt.hasNext(); ) {
530         ExceptionDest dest = (ExceptionDest) destIt.next();
531         if (dest.getTrap() != null) {
532             Unit catcher = dest.getTrap().getHandlerUnit();
533             RefType trapsType = dest.getTrap().getException().getType();
534             if (predThrowables == null ||
535             predThrowables.catchableAs(trapsType)) {
536             // Add edges from the thrower's predecessors to the catcher.
537             if (thrower == entryPoint) {
538                 trapsThatAreHeads.add(catcher);
539             }
540             for (Iterator p = throwersPreds.iterator(); p.hasNext(); ) {
541                 Unit pred = (Unit) p.next();
542                 addEdge(unitToSuccs, unitToPreds, pred, catcher);
543             }
544             }
545             if (alwaysAddSelfEdges ||
546             (selfThrowables != null &&
547              selfThrowables.catchableAs(trapsType))) {
548             addEdge(unitToSuccs, unitToPreds, thrower, catcher);
549             }
550         }
551         }
552     }
553             
554     // Now we have to worry about transitive exceptional
555     // edges, when a handler might itself throw an exception
556     // that is caught within the method.  For that we need a
557     // worklist containing CFG edges that lead to such a handler.
558     class CFGEdge {
559         Unit head;      // If null, represents an edge to the handler
560                 // from the fictitious "predecessor" of the 
561                 // very first unit in the chain. I.e., tail
562                 // is a handler which might be reached as a
563                 // result of an exception thrown by the
564                 // first Unit in the Body.
565         Unit tail;
566 
567         CFGEdge(Unit head, Unit tail) {
568         if (tail == null)
569             throw new RuntimeException  ("invalid CFGEdge(" 
570                            + head.toString() + ',' 
571                            + tail.toString() + ')');
572         this.head = head;
573         this.tail = tail;
574         }
575 
576         public boolean equals(Object   rhs) {
577         if (rhs == this) {
578             return true;
579         }
580         if (! (rhs instanceof CFGEdge)) {
581             return false;
582         }
583         CFGEdge rhsEdge = (CFGEdge) rhs;
584         return ((this.head == rhsEdge.head) && 
585             (this.tail == rhsEdge.tail));
586         }
587 
588         public int hashCode() {
589         // Following Joshua Bloch's recipe in "Effective Java", Item 8:
590         int result = 17;
591         result = 37 * result + this.head.hashCode();
592         result = 37 * result + this.tail.hashCode();
593         return result;
594         }
595     }
596 
597     LinkedList workList = new LinkedList();
598 
599     for (Iterator trapIt = body.getTraps().iterator(); trapIt.hasNext(); ) {
600         Trap trap = (Trap) trapIt.next();
601         Unit handlerStart = trap.getHandlerUnit();
602         if (mightThrowToIntraproceduralCatcher(handlerStart)) {
603         List handlerPreds = getUnexceptionalPredsOf(handlerStart);
604         for (Iterator it = handlerPreds.iterator(); it.hasNext(); ) {
605             Unit pred = (Unit) it.next();
606             workList.addLast(new CFGEdge(pred, handlerStart));
607         }
608         handlerPreds = getExceptionalPredsOf(handlerStart);
609         for (Iterator it = handlerPreds.iterator(); it.hasNext(); ) {
610             Unit pred = (Unit) it.next();
611             workList.addLast(new CFGEdge(pred, handlerStart));
612         }
613         if (trapsThatAreHeads.contains(handlerStart)) {
614             workList.addLast(new CFGEdge(null, handlerStart));
615         }
616         }
617     }
618 
619     // Now for every CFG edge that leads to a handler that may
620     // itself throw an exception catchable within the method, add
621     // edges from the head of that edge to the unit that catches
622     // the handler's exception.
623     while (workList.size() > 0) {
624         CFGEdge edgeToThrower = (CFGEdge) workList.removeFirst();
625         Unit pred = edgeToThrower.head;
626         Unit thrower = edgeToThrower.tail;
627         Collection throwerDests = getExceptionDests(thrower);
628         for (Iterator i = throwerDests.iterator(); i.hasNext(); ) {
629         ExceptionDest dest = (ExceptionDest) i.next();
630         if (dest.getTrap() != null) {
631             Unit handlerStart = dest.getTrap().getHandlerUnit();
632             boolean edgeAdded = false;
633             if (pred == null) {
634             if (! trapsThatAreHeads.contains(handlerStart)) {
635                 trapsThatAreHeads.add(handlerStart);
636                 edgeAdded = true;
637             }
638             } else {
639             if (! getExceptionalSuccsOf(pred).contains(handlerStart)) {
640                 addEdge(unitToSuccs, unitToPreds, pred, handlerStart);
641                 edgeAdded = true;
642             }
643             }
644             if (edgeAdded && 
645             mightThrowToIntraproceduralCatcher(handlerStart)) {
646             workList.addLast(new CFGEdge(pred, handlerStart));
647             }
648         }
649         }
650     }
651     return trapsThatAreHeads;
652     }
653 
654 
655     /**
656      * <p>Utility method for checking if a {@link Unit} might have side
657      * effects.  It simply returns true for any unit which invokes a
658      * method directly or which might invoke static initializers
659      * indirectly (by creating a new object or by refering to a static
660      * field; see sections 2.17.4, 2.17.5, and 5.5 of the Java Virtual
661      * Machine Specification).</p>
662      *
663      * <code>mightHaveSideEffects()</code> is declared package-private
664      * so that it is available to unit tests that are part of this
665      * package.
666      *
667      * @param u     The unit whose potential for side effects is to be checked.
668      *
669      * @return whether or not <code>u</code> has the potential for side effects.
670      */
671     static boolean mightHaveSideEffects(Unit u) {
672     if (u instanceof Inst) {
673         Inst i = (Inst) u;
674         return (i.containsInvokeExpr() || 
675             (i instanceof StaticPutInst) || 
676             (i instanceof StaticGetInst) || 
677             (i instanceof NewInst));
678     } else if (u instanceof Stmt) {
679         for (Iterator it = u.getUseBoxes().iterator(); it.hasNext(); ) {
680         Value v = ((ValueBox)(it.next())).getValue();
681         if ((v instanceof StaticFieldRef) || 
682             (v instanceof InvokeExpr) ||
683             (v instanceof NewExpr)) {
684             return true;
685         }
686         }
687     }
688     return false;
689     }
690 
691 
692     /**
693      * Utility method for checking if a Unit might throw an exception which
694      * may be caught by a {@link Trap} within this method.  
695      *
696      * @param u     The unit for whose exceptions are to be checked
697      *
698      * @return whether or not <code>u</code> may throw an exception which may be
699      *              caught by a <code>Trap</code> in this method,
700      */
701     private boolean mightThrowToIntraproceduralCatcher(Unit u) {
702     Collection dests = getExceptionDests(u);
703     for (Iterator i = dests.iterator(); i.hasNext(); ) {
704         ExceptionDest dest = (ExceptionDest) i.next();
705         if (dest.getTrap() != null) {
706         return true;
707         }
708     }
709     return false;
710     }
711 
712 
713     /**
714      * <p>A placeholder that overrides {@link UnitGraph#buildHeadsAndTails()}
715      * with a method which always throws an exception. The placeholder serves
716      * to indicate that <code>ExceptionalUnitGraph</code> does not use
717      * <code>buildHeadsAndTails()</code>, and to document the conditions under 
718      * which <code>ExceptionalUnitGraph considers a node to be a head or 
719      * tail.</p>
720      *
721      * <p><code>ExceptionalUnitGraph</code> defines the graph's set of
722      * heads to include the first {@link Unit} in the graph's body,
723      * together with the first <code>Unit</code> in any exception
724      * handler which might catch an exception thrown by the first
725      * <code>Unit</code> in the body (because any of those
726      * <code>Unit</code>s might be the first to successfully complete
727      * execution). <code>ExceptionalUnitGraph</code> defines the
728      * graph's set of tails to include all <code>Unit</code>s which
729      * represent some variety of return bytecode or an
730      * <code>athrow</code> bytecode whose argument might escape the
731      * method.</p>
732      */
733     protected void buildHeadsAndTails() throws IllegalStateException   {
734     throw new IllegalStateException  ("ExceptionalUnitGraph uses buildHeadsAndTails(List) instead of buildHeadsAndTails()");
735     }
736 
737 
738     /**
739      * Utility method, to be called only after the unitToPreds and
740      * unitToSuccs maps have been built. It defines the graph's set of
741      * heads to include the first {@link Unit} in the graph's body,
742      * together with all the <code>Unit</code>s in
743      * <code>additionalHeads</code>.  It defines the graph's set of
744      * tails to include all <code>Unit</code>s which represent some
745      * sort of return bytecode or an <code>athrow</code> bytecode
746      * which may escape the method.
747      */
748     private void buildHeadsAndTails(Set additionalHeads) {
749     List headList = new ArrayList(additionalHeads.size() + 1);
750     headList.addAll(additionalHeads);
751     Unit entryPoint = (Unit) unitChain.getFirst();
752     if (! headList.contains(entryPoint)) {
753         headList.add(entryPoint);
754     }
755     
756     List tailList = new ArrayList();
757     for (Iterator it = unitChain.iterator(); it.hasNext(); ) {
758         Unit u = (Unit) it.next();
759         if (u instanceof soot.jimple.ReturnStmt ||
760         u instanceof soot.jimple.ReturnVoidStmt ||
761         u instanceof soot.baf.ReturnInst ||
762         u instanceof soot.baf.ReturnVoidInst) {
763         tailList.add(u);
764         } else if (u instanceof soot.jimple.ThrowStmt ||
765                u instanceof soot.baf.ThrowInst) {
766         Collection dests = getExceptionDests(u);
767         int escapeMethodCount = 0;
768         for (Iterator destIt = dests.iterator(); destIt.hasNext(); ) {
769             ExceptionDest dest = (ExceptionDest) destIt.next();
770             if (dest.getTrap() == null) {
771             escapeMethodCount++;
772             }
773         }
774         if (escapeMethodCount > 0) {
775             tailList.add(u);
776         }
777         }
778     }
779     tails = Collections.unmodifiableList(tailList);
780     heads = Collections.unmodifiableList(headList);
781     }
782 
783 
784     /**
785      * Returns a collection of 
786      * {@link ExceptionalUnitGraph.ExceptionDest ExceptionDest}
787      * objects which represent how exceptions thrown by a specified
788      * unit will be handled.
789      *
790      * @param u The unit for which to provide exception information.
791      *          (<code>u</code> must be a <code>Unit</code>, though the parameter is
792      *          declared as an <code>Object</code> to satisfy the interface of 
793      *          {@link soot.toolkits.graph.ExceptionalGraph ExceptionalGraph}.
794      *
795      * @return a collection of <code>ExceptionDest</code> objects describing
796      *         the traps, if any, which catch the exceptions
797      *         which may be thrown by <code>u</code>.
798      */
799     public Collection getExceptionDests(Object   u) {
800     Collection result = (Collection) unitToExceptionDests.get(u);
801     if (result == null) {
802         result = new LinkedList();
803         result.add(new ExceptionDest(null, throwAnalysis.mightThrow((Unit) u)));
804     }
805     return result;
806     }
807 
808     
809     public static class ExceptionDest implements ExceptionalGraph.ExceptionDest {
810     private Trap trap;
811     private ThrowableSet throwables;
812 
813     protected ExceptionDest(Trap trap, ThrowableSet throwables) {
814         this.trap = trap;
815         this.throwables = throwables;
816     }
817     
818     public Trap getTrap() {
819         return trap;
820     }
821 
822     public ThrowableSet getThrowables() {
823         return throwables;
824     }
825 
826     public Object   getHandlerNode() {
827         if (trap == null) {
828         return null;
829         } else {
830         return trap.getHandlerUnit();
831         }
832     }
833 
834     public String   toString() {
835         StringBuffer   buf = new StringBuffer  ();
836         buf.append(throwables.toString());
837         buf.append(" -> ");
838         if (trap == null) {
839         buf.append("(escapes)");
840         } else {
841         buf.append(trap.toString());
842         }
843         return buf.toString();
844     }
845     }
846 
847 
848     public List getUnexceptionalPredsOf(Object   u) {
849     if (!unitToUnexceptionalPreds.containsKey(u))
850         throw new RuntimeException  ("Invalid unit " + u);
851 
852     return (List) unitToUnexceptionalPreds.get(u);
853     }
854 
855 
856     public List getUnexceptionalSuccsOf(Object   u) {
857     if (!unitToUnexceptionalSuccs.containsKey(u))
858         throw new RuntimeException  ("Invalid unit " + u);
859 
860     return (List) unitToUnexceptionalSuccs.get(u);
861     }
862 
863 
864     public List getExceptionalPredsOf(Object    u) {
865     if (!unitToExceptionalPreds.containsKey(u)) {
866         return Collections.EMPTY_LIST;
867     } else {
868         return (List) unitToExceptionalPreds.get(u);
869     }
870     }
871 
872 
873     public List getExceptionalSuccsOf(Object   u) {
874     if (!unitToExceptionalSuccs.containsKey(u)) {
875         return Collections.EMPTY_LIST;
876     } else {
877         return (List) unitToExceptionalSuccs.get(u);
878     }
879     }
880 
881 
882     /**
883      * <p>Return the {@link ThrowAnalysis} used to construct this
884      * graph, if the graph contains no {@link Trap}s, or
885      * <code>null</code> if the graph does contain
886      * <code>Trap</code>s. A reference to the
887      * <code>ThrowAnalysis</code> is kept when there are no
888      * <code>Trap</code>s so that the graph can generate responses to
889      * {@link #getExceptionDests(Object)} on the fly, rather than precomputing
890      * information that may never be needed.</p>
891      *
892      * <p>This method is package-private because it exposes a detail
893      * of the implementation of <code>ExceptionalUnitGraph</code> so
894      * that the 
895      * {@link soot.toolkits.graph.ExceptionalBlockGraph ExceptionalBlockGraph}
896      * constructor can cache the same <code>ThrowAnalysis</code> for
897      * the same purpose.
898      *
899      * @return the {@link ThrowAnalysis} used to generate this graph if the
900      *         graph contains no {@link Trap}s, or <code>null</code> if the graph 
901      *         contains one or more {@link Trap}s.
902      */
903     ThrowAnalysis getThrowAnalysis() {
904     return throwAnalysis;
905     }
906 
907 
908     public String   toString() {
909         Iterator it = unitChain.iterator();
910         StringBuffer   buf = new StringBuffer  ();
911         while(it.hasNext()) {
912             Unit u = (Unit) it.next();
913             
914             buf.append("// preds: "+getPredsOf(u)+"\n");
915             buf.append("// unexceptional preds: "+getUnexceptionalPredsOf(u)+"\n");
916             buf.append("// exceptional preds: "+getExceptionalPredsOf(u)+"\n");
917             buf.append(u.toString() + '\n');
918         buf.append("// exception destinations: "+getExceptionDests(u)+"\n");
919             buf.append("// unexceptional succs: "+getUnexceptionalPredsOf(u)+"\n");
920             buf.append("// exceptional succs: "+getExceptionalPredsOf(u)+"\n");
921             buf.append("// succs "+getSuccsOf(u)+"\n");
922         }
923         
924         return buf.toString();
925     }
926 }
927
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags