Tracking issue: deref patterns
nrc opened this issue · 66 comments
Tracking issue for implementing deref patterns (#[feature(deref_patterns)]).
deref patterns project group repo
lang team initiative issue
About tracking issues
Tracking issues are used to record the overall progress of implementation.
They are also used as hubs connecting to other relevant issues, e.g., bugs or open design questions.
A tracking issue is however not meant for large scale discussion, questions, or bug reports about a feature.
Instead, open a dedicated issue for the specific matter and add the relevant feature gate label.
Steps
- Implement the feature
- String -> &str: string_deref_patterns implementation: Minimal implementation of implicit deref patterns for Strings #98914 (stabilization not started)
- Deref patterns for other std types
- Adjust documentation (see instructions on rustc-dev-guide)
- Write an RFC
- Stabilization PR (see instructions on rustc-dev-guide)
Status
The current implementation uses a placeholder deref!(<pat>) syntax and is limited to types in the standard library. See the design proposal document for more details.
We limit to types in the standard library using the unstable trait DerefPure (#[feature(deref_pure_trait)]). It is not intended to be stabilized at this stage.
- Supported std types:
Box,Rc,Arc,Vec,String,Cow,Pin,ManuallyDrop,Ref,RefMut. - Unstable types that would be eligible :
ThinBox,UniqueRc,LazyCell,LazyLock,
There is also a feature gate just for matching string literals on Strings, under #[feature(string_deref_patterns)].
Unresolved Questions
None at this stage
@roxelo or @matthewjasper would you be able to mentor @chorman0773 on implementing the compiler parts of this please?
@nrc I would not consider myself an expert on the pattern matching code but I can try to help mentor...
I have this code, it does not compile. I am trying to match a Box<str> inside of a pattern, but the error is:
expected str, found `&str`
but there's no good way to match Box<str> in a deeply nested pattern...
#![feature(box_patterns)]
struct Type {
pub name: Box<str>,
pub generics: Option<Vec<Type>>
}
fn main(){
let kind = Type {
name: "User".into(),
generics: Some(Vec::new())
};
match kind {
Type {
name: box "User",
generics
} => {}
_ => unimplemented!()
}
}@chorman0773 anything I can do to help move this forward? I'd really love to see this feature in rust, it would be insanely useful for deep matching of things like ASTs.
Just bonked my head into this again; how can I help?
@rdrpenguin04 and everybody else who cannot wait: I made a proc macro crate, which implements deref patterns in stable Rust: https://crates.io/crates/match_deref
Is anybody involved here able to provide a rough outline or example of what this will look like when stable? I'm imagining this will be something that's automatic for anything that implements Deref
if let Some(u8) = Some(Rc::new(10)) { ... }
if let Some("yellow world") = Some(Box::new(String::from("hello world"))) { ... }edit: according to Mario on Zulip, this would be keywordless, maybe with a & or a * needed - that's not yet decided. Super elegant!
Why can't we make
trait Match {
type Target: ?Sized;
fn do_match(&self) -> &Self::Target;
}
trait MatchMut: Match {
fn do_match_mut(&mut self) -> &mut Self::Target;
}how is it done with Deref and Derefmut, respectively?
The compiler somehow correlates
*x
// and
<&XType as Deref>::deref(&x)why not do the same with match?
match x {}
// and
<XType as Match>::do_match(&x)This would solve how to match strings, SmartPointers, and other more complex constructs without adding new syntax to the language.
@simensgreen the trait isn't really an issue at this point, since Deref/DerefMut already gives the information needed (possibly with the marker trait DerefPure that has been discussed a few places). I think at this point, the goal is to start out supporting only builtin types (&str/String, &T/Vec, &T/Box, Rc, Arc).
And I think the blocker at this point is just time/people. Look at #98914 needed just to support strings, it's a pretty big change
@nrc would you maybe want to update this tracking issue to point to relevant per-type implementations? Probably just:
String->&str:string_deref_patternsimplementation #98914 (stabilization not started)Box<T>->&T:box_deref_patterns(not started)Rc<T>->&T,Arc<T>->&T:rc_deref_patterns(not started)Vec<T>->&[T]:slice_deref_patterns(not started)impl DerefPure<Target = U> -> &U: (further discussion needed)
Assuming the goal is to chunk this huge project up into bits that could be stabilized individually.
@tgross35 The existence of such a trait will help to implement match not only for standard types, including strings, but also for any arbitrary types, like Mutex. Deref does not have enough information to make a match
You wouldn't be able to pattern match directly on a Mutex, and that's a good thing because implicitly locking would lead to some very difficult to follow code. However, you could lock it yourself and then pattern match on the MutexGuard, which does Deref to &T.
Also, to quote zulip
doing it in general faces some thorny issues around speccing what happens when the deref has side effects, since we want to be able to optimize matches in ways that may not preserve how many deref calls are made
This would be the reason for DerefPure that's come up a few times, an (unsafe?) marker trait to specify a special case of Deref that has no side effects (which is already the case for much of the Deref use in std, there's just no way to express that)
This would be the reason for DerefPure that's come up a few times, an (unsafe?) marker trait to specify a special case of Deref that has no side effects (which is already the case for much of the Deref use in std, there's just no way to express that)
How exactly would this interact with our usual safety requirements / UB? Saying "it is UB to impl DerefPure on a non-pure impl Deref" is quite problematic as this would be UB which cannot be checked by a sanitizer such as Miri. Ideally we'd end up in a situation where a wrong DerefPure can lead to surprising behavior, but is not in and of itself UB.
Cc @rust-lang/opsem
I would initially expect it to behave like any other unsafe trait implementation: it gives downstream code permission to rely on the guaranteed properties, but doesn't result in UB until downstream code relies on that property to maintain soundness. Or IOW, library UB.
I think it probably does need to be unsafe, though, because it's not just about collapsing multiple calls into one, but also introducing calls where they wouldn't otherwise exist by strictly inorder trial evaluation of match arms. Since this makes otherwise dead code live, that feels unsafe, but it also can be justified as just safe misbehavior.
"I don't say how many times this gets executed" is a pretty textbook example of library instability which can't be validated operationally, although in this case it's as part of the language rather than library. The only guarantee I think the deref impl gets is that it's evaluated at least once if an arm containing it is
I also think there might be an element of one deref place evaluation being sufficient for both by-ref and by-ref mut binding modes, which while not technically unsafe (it's safe to do &*&mut *it to use DerefMut to get &T) also feels like it should be an unsafe guarantee that both are equivalent and interchangable places modulo provenance.
What sanitizers could do is always execute all structurally reachable pattern derefs from any arms, whether that arm is even reachable or not. Randomized sanitizers could also probabilistically vary how many times the derefs get evaluated, including zero times if unnecessary, and many more times than present in patterns.
Alternatively, the strong position is to go super strict about pattern derefs being not just pure but also just being composed from place computation primitives; in this case such implementations could even be verified statically to be only composed of such operations. Even if this isn't stated required at a language level, validating such composition dynamically ensures actual purity and as such skipping dynamic validation of spurious (non)evaluation.
Then, only partially unrelated, is the question on whether DerefPure's purity promise is utilized anywhere outside of deref patterns. E.g. it could potentially be used to enable borrow splitting, either by caching the place evaluation and/or not invalidating previously split borrows, although the latter means such place evaluation can't use typical reborrowing references.
Properly built-in place evaluation has a number of extra differences to overloadable place evaluation (pattern transparency, borrow splitting, "deref move", purity, const), and it needs to be decided how much or how little of that DerefPure should provide before it can properly be discussed whether that requires it to be unsafe.
"I don't say how many times this gets executed" is a pretty textbook example of library instability which can't be validated operationally, although in this case it's as part of the language rather than library.
The part where it is the language that introduces/removes these calls is what worries me. I don't quite see how we can get away with "library UB" when it's really a language thing.
The alternative, of course, is to treat it like an ellision, rather than UB.
"The behaviour of a match expression that contains a deref pattern is as though either Deref::deref or DerefMut::deref_mut is called for each match arm, except that the implementation is permitted to remove an unspecified number of calls, and if any match arm calls DerefMut, an unspecified number of required calls to Deref may be replaced with corresponding calls to DerefMut."
I think the trait would still need to be unsafe, though, as an improper Deref or DerefMut implementation could introduce UB when removing calls or replacing them, either in the language itself, or in surrounding unsafe code.
Would it make sense to create a DerefPure sealed trait and use it for the implementation of this pattern before adding support for other types? Even if it isn't planned to ever expose it publicly, it seems like it could be easier to implement that then needing the specialized builtin implementation for String/Box/Rc/etc. And give an opportunity to evaluate its soundness & usefulness outside of deref patterns.
I think the trait would still need to be unsafe, though, as an improper
DereforDerefMutimplementation could introduce UB when removing calls or replacing them,
Doing any kind of mutations inside Deref{,Mut} impl (may through *Cell or hidden behind many function calls) may cause potential UB by breaking the exhaustive check. It would be the same as #27282
miri could certainly check that,
That seems not at all obvious to me. Only some very limited notions of "pure" can be checked like that.
For example, a function that memoizes its results via a thread_local HashMap is "pure" for all intents and purposes. But there's no way for Miri to distinguish that from a function that modifies global state in a way that violates purity.
Is it possible or practical for a trait implementer to uphold a safety contract like "no side effects"? It sounds like that would require asserting the purity of the entire call graph of code reachable from the Deref impl, much of which may be outside of the author's control, and little of which would itself be labeled DerefPure.
Sure, but then match evaluation order could still matter.
That's why I propose rules that expressly permit these kinds of transformations, rather than having UB or not based on some notion of purity. Some deref impls aren't going to be inlineable - in those cases, it would be rather unfortunate if every arm had a function call, especially to a trivial function.
Also, none of the allowed transformations would change the evaluation order of the match arms for sure. Only the number of deref calls, and which function is called.
And of course, the transformations aren't necessary for UB
pub struct Foo(Cell<bool>);
impl Deref for Foo{
type Target = bool;
pub fn deref(&self) -> &bool{
const RESOLVED: &[bool;2] = &[false,true];
let val = self.0.get();
self.0.set(!val);
&RESOLVED[val as usize]
}
}
let foo = Foo(Cell::new(false));
match &foo{
true => println!("{}",foo.get()),
false => println!("{}",foo.get()),
}This code has undefined behaviour, even untransformed (incidentally, with maximal optimizations allowed, it doesn't). Thus DerefPure must exist and be unsafe in order to allow exhaustive matching through deref patterns, which is very much desirable.
Here it sounded like you were arguing that we could make "impure DerefPure" be language UB and checked by Miri. That is all I was arguing against. Your last post makes a completely different point. Maybe I just misunderstood your original post.
It was my understanding that one point of DerefPure was that for a match like this
match &foo{
true => println!("{}",foo.get()),
false => println!("{}",foo.get()),
}we do not want to specify in which order these two arms get evaluated. If Deref gets called here, we need to find some other way to uphold this property.
Adding sufficient non-determinism works of course, but is rather unsatisfying (and will still be non-trivial for Miri to implement, if we want it to actually explore a random path and not always the same one).
I was making that point then, yes. I then followed with an alternative. After further discussion, I came to conclusion that the alternative was a better solution. If that wasn't clear, I appologize.
For
match &foo{
true => println!("{}",foo.get()),
false => println!("{}",foo.get()),
}The way we allow the reordering of that is by leveraging the other rules (And also the fact that it has UB in one execution, namely the one that performs no allowed optimizations and does a deref every single pattern). Namely, we know that matching a bool is pure, so only the deref is a problem. But with the rule that states "The number of calls to Deref::deref is unspecified", we can transform it from two calls to deref to one call before the true arm, then reuse the value for both arms. Since the same value is being tested twice in pure, exclusive, patterns, we can reorder the patterns trivially.
As for miri, I'd expect most of the transformations to take place in MIR lowering on rustc anyways, so miri won't see the original match. This would leave it in a similar situation to repr(Rust), where miri cannot check UB caused by misuse of a the layout of a repr(Rust) type. This seems acceptable to me in the short term, and opens up to a similar debug flag as -Z randomize-layout (-Z randomize-deref-matches?) for sufficiently fuzz testing against improper DerefPure impls.
(I agree and maintain that adding a forever-unstable-to-implement unsafe trait DerefPure for just the stdlib-blessed receiver types makes sense short-to-mid-term to supersede box patterns, and even with the described below scheme, to keep around as an optimization for matching through those types, even if the exact requirements1 are difficult-to-impossible to specify for downstream independent of the implementation.)
(I need to learn not to draft long posts in the GitHub UI, I posted this before completion accidentally by pressing CTRL-Enter... sorry for the duplicate ping/email.)
A more aggressive position: guarantee that Deref::deref is called at most one time if any pattern matches up to the point of the deref. This actually does not seem all that problematic; there are three potential complications that I can see.
1. Providing the guarantee for "simple" cases.
("simple" here means the following two cases don't apply.)
As the simple case, this should be fairly simple to handle during THIR -> MIR lowering. (At least I assume this is where it would happen; probably along with the application of default binding modes.) Upon encountering code in the shape of
enum Scrutinee {
VariantA(_),
VariantB(impl Deref<Inner>),
VariantC(_),
}
enum Inner {
VariantX(_),
VariantY(_),
VariantZ(_),
}
match $scrutinee { // &Scrutinee
VariantA(a) => { .. }
VariantB(VariantX(x)) => { .. }
VariantB(VariantY(y)) => { .. }
c => { .. }
}currently this results (for pointer type &) in MIR in the rough shape of
MIR.
For pointer type &: [playground]
let _1: &Scrutinee;
let mut _2: isize;
let mut _3: isize;
let a: &_;
let x: &_;
let y: &_;
let c: &Scrutinee;
let mut _8: &Inner;
let mut _9: &Inner;
let mut _10: &Inner;
// entry
bb0: {
_3 = discriminant((*_1));
switchInt(move _3) -> [0: bb3, 1: bb1, otherwise: bb2];
}
// VariantB(..)
bb1: {
_8 = deref_copy (((*_1) as VariantB).0: &Inner);
_2 = discriminant((*_8));
switchInt(move _2) -> [0: bb4, 1: bb5, otherwise: bb2];
}
// c =>
bb2: {
c = _1;
..
}
// VariantA(a) =>
bb3: {
a = &(((*_1) as VariantA).0: _);
..
}
// VariantB(VariantX(x)) =>
bb4: {
_9 = deref_copy (((*_1) as VariantB).0: &Inner);
x = &(((*_9) as VariantX).0: i32);
..
}
// VariantB(VariantY(y)) =>
bb5: {
_10 = deref_copy (((*_1) as VariantB).0: &Inner);
y = &(((*_10) as VariantY).0: i32);
..
}For pointer type Box (with box patterns), it's much the same, but instead of _8 = deref_copy (((*_1) as VariantB).0: &Inner); (three times) we get _8 = deref_copy (((*_1) as VariantB).0: Box<Inner>); _11 = (((_8.0: Unique<Inner>).0: NonNull<Inner>).0: *const Inner); (three times), applying (essentially) the deref coercion.
I suggest that we can always "desugar" a pattern deref to
at a high-level pseuso-rust
'0: match $scrutinee {
VariantA(a) => { .. }
VariantB(k#placeref _5) => match deref(_5) {
VariantX(x) => { .. }
VariantY(y) => { .. }
_ => continue '0,
}
c => { .. }
}or perhaps
let _6;
'0:
match $scrutinee {
VariantA(a) => { .. }
VariantB(k#placeref _5) => {
_6 = deref(_5);
k#goto '2;
}
_ => k#goto '3;
}
k#goto '4;
'2:
match _6 {
VariantX(x) => { .. }
VariantY(y) => { .. }
_ => k#goto '3;
}
k#goto '4;
'3:
match $scrutinee {
c => { .. }
_ => static_unreachable!(), // "non-behavior"
}
k#goto '4;
'4:or more precisely, to MIR, roughly
MIR.
let _1: &Scrutinee;
let mut _2: isize;
let mut _3: isize;
let a: &_;
let x: &_;
let y: &_;
let c: &Scrutinee;
let mut _8: &Box<Inner>;
let mut _9: &Inner;
// entry
bb0: {
_3 = discriminant((*_1));
switchInt(move _3) -> [0: bb3, 1: bb1, otherwise: bb2];
}
// VariantB(..)
bb1: {
_8 = &(((*_1) as VariantB).0: Box<Inner>);
_9 = <Box<Inner> as Deref>::deref(_8) -> bb6;
}
// c =>
bb2: {
c = _1;
..
}
// VariantA(a) =>
bb3: {
a = &(((*_1) as VariantA).0: _);
..
}
// VariantB(VariantX(x)) =>
bb4: {
x = &(((*_9) as VariantX).0: i32);
..
}
// VariantB(VariantY(y)) =>
bb5: {
y = &(((*_9) as VariantY).0: i32);
..
}
// VariantB(k#deref ..) =>
bb6: {
_2 = discriminant((*_9));
switchInt(move _2) -> [0: bb4, 1: bb5, otherwise: bb2];
}What this is attempting to express is that we should be able to "just" split the patterns which require dereffing through some place as part of the pattern to an inner pattern match, such that the deref only occurs once in the desugared/lowered representation, and ensuring that the deref only happens at most once then is trivial.
This is an adjustment to the currently emitted MIR: the current MIR appears to go through the full requisite pattern destructuring again at each basic block; I'm asking for each level of pattern stripping to be in/before the block which switches on the discriminant, and for that computed temporary to be reused in downstream pattern destructuring.
Other than the two below cases, I believe the only tricky part potentially requiring additional compiler support is what I called k#placeref here, magically being binding-mode-transparent such that the inner match is still semantically operating on the same scruitinee place. Only Box supports by-move bindings after indirection, and point 3 discusses potentially-inconsistent ref and ref mut binding modes. If all patterns use the same binding mode, the k#placeref temporary can use that reference kind without causing any problems. We also need to support some sort of "resume" of the outer match if the inner match falls through; AIUI, this would already be relatively simple to do in CFG form MIR, and is only scuffed to try to express in surface-level structured control flow1.
2. Mixing deref-transparent patterns with not deref-transparent patterns.
This should be "just" making sure that pattern discriminants get tested in the correct order, ensuring that latter arms which want to re-apply the deref remain aware of the created temporary holding the dereffed scrutinee, and asserting that whatever pattern matching is done on the parent place won't invalidate the dereferenced pattern. Given that pattern guards only are allowed to use immutable/shared references to the scrutinee, this holds for Deref patterns but not DerefMut patterns, unless some sort of multi-phase borrow scheme is used such that the use in the intervening arm doesn't invalidate write provenance.
I think it makes plenty sense just to forbid mixing deref patterns and not-deref patterns in the same pattern position. If we don't, we end up where x and y in VariantB(x @ VariantX(_)) and VariantB(y) are allowed but have different types, which is at best an annoying inconvenience, and likely a viable avenue for underhanded code techniques (e.g. shadowing API on the pointer to behave differently).
3. Mixing ref and ref mut binding modes.
This only happens when using explicit binding modes, which is nowadays relatively discouraged in favor of using default binding modes, so I think it relatively reasonable to just forbid mixing different binding modes, especially since the primary way of accomplishing pattern matching through deref will probably be through the use of default binding mode projection.
This isn't about Pattern(ref a, ref mut b); the full pattern binding mode here is ref mut, and a DerefMut is obviously required to be used to match this pattern. This is about VariantA(ref a) | VariantB(ref mut b), where one arm wants to have a Deref and one arm wants to have a DerefMut.
It's imo easier to just say that all bindings through a deref pattern must be in the default binding mode. Then whether Deref or DerefMut is selected is clearly determined by that binding mode, and it only needs to be called the once.
If we want to allow different arms to take a ref or a ref mut borrow from the scrutinee place, then I think the only somewhat reasonable semantic is to say that initial pattern matching is done from a Deref, and then a follow-up DerefMut is done for the matched pattern that wants a ref mut binding. If the DerefMut produces a place that doesn't match the pattern, then either a panic occurs or it's UB, depending on what choices we make about exposing it.
So... do deref patterns need to be opt-in? If not, should they still be anyway?
If a "bad" Deref implementation can cause UB, obviously yes.
However, by implementing Deref<Target=T> for P, the type author is saying that &P should act like &T in most positions; the same goes for DerefMut/&mut P/&mut T. It's for this reason I currently think that ref-binding-mode deref patterns should work for all impl Deref, and ref mut-binding-mode for all impl DerefMut (and that we should require all bindings behind a given deref pattern position in a match to be uniformly ref or ref mut binding mode), with the semantics outlined above that Deref::deref (or DerefMut::deref_mut, if ref mut binding mode is used) is called exactly one time if a deref pattern is "evaluated" (using the same definition for patterns getting evaluated as is used for determining when if guards get evaluated).
...And for that reason, my spitball syntax for explicitly introducing an arbitrary sub-scrutinee expression1 seems quite relevant... and if the uniform-binding-mode rule is taken, the lack of place transparency is then just the same choice of Deref[Mut] present in all other deref coercion desugars.
If we want to allow intervening not-deref-transparent patterns, or mixed ref and ref mut binding mode arms, then I think it makes sense to require an unsafe trait DerefPure. Implementing DerefPure thus relaxes the behavior of a match containing a deref pattern for the type from "exactly one deref or deref_mut call if and only if a pattern requiring it is evaluated" to "between 0 and N+1 deref or deref_mut calls," where N is how many different terminal match arms go through the deref pattern, and makes it library UB for deref[_mut] to panic, or for sequential calls to deref[_mut] to return references with different addresses2 or references to "different objects3" if the impl DerefPure has only been used by-ref4 inbetween the calls. Language UB occurs when within the scope of a match, deref[_mut] of a given place panic, return different addresses2, or return a reference to an object which does not match the pattern fragment which has previously been matched against5. This specification is still too weak for Miri to be a perfect checker for (since by design it's nondeterministic), but balances the various desires I think reasonably well. Hopefully well enough that this alternative can be evaluated without too much bias from the fact I prefer the above no-opt-in UB-free always-single-deref restricted specification which this extends.
Footnotes
-
Proposed for-internal-use safety contract: if a type is
DerefPure: a) if the type isDerefMut,deref_mutexactly does themutversion ofderef, no more and no less; and b)derefonly does some combination of builtin place computation (e.g. field access and pointer/reference dereferences), taking the address/reference of places (i.e.&), and calls to otherDerefPurederef functions, and must not cause a panic (which is still possible under these restrictions via array/slice indexing, which is builtin place computation -- observe via that you can borrow split across it). This is extremely limiting (e.g. it forbids any manual pointer offsetting or even copying from fields), but it covers the implementations of all currentcore::ops::Receivertypes (i.e.&T,&mut T,Box<T>,Pin<impl Receiver>,Arc<T>,Rc<T>)... after we do some inlining, anyway. ↩ ↩2 ↩3 -
This isn't strictly required for nor exploited by the
matching process, but is trivially checked by Miri, of use to 3rd-party code (e.g.StableDeref,ErasablePtr, and various pinning-related properties), and generally understood to be part of the contract of a deref being "pure." ↩ ↩2 -
"Different object" being defined colloquially for the purpose of library UB as the two objects being indistinguishable modulo provenance; all transitively-reachable localized state (state that isn't dependent on contextual/global state) being in the same state it was left in from the last deref. ↩
-
Only being used by-
refalso means that theimpl DerefPurehasn't been moved/relocated either, and itself remains at the same address that the previous deref occurred. This hopefully ensures thatDerefPureisn't seen as implyingStableDerefstyle properties (e.g. that movingBoxdoesn't invalidate derived heap pointers), and allows deref-into-self types likeLazyCellto beDerefPure. ↩ -
Because of the nondeterminism involved in when and how many derefs are allowed to occur, Miri can't be a perfect sanitizer for this requirement (which certainly is still a point against this formulation); this is especially the case since a decent amount of the decision of how many times and when to call
deref[_mut]is already done while lowering to MIR -- most relevantly, MIR lowering probably wants to be written in such a way that the "exactly one deref" property is only broken when required by the composition of pattern arms, and the standard case that doesn't requireDerefPuredoesn't even ask ifDerefPureholds. The primary alternative where Miri catches the most UB is for zero-MIR-opt to always include the repeatedderefon the evaluation of each pattern arm, and the +1deref[_mut]when the matching pattern arm is finalized; this does not achieve the formal maximum number of derefs in all arms, but it does emit the reasonable maximum (before match arm reordering), and an MIR opt pass can coalesce the multiplederefs so long as they're marked asDerefPure-enhanced derefs (required for Miri to do the additional checking). THe secondary alternative for catching more UB is to annotate thematch(and/or deref patterns) with enough additional metadata that Miri knows what the allowed numeric range of deref calls are, and it can use its randomness seed to sometimes call deref more times than emitted to MIR. ↩
@CAD97 to summarize and make sure I'm understanding your point correctly - are you saying that, at least for ref and ref mut, you would adjust match behavior such that we can guarantee that deref does always get called once? With the exception being cases where we explicitely indicate that optimizations can be performed with e.g. DerefPure.
If I'm understanding that right, it sounds like a very reasonable way to come up with a result that "just works", which is always nice for our users. And I think it's in line with what @chorman0773 suggested here #87121 (comment)
@digama0 I'm curious to get your thoughts on this thread, since I believe it was you that originally brought up the optimization point.
I don't think I've seen much objection to making a non-public DerefPure as a way to acheive and eventually stabilize this behavior for a specific set of std types (String, Rc, Arc, Box, Vec, MutexGuard, ...), even if something better would replace the implementation down the line. This seems reasonable to do now since I think this feature is much more in demand for those than for any custom types. Also, official removal of box_syntax yesterday #108471 will leave a bit of a hole in this elegant pattern matching for those who used it.
If that is the case, I'd propose something like the following as a plan going forward:
- Do some top-down design to figure out the exact semantics of what is desired. This may have been discussed somewhere but I haven't seen it written - and I think there are some minor possible differences with how
ref/ref mutwork, howBoxshould move,*vs&vs - Implement the desired functionality via
DerefPure, add it to at least a subset of the types I listed above. IfDerefPureis a lang item then I thinkStringwould no longer need to be one, which would nicely be able to revert a lot of the clippy churn from https://github.com/rust-lang/rust/pull/98914/files - Stabilize this matching behavior. This is the MVP and as long as there are no syntax complaints, there should be no reason to not stabilize the interface even if the implementation isn't finalized
- In tandem or after: determine whether we may ever want to stabilize
DerefPure, or if a proposed implementation would suit the needs better. If something likeDerefPure(or any "allowed to rearrange match") is preferred, resolve semantics of UB and how to verify them with Miri. Or maybe add the suggested-Z randomize-deref-matches - Evaluate matching on
Deref/DerefMutwithoutDerefPure,
BTW, one thing I think that should be allowed to have DerefPure is Lazy or the types produced by lazy_static
Evaluate matching on Deref/DerefMut without DerefPure,
Not having an unsafe trait (or some other form of unsafe) is incompatible with exhaustive matching through Deref. I don't think there's a way to guarantee only one match anyways, so just making it unspecified how many occur makes more sense than trying to narrow down the precise circumstances that would add another deref call.
BTW, one thing I think that should be allowed to have DerefPure is Lazy or the types produced by lazy_static
Good thought - honestly, probably almost all Deref items in std are actually DerefPure, I just called out what I figure are the most likely use cases.
Not having an unsafe trait (or some other form of unsafe) is incompatible with exhaustive matching through Deref. I don't think there's a way to guarantee only one match anyways, so just making it unspecified how many occur makes more sense than trying to narrow down the precise circumstances that would add another deref call.
I thought that @CAD97's comment was suggesting reordering the match and/or storing the deref'd pointer so you only call deref once. So you could match anything Deref and unsafe impl DerefPure would just be an indicator that "single deref call" can be ignored for optimization. Something like:
// As written, this can optimize as it currently does
match x {
A(FooDerefPure(v)) => ...,
B(v) => ...,
// Adding this line will force generating code where this `deref` gets called exactly once
// C(FooDerefNotPure(v)) => ...
}Which would allow for users to match on their own Deref types without needing to worry about the seemingly tricky semantics of DerefPure, and without DerefPure ever needing to be made stable - just with a possible minor performance hit that's probably optimizable on the LLVM side anyway. But I don't speak MIR so maybe I completely missed the mark of that post.
I also thought that's what you were referring to in your comment here #87121 (comment) but I think I just misread that one.
The aforementioned comment only talks about removing Deref calls and replacing them with DerefMut calls. It says nothing about reordering.
The proposed behaviour in that comment is that, given
match &foo{
0 => println!("0")
1 => println!("1"),
2 => println!("2"),
4..= => println!("something else"),
}where foo is a type that Derefs to bool (other than a reference), the program behaves semantically like either:
a) All of the first 4 arms call Deref::deref() before evaluating the value against the scrutinee, or
b) Deref::deref is called before the 0 pattern (since the implementation cannot evaluate that pattern w/o doing so), and before an unspecified number of the following 3 patterns, and which ones is unspecified.
This gives 8 possible exectutions (or lowerings), and up to 4 total calls to Deref::deref. It wouldn't allow (semantically) moving the 4.. pattern up, which is correct, because if you replaced it with, say, i32::MIN.., moving that pattern up above the others would alter the observable behaviour beyond the allowed ellision of Deref::deref calls.
I agree with @CAD97 's proposal for the most part. The only reason we were investigating the possibility of nondeterministically selecting the number of derefs is because the once-per-arm algorithm is obviously bad and we want the permission to improve it (and to argue that this is an "optimization" despite not preserving the number of calls to deref). On the other hand, if the baseline algorithm does derefs by desugaring to a case tree first, then we get much closer to an already optimal algorithm and the pressure to optimize this further is much less.1
The main drawback with the case tree approach is that we still use the per-arm algorithm for the functional specification, like @chorman0773 says. That means that if you put a pattern guard in the middle you can make it impossible to handle with a single case tree:
match (x: Option<Box<bool>>) {
Some(true) => 1,
_ if guard(&x) => 2,
Some(false) => 3,
None => 4,
}Handling this is an epicycle though, and so I am less concerned about how it is resolved. Possible approaches:
- The presence of the guard invalidates the deref temporary, and this is surfaced to the user as a compile error saying that it is not an exhaustive match. (Adding a second
Some(true)branch after case2would be legal and suppress the exhaustive match error.) Boxand similar types are marked asDerefPure, which ensures either that we are allowed to continue using the old deref temporary, or that we can obtain a new deref temporary and are ensured that the result has the same state (at least up to that which will be checked by the match), such that the code is accepted as is. The requirement onDerefPureis a safety invariant, while runtime UB only occurs if we fall out of the match without an arm being selected.
Footnotes
-
There are still reasons the case tree approach might still be suboptimal. For example you might be able to compare
A(Const)by equality to a single constant, rather than first checking for theA(_)arm and then checking that the payload isConst. But I think these kind of situations occur less frequently with deref patterns, unless it's a newtype wrapper. ↩
If you have
match e {
A(Deref(true)) => { .. }
B(x) if x => { .. }
A(Deref(false)) => { .. }
_ => { .. }
}there's no issue caused by the if guard to only having one deref; the if guard only happens in the B case, and the deref only happens in the A case.
If you have
match e {
A(Deref(v)) => { .. }
B(v) => { .. }
C(Deref(v)) => { .. }
_ => { .. }
}there's also no issue, as the A and the C case are disjoint, and only one or the other can happen, never both.
There are two cases where you'd be potentially required to do more than one deref on the same place:
// mixed binding modes
match e { // by value scrutinee
A(Deref(X(ref x))) => { .. }
A(Deref(Y(ref mut y))) => { .. }
_ => { .. }
}because one of the arms wants a Deref binding and the other wants a DerefMut binding.
// mixed deref/not with if guard
match e {
A(Deref(true)) => { .. }
A(v) if test(v) => { .. }
A(Deref(false)) => { .. }
}because the intervening by-ref access would invalidate a previously acquired DerefMut. (A shared ref would be fine, assuming the API was not otherwise unsound, because the shared reference lifetime is still valid.)
My point is that by forbidding these two cases, it becomes quite realistic to guarantee that exactly one deref occurs, by translating the pattern set to effectively a state machine peeling one layer of the pattern at a time.
If supporting these cases which cannot be handled with a single deref is important, then supporting a DerefPure to opt in to nondeterministic derefs is a forwards compatible way to get us there, and we still don't have to say "these operations will cause more derefs;" we just give full permission for more derefs if DerefPure exists, and conservatively ban any pattern groups which can't be done by the simple guaranteed-only-once state machine version if DerefPure isn't implemented.
@chorman0773 if you have a counterexample, I'd like to see it. But my core argument is that restricting deref patterns to the cases where only dereffing exactly once is obviously possible is still a useful version of deref patterns, quite likely sufficient for use in practice, and makes exhaustive matching a nonproblem (as it's just a single reference being matched over after the single deref call). The utility of arms having different overall binding modes is an exotic edge case at best, and it's not a big restriction to prevent a pattern that potentially inspects the whole container from splitting two blocks of deref patterns through that container.
The form where you grab the whole pointer and then do an inner match on it is what people write today. Allowing that inner match to be non-exhaustive and fall through to the outer match's catch-all option(s) (e.g. the spitball "match guard" syntax) is an extension to what's possible today, even if we only added that one functionality without the implicit deref pattern functionality at all.
In short, I'm saying don't desugar/specify
match &foo { // &Deref<u8>
0 => println!("0")
1 => println!("1"),
2 => println!("2"),
3.. => println!("something else"),
}as
let _tmp0 = &foo;
if let 0 = _tmp0 {
println!("0")
} else if let 1 = _tmp0 {
println!("1");
} else if let 2 = _tmp0 {
println!("2");
} else if let 3.. = _tmp0 {
println("something else");
} else {
static_unreachable!();
}but instead as
let _tmp0: &Deref<u8> = &foo;
let _tmp1: &u8 = Deref::deref(_tmp0);
match *_tmp1 { // like a C style switch
0 => println!("0")
1 => println!("1"),
2 => println!("2"),
_ => println!("something else"),
}Whenever the pattern hits a deref pattern, you stop, reify that deref into a single temporary, and then continue matching over that new temporary, emitting an error if there're any fancy patterns that might complicate the pattern evaluation order and make the greedy progress assumption invalid.
Compound constant valtree matches do occur, but treating match evaluation as a case tree rather than trial evaluation doesn't preclude the use of such as an optimization over a case tree specification. And such valtree comparisons by definition can't include a deref pattern, because that's a programmatic indirection that you have to actually inspect (unless inlining says it isn't ofc); pattern-compatible structural equality is on the value behind the indirection, not on the pointer address, even if it's reference-to-static.
If guards do get in the way of a pure case tree semantic desugaring. So they're just trial evaluated when appropriate, and we don't allow that to break apart a case tree arm with an observable deref.
@CAD97 and others
...
unsafe trait DerefPurefor just the stdlib-blessed receiver types makes sense short-to-mid-term to supersede box patterns...
DerefPure and DerefMutPure will not supersede box patterns, because box patterns also allow moving out of box, so, to actually supersede, we need also DerefMovePure
I don't see a reason to separate the various types of Deref types in DerefPure - just in the Deref subtraits that get called. DerefPure would thus subsume DerefMutPure and DerefMovePure.
I also want match to work with Rc<RefCell<_>>. This will allow me to implement Scheme interpreter elegant way:
// Scheme value
enum Value {
Nil,
Cons(Rc<RefCell<Value>>, Rc<RefCell<Value>>),
Symbol(String),
}
fn eval(v: &Value, env: &HashMap<String, Value>) -> Value {
match v {
Cons(Symbol("car"), Cons(a, Nil)) => ...,
...
}
}Lack of easy Rc<RefCell<_>> pattern matching makes Rust in its current form unsuitable for writing interpreters for impure functional languages (such as Scheme). Currently Ocaml is a lot better for such task
@chorman0773 , let's ban match guards if we match through RefCell.
Also, Ocaml has match guards and still works
This proposal wouldn't work for RefCell because RefCell doesn't implement Deref - borrow/borrow_mut needs to be called explicitely.
It's not impossible to make work, but that would be a separate proposal and not part of deref patterns. It would likely be somewhat debated, the team tends to prefer things that may panic to be explicit (requiring a call to borrow(), rather than
maybe panicking in an innocent-looking match if it can't borrow), but maybe there's an acceptable way to do it.
As a side note,
Also, Ocaml has match guards
Yes, but...
and still works.
No.
Mutation during matching + exhaustive matching = segmentation fault, tested in both OCaml 4.14.1 and 5.0.0.
Issue (still open!): ocaml/ocaml#7241
A simpler example: https://counterexamples.org/mutable-matching.html
@oxalica, wow, this is great argument in favor of Rust, as opposed to Ocaml and various other languages (despite Rust's match being not-so-ergonomic at the moment). In seems Rust has simply more manpower to deal with such unsoundness issues. (See also Haskell situation. Haskell people seem to simply gave up on SafeHaskell, because they have no enough resources: https://mail.haskell.org/pipermail/haskell-cafe/2021-April/133854.html )
This might be a stupid comment but...
Why couldn't a syntax like this work?
struct Pin<T> {
pointer: T for deref
}
struct Box<T> {
ptr: *mut T for deref
}Based on writing language parsers and executors, I feel like this might not be a significant change and seems like it could solve most of the deref patterns needed for most container & collection types (eg: Box, String, Arc, Vec, Pin)
That's why I thought a solution like this, where everything can be checked statically, no Deref required, and it should be able to support user-defined cases and cover most of the deref patterns people are asking for.
Compiler would just be following various pointers to get to the underlying T
Something like:
let x: Pin<Box<i32>> = Box::pin(1);
match x {
1 => println!("1"),
_ => println!("Something else)
}This might be a stupid comment but...
No such thing when you're trying to understand something
Why couldn't a syntax like this work?
struct Pin<T> { pointer: T for deref } struct Box<T> { ptr: *mut T for deref }
It's not a question of how to represent the information of "can be dereferenced" - this already exists with Deref, which is already a lang item (meaning the compiler is aware of how it works in the same way it could be aware of syntax) and single pointer ("always safe") dereferencing could be guaranteed using DerefPure (if that even needs to be represented at all - per the above discussion, it seems like that isn't even needed - even better!). Adding new library items as lang items is usually highly preferred over new syntax. (Your suggested syntax also could be confusing for things like Vec<T>-> &[T], which needs to do *something* with multiple struct elements, which can already be trivially expressed as a function but less nicely with syntax
rust/library/alloc/src/vec/mod.rs
Lines 2624 to 2626 in c2ccc85
The current question isn't really how to represent this information: it's moreso how to use existing information in a way that "just works" as expected, but doing so with absolute bare minimum guarantees (so the compiler isn't blocked from doing interesting optimizations down the line)
That seems not at all obvious to me. Only some very limited notions of "pure" can be checked like that.
For example, a function that memoizes its results via a thread_local HashMap is "pure" for all intents and purposes. But there's no way for Miri to distinguish that from a function that modifies global state in a way that violates purity.
Yep, it should be noted that purity checking in full generality reduces to the halting problem
For example, a function that memoizes its results via a
thread_localHashMap is "pure" for all intents and purposes
for all intents and purposes
It is not pure in presence of UNIX signals. If in the middle of updating of HashMap signal arrives and signal handler tries to update this HashMap, too, bad things will happen. Yes, UNIX signals are big footgun, that is why Fuchsia removed them. UNIX signals add another dimension "reentrant - not reentrant" to widely known "thread-safe - not thread-safe"
I don't know if this is fully on topic. But something like deref binding which would work like ref binding would be great
e.g.
match (a_opt, b_opt) {
(None, None) => ...,
(Some(a), None) => ..., // non-dereffed
(None, Some(b)) => ..., // non-dereffed
(Some(deref a), Some(deref b)) => ... // both dereffed
}I feel like allowing the pattern to work through anything but a Cell type makes sense. Box, Rc, Gc, etc.. are heavily used in recursive data structures, and not being able to do nested matching on them has been one of my biggest pain points with Rust.
I don't see much pushback on unsafe trait DerefPure. Is there an issue with adding that before discussing whether matching over mutable fields or move during match is desired?
@smasher164 I think that @CAD97's proposal is definitely worth trying first because it seems much easier to get right than DerefPure. And more flexible, it means that we will also be able to match on user types that implement Deref without any added work.
The comment in this link is extremely long but has a good example halfway down: #87121 (comment). Basically that means go down the match arms, store the result of .deref whenever it is used, and use that same result whenever the same thing is derefed. Fail to compile if that doesn't work for some reason.
We might still want DerefPure to simplify lang items, but that comes with semantics that are much harder to specify.
Are you interested in working on this? It really is just waiting for someone to try it out. We can get you pointed in the right direction if so
@tgross35 I am interested in working on this. Where in the code is this lowering done, and where should I start?
@ThePuzzlemaker awesome! @Nadrieril or @CAD97 would be able to give you more details about where exactly to look, but it will touch a lot of the areas that were relevant in making this work for String #98914 (actually a lot fewer areas than that since we don’t want to do anything type-specific)
You should also drop by Zulip to coordinate efforts and ask any smaller questions, the relevant stream is here: https://rust-lang.zulipchat.com/#narrow/stream/281601-project-deref-patterns.
A reasonable first step is to make any pattern work for a single match for anything that is Deref, I don’t think there is any need to implement multiple matches (as discussed above) as part of the first PR (unless it comes naturally with the implementation).
I've realized that I think this is a little out of my ability at the moment 😅, sorry
I realized that this requires a lot more knowledge of the compiler internals than I have right now and it would take me a looong time to get that knowledge, tbh
Dw, a bunch of us are eager to get this and are slowly making progress
Would this allow for moving out of boxes? Or only getting a reference of the inner value? It's quite common for interpreters to have a recursive type like
enum Expr {
If(Box<Expr>, Box<Expr>, Box<Expr>),
...
}And being able to destructure that by moving out of Box would make code much simpler, eg.
match expr {
If(cond, left, right) => { /* Use owned `Expr` values here */ }
}I think we want to get something like that eventually, but that's not included in this proposal. The difficulty is from a language design pov: what syntax to use, how/whether to generalize that to other types than Box (which draws in the thorny DerefMove situation).
I mean, right now as it stands, Box already has its own DerefMove sugar (specifically, *b), so, I can't imagine it'd be that bad to add custom support for moving out of deref before a fully generic solution exists.
If this does not allow moving out of boxes, we should be careful to be forward-compatible with eventually allowing moving out of boxes.
Work on the feature is restarting. I'd like to remind everyone that
A tracking issue is however not meant for large scale discussion, questions, or bug reports about a feature.
Instead, open a dedicated issue for the specific matter and add the relevant feature gate label.
especially since the design aspects are contentious. Thank you! See you on zulip for discussions.
Dear T-lang, the liaison for this initiative (cramertj) has retired from the lang team. Progress is therefore halted until a new liaison is found. I would like to raise this for the next triage meeting so a liaison can be found, if the team still wants this feature to happen. I will be there to answer questions.
@rustbot labels -I-lang-nominated
We discussed this in the lang triage call today. The consensus was that I would pick up the liaisoning here, so please let me know whenever anything is needed to move this along. Thanks to @Nadrieril for pushing this forward; we'll all excited to see the outcome of that.
#![feature(string_deref_patterns)] doesn't seem to work with rust-analyzer. Any workarounds?
This is still pretty experimental. To make it work, rust-analyzer would have to update their type-checker to recognize these new patterns. It feels premature at this point of the development of the feature.