Re: [boost] [Iterator Adaptors] Bug in filter_iterator_policies

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2001-12-24 13:46:01

I'm a little nervous about this change: what if the one-past-the-end
iterator for a range fails to satisfy the predicate?

----- Original Message -----
From: "Douglas Gregor" <gregod_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, December 24, 2001 10:52 AM
Subject: [boost] [Iterator Adaptors] Bug in filter_iterator_policies

> 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
>
> Info: http://www.boost.org  Send unsubscribe requests to:
<mailto:boost-unsubscribe_at_[hidden]>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>