blob: 131b774c312459c025a2c4021f69ec6cb0b02045 [file]
/-
Copyright (c) 2021 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Leonardo de Moura, Kyle Miller
-/
module
prelude
public import Lean.AddDecl
public import Lean.Meta.AppBuilder
import Lean.Structure
import Lean.Meta.Transform
public section
namespace Lean.Meta
/-!
# Structure methods that require `MetaM` infrastructure
-/
/--
If `struct` is an application of the form `S ..` with `S` a constant for a structure,
returns the name of the structure, otherwise throws an error.
-/
def getStructureName (struct : Expr) : MetaM Name :=
match struct.getAppFn with
| Expr.const declName .. => do
unless isStructure (← getEnv) declName do
throwError "`{.ofConstName declName}` is not a structure"
return declName
| _ => throwError "expected structure"
/--
Structure projection declaration for `mkProjections`.
-/
structure StructProjDecl where
ref : Syntax
projName : Name
/-- Overrides to param binders to apply after param binder info inference. -/
paramInfoOverrides : List (Option BinderInfo) := []
/--
Adds projection functions to the environment for the one-constructor inductive type named `n`.
- The `projName`s in each `StructProjDecl` are used for the names of the declarations added to the environment.
- If `instImplicit` is true, then generates projections with `self` being instance implicit.
Notes:
- This function supports everything that `Expr.proj` supports (see `lean::type_checker::infer_proj`).
This means we can generate projections for inductive types with one-constructor,
even if it is an indexed family (which is not supported by the `structure` command).
- We throw errors in the cases that `Expr.proj` is not type-correct.
-/
def mkProjections (n : Name) (projDecls : Array StructProjDecl) (instImplicit : Bool) : MetaM Unit :=
withLCtx {} {} do
let indVal ← getConstInfoInduct n
if indVal.numCtors != 1 then
throwError "cannot generate projections for `{.ofConstName n}`, does not have exactly one constructor"
let ctorVal ← getConstInfoCtor indVal.ctors.head!
let isPredicate ← isPropFormerType indVal.type
let lvls := indVal.levelParams.map mkLevelParam
forallBoundedTelescope ctorVal.type indVal.numParams fun params ctorType => do
if params.size != indVal.numParams then
throwError "projection generation failed, `{.ofConstName n}` is an ill-formed inductive datatype"
let selfType := mkAppN (.const n lvls) params
let selfBI : BinderInfo := if instImplicit then .instImplicit else .default
withLocalDecl `self selfBI selfType fun self => do
let projArgs := params.push self
-- Make modifications to parameter binder infos that apply to all projections
let mut lctx ← getLCtx
for param in params do
let fvarId := param.fvarId!
let decl ← fvarId.getDecl
if !decl.binderInfo.isInstImplicit && !decl.type.isOutParam then
/- We reset the implicit binder to have it be inferred by `Expr.inferImplicit`.
However, outparams must be implicit. -/
lctx := lctx.setBinderInfo fvarId .default
else if decl.binderInfo.isInstImplicit && instImplicit then
lctx := lctx.setBinderInfo fvarId .implicit
-- Construct the projection functions:
let mut ctorType := ctorType
for h : i in *...projDecls.size do
let {ref, projName, paramInfoOverrides} := projDecls[i]
ctorType ← withoutExporting (when := isPrivateName projName) do
unless ctorType.isForall do
throwErrorAt ref "\
failed to generate projection `{projName}` for `{.ofConstName n}`, \
not enough constructor fields"
unless paramInfoOverrides.length ≤ params.size do
throwErrorAt ref "\
failed to generate projection `{projName}` for `{.ofConstName n}`, \
too many structure parameter overrides"
let resultType := ctorType.bindingDomain!.consumeTypeAnnotations
let isProp ← isProp resultType
if isPredicate && !isProp then
throwErrorAt ref "\
failed to generate projection `{projName}` for the 'Prop'-valued type `{.ofConstName n}`, \
field must be a proof, but it has type\
{indentExpr resultType}"
let projType := lctx.mkForall projArgs resultType
let projType := projType.inferImplicit indVal.numParams (considerRange := true)
let projType := projType.updateForallBinderInfos paramInfoOverrides
let projVal := lctx.mkLambda projArgs <| Expr.proj n i self
let cval : ConstantVal := { name := projName, levelParams := indVal.levelParams, type := projType }
withRef ref do
if isProp then
let env ← getEnv
addDecl <|
if env.hasUnsafe projType || env.hasUnsafe projVal then
-- Theorems cannot be unsafe, using opaque instead.
Declaration.opaqueDecl { cval with value := projVal, isUnsafe := true }
else
Declaration.thmDecl { cval with value := projVal }
else
let decl ← mkDefinitionValInferringUnsafe projName indVal.levelParams projType projVal ReducibilityHints.abbrev
-- Projections have special compiler support. No need to compile.
addDecl <| Declaration.defnDecl decl
-- Recall: we want instance projections to be in "reducible canonical form"
if !instImplicit then
setReducibleAttribute projName
modifyEnv fun env => addProjectionFnInfo env projName ctorVal.name indVal.numParams i instImplicit
let proj := mkApp (mkAppN (.const projName lvls) params) self
return ctorType.bindingBody!.instantiate1 proj
/--
Checks if the expression is of the form `S.mk x.1 ... x.n` with `n` nonzero
and `S.mk` a structure constructor with `S` one of the recorded structure parents.
Returns `x`.
Each projection `x.i` can be either a native projection or from a projection function.
-/
def etaStruct? (e : Expr) (p : Name → Bool) : MetaM (Option Expr) := do
let .const ctor _ := e.getAppFn | return none
let some fVal ← isCtor? ctor | return none
unless p fVal.induct do return none
unless 0 < fVal.numFields && e.getAppNumArgs == fVal.numParams + fVal.numFields do return none
let args := e.getAppArgs
let params := args.extract 0 fVal.numParams
let some x ← getProjectedExpr ctor fVal.induct params 0 args[fVal.numParams]! none | return none
for i in 1...fVal.numFields do
let arg := args[fVal.numParams + i]!
let some x' ← getProjectedExpr ctor fVal.induct params i arg x | return none
unless x' == x do return none
return x
where
sameParams (params1 params2 : Array Expr) : MetaM Bool := withNewMCtxDepth do
if params1.size == params2.size then
for p1 in params1, p2 in params2 do
unless ← isDefEqGuarded p1 p2 do
return false
return true
else
return false
/--
Given an expression `e` that's either a native projection or a registered projection
function, gives the object being projected.
Checks that the parameters are defeq to `params`, that the projection index is equal to `idx`,
and, if `x?` is provided, that the object being projected is equal to it.
-/
getProjectedExpr (ctor induct : Name) (params : Array Expr) (idx : Nat) (e : Expr) (x? : Option Expr) : MetaM (Option Expr) := do
if let .proj S i x := e then
if i == idx && induct == S && (x? |>.map (· == x) |>.getD true) then
let ety ← whnf (← inferType e)
let params' := ety.getAppArgs
if ← sameParams params params' then
return x
return none
if let .const fn _ := e.getAppFn then
if let some info ← getProjectionFnInfo? fn then
if info.ctorName == ctor && info.i == idx && e.getAppNumArgs == info.numParams + 1 then
let x := e.appArg!
if (x? |>.map (· == x) |>.getD true) then
let params' := e.appFn!.getAppArgs
if ← sameParams params params' then
return e.appArg!
return none
/--
Eta reduces all structures satisfying `p` in the whole expression.
See `etaStruct?` for reducing single expressions.
-/
def etaStructReduce (e : Expr) (p : Name → Bool) : MetaM Expr := do
let e ← instantiateMVars e
Meta.transform e (post := fun e => do
if let some e ← etaStruct? e p then
return .done e
else
return .continue)
/--
Instantiates the default value given by the default value function `defaultFn`.
- `defaultFn` is the default value function returned by `Lean.getEffectiveDefaultFnForField?` or `Lean.getDefaultFnForField?`.
- `levels?` is the list of levels to use, and otherwise the levels are inferred.
- `params` is the list of structure parameters. These are assumed to be correct for the given levels.
- `fieldVal?` is a function for getting fields for values, if they exist.
If successful, returns a set of fields used and the resulting default value.
Success is expected. Callers should do metacontext backtracking themselves if needed.
-/
partial def instantiateStructDefaultValueFn?
[Monad m] [MonadEnv m] [MonadError m] [MonadLiftT MetaM m] [MonadControlT MetaM m]
(defaultFn : Name) (levels? : Option (List Level)) (params : Array Expr)
(fieldVal? : Name → m (Option Expr)) : m (Option (NameSet × Expr)) := do
let cinfo ← getConstInfo defaultFn
let us ← levels?.getDM (mkFreshLevelMVarsFor cinfo)
assert! us.length == cinfo.levelParams.length
let mut val ← liftMetaM <| instantiateValueLevelParams cinfo us
for param in params do
let .lam _ t b _ := val | return none
-- If no levels given, need to unify to solve for level mvars.
if levels?.isNone then
unless (← isDefEq (← inferType param) t) do return none
val := b.instantiate1 param
go? {} val
where
go? (usedFields : NameSet) (e : Expr) : m (Option (NameSet × Expr)) := do
match e with
| .lam n d b _ =>
let some val ← fieldVal? n | return none
if (← isDefEq (← inferType val) d) then
go? (usedFields.insert n) (b.instantiate1 val)
else
return none
| e =>
let_expr id _ a := e | return some (usedFields, e)
return some (usedFields, a)
end Lean.Meta