Opened 3 years ago

Closed 3 years ago

#13410 closed bug (fixed)

GHC HEAD regression: Template variable unbound in rewrite rule

Reported by: RyanGlScott Owned by: simonpj
Priority: highest Milestone: 8.2.1
Component: Compiler Version: 8.0.1
Keywords: JoinPoints, SpecConstr Cc: lukemauer, goldfire
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time crash or panic Test Case: simplCore/should_compile/T13410
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description (last modified by RyanGlScott)

hybrid-vectors-0.2.1 currently fails to build with GHC HEAD. I've attached a minimized repro file with no dependencies (it's 410 lines long, since I had to copy-paste a lot of code from vector in order to reproduce this). The attached file builds on GHC 7.10.3 and 8.0.2, but fails on GHC HEAD with this panic:

$ ~/Software/ghc2/inplace/bin/ghc-stage2 -O2 -fforce-recomp Bug.hs
[1 of 1] Compiling Data.Vector.Hybrid.Internal ( Bug.hs, Bug.o )

Bug.hs:389:10: warning: [-Wmissing-methods]
    • No explicit implementation for
        ‘gmbasicOverlaps’, ‘gmbasicInitialize’, and ‘gmbasicUnsafeRead’
    • In the instance declaration for ‘GMVector (MVector u v) (a, b)’
    |
389 | instance (GMVector u a, GMVector v b) => GMVector (MVector u v) (a, b) where
    |          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Bug.hs:407:10: warning: [-Wmissing-methods]
    • No explicit implementation for
        ‘gbasicUnsafeFreeze’, ‘gbasicUnsafeThaw’, ‘gbasicLength’,
        ‘gbasicUnsafeSlice’, and ‘gbasicUnsafeIndexM’
    • In the instance declaration for ‘GVector (Vector u v) (a, b)’
    |
407 | instance (GVector u a, GVector v b) => GVector (Vector u v) (a, b) where
    |          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ghc-stage2: panic! (the 'impossible' happened)
  (GHC version 8.3.20170310 for x86_64-unknown-linux):
        Template variable unbound in rewrite rule
  Variable: sc_s8FV
  Rule "SC:$j0"
  Rule bndrs: [sc_s8FV, sc_s8FW, sc_s8FX, sg_s8FY, sc_s8FU]
  LHS args: [sc_s8FU,
             (MV
                @ (GMutable u_a4oM)
                @ (GMutable v_a4oO)
                @ (PrimState (ST RealWorld))
                @ (a_a4oN, b_a4oP)
                @ a_a4oN
                @ b_a4oP
                @~ (<(a_a4oN, b_a4oP)>_N
                    :: ((a_a4oN, b_a4oP) :: *) ~# ((a_a4oN, b_a4oP) :: *))
                sc_s8FW
                sc_s8FX)
             `cast` (sg_s8FY
                     :: (MVector
                           (GMutable u_a4oM)
                           (GMutable v_a4oO)
                           (PrimState (ST RealWorld))
                           (a_a4oN, b_a4oP) :: *)
                        ~R#
                        (GMutable
                           (Vector u_a4oM v_a4oO) (PrimState (ST RealWorld)) c_a4oQ :: *))]
  Actual args: [sc_s8FS,
                wild_X3x
                `cast` (Sub
                          (Sym (D:R:GMutableVector[0] <u_a4oM>_N <v_a4oO>_N)) <PrimState
                                                                                 (ST
                                                                                    RealWorld)>_N (Sym
                                                                                                     cobox_a4Gz)
                        :: (MVector
                              (GMutable u_a4oM)
                              (GMutable v_a4oO)
                              (PrimState (ST RealWorld))
                              (a_a4oN, b_a4oP) :: *)
                           ~R#
                           (GMutable
                              (Vector u_a4oM v_a4oO) (PrimState (ST RealWorld)) c_a4oQ :: *))]
  Call stack:
      CallStack (from HasCallStack):
        prettyCurrentCallStack, called at compiler/utils/Outputable.hs:1191:58 in ghc:Outputable
        callStackDoc, called at compiler/utils/Outputable.hs:1195:37 in ghc:Outputable
        pprPanic, called at compiler/specialise/Rules.hs:579:19 in ghc:Rules

Some important things to note:

  • -O2 is required to trigger this bug; using -O1 or below works fine.
  • The problematic code is the Read (Vector u v c) instance at the very bottom. In particular, commenting out the last line readPrec = greadPrec makes the panic go away.
  • Moreover, there's a particular INLINE pragma in the GMVector (MVector u v) (a, b) instance that is critical to triggering the panic (it's on line 395; I've added a comment Removing this INLINE pragma makes it compile above it).

Attachments (1)

Bug.hs (12.6 KB) - added by RyanGlScott 3 years ago.

Download all attachments as: .zip

Change History (13)

Changed 3 years ago by RyanGlScott

Attachment: Bug.hs added

comment:1 Changed 3 years ago by RyanGlScott

Description: modified (diff)

comment:2 Changed 3 years ago by RyanGlScott

Keywords: JoinPoints added

Commit 8d5cf8bf584fd4849917c29d82dcf46ee75dd035 (Join points) introduced this regression.

comment:3 Changed 3 years ago by bgamari

Cc: lukemauer added

comment:4 Changed 3 years ago by RyanGlScott

I reduced the file from ~400 lines to ~150 lines:

{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}

module Data.Vector.Hybrid.Internal (Vector) where

import Control.Monad (liftM2)
import Data.Functor.Identity (Identity(..))
import GHC.ST (ST, runST)
import Text.Read (ReadPrec, readPrec)

-----

class Monad m => PrimMonad m where
  type PrimState m

instance PrimMonad (ST s) where
  type PrimState (ST s) = s

class GMVector v a where
  gmbasicLength      :: v s a -> Int
  gmbasicUnsafeSlice :: Int -> Int -> v s a -> v s a
  gmbasicUnsafeNew   :: PrimMonad m => Int -> m (v (PrimState m) a)
  gmbasicUnsafeWrite :: PrimMonad m => v (PrimState m) a -> Int -> a -> m ()

type family GMutable (v :: * -> *) :: * -> * -> *

class GMVector (GMutable v) a => GVector v a where
  gbasicUnsafeFreeze :: PrimMonad m => GMutable v (PrimState m) a -> m (v a)

data Step s a where
  Yield :: a -> s -> Step s a

instance Functor (Step s) where
  {-# INLINE fmap #-}
  fmap f (Yield x s) = Yield (f x) s

data Stream m a = forall s. Stream (s -> m (Step s a)) s
data Chunk v a = Chunk Int (forall m. (PrimMonad m, GVector v a) => GMutable v (PrimState m) a -> m ())
data New v a = New { newrun :: forall s. ST s (GMutable v s a) }
type MBundle m v a = Stream m (Chunk v a)
type Bundle v a = MBundle Identity v a

mbfromStream :: Monad m => Stream m a -> MBundle m v a
{-# INLINE mbfromStream #-}
mbfromStream (Stream step t) = Stream step' t
  where
    step' s = do r <- step s
                 return $ fmap (\x -> Chunk 1 (\v -> gmbasicUnsafeWrite v 0 x)) r

mbunsafeFromList :: Monad m => [a] -> MBundle m v a
{-# INLINE [1] mbunsafeFromList #-}
mbunsafeFromList xs = mbfromStream (sfromList xs)

blift :: Monad m => Bundle v a -> MBundle m v a
{-# INLINE [1] blift #-}
blift (Stream vstep t) = Stream (return . runIdentity . vstep) t

sfromList :: Monad m => [a] -> Stream m a
{-# INLINE sfromList #-}
sfromList zs = Stream step zs
  where
    step (x:xs) = return (Yield x xs)
    step _ = undefined

sfoldlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
{-# INLINE [1] sfoldlM #-}
sfoldlM m w (Stream step t) = foldlM_loop w t
  where
    foldlM_loop z s
      = do
          r <- step s
          case r of
            Yield x s' -> do { z' <- m z x; foldlM_loop z' s' }

gmvunstream :: (PrimMonad m, GVector v a)
            => Bundle v a -> m (GMutable v (PrimState m) a)
{-# INLINE [1] gmvunstream #-}
gmvunstream s = gmvmunstreamUnknown (blift s)

gmvmunstreamUnknown :: (PrimMonad m, GVector v a)
                    => MBundle m v a -> m (GMutable v (PrimState m) a)
{-# INLINE gmvmunstreamUnknown #-}
gmvmunstreamUnknown s
  = do
      v <- gmbasicUnsafeNew 0
      (_, _) <- sfoldlM copyChunk (v,0) s
      return undefined
  where
    {-# INLINE [0] copyChunk #-}
    copyChunk (v,i) (Chunk n f)
      = do
          let j = i+n
          v' <- if gmbasicLength v < j
                  then gmbasicUnsafeNew undefined
                  else return v
          f (gmbasicUnsafeSlice i n v')
          return (v',j)

newunstream :: GVector v a => Bundle v a -> New v a
{-# INLINE [1] newunstream #-}
newunstream s = s `seq` New (gmvunstream s)

gnew :: GVector v a => New v a -> v a
{-# INLINE [1] gnew #-}
gnew m = m `seq` runST (gbasicUnsafeFreeze =<< newrun m)

gunstream :: GVector v a => Bundle v a -> v a
{-# INLINE gunstream #-}
gunstream s = gnew (newunstream s)

gfromList :: GVector v a => [a] -> v a
{-# INLINE gfromList #-}
gfromList = gunstream . mbunsafeFromList

greadPrec :: (GVector v a, Read a) => ReadPrec (v a)
{-# INLINE greadPrec #-}
greadPrec = do
  xs <- readPrec
  return (gfromList xs)

-----

data MVector :: (* -> * -> *) -> (* -> * -> *) -> * -> * -> * where
  MV :: !(u s a) -> !(v s b) -> MVector u v s (a, b)

instance (GMVector u a, GMVector v b) => GMVector (MVector u v) (a, b) where
  gmbasicLength (MV ks _) = gmbasicLength ks
  gmbasicUnsafeSlice s e (MV ks vs) = MV (gmbasicUnsafeSlice s e ks) (gmbasicUnsafeSlice s e vs)

  gmbasicUnsafeNew n = liftM2 MV (gmbasicUnsafeNew n) (gmbasicUnsafeNew n)
  -- Removing this INLINE pragma makes it compile
  {-# INLINE gmbasicUnsafeNew #-}

  gmbasicUnsafeWrite (MV ks vs) n (k,v) = do
    gmbasicUnsafeWrite ks n k
    gmbasicUnsafeWrite vs n v

data Vector :: (* -> *) -> (* -> *) -> * -> *

type instance GMutable (Vector u v) = MVector (GMutable u) (GMutable v)

instance (GVector u a, GVector v b) => GVector (Vector u v) (a, b) where
  gbasicUnsafeFreeze = undefined

instance (GVector u a, GVector v b, Read a, Read b, c ~ (a, b)) => Read (Vector u v c) where
  readPrec = greadPrec

comment:5 Changed 3 years ago by RyanGlScott

Version: 8.18.0.1

Oh dear, there's actually a distinction between the attached program and the program in comment:4. The attached program compiles without issue on GHC 8.0.2 and earlier, but panics on GHC HEAD (post–join points). The program in comment:4, however, compiles without issue on GHC 7.10.3 and earlier, but panics on GHC 8.0.1, 8.0.2, and HEAD.

This isn't terribly surprising, as others have reported seeing this error on earlier versions of GHC, but AFAICT, no one was able to minimize the panic down to a single file until now. So the issue likely predates join points, but join points have made it easier to trigger in GHC HEAD.

I'll see if I can figure out what commit lead to the panic surfacing in the program in comment:4.

comment:6 Changed 3 years ago by RyanGlScott

Huh, the commit which caused the regression in comment:4 is 6746549772c5cc0ac66c0fce562f297f4d4b80a2 (Add kind equalities to GHC). What this means, I have no idea.

comment:7 Changed 3 years ago by RyanGlScott

Keywords: SpecConstr added

comment:8 Changed 3 years ago by George

Cc: goldfire added

comment:9 Changed 3 years ago by simonpj

Owner: set to simonpj

I know exactly what is happening here. Just starved of time to fix it -- and next week looks little better.

In brief: TyCoRep.substCoVarBndr is replacing occurrences of the binder with Refl in the LHS of a rule. Solution: mkCoVarCo should not replace varaibles with Refl; but optCoercion should do so instead.

comment:10 Changed 3 years ago by Simon Peyton Jones <simonpj@…>

In 8674883c/ghc:

Allow unbound Refl binders in a RULE

Trac #13410 was failing because we had a RULE with a binder
   (c :: t~t)
and the /occurrences/ of c on the LHS were being optimised to Refl,
leaving a binder that would not be filled in by matching the LHS
of the rule.

I flirted with trying to ensure that occurrences (c :: t~t) are
not optimised to Relf, but that turned out to be fragile; it was
being done, for good reasons, in multiple places, including
  - TyCoRep.substCoVarBndr
  - Simplify.simplCast
  - Corecion.mkCoVarCo

So I fixed it in one place by making Rules.matchN deal happily
with an unbound binder (c :: t~t).  Quite easy.  See "Coercion
variables" in Note [Unbound RULE binders] in Rules.

In addition, I needed to make CoreLint be happy with an bound
RULE binder that is a Relf coercion variable

In debugging this, I was perplexed that occurrences of a variable
(c :: t~t) mysteriously turned into Refl.  I found out how it
was happening, and decided to move it:

* In TyCoRep.substCoVarBndr, do not substitute Refl for a
  binder (c :: t~t).

* In mkCoVarCo do not optimise (c :: t~t) to Refl.

Instead, we do this optimisation in optCoercion (specifically
opt_co4) where, surprisingly, the optimisation was /not/
being done.  This has no effect on what programs compile;
it just moves a relatively-expensive optimisation to optCoercion,
where it seems more properly to belong.  It's actually not clear
to me which is really "better", but this way round is less
surprising.

One small simplifying refactoring

* Eliminate TyCoRep.substCoVarBndrCallback, which was only
  called locally.

comment:11 Changed 3 years ago by simonpj

Status: newmerge
Test Case: simplCore/should_compile/T13410

OK, done!

comment:12 Changed 3 years ago by bgamari

Resolution: fixed
Status: mergeclosed
Note: See TracTickets for help on using tickets.