blob: d447a1483369fb233b0b2abec0430d341b40a4f1 [file]
/-
Copyright (c) 2019 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Leonardo de Moura
-/
import Lean.ScopedEnvExtension
import Lean.Meta.GlobalInstances
import Lean.Meta.DiscrTree
import Lean.Meta.CollectMVars
namespace Lean.Meta
register_builtin_option synthInstance.checkSynthOrder : Bool := {
defValue := true
descr := "check that instances do not introduce metavariable in non-out-params"
}
/-
Note: we want to use iota reduction when indexing instaces. Otherwise,
we cannot elaborate examples such as
```
inductive Ty where
| int
| bool
@[reducible] def Ty.interp (ty : Ty) : Type :=
Ty.casesOn (motive := fun _ => Type) ty Int Bool
def test {a b c : Ty} (f : a.interp → b.interp → c.interp) (x : a.interp) (y : b.interp) : c.interp :=
f x y
def f (a b : Ty.bool.interp) : Ty.bool.interp :=
-- We want to synthesize `BEq Ty.bool.interp` here, and it will fail
-- if we do not reduce `Ty.bool.interp` to `Bool`.
test (.==.) a b
```
See comment at `DiscrTree`.
-/
abbrev InstanceKey := DiscrTree.Key (simpleReduce := false)
structure InstanceEntry where
keys : Array InstanceKey
val : Expr
priority : Nat
globalName? : Option Name := none
/-- The order in which the instance's arguments are to be synthesized. -/
synthOrder : Array Nat
/-
We store the attribute kind to be able to implement the API `getInstanceAttrKind`.
TODO: add better support for retrieving the `attrKind` of any attribute.
The current implementation here works only for instances, but it is good enough for unblocking the
implementation of `to_additive`.
-/
attrKind : AttributeKind
deriving Inhabited
instance : BEq InstanceEntry where
beq e₁ e₂ := e₁.val == e₂.val
instance : ToFormat InstanceEntry where
format e := match e.globalName? with
| some n => format n
| _ => "<local>"
abbrev InstanceTree := DiscrTree InstanceEntry (simpleReduce := false)
structure Instances where
discrTree : InstanceTree := DiscrTree.empty
instanceNames : PHashMap Name InstanceEntry := {}
erased : PHashSet Name := {}
deriving Inhabited
def addInstanceEntry (d : Instances) (e : InstanceEntry) : Instances :=
match e.globalName? with
| some n => { d with discrTree := d.discrTree.insertCore e.keys e, instanceNames := d.instanceNames.insert n e }
| none => { d with discrTree := d.discrTree.insertCore e.keys e }
def Instances.eraseCore (d : Instances) (declName : Name) : Instances :=
{ d with erased := d.erased.insert declName, instanceNames := d.instanceNames.erase declName }
def Instances.erase [Monad m] [MonadError m] (d : Instances) (declName : Name) : m Instances := do
unless d.instanceNames.contains declName do
throwError "'{declName}' does not have [instance] attribute"
return d.eraseCore declName
builtin_initialize instanceExtension : SimpleScopedEnvExtension InstanceEntry Instances ←
registerSimpleScopedEnvExtension {
initial := {}
addEntry := addInstanceEntry
}
private def mkInstanceKey (e : Expr) : MetaM (Array InstanceKey) := do
let type ← inferType e
withNewMCtxDepth do
let (_, _, type) ← forallMetaTelescopeReducing type
DiscrTree.mkPath type
/--
Compute the order the arguments of `inst` should by synthesized.
The synthesization order makes sure that all mvars in non-out-params of the
subgoals are assigned before we try to synthesize it. Otherwise it goes left
to right.
For example:
- `[Add α] [Zero α] : Foo α` returns `[0, 1]`
- `[Mul A] [Mul B] [MulHomClass F A B] : FunLike F A B` returns `[2, 0, 1]`
(because A B are out-params and are only filled in once we synthesize 2)
(The type of `inst` must not contain mvars.)
-/
partial def computeSynthOrder (inst : Expr) : MetaM (Array Nat) :=
withReducible do
let instTy ← inferType inst
-- Gets positions of all out- and semi-out-params of `classTy`
-- (where `classTy` is e.g. something like `Inhabited Nat`)
let rec getSemiOutParamPositionsOf (classTy : Expr) : MetaM (Array Nat) := do
if let .const className .. := classTy.getAppFn then
forallTelescopeReducing (← inferType classTy.getAppFn) fun args _ => do
let mut pos := (getOutParamPositions? (← getEnv) className).getD #[]
for arg in args, i in [:args.size] do
if (← inferType arg).isAppOf ``semiOutParam then
pos := pos.push i
return pos
else
return #[]
-- Create both metavariables and free variables for the instance args
-- We will successively pick subgoals where all non-out-params have been
-- assigned already. After picking such a "ready" subgoal, we assign the
-- mvars in its out-params by the corresponding fvars.
let (argMVars, argBIs, ty) ← forallMetaTelescopeReducing instTy
let ty ← whnf ty
forallTelescopeReducing instTy fun argVars _ => do
-- Assigns all mvars from argMVars in e by the corresponding fvar.
let rec assignMVarsIn (e : Expr) : MetaM Unit := do
for mvarId in ← getMVars e do
if let some i := argMVars.findIdx? (·.mvarId! == mvarId) then
mvarId.assign argVars[i]!
assignMVarsIn (← inferType (.mvar mvarId))
-- We start by assigning all metavariables in non-out-params of the return value.
-- These are assumed to not be mvars during TC search (or at least not assignable)
let tyOutParams ← getSemiOutParamPositionsOf ty
let tyArgs := ty.getAppArgs
for tyArg in tyArgs, i in [:tyArgs.size] do
unless tyOutParams.contains i do assignMVarsIn tyArg
-- Now we successively try to find the next ready subgoal, where all
-- non-out-params are mvar-free.
let mut synthed := #[]
let mut toSynth := List.range argMVars.size |>.filter (argBIs[·]! == .instImplicit) |>.toArray
while !toSynth.isEmpty do
let next? ← toSynth.findM? fun i => do
forallTelescopeReducing (← instantiateMVars (← inferType argMVars[i]!)) fun _ argTy => do
let argTy ← whnf argTy
let argOutParams ← getSemiOutParamPositionsOf argTy
let argTyArgs := argTy.getAppArgs
for i in [:argTyArgs.size], argTyArg in argTyArgs do
if !argOutParams.contains i && argTyArg.hasExprMVar then
return false
return true
let next ←
match next? with
| some next => pure next
| none =>
if synthInstance.checkSynthOrder.get (← getOptions) then
let typeLines := ("" : MessageData).joinSep <| Array.toList <| ← toSynth.mapM fun i => do
let ty ← instantiateMVars (← inferType argMVars[i]!)
return indentExpr (ty.setPPExplicit true)
logError m!"cannot find synthesization order for instance {inst} with type{indentExpr instTy}\nall remaining arguments have metavariables:{typeLines}"
pure toSynth[0]!
synthed := synthed.push next
toSynth := toSynth.filter (· != next)
assignMVarsIn (← inferType argMVars[next]!)
assignMVarsIn argMVars[next]!
if synthInstance.checkSynthOrder.get (← getOptions) then
let ty ← instantiateMVars ty
if ty.hasExprMVar then
logError m!"instance does not provide concrete values for (semi-)out-params{indentExpr (ty.setPPExplicit true)}"
trace[Meta.synthOrder] "synthesizing the arguments of {inst} in the order {synthed}:{("" : MessageData).joinSep (← synthed.mapM fun i => return indentExpr (← inferType argVars[i]!)).toList}"
return synthed
def addInstance (declName : Name) (attrKind : AttributeKind) (prio : Nat) : MetaM Unit := do
let c ← mkConstWithLevelParams declName
let keys ← mkInstanceKey c
addGlobalInstance declName attrKind
let synthOrder ← computeSynthOrder c
instanceExtension.add { keys, val := c, priority := prio, globalName? := declName, attrKind, synthOrder } attrKind
builtin_initialize
registerBuiltinAttribute {
name := `instance
descr := "type class instance"
add := fun declName stx attrKind => do
let prio ← getAttrParamOptPrio stx[1]
discard <| addInstance declName attrKind prio |>.run {} {}
erase := fun declName => do
let s := instanceExtension.getState (← getEnv)
let s ← s.erase declName
modifyEnv fun env => instanceExtension.modifyState env fun _ => s
}
def getGlobalInstancesIndex : CoreM (DiscrTree InstanceEntry (simpleReduce := false)) :=
return Meta.instanceExtension.getState (← getEnv) |>.discrTree
def getErasedInstances : CoreM (PHashSet Name) :=
return Meta.instanceExtension.getState (← getEnv) |>.erased
def isInstance (declName : Name) : CoreM Bool :=
return Meta.instanceExtension.getState (← getEnv) |>.instanceNames.contains declName
def getInstancePriority? (declName : Name) : CoreM (Option Nat) := do
let some entry := Meta.instanceExtension.getState (← getEnv) |>.instanceNames.find? declName | return none
return entry.priority
def getInstanceAttrKind? (declName : Name) : CoreM (Option AttributeKind) := do
let some entry := Meta.instanceExtension.getState (← getEnv) |>.instanceNames.find? declName | return none
return entry.attrKind
/-! # Default instance support -/
structure DefaultInstanceEntry where
className : Name
instanceName : Name
priority : Nat
abbrev PrioritySet := RBTree Nat (fun x y => compare y x)
structure DefaultInstances where
defaultInstances : NameMap (List (Name × Nat)) := {}
priorities : PrioritySet := {}
deriving Inhabited
def addDefaultInstanceEntry (d : DefaultInstances) (e : DefaultInstanceEntry) : DefaultInstances :=
let d := { d with priorities := d.priorities.insert e.priority }
match d.defaultInstances.find? e.className with
| some insts => { d with defaultInstances := d.defaultInstances.insert e.className <| (e.instanceName, e.priority) :: insts }
| none => { d with defaultInstances := d.defaultInstances.insert e.className [(e.instanceName, e.priority)] }
builtin_initialize defaultInstanceExtension : SimplePersistentEnvExtension DefaultInstanceEntry DefaultInstances ←
registerSimplePersistentEnvExtension {
addEntryFn := addDefaultInstanceEntry
addImportedFn := fun es => (mkStateFromImportedEntries addDefaultInstanceEntry {} es)
}
def addDefaultInstance (declName : Name) (prio : Nat := 0) : MetaM Unit := do
match (← getEnv).find? declName with
| none => throwError "unknown constant '{declName}'"
| some info =>
forallTelescopeReducing info.type fun _ type => do
match type.getAppFn with
| Expr.const className _ =>
unless isClass (← getEnv) className do
throwError "invalid default instance '{declName}', it has type '({className} ...)', but {className}' is not a type class"
setEnv <| defaultInstanceExtension.addEntry (← getEnv) { className := className, instanceName := declName, priority := prio }
| _ => throwError "invalid default instance '{declName}', type must be of the form '(C ...)' where 'C' is a type class"
builtin_initialize
registerBuiltinAttribute {
name := `default_instance
descr := "type class default instance"
add := fun declName stx kind => do
let prio ← getAttrParamOptPrio stx[1]
unless kind == AttributeKind.global do throwError "invalid attribute 'default_instance', must be global"
discard <| addDefaultInstance declName prio |>.run {} {}
}
registerTraceClass `Meta.synthOrder
def getDefaultInstancesPriorities [Monad m] [MonadEnv m] : m PrioritySet :=
return defaultInstanceExtension.getState (← getEnv) |>.priorities
def getDefaultInstances [Monad m] [MonadEnv m] (className : Name) : m (List (Name × Nat)) :=
return defaultInstanceExtension.getState (← getEnv) |>.defaultInstances.find? className |>.getD []
end Lean.Meta