-- | This module defines the ordered context type and related types used by
-- the typechecking algorithm.
module Unison.Typechecker.Context.Structure
  ( -- * Elements
    Element (..),
    variable,
    declares,

    -- * Contexts
    Context,
    context0,
    elements,
    CtxSegment,

    -- * Scope
    Scope (..),
    scopeOf,
    existentialIn,
    universalIn,
    ordered,

    -- * Queries
    lookupElement,
    lookupSolved,
    lookupAnn,
    annotations,
    inconsistent,
    apply,
    applySegment,
    unsolvedExistentials,
    existentialVars,
    recorded,

    -- * Updates
    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

-- | The ordered context of the typechecking algorithm.
--
-- The context is a sequence of 'Element's. The typechecking algorithm appends
-- to it, retracts a suffix of it (everything after a marker), replaces one
-- element with a few (e.g. an existential solved to an arrow, with the arrow's
-- fresh existentials inserted before it), and asks scoping questions: is this
-- variable declared, as an existential or a universal, and at what position?
-- Is it solved, and to what?
--
-- The sequence only orders the elements. What is known about each variable
-- is kept in indexes keyed by variable name, beside the sequence, and each of
-- those maps a variable to a position in the sequence ('CtxPosition'): every
-- element in the sequence has one, and 'vars' maps each variable to
-- its element together with that position.
--
-- So for instance, a solution proposed for an existential @β@ may only
-- mention variables declared before @β@ in the context, existentials and
-- universals alike (the universals are the rigid type variables of enclosing
-- quantifiers). `solve` therefore looks up each free variable of the solution
-- in 'vars', checks that it is declared as the kind of variable it occurs
-- as, and compares its position with @β@'s. Once @β@ is solved, its solution
-- is read from the same entry. 'anns' and 'refinements' are the same idea for
-- term variable annotations and for the branch-local refinements of a
-- universal.
--
-- The sequence is a finger tree whose measure includes the greatest position in a
-- subtree (so that the element at a position can be found in logarithmic time),
-- and a count of 'Inconsistent' elements (so that 'inconsistent' can tell in
-- constant time whether the pattern-match branch being checked has been
-- marked unreachable by contradictory GADT refinements, in which case its
-- body is skipped).
--
-- Every change keeps the indexes describing exactly the elements in the
-- sequence: an append or replacement records the new elements, and a
-- retraction walks the elements it discards and forgets them. Each element
-- is appended once and discarded at most once, so a retraction costs no more
-- than the appends it undoes.
--
-- Segments of a context that have been retracted are plain lists
-- ('CtxSegment'); the typechecker reads them whole (to generalize over their
-- unsolved existentials, apply their solutions, or push some of them back).
data Context v loc = Context
  { forall v loc. Context v loc -> FingerTree Measure (Entry v loc)
entries :: !(FingerTree Measure (Entry v loc)),
    -- | Source of position components; only ever increases.
    forall v loc. Context v loc -> Word64
counter :: !Word64,
    -- | The element that declares each variable, with its position. Term and
    -- type variables share this one namespace, and a valid context declares a
    -- variable once ('check' refuses a second declaration of any kind, an
    -- 'Ann' after a 'Var' included, as 'DuplicateVariable'), so one entry per
    -- variable is exact; the one kind of element that may recur for a
    -- variable, 'Refined', declares nothing and is kept in 'refinements'.
    forall v loc. Context v loc -> Map v (Entry v loc)
vars :: !(Map v (Entry v loc)),
    -- | The 'Ann' elements again, so that a walk of the annotations (which
    -- the ability checks make per existential) costs the annotations, not
    -- the context.
    forall v loc. Context v loc -> Map v (loc, Type v loc)
anns :: !(Map v (loc, Type v loc)),
    -- | The 'Refined' elements per universal, latest first.
    forall v loc. Context v loc -> Map v [(CtxPosition, Type v loc)]
refinements :: !(Map v [(CtxPosition, Type v loc)])
  }

-- | Elements of an ordered algorithmic context. Every element but 'Refined'
-- declares its variable; a context is valid when no variable is declared twice and
-- every type in it mentions only variables declared before it.
data Element v loc
  = -- | A variable declaration
    Var (TypeVar v loc)
  | -- | `v` is solved to some monotype
    Solved (B.Blank loc) v (Monotype v loc)
  | -- | `v` has type `a`, maybe quantified
    -- loc contains the span of the name of the annotated 'v'
    Ann v loc (Type v loc)
  | -- | The (already-declared) universal variable `v` is locally known to
    -- equal the given type. This is how GADT pattern matching refines a
    -- rigid type index inside a branch: matching e.g. @NatLit : Expr Nat@
    -- against a scrutinee of type @Expr a@ records @a ~ Nat@ for the
    -- duration of that branch. Like other branch-local context, these are
    -- introduced after a 'Marker' and dropped on retraction.
    Refined v (Type v loc)
  | -- | Marks the context as inconsistent (the DK indexed-types paper's `⊥`):
    -- the branch-local equalities are contradictory, so the current pattern-match
    -- branch is unreachable and its body is vacuously well-typed. Carries a
    -- (fresh) variable only so it scopes like any other element and is dropped on
    -- retraction. See 'inconsistent'.
    Inconsistent v
  | -- | used for scoping
    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

-- | The variable an element declares, if it declares one. A 'Refined' element
-- constrains a universal declared earlier rather than declaring it.
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)

-- | The position of an element: a path of values of the context's own
-- 'counter', ending in 'maxBound', compared lexicographically.
--
-- An appended element gets @[n, maxBound]@ for the next counter value @n@,
-- which sorts after every position already in the context. An element inserted
-- before the element at position @p ++ [maxBound]@ gets @p ++ [c, maxBound]@ for
-- the next counter value @c@: that sorts before @p ++ [maxBound]@ (as
-- @c < maxBound@), after anything inserted before the same element earlier
-- (a smaller @c@), and otherwise exactly where @p@ sorts.
--
-- The counter is a field of the 'Context' value and every append or insertion
-- takes the next value from it, so within one context value no two elements
-- share a position, which is all the indexes need. The typechecker never sees
-- positions: it asks its questions by variable, and keeps its own counter
-- ('freshId') for naming variables. When the typechecker restores an earlier
-- context value (to retry something), that value's counter comes back with
-- it, and the positions it hands out again belong to that value's elements,
-- not to the elements of the abandoned one.
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])

-- | What the sequence summarizes about a subtree: enough to find an element
-- by its position, and whether an 'Inconsistent' element is present.
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
  }

-- | The empty context
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

-- | The elements, in order.
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

-- | A run of elements taken out of a context, in order.
type CtxSegment v loc = [Element v loc]

-- | A place in the context at which scoping questions are asked: at the end,
-- or just before a given element.
data Scope = AtEnd | Before !CtxPosition

-- | The scope just before the given variable's element.
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)

-- | Whether the variable is declared as an existential, solved or not, within
-- the scope.
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

-- | Whether the variable is declared as a universal within the scope.
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 ctx v v2@ holds when @v@ is an existential declared before @v2@'s
-- element: Γ[v^][v2^] in the paper's notation.
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

-- | The element declaring the variable, if any.
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)

-- | Every term variable annotation in the context.
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)]

-- | Whether the context holds an 'Inconsistent' element.
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

-- | Replace any existentials with their solution in the context, and any
-- refined universals with their refinement.
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

-- | 'apply' with the solutions and refinements found in a segment. The maps
-- are built once per segment, so a partial application to a segment can be
-- reused over many types.
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
    -- A later element wins, as the rightmost one does in a context.
    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 ->
        -- Substituting a solution into a row can nest records, so re-flatten:
        -- `{x: Nat | {y: Text}}` and `{x: Nat, y: Text}` are the same type and
        -- have to compare equal.
        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

-- | The existentials a segment declares and does not solve.
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]

-- | The existentials a segment declares, solved or not.
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]

-- | The existentials of a segment that carry a 'B.Recorded' blank, with the
-- type each stands for: its solution, or itself when unsolved.
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

-- | Why an element cannot go where it was put.
data BadContext
  = -- | Its variable is already declared by an element of the context.
    DuplicateVariable
  | -- | Its type mentions an existential not declared before it.
    UndeclaredExistential
  | -- | Its type mentions a universal not declared before it.
    UndeclaredUniversal
  | -- | A replacement for a variable's element does not bind the variable
    -- again, which would make every later element that mentions it ill-formed.
    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)

-- | A refused update: the context as it stood (for 'replace', the elements
-- before the replaced one plus the replacements accepted so far), the element
-- refused, and why.
data Rejected v loc = Rejected (Context v loc) (Element v loc) BadContext

-- Checks an element against the context at the given scope: its variable must
-- not already be declared, and its type's variables must be declared within the
-- scope, each as the kind of variable it occurs as.
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

-- Enters an element that is in the sequence into the maps.
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)}

-- Removes an element that has left the sequence from the maps. Only the entry
-- made for this element (by position) is removed, so an element that has already
-- been superseded in the maps is left alone.
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

-- Appends an element with a fresh position, without checking it.
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

-- | Adds an element to the end of the context.
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)

-- | Adds elements to the end of the context, in order.
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

-- The position of the element with the given position: the first element at
-- which the running maximum position reaches it.
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

-- | Replaces the element declaring a variable with a run of elements, which
-- must bind the variable again (typically last, after fresh existentials its
-- solution mentions). Each replacement is checked in the scope of the
-- replaced element. A variable that is not declared leaves the context as it is.
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"

-- | Removes the element declaring the variable and everything after it. Returns
-- the context that remains and the removed elements after the declaring one.
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"

-- | Marks the given existentials, where they are declared with a plain blank, as
-- retained ('B.Retain'), so that later generalization leaves them in place.
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

-- Replaces the element at a position with another declaring the same variable.
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

-- Helpers ---------------------------------------------------------------------

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

-- The variables occurring in an element's type, which must all be declared
-- before the element.
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

-- Instances -------------------------------------------------------------------

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))