ExceptionalBlockGraph


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  package soot.toolkits.graph;
28  
29  import java.util.*;
30  import soot.*;
31  import java.io.*;
32  import soot.toolkits.exceptions.ThrowAnalysis;
33  import soot.toolkits.exceptions.ThrowableSet;
34  
35  /**
36   *  <p>Represents a CFG where the nodes are {@link Block}s and the
37   *  edges are derived from control flow.  Control flow associated with
38   *  exceptions is taken into account: when a {@link Unit} may throw
39   *  an exception that is caught by a {@link Trap} within the
40   *  <code>Body</code>, the excepting <code>Unit</code> starts a new basic
41   *  block (<code>Unit</code>s do not start a new block when all the exceptions
42   *  they might throw would escape the method without being caught).
43   *  </p>
44   */
45  
46  public class ExceptionalBlockGraph extends BlockGraph implements ExceptionalGraph
47  {
48      // Maps for distinguishing exceptional and unexceptional control flow.
49      // We follow two conventions to save space (and runtime, if no client ever 
50      // asks for the exceptional information):  if the graph contains no
51      // exceptional edges (e.g. there are no traps in the method) we leave
52      // all these map references as NULL, while if an individual block has only 
53      // unexceptional successors or predecessors, it is not added to the 
54      // relevant map. When the access methods are asked about such blocks, 
55      // they return empty lists for the exceptional predecessors and successors,
56      // and the complete list of predecessors or successors for 
57      // the unexceptional predecessors and successors.
58      Map blockToExceptionalPreds;
59      Map blockToExceptionalSuccs;
60      Map blockToUnexceptionalPreds;
61      Map blockToUnexceptionalSuccs;
62      Map blockToExceptionDests;
63  
64      // When the graph has no traps (thus no exceptional CFG edges); we cache the
65      // throwAnalysis for generating ExceptionDests on demand.  If there
66      // are traps, throwAnalysis remains null.
67      ThrowAnalysis throwAnalysis ;
68  
69      /**
70       *   <p>Constructs an <code>ExceptionalBlockGraph</code> for the
71       *   blocks found by partitioning the the units of the provided
72       *   <code>Body</code> instance into basic blocks.</p>
73       *
74       *   <p>Note that this constructor builds an {@link
75       *   ExceptionalUnitGraph} internally when splitting <code>body</code>'s
76       *   {@link Unit}s into {@link Block}s.  Callers who already have
77       *   an <code>ExceptionalUnitGraph</code> to hand can use the constructor
78       *   taking an <code>ExceptionalUnitGraph</code> as a parameter, as a
79       *   minor optimization.
80       *
81       *   @param body    The underlying body we want to make a graph for.
82       */
83      public ExceptionalBlockGraph(Body body)
84      {
85          this(new ExceptionalUnitGraph(body));
86      }
87  
88  
89      /**
90       *   Constructs a graph for the blocks found by partitioning the
91       *   the {@link Unit}s in an {@link ExceptionalUnitGraph}.  
92       *
93       *   @param unitGraph The <code>ExceptionalUnitGraph</code> whose
94       *                    <code>Unit</code>s are to be split into blocks.
95       */
96      public ExceptionalBlockGraph(ExceptionalUnitGraph unitGraph)
97      {
98          super(unitGraph);
99  
100     soot.util.PhaseDumper.v().dumpGraph(this);
101     }
102 
103 
104     /**
105      * {@inheritDoc}
106      *
107      * This implementation calls the inherited implementation to split
108      * units into blocks, before adding the distinctions between
109      * exceptional and unexceptional control flow.
110      *
111      * @param {@inheritDoc}
112      *
113      * @return {@inheritDoc}
114      */
115 
116     protected Map buildBlocks(Set leaders, UnitGraph uncastUnitGraph) {
117     ExceptionalUnitGraph unitGraph = (ExceptionalUnitGraph) uncastUnitGraph;
118     Map unitToBlock = super.buildBlocks(leaders, unitGraph);
119 
120     if (unitGraph.getBody().getTraps().size() == 0) {
121         // All exceptions escape the method.  Cache the ThrowAnalysis
122         // to respond to getExceptionDests() on demand.
123         throwAnalysis = unitGraph.getThrowAnalysis();
124         if (throwAnalysis == null) {
125         throw new IllegalStateException  ("ExceptionalUnitGraph lacked a cached ThrowAnalysis for a Body with no Traps.");
126         }
127 
128     } else {
129         int initialMapSize = (mBlocks.size() * 2) / 3;
130         blockToUnexceptionalPreds = new HashMap(initialMapSize);
131         blockToUnexceptionalSuccs = new HashMap(initialMapSize);
132         blockToExceptionalPreds = new HashMap(initialMapSize);
133         blockToExceptionalSuccs = new HashMap(initialMapSize);
134 
135         for (Iterator blockIt = mBlocks.iterator(); blockIt.hasNext(); ) {
136         Block block = (Block) blockIt.next();
137 
138         Unit blockHead = block.getHead();
139         List exceptionalPredUnits = unitGraph.getExceptionalPredsOf(blockHead);
140         if (exceptionalPredUnits.size() != 0) {
141             List exceptionalPreds = mappedValues(exceptionalPredUnits,
142                              unitToBlock);
143             exceptionalPreds = Collections.unmodifiableList(exceptionalPreds);
144             blockToExceptionalPreds.put(block, exceptionalPreds);
145             List unexceptionalPredUnits = unitGraph.getUnexceptionalPredsOf(blockHead);
146             List unexceptionalPreds = null;
147             if (unexceptionalPredUnits.size() == 0) {
148             unexceptionalPreds = Collections.EMPTY_LIST;
149             } else {
150             unexceptionalPreds = mappedValues(unexceptionalPredUnits,
151                               unitToBlock);
152             unexceptionalPreds = Collections.unmodifiableList(unexceptionalPreds);
153             }
154             blockToUnexceptionalPreds.put(block, unexceptionalPreds);
155         }
156 
157         Unit blockTail = block.getTail();
158         List exceptionalSuccUnits = unitGraph.getExceptionalSuccsOf(blockTail);
159         if (exceptionalSuccUnits.size() != 0) {
160             List exceptionalSuccs = mappedValues(exceptionalSuccUnits,
161                              unitToBlock);
162             exceptionalSuccs = Collections.unmodifiableList(exceptionalSuccs);
163               blockToExceptionalSuccs.put(block, exceptionalSuccs);
164             List unexceptionalSuccUnits = unitGraph.getUnexceptionalSuccsOf(blockTail);
165             List unexceptionalSuccs = null;
166             if (unexceptionalSuccUnits.size() == 0) {
167             unexceptionalSuccs = Collections.EMPTY_LIST;
168             } else {
169             unexceptionalSuccs = mappedValues(unexceptionalSuccUnits,
170                               unitToBlock);
171             unexceptionalSuccs = Collections.unmodifiableList(unexceptionalSuccs);
172             }
173             blockToUnexceptionalSuccs.put(block,unexceptionalSuccs);
174         }
175         }
176         blockToExceptionDests = buildExceptionDests(unitGraph, unitToBlock);
177     }
178     return unitToBlock;
179     }
180 
181 
182     /**
183      * Utility method which, given a {@link List} of objects and a {@link Map}
184      * where those objects appear as keys, returns a <code>List</code> of the
185      * values to which the keys map, in the corresponding order.
186      *
187      * @param keys the keys to be looked up.
188      *
189      * @param keyToValue the map in which to look up the keys.
190      *
191      * @throws IllegalStateException if one of the elements in <code>keys</code>
192      * does not appear in <code>keyToValue</code>
193      */
194     private List mappedValues(List keys, Map keyToValue) {
195     List result = new ArrayList(keys.size());
196     for (Iterator it = keys.iterator(); it.hasNext(); ) {
197         Object   key = it.next();
198         Object   value = keyToValue.get(key);
199         if (value == null) {
200         throw new IllegalStateException  ("No value corresponding to key: " + key.toString());
201         }
202         result.add(value);
203     }
204     return result;
205     }
206 
207 
208     private Map buildExceptionDests(ExceptionalUnitGraph unitGraph, 
209                     Map unitToBlock) {
210     Map result = new HashMap(mBlocks.size() * 2 + 1, 0.7f);
211     for (Iterator blockIt = mBlocks.iterator(); blockIt.hasNext(); ) {
212         Block block = (Block) blockIt.next();
213         result.put(block, collectDests(block, unitGraph, unitToBlock));
214     }
215     return result;
216     }
217 
218 
219     /**
220      * Utility method which, given a {@link Block} and the 
221      * {@link ExceptionalUnitGraph} from which it was constructed,
222      * returns the {@link ExceptionDest}s representing the exceptions
223      * which may be thrown by units in the block.
224      *
225      * @param block the {@link Block} whose exceptions are to be collected.
226      *
227      * @param unitGraph the {@link ExceptionalUnitGraph} from which this 
228      *                  graph is constructed.
229      *
230      * @param unitToBlock a {@link Map} from the units which are block heads 
231      *                    or tails to the blocks that they belong to.
232      *
233      * @return a {@link Collection} of {@link ExceptionDest}s representing 
234      *           the exceptions that may be thrown by this block, together
235      *           with their catchers.
236      */
237     private Collection collectDests(Block block, ExceptionalUnitGraph unitGraph,
238                     Map unitToBlock) {
239     Unit blockHead = block.getHead();
240     Unit blockTail = block.getTail();
241     ArrayList blocksDests = null;
242     ThrowableSet escapingThrowables = ThrowableSet.Manager.v().EMPTY;
243     Map trapToThrowables = null;    // Don't allocate unless we need it.
244     int caughtCount = 0;
245 
246     for (Iterator unitIt = block.iterator(); unitIt.hasNext(); ) {
247         Unit unit = (Unit) unitIt.next();
248         Collection unitDests = unitGraph.getExceptionDests(unit);
249         if (unitDests.size() != 1 && unit != blockHead && unit != blockTail) {
250         throw new IllegalStateException  ("Multiple ExceptionDests associated with a unit which does not begin or end its block.");
251         }
252         for (Iterator destIt = unitDests.iterator(); destIt.hasNext(); ) {
253         ExceptionalUnitGraph.ExceptionDest unitDest 
254             = (ExceptionalUnitGraph.ExceptionDest) destIt.next();
255         if (unitDest.getTrap() == null) {
256             try {
257             escapingThrowables = escapingThrowables.add(unitDest.getThrowables());
258             } catch (ThrowableSet.AlreadyHasExclusionsException e) {
259             if (escapingThrowables != ThrowableSet.Manager.v().EMPTY) {
260                 // Return multiple escaping ExceptionDests,
261                 // since ThrowableSet's limitations do not permit us
262                 // to add all the escaping type descriptions together.
263                 if (blocksDests == null) {
264                 blocksDests = new ArrayList(10);
265                 }
266                 blocksDests.add(new ExceptionDest(null, 
267                                   escapingThrowables,
268                                   null));
269             }
270             escapingThrowables = unitDest.getThrowables();
271             }
272         } else {
273             if (unit != blockHead && unit != blockTail) {
274             // Assertion failure.
275             throw new IllegalStateException  ("Unit " 
276                             + unit.toString() 
277                             + " is not a block head or tail, yet it throws " 
278                             + unitDest.getThrowables() 
279                             + " to "
280                             + unitDest.getTrap());
281             }
282             caughtCount++;
283             if (trapToThrowables == null) {
284             trapToThrowables = new HashMap(unitDests.size() * 2);
285             }
286             Trap trap = unitDest.getTrap();
287             ThrowableSet throwables = (ThrowableSet) trapToThrowables.get(trap);
288             if (throwables == null) {
289             throwables = unitDest.getThrowables();
290             } else {
291             throwables = throwables.add(unitDest.getThrowables());
292             }
293             trapToThrowables.put(trap, throwables);
294         }
295         }
296     }
297     
298     if (blocksDests == null) {
299         blocksDests = new ArrayList(caughtCount + 1);
300     } else {
301         blocksDests.ensureCapacity(blocksDests.size() + caughtCount);
302     }
303 
304     if (escapingThrowables != ThrowableSet.Manager.v().EMPTY) {
305         ExceptionDest escapingDest = new ExceptionDest(null, escapingThrowables, 
306                                null);
307         blocksDests.add(escapingDest);
308     }
309     if (trapToThrowables != null) {
310         for (Iterator entryIt = trapToThrowables.entrySet().iterator();
311          entryIt.hasNext(); ) {
312         Map.Entry entry = (Map.Entry) entryIt.next();
313         Trap trap = (Trap) entry.getKey();
314         Block trapBlock = (Block) unitToBlock.get(trap.getHandlerUnit());
315         if (trapBlock == null) {
316             throw new IllegalStateException  ("catching unit is not recorded as a block leader.");
317         }
318         ThrowableSet throwables = (ThrowableSet) entry.getValue();
319         ExceptionDest blockDest = new ExceptionDest(trap, throwables, trapBlock);
320         blocksDests.add(blockDest);
321         }
322     }
323     return blocksDests;
324     }
325 
326                                   
327     public List getUnexceptionalPredsOf(Object   b) {
328     if ((blockToUnexceptionalPreds == null) 
329         || (! blockToUnexceptionalPreds.containsKey(b))) {
330         Block block = (Block) b;
331         return block.getPreds();
332     } else {
333         return (List) blockToUnexceptionalPreds.get(b);
334     }
335     }
336 
337 
338     public List getUnexceptionalSuccsOf(Object   b) {
339     if ((blockToUnexceptionalSuccs == null) 
340         || (! blockToUnexceptionalSuccs.containsKey(b))) {
341         Block block = (Block) b;
342         return block.getSuccs();
343     } else {
344         return (List) blockToUnexceptionalSuccs.get(b);
345     }
346     }
347 
348 
349     public List getExceptionalPredsOf(Object    b) {
350     if (blockToExceptionalPreds == null ||
351         (!blockToExceptionalPreds.containsKey(b))) {
352         return Collections.EMPTY_LIST;
353     } else {
354         return (List) blockToExceptionalPreds.get(b);
355     }
356     }
357 
358 
359     public List getExceptionalSuccsOf(Object   b) {
360     if (blockToExceptionalSuccs == null ||
361         (!blockToExceptionalSuccs.containsKey(b))) {
362         return Collections.EMPTY_LIST;
363     } else {
364         return (List) blockToExceptionalSuccs.get(b);
365     }
366     }
367 
368 
369     public Collection getExceptionDests(Object   b) {
370     if (blockToExceptionDests == null) {
371         Block block = (Block) b;
372         Collection result = new ArrayList(1);
373         ThrowableSet throwables = ThrowableSet.Manager.v().EMPTY;
374         for (Iterator unitIt = block.iterator(); unitIt.hasNext(); ) {
375         Unit unit = (Unit) unitIt.next();
376         throwables = throwables.add(throwAnalysis.mightThrow(unit));
377         }
378         result.add(new ExceptionalBlockGraph.ExceptionDest(null, throwables,
379                                    null));
380         return result;
381     } else {
382         return (Collection) blockToExceptionDests.get(b);
383     }
384     }
385 
386 
387     public static class ExceptionDest implements ExceptionalGraph.ExceptionDest {
388     private Trap trap;
389     private ThrowableSet throwables;
390     private Block handler;
391 
392     protected ExceptionDest(Trap trap, ThrowableSet throwables, Block handler) {
393         this.trap = trap;
394         this.throwables = throwables;
395         this.handler = handler;
396     }
397     
398     public Trap getTrap() {
399         return trap;
400     }
401 
402     public ThrowableSet getThrowables() {
403         return throwables;
404     }
405 
406     public Object   getHandlerNode() {
407         return handler;
408     }
409 
410     public String   toString() {
411         StringBuffer   buf = new StringBuffer  ();
412         buf.append(throwables.toString());
413         buf.append(" -> ");
414         if (trap == null) {
415         buf.append("(escapes)");
416         } else {
417         buf.append(trap.toString());
418         buf.append("handler: ");
419         buf.append(getHandlerNode().toString());
420         }
421         return buf.toString();
422     }
423     }
424 }
425 
426 
427
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags