Java > Open Source Codes > soot > dava > toolkits > base > finders > SynchronizedBlockFinder


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2003 Jerome Miecznikowski
3  * Copyright (C) 2004-20055 Nomair A. Naeem
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the
17  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18  * Boston, MA 02111-1307, USA.
19  */
20
21 package soot.dava.toolkits.base.finders;
22
23 import soot.*;
24 import soot.dava.*;
25 import soot.util.*;
26 import java.util.*;
27 import soot.jimple.*;
28 import soot.toolkits.graph.*;
29 import soot.dava.internal.asg.*;
30 import soot.dava.internal.SET.*;
31 import soot.dava.internal.AST.*;
32
33 public class SynchronizedBlockFinder implements FactFinder
34 {
35     public SynchronizedBlockFinder( Singletons.Global g ) {}
36     public static SynchronizedBlockFinder v() { return G.v().soot_dava_toolkits_base_finders_SynchronizedBlockFinder(); }
37
38     private HashMap as2ml;
39     private DavaBody davaBody;
40
41     /*
42       Nomair A Naeem 08-FEB-2005
43       monitorLocalSet contains all the locals that are used in monitors
44       monitorEnterSet contains all enterMonitorStmts Statements
45     */
46     private IterableSet monitorLocalSet, monitorEnterSet;
47
48     private Integer WHITE = new Integer (0);//never visited in DFS
49 private Integer GRAY = new Integer (1);//visited but not finished
50 private Integer BLACK = new Integer (2);//finished
51
52     private int UNKNOWN = -100000; // Note there are at most 65536 monitor exits in a method.
53 private Integer VARIABLE_INCR = new Integer (UNKNOWN);
54
55     private String THROWABLE = "java.lang.Throwable";
56
57
58     public void find( DavaBody body, AugmentedStmtGraph asg, SETNode SET) throws RetriggerAnalysisException
59     {
60     davaBody=body;
61     Dava.v().log( "SynchronizedBlockFinder::find()");
62
63     as2ml = new HashMap();
64
65     IterableSet synchronizedBlockFacts = body.get_SynchronizedBlockFacts();
66     synchronizedBlockFacts.clear();
67
68     set_MonitorLevels( asg);
69
70     Map as2synchSet = build_SynchSets();
71
72     IterableSet usedMonitors = new IterableSet();
73
74     AugmentedStmt previousStmt = null;
75
76     Iterator asgit = asg.iterator();
77     while (asgit.hasNext()) {
78         //going through all augmentedStmts
79
80         AugmentedStmt as = (AugmentedStmt) asgit.next();
81         if (as.get_Stmt() instanceof EnterMonitorStmt) {
82         //for each monitor enter stmt found
83
84         IterableSet synchSet = (IterableSet) as2synchSet.get( as);
85         if (synchSet != null) {
86             IterableSet synchBody = get_BodyApproximation( as, synchSet);
87             Value local = ((EnterMonitorStmt) as.get_Stmt()).getOp();
88             Value copiedLocal=null;
89             
90             /*
91              * Synch bug due to copy stmts
92              * r2 = r1
93              * enter monitor r1
94              * synch body
95              * exit monitor r2
96              * we need to realize that r1 and r2 are the same
97              * implemented as a hack, the correct approach is reaching copies
98              */
99             if(previousStmt != null){
100             Stmt previousS = previousStmt.get_Stmt();
101             if(previousS instanceof DefinitionStmt){
102                 DefinitionStmt previousDef = (DefinitionStmt)previousS;
103                 Value rightPrevious = previousDef.getRightOp();
104                 if(rightPrevious.toString().compareTo(local.toString())==0){
105                    copiedLocal = previousDef.getLeftOp();
106                    }
107             }
108             }
109
110
111             Integer level = (Integer ) ((HashMap) as2ml.get( as)).get( local);
112             Iterator enit = body.get_ExceptionFacts().iterator();
113
114             //going through all exception nodes in the DavaBody
115 boolean done=false;
116             IterableSet origSynchBody=synchBody;
117             while (enit.hasNext()) {
118             ExceptionNode en = (ExceptionNode) enit.next();
119             synchBody=(IterableSet)origSynchBody.clone();
120             //see if the two bodies match exactly
121
122             if (verify_CatchBody( en, synchBody, local,copiedLocal)) {
123                 if (SET.nest( new SETSynchronizedBlockNode( en, local))) {
124                 done=true;
125                 //System.out.println("synch block created");
126 Iterator ssit = synchSet.iterator();
127                 while (ssit.hasNext()) {
128                     AugmentedStmt ssas = (AugmentedStmt) ssit.next();
129                     Stmt sss = ssas.get_Stmt();
130                     
131                     /*
132                      * Jeromes Implementation: changed because of copy stmt bug
133                      *
134                      * if ((sss instanceof MonitorStmt) && (((MonitorStmt) sss).getOp() == local) &&
135                     (((Integer) ((HashMap) as2ml.get( ssas)).get( local)).equals( level)) &&
136                     (usedMonitors.contains( ssas) == false)){
137                     */
138                     if (sss instanceof MonitorStmt){
139                     if( (((MonitorStmt) sss).getOp() == local) &&
140                         (((Integer ) ((HashMap) as2ml.get( ssas)).get( local)).equals( level)) &&
141                         (usedMonitors.contains( ssas) == false) ){
142                     
143                         usedMonitors.add( ssas);
144                     }
145                     else{
146                         if( (((MonitorStmt) sss).getOp() == copiedLocal) &&
147                         (usedMonitors.contains( ssas) == false) ){
148                         //note we dont check levels in this case
149 usedMonitors.add( ssas);
150                         }
151                     }
152                     }
153                 }
154                 synchronizedBlockFacts.add( en);
155                 }
156                 break;
157             }
158             else{
159                 //throw new RuntimeException("Could not verify approximated Synchronized body");
160 }
161             }
162             if(!done)
163             throw new RuntimeException ("Could not verify approximated Synchronized body");
164         }//non null synch set for this enter monitor stmt
165 }//if the augmented stmt was a enter monitor stmt
166 previousStmt=as;
167     }//going through all augmented stmts
168
169     IterableSet monitorFacts = body.get_MonitorFacts();
170     monitorFacts.clear();
171
172     asgit = asg.iterator();
173     while (asgit.hasNext()) {
174         AugmentedStmt as = (AugmentedStmt) asgit.next();
175
176         if ((as.get_Stmt() instanceof MonitorStmt) && (usedMonitors.contains( as) == false)){
177         monitorFacts.add( as);
178         }
179     }
180     }
181
182
183
184
185
186
187     /*
188      * as2locals: contains all locals which have unknown level for this augmented stmt
189      * viAugStmts: contains all augmented stmts which have some unknown level local in them
190      */
191
192     private void find_VariableIncreasing( AugmentedStmtGraph asg, HashMap local2level_template,
193                       LinkedList viAugStmts, HashMap as2locals) {
194         StronglyConnectedComponents scc = new StronglyConnectedComponents(asg);
195     IterableSet viSeeds = new IterableSet();
196     HashMap
197         as2color = new HashMap(),
198         as2rml = new HashMap();
199
200     //as2rml contains each augmented stmt as key with a local2Level mapping as value
201 Iterator asgit = asg.iterator();
202     while (asgit.hasNext()){
203         as2rml.put( asgit.next(), local2level_template.clone());
204     }
205
206
207     // loop through all the strongly connected components in the graph
208 Iterator sccit = scc.getComponents().iterator();
209     while (sccit.hasNext()) {
210         //componentList contains augmentedstmts belonging to a particular scc
211 List componentList = (List) sccit.next();
212
213         // skip trivial strongly connected components
214 if (componentList.size() < 2)
215         continue;
216
217         //component contains augmentedstmts belonging to a particular scc
218 IterableSet component = new IterableSet();
219         component.addAll( componentList);
220
221         //add to as2color each augstmt belonging to the component as the key and the color white as the value
222 Iterator cit = component.iterator();
223         while (cit.hasNext()){
224         as2color.put( cit.next(), WHITE);
225         }
226
227         // DFS and mark enough of the variable increasing points to get started.
228 AugmentedStmt seedStmt = (AugmentedStmt) component.getFirst();
229         //seedStmt contains the first stmt of the scc
230
231         
232         DFS_Scc( seedStmt, component, as2rml, as2color, seedStmt, viSeeds);
233         //viSeeds contain augmentedStmts which have unknown level since their level was less
234 //than that of their predecessors
235 }
236
237
238
239     //viSeeds contains all the augmentedStmts with unknown level in the method (for all scc)
240 IterableSet worklist = new IterableSet();
241     worklist.addAll( viSeeds);
242
243     // Propegate the variable increasing property.
244 while (worklist.isEmpty() == false) {
245         AugmentedStmt as = (AugmentedStmt) worklist.getFirst();
246         worklist.removeFirst();
247         HashMap local2level = (HashMap) as2rml.get( as);
248         
249         //get all sucessors of the viSeed
250 Iterator sit = as.csuccs.iterator();
251         while (sit.hasNext()) {
252         AugmentedStmt sas = (AugmentedStmt) sit.next();
253         HashMap slocal2level = (HashMap) as2rml.get( sas);
254
255         Iterator mlsit = monitorLocalSet.iterator();
256         while (mlsit.hasNext()) {
257             Value local = (Value) mlsit.next();
258
259             //if the level for a local is set to unknown and the level for the same local is not
260 //set to unknown in the successor set it and add it to the worklist
261 if ((local2level.get( local) == VARIABLE_INCR) && (slocal2level.get( local) != VARIABLE_INCR)) {
262             slocal2level.put( local, VARIABLE_INCR);
263             
264             if (worklist.contains( sas) == false)
265                 worklist.addLast( sas);
266             }
267         }
268         }
269     }
270     /*
271      * At the end of this the worklist is empty
272      * the unknown level of locals of an augmentedstmt present in the viSeed has been
273      * propagated through out the stmts reachable from that stmt
274      */
275
276     // Summarize the variable increasing information for the set_MonitorLevels() function.
277 asgit = asg.iterator();
278     while (asgit.hasNext()) {
279         AugmentedStmt as = (AugmentedStmt) asgit.next();
280         HashMap local2level = (HashMap) as2rml.get( as);
281
282         Iterator mlsit = monitorLocalSet.iterator();
283         while (mlsit.hasNext()) {
284         //for each local involved in monitor stmts
285 Value local = (Value) mlsit.next();
286         
287         if (local2level.get( local) == VARIABLE_INCR) {
288
289             /*
290               Nomair A. Naeem 08-FEB-2005
291               BUG IN CODE. The getLast method returns a NoSuchElementException if list is empty.
292               Protect this by checking isEmpty
293             */
294             if (!viAugStmts.isEmpty()){
295             if (viAugStmts.getLast() != as)
296                 viAugStmts.addLast( as);
297             }
298             else{
299             //System.out.println("List was empty added as");
300 viAugStmts.addLast(as);
301             }
302
303             LinkedList locals = null;
304
305             if ((locals = (LinkedList) as2locals.get( as)) == null) {
306             locals = new LinkedList();
307             as2locals.put( as, locals);
308             }
309             
310             locals.addLast( local);
311         }
312         }
313     }
314     }
315
316
317
318
319
320     /*
321      * Inputs:
322      * as: the seed stmt, i.e. the first statement of a strongly connected component
323      * component: the strongly connected stmt being processed
324      * as2rml: a hashmap which contains an augmentedstmt as key and a hashmap with local to level mapping as value
325      * as2color: maps each augmentedstmt of a scc to a color (white initially)
326      * viSeeds: variable increasing levels, initially empty
327      *
328      * Purpose: makes a traversal of the entire scc and
329      * increases the levels of locals when used in monitor enter
330      * decreases the levels of locals when leaving monitor
331      * if a successor has never been visited invoke same method on it with updated level information
332      * if a sucessor has been visited before and has a lower level than a seed
333      * the level of the sucessor is marked unknown and is added to the viSeeds list
334      *
335      */
336     private void DFS_Scc( AugmentedStmt as, IterableSet component, HashMap as2rml,
337               HashMap as2color, AugmentedStmt seedStmt, IterableSet viSeeds){
338     as2color.put( as, GRAY);
339
340     Stmt s = as.get_Stmt();
341     //get local to level mapping of the augmented stmt
342 HashMap local2level = (HashMap) as2rml.get( as);
343     
344     if (s instanceof MonitorStmt ) {
345         Value local = ((MonitorStmt) s).getOp();
346         
347         if (s instanceof EnterMonitorStmt){//its an enter hence increase level for this local
348 local2level.put( local, new Integer ( ((Integer ) local2level.get( local)).intValue() + 1));
349         }
350         else{//its an exit stmt hence reduce level
351 local2level.put( local, new Integer ( ((Integer ) local2level.get( local)).intValue() - 1));
352         }
353     }
354         
355     //get all successors of the augmented stmt
356 Iterator sit = as.csuccs.iterator();
357     //going through sucessors
358 while (sit.hasNext()) {
359         AugmentedStmt sas = (AugmentedStmt) sit.next();
360
361         if (component.contains( sas) == false)
362         continue;
363
364         //get the local2Level hashmap for the successor
365 HashMap slocal2level = (HashMap) as2rml.get( sas);
366         //get the color for the sucessor
367 Integer scolor = (Integer ) as2color.get( sas);
368
369         if (scolor.equals( WHITE)) {
370         //the augmented stmt hasnt been handled yet
371 Iterator mlsit = monitorLocalSet.iterator();
372         while (mlsit.hasNext()) {
373             //for all locals which are used in monitor stmts
374 Value local = (Value) mlsit.next();
375             /*
376              * update the sucessors hashtable with level values from the seed stmt
377              * The loca2Level is the hashmap of local-->level for the seed
378              * The sLocal2Level is the hashmap of local --> level for the successor of the seed
379              */
380             slocal2level.put( local, local2level.get( local));
381         }
382
383         //do recursive call on the sucessor
384 DFS_Scc( sas, component, as2rml, as2color, seedStmt, viSeeds);
385         }
386
387         else {
388         //if the augmented stmt has been visited before
389 Iterator mlsit = monitorLocalSet.iterator();
390         while (mlsit.hasNext()) {
391             Value local = (Value) mlsit.next();
392
393             if (((Integer ) slocal2level.get( local)).intValue() < ((Integer ) local2level.get( local)).intValue()) {
394             //if the sucessors value for the level of a local is less than that of the level of the seed
395 //make the level for this local to be unknown--> VARIABLE_INCR
396 slocal2level.put( local, VARIABLE_INCR);
397  
398             //add this to the viSeeds list
399 if (viSeeds.contains( sas) == false)
400                 viSeeds.add( sas);
401             }
402         }
403         }
404     }
405
406     //mark augmented stmt as done
407 as2color.put( as, BLACK);
408     }
409
410
411
412
413     /*
414      * Created a synch set for each enter monitor stmt.
415      * The synch set contains all sucessors of the monitor enter stmt which is dominated by the enter stmt
416      * and the level is greater or equal to that of the enter stmt
417      */
418     private Map build_SynchSets(){
419     HashMap as2synchSet = new HashMap();
420
421     Iterator mesit = monitorEnterSet.iterator();
422     monitorEnterLoop:
423     while (mesit.hasNext()) {
424         //going through monitor enter stmts
425 AugmentedStmt headAs = (AugmentedStmt) mesit.next();
426         Value local = ((EnterMonitorStmt) headAs.get_Stmt()).getOp();
427         IterableSet synchSet = new IterableSet();
428
429         //get the monitor level for the local uses in the enter stmt
430 int monitorLevel = ((Integer ) ((HashMap) as2ml.get( headAs)).get( local)).intValue();
431         IterableSet worklist = new IterableSet();
432         worklist.add( headAs);
433
434         while (worklist.isEmpty() == false) {
435         AugmentedStmt as = (AugmentedStmt) worklist.getFirst();
436         worklist.removeFirst();
437
438         Stmt s = as.get_Stmt();
439         if ((s instanceof DefinitionStmt) && (((DefinitionStmt) s).getLeftOp() == local))
440             continue monitorEnterLoop;
441
442         synchSet.add( as);
443
444         Iterator sit = as.csuccs.iterator();
445         while (sit.hasNext()) {
446             AugmentedStmt sas = (AugmentedStmt) sit.next();
447             //get the sucessors monitor level
448 int sml = ((Integer ) ((HashMap) as2ml.get( sas)).get( local)).intValue();
449
450             /* if the sucessor is dominated by the head stmt and the level is greater or equal to that
451                of the head and is not waiting to be analysed and is not in the synchSet.. then add it to worklist
452             */
453             if (sas.get_Dominators().contains( headAs) && (sml >= monitorLevel) &&
454             (worklist.contains( sas) == false) && (synchSet.contains( sas) == false))
455
456             worklist.addLast( sas);
457         }
458         }
459
460         as2synchSet.put( headAs, synchSet);
461     }
462     return as2synchSet;
463     }
464
465
466
467
468
469
470
471     /*
472      * MonitorLocalSet: contains all locals used in monitor enter statements
473      * MonitorEnterSet: contains all monitor enter statements
474      * as2ml : key is each augmented stmt of the augmented graph,
475      * value is a hashmap which contains a local as key and the level as value
476      */
477     private void set_MonitorLevels( AugmentedStmtGraph asg){
478     monitorLocalSet = new IterableSet();
479     monitorEnterSet = new IterableSet();
480
481     // Identify the locals that are used in monitor statements, and all the monitor enters.
482 Iterator asgit = asg.iterator();
483     while (asgit.hasNext()) {
484         AugmentedStmt as = (AugmentedStmt) asgit.next();
485         Stmt s = as.get_Stmt();
486         
487         if (s instanceof MonitorStmt) {
488         Value local = ((MonitorStmt) s).getOp();
489
490         //if the monitorLocalSet does not contain this local add it
491 if (monitorLocalSet.contains( local) == false)
492             monitorLocalSet.add( local);
493         
494         //add the monitor enter statement to the monitorEnter Set
495 if (s instanceof EnterMonitorStmt)
496             monitorEnterSet.add( as);
497         }
498     }
499     
500     // Set up a base monitor lock level of 0 for all monitor locals.
501 HashMap local2level_template = new HashMap();
502     Iterator mlsit = monitorLocalSet.iterator();
503     while (mlsit.hasNext()) {
504         //add the local as key and value 0 as value
505 local2level_template.put( mlsit.next(), new Integer ( 0));
506     }
507
508     // Give each statement the base monitor lock levels.
509 asgit = asg.iterator();
510     while (asgit.hasNext()){
511         //the augmented stmt is key and the whole hashMap with all the local-->value mapping is the key
512 as2ml.put( asgit.next(), local2level_template.clone());
513     }
514
515
516     LinkedList viAugStmts = new LinkedList();
517     HashMap incrAs2locals = new HashMap();
518     
519     // setup the variable increasing monitor levels
520 find_VariableIncreasing( asg, local2level_template, viAugStmts, incrAs2locals);
521     /*
522      * At this time the viAugStmts contains all augments Stmt which have some local that has unknown level
523      * the incrAs2locals contains a map of augmented stmt to a linkedlist which contains locals with unknown level
524      */
525
526
527
528     //going through all augmented stmts with some local with unknown level
529 Iterator viasit = viAugStmts.iterator();
530     while (viasit.hasNext()) {
531         AugmentedStmt vias = (AugmentedStmt) viasit.next();
532         HashMap local2level = (HashMap) as2ml.get( vias);
533
534         //getting the list of locals with unknown level for this augmented stmt
535 Iterator lit = ((LinkedList) incrAs2locals.get( vias)).iterator();
536         while (lit.hasNext()){
537         //marking the level for this local as unknown
538 local2level.put( lit.next(), VARIABLE_INCR);
539         }
540     }
541
542     IterableSet worklist = new IterableSet();
543     worklist.addAll( monitorEnterSet);
544
545     // Flow monitor lock levels.
546 while (worklist.isEmpty() == false) {
547         //going through all monitor enter stmts
548 AugmentedStmt as = (AugmentedStmt) worklist.getFirst();
549         worklist.removeFirst();
550
551         HashMap cur_local2level = (HashMap) as2ml.get( as);
552
553         Iterator pit = as.cpreds.iterator();
554         while (pit.hasNext()) {
555         //going through preds of an enter monitor stmt
556 AugmentedStmt pas = (AugmentedStmt) pit.next();
557         Stmt s = as.get_Stmt();
558
559         HashMap pred_local2level = (HashMap) as2ml.get( pas);
560
561         mlsit = monitorLocalSet.iterator();
562         while (mlsit.hasNext()) {
563             Value local = (Value) mlsit.next();
564             
565             int predLevel = ((Integer ) pred_local2level.get( local)).intValue();
566             Stmt ps = pas.get_Stmt();
567
568             if (predLevel == UNKNOWN) // Already marked as variable increasing.
569 continue;
570             
571             if (ps instanceof ExitMonitorStmt) {
572             
573             ExitMonitorStmt ems = (ExitMonitorStmt) ps;
574             /*
575              * if the predecessor stmt is a monitor exit and the local it exits is the same
576              * as this local and the predLevel is greater than 0 decrease the pred level
577              */
578             if ((ems.getOp() == local) && (predLevel > 0))
579                 predLevel--;
580             }
581
582             if (s instanceof EnterMonitorStmt) {
583             EnterMonitorStmt ems = (EnterMonitorStmt) s;
584             /*
585              * if the stmt is a monitor enter (which is true for the initial worklist)
586              * and the local it enters is the same
587              * as this local and the predLevel is greater or equal to 0 increase the pred level
588              */
589             if ((ems.getOp() == local) && (predLevel >= 0))
590                 predLevel++;
591             }
592
593             int curLevel = ((Integer ) cur_local2level.get( local)).intValue();
594
595             /*
596               if the pred level is greater than the current level update current level
597               add the sucessors of the stmt to the worklist
598             */
599             if (predLevel > curLevel) {
600             cur_local2level.put( local, new Integer ( predLevel));
601             
602             Iterator sit = as.csuccs.iterator();
603             while (sit.hasNext()) {
604                 Object so = sit.next();
605                 
606                 if (worklist.contains( so) == false)
607                 worklist.add( so);
608             }
609             }
610         }
611         }
612     }
613     }
614
615
616
617     /*
618      * If a stmt is removed from the synchBody then all other stmts
619      * which are dominated by this stmt should also be removed from the synchBody
620      */
621     private void removeOtherDominatedStmts(IterableSet synchBody, AugmentedStmt sas){
622     ArrayList toRemove = new ArrayList();
623
624     Iterator it = synchBody.iterator();
625     while(it.hasNext()){
626         AugmentedStmt as = (AugmentedStmt)it.next();
627         IterableSet doms = as.get_Dominators();
628         if(doms.contains(sas)){
629         //System.out.println("\n\nstmt:"+as+" is dominated by removed stmt"+sas);
630 toRemove.add(as);
631         }
632     }
633     
634     it = toRemove.iterator();
635     while(it.hasNext()){
636         AugmentedStmt as = (AugmentedStmt)it.next();
637         // System.out.println("Removed dominated stmt: "+as);
638 synchBody.remove(as);
639     }
640     }
641
642
643
644
645     private boolean verify_CatchBody( ExceptionNode en, IterableSet synchBody, Value monitorVariable,Value copiedLocal)
646     {
647     //System.out.println("starting verification");
648 {
649         /*
650          * synchBody is a likely superset of exception Node since the synchBody contains a goto stmt
651          * to the stmt right after the "to be created synch block" See if this is the case and remove
652          * the stmt
653          */
654
655         IterableSet tryBodySet = en.get_TryBody();
656         Iterator tempIt = tryBodySet.iterator();
657         AugmentedStmt tempas=null;
658
659         //to compute last stmt in a tryBody one should find the stmt whose sucessor is not in the tryBody
660 outer:
661         while(tempIt.hasNext()){
662         tempas = (AugmentedStmt)tempIt.next();
663
664
665         //get natural sucessors
666 Iterator succIt = tempas.bsuccs.iterator();
667         while(succIt.hasNext()){
668             AugmentedStmt succAS = (AugmentedStmt)succIt.next();
669             if(!tryBodySet.contains(succAS)){
670             //tempas has a sucessor which is not part of the trybody hence this is the last stmt
671 break outer;
672             }
673         }
674         //System.out.println(tempas);
675 }
676
677
678         //tempas contains the last augmentedStmt
679 if(tempas!=null){
680         Stmt temps = tempas.get_Stmt();
681         //System.out.println("last stmt in try body:"+((Unit)temps).toString());
682
683         //retrieving successors
684 Iterator sit = tempas.bsuccs.iterator();
685         while (sit.hasNext()) {
686             AugmentedStmt sas = (AugmentedStmt) sit.next();
687             //System.out.println("Removing: successor of last stmt:"+sas.get_Stmt());
688
689             //this is the stmt which is the successor of the try block which shouldnt be in the synchronized block
690 //remove the stmt if present in synchBody
691
692             synchBody.remove(sas);
693             //System.out.println("Here, removed: "+sas);
694 //should remove all other stmts in the synchBody which are dominated by this stmt
695 removeOtherDominatedStmts(synchBody,sas);
696         }
697         }
698     }
699
700
701     /*
702       In the abc created code when a synch body occurs within a try block
703       There is an error because the synchBody created has addition statements
704       regarding the catching of exception due to the outer try block
705       
706       Since these statements are not part of the synch body they should be removed
707     */
708     {
709          Iterator tempIt = en.get_TryBody().iterator();
710          while(tempIt.hasNext()){
711          AugmentedStmt as = (AugmentedStmt)tempIt.next();
712         if(as.get_Stmt() instanceof ExitMonitorStmt){
713             //System.out.println("All possible sucessors of as (CSUCCS):"+as.csuccs);
714 List csuccs = as.csuccs;
715
716              //remove the natural sucessors
717 csuccs.remove(as.bsuccs);
718              //now csuccs have the exception sucessors
719 //System.out.println("Exception sucessors of Exit (CSUCCS:"+csuccs);
720
721              Iterator succIt = csuccs.iterator();
722              while(succIt.hasNext()){
723              AugmentedStmt as1 = (AugmentedStmt)succIt.next();
724              if(as1.get_Stmt() instanceof GotoStmt){
725                  Unit target=((soot.jimple.internal.JGotoStmt)as1.get_Stmt()).getTarget();
726                  if(target instanceof DefinitionStmt){
727                  DefinitionStmt defStmt = (DefinitionStmt)target;
728                  
729                  /*
730                   * These are the caught exceptions (can be more than once if there
731                   * are multiple areas of protection Keep the one which is of type Throwable
732                   */
733                  
734                  Value asnFrom = defStmt.getRightOp();
735                  
736                  //if not a caught exception of type throwable remove from synch
737 if (! (asnFrom instanceof CaughtExceptionRef)){
738                      //System.out.println("REMOVING:"+defStmt+" since this is not a caughtexception def");
739 synchBody.remove(as1);
740                      //should remove all other stmts in the synchBody which are dominated by this stmt
741 removeOtherDominatedStmts(synchBody,as1);
742                  }
743                  else{
744                      Value leftOp = defStmt.getLeftOp();
745                      //System.out.println("the left op is:"+leftOp);
746
747                      /*
748                        Only keep this if it is of throwable type
749                      */
750                      HashSet params = new HashSet();
751                      params.addAll(davaBody.get_CaughtRefs());
752                      
753                      Iterator localIt = davaBody.getLocals().iterator();
754                      String typeName="";
755                      while (localIt.hasNext()) {
756                      Local local = (Local) localIt.next();
757                      if(local.toString().compareTo(leftOp.toString())==0){
758                          Type t = local.getType();
759                      
760                          typeName = t.toString();
761                          break;
762                      }
763                      }
764
765                      if(!( typeName.compareTo(THROWABLE)==0) ){
766                      //System.out.println("REMOVING:"+defStmt+ " since the caughtException not throwable type");
767 synchBody.remove(as1);
768                      //should remove all other stmts in the synchBody which are dominated by this stmt
769 removeOtherDominatedStmts(synchBody,as1);
770                      }
771                      else{
772                      //System.out.println("KEEPING"+defStmt);
773 //System.out.println((RefType)((CaughtExceptionRef) asnFrom).getType());
774 }
775                  }
776                  }
777                 else{
778                 //System.out.println("\n\nnot definition"+target);
779 //System.out.println("Removed"+as1);
780 synchBody.remove(as1);
781                 //System.out.println(as1.bsuccs.get(0));
782 synchBody.remove(as1.bsuccs.get(0));
783                 //should remove all other stmts in the synchBody which are dominated by this stmt
784 removeOtherDominatedStmts(synchBody,as1);
785                  }
786             }
787             }
788         }
789         }
790     }
791
792     /*
793      * There might be some unwanted stmts in the synch body. These are likely
794      * to be stmts which have no predecessor in the synchbody.
795      * Remove these stmts.
796      * NOTE: the entry of the synchbody is a special case since its predecessor
797      * is also not going to be in the synchbody but we SHOULD not remove the entry point
798      */
799     
800     //find the entry point of synchbody
801 /*
802      * One way of doing this is going through the synch body and finiding a stmt whose
803      * predecessor is an enter monitor stmt NOT present in the synchBody
804      */
805     AugmentedStmt synchEnter=null;
806     Iterator synchIt = synchBody.iterator();
807
808     outerLoop:
809     while (synchIt.hasNext()) {
810         AugmentedStmt as = (AugmentedStmt) synchIt.next();
811
812         Iterator pit = as.cpreds.iterator();
813         while (pit.hasNext()) {
814         AugmentedStmt pas = (AugmentedStmt) pit.next();
815
816         if (synchBody.contains( pas) == false) {
817             //the as stmt has a predecessor which is not part of the synchBody
818 Stmt pasStmt = pas.get_Stmt();
819             if(pasStmt instanceof EnterMonitorStmt){
820             //found the entry point to the synchBody
821 synchEnter = as;
822             break outerLoop;
823             }
824         }
825         }
826     }
827
828     if(synchEnter==null){
829         throw new RuntimeException ("Could not find enter stmt of the synchBody");
830     }
831
832     //System.out.println("Enter stmt of synchBody is:"+synchEnter);
833
834
835
836     /*
837      * Now that we know the exception case we can go through the synchBody and remove
838      * all stmts whose predecessor does not belong to the synchBody
839      */
840
841     boolean unChanged=false;
842     while(!unChanged){
843         unChanged=true;
844         List toRemove = new ArrayList();
845         synchIt = synchBody.iterator();
846         while(synchIt.hasNext()){
847         AugmentedStmt synchAs = (AugmentedStmt)synchIt.next();
848         if(synchAs == synchEnter){
849             //entrypoint is an exception so just continue
850 continue;
851         }
852         Iterator pit = synchAs.cpreds.iterator();
853         boolean remove = true;
854         while (pit.hasNext()) {
855             AugmentedStmt pAs = (AugmentedStmt)pit.next();
856             if(synchBody.contains(pAs)){
857             //one of the preds of this as is in the synchBody so dont remove
858 remove=false;
859             }
860         }//going through preds of the synchAs
861 if(remove){
862             //all preds not present in synchBody
863 toRemove.add(synchAs);
864         }
865         }//going through the synchBody
866 if(toRemove.size() >0){
867         //none of the preds of synchAs are in the synchBody hence this stmt is unreachable
868 synchBody.removeAll(toRemove);
869         //System.out.println("Removing:"+toRemove+" since none of its preds are in the synchBody");
870 unChanged=false;
871         }
872     }
873
874
875
876     
877
878
879     //see if the two bodies match
880 if ((en.get_Body().equals( synchBody) == false)){
881         //System.out.println("returning unverified since synchBody does not match");
882 //System.out.println("\n\nEN BODY:\n"+en.get_Body());
883 //System.out.println("\n\nSYNCH BODY:\n"+synchBody);
884 return false;
885     }
886
887
888     /*
889      * The two bodies match
890      * check if the exception thrown is of type "throwable" and that there is only one catchlist
891      * The reason for doing this is that synchronized blocks get converted to a try catch block
892      * with the catch , catching the throwable exception and this is the ONLY catch
893      */
894     if ((en.get_Exception().getName().equals( THROWABLE) == false) || (en.get_CatchList().size() > 1)){
895         //System.out.println("returning unverified here");
896 return false;
897     }
898
899
900     //at this point we know that the two bodies match and that the en exception is a throwable exception
901
902     /*
903      * find the entry point of the catch boody
904      * The entry point of the catch body is the first stmt in the catchbody
905      * This can be found by finiding the stmt whose predecessor is not part of the catch body
906      */
907     IterableSet catchBody = en.get_CatchBody();
908     AugmentedStmt entryPoint = null;
909
910     Iterator it = catchBody.iterator();
911     catchBodyLoop:
912     while (it.hasNext()) {
913         AugmentedStmt as = (AugmentedStmt) it.next();
914
915         Iterator pit = as.cpreds.iterator();
916         while (pit.hasNext()) {
917         AugmentedStmt pas = (AugmentedStmt) pit.next();
918
919         if (catchBody.contains( pas) == false) {
920             entryPoint = as;
921             break catchBodyLoop;
922         }
923         }
924     }
925
926
927
928
929     // Horror upon horrors, what follows is a hard coded state machine.
930
931     /*
932      * To verify the catchbody one has to go through the catchbody ONE stmt at a time.
933      * This is NOT a good approach as it is using PATTERN MATCHING
934      *
935      * FIRST STEP
936      * Need to verify that the entrypoint stmt and any goto stmts following it all point to the entrypoint
937      */
938
939
940     Unit entryPointTarget = null;
941     if(entryPoint.get_Stmt() instanceof GotoStmt){
942         //System.out.println("Entry point is a goto stmt getting the target");
943 entryPointTarget=((soot.jimple.internal.JGotoStmt)entryPoint.get_Stmt()).getTarget();
944     }
945
946
947
948     AugmentedStmt as = entryPoint;
949     if (as.bsuccs.size() != 1){
950         //System.out.println("here1");
951 return false;
952     }
953
954     while (as.get_Stmt() instanceof GotoStmt) {
955         as = (AugmentedStmt) as.bsuccs.get(0);
956         //if ((as.bsuccs.size() != 1) || ((as != entryPoint) && (as.cpreds.size() != 1))) {
957 //return false;
958 //}
959 if (as.bsuccs.size() != 1){
960         //System.out.println("here2a");
961 return false;
962         }
963         if(entryPointTarget != null){
964         if ((as.get_Stmt() != entryPointTarget) && (as.cpreds.size() != 1)){
965             if(as.cpreds.size() != 1) {
966             //System.out.println("here2b");
967 return false;
968             }
969         }
970         }
971         else{
972         if ((as != entryPoint) && (as.cpreds.size() != 1)) {
973             //System.out.println("here2c");
974 return false;
975         }
976         }
977     }
978
979
980     //so now we are not at a goto stmt for sure
981 //according to the creation pattern of the try catch block we should be at the definition stmt
982 //e.g. <var> := @caughtexception
983
984     Stmt s = as.get_Stmt();
985     
986     if (!(s instanceof DefinitionStmt)){
987         //System.out.println("here3");
988 return false;
989     }
990
991
992     DefinitionStmt ds = (DefinitionStmt) s;
993     Value asnFrom = ds.getRightOp();
994     
995     //if not a caught exception of type throwable we have a problem
996 if (! ( (asnFrom instanceof CaughtExceptionRef) &&
997           (((RefType) ((CaughtExceptionRef) asnFrom).getType()).getSootClass().getName().equals( THROWABLE)) ) ){
998         //System.out.println("here4");
999 return false;
1000    }
1001
1002
1003
1004
1005    
1006    Value throwlocal = ds.getLeftOp();
1007    //System.out.println("Throw local is:"+throwlocal);
1008
1009    /*
1010      The escuccs contains all the EXCEPTION SUCESSORS of the caughtexception stmt
1011    */
1012    IterableSet esuccs = new IterableSet();
1013    esuccs.addAll( as.csuccs);
1014    esuccs.removeAll( as.bsuccs);
1015    
1016
1017
1018
1019    //sucessor of definition stmt
1020 as = (AugmentedStmt) as.bsuccs.get(0);
1021    s = as.get_Stmt();
1022
1023
1024    //this COULD be a copy stmt in which case update the throwlocal
1025 if(s instanceof DefinitionStmt &&
1026       ( ((DefinitionStmt)s).getRightOp().toString().compareTo(throwlocal.toString()) ==0)) {
1027
1028        //System.out.println("copy stmt using throwLocal found");
1029 //System.out.println("Right op is :"+((DefinitionStmt)s).getRightOp());
1030 //return false;
1031 throwlocal = ((DefinitionStmt)s).getLeftOp();
1032
1033        //the sucessor of this stmt is the exitmonitor stmt
1034 as = (AugmentedStmt) as.bsuccs.get(0);
1035    }
1036
1037
1038
1039    if (as.bsuccs.size() != 1){
1040        //should have one true sucessor
1041 //System.out.println("here5a");
1042 return false;
1043    }
1044
1045
1046    if (as.cpreds.size() != 1){
1047        //should have one true predecessor
1048 //System.out.println("here5b");
1049 return false;
1050    }
1051
1052    //need to check whether this stmt is protected by the same exception block as the whole catchbody
1053 checkProtectionArea(as,ds);
1054    
1055
1056
1057    s = as.get_Stmt();
1058    if (!(s instanceof ExitMonitorStmt)){
1059        //System.out.println("Not an exit monitor stmt"+s);
1060 return false;
1061    }
1062
1063
1064    if ( (((ExitMonitorStmt) s).getOp() != monitorVariable)){
1065
1066        if( ( ((ExitMonitorStmt) s).getOp() != copiedLocal)){
1067        //System.out.println("exit monitor variable does not match enter monitor variable");
1068 return false;
1069        }
1070    }
1071
1072
1073    
1074    //next stmt should be a throw stmt
1075 as = (AugmentedStmt) as.bsuccs.get(0);
1076    if ((as.bsuccs.size() != 0) || (as.cpreds.size() != 1) || (verify_ESuccs( as, esuccs) == false)){
1077        //System.out.println("here7");
1078 return false;
1079    }
1080
1081
1082
1083    s = as.get_Stmt();
1084
1085    if ( ! ( (s instanceof ThrowStmt) && (((ThrowStmt) s).getOp() == throwlocal) ) ){
1086        //System.out.println("here8"+s+" Throw local is:"+throwlocal);
1087 return false;
1088    }
1089    
1090    return true;
1091    }
1092
1093
1094
1095
1096
1097
1098
1099
1100    /*
1101      DefinitionStmt s is the start of the area of protection
1102      The exception sucessors of as should directly or indirectly point to s
1103    */
1104    private boolean checkProtectionArea( AugmentedStmt as, DefinitionStmt s)
1105    {
1106    IterableSet esuccs = new IterableSet();
1107    esuccs.addAll( as.csuccs);
1108    esuccs.removeAll( as.bsuccs);
1109
1110    //esuccs contains the exception sucessors of as
1111 //System.out.println("ESUCCS are:"+esuccs);
1112
1113    Iterator it = esuccs.iterator();
1114    while(it.hasNext()){
1115        //going through each exception sucessor
1116 AugmentedStmt tempas = (AugmentedStmt)it.next();
1117        Stmt temps = tempas.get_Stmt();
1118        if(temps instanceof GotoStmt){
1119        Unit target = ((GotoStmt)temps).getTarget();
1120        if(target != s){
1121            //System.out.println("DID NOT Match indirectly");
1122 return false;
1123        }
1124        else{
1125            //System.out.println("Matched indirectly");
1126 }
1127        }
1128        else{
1129        if(temps != s){
1130            //System.out.println("DID NOT Match directly");
1131 return false;
1132        }
1133        else{
1134            //System.out.println("Matched directly");
1135 }
1136        }
1137
1138    }
1139    return true;
1140    }
1141
1142    
1143
1144    private boolean verify_ESuccs( AugmentedStmt as, IterableSet ref)
1145    {
1146    IterableSet esuccs = new IterableSet();
1147
1148       
1149    esuccs.addAll( as.csuccs);
1150    esuccs.removeAll( as.bsuccs);
1151
1152    //System.out.println("ESUCCS are:"+esuccs);
1153 //System.out.println("ref are:"+ref);
1154 return esuccs.equals( ref);
1155    }
1156
1157
1158
1159    /*
1160     *Input:
1161     * head: this is the monitor enter stmt
1162     * synchSet: this contains all sucessors of head which have level greater or equal to the head
1163     */
1164    private IterableSet get_BodyApproximation( AugmentedStmt head, IterableSet synchSet) {
1165    IterableSet body = (IterableSet) synchSet.clone();
1166    Value local = ((EnterMonitorStmt) head.get_Stmt()).getOp();
1167    Integer level = (Integer ) ((HashMap) as2ml.get( head)).get( local);
1168
1169
1170    //System.out.println("BODY"+body);
1171 body.remove( head);
1172    
1173    Iterator bit = body.snapshotIterator();
1174    while (bit.hasNext()) {
1175        AugmentedStmt as = (AugmentedStmt) bit.next();
1176        Stmt s = as.get_Stmt();
1177        
1178        if ((s instanceof ExitMonitorStmt) && (((ExitMonitorStmt) s).getOp() == local) &&
1179        (((Integer ) ((HashMap) as2ml.get( as)).get( local)).equals( level))) {
1180
1181        Iterator sit = as.csuccs.iterator();
1182        while (sit.hasNext()) {
1183            AugmentedStmt sas = (AugmentedStmt) sit.next();
1184            
1185            //if not dominated by head continue with next stmt in body
1186 if (sas.get_Dominators().contains( head) == false)
1187            continue;
1188            
1189            Stmt ss = sas.get_Stmt();
1190            
1191            if (((ss instanceof GotoStmt) || (ss instanceof ThrowStmt)) && (body.contains( sas) == false)){
1192            //if (ss instanceof ThrowStmt && (body.contains( sas) == false)){
1193 //System.out.println("adding"+sas);
1194 body.add( sas);
1195            }
1196        }
1197        }
1198    }
1199
1200    return body;
1201    }
1202}
1203

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags