1 package Analysis.SSJava;
3 import java.util.ArrayList;
4 import java.util.Collections;
5 import java.util.Comparator;
6 import java.util.HashSet;
7 import java.util.Hashtable;
8 import java.util.Iterator;
11 import java.util.Vector;
13 import Analysis.Liveness;
14 import IR.AnnotationDescriptor;
15 import IR.ClassDescriptor;
16 import IR.FieldDescriptor;
17 import IR.MethodDescriptor;
20 import IR.SymbolTable;
21 import IR.TypeDescriptor;
22 import IR.VarDescriptor;
24 import IR.Flat.FlatMethod;
25 import IR.Flat.FlatNode;
26 import IR.Flat.FlatOpNode;
27 import IR.Flat.TempDescriptor;
28 import IR.Tree.ArrayAccessNode;
29 import IR.Tree.ArrayInitializerNode;
30 import IR.Tree.AssignmentNode;
31 import IR.Tree.BlockExpressionNode;
32 import IR.Tree.BlockNode;
33 import IR.Tree.BlockStatementNode;
34 import IR.Tree.CastNode;
35 import IR.Tree.CreateObjectNode;
36 import IR.Tree.DeclarationNode;
37 import IR.Tree.ExpressionNode;
38 import IR.Tree.FieldAccessNode;
39 import IR.Tree.IfStatementNode;
41 import IR.Tree.LoopNode;
42 import IR.Tree.MethodInvokeNode;
43 import IR.Tree.NameNode;
44 import IR.Tree.OffsetNode;
45 import IR.Tree.OpNode;
46 import IR.Tree.ReturnNode;
47 import IR.Tree.SubBlockNode;
48 import IR.Tree.SwitchBlockNode;
49 import IR.Tree.SwitchStatementNode;
50 import IR.Tree.SynchronizedNode;
51 import IR.Tree.TertiaryNode;
52 import IR.Tree.TreeNode;
54 public class LinearTypeCheck {
57 SSJavaAnalysis ssjava;
58 String needToNullify = null;
59 TreeNode prevAssignNode;
61 Set<TreeNode> linearTypeCheckSet;
63 Hashtable<TreeNode, FlatMethod> mapTreeNode2FlatMethod;
65 Set<MethodDescriptor> delegateThisMethodSet;
69 boolean deterministic = true;
71 public LinearTypeCheck(SSJavaAnalysis ssjava, State state) {
74 this.linearTypeCheckSet = new HashSet<TreeNode>();
75 this.mapTreeNode2FlatMethod = new Hashtable<TreeNode, FlatMethod>();
76 this.delegateThisMethodSet = new HashSet<MethodDescriptor>();
77 this.liveness = new Liveness();
80 public void linearTypeCheck() {
82 // first, parsing DELEGATE annotation from method declarations
83 Iterator it = state.getClassSymbolTable().getDescriptorsIterator();
84 while (it.hasNext()) {
85 ClassDescriptor cd = (ClassDescriptor) it.next();
86 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
87 MethodDescriptor md = (MethodDescriptor) method_it.next();
92 // second, check the linear type
95 SymbolTable classtable = state.getClassSymbolTable();
97 List<ClassDescriptor> toanalyzeList = new ArrayList<ClassDescriptor>();
98 List<MethodDescriptor> toanalyzeMethodList = new ArrayList<MethodDescriptor>();
100 toanalyzeList.addAll(classtable.getValueSet());
101 Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
102 public int compare(ClassDescriptor o1, ClassDescriptor o2) {
103 return o1.getClassName().compareTo(o2.getClassName());
107 for (int i = 0; i < toanalyzeList.size(); i++) {
108 ClassDescriptor cd = toanalyzeList.get(i);
110 SymbolTable methodtable = cd.getMethodTable();
111 toanalyzeMethodList.clear();
112 toanalyzeMethodList.addAll(methodtable.getValueSet());
113 Collections.sort(toanalyzeMethodList, new Comparator<MethodDescriptor>() {
114 public int compare(MethodDescriptor o1, MethodDescriptor o2) {
115 return o1.getSymbol().compareTo(o2.getSymbol());
119 for (int mdIdx = 0; mdIdx < toanalyzeMethodList.size(); mdIdx++) {
120 MethodDescriptor md = toanalyzeMethodList.get(mdIdx);
121 if (ssjava.needToCheckLinearType(md)) {
122 checkMethodBody(cd, md);
129 it = state.getClassSymbolTable().getDescriptorsIterator();
130 while (it.hasNext()) {
131 ClassDescriptor cd = (ClassDescriptor) it.next();
132 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
133 MethodDescriptor md = (MethodDescriptor) method_it.next();
134 checkMethodBody(cd, md);
139 // third, check if original references are destroyed after creating new
142 for (Iterator<TreeNode> iterator = linearTypeCheckSet.iterator(); iterator.hasNext();) {
143 TreeNode tn = iterator.next();
144 Set<FlatNode> fnSet = ssjava.getBuildFlat().getFlatNodeSet(tn);
146 for (Iterator iterator2 = fnSet.iterator(); iterator2.hasNext();) {
147 FlatNode fn = (FlatNode) iterator2.next();
148 if (isLiveOut(tn, fn)) {
152 + "', which is read by a method, should be destroyed after introducing new alias at "
153 + mapTreeNode2FlatMethod.get(tn).getMethod().getClassDesc().getSourceFileName()
154 + "::" + tn.getNumLine());
164 private boolean isLiveOut(TreeNode tn, FlatNode fn) {
165 Set<TempDescriptor> liveOutTemp = liveness.getLiveOutTemps(mapTreeNode2FlatMethod.get(tn), fn);
166 if (fn.kind() == FKind.FlatOpNode) {
167 FlatOpNode fon = (FlatOpNode) fn;
168 return liveOutTemp.contains(fon.getLeft());
173 private void parseAnnotations(MethodDescriptor md) {
175 // method annotation parsing
176 Vector<AnnotationDescriptor> methodAnnotations = md.getModifiers().getAnnotations();
177 if (methodAnnotations != null) {
178 for (int i = 0; i < methodAnnotations.size(); i++) {
179 AnnotationDescriptor an = methodAnnotations.elementAt(i);
180 if (an.getMarker().equals(ssjava.DELEGATETHIS)) {
181 delegateThisMethodSet.add(md);
182 md.getThis().getType().setExtension(new SSJavaType(true));
187 // paramter annotation parsing
188 for (int i = 0; i < md.numParameters(); i++) {
189 // process annotations on method parameters
190 VarDescriptor vd = (VarDescriptor) md.getParameter(i);
192 Vector<AnnotationDescriptor> annotationVec = vd.getType().getAnnotationMarkers();
194 for (int anIdx = 0; anIdx < annotationVec.size(); anIdx++) {
195 AnnotationDescriptor ad = annotationVec.elementAt(anIdx);
196 if (ad.getMarker().equals(SSJavaAnalysis.DELEGATE)) {
197 SSJavaType locationType = new SSJavaType(true);
198 vd.getType().setExtension(locationType);
204 private void checkMethodBody(ClassDescriptor cd, MethodDescriptor md) {
205 if (state.SSJAVADEBUG) {
206 System.out.println("SSJAVA: Linear Type Checking: " + md);
208 BlockNode bn = state.getMethodBody(md);
209 checkBlockNode(md, md.getParameterTable(), bn);
212 private void checkBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
213 for (int i = 0; i < bn.size(); i++) {
214 BlockStatementNode bsn = bn.get(i);
215 checkBlockStatementNode(md, bn.getVarTable(), bsn);
219 private void checkBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
220 BlockStatementNode bsn) {
222 if (needToNullify != null) {
223 if (!checkNullifying(bsn)) {
227 + "', which is read by a method, should be assigned to null before executing any following statement of the reference copy statement at "
228 + md.getClassDesc().getSourceFileName() + "::" + prevAssignNode.getNumLine());
232 switch (bsn.kind()) {
234 case Kind.BlockExpressionNode:
235 checkBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
238 case Kind.DeclarationNode:
239 checkDeclarationNode(md, nametable, (DeclarationNode) bsn);
242 case Kind.IfStatementNode:
243 checkIfStatementNode(md, nametable, (IfStatementNode) bsn);
246 case Kind.SwitchStatementNode:
247 checkSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
251 checkLoopNode(md, nametable, (LoopNode) bsn);
254 case Kind.ReturnNode:
255 checkReturnNode(md, nametable, (ReturnNode) bsn);
258 case Kind.SubBlockNode:
259 checkSubBlockNode(md, nametable, (SubBlockNode) bsn);
262 case Kind.SynchronizedNode:
263 checkSynchronizedNode(md, nametable, (SynchronizedNode) bsn);
269 private void checkSynchronizedNode(MethodDescriptor md, SymbolTable nametable,
270 SynchronizedNode sbn) {
271 checkBlockNode(md, nametable, sbn.getBlockNode());
272 // todo this could be Object
273 checkExpressionNode(md, nametable, sbn.getExpr());
276 private void checkReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn) {
277 if (rn.getReturnExpression() != null) {
278 checkExpressionNode(md, nametable, rn.getReturnExpression());
282 private void checkSubBlockNode(MethodDescriptor md, SymbolTable nametable, SubBlockNode sbn) {
283 checkBlockNode(md, nametable, sbn.getBlockNode());
286 private void checkIfStatementNode(MethodDescriptor md, SymbolTable nametable, IfStatementNode isn) {
287 checkExpressionNode(md, nametable, isn.getCondition());
288 checkBlockNode(md, nametable, isn.getTrueBlock());
289 if (isn.getFalseBlock() != null)
290 checkBlockNode(md, nametable, isn.getFalseBlock());
293 private void checkSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
294 SwitchStatementNode ssn) {
296 checkExpressionNode(md, nametable, ssn.getCondition());
298 BlockNode sbn = ssn.getSwitchBody();
299 for (int i = 0; i < sbn.size(); i++) {
300 checkSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i));
304 private void checkSwitchBlockNode(MethodDescriptor md, SymbolTable nametable, SwitchBlockNode sbn) {
305 checkBlockNode(md, nametable, sbn.getSwitchBlockStatement());
308 private void checkBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
309 BlockExpressionNode ben) {
310 checkExpressionNode(md, nametable, ben.getExpression());
313 private void checkExpressionNode(MethodDescriptor md, SymbolTable nametable, ExpressionNode en) {
315 case Kind.AssignmentNode:
316 checkAssignmentNode(md, nametable, (AssignmentNode) en);
320 checkCastNode(md, nametable, (CastNode) en);
323 case Kind.CreateObjectNode:
324 checkCreateObjectNode(md, nametable, (CreateObjectNode) en);
327 case Kind.FieldAccessNode:
328 checkFieldAccessNode(md, nametable, (FieldAccessNode) en);
331 case Kind.ArrayAccessNode:
332 checkArrayAccessNode(md, nametable, (ArrayAccessNode) en);
335 // case Kind.LiteralNode:
336 // checkLiteralNode(md, nametable, (LiteralNode) en);
339 case Kind.MethodInvokeNode:
340 checkMethodInvokeNode(md, nametable, (MethodInvokeNode) en);
344 checkNameNode(md, nametable, (NameNode) en);
348 checkOpNode(md, nametable, (OpNode) en);
351 case Kind.OffsetNode:
352 checkOffsetNode(md, nametable, (OffsetNode) en);
355 case Kind.TertiaryNode:
356 checkTertiaryNode(md, nametable, (TertiaryNode) en);
359 // case Kind.InstanceOfNode:
360 // checkInstanceOfNode(md, nametable, (InstanceOfNode) en);
363 // case Kind.ArrayInitializerNode:
364 // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en);
367 // case Kind.ClassTypeNode:
368 // checkClassTypeNode(md, nametable, (ClassTypeNode) ens);
373 private void checkTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn) {
374 checkExpressionNode(md, nametable, tn.getCond());
375 checkExpressionNode(md, nametable, tn.getTrueExpr());
376 checkExpressionNode(md, nametable, tn.getFalseExpr());
379 private void checkOffsetNode(MethodDescriptor md, SymbolTable nametable, OffsetNode en) {
380 // TODO Auto-generated method stub
384 private void checkOpNode(MethodDescriptor md, SymbolTable nametable, OpNode en) {
385 // TODO Auto-generated method stub
389 private void checkNameNode(MethodDescriptor md, SymbolTable nametable, NameNode en) {
390 // TODO Auto-generated method stub
394 private boolean isOwned(VarDescriptor varDesc) {
395 if (varDesc.getType().getExtension() != null) {
396 SSJavaType locationType = (SSJavaType) varDesc.getType().getExtension();
397 return locationType.isOwned();
402 private void checkMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
403 MethodInvokeNode min) {
405 MethodDescriptor calleeMethodDesc = min.getMethod();
407 // check delegate_this annotation
408 // only method that owns itself 'THIS' can call method with delegate_this
411 if (delegateThisMethodSet.contains(calleeMethodDesc)) {
413 if (min.getBaseName() == null) {
414 if (!delegateThisMethodSet.contains(md)) {
415 throw new Error("Caller does not own the 'THIS' argument at " + md.getClassDesc() + "::"
419 VarDescriptor baseVar = (VarDescriptor) nametable.get(min.getBaseName().getIdentifier());
420 if (!isOwned(baseVar)) {
421 throw new Error("Caller does not own the 'THIS' argument at " + md.getClassDesc() + "::"
427 // check delegate parameter annotation
428 for (int i = 0; i < min.numArgs(); i++) {
429 ExpressionNode argNode = min.getArg(i);
431 TypeDescriptor paramType = calleeMethodDesc.getParamType(i);
433 if (isReference(argNode.getType()) && !argNode.getType().isNull()) {
435 boolean isParamOwnedByCallee = false;
436 if (paramType.getExtension() != null) {
437 SSJavaType locationType = (SSJavaType) paramType.getExtension();
438 isParamOwnedByCallee = locationType.isOwned();
441 TypeDescriptor argType = getTypeDescriptor(argNode);
443 if (isParamOwnedByCallee) {
445 // cannot pass field reference through ownership transition
446 if (isField(argNode)) {
447 throw new Error("Caller cannot transfer its ownership of the field reference at "
448 + md.getClassDesc() + "::" + min.getNumLine());
451 // method expects that argument is owned by caller
452 SSJavaType locationType = (SSJavaType) argType.getExtension();
454 if (locationType == null || !locationType.isOwned()) {
455 throw new Error("Caller passes an argument not owned by itself at " + md.getClassDesc()
456 + "::" + min.getNumLine());
459 // delegated arg is no longer to be available from here
460 linearTypeCheckSet.add(argNode);
461 mapTreeNode2FlatMethod.put(argNode, state.getMethodFlat(md));
469 private void checkArrayAccessNode(MethodDescriptor md, SymbolTable nametable, ArrayAccessNode en) {
470 // TODO Auto-generated method stub
474 private void checkFieldAccessNode(MethodDescriptor md, SymbolTable nametable, FieldAccessNode fan) {
478 private void checkCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
479 CreateObjectNode con) {
481 TypeDescriptor[] tdarray = new TypeDescriptor[con.numArgs()];
482 for (int i = 0; i < con.numArgs(); i++) {
483 ExpressionNode en = con.getArg(i);
484 checkExpressionNode(md, nametable, en);
485 tdarray[i] = en.getType();
488 if ((con.getArrayInitializer() != null)) {
489 checkArrayInitializerNode(md, nametable, con.getArrayInitializer());
492 // the current method owns a instance that it makes inside
493 SSJavaType locationType = new SSJavaType(true);
494 con.getType().setExtension(locationType);
498 private void checkArrayInitializerNode(MethodDescriptor md, SymbolTable nametable,
499 ArrayInitializerNode arrayInitializer) {
500 // TODO Auto-generated method stub
504 private void checkCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn) {
505 ExpressionNode en = cn.getExpression();
506 checkExpressionNode(md, nametable, en);
509 private boolean checkNullifying(BlockStatementNode bsn) {
511 if (bsn.kind() == Kind.BlockExpressionNode) {
512 ExpressionNode en = ((BlockExpressionNode) bsn).getExpression();
513 if (en.kind() == Kind.AssignmentNode) {
514 AssignmentNode an = (AssignmentNode) en;
516 boolean postinc = isPostIncAssignment(an);
519 String destName = an.getDest().printNode(0);
520 if (destName.startsWith("this.")) {
521 destName = destName.substring(5);
523 if (an.getSrc().getType().isNull() && destName.equals(needToNullify)) {
524 needToNullify = null;
535 private void checkLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln) {
536 if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
537 checkExpressionNode(md, nametable, ln.getCondition());
538 checkBlockNode(md, nametable, ln.getBody());
541 /* Link in the initializer naming environment */
542 BlockNode bn = ln.getInitializer();
543 for (int i = 0; i < bn.size(); i++) {
544 BlockStatementNode bsn = bn.get(i);
545 checkBlockStatementNode(md, bn.getVarTable(), bsn);
547 // check the condition
548 checkExpressionNode(md, bn.getVarTable(), ln.getCondition());
549 checkBlockNode(md, bn.getVarTable(), ln.getBody());
550 checkBlockNode(md, bn.getVarTable(), ln.getUpdate());
554 public boolean isPostIncAssignment(AssignmentNode an) {
555 if (an.getOperation().getBaseOp() == null
556 || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
557 .getBaseOp().getOp() != Operation.POSTDEC)) {
564 private void checkAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an) {
566 boolean postinc = isPostIncAssignment(an);
569 checkExpressionNode(md, nametable, an.getSrc());
570 if (isReference(an.getSrc().getType()) && isReference(an.getDest().getType())) {
571 checkAlias(md, an, an.getSrc());
578 private boolean isFieldOfClass(ClassDescriptor classDesc, String varName) {
579 return classDesc.getFieldTable().contains(varName);
582 private boolean isCreatingAlias(ExpressionNode en) {
584 int kind = en.kind();
585 if (kind == Kind.NameNode || kind == Kind.ArrayAccessNode || kind == Kind.FieldAccessNode) {
592 private TypeDescriptor getTypeDescriptor(ExpressionNode en) {
593 if (en.kind() == Kind.NameNode) {
594 NameNode nn = (NameNode) en;
595 if (nn.getField() != null) {
596 return nn.getVar().getType();
597 } else if (nn.getVar() != null) {
598 return nn.getVar().getType();
600 return getTypeDescriptor(nn.getExpression());
602 } else if (en.kind() == Kind.FieldAccessNode) {
603 FieldAccessNode fan = (FieldAccessNode) en;
604 return getTypeDescriptor(fan.getExpression());
605 } else if (en.kind() == Kind.CreateObjectNode) {
606 CreateObjectNode con = (CreateObjectNode) en;
607 return con.getType();
608 } else if (en.kind() == Kind.ArrayAccessNode) {
609 ArrayAccessNode aan = (ArrayAccessNode) en;
610 return aan.getExpression().getType();
616 private FieldDescriptor getFieldDescriptorFromExpressionNode(ExpressionNode en) {
618 if (en.kind() == Kind.NameNode) {
619 NameNode nn = (NameNode) en;
620 if (nn.getField() != null) {
621 return nn.getField();
624 if (nn.getName() != null && nn.getName().getBase() != null) {
625 return getFieldDescriptorFromExpressionNode(nn.getExpression());
628 } else if (en.kind() == Kind.FieldAccessNode) {
629 FieldAccessNode fan = (FieldAccessNode) en;
630 return fan.getField();
636 private boolean isField(ExpressionNode en) {
638 if (en.kind() == Kind.NameNode) {
639 NameNode nn = (NameNode) en;
640 if (nn.getField() != null) {
644 if (nn.getName() != null && nn.getName().getBase() != null) {
648 } else if (en.kind() == Kind.FieldAccessNode) {
654 private void checkAlias(MethodDescriptor md, TreeNode node, ExpressionNode src) {
656 if (src.kind() == Kind.NameNode) {
658 NameNode nn = (NameNode) src;
660 if (nn.getField() != null) {
661 needToNullify = nn.getField().getSymbol();
662 prevAssignNode = node;
663 } else if (nn.getExpression() != null) {
664 if (nn.getExpression() instanceof FieldAccessNode) {
665 FieldAccessNode fan = (FieldAccessNode) nn.getExpression();
666 needToNullify = fan.printNode(0);
667 prevAssignNode = node;
670 // local variable case
671 linearTypeCheckSet.add(src);
672 mapTreeNode2FlatMethod.put(src, state.getMethodFlat(md));
674 } else if (src.kind() == Kind.FieldAccessNode) {
675 FieldAccessNode fan = (FieldAccessNode) src;
676 needToNullify = fan.printNode(0);
677 if (needToNullify.startsWith("this.")) {
678 needToNullify = needToNullify.substring(5);
680 prevAssignNode = node;
681 } else if (src.kind() == Kind.ArrayAccessNode) {
682 ArrayAccessNode aan = (ArrayAccessNode) src;
683 TypeDescriptor srcType = src.getType();
684 if (srcType.isPtr() && srcType.getArrayCount() > 0) {
686 "Not allowed to create an alias to the middle of the multidimensional array at "
687 + md.getClassDesc().getSourceFileName() + "::" + node.getNumLine());
689 needToNullify = aan.printNode(0);
690 prevAssignNode = node;
692 } else if (src.kind() == Kind.CreateObjectNode || src.kind() == Kind.MethodInvokeNode
693 || src.kind() == Kind.ArrayInitializerNode || src.kind() == Kind.LiteralNode) {
694 if (node.kind() == Kind.DeclarationNode) {
695 DeclarationNode dn = (DeclarationNode) node;
696 dn.getVarDescriptor().getType().setExtension(new SSJavaType(true));
699 throw new Error("Not allowed this type of assignment at "
700 + md.getClassDesc().getSourceFileName() + "::" + node.getNumLine());
703 if (isCreatingAlias(src)) {
705 TypeDescriptor srcType = getTypeDescriptor(src);
706 boolean isSourceOwned = false;
708 if (srcType.getExtension() != null) {
709 SSJavaType srcLocationType = (SSJavaType) srcType.getExtension();
710 isSourceOwned = srcLocationType.isOwned();
714 ssjava.setFieldOnwership(md, getFieldDescriptorFromExpressionNode(src));
718 } else if (md.isConstructor() && isFieldOfClass(md.getClassDesc(), src.printNode(0))) {
719 isSourceOwned = true;
720 ssjava.setFieldOnwership(md, getFieldDescriptorFromExpressionNode(src));
723 if (node.kind() == Kind.AssignmentNode) {
724 AssignmentNode an = (AssignmentNode) node;
725 if (isField(an.getDest())) {
726 // if instance is not owned by the method, not able to store
727 // instance into field
728 if (!isSourceOwned) {
730 "Method is not allowed to store an instance not owned by itself into a field at "
731 + md.getClassDesc().getSourceFileName() + "::" + node.getNumLine());
735 // here, transfer ownership from LHS to RHS when it creates alias
736 TypeDescriptor destType = getTypeDescriptor(an.getDest());
737 destType.setExtension(new SSJavaType(isSourceOwned));
746 private void checkDeclarationNode(MethodDescriptor md, SymbolTable nametable, DeclarationNode dn) {
747 if (dn.getExpression() != null) {
748 ExpressionNode src = dn.getExpression();
749 if (isReference(src.getType())) {
750 checkAlias(md, dn, src);
755 private boolean isReference(TypeDescriptor td) {
756 if (td.isPtr() && (!td.isString())) {