Friday 15 June 2012

ASCII Art Testing

Suppose we're unit testing a shortest-path graph algorithm. We might write a test like the following:
val graph = makeGraph(
  edge("A", "B", weight = 7),
  edge("A", "F", weight = 14),
  edge("B", "C", weight = 10),
  edge("B", "D", weight = 15),
  edge("C", "D", weight = 11),
  edge("C", "F", weight = 2),
  edge("D", "E", weight = 6),
  edge("E", "F", weight = 9))
 
val path = graph.findShortestPathBetween("A", "E")
  
// Assertions ...
Although this is a reasonable way to define a graph, whenever someone tries to understand this test, they'll inevitably resort to sketching the graph to get a grip on its structure. We might even include a little ASCII-art diagram as a comment to save readers the effort of having to draw it out themselves. The downside is that, like all comments, the diagram could become out of sync with the code.

ASCII Art to the Rescue!

What we can do instead is to use ASCII art to directly specify the graph, and have a diagram parser to translate it into the appropriate graph object at runtime:
 val graph = makeGraph("""
             +-+             
    ---------|E|----------   
    |        +-+         |   
 [9]|                 [6]|   
    |                    |   
   +-+  [2]  +-+  [11]  +-+  
   |F|-------|C|--------|D|  
   +-+       +-+        +-+  
    |         |          |   
[14]|     [10]|      [15]|   
    |         |          |   
   +-+       +-+         |   
   |A|-------|B|----------   
   +-+  [7]  +-+       """)
The aim is to clearly communicate the data we're working with but still be precisely machine-parsable. The fact that your tests look 10 times as awesome is a bonus extra!

This DSL is for building graphs, but I've used the same sort of principle for 2D games (think Sudoku or Tetris), and others have used it for taxonomies (see ASCII Art as a DSL for Unit Tests) and image processing (see Building Image Unit Tests). You could go as far as to argue that, whenever you think pictorially about a domain, the tests should also be specified pictorially.

Depending on the domain, perhaps what is really needed is to define test-case data in a custom editor designed for that purpose. Still, ASCII art has the advantage that it's directly embeddable into source code and plays nice with version control.

A tool like JavE is invaluable, and most IDEs/editors support modes that can make working with ASCII art easier (Eclipse Block Selection, for example).

Parser

I've published a basic graph diagram parser on Github: ascii-graphs. It can be used like this:
import com.github.mdr.ascii._

val diagram = Diagram("""
             +-+             
    ---------|E|----------   
    |        +-+         |   
 [9]|                 [6]|   
    |                    |   
   +-+  [2]  +-+  [11]  +-+  
   |F|-------|C|--------|D|  
   +-+       +-+        +-+  
    |         |          |   
[14]|     [10]|      [15]|   
    |         |          |   
   +-+       +-+         |   
   |A|-------|B|----------   
   +-+  [7]  +-+      """)

// Print all the vertices neighbouring A along with the edge weight:
for {
  box ← diagram.allBoxes.find(_.text == "A")
  (edge, otherBox) ← box.connections()
  label ← edge.label
} println(box + " ==> " + label + " ==> " + otherBox)

No comments:

Post a Comment