From ddac34bb8ed87db61d32630e714e7f006a077c8e Mon Sep 17 00:00:00 2001 From: yeom Date: Tue, 4 Dec 2012 02:37:26 +0000 Subject: [PATCH] changes. --- Robust/src/Analysis/SSJava/BuildLattice.java | 59 +- Robust/src/Analysis/SSJava/FlowGraph.java | 61 +- .../src/Analysis/SSJava/HierarchyGraph.java | 2 + .../Analysis/SSJava/LocationInference.java | 570 +++++++++++++----- .../src/Analysis/SSJava/SSJavaAnalysis.java | 2 +- Robust/src/IR/TypeUtil.java | 17 +- 6 files changed, 562 insertions(+), 149 deletions(-) diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index b4f2e37d..79ef4ac7 100644 --- a/Robust/src/Analysis/SSJava/BuildLattice.java +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -6,6 +6,7 @@ import java.util.Iterator; import java.util.Map; import java.util.Set; +import IR.ClassDescriptor; import IR.Descriptor; import IR.MethodDescriptor; import IR.NameDescriptor; @@ -17,6 +18,8 @@ public class BuildLattice { private Map mapSharedNodeToTripleItem; private Map mapHNodeToHighestIndex; + private Map> mapDescToIntermediateLocMap; + private Map, Integer> mapItemToHighestIndex; public BuildLattice(LocationInference infer) { @@ -24,7 +27,7 @@ public class BuildLattice { this.mapSharedNodeToTripleItem = new HashMap(); this.mapHNodeToHighestIndex = new HashMap(); this.mapItemToHighestIndex = new HashMap, Integer>(); - + this.mapDescToIntermediateLocMap = new HashMap>(); } public SSJavaLattice buildLattice(Descriptor desc) { @@ -66,6 +69,27 @@ public class BuildLattice { } + public void setIntermediateLocMap(Descriptor desc, Map map) { + mapDescToIntermediateLocMap.put(desc, map); + } + + public Map getIntermediateLocMap(Descriptor desc) { + if (!mapDescToIntermediateLocMap.containsKey(desc)) { + mapDescToIntermediateLocMap.put(desc, new HashMap()); + } + return mapDescToIntermediateLocMap.get(desc); + } + + private Descriptor getParent(Descriptor desc) { + if (desc instanceof MethodDescriptor) { + MethodDescriptor md = (MethodDescriptor) desc; + ClassDescriptor cd = md.getClassDesc(); + return infer.getParentMethodDesc(cd, md); + } else { + return ((ClassDescriptor) desc).getSuperDesc(); + } + } + private SSJavaLattice buildLattice(Descriptor desc, BasisSet basisSet, HierarchyGraph inputGraph, LocationSummary locSummary, Map, Set>> mapImSucc) { @@ -170,6 +194,34 @@ public class BuildLattice { public SSJavaLattice insertIntermediateNodesToStraightLine(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); + } + } + + // //// + // perform DFS that starts from each skeleton/combination node and ends by another // skeleton/combination node @@ -179,13 +231,12 @@ public class BuildLattice { HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc); LocationSummary locSummary = infer.getLocationSummary(desc); - SSJavaLattice lattice = skeletonLattice.clone(); - Set visited = new HashSet(); Set nodeSet = simpleGraph.getNodeSet(); - Map mapIntermediateLoc = new HashMap(); + Map mapIntermediateLoc = getIntermediateLocMap(desc); + // Map mapIntermediateLoc = new HashMap(); // System.out.println("*insert=" + desc); // System.out.println("***nodeSet=" + nodeSet); diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java index 4054f701..2031460d 100644 --- a/Robust/src/Analysis/SSJava/FlowGraph.java +++ b/Robust/src/Analysis/SSJava/FlowGraph.java @@ -181,7 +181,7 @@ public class FlowGraph { FlowNode flowNode = (FlowNode) iterator.next(); edgeSet.addAll(getOutEdgeSet(flowNode)); } - + System.out.println("EDGESET=" + edgeSet); return edgeSet; } @@ -194,6 +194,7 @@ public class FlowGraph { public Set getNodeSet() { Set set = new HashSet(); set.addAll(mapDescTupleToInferNode.values()); + System.out.println("NODESET=" + set); return set; } @@ -875,4 +876,62 @@ public class FlowGraph { } + public void removeNode(FlowNode node) { + + NTuple tuple = node.getCurrentDescTuple(); + + Set inEdgeSet = getInEdgeSet(node); + for (Iterator iterator = inEdgeSet.iterator(); iterator.hasNext();) { + FlowEdge flowEdge = (FlowEdge) iterator.next(); + if (flowEdge.getEndTuple().equals(tuple)) { + + Set outSet = getOutEdgeSet(getFlowNode(flowEdge.getInitTuple())); + Set toberemoved = new HashSet(); + for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) { + FlowEdge outEdge = (FlowEdge) iterator2.next(); + if (outEdge.getEndTuple().equals(tuple)) { + toberemoved.add(outEdge); + } + } + outSet.removeAll(toberemoved); + } + } + + Set outEdgeSet = getOutEdgeSet(node); + for (Iterator iterator = outEdgeSet.iterator(); iterator.hasNext();) { + FlowEdge flowEdge = (FlowEdge) iterator.next(); + if (flowEdge.getInitTuple().equals(tuple)) { + + Set inSet = getInEdgeSet(getFlowNode(flowEdge.getEndTuple())); + Set toberemoved = new HashSet(); + for (Iterator iterator2 = inSet.iterator(); iterator2.hasNext();) { + FlowEdge inEdge = (FlowEdge) iterator2.next(); + if (inEdge.getInitTuple().equals(tuple)) { + toberemoved.add(inEdge); + } + } + inSet.removeAll(toberemoved); + } + } + + for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + Set outSet = getOutEdgeSet(flowNode); + Set toberemoved = new HashSet(); + for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) { + FlowEdge flowEdge = (FlowEdge) iterator2.next(); + if (flowEdge.getInitTuple().equals(tuple) || flowEdge.getEndTuple().equals(tuple)) { + toberemoved.add(flowEdge); + } + } + outSet.removeAll(toberemoved); + } + + mapFlowNodeToOutEdgeSet.remove(node); + mapFlowNodeToInEdgeSet.remove(node); + System.out.println("REMOVING NODE=" + mapDescTupleToInferNode.get(tuple) + " from tuple=" + + tuple); + mapDescTupleToInferNode.remove(tuple); + System.out.println("mapDescTupleToInferNode=" + mapDescTupleToInferNode); + } } \ No newline at end of file diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index 2da466cb..09519c83 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -1216,6 +1216,7 @@ public class HierarchyGraph { public void writeGraph(boolean isSimple) { String graphName = "hierarchy" + name; + System.out.println("#GRAPHNAME=" + graphName); graphName = graphName.replaceAll("[\\W]", ""); if (isSimple) { @@ -1311,6 +1312,7 @@ public class HierarchyGraph { if (node.isMergeNode()) { nodeName = node.getNamePropertyString(); Set mergeSet = mapMergeNodetoMergingSet.get(node); + System.out.println("node=" + node + " mergeSet=" + mergeSet); nodeName += ":" + convertMergeSetToString(mergeSet); } else { nodeName = node.getNamePropertyString(); diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index b2e9754d..18f1d3ed 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -27,6 +27,7 @@ import IR.Operation; import IR.State; import IR.SymbolTable; import IR.TypeDescriptor; +import IR.TypeUtil; import IR.VarDescriptor; import IR.Tree.ArrayAccessNode; import IR.Tree.AssignmentNode; @@ -59,14 +60,16 @@ public class LocationInference { State state; SSJavaAnalysis ssjava; + TypeUtil tu; List temp_toanalyzeList; List temp_toanalyzeMethodList; Map mapMethodDescriptorToFlowGraph; LinkedList toanalyze_methodDescList; + Set toanalyze_classDescSet; - InheritanceTree inheritanceTree; + // InheritanceTree inheritanceTree; // map a method descriptor to its set of parameter descriptors Map> mapMethodDescriptorToParamDescSet; @@ -136,6 +139,8 @@ public class LocationInference { private Map> mapHighestOverriddenMethodDescToReturnLocTuple; + private Map> mapHighestOverriddenMethodDescToPCLocTuple; + private Map>> mapHighestOverriddenMethodDescToSetLowerThanPCLoc; public static final String GLOBALLOC = "GLOBALLOC"; @@ -172,9 +177,15 @@ public class LocationInference { private Stack arrayAccessNodeStack; - public LocationInference(SSJavaAnalysis ssjava, State state) { + private ClassDescriptor rootClassDescriptor; + + private BuildLattice buildLattice; + + public LocationInference(SSJavaAnalysis ssjava, State state, TypeUtil tu) { this.ssjava = ssjava; this.state = state; + this.tu = tu; + this.toanalyze_classDescSet = new HashSet(); this.temp_toanalyzeList = new ArrayList(); this.temp_toanalyzeMethodList = new ArrayList(); this.mapMethodDescriptorToFlowGraph = new HashMap(); @@ -234,6 +245,11 @@ public class LocationInference { mapHighestOverriddenMethodDescToReturnLocTuple = new HashMap>(); + mapHighestOverriddenMethodDescToPCLocTuple = + new HashMap>(); + + this.buildLattice = new BuildLattice(this); + } public void setupToAnalyze() { @@ -282,8 +298,6 @@ public class LocationInference { // construct value flow graph constructFlowGraph(); - buildInheritanceTree(); - constructGlobalFlowGraph(); checkReturnNodes(); @@ -295,17 +309,15 @@ public class LocationInference { _debug_writeFlowGraph(); - // System.exit(0); + buildInheritanceTree(); + calculateReturnPCLocInheritance(); constructHierarchyGraph(); - calculateReturnPCLocInheritance(); - addInheritanceConstraints(); + addInheritanceConstraintsToHierarchyGraph(); debug_writeHierarchyDotFiles(); - System.exit(0); - simplifyHierarchyGraph(); debug_writeSimpleHierarchyDotFiles(); @@ -318,7 +330,8 @@ public class LocationInference { debug_writeSkeletonCombinationHierarchyDotFiles(); - buildLattice(); + buildLatticeInheritanceTree(); + // buildLattice(); debug_writeLattices(); @@ -350,9 +363,181 @@ public class LocationInference { } private void calculateReturnPCLocInheritance() { - DFSInheritanceTreeReturnPCLoc(inheritanceTree.getRootNode()); - + calculateHighestPCLocInheritance(); calculateLowestReturnLocInheritance(); + updateFlowGraphPCReturnLocInheritance(); + } + + private void updateFlowGraphPCReturnLocInheritance() { + Set keySet = mapHighestOverriddenMethodDescToMethodDescSet.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + MethodDescriptor highestMethodDesc = (MethodDescriptor) iterator.next(); + + if (mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc).size() == 1) { + continue; + } + + Set methodDescSet = + mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc); + + NTuple highestPCLoc = + mapHighestOverriddenMethodDescToPCLocTuple.get(highestMethodDesc); + + NTuple highestRETURNLoc = + mapHighestOverriddenMethodDescToReturnLocTuple.get(highestMethodDesc); + + System.out.println("---highestMethodDesc=" + highestMethodDesc); + + for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator2.next(); + FlowGraph flowGraph = getFlowGraph(md); + + MethodSummary summary = getMethodSummary(md); + CompositeLocation curPCLoc = summary.getPCLoc(); + + // update PCLOC + if (highestPCLoc != null) { + // handle the case that PCLOC is started with 'this'... + NTuple newPCLoc = new NTuple(); + if (highestPCLoc.size() == 1) { + newPCLoc.add(highestPCLoc.get(0)); + } else { + newPCLoc.add(md.getThis()); + newPCLoc.add(highestPCLoc.get(1)); + } + + FlowNode pcFlowNode = flowGraph.getFlowNode(translateToDescTuple(curPCLoc.getTuple())); + pcFlowNode.setBaseTuple(newPCLoc); + + CompositeLocation newPCLocCompLoc = + new CompositeLocation(translateToLocTuple(md, newPCLoc)); + summary.setPCLoc(newPCLocCompLoc); + } else { + // need to remove PCLOC if the overridden method defines it + if (curPCLoc != null && !curPCLoc.get(0).isTop()) { + System.out.println("md=" + md + " curPCLoc=" + curPCLoc); + FlowNode pcFlowNode = flowGraph.getFlowNode(translateToDescTuple(curPCLoc.getTuple())); + System.out.println("#######REMOVE PCLOCNODE=" + pcFlowNode); + flowGraph.removeNode(pcFlowNode); + } + } + + // need to update RETURNLOC + if (highestRETURNLoc != null) { + + CompositeLocation curRETURNLoc = summary.getRETURNLoc(); + System.out.println("curRETURNLoc=" + curRETURNLoc); + + // handle the case that RETURNLOC is started with 'this'... + NTuple newRETURNLoc = new NTuple(); + if (highestRETURNLoc.size() == 1) { + newRETURNLoc.add(highestRETURNLoc.get(0)); + } else { + newRETURNLoc.add(md.getThis()); + newRETURNLoc.add(highestRETURNLoc.get(1)); + } + + FlowNode returnFlowNode = + flowGraph.getFlowNode(translateToDescTuple(curRETURNLoc.getTuple())); + returnFlowNode.setBaseTuple(newRETURNLoc); + + CompositeLocation newRETURNLocCompLoc = + new CompositeLocation(translateToLocTuple(md, newRETURNLoc)); + summary.setPCLoc(newRETURNLocCompLoc); + System.out.println("md=" + md + "###newRETURNLocCompLoc=" + newRETURNLocCompLoc); + + } + + } + } + } + + private void calculateHighestPCLocInheritance() { + + Set keySet = mapHighestOverriddenMethodDescToMethodDescSet.keySet(); + next: for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + MethodDescriptor highestMethodDesc = (MethodDescriptor) iterator.next(); + + NTuple tempTuple = null; + + if (getMethodSummary(highestMethodDesc).getPCLoc() != null) { + + Set methodDescSet = + mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc); + + for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator2.next(); + + FlowGraph flowGraph = getFlowGraph(md); + if (flowGraph == null) { + continue; + } + Set paramNodeSet = flowGraph.getParamFlowNodeSet(); + System.out.println("###md=" + md + " paramNodeSet=" + paramNodeSet); + + CompositeLocation pcLOC = getMethodSummary(md).getPCLoc(); + + if (!pcLOC.get(0).isTop()) { + if (pcLOC.getSize() == 1) { + // return location is not started with 'this' + // check whether the return location is lower than all parameters. + + FlowNode pcFlowNode = flowGraph.getFlowNode(translateToDescTuple(pcLOC.getTuple())); + + int count = 0; + for (Iterator iterator3 = paramNodeSet.iterator(); iterator3.hasNext();) { + FlowNode paramNode = (FlowNode) iterator3.next(); + if (flowGraph.getReachableSetFrom(pcFlowNode.getCurrentDescTuple().subList(0, 1)) + .contains(paramNode)) { + count++; + System.out.println("-------" + pcFlowNode + " -> " + paramNode); + } + } + + int offset = 0; + if (!md.isStatic()) { + offset = 1; + } + + NTuple rTuple = new NTuple(); + rTuple.add(pcLOC.get(0).getLocDescriptor()); + if (count == (md.numParameters() + offset)) { + // means return loc is lower than a composite location starting with 'this' + mapHighestOverriddenMethodDescToPCLocTuple.put(highestMethodDesc, rTuple); + } else { + if (tempTuple == null) { + tempTuple = rTuple; + } + } + } else { + // if the current overridden method has a composite pc loc(size>1) + // and it has not yet finalized the pc location, + // the highest overridden method would have the composite pc location starting with + // 'this' + NTuple rTuple = new NTuple(); + for (int i = 0; i < pcLOC.getSize(); i++) { + rTuple.add(pcLOC.get(i).getLocDescriptor()); + } + tempTuple = rTuple; + } + } else { + mapHighestOverriddenMethodDescToPCLocTuple.remove(highestMethodDesc); + System.out.println("highest=" + highestMethodDesc + " HIGHEST PCLOC=" + + mapHighestOverriddenMethodDescToPCLocTuple.get(highestMethodDesc)); + continue next; + } + } + + } + + if (!mapHighestOverriddenMethodDescToPCLocTuple.containsKey(highestMethodDesc) + && tempTuple != null) { + mapHighestOverriddenMethodDescToPCLocTuple.put(highestMethodDesc, tempTuple); + } + System.out.println("highest=" + highestMethodDesc + " HIGHEST PCLOC=" + + mapHighestOverriddenMethodDescToPCLocTuple.get(highestMethodDesc)); + } + } private void calculateLowestReturnLocInheritance() { @@ -361,35 +546,73 @@ public class LocationInference { for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { MethodDescriptor highestMethodDesc = (MethodDescriptor) iterator.next(); + NTuple tempTuple = null; + if (getMethodSummary(highestMethodDesc).getRETURNLoc() != null) { Set methodDescSet = mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc); for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) { MethodDescriptor md = (MethodDescriptor) iterator2.next(); + + FlowGraph flowGraph = getFlowGraph(md); + Set paramNodeSet = flowGraph.getParamFlowNodeSet(); + System.out.println("###md=" + md + " paramNodeSet=" + paramNodeSet); + CompositeLocation returnLoc = getMethodSummary(md).getRETURNLoc(); if (returnLoc.getSize() == 1) { - Set paramFlowNodeFlowingToReturnValueSet = - getParamNodeFlowingToReturnValue(md); + // return location is not started with 'this' + // check whether the return location is lower than all parameters. + + FlowNode returnFlowNode = + flowGraph.getFlowNode(translateToDescTuple(returnLoc.getTuple())); + + int count = 0; + for (Iterator iterator3 = paramNodeSet.iterator(); iterator3.hasNext();) { + FlowNode paramNode = (FlowNode) iterator3.next(); + if (flowGraph.getReachableSetFrom(paramNode.getCurrentDescTuple().subList(0, 1)) + .contains(returnFlowNode)) { + count++; + System.out.println("-------" + paramNode + " -> " + returnFlowNode); + } + } + + int offset = 0; + if (!md.isStatic()) { + offset = 1; + } - if (paramFlowNodeFlowingToReturnValueSet.size() == md.numParameters()) { + NTuple rTuple = new NTuple(); + rTuple.add(returnLoc.get(0).getLocDescriptor()); + if (count == (md.numParameters() + offset)) { // means return loc is lower than a composite location starting with 'this' - NTuple rTuple = new NTuple(); - rTuple.add(returnLoc.get(0).getLocDescriptor()); mapHighestOverriddenMethodDescToReturnLocTuple.put(highestMethodDesc, rTuple); + } else { + if (tempTuple == null) { + tempTuple = rTuple; + } } } else { - if (!mapHighestOverriddenMethodDescToReturnLocTuple.containsKey(highestMethodDesc)) { - NTuple rTuple = new NTuple(); - for (int i = 0; i < returnLoc.getSize(); i++) { - rTuple.add(returnLoc.get(i).getLocDescriptor()); - } - mapHighestOverriddenMethodDescToReturnLocTuple.put(highestMethodDesc, rTuple); + // if the current overridden method has a composite return loc(size>1) + // and it has not yet finalized the return location + // the highest overridden method has the composite return location starting with + // 'this' + NTuple rTuple = new NTuple(); + for (int i = 0; i < returnLoc.getSize(); i++) { + rTuple.add(returnLoc.get(i).getLocDescriptor()); } + tempTuple = rTuple; } + } } + if (!mapHighestOverriddenMethodDescToReturnLocTuple.containsKey(highestMethodDesc) + && tempTuple != null) { + mapHighestOverriddenMethodDescToReturnLocTuple.put(highestMethodDesc, tempTuple); + } + System.out.println("highest=" + highestMethodDesc + " rTuple=" + + mapHighestOverriddenMethodDescToReturnLocTuple.get(highestMethodDesc)); } } @@ -401,84 +624,25 @@ public class LocationInference { mapHighestOverriddenMethodDescToMethodDescSet.get(highest).add(md); } - private void DFSInheritanceTreeReturnPCLoc(Node node) { + private void DFSInheritanceTreeCalculatingHighestOverriddenMethod(ClassDescriptor cd) { - ClassDescriptor cd = node.getData(); + // ClassDescriptor cd = node.getData(); for (Iterator iterator = cd.getMethods(); iterator.hasNext();) { MethodDescriptor md = (MethodDescriptor) iterator.next(); MethodDescriptor highestMethodDesc = getHighestOverriddenMethod(md.getClassDesc(), md); - System.out.println("md=" + md + " highest=" + highestMethodDesc); - mapMethodDescToHighestOverriddenMethodDesc.put(md, highestMethodDesc); addMapHighestMethodDescToMethodDesc(highestMethodDesc, md); - MethodSummary summary = getMethodSummary(md); - FlowGraph flowGraph = getFlowGraph(md); - - System.out.println("#####summary.getPCLoc()=" + summary.getPCLoc() + " rloc=" - + summary.getRETURNLoc()); - - // //////////////////////////// - // calculate PCLOC constraints - if (summary.getPCLoc().get(0).isTop()) { - mapHighestOverriddenMethodDescToSetLowerThanPCLoc.put(highestMethodDesc, - new HashSet>()); - } else { - Set> lowerSet = - mapHighestOverriddenMethodDescToSetLowerThanPCLoc.get(highestMethodDesc); - - if (lowerSet == null || lowerSet.size() > 0) { - - if (lowerSet == null) { - lowerSet = new HashSet>(); - mapHighestOverriddenMethodDescToSetLowerThanPCLoc.put(highestMethodDesc, lowerSet); - } - - CompositeLocation pcLoc = summary.getPCLoc(); - Set outEdgeSet = - flowGraph - .getOutEdgeSet(flowGraph.getFlowNode(translateToDescTuple(pcLoc.getTuple()))); - - for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { - FlowEdge flowEdge = (FlowEdge) iterator2.next(); - lowerSet.add(flowEdge.getEndTuple()); - } - } - - System.out.println("---lowerSet=" + lowerSet); - } - - // //////////////////////////// - // calculate RETURN LOC constraints - CompositeLocation returnLoc = summary.getRETURNLoc(); - if (returnLoc != null) { - System.out.println("md=" + md + " returnloc=" + returnLoc); - Set inNodeSet = - flowGraph.getIncomingFlowNodeSet(flowGraph.getFlowNode(translateToDescTuple(returnLoc - .getTuple()))); - - Set> higherSet = - mapHighestOverriddenMethodDescToSetHigherThanRLoc.get(highestMethodDesc); - if (higherSet == null) { - higherSet = new HashSet>(); - mapHighestOverriddenMethodDescToSetHigherThanRLoc.put(highestMethodDesc, higherSet); - } - - for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) { - FlowNode flowNode = (FlowNode) iterator2.next(); - higherSet.add(flowNode.getCurrentDescTuple()); - } - } - } // traverse children - List> children = node.getChildren(); + Set children = getDirectSubClasses(cd); for (Iterator iterator = children.iterator(); iterator.hasNext();) { - Node child = (Node) iterator.next(); - DFSInheritanceTreeReturnPCLoc(child); + ClassDescriptor child = (ClassDescriptor) iterator.next(); + DFSInheritanceTreeCalculatingHighestOverriddenMethod(child); } + } private void addTupleLowerThanPCLoc(NTuple tuple) { @@ -488,11 +652,11 @@ public class LocationInference { private MethodDescriptor getHighestOverriddenMethod(ClassDescriptor curClassDesc, MethodDescriptor curMethodDesc) { - Node curNode = inheritanceTree.getTreeNode(curClassDesc); - Node parentNode = curNode.getParent(); + // Node curNode = inheritanceTree.getTreeNode(curClassDesc); + // Node parentNode = curNode.getParent(); + ClassDescriptor parentClassDesc = curClassDesc.getSuperDesc(); - if (parentNode != null) { - ClassDescriptor parentClassDesc = parentNode.getData(); + if (parentClassDesc != null) { if (parentClassDesc.getMethodTable().contains(curMethodDesc.getSymbol())) { Set methodDescSet = parentClassDesc.getMethodTable().getSet(curMethodDesc.getSymbol()); @@ -504,54 +668,52 @@ public class LocationInference { } } // traverse to the parent! - return getHighestOverriddenMethod(parentNode.getData(), curMethodDesc); + return getHighestOverriddenMethod(parentClassDesc, curMethodDesc); } return curMethodDesc; } private void buildInheritanceTree() { - LinkedList methodDescList = - (LinkedList) toanalyze_methodDescList.clone(); - - System.out.println("methodDescList=" + methodDescList); - - while (!methodDescList.isEmpty()) { - MethodDescriptor md = methodDescList.removeLast(); - ClassDescriptor child = md.getClassDesc(); - ClassDescriptor parent = child.getSuperDesc(); - System.out.println("parent=" + child.getSuperDesc() + " child=" + child); - if (parent != null) { - inheritanceTree.addParentChild(child.getSuperDesc(), child); - } - } + DFSInheritanceTreeCalculatingHighestOverriddenMethod(rootClassDescriptor); } - private void addInheritanceConstraints() { + private void addInheritanceConstraintsToHierarchyGraph() { // DFS the inheritance tree and propagates nodes/edges of parent to child - Node rootNode = inheritanceTree.getRootNode(); - DFSInheritanceTree(rootNode); + // Node rootNode = inheritanceTree.getRootNode(); + DFSInheritanceTree(rootClassDescriptor); } - private void DFSInheritanceTree(Node parentNode) { + private void DFSInheritanceTree(ClassDescriptor parentClassDescriptor) { - ClassDescriptor parentClassDescriptor = parentNode.getData(); + // ClassDescriptor parentClassDescriptor = parentNode.getData(); - List> children = parentNode.getChildren(); + Set children = getDirectSubClasses(parentClassDescriptor); for (Iterator iterator = children.iterator(); iterator.hasNext();) { - Node childNode = (Node) iterator.next(); - ClassDescriptor childClassDescriptor = childNode.getData(); + ClassDescriptor childClassDescriptor = (ClassDescriptor) iterator.next(); HierarchyGraph parentGraph = getHierarchyGraph(parentClassDescriptor); HierarchyGraph childGraph = getHierarchyGraph(childClassDescriptor); - Set parentNodeSet = parentGraph.getNodeSet(); + // copies extra information from the parent hierarchy graph + Map> parentMergeNodeMap = parentGraph.getMapHNodetoMergeSet(); + Map> childMergeNodeMap = childGraph.getMapHNodetoMergeSet(); + + Set keySet = parentMergeNodeMap.keySet(); + for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) { + HNode parentKey = (HNode) iterator2.next(); + if (!childMergeNodeMap.containsKey(parentKey)) { + childMergeNodeMap.put(parentKey, new HashSet()); + } + childMergeNodeMap.get(parentKey).addAll(parentMergeNodeMap.get(parentKey)); + } // copies nodes/edges from the parent class... + Set parentNodeSet = parentGraph.getNodeSet(); for (Iterator iterator2 = parentNodeSet.iterator(); iterator2.hasNext();) { HNode parentHNode = (HNode) iterator2.next(); @@ -583,6 +745,20 @@ public class LocationInference { HierarchyGraph parentMethodGraph = getHierarchyGraph(parentMethodDesc); HierarchyGraph childMethodGraph = getHierarchyGraph(childMethodDescriptor); + // copies extra information from the parent hierarchy graph + Map> parentMethodMergeNodeMap = + parentMethodGraph.getMapHNodetoMergeSet(); + Map> childMethodMergeNodeMap = childMethodGraph.getMapHNodetoMergeSet(); + + Set methodKeySet = parentMethodMergeNodeMap.keySet(); + for (Iterator iterator2 = methodKeySet.iterator(); iterator2.hasNext();) { + HNode parentKey = (HNode) iterator2.next(); + if (!childMethodMergeNodeMap.containsKey(parentKey)) { + childMethodMergeNodeMap.put(parentKey, new HashSet()); + } + childMethodMergeNodeMap.get(parentKey).addAll(parentMethodMergeNodeMap.get(parentKey)); + } + // copies nodes/edges from the parent method... for (Iterator iterator2 = parentMethodGraph.getNodeSet().iterator(); iterator2.hasNext();) { HNode parentHNode = (HNode) iterator2.next(); @@ -592,12 +768,12 @@ public class LocationInference { for (Iterator iterator4 = parentIncomingHNode.iterator(); iterator4.hasNext();) { HNode inHNode = (HNode) iterator4.next(); - childMethodGraph.addEdge(inHNode.getDescriptor(), parentHNode.getDescriptor()); + childMethodGraph.addEdge(inHNode, parentHNode); } for (Iterator iterator4 = parentOutgoingHNode.iterator(); iterator4.hasNext();) { HNode outHNode = (HNode) iterator4.next(); - childMethodGraph.addEdge(parentHNode.getDescriptor(), outHNode.getDescriptor()); + childMethodGraph.addEdge(parentHNode, outHNode); } } @@ -606,19 +782,19 @@ public class LocationInference { } - DFSInheritanceTree(childNode); + DFSInheritanceTree(childClassDescriptor); } } - private MethodDescriptor getParentMethodDesc(ClassDescriptor classDesc, - MethodDescriptor methodDesc) { + public MethodDescriptor getParentMethodDesc(ClassDescriptor classDesc, MethodDescriptor methodDesc) { - Node childNode = inheritanceTree.getTreeNode(classDesc); - Node parentNode = childNode.getParent(); + // Node childNode = inheritanceTree.getTreeNode(classDesc); + ClassDescriptor parentClassDesc = classDesc.getSuperDesc(); + // Node parentNode = childNode.getParent(); - if (parentNode != null) { - ClassDescriptor parentClassDesc = parentNode.getData(); + if (parentClassDesc != null) { + // ClassDescriptor parentClassDesc = parentNode.getData(); if (parentClassDesc.getMethodTable().contains(methodDesc.getSymbol())) { Set methodDescSet = parentClassDesc.getMethodTable().getSet(methodDesc.getSymbol()); @@ -631,7 +807,7 @@ public class LocationInference { } // traverse to the parent! - getParentMethodDesc(parentNode.getData(), methodDesc); + getParentMethodDesc(parentClassDesc, methodDesc); } @@ -669,6 +845,23 @@ public class LocationInference { System.out.println("SSJAVA: Updating a flow graph: " + md); propagateFlowsFromCalleesWithNoCompositeLocation(md); } + + Set nodeSet = getFlowGraph(md).getNodeSet(); + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + NTuple descTuple = flowNode.getCurrentDescTuple(); + NTuple locTuple = translateToLocTuple(md, descTuple); + for (int i = 0; i < locTuple.size(); i++) { + Location loc = locTuple.get(i); + if (loc.getDescriptor() instanceof ClassDescriptor) { + toanalyze_classDescSet.add((ClassDescriptor) loc.getDescriptor()); + } else if (loc.getDescriptor() instanceof MethodDescriptor) { + toanalyze_classDescSet.add(((MethodDescriptor) loc.getDescriptor()).getClassDesc()); + } + } + + } + } } @@ -1726,6 +1919,10 @@ public class LocationInference { Location lastLocationOfPrefix = curPrefix.get(curPrefix.size() - 1); // check whether prefix appears in the list of parameters Set minSet = mapMethodDescToMethodInvokeNodeSet.get(md); + System.out.println("$$$md=" + md + " minSet=" + minSet); + if (minSet == null) { + return false; + } found: for (Iterator iterator = minSet.iterator(); iterator.hasNext();) { MethodInvokeNode min = (MethodInvokeNode) iterator.next(); Map> map = mapMethodInvokeNodeToArgIdxMap.get(min); @@ -2405,6 +2602,7 @@ public class LocationInference { Set cdKeySet = cd2lattice.keySet(); for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) { ClassDescriptor cd = (ClassDescriptor) iterator.next(); + System.out.println("########cd=" + cd); writeInferredLatticeDotFile((ClassDescriptor) cd, getSkeletonCombinationHierarchyGraph(cd), cd2lattice.get(cd), ""); COUNT += cd2lattice.get(cd).getKeySet().size(); @@ -2420,9 +2618,34 @@ public class LocationInference { System.out.println("###COUNT=" + COUNT); } - private void buildLattice() { + private void buildLattice(Descriptor desc) { + System.out.println("buildLattice=" + desc); + SSJavaLattice simpleLattice = buildLattice.buildLattice(desc); + + addMapDescToSimpleLattice(desc, simpleLattice); + + HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc); + System.out.println("\n## insertIntermediateNodesToStraightLine:" + + simpleHierarchyGraph.getName()); + SSJavaLattice lattice = + buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice); + lattice.removeRedundantEdges(); - BuildLattice buildLattice = new BuildLattice(this); + if (desc instanceof ClassDescriptor) { + // field lattice + cd2lattice.put((ClassDescriptor) desc, lattice); + // ssjava.writeLatticeDotFile((ClassDescriptor) desc, null, lattice); + } else if (desc instanceof MethodDescriptor) { + // method lattice + md2lattice.put((MethodDescriptor) desc, lattice); + MethodDescriptor md = (MethodDescriptor) desc; + ClassDescriptor cd = md.getClassDesc(); + // ssjava.writeLatticeDotFile(cd, md, lattice); + } + + } + + private void buildLattice() { Set keySet = mapDescriptorToCombineSkeletonHierarchyGraph.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { @@ -2451,18 +2674,67 @@ public class LocationInference { // ssjava.writeLatticeDotFile(cd, md, lattice); } - // System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc); - // HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc); - // HierarchyGraph skeletonGraphWithCombinationNode = - // skeletonGraph.clone(); - // skeletonGraphWithCombinationNode.setName(desc + "_SC"); - // - // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc); - // System.out.println("Identifying Combination Nodes:"); - // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph); - // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph(); - // mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, - // skeletonGraphWithCombinationNode); + } + + } + + private void buildLatticeInheritanceTree() { + // DFS the inheritance tree and propagates lattice nodes/edges from the parent to children + // Node rootNode = inheritanceTree.getRootNode(); + DFSBuildLatticeInheritanceTree(rootClassDescriptor); + } + + public Set getDirectSubClasses(ClassDescriptor parent) { + + System.out.println("$$$toanalyze_classDescSet=" + toanalyze_classDescSet); + Set result = new HashSet(); + + Set children = tu.getDirectSubClasses(parent); + if (children == null) { + children = new HashSet(); + } + + for (Iterator iterator = children.iterator(); iterator.hasNext();) { + ClassDescriptor child = (ClassDescriptor) iterator.next(); + if (toanalyze_classDescSet.contains(child)) { + result.add(child); + } + } + + return result; + } + + private void DFSBuildLatticeInheritanceTree(ClassDescriptor cd) { + // ClassDescriptor cd = node.getData(); + + ClassDescriptor parentClassDesc = cd.getSuperDesc(); + if (parentClassDesc != null) { + Map parentMap = buildLattice.getIntermediateLocMap(parentClassDesc); + buildLattice.setIntermediateLocMap(cd, parentMap); + } + + buildLattice(cd); + + for (Iterator iterator = cd.getMethods(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + if (toanalyze_methodDescList.contains(md)) { + MethodDescriptor parentMethodDesc = getParentMethodDesc(md.getClassDesc(), md); + if (parentMethodDesc != null) { + Map parentMap = buildLattice.getIntermediateLocMap(parentMethodDesc); + buildLattice.setIntermediateLocMap(md, parentMap); + } + buildLattice(md); + } + } + + // traverse children + Set children = getDirectSubClasses(cd); + for (Iterator iterator = children.iterator(); iterator.hasNext();) { + ClassDescriptor classDescriptor = (ClassDescriptor) iterator.next(); + if (toanalyze_classDescSet.contains(classDescriptor)) { + DFSBuildLatticeInheritanceTree(classDescriptor); + } + } } @@ -2844,6 +3116,19 @@ public class LocationInference { NTuple srcCurTuple = srcNode.getCurrentDescTuple(); NTuple dstCurTuple = dstNode.getCurrentDescTuple(); + // ////////////////////////// + // inheritance check + if (mapMethodDescToHighestOverriddenMethodDesc.containsKey(md)) { + + MethodDescriptor highestOverriddenMethodDesc = + mapMethodDescToHighestOverriddenMethodDesc.get(md); + + if (srcCurTuple.get(srcCurTuple.size() - 1).getSymbol().startsWith(PCLOC)) { + } + + } + // ////////////////////////// + System.out.println("-srcCurTuple=" + srcCurTuple + " dstCurTuple=" + dstCurTuple + " srcNode=" + srcNode + " dstNode=" + dstNode); @@ -4382,7 +4667,7 @@ public class LocationInference { return false; } - private SSJavaLattice getLattice(Descriptor d) { + public SSJavaLattice getLattice(Descriptor d) { if (d instanceof MethodDescriptor) { return getMethodLattice((MethodDescriptor) d); } else { @@ -4470,7 +4755,8 @@ public class LocationInference { ClassDescriptor cd = toAnalyzeNext(); if (cd.getClassName().equals("Object")) { - inheritanceTree = new InheritanceTree(cd); + rootClassDescriptor = cd; + // inheritanceTree = new InheritanceTree(cd); } setupToAnalazeMethod(cd); diff --git a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java index 80f678d5..cc623cc6 100644 --- a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java +++ b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java @@ -189,7 +189,7 @@ public class SSJavaAnalysis { } private void inference() { - LocationInference inferEngine = new LocationInference(this, state); + LocationInference inferEngine = new LocationInference(this, state, tu); inferEngine.inference(); } diff --git a/Robust/src/IR/TypeUtil.java b/Robust/src/IR/TypeUtil.java index a2a76e39..fe802b0b 100644 --- a/Robust/src/IR/TypeUtil.java +++ b/Robust/src/IR/TypeUtil.java @@ -17,6 +17,7 @@ public class TypeUtil { State state; Hashtable supertable; Hashtable subclasstable; + Hashtable directSubClassTable; BuildIR bir; // for interfaces @@ -284,6 +285,7 @@ NextMethod: public void createFullTable() { subclasstable=new Hashtable(); + directSubClassTable=new Hashtable(); HashSet tovisit=new HashSet(); HashSet visited=new HashSet(); @@ -305,6 +307,14 @@ NextMethod: } } + if(tmp!=null){ + if(!directSubClassTable.containsKey(tmp)){ + directSubClassTable.put(tmp, new HashSet()); + } + ((Set)directSubClassTable.get(tmp)).add(cd); + } + + while(tmp!=null) { if (!subclasstable.containsKey(tmp)) subclasstable.put(tmp,new HashSet()); @@ -345,7 +355,12 @@ NextMethod: } } } - + + public Set getDirectSubClasses(ClassDescriptor cd) { + System.out.println("$$$cd="+cd+" children="+directSubClassTable.get(cd)); + return (Set)directSubClassTable.get(cd); + } + public Set getSubClasses(ClassDescriptor cd) { return (Set)subclasstable.get(cd); } -- 2.34.1