NAME

quest -- generate test cases for C compilers

SYNOPSIS

quest [-test test] [-n number] [-s depth] [-1|-2] [-o basename] [-i] [-e Lua chunk] [x=y] [file.lua] [-seed number]

quest -list | -lua | -man | -help | -version

DESCRIPTION

Quest generates random C code to tests the parameter passing implementation of a C compiler. When generated code is compiled and executed, it checks that the values passed to a function are actually the ones that are expected. The generated code signals an error to stdout when it finds parameter-passing bugs.

Quest can emit code into one or two C source files. Two files may be compiled by different compilers to check their interoperability. When Quest generates code for two files, one file contains calling functions and the other called functions.

Quest has an embedded interpreter for the scripting language Lua 2.5 that drives the top level of Quest. A user may add her own Lua code to define additional test code generators. Adding a new test-code generator is declarative and takes about 30 lines per generator.

OPTIONS

-test suite

Use the test-code generator suite. Such a generator may be defined by the user using the built-in Lua scripting language -- see below. By default, the ansi generator is used. For a list of available generators see the -list option.

-list

List available test suites to stdout and quit.

-n int

Test cases per file: the -n flag indicates how many test cases per file to generate. The default is 20.

-s int

Test complexity: -s indicates the complexity (or size) of the types used in a test case. A C type has a tree structure with simple types at the leaves and complex types like structs, pointers, and arrays at the inner nodes. The size provided by -s is the maximum depth of such a tree; the default size is 2.

Below are trees of depth 1, 2, and 3 to illustrate the concept of depth; curly brackets denote structs and unions, a star denotes a pointer type.

0      1         2              3
    
    char    *         *              {}
       |         |             /  \
      int        {}         int   {}
                /  \             /  \
             double int         *   char 
                                |
                               float

For example, with -s 0 all types are simple (scalar) types; with -s 1 a type may be a union or a pointer, but it must contain only simple types.

-1

Generate code for one file (compilation unit) and write it to stdout; this is the default.

-2

Generate code for two files (compilation units) whose names are controlled by the -o flag. No code is written to stdout.

-o name

When generating code for two files, write them to name-main.c and name-callee.c; the default for name is quest and the two default files are thus quest-main.c and quest-callee.c. The quest-main.c file contains the main() function of the program that results from compiling and linking these two files together.

-try gen

Instead of generating code, print the C types generated by generator gen to stdout. The generator gen must be specified as a Lua variable, e.g. Test.ansi.result and is not the same a test suite as accepted by option -test. The options -s, -n are honored. The following example prints three C types, generated by the generator for return types that is part of the -test ansi suite. See section also TYPE GENERATORS IN LUA.

$ quest -n 3 -s 1 -try Test.ansi.result
double
union at2 { char cv2; double bv2; float av2; }
double *

x=y

An assignment (containing an =) is considered a Lua code chunk and is passed to the interpreter for evaluation. This is a short form for -e x=y to simplify assigning a value to a Lua variable from the command line:

$ quest -n 3 -s 0 'foo=R.oneof{R.any_int,R.any_float}' -try foo
char
double
float

-e chunk

Evaluate the Lua code chunk in the interpreter before generating test cases. This can be used to set (global) variables in the interpreter that test generators may rely on. However, chunk may be arbitrary code, not just assignments. This option may be repeated; chunks are evaluated from left to right.

file.lua

Load and execute file.lua as Lua code. Use this option to add new code generators to Quest or to override the built-in Lua code. Evaluation order is as follows: first the built-in Lua code is loaded into the interpreter and then the command line is evaluated from left to right. This honors all assignments (x=y), -e chunks, and files file.lua in left-to-right order.

-lua

Dump the built-in Lua code to stdout. This permits to inspect the Lua code that drives the application internally.

-seed int

Use int to seed the pseudo-random generator. The default is to use an automatically chosen seed. A user-provided seed is useful for debugging because it leads to the same output in two different program runs. A seed may be negative.

Each test case contains its seed as a comment. So when a test case among many in a file has failed you can create a small file with just that test case using -seed and -n 1. Of course, you have to use otherwise the same options that were used to generate the original file. These options are included as a comment at the beginning of each file.

The seed controls the types of a test case, but not the values that are used for initializations. Two test cases generated with the same thus may differ in their values. This may change in a future version.

-h | -help

Emit help message to stdout.

-version

Emit version information to stdout.

SIMPLE EXAMPLES

```
quest > t.c
```
Emit one test file with 20 test cases to stdout.
```
quest -s 1 > t.c.
```
Emit one test file with 20 test cases of reduced complexity to stdout.
```
quest -2 -test gcc
```
Emit two files, quest_callee.c and quest_main.c with 20 test cases that may contain empty structs and arrays (as they are accepted by gcc(1)).
```
quest -2 -o ttt -n 100
```
Emit two files ttt_callee.c and ttt_main.c with 100 test cases.

ADVANCED EXAMPLES

The command sequence below for sh(1) is a quick way to test a C compiler:

while true; do
    quest > quest.c
    cc -o xxx -O2 quest.c || break
    ./xxx || break
    echo -n .
done

The loop runs until either the compiler fails or the quest-generated generated code detects a bug in the compiler. The echo command is there just to indicate some progress.

When a bug is found you can inspect the code surrounding the reported line. There you will find a seed number. You can use this to re-create a file with just the single test case that failed. Assuming the seed was 12345, the following command will create a file with just a single test case.

quest -seed 12345 -n 1 > quest-12345.c

It is important that you use the same options as before (with the exception of -n and -seed) to re-create a test case when using a seed.

TYPE GENERATORS IN LUA

Quest contains an embedded interpreter for the Pascal-like scripting language Lua. It controls Quest's high-level behavior and is used to define test code generators. Instead of using the built-in Lua code, a user may supply her own code and thus new test-code generators. Before reading on it is a good idea to read the Lua 2.5 reference manual that comes with Quest, and to study the built-in Lua code, which may be obtained with quest -lua.

All test cases are derived from function signatures (i.e., the return and parameter types). These are generated by scripted generators. To define a new test code generator it thus suffices to define a generator for C types.

A generator is a Lua value, which, when run, produces a C type. A generator is built from simpler generators; the simplest generators are for scalar C types. A generator has its own type in Lua. Like tables, generators are polymorphic: a generator may produce numbers, or strings, or a mixture of both, it may even produce another generator. Most generators produce only values of one kind. Specifically, we call a type-generating generator a typegen, and a number-generating generator an intgen, and so on.

R = Rand    -- abbreviation

-- all generators below are typegens.
R.char
R.short
R.int
R.long
R.longlong
R.float
R.double
R.longdouble

When such a generator is run (using R.run), it produces the corresponding (signed) type. Below is an interactive session with the Lua interpreter where we used print to show the result of a generator.

$ quest -i
-- $Id: quest.pod 4 2006-11-09 12:02:13Z lindig $
-- This is Lua-ML for Quest
> R = Rand
> u = Uniq.make()    
> print(R.run(R.char,u,3))
char
>

A generator for an unsigned type may be derived from a generator for a signed type, using R.unsigned(typegen); this works for all integer- and char-producing generators from above.

R.unsigned(R.char)  -- typegen

A complex type is a type that has other types embedded, like arrays, structs, unions, and pointers. The generators for these types takes another generator as argument to produce the embedded type:

R.pointer(R.char)   -- typegen

The code above is a character-pointer generator. Obviously such a generator is not very interesting, because it produces the same type in every run. Variation comes from generators that select a generator randomly from a list of generators:

R.pointer(R.oneof {R.char, R.int, R.long}) -- typegen

> print(R.run(R.pointer(R.oneof{R.char, R.int, R.long}),u,3))
int *
> print(R.run(R.pointer(R.oneof{R.char, R.int, R.long}),u,3))
long int *
> print(R.run(R.pointer(R.oneof{R.char, R.int, R.long}),u,3))
int *

The generator R.oneof(typegen list) takes a list of generators and selects in each run one randomly. The generator above thus generates pointers to characters, integers, and longs.

A generator may produce values other than C types: the generator R.integer(n) generates a (random) integer in the range 0 to n-1. Such an int_gen generator is required to decide the size of an array:

R.array(R.char, R.integer(5))

Don't confuse generator R.integer with generator R.int. The former generates a (Lua) number, the latter a (C) type.

> print(R.run(R.array(R.char, R.integer(5)),u,3))            
char [4]
> print(R.run(R.array(R.char, R.integer(5)),u,3))
char [2]
> print(R.run(R.array(R.char, R.integer(5)),u,3))
char [3]

The generator above produces character arrays of size 0 to 4. Since a size of zero is illegal in ANSI C, we also have integer generators that permit to specify a lower bound too: R.choose(1,5) produces an integer in the range 1 to 5 inclusive. A better generator thus would be:

simple = R.oneof {R.char, R.int, R.unsigned(R.int)}
R.array(R.oneof{simple, R.choose(1,5))

Here we have assigned a generator to a variable and used it in the construction of the array generator. The is perfectly legal because a generator is a Lua value and may be assigned to a variable, passed to or returned from a function.

By now you should have a good idea how generators are built and how to use additional generators. The generators for structs and unions take generators that produce lists of types. These are built with R.list, which takes two generators: one for integers, and one for types. The integer generator controls the length of the list, the type generator is used to fill the list with the appropriate number of types.

R.union(typelistgen)   -- generate unions
R.struct(typelistgen)  -- generate structs
R.list(intgen,typegen) -- generate list of types

We are now ready to look at the definition of a real generator ANSI.result for the return type of a C function.

ANSI.simple  = R.oneof {R.any_int, R.any_float }
ANSI.members = R.choose(1,3)
function ANSI.result_ (issimple)
    if issimple then
        return ANSI.simple
    else 
        return R.smaller 
        { R.any_int
        , R.any_float
        , R.pointer(ANSI.result)
        , R.struct(R.list(ANSI.members,ANSI.arg))
        , R.union(R.list(ANSI.members,ANSI.arg))
        }
    end     
end    
ANSI.result = R.bind(R.iszero,ANSI.result_) -- just use it this way

A type in general is recursive and thus generators are recursive too. However, we cannot define recursive generators directly because of the eager evaluation of function arguments in Lua (and most other languages). We thus have to use a little indirection. The generator must also limit the recursion during the construction to ensure termination. Function ANSI.result_ receives a boolean value that tells whether it should produce a simple value (and thus end recursion), or a complex value. In either case, it returns a generator.

In the simple case, the generator returns an integer or float. (R.any_int and R.any_float are predefined.) In the complex case, the generator produces and integer, float, struct, or union, but no array because these are illegal in return types. The R.smaller generator ensures that the size of the generated types becomes smaller with deeper recursion.

A test suite is a table of four generators: one for regular arguments, one used for var args, one for the result type, and one for the scope of the function under test. The scope can be static or public. Since a static function may be called using a different calling convention than a public function, some variation is useful. We use the flip generator for the scope, which returns a boolean value. The generator for static is ignored when code is emitted into two files; all functions under are declared public in this case, since they would not be visible for the caller otherwise.

This table must be returned by a function that expects no arguments.

function ANSI.test () return
    { args       = R.list(R.choose(1,4),ANSI.arg)
    , varargs    = R.list(R.unit(0),R.int)  -- var args
    , result     = ANSI.result
    , static     = R.flip -- generates bool
    }
end

The generator for parameter lists uses the ANSI.arg generator for each parameter (which we haven't shown); it used to produce a list of parameters, where the list contains between 1 and 4 parameter types. The list for var args always has zero elements and the generator for the result type is the one defined above.

To make a generator accessible for the -test command line option, it must be placed into the Test table. The generator above is thus available as -test ansi.

Test.ansi = 
    { doc   = "ANSI C, but no var args"
    , test  = ANSI.test
    }

To see the actual Lua code used in Quest, use quest -lua that dumps it to stdout. To add your own code, write it into a file my.lua and pass this file as quest my.lua to Quest. For a start, it is a good idea to extract the code in the Demo table from the Quest -lua output, to modify it, and to pass it back into the interpreter on the command line.

VAR ARGS

A function using varargs must have at least one regular argument (c.f. the documentation for stdarg.h); all test cases violating this requirement are dropped with a warning. The var args generator for the ansi generator is Test.ansi.test.varargs, the corresponding generator Test.ansi.test.args for regular arguments thus must be defined to produce at least a list of length one.

PRIMITIVE GENERATORS

This section lists the primitive and complex generators that are built into Quest and which can be used to define new generators. The following generators are in Table Rand (which we abbreviated above as R).

unit(value)             -- generator that always returns value
bind(gen,function)      -- give function access to value from gen
run(gen,uniq,number)    -- run generator, asking for for result of size
smaller(gen list)       -- select gen from list, ask for smaller size
iszero                  -- boolean generator, signals end of recursion

flip                    -- bool generator
integer(number)         -- integer generator, range 0 .. number-1
choose(number,number)   -- integer generator, range low .. high
elements(value list)    -- generator producing value from list
oneof(gen list)         -- generator selecting generator from list
list(intgen, gen)       -- generate list (length by intgen) using gen
freq(pairs)             -- see below
concat(gen list)        -- takes list of list-generating generators
                           and builds a single list-generating generator

char                    -- C char generator
short                   -- C short generator
int                     -- C int generator
long                    -- C long generator
longlong                -- C longlong generator
bitfield(intgen)        -- C bitfield of given width

unsigned(typegen)       -- generate unsigned values

float                   -- C float generator
double                  -- C double generator
longdouble              -- C long double generator
any_int                 -- generates an int type
any_float               -- generates a float type

array(typegen,intgen)   -- C array of intgen length
pointer(typegen)        -- C pointer type generator 
struct(typelistgen)     -- C struct type generator (intgen members)
union(typelistgen)      -- C union type generator  (intgen members)

Note that bitfields are legal only as part of a structure or union.

Generators like oneof or elements select generators or values from a list with equal probability. The freq generator permits to specify a biased choice:

R.freq 
    { 1, char
    , 3, int
    , 5, float
    }

It takes a list of integer/generator pairs. The integer defines a weight for the choice; hence, the float generator is chosen 5 out of 9 times (1+3+5=9).

Function run is used mostly internally; it takes a name generator and a size as arguments, where the size defines the maximum depth of a type. This size is the same that is also specified on the command line. A generator for unique names is returned by Uniq.make().

Function bind is also used mostly internally. It gives a function access to a value a generator has produced when the generator is run. This was used in the example above to give the Ansi.result_ function access to the result of iszero. Once iszero produces true in a run, recursion must stop.

The ultimate resource for the list of available generators and other primitive Lua functions is the source code of Quest's implementation: module lualink.nw.

THE GENERATED CODE

A file generated by quest typically contains a number of test cases. Each test case defines some possibly complex global variables. These are automatically initialized with random values using C initializers .

int x0 = 5;
int x1[2] = {38, 2};
struct s {
    char c;
    int  i;
} x2 = { 'c', 77 };

A generated function with corresponding parameters expects these variables to be passed; the body of the function checks that the values actually passed are indeed the ones expected.

void f(int a0, int a1[2], struct s a2)
{
    if (a0 != x0) failed(__LINE__);
    if (a1[0] != x1[0]) failed(__LINE__);
    if (a1[1] != x1[1]) failed(__LINE__);
    if (a2.c != x2.c) failed(__LINE__);
    if (a2.i != x2.i) failed(__LINE__);
}

If the function finds an unexpected value passed in a parameter, it calls failed(). The failed() function emits an error message indicating the file and line number of the error.

For each function f, a corresponding function g is generated that passes the global variables by value to f().

void g(void)
{
    f(a0,a1,a2);
}

This function is called by the main() function when the test is run. The main() function therefore just contains as many calls as there are test cases in a file.

When the code is distributed over two files, f() and g() reside in two different files; variable and function declarations as necessary are declared to make the different parts known to each other.

The code above just illustrates the principle; the real code generated uses less readable names to avoid name clashes.

The complexity of the types for global variables can be controlled by the -s flag. However, the exact distribution of types is currently hard-coded into quest.

EXIT CODE

Upon successful execution, quest exists with exit code 0. Wrong usage leads to a positive error code, internal errors to a negative error code.

The generated code contains a main function that returns the number or errors found; hence it returns 0 for a successful test and a positive number if it finds bugs.

BUGS

When something goes wrong while executing Lua code, the Lua interpreter emits a stack trace. From this it is sometimes difficult to figure out the problem.

AUTHOR

Please send feedback, bug reports, and experience reports to the author: Christian Lindig <lindig@gmail.com>

The source code is available from GitHub: https://github.com/lindig/quest

The Lua-ML interpreter was implemented by Norman Ramsey <nr@eecs.harvard.edu> and is available from http://www.cminusminus.org/ and https://github.com/lindig/lua-ml. The Lua language was designed and implemented by Roberto Ierusalimschy et al.; a C implementation of Lua is available from http://www.lua.org/

COPYRIGHT

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR AND COPYRIGHT HOLDER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

quest.pod

quest.pod

NAME

SYNOPSIS

DESCRIPTION

OPTIONS

SIMPLE EXAMPLES

ADVANCED EXAMPLES

TYPE GENERATORS IN LUA

VAR ARGS

PRIMITIVE GENERATORS

THE GENERATED CODE

EXIT CODE

BUGS

AUTHOR

COPYRIGHT

SEE ALSO

Files

quest.pod

Latest commit

History

quest.pod

File metadata and controls

NAME

SYNOPSIS

DESCRIPTION

OPTIONS

SIMPLE EXAMPLES

ADVANCED EXAMPLES

TYPE GENERATORS IN LUA

VAR ARGS

PRIMITIVE GENERATORS

THE GENERATED CODE

EXIT CODE

BUGS

AUTHOR

COPYRIGHT

SEE ALSO