Robust/src/Analysis/SSJava/FlowDownCheck.java

   1 package Analysis.SSJava;
   2
   3 import java.util.HashSet;
   4 import java.util.Hashtable;
   5 import java.util.Iterator;
   6 import java.util.Map;
   7 import java.util.Set;
   8 import java.util.StringTokenizer;
   9 import java.util.Vector;
  10
  11 import IR.AnnotationDescriptor;
  12 import IR.ClassDescriptor;
  13 import IR.Descriptor;
  14 import IR.FieldDescriptor;
  15 import IR.MethodDescriptor;
  16 import IR.NameDescriptor;
  17 import IR.Operation;
  18 import IR.State;
  19 import IR.SymbolTable;
  20 import IR.TypeDescriptor;
  21 import IR.VarDescriptor;
  22 import IR.Flat.FlatFieldNode;
  23 import IR.Tree.ArrayAccessNode;
  24 import IR.Tree.ArrayInitializerNode;
  25 import IR.Tree.AssignmentNode;
  26 import IR.Tree.BlockExpressionNode;
  27 import IR.Tree.BlockNode;
  28 import IR.Tree.BlockStatementNode;
  29 import IR.Tree.CastNode;
  30 import IR.Tree.ClassTypeNode;
  31 import IR.Tree.CreateObjectNode;
  32 import IR.Tree.DeclarationNode;
  33 import IR.Tree.ExpressionNode;
  34 import IR.Tree.FieldAccessNode;
  35 import IR.Tree.InstanceOfNode;
  36 import IR.Tree.Kind;
  37 import IR.Tree.LiteralNode;
  38 import IR.Tree.MethodInvokeNode;
  39 import IR.Tree.NameNode;
  40 import IR.Tree.OffsetNode;
  41 import IR.Tree.OpNode;
  42 import IR.Tree.SubBlockNode;
  43 import IR.Tree.TertiaryNode;
  44 import Util.Lattice;
  45
  46 public class FlowDownCheck {
  47
  48   static State state;
  49   HashSet toanalyze;
  50   Hashtable<TypeDescriptor, Location> td2loc; // mapping from 'type descriptor'
  51   // to 'location'
  52   Hashtable<String, ClassDescriptor> id2cd; // mapping from 'locID' to 'class
  53
  54   // descriptor'
  55
  56   public FlowDownCheck(State state) {
  57     this.state = state;
  58     this.toanalyze = new HashSet();
  59     this.td2loc = new Hashtable<TypeDescriptor, Location>();
  60     init();
  61   }
  62
  63   public void init() {
  64     id2cd = new Hashtable<String, ClassDescriptor>();
  65     Hashtable cd2lattice = state.getCd2LocationOrder();
  66
  67     Set cdSet = cd2lattice.keySet();
  68     for (Iterator iterator = cdSet.iterator(); iterator.hasNext();) {
  69       ClassDescriptor cd = (ClassDescriptor) iterator.next();
  70       Lattice<String> lattice = (Lattice<String>) cd2lattice.get(cd);
  71
  72       Set<String> locIdSet = lattice.getKeySet();
  73       for (Iterator iterator2 = locIdSet.iterator(); iterator2.hasNext();) {
  74         String locID = (String) iterator2.next();
  75         id2cd.put(locID, cd);
  76       }
  77     }
  78
  79   }
  80
  81   public void flowDownCheck() {
  82     SymbolTable classtable = state.getClassSymbolTable();
  83
  84     // phase 1 : checking declaration node and creating mapping of 'type
  85     // desciptor' & 'location'
  86     toanalyze.addAll(classtable.getValueSet());
  87     toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
  88     while (!toanalyze.isEmpty()) {
  89       Object obj = toanalyze.iterator().next();
  90       ClassDescriptor cd = (ClassDescriptor) obj;
  91       toanalyze.remove(cd);
  92       if (cd.isClassLibrary()) {
  93         // doesn't care about class libraries now
  94         continue;
  95       }
  96       checkDeclarationInClass(cd);
  97       for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
  98         MethodDescriptor md = (MethodDescriptor) method_it.next();
  99         try {
 100           checkDeclarationInMethodBody(cd, md);
 101         } catch (Error e) {
 102           System.out.println("Error in " + md);
 103           throw e;
 104         }
 105       }
 106     }
 107
 108     // phase2 : checking assignments
 109     toanalyze.addAll(classtable.getValueSet());
 110     toanalyze.addAll(state.getTaskSymbolTable().getValueSet());
 111     while (!toanalyze.isEmpty()) {
 112       Object obj = toanalyze.iterator().next();
 113       ClassDescriptor cd = (ClassDescriptor) obj;
 114       toanalyze.remove(cd);
 115       if (cd.isClassLibrary()) {
 116         // doesn't care about class libraries now
 117         continue;
 118       }
 119       checkClass(cd);
 120       for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
 121         MethodDescriptor md = (MethodDescriptor) method_it.next();
 122         try {
 123           checkMethodBody(cd, md);
 124         } catch (Error e) {
 125           System.out.println("Error in " + md);
 126           throw e;
 127         }
 128       }
 129     }
 130
 131   }
 132
 133   private void checkDeclarationInMethodBody(ClassDescriptor cd, MethodDescriptor md) {
 134     BlockNode bn = state.getMethodBody(md);
 135     checkDeclarationInBlockNode(md, md.getParameterTable(), bn);
 136   }
 137
 138   public void checkDeclarationInBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
 139     bn.getVarTable().setParent(nametable);
 140     for (int i = 0; i < bn.size(); i++) {
 141       BlockStatementNode bsn = bn.get(i);
 142       checkDeclarationInBlockStatementNode(md, bn.getVarTable(), bsn);
 143     }
 144   }
 145
 146   private void checkDeclarationInBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
 147       BlockStatementNode bsn) {
 148
 149     switch (bsn.kind()) {
 150     case Kind.SubBlockNode:
 151       checkDeclarationInSubBlockNode(md, nametable, (SubBlockNode) bsn);
 152       return;
 153     case Kind.DeclarationNode:
 154       checkDeclarationNode(md, (DeclarationNode) bsn);
 155       break;
 156     }
 157   }
 158
 159   public void checkMethodBody(ClassDescriptor cd, MethodDescriptor md) {
 160     BlockNode bn = state.getMethodBody(md);
 161     checkBlockNode(md, md.getParameterTable(), bn);
 162   }
 163
 164   public void checkBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
 165     /* Link in the naming environment */
 166     bn.getVarTable().setParent(nametable);
 167     for (int i = 0; i < bn.size(); i++) {
 168       BlockStatementNode bsn = bn.get(i);
 169       checkBlockStatementNode(md, bn.getVarTable(), bsn);
 170     }
 171   }
 172
 173   public void checkBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
 174       BlockStatementNode bsn) {
 175
 176     switch (bsn.kind()) {
 177     case Kind.BlockExpressionNode:
 178       checkBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
 179       return;
 180
 181     }
 182     /*
 183      * switch (bsn.kind()) { case Kind.BlockExpressionNode:
 184      * checkBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
 185      * return;
 186      *
 187      * case Kind.DeclarationNode: checkDeclarationNode(md, nametable,
 188      * (DeclarationNode) bsn); return;
 189      *
 190      * case Kind.TagDeclarationNode: checkTagDeclarationNode(md, nametable,
 191      * (TagDeclarationNode) bsn); return;
 192      *
 193      * case Kind.IfStatementNode: checkIfStatementNode(md, nametable,
 194      * (IfStatementNode) bsn); return;
 195      *
 196      * case Kind.SwitchStatementNode: checkSwitchStatementNode(md, nametable,
 197      * (SwitchStatementNode) bsn); return;
 198      *
 199      * case Kind.LoopNode: checkLoopNode(md, nametable, (LoopNode) bsn); return;
 200      *
 201      * case Kind.ReturnNode: checkReturnNode(md, nametable, (ReturnNode) bsn);
 202      * return;
 203      *
 204      * case Kind.TaskExitNode: checkTaskExitNode(md, nametable, (TaskExitNode)
 205      * bsn); return;
 206      *
 207      * case Kind.SubBlockNode: checkSubBlockNode(md, nametable, (SubBlockNode)
 208      * bsn); return;
 209      *
 210      * case Kind.AtomicNode: checkAtomicNode(md, nametable, (AtomicNode) bsn);
 211      * return;
 212      *
 213      * case Kind.SynchronizedNode: checkSynchronizedNode(md, nametable,
 214      * (SynchronizedNode) bsn); return;
 215      *
 216      * case Kind.ContinueBreakNode: checkContinueBreakNode(md, nametable,
 217      * (ContinueBreakNode) bsn); return;
 218      *
 219      * case Kind.SESENode: case Kind.GenReachNode: // do nothing, no semantic
 220      * check for SESEs return; }
 221      */
 222     // throw new Error();
 223   }
 224
 225   private void checkDeclarationInSubBlockNode(MethodDescriptor md, SymbolTable nametable,
 226       SubBlockNode sbn) {
 227     checkDeclarationInBlockNode(md, nametable, sbn.getBlockNode());
 228   }
 229
 230   void checkBlockExpressionNode(MethodDescriptor md, SymbolTable nametable, BlockExpressionNode ben) {
 231     checkExpressionNode(md, nametable, ben.getExpression(), null);
 232   }
 233
 234   void checkExpressionNode(MethodDescriptor md, SymbolTable nametable, ExpressionNode en,
 235       TypeDescriptor td) {
 236
 237     switch (en.kind()) {
 238     case Kind.AssignmentNode:
 239       checkAssignmentNode(md, nametable, (AssignmentNode) en, td);
 240       return;
 241
 242     case Kind.OpNode:
 243       checkOpNode(md, nametable, (OpNode) en, td);
 244       return;
 245
 246     case Kind.FieldAccessNode:
 247       checkFieldAccessNode(md, nametable, (FieldAccessNode) en, td);
 248       return;
 249
 250     case Kind.NameNode:
 251       checkNameNode(md, nametable, (NameNode) en, td);
 252       return;
 253
 254     }
 255
 256     /*
 257      * switch(en.kind()) { case Kind.AssignmentNode:
 258      * checkAssignmentNode(md,nametable,(AssignmentNode)en,td); return;
 259      *
 260      * case Kind.CastNode: checkCastNode(md,nametable,(CastNode)en,td); return;
 261      *
 262      * case Kind.CreateObjectNode:
 263      * checkCreateObjectNode(md,nametable,(CreateObjectNode)en,td); return;
 264      *
 265      * case Kind.FieldAccessNode:
 266      * checkFieldAccessNode(md,nametable,(FieldAccessNode)en,td); return;
 267      *
 268      * case Kind.ArrayAccessNode:
 269      * checkArrayAccessNode(md,nametable,(ArrayAccessNode)en,td); return;
 270      *
 271      * case Kind.LiteralNode: checkLiteralNode(md,nametable,(LiteralNode)en,td);
 272      * return;
 273      *
 274      * case Kind.MethodInvokeNode:
 275      * checkMethodInvokeNode(md,nametable,(MethodInvokeNode)en,td); return;
 276      *
 277      * case Kind.NameNode: checkNameNode(md,nametable,(NameNode)en,td); return;
 278      *
 279      * case Kind.OpNode: checkOpNode(md,nametable,(OpNode)en,td); return;
 280      *
 281      * case Kind.OffsetNode: checkOffsetNode(md, nametable, (OffsetNode)en, td);
 282      * return;
 283      *
 284      * case Kind.TertiaryNode: checkTertiaryNode(md, nametable,
 285      * (TertiaryNode)en, td); return;
 286      *
 287      * case Kind.InstanceOfNode: checkInstanceOfNode(md, nametable,
 288      * (InstanceOfNode) en, td); return;
 289      *
 290      * case Kind.ArrayInitializerNode: checkArrayInitializerNode(md, nametable,
 291      * (ArrayInitializerNode) en, td); return;
 292      *
 293      * case Kind.ClassTypeNode: checkClassTypeNode(md, nametable,
 294      * (ClassTypeNode) en, td); return; }
 295      */
 296   }
 297
 298   void checkNameNode(MethodDescriptor md, SymbolTable nametable, NameNode nn, TypeDescriptor td) {
 299
 300     NameDescriptor nd = nn.getName();
 301     System.out.println("checkNameNode=" + nn);
 302     System.out.println("nn.expression=" + nn.getExpression().printNode(0));
 303
 304     if (nd.getBase() != null) {
 305       /* Big hack */
 306       /* Rewrite NameNode */
 307       ExpressionNode en = translateNameDescriptorintoExpression(nd);
 308       System.out.println("base=" + nd.getBase() + " field=" + nn.getField() + " en="
 309           + en.printNode(0));
 310       nn.setExpression(en);
 311       System.out.println("checking expression node=" + en.printNode(0) + " with td=" + td);
 312       checkExpressionNode(md, nametable, en, td);
 313     } else {
 314       System.out.println("base=" + nd.getBase() + " field=" + nn.getField());
 315
 316     }
 317
 318     // ExpressionNode en=nn.getExpression();
 319     // if(en instanceof FieldAccessNode){
 320     // FieldAccessNode fan=(FieldAccessNode)en;
 321     // System.out.println("base="+nd.getBase()+" field="+fan.getFieldName());
 322     // }
 323
 324     // checkExpressionNode(md, nametable, nn.getExpression(), td);
 325     // NameDescriptor nd = nn.getName();
 326     // if (nd.getBase() != null) {
 327     // System.out.println("nd.getBase()="+nd.getBase());
 328     // /* Big hack */
 329     // /* Rewrite NameNode */
 330     // ExpressionNode en = translateNameDescriptorintoExpression(nd);
 331     // System.out.println("expressionsNode="+en);
 332     // nn.setExpression(en);
 333     // checkExpressionNode(md, nametable, en, td);
 334     // }
 335
 336   }
 337
 338   ExpressionNode translateNameDescriptorintoExpression(NameDescriptor nd) {
 339     String id = nd.getIdentifier();
 340     NameDescriptor base = nd.getBase();
 341     if (base == null) {
 342       NameNode nn = new NameNode(nd);
 343       return nn;
 344     } else {
 345       FieldAccessNode fan = new FieldAccessNode(translateNameDescriptorintoExpression(base), id);
 346       return fan;
 347     }
 348   }
 349
 350   void checkFieldAccessNode(MethodDescriptor md, SymbolTable nametable, FieldAccessNode fan,
 351       TypeDescriptor td) {
 352
 353     System.out.println("fan=" + fan + " field=" + fan.getFieldName());
 354     ExpressionNode left = fan.getExpression();
 355     System.out.println("checking expression from fan=" + left.printNode(0) + " with td=" + td);
 356     checkExpressionNode(md, nametable, left, null);
 357     TypeDescriptor ltd = left.getType();
 358     String fieldname = fan.getFieldName();
 359
 360   }
 361
 362   void checkOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on, TypeDescriptor td) {
 363
 364     Lattice<String> locOrder = (Lattice<String>) state.getCd2LocationOrder().get(md.getClassDesc());
 365
 366     CompositeLocation leftOpLoc = new CompositeLocation(md.getClassDesc());
 367     getLocationFromExpressionNode(md, nametable, on.getLeft(), leftOpLoc);
 368
 369     CompositeLocation rightOpLoc = new CompositeLocation(md.getClassDesc());
 370     if (on.getRight() != null) {
 371       getLocationFromExpressionNode(md, nametable, on.getRight(), rightOpLoc);
 372     }
 373
 374     TypeDescriptor ltd = on.getLeft().getType();
 375     TypeDescriptor rtd = on.getRight() != null ? on.getRight().getType() : null;
 376
 377     Operation op = on.getOp();
 378
 379     switch (op.getOp()) {
 380
 381     case Operation.UNARYPLUS:
 382     case Operation.UNARYMINUS:
 383     case Operation.LOGIC_NOT:
 384       // single operand
 385       on.setType(new TypeDescriptor(TypeDescriptor.BOOLEAN));
 386       break;
 387
 388     case Operation.LOGIC_OR:
 389     case Operation.LOGIC_AND:
 390     case Operation.COMP:
 391     case Operation.BIT_OR:
 392     case Operation.BIT_XOR:
 393     case Operation.BIT_AND:
 394     case Operation.ISAVAILABLE:
 395     case Operation.EQUAL:
 396     case Operation.NOTEQUAL:
 397     case Operation.LT:
 398     case Operation.GT:
 399     case Operation.LTE:
 400     case Operation.GTE:
 401     case Operation.ADD:
 402     case Operation.SUB:
 403     case Operation.MULT:
 404     case Operation.DIV:
 405     case Operation.MOD:
 406     case Operation.LEFTSHIFT:
 407     case Operation.RIGHTSHIFT:
 408     case Operation.URIGHTSHIFT:
 409
 410       Set<String> operandSet = new HashSet<String>();
 411       String leftLoc = ltd.getAnnotationMarkers().get(0).getMarker();
 412       String rightLoc = rtd.getAnnotationMarkers().get(0).getMarker();
 413
 414       operandSet.add(leftLoc);
 415       operandSet.add(rightLoc);
 416
 417       // TODO
 418       // String glbLoc = locOrder.getGLB(operandSet);
 419       // on.getType().addAnnotationMarker(new AnnotationDescriptor(glbLoc));
 420       // System.out.println(glbLoc + "<-" + leftLoc + " " + rightLoc);
 421
 422       break;
 423
 424     default:
 425       throw new Error(op.toString());
 426     }
 427
 428     if (td != null) {
 429       String lhsLoc = td.getAnnotationMarkers().get(0).getMarker();
 430       if (locOrder.isGreaterThan(lhsLoc, on.getType().getAnnotationMarkers().get(0).getMarker())) {
 431         throw new Error("The location of LHS is higher than RHS: " + on.printNode(0));
 432       }
 433     }
 434
 435   }
 436
 437   protected void getLocationFromExpressionNode(MethodDescriptor md, SymbolTable nametable,
 438       ExpressionNode en, CompositeLocation loc) {
 439
 440     switch (en.kind()) {
 441
 442     case Kind.AssignmentNode:
 443       getLocationFromAssignmentNode(md, nametable, (AssignmentNode) en, loc);
 444       return;
 445
 446     case Kind.FieldAccessNode:
 447       getLocationFromFieldAccessNode(md, nametable, (FieldAccessNode) en, loc);
 448       return;
 449
 450     case Kind.NameNode:
 451       getLocationFromNameNode(md, nametable, (NameNode) en, loc);
 452       return;
 453
 454     case Kind.OpNode:
 455       getLocationFromOpNode(md, nametable, (OpNode) en, loc);
 456       // checkOpNode(md,nametable,(OpNode)en,td);
 457       return;
 458
 459     case Kind.CastNode:
 460       // checkCastNode(md,nametable,(CastNode)en,td);
 461       return;
 462
 463     case Kind.CreateObjectNode:
 464       // checkCreateObjectNode(md, nametable, (CreateObjectNode) en, td);
 465       return;
 466
 467     case Kind.ArrayAccessNode:
 468       // checkArrayAccessNode(md, nametable, (ArrayAccessNode) en, td);
 469       return;
 470
 471     case Kind.LiteralNode:
 472       getLocationFromLiteralNode(md, nametable, (LiteralNode) en, loc);
 473       return;
 474
 475     case Kind.MethodInvokeNode:
 476       // checkMethodInvokeNode(md,nametable,(MethodInvokeNode)en,td);
 477       return;
 478
 479     case Kind.OffsetNode:
 480       // checkOffsetNode(md, nametable, (OffsetNode)en, td);
 481       return;
 482
 483     case Kind.TertiaryNode:
 484       // checkTertiaryNode(md, nametable, (TertiaryNode)en, td);
 485       return;
 486
 487     case Kind.InstanceOfNode:
 488       // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
 489       return;
 490
 491     case Kind.ArrayInitializerNode:
 492       // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
 493       // td);
 494       return;
 495
 496     case Kind.ClassTypeNode:
 497       // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
 498       return;
 499
 500     }
 501
 502   }
 503
 504   private void getLocationFromOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
 505       CompositeLocation loc) {
 506
 507     Lattice<String> locOrder = (Lattice<String>) state.getCd2LocationOrder().get(md.getClassDesc());
 508
 509     ClassDescriptor cd = md.getClassDesc();
 510     CompositeLocation leftLoc = new CompositeLocation(cd);
 511     getLocationFromExpressionNode(md, nametable, on.getLeft(), leftLoc);
 512
 513     CompositeLocation rightLoc = new CompositeLocation(cd);
 514     if (on.getRight() != null) {
 515       getLocationFromExpressionNode(md, nametable, on.getRight(), rightLoc);
 516     }
 517
 518     System.out.println("checking op node");
 519     System.out.println("left loc=" + leftLoc);
 520     System.out.println("right loc=" + rightLoc);
 521
 522     Operation op = on.getOp();
 523
 524     switch (op.getOp()) {
 525
 526     case Operation.UNARYPLUS:
 527     case Operation.UNARYMINUS:
 528     case Operation.LOGIC_NOT:
 529       // single operand
 530       on.setType(new TypeDescriptor(TypeDescriptor.BOOLEAN));
 531       break;
 532
 533     case Operation.LOGIC_OR:
 534     case Operation.LOGIC_AND:
 535     case Operation.COMP:
 536     case Operation.BIT_OR:
 537     case Operation.BIT_XOR:
 538     case Operation.BIT_AND:
 539     case Operation.ISAVAILABLE:
 540     case Operation.EQUAL:
 541     case Operation.NOTEQUAL:
 542     case Operation.LT:
 543     case Operation.GT:
 544     case Operation.LTE:
 545     case Operation.GTE:
 546     case Operation.ADD:
 547     case Operation.SUB:
 548     case Operation.MULT:
 549     case Operation.DIV:
 550     case Operation.MOD:
 551     case Operation.LEFTSHIFT:
 552     case Operation.RIGHTSHIFT:
 553     case Operation.URIGHTSHIFT:
 554
 555       Set<CompositeLocation> inputSet = new HashSet<CompositeLocation>();
 556       inputSet.add(leftLoc);
 557       inputSet.add(rightLoc);
 558       CompositeLattice.calculateGLB(inputSet, cd, loc);
 559
 560       break;
 561
 562     default:
 563       throw new Error(op.toString());
 564     }
 565
 566   }
 567
 568   private void getLocationFromLiteralNode(MethodDescriptor md, SymbolTable nametable,
 569       LiteralNode en, CompositeLocation loc) {
 570
 571     // literal value has the top location so that value can be flowed into any
 572     // location
 573     Location literalLoc = Location.createTopLocation(md.getClassDesc());
 574     loc.addLocation(literalLoc);
 575
 576   }
 577
 578   private void getLocationFromNameNode(MethodDescriptor md, SymbolTable nametable, NameNode nn,
 579       CompositeLocation loc) {
 580
 581     NameDescriptor nd = nn.getName();
 582     if (nd.getBase() != null) {
 583       getLocationFromExpressionNode(md, nametable, nn.getExpression(), loc);
 584     } else {
 585
 586       String varname = nd.toString();
 587       Descriptor d = (Descriptor) nametable.get(varname);
 588
 589       Location localLoc = null;
 590       if (d instanceof VarDescriptor) {
 591         VarDescriptor vd = (VarDescriptor) d;
 592         localLoc = td2loc.get(vd.getType());
 593       } else if (d instanceof FieldDescriptor) {
 594         FieldDescriptor fd = (FieldDescriptor) d;
 595         localLoc = td2loc.get(fd.getType());
 596       }
 597       assert (localLoc != null);
 598       loc.addLocation(localLoc);
 599     }
 600
 601   }
 602
 603   private void getLocationFromFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
 604       FieldAccessNode fan, CompositeLocation loc) {
 605     FieldDescriptor fd = fan.getField();
 606     Location fieldLoc = td2loc.get(fd.getType());
 607     loc.addLocation(fieldLoc);
 608
 609     ExpressionNode left = fan.getExpression();
 610     getLocationFromExpressionNode(md, nametable, left, loc);
 611   }
 612
 613   private CompositeLocation getLocationFromAssignmentNode(Descriptor md, SymbolTable nametable,
 614       AssignmentNode en, CompositeLocation loc) {
 615     // TODO Auto-generated method stub
 616
 617     return null;
 618   }
 619
 620   private Location createCompositeLocation(FieldAccessNode fan, Location loc) {
 621
 622     FieldDescriptor field = fan.getField();
 623     ClassDescriptor fieldCD = field.getClassDescriptor();
 624
 625     assert (field.getType().getAnnotationMarkers().size() == 1);
 626
 627     AnnotationDescriptor locAnnotation = field.getType().getAnnotationMarkers().elementAt(0);
 628     if (locAnnotation.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
 629       // single location
 630
 631     } else {
 632       // delta location
 633     }
 634
 635     // Location localLoc=new Location(field.getClassDescriptor(),field.get)
 636
 637     // System.out.println("creatingComposite's field="+field+" localLoc="+localLoc);
 638     ExpressionNode leftNode = fan.getExpression();
 639     System.out.println("creatingComposite's leftnode=" + leftNode.printNode(0));
 640
 641     return loc;
 642   }
 643
 644   void checkAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an,
 645       TypeDescriptor td) {
 646
 647     CompositeLocation srcLocation = new CompositeLocation(md.getClassDesc());
 648
 649     boolean postinc = true;
 650     if (an.getOperation().getBaseOp() == null
 651         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
 652             .getBaseOp().getOp() != Operation.POSTDEC))
 653       postinc = false;
 654     if (!postinc) {
 655       // checkExpressionNode(md, nametable, an.getSrc(), td);
 656       // calculateLocation(md, nametable, an.getSrc(), td);
 657       getLocationFromExpressionNode(md, nametable, an.getSrc(), srcLocation);
 658     }
 659
 660     ClassDescriptor cd = md.getClassDesc();
 661
 662     Location destLocation = td2loc.get(an.getDest().getType());
 663
 664     if (!CompositeLattice.isGreaterThan(srcLocation, destLocation)) {
 665       throw new Error("The value flow from " + srcLocation + " to " + destLocation
 666           + " does not respect location hierarchy on the assignment " + an.printNode(0));
 667     }
 668
 669   }
 670
 671   void checkDeclarationNode(MethodDescriptor md, DeclarationNode dn) {
 672     ClassDescriptor cd = md.getClassDesc();
 673     VarDescriptor vd = dn.getVarDescriptor();
 674     Vector<AnnotationDescriptor> annotationVec = vd.getType().getAnnotationMarkers();
 675
 676     // currently enforce every variable to have corresponding location
 677     if (annotationVec.size() == 0) {
 678       throw new Error("Location is not assigned to variable " + vd.getSymbol() + " in the method "
 679           + md.getSymbol() + " of the class " + cd.getSymbol());
 680     }
 681
 682     if (annotationVec.size() > 1) {
 683       // variable can have at most one location
 684       throw new Error(vd.getSymbol() + " has more than one location.");
 685     }
 686
 687     AnnotationDescriptor ad = annotationVec.elementAt(0);
 688
 689     if (ad.getType() == AnnotationDescriptor.MARKER_ANNOTATION) {
 690
 691       // check if location is defined
 692       String locationID = ad.getMarker();
 693       Lattice<String> lattice = (Lattice<String>) state.getCd2LocationOrder().get(cd);
 694
 695       if (lattice == null || (!lattice.containsKey(locationID))) {
 696         throw new Error("Location " + locationID
 697             + " is not defined in the location hierarchy of class " + cd.getSymbol() + ".");
 698       }
 699
 700       Location loc = new Location(cd, locationID);
 701       td2loc.put(vd.getType(), loc);
 702
 703     } else if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
 704       if (ad.getMarker().equals(SSJavaAnalysis.DELTA)) {
 705
 706         if (ad.getData().length() == 0) {
 707           throw new Error("Delta function of " + vd.getSymbol() + " does not have any locations: "
 708               + cd.getSymbol() + ".");
 709         }
 710
 711         StringTokenizer token = new StringTokenizer(ad.getData(), ",");
 712
 713         CompositeLocation compLoc = new CompositeLocation(cd);
 714         DeltaLocation deltaLoc = new DeltaLocation(cd);
 715
 716         while (token.hasMoreTokens()) {
 717           String deltaOperand = token.nextToken();
 718           ClassDescriptor deltaCD = id2cd.get(deltaOperand);
 719           if (deltaCD == null) {
 720             // delta operand is not defined in the location hierarchy
 721             throw new Error("Delta operand '" + deltaOperand + "' of declaration node '" + vd
 722                 + "' is not defined by location hierarchies.");
 723           }
 724
 725           Location loc = new Location(deltaCD, deltaOperand);
 726           deltaLoc.addDeltaOperand(loc);
 727         }
 728         compLoc.addLocation(deltaLoc);
 729         td2loc.put(vd.getType(), compLoc);
 730       }
 731     }
 732
 733   }
 734
 735   private void checkClass(ClassDescriptor cd) {
 736     // Check to see that methods respects ss property
 737     for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
 738       MethodDescriptor md = (MethodDescriptor) method_it.next();
 739       checkMethodDeclaration(cd, md);
 740     }
 741   }
 742
 743   private void checkDeclarationInClass(ClassDescriptor cd) {
 744     // Check to see that fields are okay
 745     for (Iterator field_it = cd.getFields(); field_it.hasNext();) {
 746       FieldDescriptor fd = (FieldDescriptor) field_it.next();
 747       checkFieldDeclaration(cd, fd);
 748     }
 749   }
 750
 751   private void checkMethodDeclaration(ClassDescriptor cd, MethodDescriptor md) {
 752
 753   }
 754
 755   private void checkFieldDeclaration(ClassDescriptor cd, FieldDescriptor fd) {
 756
 757     Vector<AnnotationDescriptor> annotationVec = fd.getType().getAnnotationMarkers();
 758
 759     // currently enforce every variable to have corresponding location
 760     if (annotationVec.size() == 0) {
 761       throw new Error("Location is not assigned to the field " + fd.getSymbol() + " of the class "
 762           + cd.getSymbol());
 763     }
 764
 765     if (annotationVec.size() > 1) {
 766       // variable can have at most one location
 767       throw new Error("Field " + fd.getSymbol() + " of class " + cd
 768           + " has more than one location.");
 769     }
 770
 771     // check if location is defined
 772     AnnotationDescriptor ad = annotationVec.elementAt(0);
 773     if (ad.getType() == AnnotationDescriptor.MARKER_ANNOTATION) {
 774       String locationID = annotationVec.elementAt(0).getMarker();
 775       Lattice<String> lattice = (Lattice<String>) state.getCd2LocationOrder().get(cd);
 776
 777       if (lattice == null || (!lattice.containsKey(locationID))) {
 778         throw new Error("Location " + locationID
 779             + " is not defined in the location hierarchy of class " + cd.getSymbol() + ".");
 780       }
 781
 782       Location localLoc = new Location(cd, locationID);
 783       td2loc.put(fd.getType(), localLoc);
 784
 785     } else if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
 786       if (ad.getMarker().equals(SSJavaAnalysis.DELTA)) {
 787
 788         if (ad.getData().length() == 0) {
 789           throw new Error("Delta function of " + fd.getSymbol() + " does not have any locations: "
 790               + cd.getSymbol() + ".");
 791         }
 792
 793         CompositeLocation compLoc = new CompositeLocation(cd);
 794         DeltaLocation deltaLoc = new DeltaLocation(cd);
 795
 796         StringTokenizer token = new StringTokenizer(ad.getData(), ",");
 797         while (token.hasMoreTokens()) {
 798           String deltaOperand = token.nextToken();
 799           ClassDescriptor deltaCD = id2cd.get(deltaOperand);
 800           if (deltaCD == null) {
 801             // delta operand is not defined in the location hierarchy
 802             throw new Error("Delta operand '" + deltaOperand + "' of field node '" + fd
 803                 + "' is not defined by location hierarchies.");
 804           }
 805
 806           Location loc = new Location(deltaCD, deltaOperand);
 807           deltaLoc.addDeltaOperand(loc);
 808         }
 809         compLoc.addLocation(deltaLoc);
 810         td2loc.put(fd.getType(), compLoc);
 811
 812       }
 813     }
 814
 815   }
 816
 817   static class CompositeLattice {
 818
 819     public static boolean isGreaterThan(Location loc1, Location loc2) {
 820
 821       CompositeLocation compLoc1;
 822       CompositeLocation compLoc2;
 823
 824       if (loc1 instanceof CompositeLocation) {
 825         compLoc1 = (CompositeLocation) loc1;
 826       } else {
 827         // create a bogus composite location for a single location
 828         compLoc1 = new CompositeLocation(loc1.getClassDescriptor());
 829         compLoc1.addLocation(loc1);
 830       }
 831
 832       if (loc2 instanceof CompositeLocation) {
 833         compLoc2 = (CompositeLocation) loc2;
 834       } else {
 835         // create a bogus composite location for a single location
 836         compLoc2 = new CompositeLocation(loc2.getClassDescriptor());
 837         compLoc2.addLocation(loc2);
 838       }
 839
 840       // comparing two composite locations
 841       System.out.println("compare base location=" + compLoc1 + " ? " + compLoc2);
 842
 843       int baseCompareResult = compareBaseLocationSet(compLoc1, compLoc2);
 844       if (baseCompareResult == ComparisonResult.EQUAL) {
 845         if (compareDelta(compLoc1, compLoc2) == ComparisonResult.GREATER) {
 846           return true;
 847         } else {
 848           return false;
 849         }
 850       } else if (baseCompareResult == ComparisonResult.GREATER) {
 851         return true;
 852       } else {
 853         return false;
 854       }
 855
 856     }
 857
 858     private static int compareDelta(CompositeLocation compLoc1, CompositeLocation compLoc2) {
 859
 860       if (compLoc1.getNumofDelta() < compLoc2.getNumofDelta()) {
 861         return ComparisonResult.GREATER;
 862       } else {
 863         return ComparisonResult.LESS;
 864       }
 865     }
 866
 867     private static int compareBaseLocationSet(CompositeLocation compLoc1, CompositeLocation compLoc2) {
 868
 869       // if compLoc1 is greater than compLoc2, return true
 870       // else return false;
 871
 872       Map<ClassDescriptor, Location> cd2loc1 = compLoc1.getCd2Loc();
 873       Map<ClassDescriptor, Location> cd2loc2 = compLoc2.getCd2Loc();
 874
 875       // compare base locations by class descriptor
 876
 877       Set<ClassDescriptor> keySet1 = cd2loc1.keySet();
 878
 879       int numEqualLoc = 0;
 880
 881       for (Iterator iterator = keySet1.iterator(); iterator.hasNext();) {
 882         ClassDescriptor cd1 = (ClassDescriptor) iterator.next();
 883
 884         Location loc1 = cd2loc1.get(cd1);
 885         Location loc2 = cd2loc2.get(cd1);
 886
 887         if (loc2 == null) {
 888           // if comploc2 doesn't have corresponding location, then ignore this
 889           // element
 890           numEqualLoc++;
 891           continue;
 892         }
 893
 894         Lattice<String> locationOrder = (Lattice<String>) state.getCd2LocationOrder().get(cd1);
 895         if (loc1.getLocIdentifier().equals(loc2.getLocIdentifier())) {
 896           // have the same level of local hierarchy
 897           numEqualLoc++;
 898         } else if (!locationOrder.isGreaterThan(loc1.getLocIdentifier(), loc2.getLocIdentifier())) {
 899           // if one element of composite location 1 is not higher than composite
 900           // location 2
 901           // then, composite loc 1 is not higher than composite loc 2
 902
 903           System.out.println(compLoc1 + " < " + compLoc2);
 904           return ComparisonResult.LESS;
 905         }
 906
 907       }
 908
 909       if (numEqualLoc == compLoc1.getTupleSize()) {
 910         System.out.println(compLoc1 + " == " + compLoc2);
 911         return ComparisonResult.EQUAL;
 912       }
 913
 914       System.out.println(compLoc1 + " > " + compLoc2);
 915       return ComparisonResult.GREATER;
 916     }
 917
 918     public static CompositeLocation calculateGLB(Set<CompositeLocation> inputSet,
 919         ClassDescriptor enclosingCD, CompositeLocation loc) {
 920
 921       Hashtable<ClassDescriptor, Set<Location>> cd2locSet =
 922           new Hashtable<ClassDescriptor, Set<Location>>();
 923
 924       // creating mapping from class -> set of locations
 925       for (Iterator iterator = inputSet.iterator(); iterator.hasNext();) {
 926         CompositeLocation compLoc = (CompositeLocation) iterator.next();
 927         Set<Location> baseLocationSet = compLoc.getBaseLocationSet();
 928         for (Iterator iterator2 = baseLocationSet.iterator(); iterator2.hasNext();) {
 929           Location locElement = (Location) iterator2.next();
 930           ClassDescriptor locCD = locElement.getClassDescriptor();
 931
 932           Set<Location> locSet = cd2locSet.get(locCD);
 933           if (locSet == null) {
 934             locSet = new HashSet<Location>();
 935           }
 936           locSet.add(locElement);
 937
 938           cd2locSet.put(locCD, locSet);
 939
 940         }
 941       }
 942
 943       // calculating GLB element for each class
 944       for (Iterator<ClassDescriptor> iterator = cd2locSet.keySet().iterator(); iterator.hasNext();) {
 945         ClassDescriptor localCD = iterator.next();
 946
 947         Set<Location> locSetofClass = cd2locSet.get(localCD);
 948
 949         Set<String> locIdentifierSet = new HashSet<String>();
 950
 951         for (Iterator<Location> locIterator = locSetofClass.iterator(); locIterator.hasNext();) {
 952           Location locElement = locIterator.next();
 953           locIdentifierSet.add(locElement.getLocIdentifier());
 954         }
 955
 956         Lattice<String> locOrder = (Lattice<String>) state.getCd2LocationOrder().get(localCD);
 957         String glbLocIdentifer = locOrder.getGLB(locIdentifierSet);
 958
 959         Location localGLB = new Location(localCD, glbLocIdentifer);
 960         loc.addLocation(localGLB);
 961       }
 962
 963       return loc;
 964     }
 965
 966   }
 967
 968   class ComparisonResult {
 969
 970     public static final int GREATER = 0;
 971     public static final int EQUAL = 1;
 972     public static final int LESS = 2;
 973     int result;
 974
 975   }
 976
 977 }