{- |
    Module      :  $Header$
    Description :  Extraction of free and bound variables
    Copyright   :  (c)             Wolfgang Lux
                       2011 - 2015 Björn Peemöller
                       2015        Jan Tikovsky
                       2016        Finn Teegen
    License     :  BSD-3-clause

    Maintainer  :  bjp@informatik.uni-kiel.de
    Stability   :  experimental
    Portability :  portable

    The compiler needs to compute the lists of free and bound variables for
    various different entities. We will devote three type classes to that
    purpose. The 'QualExpr' class is expected to take into account
    that it is possible to use a qualified name to refer to a function
    defined in the current module and therefore @M.x@ and @x@, where
    @M@ is the current module name, should be considered the same name.
    However, note that this is correct only after renaming all local
    definitions as @M.x@ always denotes an entity defined at the
    top-level.
-}
module Base.Expr (Expr (..), QualExpr (..), QuantExpr (..)) where

import           Data.List        (nub)
import qualified Data.Set  as Set (fromList, notMember)

import Curry.Base.Ident
import Curry.Base.SpanInfo
import Curry.Syntax

class Expr e where
  -- |Free variables in an 'Expr'
  fv :: e -> [Ident]

class QualExpr e where
  -- |Free qualified variables in an 'Expr'
  qfv :: ModuleIdent -> e -> [Ident]

class QuantExpr e where
  -- |Bounded variables in an 'Expr'
  bv :: e -> [Ident]

instance Expr e => Expr [e] where
  fv :: [e] -> [Ident]
fv = (e -> [Ident]) -> [e] -> [Ident]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap e -> [Ident]
forall e. Expr e => e -> [Ident]
fv

instance QualExpr e => QualExpr [e] where
  qfv :: ModuleIdent -> [e] -> [Ident]
qfv m :: ModuleIdent
m = (e -> [Ident]) -> [e] -> [Ident]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (ModuleIdent -> e -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m)

instance QuantExpr e => QuantExpr [e] where
  bv :: [e] -> [Ident]
bv = (e -> [Ident]) -> [e] -> [Ident]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap e -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv

-- The 'Decl' instance of 'QualExpr' returns all free
-- variables on the right hand side, regardless of whether they are bound
-- on the left hand side. This is more convenient as declarations are
-- usually processed in a declaration group where the set of free
-- variables cannot be computed independently for each declaration.

instance QualExpr (Decl a) where
  qfv :: ModuleIdent -> Decl a -> [Ident]
qfv m :: ModuleIdent
m (FunctionDecl    _ _ _ eqs :: [Equation a]
eqs) = ModuleIdent -> [Equation a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Equation a]
eqs
  qfv m :: ModuleIdent
m (PatternDecl       _ _ rhs :: Rhs a
rhs) = ModuleIdent -> Rhs a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Rhs a
rhs
  qfv m :: ModuleIdent
m (ClassDecl    _ _ _ _ _ ds :: [Decl a]
ds) = ModuleIdent -> [Decl a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Decl a]
ds
  qfv m :: ModuleIdent
m (InstanceDecl _ _ _ _ _ ds :: [Decl a]
ds) = ModuleIdent -> [Decl a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Decl a]
ds
  qfv _ _                           = []

instance QuantExpr (Decl a) where
  bv :: Decl a -> [Ident]
bv (TypeSig         _ vs :: [Ident]
vs _) = [Ident]
vs
  bv (FunctionDecl   _ _ f :: Ident
f _) = [Ident
f]
  bv (ExternalDecl      _ vs :: [Var a]
vs) = [Var a] -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv [Var a]
vs
  bv (PatternDecl      _ t :: Pattern a
t _) = Pattern a -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv Pattern a
t
  bv (FreeDecl          _ vs :: [Var a]
vs) = [Var a] -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv [Var a]
vs
  bv (ClassDecl _ _ _ _ _ ds :: [Decl a]
ds) = (Decl a -> [Ident]) -> [Decl a] -> [Ident]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Decl a -> [Ident]
forall a. Decl a -> [Ident]
methods [Decl a]
ds
  bv _                        = []

instance QualExpr (Equation a) where
  qfv :: ModuleIdent -> Equation a -> [Ident]
qfv m :: ModuleIdent
m (Equation _ lhs :: Lhs a
lhs rhs :: Rhs a
rhs) = Lhs a -> [Ident] -> [Ident]
forall e. QuantExpr e => e -> [Ident] -> [Ident]
filterBv Lhs a
lhs ([Ident] -> [Ident]) -> [Ident] -> [Ident]
forall a b. (a -> b) -> a -> b
$ ModuleIdent -> Lhs a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Lhs a
lhs [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> Rhs a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Rhs a
rhs

instance QuantExpr (Lhs a) where
  bv :: Lhs a -> [Ident]
bv = [Pattern a] -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv ([Pattern a] -> [Ident])
-> (Lhs a -> [Pattern a]) -> Lhs a -> [Ident]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Ident, [Pattern a]) -> [Pattern a]
forall a b. (a, b) -> b
snd ((Ident, [Pattern a]) -> [Pattern a])
-> (Lhs a -> (Ident, [Pattern a])) -> Lhs a -> [Pattern a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Lhs a -> (Ident, [Pattern a])
forall a. Lhs a -> (Ident, [Pattern a])
flatLhs

instance QualExpr (Lhs a) where
  qfv :: ModuleIdent -> Lhs a -> [Ident]
qfv m :: ModuleIdent
m lhs :: Lhs a
lhs = ModuleIdent -> [Pattern a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m ([Pattern a] -> [Ident]) -> [Pattern a] -> [Ident]
forall a b. (a -> b) -> a -> b
$ (Ident, [Pattern a]) -> [Pattern a]
forall a b. (a, b) -> b
snd ((Ident, [Pattern a]) -> [Pattern a])
-> (Ident, [Pattern a]) -> [Pattern a]
forall a b. (a -> b) -> a -> b
$ Lhs a -> (Ident, [Pattern a])
forall a. Lhs a -> (Ident, [Pattern a])
flatLhs Lhs a
lhs

instance QualExpr (Rhs a) where
  qfv :: ModuleIdent -> Rhs a -> [Ident]
qfv m :: ModuleIdent
m (SimpleRhs  _ _ e :: Expression a
e  ds :: [Decl a]
ds) = [Decl a] -> [Ident] -> [Ident]
forall e. QuantExpr e => e -> [Ident] -> [Ident]
filterBv [Decl a]
ds ([Ident] -> [Ident]) -> [Ident] -> [Ident]
forall a b. (a -> b) -> a -> b
$ ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e  [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> [Decl a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Decl a]
ds
  qfv m :: ModuleIdent
m (GuardedRhs _ _ es :: [CondExpr a]
es ds :: [Decl a]
ds) = [Decl a] -> [Ident] -> [Ident]
forall e. QuantExpr e => e -> [Ident] -> [Ident]
filterBv [Decl a]
ds ([Ident] -> [Ident]) -> [Ident] -> [Ident]
forall a b. (a -> b) -> a -> b
$ ModuleIdent -> [CondExpr a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [CondExpr a]
es [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> [Decl a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Decl a]
ds

instance QualExpr (CondExpr a) where
  qfv :: ModuleIdent -> CondExpr a -> [Ident]
qfv m :: ModuleIdent
m (CondExpr _ g :: Expression a
g e :: Expression a
e) = ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
g [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e

instance QualExpr (Expression a) where
  qfv :: ModuleIdent -> Expression a -> [Ident]
qfv _ (Literal             _ _ _) = []
  qfv m :: ModuleIdent
m (Variable            _ _ v :: QualIdent
v) = [Ident] -> (Ident -> [Ident]) -> Maybe Ident -> [Ident]
forall b a. b -> (a -> b) -> Maybe a -> b
maybe [] Ident -> [Ident]
forall (m :: * -> *) a. Monad m => a -> m a
return (Maybe Ident -> [Ident]) -> Maybe Ident -> [Ident]
forall a b. (a -> b) -> a -> b
$ ModuleIdent -> QualIdent -> Maybe Ident
localIdent ModuleIdent
m QualIdent
v
  qfv _ (Constructor         _ _ _) = []
  qfv m :: ModuleIdent
m (Paren               _   e :: Expression a
e) = ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e
  qfv m :: ModuleIdent
m (Typed               _ e :: Expression a
e _) = ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e
  qfv m :: ModuleIdent
m (Record           _ _ _ fs :: [Field (Expression a)]
fs) = ModuleIdent -> [Field (Expression a)] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Field (Expression a)]
fs
  qfv m :: ModuleIdent
m (RecordUpdate       _ e :: Expression a
e fs :: [Field (Expression a)]
fs) = ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> [Field (Expression a)] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Field (Expression a)]
fs
  qfv m :: ModuleIdent
m (Tuple                _ es :: [Expression a]
es) = ModuleIdent -> [Expression a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Expression a]
es
  qfv m :: ModuleIdent
m (List               _ _ es :: [Expression a]
es) = ModuleIdent -> [Expression a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Expression a]
es
  qfv m :: ModuleIdent
m (ListCompr          _ e :: Expression a
e qs :: [Statement a]
qs) = (Statement a -> [Ident] -> [Ident])
-> [Ident] -> [Statement a] -> [Ident]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (ModuleIdent -> Statement a -> [Ident] -> [Ident]
forall a. ModuleIdent -> Statement a -> [Ident] -> [Ident]
qfvStmt ModuleIdent
m) (ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e) [Statement a]
qs
  qfv m :: ModuleIdent
m (EnumFrom              _ e :: Expression a
e) = ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e
  qfv m :: ModuleIdent
m (EnumFromThen      _ e1 :: Expression a
e1 e2 :: Expression a
e2) = ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e1 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e2
  qfv m :: ModuleIdent
m (EnumFromTo        _ e1 :: Expression a
e1 e2 :: Expression a
e2) = ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e1 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e2
  qfv m :: ModuleIdent
m (EnumFromThenTo _ e1 :: Expression a
e1 e2 :: Expression a
e2 e3 :: Expression a
e3) = ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e1 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e2 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e3
  qfv m :: ModuleIdent
m (UnaryMinus            _ e :: Expression a
e) = ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e
  qfv m :: ModuleIdent
m (Apply             _ e1 :: Expression a
e1 e2 :: Expression a
e2) = ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e1 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e2
  qfv m :: ModuleIdent
m (InfixApply     _ e1 :: Expression a
e1 op :: InfixOp a
op e2 :: Expression a
e2) = ModuleIdent -> InfixOp a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m InfixOp a
op [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e1 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e2
  qfv m :: ModuleIdent
m (LeftSection        _ e :: Expression a
e op :: InfixOp a
op) = ModuleIdent -> InfixOp a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m InfixOp a
op [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e
  qfv m :: ModuleIdent
m (RightSection       _ op :: InfixOp a
op e :: Expression a
e) = ModuleIdent -> InfixOp a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m InfixOp a
op [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e
  qfv m :: ModuleIdent
m (Lambda             _ ts :: [Pattern a]
ts e :: Expression a
e) = [Pattern a] -> [Ident] -> [Ident]
forall e. QuantExpr e => e -> [Ident] -> [Ident]
filterBv [Pattern a]
ts ([Ident] -> [Ident]) -> [Ident] -> [Ident]
forall a b. (a -> b) -> a -> b
$ ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e
  qfv m :: ModuleIdent
m (Let              _ _ ds :: [Decl a]
ds e :: Expression a
e) = [Decl a] -> [Ident] -> [Ident]
forall e. QuantExpr e => e -> [Ident] -> [Ident]
filterBv [Decl a]
ds ([Ident] -> [Ident]) -> [Ident] -> [Ident]
forall a b. (a -> b) -> a -> b
$ ModuleIdent -> [Decl a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Decl a]
ds [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e
  qfv m :: ModuleIdent
m (Do              _ _ sts :: [Statement a]
sts e :: Expression a
e) = (Statement a -> [Ident] -> [Ident])
-> [Ident] -> [Statement a] -> [Ident]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (ModuleIdent -> Statement a -> [Ident] -> [Ident]
forall a. ModuleIdent -> Statement a -> [Ident] -> [Ident]
qfvStmt ModuleIdent
m) (ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e) [Statement a]
sts
  qfv m :: ModuleIdent
m (IfThenElse     _ e1 :: Expression a
e1 e2 :: Expression a
e2 e3 :: Expression a
e3) = ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e1 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e2 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e3
  qfv m :: ModuleIdent
m (Case         _ _ _ e :: Expression a
e alts :: [Alt a]
alts) = ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> [Alt a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Alt a]
alts

qfvStmt :: ModuleIdent -> (Statement a) -> [Ident] -> [Ident]
qfvStmt :: ModuleIdent -> Statement a -> [Ident] -> [Ident]
qfvStmt m :: ModuleIdent
m st :: Statement a
st fvs :: [Ident]
fvs = ModuleIdent -> Statement a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Statement a
st [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ Statement a -> [Ident] -> [Ident]
forall e. QuantExpr e => e -> [Ident] -> [Ident]
filterBv Statement a
st [Ident]
fvs

instance QualExpr (Statement a) where
  qfv :: ModuleIdent -> Statement a -> [Ident]
qfv m :: ModuleIdent
m (StmtExpr   _ e :: Expression a
e)  = ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e
  qfv m :: ModuleIdent
m (StmtDecl _ _ ds :: [Decl a]
ds) = [Decl a] -> [Ident] -> [Ident]
forall e. QuantExpr e => e -> [Ident] -> [Ident]
filterBv [Decl a]
ds ([Ident] -> [Ident]) -> [Ident] -> [Ident]
forall a b. (a -> b) -> a -> b
$ ModuleIdent -> [Decl a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Decl a]
ds
  qfv m :: ModuleIdent
m (StmtBind _ _ e :: Expression a
e)  = ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Expression a
e

instance QualExpr (Alt a) where
  qfv :: ModuleIdent -> Alt a -> [Ident]
qfv m :: ModuleIdent
m (Alt _ t :: Pattern a
t rhs :: Rhs a
rhs) = Pattern a -> [Ident] -> [Ident]
forall e. QuantExpr e => e -> [Ident] -> [Ident]
filterBv Pattern a
t ([Ident] -> [Ident]) -> [Ident] -> [Ident]
forall a b. (a -> b) -> a -> b
$ ModuleIdent -> Rhs a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Rhs a
rhs

instance QuantExpr (Var a) where
  bv :: Var a -> [Ident]
bv (Var _ v :: Ident
v) = [Ident
v]

instance QuantExpr a => QuantExpr (Field a) where
  bv :: Field a -> [Ident]
bv (Field _ _ t :: a
t) = a -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv a
t

instance QualExpr a => QualExpr (Field a) where
  qfv :: ModuleIdent -> Field a -> [Ident]
qfv m :: ModuleIdent
m (Field _ _ t :: a
t) = ModuleIdent -> a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m a
t

instance QuantExpr (Statement a) where
  bv :: Statement a -> [Ident]
bv (StmtExpr   _ _)  = []
  bv (StmtBind _ t :: Pattern a
t _)  = Pattern a -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv Pattern a
t
  bv (StmtDecl _ _ ds :: [Decl a]
ds) = [Decl a] -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv [Decl a]
ds

instance QualExpr (InfixOp a) where
  qfv :: ModuleIdent -> InfixOp a -> [Ident]
qfv m :: ModuleIdent
m (InfixOp     a :: a
a op :: QualIdent
op) = ModuleIdent -> Expression a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m (Expression a -> [Ident]) -> Expression a -> [Ident]
forall a b. (a -> b) -> a -> b
$ SpanInfo -> a -> QualIdent -> Expression a
forall a. SpanInfo -> a -> QualIdent -> Expression a
Variable SpanInfo
NoSpanInfo a
a QualIdent
op
  qfv _ (InfixConstr _ _ ) = []

instance QuantExpr (Pattern a) where
  bv :: Pattern a -> [Ident]
bv (LiteralPattern         _ _ _) = []
  bv (NegativePattern        _ _ _) = []
  bv (VariablePattern        _ _ v :: Ident
v) = [Ident
v]
  bv (ConstructorPattern  _ _ _ ts :: [Pattern a]
ts) = [Pattern a] -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv [Pattern a]
ts
  bv (InfixPattern     _ _ t1 :: Pattern a
t1 _ t2 :: Pattern a
t2) = Pattern a -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv Pattern a
t1 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ Pattern a -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv Pattern a
t2
  bv (ParenPattern             _ t :: Pattern a
t) = Pattern a -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv Pattern a
t
  bv (RecordPattern       _ _ _ fs :: [Field (Pattern a)]
fs) = [Field (Pattern a)] -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv [Field (Pattern a)]
fs
  bv (TuplePattern           _  ts :: [Pattern a]
ts) = [Pattern a] -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv [Pattern a]
ts
  bv (ListPattern          _  _ ts :: [Pattern a]
ts) = [Pattern a] -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv [Pattern a]
ts
  bv (AsPattern              _ v :: Ident
v t :: Pattern a
t) = Ident
v Ident -> [Ident] -> [Ident]
forall a. a -> [a] -> [a]
: Pattern a -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv Pattern a
t
  bv (LazyPattern              _ t :: Pattern a
t) = Pattern a -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv Pattern a
t
  bv (FunctionPattern     _ _ _ ts :: [Pattern a]
ts) = [Ident] -> [Ident]
forall a. Eq a => [a] -> [a]
nub ([Ident] -> [Ident]) -> [Ident] -> [Ident]
forall a b. (a -> b) -> a -> b
$ [Pattern a] -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv [Pattern a]
ts
  bv (InfixFuncPattern _ _ t1 :: Pattern a
t1 _ t2 :: Pattern a
t2) = [Ident] -> [Ident]
forall a. Eq a => [a] -> [a]
nub ([Ident] -> [Ident]) -> [Ident] -> [Ident]
forall a b. (a -> b) -> a -> b
$ Pattern a -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv Pattern a
t1 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ Pattern a -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv Pattern a
t2

instance QualExpr (Pattern a) where
  qfv :: ModuleIdent -> Pattern a -> [Ident]
qfv _ (LiteralPattern          _ _ _) = []
  qfv _ (NegativePattern         _ _ _) = []
  qfv _ (VariablePattern         _ _ _) = []
  qfv m :: ModuleIdent
m (ConstructorPattern   _ _ _ ts :: [Pattern a]
ts) = ModuleIdent -> [Pattern a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Pattern a]
ts
  qfv m :: ModuleIdent
m (InfixPattern      _ _ t1 :: Pattern a
t1 _ t2 :: Pattern a
t2) = ModuleIdent -> [Pattern a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Pattern a
t1, Pattern a
t2]
  qfv m :: ModuleIdent
m (ParenPattern              _ t :: Pattern a
t) = ModuleIdent -> Pattern a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Pattern a
t
  qfv m :: ModuleIdent
m (RecordPattern        _ _ _ fs :: [Field (Pattern a)]
fs) = ModuleIdent -> [Field (Pattern a)] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Field (Pattern a)]
fs
  qfv m :: ModuleIdent
m (TuplePattern             _ ts :: [Pattern a]
ts) = ModuleIdent -> [Pattern a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Pattern a]
ts
  qfv m :: ModuleIdent
m (ListPattern            _ _ ts :: [Pattern a]
ts) = ModuleIdent -> [Pattern a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Pattern a]
ts
  qfv m :: ModuleIdent
m (AsPattern              _ _ ts :: Pattern a
ts) = ModuleIdent -> Pattern a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Pattern a
ts
  qfv m :: ModuleIdent
m (LazyPattern               _ t :: Pattern a
t) = ModuleIdent -> Pattern a -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m Pattern a
t
  qfv m :: ModuleIdent
m (FunctionPattern      _ _ f :: QualIdent
f ts :: [Pattern a]
ts)
    = [Ident] -> (Ident -> [Ident]) -> Maybe Ident -> [Ident]
forall b a. b -> (a -> b) -> Maybe a -> b
maybe [] Ident -> [Ident]
forall (m :: * -> *) a. Monad m => a -> m a
return (ModuleIdent -> QualIdent -> Maybe Ident
localIdent ModuleIdent
m QualIdent
f) [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> [Pattern a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Pattern a]
ts
  qfv m :: ModuleIdent
m (InfixFuncPattern _ _ t1 :: Pattern a
t1 op :: QualIdent
op t2 :: Pattern a
t2)
    = [Ident] -> (Ident -> [Ident]) -> Maybe Ident -> [Ident]
forall b a. b -> (a -> b) -> Maybe a -> b
maybe [] Ident -> [Ident]
forall (m :: * -> *) a. Monad m => a -> m a
return (ModuleIdent -> QualIdent -> Maybe Ident
localIdent ModuleIdent
m QualIdent
op) [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ ModuleIdent -> [Pattern a] -> [Ident]
forall e. QualExpr e => ModuleIdent -> e -> [Ident]
qfv ModuleIdent
m [Pattern a
t1, Pattern a
t2]

instance Expr Constraint where
  fv :: Constraint -> [Ident]
fv (Constraint _ _ ty :: TypeExpr
ty) = TypeExpr -> [Ident]
forall e. Expr e => e -> [Ident]
fv TypeExpr
ty

instance QuantExpr Constraint where
  bv :: Constraint -> [Ident]
bv _ = []

instance Expr QualTypeExpr where
  fv :: QualTypeExpr -> [Ident]
fv (QualTypeExpr _ _ ty :: TypeExpr
ty) = TypeExpr -> [Ident]
forall e. Expr e => e -> [Ident]
fv TypeExpr
ty

instance QuantExpr QualTypeExpr where
  bv :: QualTypeExpr -> [Ident]
bv (QualTypeExpr _ _ ty :: TypeExpr
ty) = TypeExpr -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv TypeExpr
ty

instance Expr TypeExpr where
  fv :: TypeExpr -> [Ident]
fv (ConstructorType     _ _) = []
  fv (ApplyType     _ ty1 :: TypeExpr
ty1 ty2 :: TypeExpr
ty2) = TypeExpr -> [Ident]
forall e. Expr e => e -> [Ident]
fv TypeExpr
ty1 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ TypeExpr -> [Ident]
forall e. Expr e => e -> [Ident]
fv TypeExpr
ty2
  fv (VariableType       _ tv :: Ident
tv) = [Ident
tv]
  fv (TupleType         _ tys :: [TypeExpr]
tys) = [TypeExpr] -> [Ident]
forall e. Expr e => e -> [Ident]
fv [TypeExpr]
tys
  fv (ListType          _  ty :: TypeExpr
ty) = TypeExpr -> [Ident]
forall e. Expr e => e -> [Ident]
fv TypeExpr
ty
  fv (ArrowType     _ ty1 :: TypeExpr
ty1 ty2 :: TypeExpr
ty2) = TypeExpr -> [Ident]
forall e. Expr e => e -> [Ident]
fv TypeExpr
ty1 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ TypeExpr -> [Ident]
forall e. Expr e => e -> [Ident]
fv TypeExpr
ty2
  fv (ParenType          _ ty :: TypeExpr
ty) = TypeExpr -> [Ident]
forall e. Expr e => e -> [Ident]
fv TypeExpr
ty
  fv (ForallType      _ vs :: [Ident]
vs ty :: TypeExpr
ty) = (Ident -> Bool) -> [Ident] -> [Ident]
forall a. (a -> Bool) -> [a] -> [a]
filter (Ident -> [Ident] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`notElem` [Ident]
vs) ([Ident] -> [Ident]) -> [Ident] -> [Ident]
forall a b. (a -> b) -> a -> b
$ TypeExpr -> [Ident]
forall e. Expr e => e -> [Ident]
fv TypeExpr
ty

instance QuantExpr TypeExpr where
  bv :: TypeExpr -> [Ident]
bv (ConstructorType     _ _) = []
  bv (ApplyType     _ ty1 :: TypeExpr
ty1 ty2 :: TypeExpr
ty2) = TypeExpr -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv TypeExpr
ty1 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ TypeExpr -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv TypeExpr
ty2
  bv (VariableType        _ _) = []
  bv (TupleType         _ tys :: [TypeExpr]
tys) = [TypeExpr] -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv [TypeExpr]
tys
  bv (ListType           _ ty :: TypeExpr
ty) = TypeExpr -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv TypeExpr
ty
  bv (ArrowType     _ ty1 :: TypeExpr
ty1 ty2 :: TypeExpr
ty2) = TypeExpr -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv TypeExpr
ty1 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ TypeExpr -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv TypeExpr
ty2
  bv (ParenType          _ ty :: TypeExpr
ty) = TypeExpr -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv TypeExpr
ty
  bv (ForallType     _ tvs :: [Ident]
tvs ty :: TypeExpr
ty) = [Ident]
tvs [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ TypeExpr -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv TypeExpr
ty

filterBv :: QuantExpr e => e -> [Ident] -> [Ident]
filterBv :: e -> [Ident] -> [Ident]
filterBv e :: e
e = (Ident -> Bool) -> [Ident] -> [Ident]
forall a. (a -> Bool) -> [a] -> [a]
filter (Ident -> Set Ident -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.notMember` [Ident] -> Set Ident
forall a. Ord a => [a] -> Set a
Set.fromList (e -> [Ident]
forall e. QuantExpr e => e -> [Ident]
bv e
e))