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    }