This is an archive of the discontinued LLVM Phabricator instance.

Differential D18061

Add iterator types to iterator_range, to appease newer gcc's
AbandonedPublic

Authored by dim on Mar 10 2016, 1:18 PM.

Details

Reviewers
chandlerc
dblaikie
Summary

When I recently imported llvm and clang 3.8.0 into FreeBSD, our buildbot
that builds the system with gcc 5.3.0 began complaining about a call to
llvm::reverse() in CFGBuilder::buildCFG(). (Note that we are compiling
clang using gcc 5.3.0, but also using libc++ as the C++ library.)

The gist of the errors is that gcc can't match either of the reverse()
variants in include/llvm/ADT/STLExtras.h; the first variant doesn't
match because CXXConstructorDecl::init_range (which is a
llvm::iterator_range) has no rbegin() or rend() methods:

tools/clang/lib/Analysis/CFG.cpp: In member function 'std::__1::unique_ptr<clang::CFG> {anonymous}::CFGBuilder::buildCFG(const clang::Decl*, clang::Stmt*)':
tools/clang/lib/Analysis/CFG.cpp:1046:45: error: no matching function for call to 'reverse(clang::CXXConstructorDecl::init_const_range)'
     for (auto *I : llvm::reverse(CD->inits())) {
                                             ^
include/llvm/ADT/STLExtras.h:209:6: note: candidate: template<class ContainerTy> decltype (llvm::make_range(C.rbegin(), C.rend())) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<llvm::has_rbegin<ContainerTy>::value>::type*)
 auto reverse(ContainerTy &&C,
      ^
include/llvm/ADT/STLExtras.h:209:6: note:   template argument deduction/substitution failed:
include/llvm/ADT/STLExtras.h: In substitution of 'template<class ContainerTy> decltype (llvm::make_range(C.rbegin(), C.rend())) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<llvm::has_rbegin<ContainerTy>::value>::type*) [with ContainerTy = llvm::iterator_range<clang::CXXCtorInitializer* const*>]':
tools/clang/lib/Analysis/CFG.cpp:1046:45:   required from here
include/llvm/ADT/STLExtras.h:209:6: error: no type named 'type' in 'struct std::__1::enable_if<false, void>'

The second variant should really match, but for gcc it doesn't, because
llvm::iterator_range has no 'iterator' and 'const_iterator' types:

include/llvm/ADT/STLExtras.h:228:64: error: no matching function for call to 'end(llvm::iterator_range<clang::CXXCtorInitializer* const*>&)'
     -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
                                                                ^
/usr/include/c++/v1/iterator:1575:1: note: candidate: template<class _Cp> typename _Cp::const_iterator std::__1::end(const _Cp&)
 end(const _Cp& __c)
 ^
/usr/include/c++/v1/iterator:1575:1: note:   template argument deduction/substitution failed:
/usr/include/c++/v1/iterator: In substitution of 'template<class _Cp> typename _Cp::const_iterator std::__1::end(const _Cp&) [with _Cp = llvm::iterator_range<clang::CXXCtorInitializer* const*>]':
include/llvm/ADT/STLExtras.h:228:64:   required by substitution of 'template<class ContainerTy> decltype (llvm::make_range(llvm::make_reverse_iterator(std::__1::end(C)), llvm::make_reverse_iterator(std::__1::begin(C)))) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<(! llvm::has_rbegin<ContainerTy>::value)>::type*) [with ContainerTy = llvm::iterator_range<clang::CXXCtorInitializer* const*>]'
tools/clang/lib/Analysis/CFG.cpp:1046:45:   required from here
/usr/include/c++/v1/iterator:1575:1: error: no type named 'const_iterator' in 'class llvm::iterator_range<clang::CXXCtorInitializer* const*>'
include/llvm/ADT/STLExtras.h: In substitution of 'template<class ContainerTy> decltype (llvm::make_range(llvm::make_reverse_iterator(std::__1::end(C)), llvm::make_reverse_iterator(std::__1::begin(C)))) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<(! llvm::has_rbegin<ContainerTy>::value)>::type*) [with ContainerTy = llvm::iterator_range<clang::CXXCtorInitializer* const*>]':
tools/clang/lib/Analysis/CFG.cpp:1046:45:   required from here
/usr/include/c++/v1/iterator:1567:1: note: candidate: template<class _Cp> typename _Cp::iterator std::__1::end(_Cp&)
 end(_Cp& __c)
 ^
/usr/include/c++/v1/iterator:1567:1: note:   template argument deduction/substitution failed:
/usr/include/c++/v1/iterator: In substitution of 'template<class _Cp> typename _Cp::iterator std::__1::end(_Cp&) [with _Cp = llvm::iterator_range<clang::CXXCtorInitializer* const*>]':
include/llvm/ADT/STLExtras.h:228:64:   required by substitution of 'template<class ContainerTy> decltype (llvm::make_range(llvm::make_reverse_iterator(std::__1::end(C)), llvm::make_reverse_iterator(std::__1::begin(C)))) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<(! llvm::has_rbegin<ContainerTy>::value)>::type*) [with ContainerTy = llvm::iterator_range<clang::CXXCtorInitializer* const*>]'
tools/clang/lib/Analysis/CFG.cpp:1046:45:   required from here
/usr/include/c++/v1/iterator:1567:1: error: no type named 'iterator' in 'class llvm::iterator_range<clang::CXXCtorInitializer* const*>'
include/llvm/ADT/STLExtras.h: In substitution of 'template<class ContainerTy> decltype (llvm::make_range(llvm::make_reverse_iterator(std::__1::end(C)), llvm::make_reverse_iterator(std::__1::begin(C)))) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<(! llvm::has_rbegin<ContainerTy>::value)>::type*) [with ContainerTy = llvm::iterator_range<clang::CXXCtorInitializer* const*>]':
tools/clang/lib/Analysis/CFG.cpp:1046:45:   required from here

To work around this, add 'iterator' and 'const_iterator' types to
llvm::iterator_range(). I think this might even be a requirement for
being able to use std::begin() and std::end()?

As a side note, maybe it would be more efficient to also add rbegin()
and rend() members to llvm::iterator_range(), then the first variant of
llvm::reverse() can be used?

Diff Detail

Event Timeline

dim updated this revision to Diff 50340.Mar 10 2016, 1:18 PM
dim retitled this revision from to Add iterator types to iterator_range, to appease newer gcc's.
dim updated this object.
dim added reviewers: chandlerc, dblaikie.
dim added subscribers: emaste, llvm-commits.
dim added a subscriber: bdrewery.Mar 10 2016, 1:18 PM
dblaikie edited edge metadata.Mar 10 2016, 1:56 PM
dblaikie added a subscriber: dblaikie.

Is this a bug in libstdc++ - should it be requiring/relying on the operand
to have an ::iterator typedef?

(& even if it is a bug, perhaps we should still workaround it - but I'm not
entirely sure what the right workaround is, perhaps we should just have our
own begin/end that don't have this feature/bug)

dim added a subscriber: EricWF.Mar 10 2016, 2:00 PM
In D18061#372401, @dblaikie wrote:

Is this a bug in libstdc++ - should it be requiring/relying on the operand
to have an ::iterator typedef?

This compilation isn't using libstdc++, but libc++. So if it's a bug in the C++ library, it's something in libc++... However, I don't think so, really. @EricWF, any opinions about this?

(& even if it is a bug, perhaps we should still workaround it - but I'm not
entirely sure what the right workaround is, perhaps we should just have our
own begin/end that don't have this feature/bug)

I'm not sure why reverse() doesn't just call .begin() and .end() on the argument. There might have been a specific reason to use std::begin() and std::end().

dim added a comment.Mar 11 2016, 11:43 AM

As an example, I reduced the code included from CFG.cpp into

reduced-reverse.cpp4 KBDownload
. This reduced sample will define iterator_range::iterator and iterator_range::const_iterator when DEFINE_ITERATORS is defined.

When you compile

reduced-reverse.cpp4 KBDownload
using clang and libc++, it is all OK. When you compile it with gcc (I used 5.3.0) and its default libstdc++, it is also OK. However, when you compile it with gcc 5.3.0 and libc++ (the version in the FreeBSD base system, at least), you get this mess:

$ gcc5 -std=c++11 -I/usr/include/c++/v1 -c reduced-reverse.cpp
reduced-reverse.cpp: In function 'void buildCFG(CXXConstructorDecl*)':
reduced-reverse.cpp:126:43: error: no matching function for call to 'reverse(CXXConstructorDecl::init_range)'
   for (auto *I : llvm::reverse(CD->inits())) {
                                           ^
reduced-reverse.cpp:70:6: note: candidate: template<class ContainerTy> decltype (llvm::make_range(C.rbegin(), C.rend())) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<llvm::has_rbegin<ContainerTy>::value>::type*)
 auto reverse(ContainerTy &&C,
      ^
reduced-reverse.cpp:70:6: note:   template argument deduction/substitution failed:
reduced-reverse.cpp: In substitution of 'template<class ContainerTy> decltype (llvm::make_range(C.rbegin(), C.rend())) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<llvm::has_rbegin<ContainerTy>::value>::type*) [with ContainerTy = llvm::iterator_range<CXXConstructorDecl**>]':
reduced-reverse.cpp:126:43:   required from here
reduced-reverse.cpp:70:6: error: no type named 'type' in 'struct std::__1::enable_if<false, void>'
reduced-reverse.cpp:86:6: note: candidate: template<class ContainerTy> decltype (llvm::make_range(llvm::make_reverse_iterator(std::__1::end(C)), llvm::make_reverse_iterator(std::__1::begin(C)))) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<(! llvm::has_rbegin<ContainerTy>::value)>::type*)
 auto reverse(
      ^
reduced-reverse.cpp:86:6: note:   template argument deduction/substitution failed:
reduced-reverse.cpp: In substitution of 'template<class ContainerTy> decltype (llvm::make_range(llvm::make_reverse_iterator(std::__1::end(C)), llvm::make_reverse_iterator(std::__1::begin(C)))) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<(! llvm::has_rbegin<ContainerTy>::value)>::type*) [with ContainerTy = llvm::iterator_range<CXXConstructorDecl**>]':
reduced-reverse.cpp:126:43:   required from here
reduced-reverse.cpp:89:64: error: no matching function for call to 'end(llvm::iterator_range<CXXConstructorDecl**>&)'
     -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
                                                                ^
In file included from /usr/include/c++/v1/iterator:347:0,
                 from reduced-reverse.cpp:1:
/usr/include/c++/v1/initializer_list:109:1: note: candidate: template<class _Ep> const _Ep* std::end(std::initializer_list<_Ep>)
 end(initializer_list<_Ep> __il) _NOEXCEPT
 ^
/usr/include/c++/v1/initializer_list:109:1: note:   template argument deduction/substitution failed:
reduced-reverse.cpp:89:64: note:   'llvm::iterator_range<CXXConstructorDecl**>' is not derived from 'std::initializer_list<_Ep>'
     -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
                                                                ^
In file included from reduced-reverse.cpp:1:0:
/usr/include/c++/v1/iterator:1575:1: note: candidate: template<class _Cp> typename _Cp::const_iterator std::__1::end(const _Cp&)
 end(const _Cp& __c)
 ^
/usr/include/c++/v1/iterator:1575:1: note:   template argument deduction/substitution failed:
/usr/include/c++/v1/iterator: In substitution of 'template<class _Cp> typename _Cp::const_iterator std::__1::end(const _Cp&) [with _Cp = llvm::iterator_range<CXXConstructorDecl**>]':
reduced-reverse.cpp:89:64:   required by substitution of 'template<class ContainerTy> decltype (llvm::make_range(llvm::make_reverse_iterator(std::__1::end(C)), llvm::make_reverse_iterator(std::__1::begin(C)))) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<(! llvm::has_rbegin<ContainerTy>::value)>::type*) [with ContainerTy = llvm::iterator_range<CXXConstructorDecl**>]'
reduced-reverse.cpp:126:43:   required from here
/usr/include/c++/v1/iterator:1575:1: error: no type named 'const_iterator' in 'class llvm::iterator_range<CXXConstructorDecl**>'
reduced-reverse.cpp: In substitution of 'template<class ContainerTy> decltype (llvm::make_range(llvm::make_reverse_iterator(std::__1::end(C)), llvm::make_reverse_iterator(std::__1::begin(C)))) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<(! llvm::has_rbegin<ContainerTy>::value)>::type*) [with ContainerTy = llvm::iterator_range<CXXConstructorDecl**>]':
reduced-reverse.cpp:126:43:   required from here
/usr/include/c++/v1/iterator:1567:1: note: candidate: template<class _Cp> typename _Cp::iterator std::__1::end(_Cp&)
 end(_Cp& __c)
 ^
/usr/include/c++/v1/iterator:1567:1: note:   template argument deduction/substitution failed:
/usr/include/c++/v1/iterator: In substitution of 'template<class _Cp> typename _Cp::iterator std::__1::end(_Cp&) [with _Cp = llvm::iterator_range<CXXConstructorDecl**>]':
reduced-reverse.cpp:89:64:   required by substitution of 'template<class ContainerTy> decltype (llvm::make_range(llvm::make_reverse_iterator(std::__1::end(C)), llvm::make_reverse_iterator(std::__1::begin(C)))) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<(! llvm::has_rbegin<ContainerTy>::value)>::type*) [with ContainerTy = llvm::iterator_range<CXXConstructorDecl**>]'
reduced-reverse.cpp:126:43:   required from here
/usr/include/c++/v1/iterator:1567:1: error: no type named 'iterator' in 'class llvm::iterator_range<CXXConstructorDecl**>'
reduced-reverse.cpp: In substitution of 'template<class ContainerTy> decltype (llvm::make_range(llvm::make_reverse_iterator(std::__1::end(C)), llvm::make_reverse_iterator(std::__1::begin(C)))) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<(! llvm::has_rbegin<ContainerTy>::value)>::type*) [with ContainerTy = llvm::iterator_range<CXXConstructorDecl**>]':
reduced-reverse.cpp:126:43:   required from here
/usr/include/c++/v1/iterator:1418:1: note: candidate: template<class _Tp, long unsigned int _Np> _Tp* std::__1::end(_Tp (&)[_Np])
 end(_Tp (&__array)[_Np])
 ^
/usr/include/c++/v1/iterator:1418:1: note:   template argument deduction/substitution failed:
reduced-reverse.cpp:89:64: note:   mismatched types '_Tp [_Np]' and 'llvm::iterator_range<CXXConstructorDecl**>'
     -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
                                                                ^
reduced-reverse.cpp:90:66: error: no matching function for call to 'begin(llvm::iterator_range<CXXConstructorDecl**>&)'
                            llvm::make_reverse_iterator(std::begin(C)))) {
                                                                  ^
In file included from /usr/include/c++/v1/iterator:347:0,
                 from reduced-reverse.cpp:1:
/usr/include/c++/v1/initializer_list:100:1: note: candidate: template<class _Ep> const _Ep* std::begin(std::initializer_list<_Ep>)
 begin(initializer_list<_Ep> __il) _NOEXCEPT
 ^
/usr/include/c++/v1/initializer_list:100:1: note:   template argument deduction/substitution failed:
reduced-reverse.cpp:90:66: note:   'llvm::iterator_range<CXXConstructorDecl**>' is not derived from 'std::initializer_list<_Ep>'
                            llvm::make_reverse_iterator(std::begin(C)))) {
                                                                  ^
In file included from reduced-reverse.cpp:1:0:
/usr/include/c++/v1/iterator:1559:1: note: candidate: template<class _Cp> typename _Cp::const_iterator std::__1::begin(const _Cp&)
 begin(const _Cp& __c)
 ^
/usr/include/c++/v1/iterator:1559:1: note:   template argument deduction/substitution failed:
/usr/include/c++/v1/iterator: In substitution of 'template<class _Cp> typename _Cp::const_iterator std::__1::begin(const _Cp&) [with _Cp = llvm::iterator_range<CXXConstructorDecl**>]':
reduced-reverse.cpp:90:66:   required by substitution of 'template<class ContainerTy> decltype (llvm::make_range(llvm::make_reverse_iterator(std::__1::end(C)), llvm::make_reverse_iterator(std::__1::begin(C)))) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<(! llvm::has_rbegin<ContainerTy>::value)>::type*) [with ContainerTy = llvm::iterator_range<CXXConstructorDecl**>]'
reduced-reverse.cpp:126:43:   required from here
/usr/include/c++/v1/iterator:1559:1: error: no type named 'const_iterator' in 'class llvm::iterator_range<CXXConstructorDecl**>'
reduced-reverse.cpp: In substitution of 'template<class ContainerTy> decltype (llvm::make_range(llvm::make_reverse_iterator(std::__1::end(C)), llvm::make_reverse_iterator(std::__1::begin(C)))) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<(! llvm::has_rbegin<ContainerTy>::value)>::type*) [with ContainerTy = llvm::iterator_range<CXXConstructorDecl**>]':
reduced-reverse.cpp:126:43:   required from here
/usr/include/c++/v1/iterator:1551:1: note: candidate: template<class _Cp> typename _Cp::iterator std::__1::begin(_Cp&)
 begin(_Cp& __c)
 ^
/usr/include/c++/v1/iterator:1551:1: note:   template argument deduction/substitution failed:
/usr/include/c++/v1/iterator: In substitution of 'template<class _Cp> typename _Cp::iterator std::__1::begin(_Cp&) [with _Cp = llvm::iterator_range<CXXConstructorDecl**>]':
reduced-reverse.cpp:90:66:   required by substitution of 'template<class ContainerTy> decltype (llvm::make_range(llvm::make_reverse_iterator(std::__1::end(C)), llvm::make_reverse_iterator(std::__1::begin(C)))) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<(! llvm::has_rbegin<ContainerTy>::value)>::type*) [with ContainerTy = llvm::iterator_range<CXXConstructorDecl**>]'
reduced-reverse.cpp:126:43:   required from here
/usr/include/c++/v1/iterator:1551:1: error: no type named 'iterator' in 'class llvm::iterator_range<CXXConstructorDecl**>'
reduced-reverse.cpp: In substitution of 'template<class ContainerTy> decltype (llvm::make_range(llvm::make_reverse_iterator(std::__1::end(C)), llvm::make_reverse_iterator(std::__1::begin(C)))) llvm::reverse(ContainerTy&&, typename std::__1::enable_if<(! llvm::has_rbegin<ContainerTy>::value)>::type*) [with ContainerTy = llvm::iterator_range<CXXConstructorDecl**>]':
reduced-reverse.cpp:126:43:   required from here
/usr/include/c++/v1/iterator:1410:1: note: candidate: template<class _Tp, long unsigned int _Np> _Tp* std::__1::begin(_Tp (&)[_Np])
 begin(_Tp (&__array)[_Np])
 ^
/usr/include/c++/v1/iterator:1410:1: note:   template argument deduction/substitution failed:
reduced-reverse.cpp:90:66: note:   mismatched types '_Tp [_Np]' and 'llvm::iterator_range<CXXConstructorDecl**>'
                            llvm::make_reverse_iterator(std::begin(C)))) {
                                                                  ^
dim added a comment.Mar 11 2016, 12:12 PM

Hmm, on the other hand, in libc++ trunk the sample program does compile. This seems to have been fixed as a side effect of rL255585, but that commit doesn't really do anything specific to <iterator> or <utility>. @EricWF, any idea how that comes about?

dim added a comment.Mar 11 2016, 3:04 PM

Okay, the relevant change from rL255585 is that _LIBCPP_HAS_NO_TRAILING_RETURN doesn't get defined anymore, and this enables the std::begin() and std::end() implementations in <iterator>. Apparently, if these aren't defined, gcc wants to have iterator types defined in the class, though I still don't know for sure how it synthesizes begin() and end() methods then. :)

dim abandoned this revision.Mar 12 2016, 11:31 AM

Okay, nevermind about this change. In FreeBSD, I have simply imported rL255585 for now (a full libc++ import will follow later). Gcc wanted to see iterator and const_iterator types in iterator_range, when _LIBCPP_HAS_NO_TRAILING_RETURN is defined, because libc++'s <iterator> then uses the following kind of definitions for e.g. std::begin():

template <class _Cp>
inline _LIBCPP_INLINE_VISIBILITY
typename _Cp::iterator
begin(_Cp& __c)
{
    return __c.begin();
}

E.g to be able to return anything, it needs to know the type.

Revision Contents

PathSize
include/
llvm/
ADT/
3 lines

Diff 50340

include/llvm/ADT/iterator_range.h

Show All 27 Lines
/// ///
/// This just wraps two iterators into a range-compatible interface. Nothing /// This just wraps two iterators into a range-compatible interface. Nothing
/// fancy at all. /// fancy at all.
template <typename IteratorT> template <typename IteratorT>
class iterator_range { class iterator_range {
IteratorT begin_iterator, end_iterator; IteratorT begin_iterator, end_iterator;
public: public:
typedef IteratorT iterator;
typedef const IteratorT const_iterator;
//TODO: Add SFINAE to test that the Container's iterators match the range's //TODO: Add SFINAE to test that the Container's iterators match the range's
// iterators. // iterators.
template <typename Container> template <typename Container>
iterator_range(Container &&c) iterator_range(Container &&c)
//TODO: Consider ADL/non-member begin/end calls. //TODO: Consider ADL/non-member begin/end calls.
: begin_iterator(c.begin()), end_iterator(c.end()) {} : begin_iterator(c.begin()), end_iterator(c.end()) {}
iterator_range(IteratorT begin_iterator, IteratorT end_iterator) iterator_range(IteratorT begin_iterator, IteratorT end_iterator)
: begin_iterator(std::move(begin_iterator)), : begin_iterator(std::move(begin_iterator)),
Show All 25 Lines