How to Use Objects: Code and Concepts (2016)
Part III: Events
Chapter 10. State Machines
Professional developers strive to create software that is correct. It is not too hard for even the ambitious amateur to achieve satisfactory responses for the most common use cases of a system, but it takes a professional to arrive at software that behaves as expected in all possible circumstances. Design-by-contract
4 provides a solid reasoning framework for achieving this goal. Its cornerstone is the precise specification of single method calls, as shown in Fig. 10.1(a). In this model, some client accesses a service provider object. It passes arguments, obeying the method’s pre-condition. The service provider must then deliver the promised result, as specified in the method’s postcondition. Pre- and post-condition also capture the state of the service 4.1 provider before and after the call, respectively: Many operations are not invoked for their return value, but for their effect on the target object.
Figure 10.1 Correctness and Events
Events and inversion of control challenge the fundamental assumptions of this approach, as illustrated in Fig. 10.1(b). In this scenario, a method call is no longer a service request, and there is not even a client expecting a specific answer. Instead, a method call is a notification that a certain event has taken place and the event-listener object must react appropriately, without being guided by the caller’s expectations.
If contracts fail to capture the “appropriate reaction,” a new framework for reasoning about correctness has to be found. This chapter presents a common and well-studied approach: state machines. State machines perceive an object as being in one of a number of abstract states. Each incoming event can send the object to a different state and trigger the execution of some action. The overall state machine then expresses the desired behavior, by capturing the details of these individual reactions to single events. This seemingly simple approach underlies the immmensely successful field of model checking, without which many of today’s safety-critical software
64,165,120,219 systems could not have been built.
This chapter introduces the terminology and concepts of state machines as the core of the approach (Section 10.1), using the definitions of UML.
47 It then traces these concepts to examples from the Eclipse platform and introduces additional details (Section 10.2). Finally, it discusses three approaches to implementing state machines faithfully (Section 10.3). In this last step, it turns out that contracts remain indispensable for precise reasoning, even if they fail to capture the relationship between event-source and event-listener in Fig. 10.1(b).
Throughout the chapter, we will use state machines to describe individual 47,95 objects, in keeping with the subject of this book. In reality, they serve as a powerful tool at many levels of software design: They can capture the behavior of small embedded controllers and that of entire systems alike, and they cover implementation concerns and model-driven development as well as requirements analysis. We hope that the subsequent detailed treatment of their structure and meaning will give you the joy of discovering state machines hidden within many of your daily development tasks.
10.1 The Core: An Object’s State and Reactions
1.1Each object has a state, which (briefly put) is the sum of its fields’ current contents. The challenge addressed by finite state machines is that very often the reaction of an object to an event will depend on its state.
To illustrate, let us consider a button in a toolbar, called a tool item in SWT. The tool item’s reactions to mouse events are shown in Fig. 10.2. Since SWT treats widgets as black boxes and does not define the intermediate states, we borrow the terminology from Swing (see classButtonModel): (a) The tool item starts in an idle state, where it paints itself as a flat area. (b) When the mouse moves in, the tool item acknowledges this by showing a pressable surface in state rollover. (c) When the user presses the left mouse button, the tool item gets armed, which means that releasing the 7.1 button now will fire the clicked (in SWT, selected) notification. (d) When the mouse moves out while the mouse button remains down, the tool item becomes pressed. In this state, releasing the mouse button will not fire the clicked notification. (e) State pressed differs from being idle in that simply reentering makes the tool item armed again, without repressing the mouse button.
Figure 10.2 A Tool Items’s Behavior
Events are significant external occurrences that trigger reactions.
The central element of the current chapter is the passive nature of objects, as indicated in Fig. 10.1(b). An event is “something that happens” and 47 about which an object will be notified because it is relevant to the object. In the case of the tool item, the relevant occurrences, or events, are the mouse moves and clicks produced by the user.
Events are not always external occurrences. First, time events are generated just 47 198(§13.3.27) by elapsing of time, usually relative to entering the current state. Furthermore, the 198(§13.2) UML recognizes signals sent asynchronously by one object and received by another object, messages sent to an object to invoke a specific operation, and changes in state
1.4.1 that cause a condition (i.e., a Boolean-valued expression) to become true. The cases of signals and messages are especially interesting, because they enable links between the state machines of different objects: When receiving an event, an object can decide to send a signal or message to another object, thus stimulating that object’s state machine.
Finite state machines capture state-dependent behavior precisely.
Suppose you want to specify the tool item’s behavior precisely—for instance, to describe a programming job to a different team. The screenshots and a textual description may be sufficient to get the idea across, but they are hardly a sound basis for actual work.
Fig. 10.3 shows a finite state machine for the tool item, using the UML 47 notation. The rounded rectangles are the abstract states, or simply states, which represent the conceptual states from the above description. The interesting part is the object’s behavior, which is captured by thetransitions between those states, depicted as arrows. Each such transition is labeled with an event as its trigger: When the object is in the source state and the 198(§15.3.14) event occurs, then the transition is taken and the object ends up in the target state. One also says that the transition fires.
Figure 10.3 First Attempt at State Machine for a Tool Item
Let us align the drawing in Fig. 10.3 with the reactions from Fig. 10.2. Part (a) in Fig. 10.2 shows the idle state. After the mouse enters the button area, we reach state rollover in (b). When the left button is pressed down, the button is armed in (c). Moving the mouse in and out of the tool item switches between states armed and pressed in (d) and (e).
However, the state machine tells a more complete story, since the screenshots cannot show the internal state. For instance, what happens if a tool item is pressed and then the button is released—that is, if the event button up occurs? The screenshot does not change, but internally the tool item goes to state idle, as shown in Fig. 10.3. The state machine also clarifies that the only difference between states armed and idle consists of whether the mouse pointer is inside the tool item.
The machine’s states abstract over an object’s concrete field content.
The states in Fig. 10.3 derive from a previous textual description of a behavior. When read as specifications of a concrete object, their role is to arrive at a holistic understanding by suppressing the technical details of the object’s concrete fields.
47 198(§15.3.11)Toward that end, the UML understands a state as a point in time when an object waits for an event, when it performs an activity, or in general where some condition holds. The first point is the most prominent in the preceding example, as in many others: As long as no events arrive, the object just sits idle. Also, the “or” must be read inclusively: Frequently, an
10.2.2 object performing an activity waits for an event that aborts the activity, 4.1 and a specific assertion about the fields can be given that holds while the object is waiting for an event.
47Another way of looking at states is to say that they encode the past history of received events: Each event can potentially change the state, so that the event gets recorded in the new state. This view is helpful because very often some expected reaction depends on a sequence of events—for instance, if the user has to press a button, then select an item from a list, and finally confirm the selection by pressing another button. Each state then represents an intermediate step in such a sequence.
A States must have an inherent meaning.
One crucial point is that states are not simply summaries of technical field contents. States must have meanings in themselves to achieve the overall goal: to allow us to reason about the behavior expressed by the state
10.3 machine without having to go through the dreary details of a possible implementation.
Let us look again at the example in Fig. 10.3. The crucial insight of the state machine is that “pressing a button” is not quite as simple as that after all: Users should be given the chance to cancel the process after they see from the visual feedback that they are about to trigger the button’s action. The inherent meaning of the four states is clear: Idle means that nothing has happened and armed means that the button is ready to trigger its action. The other two states increase usability: Rollover indicates that the mouse cursor is inside the button area, which usually leads to somevisual feedback. Pressed is an extra state that enables users to reconsider their intentions—the button will not trigger an action, but the user also has the choice of going back to armed by moving the mouse cursor back inside.
Effects at transitions capture the object’s reactions.
So far, the example object’s description in Fig. 10.3 is rather uninteresting: The internal state of the tool item changes, but the item does not show any outward reaction. Of course, it may choose to paint itself differently on the screen, but the main reason for using tool items in the first place is not expressed: The item should notify listeners when the user clicks with the mouse.
This omission can be remedied easily, as illustrated in Fig. 10.4. As shown in the figure, the transition from armed to rollover on the mouse event button up not only changes the state, but also has the effect named fire, separated from the trigger by a slash. For now, we read fire as a call to the standard notification method from the OBSERVER pattern. 2.1
Figure 10.4 The Tool Item’s Observable Reaction
Effects always run to completion.
Events relevant to an object can conceptually occur at any time, or even all the time: While the user moves the mouse, a new event signals the new mouse position every few milliseconds. In physical reality, a new event may thus easily overlap with the processing of the previous one. As a result, a naive reading of state machines could lead to the same event handler code being executed concurrently for different events. 8
To obtain a simple explanation of a state machine’s behavior, the complexities of concurrency must be avoided. The UML therefore specifies that 8.2 effects always run to completion: Once an object has received an event, it performs the necessary processing, including any effects. The next event can be delivered to the object only after the previous one has been processed completely.
Run-to-completion is also the deeper reason behind SWT’s event queue and event 7.10.1 dispatch thread: Because the window system may detect events at any time, according to the user’s input, these events get queued before being delivered one-by-one to the application’s registered listeners.
Align the implementation with the state machine.
State machines are popular as tools for expressing specifications because 10.3 they can be aligned very closely with the implementation: Once the state machine is complete, it is a routine task to map it into concrete code implementing that specification. If the machine is sufficiently detailed, the code can even be generated automatically. Otherwise, one can think of encoding
10.3 states explicitly, either as enums or as objects in the STATE pattern.
10.3.2In the following, we will apply the most common approach. In this strategy, the abstract states remain implicit in the code, as they merely provide a particularly intuitive way of explaining the object’s concrete fields and their manipulation. We demonstrate the point and the close link between machine and code using a reimplementation of the tool item’s behavior in a CustomButton.
States map to configurations of the object’s fields.
We start by defining the object’s state. Any definition of an object’s fields must seek to simplify the internal algorithms. Fig. 10.3 provides a good hint: The arrows between the states nearly always come in symmetrical pairs. The reactions to the events therefore become simpler if each just has to toggle a switch: Is the mouse button currently down? Is the pointer inside the button? It also seems natural that being armed is special, because this state determines whether we fire an event to the listeners. We therefore introduce three corresponding fields:
custombutton.CustomButton
private boolean mouseDown;
private boolean mouseInside;
private boolean armed;
The connection between the abstract and the concrete states can then be charted (Fig. 10.5). Specifically, the object is idle if all flags are false; it is pressed if the mouse is down but the pointer has run outside; and so on.
Figure 10.5 Mapping Abstract States to Concrete States for the CustomButton
You will note immediately that the flag armed is really redundant: It is true exactly if mouseDown and mouseInside are both true. This could be expressed in a private method isArmed(). It is, of course, a matter of taste, but we feel that the methods’ code becomes more readable when the special case is made explicit. In general, introducing redundant fields should be avoided, because every developer working on the class must be aware of the redundancy and the class invariants relating the fields. 4.1
The mapping from Fig. 10.5 can be traced to the code. The painting method must necessarily interpret the concrete state as an abstract state—for instance, to choose the correct background color. As shown in the following code, we first use red for the special state armed, and then differentiate between rollover (yellow) and idle (green).
custombutton.CustomButton.paintControl
if (armed)
g.setBackground(getDisplay().getSystemColor(SWT.COLOR_RED));
else if (mouseInside)
g.setBackground(display.getSystemColor(SWT.COLOR_YELLOW));
else
g.setBackground(display.getSystemColor(SWT.COLOR_GREEN));
Events map to methods.
If the mouse events in Fig. 10.3 are relevant to the CustomButton, then the button must receive them. The standard way to achieve this is to have one method for each type of event and one method call for each event. The method is then responsible for implementing the appropriate reaction. As usual, we register a nested private listener for the raw SWT events and 2.1.3 delegate the calls to corresponding handle methods in the outer class.
custombutton.CustomButton
public class CustomButton extends Canvas {
. . .
protected void handleMouseDown() {
. . .
}
protected void handleMouseUp() {
. . .
}
protected void handleMouseEnter() {
. . .
}
protected void handleMouseExit() {
. . .
}
}
Let us look at a few of these methods. The central one is certainly handleMouseup(), because it includes the only externally visible reaction in the special state armed: When the event occurs in that state, the fire() method is invoked (lines 2–3). Otherwise, only the flags are updated to reflect the new information about the mouse (lines 4–5). Note that this update is independent of the current state because of the clever choice of fields. That is, regardless of whether the object is in state rollover or pressed, it will end up in state idle (according to the mapping fromFig. 10.5).
custombutton.CustomButton
1 protected void handleMouseUp() {
2 if (armed)
3 fire();
4 setMouseDown(false);
5 setArmed(false);
6 redraw();
7 }
Another crucial point is the notification that the mouse enters. That event must be reacted to in two states (Fig. 10.3): In state pressed, the mouse is known to be down, and so the button becomes armed (lines 2–3). In any case, we note that the mouse pointer is now inside (line 5). Note also how the code makes sense without knowing the state machine: We could read lines 2–3 as “If the mouse button is already pressed, then the CustomButton becomes armed immediately.”
custombutton.CustomButton
1 protected void handleMouseEnter() {
2 if (mouseDown) {
3 setArmed(true);
4 }
5 setMouseInside(true);
6 redraw();
7 }
These methods show that the implementation turns the intuitive reading of a state machine “inside-out”: The diagram is read and understood starting with the states, then going on to the transitions emerging from these states when triggered by certain events. The implementation, in contrast, starts from the incoming events, in the form of method calls, and then goes on 10.3.4 to differentiate between states within these methods. The STATE pattern remedies this mismatch, but at the cost of requiring some infrastructure.
State machines make the correctness of the code obvious.
The preceding code clearly reflects the state machine, and since the machine captures the button’s expected behavior, the code is correct. As a conceptual tool, the state machine structures the code with the goal of making its correctness obvious.
10.2In the inverse direction, it is often useful to explain the workings of existing code by overlaying it with a state machine. If one succeeds in constructing a machine that is implemented by the code, then one has gained a structure that explains the overall behavior at a glance.
State machines keep up a clean structure despite technical necessities.
Clearly, not all code can always be nice. Every framework and library that we use to get things done comes with its own technical details, obscurities, and idiosyncrasies. For instance, SWT has a slightly odd view on the mouseEnter and mouseExit events: When the user keeps a mouse button down while moving the pointer into and out of a widget, then the widget does not receive the events. The reason is that SWT stipulates that the widget will be tracking the mouse anyway during such drag gestures. This differs, for instance, from Swing’s view, where enter and exit do have the expected purely geometrical meaning even if a mouse button is being held down.
With state machines, the code can be kept in shape. The handle methods given earlier actually react to the conceptual events, as given in Fig. 10.3. In particular, enter/exit are read geometrically—even if we have not spelled this out, it follows from the discussion of Fig. 10.2. So far, it has been a coincidence that the conceptual events correspond one-to-one to SWT’s concrete events. The odd behavior about enter/exit now breaks the rule, but all we have to do is find SWT events that we can interpret as the corresponding conceptual events. The following method does just that: It tracks the mouse motion and computes explicitly whether the new position is inside the widget.
custombutton.CustomButton.mouseMove
public void mouseMove(MouseEvent e) {
boolean newInside = getClientArea().contains(e.x, e.y);
if (mouseInside != newInside) {
if (newInside)
handleMouseEnter();
else
handleMouseExit();
}
}
As a result, the technical obscurity is confined to this single method, while the state machine enforces a clear structure on the greater part of the class’s code. What is more, that code is still seen to be correct by its close correspondence with the state machine.
Guards capture side-conditions on reactions.
Suppose that the CustomButton is frequently used to initiate dangerous tasks, so that under some circumstances, it must be “secured.” A secured button must be sure never to notify its listeners and should not go to state armed.
Guards are Boolean conditions that enable or prevent a transition from 47 being taken. They are noted in square brackets after the trigger of the transition. Fig. 10.6 gives the current example: The crucial transitions between rollover and armed are now guarded by a flag secured. Guards are evaluated whenever the trigger of the transition occurs. If they yield true at this point, then the transition fires.
Figure 10.6 Securing the Custom Button with Guards
Guards can also be used to select one of several transitions triggered by the same event. As long as the guards are mututally exclusive (i.e., at most one can ever return true in any possible state of the object), the state machine still has a well-defined, deterministic meaning. In Fig. 10.6, the transition from armed to rollover must, of course, be made even if the button is secured; however, it must not notify the listeners. The transition from rollover to armed, in contrast, does not have to occur at all if the button is secured—the event is just ignored.
Instead of modeling “being secured” as a side-condition to reactions, one might introduce it as a separate state secured. The other state, ready, contains the machine 10.2.3 from Fig. 10.3 as a nested state machine. New events secure and unsecure trigger the transitions between these states.
The implementation of guards is straightforward: After it has been determined which transition is about to fire, one checks the guard. For instance, here is the handling of the mouseUp event in state armed; the fall-through branch switches to state rollover, as before.
custombutton.CustomButton
protected void handleMouseUp() {
if (armed)
if (!secured)
fire();
setMouseDown(false);
setArmed(false);
redraw();
}
State machines are precise, but real applications require more elements.
This section has undertaken a brief survey of the central elements of state machines and their meaning: Abstract states characterize points in an object’s lifetime, events are occurrences that objects must react to passively, and transitions describe these reactions through effects, possibly using guards to constrain the behavior. Throughout, we have emphasized the connection of state machines and concrete code, which enables state machines to serve as detailed specifications of the expected behavior.
While these elements are useful and expressive, real-world situations require more detail. Notably, objects may perform ongoing activities while they are in a given state, or the behavior in that state may be specified further by nested state machines; it is also useful to execute effects whenever a state is entered or left. These elements can be understood as extensions of the basic model given here, and we introduce them in the next section.
10.2 State Machines in Real-World Scenarios
The key idea underlying state machines is rather straightforward and we have been able to apply it to the example of a button widget directly. Almost any practical example will, however, require more detailed specifications of the expected behavior. A major strength of UML is that it is a language made by practitioners for practioners. In turn, understanding its more advanced elements also means understanding how to cover more advanced examples. This section traces more elements through concrete examples from the Eclipse platform.
10.2.1 Additional Fundamental Elements
State machines are so successful as tools because most objects have state and many objects exihibit different reactions based on that state. Here is a simple example, the ContentProposalAdapter from the JFace framework. 9.3 Fig. 10.7 shows a typical interaction sequence.
(a) We are about to enter “United States” as a country name.
(b) After pressing the pop-up trigger Ctrl-Space, we can select from a given list.
(c) Once the pop-up is shown, we can navigate within the list using the cursor up/down keys. Note that the keyboard focus remains within the text field, so the navigation is a feature of the ContentProposal Adapter and not built into the list. As we go on editing the text, the completion proposals are updated. However, when we press Esc, the pop-up is closed.
(d) Alternatively, we can press “tab” to switch the keyboard focus to the list (but we cannot return by a second “tab”).
(e) Finally, whenever we choose a proposal, it replaces the current text. This result is, in fact, independent of whether we have pressed Enter in the text field (c) or in the list (d).
Figure 10.7 Auto-completion in JFace
State machines help in understanding existing code.
The class ContentProposalAdapter implements this behavior in about 2200 lines of code, with different listeners attached to different widgets. To get an overview, we summarize the specification in a state machine (Fig. 10.8). The machine distinguishes the different states of the pop-up window and a state where the target text field has been disposed. The transitions express the processing of user input: Pressing “enter” while the pop-up is open means accepting the proposal, pressing “tab” focuses the pop-up, and so on. The remaining new elements of the diagram will be discussed subsequently.
Figure 10.8 State Machine for JFace Auto-completion
For the sake of simplicity, we have left out several details. For instance, the pop-up can be activated automatically when specific characters occur in the input. The important point is that the given machine captures the overall code structure and that the remaining details can be filled in appropriately.
Internal transitions trigger effects without leaving the current state.
The first extension to the notation is straightforward and already covers most of Fig. 10.8. Internal transitions take place within a state—that is, without leaving the state. They are written down within the state. In the example, state pop-up open handles key strokes in this way: While the pop-up remains open, the user can select a proposal; when the text to be completed changes, the proposals are updated. Internal transitions are full transitions in that they can also have guards, and different transitions triggered by the same event can be distinguished by mutually exclusive guards.
Enter and exit effects capture consistent actions conveniently.
The next new elements are enter and exit effects. Very often, some effect has to be executed whenever a state is entered or left. To avoid explicitly recording these effects at all incoming and outgoing transitions, they can be specified once in the state itself. For instance, when entering pop-up closed, the object will close the pop-up window if necessary. Likewise, when entering pop-up open, the pop-up window is created if necessary. The example does not contain exit effects; they are written analogously.
Enter and exit effects are written the same way as internal transitions are, such 198 that enter and exit appear as special types of events. Their meanings are, however, quite different, and the UML distinguishes between an internal activities compartment for entry, exit, anddo activities, and an internal transition compartment containing the 10.2.2 transitions.
Well-written code naturally resembles a mapping of a state machine.
To show how the state machine structures the code, let us first consider the question of how the ContentProposalAdapter can receive the necessary events. Clearly, it must attach a listener to the target text field somewhere. Indeed, we find the following code, which covers most events in Fig. 10.8 through a listener for keystrokes and text changes. The omitted part is rather lengthy, consisting of approximately 100 lines. The state machine helps us in understanding the overall code because we know that these 100 lines will contain the details of the transitions, and we can skip them for now.
org.eclipse.jface.fieldassist.ContentProposalAdapter
private void addControlListener(Control control) {
controlListener = new Listener() {
. . .
};
control.addListener(SWT.KeyDown, controlListener);
control.addListener(SWT.Modify, controlListener);
}
The remaining events concern default selection events (i.e., the double-clicks) on the list of propsals. These are not delivered to the listener given in the preceding snippet, so we search on through the code. Sure enough, we find the corresponding listener, complete with the expected event handler, in the code creating the pop-up:
org.eclipse.jface.fieldassist.ContentProposalAdapter
proposalTable = new Table(parent, SWT.H_SCROLL | SWT.V_SCROLL);
setProposals(filterProposals(proposals, filterText));
proposalTable.setHeaderVisible(false);
proposalTable.addSelectionListener(new SelectionListener() {
. . .
public void widgetDefaultSelected(SelectionEvent e) {
acceptCurrentProposal();
}
});
Let us now trace a few of the transitions. Most are associated with keystrokes, so their code will be found in the handleEvent method of the controlListener introduced earlier. The next code snippet, as usual, turns the state machine “inside-out,” so the case distinction is first on the 10.1 event, then on the state. We see that the state pop-up open is associated 10.3.2 with the condition popup!=null (lines 4–7; no key events will be delivered if the state is actually pop-up focused, because then the keyboard focus is on the proposal table). State pop-up closed has only one outgoing transition (lines 8–16), so the code checks whether the event completionTrigger has occurred. More concretely, this means that the key combination Ctrl-Space for opening the pop-up has been pressed. If so, method openProposalPopup() creates the pop-up and finishes processing. (Setting field doit to false indicates that the event has been accepted.)
org.eclipse.jface.fieldassist.ContentProposalAdapter
1 public void handleEvent(Event e) {
2 switch (e.type) {
3 case SWT.KeyDown:
4 if (popup != null) {
5 . . . state 'pop-up open'
6 return;
7 }
8 if (triggerKeyStroke != null) {
9 if (
10 . . . keystroke is completion trigger
11 ) {
12 e.doit = false;
13 openProposalPopup(false);
14 return;
15 }
16 }
17 break;
18 . . .
19 }
20 }
The openProposalPopup() method corresponds to the ensurePopupOpen entry effect of state pop-up opened in Fig. 10.8: It does nothing if the pop-up already exists. Lines 7–12 show an interesting detail: To ensure that popup!=null is exactly the case if the pop-up exists, the code observes the closing of the pop-up shell and sets popup=null in this event.
org.eclipse.jface.fieldassist.ContentProposalAdapter
1 private void openProposalPopup(boolean autoActivated) {
2 if (popup == null) {
3 IContentProposal[] proposals = getProposals();
4 if (proposals.length > 0) {
5 popup = new ContentProposalPopup(null, proposals);
6 popup.open();
7 popup.getShell().addDisposeListener(
8 new DisposeListener() {
9 public void widgetDisposed(DisposeEvent event) {
10 popup = null;
11 }
12 });
13 . . .
14 }
15 }
16 }
Looking back on the previous two snippets, the condition on popup being null or not null clearly links to whether the pop-up is currently showing on the screen. Such a 4.1 link is a typical class invariant:
(popup==null ∧ no pop-up showing) ∨ (popup!=null ∧ pop-up is showing)
We 10.3.2 will come back to this insight later on.
State machines offer structure for the bumpy parts of the code.
It would seem at first that the controlListener described earlier is responsible for handling all events occurring on the text field. However, this is not the case. On closer inspection of the handleEvent() method, incoming events in state pop-up open are delegated to aTargetControlListener. The method getTargetControlListener() creates an instance on the fly if necessary.
org.eclipse.jface.fieldassist.ContentProposalAdapter
if (popup != null) {
popup.getTargetControlListener().handleEvent(e);
return;
}
This delegation may be slightly unexpected from the point of view of event handling, but it is a standard coding idiom to encapsulate more complex 1.8.6 algorithms into separate objects. The state machine from Fig. 10.8 ensures that we do not miss the bigger picture: The cases shown in the next code snippet correspond directly to transitions, both normal and internal from Fig. 10.8: keyUp moves the selection in the table, keyCR accepts the current proposal (if valid), and keyTab switches the focus to the completion list.
org.eclipse.jface.fieldassist.ContentProposalAdapter
private final class TargetControlListener implements Listener {
public void handleEvent(Event e) {
char key = e.character;
. . .
if (key == 0) {
int newSelection = proposalTable.getSelectionIndex();
switch (e.keyCode) {
case SWT.ARROW_UP:
newSelection -= 1;
if (newSelection < 0) {
newSelection = proposalTable.getItemCount() - 1;
}
break;
. . .
}
if (newSelection >= 0) {
selectProposal(newSelection);
}
return;
}
switch (key) {
case SWT.CR:
e.doit = false;
Object p = getSelectedProposal();
if (p != null) {
acceptCurrentProposal();
} else {
close();
}
break;
case SWT.TAB:
e.doit = false;
getShell().setFocus();
return;
. . .
}
}
Self-transitions briefly leave and reenter the current state.
Internal transitions, as discussed earlier, execute some effect without changing the current state. In particular, they do not execute the enter and exit effects. Self-transitions, in contrast, do leave the state briefly and the corresponding effects do occur. In Fig. 10.9, when the object receives evente, effects a, b, and c are executed, in that order.
Figure 10.9 Self-Transition in a State Machine
Initial and final states delineate the state machine’s processing.
This point explains the processing of events in Fig. 10.8 and links it to the actual code. The overall machine has two more new elements, an initial state and a final state. The initial state, depicted as a filled black circle, designates the starting point of processing. The object starts its lifetime in the initial state. The final state, depicted as a circle with an inner filled circle, designates the end of the object’s life cycle. The object cannot leave the final state.
198(§15.3.8)The initial state is only a pseudostate, because the object cannot remain in that state, but must go to some normal state immediately, without waiting for an event. In the example, this transition goes to pop-up closed, because initially there will be no pop-up.
An initial state can be left by several alternative transitions as long as their guards are mutually exclusive, i.e. as long as the state machine remains deterministic.
Completion transitions fire when the state finishes its processing.
Transitions without events can occur at points other than the initial state. Such transitions are called completion transitions, because they fire as soon as their source state finishes processing and is therefore “ready to be left.” 10.2.2 The processing can consist of some ongoing activity, or can be specified 10.2.3 198 more precisely by a nested state machine. The UML fits completion transitions uniformly into the framework by introducing an implicit completion event, which occurs whenever the processing in a state finishes. Completion transitions are then just normal transitions triggered by a special event.
As a special case, if a state does not do internal processing, the completion event occurs as soon as the state has been entered—the object just passes through the state. Since completion transitions can have guards and effects, this construction can be useful for expressing sequential case distinctions with corresponding actions. In the example of Fig. 10.8, whenever the text field is disposed (event ctrlDisposed), the ContentProposalAdapter ends its life cycle. It briefly enters state text disposed, only to leave it immediately to dispose of any open dialog. The corresponding code was shown earlier in the method openProposalPopup().
10.2.2 Ongoing Activities
Sometimes, jobs just take longer: because they involve complex algorithms, because they sift through a lot of data, or because they require access to slow media, such as the Internet. In the context of user interfaces, these jobs have to run in the background—that is, outside the user interface’s 7.10 normal event dispatch thread. This is not all, however: The user interface code must also manage them. State machines can help here, by introducing special states where jobs get executed; they explain what will happen after a job finishes and in which cases it will be aborted.
For a real-world example, let us analyze the class FilteredItems SelectionDialog from the Eclipse platform. This class forms the reusable basis for various standard dialogs such as Open Type and Open Resource. The key challenge with these dialogs is that they have to filter a rather extensive set of possible items according to the user’s current search expression. Since the search involves wildcards, prefixes, CamelCase support, and other possibilities, one cannot build a special index that filters items quickly enough to do everything in the event dispatch thread. The simple solution of installing a suitable ViewerFilter into a TableViewer does 9.3.1 not work out.
Instead, FilteredItemsSelectionDialog filters the items in the background and places them into a special ContentProvider. The actual filtering is, of course, specific to the type of objects being handled, such as Java types or Eclipse resources. It is therefore delegated to a subclass, in the manner of TEMPLATE METHOD (the AbstractContentProvider exposes 1.4.9 a single method add() for reporting a found element; it is therefore a client-specific interface). 3.2.2
org.eclipse.ui.dialogs.FilteredItemsSelectionDialog
protected abstract void fillContentProvider(
AbstractContentProvider contentProvider,
ItemsFilter itemsFilter,
IProgressMonitor progressMonitor) throws CoreException;
Even without the timing issues, filtering and sorting would have to be handled by the dialog. As a further precaution to avoid swamping the event thread, the table viewer is created with flag SWT.VIRTUAL, so that only those items actually displayed on the screen get filled with text and icons. For obvious reasons, JFace viewers do not support filtering and sorting in conjunction with SWT.VIRTUAL.
The handling of the filtering and sorting is somewhat complex, because it has to cover various application scenarios encountered in the subclasses. Fig. 10.10 gives an overview. Whenever the search pattern is modified, the display is updated in four stages; the first three fill the content provider, while the last one refreshing UI displays the collected items. That last step is also the simplest: The state machine is drawn from the perspective of the user interface, assuming execution in the event dispatch thread. Refreshing the UI therefore blocks the processing, so that we can use a simple enter effect to execute the desired update. The details can be found in the nested class RefreshJob.
Figure 10.10 Example of Do Activities
Do activities are long-running, interruptable operations.
The first three states contain the new point of the current section: Their purpose 10.2.1 is to execute a do activity, shown in the internal activities compartment 47,198 of the state after reserved name do. A do activity is a long-running operation that can be interrupted by incoming events. It is long-running in the sense that unlike effects, it does not have to run to completion before the machine can go on processing events—that is, it does not have run-to-completion semantics.
In the example, each state is characterized by the condition that the filterHistoryJob, filterJob, or refreshCacheJob, respectively, is scheduled or running. All of these activities are implemented in nested 7.10.2 classes derived from Job.
But let us trace the progress through the state machine step by step to understand how do activities and event processing interact. Initially, a change of the search pattern triggers the whole process. The event handler method delegates immediately to applyFiler().
org.eclipse.ui.dialogs.FilteredItemsSelectionDialog
pattern.addModifyListener(new ModifyListener() {
public void modifyText(ModifyEvent e) {
applyFilter();
}
});
The method applyFilter() is also invoked at other points, such as when the dialog is restored with the previously used pattern. This behavior could have been captured using an initial state and a state initializing dialog.
Applying a filter then starts up the state machine. It is the central event-processing method. In Fig. 10.10 the current state is left whenever the user modifies the search pattern. In the code, the intermediate jobs are canceled (lines 3–4). This cancellation accomplishes two things at once: It interrupts any ongoing do activities according to the UML semantics and switches the state. Then, to enter state filtering selection history and start its do activity, the corresponding job is started (line 7).
org.eclipse.ui.dialogs.FilteredItemsSelectionDialog
1 protected void applyFilter() {
2 ItemsFilter newFilter = createFilter();
3 filterHistoryJob.cancel();
4 filterJob.cancel();
5 this.filter = newFilter;
6 if (this.filter != null) {
7 filterHistoryJob.schedule();
8 }
9 }
This implementation deviates slightly from the pure UML semantics. Specifically, a call to Job.cancel() does not stop the job immediately. Instead, it sends a signal to 8.3 the job, as a polite request to stop executing whenever convenient. A precise rendering would therefore have to wait for the job to actually finish before going on, using an IJobChangeListener. For the purpose of the dialog, it is sufficient that the next job is not started.
The remaining states are then arranged in a pipeline, linked by completion transitions. According to the meaning of completion transitions, the current state is left as soon as its processing has finished. For instance, the FilterHistoryJob effects the state change by scheduling the next job. The remaining steps are very similar and we do not show them here.
org.eclipse.ui.dialogs.FilteredItemsSelectionDialog.FilterHistoryJob
private class FilterHistoryJob extends Job {
private ItemsFilter itemsFilter;
. . .
protected IStatus run(IProgressMonitor monitor) {
. . . perform the actual filtering
filterJob.schedule();
return Status.OK_STATUS;
}
}
In summary, do activities embed long-running operations into the context of state machines. Conversely, state machines provide a conceptual framework for understanding and managing long-running operations.
10.2.3 Nested State Machines
A natural description of an object’s behavior often requires phrases involving “while.” Here are some examples: “While the ATM holds onto the credit card, it accepts requests from the customer.” Or: “While the browser is downloading a file, it repeatly stores the received data to disk.” Some of 10.2.2 such scenarios can be captured as do activities, but very often, this is too imprecise: Do activities are essentially opaque, black-box building blocks without inner structure. In other words, the framework of state machines cannot be used to specify them. In the two examples cited here, the handling of customer requests certainly involves several steps of selection, data entry, server communication, and so on. And even downloading a file can be split further into reading and interpreting the headers and perhaps opening a dialog box to ask for a file name. All of those can be explained as intermediate states.
Substates capture the behavior within a given state.
The UML introduces the concept of substates for expressing such behaviors. Each state can have nested substates, and these substates can be connected by transitions as usual. In effect, one can nest entire state machines within each state. A state that has substates is a composite state.
47Let us introduce the concepts using the standard example of the ATM (Fig. 10.11). The ATM has two overall states, idle and active. It switches to active once a card is inserted and back to idle whenever the user presses the abort button, the entered card is found to be invalid, or processing finishes normally. State active has several substates, which capture the user interaction with the ATM. On entry, the card data is read. The nested state machine first validates the card data, then offers a menu, requests additional data for the chosen option, and finally processes the completed request. In the end, it asks whether the user wishes to continue.
Figure 10.11 Example of Substates: ATM
While the meaning of the nested machine itself is straightforward, we have to take a closer look at the link between the substates and their surrounding states. First, and most obviously, entering the surrounding state through the transition on cardInserted starts the nested machine in its initial state. Conversely, the nested machine reaching its final state raises the 10.2.1 completion event for the outer state. Next, when the outer state is left using a usual transition, such as on event abort in the example, then the current substate is left as well. Finally, when a transition from a substate leaves the outer state, then the outer state is left as well. The example contains such a transition in the handling of invalid cards.
198(§15.3.11)As a result, transitions involving substates can always enter or leave several nested states at once. For each state entered or left, the corresponding entry or exit effect is executed. Fig. 10.12(a) illustrates this by an example. When the transition from M to N is taken, then the effects are executed in the order exitM, exitA, enterB, and enterN. It is also useful to visualize the hierarchical structure of states and substates as a tree [Fig. 10.12(b)]. Making a transition between two states or substates involves going upward through the levels toward a common ancestor state and then descending toward the target. Going upward through a state executes its exit effect; going downward executes the entry effects.
Figure 10.12 Entering and Exiting Substates
Orthogonal regions capture parallel and independent behavior.
Sometimes, an object must tackle several tasks at once, must keep track of the progress of independent processes, or simply comprises several independent aspects. The UML introduces orthogonal substates for such situations. 47 We will outline this concept only very briefly and encourage you to read up on the details and extensions if you need to apply it. Fig. 10.13 illustrates the idea. Within state A, the machine has to accomplish two things U and V, each of which is described by its own state machine. The machines are contained within two orthogonal regions, separated by a dashed line. The meaning is clear: The transitions in one machine do not influence those in the other machine; rather, each machine holds its own independent state.
Figure 10.13 Orthogonal Substates
Orthogonal substates make state machines much more expressive. Previously, a machine was always in a single state, possibly nested inside some containing states. Those states always formed a linear path in the tree shown in Fig. 10.12(b). The UML calls them active states. With orthogonal 198(§15.3.11) regions, several substates within a state can be active at the same time. As a result, the overall set of active states will itself form a tree, the state configuration. In this way, the states of the various aspects of an object can be described in very great detail.
Note, however, that orthogonal substates do not introduce concurrency. 8.1 Incoming events are still processed one-by-one, using run-to-completion semantics for effects.
10.3 Implementing Finite State Machines
We have introduced finite state machines as a framework for specifying the behavior of objects. The implementation of these objects was, however, independent of the state machines: It could have been written, or indeed had been written, without knowledge of the state machine, simply by following good coding practice. Now we will consider the case where the state machine specifying the desired behavior is given and the object has to be constructed. We start by examining a bit closer the approach followed so far: States remain implicit and are identified by conditions on the object’s natural fields. Then, we give two canonical renderings, one using enums for states and one using the STATE pattern. For simplicity, we will not deal with nested state machines. 10.2.3
10.3.1 Running Example: Line Editor
To enable a close comparison of the different techniques, we employ a small running example [Fig. 10.14(a)], where the user can edit a line by dragging its endpoints. The state machine is, of course, minimal [Fig. 10.14(b)]: The LineEditor object has to remember only whether the user is currently dragging a point. The transitions fire when the user presses or releases the first mouse button, dragging an endpoint only if the cursor was above it. The entry and exit effects on dragging concern the visual highlighting of the endpoint.
Figure 10.14 The Line Editor Example
3.1.4The three implementations are based on a superclass LineEditorBase. 7.8 It is a custom widget and provides a field line holding a Line object. The Line has two Point fields p1 and p2. The base class handles the complete rendering. It requires the subclass to communicate the currently dragged point through the method setDragIndicator().
linedit.base.LineEditorBase
protected void setDragIndicator(Point p) {
this.dragIndicator = p;
}
Subclasses can also use the method hit() to test whether a mouse event took place near a given endpoint, and the method clipLine() to ensure that the line remains within the widget’s screen area.
linedit.base.LineEditorBase
protected void clipLine()
protected boolean hit(MouseEvent e, Point p)
The overall shell in Fig. 10.14(a) then simply contains a LineEditor widget filling the entire client area.
10.3.2 States-as-Assertions
10.1 10.2In previous examples, we have linked the abstract states to the object’s concrete fields through “conditions” that the fields fulfill. For instance, the ContentProposalAdapter identified its states by checking the condition popup==null. We will now examine this approach further and give it a solid foundation by applying the established principles of design-by-contract. 4.1
Let us start with a natural implementation of a LineEditor. The central question is this: What does the object have to know to implement the behavior from Fig. 10.14(b)? Clearly, it must store the point being dragged, because otherwise it will not be able to modify it. In the statenormal, this dragged point is, of course, invalid, so we set it to null. As a minor 1.8.9 consideration, we must keep the offset from the mouse pointer to the original position of the endpoint for correct positioning of that endpoint.
linedit.inv.LineEditor
private Point draggedPoint;
private int dX, dY;
This detail is best explained by the code accessing the fields dX and dY. Whenever the mouse moves, the currently dragged point must move along. Moving the center of the draggedPoint to the exact mouse position is not sufficient: If the user clicks some distance away from the center of the handle, the next mouse motion would move the handle abruptly by that distance. The offset resolves this problem: The mouse cursor always keeps its original distance from the center of the handle.
linedit.inv.LineEditor.mouseMove
public void mouseMove(MouseEvent e) {
if (draggedPoint != null) {
draggedPoint.x = e.x + dX;
draggedPoint.y = e.y + dY;
clipLine();
redraw();
}
}
We will now implement the various features of the state machine. For each step, we will follow a developer’s intuition first. We will then continue to strengthen his foundation by relating it back to the conceptual framework of contracts. 4.1
Each abstract state is defined by an assertion about the object’s fields.
To argue that the implementation is correct, we have to relate it back to the state machine. As a first step, we have to identify the abstract state that the object is in. Fortunately, this can be done by checking rather simple conditions:
normal 
draggedPoint==null
dragging draggedPoint!=null
But now let us be more precise. A “condition on an object’s state” 4.1 is, of course, simply an assertion: It is a Boolean expression that can be tested for truth at specific points in time. It is easy to rephrase the loose correspondence given previously by defining assertions:
Pnormal = this.draggedPoint==null
Pdragging = this.draggedPoint!=null
We will summarize this approach by the term states-as-assertions: Each state is associated with a unique assertion.
The state assertions must be mutually exclusive.
Let us follow the thought of states-as-assertions one step further. One attraction of state machines is that the abstract states are disjoint; that is, the object is always in a single, well-defined abstract state. For this to be true, the assertions defining the abstract states must logically exclude one another, meaning no two of them must ever be true at the same time. In the current example, it is clear that
The proof is simply that one just expands the definitions here. Other cases, with more fields, may require a bit more thought. Also, with more than two states, we must check each pair of them separately.
For practioners, this requirement touches the core of understanding their objects: Objects very often take actions and decisions based on their fields’ state. If we do not have a clear grasp of the possible configurations, we will never be able to arrive at 208 consistent and complete case distinctions. Perlis has put this very succinctly: “Programmers are not to be measured by their ingenuity and their logic but by the completeness of their case analysis.”
It is a class invariant that one of the state assertions holds.
One point of state machines, then, is that the object is in at most one state at a time. A second, complementary requirement is that the object always is in one of the abstract states. In the current example, we must have that
However, unlike the statement (*) given earlier, this one will usually not be provable in itself. The current example is too simplistic to demonstrate this—the single field is either null or it is not. But it is sufficient to have 2.2.1 two fields. For instance, the CCombo implementation considered previously holds both a pop-up shell and a list contained in that shell. The widget has two states: In state open, both fields are not null; in state closed, both are null.
org.eclipse.swt.custom.CCombo
List list;
Shell popup;
However, there will always be brief periods of time when the one is null and the other is not, and during these intervals the object is not in a well-defined abstract state. For instance, when creating the pop-up window, the shell is necessarily created before the contained list widget:
org.eclipse.swt.custom.CCombo
void createPopup(String[] items, int selectionIndex) {
popup = new Shell (getShell (), SWT.NO_TRIM | SWT.ON_TOP);
. . .
list = new List (popup, listStyle);
. . .
}
The requirement that the object is always in one of the abstract states is therefore a statement about the object’s consistency when the object is not currently working—it is a class invariant. 4.1
The run-to-completion semantics of event processing at this point ties in with the proof obligations for class invariants. The event is delivered to the object via a public method. Any public method can assume that the invariant holds initially and it must 4.1 guarantee that the invariant holds at the end, when control returns to the caller. Since each event is processed to completion, the particular invariant given in (**) ensures that the object will again be in one of the abstract states afterward.
Temporary fields are linked to state assertions.
When using state machines to describe an object’s abstract behavior, it is typical that the abstraction does not cover all fields. In the example, the fields dX and dY contain additional data tied to the dragging state. In fact, they are temporary and their content is undefined or invalid in statenormal.
State machines provide a good handle on temporary fields. Such fields should, of course, be avoided in general. However, they do occur rather frequently in objects that essentially implement state machines. It is a good practice to reset temporary fields to special values when they become invalid when leaving a state. Object references, especially, should be set to null, because this enables the garbage collector to clean up the referenced object if it is not used elsewhere.
Event handlers change the state implicitly.
Once we have mapped states to assertions, we can map transitions to concrete code. The transition from normal to dragging is straightforward: The event becomes an event handler method, which starts out by determining 10.1 the current state (line 2). The coding is, again, “inside-out”: Reading the state machine goes from states to transitions and events; the code starts from the events and then distinguishes the states. Line 3 further checks that the left button is pressed, and lines 4 and 6 check the transition’s guard.
linedit.inv.LineEditor.mouseDown
1 public void mouseDown(MouseEvent e) {
2 if (draggedPoint == null) {
3 if (e.button == 1) {
4 if (hit(e, l.getP1()))
5 startDrag(l.getP1(), e);
6 else if (hit(e, l.getP2()))
7 startDrag(l.getP2(), e);
8 }
9 }
10 }
The actual state change of the transition is then accomplished implicitly: Because the object’s fields are modified, a different state assertion becomes true. The code exploits the symmetry between dragging the endpoints and calls a helper method startDrag(). That method switches the state (line 2) and executes the new state’s enter effect (line 3). Finally, it handles the detail of keeping the mouse pointer offset.
linedit.inv.LineEditor
1 private void startDrag(Point p, MouseEvent e) {
2 draggedPoint = p;
3 setDragIndicator(p);
4 dX = p.x - e.x;
5 dY = p.y - e.y;
6 }
Guards become if tests.
10.1The meaning of guards is linked to the occurrence of events: Whenever an event may trigger a transition, that transition’s guard is reevaluated. The code in the snippet implements this approach directly in the hit() test in lines 4 and 6, exploiting the symmetry between dragging either of the points.
Enter and exit effects are inlined.
Another detail of this code is worth noting: A state’s enter and exit effects ensure consistent behavior of the state machine. In other words, they are guaranteed to be executed regardless of how the state is entered or left. The code does not give the corresponding guarantees, so one has to be careful to inject the effects wherever the abstract state changes implicitly.
Factor changes of the abstract state into separate methods.
The startDrag() method has two merits beyond factoring out common code. First, the enter effect is sure to be executed in any case. Second, and more importantly, the method’s name indicates the change of abstract state, which otherwise is only implicit. A team member looking through the code can understand lines 5 and 7 of method mouseDown() immediately, without going through the definitions of the state assertions.
With these points in mind, we introduce a corresponding method for going back to the normal state—that is, for leaving the special dragging state. Again, the exit effect is included:
linedit.inv.LineEditor
protected void stopDrag() {
setDragIndicator(null);
dX = dY = -1;
draggedPoint = null;
}
In general, it may be important to execute the exit effect before changing the state, because the effect might rely on the temporary fields valid in the state. This is the conceptual reason why we have chosen to invoke the effect first in this method, even if the implementation ofsetDragIndicator() happens not to access dX and dY. We also set these fields to -1 to indicate that they are not valid.
With more than two states, a strict adherence to the proposed convention would require one enter method and one exit method per state. A transition then first leaves the source state and enters the target state. However, this coding idiom can easily clutter the code—and the goal of states-as-assertions, after all, is to let the state machine explain and structure the code while keeping it natural and readable at the same time. In most cases, longish methods with complex effects should be introduced, while simple state switches by setting single fields can be inlined.
Think about introducing methods for state assertions.
The assertions characterizing states remain implicit: One has to know them while writing and reading the code, but they do not occur in the code itself. There is, however, the chance that the code will become more readable if the states are made into concrete code elements as well—just introduce methods to execute the states’ assertions. In the examples, this leads to the following code:
linedit.inv.LineEditor.inNormal
private boolean inNormal() {
return draggedPoint == null;
}
private boolean inDragging() {
return draggedPoint != null;
}
The event handlers now reflect the state machine even more immediately. For instance, the code shown next can be read line-by-line to yield 10.1 exactly the meaning of the transition from normal to dragging: “If we are in state normal and the first button is pressed, check whether an endpoint is hit. If so, change to state dragging.”
linedit.inv.LineEditor
public void mouseDown(MouseEvent e) {
if (inNormal()) {
if (e.button == 1) {
if (hit(e, l.getP1()))
startDrag(l.getP1(), e);
else if (hit(e, l.getP2()))
startDrag(l.getP2(), e);
}
}
}
Again, these testing methods can have a downside. They may make the code more readable when looking at the state machine, but they may be artificial and meaningless for the developer who is not aware of the state machine. At the same time, the methods suggest to the informed reader that the code should be understood as an implementation of a state machine, so the educated maintenance programmer might start reconstructing the state machine on a whiteboard.
Implicit states enable you to take shortcuts.
Although usually the state machine will provide a consistent overview of a class, it can sometimes get in the way of obtaining clear and concise code. For instance, let us forget the state machine of LineEditor for a moment. We have introduced the field draggedPoint with the intention of having a handle on the point to be modified. With this understanding alone, the following code for event mouseUp() would be most readable, because it expresses a simple intuition: “Whenever the first button is released, stop dragging the point along.” To understand this code, there is no need to know about the state machine. Also, the intuition does not mention any state at all: Releasing the mouse button stops the dragging process, whether such a process is currently going on or not.
linedit.inv.LineEditor
public void mouseUp(MouseEvent e) {
if (e.button == 1) {
setDragIndicator(null);
draggedPoint = null;
redraw();
}
}
A similar case has been seen in the example CustomButton, where the 10.1 event handlers did not switch between states of the conceptual machine, but merely recorded the current state of the mouse button and whether the widget is armed.
custombutton.CustomButton
protected void handleMouseDown() {
setMouseDown(true);
setArmed(true);
redraw();
}
Both examples can be so concise because they exploit knowledge that is present at the implementation level but not in the abstract state machine. The mouseUp() method knew that there are only two states, and that it would not matter if field draggedPoint is set to null even if it was null before. The handleMouseDown() method exploits the symmetry in the transitions of the state machine.
States-as-assertions keep the code stand-alone.
As an overall summary, the main attraction of the states-as-assertions approach is that the state machine can serve to structure and to explain the code, but that it does not constrain the implementation: Special knowledge available at the implementation level can still be exploited and serves to keep the code natural, readable, and succinct.
As a further result, the code can still be understood without looking at the state machine. In practical development, this is often critical: The state machine might once have existed as a quick sketch on some long-erased white-board created during some long-forgotten team meeting. The code, however, lives on and needs to be maintained for years.
10.3.3 Explicit States
As a state machine gets complex, it becomes more and more important to match the code with the abstract view as closely as possible. Looking at some detail of the machine, the maintenance programmer will have to find the corresponding piece of code immediately and reliably. Toward that end, it can be useful to make the abstract state an explicit concrete field in the object.
For instance, the Graphical Editing Framework handles all user input 214 through tools, such as selection of drawing elements, creation of specific elements, and so on. The treatment of mouse and keyboard events here is often very intricate. In fact, many tools will define multistep interactions, such as when creating a new connection from some source to some target element in the drawing. The class AbstractTool therefore introduces an explicit field state, whose possible values are given by final static constants.
Making the state explicit places it at the center of reasoning.
In the example LineEditor, there are only two states. We encode them as enums to allow for switch statements while keeping the code type-safe. Besides this abstract state, the object also has to keep the draggedPoint 10.3.2 and offset (dX, dY) for the actual manipulation. The meaning of these fields is the same as before.
linedit.ids.LineEditor
private enum State { NORMAL, DRAGGING };
private State state;
private Point draggedPoint;
private int dX, dY;
The overall structure of the class is, of course, similar to the previous implementation: The object receives events, then makes a case distinction based on the state, and finally changes the state. The new point is the explicit switch statement on the current state.
linedit.ids.LineEditor.mouseDown
public void mouseDown(org.eclipse.swt.events.MouseEvent e) {
switch (getState()) {
case NORMAL:
if (e.button == 1) {
if (hit(e, l.getP1())) {
setState(State.DRAGGING);
initDraggedPoint(l.getP1(), e);
} else
. . . as before
}
break;
case DRAGGING:
break;
default:
throw new IllegalArgumentException();
}
}
The default clause is, of course, not strictly necessary, because we know that only the 1.5.4 two values of type State can ever occur. However, later extensions of the state space are simplified if new states without a corresponding handler are signaled immediately.
When ignoring the event in many states, use the fall-through semantics of the switch statement and place several cases directly behind each other, followed by a single break.
It is not always necessary to use a switch statement. GEF’s tools, for instance, employ a method isInState() with usual if statements for testing the state. Following is the example of the event handler for mouse moves from the default SelectionTool. The code then becomes similar to that found in the previous section with explicit state-checking methods.
org.eclipse.gef.tools.SelectionTool
protected boolean handleMove() {
. . .
if (isInState(STATE_INITIAL)) {
. . .
} else if (isInState(STATE_TRAVERSE_HANDLE)) {
. . .
}
. . .
}
Explicit states make the class structure more uniform.
The switch statement used in the example serves two purposes: It performs the case distinction step and at the same time ensures that the event is either handled or ignored in all possible states. This approach makes the format of the event-handling methods very uniform and predictable and helps the maintenance programmer in locating specific pieces of code.
Conversely, switches that ignore most of the states make the code almost unreadable, because they drown the really relevant bits in formal clutter. It is always possible to relegate these cases to the default clause, but this loses the automatic check for 1.5.4 completeness.
Explicit states require more class invariants.
One drawback of explicit states is that the object’s remaining fields must always be interpreted with respect to the abstract state. In the example, the field draggedPoint must be read only in state DRAGGING, because it is invalid otherwise. In the previous implementation, this connection was immediate without further reasoning, because the content of draggedPoint determined the abstract state.
Technically, the connection must be captured as a class invariant: “If 4.1 state==State.DRAGGING, then draggedPoint contains the target of the movement and dX and dY contain the offset.” This means, however, that both the original developer and the maintenance programmer must be aware of this invariant, so it must be documented somewhere.
The looser connection between explicit state and the object’s data can also be seen the following detail of the example code: Switching a state involves setting the state field and initializing the remaining fields. While it would be possible to extract these lines into a separate method, as is done for states-as-assertions, this would break the new focus on states and is usually avoided, for instance in GEF code.
linedit.ids.LineEditor.mouseDown
setState(State.DRAGGING);
initDraggedPoint(l.getP1(), e);
10.3.4 State Pattern
Both previous approaches to implementing state machines suffer from several drawbacks:
• Fields may be valid only temporarily, while the object is in specific states.
• 10.1Compared with the state machine, the code is structured inside-out; that is, the outer structure consists of event handler methods, which internally switch on the current abstract state.
• As a result, the behavior belonging to a state is scattered throughout the class.
• Furthermore, the necessary switch and if statements can quickly become hard to read.
• Extending the set of abstract states is very difficult, because one has to go through the entire class to adapt all case distinctions. Also, one must change the class invariant, which is always problematic.
100These challenges are addressed by the STATE pattern. Its main idea is illustrated in Fig. 10.15: An object context implements a state machine, but the resulting code suffers from one or more of the just-identified problems. It therefore creates internal concrete state objects, one for each abstract state, and keeps a reference to the current state object. Each state object includes all the relevant information: Its fields hold the temporary values and its event handler methods implement the transitions from that state. The outer context object delegates all received events to the current state object.
Figure 10.15 Idea Underlying the State Pattern
Pattern: State
To implement an object with complex state-dependent behavior, factor out the logic for each state into a separate concrete state object and let the main object delegate event handling to the current state object.
1. Define an abstract base class State that has one handler method for each expected event, as well as methods enter() and exit().
2. Give the context object a field curState.
3. Implement a state-switching method to set state.
4. Forward all incoming events to object state.
5. Implement the single states as subclasses of State.
STATE introduces an event-handling infrastructure.
The main point of the pattern is that the implementation of the concrete 100 event-handling code can rely on a solid infrastructure for event handling in general. Let us look at the steps one-by-one.
First, we introduce a base class of all possible states. States must be able to handle all incoming events. Also, states will be notified when they are entered and left.
linedit.state.LineEditor
private abstract class State {
public void enter() {}
public void exit() {}
public void mouseDown(MouseEvent e) {}
public void mouseUp(MouseEvent e) {}
public void mouseMove(MouseEvent e) {}
}
We use empty bodies rather than abstract methods because we expect many events to be simply ignored in many states.
Next, we keep the current state in a field:
linedit.state.LineEditor
private State state;
We finish the infrastructure with a method for switching the state. That method also notifies the old and new states that they have been left and entered, respectively. Note that this ensures that the enter and exit effects, coded in these methods, will be executed.
linedit.state.LineEditor
private void setState(State state) {
this.state.exit();
this.state = state;
this.state.enter();
}
10.2.3Nested state machines complicate the proper handling of exit and enter actions further (Fig. 10.12 on page 546). The infrastructure of the State pattern can easily cope with that complexity if the tree of possible states [Fig. 10.12(b)] is reified into an object structure.
The context object can then lie back: After providing the infrastructure, it merely forwards all incoming events to the current state. Here are two examples:
linedit.state.LineEditor
public void mouseDown(MouseEvent e) {
state.mouseDown(e);
}
public void mouseUp(MouseEvent e) {
state.mouseUp(e);
}
4.1Both setState() and the event handlers rely on the class invariant that state is 4.2.4 never null. This invariant is established in the constructor, as expected in design-by-contract:
linedit.state.LineEditor.LineEditor
state = new Initial();
state.enter();
Concrete state objects comprise all the logic for reacting in a given state.
State objects can now be self-contained definitions of the object’s behavior in a given state. First, they can contain any necessary temporary fields:
linedit.state.LineEditor
private class Dragging extends State {
private final int dX, dY;
private final Point p;
public Dragging(Point p, MouseEvent e) {
this.p = p;
dX = p.x - e.x;
dY = p.y - e.y;
}
. . .
}
We create a new instance for each state entered at runtime, in keeping with the fundamental assumption that objects are small and inexpensive entities. Alternatives 1.1 are discussed later.
Furthermore, the enter and exit effects from the state machine can now be rendered directly as methods:
linedit.state.LineEditor.Dragging
public void enter() {
setDragIndicator(p);
}
public void exit() {
setDragIndicator(null);
}
Finally, and most importantly, the state itself handles outgoing transitions. Note that the implementation is no longer “inside-out”: The logic for 10.1 identifying and firing transitions can start from the current state.
linedit.state.LineEditor.Dragging
public void mouseMove(MouseEvent e) {
p.x = e.x + dX;
p.y = e.y + dY;
clipLine();
redraw();
}
public void mouseUp(MouseEvent e) {
setState(new Initial());
redraw();
}
The other state Initial is much simpler: It waits for the user to press the mouse button near an endpoint of the line and then switches to state Dragging.
linedit.state.LineEditor
private class Initial extends State {
public void mouseDown(MouseEvent e) {
if (e.button == SWT.BUTTON1) {
if (hit(e, l.getP1()))
setState(new Dragging(l.getP1(), e));
else if (hit(e, l.getP2()))
setState(new Dragging(l.getP2(), e));
}
}
}
Keep preconstructed states for rapid switching.
For the small example with infrequent state changes, it was possible to 100 create a new object for the target state in every transition. If transitions are very frequent, the overhead of creating and garbage collecting the state objects can become an issue. In this case, one can spend a bit more memory and preconstruct one object for each state in a private field. The initializations 1.6.2 previously done in constructors then happen in life-cyle methods init().
Use static state objects if they do not have temporary fields.
100One optimization step further, if states do not have local, temporary data, they can be stored in static fields and shared by all instances of the context class. In this case, the context object has to be passed to every event handler method to enable the method to access the object’s data and 100 switch to different states. The result is similar to the FLYWEIGHT pattern, where shared objects are passed extrinsic state to each method invocation.
Think carefully before using the STATE pattern.
At first glance, the STATE pattern is the ideal solution to implementing state machines: The resulting object reflects the diagram directly, the logic does not have to be coded inside-out, the logic for each state is kept together in a single small class, and large and unreadable case distinctions are avoided. The set of states can even be extended later on, simply by adding new subclasses of State. This is particularly desirable if the requirements for the software are expected to change in the future.
However, the pattern also has a few drawbacks.
• It requires creating some infrastructure before starting on the first state. For small machines, this infrastructure dominates the actual logic.
• In many cases it is actually desirable to group the code by handled event, rather than by state; usual event-handling methods answer concisely the question “What happens if . . . ?”
• The structure of the class is far removed from a natural, naive implementation, so that understanding it will require reconstructing the state machine.
• Because event-handling logic is strictly distributed between the different states, it is not possible to exploit symmetries and commonalities directly. As a result, the code is likely to become more redundant.
In the end, as usual in software engineering, you will have to weigh the benefits against the liabilities for the concrete implementation task at hand.