Robust/src/Analysis/SSJava/LinearTypeCheck.java

   1 package Analysis.SSJava;
   2
   3 import java.util.HashSet;
   4 import java.util.Hashtable;
   5 import java.util.Iterator;
   6 import java.util.Set;
   7 import java.util.Vector;
   8
   9 import Analysis.Liveness;
  10 import IR.AnnotationDescriptor;
  11 import IR.ClassDescriptor;
  12 import IR.MethodDescriptor;
  13 import IR.NameDescriptor;
  14 import IR.Operation;
  15 import IR.State;
  16 import IR.SymbolTable;
  17 import IR.TypeDescriptor;
  18 import IR.VarDescriptor;
  19 import IR.Flat.FKind;
  20 import IR.Flat.FlatMethod;
  21 import IR.Flat.FlatNode;
  22 import IR.Flat.FlatOpNode;
  23 import IR.Flat.TempDescriptor;
  24 import IR.Tree.ArrayAccessNode;
  25 import IR.Tree.ArrayInitializerNode;
  26 import IR.Tree.AssignmentNode;
  27 import IR.Tree.BlockExpressionNode;
  28 import IR.Tree.BlockNode;
  29 import IR.Tree.BlockStatementNode;
  30 import IR.Tree.CastNode;
  31 import IR.Tree.CreateObjectNode;
  32 import IR.Tree.DeclarationNode;
  33 import IR.Tree.ExpressionNode;
  34 import IR.Tree.FieldAccessNode;
  35 import IR.Tree.IfStatementNode;
  36 import IR.Tree.Kind;
  37 import IR.Tree.LoopNode;
  38 import IR.Tree.MethodInvokeNode;
  39 import IR.Tree.NameNode;
  40 import IR.Tree.OffsetNode;
  41 import IR.Tree.OpNode;
  42 import IR.Tree.ReturnNode;
  43 import IR.Tree.SubBlockNode;
  44 import IR.Tree.SwitchBlockNode;
  45 import IR.Tree.SwitchStatementNode;
  46 import IR.Tree.SynchronizedNode;
  47 import IR.Tree.TertiaryNode;
  48 import IR.Tree.TreeNode;
  49
  50 public class LinearTypeCheck {
  51
  52   State state;
  53   SSJavaAnalysis ssjava;
  54   String needToNullify = null;
  55   AssignmentNode prevAssignNode;
  56
  57   Hashtable<MethodDescriptor, Set<VarDescriptor>> md2DelegateParamSet;
  58
  59   Set<TreeNode> linearTypeCheckSet;
  60
  61   Hashtable<TreeNode, FlatMethod> mapTreeNode2FlatMethod;
  62
  63   Liveness liveness;
  64
  65   public LinearTypeCheck(SSJavaAnalysis ssjava, State state) {
  66     this.ssjava = ssjava;
  67     this.state = state;
  68     this.md2DelegateParamSet = new Hashtable<MethodDescriptor, Set<VarDescriptor>>();
  69     this.linearTypeCheckSet = new HashSet<TreeNode>();
  70     this.mapTreeNode2FlatMethod = new Hashtable<TreeNode, FlatMethod>();
  71     this.liveness = new Liveness();
  72   }
  73
  74   public void linearTypeCheck() {
  75
  76     // first, parsing DELEGATE annotation from method declarations
  77     Iterator it = state.getClassSymbolTable().getDescriptorsIterator();
  78     while (it.hasNext()) {
  79       ClassDescriptor cd = (ClassDescriptor) it.next();
  80       for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
  81         MethodDescriptor md = (MethodDescriptor) method_it.next();
  82         parseAnnotations(md);
  83       }
  84     }
  85
  86     // second, check the linear type
  87     it = state.getClassSymbolTable().getDescriptorsIterator();
  88     while (it.hasNext()) {
  89       ClassDescriptor cd = (ClassDescriptor) it.next();
  90       for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
  91         MethodDescriptor md = (MethodDescriptor) method_it.next();
  92         checkMethodBody(cd, md);
  93       }
  94     }
  95
  96     // third, check if original references are destroyed after creating new
  97     // alias
  98
  99     for (Iterator<TreeNode> iterator = linearTypeCheckSet.iterator(); iterator.hasNext();) {
 100       TreeNode tn = iterator.next();
 101       Set<FlatNode> fnSet = ssjava.getBuildFlat().getFlatNodeSet(tn);
 102       if (fnSet != null) {
 103         for (Iterator iterator2 = fnSet.iterator(); iterator2.hasNext();) {
 104           FlatNode fn = (FlatNode) iterator2.next();
 105           if (isLiveOut(tn, fn)) {
 106             throw new Error(
 107                 "Local variable '"
 108                     + tn.printNode(0)
 109                     + "', which is read by a method, should be destroyed after introducing new alias at "
 110                     + mapTreeNode2FlatMethod.get(tn).getMethod().getClassDesc().getSourceFileName()
 111                     + "::" + tn.getNumLine());
 112           }
 113
 114         }
 115       }
 116
 117     }
 118
 119   }
 120
 121   private boolean isLiveOut(TreeNode tn, FlatNode fn) {
 122     Set<TempDescriptor> liveOutTemp = liveness.getLiveOutTemps(mapTreeNode2FlatMethod.get(tn), fn);
 123     if (fn.kind() == FKind.FlatOpNode) {
 124       FlatOpNode fon = (FlatOpNode) fn;
 125       return liveOutTemp.contains(fon.getLeft());
 126     }
 127     return false;
 128   }
 129
 130   private void parseAnnotations(MethodDescriptor md) {
 131
 132     for (int i = 0; i < md.numParameters(); i++) {
 133       // process annotations on method parameters
 134       VarDescriptor vd = (VarDescriptor) md.getParameter(i);
 135
 136       Vector<AnnotationDescriptor> annotationVec = vd.getType().getAnnotationMarkers();
 137
 138       for (int anIdx = 0; anIdx < annotationVec.size(); anIdx++) {
 139         AnnotationDescriptor ad = annotationVec.elementAt(anIdx);
 140         if (ad.getMarker().equals(SSJavaAnalysis.DELEGATE)) {
 141
 142           Set<VarDescriptor> delegateSet = md2DelegateParamSet.get(md);
 143           if (delegateSet == null) {
 144             delegateSet = new HashSet<VarDescriptor>();
 145             md2DelegateParamSet.put(md, delegateSet);
 146           }
 147           delegateSet.add(vd);
 148         }
 149       }
 150
 151     }
 152
 153   }
 154
 155   private void checkMethodBody(ClassDescriptor cd, MethodDescriptor md) {
 156     BlockNode bn = state.getMethodBody(md);
 157     checkBlockNode(md, md.getParameterTable(), bn);
 158   }
 159
 160   private void checkBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
 161     for (int i = 0; i < bn.size(); i++) {
 162       BlockStatementNode bsn = bn.get(i);
 163       checkBlockStatementNode(md, bn.getVarTable(), bsn);
 164     }
 165   }
 166
 167   private void checkBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
 168       BlockStatementNode bsn) {
 169
 170     if (needToNullify != null) {
 171       if (!checkNullifying(bsn)) {
 172         throw new Error(
 173             "Reference field '"
 174                 + needToNullify
 175                 + "', which is read by a method, should be assigned to null before executing any following statement of the reference copy statement at "
 176                 + md.getClassDesc().getSourceFileName() + "::" + prevAssignNode.getNumLine());
 177       }
 178     }
 179
 180     switch (bsn.kind()) {
 181
 182     case Kind.BlockExpressionNode:
 183       checkBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
 184       return;
 185
 186     case Kind.DeclarationNode:
 187       checkDeclarationNode(md, nametable, (DeclarationNode) bsn);
 188       return;
 189
 190     case Kind.IfStatementNode:
 191       checkIfStatementNode(md, nametable, (IfStatementNode) bsn);
 192       return;
 193
 194     case Kind.SwitchStatementNode:
 195       checkSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
 196       return;
 197
 198     case Kind.LoopNode:
 199       checkLoopNode(md, nametable, (LoopNode) bsn);
 200       return;
 201
 202     case Kind.ReturnNode:
 203       checkReturnNode(md, nametable, (ReturnNode) bsn);
 204       return;
 205
 206     case Kind.SubBlockNode:
 207       checkSubBlockNode(md, nametable, (SubBlockNode) bsn);
 208       return;
 209
 210     case Kind.SynchronizedNode:
 211       checkSynchronizedNode(md, nametable, (SynchronizedNode) bsn);
 212       return;
 213     }
 214
 215   }
 216
 217   private void checkSynchronizedNode(MethodDescriptor md, SymbolTable nametable,
 218       SynchronizedNode sbn) {
 219     checkBlockNode(md, nametable, sbn.getBlockNode());
 220     // todo this could be Object
 221     checkExpressionNode(md, nametable, sbn.getExpr());
 222   }
 223
 224   private void checkReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn) {
 225     if (rn.getReturnExpression() != null) {
 226       checkExpressionNode(md, nametable, rn.getReturnExpression());
 227     }
 228   }
 229
 230   private void checkSubBlockNode(MethodDescriptor md, SymbolTable nametable, SubBlockNode sbn) {
 231     checkBlockNode(md, nametable, sbn.getBlockNode());
 232   }
 233
 234   private void checkIfStatementNode(MethodDescriptor md, SymbolTable nametable, IfStatementNode isn) {
 235     checkExpressionNode(md, nametable, isn.getCondition());
 236     checkBlockNode(md, nametable, isn.getTrueBlock());
 237     if (isn.getFalseBlock() != null)
 238       checkBlockNode(md, nametable, isn.getFalseBlock());
 239   }
 240
 241   private void checkSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
 242       SwitchStatementNode ssn) {
 243
 244     checkExpressionNode(md, nametable, ssn.getCondition());
 245
 246     BlockNode sbn = ssn.getSwitchBody();
 247     for (int i = 0; i < sbn.size(); i++) {
 248       checkSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i));
 249     }
 250   }
 251
 252   private void checkSwitchBlockNode(MethodDescriptor md, SymbolTable nametable, SwitchBlockNode sbn) {
 253     checkBlockNode(md, nametable, sbn.getSwitchBlockStatement());
 254   }
 255
 256   private void checkBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
 257       BlockExpressionNode ben) {
 258     checkExpressionNode(md, nametable, ben.getExpression());
 259   }
 260
 261   private void checkExpressionNode(MethodDescriptor md, SymbolTable nametable, ExpressionNode en) {
 262     switch (en.kind()) {
 263     case Kind.AssignmentNode:
 264       checkAssignmentNode(md, nametable, (AssignmentNode) en);
 265       return;
 266
 267     case Kind.CastNode:
 268       checkCastNode(md, nametable, (CastNode) en);
 269       return;
 270
 271     case Kind.CreateObjectNode:
 272       checkCreateObjectNode(md, nametable, (CreateObjectNode) en);
 273       return;
 274
 275     case Kind.FieldAccessNode:
 276       checkFieldAccessNode(md, nametable, (FieldAccessNode) en);
 277       return;
 278
 279     case Kind.ArrayAccessNode:
 280       checkArrayAccessNode(md, nametable, (ArrayAccessNode) en);
 281       return;
 282
 283       // case Kind.LiteralNode:
 284       // checkLiteralNode(md, nametable, (LiteralNode) en);
 285       // return;
 286
 287     case Kind.MethodInvokeNode:
 288       checkMethodInvokeNode(md, nametable, (MethodInvokeNode) en);
 289       return;
 290
 291     case Kind.NameNode:
 292       checkNameNode(md, nametable, (NameNode) en);
 293       return;
 294
 295     case Kind.OpNode:
 296       checkOpNode(md, nametable, (OpNode) en);
 297       return;
 298
 299     case Kind.OffsetNode:
 300       checkOffsetNode(md, nametable, (OffsetNode) en);
 301       return;
 302
 303     case Kind.TertiaryNode:
 304       checkTertiaryNode(md, nametable, (TertiaryNode) en);
 305       return;
 306
 307       // case Kind.InstanceOfNode:
 308       // checkInstanceOfNode(md, nametable, (InstanceOfNode) en);
 309       // return;
 310
 311       // case Kind.ArrayInitializerNode:
 312       // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en);
 313       // return;
 314
 315       // case Kind.ClassTypeNode:
 316       // checkClassTypeNode(md, nametable, (ClassTypeNode) ens);
 317       // return;
 318     }
 319   }
 320
 321   private void checkTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode en) {
 322     // TODO Auto-generated method stub
 323
 324   }
 325
 326   private void checkOffsetNode(MethodDescriptor md, SymbolTable nametable, OffsetNode en) {
 327     // TODO Auto-generated method stub
 328
 329   }
 330
 331   private void checkOpNode(MethodDescriptor md, SymbolTable nametable, OpNode en) {
 332     // TODO Auto-generated method stub
 333
 334   }
 335
 336   private void checkNameNode(MethodDescriptor md, SymbolTable nametable, NameNode en) {
 337     // TODO Auto-generated method stub
 338
 339   }
 340
 341   private void checkMethodInvokeNode(MethodDescriptor md, SymbolTable nametable, MethodInvokeNode en) {
 342     // TODO Auto-generated method stub
 343
 344   }
 345
 346   private void checkArrayAccessNode(MethodDescriptor md, SymbolTable nametable, ArrayAccessNode en) {
 347     // TODO Auto-generated method stub
 348
 349   }
 350
 351   private void checkFieldAccessNode(MethodDescriptor md, SymbolTable nametable, FieldAccessNode fan) {
 352
 353   }
 354
 355   private void checkCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
 356       CreateObjectNode con) {
 357
 358     TypeDescriptor[] tdarray = new TypeDescriptor[con.numArgs()];
 359     for (int i = 0; i < con.numArgs(); i++) {
 360       ExpressionNode en = con.getArg(i);
 361       checkExpressionNode(md, nametable, en);
 362       tdarray[i] = en.getType();
 363     }
 364
 365     if ((con.getArrayInitializer() != null)) {
 366       checkArrayInitializerNode(md, nametable, con.getArrayInitializer());
 367     }
 368
 369   }
 370
 371   private void checkArrayInitializerNode(MethodDescriptor md, SymbolTable nametable,
 372       ArrayInitializerNode arrayInitializer) {
 373     // TODO Auto-generated method stub
 374
 375   }
 376
 377   private void checkCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn) {
 378     ExpressionNode en = cn.getExpression();
 379     checkExpressionNode(md, nametable, en);
 380   }
 381
 382   private boolean checkNullifying(BlockStatementNode bsn) {
 383
 384     if (bsn.kind() == Kind.BlockExpressionNode) {
 385       ExpressionNode en = ((BlockExpressionNode) bsn).getExpression();
 386       if (en.kind() == Kind.AssignmentNode) {
 387         AssignmentNode an = (AssignmentNode) en;
 388
 389         String destName = an.getDest().printNode(0);
 390         if (destName.startsWith("this.")) {
 391           destName = destName.substring(5);
 392         }
 393
 394         if (an.getSrc().getType().isNull() && destName.equals(needToNullify)) {
 395           needToNullify = null;
 396           return true;
 397         }
 398       }
 399     }
 400
 401     return false;
 402   }
 403
 404   private void checkLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln) {
 405     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
 406       checkExpressionNode(md, nametable, ln.getCondition());
 407       checkBlockNode(md, nametable, ln.getBody());
 408     } else {
 409       // For loop case
 410       /* Link in the initializer naming environment */
 411       BlockNode bn = ln.getInitializer();
 412       for (int i = 0; i < bn.size(); i++) {
 413         BlockStatementNode bsn = bn.get(i);
 414         checkBlockStatementNode(md, bn.getVarTable(), bsn);
 415       }
 416       // check the condition
 417       checkExpressionNode(md, bn.getVarTable(), ln.getCondition());
 418       checkBlockNode(md, bn.getVarTable(), ln.getBody());
 419       checkBlockNode(md, bn.getVarTable(), ln.getUpdate());
 420     }
 421   }
 422
 423   private void checkAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an) {
 424
 425     boolean postinc = true;
 426     if (an.getOperation().getBaseOp() == null
 427         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
 428             .getBaseOp().getOp() != Operation.POSTDEC))
 429       postinc = false;
 430
 431     if (!postinc) {
 432       if (!an.getSrc().getType().isImmutable()) {
 433         if (an.getSrc().kind() == Kind.NameNode) {
 434
 435           NameNode nn = (NameNode) an.getSrc();
 436
 437           if (nn.getField() != null) {
 438             needToNullify = nn.getField().getSymbol();
 439             prevAssignNode = an;
 440           } else if (nn.getExpression() != null) {
 441             if (nn.getExpression() instanceof FieldAccessNode) {
 442               FieldAccessNode fan = (FieldAccessNode) nn.getExpression();
 443               needToNullify = fan.printNode(0);
 444               prevAssignNode = an;
 445
 446             }
 447
 448           } else {
 449             // local variable case
 450             linearTypeCheckSet.add(an.getSrc());
 451             mapTreeNode2FlatMethod.put(an.getSrc(), state.getMethodFlat(md));
 452           }
 453         } else if (an.getSrc().kind() == Kind.FieldAccessNode) {
 454           FieldAccessNode fan = (FieldAccessNode) an.getSrc();
 455           needToNullify = fan.printNode(0);
 456           if (needToNullify.startsWith("this.")) {
 457             needToNullify = needToNullify.substring(5);
 458           }
 459           prevAssignNode = an;
 460         }
 461
 462       }
 463     }
 464
 465     // needToNullify(an.getSrc());
 466   }
 467
 468   private String getVarNameFromNameNode(NameNode nn) {
 469     NameDescriptor nd = nn.getName();
 470     String varName = nd.toString();
 471     return varName;
 472   }
 473
 474   private void checkDeclarationNode(MethodDescriptor md, SymbolTable nametable, DeclarationNode dn) {
 475     if (dn.getExpression() != null) {
 476       checkExpressionNode(md, nametable, dn.getExpression());
 477     }
 478
 479     // needToNullify(dn.getExpression());
 480   }
 481
 482   private void needToNullify(ExpressionNode en) {
 483
 484     if (en != null && en.getType().isPtr() && !en.getType().isString()) {
 485       if (en.kind() != Kind.CreateObjectNode && en.kind() != Kind.LiteralNode) {
 486         if (en.kind() == Kind.CastNode) {
 487           needToNullify = ((CastNode) en).getExpression().printNode(0);
 488         } else {
 489           needToNullify = en.printNode(0);
 490         }
 491       }
 492     }
 493
 494   }
 495
 496 }