[Iterator Adaptors] Bug in filter_iterator_policies

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-12-24 10:52:19

Hello,
  There's a bug in filter_iterator_policies, where the predicate may not be 
satisfied for the underlying iterator under extreme circumstances. The 
problem is here:

template <class IteratorAdaptor1, class IteratorAdaptor2>
bool equal(const IteratorAdaptor1& x, const IteratorAdaptor2& y) const
  { return x.base() == y.base(); }

Consider the following code, for "first" and "last" being iterators with a 
filter_iterator somewhere in them:

while (first != last)
  *first++;

Now make *first an operation that can modify the result of the predicate on 
the next iterator in the sequence. Then we have:

first++ advances the underlying iterator, then satisfies the predicate. A 
copy of the previous iterator is returned

*first dereferences the previous iterator, possibly changing the result of 
the predicates in-between the old position and the new position.

One simple fix is to instead use:

template <class IteratorAdaptor1, class IteratorAdaptor2>
bool equal(const IteratorAdaptor1& x, const IteratorAdaptor2& y) const
{ 
  satisfy_predicate(const_cast<Iterator&>(x.base()));
  satisfy_predicate(const_cast<Iterator&>(y.base()));
  return x.base() == y.base(); 
}

This fix will work well with one additional (reasonable) restriction on the 
predicate: if the predicate ever returns false for an iterator, all 
successive predicate calls for that iterator must return false.

Just to prove that I'm not crying wolf, go ahead and look at the 
deletion_test testcase in the "current" (November 25) Boost.Signals library. 
I had precisely the same bug in the slot call iterator.

I can check in the fix and documentation of the above limitation, or provide 
a real patch.

        Doug