"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).
-
To fill in some context:
My original thought was that the fact that a tick cannot occur in a
RULEmay be itself a useful invariant to enforce (e.g. if nothing else, there is no reason to write such ticks to interface file). That being said, I'll admit I'm not entirely happy with the patch that resulted from option (2).Edited by Ben Gamari changed milestone to %8.10.2
mentioned in issue #18162 (closed)
marked this issue as related to #18162 (closed)
Yes, that is fair. Alright, I'll update.
So this update is still pending? Perhaps worth finishing, since @sgraf812 has now stumbled on it too?
mentioned in merge request !3187 (closed)
marked this issue as related to #18122 (closed)
mentioned in commit 1069e168
mentioned in commit 8cbfcac6
mentioned in commit 00967b02
mentioned in commit f9d20958
closed via commit dcd6bdcc
mentioned in commit dcd6bdcc
mentioned in commit 80a93ef5
mentioned in merge request !3392 (merged)
mentioned in commit a6befeb3
- Edited by Ben Gamari
