Simplifier loop?
In !3903 (closed) we tried to define catMaybes = mapMaybe id
to fix #18574 (closed) but it makes the simplifier loop.
Small reproducer:
{-# LANGUAGE NoImplicitPrelude #-}
module Test where
import GHC.Base (build, foldr, id, Maybe(..))
catMaybes :: [Maybe a] -> [a]
catMaybes = mapMaybe id
mapMaybe :: (a -> Maybe b) -> [a] -> [b]
mapMaybe _ [] = []
mapMaybe f (x:xs) =
let rs = mapMaybe f xs in
case f x of
Nothing -> rs
Just r -> r:rs
{-# NOINLINE [1] mapMaybe #-}
{-# RULES
"mapMaybe" [~1] forall f xs. mapMaybe f xs
= build (\c n -> foldr (mapMaybeFB c f) n xs)
"mapMaybeList" [1] forall f. foldr (mapMaybeFB (:) f) [] = mapMaybe f
#-}
{-# INLINE [0] mapMaybeFB #-} -- See Note [Inline FB functions] in GHC.List
mapMaybeFB :: (b -> r -> r) -> (a -> Maybe b) -> a -> r -> r
mapMaybeFB cons f x next = case f x of
Nothing -> next
Just r -> cons r next
Building it with -O -ddump-simpl-stats
with either GHC 8.8, 8.10 or HEAD's stage1 we get:
==================== FloatOut stats: ====================
0 Lets floated to top level; 0 Lets floated elsewhere; from 4 Lambda groups
Simplifier ticks exhausted
When trying UnfoldingDone id
To increase the limit, use -fsimpl-tick-factor=N (default 100).
If you need to increase the limit substantially, please file a
bug report and indicate the factor you needed.
If GHC was unable to complete compilation even with a very large factor
(a thousand or more), please consult the "Known bugs or infelicities"
section in the Users Guide before filing a report. There are a
few situations unlikely to occur in practical programs for which
simplifier non-termination has been judged acceptable.
Total ticks: 7082
1288 PreInlineUnconditionally
642 x_aol
642 ds_dnW
1 c_alt
1 n_alu
1 f_alv
1 g_aon
644 PostInlineUnconditionally
643 ds_dnV
1 rs_spy
1286 UnfoldingDone
643 mapMaybe
642 id
1 build
1 RuleFired 1 mapMaybeList
3863 BetaReduction
643 a_ams
643 b_amt
643 ds_dnV
642 a_aok
642 x_aol
642 ds_dnW
1 c_alt
1 n_alu
1 f_alv
1 b_amZ
1 a_anj
1 b_ano
1 a_aom
1 g_aon
I've tried to debug it and the simplifier seems to loop in GHC.Core.Opt.Simplify.simplLazyBind
. Enabling the commented pprTrace in it, we get:
simplLazyBind
mapMaybe mapMaybe
\ (@a_aoy)
(@b_aoz)
(ds_dpC :: a_aoy -> Maybe b_aoz) -- <-- "dpC" is here
(ds_dpD [Occ=Once1!] :: [a_aoy]) ->
case ds_dpD of {
[] -> [] @b_aoz;
: x_a9U [Occ=Once1] xs_a9V [Occ=Once2] ->
case ds_dpC x_a9U of {
Nothing ->
build
@b_aoz
(\ (@b_ap3)
(c_anw [Occ=Once1, OS=OneShot] :: b_aoz -> b_ap3 -> b_ap3)
(n_anx [Occ=Once1, OS=OneShot] :: b_ap3) ->
foldr
@a_aoy
@b_ap3
(mapMaybeFB @b_aoz @b_ap3 @a_aoy c_anw ds_dpC)
n_anx
xs_a9V);
Just r_ano [Occ=Once1] ->
: @b_aoz
r_ano
(build
@b_aoz
(\ (@b_ap3)
(c_anw [Occ=Once1, OS=OneShot] :: b_aoz -> b_ap3 -> b_ap3)
(n_anx [Occ=Once1, OS=OneShot] :: b_ap3) ->
foldr
@a_aoy
@b_ap3
(mapMaybeFB @b_aoz @b_ap3 @a_aoy c_anw ds_dpC)
n_anx
xs_a9V))
}
}
[]
simplLazyBind
catMaybes catMaybes
\ (@a_aoO) -> mapMaybe @(Maybe a_aoO) @a_aoO (id @(Maybe a_aoO))
[]
simplLazyBind
ds_dpC ds_dpC -- binders pre- and post-simplification
id @(Maybe a_aoO) -- RHS of "dpC" is "id"
[] -- subst env
simplLazyBind
ds_dpC ds_X3
ds_dpC -- RHS of "dpC" is now "dpC" itself. Seems wrong
[dpC :-> DoneEx id @(Maybe a_aoO)]
simplLazyBind
ds_dpC ds_X8
ds_dpC
[X1 :-> DoneId wild_X4, X2 :-> DoneId wild_X7, a9U :-> DoneId x_X5,
a9V :-> DoneId xs_X6, dpC :-> DoneEx id @(Maybe a_aoO),
dpD :-> ContEx xs_a9V]
simplLazyBind
ds_dpC ds_Xd
ds_dpC
[X1 :-> DoneId wild_X9, X2 :-> DoneId wild_Xc, a9U :-> DoneId x_Xa,
a9V :-> DoneId xs_Xb, dpC :-> DoneEx id @(Maybe a_aoO),
dpD :-> ContEx xs_a9V]
simplLazyBind
ds_dpC ds_Xi
ds_dpC
[X1 :-> DoneId wild_Xe, X2 :-> DoneId wild_Xh, a9U :-> DoneId x_Xf,
a9V :-> DoneId xs_Xg, dpC :-> DoneEx id @(Maybe a_aoO),
dpD :-> ContEx xs_a9V]
simplLazyBind
ds_dpC ds_Xn
ds_dpC
[X1 :-> DoneId wild_Xj, X2 :-> DoneId wild_Xm, a9U :-> DoneId x_Xk,
a9V :-> DoneId xs_Xl, dpC :-> DoneEx id @(Maybe a_aoO),
dpD :-> ContEx xs_a9V]
-- And so on until tick exhaustion