"Tick in rule" impossible error in 8.10.1-alpha2 using Megaparsec.
Summary
A parser I'm working on that uses Megaparsec (either 7.0.5 or 8.0.0) is failing to compile under the pre-release of 8.10.1 with an "impossible" error.
Steps to reproduce
I have stripped it down to the following:
module TickInRule where
import Control.Monad (void)
import Text.Megaparsec
import Text.Megaparsec.Char
foo :: String -> Parsec () String ()
foo s = do
manyTill (foo "a") (lookAhead $ void (string s) <|> eof)
void (string s)
(This parser doesn't make much sense of course, but I've removed everything not necessary for the error.)
I get this using ghc -O2 bad.hs:
[1 of 1] Compiling TickInRule ( bad.hs, bad.o )
ghc: panic! (the 'impossible' happened)
(GHC version 8.10.0.20191210:
Tick in rule
src<libraries/base/GHC/Base.hs:(1448,1)-(1453,15)>
src<libraries/base/Data/List/NonEmpty.hs:(187,1)-(190,51)>
src<libraries/base/GHC/Base.hs:(1403,1)-(1418,26)> lvl_s3lT
Call stack:
CallStack (from HasCallStack):
callStackDoc, called at compiler/utils/Outputable.hs:1179:37 in ghc:Outputable
pprPanic, called at compiler/specialise/Rules.hs:720:5 in ghc:Rules
Please report this as a GHC bug: https://www.haskell.org/ghc/reportabugOddly, factoring out the void part (let v = void (string s)) makes the error go away; indeed, so does factoring out just string s.
Using no optimization or even -O also results in no error.
This is as far as I've gotten.
Environment
- GHC version used: ghc-8.10.0.20191210-x86_64-deb9-linux-dwarf
Activity
added Tbug needs triage labels
Ahh, it looks like we have a source tick in the LHS of a rule. Given that we will look past source notes anyways, I think we should just strip source notes from the LHS when constructing the rule.
Edited by Ben Gamariadded Phigh compiler crash simplifier + 1 deleted label and removed needs triage label
-
A bit of tracing
diff --git a/compiler/specialise/Rules.hs b/compiler/specialise/Rules.hs index 72e293421c..ea3b2f051b 100644 --- a/compiler/specialise/Rules.hs +++ b/compiler/specialise/Rules.hs @@ -530,7 +530,8 @@ matchN :: InScopeEnv -- Fail if there are two few actual arguments from the target to match the template matchN (in_scope, id_unf) rule_name tmpl_vars tmpl_es target_es rhs - = do { rule_subst <- go init_menv emptyRuleSubst tmpl_es target_es + = pprTrace "Rules.matchN" (ppr rule_name $$ ppr tmpl_vars $$ ppr tmpl_es $$ ppr target_es $$ ppr rhs) $ + do { rule_subst <- go init_menv emptyRuleSubst tmpl_es target_es ; let (_, matched_es) = mapAccumL (lookup_tmpl rule_subst) (mkEmptyTCvSubst in_scope) $ tmpl_vars `zip` tmpl_vars1Reveals the following:
Rules.matchN SC:$weerr0 [sc_s3WT, sc_s3WU, sc_s3WV, sc_s3WW, sc_s3WX] [TrivialError @ [Char] @ () (I# sc_s3WT) sc_s3WU (Bin @ (ErrorItem (Token [Char])) sc_s3WV (src<hi.hs:9:49> lvl_s3l6) sc_s3WW sc_s3WX)] [TrivialError @ [Char] @ () (I# dt_Xp) lvl_s2Zq lvl_s2Zs] jump $s$weerr_s3WY sc_s3WT sc_s3WU sc_s3WV sc_s3WW sc_s3WX mentioned in issue #17623 (closed)
-
So the rule in question originated from SpecConstr. However, the rule created by SpecConstr does not contain any ticks. Specifically:
ruleInfoBinds ["SC:$weerr0" [2] ┊ ┊ ┊forall (sc_s3WT :: Int#) ┊ ┊ ┊ ┊ ┊ ┊ (sc_s3WU :: Maybe (ErrorItem (Token [Char]))) ┊ ┊ ┊ ┊ ┊ ┊ (sc_s3WV :: Int#) ┊ ┊ ┊ ┊ ┊ ┊ (sc_s3WW :: Set (ErrorItem (Token [Char]))) ┊ ┊ ┊ ┊ ┊ ┊ (sc_s3WX :: Set (ErrorItem (Token [Char]))). ┊ ┊ ┊ ┊$weerr_Xu (TrivialError ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ @ [Char] ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ @ () ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ (I# sc_s3WT) ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ sc_s3WU ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ (Bin ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊@ (ErrorItem (Token [Char])) sc_s3WV lvl_s3l9 sc_s3WW sc_s3WX)) ┊ ┊ ┊ ┊= jump $s$weerr_s3WY sc_s3WT sc_s3WU sc_s3WV sc_s3WW sc_s3WX]However, then CSE substitutes, introducing the tick:
substIdInfo Call stack: ┊ ┊ CallStack (from HasCallStack): ┊ ┊ ┊ callStackDoc, called at compiler/coreSyn/CoreSubst.hs:614:78 in ghc:CoreSubst ┊ ┊ ┊ substIdInfo, called at compiler/coreSyn/CoreSubst.hs:487:19 in ghc:CoreSubst ┊ ┊ ┊ substIdBndr, called at compiler/coreSyn/CoreSubst.hs:452:21 in ghc:CoreSubst ┊ ┊ ┊ substBndr, called at compiler/simplCore/CSE.hs:733:32 in ghc:CSEResulting in the rule that fails:
Rules.matchRule "SC:$weerr0" [2] ┊ ┊ forall (sc_s3WT :: Int#) ┊ ┊ ┊ ┊ ┊ ┊(sc_s3WU :: Maybe (ErrorItem (Token [Char]))) ┊ ┊ ┊ ┊ ┊ ┊(sc_s3WV :: Int#) ┊ ┊ ┊ ┊ ┊ ┊(sc_s3WW :: Set (ErrorItem (Token [Char]))) ┊ ┊ ┊ ┊ ┊ ┊(sc_s3WX :: Set (ErrorItem (Token [Char]))). ┊ ┊ ┊ $weerr_Xu (TrivialError ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊@ [Char] ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊@ () ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊(I# sc_s3WT) ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊sc_s3WU ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊(Bin ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ @ (ErrorItem (Token [Char])) ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ sc_s3WV ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ (src<hi.hs:9:49> lvl_s3l6) ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ sc_s3WW ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ sc_s3WX)) ┊ ┊ ┊ = jump $s$weerr_s3WY sc_s3WT sc_s3WU sc_s3WV sc_s3WW sc_s3WXEdited by Ben Gamari -
I suspect this is all a tricky interaction between SpecConstr's treatment of ticks and the simplifier.
Here is what happens: We start with:
let { lvl_s3l6 :: ErrorItem (Token [Char]) [LclId, Unf=Unf{Src=<vanilla>, TopLvl=False, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 20}] lvl_s3l6 = Text.Megaparsec.Error.Tokens @ (Token [Char]) (src<hi.hs:9:49> dt_s3lc) } in let { lvl_s2Zs :: Data.Set.Internal.Set (ErrorItem (Token [Char])) [LclId, Unf=Unf{Src=<vanilla>, TopLvl=False, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 50}] lvl_s2Zs = Data.Set.Internal.Bin @ (ErrorItem (Token [Char])) 1# lvl_s3l6 (Data.Set.Internal.Tip @ (ErrorItem (Token [Char]))) (Data.Set.Internal.Tip @ (ErrorItem (Token [Char]))) } in let { lvl_s3l9 :: ErrorItem (Token [Char]) [LclId, Unf=Unf{Src=<vanilla>, TopLvl=False, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 20}] lvl_s3l9 = Text.Megaparsec.Error.Tokens @ (Token [Char]) (src<hi.hs:9:49> dt_s3lc) } in ...Next
SpecConstrruns, producing a rule:"SC:$weerr0" [2] forall (sc_s3W0 :: Int#) (sc_s3W1 :: Int#) (sc_s3W2 :: Set (ErrorItem (Token [Char]))) (sc_s3W3 :: Set (ErrorItem (Token [Char]))). $weerr_Xu (TrivialError @ [Char] @ () (I# sc_s3W0) lvl_s2Zq (Bin @ (ErrorItem (Token [Char])) sc_s3W1 lvl_s3l6 sc_s3W2 sc_s3W3)) = jump $s$weerr_s3W9 sc_s3W0 sc_s3W1 sc_s3W2 sc_s3W3Note how the template is free in some binders (e.g.
lvl_s3l6) of the original program.Now CSE runs, notices that the RHSs of
lvl_s3l9andlvl_s3l6are identical, and rewrites the former. This gives us,let { lvl_s3l9 :: ErrorItem (Token [Char]) [LclId] lvl_s3l9 = src<hi.hs:9:49> lvl_s3l6 } inThe tick here arose because of CSE's treatment of floatable ticks: when CSE'ing it will strip off all floatable ticks, check for an equivalent subexpression in its environment (which ignores ticks), and, if one is found, replaces the old expression with the new one, wrapping it with the ticks it previously stripped.
Now the simplifier runs, looks at the
lvl_s3l9binding, and decides to unconditionally post-inline it. This introduceslvl_s3l9 ~> src<hi.hs:9:49> lvl_s3l6into the simplifier's variable substitution.Finally we eventually get around to simplifying
$weerr_Xu, the variable to which our SpecConstr rule is attached.simplRulesapplies the variable substitution to the rule's template, giving us:"SC:$weerr0" [2] forall (sc_s3WT :: Int#) (sc_s3WU :: Maybe (ErrorItem (Token [Char]))) (sc_s3WV :: Int#) (sc_s3WW :: Set (ErrorItem (Token [Char]))) (sc_s3WX :: Set (ErrorItem (Token [Char]))). $weerr_Xu (TrivialError @ [Char] @ () (I# sc_s3WT) sc_s3WU (Bin @ (ErrorItem (Token [Char])) sc_s3WV (src<hi.hs:9:49> lvl_s3l6) sc_s3WW sc_s3WX))Which the simplifier later stumbles upon in a later pass, spots the tick in the template, and panics.
There are clearly many interactions here. However, it's not entirely clear to me which step is wrong. Substituting in the rule is clearly reasonable. However, if the call-site specialised by SpecConstr had contained a tick at the time the call was specialised then the tick would have simply been dropped (see
argToPatandNote [Notes in call patterns]) when constructing the template.I can think of two possible ways in which the problem could be avoided:
- the rule matcher could just ignore ticks in templates, dropping the invariant that rule templates are devoid of ticks
-
substRuleandsimplRulescould drop ticks from the template after it substitutes, preserving the invariant
Edited by Ben Gamari mentioned in commit ccc45f02
mentioned in merge request !2387 (closed)
mentioned in commit a7355b6d
mentioned in commit b74fb28c
mentioned in commit 56b446d2
mentioned in commit 807c323c
assigned to @bgamari
I think I prefer option (1). We alrready have
match renv subst e1 (Tick t e2) | tickishFloatable t = match renv subst' e1 e2I think we could add
match renv subst (Tick t e1) e2 | tickishFloatable t = match renv subst e1 e2This has the same effect as your changes, but localised to the same place as ticks in the expression being matched, rather that scattered around
CoreSubst.-
I have updated !2387 (closed) to implement and document option (1).
