X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FBuildLattice.java;h=2df41320b448f7dae328ff70a693ff5fdc94a8ac;hb=7701457cedb357fc5efd0170f495a22a99b18cef;hp=b3cdd8ae29bfb01f5560f334673beabbce6e1af4;hpb=aec24fc101dec2a1ece71783932d11eb46704ebe;p=IRC.git diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index b3cdd8ae..2df41320 100644 --- a/Robust/src/Analysis/SSJava/BuildLattice.java +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -12,16 +12,10 @@ import Util.Pair; public class BuildLattice { - public static int seed = 0; private LocationInference infer; - private final HNode topNode; - private final HNode bottomNode; - public BuildLattice(LocationInference infer) { this.infer = infer; - topNode = new HNode(infer.ssjava.TOP); - bottomNode = new HNode(infer.ssjava.BOTTOM); } public SSJavaLattice buildLattice(Descriptor desc) { @@ -162,9 +156,12 @@ public class BuildLattice { Map mapIntermediateLoc = new HashMap(); + System.out.println("*insert=" + desc); + System.out.println("***nodeSet=" + nodeSet); for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { HNode node = (HNode) iterator.next(); - // System.out.println("node=" + node); + System.out.println("node=" + node); + if (node.isSkeleton() && (!visited.contains(node))) { visited.add(node); @@ -174,39 +171,7 @@ 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)); - } - 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, locSummary, outNode); - } - + expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode); } else { // we have a node that is neither combination or skeleton node // System.out.println("%%%skeleton node=" + node + " outNode=" + outNode); @@ -239,8 +204,9 @@ public class BuildLattice { } else if (endCombNodeSet.size() == 0) { // the outNode is (directly/transitively) connected to the bottom node // therefore, we just add a dummy bottom HNode to the endCombNodeSet. - endCombNodeSet.add(bottomNode); + endCombNodeSet.add(LocationInference.BOTTOMHNODE); } + recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited, mapIntermediateLoc, 1, locSummary, outNode); } @@ -251,10 +217,11 @@ public class BuildLattice { } else if (!node.isSkeleton() && !node.isCombinationNode() && !node.isMergeNode() && !visited.contains(node)) { + System.out.println("n=" + node); + // an intermediate node 'node' may be located between "TOP" location and a skeleton node - int sizeIncomingNode = simpleGraph.getIncomingNodeSet(node).size(); + if (simpleGraph.getIncomingNodeSet(node).size() == 0) { - if (sizeIncomingNode == 0) { // this node will be directly connected to the TOP location // start adding the following nodes from this node @@ -267,7 +234,8 @@ public class BuildLattice { endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode)); } - HNode startNode = topNode; + System.out.println("endCombNodeSet=" + endCombNodeSet); + HNode startNode = LocationInference.TOPHNODE; visited.add(startNode); if (endCombNodeSet.size() > 0) { // follows the straight line up to another skeleton/combination node @@ -285,6 +253,56 @@ public class BuildLattice { } + private void expandCombinationNode(Descriptor desc, SSJavaLattice lattice, + Set visited, Map mapIntermediateLoc, LocationSummary locSummary, + HNode cnode) { + + System.out.println("expandCombinationNode=" + cnode); + // expand the combination node 'outNode' + // here we need to expand the corresponding combination location in the lattice + HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode); + + HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc); + + Set combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode); + + // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet); + + Set combinationNodeSet = + simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet); + + // System.out.println("combinationNodeSet=" + combinationNodeSet); + + Set endNodeSetFromSimpleGraph = + simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(cnode, 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)); + } + visited.add(cnode); + + // follows the straight line up to another skeleton/combination node + if (endCombNodeSet.size() > 0) { + System.out.println("---endCombNodeSet=" + endCombNodeSet); + endCombNodeSet = + removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet); + + recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited, + mapIntermediateLoc, 1, locSummary, cnode); + } else { + endCombNodeSet.add(LocationInference.BOTTOMHNODE); + // System.out.println("---endCombNodeSet is zero"); + // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph); + // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode)); + recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited, + mapIntermediateLoc, 1, locSummary, cnode); + + } + + } + private Set removeTransitivelyReachToNode(Descriptor desc, HNode startNode, Set endNodeSet) { @@ -292,8 +310,8 @@ public class BuildLattice { // replace it with a directly connected one which transitively reaches to it. HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc); - Set newEndNodeSet = new HashSet(); + Set newEndNodeSet = new HashSet(); for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) { HNode endNode = (HNode) iterator.next(); if (scGraph.isDirectlyConnectedTo(startNode, endNode)) { @@ -313,10 +331,64 @@ public class BuildLattice { } + private HNode getDirectlyReachableSCNodeFromEndNode(HierarchyGraph scGraph, HNode startNode, + Set endNodeSet) { + + System.out.println("getDirectlyReachableSCNodeFromEndNode start=" + startNode + " endNodeSet=" + + endNodeSet); + Set newStartNodeSet = new HashSet(); + + for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) { + HNode endNode = (HNode) iterator.next(); + Set connectedToEndNodeSet = scGraph.getIncomingNodeSet(endNode); + + for (Iterator iterator2 = connectedToEndNodeSet.iterator(); iterator2.hasNext();) { + HNode curNode = (HNode) iterator2.next(); + if (recurConnectedFromStartNode(scGraph, startNode, curNode, new HashSet())) { + newStartNodeSet.add(curNode); + } + } + } + + System.out.println("newStartNodeSet=" + newStartNodeSet); + + if (newStartNodeSet.size() == 0) { + newStartNodeSet.add(startNode); + } + + return newStartNodeSet.iterator().next(); + } + + private boolean recurConnectedFromStartNode(HierarchyGraph scGraph, HNode startNode, + HNode curNode, Set visited) { + // return true if curNode is transitively connected from the startNode + + boolean isConnected = false; + Set inNodeSet = scGraph.getIncomingNodeSet(curNode); + for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { + HNode in = (HNode) iterator.next(); + if (in.equals(startNode)) { + return true; + } else { + visited.add(in); + isConnected |= recurConnectedFromStartNode(scGraph, startNode, in, visited); + } + } + + return isConnected; + } + private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph, HNode startNode, HNode endNode) { + System.out.println("getDirectlyReachableNodeFromStartNodeReachToEndNode start=" + startNode + + " end=" + endNode); Set connected = new HashSet(); recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode, connected); + if (connected.size() == 0) { + connected.add(endNode); + } + System.out.println("connected=" + connected); + return connected.iterator().next(); } @@ -329,7 +401,6 @@ public class BuildLattice { if (inNode.equals(startNode)) { connected.add(curNode); } else { - // System.out.println("inNode=" + inNode); recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected); } } @@ -344,7 +415,7 @@ public class BuildLattice { // System.out.println("item=" + item); if (!mapIntermediateLoc.containsKey(item)) { // need to create a new intermediate location in the lattice - String newLocName = "ILOC" + (seed++); + String newLocName = "ILOC" + (LocationInference.locSeed++); String above; if (idx == 1) { above = startNode.getName(); @@ -357,15 +428,21 @@ public class BuildLattice { Set belowSet = new HashSet(); for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) { HNode endNode = (HNode) iterator.next(); - belowSet.add(endNode.getName()); + String locName; + if (locSummary.getMapHNodeNameToLocationName().containsKey(endNode.getName())) { + locName = locSummary.getLocationName(endNode.getName()); + } else { + locName = endNode.getName(); + } + belowSet.add(locName); } - lattice.insertNewLocationBetween(above, belowSet, newLocName); mapIntermediateLoc.put(item, newLocName); } String locName = mapIntermediateLoc.get(item); + HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc); Set descSet = graph.getDescSetOfNode(curNode); @@ -373,7 +450,14 @@ public class BuildLattice { Descriptor d = (Descriptor) iterator.next(); locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName); } - // locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName); + locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName); + + if (curNode.isSharedNode()) { + lattice.addSharedLoc(locName); + } + + System.out.println("-TripleItem=" + item); + System.out.println("-curNode=" + curNode.getName() + " locName=" + locName); Set outSet = graph.getOutgoingNodeSet(curNode); for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) { @@ -382,6 +466,8 @@ public class BuildLattice { visited.add(outNode); recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc, idx + 1, locSummary, outNode); + } else if (!outNode.isSkeleton() && outNode.isCombinationNode() && !visited.contains(outNode)) { + expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode); } } @@ -400,7 +486,7 @@ public class BuildLattice { String newLocName = combinationNodeInSCGraph.getName(); mapIntermediateLoc.put(item, newLocName); } else { - String newLocName = "ILOC" + (seed++); + String newLocName = "ILOC" + (LocationInference.locSeed++); int prevIdx = idx - 1; TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx); above = mapIntermediateLoc.get(prevItem); @@ -424,19 +510,34 @@ public class BuildLattice { Descriptor d = (Descriptor) iterator.next(); locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName); } + locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName); - // System.out.println("-TripleItem=" + item); - // System.out.println("-curNode=" + curNode.getName() + " locName=" + locName); + if (curNode.isSharedNode()) { + lattice.addSharedLoc(locName); + } + System.out.println("-TripleItem=" + item); + System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode() + + " locName=" + locName); Set outSet = graph.getOutgoingNodeSet(curNode); for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) { HNode outNode = (HNode) iterator2.next(); + // System.out.println("recurDFS outNode=" + outNode); + // System.out.println("---cur combinationNodeInSCGraph=" + combinationNodeInSCGraph); + // System.out.println("---outNode combinationNodeInSCGraph=" + // + getCombinationNodeInSCGraph(desc, outNode)); if (!outNode.isSkeleton() && !visited.contains(outNode)) { - if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) { - visited.add(outNode); - recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited, - mapIntermediateLoc, idx + 1, locSummary, outNode); + if (outNode.isCombinationNode()) { + // check whether the next combination node is different from the current node + if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) { + visited.add(outNode); + recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited, + mapIntermediateLoc, idx + 1, locSummary, outNode); + } else { + expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode); + } } + } } @@ -457,7 +558,7 @@ public class BuildLattice { if (inputGraph.BASISTOPELEMENT.equals(F)) { return SSJavaAnalysis.BOTTOM; } else { - String str = "LOC" + (seed++); + String str = "LOC" + (LocationInference.locSeed++); mapF2LocName.put(F, str); return str; }