Fun with associated types, Iterator, and IntoIterator

[Gankra]

(The following is a reduced example)

I have a composite two-level structure which I want to iterate. This involves iterating the first level to obtain blocks of the second level, which are in turn iterated. We would like to update this code to use associated types.

My first attempt is as follows:

use std::iter::IntoIterator;

struct AbsIter<DListIter, VecDequeIter> {
    list_iter: DListIter,
    block_iter: VecDequeIter,
}

impl<VecDequeIter, DListIter> Iterator for AbsIter<DListIter, VecDequeIter> where
    VecDequeIter: Iterator,
    DListIter: Iterator,
    // adding Item=VecDequeIter::Item solves issue
    DListIter::Item: IntoIterator<IntoIter=VecDequeIter> 
{
    type Item = VecDequeIter::Item;
    fn next(&mut self) -> Option<VecDequeIter::Item> {
        let block = self.list_iter.next().unwrap();
        self.block_iter = block.into_iter();
        self.block_iter.next()
    }
}

fn main(){}

but this errors out with:

<anon>:17:33: 17:44 error: type mismatch resolving `<VecDequeIter as core::iter::Iterator>::Item == <<DListIter as core::iter::Iterator>::Item as core::iter::IntoIterator>::Item`:
 expected trait `core::iter::Iterator`,
    found trait `core::iter::IntoIterator` [E0271]
<anon>:17         self.block_iter = block.into_iter();
                                          ^~~~~~~~~~~

Which doesn't make any sense to me. It looks like it might be a bug. Still, it's easily resolved by making the change in the comment: adding Item=VecDequeIter::Item to the IntoIterator bound solves this.

I then notice that actually VecDequeIter need not be a generic argument, it follows from DListIter. Ok, let's do that:

use std::iter::IntoIterator;

struct AbsIter<DListIter, VecDequeIter> {
    list_iter: DListIter,
    block_iter: VecDequeIter,
}

impl<DListIter> Iterator for 
AbsIter<DListIter, <DListIter::Item as IntoIterator>::IntoIter> where
    DListIter: Iterator,
    DListIter::Item: IntoIterator,
{
    type Item = <DListIter::Item as IntoIterator>::Item;
    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
        let block = self.list_iter.next().unwrap();
        self.block_iter = block.into_iter();
        self.block_iter.next()
    }
}

fn main(){}

Ignoring the apparently necessary as IntoIterator's, this triggers some clearly exponential behaviour in the coherence checker:

time: 0.000     parsing
time: 0.000     recursion limit
time: 0.000     gated macro checking
time: 0.000     configuration 1
time: 0.000     crate injection
time: 0.004     macro loading
time: 0.000     plugin loading
time: 0.000     plugin registration
time: 0.001     expansion
time: 0.000     complete gated feature checking
time: 0.000     configuration 2
time: 0.000     maybe building test harness
time: 0.000     prelude injection
time: 0.000     checking that all macro invocations are gone
time: 0.000     assigning node ids and indexing ast
time: 0.000     external crate/lib resolution
time: 0.000     language item collection
time: 0.004     resolution
time: 0.000     lifetime resolution
time: 0.000     looking for entry point
time: 0.000     looking for plugin registrar
time: 0.000     region resolution
time: 0.000     loop checking
time: 0.000     static item recursion checking
time: 0.000     type collecting
time: 0.000     variance inference
time: 16.663    coherence checking
time: 0.420     type checking
time: 0.110     const checking
time: 0.000     privacy checking
time: 0.000     stability index
time: 0.000     intrinsic checking
time: 0.000     effect checking
time: 0.001     match checking
time: 0.000     liveness checking
time: 0.212     borrow checking
time: 0.110     rvalue checking
time: 0.000     reachability checking
time: 0.000     death checking
time: 0.001     stability checking
time: 0.000     unused lib feature checking
time: 0.001     lint checking
time: 0.000     resolving dependency formats
time: 0.002     translation
  time: 0.000   llvm function passes
  time: 0.000   llvm module passes
  time: 0.009   codegen passes
  time: 0.000   codegen passes
time: 0.016     LLVM passes
  time: 0.387   running linker
time: 0.387     linking

[Gankra]

CC @nikomatsakis

[bluss]

Current behavior: Rustc suggests increasing the recursion limit. Using #![recursion_limit="1024"] it instead leads to stack overflow in rustc.

Maybe this is fixed in a sense, because I get this:

time: 0.242 coherence checking

before the stack overflow. Presumably it overflows during type checking.

[birkenfeld]

In current nightly, the second example compiles fine, in inconspicuous time. Seems to be fixed?

[Marwes]

If this is no longer slow it was probably fixed by #32062.

[bluss]

Thanks for the information. And a big ❤️ to those who improve rustc performance.