Explosive memory usage in type checker

[bkoropoff]

Test Case

To reproduce, download the two files in this gist and attempt to build mkrust.rs:

https://gist.github.com/bkoropoff/537951c596ba24166f06

Analysis

The complex json.query(...) expression in mkrust.rs seems to be the culprit. Progressively simplifying the expression will eventually cause the bug to no longer reproduce.

Running rustc under massif yields the following (truncated for space) stack for the primary memory hog, which appears to be a hash map associated with region inference:

99.25% (522,819,638B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->68.00% (358,203,360B) 0x7E5562C: je_mallocx (in /home/bkoropoff/Software/rust/lib/librustrt-d8560cb2-0.11.0-pre.so)
| ->50.16% (264,241,152B) 0x57AF077: collections::hashmap::table::RawTable$LT$K$C$$x20V$GT$::new::h16071681466547729146::v0.11.0.pre (in /home/bkoropoff/Software/rust/lib/librustc-d252d482-0.11.0-pre.so)
| | ->50.16% (264,241,152B) 0x57B1D51: collections::hashmap::HashMap$LT$K$C$$x20V$C$$x20H$GT$::resize::h9544924386944675449::v0.11.0.pre (in /home/bkoropoff/Software/rust/lib/librustc-d252d482-0.11.0-pre.so)
| | | ->50.16% (264,241,152B) 0x57B81D1: middle::typeck::infer::region_inference::RegionVarBindings$LT$$x27a$GT$::add_constraint::he966b592d2e519c2Sxo::v0.11.0.pre (in /home/bkoropoff/Software/rust/lib/librustc-d252d482-0.11.0-pre.so)
| | |   ->50.16% (264,241,152B) 0x57BA642: middle::typeck::infer::region_inference::RegionVarBindings$LT$$x27a$GT$::make_subregion::h5a25349bdfe40532sBo::v0.11.0.pre (in /home/bkoropoff/Software/rust/lib/librustc-d252d482-0.11.0-pre.so)
| | |   | ->50.16% (264,241,152B) 0x57BC9F6: middle::typeck::infer::region_inference::RegionVarBindings$LT$$x27a$GT$::lub_regions::closure.93817 (in /home/bkoropoff/Software/rust/lib/librustc-d252d482-0.11.0-pre.so)
| | |   | | ->50.16% (264,241,152B) 0x57BC0D0: middle::typeck::infer::region_inference::RegionVarBindings$LT$$x27a$GT$::combine_vars::h5ec95b92851d887cDUo::v0.11.0.pre (in /home/bkoropoff/Software/rust/lib/librustc-d252d482-0.11.0-pre.so)
| | |   | | | ->50.16% (264,241,152B) 0x57A23E6: middle::typeck::infer::region_inference::RegionVarBindings$LT$$x27a$GT$::lub_regions::hc2ef972d6db9d001eIo::v0.11.0.pre (in /home/bkoropoff/Software/rust/lib/librustc-d252d482-0.11.0-pre.so)
| | |   | | |   ->50.16% (264,241,152B) 0x578A07A: middle::typeck::infer::lub::Lub$LT$$x27f$GT$.Combine::regions::h96b097927410ccd30sn::v0.11.0.pre (in /home/bkoropoff/Software/rust/lib/librustc-d252d482-0.11.0-pre.so)

[bkoropoff]

I updated the gist to deal with recent changes to rustc and libstd. The bug still reproduces.

[bkoropoff]

Based on advice on irc, cc @nikomatsakis and @pcwalton

I should also note that code very similar to this compiled a couple weeks ago, so this is probably a recent regression.

[bkoropoff]

I went back and tried older versions of rustc all the way to the start of June, and all of them exhibited unbounded memory growth, so it isn't a regression after all.

[pnkfelix]

cc me

[bkoropoff]

I've trimmed down the test case a little bit. On my system, it runs until rustc aborts with oom. If I simplify the expression in certain ways, it will manage to actually build (although it will consume up to 4GB of RAM). So I don't think I'm hitting an infinite loop, just a pathological edge case in the type checker. Title updated to reflect this.

[bkoropoff]

After some experimenting, I now have a substantially reduced test case. Something about having a trait bound on the generic type parameter is what causes the crazy memory usage.

[huonw]

Inlined for posterity:

struct Base;
struct Wrapper<B>(B);

trait Bug {}
impl Bug for Base {}
impl<B> Bug for Wrapper<B> {}

// Removing the bound on B makes the bug go away.
// So does turning wrap into a free function and
// changing the expression below appropriately.
impl<B:Bug> Wrapper<B> {
    fn wrap(self) -> Wrapper<Wrapper<B>> {
        Wrapper(self)
    }
}

fn main() {
    // This easily crashes rustc with oom on my laptop
    let _expr = Wrapper(Base).wrap().wrap().wrap().wrap().wrap().wrap().wrap()
        .wrap().wrap().wrap().wrap().wrap().wrap().wrap().wrap().wrap().wrap()
        .wrap().wrap().wrap().wrap().wrap().wrap().wrap().wrap().wrap().wrap();
}

[pnkfelix]

cc me

[bkoropoff]

The new inference scheme fixes the reduced test case. Unfortunately it also causes my library to no longer typecheck, but that's a separate issue (#16870). Closing.