So I'm writing a new sorting function for OIDs. What OIDs are is not important right now ... the important things are that they're strings that hold dot-separated sequences of numbers, like 1.3.6.1 (the Internet OID) and because the sequence of numbers is significant, OIDs cannot be sorted alphabetically (because 1.1 should be followed by 1.2, not by 1.10 as naive alphabetic sorting would imply).

Now, there's a lot to be done to update our software to sort OIDs correctly, but, being trained as an AI programmer, I started by breaking the problem down into its smallest possible parts --- namely, an OID comparison function. And, being a good modern Java programmer, I started with a JUnit unit test which enabled me to check my comparison function.

For those who don't know, JUnit tests are functions in a software module that all start with the word "test", like testLengthOneOIDs or testOIDsVsBlanks. Initially I just had a few handwritten tests - 1 is less than 1.1, which is less than 1.2, which is less than 1.12, which is less than 1.100 but greater than 1.2.1, and so on. These tests are complicated little stanzas of code, and being trained as a good AI programmer, I kept breaking things apart, writing a validateEquality and validateOrdering functions that automatically checked two OIDs for the right ordering. The idea, you see is that once I've written one correct test, I now have a tool to write many more correct tests, and don't have to worry about typos causing failures in later tests.

But still, there were dozens and dozens of cases to test. Then I had a brainflash: rather than writing a whole bunch of tests, one for each pair I wanted to examine, why not write an array with a list of OIDs in the right order (1.1, 1.2, 1.2.1, 1.10, 1.21, 1.30.1, etc) and then write a simple pair of for loops that test each one for the right sequence?

So I did. The outer loop went through every OID in the given list, and the second one went through every OID preceding it in the list to make sure that the comparison worked. That is, for three OIDs, the outer loop would go through items 1, 2 and 3. On the first loop, the inner loop would just go through item 1, but on the second it would go through 1 and 2, and then finally 1, 2, and 3, testing all combinations of OIDs.

SO I wrote that, as well as three or four lists of OIDs. And everything passed with flying colors. So I added that code to my OID utility library, built my sorter exploiting Java's wonderful Collections framework, and sorted the OIDs to call it good. It even ran smoothly at first.

Until I added some new code to do searches. This changed the list of OIDs feeding into my sorting algorithm and --- BOOM! --- Java compains that I'm asking for the fifth item of a four item list. Bad Java juju. What gives?

Well, it's simple. My cute little validateOrdering function should have been called validateLesserThan, because it implicitly assumed that the first OID it was given was lesser and the second OID was greater. However, that test doesn't test all cases of the algorithm --- to do a sort using Java's Collections framework, you need to generate a *numerical* comparision: the compare function is not asking whether a is less than b, true or false, but instead asking for the *sign* of the *difference* --- so that compare of (1,2) is -1, compare of (2,2) is 0, and compare of (2,1) is +1. This is the mathematical signum function.

My test was testing only lesser than and equality --- two branches, not the three branches of the signum. And, sure enough, when I augmented my validateOrdering tester to include a "desired result" parameter so you could specify you wanted lesser-than (-1), equality (0), or greater-than (+1) --- BOOM --- I found an error with my unit tester. When the comparison algorithm checked to see if "1.2.3" was greater than "1", it had an off-by-one error, assuming the second OID had one more element in its list than it actually had. So Java fall down and go boom.

So the POINT? Don't assume. It's a great idea to write unit tests, and an even better idea to make them comprehensive. But when you do so, think carefully about what you're testing --- make sure that you're testing all possible branches of the function at hand, or it may blow up on you later when some new --- possibly entirely unrelated function --- rips the rug of your assumptions out from beneath your feet of clay.

-the Centaur

Labels: Webworks