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
019package org.apache.hadoop.yarn.state;
020
021import java.util.EnumMap;
022import java.util.HashMap;
023import java.util.Iterator;
024import java.util.Map;
025import java.util.Map.Entry;
026import java.util.Set;
027import java.util.Stack;
028
029import org.apache.hadoop.classification.InterfaceAudience.Public;
030import 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
046final 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 InvalidStateTransitionException {
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 InvalidStateTransitionException(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 InvalidStateTransitionException {
385      STATE postState = hook.transition(operand, event);
386
387      if (!validPostStates.contains(postState)) {
388        throw new InvalidStateTransitionException(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 InvalidStateTransitionException  {
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}