<commit_before>'''
Three control flow types for running the simulation forward.
  - Replayer: takes as input a `superlog` with causal dependencies, and
    iteratively prunes until the MCS has been found
  - Fuzzer: injects input events at random intervals, periodically checking
    for invariant violations
  - Interactive: presents an interactive prompt for injecting events and
    checking for invariants at the users' discretion
'''

import pox.openflow.libopenflow_01 as of
from topology import BufferedPatchPanel
from traffic_generator import TrafficGenerator
from sts.util.console import msg
from sts.replay_event import *
from sts.event_dag import EventDag
from sts.syncproto.sts_syncer import STSSyncCallback
import sts.log_processing.superlog_parser as superlog_parser
from sts.syncproto.base import SyncTime
from pox.lib.revent import EventMixin, Event

import sys
import time
import random
import logging
from collections import Counter

log = logging.getLogger("control_flow")

class ControlFlow(object):
  ''' Superclass of ControlFlow types '''
  def __init__(self, sync_callback):
    self.sync_callback = sync_callback

  def simulate(self, simulation):
    ''' Move the simulation forward! Take the state of the system as a
    parameter'''
    pass

  def get_sync_callback(self):
    return self.sync_callback

class Replayer(ControlFlow):
  time_epsilon_microseconds = 500

  '''
  Replay events from a `superlog` with causal dependencies, pruning as we go
  '''
  def __init__(self, superlog_path_or_dag, ignore_unsupported_input_types=False,
               mark_invalid_input_sequences=False):
    ControlFlow.__init__(self, ReplaySyncCallback(self.get_interpolated_time))
    if type(superlog_path_or_dag) == str:
      superlog_path = superlog_path_or_dag
      # The dag is codefied as a list, where each element has
      # a list of its dependents
      self.dag = EventDag(superlog_parser.parse_path(superlog_path),
                          ignore_unsupported_input_types=ignore_unsupported_input_types,
                          mark_invalid_input_sequences=mark_invalid_input_sequences)
    else:
      self.dag = superlog_path_or_dag
    # compute interpolate to time to be just before first event
    self.compute_interpolated_time(self.dag.events[0])

  def get_interpolated_time(self):
    '''
    During divergence, the controller may ask for the current time more or
    less times than they did in the original run. We control the time, so we
    need to give them some answer. The answers we give them should be
    (i) monotonically increasing, and (ii) between the time of the last
    recorded ("landmark") event and the next landmark event, and (iii)
    as close to the recorded times as possible

    Our temporary solution is to always return the time right before the next
    landmark
    '''
    # TODO(cs): implement Andi's improved time heuristic
    return self.interpolated_time

  def compute_interpolated_time(self, current_event):
    next_time = current_event.time
    just_before_micro = next_time.microSeconds - self.time_epsilon_microseconds
    just_before_micro = max(0, just_before_micro)
    self.interpolated_time = SyncTime(next_time.seconds, just_before_micro)

  def increment_round(self):
    pass

  def simulate(self, simulation):
    self.simulation = simulation
    self.run_simulation_forward(self.dag)

  def run_simulation_forward(self, dag):
    # Note that bootstrap() flushes any state from previous runs
    self.simulation.bootstrap()
    for event_watcher in dag.event_watchers:
      self.compute_interpolated_time(event_watcher.event)
      event_watcher.run(self.simulation)
      self.increment_round()

class MCSFinder(Replayer):
  def __init__(self, superlog_path,
               invariant_check=InvariantChecker.check_correspondence):
    super(MCSFinder, self).__init__(superlog_path,
                                    ignore_unsupported_input_types=True,
                                    mark_invalid_input_sequences=True)
    self.invariant_check = invariant_check

  def simulate(self, simulation):
    # First, run through without pruning to verify that the violation exists
    Replayer.simulate(self, simulation)
    # Check invariants
    violations = self.invariant_check(simulation)
    if violations == []:
      log.warn("Unable to reproduce correctness violation!")
      sys.exit(5)

    # Now start pruning
    mcs = []
    # TODO(cs): perhaps we should implement the full-blown delta-debugging
    # algorithm? See http://www.st.cs.uni-saarland.de/papers/tse2002/tse2002.pdf,
    # Section 3.2
    # We could also be pretty smart about what we prune first, since we can
    # leverage domain knowledge

    # For now, just do a modified version of binary search:
    #  - split into 2
    #  - ignore left half.
    #  - If violation
    #      - prune entire left half, and recurse!
    #  - Else, at least one member of MCS was in left half
    #      - Prune right half. If violation, prune entire right half and
    #        recurse!
    #      - Else, elements of MCS on both right and left sides. Split
    #        entire input into 4 pieces and proceed with quadary search!

    # Principles here are:
    #  - If violation, prune everything that was ignored
    #  - If no violation, at least one member of the ignored portion was part
    #    of MCS. (If the ignored portion was a singleton, add it to MCS!)

    # If the MCS hasn't been found in the first N splits, this devolves into the
    # original MCS algorithm (prune one at a time). In the average case, this
    # should do better -- in the worst case, it will take N extra iterations,
    # for a total of 2N replays

    split_ways = 2
    while split_ways <= len(self.dag):
      ignored_portions = self.dag.split(split_ways)
      for ignored_portion in ignored_portions:
        # Note that ignore_portion() invokes peek()
        new_dag = self.dag.ignore_portion(ignored_portion, self.simulation)
        # Run the simulation forward
        self.run_simulation_forward(new_dag)
        # Check if there were violations
        violations = self.invariant_check(simulation)
        if violations == []:
          # No violation!
          # If singleton, this must be part of the MCS
          if len(ignored_portion) == 1:
            mcs.append(ignored_portion[0])
          split_ways *= 2
        else:
          # Violation in the non-pruned half.
          # Prune the ignored portion (including all of its dependents)
          self.dag.remove_events(ignored_portion, self.simulation)
          # Break out of `for ignore_portion`
          split_ways = 2
          break
      return mcs

class Fuzzer(ControlFlow):
  '''<commit_msg>FindMCS: adding logging, and fixing a recursion bug<commit_after>'''
Three control flow types for running the simulation forward.
  - Replayer: takes as input a `superlog` with causal dependencies, and
    iteratively prunes until the MCS has been found
  - Fuzzer: injects input events at random intervals, periodically checking
    for invariant violations
  - Interactive: presents an interactive prompt for injecting events and
    checking for invariants at the users' discretion
'''

import pox.openflow.libopenflow_01 as of
from topology import BufferedPatchPanel
from traffic_generator import TrafficGenerator
from sts.util.console import msg
from sts.replay_event import *
from sts.event_dag import EventDag
from sts.syncproto.sts_syncer import STSSyncCallback
import sts.log_processing.superlog_parser as superlog_parser
from sts.syncproto.base import SyncTime
from pox.lib.revent import EventMixin, Event

import sys
import time
import random
import logging
from collections import Counter

log = logging.getLogger("control_flow")

class ControlFlow(object):
  ''' Superclass of ControlFlow types '''
  def __init__(self, sync_callback):
    self.sync_callback = sync_callback

  def simulate(self, simulation):
    ''' Move the simulation forward! Take the state of the system as a
    parameter'''
    pass

  def get_sync_callback(self):
    return self.sync_callback

class Replayer(ControlFlow):
  time_epsilon_microseconds = 500

  '''
  Replay events from a `superlog` with causal dependencies, pruning as we go
  '''
  def __init__(self, superlog_path_or_dag, ignore_unsupported_input_types=False,
               mark_invalid_input_sequences=False):
    ControlFlow.__init__(self, ReplaySyncCallback(self.get_interpolated_time))
    if type(superlog_path_or_dag) == str:
      superlog_path = superlog_path_or_dag
      # The dag is codefied as a list, where each element has
      # a list of its dependents
      self.dag = EventDag(superlog_parser.parse_path(superlog_path),
                          ignore_unsupported_input_types=ignore_unsupported_input_types,
                          mark_invalid_input_sequences=mark_invalid_input_sequences)
    else:
      self.dag = superlog_path_or_dag
    # compute interpolate to time to be just before first event
    self.compute_interpolated_time(self.dag.events[0])

  def get_interpolated_time(self):
    '''
    During divergence, the controller may ask for the current time more or
    less times than they did in the original run. We control the time, so we
    need to give them some answer. The answers we give them should be
    (i) monotonically increasing, and (ii) between the time of the last
    recorded ("landmark") event and the next landmark event, and (iii)
    as close to the recorded times as possible

    Our temporary solution is to always return the time right before the next
    landmark
    '''
    # TODO(cs): implement Andi's improved time heuristic
    return self.interpolated_time

  def compute_interpolated_time(self, current_event):
    next_time = current_event.time
    just_before_micro = next_time.microSeconds - self.time_epsilon_microseconds
    just_before_micro = max(0, just_before_micro)
    self.interpolated_time = SyncTime(next_time.seconds, just_before_micro)

  def increment_round(self):
    pass

  def simulate(self, simulation):
    self.simulation = simulation
    self.run_simulation_forward(self.dag)

  def run_simulation_forward(self, dag):
    # Note that bootstrap() flushes any state from previous runs
    self.simulation.bootstrap()
    for event_watcher in dag.event_watchers:
      self.compute_interpolated_time(event_watcher.event)
      event_watcher.run(self.simulation)
      self.increment_round()

class MCSFinder(Replayer):
  def __init__(self, superlog_path,
               invariant_check=InvariantChecker.check_correspondence):
    super(MCSFinder, self).__init__(superlog_path,
                                    ignore_unsupported_input_types=True,
                                    mark_invalid_input_sequences=True)
    self.invariant_check = invariant_check
    self.log = logging.getLogger("mcs_finder")

  def simulate(self, simulation):
    # First, run through without pruning to verify that the violation exists
    Replayer.simulate(self, simulation)
    # Check invariants
    violations = self.invariant_check(simulation)
    if violations == []:
      self.log.warn("Unable to reproduce correctness violation!")
      sys.exit(5)

    # Now start pruning
    mcs = []
    # TODO(cs): perhaps we should implement the full-blown delta-debugging
    # algorithm? See http://www.st.cs.uni-saarland.de/papers/tse2002/tse2002.pdf,
    # Section 3.2
    # We could also be pretty smart about what we prune first, since we can
    # leverage domain knowledge

    # For now, just do a modified version of binary search:
    #  - split into 2
    #  - ignore left half.
    #  - If violation
    #      - prune entire left half, and recurse!
    #  - Else, at least one member of MCS was in left half
    #      - Prune right half. If violation, prune entire right half and
    #        recurse!
    #      - Else, elements of MCS on both right and left sides. Split
    #        entire input into 4 pieces and proceed with quadary search!

    # Principles here are:
    #  - If violation, prune everything that was ignored
    #  - If no violation, at least one member of the ignored portion was part
    #    of MCS. (If the ignored portion was a singleton, add it to MCS!)

    # If the MCS hasn't been found in the first N splits, this devolves into the
    # original MCS algorithm (prune one at a time). In the average case, this
    # should do better -- in the worst case, it will take N extra iterations,
    # for a total of 2N replays

    split_ways = 2
    while split_ways <= len(self.dag):
      self.log.info("Splitting in %d" % split_ways)
      ignored_portions = self.dag.split(split_ways)
      for i, ignored_portion in enumerate(ignored_portions):
        # Note that ignore_portion() invokes peek()
        new_dag = self.dag.ignore_portion(ignored_portion, self.simulation)
        # Run the simulation forward
        self.run_simulation_forward(new_dag)
        # Check if there were violations
        violations = self.invariant_check(simulation)
        if violations == []:
          # No violation!
          # If singleton, this must be part of the MCS
          self.log.info("No violation..")
          if len(ignored_portion) == 1:
            self.log.info("Pruning singleton %s" % str(ignored_portion[0]))
            mcs.append(ignored_portion[0])
        else:
          # Violation in the non-pruned half.
          # Prune the ignored portion (including all of its dependents)
          self.log.info("Violation! Pruning %d'th portion" % i)
          self.dag.remove_events(ignored_portion, self.simulation)
          # Break out of `for ignore_portion`
          split_ways = 2
          break
      split_ways *= 2
    return mcs

class Fuzzer(ControlFlow):
  '''
{'fraction_non_alphanumeric': 0.06690345027544216, 'fraction_numerical': 0.003841693244418672, 'mean_word_length': 3.164503471174162, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2535310', 'n_tokens_mistral': 4026, 'n_tokens_neox': 3830, 'n_words': 1311}