X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FBuildLattice.java;h=adce54e507835d538961940090168271e27847a0;hp=61a083274e84e97c7968442d8bc6d5d502d343f8;hb=d06acf1c0be1fa63f5505cbcc7943676c4c0f008;hpb=99040b5e3460f3e28210e6b672bc8b46545a775e diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index 61a08327..adce54e5 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,14 +22,23 @@ 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(); this.mapHNodeToHighestIndex = new HashMap(); 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) { @@ -35,7 +46,8 @@ public class BuildLattice { HierarchyGraph inputGraph = infer.getSkeletonCombinationHierarchyGraph(desc); LocationSummary locSummary = infer.getLocationSummary(desc); - HierarchyGraph naiveGraph = infer.getSimpleHierarchyGraph(desc); + HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc); + HierarchyGraph naiveGraph = simpleGraph.clone(); // I don't think we need to keep the below if statement anymore // because hierarchy graph does not have any composite location @@ -74,7 +86,16 @@ public class BuildLattice { SSJavaLattice naive_lattice = buildLattice(desc, naiveBasisSet, naiveGraph, null, naive_mapImSucc); - LocationInference.numLocationsNaive += naive_lattice.getKeySet().size(); + int numLocs = naive_lattice.getKeySet().size(); + LocationInference.numLocationsNaive += numLocs; + infer.mapNumLocsMapNaive.put(desc, new Integer(numLocs)); + + int numPaths = naive_lattice.countPaths(); + infer.mapNumPathsMapNaive.put(desc, new Integer(numPaths)); + + System.out.println(desc + " numPaths=" + numPaths + " numLocs=" + + naive_lattice.getKeySet().size()); + infer.addNaiveLattice(desc, naive_lattice); } @@ -258,403 +279,277 @@ public class BuildLattice { 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); + System.out.println("\n#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; + // int numNonSharedNodes; + 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); + + System.out.println(" # direct combine node::combineSkeletonNodeSet=" + combineSet); + SCNode = scGraph.getCombinationNode(combineSet); - numNonSharedNodes = -1; + // numNonSharedNodes = -1; + dist = 0; + if (hNode.isSharedNode()) { + trace.add("S"); + } else { + trace.add("N"); + } } else { Set aboveSet = new HashSet(); if (hNode.isCombinationNode()) { - Set combineSkeletonNodeSet = - hierarchyGraph.getCombineSetByCombinationNode(hNode); + // the current node is a combination node + combineSkeletonNodeSet = hierarchyGraph.getCombineSetByCombinationNode(hNode); + System.out.println(" combineSkeletonNodeSet=" + combineSkeletonNodeSet + + " combinationNode=" + scGraph.getCombinationNode(combineSkeletonNodeSet)); + + scGraph.getCombinationNode(combineSkeletonNodeSet); + System.out.println(" firstnodeOfSimpleGraph=" + + hierarchyGraph.getFirstNodeOfCombinationNodeChainSet(combineSkeletonNodeSet)); aboveSet.addAll(hierarchyGraph .getFirstNodeOfCombinationNodeChainSet(combineSkeletonNodeSet)); + SCNode = scGraph.getCombinationNode(combineSkeletonNodeSet); + } else { - System.out.println(" #######hierarchyGraph.getSkeleteNodeSetReachTo(" + hNode + ")=" - + hierarchyGraph.getSkeleteNodeSetReachTo(hNode)); + // the current node is not a combination node + // there is only one parent node which should be skeleton node. + + // System.out.println(" hierarchyGraph.getSkeleteNodeSetReachTo(" + hNode + ")=" + // + hierarchyGraph.getSkeleteNodeSetReachTo(hNode)); + + Set reachToSet = hierarchyGraph.getSkeleteNodeSetReachTo(hNode); + for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) { + HNode reachToNode = (HNode) iterator2.next(); + aboveSet.add(scGraph.getCurrentHNode(reachToNode)); + } - 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 + // because the skeleton nodes in the original hierarchy graph may be 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)); + endSet.add(hierarchyGraph.getCurrentHNode(aboveNode)); } - numNonSharedNodes = hierarchyGraph.countNonSharedNode(hNode, endSet); - System.out.println(" node=" + hNode + " above=" + endSet + " distance=" - + numNonSharedNodes + " SCNode=" + SCNode); + trace = hierarchyGraph.computeDistance(hNode, endSet, combineSkeletonNodeSet); + + System.out.println(" COUNT-RESULT::start=" + hNode + " end=" + endSet + " trace=" + + trace); } - // 3) convert the node m into a chain of nodes with the last node in the chain having m’s + // 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); + Set outgoingSCNodeSet = scGraph.getOutgoingNodeSet(SCNode); + System.out.println(" outgoing scnode set from " + SCNode + "=" + outgoingSCNodeSet); + + // convert hnodes to location names + String startLocName = locSummary.getLocationName(SCNode.getName()); + Set outgoingLocNameSet = new HashSet(); + for (Iterator iterator2 = outgoingSCNodeSet.iterator(); iterator2.hasNext();) { + HNode outSCNode = (HNode) iterator2.next(); + String locName = locSummary.getLocationName(outSCNode.getName()); + if (!locName.equals(outSCNode.getName())) { + System.out.println(" outSCNode=" + outSCNode + " -> locName=" + + locName); + } + outgoingLocNameSet.add(locName); + } + + if (outgoingLocNameSet.isEmpty()) { + 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, SCNode.getName(), outgoingElements, numNonSharedNodes, - hNode.isSharedNode()); - System.out.println(" locName=" + locName); + getNewLocation(desc, startLocName, outgoingLocNameSet, trace, hNode.isSharedNode()); + + System.out.println(" ###hNode=" + hNode + "---->locName=" + locName); locSummary.addMapHNodeNameToLocationName(hNode.getName(), locName); } } + insertLocalLocations(desc, lattice); + 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 void insertLocalLocations(Descriptor desc, SSJavaLattice lattice) { - 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(); - } + Map> map = getLineListMap(desc); + System.out.println("####MAP=" + map); - System.out.println(" recur_getNewLocation cur=" + cur + " dist=" + dist - + " connectedSet=" + connectedSet + " endSet=" + endSet); + Set lineIdSet = map.keySet(); + for (Iterator iterator = lineIdSet.iterator(); iterator.hasNext();) { + LineIdentifier lineId = (LineIdentifier) iterator.next(); - 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; - } - } + LinkedList list = map.get(lineId); - // 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); + String higherLocName = lineId.startLoc; + Set endLocNameSet = lineId.lowerLocSet; - System.out.println(" INSERT NEW SHARED NODE=" + newLocName + " above=" + cur - + " below=" + lattice.get(newLocName)); + for (int i = 0; i < list.size(); i++) { + LocPair pair = list.get(i); - lattice.addSharedLoc(newLocName); + if (pair.nonShared != null) { - return newLocName; + 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; + } - 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(); - - 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); - } + private void addLocalLocation(SSJavaLattice lattice, String localLoc) { + if (!mapLatticeToLocalLocSet.containsKey(lattice)) { + mapLatticeToLocalLocSet.put(lattice, new HashSet()); } + mapLatticeToLocalLocSet.get(lattice).add(localLoc); + } - // //// - - // perform DFS that starts from each skeleton/combination node and ends by another - // skeleton/combination node - - mapSharedNodeToTripleItem.clear(); - - HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc); - HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc); - LocationSummary locSummary = infer.getLocationSummary(desc); + private boolean isLocalLocation(SSJavaLattice lattice, String localLoc) { + if (mapLatticeToLocalLocSet.containsKey(lattice)) { + return mapLatticeToLocalLocSet.get(lattice).contains(localLoc); + } + return false; + } - Set visited = new HashSet(); + public Map getInterLocMap(Descriptor desc) { + if (!mapDescToInterLocMap.containsKey(desc)) { + mapDescToInterLocMap.put(desc, new HashMap()); + } + return mapDescToInterLocMap.get(desc); + } - Set nodeSet = simpleGraph.getNodeSet(); + public Map> getLineListMap(Descriptor desc) { + if (!mapDescToLineListMap.containsKey(desc)) { + mapDescToLineListMap.put(desc, new HashMap>()); + } + return mapDescToLineListMap.get(desc); + } - Map mapIntermediateLoc = getIntermediateLocMap(desc); - // Map mapIntermediateLoc = new HashMap(); + public LinkedList getLineList(Descriptor desc, LineIdentifier lineId) { + Map> map = getLineListMap(desc); + if (!map.containsKey(lineId)) { + map.put(lineId, new LinkedList()); + } + return map.get(lineId); + } - // 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); + private String generateNewLocName() { + String newLocName = "ILOC" + (LocationInference.locSeed++); + System.out.println("newLocName=" + newLocName); + return newLocName; + } - if (node.isSkeleton() && (!visited.contains(node))) { - visited.add(node); + public String getNewLocation(Descriptor desc, String start, Set endSet, + Stack trace, boolean isShared) { - Set outSet = simpleGraph.getOutgoingNodeSet(node); - for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) { - HNode outNode = (HNode) iterator2.next(); + System.out.println(" #GetNewLocation start=" + start + " endSet=" + endSet + " trace=" + + trace); - if (!outNode.isSkeleton()) { - if (outNode.isCombinationNode()) { - if (visited.containsAll(simpleGraph.getIncomingNodeSet(outNode))) { - // if (needToExpandCombinationNode(desc, 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); - 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; - // } - - // TODO - // Set endNodeSetFromSimpleGraph = - // simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null); - // Set endCombNodeSet = new HashSet(); - // for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); - // iterator3.hasNext();) { - // HNode endNode = (HNode) iterator3.next(); - // endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode)); - // } - - Set endCombNodeSet = scGraph.getOutgoingNodeSet(startNode); - - // System.out.println("endCombNodeSet=" + endCombNodeSet); - visited.add(outNode); - if (endCombNodeSet.size() > 0) { - // follows the straight line up to another skeleton/combination node - endCombNodeSet = removeTransitivelyReachToNode(desc, startNode, endCombNodeSet); - } 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(LocationInference.BOTTOMHNODE); - } - - recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited, - mapIntermediateLoc, 1, locSummary, outNode); - } + LineIdentifier lineId = new LineIdentifier(start, endSet); + LinkedList list = getLineList(desc, lineId); - } + 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(); } - } 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 - if (simpleGraph.getIncomingNodeSet(node).size() == 0) { - - // this node will be directly connected to the TOP location - // start adding the following nodes from this node - - Set endNodeSetFromSimpleGraph = - simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(node, null); - - 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); - HNode startNode = LocationInference.TOPHNODE; - visited.add(startNode); - if (endCombNodeSet.size() > 0) { - // follows the straight line up to another skeleton/combination node - // endCombNodeSet = removeTransitivelyReachToNode(desc, node, endCombNodeSet); - recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited, - mapIntermediateLoc, 1, locSummary, node); - } - + return pair.shared; + } else { + 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); } - // add shared locations - Set sharedNodeSet = mapSharedNodeToTripleItem.keySet(); - for (Iterator iterator = sharedNodeSet.iterator(); iterator.hasNext();) { - HNode sharedNode = (HNode) iterator.next(); - TripleItem item = mapSharedNodeToTripleItem.get(sharedNode); - String nonSharedLocName = mapIntermediateLoc.get(item); + } - System.out.println("sharedNode=" + sharedNode + " locName=" + nonSharedLocName); + private String recur_getNewLocation(int idx, LinkedList list, Stack trace) { - String newLocName; - if (locSummary.getHNodeNameSetByLatticeLoationName(nonSharedLocName) != null - && !lattice.isSharedLoc(nonSharedLocName)) { - // need to generate a new shared location in the lattice, which is one level lower than the - // 'locName' location - newLocName = "ILOC" + (LocationInference.locSeed++); + String curType = trace.pop(); + boolean isCurShared = false; + if (curType.equals("S")) { + isCurShared = true; + } - // Set aboveElementSet = getAboveElementSet(lattice, locName); - Set belowElementSet = new HashSet(); - belowElementSet.addAll(lattice.get(nonSharedLocName)); + if (list.size() <= idx) { + // need to insert a new pair for the idx + list.add(new LocPair()); + } - System.out.println("nonSharedLocName=" + nonSharedLocName + " belowElementSet=" - + belowElementSet + " newLocName=" + newLocName); + // 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(); + } - lattice.insertNewLocationBetween(nonSharedLocName, belowElementSet, newLocName); + if (trace.isEmpty()) { + if (isCurShared) { + return pair.shared; } else { - newLocName = nonSharedLocName; - } - - lattice.addSharedLoc(newLocName); - HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc); - Set descSet = graph.getDescSetOfNode(sharedNode); - for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) { - Descriptor d = (Descriptor) iterator2.next(); - locSummary.addMapHNodeNameToLocationName(d.getSymbol(), newLocName); + return pair.nonShared; } - locSummary.addMapHNodeNameToLocationName(sharedNode.getName(), newLocName); - } - return lattice; - + idx++; + return recur_getNewLocation(idx, list, trace); } private Set getAboveElementSet(SSJavaLattice lattice, String loc) { @@ -1277,6 +1172,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; @@ -1332,4 +1344,5 @@ class TripleItem { } return rtr; } + }