1 package Analysis.SSJava;
3 import java.util.HashMap;
4 import java.util.HashSet;
5 import java.util.Iterator;
6 import java.util.LinkedList;
9 import java.util.Stack;
11 import IR.ClassDescriptor;
13 import IR.MethodDescriptor;
14 import IR.NameDescriptor;
17 public class BuildLattice {
19 private LocationInference infer;
20 private Map<HNode, TripleItem> mapSharedNodeToTripleItem;
21 private Map<HNode, Integer> mapHNodeToHighestIndex;
23 private Map<Descriptor, Map<TripleItem, String>> mapDescToIntermediateLocMap;
25 private Map<Descriptor, Map<InterLocItem, String>> mapDescToInterLocMap;
27 private Map<Pair<HNode, HNode>, Integer> mapItemToHighestIndex;
29 private Map<SSJavaLattice<String>, Set<String>> mapLatticeToLocalLocSet;
31 private Map<Descriptor, Map<LineIdentifier, LinkedList<LocPair>>> mapDescToLineListMap;
33 public BuildLattice(LocationInference infer) {
35 this.mapSharedNodeToTripleItem = new HashMap<HNode, TripleItem>();
36 this.mapHNodeToHighestIndex = new HashMap<HNode, Integer>();
37 this.mapItemToHighestIndex = new HashMap<Pair<HNode, HNode>, Integer>();
38 this.mapDescToIntermediateLocMap = new HashMap<Descriptor, Map<TripleItem, String>>();
39 this.mapLatticeToLocalLocSet = new HashMap<SSJavaLattice<String>, Set<String>>();
40 this.mapDescToInterLocMap = new HashMap<Descriptor, Map<InterLocItem, String>>();
41 this.mapDescToLineListMap = new HashMap<Descriptor, Map<LineIdentifier, LinkedList<LocPair>>>();
44 public SSJavaLattice<String> buildLattice(Descriptor desc) {
46 HierarchyGraph inputGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
47 LocationSummary locSummary = infer.getLocationSummary(desc);
49 HierarchyGraph naiveGraph = infer.getSimpleHierarchyGraph(desc);
51 // I don't think we need to keep the below if statement anymore
52 // because hierarchy graph does not have any composite location
53 Set<HNode> nodeSetWithCompositeLocation = new HashSet<HNode>();
54 if (desc instanceof MethodDescriptor) {
55 FlowGraph flowGraph = infer.getFlowGraph((MethodDescriptor) desc);
57 for (Iterator iterator = inputGraph.getNodeSet().iterator(); iterator.hasNext();) {
58 HNode hnode = (HNode) iterator.next();
59 Descriptor hnodeDesc = hnode.getDescriptor();
60 if (hnodeDesc != null) {
61 NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
62 descTuple.add(hnodeDesc);
64 if (flowGraph.contains(descTuple)) {
65 FlowNode flowNode = flowGraph.getFlowNode(descTuple);
66 if (flowNode.getCompositeLocation() != null) {
67 nodeSetWithCompositeLocation.add(hnode);
76 // /////////////////////////////////////////////////////////////////////////////////////
77 // lattice generation for the native approach
79 if (infer.state.SSJAVA_INFER_NAIVE_WRITEDOTS) {
80 BasisSet naiveBasisSet = naiveGraph.computeBasisSet(nodeSetWithCompositeLocation);
82 Family naiveFamily = generateFamily(naiveBasisSet);
83 Map<Set<Integer>, Set<Set<Integer>>> naive_mapImSucc =
84 coveringGraph(naiveBasisSet, naiveFamily);
86 SSJavaLattice<String> naive_lattice =
87 buildLattice(desc, naiveBasisSet, naiveGraph, null, naive_mapImSucc);
88 LocationInference.numLocationsNaive += naive_lattice.getKeySet().size();
89 infer.addNaiveLattice(desc, naive_lattice);
92 // /////////////////////////////////////////////////////////////////////////////////////
94 // lattice generation for the proposed approach
95 BasisSet basisSet = inputGraph.computeBasisSet(nodeSetWithCompositeLocation);
96 // debug_print(inputGraph);
98 Family family = generateFamily(basisSet);
99 Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = coveringGraph(basisSet, family);
101 SSJavaLattice<String> lattice = buildLattice(desc, basisSet, inputGraph, locSummary, mapImSucc);
106 public void setIntermediateLocMap(Descriptor desc, Map<TripleItem, String> map) {
107 mapDescToIntermediateLocMap.put(desc, map);
110 public Map<TripleItem, String> getIntermediateLocMap(Descriptor desc) {
111 if (!mapDescToIntermediateLocMap.containsKey(desc)) {
112 mapDescToIntermediateLocMap.put(desc, new HashMap<TripleItem, String>());
114 return mapDescToIntermediateLocMap.get(desc);
117 private Descriptor getParent(Descriptor desc) {
118 if (desc instanceof MethodDescriptor) {
119 MethodDescriptor md = (MethodDescriptor) desc;
120 ClassDescriptor cd = md.getClassDesc();
121 return infer.getParentMethodDesc(cd, md);
123 return ((ClassDescriptor) desc).getSuperDesc();
127 private SSJavaLattice<String> buildLattice(Descriptor desc, BasisSet basisSet,
128 HierarchyGraph inputGraph, LocationSummary locSummary,
129 Map<Set<Integer>, Set<Set<Integer>>> mapImSucc) {
131 System.out.println("\nBuild Lattice:" + inputGraph.getName());
133 SSJavaLattice<String> lattice =
134 new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
136 Map<Set<Integer>, String> mapFToLocName = new HashMap<Set<Integer>, String>();
138 Set<Set<Integer>> keySet = mapImSucc.keySet();
139 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
140 Set<Integer> higher = (Set<Integer>) iterator.next();
142 String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher);
144 HNode higherNode = inputGraph.getHNode(higherName);
146 if (higherNode == null) {
147 NameDescriptor d = new NameDescriptor(higherName);
148 higherNode = inputGraph.getHNode(d);
149 higherNode.setSkeleton(true);
152 if (higherNode != null && higherNode.isSharedNode()) {
153 lattice.addSharedLoc(higherName);
155 Set<Descriptor> descSet = inputGraph.getDescSetOfNode(higherNode);
156 // System.out.println("higherName=" + higherName + " higherNode=" + higherNode + " descSet="
159 if (locSummary != null) {
160 for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) {
161 Descriptor d = (Descriptor) iterator2.next();
162 locSummary.addMapHNodeNameToLocationName(d.getSymbol(), higherName);
166 // locSummary.addMapHNodeNameToLocationName(higherName, higherName);
168 Set<Set<Integer>> lowerSet = mapImSucc.get(higher);
169 for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
170 Set<Integer> lower = (Set<Integer>) iterator2.next();
172 String lowerName = generateElementName(basisSet, inputGraph, mapFToLocName, lower);
173 HNode lowerNode = inputGraph.getHNode(lowerName);
175 if (lowerNode == null && !lowerName.equals(SSJavaAnalysis.BOTTOM)) {
176 NameDescriptor d = new NameDescriptor(lowerName);
177 lowerNode = inputGraph.getHNode(d);
178 lowerNode.setSkeleton(true);
181 if (lowerNode != null && !inputGraph.isDirectlyConnectedTo(higherNode, lowerNode)) {
182 inputGraph.addEdge(higherNode, lowerNode);
185 if (lowerNode != null && lowerNode.isSharedNode()) {
186 lattice.addSharedLoc(lowerName);
189 Set<Descriptor> lowerDescSet = inputGraph.getDescSetOfNode(lowerNode);
190 // System.out.println("lowerName=" + lowerName + " lowerNode=" + lowerNode + " descSet="
192 if (locSummary != null) {
193 for (Iterator iterator3 = lowerDescSet.iterator(); iterator3.hasNext();) {
194 Descriptor d = (Descriptor) iterator3.next();
195 locSummary.addMapHNodeNameToLocationName(d.getSymbol(), lowerName);
198 // locSummary.addMapHNodeNameToLocationName(lowerName, lowerName);
200 if (higher.size() == 0) {
202 lattice.put(lowerName);
204 lattice.addRelationHigherToLower(higherName, lowerName);
211 inputGraph.removeRedundantEdges();
215 public HNode getCombinationNodeInSCGraph(Descriptor desc, HNode nodeFromSimpleGraph) {
217 HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
219 if (nodeFromSimpleGraph.isSkeleton()) {
220 return scGraph.getCurrentHNode(nodeFromSimpleGraph);
223 Set<HNode> combineSkeletonNodeSet =
224 infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(nodeFromSimpleGraph);
225 HNode combinationNodeInSCGraph =
226 infer.getSkeletonCombinationHierarchyGraph(desc).getMapCombineNodeSetToCombinationNode()
227 .get(combineSkeletonNodeSet);
229 // Set<HNode> combineSkeletonNodeSet =
230 // infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(simpleGraphNode);
231 // HNode combinationNodeInSCGraph =
232 // infer.getSkeletonCombinationHierarchyGraph(desc).getCombinationNode(combineSkeletonNodeSet);
233 return combinationNodeInSCGraph;
236 public SSJavaLattice<String> insertIntermediateNodesToStraightLine(Descriptor desc,
237 SSJavaLattice<String> skeletonLattice) {
239 SSJavaLattice<String> lattice = skeletonLattice.clone();
240 LocationSummary locSummary = infer.getLocationSummary(desc);
242 Descriptor parentDesc = getParent(desc);
243 if (parentDesc != null) {
244 SSJavaLattice<String> parentLattice = infer.getLattice(parentDesc);
246 Map<String, Set<String>> parentMap = parentLattice.getTable();
247 Set<String> parentKeySet = parentMap.keySet();
248 for (Iterator iterator = parentKeySet.iterator(); iterator.hasNext();) {
249 String parentKey = (String) iterator.next();
250 Set<String> parentValueSet = parentMap.get(parentKey);
251 for (Iterator iterator2 = parentValueSet.iterator(); iterator2.hasNext();) {
252 String value = (String) iterator2.next();
253 lattice.put(parentKey, value);
257 Set<String> parentSharedLocSet = parentLattice.getSharedLocSet();
258 for (Iterator iterator = parentSharedLocSet.iterator(); iterator.hasNext();) {
259 String parentSharedLoc = (String) iterator.next();
260 lattice.addSharedLoc(parentSharedLoc);
264 HierarchyGraph hierarchyGraph = infer.getSimpleHierarchyGraph(desc);
265 HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
267 Set<HNode> hierarchyGraphNodeSet = hierarchyGraph.getNodeSet();
268 for (Iterator iterator = hierarchyGraphNodeSet.iterator(); iterator.hasNext();) {
269 HNode hNode = (HNode) iterator.next();
270 if (!hNode.isSkeleton()) {
271 // here we need to insert an intermediate node for the hNode
272 System.out.println("\n#local node=" + hNode);
274 // 1) find the lowest node m in the lattice that is above hnode in the lattice
275 // 2) count the number of non-shared nodes d between the hnode and the node m
276 // int numNonSharedNodes;
280 Set<HNode> combineSkeletonNodeSet = null;
281 Stack<String> trace = new Stack<String>();
282 if (hNode.isDirectCombinationNode()) {
283 // this node itself is the lowest node m. it is the first node of the chain
284 Set<HNode> combineSet = hierarchyGraph.getCombineSetByCombinationNode(hNode);
286 System.out.println(" # direct combine node::combineSkeletonNodeSet=" + combineSet);
288 SCNode = scGraph.getCombinationNode(combineSet);
289 // numNonSharedNodes = -1;
291 if (hNode.isSharedNode()) {
298 Set<HNode> aboveSet = new HashSet<HNode>();
299 if (hNode.isCombinationNode()) {
300 // the current node is a combination node
301 combineSkeletonNodeSet = hierarchyGraph.getCombineSetByCombinationNode(hNode);
302 System.out.println(" combineSkeletonNodeSet=" + combineSkeletonNodeSet
303 + " combinationNode=" + scGraph.getCombinationNode(combineSkeletonNodeSet));
305 scGraph.getCombinationNode(combineSkeletonNodeSet);
307 System.out.println(" firstnodeOfSimpleGraph="
308 + hierarchyGraph.getFirstNodeOfCombinationNodeChainSet(combineSkeletonNodeSet));
309 aboveSet.addAll(hierarchyGraph
310 .getFirstNodeOfCombinationNodeChainSet(combineSkeletonNodeSet));
312 SCNode = scGraph.getCombinationNode(combineSkeletonNodeSet);
315 // the current node is not a combination node
316 // there is only one parent node which should be skeleton node.
318 // System.out.println(" hierarchyGraph.getSkeleteNodeSetReachTo(" + hNode + ")="
319 // + hierarchyGraph.getSkeleteNodeSetReachTo(hNode));
321 Set<HNode> reachToSet = hierarchyGraph.getSkeleteNodeSetReachTo(hNode);
322 for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
323 HNode reachToNode = (HNode) iterator2.next();
324 aboveSet.add(scGraph.getCurrentHNode(reachToNode));
327 SCNode = aboveSet.iterator().next();
330 // update above set w.r.t the hierarchy graph with SC nodes
331 // because the skeleton nodes in the original hierarchy graph may be merged to a new node
332 Set<HNode> endSet = new HashSet<HNode>();
333 for (Iterator iterator2 = aboveSet.iterator(); iterator2.hasNext();) {
334 HNode aboveNode = (HNode) iterator2.next();
335 endSet.add(hierarchyGraph.getCurrentHNode(aboveNode));
338 trace = hierarchyGraph.computeDistance(hNode, endSet, combineSkeletonNodeSet);
340 System.out.println(" COUNT-RESULT::start=" + hNode + " end=" + endSet + " trace="
344 // 3) convert the node m into a chain of nodes with the last node in the chain having m’s
346 Set<HNode> outgoingSCNodeSet = scGraph.getOutgoingNodeSet(SCNode);
347 System.out.println(" outgoing scnode set from " + SCNode + "=" + outgoingSCNodeSet);
349 // convert hnodes to location names
350 String startLocName = locSummary.getLocationName(SCNode.getName());
351 Set<String> outgoingLocNameSet = new HashSet<String>();
352 for (Iterator iterator2 = outgoingSCNodeSet.iterator(); iterator2.hasNext();) {
353 HNode outSCNode = (HNode) iterator2.next();
354 String locName = locSummary.getLocationName(outSCNode.getName());
355 if (!locName.equals(outSCNode.getName())) {
356 System.out.println(" outSCNode=" + outSCNode + " -> locName="
359 outgoingLocNameSet.add(locName);
362 if (outgoingLocNameSet.isEmpty()) {
363 outgoingLocNameSet.add(lattice.getBottomItem());
366 if (hNode.isCombinationNode()) {
367 System.out.println("make sure that the first node corresponds to the COMB node="
369 LineIdentifier lineId = new LineIdentifier(startLocName, outgoingLocNameSet);
370 LinkedList<LocPair> list = getLineList(desc, lineId);
371 // make sure that the first node corresponds to the COMB node
372 if (list.size() <= 0) {
373 list.add(new LocPair());
375 LocPair firstPair = list.get(0);
376 firstPair.nonShared = startLocName;
379 // 4) If hnode is not a shared location, check if there already exists a local variable
380 // node that has distance d below m along this chain. If such a node
381 // does not exist, insert it.
383 getNewLocation(desc, startLocName, outgoingLocNameSet, trace, hNode.isSharedNode());
385 System.out.println(" ###hNode=" + hNode + "---->locName=" + locName);
386 locSummary.addMapHNodeNameToLocationName(hNode.getName(), locName);
391 insertLocalLocations(desc, lattice);
396 private void insertLocalLocations(Descriptor desc, SSJavaLattice<String> lattice) {
398 Map<LineIdentifier, LinkedList<LocPair>> map = getLineListMap(desc);
399 System.out.println("####MAP=" + map);
401 Set<LineIdentifier> lineIdSet = map.keySet();
402 for (Iterator iterator = lineIdSet.iterator(); iterator.hasNext();) {
403 LineIdentifier lineId = (LineIdentifier) iterator.next();
405 LinkedList<LocPair> list = map.get(lineId);
407 String higherLocName = lineId.startLoc;
408 Set<String> endLocNameSet = lineId.lowerLocSet;
410 for (int i = 0; i < list.size(); i++) {
411 LocPair pair = list.get(i);
413 if (pair.nonShared != null) {
415 if (!lattice.getKeySet().contains(pair.nonShared)) {
416 lattice.insertNewLocationBetween(higherLocName, endLocNameSet, pair.nonShared);
418 higherLocName = pair.nonShared;
421 if (pair.shared != null) {
422 if (!lattice.getKeySet().contains(pair.shared)) {
423 lattice.insertNewLocationBetween(higherLocName, endLocNameSet, pair.shared);
424 lattice.addSharedLoc(pair.shared);
426 higherLocName = pair.shared;
435 private void addLocalLocation(SSJavaLattice<String> lattice, String localLoc) {
436 if (!mapLatticeToLocalLocSet.containsKey(lattice)) {
437 mapLatticeToLocalLocSet.put(lattice, new HashSet<String>());
439 mapLatticeToLocalLocSet.get(lattice).add(localLoc);
442 private boolean isLocalLocation(SSJavaLattice<String> lattice, String localLoc) {
443 if (mapLatticeToLocalLocSet.containsKey(lattice)) {
444 return mapLatticeToLocalLocSet.get(lattice).contains(localLoc);
449 public Map<InterLocItem, String> getInterLocMap(Descriptor desc) {
450 if (!mapDescToInterLocMap.containsKey(desc)) {
451 mapDescToInterLocMap.put(desc, new HashMap<InterLocItem, String>());
453 return mapDescToInterLocMap.get(desc);
456 public Map<LineIdentifier, LinkedList<LocPair>> getLineListMap(Descriptor desc) {
457 if (!mapDescToLineListMap.containsKey(desc)) {
458 mapDescToLineListMap.put(desc, new HashMap<LineIdentifier, LinkedList<LocPair>>());
460 return mapDescToLineListMap.get(desc);
463 public LinkedList<LocPair> getLineList(Descriptor desc, LineIdentifier lineId) {
464 Map<LineIdentifier, LinkedList<LocPair>> map = getLineListMap(desc);
465 if (!map.containsKey(lineId)) {
466 map.put(lineId, new LinkedList<LocPair>());
468 return map.get(lineId);
471 private String generateNewLocName() {
472 String newLocName = "ILOC" + (LocationInference.locSeed++);
473 System.out.println("newLocName=" + newLocName);
477 public String getNewLocation(Descriptor desc, String start, Set<String> endSet,
478 Stack<String> trace, boolean isShared) {
480 System.out.println(" #GetNewLocation start=" + start + " endSet=" + endSet + " trace="
483 LineIdentifier lineId = new LineIdentifier(start, endSet);
484 LinkedList<LocPair> list = getLineList(desc, lineId);
486 int locPairIdx = trace.size() - 1;
489 if (list.size() > locPairIdx) {
490 // there already exsits a list of nodes up to the current one
491 pair = list.get(locPairIdx);
492 // check if we need to add a new shared or non-shred node to the pair
494 if (pair.shared == null) {
495 pair.shared = generateNewLocName();
499 if (pair.nonShared == null) {
500 pair.nonShared = generateNewLocName();
502 return pair.nonShared;
506 // we need to set up a chain of intermediate nodes to the current one.
507 return recur_getNewLocation(0, list, trace);
512 private String recur_getNewLocation(int idx, LinkedList<LocPair> list, Stack<String> trace) {
514 String curType = trace.pop();
515 boolean isCurShared = false;
516 if (curType.equals("S")) {
520 if (list.size() <= idx) {
521 // need to insert a new pair for the idx
522 list.add(new LocPair());
525 // here, the list already has a pair for the idx
526 LocPair pair = list.get(idx);
527 if (isCurShared && pair.shared == null) {
528 pair.shared = generateNewLocName();
529 } else if (!isCurShared && pair.nonShared == null) {
530 pair.nonShared = generateNewLocName();
533 if (trace.isEmpty()) {
537 return pair.nonShared;
542 return recur_getNewLocation(idx, list, trace);
545 private Set<String> getAboveElementSet(SSJavaLattice<String> lattice, String loc) {
547 Set<String> aboveSet = new HashSet<String>();
549 Map<String, Set<String>> latticeMap = lattice.getTable();
550 Set<String> keySet = latticeMap.keySet();
551 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
552 String key = (String) iterator.next();
553 if (latticeMap.get(key).contains(loc)) {
561 private boolean needToExpandCombinationNode(Descriptor desc, HNode cnode) {
563 System.out.println("needToExpandCombinationNode?=" + cnode);
565 HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
566 // HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
567 Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
568 Set<HNode> combinationNodeSetInSimpleGraph =
569 simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
570 System.out.println("---combinationNodeSetInSimpleGraph=" + combinationNodeSetInSimpleGraph);
571 Set<HNode> inNodeSetToCNode = simpleGraph.getIncomingNodeSet(cnode);
572 System.out.println("------inNodeSetToCNode=" + inNodeSetToCNode);
573 for (Iterator iterator = combinationNodeSetInSimpleGraph.iterator(); iterator.hasNext();) {
574 HNode nodeBelongToTheSameCombinationNode = (HNode) iterator.next();
575 if (inNodeSetToCNode.contains(nodeBelongToTheSameCombinationNode)) {
576 // the combination node 'cnode' is not the highest location among the same combination node
584 private void expandCombinationNode(Descriptor desc, SSJavaLattice<String> lattice,
585 Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc, LocationSummary locSummary,
588 // expand the combination node 'outNode'
589 // here we need to expand the corresponding combination location in the lattice
590 HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
592 System.out.println("expandCombinationNode=" + cnode + " cnode in scgraph="
593 + combinationNodeInSCGraph);
595 if (combinationNodeInSCGraph == null) {
599 HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
600 HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
602 Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
604 // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet);
606 Set<HNode> combinationNodeSet =
607 simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
609 // System.out.println("combinationNodeSet=" + combinationNodeSet);
612 // Set<HNode> endNodeSetFromSimpleGraph =
613 // simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(cnode, combinationNodeSet);
614 // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
615 // Set<HNode> endCombNodeSet = new HashSet<HNode>();
616 // for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
617 // HNode endNode = (HNode) iterator3.next();
618 // endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
621 Set<HNode> endCombNodeSet = scGraph.getOutgoingNodeSet(combinationNodeInSCGraph);
624 // follows the straight line up to another skeleton/combination node
625 if (endCombNodeSet.size() > 0) {
626 // System.out.println("---endCombNodeSet=" + endCombNodeSet);
628 removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet);
630 recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
631 mapIntermediateLoc, 1, locSummary, cnode);
633 endCombNodeSet.add(LocationInference.BOTTOMHNODE);
634 // System.out.println("---endCombNodeSet is zero");
635 // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
636 // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode));
637 recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
638 mapIntermediateLoc, 1, locSummary, cnode);
644 private Set<HNode> removeTransitivelyReachToNode(Descriptor desc, HNode startNode,
645 Set<HNode> endNodeSet) {
647 // if an end node is not directly connected to the start node in the SC graph
648 // replace it with a directly connected one which transitively reaches to it.
650 HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
652 Set<HNode> newEndNodeSet = new HashSet<HNode>();
653 for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
654 HNode endNode = (HNode) iterator.next();
655 if (scGraph.isDirectlyConnectedTo(startNode, endNode)) {
656 newEndNodeSet.add(endNode);
659 getDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode);
660 // System.out.println("#### old END NODE=" + endNode + " --->" + newEndNode);
661 newEndNodeSet.add(newEndNode);
665 // System.out.println("removeTransitivelyReachToNode=" + endNodeSet + " newSet=" +
668 return newEndNodeSet;
672 private HNode getDirectlyReachableSCNodeFromEndNode(HierarchyGraph scGraph, HNode startNode,
673 Set<HNode> endNodeSet) {
675 // System.out.println("getDirectlyReachableSCNodeFromEndNode start=" + startNode +
678 Set<HNode> newStartNodeSet = new HashSet<HNode>();
680 for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
681 HNode endNode = (HNode) iterator.next();
682 Set<HNode> connectedToEndNodeSet = scGraph.getIncomingNodeSet(endNode);
684 for (Iterator iterator2 = connectedToEndNodeSet.iterator(); iterator2.hasNext();) {
685 HNode curNode = (HNode) iterator2.next();
686 if (recurConnectedFromStartNode(scGraph, startNode, curNode, new HashSet<HNode>())) {
687 newStartNodeSet.add(curNode);
692 // System.out.println("newStartNodeSet=" + newStartNodeSet);
694 if (newStartNodeSet.size() == 0) {
695 newStartNodeSet.add(startNode);
698 return newStartNodeSet.iterator().next();
701 private boolean recurConnectedFromStartNode(HierarchyGraph scGraph, HNode startNode,
702 HNode curNode, Set<HNode> visited) {
703 // return true if curNode is transitively connected from the startNode
705 boolean isConnected = false;
706 Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
707 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
708 HNode in = (HNode) iterator.next();
709 if (in.equals(startNode)) {
713 isConnected |= recurConnectedFromStartNode(scGraph, startNode, in, visited);
720 private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
721 HNode startNode, HNode endNode) {
722 // System.out.println("getDirectlyReachableNodeFromStartNodeReachToEndNode start=" + startNode
723 // + " end=" + endNode);
724 Set<HNode> connected = new HashSet<HNode>();
725 recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode, connected);
726 if (connected.size() == 0) {
727 connected.add(endNode);
729 // System.out.println("connected=" + connected);
731 return connected.iterator().next();
734 private void recurDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
735 HNode startNode, HNode curNode, Set<HNode> connected) {
737 Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
738 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
739 HNode inNode = (HNode) iterator.next();
740 if (inNode.equals(startNode)) {
741 connected.add(curNode);
743 recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected);
749 private void recurDFSNormalNode(Descriptor desc, SSJavaLattice<String> lattice, HNode startNode,
750 Set<HNode> endNodeSet, Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc,
751 int idx, LocationSummary locSummary, HNode curNode) {
753 TripleItem item = new TripleItem(startNode, endNodeSet, idx);
754 if (!mapIntermediateLoc.containsKey(item)) {
755 // need to create a new intermediate location in the lattice
756 String newLocName = "ILOC" + (LocationInference.locSeed++);
759 above = startNode.getName();
761 int prevIdx = idx - 1;
762 TripleItem prevItem = new TripleItem(startNode, endNodeSet, prevIdx);
763 above = mapIntermediateLoc.get(prevItem);
766 Set<String> belowSet = new HashSet<String>();
767 for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
768 HNode endNode = (HNode) iterator.next();
770 if (locSummary.getMapHNodeNameToLocationName().containsKey(endNode.getName())) {
771 locName = locSummary.getLocationName(endNode.getName());
773 locName = endNode.getName();
775 belowSet.add(locName);
777 lattice.insertNewLocationBetween(above, belowSet, newLocName);
779 mapIntermediateLoc.put(item, newLocName);
782 String locName = mapIntermediateLoc.get(item);
783 HierarchyGraph simpleHierarchyGraph = infer.getSimpleHierarchyGraph(desc);
785 if (curNode.isSharedNode()) {
786 // if the current node is shared location, add a shared location to the lattice later
787 System.out.println("###SHARED ITEM=" + item);
788 mapSharedNodeToTripleItem.put(curNode, item);
790 Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
791 for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
792 Descriptor d = (Descriptor) iterator.next();
793 locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
795 locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
798 System.out.println("-TripleItem normal=" + item);
799 System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
800 + " locName=" + locName + " isC=" + curNode.isCombinationNode());
802 Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
803 for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
804 HNode outNode = (HNode) iterator2.next();
806 Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
807 System.out.println("outNode=" + outNode);
808 System.out.println("---incomingHNodeSetToOutNode=" + incomingHNodeSetToOutNode);
810 if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) {
811 Pair<HNode, HNode> pair = new Pair(startNode, outNode);
812 if (visited.containsAll(simpleHierarchyGraph.getIncomingNodeSet(outNode))) {
813 visited.add(outNode);
814 int newidx = getCurrentHighestIndex(pair, idx + 1);
815 // int newidx = getCurrentHighestIndex(outNode, idx + 1);
816 recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
817 newidx, locSummary, outNode);
818 // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
819 // idx + 1, locSummary, outNode);
821 updateHighestIndex(pair, idx + 1);
822 // updateHighestIndex(outNode, idx + 1);
823 System.out.println("NOT RECUR");
825 } else if (!outNode.isSkeleton() && outNode.isCombinationNode() && !visited.contains(outNode)) {
826 if (needToExpandCombinationNode(desc, outNode)) {
827 System.out.println("NEED TO");
828 expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
830 System.out.println("NOT NEED TO");
838 private void recurDFS(Descriptor desc, SSJavaLattice<String> lattice,
839 HNode combinationNodeInSCGraph, Set<HNode> endNodeSet, Set<HNode> visited,
840 Map<TripleItem, String> mapIntermediateLoc, int idx, LocationSummary locSummary, HNode curNode) {
842 TripleItem item = new TripleItem(combinationNodeInSCGraph, endNodeSet, idx);
844 if (!mapIntermediateLoc.containsKey(item)) {
845 // need to create a new intermediate location in the lattice
848 String newLocName = combinationNodeInSCGraph.getName();
849 mapIntermediateLoc.put(item, newLocName);
851 String newLocName = "ILOC" + (LocationInference.locSeed++);
852 int prevIdx = idx - 1;
853 TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx);
854 above = mapIntermediateLoc.get(prevItem);
856 Set<String> belowSet = new HashSet<String>();
857 for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
858 HNode endNode = (HNode) iterator.next();
859 belowSet.add(endNode.getName());
861 lattice.insertNewLocationBetween(above, belowSet, newLocName);
862 mapIntermediateLoc.put(item, newLocName);
868 // Do we need to skip the combination node and assign a shared location to the next node?
869 // if (idx == 1 && curNode.isSharedNode()) {
870 // System.out.println("THE FIRST COMBINATION NODE EXPANSION IS SHARED!");
871 // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited, mapIntermediateLoc,
872 // idx + 1, locSummary, curNode);
876 HierarchyGraph simpleHierarchyGraph = infer.getSimpleHierarchyGraph(desc);
877 String locName = mapIntermediateLoc.get(item);
878 if (curNode.isSharedNode()) {
879 // if the current node is shared location, add a shared location to the lattice later
880 System.out.println("###SHARED ITEM=" + item);
881 mapSharedNodeToTripleItem.put(curNode, item);
883 Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
884 for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
885 Descriptor d = (Descriptor) iterator.next();
886 locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
888 locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
891 System.out.println("-TripleItem=" + item);
892 System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
893 + " locName=" + locName);
895 Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
896 for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
897 HNode outNode = (HNode) iterator2.next();
898 System.out.println("---recurDFS outNode=" + outNode);
899 System.out.println("---cur combinationNodeInSCGraph=" + combinationNodeInSCGraph);
900 System.out.println("---outNode combinationNodeInSCGraph="
901 + getCombinationNodeInSCGraph(desc, outNode));
903 if (!outNode.isSkeleton() && !visited.contains(outNode)) {
904 if (outNode.isCombinationNode()) {
906 Set<HNode> combineSkeletonNodeSet =
907 simpleHierarchyGraph.getCombineSetByCombinationNode(outNode);
908 Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
909 // extract nodes belong to the same combine node
910 Set<HNode> incomingCombinedHNodeSet = new HashSet<HNode>();
911 for (Iterator iterator = incomingHNodeSetToOutNode.iterator(); iterator.hasNext();) {
912 HNode inNode = (HNode) iterator.next();
913 if (combineSkeletonNodeSet.contains(inNode)) {
914 incomingCombinedHNodeSet.add(inNode);
917 System.out.println("-----incomingCombinedHNodeSet=" + incomingCombinedHNodeSet);
919 // check whether the next combination node is different from the current node
920 if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) {
921 Pair<HNode, HNode> pair = new Pair(combinationNodeInSCGraph, outNode);
922 if (visited.containsAll(incomingCombinedHNodeSet)) {
923 visited.add(outNode);
924 System.out.println("-------curIdx=" + (idx + 1));
926 int newIdx = getCurrentHighestIndex(pair, idx + 1);
927 // int newIdx = getCurrentHighestIndex(outNode, idx + 1);
928 System.out.println("-------newIdx=" + newIdx);
929 recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
930 mapIntermediateLoc, newIdx, locSummary, outNode);
931 // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
932 // mapIntermediateLoc, idx + 1, locSummary, outNode);
934 updateHighestIndex(pair, idx + 1);
935 // updateHighestIndex(outNode, idx + 1);
936 System.out.println("-----NOT RECUR!");
939 if (needToExpandCombinationNode(desc, outNode)) {
940 System.out.println("NEED TO");
941 expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
943 System.out.println("NOT NEED TO");
955 private int getCurrentHighestIndex(Pair<HNode, HNode> pair, int curIdx) {
956 int recordedIdx = getCurrentHighestIndex(pair);
957 if (recordedIdx > curIdx) {
964 private int getCurrentHighestIndex(HNode node, int curIdx) {
965 int recordedIdx = getCurrentHighestIndex(node);
966 if (recordedIdx > curIdx) {
973 private int getCurrentHighestIndex(Pair<HNode, HNode> pair) {
974 if (!mapItemToHighestIndex.containsKey(pair)) {
975 mapItemToHighestIndex.put(pair, new Integer(-1));
977 return mapItemToHighestIndex.get(pair).intValue();
980 private void updateHighestIndex(Pair<HNode, HNode> pair, int idx) {
981 if (idx > getCurrentHighestIndex(pair)) {
982 mapItemToHighestIndex.put(pair, new Integer(idx));
986 private int getCurrentHighestIndex(HNode node) {
987 if (!mapHNodeToHighestIndex.containsKey(node)) {
988 mapHNodeToHighestIndex.put(node, new Integer(-1));
990 return mapHNodeToHighestIndex.get(node).intValue();
993 private void updateHighestIndex(HNode node, int idx) {
994 if (idx > getCurrentHighestIndex(node)) {
995 mapHNodeToHighestIndex.put(node, new Integer(idx));
999 private String generateElementName(BasisSet basisSet, HierarchyGraph inputGraph,
1000 Map<Set<Integer>, String> mapF2LocName, Set<Integer> F) {
1002 if (mapF2LocName.containsKey(F)) {
1003 return mapF2LocName.get(F);
1006 HNode node = basisSet.getHNode(F);
1008 mapF2LocName.put(F, node.getName());
1009 return node.getName();
1011 if (inputGraph.BASISTOPELEMENT.equals(F)) {
1012 return SSJavaAnalysis.BOTTOM;
1014 String str = "LOC" + (LocationInference.locSeed++);
1015 mapF2LocName.put(F, str);
1021 private void resetCount(Map<Set<Integer>, Integer> mapFtoCount, Family family) {
1022 for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
1023 Set<Integer> F = iter.next();
1024 mapFtoCount.put(F, 0);
1028 private Map<Set<Integer>, Set<Set<Integer>>> coveringGraph(BasisSet basisSet, Family family) {
1030 Map<Set<Integer>, Integer> mapFtoCount = new HashMap<Set<Integer>, Integer>();
1031 Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = new HashMap<Set<Integer>, Set<Set<Integer>>>();
1033 // initialize COUNT(F) to 0 for all elements of the family
1034 resetCount(mapFtoCount, family);
1036 for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
1037 Set<Integer> F = iter.next();
1038 Set<HNode> gammaF = family.getGamma(F);
1040 Set<HNode> curHNodeSet = basisSet.getHNodeSet();
1041 curHNodeSet.removeAll(gammaF);
1042 Set<Set<Integer>> Bset = basisSet.getBasisSetByHNodeSet(curHNodeSet);
1044 for (Iterator iterator = Bset.iterator(); iterator.hasNext();) {
1045 Set<Integer> B = (Set<Integer>) iterator.next();
1047 Set<Integer> Fprime = new HashSet<Integer>();
1052 mapFtoCount.put(Fprime, mapFtoCount.get(Fprime) + 1);
1054 // if |gamma(F')|==COUNT(F') + |gamma(F)|
1055 int numGammaFprime = family.getGamma(Fprime).size();
1056 int countFprime = mapFtoCount.get(Fprime);
1057 int numGammaF = family.getGamma(F).size();
1058 if (numGammaFprime == (countFprime + numGammaF)) {
1059 // ImSucc(F)=IMSucc(F) union F'
1060 addImSucc(mapImSucc, F, Fprime);
1064 resetCount(mapFtoCount, family);
1067 // System.out.println("mapImSucc=" + mapImSucc);
1072 private Set<Set<Integer>> getImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F) {
1073 if (!mapImSucc.containsKey(F)) {
1074 mapImSucc.put(F, new HashSet<Set<Integer>>());
1076 return mapImSucc.get(F);
1079 private void addImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F,
1080 Set<Integer> Fprime) {
1082 if (!mapImSucc.containsKey(F)) {
1083 mapImSucc.put(F, new HashSet<Set<Integer>>());
1086 mapImSucc.get(F).add(Fprime);
1090 private Family generateFamily(BasisSet basisSet) {
1092 Family family = new Family();
1094 for (Iterator<Set<Integer>> iterator = basisSet.basisIterator(); iterator.hasNext();) {
1095 Set<Integer> B = iterator.next();
1097 Set<Pair<Set<Integer>, Set<HNode>>> tobeadded = new HashSet<Pair<Set<Integer>, Set<HNode>>>();
1099 for (Iterator<Set<Integer>> iterator2 = family.FIterator(); iterator2.hasNext();) {
1100 Set<Integer> F = iterator2.next();
1102 Set<Integer> Fprime = new HashSet<Integer>();
1106 Set<HNode> gammaFPrimeSet = new HashSet<HNode>();
1107 gammaFPrimeSet.addAll(family.getGamma(F));
1108 gammaFPrimeSet.add(basisSet.getHNode(B));
1110 if (!family.containsF(Fprime)) {
1111 Pair<Set<Integer>, Set<HNode>> pair =
1112 new Pair<Set<Integer>, Set<HNode>>(Fprime, gammaFPrimeSet);
1113 tobeadded.add(pair);
1115 family.updateGammaF(Fprime, gammaFPrimeSet);
1119 for (Iterator<Pair<Set<Integer>, Set<HNode>>> iterator2 = tobeadded.iterator(); iterator2
1121 Pair<Set<Integer>, Set<HNode>> pair = iterator2.next();
1122 family.addFElement(pair.getFirst());
1123 family.updateGammaF(pair.getFirst(), pair.getSecond());
1130 private void debug_print(HierarchyGraph inputGraph) {
1131 System.out.println("\nBuild Lattice:" + inputGraph.getName());
1132 System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex());
1133 System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis());
1142 public Identifier(HNode n, int i) {
1147 public int hashCode() {
1148 return node.hashCode() + idx;
1151 public boolean equals(Object obj) {
1153 if (obj instanceof Identifier) {
1154 Identifier in = (Identifier) obj;
1155 if (node.equals(in.node) && idx == in.idx) {
1166 public String nonShared;
1167 public String shared;
1169 public int hashCode() {
1171 if (nonShared != null) {
1172 h = nonShared.hashCode();
1174 if (shared != null) {
1175 h = shared.hashCode();
1180 public boolean equals(Object obj) {
1182 if (obj instanceof LocPair) {
1183 LocPair in = (LocPair) obj;
1185 if ((nonShared == null && in.nonShared == null)
1186 || (nonShared != null && nonShared.equals(in.nonShared))) {
1188 if ((shared == null && in.shared == null) || (shared != null && shared.equals(in.shared))) {
1199 public String toString() {
1200 String rtr = "<" + nonShared + "," + shared + ">";
1205 class LineIdentifier {
1206 public String startLoc;
1207 public Set<String> lowerLocSet;
1209 public LineIdentifier(String s, Set<String> lSet) {
1214 public int hashCode() {
1216 h = startLoc.hashCode();
1217 return h + lowerLocSet.hashCode();
1220 public boolean equals(Object obj) {
1222 if (obj instanceof LineIdentifier) {
1223 LineIdentifier in = (LineIdentifier) obj;
1224 if (startLoc.equals(in.startLoc) && lowerLocSet.equals(in.lowerLocSet)) {
1232 public String toString() {
1233 String rtr = startLoc + "->" + lowerLocSet;
1239 class InterLocItem {
1240 public String startLoc;
1241 public Set<String> lowerLocSet;
1244 public InterLocItem(String h, Set<String> l, int i) {
1250 public int hashCode() {
1253 if (startLoc != null) {
1254 h = startLoc.hashCode();
1257 return h + lowerLocSet.hashCode() + idx;
1260 public boolean equals(Object obj) {
1262 if (obj instanceof InterLocItem) {
1263 InterLocItem in = (InterLocItem) obj;
1264 if ((startLoc == null || (startLoc != null && startLoc.equals(in.startLoc)))
1265 && lowerLocSet.equals(in.lowerLocSet) && idx == in.idx) {
1273 public String toString() {
1274 String rtr = startLoc + "-" + idx + "->" + lowerLocSet;
1283 public HNode higherNode;
1284 public Set<HNode> lowerNodeSet;
1286 public boolean isShared;
1288 public TripleItem(HNode h, Set<HNode> l, int i) {
1295 public void setShared(boolean in) {
1299 public boolean isShared() {
1303 public int hashCode() {
1306 if (higherNode != null) {
1307 h = higherNode.hashCode();
1314 return h + lowerNodeSet.hashCode() + idx;
1317 public boolean equals(Object obj) {
1319 if (obj instanceof TripleItem) {
1320 TripleItem in = (TripleItem) obj;
1321 if ((higherNode == null || (higherNode != null && higherNode.equals(in.higherNode)))
1322 && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx && isShared == in.isShared()) {
1330 public String toString() {
1331 String rtr = higherNode + "-" + idx + "->" + lowerNodeSet;