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 }