X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FBuildLattice.java;h=bbef531aeb3c5c582fdbfc1c2aa9f50466332021;hb=75ee5e21119b65f10cf603d29ee261674cd05a9a;hp=eca8dfaa06d8878871bd682f4de70154d1b5d5f2;hpb=b1709554ba9722b714ff6e8f83d60943fc1fa1d8;p=IRC.git diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index eca8dfaa..bbef531a 100644 --- a/Robust/src/Analysis/SSJava/BuildLattice.java +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -18,7 +18,10 @@ public class BuildLattice { this.infer = infer; } - public SSJavaLattice buildLattice(HierarchyGraph inputGraph) { + public SSJavaLattice buildLattice(Descriptor desc) { + + HierarchyGraph inputGraph = infer.getSkeletonCombinationHierarchyGraph(desc); + LocationSummary locSummary = infer.getLocationSummary(desc); BasisSet basisSet = inputGraph.computeBasisSet(); debug_print(inputGraph); @@ -26,13 +29,13 @@ public class BuildLattice { Family family = generateFamily(basisSet); Map, Set>> mapImSucc = coveringGraph(basisSet, family); - SSJavaLattice lattice = buildLattice(basisSet, inputGraph, mapImSucc); + SSJavaLattice lattice = buildLattice(basisSet, inputGraph, locSummary, mapImSucc); return lattice; } private SSJavaLattice buildLattice(BasisSet basisSet, HierarchyGraph inputGraph, - Map, Set>> mapImSucc) { + LocationSummary locSummary, Map, Set>> mapImSucc) { SSJavaLattice lattice = new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM); @@ -44,12 +47,24 @@ public class BuildLattice { Set higher = (Set) iterator.next(); String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher); + locSummary.addMapHNodeNameToLocationName(higherName, higherName); + + HNode higherNode = inputGraph.getHNode(higherName); + if (higherNode != null && higherNode.isSharedNode()) { + lattice.addSharedLoc(higherName); + } Set> lowerSet = mapImSucc.get(higher); for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) { Set lower = (Set) iterator2.next(); String lowerName = generateElementName(basisSet, inputGraph, mapFToLocName, lower); + locSummary.addMapHNodeNameToLocationName(lowerName, lowerName); + + HNode lowerNode = inputGraph.getHNode(higherName); + if (lowerNode != null && lowerNode.isSharedNode()) { + lattice.addSharedLoc(lowerName); + } if (higher.size() == 0) { // empty case @@ -65,12 +80,24 @@ public class BuildLattice { return lattice; } - public HNode getCombinationNodeInSCGraph(Descriptor desc, HNode simpleGraphNode) { + public HNode getCombinationNodeInSCGraph(Descriptor desc, HNode nodeFromSimpleGraph) { + + HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc); + + if (nodeFromSimpleGraph.isSkeleton()) { + return scGraph.getCurrentHNode(nodeFromSimpleGraph); + } Set combineSkeletonNodeSet = - infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(simpleGraphNode); + infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(nodeFromSimpleGraph); HNode combinationNodeInSCGraph = - infer.getSkeletonCombinationHierarchyGraph(desc).getCombinationNode(combineSkeletonNodeSet); + infer.getSkeletonCombinationHierarchyGraph(desc).getMapCombineNodeSetToCombinationNode() + .get(combineSkeletonNodeSet); + + // Set combineSkeletonNodeSet = + // infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(simpleGraphNode); + // HNode combinationNodeInSCGraph = + // infer.getSkeletonCombinationHierarchyGraph(desc).getCombinationNode(combineSkeletonNodeSet); return combinationNodeInSCGraph; } @@ -82,19 +109,20 @@ public class BuildLattice { HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc); HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc); + LocationSummary locSummary = infer.getLocationSummary(desc); SSJavaLattice lattice = skeletonLattice.clone(); - Map mapIntermediateLocation = new HashMap(); - Set visited = new HashSet(); Set nodeSet = simpleGraph.getNodeSet(); - // expand a combination node Map mapIntermediateLoc = new HashMap(); + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { HNode node = (HNode) iterator.next(); + System.out.println("-node=" + node); + if (node.isSkeleton() && (!visited.contains(node))) { visited.add(node); @@ -104,34 +132,61 @@ public class BuildLattice { if (!outNode.isSkeleton()) { if (outNode.isCombinationNode()) { + // expand the combination node 'outNode' // here we need to expand the corresponding combination location in the lattice HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, outNode); Set combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(outNode); + + // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet); + Set combinationNodeSet = simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet); + + // System.out.println("combinationNodeSet=" + combinationNodeSet); + Set endNodeSetFromSimpleGraph = simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, combinationNodeSet); + // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph); Set endCombNodeSet = new HashSet(); for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) { HNode endNode = (HNode) iterator3.next(); endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode)); } + // System.out.println("-endCombNodeSet=" + endCombNodeSet); visited.add(outNode); + // follows the straight line up to another skeleton/combination node if (endCombNodeSet.size() > 0) { + endCombNodeSet = + removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet); recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited, - mapIntermediateLoc, 1, outNode); + mapIntermediateLoc, 1, locSummary, outNode); + // recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited, + // mapIntermediateLoc, 1, locSummary, outNode); } } else { // we have a node that is neither combination or skeleton node - HNode startNode = node; + // System.out.println("skeleton node=" + node + " outNode=" + outNode); + HNode startNode = scGraph.getCurrentHNode(node); + + // if (node.getDescriptor() != null) { + // // node is a skeleton node and it might be merged into another node in the SC + // graph. + // startNode = scGraph.getHNode(node.getDescriptor()); + // } else { + // // this node has already been merged before the SC graph. + // startNode = node; + // } + Set endNodeSetFromSimpleGraph = simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null); + // System.out.println("endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph + // + " from=" + outNode); Set endCombNodeSet = new HashSet(); for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) { HNode endNode = (HNode) iterator3.next(); @@ -141,16 +196,70 @@ public class BuildLattice { visited.add(outNode); if (endCombNodeSet.size() > 0) { // follows the straight line up to another skeleton/combination node + endCombNodeSet = removeTransitivelyReachToNode(desc, startNode, endCombNodeSet); recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited, - mapIntermediateLoc, 1, outNode); - + mapIntermediateLoc, 1, locSummary, outNode); } - } } } + } else if (!node.isSkeleton() && !node.isCombinationNode() && !node.isMergeNode() + && !visited.contains(node)) { + + // an intermediate node 'node' may be located between "TOP" location and a skeleton node + + Set outNodeSet = + simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(node, null); + // Set outNodeSet = simpleGraph.getOutgoingNodeSet(node); + System.out.println("this case? node=" + node + " outNodeSet=" + outNodeSet); + + Set belowSkeletonLocNameSet = new HashSet(); + Set belowSCNodeSet = new HashSet(); + + for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) { + HNode outNode = (HNode) iterator2.next(); + if (outNode.isSkeleton()) { + belowSCNodeSet.add(scGraph.getCurrentHNode(outNode)); + belowSkeletonLocNameSet.add(scGraph.getCurrentHNode(outNode).getName()); + } + } + System.out.println("-belowSkeletonLocNameSet=" + belowSkeletonLocNameSet); + if (belowSkeletonLocNameSet.size() > 0) { + + int count = simpleGraph.countHopFromTopLocation(node); + System.out.println("---count=" + count); + + TripleItem item = new TripleItem(null, belowSCNodeSet, count); + if (!mapIntermediateLoc.containsKey(item)) { + String newLocName = "ILOC" + (seed++); + mapIntermediateLoc.put(item, newLocName); + lattice.insertNewLocationBetween(lattice.getTopItem(), belowSkeletonLocNameSet, + newLocName); + locSummary.addMapHNodeNameToLocationName(node.getName(), newLocName); + } else { + String locName = mapIntermediateLoc.get(item); + locSummary.addMapHNodeNameToLocationName(node.getName(), locName); + } + + // if (!mapBelowNameSetToILOCName.containsKey(belowSkeletonLocNameSet)) { + // String newLocName = "ILOC" + (seed++); + // mapBelowNameSetToILOCName.put(belowSkeletonLocNameSet, newLocName); + // lattice.insertNewLocationBetween(lattice.getTopItem(), belowSkeletonLocNameSet, + // newLocName); + // locSummary.addMapHNodeNameToLocationName(node.getName(), newLocName); + // } else { + // String ilocName = mapBelowNameSetToILOCName.get(belowSkeletonLocNameSet); + // locSummary.addMapHNodeNameToLocationName(node.getName(), ilocName); + // } + + } + // else { + // System.out.println("---LocName=" + newLocName); + // lattice.put(newLocName); + // } + } } @@ -158,12 +267,63 @@ public class BuildLattice { } + private Set removeTransitivelyReachToNode(Descriptor desc, HNode startNode, + Set endNodeSet) { + + // if an end node is not directly connected to the start node in the SC graph + // replace it with a directly connected one which transitively reaches to it. + + HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc); + Set newEndNodeSet = new HashSet(); + + for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) { + HNode endNode = (HNode) iterator.next(); + if (scGraph.isDirectlyConnectedTo(startNode, endNode)) { + newEndNodeSet.add(endNode); + } else { + HNode newEndNode = + getDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode); + // System.out.println("#### old END NODE=" + endNode + " --->" + newEndNode); + newEndNodeSet.add(newEndNode); + } + } + + // System.out.println("removeTransitivelyReachToNode=" + endNodeSet + " newSet=" + + // newEndNodeSet); + + return newEndNodeSet; + + } + + private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph, + HNode startNode, HNode endNode) { + Set connected = new HashSet(); + recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode, connected); + return connected.iterator().next(); + } + + private void recurDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph, + HNode startNode, HNode curNode, Set connected) { + + Set inNodeSet = scGraph.getIncomingNodeSet(curNode); + for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { + HNode inNode = (HNode) iterator.next(); + if (inNode.equals(startNode)) { + connected.add(curNode); + } else { + // System.out.println("inNode=" + inNode); + recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected); + } + } + + } + private void recurDFSNormalNode(Descriptor desc, SSJavaLattice lattice, HNode startNode, Set endNodeSet, Set visited, Map mapIntermediateLoc, - int idx, HNode curNode) { + int idx, LocationSummary locSummary, HNode curNode) { TripleItem item = new TripleItem(startNode, endNodeSet, idx); - + // System.out.println("item=" + item); if (!mapIntermediateLoc.containsKey(item)) { // need to create a new intermediate location in the lattice String newLocName = "ILOC" + (seed++); @@ -188,6 +348,7 @@ public class BuildLattice { } String locName = mapIntermediateLoc.get(item); + locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName); HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc); Set outSet = graph.getOutgoingNodeSet(curNode); @@ -196,7 +357,7 @@ public class BuildLattice { if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) { visited.add(outNode); recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc, - idx + 1, outNode); + idx + 1, locSummary, outNode); } } @@ -204,34 +365,39 @@ public class BuildLattice { private void recurDFS(Descriptor desc, SSJavaLattice lattice, HNode combinationNodeInSCGraph, Set endNodeSet, Set visited, - Map mapIntermediateLoc, int idx, HNode curNode) { + Map mapIntermediateLoc, int idx, LocationSummary locSummary, HNode curNode) { TripleItem item = new TripleItem(combinationNodeInSCGraph, endNodeSet, idx); if (!mapIntermediateLoc.containsKey(item)) { // need to create a new intermediate location in the lattice - String newLocName = "ILOC" + (seed++); String above; if (idx == 1) { - above = combinationNodeInSCGraph.getName(); + String newLocName = combinationNodeInSCGraph.getName(); + mapIntermediateLoc.put(item, newLocName); } else { + String newLocName = "ILOC" + (seed++); int prevIdx = idx - 1; TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx); above = mapIntermediateLoc.get(prevItem); - } - Set belowSet = new HashSet(); - for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) { - HNode endNode = (HNode) iterator.next(); - belowSet.add(endNode.getName()); + Set belowSet = new HashSet(); + for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) { + HNode endNode = (HNode) iterator.next(); + belowSet.add(endNode.getName()); + } + lattice.insertNewLocationBetween(above, belowSet, newLocName); + mapIntermediateLoc.put(item, newLocName); + } - lattice.insertNewLocationBetween(above, belowSet, newLocName); - mapIntermediateLoc.put(item, newLocName); + } - String locName = mapIntermediateLoc.get(item); + String locName = mapIntermediateLoc.get(item); + locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName); - } + // System.out.println("-TripleItem=" + item); + // System.out.println("-curNode=" + curNode.getName() + " locName=" + locName); HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc); Set outSet = graph.getOutgoingNodeSet(curNode); @@ -241,7 +407,7 @@ public class BuildLattice { if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) { visited.add(outNode); recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited, - mapIntermediateLoc, idx + 1, outNode); + mapIntermediateLoc, idx + 1, locSummary, outNode); } } } @@ -316,7 +482,7 @@ public class BuildLattice { resetCount(mapFtoCount, family); } - System.out.println("mapImSucc=" + mapImSucc); + // System.out.println("mapImSucc=" + mapImSucc); return mapImSucc; } @@ -381,8 +547,8 @@ public class BuildLattice { private void debug_print(HierarchyGraph inputGraph) { System.out.println("\nBuild Lattice:" + inputGraph.getName()); - System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex()); - System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis()); + // System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex()); + // System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis()); } } @@ -426,14 +592,21 @@ class TripleItem { } public int hashCode() { - return higherNode.hashCode() + lowerNodeSet.hashCode() + idx; + + int h = 0; + if (higherNode != null) { + h = higherNode.hashCode(); + } + + return h + lowerNodeSet.hashCode() + idx; } public boolean equals(Object obj) { if (obj instanceof TripleItem) { TripleItem in = (TripleItem) obj; - if (higherNode.equals(in.higherNode) && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx) { + if ((higherNode == null || (higherNode != null && higherNode.equals(in.higherNode))) + && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx) { return true; } }