rustc runs out of memory when compiling trait heavy code

[Marwes]

Been working on an update to combine and ran into #43132. Since the fix has been merged I updated using rustup but now rustc runs out of memory when compiling instead.

This branch reproduces the issue https://github.com/Marwes/combine/tree/ice_allocator_exhausted. I haven't bothered to reduce to a minimal production given that it is likely related to the slow down mentioned in #43132 and removing code will just make it compile and make the problem less pronounced (possibly the minimal example here reproduces the same problem as well https://github.com/rust-lang/rust/pull/32062/files#diff-6a2bc45424fb5e8e0f7eb99f2e05f9cf).

$ rustc --version --verbose
rustc 1.21.0-nightly (dd53dd5f9 2017-08-01)
binary: rustc
commit-hash: dd53dd5f9e21dce1fbc06b7f9f451d1009bdcfd8
commit-date: 2017-08-01
host: x86_64-pc-windows-msvc
release: 1.21.0-nightly
LLVM version: 4.0

[Marwes]

EDIT I may have been mistaken about the example from #32062. While compilation takes far longer than one would expect, that has likely always been the case as well (still a potential issue but perhaps not a reproduction for the one I encountered).

The example added for #32062 reproduces as long as few more calls to chain gets added

// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

// pretty-expanded FIXME #23616

fn main() {
    let _ = test(Some(0).into_iter());
}

trait Parser {
    type Input: Iterator;
    type Output;
    fn parse(self, input: Self::Input) -> Result<(Self::Output, Self::Input), ()>;
    fn chain<P>(self, p: P) -> Chain<Self, P> where Self: Sized {
        Chain(self, p)
    }
}

struct Token<T>(T::Item) where T: Iterator;

impl<T> Parser for Token<T> where T: Iterator {
    type Input = T;
    type Output = T::Item;
    fn parse(self, _input: Self::Input) -> Result<(Self::Output, Self::Input), ()> {
        Err(())
    }
}

struct Chain<L, R>(L, R);

impl<L, R> Parser for Chain<L, R> where L: Parser, R: Parser<Input = L::Input> {
    type Input = L::Input;
    type Output = (L::Output, R::Output);
    fn parse(self, _input: Self::Input) -> Result<(Self::Output, Self::Input), ()> {
        Err(())
    }
}

fn test<I>(i: I) -> Result<((), I), ()> where I: Iterator<Item = i32> {
    Chain(Token(0), Token(1))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .chain(Chain(Token(0), Token(1)))
        .parse(i)
        .map(|(_, i)| ((), i))
}

[alexcrichton]

@Marwes did this compile previously? Just wondering if we can tag it as a regression!

[aturon]

cc @arielb1 for potential regression tracking

[Marwes]

@alexcrichton I am afraid the the example from #32062 would fail to compile before as well so it is likely unrelated. https://github.com/Marwes/combine/tree/ice_allocator_exhausted did not compile before due to #43132 so this is probably not a regression.

[jonhoo]

A tangentially related comment: on nightly, no error is printed when the compiler fails this way beyond Could not compile "foo".. On beta the situation is a little better, as it at least prints fatal runtime error: allocator memory exhausted.

[alexcrichton]

Ah unfortunately this is a beta regression. Compiling this source I get:

$ rustc -V
rustc 1.19.0 (0ade33941 2017-07-17)
$ time rustc foo.rs
rustc foo.rs  3.00s user 0.02s system 99% cpu 3.040 total
$ rustc +beta -V
rustc 1.20.0-beta.2 (54279dfac 2017-08-13)
$ time rustc +beta foo.rs
rustc +beta foo.rs  6.17s user 1.26s system 99% cpu 7.437 total

[alexcrichton]

cc @rust-lang/compiler for a new beta regression