From 24781fbc3ad4640b360e92561948f412fbb7ef3e Mon Sep 17 00:00:00 2001 From: Casey Dahlin Date: Sun, 21 Dec 2008 20:14:52 -0500 Subject: Beginnings of python rewrite --- .gitignore | 1 + example.rb | 19 -- legacy/example.rb | 19 ++ legacy/state.rb | 534 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ legacy/test.rb | 129 +++++++++++++ legacy/test2.rb | 93 ++++++++++ state.py | 154 ++++++++++++++++ state.rb | 534 ------------------------------------------------------ test.rb | 129 ------------- test2.rb | 93 ---------- 10 files changed, 930 insertions(+), 775 deletions(-) delete mode 100644 example.rb create mode 100644 legacy/example.rb create mode 100644 legacy/state.rb create mode 100644 legacy/test.rb create mode 100644 legacy/test2.rb create mode 100644 state.py delete mode 100644 state.rb delete mode 100644 test.rb delete mode 100644 test2.rb diff --git a/.gitignore b/.gitignore index d926099..64ae595 100644 --- a/.gitignore +++ b/.gitignore @@ -1,2 +1,3 @@ .*.swp +*.pyc coverage/ diff --git a/example.rb b/example.rb deleted file mode 100644 index 182ae1d..0000000 --- a/example.rb +++ /dev/null @@ -1,19 +0,0 @@ -require 'state' - -include UpState - -HdAvail = State.new_type("hdAvail", [Event.new("DevKit_FoundHD")], [], [:uid, :name, :blkdev]) -FstabAvail = State.new_type("fstabLine", [Event.new("Can_Mount", {:mount_str => /.*/})], [], [[:uid, :name, :blkdev], :mount_str]) -Mount = State.new_type("mount", [Event::Epsilon], [Dependency.new(HdAvail, {:uid => /.*/}), Dependency.new(FstabAvail, {:mount_str => /.*/})]) - -events = [ - ["DevKit_FoundHD", {:uid => "1234", :name => "myhd", :blkdev => "/dev/sda1"}], - ["Can_Mount", {:uid => "1234", :mount_str => "/home"}], - ["Can_Mount", {:uid => "1234"}], -] - -State.print_all_color -events.each do |x| - State.process_event Event.new(*x) - State.print_all_color -end diff --git a/legacy/example.rb b/legacy/example.rb new file mode 100644 index 0000000..182ae1d --- /dev/null +++ b/legacy/example.rb @@ -0,0 +1,19 @@ +require 'state' + +include UpState + +HdAvail = State.new_type("hdAvail", [Event.new("DevKit_FoundHD")], [], [:uid, :name, :blkdev]) +FstabAvail = State.new_type("fstabLine", [Event.new("Can_Mount", {:mount_str => /.*/})], [], [[:uid, :name, :blkdev], :mount_str]) +Mount = State.new_type("mount", [Event::Epsilon], [Dependency.new(HdAvail, {:uid => /.*/}), Dependency.new(FstabAvail, {:mount_str => /.*/})]) + +events = [ + ["DevKit_FoundHD", {:uid => "1234", :name => "myhd", :blkdev => "/dev/sda1"}], + ["Can_Mount", {:uid => "1234", :mount_str => "/home"}], + ["Can_Mount", {:uid => "1234"}], +] + +State.print_all_color +events.each do |x| + State.process_event Event.new(*x) + State.print_all_color +end 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 +=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 + # :user or :system 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 diff --git a/legacy/test.rb b/legacy/test.rb new file mode 100644 index 0000000..87cb5bf --- /dev/null +++ b/legacy/test.rb @@ -0,0 +1,129 @@ +require 'state' +require 'set' +require 'test/unit' + + +def put_states + foo = State.send(:class_variable_get, :@@states).map{ |x| x.to_s_color } + puts foo.sort.join(", ") +end + +class TC_State < Test::Unit::TestCase + include UpState + + Foo = State.new_type("foo", [Event.new("gimmefoo", {:bob => /^...$/})], [], [:bob]) + Bar = State.new_type("bar", [], [Dependency.new(Foo)]) + Baz = State.new_type("baz", [], [Dependency.new(Foo, {:bob => "abc"}, {:bob => :tom}), Dependency.new(Bar)]) + Bam = State.new_type("bam", [Event::Epsilon], [Dependency.new(Baz)]) + Bang = State.new_type("bang", [], [Dependency.new(Bam)]) + + def assert_have_states(*s) + assert_equal(s.sort, State.get_all.map{ |x| x.to_s }.sort) + end + + def assert_only_states(*s) + assert_have_states *s + assert_equal(State.get_all.size, s.size) + end + + def setup + assert_only_states "FooState{} (down)" + end + + def teardown + State.release(:user) + State.release(:system) + end + + def test_ignored_event + State.process_event(Event.new("gimmefoo", {:bob => "1234"})) + assert_only_states "FooState{} (down)" + end + + def test_responded_event + State.process_event(Event.new("gimmefoo", {:bob => "123"})) + assert_only_states('FooState{} (down)', 'FooState{:bob=>"123"} (up)', "BarState{} (down)") + end + + def test_hold_with_dependent + test_responded_event + Bar.get_all.first.hold(:user) + assert_only_states('FooState{} (down)', 'FooState{:bob=>"123"} (up)', "BarState{} (up)") + end + + def test_hold_non_existant_state + Bar.hold(:user) + assert_only_states "FooState{} (down)" + end + + def test_pattern_matched_param_dep + State.process_event(Event.new("gimmefoo", {:bob => "abc"})) + Bar.hold(:user) + assert_only_states( + 'BazState{:tom=>"abc"} (down)', + 'FooState{} (down)', + 'FooState{:bob=>"abc"} (up)', + "BarState{} (up)" + ) + end + + def test_duplicitous_state_by_deps + test_pattern_matched_param_dep + State.process_event(Event.new("gimmefoo", {:bob => "123"})) + assert_only_states( + 'BazState{:tom=>"abc"} (down)', + 'FooState{} (down)', + 'FooState{:bob=>"abc"} (up)', + 'FooState{:bob=>"123"} (up)', + "BarState{} (up)", + "BarState{} (down)" + ) + end + + def test_identity_uniqueness + test_pattern_matched_param_dep + State.process_event(Event.new("gimmefoo", {:bob => "abc"})) + assert_only_states( + 'BazState{:tom=>"abc"} (down)', + 'FooState{} (down)', + 'FooState{:bob=>"abc"} (up)', + "BarState{} (up)" + ) + end + + def test_epsilon + test_pattern_matched_param_dep + Baz.hold(:user) + assert_only_states( + 'BazState{:tom=>"abc"} (up)', + 'FooState{} (down)', + 'FooState{:bob=>"abc"} (up)', + "BarState{} (up)", + "BamState{} (up)", + "BangState{} (down)" + ) + end + + def test_release_noop + test_epsilon + Bar.release(:user) + assert_only_states( + 'BazState{:tom=>"abc"} (up)', + 'FooState{} (down)', + 'FooState{:bob=>"abc"} (up)', + "BarState{} (up)", + "BamState{} (up)", + "BangState{} (down)" + ) + end + + def test_drop_cleanup + test_release_noop + Bar.get_all.each{ |x| x.drop } + assert_only_states( + 'FooState{} (down)', + 'FooState{:bob=>"abc"} (up)', + "BarState{} (down)" + ) + end +end diff --git a/legacy/test2.rb b/legacy/test2.rb new file mode 100644 index 0000000..0a43d58 --- /dev/null +++ b/legacy/test2.rb @@ -0,0 +1,93 @@ +require 'state' +require 'set' +require 'test/unit' + +class TC_State < Test::Unit::TestCase + include UpState + + Tony = State.new_type("tony", [Event.new("tonyup", {:tony => "tony"})], [], [:tony]) + Mike = State.new_type("mike", [], [Dependency.new(Tony)]) + ChainTop = State.new_type("chaintop", [], [Dependency.new(Tony, {:tony => "tony"}, {:tony => :bob}), + Dependency.new(Mike)]) + #this state should never appear + Reversed = State.new_type("reversed", [Dependency.new(Tony)], [Event.new("tonyup", {:tony => "tony"})]) + + def put_states + foo = State.send(:class_variable_get, :@@states).map{ |x| x.to_s_color } + puts foo.sort.join(", ") + end + + def assert_have_states(*s) + assert_equal(s.sort, State.get_all.map{ |x| x.to_s }.sort) + end + + def assert_only_states(*s) + assert_have_states *s + assert_equal(State.get_all.size, s.size) + end + + def setup + assert_only_states( + 'TonyState{} (down)' + ) + end + + def teardown + State.release(:user) + State.release(:system) + end + + def test_reversed + #this should never ever come up + Reversed.hold(:user) + assert_only_states( + 'TonyState{} (down)' + ) + end + + def test_incomplete_hold + begin + Tony.hold(:user) + assert(false) + end + rescue AmbiguousRequest => e + assert(true) + end + + def test_bogus_hold + begin + Tony.hold(:cookies) + assert(false) + end + rescue TypeError => e + assert(true) + end + + def test_bogus_release + begin + State.process_event(Event.new("tonyup", {:tony => "tony"})) + Tony.release(:cookies) + assert(false) + end + rescue TypeError => e + assert(true) + end + + def test_chained_dependencies + State.process_event(Event.new("tonyup", {:tony => "tony"})) + Mike.hold(:user) + ChainTop.hold(:system, {:bob => "tony"}) + assert_only_states( + 'TonyState{} (down)', + 'ChaintopState{:bob=>"tony"} (up)', + 'MikeState{} (up)', + 'TonyState{:tony=>"tony"} (up)' + ) + end + + def test_chained_releases + test_chained_dependencies + ChainTop.release(:system) + Tony.release(:system) + end +end diff --git a/state.py b/state.py new file mode 100644 index 0000000..594b32a --- /dev/null +++ b/state.py @@ -0,0 +1,154 @@ +# +class Category: + def __init__(self, name, **args): + self.args = args + self.name = name + + def equiv(self, other): + if self.name != other.name: return False + for key, value in self.args.iteritems(): + if not other.args.has_key(key): return False + if value == None: continue + if other.args[key] == None: continue + if not other.args[key] == value: return False + return True + + def intersect(self, other): + if self.name != other.name: return None + args = {} + for key in list(set(self.args.keys() + other.args.keys())): + if not self.args.has_key(key): + args[key] = other.args[key] + elif not other.args.has_key(key): + args[key] = self.args[key] + elif self.args[key] == None: + args[key] = other.args[key] + elif other.args[key] == None: + args[key] = self.args[key] + elif self.args[key] != other.args[key]: + return None + else: # self.args[key] == other.args[key] + args[key] = self.args[key] + return Category(self.name, **args) + + def __str__(self): + string = self.name + "(" + had = False + for key, val in self.args.iteritems(): + if had: + string += ", " + had = True + if val == None: + string += "%%%s" % key + else: + string += "%s: %s" % (key, val) + return string + ")" + + def __repr__(self): + return self.__str__() + + def __hash__(self): + return hash((self.argstup(), self.name)) + + def __eq__(self, other): + return self.name == other.name and self.argstup() == other.argstup() + + def argstup(self): + retval = [] + keys = self.args.keys() + keys.sort() + for key in keys: + retval.append((key, self.args[key])) + return tuple(retval) + + def filter(self, other): + if not other.name == self.name: + raise TypeError, "States must be the same class" + args = {} + for key, value in other.args.iteritems(): + if value != None or not self.args.has_key(key): + args[key] = value + else: + args[key] = self.args[key] + return Category(self.name, **args) + + def fill(self, info): + args = {} + for key, value in self.args.iteritems(): + if value != None or not info.has_key(key): + args[key] = value + else: + args[key] = info[key] + return Category(self.name, **args) + + def is_finite(self): + return not None in self.args.values() + +class StateMachine: + def __init__(self): + self.holds = {} + self.deps = [] + + def assert_state(self, cat): + found = None + for dependency in self.get_applicable_deps(cat): + res = self.get_satisfied_states(cat, dependency) + if len(res) == 0: + return False + if found == None: + found = res + else: + found = self.intersect_list(found, res) + if found == None: + self.add_hold(cat) + return True + if len(found) == 0: + return False + for x in found: + self.add_hold(x) + return True + + def intersect_list(self, cats1, cats2): + retval = set() + found = set() + for x in cats1: + for y in cats2: + if x == y: continue + inter = x.intersect(y) + if inter != None: + retval.add(inter) + found.add(x) + found.add(y) + if len(found) == 0: + return cats1 & cats2 + return (retval | ((cats1 & cats2) - found)) + + def add_hold(self, cat): + if self.holds.has_key(cat): + self.holds[cat] = self.holds[cat] + 1 + else: + self.holds[cat] = 1 + + def get_satisfied_states(self, dependents, dependencies): + retval = [] + for key, val in self.holds.iteritems(): + if dependencies.equiv(key) and val > 0: + retval.append(dependents.fill(key.args)) + return set(retval) + + def get_applicable_deps(self, cat): + retval = [] + for (x, y) in self.deps: + if x.equiv(cat): + retval.append(y.fill(cat.filter(x).args)) + return retval + +if __name__ == "__main__": + sm = StateMachine() + sm.deps.append((Category("mounted", type="nfs"), Category("network_up"))) + sm.deps.append((Category("mounted", uuid=None, devname=None, label=None), Category("found_disk", uuid=None, devname=None, label=None))) + sm.deps.append((Category("mounted", uuid=None, devname=None, label=None), Category("vol_conf", uuid=None, devname=None, label=None))) + sm.assert_state(Category("vol_conf", uuid=None, devname=None, label="myroot", type="ext3", mountpoint="/")) + sm.assert_state(Category("found_disk", uuid="d3adb3ef", devname="/dev/sda", label="myroot")) + sm.assert_state(Category("mounted", uuid=None, type="ext3", devname=None, label=None, mountpoint=None)) + print sm.holds diff --git a/state.rb b/state.rb deleted file mode 100644 index 02c1bf3..0000000 --- a/state.rb +++ /dev/null @@ -1,534 +0,0 @@ -=begin rdoc -UpState - An Upstart state machine prototype - -Author: Casey Dahlin -=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 - # :user or :system 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 diff --git a/test.rb b/test.rb deleted file mode 100644 index 87cb5bf..0000000 --- a/test.rb +++ /dev/null @@ -1,129 +0,0 @@ -require 'state' -require 'set' -require 'test/unit' - - -def put_states - foo = State.send(:class_variable_get, :@@states).map{ |x| x.to_s_color } - puts foo.sort.join(", ") -end - -class TC_State < Test::Unit::TestCase - include UpState - - Foo = State.new_type("foo", [Event.new("gimmefoo", {:bob => /^...$/})], [], [:bob]) - Bar = State.new_type("bar", [], [Dependency.new(Foo)]) - Baz = State.new_type("baz", [], [Dependency.new(Foo, {:bob => "abc"}, {:bob => :tom}), Dependency.new(Bar)]) - Bam = State.new_type("bam", [Event::Epsilon], [Dependency.new(Baz)]) - Bang = State.new_type("bang", [], [Dependency.new(Bam)]) - - def assert_have_states(*s) - assert_equal(s.sort, State.get_all.map{ |x| x.to_s }.sort) - end - - def assert_only_states(*s) - assert_have_states *s - assert_equal(State.get_all.size, s.size) - end - - def setup - assert_only_states "FooState{} (down)" - end - - def teardown - State.release(:user) - State.release(:system) - end - - def test_ignored_event - State.process_event(Event.new("gimmefoo", {:bob => "1234"})) - assert_only_states "FooState{} (down)" - end - - def test_responded_event - State.process_event(Event.new("gimmefoo", {:bob => "123"})) - assert_only_states('FooState{} (down)', 'FooState{:bob=>"123"} (up)', "BarState{} (down)") - end - - def test_hold_with_dependent - test_responded_event - Bar.get_all.first.hold(:user) - assert_only_states('FooState{} (down)', 'FooState{:bob=>"123"} (up)', "BarState{} (up)") - end - - def test_hold_non_existant_state - Bar.hold(:user) - assert_only_states "FooState{} (down)" - end - - def test_pattern_matched_param_dep - State.process_event(Event.new("gimmefoo", {:bob => "abc"})) - Bar.hold(:user) - assert_only_states( - 'BazState{:tom=>"abc"} (down)', - 'FooState{} (down)', - 'FooState{:bob=>"abc"} (up)', - "BarState{} (up)" - ) - end - - def test_duplicitous_state_by_deps - test_pattern_matched_param_dep - State.process_event(Event.new("gimmefoo", {:bob => "123"})) - assert_only_states( - 'BazState{:tom=>"abc"} (down)', - 'FooState{} (down)', - 'FooState{:bob=>"abc"} (up)', - 'FooState{:bob=>"123"} (up)', - "BarState{} (up)", - "BarState{} (down)" - ) - end - - def test_identity_uniqueness - test_pattern_matched_param_dep - State.process_event(Event.new("gimmefoo", {:bob => "abc"})) - assert_only_states( - 'BazState{:tom=>"abc"} (down)', - 'FooState{} (down)', - 'FooState{:bob=>"abc"} (up)', - "BarState{} (up)" - ) - end - - def test_epsilon - test_pattern_matched_param_dep - Baz.hold(:user) - assert_only_states( - 'BazState{:tom=>"abc"} (up)', - 'FooState{} (down)', - 'FooState{:bob=>"abc"} (up)', - "BarState{} (up)", - "BamState{} (up)", - "BangState{} (down)" - ) - end - - def test_release_noop - test_epsilon - Bar.release(:user) - assert_only_states( - 'BazState{:tom=>"abc"} (up)', - 'FooState{} (down)', - 'FooState{:bob=>"abc"} (up)', - "BarState{} (up)", - "BamState{} (up)", - "BangState{} (down)" - ) - end - - def test_drop_cleanup - test_release_noop - Bar.get_all.each{ |x| x.drop } - assert_only_states( - 'FooState{} (down)', - 'FooState{:bob=>"abc"} (up)', - "BarState{} (down)" - ) - end -end diff --git a/test2.rb b/test2.rb deleted file mode 100644 index 0a43d58..0000000 --- a/test2.rb +++ /dev/null @@ -1,93 +0,0 @@ -require 'state' -require 'set' -require 'test/unit' - -class TC_State < Test::Unit::TestCase - include UpState - - Tony = State.new_type("tony", [Event.new("tonyup", {:tony => "tony"})], [], [:tony]) - Mike = State.new_type("mike", [], [Dependency.new(Tony)]) - ChainTop = State.new_type("chaintop", [], [Dependency.new(Tony, {:tony => "tony"}, {:tony => :bob}), - Dependency.new(Mike)]) - #this state should never appear - Reversed = State.new_type("reversed", [Dependency.new(Tony)], [Event.new("tonyup", {:tony => "tony"})]) - - def put_states - foo = State.send(:class_variable_get, :@@states).map{ |x| x.to_s_color } - puts foo.sort.join(", ") - end - - def assert_have_states(*s) - assert_equal(s.sort, State.get_all.map{ |x| x.to_s }.sort) - end - - def assert_only_states(*s) - assert_have_states *s - assert_equal(State.get_all.size, s.size) - end - - def setup - assert_only_states( - 'TonyState{} (down)' - ) - end - - def teardown - State.release(:user) - State.release(:system) - end - - def test_reversed - #this should never ever come up - Reversed.hold(:user) - assert_only_states( - 'TonyState{} (down)' - ) - end - - def test_incomplete_hold - begin - Tony.hold(:user) - assert(false) - end - rescue AmbiguousRequest => e - assert(true) - end - - def test_bogus_hold - begin - Tony.hold(:cookies) - assert(false) - end - rescue TypeError => e - assert(true) - end - - def test_bogus_release - begin - State.process_event(Event.new("tonyup", {:tony => "tony"})) - Tony.release(:cookies) - assert(false) - end - rescue TypeError => e - assert(true) - end - - def test_chained_dependencies - State.process_event(Event.new("tonyup", {:tony => "tony"})) - Mike.hold(:user) - ChainTop.hold(:system, {:bob => "tony"}) - assert_only_states( - 'TonyState{} (down)', - 'ChaintopState{:bob=>"tony"} (up)', - 'MikeState{} (up)', - 'TonyState{:tony=>"tony"} (up)' - ) - end - - def test_chained_releases - test_chained_dependencies - ChainTop.release(:system) - Tony.release(:system) - end -end -- cgit