# Testing
In this lab, you will write some black-box tests against an interface,
do glass-box testing with a tool called Bisect, and learn a little about
random number generation. That last topic will set you up to do an
optional extension of this lab, which is about a library
called QCheck that does randomized testing.
To get started, download [the provided code for this lab](code.zip).
## Black-box testing
Find `sets.ml` in the code for this lab. It implements sets with a list.
Read the `Set` signature at the top of it; **do not** read down
to the end of the file where that signature is implemented
as `ListSet`.
##### Exercise: black box test [✭✭]
Based on the specification comments of `Set`, write an OUnit test suite
for `ListSet` that does black-box testing of `size` and `insert`. We've
already got you started in the provided file `test_sets.ml`. Write
enough tests to detect at least one bug in both `size` and `insert`
without ever reading their implementations. *Hint: `empty` and
`to_list` are both correctly implemented, so you can rely on those.*
□
##### Exercise: black box test rest [✭✭✭]
Finish writing a black-box OUnit test suite for the rest of the
functions in `ListSet`. Find at least one bug in every function
except `empty` and `to_list`.
□
##### Exercise: fix ListSet [✭✭✭]
After you have found at least one bug in each function, go read the
implementation of `ListSet`. Fix all the bugs in it and make your test
suite pass.
□
## Glass-box testing
It would be difficult to determine by yourself how much coverage
a test suite achieves, especially against a large code base. Luckily,
there are tools that can compute this for you. OCaml has a tool called
[Bisect][bisect], which works as follows:
[bisect]: http://bisect.x9c.fr/
- You compile your code using Bisect as part of the compilation process.
It *instruments* your code, mainly by inserting additional
expressions to be evaluated.
- You run your code. The instrumentation that Bisect inserted causes
your program to do something in addition to whatever functionality
you programmed yourself: the program will now record which
expressions from the source code actually get executed at run time,
and which do not. Also, the program will now produce an output
file named `bisectNNNN.out` that contains that information.
A new output file will be created at each invocation, the first
being `bisect0001.out`, the second being `bisect0002.out`, etc.
- You run a tool called `bisect-report` on that output file. It
produces HTML showing you which parts of your code got executed,
and which did not.
How does that help with computing coverage of a test suite? If you
run your OUnit test suite, the test cases in it will cause the code in
whatever functions they test to be executed. If you don't have
enough test cases, some code in your functions will never be
executed. The report produced by Bisect will show you exactly
what code that is. You can then design new glass-box test cases
to cause that code to execute, add them to your OUnit suite,
and create a new Bisect report to confirm that the code really
did get executed.
To get started with Bisect, we need to install it. Run this command:
```
$ opam install -y bisect
```
##### Exercise: bisect sorts [✭]
Go to the provided code for this lab in the `sorts` folder. You will
find an implementation of insertion sort, merge sort, and the beginning
of a test suite.
The `_tags` file there includes the following:
```
true: package(oUnit), package(bisect), syntax(camlp4o), syntax(bisect_pp)
```
The latter three tags are what enable compilation with Bisect.
Run
```
$ ocamlbuild -use-ocamlfind test_sorts.byte
```
to build the test suite, and
```
$ ./test_sorts.byte -runner sequential
```
to run it. Note the additional flag `-runner sequential` that we don't normally
have to supply when running the test suite. It causes OUnit to run all the
tests sequentially, instead of trying to run many of them in parallel. The latter
is good for speeding up large test suites, but it turns out Bisect isn't designed
to handle that kind of parallelism.
Running the suite will cause `bisect0001.out` (assuming it's your first
run of the suite) to be produced.
Next run
```
$ bisect-report -I _build -html report bisect0001.out
```
to generate the Bisect report from your test suite
execution.
Open the file `report/index.html` in a web browser. Look
at the per-file coverage; you'll see we've managed to
test only 4% of `sorts.ml` with our test suite so far:
![](perfile.png)
Click on the link in that report (the actual report, not
the screenshot above) for `sorts.ml`.
![](inssort.png)
You'll see that we've managed to cover one line of the source
code so far with our test suite. The covered lines are colored
green, and the uncovered lines are red.
□
##### Exercise: glass box test [✭✭✭]
Add more OUnit test cases to `test_sorts.ml`, until you have
achieved as close to 100% coverage of `sort.ml` as possible.
□
##### Exercise: set glass box [✭✭✭, optional]
Go back to the set implementation that you black-box tested at
the beginning of this lab. Achieve as close to 100% code coverage as possible.
□
##### Exercise: Enigma glass box [✭✭✭✭]
Go back to your A1 solution. Find out what your code coverage was
from your test suite. If it wasn't 100%, add more unit tests!
□
## Random number generation
Most languages provide the facility to generate random numbers. In
truth, these generators are usually not truly random (in the sense that
they are completely unpredictable) but in fact are
[*pseudorandom*][prng]: the sequence of numbers they generate pass good
statistical tests to ensure there is no discernible pattern in them, but the
sequence itself is a deterministic function of an initial *seed* value.
(Recall that the prefix *pseudo* is from the Greek *pseudēs* meaning "false".)
[Java][java-random] and [Python][python-random] both provide
pseudorandom number generators (PRNGs). So does OCaml in the standard library's
[`Random` module][random].
[prng]: https://en.wikipedia.org/wiki/Pseudorandom_number_generator
[java-random]: https://docs.oracle.com/javase/8/docs/api/java/util/Random.html
[python-random]: https://docs.python.org/3/library/random.html
[random]: http://caml.inria.fr/pub/docs/manual-ocaml/libref/Random.html
##### Exercise: pseudorandom [✭]
Start a new session of utop. Enter the following:
```
# Random.int 100;;
# Random.int 100;;
# Random.int 100;;
```
Write down the responses that you get. Each is a pseudorandom integer \\(i\\) such that
\\(0 \leq i \lt 100\\).
Now quit utop and start another new session. Enter the same phrases as above again.
You will get the same responses as last time. Unless your OCaml installation is
different from the VM's, they will be: 44, 85, 82. Chances are that everyone in
the class will get those same numbers. Not exactly unpredictable, eh?
□
Although for purposes of security and cryptography a PRNG leads to terrible vulnerabilities,
for other purposes—including testing and simulation—PRNGs are just fine.
In fact their predictability can even be useful: given the same initial seed, a PRNG
will always produce the same sequence of pseudorandom numbers, leading to the ability
to repeat a particular sequence of tests or a particular simulation.
The way a PRNG works in general is that it initializes a *state* that it keeps internally
from the initial seed. From then on, each time the PRNG generates a new value, it
imperatively updates that state. The `Random` module in fact makes it possible to
manipulate that state in limited ways.
##### Exercise: PRNG state [✭]
Start a new session of utop. Enter the following:
```
# let s1 = Random.get_state ();;
val s1 : Random.State.t =
# let s2 = Random.State.copy s1;;
val s2 : Random.State.t =
```
Now let's use a different function, `Random.State.int`. It is like
`Random.int`, except that it explicitly accepts a state argument instead
of using the default state encapsulated in the `Random` structure:
```
# Random.State.int s1 100;;
# Random.State.int s1 100;;
# Random.State.int s1 100;;
# Random.State.int s2 100;;
# Random.State.int s2 100;;
# Random.State.int s2 100;;
```
What do you notice about the sequence of values that the six expressions above produces?
□
If you want a less predictable sequence of values, then you can change
the seed. The functions `Random.self_init` and
`Random.State.make_self_init` will choose a "random" seed to initialize
the state. They do so by sampling from a special Unix file named
[`/dev/urandom`][urandom], which is meant to provide as close to true
randomness as a computer can.
[urandom]: https://en.wikipedia.org/wiki//dev/random
##### Exercise: random seed [✭]
Start a new session of utop. Enter the following:
```
# Random.self_init ();;
# Random.int 100;;
# Random.int 100;;
# Random.int 100;;
```
Now repeat that a second time (it doesn't matter whether you exit utop
or not in between). What do you notice about the sequence of values
that is produced?
□
## Randomized testing
An [optional lab on randomized testing](qcheck_lab.html) is available
for your enrichment.