Agda.TypeChecking.SizedTypes.Solve

Solving size constraints under hypotheses.

The size solver proceeds as follows:

1. Get size constraints, cluster into connected components.

All size constraints that mention the same metas go into the same cluster. Each cluster can be solved by itself.

Constraints that do not fit our format are ignored. We check whether our computed solution fulfills them as well in the last step.

2. Find a joint context for each cluster.

Each constraint comes with its own typing context, which contains size hypotheses j : Size< i. We need to find a common super context in which all constraints of a cluster live, and raise all constraints to this context.

There might not be a common super context. Then we are screwed, since our solver is not ready to deal with such a situation. We will blatantly refuse to solve this cluster and blame it on the user.

3. Convert the joint context into a hypothesis graph.

This is straightforward. Each de Bruijn index becomes a rigid variable, each typing assumption j : Size< i becomes an arc.

4. Convert the constraints into a constraint graph.

Here we need to convert MetaVs into flexible variables.

5. Run the solver
6. Convert the solution into meta instantiations.
7. Double-check whether the constraints are solved.

Documentation

data DefaultToInfty

Flag to control the behavior of size solver.

Constructors

DefaultToInfty

Instantiate all unconstrained size variables to ∞.

DontDefaultToInfty

Leave unconstrained size variables unsolved.

Instances

Show DefaultToInfty

Defined in Agda.TypeChecking.SizedTypes.Solve

Methods

showsPrec :: Int -> DefaultToInfty -> ShowS

show :: DefaultToInfty -> String

showList :: [DefaultToInfty] -> ShowS

Eq DefaultToInfty

Defined in Agda.TypeChecking.SizedTypes.Solve

Methods

(==) :: DefaultToInfty -> DefaultToInfty -> Bool

(/=) :: DefaultToInfty -> DefaultToInfty -> Bool

Ord DefaultToInfty

Defined in Agda.TypeChecking.SizedTypes.Solve

Methods

compare :: DefaultToInfty -> DefaultToInfty -> Ordering

(<) :: DefaultToInfty -> DefaultToInfty -> Bool

(<=) :: DefaultToInfty -> DefaultToInfty -> Bool

(>) :: DefaultToInfty -> DefaultToInfty -> Bool

(>=) :: DefaultToInfty -> DefaultToInfty -> Bool

max :: DefaultToInfty -> DefaultToInfty -> DefaultToInfty

min :: DefaultToInfty -> DefaultToInfty -> DefaultToInfty

solveSizeConstraints :: DefaultToInfty -> TCM ()

Solve size constraints involving hypotheses.

castConstraintToCurrentContext' :: Closure Constraint -> MaybeT TCM Constraint

TODO: this does not actually work!

We would like to use a constraint c created in context Δ from module N in the current context Γ and current module M.

Δ is module tel Δ₁ of N extended by some local bindings Δ₂. Γ is the current context. The module parameter substitution from current M to N be Γ ⊢ σ : Δ₁.

If M == N, we do not need the parameter substitution. We try raising.

We first strengthen Δ ⊢ c to live in Δ₁ and obtain c₁ = strengthen Δ₂ c. We then transport c₁ to Γ and obtain c₂ = applySubst σ c₁.

This works for different modules, but if M == N we should not strengthen and then weaken, because strengthening is a partial operation. We should rather lift the substitution σ by Δ₂ and then raise by Γ₂ - Δ₂. This "raising" might be a strengthening if Γ₂ is shorter than Δ₂.

(TODO: If the module substitution does not exist, because N is not a parent of M, we cannot use the constraint, as it has been created in an unrelated context.)

castConstraintToCurrentContext :: ProblemConstraint -> MaybeT TCM ProblemConstraint

A hazardous hack, may the Gods have mercy on us.

To cast to the current context, we match the context of the given constraint by CtxId, and as fallback, by variable name (douh!).

This hack lets issue 2046 go through.

solveSizeConstraints_ :: DefaultToInfty -> [ProblemConstraint] -> TCM (Set MetaId)

Return the size metas occurring in the simplified constraints. A constraint like ↑ _j =< ∞ : Size simplifies to nothing, so _j would not be in this set.

solveCluster :: DefaultToInfty -> List1 (ProblemConstraint, HypSizeConstraint) -> TCM ()

Solve a cluster of constraints sharing some metas.

getSizeHypotheses :: Context -> TCM [(Nat, SizeConstraint)]

Collect constraints from a typing context, looking for SIZELT hypotheses.

canonicalizeSizeConstraint :: SizeConstraint -> Maybe SizeConstraint

Convert size constraint into form where each meta is applied to indices n-1,...,1,0 where n is the arity of that meta.

X[σ] <= t becomes X[id] <= t[σ^-1]

X[σ] ≤ Y[τ] becomes X[id] ≤ Y[τ[σ^-1]] or X[σ[τ^1]] ≤ Y[id] whichever is defined. If none is defined, we give up.

Cf. SizedTypes.oldCanonicalizeSizeConstraint.

Fixes (the rather artificial) issue 300. But it is unsound when pruned metas occur and triggers issue 1914. Thus we deactivate it. This needs to be properly implemented, possibly using the metaPermuatation of each meta variable.

computeSizeConstraint :: ProblemConstraint -> TCM (Maybe HypSizeConstraint)

Turn a constraint over de Bruijn indices into a size constraint.

sizeExpr :: Term -> TCM (Maybe DBSizeExpr)

Turn a term into a size expression.

Returns Nothing if the term isn't a proper size expression.

Orphan instances

Subst SizeConstraint

Associated Types

type SubstArg SizeConstraint

Methods

applySubst :: Substitution' (SubstArg SizeConstraint) -> SizeConstraint -> SizeConstraint

Subst SizeMeta

Associated Types

type SubstArg SizeMeta

Methods

applySubst :: Substitution' (SubstArg SizeMeta) -> SizeMeta -> SizeMeta

Subst (SizeExpr' NamedRigid SizeMeta)

Only for raise.

Associated Types

type SubstArg (SizeExpr' NamedRigid SizeMeta)

Methods

applySubst :: Substitution' (SubstArg (SizeExpr' NamedRigid SizeMeta)) -> SizeExpr' NamedRigid SizeMeta -> SizeExpr' NamedRigid SizeMeta