{-# LANGUAGE LambdaCase #-}

-- |
-- Module      : Jikka.Converter.Core.FreeVars
-- Description : provides utilities aboud free variables. / 自由変数についてのユーティリティを提供します。
-- Copyright   : (c) Kimiyuki Onaka, 2020
-- License     : Apache License 2.0
-- Maintainer  : kimiyuki95@gmail.com
-- Stability   : experimental
-- Portability : portable
module Jikka.Core.Language.FreeVars where

import Jikka.Core.Language.Expr

-- | `isFreeVar` checks if the given variable occurs in the tiven expr. This considers contexts.
--
-- >>> VarName "x" `isFreeVar` Lam (VarName "y") IntTy (Var (VarName "x"))
-- True
--
-- >>> VarName "x" `isFreeVar` Lam (VarName "x") IntTy (Var (VarName "x"))
-- False
isFreeVar :: VarName -> Expr -> Bool
isFreeVar :: VarName -> Expr -> Bool
isFreeVar VarName
x = \case
  Var VarName
y -> VarName
y VarName -> VarName -> Bool
forall a. Eq a => a -> a -> Bool
== VarName
x
  Lit Literal
_ -> Bool
False
  App Expr
f Expr
e -> VarName -> Expr -> Bool
isFreeVar VarName
x Expr
f Bool -> Bool -> Bool
|| VarName -> Expr -> Bool
isFreeVar VarName
x Expr
e
  Lam VarName
y Type
_ Expr
e -> VarName
x VarName -> VarName -> Bool
forall a. Eq a => a -> a -> Bool
/= VarName
y Bool -> Bool -> Bool
&& VarName -> Expr -> Bool
isFreeVar VarName
x Expr
e
  Let VarName
y Type
_ Expr
e1 Expr
e2 -> (VarName
y VarName -> VarName -> Bool
forall a. Eq a => a -> a -> Bool
/= VarName
x Bool -> Bool -> Bool
&& VarName -> Expr -> Bool
isFreeVar VarName
x Expr
e1) Bool -> Bool -> Bool
|| VarName -> Expr -> Bool
isFreeVar VarName
x Expr
e2

-- | `isUnusedVar` is the negation of `isFreeVar`.
--
-- TODO: rename to `isNonFreeVar`?
isUnusedVar :: VarName -> Expr -> Bool
isUnusedVar :: VarName -> Expr -> Bool
isUnusedVar VarName
x Expr
e = Bool -> Bool
not (VarName -> Expr -> Bool
isFreeVar VarName
x Expr
e)

-- | `isFreeVarOrScopedVar` checks if the given variable occurs in the tiven expr. This ignores contexts.
--
-- >>> VarName "x" `isFreeVarOrScopedVar` Lam (VarName "x") IntTy (Var (VarName "y"))
-- True
isFreeVarOrScopedVar :: VarName -> Expr -> Bool
isFreeVarOrScopedVar :: VarName -> Expr -> Bool
isFreeVarOrScopedVar VarName
x = \case
  Var VarName
y -> VarName
y VarName -> VarName -> Bool
forall a. Eq a => a -> a -> Bool
== VarName
x
  Lit Literal
_ -> Bool
False
  App Expr
f Expr
e -> VarName -> Expr -> Bool
isFreeVarOrScopedVar VarName
x Expr
f Bool -> Bool -> Bool
|| VarName -> Expr -> Bool
isFreeVarOrScopedVar VarName
x Expr
e
  Lam VarName
y Type
_ Expr
e -> VarName
x VarName -> VarName -> Bool
forall a. Eq a => a -> a -> Bool
== VarName
y Bool -> Bool -> Bool
|| VarName -> Expr -> Bool
isFreeVarOrScopedVar VarName
x Expr
e
  Let VarName
y Type
_ Expr
e1 Expr
e2 -> VarName
y VarName -> VarName -> Bool
forall a. Eq a => a -> a -> Bool
== VarName
x Bool -> Bool -> Bool
|| VarName -> Expr -> Bool
isFreeVarOrScopedVar VarName
x Expr
e1 Bool -> Bool -> Bool
|| VarName -> Expr -> Bool
isFreeVarOrScopedVar VarName
x Expr
e2

freeTyVars :: Type -> [TypeName]
freeTyVars :: Type -> [TypeName]
freeTyVars = \case
  VarTy TypeName
x -> [TypeName
x]
  Type
IntTy -> []
  Type
BoolTy -> []
  ListTy Type
t -> Type -> [TypeName]
freeTyVars Type
t
  TupleTy [Type]
ts -> (Type -> [TypeName]) -> [Type] -> [TypeName]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Type -> [TypeName]
freeTyVars [Type]
ts
  FunTy Type
t1 Type
t2 -> Type -> [TypeName]
freeTyVars Type
t1 [TypeName] -> [TypeName] -> [TypeName]
forall a. [a] -> [a] -> [a]
++ Type -> [TypeName]
freeTyVars Type
t2
  DataStructureTy DataStructure
_ -> []

findUnusedVarName :: VarName -> Expr -> VarName
findUnusedVarName :: VarName -> Expr -> VarName
findUnusedVarName (VarName String
x) Expr
e = [VarName] -> VarName
forall a. [a] -> a
head ([VarName] -> VarName)
-> ([VarName] -> [VarName]) -> [VarName] -> VarName
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (VarName -> Bool) -> [VarName] -> [VarName]
forall a. (a -> Bool) -> [a] -> [a]
filter (VarName -> Expr -> Bool
`isUnusedVar` Expr
e) ([VarName] -> VarName) -> [VarName] -> VarName
forall a b. (a -> b) -> a -> b
$ (Integer -> VarName) -> [Integer] -> [VarName]
forall a b. (a -> b) -> [a] -> [b]
map (\Integer
i -> String -> VarName
VarName (String
x String -> String -> String
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. Show a => a -> String
show Integer
i)) [Integer
0 ..]

findUnusedVarName' :: Expr -> VarName
findUnusedVarName' :: Expr -> VarName
findUnusedVarName' = VarName -> Expr -> VarName
findUnusedVarName (String -> VarName
VarName String
"x")