[llvm-bugs] [Bug 52151] New: std::search violates random access iterator concept by not using the iterator's difference_type

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=52151

            Bug ID: 52151
           Summary: std::search violates random access iterator concept by
                    not using the iterator's difference_type
           Product: libc++
           Version: 12.0
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: All Bugs
          Assignee: unassignedclangbugs at nondot.org
          Reporter: dangelog at gmail.com
                CC: llvm-bugs at lists.llvm.org, mclow.lists at gmail.com

Hi,

The std::search implementation for random access iterators performs a couple of
sums between an iterator of the first range and an integral quantity of an
"arbitrary" integer type (the difference_type of the iterator of the *second*
range):

https://github.com/llvm/llvm-project/blob/main/libcxx/include/__algorithm/search.h#L71

  typedef typename iterator_traits<_RandomAccessIterator1>::difference_type
_D1;
  typedef typename iterator_traits<_RandomAccessIterator2>::difference_type
_D2;
  const _D2 __len2 = __last2 - __first2;

  const _RandomAccessIterator1 __s = __last1 - (__len2 - 1);

        return _VSTD::make_pair(__first1, __first1 + __len2);


(Nitpicking, __len2 - 1 could also be a type different from _D2, due to integer
promotions and what not.)

Anyways, the problem is that this is illegal: random access iterators can only
be summed with their own difference_type, not with an arbitrary integer. The
solution here would simply be to add a couple of casts/conversions to _D1
before doing the sum.

--

As of why I ended up noticing this: in Qt 6, for a lot of wrong reasons that
I'm trying to fix, we have QVector's iterators which are implicitly convertible
to a raw pointer (because in Qt 5 the iterators _were_ raw pointers, so this is
a band-aid measure to avoid breaking source compatibility). 

The difference type is "qsizetype", a signed 32/64 bits integer type. 

This means that now one has something like this:

template <typename T>
class QVector {
  class iterator {
    using difference_type = qsizetype;
    /* implicit */ operator T*() const;
    iterator operator+(qsizetype) const;
  }
};

The problem with this setup is that if you apply operator+ to an iterator
object and some integer type other than qsizetype (e.g. int, ptrdiff_t, ...)
then the call becomes ambiguous; it + 42 could either be

  operator+(iterator, int converted to qsizetype)

or

  operator+(iterator converted to raw pointer, int)

and clang errors out. This is what this bug report is about.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20211012/40d5e621/attachment.html>