X-Git-Url: http://plrg.eecs.uci.edu/git/?p=jpf-core.git;a=blobdiff_plain;f=src%2Fmain%2Fgov%2Fnasa%2Fjpf%2Flistener%2FDPORStateReducer.java;h=8531e2cc4db5c1588ba3db63204858786fae26f8;hp=746adfeb2ece84d88ba72a6ee0bfa988db0ba33e;hb=2c85b3bb2b21786f8eb76be7fd4eb7dc22d95e4b;hpb=c003a76b9c164b2b07f2fd8515ea36af2a6167e8 diff --git a/src/main/gov/nasa/jpf/listener/DPORStateReducer.java b/src/main/gov/nasa/jpf/listener/DPORStateReducer.java index 746adfe..8531e2c 100644 --- a/src/main/gov/nasa/jpf/listener/DPORStateReducer.java +++ b/src/main/gov/nasa/jpf/listener/DPORStateReducer.java @@ -28,6 +28,7 @@ import gov.nasa.jpf.vm.bytecode.WriteInstruction; import gov.nasa.jpf.vm.choice.IntChoiceFromSet; import gov.nasa.jpf.vm.choice.IntIntervalGenerator; +import java.awt.*; import java.io.PrintWriter; import java.util.*; @@ -48,7 +49,7 @@ import java.util.*; */ public class DPORStateReducer extends ListenerAdapter { - // Debug info fields + // Information printout fields for verbose mode private boolean verboseMode; private boolean stateReductionMode; private final PrintWriter out; @@ -57,6 +58,34 @@ public class DPORStateReducer extends ListenerAdapter { private int id; private Transition transition; + // DPOR-related fields + // Basic information + private Integer[] choices; + private Integer[] refChoices; // Second reference to a copy of choices (choices may be modified for fair scheduling) + private int choiceCounter; + private int maxEventChoice; + // Data structure to track the events seen by each state to track cycles (containing all events) for termination + private HashSet currVisitedStates; // States being visited in the current execution + private HashSet justVisitedStates; // States just visited in the previous choice/event + private HashSet prevVisitedStates; // States visited in the previous execution + private HashMap> stateToEventMap; + // Data structure to analyze field Read/Write accesses and conflicts + private HashMap> backtrackMap; // Track created backtracking points + private PriorityQueue backtrackStateQ; // Heap that returns the latest state + private ArrayList backtrackPointList; // Record backtrack points (CG, state Id, and choice) + private HashMap> conflictPairMap; // Record conflicting events + private HashSet doneBacktrackSet; // Record state ID and trace that are done + private HashMap readWriteFieldsMap; // Record fields that are accessed + private HashMap restorableStateMap; // Maps state IDs to the restorable state object + + // Visible operation dependency graph implementation (SPIN paper) related fields + private int prevChoiceValue; + private HashMap> vodGraphMap; // Visible operation dependency graph (VOD graph) + + // Boolean states + private boolean isBooleanCGFlipped; + private boolean isEndOfExecution; + public DPORStateReducer(Config config, JPF jpf) { verboseMode = config.getBoolean("printout_state_transition", false); stateReductionMode = config.getBoolean("activate_state_reduction", true); @@ -65,6 +94,9 @@ public class DPORStateReducer extends ListenerAdapter { } else { out = null; } + isBooleanCGFlipped = false; + restorableStateMap = new HashMap<>(); + initializeStatesVariables(); } @Override @@ -105,6 +137,9 @@ public class DPORStateReducer extends ListenerAdapter { out.println("\n==> DEBUG: The state is forwarded to state with id: " + id + " with depth: " + depth + " which is " + detail + " Transition: " + transition + "\n"); } + if (stateReductionMode) { + updateStateInfo(search); + } } @Override @@ -118,6 +153,9 @@ public class DPORStateReducer extends ListenerAdapter { out.println("\n==> DEBUG: The state is backtracked to state with id: " + id + " -- Transition: " + transition + " and depth: " + depth + "\n"); } + if (stateReductionMode) { + updateStateInfo(search); + } } @Override @@ -126,4 +164,669 @@ public class DPORStateReducer extends ListenerAdapter { out.println("\n==> DEBUG: ----------------------------------- search finished" + "\n"); } } + + @Override + public void choiceGeneratorRegistered(VM vm, ChoiceGenerator nextCG, ThreadInfo currentThread, Instruction executedInstruction) { + if (stateReductionMode) { + // Initialize with necessary information from the CG + if (nextCG instanceof IntChoiceFromSet) { + IntChoiceFromSet icsCG = (IntChoiceFromSet) nextCG; + if (!isEndOfExecution) { + // Check if CG has been initialized, otherwise initialize it + Integer[] cgChoices = icsCG.getAllChoices(); + // Record the events (from choices) + if (choices == null) { + choices = cgChoices; + // Make a copy of choices as reference + refChoices = copyChoices(choices); + // Record the max event choice (the last element of the choice array) + maxEventChoice = choices[choices.length - 1]; + } + icsCG.setNewValues(choices); + icsCG.reset(); + // Use a modulo since choiceCounter is going to keep increasing + int choiceIndex = choiceCounter % choices.length; + icsCG.advance(choices[choiceIndex]); + } else { + // Set done all CGs while transitioning to a new execution + icsCG.setDone(); + } + } + } + } + + @Override + public void choiceGeneratorAdvanced(VM vm, ChoiceGenerator currentCG) { + + if (stateReductionMode) { + // Check the boolean CG and if it is flipped, we are resetting the analysis + if (currentCG instanceof BooleanChoiceGenerator) { + if (!isBooleanCGFlipped) { + isBooleanCGFlipped = true; + } else { + // Allocate new objects for data structure when the boolean is flipped from "false" to "true" + initializeStatesVariables(); + } + } + // Check every choice generated and ensure fair scheduling! + if (currentCG instanceof IntChoiceFromSet) { + IntChoiceFromSet icsCG = (IntChoiceFromSet) currentCG; + // If this is a new CG then we need to update data structures + resetStatesForNewExecution(icsCG, vm); + // If we don't see a fair scheduling of events/choices then we have to enforce it + fairSchedulingAndBacktrackPoint(icsCG, vm); + // Map state to event + mapStateToEvent(icsCG.getNextChoice()); + // Update the VOD graph always with the latest + updateVODGraph(icsCG.getNextChoice()); + // Check if we have seen this state or this state contains cycles that involve all events + if (terminateCurrentExecution()) { + exploreNextBacktrackPoints(vm, icsCG); + } + justVisitedStates.clear(); + choiceCounter++; + } + } + } + + @Override + public void instructionExecuted(VM vm, ThreadInfo ti, Instruction nextInsn, Instruction executedInsn) { + if (stateReductionMode) { + if (!isEndOfExecution) { + // Has to be initialized and a integer CG + ChoiceGenerator cg = vm.getChoiceGenerator(); + if (cg instanceof IntChoiceFromSet || cg instanceof IntIntervalGenerator) { + int currentChoice = choiceCounter - 1; // Accumulative choice w.r.t the current trace + if (currentChoice < 0) { // If choice is -1 then skip + return; + } + currentChoice = checkAndAdjustChoice(currentChoice, vm); + // Record accesses from executed instructions + if (executedInsn instanceof JVMFieldInstruction) { + // Analyze only after being initialized + String fieldClass = ((JVMFieldInstruction) executedInsn).getFieldInfo().getFullName(); + // We don't care about libraries + if (!isFieldExcluded(fieldClass)) { + analyzeReadWriteAccesses(executedInsn, fieldClass, currentChoice); + } + } else if (executedInsn instanceof INVOKEINTERFACE) { + // Handle the read/write accesses that occur through iterators + analyzeReadWriteAccesses(executedInsn, ti, currentChoice); + } + // Analyze conflicts from next instructions + if (nextInsn instanceof JVMFieldInstruction) { + // Skip the constructor because it is called once and does not have shared access with other objects + if (!nextInsn.getMethodInfo().getName().equals("")) { + String fieldClass = ((JVMFieldInstruction) nextInsn).getFieldInfo().getFullName(); + if (!isFieldExcluded(fieldClass)) { + // Check for conflict (go backward from current choice and get the first conflict) + for (int eventCounter = currentChoice - 1; eventCounter >= 0; eventCounter--) { + // Check for conflicts with Write fields for both Read and Write instructions + // Check and record a backtrack set for just once! + if (isConflictFound(nextInsn, eventCounter, currentChoice, fieldClass) && + isNewConflict(currentChoice, eventCounter)) { + // Lines 4-8 of the algorithm in the paper page 11 (see the heading note above) + if (vm.isNewState() || isReachableInVODGraph(currentChoice)) { + createBacktrackingPoint(currentChoice, eventCounter); + } + } + } + } + } + } + } + } + } + } + + + // == HELPERS + + // -- INNER CLASSES + + // This class compactly stores Read and Write field sets + // We store the field name and its object ID + // Sharing the same field means the same field name and object ID + private class ReadWriteSet { + private HashMap readSet; + private HashMap writeSet; + + public ReadWriteSet() { + readSet = new HashMap<>(); + writeSet = new HashMap<>(); + } + + public void addReadField(String field, int objectId) { + readSet.put(field, objectId); + } + + public void addWriteField(String field, int objectId) { + writeSet.put(field, objectId); + } + + public boolean readFieldExists(String field) { + return readSet.containsKey(field); + } + + public boolean writeFieldExists(String field) { + return writeSet.containsKey(field); + } + + public int readFieldObjectId(String field) { + return readSet.get(field); + } + + public int writeFieldObjectId(String field) { + return writeSet.get(field); + } + } + + // This class compactly stores backtrack points: 1) backtrack state ID, and 2) backtracking choices + private class BacktrackPoint { + private IntChoiceFromSet backtrackCG; // CG at this backtrack point + private int stateId; // State at this backtrack point + private int choice; // Choice chosen at this backtrack point + + public BacktrackPoint(IntChoiceFromSet cg, int stId, int cho) { + backtrackCG = cg; + stateId = stId; + choice = cho; + } + + public IntChoiceFromSet getBacktrackCG() { return backtrackCG; } + + public int getStateId() { + return stateId; + } + + public int getChoice() { + return choice; + } + } + + // -- CONSTANTS + private final static String DO_CALL_METHOD = "doCall"; + // We exclude fields that come from libraries (Java and Groovy), and also the infrastructure + private final static String[] EXCLUDED_FIELDS_CONTAINS_LIST = {"_closure"}; + private final static String[] EXCLUDED_FIELDS_ENDS_WITH_LIST = + // Groovy library created fields + {"stMC", "callSiteArray", "metaClass", "staticClassInfo", "__constructor__", + // Infrastructure + "sendEvent", "Object", "reference", "location", "app", "state", "log", "functionList", "objectList", + "eventList", "valueList", "settings", "printToConsole", "app1", "app2"}; + private final static String[] EXCLUDED_FIELDS_STARTS_WITH_LIST = + // Java and Groovy libraries + { "java", "org", "sun", "com", "gov", "groovy"}; + private final static String[] EXCLUDED_FIELDS_READ_WRITE_INSTRUCTIONS_STARTS_WITH_LIST = {"Event"}; + private final static String GET_PROPERTY_METHOD = + "invokeinterface org.codehaus.groovy.runtime.callsite.CallSite.callGetProperty"; + private final static String GROOVY_CALLSITE_LIB = "org.codehaus.groovy.runtime.callsite"; + private final static String JAVA_INTEGER = "int"; + private final static String JAVA_STRING_LIB = "java.lang.String"; + + // -- FUNCTIONS + private void fairSchedulingAndBacktrackPoint(IntChoiceFromSet icsCG, VM vm) { + // Check the next choice and if the value is not the same as the expected then force the expected value + int choiceIndex = choiceCounter % refChoices.length; + int nextChoice = icsCG.getNextChoice(); + if (refChoices[choiceIndex] != nextChoice) { + int expectedChoice = refChoices[choiceIndex]; + int currCGIndex = icsCG.getNextChoiceIndex(); + if ((currCGIndex >= 0) && (currCGIndex < refChoices.length)) { + icsCG.setChoice(currCGIndex, expectedChoice); + } + } + // Record state ID and choice/event as backtrack point + int stateId = vm.getStateId(); + backtrackPointList.add(new BacktrackPoint(icsCG, stateId, refChoices[choiceIndex])); + // Store restorable state object for this state (always store the latest) + RestorableVMState restorableState = vm.getRestorableState(); + restorableStateMap.put(stateId, restorableState); + } + + private Integer[] copyChoices(Integer[] choicesToCopy) { + + Integer[] copyOfChoices = new Integer[choicesToCopy.length]; + System.arraycopy(choicesToCopy, 0, copyOfChoices, 0, choicesToCopy.length); + return copyOfChoices; + } + + // --- Functions related to cycle detection + + // Detect cycles in the current execution/trace + // We terminate the execution iff: + // (1) the state has been visited in the current execution + // (2) the state has one or more cycles that involve all the events + // With simple approach we only need to check for a re-visited state. + // Basically, we have to check that we have executed all events between two occurrences of such state. + private boolean containsCyclesWithAllEvents(int stId) { + + // False if the state ID hasn't been recorded + if (!stateToEventMap.containsKey(stId)) { + return false; + } + HashSet visitedEvents = stateToEventMap.get(stId); + // Check if this set contains all the event choices + // If not then this is not the terminating condition + for(int i=0; i<=maxEventChoice; i++) { + if (!visitedEvents.contains(i)) { + return false; + } + } + return true; + } + + private void initializeStatesVariables() { + // DPOR-related + choices = null; + refChoices = null; + choiceCounter = 0; + maxEventChoice = 0; + // Cycle tracking + currVisitedStates = new HashSet<>(); + justVisitedStates = new HashSet<>(); + prevVisitedStates = new HashSet<>(); + stateToEventMap = new HashMap<>(); + // Backtracking + backtrackMap = new HashMap<>(); + backtrackStateQ = new PriorityQueue<>(Collections.reverseOrder()); + backtrackPointList = new ArrayList<>(); + conflictPairMap = new HashMap<>(); + doneBacktrackSet = new HashSet<>(); + readWriteFieldsMap = new HashMap<>(); + // VOD graph + prevChoiceValue = -1; + vodGraphMap = new HashMap<>(); + // Booleans + isEndOfExecution = false; + } + + private void mapStateToEvent(int nextChoiceValue) { + // Update all states with this event/choice + // This means that all past states now see this transition + Set stateSet = stateToEventMap.keySet(); + for(Integer stateId : stateSet) { + HashSet eventSet = stateToEventMap.get(stateId); + eventSet.add(nextChoiceValue); + } + } + + private boolean terminateCurrentExecution() { + // We need to check all the states that have just been visited + // Often a transition (choice/event) can result into forwarding/backtracking to a number of states + for(Integer stateId : justVisitedStates) { + if (prevVisitedStates.contains(stateId) || containsCyclesWithAllEvents(stateId)) { + return true; + } + } + return false; + } + + private void updateStateInfo(Search search) { + // Update the state variables + // Line 19 in the paper page 11 (see the heading note above) + int stateId = search.getStateId(); + currVisitedStates.add(stateId); + // Insert state ID into the map if it is new + if (!stateToEventMap.containsKey(stateId)) { + HashSet eventSet = new HashSet<>(); + stateToEventMap.put(stateId, eventSet); + } + justVisitedStates.add(stateId); + } + + // --- Functions related to Read/Write access analysis on shared fields + + private void addNewBacktrackPoint(int stateId, Integer[] newChoiceList) { + // Insert backtrack point to the right state ID + LinkedList backtrackList; + if (backtrackMap.containsKey(stateId)) { + backtrackList = backtrackMap.get(stateId); + } else { + backtrackList = new LinkedList<>(); + backtrackMap.put(stateId, backtrackList); + } + backtrackList.addFirst(newChoiceList); + // Add to priority queue + if (!backtrackStateQ.contains(stateId)) { + backtrackStateQ.add(stateId); + } + } + + // Analyze Read/Write accesses that are directly invoked on fields + private void analyzeReadWriteAccesses(Instruction executedInsn, String fieldClass, int currentChoice) { + // Do the analysis to get Read and Write accesses to fields + ReadWriteSet rwSet = getReadWriteSet(currentChoice); + int objectId = ((JVMFieldInstruction) executedInsn).getFieldInfo().getClassInfo().getClassObjectRef(); + // Record the field in the map + if (executedInsn instanceof WriteInstruction) { + // Exclude certain field writes because of infrastructure needs, e.g., Event class field writes + for (String str : EXCLUDED_FIELDS_READ_WRITE_INSTRUCTIONS_STARTS_WITH_LIST) { + if (fieldClass.startsWith(str)) { + return; + } + } + rwSet.addWriteField(fieldClass, objectId); + } else if (executedInsn instanceof ReadInstruction) { + rwSet.addReadField(fieldClass, objectId); + } + } + + // Analyze Read accesses that are indirect (performed through iterators) + // These accesses are marked by certain bytecode instructions, e.g., INVOKEINTERFACE + private void analyzeReadWriteAccesses(Instruction instruction, ThreadInfo ti, int currentChoice) { + // Get method name + INVOKEINTERFACE insn = (INVOKEINTERFACE) instruction; + if (insn.toString().startsWith(GET_PROPERTY_METHOD) && + insn.getMethodInfo().getName().equals(DO_CALL_METHOD)) { + // Extract info from the stack frame + StackFrame frame = ti.getTopFrame(); + int[] frameSlots = frame.getSlots(); + // Get the Groovy callsite library at index 0 + ElementInfo eiCallsite = VM.getVM().getHeap().get(frameSlots[0]); + if (!eiCallsite.getClassInfo().getName().startsWith(GROOVY_CALLSITE_LIB)) { + return; + } + // Get the iterated object whose property is accessed + ElementInfo eiAccessObj = VM.getVM().getHeap().get(frameSlots[1]); + if (eiAccessObj == null) { + return; + } + // We exclude library classes (they start with java, org, etc.) and some more + String objClassName = eiAccessObj.getClassInfo().getName(); + if (excludeThisForItStartsWith(EXCLUDED_FIELDS_STARTS_WITH_LIST, objClassName) || + excludeThisForItStartsWith(EXCLUDED_FIELDS_READ_WRITE_INSTRUCTIONS_STARTS_WITH_LIST, objClassName)) { + return; + } + // Extract fields from this object and put them into the read write + int numOfFields = eiAccessObj.getNumberOfFields(); + for(int i=0; i currentCG = vm.getChoiceGenerator(); + // This is the main event CG + if (currentCG instanceof IntIntervalGenerator) { + // This is the interval CG used in device handlers + ChoiceGenerator parentCG = ((IntIntervalGenerator) currentCG).getPreviousChoiceGenerator(); + int actualEvtNum = ((IntChoiceFromSet) parentCG).getNextChoice(); + // Find the index of the event/choice in refChoices + for (int i = 0; i 0) { + // Check if we are reaching the end of our execution: no more backtracking points to explore + // cgMap, backtrackMap, backtrackStateQ are updated simultaneously (checking backtrackStateQ is enough) + if (!backtrackStateQ.isEmpty()) { + // Set done all the other backtrack points + for (BacktrackPoint backtrackPoint : backtrackPointList) { + backtrackPoint.getBacktrackCG().setDone(); + } + // Reset the next backtrack point with the latest state + int hiStateId = backtrackStateQ.peek(); + // Restore the state first if necessary + if (vm.getStateId() != hiStateId) { + RestorableVMState restorableState = restorableStateMap.get(hiStateId); + vm.restoreState(restorableState); + } + // Set the backtrack CG + IntChoiceFromSet backtrackCG = (IntChoiceFromSet) vm.getChoiceGenerator(); + setBacktrackCG(hiStateId, backtrackCG); + } else { + // Set done this last CG (we save a few rounds) + icsCG.setDone(); + } + // Save all the visited states when starting a new execution of trace + prevVisitedStates.addAll(currVisitedStates); + currVisitedStates.clear(); + // This marks a transitional period to the new CG + isEndOfExecution = true; + } + } + + private ReadWriteSet getReadWriteSet(int currentChoice) { + // Do the analysis to get Read and Write accesses to fields + ReadWriteSet rwSet; + // We already have an entry + if (readWriteFieldsMap.containsKey(currentChoice)) { + rwSet = readWriteFieldsMap.get(currentChoice); + } else { // We need to create a new entry + rwSet = new ReadWriteSet(); + readWriteFieldsMap.put(currentChoice, rwSet); + } + return rwSet; + } + + private boolean isConflictFound(Instruction nextInsn, int eventCounter, int currentChoice, String fieldClass) { + + int actualCurrCho = currentChoice % refChoices.length; + // Skip if this event does not have any Read/Write set or the two events are basically the same event (number) + if (!readWriteFieldsMap.containsKey(eventCounter) || + choices[actualCurrCho] == backtrackPointList.get(eventCounter).getChoice()) { + return false; + } + ReadWriteSet rwSet = readWriteFieldsMap.get(eventCounter); + int currObjId = ((JVMFieldInstruction) nextInsn).getFieldInfo().getClassInfo().getClassObjectRef(); + // Check for conflicts with Write fields for both Read and Write instructions + if (((nextInsn instanceof WriteInstruction || nextInsn instanceof ReadInstruction) && + rwSet.writeFieldExists(fieldClass) && rwSet.writeFieldObjectId(fieldClass) == currObjId) || + (nextInsn instanceof WriteInstruction && rwSet.readFieldExists(fieldClass) && + rwSet.readFieldObjectId(fieldClass) == currObjId)) { + return true; + } + return false; + } + + private boolean isFieldExcluded(String field) { + // Check against "starts-with", "ends-with", and "contains" list + if (excludeThisForItStartsWith(EXCLUDED_FIELDS_STARTS_WITH_LIST, field) || + excludeThisForItEndsWith(EXCLUDED_FIELDS_ENDS_WITH_LIST, field) || + excludeThisForItContains(EXCLUDED_FIELDS_CONTAINS_LIST, field)) { + return true; + } + + return false; + } + + private boolean isNewConflict(int currentEvent, int eventNumber) { + HashSet conflictSet; + if (!conflictPairMap.containsKey(currentEvent)) { + conflictSet = new HashSet<>(); + conflictPairMap.put(currentEvent, conflictSet); + } else { + conflictSet = conflictPairMap.get(currentEvent); + } + // If this conflict has been recorded before, we return false because + // we don't want to save this backtrack point twice + if (conflictSet.contains(eventNumber)) { + return false; + } + // If it hasn't been recorded, then do otherwise + conflictSet.add(eventNumber); + return true; + } + + private boolean isTraceConstructed(Integer[] choiceList, int stateId) { + // Concatenate state ID and trace in a string, e.g., "1:10234" + StringBuilder sb = new StringBuilder(); + sb.append(stateId); + sb.append(':'); + for(Integer choice : choiceList) { + sb.append(choice); + } + // Check if the trace has been constructed as a backtrack point for this state + if (doneBacktrackSet.contains(sb.toString())) { + return true; + } + doneBacktrackSet.add(sb.toString()); + return false; + } + + private void resetStatesForNewExecution(IntChoiceFromSet icsCG, VM vm) { + if (choices == null || choices != icsCG.getAllChoices()) { + // Reset state variables + choiceCounter = 0; + choices = icsCG.getAllChoices(); + refChoices = copyChoices(choices); + // Clearing data structures + conflictPairMap.clear(); + readWriteFieldsMap.clear(); + stateToEventMap.clear(); + isEndOfExecution = false; + backtrackPointList.clear(); + } + } + + private void setBacktrackCG(int stateId, IntChoiceFromSet backtrackCG) { + // Set a backtrack CG based on a state ID + LinkedList backtrackChoices = backtrackMap.get(stateId); + backtrackCG.setNewValues(backtrackChoices.removeLast()); // Get the last from the queue + backtrackCG.setStateId(stateId); + backtrackCG.reset(); + // Remove from the queue if we don't have more backtrack points for that state + if (backtrackChoices.isEmpty()) { + backtrackMap.remove(stateId); + backtrackStateQ.remove(stateId); + } + } + + // --- Functions related to the visible operation dependency graph implementation discussed in the SPIN paper + + // This method checks whether a choice is reachable in the VOD graph from a reference choice (BFS algorithm) + //private boolean isReachableInVODGraph(int checkedChoice, int referenceChoice) { + private boolean isReachableInVODGraph(int currentChoice) { + // Extract previous and current events + int choiceIndex = currentChoice % refChoices.length; + int prevChoIndex = (currentChoice - 1) % refChoices.length; + int currEvent = refChoices[choiceIndex]; + int prevEvent = refChoices[prevChoIndex]; + // Record visited choices as we search in the graph + HashSet visitedChoice = new HashSet<>(); + visitedChoice.add(prevEvent); + LinkedList nodesToVisit = new LinkedList<>(); + // If the state doesn't advance as the threads/sub-programs are executed (basically there is no new state), + // there is a chance that the graph doesn't have new nodes---thus this check will return a null. + if (vodGraphMap.containsKey(prevEvent)) { + nodesToVisit.addAll(vodGraphMap.get(prevEvent)); + while(!nodesToVisit.isEmpty()) { + int choice = nodesToVisit.getFirst(); + if (choice == currEvent) { + return true; + } + if (visitedChoice.contains(choice)) { // If there is a loop then we don't find it + return false; + } + // Continue searching + visitedChoice.add(choice); + HashSet choiceNextNodes = vodGraphMap.get(choice); + if (choiceNextNodes != null) { + // Add only if there is a mapping for next nodes + for (Integer nextNode : choiceNextNodes) { + // Skip cycles + if (nextNode == choice) { + continue; + } + nodesToVisit.addLast(nextNode); + } + } + } + } + return false; + } + + private void updateVODGraph(int currChoiceValue) { + // Update the graph when we have the current choice value + HashSet choiceSet; + if (vodGraphMap.containsKey(prevChoiceValue)) { + // If the key already exists, just retrieve it + choiceSet = vodGraphMap.get(prevChoiceValue); + } else { + // Create a new entry + choiceSet = new HashSet<>(); + vodGraphMap.put(prevChoiceValue, choiceSet); + } + choiceSet.add(currChoiceValue); + prevChoiceValue = currChoiceValue; + } }