Repository navigation
Pattern reachability algorithm fails in the presence of uninhabited types #12609
Description
From check_match.rs:
// Algorithm from http://moscova.inria.fr/~maranget/papers/warn/index.html
//
// Whether a vector `v` of patterns is 'useful' in relation to a set of such
// vectors `m` is defined as there being a set of inputs that will match `v`
// but not any of the sets in `m`.
//
// This is used both for reachability checking (if a pattern isn't useful in
// relation to preceding patterns, it is not reachable) and exhaustiveness
// checking (if a wildcard pattern is useful in relation to a matrix, the
// matrix isn't exhaustive).
// Note: is_useful doesn't work on empty types, as the paper notes.
// So it assumes that v is non-empty.
This results in, most prominently (#4499), a match on an empty enum with a wildcard pattern being accepted:
enum X { }
fn x() -> X { unimplemented!() }
match x() {
_ => println!("hi")
}
while if you add a variant to the enum and a corresponding arm to the match:
enum X { X }
fn x() -> X { unimplemented!() }
match x() {
X => println!("hello"),
_ => println!("hi")
}
rustc rejects the program with error: unreachable pattern.
Clearly a trailing wildcard pattern after you've already matched all possible values in preceding arms should always be considered unreachable, and this is true even when the number of potential values, and hence preceding arms, are both zero.
As the comment notes the algorithm we use relies on "no empty types" as an assumption, so this may not be an easy bug, but it's still a bug.
Reacted by Colin Kiegel
Activity
glaebhoerl commentedon Jun 28, 2014
cc @brson @nikomatsakis @pcwalton (not really sure who I should be cc-ing): I think this is a backwards compatibility issue in the respect that fixing this bug will cause fewer programs to be accepted. We should make it clear that pattern matching uninhabited types with wildcard patterns is not legal according to the language spec, that it being currently accepted is a compiler bug, and that we reserve the right to fix the bug in the future (if/when we figure out how to).
See examples above if the rationale isn't clear.
glaebhoerl commentedon Jul 1, 2014
Yes, this is implied by the term "uninhabited type". (Or do you mean that there's a definition of an "empty type" in some official spec that needs updating?)
nikomatsakis commentedon Jul 3, 2014
I agree with @glaebhoerl, though this is clearly a corner case. I wonder if we should remove disallow uninhabited enums and make our lives easier?
pnkfelix commentedon Jul 3, 2014
/me cannot help but point at #4499 (comment) (though arguably feature-gating is quite different from outright removal...)
pnkfelix commentedon Jul 3, 2014
Nominating, P-backcompat-lang. See #12609 (comment) for the basis.
pnkfelix commentedon Jul 3, 2014
Assigning P-backcompat-lang, 1.0 milestone.
(There are many interesting ways to resolve this, and some not-so-interesting ways.)
sfackler commentedon Jul 3, 2014
Uninhabited enums are useful as phantom type parameters.
pcwalton commentedon Jul 4, 2014
OCaml has the same behavior as Rust today:
pcwalton commentedon Jul 4, 2014
SML/NJ ICE's:
brson commentedon Jul 4, 2014
@pcwalton that's hilarious
38 remaining items
canndrew commentedon Sep 14, 2016
I've had a crack at implementing this here: #36476
It seems to work but definitely needs review from someone who actually understands the code I hacked on.
Also, the change I've implemented allows people to omit patterns that are unreachable due to uninhabited types but doesn't force them to. This is important for backwards-compatibility but also because I think code like this:
should be allowed to compile even when
E(orT) is uninhabited. This might be important for someone who's (eg.) generating code with a macro.Check for uninhabited types in sub-patterns (rust-lang#12609)
Auto merge of #38047 - canndrew:fmt-void-non-empty, r=bluss
glaebhoerl commentedon Jan 6, 2017
So should this be closed, or do we wait for it to hit stable?
nikomatsakis commentedon Jan 7, 2017
We can close.
Auto merge of rust-lang#12609 - Alexendoo:arc-with-non-send-sync-mess…