Java > Open Source Codes > soot > dava > toolkits > base > AST > structuredAnalysis > DavaFlowSet


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2005 Nomair A. Naeem
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 /*
22  * Maintained by: Nomair A. Naeem
23  * Initial code taken from an existing implementation of the AbstractFlowSet in Soot
24  */
25
26
27 /*
28  * CHANGE LOG:
29  * 16 nov, 2005: Adding <implicitTargets> feature to be able to store mappings of breaks
30  * and continues implicitly targetting nodes
31  * 21 Nov, 2005 * Reasoning that this implmentation is correct. Adding comments
32  * * Refactored addIfNotDuplicate method since the same chunk of code was being used in
33  * multiple places
34  */
35
36
37
38 package soot.dava.toolkits.base.AST.structuredAnalysis;
39
40 import soot.toolkits.scalar.*;
41 import java.util.*;
42 import soot.dava.internal.AST.*;
43 import soot.dava.internal.SET.*;
44 import soot.dava.internal.javaRep.*;
45 import soot.dava.toolkits.base.AST.traversals.ClosestAbruptTargetFinder;
46
47 public class DavaFlowSet extends AbstractFlowSet{
48
49
50     static final int DEFAULT_SIZE = 8;
51     
52     int numElements;
53     int maxElements;
54     public Object [] elements;
55
56     /**
57      * Whenever in a structured flow analysis a break or continue stmt is encountered the current DavaFlowSet
58      * is stored in the break/continue list with the appropriate label for the target code.
59      * This is how explicit breaks and continues are handled by the analysis framework
60      */
61     HashMap breakList;
62     HashMap continueList;
63
64     /**
65      * To handle implicit breaks and continues the following HashMaps store the DavaFlowSets as value
66      * with the key being the targeted piece of code (an ASTNode)
67      */
68     HashMap implicitBreaks; //map a node and all the dataflowsets due to implicit breaks targetting it
69 HashMap implicitContinues; //map a node and all the dataflowsets due to implicit continues targetting it
70
71     public DavaFlowSet(){
72         maxElements = DEFAULT_SIZE;
73         elements = new Object [DEFAULT_SIZE];
74         numElements = 0;
75     breakList = new HashMap();
76     continueList = new HashMap();
77     implicitBreaks = new HashMap();
78     implicitContinues = new HashMap();
79     }
80     
81     private DavaFlowSet(DavaFlowSet other){
82         numElements = other.numElements;
83         maxElements = other.maxElements;
84         elements = (Object []) other.elements.clone();
85     breakList = (HashMap)other.breakList.clone();
86     continueList = (HashMap)other.continueList.clone();
87     implicitBreaks = (HashMap)other.implicitBreaks.clone();
88     implicitContinues = (HashMap)other.implicitContinues.clone();
89     }
90     
91     /** Returns true if flowSet is the same type of flow set as this. */
92     private boolean sameType(Object flowSet)
93     {
94         return (flowSet instanceof DavaFlowSet);
95     }
96
97     public Object clone()
98     {
99         return new DavaFlowSet(this);
100     }
101
102     public Object emptySet()
103     {
104         return new DavaFlowSet();
105     }
106
107     public void clear()
108     {
109         numElements = 0;
110     }
111     
112     public int size()
113     {
114         return numElements;
115     }
116
117     public boolean isEmpty()
118     {
119         return numElements == 0;
120     }
121
122     /** Returns a unbacked list of elements in this set. */
123     public List toList()
124     {
125         Object [] copiedElements = new Object [numElements];
126         System.arraycopy(elements, 0, copiedElements, 0, numElements);
127         return Arrays.asList(copiedElements);
128     }
129
130   /* Expand array only when necessary, pointed out by Florian Loitsch
131    * March 08, 2002
132    */
133     public void add(Object e){
134     /* Expand only if necessary! and removes one if too:) */
135         // Add element
136 if(!contains(e)) {
137               // Expand array if necessary
138 if(numElements == maxElements)
139                 doubleCapacity();
140               elements[numElements++] = e;
141             }
142     }
143
144     private void doubleCapacity()
145     {
146         int newSize = maxElements * 2;
147                     
148         Object [] newElements = new Object [newSize];
149                 
150         System.arraycopy(elements, 0, newElements, 0, numElements);
151         elements = newElements;
152         maxElements = newSize;
153     }
154
155     public void remove(Object obj)
156     {
157         int i = 0;
158         while (i < this.numElements) {
159             if (elements[i].equals(obj))
160             {
161                 elements[i] = elements[--numElements];
162                 return;
163             } else
164                 i++;
165         }
166     }
167
168   /* copy last element to the position of deleted element, and
169    * decrease the array size.
170    * pointed out by Florian Loitsch, March 2002
171    */
172     private void removeElementAt(int index)
173     {
174       elements[index] = elements[--numElements];
175     }
176
177     /**
178      * Notice that the union method only merges the elements of the flow set
179      * DavaFlowSet also contains information regarding abrupt control flow
180      * This should also be merged using the copyInternalDataFrom method
181      */
182     public void union(FlowSet otherFlow, FlowSet destFlow){
183       if (sameType(otherFlow) && sameType(destFlow)) {
184         DavaFlowSet other = (DavaFlowSet) otherFlow;
185         DavaFlowSet dest = (DavaFlowSet) destFlow;
186
187         // For the special case that dest == other
188 if(dest == other)
189             {
190                 for(int i = 0; i < this.numElements; i++)
191                     dest.add(this.elements[i]);
192             }
193         
194         // Else, force that dest starts with contents of this
195 else {
196             if(this != dest)
197                 copy(dest);
198
199             for(int i = 0; i < other.numElements; i++)
200                 dest.add(other.elements[i]);
201         }
202       } else
203         super.union(otherFlow, destFlow);
204     }
205
206
207     /**
208      * Notice that the intersection method only merges the elements of the flow set
209      * DavaFlowSet also contains information regarding abrupt control flow
210      * This should also be merged using the copyInternalDataFrom method
211      */
212     public void intersection(FlowSet otherFlow, FlowSet destFlow)
213     {
214       if (sameType(otherFlow) &&
215           sameType(destFlow)) {
216         DavaFlowSet other = (DavaFlowSet) otherFlow;
217         DavaFlowSet dest = (DavaFlowSet) destFlow;
218         DavaFlowSet workingSet;
219         
220         if(dest == other || dest == this)
221             workingSet = new DavaFlowSet();
222         else {
223             workingSet = dest;
224             workingSet.clear();
225         }
226         
227         for(int i = 0; i < this.numElements; i++)
228         {
229             if(other.contains(this.elements[i]))
230                 workingSet.add(this.elements[i]);
231         }
232         
233         if(workingSet != dest)
234             workingSet.copy(dest);
235       } else
236         super.intersection(otherFlow, destFlow);
237     }
238
239
240
241     public void difference(FlowSet otherFlow, FlowSet destFlow)
242     {
243       if (sameType(otherFlow) &&
244           sameType(destFlow)) {
245         DavaFlowSet other = (DavaFlowSet) otherFlow;
246         DavaFlowSet dest = (DavaFlowSet) destFlow;
247         DavaFlowSet workingSet;
248         
249         if(dest == other || dest == this)
250             workingSet = new DavaFlowSet();
251         else {
252             workingSet = dest;
253             workingSet.clear();
254         }
255         
256         for(int i = 0; i < this.numElements; i++)
257         {
258             if(!other.contains(this.elements[i]))
259                 workingSet.add(this.elements[i]);
260         }
261         
262         if(workingSet != dest)
263             workingSet.copy(dest);
264       } else
265         super.difference(otherFlow, destFlow);
266     }
267
268
269     
270     public boolean contains(Object obj)
271     {
272         for(int i = 0; i < numElements; i++)
273             if(elements[i].equals(obj))
274                 return true;
275                 
276         return false;
277     }
278
279
280
281
282     /**
283      * Notice that the equals method only checks the equality of the elements of the flow set
284      * DavaFlowSet also contains information regarding abrupt control flow
285      * This should also be checked by invoking the internalDataMatchesTo method
286      */
287
288     public boolean equals(Object otherFlow)
289     {
290       if (sameType(otherFlow)) {
291         DavaFlowSet other = (DavaFlowSet) otherFlow;
292          
293         if(other.numElements != this.numElements)
294             return false;
295      
296         int size = this.numElements;
297              
298         // Make sure that thisFlow is contained in otherFlow
299 for(int i = 0; i < size; i++)
300                 if(!other.contains(this.elements[i]))
301                     return false;
302
303             /* both arrays have the same size, no element appears twice in one
304              * array, all elements of ThisFlow are in otherFlow -> they are
305              * equal! we don't need to test again!
306         // Make sure that otherFlow is contained in ThisFlow
307             for(int i = 0; i < size; i++)
308                 if(!this.contains(other.elements[i]))
309                     return false;
310              */
311         
312         return true;
313       } else
314         return super.equals(otherFlow);
315     }
316
317     public void copy(FlowSet destFlow)
318     {
319       if (sameType(destFlow)) {
320         DavaFlowSet dest = (DavaFlowSet) destFlow;
321
322         while(dest.maxElements < this.maxElements)
323             dest.doubleCapacity();
324     
325         dest.numElements = this.numElements;
326         
327         System.arraycopy(this.elements, 0,
328             dest.elements, 0, this.numElements);
329       } else
330         super.copy(destFlow);
331     }
332
333
334
335     /**
336      * A private method used to add an element into a List if it is NOT a duplicate
337      */
338     private List addIfNotDuplicate(List into, DavaFlowSet addThis){
339     //if set is not already present in the labelsBreakList then add it
340 Iterator it = into.iterator();
341     boolean found=false;
342     while(it.hasNext()){
343         DavaFlowSet temp = (DavaFlowSet)it.next();
344         if(temp.equals(addThis) && temp.internalDataMatchesTo(addThis)){
345         found=true;
346         break;
347         }
348     }
349     if(!found)
350         into.add(addThis);
351     return into;
352     }
353
354
355     /**
356      * When an explicit break statement is encountered this method should be called
357      * to store the current davaflowset
358      */
359     public void addToBreakList(String labelBroken, DavaFlowSet set){
360     Object obj = breakList.get(labelBroken);
361     if(obj == null){
362         List labelsBreakList = new ArrayList();
363         labelsBreakList.add(set);
364         breakList.put(labelBroken,labelsBreakList);
365         //System.out.println("ADDED"+labelBroken+" with"+set.toString());
366 }
367     else{
368         List labelsBreakList = (List)obj;
369         //add set into this list if its not a duplicate and update the hashMap
370 breakList.put(labelBroken,addIfNotDuplicate(labelsBreakList,set));
371     }
372     }
373
374
375
376
377     /**
378      * When an explicit continue statement is encountered this method should be called
379      * to store the current davaflowset
380      */
381     public void addToContinueList(String labelContinued, DavaFlowSet set){
382     Object obj = continueList.get(labelContinued);
383     if(obj == null){
384         List labelsContinueList = new ArrayList();
385         labelsContinueList.add(set);
386         continueList.put(labelContinued,labelsContinueList);
387
388     }
389     else{
390         List labelsContinueList = (List)obj;
391         continueList.put(labelContinued,addIfNotDuplicate(labelsContinueList,set));
392     }
393     }
394
395
396
397     /**
398      * Checks whether the input stmt is an implicit break/continue
399      * A abrupt stmt is implicit if the SETLabelNode is null or the label.toString results in null
400      */
401     private boolean checkImplicit(DAbruptStmt ab){
402     SETNodeLabel label = ab.getLabel();
403     if(label==null)
404         return true;
405     if(label.toString()==null)
406         return true;
407     return false;
408     }
409
410     /**
411      * The next two methods take an abruptStmt as input along with a flowSet.
412      * It should be only invoked for abrupt stmts which do not have explicit labels
413
414      * The node being targeted by this implicit stmt should be found
415      * Then the flow set should be added to the list within the appropriate hashmap
416      */
417     public void addToImplicitBreaks(DAbruptStmt ab, DavaFlowSet set){
418     if(!checkImplicit(ab))
419         throw new RuntimeException ("Tried to add explicit break statement in the implicit list in");
420
421     if(!ab.is_Break())
422         throw new RuntimeException ("Tried to add continue statement in the break list in DavaFlowSet.addToImplicitBreaks");
423
424     //okkay so its an implicit break
425 //get the targetted node, use the ClosestAbruptTargetFinder
426 ASTNode node = ClosestAbruptTargetFinder.v().getTarget(ab);
427     
428     //get the list of flow sets already stored for this node
429 Object list = implicitBreaks.get(node);
430     ArrayList listSets = null;
431     if(list == null){
432         listSets = new ArrayList();
433     }
434     else{
435         //if not null
436 listSets = (ArrayList)list;
437     }
438
439     //if set is not already present in listSets add it and update hashMap
440 implicitBreaks.put(node,addIfNotDuplicate(listSets,set));
441     }
442     
443     public void addToImplicitContinues(DAbruptStmt ab, DavaFlowSet set){
444     if(!checkImplicit(ab))
445         throw new RuntimeException ("Tried to add explicit continue statement in the implicit list ");
446
447     if(!ab.is_Continue())
448         throw new RuntimeException ("Tried to add break statement in the continue list");
449
450     //okkay so its an implicit continue
451 //get the targetted node, use the ClosestAbruptTargetFinder
452 ASTNode node = ClosestAbruptTargetFinder.v().getTarget(ab);
453     
454     //get the list of flow sets already stored for this node
455 Object list = implicitContinues.get(node);
456     ArrayList listSets = null;
457     if(list == null){
458         listSets = new ArrayList();
459     }
460     else{
461         //if not null
462 listSets = (ArrayList)list;
463     }
464
465     //if set is not already present in listSets add it and update hashMap
466 implicitContinues.put(node,addIfNotDuplicate(listSets,set));
467     }
468
469
470
471     private HashMap getBreakList(){
472     return breakList;
473     }
474
475     private HashMap getContinueList(){
476     return continueList;
477     }
478
479     public HashMap getImplicitBreaks(){
480     return implicitBreaks;
481     }
482
483     public HashMap getImplicitContinues(){
484     return implicitContinues;
485     }
486
487
488     public List getImplicitlyBrokenSets(ASTNode node){
489     Object toReturn = implicitBreaks.get(node);
490     if(toReturn != null)
491         return (List)toReturn;
492     return null;
493     }
494
495     public List getImplicitlyContinuedSets(ASTNode node){
496     Object toReturn = implicitContinues.get(node);
497     if(toReturn != null)
498         return (List)toReturn;
499     return null;
500     }
501
502
503
504
505
506     /**
507      * An internal method used to copy non-duplicate entries from the temp list
508      * into the currentList
509      */
510     private List copyDavaFlowSetList(List currentList, List temp){
511     Iterator tempIt = temp.iterator();
512     while(tempIt.hasNext()){
513         DavaFlowSet check = (DavaFlowSet)tempIt.next();
514         Iterator currentListIt = currentList.iterator();
515         boolean found=false;
516         while(currentListIt.hasNext()){
517         //see if currentList has check
518 DavaFlowSet currentSet = (DavaFlowSet)currentListIt.next();
519         if(check.equals(currentSet) && check.internalDataMatchesTo(currentSet)){
520             found=true;
521             break;
522         }
523         }
524         if(!found){
525         currentList.add(check);
526         }
527     }
528     return currentList;
529     }
530     
531     public void copyInternalDataFrom(Object fromThis){
532     if(!sameType(fromThis))
533         return;
534
535     //copy elements of breaklist
536 {
537         HashMap fromThisBreakList = ((DavaFlowSet)fromThis).getBreakList();
538
539         Iterator keys = fromThisBreakList.keySet().iterator();
540         while(keys.hasNext()){
541         String labelBroken = (String )keys.next();
542         List temp = (List)fromThisBreakList.get(labelBroken);
543         
544         Object list = breakList.get(labelBroken);
545
546         if(list == null){
547             breakList.put(labelBroken,temp);
548         }
549         else{
550         List currentList = (List)list;
551             List complete = copyDavaFlowSetList(currentList,temp);
552             breakList.put(labelBroken,complete);
553         }
554         }
555     }
556
557
558
559         
560         //copy elements of continuelist
561 {
562         HashMap fromThisContinueList = ((DavaFlowSet)fromThis).getContinueList();
563         
564         Iterator keys = fromThisContinueList.keySet().iterator();
565         while(keys.hasNext()){
566         String labelContinued = (String )keys.next();
567         List temp = (List)fromThisContinueList.get(labelContinued);
568         
569         Object list = (List)continueList.get(labelContinued);
570         if(list == null){
571             continueList.put(labelContinued,temp);
572         }
573         else{
574             List currentList = (List)list;
575             List complete = copyDavaFlowSetList(currentList,temp);
576             continueList.put(labelContinued,currentList);
577         }
578         }
579     }
580     
581     //copy elements of implicitBreaks
582 //this hashMap contains a mapping of ASTNodes to DavaFlowSets due to impicit breaks
583 {
584         HashMap copyThis = ((DavaFlowSet)fromThis).getImplicitBreaks();
585         Iterator it = copyThis.keySet().iterator();
586         while(it.hasNext()){ //going through all nodes in the other objects implicitBreaks hashMap
587 //each is a node
588 ASTNode node = (ASTNode)it.next();
589         //get list of dava flow sets targetting this node implicitly
590 ArrayList fromDavaFlowSets = (ArrayList)copyThis.get(node);
591         //Have copy non duplicates in this to the implicitbreak hashMap the current dava flow set has
592
593
594         Object list = implicitBreaks.get(node);
595         if(list==null){
596             //there was no dava flow set currently targetting this node implicitly
597 //put the fromDavaFlowSets into the hashMap
598 implicitBreaks.put(node,fromDavaFlowSets);
599         }
600         else{
601             ArrayList toDavaFlowSets = (ArrayList)list;
602             List complete = copyDavaFlowSetList(toDavaFlowSets,fromDavaFlowSets);
603             implicitBreaks.put(node,complete);
604         }
605         }
606     }
607
608     //copy elements of implicitContinues
609 //this hashMap contains a mapping of ASTNodes to DavaFlowSets due to impicit continues
610 {
611         HashMap copyThis = ((DavaFlowSet)fromThis).getImplicitContinues();
612         Iterator it = copyThis.keySet().iterator();
613         while(it.hasNext()){ //going through all nodes in the other objects implicitcontinues hashMap
614 //each is a node
615 ASTNode node = (ASTNode)it.next();
616         //get list of dava flow sets targetting this node implicitly
617 ArrayList fromDavaFlowSets = (ArrayList)copyThis.get(node);
618         //Have copy non duplicates in this to the implicitContinue hashMap the current dava flow set has
619
620
621
622         Object list = implicitContinues.get(node);
623         if(list==null){
624             //there was no dava flow set currently targetting this node implicitly
625 //put the fromDavaFlowSets into the hashMap
626 implicitContinues.put(node,fromDavaFlowSets);
627         }
628         else{
629             ArrayList toDavaFlowSets = (ArrayList)list;
630             List complete = copyDavaFlowSetList(toDavaFlowSets,fromDavaFlowSets);
631             implicitContinues.put(node,complete);
632         }
633         }
634         
635     }
636
637     }
638
639     private boolean compareLists(Object One , Object Two){
640     if(One==null && Two == null)
641         return true;
642
643     if(One == null || Two == null)
644         return false;
645
646     List listOne = (List)One;
647     List listTwo = (List)Two;
648
649     //compare elements of the list
650 if(listOne.size()!= listTwo.size()){
651         //size has to be same for lists to match
652 return false;
653     }
654     Iterator listOneIt = listOne.iterator();
655     boolean found=false;
656     while(listOneIt.hasNext()){
657         //going through the first list
658 Object listOneObj = listOneIt.next();
659
660
661         Iterator listTwoIt = listTwo.iterator();
662         while(listTwoIt.hasNext()){
663         //find the object in the second list
664 Object listTwoObj = listTwoIt.next();
665         if(listOneObj.equals(listTwoObj)){
666             //if object is found stop search
667 found=true;
668             break;
669         }
670         }
671         if(!found){
672         //if didnt find object return false
673 return false;
674         }
675         found=false;
676     }
677     return true;
678     }
679
680     public boolean internalDataMatchesTo(Object otherObj){
681     if(!(otherObj instanceof DavaFlowSet))
682         return false;
683
684     DavaFlowSet other = (DavaFlowSet)otherObj;
685
686     //check if same break list
687 HashMap otherMap = other.getBreakList();
688     if( ! compareHashMaps(breakList,otherMap) )
689         return false;
690
691
692     //check if same continue list
693 otherMap = other.getContinueList();
694     if( ! compareHashMaps(continueList,otherMap) )
695         return false;
696
697
698     //check implicitBreaks match
699 otherMap = other.getImplicitBreaks();
700     if( ! compareHashMaps(implicitBreaks,otherMap) )
701         return false;
702
703     //check implicitContinues match
704 otherMap = other.getImplicitContinues();
705     if( ! compareHashMaps(implicitContinues,otherMap) )
706         return false;
707     
708     return true;
709     }
710
711
712     private boolean compareHashMaps(HashMap thisMap,HashMap otherMap){
713     List otherKeyList = new ArrayList();
714     
715     Iterator keys = otherMap.keySet().iterator();
716     while(keys.hasNext()){
717         String otherKey = (String )keys.next();
718         otherKeyList.add(otherKey);
719         
720         Object listOther = otherMap.get(otherKey);
721         Object listThis = thisMap.get(otherKey);
722
723         //compare the two lists
724 if(!compareLists(listOther,listThis)){
725         //if lists dont match internalData doesnt match
726 return false;
727         }
728     }
729     //have gone through otherMap
730
731     //going through thisMap
732 keys = thisMap.keySet().iterator();
733     while(keys.hasNext()){
734         String key = (String )keys.next();
735         
736         Iterator keyListIt = otherKeyList.iterator();
737         boolean alreadyDone=false;
738         
739         while(keyListIt.hasNext()){
740         String doneKey = (String )keyListIt.next();
741         if(key.equals(doneKey)){
742             alreadyDone=true;
743             break;
744         }
745         }
746         if(!alreadyDone){
747         /*
748           we have come across a label
749           which was not done by the first hashmap
750           meaning it was NOT in the first hashMap
751         */
752         return false;
753         }
754     }
755     return true;
756     }
757
758
759     public List getContinueSet(String label){
760     return (List)continueList.remove(label);
761     }
762
763
764     public List getBreakSet(String label){
765     return (List)breakList.remove(label);
766     }
767
768
769
770     public String toString(){
771     StringBuffer b = new StringBuffer ();
772     b.append(" SET={");
773         for(int i = 0; i < this.numElements; i++){
774         if(i!=0)
775         b.append(" , ");
776
777         b.append(this.elements[i].toString());
778     }
779     b.append(" }");
780     return b.toString();
781     }
782
783
784
785
786     /* public String toString(){
787     StringBuffer b = new StringBuffer();
788     b.append("\nSETTTTT\n");
789         for(int i = 0; i < this.numElements; i++){
790         b.append("\t"+this.elements[i]+"\n");
791     }
792     b.append("BREAK LIST\n");
793     b.append("\t"+breakList.toString()+"\n");
794     
795
796     b.append("CONTINUE LIST\n");
797     b.append("\t"+continueList.toString()+"\n");
798
799     b.append("EXCEPTION LIST\n");
800     b.append("\t"+exceptionList.toString()+"\n");
801     return b.toString();
802     }
803     */
804 }
805

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags