Why does same_as concept check type equality twice?

Question

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 needed? The second is why same_as checks if T is the same as U and U the same as T? Isn't it redundant?

Thithia

Just because SameHelper<T, U> might be true doesn't mean SameHelper<U, T> might be. – Eous

that's the point, if a equals b, b equals a isnt't it? – Thithia

@Thithia Yes, and this is defining that relation. – Emitter

Hmm the documentation for std::is_same even says "Commutativity is satisfied, i.e. for any two types T and U, is_same<T, U>::value == true if and only if is_same<U, T>::value == true." This implies that this double check isn't necessary – Clutch

No, this is wrong, the std::is_same says: if and only if the condition holds, two types are commutative. This is not necessarily so. But I fail to find the example of two non-commutative types. – Upbear

What does "looking for an answer from a reputable source" mean? – Eolic

An answer which is not based on assumptions – Thithia

Answer 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.

Agee

same_as<T, U> and same_as<U, T> could also be different atomic contraints but their result would still be the same. Why the compiler cares so much about defining same_as as two different atomic constraints which from a logical point of view are the same? – Thithia

The compiler is required to consider any two expressions as distinct for constraint subsumption, but it can consider arguments to them in the obvious fashion. So not only do we need both directions (so that it doesn’t matter in which order they’re named when comparing constraints), we also need SameHelper: it makes the two uses of is_same_v derive from the same expression. – Jump

It seems conventional wisdom is wrong regarding concept equality. Unlike templates where is_same<T, U> is identical to is_same<U, T>, two atomic constraints are not considered identical unless they're also formed from the same expression. Hence the need for both. – Fraise

What about are_same_as? template<typename T, typename U0, typename... Un> concept are_same_as = SameAs<T, U0> && (SameAs<T, Un> && ...); would fail in some cases. For example are_same_as<T, U, int> would be equivalent to are_same_as<T, int, U> but not to are_same_as<U, T, int> – Thithia

Furthermore concepts cannot recursively refer to themselves so this template<typename T, typename U0, typename... Un> concept are_same_as = SameAs<T, U0> && (SameAs<T, Un> && ...) && (sizeof...(Un) == 0 || are_same_as<U, Un...>); would not be allowed – Thithia

@Thithia That deserves a separate question lol. I thought nested folding would work but actually it did not. – Agee

I'll try to look for a solution by myself before asking – Thithia

Answer 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>;

1. 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>;

1. [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.

Protuberancy

So this boils down that compiler does not know/can not assume that is_same is symmetric, since for example has_greater_sizeof<A,B> is obviously not symmetric? And there is no nice way to spell it in language like "symmetric_concept" keyword. – Minutes

I think the proposed fix was saying that the original implementation only works because of compiler magic (not because [temp.constr.order] mandates so). – Agee

"could .. go down the rabbit hole ... to show that even in the older implementation ... same_as<T, U> would still subsume same_as<U, T>" Do you mean "the standard could be fixed to make it work", or "it should already work"? It doesn't seem to work on existing compilers: gcc.godbolt.org/z/q5hq1b3ME – Porkpie

Answer 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.

Mulberry

I agree with you, but this last argument is a bit of a stretch. To me, it sounds like: "Hey, I have this reusable component that tells me whether two types are the same. Now I have this other component that needs to know whether to types are the same, but, instead of reusing my previous component, I'll just create an ad-hoc solution specific to this case. Now I've 'decoupled' the guy who needs the definition of equality from the guy who has the definition of equality. Yay!" – Capitulate

@CássioRenan Sure. Like I said, I don't know why, that's just best reasoning that I could come up with. The authors may have a better rationale. – Mulberry