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.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   Set<TreeNode> linearTypeCheckSet;
  58
  59   Hashtable<TreeNode, FlatMethod> mapTreeNode2FlatMethod;
  60
  61   Set<MethodDescriptor> delegateThisMethodSet;
  62
  63   Liveness liveness;
  64
  65   public LinearTypeCheck(SSJavaAnalysis ssjava, State state) {
  66     this.ssjava = ssjava;
  67     this.state = state;
  68     this.linearTypeCheckSet = new HashSet<TreeNode>();
  69     this.mapTreeNode2FlatMethod = new Hashtable<TreeNode, FlatMethod>();
  70     this.delegateThisMethodSet = new HashSet<MethodDescriptor>();
  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     // method annotation parsing
 133     Vector<AnnotationDescriptor> methodAnnotations = md.getModifiers().getAnnotations();
 134     if (methodAnnotations != null) {
 135       for (int i = 0; i < methodAnnotations.size(); i++) {
 136         AnnotationDescriptor an = methodAnnotations.elementAt(i);
 137         if (an.getMarker().equals(ssjava.DELEGATETHIS)) {
 138           delegateThisMethodSet.add(md);
 139           md.getThis().getType().setExtension(new SSJavaType(true));
 140         }
 141       }
 142     }
 143
 144     // paramter annotation parsing
 145     for (int i = 0; i < md.numParameters(); i++) {
 146       // process annotations on method parameters
 147       VarDescriptor vd = (VarDescriptor) md.getParameter(i);
 148
 149       Vector<AnnotationDescriptor> annotationVec = vd.getType().getAnnotationMarkers();
 150
 151       for (int anIdx = 0; anIdx < annotationVec.size(); anIdx++) {
 152         AnnotationDescriptor ad = annotationVec.elementAt(anIdx);
 153         if (ad.getMarker().equals(SSJavaAnalysis.DELEGATE)) {
 154           SSJavaType locationType = new SSJavaType(true);
 155           vd.getType().setExtension(locationType);
 156         }
 157       }
 158     }
 159   }
 160
 161   private void checkMethodBody(ClassDescriptor cd, MethodDescriptor md) {
 162     BlockNode bn = state.getMethodBody(md);
 163     checkBlockNode(md, md.getParameterTable(), bn);
 164   }
 165
 166   private void checkBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
 167     for (int i = 0; i < bn.size(); i++) {
 168       BlockStatementNode bsn = bn.get(i);
 169       checkBlockStatementNode(md, bn.getVarTable(), bsn);
 170     }
 171   }
 172
 173   private void checkBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
 174       BlockStatementNode bsn) {
 175
 176     if (needToNullify != null) {
 177       if (!checkNullifying(bsn)) {
 178         throw new Error(
 179             "Reference field '"
 180                 + needToNullify
 181                 + "', which is read by a method, should be assigned to null before executing any following statement of the reference copy statement at "
 182                 + md.getClassDesc().getSourceFileName() + "::" + prevAssignNode.getNumLine());
 183       }
 184     }
 185
 186     switch (bsn.kind()) {
 187
 188     case Kind.BlockExpressionNode:
 189       checkBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
 190       return;
 191
 192     case Kind.DeclarationNode:
 193       checkDeclarationNode(md, nametable, (DeclarationNode) bsn);
 194       return;
 195
 196     case Kind.IfStatementNode:
 197       checkIfStatementNode(md, nametable, (IfStatementNode) bsn);
 198       return;
 199
 200     case Kind.SwitchStatementNode:
 201       checkSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
 202       return;
 203
 204     case Kind.LoopNode:
 205       checkLoopNode(md, nametable, (LoopNode) bsn);
 206       return;
 207
 208     case Kind.ReturnNode:
 209       checkReturnNode(md, nametable, (ReturnNode) bsn);
 210       return;
 211
 212     case Kind.SubBlockNode:
 213       checkSubBlockNode(md, nametable, (SubBlockNode) bsn);
 214       return;
 215
 216     case Kind.SynchronizedNode:
 217       checkSynchronizedNode(md, nametable, (SynchronizedNode) bsn);
 218       return;
 219     }
 220
 221   }
 222
 223   private void checkSynchronizedNode(MethodDescriptor md, SymbolTable nametable,
 224       SynchronizedNode sbn) {
 225     checkBlockNode(md, nametable, sbn.getBlockNode());
 226     // todo this could be Object
 227     checkExpressionNode(md, nametable, sbn.getExpr());
 228   }
 229
 230   private void checkReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn) {
 231     if (rn.getReturnExpression() != null) {
 232       checkExpressionNode(md, nametable, rn.getReturnExpression());
 233     }
 234   }
 235
 236   private void checkSubBlockNode(MethodDescriptor md, SymbolTable nametable, SubBlockNode sbn) {
 237     checkBlockNode(md, nametable, sbn.getBlockNode());
 238   }
 239
 240   private void checkIfStatementNode(MethodDescriptor md, SymbolTable nametable, IfStatementNode isn) {
 241     checkExpressionNode(md, nametable, isn.getCondition());
 242     checkBlockNode(md, nametable, isn.getTrueBlock());
 243     if (isn.getFalseBlock() != null)
 244       checkBlockNode(md, nametable, isn.getFalseBlock());
 245   }
 246
 247   private void checkSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
 248       SwitchStatementNode ssn) {
 249
 250     checkExpressionNode(md, nametable, ssn.getCondition());
 251
 252     BlockNode sbn = ssn.getSwitchBody();
 253     for (int i = 0; i < sbn.size(); i++) {
 254       checkSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i));
 255     }
 256   }
 257
 258   private void checkSwitchBlockNode(MethodDescriptor md, SymbolTable nametable, SwitchBlockNode sbn) {
 259     checkBlockNode(md, nametable, sbn.getSwitchBlockStatement());
 260   }
 261
 262   private void checkBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
 263       BlockExpressionNode ben) {
 264     checkExpressionNode(md, nametable, ben.getExpression());
 265   }
 266
 267   private void checkExpressionNode(MethodDescriptor md, SymbolTable nametable, ExpressionNode en) {
 268     switch (en.kind()) {
 269     case Kind.AssignmentNode:
 270       checkAssignmentNode(md, nametable, (AssignmentNode) en);
 271       return;
 272
 273     case Kind.CastNode:
 274       checkCastNode(md, nametable, (CastNode) en);
 275       return;
 276
 277     case Kind.CreateObjectNode:
 278       checkCreateObjectNode(md, nametable, (CreateObjectNode) en);
 279       return;
 280
 281     case Kind.FieldAccessNode:
 282       checkFieldAccessNode(md, nametable, (FieldAccessNode) en);
 283       return;
 284
 285     case Kind.ArrayAccessNode:
 286       checkArrayAccessNode(md, nametable, (ArrayAccessNode) en);
 287       return;
 288
 289       // case Kind.LiteralNode:
 290       // checkLiteralNode(md, nametable, (LiteralNode) en);
 291       // return;
 292
 293     case Kind.MethodInvokeNode:
 294       checkMethodInvokeNode(md, nametable, (MethodInvokeNode) en);
 295       return;
 296
 297     case Kind.NameNode:
 298       checkNameNode(md, nametable, (NameNode) en);
 299       return;
 300
 301     case Kind.OpNode:
 302       checkOpNode(md, nametable, (OpNode) en);
 303       return;
 304
 305     case Kind.OffsetNode:
 306       checkOffsetNode(md, nametable, (OffsetNode) en);
 307       return;
 308
 309     case Kind.TertiaryNode:
 310       checkTertiaryNode(md, nametable, (TertiaryNode) en);
 311       return;
 312
 313       // case Kind.InstanceOfNode:
 314       // checkInstanceOfNode(md, nametable, (InstanceOfNode) en);
 315       // return;
 316
 317       // case Kind.ArrayInitializerNode:
 318       // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en);
 319       // return;
 320
 321       // case Kind.ClassTypeNode:
 322       // checkClassTypeNode(md, nametable, (ClassTypeNode) ens);
 323       // return;
 324     }
 325   }
 326
 327   private void checkTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode en) {
 328     // TODO Auto-generated method stub
 329
 330   }
 331
 332   private void checkOffsetNode(MethodDescriptor md, SymbolTable nametable, OffsetNode en) {
 333     // TODO Auto-generated method stub
 334
 335   }
 336
 337   private void checkOpNode(MethodDescriptor md, SymbolTable nametable, OpNode en) {
 338     // TODO Auto-generated method stub
 339
 340   }
 341
 342   private void checkNameNode(MethodDescriptor md, SymbolTable nametable, NameNode en) {
 343     // TODO Auto-generated method stub
 344
 345   }
 346
 347   private boolean isOwned(VarDescriptor varDesc) {
 348     if (varDesc.getType().getExtension() != null) {
 349       SSJavaType locationType = (SSJavaType) varDesc.getType().getExtension();
 350       return locationType.isOwned();
 351     }
 352     return false;
 353   }
 354
 355   private void checkMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
 356       MethodInvokeNode min) {
 357
 358     MethodDescriptor calleeMethodDesc = min.getMethod();
 359
 360     // check delegate_this annotation
 361     // only method that owns itself 'THIS' can call method with delegate_this
 362     // annotation
 363
 364     if (delegateThisMethodSet.contains(calleeMethodDesc)) {
 365
 366       if (min.getBaseName() == null) {
 367         if (!delegateThisMethodSet.contains(md)) {
 368           throw new Error("Caller does not own the 'THIS' argument at " + md.getClassDesc() + "::"
 369               + min.getNumLine());
 370         }
 371       } else {
 372         VarDescriptor baseVar = (VarDescriptor) nametable.get(min.getBaseName().getIdentifier());
 373         if (!isOwned(baseVar)) {
 374           throw new Error("Caller does not own the 'THIS' argument at " + md.getClassDesc() + "::"
 375               + min.getNumLine());
 376         }
 377       }
 378     }
 379
 380     // check delegate parameter annotation
 381     for (int i = 0; i < min.numArgs(); i++) {
 382       ExpressionNode argNode = min.getArg(i);
 383
 384       TypeDescriptor paramType = calleeMethodDesc.getParamType(i);
 385
 386       if (isReference(argNode.getType())) {
 387
 388         boolean isParamOwnedByCallee = false;
 389         if (paramType.getExtension() != null) {
 390           SSJavaType locationType = (SSJavaType) paramType.getExtension();
 391           isParamOwnedByCallee = locationType.isOwned();
 392         }
 393
 394         TypeDescriptor argType = getTypeDescriptor(argNode);
 395
 396         if (isParamOwnedByCallee) {
 397
 398           // method expects that argument is owned by caller
 399           SSJavaType locationType = (SSJavaType) argType.getExtension();
 400
 401           if (locationType == null || !locationType.isOwned()) {
 402             throw new Error("Caller passes an argument not owned by itself at " + md.getClassDesc()
 403                 + "::" + min.getNumLine());
 404           }
 405         }
 406
 407       }
 408     }
 409
 410   }
 411
 412   private void checkArrayAccessNode(MethodDescriptor md, SymbolTable nametable, ArrayAccessNode en) {
 413     // TODO Auto-generated method stub
 414
 415   }
 416
 417   private void checkFieldAccessNode(MethodDescriptor md, SymbolTable nametable, FieldAccessNode fan) {
 418
 419   }
 420
 421   private void checkCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
 422       CreateObjectNode con) {
 423
 424     TypeDescriptor[] tdarray = new TypeDescriptor[con.numArgs()];
 425     for (int i = 0; i < con.numArgs(); i++) {
 426       ExpressionNode en = con.getArg(i);
 427       checkExpressionNode(md, nametable, en);
 428       tdarray[i] = en.getType();
 429     }
 430
 431     if ((con.getArrayInitializer() != null)) {
 432       checkArrayInitializerNode(md, nametable, con.getArrayInitializer());
 433     }
 434
 435     // the current method owns a instance that it makes inside
 436     SSJavaType locationType = new SSJavaType(true);
 437     con.getType().setExtension(locationType);
 438
 439   }
 440
 441   private void checkArrayInitializerNode(MethodDescriptor md, SymbolTable nametable,
 442       ArrayInitializerNode arrayInitializer) {
 443     // TODO Auto-generated method stub
 444
 445   }
 446
 447   private void checkCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn) {
 448     ExpressionNode en = cn.getExpression();
 449     checkExpressionNode(md, nametable, en);
 450   }
 451
 452   private boolean checkNullifying(BlockStatementNode bsn) {
 453
 454     if (bsn.kind() == Kind.BlockExpressionNode) {
 455       ExpressionNode en = ((BlockExpressionNode) bsn).getExpression();
 456       if (en.kind() == Kind.AssignmentNode) {
 457         AssignmentNode an = (AssignmentNode) en;
 458
 459         String destName = an.getDest().printNode(0);
 460         if (destName.startsWith("this.")) {
 461           destName = destName.substring(5);
 462         }
 463
 464         if (an.getSrc().getType().isNull() && destName.equals(needToNullify)) {
 465           needToNullify = null;
 466           return true;
 467         }
 468       }
 469     }
 470
 471     return false;
 472   }
 473
 474   private void checkLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln) {
 475     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
 476       checkExpressionNode(md, nametable, ln.getCondition());
 477       checkBlockNode(md, nametable, ln.getBody());
 478     } else {
 479       // For loop case
 480       /* Link in the initializer naming environment */
 481       BlockNode bn = ln.getInitializer();
 482       for (int i = 0; i < bn.size(); i++) {
 483         BlockStatementNode bsn = bn.get(i);
 484         checkBlockStatementNode(md, bn.getVarTable(), bsn);
 485       }
 486       // check the condition
 487       checkExpressionNode(md, bn.getVarTable(), ln.getCondition());
 488       checkBlockNode(md, bn.getVarTable(), ln.getBody());
 489       checkBlockNode(md, bn.getVarTable(), ln.getUpdate());
 490     }
 491   }
 492
 493   private void checkAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an) {
 494
 495     boolean postinc = true;
 496     if (an.getOperation().getBaseOp() == null
 497         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
 498             .getBaseOp().getOp() != Operation.POSTDEC))
 499       postinc = false;
 500
 501     if (!postinc) {
 502
 503       checkExpressionNode(md, nametable, an.getSrc());
 504
 505       if (isReference(an.getSrc().getType()) && isReference(an.getDest().getType())) {
 506         if (an.getSrc().kind() == Kind.NameNode) {
 507
 508           NameNode nn = (NameNode) an.getSrc();
 509
 510           if (nn.getField() != null) {
 511             needToNullify = nn.getField().getSymbol();
 512             prevAssignNode = an;
 513           } else if (nn.getExpression() != null) {
 514             if (nn.getExpression() instanceof FieldAccessNode) {
 515               FieldAccessNode fan = (FieldAccessNode) nn.getExpression();
 516               needToNullify = fan.printNode(0);
 517               prevAssignNode = an;
 518
 519             }
 520
 521           } else {
 522             // local variable case
 523             linearTypeCheckSet.add(an.getSrc());
 524             mapTreeNode2FlatMethod.put(an.getSrc(), state.getMethodFlat(md));
 525           }
 526         } else if (an.getSrc().kind() == Kind.FieldAccessNode) {
 527           FieldAccessNode fan = (FieldAccessNode) an.getSrc();
 528           needToNullify = fan.printNode(0);
 529           if (needToNullify.startsWith("this.")) {
 530             needToNullify = needToNullify.substring(5);
 531           }
 532           prevAssignNode = an;
 533         } else if (an.getSrc().kind() == Kind.ArrayAccessNode) {
 534           throw new Error(
 535               "Not allowed to create an alias to the middle of the multidimensional array at "
 536                   + md.getClassDesc() + "::" + an.getNumLine());
 537         }
 538
 539         if (!an.getSrc().getType().isNull()) {
 540
 541           TypeDescriptor srcType = getTypeDescriptor(an.getSrc());
 542           boolean isSourceOwned = false;
 543
 544           if (srcType.getExtension() != null) {
 545             SSJavaType srcLocationType = (SSJavaType) srcType.getExtension();
 546             isSourceOwned = srcLocationType.isOwned();
 547           }
 548
 549           if (!isField(an.getDest()) && isSourceOwned) {
 550             // here, transfer ownership from LHS to RHS when it creates alias
 551             TypeDescriptor destType = getTypeDescriptor(an.getDest());
 552             destType.setExtension(new SSJavaType(isSourceOwned));
 553           } else {
 554             // if instance is not owned by the method, not able to store
 555             // instance into field
 556             if (!isSourceOwned) {
 557               throw new Error(
 558                   "Method is not allowed to store an instance not owned by itself into a field at "
 559                       + md.getClassDesc() + "::" + an.getNumLine());
 560             }
 561           }
 562
 563         }
 564
 565       }
 566
 567     }
 568
 569   }
 570
 571   private TypeDescriptor getTypeDescriptor(ExpressionNode en) {
 572
 573     if (en.kind() == Kind.NameNode) {
 574       NameNode nn = (NameNode) en;
 575       if (nn.getField() != null) {
 576         return nn.getVar().getType();
 577       } else if (nn.getVar() != null) {
 578         return nn.getVar().getType();
 579       } else {
 580         return getTypeDescriptor(nn.getExpression());
 581       }
 582     } else if (en.kind() == Kind.FieldAccessNode) {
 583       FieldAccessNode fan = (FieldAccessNode) en;
 584       return getTypeDescriptor(fan.getExpression());
 585     } else if (en.kind() == Kind.CreateObjectNode) {
 586       CreateObjectNode con = (CreateObjectNode) en;
 587       return con.getType();
 588     }
 589
 590     return null;
 591   }
 592
 593   private boolean isField(ExpressionNode en) {
 594
 595     if (en.kind() == Kind.NameNode) {
 596       NameNode nn = (NameNode) en;
 597       if (nn.getField() != null) {
 598         return true;
 599       }
 600
 601       if (nn.getName() != null && nn.getName().getBase() != null) {
 602         return true;
 603       }
 604
 605     } else if (en.kind() == Kind.FieldAccessNode) {
 606       return true;
 607     }
 608     return false;
 609   }
 610
 611   private void checkDeclarationNode(MethodDescriptor md, SymbolTable nametable, DeclarationNode dn) {
 612     if (dn.getExpression() != null) {
 613       checkExpressionNode(md, nametable, dn.getExpression());
 614       if (dn.getExpression().kind() == Kind.CreateObjectNode) {
 615         dn.getVarDescriptor().getType().setExtension(new SSJavaType(true));
 616       }
 617
 618     }
 619
 620   }
 621
 622   private boolean isReference(TypeDescriptor td) {
 623     if (td.isPtr()) {
 624       return true;
 625     }
 626     return false;
 627   }
 628
 629 }