rustc stack overflow when using polymorphically recursive type

[rntz]

Compiling the following file:

// Type of complete binary trees with data at the leaves.
enum Tree<T> {
    Leaf(T),
    Branch(~Tree<(T,T)>),
}

fn main () {
  // a completely trivial use
  let _x: Tree<int> = Leaf(5);
}

Results in rustc running for a while and eventually aborting:

$ time rustc hang-polymorphic-recursion.rs
zsh: abort      rustc hang-polymorphic-recursion.rs
rustc hang-polymorphic-recursion.rs  5.97s user 0.83s system 99% cpu 6.811 total

Using gdb, the cause of this appears to be an infinite recursion resulting in stack overflow. Setting RUST_MAX_STACK=48000 to limit the size of the backtrace, and omitting a bunch of lines in the middle, we get:

#0  0x00007ffff37d5545 in raise () from /lib64/libc.so.6
#1  0x00007ffff37d69c8 in abort () from /lib64/libc.so.6
#2  0x00007ffff5e138f6 in rust_task::new_stack (this=0x7fffec20cce0, 
    requested_sz=<optimized out>) at /home/rntz/s/rust/src/rt/rust_task.cpp:538
#3  0x00007ffff5e24629 in __morestack ()
   from /home/rntz/p/bin/../lib/librustrt.so
#4  0x00007ffff5e15f00 in call_on_c_stack (fn_ptr=<optimized out>, 
    args=0x7ffff287d140, this=0x7fffec20cce0)
    at /home/rntz/s/rust/src/rt/rust_task.h:481
#5  new_stack_fast (requested_sz=2097152, this=0x7fffec20cce0)
    at /home/rntz/s/rust/src/rt/rust_task.h:597
#6  next_stack (args_sz=0, args_addr=0x7ffff287d1e0, stk_sz=<optimized out>, 
    this=0x7fffec20cce0) at /home/rntz/s/rust/src/rt/rust_task.h:540
#7  upcall_new_stack (stk_sz=<optimized out>, args_addr=0x7ffff287d1e0, 
    args_sz=0) at /home/rntz/s/rust/src/rt/rust_upcall.cpp:323
#8  0x00007ffff790f3ae in __morestack ()
   from /home/rntz/p/bin/../lib/libstd-6c65cf4b443341b1-0.7.so
#9  0x00007ffff61849ec in vec::with_capacity_22951::_e02e2fffb267a2c::_0$x2e7
    () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#10 0x00007ffff63225a4 in vec::__extensions__::map_40734::_af9d6bbe4c97e84::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#11 0x00007ffff634a99a in middle::ty::fold_sty::_54deb1bc56a6c17::_0$x2e7 ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#12 0x00007ffff634a419 in middle::ty::fold_sty_to_ty::_cfbe63c86e51edca::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#13 0x00007ffff634be59 in middle::ty::fold_regions_and_ty::_f3996f94f24f218::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#14 0x00007ffff6372ed5 in middle::subst::__extensions__::meth_46035::effectfulSubst::_e77fdc2970e65b2::_0$x2e7 ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#15 0x00007ffff637355b in middle::subst::__extensions__::effectfulSubst::anon::expr_fn_46046 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#16 0x00007ffff63225ce in vec::__extensions__::map_40734::_af9d6bbe4c97e84::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#17 0x00007ffff634e893 in middle::ty::fold_regions_and_ty::fold_substs::_1f3b6299fc26c43a::_0$x2e7 ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#18 0x00007ffff634bd6c in middle::ty::fold_regions_and_ty::_f3996f94f24f218::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#19 0x00007ffff6372ed5 in middle::subst::__extensions__::meth_46035::effectfulSubst::_e77fdc2970e65b2::_0$x2e7 ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#20 0x00007ffff637355b in middle::subst::__extensions__::effectfulSubst::anon::expr_fn_46046 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#21 0x00007ffff634a5e5 in middle::ty::fold_sty::_54deb1bc56a6c17::_0$x2e7 ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#22 0x00007ffff634a419 in middle::ty::fold_sty_to_ty::_cfbe63c86e51edca::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#23 0x00007ffff634be59 in middle::ty::fold_regions_and_ty::_f3996f94f24f218::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#24 0x00007ffff6372ed5 in middle::subst::__extensions__::meth_46035::effectfulSubst::_e77fdc2970e65b2::_0$x2e7 ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#25 0x00007ffff63734fb in middle::subst::__extensions__::effectfulSubst::anon::expr_fn_46044 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#26 0x00007ffff63225ce in vec::__extensions__::map_40734::_af9d6bbe4c97e84::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#27 0x00007ffff634b470 in middle::ty::fold_sig::_88677926f15b4cd8::_0$x2e7 ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#28 0x00007ffff634bf1e in middle::ty::fold_regions_and_ty::_f3996f94f24f218::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#29 0x00007ffff6372ed5 in middle::subst::__extensions__::meth_46035::effectfulSubst::_e77fdc2970e65b2::_0$x2e7 ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#30 0x00007ffff634f50f in middle::subst::__extensions__::meth_43986::subst::_e77fdc2970e65b2::_0$x2e7 ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#31 0x00007ffff61ec983 in middle::ty::subst::_60764340192f4aa4::_0$x2e7 ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#32 0x00007ffff636ad0d in middle::ty::substd_enum_variants::anon::expr_fn_45497
    () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#33 0x00007ffff636ab96 in vec::__extensions__::from_iterator_45483::_d92c4743c97fe764::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#34 0x00007ffff6317fab in middle::ty::substd_enum_variants::_eb876c23233c1d77::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#35 0x00007ffff6352909 in middle::ty::type_contents::tc_ty::_7cc6d67baf8e7d7e::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#36 0x00007ffff6354b10 in middle::ty::type_contents::tc_mt::_fccf794e93a99779::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#37 0x00007ffff6352acb in middle::ty::type_contents::tc_ty::_7cc6d67baf8e7d7e::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#38 0x00007ffff6352983 in middle::ty::type_contents::tc_ty::_7cc6d67baf8e7d7e::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#39 0x00007ffff6354b10 in middle::ty::type_contents::tc_mt::_fccf794e93a99779::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#40 0x00007ffff6352acb in middle::ty::type_contents::tc_ty::_7cc6d67baf8e7d7e::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#41 0x00007ffff6352983 in middle::ty::type_contents::tc_ty::_7cc6d67baf8e7d7e::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#42 0x00007ffff6354b10 in middle::ty::type_contents::tc_mt::_fccf794e93a99779::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
    ...
    ... MANY LINES OMITTED HERE ...
    ...
#5205 0x00007ffff6354b10 in middle::ty::type_contents::tc_mt::_fccf794e93a99779::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5206 0x00007ffff6352acb in middle::ty::type_contents::tc_ty::_7cc6d67baf8e7d7e::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5207 0x00007ffff6352983 in middle::ty::type_contents::tc_ty::_7cc6d67baf8e7d7e::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5208 0x00007ffff62ad57f in middle::ty::type_contents::_d97cb6e18e2777dc::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5209 0x00007ffff6356948 in middle::ty::type_moves_by_default::_8790fe2979702bc7::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5210 0x00007ffff6779e54 in middle::moves::__extensions__::meth_88738::consume_expr::_80ad785c8e2f39d6::_0$x2e7 ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5211 0x00007ffff677053f in middle::moves::compute_modes_for_expr::_536438e3f6ba19f::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5212 0x00007ffff6773239 in visit::default_visitor_88498::anon::expr_fn_88570
    () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5213 0x00007ffff677588a in visit::default_visitor_88498::anon::expr_fn_88630
    () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5214 0x00007ffff6773bdb in visit::default_visitor_88498::anon::expr_fn_88587
    () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5215 0x00007ffff67735cf in visit::default_visitor_88498::anon::expr_fn_88575
    () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5216 0x00007ffff6778b93 in visit::default_visitor_88498::anon::expr_fn_88677
    () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5217 0x00007ffff677161f in visit::default_visitor_88498::anon::expr_fn_88530
    () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5218 0x00007ffff677083a in visit::default_visitor_88498::anon::expr_fn_88501
    () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5219 0x00007ffff676c694 in middle::moves::compute_moves::_21d0e5db50b085::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5220 0x00007ffff681cd6f in driver::driver::compile_rest::_962c67cf6f6b38e6::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5221 0x00007ffff6851774 in __morestack ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5222 0x00007ffff681ffec in driver::driver::compile_upto::_eb1a36cc59485b2::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5223 0x00007ffff6820385 in driver::driver::compile_input::_9d565d13a71137c::_0$x2e7 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5224 0x00007ffff683f6b3 in run_compiler::_5e2f8a97d6ae9ffb::_0$x2e7 ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5225 0x00007ffff685149e in main::anon::expr_fn_99541 ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5226 0x00007ffff684ef47 in monitor::anon::expr_fn_99366 ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5227 0x00007ffff684685b in task::__extensions__::try_98227::anon::expr_fn_98665 () from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5228 0x00007ffff6851774 in __morestack ()
   from /home/rntz/p/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.7.so
#5229 0x00007ffff7897f01 in task::spawn::spawn_raw_oldsched::make_child_wrapper::anon::expr_fn_18364 ()
   from /home/rntz/p/bin/../lib/libstd-6c65cf4b443341b1-0.7.so
#5230 0x00007ffff790f3dc in __morestack ()
   from /home/rntz/p/bin/../lib/libstd-6c65cf4b443341b1-0.7.so
#5231 0x00007ffff5e13b9b in task_start_wrapper (a=0x7fffec20dc90)
    at /home/rntz/s/rust/src/rt/rust_task.cpp:164
#5232 0x0000000000000000 in ?? ()

[bblum]

The issue is with type_contents. That function uses a local cache to avoid repeating work for recursive types, but when it instantiates the nested Trees, the parameterized type is different. Basically any polymorphic reinstantiation seems to cause this problem, as long as the substitution keeps creating new types:

enum Tree<T> {
        Leaf(T),
        Branch(~Tree<~T>),
}

enum Tree<T> {
        Leaf(T),
        Branch(~Tree<(T,)>),
}

enum Tree<T> {
        Leaf(T),
        Branch(~Tree<Tree<T>>),
}

It shouldn't be surprising that this, however, doesn't cause the problem:

enum Tree<T,U> {
        Leaf(T),
        Branch(~Tree<U,T>),
}

[bblum]

i guess @nikomatsakis is most likely to know how to deal with this

[nikomatsakis]

This is interesting. I can't decide whether such a type ought to be legal or not. I can't think of any principled reason for it to be illegal precisely, though it's not quite clear to me what such a type is good for. In any case, handling this case does significantly complicate type contents (and perhaps a few other similar algorithms, though most are robust to such types). As @bblum points out, the current design is "inductive" and assumes we can fully expand out all the types.

One alternate design that comes to mind would be to modify type contents so that it computes "type content equations" rather than precise bit sets. These equations could then be applied to a specific set of type parameters. So, in other words, for something like struct Foo<T> { a: @int, b: T } we would generate a type contents like TC_MANAGED + TC(T). Then when a precise T was given, we could compute the final result. In the case of sometihng like @T we'd need to handle that too. This design might be faster, not sure. I've been wanting to reimplement type contents anyhow because it's become rather confusing, this might be a nice excuse.

However, I should go re-read the various literature on other algorithms that operate over infinitely sized types and see whether there is another approach. This seems to be highly related to such algorithms as well as induction vs co-induction and maybe there is another solution to be had.

[msullivan]

Actually using such a type won't work well, since polymorphic recursion doesn't work in rust. (Because we monomorphize.)

[pnkfelix]

�I went ahead and looked up the references I could remember and skimmed them over, so i figured I might as well attach them here:

• Jim's "What are principal typings and what are they good for?" (1996) references polymorphic recursion and mentions it as a recurring topic on the ML mailing list. Here's a page from the ML community with a couple of motivating examples.
• Okasaki's dissertation (1996) provides at least one motivating example for polymorphic recursion (see section 7.1), but also provides the regular datatype encoding.
• Bird and Meertens' "Nested Datatypes" (1998) has small examples of polymorphic recursion (aka "non-regular datatypes" aka "nested datatypes").
• Hallett and Kfoury (2005) has a mix of examples, but some of them require an intersection type system; perhaps eight of them may be relevant here.

Am I convinced by these examples? Well, no, at least, not the one's I've actually read and digested.

[bblum]

actually this is a dupe of #4363.