X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=src%2Fmain%2Fgov%2Fnasa%2Fjpf%2Flistener%2FConflictTracker.java;h=2ba4eca77a79eef876af31ceac8a11bd52f48763;hb=7fc8507dc2288f94a42c8d4d59107ace9ded3a99;hp=a0ecc4bb6721597ba8631d83deeb8929feb207f8;hpb=c61aed3f0b13d4c606f19fdb2f2e48708a47d5df;p=jpf-core.git

diff --git a/src/main/gov/nasa/jpf/listener/ConflictTracker.java b/src/main/gov/nasa/jpf/listener/ConflictTracker.java
index a0ecc4b..2ba4eca 100644
--- a/src/main/gov/nasa/jpf/listener/ConflictTracker.java
+++ b/src/main/gov/nasa/jpf/listener/ConflictTracker.java
@@ -37,7 +37,6 @@ import java.util.*;
  **/
 
 public class ConflictTracker extends ListenerAdapter {
-
   private final PrintWriter out;
   private final HashSet<String> conflictSet = new HashSet<String>(); // Variables we want to track
   private final HashSet<String> appSet = new HashSet<String>(); // Apps we want to find their conflicts
@@ -89,220 +88,285 @@ public class ConflictTracker extends ListenerAdapter {
   }
 
   boolean propagateTheChange(Node currentNode) {
-	HashSet<Node> changed = new HashSet<Node>(currentNode.getSuccessors());
-
-	while(!changed.isEmpty()) {
-        	// Get the first element of HashSet and remove it from the changed set
-      		Node nodeToProcess = changed.iterator().next();
-      		changed.remove(nodeToProcess);
-
-      		// Update the edge
-      		boolean isChanged = updateEdge(currentNode, nodeToProcess);
-
-      		// Check for a conflict in this transition(currentNode -> nodeToProcess)
-      		if (checkForConflict(nodeToProcess))
-       			return true;
-
-      		// Checking if the out set has changed or not(Add its successors to the change list!)
-      		if (isChanged) {
-			propagateTheChange(nodeToProcess);
-      		}
+    HashSet<Node> changed = new HashSet<Node>();
+    boolean isChanged = false;
+
+    // Add the current node to the changed set
+    changed.add(currentNode);
+
+    while(!changed.isEmpty()) {
+      // Get the first element of the changed set and remove it
+      Node nodeToProcess = changed.iterator().next();
+      changed.remove(nodeToProcess);
+
+      // Update all the successors of the node
+      for (Node node : nodeToProcess.getSuccessors()) {
+	isChanged = false;
+      	isChanged = updateTheOutSet(nodeToProcess, node);
+	if (isChanged) {
+          changed.add(node);
+          if (checkAllSuccForConflict(node))
+            return true;
+	}
       }
-
-      return false;
+    }
+    return false;
   }
 
   String createErrorMessage(NameValuePair pair, HashMap<String, String> valueMap, HashMap<String, Integer> writerMap) {
-	String message = "Conflict found between the two apps. App"+pair.getAppNum()+
-			 " has written the value: "+pair.getValue()+
-			 " to the variable: "+pair.getVarName()+" while App"+
-			 writerMap.get(pair.getVarName())+" is overwriting the value: "
-			 +valueMap.get(pair.getVarName())+" to the same variable!";
-	System.out.println(message);	
-	return message;
+    String message = "Conflict found between the two apps. App"+pair.getAppNum()+
+		     " has written the value: "+pair.getValue()+
+		     " to the variable: "+pair.getVarName()+" while App"
+		     +writerMap.get(pair.getVarName())+" is overwriting the value: "
+		     +valueMap.get(pair.getVarName())+" to the same variable!";
+    System.out.println(message);	
+    return message;
   }
 
-  boolean checkForConflict(Node nodeToProcess) {
-	HashMap<String, String> valueMap = new HashMap<String, String>(); // HashMap from varName to value
-	HashMap<String, Integer> writerMap = new HashMap<String, Integer>(); // HashMap from varName to appNum
-
-	// Update the valueMap
-	for (int i = 0;i < nodeToProcess.getSetSet().size();i++) {
-		NameValuePair nameValuePair = nodeToProcess.getSetSet().get(i);
-
-		if (valueMap.containsKey(nameValuePair.getVarName())) {
-			// Check if we have a same writer
-			if (!writerMap.get(nameValuePair.getVarName()).equals(nameValuePair.getAppNum())) {
-				// Check if we have a conflict or not
-				if (!valueMap.get(nameValuePair.getVarName()).equals(nameValuePair.getValue())) {
-					errorMessage = createErrorMessage(nameValuePair, valueMap, writerMap);
-					return true;
-				} else { // We have two writers writing the same value
-					writerMap.put(nameValuePair.getVarName(), 3); // 3 represents both apps
-				}	
-			} else {
-				// Check if we have more than one value with the same writer
-				if (!valueMap.get(nameValuePair.getVarName()).equals(nameValuePair.getValue())) {
-					valueMap.put(nameValuePair.getVarName(), "twoValue"); // We have one writer writing more than one value in a same event
-				}
-			}	
-		} else {
-			valueMap.put(nameValuePair.getVarName(), nameValuePair.getValue());
-			writerMap.put(nameValuePair.getVarName(), nameValuePair.getAppNum());
-		}
-	}
+  boolean checkAllSuccForConflict(Node currentNode) {
+    for (Node node : currentNode.getSuccessors()) {
+      HashMap<Transition, ArrayList<NameValuePair>> setSets = currentNode.getOutgoingEdges().get(node).getSetSetMap();
+      for (Map.Entry mapElement : setSets.entrySet()) {
+        Transition transition = (Transition)mapElement.getKey();
+	if (checkForConflict(currentNode, node, transition))
+	  return true;
+      }
+    }
+    return false;
+  }
 
-	// Comparing the outSet to setSet
-	for (NameValuePair i : nodeToProcess.getOutSet()) {
-		if (valueMap.containsKey(i.getVarName())) {
-			String value = valueMap.get(i.getVarName());
-			Integer writer = writerMap.get(i.getVarName());
-			if ((value != null)&&(writer != null)) {
-				if (!value.equals(i.getValue())&&!writer.equals(i.getAppNum())) { // We have different values
-					errorMessage = createErrorMessage(i, valueMap, writerMap);
-					return true;
-				}
-			}
-		}
+  boolean checkForConflict(Node parentNode, Node currentNode, Transition currentTransition) {
+    ArrayList<NameValuePair> setSet = parentNode.getOutgoingEdges().get(currentNode).getSetSetMap().get(currentTransition);
+    HashMap<String, String> valueMap = new HashMap<String, String>(); // HashMap from varName to value
+    HashMap<String, Integer> writerMap = new HashMap<String, Integer>(); //  HashMap from varName to appNum
+    HashMap<String, String> firstValueMap = new HashMap<String, String>(); // HashMap from varName to value - first instruction in transition
+    HashMap<String, Integer> firstWriterMap = new HashMap<String, Integer>(); // HashMap from varName to appNum - first instruction in transition
+	
+    // Update the valueMap and writerMap + check for conflict between the elements of setSet
+    for (int i = 0;i < setSet.size();i++) {
+      NameValuePair nameValuePair = setSet.get(i);
+      String varName = nameValuePair.getVarName();
+      String value = nameValuePair.getValue();
+      Integer appNum = nameValuePair.getAppNum();
+      Boolean isManual = nameValuePair.getIsManual();
+
+      if (valueMap.containsKey(varName)) {
+        // Check if we have a same writer
+	if (!writerMap.get(varName).equals(appNum)) {
+	  // Check if we have a conflict or not
+	  if (!valueMap.get(varName).equals(value)) {
+	    errorMessage = createErrorMessage(nameValuePair, valueMap, writerMap);
+	    return true;
+	  }
+	}
+	valueMap.put(varName, value);
+	writerMap.put(varName, appNum);
+      } else {
+        valueMap.put(varName, value);
+	writerMap.put(varName, appNum);
+	if (!isManual) {
+	  firstValueMap.put(varName, value);
+	  firstWriterMap.put(varName, appNum);
 	}
+      }
+    }
 
-	return false;
+    // Check for conflict between outSet and this transition setSet
+    for (NameValuePair i : parentNode.getOutSet()) {
+      if (firstValueMap.containsKey(i.getVarName())) {
+        String value = firstValueMap.get(i.getVarName());
+        Integer writer = firstWriterMap.get(i.getVarName());
+        if ((value != null)&&(writer != null)) {
+          if (!value.equals(i.getValue())&&!writer.equals(i.getAppNum())) { 
+	    // We have different values and different writers
+	    errorMessage = createErrorMessage(i, firstValueMap, firstWriterMap);
+	    return true;
+	  }
+        }
+      }
+    }
+    return false;
   }
 
-  boolean updateEdge(Node parentNode, Node currentNode) {
-	ArrayList<NameValuePair> setSet = currentNode.getSetSetMap().get(parentNode);
-	HashSet<String> updatedVarNames = new HashSet<String>();
-	HashMap<Integer, String> writerLastValue = new HashMap<Integer, String>();
+  boolean updateTheOutSet(Node parentNode, Node currentNode) {
+    Edge edge = parentNode.getOutgoingEdges().get(currentNode);
+    HashMap<Transition, ArrayList<NameValuePair>> setSets = edge.getSetSetMap();
+    HashSet<String> updatedVarNames = new HashSet<String>();
+    boolean isChanged = false;
 
-	boolean isChanged = false;
-	
-	if (setSet != null) {
-		for (int i = 0;i < setSet.size();i++) {
-			updatedVarNames.add(setSet.get(i).getVarName());
-			writerLastValue.put(setSet.get(i).getAppNum(), setSet.get(i).getValue());
-		}
-	}
+    for (Map.Entry mapElement : setSets.entrySet()) {
+      ArrayList<NameValuePair> setSet = (ArrayList<NameValuePair>)mapElement.getValue();
+  
+      for (int i = 0;i < setSet.size();i++) {
+        updatedVarNames.add(setSet.get(i).getVarName());
+      }
+    }
 
-	for (NameValuePair i : parentNode.getOutSet()) {
-		if (!updatedVarNames.contains(i.getVarName()))
-			isChanged |= currentNode.getOutSet().add(i);
-	}
+    for (NameValuePair i : parentNode.getOutSet()) {
+      if (!updatedVarNames.contains(i.getVarName()))
+        isChanged |= currentNode.getOutSet().add(i);
+    }
 
-	if (setSet != null) {
-		for (int i = 0;i < setSet.size();i++) {
-			if (setSet.get(i).getValue().equals(writerLastValue.get(setSet.get(i).getAppNum()))) {
-				isChanged |= currentNode.getOutSet().add(setSet.get(i));
-			}
-		}
-	}
+    ArrayList<NameValuePair> lastSetSet = setSets.get(edge.getFinalTransition());
 
-	return isChanged;
+    for (int i = 0;i < lastSetSet.size();i++) {
+      isChanged |= currentNode.getOutSet().add(lastSetSet.get(i));
+    }
+    return isChanged;
+  }
+
+  void updateTheEdge(Node currentNode, Transition transition) {
+    if (parentNode.getOutgoingEdges().containsKey(currentNode)) {
+      Edge currentEdge = parentNode.getOutgoingEdges().get(currentNode);
+      if (currentEdge.getSetSetMap().containsKey(transition)) { // Update the transition
+	if (manual)
+	  currentEdge.getSetSetMap().put(transition, tempSetSet);
+	else
+	  currentEdge.getSetSetMap().get(transition).addAll(tempSetSet);
+      } else { // Add a new transition
+	currentEdge.getSetSetMap().put(transition, tempSetSet);
+      }
+      currentEdge.setFinalTransition(transition);
+    } else {
+      parentNode.getOutgoingEdges().put(currentNode, new Edge(parentNode, currentNode));
+      Edge currentEdge = parentNode.getOutgoingEdges().get(currentNode);
+      currentEdge.getSetSetMap().put(transition, tempSetSet);
+      currentEdge.setFinalTransition(transition);
+    }
   }
 
   static class Node {
-        Integer id;
-	HashSet<Node> predecessors = new HashSet<Node>();
-	HashSet<Node> successors = new HashSet<Node>();
-	HashSet<NameValuePair> outSet = new HashSet<NameValuePair>();
-        ArrayList<NameValuePair> setSet = new ArrayList<NameValuePair>();
-	HashMap<Node, ArrayList<NameValuePair>> setSetMap = new HashMap<Node, ArrayList<NameValuePair>>();
-
-	Node(Integer id) {
-	  this.id = id;
-	}
+    Integer id;
+    HashSet<Node> predecessors = new HashSet<Node>();
+    HashSet<Node> successors = new HashSet<Node>();
+    HashSet<NameValuePair> outSet = new HashSet<NameValuePair>();
+    HashMap<Node, Edge> outgoingEdges = new HashMap<Node, Edge>();
+
+    Node(Integer id) {
+      this.id = id;
+    }
 
-	void addPredecessor(Node node) {
-	  predecessors.add(node);
-	}
+    Integer getId() {
+      return id;
+    }
 
-	void addSuccessor(Node node) {
-	  successors.add(node);
-	}
+    HashSet<Node> getPredecessors() {
+      return predecessors;
+    }
 
-	Integer getId() {
-		return id;
-	}
+    HashSet<Node> getSuccessors() {
+      return successors;
+    }
 
-	HashSet<Node> getPredecessors() {
-		return predecessors;
-	}
+    HashSet<NameValuePair> getOutSet() {
+      return outSet;
+    }
 
-	HashSet<Node> getSuccessors() {
-		return successors;
-	}
+    HashMap<Node, Edge> getOutgoingEdges() {
+      return outgoingEdges;
+    }
+  }
 
-	HashSet<NameValuePair> getOutSet() {
-		return outSet;
-	}
+  static class Edge {
+    Node source, destination;
+    Transition finalTransition;
+    HashMap<String, Integer> lastWriter = new HashMap<String, Integer>();
+    HashMap<String, String> lastValue = new HashMap<String, String>();
+    HashMap<Transition, ArrayList<NameValuePair>> setSetMap = new HashMap<Transition, ArrayList<NameValuePair>>();
 
-        ArrayList<NameValuePair> getSetSet() {
-		return setSet;
-        }
+    Edge(Node source, Node destination) {
+      this.source = source;
+      this.destination = destination;
+    }
 
-	HashMap<Node, ArrayList<NameValuePair>> getSetSetMap() {
-		return setSetMap;
-	}
+    Node getSource() {
+      return source;
+    }
+
+    Node getDestination() {
+      return destination;
+    }
+
+    Transition getFinalTransition() {
+      return finalTransition;
+    }
+
+    void setFinalTransition(Transition transition) {
+      finalTransition = transition;
+    }
+
+    HashMap<Transition, ArrayList<NameValuePair>> getSetSetMap() {
+      return setSetMap;
+    }
+
+    HashMap<String, Integer> getLastWriter() {
+      return lastWriter;
+    }
+
+    HashMap<String, String> getLastValue() {
+      return lastValue;
+    }
   }
 
   static class NameValuePair {
-	Integer appNum;
-	String value;
-	String varName;
-	boolean isManual;
-
-	NameValuePair(Integer appNum, String value, String varName, boolean isManual) {
-      		this.appNum = appNum;
-      		this.value = value;
-      		this.varName = varName;
-      		this.isManual = isManual;
-	}
+    Integer appNum;
+    String value;
+    String varName;
+    boolean isManual;
+
+    NameValuePair(Integer appNum, String value, String varName, boolean isManual) {
+      this.appNum = appNum;
+      this.value = value;
+      this.varName = varName;
+      this.isManual = isManual;
+    }
 
-	void setAppNum(Integer appNum) {
-		this.appNum = appNum;
-	}
+    void setAppNum(Integer appNum) {
+      this.appNum = appNum;
+    }
 
-	void setValue(String value) {
-		this.value = value;
-	}
+    void setValue(String value) {
+      this.value = value;
+    }
 
-	void setVarName(String varName) {
-		this.varName = varName;
-	}
+    void setVarName(String varName) {
+      this.varName = varName;
+    }
 
-        void setIsManual(String varName) {
-		this.isManual = isManual;
-	}
+    void setIsManual(String varName) {
+      this.isManual = isManual;
+    }
 
-	Integer getAppNum() {
-		return appNum;
-	}
+    Integer getAppNum() {
+      return appNum;
+    }
 
-	String getValue() {
-		return value;
-	}
+    String getValue() {
+      return value;
+    }
 
-	String getVarName() {
-		return varName;
-	}
+    String getVarName() {
+      return varName;
+    }
 
-	boolean getIsManual() {
-		return isManual;
-	}
+    boolean getIsManual() {
+      return isManual;
+    }
 
-	@Override
-	public boolean equals(Object o) {
+    @Override
+    public boolean equals(Object o) {
       if (o instanceof NameValuePair) {
         NameValuePair other = (NameValuePair) o;
         if (varName.equals(other.getVarName()))
           return appNum.equals(other.getAppNum());
       }
       return false;
-	}
+    }
 
-	@Override
-	public int hashCode() {
-		return appNum.hashCode() * 31 + varName.hashCode();
-	}
+    @Override
+    public int hashCode() {
+      return appNum.hashCode() * 31 + varName.hashCode();
+    }
   }
 
   @Override
@@ -316,9 +380,9 @@ public class ConflictTracker extends ListenerAdapter {
   
     // Update the parent node
     if (nodes.containsKey(id)) {
-	  parentNode = nodes.get(id);
+      parentNode = nodes.get(id);
     } else {
-	  parentNode = new Node(id);
+      parentNode = new Node(id);
     }
   }
 
@@ -331,27 +395,26 @@ public class ConflictTracker extends ListenerAdapter {
   @Override
   public void stateAdvanced(Search search) {
     String theEnd = null;
+    Transition transition = search.getTransition();
     id = search.getStateId();
     depth = search.getDepth();
     operation = "forward";
 
     // Add the node to the list of nodes
     if (nodes.get(id) == null)
-	nodes.put(id, new Node(id));
+      nodes.put(id, new Node(id));
 
     Node currentNode = nodes.get(id);
 
-    if ((currentNode.getSetSetMap().get(parentNode) == null) || manual)
-	currentNode.getSetSetMap().put(parentNode, new ArrayList<NameValuePair>());
+    // Update the edge based on the current transition
+    updateTheEdge(currentNode, transition);
 
-    // Update the setSet for the edge
-    currentNode.getSetSetMap().get(parentNode).addAll(tempSetSet);
-    parentNode.getSetSet().addAll(tempSetSet);
+    // Reset the temporary variables and flags
     tempSetSet = new ArrayList<NameValuePair>();
     manual = false;
 
-    // Check for the conflict in this edge
-    conflictFound = checkForConflict(parentNode);
+    // Check for the conflict in this transition
+    conflictFound = checkForConflict(parentNode, currentNode, transition);
 
     if (search.isNewState()) {
       detail = "new";
@@ -369,25 +432,25 @@ public class ConflictTracker extends ListenerAdapter {
     // Updating the predecessors for this node
     // Check if parent node is already in successors of the current node or not
     if (!(currentNode.getPredecessors().contains(parentNode)))
-	currentNode.addPredecessor(parentNode);
+      currentNode.getPredecessors().add(parentNode);
 
     // Update the successors for this node
     // Check if current node is already in successors of the parent node or not
     if (!(parentNode.getSuccessors().contains(currentNode)))
-        parentNode.addSuccessor(currentNode);
+      parentNode.getSuccessors().add(currentNode);
 
-    // Update the edge and check if the outset of the current node is changed or not to propagate the change
-    boolean isChanged = updateEdge(parentNode, currentNode);
-    
+    // Update the outset of the current node and check if it is changed or not to propagate the change
+    boolean isChanged = updateTheOutSet(parentNode, currentNode);
+	    
     // Check if the outSet of this state has changed, update all of its successors' sets if any
     if (isChanged)
-	conflictFound = conflictFound || propagateTheChange(currentNode);
-
+      conflictFound = conflictFound || checkAllSuccForConflict(currentNode) || propagateTheChange(currentNode);
+    
     // Update the parent node
     if (nodes.containsKey(id)) {
-	  parentNode = nodes.get(id);
+      parentNode = nodes.get(id);
     } else {
-	  parentNode = new Node(id);
+      parentNode = new Node(id);
     }
   }
 
@@ -402,9 +465,9 @@ public class ConflictTracker extends ListenerAdapter {
 
     // Update the parent node
     if (nodes.containsKey(id)) {
-	  parentNode = nodes.get(id);
+      parentNode = nodes.get(id);
     } else {
-	  parentNode = new Node(id);
+      parentNode = new Node(id);
     }
   }
 
@@ -551,7 +614,7 @@ public class ConflictTracker extends ListenerAdapter {
     // Update the temporary Set set.
     NameValuePair temp = new NameValuePair(1, value, var, manual);
     if (writer.equals("App2"))
-    	temp = new NameValuePair(2, value, var, manual);
+      temp = new NameValuePair(2, value, var, manual);
     
     tempSetSet.add(temp);
   }
@@ -577,7 +640,7 @@ public class ConflictTracker extends ListenerAdapter {
         MethodInfo mi = executedInsn.getMethodInfo();
         // Find the last load before return and get the value here
         if (mi.getName().equals(SET_LOCATION_METHOD) &&
-                executedInsn instanceof ALOAD && nextInsn instanceof ARETURN) {
+            executedInsn instanceof ALOAD && nextInsn instanceof ARETURN) {
           byte type  = getType(ti, executedInsn);
           String value = getValue(ti, executedInsn, type);
 
@@ -604,7 +667,7 @@ public class ConflictTracker extends ListenerAdapter {
 
               if (getWriter(ti.getStack(), manualSet) != null)
                 manual = true;
-
+	      
               // Update the temporary Set set.
               writeWriterAndValue(writer, value, var);
             }