Wednesday, 16 April 2014

Guideline 6. Ensure entry and exit conditions in loops


Ensure entry and exit conditions in loops. Write code  that guarantees that loops will be entered and exited correctly. Be aware of the possibility of an infinite loop and prevent it.


More about loops

Guideline #5 was focused in discussing how for loops should be. But it also contained some discussion about choosing a loop structure. Let's review it:

A for loop makes sense when you repeat an action for a known number of times, or for all the elements of a known set. It makes sense when you have a loop counter - one variable which is initialized in the initialization, evaluated in the condition, and incremented (or decremented) by a constant amount in the expression. (...)
If you don't know the number of times or the total set of elements for which you're going to do something, and what's essential in your looping activity is a certain condition which will at some point interrupt it, you'd better chose one of the other two looping structures: a while or a do ... while. It is easy to choose between them: the former checks the condition beforehand and thus may never perform the repeated action (if the condition happens to be false at the beginning), and the latter executes the repeated action at least once and then checks the condition to see if it must keep repeating it, or just finish.

After this discussion the guideline set the focus back on the for loop. This is because the use of a specific variable called the loop counter, possibly combined with other loop control variables, introduces extra complexity and is a frequent source of defects in for loops.

However, what if we don't use a for loop in the first place? Isn't there a guideline to follow? Can't things go wrong in a while or a do ... while loop? Don't worry: They can.

There are at least two questions you should always ask yourself while you're writing code for a loop - and ask yourself again after writing it. Here they are:
  1. Will the loop body be entered at least once?
  2. Will the loop be exited?
Let's discuss them separately.

Entering the loop

If your loop is a do .. while, the first question has an obvious answer: yes. It will be entered at least once (as long as the execution point reaches it, of course). That's why you chose that structure in the first place.

If it is a while or a for, you should ask yourself that first question. Review the loop condition thoroughly and think about the possibility of it being false at the very beginning of the loop. In that case, the loop body would never be executed.

Is that possibility perfectly correct in the context of your function, or is it something you should avoid? If the latter is true, then you should write the specific code to handle that.

Exiting the loop

The loop will be exited when the condition is evaluated to false. The condition is evaluated once for each iteration. Will it eventually become false? Are you totally sure that this will happen? Can you guarantee it?

There are at least two possible sources of infinite loops that you should try to avoid. You will see them in the examples below.


Example 1

This is an infinite loop:

for (unsigned char c = 0 ; c < 256; ++c) {
    std::cout << c;

The range of the type unsigned char is from 0 to 255. In C++ addition, unsigned integer types (and unsigned char is an integer type, by the way) wrap around when they exceed their upper numeric limit, so if the value of c is 255, ++c "increments" it to 0. From there it will go up again, if you keep incrementing it, until it reaches 255, from where it will wrap around again to 0, in an infinite loop which would be too long to write completely.

This behaviour of the C++ arithmetic is neither "right" or "wrong" - it's just how the language is specified. You, as a programmer, must be aware of it and write your code so that it does the right things.

Always keep in mind the numeric limits of the types you use. The comparison c < 256 above violates the guideline against implicit type conversions (see Guideline #2), because 256 is obviously not a value of type unsigned char. It will probably cause a compiler warning, such as "Constant out of range in comparison" (and you should fix all compiler warnings), but anyway, you should be aware of the semantics of the types you use in the first place, including their limits.

Following Guideline #5 you will avoid another source of infinite loops: to play with the value of the loop counter inside the loop body. Do not modify the loop counter in the loop body, and it will eventually reach the limit value of the loop condition so that it can become false.

Example 2

int x = 0;
int y = 0;
bool sucess = false;
while (!success) {
    success = do(x, y);

Whatever the function do does, and whatever success means, this code doesn't look very safe. You will keep trying forever until something succeeds and do returns true. Are you sure there isn't another terminating condition? If you are, go ahead, but it is not a good idea to have a loop in which termination is not evident.

This looks a bit better:

int x = 0;
int y = 0;
bool sucess = false;
int iterations = 0;
const int max_iterations = 10;
while (!success && iterations < max_iterations ) {
    success = do(x, y);

A maximum number of retries, a second boolean variable which will obviously change its value at some point, even a timer... Anything is better than just waiting for a complex operation (creating something, finding something, etc.) to succeed one day. In short, your design should guarantee the termination of the loop, not just suggest it.

But I don't want it to end

If you actually want an infinite loop, because its purpose is to actually run forever or until some external event interrupts it, you should stress it right from the start.

while (true)

Using this style you avoid the confusion between the chosen loops designed to last forever, and the more run of the mill loops which are meant to come to an end.


See the page Bibliography for details of the referenced materials.

[McCONNELL 2004] This book discusses loops in Chapter 16: "Loops" (pages 367-389).

[MEYER 1997] One day we'll talk about the design by contract, which is developed in this book like nowhere else I know. Meyer introduces the concepts of loop invariant and loop variant in Chapter 11: "Design by Contract: Building reliable software", section 11.12 "Loop invariants and variants". These concepts are thetheoretic background which allows you to actually prove that your loops will come to an end at their due time.