1# Copyright (c) 2008, Google Inc.
2# All rights reserved.
3#
4# Redistribution and use in source and binary forms, with or without
5# modification, are permitted provided that the following conditions are
6# met:
7#
8#     * Redistributions of source code must retain the above copyright
9# notice, this list of conditions and the following disclaimer.
10#     * Redistributions in binary form must reproduce the above
11# copyright notice, this list of conditions and the following disclaimer
12# in the documentation and/or other materials provided with the
13# distribution.
14#     * Neither the name of Google Inc. nor the names of its
15# contributors may be used to endorse or promote products derived from
16# this software without specific prior written permission.
17#
18# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29# ---
30#
31# Create a state machine object based on a definition file.
32#
33
34__author__ = 'falmeida@google.com (Filipe Almeida)'
35
36class OrderedDict:
37  """Ordered dictionary implementation."""
38
39  # Define the minimum functionality we need for our application.
40  # Easiser would be to subclass from UserDict.DictMixin, and only
41  # define __getitem__, __setitem__, __delitem__, and keys, but that's
42  # not as portable.  We don't need to define much more, so we just do.
43
44  def __init__(self):
45    self._dict = {}
46    self._keys = []
47
48  def __getitem__(self, key):
49    return self._dict[key]
50
51  def __setitem__(self, key, value):
52    if key not in self._keys:
53      self._keys.append(key)
54    self._dict[key] = value
55
56  def __delitem__(self, key):
57    self._keys.remove(key)
58    del self._dict[key]
59
60  def keys(self):
61    return self._keys
62
63  # Below are all we have to define in addition to what DictMixin would need
64  def __len__(self):
65    return len(self.keys())
66
67  def __contains__(self, key):
68    return self.has_key(key)
69
70  def __iter__(self):
71    # It's not as portable -- though it would be more space-efficient -- to do
72    #   for k in self.keys(): yield k
73    return iter(self.keys())
74
75class State(object):
76  """Contains information about a specific state."""
77
78  def __init__(self):
79    pass
80
81  name = None
82  external_name = None
83  transitions = []
84
85
86class Transition(object):
87  """Contains information about a specific transition."""
88
89  def __init__(self, condition, source, destination):
90    self.condition = condition
91    self.source = source
92    self.destination = destination
93
94
95class FSMConfig(object):
96  """Container for the statemachine definition."""
97
98  sm = {}  # dictionary that contains the finite state machine definition
99           # loaded from a config file.
100  transitions = []  # List of transitions.
101  conditions = {}   # Mapping between the condition name and the bracket
102                    # expression.
103  states = OrderedDict()  # Ordered dictionary of states.
104  name = None
105  comment = None
106
107  def AddState(self, **dic):
108    """Called from the definition file with the description of the state.
109
110    Receives a dictionary and populates internal structures based on it. The
111    dictionary is in the following format:
112
113    {'name': state_name,
114     'external': exposed state name,
115     'transitions': [
116       [condition, destination_state ],
117       [condition, destination_state ]
118     ]
119    }
120
121    """
122
123    state = State()
124    state.name = dic['name']
125    state.external_name = dic['external']
126
127    state_transitions = []
128
129    for (condition, destination) in dic['transitions']:
130      transition = Transition(condition, state.name, destination)
131      state_transitions.append(transition)
132
133    self.transitions.extend(state_transitions)
134    state.transitions = state_transitions
135    self.states[state.name] = state
136
137  def AddCondition(self, name, expression):
138    """Called from the definition file with the definition of a condition.
139
140    Receives the name of the condition and it's expression.
141    """
142    self.conditions[name] = expression
143
144  def Load(self, filename):
145    """Load the state machine definition file.
146
147    In the definition file, which is based on the python syntax, the following
148    variables and functions are defined.
149
150    name: Name of the state machine
151    comment: Comment line on the generated file.
152    condition(): A mapping between condition names and bracket expressions.
153    state(): Defines a state and it's transitions. It accepts the following
154             attributes:
155      name: name of the state
156      external: exported name of the state. The exported name can be used
157                multiple times in order to create a super state.
158      transitions: List of pairs containing the condition for the transition
159                   and the destination state. Transitions are ordered so if
160                   a default rule is used, it must be the last one in the list.
161
162    Example:
163
164    name = 'c comment parser'
165
166    condition('/', '/')
167    condition('*', '*')
168    condition('linefeed', '\\n')
169    condition('default', '[:default:]')
170
171    state(name = 'text',
172          external = 'comment',
173          transitions = [
174            [ '/', 'comment_start' ],
175            [ 'default', 'text' ]
176          ])
177
178    state(name = 'comment_start',
179          external = 'comment',
180          transitions = [
181            [ '/', 'comment_line' ],
182            [ '*', 'comment_multiline' ],
183            [ 'default', 'text' ]
184          ])
185
186    state(name = 'comment_line',
187          external = 'comment',
188          transitions = [
189            [ 'linefeed', 'text' ],
190            [ 'default', 'comment_line' ]
191          ])
192
193    state(name = 'comment_multiline',
194          external = 'comment',
195          transitions = [
196            [ '*', 'comment_multiline_close' ],
197            [ 'default', 'comment_multiline' ]
198          ])
199
200    state(name = 'comment_multiline_close',
201          external = 'comment',
202          transitions = [
203            [ '/', 'text' ],
204            [ 'default', 'comment_multiline' ]
205          ])
206
207    """
208
209    self.sm['state'] = self.AddState
210    self.sm['condition'] = self.AddCondition
211    exec(open(filename).read(), self.sm)
212    self.name = self.sm['name']
213    if not self.name.isalnum():
214      raise Exception("State machine name must consist of only alphanumeric"
215                      "characters.")
216    self.comment = self.sm['comment']
217
218  def __init__(self):
219    pass
220