X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FBuildLattice.java;h=61a083274e84e97c7968442d8bc6d5d502d343f8;hp=3bd84fef8fef0117867f73b8f334652910015c37;hb=99040b5e3460f3e28210e6b672bc8b46545a775e;hpb=937867fd8d958d7ce7dadc3e4aab8ff03084eb51 diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index 3bd84fef..61a08327 100644 --- a/Robust/src/Analysis/SSJava/BuildLattice.java +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -62,17 +62,23 @@ public class BuildLattice { } + // ///////////////////////////////////////////////////////////////////////////////////// // lattice generation for the native approach - BasisSet naiveBasisSet = naiveGraph.computeBasisSet(nodeSetWithCompositeLocation); - // debug_print(inputGraph); - Family naiveFamily = generateFamily(naiveBasisSet); - Map, Set>> naive_mapImSucc = - coveringGraph(naiveBasisSet, naiveFamily); + if (infer.state.SSJAVA_INFER_NAIVE_WRITEDOTS) { + BasisSet naiveBasisSet = naiveGraph.computeBasisSet(nodeSetWithCompositeLocation); + + Family naiveFamily = generateFamily(naiveBasisSet); + Map, Set>> naive_mapImSucc = + coveringGraph(naiveBasisSet, naiveFamily); + + SSJavaLattice naive_lattice = + buildLattice(desc, naiveBasisSet, naiveGraph, null, naive_mapImSucc); + LocationInference.numLocationsNaive += naive_lattice.getKeySet().size(); + infer.addNaiveLattice(desc, naive_lattice); + } - SSJavaLattice naive_lattice = - buildLattice(desc, naiveBasisSet, naiveGraph, null, naive_mapImSucc); - LocationInference.numLocationsNaive += naive_lattice.getKeySet().size(); + // ///////////////////////////////////////////////////////////////////////////////////// // lattice generation for the proposed approach BasisSet basisSet = inputGraph.computeBasisSet(nodeSetWithCompositeLocation); @@ -218,6 +224,253 @@ public class BuildLattice { public SSJavaLattice insertIntermediateNodesToStraightLine(Descriptor desc, SSJavaLattice skeletonLattice) { + + SSJavaLattice lattice = skeletonLattice.clone(); + LocationSummary locSummary = infer.getLocationSummary(desc); + + Descriptor parentDesc = getParent(desc); + if (parentDesc != null) { + SSJavaLattice parentLattice = infer.getLattice(parentDesc); + + Map> parentMap = parentLattice.getTable(); + Set parentKeySet = parentMap.keySet(); + for (Iterator iterator = parentKeySet.iterator(); iterator.hasNext();) { + String parentKey = (String) iterator.next(); + Set parentValueSet = parentMap.get(parentKey); + for (Iterator iterator2 = parentValueSet.iterator(); iterator2.hasNext();) { + String value = (String) iterator2.next(); + lattice.put(parentKey, value); + } + } + + Set parentSharedLocSet = parentLattice.getSharedLocSet(); + for (Iterator iterator = parentSharedLocSet.iterator(); iterator.hasNext();) { + String parentSharedLoc = (String) iterator.next(); + lattice.addSharedLoc(parentSharedLoc); + } + } + + HierarchyGraph hierarchyGraph = infer.getSimpleHierarchyGraph(desc); + HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc); + + Set hierarchyGraphNodeSet = hierarchyGraph.getNodeSet(); + for (Iterator iterator = hierarchyGraphNodeSet.iterator(); iterator.hasNext();) { + HNode hNode = (HNode) iterator.next(); + if (!hNode.isSkeleton()) { + // here we need to insert an intermediate node for the hNode + System.out.println("local node=" + hNode); + + // 1) find the lowest node m in the lattice that is above hnode in the lattice + // 2) count the number of non-shared nodes d between the hnode and the node m + int numNonSharedNodes; + + HNode SCNode; + if (hNode.isDirectCombinationNode()) { + // this node itself is the lowest node m. it is the first node of the chain + Set combineSet = hierarchyGraph.getCombineSetByCombinationNode(hNode); + SCNode = scGraph.getCombinationNode(combineSet); + numNonSharedNodes = -1; + } else { + + Set aboveSet = new HashSet(); + if (hNode.isCombinationNode()) { + Set combineSkeletonNodeSet = + hierarchyGraph.getCombineSetByCombinationNode(hNode); + + aboveSet.addAll(hierarchyGraph + .getFirstNodeOfCombinationNodeChainSet(combineSkeletonNodeSet)); + SCNode = scGraph.getCombinationNode(combineSkeletonNodeSet); + } else { + System.out.println(" #######hierarchyGraph.getSkeleteNodeSetReachTo(" + hNode + ")=" + + hierarchyGraph.getSkeleteNodeSetReachTo(hNode)); + + aboveSet.addAll(hierarchyGraph.getSkeleteNodeSetReachTo(hNode)); + // assert aboveSet.size() == 1; + SCNode = aboveSet.iterator().next(); + } + + // update above set w.r.t the hierarchy graph with SC nodes + // because the skeleton nodes in the origianl hierarchy graph may merged to a new node + Set endSet = new HashSet(); + for (Iterator iterator2 = aboveSet.iterator(); iterator2.hasNext();) { + HNode aboveNode = (HNode) iterator2.next(); + endSet.add(scGraph.getCurrentHNode(aboveNode)); + } + numNonSharedNodes = hierarchyGraph.countNonSharedNode(hNode, endSet); + + System.out.println(" node=" + hNode + " above=" + endSet + " distance=" + + numNonSharedNodes + " SCNode=" + SCNode); + } + + // 3) convert the node m into a chain of nodes with the last node in the chain having m’s + // outgoing edges. + Set outgoingElements = skeletonLattice.get(SCNode.getName()); + System.out.println(" SCNODE outgoing=" + outgoingElements); + + // 4) If hnode is not a shared location, check if there already exists a local variable + // node that has distance d below m along this chain. If such a node + // does not exist, insert it. + String locName = + getNewLocation(lattice, SCNode.getName(), outgoingElements, numNonSharedNodes, + hNode.isSharedNode()); + System.out.println(" locName=" + locName); + locSummary.addMapHNodeNameToLocationName(hNode.getName(), locName); + + } + } + + return lattice; + } + + public String getNewLocation(SSJavaLattice lattice, String start, Set endSet, + int dist, boolean isShared) { + System.out.println(" getNewLocation:: start=" + start + " endSet=" + endSet + " dist=" + + dist + " isShared=" + isShared); + if (dist == -1) { + return start; + } + return recur_getNewLocation(lattice, start, endSet, dist, isShared); + } + + private String recur_getNewLocation(SSJavaLattice lattice, String cur, + Set endSet, int dist, boolean isShared) { + System.out.println("H"); + Set connectedSet = lattice.get(cur); + if (connectedSet == null) { + connectedSet = new HashSet(); + } + + System.out.println(" recur_getNewLocation cur=" + cur + " dist=" + dist + + " connectedSet=" + connectedSet + " endSet=" + endSet); + + if (dist == 0 && isShared) { + // if the node is shared, + // check if there already exists a shared node that has distance d + 1 on the chain + connectedSet = lattice.get(cur); + if (connectedSet.equals(endSet)) { + // need to insert a new shared location + } else { + assert connectedSet.size() == 1; + String below = connectedSet.iterator().next(); + if (lattice.isSharedLoc(below)) { + return below; + } + } + + // need to insert a new shared location + String newLocName = "ILOC" + (LocationInference.locSeed++); + for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) { + String outNode = (String) iterator.next(); + lattice.put(newLocName, outNode); + } + connectedSet.clear(); + lattice.put(cur, newLocName); + + System.out.println(" INSERT NEW SHARED NODE=" + newLocName + " above=" + cur + + " below=" + lattice.get(newLocName)); + + lattice.addSharedLoc(newLocName); + + return newLocName; + + } + + String next; + if (connectedSet.equals(endSet)) { + // need to insert a new location + String newLocName = "ILOC" + (LocationInference.locSeed++); + connectedSet.clear(); + lattice.put(cur, newLocName); + System.out.println("NEW RELATION=" + lattice.get(cur)); + for (Iterator iterator = endSet.iterator(); iterator.hasNext();) { + String endNode = (String) iterator.next(); + lattice.put(newLocName, endNode); + } + next = newLocName; + System.out.println(" INSERT NEW NODE=" + newLocName + " above=" + cur + " below=" + + endSet); + } else { + assert connectedSet.size() == 1; + next = connectedSet.iterator().next(); + } + System.out.println(" next=" + next); + + // if (dist == 0) { + + // if (isShared) { + + // // if the node is shared, + // // check if there already exists a shared node that has distance d + 1 on the chain + // + // connectedSet = lattice.get(next); + // + // if (connectedSet.equals(endSet)) { + // // need to insert a new shared location + // } else { + // assert connectedSet.size() != 1; + // String below = connectedSet.iterator().next(); + // if (lattice.isSharedLoc(below)) { + // return below; + // } + // } + // + // // need to insert a new shared location + // String newLocName = "ILOC" + (LocationInference.locSeed++); + // for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) { + // String outNode = (String) iterator.next(); + // lattice.put(newLocName, outNode); + // } + // connectedSet.clear(); + // lattice.put(next, newLocName); + // + // System.out.println(" INSERT NEW SHARED NODE=" + newLocName + " above=" + next + // + " below=" + lattice.get(newLocName)); + // + // lattice.addSharedLoc(newLocName); + // + // next = newLocName; + // + // } + // + // return next; + + // } else { + + if (dist == 0) { + return next; + } else { + if (!lattice.isSharedLoc(next)) { + dist--; + } + return recur_getNewLocation(lattice, next, endSet, dist, isShared); + } + + // } + + // /////////////////////////////////////////////// + + // if (dist == 0) { + // return cur; + // } else if (connectedSet.equals(endSet)) { + // // need to insert a new location + // String newLocName = "ILOC" + (LocationInference.locSeed++); + // connectedSet.clear(); + // lattice.put(cur, newLocName); + // for (Iterator iterator = endSet.iterator(); iterator.hasNext();) { + // String endNode = (String) iterator.next(); + // lattice.put(newLocName, endNode); + // } + // return recur_getNewLocation(lattice, newLocName, endSet, --dist, isShared); + // } else { + // assert connectedSet.size() != 1; + // String next = connectedSet.iterator().next(); + // return recur_getNewLocation(lattice, next, endSet, --dist, isShared); + // } + + } + + public SSJavaLattice insertIntermediateNodesToStraightLine2(Descriptor desc, + SSJavaLattice skeletonLattice) { // copy nodes/edges from the parent method/class if possible SSJavaLattice lattice = skeletonLattice.clone(); @@ -265,7 +518,7 @@ public class BuildLattice { // 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);