Stream: t-lang

Topic: Terminology "structural match"


RalfJ (May 13 2020 at 09:00, on Zulip):

I keep being confused by the term "structural match". AFAIK it expresses a property of PartialEq and is very relevant not just to match but also to const generics (because they care about equality of values), so I am rather surprised that the name does not mention equality at all. Is there some deeper connection that I am missing? is this term and its formal definition documented somewhere? (I checked the dev-guide, didn't find it.)
Cc @oli @pnkfelix @lcnr

RalfJ (May 13 2020 at 09:00, on Zulip):

(I am putting this in the t-lang stream because this seems to not just be a rustc implementation detail, but indeed part of the language spec)

RalfJ (May 13 2020 at 09:02, on Zulip):

it's even weirder when someone talks about "implementing strcutural match", like here. that makes it sound like a trait, which maybe it is / should be? but then the text of the issue says "passes the structural match check" which does not sound like a trait at all.

lcnr (May 13 2020 at 09:04, on Zulip):

it's even weirder when someone talks about "implementing strcutural match", like here.

That's my bad :sweat_smile: I tend to think of this in terms of StructuralEq and StructuralPartialEq, which are actual traits.

RalfJ (May 13 2020 at 09:07, on Zulip):

indeed there are traits, and even two of them

/// This implements the traversal over the structure of a given type to try to
/// find instances of ADTs (specifically structs or enums) that do not implement
/// the structural-match traits (`StructuralPartialEq` and `StructuralEq`).
RalfJ (May 13 2020 at 09:07, on Zulip):

the traits are called "structural equality" though, not "structural match"

RalfJ (May 13 2020 at 09:08, on Zulip):

and also, why does this not use the machinery that Send/Sync/Freeze etc use?

RalfJ (May 13 2020 at 09:09, on Zulip):

Unfortunately the docs talk about when the trait is implemented but not about what the trait guarantees. and indeed it is a safe trait so it cannot actually guarantee anything?? now I am even more confused.^^

RalfJ (May 13 2020 at 09:14, on Zulip):

My mental model of StructuralPartialEq trait is that it provides a guarantee about the PartialEq impl. But then (a) it should be unsafe, (b) it should "inherit" from PartialEq, and (c) StructuralEq is useless as I can't think of extra guarantees that it would introduce...

RalfJ (May 13 2020 at 09:15, on Zulip):

what exactly that guarantee is I am not sure and the docs don't say :/ I'll try to read through the tracking issue and associated RFC when I have some time

RalfJ (May 13 2020 at 09:19, on Zulip):

or maybe since the trait is safe there actually isn't a guarantee and this is all basically just a lint?

lcnr (May 13 2020 at 09:30, on Zulip):

Ok, I looked into this a bit more and am still not completely sure my understanding is correct here.

StructuralEq means "I am okay with comparing self using bitwise comparision". The reason that this is not unsafe is that while this may be surprising, it should not be able to cause any UB.

So both StructuralEq and StructuralPartialEq do not guarantee anything, they are more similar to UnwindSafe I guess :thinking:

lcnr (May 13 2020 at 09:35, on Zulip):

and also, why does this not use the machinery that Send/Sync/Freeze etc use?

These traits should be implemented for types implementing PartialEq/Eq only if they use derive. which means that we have to allow some manual (inside of derive) implementations. I currently don't know of a good way to check this inside of the compiler.

varkor (May 13 2020 at 12:54, on Zulip):

structural_match was originally introduced for pattern-matching on constants, hence "structural match". It has since been expanded to also cover equality for const generics, though in the future const generics may use more sophisticated equality testing.

varkor (May 13 2020 at 12:55, on Zulip):

It does not guarantee anything about how objects may be compared: just that they may be compared in certain contexts (pattern matching and const generics). In particular, it does not guarantee we can test for equality through bitwise equality.

varkor (May 13 2020 at 12:56, on Zulip):

structural_match used to be an attribute, but is now implemented using two traits, StructuralPartialEq and StructuralEq: that's why there's some confusion, because the name changed without going via an RFC.

varkor (May 13 2020 at 12:56, on Zulip):

They are not unsafe, as I understand it, simply because they were never intended to be stabilised, though perhaps it would be pertinent to make them unsafe even for internal use.

varkor (May 13 2020 at 12:57, on Zulip):

They're both marker traits.

varkor (May 13 2020 at 12:58, on Zulip):

I don't think their current semantics is actually described in an RFC, as they have evolved organically: @pnkfelix and @eddyb are probably most up-to-date on the precise meaning, but I think even this is still subject to change.

varkor (May 13 2020 at 12:58, on Zulip):

They are auto-implemented for anything that derives PartialEq and Eq, because then the compiler has full control over equality, and so it should be safe to use in pattern matching or const generics.

pnkfelix (May 13 2020 at 13:47, on Zulip):

I don't think we would need to make the traits unsafe. The reason we have this restriction in place is not a safety concern (AFAIK), at least when it comes to its use in match

pnkfelix (May 13 2020 at 13:47, on Zulip):

Its more that we didn't want to commit to a particular choice of semantics (which I think is explained in the RFC). Niko and I have spoken recently about wanting to untie this gordian knot

varkor (May 13 2020 at 14:18, on Zulip):

I think there could be safety concerns with const generics.

pnkfelix (May 13 2020 at 14:19, on Zulip):

yes, I do believe that may be true

pnkfelix (May 13 2020 at 14:19, on Zulip):

or at least ... well I'm not sure

pnkfelix (May 13 2020 at 14:20, on Zulip):

it certainly is scary to start having your type-equivalence relation depend upon user-defined code

lcnr (May 13 2020 at 14:22, on Zulip):

I would expect const generics to always use bitwise(structural) equivalence. So StructuralEq would mostly be an acknowledgement that this is the case.

lcnr (May 13 2020 at 14:23, on Zulip):

Which should prevent most safety concerns here.

pnkfelix (May 13 2020 at 14:24, on Zulip):

yes, but if bitwise equality simply is the right thing, then we could just use it directly

pnkfelix (May 13 2020 at 14:24, on Zulip):

which is an example of one way to untie the gordian knot

varkor (May 13 2020 at 21:08, on Zulip):

Bitwise equality is not the same as structural equality, particularly when it comes to unifying const expressions.

lcnr (May 13 2020 at 21:22, on Zulip):

hmm, looking at the following I don't yet get the difference here.

Structural equality basically says "two things are structurally equal if their fields are structurally equal".

and

Primitive types like u32 are structurally equal if they represent the same value (but see below for discussion about floating point types like f32 and f64).
That is, two values that are semantically unequal could be structurally equal (an example where this might occur is the floating point value NaN).

Can you elaborate the differences between structural and bitwise equality?

varkor (May 13 2020 at 23:17, on Zulip):

I'll admit I was mainly thinking of expressions involving generic parameters, that we could unify without knowing their concrete values. Arguably this is still "structurally matching", albeit in a looser sense of the term, but is more sophisticated than checking directly for bitwise equality.

varkor (May 13 2020 at 23:18, on Zulip):

But I think &str is structural match, but uses equality of strings rather than bitwise pointer equality.

rpjohnst (May 14 2020 at 00:03, on Zulip):

varkor said:

But I think &str is structural match, but uses equality of strings rather than bitwise pointer equality.

This case does involve soundness: https://github.com/rust-lang/const-eval/issues/42

isHavvy (May 14 2020 at 07:42, on Zulip):

Does structural match need to be defined in the reference currently? If so, can somebody give me a definition?

varkor (May 14 2020 at 11:02, on Zulip):

It's not stable and is still undergoing design discussions, so probably better to wait.

RalfJ (May 14 2020 at 18:08, on Zulip):

lcnr said:

StructuralEq means "I am okay with comparing self using bitwise comparision". The reason that this is not unsafe is that while this may be surprising, it should not be able to cause any UB.

that can't be true. the following type is not okay with bitwise comparison due to padding: (u8, u16).

They are not unsafe, as I understand it, simply because they were never intended to be stabilised, though perhaps it would be pertinent to make them unsafe even for internal use.

Safety and stability are orthogonal concerns.. or IOW, if libstd can cause UB without unsafe code that's still a soundess bug.
so if there are any semantic guarantees attached to this trait, it should be made unsafe IMO.

RalfJ (May 14 2020 at 18:09, on Zulip):

so bitwise equality is not what we want. at best we want "bitwise padding-aware equality".

pnkfelix (May 14 2020 at 18:10, on Zulip):

varkor said:

But I think &str is structural match, but uses equality of strings rather than bitwise pointer equality.

("bitwise pointer equality" was not what I meant by "bitwise equality", FWIW)

RalfJ (May 14 2020 at 18:10, on Zulip):

(also see https://github.com/rust-lang/rust/issues/70889 )

RalfJ (May 14 2020 at 18:11, on Zulip):

for const generics we probably want "it's the same as equality of @eddyb's 'value tree'"

RalfJ (May 14 2020 at 18:11, on Zulip):

which indeed is a property that is preserved by derive(PartialEq) so the setup makes sense for that -- except that Eq is entirely irrelevant so there would be no soundness reason to have StructuralEq

Matthew Jasper (May 14 2020 at 18:30, on Zulip):

Eq is relevant for "does not contain floats"

RalfJ (May 16 2020 at 08:57, on Zulip):

@Matthew Jasper floats just shouldn't implement StructuralPartialEq if their equality test doesnt satisfy whatever guarantees we need?

Last update: Jun 05 2020 at 23:20UTC