General plan for testing

[Quincunx271]

We have very few unit or integration tests. This is something we really should change. I've lost count of the number of times that graph transformations appeared to be having no effect, but it turned out to be due to a bug, bugs which may have been caught if we had tests.

Previously, the assumption was that running our algorithms over large benchmark suites was a substitute for proper tests. However, this only works if it's easy to determine correctness. Yes, we have validation-test. However, validation-test does not detect all possible errors. For the case of graph transformations, most of the bugs I worked out were not things which validation-test caught, and those which it did catch were difficult to determine the cause of. I think it is highly beneficial to write tests for our code.

Another point to mention is that refactoring is difficult without tests. Without tests, it is hard to tell if a refactor will break existing code.

---

There are a few kinds of things I can think of which need testing:

• Regular code. This is things like our custom data structures, straightforward algorithms, etc.
• New algorithms. Of course, we have new algorithms due to this being a research project. These are much harder to test. I think we can still test individual components of the algorithms even if writing a test for the entire algorithm is too difficult. For example, I believe that the graph transformations conditions can be tested on its own; the iterative component is hard enough to test that it makes sense to defer to the status quo for testing it.
• Util code. These scripts can have bugs. In fact, around half of the bugs I found were actually bugs in these scripts, although they were often uncovered by graph transformations breaking old assumptions about them. These should be tested. I recommend pytest.