changes.

[IRC.git] / Robust / src / Analysis / SSJava / GlobalFlowGraph.java

diff --git a/Robust/src/Analysis/SSJava/GlobalFlowGraph.java b/Robust/src/Analysis/SSJava/GlobalFlowGraph.java
index 35fbd006bb2fa93f887e0b260dce42cd3afc371a..bd0faa10eeff8ff525be6134bcee9169ae72b4b5 100644 (file)
--- a/Robust/src/Analysis/SSJava/GlobalFlowGraph.java
+++ b/Robust/src/Analysis/SSJava/GlobalFlowGraph.java
@@ -19,6 +19,7 @@ public class GlobalFlowGraph {
 
   Map<NTuple<Location>, GlobalFlowNode> mapLocTupleToNode;
   Map<GlobalFlowNode, Set<GlobalFlowNode>> mapFlowNodeToOutNodeSet;
+  Map<GlobalFlowNode, Set<GlobalFlowNode>> mapFlowNodeToInNodeSet;
 
   Map<Location, CompositeLocation> mapLocationToInferCompositeLocation;
 
@@ -26,6 +27,8 @@ public class GlobalFlowGraph {
     this.md = md;
     this.mapLocTupleToNode = new HashMap<NTuple<Location>, GlobalFlowNode>();
     this.mapFlowNodeToOutNodeSet = new HashMap<GlobalFlowNode, Set<GlobalFlowNode>>();
+    this.mapFlowNodeToInNodeSet = new HashMap<GlobalFlowNode, Set<GlobalFlowNode>>();
+
     this.mapLocationToInferCompositeLocation = new HashMap<Location, CompositeLocation>();
   }
 
@@ -37,6 +40,10 @@ public class GlobalFlowGraph {
     return mapLocationToInferCompositeLocation;
   }
 
+  public boolean contains(NTuple<Location> locTuple) {
+    return mapLocTupleToNode.containsKey(locTuple);
+  }
+
   public GlobalFlowNode getFlowNode(NTuple<Location> locTuple) {
     if (!mapLocTupleToNode.containsKey(locTuple)) {
       GlobalFlowNode node = createNewGlobalFlowNode(locTuple);
@@ -46,10 +53,17 @@ public class GlobalFlowGraph {
   }
 
   private GlobalFlowNode createNewGlobalFlowNode(NTuple<Location> locTuple) {
+    if (locTuple.size() == 0) {
+      throw new Error();
+    }
     GlobalFlowNode node = new GlobalFlowNode(locTuple);
     return node;
   }
 
+  public boolean contrainsInferCompositeLocationMapKey(Location loc) {
+    return mapLocationToInferCompositeLocation.containsKey(loc);
+  }
+
   public void addMapLocationToInferCompositeLocation(Location loc, CompositeLocation newCompLoc) {
     if (mapLocationToInferCompositeLocation.containsKey(loc)) {
       // need to do a sanity check
@@ -59,7 +73,7 @@ public class GlobalFlowGraph {
       CompositeLocation oldCompLoc = mapLocationToInferCompositeLocation.get(loc);
 
       if (newCompLoc.getSize() == oldCompLoc.getSize()) {
-        for (int i = 0; i < oldCompLoc.getSize(); i++) {
+        for (int i = 0; i < oldCompLoc.getSize() - 1; i++) {
           Location oldLocElement = oldCompLoc.get(i);
           Location newLocElement = newCompLoc.get(i);
 
@@ -86,8 +100,37 @@ public class GlobalFlowGraph {
     return mapLocationToInferCompositeLocation.get(loc);
   }
 
+  public boolean hasValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
+
+    // return true if the graph already has a flow edge
+
+    if (!mapLocTupleToNode.containsKey(fromLocTuple) || !mapLocTupleToNode.containsKey(toLocTuple)) {
+      return false;
+    }
+
+    GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
+    GlobalFlowNode toNode = getFlowNode(toLocTuple);
+
+    if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)
+        || !mapFlowNodeToInNodeSet.containsKey(toNode)) {
+      return false;
+    }
+
+    if (mapFlowNodeToOutNodeSet.get(fromNode).contains(toNode)
+        && mapFlowNodeToInNodeSet.get(toNode).contains(fromNode)) {
+      return true;
+    }
+
+    return false;
+  }
+
   public void addValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
 
+    Location lastElementfromLocTuple = fromLocTuple.get(fromLocTuple.size() - 1);
+    if (lastElementfromLocTuple.getLocDescriptor().equals(LocationInference.LITERALDESC)) {
+      return;
+    }
+
     GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
     GlobalFlowNode toNode = getFlowNode(toLocTuple);
 
@@ -96,8 +139,20 @@ public class GlobalFlowGraph {
     }
     mapFlowNodeToOutNodeSet.get(fromNode).add(toNode);
 
-    System.out.println("create a global edge from " + fromNode + " to " + toNode);
+    if (!mapFlowNodeToInNodeSet.containsKey(toNode)) {
+      mapFlowNodeToInNodeSet.put(toNode, new HashSet<GlobalFlowNode>());
+    }
+    mapFlowNodeToInNodeSet.get(toNode).add(fromNode);
+
+    // System.out.println("create a global edge from " + fromNode + " to " + toNode);
+
+  }
 
+  public Set<GlobalFlowNode> getInNodeSet(GlobalFlowNode node) {
+    if (!mapFlowNodeToInNodeSet.containsKey(node)) {
+      mapFlowNodeToInNodeSet.put(node, new HashSet<GlobalFlowNode>());
+    }
+    return mapFlowNodeToInNodeSet.get(node);
   }
 
   public Set<GlobalFlowNode> getNodeSet() {
@@ -202,6 +257,79 @@ public class GlobalFlowGraph {
 
   }
 
+  public Set<GlobalFlowNode> getIncomingNodeSetByPrefix(Location prefix) {
+
+    Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
+
+    for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
+      GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
+      Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
+
+      for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
+        GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
+        if (outNode.getLocTuple().startsWith(prefix)) {
+          incomingNodeSet.add(curNode);
+          recurIncomingNodeSetByPrefix(prefix, curNode, incomingNodeSet);
+        }
+
+      }
+    }
+
+    return incomingNodeSet;
+
+  }
+
+  private void recurIncomingNodeSetByPrefix(Location prefix, GlobalFlowNode node,
+      Set<GlobalFlowNode> visited) {
+
+    Set<GlobalFlowNode> inNodeSet = getInNodeSet(node);
+
+    for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
+      GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
+
+      if (!curNode.getLocTuple().startsWith(prefix) && !visited.contains(curNode)) {
+        visited.add(curNode);
+        recurIncomingNodeSetByPrefix(prefix, curNode, visited);
+      }
+    }
+
+  }
+
+  public Set<GlobalFlowNode> getReachableNodeSetByPrefix(Location prefix) {
+
+    Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
+
+    for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
+      GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
+
+      if (curNode.getLocTuple().startsWith(prefix)) {
+        Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
+        for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
+          GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
+          if (!outNode.getLocTuple().startsWith(prefix) && !reachableNodeSet.contains(outNode)) {
+            reachableNodeSet.add(outNode);
+            recurReachableNodeSetByPrefix(prefix, outNode, reachableNodeSet);
+          }
+
+        }
+      }
+    }
+
+    return reachableNodeSet;
+  }
+
+  private void recurReachableNodeSetByPrefix(Location prefix, GlobalFlowNode node,
+      Set<GlobalFlowNode> reachableNodeSet) {
+    Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
+    for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
+      GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
+      if (!outNode.getLocTuple().startsWith(prefix) && !reachableNodeSet.contains(outNode)) {
+        reachableNodeSet.add(outNode);
+        recurReachableNodeSetByPrefix(prefix, outNode, reachableNodeSet);
+      }
+    }
+  }
+
   public Set<GlobalFlowNode> getReachableNodeSetFrom(GlobalFlowNode node) {
 
     Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
@@ -221,4 +349,20 @@ public class GlobalFlowGraph {
     }
   }
 
+  public Set<GlobalFlowNode> debug_getIncomingNodeSetFromPrefix(GlobalFlowNode node,
+      NTuple<Location> curPrefix) {
+
+    Set<GlobalFlowNode> result = new HashSet<GlobalFlowNode>();
+
+    Set<GlobalFlowNode> allIncomingNodeSet = getIncomingNodeSet(node);
+    for (Iterator iterator = allIncomingNodeSet.iterator(); iterator.hasNext();) {
+      GlobalFlowNode incomingNode = (GlobalFlowNode) iterator.next();
+      if (incomingNode.getLocTuple().startsWith(curPrefix)) {
+        result.add(incomingNode);
+      }
+    }
+
+    return result;
+  }
+
 }