detect non-regular recursion in types and error out early

[pnkfelix]

We don't currently support non-regular recursive types; an example of such a type is:

struct Foo<A> {
    data: Option<Foo<Vec<A>>>
}

Foo<A> is non-regular, because the recursive reference to Foo within the type is not Foo<A>, but instead is Foo<Vec<A>>.

We don't support such types today (and are unlikely to do so in the foreseeable future) because our strategy of code-generation via monomorphization breaks down for such types, which yield an infinite-sized family of instances. (We might support some cases of this in the future, if we can somehow identify some subfamily as being all representable via one piece of generated code. But that's not a question for today.)

A number of compiler passes in rustc are not really equipped to deal with such types.

We could (and should) write code to detect such types early on, (perhaps in the well-formedness checking code in wf.rs), and report an error to the user with appropriate feedback about the source of the non-regular recursion.

[huonw]

cc #4287

[steveklabnik]

We have like three or four bugs associated with this...

[pnkfelix]

oh this is totally a dupe of #4287.