Exponential type/trait-checking behavior from linearly nested iterator adapters.

[eddyb]

The following test takes an exponential amount of time to type-check the body of huge (at the time of this writing, reported by -Z time-passes under "item-types checking"):

#![crate_type = "lib"]

pub fn unit() -> std::iter::Empty<()> {
    std::iter::empty()
}

macro_rules! nest {
    ($inner:expr) => (unit().flat_map(|_| {
        $inner
    }).flat_map(|_| unit()))
}

macro_rules! nests {
    () => (unit());
    ($_first:tt $($rest:tt)*) => (nest!(nests!($($rest)*)))
}

pub fn huge() -> impl Iterator<Item = ()> {
    nests! {
        // 1/x * 6/5 seconds.
        4096 2048 1024 512 256 128 64 32 16 8 4 2

        // x * 6/5 seconds.
        1 2 4 8 // 16 32 64
    }
}

This has been reduced from an ambiguity-aware parse tree visitor, and you can see a partial reduction here: https://gist.github.com/eddyb/5f20b8f48b68c92f7d4f022a18c374f4#file-repro-rs.

cc @nikomatsakis

[eddyb]

I should've tried to avoid impl Trait - AFAICT, it's irrelevant here, the compiler is just having a hard time dealing with the body of the function.

For the record, our workaround is using one big generator with many nested for loops, instead of nested iterator adaptors (see rust-lang/gll#47).

[eddyb]

I just tested this and it seems to work really well, until it hits the recursion limit:

pub fn nest<F: FnMut() -> R, R>(mut f: F) -> R {
    f()
}

macro_rules! nest {
    ($inner:expr) => (nest(|| {
        $inner
    }))
}

macro_rules! nests {
    () => (());
    ($_first:tt $($rest:tt)*) => (nest!(nests!($($rest)*)))
}

So a for_each ("internal iteration") solution (with many nested closures) should work much better than one based on Iterator ("external iteration") adapters (with many of them nested in types).

[eddyb]

@nikomatsakis Do you think this could be caused by the closures returning adapters, as opposed to them being chained without closures? I might try a different implementation as a workaround.