Test case pattern matching

Test case pattern matching

Problem statement

A common problem in testing arises, when success of given unit test can only be formulated in terms of routine under test producing a certain output. Thus, comparison of unit test output to some predefined textual reference is provided by many test frameworks, including Boost.Test, used in this project. Unfortunately, literal comparison of test output to a fixed pattern is not very useful for a major part of difficult development scenarios.

Let's consider a fairly typical message produced by a non-trivial development helper program (such messages are hereafter referred as test space):

[236.768961] '' <0x1d34e98> loci: 0, sinks a/p: 1/1

At the very least, the values in square and angled brackets can not be matched literally to a reference pattern, because they change from one test run to another (the first value being a time stamp, the second one - some heap pointer).

Basic approach to pattern space definition

One simple approach is to augment the pattern space side of output matching with configurable parser references. Thus, a useful pattern for the test message above may look like this:

[%f] '' <%p> loci: 0, sinks a/p: 1/1

With escape character ('%'), it's literal reference ('%%') and parser reference names for some float ('f') and pointer ('p') values configurable through the matcher traits interface of appropriate sort. This approach is already way more useful than invariable literal matching. Needless to add that injected parsers must match the test space input for the overall pattern match to be considered successful.

Functionalized pattern space with constraints and memoization

Test space parser can carry an associated attribute (in Boost.Spirit terminology), which could be used to capture the actual parsed values of arbitrary types from the test space messages. This leads to a possibility to specify two broad classes of actions associated with non-trivial pattern space parser:

1. Values can be captured into uniquely named scalar or vector (all tagged values in order of occurrence) variables.
2. Values may have associated predicate expressions to be applied after success of parser to determine final status of matching to the point of occurrence.

For the later, minimalistic Lisp-like language feels like the most convenient choice, as most such predicates are rather simple (range or alignment tests). The predicate function must be able to access all values captured beforehand by their names.

If need arises to trigger unit test actions on some really complex behavior (such as timing irregularities) this can always be achieved by capturing appropriate data vectors and analysis of those in main unit test environment implementation language.

The pattern in a such, more complex system can look like this:

[%f[+ times]] '' <%p[ptr_a]{zero? (remainder this 8)}> loci: 0, sinks a/p: 1/1

With an intended meaning of:

1. Parser reference name can be trailed by one or two argument blocks.
2. Square bracket argument block carries instructions for value capture (into a vector of floats named times in %f[+ times] case and into a scalar long integer named ptr_a in %p[ptr_a] case).
3. Curly bracket argument is a predicate, applied post value capture to fail the pattern match or perform some other semantic action. An expression %p{zero? (remainder this 8)} is expected to implicitly mean something like (lambda (this) (zero? (remainder this 8))) applied to the just captured value (Scheme is used as an expression language here).
4. Javascript can also serve as a good predicate expression language choice - while having less elegant syntax, Javascript interpreters are plentiful and feature the highest performance of all embeddable languages. For example, expression %p{this_ & 7} can be evaluated directly through eval() facility (and, of course, Javascript provides ample, even though somewhat verbose, means to expand the predicate functionality).

Some trade offs between Scheme and Javascript

Javascript implementations tend to be the fastest among interpreted languages and when simpler predicates are concerned, the syntax is more friendly. However, for intermediate complexity predicates specified "in-line", Lisp-like syntax tends to "work" better (this is particularly important, because spurious newlines in predicate definitions and unnecessary verbosity will clutter the pattern space).

Another issue is interpreter size and complexity. Smallest practical Scheme interpreters, such as "TinyScheme" used in Gimp, are barely few tens of kilobytes in size and have barely any external dependencies. On the other hand, Javascript interpreters are multi-megabyte beasts, possibly linking to quite a few additional libraries. Normally, this would not be a problem, yet in typical unit test deployment the whole instrumentation framework (predicate interpreter included) is linked to a multitude of small programs, executed one after another. The need to initialize complex interpreter machinery on each unit test invocation (even if no fancy predicates are being used) may, therefore, significantly slow down the whole testing run, despite the better performance of individual predicate evaluations.