[boost] Re: Iterator adaptors <-> boost::bind interaction

From: Aleksey Gurtovoy (agurtovoy_at_[hidden])
Date: 2005-05-24 08:00:17

Following up with more use cases/data before I forget the details.

Aleksey Gurtovoy writes:
> The following code currently fails to compile because of a subtle
> interaction between bind-produced function objects and the current
> implementation of transform_iterator's 'dereference' function (the
> same applies to 'filter_iterator' and most likely the rest of the
> adaptors in the library):
>
>     #include <boost/iterator/transform_iterator.hpp>
>     #include <boost/bind.hpp>
>
>     int add_two( int x ) { return x + 2; }
>
>     int main()
>     {
>         int x[] = { 0 };
>         *boost::make_transform_iterator( 
>              boost::make_transform_iterator( x, boost::bind( &add_two, _1 ) )
>            , boost::bind( &add_two, _1 )
>            );
>     }
>
> The problem here is that the result of 'boost::bind( &add_two, _1 )'
> takes its argument by reference, while transform_iterator's
> 'dereference' implementation is:
>
>     typename super_t::reference dereference() const
>     { return m_f(*this->base()); }
>                  ^^^^^^^^^^^^^
>
> In our case, '*this->base()' produces a temporary 'int' which cannot
> be directly passed to 'm_f'.
>
> Effectively, the issue prevents you from layering any iterator
> adaptors built with 'boost::bind' on top of 'transform_iterator',
> which, needless to say, is BAD.
>
> My sugesstion would be to replace the above with
>
>     typename super_t::reference dereference() const
>     {
>         typename iterator_reference<Iterator>::type x( *this->base() );
>         return m_f( x );
>     }

... which turns out to be not enough to make transform_iterator
usable. For instance, this will still fail:

    #include <boost/iterator/transform_iterator.hpp>
    #include <boost/bind.hpp>
    #include <algorithm>

    int add_two( int x ) { return x + 2; }
    bool is_odd( int x ) { return x % 2; }

    int main()
    {
        int x[] = { 0 };
        std::count_if(
              boost::make_transform_iterator( x, boost::bind( &add_two, _1 ) )
            , boost::make_transform_iterator( x + 1, boost::bind( &add_two, _1 ) )
            , boost::bind( &is_odd, _1 )
            );
    }

I had to dig into our old in-house transform_iterator implementation
to see why _we_ don't have this problem (it's been a long time).
Translating into the boost::transform_iterator terms, basically, what
we do is this:

    template <class UnaryFunction>
    struct function_object_result
        : mpl::if_<
              is_reference< typename UnaryFunction::result_type >
            , typename UnaryFunction::result_type
            , typename UnaryFunction::result_type const
                                               // ^^^^^
            >
    {
    };

This takes care of both the original issue and the earlier snippet.

Unfortunately, this is not the end of the story yet. Another iterator
library's innovation is blending together transform and projection
iterators and using tranformation object's return type to decide
whether to return by value (conventional transform_iterator behavior)
or by reference (conventional projection_iterator behavior). While
conceptually appealing, I'm afraid the folding resulted in a seriously
increased fragility of the user code. It became way too easy to write
an innocently looking transformation that in fact invokes undefined
behavior -- and the latter is not even diagnosed by the most compilers
(neither at compile nor at run time). Consider, for instance, this:

    #include <boost/iterator/transform_iterator.hpp>
    #include <boost/bind.hpp>
    #include <algorithm>

    struct X
    {
        X( int i = 7 ) : i_( i ) {}
        ~X() { this->i_ = -1; }
        int const& get_i() const { return this->i_; }
 
     private:
        int i_;
    };

    struct Y { X x; };
    X make_x( int i ) { return X( i ); }

    int main()
    {
        int i[] = { 8 };
        Y y[1];

        // undefined behavior #1 (returning reference to a temporary)
        int r = *boost::make_transform_iterator(
              boost::make_transform_iterator( i, std::ptr_fun( &make_x ) )
            , std::mem_fun_ref( &X::get_i )
            );

        assert( r == 8 );

        // undefined behavior #2 (returning reference to a temporary)
        r = *boost::make_transform_iterator(
              boost::make_transform_iterator( y, boost::bind( &Y::x, _1 ) )
            , std::mem_fun_ref( &X::get_i )
            );

        assert( r == 7 );
    }

IMO this is way too subtle and error-prone to leave it as
is. Opinions?

-- 
Aleksey Gurtovoy
MetaCommunications Engineering