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

class Array
	# Confirm that this array has no duplicate elements
	def is_uniq?
		self == self.uniq
	end
end

class Symbol
	def <=>(other)
		self.to_s <=> other.to_s
	end
end

module UpState

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

# Occurs when something tries to bring up a state without filling
# out its parameters
class AmbiguousRequest < StandardError; end

ENABLE_TRACE = false

=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 :deps   # What are our dependencies?
	attr :holds  # Holds that are had on this state
	attr :status # Are we up? Down? Getting there?
	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?
		attr :hold_provides # What params should come from this state's holder?
	protected
		attr_writer :depends
		attr_writer :caused_by
		attr_writer :rising_edge
		attr_writer :falling_edge
		attr_writer :hold_provides
	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 DSTuple objects
	def initialize(deps)
		raise NoMethodError if self.class == State

		@holds = Set.new
		@deps = deps.to_set
		@status = :down
		@hold_params = {}

		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 react_to?(event)
		return false if @status != :down
		self.class.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
		return if @status == :dropping
		@deps.each do |dep|
			dep = dep.state
			next if dep.status != :down
			unless @status == :down
				raise ConsistencyFault, "Lost dep on #{dep} without notify for #{self}"
			end
			@@states.delete self
			self.freeze
			return
		end
	end

	# Puts the class name and parameters
	def to_s
		"#{name} (#{@status.to_s})"
	end

	# The name of this state
	def name
		"#{self.class.name.split("::").last}#{params.inspect}"
	end

	# Prints a string that uses TTY color escapes
	def to_s_color
		colors = {
			:up => "1;32",
			:down => "1;31",
			:rising => "0;32",
			:dropping => "0;31",
		}

		"\e[%sm%s\e[0;49m" % [colors[status], name]
	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, params = {})
		hold = Hold::Dep.new(hold) if hold.is_a? State
		hold = Hold::User.new(params) if hold == :user
		hold = Hold::System.new(params) if hold == :system
		raise TypeError, "Invalid hold specifier" unless hold.is_a? Hold
		if @status == :down and self.class.hold_provides.size > 0
			return self.fork(hold)
		end
		@holds.add hold
		rise if @status == :down
		self
	end

	# Duplicate this class and bring the duplicate up with the given hold attached
	def fork(hold)
		raise Consistency Fault, "Fork of live state" unless @status == :down
		new_one = self.clone
		new_one.instance_eval do
			@holds = Set.new [hold]
			@hold_params = {}
			self.class.hold_provides.each do |x|
				if x.is_a? Array
					worked = false
					x.each do |y|
						hold.params[y] or next
						@hold_params[y] = hold.params[y]
						worked = true
					end
					worked or raise AmbiguousRequest, "None of #{x.join(', ')} defined"
					next
				end

				hold.params[x] or raise AmbiguousRequest, "#{x} undefined"
				@hold_params[x] = hold.params[x]
			end
		end
		@@states.each do |state|
			next unless state == new_one
			state.hold(hold)
			return state
		end
		@@states.add new_one
		new_one.send :rise
		new_one
	end

	# Release a hold on this state. Arguments are the same as for +hold+.
	def release(hold, params = {})
		return if @holds.size == 0
		hold = Hold::Dep.new(hold) if hold.is_a? State
		hold = Hold::User.new(params) if hold == :user
		hold = Hold::System.new(params) if hold == :system
		raise TypeError, "Invalid hold specifier" unless hold.is_a? Hold
		@holds.reject!{ |x| hold == x }
		drop if @holds.size == 0
		self
	end

	# Set this state to untrue
	def drop
		becomes_defunct(true)
	end

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

	# Set this state to untrue without running any falling edge code
	def becomes_defunct(drop=false)
		return unless @status == :up
		@status = :dropping
		@holds.each{ |x| x.clear }
		@holds = Set.new
		self.class.falling_edge.call(params) if drop
		@deps.each{ |x| x.state.release(self) }
		@hold_params = {}
		@status = :down
		State.gc
		State.depsolve_all
	end

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

	# eql? is the same as ==
	alias :eql? :==

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

	# Our ID is a function of our class and deps
	def hash
		(self.class.name.hash ** 3 +
		 self.params.sort.hash ** 2 +
		 @deps.map{ |x| x.state.hash }.sort.hash) % 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.state.rooted_in set } and \
		self.class.depends.map{ |x| set.select{ |y| x === y } } \
			.inject([]){ |x, y| x+y }.to_set.subset? @deps.map{ |x| x.state }.to_set
	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 Dependency
	# Objects. This method is not defined in subclasses of State.
	def State.new_type(name, caused_by, depends, hold_provides = [])
		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.hold_provides = hold_provides
		newtype.instance_eval do
			undef :new_type, :process_event, :gc, :depsolve_all
			def name
				@name
			end
		end
		newtype.instance_variable_set(:@name, name)
		@@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, "Argument must be an Event" unless event.is_a? Event
		count = 0
		@@states.select{ |x| x.status == :down }.each do |x|
			next unless x.react_to? event
			x.hold(:system, event.params)
			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 = @@states.to_a.to_set # Mutability + identity = pain. Semper λ
		@@states.each{ |x| x.check_deps }
		nil
	end

	# Print color string reps of all states
	def State.print_all_color
		@@states.each do |s|
			puts s.to_s_color if s.is_a? self
		end
	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.status == :up }
		candidates = @depends.map do |d|
			active_states.map{ |s| DSTuple.new(d, s) }.select{ |x| x.valid? }
		end

		return nil if candidates.include? []

		unless candidates == []
			candidates = candidates[0].product(*candidates[1..-1]).map{ |x| x.to_set } \
				.select{ |x| x.size == 0 or x.inject(true){ |st, y| st and y.rooted_in x } }
		else
			candidates = [Set.new]
		end

		candidates.each{ |x| self.new x }
		nil
	end

	# Get all states of this type
	def State.get_all
		@@states.select{ |x| x.is_a? self }
	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

	# Hold all states of a class
	def State.hold(type, params = {})
		@@states.select{ |x| x.is_a? self }.map{ |x| x.hold(type, params) }
	end

	# Release all states of a class
	def State.release(type, params = {})
		@@states.select{ |x| x.is_a? self }.map{ |x| x.release(type, params) }
	end

private
	# Set this state to true
	def rise
		return if @status == :up
		@status = :rising
		@deps.each{ |x| x.state.hold(self) }
		self.class.rising_edge.call(params)
		@status = :up
		State.depsolve_all
	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, "Parameters must be a hash" 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

	# eql? is the same as ==
	def eql?(other); self == other; end

	# The default to_s just prints the type of hold
	def to_s
		self.class.name
	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, "Dependent must be a State" unless dependent.is_a? State
			@dependent = dependent
		end

		def params; @dependent.params; end #:nodoc:

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

		# Prints the state who has this hold
		def to_s
			"hold by #{@dependent}"
		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 Dependency is a notion of a state which might satisfy the needs of another
state. 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 Dependency
	attr :params     # What parameters do we expect?
	attr :stateclass # What class of state do we match?
	attr :remap      # Parameters our dependent wants to get under another name.

	# A dependency 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 = {}, remap = {})
		raise TypeError, "Class must be a State Class" unless State > stateclass
		raise TypeError, "Params must be a hash" unless params.is_a? Hash
		@stateclass = stateclass
		@params = params
		@remap = remap
	end

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

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

	# Determines if a state meets this dependency
	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
end

=begin rdoc
A DSTuple is a pairing of a Dependency and a State that meets it.
=end
class DSTuple
	attr :dep   # What dependency do we resolve?
	attr :state # How do we resolve it?

	# DSTuples are born of a Dependency, and a State which satisfies it
	def initialize(dep, state)
		@dep = dep
		@state = state
	end

	# Is our state rooted in the given set of DSTuples?
	def rooted_in(set)
		@state.rooted_in set.map{ |x| x.state }
	end

	# Does this DSTuple represent a sane resolution?
	def valid?
		@dep === @state
	end

	# What parameters does this tuple provide to its parent?
	def params
		result = {}
		input = @state.params
		@dep.params.each_key{ |x| result[(@dep.remap[x] or x)] = input[x] }
		result
	end
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.sort.hash == other.params.sort.hash 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