Robust/src/Analysis/SSJava/BuildLattice.java

   1 package Analysis.SSJava;
   2
   3 import java.util.HashMap;
   4 import java.util.HashSet;
   5 import java.util.Iterator;
   6 import java.util.Map;
   7 import java.util.Set;
   8
   9 import IR.ClassDescriptor;
  10 import IR.Descriptor;
  11 import IR.MethodDescriptor;
  12 import IR.NameDescriptor;
  13 import Util.Pair;
  14
  15 public class BuildLattice {
  16
  17   private LocationInference infer;
  18   private Map<HNode, TripleItem> mapSharedNodeToTripleItem;
  19   private Map<HNode, Integer> mapHNodeToHighestIndex;
  20
  21   private Map<Descriptor, Map<TripleItem, String>> mapDescToIntermediateLocMap;
  22
  23   private Map<Pair<HNode, HNode>, Integer> mapItemToHighestIndex;
  24
  25   public BuildLattice(LocationInference infer) {
  26     this.infer = infer;
  27     this.mapSharedNodeToTripleItem = new HashMap<HNode, TripleItem>();
  28     this.mapHNodeToHighestIndex = new HashMap<HNode, Integer>();
  29     this.mapItemToHighestIndex = new HashMap<Pair<HNode, HNode>, Integer>();
  30     this.mapDescToIntermediateLocMap = new HashMap<Descriptor, Map<TripleItem, String>>();
  31   }
  32
  33   public SSJavaLattice<String> buildLattice(Descriptor desc) {
  34
  35     HierarchyGraph inputGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
  36     LocationSummary locSummary = infer.getLocationSummary(desc);
  37
  38     HierarchyGraph naiveGraph = infer.getSimpleHierarchyGraph(desc);
  39
  40     // I don't think we need to keep the below if statement anymore
  41     // because hierarchy graph does not have any composite location
  42     Set<HNode> nodeSetWithCompositeLocation = new HashSet<HNode>();
  43     if (desc instanceof MethodDescriptor) {
  44       FlowGraph flowGraph = infer.getFlowGraph((MethodDescriptor) desc);
  45
  46       for (Iterator iterator = inputGraph.getNodeSet().iterator(); iterator.hasNext();) {
  47         HNode hnode = (HNode) iterator.next();
  48         Descriptor hnodeDesc = hnode.getDescriptor();
  49         if (hnodeDesc != null) {
  50           NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
  51           descTuple.add(hnodeDesc);
  52
  53           if (flowGraph.contains(descTuple)) {
  54             FlowNode flowNode = flowGraph.getFlowNode(descTuple);
  55             if (flowNode.getCompositeLocation() != null) {
  56               nodeSetWithCompositeLocation.add(hnode);
  57             }
  58           }
  59
  60         }
  61       }
  62
  63     }
  64
  65     // /////////////////////////////////////////////////////////////////////////////////////
  66     // lattice generation for the native approach
  67     BasisSet naiveBasisSet = naiveGraph.computeBasisSet(nodeSetWithCompositeLocation);
  68     // debug_print(inputGraph);
  69
  70     Family naiveFamily = generateFamily(naiveBasisSet);
  71     Map<Set<Integer>, Set<Set<Integer>>> naive_mapImSucc =
  72         coveringGraph(naiveBasisSet, naiveFamily);
  73
  74     SSJavaLattice<String> naive_lattice =
  75         buildLattice(desc, naiveBasisSet, naiveGraph, null, naive_mapImSucc);
  76     LocationInference.numLocationsNaive += naive_lattice.getKeySet().size();
  77     infer.addNaiveLattice(desc, naive_lattice);
  78     // /////////////////////////////////////////////////////////////////////////////////////
  79
  80     // lattice generation for the proposed approach
  81     BasisSet basisSet = inputGraph.computeBasisSet(nodeSetWithCompositeLocation);
  82     // debug_print(inputGraph);
  83
  84     Family family = generateFamily(basisSet);
  85     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = coveringGraph(basisSet, family);
  86
  87     SSJavaLattice<String> lattice = buildLattice(desc, basisSet, inputGraph, locSummary, mapImSucc);
  88     return lattice;
  89
  90   }
  91
  92   public void setIntermediateLocMap(Descriptor desc, Map<TripleItem, String> map) {
  93     mapDescToIntermediateLocMap.put(desc, map);
  94   }
  95
  96   public Map<TripleItem, String> getIntermediateLocMap(Descriptor desc) {
  97     if (!mapDescToIntermediateLocMap.containsKey(desc)) {
  98       mapDescToIntermediateLocMap.put(desc, new HashMap<TripleItem, String>());
  99     }
 100     return mapDescToIntermediateLocMap.get(desc);
 101   }
 102
 103   private Descriptor getParent(Descriptor desc) {
 104     if (desc instanceof MethodDescriptor) {
 105       MethodDescriptor md = (MethodDescriptor) desc;
 106       ClassDescriptor cd = md.getClassDesc();
 107       return infer.getParentMethodDesc(cd, md);
 108     } else {
 109       return ((ClassDescriptor) desc).getSuperDesc();
 110     }
 111   }
 112
 113   private SSJavaLattice<String> buildLattice(Descriptor desc, BasisSet basisSet,
 114       HierarchyGraph inputGraph, LocationSummary locSummary,
 115       Map<Set<Integer>, Set<Set<Integer>>> mapImSucc) {
 116
 117     System.out.println("\nBuild Lattice:" + inputGraph.getName());
 118
 119     SSJavaLattice<String> lattice =
 120         new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
 121
 122     Map<Set<Integer>, String> mapFToLocName = new HashMap<Set<Integer>, String>();
 123
 124     Set<Set<Integer>> keySet = mapImSucc.keySet();
 125     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 126       Set<Integer> higher = (Set<Integer>) iterator.next();
 127
 128       String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher);
 129
 130       HNode higherNode = inputGraph.getHNode(higherName);
 131
 132       if (higherNode == null) {
 133         NameDescriptor d = new NameDescriptor(higherName);
 134         higherNode = inputGraph.getHNode(d);
 135         higherNode.setSkeleton(true);
 136       }
 137
 138       if (higherNode != null && higherNode.isSharedNode()) {
 139         lattice.addSharedLoc(higherName);
 140       }
 141       Set<Descriptor> descSet = inputGraph.getDescSetOfNode(higherNode);
 142       // System.out.println("higherName=" + higherName + "  higherNode=" + higherNode + "  descSet="
 143       // + descSet);
 144
 145       if (locSummary != null) {
 146         for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) {
 147           Descriptor d = (Descriptor) iterator2.next();
 148           locSummary.addMapHNodeNameToLocationName(d.getSymbol(), higherName);
 149         }
 150       }
 151
 152       // locSummary.addMapHNodeNameToLocationName(higherName, higherName);
 153
 154       Set<Set<Integer>> lowerSet = mapImSucc.get(higher);
 155       for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
 156         Set<Integer> lower = (Set<Integer>) iterator2.next();
 157
 158         String lowerName = generateElementName(basisSet, inputGraph, mapFToLocName, lower);
 159         HNode lowerNode = inputGraph.getHNode(lowerName);
 160
 161         if (lowerNode == null && !lowerName.equals(SSJavaAnalysis.BOTTOM)) {
 162           NameDescriptor d = new NameDescriptor(lowerName);
 163           lowerNode = inputGraph.getHNode(d);
 164           lowerNode.setSkeleton(true);
 165         }
 166
 167         if (lowerNode != null && !inputGraph.isDirectlyConnectedTo(higherNode, lowerNode)) {
 168           inputGraph.addEdge(higherNode, lowerNode);
 169         }
 170
 171         if (lowerNode != null && lowerNode.isSharedNode()) {
 172           lattice.addSharedLoc(lowerName);
 173         }
 174
 175         Set<Descriptor> lowerDescSet = inputGraph.getDescSetOfNode(lowerNode);
 176         // System.out.println("lowerName=" + lowerName + "  lowerNode=" + lowerNode + "  descSet="
 177         // + lowerDescSet);
 178         if (locSummary != null) {
 179           for (Iterator iterator3 = lowerDescSet.iterator(); iterator3.hasNext();) {
 180             Descriptor d = (Descriptor) iterator3.next();
 181             locSummary.addMapHNodeNameToLocationName(d.getSymbol(), lowerName);
 182           }
 183         }
 184         // locSummary.addMapHNodeNameToLocationName(lowerName, lowerName);
 185
 186         if (higher.size() == 0) {
 187           // empty case
 188           lattice.put(lowerName);
 189         } else {
 190           lattice.addRelationHigherToLower(higherName, lowerName);
 191         }
 192
 193       }
 194
 195     }
 196
 197     inputGraph.removeRedundantEdges();
 198     return lattice;
 199   }
 200
 201   public HNode getCombinationNodeInSCGraph(Descriptor desc, HNode nodeFromSimpleGraph) {
 202
 203     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 204
 205     if (nodeFromSimpleGraph.isSkeleton()) {
 206       return scGraph.getCurrentHNode(nodeFromSimpleGraph);
 207     }
 208
 209     Set<HNode> combineSkeletonNodeSet =
 210         infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(nodeFromSimpleGraph);
 211     HNode combinationNodeInSCGraph =
 212         infer.getSkeletonCombinationHierarchyGraph(desc).getMapCombineNodeSetToCombinationNode()
 213             .get(combineSkeletonNodeSet);
 214
 215     // Set<HNode> combineSkeletonNodeSet =
 216     // infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(simpleGraphNode);
 217     // HNode combinationNodeInSCGraph =
 218     // infer.getSkeletonCombinationHierarchyGraph(desc).getCombinationNode(combineSkeletonNodeSet);
 219     return combinationNodeInSCGraph;
 220   }
 221
 222   public SSJavaLattice<String> insertIntermediateNodesToStraightLine(Descriptor desc,
 223       SSJavaLattice<String> skeletonLattice) {
 224     // copy nodes/edges from the parent method/class if possible
 225     SSJavaLattice<String> lattice = skeletonLattice.clone();
 226
 227     Descriptor parentDesc = getParent(desc);
 228     if (parentDesc != null) {
 229       SSJavaLattice<String> parentLattice = infer.getLattice(parentDesc);
 230
 231       Map<String, Set<String>> parentMap = parentLattice.getTable();
 232       Set<String> parentKeySet = parentMap.keySet();
 233       for (Iterator iterator = parentKeySet.iterator(); iterator.hasNext();) {
 234         String parentKey = (String) iterator.next();
 235         Set<String> parentValueSet = parentMap.get(parentKey);
 236         for (Iterator iterator2 = parentValueSet.iterator(); iterator2.hasNext();) {
 237           String value = (String) iterator2.next();
 238           lattice.put(parentKey, value);
 239         }
 240       }
 241
 242       Set<String> parentSharedLocSet = parentLattice.getSharedLocSet();
 243       for (Iterator iterator = parentSharedLocSet.iterator(); iterator.hasNext();) {
 244         String parentSharedLoc = (String) iterator.next();
 245         lattice.addSharedLoc(parentSharedLoc);
 246       }
 247     }
 248
 249     // ////
 250
 251     // perform DFS that starts from each skeleton/combination node and ends by another
 252     // skeleton/combination node
 253
 254     mapSharedNodeToTripleItem.clear();
 255
 256     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 257     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 258     LocationSummary locSummary = infer.getLocationSummary(desc);
 259
 260     Set<HNode> visited = new HashSet<HNode>();
 261
 262     Set<HNode> nodeSet = simpleGraph.getNodeSet();
 263
 264     Map<TripleItem, String> mapIntermediateLoc = getIntermediateLocMap(desc);
 265     // Map<TripleItem, String> mapIntermediateLoc = new HashMap<TripleItem, String>();
 266
 267     // System.out.println("*insert=" + desc);
 268     // System.out.println("***nodeSet=" + nodeSet);
 269     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 270       HNode node = (HNode) iterator.next();
 271       System.out.println("node=" + node);
 272
 273       if (node.isSkeleton() && (!visited.contains(node))) {
 274         visited.add(node);
 275
 276         Set<HNode> outSet = simpleGraph.getOutgoingNodeSet(node);
 277         for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 278           HNode outNode = (HNode) iterator2.next();
 279
 280           if (!outNode.isSkeleton()) {
 281             if (outNode.isCombinationNode()) {
 282               if (visited.containsAll(simpleGraph.getIncomingNodeSet(outNode))) {
 283                 // if (needToExpandCombinationNode(desc, outNode)) {
 284                 expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary,
 285                     outNode);
 286                 // }
 287               }
 288             } else {
 289               // we have a node that is neither combination or skeleton node
 290               // System.out.println("%%%skeleton node=" + node + "  outNode=" + outNode);
 291               HNode startNode = scGraph.getCurrentHNode(node);
 292
 293               // if (node.getDescriptor() != null) {
 294               // // node is a skeleton node and it might be merged into another node in the SC
 295               // graph.
 296               // startNode = scGraph.getHNode(node.getDescriptor());
 297               // } else {
 298               // // this node has already been merged before the SC graph.
 299               // startNode = node;
 300               // }
 301
 302               // TODO
 303               // Set<HNode> endNodeSetFromSimpleGraph =
 304               // simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null);
 305               // Set<HNode> endCombNodeSet = new HashSet<HNode>();
 306               // for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator();
 307               // iterator3.hasNext();) {
 308               // HNode endNode = (HNode) iterator3.next();
 309               // endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 310               // }
 311
 312               Set<HNode> endCombNodeSet = scGraph.getOutgoingNodeSet(startNode);
 313
 314               // System.out.println("endCombNodeSet=" + endCombNodeSet);
 315               visited.add(outNode);
 316               if (endCombNodeSet.size() > 0) {
 317                 // follows the straight line up to another skeleton/combination node
 318                 endCombNodeSet = removeTransitivelyReachToNode(desc, startNode, endCombNodeSet);
 319               } else if (endCombNodeSet.size() == 0) {
 320                 // the outNode is (directly/transitively) connected to the bottom node
 321                 // therefore, we just add a dummy bottom HNode to the endCombNodeSet.
 322                 endCombNodeSet.add(LocationInference.BOTTOMHNODE);
 323               }
 324
 325               recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited,
 326                   mapIntermediateLoc, 1, locSummary, outNode);
 327             }
 328
 329           }
 330
 331         }
 332       } else if (!node.isSkeleton() && !node.isCombinationNode() && !node.isMergeNode()
 333           && !visited.contains(node)) {
 334
 335         System.out.println("n=" + node);
 336
 337         // an intermediate node 'node' may be located between "TOP" location and a skeleton node
 338         if (simpleGraph.getIncomingNodeSet(node).size() == 0) {
 339
 340           // this node will be directly connected to the TOP location
 341           // start adding the following nodes from this node
 342
 343           Set<HNode> endNodeSetFromSimpleGraph =
 344               simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(node, null);
 345
 346           Set<HNode> endCombNodeSet = new HashSet<HNode>();
 347           for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 348             HNode endNode = (HNode) iterator3.next();
 349             endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 350           }
 351
 352           System.out.println("endCombNodeSet=" + endCombNodeSet);
 353           HNode startNode = LocationInference.TOPHNODE;
 354           visited.add(startNode);
 355           if (endCombNodeSet.size() > 0) {
 356             // follows the straight line up to another skeleton/combination node
 357             // endCombNodeSet = removeTransitivelyReachToNode(desc, node, endCombNodeSet);
 358             recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited,
 359                 mapIntermediateLoc, 1, locSummary, node);
 360           }
 361
 362         }
 363
 364       }
 365     }
 366
 367     // add shared locations
 368     Set<HNode> sharedNodeSet = mapSharedNodeToTripleItem.keySet();
 369     for (Iterator iterator = sharedNodeSet.iterator(); iterator.hasNext();) {
 370       HNode sharedNode = (HNode) iterator.next();
 371       TripleItem item = mapSharedNodeToTripleItem.get(sharedNode);
 372       String nonSharedLocName = mapIntermediateLoc.get(item);
 373
 374       System.out.println("sharedNode=" + sharedNode + "    locName=" + nonSharedLocName);
 375
 376       String newLocName;
 377       if (locSummary.getHNodeNameSetByLatticeLoationName(nonSharedLocName) != null
 378           && !lattice.isSharedLoc(nonSharedLocName)) {
 379         // need to generate a new shared location in the lattice, which is one level lower than the
 380         // 'locName' location
 381         newLocName = "ILOC" + (LocationInference.locSeed++);
 382
 383         // Set<String> aboveElementSet = getAboveElementSet(lattice, locName);
 384         Set<String> belowElementSet = new HashSet<String>();
 385         belowElementSet.addAll(lattice.get(nonSharedLocName));
 386
 387         System.out.println("nonSharedLocName=" + nonSharedLocName + "   belowElementSet="
 388             + belowElementSet + "  newLocName=" + newLocName);
 389
 390         lattice.insertNewLocationBetween(nonSharedLocName, belowElementSet, newLocName);
 391       } else {
 392         newLocName = nonSharedLocName;
 393       }
 394
 395       lattice.addSharedLoc(newLocName);
 396       HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc);
 397       Set<Descriptor> descSet = graph.getDescSetOfNode(sharedNode);
 398       for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) {
 399         Descriptor d = (Descriptor) iterator2.next();
 400         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), newLocName);
 401       }
 402       locSummary.addMapHNodeNameToLocationName(sharedNode.getName(), newLocName);
 403
 404     }
 405
 406     return lattice;
 407
 408   }
 409
 410   private Set<String> getAboveElementSet(SSJavaLattice<String> lattice, String loc) {
 411
 412     Set<String> aboveSet = new HashSet<String>();
 413
 414     Map<String, Set<String>> latticeMap = lattice.getTable();
 415     Set<String> keySet = latticeMap.keySet();
 416     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 417       String key = (String) iterator.next();
 418       if (latticeMap.get(key).contains(loc)) {
 419         aboveSet.add(key);
 420       }
 421     }
 422
 423     return aboveSet;
 424   }
 425
 426   private boolean needToExpandCombinationNode(Descriptor desc, HNode cnode) {
 427
 428     System.out.println("needToExpandCombinationNode?=" + cnode);
 429
 430     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 431     // HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
 432     Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
 433     Set<HNode> combinationNodeSetInSimpleGraph =
 434         simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
 435     System.out.println("---combinationNodeSetInSimpleGraph=" + combinationNodeSetInSimpleGraph);
 436     Set<HNode> inNodeSetToCNode = simpleGraph.getIncomingNodeSet(cnode);
 437     System.out.println("------inNodeSetToCNode=" + inNodeSetToCNode);
 438     for (Iterator iterator = combinationNodeSetInSimpleGraph.iterator(); iterator.hasNext();) {
 439       HNode nodeBelongToTheSameCombinationNode = (HNode) iterator.next();
 440       if (inNodeSetToCNode.contains(nodeBelongToTheSameCombinationNode)) {
 441         // the combination node 'cnode' is not the highest location among the same combination node
 442         return false;
 443       }
 444     }
 445
 446     return true;
 447   }
 448
 449   private void expandCombinationNode(Descriptor desc, SSJavaLattice<String> lattice,
 450       Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc, LocationSummary locSummary,
 451       HNode cnode) {
 452
 453     // expand the combination node 'outNode'
 454     // here we need to expand the corresponding combination location in the lattice
 455     HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
 456
 457     System.out.println("expandCombinationNode=" + cnode + "  cnode in scgraph="
 458         + combinationNodeInSCGraph);
 459
 460     if (combinationNodeInSCGraph == null) {
 461       return;
 462     }
 463
 464     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 465     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 466
 467     Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
 468
 469     // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet);
 470
 471     Set<HNode> combinationNodeSet =
 472         simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
 473
 474     // System.out.println("combinationNodeSet=" + combinationNodeSet);
 475
 476     // TODO
 477     // Set<HNode> endNodeSetFromSimpleGraph =
 478     // simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(cnode, combinationNodeSet);
 479     // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 480     // Set<HNode> endCombNodeSet = new HashSet<HNode>();
 481     // for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 482     // HNode endNode = (HNode) iterator3.next();
 483     // endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 484     // }
 485
 486     Set<HNode> endCombNodeSet = scGraph.getOutgoingNodeSet(combinationNodeInSCGraph);
 487     visited.add(cnode);
 488
 489     // follows the straight line up to another skeleton/combination node
 490     if (endCombNodeSet.size() > 0) {
 491       // System.out.println("---endCombNodeSet=" + endCombNodeSet);
 492       endCombNodeSet =
 493           removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet);
 494
 495       recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
 496           mapIntermediateLoc, 1, locSummary, cnode);
 497     } else {
 498       endCombNodeSet.add(LocationInference.BOTTOMHNODE);
 499       // System.out.println("---endCombNodeSet is zero");
 500       // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 501       // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode));
 502       recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
 503           mapIntermediateLoc, 1, locSummary, cnode);
 504
 505     }
 506
 507   }
 508
 509   private Set<HNode> removeTransitivelyReachToNode(Descriptor desc, HNode startNode,
 510       Set<HNode> endNodeSet) {
 511
 512     // if an end node is not directly connected to the start node in the SC graph
 513     // replace it with a directly connected one which transitively reaches to it.
 514
 515     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 516
 517     Set<HNode> newEndNodeSet = new HashSet<HNode>();
 518     for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 519       HNode endNode = (HNode) iterator.next();
 520       if (scGraph.isDirectlyConnectedTo(startNode, endNode)) {
 521         newEndNodeSet.add(endNode);
 522       } else {
 523         HNode newEndNode =
 524             getDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode);
 525         // System.out.println("#### old END NODE=" + endNode + " --->" + newEndNode);
 526         newEndNodeSet.add(newEndNode);
 527       }
 528     }
 529
 530     // System.out.println("removeTransitivelyReachToNode=" + endNodeSet + "  newSet=" +
 531     // newEndNodeSet);
 532
 533     return newEndNodeSet;
 534
 535   }
 536
 537   private HNode getDirectlyReachableSCNodeFromEndNode(HierarchyGraph scGraph, HNode startNode,
 538       Set<HNode> endNodeSet) {
 539
 540     // System.out.println("getDirectlyReachableSCNodeFromEndNode start=" + startNode +
 541     // " endNodeSet="
 542     // + endNodeSet);
 543     Set<HNode> newStartNodeSet = new HashSet<HNode>();
 544
 545     for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 546       HNode endNode = (HNode) iterator.next();
 547       Set<HNode> connectedToEndNodeSet = scGraph.getIncomingNodeSet(endNode);
 548
 549       for (Iterator iterator2 = connectedToEndNodeSet.iterator(); iterator2.hasNext();) {
 550         HNode curNode = (HNode) iterator2.next();
 551         if (recurConnectedFromStartNode(scGraph, startNode, curNode, new HashSet<HNode>())) {
 552           newStartNodeSet.add(curNode);
 553         }
 554       }
 555     }
 556
 557     // System.out.println("newStartNodeSet=" + newStartNodeSet);
 558
 559     if (newStartNodeSet.size() == 0) {
 560       newStartNodeSet.add(startNode);
 561     }
 562
 563     return newStartNodeSet.iterator().next();
 564   }
 565
 566   private boolean recurConnectedFromStartNode(HierarchyGraph scGraph, HNode startNode,
 567       HNode curNode, Set<HNode> visited) {
 568     // return true if curNode is transitively connected from the startNode
 569
 570     boolean isConnected = false;
 571     Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
 572     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 573       HNode in = (HNode) iterator.next();
 574       if (in.equals(startNode)) {
 575         return true;
 576       } else {
 577         visited.add(in);
 578         isConnected |= recurConnectedFromStartNode(scGraph, startNode, in, visited);
 579       }
 580     }
 581
 582     return isConnected;
 583   }
 584
 585   private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 586       HNode startNode, HNode endNode) {
 587     // System.out.println("getDirectlyReachableNodeFromStartNodeReachToEndNode start=" + startNode
 588     // + " end=" + endNode);
 589     Set<HNode> connected = new HashSet<HNode>();
 590     recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode, connected);
 591     if (connected.size() == 0) {
 592       connected.add(endNode);
 593     }
 594     // System.out.println("connected=" + connected);
 595
 596     return connected.iterator().next();
 597   }
 598
 599   private void recurDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 600       HNode startNode, HNode curNode, Set<HNode> connected) {
 601
 602     Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
 603     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 604       HNode inNode = (HNode) iterator.next();
 605       if (inNode.equals(startNode)) {
 606         connected.add(curNode);
 607       } else {
 608         recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected);
 609       }
 610     }
 611
 612   }
 613
 614   private void recurDFSNormalNode(Descriptor desc, SSJavaLattice<String> lattice, HNode startNode,
 615       Set<HNode> endNodeSet, Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc,
 616       int idx, LocationSummary locSummary, HNode curNode) {
 617
 618     TripleItem item = new TripleItem(startNode, endNodeSet, idx);
 619     if (!mapIntermediateLoc.containsKey(item)) {
 620       // need to create a new intermediate location in the lattice
 621       String newLocName = "ILOC" + (LocationInference.locSeed++);
 622       String above;
 623       if (idx == 1) {
 624         above = startNode.getName();
 625       } else {
 626         int prevIdx = idx - 1;
 627         TripleItem prevItem = new TripleItem(startNode, endNodeSet, prevIdx);
 628         above = mapIntermediateLoc.get(prevItem);
 629       }
 630
 631       Set<String> belowSet = new HashSet<String>();
 632       for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 633         HNode endNode = (HNode) iterator.next();
 634         String locName;
 635         if (locSummary.getMapHNodeNameToLocationName().containsKey(endNode.getName())) {
 636           locName = locSummary.getLocationName(endNode.getName());
 637         } else {
 638           locName = endNode.getName();
 639         }
 640         belowSet.add(locName);
 641       }
 642       lattice.insertNewLocationBetween(above, belowSet, newLocName);
 643
 644       mapIntermediateLoc.put(item, newLocName);
 645     }
 646
 647     String locName = mapIntermediateLoc.get(item);
 648     HierarchyGraph simpleHierarchyGraph = infer.getSimpleHierarchyGraph(desc);
 649
 650     if (curNode.isSharedNode()) {
 651       // if the current node is shared location, add a shared location to the lattice later
 652       System.out.println("###SHARED ITEM=" + item);
 653       mapSharedNodeToTripleItem.put(curNode, item);
 654     } else {
 655       Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
 656       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 657         Descriptor d = (Descriptor) iterator.next();
 658         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 659       }
 660       locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
 661     }
 662
 663     System.out.println("-TripleItem normal=" + item);
 664     System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
 665         + " locName=" + locName + "  isC=" + curNode.isCombinationNode());
 666
 667     Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
 668     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 669       HNode outNode = (HNode) iterator2.next();
 670
 671       Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
 672       System.out.println("outNode=" + outNode);
 673       System.out.println("---incomingHNodeSetToOutNode=" + incomingHNodeSetToOutNode);
 674
 675       if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) {
 676         Pair<HNode, HNode> pair = new Pair(startNode, outNode);
 677         if (visited.containsAll(simpleHierarchyGraph.getIncomingNodeSet(outNode))) {
 678           visited.add(outNode);
 679           int newidx = getCurrentHighestIndex(pair, idx + 1);
 680           // int newidx = getCurrentHighestIndex(outNode, idx + 1);
 681           recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
 682               newidx, locSummary, outNode);
 683           // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
 684           // idx + 1, locSummary, outNode);
 685         } else {
 686           updateHighestIndex(pair, idx + 1);
 687           // updateHighestIndex(outNode, idx + 1);
 688           System.out.println("NOT RECUR");
 689         }
 690       } else if (!outNode.isSkeleton() && outNode.isCombinationNode() && !visited.contains(outNode)) {
 691         if (needToExpandCombinationNode(desc, outNode)) {
 692           System.out.println("NEED TO");
 693           expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
 694         } else {
 695           System.out.println("NOT NEED TO");
 696         }
 697       }
 698
 699     }
 700
 701   }
 702
 703   private void recurDFS(Descriptor desc, SSJavaLattice<String> lattice,
 704       HNode combinationNodeInSCGraph, Set<HNode> endNodeSet, Set<HNode> visited,
 705       Map<TripleItem, String> mapIntermediateLoc, int idx, LocationSummary locSummary, HNode curNode) {
 706
 707     TripleItem item = new TripleItem(combinationNodeInSCGraph, endNodeSet, idx);
 708
 709     if (!mapIntermediateLoc.containsKey(item)) {
 710       // need to create a new intermediate location in the lattice
 711       String above;
 712       if (idx == 1) {
 713         String newLocName = combinationNodeInSCGraph.getName();
 714         mapIntermediateLoc.put(item, newLocName);
 715       } else {
 716         String newLocName = "ILOC" + (LocationInference.locSeed++);
 717         int prevIdx = idx - 1;
 718         TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx);
 719         above = mapIntermediateLoc.get(prevItem);
 720
 721         Set<String> belowSet = new HashSet<String>();
 722         for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 723           HNode endNode = (HNode) iterator.next();
 724           belowSet.add(endNode.getName());
 725         }
 726         lattice.insertNewLocationBetween(above, belowSet, newLocName);
 727         mapIntermediateLoc.put(item, newLocName);
 728       }
 729
 730     }
 731
 732     // TODO
 733     // Do we need to skip the combination node and assign a shared location to the next node?
 734     // if (idx == 1 && curNode.isSharedNode()) {
 735     // System.out.println("THE FIRST COMBINATION NODE EXPANSION IS SHARED!");
 736     // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited, mapIntermediateLoc,
 737     // idx + 1, locSummary, curNode);
 738     // return;
 739     // }
 740
 741     HierarchyGraph simpleHierarchyGraph = infer.getSimpleHierarchyGraph(desc);
 742     String locName = mapIntermediateLoc.get(item);
 743     if (curNode.isSharedNode()) {
 744       // if the current node is shared location, add a shared location to the lattice later
 745       System.out.println("###SHARED ITEM=" + item);
 746       mapSharedNodeToTripleItem.put(curNode, item);
 747     } else {
 748       Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
 749       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 750         Descriptor d = (Descriptor) iterator.next();
 751         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 752       }
 753       locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
 754     }
 755
 756     System.out.println("-TripleItem=" + item);
 757     System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
 758         + " locName=" + locName);
 759
 760     Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
 761     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 762       HNode outNode = (HNode) iterator2.next();
 763       System.out.println("---recurDFS outNode=" + outNode);
 764       System.out.println("---cur combinationNodeInSCGraph=" + combinationNodeInSCGraph);
 765       System.out.println("---outNode combinationNodeInSCGraph="
 766           + getCombinationNodeInSCGraph(desc, outNode));
 767
 768       if (!outNode.isSkeleton() && !visited.contains(outNode)) {
 769         if (outNode.isCombinationNode()) {
 770
 771           Set<HNode> combineSkeletonNodeSet =
 772               simpleHierarchyGraph.getCombineSetByCombinationNode(outNode);
 773           Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
 774           // extract nodes belong to the same combine node
 775           Set<HNode> incomingCombinedHNodeSet = new HashSet<HNode>();
 776           for (Iterator iterator = incomingHNodeSetToOutNode.iterator(); iterator.hasNext();) {
 777             HNode inNode = (HNode) iterator.next();
 778             if (combineSkeletonNodeSet.contains(inNode)) {
 779               incomingCombinedHNodeSet.add(inNode);
 780             }
 781           }
 782           System.out.println("-----incomingCombinedHNodeSet=" + incomingCombinedHNodeSet);
 783
 784           // check whether the next combination node is different from the current node
 785           if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) {
 786             Pair<HNode, HNode> pair = new Pair(combinationNodeInSCGraph, outNode);
 787             if (visited.containsAll(incomingCombinedHNodeSet)) {
 788               visited.add(outNode);
 789               System.out.println("-------curIdx=" + (idx + 1));
 790
 791               int newIdx = getCurrentHighestIndex(pair, idx + 1);
 792               // int newIdx = getCurrentHighestIndex(outNode, idx + 1);
 793               System.out.println("-------newIdx=" + newIdx);
 794               recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
 795                   mapIntermediateLoc, newIdx, locSummary, outNode);
 796               // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
 797               // mapIntermediateLoc, idx + 1, locSummary, outNode);
 798             } else {
 799               updateHighestIndex(pair, idx + 1);
 800               // updateHighestIndex(outNode, idx + 1);
 801               System.out.println("-----NOT RECUR!");
 802             }
 803           } else {
 804             if (needToExpandCombinationNode(desc, outNode)) {
 805               System.out.println("NEED TO");
 806               expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
 807             } else {
 808               System.out.println("NOT NEED TO");
 809             }
 810
 811           }
 812         }
 813       }
 814       // }
 815
 816     }
 817
 818   }
 819
 820   private int getCurrentHighestIndex(Pair<HNode, HNode> pair, int curIdx) {
 821     int recordedIdx = getCurrentHighestIndex(pair);
 822     if (recordedIdx > curIdx) {
 823       return recordedIdx;
 824     } else {
 825       return curIdx;
 826     }
 827   }
 828
 829   private int getCurrentHighestIndex(HNode node, int curIdx) {
 830     int recordedIdx = getCurrentHighestIndex(node);
 831     if (recordedIdx > curIdx) {
 832       return recordedIdx;
 833     } else {
 834       return curIdx;
 835     }
 836   }
 837
 838   private int getCurrentHighestIndex(Pair<HNode, HNode> pair) {
 839     if (!mapItemToHighestIndex.containsKey(pair)) {
 840       mapItemToHighestIndex.put(pair, new Integer(-1));
 841     }
 842     return mapItemToHighestIndex.get(pair).intValue();
 843   }
 844
 845   private void updateHighestIndex(Pair<HNode, HNode> pair, int idx) {
 846     if (idx > getCurrentHighestIndex(pair)) {
 847       mapItemToHighestIndex.put(pair, new Integer(idx));
 848     }
 849   }
 850
 851   private int getCurrentHighestIndex(HNode node) {
 852     if (!mapHNodeToHighestIndex.containsKey(node)) {
 853       mapHNodeToHighestIndex.put(node, new Integer(-1));
 854     }
 855     return mapHNodeToHighestIndex.get(node).intValue();
 856   }
 857
 858   private void updateHighestIndex(HNode node, int idx) {
 859     if (idx > getCurrentHighestIndex(node)) {
 860       mapHNodeToHighestIndex.put(node, new Integer(idx));
 861     }
 862   }
 863
 864   private String generateElementName(BasisSet basisSet, HierarchyGraph inputGraph,
 865       Map<Set<Integer>, String> mapF2LocName, Set<Integer> F) {
 866
 867     if (mapF2LocName.containsKey(F)) {
 868       return mapF2LocName.get(F);
 869     }
 870
 871     HNode node = basisSet.getHNode(F);
 872     if (node != null) {
 873       mapF2LocName.put(F, node.getName());
 874       return node.getName();
 875     } else {
 876       if (inputGraph.BASISTOPELEMENT.equals(F)) {
 877         return SSJavaAnalysis.BOTTOM;
 878       } else {
 879         String str = "LOC" + (LocationInference.locSeed++);
 880         mapF2LocName.put(F, str);
 881         return str;
 882       }
 883     }
 884   }
 885
 886   private void resetCount(Map<Set<Integer>, Integer> mapFtoCount, Family family) {
 887     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
 888       Set<Integer> F = iter.next();
 889       mapFtoCount.put(F, 0);
 890     }
 891   }
 892
 893   private Map<Set<Integer>, Set<Set<Integer>>> coveringGraph(BasisSet basisSet, Family family) {
 894
 895     Map<Set<Integer>, Integer> mapFtoCount = new HashMap<Set<Integer>, Integer>();
 896     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = new HashMap<Set<Integer>, Set<Set<Integer>>>();
 897
 898     // initialize COUNT(F) to 0 for all elements of the family
 899     resetCount(mapFtoCount, family);
 900
 901     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
 902       Set<Integer> F = iter.next();
 903       Set<HNode> gammaF = family.getGamma(F);
 904
 905       Set<HNode> curHNodeSet = basisSet.getHNodeSet();
 906       curHNodeSet.removeAll(gammaF);
 907       Set<Set<Integer>> Bset = basisSet.getBasisSetByHNodeSet(curHNodeSet);
 908
 909       for (Iterator iterator = Bset.iterator(); iterator.hasNext();) {
 910         Set<Integer> B = (Set<Integer>) iterator.next();
 911
 912         Set<Integer> Fprime = new HashSet<Integer>();
 913         Fprime.addAll(F);
 914         Fprime.addAll(B);
 915
 916         // COUNT(F')++;
 917         mapFtoCount.put(Fprime, mapFtoCount.get(Fprime) + 1);
 918
 919         // if |gamma(F')|==COUNT(F') + |gamma(F)|
 920         int numGammaFprime = family.getGamma(Fprime).size();
 921         int countFprime = mapFtoCount.get(Fprime);
 922         int numGammaF = family.getGamma(F).size();
 923         if (numGammaFprime == (countFprime + numGammaF)) {
 924           // ImSucc(F)=IMSucc(F) union F'
 925           addImSucc(mapImSucc, F, Fprime);
 926         }
 927
 928       }
 929       resetCount(mapFtoCount, family);
 930     }
 931
 932     // System.out.println("mapImSucc=" + mapImSucc);
 933
 934     return mapImSucc;
 935   }
 936
 937   private Set<Set<Integer>> getImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F) {
 938     if (!mapImSucc.containsKey(F)) {
 939       mapImSucc.put(F, new HashSet<Set<Integer>>());
 940     }
 941     return mapImSucc.get(F);
 942   }
 943
 944   private void addImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F,
 945       Set<Integer> Fprime) {
 946
 947     if (!mapImSucc.containsKey(F)) {
 948       mapImSucc.put(F, new HashSet<Set<Integer>>());
 949     }
 950
 951     mapImSucc.get(F).add(Fprime);
 952
 953   }
 954
 955   private Family generateFamily(BasisSet basisSet) {
 956
 957     Family family = new Family();
 958
 959     for (Iterator<Set<Integer>> iterator = basisSet.basisIterator(); iterator.hasNext();) {
 960       Set<Integer> B = iterator.next();
 961
 962       Set<Pair<Set<Integer>, Set<HNode>>> tobeadded = new HashSet<Pair<Set<Integer>, Set<HNode>>>();
 963
 964       for (Iterator<Set<Integer>> iterator2 = family.FIterator(); iterator2.hasNext();) {
 965         Set<Integer> F = iterator2.next();
 966
 967         Set<Integer> Fprime = new HashSet<Integer>();
 968         Fprime.addAll(F);
 969         Fprime.addAll(B);
 970
 971         Set<HNode> gammaFPrimeSet = new HashSet<HNode>();
 972         gammaFPrimeSet.addAll(family.getGamma(F));
 973         gammaFPrimeSet.add(basisSet.getHNode(B));
 974
 975         if (!family.containsF(Fprime)) {
 976           Pair<Set<Integer>, Set<HNode>> pair =
 977               new Pair<Set<Integer>, Set<HNode>>(Fprime, gammaFPrimeSet);
 978           tobeadded.add(pair);
 979         } else {
 980           family.updateGammaF(Fprime, gammaFPrimeSet);
 981         }
 982       }
 983
 984       for (Iterator<Pair<Set<Integer>, Set<HNode>>> iterator2 = tobeadded.iterator(); iterator2
 985           .hasNext();) {
 986         Pair<Set<Integer>, Set<HNode>> pair = iterator2.next();
 987         family.addFElement(pair.getFirst());
 988         family.updateGammaF(pair.getFirst(), pair.getSecond());
 989       }
 990
 991     }
 992     return family;
 993   }
 994
 995   private void debug_print(HierarchyGraph inputGraph) {
 996     System.out.println("\nBuild Lattice:" + inputGraph.getName());
 997     System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex());
 998     System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis());
 999   }
1000
1001 }
1002
1003 class Identifier {
1004   public HNode node;
1005   public int idx;
1006
1007   public Identifier(HNode n, int i) {
1008     node = n;
1009     idx = i;
1010   }
1011
1012   public int hashCode() {
1013     return node.hashCode() + idx;
1014   }
1015
1016   public boolean equals(Object obj) {
1017
1018     if (obj instanceof Identifier) {
1019       Identifier in = (Identifier) obj;
1020       if (node.equals(in.node) && idx == in.idx) {
1021         return true;
1022       }
1023     }
1024
1025     return false;
1026   }
1027
1028 }
1029
1030 class TripleItem {
1031   public HNode higherNode;
1032   public Set<HNode> lowerNodeSet;
1033   public int idx;
1034   public boolean isShared;
1035
1036   public TripleItem(HNode h, Set<HNode> l, int i) {
1037     higherNode = h;
1038     lowerNodeSet = l;
1039     idx = i;
1040     isShared = false;
1041   }
1042
1043   public void setShared(boolean in) {
1044     this.isShared = in;
1045   }
1046
1047   public boolean isShared() {
1048     return isShared;
1049   }
1050
1051   public int hashCode() {
1052
1053     int h = 0;
1054     if (higherNode != null) {
1055       h = higherNode.hashCode();
1056     }
1057
1058     if (isShared) {
1059       h++;
1060     }
1061
1062     return h + lowerNodeSet.hashCode() + idx;
1063   }
1064
1065   public boolean equals(Object obj) {
1066
1067     if (obj instanceof TripleItem) {
1068       TripleItem in = (TripleItem) obj;
1069       if ((higherNode == null || (higherNode != null && higherNode.equals(in.higherNode)))
1070           && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx && isShared == in.isShared()) {
1071         return true;
1072       }
1073     }
1074
1075     return false;
1076   }
1077
1078   public String toString() {
1079     String rtr = higherNode + "-" + idx + "->" + lowerNodeSet;
1080     if (isShared) {
1081       rtr += " S";
1082     }
1083     return rtr;
1084   }
1085 }