P2538R1: ADL-proof std::projected (original) (raw)

1. Changelog

2. Background on ADL-proofing

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

template 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 struct Holder { T t; }; ^

:6:20: note: in instantiation of template class 'Holder' requested here Holder h; ^

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

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

but this snippet will be OK:

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

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

Holder *a[10] = {}; // ten null pointers Holder **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. As far as I know, we consider 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, and 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 *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. Because the error messages are so long, I’ve moved them into Appendix A.

In fact, even the following program causes hard errors:

using T = Holder*;

static_assert(std::equality_comparable); // 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" types, but their std::ranges:: counterparts are not.

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*, identity>. We can do this by inserting an ADL firewall.

The basic technique is to replace

template struct projected { };

with

template struct __projected_impl { struct type { }; };

template using projected = __projected_impl::type;

ADL will associate the base classes of derived classes, but it does not associate the containing classes of nested classes. In short, the :: in __projected_impl<NonAssociated>::type acts as a firewall against unwanted ADL.

For more information, see [Disable].

[P2300R4] actually provides blanket wording and a phrase of power that denotes this technique, in their proposed new library section [lib.tmpl-heads]. Quote:

If a class template’s template-head is marked with "arguments are not associated entities", any template arguments do not contribute to the associated entities of a function call where a specialization of the class template is an associated entity. In such a case, the class template may be implemented as an alias template referring to a templated class, or as a class template where the template arguments themselves are templated classes.

This is exactly the sort of thing I’m talking about, and if that wording is shipped, then we might consider rewording std::projected to use the phrase of power. However, I’m proposing a particular implementation technique below, so that the wording here (which I hope vendors will DR back to C++20) is not unnecessarily tied to the fate of P2300. The proposed wording here also removes some unnecessary complexity (a partial specialization of incrementable_traits that, after this patch, will not be physically possible to implement).

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

using T = Holder*;

static_assert(std::equality_comparable); // 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 *a[10] = {}; // ten null pointers assert(std::count(a, a+10, nullptr) == 10); // OK assert(std::ranges::count(a, a+10, nullptr) == 10); // will be OK }

5. Implementation experience

This has been prototyped in a branch of libc++, and is just waiting for the paper to be adopted so that we can merge it. See [D119029].

6. Proposed wording relative to N4868

Note: The phrase of power "present only if..." was recently introduced into the working draft by [P2259R1]; see for example [counted.iterator] and [range.iota.iterator].

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 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; }; }

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; // present only if I models weaklyincrementable indirect_result_t<Proj&, I> operator*() const; // not defined }; };

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

7. Acknowledgments

Appendix A: Compiler error messages for the ranges::count example

Here’s the sample program again (Godbolt):

#include

template struct Holder { T t; }; struct Incomplete;

int main() { Holder *a[10] = {}; // ten null pointers // (void)std::count(a, a+10, nullptr); // OK on libstdc++ and libc++, hard error on Microsoft STL (void)std::ranges::count(a, a+10, nullptr); // hard error }

GCC (with libstdc++) says:

In instantiation of 'struct Holder': bits/iterator_concepts.h:292:6: required by substitution of 'template requires (__iter_without_nested_types<_Iterator>) && (__cpp17_iterator<_Iterator>) struct std::__iterator_traits<_Iter, void> [with _Iterator = std::projected<Holder, std::identity>]' bits/stl_iterator_base_types.h:177:12: required from 'struct std::iterator_traits<std::projected<Holder, std::identity> >' bits/iterator_concepts.h:191:4: required by substitution of 'template<class _Iter, class _Tp> requires __primary_traits_iter<_Iter> struct std::__detail::__iter_traits_impl<_Iter, _Tp> [with _Iter = std::projected<Holder, std::identity>; _Tp = std::indirectly_readable_traits<std::projected<Holder, std::identity> >]' bits/iterator_concepts.h:204:13: required by substitution of 'template<class _Iter, class _Tp> using __iter_traits = typename std::__detail::__iter_traits_impl::type [with _Iter = std::projected<Holder, std::identity>; _Tp = std::indirectly_readable_traits<std::projected<Holder, std::identity> >]' bits/iterator_concepts.h:278:13: required by substitution of 'template using __iter_value_t = typename std::__detail::__iter_traits_impl<_Tp, std::indirectly_readable_traits<_Iter> >::type::value_type [with _Tp = std::projected<Holder, std::identity>]' bits/iterator_concepts.h:283:11: required by substitution of 'template using iter_value_t = std::__detail::__iter_value_t<typename std::remove_cvref<_Tp>::type> [with _Tp = std::projected<Holder, std::identity>]' bits/iterator_concepts.h:515:11: required by substitution of 'template<class _Iter, class _Sent, class _Tp, class _Proj> requires (input_iterator<_Iter>) && (sentinel_for<_Sent, _Iter>) && (indirect_binary_predicate<std::ranges::equal_to, std::projected<_I1, _P1>, const _Tp*>) constexpr std::iter_difference_t<_Iter> std::ranges::__count_fn::operator()(_Iter, _Sent, const _Tp&, _Proj) const [with _Iter = Holder; _Sent = Holder; _Tp = std::nullptr_t; _Proj = std::identity]' required from here error: 'Holder::t' has incomplete type 5 | template struct Holder { T t; }; | ^ note: forward declaration of 'struct Incomplete' 4 | struct Incomplete; | ^~~~~~~~~~

Clang (with libc++, after applying [D121523]'s implementation of ranges::count) says:

error: field has incomplete type 'Incomplete' template struct Holder { T t; }; ^ __iterator/iterator_traits.h:151:9: note: in instantiation of template class 'Holder' requested here { *__i } -> __can_reference; ^ __iterator/iterator_traits.h:151:9: note: in instantiation of requirement here { *__i } -> __can_reference; ^~~~ __iterator/iterator_traits.h:150:3: note: while substituting template arguments into constraint expression here requires(_Ip __i) { ^~~~~~~~~~~~~~~~~~~ __iterator/iterator_traits.h:237:3: note: while checking the satisfaction of concept '__cpp17_iterator<std::projected<Holder **, std::identity>>' requested here __iterator_traits_detail::__cpp17_iterator<_Tp>; ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ __iterator/iterator_traits.h:237:29: note: while substituting template arguments into constraint expression here __iterator_traits_detail::__cpp17_iterator<_Tp>; ^~~~~~~~~~~~~~~~~~~~~ __iterator/iterator_traits.h:241:3: note: (skipping 19 contexts in backtrace; use -ftemplate-backtrace-limit=0 to see all) __cpp17_iterator_missing_members<_Tp> && ^ __iterator/concepts.h:212:3: note: while substituting template arguments into constraint expression here indirectly_readable<_It1> && indirectly_readable<_It2> && ^~~~~~~~~~~~~~~~~~~~~~~~~ __algorithm/ranges_count.h:35:14: note: while checking the satisfaction of concept 'indirect_binary_predicate<std::ranges::equal_to, std::projected<Holder **, std::identity>, const std::nullptr_t >' requested here requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Type> ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ __algorithm/ranges_count.h:35:14: note: while substituting template arguments into constraint expression here requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Type*> ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ note: while checking constraint satisfaction for template 'operator()<Holder **, Holder **, std::nullptr_t, std::identity>' required here (void)std::ranges::count(a, a+10, nullptr); // hard error ^ note: in instantiation of function template specialization 'std::ranges::__count::__fn::operator()<Holder **, Holder **, std::nullptr_t, std::identity>' requested here note: forward declaration of 'Incomplete' struct Incomplete; ^ 1 error generated.

MSVC (with Microsoft STL, which already does not ADL-proof std::count) says:

error C2079: 'Holder::t' uses undefined struct 'Incomplete' xutility(471): note: see reference to class template instantiation 'Holder' being compiled xutility(485): note: see reference to variable template 'bool _Cpp17_iterator<std::projected<Holder * *,std::identity> >' being compiled xutility(362): note: see reference to class template instantiation 'std::iterator_traits<std::projected<Holder **,std::identity>>' being compiled xutility(417): note: see reference to variable template 'bool _Is_from_primary<std::iterator_traits<std::projected<Holder * *,std::identity> > >' being compiled xutility(718): note: see reference to alias template instantiation 'std::iter_value_t<std::projected<Holder **,std::identity>>' being compiled xutility(728): note: see reference to variable template 'bool _Indirectly_readable_impl<std::projected<Holder * *,std::identity> >' being compiled xutility(904): note: see reference to variable template 'bool indirectly_readable<std::projected<Holder * *,std::identity> >' being compiled algorithm(466): note: see reference to variable template 'bool indirect_binary_predicate<std::ranges::equal_to,std::projected<Holder * *,std::identity>,std::nullptr_t const *>' being compiled