Impossible sequence of events

Question

I'm trying to track down a mysterious iterator problem in a for loop. I get an error in the iterator's operator!= which generally means that the iterators being compared do not belong to the same container. Tracing into Microsoft's implementation of the library, operator!= calls operator== where this test is true:

    bool operator==(const _Myiter& _Right) const
        {   // test for iterator equality
 #if _ITERATOR_DEBUG_LEVEL == 2
        if (this->_Getcont() == 0
            || this->_Getcont() != _Right._Getcont())
            {   // report error
            _DEBUG_ERROR("list iterators incompatible");

In an attempt to get more information I wrote this little function to replace my != in the for loop:

template<typename iter>
bool bang_equal(const iter & left, const iter & right)
{
   static int count = 0;
   auto p1 = left._Getcont();
   auto p2 = right._Getcont();
   ATLTRACE("Iterator comparison left _Getcont()=%p right _Getcont()=%p %d\n", p1, p2, ++count);
   MemoryBarrier();
   bool b = left != right;
   MemoryBarrier();
   auto p3 = left._Getcont();
   auto p4 = right._Getcont();
   ATLTRACE("                    left _Getcont()=%p right _Getcont()=%p %d\n", p3, p4, ++count);
   return b;
}

Here's where it gets interesting. I still get the error in the expression left != right and the debugger stops there, but either the first ATLTRACE has been skipped or the second one has run ahead of time! The debugger output has both lines, and the value of count as shown by the debugger matches the last line of output.

Iterator comparison left _Getcont()=07D0B2C8 right _Getcont()=07D0B2C8 2984
                    left _Getcont()=07D0B2C8 right _Getcont()=07D0B2C8 2985
Myprog.exe has triggered a breakpoint.

Looking at the disassembly window shows the instructions in the expected order. I'm stumped. What might be happening?

Answer 1

Finally figured it out. The Microsoft function _Debug_message displays a dialog box asking if you want to Abort, Retry (debug), or Ignore the error. While the dialog box is displayed the message pump is still running, allowing other activity to take place. My function was being called again and this time it ran to completion, generating lots of debug output in the process. If I put an explicit breakpoint on the _DEBUG_ERROR line in the library code I catch the error without additional execution in the background. Looking back at the debug output with the benefit of hindsight I can see that the expected error output was indeed there, just buried so far that I never saw it.

Answer 2

My intuition tells me that Occam's razor is the most likely explanation here: Specifically that you're invalidating the iterator during iteration. The fact that you don't have a ++iter in the for loop further emphasizes that it's not a straight up iteration over every element.

It's probably not directly inside the loop, but the container is likely aliased somewhere within a call chain being called from the loop body - those are pretty easy mistakes to make and absolutely brutal to diagnose. You should at least print the size of the container at every iteration.

If you have access to Linux and a small enough part of code that reproduces the problem you could utilize valgrind to help you hunt down this as well.