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