From 7bc545e61609c3274ae70619762f1000a7863a6c Mon Sep 17 00:00:00 2001 From: yeom Date: Wed, 5 Dec 2012 01:44:47 +0000 Subject: [PATCH] the last piece for the inheritance checking... --- .../src/Analysis/SSJava/HierarchyGraph.java | 22 +- .../Analysis/SSJava/LocationInference.java | 208 ++++++++++-------- 2 files changed, 129 insertions(+), 101 deletions(-) diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index 09519c83..e701c3ed 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -298,21 +298,16 @@ public class HierarchyGraph { } - public void simplifyHierarchyGraph() { + public void simplifyHierarchyGraph(LocationInference infer) { removeRedundantEdges(); - combineRedundantNodes(false); + combineRedundantNodes(false, infer); } - public void simplifySkeletonCombinationHierarchyGraph() { - removeRedundantEdges(); - combineRedundantNodes(true); - } - - public void combineRedundantNodes(boolean onlyCombinationNodes) { + public void combineRedundantNodes(boolean onlyCombinationNodes, LocationInference infer) { // Combine field/parameter nodes who have the same set of incoming/outgoing edges. boolean isUpdated = false; do { - isUpdated = combineTwoRedundatnNodes(onlyCombinationNodes); + isUpdated = combineTwoRedundatnNodes(onlyCombinationNodes, infer); } while (isUpdated); } @@ -330,7 +325,7 @@ public class HierarchyGraph { return mapHNodeToOutgoingSet.get(node); } - private boolean combineTwoRedundatnNodes(boolean onlyCombinationNodes) { + private boolean combineTwoRedundatnNodes(boolean onlyCombinationNodes, LocationInference infer) { for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { HNode node1 = (HNode) iterator.next(); @@ -363,9 +358,16 @@ public class HierarchyGraph { && outgoingNodeSet1.equals(outgoingNodeSet2)) { // need to merge node1 and node2 + // /////////////// + // merge two nodes only if every hierarchy graph in the inheritance hierarchy + // that includes both nodes allows the merging of them... Set mergeSet = new HashSet(); mergeSet.add(node1); mergeSet.add(node2); + infer.isValidMergeInheritanceCheck(desc, mergeSet); + + // /////////////// + mergeNodes(mergeSet, onlyCombinationNodes); return true; } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 18f1d3ed..3224bbe4 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -135,8 +135,6 @@ public class LocationInference { private Map> mapHighestOverriddenMethodDescToMethodDescSet; - private Map>> mapHighestOverriddenMethodDescToSetHigherThanRLoc; - private Map> mapHighestOverriddenMethodDescToReturnLocTuple; private Map> mapHighestOverriddenMethodDescToPCLocTuple; @@ -233,9 +231,6 @@ public class LocationInference { mapMethodDescToHighestOverriddenMethodDesc = new HashMap(); - mapHighestOverriddenMethodDescToSetHigherThanRLoc = - new HashMap>>(); - mapHighestOverriddenMethodDescToSetLowerThanPCLoc = new HashMap>>(); @@ -645,10 +640,6 @@ public class LocationInference { } - private void addTupleLowerThanPCLoc(NTuple tuple) { - - } - private MethodDescriptor getHighestOverriddenMethod(ClassDescriptor curClassDesc, MethodDescriptor curMethodDesc) { @@ -1046,46 +1037,6 @@ public class LocationInference { } - private CompositeLocation translateArgCompLocToParamCompLoc(MethodInvokeNode min, - CompositeLocation argCompLoc) { - - System.out.println("--------translateArgCompLocToParamCompLoc argCompLoc=" + argCompLoc); - MethodDescriptor mdCallee = min.getMethod(); - FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); - - NTuple argLocTuple = argCompLoc.getTuple(); - Location argLocalLoc = argLocTuple.get(0); - - Map> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min); - Set idxSet = mapIdxToArgTuple.keySet(); - for (Iterator iterator2 = idxSet.iterator(); iterator2.hasNext();) { - Integer idx = (Integer) iterator2.next(); - - if (idx == 0 && !min.getMethod().isStatic()) { - continue; - } - - NTuple argTuple = mapIdxToArgTuple.get(idx); - if (argTuple.size() > 0 && argTuple.get(0).equals(argLocalLoc.getLocDescriptor())) { - // it matches with the current argument composite location - // so what is the corresponding parameter local descriptor? - FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); - // System.out.println("----------found paramNode=" + paramNode); - NTuple paramDescTuple = paramNode.getCurrentDescTuple(); - - NTuple newParamTupleFromArgTuple = translateToLocTuple(mdCallee, paramDescTuple); - for (int i = 1; i < argLocTuple.size(); i++) { - newParamTupleFromArgTuple.add(argLocTuple.get(i)); - } - - // System.out.println("-----------newParamTuple=" + newParamTupleFromArgTuple); - return new CompositeLocation(newParamTupleFromArgTuple); - - } - } - return null; - } - private void addAddtionalOrderingConstraints(MethodDescriptor mdCaller) { // First, assign a composite location to a node in the flow graph @@ -2148,20 +2099,6 @@ public class LocationInference { } - private boolean containsClassDesc(ClassDescriptor cd, NTuple prefixLocTuple) { - for (int i = 0; i < prefixLocTuple.size(); i++) { - Location loc = prefixLocTuple.get(i); - Descriptor locDesc = loc.getLocDescriptor(); - if (locDesc != null) { - ClassDescriptor type = getClassTypeDescriptor(locDesc); - if (type != null && type.equals(cd)) { - return true; - } - } - } - return false; - } - private GlobalFlowGraph constructSubGlobalFlowGraph(FlowGraph flowGraph) { MethodDescriptor md = flowGraph.getMethodDescriptor(); @@ -2438,6 +2375,9 @@ public class LocationInference { System.out.println("\nSSJAVA: generate method summary: " + md); FlowGraph flowGraph = getFlowGraph(md); + if (flowGraph == null) { + continue; + } MethodSummary methodSummary = getMethodSummary(md); HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(md); @@ -2553,31 +2493,6 @@ public class LocationInference { return false; } - private CompositeLocation translateCompositeLocation(CompositeLocation compLoc) { - CompositeLocation newCompLoc = new CompositeLocation(); - - // System.out.println("compLoc=" + compLoc); - for (int i = 0; i < compLoc.getSize(); i++) { - Location loc = compLoc.get(i); - Descriptor enclosingDescriptor = loc.getDescriptor(); - Descriptor locDescriptor = loc.getLocDescriptor(); - - HNode hnode = getHierarchyGraph(enclosingDescriptor).getHNode(locDescriptor); - // System.out.println("-hnode=" + hnode + " from=" + locDescriptor + - // " enclosingDescriptor=" - // + enclosingDescriptor); - // System.out.println("-getLocationSummary(enclosingDescriptor)=" - // + getLocationSummary(enclosingDescriptor)); - String locName = getLocationSummary(enclosingDescriptor).getLocationName(hnode.getName()); - // System.out.println("-locName=" + locName); - Location newLoc = new Location(enclosingDescriptor, locName); - newLoc.setLocDescriptor(locDescriptor); - newCompLoc.addLocation(newLoc); - } - - return newCompLoc; - } - private void debug_writeLattices() { Set keySet = mapDescriptorToSimpleLattice.keySet(); @@ -2787,13 +2702,124 @@ public class LocationInference { HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph(); skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode()); skeletonGraph.setMapHNodeToDescSet(simpleGraph.getMapHNodeToDescSet()); - skeletonGraph.simplifyHierarchyGraph(); - // skeletonGraph.combineRedundantNodes(false); - // skeletonGraph.removeRedundantEdges(); + skeletonGraph.simplifyHierarchyGraph(this); mapDescriptorToSkeletonHierarchyGraph.put(desc, skeletonGraph); } } + private void recurUpAccumulateInheritanceDesc(Descriptor curDesc, Set set) { + + if (curDesc instanceof ClassDescriptor) { + ClassDescriptor cd = (ClassDescriptor) curDesc; + ClassDescriptor parentClassDesc = cd.getSuperDesc(); + if (parentClassDesc != null && !parentClassDesc.equals(rootClassDescriptor)) { + set.add(parentClassDesc); + recurUpAccumulateInheritanceDesc(parentClassDesc, set); + } + } else { + MethodDescriptor md = (MethodDescriptor) curDesc; + ClassDescriptor cd = md.getClassDesc(); + + // traverse up + ClassDescriptor parentClassDesc = cd.getSuperDesc(); + if (parentClassDesc != null && !parentClassDesc.equals(rootClassDescriptor)) { + + Set methodDescSet = + parentClassDesc.getMethodTable().getSet(md.getSymbol()); + for (Iterator iterator = methodDescSet.iterator(); iterator.hasNext();) { + MethodDescriptor parentMethodDesc = (MethodDescriptor) iterator.next(); + if (parentMethodDesc.matches(md)) { + set.add(parentMethodDesc); + recurUpAccumulateInheritanceDesc(parentMethodDesc, set); + } + } + } + + } + + } + + private void recurDownAccumulateInheritanceDesc(Descriptor curDesc, Set set) { + + if (curDesc instanceof ClassDescriptor) { + ClassDescriptor cd = (ClassDescriptor) curDesc; + ClassDescriptor parentClassDesc = cd.getSuperDesc(); + Set directSubClasses = tu.getDirectSubClasses(cd); + for (Iterator iterator = directSubClasses.iterator(); iterator.hasNext();) { + ClassDescriptor child = (ClassDescriptor) iterator.next(); + recurDownAccumulateInheritanceDesc(child, set); + } + } else { + MethodDescriptor md = (MethodDescriptor) curDesc; + ClassDescriptor cd = md.getClassDesc(); + + // traverse down + Set directSubClasses = tu.getDirectSubClasses(cd); + for (Iterator iterator = directSubClasses.iterator(); iterator.hasNext();) { + ClassDescriptor child = (ClassDescriptor) iterator.next(); + + Set methodDescSet = child.getMethodTable().getSet(md.getSymbol()); + for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) { + MethodDescriptor childMethodDesc = (MethodDescriptor) iterator2.next(); + if (childMethodDesc.matches(md)) { + set.add(childMethodDesc); + recurDownAccumulateInheritanceDesc(childMethodDesc, set); + } + } + } + + } + + } + + private void accumulateInheritanceDesc(Descriptor curDesc, Set set) { + + recurUpAccumulateInheritanceDesc(curDesc, set); + recurDownAccumulateInheritanceDesc(curDesc, set); + + } + + public boolean isValidMergeInheritanceCheck(Descriptor desc, Set mergeSet) { + + // set up inheritance chain set... + Set inheritanceDescSet = new HashSet(); + recurUpAccumulateInheritanceDesc(desc, inheritanceDescSet); + + nextgraph: for (Iterator iterator = inheritanceDescSet.iterator(); iterator.hasNext();) { + Descriptor inheritDesc = (Descriptor) iterator.next(); + + if (!desc.equals(inheritDesc)) { + HierarchyGraph graph = getSkeletonCombinationHierarchyGraph(inheritDesc); + + // first check whether this graph includes all elements of the merge set + for (Iterator iterator2 = mergeSet.iterator(); iterator2.hasNext();) { + HNode node = (HNode) iterator2.next(); + if (!graph.contains(node)) { + continue nextgraph; + } + } + + HNode firstNode = mergeSet.iterator().next(); + + Set incomingNode = graph.getIncomingNodeSet(firstNode); + Set outgoingNode = graph.getOutgoingNodeSet(firstNode); + + for (Iterator iterator2 = mergeSet.iterator(); iterator2.hasNext();) { + HNode node = (HNode) iterator2.next(); + + if (!graph.getIncomingNodeSet(node).equals(incomingNode) + || !graph.getOutgoingNodeSet(node).equals(outgoingNode)) { + return false; + } + + } + } + + } + + return true; + } + private void debug_writeHierarchyDotFiles() { Set keySet = mapDescriptorToHierarchyGraph.keySet(); -- 2.34.1