D2538R2
ADL-proof std::projected

1. Changelog

• R2:

  • Merge the fix for [LWG3859]. Add the isNull example, which is not fixed by LWG3859 alone, but is fixed by this combined patch.

• R1:

  • Added Casey Carter as coauthor.

2. Background on ADL-proofing

Throughout this paper, we use Holder<Incomplete> as the canonical example of a "dangerous-to-complete" type.

template<class T> struct Holder { T t; };
struct Incomplete;

Any operation that requires type Holder<Incomplete> to be completed will trigger a hard error. For example:

error: field has incomplete type 'Incomplete'
template<class T> struct Holder { T t; };
                                    ^
<source>:6:20: note: in instantiation of template class 'Holder<Incomplete>' requested here
Holder<Incomplete> h;
                   ^

One such operation is ADL. For example, this snippet will trigger a hard error:

Holder<Incomplete> *p;
int f(Holder<Incomplete>*);
int x = f(p);  // error: ADL requires completing the associated type Holder<Incomplete>

but this snippet will be OK:

Holder<Incomplete> *p;
int f(Holder<Incomplete>*);
int x = ::f(p);  // OK: no ADL, therefore no error

Most operations on native pointers do not trigger ADL. For example:

Holder<Incomplete> *a[10] = {}; // ten null pointers
Holder<Incomplete> **p = a;                 // OK
p += 1;                                     // OK
assert(*p == nullptr);                      // OK
assert(p == a+1);                           // OK
assert(std::count(a, a+10, nullptr) == 10); // OK

The libc++ test suite includes a lot of "ADL-proofing" test cases, to make sure that our STL algorithms don’t unnecessarily trigger the completion of associated types. Libc++ considers this not a conformance issue, but a pretty important quality-of-implementation issue. Unnecessarily prematurely completing a type can cause hard errors for the user that are difficult to fix; I imagine it could cause ODR issues too.

For more information, see [Uglification].

3. The problem in C++20

Most C++20 Ranges algorithms fundamentally cannot be ADL-proofed.

Holder<Incomplete> *a[10] = {}; // ten null pointers
assert(std::count(a, a+10, nullptr) == 10); // OK
assert(std::ranges::count(a, a+10, nullptr) == 10); // hard error

This causes a hard error on all possible implementations.

In fact, even the following program causes hard errors:

using T = Holder<Incomplete>*;

static_assert(std::equality_comparable<T>); // OK
bool x = std::indirectly_comparable<T*, T*, std::equal_to<>>; // hard error
bool y = std::sortable<T*>; // hard error

The error happens because indirectly_comparable<T*, T*, Pred> is actually defined as indirect_binary_predicate<Pred, projected<T*, identity>, projected<T*, identity>>. In evaluating that concept, we eventually need to ask whether *it is a valid expression for an iterator of type projected<T*, identity>. This means we need to complete all the associated types of projected<T*, identity>, which includes all the associated types of T, which includes Holder<Incomplete>.

So, we are in the sad state that std::sort, std::count, etc., are safe to use on "dangerous-to-ADL" pointer types, but their std::ranges:: counterparts are not.

The problem also exists with projections other than identity; for example,

using T = Holder<Incomplete>*;

Holder<Incomplete> *a[10] = {}; // ten null pointers
auto isNull = [](auto *p) { return p == nullptr; };
assert(std::ranges::count(a, a+10, true, isNull) == 10); // hard error

4. The solution: ADL-proof std::projected

To fix the problem and ADL-proof all the Ranges algorithms, we simply have to stop T from being an associated type of projected<T*, Proj>. We can do this by inserting an ADL firewall; see P2538R1 and [Disable] for details of the technique.

[P2300R4] actually provides blanket wording and a phrase of power, "arguments are not associated entities," that denotes this technique. However, I don’t use that phrase of power here because we need wording that can be DR’ed back to C++20 and C++23; our wording can’t depend on P2300.

If we adopt this proposal and respecify std::projected along these lines, then the programmer will be able to write:

using T = Holder<Incomplete>*;

static_assert(std::equality_comparable<T>); // OK
static_assert(std::indirectly_comparable<T*, T*, std::equal_to<>>); // will be OK
static_assert(std::sortable<T*>); // will be OK

int main() {
  Holder<Incomplete> *a[10] = {}; // ten null pointers
  auto isNull = [](auto *p) { return p == nullptr; };
  assert(std::count(a, a+10, nullptr) == 10); // OK
  assert(std::ranges::count(a, a+10, nullptr) == 10); // will be OK
  assert(std::ranges::count(a, a+10, true, isNull) == 10); // will be OK
}

5. Implementation experience

This has been prototyped in Arthur’s libc++ fork; see [Patch].

The P/R for [LWG3859] merge-conflicts with P2538R1; therefore I’ve included the fix for LWG3859 as part of P2538R2.

6. Proposed wording

Note: I believe this doesn’t need a feature-test macro, because it merely enables code that was ill-formed before, and I can’t think of a scenario where you’d want to do one thing if the feature was available and a different thing if it wasn’t.

Modify [projected] as follows:

Class template projected is used to constrain algorithms that accept callable objects and projections. It combines a an indirectly_readable type I and a callable object type Proj into a new indirectly_readable type whose reference type is the result of applying Proj to the iter_reference_t of I.

namespace std {
  template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj>
  struct projected {
    using value_type = remove_cvref_t<indirect_result_t<Proj&, I>>;
    indirect_result_t<Proj&, I> operator*() const; // not defined
  };

  template<weakly_incrementable I, class Proj>
  struct incrementable_traits<projected<I, Proj>> {
    using difference_type = iter_difference_t<I>;
  };
}

namespace std {
  template<class I, class Proj>
  struct projected-impl { // exposition only
    struct type { // exposition only
      using value_type = remove_cvref_t<indirect_result_t<Proj&, I>>;
      using difference_type = iter_difference_t<I>; // present only if I models weakly_incrementable
      indirect_result_t<Proj&, I> operator*() const; // not defined
    };
  };

  template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj>
  using projected = conditional_t<same_as<Proj, identity>, I, projected-impl<I, Proj>::type>;
}

7. Straw polls

7.1. Polls taken electronically, May 2022

In May 2022, LEWG took an electronic straw poll of a number of papers, including P2538R0. The results are tallied in P2575R0 "2022-05 Library Evolution Poll Outcomes." P2538R0’s poll had this result:

8. Acknowledgments

• Thanks to Jonathan Wakely and Ville Voutilainen for recommending Arthur write this paper.

• Thanks to Barry Revzin for suggesting the "present only if..." wording, and to Hui Xie for pointing out the relevance of [P2300R4].

• Thanks to Walter E. Brown for pointing out P2538R1’s merge-conflict with [LWG3859]; P2538R2 merges in the proposed fix for LWG3859.