From dfaefc442488f69bf9f33038ddafb7ff47a67d8d Mon Sep 17 00:00:00 2001 From: yeom Date: Fri, 13 Jul 2012 19:09:33 +0000 Subject: [PATCH] changes. --- Robust/src/Analysis/SSJava/FlowGraph.java | 138 ++++++- Robust/src/Analysis/SSJava/FlowNode.java | 12 + .../Analysis/SSJava/LocationInference.java | 363 ++++++++++++++++-- Robust/src/Analysis/SSJava/LocationInfo.java | 67 ++++ .../Analysis/SSJava/MethodLocationInfo.java | 27 +- Robust/src/Analysis/SSJava/SSJavaLattice.java | 111 ++++++ Robust/src/Util/Lattice.java | 5 + 7 files changed, 690 insertions(+), 33 deletions(-) create mode 100644 Robust/src/Analysis/SSJava/LocationInfo.java diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java index ce0021ca..6382ed00 100644 --- a/Robust/src/Analysis/SSJava/FlowGraph.java +++ b/Robust/src/Analysis/SSJava/FlowGraph.java @@ -1,7 +1,6 @@ package Analysis.SSJava; import java.io.BufferedWriter; -import java.io.File; import java.io.FileWriter; import java.io.IOException; import java.util.HashMap; @@ -9,10 +8,8 @@ import java.util.HashSet; import java.util.Iterator; import java.util.Map; import java.util.Set; -import java.util.Map.Entry; -import Analysis.OoOJava.ConflictEdge; -import Analysis.OoOJava.ConflictNode; +import IR.ClassDescriptor; import IR.Descriptor; import IR.FieldDescriptor; import IR.MethodDescriptor; @@ -60,6 +57,10 @@ public class FlowGraph { return nodeSet; } + public MethodDescriptor getMethodDescriptor() { + return md; + } + public Set getParameterNodeSet() { Set paramNodeSet = new HashSet(); for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { @@ -186,6 +187,135 @@ public class FlowGraph { return returnNodeSet; } + public Set getReachableFlowNodeSet(FlowNode fn) { + Set set = new HashSet(); + getReachableFlowNodeSet(fn, set); + return set; + } + + private void getReachableFlowNodeSet(FlowNode fn, Set visited) { + + for (Iterator iterator = fn.getOutEdgeSet().iterator(); iterator.hasNext();) { + FlowEdge edge = (FlowEdge) iterator.next(); + + if (fn.equals(getFlowNode(edge.getInitTuple()))) { + + FlowNode dstNode = getFlowNode(edge.getEndTuple()); + + if (!visited.contains(dstNode)) { + visited.add(dstNode); + getReachableFlowNodeSet(dstNode, visited); + } + } + } + + } + + public Set> getReachableFlowTupleSet(Set> visited, FlowNode fn) { + for (Iterator iterator = fn.getOutEdgeSet().iterator(); iterator.hasNext();) { + FlowEdge edge = (FlowEdge) iterator.next(); + + if (fn.getDescTuple().equals(edge.getInitTuple())) { + FlowNode dstNode = getFlowNode(edge.getEndTuple()); + NTuple dstTuple = getLocationTuple(dstNode); + + if (!visited.contains(dstTuple)) { + visited.add(dstTuple); + visited.addAll(getReachableFlowTupleSet(visited, dstNode)); + } + + } + } + return visited; + } + + public NTuple getLocationTuple(FlowNode fn) { + + NTuple descTuple = fn.getDescTuple(); + + NTuple locTuple = new NTuple(); + + ClassDescriptor cd = null; + + for (int i = 0; i < descTuple.size(); i++) { + Descriptor d = descTuple.get(i); + Location loc; + if (i == 0) { + loc = new Location(md, d.getSymbol()); + cd = ((VarDescriptor) d).getType().getClassDesc(); + } else { + loc = new Location(cd, d.getSymbol()); + cd = ((FieldDescriptor) d).getType().getClassDesc(); + } + locTuple.add(loc); + } + + return locTuple; + } + + public Set getIncomingFlowNodeSet(FlowNode node) { + Set set = new HashSet(); + getIncomingFlowNodeSet(node, set); + return set; + } + + public void getIncomingFlowNodeSet(FlowNode node, Set visited) { + + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode curNode = (FlowNode) iterator.next(); + Set edgeSet = curNode.getOutEdgeSet(); + + for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) { + FlowEdge flowEdge = (FlowEdge) iterator2.next(); + + if (node.equals(getFlowNode(flowEdge.getEndTuple()))) { + FlowNode incomingNode = getFlowNode(flowEdge.getInitTuple()); + + if (!visited.contains(incomingNode)) { + visited.add(incomingNode); + getIncomingFlowNodeSet(incomingNode, visited); + } + } + } + } + + } + + public Set> getIncomingFlowTupleSet(FlowNode fn) { + + NTuple dstTuple = fn.getDescTuple(); + + Set> set = new HashSet>(); + + ClassDescriptor cd = null; + + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode node = (FlowNode) iterator.next(); + Set edgeSet = node.getOutEdgeSet(); + for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) { + FlowEdge flowEdge = (FlowEdge) iterator2.next(); + if (dstTuple.equals(flowEdge.getEndTuple())) { + NTuple initTuple = flowEdge.getInitTuple(); + NTuple locTuple = new NTuple(); + for (int i = 0; i < initTuple.size(); i++) { + Descriptor d = initTuple.get(i); + Location loc; + if (i == 0) { + loc = new Location(md, d.getSymbol()); + cd = ((VarDescriptor) d).getType().getClassDesc(); + } else { + loc = new Location(cd, d.getSymbol()); + cd = ((FieldDescriptor) d).getType().getClassDesc(); + } + locTuple.add(loc); + } + set.add(locTuple); + } + } + } + return set; + } + public boolean isParamter(NTuple tuple) { // return true if a descriptor tuple is started with a parameter descriptor Descriptor firstIdxDesc = tuple.get(0); diff --git a/Robust/src/Analysis/SSJava/FlowNode.java b/Robust/src/Analysis/SSJava/FlowNode.java index eb9c2a7e..7ce39ed5 100644 --- a/Robust/src/Analysis/SSJava/FlowNode.java +++ b/Robust/src/Analysis/SSJava/FlowNode.java @@ -5,6 +5,8 @@ import java.util.Iterator; import java.util.Set; import IR.Descriptor; +import IR.FieldDescriptor; +import IR.VarDescriptor; public class FlowNode { @@ -74,6 +76,16 @@ public class FlowNode { this.isReturn = isReturn; } + public boolean isPrimitiveType() { + Descriptor desc = descTuple.get(descTuple.size() - 1); + if (desc instanceof VarDescriptor) { + return ((VarDescriptor) desc).getType().isPrimitive(); + } else if (desc instanceof FieldDescriptor) { + return ((FieldDescriptor) desc).getType().isPrimitive(); + } + return false; + } + public String toString() { String rtr = "[FlowNode]:"; if (isParameter()) { diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 089e7f8b..60b56686 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -13,8 +13,6 @@ import java.util.Map; import java.util.Set; import java.util.Stack; -import Analysis.SSJava.FlowDownCheck.ComparisonResult; -import Analysis.SSJava.FlowDownCheck.CompositeLattice; import IR.ClassDescriptor; import IR.Descriptor; import IR.FieldDescriptor; @@ -74,7 +72,9 @@ public class LocationInference { private Map>> mapMethodInvokeNodeToArgIdxMap; - private Map mapLatticeToMethodLocationInfo; + private Map mapMethodDescToMethodLocationInfo; + + private Map mapClassToLocationInfo; private Map> mapMethodDescToPossibleMethodDescSet; @@ -93,9 +93,10 @@ public class LocationInference { new HashMap>(); this.mapMethodInvokeNodeToArgIdxMap = new HashMap>>(); - this.mapLatticeToMethodLocationInfo = new HashMap(); + this.mapMethodDescToMethodLocationInfo = new HashMap(); this.mapMethodDescToPossibleMethodDescSet = new HashMap>(); + this.mapClassToLocationInfo = new HashMap(); } public void setupToAnalyze() { @@ -318,6 +319,11 @@ public class LocationInference { return desc.getSymbol(); } + private Descriptor getDescriptor(int idx, FlowNode node) { + Descriptor desc = node.getDescTuple().get(idx); + return desc; + } + private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice methodLattice) { MethodLocationInfo methodInfo = getMethodLocationInfo(md); @@ -355,14 +361,16 @@ public class LocationInference { extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, 1); } else { - // in this case, take a look at connected nodes at the local level - addRelationToLattice(md, methodLattice, srcNode, dstNode); + // for the method lattice, we need to look at the first element of + // NTuple + if (srcNodeTuple.size() == 1 || dstNodeTuple.size() == 1) { + // in this case, take a look at connected nodes at the local level + addRelationToLattice(md, methodLattice, srcNode, dstNode); + } } } - } - } // grab the this location if the method use the 'this' reference @@ -472,40 +480,334 @@ public class LocationInference { } + private LocationInfo getLocationInfo(Descriptor d) { + if (d instanceof MethodDescriptor) { + return getMethodLocationInfo((MethodDescriptor) d); + } else { + return getFieldLocationInfo((ClassDescriptor) d); + } + } + private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) { - if (!mapLatticeToMethodLocationInfo.containsKey(md)) { - mapLatticeToMethodLocationInfo.put(md, new MethodLocationInfo(md)); + if (!mapMethodDescToMethodLocationInfo.containsKey(md)) { + mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md)); + } + + return mapMethodDescToMethodLocationInfo.get(md); + + } + + private LocationInfo getFieldLocationInfo(ClassDescriptor cd) { + + if (!mapClassToLocationInfo.containsKey(cd)) { + mapClassToLocationInfo.put(cd, new LocationInfo(cd)); } - return mapLatticeToMethodLocationInfo.get(md); + return mapClassToLocationInfo.get(cd); } private void addRelationToLattice(MethodDescriptor md, SSJavaLattice methodLattice, FlowNode srcNode, FlowNode dstNode) { - // add a new binary relation of dstNode < srcNode - String srcSymbol = getSymbol(0, srcNode); - String dstSymbol = getSymbol(0, dstNode); + System.out.println("### addRelationToLattice src=" + srcNode + " dst=" + dstNode); + // add a new binary relation of dstNode < srcNode FlowGraph flowGraph = getFlowGraph(md); MethodLocationInfo methodInfo = getMethodLocationInfo(md); + String srcOriginSymbol = getSymbol(0, srcNode); + String dstOriginSymbol = getSymbol(0, dstNode); + + Descriptor srcDesc = getDescriptor(0, srcNode); + Descriptor dstDesc = getDescriptor(0, dstNode); + + String srcSymbol = methodInfo.getLocName(srcOriginSymbol); + String dstSymbol = methodInfo.getLocName(dstOriginSymbol); + if (srcNode.isParameter()) { int paramIdx = flowGraph.getParamIdx(srcNode.getDescTuple()); - methodInfo.addParameter(srcSymbol, srcNode, paramIdx); + methodInfo.addParameter(srcSymbol, srcDesc, paramIdx); + } else { + methodInfo.addMappingOfLocNameToDescriptor(srcSymbol, srcDesc); } + if (dstNode.isParameter()) { int paramIdx = flowGraph.getParamIdx(dstNode.getDescTuple()); - methodInfo.addParameter(dstSymbol, dstNode, paramIdx); + methodInfo.addParameter(dstSymbol, dstDesc, paramIdx); + } else { + methodInfo.addMappingOfLocNameToDescriptor(dstSymbol, dstDesc); + } + + // consider a composite location case + + boolean isSrcLocalVar = false; + boolean isDstLocalVar = false; + if (srcNode.getDescTuple().size() == 1) { + isSrcLocalVar = true; + } + + if (dstNode.getDescTuple().size() == 1) { + isDstLocalVar = true; + } + + boolean isAssignedCompositeLocation = false; + if (isSrcLocalVar && isDstLocalVar) { + // both src and dst are local var + + // CompositeLocation inferSrc=methodInfo.getInferLocation(srcNode); + // CompositeLocation inferDst=methodInfo.getInferLocation(dstNode); + // if( (inferSrc!=null && inferSrc.getSize()>1) || (inferDst!=null && + // inferDst.getSize()>1)){ + // isAssignedCompositeLocation = true; + // } + + // TODO: need to fix + isAssignedCompositeLocation = + calculateCompositeLocationForLocalVar(flowGraph, methodLattice, methodInfo, srcNode); + calculateCompositeLocationForLocalVar(flowGraph, methodLattice, methodInfo, dstNode); + + } else if (isSrcLocalVar) { + // src is local var + isAssignedCompositeLocation = + calculateCompositeLocationForLocalVar(flowGraph, methodLattice, methodInfo, srcNode); + } else if (isDstLocalVar) { + // dst is local var + isAssignedCompositeLocation = + calculateCompositeLocationForLocalVar(flowGraph, methodLattice, methodInfo, dstNode); + } + + if (!isAssignedCompositeLocation) { + if (!methodLattice.isGreaterThan(srcSymbol, dstSymbol)) { + // if the lattice does not have this relation, add it + methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol); + } + } + + // Set cycleElementSet = + // methodLattice.getPossibleCycleElements(srcSymbol, dstSymbol); + // + // System.out.println("### POSSIBLE CYCLE ELEMENT SET=" + cycleElementSet); + // boolean hasNonPrimitiveElement = false; + // for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) + // { + // String cycleElementSymbol = (String) iterator.next(); + // Set flowNodeSet = + // methodInfo.getFlowNodeSet(cycleElementSymbol); + // for (Iterator iterator2 = flowNodeSet.iterator(); iterator2.hasNext();) { + // Descriptor desc = (Descriptor) iterator2.next(); + // if (!isPrimitiveTypeDescriptor(desc)) { + // hasNonPrimitiveElement = true; + // } + // System.out + // .println("flowNode=" + desc + " is primitive?=" + + // isPrimitiveTypeDescriptor(desc)); + // } + // } + // + // if (hasNonPrimitiveElement) { + // // if there is non-primitive element in the cycle, no way to merge cyclic + // // elements into the shared location + // System.out.println("Failed to merge cyclic value flows into a shared location."); + // + // // try to assign more fine-grind composite location to the source or the + // // destination + // System.out.println("SRC=" + srcSymbol + " DST=" + dstSymbol); + // System.out.println("### SRCNODE=" + srcNode + " DSTNODE=" + dstNode); + // + // FlowNode targetNode; + // if (isPrimitiveLocalVariable(srcNode)) { + // targetNode = srcNode; + // } else { + // targetNode = dstNode; + // } + // + // calculateMoreFineGrainedLocation(md, methodLattice, targetNode); + // + // return; + // } + // + // if (cycleElementSet.size() > 0) { + // String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++); + // methodLattice.mergeIntoSharedLocation(cycleElementSet, newSharedLoc); + // + // for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) + // { + // String locName = (String) iterator.next(); + // methodInfo.mapDescSymbolToLocName(locName, newSharedLoc); + // } + // + // } else if (!methodLattice.isGreaterThan(srcSymbol, dstSymbol)) { + // // if the lattice does not have this relation, add it + // methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol); + // } + // + // System.out.println("methodLattice=" + methodLattice.getKeySet()); + + } + + private void addPrefixMapping(Map, Set>> map, + NTuple prefix, NTuple element) { + + if (!map.containsKey(prefix)) { + map.put(prefix, new HashSet>()); } + map.get(prefix).add(element); + + } - if (!methodLattice.isGreaterThan(srcSymbol, dstSymbol)) { - // if the lattice does not have this relation, add it - methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol); + private NTuple getLocationTuple(MethodLocationInfo methodInfo, FlowGraph flowGraph, + FlowNode flowNode) { + + NTuple locTuple; + CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode); + if (inferLoc != null) { + // the flow node has already been assigned to the location + locTuple = new NTuple(); + NTuple inferLocTuple = inferLoc.getTuple(); + for (int i = 0; i < inferLocTuple.size(); i++) { + locTuple.add(inferLocTuple.get(i)); + } + } else { + locTuple = flowGraph.getLocationTuple(flowNode); } + return locTuple; + } + + private boolean calculateCompositeLocationForLocalVar(FlowGraph flowGraph, + SSJavaLattice methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode) { + + Set inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode); + Set reachableNodeSet = flowGraph.getReachableFlowNodeSet(flowNode); + + Map, Set>> mapPrefixToIncomingLocTupleSet = + new HashMap, Set>>(); + + List> prefixList = new ArrayList>(); + + for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { + FlowNode inNode = (FlowNode) iterator.next(); + NTuple inTuple = getLocationTuple(methodInfo, flowGraph, inNode); + + if (inTuple.size() > 1) { + for (int i = 1; i < inTuple.size(); i++) { + NTuple prefix = inTuple.subList(0, i); + if (!prefixList.contains(prefix)) { + prefixList.add(prefix); + } + addPrefixMapping(mapPrefixToIncomingLocTupleSet, prefix, inTuple); + } + } + } + + Collections.sort(prefixList, new Comparator>() { + public int compare(NTuple arg0, NTuple arg1) { + int s0 = arg0.size(); + int s1 = arg1.size(); + if (s0 > s1) { + return -1; + } else if (s0 == s1) { + return 0; + } else { + return 1; + } + } + }); + + // find out reachable nodes that have the longest common prefix + for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + Set> reachableCommonPrefixSet = new HashSet>(); + + for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { + FlowNode reachableNode = (FlowNode) iterator2.next(); + NTuple reachLocTuple = flowGraph.getLocationTuple(reachableNode); + if (reachLocTuple.startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachLocTuple); + } + } + + if (!reachableCommonPrefixSet.isEmpty()) { + Set> incomingCommonPrefixSet = + mapPrefixToIncomingLocTupleSet.get(curPrefix); + + int idx = curPrefix.size(); + NTuple element = incomingCommonPrefixSet.iterator().next(); + Descriptor desc = element.get(idx).getDescriptor(); + + SSJavaLattice lattice = getLattice(desc); + LocationInfo locInfo = getLocationInfo(desc); + + CompositeLocation inferNode = methodInfo.getInferLocation(flowNode); + String nodeSymbol; + if (inferNode != null) { + + } else { + String newLocSymbol = "Loc" + (SSJavaLattice.seed++); + inferNode = new CompositeLocation(); + for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) { + inferNode.addLocation(curPrefix.get(locIdx)); + } + inferNode.addLocation(new Location(desc, newLocSymbol)); + methodInfo.mapFlowNodeToInferLocation(flowNode, inferNode); + if (flowNode.getDescTuple().size() == 1) { + // local variable case + modifyLocalLatticeAccrodingToNewlyAddedCompositeLocation(methodLattice, methodInfo, + inferNode, flowNode); + } + } + + nodeSymbol = inferNode.get(inferNode.getSize() - 1).getLocIdentifier(); + + for (Iterator iterator = incomingCommonPrefixSet.iterator(); iterator.hasNext();) { + NTuple tuple = (NTuple) iterator.next(); + Location loc = tuple.get(idx); + String higher = locInfo.getLocName(loc.getLocIdentifier()); + lattice.addRelationHigherToLower(higher, nodeSymbol); + } + + for (Iterator iterator = reachableCommonPrefixSet.iterator(); iterator.hasNext();) { + NTuple tuple = (NTuple) iterator.next(); + Location loc = tuple.get(idx); + String lower = locInfo.getLocName(loc.getLocIdentifier()); + lattice.addRelationHigherToLower(nodeSymbol, lower); + } + + return true; + } + + } + + return false; + + } + + private void modifyLocalLatticeAccrodingToNewlyAddedCompositeLocation( + SSJavaLattice methodLattice, MethodLocationInfo methodInfo, + CompositeLocation inferNode, FlowNode flowNode) { + + Location localLocation = inferNode.get(0); + String newLocName = methodInfo.getLocName(localLocation.getLocIdentifier()); + String oldLocName = methodInfo.getLocName(flowNode.getDescTuple().get(0).getSymbol()); + + methodInfo.mapDescSymbolToLocName(oldLocName, newLocName); + methodLattice.substituteLocation(oldLocName, newLocName); + + } + + public boolean isPrimitiveLocalVariable(FlowNode node) { + VarDescriptor varDesc = (VarDescriptor) node.getDescTuple().get(0); + return varDesc.getType().isPrimitive(); + } + + private SSJavaLattice getLattice(Descriptor d) { + if (d instanceof MethodDescriptor) { + return getMethodLattice((MethodDescriptor) d); + } else { + return getFieldLattice((ClassDescriptor) d); + } } private SSJavaLattice getMethodLattice(MethodDescriptor md) { @@ -546,10 +848,27 @@ public class LocationInference { // add a new binary relation of dstNode < srcNode SSJavaLattice fieldLattice = getFieldLattice(cd); - String srcSymbol = srcFieldDesc.getSymbol(); - String dstSymbol = dstFieldDesc.getSymbol(); + String srcOriginalSymbol = srcFieldDesc.getSymbol(); + String dstOriginalSymbol = dstFieldDesc.getSymbol(); + + LocationInfo fieldInfo = getFieldLocationInfo(cd); + + String srcSymbol = fieldInfo.getLocName(srcOriginalSymbol); + String dstSymbol = fieldInfo.getLocName(dstOriginalSymbol); + + Set cycleElementSet = fieldLattice.getPossibleCycleElements(srcSymbol, dstSymbol); + + if (cycleElementSet.size() > 0) { + String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++); + fieldLattice.mergeIntoSharedLocation(cycleElementSet, newSharedLoc); + + for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) { + String locName = (String) iterator.next(); + fieldInfo.mapDescSymbolToLocName(locName, newSharedLoc); + } - if (!fieldLattice.isGreaterThan(srcSymbol, dstSymbol)) { + } else if (!fieldLattice.isGreaterThan(srcSymbol, dstSymbol)) { + // if the lattice does not have this relation, add it fieldLattice.addRelationHigherToLower(srcSymbol, dstSymbol); } diff --git a/Robust/src/Analysis/SSJava/LocationInfo.java b/Robust/src/Analysis/SSJava/LocationInfo.java new file mode 100644 index 00000000..8709ad30 --- /dev/null +++ b/Robust/src/Analysis/SSJava/LocationInfo.java @@ -0,0 +1,67 @@ +package Analysis.SSJava; + +import java.util.HashMap; +import java.util.HashSet; +import java.util.Map; +import java.util.Set; + +import IR.ClassDescriptor; +import IR.Descriptor; +import IR.MethodDescriptor; + +public class LocationInfo { + + Map> mapLocNameToDescSet; + Map mapDescSymbolToLocName; + Map mapDescToInferCompositeLocation; + MethodDescriptor md; + ClassDescriptor cd; + + public LocationInfo() { + mapDescSymbolToLocName = new HashMap(); + mapLocNameToDescSet = new HashMap>(); + mapDescToInferCompositeLocation = new HashMap(); + } + + public LocationInfo(ClassDescriptor cd) { + this.cd = cd; + this.mapDescSymbolToLocName = new HashMap(); + } + + public void mapDescriptorToCompositeLocation(Descriptor desc, CompositeLocation inferLoc) { + mapDescToInferCompositeLocation.put(desc, inferLoc); + } + + public void mapDescSymbolToLocName(String descSymbol, String locName) { + mapDescSymbolToLocName.put(descSymbol, locName); + } + + public String getLocName(String descSymbol) { + if (!mapDescSymbolToLocName.containsKey(descSymbol)) { + mapDescSymbolToLocName.put(descSymbol, descSymbol); + } + return mapDescSymbolToLocName.get(descSymbol); + } + + public void addMappingOfLocNameToDescriptor(String locName, Descriptor desc) { + + // System.out.println("### MAP LocName=" + locName + " to " + desc); + + if (!mapLocNameToDescSet.containsKey(locName)) { + mapLocNameToDescSet.put(locName, new HashSet()); + } + + mapLocNameToDescSet.get(locName).add(desc); + + } + + public Set getFlowNodeSet(String locName) { + + if (!mapLocNameToDescSet.containsKey(locName)) { + mapLocNameToDescSet.put(locName, new HashSet()); + } + + return mapLocNameToDescSet.get(locName); + } + +} diff --git a/Robust/src/Analysis/SSJava/MethodLocationInfo.java b/Robust/src/Analysis/SSJava/MethodLocationInfo.java index ad78508b..5a150aff 100644 --- a/Robust/src/Analysis/SSJava/MethodLocationInfo.java +++ b/Robust/src/Analysis/SSJava/MethodLocationInfo.java @@ -5,22 +5,35 @@ import java.util.HashSet; import java.util.Map; import java.util.Set; +import IR.Descriptor; import IR.MethodDescriptor; -public class MethodLocationInfo { +public class MethodLocationInfo extends LocationInfo { + + MethodDescriptor md; String returnLocName; String thisLocName; String PCLocName; + Map mapParamIdxToLocName; - Map mapLocNameToFlowNode; - MethodDescriptor md; + Set paramLocNameSet; + Map mapFlowNodeToLocation; public MethodLocationInfo(MethodDescriptor md) { this.md = md; this.mapParamIdxToLocName = new HashMap(); - this.mapLocNameToFlowNode = new HashMap(); + this.paramLocNameSet = new HashSet(); this.PCLocName = SSJavaAnalysis.TOP; + this.mapFlowNodeToLocation = new HashMap(); + } + + public void mapFlowNodeToInferLocation(FlowNode node, CompositeLocation location) { + mapFlowNodeToLocation.put(node, location); + } + + public CompositeLocation getInferLocation(FlowNode node) { + return mapFlowNodeToLocation.get(node); } public String getReturnLocName() { @@ -47,9 +60,9 @@ public class MethodLocationInfo { PCLocName = pCLocName; } - public void addParameter(String name, FlowNode node, int idx) { + public void addParameter(String name, Descriptor desc, int idx) { mapParamIdxToLocName.put(new Integer(idx), name); - mapLocNameToFlowNode.put(name, node); + addMappingOfLocNameToDescriptor(name, desc); } public Set getParameterLocNameSet() { @@ -65,7 +78,7 @@ public class MethodLocationInfo { paramSet.add(returnLocName); } - paramSet.addAll(mapLocNameToFlowNode.keySet()); + paramSet.addAll(mapParamIdxToLocName.values()); return paramSet; } diff --git a/Robust/src/Analysis/SSJava/SSJavaLattice.java b/Robust/src/Analysis/SSJava/SSJavaLattice.java index be1a342e..d30aa399 100644 --- a/Robust/src/Analysis/SSJava/SSJavaLattice.java +++ b/Robust/src/Analysis/SSJava/SSJavaLattice.java @@ -63,4 +63,115 @@ public class SSJavaLattice extends Lattice { } } + + public Set getPossibleCycleElements(T higherLoc, T lowerLoc) { + // if a relation of higherloc & lowerloc introduces a new cycle flow, + // return the set of elements consisting of the cycle + Set cycleElemetns = new HashSet(); + + // if lowerLoc has already been higher than higherLoc, the new relation + // introduces a cycle to the lattice + if (lowerLoc.equals(higherLoc)) { + cycleElemetns.add(lowerLoc); + cycleElemetns.add(higherLoc); + } else if (isGreaterThan(lowerLoc, higherLoc)) { + cycleElemetns.add(lowerLoc); + cycleElemetns.add(higherLoc); + getInBetweenElements(lowerLoc, higherLoc, cycleElemetns); + } + return cycleElemetns; + } + + private void getInBetweenElements(T start, T end, Set elementSet) { + Set connectedSet = get(start); + for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) { + T cur = (T) iterator.next(); + if ((!start.equals(cur)) && (!cur.equals(end)) && isGreaterThan(cur, end)) { + elementSet.add(cur); + getInBetweenElements(cur, end, elementSet); + } + } + } + + public void mergeIntoSharedLocation(Set cycleSet, T newLoc) { + + // add a new shared loc + put(newLoc); + addSharedLoc(newLoc); + + Set keySet = getKeySet(); + + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + T keyElement = (T) iterator.next(); + Set connectedSet = get(keyElement); + Set removeSet = new HashSet(); + for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) { + T cur = (T) iterator2.next(); + if (cycleSet.contains(cur)) { + removeSet.add(cur); + } + } + if (!removeSet.isEmpty()) { + // remove relations of locationElement -> cycle + connectedSet.removeAll(removeSet); + // add a new relation of location Element -> shared loc + connectedSet.add(newLoc); + getTable().put(keyElement, connectedSet); + } + } + + Set newConnectedSet = new HashSet(); + for (Iterator iterator = cycleSet.iterator(); iterator.hasNext();) { + T cycleElement = (T) iterator.next(); + Set connectedSet = get(cycleElement); + if (connectedSet != null) { + newConnectedSet.addAll(connectedSet); + } + getTable().remove(cycleElement); + } + newConnectedSet.removeAll(cycleSet); + newConnectedSet.remove(newLoc); + + Set set = getTable().get(newLoc); + set.addAll(newConnectedSet); + + } + + public void substituteLocation(T oldLoc, T newLoc) { + // the new location is going to take all relations of the old location + + // consider the set of location s.t. LOC is greater than oldLoc + Set keySet = getKeySet(); + Set directedConnctedHigherLocSet = new HashSet(); + + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + T key = (T) iterator.next(); + Set connectedSet = getTable().get(key); + if (connectedSet.contains(oldLoc)) { + directedConnctedHigherLocSet.add(key); + } + } + + Set connctedLowerSet = getTable().get(oldLoc); + Set directedConnctedLowerLocSet = new HashSet(); + if (connctedLowerSet != null) { + directedConnctedLowerLocSet.addAll(connctedLowerSet); + } + + for (Iterator iterator = directedConnctedHigherLocSet.iterator(); iterator.hasNext();) { + T higher = (T) iterator.next(); + if (!higher.equals(newLoc)) { + addRelationHigherToLower(higher, newLoc); + } + } + + for (Iterator iterator = directedConnctedLowerLocSet.iterator(); iterator.hasNext();) { + T lower = (T) iterator.next(); + if (!lower.equals(newLoc)) { + addRelationHigherToLower(newLoc, lower); + } + } + + } + } diff --git a/Robust/src/Util/Lattice.java b/Robust/src/Util/Lattice.java index bc024cfa..76aa706c 100644 --- a/Robust/src/Util/Lattice.java +++ b/Robust/src/Util/Lattice.java @@ -3,6 +3,7 @@ package Util; import java.util.HashSet; import java.util.Hashtable; import java.util.Iterator; +import java.util.Map; import java.util.Set; public class Lattice { @@ -34,6 +35,10 @@ public class Lattice { return table.keySet(); } + public Map> getTable() { + return table; + } + public boolean put(T key) { if (table.containsKey(key)) { return false; -- 2.34.1