Finite state machine based testing tool.
Python-Graphwalker is a tool for testing based on finite state machine graphs. Graphwalker reads FSMs specified by graphs, plans paths, calls model methods by name from graph labels and reports progress and results.
While conceptually derived from the Graphwalker project, (implemented in java) this is a complete reimplementation from that initial concept.
Notably, there are a few differences:
The graph for the self-test of the Interactive planner.
The idea that has driven the design is that the graph-problems are quite orthogonal to the testing actions and that the problem of reporting the results are orthogonal to both. The graph-problems are further decomposable into path planning, stop conditions and of course loading graph files.
The added feature request to be able save and replay the path of a run dissolve into the path-recorder reporting class and the plain text graph loader.
The design is separated into these parts:
There is a common code-loader interface, so it’s easy to load custom code and supply arguments (if any, if callable) from the command line:
If the object found is callable, it will be called, with any arguments supplied, and the result used.
Currently, Python Graphwalker understands a few simple file formats:
Graphs for the original Graphwalker are typically drawn using yEd, which normally produces graphml files, so support for these have been a priority.
Plain graphviz files can also be written, which turns out to be useful: The Cartographer reporter uses dot to generate highlighted maps as it goes.
Plain text word lists are interpreted as a linear list of nodes to visit. Comments of the familiar “/* … */” form are respected, as are line comments of both the “#” and “//” varieties. If the first node isn’t labeled “Start”, such a node is added.
Other formats are easy enough to add. All that you need to supply for a reader is an iterable of vertex (id, label) pairs and an iterable of (id, label, from-id, to-id) quadruples. Graphwalker will convert these to its internal formats. For write-support, you need to take a similar pair of sequences, but with the difference that for the vertex and edge tuples might be longer.
The steps to be executed by the executor are determined by one or more planners. Normally, planners are expected to examine the supplied graph and plan a traversal of it, but the lack of enforcement creates a few special opportunities.
Planners are instantiated through the common code-loader interface, so it’s easy to plug in your own planner. They’re called with a graph and a StopCond instance to supply an iterable containing tuples of at least two elements, as the executor expects id and label.
To generate repeatable plans, use the seed keyword argument as planners keep their own random number generators.
The simplest planner, Random, traverses the graph by randomly choosing an edge and visiting that edge and the target vertex until the StopCond is satisfied. It does not check the StopCond between edge and vertex.
graphwalker --stopcond=Coverage --planner=Random:seed=1337 model.dot
To visit specific vertices, name them as arguments to the Goto planner. In addition to names and ids, ‘random’ will pick a vertex at random. If there is more than one candidate, the one closest to the current vertex will be chosen. (So this does not, currently, minimize the total path.)
An integer for the keyword argument ‘repeat’ will repeat the name list. (but not, nota bene, the specific vertices.) A repeat of zero will be taken to mean infinity.
graphwalker --planner=Goto:happy,random,sad,repeat=10 model.dot
To visit all edges in the graph most efficiently, we’d like to generate an Eulerian trail. Since the graph is not necessarily even (semi-)Eulerian, the Euler planner copies the graph and modifies it. First, by cutting out the forced steps from the Start vertex source subgraph. The graph is then ‘eulerized’ by adding edges to make it Eulerian. (in-degree equal to out-degree for all vertices) After the plan is created it run through the StopCond, to get rid of extraneous steps at the end.
graphwalker --planner=Euler model.dot
There’s often a wish to choose paths as the test is running when developing or debugging models. When run, Interactive lists the edges of the current vertex and prompts for input. You can choose a listed edge by entering it’s number, or you can use one of the special commands:
|g, go to||Goes to the specified vertex |
|f, force||Send some arbitrary name(s) as plan steps|
|j, jump||Set some new vertex  as the current one|
|d, debug||Enter the pdb debugger|
|q, quit||End the plan|
|||(1, 2) asks if there’s more than one|
If you quit from the debugger, you quit from the whole program. Catching BdbQuit exceptions doesn’t seem to work, instead, use c/continue
You can set breakpoints in, for instance, other planners, that will drop you back into the debugger after you’ve left it.
Some planners have inherent stopping conditions, others don’t, so there are independent conditions that can be applied to the plans. It’s up to the planner to consult them, to they don’t always cut the test off optimally, or at all.
The default stop condition is coverage of 100% of edges, which means that it will signal completion when it’s seen all the edges in the graph. It can also require some percentage of vertices, or some percentage of each. The percentages are given as keywords arguments named ‘edges’ and ‘verts’ or ‘vertices’.
graphwalker --stopcond=Coverage:edges=100,verts=50 model.dot
graphwalker --stopcond=Coverage:vertices=25 model.dot
Ignoring the difference between edges and vertices, SeenSteps will simply be done when it has seen all the steps it’s looking for. The steps are given as an argument list.
graphwalker --stopcond=SeenSteps:a,e_once,b model.dot
Again ignoring the difference between edges and vertices, simply counts the test steps and signals when some number of steps have been taken. The number of steps is the first argument, or the keyword argument ‘steps’, defaulting to 100.
graphwalker --stopcond=CountSteps:52 model.dot
graphwalker --stopcond=CountSteps:steps=52 model.dot
The test executor simply uses getattr to look up callables by the names supplied by the planner, so you can implement the test code as a module, a class, or, using the programmatic interface, basically any object you like.
The callables on the test object are called without arguments for now.
In addition to the labels in the graph, a few administrative methods are also called, if present:
To report the results of the tests, the reporters are all called for each event, notably step_begin and step_end.
Simply print to stdout (default) or stderr, controlled with the keyword argument output. If you are using the programming interface, you can send any file-like, writable object. Note that combinations of Log and Print quickly get really confusing.
graphwalker --reporter=Print:output=stderr model.dot
Emits to the standard python logger. The name of the logger defaults to the name of the reporting module, but can be set via the keyword argument ‘logger’. The level can also be set with the keyword argument ‘level’. Note that combinations of Log and Print quickly get really confusing.
graphwalker --reporter=Log:logger=moo,level=WARN model.dot
The PathRecorder simply saves the plan step names to a text file, so that the run can be replicated by feeding recording to the plain-text graph reader. The directory where the file is saved defaults to ‘.’ but can be given as the keyword argument ‘path’. Likewise name defaults to the test name but can be set with the keyword argument ‘name’. The ‘attach’ keyword argument, if set (at all) makes it try to attach it.
graphwalker --reporter=PathRecorder:path=/tmp,name=steps model.dot
graphwalker --reporter=PathRecorder:attach=true,name=steps model.dot
To map the progress of the test graphically, the Cartographer reporter emits graphviz files with the current step highlighted. The keyword arguments ‘dotpath’ and ‘imgpath’ control where the graphviz input and output files go, respectively, bot defaulting to ‘.’. The image type defaults to PNG but can be set using the keyword argument ‘imgtype’. The ‘attach’ keyword argument, if set (at all) makes it try to attach it.
graphwalker --reporter=Cartographer model.dot
graphwalker --reporter=Cartographer:imgtype=jpg,attach=1 model.dot
graphwalker --reporter=Cartographer:dotpath=/tmp,imgpath=./www model.dot
Currently, the there are only taps for streams and the logging system. Both the logging tap and taps of standard out & error are included by default.
Graphwalker itself needs a lot more, and a lot more devious tests.
The license we have chosen is the Apache License, version 2.0. You should find the full text in the file named “LICENSE.txt”.