Cleaning up DPORStateReducer.java

[jpf-core.git] / src / main / gov / nasa / jpf / listener / DPORStateReducer.java

diff --git a/src/main/gov/nasa/jpf/listener/DPORStateReducer.java b/src/main/gov/nasa/jpf/listener/DPORStateReducer.java
old mode 100644 (file)
new mode 100755 (executable)
index 5ce8c40..9ce2c3d
--- a/src/main/gov/nasa/jpf/listener/DPORStateReducer.java
+++ b/src/main/gov/nasa/jpf/listener/DPORStateReducer.java
@@ -531,6 +531,8 @@ public class DPORStateReducer extends ListenerAdapter {
     private int choiceCounter;                 // Choice counter at this transition
     private Execution execution;               // The execution where this transition belongs
     private HashSet<Predecessor> predecessors; // Maps incoming events/transitions (execution and choice)
+    private HashMap<Execution, HashSet<Integer>> recordedPredecessors;
+                                               // Memorize event and choice number to not record them twice
     private int stateId;                       // State at this transition
     private IntChoiceFromSet transitionCG;     // CG at this transition
 
@@ -539,6 +541,7 @@ public class DPORStateReducer extends ListenerAdapter {
       choiceCounter = 0;
       execution = null;
       predecessors = new HashSet<>();
+      recordedPredecessors = new HashMap<>();
       stateId = 0;
       transitionCG = null;
     }
@@ -565,8 +568,28 @@ public class DPORStateReducer extends ListenerAdapter {
 
     public IntChoiceFromSet getTransitionCG() { return transitionCG; }
 
+    private boolean isRecordedPredecessor(Execution execution, int choice) {
+      // See if we have recorded this predecessor earlier
+      HashSet<Integer> recordedChoices;
+      if (recordedPredecessors.containsKey(execution)) {
+        recordedChoices = recordedPredecessors.get(execution);
+        if (recordedChoices.contains(choice)) {
+          return true;
+        }
+      } else {
+        recordedChoices = new HashSet<>();
+        recordedPredecessors.put(execution, recordedChoices);
+      }
+      // Record the choice if we haven't seen it
+      recordedChoices.add(choice);
+
+      return false;
+    }
+
     public void recordPredecessor(Execution execution, int choice) {
-      predecessors.add(new Predecessor(choice, execution));
+      if (!isRecordedPredecessor(execution, choice)) {
+        predecessors.add(new Predecessor(choice, execution));
+      }
     }
 
     public void setChoice(int cho) {
@@ -1100,41 +1123,9 @@ public class DPORStateReducer extends ListenerAdapter {
     // Memorize visited TransitionEvent object while performing backward DFS to avoid getting caught up in a cycle
     HashSet<TransitionEvent> visited = new HashSet<>();
     // Update backtrack set recursively
-    // TODO: The following is the call to the original version of the method
-//    updateBacktrackSetRecursive(execution, currentChoice, execution, currentChoice, currRWSet, visited);
-    // TODO: The following is the call to the version of the method with pushing up happens-before transitions
     updateBacktrackSetRecursive(execution, currentChoice, execution, currentChoice, currRWSet, visited);
   }
 
-//  TODO: This is the original version of the recursive method
-//  private void updateBacktrackSetRecursive(Execution execution, int currentChoice,
-//                                           Execution conflictExecution, int conflictChoice,
-//                                           ReadWriteSet currRWSet, HashSet<TransitionEvent> visited) {
-//    // Halt when we have found the first read/write conflicts for all memory locations
-//    if (currRWSet.isEmpty()) {
-//      return;
-//    }
-//    TransitionEvent confTrans = conflictExecution.getExecutionTrace().get(conflictChoice);
-//    // Halt when we have visited this transition (in a cycle)
-//    if (visited.contains(confTrans)) {
-//      return;
-//    }
-//    visited.add(confTrans);
-//    // Explore all predecessors
-//    for (Predecessor predecessor : confTrans.getPredecessors()) {
-//      // Get the predecessor (previous conflict choice)
-//      conflictChoice = predecessor.getChoice();
-//      conflictExecution = predecessor.getExecution();
-//      // Check if a conflict is found
-//      if (isConflictFound(execution, currentChoice, conflictExecution, conflictChoice, currRWSet)) {
-//        createBacktrackingPoint(execution, currentChoice, conflictExecution, conflictChoice);
-//      }
-//      // Continue performing DFS if conflict is not found
-//      updateBacktrackSetRecursive(execution, currentChoice, conflictExecution, conflictChoice, currRWSet, visited);
-//    }
-//  }
-
-  // TODO: This is the version of the method with pushing up happens-before transitions
   private void updateBacktrackSetRecursive(Execution execution, int currentChoice,
                                            Execution conflictExecution, int conflictChoice,
                                            ReadWriteSet currRWSet, HashSet<TransitionEvent> visited) {
@@ -1159,16 +1150,13 @@ public class DPORStateReducer extends ListenerAdapter {
       // Check if a conflict is found
       if (isConflictFound(conflictExecution, conflictChoice, predecessorExecution, predecessorChoice, currRWSet)) {
         createBacktrackingPoint(conflictExecution, conflictChoice, predecessorExecution, predecessorChoice);
-        newConflictChoice = conflictChoice;
-        newConflictExecution = conflictExecution;
+        newConflictChoice = predecessorChoice;
+        newConflictExecution = predecessorExecution;
       }
       // Continue performing DFS if conflict is not found
       updateBacktrackSetRecursive(predecessorExecution, predecessorChoice, newConflictExecution, newConflictChoice,
               currRWSet, visited);
     }
-    // Remove the transition after being explored
-    // TODO: Seems to cause a lot of loops---commented out for now
-    //visited.remove(confTrans);
   }
 
   // --- Functions related to the reachability analysis when there is a state match
@@ -1185,13 +1173,13 @@ public class DPORStateReducer extends ListenerAdapter {
         for(TransitionEvent transition : reachableTransitions) {
           transition.recordPredecessor(currentExecution, choiceCounter - 1);
         }
-        updateBacktrackSetsFromPreviousExecution(stateId);
+        updateBacktrackSetsFromGraph(stateId);
       }
     }
   }
 
   // Update the backtrack sets from previous executions
-  private void updateBacktrackSetsFromPreviousExecution(int stateId) {
+  private void updateBacktrackSetsFromGraph(int stateId) {
     // Collect all the reachable transitions from R-Graph
     HashSet<TransitionEvent> reachableTransitions = rGraph.getReachableTransitions(stateId);
     for(TransitionEvent transition : reachableTransitions) {