Android State Machine Library

    In a "code surfing" within the AOSP WIFI subsystem, I found that there is a great and well developing state machine library working behind it. Although it is hidden by the build system so we can't use it from SDK, there are ways like my previous article to access them. This article shows a brief how-to due to lack of documentation of the library.

Introduction

    State machine plays an extremely important role in computer science. In short, the machine would stay in a specific state at any moment and transfer to another state if a particular condition is satisfied. There are also lots of variant like the most familiar, to college student who just finished the discrete math class, Finite State Machine, and another one which is used in this case, Hierarchy State Machine. As the name implies, there is a hierarchy structure among the states within the machine like the below diagram.

(Fig. 1)

State B1, B2 and B3 are the children of state B. These state still have the properties of normal state like transition among each other if certain condition happens, but the hierarchy relationship would make the execution logic a lot different which we'll see later.

Usage

    If you feel lazy to fetch the internal Java API of AOSP following the previous suggestion, here is a jar containing some internal classes which are mostly in com.android.* or com.google.* packages, state machine classes we are discussing are also in that. You had been warned that the jar was build from AOSP master branch which API level was about 21 then(Although I think the APIs within it are mostly platform-neutral).

    Classes we're going to use are StateMachine and State which live in the com.android.internal.util package within platform/framework/base repository. The truth is that there IS a simple documentation of the machine design embedded as code comment within the StateMachine source code. I had converted it to web page and you may read it from here. 

    First, we need to create states by extending State class.

class A extends State {
 @Override
 public void enter(){
  Log.d(TAG, "Enter state A");
 }

 @Override
 public boolean handleMessage(Message msg){
  boolean ret = NOT_HANDLED;
  switch(msg.what){
   case CMD1:
    sendMessage(mSM.obtainMessage(CMD2));
    ret = HANDLED;
    break;

   case CMD2:
    transitionTo(mStateB);
    ret = HANDLED;
    break;
  }

  return ret;
 }

 @Override
 public void exit(){
  Log.d(TAG, "Exit state A");
 }
}

Although the handleMessage method is not abstract, it must be implemented. Other like enter or exit are optional. The state machine is a Moore machine, that is, actions would be performed after migrating to the destination state instead of the transition process. The most powerful thing, in my opinion, is the message delivering mechanism which handleMessage is responsible for. In the above example, state A send CMD2 upon receiving the CMD1 message, and since we're still at state A, the CMD2 case would be triggered and migrate to state B. But what if we get messages neither CMD1 nor CMD2, that is, we're NOT_HANDLED ? Let's look at the below example and take Fig. 1 as design blueprint.

class B extends State {
 @Override
 public void enter(){
  Log.d(TAG, "Enter state B");
 }

 @Override
 public boolean handleMessage(Message msg){
  boolean ret = NOT_HANDLED;
  switch(msg.what){
   case CMD3:
    Log.d(TAG, "Get CMD3");
    ret = HANDLED;
    break;
  }

  return ret;
 }
}

class B1 extends State {
 @Override
 public void enter(){
  Log.d(TAG, "Enter state B1");
 }

 @Override
 public boolean handleMessage(Message msg){
  boolean ret = NOT_HANDLED;
  switch(msg.what){
   case CMD1:
    Log.d(TAG, "Get CMD1");
    ret = HANDLED;
    break;

   case CMD2:
    deferMessage(msg);
    transitionTo(mStateB2);
    ret = HANDLED;
    break;
  }

  return ret;
 }
}

If we send CMD3 when the machine is at state B1, since state B1 couldn't handle it, the machine would leave state B1 and deliver the message to B1's parent, state B. So the output after sending CMD3 would be "Enter state B" followed by "Get CMD3". Clever person like you must find out another interesting thing: deferMessage. The deferMessage would store the passed in message and send it to the next state after migrating. If there are multiple accumulate message, oldest one would deliver first and then so on.
    Finally, we need to add all the states to the machine and define the relations, still take Fig. 1 as structure blueprint.

mSM.addState(mStateA);
mSm.addState(mStateB);
 mSM.addState(mStateB1, mStateB);
 mSM.addState(mStateB2, mStateB);
 mSM.addState(mStateB3, mStateB);

mSM.setInitialState(mStateA);

    Now we're going to talk about the hierarchy design's affection on machine behavior. If the machine start from state B1, the execution flow actually won't execute from B1, instead, it would first pass through state B, and finally state B1. As a consequence, if the initial state is B3, the execution flow would be: B -> B1 -> B3. Same philosophy can be applied when we migrate from one "tree" to another "tree". That is, if we called transitionTo(mStateB2) when we're at state A, the flow after transition would still be: B -> B1 -> B2.

Summary

    I'm not an expert in discrete math, so I don't know the real theoretical advantage of hierarchy state machine. But in my opinion, as an developer, this sort of design pattern is suit for situation where we must do A before B. In another word, HSM makes guarantee on the processing order among some of the tasks. Thus, Android system use it on places like WIFI subsystem and some of the Bluetooth profile subsystems like A2DP.