Robust/src/Analysis/SSJava/FlowDownCheck.java

   1 package Analysis.SSJava;
   2
   3 import java.util.ArrayList;
   4 import java.util.HashSet;
   5 import java.util.Hashtable;
   6 import java.util.Iterator;
   7 import java.util.List;
   8 import java.util.Set;
   9 import java.util.StringTokenizer;
  10 import java.util.Vector;
  11
  12 import Analysis.SSJava.FlowDownCheck.ComparisonResult;
  13 import Analysis.SSJava.FlowDownCheck.CompositeLattice;
  14 import IR.AnnotationDescriptor;
  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.TypeDescriptor;
  24 import IR.VarDescriptor;
  25 import IR.Tree.ArrayAccessNode;
  26 import IR.Tree.AssignmentNode;
  27 import IR.Tree.BlockExpressionNode;
  28 import IR.Tree.BlockNode;
  29 import IR.Tree.BlockStatementNode;
  30 import IR.Tree.CastNode;
  31 import IR.Tree.CreateObjectNode;
  32 import IR.Tree.DeclarationNode;
  33 import IR.Tree.ExpressionNode;
  34 import IR.Tree.FieldAccessNode;
  35 import IR.Tree.IfStatementNode;
  36 import IR.Tree.Kind;
  37 import IR.Tree.LiteralNode;
  38 import IR.Tree.LoopNode;
  39 import IR.Tree.MethodInvokeNode;
  40 import IR.Tree.NameNode;
  41 import IR.Tree.OpNode;
  42 import IR.Tree.ReturnNode;
  43 import IR.Tree.SubBlockNode;
  44 import IR.Tree.TertiaryNode;
  45 import IR.Tree.TreeNode;
  46 import Util.Pair;
  47
  48 public class FlowDownCheck {
  49
  50   State state;
  51   static SSJavaAnalysis ssjava;
  52
  53   HashSet toanalyze;
  54
  55   // mapping from 'descriptor' to 'composite location'
  56   Hashtable<Descriptor, CompositeLocation> d2loc;
  57
  58   Hashtable<MethodDescriptor, CompositeLocation> md2ReturnLoc;
  59   Hashtable<MethodDescriptor, ReturnLocGenerator> md2ReturnLocGen;
  60
  61   // mapping from 'locID' to 'class descriptor'
  62   Hashtable<String, ClassDescriptor> fieldLocName2cd;
  63
  64   public FlowDownCheck(SSJavaAnalysis ssjava, State state) {
  65     this.ssjava = ssjava;
  66     this.state = state;
  67     this.toanalyze = new HashSet();
  68     this.d2loc = new Hashtable<Descriptor, CompositeLocation>();
  69     this.fieldLocName2cd = new Hashtable<String, ClassDescriptor>();
  70     this.md2ReturnLoc = new Hashtable<MethodDescriptor, CompositeLocation>();
  71     this.md2ReturnLocGen = new Hashtable<MethodDescriptor, ReturnLocGenerator>();
  72   }
  73
  74   public void init() {
  75
  76     // construct mapping from the location name to the class descriptor
  77     // assume that the location name is unique through the whole program
  78
  79     Set<ClassDescriptor> cdSet = ssjava.getCd2lattice().keySet();
  80     for (Iterator iterator = cdSet.iterator(); iterator.hasNext();) {
  81       ClassDescriptor cd = (ClassDescriptor) iterator.next();
  82       SSJavaLattice<String> lattice = ssjava.getCd2lattice().get(cd);
  83       Set<String> fieldLocNameSet = lattice.getKeySet();
  84
  85       for (Iterator iterator2 = fieldLocNameSet.iterator(); iterator2.hasNext();) {
  86         String fieldLocName = (String) iterator2.next();
  87         fieldLocName2cd.put(fieldLocName, cd);
  88       }
  89
  90     }
  91
  92   }
  93
  94   public void flowDownCheck() {
  95     SymbolTable classtable = state.getClassSymbolTable();
  96
  97     // phase 1 : checking declaration node and creating mapping of 'type
  98     // desciptor' & 'location'
  99     toanalyze.addAll(classtable.getValueSet());
 100     toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
 101     while (!toanalyze.isEmpty()) {
 102       Object obj = toanalyze.iterator().next();
 103       ClassDescriptor cd = (ClassDescriptor) obj;
 104       toanalyze.remove(cd);
 105
 106       if (ssjava.needToBeAnnoated(cd) && (!cd.isInterface())) {
 107
 108         ClassDescriptor superDesc = cd.getSuperDesc();
 109         if (superDesc != null && (!superDesc.isInterface())
 110             && (!superDesc.getSymbol().equals("Object"))) {
 111           checkOrderingInheritance(superDesc, cd);
 112         }
 113
 114         checkDeclarationInClass(cd);
 115         for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
 116           MethodDescriptor md = (MethodDescriptor) method_it.next();
 117           if (ssjava.needTobeAnnotated(md)) {
 118             checkDeclarationInMethodBody(cd, md);
 119           }
 120         }
 121       }
 122
 123     }
 124
 125     // phase2 : checking assignments
 126     toanalyze.addAll(classtable.getValueSet());
 127     toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
 128     while (!toanalyze.isEmpty()) {
 129       Object obj = toanalyze.iterator().next();
 130       ClassDescriptor cd = (ClassDescriptor) obj;
 131       toanalyze.remove(cd);
 132
 133       checkClass(cd);
 134       for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
 135         MethodDescriptor md = (MethodDescriptor) method_it.next();
 136         if (ssjava.needTobeAnnotated(md)) {
 137           checkMethodBody(cd, md);
 138         }
 139       }
 140     }
 141
 142   }
 143
 144   private void checkOrderingInheritance(ClassDescriptor superCd, ClassDescriptor cd) {
 145     // here, we're going to check that sub class keeps same relative orderings
 146     // in respect to super class
 147
 148     SSJavaLattice<String> superLattice = ssjava.getClassLattice(superCd);
 149     SSJavaLattice<String> subLattice = ssjava.getClassLattice(cd);
 150
 151     if (superLattice != null) {
 152
 153       if (subLattice == null) {
 154         throw new Error("If a parent class '" + superCd
 155             + "' has a ordering lattice, its subclass '" + cd + "' should have one.");
 156       }
 157
 158       Set<Pair<String, String>> superPairSet = superLattice.getOrderingPairSet();
 159       Set<Pair<String, String>> subPairSet = subLattice.getOrderingPairSet();
 160
 161       for (Iterator iterator = superPairSet.iterator(); iterator.hasNext();) {
 162         Pair<String, String> pair = (Pair<String, String>) iterator.next();
 163
 164         if (!subPairSet.contains(pair)) {
 165           throw new Error("Subclass '" + cd + "' does not have the relative ordering '"
 166               + pair.getSecond() + " < " + pair.getFirst()
 167               + "' that is defined by its superclass '" + superCd + "'.");
 168         }
 169       }
 170
 171     }
 172     // if super class doesn't define lattice, then we don't need to check its
 173     // subclass
 174
 175   }
 176
 177   public Hashtable getMap() {
 178     return d2loc;
 179   }
 180
 181   private void checkDeclarationInMethodBody(ClassDescriptor cd, MethodDescriptor md) {
 182     BlockNode bn = state.getMethodBody(md);
 183
 184     // parsing returnloc annotation
 185     if (ssjava.needTobeAnnotated(md)) {
 186
 187       Vector<AnnotationDescriptor> methodAnnotations = md.getModifiers().getAnnotations();
 188       if (methodAnnotations != null) {
 189         for (int i = 0; i < methodAnnotations.size(); i++) {
 190           AnnotationDescriptor an = methodAnnotations.elementAt(i);
 191           if (an.getMarker().equals(ssjava.RETURNLOC)) {
 192             // developer explicitly defines method lattice
 193             String returnLocDeclaration = an.getValue();
 194             CompositeLocation returnLocComp =
 195                 parseLocationDeclaration(md, null, returnLocDeclaration);
 196             md2ReturnLoc.put(md, returnLocComp);
 197           }
 198         }
 199
 200         if (!md.getReturnType().isVoid() && !md2ReturnLoc.containsKey(md)) {
 201           throw new Error("Return location is not specified for the method " + md + " at "
 202               + cd.getSourceFileName());
 203         }
 204
 205       }
 206     }
 207
 208     List<CompositeLocation> paramList = new ArrayList<CompositeLocation>();
 209
 210     boolean hasReturnValue = (!md.getReturnType().isVoid());
 211     if (hasReturnValue) {
 212       MethodLattice<String> methodLattice = ssjava.getMethodLattice(md);
 213       String thisLocId = methodLattice.getThisLoc();
 214       CompositeLocation thisLoc = new CompositeLocation(new Location(md, thisLocId));
 215       paramList.add(thisLoc);
 216     }
 217
 218     for (int i = 0; i < md.numParameters(); i++) {
 219       // process annotations on method parameters
 220       VarDescriptor vd = (VarDescriptor) md.getParameter(i);
 221       assignLocationOfVarDescriptor(vd, md, md.getParameterTable(), bn);
 222       if (hasReturnValue) {
 223         paramList.add(d2loc.get(vd));
 224       }
 225     }
 226
 227     if (hasReturnValue) {
 228       md2ReturnLocGen.put(md, new ReturnLocGenerator(md2ReturnLoc.get(md), paramList));
 229     }
 230
 231     checkDeclarationInBlockNode(md, md.getParameterTable(), bn);
 232   }
 233
 234   private void checkDeclarationInBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
 235     bn.getVarTable().setParent(nametable);
 236     for (int i = 0; i < bn.size(); i++) {
 237       BlockStatementNode bsn = bn.get(i);
 238       checkDeclarationInBlockStatementNode(md, bn.getVarTable(), bsn);
 239     }
 240   }
 241
 242   private void checkDeclarationInBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
 243       BlockStatementNode bsn) {
 244
 245     switch (bsn.kind()) {
 246     case Kind.SubBlockNode:
 247       checkDeclarationInSubBlockNode(md, nametable, (SubBlockNode) bsn);
 248       return;
 249
 250     case Kind.DeclarationNode:
 251       checkDeclarationNode(md, nametable, (DeclarationNode) bsn);
 252       break;
 253
 254     case Kind.LoopNode:
 255       checkDeclarationInLoopNode(md, nametable, (LoopNode) bsn);
 256       break;
 257     }
 258   }
 259
 260   private void checkDeclarationInLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln) {
 261
 262     if (ln.getType() == LoopNode.FORLOOP) {
 263       // check for loop case
 264       ClassDescriptor cd = md.getClassDesc();
 265       BlockNode bn = ln.getInitializer();
 266       for (int i = 0; i < bn.size(); i++) {
 267         BlockStatementNode bsn = bn.get(i);
 268         checkDeclarationInBlockStatementNode(md, nametable, bsn);
 269       }
 270     }
 271
 272     // check loop body
 273     checkDeclarationInBlockNode(md, nametable, ln.getBody());
 274   }
 275
 276   private void checkMethodBody(ClassDescriptor cd, MethodDescriptor md) {
 277     BlockNode bn = state.getMethodBody(md);
 278     checkLocationFromBlockNode(md, md.getParameterTable(), bn);
 279   }
 280
 281   private CompositeLocation checkLocationFromBlockNode(MethodDescriptor md, SymbolTable nametable,
 282       BlockNode bn) {
 283
 284     bn.getVarTable().setParent(nametable);
 285     // it will return the lowest location in the block node
 286     CompositeLocation lowestLoc = null;
 287
 288     for (int i = 0; i < bn.size(); i++) {
 289       BlockStatementNode bsn = bn.get(i);
 290       CompositeLocation bLoc = checkLocationFromBlockStatementNode(md, bn.getVarTable(), bsn);
 291       if (!bLoc.isEmpty()) {
 292         if (lowestLoc == null) {
 293           lowestLoc = bLoc;
 294         } else {
 295           if (CompositeLattice.isGreaterThan(lowestLoc, bLoc)) {
 296             lowestLoc = bLoc;
 297           }
 298         }
 299       }
 300
 301     }
 302
 303     if (lowestLoc == null) {
 304       lowestLoc = new CompositeLocation(Location.createBottomLocation(md));
 305     }
 306
 307     return lowestLoc;
 308   }
 309
 310   private CompositeLocation checkLocationFromBlockStatementNode(MethodDescriptor md,
 311       SymbolTable nametable, BlockStatementNode bsn) {
 312
 313     CompositeLocation compLoc = null;
 314     switch (bsn.kind()) {
 315     case Kind.BlockExpressionNode:
 316       compLoc = checkLocationFromBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
 317       break;
 318
 319     case Kind.DeclarationNode:
 320       compLoc = checkLocationFromDeclarationNode(md, nametable, (DeclarationNode) bsn);
 321       break;
 322
 323     case Kind.IfStatementNode:
 324       compLoc = checkLocationFromIfStatementNode(md, nametable, (IfStatementNode) bsn);
 325       break;
 326
 327     case Kind.LoopNode:
 328       compLoc = checkLocationFromLoopNode(md, nametable, (LoopNode) bsn);
 329       break;
 330
 331     case Kind.ReturnNode:
 332       compLoc = checkLocationFromReturnNode(md, nametable, (ReturnNode) bsn);
 333       break;
 334
 335     case Kind.SubBlockNode:
 336       compLoc = checkLocationFromSubBlockNode(md, nametable, (SubBlockNode) bsn);
 337       break;
 338
 339     case Kind.ContinueBreakNode:
 340       compLoc = new CompositeLocation();
 341       break;
 342
 343     }
 344     return compLoc;
 345   }
 346
 347   private CompositeLocation checkLocationFromReturnNode(MethodDescriptor md, SymbolTable nametable,
 348       ReturnNode rn) {
 349
 350     ExpressionNode returnExp = rn.getReturnExpression();
 351
 352     CompositeLocation expLoc;
 353     if (returnExp != null) {
 354       expLoc = checkLocationFromExpressionNode(md, nametable, returnExp, new CompositeLocation());
 355       // check if return value is equal or higher than RETRUNLOC of method
 356       // declaration annotation
 357       CompositeLocation returnLocAt = md2ReturnLoc.get(md);
 358
 359       if (CompositeLattice.isGreaterThan(returnLocAt, expLoc)) {
 360         throw new Error(
 361             "Return value location is not equal or higher than the declaraed return location at "
 362                 + md.getClassDesc().getSourceFileName() + "::" + rn.getNumLine());
 363       }
 364     }
 365
 366     return new CompositeLocation();
 367   }
 368
 369   private boolean hasOnlyLiteralValue(ExpressionNode en) {
 370     if (en.kind() == Kind.LiteralNode) {
 371       return true;
 372     } else {
 373       return false;
 374     }
 375   }
 376
 377   private CompositeLocation checkLocationFromLoopNode(MethodDescriptor md, SymbolTable nametable,
 378       LoopNode ln) {
 379
 380     ClassDescriptor cd = md.getClassDesc();
 381     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
 382
 383       CompositeLocation condLoc =
 384           checkLocationFromExpressionNode(md, nametable, ln.getCondition(), new CompositeLocation());
 385       addLocationType(ln.getCondition().getType(), (condLoc));
 386
 387       CompositeLocation bodyLoc = checkLocationFromBlockNode(md, nametable, ln.getBody());
 388
 389       if (!CompositeLattice.isGreaterThan(condLoc, bodyLoc)) {
 390         // loop condition should be higher than loop body
 391         throw new Error(
 392             "The location of the while-condition statement is lower than the loop body at "
 393                 + cd.getSourceFileName() + ":" + ln.getCondition().getNumLine());
 394       }
 395
 396       return bodyLoc;
 397
 398     } else {
 399       // check for loop case
 400       BlockNode bn = ln.getInitializer();
 401       bn.getVarTable().setParent(nametable);
 402
 403       // calculate glb location of condition and update statements
 404       CompositeLocation condLoc =
 405           checkLocationFromExpressionNode(md, bn.getVarTable(), ln.getCondition(),
 406               new CompositeLocation());
 407       addLocationType(ln.getCondition().getType(), condLoc);
 408
 409       CompositeLocation updateLoc =
 410           checkLocationFromBlockNode(md, bn.getVarTable(), ln.getUpdate());
 411
 412       Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
 413       glbInputSet.add(condLoc);
 414       // glbInputSet.add(updateLoc);
 415
 416       CompositeLocation glbLocOfForLoopCond = CompositeLattice.calculateGLB(glbInputSet);
 417
 418       // check location of 'forloop' body
 419       CompositeLocation blockLoc = checkLocationFromBlockNode(md, bn.getVarTable(), ln.getBody());
 420
 421       // compute glb of body including loop body and update statement
 422       glbInputSet.clear();
 423
 424       if (blockLoc == null) {
 425         // when there is no statement in the loop body
 426
 427         if (updateLoc == null) {
 428           // also there is no update statement in the loop body
 429           return glbLocOfForLoopCond;
 430         }
 431         glbInputSet.add(updateLoc);
 432
 433       } else {
 434         glbInputSet.add(blockLoc);
 435         glbInputSet.add(updateLoc);
 436       }
 437
 438       CompositeLocation loopBodyLoc = CompositeLattice.calculateGLB(glbInputSet);
 439
 440       if (!CompositeLattice.isGreaterThan(glbLocOfForLoopCond, loopBodyLoc)) {
 441         throw new Error(
 442             "The location of the for-condition statement is lower than the for-loop body at "
 443                 + cd.getSourceFileName() + ":" + ln.getCondition().getNumLine());
 444       }
 445       return blockLoc;
 446     }
 447
 448   }
 449
 450   private CompositeLocation checkLocationFromSubBlockNode(MethodDescriptor md,
 451       SymbolTable nametable, SubBlockNode sbn) {
 452     CompositeLocation compLoc = checkLocationFromBlockNode(md, nametable, sbn.getBlockNode());
 453     return compLoc;
 454   }
 455
 456   private CompositeLocation checkLocationFromIfStatementNode(MethodDescriptor md,
 457       SymbolTable nametable, IfStatementNode isn) {
 458
 459     ClassDescriptor localCD = md.getClassDesc();
 460     Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
 461
 462     CompositeLocation condLoc =
 463         checkLocationFromExpressionNode(md, nametable, isn.getCondition(), new CompositeLocation());
 464
 465     addLocationType(isn.getCondition().getType(), condLoc);
 466     glbInputSet.add(condLoc);
 467
 468     CompositeLocation locTrueBlock = checkLocationFromBlockNode(md, nametable, isn.getTrueBlock());
 469     if (locTrueBlock != null) {
 470       glbInputSet.add(locTrueBlock);
 471       // here, the location of conditional block should be higher than the
 472       // location of true/false blocks
 473       if (locTrueBlock != null && !CompositeLattice.isGreaterThan(condLoc, locTrueBlock)) {
 474         // error
 475         throw new Error(
 476             "The location of the if-condition statement is lower than the conditional block at "
 477                 + localCD.getSourceFileName() + ":" + isn.getCondition().getNumLine());
 478       }
 479     }
 480
 481     if (isn.getFalseBlock() != null) {
 482       CompositeLocation locFalseBlock =
 483           checkLocationFromBlockNode(md, nametable, isn.getFalseBlock());
 484
 485       if (locFalseBlock != null) {
 486         glbInputSet.add(locFalseBlock);
 487
 488         if (!CompositeLattice.isGreaterThan(condLoc, locFalseBlock)) {
 489           // error
 490           throw new Error(
 491               "The location of the if-condition statement is lower than the conditional block at "
 492                   + localCD.getSourceFileName() + ":" + isn.getCondition().getNumLine());
 493         }
 494       }
 495
 496     }
 497
 498     // return GLB location of condition, true, and false block
 499     CompositeLocation glbLoc = CompositeLattice.calculateGLB(glbInputSet);
 500
 501     return glbLoc;
 502   }
 503
 504   private CompositeLocation checkLocationFromDeclarationNode(MethodDescriptor md,
 505       SymbolTable nametable, DeclarationNode dn) {
 506
 507     VarDescriptor vd = dn.getVarDescriptor();
 508
 509     CompositeLocation destLoc = d2loc.get(vd);
 510
 511     if (dn.getExpression() != null) {
 512       CompositeLocation expressionLoc =
 513           checkLocationFromExpressionNode(md, nametable, dn.getExpression(),
 514               new CompositeLocation());
 515       // addTypeLocation(dn.getExpression().getType(), expressionLoc);
 516
 517       if (expressionLoc != null) {
 518         // checking location order
 519         if (!CompositeLattice.isGreaterThan(expressionLoc, destLoc)) {
 520           throw new Error("The value flow from " + expressionLoc + " to " + destLoc
 521               + " does not respect location hierarchy on the assignment " + dn.printNode(0)
 522               + " at " + md.getClassDesc().getSourceFileName() + "::" + dn.getNumLine());
 523         }
 524       }
 525       return expressionLoc;
 526
 527     } else {
 528
 529       return new CompositeLocation();
 530
 531     }
 532
 533   }
 534
 535   private void checkDeclarationInSubBlockNode(MethodDescriptor md, SymbolTable nametable,
 536       SubBlockNode sbn) {
 537     checkDeclarationInBlockNode(md, nametable.getParent(), sbn.getBlockNode());
 538   }
 539
 540   private CompositeLocation checkLocationFromBlockExpressionNode(MethodDescriptor md,
 541       SymbolTable nametable, BlockExpressionNode ben) {
 542     CompositeLocation compLoc =
 543         checkLocationFromExpressionNode(md, nametable, ben.getExpression(), null);
 544     // addTypeLocation(ben.getExpression().getType(), compLoc);
 545     return compLoc;
 546   }
 547
 548   private CompositeLocation checkLocationFromExpressionNode(MethodDescriptor md,
 549       SymbolTable nametable, ExpressionNode en, CompositeLocation loc) {
 550
 551     CompositeLocation compLoc = null;
 552     switch (en.kind()) {
 553
 554     case Kind.AssignmentNode:
 555       compLoc = checkLocationFromAssignmentNode(md, nametable, (AssignmentNode) en, loc);
 556       break;
 557
 558     case Kind.FieldAccessNode:
 559       compLoc = checkLocationFromFieldAccessNode(md, nametable, (FieldAccessNode) en, loc);
 560       break;
 561
 562     case Kind.NameNode:
 563       compLoc = checkLocationFromNameNode(md, nametable, (NameNode) en, loc);
 564       break;
 565
 566     case Kind.OpNode:
 567       compLoc = checkLocationFromOpNode(md, nametable, (OpNode) en);
 568       break;
 569
 570     case Kind.CreateObjectNode:
 571       compLoc = checkLocationFromCreateObjectNode(md, nametable, (CreateObjectNode) en);
 572       break;
 573
 574     case Kind.ArrayAccessNode:
 575       compLoc = checkLocationFromArrayAccessNode(md, nametable, (ArrayAccessNode) en);
 576       break;
 577
 578     case Kind.LiteralNode:
 579       compLoc = checkLocationFromLiteralNode(md, nametable, (LiteralNode) en, loc);
 580       break;
 581
 582     case Kind.MethodInvokeNode:
 583       compLoc = checkLocationFromMethodInvokeNode(md, nametable, (MethodInvokeNode) en, loc);
 584       break;
 585
 586     case Kind.TertiaryNode:
 587       compLoc = checkLocationFromTertiaryNode(md, nametable, (TertiaryNode) en);
 588       break;
 589
 590     case Kind.CastNode:
 591       compLoc = checkLocationFromCastNode(md, nametable, (CastNode) en);
 592       break;
 593
 594     // case Kind.InstanceOfNode:
 595     // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
 596     // return null;
 597
 598     // case Kind.ArrayInitializerNode:
 599     // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
 600     // td);
 601     // return null;
 602
 603     // case Kind.ClassTypeNode:
 604     // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
 605     // return null;
 606
 607     // case Kind.OffsetNode:
 608     // checkOffsetNode(md, nametable, (OffsetNode)en, td);
 609     // return null;
 610
 611     default:
 612       return null;
 613
 614     }
 615     // addTypeLocation(en.getType(), compLoc);
 616     return compLoc;
 617
 618   }
 619
 620   private CompositeLocation checkLocationFromCastNode(MethodDescriptor md, SymbolTable nametable,
 621       CastNode cn) {
 622
 623     ExpressionNode en = cn.getExpression();
 624     return checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation());
 625
 626   }
 627
 628   private CompositeLocation checkLocationFromTertiaryNode(MethodDescriptor md,
 629       SymbolTable nametable, TertiaryNode tn) {
 630     ClassDescriptor cd = md.getClassDesc();
 631
 632     CompositeLocation condLoc =
 633         checkLocationFromExpressionNode(md, nametable, tn.getCond(), new CompositeLocation());
 634     addLocationType(tn.getCond().getType(), condLoc);
 635     CompositeLocation trueLoc =
 636         checkLocationFromExpressionNode(md, nametable, tn.getTrueExpr(), new CompositeLocation());
 637     addLocationType(tn.getTrueExpr().getType(), trueLoc);
 638     CompositeLocation falseLoc =
 639         checkLocationFromExpressionNode(md, nametable, tn.getFalseExpr(), new CompositeLocation());
 640     addLocationType(tn.getFalseExpr().getType(), falseLoc);
 641
 642     // check if condLoc is higher than trueLoc & falseLoc
 643     if (!CompositeLattice.isGreaterThan(condLoc, trueLoc)) {
 644       throw new Error(
 645           "The location of the condition expression is lower than the true expression at "
 646               + cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
 647     }
 648
 649     if (!CompositeLattice.isGreaterThan(condLoc, falseLoc)) {
 650       throw new Error(
 651           "The location of the condition expression is lower than the true expression at "
 652               + cd.getSourceFileName() + ":" + tn.getCond().getNumLine());
 653     }
 654
 655     // then, return glb of trueLoc & falseLoc
 656     Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
 657     glbInputSet.add(trueLoc);
 658     glbInputSet.add(falseLoc);
 659
 660     return CompositeLattice.calculateGLB(glbInputSet);
 661   }
 662
 663   private CompositeLocation checkLocationFromMethodInvokeNode(MethodDescriptor md,
 664       SymbolTable nametable, MethodInvokeNode min, CompositeLocation loc) {
 665
 666     checkCalleeConstraints(md, nametable, min);
 667
 668     CompositeLocation baseLocation = null;
 669     if (min.getExpression() != null) {
 670       baseLocation =
 671           checkLocationFromExpressionNode(md, nametable, min.getExpression(),
 672               new CompositeLocation());
 673     } else {
 674       String thisLocId = ssjava.getMethodLattice(md).getThisLoc();
 675       baseLocation = new CompositeLocation(new Location(md, thisLocId));
 676     }
 677
 678     if (!min.getMethod().getReturnType().isVoid()) {
 679       // If method has a return value, compute the highest possible return
 680       // location in the caller's perspective
 681       CompositeLocation ceilingLoc =
 682           computeCeilingLocationForCaller(md, nametable, min, baseLocation);
 683       return ceilingLoc;
 684     }
 685
 686     return new CompositeLocation();
 687
 688   }
 689
 690   private CompositeLocation computeCeilingLocationForCaller(MethodDescriptor md,
 691       SymbolTable nametable, MethodInvokeNode min, CompositeLocation baseLocation) {
 692     List<CompositeLocation> argList = new ArrayList<CompositeLocation>();
 693
 694     // by default, method has a THIS parameter
 695     argList.add(baseLocation);
 696
 697     for (int i = 0; i < min.numArgs(); i++) {
 698       ExpressionNode en = min.getArg(i);
 699       CompositeLocation callerArg =
 700           checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation());
 701       argList.add(callerArg);
 702     }
 703
 704     return md2ReturnLocGen.get(min.getMethod()).computeReturnLocation(argList);
 705
 706   }
 707
 708   private void checkCalleeConstraints(MethodDescriptor md, SymbolTable nametable,
 709       MethodInvokeNode min) {
 710
 711     if (min.numArgs() > 1) {
 712       // caller needs to guarantee that it passes arguments in regarding to
 713       // callee's hierarchy
 714       for (int i = 0; i < min.numArgs(); i++) {
 715         ExpressionNode en = min.getArg(i);
 716         CompositeLocation callerArg1 =
 717             checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation());
 718
 719         ClassDescriptor calleecd = min.getMethod().getClassDesc();
 720         VarDescriptor calleevd = (VarDescriptor) min.getMethod().getParameter(i);
 721         CompositeLocation calleeLoc1 = d2loc.get(calleevd);
 722
 723         if (!callerArg1.get(0).isTop()) {
 724           // here, check if ordering relations among caller's args respect
 725           // ordering relations in-between callee's args
 726           for (int currentIdx = 0; currentIdx < min.numArgs(); currentIdx++) {
 727             if (currentIdx != i) { // skip itself
 728               ExpressionNode argExp = min.getArg(currentIdx);
 729
 730               CompositeLocation callerArg2 =
 731                   checkLocationFromExpressionNode(md, nametable, argExp, new CompositeLocation());
 732
 733               VarDescriptor calleevd2 = (VarDescriptor) min.getMethod().getParameter(currentIdx);
 734               CompositeLocation calleeLoc2 = d2loc.get(calleevd2);
 735
 736               int callerResult = CompositeLattice.compare(callerArg1, callerArg2);
 737               int calleeResult = CompositeLattice.compare(calleeLoc1, calleeLoc2);
 738               if (calleeResult == ComparisonResult.GREATER
 739                   && callerResult != ComparisonResult.GREATER) {
 740                 // If calleeLoc1 is higher than calleeLoc2
 741                 // then, caller should have same ordering relation in-bet
 742                 // callerLoc1 & callerLoc2
 743
 744                 throw new Error("Caller doesn't respect ordering relations among method arguments:"
 745                     + md.getClassDesc().getSourceFileName() + ":" + min.getNumLine());
 746               }
 747
 748             }
 749           }
 750         }
 751
 752       }
 753
 754     }
 755
 756   }
 757
 758   private CompositeLocation checkLocationFromArrayAccessNode(MethodDescriptor md,
 759       SymbolTable nametable, ArrayAccessNode aan) {
 760
 761     // return glb location of array itself and index
 762
 763     ClassDescriptor cd = md.getClassDesc();
 764
 765     Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
 766
 767     CompositeLocation arrayLoc =
 768         checkLocationFromExpressionNode(md, nametable, aan.getExpression(), new CompositeLocation());
 769     // addTypeLocation(aan.getExpression().getType(), arrayLoc);
 770     glbInputSet.add(arrayLoc);
 771     CompositeLocation indexLoc =
 772         checkLocationFromExpressionNode(md, nametable, aan.getIndex(), new CompositeLocation());
 773     glbInputSet.add(indexLoc);
 774     // addTypeLocation(aan.getIndex().getType(), indexLoc);
 775
 776     CompositeLocation glbLoc = CompositeLattice.calculateGLB(glbInputSet);
 777     return glbLoc;
 778   }
 779
 780   private CompositeLocation checkLocationFromCreateObjectNode(MethodDescriptor md,
 781       SymbolTable nametable, CreateObjectNode con) {
 782
 783     ClassDescriptor cd = md.getClassDesc();
 784
 785     // check arguments
 786     Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
 787     for (int i = 0; i < con.numArgs(); i++) {
 788       ExpressionNode en = con.getArg(i);
 789       CompositeLocation argLoc =
 790           checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation());
 791       glbInputSet.add(argLoc);
 792       addLocationType(en.getType(), argLoc);
 793     }
 794
 795     // check array initializers
 796     // if ((con.getArrayInitializer() != null)) {
 797     // checkLocationFromArrayInitializerNode(md, nametable,
 798     // con.getArrayInitializer());
 799     // }
 800
 801     if (glbInputSet.size() > 0) {
 802       return CompositeLattice.calculateGLB(glbInputSet);
 803     }
 804
 805     CompositeLocation compLoc = new CompositeLocation();
 806     compLoc.addLocation(Location.createTopLocation(md));
 807     return compLoc;
 808
 809   }
 810
 811   private CompositeLocation checkLocationFromOpNode(MethodDescriptor md, SymbolTable nametable,
 812       OpNode on) {
 813
 814     ClassDescriptor cd = md.getClassDesc();
 815     CompositeLocation leftLoc = new CompositeLocation();
 816     leftLoc = checkLocationFromExpressionNode(md, nametable, on.getLeft(), leftLoc);
 817     // addTypeLocation(on.getLeft().getType(), leftLoc);
 818
 819     CompositeLocation rightLoc = new CompositeLocation();
 820     if (on.getRight() != null) {
 821       rightLoc = checkLocationFromExpressionNode(md, nametable, on.getRight(), rightLoc);
 822       // addTypeLocation(on.getRight().getType(), rightLoc);
 823     }
 824
 825     // System.out.println("checking op node=" + on.printNode(0));
 826     // System.out.println("left loc=" + leftLoc + " from " +
 827     // on.getLeft().getClass());
 828     // System.out.println("right loc=" + rightLoc + " from " +
 829     // on.getRight().getClass());
 830
 831     Operation op = on.getOp();
 832
 833     switch (op.getOp()) {
 834
 835     case Operation.UNARYPLUS:
 836     case Operation.UNARYMINUS:
 837     case Operation.LOGIC_NOT:
 838       // single operand
 839       return leftLoc;
 840
 841     case Operation.LOGIC_OR:
 842     case Operation.LOGIC_AND:
 843     case Operation.COMP:
 844     case Operation.BIT_OR:
 845     case Operation.BIT_XOR:
 846     case Operation.BIT_AND:
 847     case Operation.ISAVAILABLE:
 848     case Operation.EQUAL:
 849     case Operation.NOTEQUAL:
 850     case Operation.LT:
 851     case Operation.GT:
 852     case Operation.LTE:
 853     case Operation.GTE:
 854     case Operation.ADD:
 855     case Operation.SUB:
 856     case Operation.MULT:
 857     case Operation.DIV:
 858     case Operation.MOD:
 859     case Operation.LEFTSHIFT:
 860     case Operation.RIGHTSHIFT:
 861     case Operation.URIGHTSHIFT:
 862
 863       Set<CompositeLocation> inputSet = new HashSet<CompositeLocation>();
 864       inputSet.add(leftLoc);
 865       inputSet.add(rightLoc);
 866       CompositeLocation glbCompLoc = CompositeLattice.calculateGLB(inputSet);
 867       return glbCompLoc;
 868
 869     default:
 870       throw new Error(op.toString());
 871     }
 872
 873   }
 874
 875   private CompositeLocation checkLocationFromLiteralNode(MethodDescriptor md,
 876       SymbolTable nametable, LiteralNode en, CompositeLocation loc) {
 877
 878     // literal value has the top location so that value can be flowed into any
 879     // location
 880     Location literalLoc = Location.createTopLocation(md);
 881     loc.addLocation(literalLoc);
 882     return loc;
 883
 884   }
 885
 886   private CompositeLocation checkLocationFromNameNode(MethodDescriptor md, SymbolTable nametable,
 887       NameNode nn, CompositeLocation loc) {
 888
 889     NameDescriptor nd = nn.getName();
 890     if (nd.getBase() != null) {
 891
 892       loc = checkLocationFromExpressionNode(md, nametable, nn.getExpression(), loc);
 893       // addTypeLocation(nn.getExpression().getType(), loc);
 894     } else {
 895       String varname = nd.toString();
 896
 897       if (varname.equals("this")) {
 898         // 'this' itself!
 899         MethodLattice<String> methodLattice = ssjava.getMethodLattice(md);
 900         String thisLocId = methodLattice.getThisLoc();
 901         if (thisLocId == null) {
 902           throw new Error("The location for 'this' is not defined at "
 903               + md.getClassDesc().getSourceFileName() + "::" + nn.getNumLine());
 904         }
 905         Location locElement = new Location(md, thisLocId);
 906         loc.addLocation(locElement);
 907         return loc;
 908       }
 909       Descriptor d = (Descriptor) nametable.get(varname);
 910
 911       // CompositeLocation localLoc = null;
 912       if (d instanceof VarDescriptor) {
 913         VarDescriptor vd = (VarDescriptor) d;
 914         // localLoc = d2loc.get(vd);
 915         // the type of var descriptor has a composite location!
 916         loc = ((CompositeLocation) vd.getType().getExtension()).clone();
 917       } else if (d instanceof FieldDescriptor) {
 918         // the type of field descriptor has a location!
 919         FieldDescriptor fd = (FieldDescriptor) d;
 920
 921         if (fd.isStatic()) {
 922           if (fd.isFinal()) {
 923             // if it is 'static final', the location has TOP since no one can
 924             // change its value
 925             loc.addLocation(Location.createTopLocation(md));
 926           } else {
 927             // if 'static', the location has pre-assigned global loc
 928             MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
 929             String globalLocId = localLattice.getGlobalLoc();
 930             if (globalLocId == null) {
 931               throw new Error("Global location element is not defined in the method " + md);
 932             }
 933             Location globalLoc = new Location(md, globalLocId);
 934
 935             loc.addLocation(globalLoc);
 936           }
 937         } else {
 938           // the location of field access starts from this, followed by field
 939           // location
 940           MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
 941           Location thisLoc = new Location(md, localLattice.getThisLoc());
 942           loc.addLocation(thisLoc);
 943         }
 944
 945         Location fieldLoc = (Location) fd.getType().getExtension();
 946         loc.addLocation(fieldLoc);
 947       }
 948     }
 949     return loc;
 950   }
 951
 952   private CompositeLocation checkLocationFromFieldAccessNode(MethodDescriptor md,
 953       SymbolTable nametable, FieldAccessNode fan, CompositeLocation loc) {
 954
 955     ExpressionNode left = fan.getExpression();
 956     loc = checkLocationFromExpressionNode(md, nametable, left, loc);
 957
 958     if (!left.getType().isPrimitive()) {
 959       FieldDescriptor fd = fan.getField();
 960       Location fieldLoc = (Location) fd.getType().getExtension();
 961       loc.addLocation(fieldLoc);
 962     }
 963
 964     return loc;
 965   }
 966
 967   private CompositeLocation checkLocationFromAssignmentNode(MethodDescriptor md,
 968       SymbolTable nametable, AssignmentNode an, CompositeLocation loc) {
 969
 970     ClassDescriptor cd = md.getClassDesc();
 971
 972     boolean postinc = true;
 973     if (an.getOperation().getBaseOp() == null
 974         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
 975             .getBaseOp().getOp() != Operation.POSTDEC))
 976       postinc = false;
 977
 978     CompositeLocation destLocation =
 979         checkLocationFromExpressionNode(md, nametable, an.getDest(), new CompositeLocation());
 980
 981     CompositeLocation srcLocation = new CompositeLocation();
 982
 983     if (!postinc) {
 984       if (hasOnlyLiteralValue(an.getSrc())) {
 985         // if source is literal value, src location is TOP. so do not need to
 986         // compare!
 987         return destLocation;
 988       }
 989       srcLocation = new CompositeLocation();
 990       srcLocation = checkLocationFromExpressionNode(md, nametable, an.getSrc(), srcLocation);
 991       // System.out.println(" an= " + an.printNode(0) + " an.getSrc()=" +
 992       // an.getSrc().getClass()
 993       // + " at " + cd.getSourceFileName() + "::" + an.getNumLine());
 994       // System.out.println("srcLocation=" + srcLocation);
 995       // System.out.println("dstLocation=" + destLocation);
 996       if (!CompositeLattice.isGreaterThan(srcLocation, destLocation)) {
 997         throw new Error("The value flow from " + srcLocation + " to " + destLocation
 998             + " does not respect location hierarchy on the assignment " + an.printNode(0) + " at "
 999             + cd.getSourceFileName() + "::" + an.getNumLine());
1000       }
1001     } else {
1002       destLocation =
1003           srcLocation = checkLocationFromExpressionNode(md, nametable, an.getDest(), srcLocation);
1004
1005       if (!CompositeLattice.isGreaterThan(srcLocation, destLocation)) {
1006         throw new Error("Location " + destLocation
1007             + " is not allowed to have the value flow that moves within the same location at "
1008             + cd.getSourceFileName() + "::" + an.getNumLine());
1009       }
1010
1011     }
1012
1013     return destLocation;
1014   }
1015
1016   private void assignLocationOfVarDescriptor(VarDescriptor vd, MethodDescriptor md,
1017       SymbolTable nametable, TreeNode n) {
1018
1019     ClassDescriptor cd = md.getClassDesc();
1020     Vector<AnnotationDescriptor> annotationVec = vd.getType().getAnnotationMarkers();
1021
1022     if (!md.getModifiers().isAbstract()) {
1023       // currently enforce every variable to have corresponding location
1024       if (annotationVec.size() == 0) {
1025         throw new Error("Location is not assigned to variable " + vd.getSymbol()
1026             + " in the method " + md.getSymbol() + " of the class " + cd.getSymbol());
1027       }
1028
1029       if (annotationVec.size() > 1) { // variable can have at most one location
1030         throw new Error(vd.getSymbol() + " has more than one location.");
1031       }
1032
1033       AnnotationDescriptor ad = annotationVec.elementAt(0);
1034
1035       if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
1036
1037         if (ad.getMarker().equals(SSJavaAnalysis.LOC)) {
1038           String locDec = ad.getValue(); // check if location is defined
1039
1040           if (locDec.startsWith(SSJavaAnalysis.DELTA)) {
1041             DeltaLocation deltaLoc = parseDeltaDeclaration(md, n, locDec);
1042             d2loc.put(vd, deltaLoc);
1043             addLocationType(vd.getType(), deltaLoc);
1044           } else {
1045             CompositeLocation compLoc = parseLocationDeclaration(md, n, locDec);
1046
1047             Location lastElement = compLoc.get(compLoc.getSize() - 1);
1048             if (ssjava.isSharedLocation(lastElement)) {
1049               ssjava.mapSharedLocation2Descriptor(lastElement, vd);
1050             }
1051
1052             d2loc.put(vd, compLoc);
1053             addLocationType(vd.getType(), compLoc);
1054           }
1055
1056         }
1057       }
1058     }
1059
1060   }
1061
1062   private DeltaLocation parseDeltaDeclaration(MethodDescriptor md, TreeNode n, String locDec) {
1063
1064     int deltaCount = 0;
1065     int dIdx = locDec.indexOf(SSJavaAnalysis.DELTA);
1066     while (dIdx >= 0) {
1067       deltaCount++;
1068       int beginIdx = dIdx + 6;
1069       locDec = locDec.substring(beginIdx, locDec.length() - 1);
1070       dIdx = locDec.indexOf(SSJavaAnalysis.DELTA);
1071     }
1072
1073     CompositeLocation compLoc = parseLocationDeclaration(md, n, locDec);
1074     DeltaLocation deltaLoc = new DeltaLocation(compLoc, deltaCount);
1075
1076     return deltaLoc;
1077   }
1078
1079   private Location parseFieldLocDeclaraton(String decl) {
1080
1081     int idx = decl.indexOf(".");
1082     String className = decl.substring(0, idx);
1083     String fieldName = decl.substring(idx + 1);
1084
1085     Descriptor d = state.getClassSymbolTable().get(className);
1086
1087     assert (d instanceof ClassDescriptor);
1088     SSJavaLattice<String> lattice = ssjava.getClassLattice((ClassDescriptor) d);
1089     if (!lattice.containsKey(fieldName)) {
1090       throw new Error("The location " + fieldName + " is not defined in the field lattice of '"
1091           + className + "'.");
1092     }
1093
1094     return new Location(d, fieldName);
1095   }
1096
1097   private CompositeLocation parseLocationDeclaration(MethodDescriptor md, TreeNode n, String locDec) {
1098
1099     CompositeLocation compLoc = new CompositeLocation();
1100
1101     StringTokenizer tokenizer = new StringTokenizer(locDec, ",");
1102     List<String> locIdList = new ArrayList<String>();
1103     while (tokenizer.hasMoreTokens()) {
1104       String locId = tokenizer.nextToken();
1105       locIdList.add(locId);
1106     }
1107
1108     // at least,one location element needs to be here!
1109     assert (locIdList.size() > 0);
1110
1111     // assume that loc with idx 0 comes from the local lattice
1112     // loc with idx 1 comes from the field lattice
1113
1114     String localLocId = locIdList.get(0);
1115     SSJavaLattice<String> localLattice = CompositeLattice.getLatticeByDescriptor(md);
1116     Location localLoc = new Location(md, localLocId);
1117     if (localLattice == null || (!localLattice.containsKey(localLocId))) {
1118       throw new Error("Location " + localLocId
1119           + " is not defined in the local variable lattice at "
1120           + md.getClassDesc().getSourceFileName() + "::" + (n != null ? n.getNumLine() : "") + ".");
1121     }
1122     compLoc.addLocation(localLoc);
1123
1124     for (int i = 1; i < locIdList.size(); i++) {
1125       String locName = locIdList.get(i);
1126
1127       Location fieldLoc = parseFieldLocDeclaraton(locName);
1128       // ClassDescriptor cd = fieldLocName2cd.get(locName);
1129       // SSJavaLattice<String> fieldLattice =
1130       // CompositeLattice.getLatticeByDescriptor(cd);
1131       //
1132       // if (fieldLattice == null || (!fieldLattice.containsKey(locName))) {
1133       // throw new Error("Location " + locName +
1134       // " is not defined in the field lattice at "
1135       // + cd.getSourceFileName() + ".");
1136       // }
1137       // Location fieldLoc = new Location(cd, locName);
1138       compLoc.addLocation(fieldLoc);
1139     }
1140
1141     return compLoc;
1142
1143   }
1144
1145   private void checkDeclarationNode(MethodDescriptor md, SymbolTable nametable, DeclarationNode dn) {
1146     VarDescriptor vd = dn.getVarDescriptor();
1147     assignLocationOfVarDescriptor(vd, md, nametable, dn);
1148   }
1149
1150   private void checkClass(ClassDescriptor cd) {
1151     // Check to see that methods respects ss property
1152     for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
1153       MethodDescriptor md = (MethodDescriptor) method_it.next();
1154       checkMethodDeclaration(cd, md);
1155     }
1156   }
1157
1158   private void checkDeclarationInClass(ClassDescriptor cd) {
1159     // Check to see that fields are okay
1160     for (Iterator field_it = cd.getFields(); field_it.hasNext();) {
1161       FieldDescriptor fd = (FieldDescriptor) field_it.next();
1162
1163       if (!(fd.isFinal() && fd.isStatic())) {
1164         checkFieldDeclaration(cd, fd);
1165       }
1166     }
1167   }
1168
1169   private void checkMethodDeclaration(ClassDescriptor cd, MethodDescriptor md) {
1170     // TODO
1171   }
1172
1173   private void checkFieldDeclaration(ClassDescriptor cd, FieldDescriptor fd) {
1174
1175     Vector<AnnotationDescriptor> annotationVec = fd.getType().getAnnotationMarkers();
1176
1177     // currently enforce every field to have corresponding location
1178     if (annotationVec.size() == 0) {
1179       throw new Error("Location is not assigned to the field '" + fd.getSymbol()
1180           + "' of the class " + cd.getSymbol() + " at " + cd.getSourceFileName());
1181     }
1182
1183     if (annotationVec.size() > 1) {
1184       // variable can have at most one location
1185       throw new Error("Field " + fd.getSymbol() + " of class " + cd
1186           + " has more than one location.");
1187     }
1188
1189     AnnotationDescriptor ad = annotationVec.elementAt(0);
1190
1191     if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
1192
1193       if (ad.getMarker().equals(SSJavaAnalysis.LOC)) {
1194         String locationID = ad.getValue();
1195         // check if location is defined
1196         SSJavaLattice<String> lattice = ssjava.getClassLattice(cd);
1197         if (lattice == null || (!lattice.containsKey(locationID))) {
1198           throw new Error("Location " + locationID
1199               + " is not defined in the field lattice of class " + cd.getSymbol() + " at"
1200               + cd.getSourceFileName() + ".");
1201         }
1202         Location loc = new Location(cd, locationID);
1203
1204         if (ssjava.isSharedLocation(loc)) {
1205           ssjava.mapSharedLocation2Descriptor(loc, fd);
1206         }
1207
1208         addLocationType(fd.getType(), loc);
1209
1210       }
1211     }
1212
1213   }
1214
1215   private void addLocationType(TypeDescriptor type, CompositeLocation loc) {
1216     if (type != null) {
1217       type.setExtension(loc);
1218     }
1219   }
1220
1221   private void addLocationType(TypeDescriptor type, Location loc) {
1222     if (type != null) {
1223       type.setExtension(loc);
1224     }
1225   }
1226
1227   static class CompositeLattice {
1228
1229     public static boolean isGreaterThan(CompositeLocation loc1, CompositeLocation loc2) {
1230
1231       int baseCompareResult = compareBaseLocationSet(loc1, loc2, true);
1232       if (baseCompareResult == ComparisonResult.EQUAL) {
1233         if (compareDelta(loc1, loc2) == ComparisonResult.GREATER) {
1234           return true;
1235         } else {
1236           return false;
1237         }
1238       } else if (baseCompareResult == ComparisonResult.GREATER) {
1239         return true;
1240       } else {
1241         return false;
1242       }
1243
1244     }
1245
1246     public static int compare(CompositeLocation loc1, CompositeLocation loc2) {
1247
1248       // System.out.println("compare=" + loc1 + " " + loc2);
1249       int baseCompareResult = compareBaseLocationSet(loc1, loc2, false);
1250
1251       if (baseCompareResult == ComparisonResult.EQUAL) {
1252         return compareDelta(loc1, loc2);
1253       } else {
1254         return baseCompareResult;
1255       }
1256
1257     }
1258
1259     private static int compareDelta(CompositeLocation dLoc1, CompositeLocation dLoc2) {
1260
1261       int deltaCount1 = 0;
1262       int deltaCount2 = 0;
1263       if (dLoc1 instanceof DeltaLocation) {
1264         deltaCount1 = ((DeltaLocation) dLoc1).getNumDelta();
1265       }
1266
1267       if (dLoc2 instanceof DeltaLocation) {
1268         deltaCount2 = ((DeltaLocation) dLoc2).getNumDelta();
1269       }
1270       if (deltaCount1 < deltaCount2) {
1271         return ComparisonResult.GREATER;
1272       } else if (deltaCount1 == deltaCount2) {
1273         return ComparisonResult.EQUAL;
1274       } else {
1275         return ComparisonResult.LESS;
1276       }
1277
1278     }
1279
1280     private static int compareBaseLocationSet(CompositeLocation compLoc1,
1281         CompositeLocation compLoc2, boolean awareSharedLoc) {
1282
1283       // if compLoc1 is greater than compLoc2, return true
1284       // else return false;
1285
1286       // compare one by one in according to the order of the tuple
1287       int numOfTie = 0;
1288       for (int i = 0; i < compLoc1.getSize(); i++) {
1289         Location loc1 = compLoc1.get(i);
1290         if (i >= compLoc2.getSize()) {
1291           throw new Error("Failed to compare two locations of " + compLoc1 + " and " + compLoc2
1292               + " because they are not comparable.");
1293         }
1294         Location loc2 = compLoc2.get(i);
1295
1296         if (!loc1.getDescriptor().equals(loc2.getDescriptor())) {
1297           throw new Error("Failed to compare two locations of " + compLoc1 + " and " + compLoc2
1298               + " because they are not comparable.");
1299         }
1300
1301         Descriptor d1 = loc1.getDescriptor();
1302         Descriptor d2 = loc2.getDescriptor();
1303
1304         SSJavaLattice<String> lattice1 = getLatticeByDescriptor(d1);
1305         SSJavaLattice<String> lattice2 = getLatticeByDescriptor(d2);
1306
1307         // check if the spin location is appeared only at the end of the
1308         // composite location
1309         if (lattice1.getSpinLocSet().contains(loc1.getLocIdentifier())) {
1310           if (i != (compLoc1.getSize() - 1)) {
1311             throw new Error("The spin location " + loc1.getLocIdentifier()
1312                 + " cannot be appeared in the middle of composite location.");
1313           }
1314         }
1315
1316         if (lattice2.getSpinLocSet().contains(loc2.getLocIdentifier())) {
1317           if (i != (compLoc2.getSize() - 1)) {
1318             throw new Error("The spin location " + loc2.getLocIdentifier()
1319                 + " cannot be appeared in the middle of composite location.");
1320           }
1321         }
1322
1323         if (!lattice1.equals(lattice2)) {
1324           throw new Error("Failed to compare two locations of " + compLoc1 + " and " + compLoc2
1325               + " because they are not comparable.");
1326         }
1327
1328         if (loc1.getLocIdentifier().equals(loc2.getLocIdentifier())) {
1329           numOfTie++;
1330           // check if the current location is the spinning location
1331           // note that the spinning location only can be appeared in the last
1332           // part of the composite location
1333           if (awareSharedLoc && numOfTie == compLoc1.getSize()
1334               && lattice1.getSpinLocSet().contains(loc1.getLocIdentifier())) {
1335             return ComparisonResult.GREATER;
1336           }
1337           continue;
1338         } else if (lattice1.isGreaterThan(loc1.getLocIdentifier(), loc2.getLocIdentifier())) {
1339           return ComparisonResult.GREATER;
1340         } else {
1341           return ComparisonResult.LESS;
1342         }
1343
1344       }
1345
1346       if (numOfTie == compLoc1.getSize()) {
1347
1348         if (numOfTie != compLoc2.getSize()) {
1349           throw new Error("Failed to compare two locations of " + compLoc1 + " and " + compLoc2
1350               + " because they are not comparable.");
1351         }
1352
1353         return ComparisonResult.EQUAL;
1354       }
1355
1356       return ComparisonResult.LESS;
1357
1358     }
1359
1360     public static CompositeLocation calculateGLB(Set<CompositeLocation> inputSet) {
1361
1362       // System.out.println("Calculating GLB=" + inputSet);
1363       CompositeLocation glbCompLoc = new CompositeLocation();
1364
1365       // calculate GLB of the first(priority) element
1366       Set<String> priorityLocIdentifierSet = new HashSet<String>();
1367       Descriptor priorityDescriptor = null;
1368
1369       Hashtable<String, Set<CompositeLocation>> locId2CompLocSet =
1370           new Hashtable<String, Set<CompositeLocation>>();
1371       // mapping from the priority loc ID to its full representation by the
1372       // composite location
1373
1374       int maxTupleSize = 0;
1375       CompositeLocation maxCompLoc = null;
1376
1377       for (Iterator iterator = inputSet.iterator(); iterator.hasNext();) {
1378         CompositeLocation compLoc = (CompositeLocation) iterator.next();
1379         if (compLoc.getSize() > maxTupleSize) {
1380           maxTupleSize = compLoc.getSize();
1381           maxCompLoc = compLoc;
1382         }
1383         Location priorityLoc = compLoc.get(0);
1384         String priorityLocId = priorityLoc.getLocIdentifier();
1385         priorityLocIdentifierSet.add(priorityLocId);
1386
1387         if (locId2CompLocSet.containsKey(priorityLocId)) {
1388           locId2CompLocSet.get(priorityLocId).add(compLoc);
1389         } else {
1390           Set<CompositeLocation> newSet = new HashSet<CompositeLocation>();
1391           newSet.add(compLoc);
1392           locId2CompLocSet.put(priorityLocId, newSet);
1393         }
1394
1395         // check if priority location are coming from the same lattice
1396         if (priorityDescriptor == null) {
1397           priorityDescriptor = priorityLoc.getDescriptor();
1398         } else if (!priorityDescriptor.equals(priorityLoc.getDescriptor())) {
1399           throw new Error("Failed to calculate GLB of " + inputSet
1400               + " because they are from different lattices.");
1401         }
1402       }
1403
1404       SSJavaLattice<String> locOrder = getLatticeByDescriptor(priorityDescriptor);
1405       String glbOfPriorityLoc = locOrder.getGLB(priorityLocIdentifierSet);
1406
1407       glbCompLoc.addLocation(new Location(priorityDescriptor, glbOfPriorityLoc));
1408       Set<CompositeLocation> compSet = locId2CompLocSet.get(glbOfPriorityLoc);
1409
1410       // here find out composite location that has a maximum length tuple
1411       // if we have three input set: [A], [A,B], [A,B,C]
1412       // maximum length tuple will be [A,B,C]
1413       int max = 0;
1414       CompositeLocation maxFromCompSet = null;
1415       for (Iterator iterator = compSet.iterator(); iterator.hasNext();) {
1416         CompositeLocation c = (CompositeLocation) iterator.next();
1417         if (c.getSize() > max) {
1418           max = c.getSize();
1419           maxFromCompSet = c;
1420         }
1421       }
1422
1423       if (compSet == null) {
1424         // when GLB(x1,x2)!=x1 and !=x2 : GLB case 4
1425         // mean that the result is already lower than <x1,y1> and <x2,y2>
1426         // assign TOP to the rest of the location elements
1427
1428         // in this case, do not take care about delta
1429         // CompositeLocation inputComp = inputSet.iterator().next();
1430         CompositeLocation inputComp = maxCompLoc;
1431         for (int i = 1; i < inputComp.getSize(); i++) {
1432           glbCompLoc.addLocation(Location.createTopLocation(inputComp.get(i).getDescriptor()));
1433         }
1434       } else {
1435         if (compSet.size() == 1) {
1436
1437           // if GLB(x1,x2)==x1 or x2 : GLB case 2,3
1438           CompositeLocation comp = compSet.iterator().next();
1439           for (int i = 1; i < comp.getSize(); i++) {
1440             glbCompLoc.addLocation(comp.get(i));
1441           }
1442
1443           // if input location corresponding to glb is a delta, need to apply
1444           // delta to glb result
1445           if (comp instanceof DeltaLocation) {
1446             glbCompLoc = new DeltaLocation(glbCompLoc, 1);
1447           }
1448
1449         } else {
1450           // when GLB(x1,x2)==x1 and x2 : GLB case 1
1451           // if more than one location shares the same priority GLB
1452           // need to calculate the rest of GLB loc
1453
1454           // int compositeLocSize = compSet.iterator().next().getSize();
1455           int compositeLocSize = maxFromCompSet.getSize();
1456
1457           Set<String> glbInputSet = new HashSet<String>();
1458           Descriptor currentD = null;
1459           for (int i = 1; i < compositeLocSize; i++) {
1460             for (Iterator iterator = compSet.iterator(); iterator.hasNext();) {
1461               CompositeLocation compositeLocation = (CompositeLocation) iterator.next();
1462               if (compositeLocation.getSize() > i) {
1463                 Location currentLoc = compositeLocation.get(i);
1464                 currentD = currentLoc.getDescriptor();
1465                 // making set of the current location sharing the same idx
1466                 glbInputSet.add(currentLoc.getLocIdentifier());
1467               }
1468             }
1469             // calculate glb for the current lattice
1470
1471             SSJavaLattice<String> currentLattice = getLatticeByDescriptor(currentD);
1472             String currentGLBLocId = currentLattice.getGLB(glbInputSet);
1473             glbCompLoc.addLocation(new Location(currentD, currentGLBLocId));
1474           }
1475
1476           // if input location corresponding to glb is a delta, need to apply
1477           // delta to glb result
1478
1479           for (Iterator iterator = compSet.iterator(); iterator.hasNext();) {
1480             CompositeLocation compLoc = (CompositeLocation) iterator.next();
1481             if (compLoc instanceof DeltaLocation) {
1482               if (glbCompLoc.equals(compLoc)) {
1483                 glbCompLoc = new DeltaLocation(glbCompLoc, 1);
1484                 break;
1485               }
1486             }
1487           }
1488
1489         }
1490       }
1491
1492       return glbCompLoc;
1493
1494     }
1495
1496     static SSJavaLattice<String> getLatticeByDescriptor(Descriptor d) {
1497
1498       SSJavaLattice<String> lattice = null;
1499
1500       if (d instanceof ClassDescriptor) {
1501         lattice = ssjava.getCd2lattice().get(d);
1502       } else if (d instanceof MethodDescriptor) {
1503         if (ssjava.getMd2lattice().containsKey(d)) {
1504           lattice = ssjava.getMd2lattice().get(d);
1505         } else {
1506           // use default lattice for the method
1507           lattice = ssjava.getCd2methodDefault().get(((MethodDescriptor) d).getClassDesc());
1508         }
1509       }
1510
1511       return lattice;
1512     }
1513
1514   }
1515
1516   class ComparisonResult {
1517
1518     public static final int GREATER = 0;
1519     public static final int EQUAL = 1;
1520     public static final int LESS = 2;
1521     public static final int INCOMPARABLE = 3;
1522     int result;
1523
1524   }
1525
1526 }
1527
1528 class ReturnLocGenerator {
1529
1530   public static final int PARAMISHIGHER = 0;
1531   public static final int PARAMISSAME = 1;
1532   public static final int IGNORE = 2;
1533
1534   Hashtable<Integer, Integer> paramIdx2paramType;
1535
1536   public ReturnLocGenerator(CompositeLocation returnLoc, List<CompositeLocation> params) {
1537     // creating mappings
1538
1539     paramIdx2paramType = new Hashtable<Integer, Integer>();
1540     for (int i = 0; i < params.size(); i++) {
1541       CompositeLocation param = params.get(i);
1542       int compareResult = CompositeLattice.compare(param, returnLoc);
1543
1544       int type;
1545       if (compareResult == ComparisonResult.GREATER) {
1546         type = 0;
1547       } else if (compareResult == ComparisonResult.EQUAL) {
1548         type = 1;
1549       } else {
1550         type = 2;
1551       }
1552       paramIdx2paramType.put(new Integer(i), new Integer(type));
1553     }
1554
1555   }
1556
1557   public CompositeLocation computeReturnLocation(List<CompositeLocation> args) {
1558
1559     // compute the highest possible location in caller's side
1560     assert paramIdx2paramType.keySet().size() == args.size();
1561
1562     Set<CompositeLocation> inputGLB = new HashSet<CompositeLocation>();
1563     for (int i = 0; i < args.size(); i++) {
1564       int type = (paramIdx2paramType.get(new Integer(i))).intValue();
1565       CompositeLocation argLoc = args.get(i);
1566       if (type == PARAMISHIGHER) {
1567         // return loc is lower than param
1568         DeltaLocation delta = new DeltaLocation(argLoc, 1);
1569         inputGLB.add(delta);
1570       } else if (type == PARAMISSAME) {
1571         // return loc is equal or lower than param
1572         inputGLB.add(argLoc);
1573       }
1574     }
1575
1576     // compute GLB of arguments subset that are same or higher than return
1577     // location
1578     CompositeLocation glb = CompositeLattice.calculateGLB(inputGLB);
1579     return glb;
1580   }
1581 }