1
# canonical.ubuntuone.storage.syncdaemon.fsm.fsm - a fsm
3
# Author: Lucio Torre <lucio.torre@canonical.com>
5
# Copyright 2009 Canonical Ltd.
7
# This program is free software: you can redistribute it and/or modify it
8
# under the terms of the GNU General Public License version 3, as published
9
# by the Free Software Foundation.
11
# This program is distributed in the hope that it will be useful, but
12
# WITHOUT ANY WARRANTY; without even the implied warranties of
13
# MERCHANTABILITY, SATISFACTORY QUALITY, or FITNESS FOR A PARTICULAR
14
# PURPOSE. See the GNU General Public License for more details.
16
# You should have received a copy of the GNU General Public License along
17
# with this program. If not, see <http://www.gnu.org/licenses/>.
19
Will read the output produced by fsm_parser.parse or a .py serialization of
20
it and create and validate a state machine.
24
from canonical.ubuntuone.storage.syncdaemon import logger
27
product = itertools.product
28
except AttributeError:
29
# taken from python docs for 2.6
30
def product(*args, **kwds):
32
# product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
33
# product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
34
pools = map(tuple, args) * kwds.get('repeat', 1)
37
result = [x+[y] for x in result for y in pool]
43
"return a hashable representation of the dict"
44
return tuple(sorted(d.items()))
46
class ValidationFailed(Exception):
47
"""signals that the specification is not correct"""
49
class ValidationError(object):
50
"""Contains validation errors"""
52
def __init__(self, description):
53
"create a validation error with description"
54
self.description = description
58
return "Validation Error: %s" % self.description
60
def build_combinations_from_varlist(varlist):
61
""" create all posible variable values combinations
63
takes a dict in the form {varname: [value, value2, *]}
64
returns [{varname:value}, {varname:value2}, ...]
66
items = varlist.items()
67
keys = [ x[0] for x in items ]
68
# pylint: disable-msg=W0631
69
values = [ x[1] for x in items ]
71
possible_states = [dict(zip(keys, state))
72
for state in product(*values) ]
73
return possible_states
75
def expand_var_list(varlist, values):
76
""" exapand a state description
78
takes a {varname:value} dict and returns a list of {varname:value} but with
79
stars and bangs replaced for all its possible values
81
myvalues = values.copy()
84
if str(myvalues[name]) == "*":
85
myvalues[name] = varlist[name]
86
elif str(myvalues[name])[0] == "!":
87
l = varlist[name].copy()
88
l.remove(myvalues[name][1:])
91
myvalues[name] = [myvalues[name]]
92
return build_combinations_from_varlist(myvalues)
94
class StateMachineRunner(object):
95
"""Reads a StateMachine descriptions and executes transitions."""
97
def __init__(self, fsm, log=None):
98
"""Create a state machine based on fsm."""
101
self.log = logger.root_logger
105
def on_event(self, event_name, parameters, *args):
106
"""Do the transition for this event."""
108
self.log.debug("EVENT: %s:%s with ARGS:%s"%(
109
event_name, parameters, args))
111
enter_state = self.get_state()
113
self.log.error("cant find current state: %s" % (
114
self.get_state_values()))
115
raise KeyError("Incorrect In State")
117
# find the transition
119
transition = enter_state.get_transition(event_name, parameters)
121
self.log.error("Cant find transition %s:%s" %
122
(event_name, parameters))
124
action_func_name = transition.action_func
125
# call the action_func
126
af = getattr(self, action_func_name, None)
128
self.log.error("cant find ACTION_FUNC: %s" % (action_func_name))
130
self.log.debug("passing")
132
# pylint: disable-msg=W0703
133
self.log.debug("Calling %s"%action_func_name)
135
af(event_name, parameters, *args)
137
self.log.exception("Executing ACTION_FUNC '%s' "
138
"gave an exception" %
140
self.on_error(event_name, parameters)
142
# validate the end state
144
out_state = self.get_state()
146
self.log.error("from state %s on %s:%s, "
147
"cant find current out state: %s" % (
148
enter_state.values, event_name, parameters,
149
self.get_state_values()))
150
self.on_error(event_name, parameters)
151
raise KeyError("unknown out state")
153
if out_state.values != transition.target:
155
"in state %s with event %s:%s, out state is:"
156
"%s and should be %s" % (
157
enter_state.values, event_name, parameters,
158
out_state.values, transition.target))
159
raise ValueError("Incorrect out state")
160
self.log.debug("Called %s"%action_func_name)
163
"""Get the current state's object"""
164
return self.fsm.get_state(self.get_state_values())
166
def get_state_values(self):
167
"""Get the state variables values for this state.
169
This has to be overridden on implementations of this class.
171
raise NotImplementedError()
173
def on_error(self, event_name, parameters):
174
"""A Transition encontered an error. Cleanup.
178
class StateMachine(object):
179
"""The state machine"""
181
def __init__(self, input_data, event_filter=None):
182
"""create a fsm from filename.
184
filename can be an .ods file or a dictionary
185
event_filter, if not None, limits the events you want to parse.
188
self.event_filter = event_filter
189
if isinstance(input_data, str):
190
if input_data.endswith(".ods"):
191
# fsm_parser depends on python-uno for reading ods documents
192
# this shouldnt be called with an .ods file on production
194
from canonical.ubuntuone.storage.syncdaemon.fsm import \
196
spec = fsm_parser.parse(input_data)
197
elif input_data.endswith(".py"):
199
# pylint doesnt like exec
200
# pylint: disable-msg=W0122
201
exec open(input_data) in result
202
spec = result["state_machine"]
204
raise ValueError("Unknown input format")
215
"""Raises an exception if the file had errors."""
217
raise ValidationFailed("There are %s validation errors"%
221
def get_variable_values(self, kind, name):
222
"""Returns all the values a variable of kind in
223
[STATE, PARAMETERS, STATE_OUT] with name name can take.
226
for event in self.spec["events"].values():
229
value = state[kind][name]
231
self.errors.append(ValidationError(
232
"variable name '%s' not found in section %s"%(
235
if str(value).strip() == "=" and kind != "STATE_OUT":
236
self.errors.append(ValidationError(
237
"Cant have '=' in STATE or PARAMETERS section"
239
if not str(value).strip() in ("*", "="):
240
if not str(value).strip()[0] == "!":
246
"""Do all the parsing and validating."""
247
# build state variable posible values
249
for state_var in self.spec["state_vars"]:
250
values = self.get_variable_values("STATE", state_var)
251
values.update(self.get_variable_values("STATE_OUT", state_var))
252
state_vars[state_var] = values
254
self.state_vars = state_vars
256
# build message parameter posible values
258
for state_var in self.spec["parameters"]:
259
values = self.get_variable_values("PARAMETERS", state_var)
260
parameters[state_var] = values
262
self.param_vars = parameters
264
# build posible states
265
possible_states = build_combinations_from_varlist(self.state_vars)
267
for s in self.spec["invalid"]:
268
for es in expand_var_list(self.state_vars, s):
270
possible_states.remove(es)
273
ValidationError("State %s already removed from invalid"%
277
for stateval in possible_states:
278
self.states[hash_dict(stateval)] = State(stateval)
281
for event_name, lines in self.spec["events"].items():
282
if self.event_filter and not event_name in self.event_filter:
284
event = Event(event_name, lines, self)
285
self.events[event_name] = event
286
tracker = event.get_tracker()
287
for transition in event.transitions:
288
# for each transition
290
state = self.states[hash_dict(transition.source)]
293
# pylint: disable-msg=W0101
294
# we dont error, so * that cover invalid states still work
296
# we should check that if the transition
297
# is not expanded or all the states it covers are
298
# invalid, because this is an error
300
ValidationError("Transitiont on %s with %s from '%s'"
301
"cant find source state."%(
303
transition.parameters,
308
s.update(transition.source)
309
s.update(transition.parameters)
313
self.errors.append(ValidationError(
314
"For event %s, the following transition was "
315
"already covered: %s"%(
318
state.add_transition(transition)
320
for s in tracker.pending:
321
self.errors.append(ValidationError(
322
"The following state x parameters where "
323
"not covered for '%s': %s"%(
326
def get_state(self, vars_dict):
327
"""Get a state instance from a dict with {varname:value}"""
328
return self.states[hash_dict(vars_dict)]
330
class Tracker(object):
331
"""Tracks a list of state_x_params combinations.
333
Does the same that a list does, but its more explicit. it used to do more.
335
def __init__(self, state_x_params):
336
"""Create a tracker."""
337
self.pending = state_x_params[:]
339
def remove(self, case):
341
self.pending.remove(case)
344
"""Check for pending cases."""
345
return bool(self.pending)
348
"""Represents events that may happen.
350
Interesting properties:
351
name: the name of the event
352
state_vars: {varname:[value, value2, ...]} for state
353
param_vars: {varname:[value, value2, ...]} for params
354
transitions: all the transitions that this event produces
355
draw_transitions: the transitions, but not expanded. for drawing.
356
state_x_params: all the posible state_x_params this event may encounter
358
def __init__(self, name, lines, machine):
359
state_vars = machine.state_vars
360
param_vars = machine.param_vars
361
self.invalid_states = machine.spec["invalid"]
363
self.state_vars = state_vars.copy()
364
self.event_vars = param_vars.copy()
365
# create transitions expanding *'s
366
self.transitions = []
367
# we have to remove parameters that have NA on all the rows
368
invalid = set(param_vars.keys())
371
for k, v in line["PARAMETERS"].items():
372
if str(v).strip() != "NA":
373
# this parameter has a value, remove from invalid list
377
#remove invalids from lines
380
if inv in line["PARAMETERS"]:
381
del line["PARAMETERS"][inv]
383
# remove invalid from param_vars
385
del self.event_vars[inv]
387
# make list of state_x_parameters to cover
389
vlist.update(self.state_vars)
390
vlist.update(self.event_vars)
391
self.state_x_params = build_combinations_from_varlist(vlist)
392
# now we remove the lines that have been defines as invalid
394
for i in self.invalid_states:
395
for ei in expand_var_list(state_vars, i):
396
for sxp in self.state_x_params:
397
for k, v in ei.items():
401
if not sxp in toremove:
404
map(self.state_x_params.remove, toremove)
406
# create transitions by expanding states
408
state_exp = expand_var_list(state_vars, line["STATE"])
409
param_exp = expand_var_list(param_vars, line["PARAMETERS"])
412
new_line = line.copy()
413
# copy source state if dest state is '='
414
so = new_line["STATE_OUT"].copy()
416
if str(so[k]).strip() == "=":
418
new_line["STATE"] = se
419
new_line["PARAMETERS"] = pe
420
new_line["STATE_OUT"] = so
422
# here we have the expanded lines, remove from
423
# states_x_params the lines with action NA
424
if str(new_line["ACTION"]).strip() == "NA":
426
s_x_p.update(new_line["STATE"])
427
s_x_p.update(new_line["PARAMETERS"])
428
if s_x_p in self.state_x_params:
429
self.state_x_params.remove(s_x_p)
431
self.transitions.append(Transition(name, new_line))
433
# create transitions by expanding states, but dont expand params
434
# so we can use this transitions to draw them
435
self.draw_transitions = []
437
state_exp = expand_var_list(state_vars, line["STATE"])
438
pe = line["PARAMETERS"]
440
new_line = line.copy()
441
# copy source state if dest state is '='
442
so = new_line["STATE_OUT"].copy()
444
if str(so[k]).strip() == "=":
446
new_line["STATE"] = se
447
new_line["PARAMETERS"] = pe
448
new_line["STATE_OUT"] = so
450
# here we have the expanded lines, remove from
451
# states_x_params the lines with action NA
452
if not str(new_line["ACTION"]).strip() == "NA":
453
self.draw_transitions.append(Transition(name, new_line))
458
return "<Event: %s>" % self.name
460
def get_tracker(self):
461
"""Get a tracker for this state."""
462
return Tracker(self.state_x_params)
465
class Transition(object):
468
For each expansion of a transition line in the original spreadsheet we
469
get one of these. with the corresponding attributes for all sections
472
def __init__(self, event, line):
473
"""Create a transition for event event from line.
475
line may be an expanded version of a source line.
479
self.source = line["STATE"]
480
self.target = line["STATE_OUT"]
481
self.parameters = line["PARAMETERS"]
482
self.action_func = line["ACTION_FUNC"]
486
return "<Transition: %s: %s x %s>" % (
487
self.event, self.source, self.parameters)
493
Represents a combination of state variable values.
494
values: the state values
495
transitions: the transitions that leave from this state
498
def __init__(self, values):
499
"""Create a state."""
501
self.transitions = {}
503
def add_transition(self, transition):
504
"""Add a transition."""
505
self.transitions[transition.event,
506
hash_dict(transition.parameters)] = transition
508
def get_transition(self, event, parameters):
509
"""Get the transition for this events with these parameters."""
510
return self.transitions[event, hash_dict(parameters)]
512
if __name__ == "__main__":
514
s = StateMachine(sys.argv[1], sys.argv[2:])
517
print >> sys.stderr, e
518
print "There are %s errors" % (len(s.errors))
521
print "validated ok."
added
removed
canonical/ubuntuone/storage/syncdaemon/fsm/fsm.py
