blob: 954471f812b3f2f4c098ce5b86c088e6670faa05 [file]
/-
Copyright (c) 2020 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.Elab.MutualInductive
public section
namespace Lean.Elab.Command
open Meta
/-
```
def Lean.Parser.Command.«inductive» :=
leading_parser "inductive " >> declId >> optDeclSig >> optional ("where" <|> ":=") >> many ctor
def Lean.Parser.Command.classInductive :=
leading_parser atomic (group ("class " >> "inductive ")) >> declId >> optDeclSig >> optional ("where" <|> ":=") >> many ctor >> optDeriving
```
-/
private def inductiveSyntaxToView (modifiers : Modifiers) (decl : Syntax) (isCoinductive : Bool) : TermElabM InductiveView := do
let isClass := decl.isOfKind ``Parser.Command.classInductive
let modifiers := if isClass then modifiers.addAttr { name := `class } else modifiers
let (binders, type?) := expandOptDeclSig decl[2]
let declId := decl[1]
let ⟨name, declName, levelNames, docString?⟩ ← Term.expandDeclId (← getCurrNamespace) (← Term.getLevelNames) declId modifiers
-- In the case of mutual inductives, this is the earliests point where we can establish the
-- correct scope for each individual inductive declaration (used e.g. to infer ctor visibility
-- below), so let's do that now.
withExporting (isExporting := !isPrivateName declName) do
if modifiers.isMeta then
modifyEnv (markMeta · declName)
addDeclarationRangesForBuiltin declName modifiers.stx decl
/-
Relates to issue
https://github.com/leanprover/lean4/issues/10503
-/
if declName.hasMacroScopes && isCoinductive then
throwError "Coinductive predicates are not allowed inside of macro scopes"
let ctors ← decl[4].getArgs.mapM fun ctor => withRef ctor do
/-
```
def ctor := leading_parser optional docComment >> "\n| " >> declModifiers >> rawIdent >> optDeclSig
```
-/
let modifiersStx := ctor[2]
let mut ctorModifiers ← elabModifiers ⟨modifiersStx⟩
if let some leadingDocComment := ctor[0].getOptional? then
if ctorModifiers.docString?.isSome then
logErrorAt leadingDocComment "Duplicate doc string"
ctorModifiers := { ctorModifiers with
docString? := some (⟨leadingDocComment⟩, doc.verso.get (← getOptions)) }
if ctorModifiers.isPrivate && modifiers.isPrivate then
let hint ← do
let .original .. := modifiersStx.getHeadInfo | pure .nil
let some range := modifiersStx[2].getRangeWithTrailing? | pure .nil
-- Drop the doc comment from both the `declModifiers` and outer `ctor`, as well as
-- everything after the constructor name (yielding invalid syntax with the desired range)
let previewSpan? := ctor.modifyArgs (·[2...4].toArray.modify 0 (·.modifyArgs (·[1...*])))
MessageData.hint "Remove `private` modifier from constructor" #[{
suggestion := ""
span? := Syntax.ofRange range
previewSpan?
toCodeActionTitle? := some fun _ => "Delete `private` modifier"
}]
throwError m!"Constructor cannot be marked `private` because it is already in a `private` inductive datatype" ++ hint
if ctorModifiers.isProtected && modifiers.isPrivate then
throwError "Constructor cannot be `protected` because it is in a `private` inductive datatype"
checkValidCtorModifier ctorModifiers
let ctorName := ctor.getIdAt 3
let ctorName := declName ++ ctorName
let ctorName ← withRef ctor[3] <| applyVisibility ctorModifiers ctorName
let (binders, type?) := expandOptDeclSig ctor[4]
addDeclarationRangesFromSyntax ctorName ctor ctor[3]
if modifiers.isMeta then
modifyEnv (markMeta · ctorName)
return { ref := ctor, declId := ctor[3], modifiers := ctorModifiers, declName := ctorName, binders := binders, type? := type? : CtorView }
let computedFields ← (decl[5].getOptional?.map (·[1].getArgs) |>.getD #[]).mapM fun cf => withRef cf do
return { ref := cf, modifiers := cf[0], fieldId := cf[1].getId, type := ⟨cf[3]⟩, matchAlts := ⟨cf[4]⟩ }
let classes ← getOptDerivingClasses decl[6]
if decl[3][0].isToken ":=" then
-- https://github.com/leanprover/lean4/issues/5236
withRef decl[0] <| Linter.logLintIf Linter.linter.deprecated decl[3]
"`inductive ... :=` has been deprecated in favor of `inductive ... where`"
return {
ref := decl
shortDeclName := name
derivingClasses := classes
allowIndices := true
allowSortPolymorphism := true
declId, modifiers, isClass, declName, levelNames
binders, type?, ctors
computedFields
docString?
isCoinductive := isCoinductive
}
private def isInductiveFamily (numParams : Nat) (indFVar : Expr) : TermElabM Bool := do
let indFVarType ← inferType indFVar
forallTelescopeReducing indFVarType fun xs _ =>
return xs.size > numParams
private def getArrowBinderNames (type : Expr) : Array Name :=
go type #[]
where
go (type : Expr) (acc : Array Name) : Array Name :=
match type with
| .forallE n _ b _ => go b (acc.push n)
| .mdata _ b => go b acc
| _ => acc
/--
Replaces binder names in `type` with `newNames`.
Remark: we only replace the names for binder containing macroscopes.
-/
private def replaceArrowBinderNames (type : Expr) (newNames : Array Name) : Expr :=
go type 0
where
go (type : Expr) (i : Nat) : Expr :=
if h : i < newNames.size then
match type with
| .forallE n d b bi =>
if n.hasMacroScopes then
mkForall newNames[i] bi d (go b (i+1))
else
mkForall n bi d (go b (i+1))
| _ => type
else
type
/--
Reorders constructor arguments to improve the effectiveness of the `fixedIndicesToParams` method.
The idea is quite simple. Given a constructor type of the form
```
(a₁ : A₁) → ... → (aₙ : Aₙ) → C b₁ ... bₘ
```
We try to find the longest prefix `b₁ ... bᵢ`, `i ≤ m` s.t.
- each `bₖ` is in `{a₁, ..., aₙ}`
- each `bₖ` only depends on variables in `{b₁, ..., bₖ₋₁}`
Then, it moves this prefix `b₁ ... bᵢ` to the front.
Remark: We only reorder implicit arguments that have macroscopes. See issue #1156.
The macroscope test is an approximation, we could have restricted ourselves to auto-implicit arguments.
-/
private def reorderCtorArgs (ctorType : Expr) : MetaM Expr := do
forallTelescopeReducing ctorType fun as type => do
/- `type` is of the form `C ...` where `C` is the inductive datatype being defined. -/
let bs := type.getAppArgs
let mut as := as
let mut bsPrefix := #[]
for b in bs do
unless b.isFVar && as.contains b do
break
let localDecl ← getFVarLocalDecl b
if localDecl.binderInfo.isExplicit then
break
unless localDecl.userName.hasMacroScopes do
break
if (← localDeclDependsOnPred localDecl fun fvarId => as.any fun p => p.fvarId! == fvarId) then
break
bsPrefix := bsPrefix.push b
as := as.erase b
if bsPrefix.isEmpty then
return ctorType
else
let r ← mkForallFVars (bsPrefix ++ as) type
/- `r` already contains the resulting type.
To be able to produce better error messages, we copy the first `bsPrefix.size` binder names from `C` to `r`.
This is important when some of constructor parameters were inferred using the auto-bound implicit feature.
For example, in the following declaration.
```
inductive Member : α → List α → Type u
| head : Member a (a::as)
| tail : Member a bs → Member a (b::bs)
```
if we do not copy the binder names
```
#check @Member.head
```
produces `@Member.head : {x : Type u_1} → {a : x} → {as : List x} → Member a (a :: as)`
which is correct, but a bit confusing. By copying the binder names, we obtain
`@Member.head : {α : Type u_1} → {a : α} → {as : List α} → Member a (a :: as)`
-/
let C := type.getAppFn
let binderNames := getArrowBinderNames (← instantiateMVars (← inferType C))
return replaceArrowBinderNames r binderNames[*...bsPrefix.size]
/--
Elaborate constructor types.
Remark: we check whether the resulting type is correct, and the parameter occurrences are consistent, but
we currently do not check for:
- Positivity (it is a rare failure, and the kernel already checks for it).
- Universe constraints (the kernel checks for it).
-/
private def elabCtors (indFVars : Array Expr) (params : Array Expr) (r : ElabHeaderResult) : TermElabM (List Constructor) :=
withRef r.view.ref do
withExplicitToImplicit params do
let indFVar := r.indFVar
let indFamily ← isInductiveFamily params.size indFVar
r.view.ctors.toList.mapM fun ctorView =>
withoutExporting (when := isPrivateName ctorView.declName) do
Term.withAutoBoundImplicit <| Term.elabBinders ctorView.binders.getArgs fun ctorParams =>
withRef ctorView.ref do
let elabCtorType : TermElabM Expr := do
match ctorView.type? with
| none =>
if indFamily then
throwError "Missing resulting type for constructor `{ctorView.declName}`: \
Its resulting type must be specified because it is part of an inductive family declaration"
return mkAppN indFVar params
| some ctorType =>
let type ← Term.elabType ctorType
trace[Elab.inductive] "elabType {ctorView.declName} : {type} "
Term.synthesizeSyntheticMVars (postpone := .yes)
let type ← instantiateMVars type
let type ← checkParamOccs type
forallTelescopeReducing type fun _ resultingType => do
unless resultingType.getAppFn == indFVar do
throwUnexpectedResultingTypeMismatch resultingType indFVar ctorView.declName ctorType
unless (← isType resultingType) do
throwUnexpectedResultingTypeNotType resultingType ctorView.declName ctorType
return type
let type ← elabCtorType
Term.synthesizeSyntheticMVarsNoPostponing
let ctorParams ← Term.addAutoBoundImplicits ctorParams (ctorView.declId.getTailPos? (canonicalOnly := true))
let except (mvarId : MVarId) := ctorParams.any fun ctorParam => ctorParam.isMVar && ctorParam.mvarId! == mvarId
/-
We convert metavariables in the resulting type into extra parameters. Otherwise, we would not be able to elaborate
declarations such as
```
inductive Palindrome : List α → Prop where
| nil : Palindrome [] -- We would get an error here saying "failed to synthesize implicit argument" at `@List.nil ?m`
| single : (a : α) → Palindrome [a]
| sandwich : (a : α) → Palindrome as → Palindrome ([a] ++ as ++ [a])
```
We used to also collect unassigned metavariables on `ctorParams`, but it produced counterintuitive behavior.
For example, the following declaration used to be accepted.
```
inductive Foo
| bar (x)
#check Foo.bar
-- @Foo.bar : {x : Sort u_1} → x → Foo
```
which is also inconsistent with the behavior of auto implicits in definitions. For example, the following example was never accepted.
```
def bar (x) := 1
```
-/
let extraCtorParams ← Term.collectUnassignedMVars (← instantiateMVars type) #[] except
trace[Elab.inductive] "extraCtorParams: {extraCtorParams}"
/- We must abstract `extraCtorParams` and `ctorParams` simultaneously to make
sure we do not create auxiliary metavariables. -/
let type ← mkForallFVars (extraCtorParams ++ ctorParams) type
let type ← reorderCtorArgs type
let type ← mkForallFVars params type
trace[Elab.inductive] "{ctorView.declName} : {type}"
return { name := ctorView.declName, type }
where
/--
Ensures that the arguments to recursive occurrences of the type family being defined match the
parameters from the inductive definition.
-/
checkParamOccs (ctorType : Expr) : MetaM Expr :=
let visit (e : Expr) : StateT (List Expr) MetaM TransformStep := do
let f := e.getAppFn
if indFVars.contains f then
let mut args := e.getAppArgs
-- Prefer throwing an "argument mismatch" error rather than a "missing parameter" one
for i in *...min args.size params.size do
let param := params[i]!
let arg := args[i]!
unless (← isDefEq param arg) do
let (arg, param) ← addPPExplicitToExposeDiff arg param
let msg := m!"Mismatched inductive type parameter in{indentExpr e}\nThe provided argument\
{indentExpr arg}\nis not definitionally equal to the expected parameter{indentExpr param}"
let noteMsg := m!"The value of parameter `{param}` must be fixed throughout the inductive \
declaration. Consider making this parameter an index if it must vary."
throwNamedError lean.inductiveParamMismatch (msg ++ .note noteMsg)
args := args.set! i param
unless args.size ≥ params.size do
let expected := mkAppN f params
let containingExprMsg := (← get).head?.map toMessageData |>.getD m!"<missing>"
let msg :=
m!"Missing parameter(s) in occurrence of inductive type: In the expression{indentD containingExprMsg}\n\
found{indentExpr e}\nbut expected all parameters to be specified:{indentExpr expected}"
let noteMsg :=
m!"All occurrences of an inductive type in the types of its constructors must specify its \
fixed parameters. Only indices can be omitted in a partial application of the type constructor."
throwNamedError lean.inductiveParamMissing (msg ++ .note noteMsg)
return TransformStep.done (mkAppN f args)
else
modify fun es => e :: es
return .continue
let popContainingExpr (e : Expr) : StateT (List Expr) MetaM TransformStep := do
modify fun es => es.drop 1
return .done e
transform ctorType (pre := visit) (post := popContainingExpr) |>.run' [ctorType]
throwUnexpectedResultingTypeMismatch (resultingType indFVar : Expr) (declName : Name) (ctorType : Syntax) := do
let lazyAppMsg := MessageData.ofLazyM do
if let some fvarId := indFVar.fvarId? then
if let some decl := (← getLCtx).find? fvarId then
if (← whnfD decl.type).isForall then
return m!" an application of"
return m!""
throwNamedErrorAt ctorType lean.ctorResultingTypeMismatch "Unexpected resulting type for constructor `{declName}`: \
Expected{lazyAppMsg}{indentExpr indFVar}\nbut found{indentExpr resultingType}"
throwUnexpectedResultingTypeNotType (resultingType : Expr) (declName : Name) (ctorType : Syntax) := do
let lazyMsg := MessageData.ofLazyM do
let resultingTypeType ← inferType resultingType
return indentExpr resultingTypeType
throwNamedErrorAt ctorType lean.ctorResultingTypeMismatch "Unexpected resulting type for constructor `{declName}`: \
Expected a type, but found{indentExpr resultingType}\nof type{lazyMsg}"
def mkInductiveElabDescr (isCoinductive := false) : InductiveElabDescr where
mkInductiveView (modifiers : Modifiers) (stx : Syntax) := do
let view ← inductiveSyntaxToView modifiers stx isCoinductive
return {
view
elabCtors := fun rs r params => do
let ctors ← elabCtors (rs.map (·.indFVar)) params r
return { ctors }
}
@[builtin_inductive_elab Lean.Parser.Command.inductive, builtin_inductive_elab Lean.Parser.Command.classInductive]
def elabInductiveCommand : InductiveElabDescr := mkInductiveElabDescr
@[builtin_inductive_elab Lean.Parser.Command.coinductive]
def elabCoinductiveCommand : InductiveElabDescr := mkInductiveElabDescr (isCoinductive := true)
end Lean.Elab.Command