I need help building a data structure for a state diagram

[Matthew Wilson]

I'm working on a really simple workflow for my bug tracker. I want
filed bugs to start in an UNSTARTED status. From there, they can go to
STARTED.

From STARTED, bugs can go to FINISHED or ABANDONED.

I know I can easily hard-code this stuff into some if-clauses, but I
expect to need to add a lot more statuses over time and a lot more
relationships.

This seems like a crude state diagram. So, has anyone on this list done
similar work?

How should I design this so that users can add arbitrary new statuses
and then define how to get to and from those statuses?

TIA

MAtt

 

[Tim Chase]

I'm working on a really simple workflow for my bug tracker. I want

filed bugs to start in an UNSTARTED status. From there, they can go to
STARTED.


I know I can easily hard-code this stuff into some if-clauses, but I
expect to need to add a lot more statuses over time and a lot more
relationships.

This seems like a crude state diagram. So, has anyone on this list done
similar work?

I've got a similar workflow in one of my applications at work. I
use a database to persist the available states along with their
transitions. Both the states themselves and the transitions have
various attributes to them to facilitate my workflows. The
following schema should work in most databases such as sqlite
(included with Python2.5+) with minor syntactic tweaks (such as
auto-increment)

CREATE TABLE States (
id INT PRIMARY KEY AUTOINCREMENT,
description VARCHAR(50),
other_attributes ...
);

CREATE TABLE Transitions (
id INT PRIMARY KEY AUTOINCREMENT,
from_state INT NOT NULL REFERENCES States(id),
to_state INT NOT NULL REFERENCES States(id),
other_attributes ...
);
INSERT INTO States (description) VALUES
('Started'),
('Finished'),
('Abandoned');
INSERT INTO Transitions (from_state, to_state) VALUES
(1, 2), -- Started -> Finished
(1, 3), -- Started -> Abandoned
(3, 2); -- Abandoned -> Finished

You can then query states you can transition to:

SELECT s1.description, s2.description, t.other_attributes
FROM Transitions t
INNER JOIN States s1
ON s1.id = t.from_id
INNER JOIN States s2
ON s2.id = t.to_id
-- WHERE t.from_id = @current_id
ORDER BY s1.description, s2.description


You can easily add more state rows as well as transition rows to
the tables. Then use the other_attributes of either the
transition or the state to control the workflows (we have
transition attributes for things like "notifies account-manager",
"notifies customer", "number of days that must pass from initial
workflow-start", "number of days that must pass from most recent
status change", "does this transition happen manually or
automatically via an overnight script", etc.) The workflow
processing code then looks at these attributes for the transition
that's being attempted, and behaves accordingly.

Hope this gives you some ideas. If you want to read more, the
magic google-words are "finite state automaton" (FSA) or "finite
state machine" (FSM)[1]

-tkc

[1]
http://en.wikipedia.org/wiki/Finite_state_machine

 

[Kay Schluehr]

I'm working on a really simple workflow for my bug tracker.  I want
filed bugs to start in an UNSTARTED status.  From there, they can go to
STARTED.

From STARTED, bugs can go to FINISHED or ABANDONED.

I know I can easily hard-code this stuff into some if-clauses, but I
expect to need to add a lot more statuses over time and a lot more
relationships.

This seems like a crude state diagram.  So, has anyone on this list done
similar work?

How should I design this so that users can add arbitrary new statuses
and then define how to get to and from those statuses?

TIA

MAtt

General answer: you can encode finite state machines as grammars.
States as non-terminals and transition labels as terminals:

UNSTARTED: 'start' STARTED
STARTED: 'ok' FINISHED | 'cancel' ABANDONED
ABANDONED: 'done'
FINISHED: 'done'

In some sense each state-machine is also a little language.

 

[Matthew Wilson]

General answer: you can encode finite state machines as grammars.
States as non-terminals and transition labels as terminals:

UNSTARTED: 'start' STARTED
STARTED: 'ok' FINISHED | 'cancel' ABANDONED
ABANDONED: 'done'
FINISHED: 'done'

In some sense each state-machine is also a little language.

I've never formally studied grammars, but I've worked through trivial
stuff that uses BNF to express ideas like

<postal-address> ::= <name-part> <street-address> <zip-part>

I don't really understand how to apply that notion to this statement:

UNSTARTED: 'start' STARTED

That doesn't seem to be BNF, and that's all I know about grammar stuff.

Can you explain a little more? This idea of using grammars for my
workflow sounds *really* fun and I'd love to learn this stuff, but I
could benefit from some more explanation.


Matt

 

[Kay Schluehr]

I've never formally studied grammars, but I've worked through trivial
stuff that uses BNF to express ideas like

    <postal-address> ::= <name-part> <street-address> <zip-part>

I don't really understand how to apply that notion to this statement:

    UNSTARTED: 'start' STARTED

That doesn't seem to be BNF, and that's all I know about grammar stuff.

Some comments

1) The separator is arbitrary. You can use ':' or '->' or '::=' etc.
2) A full EBNF grammar can be described in itself:

GRAMMAR: RULE+
RULE: NAME ':' RHS
RHS: ALT ( '|' ALT )*
ALT: ITEM+
ITEM: '[' RHS ']' | ATOM [ '*' | '+' ]
ATOM: '(' RHS ')' | NAME | STRING
STRING: '"' any* '"'
NAME: char (digit | char)*

[A] zero or one repetition
A* zero or more repetitions
A+ one or more repetitions
A|B A or B
A B first A next B
(A ..) parentheses for separation
"A" keyword A


In some sense all the words 'start', 'done', 'ok' etc. are keywords of
the language. If I actually attempted to use the grammar for parsing
it could parse a few sentences like:

'start ok done' or 'start cancel done'

and create parse trees [UNSTARTED, start, [STARTED, ok, [FINSIHED,
done]]] etc.

One can however use the Finite State Machine generated from the
grammar for totally different purposes: interpret each rule as a state
and the keywords as events that cause state transitions.

UNSTARTED -- start --> STARTED
STARTED -- ok --> FINISHED
STARTED -- cancel --> ABANDONED
FINISHED -- done --> .
ABANDONED -- done --> .

That's basically the same formal language with a different, more
intuitive notation.

 

[Paul McGuire]

I'm working on a really simple workflow for my bug tracker.  I want
filed bugs to start in an UNSTARTED status.  From there, they can go to
STARTED.

I just wrote an article for the April issue of Python Magazine on how
to add embedded DSL code to your Python scripts using Python's imputil
module, and I used a state pattern for my example. Two state machine
examples I used to illustrate the work were a traffic light and a
library book checkin/checkout. The traffic light state machine is
just a simple cycle through the 3 light states. But the library book
state machine is more complex (your bug tracking example made me think
of it), with different transitions allowed one state into multiple
different states. Here is how the code looks for these examples:

==============
# trafficLight.pystate
statemachine TrafficLight:
Red -> Green
Green -> Yellow
Yellow -> Red

Red.carsCanGo = False
Yellow.carsCanGo = True
Green.carsCanGo = True

# ... other class definitions for state-specific behavior ...

==============
# trafficLightDemo.py

# add support for .pystate files, with
# embedded state machine DSL
import stateMachine

import trafficLight

tlight = trafficLight.Red()
while 1:
print tlight, "GO" if tlight.carsCanGo else "STOP"
tlight.delay()
tlight = tlight.next_state()


==============
# libraryBook.pystate

statemachine BookCheckout:
New -(create)-> Available
Available -(reserve)-> Reserved
Available -(checkout)-> CheckedOut
Reserved -(cancel)-> Available
Reserved -(checkout)-> CheckedOut
CheckedOut -(checkin)-> Available
CheckedOut -(renew)-> CheckedOut


You don't need to adopt this whole DSL implementation, but the article
might give you some other ideas.

-- Paul