KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > annotation > purity > DirectedCallGraph


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2005 Antoine Mine
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  * Implementation of the paper "A Combined Pointer and Purity Analysis for
22  * Java Programs" by Alexandru Salcianu and Martin Rinard, within the
23  * Soot Optimization Framework.
24  *
25  * by Antoine Mine, 2005/01/24
26  */
27
28 package soot.jimple.toolkits.annotation.purity;
29 import java.util.*;
30 import soot.*;
31 import soot.util.*;
32 import soot.jimple.*;
33 import soot.jimple.toolkits.callgraph.*;
34 import soot.toolkits.graph.*;
35
36 /**
37  * Builds a DirectedGraph from a CallGraph and SootMethodFilter.
38  *
39  * This is used in AbstractInterproceduralAnalysis to construct a reverse
40  * pseudo topological order on which to iterate.
41  * You can specify a SootMethodFilter to trim the graph by cutting
42  * call edges strarting
43  *
44  * Methods filtered-out by the SootMethodFilter will not appear in the
45  * DirectedGraph!
46  */
47 public class DirectedCallGraph implements DirectedGraph {
48
49     protected Set nodes;
50     protected Map succ;
51     protected Map pred;
52     protected List heads;
53     protected List tails;
54     protected int size;
55
56     /**
57      * The constructor does all the work here.
58      * After constructed, you can safely use all interface methods.
59      * Moreover, these methods should perform very fastly...
60      *
61      * The DirectedGraph will only contain methods in call paths from a method
62      * in head and comprising only methods wanted by filter.
63      * Moreover, only concrete methods are put in the graph...
64      *
65      * @param heads is a List of SootMethod
66      */
67     public DirectedCallGraph(CallGraph cg,
68                  SootMethodFilter filter,
69                  Iterator heads,
70                  boolean verbose)
71     {
72     // filter heads by filter
73 List filteredHeads = new LinkedList();
74     while (heads.hasNext()) {
75         SootMethod m = (SootMethod) heads.next();
76         if (m.isConcrete() && filter.want(m)) filteredHeads.add(m);
77     }
78
79     this.nodes = new HashSet(filteredHeads);
80     
81     MultiMap s = new HashMultiMap();
82     MultiMap p = new HashMultiMap();
83
84     // simple breadth-first visit
85 Set remain = new HashSet(filteredHeads);
86     int nb = 0;
87     if (verbose) G.v().out.println("[AM] dumping method dependencies");
88     while (!remain.isEmpty()) {
89         Set newRemain = new HashSet();
90         Iterator it = remain.iterator();
91         while (it.hasNext()) {
92         SootMethod m = (SootMethod)it.next();
93         Iterator itt = cg.edgesOutOf(m);
94         if (verbose)
95             G.v().out.println(" |- "+m.toString()+" calls");
96         while (itt.hasNext()) {
97             Edge edge = (Edge)itt.next();
98             SootMethod mm = edge.tgt();
99             boolean keep = mm.isConcrete() && filter.want(mm);
100             if (verbose)
101             G.v().out.println(" | |- "+mm.toString()+
102                       (keep?"":" (filtered out)"));
103             if (keep) {
104             if (this.nodes.add(mm)) newRemain.add(mm);
105             s.put(m,mm);
106             p.put(mm,m);
107             }
108         }
109         nb++;
110         }
111         remain = newRemain;
112     }
113     G.v().out.println("[AM] number of methods to be analysed: "+nb);
114
115     // MultiMap -> Map of List
116 this.succ = new HashMap();
117     this.pred = new HashMap();
118     this.tails = new LinkedList();
119     this.heads = new LinkedList();
120     Iterator it = this.nodes.iterator();
121     while (it.hasNext()) {
122         Object JavaDoc x = it.next();
123         Set ss = s.get(x);
124         Set pp = p.get(x);
125         this.succ.put(x, new LinkedList(ss));
126         this.pred.put(x, new LinkedList(pp));
127         if (ss.isEmpty()) this.tails.add(x);
128         if (pp.isEmpty()) this.heads.add(x);
129     }
130
131     this.size = this.nodes.size();
132     }
133
134     /** You get a List of SootMethod. */
135     public List getHeads() { return heads; }
136
137     /** You get a List of SootMethod. */
138     public List getTails() { return tails; }
139
140     /** You get an Iterator on SootMethod. */
141     public Iterator iterator() { return nodes.iterator(); }
142
143     public int size() { return size; }
144     
145     /** You get a List of SootMethod. */
146     public List getSuccsOf(Object JavaDoc s) { return (List)succ.get(s); }
147
148     /** You get a List of SootMethod. */
149     public List getPredsOf(Object JavaDoc s) { return (List)pred.get(s); }
150 }
151
Popular Tags