Robust/src/Analysis/SSJava/HierarchyGraph.java

   1 package Analysis.SSJava;
   2
   3 import java.io.BufferedWriter;
   4 import java.io.FileWriter;
   5 import java.io.IOException;
   6 import java.util.HashMap;
   7 import java.util.HashSet;
   8 import java.util.Iterator;
   9 import java.util.Map;
  10 import java.util.Set;
  11
  12 import IR.Descriptor;
  13 import IR.FieldDescriptor;
  14 import IR.VarDescriptor;
  15
  16 public class HierarchyGraph {
  17
  18   Descriptor desc;
  19
  20   String name;
  21
  22   // graph structure
  23   Map<HNode, Set<HNode>> mapHNodeToIncomingSet;
  24   Map<HNode, Set<HNode>> mapHNodeToOutgoingSet;
  25
  26   Map<Descriptor, HNode> mapDescToHNode;
  27   Map<HNode, Set<Descriptor>> mapHNodeToDescSet;
  28   Map<HNode, HNode> mapHNodeToCurrentHNode; // tracking which node corresponds to the initial node
  29   Map<String, HNode> mapHNodeNameToCurrentHNode; // tracking which node corresponds to the initial
  30                                                  // node
  31   Map<HNode, Set<HNode>> mapMergeNodetoMergingSet;
  32
  33   // data structures for a combination node
  34   Map<Set<HNode>, HNode> mapSkeletonNodeSetToCombinationNode;
  35   Map<HNode, Set<HNode>> mapCombinationNodeToCombineNodeSet;
  36   Map<Set<HNode>, HNode> mapCombineNodeSetToCombinationNode;
  37   Map<Set<HNode>, Set<HNode>> mapCombineNodeSetToOutgoingNodeSet;
  38
  39   Set<HNode> nodeSet;
  40
  41   // for the lattice generation
  42   Map<HNode, Integer> mapHNodeToUniqueIndex;
  43   Map<HNode, Set<Integer>> mapHNodeToBasis;
  44   Set<Integer> BASISTOPELEMENT;
  45
  46   public HierarchyGraph() {
  47     mapHNodeToIncomingSet = new HashMap<HNode, Set<HNode>>();
  48     mapHNodeToOutgoingSet = new HashMap<HNode, Set<HNode>>();
  49     mapHNodeToDescSet = new HashMap<HNode, Set<Descriptor>>();
  50     mapDescToHNode = new HashMap<Descriptor, HNode>();
  51     mapSkeletonNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
  52     mapCombinationNodeToCombineNodeSet = new HashMap<HNode, Set<HNode>>();
  53     mapCombineNodeSetToOutgoingNodeSet = new HashMap<Set<HNode>, Set<HNode>>();
  54     mapCombineNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
  55     nodeSet = new HashSet<HNode>();
  56
  57     mapHNodeToUniqueIndex = new HashMap<HNode, Integer>();
  58     mapHNodeToBasis = new HashMap<HNode, Set<Integer>>();
  59
  60     mapMergeNodetoMergingSet = new HashMap<HNode, Set<HNode>>();
  61
  62     mapHNodeToCurrentHNode = new HashMap<HNode, HNode>();
  63
  64     mapHNodeNameToCurrentHNode = new HashMap<String, HNode>();
  65
  66   }
  67
  68   public Descriptor getDesc() {
  69     return desc;
  70   }
  71
  72   public void setDesc(Descriptor desc) {
  73     this.desc = desc;
  74   }
  75
  76   public String getName() {
  77     return name;
  78   }
  79
  80   public void setName(String name) {
  81     this.name = name;
  82   }
  83
  84   public HierarchyGraph(Descriptor d) {
  85     this();
  86     desc = d;
  87     name = d.toString();
  88   }
  89
  90   public Map<HNode, Set<Descriptor>> getMapHNodeToDescSet() {
  91     return mapHNodeToDescSet;
  92   }
  93
  94   public void setMapHNodeToDescSet(Map<HNode, Set<Descriptor>> map) {
  95     mapHNodeToDescSet.putAll(map);
  96   }
  97
  98   public Map<HNode, HNode> getMapHNodeToCurrentHNode() {
  99     return mapHNodeToCurrentHNode;
 100   }
 101
 102   public Map<String, HNode> getMapHNodeNameToCurrentHNode() {
 103     return mapHNodeNameToCurrentHNode;
 104   }
 105
 106   public void setMapHNodeToCurrentHNode(Map<HNode, HNode> mapHNodeToCurrentHNode) {
 107     this.mapHNodeToCurrentHNode = mapHNodeToCurrentHNode;
 108   }
 109
 110   public void setMapHNodeNameToCurrentHNode(Map<String, HNode> mapHNodeNameToCurrentHNode) {
 111     this.mapHNodeNameToCurrentHNode = mapHNodeNameToCurrentHNode;
 112   }
 113
 114   public Map<Descriptor, HNode> getMapDescToHNode() {
 115     return mapDescToHNode;
 116   }
 117
 118   public void setMapDescToHNode(Map<Descriptor, HNode> map) {
 119     mapDescToHNode.putAll(map);
 120   }
 121
 122   public Set<HNode> getNodeSet() {
 123     return nodeSet;
 124   }
 125
 126   public void addEdge(HNode srcHNode, HNode dstHNode) {
 127
 128     if (!nodeSet.contains(srcHNode)) {
 129       nodeSet.add(srcHNode);
 130     }
 131
 132     if (!nodeSet.contains(dstHNode)) {
 133       nodeSet.add(dstHNode);
 134     }
 135
 136     Set<HNode> possibleCycleSet = getPossibleCycleNodes(srcHNode, dstHNode);
 137
 138     if (possibleCycleSet.size() > 0) {
 139
 140       if (possibleCycleSet.size() == 1) {
 141         if (dstHNode.isSharedNode()) {
 142           // it has already been assigned shared node.
 143         } else {
 144           dstHNode.setSharedNode(true);
 145         }
 146         return;
 147       }
 148
 149       HNode newMergeNode = mergeNodes(possibleCycleSet, false);
 150       newMergeNode.setSharedNode(true);
 151       System.out.println("### INTRODUCE A NEW MERGE NODE: " + newMergeNode);
 152       System.out.println("### CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode + "\n");
 153     } else {
 154       getIncomingNodeSet(dstHNode).add(srcHNode);
 155       getOutgoingNodeSet(srcHNode).add(dstHNode);
 156       // System.out.println("add an edge " + srcHNode + " -> " + dstHNode);
 157     }
 158
 159   }
 160
 161   public void addNode(HNode node) {
 162     nodeSet.add(node);
 163   }
 164
 165   public void addEdge(Descriptor src, Descriptor dst) {
 166     HNode srcHNode = getHNode(src);
 167     HNode dstHNode = getHNode(dst);
 168
 169     addEdge(srcHNode, dstHNode);
 170
 171   }
 172
 173   public void setParamHNode(Descriptor d) {
 174     getHNode(d).setSkeleton(true);
 175   }
 176
 177   public HNode getHNode(Descriptor d) {
 178     if (!mapDescToHNode.containsKey(d)) {
 179       HNode newNode = new HNode(d);
 180       if (d instanceof FieldDescriptor) {
 181         newNode.setSkeleton(true);
 182       }
 183       mappingDescriptorToHNode(d, newNode);
 184       nodeSet.add(newNode);
 185     }
 186     return mapDescToHNode.get(d);
 187   }
 188
 189   public HNode getHNode(String name) {
 190     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 191       HNode node = (HNode) iterator.next();
 192       if (node.getName().equals(name)) {
 193         return node;
 194       }
 195     }
 196     return null;
 197   }
 198
 199   private void mappingDescriptorToHNode(Descriptor desc, HNode node) {
 200     mapDescToHNode.put(desc, node);
 201     if (!mapHNodeToDescSet.containsKey(node)) {
 202       mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
 203     }
 204     mapHNodeToDescSet.get(node).add(desc);
 205   }
 206
 207   public HierarchyGraph generateSkeletonGraph() {
 208
 209     // compose a skeleton graph that only consists of fields or parameters
 210     HierarchyGraph skeletonGraph = new HierarchyGraph(desc);
 211     skeletonGraph.setName(desc + "_SKELETON");
 212
 213     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 214       HNode src = (HNode) iterator.next();
 215       if (src.isSkeleton()) {
 216         Set<HNode> reachSet = getDirectlyReachSkeletonSet(src);
 217         if (reachSet.size() > 0) {
 218           for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) {
 219             HNode dst = (HNode) iterator2.next();
 220             skeletonGraph.addEdge(src, dst);
 221           }
 222         } else {
 223           skeletonGraph.addNode(src);
 224         }
 225       }
 226     }
 227
 228     skeletonGraph.setMapDescToHNode(getMapDescToHNode());
 229     skeletonGraph.setMapHNodeToDescSet(getMapHNodeToDescSet());
 230     skeletonGraph.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
 231     skeletonGraph.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
 232
 233     return skeletonGraph;
 234
 235   }
 236
 237   private Set<HNode> getDirectlyReachSkeletonSet(HNode node) {
 238
 239     Set<HNode> visited = new HashSet<HNode>();
 240     Set<HNode> connected = new HashSet<HNode>();
 241     recurReachSkeletonSet(node, connected, visited);
 242
 243     return connected;
 244   }
 245
 246   public void removeRedundantEdges() {
 247
 248     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 249       HNode src = (HNode) iterator.next();
 250       Set<HNode> connectedSet = getOutgoingNodeSet(src);
 251       Set<HNode> toberemovedSet = new HashSet<HNode>();
 252       for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
 253         HNode dst = (HNode) iterator2.next();
 254         Set<HNode> otherNeighborSet = new HashSet<HNode>();
 255         otherNeighborSet.addAll(connectedSet);
 256         otherNeighborSet.remove(dst);
 257         for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) {
 258           HNode neighbor = (HNode) iterator3.next();
 259           if (reachTo(neighbor, dst, new HashSet<HNode>())) {
 260             toberemovedSet.add(dst);
 261           }
 262         }
 263       }
 264       if (toberemovedSet.size() > 0) {
 265         connectedSet.removeAll(toberemovedSet);
 266
 267         for (Iterator iterator2 = toberemovedSet.iterator(); iterator2.hasNext();) {
 268           HNode node = (HNode) iterator2.next();
 269           getIncomingNodeSet(node).remove(src);
 270         }
 271
 272       }
 273     }
 274
 275   }
 276
 277   public void simplifyHierarchyGraph() {
 278     removeRedundantEdges();
 279     combineRedundantNodes(false);
 280   }
 281
 282   public void simplifySkeletonCombinationHierarchyGraph() {
 283     removeRedundantEdges();
 284     combineRedundantNodes(true);
 285   }
 286
 287   public void combineRedundantNodes(boolean onlyCombinationNodes) {
 288     // Combine field/parameter nodes who have the same set of incoming/outgoing edges.
 289     boolean isUpdated = false;
 290     do {
 291       isUpdated = combineTwoRedundatnNodes(onlyCombinationNodes);
 292     } while (isUpdated);
 293   }
 294
 295   public Set<HNode> getIncomingNodeSet(HNode node) {
 296     if (!mapHNodeToIncomingSet.containsKey(node)) {
 297       mapHNodeToIncomingSet.put(node, new HashSet<HNode>());
 298     }
 299     return mapHNodeToIncomingSet.get(node);
 300   }
 301
 302   public Set<HNode> getOutgoingNodeSet(HNode node) {
 303     if (!mapHNodeToOutgoingSet.containsKey(node)) {
 304       mapHNodeToOutgoingSet.put(node, new HashSet<HNode>());
 305     }
 306     return mapHNodeToOutgoingSet.get(node);
 307   }
 308
 309   private boolean combineTwoRedundatnNodes(boolean onlyCombinationNodes) {
 310     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 311       HNode node1 = (HNode) iterator.next();
 312
 313       if ((onlyCombinationNodes && (!node1.isCombinationNode()))
 314           || (!onlyCombinationNodes && (!node1.isSkeleton()))) {
 315         continue;
 316       }
 317
 318       Set<HNode> incomingNodeSet1 = getIncomingNodeSet(node1);
 319       Set<HNode> outgoingNodeSet1 = getOutgoingNodeSet(node1);
 320
 321       for (Iterator iterator2 = nodeSet.iterator(); iterator2.hasNext();) {
 322         HNode node2 = (HNode) iterator2.next();
 323
 324         if ((onlyCombinationNodes && (!node2.isCombinationNode()))
 325             || (!onlyCombinationNodes && (!node2.isSkeleton()))) {
 326           continue;
 327         }
 328
 329         if (!isEligibleForMerging(node1, node2)) {
 330           continue;
 331         }
 332
 333         if (!node1.equals(node2)) {
 334
 335           Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
 336           Set<HNode> outgoingNodeSet2 = getOutgoingNodeSet(node2);
 337
 338           if (incomingNodeSet1.equals(incomingNodeSet2)
 339               && outgoingNodeSet1.equals(outgoingNodeSet2)) {
 340             // need to merge node1 and node2
 341
 342             Set<HNode> mergeSet = new HashSet<HNode>();
 343             mergeSet.add(node1);
 344             mergeSet.add(node2);
 345             mergeNodes(mergeSet, onlyCombinationNodes);
 346             return true;
 347           }
 348
 349         }
 350       }
 351
 352     }
 353     return false;
 354   }
 355
 356   private boolean isEligibleForMerging(HNode node1, HNode node2) {
 357
 358     System.out.println("********isEligibleForMerging=" + node1 + " " + node2);
 359
 360     if (node1.isSharedNode() || node2.isSharedNode()) {
 361
 362       // if either of nodes is a shared node,
 363       // all descriptors of node1 & node2 should have a primitive type
 364
 365       Set<Descriptor> descSet = new HashSet<Descriptor>();
 366       descSet.addAll(getDescSetOfNode(node1));
 367       descSet.addAll(getDescSetOfNode(node2));
 368
 369       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 370         Descriptor desc = (Descriptor) iterator.next();
 371         if (!LocationInference.isPrimitive(desc)) {
 372           return false;
 373         }
 374       }
 375       System.out.println("******** true");
 376       return true;
 377     }
 378     return false;
 379   }
 380
 381   private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
 382     getIncomingNodeSet(dstHNode).add(srcHNode);
 383     getOutgoingNodeSet(srcHNode).add(dstHNode);
 384     System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode);
 385   }
 386
 387   private HNode mergeNodes(Set<HNode> set, boolean onlyCombinationNodes) {
 388
 389     Set<HNode> incomingNodeSet = new HashSet<HNode>();
 390     Set<HNode> outgoingNodeSet = new HashSet<HNode>();
 391
 392     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 393       HNode node = (HNode) iterator.next();
 394       incomingNodeSet.addAll(getIncomingNodeSet(node));
 395       outgoingNodeSet.addAll(getOutgoingNodeSet(node));
 396     }
 397
 398     String nodeName;
 399     boolean isMergeNode = false;
 400     if (onlyCombinationNodes) {
 401       nodeName = "Comb" + (LocationInference.locSeed++);
 402     } else {
 403       nodeName = "Node" + (LocationInference.locSeed++);
 404       isMergeNode = true;
 405     }
 406     HNode newMergeNode = new HNode(nodeName);
 407     newMergeNode.setMergeNode(isMergeNode);
 408
 409     nodeSet.add(newMergeNode);
 410     nodeSet.removeAll(set);
 411
 412     // if the input set contains a skeleton node, need to set a new merge node as skeleton also
 413     boolean hasSkeleton = false;
 414     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 415       HNode inNode = (HNode) iterator.next();
 416       if (inNode.isSkeleton()) {
 417         hasSkeleton = true;
 418         break;
 419       }
 420     }
 421     System.out.println("--Set merging node=" + newMergeNode + " as a skeleton=" + set
 422         + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc);
 423     newMergeNode.setSkeleton(hasSkeleton);
 424
 425     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 426       HNode node = (HNode) iterator.next();
 427       Set<Descriptor> descSetOfNode = getDescSetOfNode(node);
 428       for (Iterator iterator2 = descSetOfNode.iterator(); iterator2.hasNext();) {
 429         Descriptor desc = (Descriptor) iterator2.next();
 430         mappingDescriptorToHNode(desc, newMergeNode);
 431       }
 432     }
 433
 434     for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
 435       HNode inNode = (HNode) iterator.next();
 436       Set<HNode> outSet = getOutgoingNodeSet(inNode);
 437       outSet.removeAll(set);
 438       if (!set.contains(inNode)) {
 439         addEdgeWithNoCycleCheck(inNode, newMergeNode);
 440       }
 441     }
 442
 443     for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
 444       HNode outNode = (HNode) iterator.next();
 445       Set<HNode> inSet = getIncomingNodeSet(outNode);
 446       inSet.removeAll(set);
 447       if (!set.contains(outNode)) {
 448         addEdgeWithNoCycleCheck(newMergeNode, outNode);
 449       }
 450     }
 451
 452     Set<HNode> mergedSkeletonNode = new HashSet<HNode>();
 453     for (Iterator<HNode> iter = set.iterator(); iter.hasNext();) {
 454       HNode merged = iter.next();
 455       if (merged.isSkeleton()) {
 456         mergedSkeletonNode.add(merged);
 457       }
 458     }
 459
 460     // mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode);
 461     // for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 462     mapMergeNodetoMergingSet.put(newMergeNode, set);
 463     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 464       HNode mergedNode = (HNode) iterator.next();
 465       addMapHNodeToCurrentHNode(mergedNode, newMergeNode);
 466     }
 467     System.out.println("###mergedSkeletonNode=" + mergedSkeletonNode);
 468     System.out.println("###MERGING NODE=" + set + " new node=" + newMergeNode);
 469
 470     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 471       HNode hNode = (HNode) iterator.next();
 472       System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode));
 473     }
 474
 475     return newMergeNode;
 476   }
 477
 478   private void addMapHNodeToCurrentHNode(HNode curNode, HNode newNode) {
 479     if (curNode.isMergeNode()) {
 480       Set<HNode> mergingSet = getMergingSet(curNode);
 481       mergingSet.add(curNode);
 482       System.out.println("addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet="
 483           + mergingSet);
 484       for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) {
 485         HNode mergingNode = (HNode) iterator.next();
 486         mapHNodeToCurrentHNode.put(mergingNode, newNode);
 487         mapHNodeNameToCurrentHNode.put(mergingNode.getName(), newNode);
 488       }
 489     } else {
 490       mapHNodeToCurrentHNode.put(curNode, newNode);
 491       mapHNodeNameToCurrentHNode.put(curNode.getName(), newNode);
 492     }
 493   }
 494
 495   public HNode getCurrentHNode(HNode node) {
 496     if (!mapHNodeToCurrentHNode.containsKey(node)) {
 497       mapHNodeToCurrentHNode.put(node, node);
 498     }
 499     return mapHNodeToCurrentHNode.get(node);
 500   }
 501
 502   public HNode getCurrentHNode(String nodeName) {
 503     return mapHNodeNameToCurrentHNode.get(nodeName);
 504   }
 505
 506   private Set<HNode> getMergingSet(HNode mergeNode) {
 507     Set<HNode> mergingSet = new HashSet<HNode>();
 508     Set<HNode> mergedNode = mapMergeNodetoMergingSet.get(mergeNode);
 509     for (Iterator iterator = mergedNode.iterator(); iterator.hasNext();) {
 510       HNode node = (HNode) iterator.next();
 511       if (node.isMergeNode()) {
 512         mergingSet.add(node);
 513         mergingSet.addAll(getMergingSet(node));
 514       } else {
 515         mergingSet.add(node);
 516       }
 517     }
 518     return mergingSet;
 519   }
 520
 521   public Set<Descriptor> getDescSetOfNode(HNode node) {
 522     if (!mapHNodeToDescSet.containsKey(node)) {
 523       mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
 524     }
 525     return mapHNodeToDescSet.get(node);
 526   }
 527
 528   private boolean reachTo(HNode src, HNode dst, Set<HNode> visited) {
 529     Set<HNode> connectedSet = getOutgoingNodeSet(src);
 530     for (Iterator<HNode> iterator = connectedSet.iterator(); iterator.hasNext();) {
 531       HNode n = iterator.next();
 532       if (n.equals(dst)) {
 533         return true;
 534       }
 535       if (!visited.contains(n)) {
 536         visited.add(n);
 537         if (reachTo(n, dst, visited)) {
 538           return true;
 539         }
 540       }
 541     }
 542     return false;
 543   }
 544
 545   private void recurReachSkeletonSet(HNode node, Set<HNode> connected, Set<HNode> visited) {
 546
 547     Set<HNode> outSet = getOutgoingNodeSet(node);
 548     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 549       HNode outNode = (HNode) iterator.next();
 550
 551       if (outNode.isSkeleton()) {
 552         connected.add(outNode);
 553       } else if (!visited.contains(outNode)) {
 554         visited.add(outNode);
 555         recurReachSkeletonSet(outNode, connected, visited);
 556       }
 557     }
 558
 559   }
 560
 561   public Set<HNode> getDirectlyReachableSkeletonCombinationNodeFrom(HNode node,
 562       Set<HNode> combinationNodeSet) {
 563     Set<HNode> reachable = new HashSet<HNode>();
 564     Set<HNode> visited = new HashSet<HNode>();
 565     visited.add(node);
 566     recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited, reachable, combinationNodeSet);
 567     return reachable;
 568   }
 569
 570   public void recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited,
 571       Set<HNode> reachable, Set<HNode> combinationNodeSet) {
 572
 573     Set<HNode> outSet = getOutgoingNodeSet(node);
 574     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 575       HNode out = (HNode) iterator.next();
 576
 577       if (!visited.contains(out)) {
 578         visited.add(out);
 579         if (out.isSkeleton()) {
 580           reachable.add(out);
 581         } else if (out.isCombinationNode()) {
 582           if (combinationNodeSet == null) {
 583             reachable.add(out);
 584           } else if (!combinationNodeSet.contains(out)) {
 585             reachable.add(out);
 586           } else {
 587             recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
 588                 combinationNodeSet);
 589           }
 590         } else {
 591           recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
 592               combinationNodeSet);
 593         }
 594
 595       }
 596
 597     }
 598
 599   }
 600
 601   public HNode getDirectlyReachableSkeletonCombinationNodeFrom(HNode node) {
 602     Set<HNode> visited = new HashSet<HNode>();
 603     return recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited);
 604   }
 605
 606   public HNode recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited) {
 607
 608     Set<HNode> outSet = getOutgoingNodeSet(node);
 609     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 610       HNode out = (HNode) iterator.next();
 611       // if (!visited.contains(out)) {
 612       if (out.isCombinationNode() || out.isSkeleton()) {
 613         return out;
 614       } else {
 615         // visited.add(out);
 616         return getDirectlyReachableSkeletonCombinationNodeFrom(out);
 617       }
 618     }
 619     // }
 620
 621     return null;
 622   }
 623
 624   public Set<HNode> getPossibleCycleNodes(HNode src, HNode dst) {
 625     // if an edge from src to dst introduces a new cycle flow,
 626     // the method returns the set of elements consisting of the cycle
 627     Set<HNode> cycleNodeSet = new HashSet<HNode>();
 628     // if the dst node reaches to the src node, the new relation
 629     // introduces a cycle to the lattice
 630     if (dst.equals(src)) {
 631       cycleNodeSet.add(dst);
 632       cycleNodeSet.add(src);
 633     } else if (reachTo(dst, src)) {
 634       cycleNodeSet.add(dst);
 635       cycleNodeSet.add(src);
 636       getInBetweenElements(dst, src, cycleNodeSet);
 637     }
 638     return cycleNodeSet;
 639   }
 640
 641   private void getInBetweenElements(HNode start, HNode end, Set<HNode> nodeSet) {
 642     Set<HNode> connectedSet = getOutgoingNodeSet(start);
 643     for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
 644       HNode cur = (HNode) iterator.next();
 645       if ((!start.equals(cur)) && (!cur.equals(end)) && reachTo(cur, end)) {
 646         nodeSet.add(cur);
 647         getInBetweenElements(cur, end, nodeSet);
 648       }
 649     }
 650   }
 651
 652   public boolean reachTo(HNode node1, HNode node2) {
 653     return reachTo(node1, node2, new HashSet<HNode>());
 654   }
 655
 656   public Set<HNode> getCombineSetByCombinationNode(HNode node) {
 657     if (!mapCombinationNodeToCombineNodeSet.containsKey(node)) {
 658       mapCombinationNodeToCombineNodeSet.put(node, new HashSet<HNode>());
 659     }
 660     return mapCombinationNodeToCombineNodeSet.get(node);
 661   }
 662
 663   public HNode getCombinationNode(Set<HNode> combineSet) {
 664     if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
 665       String name = "COMB" + (LocationInference.locSeed++);
 666       HNode node = new HNode(name);
 667       node.setCombinationNode(true);
 668       nodeSet.add(node);
 669       mapCombineNodeSetToCombinationNode.put(combineSet, node);
 670       mapCombinationNodeToCombineNodeSet.put(node, combineSet);
 671     }
 672
 673     return mapCombineNodeSetToCombinationNode.get(combineSet);
 674   }
 675
 676   public Map<Set<HNode>, HNode> getMapCombineNodeSetToCombinationNode() {
 677     return mapCombineNodeSetToCombinationNode;
 678   }
 679
 680   public Set<Set<HNode>> getCombineNodeSet() {
 681     return mapCombineNodeSetToOutgoingNodeSet.keySet();
 682   }
 683
 684   public void insertCombinationNodesToGraph(HierarchyGraph simpleHierarchyGraph) {
 685     // add a new combination node where parameter/field flows are actually combined.
 686
 687     simpleHierarchyGraph.identifyCombinationNodes();
 688
 689     Set<Set<HNode>> keySet = simpleHierarchyGraph.getCombineNodeSet();
 690     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 691       Set<HNode> combineSet = (Set<HNode>) iterator.next();
 692       System.out.println("--combineSet=" + combineSet);
 693       HNode combinationNode = getCombinationNode(combineSet);
 694       System.out.println("--combinationNode=" + combinationNode);
 695       // add an edge from a skeleton node to a combination node
 696       for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
 697         HNode inSkeletonNode = (HNode) iterator2.next();
 698         // System.out.println("--inSkeletonNode=" + inSkeletonNode + "  desc="
 699         // + inSkeletonNode.getDescriptor());
 700         HNode srcNode;
 701         if (inSkeletonNode.getDescriptor() == null) {
 702           // the node is merging one...
 703           srcNode = inSkeletonNode;
 704         } else {
 705           srcNode = getHNode(inSkeletonNode.getDescriptor());
 706         }
 707         // System.out.println("--srcNode=" + srcNode);
 708         addEdgeWithNoCycleCheck(srcNode, combinationNode);
 709       }
 710
 711       // add an edge from the combination node to outgoing nodes
 712       Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
 713       for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 714         HNode curNode = (HNode) iterator2.next();
 715         if (curNode.isCombinationNode()) {
 716           Set<HNode> combineNode = simpleHierarchyGraph.getCombineSetByCombinationNode(curNode);
 717           HNode outNode = getCombinationNode(combineNode);
 718           addEdgeWithNoCycleCheck(combinationNode, outNode);
 719         } else if (curNode.isSkeleton()) {
 720           // HNode dstNode2 = getHNode(curNode.getDescriptor());
 721           HNode dstNode = getCurrentHNode(curNode);
 722           // System.out.println("-----curNode=" + curNode + "------->" + dstNode + "    dstNode2="
 723           // + dstNode2);
 724           addEdgeWithNoCycleCheck(combinationNode, dstNode);
 725         }
 726       }
 727
 728       System.out.println("--");
 729
 730     }
 731
 732   }
 733
 734   private void addCombinationNode(HNode curNode, Set<HNode> reachToSet, Set<HNode> reachableSet) {
 735     if (!mapSkeletonNodeSetToCombinationNode.containsKey(reachToSet)) {
 736       // need to create a new combination node
 737       String nodeName = "Comb" + (LocationInference.locSeed++);
 738       HNode newCombinationNode = new HNode(nodeName);
 739       newCombinationNode.setCombinationNode(true);
 740
 741       nodeSet.add(newCombinationNode);
 742       mapSkeletonNodeSetToCombinationNode.put(reachToSet, newCombinationNode);
 743
 744       for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
 745         HNode reachToNode = (HNode) iterator.next();
 746         addEdge(reachToNode, newCombinationNode);
 747       }
 748
 749     }
 750
 751     HNode combinationNode = mapSkeletonNodeSetToCombinationNode.get(reachToSet);
 752     for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
 753       HNode reachableNode = (HNode) iterator.next();
 754       addEdge(combinationNode, reachableNode);
 755     }
 756
 757   }
 758
 759   private Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
 760
 761     Set<HNode> reachToSet = new HashSet<HNode>();
 762     Set<HNode> visited = new HashSet<HNode>();
 763     recurSkeletonReachTo(node, reachToSet, visited);
 764
 765     // if a node reaches to one of elements in the reachToSet, we do not need to keep it
 766     // because the node is not directly connected to the combination node
 767
 768     removeRedundantReachToNodes(reachToSet);
 769
 770     return reachToSet;
 771   }
 772
 773   private void removeRedundantReachToNodes(Set<HNode> reachToSet) {
 774
 775     Set<HNode> toberemoved = new HashSet<HNode>();
 776     for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
 777       HNode cur = (HNode) iterator.next();
 778
 779       for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
 780         HNode dst = (HNode) iterator2.next();
 781         if (!cur.equals(dst) && reachTo(cur, dst)) {
 782           // it is redundant
 783           toberemoved.add(cur);
 784         }
 785       }
 786     }
 787     reachToSet.removeAll(toberemoved);
 788   }
 789
 790   private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
 791
 792     Set<HNode> inSet = getIncomingNodeSet(node);
 793     for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
 794       HNode inNode = (HNode) iterator.next();
 795
 796       if (inNode.isSkeleton()) {
 797         reachToSet.add(inNode);
 798       } else if (!visited.contains(inNode)) {
 799         visited.add(inNode);
 800         recurSkeletonReachTo(inNode, reachToSet, visited);
 801       }
 802     }
 803
 804   }
 805
 806   public Map<HNode, Set<HNode>> getMapHNodeToOutgoingSet() {
 807     return mapHNodeToOutgoingSet;
 808   }
 809
 810   public Map<HNode, Set<HNode>> getMapHNodeToIncomingSet() {
 811     return mapHNodeToIncomingSet;
 812   }
 813
 814   public void setMapHNodeToOutgoingSet(Map<HNode, Set<HNode>> in) {
 815     mapHNodeToOutgoingSet.clear();
 816     Set<HNode> keySet = in.keySet();
 817     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 818       HNode key = (HNode) iterator.next();
 819       Set<HNode> inSet = in.get(key);
 820       Set<HNode> newSet = new HashSet<HNode>();
 821       newSet.addAll(inSet);
 822       mapHNodeToOutgoingSet.put(key, newSet);
 823     }
 824   }
 825
 826   public void setMapHNodeToIncomingSet(Map<HNode, Set<HNode>> in) {
 827     mapHNodeToIncomingSet.clear();
 828     Set<HNode> keySet = in.keySet();
 829     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 830       HNode key = (HNode) iterator.next();
 831       Set<HNode> inSet = in.get(key);
 832       Set<HNode> newSet = new HashSet<HNode>();
 833       newSet.addAll(inSet);
 834       mapHNodeToIncomingSet.put(key, newSet);
 835     }
 836   }
 837
 838   public void setNodeSet(Set<HNode> inSet) {
 839     nodeSet.clear();
 840     nodeSet.addAll(inSet);
 841   }
 842
 843   public HierarchyGraph clone() {
 844     HierarchyGraph clone = new HierarchyGraph();
 845     clone.setDesc(getDesc());
 846     clone.setName(getName());
 847     clone.setNodeSet(getNodeSet());
 848     clone.setMapHNodeToIncomingSet(getMapHNodeToIncomingSet());
 849     clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
 850     clone.setMapDescToHNode(getMapDescToHNode());
 851     clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
 852     clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
 853     clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
 854     clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
 855
 856     return clone;
 857   }
 858
 859   public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
 860     return mapMergeNodetoMergingSet;
 861   }
 862
 863   public void setMapHNodetoMergeSet(Map<HNode, Set<HNode>> mapHNodetoMergeSet) {
 864     this.mapMergeNodetoMergingSet = mapHNodetoMergeSet;
 865   }
 866
 867   public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
 868
 869     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
 870       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
 871     }
 872     return mapCombineNodeSetToOutgoingNodeSet.get(combineSet);
 873   }
 874
 875   public void identifyCombinationNodes() {
 876
 877     // 1) set combination node flag if a node combines more than one skeleton node.
 878     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 879       HNode node = (HNode) iterator.next();
 880       if (!node.isSkeleton()) {
 881         Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
 882         if (reachToSet.size() > 1) {
 883           // if (countSkeletonNodes(reachToSet) > 1) {
 884           System.out.println("-node=" + node + "  reachToSet=" + reachToSet);
 885           System.out.println("-set combinationnode=" + node);
 886           node.setCombinationNode(true);
 887           mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
 888         }
 889       }
 890     }
 891
 892     // 2) compute the outgoing set that needs to be directly connected from the combination node
 893     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 894       HNode node = (HNode) iterator.next();
 895       if (node.isCombinationNode()) {
 896         Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
 897         Set<HNode> outSet = getDirectlyReachableNodeSetFromCombinationNode(node);
 898         addMapCombineSetToOutgoingSet(combineSet, outSet);
 899       }
 900     }
 901
 902   }
 903
 904   public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
 905     return mapCombinationNodeToCombineNodeSet;
 906   }
 907
 908   public int countSkeletonNodes(Set<HNode> set) {
 909     int count = 0;
 910
 911     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 912       HNode node = (HNode) iterator.next();
 913       Set<Descriptor> descSet = getDescSetOfNode(node);
 914       count += descSet.size();
 915     }
 916
 917     return count;
 918   }
 919
 920   private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
 921     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
 922       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
 923     }
 924     mapCombineNodeSetToOutgoingNodeSet.get(combineSet).addAll(outSet);
 925   }
 926
 927   private Set<HNode> getDirectlyReachableNodeSetFromCombinationNode(HNode node) {
 928     // the method returns the set of nodes that are reachable from the current node
 929     // and do not combine the same set of skeleton nodes...
 930
 931     Set<HNode> visited = new HashSet<HNode>();
 932     Set<HNode> reachableSet = new HashSet<HNode>();
 933     Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
 934
 935     recurDirectlyReachableNodeSetFromCombinationNode(node, combineSet, reachableSet, visited);
 936
 937     return reachableSet;
 938   }
 939
 940   private void recurDirectlyReachableNodeSetFromCombinationNode(HNode node, Set<HNode> combineSet,
 941       Set<HNode> reachableSet, Set<HNode> visited) {
 942
 943     Set<HNode> outSet = getOutgoingNodeSet(node);
 944     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 945       HNode outNode = (HNode) iterator.next();
 946
 947       if (outNode.isCombinationNode()) {
 948         Set<HNode> combineSetOfOutNode = mapCombinationNodeToCombineNodeSet.get(outNode);
 949         if (combineSetOfOutNode.equals(combineSet)) {
 950           recurDirectlyReachableNodeSetFromCombinationNode(outNode, combineSet, reachableSet,
 951               visited);
 952         } else {
 953           reachableSet.add(outNode);
 954         }
 955       } else if (outNode.isSkeleton()) {
 956         reachableSet.add(outNode);
 957       }
 958
 959     }
 960
 961   }
 962
 963   private Set<HNode> getReachableNodeSetFrom(HNode node) {
 964
 965     Set<HNode> reachableSet = new HashSet<HNode>();
 966     Set<HNode> visited = new HashSet<HNode>();
 967
 968     recurReachableNodeSetFrom(node, reachableSet, visited);
 969
 970     return reachableSet;
 971   }
 972
 973   private void recurReachableNodeSetFrom(HNode node, Set<HNode> reachableSet, Set<HNode> visited) {
 974
 975     Set<HNode> outgoingNodeSet = getOutgoingNodeSet(node);
 976     for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
 977       HNode outNode = (HNode) iterator.next();
 978       reachableSet.add(outNode);
 979       if (!visited.contains(outNode)) {
 980         visited.add(outNode);
 981         recurReachableNodeSetFrom(outNode, reachableSet, visited);
 982       }
 983     }
 984
 985   }
 986
 987   public void assignUniqueIndexToNode() {
 988     int idx = 1;
 989     System.out.println("nodeSet=" + nodeSet);
 990     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 991       HNode node = (HNode) iterator.next();
 992       mapHNodeToUniqueIndex.put(node, idx);
 993       idx++;
 994     }
 995
 996     BASISTOPELEMENT = new HashSet<Integer>();
 997     for (int i = 1; i < idx + 1; i++) {
 998       BASISTOPELEMENT.add(i);
 999     }
1000   }
1001
1002   public BasisSet computeBasisSet(Set<HNode> notGenerateSet) {
1003
1004     // assign a unique index to a node
1005     assignUniqueIndexToNode();
1006
1007     // compute basis for each node
1008     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1009       HNode node = (HNode) iterator.next();
1010
1011       if (notGenerateSet.contains(node)) {
1012         System.out.println("%%%SKIP =" + node);
1013         continue;
1014       }
1015       Set<Integer> basis = new HashSet<Integer>();
1016       basis.addAll(BASISTOPELEMENT);
1017
1018       Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
1019       System.out.println("node=" + node + "    reachableNodeSet=" + reachableNodeSet);
1020       System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node));
1021       // if a node is reachable from the current node
1022       // need to remove the index of the reachable node from the basis
1023
1024       basis.remove(getHNodeIndex(node));
1025       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1026         HNode reachableNode = (HNode) iterator2.next();
1027         System.out.println("reachableNode=" + reachableNode);
1028         System.out.println("getHNodeIndex(reachableNode))="
1029             + mapHNodeToUniqueIndex.get(reachableNode));
1030         int idx = getHNodeIndex(reachableNode);
1031         basis.remove(idx);
1032       }
1033
1034       mapHNodeToBasis.put(node, basis);
1035     }
1036
1037     // construct the basis set
1038
1039     BasisSet basisSet = new BasisSet();
1040
1041     Set<HNode> keySet = mapHNodeToBasis.keySet();
1042     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1043       HNode node = (HNode) iterator.next();
1044       Set<Integer> basis = mapHNodeToBasis.get(node);
1045       basisSet.addElement(basis, node);
1046     }
1047
1048     return basisSet;
1049
1050   }
1051
1052   public int getHNodeIndex(HNode node) {
1053     return mapHNodeToUniqueIndex.get(node).intValue();
1054   }
1055
1056   public Map<HNode, Integer> getMapHNodeToUniqueIndex() {
1057     return mapHNodeToUniqueIndex;
1058   }
1059
1060   public Map<HNode, Set<Integer>> getMapHNodeToBasis() {
1061     return mapHNodeToBasis;
1062   }
1063
1064   public Set<HNode> getCombinationNodeSetByCombineNodeSet(Set<HNode> combineSkeletonNodeSet) {
1065
1066     Set<HNode> combinationNodeSet = new HashSet<HNode>();
1067     Set<HNode> keySet = mapCombinationNodeToCombineNodeSet.keySet();
1068     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1069       HNode key = (HNode) iterator.next();
1070
1071       if (mapCombinationNodeToCombineNodeSet.get(key).equals(combineSkeletonNodeSet)) {
1072         combinationNodeSet.add(key);
1073       }
1074     }
1075
1076     return combinationNodeSet;
1077   }
1078
1079   public void writeGraph() {
1080
1081     String graphName = "hierarchy" + name;
1082     graphName = graphName.replaceAll("[\\W]", "");
1083
1084     try {
1085       BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
1086
1087       bw.write("digraph " + graphName + " {\n");
1088
1089       Iterator<HNode> iter = nodeSet.iterator();
1090
1091       Set<HNode> addedNodeSet = new HashSet<HNode>();
1092
1093       while (iter.hasNext()) {
1094         HNode u = iter.next();
1095
1096         Set<HNode> outSet = getOutgoingNodeSet(u);
1097
1098         if (outSet.size() == 0) {
1099           if (!addedNodeSet.contains(u)) {
1100             drawNode(bw, u);
1101             addedNodeSet.add(u);
1102           }
1103         } else {
1104           for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1105             HNode v = (HNode) iterator.next();
1106             if (!addedNodeSet.contains(u)) {
1107               drawNode(bw, u);
1108               addedNodeSet.add(u);
1109             }
1110             if (!addedNodeSet.contains(v)) {
1111               drawNode(bw, v);
1112               addedNodeSet.add(v);
1113             }
1114             bw.write("" + u.getName() + " -> " + v.getName() + ";\n");
1115           }
1116         }
1117
1118       }
1119
1120       bw.write("}\n");
1121       bw.close();
1122
1123     } catch (IOException e) {
1124       e.printStackTrace();
1125     }
1126   }
1127
1128   public boolean contains(HNode node) {
1129     return nodeSet.contains(node);
1130   }
1131
1132   public boolean isDirectlyConnectedTo(HNode src, HNode dst) {
1133     return getOutgoingNodeSet(src).contains(dst);
1134   }
1135
1136   private String convertMergeSetToString(Set<HNode> mergeSet) {
1137     String str = "";
1138     for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
1139       HNode merged = (HNode) iterator.next();
1140       if (merged.isMergeNode()) {
1141         str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged));
1142       } else {
1143         str += " " + merged.getName();
1144       }
1145     }
1146     return str;
1147   }
1148
1149   private void drawNode(BufferedWriter bw, HNode node) throws IOException {
1150     String nodeName;
1151     if (node.isMergeNode()) {
1152       nodeName = node.getNamePropertyString();
1153       Set<HNode> mergeSet = mapMergeNodetoMergingSet.get(node);
1154       nodeName += ":" + convertMergeSetToString(mergeSet);
1155     } else {
1156       nodeName = node.getNamePropertyString();
1157     }
1158     bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1159   }
1160
1161   public int countHopFromTopLocation(HNode node) {
1162
1163     Set<HNode> inNodeSet = getIncomingNodeSet(node);
1164     int count = 0;
1165     if (inNodeSet.size() > 0) {
1166       count = recurCountHopFromTopLocation(inNodeSet, 1);
1167     }
1168
1169     return count;
1170   }
1171
1172   private int recurCountHopFromTopLocation(Set<HNode> nodeSet, int curCount) {
1173
1174     int max = curCount;
1175     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1176       HNode node = (HNode) iterator.next();
1177       Set<HNode> inNodeSet = getIncomingNodeSet(node);
1178       if (inNodeSet.size() > 0) {
1179         int recurCount = recurCountHopFromTopLocation(inNodeSet, curCount + 1);
1180         if (max < recurCount) {
1181           max = recurCount;
1182         }
1183       }
1184     }
1185     return max;
1186   }
1187
1188 }