Precise range exhaustiveness check for match on integer patterns

[pnkfelix]

In theory the compiler should be able to detect that the following range is exhaustive and not error about non-exaustive match:

fn wont_compile(x : u8) { 
    match (x) {
        0x00 ... 0xff => { }
    }
}

Proposed (as a side-portion) in #880

Discussed in rust-lang/rust#12483 and rust-lang/rust#32381

[oli-obk]

The following will then error due to _ being unreachable, but it currently is allowed. So we'd need some way to prevent "new" unreachable patterns from being a hard error.

match x {
    0x00...0xFF => {},
    _ => {},
}

[jonas-schievink]

@oli-obk We could just warn in that case (and make it a lint so people can #[deny] or #[allow] it, depending on what they want)

[igor-krawczuk]

Are there any new discussion/plans on this? Adding a warning which can be turned off for legacy code seems like the most elegant solution to me. If that aligns with the consensus, I'd try and take a shot at this during my spring vacation and send a pull request

[burdges]

It's another issue, and likely unsolvable, but this also fails the range exhaustiveness check:

match x & 0x03 {
    0 .. 3 => ..
}

[glaebhoerl]

@igor-krawczuk Unreachable patterns have already been downgraded from errors to warnings in rust-lang/rust#38069 I believe, so that sounds reasonable to me.

[leonardo-m]

Perhaps it's time to remove the "postponed" tag.

"match x & 0x03 {}" can be solved with a small amount of value range analysis, that will benefit other parts of Rust.

[euclio]

I'd also like to see discussion start on this again. I ran into this today and was very surprised to see that Rust can't determine that all ranges of a given integer type were covered. I had to add a _ => unreachable!() arm instead.

[iamrecursion]

Determining the completeness of a set of guards/pattern matches over a given domain is a fairly non-trivial problem. I ran into it writing my thesis and it requires applications of the Simplex Algorithm to solve what is effectively a linear programming problem.

It's not impossible to solve, but the complexity of doing so needs to be weighed against the possible ergonomic benefits.

[leonardo-m]

Step 1: perform this conservatively, on integral ranges only and only if there are no guards. This is a common case in low-level code. Benefits: avoided a class of bugs, etc.

[euclio]

Yes, this problem in general is very much non-trivial, but the case outlined by @leonardo-m covers my use case and is certainly doable.

[scottmcm]

This could be particularly elegant for char:

match c {
    '\u{0000}'..='\u{D7FF}' => ...
    '\u{E000}'..='\u{10_FFFF}' => ...
    // No wildcard needed; all legal USVs are covered
}

[varkor]

I have an implementation of this (specifically: interval exhaustiveness checking over integer types). If we need to write up an RFC before integrating it, I'll try to do so in a couple of weeks or so (or if anyone'd like to accelerate the process and write one sooner, that'd be great too)!

Edit: Actually, I'm going to try merged it under a feature flag immediately, as it seems like a straightforward extension to the existing exhaustiveness checks, but it may require an RFC to stabilise.

I've created a tracking issue here: rust-lang/rust#50907 and the pull request is at: rust-lang/rust#50912.

[varkor]

This has been implemented in rust-lang/rust#50912 as #![feature(exhaustive_integer_patterns)] (tracking issue). We can probably close this issue now.