1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
{-
(c) The University of Glasgow 2006
(c) The GRASP/AQUA Project, Glasgow University, 1992-1998
Check for recursive type constructors.
-}
{-# LANGUAGE CPP #-}
module GHC.Core.TyCon.RecWalk (
-- * Recursion breaking
RecTcChecker, initRecTc, defaultRecTcMaxBound,
setRecTcMaxBound, checkRecTc
) where
import GHC.Prelude
import GHC.Core.TyCon
import GHC.Core.TyCon.Env
{-
************************************************************************
* *
Walking over recursive TyCons
* *
************************************************************************
Note [Expanding newtypes and products]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
When expanding a type to expose a data-type constructor, we need to be
careful about newtypes, lest we fall into an infinite loop. Here are
the key examples:
newtype Id x = MkId x
newtype Fix f = MkFix (f (Fix f))
newtype T = MkT (T -> T)
Type Expansion
--------------------------
T T -> T
Fix Maybe Maybe (Fix Maybe)
Id (Id Int) Int
Fix Id NO NO NO
Notice that
* We can expand T, even though it's recursive.
* We can expand Id (Id Int), even though the Id shows up
twice at the outer level, because Id is non-recursive
So, when expanding, we keep track of when we've seen a recursive
newtype at outermost level; and bail out if we see it again.
We sometimes want to do the same for product types, so that the
strictness analyser doesn't unbox infinitely deeply.
More precisely, we keep a *count* of how many times we've seen it.
This is to account for
data instance T (a,b) = MkT (T a) (T b)
Then (#10482) if we have a type like
T (Int,(Int,(Int,(Int,Int))))
we can still unbox deeply enough during strictness analysis.
We have to treat T as potentially recursive, but it's still
good to be able to unwrap multiple layers.
The function that manages all this is checkRecTc.
-}
data RecTcChecker = RC !Int (TyConEnv Int)
-- The upper bound, and the number of times
-- we have encountered each TyCon
-- | Initialise a 'RecTcChecker' with 'defaultRecTcMaxBound'.
initRecTc :: RecTcChecker
initRecTc = RC defaultRecTcMaxBound emptyTyConEnv
-- | The default upper bound (100) for the number of times a 'RecTcChecker' is
-- allowed to encounter each 'TyCon'.
defaultRecTcMaxBound :: Int
defaultRecTcMaxBound = 100
-- Should we have a flag for this?
-- | Change the upper bound for the number of times a 'RecTcChecker' is allowed
-- to encounter each 'TyCon'.
setRecTcMaxBound :: Int -> RecTcChecker -> RecTcChecker
setRecTcMaxBound new_bound (RC _old_bound rec_nts) = RC new_bound rec_nts
checkRecTc :: RecTcChecker -> TyCon -> Maybe RecTcChecker
-- Nothing => Recursion detected
-- Just rec_tcs => Keep going
checkRecTc (RC bound rec_nts) tc
= case lookupTyConEnv rec_nts tc of
Just n | n >= bound -> Nothing
| otherwise -> Just (RC bound (extendTyConEnv rec_nts tc (n+1)))
Nothing -> Just (RC bound (extendTyConEnv rec_nts tc 1))
|