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);
 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       break;
 268 */
 269     default:
 270         System.out.println(bsn.kind() + " not handled...");
 271       break;
 272     }
 273   }
 274
 275     /*private CompositeLocation inferRelationsFromSwitchStatementNode(MethodDescriptor md,
 276       SymbolTable nametable, SwitchStatementNode ssn, CompositeLocation constraint) {
 277
 278     ClassDescriptor cd = md.getClassDesc();
 279     CompositeLocation condLoc =
 280         inferRelationsFromExpressionNode(md, nametable, ssn.getCondition(), new CompositeLocation(),
 281             constraint, false);
 282     BlockNode sbn = ssn.getSwitchBody();
 283
 284     constraint = generateNewConstraint(constraint, condLoc);
 285
 286     for (int i = 0; i < sbn.size(); i++) {
 287       inferRelationsFromSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i), constraint);
 288     }
 289     return new CompositeLocation();
 290   }
 291
 292   private CompositeLocation inferRelationsFromSwitchBlockNode(MethodDescriptor md,
 293       SymbolTable nametable, SwitchBlockNode sbn, CompositeLocation constraint) {
 294
 295     CompositeLocation blockLoc =
 296         inferRelationsFromBlockNode(md, nametable, sbn.getSwitchBlockStatement(), constraint);
 297
 298     return blockLoc;
 299
 300   }
 301
 302   private CompositeLocation inferRelationsFromReturnNode(MethodDescriptor md, SymbolTable nametable,
 303       ReturnNode rn, CompositeLocation constraint) {
 304
 305     ExpressionNode returnExp = rn.getReturnExpression();
 306
 307     CompositeLocation returnValueLoc;
 308     if (returnExp != null) {
 309       returnValueLoc =
 310           inferRelationsFromExpressionNode(md, nametable, returnExp, new CompositeLocation(),
 311               constraint, false);
 312
 313       // if this return statement is inside branch, return value has an implicit
 314       // flow from conditional location
 315       if (constraint != null) {
 316         Set<CompositeLocation> inputGLB = new HashSet<CompositeLocation>();
 317         inputGLB.add(returnValueLoc);
 318         inputGLB.add(constraint);
 319         returnValueLoc =
 320             CompositeLattice.calculateGLB(inputGLB, generateErrorMessage(md.getClassDesc(), rn));
 321       }
 322
 323       // check if return value is equal or higher than RETRUNLOC of method
 324       // declaration annotation
 325       CompositeLocation declaredReturnLoc = md2ReturnLoc.get(md);
 326
 327       int compareResult =
 328           CompositeLattice.compare(returnValueLoc, declaredReturnLoc, false,
 329               generateErrorMessage(md.getClassDesc(), rn));
 330
 331       if (compareResult == ComparisonResult.LESS || compareResult == ComparisonResult.INCOMPARABLE) {
 332         throw new Error(
 333             "Return value location is not equal or higher than the declaraed return location at "
 334                 + md.getClassDesc().getSourceFileName() + "::" + rn.getNumLine());
 335       }
 336     }
 337
 338     return new CompositeLocation();
 339   }
 340
 341   private boolean hasOnlyLiteralValue(ExpressionNode en) {
 342     if (en.kind() == Kind.LiteralNode) {
 343       return true;
 344     } else {
 345       return false;
 346     }
 347   }
 348
 349   private CompositeLocation inferRelationsFromLoopNode(MethodDescriptor md, SymbolTable nametable,
 350       LoopNode ln, CompositeLocation constraint) {
 351
 352     ClassDescriptor cd = md.getClassDesc();
 353     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
 354
 355       CompositeLocation condLoc =
 356           inferRelationsFromExpressionNode(md, nametable, ln.getCondition(),
 357               new CompositeLocation(), constraint, false);
 358       // addLocationType(ln.getCondition().getType(), (condLoc));
 359
 360       constraint = generateNewConstraint(constraint, condLoc);
 361       inferRelationsFromBlockNode(md, nametable, ln.getBody(), constraint);
 362
 363       return new CompositeLocation();
 364
 365     } else {
 366       // check 'for loop' case
 367       BlockNode bn = ln.getInitializer();
 368       bn.getVarTable().setParent(nametable);
 369
 370       // calculate glb location of condition and update statements
 371       CompositeLocation condLoc =
 372           inferRelationsFromExpressionNode(md, bn.getVarTable(), ln.getCondition(),
 373               new CompositeLocation(), constraint, false);
 374       // addLocationType(ln.getCondition().getType(), condLoc);
 375
 376       constraint = generateNewConstraint(constraint, condLoc);
 377
 378       inferRelationsFromBlockNode(md, bn.getVarTable(), ln.getUpdate(), constraint);
 379       inferRelationsFromBlockNode(md, bn.getVarTable(), ln.getBody(), constraint);
 380
 381       return new CompositeLocation();
 382
 383     }
 384
 385   }
 386     */
 387   private void inferRelationsFromSubBlockNode(MethodDescriptor md,
 388       SymbolTable nametable, SubBlockNode sbn) {
 389      inferRelationsFromBlockNode(md, nametable, sbn.getBlockNode());
 390   }
 391
 392
 393   private void inferRelationsFromIfStatementNode(MethodDescriptor md,
 394       SymbolTable nametable, IfStatementNode isn) {
 395
 396       inferRelationsFromExpressionNode(md, nametable, isn.getCondition(), null, isn, false);
 397
 398     inferRelationsFromBlockNode(md, nametable, isn.getTrueBlock());
 399
 400     if (isn.getFalseBlock() != null) {
 401       inferRelationsFromBlockNode(md, nametable, isn.getFalseBlock());
 402     }
 403
 404     for(ImplicitTuple tuple: implicitFlowSet){
 405       if(tuple.isFromBranch(isn)){
 406         implicitFlowSet.remove(tuple);
 407       }
 408     }
 409   }
 410
 411   private void inferRelationsFromDeclarationNode(MethodDescriptor md,
 412       SymbolTable nametable, DeclarationNode dn) {
 413   }
 414
 415     /*private void inferRelationsFromSubBlockNode(MethodDescriptor md, SymbolTable nametable,
 416       SubBlockNode sbn) {
 417     inferRelationsFromBlockNode(md, nametable.getParent(), sbn.getBlockNode());
 418     }*/
 419
 420   private void inferRelationsFromBlockExpressionNode(MethodDescriptor md,
 421       SymbolTable nametable, BlockExpressionNode ben) {
 422       inferRelationsFromExpressionNode(md, nametable, ben.getExpression(), null, null, false);
 423     // addTypeLocation(ben.getExpression().getType(), compLoc);
 424   }
 425
 426   private VarID inferRelationsFromExpressionNode(MethodDescriptor md,
 427      SymbolTable nametable, ExpressionNode en, VarID flowTo, BlockStatementNode implicitTag, boolean isLHS) {
 428
 429     VarID var = null;
 430     switch (en.kind()) {
 431
 432     case Kind.AssignmentNode:
 433       var =
 434           inferRelationsFromAssignmentNode(md, nametable, (AssignmentNode) en, flowTo, implicitTag);
 435       break;
 436
 437       //   case Kind.FieldAccessNode:
 438       // var =
 439       //    inferRelationsFromFieldAccessNode(md, nametable, (FieldAccessNode) en, flowTo);
 440       // break;
 441
 442     case Kind.NameNode:
 443         var = inferRelationsFromNameNode(md, nametable, (NameNode) en, flowTo, implicitTag);
 444       break;
 445
 446       /* case Kind.OpNode:
 447         var = inferRelationsFromOpNode(md, nametable, (OpNode) en, flowTo);
 448       break;
 449
 450     case Kind.CreateObjectNode:
 451       var = inferRelationsFromCreateObjectNode(md, nametable, (CreateObjectNode) en);
 452       break;
 453
 454     case Kind.ArrayAccessNode:
 455       var =
 456           inferRelationsFromArrayAccessNode(md, nametable, (ArrayAccessNode) en, flowTo, isLHS);
 457       break;
 458       */
 459     case Kind.LiteralNode:
 460         var = inferRelationsFromLiteralNode(md, nametable, (LiteralNode) en);
 461       break;
 462       /*
 463      case Kind.MethodInvokeNode:
 464       var =
 465           inferRelationsFromMethodInvokeNode(md, nametable, (MethodInvokeNode) en, flowTo);
 466       break;
 467
 468     case Kind.TertiaryNode:
 469       var = inferRelationsFromTertiaryNode(md, nametable, (TertiaryNode) en);
 470       break;
 471
 472     case Kind.CastNode:
 473       var = inferRelationsFromCastNode(md, nametable, (CastNode) en);
 474       break;
 475       */
 476     // case Kind.InstanceOfNode:
 477     // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
 478     // return null;
 479
 480     // case Kind.ArrayInitializerNode:
 481     // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
 482     // td);
 483     // return null;
 484
 485     // case Kind.ClassTypeNode:
 486     // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
 487     // return null;
 488
 489     // case Kind.OffsetNode:
 490     // checkOffsetNode(md, nametable, (OffsetNode)en, td);
 491     // return null;
 492
 493     default:
 494         System.out.println("expressionnode not handled...");
 495       return null;
 496
 497     }
 498     // addTypeLocation(en.getType(), compLoc);
 499     return var;
 500
 501   }
 502     /*
 503  private CompositeLocation inferRelationsFromCastNode(MethodDescriptor md, SymbolTable nametable,
 504       CastNode cn, CompositeLocation constraint) {
 505
 506     ExpressionNode en = cn.getExpression();
 507     return inferRelationsFromExpressionNode(md, nametable, en, new CompositeLocation(), constraint,
 508         false);
 509
 510   }
 511
 512   private CompositeLocation inferRelationsFromTertiaryNode(MethodDescriptor md,
 513       SymbolTable nametable, TertiaryNode tn, CompositeLocation constraint) {
 514     ClassDescriptor cd = md.getClassDesc();
 515
 516     CompositeLocation condLoc =
 517         inferRelationsFromExpressionNode(md, nametable, tn.getCond(), new CompositeLocation(),
 518             constraint, false);
 519     // addLocationType(tn.getCond().getType(), condLoc);
 520     CompositeLocation trueLoc =
 521         inferRelationsFromExpressionNode(md, nametable, tn.getTrueExpr(), new CompositeLocation(),
 522             constraint, false);
 523     // addLocationType(tn.getTrueExpr().getType(), trueLoc);
 524     CompositeLocation falseLoc =
 525         inferRelationsFromExpressionNode(md, nametable, tn.getFalseExpr(), new CompositeLocation(),
 526             constraint, false);
 527     // addLocationType(tn.getFalseExpr().getType(), falseLoc);
 528
 529     // locations from true/false branches can be TOP when there are only literal
 530     // values
 531     // in this case, we don't need to check flow down rule!
 532
 533     // check if condLoc is higher than trueLoc & falseLoc
 534     if (!trueLoc.get(0).isTop()
 535         && !CompositeLattice.isGreaterThan(condLoc, trueLoc, generateErrorMessage(cd, tn))) {
 536       throw new Error(
 537           "The location of the condition expression is lower than the true expression at "
 538               + cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
 539     }
 540
 541     if (!falseLoc.get(0).isTop()
 542         && !CompositeLattice.isGreaterThan(condLoc, falseLoc,
 543             generateErrorMessage(cd, tn.getCond()))) {
 544       throw new Error(
 545           "The location of the condition expression is lower than the true expression at "
 546               + cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
 547     }
 548
 549     // then, return glb of trueLoc & falseLoc
 550     Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
 551     glbInputSet.add(trueLoc);
 552     glbInputSet.add(falseLoc);
 553
 554     return CompositeLattice.calculateGLB(glbInputSet, generateErrorMessage(cd, tn));
 555   }
 556
 557   private CompositeLocation inferRelationsFromMethodInvokeNode(MethodDescriptor md,
 558       SymbolTable nametable, MethodInvokeNode min, CompositeLocation loc,
 559       CompositeLocation constraint) {
 560
 561     CompositeLocation baseLocation = null;
 562     if (min.getExpression() != null) {
 563       baseLocation =
 564           inferRelationsFromExpressionNode(md, nametable, min.getExpression(),
 565               new CompositeLocation(), constraint, false);
 566     } else {
 567
 568       if (min.getMethod().isStatic()) {
 569         String globalLocId = ssjava.getMethodLattice(md).getGlobalLoc();
 570         if (globalLocId == null) {
 571           throw new Error("Method lattice does not define global variable location at "
 572               + generateErrorMessage(md.getClassDesc(), min));
 573         }
 574         baseLocation = new CompositeLocation(new Location(md, globalLocId));
 575       } else {
 576         String thisLocId = ssjava.getMethodLattice(md).getThisLoc();
 577         baseLocation = new CompositeLocation(new Location(md, thisLocId));
 578       }
 579     }
 580
 581     checkCalleeConstraints(md, nametable, min, baseLocation, constraint);
 582
 583     checkCallerArgumentLocationConstraints(md, nametable, min, baseLocation, constraint);
 584
 585     if (!min.getMethod().getReturnType().isVoid()) {
 586       // If method has a return value, compute the highest possible return
 587       // location in the caller's perspective
 588       CompositeLocation ceilingLoc =
 589           computeCeilingLocationForCaller(md, nametable, min, baseLocation, constraint);
 590       return ceilingLoc;
 591     }
 592
 593     return new CompositeLocation();
 594
 595   }
 596
 597   private void checkCallerArgumentLocationConstraints(MethodDescriptor md, SymbolTable nametable,
 598       MethodInvokeNode min, CompositeLocation callerBaseLoc, CompositeLocation constraint) {
 599     // if parameter location consists of THIS and FIELD location,
 600     // caller should pass an argument that is comparable to the declared
 601     // parameter location
 602     // and is not lower than the declared parameter location in the field
 603     // lattice.
 604
 605     MethodDescriptor calleemd = min.getMethod();
 606
 607     List<CompositeLocation> callerArgList = new ArrayList<CompositeLocation>();
 608     List<CompositeLocation> calleeParamList = new ArrayList<CompositeLocation>();
 609
 610     MethodLattice<String> calleeLattice = ssjava.getMethodLattice(calleemd);
 611     Location calleeThisLoc = new Location(calleemd, calleeLattice.getThisLoc());
 612
 613     for (int i = 0; i < min.numArgs(); i++) {
 614       ExpressionNode en = min.getArg(i);
 615       CompositeLocation callerArgLoc =
 616           inferRelationsFromExpressionNode(md, nametable, en, new CompositeLocation(), constraint,
 617               false);
 618       callerArgList.add(callerArgLoc);
 619     }
 620
 621     // setup callee params set
 622     for (int i = 0; i < calleemd.numParameters(); i++) {
 623       VarDescriptor calleevd = (VarDescriptor) calleemd.getParameter(i);
 624       CompositeLocation calleeLoc = d2loc.get(calleevd);
 625       calleeParamList.add(calleeLoc);
 626     }
 627
 628     String errorMsg = generateErrorMessage(md.getClassDesc(), min);
 629
 630     System.out.println("checkCallerArgumentLocationConstraints=" + min.printNode(0));
 631     System.out.println("base location=" + callerBaseLoc);
 632
 633     for (int i = 0; i < calleeParamList.size(); i++) {
 634       CompositeLocation calleeParamLoc = calleeParamList.get(i);
 635       if (calleeParamLoc.get(0).equals(calleeThisLoc) && calleeParamLoc.getSize() > 1) {
 636
 637         // callee parameter location has field information
 638         CompositeLocation callerArgLoc = callerArgList.get(i);
 639
 640         CompositeLocation paramLocation =
 641             translateCalleeParamLocToCaller(md, calleeParamLoc, callerBaseLoc, errorMsg);
 642
 643         Set<CompositeLocation> inputGLBSet = new HashSet<CompositeLocation>();
 644         if (constraint != null) {
 645           inputGLBSet.add(callerArgLoc);
 646           inputGLBSet.add(constraint);
 647           callerArgLoc =
 648               CompositeLattice.calculateGLB(inputGLBSet,
 649                   generateErrorMessage(md.getClassDesc(), min));
 650         }
 651
 652         if (!CompositeLattice.isGreaterThan(callerArgLoc, paramLocation, errorMsg)) {
 653           throw new Error("Caller argument '" + min.getArg(i).printNode(0) + " : " + callerArgLoc
 654               + "' should be higher than corresponding callee's parameter : " + paramLocation
 655               + " at " + errorMsg);
 656         }
 657
 658       }
 659     }
 660
 661   }
 662
 663   private CompositeLocation translateCalleeParamLocToCaller(MethodDescriptor md,
 664       CompositeLocation calleeParamLoc, CompositeLocation callerBaseLocation, String errorMsg) {
 665
 666     CompositeLocation translate = new CompositeLocation();
 667
 668     for (int i = 0; i < callerBaseLocation.getSize(); i++) {
 669       translate.addLocation(callerBaseLocation.get(i));
 670     }
 671
 672     for (int i = 1; i < calleeParamLoc.getSize(); i++) {
 673       translate.addLocation(calleeParamLoc.get(i));
 674     }
 675
 676     System.out.println("TRANSLATED=" + translate + " from calleeParamLoc=" + calleeParamLoc);
 677
 678     return translate;
 679   }
 680
 681   private CompositeLocation computeCeilingLocationForCaller(MethodDescriptor md,
 682       SymbolTable nametable, MethodInvokeNode min, CompositeLocation baseLocation,
 683       CompositeLocation constraint) {
 684     List<CompositeLocation> argList = new ArrayList<CompositeLocation>();
 685
 686     // by default, method has a THIS parameter
 687     argList.add(baseLocation);
 688
 689     for (int i = 0; i < min.numArgs(); i++) {
 690       ExpressionNode en = min.getArg(i);
 691       CompositeLocation callerArg =
 692           inferRelationsFromExpressionNode(md, nametable, en, new CompositeLocation(), constraint,
 693               false);
 694       argList.add(callerArg);
 695     }
 696
 697     System.out.println("\n## computeReturnLocation=" + min.getMethod() + " argList=" + argList);
 698     CompositeLocation compLoc = md2ReturnLocGen.get(min.getMethod()).computeReturnLocation(argList);
 699     DeltaLocation delta = new DeltaLocation(compLoc, 1);
 700     System.out.println("##computeReturnLocation=" + delta);
 701
 702     return delta;
 703
 704   }
 705
 706   private void checkCalleeConstraints(MethodDescriptor md, SymbolTable nametable,
 707       MethodInvokeNode min, CompositeLocation callerBaseLoc, CompositeLocation constraint) {
 708
 709     System.out.println("checkCalleeConstraints="+min.printNode(0));
 710
 711     MethodDescriptor calleemd = min.getMethod();
 712
 713     MethodLattice<String> calleeLattice = ssjava.getMethodLattice(calleemd);
 714     CompositeLocation calleeThisLoc =
 715         new CompositeLocation(new Location(calleemd, calleeLattice.getThisLoc()));
 716
 717     List<CompositeLocation> callerArgList = new ArrayList<CompositeLocation>();
 718     List<CompositeLocation> calleeParamList = new ArrayList<CompositeLocation>();
 719
 720     if (min.numArgs() > 0) {
 721       // caller needs to guarantee that it passes arguments in regarding to
 722       // callee's hierarchy
 723
 724       // setup caller args set
 725       // first, add caller's base(this) location
 726       callerArgList.add(callerBaseLoc);
 727       // second, add caller's arguments
 728       for (int i = 0; i < min.numArgs(); i++) {
 729         ExpressionNode en = min.getArg(i);
 730         CompositeLocation callerArgLoc =
 731             inferRelationsFromExpressionNode(md, nametable, en, new CompositeLocation(), constraint,
 732                 false);
 733         callerArgList.add(callerArgLoc);
 734       }
 735
 736       // setup callee params set
 737       // first, add callee's this location
 738       calleeParamList.add(calleeThisLoc);
 739       // second, add callee's parameters
 740       for (int i = 0; i < calleemd.numParameters(); i++) {
 741         VarDescriptor calleevd = (VarDescriptor) calleemd.getParameter(i);
 742         CompositeLocation calleeLoc = d2loc.get(calleevd);
 743         System.out.println("calleevd="+calleevd+" loc="+calleeLoc);
 744         calleeParamList.add(calleeLoc);
 745       }
 746
 747       // here, check if ordering relations among caller's args respect
 748       // ordering relations in-between callee's args
 749       CHECK: for (int i = 0; i < calleeParamList.size(); i++) {
 750         CompositeLocation calleeLoc1 = calleeParamList.get(i);
 751         CompositeLocation callerLoc1 = callerArgList.get(i);
 752
 753         for (int j = 0; j < calleeParamList.size(); j++) {
 754           if (i != j) {
 755             CompositeLocation calleeLoc2 = calleeParamList.get(j);
 756             CompositeLocation callerLoc2 = callerArgList.get(j);
 757
 758             if (callerLoc1.get(callerLoc1.getSize() - 1).isTop()
 759                 || callerLoc2.get(callerLoc2.getSize() - 1).isTop()) {
 760               continue CHECK;
 761             }
 762
 763             System.out.println("calleeLoc1="+calleeLoc1);
 764             System.out.println("calleeLoc2="+calleeLoc2+"calleeParamList="+calleeParamList);
 765
 766             int callerResult =
 767                 CompositeLattice.compare(callerLoc1, callerLoc2, true,
 768                     generateErrorMessage(md.getClassDesc(), min));
 769             int calleeResult =
 770                 CompositeLattice.compare(calleeLoc1, calleeLoc2, true,
 771                     generateErrorMessage(md.getClassDesc(), min));
 772
 773             if (calleeResult == ComparisonResult.GREATER
 774                 && callerResult != ComparisonResult.GREATER) {
 775               // If calleeLoc1 is higher than calleeLoc2
 776               // then, caller should have same ordering relation in-bet
 777               // callerLoc1 & callerLoc2
 778
 779               String paramName1, paramName2;
 780
 781               if (i == 0) {
 782                 paramName1 = "'THIS'";
 783               } else {
 784                 paramName1 = "'parameter " + calleemd.getParamName(i - 1) + "'";
 785               }
 786
 787               if (j == 0) {
 788                 paramName2 = "'THIS'";
 789               } else {
 790                 paramName2 = "'parameter " + calleemd.getParamName(j - 1) + "'";
 791               }
 792
 793               throw new Error(
 794                   "Caller doesn't respect an ordering relation among method arguments: callee expects that "
 795                       + paramName1 + " should be higher than " + paramName2 + " in " + calleemd
 796                       + " at " + md.getClassDesc().getSourceFileName() + ":" + min.getNumLine());
 797             }
 798           }
 799
 800         }
 801       }
 802
 803     }
 804
 805   }
 806
 807   private CompositeLocation inferRelationsFromArrayAccessNode(MethodDescriptor md,
 808       SymbolTable nametable, ArrayAccessNode aan, CompositeLocation constraint, boolean isLHS) {
 809
 810     ClassDescriptor cd = md.getClassDesc();
 811
 812     CompositeLocation arrayLoc =
 813         inferRelationsFromExpressionNode(md, nametable, aan.getExpression(),
 814             new CompositeLocation(), constraint, isLHS);
 815     // addTypeLocation(aan.getExpression().getType(), arrayLoc);
 816     CompositeLocation indexLoc =
 817         inferRelationsFromExpressionNode(md, nametable, aan.getIndex(), new CompositeLocation(),
 818             constraint, isLHS);
 819     // addTypeLocation(aan.getIndex().getType(), indexLoc);
 820
 821     if (isLHS) {
 822       if (!CompositeLattice.isGreaterThan(indexLoc, arrayLoc, generateErrorMessage(cd, aan))) {
 823         throw new Error("Array index value is not higher than array location at "
 824             + generateErrorMessage(cd, aan));
 825       }
 826       return arrayLoc;
 827     } else {
 828       Set<CompositeLocation> inputGLB = new HashSet<CompositeLocation>();
 829       inputGLB.add(arrayLoc);
 830       inputGLB.add(indexLoc);
 831       return CompositeLattice.calculateGLB(inputGLB, generateErrorMessage(cd, aan));
 832     }
 833
 834   }
 835
 836   private CompositeLocation inferRelationsFromCreateObjectNode(MethodDescriptor md,
 837       SymbolTable nametable, CreateObjectNode con) {
 838
 839     ClassDescriptor cd = md.getClassDesc();
 840
 841     CompositeLocation compLoc = new CompositeLocation();
 842     compLoc.addLocation(Location.createTopLocation(md));
 843     return compLoc;
 844
 845   }
 846
 847   private CompositeLocation inferRelationsFromOpNode(MethodDescriptor md, SymbolTable nametable,
 848       OpNode on, CompositeLocation constraint) {
 849
 850     ClassDescriptor cd = md.getClassDesc();
 851     CompositeLocation leftLoc = new CompositeLocation();
 852     leftLoc =
 853         inferRelationsFromExpressionNode(md, nametable, on.getLeft(), leftLoc, constraint, false);
 854     // addTypeLocation(on.getLeft().getType(), leftLoc);
 855
 856     CompositeLocation rightLoc = new CompositeLocation();
 857     if (on.getRight() != null) {
 858       rightLoc =
 859           inferRelationsFromExpressionNode(md, nametable, on.getRight(), rightLoc, constraint, false);
 860       // addTypeLocation(on.getRight().getType(), rightLoc);
 861     }
 862
 863     System.out.println("\n# OP NODE=" + on.printNode(0));
 864     System.out.println("# left loc=" + leftLoc + " from " + on.getLeft().getClass());
 865     if (on.getRight() != null) {
 866       System.out.println("# right loc=" + rightLoc + " from " + on.getRight().getClass());
 867     }
 868
 869     Operation op = on.getOp();
 870
 871     switch (op.getOp()) {
 872
 873     case Operation.UNARYPLUS:
 874     case Operation.UNARYMINUS:
 875     case Operation.LOGIC_NOT:
 876       // single operand
 877       return leftLoc;
 878
 879     case Operation.LOGIC_OR:
 880     case Operation.LOGIC_AND:
 881     case Operation.COMP:
 882     case Operation.BIT_OR:
 883     case Operation.BIT_XOR:
 884     case Operation.BIT_AND:
 885     case Operation.ISAVAILABLE:
 886     case Operation.EQUAL:
 887     case Operation.NOTEQUAL:
 888     case Operation.LT:
 889     case Operation.GT:
 890     case Operation.LTE:
 891     case Operation.GTE:
 892     case Operation.ADD:
 893     case Operation.SUB:
 894     case Operation.MULT:
 895     case Operation.DIV:
 896     case Operation.MOD:
 897     case Operation.LEFTSHIFT:
 898     case Operation.RIGHTSHIFT:
 899     case Operation.URIGHTSHIFT:
 900
 901       Set<CompositeLocation> inputSet = new HashSet<CompositeLocation>();
 902       inputSet.add(leftLoc);
 903       inputSet.add(rightLoc);
 904       CompositeLocation glbCompLoc =
 905           CompositeLattice.calculateGLB(inputSet, generateErrorMessage(cd, on));
 906       System.out.println("# glbCompLoc=" + glbCompLoc);
 907       return glbCompLoc;
 908
 909     default:
 910       throw new Error(op.toString());
 911     }
 912
 913   }
 914     */
 915   private VarID inferRelationsFromLiteralNode(MethodDescriptor md,
 916   SymbolTable nametable, LiteralNode ln) {
 917       //literal data flow does not matter
 918     return null;
 919
 920   }
 921
 922   private VarID inferRelationsFromNameNode(MethodDescriptor md, SymbolTable nametable,
 923                                            NameNode nn, VarID flowTo, BlockStatementNode implicitTag) {
 924     VarID var = null;
 925     NameDescriptor nd = nn.getName();
 926     if (nd.getBase() != null) {
 927       var =
 928           inferRelationsFromExpressionNode(md, nametable, nn.getExpression(), flowTo, implicitTag, false);
 929     } else {
 930       String varname = nd.toString();
 931       if (varname.equals("this")) {
 932         var = new VarID(nd);
 933         if(flowTo != null){
 934             rSet.addRelation(new BinaryRelation(var,flowTo));
 935         }
 936         if(implicitTag != null){
 937             implicitFlowSet.add(new ImplicitTuple(var,implicitTag));
 938         }
 939         var.setThis();
 940         return var;
 941       }
 942
 943       Descriptor d = (Descriptor) nametable.get(varname);
 944
 945       if (d instanceof VarDescriptor) {
 946         var = new VarID(nd);
 947         if(flowTo != null){
 948           rSet.addRelation(new BinaryRelation(var,flowTo));
 949         }
 950         if(implicitTag != null){
 951             implicitFlowSet.add(new ImplicitTuple(var,implicitTag));
 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             if(implicitTag != null){
 962                 implicitFlowSet.add(new ImplicitTuple(var,implicitTag));
 963             }
 964             var.setTop();
 965             return var;
 966           } else {
 967             var = new VarID(nd);
 968             if(flowTo != null){
 969               rSet.addRelation(new BinaryRelation(var,flowTo));
 970             }
 971             if(implicitTag != null){
 972                 implicitFlowSet.add(new ImplicitTuple(var,implicitTag));
 973             }
 974             var.setGlobal();
 975           }
 976         } else {
 977             var = new VarID(nd);
 978             if(flowTo != null){
 979               rSet.addRelation(new BinaryRelation(var,flowTo));
 980             }
 981             if(implicitTag != null){
 982                 implicitFlowSet.add(new ImplicitTuple(var,implicitTag));
 983             }
 984             var.setThis();
 985         }
 986       } else if (d == null) {
 987         var = new VarID(nd);
 988         if(flowTo != null){
 989           rSet.addRelation(new BinaryRelation(var,flowTo));
 990         }
 991         if(implicitTag != null){
 992             implicitFlowSet.add(new ImplicitTuple(var,implicitTag));
 993         }
 994         var.setGlobal();
 995         return var;
 996       }
 997     }
 998     return var;
 999   }
1000   /*
1001   private CompositeLocation inferRelationsFromFieldAccessNode(MethodDescriptor md,
1002       SymbolTable nametable, FieldAccessNode fan, CompositeLocation loc,
1003       CompositeLocation constraint) {
1004
1005     ExpressionNode left = fan.getExpression();
1006     TypeDescriptor ltd = left.getType();
1007
1008     FieldDescriptor fd = fan.getField();
1009
1010     String varName = null;
1011     if (left.kind() == Kind.NameNode) {
1012       NameDescriptor nd = ((NameNode) left).getName();
1013       varName = nd.toString();
1014     }
1015
1016     if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
1017       // using a class name directly or access using this
1018       if (fd.isStatic() && fd.isFinal()) {
1019         loc.addLocation(Location.createTopLocation(md));
1020         return loc;
1021       }
1022     }
1023
1024     loc = inferRelationsFromExpressionNode(md, nametable, left, loc, constraint, false);
1025     System.out.println("### inferRelationsFromFieldAccessNode=" + fan.printNode(0));
1026     System.out.println("### left=" + left.printNode(0));
1027     if (!left.getType().isPrimitive()) {
1028       Location fieldLoc = getFieldLocation(fd);
1029       loc.addLocation(fieldLoc);
1030     }
1031
1032     return loc;
1033   }
1034
1035   private Location getFieldLocation(FieldDescriptor fd) {
1036
1037     System.out.println("### getFieldLocation=" + fd);
1038     System.out.println("### fd.getType().getExtension()=" + fd.getType().getExtension());
1039
1040     Location fieldLoc = (Location) fd.getType().getExtension();
1041
1042     // handle the case that method annotation checking skips checking field
1043     // declaration
1044     if (fieldLoc == null) {
1045       fieldLoc = checkFieldDeclaration(fd.getClassDescriptor(), fd);
1046     }
1047
1048     return fieldLoc;
1049
1050   }*/
1051
1052   private VarID inferRelationsFromAssignmentNode(MethodDescriptor md,
1053          SymbolTable nametable, AssignmentNode an, VarID flowTo, BlockStatementNode implicitTag) {
1054     ClassDescriptor cd = md.getClassDesc();
1055     boolean postinc = true;
1056
1057     if (an.getOperation().getBaseOp() == null
1058         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
1059             .getBaseOp().getOp() != Operation.POSTDEC))
1060       postinc = false;
1061     //get ID for leftside
1062     VarID destID = inferRelationsFromExpressionNode(md, nametable, an.getDest(), flowTo, implicitTag, true);
1063
1064     if (!postinc) {
1065       //recursively add relations from RHS to LHS
1066         inferRelationsFromExpressionNode(md, nametable, an.getSrc(), destID, null, false);
1067
1068     } else {
1069         //add relation to self
1070         destID = inferRelationsFromExpressionNode(md, nametable, an.getDest(), destID, null, false);
1071     }
1072
1073     //checks if flow to anythin and adds relation
1074     if(flowTo != null){
1075         rSet.addRelation(new BinaryRelation(destID, flowTo));
1076     }
1077
1078     //add relations for implicit flow
1079     for(ImplicitTuple it: implicitFlowSet){
1080         rSet.addRelation(new BinaryRelation(it.getVar(),destID));
1081     }
1082
1083     return destID;
1084   }
1085 }