State Machine Builder: Assembling the State Machine

To support asynchronous code, we must convert user expression trees into state machine representations that can suspend and resume operations.

Introduction

The StateMachineBuilder is responsible for assembling a state machine from the lowered expression nodes generated by the LoweringVisitor. This state machine manages transitions between states and ensures correct execution of asynchronous operations and control flow.

The purpose of this phase is to link the individual states generated during the lowering phase and build a fully functional state machine that can handle complex control flow and asynchronous operations.

1. Building the State Machine

What is being done?

The StateMachineBuilder assembles the state machine by linking together the states generated by the LoweringVisitor. The builder constructs the MoveNext method, which advances the state machine from one state to the next.

Problem

We need to manage complex control flow across multiple states, ensuring that the state machine can correctly transition from one state to another, especially in asynchronous operations.

Discussion

The StateMachineBuilder defines the base type for the state machine, which includes system fields (such as the state ID and task builder) and any hoisted variables. The MoveNext method is then constructed to handle the state transitions. This method ensures that execution advances correctly based on the current state of the machine.

Solution

The StateMachineBuilder constructs the MoveNext method to manage state transitions. By linking the states together and using system fields, the state machine can maintain the flow of execution across different states, preserving the integrity of the program’s logic.

2. Handling Incomplete Results

What is being done?

The state machine must handle scenarios where results are incomplete, such as when an asynchronous operation has not yet completed. This requires the state machine to pause execution and resume once the result is available.

Problem

Incomplete results, such as those from asynchronous operations, can cause the state machine to stall. We need to ensure that the machine can handle these situations without losing track of the program’s logic.

Discussion

The StateMachineBuilder ensures that the state machine can pause and wait for asynchronous operations to complete. The machine creates a state to handle the task’s completion and then resumes execution once the result is available. This ensures that incomplete results do not cause the state machine to fail.

Solution

By creating states to handle incomplete results, the state machine can pause and wait for the completion of tasks without losing the flow of execution. This allows asynchronous operations to be managed effectively within the state machine.

3. Optimizing States

What is being done?

The StateMachineBuilder optimizes state transitions by minimizing the number of unnecessary transitions and ensuring that the machine executes efficiently.

Problem

Unoptimized state transitions can lead to excessive overhead and slower execution times. We need to ensure that the state machine transitions efficiently between states.

Discussion

The StateMachineBuilder optimizes state transitions by reordering nodes and reducing unnecessary transitions. This ensures that the state machine runs efficiently, reducing the performance impact of transitioning between states.

The optimization process analyzing the default ‘fallthrough’ state transitions using a DFS search, and reorders the physical state order accordingly. This will arrange the greatest possible number of states, such that their transition targets are ordered immediately after them. In these cases we can eliminate the goto instructions, and allow code execution to ‘fall through’ to the next state (thereby saving unnecessary instructions).

Solution

By optimizing state transitions, the StateMachineBuilder ensures that the machine executes efficiently. This reduces the overhead associated with state transitions, leading to better performance.

4. Task Management

What is being done?

The state machine uses AsyncTaskMethodBuilder to manage task execution across states. This ensures that asynchronous operations are handled correctly and that the state machine can resume execution once the tasks are complete.

Problem

Managing tasks in a state machine can be complex due to the asynchronous nature of many operations. We need to ensure that tasks are managed correctly across different states.

Discussion

The StateMachineBuilder uses the AsyncTaskMethodBuilder to manage task execution within the state machine. This builder starts the state machine, manages its state, and ensures that the result is returned once the machine finishes executing. This builder is the same builder used by standard async methods in C#, allowing for consistent task management, and correct handling of asynchronous operations and capturing of the execution context.

Solution

By using the AsyncTaskMethodBuilder, the StateMachineBuilder manages task execution across states. This ensures that asynchronous operations are handled correctly, allowing the state machine to pause and resume execution as needed.

5. Example StateMachine: Building the MoveNext Expression

The MoveNext method is the core execution function of the state machine. It controls the state transitions, handles task completions, and manages exceptions. Below is a visualization of a generated MoveNext method.

Here is an example of a generated MoveNext (expressed as c# code):

var stateMachine = new RuntimeStateMachine(); 
    
stateMachine.SetMoveNext( (RuntimeStateMachineBase stateMachine) => 
{ 
    try 
    { 
        switch (stateMachine.__state<>) 
        { 
        case 0: 
            stateMachine.__state<> = -1; 
            goto ST_0002; 
            break;

        case 1:
            stateMachine.__state<> = -1;
            goto ST_0004;
            break;

        default:
            break;
        }

        ST_0000:
        stateMachine.x = 10;
        stateMachine.awaiter<0> = Task<VoidTaskResult>.GetAwaiter();

        if (!stateMachine.awaiter<0>.IsCompleted) {
            stateMachine.__state<> = 0;
            stateMachine.__builder<>.AwaitUnsafeOnCompleted(ref stateMachine.awaiter<0>, ref stateMachine);
            return;
        }

        goto ST_0002;

        ST_0001:
        stateMachine.x = stateMachine.x + 1;
        stateMachine.awaiter<1> = Task<VoidTaskResult>.GetAwaiter();

        if (!stateMachine.awaiter<1>.IsCompleted) {
            stateMachine.__state<> = 1;
            stateMachine.__builder<>.AwaitUnsafeOnCompleted(ref stateMachine.awaiter<1>, ref stateMachine);
            return;
        }

        goto ST_0004;

        ST_0002:
        stateMachine.awaiter<0>.GetResult();
        goto ST_0001;

        ST_0003:
        stateMachine.__finalResult<> = {
            AsyncBlockTests.AreEqual(11, stateMachine.x);
            stateMachine.x = stateMachine.x + 1;

            return AsyncBlockTests.AreEqual(12, stateMachine.x);
        };

        stateMachine.__state<> = -2;
        stateMachine.__builder<>.SetResult(stateMachine.__finalResult<>);
        goto ST_FINAL;

        ST_0004:
        stateMachine.awaiter<1>.GetResult();
        goto ST_0003;
    } 
    catch (Exception ex) 
    {
        stateMachine.__state<> = -2;
        stateMachine.__builder<>.SetException(ex);
        return;
    }

    ST_FINAL:
});

stateMachine.__builder<>.Start(ref stateMachine); 
return stateMachine.__builder<>.Task;

Breakdown

Breakdown of MoveNext

  • State Tracking: The __state<> field directs which block of code the method should jump to after an await completes. Different case blocks correspond to different states in the state machine.

  • Awaiter Management: Each TaskAwaiter (awaiter<0>, awaiter<1>) checks if the corresponding task has completed. If not, the state is updated, and execution is suspended using AwaitUnsafeOnCompleted. When the task completes, execution resumes at the corresponding state.

  • Goto Statements: The goto labels (e.g., ST_0001, ST_0002) handle jumping between different execution points in the state machine, simulating the flow of code that would normally occur after await.

  • Exception Handling: The try-catch block ensures that exceptions during the execution are caught, and the task is marked as faulted by calling SetException.

  • Task Completion: When the state machine reaches the final state (ST_0003), it calls SetResult to complete the task successfully. If an exception occurs, SetException is called instead, signaling task failure.

Conclusion

The StateMachineBuilder assembles a fully functional state machine from the lowered nodes generated by the LoweringVisitor. By transforming control flow constructs into state transitions and handling tasks using AsyncTaskMethodBuilder<TResult>, the builder creates an efficient runtime representation of the state machine. This process involves managing state transitions, hoisting variables across state boundaries, and handling exceptions to ensure correct task completion.