<html>
    <head>
      <base href="https://bugs.llvm.org/">
    </head>
    <body><table border="1" cellspacing="0" cellpadding="8">
        <tr>
          <th>Bug ID</th>
          <td><a class="bz_bug_link 
          bz_status_NEW "
   title="NEW - std::search violates random access iterator concept by not using the iterator's difference_type"
   href="https://bugs.llvm.org/show_bug.cgi?id=52151">52151</a>
          </td>
        </tr>

        <tr>
          <th>Summary</th>
          <td>std::search violates random access iterator concept by not using the iterator's difference_type
          </td>
        </tr>

        <tr>
          <th>Product</th>
          <td>libc++
          </td>
        </tr>

        <tr>
          <th>Version</th>
          <td>12.0
          </td>
        </tr>

        <tr>
          <th>Hardware</th>
          <td>PC
          </td>
        </tr>

        <tr>
          <th>OS</th>
          <td>Linux
          </td>
        </tr>

        <tr>
          <th>Status</th>
          <td>NEW
          </td>
        </tr>

        <tr>
          <th>Severity</th>
          <td>enhancement
          </td>
        </tr>

        <tr>
          <th>Priority</th>
          <td>P
          </td>
        </tr>

        <tr>
          <th>Component</th>
          <td>All Bugs
          </td>
        </tr>

        <tr>
          <th>Assignee</th>
          <td>unassignedclangbugs@nondot.org
          </td>
        </tr>

        <tr>
          <th>Reporter</th>
          <td>dangelog@gmail.com
          </td>
        </tr>

        <tr>
          <th>CC</th>
          <td>llvm-bugs@lists.llvm.org, mclow.lists@gmail.com
          </td>
        </tr></table>
      <p>
        <div>
        <pre>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):

<a href="https://github.com/llvm/llvm-project/blob/main/libcxx/include/__algorithm/search.h#L71">https://github.com/llvm/llvm-project/blob/main/libcxx/include/__algorithm/search.h#L71</a>

  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.</pre>
        </div>
      </p>


      <hr>
      <span>You are receiving this mail because:</span>

      <ul>
          <li>You are on the CC list for the bug.</li>
      </ul>
    </body>
</html>