001 /**
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements. See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership. The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License. You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018
019 package org.apache.hadoop.yarn.state;
020
021 import java.util.EnumMap;
022 import java.util.HashMap;
023 import java.util.Iterator;
024 import java.util.Map;
025 import java.util.Map.Entry;
026 import java.util.Set;
027 import java.util.Stack;
028
029 import org.apache.hadoop.classification.InterfaceAudience.Public;
030 import org.apache.hadoop.classification.InterfaceStability.Evolving;
031
032 /**
033 * State machine topology.
034 * This object is semantically immutable. If you have a
035 * StateMachineFactory there's no operation in the API that changes
036 * its semantic properties.
037 *
038 * @param <OPERAND> The object type on which this state machine operates.
039 * @param <STATE> The state of the entity.
040 * @param <EVENTTYPE> The external eventType to be handled.
041 * @param <EVENT> The event object.
042 *
043 */
044 @Public
045 @Evolving
046 final public class StateMachineFactory
047 <OPERAND, STATE extends Enum<STATE>,
048 EVENTTYPE extends Enum<EVENTTYPE>, EVENT> {
049
050 private final TransitionsListNode transitionsListNode;
051
052 private Map<STATE, Map<EVENTTYPE,
053 Transition<OPERAND, STATE, EVENTTYPE, EVENT>>> stateMachineTable;
054
055 private STATE defaultInitialState;
056
057 private final boolean optimized;
058
059 /**
060 * Constructor
061 *
062 * This is the only constructor in the API.
063 *
064 */
065 public StateMachineFactory(STATE defaultInitialState) {
066 this.transitionsListNode = null;
067 this.defaultInitialState = defaultInitialState;
068 this.optimized = false;
069 this.stateMachineTable = null;
070 }
071
072 private StateMachineFactory
073 (StateMachineFactory<OPERAND, STATE, EVENTTYPE, EVENT> that,
074 ApplicableTransition<OPERAND, STATE, EVENTTYPE, EVENT> t) {
075 this.defaultInitialState = that.defaultInitialState;
076 this.transitionsListNode
077 = new TransitionsListNode(t, that.transitionsListNode);
078 this.optimized = false;
079 this.stateMachineTable = null;
080 }
081
082 private StateMachineFactory
083 (StateMachineFactory<OPERAND, STATE, EVENTTYPE, EVENT> that,
084 boolean optimized) {
085 this.defaultInitialState = that.defaultInitialState;
086 this.transitionsListNode = that.transitionsListNode;
087 this.optimized = optimized;
088 if (optimized) {
089 makeStateMachineTable();
090 } else {
091 stateMachineTable = null;
092 }
093 }
094
095 private interface ApplicableTransition
096 <OPERAND, STATE extends Enum<STATE>,
097 EVENTTYPE extends Enum<EVENTTYPE>, EVENT> {
098 void apply(StateMachineFactory<OPERAND, STATE, EVENTTYPE, EVENT> subject);
099 }
100
101 private class TransitionsListNode {
102 final ApplicableTransition<OPERAND, STATE, EVENTTYPE, EVENT> transition;
103 final TransitionsListNode next;
104
105 TransitionsListNode
106 (ApplicableTransition<OPERAND, STATE, EVENTTYPE, EVENT> transition,
107 TransitionsListNode next) {
108 this.transition = transition;
109 this.next = next;
110 }
111 }
112
113 static private class ApplicableSingleOrMultipleTransition
114 <OPERAND, STATE extends Enum<STATE>,
115 EVENTTYPE extends Enum<EVENTTYPE>, EVENT>
116 implements ApplicableTransition<OPERAND, STATE, EVENTTYPE, EVENT> {
117 final STATE preState;
118 final EVENTTYPE eventType;
119 final Transition<OPERAND, STATE, EVENTTYPE, EVENT> transition;
120
121 ApplicableSingleOrMultipleTransition
122 (STATE preState, EVENTTYPE eventType,
123 Transition<OPERAND, STATE, EVENTTYPE, EVENT> transition) {
124 this.preState = preState;
125 this.eventType = eventType;
126 this.transition = transition;
127 }
128
129 @Override
130 public void apply
131 (StateMachineFactory<OPERAND, STATE, EVENTTYPE, EVENT> subject) {
132 Map<EVENTTYPE, Transition<OPERAND, STATE, EVENTTYPE, EVENT>> transitionMap
133 = subject.stateMachineTable.get(preState);
134 if (transitionMap == null) {
135 // I use HashMap here because I would expect most EVENTTYPE's to not
136 // apply out of a particular state, so FSM sizes would be
137 // quadratic if I use EnumMap's here as I do at the top level.
138 transitionMap = new HashMap<EVENTTYPE,
139 Transition<OPERAND, STATE, EVENTTYPE, EVENT>>();
140 subject.stateMachineTable.put(preState, transitionMap);
141 }
142 transitionMap.put(eventType, transition);
143 }
144 }
145
146 /**
147 * @return a NEW StateMachineFactory just like {@code this} with the current
148 * transition added as a new legal transition. This overload
149 * has no hook object.
150 *
151 * Note that the returned StateMachineFactory is a distinct
152 * object.
153 *
154 * This method is part of the API.
155 *
156 * @param preState pre-transition state
157 * @param postState post-transition state
158 * @param eventType stimulus for the transition
159 */
160 public StateMachineFactory
161 <OPERAND, STATE, EVENTTYPE, EVENT>
162 addTransition(STATE preState, STATE postState, EVENTTYPE eventType) {
163 return addTransition(preState, postState, eventType, null);
164 }
165
166 /**
167 * @return a NEW StateMachineFactory just like {@code this} with the current
168 * transition added as a new legal transition. This overload
169 * has no hook object.
170 *
171 *
172 * Note that the returned StateMachineFactory is a distinct
173 * object.
174 *
175 * This method is part of the API.
176 *
177 * @param preState pre-transition state
178 * @param postState post-transition state
179 * @param eventTypes List of stimuli for the transitions
180 */
181 public StateMachineFactory<OPERAND, STATE, EVENTTYPE, EVENT> addTransition(
182 STATE preState, STATE postState, Set<EVENTTYPE> eventTypes) {
183 return addTransition(preState, postState, eventTypes, null);
184 }
185
186 /**
187 * @return a NEW StateMachineFactory just like {@code this} with the current
188 * transition added as a new legal transition
189 *
190 * Note that the returned StateMachineFactory is a distinct
191 * object.
192 *
193 * This method is part of the API.
194 *
195 * @param preState pre-transition state
196 * @param postState post-transition state
197 * @param eventTypes List of stimuli for the transitions
198 * @param hook transition hook
199 */
200 public StateMachineFactory<OPERAND, STATE, EVENTTYPE, EVENT> addTransition(
201 STATE preState, STATE postState, Set<EVENTTYPE> eventTypes,
202 SingleArcTransition<OPERAND, EVENT> hook) {
203 StateMachineFactory<OPERAND, STATE, EVENTTYPE, EVENT> factory = null;
204 for (EVENTTYPE event : eventTypes) {
205 if (factory == null) {
206 factory = addTransition(preState, postState, event, hook);
207 } else {
208 factory = factory.addTransition(preState, postState, event, hook);
209 }
210 }
211 return factory;
212 }
213
214 /**
215 * @return a NEW StateMachineFactory just like {@code this} with the current
216 * transition added as a new legal transition
217 *
218 * Note that the returned StateMachineFactory is a distinct object.
219 *
220 * This method is part of the API.
221 *
222 * @param preState pre-transition state
223 * @param postState post-transition state
224 * @param eventType stimulus for the transition
225 * @param hook transition hook
226 */
227 public StateMachineFactory
228 <OPERAND, STATE, EVENTTYPE, EVENT>
229 addTransition(STATE preState, STATE postState,
230 EVENTTYPE eventType,
231 SingleArcTransition<OPERAND, EVENT> hook){
232 return new StateMachineFactory<OPERAND, STATE, EVENTTYPE, EVENT>
233 (this, new ApplicableSingleOrMultipleTransition<OPERAND, STATE, EVENTTYPE, EVENT>
234 (preState, eventType, new SingleInternalArc(postState, hook)));
235 }
236
237 /**
238 * @return a NEW StateMachineFactory just like {@code this} with the current
239 * transition added as a new legal transition
240 *
241 * Note that the returned StateMachineFactory is a distinct object.
242 *
243 * This method is part of the API.
244 *
245 * @param preState pre-transition state
246 * @param postStates valid post-transition states
247 * @param eventType stimulus for the transition
248 * @param hook transition hook
249 */
250 public StateMachineFactory
251 <OPERAND, STATE, EVENTTYPE, EVENT>
252 addTransition(STATE preState, Set<STATE> postStates,
253 EVENTTYPE eventType,
254 MultipleArcTransition<OPERAND, EVENT, STATE> hook){
255 return new StateMachineFactory<OPERAND, STATE, EVENTTYPE, EVENT>
256 (this,
257 new ApplicableSingleOrMultipleTransition<OPERAND, STATE, EVENTTYPE, EVENT>
258 (preState, eventType, new MultipleInternalArc(postStates, hook)));
259 }
260
261 /**
262 * @return a StateMachineFactory just like {@code this}, except that if
263 * you won't need any synchronization to build a state machine
264 *
265 * Note that the returned StateMachineFactory is a distinct object.
266 *
267 * This method is part of the API.
268 *
269 * The only way you could distinguish the returned
270 * StateMachineFactory from {@code this} would be by
271 * measuring the performance of the derived
272 * {@code StateMachine} you can get from it.
273 *
274 * Calling this is optional. It doesn't change the semantics of the factory,
275 * if you call it then when you use the factory there is no synchronization.
276 */
277 public StateMachineFactory
278 <OPERAND, STATE, EVENTTYPE, EVENT>
279 installTopology() {
280 return new StateMachineFactory<OPERAND, STATE, EVENTTYPE, EVENT>(this, true);
281 }
282
283 /**
284 * Effect a transition due to the effecting stimulus.
285 * @param state current state
286 * @param eventType trigger to initiate the transition
287 * @param cause causal eventType context
288 * @return transitioned state
289 */
290 private STATE doTransition
291 (OPERAND operand, STATE oldState, EVENTTYPE eventType, EVENT event)
292 throws InvalidStateTransitonException {
293 // We can assume that stateMachineTable is non-null because we call
294 // maybeMakeStateMachineTable() when we build an InnerStateMachine ,
295 // and this code only gets called from inside a working InnerStateMachine .
296 Map<EVENTTYPE, Transition<OPERAND, STATE, EVENTTYPE, EVENT>> transitionMap
297 = stateMachineTable.get(oldState);
298 if (transitionMap != null) {
299 Transition<OPERAND, STATE, EVENTTYPE, EVENT> transition
300 = transitionMap.get(eventType);
301 if (transition != null) {
302 return transition.doTransition(operand, oldState, event, eventType);
303 }
304 }
305 throw new InvalidStateTransitonException(oldState, eventType);
306 }
307
308 private synchronized void maybeMakeStateMachineTable() {
309 if (stateMachineTable == null) {
310 makeStateMachineTable();
311 }
312 }
313
314 private void makeStateMachineTable() {
315 Stack<ApplicableTransition<OPERAND, STATE, EVENTTYPE, EVENT>> stack =
316 new Stack<ApplicableTransition<OPERAND, STATE, EVENTTYPE, EVENT>>();
317
318 Map<STATE, Map<EVENTTYPE, Transition<OPERAND, STATE, EVENTTYPE, EVENT>>>
319 prototype = new HashMap<STATE, Map<EVENTTYPE, Transition<OPERAND, STATE, EVENTTYPE, EVENT>>>();
320
321 prototype.put(defaultInitialState, null);
322
323 // I use EnumMap here because it'll be faster and denser. I would
324 // expect most of the states to have at least one transition.
325 stateMachineTable
326 = new EnumMap<STATE, Map<EVENTTYPE,
327 Transition<OPERAND, STATE, EVENTTYPE, EVENT>>>(prototype);
328
329 for (TransitionsListNode cursor = transitionsListNode;
330 cursor != null;
331 cursor = cursor.next) {
332 stack.push(cursor.transition);
333 }
334
335 while (!stack.isEmpty()) {
336 stack.pop().apply(this);
337 }
338 }
339
340 private interface Transition<OPERAND, STATE extends Enum<STATE>,
341 EVENTTYPE extends Enum<EVENTTYPE>, EVENT> {
342 STATE doTransition(OPERAND operand, STATE oldState,
343 EVENT event, EVENTTYPE eventType);
344 }
345
346 private class SingleInternalArc
347 implements Transition<OPERAND, STATE, EVENTTYPE, EVENT> {
348
349 private STATE postState;
350 private SingleArcTransition<OPERAND, EVENT> hook; // transition hook
351
352 SingleInternalArc(STATE postState,
353 SingleArcTransition<OPERAND, EVENT> hook) {
354 this.postState = postState;
355 this.hook = hook;
356 }
357
358 @Override
359 public STATE doTransition(OPERAND operand, STATE oldState,
360 EVENT event, EVENTTYPE eventType) {
361 if (hook != null) {
362 hook.transition(operand, event);
363 }
364 return postState;
365 }
366 }
367
368 private class MultipleInternalArc
369 implements Transition<OPERAND, STATE, EVENTTYPE, EVENT>{
370
371 // Fields
372 private Set<STATE> validPostStates;
373 private MultipleArcTransition<OPERAND, EVENT, STATE> hook; // transition hook
374
375 MultipleInternalArc(Set<STATE> postStates,
376 MultipleArcTransition<OPERAND, EVENT, STATE> hook) {
377 this.validPostStates = postStates;
378 this.hook = hook;
379 }
380
381 @Override
382 public STATE doTransition(OPERAND operand, STATE oldState,
383 EVENT event, EVENTTYPE eventType)
384 throws InvalidStateTransitonException {
385 STATE postState = hook.transition(operand, event);
386
387 if (!validPostStates.contains(postState)) {
388 throw new InvalidStateTransitonException(oldState, eventType);
389 }
390 return postState;
391 }
392 }
393
394 /*
395 * @return a {@link StateMachine} that starts in
396 * {@code initialState} and whose {@link Transition} s are
397 * applied to {@code operand} .
398 *
399 * This is part of the API.
400 *
401 * @param operand the object upon which the returned
402 * {@link StateMachine} will operate.
403 * @param initialState the state in which the returned
404 * {@link StateMachine} will start.
405 *
406 */
407 public StateMachine<STATE, EVENTTYPE, EVENT>
408 make(OPERAND operand, STATE initialState) {
409 return new InternalStateMachine(operand, initialState);
410 }
411
412 /*
413 * @return a {@link StateMachine} that starts in the default initial
414 * state and whose {@link Transition} s are applied to
415 * {@code operand} .
416 *
417 * This is part of the API.
418 *
419 * @param operand the object upon which the returned
420 * {@link StateMachine} will operate.
421 *
422 */
423 public StateMachine<STATE, EVENTTYPE, EVENT> make(OPERAND operand) {
424 return new InternalStateMachine(operand, defaultInitialState);
425 }
426
427 private class InternalStateMachine
428 implements StateMachine<STATE, EVENTTYPE, EVENT> {
429 private final OPERAND operand;
430 private STATE currentState;
431
432 InternalStateMachine(OPERAND operand, STATE initialState) {
433 this.operand = operand;
434 this.currentState = initialState;
435 if (!optimized) {
436 maybeMakeStateMachineTable();
437 }
438 }
439
440 @Override
441 public synchronized STATE getCurrentState() {
442 return currentState;
443 }
444
445 @Override
446 public synchronized STATE doTransition(EVENTTYPE eventType, EVENT event)
447 throws InvalidStateTransitonException {
448 currentState = StateMachineFactory.this.doTransition
449 (operand, currentState, eventType, event);
450 return currentState;
451 }
452 }
453
454 /**
455 * Generate a graph represents the state graph of this StateMachine
456 * @param name graph name
457 * @return Graph object generated
458 */
459 @SuppressWarnings("rawtypes")
460 public Graph generateStateGraph(String name) {
461 maybeMakeStateMachineTable();
462 Graph g = new Graph(name);
463 for (STATE startState : stateMachineTable.keySet()) {
464 Map<EVENTTYPE, Transition<OPERAND, STATE, EVENTTYPE, EVENT>> transitions
465 = stateMachineTable.get(startState);
466 for (Entry<EVENTTYPE, Transition<OPERAND, STATE, EVENTTYPE, EVENT>> entry :
467 transitions.entrySet()) {
468 Transition<OPERAND, STATE, EVENTTYPE, EVENT> transition = entry.getValue();
469 if (transition instanceof StateMachineFactory.SingleInternalArc) {
470 StateMachineFactory.SingleInternalArc sa
471 = (StateMachineFactory.SingleInternalArc) transition;
472 Graph.Node fromNode = g.getNode(startState.toString());
473 Graph.Node toNode = g.getNode(sa.postState.toString());
474 fromNode.addEdge(toNode, entry.getKey().toString());
475 } else if (transition instanceof StateMachineFactory.MultipleInternalArc) {
476 StateMachineFactory.MultipleInternalArc ma
477 = (StateMachineFactory.MultipleInternalArc) transition;
478 Iterator iter = ma.validPostStates.iterator();
479 while (iter.hasNext()) {
480 Graph.Node fromNode = g.getNode(startState.toString());
481 Graph.Node toNode = g.getNode(iter.next().toString());
482 fromNode.addEdge(toNode, entry.getKey().toString());
483 }
484 }
485 }
486 }
487 return g;
488 }
489 }