Skip to content

Be smarter about recognizing recursive data types.

Andreas Klebinger requested to merge wip/andreask/rec_field_shapes into master

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.
Edited by Andreas Klebinger

Merge request reports