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 simpleGraph = infer.getSimpleHierarchyGraph(desc);
50 HierarchyGraph naiveGraph = simpleGraph.clone();
52 // I don't think we need to keep the below if statement anymore
53 // because hierarchy graph does not have any composite location
54 Set<HNode> nodeSetWithCompositeLocation = new HashSet<HNode>();
55 if (desc instanceof MethodDescriptor) {
56 FlowGraph flowGraph = infer.getFlowGraph((MethodDescriptor) desc);
58 for (Iterator iterator = inputGraph.getNodeSet().iterator(); iterator.hasNext();) {
59 HNode hnode = (HNode) iterator.next();
60 Descriptor hnodeDesc = hnode.getDescriptor();
61 if (hnodeDesc != null) {
62 NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
63 descTuple.add(hnodeDesc);
65 if (flowGraph.contains(descTuple)) {
66 FlowNode flowNode = flowGraph.getFlowNode(descTuple);
67 if (flowNode.getCompositeLocation() != null) {
68 nodeSetWithCompositeLocation.add(hnode);
77 // /////////////////////////////////////////////////////////////////////////////////////
78 // lattice generation for the native approach
80 if (infer.state.SSJAVA_INFER_NAIVE_WRITEDOTS) {
81 BasisSet naiveBasisSet = naiveGraph.computeBasisSet(nodeSetWithCompositeLocation);
83 Family naiveFamily = generateFamily(naiveBasisSet);
84 Map<Set<Integer>, Set<Set<Integer>>> naive_mapImSucc =
85 coveringGraph(naiveBasisSet, naiveFamily);
87 SSJavaLattice<String> naive_lattice =
88 buildLattice(desc, naiveBasisSet, naiveGraph, null, naive_mapImSucc);
89 int numLocs = naive_lattice.getKeySet().size();
90 LocationInference.numLocationsNaive += numLocs;
91 infer.mapNumLocsMapNaive.put(desc, new Integer(numLocs));
93 int numPaths = naive_lattice.countPaths();
94 infer.mapNumPathsMapNaive.put(desc, new Integer(numPaths));
96 System.out.println(desc + " numPaths=" + numPaths + " numLocs="
97 + naive_lattice.getKeySet().size());
99 infer.addNaiveLattice(desc, naive_lattice);
102 // /////////////////////////////////////////////////////////////////////////////////////
104 // lattice generation for the proposed approach
105 BasisSet basisSet = inputGraph.computeBasisSet(nodeSetWithCompositeLocation);
106 // debug_print(inputGraph);
108 Family family = generateFamily(basisSet);
109 Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = coveringGraph(basisSet, family);
111 SSJavaLattice<String> lattice = buildLattice(desc, basisSet, inputGraph, locSummary, mapImSucc);
116 public void setIntermediateLocMap(Descriptor desc, Map<TripleItem, String> map) {
117 mapDescToIntermediateLocMap.put(desc, map);
120 public Map<TripleItem, String> getIntermediateLocMap(Descriptor desc) {
121 if (!mapDescToIntermediateLocMap.containsKey(desc)) {
122 mapDescToIntermediateLocMap.put(desc, new HashMap<TripleItem, String>());
124 return mapDescToIntermediateLocMap.get(desc);
127 private Descriptor getParent(Descriptor desc) {
128 if (desc instanceof MethodDescriptor) {
129 MethodDescriptor md = (MethodDescriptor) desc;
130 ClassDescriptor cd = md.getClassDesc();
131 return infer.getParentMethodDesc(cd, md);
133 return ((ClassDescriptor) desc).getSuperDesc();
137 private SSJavaLattice<String> buildLattice(Descriptor desc, BasisSet basisSet,
138 HierarchyGraph inputGraph, LocationSummary locSummary,
139 Map<Set<Integer>, Set<Set<Integer>>> mapImSucc) {
141 System.out.println("\nBuild Lattice:" + inputGraph.getName());
143 SSJavaLattice<String> lattice =
144 new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
146 Map<Set<Integer>, String> mapFToLocName = new HashMap<Set<Integer>, String>();
148 Set<Set<Integer>> keySet = mapImSucc.keySet();
149 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
150 Set<Integer> higher = (Set<Integer>) iterator.next();
152 String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher);
154 HNode higherNode = inputGraph.getHNode(higherName);
156 if (higherNode == null) {
157 NameDescriptor d = new NameDescriptor(higherName);
158 higherNode = inputGraph.getHNode(d);
159 higherNode.setSkeleton(true);
162 if (higherNode != null && higherNode.isSharedNode()) {
163 lattice.addSharedLoc(higherName);
165 Set<Descriptor> descSet = inputGraph.getDescSetOfNode(higherNode);
166 // System.out.println("higherName=" + higherName + " higherNode=" + higherNode + " descSet="
169 if (locSummary != null) {
170 for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) {
171 Descriptor d = (Descriptor) iterator2.next();
172 locSummary.addMapHNodeNameToLocationName(d.getSymbol(), higherName);
176 // locSummary.addMapHNodeNameToLocationName(higherName, higherName);
178 Set<Set<Integer>> lowerSet = mapImSucc.get(higher);
179 for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
180 Set<Integer> lower = (Set<Integer>) iterator2.next();
182 String lowerName = generateElementName(basisSet, inputGraph, mapFToLocName, lower);
183 HNode lowerNode = inputGraph.getHNode(lowerName);
185 if (lowerNode == null && !lowerName.equals(SSJavaAnalysis.BOTTOM)) {
186 NameDescriptor d = new NameDescriptor(lowerName);
187 lowerNode = inputGraph.getHNode(d);
188 lowerNode.setSkeleton(true);
191 if (lowerNode != null && !inputGraph.isDirectlyConnectedTo(higherNode, lowerNode)) {
192 inputGraph.addEdge(higherNode, lowerNode);
195 if (lowerNode != null && lowerNode.isSharedNode()) {
196 lattice.addSharedLoc(lowerName);
199 Set<Descriptor> lowerDescSet = inputGraph.getDescSetOfNode(lowerNode);
200 // System.out.println("lowerName=" + lowerName + " lowerNode=" + lowerNode + " descSet="
202 if (locSummary != null) {
203 for (Iterator iterator3 = lowerDescSet.iterator(); iterator3.hasNext();) {
204 Descriptor d = (Descriptor) iterator3.next();
205 locSummary.addMapHNodeNameToLocationName(d.getSymbol(), lowerName);
208 // locSummary.addMapHNodeNameToLocationName(lowerName, lowerName);
210 if (higher.size() == 0) {
212 lattice.put(lowerName);
214 lattice.addRelationHigherToLower(higherName, lowerName);
221 inputGraph.removeRedundantEdges();
225 public HNode getCombinationNodeInSCGraph(Descriptor desc, HNode nodeFromSimpleGraph) {
227 HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
229 if (nodeFromSimpleGraph.isSkeleton()) {
230 return scGraph.getCurrentHNode(nodeFromSimpleGraph);
233 Set<HNode> combineSkeletonNodeSet =
234 infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(nodeFromSimpleGraph);
235 HNode combinationNodeInSCGraph =
236 infer.getSkeletonCombinationHierarchyGraph(desc).getMapCombineNodeSetToCombinationNode()
237 .get(combineSkeletonNodeSet);
239 // Set<HNode> combineSkeletonNodeSet =
240 // infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(simpleGraphNode);
241 // HNode combinationNodeInSCGraph =
242 // infer.getSkeletonCombinationHierarchyGraph(desc).getCombinationNode(combineSkeletonNodeSet);
243 return combinationNodeInSCGraph;
246 public SSJavaLattice<String> insertIntermediateNodesToStraightLine(Descriptor desc,
247 SSJavaLattice<String> skeletonLattice) {
249 SSJavaLattice<String> lattice = skeletonLattice.clone();
250 LocationSummary locSummary = infer.getLocationSummary(desc);
252 Descriptor parentDesc = getParent(desc);
253 if (parentDesc != null) {
254 SSJavaLattice<String> parentLattice = infer.getLattice(parentDesc);
256 Map<String, Set<String>> parentMap = parentLattice.getTable();
257 Set<String> parentKeySet = parentMap.keySet();
258 for (Iterator iterator = parentKeySet.iterator(); iterator.hasNext();) {
259 String parentKey = (String) iterator.next();
260 Set<String> parentValueSet = parentMap.get(parentKey);
261 for (Iterator iterator2 = parentValueSet.iterator(); iterator2.hasNext();) {
262 String value = (String) iterator2.next();
263 lattice.put(parentKey, value);
267 Set<String> parentSharedLocSet = parentLattice.getSharedLocSet();
268 for (Iterator iterator = parentSharedLocSet.iterator(); iterator.hasNext();) {
269 String parentSharedLoc = (String) iterator.next();
270 lattice.addSharedLoc(parentSharedLoc);
274 HierarchyGraph hierarchyGraph = infer.getSimpleHierarchyGraph(desc);
275 HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
277 Set<HNode> hierarchyGraphNodeSet = hierarchyGraph.getNodeSet();
278 for (Iterator iterator = hierarchyGraphNodeSet.iterator(); iterator.hasNext();) {
279 HNode hNode = (HNode) iterator.next();
280 if (!hNode.isSkeleton()) {
281 // here we need to insert an intermediate node for the hNode
282 System.out.println("\n#local node=" + hNode);
284 // 1) find the lowest node m in the lattice that is above hnode in the lattice
285 // 2) count the number of non-shared nodes d between the hnode and the node m
286 // int numNonSharedNodes;
290 Set<HNode> combineSkeletonNodeSet = null;
291 Stack<String> trace = new Stack<String>();
292 if (hNode.isDirectCombinationNode()) {
293 // this node itself is the lowest node m. it is the first node of the chain
294 Set<HNode> combineSet = hierarchyGraph.getCombineSetByCombinationNode(hNode);
296 System.out.println(" # direct combine node::combineSkeletonNodeSet=" + combineSet);
298 SCNode = scGraph.getCombinationNode(combineSet);
299 // numNonSharedNodes = -1;
301 if (hNode.isSharedNode()) {
308 Set<HNode> aboveSet = new HashSet<HNode>();
309 if (hNode.isCombinationNode()) {
310 // the current node is a combination node
311 combineSkeletonNodeSet = hierarchyGraph.getCombineSetByCombinationNode(hNode);
312 System.out.println(" combineSkeletonNodeSet=" + combineSkeletonNodeSet
313 + " combinationNode=" + scGraph.getCombinationNode(combineSkeletonNodeSet));
315 scGraph.getCombinationNode(combineSkeletonNodeSet);
317 System.out.println(" firstnodeOfSimpleGraph="
318 + hierarchyGraph.getFirstNodeOfCombinationNodeChainSet(combineSkeletonNodeSet));
319 aboveSet.addAll(hierarchyGraph
320 .getFirstNodeOfCombinationNodeChainSet(combineSkeletonNodeSet));
322 SCNode = scGraph.getCombinationNode(combineSkeletonNodeSet);
325 // the current node is not a combination node
326 // there is only one parent node which should be skeleton node.
328 // System.out.println(" hierarchyGraph.getSkeleteNodeSetReachTo(" + hNode + ")="
329 // + hierarchyGraph.getSkeleteNodeSetReachTo(hNode));
331 Set<HNode> reachToSet = hierarchyGraph.getSkeleteNodeSetReachTo(hNode);
332 for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
333 HNode reachToNode = (HNode) iterator2.next();
334 aboveSet.add(scGraph.getCurrentHNode(reachToNode));
337 SCNode = aboveSet.iterator().next();
340 // update above set w.r.t the hierarchy graph with SC nodes
341 // because the skeleton nodes in the original hierarchy graph may be merged to a new node
342 Set<HNode> endSet = new HashSet<HNode>();
343 for (Iterator iterator2 = aboveSet.iterator(); iterator2.hasNext();) {
344 HNode aboveNode = (HNode) iterator2.next();
345 endSet.add(hierarchyGraph.getCurrentHNode(aboveNode));
348 trace = hierarchyGraph.computeDistance(hNode, endSet, combineSkeletonNodeSet);
350 System.out.println(" COUNT-RESULT::start=" + hNode + " end=" + endSet + " trace="
354 // 3) convert the node m into a chain of nodes with the last node in the chain having m’s
356 Set<HNode> outgoingSCNodeSet = scGraph.getOutgoingNodeSet(SCNode);
357 System.out.println(" outgoing scnode set from " + SCNode + "=" + outgoingSCNodeSet);
359 // convert hnodes to location names
360 String startLocName = locSummary.getLocationName(SCNode.getName());
361 Set<String> outgoingLocNameSet = new HashSet<String>();
362 for (Iterator iterator2 = outgoingSCNodeSet.iterator(); iterator2.hasNext();) {
363 HNode outSCNode = (HNode) iterator2.next();
364 String locName = locSummary.getLocationName(outSCNode.getName());
365 if (!locName.equals(outSCNode.getName())) {
366 System.out.println(" outSCNode=" + outSCNode + " -> locName="
369 outgoingLocNameSet.add(locName);
372 if (outgoingLocNameSet.isEmpty()) {
373 outgoingLocNameSet.add(lattice.getBottomItem());
376 if (hNode.isCombinationNode()) {
377 System.out.println("make sure that the first node corresponds to the COMB node="
379 LineIdentifier lineId = new LineIdentifier(startLocName, outgoingLocNameSet);
380 LinkedList<LocPair> list = getLineList(desc, lineId);
381 // make sure that the first node corresponds to the COMB node
382 if (list.size() <= 0) {
383 list.add(new LocPair());
385 LocPair firstPair = list.get(0);
386 firstPair.nonShared = startLocName;
389 // 4) If hnode is not a shared location, check if there already exists a local variable
390 // node that has distance d below m along this chain. If such a node
391 // does not exist, insert it.
393 getNewLocation(desc, startLocName, outgoingLocNameSet, trace, hNode.isSharedNode());
395 System.out.println(" ###hNode=" + hNode + "---->locName=" + locName);
396 locSummary.addMapHNodeNameToLocationName(hNode.getName(), locName);
401 insertLocalLocations(desc, lattice);
406 private void insertLocalLocations(Descriptor desc, SSJavaLattice<String> lattice) {
408 Map<LineIdentifier, LinkedList<LocPair>> map = getLineListMap(desc);
409 System.out.println("####MAP=" + map);
411 Set<LineIdentifier> lineIdSet = map.keySet();
412 for (Iterator iterator = lineIdSet.iterator(); iterator.hasNext();) {
413 LineIdentifier lineId = (LineIdentifier) iterator.next();
415 LinkedList<LocPair> list = map.get(lineId);
417 String higherLocName = lineId.startLoc;
418 Set<String> endLocNameSet = lineId.lowerLocSet;
420 for (int i = 0; i < list.size(); i++) {
421 LocPair pair = list.get(i);
423 if (pair.nonShared != null) {
425 if (!lattice.getKeySet().contains(pair.nonShared)) {
426 lattice.insertNewLocationBetween(higherLocName, endLocNameSet, pair.nonShared);
428 higherLocName = pair.nonShared;
431 if (pair.shared != null) {
432 if (!lattice.getKeySet().contains(pair.shared)) {
433 lattice.insertNewLocationBetween(higherLocName, endLocNameSet, pair.shared);
434 lattice.addSharedLoc(pair.shared);
436 higherLocName = pair.shared;
445 private void addLocalLocation(SSJavaLattice<String> lattice, String localLoc) {
446 if (!mapLatticeToLocalLocSet.containsKey(lattice)) {
447 mapLatticeToLocalLocSet.put(lattice, new HashSet<String>());
449 mapLatticeToLocalLocSet.get(lattice).add(localLoc);
452 private boolean isLocalLocation(SSJavaLattice<String> lattice, String localLoc) {
453 if (mapLatticeToLocalLocSet.containsKey(lattice)) {
454 return mapLatticeToLocalLocSet.get(lattice).contains(localLoc);
459 public Map<InterLocItem, String> getInterLocMap(Descriptor desc) {
460 if (!mapDescToInterLocMap.containsKey(desc)) {
461 mapDescToInterLocMap.put(desc, new HashMap<InterLocItem, String>());
463 return mapDescToInterLocMap.get(desc);
466 public Map<LineIdentifier, LinkedList<LocPair>> getLineListMap(Descriptor desc) {
467 if (!mapDescToLineListMap.containsKey(desc)) {
468 mapDescToLineListMap.put(desc, new HashMap<LineIdentifier, LinkedList<LocPair>>());
470 return mapDescToLineListMap.get(desc);
473 public LinkedList<LocPair> getLineList(Descriptor desc, LineIdentifier lineId) {
474 Map<LineIdentifier, LinkedList<LocPair>> map = getLineListMap(desc);
475 if (!map.containsKey(lineId)) {
476 map.put(lineId, new LinkedList<LocPair>());
478 return map.get(lineId);
481 private String generateNewLocName() {
482 String newLocName = "ILOC" + (LocationInference.locSeed++);
483 System.out.println("newLocName=" + newLocName);
487 public String getNewLocation(Descriptor desc, String start, Set<String> endSet,
488 Stack<String> trace, boolean isShared) {
490 System.out.println(" #GetNewLocation start=" + start + " endSet=" + endSet + " trace="
493 LineIdentifier lineId = new LineIdentifier(start, endSet);
494 LinkedList<LocPair> list = getLineList(desc, lineId);
496 int locPairIdx = trace.size() - 1;
499 if (list.size() > locPairIdx) {
500 // there already exsits a list of nodes up to the current one
501 pair = list.get(locPairIdx);
502 // check if we need to add a new shared or non-shred node to the pair
504 if (pair.shared == null) {
505 pair.shared = generateNewLocName();
509 if (pair.nonShared == null) {
510 pair.nonShared = generateNewLocName();
512 return pair.nonShared;
516 // we need to set up a chain of intermediate nodes to the current one.
517 return recur_getNewLocation(0, list, trace);
522 private String recur_getNewLocation(int idx, LinkedList<LocPair> list, Stack<String> trace) {
524 String curType = trace.pop();
525 boolean isCurShared = false;
526 if (curType.equals("S")) {
530 if (list.size() <= idx) {
531 // need to insert a new pair for the idx
532 list.add(new LocPair());
535 // here, the list already has a pair for the idx
536 LocPair pair = list.get(idx);
537 if (isCurShared && pair.shared == null) {
538 pair.shared = generateNewLocName();
539 } else if (!isCurShared && pair.nonShared == null) {
540 pair.nonShared = generateNewLocName();
543 if (trace.isEmpty()) {
547 return pair.nonShared;
552 return recur_getNewLocation(idx, list, trace);
555 private Set<String> getAboveElementSet(SSJavaLattice<String> lattice, String loc) {
557 Set<String> aboveSet = new HashSet<String>();
559 Map<String, Set<String>> latticeMap = lattice.getTable();
560 Set<String> keySet = latticeMap.keySet();
561 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
562 String key = (String) iterator.next();
563 if (latticeMap.get(key).contains(loc)) {
571 private boolean needToExpandCombinationNode(Descriptor desc, HNode cnode) {
573 System.out.println("needToExpandCombinationNode?=" + cnode);
575 HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
576 // HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
577 Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
578 Set<HNode> combinationNodeSetInSimpleGraph =
579 simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
580 System.out.println("---combinationNodeSetInSimpleGraph=" + combinationNodeSetInSimpleGraph);
581 Set<HNode> inNodeSetToCNode = simpleGraph.getIncomingNodeSet(cnode);
582 System.out.println("------inNodeSetToCNode=" + inNodeSetToCNode);
583 for (Iterator iterator = combinationNodeSetInSimpleGraph.iterator(); iterator.hasNext();) {
584 HNode nodeBelongToTheSameCombinationNode = (HNode) iterator.next();
585 if (inNodeSetToCNode.contains(nodeBelongToTheSameCombinationNode)) {
586 // the combination node 'cnode' is not the highest location among the same combination node
594 private void expandCombinationNode(Descriptor desc, SSJavaLattice<String> lattice,
595 Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc, LocationSummary locSummary,
598 // expand the combination node 'outNode'
599 // here we need to expand the corresponding combination location in the lattice
600 HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
602 System.out.println("expandCombinationNode=" + cnode + " cnode in scgraph="
603 + combinationNodeInSCGraph);
605 if (combinationNodeInSCGraph == null) {
609 HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
610 HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
612 Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
614 // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet);
616 Set<HNode> combinationNodeSet =
617 simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
619 // System.out.println("combinationNodeSet=" + combinationNodeSet);
622 // Set<HNode> endNodeSetFromSimpleGraph =
623 // simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(cnode, combinationNodeSet);
624 // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
625 // Set<HNode> endCombNodeSet = new HashSet<HNode>();
626 // for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
627 // HNode endNode = (HNode) iterator3.next();
628 // endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
631 Set<HNode> endCombNodeSet = scGraph.getOutgoingNodeSet(combinationNodeInSCGraph);
634 // follows the straight line up to another skeleton/combination node
635 if (endCombNodeSet.size() > 0) {
636 // System.out.println("---endCombNodeSet=" + endCombNodeSet);
638 removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet);
640 recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
641 mapIntermediateLoc, 1, locSummary, cnode);
643 endCombNodeSet.add(LocationInference.BOTTOMHNODE);
644 // System.out.println("---endCombNodeSet is zero");
645 // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
646 // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode));
647 recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
648 mapIntermediateLoc, 1, locSummary, cnode);
654 private Set<HNode> removeTransitivelyReachToNode(Descriptor desc, HNode startNode,
655 Set<HNode> endNodeSet) {
657 // if an end node is not directly connected to the start node in the SC graph
658 // replace it with a directly connected one which transitively reaches to it.
660 HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
662 Set<HNode> newEndNodeSet = new HashSet<HNode>();
663 for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
664 HNode endNode = (HNode) iterator.next();
665 if (scGraph.isDirectlyConnectedTo(startNode, endNode)) {
666 newEndNodeSet.add(endNode);
669 getDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode);
670 // System.out.println("#### old END NODE=" + endNode + " --->" + newEndNode);
671 newEndNodeSet.add(newEndNode);
675 // System.out.println("removeTransitivelyReachToNode=" + endNodeSet + " newSet=" +
678 return newEndNodeSet;
682 private HNode getDirectlyReachableSCNodeFromEndNode(HierarchyGraph scGraph, HNode startNode,
683 Set<HNode> endNodeSet) {
685 // System.out.println("getDirectlyReachableSCNodeFromEndNode start=" + startNode +
688 Set<HNode> newStartNodeSet = new HashSet<HNode>();
690 for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
691 HNode endNode = (HNode) iterator.next();
692 Set<HNode> connectedToEndNodeSet = scGraph.getIncomingNodeSet(endNode);
694 for (Iterator iterator2 = connectedToEndNodeSet.iterator(); iterator2.hasNext();) {
695 HNode curNode = (HNode) iterator2.next();
696 if (recurConnectedFromStartNode(scGraph, startNode, curNode, new HashSet<HNode>())) {
697 newStartNodeSet.add(curNode);
702 // System.out.println("newStartNodeSet=" + newStartNodeSet);
704 if (newStartNodeSet.size() == 0) {
705 newStartNodeSet.add(startNode);
708 return newStartNodeSet.iterator().next();
711 private boolean recurConnectedFromStartNode(HierarchyGraph scGraph, HNode startNode,
712 HNode curNode, Set<HNode> visited) {
713 // return true if curNode is transitively connected from the startNode
715 boolean isConnected = false;
716 Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
717 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
718 HNode in = (HNode) iterator.next();
719 if (in.equals(startNode)) {
723 isConnected |= recurConnectedFromStartNode(scGraph, startNode, in, visited);
730 private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
731 HNode startNode, HNode endNode) {
732 // System.out.println("getDirectlyReachableNodeFromStartNodeReachToEndNode start=" + startNode
733 // + " end=" + endNode);
734 Set<HNode> connected = new HashSet<HNode>();
735 recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode, connected);
736 if (connected.size() == 0) {
737 connected.add(endNode);
739 // System.out.println("connected=" + connected);
741 return connected.iterator().next();
744 private void recurDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
745 HNode startNode, HNode curNode, Set<HNode> connected) {
747 Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
748 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
749 HNode inNode = (HNode) iterator.next();
750 if (inNode.equals(startNode)) {
751 connected.add(curNode);
753 recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected);
759 private void recurDFSNormalNode(Descriptor desc, SSJavaLattice<String> lattice, HNode startNode,
760 Set<HNode> endNodeSet, Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc,
761 int idx, LocationSummary locSummary, HNode curNode) {
763 TripleItem item = new TripleItem(startNode, endNodeSet, idx);
764 if (!mapIntermediateLoc.containsKey(item)) {
765 // need to create a new intermediate location in the lattice
766 String newLocName = "ILOC" + (LocationInference.locSeed++);
769 above = startNode.getName();
771 int prevIdx = idx - 1;
772 TripleItem prevItem = new TripleItem(startNode, endNodeSet, prevIdx);
773 above = mapIntermediateLoc.get(prevItem);
776 Set<String> belowSet = new HashSet<String>();
777 for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
778 HNode endNode = (HNode) iterator.next();
780 if (locSummary.getMapHNodeNameToLocationName().containsKey(endNode.getName())) {
781 locName = locSummary.getLocationName(endNode.getName());
783 locName = endNode.getName();
785 belowSet.add(locName);
787 lattice.insertNewLocationBetween(above, belowSet, newLocName);
789 mapIntermediateLoc.put(item, newLocName);
792 String locName = mapIntermediateLoc.get(item);
793 HierarchyGraph simpleHierarchyGraph = infer.getSimpleHierarchyGraph(desc);
795 if (curNode.isSharedNode()) {
796 // if the current node is shared location, add a shared location to the lattice later
797 System.out.println("###SHARED ITEM=" + item);
798 mapSharedNodeToTripleItem.put(curNode, item);
800 Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
801 for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
802 Descriptor d = (Descriptor) iterator.next();
803 locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
805 locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
808 System.out.println("-TripleItem normal=" + item);
809 System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
810 + " locName=" + locName + " isC=" + curNode.isCombinationNode());
812 Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
813 for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
814 HNode outNode = (HNode) iterator2.next();
816 Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
817 System.out.println("outNode=" + outNode);
818 System.out.println("---incomingHNodeSetToOutNode=" + incomingHNodeSetToOutNode);
820 if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) {
821 Pair<HNode, HNode> pair = new Pair(startNode, outNode);
822 if (visited.containsAll(simpleHierarchyGraph.getIncomingNodeSet(outNode))) {
823 visited.add(outNode);
824 int newidx = getCurrentHighestIndex(pair, idx + 1);
825 // int newidx = getCurrentHighestIndex(outNode, idx + 1);
826 recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
827 newidx, locSummary, outNode);
828 // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
829 // idx + 1, locSummary, outNode);
831 updateHighestIndex(pair, idx + 1);
832 // updateHighestIndex(outNode, idx + 1);
833 System.out.println("NOT RECUR");
835 } else if (!outNode.isSkeleton() && outNode.isCombinationNode() && !visited.contains(outNode)) {
836 if (needToExpandCombinationNode(desc, outNode)) {
837 System.out.println("NEED TO");
838 expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
840 System.out.println("NOT NEED TO");
848 private void recurDFS(Descriptor desc, SSJavaLattice<String> lattice,
849 HNode combinationNodeInSCGraph, Set<HNode> endNodeSet, Set<HNode> visited,
850 Map<TripleItem, String> mapIntermediateLoc, int idx, LocationSummary locSummary, HNode curNode) {
852 TripleItem item = new TripleItem(combinationNodeInSCGraph, endNodeSet, idx);
854 if (!mapIntermediateLoc.containsKey(item)) {
855 // need to create a new intermediate location in the lattice
858 String newLocName = combinationNodeInSCGraph.getName();
859 mapIntermediateLoc.put(item, newLocName);
861 String newLocName = "ILOC" + (LocationInference.locSeed++);
862 int prevIdx = idx - 1;
863 TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx);
864 above = mapIntermediateLoc.get(prevItem);
866 Set<String> belowSet = new HashSet<String>();
867 for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
868 HNode endNode = (HNode) iterator.next();
869 belowSet.add(endNode.getName());
871 lattice.insertNewLocationBetween(above, belowSet, newLocName);
872 mapIntermediateLoc.put(item, newLocName);
878 // Do we need to skip the combination node and assign a shared location to the next node?
879 // if (idx == 1 && curNode.isSharedNode()) {
880 // System.out.println("THE FIRST COMBINATION NODE EXPANSION IS SHARED!");
881 // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited, mapIntermediateLoc,
882 // idx + 1, locSummary, curNode);
886 HierarchyGraph simpleHierarchyGraph = infer.getSimpleHierarchyGraph(desc);
887 String locName = mapIntermediateLoc.get(item);
888 if (curNode.isSharedNode()) {
889 // if the current node is shared location, add a shared location to the lattice later
890 System.out.println("###SHARED ITEM=" + item);
891 mapSharedNodeToTripleItem.put(curNode, item);
893 Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
894 for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
895 Descriptor d = (Descriptor) iterator.next();
896 locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
898 locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
901 System.out.println("-TripleItem=" + item);
902 System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
903 + " locName=" + locName);
905 Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
906 for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
907 HNode outNode = (HNode) iterator2.next();
908 System.out.println("---recurDFS outNode=" + outNode);
909 System.out.println("---cur combinationNodeInSCGraph=" + combinationNodeInSCGraph);
910 System.out.println("---outNode combinationNodeInSCGraph="
911 + getCombinationNodeInSCGraph(desc, outNode));
913 if (!outNode.isSkeleton() && !visited.contains(outNode)) {
914 if (outNode.isCombinationNode()) {
916 Set<HNode> combineSkeletonNodeSet =
917 simpleHierarchyGraph.getCombineSetByCombinationNode(outNode);
918 Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
919 // extract nodes belong to the same combine node
920 Set<HNode> incomingCombinedHNodeSet = new HashSet<HNode>();
921 for (Iterator iterator = incomingHNodeSetToOutNode.iterator(); iterator.hasNext();) {
922 HNode inNode = (HNode) iterator.next();
923 if (combineSkeletonNodeSet.contains(inNode)) {
924 incomingCombinedHNodeSet.add(inNode);
927 System.out.println("-----incomingCombinedHNodeSet=" + incomingCombinedHNodeSet);
929 // check whether the next combination node is different from the current node
930 if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) {
931 Pair<HNode, HNode> pair = new Pair(combinationNodeInSCGraph, outNode);
932 if (visited.containsAll(incomingCombinedHNodeSet)) {
933 visited.add(outNode);
934 System.out.println("-------curIdx=" + (idx + 1));
936 int newIdx = getCurrentHighestIndex(pair, idx + 1);
937 // int newIdx = getCurrentHighestIndex(outNode, idx + 1);
938 System.out.println("-------newIdx=" + newIdx);
939 recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
940 mapIntermediateLoc, newIdx, locSummary, outNode);
941 // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
942 // mapIntermediateLoc, idx + 1, locSummary, outNode);
944 updateHighestIndex(pair, idx + 1);
945 // updateHighestIndex(outNode, idx + 1);
946 System.out.println("-----NOT RECUR!");
949 if (needToExpandCombinationNode(desc, outNode)) {
950 System.out.println("NEED TO");
951 expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
953 System.out.println("NOT NEED TO");
965 private int getCurrentHighestIndex(Pair<HNode, HNode> pair, int curIdx) {
966 int recordedIdx = getCurrentHighestIndex(pair);
967 if (recordedIdx > curIdx) {
974 private int getCurrentHighestIndex(HNode node, int curIdx) {
975 int recordedIdx = getCurrentHighestIndex(node);
976 if (recordedIdx > curIdx) {
983 private int getCurrentHighestIndex(Pair<HNode, HNode> pair) {
984 if (!mapItemToHighestIndex.containsKey(pair)) {
985 mapItemToHighestIndex.put(pair, new Integer(-1));
987 return mapItemToHighestIndex.get(pair).intValue();
990 private void updateHighestIndex(Pair<HNode, HNode> pair, int idx) {
991 if (idx > getCurrentHighestIndex(pair)) {
992 mapItemToHighestIndex.put(pair, new Integer(idx));
996 private int getCurrentHighestIndex(HNode node) {
997 if (!mapHNodeToHighestIndex.containsKey(node)) {
998 mapHNodeToHighestIndex.put(node, new Integer(-1));
1000 return mapHNodeToHighestIndex.get(node).intValue();
1003 private void updateHighestIndex(HNode node, int idx) {
1004 if (idx > getCurrentHighestIndex(node)) {
1005 mapHNodeToHighestIndex.put(node, new Integer(idx));
1009 private String generateElementName(BasisSet basisSet, HierarchyGraph inputGraph,
1010 Map<Set<Integer>, String> mapF2LocName, Set<Integer> F) {
1012 if (mapF2LocName.containsKey(F)) {
1013 return mapF2LocName.get(F);
1016 HNode node = basisSet.getHNode(F);
1018 mapF2LocName.put(F, node.getName());
1019 return node.getName();
1021 if (inputGraph.BASISTOPELEMENT.equals(F)) {
1022 return SSJavaAnalysis.BOTTOM;
1024 String str = "LOC" + (LocationInference.locSeed++);
1025 mapF2LocName.put(F, str);
1031 private void resetCount(Map<Set<Integer>, Integer> mapFtoCount, Family family) {
1032 for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
1033 Set<Integer> F = iter.next();
1034 mapFtoCount.put(F, 0);
1038 private Map<Set<Integer>, Set<Set<Integer>>> coveringGraph(BasisSet basisSet, Family family) {
1040 Map<Set<Integer>, Integer> mapFtoCount = new HashMap<Set<Integer>, Integer>();
1041 Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = new HashMap<Set<Integer>, Set<Set<Integer>>>();
1043 // initialize COUNT(F) to 0 for all elements of the family
1044 resetCount(mapFtoCount, family);
1046 for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
1047 Set<Integer> F = iter.next();
1048 Set<HNode> gammaF = family.getGamma(F);
1050 Set<HNode> curHNodeSet = basisSet.getHNodeSet();
1051 curHNodeSet.removeAll(gammaF);
1052 Set<Set<Integer>> Bset = basisSet.getBasisSetByHNodeSet(curHNodeSet);
1054 for (Iterator iterator = Bset.iterator(); iterator.hasNext();) {
1055 Set<Integer> B = (Set<Integer>) iterator.next();
1057 Set<Integer> Fprime = new HashSet<Integer>();
1062 mapFtoCount.put(Fprime, mapFtoCount.get(Fprime) + 1);
1064 // if |gamma(F')|==COUNT(F') + |gamma(F)|
1065 int numGammaFprime = family.getGamma(Fprime).size();
1066 int countFprime = mapFtoCount.get(Fprime);
1067 int numGammaF = family.getGamma(F).size();
1068 if (numGammaFprime == (countFprime + numGammaF)) {
1069 // ImSucc(F)=IMSucc(F) union F'
1070 addImSucc(mapImSucc, F, Fprime);
1074 resetCount(mapFtoCount, family);
1077 // System.out.println("mapImSucc=" + mapImSucc);
1082 private Set<Set<Integer>> getImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F) {
1083 if (!mapImSucc.containsKey(F)) {
1084 mapImSucc.put(F, new HashSet<Set<Integer>>());
1086 return mapImSucc.get(F);
1089 private void addImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F,
1090 Set<Integer> Fprime) {
1092 if (!mapImSucc.containsKey(F)) {
1093 mapImSucc.put(F, new HashSet<Set<Integer>>());
1096 mapImSucc.get(F).add(Fprime);
1100 private Family generateFamily(BasisSet basisSet) {
1102 Family family = new Family();
1104 for (Iterator<Set<Integer>> iterator = basisSet.basisIterator(); iterator.hasNext();) {
1105 Set<Integer> B = iterator.next();
1107 Set<Pair<Set<Integer>, Set<HNode>>> tobeadded = new HashSet<Pair<Set<Integer>, Set<HNode>>>();
1109 for (Iterator<Set<Integer>> iterator2 = family.FIterator(); iterator2.hasNext();) {
1110 Set<Integer> F = iterator2.next();
1112 Set<Integer> Fprime = new HashSet<Integer>();
1116 Set<HNode> gammaFPrimeSet = new HashSet<HNode>();
1117 gammaFPrimeSet.addAll(family.getGamma(F));
1118 gammaFPrimeSet.add(basisSet.getHNode(B));
1120 if (!family.containsF(Fprime)) {
1121 Pair<Set<Integer>, Set<HNode>> pair =
1122 new Pair<Set<Integer>, Set<HNode>>(Fprime, gammaFPrimeSet);
1123 tobeadded.add(pair);
1125 family.updateGammaF(Fprime, gammaFPrimeSet);
1129 for (Iterator<Pair<Set<Integer>, Set<HNode>>> iterator2 = tobeadded.iterator(); iterator2
1131 Pair<Set<Integer>, Set<HNode>> pair = iterator2.next();
1132 family.addFElement(pair.getFirst());
1133 family.updateGammaF(pair.getFirst(), pair.getSecond());
1140 private void debug_print(HierarchyGraph inputGraph) {
1141 System.out.println("\nBuild Lattice:" + inputGraph.getName());
1142 System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex());
1143 System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis());
1152 public Identifier(HNode n, int i) {
1157 public int hashCode() {
1158 return node.hashCode() + idx;
1161 public boolean equals(Object obj) {
1163 if (obj instanceof Identifier) {
1164 Identifier in = (Identifier) obj;
1165 if (node.equals(in.node) && idx == in.idx) {
1176 public String nonShared;
1177 public String shared;
1179 public int hashCode() {
1181 if (nonShared != null) {
1182 h = nonShared.hashCode();
1184 if (shared != null) {
1185 h = shared.hashCode();
1190 public boolean equals(Object obj) {
1192 if (obj instanceof LocPair) {
1193 LocPair in = (LocPair) obj;
1195 if ((nonShared == null && in.nonShared == null)
1196 || (nonShared != null && nonShared.equals(in.nonShared))) {
1198 if ((shared == null && in.shared == null) || (shared != null && shared.equals(in.shared))) {
1209 public String toString() {
1210 String rtr = "<" + nonShared + "," + shared + ">";
1215 class LineIdentifier {
1216 public String startLoc;
1217 public Set<String> lowerLocSet;
1219 public LineIdentifier(String s, Set<String> lSet) {
1224 public int hashCode() {
1226 h = startLoc.hashCode();
1227 return h + lowerLocSet.hashCode();
1230 public boolean equals(Object obj) {
1232 if (obj instanceof LineIdentifier) {
1233 LineIdentifier in = (LineIdentifier) obj;
1234 if (startLoc.equals(in.startLoc) && lowerLocSet.equals(in.lowerLocSet)) {
1242 public String toString() {
1243 String rtr = startLoc + "->" + lowerLocSet;
1249 class InterLocItem {
1250 public String startLoc;
1251 public Set<String> lowerLocSet;
1254 public InterLocItem(String h, Set<String> l, int i) {
1260 public int hashCode() {
1263 if (startLoc != null) {
1264 h = startLoc.hashCode();
1267 return h + lowerLocSet.hashCode() + idx;
1270 public boolean equals(Object obj) {
1272 if (obj instanceof InterLocItem) {
1273 InterLocItem in = (InterLocItem) obj;
1274 if ((startLoc == null || (startLoc != null && startLoc.equals(in.startLoc)))
1275 && lowerLocSet.equals(in.lowerLocSet) && idx == in.idx) {
1283 public String toString() {
1284 String rtr = startLoc + "-" + idx + "->" + lowerLocSet;
1293 public HNode higherNode;
1294 public Set<HNode> lowerNodeSet;
1296 public boolean isShared;
1298 public TripleItem(HNode h, Set<HNode> l, int i) {
1305 public void setShared(boolean in) {
1309 public boolean isShared() {
1313 public int hashCode() {
1316 if (higherNode != null) {
1317 h = higherNode.hashCode();
1324 return h + lowerNodeSet.hashCode() + idx;
1327 public boolean equals(Object obj) {
1329 if (obj instanceof TripleItem) {
1330 TripleItem in = (TripleItem) obj;
1331 if ((higherNode == null || (higherNode != null && higherNode.equals(in.higherNode)))
1332 && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx && isShared == in.isShared()) {
1340 public String toString() {
1341 String rtr = higherNode + "-" + idx + "->" + lowerNodeSet;