From: yeom Date: Thu, 8 Nov 2012 06:49:58 +0000 (+0000) Subject: changes. it generates correct lattices. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=commitdiff_plain;h=f7b671e1dd0d86e45ef2ceb2d83fde738997720d changes. it generates correct lattices. --- diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index cbddb358..fd2d0e8f 100644 --- a/Robust/src/Analysis/SSJava/BuildLattice.java +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -17,10 +17,14 @@ public class BuildLattice { private Map mapSharedNodeToTripleItem; private Map mapHNodeToHighestIndex; + private Map, Integer> mapItemToHighestIndex; + public BuildLattice(LocationInference infer) { this.infer = infer; this.mapSharedNodeToTripleItem = new HashMap(); this.mapHNodeToHighestIndex = new HashMap(); + this.mapItemToHighestIndex = new HashMap, Integer>(); + } public SSJavaLattice buildLattice(Descriptor desc) { @@ -166,355 +170,6 @@ public class BuildLattice { public SSJavaLattice insertIntermediateNodesToStraightLine(Descriptor desc, SSJavaLattice skeletonLattice) { - mapSharedNodeToTripleItem.clear(); - - HierarchyGraph hierarchyGraph = infer.getSimpleHierarchyGraph(desc); - HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc); - LocationSummary locSummary = infer.getLocationSummary(desc); - SSJavaLattice lattice = skeletonLattice.clone(); - Set visited = new HashSet(); - Set scNodeSet = scGraph.getNodeSet(); - - Map mapIntermediateLoc = new HashMap(); - - for (Iterator iterator = scNodeSet.iterator(); iterator.hasNext();) { - HNode scNode = (HNode) iterator.next(); - Set outHierarchyNodeSet = hierarchyGraph.getOutgoingNodeSet(scNode); - for (Iterator iterator2 = outHierarchyNodeSet.iterator(); iterator2.hasNext();) { - HNode outHierarchyNode = (HNode) iterator2.next(); - - if (!visited.contains(outHierarchyNode)) { - - if (!outHierarchyNode.isCombinationNode() && !outHierarchyNode.isSkeleton()) { - visited.add(outHierarchyNode); - Set outSCNodeSet = scGraph.getOutgoingNodeSet(scNode); - - if (outSCNodeSet.size() > 0) { - // follows the straight line up to another skeleton/combination node - outSCNodeSet = removeTransitivelyReachToNode(desc, scNode, outSCNodeSet); - } else if (outSCNodeSet.size() == 0) { - // the outNode is (directly/transitively) connected to the bottom node - // therefore, we just add a dummy bottom HNode to the endCombNodeSet. - outSCNodeSet.add(LocationInference.BOTTOMHNODE); - } - - recurDFVisitNormalNode(scNode, outSCNodeSet, outHierarchyNode, 1, desc, lattice, - visited, locSummary, mapIntermediateLoc); - } else if (outHierarchyNode.isCombinationNode()) { - visited.add(outHierarchyNode); - expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, - outHierarchyNode); - } - - } - - } - - } - - // add shared locations - Set sharedNodeSet = mapSharedNodeToTripleItem.keySet(); - for (Iterator iterator = sharedNodeSet.iterator(); iterator.hasNext();) { - HNode sharedNode = (HNode) iterator.next(); - TripleItem item = mapSharedNodeToTripleItem.get(sharedNode); - String nonSharedLocName = mapIntermediateLoc.get(item); - // System.out.println("sharedNode=" + sharedNode + " locName=" + nonSharedLocName); - - String newLocName; - if (locSummary.getHNodeNameSetByLatticeLoationName(nonSharedLocName) != null - && !lattice.isSharedLoc(nonSharedLocName)) { - // need to generate a new shared location in the lattice, which is one level lower than the - // 'locName' location - newLocName = "ILOC" + (LocationInference.locSeed++); - - // Set aboveElementSet = getAboveElementSet(lattice, locName); - Set belowElementSet = new HashSet(); - belowElementSet.addAll(lattice.get(nonSharedLocName)); - - // System.out.println("nonSharedLocName=" + nonSharedLocName + " belowElementSet=" - // + belowElementSet + " newLocName=" + newLocName); - - lattice.insertNewLocationBetween(nonSharedLocName, belowElementSet, newLocName); - } else { - newLocName = nonSharedLocName; - } - - lattice.addSharedLoc(newLocName); - HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc); - Set descSet = graph.getDescSetOfNode(sharedNode); - for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) { - Descriptor d = (Descriptor) iterator2.next(); - locSummary.addMapHNodeNameToLocationName(d.getSymbol(), newLocName); - } - locSummary.addMapHNodeNameToLocationName(sharedNode.getName(), newLocName); - - } - - return lattice; - } - - private void recurDFVisitNormalNode(HNode scStartNode, Set scEndNodeSet, - HNode curHierarchyNode, int idx, Descriptor desc, SSJavaLattice lattice, - Set visited, LocationSummary locSummary, Map mapIntermediateLoc) { - - TripleItem item = new TripleItem(scStartNode, scEndNodeSet, idx); - // System.out.println("item=" + item); - if (!mapIntermediateLoc.containsKey(item)) { - // need to create a new intermediate location in the lattice - String newLocName = "ILOC" + (LocationInference.locSeed++); - String above; - if (idx == 1) { - above = scStartNode.getName(); - } else { - int prevIdx = idx - 1; - TripleItem prevItem = new TripleItem(scStartNode, scEndNodeSet, prevIdx); - above = mapIntermediateLoc.get(prevItem); - } - - Set belowSet = new HashSet(); - for (Iterator iterator = scEndNodeSet.iterator(); iterator.hasNext();) { - HNode endNode = (HNode) iterator.next(); - String locName; - if (locSummary.getMapHNodeNameToLocationName().containsKey(endNode.getName())) { - locName = locSummary.getLocationName(endNode.getName()); - } else { - locName = endNode.getName(); - } - belowSet.add(locName); - } - lattice.insertNewLocationBetween(above, belowSet, newLocName); - - mapIntermediateLoc.put(item, newLocName); - } - - String curLocName = mapIntermediateLoc.get(item); - HierarchyGraph hierarchyGraph = infer.getSimpleHierarchyGraph(desc); - - if (curHierarchyNode.isSharedNode()) { - // if the current node is shared location, add a shared location to the lattice later - mapSharedNodeToTripleItem.put(curHierarchyNode, item); - } else { - Set descSet = hierarchyGraph.getDescSetOfNode(curHierarchyNode); - for (Iterator iterator = descSet.iterator(); iterator.hasNext();) { - Descriptor d = (Descriptor) iterator.next(); - locSummary.addMapHNodeNameToLocationName(d.getSymbol(), curLocName); - } - locSummary.addMapHNodeNameToLocationName(curHierarchyNode.getName(), curLocName); - } - - System.out.println("-TripleItem normal=" + item); - System.out.println("-curNode=" + curHierarchyNode.getName() + " S=" - + curHierarchyNode.isSharedNode() + " locName=" + curLocName + " isC=" - + curHierarchyNode.isCombinationNode()); - - Set outSet = hierarchyGraph.getOutgoingNodeSet(curHierarchyNode); - for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) { - HNode outHierarchyNodeFromCurNode = (HNode) iterator2.next(); - - // Set incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode); - System.out.println("outHierarchyNodeFromCurNode=" + outHierarchyNodeFromCurNode); - // System.out.println("---incomingHNodeSetToOutNode=" + incomingHNodeSetToOutNode); - - if (outHierarchyNodeFromCurNode.isSkeleton() - || outHierarchyNodeFromCurNode.isCombinationNode()) { - String lowerLocName = locSummary.getLocationName(outHierarchyNodeFromCurNode.getName()); - lattice.addRelationHigherToLower(curLocName, lowerLocName); - } else { - if (visited.containsAll(hierarchyGraph.getIncomingNodeSet(outHierarchyNodeFromCurNode))) { - visited.add(outHierarchyNodeFromCurNode); - int newidx = getCurrentHighestIndex(outHierarchyNodeFromCurNode, idx + 1); - recurDFVisitNormalNode(scStartNode, scEndNodeSet, outHierarchyNodeFromCurNode, newidx, - desc, lattice, visited, locSummary, mapIntermediateLoc); - } else { - System.out.println("NOT RECUR"); - updateHighestIndex(outHierarchyNodeFromCurNode, idx + 1); - } - } - - // if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) { - // if (visited.containsAll(simpleHierarchyGraph.getIncomingNodeSet(outNode))) { - // visited.add(outNode); - // int newidx = getCurrentHighestIndex(outNode, idx + 1); - // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc, - // newidx, locSummary, outNode); - // // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc, - // // idx + 1, locSummary, outNode); - // } else { - // updateHighestIndex(outNode, idx + 1); - // System.out.println("NOT RECUR"); - // } - // } else if (!outNode.isSkeleton() && outNode.isCombinationNode() && - // !visited.contains(outNode)) { - // if (needToExpandCombinationNode(desc, outNode)) { - // System.out.println("NEED TO"); - // expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode); - // } else { - // System.out.println("NOT NEED TO"); - // } - // } - - } - - } - - private void recurDFVisitCombinationNode(HNode scCombNode, Set scEndNodeSet, - HNode curHierarchyCombNode, int idx, Descriptor desc, SSJavaLattice lattice, - Set visited, LocationSummary locSummary, Map mapIntermediateLoc) { - - // Descriptor desc, SSJavaLattice lattice, - // HNode combinationNodeInSCGraph, Set endNodeSet, Set visited, - // Map mapIntermediateLoc, int idx, LocationSummary locSummary, HNode - // curNode) { - - TripleItem item = new TripleItem(scCombNode, scEndNodeSet, idx); - - if (!mapIntermediateLoc.containsKey(item)) { - // need to create a new intermediate location in the lattice - String above; - if (idx == 1) { - String newLocName = scCombNode.getName(); - mapIntermediateLoc.put(item, newLocName); - } else { - String newLocName = "ILOC" + (LocationInference.locSeed++); - int prevIdx = idx - 1; - TripleItem prevItem = new TripleItem(scCombNode, scEndNodeSet, prevIdx); - above = mapIntermediateLoc.get(prevItem); - - Set belowSet = new HashSet(); - for (Iterator iterator = scEndNodeSet.iterator(); iterator.hasNext();) { - HNode endNode = (HNode) iterator.next(); - belowSet.add(endNode.getName()); - } - lattice.insertNewLocationBetween(above, belowSet, newLocName); - mapIntermediateLoc.put(item, newLocName); - } - - } - - HierarchyGraph hierarchyNode = infer.getSimpleHierarchyGraph(desc); - String locName = mapIntermediateLoc.get(item); - if (curHierarchyCombNode.isSharedNode()) { - // if the current node is shared location, add a shared location to the lattice later - mapSharedNodeToTripleItem.put(curHierarchyCombNode, item); - } else { - Set descSet = hierarchyNode.getDescSetOfNode(curHierarchyCombNode); - for (Iterator iterator = descSet.iterator(); iterator.hasNext();) { - Descriptor d = (Descriptor) iterator.next(); - locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName); - } - locSummary.addMapHNodeNameToLocationName(curHierarchyCombNode.getName(), locName); - } - - System.out.println("-TripleItem=" + item); - System.out.println("-curNode=" + curHierarchyCombNode.getName() + " S=" - + curHierarchyCombNode.isSharedNode() + " locName=" + locName); - - Set outSet = hierarchyNode.getOutgoingNodeSet(curHierarchyCombNode); - for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) { - HNode outHierarchyNode = (HNode) iterator2.next(); - - System.out.println("---recurDFS outNode=" + outHierarchyNode); - System.out.println("---outNode combinationNodeInSCGraph=" - + getCombinationNodeInSCGraph(desc, outHierarchyNode)); - - if (outHierarchyNode.isCombinationNode()) { - HNode outCombinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, outHierarchyNode); - if (outCombinationNodeInSCGraph.equals(scCombNode)) { - - Set combineSkeletonNodeSet = - hierarchyNode.getCombineSetByCombinationNode(outHierarchyNode); - Set incomingHNodeSetToOutNode = hierarchyNode.getIncomingNodeSet(outHierarchyNode); - // extract nodes belong to the same combine node - Set incomingCombinedHNodeSet = new HashSet(); - for (Iterator iterator = incomingHNodeSetToOutNode.iterator(); iterator.hasNext();) { - HNode inNode = (HNode) iterator.next(); - if (combineSkeletonNodeSet.contains(inNode)) { - incomingCombinedHNodeSet.add(inNode); - } - } - System.out.println("incomingCombinedHNodeSet=" + incomingCombinedHNodeSet); - if (visited.containsAll(incomingCombinedHNodeSet)) { - visited.add(outHierarchyNode); - System.out.println("-------curIdx=" + (idx + 1)); - int newIdx = getCurrentHighestIndex(outHierarchyNode, idx + 1); - System.out.println("-------newIdx=" + newIdx); - recurDFVisitCombinationNode(scCombNode, scEndNodeSet, outHierarchyNode, newIdx, desc, - lattice, visited, locSummary, mapIntermediateLoc); - } else { - updateHighestIndex(outHierarchyNode, idx + 1); - System.out.println("-----NOT RECUR!"); - } - - } - } - - } - - } - - private void expandCombinationNode(Descriptor desc, SSJavaLattice lattice, - Set visited, Map mapIntermediateLoc, LocationSummary locSummary, - HNode cnode) { - - // expand the combination node 'outNode' - // here we need to expand the corresponding combination location in the lattice - HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode); - Set endNodeSet = - infer.getSkeletonCombinationHierarchyGraph(desc).getOutgoingNodeSet( - combinationNodeInSCGraph); - - System.out.println("expandCombinationNode=" + cnode + " cnode in scgraph=" - + combinationNodeInSCGraph); - System.out.println("endnodeset=" + endNodeSet); - - if (combinationNodeInSCGraph == null) { - return; - } - - // HierarchyGraph hierarchyGraph = infer.getSimpleHierarchyGraph(desc); - // - // Set combineSkeletonNodeSet = hierarchyGraph.getCombineSetByCombinationNode(cnode); - // - // // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet); - // - // Set combinationNodeSet = - // hierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet); - // - // // System.out.println("combinationNodeSet=" + combinationNodeSet); - // - // Set endNodeSetFromSimpleGraph = - // hierarchyGraph.getDirectlyReachableSkeletonCombinationNodeFrom(cnode, combinationNodeSet); - // // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph); - // Set endCombNodeSet = new HashSet(); - // for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) { - // HNode endNode = (HNode) iterator3.next(); - // endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode)); - // } - - visited.add(cnode); - - // follows the straight line up to another skeleton/combination node - if (endNodeSet.size() > 0) { - // System.out.println("---endCombNodeSet=" + endCombNodeSet); - endNodeSet = removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endNodeSet); - - recurDFVisitCombinationNode(combinationNodeInSCGraph, endNodeSet, cnode, 1, desc, lattice, - visited, locSummary, mapIntermediateLoc); - - } else { - endNodeSet.add(LocationInference.BOTTOMHNODE); - // System.out.println("---endCombNodeSet is zero"); - // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph); - // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode)); - recurDFVisitCombinationNode(combinationNodeInSCGraph, endNodeSet, cnode, 1, desc, lattice, - visited, locSummary, mapIntermediateLoc); - } - - } - - public SSJavaLattice insertIntermediateNodesToStraightLine2(Descriptor desc, - SSJavaLattice skeletonLattice) { - // perform DFS that starts from each skeleton/combination node and ends by another // skeleton/combination node @@ -549,7 +204,7 @@ public class BuildLattice { if (outNode.isCombinationNode()) { if (visited.containsAll(simpleGraph.getIncomingNodeSet(outNode))) { // if (needToExpandCombinationNode(desc, outNode)) { - expandCombinationNode3(desc, lattice, visited, mapIntermediateLoc, locSummary, + expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode); // } } @@ -567,16 +222,18 @@ public class BuildLattice { // startNode = node; // } - Set endNodeSetFromSimpleGraph = - simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null); + // TODO + // Set endNodeSetFromSimpleGraph = + // simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null); + // Set endCombNodeSet = new HashSet(); + // for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); + // iterator3.hasNext();) { + // HNode endNode = (HNode) iterator3.next(); + // endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode)); + // } + + Set endCombNodeSet = scGraph.getOutgoingNodeSet(startNode); - // System.out.println("endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph - // + " from=" + outNode); - Set endCombNodeSet = new HashSet(); - for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) { - HNode endNode = (HNode) iterator3.next(); - endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode)); - } // System.out.println("endCombNodeSet=" + endCombNodeSet); visited.add(outNode); if (endCombNodeSet.size() > 0) { @@ -636,7 +293,8 @@ public class BuildLattice { HNode sharedNode = (HNode) iterator.next(); TripleItem item = mapSharedNodeToTripleItem.get(sharedNode); String nonSharedLocName = mapIntermediateLoc.get(item); - // System.out.println("sharedNode=" + sharedNode + " locName=" + nonSharedLocName); + + System.out.println("sharedNode=" + sharedNode + " locName=" + nonSharedLocName); String newLocName; if (locSummary.getHNodeNameSetByLatticeLoationName(nonSharedLocName) != null @@ -649,8 +307,8 @@ public class BuildLattice { Set belowElementSet = new HashSet(); belowElementSet.addAll(lattice.get(nonSharedLocName)); - // System.out.println("nonSharedLocName=" + nonSharedLocName + " belowElementSet=" - // + belowElementSet + " newLocName=" + newLocName); + System.out.println("nonSharedLocName=" + nonSharedLocName + " belowElementSet=" + + belowElementSet + " newLocName=" + newLocName); lattice.insertNewLocationBetween(nonSharedLocName, belowElementSet, newLocName); } else { @@ -711,6 +369,66 @@ public class BuildLattice { return true; } + private void expandCombinationNode(Descriptor desc, SSJavaLattice lattice, + Set visited, Map mapIntermediateLoc, LocationSummary locSummary, + HNode cnode) { + + // expand the combination node 'outNode' + // here we need to expand the corresponding combination location in the lattice + HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode); + + System.out.println("expandCombinationNode=" + cnode + " cnode in scgraph=" + + combinationNodeInSCGraph); + + if (combinationNodeInSCGraph == null) { + return; + } + + HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc); + HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc); + + Set combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode); + + // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet); + + Set combinationNodeSet = + simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet); + + // System.out.println("combinationNodeSet=" + combinationNodeSet); + + // TODO + // Set endNodeSetFromSimpleGraph = + // simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(cnode, combinationNodeSet); + // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph); + // Set endCombNodeSet = new HashSet(); + // for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) { + // HNode endNode = (HNode) iterator3.next(); + // endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode)); + // } + + Set endCombNodeSet = scGraph.getOutgoingNodeSet(combinationNodeInSCGraph); + visited.add(cnode); + + // follows the straight line up to another skeleton/combination node + if (endCombNodeSet.size() > 0) { + // System.out.println("---endCombNodeSet=" + endCombNodeSet); + endCombNodeSet = + removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet); + + recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited, + mapIntermediateLoc, 1, locSummary, cnode); + } else { + endCombNodeSet.add(LocationInference.BOTTOMHNODE); + // System.out.println("---endCombNodeSet is zero"); + // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph); + // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode)); + recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited, + mapIntermediateLoc, 1, locSummary, cnode); + + } + + } + private Set removeTransitivelyReachToNode(Descriptor desc, HNode startNode, Set endNodeSet) { @@ -801,62 +519,6 @@ public class BuildLattice { return connected.iterator().next(); } - private void expandCombinationNode3(Descriptor desc, SSJavaLattice lattice, - Set visited, Map mapIntermediateLoc, LocationSummary locSummary, - HNode cnode) { - - // expand the combination node 'outNode' - // here we need to expand the corresponding combination location in the lattice - HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode); - - System.out.println("expandCombinationNode=" + cnode + " cnode in scgraph=" - + combinationNodeInSCGraph); - - if (combinationNodeInSCGraph == null) { - return; - } - - HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc); - - Set combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode); - - // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet); - - Set combinationNodeSet = - simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet); - - // System.out.println("combinationNodeSet=" + combinationNodeSet); - - Set endNodeSetFromSimpleGraph = - simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(cnode, combinationNodeSet); - // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph); - Set endCombNodeSet = new HashSet(); - for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) { - HNode endNode = (HNode) iterator3.next(); - endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode)); - } - visited.add(cnode); - - // follows the straight line up to another skeleton/combination node - if (endCombNodeSet.size() > 0) { - // System.out.println("---endCombNodeSet=" + endCombNodeSet); - endCombNodeSet = - removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet); - - recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited, - mapIntermediateLoc, 1, locSummary, cnode); - } else { - endCombNodeSet.add(LocationInference.BOTTOMHNODE); - // System.out.println("---endCombNodeSet is zero"); - // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph); - // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode)); - recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited, - mapIntermediateLoc, 1, locSummary, cnode); - - } - - } - private void recurDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph, HNode startNode, HNode curNode, Set connected) { @@ -877,7 +539,6 @@ public class BuildLattice { int idx, LocationSummary locSummary, HNode curNode) { TripleItem item = new TripleItem(startNode, endNodeSet, idx); - // System.out.println("item=" + item); if (!mapIntermediateLoc.containsKey(item)) { // need to create a new intermediate location in the lattice String newLocName = "ILOC" + (LocationInference.locSeed++); @@ -934,21 +595,24 @@ public class BuildLattice { System.out.println("---incomingHNodeSetToOutNode=" + incomingHNodeSetToOutNode); if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) { + Pair pair = new Pair(startNode, outNode); if (visited.containsAll(simpleHierarchyGraph.getIncomingNodeSet(outNode))) { visited.add(outNode); - int newidx = getCurrentHighestIndex(outNode, idx + 1); + int newidx = getCurrentHighestIndex(pair, idx + 1); + // int newidx = getCurrentHighestIndex(outNode, idx + 1); recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc, newidx, locSummary, outNode); // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc, // idx + 1, locSummary, outNode); } else { - updateHighestIndex(outNode, idx + 1); + updateHighestIndex(pair, idx + 1); + // updateHighestIndex(outNode, idx + 1); System.out.println("NOT RECUR"); } } else if (!outNode.isSkeleton() && outNode.isCombinationNode() && !visited.contains(outNode)) { if (needToExpandCombinationNode(desc, outNode)) { System.out.println("NEED TO"); - expandCombinationNode3(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode); + expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode); } else { System.out.println("NOT NEED TO"); } @@ -1040,24 +704,27 @@ public class BuildLattice { // check whether the next combination node is different from the current node if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) { + Pair pair = new Pair(combinationNodeInSCGraph, outNode); if (visited.containsAll(incomingCombinedHNodeSet)) { visited.add(outNode); System.out.println("-------curIdx=" + (idx + 1)); - int newIdx = getCurrentHighestIndex(outNode, idx + 1); + + int newIdx = getCurrentHighestIndex(pair, idx + 1); + // int newIdx = getCurrentHighestIndex(outNode, idx + 1); System.out.println("-------newIdx=" + newIdx); recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited, mapIntermediateLoc, newIdx, locSummary, outNode); // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited, // mapIntermediateLoc, idx + 1, locSummary, outNode); } else { - updateHighestIndex(outNode, idx + 1); + updateHighestIndex(pair, idx + 1); + // updateHighestIndex(outNode, idx + 1); System.out.println("-----NOT RECUR!"); } } else { if (needToExpandCombinationNode(desc, outNode)) { System.out.println("NEED TO"); - expandCombinationNode3(desc, lattice, visited, mapIntermediateLoc, locSummary, - outNode); + expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode); } else { System.out.println("NOT NEED TO"); } @@ -1071,6 +738,15 @@ public class BuildLattice { } + private int getCurrentHighestIndex(Pair pair, int curIdx) { + int recordedIdx = getCurrentHighestIndex(pair); + if (recordedIdx > curIdx) { + return recordedIdx; + } else { + return curIdx; + } + } + private int getCurrentHighestIndex(HNode node, int curIdx) { int recordedIdx = getCurrentHighestIndex(node); if (recordedIdx > curIdx) { @@ -1080,6 +756,19 @@ public class BuildLattice { } } + private int getCurrentHighestIndex(Pair pair) { + if (!mapItemToHighestIndex.containsKey(pair)) { + mapItemToHighestIndex.put(pair, new Integer(-1)); + } + return mapItemToHighestIndex.get(pair).intValue(); + } + + private void updateHighestIndex(Pair pair, int idx) { + if (idx > getCurrentHighestIndex(pair)) { + mapItemToHighestIndex.put(pair, new Integer(idx)); + } + } + private int getCurrentHighestIndex(HNode node) { if (!mapHNodeToHighestIndex.containsKey(node)) { mapHNodeToHighestIndex.put(node, new Integer(-1)); diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index ce62cf57..f9bb5e90 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -783,6 +783,9 @@ public class HierarchyGraph { // System.out.println("--combineSet=" + combineSet); HNode combinationNode = getCombinationNode(combineSet); System.out.println("--combinationNode=" + combinationNode + " combineSet=" + combineSet); + + System.out.println("--hierarchynodes=" + + simpleHierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSet)); // add an edge from a skeleton node to a combination node for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) { HNode inSkeletonNode = (HNode) iterator2.next(); @@ -972,7 +975,11 @@ public class HierarchyGraph { HNode node = (HNode) iterator.next(); if (!node.isSkeleton()) { Set reachToSet = getSkeleteNodeSetReachTo(node); - System.out.println("$node=" + node + " reachToNodeSet=" + reachToSet); + // Set tempSet = removeTransitivelyReachToSet(reachToSet); + // reachToSet = removeTransitivelyReachToSet(reachToSet); + Set tempSet = reachToSet; + System.out.println("$node=" + node + " reachToNodeSet=" + reachToSet + " tempSet=" + + tempSet); if (reachToSet.size() > 1) { // if (countSkeletonNodes(reachToSet) > 1) { System.out.println("-node=" + node + " reachToSet=" + reachToSet); @@ -995,6 +1002,38 @@ public class HierarchyGraph { } + private Set removeTransitivelyReachToSet(Set reachToSet) { + + Set toberemoved = new HashSet(); + Set visited = new HashSet(); + for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) { + HNode node = (HNode) iterator.next(); + visited.add(node); + recurIsReachingTo(node, reachToSet, toberemoved, visited); + } + + Set rSet = new HashSet(); + rSet.addAll(reachToSet); + rSet.removeAll(toberemoved); + return rSet; + } + + private void recurIsReachingTo(HNode curNode, Set reachToSet, Set toberemoved, + Set visited) { + Set inNodeSet = getIncomingNodeSet(curNode); + + for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { + HNode inNode = (HNode) iterator.next(); + if (reachToSet.contains(inNode)) { + toberemoved.add(inNode); + } else if (!visited.contains(inNode)) { + visited.add(inNode); + recurIsReachingTo(inNode, reachToSet, toberemoved, visited); + } + } + + } + public Map> getMapCombinationNodeToCombineNodeSet() { return mapCombinationNodeToCombineNodeSet; } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 05500e22..fe7d2b92 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -452,7 +452,7 @@ public class LocationInference { String locName; if (!enclosingDesc.equals(GLOBALDESC)) { LocationSummary locSummary = getLocationSummary(enclosingDesc); -// HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(enclosingDesc); + // HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(enclosingDesc); HierarchyGraph scGraph = getSimpleHierarchyGraph(enclosingDesc); if (scGraph != null) { HNode curNode = scGraph.getCurrentHNode(nodeIdentifier); @@ -2150,15 +2150,17 @@ public class LocationInference { Set keySet = mapDescriptorToSkeletonHierarchyGraph.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Descriptor desc = (Descriptor) iterator.next(); - System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc); + System.out.println("\nSSJAVA: Inserting 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(); + // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph, + // skeletonGraph); + // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph(); + skeletonGraphWithCombinationNode.removeRedundantEdges(); mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode); } } @@ -3302,6 +3304,8 @@ public class LocationInference { // int size = paramLocTupleHavingInFlowSet.size(); int size = countFirstDescriptorSetSize(paramLocTupleHavingInFlowSet); + System.out.println("numParam=" + numParam + " size=" + size); + // if (!md.isStatic()) { // // // if the method is not static && there is a parameter composite location && @@ -4660,7 +4664,7 @@ public class LocationInference { private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable, IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) { - System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0)); + // System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0)); NodeTupleSet condTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,