<algorithm>: unqualified calls to _Adl_verify_range incorrectly cause instantiation

[CaseyCarter]

Our implementation rejects this well-formed program (derived from the libc++ test that fails because of this bug):

#include <algorithm>
#include <iterator>

struct incomplete;

template <class T>
struct wrapper {
    T t;
};

int main() {
    wrapper<incomplete>* some_pointers[42]{};
    std::sort(std::begin(some_pointers), std::end(some_pointers));
}

by trying to instantiate wrapper<incomplete> despite that such instantiation is not necessary. The unqualified call to _Adl_verify_range(_First, _Last) (which appears in most algorithms, std::sort is simply an exemplar) necessitates instantiation of wrapper<incomplete> when _First has type wrapper<incomplete>**.

The problem runs deeper than simply _STD-qualifying _Adl_verify_range:

• the machinery it uses presumably makes other unqualified calls that will need to be dealt with, and
• the unqualified call to _Verify_range should be avoided when the arguments are pointers.

[cpplearner]

I think this is a duplicate of #140.

[miscco]

I never really grogged how that magic works, but doesnt _Range_verifiable_v<_Iter, _Sentinel> already require the type to be instantiated?

if so would we need to do something like

template <class _Iter, class _Sentinel>
constexpr void _Adl_verify_range(const _Iter& _First, const _Sentinel& _Last) {
    // check that [_First, _Last) forms an iterator range
    if constexpr (is_pointer_v<_Iter> && is_pointer_v<_Sentinel>) {
         _STL_VERIFY(_First <= _Last, "transposed pointer range");
    } else if constexpr (_Range_verifiable_v<_Iter, _Sentinel>) {
        _Verify_range(_First, _Last);
    }
}

[CaseyCarter]

I think this is a duplicate of #140.

It's certainly related; I should have linked #140 in my submission. We've moved a bit beyond the hypothetical of #140 now that there are libc++ tests that we will have to avoid running.

I never really grogged how that magic works,

grog; grok =)

but doesn't _Range_verifiable_v<_Iter, _Sentinel> already require the type to be instantiated?

Yes. Any unqualified call (or operator use) with the meow** argument type needs to determine its associated namespace and entities, which are those of meow*, which are those of meow, which will instantiate meow if it's a template specialization to determine its base classes. The _Verify_range call in _Range_verifiable_v is a good example. Following the general Casey principal that "we shouldn't allow users to customize the behavior of pointers because I don't want to ever work on code where pointers mean something different from what the core language says" we should never call customization hooks for pointer types. Avoiding lookup for things we shouldn't be calling anyway seems like a good idea.

if so would we need to do something like

template <class _Iter, class _Sentinel>
constexpr void _Adl_verify_range(const _Iter& _First, const _Sentinel& _Last) {
    // check that [_First, _Last) forms an iterator range
    if constexpr (is_pointer_v<_Iter> && is_pointer_v<_Sentinel>) {
         _STL_VERIFY(_First <= _Last, "transposed pointer range");
    } else if constexpr (_Range_verifiable_v<_Iter, _Sentinel>) {
        _Verify_range(_First, _Last);
    }
}

Yes, this seems necessary but I haven't given enough thought to determine if it's sufficient.