Clarify "structural equality" rules

@oli-obk

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

So, one thing I was surpised about but now think is important is that structural equality is not a recursive property. If we used a marker trait, that would mean that [T; 3] is only has structural equality if T has it. But we can destructure such an array trivially, we just can't continue destructuring the T if that doesn't have structural equality. We have to fall back to T::eq to check for equality.

So if we accept that we can match on !StructuralEq types, but keep falling back to runtime equality (so no exhaustiveness or duplication checking, meaning a second CFN pattern in your example would stop linting about unreachable arms), then we keep backwards compatibility to all existing code, but just allow arbitrary matching.

Note that you can work around any of our checks by using a reference in your constant: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=dc3b8eb7eb67cfaa0c0a38c0526a9ed9
Constants of reference type already have this PartialEq behaviour, we can just extend it to everything. This is in conflict with an existing RFC #70743 (comment) but I don't know how we can get the behaviour of the RFC without breaking existing code.

So, one thing I was surpised about but now think is important is that structural equality is not a recursive property.

Indeed. Condition (a) that I listed above is recursive (except for unions), but condition (b) is not as PartialEq could be overwritten to not match value tree equality any more.

If we used a marker trait, that would mean that [T; 3] is only has structural equality if T has it. But we can destructure such an array trivially, we just can't continue destructuring the T if that doesn't have structural equality. We have to fall back to T::eq to check for equality.

I am confused by this and the rest of your post, what do you mean here? It all seems to pertain only to matching and not do const generics?

Note that you can work around any of our checks by using a reference in your constant

What exactly is this working around?

I am confused by this and the rest of your post, what do you mean here? It all seems to pertain only to matching and not do const generics?

Well, either we find rules that apply to both (which my post was assuming), and thus we can't leave out patterns, or we need to find different rules for patterns and const generics. And as far as I can tell, without doing breaking changes we can't just convert constants in patterns to valtrees

What exactly is this working around?

If you change the constants to use Wrap directly instead of &Wrap, you get a hard error

If you change the constants to use Wrap directly instead of &Wrap, you get a hard error

Oh I see. So somehow the "structural equality" test for matching assumes that all references have structural equality? That seems like a rather gaping hole in the match story.^^

You're very welcome to help fix this hole by reviewing #70743 ^^

That seems to be about what actually happens during pattern building though, not about the "structural eq" analysis? What I would have expected is a test there that shows that a constant of type &NonStructuralEqType is no longer accepted as a pattern.

well, that's what's happening now, because we're essentially doing the const to value tree conversion, but the value tree is the pattern data structure. So if we move to actual value trees, we'll have a unified system and the value tree -> pattern conversion will become trivial and infallible. Though there's also the open question of whether it's ok to have NonStructuralEqTypes in patterns and just use the runtime PartialEq::eq function for it, which is something that can't be done for const generics. So we may just need different systems here.

Though there's also the open question of whether it's ok to have NonStructuralEqTypes in patterns and just use the runtime PartialEq::eq function for it

I guess it depends on what you mean by "okay". I think it is "okay" for soundness as long as we ignore those arms for exhaustiveness checking. But we have an RFC with the clear intent of not allowing such matches. OTOH, the implementation of that RFC seems to have gaping holes.

But we have an RFC with the clear intent of not allowing such matches. OTOH, the implementation of that RFC seems to have gaping holes.

Yea, I don't know if we can resolve this and maybe I should write a counter RFC. The breaking changes necessary to do the existing RFC don't feel like breaking changes we can do with our stability guarantees.

We don't really need to resolve this for const generics though, we can just specify the const generics rules separately

It would be reasonable IMO to at least put the soundness-relevant parts of pattern matching, and const generics, on common footing (like the notion of "structural equality" I proposed above). Pattern matching can have an "escape hatch", with nodes in the value/pattern tree that just hold opaque consts and that are ignored by exhaustiveness checking. The main issue I see here is that we want value trees without such opaque consts for const generics, but we also want to construct the pattern match tree from the value tree -- and those constraints are mutually exclusive, as far as I can see.

Another thing: one could argue that for const generics, it hardly matters what PartialEq::eq does. But it seems like that notion of equality differing from the one used by the type system could be rather confusing.

The breaking changes necessary to do the existing RFC don't feel like breaking changes we can do with our stability guarantees.

We can always do a crater run, estimate the breakage and then emit deprecation warnings until the next edition if necessary.

The breaking changes necessary to do the existing RFC don't feel like breaking changes we can do with our stability guarantees.

We can always do a crater run, estimate the breakage and then emit deprecation warnings until the next edition if necessary.

Basically, that would be an extension of the existing future compat lint for matching on floats. It would also cover matching on function pointers, raw pointers, and &T where T does not allow matching.

@rpjohnst

If we decide that we cannot or do not want to entirely forbid patterns that cannot be represented as a value tree, we need a form of "fallback" leaf for the value tree that points to CTFE memory (i.e., something like the current ConstValue::ByRef).

In that case, we have to ensure that value trees participating in const generics do not contain such a node. I could imagine two schemes:

Something type-based, where we have a ty::Const<FallbackNodeType> and use ty::Const<!> for const generics. This may induce some overhead due to having to convert between the different kind of value trees.
Something with run-time checks, where we have a assert_no_fallback method on ty::Const that we call on every const used in a type. We better make sure we do not forget to do this call...

Either way, we'll end up with some perf and complexity hit, so IMO it is worth the experiment to see how widely such patterns are even used. After all, at least for floats this was considered worthwhile; they are future-incompat since forever; maybe we can get away with the same for raw and function pointers.

Cc @rpjohnst who mentioned in rust-lang/const-eval#11 that they use raw pointers in patterns.

I've come around to trying to do the breaking change that would allow us to move to value trees. I've done some experiments yesterday and it's not so easy, because the reason we are in today's mess is that I avoided some ICEs by doing the problematic destructurings. I've never been able to figure out these ICEs because they are in the middle of our exhaustiveness checks, whose paper I've never read and whose implementation I've never understood.

All the raw pointers I (plan to) use in patterns are static addresses. I would expect those to be supportable as ty::Const leaf nodes, even in types, at some point in the future- does that seem plausible? They should be able to function as opaque/abstract names, much like types themselves, since address stability is the raison d'etre of static.

Hm... that argument only works for non-ZST statics, and I feel like actually supporting this is a long way off.

But indeed, if I interpret this code correctly then it is indeed a pointer to a (non-ZST) static (and not a pointer to some memory that was created for the initial value of a static).

I wrote down a summary and my latest thoughts on this here on Zulip:

My personal thinking (which is some variant of the links I posted above) is roughly as follows:
In general, the value of a constant (const/static body, but also more general any Constant MIR operand, which includes all literals) inside rustc is just an unstructured blob of bytes (and Allocation, in technical terms). This is sufficient for when a const is just used in code. (There's a slight inaccuracy here in that, for efficiency reasons, we do not actually create an Allocation for each integer literal, so we have more efficient representations for some very simple constants. This is not relevant for the StructuralEq discussion.)
However, there are 2 things the compiler does where an "unstructured blob" view of a constant is insufficient:

pattern matching against a const, if we want exhaustiveness checking to properly take the const into account (i.e., "as-if" the const would have been written inline as a normal pattern). Note that if we don't do exhaustiveness checking then we can still treat the const as a blob; this is sound if exhaustiveness checking considers such a match arm to not match anything, thus enforcing the addition of a fallback _ arm. In this case the match can be implemented by calling PartialEq.
const generics. In particular here we need a notion of equality on consts that acts more like PartialEq than memcmp, i.e., comparing references by comparing their pointees and skipping padding bytes.

Not all consts of all types can be treated in this more structured way, so this is where the need of a StructuralEq constraint arises.

To support these usecases, the compiler will use "valtrees", a high-level, more structural representation of a constant. A valtree is a tree where the leaves carry integer values and both pointer indirection and "is a field of" are represented as edges between nodes.
So e.g. 2 would be a valtree with just a single node carrying a 2; (2, 2) would be a valtree where the root points to two leaf nodes that carry a 2. &2 would be a valtree where the root points to a leaf node that carries a 2. (2,) would be the same valtree as &2; that's okay -- valtrees are meant to capture everything about a value that matters at a high level; comparing valtrees of different types is not very meaningful.

Pattern matching exhaustiveness checking can use valtrees to basically convert a constant into a regular pattern and then treat it as-if that pattern had been written literally. Const generics can compare two valtrees (where inner nodes are compared by recursively comparing the children) to determine equality of const values.

Now, which values are safe to be converted into valtees? I think this is the class of values that we want to say has "structural equality", and then we can say that T: StructuralEq if all values of T have "structural equality". (Note that e.g. the value None::<T> has structural equality for all T, that's why it makes sense to distinguish value-level and type-level notions here. I am not suggesting we actually do anything like this in rustc, but I think it is good to develop the theory in this style. And if we want to allow non-NAN floats in const generics, we do have to take this approach.)
There are some values which we simply cannot turn into valtrees, so they are out, most notably all values of union type (because a union is just a bag of bytes, there's no high-level representation we can turn that into). But we also quickly realize that there is a deep link with equality here: the behavior of pattern matching against a constant should ideally be equivalent to testing equality with PartialEq. And likewise for const generics, when two constants are equal according to PartialEq, we better treat them as "equal" from the perspective of the type system. This guides us to the following key constraint that I think must be satisifed to ensure things make sense:

STRUCT1: Given two values v1, v2 of type T: PartialEq, if both can be converted to a valtree then the valtrees are equal if and only if v1 == v2. Moreover, if v1 can be converted to a valtree and v2 cannot, then !(v1 == v2).

(Remember that "can be converted to a valtree" is equivalent to "has structural equality".)

This is the basic minimum. I feel like we might want to strengthen this to make it easier to reason about; making definitions conditional on whether a type implements a trait is tricky business (if we aren't careful, adding a PartialEq impl can now break this property! We saw with Pin how easily this goes wrong). Also PartialEq allows some "whacky" non-reflexive equality relations which don't make these things easier to think about. So I think we want a property more like:

STRUCT2: When a value v1 of type T can be converted to a valtree, then T: Eq and for any v2: T, their valtrees are equal if and only if v1 == v2 (in particular if v2 cannot be converted into a valtree, then !(v1 == v2)).

As above, a type T is StrucuralEq if all its values can be converted to a valtree. This lends itself toward saying that the trait should be declared as

/// SAFETY constraint: all values of this type must be convertible to valtrees such
/// that the valtrees are equal if and only if the values compare equal with `Eq::eq`.
unsafe trait StructuralEq: Eq {}

So, not really sure where is best to mention this, but figured I'd mention this here. I have two mostly disjoint things, so, I'll separate them out.

First, it would be useful to support more forms of structural equality than the existing kind, specifically the kind that ignores certain fields. Equivalence classes like this are completely valid conceptually, and one is even used on the documentation for Eq:

enum BookFormat { Paperback, Hardback, Ebook }
struct Book {
    isbn: i32,
    format: BookFormat,
}
impl PartialEq for Book {
    fn eq(&self, other: &Self) -> bool {
        self.isbn == other.isbn
    }
}
impl Eq for Book {}

I don't think there'd be any specific issues with allowing constants of type Book to be used in match statements, and it would simply allow all books with the same ISBN, regardless of their format. I don't think it'd be that difficult to implement, either, but I also haven't touched any of the code for structural equality.

This would presumably be part of some derive attribute (like the current #[default] that recently got stabilised), where something like #[compare(ignore)] could be marked on individual fields of a type that derives Eq or PartialEq. I use #[compare] here because it would presumably also apply to PartialOrd, Ord, and Hash implementations, but those aren't necessary for structural equality, at least for now.

The second part actually applies to what I just mentioned… could there be the potential for structural ordering as well? It would be truly fantastic if code like this could eventually work:

#[derive(PartialEq, Eq, PartialOrd, Ord)]
enum Month { Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec }
use self::Month::*;

fn quarter(val: Month) -> u8 {
    match val {
        Jan..=Mar => 1,
        Apr..=Jun => 2,
        Jul..=Aug => 3,
        Sep..=Dec => 4,
    }
}

This bit is obviously a lot harder and I don't expect it any time soon, but it would be nice if the current way structural equality were defined would be compatible with an extension like this in the future.

The first point, I think, pretty much means the compiler has to make no assumptions about how comparing values of that type actually works, has to always require a fallback case since exhaustiveness checking is impossible, and compiles the match to an if else chain of equality tests. That is certainly possible; this is what we can / have to apply when we do do not have structural equality.

The second point requires expanding how ranges are handled in patterns; I think it is mostly out-of-scope for this issue but an interesting extension to consider when we got the basics sorted out.

I think clarifying the rules here is blocked on us first even having coherent rules -- currently it's a fallback logic that is hard to reason about. So this is kind of blocked on #62411 I think; also see my recent question there.

After reading through #62411 and seeing changes like #67343, I wonder if I've been thinking about this all wrong. Maybe "structural equality" really is just a lint. But then we should make it one. Maybe the rules should just be:

You can use any const that implements PartialEq as a pattern. The semantics is always that of PartialEq.
We have a warn/deny-by-default lint for cases where the pattern behavior disagrees with what would happen if you inline the constant value as a pattern (i.e., the type/value does not have structural ==, recursively all the way down). This is, I think, exactly what the custom_eq MIR qualif finds.

Then the entire StructuralEq trait becomes merely a lint and it's completely okay for it to be safe.

There is a separate question of how exactly exhaustiveness checking works. That I am much less sure about. Right now, how exactly do we decide whether we want to "look into" a constant for exhaustiveness checking? At that point we better be sure that its PartialEq is structural, this becomes a soundness question! (At least if we want to say that match always behaves like PartialEq, which I think we do.)

And then there's const generics, which is what triggered this entire thread to begin with. But for that we now have ConstParamTy, and that's a recursive property. It is a safe trait, which IMO makes little sense, but it's now decoupled from StructuralEq. (Well they still interact, it requires StructuralEq as well.)

Right now, how exactly do we decide whether we want to "look into" a constant for exhaustiveness checking?

I went through the code, and I think the answer is: if the constant

can be converted into a valtree
- this means it recursively consists only of FnDef, bool, char, int, float, ref, str, slice, array, enum, struct, tuple
and in the concrete value that was produced, all ADTs that we encounter have their PartialEq derived

then we turn the constant into a detailed Pat that is used for exhaustiveness checking.

So the presence of the Structural(Partial)Eq trait does impact whether we look inot a constant for exhaustiveness checking or not. That can't be unsound per se since impl StructuralPartialEq for T will then also mean we actually don't call the PartialEq for matching, we deconstruct the value directly. But that feels like exposing an implementation detail to me; I'd rather be able to say that we always use PartialEq semantics -- but then the trait needs to be unsafe.

After digging a bit more through our pattern matching code, I think here's the end state I'd like us to achieve for pattern matching on consts:

All consts being matched on must be of a type that implements PartialEq. The semantics we guarantee is that matching behaves like ==. (This is currently actually not the case, see lint towards rejecting consts in patterns that do not implement PartialEq #115893.)
Valtree construction enforces some new invariants: valtrees can only be constructed for PartialEq types, and if valtree construction succeeds then valtree equality matches ==.
- This is enforced with the help of unsafe trait StructuralPartialEq : PartialEq {}, a trait that guarantees that PartialEq on this type behaves the same as comparing all fields structurally. (This is a shallow property, it relates == on the fields with == on the type.) derive(PartialEq) automatically implement this trait; we could in principle eventually allow users to implement it as well. When valtree construction hits an ADT type, it checks whether that the type implements StructuralPartialEq, and fails if that is not the case.
When a const is matched on, we run the custom_eq MIR qualif. If that says that there is no custom eq, then we can construct a valtree and that shouldn't fail -- the properties required for valtree construction are enforced by the custom_eq check. We then treat this as a transparent constant for pattern matching, i.e. its value is used for exhaustiveness checking. (This also means executing the match test at runtime will actually directly compare enum variants and fields, but the valtree invariant ensures us that this is equivalent to using ==.)
If the custom_eq MIR qualif says there might be a custom eq, then we treat this as an opaque constant (and use == to execute the match test at runtime). For some of these cases we might have warn-by-default lints informing the user that their == is a bit odd and doesn't match what one might expect for match semantics.

We don't absolutely need the custom_eq MIR qualif for this; we could alternatively just call search_for_structural_match_violation to determine whether we treat the constant transparently or opaquely. That would mean we honor constants for exhaustiveness checking only if their type is recursively StructuralPartialEq. That's the semantics I would have expected, but given that we have this MIR qualif implemented now, I guess we can make use of it to get better exhaustiveness checking? Not sure if it's worth it, I'm fine either way.

Compared to today, this is a breaking change for some obscure corner cases that #115893 is intended to lint against. We can also get rid of the StructuralEq trait. We will accept a lot more constants in pattern-matching -- everything that implements PartialEq. The subtle rules around structural-match only affect whether the value of a constant can be used for exhaustiveness checking, not whether the constant can be used in a match at all.

Const generics are mostly orthogonal, except that they share the ValTree infrastructure, so ConstParamTy has to ensure that the type is valtree-constructible with the invariants given above. I think that's a property we want anyway, that const generics only work for types whose == matches ValTree == (and in particular, only for types that have ==).

We don't absolutely need the custom_eq MIR qualif for this

Concretely, here is the alternative that avoids the custom_eq MIR qualif:

We change the meaning of StructuralPartialEq (still unsafe, still has PartialEq as supertrait) to be "all values of this type can be turned into a valtree, and its == agrees with valtree ==. (Actually then we can have Eq as supertrait I think.) This is a deep recursive property. Valtree construction just checks this trait once before traversing the value.
When a const is matched on, we check that trait. If it is implemented for the type, we use valtrees and treat the const transparently.
If it is not implemented, we treat the const opaquely.

This has the downside of being a breaking change for code like this. MyEnum is not recursively StructuralPartialEq, so it would be treated opaquely, so the compiler would consider V1(0) as not being covered by a match arm.

This has the upside of likely getting us back the perf that was lost here.

With rust-lang/rfcs#3535 being accepted, this is largely resolved. The remaining work is tracked at #120362.

Navigation Menu

Repository navigation

Clarify "structural equality" rules #74446

Open problems

2 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Clarify "structural equality" rules #74446

Description

Open problems

Activity

oli-obk commented on Jul 22, 2020

RalfJung commented on Jul 24, 2020

oli-obk commented on Jul 24, 2020

RalfJung commented on Jul 24, 2020

oli-obk commented on Jul 24, 2020

RalfJung commented on Jul 24, 2020

oli-obk commented on Jul 24, 2020

RalfJung commented on Jul 24, 2020

oli-obk commented on Jul 24, 2020

oli-obk commented on Jul 24, 2020

RalfJung commented on Jul 24, 2020

petrochenkov commented on Jul 24, 2020

RalfJung commented on Jul 24, 2020

2 remaining items

RalfJung commented on Jul 28, 2020

oli-obk commented on Jul 28, 2020

rpjohnst commented on Jul 28, 2020

RalfJung commented on Jul 28, 2020

RalfJung commented on May 15, 2021

clarfonthey commented on May 26, 2022

RalfJung commented on May 28, 2022

RalfJung commented on Sep 15, 2023

RalfJung commented on Sep 15, 2023

RalfJung commented on Sep 15, 2023

RalfJung commented on Sep 16, 2023

RalfJung commented on Sep 17, 2023

RalfJung commented on Apr 15, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions