06 Mar 2013

Infinite loop

06 Mar 2013

An infinite loop is a loop whose break condition is never fulfilled. You should distinguish between infinite loops written purposefully and those created through a programming mistake.

We will further discuss the second type of infinite loops caused by mistakes in C/C++ programs.

Here is the first sample of this type of errors.

void CXmlReader::UnsafePutCharsBack(
  const TCHAR* pChars, size_t nNumChars)
{
  if (nNumChars == 0)
    return;
  for (size_t nCharPos = nNumChars - 1;
       nCharPos >= 0;
       --nCharPos)
    UnsafePutCharBack(pChars[nCharPos]);
}

The 'nCharPos >= 0' condition is always true because the nCharPos variable has the size_t type. This is an unsigned type, which means that the variable is always above or equal to zero. That's why the loop becomes an infinite one.

Have a look at one more example of a loop that may become infinite.

size_t n;
unsigned i;
for (i = 0; i != n; ++i)
{
  ...
}

The error in this case may reveal itself on the 64-bit platform if the number of items being processed is bigger than UINT_MAX (4294967295). If the 'n' variable is bigger than UINT_MAX (4294967295), the 'i != n' condition will always be true. An overflow will occur at the next step, and the 'i' variable will be zeroed again. It will never become equal to the 'n' variable.

Note. The type of 64-bit errors described here is pretty tricky. The point is that the compiler sometimes builds a terminable loop while optimizing the code. As a result, the error becomes an intermittent one and reveals itself depending on compiler settings and other factors. To learn more about this interesting issue see the article "A 64-bit horse that can count".

These errors are well diagnosed by static analyzers already at the stage of program writing.