X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FHierarchyGraph.java;h=d51e6107d41705113b6d3f0bc682f153e30c8e12;hb=16c9b68be88b7753b0b2a8b5766983ce06d0c2ad;hp=e0fa16fc1596e1a2d2c433d8c61f0ee02324df8c;hpb=2e579e40f20a086e38dff23ac2b46fdd28f6f435;p=IRC.git diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index e0fa16fc..d51e6107 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -36,6 +36,8 @@ public class HierarchyGraph { Map, HNode> mapCombineNodeSetToCombinationNode; Map, Set> mapCombineNodeSetToOutgoingNodeSet; + Map> mapNormalNodeToSCNodeReachToSet; + Set nodeSet; // for the lattice generation @@ -63,6 +65,7 @@ public class HierarchyGraph { mapHNodeNameToCurrentHNode = new HashMap(); + mapNormalNodeToSCNodeReachToSet = new HashMap>(); } public Descriptor getDesc() { @@ -138,18 +141,21 @@ public class HierarchyGraph { if (possibleCycleSet.size() > 0) { if (possibleCycleSet.size() == 1) { + System.out.println("possibleCycleSet=" + possibleCycleSet + " from src=" + srcHNode + + " dstHNode=" + dstHNode); if (dstHNode.isSharedNode()) { // it has already been assigned shared node. } else { dstHNode.setSharedNode(true); + System.out.println("$$$setShared=" + dstHNode); } return; } + System.out.println("--- CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode); HNode newMergeNode = mergeNodes(possibleCycleSet, false); newMergeNode.setSharedNode(true); - System.out.println("### INTRODUCE A NEW MERGE NODE: " + newMergeNode); - System.out.println("### CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode + "\n"); + } else { getIncomingNodeSet(dstHNode).add(srcHNode); getOutgoingNodeSet(srcHNode).add(dstHNode); @@ -163,10 +169,16 @@ public class HierarchyGraph { } public void addEdge(Descriptor src, Descriptor dst) { - HNode srcHNode = getHNode(src); - HNode dstHNode = getHNode(dst); - addEdge(srcHNode, dstHNode); + if (src.equals(LocationInference.LITERALDESC)) { + // in this case, we do not need to add a source hnode + // just add a destination hnode + getHNode(dst); + } else { + HNode srcHNode = getHNode(src); + HNode dstHNode = getHNode(dst); + addEdge(srcHNode, dstHNode); + } } @@ -177,9 +189,20 @@ public class HierarchyGraph { public HNode getHNode(Descriptor d) { if (!mapDescToHNode.containsKey(d)) { HNode newNode = new HNode(d); + if (d instanceof FieldDescriptor) { newNode.setSkeleton(true); } + + if (d.equals(LocationInference.TOPDESC)) { + newNode.setSkeleton(true); + } + + String symbol = d.getSymbol(); + if (symbol.startsWith(LocationInference.PCLOC) || symbol.startsWith(LocationInference.RLOC)) { + newNode.setSkeleton(true); + } + mappingDescriptorToHNode(d, newNode); nodeSet.add(newNode); } @@ -378,7 +401,7 @@ public class HierarchyGraph { private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) { getIncomingNodeSet(dstHNode).add(srcHNode); getOutgoingNodeSet(srcHNode).add(dstHNode); - System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode); + // System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode); } private HNode mergeNodes(Set set, boolean onlyCombinationNodes) { @@ -408,16 +431,22 @@ public class HierarchyGraph { // if the input set contains a skeleton node, need to set a new merge node as skeleton also boolean hasSkeleton = false; + boolean hasShared = false; for (Iterator iterator = set.iterator(); iterator.hasNext();) { HNode inNode = (HNode) iterator.next(); if (inNode.isSkeleton()) { hasSkeleton = true; - break; + } + if (inNode.isSharedNode()) { + hasShared = true; } } - System.out.println("--Set merging node=" + newMergeNode + " as a skeleton=" + set - + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc); + // System.out.println("-----Set merging node=" + newMergeNode + " as a skeleton=" + set + // + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc); newMergeNode.setSkeleton(hasSkeleton); + newMergeNode.setSharedNode(hasShared); + + System.out.println("-----MERGING NODE=" + set + " new node=" + newMergeNode); for (Iterator iterator = set.iterator(); iterator.hasNext();) { HNode node = (HNode) iterator.next(); @@ -461,14 +490,14 @@ public class HierarchyGraph { HNode mergedNode = (HNode) iterator.next(); addMapHNodeToCurrentHNode(mergedNode, newMergeNode); } - System.out.println("###mergedSkeletonNode=" + mergedSkeletonNode); - System.out.println("###MERGING NODE=" + set + " new node=" + newMergeNode); for (Iterator iterator = set.iterator(); iterator.hasNext();) { HNode hNode = (HNode) iterator.next(); System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode)); } + System.out.println(); + return newMergeNode; } @@ -476,8 +505,8 @@ public class HierarchyGraph { if (curNode.isMergeNode()) { Set mergingSet = getMergingSet(curNode); mergingSet.add(curNode); - System.out.println("addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet=" - + mergingSet); + System.out.println("-------addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet=" + + mergingSet + " newNode=" + newNode); for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) { HNode mergingNode = (HNode) iterator.next(); mapHNodeToCurrentHNode.put(mergingNode, newNode); @@ -555,6 +584,68 @@ public class HierarchyGraph { } + public Set getReachableSCNodeSet(HNode startNode) { + // returns the set of hnodes which is reachable from the startNode and is either SC node or a + // node which is directly connected to the SC nodes + Set reachable = new HashSet(); + Set visited = new HashSet(); + visited.add(startNode); + recurReachableNodeSet(startNode, visited, reachable); + return reachable; + } + + public Set getSCNodeReachToSet(HNode node) { + if (!mapNormalNodeToSCNodeReachToSet.containsKey(node)) { + mapNormalNodeToSCNodeReachToSet.put(node, new HashSet()); + } + return mapNormalNodeToSCNodeReachToSet.get(node); + } + + private void recurReachableNodeSet(HNode node, Set visited, Set reachable) { + + Set outSet = getOutgoingNodeSet(node); + for (Iterator iterator = outSet.iterator(); iterator.hasNext();) { + HNode out = (HNode) iterator.next(); + + if (!visited.contains(out)) { + visited.add(out); + Set reachableFromSCNodeSet = reachableFromSCNode(out); + mapNormalNodeToSCNodeReachToSet.put(out, reachableFromSCNodeSet); + if (out.isSkeleton() || out.isCombinationNode() || reachableFromSCNodeSet.size() > 0) { + reachable.add(out); + } else { + visited.add(out); + recurReachableNodeSet(out, visited, reachable); + } + + } + + } + + } + + private Set reachableFromSCNode(HNode node) { + Set visited = new HashSet(); + visited.add(node); + Set reachable = new HashSet(); + recurReachableFromSCNode(node, reachable, visited); + return reachable; + } + + private void recurReachableFromSCNode(HNode node, Set reachable, Set visited) { + Set inNodeSet = getIncomingNodeSet(node); + for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { + HNode inNode = (HNode) iterator.next(); + if (inNode.isSkeleton() || inNode.isCombinationNode()) { + visited.add(inNode); + reachable.add(inNode); + } else if (!visited.contains(inNode)) { + visited.add(inNode); + recurReachableFromSCNode(inNode, reachable, visited); + } + } + } + public Set getDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set combinationNodeSet) { Set reachable = new HashSet(); @@ -686,9 +777,9 @@ public class HierarchyGraph { Set> keySet = simpleHierarchyGraph.getCombineNodeSet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Set combineSet = (Set) iterator.next(); - System.out.println("--combineSet=" + combineSet); + // System.out.println("--combineSet=" + combineSet); HNode combinationNode = getCombinationNode(combineSet); - System.out.println("--combinationNode=" + combinationNode); + // System.out.println("--combinationNode=" + combinationNode); // add an edge from a skeleton node to a combination node for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) { HNode inSkeletonNode = (HNode) iterator2.next(); @@ -759,10 +850,10 @@ public class HierarchyGraph { Set visited = new HashSet(); recurSkeletonReachTo(node, reachToSet, visited); + // obsolete! // if a node reaches to one of elements in the reachToSet, we do not need to keep it // because the node is not directly connected to the combination node - - removeRedundantReachToNodes(reachToSet); + // removeRedundantReachToNodes(reachToSet); return reachToSet; } @@ -876,6 +967,7 @@ public class HierarchyGraph { HNode node = (HNode) iterator.next(); if (!node.isSkeleton()) { Set reachToSet = getSkeleteNodeSetReachTo(node); + System.out.println("$node=" + node + " reachToNodeSet=" + reachToSet); if (reachToSet.size() > 1) { // if (countSkeletonNodes(reachToSet) > 1) { System.out.println("-node=" + node + " reachToSet=" + reachToSet); @@ -983,7 +1075,7 @@ public class HierarchyGraph { public void assignUniqueIndexToNode() { int idx = 1; - System.out.println("nodeSet=" + nodeSet); + // System.out.println("nodeSet=" + nodeSet); for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { HNode node = (HNode) iterator.next(); mapHNodeToUniqueIndex.put(node, idx); @@ -1013,17 +1105,17 @@ public class HierarchyGraph { basis.addAll(BASISTOPELEMENT); Set reachableNodeSet = getReachableNodeSetFrom(node); - System.out.println("node=" + node + " reachableNodeSet=" + reachableNodeSet); - System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node)); + // System.out.println("node=" + node + " reachableNodeSet=" + reachableNodeSet); + // System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node)); // if a node is reachable from the current node // need to remove the index of the reachable node from the basis basis.remove(getHNodeIndex(node)); for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { HNode reachableNode = (HNode) iterator2.next(); - System.out.println("reachableNode=" + reachableNode); - System.out.println("getHNodeIndex(reachableNode))=" - + mapHNodeToUniqueIndex.get(reachableNode)); + // System.out.println("reachableNode=" + reachableNode); + // System.out.println("getHNodeIndex(reachableNode))=" + // + mapHNodeToUniqueIndex.get(reachableNode)); int idx = getHNodeIndex(reachableNode); basis.remove(idx); }