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