Technical non-terminating condition in a loop

Question

Most of us know that a loop should not have a non-terminating condition. For example, this C# loop has a non-terminating condition: any even value of i. This is an obvious logic error.

void CountByTwosStartingAt(byte i) { // If i is even, it never exceeds 254
    for(; i < 255; i += 2) { 
        Console.WriteLine(i);
    }
}

Sometimes there are edge cases that are extremely unlikeley, but technically constitute non-exiting conditions (stack overflows and out-of-memory errors aside). Suppose you have a function that counts the number of sequential zeros in a stream:

int CountZeros(Stream s) {
    int total = 0;
    while(s.ReadByte() == 0) total++;
    return total;
}

Now, suppose you feed it this thing:

class InfiniteEmptyStream:Stream
{
    // ... Other members ...

    public override int Read(byte[] buffer, int offset, int count) {      
        Array.Clear(buffer, offset, count); // Output zeros
        return count; // Never returns -1 (end of stream)
    }
}

Or more realistically, maybe a stream that returns data from external hardware, which in certain cases might return lots of zeros (such as a game controller sitting on your desk). Either way we have an infinite loop. This particular non-terminating condition stands out, but sometimes they don't.

A completely real-world example as in an app I'm writing. An endless stream of zeros will be deserialized into infinite "empty" objects (until the collection class or GC throws an exception because I've exceeded two billion items). But this would be a completely unexpected circumstance (considering my data source).

How important is it to have absolutely no non-terminating conditions? How much does this affect "robustness?" Does it matter if they are only "theoretically" non-terminating (is it okay if an exception represents an implicit terminating condition)? Does it matter whether the app is commercial? If it is publicly distributed? Does it matter if the problematic code is in no way accessible through a public interface/API?

Edit: One of the primary concerns I have is unforseen logic errors that can create the non-terminating condition. If, as a rule, you ensure there are no non-terminating conditions, you can identify or handle these logic errors more gracefully, but is it worth it? And when? This is a concern orthogonal to trust.

Answer 1

You either "trust" your data source, or you don't.

If you trust it, then probably you want to make a best effort to process the data, no matter what it is. If it sends you zeros for ever, then it has posed you a problem too big for your resources to solve, and you expend all your resources on it and fail. You say this is "completely unexpected", so the question is whether it's OK for it to merely be "completely unexpected" for your application to fall over because it's out of memory. Or does it need to actually be impossible?

If you don't trust your data source, then you might want to put an artificial limit on the size of problem you will attempt, in order to fail before your system runs out of memory.

In either case it might be possible to write your app in such a way that you recover gracefully from an out-of-memory exception.

Either way it's a robustness issue, but falling over because the problem is too big to solve (your task is impossible) is usually considered more acceptable than falling over because some malicious user is sending you a stream of zeros (you accepted an impossible task from some script-kiddie DoS attacker).

Answer 2

Things like that have to decided on a case-by-case basis. If may make sense to have additional sanity checks, but it is too much work too make every piece of code completely foolproof; and it is not always possible to anticipate what fools come up with.

Answer 3

You either "trust" your data source, or you don't.

I'd say that you either "support" the software being used with that data source, or you don't. For example I've seen software which doesn't handle an insufficient-memory condition: but insufficient memory isn't "supported" for that software (or less specifically it isn't supported for that system); so, for that system, if an insufficient-memory condition occurs, the fix is to reduce the load on the system or to increase the memory (not to fix the software). For that system, handling insufficient memory isn't a requirement: what is a requirements is to manage the load put on the system, and to provide sufficient memory for that given load.

Answer 4

How important is it to have absolutely no non-terminating conditions?

It isn't important at all. That is, it's not a goal by itself. The important thing is that the code correctly implements the spec. For example, an interactive shell may have a bug if the main loop does terminate.

In the scenario you're describing, the problem of infinite zeros is actually a special case of memory exhaustion. It's not a theoretical question but something that can actually happen. You should decide how to handle this.