Boost C++ Libraries: Ticket #1315: iterator_adaptor does not work with incomplete Value types

Thu, 24 Apr 2008 14:36:22 GMT

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

Thu, 24 Apr 2008 14:43:34 GMT

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.

status changed

Dave Abrahams — Thu, 24 Apr 2008 17:51:47 GMT

status new → assigned

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 — Thu, 24 Apr 2008 19:11:08 GMT

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.

owner, status changed

Dave Abrahams — Thu, 24 Apr 2008 23:59:28 GMT

owner changed from Dave Abrahams to Thomas Witt
status assigned → new

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?

Fri, 25 Apr 2008 08:24:57 GMT

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.

cc set

Wed, 13 Oct 2010 22:43:20 GMT

cc duncanphilipnorman@… added

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?

Wed, 13 Oct 2010 22:51:20 GMT

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.

owner changed

Dave Abrahams — Wed, 21 Nov 2012 22:30:59 GMT

owner changed from Thomas Witt to jeffrey.hellrung

Thu, 22 Nov 2012 15:52:09 GMT

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_);