-
Notifications
You must be signed in to change notification settings - Fork 12.7k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Clarify "structural equality" rules #74446
Comments
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 So if we accept that we can match on 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 |
Indeed. Condition (a) that I listed above is recursive (except for unions), but condition (b) is not as
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?
What exactly is this working around? |
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
If you change the constants to use |
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 |
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 |
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. |
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 |
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 |
The problem with editions is that they don't allow us to simplify the implementation, we'd still not be able to use value trees and we'd have to keep all the logic just to support older editions. So even if language wise we want pattern matching to be the same as const generics, implementation wise they will never be. |
Yeah we'd have to deprecate and actually remove this from all editions if we really want clean code. Or we give up on restricting const pattern matching. But I am not convinced that enough people match on consts of reference type to warrant such drastic steps, so a crater run would still be interesting. |
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 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:
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 |
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:
Not all consts of all types can be treated in this more structured way, so this is where the need of a 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. 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 STRUCT1: Given two values (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 STRUCT2: When a value As above, a type /// 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 This would presumably be part of some derive attribute (like the current 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 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:
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 |
I went through the code, and I think the answer is: if the constant
then we turn the constant into a detailed 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 |
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:
We don't absolutely need the custom_eq MIR qualif for this; we could alternatively just call 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 Const generics are mostly orthogonal, except that they share the ValTree infrastructure, so |
Concretely, here is the alternative that avoids the custom_eq MIR qualif:
This has the downside of being a breaking change for code like this. 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. |
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
andStructuralEq
. 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:
v
has structural equality if (a) it can be converted to a value tree, and (b)PartialEq::eq(v, v2)
returnstrue
if and only if the value tree representation ofv2
equals that ofv
(in particular, ifv2
cannot be represented in a value tree, the return value must befalse
).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 exampleHowever, 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
implementsPartialEq
, then this property has to hold (so values of types not implementingPartialEq
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 aty::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
The text was updated successfully, but these errors were encountered: