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
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
|
=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
# 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|
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
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, "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
# 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
|