1 package Analysis.SSJava;
3 import java.util.HashSet;
4 import java.util.Hashtable;
5 import java.util.Iterator;
7 import java.util.Vector;
9 import Analysis.Liveness;
10 import IR.AnnotationDescriptor;
11 import IR.ClassDescriptor;
13 import IR.MethodDescriptor;
14 import IR.NameDescriptor;
17 import IR.SymbolTable;
18 import IR.TypeDescriptor;
19 import IR.VarDescriptor;
21 import IR.Flat.FlatMethod;
22 import IR.Flat.FlatNode;
23 import IR.Flat.FlatOpNode;
24 import IR.Flat.TempDescriptor;
25 import IR.Tree.ArrayAccessNode;
26 import IR.Tree.ArrayInitializerNode;
27 import IR.Tree.AssignmentNode;
28 import IR.Tree.BlockExpressionNode;
29 import IR.Tree.BlockNode;
30 import IR.Tree.BlockStatementNode;
31 import IR.Tree.CastNode;
32 import IR.Tree.CreateObjectNode;
33 import IR.Tree.DeclarationNode;
34 import IR.Tree.ExpressionNode;
35 import IR.Tree.FieldAccessNode;
36 import IR.Tree.IfStatementNode;
38 import IR.Tree.LoopNode;
39 import IR.Tree.MethodInvokeNode;
40 import IR.Tree.NameNode;
41 import IR.Tree.OffsetNode;
42 import IR.Tree.OpNode;
43 import IR.Tree.ReturnNode;
44 import IR.Tree.SubBlockNode;
45 import IR.Tree.SwitchBlockNode;
46 import IR.Tree.SwitchStatementNode;
47 import IR.Tree.SynchronizedNode;
48 import IR.Tree.TertiaryNode;
49 import IR.Tree.TreeNode;
51 public class LinearTypeCheck {
54 SSJavaAnalysis ssjava;
55 String needToNullify = null;
56 AssignmentNode prevAssignNode;
58 Hashtable<MethodDescriptor, Set<String>> md2OwnSet;
60 Set<TreeNode> linearTypeCheckSet;
62 Hashtable<TreeNode, FlatMethod> mapTreeNode2FlatMethod;
66 public LinearTypeCheck(SSJavaAnalysis ssjava, State state) {
69 this.md2OwnSet = new Hashtable<MethodDescriptor, Set<String>>();
70 this.linearTypeCheckSet = new HashSet<TreeNode>();
71 this.mapTreeNode2FlatMethod = new Hashtable<TreeNode, FlatMethod>();
72 this.liveness = new Liveness();
75 public void linearTypeCheck() {
77 // first, parsing DELEGATE annotation from method declarations
78 Iterator it = state.getClassSymbolTable().getDescriptorsIterator();
79 while (it.hasNext()) {
80 ClassDescriptor cd = (ClassDescriptor) it.next();
81 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
82 MethodDescriptor md = (MethodDescriptor) method_it.next();
87 // second, check the linear type
88 it = state.getClassSymbolTable().getDescriptorsIterator();
89 while (it.hasNext()) {
90 ClassDescriptor cd = (ClassDescriptor) it.next();
91 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
92 MethodDescriptor md = (MethodDescriptor) method_it.next();
93 checkMethodBody(cd, md);
97 // third, check if original references are destroyed after creating new
100 for (Iterator<TreeNode> iterator = linearTypeCheckSet.iterator(); iterator.hasNext();) {
101 TreeNode tn = iterator.next();
102 Set<FlatNode> fnSet = ssjava.getBuildFlat().getFlatNodeSet(tn);
104 for (Iterator iterator2 = fnSet.iterator(); iterator2.hasNext();) {
105 FlatNode fn = (FlatNode) iterator2.next();
106 if (isLiveOut(tn, fn)) {
110 + "', which is read by a method, should be destroyed after introducing new alias at "
111 + mapTreeNode2FlatMethod.get(tn).getMethod().getClassDesc().getSourceFileName()
112 + "::" + tn.getNumLine());
122 private boolean isLiveOut(TreeNode tn, FlatNode fn) {
123 Set<TempDescriptor> liveOutTemp = liveness.getLiveOutTemps(mapTreeNode2FlatMethod.get(tn), fn);
124 if (fn.kind() == FKind.FlatOpNode) {
125 FlatOpNode fon = (FlatOpNode) fn;
126 return liveOutTemp.contains(fon.getLeft());
131 private void parseAnnotations(MethodDescriptor md) {
133 for (int i = 0; i < md.numParameters(); i++) {
134 // process annotations on method parameters
135 VarDescriptor vd = (VarDescriptor) md.getParameter(i);
137 Vector<AnnotationDescriptor> annotationVec = vd.getType().getAnnotationMarkers();
139 for (int anIdx = 0; anIdx < annotationVec.size(); anIdx++) {
140 AnnotationDescriptor ad = annotationVec.elementAt(anIdx);
141 if (ad.getMarker().equals(SSJavaAnalysis.DELEGATE)) {
143 addOwnSet(md, vd.getName());
144 SSJavaType locationType = new SSJavaType(true);
145 vd.getType().setExtension(locationType);
151 private void addOwnSet(MethodDescriptor md, String own) {
152 Set<String> ownSet = md2OwnSet.get(md);
153 if (ownSet == null) {
154 ownSet = new HashSet<String>();
155 md2OwnSet.put(md, ownSet);
160 private void checkMethodBody(ClassDescriptor cd, MethodDescriptor md) {
161 BlockNode bn = state.getMethodBody(md);
162 checkBlockNode(md, md.getParameterTable(), bn);
165 private void checkBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
166 for (int i = 0; i < bn.size(); i++) {
167 BlockStatementNode bsn = bn.get(i);
168 checkBlockStatementNode(md, bn.getVarTable(), bsn);
172 private void checkBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
173 BlockStatementNode bsn) {
175 if (needToNullify != null) {
176 if (!checkNullifying(bsn)) {
180 + "', which is read by a method, should be assigned to null before executing any following statement of the reference copy statement at "
181 + md.getClassDesc().getSourceFileName() + "::" + prevAssignNode.getNumLine());
185 switch (bsn.kind()) {
187 case Kind.BlockExpressionNode:
188 checkBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
191 case Kind.DeclarationNode:
192 checkDeclarationNode(md, nametable, (DeclarationNode) bsn);
195 case Kind.IfStatementNode:
196 checkIfStatementNode(md, nametable, (IfStatementNode) bsn);
199 case Kind.SwitchStatementNode:
200 checkSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
204 checkLoopNode(md, nametable, (LoopNode) bsn);
207 case Kind.ReturnNode:
208 checkReturnNode(md, nametable, (ReturnNode) bsn);
211 case Kind.SubBlockNode:
212 checkSubBlockNode(md, nametable, (SubBlockNode) bsn);
215 case Kind.SynchronizedNode:
216 checkSynchronizedNode(md, nametable, (SynchronizedNode) bsn);
222 private void checkSynchronizedNode(MethodDescriptor md, SymbolTable nametable,
223 SynchronizedNode sbn) {
224 checkBlockNode(md, nametable, sbn.getBlockNode());
225 // todo this could be Object
226 checkExpressionNode(md, nametable, sbn.getExpr());
229 private void checkReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn) {
230 if (rn.getReturnExpression() != null) {
231 checkExpressionNode(md, nametable, rn.getReturnExpression());
235 private void checkSubBlockNode(MethodDescriptor md, SymbolTable nametable, SubBlockNode sbn) {
236 checkBlockNode(md, nametable, sbn.getBlockNode());
239 private void checkIfStatementNode(MethodDescriptor md, SymbolTable nametable, IfStatementNode isn) {
240 checkExpressionNode(md, nametable, isn.getCondition());
241 checkBlockNode(md, nametable, isn.getTrueBlock());
242 if (isn.getFalseBlock() != null)
243 checkBlockNode(md, nametable, isn.getFalseBlock());
246 private void checkSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
247 SwitchStatementNode ssn) {
249 checkExpressionNode(md, nametable, ssn.getCondition());
251 BlockNode sbn = ssn.getSwitchBody();
252 for (int i = 0; i < sbn.size(); i++) {
253 checkSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i));
257 private void checkSwitchBlockNode(MethodDescriptor md, SymbolTable nametable, SwitchBlockNode sbn) {
258 checkBlockNode(md, nametable, sbn.getSwitchBlockStatement());
261 private void checkBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
262 BlockExpressionNode ben) {
263 checkExpressionNode(md, nametable, ben.getExpression());
266 private void checkExpressionNode(MethodDescriptor md, SymbolTable nametable, ExpressionNode en) {
268 case Kind.AssignmentNode:
269 checkAssignmentNode(md, nametable, (AssignmentNode) en);
273 checkCastNode(md, nametable, (CastNode) en);
276 case Kind.CreateObjectNode:
277 checkCreateObjectNode(md, nametable, (CreateObjectNode) en);
280 case Kind.FieldAccessNode:
281 checkFieldAccessNode(md, nametable, (FieldAccessNode) en);
284 case Kind.ArrayAccessNode:
285 checkArrayAccessNode(md, nametable, (ArrayAccessNode) en);
288 // case Kind.LiteralNode:
289 // checkLiteralNode(md, nametable, (LiteralNode) en);
292 case Kind.MethodInvokeNode:
293 checkMethodInvokeNode(md, nametable, (MethodInvokeNode) en);
297 checkNameNode(md, nametable, (NameNode) en);
301 checkOpNode(md, nametable, (OpNode) en);
304 case Kind.OffsetNode:
305 checkOffsetNode(md, nametable, (OffsetNode) en);
308 case Kind.TertiaryNode:
309 checkTertiaryNode(md, nametable, (TertiaryNode) en);
312 // case Kind.InstanceOfNode:
313 // checkInstanceOfNode(md, nametable, (InstanceOfNode) en);
316 // case Kind.ArrayInitializerNode:
317 // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en);
320 // case Kind.ClassTypeNode:
321 // checkClassTypeNode(md, nametable, (ClassTypeNode) ens);
326 private void checkTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode en) {
327 // TODO Auto-generated method stub
331 private void checkOffsetNode(MethodDescriptor md, SymbolTable nametable, OffsetNode en) {
332 // TODO Auto-generated method stub
336 private void checkOpNode(MethodDescriptor md, SymbolTable nametable, OpNode en) {
337 // TODO Auto-generated method stub
341 private void checkNameNode(MethodDescriptor md, SymbolTable nametable, NameNode en) {
342 // TODO Auto-generated method stub
346 private void checkMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
347 MethodInvokeNode min) {
349 MethodDescriptor calleeMethodDesc = min.getMethod();
351 for (int i = 0; i < min.numArgs(); i++) {
352 ExpressionNode argNode = min.getArg(i);
354 VarDescriptor paramDesc = (VarDescriptor) calleeMethodDesc.getParameter(i);
355 TypeDescriptor paramType = calleeMethodDesc.getParamType(i);
357 if (isReference(argNode.getType())) {
359 if (argNode.kind() == Kind.NameNode) {
360 NameNode argNN = (NameNode) argNode;
361 NameDescriptor argNameDesc = argNN.getName();
363 if (isOwned(calleeMethodDesc, paramDesc.getName())
364 && !isOwned(md, argNameDesc.getIdentifier())) {
365 // method expects that argument is owned by caller
367 throw new Error("Caller passes an argument not owned by itself at " + md.getClassDesc()
368 + "::" + min.getNumLine());
374 md2OwnSet.get(calleeMethodDesc);
381 private boolean isOwned(MethodDescriptor md, String id) {
382 if (md2OwnSet.get(md) == null) {
384 } else if (md2OwnSet.get(md).contains(id)) {
391 private void checkArrayAccessNode(MethodDescriptor md, SymbolTable nametable, ArrayAccessNode en) {
392 // TODO Auto-generated method stub
396 private void checkFieldAccessNode(MethodDescriptor md, SymbolTable nametable, FieldAccessNode fan) {
400 private void checkCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
401 CreateObjectNode con) {
403 TypeDescriptor[] tdarray = new TypeDescriptor[con.numArgs()];
404 for (int i = 0; i < con.numArgs(); i++) {
405 ExpressionNode en = con.getArg(i);
406 checkExpressionNode(md, nametable, en);
407 tdarray[i] = en.getType();
410 if ((con.getArrayInitializer() != null)) {
411 checkArrayInitializerNode(md, nametable, con.getArrayInitializer());
414 // the current method owns a instance that it makes inside
415 SSJavaType locationType = new SSJavaType(true);
416 con.getType().setExtension(locationType);
420 private void checkArrayInitializerNode(MethodDescriptor md, SymbolTable nametable,
421 ArrayInitializerNode arrayInitializer) {
422 // TODO Auto-generated method stub
426 private void checkCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn) {
427 ExpressionNode en = cn.getExpression();
428 checkExpressionNode(md, nametable, en);
431 private boolean checkNullifying(BlockStatementNode bsn) {
433 if (bsn.kind() == Kind.BlockExpressionNode) {
434 ExpressionNode en = ((BlockExpressionNode) bsn).getExpression();
435 if (en.kind() == Kind.AssignmentNode) {
436 AssignmentNode an = (AssignmentNode) en;
438 String destName = an.getDest().printNode(0);
439 if (destName.startsWith("this.")) {
440 destName = destName.substring(5);
443 if (an.getSrc().getType().isNull() && destName.equals(needToNullify)) {
444 needToNullify = null;
453 private void checkLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln) {
454 if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
455 checkExpressionNode(md, nametable, ln.getCondition());
456 checkBlockNode(md, nametable, ln.getBody());
459 /* Link in the initializer naming environment */
460 BlockNode bn = ln.getInitializer();
461 for (int i = 0; i < bn.size(); i++) {
462 BlockStatementNode bsn = bn.get(i);
463 checkBlockStatementNode(md, bn.getVarTable(), bsn);
465 // check the condition
466 checkExpressionNode(md, bn.getVarTable(), ln.getCondition());
467 checkBlockNode(md, bn.getVarTable(), ln.getBody());
468 checkBlockNode(md, bn.getVarTable(), ln.getUpdate());
472 private void checkAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an) {
474 boolean postinc = true;
475 if (an.getOperation().getBaseOp() == null
476 || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
477 .getBaseOp().getOp() != Operation.POSTDEC))
482 checkExpressionNode(md, nametable, an.getSrc());
484 if (isReference(an.getSrc().getType())) {
485 if (an.getSrc().kind() == Kind.NameNode) {
487 NameNode nn = (NameNode) an.getSrc();
489 if (nn.getField() != null) {
490 needToNullify = nn.getField().getSymbol();
492 } else if (nn.getExpression() != null) {
493 if (nn.getExpression() instanceof FieldAccessNode) {
494 FieldAccessNode fan = (FieldAccessNode) nn.getExpression();
495 needToNullify = fan.printNode(0);
501 // local variable case
502 linearTypeCheckSet.add(an.getSrc());
503 mapTreeNode2FlatMethod.put(an.getSrc(), state.getMethodFlat(md));
505 } else if (an.getSrc().kind() == Kind.FieldAccessNode) {
506 FieldAccessNode fan = (FieldAccessNode) an.getSrc();
507 needToNullify = fan.printNode(0);
508 if (needToNullify.startsWith("this.")) {
509 needToNullify = needToNullify.substring(5);
514 // here, transfer ownership from LHS to RHS when it creates alias
515 if (isReference(an.getDest().getType()) && !an.getSrc().getType().isNull()) {
517 if (!isField(an.getDest())) {
518 if (an.getDest().kind() == Kind.NameNode) {
519 NameNode nn = ((NameNode) an.getDest());
520 String baseId = getBase(an.getSrc());
522 if (isField(an.getSrc())) {
523 if (isOwned(md, baseId)) {
524 addOwnSet(md, nn.getName().toString());
527 if (isOwned(md, an.getSrc().printNode(0))) {
528 addOwnSet(md, nn.getName().toString());
533 // if instance is not owned by the method, not able to store
536 if (!isOwned(md, an.getSrc().printNode(0))) {
538 "Method is not allowed to store an instance not owned by itself into a field at "
539 + md.getClassDesc() + "::" + an.getNumLine());
550 private boolean isLocationTypeOwned(SSJavaType locationType) {
551 if (locationType != null) {
552 return locationType.isOwned();
558 private boolean isField(ExpressionNode en) {
560 if (en.kind() == Kind.NameNode) {
561 NameNode nn = (NameNode) en;
562 if (nn.getField() != null) {
566 if (nn.getName() != null && nn.getName().getBase() != null) {
570 } else if (en.kind() == Kind.FieldAccessNode) {
576 private String getBase(ExpressionNode en) {
578 if (en.kind() == Kind.NameNode) {
579 NameNode nn = (NameNode) en;
580 if (nn.getName().getBase() != null) {
581 return nn.getName().getBase().toString();
585 } else if (en.kind() == Kind.FieldAccessNode) {
586 FieldAccessNode fan = (FieldAccessNode) en;
587 return fan.getExpression().printNode(0);
594 private String getVarNameFromNameNode(NameNode nn) {
595 NameDescriptor nd = nn.getName();
596 String varName = nd.toString();
600 private void checkDeclarationNode(MethodDescriptor md, SymbolTable nametable, DeclarationNode dn) {
601 if (dn.getExpression() != null) {
602 checkExpressionNode(md, nametable, dn.getExpression());
603 if (dn.getExpression().kind() == Kind.CreateObjectNode) {
604 addOwnSet(md, dn.getVarDescriptor().getName());
611 private boolean isReference(TypeDescriptor td) {
612 if (td.isPtr() && !td.isImmutable()) {