Isn't "return" supposed to exit a function?

I wrote a generic function for finding out if one container sequence can be found inside another:

Code:

template <class Container>
bool is_in(const Container& c1, const Container& c2)
{
  typename Container::const_iterator it, prev_find, this_find;
  it = c1.begin();
  prev_find = find(c2.begin(), c2.end(), *it++);
  for(; it != c1.end(); it++)
    {
      this_find = find(++prev_find, c2.end(), *it);
      if(prev_find != this_find || this_find == c2.end())
	{
	  return false;
	}
    }
  return true;
}

Problem is, when it does reach the conditional inside the loop, and goes inside it, it "returns false", exits the loop, then "returns true". I followed it inside a debugger, and that's exactly what it did before my own eyes.

I always that if a program hits a "return" directive, it's supposed to exit the function no matter what. What am I doing wrong here?

Are you ABSOLUTELY sure that it actually returns true?
I have seen [every day when I debug my target code] that the compiler "visits" the return in another place because it's combined the actual exit of the function, but it doesn't mean that the return value is "incorrect" - it's just that the debugger isn't able to connect the fact that you are in the "return false" code, but you are actually in the common part where the function exits - there is always some cleanup at the end of a function, and most of the time, this is not duplicated, as that saves some code-space.

What compiler are you using? Could you produce the assembler listing of the code, and post it here?

--
Mats

Yes, I'm quite sure it returns true. The problem is that it doesn't return false. And I checked inside a debugger that it does go inside the conditional statement.

I hardly know anything about assembly, so rather than just paste something that might turn out to be completely irrelevant, I've attached the assembly output. The extension is .cc, but it's just a .s file generated by the compiler.

I use g++ 4.0.3 and my debugger is gdb.

Thanks for the help.

I've attached a slightly different assembly output. It's the same code but compiled with the -ggdb3 option. This is what I was debugging with, and I have had one or two experiences where the debugging version did different things compared to the optimized version (can't exactly remember where, though) so maybe this is different.

It's a tarball compressed with bzip2, so just remove the cc extension.

Code:

_Z5is_inISsEbRKT_S2_:
.LFB2015:
	pushl	%ebp
.LCFI134:
	movl	%esp, %ebp
.LCFI135:
	pushl	%ebx
.LCFI136:
	subl	$116, %esp
.LCFI137:
	leal	-32(%ebp), %eax
	movl	%eax, (%esp)
[snip lots of setup code]
	call	_ZN9__gnu_cxxeqIPKcSsEEbRKNS_17__normal_iteratorIT_T0_EES8_
	testb	%al, %al
	je	.L132
.L130:
	movb	$1, -97(%ebp)
	jmp	.L133
.L132:
	movb	$0, -97(%ebp)
.L133:
	movzbl	-97(%ebp), %eax
	testb	%al, %al
	je	.L134
	movl	$0, -96(%ebp)
	jmp	.L136
.L134:
	leal	-88(%ebp), %edx
	movl	$0, 8(%esp)
	leal	-32(%ebp), %eax
	movl	%eax, 4(%esp)
	movl	%edx, (%esp)
	call	_ZN9__gnu_cxx17__normal_iteratorIPKcSsEppEi
	subl	$4, %esp
.L128:
	leal	-92(%ebp), %edx
	movl	8(%ebp), %eax
	movl	%eax, 4(%esp)
	movl	%edx, (%esp)
	call	_ZNKSs3endEv
	subl	$4, %esp
	movl	-92(%ebp), %eax
	movl	%eax, -16(%ebp)
	leal	-16(%ebp), %eax
	movl	%eax, 4(%esp)
	leal	-32(%ebp), %eax
	movl	%eax, (%esp)
	call	_ZN9__gnu_cxxneIPKcSsEEbRKNS_17__normal_iteratorIT_T0_EES8_
	testb	%al, %al
	jne	.L129
	movl	$1, -96(%ebp)
.L136:
	movl	-96(%ebp), %eax
	movl	-4(%ebp), %ebx
	leave
	ret

If you look at the above code, it has a jump (RED) to L136, which is the exit of the function. -96(%ebp) is set to 0 just before that jump, and then -96(%ebp) is moved to %eax, which holds the return value - so I'm 99.9% sure that it's returning FALSE in this case.

But the code at L136 (also) belongs to "return true", so when you step through it with the debugger, you will possibly step onto the "return true" line because the debugger doesn't actually understand the difference.

--
Mats

I don't know what to say. Thanks for going to all the trouble. What I discovered was that the code in my main routine was printing out the same stuff for when it returned either true or false. So you are right. It was returning false. It also proves that I need to sleep.

Many compilers implement single exit points in the generated code (as the example matsp shows), whereby return statements in the middle of the code are in fact jumps to the single exit point (with the appropriate return result already stored).

This does lead to a bit of strangeness when single stepping the code, but you should find the correct result is indeed returned when you finally step out of the function.

It makes it even worse that the particular compiler I use, it puts the FIRST return statement as the "line of this code", when the return is actually at the bottom of the function. It looks really strange when you are in the middle of a loop in the bottom of the function, and all of a sudden you are back at line 3 of the function where it returns "bad parameter" because input X was zero...

I wish the compiler + debugger could understand this particular scenario, and give good hints on where it was.

Just get used to it.

--
Mats