iterator_adaptor does not work with incomplete Value types

[Joaquín M López Muñoz]

boost::iterator_adaptor doesn't work when the associated Value type is incomplete, at least in MSVC++ 8.0 (my hunch is that the problem is general). The following

#include <boost/iterator/iterator_adaptor.hpp>

template<typename T>
struct my_iterator:
  boost::iterator_adaptor<my_iterator<T>,T*>
{
};

struct foo
{
  my_iterator<foo> it;
};

int main(){}

results in:

...\boost\type_traits\is_pod.hpp(34) : error C2139: 'foo' :
an undefined class is not allowed as an argument to compiler
intrinsic type trait '__is_pod'
    ...\sandbox.cpp(10) : see declaration of 'foo'
    ...\type_traits\is_pod.hpp(128) : see reference to class template
    instantiation 'boost::detail::is_pod_impl<T>' being compiled
[...]
    ...\boost\iterator\iterator_facade.hpp(652) : see reference to
    class templateinstantiation 
    'boost::detail::operator_brackets_result<Iterator,Value,Reference>'
    being compiled
    with
    [
        Iterator=my_iterator<foo>,
        Value=foo,
        Reference=foo &
    ]
[...]

Although this is probably not a bug strictly speaking, it would be fine if iterator_adaptor could be made to work with incomplete Value types, just as the canonical model for iterators, Value*, does.

[Laurent Rineau <Laurent.Rineau__boost@…>]

I encounter this bug with a code example a bit more tricky:

#include <boost/iterator/iterator_facade.hpp>

template <class V>
struct Iterator
    : public boost::iterator_facade<Iterator<V>,
                                    V,
                                    std::bidirectional_iterator_tag >
{
  friend class boost::iterator_core_access;

  bool equal(Iterator other) const { return true; }

  V& dereference() const { V ref; return ref; }

  void increment()  {}

  void decrement()  {}
};


template < class T >
struct Vertex_base 
{
  typedef typename T::Face_iterator    Face_iterator;

  Face_iterator _f;
};



template < typename T>
struct Face_base 
{
  typedef typename T::Vertex_iterator  Vertex_iterator;

  Vertex_iterator V;
};


struct Triangulation 
{
  typedef Vertex_base<Triangulation> Vertex;
  typedef Face_base<Triangulation>   Face;

  typedef Iterator<Face>             Face_iterator;
  typedef Iterator<Vertex>           Vertex_iterator;
  
  Vertex_iterator v;
};


int main()
{
  Triangulation t;
  
  return 0;
}

g++-4.1.2 and g++-4.3.0 do compile the code above, with boost-1.34.1 or with boost trunk (revision 44750), but MSVC++ 8.0 does not (same error diagnostic as the bug submitter):

cd c:/applis/downloads/boost_1_35_0/
cl.exe -I. facade.cpp
Microsoft (R) C/C++ Optimizing Compiler Version 14.00.50727.42 for x64
Copyright (C) Microsoft Corporation.  All rights reserved.

facade.cpp
facade.cpp(42) : error C2148: total size of array must not exceed 0x7fffffff bytes
        .\boost/type_traits/is_class.hpp(76) : see reference to class template instantiation 'Face_base<T>' being compiled
        with
        [
            T=Triangulation
        ]
        .\boost/type_traits/is_class.hpp(121) : see reference to class template instantiation 'boost::detail::is_class_impl<T>' being compiled
        with
        [
            T=Triangulation::Face
        ]
        .\boost/type_traits/is_enum.hpp(43) : see reference to class template instantiation 'boost::is_class<T>' being compiled
        with
        [
            T=Triangulation::Face
        ]
        .\boost/type_traits/is_enum.hpp(134) : see reference to class template instantiation 'boost::detail::is_class_or_union<T>' being compiled
        with
        [
            T=Triangulation::Face
        ]
        .\boost/type_traits/is_enum.hpp(166) : see reference to class template instantiation 'boost::detail::is_enum_impl<T>' being compiled
        with
        [
            T=Triangulation::Face
        ]
        .\boost/type_traits/is_scalar.hpp(29) : see reference to class template instantiation 'boost::is_enum<T>' being compiled
        with
        [
            T=Triangulation::Face
        ]
        .\boost/type_traits/is_scalar.hpp(49) : see reference to class template instantiation 'boost::detail::is_scalar_impl<T>' being compiled
        with
        [
            T=Triangulation::Face
        ]
        .\boost/type_traits/is_pod.hpp(34) : see reference to class template instantiation 'boost::is_scalar<T>' being compiled
        with
        [
            T=Triangulation::Face
        ]
        .\boost/type_traits/is_pod.hpp(128) : see reference to class template instantiation 'boost::detail::is_pod_impl<T>' being compiled
        with
        [
            T=Triangulation::Face
        ]
        c:\applis\downloads\boost_1_35_0\boost/mpl/aux_/preprocessed/plain/and.hpp(51) : see reference to class template instantiation 'boost::is_POD<T>' being compiled
        with
        [
            T=Triangulation::Face
        ]
        .\boost/mpl/not.hpp(41) : see reference to class template instantiation 'boost::mpl::and_<T1,T2>' being compiled
        with
        [
            T1=boost::is_POD<Triangulation::Face>,
            T2=boost::detail::iterator_writability_disabled<Triangulation::Face,Face_base<Triangulation> &>
        ]
        .\boost/iterator/iterator_facade.hpp(382) : see reference to class template instantiation 'boost::mpl::not_<T>' being compiled
        with
        [
            T=boost::mpl::and_<boost::is_POD<Triangulation::Face>,boost::detail::iterator_writability_disabled<Triangulation::Face,Face_base<Triangulation> &>>
        ]
        .\boost/mpl/if.hpp(63) : see reference to class template instantiation 'boost::detail::use_operator_brackets_proxy<ValueType,Reference>' being compiled
        with
        [
            ValueType=Triangulation::Face,
            Reference=Face_base<Triangulation> &
        ]
        .\boost/iterator/iterator_facade.hpp(391) : see reference to class template instantiation 'boost::mpl::if_<T1,T2,T3>' being compiled
        with
        [
            T1=boost::detail::use_operator_brackets_proxy<Triangulation::Face,Face_base<Triangulation> &>,
            T2=boost::detail::operator_brackets_proxy<Iterator<Triangulation::Face>>,
            T3=Triangulation::Face
        ]
        .\boost/iterator/iterator_facade.hpp(652) : see reference to class template instantiation 'boost::detail::operator_brackets_result<Iterator,Value,Reference>' being compiled
        with
        [
            Iterator=Iterator<Triangulation::Face>,
            Value=Triangulation::Face,
            Reference=Face_base<Triangulation> &
        ]
        facade.cpp(8) : see reference to class template instantiation 'boost::iterator_facade<Derived,Value,CategoryOrTraversal>' being compiled
        with
        [
            Derived=Iterator<Triangulation::Face>,
            Value=Triangulation::Face,
            CategoryOrTraversal=std::bidirectional_iterator_tag
        ]
        facade.cpp(32) : see reference to class template instantiation 'Iterator<V>' being compiled
        with
        [
            V=Triangulation::Face
        ]
        .\boost/type_traits/is_class.hpp(76) : see reference to class template instantiation 'Vertex_base<T>' being compiled
        with
        [
            T=Triangulation
        ]
        .\boost/type_traits/is_class.hpp(121) : see reference to class template instantiation 'boost::detail::is_class_impl<T>' being compiled
        with
        [
            T=Triangulation::Vertex
        ]
        .\boost/type_traits/is_enum.hpp(43) : see reference to class template instantiation 'boost::is_class<T>' being compiled
        with
        [
            T=Triangulation::Vertex
        ]
        .\boost/type_traits/is_enum.hpp(134) : see reference to class template instantiation 'boost::detail::is_class_or_union<T>' being compiled
        with
        [
            T=Triangulation::Vertex
        ]
        .\boost/type_traits/is_enum.hpp(166) : see reference to class template instantiation 'boost::detail::is_enum_impl<T>' being compiled
        with
        [
            T=Triangulation::Vertex
        ]
        .\boost/type_traits/is_scalar.hpp(29) : see reference to class template instantiation 'boost::is_enum<T>' being compiled
        with
        [
            T=Triangulation::Vertex
        ]
        .\boost/type_traits/is_scalar.hpp(49) : see reference to class template instantiation 'boost::detail::is_scalar_impl<T>' being compiled
        with
        [
            T=Triangulation::Vertex
        ]
        .\boost/type_traits/is_pod.hpp(34) : see reference to class template instantiation 'boost::is_scalar<T>' being compiled
        with
        [
            T=Triangulation::Vertex
        ]
        .\boost/type_traits/is_pod.hpp(128) : see reference to class template instantiation 'boost::detail::is_pod_impl<T>' being compiled
        with
        [
            T=Triangulation::Vertex
        ]
        c:\applis\downloads\boost_1_35_0\boost/mpl/aux_/preprocessed/plain/and.hpp(51) : see reference to class template instantiation 'boost::is_POD<T>' being compiled
        with
        [
            T=Triangulation::Vertex
        ]
        .\boost/mpl/not.hpp(41) : see reference to class template instantiation 'boost::mpl::and_<T1,T2>' being compiled
        with
        [
            T1=boost::is_POD<Triangulation::Vertex>,
            T2=boost::detail::iterator_writability_disabled<Triangulation::Vertex,Vertex_base<Triangulation> &>
        ]
        .\boost/iterator/iterator_facade.hpp(382) : see reference to class template instantiation 'boost::mpl::not_<T>' being compiled
        with
        [
            T=boost::mpl::and_<boost::is_POD<Triangulation::Vertex>,boost::detail::iterator_writability_disabled<Triangulation::Vertex,Vertex_base<Triangulation> &>>
        ]
        .\boost/mpl/if.hpp(63) : see reference to class template instantiation 'boost::detail::use_operator_brackets_proxy<ValueType,Reference>' being compiled
        with
        [
            ValueType=Triangulation::Vertex,
            Reference=Vertex_base<Triangulation> &
        ]
        .\boost/iterator/iterator_facade.hpp(391) : see reference to class template instantiation 'boost::mpl::if_<T1,T2,T3>' being compiled
        with
        [
            T1=boost::detail::use_operator_brackets_proxy<Triangulation::Vertex,Vertex_base<Triangulation> &>,
            T2=boost::detail::operator_brackets_proxy<Iterator<Triangulation::Vertex>>,
            T3=Triangulation::Vertex
        ]
        .\boost/iterator/iterator_facade.hpp(652) : see reference to class template instantiation 'boost::detail::operator_brackets_result<Iterator,Value,Reference>' being compiled
        with
        [
            Iterator=Iterator<Triangulation::Vertex>,
            Value=Triangulation::Vertex,
            Reference=Vertex_base<Triangulation> &
        ]
        facade.cpp(8) : see reference to class template instantiation 'boost::iterator_facade<Derived,Value,CategoryOrTraversal>' being compiled
        with
        [
            Derived=Iterator<Triangulation::Vertex>,
            Value=Triangulation::Vertex,
            CategoryOrTraversal=std::bidirectional_iterator_tag
        ]
        facade.cpp(54) : see reference to class template instantiation 'Iterator<V>' being compiled
        with
        [
            V=Triangulation::Vertex
        ]
facade.cpp(42) : error C2079: 'Face_base<T>::V' uses undefined struct 'Iterator<V>'
        with
        [
            T=Triangulation
        ]
        and
        [
            V=Triangulation::Vertex
        ]

Compilation exited abnormally with code 2 at Thu Apr 24 13:19:24

[Laurent Rineau <Laurent.Rineau__boost@…>]

As far as I have understood, when iterator_facade<Derived,Value,Category,...> is instanciated, the type Value is required to be complete because of the following member function prototype:

typename detail::operator_brackets_result<Derived,Value,reference>::type
operator[](difference_type n) const

which triggers the instanciation of use_operator_brackets_proxy<Value,Reference> (in the same file), which triggers the instanciation of is_POD<Value>, which requires a complete type.

[Dave Abrahams]

I think your analysis is correct, but my question to you is: why should this be considered a bug?

I can only think of one way around it, and that's to templatize operator[].

[Joaquín M López Muñoz]

I think your analysis is correct, but my question to you is: why should this be considered a bug?

Because T*, which is the type upon which iterators are modelled, can be instantiated on incomplete types. I've checked section 24.1 of the standard and this requirement does not seem to be explicitly stated, but IMHO it's a nice feature to have, given that 24.1.2 recognized iterators as an abstraction of pointers. FWIW, I first encountered the problem in the context of a real situation.

I can only think of one way around it, and that's to templatize operator[]

Correct. Please see

​http://lists.boost.org/Archives/boost/2007/10/128738.php

where I propose a possible implementation of the workaround.

[Dave Abrahams]

Replying to joaquin:

I think your analysis is correct, but my question to you is: why should this be considered a bug?

Because T*, which is the type upon which iterators are modelled, can be instantiated on incomplete types.

Technically, T* can't be instantiated, since it isn't a template.

I've checked section 24.1 of the standard and this requirement does not seem to be explicitly stated, but IMHO it's a nice feature to have, given that 24.1.2 recognized iterators as an abstraction of pointers. FWIW, I first encountered the problem in the context of a real situation.

Exactly, a nice feature to have. I think this is a feature request... which is why you've labelled it as such. OK, objection withdrawn ;-)

I can only think of one way around it, and that's to templatize operator[]

Correct. Please see

​http://lists.boost.org/Archives/boost/2007/10/128738.php

where I propose a possible implementation of the workaround.

Thomas: I guess since operator[] has to be a member function, we wouldn't gain anything by enable-if'ing it?

[Laurent Rineau <Laurent.Rineau__boost@…>]

Replying to dave:

I think your analysis is correct, but my question to you is: why should this be considered a bug?

It is more a feature request than a bug. In a software of ours, ​CGAL, we would like to use the features of iterator_facade, in a scenario alike the one I posted in comment 1. It currently works with GNU/g++ (versions 4.1.2 and 4.3.0 at least), even if I do not know why, but not with MSVC++ 8.

[Duncan Exon Smith <duncanphilipnorman@…>]

Replying to Laurent Rineau <Laurent.Rineau__boost@…>:

Replying to dave:

I think your analysis is correct, but my question to you is: why should this be considered a bug?

It is more a feature request than a bug. In a software of ours, ​CGAL, we would like to use the features of iterator_facade, in a scenario alike the one I posted in comment 1. It currently works with GNU/g++ (versions 4.1.2 and 4.3.0 at least), even if I do not know why, but not with MSVC++ 8.

This feature worked in GCC only because of a bug prior to v4.4 (e.g., you could use abstract types in v4.3.4). However, this bug -- to do with the intrinsics __is_abstract and __is_pod -- was fixed:

​http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39475

GCC v4.4.3 now gives the same as MSVC. In particular, iterator_facade<> cannot be used to wrap pointers to abstract types any longer. With a large codebase that accidentally relied on this misbehaviour, we cannot upgrade past GCC v4.3 without this feature.

Does anyone know if ​the workaround above causes any problems?

[Duncan Exon Smith <duncanphilipnorman@…>]

Replying to Duncan Exon Smith <duncanphilipnorman@…>:

This feature worked in GCC only because of a bug prior to v4.4 (e.g., you could use abstract types in v4.3.4). However, this bug -- to do with the intrinsics __is_abstract and __is_pod -- was fixed:

​http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39475

GCC v4.4.3 now gives the same as MSVC. In particular, iterator_facade<> cannot be used to wrap pointers to abstract types any longer. With a large codebase that accidentally relied on this misbehaviour, we cannot upgrade past GCC v4.3 without this feature.

BTW, in case anyone else is searching for it, there's a similar problem with boost::iterator_range<>, from Boost.RangeEx, since it uses is_abstract<>. Incomplete types cannot be used there, either.

[Duncan Exon Smith <duncanphilipnorman@…>]

Since I saw this changed owners, I should maybe give some feedback. We've been using something similar to ​the workaround above for a couple of years, and it has worked well.

• There are a few places in the file that need to be templated on Difference.
• We've applied similar patches to parts of Boost.Range.

E.g., our version of the relevant code from the linked patch is:

    template <typename DummyDifference>
        typename boost::lazy_enable_if
        < boost::is_convertible<DummyDifference, difference_type>
        , typename boost::detail::operator_brackets_result<Derived,Value,reference,DummyDifference>::type
        >::type
    operator[](DummyDifference n_) const
    {
        difference_type n(n_);