Debugging with Contracts

To finish up this series on contract checking (see previous post), I wanted to show an example of code with contract checks in it. The fun part is that, in the course of creating the example, I ended up practicing what I’ve been preaching – using contract checks as a debugging tool.

When we left off, I had written an example test for a routine that calculates the permutation needed to sort an array, and shown how much simpler it is if the validation code is moved into the routine as contract checks. What I didn’t have room to do is show the actual routine with the contract checks in. My original intent was to only show the contract checks in the routine, but I thought it would be more interesting to show real, working code with the conceptual error that might be easy for someone to fall into: forgetting that the array to be sorted might have duplicate entries. So I started up my C# Visual Studio session and rattled off the routine. Here’s what I came up with:

Actually, I first wrote the non-contract checks block to go with test1 in the previous post, then copied it into PermutationArray2 and added the contract check section for use in test2 and test3. You’ll notice that I very carefully picked a clunky algorithm that first sorts the values then searches through the list for the index of each values so that I could demonstrate how the algorithm is fatally flawed based on the incorrect assumption of unique values in the input array. Then I ran my tests with test2 first, then test3 and finally test1, expecting to have the contract assertion at line 55 in validation #2 fail when test3 was run. Alas, it was not to be….

What happened is that I got an IndexOutOfRangeException that I hadn’t expected at line 53 in validation #2 when test2 was run. Oops. Looking at it in the debugger, I noticed that permutationIndices[0] was equal to 9. Since 9 just happens to be the number of elements in the input list, I had a pretty strong suspicion that the while loop at line 34 had overrun the array and exited due to the test against permutationIndices.Length.

So I put in a contract check to test this.

Now here’s the interesting part. When I first wrote the code for test1, I really wanted to put a comment at line 39 saying something like “we should always find a value, so the index shouldn’t ever overrun the loop”. And whenever I put a comment like that in, it’s second nature to put in a contract check that ensures that what I’m claiming to be true really is true. But I didn’t do it – not even the comment – because I was writing example code for test1, which was the “prefer external validation to contract checks” version and I didn’t want to inject “contract-y” stuff. And it turns out that that was exactly the right contract check to stick in to localize this stupid typo happy-trail (STHT) bug (there were actually two of these). Because I didn’t have this contract check in place, I had to work harder in the debugger to figure out where the bug was. In this case it wasn’t that much harder but it is easy to imagine much nastier cases where the principle holds. So that’s the test I added.

Here’s the routine I ended up with after working through and fixing both STHT bugs (the contract checks are the same):

You can see that the new version has the new contract check that I’ve been talking about – it was put in to verify my conjecture that the loop was overrunning. And because it was put in as a contract check, it has incrementally improved the code – the same mistake won’t be able to slip in again and if there’s some weird data configuration that triggers the same bug it will be detected and localized as soon as it’s run with contract checks turned on.

You’ll notice that I called both the bugs “happy trail” bugs. This is because I wanted to emphasis that there are two gross categories of bugs: the ones that you’re going to find no matter what you do (happy trail), and the ones I’ve been emphasizing in these contract check posts – the nasty, subtle, data-dependent corner case ones. The bug that still remains is the nasty type – test2 works fine, but test3 fails the contract check at line 55, and fixing it will require either a complete rework or forbidding duplicates. I hope I’ve convinced people in this series of posts that either unit- or contract-based-testing will detect the happy trail bugs, but that contract checks are much more powerful when dealing with the nasty ones.