blob: 86d53c3851ea6284ac0de134566554de591424d0 [file]
/-
Copyright (c) 2026 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Authors: Eric Wieser, Kyle Miller, Jovan Gerbscheid, Kim Morrison, Sebastian Ullrich
-/
module
prelude
public import Lean.Meta.Closure
public import Lean.Meta.SynthInstance
public import Lean.Meta.CtorRecognizer
public section
/-!
# Instance Normal Form
Both `inferInstanceAs` and the default `deriving` handler normalize instance bodies to
"instance normal form". This ensures that when deriving or inferring an instance for a
semireducible type definition, the definition's RHS is not leaked when reduced at lower
than semireducible transparency.
## Algorithm
Given an instance `i : I` and expected type `I'` (where `I'` must be mvar-free),
`normalizeInstance` constructs a result instance as follows, executing all steps at
`instances` transparency:
1. If `I'` is not a class, return `i` unchanged.
2. If `I'` is a proposition, wrap `i` in an auxiliary theorem of type `I'` and return it
(controlled by `backward.inferInstanceAs.wrap.instances`).
3. Reduce `i` to whnf.
4. If `i` is not a constructor application: if the type of `i` is already defeq to `I'`,
return `i`; otherwise wrap it in an auxiliary definition of type `I'` and return it
(controlled by `backward.inferInstanceAs.wrap.instances`).
5. Otherwise, for `i = ctor a₁ ... aₙ` with `ctor : C ?p₁ ... ?pₙ`:
- Unify `C ?p₁ ... ?pₙ` with `I'`.
- Return a new application `ctor a₁' ... aₙ' : I'` where each `aᵢ'` is constructed as:
- If the field type is a proposition: assign directly if types are defeq, otherwise
wrap in an auxiliary theorem.
- If the field type is a class: first try to reuse an existing synthesized instance
for the target type (controlled by `backward.inferInstanceAs.wrap.reuseSubInstances`);
if that fails, recurse with source instance `aᵢ` and expected type `?pᵢ`.
- Otherwise (data field): assign directly if types are defeq, otherwise wrap in an
auxiliary definition to fix the type (controlled by `backward.inferInstanceAs.wrap.data`).
## Options
- `backward.inferInstanceAs.wrap`: master switch for normalization in both `inferInstanceAs`
and the default `deriving` handler
- `backward.inferInstanceAs.wrap.reuseSubInstances`: reuse existing instances for sub-instance
fields to avoid non-defeq instance diamonds
- `backward.inferInstanceAs.wrap.instances`: wrap non-reducible instances in auxiliary
definitions
- `backward.inferInstanceAs.wrap.data`: wrap data fields in auxiliary definitions
-/
namespace Lean.Meta
register_builtin_option backward.inferInstanceAs.wrap : Bool := {
defValue := true
descr := "normalize instance bodies to constructor-based normal form in `inferInstanceAs` and the default `deriving` handler"
}
register_builtin_option backward.inferInstanceAs.wrap.reuseSubInstances : Bool := {
defValue := true
descr := "when recursing into sub-instances, reuse existing instances for the target type instead of re-wrapping them, which can be important to avoid non-defeq instance diamonds"
}
register_builtin_option backward.inferInstanceAs.wrap.instances : Bool := {
defValue := true
descr := "wrap non-reducible instances in auxiliary definitions to fix their types"
}
register_builtin_option backward.inferInstanceAs.wrap.data : Bool := {
defValue := true
descr := "wrap data fields in auxiliary definitions to fix their types"
}
builtin_initialize registerTraceClass `Meta.instanceNormalForm
/--
Rebuild a type application with fresh synthetic metavariables for instance-implicit arguments.
Non-instance-implicit arguments are assigned from the original application's arguments.
If the function is over-applied, extra arguments are preserved.
-/
def abstractInstImplicitArgs (type : Expr) : MetaM Expr := do
let fn := type.getAppFn
let args := type.getAppArgs
let (mvars, bis, _) ← forallMetaTelescope (← inferType fn)
for i in [:mvars.size] do
unless bis[i]!.isInstImplicit do
mvars[i]!.mvarId!.assign args[i]!
let args := mvars ++ args.drop mvars.size
instantiateMVars (mkAppN fn args)
/--
Normalize an instance value to "instance normal form".
See the module docstring for the full algorithm specification.
-/
partial def normalizeInstance (inst expectedType : Expr) (compile : Bool := true)
(logCompileErrors : Bool := true) (isMeta : Bool := false) : MetaM Expr := withTransparency .instances do
withTraceNode `Meta.instanceNormalForm
(fun _ => return m!"type: {expectedType}") do
let some className ← isClass? expectedType
| return inst
trace[Meta.instanceNormalForm] "class is {className}"
if ← isProp expectedType then
if backward.inferInstanceAs.wrap.instances.get (← getOptions) then
return (← mkAuxTheorem expectedType inst (zetaDelta := true))
else
return inst
-- Try to reduce it to a constructor.
let inst ← whnf inst
inst.withApp fun f args => do
let some (.ctorInfo ci) ← f.constName?.mapM getConstInfo
| do
trace[Meta.instanceNormalForm] "did not reduce to constructor application, returning/wrapping as is: {inst}"
if backward.inferInstanceAs.wrap.instances.get (← getOptions) then
let instType ← inferType inst
if ← isDefEq expectedType instType then
return inst
else
let name ← mkAuxDeclName
let wrapped ← mkAuxDefinition name expectedType inst (compile := false)
setReducibilityStatus name .implicitReducible
if isMeta then modifyEnv (markMeta · name)
if compile then
compileDecls (logErrors := logCompileErrors) #[name]
enableRealizationsForConst name
return wrapped
else
return inst
let (mvars, _, cls) ← forallMetaTelescope (← inferType f)
if h₁ : args.size ≠ mvars.size then
throwError "instance normal form: incorrect number of arguments for \
constructor application `{f}`: {args}"
else
unless ← isDefEq expectedType cls do
throwError "instance normal form: `{expectedType}` does not unify with the conclusion of \
`{.ofConstName ci.name}`"
for h₂ : i in ci.numParams...args.size do
have : i < mvars.size := by
simp only [ne_eq, Decidable.not_not] at h₁
rw [← h₁]
get_elem_tactic
let mvarId := mvars[i].mvarId!
let mvarDecl ← mvarId.getDecl
let argExpectedType ← instantiateMVars mvarDecl.type
let arg := args[i]
if ← isProp argExpectedType then
let argType ← inferType arg
if ← isDefEq argExpectedType argType then
mvarId.assign arg
else
trace[Meta.instanceNormalForm] "proof field {i} does not have expected type {argExpectedType} but {argType}, wrapping in auxiliary theorem: {arg}"
mvarId.assign (← mkAuxTheorem argExpectedType arg (zetaDelta := true))
-- Recurse into instance arguments of the constructor
else if (← isClass? argExpectedType).isSome then
if backward.inferInstanceAs.wrap.reuseSubInstances.get (← getOptions) then
-- Reuse existing instance for the target type if any. This is especially important when recursing
-- as it guarantees subinstances of overlapping instances are defeq under more than just
-- semireducible transparency.
try
if let .some new ← trySynthInstance argExpectedType then
trace[Meta.instanceNormalForm] "using existing instance {new}"
mvarId.assign new
continue
catch _ => pure ()
mvarId.assign (← normalizeInstance arg argExpectedType (compile := compile)
(logCompileErrors := logCompileErrors) (isMeta := isMeta))
else
-- For data fields, assign directly or wrap in aux def to fix types.
if backward.inferInstanceAs.wrap.data.get (← getOptions) then
let argType ← inferType arg
if ← isDefEq argExpectedType argType then
mvarId.assign arg
else
let name ← mkAuxDeclName
mvarId.assign (← mkAuxDefinition name argExpectedType arg (compile := false))
setInlineAttribute name
if isMeta then modifyEnv (markMeta · name)
if compile then
compileDecls (logErrors := logCompileErrors) #[name]
enableRealizationsForConst name
else
mvarId.assign arg
return mkAppN f (← mvars.mapM instantiateMVars)
end Lean.Meta