search

ponylang / ponyc

Pony is an open-source, actor-model, capabilities-secure, high performance programming language
http://www.ponylang.io
BSD 2-Clause "Simplified" License
5.71k stars 415 forks source link

Compiler Crash with Generics and Types #3930

Open redvers opened 2 years ago

redvers commented 2 years ago

Minimal case:

  fun flatten[A: Array[Array[A]] #read](arrayin: Array[Array[A]]): Array[A] =>
    let rv: Array[A] = Array[A]
    for f in arrayin.values() do
      for g in f.values() do
        rv.push(g)
      end
    end
    rv

lldb gives:

[nix-shell:~/projects/ponyc]$ lldb ./build/debug/ponyc
(lldb) target create "./build/debug/ponyc"
Current executable set to '/home/red/projects/ponyc/build/debug/ponyc' (x86_64).
(lldb) run
Process 1137358 launched: '/home/red/projects/ponyc/build/debug/ponyc' (x86_64)
Building builtin -> /home/red/projects/ponyc/packages/builtin
Building . -> /home/red/projects/ponyc
Building collections -> /home/red/projects/ponyc/packages/collections
Building ponytest -> /home/red/projects/ponyc/packages/ponytest
Building time -> /home/red/projects/ponyc/packages/time
Building random -> /home/red/projects/ponyc/packages/random
Process 1137358 stopped
* thread #1, name = 'ponyc', stop reason = signal SIGSEGV: invalid address (fault address: 0x7fffff7feff0)
    frame #0: 0x000000000082121b ponyc`pool_get at pool.c:732:15
   729    pool_central_t* top;
   730    PONY_ABA_PROTECTED_PTR(pool_central_t) cmp;
   731    PONY_ABA_PROTECTED_PTR(pool_central_t) xchg;
-> 732    cmp.object = global->central.object;
   733    cmp.counter = global->central.counter;
   734    pool_central_t* next;
   735
(lldb) bt

**Lots of scroll**

    frame #136099: 0x00000000007d36b7 ponyc`is_x_sub_x at subtype.c:74:7
    frame #136100: 0x00000000007d3629 ponyc`is_x_sub_x at subtype.c:87
    frame #136101: 0x00000000007d3629 ponyc`is_x_sub_x at subtype.c:1120
    frame #136102: 0x00000000007d3629 ponyc`is_x_sub_x at subtype.c:1289
    frame #136103: 0x00000000007d3629 ponyc`is_x_sub_x(sub=<unavailable>, super=<unavailable>, check_cap=<unavailable>, errorf=0x0000000000000000, opt=0x00007fffffff5dd0) at subtype.c:1677
    frame #136104: 0x00000000007d3f1c ponyc`is_eqtype(a=0x00007ffff5aa7fc0, b=0x00007ffff5aab440, errorf=0x0000000000000000, opt=0x00007fffffff5dd0) at subtype.c:1723:1
    frame #136105: 0x00000000007d4031 ponyc`is_eq_typeargs(a=0x00007ffff5aa7cc0, b=0x00007ffff5aa8e80, errorf=0x0000000000000000, opt=0x00007fffffff5dd0) at subtype.c:202:5
    frame #136106: 0x00000000007d4240 ponyc`exact_nominal(a=0x00007ffff5aa7cc0, b=0x00007ffff5aa8e80, opt=0x00007fffffff5dd0) at subtype.c:60:1
    frame #136107: 0x00000000007d36b7 ponyc`is_x_sub_x at subtype.c:74:7
    frame #136108: 0x00000000007d3629 ponyc`is_x_sub_x at subtype.c:87
    frame #136109: 0x00000000007d3629 ponyc`is_x_sub_x at subtype.c:1120
    frame #136110: 0x00000000007d3629 ponyc`is_x_sub_x at subtype.c:1289
    frame #136111: 0x00000000007d3629 ponyc`is_x_sub_x(sub=<unavailable>, super=<unavailable>, check_cap=<unavailable>, errorf=0x0000000000000000, opt=0x00007fffffff5dd0) at subtype.c:1677
    frame #136112: 0x00000000007d3246 ponyc`is_x_sub_x at subtype.c:1473:3
    frame #136113: 0x00000000007d3210 ponyc`is_x_sub_x(sub=<unavailable>, super=<unavailable>, check_cap=<unavailable>, errorf=0x0000000000000000, opt=0x00007fffffff5dd0) at subtype.c:1680
    frame #136114: 0x00000000007d3f1c ponyc`is_eqtype(a=0x00007ffff5aab040, b=0x00007ffff5aab440, errorf=0x0000000000000000, opt=0x00007fffffff5dd0) at subtype.c:1723:1
    frame #136115: 0x00000000007d4031 ponyc`is_eq_typeargs(a=0x00007ffff5aab2c0, b=0x00007ffff5aa8e80, errorf=0x0000000000000000, opt=0x00007fffffff5dd0) at subtype.c:202:5
    frame #136116: 0x00000000007d4240 ponyc`exact_nominal(a=0x00007ffff5aab2c0, b=0x00007ffff5aa8e80, opt=0x00007fffffff5dd0) at subtype.c:60:1
    frame #136117: 0x00000000007d36b7 ponyc`is_x_sub_x at subtype.c:74:7
    frame #136118: 0x00000000007d3629 ponyc`is_x_sub_x at subtype.c:87
    frame #136119: 0x00000000007d3629 ponyc`is_x_sub_x at subtype.c:1120
    frame #136120: 0x00000000007d3629 ponyc`is_x_sub_x at subtype.c:1289
    frame #136121: 0x00000000007d3629 ponyc`is_x_sub_x(sub=<unavailable>, super=<unavailable>, check_cap=<unavailable>, errorf=0x00007fffffff54e0, opt=0x00007fffffff5dd0) at subtype.c:1677
    frame #136122: 0x00000000007d3f1c ponyc`is_eqtype(a=0x00007ffff5aab2c0, b=0x00007ffff5aa8880, errorf=0x00007fffffff54e0, opt=0x00007fffffff5dd0) at subtype.c:1723:1
    frame #136123: 0x00000000007d4031 ponyc`is_eq_typeargs(a=0x00007ffff5aaa100, b=0x00007ffff5aa8f00, errorf=0x00007fffffff54e0, opt=0x00007fffffff5dd0) at subtype.c:202:5
    frame #136124: 0x00000000007d3e6b ponyc`is_x_sub_x at subtype.c:823:3
    frame #136125: 0x00000000007d3e5a ponyc`is_x_sub_x at subtype.c:1133
    frame #136126: 0x00000000007d3e15 ponyc`is_x_sub_x at subtype.c:1289
    frame #136127: 0x00000000007d3e15 ponyc`is_x_sub_x(sub=<unavailable>, super=<unavailable>, check_cap=<unavailable>, errorf=0x00007fffffff54e0, opt=0x00007fffffff5dd0) at subtype.c:1677
    frame #136128: 0x000000000080844c ponyc`check_receiver_cap at call.c:400:3
    frame #136129: 0x00000000008092c3 ponyc`method_application(opt=0x00007fffffff5dd0, ast=0x00007ffff72de5c0, partial=false) at call.c:577:9
    frame #136130: 0x000000000080962f ponyc`expr_call at call.c:609:3
    frame #136131: 0x0000000000809622 ponyc`expr_call(opt=0x00007fffffff5dd0, astp=0x00007fffffff58b0) at call.c:985
    frame #136132: 0x00000000007a7ffd ponyc`pass_expr(astp=0x00007fffffff58b0, options=0x00007fffffff5dd0) at expr.c:576:25
    frame #136133: 0x00000000007a868c ponyc`ast_visit(ast=0x00007fffffff58b0, pre=(ponyc`pass_pre_expr at expr.c:521:3), post=(ponyc`pass_expr at expr.c:542:1), options=0x00007fffffff5dd0, pass=PASS_EXPR) at pass.c:457:5
    frame #136134: 0x00000000007a8634 ponyc`ast_visit(ast=0x00007fffffff5910, pre=(ponyc`pass_pre_expr at expr.c:521:3), post=(ponyc`pass_expr at expr.c:542:1), options=0x00007fffffff5dd0, pass=PASS_EXPR) at pass.c:428:7
    frame #136135: 0x00000000007a8634 ponyc`ast_visit(ast=0x00007fffffff5970, pre=(ponyc`pass_pre_expr at expr.c:521:3), post=(ponyc`pass_expr at expr.c:542:1), options=0x00007fffffff5dd0, pass=PASS_EXPR) at pass.c:428:7
    frame #136136: 0x00000000007a8634 ponyc`ast_visit(ast=0x00007fffffff59d0, pre=(ponyc`pass_pre_expr at expr.c:521:3), post=(ponyc`pass_expr at expr.c:542:1), options=0x00007fffffff5dd0, pass=PASS_EXPR) at pass.c:428:7
    frame #136137: 0x00000000007a8634 ponyc`ast_visit(ast=0x00007fffffff5a30, pre=(ponyc`pass_pre_expr at expr.c:521:3), post=(ponyc`pass_expr at expr.c:542:1), options=0x00007fffffff5dd0, pass=PASS_EXPR) at pass.c:428:7
    frame #136138: 0x00000000007a8634 ponyc`ast_visit(ast=0x00007fffffff5a90, pre=(ponyc`pass_pre_expr at expr.c:521:3), post=(ponyc`pass_expr at expr.c:542:1), options=0x00007fffffff5dd0, pass=PASS_EXPR) at pass.c:428:7
    frame #136139: 0x00000000007a8634 ponyc`ast_visit(ast=0x00007fffffff5af0, pre=(ponyc`pass_pre_expr at expr.c:521:3), post=(ponyc`pass_expr at expr.c:542:1), options=0x00007fffffff5dd0, pass=PASS_EXPR) at pass.c:428:7
    frame #136140: 0x00000000007a8634 ponyc`ast_visit(ast=0x00007fffffff5b50, pre=(ponyc`pass_pre_expr at expr.c:521:3), post=(ponyc`pass_expr at expr.c:542:1), options=0x00007fffffff5dd0, pass=PASS_EXPR) at pass.c:428:7
    frame #136141: 0x00000000007a8634 ponyc`ast_visit(ast=0x00007fffffff5bb0, pre=(ponyc`pass_pre_expr at expr.c:521:3), post=(ponyc`pass_expr at expr.c:542:1), options=0x00007fffffff5dd0, pass=PASS_EXPR) at pass.c:428:7
    frame #136142: 0x00000000007a8634 ponyc`ast_visit(ast=0x00007fffffff5c10, pre=(ponyc`pass_pre_expr at expr.c:521:3), post=(ponyc`pass_expr at expr.c:542:1), options=0x00007fffffff5dd0, pass=PASS_EXPR) at pass.c:428:7
    frame #136143: 0x00000000007a8634 ponyc`ast_visit(ast=0x00007fffffff5d08, pre=(ponyc`pass_pre_expr at expr.c:521:3), post=(ponyc`pass_expr at expr.c:542:1), options=0x00007fffffff5dd0, pass=PASS_EXPR) at pass.c:428:7
    frame #136144: 0x00000000007a899b ponyc`visit_pass(astp=0x00007fffffff5d08, options=0x00007fffffff5dd0, last_pass=PASS_ALL, out_r=0x00007fffffff5cb7, pass=PASS_EXPR, pre_fn=(ponyc`pass_pre_expr at expr.c:521:3), post_fn=(ponyc`pass_expr at expr.c:542:1)) at pass.c:176:3
    frame #136145: 0x00000000007a8ee3 ponyc`ast_passes(astp=0x00007fffffff5d08, options=0x00007fffffff5dd0, last=PASS_ALL) at pass.c:269:3
    frame #136146: 0x00000000007a9068 ponyc`ast_passes_program(ast=<unavailable>, options=<unavailable>) at pass.c:318:1
    frame #136147: 0x00000000007c1d47 ponyc`program_load(path=".", opt=0x00007fffffff5dd0) at package.c:937:3
    frame #136148: 0x0000000000773887 ponyc`compile_package(path=<unavailable>, opt=0x00007fffffff5dd0, print_program_ast=<unavailable>, print_package_ast=<unavailable>) at main.c:56:1
    frame #136149: 0x00000000006f6259 ponyc`main(argc=<unavailable>, argv=0x00007fffffff5fe8) at main.c:133:7
    frame #136150: 0x00007ffff7ca9780 libc.so.6`__libc_start_main + 208
    frame #136151: 0x00000000007737aa ponyc`_start at start.S:120
redvers commented 2 years ago

I accidentally'd the stack.

ergl commented 2 years ago

From my backtrace, it seems like the compiler is getting into an infinite recursive loop:

frame #55455: 0x00000001000a44f8 ponyc`is_x_sub_x + 1824
frame #55456: 0x00000001000a6cc8 ponyc`is_typeparam_sub_x + 184
frame #55457: 0x00000001000a7390 ponyc`is_eq_typeargs + 232
frame #55458: 0x00000001000a7278 ponyc`exact_nominal + 196

frame #55459: 0x00000001000a44f8 ponyc`is_x_sub_x + 1824
frame #55460: 0x00000001000a7390 ponyc`is_eq_typeargs + 232
frame #55461: 0x00000001000a7278 ponyc`exact_nominal + 196

frame #55462: 0x00000001000a44f8 ponyc`is_x_sub_x + 1824
frame #55463: 0x00000001000a6cc8 ponyc`is_typeparam_sub_x + 184
frame #55464: 0x00000001000a7390 ponyc`is_eq_typeargs + 232

frame #55465: 0x00000001000a7278 ponyc`exact_nominal + 196
frame #55466: 0x00000001000a44f8 ponyc`is_x_sub_x + 1824
frame #55467: 0x00000001000a7390 ponyc`is_eq_typeargs + 232
frame #55468: 0x00000001000a4c34 ponyc`is_x_sub_x + 3676
frame #55469: 0x000000010006a70c ponyc`check_receiver_cap + 712
frame #55470: 0x000000010006a3bc ponyc`method_application + 1504
redvers commented 2 years ago

Well, since this is tagged 'help wanted' and the issue isn't obvious - let's see if I can help:

Minimal Crash:

  fun flatten[A: Array[Array[A]] #read](arrayin: Array[Array[A]]) =>
    let rv: Array[A] = Array[A]
    for f in arrayin.values() do
      None
    end

Doesn't crash:

  fun flatten[A: Array[Array[A]] #read](arrayin: Array[Array[A]]) => //: Array[A] =>
    let rv: Array[A] = Array[A]

Crashes:

  fun flatten[A: Array[Array[A]] #read](arrayin: Array[Array[A]]) => //: Array[A] =>
    let rv: Array[A] = Array[A]
    try
      let q = arrayin(0)?
    end

Doesn't crash:

  fun flatten[A: Array[MapIs[A, Any]] #read](arrayin: Array[MapIs[A, Any]]) => //: Array[A] =>
    let rv: Array[A] = Array[A]
    try
      let q = arrayin(0)?
    end

Does crash:

  fun flatten[A: MapIs[MapIs[A, Any], Any] #read](arrayin: MapIs[MapIs[A, Any], Any]) => //: Array[A] =>
    let rv: Array[A] = Array[A]
    try
      let q = arrayin(0)?
    end

So, I'm concluding that the compiler is having issues with generic types which contain themselves. I'm guessing (I'm not deep enough in the compiler to fully understand what is going on) that when it tries to navigate the AST the reference to Array[A] and Array[Array[A]] is the same?

redvers commented 2 years ago

fun flatten[A: Array[A] #read, B: Array[A]](arrayin: Array[Array[A]]) => Also crashes

redvers commented 2 years ago

fun flatten[A: Array[B] #read, B: Array[Any] #read](arrayin: Array[Array[A]]) =>

Does work when you don't do anything with it, but when you try and use it:

    /home/red/projects/pony/pony-enum/enum/Enum.pony:71:43: Any tag is not a subtype of Array[Any tag] #read
      fun flatten[A: Array[B] #read, B: Array[Any] #read](arrayin: Array[Array[A]]) => //: Array[A] =>
                                              ^
    /home/red/projects/pony/pony-enum/enum/Enum.pony:71:18: Array[B #read] #read has different type arguments than Array[Any tag] #read^
      fun flatten[A: Array[B] #read, B: Array[Any] #read](arrayin: Array[Array[A]]) => //: Array[A] =>
                     ^
    /home/red/projects/pony/pony-enum/enum/Enum.pony:71:18: Array[B #read] #read is not a subtype of Array[Any tag] #read^: #read is not a subcap of #read^
      fun flatten[A: Array[B] #read, B: Array[Any] #read](arrayin: Array[Array[A]]) => //: Array[A] =>
                     ^
redvers commented 2 years ago

The more I think about this, the more that I'm thinking I'm asking the impossible. This may be something that shouldn't be able to be expressed. I'm going to think on it some more.

redvers commented 2 years ago

... because I'm saying that A is always an Array of something. So it's Arrays all the way down.

I should probably close this.

redvers commented 2 years ago

(Basically - I'm doing a version of this:

fun flatten[A: Array[B] #read, B: Array[A] #read](arrayin: Array[Array[A]]) =>

ergl commented 2 years ago

I don't think this should be closed, it should at least be fixed by making the compiler print an error message.

redvers commented 2 years ago

I'm trying to see if I can formulate another way to create my function. I'm not sure there is.

redvers commented 2 years ago

fun flatten[A: Array[Array[B]] #read, B: Any #read](arrayin: Array[Array[B]]) !

jasoncarr0 commented 2 years ago

Yeah, there are two issues here:

  1. The compiler should handle this case gracefully at the user level
  2. If there is a use case, then recursive types can be possibly be handled, which is a long arduous but possible process.
SeanTAllen commented 2 years ago

I would love to be able to have recursive types. There's a really old issue opened by me for it.

That said as @jasoncarr0 said, we should fix the "BOOM!" that happens here. I know at some point there was no boom for recursive types, that might still be the case and this is missed by the recursive type prevention in the compiler.