I wrote a piece of code recently to follow a linked list. We were linking records together in a way that a few records would normally be grouped together in a tree, with one parent above them all. However, because of the way the records were linked, it was also possible for a loop to occur -- that is A would reference B, B would reference C, and C would reference A.

If there was a loop, it would be a small one (less than 5 records total). Our code that read the loop would run forever if it were to encounter a loop (and eventually overflow the stack). Since it would be a very small loop, and it was not reasonably possible to prevent a loop from happening, we had to handle it in the reader. Our reader was recursive, so we passed in an array to the recursive call, and it would constantly add the ID being looked at. At each recursive step, we'd check if we had already seen the ID we were about to look at, and if we found a loop, we exited accordingly.

We wanted to write a test to ensure that our code would never follow a loop. The only way to do this was to write a test that created a loop of records, and run the function on the loop. If the loop-blocking code worked, it exited instantly. But if the code were to not work, our test would run for a very long time before we overflow the stack. This is essentially testing the halting problem, a famous computer science problem with no real solution, and no chance of ever being solved.

The most straightforward solution available was this:

If you want to put this in a CI system, a more heavy-duty way of doing this would be to start two processes: one that runs the possible infinite loop, and one that raises an exception after N seconds if the first process hasn't completed.

Filed under: hey it works