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.Descriptor;
  13 import IR.MethodDescriptor;
  14 import IR.NameDescriptor;
  15 import IR.Operation;
  16 import IR.State;
  17 import IR.SymbolTable;
  18 import IR.TypeDescriptor;
  19 import IR.VarDescriptor;
  20 import IR.Flat.FKind;
  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;
  37 import IR.Tree.Kind;
  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;
  50
  51 public class LinearTypeCheck {
  52
  53   State state;
  54   SSJavaAnalysis ssjava;
  55   String needToNullify = null;
  56   AssignmentNode prevAssignNode;
  57
  58   Hashtable<MethodDescriptor, Set<String>> md2OwnSet;
  59
  60   Set<TreeNode> linearTypeCheckSet;
  61
  62   Hashtable<TreeNode, FlatMethod> mapTreeNode2FlatMethod;
  63
  64   Liveness liveness;
  65
  66   public LinearTypeCheck(SSJavaAnalysis ssjava, State state) {
  67     this.ssjava = ssjava;
  68     this.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();
  73   }
  74
  75   public void linearTypeCheck() {
  76
  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();
  83         parseAnnotations(md);
  84       }
  85     }
  86
  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);
  94       }
  95     }
  96
  97     // third, check if original references are destroyed after creating new
  98     // alias
  99
 100     for (Iterator<TreeNode> iterator = linearTypeCheckSet.iterator(); iterator.hasNext();) {
 101       TreeNode tn = iterator.next();
 102       Set<FlatNode> fnSet = ssjava.getBuildFlat().getFlatNodeSet(tn);
 103       if (fnSet != null) {
 104         for (Iterator iterator2 = fnSet.iterator(); iterator2.hasNext();) {
 105           FlatNode fn = (FlatNode) iterator2.next();
 106           if (isLiveOut(tn, fn)) {
 107             throw new Error(
 108                 "Local variable '"
 109                     + tn.printNode(0)
 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());
 113           }
 114
 115         }
 116       }
 117
 118     }
 119
 120   }
 121
 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());
 127     }
 128     return false;
 129   }
 130
 131   private void parseAnnotations(MethodDescriptor md) {
 132
 133     for (int i = 0; i < md.numParameters(); i++) {
 134       // process annotations on method parameters
 135       VarDescriptor vd = (VarDescriptor) md.getParameter(i);
 136
 137       Vector<AnnotationDescriptor> annotationVec = vd.getType().getAnnotationMarkers();
 138
 139       for (int anIdx = 0; anIdx < annotationVec.size(); anIdx++) {
 140         AnnotationDescriptor ad = annotationVec.elementAt(anIdx);
 141         if (ad.getMarker().equals(SSJavaAnalysis.DELEGATE)) {
 142
 143           addOwnSet(md, vd.getName());
 144           SSJavaType locationType = new SSJavaType(true);
 145           vd.getType().setExtension(locationType);
 146         }
 147       }
 148     }
 149   }
 150
 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);
 156     }
 157     ownSet.add(own);
 158   }
 159
 160   private void checkMethodBody(ClassDescriptor cd, MethodDescriptor md) {
 161     BlockNode bn = state.getMethodBody(md);
 162     checkBlockNode(md, md.getParameterTable(), bn);
 163   }
 164
 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);
 169     }
 170   }
 171
 172   private void checkBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
 173       BlockStatementNode bsn) {
 174
 175     if (needToNullify != null) {
 176       if (!checkNullifying(bsn)) {
 177         throw new Error(
 178             "Reference field '"
 179                 + needToNullify
 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());
 182       }
 183     }
 184
 185     switch (bsn.kind()) {
 186
 187     case Kind.BlockExpressionNode:
 188       checkBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
 189       return;
 190
 191     case Kind.DeclarationNode:
 192       checkDeclarationNode(md, nametable, (DeclarationNode) bsn);
 193       return;
 194
 195     case Kind.IfStatementNode:
 196       checkIfStatementNode(md, nametable, (IfStatementNode) bsn);
 197       return;
 198
 199     case Kind.SwitchStatementNode:
 200       checkSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
 201       return;
 202
 203     case Kind.LoopNode:
 204       checkLoopNode(md, nametable, (LoopNode) bsn);
 205       return;
 206
 207     case Kind.ReturnNode:
 208       checkReturnNode(md, nametable, (ReturnNode) bsn);
 209       return;
 210
 211     case Kind.SubBlockNode:
 212       checkSubBlockNode(md, nametable, (SubBlockNode) bsn);
 213       return;
 214
 215     case Kind.SynchronizedNode:
 216       checkSynchronizedNode(md, nametable, (SynchronizedNode) bsn);
 217       return;
 218     }
 219
 220   }
 221
 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());
 227   }
 228
 229   private void checkReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn) {
 230     if (rn.getReturnExpression() != null) {
 231       checkExpressionNode(md, nametable, rn.getReturnExpression());
 232     }
 233   }
 234
 235   private void checkSubBlockNode(MethodDescriptor md, SymbolTable nametable, SubBlockNode sbn) {
 236     checkBlockNode(md, nametable, sbn.getBlockNode());
 237   }
 238
 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());
 244   }
 245
 246   private void checkSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
 247       SwitchStatementNode ssn) {
 248
 249     checkExpressionNode(md, nametable, ssn.getCondition());
 250
 251     BlockNode sbn = ssn.getSwitchBody();
 252     for (int i = 0; i < sbn.size(); i++) {
 253       checkSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i));
 254     }
 255   }
 256
 257   private void checkSwitchBlockNode(MethodDescriptor md, SymbolTable nametable, SwitchBlockNode sbn) {
 258     checkBlockNode(md, nametable, sbn.getSwitchBlockStatement());
 259   }
 260
 261   private void checkBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
 262       BlockExpressionNode ben) {
 263     checkExpressionNode(md, nametable, ben.getExpression());
 264   }
 265
 266   private void checkExpressionNode(MethodDescriptor md, SymbolTable nametable, ExpressionNode en) {
 267     switch (en.kind()) {
 268     case Kind.AssignmentNode:
 269       checkAssignmentNode(md, nametable, (AssignmentNode) en);
 270       return;
 271
 272     case Kind.CastNode:
 273       checkCastNode(md, nametable, (CastNode) en);
 274       return;
 275
 276     case Kind.CreateObjectNode:
 277       checkCreateObjectNode(md, nametable, (CreateObjectNode) en);
 278       return;
 279
 280     case Kind.FieldAccessNode:
 281       checkFieldAccessNode(md, nametable, (FieldAccessNode) en);
 282       return;
 283
 284     case Kind.ArrayAccessNode:
 285       checkArrayAccessNode(md, nametable, (ArrayAccessNode) en);
 286       return;
 287
 288       // case Kind.LiteralNode:
 289       // checkLiteralNode(md, nametable, (LiteralNode) en);
 290       // return;
 291
 292     case Kind.MethodInvokeNode:
 293       checkMethodInvokeNode(md, nametable, (MethodInvokeNode) en);
 294       return;
 295
 296     case Kind.NameNode:
 297       checkNameNode(md, nametable, (NameNode) en);
 298       return;
 299
 300     case Kind.OpNode:
 301       checkOpNode(md, nametable, (OpNode) en);
 302       return;
 303
 304     case Kind.OffsetNode:
 305       checkOffsetNode(md, nametable, (OffsetNode) en);
 306       return;
 307
 308     case Kind.TertiaryNode:
 309       checkTertiaryNode(md, nametable, (TertiaryNode) en);
 310       return;
 311
 312       // case Kind.InstanceOfNode:
 313       // checkInstanceOfNode(md, nametable, (InstanceOfNode) en);
 314       // return;
 315
 316       // case Kind.ArrayInitializerNode:
 317       // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en);
 318       // return;
 319
 320       // case Kind.ClassTypeNode:
 321       // checkClassTypeNode(md, nametable, (ClassTypeNode) ens);
 322       // return;
 323     }
 324   }
 325
 326   private void checkTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode en) {
 327     // TODO Auto-generated method stub
 328
 329   }
 330
 331   private void checkOffsetNode(MethodDescriptor md, SymbolTable nametable, OffsetNode en) {
 332     // TODO Auto-generated method stub
 333
 334   }
 335
 336   private void checkOpNode(MethodDescriptor md, SymbolTable nametable, OpNode en) {
 337     // TODO Auto-generated method stub
 338
 339   }
 340
 341   private void checkNameNode(MethodDescriptor md, SymbolTable nametable, NameNode en) {
 342     // TODO Auto-generated method stub
 343
 344   }
 345
 346   private void checkMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
 347       MethodInvokeNode min) {
 348
 349     MethodDescriptor calleeMethodDesc = min.getMethod();
 350
 351     for (int i = 0; i < min.numArgs(); i++) {
 352       ExpressionNode argNode = min.getArg(i);
 353
 354       VarDescriptor paramDesc = (VarDescriptor) calleeMethodDesc.getParameter(i);
 355       TypeDescriptor paramType = calleeMethodDesc.getParamType(i);
 356
 357       if (isReference(argNode.getType())) {
 358
 359         if (argNode.kind() == Kind.NameNode) {
 360           NameNode argNN = (NameNode) argNode;
 361           NameDescriptor argNameDesc = argNN.getName();
 362
 363           if (isOwned(calleeMethodDesc, paramDesc.getName())
 364               && !isOwned(md, argNameDesc.getIdentifier())) {
 365             // method expects that argument is owned by caller
 366
 367             throw new Error("Caller passes an argument not owned by itself at " + md.getClassDesc()
 368                 + "::" + min.getNumLine());
 369
 370           }
 371
 372         }
 373
 374         md2OwnSet.get(calleeMethodDesc);
 375
 376       }
 377     }
 378
 379   }
 380
 381   private boolean isOwned(MethodDescriptor md, String id) {
 382     if (md2OwnSet.get(md) == null) {
 383       return false;
 384     } else if (md2OwnSet.get(md).contains(id)) {
 385       return true;
 386     } else {
 387       return false;
 388     }
 389   }
 390
 391   private void checkArrayAccessNode(MethodDescriptor md, SymbolTable nametable, ArrayAccessNode en) {
 392     // TODO Auto-generated method stub
 393
 394   }
 395
 396   private void checkFieldAccessNode(MethodDescriptor md, SymbolTable nametable, FieldAccessNode fan) {
 397
 398   }
 399
 400   private void checkCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
 401       CreateObjectNode con) {
 402
 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();
 408     }
 409
 410     if ((con.getArrayInitializer() != null)) {
 411       checkArrayInitializerNode(md, nametable, con.getArrayInitializer());
 412     }
 413
 414     // the current method owns a instance that it makes inside
 415     SSJavaType locationType = new SSJavaType(true);
 416     con.getType().setExtension(locationType);
 417
 418   }
 419
 420   private void checkArrayInitializerNode(MethodDescriptor md, SymbolTable nametable,
 421       ArrayInitializerNode arrayInitializer) {
 422     // TODO Auto-generated method stub
 423
 424   }
 425
 426   private void checkCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn) {
 427     ExpressionNode en = cn.getExpression();
 428     checkExpressionNode(md, nametable, en);
 429   }
 430
 431   private boolean checkNullifying(BlockStatementNode bsn) {
 432
 433     if (bsn.kind() == Kind.BlockExpressionNode) {
 434       ExpressionNode en = ((BlockExpressionNode) bsn).getExpression();
 435       if (en.kind() == Kind.AssignmentNode) {
 436         AssignmentNode an = (AssignmentNode) en;
 437
 438         String destName = an.getDest().printNode(0);
 439         if (destName.startsWith("this.")) {
 440           destName = destName.substring(5);
 441         }
 442
 443         if (an.getSrc().getType().isNull() && destName.equals(needToNullify)) {
 444           needToNullify = null;
 445           return true;
 446         }
 447       }
 448     }
 449
 450     return false;
 451   }
 452
 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());
 457     } else {
 458       // For loop case
 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);
 464       }
 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());
 469     }
 470   }
 471
 472   private void checkAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an) {
 473
 474     boolean postinc = true;
 475     if (an.getOperation().getBaseOp() == null
 476         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
 477             .getBaseOp().getOp() != Operation.POSTDEC))
 478       postinc = false;
 479
 480     if (!postinc) {
 481
 482       checkExpressionNode(md, nametable, an.getSrc());
 483
 484       if (isReference(an.getSrc().getType())) {
 485         if (an.getSrc().kind() == Kind.NameNode) {
 486
 487           NameNode nn = (NameNode) an.getSrc();
 488
 489           if (nn.getField() != null) {
 490             needToNullify = nn.getField().getSymbol();
 491             prevAssignNode = an;
 492           } else if (nn.getExpression() != null) {
 493             if (nn.getExpression() instanceof FieldAccessNode) {
 494               FieldAccessNode fan = (FieldAccessNode) nn.getExpression();
 495               needToNullify = fan.printNode(0);
 496               prevAssignNode = an;
 497
 498             }
 499
 500           } else {
 501             // local variable case
 502             linearTypeCheckSet.add(an.getSrc());
 503             mapTreeNode2FlatMethod.put(an.getSrc(), state.getMethodFlat(md));
 504           }
 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);
 510           }
 511           prevAssignNode = an;
 512         }
 513
 514         // here, transfer ownership from LHS to RHS when it creates alias
 515         if (isReference(an.getDest().getType()) && !an.getSrc().getType().isNull()) {
 516
 517           if (!isField(an.getDest())) {
 518             if (an.getDest().kind() == Kind.NameNode) {
 519               NameNode nn = ((NameNode) an.getDest());
 520               String baseId = getBase(an.getSrc());
 521
 522               if (isField(an.getSrc())) {
 523                 if (isOwned(md, baseId)) {
 524                   addOwnSet(md, nn.getName().toString());
 525                 }
 526               } else {
 527                 if (isOwned(md, an.getSrc().printNode(0))) {
 528                   addOwnSet(md, nn.getName().toString());
 529                 }
 530               }
 531             }
 532           } else {
 533             // if instance is not owned by the method, not able to store
 534             // instance
 535             // into field
 536             if (!isOwned(md, an.getSrc().printNode(0))) {
 537               throw new Error(
 538                   "Method is not allowed to store an instance not owned by itself into a field at "
 539                       + md.getClassDesc() + "::" + an.getNumLine());
 540             }
 541           }
 542
 543         }
 544       }
 545
 546     }
 547
 548   }
 549
 550   private boolean isLocationTypeOwned(SSJavaType locationType) {
 551     if (locationType != null) {
 552       return locationType.isOwned();
 553     } else {
 554       return false;
 555     }
 556   }
 557
 558   private boolean isField(ExpressionNode en) {
 559
 560     if (en.kind() == Kind.NameNode) {
 561       NameNode nn = (NameNode) en;
 562       if (nn.getField() != null) {
 563         return true;
 564       }
 565
 566       if (nn.getName() != null && nn.getName().getBase() != null) {
 567         return true;
 568       }
 569
 570     } else if (en.kind() == Kind.FieldAccessNode) {
 571       return true;
 572     }
 573     return false;
 574   }
 575
 576   private String getBase(ExpressionNode en) {
 577
 578     if (en.kind() == Kind.NameNode) {
 579       NameNode nn = (NameNode) en;
 580       if (nn.getName().getBase() != null) {
 581         return nn.getName().getBase().toString();
 582       } else {
 583         return null;
 584       }
 585     } else if (en.kind() == Kind.FieldAccessNode) {
 586       FieldAccessNode fan = (FieldAccessNode) en;
 587       return fan.getExpression().printNode(0);
 588     }
 589
 590     return null;
 591
 592   }
 593
 594   private String getVarNameFromNameNode(NameNode nn) {
 595     NameDescriptor nd = nn.getName();
 596     String varName = nd.toString();
 597     return varName;
 598   }
 599
 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());
 605       }
 606
 607     }
 608
 609   }
 610
 611   private boolean isReference(TypeDescriptor td) {
 612     if (td.isPtr() && !td.isImmutable()) {
 613       return true;
 614     }
 615     return false;
 616   }
 617
 618 }