Find position of a value in a list. Used to change metavar argument indices during assignment.

reverse is necessary because we are directly abstracting over the list.

Does the given local meta-variable have a twin meta-variable?

Check whether a meta variable is a place holder for a blocked term.

Performing the meta variable assignment.

The instantiation should not be an InstV and the MetaId should point to something Open or a BlockedConst. Further, the meta variable may not be Frozen.

Skip frozen check. Used for eta expanding frozen metas.

Create a sort meta that cannot be instantiated with Inf (Setω).

Create a sort meta that may be instantiated with Inf (Setω).

Create a sort meta that may be instantiated with Inf (Setω).

newInstanceMeta s t cands creates a new instance metavariable of type the output type of t with name suggestion s.

Create a new value meta with specific dependencies, possibly η-expanding in the process.

Create a new value meta with specific dependencies without η-expanding.

Create a new metavariable, possibly η-expanding in the process.

Create a new value meta without η-expanding.

Create a metavariable of record type. This is actually one metavariable for each field.

Construct a blocked constant if there are constraints.

unblockedTester t returns a Blocker for t.

Auxiliary function used when creating a postponed type checking problem.

Create a postponed type checking problem e : t that waits for type t to unblock (become instantiated or its constraints resolved).

Create a postponed type checking problem e : t that waits for conditon unblock. A new meta is created in the current context that has as instantiation the postponed type checking problem. An UnBlock constraint is added for this meta, which links to this meta.

Type of the term that is produced by solving the TypeCheckingProblem.

Eta-expand a local meta-variable, if it is of the specified kind. Don't do anything if the meta-variable is a blocked term.

Eta expand blocking metavariables of record type, and reduce the blocked thing.

Miller pattern unification:

assign dir x vs v a solves problem x vs <=(dir) v : a for meta x if vs are distinct variables (linearity check) and v depends only on these variables and does not contain x itself (occurs check).

This is the basic story, but we have added some features:

1. Pruning.
2. Benign cases of non-linearity.
3. vs may contain record patterns.

For a reference to some of these extensions, read Andreas Abel and Brigitte Pientka's TLCA 2011 paper.

assignMeta m x t ids u solves x ids = u for meta x of type t, where term u lives in a context of length m. Precondition: ids is linear.

assignMeta' m x t ids u solves x = [ids]u for meta x of type t, where term u lives in a context of length m, and ids is a partial substitution.

Check that the instantiation of the given metavariable fits the type of the metavariable. If the metavariable is not yet instantiated, add a constraint to check the instantiation later.

Check that the instantiation of the metavariable with the given term is well-typed.

Given two types a and b with a <: b, check that a == b.

Turn the assignment problem _X args <= SizeLt u into _X args = SizeLt (_Y args) and constraint _Y args <= u.

Eta-expand bound variables like z in X (fst z).

Eta-expand a de Bruijn index of record type in context and passed term(s).

Check whether one of the meta args is a projected var.

Normalize just far enough to be able to eta-contract maximally.

Turn non-det substitution into proper substitution, if possible. Otherwise, raise the error.

Exceptions raised when substitution cannot be inverted.

Check that arguments args to a metavar are in pattern fragment. Assumes all arguments already in whnf and eta-reduced. Parameters are represented as Vars so checkArgs really checks that all args are Vars and returns the "substitution" to be applied to the rhs of the equation to solve. (If args is considered a substitution, its inverse is returned.)

The returned list might not be ordered. Linearity, i.e., whether the substitution is deterministic, has to be checked separately.

Turn open metas into postulates.

Preconditions:

1. We are inTopContext.
2. envCurrentModule is set to the top-level module.

Sort metas in dependency order.