path: root/state.rb

=begin rdoc
UpState - An Upstart state machine prototype

Author: Casey Dahlin <cjdahlin@ncsu.edu>
=end
require 'set'

unless Array.instance_methods.include? "product"
	class Array #:nodoc:
		def product(*others)
			return self.map{ |x| [x] } if others.size == 0
			self.map do |x|
				(others[0].product(*others[1..-1])).map{ |y| [x] + y }
			end.inject([]){ |x,y| x+y }
		end
	end
end

module UpState

# Occurs when the state machine becomes inconsistent
class ConsistencyFault < StandardError; end

=begin rdoc
An instance of State exists whenever a state can become true without having to
toggle any other states, or whenever a state _is_ true.
=end
class State
	attr :holds  # Holds that are had on this state
	attr :active # Are we active?
	class << self
		attr :depends			 # What states does this state depend on?
		attr :caused_by		 # What events can cause this state?
		attr :rising_edge	 # What do we do as we're coming up?
		attr :falling_edge # What do we do as we're going down?
	protected
		attr_writer :depends
		attr_writer :caused_by
		attr_writer :rising_edge
		attr_writer :falling_edge
	end

	@@states = Set.new      # Set of activatable states
	@@state_types = Set.new # Set of state types

	# Create a new state. +deps+ is a list of State objects, not patterns
	def initialize(deps)
		raise NoMethodError if self.class == State

		@holds = Set.new
		@deps = deps.to_set
		@active = false

		return if @@states.include? self
		@@states.add self
		hold(:system) if self.class.caused_by.include? Event::Epsilon
	end

	# Returns true if this state should be raised if +event+ is occuring
	def respond_to?(event)
		return false if @active
		@caused_by.each do |x|
			return true if x === event
		end
		return false
	end

	# Make sure our deps are satisfied, and remove ourselves from the list of
	# states if they aren't
	def check_deps
		@deps.each do |dep|
			next if dep.active
			raise ConsistencyFault if self.active
			@@states.delete self
			self.methods.each{ |x| undef x }
			self.freeze
		end
	end

	# Hold this state. Holding a state informs the system that you would like it
	# to come up or remain up. +hold+ can be an object of type Hold, an object of
	# type State to establish that said state depends on this one, or one of
	# <tt>:user</tt> or <tt>:system</tt> to establish that the user or system
	# has an interest in keeping this service running
	def hold(hold)
		hold = Hold::Dep.new(hold) if hold.is_a? State
		hold = Hold::User.new if hold == :user
		hold = Hold::System.new if hold == :system
		raise TypeError unless hold.is_a? Hold
		@holds.add hold
		rise if @holds.size == 1
	end

	# Release a hold on this state. Arguments are the same as for +hold+.
	def release(hold)
		hold = Hold::Dep.new(hold) if hold.is_a? State
		hold = Hold::User.new if hold == :user
		hold = Hold::System.new if hold == :system
		raise TypeError unless hold.is_a? Hold
		@holds.remove hold
		drop if @holds.size == 0
	end

	# Set this state to untrue
	def drop
		return unless @active
		break_holds if @holds.size > 0
		self.class.falling_edge.call(params)
		becomes_defunct
	end

	# Parameters to this state
	def params
		@deps.map{ |x| x.params }.inject{ |x,y| x.merge y }.merge \
			@holds.map{ |x| x.params }.inject{ |x,y| x.merge y }
	end

	# Set this state to untrue without running any falling edge code
	def becomes_defunct
		return unless @active
		break_holds if @holds.size > 0
		@active = false
		self.class.depends.each{ |x| x.remove_hold(x) }
		State.gc
		State.depsolve_all
	end

	# Determine if two State objects are equivalent
	def ==(other)
		self.hash == other.hash
	end

	# Match this State object to patterns or other State objects
	def ===(other)
		return other === self if other.is_a? StatePattern
		return self == other
	end

	# Our ID is a function of our class and deps
	def hash
		@deps.inject(self.class.hash){ |x,y| (x ** 2 + y.object_id) % 0x4000000000000000 }
	end

	# A state is rooted in a set of states if any state in the set which it _may_
	# depend on, it _does_ depend on, and if all of its depended states are rooted
	# in the set.
	def rooted_in(set)
		@deps.inject(true){ |x,y| x and y.rooted_in set } and \
		self.class.depends.map{ |x| set.select{ |y| x === y } } \
			.inject{ |x, y| x+y }.to_set.subset? @deps
	end

	# Create a new type of state. +name+ is capitalized and postfixed with "State"
	# to create the new state class name. +depends+ is a series of StatePattern
	# Objects. This method is not defined in subclasses of State.
	def State.new_type(name, caused_by, depends)
		name = name.capitalize + "State"
		raise NameError, "State already exists" if self.const_defined? name
		newtype = const_set(name, Class.new(State))
		newtype.depends = depends
		newtype.caused_by = caused_by
		newtype.rising_edge = Proc.new{}
		newtype.falling_edge = Proc.new{}
		newtype.instance_eval do
			undef :new_type, :process_event, :gc, :depsolve_all
		end
		@@state_types.add newtype
		newtype.depsolve
		newtype
	end

	# Handle the occurance of an event. This method is not defined in subclasses
	# of State.
	def State.process_event(event)
		raise TypeError unless event.is_a? Event
		count = 0
		@@states.select{ |x| x.active }.each do 
			next unless x.respond_to? event
			x.hold(:system)
			count += 1
		end
		count
	end

	# Remove inactive states whose deps are no longer satisfied. This method is
	# not defined in subclasses of State.
	def State.gc
		@@states.each{ |x| x.check_deps }
		nil
	end

	# Look at the list of active states and see how the deps of this state could
	# be met
	def State.depsolve
		active_states = @@states.select{ |x| x.active }
		candidates = @depends.map{ |d| active_states.select{ |s| d.match s } }
		return nil if candidates.include? []
		candidates[0].product(*candidates[1..-1]).map{ |x| x.to_set } \
			.select{ |x| x.inject(true){ |st, y| st and y.rooted_in x } } \
			.reject do |dset|
				active_states.select{ |x| x.is_a? self and x.deps == dset }.size > 0
			end.each{ |x| self.new x }
	end

	# Depsolve all state classes. This method is not defined in subclasses of
	# State.
	def State.depsolve_all
		@@state_types.each{ |x| x.depsolve }
		nil
	end

private
	# Set this state to true
	def rise
		return if @active
		self.class.depends.each{ |x| x.hold(self) }
		self.class.rising_edge.call(params)
		@active = true
		State.depsolve_all
	end

	# Inform other states that they may no longer depend on this one
	def break_holds
		@holds.each{ |x| x.clear }
		@holds = Set.new
	end
end

=begin rdoc
A Hold is placed on a State when something has an interest in that State being
up. States drop automatically when they cease to have any holds on them.
=end
class Hold
	attr :params # Parameters of this hold

	# +params+ should be a hash of parameters.
	def initialize(params)
		raise NoMethodError if self.class == Hold
		raise TypeError unless params.is_a? Hash
		@params = params
	end

	# Inform interested parties that this hold can no longer be maintained, and
	# that the held state is going to drop.
	def clear; end

	# The non-dep holds have no interesting attributes and may be compared
	# solely by type
	def ==(other) #:nodoc:
		self.class == other.class
	end

	# A hold placed when the system has an interest in something being running
	class System < Hold; end
	# A hold placed when the user has asked for something to be running
	class User < Hold; end

	# A hold place when a state is depended on by another state.
	class Dep < Hold
		# +dependent+ must be an object of type State
		def initialize(dependent)
			raise TypeError unless dependent.is_a? State
			@dependent = dependent
		end

		def params; {}; end #:nodoc:

		# Kill the dependent state so that the depended state can drop
		def clear
			@dependent.drop
		end

		# Two Dep holds are equal if they have the same dependent
		def ==(other)
			return other == @dependent if other.is_a? State
			return other.dependent == @dependent if other.is_a? Dep
			return false
		end

	protected
		attr :dependent # State which depends on what we hold
	end
end

=begin rdoc
A StatePattern is a notion of a state which might exist. It will contain the
type of the state and perhaps some sort of patterns which certain parameters
must conform to, but it does not necessarily contain enough info to define a
state in its entirety.
=end
class StatePattern
	# A state pattern is created from a class of state to match, and a hash of
	# parameters. The parameters in the hash can be string values to match or
	# Regex objects
	def initialize(stateclass, params = {})
		raise TypeError unless State < stateclass
		raise TypeError unless params.is_a? Hash
		@stateclass = stateclass
		@params = params
	end

	# Two state patterns are equal if any given set would be either matched
	# by both or rejected by both
	def ==(other)
		return false unless other.is_a? StatePattern
		return(other.stateclass == @stateclass and other.params == params)
	end

	# Tests for equality between state patterns or matching between a state
	# pattern and a state
	def ===(other)
		return(self.match(other) or self == other)
	end

	# Determines if a state matches this pattern
	def match(other)
		return false unless other.is_a? @stateclass
		return false if (@params.keys - other.params.keys).size > 0
		@params.each do |x,y|
			return false unless y === other.params[x]
		end
		return true
	end

protected
	attr :stateclass # What class of state do we match?
	attr :params     # What parameters do we expect?
end

=begin rdoc
An event indicates something happening to the system that may cause a state
change
=end
class Event
	attr :name   # What happened?
	attr :params # Where/when/why/how/to what did it happen?

	# Params should be a series of specific properties of this event in hash form
	def initialize(name, params = {})
		@name = name
		@params = params
	end

	# Epsilon is defined as "An event which occurs whenever its occuring would
	# cause change in the system"
	Epsilon = self.new("ε")

	# Two Events are equal if their params are equal and their name is the same
	def ==(other)
		other.is_a? Event and \
			@params == other.params and \
			@name == other.name
	end

	# Two Events match if any common params match and their name is the same
	def ===(other)
		return false unless other.is_a? Event and @name == other.name
		@params.each do |x, y|
			return false unless y === other.params[x]
		end
		return true
	end
end

end # module UpState