1 package Analysis.SSJava;
3 import java.util.ArrayList;
4 import java.util.Collections;
5 import java.util.Comparator;
6 import java.util.HashMap;
7 import java.util.Iterator;
11 import IR.ClassDescriptor;
13 import IR.FieldDescriptor;
14 import IR.MethodDescriptor;
16 import IR.SymbolTable;
17 import IR.VarDescriptor;
18 import IR.Tree.ArrayAccessNode;
19 import IR.Tree.AssignmentNode;
20 import IR.Tree.BlockExpressionNode;
21 import IR.Tree.BlockNode;
22 import IR.Tree.BlockStatementNode;
23 import IR.Tree.CastNode;
24 import IR.Tree.CreateObjectNode;
25 import IR.Tree.DeclarationNode;
26 import IR.Tree.ExpressionNode;
27 import IR.Tree.FieldAccessNode;
28 import IR.Tree.IfStatementNode;
30 import IR.Tree.LiteralNode;
31 import IR.Tree.LoopNode;
32 import IR.Tree.MethodInvokeNode;
33 import IR.Tree.NameNode;
34 import IR.Tree.OpNode;
35 import IR.Tree.ReturnNode;
36 import IR.Tree.SubBlockNode;
37 import IR.Tree.SwitchBlockNode;
38 import IR.Tree.SwitchStatementNode;
39 import IR.Tree.TertiaryNode;
41 public class LocationInference {
44 SSJavaAnalysis ssjava;
46 List<ClassDescriptor> toanalyzeList;
47 List<MethodDescriptor> toanalyzeMethodList;
53 public LocationInference(SSJavaAnalysis ssjava, State state) {
56 this.toanalyzeList = new ArrayList<ClassDescriptor>();
57 this.toanalyzeMethodList = new ArrayList<MethodDescriptor>();
58 this.graph = new InferGraph();
61 public void setupToAnalyze() {
62 SymbolTable classtable = state.getClassSymbolTable();
63 toanalyzeList.clear();
64 toanalyzeList.addAll(classtable.getValueSet());
65 Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
66 public int compare(ClassDescriptor o1, ClassDescriptor o2) {
67 return o1.getClassName().compareToIgnoreCase(o2.getClassName());
72 public void setupToAnalazeMethod(ClassDescriptor cd) {
74 SymbolTable methodtable = cd.getMethodTable();
75 toanalyzeMethodList.clear();
76 toanalyzeMethodList.addAll(methodtable.getValueSet());
77 Collections.sort(toanalyzeMethodList, new Comparator<MethodDescriptor>() {
78 public int compare(MethodDescriptor o1, MethodDescriptor o2) {
79 return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
84 public boolean toAnalyzeMethodIsEmpty() {
85 return toanalyzeMethodList.isEmpty();
88 public boolean toAnalyzeIsEmpty() {
89 return toanalyzeList.isEmpty();
92 public ClassDescriptor toAnalyzeNext() {
93 return toanalyzeList.remove(0);
96 public MethodDescriptor toAnalyzeMethodNext() {
97 return toanalyzeMethodList.remove(0);
100 private void checkDeclarationInClass(ClassDescriptor cd) {
101 // Check to see that fields are okay
102 for (Iterator field_it = cd.getFields(); field_it.hasNext();) {
103 FieldDescriptor fd = (FieldDescriptor) field_it.next();
105 if (!(fd.isFinal() && fd.isStatic())) {
106 analyzeFieldDeclaration(cd, fd);
108 // for static final, assign top location by default
109 graph.assignTopLocationToDescriptor(fd);
114 private void analyzeFieldDeclaration(ClassDescriptor cd, FieldDescriptor fd) {
115 graph.assignUniqueIDtoDescriptor(fd);
118 public void inference() {
120 // 1) assign a unique id to every field & variable
123 while (!toAnalyzeIsEmpty()) {
124 ClassDescriptor cd = toAnalyzeNext();
126 System.out.println("SSJAVA: Location Inference on the class: " + cd);
127 checkDeclarationInClass(cd);
129 setupToAnalazeMethod(cd);
130 while (!toAnalyzeMethodIsEmpty()) {
131 MethodDescriptor md = toAnalyzeMethodNext();
133 if (ssjava.needTobeAnnotated(md)) {
134 // assigns unique id to the method parameters
135 assignUniqueIDMethodParamteres(cd, md);
137 if (state.SSJAVADEBUG) {
138 System.out.println("SSJAVA: Location Inference on the method: " + md);
140 assignUniqueIDMethodBody(cd, md);
145 // 2) construct value flow graph
149 while (!toAnalyzeIsEmpty()) {
150 ClassDescriptor cd = toAnalyzeNext();
152 setupToAnalazeMethod(cd);
153 while (!toAnalyzeMethodIsEmpty()) {
154 MethodDescriptor md = toAnalyzeMethodNext();
155 if (ssjava.needTobeAnnotated(md)) {
156 if (state.SSJAVADEBUG) {
157 System.out.println("SSJAVA: Constructing a flow graph: " + md);
159 analyzeMethodBody(cd, md);
166 private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
167 BlockNode bn = state.getMethodBody(md);
168 // checkLocationFromBlockNode(md, md.getParameterTable(), bn, constraints);
171 private void assignUniqueIDMethodParamteres(ClassDescriptor cd, MethodDescriptor md) {
173 List<CompositeLocation> paramList = new ArrayList<CompositeLocation>();
174 for (int i = 0; i < md.numParameters(); i++) {
175 // process annotations on method parameters
176 VarDescriptor vd = (VarDescriptor) md.getParameter(i);
177 graph.assignUniqueIDtoDescriptor(vd);
182 private void assignUniqueIDMethodBody(ClassDescriptor cd, MethodDescriptor md) {
183 BlockNode bn = state.getMethodBody(md);
184 assignUniqueIDBlockNode(md, md.getParameterTable(), bn);
187 private void assignUniqueIDBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
189 bn.getVarTable().setParent(nametable);
190 for (int i = 0; i < bn.size(); i++) {
191 BlockStatementNode bsn = bn.get(i);
192 assignUniqueIDBlockStatementNode(md, bn.getVarTable(), bsn);
197 private void assignUniqueIDBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
198 BlockStatementNode bsn) {
200 switch (bsn.kind()) {
202 case Kind.DeclarationNode:
203 assignUniqueIDDeclarationNode(md, nametable, (DeclarationNode) bsn);
206 case Kind.IfStatementNode:
207 assignUniqueIDIfStatementNode(md, nametable, (IfStatementNode) bsn);
211 assignUniqueIDLoopNode(md, nametable, (LoopNode) bsn);
214 case Kind.SubBlockNode:
215 assignUniqueIDSubBlockNode(md, nametable, (SubBlockNode) bsn);
218 case Kind.ContinueBreakNode:
221 case Kind.SwitchStatementNode:
222 assignUniqueIDSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
227 private void assignUniqueIDSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
228 SwitchStatementNode ssn) {
229 BlockNode sbn = ssn.getSwitchBody();
230 for (int i = 0; i < sbn.size(); i++) {
231 SwitchBlockNode node = (SwitchBlockNode) sbn.get(i);
232 assignUniqueIDBlockNode(md, nametable, node.getSwitchBlockStatement());
236 private void assignUniqueIDSubBlockNode(MethodDescriptor md, SymbolTable nametable,
238 assignUniqueIDBlockNode(md, nametable, sbn.getBlockNode());
241 private void assignUniqueIDLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln) {
243 if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
244 assignUniqueIDBlockNode(md, nametable, ln.getBody());
246 // check 'for loop' case
247 BlockNode bn = ln.getInitializer();
248 bn.getVarTable().setParent(nametable);
249 assignUniqueIDBlockNode(md, bn.getVarTable(), ln.getUpdate());
250 assignUniqueIDBlockNode(md, bn.getVarTable(), ln.getBody());
255 private void assignUniqueIDIfStatementNode(MethodDescriptor md, SymbolTable nametable,
256 IfStatementNode isn) {
258 assignUniqueIDBlockNode(md, nametable, isn.getTrueBlock());
260 if (isn.getFalseBlock() != null) {
261 assignUniqueIDBlockNode(md, nametable, isn.getFalseBlock());
266 private void assignUniqueIDDeclarationNode(MethodDescriptor md, SymbolTable nametable,
267 DeclarationNode dn) {
269 VarDescriptor vd = dn.getVarDescriptor();
270 graph.assignUniqueIDtoDescriptor(vd);