|
1
19
20 package soot.dava.toolkits.base.finders;
21
22 import soot.*;
23 import java.util.*;
24 import soot.dava.*;
25 import soot.util.*;
26 import soot.jimple.*;
27 import soot.jimple.internal.*;
28 import soot.dava.internal.asg.*;
29 import soot.dava.internal.SET.*;
30 import soot.dava.internal.AST.*;
31
32 public class SwitchFinder implements FactFinder
33 {
34 public SwitchFinder( Singletons.Global g ) {}
35 public static SwitchFinder v() { return G.v().soot_dava_toolkits_base_finders_SwitchFinder(); }
36
37 private IterableSet junkBody;
38 private HashSet targetSet;
39 private LinkedList targetList, snTargetList, tSuccList;
40 private HashMap index2target, tSucc2indexSet, tSucc2target, tSucc2Body;
41
42 public void find( DavaBody davaBody, AugmentedStmtGraph asg, SETNode SET) throws RetriggerAnalysisException
43 {
44 Dava.v().log( "SwitchFinder::find()");
45
46 final String  defaultStr = "default";
47
48 Iterator asgit = asg.iterator();
49 while (asgit.hasNext()) {
50 AugmentedStmt as = (AugmentedStmt) asgit.next();
51
52 Stmt s = as.get_Stmt();
53
54 if (((s instanceof TableSwitchStmt) == false) && ((s instanceof LookupSwitchStmt) == false))
55 continue;
56
57
58 Value key = null;
59
60 junkBody = new IterableSet();
61 targetSet = new HashSet();
62
63 targetList = new LinkedList();
64 snTargetList = new LinkedList();
65 tSuccList = new LinkedList();
66
67 index2target = new HashMap();
68 tSucc2indexSet = new HashMap();
69 tSucc2target = new HashMap();
70 tSucc2Body = new HashMap();
71
72 if (s instanceof TableSwitchStmt) {
73 TableSwitchStmt tss = (TableSwitchStmt) s;
74
75 int target_count = tss.getHighIndex() - tss.getLowIndex() + 1;
76 for (int i=0; i<target_count; i++)
77 build_Bindings( as, new Integer (i + tss.getLowIndex()), asg.get_AugStmt( (Stmt) tss.getTarget( i)));
78
79 build_Bindings( as, defaultStr, asg.get_AugStmt( (Stmt) tss.getDefaultTarget()));
80 key = tss.getKey();
81 }
82
83 else if (s instanceof LookupSwitchStmt) {
84 LookupSwitchStmt lss = (LookupSwitchStmt) s;
85
86 int target_count = lss.getTargetCount();
87 for (int i=0; i<target_count; i++)
88 build_Bindings( as, new Integer ( lss.getLookupValue( i)), asg.get_AugStmt( (Stmt) lss.getTarget( i)));
89
90 build_Bindings( as, defaultStr, asg.get_AugStmt( (Stmt) lss.getDefaultTarget()));
91 key = lss.getKey();
92 }
93
94 Iterator tsit = tSuccList.iterator();
95 while (tsit.hasNext()) {
96 AugmentedStmt tSucc = (AugmentedStmt) tsit.next();
97 AugmentedStmt target = (AugmentedStmt) tSucc2target.get( tSucc);
98
99 snTargetList.addLast( new SwitchNode( target, (TreeSet) tSucc2indexSet.get( tSucc), (IterableSet) tSucc2Body.get( tSucc)));
100 }
101
102 TreeSet
103 targetHeads = new TreeSet(),
104 killBodies = new TreeSet();
105
106 {
108 asg.calculate_Reachability( targetList, targetSet, as);
109
110 SwitchNodeGraph sng = new SwitchNodeGraph( snTargetList);
111
112 killBodies.addAll( snTargetList);
113 snTargetList = new LinkedList();
114
115 LinkedList worklist = new LinkedList();
116 worklist.addAll( sng.getHeads());
117
118 while (worklist.isEmpty() == false) {
119 SwitchNode sn = (SwitchNode) worklist.removeFirst();
120
121 snTargetList.addLast( sn);
122 killBodies.remove( sn);
123
124 SwitchNode champ = null;
125 Iterator sit = sn.get_Succs().iterator();
126
127 while (sit.hasNext()) {
128 SwitchNode ssn = (SwitchNode) sit.next();
129
130 if ((champ == null) || (champ.get_Score() < ssn.get_Score()))
131 champ = ssn;
132 }
133
134 if ((champ != null) && (champ.get_Score() > 0))
135 worklist.addLast( champ);
136
137 }
138
139 Iterator kit = killBodies.iterator();
140 while (kit.hasNext()) {
141 SwitchNode sn = (SwitchNode) kit.next();
142
143 IterableSet snBody = sn.get_Body();
144 snBody.clear();
145 snBody.add( sn.get_AugStmt());
146 }
147
148 sng = new SwitchNodeGraph( snTargetList);
149 targetHeads.addAll( sng.getHeads());
150 }
151
152 LinkedList switchNodeList = new LinkedList();
153
154 {
156 while ((targetHeads.isEmpty() == false) || (killBodies.isEmpty() == false)) {
157
158 if ((targetHeads.isEmpty()) ||
159 ((targetHeads.isEmpty() == false) && (killBodies.isEmpty() == false) && (((SwitchNode) targetHeads.first()).compareTo( killBodies.first()) > 0))) {
160
161 SwitchNode nextNode = (SwitchNode) killBodies.first();
162 killBodies.remove( nextNode);
163
164 switchNodeList.addLast( nextNode);
165 }
166 else {
167
168 SwitchNode nextNode = (SwitchNode) targetHeads.first();
169 targetHeads.remove( nextNode);
170
171 while (true) {
172 switchNodeList.addLast( nextNode);
173
174 if (nextNode.get_Succs().isEmpty())
175 break;
176
177 nextNode = (SwitchNode) nextNode.get_Succs().get(0);
178 }
179 }
180 }
181 }
182
183 IterableSet body = new IterableSet();
184 body.add( as);
185 Iterator snlit = switchNodeList.iterator();
186 while (snlit.hasNext()) {
187 SwitchNode sn = (SwitchNode) snlit.next();
188
189 body.addAll( sn.get_Body());
190 if (sn.get_IndexSet().contains( defaultStr)) {
191 sn.get_IndexSet().clear();
192 sn.get_IndexSet().add( defaultStr);
193 }
194 }
195
196 body.addAll( junkBody);
197
198 Iterator enlit = davaBody.get_ExceptionFacts().iterator();
199 while (enlit.hasNext()) {
200 ExceptionNode en = (ExceptionNode) enlit.next();
201 IterableSet tryBody = en.get_TryBody();
202
203 if (tryBody.contains( as)) {
204 Iterator fbit = body.snapshotIterator();
205
206 while (fbit.hasNext()) {
207 AugmentedStmt fbas = (AugmentedStmt) fbit.next();
208
209 if (tryBody.contains( fbas) == false) {
210 body.remove( fbas);
211
212 snlit = switchNodeList.iterator();
213 while (snlit.hasNext()) {
214 IterableSet switchBody = ((SwitchNode) snlit.next()).get_Body();
215
216 if (switchBody.contains( fbas)) {
217 switchBody.remove( fbas);
218 break;
219 }
220 }
221 }
222 }
223 }
224 }
225
226 SET.nest( new SETSwitchNode( as, key, body, switchNodeList, junkBody));
227 }
228 }
229
230 private IterableSet find_SubBody( AugmentedStmt switchAS, AugmentedStmt branchS)
231 {
232 IterableSet subBody = new IterableSet();
233 LinkedList worklist = new LinkedList();
234
235 subBody.add( branchS);
236 branchS = (AugmentedStmt) branchS.bsuccs.get(0);
237
238 if (branchS.get_Dominators().contains( switchAS)) {
239 worklist.addLast( branchS);
240 subBody.add( branchS);
241 }
242
243 while (worklist.isEmpty() == false) {
244 AugmentedStmt as = (AugmentedStmt) worklist.removeFirst();
245
246 Iterator sit = as.csuccs.iterator();
247 while (sit.hasNext()) {
248 AugmentedStmt sas = (AugmentedStmt) sit.next();
249
250 if ((subBody.contains( sas) == false) && (sas.get_Dominators().contains( branchS))) {
251 worklist.addLast( sas);
252 subBody.add( sas);
253 }
254 }
255 }
256
257 return subBody;
258 }
259
260 private void build_Bindings( AugmentedStmt swAs, Object index, AugmentedStmt target)
261 {
262 AugmentedStmt tSucc = (AugmentedStmt) target.bsuccs.get(0);
263
264 if (targetSet.add( tSucc))
265 targetList.addLast( tSucc);
266
267 index2target.put( index, target);
268
269 TreeSet indices = null;
270 if ((indices = (TreeSet) tSucc2indexSet.get( tSucc)) == null) {
271 indices = new TreeSet( new IndexComparator());
272 tSucc2indexSet.put( tSucc, indices);
273 tSucc2target.put( tSucc, target);
274 tSucc2Body.put( tSucc, find_SubBody( swAs, target));
275 tSuccList.add( tSucc);
276 }
277 else {
278 junkBody.add( target);
279
280
282 Iterator sit = target.bsuccs.iterator();
283 while (sit.hasNext())
284 ((AugmentedStmt) sit.next()).bpreds.remove( target);
285
286 sit = target.csuccs.iterator();
287 while (sit.hasNext())
288 ((AugmentedStmt) sit.next()).cpreds.remove( target);
289
290 target.bsuccs.clear();
291 target.csuccs.clear();
292 }
293
294 indices.add( index);
295 }
296 }
297 |
Popular Tags |
Java API By Example, From Geeks To Geeks.