Repository files navigation

Python-Graphwalker is a tool for testing based on finite statemachine graphs. Graphwalker reads FSMs specified by graphs, planspaths, calls model methods by name from graph labels and reportsprogress and results.

While conceptually derived from the Graphwalker projectgw,(implemented in java) this is a complete reimplementation from thatinitial concept.

Notably, there are a few differences:

• In the original, nodes are considered states to be verified andedges actions to be taken, but this version has no ambition toenforce this convention in any way, even though it is quiteuseful.

• Python Graphwalker does not understand extended FSM labels. Itshould ignore them, but proceed at your own risk until this isdefinitively dealt with one way or the other.

• Python Graphwalker is quite promiscuous about letting you loadand combine code to implement the different components of thedesign. Some combinations don't make sense.

• Instead of the SWITCH_MODEL keywords in the original, this versionsimply allows you to load multiple graphs and stitches themtogether where id:s and labels match.

Generally, these simplifications makes the resulting graph much easierto reason about.

The idea that has driven the design is that the graph-problems arequite orthogonal to the testing actions and that the problem ofreporting the results are orthogonal to both. The graph-problemsare further decomposable into path planning, stop conditions and ofcourse loading graph files.

The added feature request to be able save and replay the path of arun dissolve into the path-recorder reporting class and the plaintext graph loader.

The design is separated into these parts:

• Model, (normally) supplied by the user as a graph file.

• Stop condition, which bool-converts to true if its conditionsare met.

• Planner, which uses the model and stop condition to provide aniterable of plan steps as (id, name, ...) tuples.

• Reporter, which is called on execution events.

• Taps, installed by the reporter system to capture side-effects.(currently stdout/stderr and logging)

• Actor supplied by the user as an object with functionattributes, normally an object instance.

• Executor that, for each step in the plan, calls the reporterand looks up and calls the named method on the actor. In additionto the step methods, it also calls a few other methods, if presenton the actor.

There is a common code-loader interface, so it's easy to loadcustom code and supply arguments (if any, if callable) from thecommand line:

• --foo=module.module

• --foo=module.module.function

• --foo=module.module.class:argument,...,keyword=value,...

If the object found is callable, it will be called, with anyarguments supplied, and the result used.

Models can now be broken down into sub-graphs that can be combined atloading time. In order for this to make sense, some nodes (andoptionally edges) need to have the same id and label, and these willbe considered the same in the new graph. They must match on both idand label, but they are permitted to have different attributes likeweight, as long as those attributes don't conflict.

Currently, Python Graphwalker understands a few simple fileformats:

Graphs for the original Graphwalker are typically drawn using[yEd], which normally produces graphml files, so support for thesehave been a priority.

Plain graphviz files can also be written, which turns out to beuseful: The Cartographer reporter uses dot to generate highlightedmaps as it goes.

Plain text word lists are interpreted as a linear list of nodes tovisit. Comments of the familiar "/* ... */" form are respected,as are line comments of both the "#" and "//" varieties. If thefirst node isn't labeled "Start", such a node is added.

Other formats are easy enough to add. All that you need to supplyfor a reader is an iterable of vertex (id, label) pairs and aniterable of (id, label, from-id, to-id) quadruples. Graphwalkerwill convert these to its internal formats. For write-support, youneed to take a similar pair of sequences, but with the differencethat for the vertex and edge tuples might be longer.

The steps to be executed by the executor are determined by one ormore planners. Normally, planners are expected to examine thesupplied graph and plan a traversal of it, but the lack ofenforcement 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 agraph and a StopCond instance to supply an iterable containingtuples of at least two elements, as the executor expects id andlabel.

To generate repeatable plans, use the seed keyword argument asplanners keep their own random number generators.

The simplest planner, Random, traverses the graph by randomlychoosing an edge and visiting that edge and the target vertex untilthe StopCond is satisfied. It does not check the StopCond betweenedge and vertex. Edges may be weighted to skew the edge choices, byadding attributes like "weight=0.3" to a second line of edge labels.If used, weights should sum to 1.0. If only some edges have weights,the remaining edges will share the remaining weight equally.

graphwalker --stopcond=Coverage --planner=Random:seed=1337 model.dot

To visit specific vertices, name them as arguments to the Gotoplanner. In addition to names and ids, 'random' will pick a vertexat random. If there is more than one candidate, the one closest tothe current vertex will be chosen. (So this does not, currently,minimize the total path.)

An integer for the keyword argument 'repeat' will repeat the namelist. (but not, nota bene, the specific vertices.) A repeat of zerowill 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 togenerate anEulerian trail. Since the graph is not necessarilyeven (semi-)Eulerian, the Euler planner copies the graph andmodifies it. First, by cutting out the forced steps from the Startvertex source subgraph. The graph is then 'eulerized' by addingedges to make it Eulerian. (in-degree equal to out-degree for allvertices) After the plan is created it run through the StopCond, toget 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 whendeveloping or debugging models. When run, Interactive lists theedges of the current vertex and prompts for input. You can choose alisted edge by entering it's number, or you can use one of thespecial commands:

*: asks if there's more than one by the name given

If you quit from the debugger,you quit from the whole program. Catching BdbQuit exceptionsdoesn't seem to work, instead, use c/continue

You can set breakpoints in, for instance, other planners, that willdrop you back into the debugger after you've left it.

Some planners have inherent stopping conditions, others don't, sothere are independent conditions that can be applied to the plans.It's up to the planner to consult them, to they don't always cutthe test off optimally, or at all.

The default stop condition is coverage of 100% of edges, whichmeans that it will signal completion when it's seen all the edgesin the graph. It can also require some percentage of vertices, orsome percentage of each. The percentages are given as keywordsarguments 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 willsimply be done when it has seen all the steps it's looking for. Thesteps are given as an argument list.

graphwalker --stopcond=SeenSteps:a,e_once,b model.dot

Again ignoring the difference between edges and vertices, simplycounts the test steps and signals when some number of steps havebeen taken. The number of steps is the first argument, or thekeyword 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 thenames supplied by the planner, so you can implement the test codeas a module, a class, or, using the programmatic interface,basically any object you like.

The callables on the test object are called without arguments fornow.

In addition to the labels in the graph, a few administrativemethods are also called, if present:

• setup is called at the start of the test session with adictionary containing the other instances involved in the test: thereporter, the model, and so on. Notably, if you want to saveattachments from the test methods, you should use the reporterinstance here.

• step_begin is called before each step with the stepdefinition. The step definition is an iterable where the first isthe id and the second the name of the step.

• step_end is called before after each step like step_begin,but with the addition of a failure, usually None. If the testfailed, or there was some other exception, step_end is called withthat exception, typically an AssertionError. The step_end methodcan permit the testing to continue by returning the exact string"RECOVER".

• teardown is called the same way as setup, at the end.

To report the results of the tests, the reporters are all calledfor each event, notably step_begin and step_end.

Simply print to stdout (default) or stderr, controlled with thekeyword argument output. If you are using the programminginterface, you can send any file-like, writable object. Note thatcombinations 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 loggerdefaults to the name of the reporting module, but can be set viathe keyword argument 'logger'. The level can also be set with thekeyword argument 'level'. Note that combinations of Log and Printquickly 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 theplain-text graph reader. The directory where the file is saveddefaults to '.' but can be given as the keyword argument 'path'.Likewise name defaults to the test name but can be set with thekeyword argument 'name'. The 'attach' keyword argument, if set (atall) 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 Cartographerreporter emits graphviz files with the current step highlighted.The keyword arguments 'dotpath' and 'imgpath' control where thegraphviz input and output files go, respectively, bot defaulting to'.'. The image type defaults to PNG but can be set using thekeyword 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 loggingsystem. Both the logging tap and taps of standard out & error areincluded by default.

Graphwalker itself needs a lot more, and a lot more devious tests.

The first iteration of the Python port of Graphwalker was writtenby Viktor Holmberg, Harald Hartwig and Chongyang Sun under thedirection of Nils Österling (tester) and Anders Eurenius(developer).

This iteration was rewritten from scratch by Anders Eurenius toincorporate everything we learned from the first.

The license we have chosen is the Apache License, version 2.0. Youshould find the full text in the file named "LICENSE.txt".