Raw pointer does not satisfy the requirements of RandomAccessIterator

[tomaszkam]

In the requirement of RandomAccessIterator<I> requires that I must satisfy TotallyOrder<I>. From the semantical requirement of 19.3.4 [concepts.lib.compare.totallyordered] p1, this requires that for all objects a, b, c of iterator type one of following is true: a < b, b < a, b == a. Non normative note placed below there requirements, states that this is not required to be true for not well-formed object (default constructed pointers/iterators), but does not exclude compare pointer to different arrays (which are well-formed).

Related question, does calling std::max(begin(v), end(v)) on vector of pointers to same array is well-formed, or it is now ill-formed? In other words, are we allowed to call sort with the comparator that does not impose total order on all values of given type, but is total order if we limit domain to collection of object passed in invocation?

Proposed Resolution

Modify the synopsis of the header <experimental/ranges/functional> in [function.objects] as follows:

 // 8.3.2, comparisons:
 template <class T = void>
-  requires EqualityComparable<T> || Same<T, void>
+  requires see below
 struct equal_to;

 template <class T = void>
-  requires EqualityComparable<T> || Same<T, void>
+  requires see below
 struct not_equal_to;

 template <class T = void>
-  requires StrictTotallyOrdered<T> || Same<T, void>
+  requires see below
 struct greater;

 template <class T = void>
-  requires StrictTotallyOrdered<T> || Same<T, void>
+  requires see below
 struct less;

 template <class T = void>
-  requires StrictTotallyOrdered<T> || Same<T, void>
+  requires see below
 struct greater_equal;

 template <class T = void>
-  requires StrictTotallyOrdered<T> || Same<T, void>
+  requires see below
 struct less_equal;

 template <> struct equal_to<void>;
 template <> struct not_equal_to<void>;
 [...]

Also modify the detailed specifications of the comparison function objects in [comparisons]:

 1 The library provides basic function object classes for all of the comparison operators in the
   language (ISO/IEC 14882:2014 §5.9, ISO/IEC 14882:2014 §5.10).

+? In this section, BUILTIN_PTR_CMP(T, OP, U) for types T and U and where OP is
+  an equality (\cxxref{expr.eq}) or relational operator (\cxxref{expr.rel}) is
+  a boolean constant expression. BUILTIN_PTR_CMP(T, OP, U) is true if and only
+  if OP in the expression declval<T>() OP declval<U>() resolves to a built-in
+  operator comparing pointers.
+
+? There is an implementation-defined strict total ordering over all pointer
+  values of a given type. This total ordering is consistent with the partial
+  order imposed by the builtin operators <, >, <=, and >=.

 template <class T = void>
   requires EqualityComparable<T> || Same<T, void>
+    || BUILTIN_PTR_CMP(const T&, ==, const T&)
 struct equal_to {
   constexpr bool operator()(const T& x, const T& y) const;
 };

-2 operator() returns x == y.
+2 operator() has effects equivalent to: return equal_to<>{}(x, y);

 template <class T = void>
   requires EqualityComparable<T> || Same<T, void>
+    || BUILTIN_PTR_CMP(const T&, ==, const T&)
 struct not_equal_to {
   constexpr bool operator()(const T& x, const T& y) const;
 };

-3 operator() returns x != y.
+3 operator() has effects equivalent to: return !equal_to<>{}(x, y);

 template <class T = void>
   requires StrictTotallyOrdered<T> || Same<T, void>
+    || BUILTIN_PTR_CMP(const T&, <, const T&)
 struct greater {
   constexpr bool operator()(const T& x, const T& y) const;
 };

-4 operator() returns x > y.
+4 operator() has effects equivalent to: return less<>{}(y, x);

 template <class T = void>
   requires StrictTotallyOrdered<T> || Same<T, void>
+    || BUILTIN_PTR_CMP(const T&, <, const T&)
 struct less {
   constexpr bool operator()(const T& x, const T& y) const;
 };

-5 operator() returns x < y.
+5 operator() has effects equivalent to return less<>{}(x, y);

 template <class T = void>
   requires StrictTotallyOrdered<T> || Same<T, void>
+    || BUILTIN_PTR_CMP(const T&, <, const T&)
 struct greater_equal {
   constexpr bool operator()(const T& x, const T& y) const;
 };

-6 operator() returns x >= y.
+6 operator() has effects equivalent to return !less<>{}(x, y);.

 template <class T = void>
   requires StrictTotallyOrdered<T> || Same<T, void>
+    || BUILTIN_PTR_CMP(const T&, <, const T&)
 struct less_equal {
   constexpr bool operator()(const T& x, const T& y) const;
 };

-7 operator() returns x <= y.
+7 operator() has effects equivalent to: return !less<>{}(y, x);

 template <> struct equal_to<void> {
   template <class T, class U>
-    requires EqualityComparableWith<T, U>
-  constexpr auto operator()(T&& t, U&& u) const
-    -> decltype(std::forward<T>(t) == std::forward<U>(u));
+    requires EqualityComparableWith<T, U> || BUILTIN_PTR_CMP(T, ==, U)
+  constexpr bool operator()(T&& t, U&& u) const;

   typedef unspecified is_transparent;
 };

-8 operator() returns std::forward<T>(t) == std::forward<U>(u).
+8 Requires: If the expression std::forward<T>(t) == std::forward<U>(u) results in a call to a
+   built-in operator == comparing pointers of type P, the conversion sequences from both
+   T and U to P shall be equality-preserving (\ref{concepts.lib.general.equality}).

+-?- Effects:
+(?.1) - If the expression std::forward<T>(t) == std::forward<U>(u) results in a call to a
+        built-in operator == comparing pointers of type P: returns false if either (the
+        converted value of) t precedes u or u precedes t in the implementation-defined
+        strict total order over pointers of type P and otherwise true.
+(?.2) - Otherwise, equivalent to: return std::forward<T>(t) == std::forward<U>(u);

 template <> struct not_equal_to<void> {
   template <class T, class U>
-    requires EqualityComparableWith<T, U>
-  constexpr auto operator()(T&& t, U&& u) const
-    -> decltype(std::forward<T>(t) != std::forward<U>(u));
+    requires EqualityComparableWith<T, U> || BUILTIN_PTR_CMP(T, ==, U)
+  constexpr bool operator()(T&& t, U&& u) const;

   typedef unspecified is_transparent;
 };

-9 operator() returns std::forward<T>(t) != std::forward<U>(u).
+9 operator() has effects equivalent to:
+    return !equal_to<>{}(std::forward<T>(t), std::forward<U>(u));

 template <> struct greater<void> {
   template <class T, class U>
-    requires StrictTotallyOrderedWith<T, U>
-  constexpr auto operator()(T&& t, U&& u) const
-    -> decltype(std::forward<T>(t) > std::forward<U>(u));
+    requires StrictTotallyOrderedWith<T, U> || BUILTIN_PTR_CMP(U, <, T)
+  constexpr bool operator()(T&& t, U&& u) const;

   typedef unspecified is_transparent;
 };

-10 operator() returns std::forward<T>(t) > std::forward<U>(u).
+10 operator() has effects equivalent to:
+     return less<>{}(std::forward<U>(u), std::forward<T>(t));

 template <> struct less<void> {
   template <class T, class U>
-    requires StrictTotallyOrderedWith<T, U>
-  constexpr auto operator()(T&& t, U&& u) const
-    -> decltype(std::forward<T>(t) < std::forward<U>(u));
+    requires StrictTotallyOrderedWith<T, U> || BUILTIN_PTR_CMP(T, <, U)
+  constexpr bool operator()(T&& t, U&& u) const;

   typedef unspecified is_transparent;
 };

-11 operator() returns std::forward<T>(t) < std::forward<U>(u).
+11 Requires: If the expression std::forward<T>(t) < std::forward<U>(u) results in a call to a
+   built-in operator < comparing pointers of type P, the conversion sequences from both
+   T and U to P shall be equality-preserving (\ref{concepts.lib.general.equality}). For any
+   expressions ET and EU such that decltype((ET)) is T and decltype((EU)) is U, exactly one 
+   of less<>{}(ET, EU), less<>{}(EU, ET) or equal_to<>{}(ET, EU) shall be true.

+-?- Effects:
+(?.1) - If the expression std::forward<T>(t) < std::forward<U>(u) results in a call to a
+        built-in 
+        operator < comparing pointers of type P: returns true if (the converted value of) t
+        precedes u in the implementation-defined strict total order over pointers of type P
+        and otherwise false.
+(?.2) - Otherwise, equivalent to: return std::forward<T>(t) < std::forward<U>(u);

 template <> struct greater_equal<void> {
   template <class T, class U>
-    requires StrictTotallyOrderedWith<T, U>
-  constexpr auto operator()(T&& t, U&& u) const
-    -> decltype(std::forward<T>(t) >= std::forward<U>(u));
+    requires StrictTotallyOrderedWith<T, U> || BUILTIN_PTR_CMP(T, <, U)
+  constexpr bool operator()(T&& t, U&& u) const;

   typedef unspecified is_transparent;
 };

-12 operator() returns std::forward<T>(t) >= std::forward<U>(u).
+12 operator() has effects equivalent to:
+     return !less<>{}(std::forward<T>(t), std::forward<U>(u));

 template <> struct less_equal<void> {
   template <class T, class U>
-    requires StrictTotallyOrderedWith<T, U>
-  constexpr auto operator()(T&& t, U&& u) const
-    -> decltype(std::forward<T>(t) <= std::forward<U>(u));
+    requires StrictTotallyOrderedWith<T, U> || BUILTIN_PTR_CMP(U, <, T)
+  constexpr bool operator()(T&& t, U&& u) const;

   typedef unspecified is_transparent;
 };

-13 operator() returns std::forward<T>(t) <= std::forward<U>(u).
+13 operator() has effects equivalent to:
+      return !less<>{}(std::forward<U>(u), std::forward<T>(t));

-14 For templates greater, less, greater_equal, and less_equal, the specializations for any
-   pointer type yield a total order, even if the built-in operators <, >, <=, >= do not.

[ericniebler]

Somewhere it needs to say that comparison ops for iterators are only required to be well-defined given iterators into the same range. So, in the domain of op< raw pointers are totally ordered.

[ericniebler]

is total order if we limit domain to collection of object passed in invocation

That.

[tomaszkam]

In other words, are we allowed to call sort with the comparator that does not impose total order on all values of given type, but is total order if we limit domain to collection of object passed in invocation?

This should apply not only for algorithms, but also to comparison operators of iterators wrappers like reverse_iterator. Or even on definition of TotalOrder in general.

[CaseyCarter]

This should apply not only for algorithms, but also to comparison operators of iterators wrappers like reverse_iterator. Or even on definition of TotalOrder in general.

The issue isn't specific to StrictTotallyOrdered, or to algorithms. Nearly every concept and every type that potentially satisfies that concept has some values that aren't in the definition space of some of the required expressions. We have a few paragraphs that apply library-wide in [structure.requirements]:

Required operations of any concept defined in this document need not be total functions; that is, some arguments to a required operation may result in the required semantics failing to be satisfied. [ Example: The required < operator of the StrictTotallyOrdered concept (19.3.4) does not meet the
semantic requirements of that concept when operating on NaNs.—end example ] This does not affect whether a type satisfies the concept.

A declaration may explicitly impose requirements through its associated constraints ([14.10.2] in the Concepts TS). When the associated constraints refer to a concept (N4377 [dcl.spec.concept]), additional semantic requirements are imposed on the use of the declaration.

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

Which are collectively intended to imply that it's the users responsibility to ensure that all the values of objects a library function is specified to access through its arguments are in a valid domain of all expressions required of their types by the associated constraints. So if you e.g. pass a range of double to std::sort(first, last), the associated constraints require std::less<> to satisfy StrictWeakOrder with double, and std::less<>::operator() requires double to be StrictTotallyOrdered. That is not the case if one of your doubles is a NaN; the semantic requirements of the declaration are not met. If you instead call std::sort(first, last, cmp) the associated constraints require decltype(cmp) to satisfy StrictWeakOrder. If cmp properly orders doubles including NaNs your program as well-formed.

I'm going to spend some time expanding and/or clarifying that wording in the next few days, so I'd appreciate any feedback.

[tomaszkam]

Which are collectively intended to imply that it's the users responsibility to ensure that all the values of objects a library function is specified to access through its arguments are in a valid domain of all expressions required of their types by the associated constraints. So if you e.g. pass a range of double to std::sort(first, last), the associated constraints require std::less<> to satisfy StrictWeakOrder with double, and std::less<>::operator() requires double to be StrictTotallyOrdered. That is not the case if one of your doubles is a NaN; the semantic requirements of the declaration are not met. If you instead call std::sort(first, last, cmp) the associated constraints require decltype(cmp) to satisfy StrictWeakOrder. If cmp properly orders doubles including NaNs your program as well-formed.

So, if I am understanding this correctly, we support types for which operator< defines partial order if user pass only totally ordered subsets of values to all STL2 algorithms used in program.

Do we allow operator< to be used as partial order outside from STL2 calls,, for example allow to have function is_totally_ordered that will check that for all pair of arguments a, b one of the following is true: a < b, a > b, a == b?

[CaseyCarter]

So, if I am understanding this correctly, we support types for which operator< defines partial order if user pass only totally ordered subsets of values to all STL2 algorithms used in program.

Yes, that's exactly correct; the semantics are all about observable behavior. If the expressions required by StrictTotallyOrdered impose a total ordering on the set of values with which a library function that requires StrictTotallyOrdered is specified to interact, it cannot observe behavior that does not satisfy the constraints.

Do we allow operator< to be used as partial order outside from STL2 calls, for example allow to have function is_totally_ordered that will check that for all pair of arguments a, b one of the following is true: a < b, a > b, a == b?

operator< can modify the arguments or set the computer on fire or launch the missiles outside the library, but its observable behavior when the library uses it must be to impose a total ordering.

[tomaszkam]

Yes, that's exactly correct; the semantics are all about observable behavior. If the expressions required by StrictTotallyOrdered impose a total ordering on the set of values with which a library function that requires StrictTotallyOrdered is specified to interact, it cannot observe behavior that does not satisfy the constraints.

This is important question regarding to requirement placed on operator< on object wrappers. If we care only about the values observable by library function, the user is free to specify partial ordered type, if he guarantee that input of all STL2 functions is totally ordered. In that case I think that operator< on reverse_iterator (and other wrappers) is over-specified. We should require operator< to only constitute some strict order and allow reverse_iterator to be used with other non-STL functions, that handle e.g. partially ordered type.

[CaseyCarter]

As it's specified now, reverse_iterator's operator< requires the two wrapped iterators to be totally ordered so that it can provide a total ordering for reverse_iterators, as is needed to satisfy RandomAccessIterator (we want reverse_iterator<RandomAccessIterator> to be a RandomAccessIterator). If I understand you correctly, you're suggesting we should relax the requirement and the resulting postcondition so that the ordering of reverse_iterator<I1> with reverse_iterator<I2> corresponds to the ordering of I1 with I2 instead of always requiring and providing StrictTotallyOrdered. Is that correct? What's the use case for this?

[tomaszkam]

Actually none of random access iterators defined in STL (raw pointer, array, vector, deque) are totally ordered, as they operator< is defined only if the point to the same collections. This is essentially example of partial order, as not all elements are in relation, and this case is not covered by eliminating singular values (NaN, default constructed iterator). So they are not RandomAccessIterator if you consider all well-formed values of this type.

We already agreed that for algorithms like sort and min, the requirement of StrictWeakOrder is imposed on the values of the elements passed to the invocation, so we actually do not care if T is partial or total order, only that the values seen be specific invocation are totally ordered. That means we only require that operator< on reverse_iterator will constitute total order on iterators passed to STL algorithm, but we have required it for essentially all uses of operator< not only inside STL2 functions. If we follow that direction for pairs or tuples we will essentially eliminate support for partially order types for this component, without having any gain. Notice that N4475 is explicitly supporting partially ordered types by requiring that <= is synthesized out of < and ==.

For use cases, we can imagine structure for which the comparison of iterators to different containers will return false from both <, >, instead of not being defined. In that case we could use is_totally_ordered (checks if one of a < b, a > b, a == b is true for each pair of elements) function on collection of iterators to check if they pointing to same array. Why this should be unsupported if I will wrap it in reverse_iterator?

[tomaszkam]

Sorry, for mistake. pair and tuple are not currently supporting partially ordered types, as they assume total order by implementing a <= b as !(a > b).

[CaseyCarter]

I now understand the problem description, and I think it's an interesting problem to solve. Actually I see two problems here:

1. How should the standard library handle orderings in general?
2. How can a concept-enabled library simultaneously provide strong semantics and the flexibility to support the solution of (1)

The second problem is in the purview of the Ranges TS in that we need to determine how to solve that problem for iterators and algorithms, but the first is out of scope. I think it would be waste of effort to attempt to address the second problem until the ongoing research in the committee settles on a solution for the first.

[ericniebler]

I now understand the problem description, and I think it's an interesting problem to solve.

@CaseyCarter Can you summarize the problem as you see it? I don't see an issue here.

See also issue #21, std::less and friends may be (are probably) over-constrained.

[CaseyCarter]

Equational reasoning doesn't need less et al. to impose requirements, it only needs them to preserve guarantees.

I had an epiphany that less can best support equational reasoning by providing a guarantee that it preserves the behavior of <. less doesn't need to require that its argument is StrictTotallyOrdered, or that < induces a strict weak ordering; the only guarantee we need fromless in generic code is thatless::operator()(a, b) == a < bwhenevera < bis defined. In other words, that the domain of <is a subset of the domain of less::operator() and that the two always agree where both are defined.

If you want a strict weak ordering that defaults to less<T>, you declare that:

template<class T, StrictWeakOrder<T> C = less<T>>
void f();

if you want T to be StrictTotallyOrdered, you don't need less to impose that requirement for you:

template <StrictTotallyOrdered T>
void g() {
  auto cmp = less<T>{};
  // Do stuff with cmp, which we know induces a strict total order because it cannot weaken
  // the guarantees provided by T.
}

Not that the definition of g looks exactly as it would with the current definition of less in the TS working paper: less requires its argument to be StrictTotallyOrdered, so g must enforce that requirement on its parameter type. f's declaration is possible with the current definition in the WP, but it has a slightly different meaning: f also needs its argument T to be StrictTotallyOrdered, albeit implicitly. If the writer of f doesn't want that added (over-)constraint, she can't use less.

Overconstraining the standard comparison function objects doesn't help writers of code that want stronger constraints, it only excludes writers of code that want weaker constraints.

I had planned to write a paper discussing this and proposing the proper semantic constraints for the default implementations of the comparison function objects and for user-defined specializations thereof, but the idea was crushed on the rocks of less<void> and the other transparent comparison function object types. I can't see a way to allow user customization of less that doesn't allow less<void> to become inconsistent. LWG2450 and LWG2562 both indicate how much trouble we've had keeping less<T*> and less<void> consistent with < for pointers; I'm not certain we're capable of devising a reasonable scheme allowing users to customize them. (Oh, and I forgot to mention that we're going to be fixing std::less again to allow comparison of pointers with nullptr_t, which the core language has decided is invalid.)

[CaseyCarter]

For now, I think perhaps the best we can do is to relax the requirements on the primary templates and forbid user specialization of less et al. That seems a better idea to me than allowing user specializations that much generic code will ignore anyway by using less<void>.

EDIT: "forbid user specialization" may be best enforced, as with iterator_traits, by replacing the template class with a template alias.

[CaseyCarter]

Someone needs to review this discussion thoroughly, and summarize the current status of the issue so we can properly assess if there's something here that still needs fixing.

[ericniebler]

@tomaszkam wrote:

Actually none of random access iterators defined in STL (raw pointer, array, vector, deque) are totally ordered, as they operator< is defined only if the point to the same collections. This is essentially example of partial order, as not all elements are in relation, and this case is not covered by eliminating singular values (NaN, default constructed iterator). So they are not RandomAccessIterator if you consider all well-formed values of this type.

This seems to presuppose something that doesn't match my understanding: that only singular values can fall outside the domain of an operation. Zero is a well-formed value of type int, and yet it is outside the domain of division when used as the denominator. I feel this basic (mis-)understanding has taken this discussion into the weeds.

We can carefully define the domain of required expressions, and for some operations we do (e.g. [iterators.sentinel]/p3). The operations are not required to be complete for the type to satisfy the concept. We already say that.

I am still of the opinion that pointers are totally ordered in the domain of op< on pointers. And I don't think it's wrong for less to require StrictTotallyOrdered.

[tomaszkam]

But if we move forward this path, then we can take any Partial Order r and create new order r' that is defined on following domain: (a, b) is in the domain of r' if r(a,b) or r(b,a) - i.e. domain of r' are pair of elements that or ordered in original order r. Now r' is Total Order (by definition, all elements in the domain are ordered).

We are following exactly the same reasoning for the op< on the pointers - we are saying that all pairs of pointers that are not ordered are outside domain. However, I still believe that we are stretching things too much, to make it just fit into the original design.

But all of above does not change the fact that op< is Partial Order on the domain P x P, where P is set of valid values of the pointers. Not all pairs of valid pointer values are ordered (they are not if they do not point to same array).

[tomaszkam]

Zero is a well-formed value of type int, and yet it is outside the domain of division when used as the denominator.

Let define D to be set of all well-formed values of int expect 0. Nowe division is an operation on D: i.e. transforms D x D into D.

But if you want to create an subset P of valid pointer values for which op< is Total Order (i.e. all pairs in P x P are ordered), you need to select only pointers pointing to one single array. So either:

• program can invoke sort only on pointers to one single array - and the P is defined statically
• requirements on the StrictWeakOrder are only applied to objects passed to given invocation of sort, i.e. are runtime conditions

[ericniebler]

But if we move forward this path, then we can take any Partial Order r and create new order r' that is defined on following domain: (a, b) is in the domain of r' if r(a,b) or r(b,a) - i.e. domain of r' are pair of elements that or ordered in original order r. Now r' is Total Order (by definition, all elements in the domain are ordered).

So the number of values that are outside the domain matters when deciding whether a type satisfied a concept? Not sure I buy that. There are by my count 2^23-1 different values of NaN in IEEE 754. Is that too many for double to be totally ordered? No, it's not.

we are saying that all pairs of poitners that are not ordered are outside domain

We are saying that pointers that are outside the domain are not ordered.

requirements on the StrictWeakOrder are only applied to objects passed to given invocation of sort, i.e. are runtime conditions

When users pass a range of pointers to sort, they plainly see from the algorithm's requirements that the relation must impose a strict weak ordering on the values passed in -- otherwise, the program is ill-formed, NDR. What's the problem?

[tomaszkam]

When users pass a range of pointers to sort, they plainly see from the algorithm's requirements that the relation must impose a strict weak ordering on the values passed in -- otherwise, the program is ill-formed, NDR. What's the problem?

There is no problem if we agree on that interpretation - we only care if the concept requirement are imposed on the values passed to the specific invocation, and we do not care about all other possible values of the objects of given type.

For example, is the following interpretation correct?

1. std::vector<A> vb{a}; std::ranges::sort(va); - we only care if following {a} x {a} (single element set) is totally ordered
2. std::vector<A> vb{a, b}; std::ranges::sort(vb); - we only care if following {a, b} x {a, b} (4 pairs of elements) is totally ordered

If only following two invocations are executed in program, the program is valid regardless of validity/result of the calls of op< on any other value of type A constructed in program.

[timsong-cpp]

Just like the IS, we say that less<T*> is a total order even when the built-in < isn't. So I assume that we want less<T*>()(pointer-to-one-array, pointer-to-another-array) to be valid.

But meanwhile less<T*> requires StrictTotallyOrdered<T*>, and the semantic requirements of that concept is only met when the pointer values point into the same array, so as far as I can tell the above expression renders the program ill-formed NDR.

[ericniebler]

Just like the IS, we say that less<T*> is a total order even when the built-in < isn't.

No we don't. We only make special accommodation for less<void *>.

we want less<T*>()(pointer-to-one-array, pointer-to-another-array) to be valid.

No we don't.

[timsong-cpp]

No we don't. We only make special accommodation for less<void *>.

My HTML generated from current trunk says - and so does the LaTeX source:

For templates greater, less, greater_equal, and less_equal, the specializations for any pointer type yield a total order, even if the built-in operators <, >, <=, >= do not.

Is there a pending issue resolution that I missed?

[ericniebler]

For templates greater, less, greater_equal, and less_equal, the specializations for any pointer type yield a total order, even if the built-in operators <, >, <=, >= do not.

Cripes. Is my memory glitching? Apologies for the FUD. :-(

But meanwhile less<T*> requires StrictTotallyOrdered<T*>, and the semantic requirements of that concept is only met when the pointer values point into the same array, so as far as I can tell the above expression renders the program ill-formed NDR.

Now wait a minute. I know we fixed this in 0f70344 as part of the discussion of #151. What happened to that change??? @CaseyCarter?

EDIT: Looks like @CaseyCarter reverted that fix in 8914792. I'm not sure why.

[CaseyCarter]

LEWG rejected the changes to the comparison function objects from P0370R0. The feeling was that it was too permissive to allow users to specialize the comparisons to have meaning different from the operators. My personal opinion is that the comparisons should impose no requirements on the parameters: they should be exactly and only names for the operators, propagating the requirements and properties of those operators.

The comparisons are virtually unimplementable in the IS right now. To impose a total ordering on pointers the comparisons must use representations, but to be usable in constant expressions they cannot access representations. Also, there's the problem that representations of pointers may not be fixed until load time. Queue the laugh track.

None of the above says anything about making the comparisons work with pointers in the TS. I agree that it's seriously murky what it means for e.g. less<int*> to require EqualityComparable<int*> and yet have a paragraph that says the specialization yields a total order even if the underlying operator does not. The best fix here would be split out the pointer behavior into a distinct function object(s) whose responsibility is to provide a total ordering for types whose natural order is not total like pointers and complex numbers. That definitely won't happen for Toronto. The quick fix would be to punch a hole in the requirements for pointers:

requires is_pointer<T>::value && is_pointer<U>::value || (/*...pre-existing requirements...*/)

[CaseyCarter]

The quick fix would be to punch a hole in the requirements for pointers

We could quickly extract the wording for just this change from 0f70344. (EDIT: instead of the obviously broken off-the-cuff suggestion I make above.)

[CaseyCarter]

As to the rest of the discussion: We've been trying to avoid having to state requirements on values by making it implicit that the values supplied to a library component that imposes requirements via Concepts must be in the domain of the operations those Concepts require. E.g. passing a vector<T> to ranges::sort(vec) requires StrictTotallyOrdered<T>, so either T must be totally ordered or the range must contain no pair of values that witnesses that T is not totally ordered.

This approach works great for components like the standard algorithms that operate only on supplied values and do not synthesize new values. It may fail completely for components that do synthesize values like the contents of <numeric>.

[CaseyCarter]

Resolution-in-progress. I will move this into the OP (and delete it from this post) when we're done with it.

(To avoid confusion, the PR-in-progress that was here has been removed.)

[timsong-cpp]

Hmm, does BUILTIN_PTR_CMP on the primary template punch too big a hole? less<convertible_to_pointer> isn't required to yield a total order even if the < resolves to a built-in pointer comparison.

[CaseyCarter]

Hmm, does BUILTIN_PTR_CMP on the primary template punch too big a hole?

Yes it does. I was planning to increase the scope to cover all specializations whose function call operator results in a call to a builtin pointer comparison and didn't make the changes to para 2. I'll let discussion here guide whether I finish that process - so the semantics are consistent - or back it out to what C++17 requires and give up on these things until after the TS.

EDIT: Specifically I mean that std::less<T> should be consistent with std::less<void>::operator< <T const&, T const&>.

EDIT AGAIN: Ok, this is a terrible idea. I don't want to screw up our chances of getting the TS out the door in Toronto in order to make a point about how broken the comparison function objects are. Backing out...

[CaseyCarter]

Backed out requirement to Same<T, void>() || is_pointer<T>::value || CONCEPT<T>() on the base templates.

Added a requirement for BUILTIN_PTR_CMP that declval<T>() OP declval<U>() must be equality preserving.

[ericniebler]

Do we have any idea if BUILTIN_PTR_CMP is even implementable? Do we care?

[CaseyCarter]

Do we have any idea if BUILTIN_PTR_CMP is even implementable? Do we care?

We sort-of hacked something up when we went through this the first time. IIRC:

• test that the expression is valid
• test that there's no non-member operator OP (T, U)
• test that there's no T.operator OP (U)
• test that T and U convert to void const volatile*

I honestly don't care. The worse it is, the easier it will be to convince WG21 to fix this mess in std2 by splitting less into two components.

[timsong-cpp]

declval<T>() OP declval<U>() must be equality preserving.

The current wording (incorrectly) says OP must be equality preserving, not the whole expression. Also, the built-in < on pointers is not equality preserving, so this needs some wordsmithing. I assume that the requirement is meant to be that the conversions to yield the operand type are equality preserving?

[CaseyCarter]

The call operator is what must be equality preserving, not the "expression that we don't actually use but that lets these types end-run around the semantic requirements." I think "the call operator yields a strict total order" is sufficient to require that it be equality-preserving without extra verbiage.

[timsong-cpp]

Yes, but the call operator can't possibly be a strict total order if the conversions-to-pointer aren't equality-preserving. I think we need to say that requirement somewhere?

[CaseyCarter]

Yes, but the call operator can't possibly be a strict total order if the conversions-to-pointer aren't equality-preserving. I think we need to say that requirement somewhere?

This is complicated by the fact that "if the call operator calls a built-in operator comparing pointers, the call operator yields a strict total order" implies that the "built-in operator comparing pointers" yields a strict total order. LWG 2562 completely contradicts the core language.

EDIT: I think LWG 2562 actually wants "if declval<T>() OP declval<U>() would invoke a built-in operator comparing pointers, the call operator instead yields a strict total order." which sounds even less implementable.

EDIT 2: "if the call operator calls a built-in operator comparing pointers, the call operator yields a strict total order" admits the possibility that the call operator "calls a built-in operator comparing pointers," discards the result of that operation, and then performs the strict total order magic. However, the specification of the call operators is "*Returns: std::forward<T>(t) < std::forward<U>(u)." So this library clause does in fact require the core language comparison operators over pointers to yield a strict total order.

EDIT 3: If you squint at it sideways hard enough, you could claim that when the result of a < b is unspecified a function specified to return a < b can return anything it likes and be consistent with that specification under as-if. Under that interpretation, the comparison objects can be specified to both return a < b and impose a total order on pointer arguments without necessarily requiring the core language operator to yield that total order.

What we want this to say is something like:

For template specializations less<void>, greater<void>, less_equal<void>, and greater_equal<void>, if the expression declval<T>() OP declval<U>() (where OP is respectively <, >, <=, or >=) would call a built-in operator comparing pointers, the call operator yields a strict total order that is consistent among those specializations and is also consistent with the partial order imposed by those built-in operators when applied to expressions ET and EU such that decltype((ET)) is T and decltype((EU)) is U.

but this needs to be specified as the behavior of the individual call operators, so maybe e.g. for less<void>:

Requires: The expression std::forward<T>(t) < std::forward<U>(u) shall be equality-preserving (\ref{FIXME}).

Effects: If the expression std::forward<T>(t) < std::forward<U>(u) would call a built-in operator comparing pointers, yields a strict total order that is consistent with the partial order imposed by that built-in operator. Otherwise, equivalent to: return std::forward<T>(t) < std::forward<U>(u);.

And for the other operators, delegate pointers to less<void>. e.g. greater<void>:

Requires: The expression std::forward<T>(t) > std::forward<U>(u) shall be equality-preserving (\ref{FIXME}).

Effects: If the expression std::forward<T>(t) > std::forward<U>(u) would call a built-in operator comparing pointers, equivalent to less<>{}(std::forward<U>(u), std::forward<T>(t)). Otherwise, equivalent to: return std::forward<T>(t) > std::forward<U>(u);.

The non-<void> operators have the same problem: the call operators are specified as e.g. "Returns: x < y." which together with "For templates less, greater, less_equal, and greater_equal, the specializations for any pointer type yield a strict total order that is consistent among those specializations and is also consistent with the partial order imposed by the built-in operators <, >, <=, >=." implies that the builtin operators must yield a strict total order. The fix here is to partially specialize each template for pointer types and apply the strict-total-order magic to the call operator of those specializations:

template <class T> struct less<T*> {
  constexpr operator()(T* x, T* y) const noexcept;
};

constexpr operator()(T* x, T* y) const noexcept;

1 Effects: Yields a strict total order that is consistent with the partial order imposed by the built-in operator <.

[ericniebler]

• For template specializations less, greater, less_equal, and
• greater_equal, if the call operator calls a built-in operator comparing pointers, the
• call operator yields a strict total order that is consistent among those specializations and
• is also consistent with the partial order imposed by those built-in operators.

... when the operation is well-defined.

[ericniebler]

The fix here is to partially specialize each template for pointer types and apply the strict-total-order magic to the call operator of those specializations:

Not sure that works. What about types like:

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

Then equal_to<S>::operator() ends up calling the built-in pointer comparison operator, and the partial ordering language applies here too.

[timsong-cpp]

Requires: The expression std::forward<T>(t) < std::forward<U>(u) shall be equality-preserving (\ref{FIXME}).

Once again, the built-in < on pointers is not equality-preserving in the result-is-unspecified cases.

Maybe we can simply add something like "for the purposes of this requirement, the built-in < operator is always considered equality-preserving".

[CaseyCarter]

Enormous PR update (now in the first post). I've specified foo<T>::operator() in terms of effects equivalent to foo<>::operator() to ensure consistency of the requirements and behavior of the <T> and <> forms. I've specified all of the other comparisons in terms of equal_to and less to ensure consistency. I've enforced consistency between equal_to<> and less<> "manually" with the hamfisted requirement that exactly one of equal_to<>{}(x, y), less<>{}(x, y) or less<>{}(y, x) must be true.

EDIT: Oh, and I removed the requirement that a OP b be equality-preserving. It's already required for StrictTotallyOrdered, and for pointer cases I separately require the conversion sequence from the parameter types to the underlying pointer type being compared to be equality preserving.