Wrong reordering of match arms with ranges

[lifthrasiir]

Adopted and minimized from the HTTP method parsing routine of hyperium/hyper:

println!("{}", match (1u, 3u) { (0, 2...5) => 1, (1, 3) => 2, (_, 2...5) => 3, (_, _) => 4u });
println!("{}", match (1u, 3u) {                  (1, 3) => 2, (_, 2...5) => 3, (_, _) => 4u });
println!("{}", match (1u, 7u) { (0, 2...5) => 1, (1, 7) => 2, (_, 2...5) => 3, (_, _) => 4u });

All three lines should print 2, but the first line prints 3 on the current nightly (rustc 0.13.0-nightly (40b244973 2014-10-14 23:22:20 +0000)). The match trans apparantly groupped the second pattern even when it may result in the wrong result.

Broken in 0.11 and 0.12. Fine in 0.10 so I blame one of my refactors.

[reem]

cc me

[edwardw]

This is troublesome. As being mentioned in #13027 (comment), Marijn's article outlines how the pattern matching is compiled into a decision tree. In the test case illustrated here, the tree ends up like this:

                                  (0, 2...5) => 1
(0, 2...5) => 1                   (_, 2...5) => 3
(1, 3) => 2      pick column 1    (_, _) => 4u
(_, 2...5) => 3  ==============> and
(_, _) => 4u                      (1, 3) => 2
                                  (_, _) => 4u

So the match arms are not really reordered but rather grouped together. But never the less, the result here is simply wrong. Some fundamental assumptions of the algorithm could be wrong.

There's also a minor issue. The following code:

println!("{}", match (1u, 3u) { (0, 2...5) => 1, (1, 3) => 2, (_, 3) => 3, (_, _) => 4u });

gives the wrong answer 4. It has to do with what counts as a default wildcard arm as trans/_match.rs sees it. Right now only _ => foo is but a tuple pattern with all wildcard elements should be, too.

The bug is that we consider the range 2..5 to be a "constructor" of the integer type being matched which is wrong (constructors must be disjoint much like variants of an enum). The right thing is to treat it as x if x >= 2 && x <= 5. Should be very easy to fix.

Not sure about the wild pattern but I do remember being surprised seeing that we'd only check for PatWild.

[edwardw]

@jakub-, your assessment is more accurate. I have a fix for the minor issue I described. Not really worthy of a separated PR, so should I leave that to you too?

@edwardw Thanks! Yes, I'm on it. :-)

An update: I haven't forgotten about this, will look this week.