Debug support for arbitrary state-machines

I mentioned here  that if your language compiles to IL, then you get free debugging support with Visual Studio (and other managed debuggers).
But what if you have an interpreter that can’t compile to IL? For example, suppose you load some state machine via an xml file, and then an interpreter reads in the xml file and “executes” the state machine from the xml.

In practice, if you try to debug that execution, you’ll end up debugging the actual guts of the xml interpreter. In contrast, it would be nice to debug that state machine at the xml source level. For example, it would be nice to be able to set breakpoints, use step-next, and set-ip all at the xml source.

In this entry, I’ll explain how you can add this sort of debugging support to an existing interpreter using VS 2005 (Whidbey) or any managed debugger with Just-My-Code (JMC) support.

10,000 foot overview:
First, we recognize that the problem with debugging the state-machine source file is that most debug support is code-centric; whereas state-machines are data centric. We overcome this by employing a technique to convert the data-centric model into a code-centric one, and then leveraging existing code-centric debugging techniques. We then mark the actual interpreter as not-my-code while leaving the code associated with the state-machine data as user-code.  We then use JMC to debug just the user-code and thus only debug the state-machine data and not the actual state-machine engine.

Drilling into the details of the state-machine:
Here are the givens:
1) The states are generated from source file.
2) There are a finite set of states (this is reasonable since there are a finite set of characters in the source file).

Say we have a typical table driven state machine implemented like this:
     while(idxCurrent != -1) {
DoAction() // do whatever action is associated with this state
idxCurrent = NextState();
}
Where idxCurrent is the index of the current state.

In the implementation above, all states map to the same source line. This makes sense because the state is determined by the value of idxCurrent (data) and not the current source line (code).

To make it debuggable, we want to map each state back to a given source-line. We can do this by having little snippets of code (“islands”) for each different state. Imagine this:

     while(idxCurrent != -1) {
        DoActionWithDebugHook()
        idxCurrent = NextState();
    }

    void DoActionWithDebugHook() {
        switch(idxCurrent) {
        case 0:
            #line // map this entire case statement to source line from State 0
            idxCurrent = 0;
            DoAction();
            Return;
        case 1:
            #line // map this entire case statement to source line from State 0
            idxCurrent = 1;
            DoAction();
            Return;
        // repeat case statement for each unique State
        }
    }

Now each state gets has its own unique source-line. Each case statement is an “island” that can be uniquely mapped back to source for that state.
Here’s how the various debugging features now work:

Breakpoints
The #line directives can map each call to DoAction() back to the state-machine’s source-line for that state. If you place a breakpoint at the source-line, it will get bound to the appropriate case-statement, and the interpreter will actually hit the breakpoint right before it executes that state. The #line directives will also cause a debugger to show the state-machine’s source-line instead of the interpreter’s actual source-line. Thus an end user will appear to be debugging the actual state-machine and not just the interpreter.

Set Next Statement:
This model also works with set-next-statement because all the islands are within a single function. If you set-next-statement to a given state, the assignment lines “idxCurrent = n” will update the state index to the state you just set to. For example, suppose you hit a breakpoint in state 1, and so idxCurrent = 1. No you set-next-statement to state 0 (which can all be done at the state-machine’s source-level). When you continue to run, you’ll immediately execute the “idxCurrent = 0”, which will properly adjust the state before calling DoAction().

Stepping:
In order to step through the state-machine’s source, we want to be able to step from island to island and skip everything else. This is exactly what Just-My-Code  stepping is for. We mark the actual interpreter as “not-my-code” (or “non-user code”) and the islands are marked as “user-code”. Furthermore, we can use 0xFeeFee sequence points to mark regions within user-functions (like DoActionWithDebugHook) as hidden such that steppers will skip past them. Thus now that a stepper can skip everything outside the immediate islands, stepping will naturally work from island to island. And that will simulate stepping from state to state.

Virtual Locals and callstacks:
If the state machine has its own set of locals or a callstack (imagine a parser with a reduction stack), we can provide debug support for those too. Just add a single local variable of type System.Object to the debug hook function and call it something like “locals”. The interpreter can set it to point to any data structure that represents the state-machine source-level locals for the given state. That “locals” variable will show up in a debugger’s locals window, and when expanded, will then show the state-machine locals. Recall that the debugger can safely view the derived type of an object.

Simplified Example
Here’s a simplified example that demonstrates stepping between islands: [update: I've updated the example to also demonstrate "virtual" local variables for the states]
This mocks a simple 2 state FSA. State 1 prints "One", and has 2 local variables (integers x and y). State 2 prints "Two" and has a single local variable (a string).

 class Program
{
    // Each state can have its own set of variables.
    class State1Vars
    {
        public int x = 3;
        public int y =4;
    };
    class State2Vars
    {
        public string s = "I'm in state 2";
    }

    // Allocate space for the vars. 
    static State1Vars vars1 = new State1Vars();
    static State2Vars vars2 = new State2Vars();

    [System.Diagnostics.DebuggerNonUserCode]
    public static void Main()
    {
        Hooks(1);
        Hooks(2);        
    }

    static void Hooks(int state)
#line hidden
    {
        object locals = null; // represents vars for the current state.
        switch (state)
        {
            case 1:
                locals = vars1;
#line default
                System.Console.WriteLine("One");
#line hidden
                return;
            case 2:
                locals = vars2;
#line default
                System.Console.WriteLine("Two");
#line hidden
                return;
        }
#line hidden
    }
} // end class

Create a console C# app in VS 2005, paste in the code above, and try it out to get a feel for it. When you're stopped at the states, the local variable "local" will refer to a class containing the virtual local sfor that state. Depending on the debugger, you may have to expand "locals", to see its fields.

Putting it all together.
The remaining piece is to dynamically generate the debug hook function containing the islands based off the state. This can be done via reflection-emit at the time the state-machine is originally loaded.

Alternate designs
This may sound like a lot of work just to “trick” the debugger into showing the proper source-line. It does have the advantage that it uses common building blocks (such as 0xFeeFee sequence points, and JMC) so that it could work with most high-level debuggers. It also provides a single unified model to debug both the state-machine (user-code) and the actual interpreter (non-user code).

However, an alternative approach could be to write a debugger specific extension that takes advantage of that debugger’s specific extensibility model. For example, if a debugger has extensibility hooks that let an extension inject “virtual frames” into the callstack, then the extension could just inspect the debuggee to determine the current state, and then inject a virtual frame into the debugger’s callstack for the debuggee. This would require considerably less debug support within the debuggee (you wouldn’t need the debug hooks), but it would require an extensible debugger.

[Update] I have some sample code in zip file up here. textfile2.txt is the pseudo-source for the state machine. program.cs is the interpreter. It has a hardcoded table-based state machine corresponding to textfile2.txt, and then uses reflection-emit to build the island. The sample supports breakpoints, stepping, and set-ip.

What's next?
Every state-machine and interpreter is different, so some cleverness may be needed to apply these techniques to a given implementation.
I'd also like to cobble together an example that shows source-level debugging an xml interpreter, since I believe that may have wide application.

Comments

• Anonymous
  July 26, 2005
  This sound quite cool but how does variable inspection work?
  
  Regards
  Lee

• Anonymous
  July 27, 2005
  I've updated the mini-example to show how basic variable inspection would work. It takes advantage of the fact that debuggers can automatically see the derived instance of a variable ("locals" of type System.object in this case)

• Anonymous
  July 30, 2005
  Great article! The solution doesn't seem obvious, but you explain it very well. Thanks.

• Anonymous
  August 22, 2005
  Sometimes you may have functions that you don’t want a debugger to step into (such as 3rd-party library...

• Anonymous
  October 18, 2007
  Recently I was talking to Mike Stall from the VS team and he showed me this cool concept of state debuggers.

• Anonymous
  November 30, 2007
  There were over 80 responses to my recent post asking for feedback on where MSBuild should be heading

• Anonymous
  November 30, 2007
  There were over 80 responses to my recent post asking for feedback on where MSBuild should be heading

• Anonymous
  October 31, 2008
  Truth is Step aerobics does provide a whopping aerobic exercise that