RFC 1445 introduced the notion of a type supporting "structural match", which enables constants of that type to be used in patterns. The goal was to only let primitive types and types with derive(PartialEq, Eq) participate in patterns. Since then the #[structural_match] attribute was replaced by two traits: StructuralPartialEq and StructuralEq. More recently, a value-based analysis was introduced as an alternative to the type-based traits.

In the past, if my understanding is correct, this was only used as a kind of "lint" to avoid strange behavior on match. (Though there are some question marks here and some matches on constants can affect exhaustiveness checking, which is crucial for soundness.) But my understanding is that recently, it also started playing a role around const generics -- and thus the entire story could become critical for soundness, and I start to become interested. ;) So far, the traits mentioned above are safe, so in principle nothing can depend on them for soundness. They are also unstable though, so any such soundness issue would affect just nightly Rust.

There is a lot of good documentation on when and how these traits are implemented, but what I am missing is good documentation on what the trait means. I have the feeling that there is a very concrete guarantee associated with these traits, a guarantee that const generics and match both would like to rely on. I'd like to "tease out" that guarantee from the existing trait and analysis with the benefit of hindsight, and then hopefully that enables us to simplify this story, or at least document it better.

So, here is what I think the guarantee is, based on what I saw so far:

• A value v has structural equality if (a) it can be converted to a value tree, and (b) PartialEq::eq(v, v2) returns true if and only if the value tree representation of v2 equals that of v (in particular, if v2 cannot be represented in a value tree, the return value must be false).
• A type has structural equality if all of its values do.

Now I wonder, does this make sense? Of course this is slightly hypothetical as value trees are not implemented yet, but in most cases I think it is intuitively clear what the tree for a value looks like -- and when it is not clear, it likely has no tree. (In particular, unions, raw pointers [except when cast from an integer] and function pointers cannot be represented in a value tree.) I think this is exactly the guarantee that const generics need, but I only have a birds-eye view of const generics so I am not certain of this. And this also seems closely related to the idea of "which const values are reasonable to use as a pattern". I'd be interested in any counterexamples that you might know of.

If this definition works, then I think we could replace both of the Structural* traits by a single marker trait that just represents this guarantee. But to evaluate if that definition makes sense, we first have to figure out what we want from "structural equality".

EDIT (2021-05): Also see this more recent analysis.

EDIT (2023-09): Here's an update of the current status. My view changed quite a bit due to how the compiler developed over the last 2 years.

Open problems

There is one problem that I know of so far: the StructuralEq trait docs have this example

#[derive(PartialEq, Eq)]
struct Wrap<X>(X);
fn higher_order(_: &()) { }
const CFN: Wrap<fn(&())> = Wrap(higher_order);
fn main() {
    match CFN {
        CFN => {}
        _ => {}
    }
}

However, function pointers do not have a well-behaved notion of equality (Rust functions are "unnamed" in LLVM terms), and as such they are not suited for a value tree representation. Indeed function pointers should not be used for const generics; I assume there is some safeguard in place that rejects even some "structural equality" values/types for const generics. Moreover higher-order function pointers do not implement PartialEq.

Curiously, floats are allowed in patterns but show a future-compat warning. If floats are problematic even though they have deterministic equality, then for sure we could deprecate matching on function pointers whose equality is non-deterministic and can change when codegen units are partitioned differently!

But leaving that aside, I could imagine handling this by changing (b) to say that if T implements PartialEq, then this property has to hold (so values of types not implementing PartialEq are fine as long as we can put them into a valtree). For (a) I could imagine an "extended valtree" that permits function pointers (represented as a ty::Instance<'tcx>) in its leaves; we would only permit such leaves for "structural equality checking for matches" but strictly disallow them for constant generics.

Cc @oli-obk @lcnr @pnkfelix @varkor @ecstatic-morse