Robust/src/Analysis/SSJava/SSJavaInferenceEngine.java

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