diff options
Diffstat (limited to 'legacy/state.rb')
| -rw-r--r-- | legacy/state.rb | 534 |
1 files changed, 534 insertions, 0 deletions
diff --git a/legacy/state.rb b/legacy/state.rb new file mode 100644 index 0000000..02c1bf3 --- /dev/null +++ b/legacy/state.rb @@ -0,0 +1,534 @@ +=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 ConsistencyFault, "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 + puts @@states.select{ |s| s.is_a? self }.map{ |s| s.to_s_color }.join(", ") + 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 } } \ + .select{ |x| x.map{ |y| y.params.to_a }.inject([]){ |a, b| a + b }.uniq.map{ |y| y[0] }.is_uniq? } + 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 |