X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FLinearTypeCheck.java;h=77b7de65ac7fce791395279587d2f816ee0a2272;hb=e7c8e9210252cff4bae7cb0551182bd179fa98a2;hp=2a6d905aa916d969be51dbf44a60ce94e519690f;hpb=82896c3e8ba574153f74dcc8bfad08748cdb86a8;p=IRC.git

diff --git a/Robust/src/Analysis/SSJava/LinearTypeCheck.java b/Robust/src/Analysis/SSJava/LinearTypeCheck.java
index 2a6d905a..77b7de65 100644
--- a/Robust/src/Analysis/SSJava/LinearTypeCheck.java
+++ b/Robust/src/Analysis/SSJava/LinearTypeCheck.java
@@ -1,16 +1,20 @@
 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;
@@ -52,22 +56,24 @@ public class LinearTypeCheck {
   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();
   }
 
@@ -84,12 +90,49 @@ public class LinearTypeCheck {
     }
 
     // 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);
+        }
       }
     }
 
@@ -129,6 +172,19 @@ public class LinearTypeCheck {
 
   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);
@@ -138,21 +194,17 @@ public class LinearTypeCheck {
       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);
   }
@@ -318,9 +370,10 @@ public class LinearTypeCheck {
     }
   }
 
-  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) {
@@ -338,8 +391,78 @@ public class LinearTypeCheck {
 
   }
 
-  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));
+        }
+
+      }
+    }
 
   }
 
@@ -366,6 +489,10 @@ public class LinearTypeCheck {
       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,
@@ -386,15 +513,19 @@ public class LinearTypeCheck {
       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;
+          }
         }
+
       }
     }
 
@@ -420,77 +551,212 @@ public class LinearTypeCheck {
     }
   }
 
-  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;
+  }
+
 }