Robust/src/Analysis/SSJava/SSJavaInferenceEngine.java

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