Re: gcc-3.0: Obvious infinite recursion not detected

[Fergus Henderson <fjh at cs dot mu dot oz dot au>]

On 05-Jul-2001, Alexandre Oliva <aoliva@redhat.com> wrote:
> On Jul  5, 2001, Ryszard Kabatek <Ryszard.Kabatek@softax.pl> wrote:
> 
> > but the compiler does not warn.
> 
> And why should it?

Such a warning would certainly be useful, since infinite recursion
of this kind is almost always accidental.

> What do you suggest the warning to be?

The Mercury compiler issues a warning of the form

	foo.m:123: Warning: recursive call will lead to infinite recursion.

for cases like this.

> Under what conditions would it trigger?

For the Mercury compiler, the conditions are that all of the following hold:
	- the call is to the same procedure that the call occurs in
	- the input arguments in the call are the same as the input parameters
	  for the calling procedure

This condition is very easy to check, since it can be done purely locally;
the compiler doesn't need to do any data-flow analysis or anything like that.

Unfortunately this condition relies on the side effect free nature of Mercury.
It's not quite so easy in languages like C/C++, where you can have loops
written using side effects that modify the termination condition of the loop;
in such languages, this condition is not sufficient to guarantee that the
recursive call will lead to infinite recursion, so using this condition as
the trigger for a warning would lead to too many false positives.

However, a sufficient condition would be that in addition to the
conditions mentioned earlier, there are no side effects between the
start of the function and the call.  (By side effects, I mean writes to
memory, inline asm, or calls to unknown functions.)  That condition
would have caught the example posted by the original poster Ryszard
Kabatek <Ryszard.Kabatek@softax.pl>.  

But this would be more difficult to implement than the Mercury
compiler's warning, and would catch fewer cases; I'm not sure if it's
really worth the effort.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.