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


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  * Maintained by: Nomair A. Naeem
22  */
23
24
25 /**
26  * CHANGE LOG:
27  * November 21st, 2005: Reasoning about correctness of implementation.
28  * November 22nd, 2005: Found bug in process_DoWhile while implementing ReachingCopies..
29  * see method for details
30  * January 30th, 2006: Found bug in handling of breaks inside the ASTTryNode while implementing
31  * MustMayinitialize...see ASTTryNode method for details
32  * January 30th, 2006: Found bug in handling of switchNode while implementing MustMayInitialize
33  * NEEDS THOROUGH TESTING!!!
34  *
35  */
36
37
38 /**
39  * TODO:
40  * Refactor the class into a top level class and a forward analysis subclass
41  * Write the backwards flow analysis
42  *
43  * THOROUGH TESTING OF BUG FOUND ON 30th January
44  */
45 package soot.dava.toolkits.base.AST.structuredAnalysis;
46
47
48 import soot.*;
49 import java.util.*;
50 import soot.jimple.*;
51 import soot.dava.internal.AST.*;
52 import soot.dava.internal.SET.*;
53 import soot.dava.internal.asg.*;
54 import soot.dava.internal.javaRep.*;
55
56
57 /*
58  * This class is meant to be extended to write structred analyses.
59  * The analysis is invoked by invoking the process method sending it
60  * the body to be analyzed and the input flowset
61  * Currently support is available only for a forward flow analysis.
62  * This should soon be refactored to include backwards flow analysis
63  * (Nomair 16th November 2005)
64  */
65 public abstract class StructuredAnalysis{
66
67     /**
68      * Whenever an abrupt edge is encountered the flow set is
69      * added into a the break or continue list and a NOPATH
70      * object is returned
71      */
72     DavaFlowSet NOPATH = new DavaFlowSet();
73     int MERGETYPE; //the confluence operator
74
75     //the three types of operators
76 final int UNDEFINED=0;
77     final int UNION=1;
78     final int INTERSECTION=2;
79
80     //storing before and after sets for each stmt or ASTNode
81 HashMap beforeSets,afterSets;
82
83     public StructuredAnalysis(){
84     beforeSets = new HashMap();
85     afterSets = new HashMap();
86     MERGETYPE=UNDEFINED;
87     //invoke user defined function which makes sure that you have the merge operator set
88 setMergeType();
89     //System.out.println("MergeType is"+MERGETYPE);
90 if(MERGETYPE == UNDEFINED)
91         throw new RuntimeException ("MERGETYPE UNDEFINED");
92     }
93
94     /*
95      * This method should be used to set the variable MERGETYPE
96      * use StructuredAnalysis.UNION for union
97      * use StructuredAnalysis.INTERSECTION for intersection
98      */
99     public abstract void setMergeType();
100
101     /*
102      * Returns the flow object corresponding to the initial values for
103      * the catch statements
104      */
105     public abstract Object newInitialFlow();
106
107     /**
108      * Make a clone of the flowset
109      * The implementor should know when they want a shallow or deep clone
110      */
111     public abstract Object cloneFlowSet(Object flowSet);
112
113     /**
114      * Specific stmts within AST Constructs are processed through this
115      * method. It will be invoked everytime a stmt is encountered
116      */
117     public abstract Object processStatement(Stmt s, Object input);
118
119
120
121     /**
122      * To have maximum flexibility in analyzing conditions the analysis API
123      * breaks down the aggregated conditions to simple unary or binary conditions
124      * user defined code can then deal with each condition separatly.
125      * To be able to deal with entire aggregated conditions the user should
126      * wite their own implementation of the method processCondition
127      */
128     public abstract Object processUnaryBinaryCondition(ASTUnaryBinaryCondition cond,Object input);
129
130
131
132     /**
133      * To deal with the local used for synch blocks
134      */
135     public abstract Object processSynchronizedLocal(Local local,Object input);
136
137
138
139     /**
140      * Deal with the key in the switch construct
141      */
142     public abstract Object processSwitchKey(Value key,Object input);
143
144
145
146
147     public void print(Object toPrint){
148     System.out.println(toPrint.toString());
149     }
150
151
152
153     /**
154      * This implementation breaks down the aggregated condition to the terminal conditions
155      * which all have type ASTUnaryBinaryCondition. Once these are obtained the
156      * abstract method processUnaryBinaryCondition is invoked.
157      * For aggregated conditions the merging is done in a depth first order of the
158      * condition tree.
159      */
160     public Object processCondition(ASTCondition cond,Object input){
161     if(cond instanceof ASTUnaryBinaryCondition){
162         return processUnaryBinaryCondition((ASTUnaryBinaryCondition)cond,input);
163     }
164     else if (cond instanceof ASTAggregatedCondition){
165         ASTCondition left = ((ASTAggregatedCondition)cond).getLeftOp();
166         Object output1 = processCondition(left,input);
167
168         ASTCondition right = ((ASTAggregatedCondition)cond).getRightOp();
169         Object output2 = processCondition(right,output1);
170
171         return merge(output1,output2);
172     }
173     else{
174         throw new RuntimeException ("Unknown ASTCondition found in structred flow analysis");
175     }
176     }
177
178
179
180
181     /*
182      * The parameter body contains the body to be analysed
183      * It can be an ASTNode, a Stmt, an augmentedStmt or a list of ASTNodes
184      * The input is any data that is gathered plus any info needed for making
185      * decisions during the analysis
186      */
187     public Object process(Object body, Object input){
188     if(!(input instanceof DavaFlowSet))
189         throw new RuntimeException ("process method of StructuredAnalysis invoked with non DavaFlowSet object");
190
191     if(body instanceof ASTNode){
192         beforeSets.put(body,input);
193         Object temp=processASTNode((ASTNode)body,input);
194         afterSets.put(body,temp);
195         return temp;
196     }
197     else if(body instanceof Stmt){
198         beforeSets.put(body,input);
199         Object result=processAbruptStatements((Stmt)body,(DavaFlowSet)input);
200         afterSets.put(body,result);
201         return result;
202     }
203     else if (body instanceof AugmentedStmt){
204         AugmentedStmt as = (AugmentedStmt)body;
205         Stmt s = as.get_Stmt();
206
207         beforeSets.put(s,input);
208         Object result=processAbruptStatements(s,(DavaFlowSet)input);
209         afterSets.put(s,result);
210         return result;
211
212     }
213     else if (body instanceof List){
214         //this should always be a list of ASTNodes
215 Iterator it = ((List)body).iterator();
216         Object result=input;
217         while(it.hasNext()){
218         Object temp = it.next();
219         if(!(temp instanceof ASTNode))
220             throw new RuntimeException ("Body sent to be processed by "+
221                            "StructuredAnalysis contains a list which does not have ASTNodes");
222         else{
223             /*
224               As we are simply going through a list of ASTNodes
225               The output of the previous becomes the input of the next
226             */
227             beforeSets.put(temp,result);
228             result= processASTNode((ASTNode)temp,result);
229             afterSets.put(temp,result);
230         }
231         }//end of going through list
232
233         //at this point the result var contains the result of processing the List
234 return result;
235     }
236     else{
237         throw new RuntimeException ("Body sent to be processed by "+
238                        "StructuredAnalysis is not a valid body");
239     }
240     }
241
242
243     /*
244      * This method internally invoked by the process method decides which ASTNode
245      * specialized method to call
246      */
247     public Object processASTNode(ASTNode node, Object input){
248     if(node instanceof ASTDoWhileNode){
249         return processASTDoWhileNode((ASTDoWhileNode)node,input);
250     }
251     else if(node instanceof ASTForLoopNode){
252         return processASTForLoopNode((ASTForLoopNode)node,input);
253     }
254     else if(node instanceof ASTIfElseNode){
255         return processASTIfElseNode((ASTIfElseNode)node,input);
256     }
257     else if(node instanceof ASTIfNode){
258         return processASTIfNode((ASTIfNode)node,input);
259     }
260     else if(node instanceof ASTLabeledBlockNode){
261         return processASTLabeledBlockNode((ASTLabeledBlockNode)node,input);
262     }
263     else if(node instanceof ASTMethodNode){
264         return processASTMethodNode((ASTMethodNode)node,input);
265     }
266     else if(node instanceof ASTStatementSequenceNode){
267         return processASTStatementSequenceNode((ASTStatementSequenceNode)node,input);
268     }
269     else if(node instanceof ASTSwitchNode){
270         return processASTSwitchNode((ASTSwitchNode)node,input);
271     }
272     else if(node instanceof ASTSynchronizedBlockNode){
273         return processASTSynchronizedBlockNode((ASTSynchronizedBlockNode)node,input);
274     }
275     else if(node instanceof ASTTryNode){
276         return processASTTryNode((ASTTryNode)node,input);
277     }
278     else if(node instanceof ASTWhileNode){
279         return processASTWhileNode((ASTWhileNode)node,input);
280     }
281     else if(node instanceof ASTUnconditionalLoopNode){
282         return processASTUnconditionalLoopNode((ASTUnconditionalLoopNode)node,input);
283     }
284     else{
285         throw new RuntimeException ("processASTNode called using unknown node type");
286     }
287     }
288
289
290     /**
291      * This method is called from the specialized ASTNodes.
292      * The purpose was to deal with different ASTNodes with similar structure in one
293      * go. The method will deal with retrieve the body of the ASTNode which are known
294      * to have only one subBody
295      */
296     public final Object processSingleSubBodyNode(ASTNode node, Object input){
297     //get the subBodies
298 List subBodies = node.get_SubBodies();
299     if(subBodies.size()!=1){
300         throw new RuntimeException ("processSingleSubBodyNode called with a node without one subBody");
301     }
302     //we know there is only one
303 List subBody = (List)subBodies.get(0);
304     return process(subBody,input);
305     }
306
307
308
309
310     /**
311      * returns label on the ASTNode
312      * null if the ASTNode cannot hold a label or if the label is null
313      */
314     private String getLabel(ASTNode node){
315     if(node instanceof ASTLabeledNode){
316         Object temp = ((ASTLabeledNode)node).get_Label();
317         if(temp != null)
318         return temp.toString();
319     }
320     return null;
321     }
322
323
324
325
326     /**
327      * Whenever a statement has to be processed the first step is to invoke this method.
328      * This is to remove the tedious work of adding code to deal with abrupt control flow
329      * from the programmer of the analysis.
330      * The method invokes the processStatement method for all other statements
331      */
332     public Object processAbruptStatements(Stmt s, DavaFlowSet input){
333     if(s instanceof ReturnStmt || s instanceof RetStmt || s instanceof ReturnVoidStmt){
334         //dont need to remember this path
335 return NOPATH;
336     }
337     else if(s instanceof DAbruptStmt){
338         DAbruptStmt abStmt = (DAbruptStmt)s;
339         
340         //see if its a break or continue
341 if(!(abStmt.is_Continue()|| abStmt.is_Break())){
342         //DAbruptStmt is of only two kinds
343 throw new RuntimeException ("Found a DAbruptStmt which is neither break nor continue!!");
344         }
345         
346         
347         DavaFlowSet temp = NOPATH;
348         SETNodeLabel nodeLabel = abStmt.getLabel();
349         //System.out.println("here");
350 if(nodeLabel != null && nodeLabel.toString() != null){
351         //System.out.println("explicit");
352 //System.out.println(input);
353 //explicit abrupt stmt
354 if(abStmt.is_Continue())
355             temp.addToContinueList(nodeLabel.toString(),input);
356         else if (abStmt.is_Break())
357             temp.addToBreakList(nodeLabel.toString(),input);
358         else
359             throw new RuntimeException ("Found abruptstmt which is neither break nor continue");
360         }
361         else{
362         //System.out.println("implicit");
363 //found implicit break/continue
364 if(abStmt.is_Continue())
365             temp.addToImplicitContinues(abStmt,input);
366         else if (abStmt.is_Break())
367             temp.addToImplicitBreaks(abStmt,input);
368         else
369             throw new RuntimeException ("Found abruptstmt which is neither break nor continue");
370         }
371         return temp;
372     }
373     else{
374         /**************************************************************/
375         /******ALL OTHER STATEMENTS HANDLED BY PROGRAMMER**************/
376         /**************************************************************/
377         return processStatement(s,input);
378     }
379     }
380
381
382
383
384
385
386
387
388
389
390
391
392
393     /*
394      * Notice Right now the output of the processing of method bodies
395      * is returned as the output. This only works for INTRA procedural
396      * Analysis. For accomodating INTER procedural analysis one needs
397      * to have a return list of all possible returns (stored in the flowset)
398      * And merge Returns with the output of normal execution of the body
399      */
400     //reasoned about this....seems right!!
401 public Object processASTMethodNode(ASTMethodNode node,Object input){
402     Object temp = processSingleSubBodyNode(node,input);
403     return temp;
404     }
405
406
407
408
409
410
411
412
413
414
415     public Object processASTStatementSequenceNode(ASTStatementSequenceNode node,Object input){
416     List statements = node.getStatements();
417     Iterator it = statements.iterator();
418     
419     Object output = cloneFlowSet(input);//needed if there are no stmts
420 while(it.hasNext()){
421         AugmentedStmt as = (AugmentedStmt)it.next();
422         Stmt s = as.get_Stmt();
423         /*
424           Since we are processing a list of statements the output of
425           previous is input of next
426         */
427         output=process(s,output);
428     }
429     return output;
430     }
431
432
433
434
435
436
437
438
439
440
441     //reasoned about this....seems right!!
442 public Object processASTLabeledBlockNode(ASTLabeledBlockNode node,Object input){
443     Object output1 = processSingleSubBodyNode(node,input);
444     
445     //handle break
446 String label = getLabel(node);
447     return handleBreak(label,output1,node);
448     }
449
450
451
452
453
454
455
456
457
458
459     public Object processASTSynchronizedBlockNode(ASTSynchronizedBlockNode node,Object input){
460     input = processSynchronizedLocal(node.getLocal(),input);
461
462     Object output = processSingleSubBodyNode(node,input);
463     String label = getLabel(node);
464     return handleBreak(label,output,node);
465     }
466
467
468
469
470
471
472
473
474
475
476
477
478     //reasoned about this....seems right!!
479 public Object processASTIfNode(ASTIfNode node,Object input){
480     input = processCondition(node.get_Condition(),input);
481     Object output1 = processSingleSubBodyNode(node,input);
482
483     //merge with input which tells if the cond did not evaluate to true
484 Object output2 = merge(input,output1);
485
486     //handle break
487 String label = getLabel(node);
488     
489     Object temp= handleBreak(label,output2,node);
490     return temp;
491     }
492
493
494
495
496
497
498
499
500
501
502
503
504     public Object processASTIfElseNode(ASTIfElseNode node,Object input){
505     //get the subBodies
506 List subBodies = node.get_SubBodies();
507     if(subBodies.size()!=2){
508         throw new RuntimeException ("processASTIfElseNode called with a node without two subBodies");
509     }
510     //we know there is only two subBodies
511 List subBodyOne = (List)subBodies.get(0);
512     List subBodyTwo = (List)subBodies.get(1);
513
514     //process Condition
515 input = processCondition(node.get_Condition(),input);
516     //the current input flowset is sent to both branches
517 Object clonedInput = cloneFlowSet(input);
518     Object output1 = process(subBodyOne,clonedInput);
519
520     clonedInput = cloneFlowSet(input);
521     Object output2 = process(subBodyTwo,clonedInput);
522
523     Object temp=merge(output1,output2);
524
525     //notice we handle breaks only once since these are breaks to the same label or same node
526 String label = getLabel(node);
527     output1 = handleBreak(label,temp,node);
528     return output1;
529     }
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550     public Object processASTWhileNode(ASTWhileNode node,Object input){
551     Object lastin=null;
552     Object initialInput = cloneFlowSet(input);
553     
554     String label = getLabel(node);
555     Object output=null;
556
557     input = processCondition(node.get_Condition(),input);
558
559     do{
560         lastin = cloneFlowSet(input);
561         output = processSingleSubBodyNode(node,input);
562
563         //handle continue
564 output = handleContinue(label,output,node);
565
566         //merge with the initial input
567 input = merge(initialInput,output);
568         input = processCondition(node.get_Condition(),input);
569     } while(isDifferent(lastin,input));
570
571     //input contains the result of the fixed point
572 Object temp= handleBreak(label,input,node);
573     return temp;
574     }
575
576
577
578
579
580
581
582
583
584
585
586
587     public Object processASTDoWhileNode(ASTDoWhileNode node, Object input){
588     Object lastin=null,output=null;
589     Object initialInput = cloneFlowSet(input);
590     String label = getLabel(node);
591
592     do{
593         lastin = cloneFlowSet(input);
594         output = processSingleSubBodyNode(node,input);
595
596         //handle continue
597 output = handleContinue(label,output,node);
598
599         output = processCondition(node.get_Condition(),output);
600
601         //merge with the initial input
602 input = merge(initialInput,output);
603     } while(isDifferent(lastin,input));
604
605     //output contains the result of the fixed point since do-while breaks of at the processing of cond
606 Object temp= handleBreak(label,output,node);
607     return temp;
608
609     }
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626     public Object processASTUnconditionalLoopNode(ASTUnconditionalLoopNode node,Object input){
627     //an unconditional loop behaves almost like a conditional While loop
628 Object initialInput = cloneFlowSet(input);
629     Object lastin=null;
630
631     String label = getLabel(node);
632     Object output=null;
633     do{
634         lastin = cloneFlowSet(input);
635         output = processSingleSubBodyNode(node,input);
636
637         //handle continue
638 output = handleContinue(label,output,node);
639
640         //merge this with the initial input
641 input = merge(initialInput,output);
642     } while(isDifferent(lastin,input));
643
644     //the output is not part of the set returned
645 //it is just used to retireve the set of breaklists stored for this label
646 return getMergedBreakList(label,output,node);
647     }
648
649
650
651
652
653
654
655
656
657
658
659
660
661     public Object processASTForLoopNode(ASTForLoopNode node,Object input){
662     List init = node.getInit();
663     Iterator it = init.iterator();
664     while(it.hasNext()){
665         AugmentedStmt as = (AugmentedStmt)it.next();
666         Stmt s = as.get_Stmt();
667         input = process(s,input);
668     }
669
670     //finished processing the init part of the for loop
671 Object initialInput = cloneFlowSet(input);
672
673     input = processCondition(node.get_Condition(),input);
674     Object lastin = null;
675     String label = getLabel(node);
676     Object output2=null;
677     do{
678         lastin = cloneFlowSet(input);
679         
680         //process body
681 Object output1 = processSingleSubBodyNode(node,input);
682
683         //handle continues (Notice this is done before update!!!)
684 output1 = handleContinue(label,output1,node);
685
686         //notice that we dont merge with the initial output1 from processing singleSubBody
687 //the handlecontinue function takes care of it
688
689         //handle update
690 output2 = cloneFlowSet(output1);//if there is nothing in update
691
692         List update = node.getUpdate();
693         it = update.iterator();
694         while(it.hasNext()){
695         AugmentedStmt as = (AugmentedStmt)it.next();
696         Stmt s = as.get_Stmt();
697         /*
698           Since we are just going over a list of statements
699           the output of each statement is the input of the next
700         */
701         output2 = process(s,output2);
702         }
703
704         //output2 is the final result
705
706         //merge this with the input
707 input = merge(initialInput,output2);
708         input = processCondition(node.get_Condition(),input);
709     }while(isDifferent(lastin,input));
710
711     //handle break
712 return handleBreak(label,input,node);
713     }
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732     /*
733      * Notice ASTSwitch is horribly conservative....eg. if all cases break properly
734      * it will still merge with defaultOut which will be a NOPATH and bound to have empty or full sets
735      */
736     public Object processASTSwitchNode(ASTSwitchNode node,Object input){
737     List indexList = node.getIndexList();
738     Map index2BodyList = node.getIndex2BodyList();
739
740     Iterator it = indexList.iterator();
741     
742
743     input=processSwitchKey(node.get_Key(),input);
744     Object initialIn = cloneFlowSet(input);
745
746     Object out = null;
747     Object defaultOut = null;
748     
749     List toMergeBreaks = new ArrayList();
750
751     while (it.hasNext()) {//going through all the cases of the switch statement
752 Object currentIndex = it.next();
753         List body = (List) index2BodyList.get( currentIndex);
754
755         //BUG FIX if body is null (fall through we shouldnt invoke process
756 //Reported by Steffen Pingel 14th Jan 2006 on the soot mailing list
757 if(body != null){
758         out=process(body,input);
759         
760         // System.out.println("Breaklist for this out is"+out.getBreakList());
761 toMergeBreaks.add(cloneFlowSet(out));
762         
763         if(currentIndex instanceof String ){
764             //this is the default
765 defaultOut=out;
766         }
767
768         //the input to the next can be a fall through or directly input
769 input=merge(out,initialIn);
770         }//body was non null
771 }
772
773     //have to handle the case when no case matches. The input is the output
774 Object output=null;
775     if(out!=null){//just to make sure that there were some cases present
776
777         /*
778          * January 30th 2006, FOUND BUG
779          * The initialIn should only be merge with the out if there is no default
780          * in the list of switch cases
781          * If there is a default then there is no way that the initialIn is the actual
782          * result. Then its either the default or one of the outs!!!
783          */
784         if(defaultOut!=null){
785         //there was a default
786 //System.out.println("DEFAULTSET");
787 //System.out.println("defaultOut is"+defaultOut);
788 //System.out.println("out is"+out);
789
790         output=merge(defaultOut,out);
791         }else{
792         //there was no default so no case might match
793 output = merge(initialIn,out);
794         }
795
796     }
797     else
798         output = initialIn;
799
800     //handle break
801 String label = getLabel(node);
802
803     //have to handleBreaks for all the different cases
804
805     List outList = new ArrayList();
806     
807     //handling breakLists of each of the toMergeBreaks
808 it = toMergeBreaks.iterator();
809     while(it.hasNext()){
810         outList.add(handleBreak(label,it.next(),node));
811     }
812
813     //merge all outList elements. since these are the outputs with breaks handled
814 Object finalOut=output;
815     it = outList.iterator();
816     while(it.hasNext()){
817         finalOut = merge(finalOut,it.next());
818     }
819
820     return finalOut;
821     }
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841     public Object processASTTryNode(ASTTryNode node,Object input){
842     //System.out.println("SET beginning of tryBody is:"+input);
843 List tryBody = node.get_TryBody();
844     Object tryBodyOutput = process(tryBody,input);
845     //System.out.println("SET end of tryBody is:"+tryBodyOutput);
846
847     /*
848       By default take either top or bottom as the input to the catch statements
849       Which goes in depends on the type of analysis.
850     */
851     Object inputCatch = newInitialFlow();
852
853         List catchList = node.get_CatchList();
854         Iterator it = catchList.iterator();
855     List catchOutput = new ArrayList();
856
857     while (it.hasNext()) {
858         ASTTryNode.container catchBody = (ASTTryNode.container)it.next();
859         
860         List body = (List)catchBody.o;
861         //list of ASTNodes
862
863         //result because of going through the catchBody
864 Object tempResult = process(body,cloneFlowSet(inputCatch));
865         //System.out.println("TempResult going through body"+tempResult);
866 catchOutput.add(tempResult);
867     }
868         
869     //handle breaks
870 String label = getLabel(node);
871
872
873
874     /*
875      * 30th Jan 2005,
876      * Found bug in handling out breaks
877      * what was being done was that handleBreak was invoked using just handleBreak(label,tryBodyoutput,node)
878      * Now what it does is that it looks for the breakList stored in the tryBodyOutput node
879      * What might happen is that there might be some breaks in the catchOutput which would have gotten
880      * stored in the breakList of the respective catchoutput
881      *
882      * The correct way to handle this is create a list of handledBreak objects (in the outList)
883      * And then to merge them
884      */
885     List outList = new ArrayList();
886     
887     //handle breaks out of tryBodyOutput
888 outList.add(handleBreak(label,tryBodyOutput,node));
889     //System.out.println("After handling break from tryBodyOutput"+outList.get(0));
890
891     //handling breakLists of each of the catchOutputs
892 it = catchOutput.iterator();
893     while(it.hasNext()){
894         outList.add(handleBreak(label,it.next(),node));
895     }
896
897
898     //merge all outList elements. since these are the outputs with breaks handled
899 Object out=tryBodyOutput;
900     it = outList.iterator();
901     while(it.hasNext()){
902         out = merge(out,it.next());
903     }
904
905
906
907     //System.out.println("After handling break"+out);
908
909     it = catchOutput.iterator();
910     while(it.hasNext()){
911         out = merge(out,it.next());
912     }
913     //System.out.println("SET end of complete trycatch is:"+out);
914 return out;
915     }
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933     /*
934       MERGETYPE var has to be set
935        0, means no type set
936        1, means union
937        2, means intersection
938     */
939     public Object merge(Object obj1, Object obj2){
940     if(MERGETYPE==0)
941         throw new RuntimeException ("Use the setMergeType method to set the type of merge used in the analysis");
942
943     if( !(obj1 instanceof DavaFlowSet) || !(obj2 instanceof DavaFlowSet) ){
944         /* if(obj1 instanceof DavaFlowSet)
945           System.out.println("obj1 is a davaflowset");
946           else
947           System.out.println("obj1 is NOT a davaflowset");
948           
949           if(obj2 instanceof DavaFlowSet)
950           System.out.println("obj2 is a davaflowset");
951           else
952           System.out.println("obj2 is NOT a davaflowset"+obj2);
953         */
954
955         throw new RuntimeException ("merge not implemented for other flowSet types");
956     }
957
958     DavaFlowSet in1 = (DavaFlowSet)obj1;
959     DavaFlowSet in2 = (DavaFlowSet)obj2;
960     
961     DavaFlowSet out = new DavaFlowSet();
962     if(in1 == NOPATH && in2 != NOPATH){
963         out = (DavaFlowSet)in2.clone();
964         out.copyInternalDataFrom(in1);
965         return out;
966     }
967     else if(in1 != NOPATH && in2 == NOPATH){
968         out = (DavaFlowSet)in1.clone();
969         out.copyInternalDataFrom(in2);
970         return out;
971     }
972     else if(in1 == NOPATH && in2 == NOPATH){
973         out = (DavaFlowSet)in1.clone();
974         out.copyInternalDataFrom(in2);
975         return out; //meaning return NOPATH
976 }
977     else{//both are not NOPATH
978 if(MERGETYPE==1)//union
979 ((DavaFlowSet)obj1).union((DavaFlowSet)obj2, out);
980         else if(MERGETYPE==2)//intersection
981 ((DavaFlowSet)obj1).intersection((DavaFlowSet)obj2, out);
982         else
983         throw new RuntimeException ("Merge type value"+MERGETYPE+" not recognized");
984         out.copyInternalDataFrom(obj1);
985         out.copyInternalDataFrom(obj2);
986         return out;
987     }
988     }
989
990
991
992     public Object mergeExplicitAndImplicit(String label,DavaFlowSet output,List explicitSet, List implicitSet){
993     Object toReturn = output.clone();
994
995     if(label!=null){
996         //use the explicit list
997 /*
998           If there is no list associated with this label
999           or the list is empty
1000          there no explicit merging to be done
1001        */
1002        if(explicitSet != null && explicitSet.size()!=0){
1003        //explicitSet is a list of DavaFlowSets
1004 Iterator it = explicitSet.iterator();
1005
1006        //we know there is atleast one element
1007 toReturn = merge(output,it.next());
1008
1009        while(it.hasNext()){
1010            //merge this with toReturn
1011 toReturn = merge(toReturn,it.next());
1012        }
1013        }//a non empty explicitSet was found
1014 }//label not null could have explicit sets
1015
1016    //toReturn contains result of dealing with explicit stmts
1017
1018    //dealing with implicit set now
1019 if(implicitSet != null){
1020        //implicitSet is a list of DavaFlowSets
1021 Iterator it = implicitSet.iterator();
1022        while(it.hasNext()){
1023        //merge this with toReturn
1024 toReturn = merge(toReturn,it.next());
1025        }
1026    }
1027    return toReturn;
1028    }
1029
1030
1031
1032
1033    /**
1034     * Need to handleBreak stmts
1035     * There can be explicit breaks (in which case label is non null)
1036     * There can always be implicit breaks
1037     * ASTNode is non null
1038     */
1039    public Object handleBreak(String label,Object output,ASTNode node){
1040    if( !(output instanceof DavaFlowSet) )
1041        throw new RuntimeException ("handleBreak is only implemented for DavaFlowSet type");
1042
1043    DavaFlowSet out = (DavaFlowSet)output;
1044
1045    //get the explicit list with this label from the breakList
1046 List explicitSet = out.getBreakSet(label);
1047    //System.out.println("\n\nExplicit set is"+explicitSet);
1048 //getting the implicit list now
1049 if(node ==null)
1050        throw new RuntimeException ("ASTNode sent to handleBreak was null");
1051    
1052    List implicitSet = out.getImplicitlyBrokenSets(node);
1053    //System.out.println("\n\nImplicit set is"+implicitSet);
1054
1055    //invoke mergeExplicitAndImplicit
1056 return mergeExplicitAndImplicit(label,out,explicitSet,implicitSet);
1057    }
1058
1059
1060
1061
1062
1063
1064
1065    /**
1066     * Need to handleContinue stmts
1067     * There can be explicit continues (in which case label is non null)
1068     * There can always be implicit continues
1069     * ASTNode is non null
1070     */
1071    public Object handleContinue(String label,Object output,ASTNode node){
1072    if( !(output instanceof DavaFlowSet) )
1073        throw new RuntimeException ("handleContinue is only implemented for DavaFlowSet type");
1074
1075    DavaFlowSet out = (DavaFlowSet)output;
1076
1077    //get the explicit list with this label from the continueList
1078 List explicitSet = out.getContinueSet(label);
1079    
1080    //getting the implicit list now
1081 if(node ==null)
1082        throw new RuntimeException ("ASTNode sent to handleContinue was null");
1083    
1084    List implicitSet = out.getImplicitlyContinuedSets(node);
1085        
1086    //invoke mergeExplicitAndImplicit
1087 return mergeExplicitAndImplicit(label,out,explicitSet,implicitSet);
1088    }
1089
1090
1091
1092
1093
1094    /**
1095     * Invoked from within the UnconditionalWhile processing method
1096     * Need to handle both explicit and implicit breaks
1097     */
1098    private Object getMergedBreakList(String label,Object output,ASTNode node){
1099    if( !(output instanceof DavaFlowSet) )
1100        throw new RuntimeException ("getMergedBreakList is only implemented for DavaFlowSet type");
1101
1102    List breakSet = ((DavaFlowSet)output).getBreakSet(label);
1103    Object toReturn = null;
1104
1105    if(breakSet ==null){
1106        //there is no list associated with this label hence no merging to be done
1107 //since this is a call from unconditional this means there should have been an implicit break
1108 toReturn = NOPATH;
1109    }
1110    else if(breakSet.size()==0){
1111        //list is empty for this label hence no merging to be done
1112 //since this is a call from unconditional this means there should have been an implicit break
1113 toReturn = NOPATH;
1114    }
1115    else{
1116        //breakSet is a list of DavaFlowSets
1117 Iterator it = breakSet.iterator();
1118        
1119        //we know there is atleast one element
1120 //making sure we dont send NOPATH
1121 toReturn = it.next();
1122        
1123        while(it.hasNext()){
1124        //merge this with toReturn
1125 toReturn = merge(toReturn,it.next());
1126        }
1127    }//a non empty breakSet was found
1128
1129    //dealing with implicit set now
1130
1131    List implicitSet = ((DavaFlowSet)output).getImplicitlyBrokenSets(node);
1132    if(implicitSet != null){
1133        //implicitSet is a list of DavaFlowSets
1134 Iterator it = implicitSet.iterator();
1135
1136        //making sure that we dont send NOPATH
1137 if(implicitSet.size()>0)
1138        toReturn = it.next();
1139
1140        while(it.hasNext()){
1141        //merge this with toReturn
1142 toReturn = merge(toReturn,it.next());
1143        }
1144    }
1145    return toReturn;
1146    }
1147
1148
1149    public boolean isDifferent(Object oldObj, Object newObj){
1150       if(oldObj instanceof DavaFlowSet && newObj instanceof DavaFlowSet){
1151       if (((DavaFlowSet)oldObj).equals(newObj) && ((DavaFlowSet)oldObj).internalDataMatchesTo(newObj)){
1152           //set matches and breaks and continues also match
1153 return false;
1154       }
1155       else{
1156           //System.out.println(oldObj);
1157 //System.out.println(newObj);
1158 return true;
1159       }
1160    }
1161       else
1162        throw new RuntimeException ("isDifferent not implemented for other flowSet types");
1163    }
1164
1165
1166    public Object getBeforeSet(Object beforeThis){
1167    return beforeSets.get(beforeThis);
1168    }
1169
1170    public Object getAfterSet(Object afterThis){
1171    return afterSets.get(afterThis);
1172    }
1173}

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags