llvm / llvm/llvm-project

[libc++] std::sort passes `it[n]` to the comparator since libc++ 22, which breaks iterators whose `operator[]` returns a proxy

Open Beginner friendly
#223,290 4 comments 0 reactions 0 assignees View on GitHub
libc++ regression:22 rejects-valid
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.