class StateMachineChecker::FiniteStateMachine

Represents a finite state machine: a set of states, an initial state, and transitions among them.

This class is used to limit the dependency on any particular state machine library.

Attributes

initial_state[R]
transitions[R]

Public Class Methods

new(initial_state, transitions) click to toggle source

@param [Symbol] initial_state the name of the initial state. @param [Array<Transition>] transitions the transitions of the FSM.

# File lib/state_machine_checker/finite_state_machine.rb, line 12
def initialize(initial_state, transitions)
  @initial_state = initial_state
  @transitions = transitions
end

Public Instance Methods

state_paths() click to toggle source

Enumerate the states and for each provide a path to it.

@return [Enumerator<Array(Symbol, Array<Transition>)>] an enumerator where

each element is a pair of a state and an array of transitions to reach the
state.
# File lib/state_machine_checker/finite_state_machine.rb, line 22
def state_paths
  Enumerator.new do |yielder|
    depth_first_search(Set.new, initial_state, [], yielder)
  end
end
states() click to toggle source

Enumerate the states.

@return [Enumerator<Symbol>] an enumerator over the names of the states.

# File lib/state_machine_checker/finite_state_machine.rb, line 31
def states
  seen = Set.new

  Enumerator.new do |yielder|
    seen << initial_state
    yielder << initial_state

    transitions.each do |transition|
      unless seen.include?(transition.from)
        seen << transition.from
        yielder << transition.from
      end

      unless seen.include?(transition.to)
        seen << transition.to
        yielder << transition.to
      end
    end
  end
end
transitions_from(state) click to toggle source
# File lib/state_machine_checker/finite_state_machine.rb, line 64
def transitions_from(state)
  transitions.select { |t| t.from == state }
end
transitions_to(state) click to toggle source
# File lib/state_machine_checker/finite_state_machine.rb, line 68
def transitions_to(state)
  transitions.select { |t| t.to == state }
end
traverse(from_state, reverse: false, &block) click to toggle source

Traverse the graph from the given state. Yield each state and the transitions from it to the from_state. If the result of the block is falsey for any state then the search will not continue to the children of that state.

@param [Symbol] from_state @param [true, false] reverse traverse in reverse? @yield [Symbol, Array<Symbol>]

# File lib/state_machine_checker/finite_state_machine.rb, line 60
def traverse(from_state, reverse: false, &block)
  rec_traverse(from_state, [], Set[from_state], reverse, &block)
end

Private Instance Methods

rec_traverse(state, stack, seen, reverse, &block) click to toggle source

Traverse the graph, maintaining a stack of transitions.

# File lib/state_machine_checker/finite_state_machine.rb, line 75
def rec_traverse(state, stack, seen, reverse, &block)
  # If we are reverse searching than the stack will be in reverse order.
  path = reverse ? stack.reverse : stack.clone
  continue = block.yield(state, path.map(&:name)) != false

  if continue
    trans = if reverse
      transitions_to(state)
    else
      transitions_from(state)
    end

    trans.each do |transition|
      next_state = if reverse
        transition.from
      else
        transition.to
      end

      unless seen.include?(next_state)
        seen.add(next_state)
        stack.push(transition)

        rec_traverse(next_state, stack, seen, reverse, &block)

        stack.pop
      end
    end
  end
end