| /- | |
| Copyright (c) 2019 Microsoft Corporation. All rights reserved. | |
| Released under Apache 2.0 license as described in the file LICENSE. | |
| Authors: Leonardo de Moura | |
| -/ | |
| module | |
| prelude | |
| public import Init.Data.Range.Polymorphic.Stream | |
| public import Lean.Meta.DiscrTree.Main | |
| public import Lean.Meta.CollectMVars | |
| import Init.While | |
| import Lean.OriginalConstKind | |
| import Lean.ProjFns | |
| public section | |
| 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 instances. 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 | |
| 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 | |
| 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.insertKeyValue e.keys e, instanceNames := d.instanceNames.insert n e, erased := d.erased.erase n } | |
| | none => { d with discrTree := d.discrTree.insertKeyValue 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 "`{.ofConstName declName}` does not have [instance] attribute" | |
| return d.eraseCore declName | |
| builtin_initialize instanceExtension : SimpleScopedEnvExtension InstanceEntry Instances ← | |
| registerSimpleScopedEnvExtension { | |
| initial := {} | |
| addEntry := addInstanceEntry | |
| exportEntry? := fun level e => | |
| guard (level == .private || e.globalName?.any (!isPrivateName ·)) *> e | |
| } | |
| 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 be 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.) | |
| Remark: `projInfo?` is `some` if the instance is a projection. | |
| We need this information because of the heuristic we use to annotate binder | |
| information in projections. See PR #5376 and issue #5333. Before PR | |
| #5376, given a class `C` at | |
| ``` | |
| class A (n : Nat) where | |
| instance [A n] : A n.succ where | |
| class B [A 20050] where | |
| class C [A 20000] extends B where | |
| ``` | |
| we would get the following instance | |
| ``` | |
| C.toB [inst : A 20000] [self : @C inst] : @B ... | |
| ``` | |
| After the PR, we have | |
| ``` | |
| C.toB {inst : A 20000} [self : @C inst] : @B ... | |
| ``` | |
| Note the attribute `inst` is now just a regular implicit argument. | |
| To ensure `computeSynthOrder` works as expected, we should take | |
| this change into account while processing field `self`. | |
| This field is the one at position `projInfo?.numParams`. | |
| -/ | |
| private partial def computeSynthOrder (inst : Expr) (projInfo? : Option ProjectionFunctionInfo) : 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 | |
| let argTy ← instantiateMVars (← inferType argMVars[i]!) | |
| if let some projInfo := projInfo? then | |
| if projInfo.numParams == i then | |
| -- See comment regarding `projInfo?` at the beginning of this function | |
| assignMVarsIn argTy | |
| return true | |
| forallTelescopeReducing argTy 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) | |
| throwError m!"\ | |
| cannot find synthesization order for instance {inst} with type{indentExpr instTy}\n\ | |
| all 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 | |
| throwError 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 | |
| let status ← getReducibilityStatus declName | |
| unless status matches .reducible | .instanceReducible do | |
| let info ← getConstInfo declName | |
| if info.isDefinition then | |
| logWarning m!"instance `{declName}` must be marked with `@[reducible]` or `@[instance_reducible]`" | |
| else if wasOriginallyDefn (← getEnv) declName then | |
| logWarning m!"instance `{declName}` must be marked with `@[expose]`" | |
| let projInfo? ← getProjectionFnInfo? declName | |
| let synthOrder ← computeSynthOrder c projInfo? | |
| instanceExtension.add { keys, val := c, priority := prio, globalName? := declName, attrKind, synthOrder } attrKind | |
| /- | |
| Adds instance **and** marks it with reducibility status `@[instance_reducible]`. We use this function | |
| to elaborate `instance` command. | |
| **Note**: We used to check whether `declName` had `instance` reducibility by using `isInstance declName`. | |
| However, this was not a robust solution because: | |
| - We have scoped instances, and `isInstance declName` returns true only if the scope is active. | |
| - We have auxiliary declarations used to construct instances manually, such as: | |
| ``` | |
| def lt_wfRel : WellFoundedRelation Nat | |
| ``` | |
| `isInstance` also returns `false` for this kind of declaration. | |
| In both cases, the declaration may be (or may have been) used to construct an instance, but `isInstance` | |
| returns `false`. We claim it is a mistake to check the reducibility status using `isInstance`. | |
| `isInstance` indicates whether a declaration is available for the type class resolution mechanism, | |
| not its transparency status. | |
| Thus, we added a new transparency setting and set it here. | |
| -/ | |
| def registerInstance (declName : Name) (attrKind : AttributeKind) (prio : Nat) : MetaM Unit := do | |
| setReducibilityStatus declName .instanceReducible | |
| addInstance declName attrKind prio | |
| /-- | |
| Registers type class instances. | |
| The `instance` command, which expands to `@[instance] def`, is usually preferred over using this | |
| attribute directly. However it might sometimes still be necessary to use this attribute directly, | |
| in particular for `opaque` instances. | |
| To assign priorities to instances, `@[instance prio]` can be used (where `prio` is a priority). | |
| This corresponds to the `instance (priority := prio)` notation. | |
| -/ | |
| @[builtin_doc] | |
| 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) := | |
| return Meta.instanceExtension.getState (← getEnv) |>.discrTree | |
| def getErasedInstances : CoreM (PHashSet Name) := | |
| return Meta.instanceExtension.getState (← getEnv) |>.erased | |
| def isInstanceCore (env : Environment) (declName : Name) : Bool := | |
| Meta.instanceExtension.getState env |>.instanceNames.contains declName | |
| def isInstance (declName : Name) : CoreM Bool := | |
| return isInstanceCore (← getEnv) 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 := Std.TreeSet 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 `{.ofConstName 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 `{.ofConstName declName}`, it has type `({className} ...)`, but `{.ofConstName className}` is not a type class" | |
| setEnv <| defaultInstanceExtension.addEntry (← getEnv) { className := className, instanceName := declName, priority := prio } | |
| | _ => throwError "invalid default instance `{.ofConstName 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 throwAttrMustBeGlobal `default_instance kind | |
| 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 |