Be smarter about recognizing recursive data types.
Motivation
Currently we don't fully analyze things like nested strict tuples.
The reason is that a data type is currently considered recursive if TyCon appearances cross a certain threshold (two occurrences).
Regular tuples are hardcoded to work, but that seems unsatisfying to me.
Further the current approach can cause findTypeShape to loop when dealing with code like newtype T = T (Int, T)
Solution
Instead try to keep track of seen types.
If a type we have seen before appears in a field we hit a recursive case and bail out.
We still keep the old TyCon based approach around.
Performance impact in the regular case is negglible at a ~0.09% allocation increase. In cases where we spend a significant amount of work determining type shapes allocations increase by 3%.
I argue this is worthwhile since it:
- Removes a magic behaviour where user defined and builtin types behave differently.
- Avoid the risk of the compiler looping on very specific code (the newtype/tuple loop above).
- Analyzes non-recursive types independent of their depth of nesting.
- Doesn't regress termination or correctness of the compiler.