From 47cc527f574f19b71e92fceac668fb8c0655b13b Mon Sep 17 00:00:00 2001 From: Yong hun eom Date: Mon, 4 Mar 2013 20:46:34 -0800 Subject: [PATCH] changes. --- Robust/src/Analysis/SSJava/BuildLattice.java | 104 +++++++++++++- .../src/Analysis/SSJava/HierarchyGraph.java | 133 ++++++++++-------- .../src/Analysis/SSJava/SSJavaAnalysis.java | 118 +++++++++++++++- 3 files changed, 289 insertions(+), 66 deletions(-) diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index adce54e5..43201447 100644 --- a/Robust/src/Analysis/SSJava/BuildLattice.java +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -30,6 +30,10 @@ public class BuildLattice { private Map>> mapDescToLineListMap; + public BuildLattice() { + this(null); + } + public BuildLattice(LocationInference infer) { this.infer = infer; this.mapSharedNodeToTripleItem = new HashMap(); @@ -86,7 +90,7 @@ public class BuildLattice { SSJavaLattice naive_lattice = buildLattice(desc, naiveBasisSet, naiveGraph, null, naive_mapImSucc); - int numLocs = naive_lattice.getKeySet().size(); + int numLocs = naive_lattice.getKeySet().size() ; LocationInference.numLocationsNaive += numLocs; infer.mapNumLocsMapNaive.put(desc, new Integer(numLocs)); @@ -97,6 +101,15 @@ public class BuildLattice { + naive_lattice.getKeySet().size()); infer.addNaiveLattice(desc, naive_lattice); + + // write a dot file before everything is done + if (desc instanceof ClassDescriptor) { + infer.writeInferredLatticeDotFile((ClassDescriptor) desc, null, naive_lattice, "_naive"); + } else { + MethodDescriptor md = (MethodDescriptor) desc; + infer.writeInferredLatticeDotFile(md.getClassDesc(), md, naive_lattice, "_naive"); + } + } // ///////////////////////////////////////////////////////////////////////////////////// @@ -134,6 +147,79 @@ public class BuildLattice { } } + private SSJavaLattice buildLattice(BasisSet basisSet, HierarchyGraph inputGraph, + Map, Set>> mapImSucc) { + + System.out.println("\nBuild Complete Lattice:" + inputGraph.getName()); + + SSJavaLattice completeLattice = + new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM); + + Map, String> mapFToLocName = new HashMap, String>(); + + Set> keySet = mapImSucc.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Set higher = (Set) iterator.next(); + + String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher); + + HNode higherNode = inputGraph.getHNode(higherName); + + if (higherNode == null) { + NameDescriptor d = new NameDescriptor(higherName); + higherNode = inputGraph.getHNode(d); + higherNode.setSkeleton(true); + } + + if (higherNode != null && higherNode.isSharedNode()) { + completeLattice.addSharedLoc(higherName); + } + Set descSet = inputGraph.getDescSetOfNode(higherNode); + // System.out.println("higherName=" + higherName + " higherNode=" + higherNode + " descSet=" + // + descSet); + + // locSummary.addMapHNodeNameToLocationName(higherName, higherName); + + Set> lowerSet = mapImSucc.get(higher); + for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) { + Set lower = (Set) iterator2.next(); + + String lowerName = generateElementName(basisSet, inputGraph, mapFToLocName, lower); + HNode lowerNode = inputGraph.getHNode(lowerName); + + if (lowerNode == null && !lowerName.equals(SSJavaAnalysis.BOTTOM)) { + NameDescriptor d = new NameDescriptor(lowerName); + lowerNode = inputGraph.getHNode(d); + lowerNode.setSkeleton(true); + } + + if (lowerNode != null && !inputGraph.isDirectlyConnectedTo(higherNode, lowerNode)) { + inputGraph.addEdge(higherNode, lowerNode); + } + + if (lowerNode != null && lowerNode.isSharedNode()) { + completeLattice.addSharedLoc(lowerName); + } + + Set lowerDescSet = inputGraph.getDescSetOfNode(lowerNode); + // System.out.println("lowerName=" + lowerName + " lowerNode=" + lowerNode + " descSet=" + // + lowerDescSet); + // locSummary.addMapHNodeNameToLocationName(lowerName, lowerName); + + if (higher.size() == 0) { + // empty case + completeLattice.put(lowerName); + } else { + completeLattice.addRelationHigherToLower(higherName, lowerName); + } + + } + + } + + return completeLattice; + } + private SSJavaLattice buildLattice(Descriptor desc, BasisSet basisSet, HierarchyGraph inputGraph, LocationSummary locSummary, Map, Set>> mapImSucc) { @@ -328,7 +414,11 @@ public class BuildLattice { // System.out.println(" hierarchyGraph.getSkeleteNodeSetReachTo(" + hNode + ")=" // + hierarchyGraph.getSkeleteNodeSetReachTo(hNode)); + + //TODO attempt to use non-transitive reachToSet +// Set reachToSet = hierarchyGraph.getSkeleteNodeSetReachToNoTransitive(hNode); Set reachToSet = hierarchyGraph.getSkeleteNodeSetReachTo(hNode); +// System.out.println("reachToSet=" + reachToSet); for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) { HNode reachToNode = (HNode) iterator2.next(); aboveSet.add(scGraph.getCurrentHNode(reachToNode)); @@ -345,7 +435,7 @@ public class BuildLattice { endSet.add(hierarchyGraph.getCurrentHNode(aboveNode)); } - trace = hierarchyGraph.computeDistance(hNode, endSet, combineSkeletonNodeSet); + trace = hierarchyGraph.computeDistance(hNode, endSet, scGraph, combineSkeletonNodeSet); System.out.println(" COUNT-RESULT::start=" + hNode + " end=" + endSet + " trace=" + trace); @@ -1143,6 +1233,16 @@ public class BuildLattice { System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis()); } + public SSJavaLattice buildLattice(HierarchyGraph hierarchyGraph) { + BasisSet basisSet = hierarchyGraph.computeBasisSet(new HashSet()); + + Family family = generateFamily(basisSet); + Map, Set>> mapImSucc = coveringGraph(basisSet, family); + + SSJavaLattice completeLattice = buildLattice(basisSet, hierarchyGraph, mapImSucc); + return completeLattice; + } + } class Identifier { diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index f39ac738..d7900939 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -893,6 +893,22 @@ public class HierarchyGraph { } + public Set getSkeleteNodeSetReachToNoTransitive(HNode node) { + + Set reachToSet = new HashSet(); + Set visited = new HashSet(); + // visited.add(node); + recurSkeletonReachTo(node, reachToSet, visited); + + // obsolete! + // if a node reaches to one of elements in the reachToSet, we do not need to keep it + // because the node is not directly connected to the combination node + // removeRedundantReachToNodes(reachToSet); + + return removeTransitivelyReachToSet(reachToSet); + // return reachToSet; + } + public Set getSkeleteNodeSetReachTo(HNode node) { Set reachToSet = new HashSet(); @@ -905,6 +921,7 @@ public class HierarchyGraph { // because the node is not directly connected to the combination node // removeRedundantReachToNodes(reachToSet); + // TODO return removeTransitivelyReachToSet(reachToSet); // return reachToSet; } @@ -1422,9 +1439,18 @@ public class HierarchyGraph { return max; } - public Stack computeDistance(HNode startNode, Set endNodeSet, Set combineSet) { - // System.out.println("#####computeDistanceance startNode=" + startNode + " endNode=" + - // endNodeSet); + public Stack computeDistance2(HNode startNode, Set endNodeSet, + HierarchyGraph scGraph, Set combineSet) { + System.out + .println("#####computeDistanceance startNode=" + startNode + " endNode=" + endNodeSet); + Stack trace = new Stack(); + return recur_computeDistance2(startNode, endNodeSet, scGraph, 0, combineSet, trace); + } + + public Stack computeDistance(HNode startNode, Set endNodeSet, + HierarchyGraph scGraph, Set combineSet) { + System.out + .println("#####computeDistanceance startNode=" + startNode + " endNode=" + endNodeSet); Stack trace = new Stack(); return recur_computeDistance(startNode, endNodeSet, 0, combineSet, trace); } @@ -1462,7 +1488,7 @@ public class HierarchyGraph { } } - System.out.println(" traverse more to" + inNode + " before-trace=" + trace); + // System.out.println(" traverse more to" + inNode + " before-trace=" + trace); Stack newTrace = (Stack) trace.clone(); Stack curTrace = recur_computeDistance(inNode, endNodeSet, count, combineSet, newTrace); @@ -1474,24 +1500,34 @@ public class HierarchyGraph { } } return curMaxTrace; + } - private int recur_computeDistance2(HNode startNode, HNode curNode, Set endNodeSet, - int count, Set combineSet) { + private Stack recur_computeDistance2(HNode curNode, Set endNodeSet, + HierarchyGraph scGraph, int count, Set combineSet, Stack trace) { - if (!curNode.equals(startNode)) { - // do not count the start node - count++; + if (!curNode.isSkeleton()) { + if (curNode.isSharedNode()) { + trace.add("S"); + } else { + trace.add("N"); + } } - if (endNodeSet.contains(curNode)) { + System.out.println(" curNode=" + curNode + " curTrace=" + trace); + // System.out.println(" curNode=" + curNode + " curSCNode=" + // + scGraph.getCurrentHNode(curNode) + " contains=" + // + endNodeSet.contains(scGraph.getCurrentHNode(curNode))); + if (endNodeSet.contains(scGraph.getCurrentHNode(curNode))) { // it reaches to one of endNodeSet - return count; + return trace; } Set inNodeSet = getIncomingNodeSet(curNode); int curMaxDistance = 0; + Stack curMaxTrace = (Stack) trace.clone(); + ; for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { HNode inNode = (HNode) iterator.next(); // traverse more... @@ -1504,66 +1540,39 @@ public class HierarchyGraph { } } - System.out.println(" traverse more to" + inNode + " before-count=" + count); - int dist = recur_computeDistance2(startNode, inNode, endNodeSet, count, combineSet); - if (dist > curMaxDistance) { - curMaxDistance = dist; - } - } - return curMaxDistance; - } - - public int computeDistance2(HNode startNode, Set endNodeSet, Set combineSet) { - System.out.println("#####computeDistance startNode=" + startNode + " endNode=" + endNodeSet); - return recur_computeDistance2(startNode, startNode, endNodeSet, 0, 0, combineSet); - } - - private int recur_computeDistance2(HNode startNode, HNode curNode, Set endNodeSet, - int sharedCount, int nonSharedCount, Set combineSet) { + // Stack newTrace = (Stack) trace.clone(); + // Stack curTrace = + // recur_computeDistance(inNode, endNodeSet, scGraph, count, combineSet, newTrace); + // if (curTrace != null) { + // return curTrace; + // } - if (!curNode.equals(startNode)) { - // do not count the start node - if (curNode.isSharedNode()) { - sharedCount++; - } else { - nonSharedCount++; + Set inReachToNodeSet = getSkeleteNodeSetReachToNoTransitive(inNode); + Set inCurReachToNodeSet = new HashSet(); + for (Iterator iterator2 = inReachToNodeSet.iterator(); iterator2.hasNext();) { + HNode aboveNode = (HNode) iterator2.next(); + inCurReachToNodeSet.add(getCurrentHNode(aboveNode)); } - } - if (endNodeSet.contains(curNode)) { - // it reaches to one of endNodeSet - if (sharedCount > nonSharedCount) { - return sharedCount; - } else { - return nonSharedCount; - } - } + if (combineSet != null || inCurReachToNodeSet.equals(endNodeSet)) { + System.out + .println(" traverse to incomingNode=" + inNode + " before-trace=" + trace); - Set inNodeSet = getIncomingNodeSet(curNode); + Stack newTrace = (Stack) trace.clone(); + Stack curTrace = + recur_computeDistance2(inNode, endNodeSet, scGraph, count, combineSet, newTrace); - int curMaxDistance = 0; - for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { - HNode inNode = (HNode) iterator.next(); - // traverse more... - - if (inNode.isCombinationNode() && combineSet != null) { - // check if inNode have the same combination set of the starting node - Set inNodeCombineSet = getCombineSetByCombinationNode(inNode); - if (!inNodeCombineSet.equals(combineSet)) { - continue; + if (curTrace != null && curTrace.size() > curMaxDistance) { + curMaxTrace = curTrace; + curMaxDistance = curTrace.size(); } + } else { + System.out.println("NOT TRAVERSE a new inNode=" + inNode + " inReachToNodeSet=" + + inCurReachToNodeSet); } - System.out.println(" traverse more to" + inNode + " sC=" + sharedCount + " nC=" - + nonSharedCount); - int dist = - recur_computeDistance2(startNode, inNode, endNodeSet, sharedCount, nonSharedCount, - combineSet); - if (dist > curMaxDistance) { - curMaxDistance = dist; - } } - return curMaxDistance; + return curMaxTrace; } public int countNonSharedNode(HNode startNode, Set endNodeSet) { diff --git a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java index fb9d4d5c..61a90d09 100644 --- a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java +++ b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java @@ -26,6 +26,7 @@ import IR.ClassDescriptor; import IR.Descriptor; import IR.FieldDescriptor; import IR.MethodDescriptor; +import IR.NameDescriptor; import IR.State; import IR.SymbolTable; import IR.TypeUtil; @@ -112,6 +113,10 @@ public class SSJavaAnalysis { private Map> mapSharedLocToDescSet; + private Map> mapDescToCompleteLattice; + public Map mapNumLocsMapManual; + public Map mapNumPathsMapManual; + public SSJavaAnalysis(State state, TypeUtil tu, BuildFlat bf, CallGraph callgraph) { this.state = state; this.tu = tu; @@ -132,6 +137,9 @@ public class SSJavaAnalysis { this.sortedDescriptors = new LinkedList(); this.md2pcLoc = new HashMap(); this.mapSharedLocToDescSet = new HashMap>(); + this.mapDescToCompleteLattice = new HashMap>(); + this.mapNumLocsMapManual = new HashMap(); + this.mapNumPathsMapManual = new HashMap(); } public void doCheck() { @@ -151,6 +159,8 @@ public class SSJavaAnalysis { System.exit(0); } else { parseLocationAnnotation(); + debug_countNumLocations(); + // System.exit(0); doFlowDownCheck(); doDefinitelyWrittenCheck(); doLoopCheck(); @@ -160,9 +170,113 @@ public class SSJavaAnalysis { MethodDescriptor md = (MethodDescriptor) iterator.next(); MethodLattice locOrder = getMethodLattice(md); writeLatticeDotFile(md.getClassDesc(), md, getMethodLattice(md)); - // System.out.println("~~~\t" + md.getClassDesc() + "_" + md + "\t" - // + locOrder.getKeySet().size()); + System.out.println("~~~\t" + md.getClassDesc() + "_" + md + "\t" + + locOrder.getKeySet().size()); + } + + } + + private void debug_countNumLocations() { + + BuildLattice buildLattice = new BuildLattice(); + + for (Iterator iterator = cd2lattice.keySet().iterator(); iterator.hasNext();) { + ClassDescriptor cd = (ClassDescriptor) iterator.next(); + SSJavaLattice lattice = cd2lattice.get(cd).clone(); + SSJavaLattice completeLattice = debug_buildCompleteLattice(buildLattice, cd, lattice); + mapDescToCompleteLattice.put(cd, completeLattice); + writeLatticeDotFile(cd, null, completeLattice); + } + + for (Iterator iterator = md2lattice.keySet().iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + SSJavaLattice lattice = md2lattice.get(md).clone(); + SSJavaLattice completeLattice = debug_buildCompleteLattice(buildLattice, md, lattice); + mapDescToCompleteLattice.put(md, completeLattice); + writeLatticeDotFile(md.getClassDesc(), md, completeLattice); + } + + for (Iterator iterator = annotationRequireSet.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + SSJavaLattice lattice = getMethodLattice(md).clone(); + if (!mapDescToCompleteLattice.containsKey(md)) { + System.out.println("@NOT FOUND!"); + SSJavaLattice completeLattice = + debug_buildCompleteLattice(buildLattice, md, lattice); + mapDescToCompleteLattice.put(md, completeLattice); + writeLatticeDotFile(md.getClassDesc(), md, completeLattice); + } + } + + writeNumLocsPathsCSVFile(); + + } + + public SSJavaLattice debug_buildCompleteLattice(BuildLattice buildLattice, + Descriptor desc, SSJavaLattice lattice) { + + // First, create a hierarchy graph + HierarchyGraph hierarchyGraph = new HierarchyGraph(); + Set keySet = lattice.getKeySet(); + + Map mapLocNameToDesc = new HashMap(); + + for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) { + String higher = (String) iterator2.next(); + Set lowerSet = lattice.get(higher); + if (!mapLocNameToDesc.containsKey(higher)) { + mapLocNameToDesc.put(higher, new NameDescriptor(higher)); + } + + Descriptor higherDesc = mapLocNameToDesc.get(higher); + + for (Iterator iterator3 = lowerSet.iterator(); iterator3.hasNext();) { + String lower = (String) iterator3.next(); + if (!mapLocNameToDesc.containsKey(lower)) { + mapLocNameToDesc.put(lower, new NameDescriptor(lower)); + } + Descriptor lowerDesc = mapLocNameToDesc.get(lower); + hierarchyGraph.addEdge(higherDesc, lowerDesc); + } } + + BasisSet basisSet = hierarchyGraph.computeBasisSet(new HashSet()); + + SSJavaLattice completeLattice = buildLattice.buildLattice(hierarchyGraph); + + int numLocs = completeLattice.getKeySet().size() + 1; + LocationInference.numLocationsSInfer += numLocs; + mapNumLocsMapManual.put(desc, new Integer(numLocs)); + + System.out.println(desc + "::" + "lattice=" + lattice.getKeySet().size() + " complete=" + + numLocs); + + int numPaths = completeLattice.countPaths(); + LocationInference.numLocationsSInfer += numPaths; + mapNumPathsMapManual.put(desc, new Integer(numPaths)); + + return completeLattice; + } + + public void writeNumLocsPathsCSVFile() { + + try { + BufferedWriter bw = new BufferedWriter(new FileWriter("manualnumbers.csv")); + + Set keySet = mapNumLocsMapManual.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + int numLocs = mapNumLocsMapManual.get(desc); + int numPaths = mapNumPathsMapManual.get(desc); + bw.write(desc.getSymbol().replaceAll("[,]", "") + "," + numLocs + "," + numPaths + "\n"); + } + bw.close(); + + } catch (IOException e) { + // TODO Auto-generated catch block + e.printStackTrace(); + } + } public void init() { -- 2.34.1