`std::less<T*>` is ill-formed.

[tomaszkam]

According to the current version of the Range TS, the std::less<T> is requiring that T should should satisfy StrictTotalOrder or be same as void. Notice that both of this constrain are not satisfied if T is an pointer type, as operator< is required to represent only partial (points to same array) order on pointer types, and this breaks semantics for StrictTotalOrder concept. According to 17.5.1.3 [structure.requirements] p9 this makes programs using std::less with pointer type are ill-formed.:

If the semantic requirements of a declaration are not satisfied at the point of use, the program is ill-formed, no diagnostic required.

This is esentailly contradiction to initial purpose of introduction of std::less wrappers that was designed to provide an total order for poitner types. The resolution may be to change the requirement for std::less (and others) to require that T is either void, pointer or models StrictTotalOrder,

[asutton]

Maybe we should define the comparators as:

template struct less;

template<> struct less { ... };

template struct less<T*> { ... };

template struct less { ... };

If a top-level constraint is needed:

template requires is_void_c || is_pointer_c || TotallyOrdered() struct less;

Typical usage means you're going to instantiate the comparator immediately, so you wouldn't get bad errors messages --- actually they might be better (no specialization found, candidates are...)

Andrew Sutton

On Tue, Nov 17, 2015 at 6:05 AM, tomaszkam notifications@github.com wrote:

According to the current version of the Range TS, the std::less is requiring that T should should satisfy StrictTotalOrder or be same as void. Notice that both of this constrain are not satisfied if T is an pointer type, as operator< is required to represent only partial (points to same array) order on pointer types, and this breaks semantics for StrictTotalOrder concept. According to 17.5.1.3 [structure.requirements] p9 this makes programs using std::less with pointer type are ill-formed.:

If the semantic requirements of a declaration are not satisfied at the point of use, the program is ill-formed, no diagnostic required.

This is esentailly contradiction to initial purpose of introduction of std::less wrappers that was designed to provide an total order for poitner types. The resolution may be to change the requirement for std::less (and others) to require that T is either void, pointer or models StrictTotalOrder,

— Reply to this email directly or view it on GitHub https://github.com/ericniebler/stl2/issues/151.

[CaseyCarter]

There should definitely not be a top-level constraint on the template. There's no need to constrain which types may have an ordering defined for them, all we need do is constrain the specializations to apply only to types they are capable of ordering. The effect of the top-level constraint is to forbid me to specialize less for Widget unless Widget is StrictTotallyOrdered, which is ridiculous. If that were the case I likely wouldn't be bothering to specialize less.

It would be convenient if user specializations of less were required to satisfy StrictWeakOrder - as the library-supplied implementations do - so that generic code that requires an ordering for T is guaranteed that less<T> provides one if it is defined.

[ericniebler]

Agree with all of this. I'll make the change.

[asutton]

There should definitely not be a top-level constraint on the template. There's no need to constrain which types may have an ordering defined for them, all we need do is constrain the specializations to apply only to types they are capable of ordering.

Good point.

It would be convenient if user specializations of less were required to satisfy StrictWeakOrder - as the library-supplied implementations do - so that generic code that requires an ordering for T is guaranteed that less provides one if it is defined.

I think that needs be stated. If a user specialization does not define a strict weak order, then it is likely to be used in a way that produces undefined behavior.

Maybe as a general rule: if the template is designed for user specialization and has an unconstrained or weakly constrained primary, then a concept must specify the postcondition of instantiation.

[ericniebler]

We currently appear to be somewhat schizophrenic about whether less and friends require/impose a strict weak order or a strict total order. I think this is because the Palo Alto TR strengthened the requirements of the sorting algorithms from weak to total, and I flubbed it when I merged things into the Ranges TS. What should we do? Change StrictWeakOrder to StrictTotalOrder and make the corresponding changes everywhere?

[CaseyCarter]

Maybe as a general rule: if the template is designed for user specialization and has an unconstrained or weakly constrained primary, then a concept must specify the postcondition of instantiation.

This is definitely something I'd like to see in a future Concepts TS; a mechanism to allow a class template definition to specify constraints on its specializations:

template <C1 T = void>
  requires C2<T>
struct foo
  __strawman_syntax__ C3<foo<T>>
{
 // ...
};

template <C4 T>
  requires C5<T>
struct foo<T>
  __strawman_syntax__ C6<foo<T>>
{
  // ...
};

such that the program is ill-formed if the instantiated specialization foo<Widget> does not satisfy the constraint expressions introduced by __strawman_syntax__ for every declaration of foo whose parameter constraints are satisfied by Widget. This would ensure that foo<T> satisfies C3, and also satisfies C6 if T satisfies C4 and C5, regardless of the existence of any other specializations of foo. It would be nice to ensure that e.g. less<T> is always a StrictWeakOrder and vector<T, A> is always a Container.

[tomaszkam]

There should definitely not be a top-level constraint on the template. There's no need to constrain which types may have an ordering defined for them, all we need do is constrain the specializations to apply only to types they are capable of ordering.

I would like to point out that both STL1, that uses operator<, directly and STL2, that uses std::less<void>, are essentially ignoring user defined specialization of less. I thought that less<void> was changed to provide total order for pointers, but failed to see that change in recent working draft.

I think this is because the Palo Alto TR strengthened the requirements of the sorting algorithms from weak to total, and I flubbed it when I merged things into the Ranges TS.

Please correct me, but if I am understanding you correctly, sort now requires that strict total order, so this means that for pair of elements, either one of them is less than other, or their are exactly the same. Then was it the point of having sort and stable_sort in this case, as same elements by definition are indistinguishable.

[ericniebler]

Nevermind. The Palo Alto TR doesn't require the relation used to sort to induce a strict total order. Rather, if no relation is passed, the value type of the sequence must be totally ordered. Sorry for the noise. I'll double-check that we got it right in the TS.

[tomaszkam]

The issue that requires less<void> to provide total order on pointers has Tentatively Ready status (http://cplusplus.github.io/LWG/lwg-active.html#2450). So we will probably need to look on StrictTotallyOrdered{T, U} requirement placed on operator() for diamond comparators.

[ericniebler]

Reading lwg#2450, I was stumped at first how to detect whether a<b would call the builtin op< on pointers. But I came up with this, and it seems to work. Any ideas for simplification? I'd rather not duplicate this 4 times for <, <=, >, >=.

#include <string>

namespace __udl {
    void operator<(auto&&, auto&&) = delete;

    template<class A, class B>
    concept bool _BuiltinPtrLess =
        requires(A&& a, B&& b) {
            (A&&)a < (B&&)b;
            {true ? (A&&)a : (B&&)b} -> auto*;
        } &&
        !requires(A&& a, B&& b) {
            ((A&&)a).operator<((B&&)b);
        } &&
        !requires(A&& a, B&& b) {
            operator<((A&&)a, (B&&)b);
        };
}

template<class A, class B>
constexpr bool builtin_ptr_less = false;
__udl::_BuiltinPtrLess{ A, B }
constexpr bool builtin_ptr_less<A, B> = true;

struct S {
    operator void*() const { return nullptr; }
};

struct T {
    operator void*() const { return nullptr; }
};

bool operator<(S, T) { return false; }

struct U {
    operator void*() const { return nullptr; }
};

struct V {
    operator void*() const { return nullptr; }
};

static_assert(!builtin_ptr_less<int, int>, "");
static_assert(builtin_ptr_less<int*, int const*>, "");
static_assert(builtin_ptr_less<int[], int const*>, "");
static_assert(builtin_ptr_less<int[], int[5]>, "");
static_assert(builtin_ptr_less<int*, decltype(nullptr)>, "");
static_assert(!builtin_ptr_less<std::string, std::string>, "");
static_assert(!builtin_ptr_less<S, T>, "");
static_assert(builtin_ptr_less<U, V>, "");

[CaseyCarter]

struct A {
  constexpr operator void*() const { return nullptr; }
};

struct B : A {};

static_assert(!(A{} < B{}));
static_assert(builtin_ptr_less<A, B>); // Failure
static_assert(__is_same_as(A, decltype(true ? A{} : B{}))); // Because of this

I doubt it's possible to implement this portably.

[ericniebler]

Can you break this?

void operator<(auto&&, auto&&) = delete;
struct __convertible_to_pointer {
    __convertible_to_pointer(const volatile void*);
};

template<class A, class B>
concept bool _BuiltinPtrLess =
    requires(A&& a, B&& b) {
        (A&&)a < (B&&)b;
        {true ? (A&&)a : (B&&)b} -> __convertible_to_pointer;
    } &&
    !requires(A&& a, B&& b) {
        ((A&&)a).operator<((B&&)b);
    } &&
    !requires(A&& a, B&& b) {
        operator<((A&&)a, (B&&)b);
    };

[CaseyCarter]

Stumbled across that a few minutes after posting, except I'm just using -> const volatile void*. Haven't broken it yet.

[CaseyCarter]

struct C {};
constexpr bool operator<(C, C) { return true; }

struct A : C {
  constexpr operator void*() const { return nullptr; }
};

struct B : C {
  constexpr operator int*() const { return nullptr; }
};

static_assert(A{} < B{});
static_assert(builtin_ptr_less<A, B>); // Failure

Don't ask me to figure out overload resolution for < here, I just know that it's calling the C overload because A{} < B{} is true ;)

[ericniebler]

Stop it.

[ericniebler]

I don't get it. The expression operator<(A{}, B{}) compiles, so it should not satisfy _BuiltinPtrLess. What's going on here?

[CaseyCarter]

The poison pill is a better match than operator<(C, C).

[ericniebler]

Oh! Yeah, just delete the poison pill. It's not needed.

[ericniebler]

Where in the current standard does it say that users can specialize less? Can they specialize greater?

[CaseyCarter]

17.6.4.2.1 [namespace.std]/1:

The behavior of a C++ program is undefined if it adds declarations or definitions to namespace std or to a namespace within namespace std unless otherwise specified. A program may add a template specialization for any standard library template to namespace std only if the declaration depends on a user-defined type and the specialization meets the standard library requirements for the original template and is not explicitly prohibited.

So for e.g. less, we need to somehow require StrictWeakOrder<less<T>, T>() and/or StrictWeakOrder<less<>, T, U>() to ensure that users can't break it.

[CaseyCarter]

[unord.hash]/1 is the perfect example:

The unordered associative containers defined in 23.5 use specializations of the class template hash as the default hash function. For all object types Key for which there exists a specialization hash<Key>, and for all integral and enumeration types (7.2) Key, the instantiation hash<Key> shall:

(1.1) — satisfy the Hash requirements (17.6.3.4), with Key as the function call argument type, the Default-Constructible requirements (Table 19), the CopyAssignable requirements (Table 23),

(1.2) — be swappable (17.6.3.2) for lvalues,

(1.3) ...

We want the words of power:

For all object types T for which there exists a specialization less<T>, the instantiation less<T> shall satisfy StrictWeakOrder<less<T>, T>().

and....something else for less<void>. Correction, we don't need anything for less<void>. We already ensure that it provides a StrictWeakOrder.

[tomaszkam]

Maybe we should propose that pointer comparision should inflict total order on all architectures. We recently got the change that define order of evaolution of arguments. In comments from the issue I have linked, STL is claiming that there on all currently used architectures pointers are totally ordered anyway.

[ericniebler]

Fixed in 0f70344

[tomaszkam]

I noticed that the change from the http://cplusplus.github.io/LWG/lwg-active.html#2450 is introducing breakage in all programs that will use ordering algorithms (min, sort, etc.) on raw pointers/iterators to same container without specialized comparator. This is caused by the fact that STL1 was using operator< that was representing address ordering, but now we use less<void> that provide total order, but this new relation is not required to be compatible with one imposed by operator<. I mean that we do not require that less<void>(a,b) is equivalent to a < b, when the later is well-defined.

Basically I am saying that we need to incorporate N4229: Pointer Ordering.

[CaseyCarter]

It's a shame I hadn't seen N4229 before, I submitted a library issue when we fixed this in the TS 2 days ago with almost exactly the same proposed resolution.