[GHC] #11518: Test TcCoercibleFail hangs with substitution sanity checks enabled

[GHC]

#11518: Test TcCoercibleFail hangs with substitution sanity checks enabled
-------------------------------------+-------------------------------------
        Reporter:  niteria           |                Owner:  niteria
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler (Type    |              Version:  8.1
  checker)                           |
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by niteria):

 > But what's odd is that it doesn't bomb out on us when the ASSERT is not
 there. That seems odd to me -- if the types get very large I'd expect the
 type checker to fail even in the absence of the ASSERT.

 I think I can explain this. The
 [https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/types/Coercion.hs;a883c1b7b08657102a2081b55c8fe68714d8bf73$1305
 unwrapNewTypeStepper] is protected by a
 [https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/types/TyCon.hs;a883c1b7b08657102a2081b55c8fe68714d8bf73$2062
 checkRecTc] which will cause an abort if the same newtype constructor is
 unwrapped 100 times. The difference I believe is due to laziness and
 sharing, it's easy to create an exponentially big type by repeated
 substitution into `(a, a)` and unless `a` is (deeply) forced at some point
 you can do it in sub-exponential time. So when `substTy` began to force it
 by computing the free variables for the sanity check the problem became
 visible.

 In other words the recursion check in `checkRecTc` didn't need to force
 the type to decide it was a loop, so it wasn't bothered by it growing
 exponentially (made possible by sharing and laziness) before.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11518#comment:6>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler