Robust/src/Analysis/SSJava/SSJavaInferenceEngine.java

   1 package Analysis.SSJava;
   2
   3 import java.util.ArrayList;
   4 import java.util.Collections;
   5 import java.util.Comparator;
   6 import java.util.HashSet;
   7 import java.util.Hashtable;
   8 import java.util.Iterator;
   9 import java.util.List;
  10 import java.util.Set;
  11 import java.util.StringTokenizer;
  12 import java.util.Vector;
  13 import java.io.FileWriter;
  14 import java.io.PrintWriter;
  15 import java.io.IOException;
  16
  17 import Analysis.SSJava.FlowDownCheck.ComparisonResult;
  18 import Analysis.SSJava.FlowDownCheck.CompositeLattice;
  19 import IR.AnnotationDescriptor;
  20 import IR.ClassDescriptor;
  21 import IR.Descriptor;
  22 import IR.FieldDescriptor;
  23 import IR.MethodDescriptor;
  24 import IR.NameDescriptor;
  25 import IR.Operation;
  26 import IR.State;
  27 import IR.SymbolTable;
  28 import IR.TypeDescriptor;
  29 import IR.VarDescriptor;
  30 import IR.Tree.ArrayAccessNode;
  31 import IR.Tree.AssignmentNode;
  32 import IR.Tree.BlockExpressionNode;
  33 import IR.Tree.BlockNode;
  34 import IR.Tree.BlockStatementNode;
  35 import IR.Tree.CastNode;
  36 import IR.Tree.CreateObjectNode;
  37 import IR.Tree.DeclarationNode;
  38 import IR.Tree.ExpressionNode;
  39 import IR.Tree.FieldAccessNode;
  40 import IR.Tree.IfStatementNode;
  41 import IR.Tree.Kind;
  42 import IR.Tree.LiteralNode;
  43 import IR.Tree.LoopNode;
  44 import IR.Tree.MethodInvokeNode;
  45 import IR.Tree.NameNode;
  46 import IR.Tree.OpNode;
  47 import IR.Tree.ReturnNode;
  48 import IR.Tree.SubBlockNode;
  49 import IR.Tree.SwitchBlockNode;
  50 import IR.Tree.SwitchStatementNode;
  51 import IR.Tree.SynchronizedNode;
  52 import IR.Tree.TertiaryNode;
  53 import IR.Tree.TreeNode;
  54 import Util.Pair;
  55
  56 public class SSJavaInferenceEngine {
  57
  58   State state;
  59   static SSJavaAnalysis ssjava;
  60
  61   Set<ClassDescriptor> toanalyze;
  62   List<ClassDescriptor> toanalyzeList;
  63
  64   Set<MethodDescriptor> toanalyzeMethod;
  65   List<MethodDescriptor> toanalyzeMethodList;
  66
  67   // mapping from 'descriptor' to 'composite location'
  68   Hashtable<Descriptor, CompositeLocation> d2loc;
  69
  70   Hashtable<MethodDescriptor, CompositeLocation> md2ReturnLoc;
  71   Hashtable<MethodDescriptor, ReturnLocGenerator> md2ReturnLocGen;
  72
  73   // mapping from 'locID' to 'class descriptor'
  74   Hashtable<String, ClassDescriptor> fieldLocName2cd;
  75
  76     private Set<ImplicitTuple> implicitFlowSet;  /*should maybe be hashtable<ExpressionNode,Set<VarID>>*/
  77   private RelationSet rSet;
  78
  79   boolean deterministic = true;
  80
  81   public SSJavaInferenceEngine(SSJavaAnalysis ssjava, State state) {
  82     this.ssjava = ssjava;
  83     this.state = state;
  84     if (deterministic) {
  85       this.toanalyzeList = new ArrayList<ClassDescriptor>();
  86     } else {
  87       this.toanalyze = new HashSet<ClassDescriptor>();
  88     }
  89     if (deterministic) {
  90       this.toanalyzeMethodList = new ArrayList<MethodDescriptor>();
  91     } else {
  92       this.toanalyzeMethod = new HashSet<MethodDescriptor>();
  93     }
  94     this.d2loc = new Hashtable<Descriptor, CompositeLocation>();
  95     this.fieldLocName2cd = new Hashtable<String, ClassDescriptor>();
  96     this.md2ReturnLoc = new Hashtable<MethodDescriptor, CompositeLocation>();
  97     this.md2ReturnLocGen = new Hashtable<MethodDescriptor, ReturnLocGenerator>();
  98     this.implicitFlowSet = new HashSet<ImplicitTuple>();
  99     this.rSet = new RelationSet();
 100   }
 101
 102   public void init() {
 103
 104     // construct mapping from the location name to the class descriptor
 105     // assume that the location name is unique through the whole program
 106
 107     Set<ClassDescriptor> cdSet = ssjava.getCd2lattice().keySet();
 108     for (Iterator iterator = cdSet.iterator(); iterator.hasNext();) {
 109       ClassDescriptor cd = (ClassDescriptor) iterator.next();
 110       SSJavaLattice<String> lattice = ssjava.getCd2lattice().get(cd);
 111       Set<String> fieldLocNameSet = lattice.getKeySet();
 112
 113       for (Iterator iterator2 = fieldLocNameSet.iterator(); iterator2.hasNext();) {
 114         String fieldLocName = (String) iterator2.next();
 115         fieldLocName2cd.put(fieldLocName, cd);
 116       }
 117
 118     }
 119
 120   }
 121
 122   public boolean toAnalyzeIsEmpty() {
 123     if (deterministic) {
 124       return toanalyzeList.isEmpty();
 125     } else {
 126       return toanalyze.isEmpty();
 127     }
 128   }
 129
 130   public ClassDescriptor toAnalyzeNext() {
 131     if (deterministic) {
 132       return toanalyzeList.remove(0);
 133     } else {
 134       ClassDescriptor cd = toanalyze.iterator().next();
 135       toanalyze.remove(cd);
 136       return cd;
 137     }
 138   }
 139
 140   public void setupToAnalyze() {
 141     SymbolTable classtable = state.getClassSymbolTable();
 142     if (deterministic) {
 143       toanalyzeList.clear();
 144       toanalyzeList.addAll(classtable.getValueSet());
 145       Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
 146         public int compare(ClassDescriptor o1, ClassDescriptor o2) {
 147           return o1.getClassName().compareTo(o2.getClassName());
 148         }
 149       });
 150     } else {
 151       toanalyze.clear();
 152       toanalyze.addAll(classtable.getValueSet());
 153     }
 154   }
 155
 156   public void setupToAnalazeMethod(ClassDescriptor cd) {
 157
 158     SymbolTable methodtable = cd.getMethodTable();
 159     if (deterministic) {
 160       toanalyzeMethodList.clear();
 161       toanalyzeMethodList.addAll(methodtable.getValueSet());
 162       Collections.sort(toanalyzeMethodList, new Comparator<MethodDescriptor>() {
 163         public int compare(MethodDescriptor o1, MethodDescriptor o2) {
 164           return o1.getSymbol().compareTo(o2.getSymbol());
 165         }
 166       });
 167     } else {
 168       toanalyzeMethod.clear();
 169       toanalyzeMethod.addAll(methodtable.getValueSet());
 170     }
 171   }
 172
 173   public boolean toAnalyzeMethodIsEmpty() {
 174     if (deterministic) {
 175       return toanalyzeMethodList.isEmpty();
 176     } else {
 177       return toanalyzeMethod.isEmpty();
 178     }
 179   }
 180
 181   public MethodDescriptor toAnalyzeMethodNext() {
 182     if (deterministic) {
 183       return toanalyzeMethodList.remove(0);
 184     } else {
 185       MethodDescriptor md = toanalyzeMethod.iterator().next();
 186       toanalyzeMethod.remove(md);
 187       return md;
 188     }
 189   }
 190
 191   public void inference() {
 192     FileWriter latticeFile;
 193     PrintWriter latticeOut;
 194     setupToAnalyze();
 195
 196     while (!toAnalyzeIsEmpty()) {
 197       ClassDescriptor cd = toAnalyzeNext();
 198       try{
 199       latticeFile = new FileWriter(cd.getClassName()+".lat");
 200       } catch(IOException e){
 201           System.out.println("File Fail");
 202           return;
 203       }
 204       latticeOut = new PrintWriter(latticeFile);
 205       if (ssjava.needToBeAnnoated(cd)) {
 206         setupToAnalazeMethod(cd);
 207         while (!toAnalyzeMethodIsEmpty()) {
 208           MethodDescriptor md = toAnalyzeMethodNext();
 209           if (ssjava.needTobeAnnotated(md)) {
 210             inferRelationsFromBlockNode(md, md.getParameterTable(), state.getMethodBody(md));
 211             latticeOut.println(md.getClassMethodName() + "\n");
 212             latticeOut.println(rSet.toString());
 213             rSet = new RelationSet();
 214           }
 215         }
 216       }
 217       latticeOut.flush();
 218       latticeOut.close();
 219     }
 220   }
 221
 222   private void inferRelationsFromBlockNode(MethodDescriptor md, SymbolTable nametable,
 223       BlockNode bn) {
 224
 225     bn.getVarTable().setParent(nametable);
 226     for (int i = 0; i < bn.size(); i++) {
 227       BlockStatementNode bsn = bn.get(i);
 228       inferRelationsFromBlockStatementNode(md, bn.getVarTable(), bsn);
 229     }
 230
 231   }
 232
 233   private void inferRelationsFromBlockStatementNode(MethodDescriptor md,
 234       SymbolTable nametable, BlockStatementNode bsn) {
 235
 236     switch (bsn.kind()) {
 237     case Kind.BlockExpressionNode:
 238       inferRelationsFromBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
 239       break;
 240
 241     case Kind.DeclarationNode:
 242       inferRelationsFromDeclarationNode(md, nametable, (DeclarationNode) bsn);
 243       break;
 244       /*
 245     case Kind.IfStatementNode:
 246       inferRelationsFromIfStatementNode(md, nametable, (IfStatementNode) bsn);
 247       break;
 248
 249     case Kind.LoopNode:
 250       inferRelationsFromLoopNode(md, nametable, (LoopNode) bsn, constraint);
 251       break;
 252
 253     case Kind.ReturnNode:
 254       inferRelationsFromReturnNode(md, nametable, (ReturnNode) bsn, constraint);
 255       break;
 256
 257     case Kind.SubBlockNode:
 258       inferRelationsFromSubBlockNode(md, nametable, (SubBlockNode) bsn, constraint);
 259       break;
 260
 261     case Kind.ContinueBreakNode:
 262       compLoc = new CompositeLocation();
 263       break;
 264
 265     case Kind.SwitchStatementNode:
 266       inferRelationsFromSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn, constraint);
 267       */
 268     }
 269   }
 270
 271     /*private CompositeLocation inferRelationsFromSwitchStatementNode(MethodDescriptor md,
 272       SymbolTable nametable, SwitchStatementNode ssn, CompositeLocation constraint) {
 273
 274     ClassDescriptor cd = md.getClassDesc();
 275     CompositeLocation condLoc =
 276         inferRelationsFromExpressionNode(md, nametable, ssn.getCondition(), new CompositeLocation(),
 277             constraint, false);
 278     BlockNode sbn = ssn.getSwitchBody();
 279
 280     constraint = generateNewConstraint(constraint, condLoc);
 281
 282     for (int i = 0; i < sbn.size(); i++) {
 283       inferRelationsFromSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i), constraint);
 284     }
 285     return new CompositeLocation();
 286   }
 287
 288   private CompositeLocation inferRelationsFromSwitchBlockNode(MethodDescriptor md,
 289       SymbolTable nametable, SwitchBlockNode sbn, CompositeLocation constraint) {
 290
 291     CompositeLocation blockLoc =
 292         inferRelationsFromBlockNode(md, nametable, sbn.getSwitchBlockStatement(), constraint);
 293
 294     return blockLoc;
 295
 296   }
 297
 298   private CompositeLocation inferRelationsFromReturnNode(MethodDescriptor md, SymbolTable nametable,
 299       ReturnNode rn, CompositeLocation constraint) {
 300
 301     ExpressionNode returnExp = rn.getReturnExpression();
 302
 303     CompositeLocation returnValueLoc;
 304     if (returnExp != null) {
 305       returnValueLoc =
 306           inferRelationsFromExpressionNode(md, nametable, returnExp, new CompositeLocation(),
 307               constraint, false);
 308
 309       // if this return statement is inside branch, return value has an implicit
 310       // flow from conditional location
 311       if (constraint != null) {
 312         Set<CompositeLocation> inputGLB = new HashSet<CompositeLocation>();
 313         inputGLB.add(returnValueLoc);
 314         inputGLB.add(constraint);
 315         returnValueLoc =
 316             CompositeLattice.calculateGLB(inputGLB, generateErrorMessage(md.getClassDesc(), rn));
 317       }
 318
 319       // check if return value is equal or higher than RETRUNLOC of method
 320       // declaration annotation
 321       CompositeLocation declaredReturnLoc = md2ReturnLoc.get(md);
 322
 323       int compareResult =
 324           CompositeLattice.compare(returnValueLoc, declaredReturnLoc, false,
 325               generateErrorMessage(md.getClassDesc(), rn));
 326
 327       if (compareResult == ComparisonResult.LESS || compareResult == ComparisonResult.INCOMPARABLE) {
 328         throw new Error(
 329             "Return value location is not equal or higher than the declaraed return location at "
 330                 + md.getClassDesc().getSourceFileName() + "::" + rn.getNumLine());
 331       }
 332     }
 333
 334     return new CompositeLocation();
 335   }
 336
 337   private boolean hasOnlyLiteralValue(ExpressionNode en) {
 338     if (en.kind() == Kind.LiteralNode) {
 339       return true;
 340     } else {
 341       return false;
 342     }
 343   }
 344
 345   private CompositeLocation inferRelationsFromLoopNode(MethodDescriptor md, SymbolTable nametable,
 346       LoopNode ln, CompositeLocation constraint) {
 347
 348     ClassDescriptor cd = md.getClassDesc();
 349     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
 350
 351       CompositeLocation condLoc =
 352           inferRelationsFromExpressionNode(md, nametable, ln.getCondition(),
 353               new CompositeLocation(), constraint, false);
 354       // addLocationType(ln.getCondition().getType(), (condLoc));
 355
 356       constraint = generateNewConstraint(constraint, condLoc);
 357       inferRelationsFromBlockNode(md, nametable, ln.getBody(), constraint);
 358
 359       return new CompositeLocation();
 360
 361     } else {
 362       // check 'for loop' case
 363       BlockNode bn = ln.getInitializer();
 364       bn.getVarTable().setParent(nametable);
 365
 366       // calculate glb location of condition and update statements
 367       CompositeLocation condLoc =
 368           inferRelationsFromExpressionNode(md, bn.getVarTable(), ln.getCondition(),
 369               new CompositeLocation(), constraint, false);
 370       // addLocationType(ln.getCondition().getType(), condLoc);
 371
 372       constraint = generateNewConstraint(constraint, condLoc);
 373
 374       inferRelationsFromBlockNode(md, bn.getVarTable(), ln.getUpdate(), constraint);
 375       inferRelationsFromBlockNode(md, bn.getVarTable(), ln.getBody(), constraint);
 376
 377       return new CompositeLocation();
 378
 379     }
 380
 381   }
 382
 383   private CompositeLocation inferRelationsFromSubBlockNode(MethodDescriptor md,
 384       SymbolTable nametable, SubBlockNode sbn, CompositeLocation constraint) {
 385     CompositeLocation compLoc =
 386         inferRelationsFromBlockNode(md, nametable, sbn.getBlockNode(), constraint);
 387     return compLoc;
 388   }
 389
 390   private CompositeLocation generateNewConstraint(CompositeLocation currentCon,
 391       CompositeLocation newCon) {
 392
 393     if (currentCon == null) {
 394       return newCon;
 395     } else {
 396       // compute GLB of current constraint and new constraint
 397       Set<CompositeLocation> inputSet = new HashSet<CompositeLocation>();
 398       inputSet.add(currentCon);
 399       inputSet.add(newCon);
 400       return CompositeLattice.calculateGLB(inputSet, "");
 401     }
 402
 403   }
 404
 405   private void inferRelationsFromIfStatementNode(MethodDescriptor md,
 406       SymbolTable nametable, IfStatementNode isn) {
 407
 408     inferRelationsFromExpressionNode(md, nametable, isn.getCondition(), null, false);
 409
 410     constraint = generateNewConstraint(constraint, condLoc);
 411     inferRelationFromBlockNode(md, nametable, isn.getTrueBlock(), constraint);
 412
 413     if (isn.getFalseBlock() != null) {
 414       inferRelationsFromBlockNode(md, nametable, isn.getFalseBlock(), constraint);
 415     }
 416   }
 417     */
 418   private void inferRelationsFromDeclarationNode(MethodDescriptor md,
 419       SymbolTable nametable, DeclarationNode dn) {
 420   }
 421
 422     /*private void inferRelationsFromSubBlockNode(MethodDescriptor md, SymbolTable nametable,
 423       SubBlockNode sbn) {
 424     inferRelationsFromBlockNode(md, nametable.getParent(), sbn.getBlockNode());
 425     }*/
 426
 427   private void inferRelationsFromBlockExpressionNode(MethodDescriptor md,
 428       SymbolTable nametable, BlockExpressionNode ben) {
 429       inferRelationsFromExpressionNode(md, nametable, ben.getExpression(), null, false);
 430     // addTypeLocation(ben.getExpression().getType(), compLoc);
 431   }
 432
 433   private VarID inferRelationsFromExpressionNode(MethodDescriptor md,
 434       SymbolTable nametable, ExpressionNode en, VarID flowTo, boolean isLHS) {
 435
 436     VarID var = null;
 437     switch (en.kind()) {
 438
 439     case Kind.AssignmentNode:
 440       var =
 441           inferRelationsFromAssignmentNode(md, nametable, (AssignmentNode) en, flowTo);
 442       break;
 443
 444       //   case Kind.FieldAccessNode:
 445       // var =
 446       //    inferRelationsFromFieldAccessNode(md, nametable, (FieldAccessNode) en, flowTo);
 447       // break;
 448
 449     case Kind.NameNode:
 450         var = inferRelationsFromNameNode(md, nametable, (NameNode) en, flowTo);
 451       break;
 452
 453       /* case Kind.OpNode:
 454         var = inferRelationsFromOpNode(md, nametable, (OpNode) en, flowTo);
 455       break;
 456
 457     case Kind.CreateObjectNode:
 458       var = inferRelationsFromCreateObjectNode(md, nametable, (CreateObjectNode) en);
 459       break;
 460
 461     case Kind.ArrayAccessNode:
 462       var =
 463           inferRelationsFromArrayAccessNode(md, nametable, (ArrayAccessNode) en, flowTo, isLHS);
 464       break;
 465       */
 466     case Kind.LiteralNode:
 467         var = inferRelationsFromLiteralNode(md, nametable, (LiteralNode) en);
 468       break;
 469       /*
 470      case Kind.MethodInvokeNode:
 471       var =
 472           inferRelationsFromMethodInvokeNode(md, nametable, (MethodInvokeNode) en, flowTo);
 473       break;
 474
 475     case Kind.TertiaryNode:
 476       var = inferRelationsFromTertiaryNode(md, nametable, (TertiaryNode) en);
 477       break;
 478
 479     case Kind.CastNode:
 480       var = inferRelationsFromCastNode(md, nametable, (CastNode) en);
 481       break;
 482       */
 483     // case Kind.InstanceOfNode:
 484     // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
 485     // return null;
 486
 487     // case Kind.ArrayInitializerNode:
 488     // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
 489     // td);
 490     // return null;
 491
 492     // case Kind.ClassTypeNode:
 493     // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
 494     // return null;
 495
 496     // case Kind.OffsetNode:
 497     // checkOffsetNode(md, nametable, (OffsetNode)en, td);
 498     // return null;
 499
 500     default:
 501       return null;
 502
 503     }
 504     // addTypeLocation(en.getType(), compLoc);
 505     return var;
 506
 507   }
 508     /*
 509  private CompositeLocation inferRelationsFromCastNode(MethodDescriptor md, SymbolTable nametable,
 510       CastNode cn, CompositeLocation constraint) {
 511
 512     ExpressionNode en = cn.getExpression();
 513     return inferRelationsFromExpressionNode(md, nametable, en, new CompositeLocation(), constraint,
 514         false);
 515
 516   }
 517
 518   private CompositeLocation inferRelationsFromTertiaryNode(MethodDescriptor md,
 519       SymbolTable nametable, TertiaryNode tn, CompositeLocation constraint) {
 520     ClassDescriptor cd = md.getClassDesc();
 521
 522     CompositeLocation condLoc =
 523         inferRelationsFromExpressionNode(md, nametable, tn.getCond(), new CompositeLocation(),
 524             constraint, false);
 525     // addLocationType(tn.getCond().getType(), condLoc);
 526     CompositeLocation trueLoc =
 527         inferRelationsFromExpressionNode(md, nametable, tn.getTrueExpr(), new CompositeLocation(),
 528             constraint, false);
 529     // addLocationType(tn.getTrueExpr().getType(), trueLoc);
 530     CompositeLocation falseLoc =
 531         inferRelationsFromExpressionNode(md, nametable, tn.getFalseExpr(), new CompositeLocation(),
 532             constraint, false);
 533     // addLocationType(tn.getFalseExpr().getType(), falseLoc);
 534
 535     // locations from true/false branches can be TOP when there are only literal
 536     // values
 537     // in this case, we don't need to check flow down rule!
 538
 539     // check if condLoc is higher than trueLoc & falseLoc
 540     if (!trueLoc.get(0).isTop()
 541         && !CompositeLattice.isGreaterThan(condLoc, trueLoc, generateErrorMessage(cd, tn))) {
 542       throw new Error(
 543           "The location of the condition expression is lower than the true expression at "
 544               + cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
 545     }
 546
 547     if (!falseLoc.get(0).isTop()
 548         && !CompositeLattice.isGreaterThan(condLoc, falseLoc,
 549             generateErrorMessage(cd, tn.getCond()))) {
 550       throw new Error(
 551           "The location of the condition expression is lower than the true expression at "
 552               + cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
 553     }
 554
 555     // then, return glb of trueLoc & falseLoc
 556     Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
 557     glbInputSet.add(trueLoc);
 558     glbInputSet.add(falseLoc);
 559
 560     return CompositeLattice.calculateGLB(glbInputSet, generateErrorMessage(cd, tn));
 561   }
 562
 563   private CompositeLocation inferRelationsFromMethodInvokeNode(MethodDescriptor md,
 564       SymbolTable nametable, MethodInvokeNode min, CompositeLocation loc,
 565       CompositeLocation constraint) {
 566
 567     CompositeLocation baseLocation = null;
 568     if (min.getExpression() != null) {
 569       baseLocation =
 570           inferRelationsFromExpressionNode(md, nametable, min.getExpression(),
 571               new CompositeLocation(), constraint, false);
 572     } else {
 573
 574       if (min.getMethod().isStatic()) {
 575         String globalLocId = ssjava.getMethodLattice(md).getGlobalLoc();
 576         if (globalLocId == null) {
 577           throw new Error("Method lattice does not define global variable location at "
 578               + generateErrorMessage(md.getClassDesc(), min));
 579         }
 580         baseLocation = new CompositeLocation(new Location(md, globalLocId));
 581       } else {
 582         String thisLocId = ssjava.getMethodLattice(md).getThisLoc();
 583         baseLocation = new CompositeLocation(new Location(md, thisLocId));
 584       }
 585     }
 586
 587     checkCalleeConstraints(md, nametable, min, baseLocation, constraint);
 588
 589     checkCallerArgumentLocationConstraints(md, nametable, min, baseLocation, constraint);
 590
 591     if (!min.getMethod().getReturnType().isVoid()) {
 592       // If method has a return value, compute the highest possible return
 593       // location in the caller's perspective
 594       CompositeLocation ceilingLoc =
 595           computeCeilingLocationForCaller(md, nametable, min, baseLocation, constraint);
 596       return ceilingLoc;
 597     }
 598
 599     return new CompositeLocation();
 600
 601   }
 602
 603   private void checkCallerArgumentLocationConstraints(MethodDescriptor md, SymbolTable nametable,
 604       MethodInvokeNode min, CompositeLocation callerBaseLoc, CompositeLocation constraint) {
 605     // if parameter location consists of THIS and FIELD location,
 606     // caller should pass an argument that is comparable to the declared
 607     // parameter location
 608     // and is not lower than the declared parameter location in the field
 609     // lattice.
 610
 611     MethodDescriptor calleemd = min.getMethod();
 612
 613     List<CompositeLocation> callerArgList = new ArrayList<CompositeLocation>();
 614     List<CompositeLocation> calleeParamList = new ArrayList<CompositeLocation>();
 615
 616     MethodLattice<String> calleeLattice = ssjava.getMethodLattice(calleemd);
 617     Location calleeThisLoc = new Location(calleemd, calleeLattice.getThisLoc());
 618
 619     for (int i = 0; i < min.numArgs(); i++) {
 620       ExpressionNode en = min.getArg(i);
 621       CompositeLocation callerArgLoc =
 622           inferRelationsFromExpressionNode(md, nametable, en, new CompositeLocation(), constraint,
 623               false);
 624       callerArgList.add(callerArgLoc);
 625     }
 626
 627     // setup callee params set
 628     for (int i = 0; i < calleemd.numParameters(); i++) {
 629       VarDescriptor calleevd = (VarDescriptor) calleemd.getParameter(i);
 630       CompositeLocation calleeLoc = d2loc.get(calleevd);
 631       calleeParamList.add(calleeLoc);
 632     }
 633
 634     String errorMsg = generateErrorMessage(md.getClassDesc(), min);
 635
 636     System.out.println("checkCallerArgumentLocationConstraints=" + min.printNode(0));
 637     System.out.println("base location=" + callerBaseLoc);
 638
 639     for (int i = 0; i < calleeParamList.size(); i++) {
 640       CompositeLocation calleeParamLoc = calleeParamList.get(i);
 641       if (calleeParamLoc.get(0).equals(calleeThisLoc) && calleeParamLoc.getSize() > 1) {
 642
 643         // callee parameter location has field information
 644         CompositeLocation callerArgLoc = callerArgList.get(i);
 645
 646         CompositeLocation paramLocation =
 647             translateCalleeParamLocToCaller(md, calleeParamLoc, callerBaseLoc, errorMsg);
 648
 649         Set<CompositeLocation> inputGLBSet = new HashSet<CompositeLocation>();
 650         if (constraint != null) {
 651           inputGLBSet.add(callerArgLoc);
 652           inputGLBSet.add(constraint);
 653           callerArgLoc =
 654               CompositeLattice.calculateGLB(inputGLBSet,
 655                   generateErrorMessage(md.getClassDesc(), min));
 656         }
 657
 658         if (!CompositeLattice.isGreaterThan(callerArgLoc, paramLocation, errorMsg)) {
 659           throw new Error("Caller argument '" + min.getArg(i).printNode(0) + " : " + callerArgLoc
 660               + "' should be higher than corresponding callee's parameter : " + paramLocation
 661               + " at " + errorMsg);
 662         }
 663
 664       }
 665     }
 666
 667   }
 668
 669   private CompositeLocation translateCalleeParamLocToCaller(MethodDescriptor md,
 670       CompositeLocation calleeParamLoc, CompositeLocation callerBaseLocation, String errorMsg) {
 671
 672     CompositeLocation translate = new CompositeLocation();
 673
 674     for (int i = 0; i < callerBaseLocation.getSize(); i++) {
 675       translate.addLocation(callerBaseLocation.get(i));
 676     }
 677
 678     for (int i = 1; i < calleeParamLoc.getSize(); i++) {
 679       translate.addLocation(calleeParamLoc.get(i));
 680     }
 681
 682     System.out.println("TRANSLATED=" + translate + " from calleeParamLoc=" + calleeParamLoc);
 683
 684     return translate;
 685   }
 686
 687   private CompositeLocation computeCeilingLocationForCaller(MethodDescriptor md,
 688       SymbolTable nametable, MethodInvokeNode min, CompositeLocation baseLocation,
 689       CompositeLocation constraint) {
 690     List<CompositeLocation> argList = new ArrayList<CompositeLocation>();
 691
 692     // by default, method has a THIS parameter
 693     argList.add(baseLocation);
 694
 695     for (int i = 0; i < min.numArgs(); i++) {
 696       ExpressionNode en = min.getArg(i);
 697       CompositeLocation callerArg =
 698           inferRelationsFromExpressionNode(md, nametable, en, new CompositeLocation(), constraint,
 699               false);
 700       argList.add(callerArg);
 701     }
 702
 703     System.out.println("\n## computeReturnLocation=" + min.getMethod() + " argList=" + argList);
 704     CompositeLocation compLoc = md2ReturnLocGen.get(min.getMethod()).computeReturnLocation(argList);
 705     DeltaLocation delta = new DeltaLocation(compLoc, 1);
 706     System.out.println("##computeReturnLocation=" + delta);
 707
 708     return delta;
 709
 710   }
 711
 712   private void checkCalleeConstraints(MethodDescriptor md, SymbolTable nametable,
 713       MethodInvokeNode min, CompositeLocation callerBaseLoc, CompositeLocation constraint) {
 714
 715     System.out.println("checkCalleeConstraints="+min.printNode(0));
 716
 717     MethodDescriptor calleemd = min.getMethod();
 718
 719     MethodLattice<String> calleeLattice = ssjava.getMethodLattice(calleemd);
 720     CompositeLocation calleeThisLoc =
 721         new CompositeLocation(new Location(calleemd, calleeLattice.getThisLoc()));
 722
 723     List<CompositeLocation> callerArgList = new ArrayList<CompositeLocation>();
 724     List<CompositeLocation> calleeParamList = new ArrayList<CompositeLocation>();
 725
 726     if (min.numArgs() > 0) {
 727       // caller needs to guarantee that it passes arguments in regarding to
 728       // callee's hierarchy
 729
 730       // setup caller args set
 731       // first, add caller's base(this) location
 732       callerArgList.add(callerBaseLoc);
 733       // second, add caller's arguments
 734       for (int i = 0; i < min.numArgs(); i++) {
 735         ExpressionNode en = min.getArg(i);
 736         CompositeLocation callerArgLoc =
 737             inferRelationsFromExpressionNode(md, nametable, en, new CompositeLocation(), constraint,
 738                 false);
 739         callerArgList.add(callerArgLoc);
 740       }
 741
 742       // setup callee params set
 743       // first, add callee's this location
 744       calleeParamList.add(calleeThisLoc);
 745       // second, add callee's parameters
 746       for (int i = 0; i < calleemd.numParameters(); i++) {
 747         VarDescriptor calleevd = (VarDescriptor) calleemd.getParameter(i);
 748         CompositeLocation calleeLoc = d2loc.get(calleevd);
 749         System.out.println("calleevd="+calleevd+" loc="+calleeLoc);
 750         calleeParamList.add(calleeLoc);
 751       }
 752
 753       // here, check if ordering relations among caller's args respect
 754       // ordering relations in-between callee's args
 755       CHECK: for (int i = 0; i < calleeParamList.size(); i++) {
 756         CompositeLocation calleeLoc1 = calleeParamList.get(i);
 757         CompositeLocation callerLoc1 = callerArgList.get(i);
 758
 759         for (int j = 0; j < calleeParamList.size(); j++) {
 760           if (i != j) {
 761             CompositeLocation calleeLoc2 = calleeParamList.get(j);
 762             CompositeLocation callerLoc2 = callerArgList.get(j);
 763
 764             if (callerLoc1.get(callerLoc1.getSize() - 1).isTop()
 765                 || callerLoc2.get(callerLoc2.getSize() - 1).isTop()) {
 766               continue CHECK;
 767             }
 768
 769             System.out.println("calleeLoc1="+calleeLoc1);
 770             System.out.println("calleeLoc2="+calleeLoc2+"calleeParamList="+calleeParamList);
 771
 772             int callerResult =
 773                 CompositeLattice.compare(callerLoc1, callerLoc2, true,
 774                     generateErrorMessage(md.getClassDesc(), min));
 775             int calleeResult =
 776                 CompositeLattice.compare(calleeLoc1, calleeLoc2, true,
 777                     generateErrorMessage(md.getClassDesc(), min));
 778
 779             if (calleeResult == ComparisonResult.GREATER
 780                 && callerResult != ComparisonResult.GREATER) {
 781               // If calleeLoc1 is higher than calleeLoc2
 782               // then, caller should have same ordering relation in-bet
 783               // callerLoc1 & callerLoc2
 784
 785               String paramName1, paramName2;
 786
 787               if (i == 0) {
 788                 paramName1 = "'THIS'";
 789               } else {
 790                 paramName1 = "'parameter " + calleemd.getParamName(i - 1) + "'";
 791               }
 792
 793               if (j == 0) {
 794                 paramName2 = "'THIS'";
 795               } else {
 796                 paramName2 = "'parameter " + calleemd.getParamName(j - 1) + "'";
 797               }
 798
 799               throw new Error(
 800                   "Caller doesn't respect an ordering relation among method arguments: callee expects that "
 801                       + paramName1 + " should be higher than " + paramName2 + " in " + calleemd
 802                       + " at " + md.getClassDesc().getSourceFileName() + ":" + min.getNumLine());
 803             }
 804           }
 805
 806         }
 807       }
 808
 809     }
 810
 811   }
 812
 813   private CompositeLocation inferRelationsFromArrayAccessNode(MethodDescriptor md,
 814       SymbolTable nametable, ArrayAccessNode aan, CompositeLocation constraint, boolean isLHS) {
 815
 816     ClassDescriptor cd = md.getClassDesc();
 817
 818     CompositeLocation arrayLoc =
 819         inferRelationsFromExpressionNode(md, nametable, aan.getExpression(),
 820             new CompositeLocation(), constraint, isLHS);
 821     // addTypeLocation(aan.getExpression().getType(), arrayLoc);
 822     CompositeLocation indexLoc =
 823         inferRelationsFromExpressionNode(md, nametable, aan.getIndex(), new CompositeLocation(),
 824             constraint, isLHS);
 825     // addTypeLocation(aan.getIndex().getType(), indexLoc);
 826
 827     if (isLHS) {
 828       if (!CompositeLattice.isGreaterThan(indexLoc, arrayLoc, generateErrorMessage(cd, aan))) {
 829         throw new Error("Array index value is not higher than array location at "
 830             + generateErrorMessage(cd, aan));
 831       }
 832       return arrayLoc;
 833     } else {
 834       Set<CompositeLocation> inputGLB = new HashSet<CompositeLocation>();
 835       inputGLB.add(arrayLoc);
 836       inputGLB.add(indexLoc);
 837       return CompositeLattice.calculateGLB(inputGLB, generateErrorMessage(cd, aan));
 838     }
 839
 840   }
 841
 842   private CompositeLocation inferRelationsFromCreateObjectNode(MethodDescriptor md,
 843       SymbolTable nametable, CreateObjectNode con) {
 844
 845     ClassDescriptor cd = md.getClassDesc();
 846
 847     CompositeLocation compLoc = new CompositeLocation();
 848     compLoc.addLocation(Location.createTopLocation(md));
 849     return compLoc;
 850
 851   }
 852
 853   private CompositeLocation inferRelationsFromOpNode(MethodDescriptor md, SymbolTable nametable,
 854       OpNode on, CompositeLocation constraint) {
 855
 856     ClassDescriptor cd = md.getClassDesc();
 857     CompositeLocation leftLoc = new CompositeLocation();
 858     leftLoc =
 859         inferRelationsFromExpressionNode(md, nametable, on.getLeft(), leftLoc, constraint, false);
 860     // addTypeLocation(on.getLeft().getType(), leftLoc);
 861
 862     CompositeLocation rightLoc = new CompositeLocation();
 863     if (on.getRight() != null) {
 864       rightLoc =
 865           inferRelationsFromExpressionNode(md, nametable, on.getRight(), rightLoc, constraint, false);
 866       // addTypeLocation(on.getRight().getType(), rightLoc);
 867     }
 868
 869     System.out.println("\n# OP NODE=" + on.printNode(0));
 870     System.out.println("# left loc=" + leftLoc + " from " + on.getLeft().getClass());
 871     if (on.getRight() != null) {
 872       System.out.println("# right loc=" + rightLoc + " from " + on.getRight().getClass());
 873     }
 874
 875     Operation op = on.getOp();
 876
 877     switch (op.getOp()) {
 878
 879     case Operation.UNARYPLUS:
 880     case Operation.UNARYMINUS:
 881     case Operation.LOGIC_NOT:
 882       // single operand
 883       return leftLoc;
 884
 885     case Operation.LOGIC_OR:
 886     case Operation.LOGIC_AND:
 887     case Operation.COMP:
 888     case Operation.BIT_OR:
 889     case Operation.BIT_XOR:
 890     case Operation.BIT_AND:
 891     case Operation.ISAVAILABLE:
 892     case Operation.EQUAL:
 893     case Operation.NOTEQUAL:
 894     case Operation.LT:
 895     case Operation.GT:
 896     case Operation.LTE:
 897     case Operation.GTE:
 898     case Operation.ADD:
 899     case Operation.SUB:
 900     case Operation.MULT:
 901     case Operation.DIV:
 902     case Operation.MOD:
 903     case Operation.LEFTSHIFT:
 904     case Operation.RIGHTSHIFT:
 905     case Operation.URIGHTSHIFT:
 906
 907       Set<CompositeLocation> inputSet = new HashSet<CompositeLocation>();
 908       inputSet.add(leftLoc);
 909       inputSet.add(rightLoc);
 910       CompositeLocation glbCompLoc =
 911           CompositeLattice.calculateGLB(inputSet, generateErrorMessage(cd, on));
 912       System.out.println("# glbCompLoc=" + glbCompLoc);
 913       return glbCompLoc;
 914
 915     default:
 916       throw new Error(op.toString());
 917     }
 918
 919   }
 920     */
 921   private VarID inferRelationsFromLiteralNode(MethodDescriptor md,
 922   SymbolTable nametable, LiteralNode ln) {
 923       //literal data flow does not matter
 924     return null;
 925
 926   }
 927
 928   private VarID inferRelationsFromNameNode(MethodDescriptor md, SymbolTable nametable,
 929     NameNode nn, VarID flowTo) {
 930     VarID var = null;
 931     NameDescriptor nd = nn.getName();
 932     if (nd.getBase() != null) {
 933       var =
 934           inferRelationsFromExpressionNode(md, nametable, nn.getExpression(), flowTo, false);
 935     } else {
 936       String varname = nd.toString();
 937       if (varname.equals("this")) {
 938         var = new VarID(nd);
 939         if(flowTo != null){
 940             rSet.addRelation(new BinaryRelation(var,flowTo));
 941         }
 942         var.setThis();
 943         return var;
 944       }
 945
 946       Descriptor d = (Descriptor) nametable.get(varname);
 947
 948       if (d instanceof VarDescriptor) {
 949         var = new VarID(nd);
 950         if(flowTo != null){
 951           rSet.addRelation(new BinaryRelation(var,flowTo));
 952         }
 953       } else if (d instanceof FieldDescriptor) {
 954         FieldDescriptor fd = (FieldDescriptor) d;
 955         if (fd.isStatic()) {
 956           if (fd.isFinal()) {
 957             var = new VarID(nd);
 958             if(flowTo != null){
 959               rSet.addRelation(new BinaryRelation(var,flowTo));
 960             }
 961             var.setTop();
 962             return var;
 963           } else {
 964             var = new VarID(nd);
 965             if(flowTo != null){
 966               rSet.addRelation(new BinaryRelation(var,flowTo));
 967             }
 968             var.setGlobal();
 969           }
 970         } else {
 971             var = new VarID(nd);
 972             if(flowTo != null){
 973               rSet.addRelation(new BinaryRelation(var,flowTo));
 974             }
 975             var.setThis();
 976         }
 977       } else if (d == null) {
 978         var = new VarID(nd);
 979           if(flowTo != null){
 980             rSet.addRelation(new BinaryRelation(var,flowTo));
 981           }
 982         var.setGlobal();
 983         return var;
 984       }
 985     }
 986     return var;
 987   }
 988   /*
 989   private CompositeLocation inferRelationsFromFieldAccessNode(MethodDescriptor md,
 990       SymbolTable nametable, FieldAccessNode fan, CompositeLocation loc,
 991       CompositeLocation constraint) {
 992
 993     ExpressionNode left = fan.getExpression();
 994     TypeDescriptor ltd = left.getType();
 995
 996     FieldDescriptor fd = fan.getField();
 997
 998     String varName = null;
 999     if (left.kind() == Kind.NameNode) {
1000       NameDescriptor nd = ((NameNode) left).getName();
1001       varName = nd.toString();
1002     }
1003
1004     if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
1005       // using a class name directly or access using this
1006       if (fd.isStatic() && fd.isFinal()) {
1007         loc.addLocation(Location.createTopLocation(md));
1008         return loc;
1009       }
1010     }
1011
1012     loc = inferRelationsFromExpressionNode(md, nametable, left, loc, constraint, false);
1013     System.out.println("### inferRelationsFromFieldAccessNode=" + fan.printNode(0));
1014     System.out.println("### left=" + left.printNode(0));
1015     if (!left.getType().isPrimitive()) {
1016       Location fieldLoc = getFieldLocation(fd);
1017       loc.addLocation(fieldLoc);
1018     }
1019
1020     return loc;
1021   }
1022
1023   private Location getFieldLocation(FieldDescriptor fd) {
1024
1025     System.out.println("### getFieldLocation=" + fd);
1026     System.out.println("### fd.getType().getExtension()=" + fd.getType().getExtension());
1027
1028     Location fieldLoc = (Location) fd.getType().getExtension();
1029
1030     // handle the case that method annotation checking skips checking field
1031     // declaration
1032     if (fieldLoc == null) {
1033       fieldLoc = checkFieldDeclaration(fd.getClassDescriptor(), fd);
1034     }
1035
1036     return fieldLoc;
1037
1038   }*/
1039
1040   private VarID inferRelationsFromAssignmentNode(MethodDescriptor md,
1041     SymbolTable nametable, AssignmentNode an, VarID flowTo) {
1042     ClassDescriptor cd = md.getClassDesc();
1043     boolean postinc = true;
1044
1045     if (an.getOperation().getBaseOp() == null
1046         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
1047             .getBaseOp().getOp() != Operation.POSTDEC))
1048       postinc = false;
1049     //get ID for leftside
1050     VarID destID = inferRelationsFromExpressionNode(md, nametable, an.getDest(), flowTo, true);
1051
1052     if (!postinc) {
1053       //recursively add relations from RHS to LHS
1054       inferRelationsFromExpressionNode(md, nametable, an.getSrc(), destID, false);
1055
1056     } else {
1057         //add relation to self
1058       destID = inferRelationsFromExpressionNode(md, nametable, an.getDest(), destID, false);
1059     }
1060
1061     //checks if flow to anythin and adds relation
1062     if(flowTo != null){
1063         rSet.addRelation(new BinaryRelation(destID, flowTo));
1064     }
1065
1066     //add relations for implicit flow
1067     for(ImplicitTuple it: implicitFlowSet){
1068         rSet.addRelation(new BinaryRelation(it.getVar(),destID));
1069     }
1070     return destID;
1071   }
1072 }