[libc++] std::sort passes `it[n]` to the comparator since libc++ 22, which breaks iterators whose `operator[]` returns a proxy
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
Written with help from Claude.
## Summary
Since https://github.com/llvm/llvm-project/pull/154092 (libc++ 22), `__sift_down` in `<__algorithm/sift_down.h>` calls the comparator as `__comp(__first[__child], __first[__child + 1])` instead of `__comp(*__child_i, *(__child_i + 1))`.
For a Cpp17RandomAccessIterator, the standard only requires `a[n]` to be "convertible to `reference`", with operational semantics `*(a + n)` ([\[random.access.iterators\]](https://eel.is/c++draft/random.access.iterators), Table "Cpp17RandomAccessIterator requirements"). It does not have to *be* `reference`. `boost::iterator_facade` uses that latitude: for every non-trivial value type its `operator[]` returns an `operator_brackets_proxy` that converts to `reference` on demand. `boost::transform_iterator`, `boost::indirect_iterator`, `boost::zip_iterator` and every user iterator built on `boost::iterator_adaptor` therefore hand `std::sort` a proxy.
The comparator then receives the proxy, not the element. A comparator with a non-template `operator()` still works through the implicit conversion. A comparator with a templated `operator()` fails, because template argument deduction does not consider user-defined conversions.
`Compare` "meets the requirements for a template parameter named BinaryPredicate" ([\[alg.sorting.general\]/2](https://eel.is/c++draft/alg.sorting.general#2)), and a BinaryPredicate is "applied to the result of dereferencing two corresponding iterators" ([\[algorithms.requirements\]/7](https://eel.is/c++draft/algorithms.requirements#7)). `it[n]` is not the result of dereferencing an iterator, so passing it to the comparator looks like a libc++ bug rather than a user bug. This worked with every libc++ up to and including 19 and works with libstdc++.
## Reproducer
```cpp
#include
#include
#include
#include
template struct Wrapper { T item; };
struct Identity {
Wrapper &operator()(Wrapper &w) const { return w; }
};
struct Cmp {
template
bool operator()(const Wrapper &a, const Wrapper &b) const { return a.item < b.item; }
};
int main() {
std::vector> v{{"b"}, {"a"}};
typedef boost::transform_iterator>::iterator> It;
std::sort(It(v.begin()), It(v.end()), Cmp());
}
```
```
$ clang++ -std=c++17 -stdlib=libc++ -c repro.cpp
```
Output with libc++ 22.1.8 (Arch Linux, clang 22.1.8):
```
/usr/bin/../include/c++/v1/__algorithm/sift_down.h:49:39: error: no matching function for call to object of type 'Cmp'
49 | } else if ((__child + 1) < __len && __comp(__first[__child], __first[__child + 1])) {
| ^~~~~~
/usr/bin/../include/c++/v1/__algorithm/make_heap.h:49:12: note: in instantiation of function template specialization 'std::__sift_down *>>>' requested here
...
repro.cpp:14:8: note: candidate template ignored: could not match 'Wrapper' against 'operator_brackets_proxy'
```
The same file compiles with libc++ 19 and with libstdc++.
## Expected behavior
`std::sort` and the heap algorithms apply the comparator to `*it`, or to something of type `iterator_traits::reference`, as they did before PR 154092.
## Suggested fix
In `<__algorithm/sift_down.h>`, dereference through iterator arithmetic instead of `operator[]`, e.g. `*(__first + __child)`, or use a helper such as `_Ops::__iter_deref`. The assignments `__first[__start] = ...` are fine, since a proxy is assignable.
## Real-world impact
ncmpcpp fails to build against libc++ 22: https://github.com/ncmpcpp/ncmpcpp/issues/663. It sorts `NC::Menu` items through a `boost::transform_iterator` with a comparator that has templated overloads.
Contributor guide
Research direction
Start with <__algorithm/sift_down.h> and the provided repro.cpp, then compile it with clang++ -std=c++17 -stdlib=libc++ to reproduce the proxy-iterator failure. Verify that std::sort and the heap algorithms pass dereferenced iterator values to templated comparators, while the existing proxy-compatible assignments remain valid.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 2/5
- Estimated time
- 1-2 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 76/100