Project: | ISO JTC1/SC22/WG21: Programming Language C++ |
---|---|

Number: | P1380R1 |

Date: | 2019-01-20 |

Audience | CWG, LWG |

Revises: | P1380R0 |

Author: | Lawrence Crowl |

Contact | Lawrence@Crowl.org |

Lawrence Crowl, Lawrence@Crowl.org

Three-way comparisons are currently unsound. There are problems in the definition of three-way comparison functions and in the definition of template non-type parameter equivalence. We propose several small changes to improve the soundness of comparison.

Introduction

General Comparison Functions

16.11.4 Comparison algorithms [cmp.alg]

23.7.11 Three-way comparison algorithms [alg.3way]

Floating-Point Comparison Functions

16.11.4 Comparison algorithms [cmp.alg]

Non-Type Equivalence and Structural Equality

12.5 Type equivalence [temp.type]

10.10.1 Defaulted comparison operator functions [class.compare.default]

Revisions

P0100R0 Comparison in C++ introduced three-way comparison with the express purpose of making comparison sound. Programmers should be sure that their comparison operations meet the constraints of the algorithms they use.

Recent changes to the standard have made comparison less sound. Much of the problem seems to have arisen with the 'demotion' of the three-way comparison functions from specialization points providing the primary comparison mechanism to adjuncts to the three-way comparison operators.

Existing algorithms currently take a boolean comparison function. For compatibility with existing programs, these algorithms will continue to accept boolean comparisons. When we introduce three-way comparison into algorithms, we can do so in a sound manner without invalidating any existing code.

All wording edits are relative to N4778 Working Draft, Standard for Programming Language C++.

Comparison operators can serve two purposes, the application domain or the C++ standard algorithms. When these two purposes cannot be simultaneously satisfied, as with floating-point computation, the operators should be left to the application domain. To quote from P0100R2 Comparison in C++, "robust standard algorithms should never use [boolean] comparison operators". The consequence is that (a) C++ standard algorithms must accept three-way comparion functions and (b) those functions should not be 'automatically' defined in terms of boolean comparsion operators. However, the current definitions do define those functions in terms of boolean comparison operators. The intent of this paper is to change those definitions to reduce or expose errors.

The current definitions of several standard functions
infer a strong ordering from existing
`<`

and `==`

operators.
Unfortunately, doing so has a strong chance of making the program unsound.
For example, see Herb Sutter's `CaseInsensitiveString`

(
P0515R0 Consistent comparison).
If that class were written with traditional operators,
the existing `strong_order`

function
would silently promote the weak ordering to strong.
A strong ordering on user-defined types
takes special care to ensure substitutability.
As a consequence,
it is easy to write a class that fails to provide strong ordering.
So, we should not infer a strong ordering from non-3way operators.

In contrast, user-defined types are much more likely to provide a weak ordering on existing operators, if for no other reason than to enable use with the standard algorithms. So, infering a weak ordering from existing operators is far less problematic. However, there is still the potential to strengthen a partial ordering into a weak ordering. As currently defined, this strengthening causes silent failure. An exception is preferable to silent failure.

Constructing a strong ordering
from the existence of `<`

and `==`

has a strong chance of making the program unsound.
Furthermore, most algorithms do not need a strong ordering,
so the risk outweighs the reward.
Programmers that need the strong ordering can write it.

Remove paragraph 1.4.

(1.4) — Otherwise, if the expressions

`a == b`

and`a < b`

are each well-formed and convertible to bool, then

- (1.4.1) — if a == b is true, returns strong_ordering::equal;
- (1.4.2) — otherwise, if a < b is true, returns strong_ordering::less;
- (1.4.3) — otherwise, returns strong_ordering::greater.

Rather than silently promote partial orders to weak orders, we propose to detect comparisons that are not weak and throw an exception.

Edit paragraph 2.3 as follows.

(2.3) — Otherwise, if the expressions

`a == b`

and`a < b`

are each well-formed and convertible to bool, then

- (2.3.1) — if
`a == b`

is`true`

, returns`weak_ordering::equivalent`

;- (2.3.2) — otherwise, if
`a < b`

is`true`

, returns`weak_ordering::less`

;- (2.3.3) — otherwise, if
`b < a`

is`true`

, returns`weak_ordering::greater`

;- (2.3.4) — otherwise, throws
`std::domain_error`

.

Similarly, the definition for `partial_order`

incorrectly strengthens a partial ordering.

Edit paragraph 3.3 as follows.

(3.3) — Otherwise, if the expressions

`a == b`

and`a < b`

are each well-formed and convertible to bool, then

- (3.3.1) — if
`a == b`

is`true`

, returns`partial_ordering::equivalent`

;- (3.3.2) — otherwise, if
`a < b`

is`true`

, returns`partial_ordering::less`

;- (3.3.3) — otherwise, if
`b < a`

is`true`

, returns`partial_ordering::greater`

;- (3.3.4) — otherwise, returns
`partial_ordering::unordered`

.

Similarly to `strong_order`

,
`strong_equal`

unsafely strengthens the order of the operators.

Delete paragraph (4.3).

(4.3) — Otherwise, if the expression

`a == b`

is well-formed and convertible to`bool`

, then

- (4.3.1) — if
`a == b`

is`true`

, returns`strong_equality::equal`

;- (4.3.2) — otherwise, returns
`strong_equality::nonequal`

.

Paragraph 5 defining `weak_order`

is probably an acceptable default.
Programmers that use `operator ==`

for other purposes
will need to delete the overload.

As before, inferring a `strong_ordering`

or a `strong_equality`

from `<`

and `==`

is unsound.
Again, a weak ordering, with protection,
is probably acceptable.

Edit paragraph 1.2 for `compare_3way`

as follows.

(1.2) — Otherwise, if the expressions

`a == b`

and`a < b`

are each well-formed and convertible to`bool`

, returns`strong_ordering::equal`

`weak_ordering::equivalent`

when`a == b`

is`true`

, otherwise returns`strong_ordering::less`

`weak_ordering::less`

when`a < b`

is`true`

, and otherwise returns`strong_ordering::greater`

`weak_ordering::greater`

when`b < a`

is`true`

, and otherwise throws`std::domain_error`

.

(1.3) — Otherwise, if the expression

`a == b`

is well-formed and convertible to`bool`

, returns`strong_equality::equal`

`weak_equality::equivalent`

when`a == b`

is`true`

, and otherwise returns`strong_equality::nonequal`

`weak_equality::nonequivalent`

.

P1186R0 When do you actually use <=>
proposes to move this function definition
into the definition for `operator <=>`

.
If so done,
the edits here would apply to `operator <=>`

.

The boolean comparison operators for standard floating-point types have a partial order, so we have no reason to assume that non-standard floating-point types have stronger orders. Despite this, non-standard floating-point types are not explicitly handled.

There are reasons to wish for a weak ordering on floating-point types, particularly when keeping sets of 'normally distinguishable' values. We provide the means to do so.

The `strong_order`

function
has a special case for ISO/IEC/IEEE floating point.
However, when `is_iec559`

is `false`

,
there is no special handling of floating point.
The default algorithm may lead to intransitive 'greater' relations.
We propose to explicitly provide for non-standard floating point.

Edit paragraph 1.1 as follows.

(1.1) — If

`is_floating_point<T>::value`

is is`true`

, returns a result of type`strong_ordering`

that is a strong order and that is consistent with`T`

's comparison operators. If`numeric_limits<T>::is_iec559`

is also`true`

,~~returns a result of type~~that order must be consistent with the`strong_ordering`

that`totalOrder`

operation as specified in ISO/IEC/IEEE 60559.

Because standard floating point provides only a partial ordering,
we have a gap in the comparison strengths at weak ordering.
So, a similar special case is needed for a weak ordering.
This special case should be consistent
(
P0100R2 Comparion in C++, Consistency Between Relations)
with both `strong_order`

and the partial order implied by the operators.

Add a new subparagraph before (2.1) as follows.

(2.05) — If

`is_floating_point<T>::value`

is`true`

, returns a result of type`weak_ordering`

that is a weak order and is consistent with`T`

's comparison operators and with`strong_order`

. If`numeric_limits<T>::is_iec559`

is also`true`

, returns a result of type`weak_ordering`

that has the following equivalence classes ordered from lesser to greater.

- Together, all negative NaN values.
- Negative infinity.
- Separately, each normal and subnormal negative value.
- Together, both zero values.
- Separately, each normal and subnormal positive value.
- Positive infinity.
- Together, all positive NaN values.

The definition of non-type template parameter equivalence appeals to the <=> operator, but fails to specify the strength. Specifying a strong ordering solves the problem.

Note that using `strong_compare`

or `strong_equal`

instead of `operator <=>`

for non-type template argument equivalence
would enable more types as non-type template parameters,
particularly floating-point types.
We make no proposal here, but merely float the idea.
Doing so requires stable conversion
of decimal literals to floating-point values.

Template non-type argument equality is ambiguous; it fails to specify the strength of the equality. Since this ambiguity affects the application binary interface, we should be cautious and require strong equality.

Edit paragraph 1.5 as follows.

(1.5) — their remaining corresponding non-type

template-argumentshave the same type and value after conversion to the type of thetemplate-parameter, where they are considered to have the same value if they compare~~equal~~`std::strong_ordering::equal`

with`operator<=>`

, and

P1185R0 <=> != == proposes a "structural equality operator" (section 4.1 of the paper, section 10.10.1 of the standard). With adoption of P1185R0 or a successor, the above paragraph should be rewritten using strong structural equality.

Edit paragraph 1.5 as follows.

(1.5) — their remaining corresponding non-type

template-argumentshave the same type and value after conversion to the type of thetemplate-parameter, where they are considered to have the same value if they compare equal with a strong structural equality`operator<=>`

, and

P1185R0 <=> != == proposes a "structural equality operator" (section 4.1 of the paper, section 10.10.1 of the standard). This proposal calls out floating-point types as an exception, rather than calling out the fact that the comparison is not strong. This approach means that the standard has a stealth defect if it ever introduces a new built-in type without strong equality.

Edit the proposal in P1185R0 section 4.1 as follows.

An

`==`

(equal to) operator is a structural equality operator if:

- it is a built-in candidate ([over.built]) where
~~neither argument has floating point type~~both arguments have strong equality comparisions, or- it is an operator for a class type
`C`

that is defined as defaulted in the definition of`C`

and all`==`

operators it invokes are structural equality operators.A type

`T`

has strong structural equality if, for a glvalue`x`

of type`const T`

,`x == x`

is a valid expression of type`bool`

and invokes a structural equality operator.

From P1380R0:

Add contents.

Simplify the abstract.

Reorganize the presentation to topics, rather than sections in the standard.

Add introductory background material.

Define orderings for non-IEEE floating point types.

Improve exposition.

Correct bugs.

Remove the aside on the confusion of "explicitly defaulted functions defined as deleted".

Add a revision section.