From 3e70000b1b45e43a58585fc075ee721adf2a0af0 Mon Sep 17 00:00:00 2001 From: yeom Date: Tue, 26 Feb 2013 02:33:32 +0000 Subject: [PATCH] changes. --- Robust/src/Analysis/SSJava/BuildLattice.java | 362 +++++++++++++----- .../src/Analysis/SSJava/HierarchyGraph.java | 80 +++- 2 files changed, 338 insertions(+), 104 deletions(-) diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index c26b70a8..aa8ac139 100644 --- a/Robust/src/Analysis/SSJava/BuildLattice.java +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -3,8 +3,10 @@ package Analysis.SSJava; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; +import java.util.LinkedList; import java.util.Map; import java.util.Set; +import java.util.Stack; import IR.ClassDescriptor; import IR.Descriptor; @@ -20,10 +22,14 @@ public class BuildLattice { private Map> mapDescToIntermediateLocMap; + private Map> mapDescToInterLocMap; + private Map, Integer> mapItemToHighestIndex; private Map, Set> mapLatticeToLocalLocSet; + private Map>> mapDescToLineListMap; + public BuildLattice(LocationInference infer) { this.infer = infer; this.mapSharedNodeToTripleItem = new HashMap(); @@ -31,6 +37,8 @@ public class BuildLattice { this.mapItemToHighestIndex = new HashMap, Integer>(); this.mapDescToIntermediateLocMap = new HashMap>(); this.mapLatticeToLocalLocSet = new HashMap, Set>(); + this.mapDescToInterLocMap = new HashMap>(); + this.mapDescToLineListMap = new HashMap>>(); } public SSJavaLattice buildLattice(Descriptor desc) { @@ -266,10 +274,11 @@ public class BuildLattice { // 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; - int dist; + int dist = 0; HNode SCNode; Set combineSkeletonNodeSet = null; + Stack trace = new Stack(); if (hNode.isDirectCombinationNode()) { // this node itself is the lowest node m. it is the first node of the chain Set combineSet = hierarchyGraph.getCombineSetByCombinationNode(hNode); @@ -279,6 +288,11 @@ public class BuildLattice { SCNode = scGraph.getCombinationNode(combineSet); // numNonSharedNodes = -1; dist = 0; + if (hNode.isSharedNode()) { + trace.add("S"); + } else { + trace.add("N"); + } } else { Set aboveSet = new HashSet(); @@ -317,13 +331,10 @@ public class BuildLattice { endSet.add(hierarchyGraph.getCurrentHNode(aboveNode)); } - dist = hierarchyGraph.computeDistance(hNode, endSet, combineSkeletonNodeSet); - System.out.println("##### " + hNode + "::dist=" + dist); - - // numNonSharedNodes = hierarchyGraph.countNonSharedNode(hNode, endSet); + trace = hierarchyGraph.computeDistance(hNode, endSet, combineSkeletonNodeSet); - System.out.println(" COUNT-RESULT::node=" + hNode + " above=" + endSet + " distance=" - + dist + " SCNode=" + SCNode); + System.out.println(" COUNT-RESULT::node=" + hNode + " above=" + endSet + " trace=" + + trace + " SCNode=" + SCNode); } // 3) convert the node m into a chain of nodes with the last node in the chain having m’s @@ -348,20 +359,75 @@ public class BuildLattice { outgoingLocNameSet.add(lattice.getBottomItem()); } + if (hNode.isCombinationNode()) { + System.out.println("make sure that the first node corresponds to the COMB node=" + + startLocName); + LineIdentifier lineId = new LineIdentifier(startLocName, outgoingLocNameSet); + LinkedList list = getLineList(desc, lineId); + // make sure that the first node corresponds to the COMB node + if (list.size() <= 0) { + list.add(new LocPair()); + } + LocPair firstPair = list.get(0); + firstPair.nonShared = startLocName; + } + // 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, startLocName, outgoingLocNameSet, dist, hNode.isSharedNode()); + getNewLocation(desc, startLocName, outgoingLocNameSet, trace, hNode.isSharedNode()); + System.out.println(" ###hNode=" + hNode + "---->locName=" + locName); locSummary.addMapHNodeNameToLocationName(hNode.getName(), locName); } } + insertLocalLocations(desc, lattice); + return lattice; } + private void insertLocalLocations(Descriptor desc, SSJavaLattice lattice) { + + Map> map = getLineListMap(desc); + System.out.println("####MAP=" + map); + + Set lineIdSet = map.keySet(); + for (Iterator iterator = lineIdSet.iterator(); iterator.hasNext();) { + LineIdentifier lineId = (LineIdentifier) iterator.next(); + + LinkedList list = map.get(lineId); + + String higherLocName = lineId.startLoc; + Set endLocNameSet = lineId.lowerLocSet; + + for (int i = 0; i < list.size(); i++) { + LocPair pair = list.get(i); + + if (pair.nonShared != null) { + + if (!lattice.getKeySet().contains(pair.nonShared)) { + lattice.insertNewLocationBetween(higherLocName, endLocNameSet, pair.nonShared); + } + higherLocName = pair.nonShared; + } + + if (pair.shared != null) { + if (!lattice.getKeySet().contains(pair.shared)) { + lattice.insertNewLocationBetween(higherLocName, endLocNameSet, pair.shared); + lattice.addSharedLoc(pair.shared); + } + higherLocName = pair.shared; + } + + } + + } + + } + private void addLocalLocation(SSJavaLattice lattice, String localLoc) { if (!mapLatticeToLocalLocSet.containsKey(lattice)) { mapLatticeToLocalLocSet.put(lattice, new HashSet()); @@ -376,114 +442,100 @@ public class BuildLattice { return false; } - 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); - return recur_getNewLocation(lattice, start, start, endSet, dist, isShared); + public Map getInterLocMap(Descriptor desc) { + if (!mapDescToInterLocMap.containsKey(desc)) { + mapDescToInterLocMap.put(desc, new HashMap()); + } + return mapDescToInterLocMap.get(desc); } - private String recur_getNewLocation(SSJavaLattice lattice, String start, String cur, - Set endSet, int dist, boolean isShared) { + public Map> getLineListMap(Descriptor desc) { + if (!mapDescToLineListMap.containsKey(desc)) { + mapDescToLineListMap.put(desc, new HashMap>()); + } + return mapDescToLineListMap.get(desc); + } - System.out.println(" recur_getNewLocation cur=" + cur + " dist=" + dist); + public LinkedList getLineList(Descriptor desc, LineIdentifier lineId) { + Map> map = getLineListMap(desc); + if (!map.containsKey(lineId)) { + map.put(lineId, new LinkedList()); + } + return map.get(lineId); + } - if (dist == 0) { - if (isShared) { - // first check if there already exists a non-shared node at distance d - if (!isLocalLocation(lattice, cur) && !start.equals(cur)) { - // if not, need to insert a new SHARED local location at this point - System.out.println("if not, need to insert a new SHARED local location at this point"); - String newLocName = "ILOC" + (LocationInference.locSeed++); - Set lowerSet = new HashSet(); - lowerSet.addAll(lattice.get(cur)); - lattice.insertNewLocationBetween(cur, lowerSet, newLocName); - lattice.addSharedLoc(newLocName); - addLocalLocation(lattice, newLocName); - return newLocName; - } - // if there exists a non-shared node at distance d - // then try to add a new SHARED loc at distance d+1 + private String generateNewLocName() { + String newLocName = "ILOC" + (LocationInference.locSeed++); + System.out.println("newLocName=" + newLocName); + return newLocName; + } - Set connectedSet = lattice.get(cur); - if (connectedSet == null) { - connectedSet = new HashSet(); - } - System.out.println("cur=" + cur + " connectedSet=" + connectedSet); + public String getNewLocation(Descriptor desc, String start, Set endSet, + Stack trace, boolean isShared) { - // check if there already exists a shared node that has distance d + 1 on the chain - boolean needToInsertSharedNode = false; - if (connectedSet.equals(endSet)) { - needToInsertSharedNode = true; - } else { - // in this case, the current node is in the middle of the chain - assert connectedSet.size() == 1; - String below = connectedSet.iterator().next(); - if (lattice.isSharedLoc(below)) { - return below; - } else { - needToInsertSharedNode = true; - } - } + System.out.println(" #GetNewLocation start=" + start + " endSet=" + endSet + " trace=" + + trace); - if (needToInsertSharedNode) { - // no shared local location at d+1, need to insert it! - String newSharedLocName = "ILOC" + (LocationInference.locSeed++); - Set lowerSet = new HashSet(); - lowerSet.addAll(connectedSet); - lattice.insertNewLocationBetween(cur, lowerSet, newSharedLocName); - lattice.addSharedLoc(newSharedLocName); - addLocalLocation(lattice, newSharedLocName); - System.out.println(" INSERT NEW SHARED LOC=" + newSharedLocName); - cur = newSharedLocName; - } + LineIdentifier lineId = new LineIdentifier(start, endSet); + LinkedList list = getLineList(desc, lineId); - return cur; + int locPairIdx = trace.size() - 1; + LocPair pair; + if (list.size() > locPairIdx) { + // there already exsits a list of nodes up to the current one + pair = list.get(locPairIdx); + // check if we need to add a new shared or non-shred node to the pair + if (isShared) { + if (pair.shared == null) { + pair.shared = generateNewLocName(); + } + return pair.shared; } else { - // if the node is not a shared one, - // check if the cur node is a shared node - if (lattice.isSharedLoc(cur)) { - // here, we need to add a new local NONSHARED node above cur - - String newLocName = "ILOC" + (LocationInference.locSeed++); - lattice.insertNewLocationAtOneLevelHigher(cur, newLocName); - addLocalLocation(lattice, newLocName); - System.out.println(" INSERT NEW LOC=" + newLocName + " ABOVE=" + cur); - return newLocName; - } else { - // if cur is not shared, return it! - return cur; + if (pair.nonShared == null) { + pair.nonShared = generateNewLocName(); } + return pair.nonShared; } + + } else { + // we need to set up a chain of intermediate nodes to the current one. + return recur_getNewLocation(0, list, trace); } - Set connectedSet = lattice.get(cur); - if (connectedSet == null) { - connectedSet = new HashSet(); + } + + private String recur_getNewLocation(int idx, LinkedList list, Stack trace) { + + String curType = trace.pop(); + boolean isCurShared = false; + if (curType.equals("S")) { + isCurShared = true; } - System.out.println("cur=" + cur + " connected set=" + connectedSet); - if (cur.equals(lattice.getTopItem()) || connectedSet.equals(endSet)) { - // if not, need to insert a new local location at this point - System.out.println("NEED TO INSERT A NEW LOCAL LOC FOR NEXT connectedSet=" + connectedSet); - String newLocName = "ILOC" + (LocationInference.locSeed++); - Set lowerSet = new HashSet(); - lowerSet.addAll(connectedSet); - lattice.insertNewLocationBetween(cur, lowerSet, newLocName); - addLocalLocation(lattice, newLocName); - cur = newLocName; - } else { - // in this case, the current node is in the middle of the chain - assert connectedSet.size() == 1; - cur = connectedSet.iterator().next(); + if (list.size() <= idx) { + // need to insert a new pair for the idx + list.add(new LocPair()); + } + + // here, the list already has a pair for the idx + LocPair pair = list.get(idx); + if (isCurShared && pair.shared == null) { + pair.shared = generateNewLocName(); + } else if (!isCurShared && pair.nonShared == null) { + pair.nonShared = generateNewLocName(); } - if (!lattice.isSharedLoc(cur)) { - dist--; + if (trace.isEmpty()) { + if (isCurShared) { + return pair.shared; + } else { + return pair.nonShared; + } } - return recur_getNewLocation(lattice, start, cur, endSet, dist, isShared); + idx++; + return recur_getNewLocation(idx, list, trace); } private Set getAboveElementSet(SSJavaLattice lattice, String loc) { @@ -1106,6 +1158,123 @@ class Identifier { } +class LocPair { + public String nonShared; + public String shared; + + public int hashCode() { + int h = 0; + if (nonShared != null) { + h = nonShared.hashCode(); + } + if (shared != null) { + h = shared.hashCode(); + } + return h; + } + + public boolean equals(Object obj) { + + if (obj instanceof LocPair) { + LocPair in = (LocPair) obj; + + if ((nonShared == null && in.nonShared == null) + || (nonShared != null && nonShared.equals(in.nonShared))) { + + if ((shared == null && in.shared == null) || (shared != null && shared.equals(in.shared))) { + return true; + } + + } + + } + + return false; + } + + public String toString() { + String rtr = "<" + nonShared + "," + shared + ">"; + return rtr; + } +} + +class LineIdentifier { + public String startLoc; + public Set lowerLocSet; + + public LineIdentifier(String s, Set lSet) { + startLoc = s; + lowerLocSet = lSet; + } + + public int hashCode() { + int h = 0; + h = startLoc.hashCode(); + return h + lowerLocSet.hashCode(); + } + + public boolean equals(Object obj) { + + if (obj instanceof LineIdentifier) { + LineIdentifier in = (LineIdentifier) obj; + if (startLoc.equals(in.startLoc) && lowerLocSet.equals(in.lowerLocSet)) { + return true; + } + } + + return false; + } + + public String toString() { + String rtr = startLoc + "->" + lowerLocSet; + return rtr; + } + +} + +class InterLocItem { + public String startLoc; + public Set lowerLocSet; + public int idx; + + public InterLocItem(String h, Set l, int i) { + startLoc = h; + lowerLocSet = l; + idx = i; + } + + public int hashCode() { + + int h = 0; + if (startLoc != null) { + h = startLoc.hashCode(); + } + + return h + lowerLocSet.hashCode() + idx; + } + + public boolean equals(Object obj) { + + if (obj instanceof InterLocItem) { + InterLocItem in = (InterLocItem) obj; + if ((startLoc == null || (startLoc != null && startLoc.equals(in.startLoc))) + && lowerLocSet.equals(in.lowerLocSet) && idx == in.idx) { + return true; + } + } + + return false; + } + + public String toString() { + String rtr = startLoc + "-" + idx + "->" + lowerLocSet; + if (idx % 2 != 0) { + rtr += " S"; + } + return rtr; + } +} + class TripleItem { public HNode higherNode; public Set lowerNodeSet; @@ -1161,4 +1330,5 @@ class TripleItem { } return rtr; } + } diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index c14864e7..145cf8af 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -8,10 +8,10 @@ import java.util.HashSet; import java.util.Iterator; import java.util.Map; import java.util.Set; +import java.util.Stack; import IR.Descriptor; import IR.FieldDescriptor; -import IR.VarDescriptor; public class HierarchyGraph { @@ -369,6 +369,7 @@ public class HierarchyGraph { continue; } + // System.out.println("node1=" + node1 + " vs node2=" + node2); if (!isEligibleForMerging(node1, node2)) { continue; } @@ -378,10 +379,15 @@ public class HierarchyGraph { Set incomingNodeSet2 = getIncomingNodeSet(node2); Set outgoingNodeSet2 = getOutgoingNodeSet(node2); + // System.out.println(node1 + " " + node2 + " MERGING incoming?=" + incomingNodeSet1 + // + " vs " + incomingNodeSet2); + // System.out.println(node1 + " " + node2 + " MERGING outgoing?=" + outgoingNodeSet1 + // + " vs " + outgoingNodeSet2); + if (incomingNodeSet1.equals(incomingNodeSet2) && outgoingNodeSet1.equals(outgoingNodeSet2)) { // need to merge node1 and node2 - + // System.out.println("MERGE!!!!!!!!!!!!!"); // /////////////// // merge two nodes only if every hierarchy graph in the inheritance hierarchy // that includes both nodes allows the merging of them... @@ -422,7 +428,7 @@ public class HierarchyGraph { } return true; } - return false; + return true; } private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) { @@ -993,7 +999,16 @@ public class HierarchyGraph { Set reachToSet = getSkeleteNodeSetReachTo(node); // Set tempSet = removeTransitivelyReachToSet(reachToSet); // reachToSet = removeTransitivelyReachToSet(reachToSet); - Set tempSet = reachToSet; + + Set curReachToSet = new HashSet(); + for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) { + HNode reachSkeletonNode = (HNode) iterator2.next(); + curReachToSet.add(getCurrentHNode(reachSkeletonNode)); + } + + System.out.println("-curReachToSet=" + curReachToSet + " reachToSet=" + reachToSet); + + reachToSet = curReachToSet; // System.out.println("$node=" + node + " reachToNodeSet=" + reachToSet + " tempSet=" // + tempSet); if (reachToSet.size() > 1) { @@ -1397,12 +1412,61 @@ public class HierarchyGraph { return max; } - public int computeDistance(HNode startNode, Set endNodeSet, Set combineSet) { + public Stack computeDistance(HNode startNode, Set endNodeSet, Set combineSet) { System.out.println("#####computeDistance startNode=" + startNode + " endNode=" + endNodeSet); - return recur_computeDistance(startNode, startNode, endNodeSet, 0, combineSet); + Stack trace = new Stack(); + return recur_computeDistance(startNode, endNodeSet, 0, combineSet, trace); } - private int recur_computeDistance(HNode startNode, HNode curNode, Set endNodeSet, + private Stack recur_computeDistance(HNode curNode, Set endNodeSet, int count, + Set combineSet, Stack trace) { + + if (!curNode.isSkeleton()) { + if (curNode.isSharedNode()) { + trace.add("S"); + } else { + trace.add("N"); + } + } + + + if (endNodeSet.contains(curNode)) { + // it reaches to one of endNodeSet + return trace; + } + + Set inNodeSet = getIncomingNodeSet(curNode); + + int curMaxDistance = 0; + Stack curMaxTrace = (Stack) trace.clone(); + ; + for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { + HNode inNode = (HNode) iterator.next(); + // traverse more... + + if (inNode.isCombinationNode() && combineSet != null) { + // check if inNode have the same combination set of the starting node + Set inNodeCombineSet = getCombineSetByCombinationNode(inNode); + if (!inNodeCombineSet.equals(combineSet)) { + continue; + } + } + + System.out.println(" traverse more to" + inNode + " before-trace=" + trace); + Stack newTrace = (Stack) trace.clone(); + Stack curTrace = + recur_computeDistance(inNode, endNodeSet, count, combineSet, newTrace); + System.out.println("curTrace=" + curTrace); + + if (curTrace != null && curTrace.size() > curMaxDistance) { + curMaxTrace = curTrace; + curMaxDistance = curTrace.size(); + } + } + return curMaxTrace; + } + + private int recur_computeDistance2(HNode startNode, HNode curNode, Set endNodeSet, int count, Set combineSet) { if (!curNode.equals(startNode)) { @@ -1431,7 +1495,7 @@ public class HierarchyGraph { } System.out.println(" traverse more to" + inNode + " before-count=" + count); - int dist = recur_computeDistance(startNode, inNode, endNodeSet, count, combineSet); + int dist = recur_computeDistance2(startNode, inNode, endNodeSet, count, combineSet); if (dist > curMaxDistance) { curMaxDistance = dist; } -- 2.34.1