# 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 [&#10029;&#10029;] 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.* &square; ##### Exercise: black box test rest [&#10029;&#10029;&#10029;] 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. &square; ##### Exercise: fix ListSet [&#10029;&#10029;&#10029;] 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. &square; ## 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 [&#10029;] 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. &square; ##### Exercise: glass box test [&#10029;&#10029;&#10029;] Add more OUnit test cases to test_sorts.ml, until you have achieved as close to 100% coverage of sort.ml as possible. &square; ##### Exercise: set glass box [&#10029;&#10029;&#10029;, 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. &square; ##### Exercise: Enigma glass box [&#10029;&#10029;&#10029;&#10029;] 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! &square; ## 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&emacr;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 [&#10029;] 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? &square; Although for purposes of security and cryptography a PRNG leads to terrible vulnerabilities, for other purposes&mdash;including testing and simulation&mdash;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 [&#10029;] Start a new session of utop. Enter the following:  # let s1 = Random.get_state ();; val s1 : Random.State.t = <abstr> # let s2 = Random.State.copy s1;; val s2 : Random.State.t = <abstr>  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? &square; 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 [&#10029;] 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? &square; ## Randomized testing An [optional lab on randomized testing](qcheck_lab.html) is available for your enrichment.