package Analysis.SSJava;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
+import java.util.List;
import java.util.Set;
import java.util.Vector;
import Analysis.Liveness;
import IR.AnnotationDescriptor;
import IR.ClassDescriptor;
+import IR.FieldDescriptor;
import IR.MethodDescriptor;
-import IR.NameDescriptor;
import IR.Operation;
import IR.State;
import IR.SymbolTable;
State state;
SSJavaAnalysis ssjava;
String needToNullify = null;
- AssignmentNode prevAssignNode;
-
- Hashtable<MethodDescriptor, Set<VarDescriptor>> md2DelegateParamSet;
+ TreeNode prevAssignNode;
Set<TreeNode> linearTypeCheckSet;
Hashtable<TreeNode, FlatMethod> mapTreeNode2FlatMethod;
+ Set<MethodDescriptor> delegateThisMethodSet;
+
Liveness liveness;
+ boolean deterministic = true;
+
public LinearTypeCheck(SSJavaAnalysis ssjava, State state) {
this.ssjava = ssjava;
this.state = state;
- this.md2DelegateParamSet = new Hashtable<MethodDescriptor, Set<VarDescriptor>>();
this.linearTypeCheckSet = new HashSet<TreeNode>();
this.mapTreeNode2FlatMethod = new Hashtable<TreeNode, FlatMethod>();
+ this.delegateThisMethodSet = new HashSet<MethodDescriptor>();
this.liveness = new Liveness();
}
}
// second, check the linear type
- it = state.getClassSymbolTable().getDescriptorsIterator();
- while (it.hasNext()) {
- ClassDescriptor cd = (ClassDescriptor) it.next();
- for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
- MethodDescriptor md = (MethodDescriptor) method_it.next();
- checkMethodBody(cd, md);
+ if (deterministic) {
+
+ SymbolTable classtable = state.getClassSymbolTable();
+
+ List<ClassDescriptor> toanalyzeList = new ArrayList<ClassDescriptor>();
+ List<MethodDescriptor> toanalyzeMethodList = new ArrayList<MethodDescriptor>();
+
+ toanalyzeList.addAll(classtable.getValueSet());
+ Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
+ public int compare(ClassDescriptor o1, ClassDescriptor o2) {
+ return o1.getClassName().compareTo(o2.getClassName());
+ }
+ });
+
+ for (int i = 0; i < toanalyzeList.size(); i++) {
+ ClassDescriptor cd = toanalyzeList.get(i);
+
+ SymbolTable methodtable = cd.getMethodTable();
+ toanalyzeMethodList.clear();
+ toanalyzeMethodList.addAll(methodtable.getValueSet());
+ Collections.sort(toanalyzeMethodList, new Comparator<MethodDescriptor>() {
+ public int compare(MethodDescriptor o1, MethodDescriptor o2) {
+ return o1.getSymbol().compareTo(o2.getSymbol());
+ }
+ });
+
+ for (int mdIdx = 0; mdIdx < toanalyzeMethodList.size(); mdIdx++) {
+ MethodDescriptor md = toanalyzeMethodList.get(mdIdx);
+ if (ssjava.needToCheckLinearType(md)) {
+ checkMethodBody(cd, md);
+ }
+ }
+
+ }
+
+ } else {
+ it = state.getClassSymbolTable().getDescriptorsIterator();
+ while (it.hasNext()) {
+ ClassDescriptor cd = (ClassDescriptor) it.next();
+ for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
+ MethodDescriptor md = (MethodDescriptor) method_it.next();
+ checkMethodBody(cd, md);
+ }
}
}
private void parseAnnotations(MethodDescriptor md) {
+ // method annotation parsing
+ Vector<AnnotationDescriptor> methodAnnotations = md.getModifiers().getAnnotations();
+ if (methodAnnotations != null) {
+ for (int i = 0; i < methodAnnotations.size(); i++) {
+ AnnotationDescriptor an = methodAnnotations.elementAt(i);
+ if (an.getMarker().equals(ssjava.DELEGATETHIS)) {
+ delegateThisMethodSet.add(md);
+ md.getThis().getType().setExtension(new SSJavaType(true));
+ }
+ }
+ }
+
+ // paramter annotation parsing
for (int i = 0; i < md.numParameters(); i++) {
// process annotations on method parameters
VarDescriptor vd = (VarDescriptor) md.getParameter(i);
for (int anIdx = 0; anIdx < annotationVec.size(); anIdx++) {
AnnotationDescriptor ad = annotationVec.elementAt(anIdx);
if (ad.getMarker().equals(SSJavaAnalysis.DELEGATE)) {
-
- Set<VarDescriptor> delegateSet = md2DelegateParamSet.get(md);
- if (delegateSet == null) {
- delegateSet = new HashSet<VarDescriptor>();
- md2DelegateParamSet.put(md, delegateSet);
- }
- delegateSet.add(vd);
+ SSJavaType locationType = new SSJavaType(true);
+ vd.getType().setExtension(locationType);
}
}
-
}
-
}
private void checkMethodBody(ClassDescriptor cd, MethodDescriptor md) {
+ if (state.SSJAVADEBUG) {
+ System.out.println("SSJAVA: Linear Type Checking: " + md);
+ }
BlockNode bn = state.getMethodBody(md);
checkBlockNode(md, md.getParameterTable(), bn);
}
}
}
- private void checkTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode en) {
- // TODO Auto-generated method stub
-
+ private void checkTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn) {
+ checkExpressionNode(md, nametable, tn.getCond());
+ checkExpressionNode(md, nametable, tn.getTrueExpr());
+ checkExpressionNode(md, nametable, tn.getFalseExpr());
}
private void checkOffsetNode(MethodDescriptor md, SymbolTable nametable, OffsetNode en) {
}
- private void checkMethodInvokeNode(MethodDescriptor md, SymbolTable nametable, MethodInvokeNode en) {
- // TODO Auto-generated method stub
+ private boolean isOwned(VarDescriptor varDesc) {
+ if (varDesc.getType().getExtension() != null) {
+ SSJavaType locationType = (SSJavaType) varDesc.getType().getExtension();
+ return locationType.isOwned();
+ }
+ return false;
+ }
+
+ private void checkMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
+ MethodInvokeNode min) {
+
+ MethodDescriptor calleeMethodDesc = min.getMethod();
+
+ // check delegate_this annotation
+ // only method that owns itself 'THIS' can call method with delegate_this
+ // annotation
+
+ if (delegateThisMethodSet.contains(calleeMethodDesc)) {
+
+ if (min.getBaseName() == null) {
+ if (!delegateThisMethodSet.contains(md)) {
+ throw new Error("Caller does not own the 'THIS' argument at " + md.getClassDesc() + "::"
+ + min.getNumLine());
+ }
+ } else {
+ VarDescriptor baseVar = (VarDescriptor) nametable.get(min.getBaseName().getIdentifier());
+ if (!isOwned(baseVar)) {
+ throw new Error("Caller does not own the 'THIS' argument at " + md.getClassDesc() + "::"
+ + min.getNumLine());
+ }
+ }
+ }
+
+ // check delegate parameter annotation
+ for (int i = 0; i < min.numArgs(); i++) {
+ ExpressionNode argNode = min.getArg(i);
+
+ TypeDescriptor paramType = calleeMethodDesc.getParamType(i);
+
+ if (isReference(argNode.getType()) && !argNode.getType().isNull()) {
+
+ boolean isParamOwnedByCallee = false;
+ if (paramType.getExtension() != null) {
+ SSJavaType locationType = (SSJavaType) paramType.getExtension();
+ isParamOwnedByCallee = locationType.isOwned();
+ }
+
+ TypeDescriptor argType = getTypeDescriptor(argNode);
+
+ if (isParamOwnedByCallee) {
+
+ // cannot pass field reference through ownership transition
+ if (isField(argNode)) {
+ throw new Error("Caller cannot transfer its ownership of the field reference at "
+ + md.getClassDesc() + "::" + min.getNumLine());
+ }
+
+ // method expects that argument is owned by caller
+ SSJavaType locationType = (SSJavaType) argType.getExtension();
+
+ if (locationType == null || !locationType.isOwned()) {
+ throw new Error("Caller passes an argument not owned by itself at " + md.getClassDesc()
+ + "::" + min.getNumLine());
+ }
+
+ // delegated arg is no longer to be available from here
+ linearTypeCheckSet.add(argNode);
+ mapTreeNode2FlatMethod.put(argNode, state.getMethodFlat(md));
+ }
+
+ }
+ }
}
checkArrayInitializerNode(md, nametable, con.getArrayInitializer());
}
+ // the current method owns a instance that it makes inside
+ SSJavaType locationType = new SSJavaType(true);
+ con.getType().setExtension(locationType);
+
}
private void checkArrayInitializerNode(MethodDescriptor md, SymbolTable nametable,
if (en.kind() == Kind.AssignmentNode) {
AssignmentNode an = (AssignmentNode) en;
- String destName = an.getDest().printNode(0);
- if (destName.startsWith("this.")) {
- destName = destName.substring(5);
- }
+ boolean postinc = isPostIncAssignment(an);
- if (an.getSrc().getType().isNull() && destName.equals(needToNullify)) {
- needToNullify = null;
- return true;
+ if (!postinc) {
+ String destName = an.getDest().printNode(0);
+ if (destName.startsWith("this.")) {
+ destName = destName.substring(5);
+ }
+ if (an.getSrc().getType().isNull() && destName.equals(needToNullify)) {
+ needToNullify = null;
+ return true;
+ }
}
+
}
}
}
}
- private void checkAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an) {
-
- boolean postinc = true;
+ public boolean isPostIncAssignment(AssignmentNode an) {
if (an.getOperation().getBaseOp() == null
|| (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
- .getBaseOp().getOp() != Operation.POSTDEC))
- postinc = false;
+ .getBaseOp().getOp() != Operation.POSTDEC)) {
+ return false;
+ } else {
+ return true;
+ }
+ }
- if (!postinc) {
- if (!an.getSrc().getType().isImmutable()) {
- if (an.getSrc().kind() == Kind.NameNode) {
-
- NameNode nn = (NameNode) an.getSrc();
-
- if (nn.getField() != null) {
- needToNullify = nn.getField().getSymbol();
- prevAssignNode = an;
- } else if (nn.getExpression() != null) {
- if (nn.getExpression() instanceof FieldAccessNode) {
- FieldAccessNode fan = (FieldAccessNode) nn.getExpression();
- needToNullify = fan.printNode(0);
- prevAssignNode = an;
-
- }
-
- } else {
- // local variable case
- linearTypeCheckSet.add(an.getSrc());
- mapTreeNode2FlatMethod.put(an.getSrc(), state.getMethodFlat(md));
- }
- } else if (an.getSrc().kind() == Kind.FieldAccessNode) {
- FieldAccessNode fan = (FieldAccessNode) an.getSrc();
- needToNullify = fan.printNode(0);
- if (needToNullify.startsWith("this.")) {
- needToNullify = needToNullify.substring(5);
- }
- prevAssignNode = an;
- }
+ private void checkAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an) {
+ boolean postinc = isPostIncAssignment(an);
+
+ if (!postinc) {
+ checkExpressionNode(md, nametable, an.getSrc());
+ if (isReference(an.getSrc().getType()) && isReference(an.getDest().getType())) {
+ checkAlias(md, an, an.getSrc());
}
+
}
- // needToNullify(an.getSrc());
}
- private String getVarNameFromNameNode(NameNode nn) {
- NameDescriptor nd = nn.getName();
- String varName = nd.toString();
- return varName;
+ private boolean isFieldOfClass(ClassDescriptor classDesc, String varName) {
+ return classDesc.getFieldTable().contains(varName);
}
- private void checkDeclarationNode(MethodDescriptor md, SymbolTable nametable, DeclarationNode dn) {
- if (dn.getExpression() != null) {
- checkExpressionNode(md, nametable, dn.getExpression());
+ private boolean isCreatingAlias(ExpressionNode en) {
+
+ int kind = en.kind();
+ if (kind == Kind.NameNode || kind == Kind.ArrayAccessNode || kind == Kind.FieldAccessNode) {
+ return true;
+ }
+ return false;
+
+ }
+
+ private TypeDescriptor getTypeDescriptor(ExpressionNode en) {
+ if (en.kind() == Kind.NameNode) {
+ NameNode nn = (NameNode) en;
+ if (nn.getField() != null) {
+ return nn.getVar().getType();
+ } else if (nn.getVar() != null) {
+ return nn.getVar().getType();
+ } else {
+ return getTypeDescriptor(nn.getExpression());
+ }
+ } else if (en.kind() == Kind.FieldAccessNode) {
+ FieldAccessNode fan = (FieldAccessNode) en;
+ return getTypeDescriptor(fan.getExpression());
+ } else if (en.kind() == Kind.CreateObjectNode) {
+ CreateObjectNode con = (CreateObjectNode) en;
+ return con.getType();
+ } else if (en.kind() == Kind.ArrayAccessNode) {
+ ArrayAccessNode aan = (ArrayAccessNode) en;
+ return aan.getExpression().getType();
+ }
+
+ return null;
+ }
+
+ private FieldDescriptor getFieldDescriptorFromExpressionNode(ExpressionNode en) {
+
+ if (en.kind() == Kind.NameNode) {
+ NameNode nn = (NameNode) en;
+ if (nn.getField() != null) {
+ return nn.getField();
+ }
+
+ if (nn.getName() != null && nn.getName().getBase() != null) {
+ return getFieldDescriptorFromExpressionNode(nn.getExpression());
+ }
+
+ } else if (en.kind() == Kind.FieldAccessNode) {
+ FieldAccessNode fan = (FieldAccessNode) en;
+ return fan.getField();
}
- // needToNullify(dn.getExpression());
+ return null;
}
- private void needToNullify(ExpressionNode en) {
+ private boolean isField(ExpressionNode en) {
+
+ if (en.kind() == Kind.NameNode) {
+ NameNode nn = (NameNode) en;
+ if (nn.getField() != null) {
+ return true;
+ }
+
+ if (nn.getName() != null && nn.getName().getBase() != null) {
+ return true;
+ }
+
+ } else if (en.kind() == Kind.FieldAccessNode) {
+ return true;
+ }
+ return false;
+ }
- if (en != null && en.getType().isPtr() && !en.getType().isString()) {
- if (en.kind() != Kind.CreateObjectNode && en.kind() != Kind.LiteralNode) {
- if (en.kind() == Kind.CastNode) {
- needToNullify = ((CastNode) en).getExpression().printNode(0);
+ private void checkAlias(MethodDescriptor md, TreeNode node, ExpressionNode src) {
+
+ if (src.kind() == Kind.NameNode) {
+
+ NameNode nn = (NameNode) src;
+
+ if (nn.getField() != null) {
+ needToNullify = nn.getField().getSymbol();
+ prevAssignNode = node;
+ } else if (nn.getExpression() != null) {
+ if (nn.getExpression() instanceof FieldAccessNode) {
+ FieldAccessNode fan = (FieldAccessNode) nn.getExpression();
+ needToNullify = fan.printNode(0);
+ prevAssignNode = node;
+ }
+ } else {
+ // local variable case
+ linearTypeCheckSet.add(src);
+ mapTreeNode2FlatMethod.put(src, state.getMethodFlat(md));
+ }
+ } else if (src.kind() == Kind.FieldAccessNode) {
+ FieldAccessNode fan = (FieldAccessNode) src;
+ needToNullify = fan.printNode(0);
+ if (needToNullify.startsWith("this.")) {
+ needToNullify = needToNullify.substring(5);
+ }
+ prevAssignNode = node;
+ } else if (src.kind() == Kind.ArrayAccessNode) {
+ ArrayAccessNode aan = (ArrayAccessNode) src;
+ TypeDescriptor srcType = src.getType();
+ if (srcType.isPtr() && srcType.getArrayCount() > 0) {
+ throw new Error(
+ "Not allowed to create an alias to the middle of the multidimensional array at "
+ + md.getClassDesc().getSourceFileName() + "::" + node.getNumLine());
+ } else {
+ needToNullify = aan.printNode(0);
+ prevAssignNode = node;
+ }
+ } else if (src.kind() == Kind.CreateObjectNode || src.kind() == Kind.MethodInvokeNode
+ || src.kind() == Kind.ArrayInitializerNode || src.kind() == Kind.LiteralNode) {
+ if (node.kind() == Kind.DeclarationNode) {
+ DeclarationNode dn = (DeclarationNode) node;
+ dn.getVarDescriptor().getType().setExtension(new SSJavaType(true));
+ }
+ } else {
+ throw new Error("Not allowed this type of assignment at "
+ + md.getClassDesc().getSourceFileName() + "::" + node.getNumLine());
+ }
+
+ if (isCreatingAlias(src)) {
+
+ TypeDescriptor srcType = getTypeDescriptor(src);
+ boolean isSourceOwned = false;
+
+ if (srcType.getExtension() != null) {
+ SSJavaType srcLocationType = (SSJavaType) srcType.getExtension();
+ isSourceOwned = srcLocationType.isOwned();
+
+ if (isSourceOwned) {
+ if (isField(src)) {
+ ssjava.setFieldOnwership(md, getFieldDescriptorFromExpressionNode(src));
+ }
+ }
+
+ } else if (md.isConstructor() && isFieldOfClass(md.getClassDesc(), src.printNode(0))) {
+ isSourceOwned = true;
+ ssjava.setFieldOnwership(md, getFieldDescriptorFromExpressionNode(src));
+ }
+
+ if (node.kind() == Kind.AssignmentNode) {
+ AssignmentNode an = (AssignmentNode) node;
+ if (isField(an.getDest())) {
+ // if instance is not owned by the method, not able to store
+ // instance into field
+ if (!isSourceOwned) {
+ throw new Error(
+ "Method is not allowed to store an instance not owned by itself into a field at "
+ + md.getClassDesc().getSourceFileName() + "::" + node.getNumLine());
+ }
} else {
- needToNullify = en.printNode(0);
+ if (isSourceOwned) {
+ // here, transfer ownership from LHS to RHS when it creates alias
+ TypeDescriptor destType = getTypeDescriptor(an.getDest());
+ destType.setExtension(new SSJavaType(isSourceOwned));
+ }
}
}
+
}
}
+ private void checkDeclarationNode(MethodDescriptor md, SymbolTable nametable, DeclarationNode dn) {
+ if (dn.getExpression() != null) {
+ ExpressionNode src = dn.getExpression();
+ if (isReference(src.getType())) {
+ checkAlias(md, dn, src);
+ }
+ }
+ }
+
+ private boolean isReference(TypeDescriptor td) {
+ if (td.isPtr() && (!td.isString())) {
+ return true;
+ }
+ return false;
+ }
+
}
projects / IRC.git / blobdiff