module Unison.Typechecker.Context.Structure
(
Element (..),
variable,
declares,
Context,
context0,
elements,
CtxSegment,
Scope (..),
scopeOf,
existentialIn,
universalIn,
ordered,
lookupElement,
lookupSolved,
lookupAnn,
annotations,
inconsistent,
apply,
applySegment,
unsolvedExistentials,
existentialVars,
recorded,
BadContext (..),
Rejected (..),
extend,
extends,
replace,
retract,
markRetained,
)
where
import Data.FingerTree (FingerTree, Measured (..), SearchResult (..), search, (<|), (><), (|>))
import Data.FingerTree qualified as FT
import Data.Foldable qualified as FO
import Data.List qualified as List
import Data.Map.Strict (Map)
import Data.Map.Strict qualified as Map
import Data.Maybe (listToMaybe, mapMaybe)
import Data.Set (Set)
import Data.Set qualified as Set
import Data.Text qualified as Text
import Data.Word (Word64)
import Unison.ABT qualified as ABT
import Unison.Blank qualified as B
import Unison.PrettyPrintEnv qualified as PPE
import Unison.Syntax.TypePrinter qualified as TP
import Unison.Type qualified as Type
import Unison.Typechecker.TypeVar qualified as TypeVar
import Unison.Var (Var)
import Unison.Var qualified as Var
type Monotype v loc = Type.Monotype (TypeVar v loc) loc
type TypeVar v loc = TypeVar.TypeVar (B.Blank loc) v
type Type v loc = Type.Type (TypeVar v loc) loc
data Context v loc = Context
{ forall v loc. Context v loc -> FingerTree Measure (Entry v loc)
entries :: !(FingerTree Measure (Entry v loc)),
forall v loc. Context v loc -> Word64
counter :: !Word64,
forall v loc. Context v loc -> Map v (Entry v loc)
vars :: !(Map v (Entry v loc)),
forall v loc. Context v loc -> Map v (loc, Type v loc)
anns :: !(Map v (loc, Type v loc)),
forall v loc. Context v loc -> Map v [(CtxPosition, Type v loc)]
refinements :: !(Map v [(CtxPosition, Type v loc)])
}
data Element v loc
=
Var (TypeVar v loc)
|
Solved (B.Blank loc) v (Monotype v loc)
|
Ann v loc (Type v loc)
|
Refined v (Type v loc)
|
Inconsistent v
|
Marker v
variable :: Element v loc -> v
variable :: forall v loc. Element v loc -> v
variable (Var TypeVar v loc
v) = TypeVar v loc -> v
forall b v. TypeVar b v -> v
TypeVar.underlying TypeVar v loc
v
variable (Solved Blank loc
_ v
v Monotype v loc
_) = v
v
variable (Ann v
v loc
_ Type v loc
_) = v
v
variable (Refined v
v Type v loc
_) = v
v
variable (Inconsistent v
v) = v
v
variable (Marker v
v) = v
v
declares :: Element v loc -> Maybe v
declares :: forall v loc. Element v loc -> Maybe v
declares (Refined v
_ Type v loc
_) = Maybe v
forall a. Maybe a
Nothing
declares Element v loc
e = v -> Maybe v
forall a. a -> Maybe a
Just (Element v loc -> v
forall v loc. Element v loc -> v
variable Element v loc
e)
newtype CtxPosition = CtxPosition [Word64] deriving (CtxPosition -> CtxPosition -> Bool
(CtxPosition -> CtxPosition -> Bool)
-> (CtxPosition -> CtxPosition -> Bool) -> Eq CtxPosition
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: CtxPosition -> CtxPosition -> Bool
== :: CtxPosition -> CtxPosition -> Bool
$c/= :: CtxPosition -> CtxPosition -> Bool
/= :: CtxPosition -> CtxPosition -> Bool
Eq, Eq CtxPosition
Eq CtxPosition =>
(CtxPosition -> CtxPosition -> Ordering)
-> (CtxPosition -> CtxPosition -> Bool)
-> (CtxPosition -> CtxPosition -> Bool)
-> (CtxPosition -> CtxPosition -> Bool)
-> (CtxPosition -> CtxPosition -> Bool)
-> (CtxPosition -> CtxPosition -> CtxPosition)
-> (CtxPosition -> CtxPosition -> CtxPosition)
-> Ord CtxPosition
CtxPosition -> CtxPosition -> Bool
CtxPosition -> CtxPosition -> Ordering
CtxPosition -> CtxPosition -> CtxPosition
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: CtxPosition -> CtxPosition -> Ordering
compare :: CtxPosition -> CtxPosition -> Ordering
$c< :: CtxPosition -> CtxPosition -> Bool
< :: CtxPosition -> CtxPosition -> Bool
$c<= :: CtxPosition -> CtxPosition -> Bool
<= :: CtxPosition -> CtxPosition -> Bool
$c> :: CtxPosition -> CtxPosition -> Bool
> :: CtxPosition -> CtxPosition -> Bool
$c>= :: CtxPosition -> CtxPosition -> Bool
>= :: CtxPosition -> CtxPosition -> Bool
$cmax :: CtxPosition -> CtxPosition -> CtxPosition
max :: CtxPosition -> CtxPosition -> CtxPosition
$cmin :: CtxPosition -> CtxPosition -> CtxPosition
min :: CtxPosition -> CtxPosition -> CtxPosition
Ord, Int -> CtxPosition -> ShowS
[CtxPosition] -> ShowS
CtxPosition -> String
(Int -> CtxPosition -> ShowS)
-> (CtxPosition -> String)
-> ([CtxPosition] -> ShowS)
-> Show CtxPosition
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> CtxPosition -> ShowS
showsPrec :: Int -> CtxPosition -> ShowS
$cshow :: CtxPosition -> String
show :: CtxPosition -> String
$cshowList :: [CtxPosition] -> ShowS
showList :: [CtxPosition] -> ShowS
Show)
appended :: Word64 -> CtxPosition
appended :: Word64 -> CtxPosition
appended Word64
n = [Word64] -> CtxPosition
CtxPosition [Word64
n, Word64
forall a. Bounded a => a
maxBound]
insertedBefore :: CtxPosition -> Word64 -> CtxPosition
insertedBefore :: CtxPosition -> Word64 -> CtxPosition
insertedBefore (CtxPosition [Word64]
ws) Word64
c = [Word64] -> CtxPosition
CtxPosition ([Word64] -> [Word64]
forall a. HasCallStack => [a] -> [a]
List.init [Word64]
ws [Word64] -> [Word64] -> [Word64]
forall a. [a] -> [a] -> [a]
++ [Word64
c, Word64
forall a. Bounded a => a
maxBound])
data Measure = Measure
{ Measure -> CtxPosition
maxPosition :: !CtxPosition,
Measure -> Int
inconsistentCount :: !Int
}
data Entry v loc = Entry
{ forall v loc. Entry v loc -> CtxPosition
entryPosition :: !CtxPosition,
forall v loc. Entry v loc -> Element v loc
entryElement :: Element v loc
}
context0 :: Context v loc
context0 :: forall v loc. Context v loc
context0 = FingerTree Measure (Entry v loc)
-> Word64
-> Map v (Entry v loc)
-> Map v (loc, Type v loc)
-> Map v [(CtxPosition, Type v loc)]
-> Context v loc
forall v loc.
FingerTree Measure (Entry v loc)
-> Word64
-> Map v (Entry v loc)
-> Map v (loc, Type v loc)
-> Map v [(CtxPosition, Type v loc)]
-> Context v loc
Context FingerTree Measure (Entry v loc)
forall v a. Measured v a => FingerTree v a
FT.empty Word64
0 Map v (Entry v loc)
forall k a. Map k a
Map.empty Map v (loc, Type v loc)
forall k a. Map k a
Map.empty Map v [(CtxPosition, Type v loc)]
forall k a. Map k a
Map.empty
elements :: Context v loc -> [Element v loc]
elements :: forall v loc. Context v loc -> [Element v loc]
elements = (Entry v loc -> Element v loc) -> [Entry v loc] -> [Element v loc]
forall a b. (a -> b) -> [a] -> [b]
map Entry v loc -> Element v loc
forall v loc. Entry v loc -> Element v loc
entryElement ([Entry v loc] -> [Element v loc])
-> (Context v loc -> [Entry v loc])
-> Context v loc
-> [Element v loc]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FingerTree Measure (Entry v loc) -> [Entry v loc]
forall a. FingerTree Measure a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
FO.toList (FingerTree Measure (Entry v loc) -> [Entry v loc])
-> (Context v loc -> FingerTree Measure (Entry v loc))
-> Context v loc
-> [Entry v loc]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Context v loc -> FingerTree Measure (Entry v loc)
forall v loc. Context v loc -> FingerTree Measure (Entry v loc)
entries
type CtxSegment v loc = [Element v loc]
data Scope = AtEnd | Before !CtxPosition
scopeOf :: (Ord v) => v -> Context v loc -> Maybe Scope
scopeOf :: forall v loc. Ord v => v -> Context v loc -> Maybe Scope
scopeOf v
v Context v loc
ctx = CtxPosition -> Scope
Before (CtxPosition -> Scope)
-> (Entry v loc -> CtxPosition) -> Entry v loc -> Scope
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Entry v loc -> CtxPosition
forall v loc. Entry v loc -> CtxPosition
entryPosition (Entry v loc -> Scope) -> Maybe (Entry v loc) -> Maybe Scope
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> v -> Map v (Entry v loc) -> Maybe (Entry v loc)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup v
v (Context v loc -> Map v (Entry v loc)
forall v loc. Context v loc -> Map v (Entry v loc)
vars Context v loc
ctx)
existentialIn :: (Ord v) => Scope -> v -> Context v loc -> Bool
existentialIn :: forall v loc. Ord v => Scope -> v -> Context v loc -> Bool
existentialIn Scope
sc v
v Context v loc
ctx = case v -> Map v (Entry v loc) -> Maybe (Entry v loc)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup v
v (Context v loc -> Map v (Entry v loc)
forall v loc. Context v loc -> Map v (Entry v loc)
vars Context v loc
ctx) of
Just (Entry CtxPosition
l Element v loc
e) | Element v loc -> Bool
forall v loc. Element v loc -> Bool
isExistential Element v loc
e -> Scope -> CtxPosition -> Bool
inScope Scope
sc CtxPosition
l
Maybe (Entry v loc)
_ -> Bool
False
universalIn :: (Ord v) => Scope -> v -> Context v loc -> Bool
universalIn :: forall v loc. Ord v => Scope -> v -> Context v loc -> Bool
universalIn Scope
sc v
v Context v loc
ctx = case v -> Map v (Entry v loc) -> Maybe (Entry v loc)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup v
v (Context v loc -> Map v (Entry v loc)
forall v loc. Context v loc -> Map v (Entry v loc)
vars Context v loc
ctx) of
Just (Entry CtxPosition
l Element v loc
e) | Element v loc -> Bool
forall v loc. Element v loc -> Bool
isUniversal Element v loc
e -> Scope -> CtxPosition -> Bool
inScope Scope
sc CtxPosition
l
Maybe (Entry v loc)
_ -> Bool
False
ordered :: (Ord v) => Context v loc -> v -> v -> Bool
ordered :: forall v loc. Ord v => Context v loc -> v -> v -> Bool
ordered Context v loc
ctx v
v v
v2 = case v -> Map v (Entry v loc) -> Maybe (Entry v loc)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup v
v2 (Context v loc -> Map v (Entry v loc)
forall v loc. Context v loc -> Map v (Entry v loc)
vars Context v loc
ctx) of
Just (Entry CtxPosition
l Element v loc
_) -> Scope -> v -> Context v loc -> Bool
forall v loc. Ord v => Scope -> v -> Context v loc -> Bool
existentialIn (CtxPosition -> Scope
Before CtxPosition
l) v
v Context v loc
ctx
Maybe (Entry v loc)
Nothing -> Bool
False
lookupElement :: (Ord v) => v -> Context v loc -> Maybe (Element v loc)
lookupElement :: forall v loc. Ord v => v -> Context v loc -> Maybe (Element v loc)
lookupElement v
v Context v loc
ctx = Entry v loc -> Element v loc
forall v loc. Entry v loc -> Element v loc
entryElement (Entry v loc -> Element v loc)
-> Maybe (Entry v loc) -> Maybe (Element v loc)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> v -> Map v (Entry v loc) -> Maybe (Entry v loc)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup v
v (Context v loc -> Map v (Entry v loc)
forall v loc. Context v loc -> Map v (Entry v loc)
vars Context v loc
ctx)
lookupSolved :: (Ord v) => Context v loc -> v -> Maybe (Monotype v loc)
lookupSolved :: forall v loc. Ord v => Context v loc -> v -> Maybe (Monotype v loc)
lookupSolved Context v loc
ctx v
v = case v -> Context v loc -> Maybe (Element v loc)
forall v loc. Ord v => v -> Context v loc -> Maybe (Element v loc)
lookupElement v
v Context v loc
ctx of
Just (Solved Blank loc
_ v
_ Monotype v loc
t) -> Monotype v loc -> Maybe (Monotype v loc)
forall a. a -> Maybe a
Just Monotype v loc
t
Maybe (Element v loc)
_ -> Maybe (Monotype v loc)
forall a. Maybe a
Nothing
lookupAnn :: (Ord v) => Context v loc -> v -> Maybe (Type v loc)
lookupAnn :: forall v loc. Ord v => Context v loc -> v -> Maybe (Type v loc)
lookupAnn Context v loc
ctx v
v = (loc, Type v loc) -> Type v loc
forall a b. (a, b) -> b
snd ((loc, Type v loc) -> Type v loc)
-> Maybe (loc, Type v loc) -> Maybe (Type v loc)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> v -> Map v (loc, Type v loc) -> Maybe (loc, Type v loc)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup v
v (Context v loc -> Map v (loc, Type v loc)
forall v loc. Context v loc -> Map v (loc, Type v loc)
anns Context v loc
ctx)
annotations :: Context v loc -> [(v, loc, Type v loc)]
annotations :: forall v loc. Context v loc -> [(v, loc, Type v loc)]
annotations Context v loc
ctx = [(v
v, loc
l, Type v loc
t) | (v
v, (loc
l, Type v loc
t)) <- Map v (loc, Type v loc) -> [(v, (loc, Type v loc))]
forall k a. Map k a -> [(k, a)]
Map.toList (Context v loc -> Map v (loc, Type v loc)
forall v loc. Context v loc -> Map v (loc, Type v loc)
anns Context v loc
ctx)]
inconsistent :: Context v loc -> Bool
inconsistent :: forall v loc. Context v loc -> Bool
inconsistent Context v loc
ctx = Measure -> Int
inconsistentCount (FingerTree Measure (Entry v loc) -> Measure
forall v a. Measured v a => a -> v
measure (Context v loc -> FingerTree Measure (Entry v loc)
forall v loc. Context v loc -> FingerTree Measure (Entry v loc)
entries Context v loc
ctx)) Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0
apply :: (Var v) => Context v loc -> Type v loc -> Type v loc
apply :: forall v loc. Var v => Context v loc -> Type v loc -> Type v loc
apply Context v loc
ctx = (v -> Maybe (Monotype v loc))
-> (v -> Maybe (Type v loc)) -> Type v loc -> Type v loc
forall v loc.
Var v =>
(v -> Maybe (Monotype v loc))
-> (v -> Maybe (Type v loc)) -> Type v loc -> Type v loc
apply' (Context v loc -> v -> Maybe (Monotype v loc)
forall v loc. Ord v => Context v loc -> v -> Maybe (Monotype v loc)
lookupSolved Context v loc
ctx) v -> Maybe (Type v loc)
refined
where
refined :: v -> Maybe (Type v loc)
refined v
v = case v
-> Map v [(CtxPosition, Type v loc)]
-> Maybe [(CtxPosition, Type v loc)]
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup v
v (Context v loc -> Map v [(CtxPosition, Type v loc)]
forall v loc. Context v loc -> Map v [(CtxPosition, Type v loc)]
refinements Context v loc
ctx) of
Just ((CtxPosition
_, Type v loc
t) : [(CtxPosition, Type v loc)]
_) -> Type v loc -> Maybe (Type v loc)
forall a. a -> Maybe a
Just Type v loc
t
Maybe [(CtxPosition, Type v loc)]
_ -> Maybe (Type v loc)
forall a. Maybe a
Nothing
applySegment :: (Var v) => CtxSegment v loc -> Type v loc -> Type v loc
applySegment :: forall v loc. Var v => CtxSegment v loc -> Type v loc -> Type v loc
applySegment CtxSegment v loc
es = (v -> Maybe (Monotype v loc))
-> (v -> Maybe (Type v loc)) -> Type v loc -> Type v loc
forall v loc.
Var v =>
(v -> Maybe (Monotype v loc))
-> (v -> Maybe (Type v loc)) -> Type v loc -> Type v loc
apply' (v -> Map v (Monotype v loc) -> Maybe (Monotype v loc)
forall k a. Ord k => k -> Map k a -> Maybe a
`Map.lookup` Map v (Monotype v loc)
solved) (v -> Map v (Type v loc) -> Maybe (Type v loc)
forall k a. Ord k => k -> Map k a -> Maybe a
`Map.lookup` Map v (Type v loc)
refined)
where
solved :: Map v (Monotype v loc)
solved = [(v, Monotype v loc)] -> Map v (Monotype v loc)
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList [(v
v, Monotype v loc
t) | Solved Blank loc
_ v
v Monotype v loc
t <- CtxSegment v loc
es]
refined :: Map v (Type v loc)
refined = [(v, Type v loc)] -> Map v (Type v loc)
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList [(v
v, Type v loc
t) | Refined v
v Type v loc
t <- CtxSegment v loc
es]
apply' ::
(Var v) =>
(v -> Maybe (Monotype v loc)) ->
(v -> Maybe (Type v loc)) ->
Type v loc ->
Type v loc
apply' :: forall v loc.
Var v =>
(v -> Maybe (Monotype v loc))
-> (v -> Maybe (Type v loc)) -> Type v loc -> Type v loc
apply' v -> Maybe (Monotype v loc)
solved v -> Maybe (Term F (TypeVar (Blank loc) v) loc)
refined Term F (TypeVar (Blank loc) v) loc
t0
| Set (TypeVar (Blank loc) v) -> Bool
forall a. Set a -> Bool
Set.null (Term F (TypeVar (Blank loc) v) loc -> Set (TypeVar (Blank loc) v)
forall v a. Type v a -> Set v
Type.freeVars Term F (TypeVar (Blank loc) v) loc
t0) = Term F (TypeVar (Blank loc) v) loc
t0
| Bool
otherwise = Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go Term F (TypeVar (Blank loc) v) loc
t0
where
go :: Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go Term F (TypeVar (Blank loc) v) loc
t = case Term F (TypeVar (Blank loc) v) loc
t of
Type.Var' (TypeVar.Universal v
v) ->
Term F (TypeVar (Blank loc) v) loc
-> (Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc)
-> Maybe (Term F (TypeVar (Blank loc) v) loc)
-> Term F (TypeVar (Blank loc) v) loc
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Term F (TypeVar (Blank loc) v) loc
t Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go (v -> Maybe (Term F (TypeVar (Blank loc) v) loc)
refined v
v)
Type.Ref' TypeReference
_ -> Term F (TypeVar (Blank loc) v) loc
t
Type.Var' (TypeVar.Existential Blank loc
_ v
v) ->
Term F (TypeVar (Blank loc) v) loc
-> (Monotype v loc -> Term F (TypeVar (Blank loc) v) loc)
-> Maybe (Monotype v loc)
-> Term F (TypeVar (Blank loc) v) loc
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Term F (TypeVar (Blank loc) v) loc
t (\(Type.Monotype Term F (TypeVar (Blank loc) v) loc
t') -> Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go Term F (TypeVar (Blank loc) v) loc
t') (v -> Maybe (Monotype v loc)
solved v
v)
Type.Arrow' Term F (TypeVar (Blank loc) v) loc
i Term F (TypeVar (Blank loc) v) loc
o -> loc
-> Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
forall v a. Ord v => a -> Type v a -> Type v a -> Type v a
Type.arrow loc
a (Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go Term F (TypeVar (Blank loc) v) loc
i) (Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go Term F (TypeVar (Blank loc) v) loc
o)
Type.App' Term F (TypeVar (Blank loc) v) loc
x Term F (TypeVar (Blank loc) v) loc
y -> loc
-> Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
forall v a. Ord v => a -> Type v a -> Type v a -> Type v a
Type.app loc
a (Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go Term F (TypeVar (Blank loc) v) loc
x) (Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go Term F (TypeVar (Blank loc) v) loc
y)
Type.Ann' Term F (TypeVar (Blank loc) v) loc
v Kind
k -> loc
-> Term F (TypeVar (Blank loc) v) loc
-> Kind
-> Term F (TypeVar (Blank loc) v) loc
forall v a. Ord v => a -> Type v a -> Kind -> Type v a
Type.ann loc
a (Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go Term F (TypeVar (Blank loc) v) loc
v) Kind
k
Type.Effect1' Term F (TypeVar (Blank loc) v) loc
e Term F (TypeVar (Blank loc) v) loc
t -> loc
-> Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
forall v a. Ord v => a -> Type v a -> Type v a -> Type v a
Type.effect1 loc
a (Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go Term F (TypeVar (Blank loc) v) loc
e) (Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go Term F (TypeVar (Blank loc) v) loc
t)
Type.Effects' [Term F (TypeVar (Blank loc) v) loc]
es -> loc
-> [Term F (TypeVar (Blank loc) v) loc]
-> Term F (TypeVar (Blank loc) v) loc
forall v a. Ord v => a -> [Type v a] -> Type v a
Type.effects loc
a ((Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc)
-> [Term F (TypeVar (Blank loc) v) loc]
-> [Term F (TypeVar (Blank loc) v) loc]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go [Term F (TypeVar (Blank loc) v) loc]
es)
Type.ForallNamed' TypeVar (Blank loc) v
v Term F (TypeVar (Blank loc) v) loc
t' -> loc
-> TypeVar (Blank loc) v
-> Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
forall v a. Ord v => a -> v -> Type v a -> Type v a
Type.forAll loc
a TypeVar (Blank loc) v
v (Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go Term F (TypeVar (Blank loc) v) loc
t')
Type.IntroOuterNamed' TypeVar (Blank loc) v
v Term F (TypeVar (Blank loc) v) loc
t' -> loc
-> TypeVar (Blank loc) v
-> Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
forall v a. Ord v => a -> v -> Type v a -> Type v a
Type.introOuter loc
a TypeVar (Blank loc) v
v (Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go Term F (TypeVar (Blank loc) v) loc
t')
Type.Record' RecordTail (Term F (TypeVar (Blank loc) v) loc)
fb Map Text (Term F (TypeVar (Blank loc) v) loc)
fields ->
Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
forall v a. Ord v => Type v a -> Type v a
Type.normalize (loc
-> RecordTail (Term F (TypeVar (Blank loc) v) loc)
-> Map Text (Term F (TypeVar (Blank loc) v) loc)
-> Term F (TypeVar (Blank loc) v) loc
forall v a.
Ord v =>
a -> RecordTail (Type v a) -> Map Text (Type v a) -> Type v a
Type.record loc
a (Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go (Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc)
-> RecordTail (Term F (TypeVar (Blank loc) v) loc)
-> RecordTail (Term F (TypeVar (Blank loc) v) loc)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> RecordTail (Term F (TypeVar (Blank loc) v) loc)
fb) (Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc
go (Term F (TypeVar (Blank loc) v) loc
-> Term F (TypeVar (Blank loc) v) loc)
-> Map Text (Term F (TypeVar (Blank loc) v) loc)
-> Map Text (Term F (TypeVar (Blank loc) v) loc)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Map Text (Term F (TypeVar (Blank loc) v) loc)
fields))
Term F (TypeVar (Blank loc) v) loc
_ -> String -> Term F (TypeVar (Blank loc) v) loc
forall a. HasCallStack => String -> a
error (String -> Term F (TypeVar (Blank loc) v) loc)
-> String -> Term F (TypeVar (Blank loc) v) loc
forall a b. (a -> b) -> a -> b
$ String
"Match error in Context.apply': " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Term F (TypeVar (Blank loc) v) loc -> String
forall a. Show a => a -> String
show Term F (TypeVar (Blank loc) v) loc
t
where
a :: loc
a = Term F (TypeVar (Blank loc) v) loc -> loc
forall (f :: * -> *) v a. Term f v a -> a
ABT.annotation Term F (TypeVar (Blank loc) v) loc
t
unsolvedExistentials :: (Ord v) => CtxSegment v loc -> Set v
unsolvedExistentials :: forall v loc. Ord v => CtxSegment v loc -> Set v
unsolvedExistentials CtxSegment v loc
es =
[v] -> Set v
forall a. Ord a => [a] -> Set a
Set.fromList [v
v | Var (TypeVar.Existential Blank loc
_ v
v) <- CtxSegment v loc
es]
Set v -> Set v -> Set v
forall a. Ord a => Set a -> Set a -> Set a
`Set.difference` [v] -> Set v
forall a. Ord a => [a] -> Set a
Set.fromList [v
v | Solved Blank loc
_ v
v Monotype v loc
_ <- CtxSegment v loc
es]
existentialVars :: (Ord v) => CtxSegment v loc -> Set v
existentialVars :: forall v loc. Ord v => CtxSegment v loc -> Set v
existentialVars CtxSegment v loc
es = [v] -> Set v
forall a. Ord a => [a] -> Set a
Set.fromList [Element v loc -> v
forall v loc. Element v loc -> v
variable Element v loc
e | Element v loc
e <- CtxSegment v loc
es, Element v loc -> Bool
forall v loc. Element v loc -> Bool
isExistential Element v loc
e]
recorded :: (Ord v) => CtxSegment v loc -> Map v (B.Recorded loc, Type v loc)
recorded :: forall v loc.
Ord v =>
CtxSegment v loc -> Map v (Recorded loc, Type v loc)
recorded = [(v, (Recorded loc, Type v loc))]
-> Map v (Recorded loc, Type v loc)
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList ([(v, (Recorded loc, Type v loc))]
-> Map v (Recorded loc, Type v loc))
-> (CtxSegment v loc -> [(v, (Recorded loc, Type v loc))])
-> CtxSegment v loc
-> Map v (Recorded loc, Type v loc)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Element v loc -> Maybe (v, (Recorded loc, Type v loc)))
-> CtxSegment v loc -> [(v, (Recorded loc, Type v loc))]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe Element v loc -> Maybe (v, (Recorded loc, Type v loc))
forall {a} {a}.
Element a a -> Maybe (a, (Recorded a, Term F (TypeVar a a) a))
f
where
f :: Element a a -> Maybe (a, (Recorded a, Term F (TypeVar a a) a))
f (Var tv :: TypeVar a a
tv@(TypeVar.Existential (B.Recorded Recorded a
b) a
v)) =
(a, (Recorded a, Term F (TypeVar a a) a))
-> Maybe (a, (Recorded a, Term F (TypeVar a a) a))
forall a. a -> Maybe a
Just (a
v, (Recorded a
b, a -> TypeVar a a -> Term F (TypeVar a a) a
forall a v (f :: * -> *). a -> v -> Term f v a
ABT.annotatedVar (Recorded a -> a
forall loc. Recorded loc -> loc
B.loc Recorded a
b) TypeVar a a
tv))
f (Solved (B.Recorded Recorded a
b) a
v Monotype a a
ty) = (a, (Recorded a, Term F (TypeVar a a) a))
-> Maybe (a, (Recorded a, Term F (TypeVar a a) a))
forall a. a -> Maybe a
Just (a
v, (Recorded a
b, Monotype a a -> Term F (TypeVar a a) a
forall v a. Monotype v a -> Type v a
Type.getPolytype Monotype a a
ty))
f Element a a
_ = Maybe (a, (Recorded a, Term F (TypeVar a a) a))
forall a. Maybe a
Nothing
data BadContext
=
DuplicateVariable
|
UndeclaredExistential
|
UndeclaredUniversal
|
NotRedeclared
deriving (BadContext -> BadContext -> Bool
(BadContext -> BadContext -> Bool)
-> (BadContext -> BadContext -> Bool) -> Eq BadContext
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: BadContext -> BadContext -> Bool
== :: BadContext -> BadContext -> Bool
$c/= :: BadContext -> BadContext -> Bool
/= :: BadContext -> BadContext -> Bool
Eq, Int -> BadContext -> ShowS
[BadContext] -> ShowS
BadContext -> String
(Int -> BadContext -> ShowS)
-> (BadContext -> String)
-> ([BadContext] -> ShowS)
-> Show BadContext
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> BadContext -> ShowS
showsPrec :: Int -> BadContext -> ShowS
$cshow :: BadContext -> String
show :: BadContext -> String
$cshowList :: [BadContext] -> ShowS
showList :: [BadContext] -> ShowS
Show)
data Rejected v loc = Rejected (Context v loc) (Element v loc) BadContext
check :: (Ord v) => Scope -> Element v loc -> Context v loc -> Maybe BadContext
check :: forall v loc.
Ord v =>
Scope -> Element v loc -> Context v loc -> Maybe BadContext
check Scope
sc Element v loc
e Context v loc
ctx
| Just v
v <- Element v loc -> Maybe v
forall v loc. Element v loc -> Maybe v
declares Element v loc
e, v -> Map v (Entry v loc) -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.member v
v (Context v loc -> Map v (Entry v loc)
forall v loc. Context v loc -> Map v (Entry v loc)
vars Context v loc
ctx) = BadContext -> Maybe BadContext
forall a. a -> Maybe a
Just BadContext
DuplicateVariable
| Refined v
v Type v loc
_ <- Element v loc
e, Bool -> Bool
not (Scope -> v -> Context v loc -> Bool
forall v loc. Ord v => Scope -> v -> Context v loc -> Bool
universalIn Scope
sc v
v Context v loc
ctx) = BadContext -> Maybe BadContext
forall a. a -> Maybe a
Just BadContext
UndeclaredUniversal
| Bool
otherwise = [BadContext] -> Maybe BadContext
forall a. [a] -> Maybe a
listToMaybe ((TypeVar (Blank loc) v -> Maybe BadContext)
-> [TypeVar (Blank loc) v] -> [BadContext]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe TypeVar (Blank loc) v -> Maybe BadContext
undeclared (Set (TypeVar (Blank loc) v) -> [TypeVar (Blank loc) v]
forall a. Set a -> [a]
Set.toList (Element v loc -> Set (TypeVar (Blank loc) v)
forall v loc. Ord v => Element v loc -> Set (TypeVar v loc)
freeVarsOf Element v loc
e)))
where
undeclared :: TypeVar (Blank loc) v -> Maybe BadContext
undeclared (TypeVar.Existential Blank loc
_ v
v)
| Scope -> v -> Context v loc -> Bool
forall v loc. Ord v => Scope -> v -> Context v loc -> Bool
existentialIn Scope
sc v
v Context v loc
ctx = Maybe BadContext
forall a. Maybe a
Nothing
| Bool
otherwise = BadContext -> Maybe BadContext
forall a. a -> Maybe a
Just BadContext
UndeclaredExistential
undeclared (TypeVar.Universal v
v)
| Scope -> v -> Context v loc -> Bool
forall v loc. Ord v => Scope -> v -> Context v loc -> Bool
universalIn Scope
sc v
v Context v loc
ctx = Maybe BadContext
forall a. Maybe a
Nothing
| Bool
otherwise = BadContext -> Maybe BadContext
forall a. a -> Maybe a
Just BadContext
UndeclaredUniversal
record :: (Ord v) => Entry v loc -> Context v loc -> Context v loc
record :: forall v loc.
Ord v =>
Entry v loc -> Context v loc -> Context v loc
record en :: Entry v loc
en@(Entry CtxPosition
l Element v loc
e) Context v loc
ctx = case Element v loc
e of
Refined v
v Type v loc
t -> Context v loc
ctx {refinements = Map.insertWith (++) v [(l, t)] (refinements ctx)}
Ann v
v loc
loc Type v loc
t -> Context v loc
ctx {vars = Map.insert v en (vars ctx), anns = Map.insert v (loc, t) (anns ctx)}
Element v loc
_ -> Context v loc
ctx {vars = Map.insert (variable e) en (vars ctx)}
forget :: (Ord v) => Entry v loc -> Context v loc -> Context v loc
forget :: forall v loc.
Ord v =>
Entry v loc -> Context v loc -> Context v loc
forget (Entry CtxPosition
l Element v loc
e) Context v loc
ctx = case Element v loc
e of
Refined v
v Type v loc
_ ->
Context v loc
ctx {refinements = Map.update (nonEmpty . List.filter ((/= l) . fst)) v (refinements ctx)}
Element v loc
_
| Just Entry v loc
en <- v -> Map v (Entry v loc) -> Maybe (Entry v loc)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup v
v (Context v loc -> Map v (Entry v loc)
forall v loc. Context v loc -> Map v (Entry v loc)
vars Context v loc
ctx),
Entry v loc -> CtxPosition
forall v loc. Entry v loc -> CtxPosition
entryPosition Entry v loc
en CtxPosition -> CtxPosition -> Bool
forall a. Eq a => a -> a -> Bool
== CtxPosition
l ->
Context v loc
ctx
{ vars = Map.delete v (vars ctx),
anns = case e of
Ann {} -> v -> Map v (loc, Type v loc) -> Map v (loc, Type v loc)
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete v
v (Context v loc -> Map v (loc, Type v loc)
forall v loc. Context v loc -> Map v (loc, Type v loc)
anns Context v loc
ctx)
Element v loc
_ -> Context v loc -> Map v (loc, Type v loc)
forall v loc. Context v loc -> Map v (loc, Type v loc)
anns Context v loc
ctx
}
| Bool
otherwise -> Context v loc
ctx
where
v :: v
v = Element v loc -> v
forall v loc. Element v loc -> v
variable Element v loc
e
nonEmpty :: [a] -> Maybe [a]
nonEmpty [] = Maybe [a]
forall a. Maybe a
Nothing
nonEmpty [a]
xs = [a] -> Maybe [a]
forall a. a -> Maybe a
Just [a]
xs
append :: (Ord v) => CtxPosition -> Element v loc -> Context v loc -> Context v loc
append :: forall v loc.
Ord v =>
CtxPosition -> Element v loc -> Context v loc -> Context v loc
append CtxPosition
l Element v loc
e Context v loc
ctx = Entry v loc -> Context v loc -> Context v loc
forall v loc.
Ord v =>
Entry v loc -> Context v loc -> Context v loc
record Entry v loc
en Context v loc
ctx {entries = entries ctx |> en, counter = counter ctx + 1}
where
en :: Entry v loc
en = CtxPosition -> Element v loc -> Entry v loc
forall v loc. CtxPosition -> Element v loc -> Entry v loc
Entry CtxPosition
l Element v loc
e
extend :: (Ord v) => Element v loc -> Context v loc -> Either BadContext (Context v loc)
extend :: forall v loc.
Ord v =>
Element v loc -> Context v loc -> Either BadContext (Context v loc)
extend Element v loc
e Context v loc
ctx = case Scope -> Element v loc -> Context v loc -> Maybe BadContext
forall v loc.
Ord v =>
Scope -> Element v loc -> Context v loc -> Maybe BadContext
check Scope
AtEnd Element v loc
e Context v loc
ctx of
Just BadContext
bad -> BadContext -> Either BadContext (Context v loc)
forall a b. a -> Either a b
Left BadContext
bad
Maybe BadContext
Nothing -> Context v loc -> Either BadContext (Context v loc)
forall a b. b -> Either a b
Right (CtxPosition -> Element v loc -> Context v loc -> Context v loc
forall v loc.
Ord v =>
CtxPosition -> Element v loc -> Context v loc -> Context v loc
append (Word64 -> CtxPosition
appended (Context v loc -> Word64
forall v loc. Context v loc -> Word64
counter Context v loc
ctx)) Element v loc
e Context v loc
ctx)
extends :: (Ord v) => CtxSegment v loc -> Context v loc -> Either (Rejected v loc) (Context v loc)
extends :: forall v loc.
Ord v =>
CtxSegment v loc
-> Context v loc -> Either (Rejected v loc) (Context v loc)
extends CtxSegment v loc
es Context v loc
ctx0 = Context v loc
-> CtxSegment v loc -> Either (Rejected v loc) (Context v loc)
forall {v} {loc}.
Ord v =>
Context v loc
-> [Element v loc] -> Either (Rejected v loc) (Context v loc)
go Context v loc
ctx0 CtxSegment v loc
es
where
go :: Context v loc
-> [Element v loc] -> Either (Rejected v loc) (Context v loc)
go Context v loc
ctx [] = Context v loc -> Either (Rejected v loc) (Context v loc)
forall a b. b -> Either a b
Right Context v loc
ctx
go Context v loc
ctx (Element v loc
e : [Element v loc]
rest) = case Element v loc -> Context v loc -> Either BadContext (Context v loc)
forall v loc.
Ord v =>
Element v loc -> Context v loc -> Either BadContext (Context v loc)
extend Element v loc
e Context v loc
ctx of
Left BadContext
bad -> Rejected v loc -> Either (Rejected v loc) (Context v loc)
forall a b. a -> Either a b
Left (Context v loc -> Element v loc -> BadContext -> Rejected v loc
forall v loc.
Context v loc -> Element v loc -> BadContext -> Rejected v loc
Rejected Context v loc
ctx Element v loc
e BadContext
bad)
Right Context v loc
ctx' -> Context v loc
-> [Element v loc] -> Either (Rejected v loc) (Context v loc)
go Context v loc
ctx' [Element v loc]
rest
atPosition :: CtxPosition -> Measure -> Measure -> Bool
atPosition :: CtxPosition -> Measure -> Measure -> Bool
atPosition CtxPosition
l Measure
pre Measure
_ = Measure -> CtxPosition
maxPosition Measure
pre CtxPosition -> CtxPosition -> Bool
forall a. Ord a => a -> a -> Bool
>= CtxPosition
l
replace :: (Ord v) => v -> CtxSegment v loc -> Context v loc -> Either (Rejected v loc) (Context v loc)
replace :: forall v loc.
Ord v =>
v
-> CtxSegment v loc
-> Context v loc
-> Either (Rejected v loc) (Context v loc)
replace v
v CtxSegment v loc
es Context v loc
ctx0 = case v -> Map v (Entry v loc) -> Maybe (Entry v loc)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup v
v (Context v loc -> Map v (Entry v loc)
forall v loc. Context v loc -> Map v (Entry v loc)
vars Context v loc
ctx0) of
Maybe (Entry v loc)
Nothing -> Context v loc -> Either (Rejected v loc) (Context v loc)
forall a b. b -> Either a b
Right Context v loc
ctx0
Just old :: Entry v loc
old@(Entry CtxPosition
l Element v loc
oldE)
| Bool -> Bool
not ((Element v loc -> Bool) -> CtxSegment v loc -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any ((Maybe v -> Maybe v -> Bool
forall a. Eq a => a -> a -> Bool
== v -> Maybe v
forall a. a -> Maybe a
Just v
v) (Maybe v -> Bool)
-> (Element v loc -> Maybe v) -> Element v loc -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Element v loc -> Maybe v
forall v loc. Element v loc -> Maybe v
declares) CtxSegment v loc
es) -> Rejected v loc -> Either (Rejected v loc) (Context v loc)
forall a b. a -> Either a b
Left (Context v loc -> Element v loc -> BadContext -> Rejected v loc
forall v loc.
Context v loc -> Element v loc -> BadContext -> Rejected v loc
Rejected Context v loc
ctx0 Element v loc
oldE BadContext
NotRedeclared)
| Position FingerTree Measure (Entry v loc)
left Entry v loc
_ FingerTree Measure (Entry v loc)
right <- (Measure -> Measure -> Bool)
-> FingerTree Measure (Entry v loc)
-> SearchResult Measure (Entry v loc)
forall v a.
Measured v a =>
(v -> v -> Bool) -> FingerTree v a -> SearchResult v a
search (CtxPosition -> Measure -> Measure -> Bool
atPosition CtxPosition
l) (Context v loc -> FingerTree Measure (Entry v loc)
forall v loc. Context v loc -> FingerTree Measure (Entry v loc)
entries Context v loc
ctx0) ->
let go :: Context v loc
-> CtxSegment v loc -> Either (Rejected v loc) (Context v loc)
go Context v loc
ctx [] = Context v loc -> Either (Rejected v loc) (Context v loc)
forall a b. b -> Either a b
Right Context v loc
ctx {entries = entries ctx >< right}
go Context v loc
ctx (Element v loc
e : CtxSegment v loc
rest) = case Scope -> Element v loc -> Context v loc -> Maybe BadContext
forall v loc.
Ord v =>
Scope -> Element v loc -> Context v loc -> Maybe BadContext
check (CtxPosition -> Scope
Before CtxPosition
l) Element v loc
e Context v loc
ctx of
Just BadContext
bad -> Rejected v loc -> Either (Rejected v loc) (Context v loc)
forall a b. a -> Either a b
Left (Context v loc -> Element v loc -> BadContext -> Rejected v loc
forall v loc.
Context v loc -> Element v loc -> BadContext -> Rejected v loc
Rejected Context v loc
ctx Element v loc
e BadContext
bad)
Maybe BadContext
Nothing -> Context v loc
-> CtxSegment v loc -> Either (Rejected v loc) (Context v loc)
go (CtxPosition -> Element v loc -> Context v loc -> Context v loc
forall v loc.
Ord v =>
CtxPosition -> Element v loc -> Context v loc -> Context v loc
append (CtxPosition -> Word64 -> CtxPosition
insertedBefore CtxPosition
l (Context v loc -> Word64
forall v loc. Context v loc -> Word64
counter Context v loc
ctx)) Element v loc
e Context v loc
ctx) CtxSegment v loc
rest
in Context v loc
-> CtxSegment v loc -> Either (Rejected v loc) (Context v loc)
go (Entry v loc -> Context v loc -> Context v loc
forall v loc.
Ord v =>
Entry v loc -> Context v loc -> Context v loc
forget Entry v loc
old Context v loc
ctx0) {entries = left} CtxSegment v loc
es
| Bool
otherwise -> String -> Either (Rejected v loc) (Context v loc)
forall a. HasCallStack => String -> a
error String
"Context.Structure.replace: a declared variable's position is not in the sequence"
retract :: (Ord v) => v -> Context v loc -> Maybe (Context v loc, CtxSegment v loc)
retract :: forall v loc.
Ord v =>
v -> Context v loc -> Maybe (Context v loc, CtxSegment v loc)
retract v
v Context v loc
ctx = case v -> Map v (Entry v loc) -> Maybe (Entry v loc)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup v
v (Context v loc -> Map v (Entry v loc)
forall v loc. Context v loc -> Map v (Entry v loc)
vars Context v loc
ctx) of
Maybe (Entry v loc)
Nothing -> Maybe (Context v loc, CtxSegment v loc)
forall a. Maybe a
Nothing
Just (Entry CtxPosition
l Element v loc
_) -> case (Measure -> Measure -> Bool)
-> FingerTree Measure (Entry v loc)
-> SearchResult Measure (Entry v loc)
forall v a.
Measured v a =>
(v -> v -> Bool) -> FingerTree v a -> SearchResult v a
search (CtxPosition -> Measure -> Measure -> Bool
atPosition CtxPosition
l) (Context v loc -> FingerTree Measure (Entry v loc)
forall v loc. Context v loc -> FingerTree Measure (Entry v loc)
entries Context v loc
ctx) of
Position FingerTree Measure (Entry v loc)
left Entry v loc
en FingerTree Measure (Entry v loc)
right ->
let gone :: [Entry v loc]
gone = Entry v loc
en Entry v loc -> [Entry v loc] -> [Entry v loc]
forall a. a -> [a] -> [a]
: FingerTree Measure (Entry v loc) -> [Entry v loc]
forall a. FingerTree Measure a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
FO.toList FingerTree Measure (Entry v loc)
right
ctx' :: Context v loc
ctx' = (Context v loc -> Entry v loc -> Context v loc)
-> Context v loc -> [Entry v loc] -> Context v loc
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' ((Entry v loc -> Context v loc -> Context v loc)
-> Context v loc -> Entry v loc -> Context v loc
forall a b c. (a -> b -> c) -> b -> a -> c
flip Entry v loc -> Context v loc -> Context v loc
forall v loc.
Ord v =>
Entry v loc -> Context v loc -> Context v loc
forget) Context v loc
ctx [Entry v loc]
gone
in (Context v loc, CtxSegment v loc)
-> Maybe (Context v loc, CtxSegment v loc)
forall a. a -> Maybe a
Just (Context v loc
ctx' {entries = left}, (Entry v loc -> Element v loc) -> [Entry v loc] -> CtxSegment v loc
forall a b. (a -> b) -> [a] -> [b]
map Entry v loc -> Element v loc
forall v loc. Entry v loc -> Element v loc
entryElement (FingerTree Measure (Entry v loc) -> [Entry v loc]
forall a. FingerTree Measure a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
FO.toList FingerTree Measure (Entry v loc)
right))
SearchResult Measure (Entry v loc)
_ -> String -> Maybe (Context v loc, CtxSegment v loc)
forall a. HasCallStack => String -> a
error String
"Context.Structure.retract: a declared variable's position is not in the sequence"
markRetained :: (Ord v) => Set v -> Context v loc -> Context v loc
markRetained :: forall v loc. Ord v => Set v -> Context v loc -> Context v loc
markRetained Set v
keep Context v loc
ctx0 = (Context v loc -> v -> Context v loc)
-> Context v loc -> Set v -> Context v loc
forall b a. (b -> a -> b) -> b -> Set a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
FO.foldl' Context v loc -> v -> Context v loc
forall {v} {loc}. Ord v => Context v loc -> v -> Context v loc
mark Context v loc
ctx0 Set v
keep
where
mark :: Context v loc -> v -> Context v loc
mark Context v loc
ctx v
v = case v -> Map v (Entry v loc) -> Maybe (Entry v loc)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup v
v (Context v loc -> Map v (Entry v loc)
forall v loc. Context v loc -> Map v (Entry v loc)
vars Context v loc
ctx) of
Just (Entry CtxPosition
l Element v loc
e) | Just Element v loc
e' <- Element v loc -> Maybe (Element v loc)
forall {v} {loc}. Element v loc -> Maybe (Element v loc)
retain Element v loc
e -> CtxPosition -> Element v loc -> Context v loc -> Context v loc
forall v loc.
Ord v =>
CtxPosition -> Element v loc -> Context v loc -> Context v loc
replaceAt CtxPosition
l Element v loc
e' Context v loc
ctx
Maybe (Entry v loc)
_ -> Context v loc
ctx
retain :: Element v loc -> Maybe (Element v loc)
retain (Var (TypeVar.Existential Blank loc
B.Blank v
v)) = Element v loc -> Maybe (Element v loc)
forall a. a -> Maybe a
Just (TypeVar (Blank loc) v -> Element v loc
forall v loc. TypeVar v loc -> Element v loc
Var (Blank loc -> v -> TypeVar (Blank loc) v
forall b v. b -> v -> TypeVar b v
TypeVar.Existential Blank loc
forall loc. Blank loc
B.Retain v
v))
retain (Solved Blank loc
B.Blank v
v Monotype v loc
t) = Element v loc -> Maybe (Element v loc)
forall a. a -> Maybe a
Just (Blank loc -> v -> Monotype v loc -> Element v loc
forall v loc. Blank loc -> v -> Monotype v loc -> Element v loc
Solved Blank loc
forall loc. Blank loc
B.Retain v
v Monotype v loc
t)
retain Element v loc
_ = Maybe (Element v loc)
forall a. Maybe a
Nothing
replaceAt :: (Ord v) => CtxPosition -> Element v loc -> Context v loc -> Context v loc
replaceAt :: forall v loc.
Ord v =>
CtxPosition -> Element v loc -> Context v loc -> Context v loc
replaceAt CtxPosition
l Element v loc
e Context v loc
ctx = case (Measure -> Measure -> Bool)
-> FingerTree Measure (Entry v loc)
-> SearchResult Measure (Entry v loc)
forall v a.
Measured v a =>
(v -> v -> Bool) -> FingerTree v a -> SearchResult v a
search (CtxPosition -> Measure -> Measure -> Bool
atPosition CtxPosition
l) (Context v loc -> FingerTree Measure (Entry v loc)
forall v loc. Context v loc -> FingerTree Measure (Entry v loc)
entries Context v loc
ctx) of
Position FingerTree Measure (Entry v loc)
left Entry v loc
_ FingerTree Measure (Entry v loc)
right -> Entry v loc -> Context v loc -> Context v loc
forall v loc.
Ord v =>
Entry v loc -> Context v loc -> Context v loc
record Entry v loc
en Context v loc
ctx {entries = left >< (en <| right)}
SearchResult Measure (Entry v loc)
_ -> Context v loc
ctx
where
en :: Entry v loc
en = CtxPosition -> Element v loc -> Entry v loc
forall v loc. CtxPosition -> Element v loc -> Entry v loc
Entry CtxPosition
l Element v loc
e
isExistential :: Element v loc -> Bool
isExistential :: forall v loc. Element v loc -> Bool
isExistential (Var (TypeVar.Existential Blank loc
_ v
_)) = Bool
True
isExistential (Solved {}) = Bool
True
isExistential Element v loc
_ = Bool
False
isUniversal :: Element v loc -> Bool
isUniversal :: forall v loc. Element v loc -> Bool
isUniversal (Var (TypeVar.Universal v
_)) = Bool
True
isUniversal Element v loc
_ = Bool
False
freeVarsOf :: (Ord v) => Element v loc -> Set (TypeVar v loc)
freeVarsOf :: forall v loc. Ord v => Element v loc -> Set (TypeVar v loc)
freeVarsOf (Solved Blank loc
_ v
_ Monotype v loc
t) = Type (TypeVar v loc) loc -> Set (TypeVar v loc)
forall v a. Type v a -> Set v
Type.freeVars (Monotype v loc -> Type (TypeVar v loc) loc
forall v a. Monotype v a -> Type v a
Type.getPolytype Monotype v loc
t)
freeVarsOf (Ann v
_ loc
_ Type (TypeVar v loc) loc
t) = Type (TypeVar v loc) loc -> Set (TypeVar v loc)
forall v a. Type v a -> Set v
Type.freeVars Type (TypeVar v loc) loc
t
freeVarsOf (Refined v
_ Type (TypeVar v loc) loc
t) = Type (TypeVar v loc) loc -> Set (TypeVar v loc)
forall v a. Type v a -> Set v
Type.freeVars Type (TypeVar v loc) loc
t
freeVarsOf Element v loc
_ = Set (TypeVar v loc)
forall a. Set a
Set.empty
inScope :: Scope -> CtxPosition -> Bool
inScope :: Scope -> CtxPosition -> Bool
inScope Scope
AtEnd CtxPosition
_ = Bool
True
inScope (Before CtxPosition
l) CtxPosition
l' = CtxPosition
l' CtxPosition -> CtxPosition -> Bool
forall a. Ord a => a -> a -> Bool
< CtxPosition
l
instance Semigroup Measure where
Measure CtxPosition
l Int
i <> :: Measure -> Measure -> Measure
<> Measure CtxPosition
l' Int
i' = CtxPosition -> Int -> Measure
Measure (CtxPosition -> CtxPosition -> CtxPosition
forall a. Ord a => a -> a -> a
max CtxPosition
l CtxPosition
l') (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i')
instance Monoid Measure where
mempty :: Measure
mempty = CtxPosition -> Int -> Measure
Measure ([Word64] -> CtxPosition
CtxPosition []) Int
0
instance Measured Measure (Entry v loc) where
measure :: Entry v loc -> Measure
measure (Entry CtxPosition
l Element v loc
e) = CtxPosition -> Int -> Measure
Measure CtxPosition
l (case Element v loc
e of Inconsistent v
_ -> Int
1; Element v loc
_ -> Int
0)
instance (Var v) => Eq (Element v loc) where
Var TypeVar v loc
v == :: Element v loc -> Element v loc -> Bool
== Var TypeVar v loc
v2 = TypeVar v loc
v TypeVar v loc -> TypeVar v loc -> Bool
forall a. Eq a => a -> a -> Bool
== TypeVar v loc
v2
Solved Blank loc
_ v
v Monotype v loc
t == Solved Blank loc
_ v
v2 Monotype v loc
t2 = v
v v -> v -> Bool
forall a. Eq a => a -> a -> Bool
== v
v2 Bool -> Bool -> Bool
&& Monotype v loc
t Monotype v loc -> Monotype v loc -> Bool
forall a. Eq a => a -> a -> Bool
== Monotype v loc
t2
Ann v
v loc
_loc Type v loc
t == Ann v
v2 loc
_loc2 Type v loc
t2 = v
v v -> v -> Bool
forall a. Eq a => a -> a -> Bool
== v
v2 Bool -> Bool -> Bool
&& Type v loc
t Type v loc -> Type v loc -> Bool
forall a. Eq a => a -> a -> Bool
== Type v loc
t2
Refined v
v Type v loc
t == Refined v
v2 Type v loc
t2 = v
v v -> v -> Bool
forall a. Eq a => a -> a -> Bool
== v
v2 Bool -> Bool -> Bool
&& Type v loc
t Type v loc -> Type v loc -> Bool
forall a. Eq a => a -> a -> Bool
== Type v loc
t2
Inconsistent v
v == Inconsistent v
v2 = v
v v -> v -> Bool
forall a. Eq a => a -> a -> Bool
== v
v2
Marker v
v == Marker v
v2 = v
v v -> v -> Bool
forall a. Eq a => a -> a -> Bool
== v
v2
Element v loc
_ == Element v loc
_ = Bool
False
instance (Var v) => Show (Element v loc) where
show :: Element v loc -> String
show (Var TypeVar v loc
v) = case TypeVar v loc
v of
TypeVar.Universal v
x -> String
"@" String -> ShowS
forall a. Semigroup a => a -> a -> a
<> v -> String
forall a. Show a => a -> String
show v
x
TypeVar v loc
e -> TypeVar v loc -> String
forall a. Show a => a -> String
show TypeVar v loc
e
show (Solved Blank loc
_ v
v Monotype v loc
t) = String
"'" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Text -> String
Text.unpack (v -> Text
forall v. Var v => v -> Text
Var.name v
v) String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" = " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Text -> String
Text.unpack (Width -> PrettyPrintEnv -> Type (TypeVar v loc) loc -> Text
forall v a. Var v => Width -> PrettyPrintEnv -> Type v a -> Text
TP.prettyStr Width
0 PrettyPrintEnv
PPE.empty (Monotype v loc -> Type (TypeVar v loc) loc
forall v a. Monotype v a -> Type v a
Type.getPolytype Monotype v loc
t))
show (Ann v
v loc
_loc Type (TypeVar v loc) loc
t) =
Text -> String
Text.unpack (v -> Text
forall v. Var v => v -> Text
Var.name v
v)
String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" : "
String -> ShowS
forall a. [a] -> [a] -> [a]
++ Text -> String
Text.unpack (Width -> PrettyPrintEnv -> Type (TypeVar v loc) loc -> Text
forall v a. Var v => Width -> PrettyPrintEnv -> Type v a -> Text
TP.prettyStr Width
0 PrettyPrintEnv
PPE.empty Type (TypeVar v loc) loc
t)
show (Refined v
v Type (TypeVar v loc) loc
t) =
Text -> String
Text.unpack (v -> Text
forall v. Var v => v -> Text
Var.name v
v)
String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" ~ "
String -> ShowS
forall a. [a] -> [a] -> [a]
++ Text -> String
Text.unpack (Width -> PrettyPrintEnv -> Type (TypeVar v loc) loc -> Text
forall v a. Var v => Width -> PrettyPrintEnv -> Type v a -> Text
TP.prettyStr Width
0 PrettyPrintEnv
PPE.empty Type (TypeVar v loc) loc
t)
show (Inconsistent v
_) = String
"⊥"
show (Marker v
v) = String
"|" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Text -> String
Text.unpack (v -> Text
forall v. Var v => v -> Text
Var.name v
v) String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"|"
renderType :: (Ord loc, Var v) => Context v loc -> Type v loc -> String
renderType :: forall loc v.
(Ord loc, Var v) =>
Context v loc -> Type v loc -> String
renderType Context v loc
ctx Type v loc
ty = Text -> String
Text.unpack (Text -> String) -> (Type v loc -> Text) -> Type v loc -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Width -> PrettyPrintEnv -> Type v loc -> Text
forall v a. Var v => Width -> PrettyPrintEnv -> Type v a -> Text
TP.prettyStr Width
0 PrettyPrintEnv
PPE.empty (Type v loc -> String) -> Type v loc -> String
forall a b. (a -> b) -> a -> b
$ Context v loc -> Type v loc -> Type v loc
forall v loc. Var v => Context v loc -> Type v loc -> Type v loc
apply Context v loc
ctx Type v loc
ty
renderElement ::
(Ord loc, Var v) => Context v loc -> Element v loc -> String
renderElement :: forall loc v.
(Ord loc, Var v) =>
Context v loc -> Element v loc -> String
renderElement Context v loc
ctx = \case
Var TypeVar v loc
v
| TypeVar.Universal v
x <- TypeVar v loc
v -> String
"@" String -> ShowS
forall a. Semigroup a => a -> a -> a
<> v -> String
forall a. Show a => a -> String
show v
x
| Bool
otherwise -> TypeVar v loc -> String
forall a. Show a => a -> String
show TypeVar v loc
v
Solved Blank loc
_ v
v (Type.Monotype Type (TypeVar v loc) loc
t) ->
[String] -> String
forall a. Monoid a => [a] -> a
mconcat
[ String
"'",
Text -> String
Text.unpack (Text -> String) -> Text -> String
forall a b. (a -> b) -> a -> b
$ v -> Text
forall v. Var v => v -> Text
Var.name v
v,
String
" = ",
Context v loc -> Type (TypeVar v loc) loc -> String
forall loc v.
(Ord loc, Var v) =>
Context v loc -> Type v loc -> String
renderType Context v loc
ctx Type (TypeVar v loc) loc
t
]
Ann v
v loc
_loc Type (TypeVar v loc) loc
t ->
[String] -> String
forall a. Monoid a => [a] -> a
mconcat
[ Text -> String
Text.unpack (Text -> String) -> Text -> String
forall a b. (a -> b) -> a -> b
$ v -> Text
forall v. Var v => v -> Text
Var.name v
v,
String
" : ",
Context v loc -> Type (TypeVar v loc) loc -> String
forall loc v.
(Ord loc, Var v) =>
Context v loc -> Type v loc -> String
renderType Context v loc
ctx Type (TypeVar v loc) loc
t
]
Refined v
v Type (TypeVar v loc) loc
t ->
[String] -> String
forall a. Monoid a => [a] -> a
mconcat
[ Text -> String
Text.unpack (Text -> String) -> Text -> String
forall a b. (a -> b) -> a -> b
$ v -> Text
forall v. Var v => v -> Text
Var.name v
v,
String
" ~ ",
Context v loc -> Type (TypeVar v loc) loc -> String
forall loc v.
(Ord loc, Var v) =>
Context v loc -> Type v loc -> String
renderType Context v loc
ctx Type (TypeVar v loc) loc
t
]
Inconsistent v
_ -> String
"⊥"
Marker v
v -> String
"|" String -> ShowS
forall a. Semigroup a => a -> a -> a
<> Text -> String
Text.unpack (v -> Text
forall v. Var v => v -> Text
Var.name v
v) String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
"|"
renderElements ::
(Ord loc, Var v) => Context v loc -> [Element v loc] -> String
renderElements :: forall loc v.
(Ord loc, Var v) =>
Context v loc -> [Element v loc] -> String
renderElements Context v loc
ctx = String -> [String] -> String
forall a. [a] -> [[a]] -> [a]
List.intercalate String
"\n " ([String] -> String)
-> ([Element v loc] -> [String]) -> [Element v loc] -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Element v loc -> String) -> [Element v loc] -> [String]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Context v loc -> Element v loc -> String
forall loc v.
(Ord loc, Var v) =>
Context v loc -> Element v loc -> String
renderElement Context v loc
ctx)
instance (Ord loc, Var v) => Show (Context v loc) where
show :: Context v loc -> String
show Context v loc
ctx =
String
"Γ\n " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> Context v loc -> [Element v loc] -> String
forall loc v.
(Ord loc, Var v) =>
Context v loc -> [Element v loc] -> String
renderElements Context v loc
ctx ([Element v loc] -> [Element v loc]
forall a. [a] -> [a]
reverse (Context v loc -> [Element v loc]
forall v loc. Context v loc -> [Element v loc]
elements Context v loc
ctx))