oridb/mc

Codegen bug in pattern match

andrewchambers opened this issue · 3 comments

use std

type tok = union
    `A
    `B
    `C
;;

const main = {

    // Passes
    //var v : int = 0

    // Fails
    var v : byte[:] = [][:]

    match ((v, `A), (v, `B))
    | ((_ ,`C), (_, `B)):
        std.put("fail\n")
    | _:
    ;;  

}
ac@virt:~/Desktop$ mbld -R /tmp/bug.myr 
/tmp/runmyr3757563389...
    6m  /tmp/bug.myr 
    ld  -o /tmp/runmyr3757563389 /usr/local/lib/myr/_myrrt.o /tmp/bug.o -L/usr/local/lib/myr -lstd -lsys 
    /tmp/runmyr3757563389   
fail

reminder from irc:

14:05 < Ori> ok, that test case says to me it's 99% an error with wildcards.
14:06 < Ori> there's weird things we do with slices for wildcarding.
14:06 < Ori> I'm going to bet that it works with any non-slice parameter in there.
14:06 < ac> yeah
14:07 < ac> i will try void
14:07 < ac> yeah
14:08 < Ori> so, basically, to debug that, you start by dumping the decision tree, and tracing what we accept/reject.
14:08 < Ori> the issue with matching slices is that the match thing ends up looking something like:
14:08 < Ori> (in theory)
14:08 < Ori> if (sl.length != pat.length) goto next
14:09 < Ori> if (sl[0] != pat[0] goto next
14:09 < Ori> if (sl[1] != pat[1] goto next
14:09 < Ori> ...
14:09 < Ori> if (sl[n] != pat[n] goto next
14:09 < Ori> accept
14:10 < Ori> now, with wildcards, you basically need to skip the slice and treat any match as an accept.
14:10 < Ori> but you still need to try matching the *other* patterns there

Simpler reproduction.

const main = {

    var v : byte[:] = [][:]

    match (v, 0, v)
    | (_ , 3, _):
        std.put("fail\n")
    | _:
    ;;  

}

The issue can be seen in the decision tree here, both accept states have the same label for some reason.

oridb commented

I believe this has been fixed already.