Infinite recursion in compiler when combining cyclic bounds and intersection types

[plietar]

The following program causes the compiler to recurse infinitely, until it overflows its stack and segfaults. Using a union type (X | N iso) compiles fine.

trait N
class A[Y: (X & N iso), X: Y]

This is the bottom of the backtrace in lldb. The frames before that just alternate between typeparam.c:330 and typeparam.c:314

    frame #87334: 0x00000001000cedd0 ponyc`cap_from_constraint(type=0x000000010b1d7600) + 384 at typeparam.c:330
    frame #87335: 0x00000001000ced57 ponyc`cap_from_constraint(type=0x000000010b1d9e00) + 263 at typeparam.c:314
    frame #87336: 0x00000001000cedd0 ponyc`cap_from_constraint(type=0x000000010b1d7600) + 384 at typeparam.c:330
    frame #87337: 0x00000001000ced57 ponyc`cap_from_constraint(type=0x000000010b1d9e00) + 263 at typeparam.c:314
    frame #87338: 0x00000001000cedd0 ponyc`cap_from_constraint(type=0x000000010b1d7600) + 384 at typeparam.c:330
    frame #87339: 0x00000001000ced57 ponyc`cap_from_constraint(type=0x000000010b1d9e00) + 263 at typeparam.c:314
    frame #87340: 0x00000001000cec1e ponyc`typeparam_set_cap(typeparamref=0x000000010b1d7600) + 158 at typeparam.c:547
    frame #87341: 0x0000000100096e56 ponyc`flatten_typeparamref(opt=0x00007fff5fbff878, ast=0x000000010b1d7600) + 150 at flatten.c:88
    frame #87342: 0x000000010009708c ponyc`pass_flatten(astp=0x00007fff5fbff2b0, options=0x00007fff5fbff878) + 508 at flatten.c:302
    frame #87343: 0x0000000100099e3d ponyc`ast_visit(ast=0x00007fff5fbff2b0, pre=0x0000000000000000, post=(ponyc`pass_flatten at flatten.c:266), options=0x00007fff5fbff878, pass=PASS_FLATTEN) + 685 at pass.c:387
    frame #87344: 0x0000000100099d74 ponyc`ast_visit(ast=0x00007fff5fbff340, pre=0x0000000000000000, post=(ponyc`pass_flatten at flatten.c:266), options=0x00007fff5fbff878, pass=PASS_FLATTEN) + 484 at pass.c:358
    frame #87345: 0x0000000100099d74 ponyc`ast_visit(ast=0x00007fff5fbff3d0, pre=0x0000000000000000, post=(ponyc`pass_flatten at flatten.c:266), options=0x00007fff5fbff878, pass=PASS_FLATTEN) + 484 at pass.c:358
    frame #87346: 0x0000000100099d74 ponyc`ast_visit(ast=0x00007fff5fbff460, pre=0x0000000000000000, post=(ponyc`pass_flatten at flatten.c:266), options=0x00007fff5fbff878, pass=PASS_FLATTEN) + 484 at pass.c:358
    frame #87347: 0x0000000100099d74 ponyc`ast_visit(ast=0x00007fff5fbff4f0, pre=0x0000000000000000, post=(ponyc`pass_flatten at flatten.c:266), options=0x00007fff5fbff878, pass=PASS_FLATTEN) + 484 at pass.c:358
    frame #87348: 0x0000000100099d74 ponyc`ast_visit(ast=0x00007fff5fbff580, pre=0x0000000000000000, post=(ponyc`pass_flatten at flatten.c:266), options=0x00007fff5fbff878, pass=PASS_FLATTEN) + 484 at pass.c:358
    frame #87349: 0x0000000100099d74 ponyc`ast_visit(ast=0x00007fff5fbff610, pre=0x0000000000000000, post=(ponyc`pass_flatten at flatten.c:266), options=0x00007fff5fbff878, pass=PASS_FLATTEN) + 484 at pass.c:358
    frame #87350: 0x0000000100099d74 ponyc`ast_visit(ast=0x00007fff5fbff738, pre=0x0000000000000000, post=(ponyc`pass_flatten at flatten.c:266), options=0x00007fff5fbff878, pass=PASS_FLATTEN) + 484 at pass.c:358
    frame #87351: 0x000000010009a6fc ponyc`visit_pass(astp=0x00007fff5fbff738, options=0x00007fff5fbff878, last_pass=PASS_ALL, out_r=0x00007fff5fbff703, pass=PASS_FLATTEN, pre_fn=0x0000000000000000, post_fn=(ponyc`pass_flatten at flatten.c:266)) + 156 at pass.c:166
    frame #87352: 0x000000010009a10b ponyc`ast_passes(astp=0x00007fff5fbff738, options=0x00007fff5fbff878, last=PASS_ALL) + 443 at pass.c:217
    frame #87353: 0x0000000100099f45 ponyc`ast_passes_program(ast=0x000000010b7bfcc0, options=0x00007fff5fbff878) + 37 at pass.c:249
    frame #87354: 0x00000001000b5c3e ponyc`program_load(path=".", opt=0x00007fff5fbff878) + 190 at package.c:833
    frame #87355: 0x00000001000029bf ponyc`compile_package(path=".", opt=0x00007fff5fbff878, print_program_ast=false, print_package_ast=false) + 47 at main.c:234
    frame #87356: 0x00000001000027ef ponyc`main(argc=1, argv=0x00007fff5fbff928) + 1103 at main.c:367
    frame #87357: 0x00007fffe3db2255 libdyld.dylib`start + 1
    frame #87358: 0x00007fffe3db2255 libdyld.dylib`start + 1

$ ponyc -v
0.11.2-35b803c3b [debug]
compiled with: llvm 3.9.1 -- Apple LLVM version 8.0.0 (clang-800.0.42.1)

[jemc]

Definitely seems like something we should support if it is possible. I'll have to look into this later and see what's causing the cycle and if we can easily avoid it.

[sylvanc]

Yeah, we should be able to handle this. It's another recursive type edge case.