import java.io.FileWriter;
import java.io.PrintWriter;
-import java.lang.reflect.Field;
import java.util.*;
import java.util.logging.Logger;
import java.io.IOException;
private HashMap<Integer, LinkedList<BacktrackExecution>> backtrackMap; // Track created backtracking points
private PriorityQueue<Integer> backtrackStateQ; // Heap that returns the latest state
private Execution currentExecution; // Holds the information about the current execution
- private HashSet<String> doneBacktrackSet; // Record state ID and trace already constructed
+ private HashMap<Integer, HashSet<Integer>> doneBacktrackMap; // Record state ID and trace already constructed
private HashMap<Integer, RestorableVMState> restorableStateMap; // Maps state IDs to the restorable state object
private RGraph rGraph; // R-Graph for past executions
private boolean isEndOfExecution;
// Statistics
- private int numOfConflicts;
private int numOfTransitions;
public DPORStateReducer(Config config, JPF jpf) {
}
}
isBooleanCGFlipped = false;
- numOfConflicts = 0;
numOfTransitions = 0;
nonRelevantClasses = new HashSet<>();
nonRelevantFields = new HashSet<>();
@Override
public void searchFinished(Search search) {
- if (stateReductionMode) {
- // Number of conflicts = first trace + subsequent backtrack points
- numOfConflicts += 1 + doneBacktrackSet.size();
- }
if (verboseMode) {
out.println("\n==> DEBUG: ----------------------------------- search finished");
out.println("\n==> DEBUG: State reduction mode : " + stateReductionMode);
- out.println("\n==> DEBUG: Number of conflicts : " + numOfConflicts);
out.println("\n==> DEBUG: Number of transitions : " + numOfTransitions);
out.println("\n==> DEBUG: ----------------------------------- search finished" + "\n");
fileWriter.println("==> DEBUG: State reduction mode : " + stateReductionMode);
- fileWriter.println("==> DEBUG: Number of conflicts : " + numOfConflicts);
fileWriter.println("==> DEBUG: Number of transitions : " + numOfTransitions);
fileWriter.println();
fileWriter.close();
// Initialize with necessary information from the CG
if (nextCG instanceof IntChoiceFromSet) {
IntChoiceFromSet icsCG = (IntChoiceFromSet) nextCG;
+ // Tell JPF that we are performing DPOR
+ icsCG.setDpor();
if (!isEndOfExecution) {
// Check if CG has been initialized, otherwise initialize it
Integer[] cgChoices = icsCG.getAllChoices();
if (!isBooleanCGFlipped) {
isBooleanCGFlipped = true;
} else {
- // Number of conflicts = first trace + subsequent backtrack points
- numOfConflicts = 1 + doneBacktrackSet.size();
// Allocate new objects for data structure when the boolean is flipped from "false" to "true"
initializeStatesVariables();
}
private ArrayList<TransitionEvent> executionTrace; // The BacktrackPoint objects of this execution
private boolean isNew; // Track if this is the first time it is accessed
private HashMap<Integer, ReadWriteSet> readWriteFieldsMap; // Record fields that are accessed
- private HashMap<Integer, TransitionEvent> stateToTransitionMap; // For O(1) access to backtrack point
public Execution() {
cgToChoiceMap = new HashMap<>();
executionTrace = new ArrayList<>();
isNew = true;
readWriteFieldsMap = new HashMap<>();
- stateToTransitionMap = new HashMap<>();
}
public void addTransition(TransitionEvent newBacktrackPoint) {
return executionTrace.get(0);
}
- public HashMap<Integer, ReadWriteSet> getReadWriteFieldsMap() {
- return readWriteFieldsMap;
+ public TransitionEvent getLastTransition() {
+ return executionTrace.get(executionTrace.size() - 1);
}
- public TransitionEvent getTransitionFromState(int stateId) {
- if (stateToTransitionMap.containsKey(stateId)) {
- return stateToTransitionMap.get(stateId);
- }
- // Return the latest transition for unseen states (that have just been encountered in this transition)
- return executionTrace.get(executionTrace.size() - 1);
+ public HashMap<Integer, ReadWriteSet> getReadWriteFieldsMap() {
+ return readWriteFieldsMap;
}
public boolean isNew() {
public void mapCGToChoice(IntChoiceFromSet icsCG, int choice) {
cgToChoiceMap.put(icsCG, choice);
}
-
- public void mapStateToTransition(int stateId, TransitionEvent transition) {
- stateToTransitionMap.put(stateId, transition);
- }
}
// This class compactly stores a predecessor
}
public HashSet<TransitionEvent> getReachableTransitionsAtState(int stateId) {
+ if (!graph.containsKey(stateId)) {
+ // This is a loop from a transition to itself, so just return the current transition
+ HashSet<TransitionEvent> transitionSet = new HashSet<>();
+ transitionSet.add(currentExecution.getLastTransition());
+ return transitionSet;
+ }
return graph.get(stateId);
}
HashSet<TransitionEvent> reachableTransitions = new HashSet<>();
// All transitions from states higher than the given state ID (until the highest state ID) are reachable
for(int stId = stateId; stId <= hiStateId; stId++) {
- reachableTransitions.addAll(graph.get(stId));
+ // We might encounter state IDs from the first round of Boolean CG
+ // The second round of Boolean CG should consider these new states
+ if (graph.containsKey(stId)) {
+ reachableTransitions.addAll(graph.get(stId));
+ }
}
return reachableTransitions;
}
// Add new transition to the current execution and map it in R-Graph
for (Integer stId : justVisitedStates) { // Map this transition to all the previously passed states
rGraph.addReachableTransition(stId, transition);
- currentExecution.mapStateToTransition(stId, transition);
}
currentExecution.mapCGToChoice(icsCG, choiceCounter);
// Store restorable state object for this state (always store the latest)
- RestorableVMState restorableState = vm.getRestorableState();
- restorableStateMap.put(stateId, restorableState);
+ if (!restorableStateMap.containsKey(stateId)) {
+ RestorableVMState restorableState = vm.getRestorableState();
+ restorableStateMap.put(stateId, restorableState);
+ }
}
private TransitionEvent setupTransition(IntChoiceFromSet icsCG, int stateId, int choiceIndex) {
backtrackStateQ = new PriorityQueue<>(Collections.reverseOrder());
currentExecution = new Execution();
currentExecution.addTransition(new TransitionEvent()); // Always start with 1 backtrack point
- doneBacktrackSet = new HashSet<>();
+ doneBacktrackMap = new HashMap<>();
rGraph = new RGraph();
// Booleans
isEndOfExecution = false;
// Check if this trace is already constructed
private boolean isTraceAlreadyConstructed(int firstChoice, int stateId) {
// Concatenate state ID and only the first event in the string, e.g., "1:1 for the trace 10234 at state 1"
- // TODO: THIS IS AN OPTIMIZATION!
- // This is the optimized version because after we execute, e.g., the trace 1:10234, we don't need to try
- // another trace that starts with event 1 at state 1, e.g., the trace 1:13024
- // The second time this event 1 is explored, it will generate the same state as the first one
- StringBuilder sb = new StringBuilder();
- sb.append(stateId);
- sb.append(':');
- sb.append(firstChoice);
// Check if the trace has been constructed as a backtrack point for this state
- if (doneBacktrackSet.contains(sb.toString())) {
- return true;
+ // TODO: THIS IS AN OPTIMIZATION!
+ HashSet<Integer> choiceSet;
+ if (doneBacktrackMap.containsKey(stateId)) {
+ choiceSet = doneBacktrackMap.get(stateId);
+ if (choiceSet.contains(firstChoice)) {
+ return true;
+ }
+ } else {
+ choiceSet = new HashSet<>();
+ doneBacktrackMap.put(stateId, choiceSet);
}
- doneBacktrackSet.add(sb.toString());
+ choiceSet.add(firstChoice);
+
return false;
}
updateBacktrackSetRecursive(execution, currentChoice, conflictExecution, conflictChoice,
pushedExecution, pushedChoice, 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
// 2) at least 2 choices/events have been explored (choiceCounter > 1),
// 3) state > 0 (state 0 is for boolean CG)
if (!isEndOfExecution && choiceCounter > 1 && stateId > 0) {
- if (currVisitedStates.contains(stateId)) {
- // Get the backtrack point from the current execution
- TransitionEvent transition = currentExecution.getTransitionFromState(stateId);
- transition.recordPredecessor(currentExecution, choiceCounter - 1);
- updateBacktrackSetsFromPreviousExecution(stateId);
- } else if (prevVisitedStates.contains(stateId)) { // We visit a state in a previous execution
- // Update past executions with a predecessor
+ if (currVisitedStates.contains(stateId) || prevVisitedStates.contains(stateId)) {
+ // Update reachable transitions in the graph with a predecessor
HashSet<TransitionEvent> reachableTransitions = rGraph.getReachableTransitionsAtState(stateId);
for(TransitionEvent transition : reachableTransitions) {
transition.recordPredecessor(currentExecution, choiceCounter - 1);
projects / jpf-core.git / blobdiff