[patch] [libc++] missing difference_type in advance implementation

Clang Frontend
#1

The following patch fixes some missing difference_type
in the implementation of std::advance. The problem is that
depending on the type of

iterator_traits::difference_type

otherwise valid code fails to compile (this was the case for
my code), and warnings might show up.

Bests,
Gonzalo BG

P.S.: libcxx.llvm.org should have a small section explaining
the best way to contribute patches. I hope I posted the patch
in the correct mailing list.

difference_type.patch (1019 Bytes)

#2

Do you have a test case that failed before?

Joerg

#3

I have an iterator with a difference_type that is only explicitly
convertible from int (not implicitly) and thus fails. Its implementation
depends on Boost.Iterator (and everything that Boost.Iterator depends on)
so I don't think it would be suitable for a test-case.

#4

I’d really, really like to see a failing test case that I can include in the libc++ test suite.
Otherwise, someone might break it again in the future.

— Marshall

P.S. For future reference (no need to do it in this case), patches should go to the cfe-commits mailing list.
P.P.S. I’ll take a look at adding info to the libc++ web page.

#5

I’m also wondering about this.

The standard says that an iterator’s difference_type must be a ‘signed integer type” section 24.2.1 [iterator.requirements.general]

These types are defined in section 3.9.1 [basic.fundamental], and seems to me to imply that it has to be either one of “signed char”, “short int”, “int”, “long int”, and “long long int”, or an “extended signed integer type” provided by the implementation (which means the compiler and/or standard library). I don’t see any provision here for an iterator having a difference_type that is a user-defined type.

Off to read the Boost.Iterator documentation….

— Marshall

#6

My iterator is using as difference_type this user-defined integer (https://github.com/gnzlbg/arithmetic_type) which can’t be compared with int and is only explicitly convertible to other types.

I just reproduced the exact error I was getting. It fails due to the lack of operator< for my difference_type and int.

I don’t see any provision here for an iterator having a difference_type that is a user-defined type.

I don’t think the standard allows user-defined integer types with extraneous conversion rules as difference_type either.

I’d really, really like to see a failing test case that I can include in the libc++ test suite.
Otherwise, someone might break it again in the future.

Since all integer types can be compared with int, one would need a custom integer type to construct a test for this. I can provide a random access counting range this week, whose counting iterators have this custom integer as difference_type if there is interest for it.

The arguments behind this patch are weak. There are probably multiple occurrences of similar constructs within the standard library. Using a custom integer without implicit conversions would require that the types match exactly (e.g. difference_type{0}), and that all type conversions are made explicit (e.g. via a static_cast). I don’t know if this is worth pursuing due to its low ROI. If this would be worth pursuing, adding a clang warning for mismatching integer types would probably be a better way of ensuring this than run-time tests.

#7

I’ve added a section to http://libcxx.llvm.org about reporting bugs and contributing patches

— Marshall

#8

Thanks for adding the section.

I’ve tried hard to come up with a MWE that is simpler than this, but I’ve failed. This is the simplest thing I’ve been able to come up with. As you can see, the code works fine for random access iterators, but fails for bidirectional and forward iterators (see the errors below in the comments):

#include
#include <boost/iterator/counting_iterator.hpp>
// From https://github.com/gnzlbg/arithmetic_type :
#include <arithmetic_type/arithmetic_type.hpp>

int main() {
/// Opaque Integer without implicit conversions:
struct tag {};
using Int = arithmetic::Arithmetic<int, tag>;

/// Works as expected
boost::counting_iterator<Int, boost::random_access_traversal_tag, Int> a(Int{10});
std::advance(a, Int{5});

/// Fails: libcxx/iterator:458:13: error: invalid operands to
/// binary expression (‘typename
/// iterator_traits<counting_iterator<Arithmetic<int, tag>,
/// bidirectional_traversal_tag, Arithmetic<int, tag> > >::difference_type’
/// (aka ‘arithmetic::Arithmetic<int, tag>’) and ‘int’)
/// if (__n >= 0)
/// ~~~ ^ ~
boost::counting_iterator<Int, boost::bidirectional_traversal_tag, Int> b(Int{10});
std::advance(b, Int{5});

/// Fails: libcxx/iterator:449:16: error: invalid operands to binary
/// expression (‘typename iterator_traits<counting_iterator<Arithmetic<int, tag>,
/// forward_traversal_tag, Arithmetic<int, tag> > >::difference_type’ (aka
/// ‘arithmetic::Arithmetic<int, tag>’) and ‘int’)
/// for (; __n > 0; --__n)
/// ~~~ ^ ~
boost::counting_iterator<Int, boost::forward_traversal_tag, Int> c(Int{10});
std::advance(c, Int{5});
}

#9

Thanks for adding the section.

I’ve tried hard to come up with a MWE that is simpler than this, but I’ve failed. This is the simplest thing I’ve been able to come up with. As you can see, the code works fine for random access iterators, but fails for bidirectional and forward iterators (see the errors below in the comments):

Thanks for the example; I’ll try it out on Monday.

However, I think you’re out of luck, anyway, because of [iterator.requirements.general]/p1; the last sentence:

For every iterator type X for which equality is defined, there is a corresponding signed integer type called the difference type of the iterator.

And [basic.fundamental]/p2, which says:

There are five standard signed integer types : “signed char”, “short int”, “int”, “long int”, and “long long int”.
followed by:
There may also be implementation-defined extended signed integer types. The standard and extended signed integer types are collectively called signed integer types.

To me this says that you can’t have an standard-conforming iterator with a difference_type that isn’t one of those types.

[ And a brief search of the standards committee mailing list found a discussion on exactly this point back in August of 2012,
and the consensus was that the standard did not allow iterators with such difference types. ]

Just FYI: The difference_type of the standard containers and allocators is defined the same way.

— Marshall