{-
(c) The University of Glasgow 2011


The deriving code for the Functor, Foldable, and Traversable classes
(equivalent to the code in TcGenDeriv, for other classes)
-}

{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE LambdaCase #-}

module TcGenFunctor (
        FFoldType(..), functorLikeTraverse,
        deepSubtypesContaining, foldDataConArgs,

        gen_Functor_binds, gen_Foldable_binds, gen_Traversable_binds
    ) where

import GhcPrelude

import Bag
import DataCon
import FastString
import GHC.Hs
import Panic
import PrelNames
import RdrName
import SrcLoc
import State
import TcGenDeriv
import TcType
import TyCon
import TyCoRep
import Type
import Util
import Var
import VarSet
import MkId (coerceId)
import TysWiredIn (true_RDR, false_RDR)

import Data.Maybe (catMaybes, isJust)

{-
************************************************************************
*                                                                      *
                        Functor instances

 see http://www.mail-archive.com/haskell-prime@haskell.org/msg02116.html

*                                                                      *
************************************************************************

For the data type:

  data T a = T1 Int a | T2 (T a)

We generate the instance:

  instance Functor T where
      fmap f (T1 b1 a) = T1 b1 (f a)
      fmap f (T2 ta)   = T2 (fmap f ta)

Notice that we don't simply apply 'fmap' to the constructor arguments.
Rather
  - Do nothing to an argument whose type doesn't mention 'a'
  - Apply 'f' to an argument of type 'a'
  - Apply 'fmap f' to other arguments
That's why we have to recurse deeply into the constructor argument types,
rather than just one level, as we typically do.

What about types with more than one type parameter?  In general, we only
derive Functor for the last position:

  data S a b = S1 [b] | S2 (a, T a b)
  instance Functor (S a) where
    fmap f (S1 bs)    = S1 (fmap f bs)
    fmap f (S2 (p,q)) = S2 (a, fmap f q)

However, we have special cases for
         - tuples
         - functions

More formally, we write the derivation of fmap code over type variable
'a for type 'b as ($fmap 'a 'b).  In this general notation the derived
instance for T is:

  instance Functor T where
      fmap f (T1 x1 x2) = T1 ($(fmap 'a 'b1) x1) ($(fmap 'a 'a) x2)
      fmap f (T2 x1)    = T2 ($(fmap 'a '(T a)) x1)

  $(fmap 'a 'b)          =  \x -> x     -- when b does not contain a
  $(fmap 'a 'a)          =  f
  $(fmap 'a '(b1,b2))    =  \x -> case x of (x1,x2) -> ($(fmap 'a 'b1) x1, $(fmap 'a 'b2) x2)
  $(fmap 'a '(T b1 b2))  =  fmap $(fmap 'a 'b2)   -- when a only occurs in the last parameter, b2
  $(fmap 'a '(b -> c))   =  \x b -> $(fmap 'a' 'c) (x ($(cofmap 'a 'b) b))

For functions, the type parameter 'a can occur in a contravariant position,
which means we need to derive a function like:

  cofmap :: (a -> b) -> (f b -> f a)

This is pretty much the same as $fmap, only without the $(cofmap 'a 'a) case:

  $(cofmap 'a 'b)          =  \x -> x     -- when b does not contain a
  $(cofmap 'a 'a)          =  error "type variable in contravariant position"
  $(cofmap 'a '(b1,b2))    =  \x -> case x of (x1,x2) -> ($(cofmap 'a 'b1) x1, $(cofmap 'a 'b2) x2)
  $(cofmap 'a '[b])        =  map $(cofmap 'a 'b)
  $(cofmap 'a '(T b1 b2))  =  fmap $(cofmap 'a 'b2)   -- when a only occurs in the last parameter, b2
  $(cofmap 'a '(b -> c))   =  \x b -> $(cofmap 'a' 'c) (x ($(fmap 'a 'c) b))

Note that the code produced by $(fmap _ _) is always a higher order function,
with type `(a -> b) -> (g a -> g b)` for some g. When we need to do pattern
matching on the type, this means create a lambda function (see the (,) case above).
The resulting code for fmap can look a bit weird, for example:

  data X a = X (a,Int)
  -- generated instance
  instance Functor X where
      fmap f (X x) = (\y -> case y of (x1,x2) -> X (f x1, (\z -> z) x2)) x

The optimizer should be able to simplify this code by simple inlining.

An older version of the deriving code tried to avoid these applied
lambda functions by producing a meta level function. But the function to
be mapped, `f`, is a function on the code level, not on the meta level,
so it was eta expanded to `\x -> [| f $x |]`. This resulted in too much eta expansion.
It is better to produce too many lambdas than to eta expand, see ticket #7436.
-}

gen_Functor_binds :: SrcSpan -> TyCon -> (LHsBinds GhcPs, BagDerivStuff)
-- When the argument is phantom, we can use  fmap _ = coerce
-- See Note [Phantom types with Functor, Foldable, and Traversable]
gen_Functor_binds :: SrcSpan -> TyCon -> (LHsBinds GhcPs, BagDerivStuff)
gen_Functor_binds SrcSpan
loc TyCon
tycon
  | Role
Phantom <- [Role] -> Role
forall a. [a] -> a
last (TyCon -> [Role]
tyConRoles TyCon
tycon)
  = (LHsBind GhcPs -> LHsBinds GhcPs
forall a. a -> Bag a
unitBag LHsBind GhcPs
fmap_bind, BagDerivStuff
forall a. Bag a
emptyBag)
  where
    fmap_name :: GenLocated SrcSpan RdrName
fmap_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName
forall l e. l -> e -> GenLocated l e
L SrcSpan
loc RdrName
fmap_RDR
    fmap_bind :: LHsBind GhcPs
fmap_bind = GenLocated SrcSpan RdrName
-> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsBind GhcPs
mkRdrFunBind GenLocated SrcSpan RdrName
fmap_name [LMatch GhcPs (LHsExpr GhcPs)]
fmap_eqns
    fmap_eqns :: [LMatch GhcPs (LHsExpr GhcPs)]
fmap_eqns = [HsMatchContext (NameOrRdrName (IdP GhcPs))
-> [LPat GhcPs] -> LHsExpr GhcPs -> LMatch GhcPs (LHsExpr GhcPs)
forall (p :: Pass) (body :: * -> *).
HsMatchContext (NameOrRdrName (IdP (GhcPass p)))
-> [LPat (GhcPass p)]
-> Located (body (GhcPass p))
-> LMatch (GhcPass p) (Located (body (GhcPass p)))
mkSimpleMatch HsMatchContext RdrName
HsMatchContext (NameOrRdrName (IdP GhcPs))
fmap_match_ctxt
                               [LPat GhcPs
nlWildPat]
                               LHsExpr GhcPs
coerce_Expr]
    fmap_match_ctxt :: HsMatchContext RdrName
fmap_match_ctxt = GenLocated SrcSpan RdrName -> HsMatchContext RdrName
forall id. Located id -> HsMatchContext id
mkPrefixFunRhs GenLocated SrcSpan RdrName
fmap_name

gen_Functor_binds SrcSpan
loc TyCon
tycon
  = ([LHsBind GhcPs] -> LHsBinds GhcPs
forall a. [a] -> Bag a
listToBag [LHsBind GhcPs
fmap_bind, LHsBind GhcPs
replace_bind], BagDerivStuff
forall a. Bag a
emptyBag)
  where
    data_cons :: [DataCon]
data_cons = TyCon -> [DataCon]
tyConDataCons TyCon
tycon
    fmap_name :: GenLocated SrcSpan RdrName
fmap_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName
forall l e. l -> e -> GenLocated l e
L SrcSpan
loc RdrName
fmap_RDR

    -- See Note [EmptyDataDecls with Functor, Foldable, and Traversable]
    fmap_bind :: LHsBind GhcPs
fmap_bind = Arity
-> (LHsExpr GhcPs -> LHsExpr GhcPs)
-> GenLocated SrcSpan RdrName
-> [LMatch GhcPs (LHsExpr GhcPs)]
-> LHsBind GhcPs
mkRdrFunBindEC Arity
2 LHsExpr GhcPs -> LHsExpr GhcPs
forall a. a -> a
id GenLocated SrcSpan RdrName
fmap_name [LMatch GhcPs (LHsExpr GhcPs)]
fmap_eqns
    fmap_match_ctxt :: HsMatchContext RdrName
fmap_match_ctxt = GenLocated SrcSpan RdrName -> HsMatchContext RdrName
forall id. Located id -> HsMatchContext id
mkPrefixFunRhs GenLocated SrcSpan RdrName
fmap_name

    fmap_eqn :: DataCon -> LMatch GhcPs (LHsExpr GhcPs)
fmap_eqn DataCon
con = (State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
 -> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs))
-> [RdrName]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
-> LMatch GhcPs (LHsExpr GhcPs)
forall a b c. (a -> b -> c) -> b -> a -> c
flip State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
-> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs)
forall s a. State s a -> s -> a
evalState [RdrName]
bs_RDRs (State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
 -> LMatch GhcPs (LHsExpr GhcPs))
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
-> LMatch GhcPs (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$
                     HsMatchContext RdrName
-> [LPat GhcPs]
-> DataCon
-> [LHsExpr GhcPs]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_for_con HsMatchContext RdrName
fmap_match_ctxt [LPat GhcPs
f_Pat] DataCon
con ([LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> State [RdrName] [LHsExpr GhcPs]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< State [RdrName] [LHsExpr GhcPs]
parts
      where
        parts :: State [RdrName] [LHsExpr GhcPs]
parts = [State [RdrName] (LHsExpr GhcPs)]
-> State [RdrName] [LHsExpr GhcPs]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence ([State [RdrName] (LHsExpr GhcPs)]
 -> State [RdrName] [LHsExpr GhcPs])
-> [State [RdrName] (LHsExpr GhcPs)]
-> State [RdrName] [LHsExpr GhcPs]
forall a b. (a -> b) -> a -> b
$ FFoldType (State [RdrName] (LHsExpr GhcPs))
-> DataCon -> [State [RdrName] (LHsExpr GhcPs)]
forall a. FFoldType a -> DataCon -> [a]
foldDataConArgs FFoldType (State [RdrName] (LHsExpr GhcPs))
ft_fmap DataCon
con

    fmap_eqns :: [LMatch GhcPs (LHsExpr GhcPs)]
fmap_eqns = (DataCon -> LMatch GhcPs (LHsExpr GhcPs))
-> [DataCon] -> [LMatch GhcPs (LHsExpr GhcPs)]
forall a b. (a -> b) -> [a] -> [b]
map DataCon -> LMatch GhcPs (LHsExpr GhcPs)
fmap_eqn [DataCon]
data_cons

    ft_fmap :: FFoldType (State [RdrName] (LHsExpr GhcPs))
    ft_fmap :: FFoldType (State [RdrName] (LHsExpr GhcPs))
ft_fmap = FT :: forall a.
a
-> a
-> a
-> (a -> a -> a)
-> (TyCon -> [a] -> a)
-> (Type -> a -> a)
-> a
-> (TcTyVar -> a -> a)
-> FFoldType a
FT { ft_triv :: State [RdrName] (LHsExpr GhcPs)
ft_triv = (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
 -> State [RdrName] (LHsExpr GhcPs))
-> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$ \LHsExpr GhcPs
x -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a. Monad m => a -> m a
return LHsExpr GhcPs
x
                   -- fmap f = \x -> x
                 , ft_var :: State [RdrName] (LHsExpr GhcPs)
ft_var  = LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a. Monad m => a -> m a
return LHsExpr GhcPs
f_Expr
                   -- fmap f = f
                 , ft_fun :: State [RdrName] (LHsExpr GhcPs)
-> State [RdrName] (LHsExpr GhcPs)
-> State [RdrName] (LHsExpr GhcPs)
ft_fun  = \State [RdrName] (LHsExpr GhcPs)
g State [RdrName] (LHsExpr GhcPs)
h -> do
                     LHsExpr GhcPs
gg <- State [RdrName] (LHsExpr GhcPs)
g
                     LHsExpr GhcPs
hh <- State [RdrName] (LHsExpr GhcPs)
h
                     (LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
mkSimpleLam2 ((LHsExpr GhcPs
  -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
 -> State [RdrName] (LHsExpr GhcPs))
-> (LHsExpr GhcPs
    -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$ \LHsExpr GhcPs
x LHsExpr GhcPs
b -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a. Monad m => a -> m a
return (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$
                       LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
nlHsApp LHsExpr GhcPs
hh (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
nlHsApp LHsExpr GhcPs
x (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
nlHsApp LHsExpr GhcPs
gg LHsExpr GhcPs
b))
                   -- fmap f = \x b -> h (x (g b))
                 , ft_tup :: TyCon
-> [State [RdrName] (LHsExpr GhcPs)]
-> State [RdrName] (LHsExpr GhcPs)
ft_tup = \TyCon
t [State [RdrName] (LHsExpr GhcPs)]
gs -> do
                     [LHsExpr GhcPs]
gg <- [State [RdrName] (LHsExpr GhcPs)]
-> State [RdrName] [LHsExpr GhcPs]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence [State [RdrName] (LHsExpr GhcPs)]
gs
                     (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
 -> State [RdrName] (LHsExpr GhcPs))
-> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$ ([LPat GhcPs]
 -> DataCon
 -> [LHsExpr GhcPs]
 -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> TyCon
-> [LHsExpr GhcPs]
-> LHsExpr GhcPs
-> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a.
Monad m =>
([LPat GhcPs]
 -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs)))
-> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs)
mkSimpleTupleCase (HsMatchContext RdrName
-> [LPat GhcPs]
-> DataCon
-> [LHsExpr GhcPs]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_for_con HsMatchContext RdrName
forall id. HsMatchContext id
CaseAlt) TyCon
t [LHsExpr GhcPs]
gg
                   -- fmap f = \x -> case x of (a1,a2,..) -> (g1 a1,g2 a2,..)
                 , ft_ty_app :: Type
-> State [RdrName] (LHsExpr GhcPs)
-> State [RdrName] (LHsExpr GhcPs)
ft_ty_app = \Type
_ State [RdrName] (LHsExpr GhcPs)
g -> LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
nlHsApp LHsExpr GhcPs
fmap_Expr (LHsExpr GhcPs -> LHsExpr GhcPs)
-> State [RdrName] (LHsExpr GhcPs)
-> State [RdrName] (LHsExpr GhcPs)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> State [RdrName] (LHsExpr GhcPs)
g
                   -- fmap f = fmap g
                 , ft_forall :: TcTyVar
-> State [RdrName] (LHsExpr GhcPs)
-> State [RdrName] (LHsExpr GhcPs)
ft_forall = \TcTyVar
_ State [RdrName] (LHsExpr GhcPs)
g -> State [RdrName] (LHsExpr GhcPs)
g
                 , ft_bad_app :: State [RdrName] (LHsExpr GhcPs)
ft_bad_app = String -> State [RdrName] (LHsExpr GhcPs)
forall a. String -> a
panic String
"in other argument in ft_fmap"
                 , ft_co_var :: State [RdrName] (LHsExpr GhcPs)
ft_co_var = String -> State [RdrName] (LHsExpr GhcPs)
forall a. String -> a
panic String
"contravariant in ft_fmap" }

    -- See Note [Deriving <$]
    replace_name :: GenLocated SrcSpan RdrName
replace_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName
forall l e. l -> e -> GenLocated l e
L SrcSpan
loc RdrName
replace_RDR

    -- See Note [EmptyDataDecls with Functor, Foldable, and Traversable]
    replace_bind :: LHsBind GhcPs
replace_bind = Arity
-> (LHsExpr GhcPs -> LHsExpr GhcPs)
-> GenLocated SrcSpan RdrName
-> [LMatch GhcPs (LHsExpr GhcPs)]
-> LHsBind GhcPs
mkRdrFunBindEC Arity
2 LHsExpr GhcPs -> LHsExpr GhcPs
forall a. a -> a
id GenLocated SrcSpan RdrName
replace_name [LMatch GhcPs (LHsExpr GhcPs)]
replace_eqns
    replace_match_ctxt :: HsMatchContext RdrName
replace_match_ctxt = GenLocated SrcSpan RdrName -> HsMatchContext RdrName
forall id. Located id -> HsMatchContext id
mkPrefixFunRhs GenLocated SrcSpan RdrName
replace_name

    replace_eqn :: DataCon -> LMatch GhcPs (LHsExpr GhcPs)
replace_eqn DataCon
con = (State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
 -> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs))
-> [RdrName]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
-> LMatch GhcPs (LHsExpr GhcPs)
forall a b c. (a -> b -> c) -> b -> a -> c
flip State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
-> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs)
forall s a. State s a -> s -> a
evalState [RdrName]
bs_RDRs (State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
 -> LMatch GhcPs (LHsExpr GhcPs))
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
-> LMatch GhcPs (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$
        HsMatchContext RdrName
-> [LPat GhcPs]
-> DataCon
-> [LHsExpr GhcPs]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_for_con HsMatchContext RdrName
replace_match_ctxt [LPat GhcPs
z_Pat] DataCon
con ([LHsExpr GhcPs] -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> State [RdrName] [LHsExpr GhcPs]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< State [RdrName] [LHsExpr GhcPs]
parts
      where
        parts :: State [RdrName] [LHsExpr GhcPs]
parts = (State [RdrName] Replacer -> State [RdrName] (LHsExpr GhcPs))
-> [State [RdrName] Replacer] -> State [RdrName] [LHsExpr GhcPs]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((Replacer -> LHsExpr GhcPs)
-> State [RdrName] Replacer -> State [RdrName] (LHsExpr GhcPs)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Replacer -> LHsExpr GhcPs
replace) ([State [RdrName] Replacer] -> State [RdrName] [LHsExpr GhcPs])
-> [State [RdrName] Replacer] -> State [RdrName] [LHsExpr GhcPs]
forall a b. (a -> b) -> a -> b
$ FFoldType (State [RdrName] Replacer)
-> DataCon -> [State [RdrName] Replacer]
forall a. FFoldType a -> DataCon -> [a]
foldDataConArgs FFoldType (State [RdrName] Replacer)
ft_replace DataCon
con

    replace_eqns :: [LMatch GhcPs (LHsExpr GhcPs)]
replace_eqns = (DataCon -> LMatch GhcPs (LHsExpr GhcPs))
-> [DataCon] -> [LMatch GhcPs (LHsExpr GhcPs)]
forall a b. (a -> b) -> [a] -> [b]
map DataCon -> LMatch GhcPs (LHsExpr GhcPs)
replace_eqn [DataCon]
data_cons

    ft_replace :: FFoldType (State [RdrName] Replacer)
    ft_replace :: FFoldType (State [RdrName] Replacer)
ft_replace = FT :: forall a.
a
-> a
-> a
-> (a -> a -> a)
-> (TyCon -> [a] -> a)
-> (Type -> a -> a)
-> a
-> (TcTyVar -> a -> a)
-> FFoldType a
FT { ft_triv :: State [RdrName] Replacer
ft_triv = (LHsExpr GhcPs -> Replacer)
-> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap LHsExpr GhcPs -> Replacer
Nested (State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer)
-> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer
forall a b. (a -> b) -> a -> b
$ (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
 -> State [RdrName] (LHsExpr GhcPs))
-> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$ \LHsExpr GhcPs
x -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a. Monad m => a -> m a
return LHsExpr GhcPs
x
                   -- (p <$) = \x -> x
                 , ft_var :: State [RdrName] Replacer
ft_var  = (LHsExpr GhcPs -> Replacer)
-> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap LHsExpr GhcPs -> Replacer
Immediate (State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer)
-> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer
forall a b. (a -> b) -> a -> b
$ (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
 -> State [RdrName] (LHsExpr GhcPs))
-> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$ \LHsExpr GhcPs
_ -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a. Monad m => a -> m a
return LHsExpr GhcPs
z_Expr
                   -- (p <$) = const p
                 , ft_fun :: State [RdrName] Replacer
-> State [RdrName] Replacer -> State [RdrName] Replacer
ft_fun  = \State [RdrName] Replacer
g State [RdrName] Replacer
h -> do
                     LHsExpr GhcPs
gg <- Replacer -> LHsExpr GhcPs
replace (Replacer -> LHsExpr GhcPs)
-> State [RdrName] Replacer -> State [RdrName] (LHsExpr GhcPs)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> State [RdrName] Replacer
g
                     LHsExpr GhcPs
hh <- Replacer -> LHsExpr GhcPs
replace (Replacer -> LHsExpr GhcPs)
-> State [RdrName] Replacer -> State [RdrName] (LHsExpr GhcPs)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> State [RdrName] Replacer
h
                     (LHsExpr GhcPs -> Replacer)
-> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap LHsExpr GhcPs -> Replacer
Nested (State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer)
-> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer
forall a b. (a -> b) -> a -> b
$ (LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
mkSimpleLam2 ((LHsExpr GhcPs
  -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
 -> State [RdrName] (LHsExpr GhcPs))
-> (LHsExpr GhcPs
    -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$ \LHsExpr GhcPs
x LHsExpr GhcPs
b -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a. Monad m => a -> m a
return (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$
                       LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
nlHsApp LHsExpr GhcPs
hh (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
nlHsApp LHsExpr GhcPs
x (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
nlHsApp LHsExpr GhcPs
gg LHsExpr GhcPs
b))
                   -- (<$) p = \x b -> h (x (g b))
                 , ft_tup :: TyCon -> [State [RdrName] Replacer] -> State [RdrName] Replacer
ft_tup = \TyCon
t [State [RdrName] Replacer]
gs -> do
                     [LHsExpr GhcPs]
gg <- (State [RdrName] Replacer -> State [RdrName] (LHsExpr GhcPs))
-> [State [RdrName] Replacer] -> State [RdrName] [LHsExpr GhcPs]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((Replacer -> LHsExpr GhcPs)
-> State [RdrName] Replacer -> State [RdrName] (LHsExpr GhcPs)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Replacer -> LHsExpr GhcPs
replace) [State [RdrName] Replacer]
gs
                     (LHsExpr GhcPs -> Replacer)
-> State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap LHsExpr GhcPs -> Replacer
Nested (State [RdrName] (LHsExpr GhcPs) -> State [RdrName] Replacer)
-> ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
    -> State [RdrName] (LHsExpr GhcPs))
-> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] Replacer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
 -> State [RdrName] Replacer)
-> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] Replacer
forall a b. (a -> b) -> a -> b
$
                          ([LPat GhcPs]
 -> DataCon
 -> [LHsExpr GhcPs]
 -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> TyCon
-> [LHsExpr GhcPs]
-> LHsExpr GhcPs
-> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a.
Monad m =>
([LPat GhcPs]
 -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs)))
-> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs)
mkSimpleTupleCase (HsMatchContext RdrName
-> [LPat GhcPs]
-> DataCon
-> [LHsExpr GhcPs]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_for_con HsMatchContext RdrName
forall id. HsMatchContext id
CaseAlt) TyCon
t [LHsExpr GhcPs]
gg
                   -- (p <$) = \x -> case x of (a1,a2,..) -> (g1 a1,g2 a2,..)
                 , ft_ty_app :: Type -> State [RdrName] Replacer -> State [RdrName] Replacer
ft_ty_app = \Type
_ State [RdrName] Replacer
gm -> do
                       Replacer
g <- State [RdrName] Replacer
gm
                       case Replacer
g of
                         Nested LHsExpr GhcPs
g' -> Replacer -> State [RdrName] Replacer
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Replacer -> State [RdrName] Replacer)
-> (LHsExpr GhcPs -> Replacer)
-> LHsExpr GhcPs
-> State [RdrName] Replacer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. LHsExpr GhcPs -> Replacer
Nested (LHsExpr GhcPs -> State [RdrName] Replacer)
-> LHsExpr GhcPs -> State [RdrName] Replacer
forall a b. (a -> b) -> a -> b
$
                                          LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
nlHsApp LHsExpr GhcPs
fmap_Expr (LHsExpr GhcPs -> LHsExpr GhcPs) -> LHsExpr GhcPs -> LHsExpr GhcPs
forall a b. (a -> b) -> a -> b
$ LHsExpr GhcPs
g'
                         Immediate LHsExpr GhcPs
_ -> Replacer -> State [RdrName] Replacer
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Replacer -> State [RdrName] Replacer)
-> (LHsExpr GhcPs -> Replacer)
-> LHsExpr GhcPs
-> State [RdrName] Replacer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. LHsExpr GhcPs -> Replacer
Nested (LHsExpr GhcPs -> State [RdrName] Replacer)
-> LHsExpr GhcPs -> State [RdrName] Replacer
forall a b. (a -> b) -> a -> b
$
                                          LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
nlHsApp LHsExpr GhcPs
replace_Expr LHsExpr GhcPs
z_Expr
                   -- (p <$) = fmap (p <$)
                 , ft_forall :: TcTyVar -> State [RdrName] Replacer -> State [RdrName] Replacer
ft_forall = \TcTyVar
_ State [RdrName] Replacer
g -> State [RdrName] Replacer
g
                 , ft_bad_app :: State [RdrName] Replacer
ft_bad_app = String -> State [RdrName] Replacer
forall a. String -> a
panic String
"in other argument in ft_replace"
                 , ft_co_var :: State [RdrName] Replacer
ft_co_var = String -> State [RdrName] Replacer
forall a. String -> a
panic String
"contravariant in ft_replace" }

    -- Con a1 a2 ... -> Con (f1 a1) (f2 a2) ...
    match_for_con :: HsMatchContext RdrName
                  -> [LPat GhcPs] -> DataCon -> [LHsExpr GhcPs]
                  -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
    match_for_con :: HsMatchContext RdrName
-> [LPat GhcPs]
-> DataCon
-> [LHsExpr GhcPs]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_for_con HsMatchContext RdrName
ctxt = HsMatchContext RdrName
-> (RdrName -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [LHsExpr GhcPs]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall (m :: * -> *).
Monad m =>
HsMatchContext RdrName
-> (RdrName -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [LHsExpr GhcPs]
-> m (LMatch GhcPs (LHsExpr GhcPs))
mkSimpleConMatch HsMatchContext RdrName
ctxt ((RdrName -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs))
 -> [LPat GhcPs]
 -> DataCon
 -> [LHsExpr GhcPs]
 -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> (RdrName -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [LHsExpr GhcPs]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall a b. (a -> b) -> a -> b
$
        \RdrName
con_name [LHsExpr GhcPs]
xs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a. Monad m => a -> m a
return (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$ IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs
forall (id :: Pass).
IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id)
nlHsApps RdrName
IdP GhcPs
con_name [LHsExpr GhcPs]
xs  -- Con x1 x2 ..

-- See Note [Deriving <$]
data Replacer = Immediate {Replacer -> LHsExpr GhcPs
replace :: LHsExpr GhcPs}
              | Nested {replace :: LHsExpr GhcPs}

{- Note [Deriving <$]
   ~~~~~~~~~~~~~~~~~~

We derive the definition of <$. Allowing this to take the default definition
can lead to memory leaks: mapping over a structure with a constant function can
fill the result structure with trivial thunks that retain the values from the
original structure. The simplifier seems to handle this all right for simple
types, but not for recursive ones. Consider

data Tree a = Bin !(Tree a) a !(Tree a) | Tip deriving Functor

-- fmap _ Tip = Tip
-- fmap f (Bin l v r) = Bin (fmap f l) (f v) (fmap f r)

Using the default definition of <$, we get (<$) x = fmap (\_ -> x) and that
simplifies no further. Why is that? `fmap` is defined recursively, so GHC
cannot inline it. The static argument transformation would turn the definition
into a non-recursive one

-- fmap f = go where
--   go Tip = Tip
--   go (Bin l v r) = Bin (go l) (f v) (go r)

which GHC could inline, producing an efficient definion of `<$`. But there are
several problems. First, GHC does not perform the static argument transformation
by default, even with -O2. Second, even when it does perform the static argument
transformation, it does so only when there are at least two static arguments,
which is not the case for fmap. Finally, when the type in question is
non-regular, such as

data Nesty a = Z a | S (Nesty a) (Nest (a, a))

the function argument is no longer (entirely) static, so the static argument
transformation will do nothing for us.

Applying the default definition of `<$` will produce a tree full of thunks that
look like ((\_ -> x) x0), which represents unnecessary thunk allocation and
also retention of the previous value, potentially leaking memory. Instead, we
derive <$ separately. Two aspects are different from fmap: the case of the
sought type variable (ft_var) and the case of a type application (ft_ty_app).
The interesting one is ft_ty_app. We have to distinguish two cases: the
"immediate" case where the type argument *is* the sought type variable, and
the "nested" case where the type argument *contains* the sought type variable.

The immediate case:

Suppose we have

data Imm a = Imm (F ... a)

Then we want to define

x <$ Imm q = Imm (x <$ q)

The nested case:

Suppose we have

data Nes a = Nes (F ... (G a))

Then we want to define

x <$ Nes q = Nes (fmap (x <$) q)

We use the Replacer type to tag whether the expression derived for applying
<$ to the last type variable was the ft_var case (immediate) or one of the
others (letting ft_forall pass through as usual).

We could, but do not, give tuples special treatment to improve efficiency
in some cases. Suppose we have

data Nest a = Z a | S (Nest (a,a))

The optimal definition would be

x <$ Z _ = Z x
x <$ S t = S ((x, x) <$ t)

which produces a result with maximal internal sharing. The reason we do not
attempt to treat this case specially is that we have no way to give
user-provided tuple-like types similar treatment. If the user changed the
definition to

data Pair a = Pair a a
data Nest a = Z a | S (Nest (Pair a))

they would experience a surprising degradation in performance. -}


{-
Utility functions related to Functor deriving.

Since several things use the same pattern of traversal, this is abstracted into functorLikeTraverse.
This function works like a fold: it makes a value of type 'a' in a bottom up way.
-}

-- Generic traversal for Functor deriving
-- See Note [FFoldType and functorLikeTraverse]
data FFoldType a      -- Describes how to fold over a Type in a functor like way
   = FT { FFoldType a -> a
ft_triv    :: a
          -- ^ Does not contain variable
        , FFoldType a -> a
ft_var     :: a
          -- ^ The variable itself
        , FFoldType a -> a
ft_co_var  :: a
          -- ^ The variable itself, contravariantly
        , FFoldType a -> a -> a -> a
ft_fun     :: a -> a -> a
          -- ^ Function type
        , FFoldType a -> TyCon -> [a] -> a
ft_tup     :: TyCon -> [a] -> a
          -- ^ Tuple type
        , FFoldType a -> Type -> a -> a
ft_ty_app  :: Type -> a -> a
          -- ^ Type app, variable only in last argument
        , FFoldType a -> a
ft_bad_app :: a
          -- ^ Type app, variable other than in last argument
        , FFoldType a -> TcTyVar -> a -> a
ft_forall  :: TcTyVar -> a -> a
          -- ^ Forall type
     }

functorLikeTraverse :: forall a.
                       TyVar         -- ^ Variable to look for
                    -> FFoldType a   -- ^ How to fold
                    -> Type          -- ^ Type to process
                    -> a
functorLikeTraverse :: TcTyVar -> FFoldType a -> Type -> a
functorLikeTraverse TcTyVar
var (FT { ft_triv :: forall a. FFoldType a -> a
ft_triv = a
caseTrivial,     ft_var :: forall a. FFoldType a -> a
ft_var = a
caseVar
                            , ft_co_var :: forall a. FFoldType a -> a
ft_co_var = a
caseCoVar,     ft_fun :: forall a. FFoldType a -> a -> a -> a
ft_fun = a -> a -> a
caseFun
                            , ft_tup :: forall a. FFoldType a -> TyCon -> [a] -> a
ft_tup = TyCon -> [a] -> a
caseTuple,        ft_ty_app :: forall a. FFoldType a -> Type -> a -> a
ft_ty_app = Type -> a -> a
caseTyApp
                            , ft_bad_app :: forall a. FFoldType a -> a
ft_bad_app = a
caseWrongArg, ft_forall :: forall a. FFoldType a -> TcTyVar -> a -> a
ft_forall = TcTyVar -> a -> a
caseForAll })
                    Type
ty
  = (a, Bool) -> a
forall a b. (a, b) -> a
fst (Bool -> Type -> (a, Bool)
go Bool
False Type
ty)
  where
    go :: Bool        -- Covariant or contravariant context
       -> Type
       -> (a, Bool)   -- (result of type a, does type contain var)

    go :: Bool -> Type -> (a, Bool)
go Bool
co Type
ty | Just Type
ty' <- Type -> Maybe Type
tcView Type
ty = Bool -> Type -> (a, Bool)
go Bool
co Type
ty'
    go Bool
co (TyVarTy    TcTyVar
v) | TcTyVar
v TcTyVar -> TcTyVar -> Bool
forall a. Eq a => a -> a -> Bool
== TcTyVar
var = (if Bool
co then a
caseCoVar else a
caseVar,Bool
True)
    go Bool
co (FunTy { ft_arg :: Type -> Type
ft_arg = Type
x, ft_res :: Type -> Type
ft_res = Type
y, ft_af :: Type -> AnonArgFlag
ft_af = AnonArgFlag
af })
       | AnonArgFlag
InvisArg <- AnonArgFlag
af = Bool -> Type -> (a, Bool)
go Bool
co Type
y
       | Bool
xc Bool -> Bool -> Bool
|| Bool
yc       = (a -> a -> a
caseFun a
xr a
yr,Bool
True)
       where (a
xr,Bool
xc) = Bool -> Type -> (a, Bool)
go (Bool -> Bool
not Bool
co) Type
x
             (a
yr,Bool
yc) = Bool -> Type -> (a, Bool)
go Bool
co       Type
y
    go Bool
co (AppTy    Type
x Type
y) | Bool
xc = (a
caseWrongArg,   Bool
True)
                         | Bool
yc = (Type -> a -> a
caseTyApp Type
x a
yr, Bool
True)
        where (a
_, Bool
xc) = Bool -> Type -> (a, Bool)
go Bool
co Type
x
              (a
yr,Bool
yc) = Bool -> Type -> (a, Bool)
go Bool
co Type
y
    go Bool
co ty :: Type
ty@(TyConApp TyCon
con [Type]
args)
       | Bool -> Bool
not ([Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
or [Bool]
xcs)     = (a
caseTrivial, Bool
False)   -- Variable does not occur
       -- At this point we know that xrs, xcs is not empty,
       -- and at least one xr is True
       | TyCon -> Bool
isTupleTyCon TyCon
con = (TyCon -> [a] -> a
caseTuple TyCon
con [a]
xrs, Bool
True)
       | [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
or ([Bool] -> [Bool]
forall a. [a] -> [a]
init [Bool]
xcs)    = (a
caseWrongArg, Bool
True)         -- T (..var..)    ty
       | Just (Type
fun_ty, Type
_) <- Type -> Maybe (Type, Type)
splitAppTy_maybe Type
ty         -- T (..no var..) ty
                          = (Type -> a -> a
caseTyApp Type
fun_ty ([a] -> a
forall a. [a] -> a
last [a]
xrs), Bool
True)
       | Bool
otherwise        = (a
caseWrongArg, Bool
True)   -- Non-decomposable (eg type function)
       where
         -- When folding over an unboxed tuple, we must explicitly drop the
         -- runtime rep arguments, or else GHC will generate twice as many
         -- variables in a unboxed tuple pattern match and expression as it
         -- actually needs. See #12399
         ([a]
xrs,[Bool]
xcs) = [(a, Bool)] -> ([a], [Bool])
forall a b. [(a, b)] -> ([a], [b])
unzip ((Type -> (a, Bool)) -> [Type] -> [(a, Bool)]
forall a b. (a -> b) -> [a] -> [b]
map (Bool -> Type -> (a, Bool)
go Bool
co) ([Type] -> [Type]
dropRuntimeRepArgs [Type]
args))
    go Bool
co (ForAllTy (Bndr TcTyVar
v ArgFlag
vis) Type
x)
       | ArgFlag -> Bool
isVisibleArgFlag ArgFlag
vis = String -> (a, Bool)
forall a. String -> a
panic String
"unexpected visible binder"
       | TcTyVar
v TcTyVar -> TcTyVar -> Bool
forall a. Eq a => a -> a -> Bool
/= TcTyVar
var Bool -> Bool -> Bool
&& Bool
xc       = (TcTyVar -> a -> a
caseForAll TcTyVar
v a
xr,Bool
True)
       where (a
xr,Bool
xc) = Bool -> Type -> (a, Bool)
go Bool
co Type
x

    go Bool
_ Type
_ = (a
caseTrivial,Bool
False)

-- Return all syntactic subterms of ty that contain var somewhere
-- These are the things that should appear in instance constraints
deepSubtypesContaining :: TyVar -> Type -> [TcType]
deepSubtypesContaining :: TcTyVar -> Type -> [Type]
deepSubtypesContaining TcTyVar
tv
  = TcTyVar -> FFoldType [Type] -> Type -> [Type]
forall a. TcTyVar -> FFoldType a -> Type -> a
functorLikeTraverse TcTyVar
tv
        (FT :: forall a.
a
-> a
-> a
-> (a -> a -> a)
-> (TyCon -> [a] -> a)
-> (Type -> a -> a)
-> a
-> (TcTyVar -> a -> a)
-> FFoldType a
FT { ft_triv :: [Type]
ft_triv = []
            , ft_var :: [Type]
ft_var = []
            , ft_fun :: [Type] -> [Type] -> [Type]
ft_fun = [Type] -> [Type] -> [Type]
forall a. [a] -> [a] -> [a]
(++)
            , ft_tup :: TyCon -> [[Type]] -> [Type]
ft_tup = \TyCon
_ [[Type]]
xs -> [[Type]] -> [Type]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[Type]]
xs
            , ft_ty_app :: Type -> [Type] -> [Type]
ft_ty_app = (:)
            , ft_bad_app :: [Type]
ft_bad_app = String -> [Type]
forall a. String -> a
panic String
"in other argument in deepSubtypesContaining"
            , ft_co_var :: [Type]
ft_co_var = String -> [Type]
forall a. String -> a
panic String
"contravariant in deepSubtypesContaining"
            , ft_forall :: TcTyVar -> [Type] -> [Type]
ft_forall = \TcTyVar
v [Type]
xs -> (Type -> Bool) -> [Type] -> [Type]
forall a. (a -> Bool) -> [a] -> [a]
filterOut ((TcTyVar
v TcTyVar -> VarSet -> Bool
`elemVarSet`) (VarSet -> Bool) -> (Type -> VarSet) -> Type -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Type -> VarSet
tyCoVarsOfType) [Type]
xs })


foldDataConArgs :: FFoldType a -> DataCon -> [a]
-- Fold over the arguments of the datacon
foldDataConArgs :: FFoldType a -> DataCon -> [a]
foldDataConArgs FFoldType a
ft DataCon
con
  = (Type -> a) -> [Type] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map Type -> a
foldArg (DataCon -> [Type]
dataConOrigArgTys DataCon
con)
  where
    foldArg :: Type -> a
foldArg
      = case Type -> Maybe TcTyVar
getTyVar_maybe ([Type] -> Type
forall a. [a] -> a
last (Type -> [Type]
tyConAppArgs (DataCon -> Type
dataConOrigResTy DataCon
con))) of
             Just TcTyVar
tv -> TcTyVar -> FFoldType a -> Type -> a
forall a. TcTyVar -> FFoldType a -> Type -> a
functorLikeTraverse TcTyVar
tv FFoldType a
ft
             Maybe TcTyVar
Nothing -> a -> Type -> a
forall a b. a -> b -> a
const (FFoldType a -> a
forall a. FFoldType a -> a
ft_triv FFoldType a
ft)
    -- If we are deriving Foldable for a GADT, there is a chance that the last
    -- type variable in the data type isn't actually a type variable at all.
    -- (for example, this can happen if the last type variable is refined to
    -- be a concrete type such as Int). If the last type variable is refined
    -- to be a specific type, then getTyVar_maybe will return Nothing.
    -- See Note [DeriveFoldable with ExistentialQuantification]
    --
    -- The kind checks have ensured the last type parameter is of kind *.

-- Make a HsLam using a fresh variable from a State monad
mkSimpleLam :: (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
            -> State [RdrName] (LHsExpr GhcPs)
-- (mkSimpleLam fn) returns (\x. fn(x))
mkSimpleLam :: (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
mkSimpleLam LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
lam =
    State [RdrName] [RdrName]
forall s. State s s
get State [RdrName] [RdrName]
-> ([RdrName] -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
      RdrName
n:[RdrName]
names -> do
        [RdrName] -> State [RdrName] ()
forall s. s -> State s ()
put [RdrName]
names
        LHsExpr GhcPs
body <- LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
lam (IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
n)
        LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a. Monad m => a -> m a
return ([LPat GhcPs] -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (p :: Pass).
(XMG (GhcPass p) (LHsExpr (GhcPass p)) ~ NoExtField) =>
[LPat (GhcPass p)] -> LHsExpr (GhcPass p) -> LHsExpr (GhcPass p)
mkHsLam [IdP GhcPs -> LPat GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LPat (GhcPass id)
nlVarPat RdrName
IdP GhcPs
n] LHsExpr GhcPs
body)
      [RdrName]
_ -> String -> State [RdrName] (LHsExpr GhcPs)
forall a. String -> a
panic String
"mkSimpleLam"

mkSimpleLam2 :: (LHsExpr GhcPs -> LHsExpr GhcPs
             -> State [RdrName] (LHsExpr GhcPs))
             -> State [RdrName] (LHsExpr GhcPs)
mkSimpleLam2 :: (LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
mkSimpleLam2 LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
lam =
    State [RdrName] [RdrName]
forall s. State s s
get State [RdrName] [RdrName]
-> ([RdrName] -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
      RdrName
n1:RdrName
n2:[RdrName]
names -> do
        [RdrName] -> State [RdrName] ()
forall s. s -> State s ()
put [RdrName]
names
        LHsExpr GhcPs
body <- LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
lam (IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
n1) (IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
n2)
        LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a. Monad m => a -> m a
return ([LPat GhcPs] -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (p :: Pass).
(XMG (GhcPass p) (LHsExpr (GhcPass p)) ~ NoExtField) =>
[LPat (GhcPass p)] -> LHsExpr (GhcPass p) -> LHsExpr (GhcPass p)
mkHsLam [IdP GhcPs -> LPat GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LPat (GhcPass id)
nlVarPat RdrName
IdP GhcPs
n1,IdP GhcPs -> LPat GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LPat (GhcPass id)
nlVarPat RdrName
IdP GhcPs
n2] LHsExpr GhcPs
body)
      [RdrName]
_ -> String -> State [RdrName] (LHsExpr GhcPs)
forall a. String -> a
panic String
"mkSimpleLam2"

-- "Con a1 a2 a3 -> fold [x1 a1, x2 a2, x3 a3]"
--
-- @mkSimpleConMatch fold extra_pats con insides@ produces a match clause in
-- which the LHS pattern-matches on @extra_pats@, followed by a match on the
-- constructor @con@ and its arguments. The RHS folds (with @fold@) over @con@
-- and its arguments, applying an expression (from @insides@) to each of the
-- respective arguments of @con@.
mkSimpleConMatch :: Monad m => HsMatchContext RdrName
                 -> (RdrName -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs))
                 -> [LPat GhcPs]
                 -> DataCon
                 -> [LHsExpr GhcPs]
                 -> m (LMatch GhcPs (LHsExpr GhcPs))
mkSimpleConMatch :: HsMatchContext RdrName
-> (RdrName -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [LHsExpr GhcPs]
-> m (LMatch GhcPs (LHsExpr GhcPs))
mkSimpleConMatch HsMatchContext RdrName
ctxt RdrName -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs)
fold [LPat GhcPs]
extra_pats DataCon
con [LHsExpr GhcPs]
insides = do
    let con_name :: RdrName
con_name = DataCon -> RdrName
forall thing. NamedThing thing => thing -> RdrName
getRdrName DataCon
con
    let vars_needed :: [RdrName]
vars_needed = [LHsExpr GhcPs] -> [RdrName] -> [RdrName]
forall b a. [b] -> [a] -> [a]
takeList [LHsExpr GhcPs]
insides [RdrName]
as_RDRs
    let bare_pat :: LPat GhcPs
bare_pat = RdrName -> [RdrName] -> LPat GhcPs
nlConVarPat RdrName
con_name [RdrName]
vars_needed
    let pat :: Located (Pat GhcPs)
pat = if [RdrName] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [RdrName]
vars_needed
          then Located (Pat GhcPs)
LPat GhcPs
bare_pat
          else LPat GhcPs -> LPat GhcPs
forall (name :: Pass). LPat (GhcPass name) -> LPat (GhcPass name)
nlParPat LPat GhcPs
bare_pat
    LHsExpr GhcPs
rhs <- RdrName -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs)
fold RdrName
con_name
                ((LHsExpr GhcPs -> RdrName -> LHsExpr GhcPs)
-> [LHsExpr GhcPs] -> [RdrName] -> [LHsExpr GhcPs]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (\LHsExpr GhcPs
i RdrName
v -> LHsExpr GhcPs
i LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
`nlHsApp` IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
v) [LHsExpr GhcPs]
insides [RdrName]
vars_needed)
    LMatch GhcPs (LHsExpr GhcPs) -> m (LMatch GhcPs (LHsExpr GhcPs))
forall (m :: * -> *) a. Monad m => a -> m a
return (LMatch GhcPs (LHsExpr GhcPs) -> m (LMatch GhcPs (LHsExpr GhcPs)))
-> LMatch GhcPs (LHsExpr GhcPs) -> m (LMatch GhcPs (LHsExpr GhcPs))
forall a b. (a -> b) -> a -> b
$ HsMatchContext (NameOrRdrName (IdP GhcPs))
-> [LPat GhcPs]
-> LHsExpr GhcPs
-> Located (HsLocalBinds GhcPs)
-> LMatch GhcPs (LHsExpr GhcPs)
forall (p :: Pass).
HsMatchContext (NameOrRdrName (IdP (GhcPass p)))
-> [LPat (GhcPass p)]
-> LHsExpr (GhcPass p)
-> Located (HsLocalBinds (GhcPass p))
-> LMatch (GhcPass p) (LHsExpr (GhcPass p))
mkMatch HsMatchContext RdrName
HsMatchContext (NameOrRdrName (IdP GhcPs))
ctxt ([Located (Pat GhcPs)]
[LPat GhcPs]
extra_pats [Located (Pat GhcPs)]
-> [Located (Pat GhcPs)] -> [Located (Pat GhcPs)]
forall a. [a] -> [a] -> [a]
++ [Located (Pat GhcPs)
pat]) LHsExpr GhcPs
rhs
                     (SrcSpanLess (Located (HsLocalBinds GhcPs))
-> Located (HsLocalBinds GhcPs)
forall a. HasSrcSpan a => SrcSpanLess a -> a
noLoc SrcSpanLess (Located (HsLocalBinds GhcPs))
forall (a :: Pass) (b :: Pass).
HsLocalBindsLR (GhcPass a) (GhcPass b)
emptyLocalBinds)

-- "Con a1 a2 a3 -> fmap (\b2 -> Con a1 b2 a3) (traverse f a2)"
--
-- @mkSimpleConMatch2 fold extra_pats con insides@ behaves very similarly to
-- 'mkSimpleConMatch', with two key differences:
--
-- 1. @insides@ is a @[Maybe (LHsExpr RdrName)]@ instead of a
--    @[LHsExpr RdrName]@. This is because it filters out the expressions
--    corresponding to arguments whose types do not mention the last type
--    variable in a derived 'Foldable' or 'Traversable' instance (i.e., the
--    'Nothing' elements of @insides@).
--
-- 2. @fold@ takes an expression as its first argument instead of a
--    constructor name. This is because it uses a specialized
--    constructor function expression that only takes as many parameters as
--    there are argument types that mention the last type variable.
--
-- See Note [Generated code for DeriveFoldable and DeriveTraversable]
mkSimpleConMatch2 :: Monad m
                  => HsMatchContext RdrName
                  -> (LHsExpr GhcPs -> [LHsExpr GhcPs]
                                      -> m (LHsExpr GhcPs))
                  -> [LPat GhcPs]
                  -> DataCon
                  -> [Maybe (LHsExpr GhcPs)]
                  -> m (LMatch GhcPs (LHsExpr GhcPs))
mkSimpleConMatch2 :: HsMatchContext RdrName
-> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> m (LMatch GhcPs (LHsExpr GhcPs))
mkSimpleConMatch2 HsMatchContext RdrName
ctxt LHsExpr GhcPs -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs)
fold [LPat GhcPs]
extra_pats DataCon
con [Maybe (LHsExpr GhcPs)]
insides = do
    let con_name :: RdrName
con_name = DataCon -> RdrName
forall thing. NamedThing thing => thing -> RdrName
getRdrName DataCon
con
        vars_needed :: [RdrName]
vars_needed = [Maybe (LHsExpr GhcPs)] -> [RdrName] -> [RdrName]
forall b a. [b] -> [a] -> [a]
takeList [Maybe (LHsExpr GhcPs)]
insides [RdrName]
as_RDRs
        pat :: LPat GhcPs
pat = RdrName -> [RdrName] -> LPat GhcPs
nlConVarPat RdrName
con_name [RdrName]
vars_needed
        -- Make sure to zip BEFORE invoking catMaybes. We want the variable
        -- indicies in each expression to match up with the argument indices
        -- in con_expr (defined below).
        exps :: [LHsExpr GhcPs]
exps = [Maybe (LHsExpr GhcPs)] -> [LHsExpr GhcPs]
forall a. [Maybe a] -> [a]
catMaybes ([Maybe (LHsExpr GhcPs)] -> [LHsExpr GhcPs])
-> [Maybe (LHsExpr GhcPs)] -> [LHsExpr GhcPs]
forall a b. (a -> b) -> a -> b
$ (Maybe (LHsExpr GhcPs) -> RdrName -> Maybe (LHsExpr GhcPs))
-> [Maybe (LHsExpr GhcPs)] -> [RdrName] -> [Maybe (LHsExpr GhcPs)]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (\Maybe (LHsExpr GhcPs)
i RdrName
v -> (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
`nlHsApp` IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
v) (LHsExpr GhcPs -> LHsExpr GhcPs)
-> Maybe (LHsExpr GhcPs) -> Maybe (LHsExpr GhcPs)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe (LHsExpr GhcPs)
i)
                                   [Maybe (LHsExpr GhcPs)]
insides [RdrName]
vars_needed
        -- An element of argTysTyVarInfo is True if the constructor argument
        -- with the same index has a type which mentions the last type
        -- variable.
        argTysTyVarInfo :: [Bool]
argTysTyVarInfo = (Maybe (LHsExpr GhcPs) -> Bool)
-> [Maybe (LHsExpr GhcPs)] -> [Bool]
forall a b. (a -> b) -> [a] -> [b]
map Maybe (LHsExpr GhcPs) -> Bool
forall a. Maybe a -> Bool
isJust [Maybe (LHsExpr GhcPs)]
insides
        ([LHsExpr GhcPs]
asWithTyVar, [LHsExpr GhcPs]
asWithoutTyVar) = [Bool] -> [LHsExpr GhcPs] -> ([LHsExpr GhcPs], [LHsExpr GhcPs])
forall a. [Bool] -> [a] -> ([a], [a])
partitionByList [Bool]
argTysTyVarInfo [LHsExpr GhcPs]
as_Vars

        con_expr :: LHsExpr GhcPs
con_expr
          | [LHsExpr GhcPs] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [LHsExpr GhcPs]
asWithTyVar = IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs
forall (id :: Pass).
IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id)
nlHsApps RdrName
IdP GhcPs
con_name [LHsExpr GhcPs]
asWithoutTyVar
          | Bool
otherwise =
              let bs :: [RdrName]
bs   = [Bool] -> [RdrName] -> [RdrName]
forall a. [Bool] -> [a] -> [a]
filterByList  [Bool]
argTysTyVarInfo [RdrName]
bs_RDRs
                  vars :: [LHsExpr GhcPs]
vars = [Bool] -> [LHsExpr GhcPs] -> [LHsExpr GhcPs] -> [LHsExpr GhcPs]
forall a. [Bool] -> [a] -> [a] -> [a]
filterByLists [Bool]
argTysTyVarInfo [LHsExpr GhcPs]
bs_Vars [LHsExpr GhcPs]
as_Vars
              in [LPat GhcPs] -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (p :: Pass).
(XMG (GhcPass p) (LHsExpr (GhcPass p)) ~ NoExtField) =>
[LPat (GhcPass p)] -> LHsExpr (GhcPass p) -> LHsExpr (GhcPass p)
mkHsLam ((RdrName -> Located (Pat GhcPs))
-> [RdrName] -> [Located (Pat GhcPs)]
forall a b. (a -> b) -> [a] -> [b]
map RdrName -> Located (Pat GhcPs)
forall (id :: Pass). IdP (GhcPass id) -> LPat (GhcPass id)
nlVarPat [RdrName]
bs) (IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs
forall (id :: Pass).
IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id)
nlHsApps RdrName
IdP GhcPs
con_name [LHsExpr GhcPs]
vars)

    LHsExpr GhcPs
rhs <- LHsExpr GhcPs -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs)
fold LHsExpr GhcPs
con_expr [LHsExpr GhcPs]
exps
    LMatch GhcPs (LHsExpr GhcPs) -> m (LMatch GhcPs (LHsExpr GhcPs))
forall (m :: * -> *) a. Monad m => a -> m a
return (LMatch GhcPs (LHsExpr GhcPs) -> m (LMatch GhcPs (LHsExpr GhcPs)))
-> LMatch GhcPs (LHsExpr GhcPs) -> m (LMatch GhcPs (LHsExpr GhcPs))
forall a b. (a -> b) -> a -> b
$ HsMatchContext (NameOrRdrName (IdP GhcPs))
-> [LPat GhcPs]
-> LHsExpr GhcPs
-> Located (HsLocalBinds GhcPs)
-> LMatch GhcPs (LHsExpr GhcPs)
forall (p :: Pass).
HsMatchContext (NameOrRdrName (IdP (GhcPass p)))
-> [LPat (GhcPass p)]
-> LHsExpr (GhcPass p)
-> Located (HsLocalBinds (GhcPass p))
-> LMatch (GhcPass p) (LHsExpr (GhcPass p))
mkMatch HsMatchContext RdrName
HsMatchContext (NameOrRdrName (IdP GhcPs))
ctxt ([Located (Pat GhcPs)]
[LPat GhcPs]
extra_pats [Located (Pat GhcPs)]
-> [Located (Pat GhcPs)] -> [Located (Pat GhcPs)]
forall a. [a] -> [a] -> [a]
++ [Located (Pat GhcPs)
LPat GhcPs
pat]) LHsExpr GhcPs
rhs
                     (SrcSpanLess (Located (HsLocalBinds GhcPs))
-> Located (HsLocalBinds GhcPs)
forall a. HasSrcSpan a => SrcSpanLess a -> a
noLoc SrcSpanLess (Located (HsLocalBinds GhcPs))
forall (a :: Pass) (b :: Pass).
HsLocalBindsLR (GhcPass a) (GhcPass b)
emptyLocalBinds)

-- "case x of (a1,a2,a3) -> fold [x1 a1, x2 a2, x3 a3]"
mkSimpleTupleCase :: Monad m => ([LPat GhcPs] -> DataCon -> [a]
                                 -> m (LMatch GhcPs (LHsExpr GhcPs)))
                  -> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs)
mkSimpleTupleCase :: ([LPat GhcPs]
 -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs)))
-> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs)
mkSimpleTupleCase [LPat GhcPs] -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs))
match_for_con TyCon
tc [a]
insides LHsExpr GhcPs
x
  = do { let data_con :: DataCon
data_con = TyCon -> DataCon
tyConSingleDataCon TyCon
tc
       ; LMatch GhcPs (LHsExpr GhcPs)
match <- [LPat GhcPs] -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs))
match_for_con [] DataCon
data_con [a]
insides
       ; LHsExpr GhcPs -> m (LHsExpr GhcPs)
forall (m :: * -> *) a. Monad m => a -> m a
return (LHsExpr GhcPs -> m (LHsExpr GhcPs))
-> LHsExpr GhcPs -> m (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$ LHsExpr GhcPs -> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsExpr GhcPs
nlHsCase LHsExpr GhcPs
x [LMatch GhcPs (LHsExpr GhcPs)
match] }

{-
************************************************************************
*                                                                      *
                        Foldable instances

 see http://www.mail-archive.com/haskell-prime@haskell.org/msg02116.html

*                                                                      *
************************************************************************

Deriving Foldable instances works the same way as Functor instances,
only Foldable instances are not possible for function types at all.
Given (data T a = T a a (T a) deriving Foldable), we get:

  instance Foldable T where
      foldr f z (T x1 x2 x3) =
        $(foldr 'a 'a) x1 ( $(foldr 'a 'a) x2 ( $(foldr 'a '(T a)) x3 z ) )

-XDeriveFoldable is different from -XDeriveFunctor in that it filters out
arguments to the constructor that would produce useless code in a Foldable
instance. For example, the following datatype:

  data Foo a = Foo Int a Int deriving Foldable

would have the following generated Foldable instance:

  instance Foldable Foo where
    foldr f z (Foo x1 x2 x3) = $(foldr 'a 'a) x2

since neither of the two Int arguments are folded over.

The cases are:

  $(foldr 'a 'a)         =  f
  $(foldr 'a '(b1,b2))   =  \x z -> case x of (x1,x2) -> $(foldr 'a 'b1) x1 ( $(foldr 'a 'b2) x2 z )
  $(foldr 'a '(T b1 b2)) =  \x z -> foldr $(foldr 'a 'b2) z x  -- when a only occurs in the last parameter, b2

Note that the arguments to the real foldr function are the wrong way around,
since (f :: a -> b -> b), while (foldr f :: b -> t a -> b).

One can envision a case for types that don't contain the last type variable:

  $(foldr 'a 'b)         =  \x z -> z     -- when b does not contain a

But this case will never materialize, since the aforementioned filtering
removes all such types from consideration.
See Note [Generated code for DeriveFoldable and DeriveTraversable].

Foldable instances differ from Functor and Traversable instances in that
Foldable instances can be derived for data types in which the last type
variable is existentially quantified. In particular, if the last type variable
is refined to a more specific type in a GADT:

  data GADT a where
      G :: a ~ Int => a -> G Int

then the deriving machinery does not attempt to check that the type a contains
Int, since it is not syntactically equal to a type variable. That is, the
derived Foldable instance for GADT is:

  instance Foldable GADT where
      foldr _ z (GADT _) = z

See Note [DeriveFoldable with ExistentialQuantification].

Note [Deriving null]
~~~~~~~~~~~~~~~~~~~~

In some cases, deriving the definition of 'null' can produce much better
results than the default definition. For example, with

  data SnocList a = Nil | Snoc (SnocList a) a

the default definition of 'null' would walk the entire spine of a
nonempty snoc-list before concluding that it is not null. But looking at
the Snoc constructor, we can immediately see that it contains an 'a', and
so 'null' can return False immediately if it matches on Snoc. When we
derive 'null', we keep track of things that cannot be null. The interesting
case is type application. Given

  data Wrap a = Wrap (Foo (Bar a))

we use

  null (Wrap fba) = all null fba

but if we see

  data Wrap a = Wrap (Foo a)

we can just use

  null (Wrap fa) = null fa

Indeed, we allow this to happen even for tuples:

  data Wrap a = Wrap (Foo (a, Int))

produces

  null (Wrap fa) = null fa

As explained in Note [Deriving <$], giving tuples special performance treatment
could surprise users if they switch to other types, but Ryan Scott seems to
think it's okay to do it for now.
-}

gen_Foldable_binds :: SrcSpan -> TyCon -> (LHsBinds GhcPs, BagDerivStuff)
-- When the parameter is phantom, we can use foldMap _ _ = mempty
-- See Note [Phantom types with Functor, Foldable, and Traversable]
gen_Foldable_binds :: SrcSpan -> TyCon -> (LHsBinds GhcPs, BagDerivStuff)
gen_Foldable_binds SrcSpan
loc TyCon
tycon
  | Role
Phantom <- [Role] -> Role
forall a. [a] -> a
last (TyCon -> [Role]
tyConRoles TyCon
tycon)
  = (LHsBind GhcPs -> LHsBinds GhcPs
forall a. a -> Bag a
unitBag LHsBind GhcPs
foldMap_bind, BagDerivStuff
forall a. Bag a
emptyBag)
  where
    foldMap_name :: GenLocated SrcSpan RdrName
foldMap_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName
forall l e. l -> e -> GenLocated l e
L SrcSpan
loc RdrName
foldMap_RDR
    foldMap_bind :: LHsBind GhcPs
foldMap_bind = GenLocated SrcSpan RdrName
-> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsBind GhcPs
mkRdrFunBind GenLocated SrcSpan RdrName
foldMap_name [LMatch GhcPs (LHsExpr GhcPs)]
foldMap_eqns
    foldMap_eqns :: [LMatch GhcPs (LHsExpr GhcPs)]
foldMap_eqns = [HsMatchContext (NameOrRdrName (IdP GhcPs))
-> [LPat GhcPs] -> LHsExpr GhcPs -> LMatch GhcPs (LHsExpr GhcPs)
forall (p :: Pass) (body :: * -> *).
HsMatchContext (NameOrRdrName (IdP (GhcPass p)))
-> [LPat (GhcPass p)]
-> Located (body (GhcPass p))
-> LMatch (GhcPass p) (Located (body (GhcPass p)))
mkSimpleMatch HsMatchContext RdrName
HsMatchContext (NameOrRdrName (IdP GhcPs))
foldMap_match_ctxt
                                  [LPat GhcPs
nlWildPat, LPat GhcPs
nlWildPat]
                                  LHsExpr GhcPs
mempty_Expr]
    foldMap_match_ctxt :: HsMatchContext RdrName
foldMap_match_ctxt = GenLocated SrcSpan RdrName -> HsMatchContext RdrName
forall id. Located id -> HsMatchContext id
mkPrefixFunRhs GenLocated SrcSpan RdrName
foldMap_name

gen_Foldable_binds SrcSpan
loc TyCon
tycon
  | [DataCon] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [DataCon]
data_cons  -- There's no real point producing anything but
                    -- foldMap for a type with no constructors.
  = (LHsBind GhcPs -> LHsBinds GhcPs
forall a. a -> Bag a
unitBag LHsBind GhcPs
foldMap_bind, BagDerivStuff
forall a. Bag a
emptyBag)

  | Bool
otherwise
  = ([LHsBind GhcPs] -> LHsBinds GhcPs
forall a. [a] -> Bag a
listToBag [LHsBind GhcPs
foldr_bind, LHsBind GhcPs
foldMap_bind, LHsBind GhcPs
null_bind], BagDerivStuff
forall a. Bag a
emptyBag)
  where
    data_cons :: [DataCon]
data_cons = TyCon -> [DataCon]
tyConDataCons TyCon
tycon

    foldr_bind :: LHsBind GhcPs
foldr_bind = GenLocated SrcSpan RdrName
-> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsBind GhcPs
mkRdrFunBind (SrcSpan -> RdrName -> GenLocated SrcSpan RdrName
forall l e. l -> e -> GenLocated l e
L SrcSpan
loc RdrName
foldable_foldr_RDR) [LMatch GhcPs (LHsExpr GhcPs)]
eqns
    eqns :: [LMatch GhcPs (LHsExpr GhcPs)]
eqns = (DataCon -> LMatch GhcPs (LHsExpr GhcPs))
-> [DataCon] -> [LMatch GhcPs (LHsExpr GhcPs)]
forall a b. (a -> b) -> [a] -> [b]
map DataCon -> LMatch GhcPs (LHsExpr GhcPs)
foldr_eqn [DataCon]
data_cons
    foldr_eqn :: DataCon -> LMatch GhcPs (LHsExpr GhcPs)
foldr_eqn DataCon
con
      = State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
-> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs)
forall s a. State s a -> s -> a
evalState (LHsExpr GhcPs
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_foldr LHsExpr GhcPs
z_Expr [LPat GhcPs
f_Pat,LPat GhcPs
z_Pat] DataCon
con ([Maybe (LHsExpr GhcPs)]
 -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> State [RdrName] [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< State [RdrName] [Maybe (LHsExpr GhcPs)]
parts) [RdrName]
bs_RDRs
      where
        parts :: State [RdrName] [Maybe (LHsExpr GhcPs)]
parts = [State [RdrName] (Maybe (LHsExpr GhcPs))]
-> State [RdrName] [Maybe (LHsExpr GhcPs)]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence ([State [RdrName] (Maybe (LHsExpr GhcPs))]
 -> State [RdrName] [Maybe (LHsExpr GhcPs)])
-> [State [RdrName] (Maybe (LHsExpr GhcPs))]
-> State [RdrName] [Maybe (LHsExpr GhcPs)]
forall a b. (a -> b) -> a -> b
$ FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs)))
-> DataCon -> [State [RdrName] (Maybe (LHsExpr GhcPs))]
forall a. FFoldType a -> DataCon -> [a]
foldDataConArgs FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs)))
ft_foldr DataCon
con

    foldMap_name :: GenLocated SrcSpan RdrName
foldMap_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName
forall l e. l -> e -> GenLocated l e
L SrcSpan
loc RdrName
foldMap_RDR

    -- See Note [EmptyDataDecls with Functor, Foldable, and Traversable]
    foldMap_bind :: LHsBind GhcPs
foldMap_bind = Arity
-> (LHsExpr GhcPs -> LHsExpr GhcPs)
-> GenLocated SrcSpan RdrName
-> [LMatch GhcPs (LHsExpr GhcPs)]
-> LHsBind GhcPs
mkRdrFunBindEC Arity
2 (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall a b. a -> b -> a
const LHsExpr GhcPs
mempty_Expr)
                      GenLocated SrcSpan RdrName
foldMap_name [LMatch GhcPs (LHsExpr GhcPs)]
foldMap_eqns

    foldMap_eqns :: [LMatch GhcPs (LHsExpr GhcPs)]
foldMap_eqns = (DataCon -> LMatch GhcPs (LHsExpr GhcPs))
-> [DataCon] -> [LMatch GhcPs (LHsExpr GhcPs)]
forall a b. (a -> b) -> [a] -> [b]
map DataCon -> LMatch GhcPs (LHsExpr GhcPs)
foldMap_eqn [DataCon]
data_cons

    foldMap_eqn :: DataCon -> LMatch GhcPs (LHsExpr GhcPs)
foldMap_eqn DataCon
con
      = State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
-> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs)
forall s a. State s a -> s -> a
evalState ([LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_foldMap [LPat GhcPs
f_Pat] DataCon
con ([Maybe (LHsExpr GhcPs)]
 -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> State [RdrName] [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< State [RdrName] [Maybe (LHsExpr GhcPs)]
parts) [RdrName]
bs_RDRs
      where
        parts :: State [RdrName] [Maybe (LHsExpr GhcPs)]
parts = [State [RdrName] (Maybe (LHsExpr GhcPs))]
-> State [RdrName] [Maybe (LHsExpr GhcPs)]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence ([State [RdrName] (Maybe (LHsExpr GhcPs))]
 -> State [RdrName] [Maybe (LHsExpr GhcPs)])
-> [State [RdrName] (Maybe (LHsExpr GhcPs))]
-> State [RdrName] [Maybe (LHsExpr GhcPs)]
forall a b. (a -> b) -> a -> b
$ FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs)))
-> DataCon -> [State [RdrName] (Maybe (LHsExpr GhcPs))]
forall a. FFoldType a -> DataCon -> [a]
foldDataConArgs FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs)))
ft_foldMap DataCon
con

    -- Given a list of NullM results, produce Nothing if any of
    -- them is NotNull, and otherwise produce a list of Maybes
    -- with Justs representing unknowns and Nothings representing
    -- things that are definitely null.
    convert :: [NullM a] -> Maybe [Maybe a]
    convert :: [NullM a] -> Maybe [Maybe a]
convert = (NullM a -> Maybe (Maybe a)) -> [NullM a] -> Maybe [Maybe a]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse NullM a -> Maybe (Maybe a)
forall a. NullM a -> Maybe (Maybe a)
go where
      go :: NullM a -> Maybe (Maybe a)
go NullM a
IsNull = Maybe a -> Maybe (Maybe a)
forall a. a -> Maybe a
Just Maybe a
forall a. Maybe a
Nothing
      go NullM a
NotNull = Maybe (Maybe a)
forall a. Maybe a
Nothing
      go (NullM a
a) = Maybe a -> Maybe (Maybe a)
forall a. a -> Maybe a
Just (a -> Maybe a
forall a. a -> Maybe a
Just a
a)

    null_name :: GenLocated SrcSpan RdrName
null_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName
forall l e. l -> e -> GenLocated l e
L SrcSpan
loc RdrName
null_RDR
    null_match_ctxt :: HsMatchContext RdrName
null_match_ctxt = GenLocated SrcSpan RdrName -> HsMatchContext RdrName
forall id. Located id -> HsMatchContext id
mkPrefixFunRhs GenLocated SrcSpan RdrName
null_name
    null_bind :: LHsBind GhcPs
null_bind = GenLocated SrcSpan RdrName
-> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsBind GhcPs
mkRdrFunBind GenLocated SrcSpan RdrName
null_name [LMatch GhcPs (LHsExpr GhcPs)]
null_eqns
    null_eqns :: [LMatch GhcPs (LHsExpr GhcPs)]
null_eqns = (DataCon -> LMatch GhcPs (LHsExpr GhcPs))
-> [DataCon] -> [LMatch GhcPs (LHsExpr GhcPs)]
forall a b. (a -> b) -> [a] -> [b]
map DataCon -> LMatch GhcPs (LHsExpr GhcPs)
null_eqn [DataCon]
data_cons
    null_eqn :: DataCon -> LMatch GhcPs (LHsExpr GhcPs)
null_eqn DataCon
con
      = (State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
 -> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs))
-> [RdrName]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
-> LMatch GhcPs (LHsExpr GhcPs)
forall a b c. (a -> b -> c) -> b -> a -> c
flip State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
-> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs)
forall s a. State s a -> s -> a
evalState [RdrName]
bs_RDRs (State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
 -> LMatch GhcPs (LHsExpr GhcPs))
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
-> LMatch GhcPs (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$ do
          [NullM (LHsExpr GhcPs)]
parts <- [State [RdrName] (NullM (LHsExpr GhcPs))]
-> State [RdrName] [NullM (LHsExpr GhcPs)]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence ([State [RdrName] (NullM (LHsExpr GhcPs))]
 -> State [RdrName] [NullM (LHsExpr GhcPs)])
-> [State [RdrName] (NullM (LHsExpr GhcPs))]
-> State [RdrName] [NullM (LHsExpr GhcPs)]
forall a b. (a -> b) -> a -> b
$ FFoldType (State [RdrName] (NullM (LHsExpr GhcPs)))
-> DataCon -> [State [RdrName] (NullM (LHsExpr GhcPs))]
forall a. FFoldType a -> DataCon -> [a]
foldDataConArgs FFoldType (State [RdrName] (NullM (LHsExpr GhcPs)))
ft_null DataCon
con
          case [NullM (LHsExpr GhcPs)] -> Maybe [Maybe (LHsExpr GhcPs)]
forall a. [NullM a] -> Maybe [Maybe a]
convert [NullM (LHsExpr GhcPs)]
parts of
            Maybe [Maybe (LHsExpr GhcPs)]
Nothing -> LMatch GhcPs (LHsExpr GhcPs)
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall (m :: * -> *) a. Monad m => a -> m a
return (LMatch GhcPs (LHsExpr GhcPs)
 -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> LMatch GhcPs (LHsExpr GhcPs)
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall a b. (a -> b) -> a -> b
$
              HsMatchContext (NameOrRdrName (IdP GhcPs))
-> [LPat GhcPs]
-> LHsExpr GhcPs
-> Located (HsLocalBinds GhcPs)
-> LMatch GhcPs (LHsExpr GhcPs)
forall (p :: Pass).
HsMatchContext (NameOrRdrName (IdP (GhcPass p)))
-> [LPat (GhcPass p)]
-> LHsExpr (GhcPass p)
-> Located (HsLocalBinds (GhcPass p))
-> LMatch (GhcPass p) (LHsExpr (GhcPass p))
mkMatch HsMatchContext RdrName
HsMatchContext (NameOrRdrName (IdP GhcPs))
null_match_ctxt [LPat GhcPs -> LPat GhcPs
forall (name :: Pass). LPat (GhcPass name) -> LPat (GhcPass name)
nlParPat (DataCon -> LPat GhcPs
nlWildConPat DataCon
con)]
                LHsExpr GhcPs
false_Expr (SrcSpanLess (Located (HsLocalBinds GhcPs))
-> Located (HsLocalBinds GhcPs)
forall a. HasSrcSpan a => SrcSpanLess a -> a
noLoc SrcSpanLess (Located (HsLocalBinds GhcPs))
forall (a :: Pass) (b :: Pass).
HsLocalBindsLR (GhcPass a) (GhcPass b)
emptyLocalBinds)
            Just [Maybe (LHsExpr GhcPs)]
cp -> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_null [] DataCon
con [Maybe (LHsExpr GhcPs)]
cp

    -- Yields 'Just' an expression if we're folding over a type that mentions
    -- the last type parameter of the datatype. Otherwise, yields 'Nothing'.
    -- See Note [FFoldType and functorLikeTraverse]
    ft_foldr :: FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs)))
    ft_foldr :: FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs)))
ft_foldr
      = FT :: forall a.
a
-> a
-> a
-> (a -> a -> a)
-> (TyCon -> [a] -> a)
-> (Type -> a -> a)
-> a
-> (TcTyVar -> a -> a)
-> FFoldType a
FT { ft_triv :: State [RdrName] (Maybe (LHsExpr GhcPs))
ft_triv    = Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe (LHsExpr GhcPs)
forall a. Maybe a
Nothing
             -- foldr f = \x z -> z
           , ft_var :: State [RdrName] (Maybe (LHsExpr GhcPs))
ft_var     = Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall (m :: * -> *) a. Monad m => a -> m a
return (Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs)))
-> Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall a b. (a -> b) -> a -> b
$ LHsExpr GhcPs -> Maybe (LHsExpr GhcPs)
forall a. a -> Maybe a
Just LHsExpr GhcPs
f_Expr
             -- foldr f = f
           , ft_tup :: TyCon
-> [State [RdrName] (Maybe (LHsExpr GhcPs))]
-> State [RdrName] (Maybe (LHsExpr GhcPs))
ft_tup     = \TyCon
t [State [RdrName] (Maybe (LHsExpr GhcPs))]
g -> do
               [Maybe (LHsExpr GhcPs)]
gg  <- [State [RdrName] (Maybe (LHsExpr GhcPs))]
-> State [RdrName] [Maybe (LHsExpr GhcPs)]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence [State [RdrName] (Maybe (LHsExpr GhcPs))]
g
               LHsExpr GhcPs
lam <- (LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
mkSimpleLam2 ((LHsExpr GhcPs
  -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
 -> State [RdrName] (LHsExpr GhcPs))
-> (LHsExpr GhcPs
    -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$ \LHsExpr GhcPs
x LHsExpr GhcPs
z ->
                 ([LPat GhcPs]
 -> DataCon
 -> [Maybe (LHsExpr GhcPs)]
 -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> TyCon
-> [Maybe (LHsExpr GhcPs)]
-> LHsExpr GhcPs
-> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a.
Monad m =>
([LPat GhcPs]
 -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs)))
-> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs)
mkSimpleTupleCase (LHsExpr GhcPs
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_foldr LHsExpr GhcPs
z) TyCon
t [Maybe (LHsExpr GhcPs)]
gg LHsExpr GhcPs
x
               Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall (m :: * -> *) a. Monad m => a -> m a
return (LHsExpr GhcPs -> Maybe (LHsExpr GhcPs)
forall a. a -> Maybe a
Just LHsExpr GhcPs
lam)
             -- foldr f = (\x z -> case x of ...)
           , ft_ty_app :: Type
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
ft_ty_app  = \Type
_ State [RdrName] (Maybe (LHsExpr GhcPs))
g -> do
               Maybe (LHsExpr GhcPs)
gg <- State [RdrName] (Maybe (LHsExpr GhcPs))
g
               (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM (\LHsExpr GhcPs
gg' -> (LHsExpr GhcPs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
mkSimpleLam2 ((LHsExpr GhcPs
  -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
 -> State [RdrName] (LHsExpr GhcPs))
-> (LHsExpr GhcPs
    -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$ \LHsExpr GhcPs
x LHsExpr GhcPs
z -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a. Monad m => a -> m a
return (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$
                 IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs
forall (id :: Pass).
IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id)
nlHsApps RdrName
IdP GhcPs
foldable_foldr_RDR [LHsExpr GhcPs
gg',LHsExpr GhcPs
z,LHsExpr GhcPs
x]) Maybe (LHsExpr GhcPs)
gg
             -- foldr f = (\x z -> foldr g z x)
           , ft_forall :: TcTyVar
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
ft_forall  = \TcTyVar
_ State [RdrName] (Maybe (LHsExpr GhcPs))
g -> State [RdrName] (Maybe (LHsExpr GhcPs))
g
           , ft_co_var :: State [RdrName] (Maybe (LHsExpr GhcPs))
ft_co_var  = String -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall a. String -> a
panic String
"contravariant in ft_foldr"
           , ft_fun :: State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
ft_fun     = String
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
forall a. String -> a
panic String
"function in ft_foldr"
           , ft_bad_app :: State [RdrName] (Maybe (LHsExpr GhcPs))
ft_bad_app = String -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall a. String -> a
panic String
"in other argument in ft_foldr" }

    match_foldr :: LHsExpr GhcPs
                -> [LPat GhcPs]
                -> DataCon
                -> [Maybe (LHsExpr GhcPs)]
                -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
    match_foldr :: LHsExpr GhcPs
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_foldr LHsExpr GhcPs
z = HsMatchContext RdrName
-> (LHsExpr GhcPs
    -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall (m :: * -> *).
Monad m =>
HsMatchContext RdrName
-> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> m (LMatch GhcPs (LHsExpr GhcPs))
mkSimpleConMatch2 HsMatchContext RdrName
forall id. HsMatchContext id
LambdaExpr ((LHsExpr GhcPs
  -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs))
 -> [LPat GhcPs]
 -> DataCon
 -> [Maybe (LHsExpr GhcPs)]
 -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> (LHsExpr GhcPs
    -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall a b. (a -> b) -> a -> b
$ \LHsExpr GhcPs
_ [LHsExpr GhcPs]
xs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a. Monad m => a -> m a
return ([LHsExpr GhcPs] -> LHsExpr GhcPs
mkFoldr [LHsExpr GhcPs]
xs)
      where
        -- g1 v1 (g2 v2 (.. z))
        mkFoldr :: [LHsExpr GhcPs] -> LHsExpr GhcPs
        mkFoldr :: [LHsExpr GhcPs] -> LHsExpr GhcPs
mkFoldr = (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs)
-> LHsExpr GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
nlHsApp LHsExpr GhcPs
z

    -- See Note [FFoldType and functorLikeTraverse]
    ft_foldMap :: FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs)))
    ft_foldMap :: FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs)))
ft_foldMap
      = FT :: forall a.
a
-> a
-> a
-> (a -> a -> a)
-> (TyCon -> [a] -> a)
-> (Type -> a -> a)
-> a
-> (TcTyVar -> a -> a)
-> FFoldType a
FT { ft_triv :: State [RdrName] (Maybe (LHsExpr GhcPs))
ft_triv = Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe (LHsExpr GhcPs)
forall a. Maybe a
Nothing
             -- foldMap f = \x -> mempty
           , ft_var :: State [RdrName] (Maybe (LHsExpr GhcPs))
ft_var  = Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall (m :: * -> *) a. Monad m => a -> m a
return (LHsExpr GhcPs -> Maybe (LHsExpr GhcPs)
forall a. a -> Maybe a
Just LHsExpr GhcPs
f_Expr)
             -- foldMap f = f
           , ft_tup :: TyCon
-> [State [RdrName] (Maybe (LHsExpr GhcPs))]
-> State [RdrName] (Maybe (LHsExpr GhcPs))
ft_tup  = \TyCon
t [State [RdrName] (Maybe (LHsExpr GhcPs))]
g -> do
               [Maybe (LHsExpr GhcPs)]
gg  <- [State [RdrName] (Maybe (LHsExpr GhcPs))]
-> State [RdrName] [Maybe (LHsExpr GhcPs)]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence [State [RdrName] (Maybe (LHsExpr GhcPs))]
g
               LHsExpr GhcPs
lam <- (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
 -> State [RdrName] (LHsExpr GhcPs))
-> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$ ([LPat GhcPs]
 -> DataCon
 -> [Maybe (LHsExpr GhcPs)]
 -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> TyCon
-> [Maybe (LHsExpr GhcPs)]
-> LHsExpr GhcPs
-> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a.
Monad m =>
([LPat GhcPs]
 -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs)))
-> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs)
mkSimpleTupleCase [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_foldMap TyCon
t [Maybe (LHsExpr GhcPs)]
gg
               Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall (m :: * -> *) a. Monad m => a -> m a
return (LHsExpr GhcPs -> Maybe (LHsExpr GhcPs)
forall a. a -> Maybe a
Just LHsExpr GhcPs
lam)
             -- foldMap f = \x -> case x of (..,)
           , ft_ty_app :: Type
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
ft_ty_app = \Type
_ State [RdrName] (Maybe (LHsExpr GhcPs))
g -> (LHsExpr GhcPs -> LHsExpr GhcPs)
-> Maybe (LHsExpr GhcPs) -> Maybe (LHsExpr GhcPs)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
nlHsApp LHsExpr GhcPs
foldMap_Expr) (Maybe (LHsExpr GhcPs) -> Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> State [RdrName] (Maybe (LHsExpr GhcPs))
g
             -- foldMap f = foldMap g
           , ft_forall :: TcTyVar
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
ft_forall = \TcTyVar
_ State [RdrName] (Maybe (LHsExpr GhcPs))
g -> State [RdrName] (Maybe (LHsExpr GhcPs))
g
           , ft_co_var :: State [RdrName] (Maybe (LHsExpr GhcPs))
ft_co_var = String -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall a. String -> a
panic String
"contravariant in ft_foldMap"
           , ft_fun :: State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
ft_fun = String
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
forall a. String -> a
panic String
"function in ft_foldMap"
           , ft_bad_app :: State [RdrName] (Maybe (LHsExpr GhcPs))
ft_bad_app = String -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall a. String -> a
panic String
"in other argument in ft_foldMap" }

    match_foldMap :: [LPat GhcPs]
                  -> DataCon
                  -> [Maybe (LHsExpr GhcPs)]
                  -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
    match_foldMap :: [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_foldMap = HsMatchContext RdrName
-> (LHsExpr GhcPs
    -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall (m :: * -> *).
Monad m =>
HsMatchContext RdrName
-> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> m (LMatch GhcPs (LHsExpr GhcPs))
mkSimpleConMatch2 HsMatchContext RdrName
forall id. HsMatchContext id
CaseAlt ((LHsExpr GhcPs
  -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs))
 -> [LPat GhcPs]
 -> DataCon
 -> [Maybe (LHsExpr GhcPs)]
 -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> (LHsExpr GhcPs
    -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall a b. (a -> b) -> a -> b
$ \LHsExpr GhcPs
_ [LHsExpr GhcPs]
xs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a. Monad m => a -> m a
return ([LHsExpr GhcPs] -> LHsExpr GhcPs
mkFoldMap [LHsExpr GhcPs]
xs)
      where
        -- mappend v1 (mappend v2 ..)
        mkFoldMap :: [LHsExpr GhcPs] -> LHsExpr GhcPs
        mkFoldMap :: [LHsExpr GhcPs] -> LHsExpr GhcPs
mkFoldMap [] = LHsExpr GhcPs
mempty_Expr
        mkFoldMap [LHsExpr GhcPs]
xs = (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs)
-> [LHsExpr GhcPs] -> LHsExpr GhcPs
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
foldr1 (\LHsExpr GhcPs
x LHsExpr GhcPs
y -> IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs
forall (id :: Pass).
IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id)
nlHsApps RdrName
IdP GhcPs
mappend_RDR [LHsExpr GhcPs
x,LHsExpr GhcPs
y]) [LHsExpr GhcPs]
xs

    -- See Note [FFoldType and functorLikeTraverse]
    -- Yields NullM an expression if we're folding over an expression
    -- that may or may not be null. Yields IsNull if it's certainly
    -- null, and yields NotNull if it's certainly not null.
    -- See Note [Deriving null]
    ft_null :: FFoldType (State [RdrName] (NullM (LHsExpr GhcPs)))
    ft_null :: FFoldType (State [RdrName] (NullM (LHsExpr GhcPs)))
ft_null
      = FT :: forall a.
a
-> a
-> a
-> (a -> a -> a)
-> (TyCon -> [a] -> a)
-> (Type -> a -> a)
-> a
-> (TcTyVar -> a -> a)
-> FFoldType a
FT { ft_triv :: State [RdrName] (NullM (LHsExpr GhcPs))
ft_triv = NullM (LHsExpr GhcPs) -> State [RdrName] (NullM (LHsExpr GhcPs))
forall (m :: * -> *) a. Monad m => a -> m a
return NullM (LHsExpr GhcPs)
forall a. NullM a
IsNull
             -- null = \_ -> True
           , ft_var :: State [RdrName] (NullM (LHsExpr GhcPs))
ft_var  = NullM (LHsExpr GhcPs) -> State [RdrName] (NullM (LHsExpr GhcPs))
forall (m :: * -> *) a. Monad m => a -> m a
return NullM (LHsExpr GhcPs)
forall a. NullM a
NotNull
             -- null = \_ -> False
           , ft_tup :: TyCon
-> [State [RdrName] (NullM (LHsExpr GhcPs))]
-> State [RdrName] (NullM (LHsExpr GhcPs))
ft_tup  = \TyCon
t [State [RdrName] (NullM (LHsExpr GhcPs))]
g -> do
               [NullM (LHsExpr GhcPs)]
gg  <- [State [RdrName] (NullM (LHsExpr GhcPs))]
-> State [RdrName] [NullM (LHsExpr GhcPs)]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence [State [RdrName] (NullM (LHsExpr GhcPs))]
g
               case [NullM (LHsExpr GhcPs)] -> Maybe [Maybe (LHsExpr GhcPs)]
forall a. [NullM a] -> Maybe [Maybe a]
convert [NullM (LHsExpr GhcPs)]
gg of
                 Maybe [Maybe (LHsExpr GhcPs)]
Nothing -> NullM (LHsExpr GhcPs) -> State [RdrName] (NullM (LHsExpr GhcPs))
forall (f :: * -> *) a. Applicative f => a -> f a
pure NullM (LHsExpr GhcPs)
forall a. NullM a
NotNull
                 Just [Maybe (LHsExpr GhcPs)]
ggg ->
                   LHsExpr GhcPs -> NullM (LHsExpr GhcPs)
forall a. a -> NullM a
NullM (LHsExpr GhcPs -> NullM (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
-> State [RdrName] (NullM (LHsExpr GhcPs))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
 -> State [RdrName] (LHsExpr GhcPs))
-> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$ ([LPat GhcPs]
 -> DataCon
 -> [Maybe (LHsExpr GhcPs)]
 -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> TyCon
-> [Maybe (LHsExpr GhcPs)]
-> LHsExpr GhcPs
-> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a.
Monad m =>
([LPat GhcPs]
 -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs)))
-> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs)
mkSimpleTupleCase [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_null TyCon
t [Maybe (LHsExpr GhcPs)]
ggg)
             -- null = \x -> case x of (..,)
           , ft_ty_app :: Type
-> State [RdrName] (NullM (LHsExpr GhcPs))
-> State [RdrName] (NullM (LHsExpr GhcPs))
ft_ty_app = \Type
_ State [RdrName] (NullM (LHsExpr GhcPs))
g -> ((NullM (LHsExpr GhcPs) -> NullM (LHsExpr GhcPs))
 -> State [RdrName] (NullM (LHsExpr GhcPs))
 -> State [RdrName] (NullM (LHsExpr GhcPs)))
-> State [RdrName] (NullM (LHsExpr GhcPs))
-> (NullM (LHsExpr GhcPs) -> NullM (LHsExpr GhcPs))
-> State [RdrName] (NullM (LHsExpr GhcPs))
forall a b c. (a -> b -> c) -> b -> a -> c
flip (NullM (LHsExpr GhcPs) -> NullM (LHsExpr GhcPs))
-> State [RdrName] (NullM (LHsExpr GhcPs))
-> State [RdrName] (NullM (LHsExpr GhcPs))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap State [RdrName] (NullM (LHsExpr GhcPs))
g ((NullM (LHsExpr GhcPs) -> NullM (LHsExpr GhcPs))
 -> State [RdrName] (NullM (LHsExpr GhcPs)))
-> (NullM (LHsExpr GhcPs) -> NullM (LHsExpr GhcPs))
-> State [RdrName] (NullM (LHsExpr GhcPs))
forall a b. (a -> b) -> a -> b
$ \NullM (LHsExpr GhcPs)
nestedResult ->
                              case NullM (LHsExpr GhcPs)
nestedResult of
                                -- If e definitely contains the parameter,
                                -- then we can test if (G e) contains it by
                                -- simply checking if (G e) is null
                                NullM (LHsExpr GhcPs)
NotNull -> LHsExpr GhcPs -> NullM (LHsExpr GhcPs)
forall a. a -> NullM a
NullM LHsExpr GhcPs
null_Expr
                                -- This case is unreachable--it will actually be
                                -- caught by ft_triv
                                NullM (LHsExpr GhcPs)
IsNull -> NullM (LHsExpr GhcPs)
forall a. NullM a
IsNull
                                -- The general case uses (all null),
                                -- (all (all null)), etc.
                                NullM LHsExpr GhcPs
nestedTest -> LHsExpr GhcPs -> NullM (LHsExpr GhcPs)
forall a. a -> NullM a
NullM (LHsExpr GhcPs -> NullM (LHsExpr GhcPs))
-> LHsExpr GhcPs -> NullM (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$
                                                    LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
nlHsApp LHsExpr GhcPs
all_Expr LHsExpr GhcPs
nestedTest
             -- null fa = null fa, or null fa = all null fa, or null fa = True
           , ft_forall :: TcTyVar
-> State [RdrName] (NullM (LHsExpr GhcPs))
-> State [RdrName] (NullM (LHsExpr GhcPs))
ft_forall = \TcTyVar
_ State [RdrName] (NullM (LHsExpr GhcPs))
g -> State [RdrName] (NullM (LHsExpr GhcPs))
g
           , ft_co_var :: State [RdrName] (NullM (LHsExpr GhcPs))
ft_co_var = String -> State [RdrName] (NullM (LHsExpr GhcPs))
forall a. String -> a
panic String
"contravariant in ft_null"
           , ft_fun :: State [RdrName] (NullM (LHsExpr GhcPs))
-> State [RdrName] (NullM (LHsExpr GhcPs))
-> State [RdrName] (NullM (LHsExpr GhcPs))
ft_fun = String
-> State [RdrName] (NullM (LHsExpr GhcPs))
-> State [RdrName] (NullM (LHsExpr GhcPs))
-> State [RdrName] (NullM (LHsExpr GhcPs))
forall a. String -> a
panic String
"function in ft_null"
           , ft_bad_app :: State [RdrName] (NullM (LHsExpr GhcPs))
ft_bad_app = String -> State [RdrName] (NullM (LHsExpr GhcPs))
forall a. String -> a
panic String
"in other argument in ft_null" }

    match_null :: [LPat GhcPs]
                  -> DataCon
                  -> [Maybe (LHsExpr GhcPs)]
                  -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
    match_null :: [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_null = HsMatchContext RdrName
-> (LHsExpr GhcPs
    -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall (m :: * -> *).
Monad m =>
HsMatchContext RdrName
-> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> m (LMatch GhcPs (LHsExpr GhcPs))
mkSimpleConMatch2 HsMatchContext RdrName
forall id. HsMatchContext id
CaseAlt ((LHsExpr GhcPs
  -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs))
 -> [LPat GhcPs]
 -> DataCon
 -> [Maybe (LHsExpr GhcPs)]
 -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> (LHsExpr GhcPs
    -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall a b. (a -> b) -> a -> b
$ \LHsExpr GhcPs
_ [LHsExpr GhcPs]
xs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a. Monad m => a -> m a
return ([LHsExpr GhcPs] -> LHsExpr GhcPs
mkNull [LHsExpr GhcPs]
xs)
      where
        -- v1 && v2 && ..
        mkNull :: [LHsExpr GhcPs] -> LHsExpr GhcPs
        mkNull :: [LHsExpr GhcPs] -> LHsExpr GhcPs
mkNull [] = LHsExpr GhcPs
true_Expr
        mkNull [LHsExpr GhcPs]
xs = (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs)
-> [LHsExpr GhcPs] -> LHsExpr GhcPs
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
foldr1 (\LHsExpr GhcPs
x LHsExpr GhcPs
y -> IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs
forall (id :: Pass).
IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id)
nlHsApps RdrName
IdP GhcPs
and_RDR [LHsExpr GhcPs
x,LHsExpr GhcPs
y]) [LHsExpr GhcPs]
xs

data NullM a =
    IsNull   -- Definitely null
  | NotNull  -- Definitely not null
  | NullM a  -- Unknown

{-
************************************************************************
*                                                                      *
                        Traversable instances

 see http://www.mail-archive.com/haskell-prime@haskell.org/msg02116.html
*                                                                      *
************************************************************************

Again, Traversable is much like Functor and Foldable.

The cases are:

  $(traverse 'a 'a)          =  f
  $(traverse 'a '(b1,b2))    =  \x -> case x of (x1,x2) ->
     liftA2 (,) ($(traverse 'a 'b1) x1) ($(traverse 'a 'b2) x2)
  $(traverse 'a '(T b1 b2))  =  traverse $(traverse 'a 'b2)  -- when a only occurs in the last parameter, b2

Like -XDeriveFoldable, -XDeriveTraversable filters out arguments whose types
do not mention the last type parameter. Therefore, the following datatype:

  data Foo a = Foo Int a Int

would have the following derived Traversable instance:

  instance Traversable Foo where
    traverse f (Foo x1 x2 x3) =
      fmap (\b2 -> Foo x1 b2 x3) ( $(traverse 'a 'a) x2 )

since the two Int arguments do not produce any effects in a traversal.

One can envision a case for types that do not mention the last type parameter:

  $(traverse 'a 'b)          =  pure     -- when b does not contain a

But this case will never materialize, since the aforementioned filtering
removes all such types from consideration.
See Note [Generated code for DeriveFoldable and DeriveTraversable].
-}

gen_Traversable_binds :: SrcSpan -> TyCon -> (LHsBinds GhcPs, BagDerivStuff)
-- When the argument is phantom, we can use traverse = pure . coerce
-- See Note [Phantom types with Functor, Foldable, and Traversable]
gen_Traversable_binds :: SrcSpan -> TyCon -> (LHsBinds GhcPs, BagDerivStuff)
gen_Traversable_binds SrcSpan
loc TyCon
tycon
  | Role
Phantom <- [Role] -> Role
forall a. [a] -> a
last (TyCon -> [Role]
tyConRoles TyCon
tycon)
  = (LHsBind GhcPs -> LHsBinds GhcPs
forall a. a -> Bag a
unitBag LHsBind GhcPs
traverse_bind, BagDerivStuff
forall a. Bag a
emptyBag)
  where
    traverse_name :: GenLocated SrcSpan RdrName
traverse_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName
forall l e. l -> e -> GenLocated l e
L SrcSpan
loc RdrName
traverse_RDR
    traverse_bind :: LHsBind GhcPs
traverse_bind = GenLocated SrcSpan RdrName
-> [LMatch GhcPs (LHsExpr GhcPs)] -> LHsBind GhcPs
mkRdrFunBind GenLocated SrcSpan RdrName
traverse_name [LMatch GhcPs (LHsExpr GhcPs)]
traverse_eqns
    traverse_eqns :: [LMatch GhcPs (LHsExpr GhcPs)]
traverse_eqns =
        [HsMatchContext (NameOrRdrName (IdP GhcPs))
-> [LPat GhcPs] -> LHsExpr GhcPs -> LMatch GhcPs (LHsExpr GhcPs)
forall (p :: Pass) (body :: * -> *).
HsMatchContext (NameOrRdrName (IdP (GhcPass p)))
-> [LPat (GhcPass p)]
-> Located (body (GhcPass p))
-> LMatch (GhcPass p) (Located (body (GhcPass p)))
mkSimpleMatch HsMatchContext RdrName
HsMatchContext (NameOrRdrName (IdP GhcPs))
traverse_match_ctxt
                       [LPat GhcPs
nlWildPat, LPat GhcPs
z_Pat]
                       (IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs
forall (id :: Pass).
IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id)
nlHsApps RdrName
IdP GhcPs
pure_RDR [LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
nlHsApp LHsExpr GhcPs
coerce_Expr LHsExpr GhcPs
z_Expr])]
    traverse_match_ctxt :: HsMatchContext RdrName
traverse_match_ctxt = GenLocated SrcSpan RdrName -> HsMatchContext RdrName
forall id. Located id -> HsMatchContext id
mkPrefixFunRhs GenLocated SrcSpan RdrName
traverse_name

gen_Traversable_binds SrcSpan
loc TyCon
tycon
  = (LHsBind GhcPs -> LHsBinds GhcPs
forall a. a -> Bag a
unitBag LHsBind GhcPs
traverse_bind, BagDerivStuff
forall a. Bag a
emptyBag)
  where
    data_cons :: [DataCon]
data_cons = TyCon -> [DataCon]
tyConDataCons TyCon
tycon

    traverse_name :: GenLocated SrcSpan RdrName
traverse_name = SrcSpan -> RdrName -> GenLocated SrcSpan RdrName
forall l e. l -> e -> GenLocated l e
L SrcSpan
loc RdrName
traverse_RDR

    -- See Note [EmptyDataDecls with Functor, Foldable, and Traversable]
    traverse_bind :: LHsBind GhcPs
traverse_bind = Arity
-> (LHsExpr GhcPs -> LHsExpr GhcPs)
-> GenLocated SrcSpan RdrName
-> [LMatch GhcPs (LHsExpr GhcPs)]
-> LHsBind GhcPs
mkRdrFunBindEC Arity
2 (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
nlHsApp LHsExpr GhcPs
pure_Expr)
                                   GenLocated SrcSpan RdrName
traverse_name [LMatch GhcPs (LHsExpr GhcPs)]
traverse_eqns
    traverse_eqns :: [LMatch GhcPs (LHsExpr GhcPs)]
traverse_eqns = (DataCon -> LMatch GhcPs (LHsExpr GhcPs))
-> [DataCon] -> [LMatch GhcPs (LHsExpr GhcPs)]
forall a b. (a -> b) -> [a] -> [b]
map DataCon -> LMatch GhcPs (LHsExpr GhcPs)
traverse_eqn [DataCon]
data_cons
    traverse_eqn :: DataCon -> LMatch GhcPs (LHsExpr GhcPs)
traverse_eqn DataCon
con
      = State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
-> [RdrName] -> LMatch GhcPs (LHsExpr GhcPs)
forall s a. State s a -> s -> a
evalState ([LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_for_con [LPat GhcPs
f_Pat] DataCon
con ([Maybe (LHsExpr GhcPs)]
 -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> State [RdrName] [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< State [RdrName] [Maybe (LHsExpr GhcPs)]
parts) [RdrName]
bs_RDRs
      where
        parts :: State [RdrName] [Maybe (LHsExpr GhcPs)]
parts = [State [RdrName] (Maybe (LHsExpr GhcPs))]
-> State [RdrName] [Maybe (LHsExpr GhcPs)]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence ([State [RdrName] (Maybe (LHsExpr GhcPs))]
 -> State [RdrName] [Maybe (LHsExpr GhcPs)])
-> [State [RdrName] (Maybe (LHsExpr GhcPs))]
-> State [RdrName] [Maybe (LHsExpr GhcPs)]
forall a b. (a -> b) -> a -> b
$ FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs)))
-> DataCon -> [State [RdrName] (Maybe (LHsExpr GhcPs))]
forall a. FFoldType a -> DataCon -> [a]
foldDataConArgs FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs)))
ft_trav DataCon
con

    -- Yields 'Just' an expression if we're folding over a type that mentions
    -- the last type parameter of the datatype. Otherwise, yields 'Nothing'.
    -- See Note [FFoldType and functorLikeTraverse]
    ft_trav :: FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs)))
    ft_trav :: FFoldType (State [RdrName] (Maybe (LHsExpr GhcPs)))
ft_trav
      = FT :: forall a.
a
-> a
-> a
-> (a -> a -> a)
-> (TyCon -> [a] -> a)
-> (Type -> a -> a)
-> a
-> (TcTyVar -> a -> a)
-> FFoldType a
FT { ft_triv :: State [RdrName] (Maybe (LHsExpr GhcPs))
ft_triv    = Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe (LHsExpr GhcPs)
forall a. Maybe a
Nothing
             -- traverse f = pure x
           , ft_var :: State [RdrName] (Maybe (LHsExpr GhcPs))
ft_var     = Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall (m :: * -> *) a. Monad m => a -> m a
return (LHsExpr GhcPs -> Maybe (LHsExpr GhcPs)
forall a. a -> Maybe a
Just LHsExpr GhcPs
f_Expr)
             -- traverse f = f x
           , ft_tup :: TyCon
-> [State [RdrName] (Maybe (LHsExpr GhcPs))]
-> State [RdrName] (Maybe (LHsExpr GhcPs))
ft_tup     = \TyCon
t [State [RdrName] (Maybe (LHsExpr GhcPs))]
gs -> do
               [Maybe (LHsExpr GhcPs)]
gg  <- [State [RdrName] (Maybe (LHsExpr GhcPs))]
-> State [RdrName] [Maybe (LHsExpr GhcPs)]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence [State [RdrName] (Maybe (LHsExpr GhcPs))]
gs
               LHsExpr GhcPs
lam <- (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
mkSimpleLam ((LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
 -> State [RdrName] (LHsExpr GhcPs))
-> (LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs))
-> State [RdrName] (LHsExpr GhcPs)
forall a b. (a -> b) -> a -> b
$ ([LPat GhcPs]
 -> DataCon
 -> [Maybe (LHsExpr GhcPs)]
 -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> TyCon
-> [Maybe (LHsExpr GhcPs)]
-> LHsExpr GhcPs
-> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a.
Monad m =>
([LPat GhcPs]
 -> DataCon -> [a] -> m (LMatch GhcPs (LHsExpr GhcPs)))
-> TyCon -> [a] -> LHsExpr GhcPs -> m (LHsExpr GhcPs)
mkSimpleTupleCase [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_for_con TyCon
t [Maybe (LHsExpr GhcPs)]
gg
               Maybe (LHsExpr GhcPs) -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall (m :: * -> *) a. Monad m => a -> m a
return (LHsExpr GhcPs -> Maybe (LHsExpr GhcPs)
forall a. a -> Maybe a
Just LHsExpr GhcPs
lam)
             -- traverse f = \x -> case x of (a1,a2,..) ->
             --                           liftA2 (,,) (g1 a1) (g2 a2) <*> ..
           , ft_ty_app :: Type
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
ft_ty_app  = \Type
_ State [RdrName] (Maybe (LHsExpr GhcPs))
g -> (LHsExpr GhcPs -> LHsExpr GhcPs)
-> Maybe (LHsExpr GhcPs) -> Maybe (LHsExpr GhcPs)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
nlHsApp LHsExpr GhcPs
traverse_Expr) (Maybe (LHsExpr GhcPs) -> Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> State [RdrName] (Maybe (LHsExpr GhcPs))
g
             -- traverse f = traverse g
           , ft_forall :: TcTyVar
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
ft_forall  = \TcTyVar
_ State [RdrName] (Maybe (LHsExpr GhcPs))
g -> State [RdrName] (Maybe (LHsExpr GhcPs))
g
           , ft_co_var :: State [RdrName] (Maybe (LHsExpr GhcPs))
ft_co_var  = String -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall a. String -> a
panic String
"contravariant in ft_trav"
           , ft_fun :: State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
ft_fun     = String
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
-> State [RdrName] (Maybe (LHsExpr GhcPs))
forall a. String -> a
panic String
"function in ft_trav"
           , ft_bad_app :: State [RdrName] (Maybe (LHsExpr GhcPs))
ft_bad_app = String -> State [RdrName] (Maybe (LHsExpr GhcPs))
forall a. String -> a
panic String
"in other argument in ft_trav" }

    -- Con a1 a2 ... -> liftA2 (\b1 b2 ... -> Con b1 b2 ...) (g1 a1)
    --                    (g2 a2) <*> ...
    match_for_con :: [LPat GhcPs]
                  -> DataCon
                  -> [Maybe (LHsExpr GhcPs)]
                  -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
    match_for_con :: [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
match_for_con = HsMatchContext RdrName
-> (LHsExpr GhcPs
    -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall (m :: * -> *).
Monad m =>
HsMatchContext RdrName
-> (LHsExpr GhcPs -> [LHsExpr GhcPs] -> m (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> m (LMatch GhcPs (LHsExpr GhcPs))
mkSimpleConMatch2 HsMatchContext RdrName
forall id. HsMatchContext id
CaseAlt ((LHsExpr GhcPs
  -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs))
 -> [LPat GhcPs]
 -> DataCon
 -> [Maybe (LHsExpr GhcPs)]
 -> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs)))
-> (LHsExpr GhcPs
    -> [LHsExpr GhcPs] -> State [RdrName] (LHsExpr GhcPs))
-> [LPat GhcPs]
-> DataCon
-> [Maybe (LHsExpr GhcPs)]
-> State [RdrName] (LMatch GhcPs (LHsExpr GhcPs))
forall a b. (a -> b) -> a -> b
$
                                             \LHsExpr GhcPs
con [LHsExpr GhcPs]
xs -> LHsExpr GhcPs -> State [RdrName] (LHsExpr GhcPs)
forall (m :: * -> *) a. Monad m => a -> m a
return (LHsExpr GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs
mkApCon LHsExpr GhcPs
con [LHsExpr GhcPs]
xs)
      where
        -- liftA2 (\b1 b2 ... -> Con b1 b2 ...) x1 x2 <*> ..
        mkApCon :: LHsExpr GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs
        mkApCon :: LHsExpr GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs
mkApCon LHsExpr GhcPs
con [] = IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs
forall (id :: Pass).
IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id)
nlHsApps RdrName
IdP GhcPs
pure_RDR [LHsExpr GhcPs
con]
        mkApCon LHsExpr GhcPs
con [LHsExpr GhcPs
x] = IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs
forall (id :: Pass).
IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id)
nlHsApps RdrName
IdP GhcPs
fmap_RDR [LHsExpr GhcPs
con,LHsExpr GhcPs
x]
        mkApCon LHsExpr GhcPs
con (LHsExpr GhcPs
x1:LHsExpr GhcPs
x2:[LHsExpr GhcPs]
xs) =
            (LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs)
-> LHsExpr GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' LHsExpr GhcPs -> LHsExpr GhcPs -> LHsExpr GhcPs
forall (id :: Pass).
(IdP (GhcPass id) ~ RdrName) =>
LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
appAp (IdP GhcPs -> [LHsExpr GhcPs] -> LHsExpr GhcPs
forall (id :: Pass).
IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id)
nlHsApps RdrName
IdP GhcPs
liftA2_RDR [LHsExpr GhcPs
con,LHsExpr GhcPs
x1,LHsExpr GhcPs
x2]) [LHsExpr GhcPs]
xs
          where appAp :: LHsExpr (GhcPass id)
-> LHsExpr (GhcPass id) -> LHsExpr (GhcPass id)
appAp LHsExpr (GhcPass id)
x LHsExpr (GhcPass id)
y = IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id)
forall (id :: Pass).
IdP (GhcPass id) -> [LHsExpr (GhcPass id)] -> LHsExpr (GhcPass id)
nlHsApps RdrName
IdP (GhcPass id)
ap_RDR [LHsExpr (GhcPass id)
x,LHsExpr (GhcPass id)
y]

-----------------------------------------------------------------------

f_Expr, z_Expr, fmap_Expr, replace_Expr, mempty_Expr, foldMap_Expr,
    traverse_Expr, coerce_Expr, pure_Expr, true_Expr, false_Expr,
    all_Expr, null_Expr :: LHsExpr GhcPs
f_Expr :: LHsExpr GhcPs
f_Expr        = IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
f_RDR
z_Expr :: LHsExpr GhcPs
z_Expr        = IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
z_RDR
fmap_Expr :: LHsExpr GhcPs
fmap_Expr     = IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
fmap_RDR
replace_Expr :: LHsExpr GhcPs
replace_Expr  = IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
replace_RDR
mempty_Expr :: LHsExpr GhcPs
mempty_Expr   = IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
mempty_RDR
foldMap_Expr :: LHsExpr GhcPs
foldMap_Expr  = IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
foldMap_RDR
traverse_Expr :: LHsExpr GhcPs
traverse_Expr = IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
traverse_RDR
coerce_Expr :: LHsExpr GhcPs
coerce_Expr   = IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar (TcTyVar -> RdrName
forall thing. NamedThing thing => thing -> RdrName
getRdrName TcTyVar
coerceId)
pure_Expr :: LHsExpr GhcPs
pure_Expr     = IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
pure_RDR
true_Expr :: LHsExpr GhcPs
true_Expr     = IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
true_RDR
false_Expr :: LHsExpr GhcPs
false_Expr    = IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
false_RDR
all_Expr :: LHsExpr GhcPs
all_Expr      = IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
all_RDR
null_Expr :: LHsExpr GhcPs
null_Expr     = IdP GhcPs -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar RdrName
IdP GhcPs
null_RDR

f_RDR, z_RDR :: RdrName
f_RDR :: RdrName
f_RDR = FastString -> RdrName
mkVarUnqual (String -> FastString
fsLit String
"f")
z_RDR :: RdrName
z_RDR = FastString -> RdrName
mkVarUnqual (String -> FastString
fsLit String
"z")

as_RDRs, bs_RDRs :: [RdrName]
as_RDRs :: [RdrName]
as_RDRs = [ FastString -> RdrName
mkVarUnqual (String -> FastString
mkFastString (String
"a"String -> String -> String
forall a. [a] -> [a] -> [a]
++Arity -> String
forall a. Show a => a -> String
show Arity
i)) | Arity
i <- [(Arity
1::Int) .. ] ]
bs_RDRs :: [RdrName]
bs_RDRs = [ FastString -> RdrName
mkVarUnqual (String -> FastString
mkFastString (String
"b"String -> String -> String
forall a. [a] -> [a] -> [a]
++Arity -> String
forall a. Show a => a -> String
show Arity
i)) | Arity
i <- [(Arity
1::Int) .. ] ]

as_Vars, bs_Vars :: [LHsExpr GhcPs]
as_Vars :: [LHsExpr GhcPs]
as_Vars = (RdrName -> LHsExpr GhcPs) -> [RdrName] -> [LHsExpr GhcPs]
forall a b. (a -> b) -> [a] -> [b]
map RdrName -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar [RdrName]
as_RDRs
bs_Vars :: [LHsExpr GhcPs]
bs_Vars = (RdrName -> LHsExpr GhcPs) -> [RdrName] -> [LHsExpr GhcPs]
forall a b. (a -> b) -> [a] -> [b]
map RdrName -> LHsExpr GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LHsExpr (GhcPass id)
nlHsVar [RdrName]
bs_RDRs

f_Pat, z_Pat :: LPat GhcPs
f_Pat :: LPat GhcPs
f_Pat = IdP GhcPs -> LPat GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LPat (GhcPass id)
nlVarPat RdrName
IdP GhcPs
f_RDR
z_Pat :: LPat GhcPs
z_Pat = IdP GhcPs -> LPat GhcPs
forall (id :: Pass). IdP (GhcPass id) -> LPat (GhcPass id)
nlVarPat RdrName
IdP GhcPs
z_RDR

{-
Note [DeriveFoldable with ExistentialQuantification]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Functor and Traversable instances can only be derived for data types whose
last type parameter is truly universally polymorphic. For example:

  data T a b where
    T1 ::                 b   -> T a b   -- YES, b is unconstrained
    T2 :: Ord b   =>      b   -> T a b   -- NO, b is constrained by (Ord b)
    T3 :: b ~ Int =>      b   -> T a b   -- NO, b is constrained by (b ~ Int)
    T4 ::                 Int -> T a Int -- NO, this is just like T3
    T5 :: Ord a   => a -> b   -> T a b   -- YES, b is unconstrained, even
                                         -- though a is existential
    T6 ::                 Int -> T Int b -- YES, b is unconstrained

For Foldable instances, however, we can completely lift the constraint that
the last type parameter be truly universally polymorphic. This means that T
(as defined above) can have a derived Foldable instance:

  instance Foldable (T a) where
    foldr f z (T1 b)   = f b z
    foldr f z (T2 b)   = f b z
    foldr f z (T3 b)   = f b z
    foldr f z (T4 b)   = z
    foldr f z (T5 a b) = f b z
    foldr f z (T6 a)   = z

    foldMap f (T1 b)   = f b
    foldMap f (T2 b)   = f b
    foldMap f (T3 b)   = f b
    foldMap f (T4 b)   = mempty
    foldMap f (T5 a b) = f b
    foldMap f (T6 a)   = mempty

In a Foldable instance, it is safe to fold over an occurrence of the last type
parameter that is not truly universally polymorphic. However, there is a bit
of subtlety in determining what is actually an occurrence of a type parameter.
T3 and T4, as defined above, provide one example:

  data T a b where
    ...
    T3 :: b ~ Int => b   -> T a b
    T4 ::            Int -> T a Int
    ...

  instance Foldable (T a) where
    ...
    foldr f z (T3 b) = f b z
    foldr f z (T4 b) = z
    ...
    foldMap f (T3 b) = f b
    foldMap f (T4 b) = mempty
    ...

Notice that the argument of T3 is folded over, whereas the argument of T4 is
not. This is because we only fold over constructor arguments that
syntactically mention the universally quantified type parameter of that
particular data constructor. See foldDataConArgs for how this is implemented.

As another example, consider the following data type. The argument of each
constructor has the same type as the last type parameter:

  data E a where
    E1 :: (a ~ Int) => a   -> E a
    E2 ::              Int -> E Int
    E3 :: (a ~ Int) => a   -> E Int
    E4 :: (a ~ Int) => Int -> E a

Only E1's argument is an occurrence of a universally quantified type variable
that is syntactically equivalent to the last type parameter, so only E1's
argument will be folded over in a derived Foldable instance.

See #10447 for the original discussion on this feature. Also see
https://gitlab.haskell.org/ghc/ghc/wikis/commentary/compiler/derive-functor
for a more in-depth explanation.

Note [FFoldType and functorLikeTraverse]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Deriving Functor, Foldable, and Traversable all require generating expressions
which perform an operation on each argument of a data constructor depending
on the argument's type. In particular, a generated operation can be different
depending on whether the type mentions the last type variable of the datatype
(e.g., if you have data T a = MkT a Int, then a generated foldr expression would
fold over the first argument of MkT, but not the second).

This pattern is abstracted with the FFoldType datatype, which provides hooks
for the user to specify how a constructor argument should be folded when it
has a type with a particular "shape". The shapes are as follows (assume that
a is the last type variable in a given datatype):

* ft_triv:    The type does not mention the last type variable at all.
              Examples: Int, b

* ft_var:     The type is syntactically equal to the last type variable.
              Moreover, the type appears in a covariant position (see
              the Deriving Functor instances section of the user's guide
              for an in-depth explanation of covariance vs. contravariance).
              Example: a (covariantly)

* ft_co_var:  The type is syntactically equal to the last type variable.
              Moreover, the type appears in a contravariant position.
              Example: a (contravariantly)

* ft_fun:     A function type which mentions the last type variable in
              the argument position, result position or both.
              Examples: a -> Int, Int -> a, Maybe a -> [a]

* ft_tup:     A tuple type which mentions the last type variable in at least
              one of its fields. The TyCon argument of ft_tup represents the
              particular tuple's type constructor.
              Examples: (a, Int), (Maybe a, [a], Either a Int), (# Int, a #)

* ft_ty_app:  A type is being applied to the last type parameter, where the
              applied type does not mention the last type parameter (if it
              did, it would fall under ft_bad_app). The Type argument to
              ft_ty_app represents the applied type.

              Note that functions, tuples, and foralls are distinct cases
              and take precedence of ft_ty_app. (For example, (Int -> a) would
              fall under (ft_fun Int a), not (ft_ty_app ((->) Int) a).
              Examples: Maybe a, Either b a

* ft_bad_app: A type application uses the last type parameter in a position
              other than the last argument. This case is singled out because
              Functor, Foldable, and Traversable instances cannot be derived
              for datatypes containing arguments with such types.
              Examples: Either a Int, Const a b

* ft_forall:  A forall'd type mentions the last type parameter on its right-
              hand side (and is not quantified on the left-hand side). This
              case is present mostly for plumbing purposes.
              Example: forall b. Either b a

If FFoldType describes a strategy for folding subcomponents of a Type, then
functorLikeTraverse is the function that applies that strategy to the entirety
of a Type, returning the final folded-up result.

foldDataConArgs applies functorLikeTraverse to every argument type of a
constructor, returning a list of the fold results. This makes foldDataConArgs
a natural way to generate the subexpressions in a generated fmap, foldr,
foldMap, or traverse definition (the subexpressions must then be combined in
a method-specific fashion to form the final generated expression).

Deriving Generic1 also does validity checking by looking for the last type
variable in certain positions of a constructor's argument types, so it also
uses foldDataConArgs. See Note [degenerate use of FFoldType] in TcGenGenerics.

Note [Generated code for DeriveFoldable and DeriveTraversable]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
We adapt the algorithms for -XDeriveFoldable and -XDeriveTraversable based on
that of -XDeriveFunctor. However, there an important difference between deriving
the former two typeclasses and the latter one, which is best illustrated by the
following scenario:

  data WithInt a = WithInt a Int# deriving (Functor, Foldable, Traversable)

The generated code for the Functor instance is straightforward:

  instance Functor WithInt where
    fmap f (WithInt a i) = WithInt (f a) i

But if we use too similar of a strategy for deriving the Foldable and
Traversable instances, we end up with this code:

  instance Foldable WithInt where
    foldMap f (WithInt a i) = f a <> mempty

  instance Traversable WithInt where
    traverse f (WithInt a i) = fmap WithInt (f a) <*> pure i

This is unsatisfying for two reasons:

1. The Traversable instance doesn't typecheck! Int# is of kind #, but pure
   expects an argument whose type is of kind *. This effectively prevents
   Traversable from being derived for any datatype with an unlifted argument
   type (#11174).

2. The generated code contains superfluous expressions. By the Monoid laws,
   we can reduce (f a <> mempty) to (f a), and by the Applicative laws, we can
   reduce (fmap WithInt (f a) <*> pure i) to (fmap (\b -> WithInt b i) (f a)).

We can fix both of these issues by incorporating a slight twist to the usual
algorithm that we use for -XDeriveFunctor. The differences can be summarized
as follows:

1. In the generated expression, we only fold over arguments whose types
   mention the last type parameter. Any other argument types will simply
   produce useless 'mempty's or 'pure's, so they can be safely ignored.

2. In the case of -XDeriveTraversable, instead of applying ConName,
   we apply (\b_i ... b_k -> ConName a_1 ... a_n), where

   * ConName has n arguments
   * {b_i, ..., b_k} is a subset of {a_1, ..., a_n} whose indices correspond
     to the arguments whose types mention the last type parameter. As a
     consequence, taking the difference of {a_1, ..., a_n} and
     {b_i, ..., b_k} yields the all the argument values of ConName whose types
     do not mention the last type parameter. Note that [i, ..., k] is a
     strictly increasing—but not necessarily consecutive—integer sequence.

     For example, the datatype

       data Foo a = Foo Int a Int a

     would generate the following Traversable instance:

       instance Traversable Foo where
         traverse f (Foo a1 a2 a3 a4) =
           fmap (\b2 b4 -> Foo a1 b2 a3 b4) (f a2) <*> f a4

Technically, this approach would also work for -XDeriveFunctor as well, but we
decide not to do so because:

1. There's not much benefit to generating, e.g., ((\b -> WithInt b i) (f a))
   instead of (WithInt (f a) i).

2. There would be certain datatypes for which the above strategy would
   generate Functor code that would fail to typecheck. For example:

     data Bar f a = Bar (forall f. Functor f => f a) deriving Functor

   With the conventional algorithm, it would generate something like:

     fmap f (Bar a) = Bar (fmap f a)

   which typechecks. But with the strategy mentioned above, it would generate:

     fmap f (Bar a) = (\b -> Bar b) (fmap f a)

   which does not typecheck, since GHC cannot unify the rank-2 type variables
   in the types of b and (fmap f a).

Note [Phantom types with Functor, Foldable, and Traversable]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Given a type F :: * -> * whose type argument has a phantom role, we can always
produce lawful Functor and Traversable instances using

    fmap _ = coerce
    traverse _ = pure . coerce

Indeed, these are equivalent to any *strictly lawful* instances one could
write, except that this definition of 'traverse' may be lazier.  That is, if
instances obey the laws under true equality (rather than up to some equivalence
relation), then they will be essentially equivalent to these. These definitions
are incredibly cheap, so we want to use them even if it means ignoring some
non-strictly-lawful instance in an embedded type.

Foldable has far fewer laws to work with, which leaves us unwelcome
freedom in implementing it. At a minimum, we would like to ensure that
a derived foldMap is always at least as good as foldMapDefault with a
derived traverse. To accomplish that, we must define

   foldMap _ _ = mempty

in these cases.

This may have different strictness properties from a standard derivation.
Consider

   data NotAList a = Nil | Cons (NotAList a) deriving Foldable

The usual deriving mechanism would produce

   foldMap _ Nil = mempty
   foldMap f (Cons x) = foldMap f x

which is strict in the entire spine of the NotAList.

Final point: why do we even care about such types? Users will rarely if ever
map, fold, or traverse over such things themselves, but other derived
instances may:

   data Hasn'tAList a = NotHere a (NotAList a) deriving Foldable

Note [EmptyDataDecls with Functor, Foldable, and Traversable]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

There are some slightly tricky decisions to make about how to handle
Functor, Foldable, and Traversable instances for types with no constructors.
For fmap, the two basic options are

   fmap _ _ = error "Sorry, no constructors"

or

   fmap _ z = case z of

In most cases, the latter is more helpful: if the thunk passed to fmap
throws an exception, we're generally going to be much more interested in
that exception than in the fact that there aren't any constructors.

In order to match the semantics for phantoms (see note above), we need to
be a bit careful about 'traverse'. The obvious definition would be

   traverse _ z = case z of

but this is stricter than the one for phantoms. We instead use

   traverse _ z = pure $ case z of

For foldMap, the obvious choices are

   foldMap _ _ = mempty

or

   foldMap _ z = case z of

We choose the first one to be consistent with what foldMapDefault does for
a derived Traversable instance.
-}