unison-parser-typechecker-0.0.0
Safe HaskellNone
LanguageHaskell2010

Unison.Typechecker.Context.Structure

Description

This module defines the ordered context type and related types used by the typechecking algorithm.

Synopsis

Elements

data Element v loc Source #

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.

Constructors

Var (TypeVar v loc)

A variable declaration

Solved (Blank loc) v (Monotype v loc)

v is solved to some monotype

Ann v loc (Type v loc)

v has type a, maybe quantified loc contains the span of the name of the annotated v

Refined v (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.

Inconsistent v

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.

Marker v

used for scoping

Instances

Instances details
Var v => Show (Element v loc) Source # 
Instance details

Defined in Unison.Typechecker.Context.Structure

Methods

showsPrec :: Int -> Element v loc -> ShowS #

show :: Element v loc -> String #

showList :: [Element v loc] -> ShowS #

Var v => Eq (Element v loc) Source # 
Instance details

Defined in Unison.Typechecker.Context.Structure

Methods

(==) :: Element v loc -> Element v loc -> Bool #

(/=) :: Element v loc -> Element v loc -> Bool #

variable :: Element v loc -> v Source #

declares :: Element v loc -> Maybe v Source #

The variable an element declares, if it declares one. A Refined element constrains a universal declared earlier rather than declaring it.

Contexts

data Context v loc Source #

The ordered context of the typechecking algorithm.

The context is a sequence of Elements. 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).

Instances

Instances details
(Ord loc, Var v) => Show (Context v loc) Source # 
Instance details

Defined in Unison.Typechecker.Context.Structure

Methods

showsPrec :: Int -> Context v loc -> ShowS #

show :: Context v loc -> String #

showList :: [Context v loc] -> ShowS #

context0 :: Context v loc Source #

The empty context

elements :: Context v loc -> [Element v loc] Source #

The elements, in order.

type CtxSegment v loc = [Element v loc] Source #

A run of elements taken out of a context, in order.

Scope

data Scope Source #

A place in the context at which scoping questions are asked: at the end, or just before a given element.

Constructors

AtEnd 
Before !CtxPosition 

scopeOf :: Ord v => v -> Context v loc -> Maybe Scope Source #

The scope just before the given variable's element.

existentialIn :: Ord v => Scope -> v -> Context v loc -> Bool Source #

Whether the variable is declared as an existential, solved or not, within the scope.

universalIn :: Ord v => Scope -> v -> Context v loc -> Bool Source #

Whether the variable is declared as a universal within the scope.

ordered :: Ord v => Context v loc -> v -> v -> Bool Source #

ordered ctx v v2 holds when v is an existential declared before v2's element: Γ[v^][v2^] in the paper's notation.

Queries

lookupElement :: Ord v => v -> Context v loc -> Maybe (Element v loc) Source #

The element declaring the variable, if any.

lookupSolved :: Ord v => Context v loc -> v -> Maybe (Monotype v loc) Source #

lookupAnn :: Ord v => Context v loc -> v -> Maybe (Type v loc) Source #

annotations :: Context v loc -> [(v, loc, Type v loc)] Source #

Every term variable annotation in the context.

inconsistent :: Context v loc -> Bool Source #

Whether the context holds an Inconsistent element.

apply :: Var v => Context v loc -> Type v loc -> Type v loc Source #

Replace any existentials with their solution in the context, and any refined universals with their refinement.

applySegment :: Var v => CtxSegment v loc -> Type v loc -> Type v loc Source #

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.

unsolvedExistentials :: Ord v => CtxSegment v loc -> Set v Source #

The existentials a segment declares and does not solve.

existentialVars :: Ord v => CtxSegment v loc -> Set v Source #

The existentials a segment declares, solved or not.

recorded :: Ord v => CtxSegment v loc -> Map v (Recorded loc, Type v loc) Source #

The existentials of a segment that carry a Recorded blank, with the type each stands for: its solution, or itself when unsolved.

Updates

data BadContext Source #

Why an element cannot go where it was put.

Constructors

DuplicateVariable

Its variable is already declared by an element of the context.

UndeclaredExistential

Its type mentions an existential not declared before it.

UndeclaredUniversal

Its type mentions a universal not declared before it.

NotRedeclared

A replacement for a variable's element does not bind the variable again, which would make every later element that mentions it ill-formed.

Instances

Instances details
Show BadContext Source # 
Instance details

Defined in Unison.Typechecker.Context.Structure

Eq BadContext Source # 
Instance details

Defined in Unison.Typechecker.Context.Structure

data Rejected v loc Source #

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.

Constructors

Rejected (Context v loc) (Element v loc) BadContext 

extend :: Ord v => Element v loc -> Context v loc -> Either BadContext (Context v loc) Source #

Adds an element to the end of the context.

extends :: Ord v => CtxSegment v loc -> Context v loc -> Either (Rejected v loc) (Context v loc) Source #

Adds elements to the end of the context, in order.

replace :: Ord v => v -> CtxSegment v loc -> Context v loc -> Either (Rejected v loc) (Context v loc) Source #

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.

retract :: Ord v => v -> Context v loc -> Maybe (Context v loc, CtxSegment v loc) Source #

Removes the element declaring the variable and everything after it. Returns the context that remains and the removed elements after the declaring one.

markRetained :: Ord v => Set v -> Context v loc -> Context v loc Source #

Marks the given existentials, where they are declared with a plain blank, as retained (Retain), so that later generalization leaves them in place.