Skip to content

Wrong reordering of match arms with ranges #18060

Closed
@lifthrasiir

Description

@lifthrasiir
Contributor

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.

Activity

ghost
self-assigned this
on Oct 15, 2014
ghost

ghost commented on Oct 15, 2014

@ghost

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

reem

reem commented on Oct 15, 2014

@reem
Contributor

cc me

edwardw

edwardw commented on Oct 16, 2014

@edwardw
Contributor

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.

ghost

ghost commented on Oct 16, 2014

@ghost

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

edwardw commented on Oct 16, 2014

@edwardw
Contributor

@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?

ghost

ghost commented on Oct 16, 2014

@ghost

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

ghost

ghost commented on Nov 11, 2014

@ghost

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

1 remaining item

remram44

remram44 commented on May 20, 2015

@remram44
Contributor

Still happens :(

niconii

niconii commented on Sep 21, 2016

@niconii
Contributor

This seems to be fixed as of beta?

solson

solson commented on Sep 21, 2016

@solson
Member

Yes, this is already fixed in beta 1.12: https://is.gd/fwGJ30

added
E-needs-testCall for participation: An issue has been fixed and does not reproduce, but no test has been added.
E-easyCall for participation: Easy difficulty. Experience needed to fix: Not much. Good first issue.
on Sep 21, 2016
added a commit that references this issue on Nov 6, 2016

Auto merge of #37616 - jneem:master, r=alexcrichton

2a44315
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    A-codegenArea: Code generationE-easyCall for participation: Easy difficulty. Experience needed to fix: Not much. Good first issue.E-needs-testCall for participation: An issue has been fixed and does not reproduce, but no test has been added.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      Participants

      @solson@steveklabnik@lifthrasiir@remram44@edwardw

      Issue actions

        Wrong reordering of match arms with ranges · Issue #18060 · rust-lang/rust