1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
|
=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
ENABLE_TRACE = false
def trace(*args)
return unless ENABLE_TRACE
$stderr.puts *args
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 :deps # What are our dependencies?
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 react_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
# Puts the class name and parameters
def to_s
"#{self.class.name}#{params.inspect} (#{@active ? "up" : "down"})"
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
# eql? is the same as ==
alias :eql? :==
# 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.react_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? []
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.reject! do |dset|
active_states.select{ |x| x.is_a? self and x.deps == dset }.size > 0
end
candidates.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
# Hold all states of a class
def State.hold(type)
@@states.select{ |x| x.is_a? self }.each{ |x| x.hold(type) }
end
private
# Set this state to true
def rise
return if @active
@deps.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
# 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 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
# 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 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
|