bad diagnostic on using `impl Trait` in recursive function

[rylev]

Given the following code: [link]

struct Tree<'a> {
    nested: std::collections::BTreeMap<&'a str, Tree<'a>>,
}

impl<'a> Tree<'a> {
    fn flatten(&self) -> impl Iterator<Item = &Tree<'a>> {
        std::iter::once(self).chain(self.nested.values().flat_map(|tree| tree.flatten()))
    }
}

The current output on stable is:

error: hidden type `impl Iterator<Item = &Tree<'a>>` differed from previous `std::iter::Chain<std::iter::Once<&Tree<'a>>, FlatMap<std::collections::btree_map::Values<'_, &str, Tree<'a>>, impl Iterator<Item = &Tree<'a>>, [closure@src/lib.rs:7:67: 7:88]>>`
 --> src/lib.rs:7:9
  |
7 |         std::iter::once(self).chain(self.nested.values().flat_map(|tree| tree.flatten()))
  |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
note: previous hidden type bound here
 --> src/lib.rs:7:9
  |
7 |         std::iter::once(self).chain(self.nested.values().flat_map(|tree| tree.flatten()))
  |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

and on nightly:

error: concrete type differs from previous defining opaque type use
 --> src/lib.rs:7:9
  |
7 |         std::iter::once(self).chain(self.nested.values().flat_map(|tree| tree.flatten()))
  |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |         |
  |         expected `std::iter::Chain<std::iter::Once<&Tree<'a>>, FlatMap<std::collections::btree_map::Values<'_, &str, Tree<'a>>, impl Iterator<Item = &Tree<'a>>, [closure@src/lib.rs:7:67: 7:88]>>`, got `impl Iterator<Item = &Tree<'a>>`
  |         this expression supplies two conflicting concrete types for the same opaque type

Ideally this code should compile, but if it cannot be made to compile than the compiler error should use lesson compiler jargon (e.g., "opaque type").

[wwylele]

The code cannot compile because, from different points of view, the function is doing either of the following 2 things

• the return type is infinite. The concrete type of such function would be (informally) ReturnTypeOf(flatten) = Chain<Once, FlatMap<BTreeMapValue, flatten>>. Note that flatten appears on both sides, and you would get an infinitely nested type if you try to deduce the return type
• Suppose the type is finite and has a Leaf return type for the leaf, then the function is returning a different type for each recursion level, which a single impl Trait cannot capture. If the leaf level returns a Leaf type, then the next level would return a Chain<Once, FlatMap<BTreeMapValue, BTreeMap -> Leaf>> type, and then the next following level would be Chain<Once, FlatMap<BTreeMapValue, BTreeMap -> Chain<Once, FlatMap<BTreeMapValue, BTreeMap -> Leaf>>>>, and so on. This is also what the error message is about:

  hidden type (of the current recursion level) is differed from previous (the previous recursion level)

---

One way to work around this is to introduce a type-erasing dynamic dispatch somewhere in the recursion, so the return type becomes finite. For example:

struct Tree<'a> {
    nested: std::collections::BTreeMap<&'a str, Tree<'a>>,
}

impl<'a> Tree<'a> {
    fn flatten(&self) -> impl Iterator<Item = &Tree<'a>> {
        Box::new(std::iter::once(self).chain(self.nested.values().flat_map(|tree| tree.flatten())))
            as Box<dyn Iterator<Item = &Tree<'a>>>
    }
}

[wwylele]

The error message indeed looks confusing on a recursive function. Maybe some special case error message and advises could be better for recursive function.