Why does same_as concept check type equality twice?

Looking at the possible implementation of the same_as concept at https://en.cppreference.com/w/cpp/concepts/same_as i noticed something strange is happening.

namespace detail {
    template< class T, class U >
    concept SameHelper = std::is_same_v<T, U>;
}

template< class T, class U >
concept same_as = detail::SameHelper<T, U> && detail::SameHelper<U, T>;

The first question is why a SameHelper concept is nedded? The second is why same_as checks if T is the same as U and U the same as T? Isn't it redundant?

Solution 1:

Interesting question. I have recently watched Andrew Sutton's talk on Concepts, and in the Q&A session someone asked the following question (timestamp in the following link): CppCon 2018: Andrew Sutton “Concepts in 60: Everything you need to know and nothing you don't”

So the question boils down to: If I have a concept that says A && B && C, another says C && B && A, would those be equivalent? Andrew answered yes, but pointed out the fact the compiler has some internal methods (that is transparent to the user) to decompose the concepts into atomic logical propositions (atomic constraints as Andrew worded the term) and check whether they are equivalent.

Now look at what cppreference says about std::same_as:

std::same_as<T, U> subsumes std::same_as<U, T> and vice versa.

It is basically an "if-and-only-if" relationship: they imply each other. (Logical Equivalence)

My conjecture is that here the atomic constraints are std::is_same_v<T, U>. The way compilers treat std::is_same_v might make them think std::is_same_v<T, U> and std::is_same_v<U, T> as two different constraints (they are different entities!). So if you implement std::same_as using only one of them:

template< class T, class U >
concept same_as = detail::SameHelper<T, U>;

Then std::same_as<T, U> and std::same_as<U, T> would "explode" to different atomic constrains and become not equivalent.

Well, why does the compiler care?

Consider this example:

#include <type_traits>
#include <iostream>
#include <concepts>

template< class T, class U >
concept SameHelper = std::is_same_v<T, U>;

template< class T, class U >
concept my_same_as = SameHelper<T, U>;

template< class T, class U> requires my_same_as<U, T>
void foo(T a, U b) {
    std::cout << "Not integral" << std::endl;
}

template< class T, class U> requires (my_same_as<T, U> && std::integral<T>)
void foo(T a, U b) {
    std::cout << "Integral" << std::endl;
}

int main() {
    foo(1, 2);
    return 0;
}

Ideally, my_same_as<T, U> && std::integral<T> subsumes my_same_as<U, T>; therefore, the compiler should select the second template specialization, except ... it does not: the compiler emits an error error: call of overloaded 'foo(int, int)' is ambiguous.

The reason behind this is that since my_same_as<U, T> and my_same_as<T, U> does not subsume each other, my_same_as<T, U> && std::integral<T> and my_same_as<U, T> become incomparable (on the partially ordered set of constraints under the relation of subsumption).

However, if you replace

template< class T, class U >
concept my_same_as = SameHelper<T, U>;

with

template< class T, class U >
concept my_same_as = SameHelper<T, U> && SameHelper<U, T>;

The code compiles.

Solution 2:

[concept.same] was changed as part of LWG issue 3182 (before the concept Same was renamed to is_same as per P1754R1) [emphasis mine]:

3182. Specification of Same could be clearer

Section: 18.4.2 [concept.same]

Status: WP

[...]

Discussion:

The specification of the Same concept in 18.4.2 [concept.same]:
template<class T, class U>
  concept Same = is_same_v<T, U>;
Same<T, U> subsumes Same<U, T> and vice versa.
seems contradictory. From the concept definition alone, it is not the case that Same<T, U> subsumes Same<U, T> nor vice versa. Paragraph 1 is trying to tell us that there's some magic that provides the stated subsumption relationship, but to a casual reader it appears to be a mis-annotated note. We should either add a note to explain what's actually happening here, or define the concept in such a way that it naturally provides the specified subsumption relationship.

Given that there's a straightforward library implementation of the symmetric subsumption idiom, the latter option seems preferable.

[...]

Proposed resolution:

This wording is relative to N4791.

Change 18.4.2 [concept.same] as follows:
template<class T, class U>
  concept same-impl = // exposition only
    is_same_v<T, U>;

template<class T, class U>
  concept Same = is_same_v<T, U>same-impl<T, U> && same-impl<U, T>;
[Note: Same<T, U> subsumes Same<U, T> and vice versa. — end note]

I will start addressing the second question of the OP (as the answer to the first question will follow from it):

OP: The second is why same_as checks if T is the same as U and U the same as T? Isn't it redundant?

As per the last part emphasized above:

[...] Given that there's a straightforward library implementation of the symmetric subsumption idiom, the latter option seems preferable.

the resolution to CWG 3182 was to redefine the library spec to use two symmetric constraints specifically to fulfill the subsumption relationsship between the two ("the symmetric subsumption idiom", if you will) in a (semantically) natural way.

As a tangent (but relevant to answer OP's first question), this can be important for partial ordering by constraints, as per [temp.constr.order], particularly [temp.constr.order]/1 and [temp.constr.order]/3

/1 A constraint P subsumes a constraint Q if and only if, [...] [ Example: Let A and B be atomic constraints. The constraint A ∧ B subsumes A, but A does not subsume A ∧ B. The constraint A subsumes A ∨ B, but A ∨ B does not subsume A. Also note that every constraint subsumes itself. — end example ]

/3 A declaration D1 is at least as constrained as a declaration D2 if

(3.1) D1 and D2 are both constrained declarations and D1's associated constraints subsume those of D2; or

(3.2) D2 has no associated constraints.

Such that in the following example:

#include <iostream>

template <typename T> concept C1 = true;    
template <typename T> concept C2 = true; 

template <typename T> requires C1<T> && C2<T> // #1
void f() { std::cout << "C1 && C2"; }

template <typename T> requires C1<T>          // #2
void f() { std::cout << "C1"; }

a call to, say, f<int>(), is not ambiguous (#1 will be called) as the constraints at #1, C1<T> && C2<T>, subsumes the constraint at #2, C1<T>, but not vice versa.

We could, however, go down the rabbit hole of [temp.constr.order] and [temp.constr.atomic] to show that even in the older implementation of same_as:

// old impl.; was named Same back then
template<typename T, typename U>
concept same_as = is_same_v<T, U>;

same_as<T, U> would still subsume same_as<U, T> and vice versa; this is not entirely trivial, however.

Thus, instead of choosing the option of "add a note to explain what's actually happening here" to resolve LWG 3182, [concept.same] instead changed the library implementation to be defined in a form that had a clearer semantic meaning to the "casual reader":

// A and B are concepts
concept same_as = A ^ B

As per the (tangential) part above, we may also note that same_as subsumes both the concepts A and B in isolation, whereas A and B in isolation does not subsume same_as.

OP: The first question is why a SameHelper concept is nedded?

As per temp.constr.order]/1, only concepts can be subsumed. Thus, for the older implementation of the concept, where the is_same transformation trait (which is not a concept) was used directly, the trait itself did not fall under the subsumption rules. Meaning an implementation as follows:

template< class T, class U >
concept same_as = std::is_same_v<T, U> && std::is_same_v<U, T>

would truly contain a redundant r.h.s. for &&, as type traits cannot subsume type traits. When LWG 3182 was resolved, and an intention was to semantically show the subsumption relationship as per above, an intermediate concept was added to place emphasis on subsumption.

Solution 3:

std::is_same is defined as true if and only if:

T and U name the same type with the same cv-qualifications

As far as I know, standard doesn't define the meaning of "same type", but in natural language and logic "same" is an equivalence relation and thus is commutative.

Given this assumption, which I ascribe to, is_same_v<T, U> && is_same_v<U, V> would indeed be redundant. But same_as is not specified in terms of is_same_v; that is only for exposition.

The explicit check for both allows for the implementation for same-as-impl to satisfy same_as without being commutative. Specifying it this way describes exactly how the concept behaves without restricting how it could be implemented.

Exactly why this approach was chosen instead of specifying in terms of is_same_v, I don't know. An advantage of the chosen approach is arguably that the two definitions are de-coupled. One does not depend on the other.

Why does same_as concept check type equality twice?

Solution 1:

Solution 2:

3182. Specification of Same could be clearer

Solution 3:

Related

Recent Posts