Java > Open Source Codes > soot > toolkits > graph > GraphComparer


1 /**
2  * This class is a piece of test infrastructure. It compares various
3  * varieties of control flow graphs.
4  */
5
6 package soot.toolkits.graph;
7
8 import java.lang.Class ;
9 import java.lang.reflect.Method ;
10 import java.util.ArrayList ;
11 import java.util.Collection ;
12 import java.util.Collections ;
13 import java.util.HashMap ;
14 import java.util.Iterator ;
15 import java.util.List ;
16 import java.util.Map ;
17 import java.util.Set ;
18 import soot.Body;
19 import soot.BriefUnitPrinter;
20 import soot.CompilationDeathException;
21 import soot.G;
22 import soot.LabeledUnitPrinter;
23 import soot.SootMethod;
24 import soot.Trap;
25 import soot.Unit;
26 import soot.options.Options;
27 import soot.toolkits.graph.ExceptionalUnitGraph.ExceptionDest;
28 import soot.util.ArraySet;
29 import soot.util.Chain;
30
31 public class GraphComparer {
32
33     DirectedGraph g1;
34     DirectedGraph g2;
35
36     /**
37      * Utility interface for keeping track of graph nodes which
38      * are considered to represent equivalent nodes in
39      * the two graphs being compared.
40      */
41     interface EquivalenceRegistry {
42     /**
43      * @param node a node in one graph.
44      * @return the equivalent node from the other graph.
45      */
46     Object getEquiv(Object node);
47     }
48
49     EquivalenceRegistry equivalences = null;
50
51     /**
52      * {@link EquivalenceRegistry} for comparing two {@link UnitGraph}s
53      * Since the same {@link Unit}s are stored as nodes in both graphs,
54      * equivalence is the same as object equality.
55      */
56     class EquivalentUnitRegistry implements EquivalenceRegistry {
57     /**
58      * @param node a graph node that represents a {@link Unit}.
59      * @return <tt>node</tt>.
60      */
61     public Object getEquiv(Object node) {
62         return node;
63     }
64     }
65
66     
67     /**
68      * {@link EquivalenceRegistry} for comparing two {@link BlockGraph}s.
69      * Two blocks are considered equivalent if they contain exactly the same
70      * list of {@link Unit}s, in the same order.
71      */
72     static class EquivalentBlockRegistry implements EquivalenceRegistry {
73     private Map equivalenceMap = new HashMap ();
74
75     /**
76      * Create an {@link EquivalentBlockRegistry} which records the
77      * equivalent blocks in two graphs whose nodes are blocks. To
78      * allow the use of graphs that are loaded from alternate
79      * class paths, the parameters are not required to be instances of
80      * {@link BlockGraph}. They just have to be {@link
81      * DirectedGraph}s whose nodes are instances of some class
82      * that has an <tt>iterator()</tt> method that iterates over
83      * the {@link Unit}s in that block.
84      *
85      * @param g1 The first graph to register.
86      * @param g2 The second graph to register.
87      * @throws IllegalArgumentException if a given {@link Unit} appears
88      * in more than one block of either of the graphs.
89      */
90      
91     EquivalentBlockRegistry(DirectedGraph g1, DirectedGraph g2) {
92         Map g1UnitToBlock = blockGraphToUnitMap(g1); // We don't need this
93 // map, but we want
94 // to confirm that no
95 // Unit appears in
96 // multiple Blocks.
97 Map g2UnitToBlock = blockGraphToUnitMap(g2);
98         for (Iterator g1it = g1.iterator(); g1it.hasNext(); ) {
99         Object g1Block = g1it.next();
100         List g1Units = getUnits(g1Block);
101         Object g2Block = g2UnitToBlock.get(g1Units.get(0));
102         List g2Units = getUnits(g2Block);
103         if (g1Units.equals(g2Units)) {
104             equivalenceMap.put(g1Block, g2Block);
105             equivalenceMap.put(g2Block, g1Block);
106         }
107         }
108     }
109
110
111     /**
112      * @param node a graph node that represents a {@link Block}.
113      * @return the node from the other graph being compared which
114      * represents the same block, or <tt>null</tt> if there
115      * is no such node.
116      */
117     public Object getEquiv(Object node) {
118         return equivalenceMap.get(node);
119     }
120
121
122     /**
123      * Return a map from a {@link Unit} in the body represented by
124      * a {@link BlockGraph} to the graph node representing the
125      * block containing that {@link Unit}.
126      *
127      * @param g a graph whose nodes represent lists of {@link Unit}s.
128      * The nodes must have an <tt>iterator()</tt> method which
129      * will iterate over the {@link Unit}s represented by the
130      * node.
131      * @return a {@link Map} from {@link Unit}s to {@link Object}s
132      * that are the graph nodes containing those {@link Unit}s.
133      * @throws IllegalArgumentException should any node of <tt>g</tt>
134      * lack an <tt>iterator()</tt> method or should
135      * any {@link Unit} appear in
136      * more than one node of the graph.
137      */
138     private static Map blockGraphToUnitMap(DirectedGraph g)
139     throws IllegalArgumentException {
140         Map result = new HashMap ();
141         for (Iterator blockIt = g.iterator(); blockIt.hasNext(); ) {
142         Object block = blockIt.next();
143         List units = getUnits(block);
144         for (Iterator unitIt = units.iterator(); unitIt.hasNext(); ) {
145             Unit unit = (Unit) unitIt.next();
146             if (result.containsKey(unit)) {
147             throw new IllegalArgumentException ("blockGraphToUnitMap(): adding " +
148                                unit.toString() +
149                                " twice");
150             }
151             result.put(unit, block);
152         }
153         }
154         return result;
155     }
156
157
158     /**
159      * Return the {@link List} of {@link Unit}s represented by an
160      * object which has an <tt>iterator()</tt> method which
161      * iterates over {@link Unit}s.
162      *
163      * @param block the object which contains a list of {@link Unit}s.
164      * @return the list of {@link Unit}s.
165      */
166     private static List getUnits(Object block) {
167         Class blockClass = block.getClass();
168         Class [] emptyParams = new Class [0];
169         List result = new ArrayList ();
170         try {
171         Method iterMethod = blockClass.getMethod("iterator", emptyParams);
172         for (Iterator it = (Iterator ) iterMethod.invoke(block, emptyParams);
173              it.hasNext(); ) {
174             Unit unit = (Unit) it.next();
175             result.add(unit);
176         }
177         } catch (NoSuchMethodException e) {
178         throw new IllegalArgumentException ("GraphComparer.getUnits(): node lacks iterator() method.");
179         } catch (IllegalAccessException e) {
180         throw new IllegalArgumentException ("GraphComparer.getUnits(): inaccessible iterator() method.");
181         } catch (java.lang.reflect.InvocationTargetException e) {
182         throw new IllegalArgumentException ("GraphComparer.getUnits(): failed iterator() invocation.");
183         }
184         return result;
185     }
186     }
187
188
189
190     /**
191      * Utility interface for checking whether two graphs of particular types
192      * differ only in the ways we would expect from two graphs
193      * of those types that represent the same {@link Body}.
194      */
195     interface TypedGraphComparer {
196     /**
197      * @return true if the two graphs represented by this comparer
198      * differ only in expected ways.
199      */
200     boolean onlyExpectedDiffs();
201     }
202
203     TypedGraphComparer subcomparer = null;
204
205     /**
206      * Return a class that implements <tt>TypedGraphComparer</tt> for
207      * the two graphs being compared by this <tt>GraphComparer</tt>,
208      * or <tt>null</tt>, if there is no comparer available to compare
209      * their types.
210      */
211     TypedGraphComparer TypedGraphComparerFactory() {
212     class TypeAssignments {
213         // Note that "Alt" graphs are loaded from an alternate
214 // class path, so we need ugly, fragile, special-purpose
215 // hacks to recognize them.
216
217         ExceptionalUnitGraph exceptionalUnitGraph = null;
218         boolean omitExceptingUnitEdges;
219
220         ClassicCompleteUnitGraph classicCompleteUnitGraph = null;
221         DirectedGraph altCompleteUnitGraph = null;
222         TrapUnitGraph trapUnitGraph = null;
223         DirectedGraph altTrapUnitGraph = null;
224         BriefUnitGraph briefUnitGraph = null;
225         DirectedGraph altBriefUnitGraph = null;
226         BriefBlockGraph briefBlockGraph = null;
227         ExceptionalBlockGraph exceptionalBlockGraph = null;
228         ClassicCompleteBlockGraph classicCompleteBlockGraph = null;
229         DirectedGraph altCompleteBlockGraph = null;
230         DirectedGraph altBriefBlockGraph = null;
231         ArrayRefBlockGraph arrayRefBlockGraph = null;
232         DirectedGraph altArrayRefBlockGraph = null;
233         ZonedBlockGraph zonedBlockGraph = null;
234         DirectedGraph altZonedBlockGraph = null;
235
236         TypeAssignments(DirectedGraph g1, DirectedGraph g2) {
237         this.add(g1);
238         this.add(g2);
239         }
240
241         // The type-specific add() routine provides a means to
242 // specify the value of omitExceptingUnitEdges
243 // for ExceptionalUnitGraph. We are counting on the
244 // callers to keep straight whether the graph was created
245 // with a non-default value for
246 // omitExceptingUnitEdges, since it doesn't seem
247 // worth saving the value of the boolean used with each
248 // ExceptionalUnitGraph constructed.
249 void add(ExceptionalUnitGraph g, boolean omitExceptingUnitEdges) {
250         this.exceptionalUnitGraph = g;
251         this.omitExceptingUnitEdges
252             = omitExceptingUnitEdges;
253         }
254
255         void add(DirectedGraph g) {
256         if (g instanceof CompleteUnitGraph) {
257             this.add((ExceptionalUnitGraph) g, false);
258         } else if (g instanceof ExceptionalUnitGraph) {
259             this.add((ExceptionalUnitGraph) g,
260                  Options.v().omit_excepting_unit_edges());
261         } else if (g instanceof ClassicCompleteUnitGraph) {
262             classicCompleteUnitGraph = (ClassicCompleteUnitGraph) g;
263         } else if (g.getClass().getName().endsWith(".CompleteUnitGraph")) {
264             altCompleteUnitGraph = g;
265         } else if (g instanceof TrapUnitGraph) {
266             trapUnitGraph = (TrapUnitGraph) g;
267         } else if (g.getClass().getName().endsWith(".TrapUnitGraph")) {
268             altTrapUnitGraph = g;
269         } else if (g instanceof BriefUnitGraph) {
270             briefUnitGraph = (BriefUnitGraph) g;
271         } else if (g.getClass().getName().endsWith(".BriefUnitGraph")) {
272             altBriefUnitGraph = g;
273         } else if (g instanceof ExceptionalBlockGraph) {
274             exceptionalBlockGraph = (ExceptionalBlockGraph) g;
275         } else if (g instanceof ClassicCompleteBlockGraph) {
276             classicCompleteBlockGraph = (ClassicCompleteBlockGraph) g;
277         } else if (g.getClass().getName().endsWith(".CompleteBlockGraph")) {
278             altCompleteBlockGraph = g;
279         } else if (g instanceof BriefBlockGraph) {
280             briefBlockGraph = (BriefBlockGraph) g;
281         } else if (g.getClass().getName().endsWith(".BriefBlockGraph")) {
282             altBriefBlockGraph = g;
283         } else if (g instanceof ArrayRefBlockGraph) {
284             arrayRefBlockGraph = (ArrayRefBlockGraph) g;
285         } else if (g.getClass().getName().endsWith(".ArrayRefBlockGraph")) {
286             altArrayRefBlockGraph = g;
287         } else if (g instanceof ZonedBlockGraph) {
288             zonedBlockGraph = (ZonedBlockGraph) g;
289         } else if (g.getClass().getName().endsWith(".ZonedBlockGraph")) {
290             altZonedBlockGraph = g;
291         } else {
292             throw new IllegalStateException ("GraphComparer.add(): don't know how to add("
293                             + g.getClass().getName()
294                             + ')');
295         }
296         }
297     }
298     TypeAssignments subtypes = new TypeAssignments(g1, g2);
299
300     if (subtypes.exceptionalUnitGraph != null &&
301         subtypes.classicCompleteUnitGraph != null) {
302         return new ExceptionalToClassicCompleteUnitGraphComparer(
303          subtypes.exceptionalUnitGraph,
304          subtypes.classicCompleteUnitGraph,
305          subtypes.omitExceptingUnitEdges);
306     }
307
308     if (subtypes.exceptionalUnitGraph != null &&
309         subtypes.trapUnitGraph != null) {
310         return new ExceptionalToTrapUnitGraphComparer(subtypes.exceptionalUnitGraph,
311                               subtypes.trapUnitGraph,
312                               subtypes.omitExceptingUnitEdges);
313     }
314
315     if (subtypes.classicCompleteBlockGraph != null &&
316         subtypes.altCompleteBlockGraph != null) {
317         return new BlockToAltBlockGraphComparer(subtypes.classicCompleteBlockGraph,
318                             subtypes.altCompleteBlockGraph);
319     }
320
321     if (subtypes.briefBlockGraph != null &&
322         subtypes.altBriefBlockGraph != null) {
323         return new BlockToAltBlockGraphComparer(subtypes.briefBlockGraph,
324                             subtypes.altBriefBlockGraph);
325     }
326
327     if (subtypes.arrayRefBlockGraph != null &&
328         subtypes.altArrayRefBlockGraph != null) {
329         return new BlockToAltBlockGraphComparer(subtypes.arrayRefBlockGraph,
330                             subtypes.altArrayRefBlockGraph);
331     }
332
333     if (subtypes.zonedBlockGraph != null &&
334         subtypes.altZonedBlockGraph != null) {
335         return new BlockToAltBlockGraphComparer(subtypes.zonedBlockGraph,
336                             subtypes.altZonedBlockGraph);
337     }
338     return null;
339     }
340
341
342     public GraphComparer(DirectedGraph g1, DirectedGraph g2) {
343     // Since we may be comparing graphs of classes loaded
344 // from alternate class paths, we'll use conventions in
345 // the class names to recognize BlockGraphs.
346 this.g1 = g1;
347     this.g2 = g2;
348     String g1ClassName = g1.getClass().getName();
349     String g2ClassName = g2.getClass().getName();
350     if (g1ClassName.endsWith("BlockGraph") &&
351         g2ClassName.endsWith("BlockGraph")) {
352         equivalences = new EquivalentBlockRegistry(g1, g2);
353     } else {
354         equivalences = new EquivalentUnitRegistry();
355     }
356     subcomparer = TypedGraphComparerFactory();
357     }
358
359
360     /**
361      * Checks that the two graphs in the GraphComparer differ only in
362      * ways that the GraphComparer expects that they should differ,
363      * given the types of graphs they are, assuming that the two
364      * graphs represent the same body.
365      */
366     public boolean onlyExpectedDiffs() {
367     if (subcomparer == null) {
368         return equal();
369     } else {
370         return subcomparer.onlyExpectedDiffs();
371     }
372     }
373     
374
375     /**
376      * Checks if a graph's edge set is consistent.
377      *
378      * @param g the {@link DirectedGraph} whose edge set is to be
379      * checked.
380      *
381      * @return <tt>true</tt> if <tt>g</tt>'s edge set is consistent
382      * (meaning that <tt>x</tt> is recorded as a predecessor of <tt>y</tt>
383      * if and only if <tt>y</tt> is recorded as a successor of <tt>x</tt>).
384      */
385     public static boolean consistentGraph(DirectedGraph g) {
386     for (Iterator nodeIt = g.iterator(); nodeIt.hasNext(); ) {
387         Object node = nodeIt.next();
388         for (Iterator predIt = g.getPredsOf(node).iterator();
389          predIt.hasNext(); ) {
390         Object pred = predIt.next();
391         if (! g.getSuccsOf(pred).contains(node)) {
392             return false;
393         }
394         }
395         for (Iterator succIt = g.getSuccsOf(node).iterator();
396          succIt.hasNext(); ) {
397         Object succ = succIt.next();
398         if (! g.getPredsOf(succ).contains(node)) {
399             return false;
400         }
401         }
402     }
403     return true;
404     }
405
406
407     /**
408      * Compares this {@link GraphComparer}'s two {@link DirectedGraph}s.
409      *
410      * @return <tt>true</tt> if the two graphs have
411      * the same nodes, the same lists of heads and tails, and the
412      * same sets of edges, <tt>false</tt> otherwise.
413      */
414     public boolean equal() {
415     if ((! consistentGraph(g1)) || (! consistentGraph(g2))) {
416         throw new CompilationDeathException(
417         CompilationDeathException.COMPILATION_ABORTED,
418         "Cannot compare inconsistent graphs");
419     }
420     if (! equivLists(g1.getHeads(), g2.getHeads())) {
421         return false;
422     }
423     if (! equivLists(g1.getTails(), g2.getTails())) {
424         return false;
425     }
426     return equivPredsAndSuccs();
427     }
428
429
430     /**
431      * <p>Compares the predecessors and successors of corresponding
432      * nodes of this {@link GraphComparer}'s two {@link
433      * DirectedGraph}s. This is factored out for sharing by {@link
434      * #equal()} and {@link BlockToAltBlockGraphComparer#onlyExpectedDiffs}.
435      *
436      * @return <tt>true</tt> if the predecessors and successors of each
437      * node in one graph are equivalent to the predecessors and successors
438      * of the equivalent node in the other graph.
439      */
440     protected boolean equivPredsAndSuccs() {
441     if (g1.size() != g2.size()) {
442         return false;
443     }
444     // We know the two graphs have the same size, so we only need
445 // to iterate through one's nodes to see if the two match.
446 for (Iterator g1it = g1.iterator(); g1it.hasNext(); ) {
447         Object g1node = g1it.next();
448         try {
449         if (! equivLists(g1.getSuccsOf(g1node),
450                  g2.getSuccsOf(equivalences.getEquiv(g1node)))) {
451             return false;
452         }
453         if (! equivLists(g1.getPredsOf(g1node),
454                  g2.getPredsOf(equivalences.getEquiv(g1node)))) {
455             return false;
456         }
457         } catch (RuntimeException e) {
458         if (e.getMessage() != null &&
459             e.getMessage().startsWith("Invalid unit ")) {
460             return false;
461         } else {
462             throw e;
463         }
464         }
465     }
466     return true;
467     }
468
469
470     /**
471      * Report the differences between the two {@link DirectedGraph}s.
472      *
473      * @param graph1Label a string to be used to identify the first
474      * graph (<tt>g1</tt> in the call to {@link
475      * GraphComparer#GraphComparer()}) in the report of differences.
476      *
477      * @param graph2Label a string to be used to identify the second
478      * graph (<tt>g2</tt> in the call to {@link
479      * GraphComparer@GraphComparer()}) in the report of differences .
480      *
481      * @return a {@link String} summarizing the differences
482      * between the two graphs.
483      */
484     public String diff(String graph1Label, String graph2Label) {
485     StringBuffer report = new StringBuffer ();
486     LabeledUnitPrinter printer1 = makeUnitPrinter(g1);
487     LabeledUnitPrinter printer2 = makeUnitPrinter(g2);
488     diffList(report, printer1, printer2, "HEADS",
489          g1.getHeads(), g2.getHeads());
490     diffList(report, printer1, printer2, "TAILS",
491          g1.getTails(), g2.getTails());
492            
493     for (Iterator g1it = g1.iterator(); g1it.hasNext(); ) {
494         Object g1node = g1it.next();
495         Object g2node = equivalences.getEquiv(g1node);
496         String g1string = nodeToString(g1node, printer1);
497         List g1succs = g1.getSuccsOf(g1node);
498         List g1preds = g1.getPredsOf(g1node);
499         List g2succs = null;
500         List g2preds = null;
501
502         try {
503         if (g2node != null) {
504             g2preds = g2.getPredsOf(g2node);
505         }
506         } catch (RuntimeException e) {
507         if (e.getMessage() != null &&
508             e.getMessage().startsWith("Invalid unit ")) {
509             // No preds entry for g1node in g2
510 } else {
511             throw e;
512         }
513         }
514         diffList(report, printer1, printer2, g1string + " PREDS",
515              g1preds, g2preds);
516
517         try {
518         if (g2node != null) {
519             g2succs = g2.getSuccsOf(g2node);
520         }
521         } catch (RuntimeException e) {
522         if (e.getMessage() != null &&
523             e.getMessage().startsWith("Invalid unit ")) {
524             // No succs entry for g1node in g2
525 } else {
526             throw e;
527         }
528         }
529         diffList(report, printer1, printer2, g1string + " SUCCS",
530              g1succs, g2succs);
531
532         
533     }
534
535     for (Iterator g2it = g2.iterator(); g2it.hasNext(); ) {
536         // In this loop we Only need to report the cases where
537 // there is no g1 entry at all, cases where there is an
538 // entry in both graphs but with differing lists of preds
539 // or succs will have already been reported by the loop over
540 // g1's nodes.
541 Object g2node = g2it.next();
542         Object g1node = equivalences.getEquiv(g2node);
543         String g2string = nodeToString(g2node, printer2);
544         List g2succs = g2.getSuccsOf(g2node);
545         List g2preds = g2.getPredsOf(g2node);
546
547         try {
548         if (g1node != null) {
549             g1.getPredsOf(g1node);
550         }
551         } catch (RuntimeException e) {
552         if (e.getMessage() != null &&
553             e.getMessage().startsWith("Invalid unit ")) {
554             diffList(report, printer1, printer2,
555                  g2string + " PREDS",
556                  null, g2preds);
557         } else {
558             throw e;
559         }
560         }
561
562         try {
563         if (g1node != null) {
564             g1.getSuccsOf(g1node);
565         }
566         } catch (RuntimeException e) {
567         if (e.getMessage() != null &&
568             e.getMessage().startsWith("Invalid unit ")) {
569             diffList(report, printer1, printer2,
570                  g2string + " SUCCS" ,
571                  null, g2succs);
572         } else {
573             throw e;
574         }
575         }
576     }
577
578     if (report.length() > 0) {
579         String leader1 = "*** ";
580         String leader2 = "\n--- ";
581         String leader3 = "\n";
582         StringBuffer result = new StringBuffer (leader1.length() +
583                            graph1Label.length() +
584                            leader2.length() +
585                            graph2Label.length() +
586                            leader3.length() +
587                            report.length());
588         result.append(leader1)
589         .append(graph1Label)
590         .append(leader2)
591         .append(graph2Label)
592         .append(leader3)
593         .append(report);
594         return result.toString();
595     } else {
596         return "";
597     }
598     }
599
600
601     /**
602      * Class for comparing a {@link TrapUnitGraph} to an {@link
603      * ExceptionalUnitGraph}.
604      */
605     class ExceptionalToTrapUnitGraphComparer implements TypedGraphComparer {
606     protected ExceptionalUnitGraph exceptional;
607     protected TrapUnitGraph cOrT; // ClassicCompleteUnitGraph Or TrapUnitGraph.
608 protected boolean omitExceptingUnitEdges;
609
610     /**
611      * Indicates whether {@link #predOfTrappedThrower()} should
612      * return false for edges from head to tail when the only one
613      * of head's successors which throws an exception caught by
614      * tail is the first unit trapped by tail (this distinguishes
615      * ClassicCompleteUnitGraph from TrapUnitGraph).
616      */
617     protected boolean predOfTrappedThrowerScreensFirstTrappedUnit;
618
619     ExceptionalToTrapUnitGraphComparer(ExceptionalUnitGraph exceptional,
620                        TrapUnitGraph cOrT,
621                        boolean omitExceptingUnitEdges) {
622         this.exceptional = exceptional;
623         this.cOrT = cOrT;
624         this.omitExceptingUnitEdges
625         = omitExceptingUnitEdges;
626         this.predOfTrappedThrowerScreensFirstTrappedUnit = false;
627     }
628
629     public boolean onlyExpectedDiffs() {
630             if (exceptional.size() != cOrT.size()) {
631         if (Options.v().verbose())
632             G.v().out.println("ExceptionalToTrapUnitComparer.onlyExpectedDiffs(): sizes differ" + exceptional.size() + " " + cOrT.size());
633             return false;
634         }
635
636         if (! (exceptional.getHeads().containsAll(cOrT.getHeads())
637            && cOrT.getHeads().containsAll(exceptional.getHeads())) ) {
638         if (Options.v().verbose())
639             G.v().out.println("ExceptionalToTrapUnitComparer.onlyExpectedDiffs(): heads differ");
640         return false;
641         }
642
643         if (! (exceptional.getTails().containsAll(cOrT.getTails()))) {
644         return false;
645         }
646
647         for (Iterator tailIt = exceptional.getTails().iterator();
648          tailIt.hasNext(); ) {
649         Object tail = tailIt.next();
650         if ((! cOrT.getTails().contains(tail)) &&
651             (! trappedReturnOrThrow(tail))) {
652             if (Options.v().verbose())
653             G.v().out.println("ExceptionalToTrapUnitComparer.onlyExpectedDiffs(): " + tail.toString() + " is not a tail in cOrT, but not a trapped Return or Throw either");
654             return false;
655         }
656         }
657
658         // Since we've already confirmed that the two graphs have
659 // the same number of nodes, we only need to iterate through
660 // the nodes of one of them --- if they don't have exactly the same
661 // set of nodes, this single iteration will reveal some
662 // node in cOrT that is not in exceptional.
663 for (Iterator nodeIt = cOrT.iterator(); nodeIt.hasNext(); ) {
664         Unit node = (Unit) nodeIt.next();
665         try {
666             List cOrTSuccs = cOrT.getSuccsOf(node);
667             List exceptionalSuccs = exceptional.getSuccsOf(node);
668             for (Iterator it = cOrTSuccs.iterator(); it.hasNext(); ) {
669             Unit cOrTSucc = (Unit) it.next();
670             if ((! exceptionalSuccs.contains(cOrTSucc)) &&
671                 (! cannotReallyThrowTo(node, cOrTSucc))) {
672                 if (Options.v().verbose())
673                 G.v().out.println("ExceptionalToTrapUnitComparer.onlyExpectedDiffs(): " + cOrTSucc.toString() + " is not exceptional successor of " + node.toString() + " even though " + node.toString() + " can throw to it");
674                 return false;
675             }
676             }
677             for (Iterator it = exceptionalSuccs.iterator(); it.hasNext(); ) {
678             Unit exceptionalSucc = (Unit) it.next();
679             if ((! cOrTSuccs.contains(exceptionalSucc)) &&
680                 (! predOfTrappedThrower(node, exceptionalSucc))) {
681                 if (Options.v().verbose())
682                 G.v().out.println("ExceptionalToTrapUnitComparer.onlyExpectedDiffs(): " + exceptionalSucc.toString() + " is not TrapUnitGraph successor of " + node.toString() + " even though " + node.toString() + " is not a predOfTrappedThrower or predOfTrapBegin");
683                 return false;
684             }
685             }
686
687             List cOrTPreds = cOrT.getPredsOf(node);
688             List exceptionalPreds = exceptional.getPredsOf(node);
689             for (Iterator it = cOrTPreds.iterator(); it.hasNext(); ) {
690             Unit cOrTPred = (Unit) it.next();
691             if ((! exceptionalPreds.contains(cOrTPred)) &&
692                 (! cannotReallyThrowTo(cOrTPred, node))) {
693                 if (Options.v().verbose())
694                 G.v().out.println("ExceptionalToTrapUnitComparer.onlyExpectedDiffs(): " + cOrTPred.toString() + " is not ExceptionalUnitGraph predecessor of " + node.toString() + " even though " + cOrTPred.toString() + " can throw to " + node.toString());
695                 return false;
696             }
697             }
698             for (Iterator it = exceptionalPreds.iterator(); it.hasNext(); ) {
699             Unit exceptionalPred = (Unit) it.next();
700             if ((! cOrTPreds.contains(exceptionalPred)) &&
701                 (! predOfTrappedThrower(exceptionalPred, node))) {
702                 if (Options.v().verbose())
703                 G.v().out.println("ExceptionalToTrapUnitComparer.onlyExpectedDiffs(): " + exceptionalPred.toString() + " is not COrTUnitGraph predecessor of " + node.toString() + " even though " + exceptionalPred.toString() + " is not a predOfTrappedThrower");
704                 return false;
705             }
706             }
707             
708         } catch (RuntimeException e) {
709             e.printStackTrace(System.err);
710             if (e.getMessage() != null &&
711             e.getMessage().startsWith("Invalid unit ")) {
712             if (Options.v().verbose())
713                 G.v().out.println("ExceptionalToTrapUnitComparer.onlyExpectedDiffs(): " + node.toString() + " is not in ExceptionalUnitGraph at all");
714             // node is not in exceptional graph.
715 return false;
716             } else {
717             throw e;
718             }
719         }
720         }
721         return true;
722     }
723
724
725     /**
726      * <p>A utility method for confirming that a node which is
727      * considered a tail by a {@link ExceptionalUnitGraph} but not by the
728      * corresponding {@link TrapUnitGraph} or {@link
729      * ClassicCompleteUnitGraph} is a return instruction or throw
730      * instruction with a {@link Trap} handler as its successor in the
731      * {@link TrapUnitGraph} or {@link ClassicCompleteUnitGraph}.</p>
732      *
733      * @param node the node which is considered a tail by
734      * <tt>exceptional</tt> but not by <tt>cOrT</tt>.
735      *
736      * @return <tt>true</tt> if <tt>node</tt> is a return instruction
737      * which has a trap handler as its successor in <tt>cOrT</tt>.\
738      */
739     protected boolean trappedReturnOrThrow(Object node) {
740         if (! ((node instanceof soot.jimple.ReturnStmt) ||
741            (node instanceof soot.jimple.ReturnVoidStmt) ||
742            (node instanceof soot.baf.ReturnInst) ||
743            (node instanceof soot.baf.ReturnVoidInst) ||
744            (node instanceof soot.jimple.ThrowStmt) ||
745            (node instanceof soot.baf.ThrowInst))) {
746         return false;
747         }
748         List succsUnaccountedFor = new ArrayList (cOrT.getSuccsOf(node));
749         if (succsUnaccountedFor.size() <= 0) {
750         return false;
751         }
752         for (Iterator trapIt = cOrT.getBody().getTraps().iterator();
753          trapIt.hasNext(); ) {
754         Trap trap = (Trap) trapIt.next();
755         succsUnaccountedFor.remove(trap.getHandlerUnit());
756         }
757         return (succsUnaccountedFor.size() == 0);
758     }
759
760
761     /**
762      * A utility method for confirming that an edge which is in a
763      * {@link TrapUnitGraph} or {@link ClassicCompleteUnitGraph} but
764      * not the corresponding {@link ExceptionalUnitGraph} satisfies the
765      * criterion we would expect of such an edge: that it leads from a
766      * unit to a handler, that the unit might be expected to trap to
767      * the handler based solely on the range of Units trapped by the
768      * handler, but that there is no way for the particular exception
769      * that the handler catches to be thrown at this point.
770      *
771      * @param head the graph node that the edge leaves.
772      * @param tail the graph node that the edge leads to.
773      * @return true if <tt>head</tt> cannot really be associated with
774      * an exception that <tt>tail</tt> catches, false otherwise.
775      */
776     protected boolean cannotReallyThrowTo(Unit head, Unit tail) {
777         List tailsTraps = returnHandlersTraps(tail);
778
779         // Check if head is in one of the traps' protected
780 // area, but either cannot throw an exception that the
781 // trap catches, or is not included in ExceptionalUnitGraph
782 // because it has no side-effects:
783 Collection headsDests = exceptional.getExceptionDests(head);
784         for (Iterator it = tailsTraps.iterator(); it.hasNext(); ) {
785         Trap tailsTrap = (Trap) it.next();
786         if (amongTrappedUnits(head, tailsTrap)
787             && ((! destCollectionIncludes(headsDests, tailsTrap))
788             || ((! ExceptionalUnitGraph.mightHaveSideEffects(head))
789                 && omitExceptingUnitEdges))) {
790             return true;
791         }
792         
793         }
794         return false;
795     }
796
797
798     /**
799      * A utility method for determining if a {@link Unit} is among
800      * those protected by a particular {@link Trap}..
801      *
802      * @param unit the {@link Unit} being asked about.
803      *
804      * @param trap the {@link Trap} being asked about.
805      *
806      * @return <tt>true</tt> if <tt>unit</tt> is protected by
807      * <tt>trap</tt>, false otherwise.
808      */
809     protected boolean amongTrappedUnits(Unit unit, Trap trap) {
810         Chain units = exceptional.getBody().getUnits();
811         for (Iterator it = units.iterator(trap.getBeginUnit(),
812                           units.getPredOf(trap.getEndUnit()));
813          it.hasNext(); ) {
814         Unit u = (Unit) it.next();
815         if (u == unit) {
816             return true;
817         }
818         }
819         return false;
820     }
821
822
823     /**
824      * A utility method for confirming that an edge which is in a
825      * {@link CompleteUnitGraph} but not the corresponding {@link
826      * TrapUnitGraph} satisfies the criteria we would expect of such
827      * an edge: that the tail of the edge is a {@link Trap} handler,
828      * and that the head of the edge is not itself in the
829      * <tt>Trap</tt>'s protected area, but is the predecessor of a
830      * {@link Unit}, call it <tt>u</tt>, such that <tt>u</tt> is a
831      * <tt>Unit</tt> in the <tt>Trap</tt>'s protected area and
832      * <tt>u</tt> might throw an exception that the <tt>Trap</tt>
833      * catches.
834      *
835      * @param head the graph node that the edge leaves.
836      * @param tail the graph node that the edge leads to.
837      * @return a {@link List} of {@link Trap}s such that <tt>head</tt> is
838      * a predecessor of a {@link Unit} that might throw an exception
839      * caught by {@link Trap}.
840      */
841     protected boolean predOfTrappedThrower(Unit head, Unit tail) {
842         // First, ensure that tail is a handler.
843 List tailsTraps = returnHandlersTraps(tail);
844         if (tailsTraps.size() == 0) {
845         if (Options.v().verbose())
846             G.v().out.println("trapsReachedViaEdge(): " + tail.toString() + " is not a trap handler");
847         return false;
848         }
849
850         // Build a list of Units, other than head itself, which, if
851 // they threw a caught exception, would cause
852 // CompleteUnitGraph to add an edge from head to the tail:
853 List possibleThrowers = new ArrayList (exceptional.getSuccsOf(head));
854         possibleThrowers.remove(tail); // This method wouldn't have been
855 possibleThrowers.remove(head); // called if tail was not in
856 // g.getSuccsOf(head).
857
858         // We need to screen out Traps that catch exceptions from
859 // head itself, since they should be in both CompleteUnitGraph
860 // and TrapUnitGraph.
861 List headsCatchers = new ArrayList ();
862         for (Iterator it = exceptional.getExceptionDests(head).iterator();
863          it.hasNext(); ) {
864         ExceptionDest dest = (ExceptionDest) it.next();
865         headsCatchers.add(dest.getTrap());
866         }
867
868         // Now ensure that one of the possibleThrowers might throw
869 // an exception caught by one of tail's Traps,
870 // screening out combinations where possibleThrower is the
871 // first trapped Unit, if screenFirstTrappedUnit is true.
872 for (Iterator throwerIt = possibleThrowers.iterator();
873          throwerIt.hasNext(); ) {
874         Unit thrower = (Unit) throwerIt.next();
875         Collection dests = exceptional.getExceptionDests(thrower);
876         for (Iterator destIt = dests.iterator(); destIt.hasNext(); ) {
877             ExceptionDest dest = (ExceptionDest) destIt.next();
878             Trap trap = dest.getTrap();
879             if (tailsTraps.contains(trap)) {
880             if (headsCatchers.contains(trap)) {
881                 throw new RuntimeException ("trapsReachedViaEdge(): somehow there is no TrapUnitGraph edge from " + head + " to " + tail + " even though the former throws an exception caught by the latter!");
882             } else if ((! predOfTrappedThrowerScreensFirstTrappedUnit) ||
883                    (thrower != trap.getBeginUnit())) {
884                 return true;
885             }
886             }
887         }
888         }
889         return false;
890     }
891
892
893     /**
894      * Utility method that returns all the {@link Trap}s whose
895      * handlers begin with a particular {@link Unit}.
896      *
897      * @param handler the handler {@link Unit} whose {@link Trap}s are
898      * to be returned.
899      * @return a {@link List} of {@link Trap}s with <code>handler</code>
900      * as their handler's first {@link Unit}. The list may be empty.
901      */
902     protected List returnHandlersTraps(Unit handler) {
903         Body body = exceptional.getBody();
904         List result = null;
905         for (Iterator it = body.getTraps().iterator(); it.hasNext(); ) {
906         Trap trap = (Trap) it.next();
907         if (trap.getHandlerUnit() == handler) {
908             if (result == null) {
909             result = new ArrayList ();
910             }
911             result.add(trap);
912         }
913         }
914         if (result == null) {
915         result = Collections.EMPTY_LIST;
916         }
917         return result;
918     }
919     }
920
921     /**
922      * Class for comparing an {@link ExceptionalUnitGraph} to a {@link
923      * ClassicCompleteUnitGraph} . Since {@link
924      * ClassicCompleteUnitGraph} is a subclass of {@link
925      * TrapUnitGraph}, this class makes only minor adjustments to its
926      * parent.
927      */
928     class ExceptionalToClassicCompleteUnitGraphComparer
929     extends ExceptionalToTrapUnitGraphComparer {
930
931     ExceptionalToClassicCompleteUnitGraphComparer(ExceptionalUnitGraph exceptional,
932                               ClassicCompleteUnitGraph trap,
933                               boolean omitExceptingUnitEdges) {
934         super(exceptional, trap, omitExceptingUnitEdges);
935         this.predOfTrappedThrowerScreensFirstTrappedUnit = true;
936     }
937
938     protected boolean cannotReallyThrowTo(Unit head, Unit tail) {
939         if (Options.v().verbose())
940         G.v().out.println("ExceptionalToClassicCompleteUnitGraphComparer.cannotReallyThrowTo() called.");
941         if (super.cannotReallyThrowTo(head, tail)) {
942         return true;
943         } else {
944         // A ClassicCompleteUnitGraph will consider the predecessors
945 // of the first trapped Unit as predecessors of the Trap's
946 // handler.
947 List headsSuccs = exceptional.getSuccsOf(head);
948         List tailsTraps = returnHandlersTraps(tail);
949         for (Iterator it = tailsTraps.iterator(); it.hasNext(); ) {
950             Trap tailsTrap = (Trap) it.next();
951             Unit tailsFirstTrappedUnit = tailsTrap.getBeginUnit();
952             if (headsSuccs.contains(tailsFirstTrappedUnit)) {
953             Collection succsDests = exceptional.getExceptionDests(tailsFirstTrappedUnit);
954             if ((! destCollectionIncludes(succsDests, tailsTrap)) ||
955                 (! CompleteUnitGraph.mightHaveSideEffects(tailsFirstTrappedUnit))) {
956                 return true;
957             }
958             }
959         }
960         return false;
961         }
962     }
963     }
964
965
966     /**
967      * Class for Comparing a {@link BriefBlockGraph}, {@link
968      * ArrayRefBlockGraph}, or {@link ZonedBlockGraph} to an {@link
969      * AltBriefBlockGraph}, {@link AltArrayRefBlockGraph}, or {@link
970      * AltZonedBlockGraph}, respectively. The two should differ only
971      * in that the <tt>Alt</tt> variants have empty tail lists.
972      */
973     class BlockToAltBlockGraphComparer implements TypedGraphComparer {
974     DirectedGraph reg; // The regular BlockGraph.
975 DirectedGraph alt; // The Alt BlockGraph.
976
977     BlockToAltBlockGraphComparer(DirectedGraph reg, DirectedGraph alt) {
978         this.reg = reg;
979         this.alt = alt;
980     }
981
982     public boolean onlyExpectedDiffs() {
983         if (reg.size() != alt.size()) {
984         return false;
985         }
986         if (! equivLists(reg.getHeads(), alt.getHeads())) {
987         return false;
988         }
989         if (alt.getTails().size() != 0) {
990         return false;
991         }
992         return equivPredsAndSuccs();
993     }
994     }
995
996
997     /**
998      * A utility method for determining if a {@link Collection}
999      * of {@link CompleteUnitGraph#ExceptionDest} contains
1000     * one which leads to a specified {@link Trap}.
1001     *
1002     * @param dests the {@link Collection} of {@link
1003     * CompleteUnitGraph#ExceptionDest}s to search.
1004     *
1005     * @param trap the {@link Trap} to search for.
1006     *
1007     * @return <tt>true</tt> if <tt>dests</tt> contains
1008     * <tt>trap</tt> as a destination, false otherwise.
1009     */
1010    private static boolean destCollectionIncludes(Collection dests, Trap trap) {
1011    for (Iterator destIt = dests.iterator(); destIt.hasNext(); ) {
1012        ExceptionDest dest = (ExceptionDest) destIt.next();
1013        if (dest.getTrap() == trap) {
1014        return true;
1015        }
1016    }
1017    return false;
1018    }
1019        
1020    private final static String diffMarker = " ***";
1021
1022
1023    /**
1024     * Utility method to return the {@link Body} associated with a
1025     * {@link DirectedGraph}, if there is one.
1026     *
1027     * @param g the graph for which to return a {@link Body}.
1028     *
1029     * @return the {@link Body} represented by <tt>g</tt>, if <tt>g</tt>
1030     * is a control flow graph, or <tt>null</tt> if <tt>g</tt> is not a
1031     * control flow graph.
1032     */
1033    private static Body getGraphsBody(DirectedGraph g) {
1034    Body result = null;
1035    if (g instanceof UnitGraph) {
1036        result = ((UnitGraph) g).getBody();
1037    } else if (g instanceof BlockGraph) {
1038        result = ((BlockGraph) g).getBody();
1039    }
1040    return result;
1041    }
1042
1043
1044    /**
1045     * Utility method to return a short string label identifying a graph.
1046     *
1047     * @param g the graph for which to return a label.
1048     *
1049     * @return the method signature associated with <tt>g</tt>, if <tt>g</tt>
1050     * is a control flow graph, or an arbitrary identifying string if
1051     * <tt>g</tt> is not a control flow graph.
1052     */
1053    private static String graphToStringLabel(DirectedGraph g) {
1054    StringBuffer result = new StringBuffer (g.getClass().getName());
1055    Body b = getGraphsBody(g);
1056    if (b != null) {
1057        result.append('(');
1058        result.append(b.getMethod().getSignature());
1059        result.append(')');
1060    }
1061    return b.toString();
1062    }
1063
1064
1065    /**
1066     * Utility method that returns a {@link LabeledUnitPrinter} for printing
1067     * the {@link Unit}s in graph.
1068     *
1069     * @param g the graph for which to return a {@link LabeledUnitPrinter}.
1070     * @return A {@link LabeledUnitPrinter} for printing the {@link Unit}s in
1071     * <tt>g</tt> if <tt>g</tt> is a control flow graph. Returns
1072     * <tt>null</tt> if <tt>g</tt> is not a control flow graph.
1073     */
1074    private static LabeledUnitPrinter makeUnitPrinter(DirectedGraph g) {
1075    Body b = getGraphsBody(g);
1076    if (b == null) {
1077        return null;
1078    } else {
1079        BriefUnitPrinter printer = new BriefUnitPrinter(b);
1080        printer.noIndent();
1081        return printer;
1082    }
1083    }
1084
1085
1086    /**
1087     * Utility method to return a {@link String} representation of a
1088     * graph node.
1089     *
1090     * @param node an {@link Object} representing a node in a
1091     * {@link DirectedGraph}.
1092     *
1093     * @param printer either a {@link LabeledUnitPrinter} for printing the
1094     * {@link Unit}s in the graph represented by <tt>node</tt>'s
1095     * graph, if node is part of a control flow graph, or <tt>null</tt>, if
1096     * <tt>node</tt> is not part of a control flow graph.
1097     *
1098     * @return a {@link String} representation of <tt>node</tt>.
1099     */
1100    private static String nodeToString(Object node,
1101                       LabeledUnitPrinter printer) {
1102    String result = null;
1103    if (printer == null) {
1104        result = node.toString();
1105    } else if (node instanceof Unit) {
1106        ((Unit) node).toString(printer);
1107        result = printer.toString();
1108    } else if (node instanceof Block) {
1109        Block b = (Block) node;
1110        StringBuffer buffer = new StringBuffer ();
1111        Iterator units = ((Block) node).iterator();
1112        while (units.hasNext()) {
1113        Unit unit = (Unit) units.next();
1114        String targetLabel = (String ) printer.labels().get(unit);
1115        if (targetLabel != null) {
1116            buffer.append(targetLabel)
1117            .append(": ");
1118        }
1119        unit.toString(printer);
1120        buffer.append(printer.toString()).append("; ");
1121      }
1122      result = buffer.toString();
1123    }
1124    return result;
1125    }
1126
1127
1128    /**
1129     * A utility method for reporting the differences between two lists
1130     * of graph nodes. The lists are usually the result of calling
1131     * <tt>getHeads()</tt>, <tt>getTails()</tt>, <tt>getSuccsOf()</tt>
1132     * or <tt>getPredsOf()</tt> on each of two graphs being compared.
1133     *
1134     * @param buffer a {@link StringBuffer} to which to append the
1135     * description of differences.
1136     *
1137     * @param printer1 a {@link LabeledUnitPrinter} to be used to format
1138     * any {@link Unit}s found in <tt>list1</tt>.
1139     *
1140     * @param printer2 a {@link LabeledUnitPrinter} to be used to format
1141     * any {@link Unit}s found in <tt>list2</tt>.
1142     *
1143     * @param label a string characterizing these lists.
1144     *
1145     * @param list1 the list from the first graph, or <tt>null</tt> if
1146     * this list is missing in the first graph.
1147     *
1148     * @param list2 the list from the second graph, or <tt>null</tt> if
1149     * this list is missing in the second graph.
1150     */
1151    private void diffList(StringBuffer buffer,
1152              LabeledUnitPrinter printer1,
1153              LabeledUnitPrinter printer2,
1154              String label, List list1, List list2) {
1155    if (! equivLists(list1, list2)) {
1156        buffer.append("*********\n");
1157        if (list1 == null) {
1158        buffer.append("+ ");
1159        list1 = Collections.EMPTY_LIST;
1160        } else if (list2 == null) {
1161        buffer.append("- ");
1162        list2 = Collections.EMPTY_LIST;
1163        } else {
1164        buffer.append(" ");
1165        }
1166        buffer.append(label)
1167        .append(":\n");
1168        for (Iterator it = list1.iterator(); it.hasNext(); ) {
1169        Object list1Node = it.next();
1170        Object list2Node = equivalences.getEquiv(list1Node);
1171        if (list2.contains(list2Node)) {
1172            buffer.append(" ");
1173        } else {
1174            buffer.append("- ");
1175        }
1176        buffer.append(nodeToString(list1Node, printer1)).append("\n");
1177        }
1178        for (Iterator it = list2.iterator(); it.hasNext(); ) {
1179        Object list2Node = it.next();
1180        Object list1Node = equivalences.getEquiv(list2Node);
1181        if (! list1.contains(list1Node)) {
1182            buffer.append("+ ")
1183            .append(nodeToString(list2Node,printer2))
1184            .append("\n");
1185        }
1186        }
1187        buffer.append("---------\n");
1188    }
1189
1190    }
1191
1192
1193    /**
1194     * Utility method that determines if two lists of nodes are equivalent.
1195     *
1196     * @param list1 The first list of nodes.
1197     * @param list2 The second list of nodes.
1198     * @return <tt>true</tt> if the equivalent of each node in <tt>list1</tt>
1199     * is found in <tt>list2</tt>, and vice versa.
1200     */
1201    private boolean equivLists(List list1, List list2) {
1202    if (list1 == null) {
1203        return (list2 == null);
1204    } else if (list2 == null) {
1205        return false;
1206    }
1207
1208    if (list1.size() != list2.size()) {
1209        return false;
1210    }
1211
1212    for (Iterator i = list1.iterator(); i.hasNext(); ) {
1213        if (! list2.contains(equivalences.getEquiv(i.next()))) {
1214        return false;
1215        }
1216    }
1217
1218    // Since getEquiv() should be symmetric, and we've confirmed that
1219 // the lists are the same size, the next loop shouldn't really
1220 // be necessary. But just in case something is fouled up, we
1221 // include this loop as an assertion check.
1222 for (Iterator i = list2.iterator(); i.hasNext(); ) {
1223        if (! list1.contains(equivalences.getEquiv(i.next()))) {
1224        throw new IllegalArgumentException ("equivLists: " +
1225                           list2.toString() +
1226                           " contains all the equivalents of " +
1227                           list1.toString() +
1228                           ", but the reverse is not true.");
1229        }
1230    }
1231    return true;
1232    }
1233}
1234

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags