blob: e50de48ba5b6bf829998ec1167dff9e3d159f5b2 [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
-/
module
prelude
public import Lean.Elab.Arg
public import Lean.Elab.MatchAltView
public import Init.Syntax
import Init.Data.Nat.Linear
import Init.Omega
public section
namespace Lean.Elab.Term
open Meta
abbrev PatternVar := Syntax -- TODO: should be `Ident`
/-!
Patterns define new local variables.
This module collects them and preprocesses `_` occurring in patterns.
Recall that an `_` may represent anonymous variables or inaccessible terms
that are implied by typing constraints. Thus, we represent them with fresh named holes `?x`.
After we elaborate the pattern, if the metavariable remains unassigned, we transform it into
a regular pattern variable. Otherwise, it becomes an inaccessible term.
Macros occurring in patterns are expanded before the `collectPatternVars` method is executed.
The following kinds of Syntax are handled by this module
- Constructor applications
- Applications of functions tagged with the `[match_pattern]` attribute
- Identifiers
- Anonymous constructors
- Structure instances
- Inaccessible terms
- Named patterns
- Tuple literals
- Type ascriptions
- Literals: num, string and char
-/
namespace CollectPatternVars
/-- State for the pattern variable collector monad. -/
structure State where
/-- Pattern variables found so far. -/
found : NameSet := {}
/-- Pattern variables found so far as an array. It contains the order they were found. -/
vars : Array PatternVar := #[]
deriving Inhabited
abbrev M := StateRefT State TermElabM
private def throwCtorExpected {α} (ident : Option Syntax) : M α := do
let message : MessageData :=
"Invalid pattern: Expected a constructor or constant marked with `[match_pattern]`"
let some idStx := ident | throwError message
let name := idStx.getId
if let .anonymous := name then throwError message
let env ← getEnv
let mut candidates : Array Name := #[]
for (c, _) in env.constants do
if isPrivateName c then continue
if !(name.isSuffixOf c) then continue
if env.isConstructor c || hasMatchPatternAttribute env c then
candidates := candidates.push c
if candidates.size = 0 then
throwError message
let oneOfThese := if h : candidates.size = 1 then m!"`{candidates[0]}`" else m!"one of these"
let hint ← m!"Using {oneOfThese} would be valid:".hint (ref? := idStx) (candidates.map fun candidate => {
suggestion := mkIdent candidate
toCodeActionTitle? := .some (s!"Change to {·}")
messageData? := .some m!"`{.ofConstName candidate}`",
})
throwError message ++ hint
private def throwInvalidPattern {α} : M α :=
throwError "Invalid pattern"
/-!
An application in a pattern can be
1- A constructor application
The elaborator assumes fields are accessible and inductive parameters are not accessible.
2- A regular application `(f ...)` where `f` is tagged with `[match_pattern]`.
The elaborator assumes implicit arguments are not accessible and explicit ones are accessible.
-/
structure Context where
funId : Ident
ctorVal? : Option ConstructorVal -- It is `some`, if constructor application
explicit : Bool
ellipsis : Bool
paramDecls : Array (Name × BinderInfo) -- parameters' names and binder information
paramDeclIdx : Nat := 0
namedArgs : Array NamedArg
usedNames : Std.HashSet Name := {}
args : List Arg
newArgs : Array Term := #[]
deriving Inhabited
private def throwInvalidNamedArgs (ctx : Context) (h : !ctx.namedArgs.isEmpty) : MetaM α := do
let names := (ctx.namedArgs.map fun narg => m!"`{narg.name}`").toList
let nameStr := if names.length == 1 then "name" else "names"
let validNames := ctx.paramDecls.filterMap fun (name, _) =>
if name.hasMacroScopes then none else some name
have h := Nat.zero_lt_of_ne_zero (mt Array.isEmpty_iff_size_eq_zero.mpr (Bool.not_eq.mp h))
-- We offer hints only for the first argument
let firstNamedArg := ctx.namedArgs[0]'h
let replacementSpan := firstNamedArg.ref[1]
let unused := validNames.filter (!ctx.usedNames.contains ·)
let hint ← do
if replacementSpan.getHeadInfo matches .original .. then
let suggestions := unused.map fun validName =>
{ suggestion := validName.toString
span? := replacementSpan
preInfo? := some s!"`{validName}`: "
toCodeActionTitle? := some fun s => s!"Change argument name `{firstNamedArg.name}` to `{s}`" }
let hintMsg := m!"Replace `{firstNamedArg.name}` with one of the following parameter names:"
MessageData.hint (forceList := true) hintMsg suggestions
else
let validNamesMsg := MessageData.orList <| unused.map (m!"`{·}`") |>.toList
pure <| MessageData.hint' m!"Perhaps you meant one of the following parameter names: {validNamesMsg}"
throwError m!"Invalid argument {nameStr} {.andList names} for function `{ctx.funId}`" ++ hint
private def isDone (ctx : Context) : Bool :=
ctx.paramDeclIdx ≥ ctx.paramDecls.size
private def getNextParam (ctx : Context) : (Name × BinderInfo) × Context :=
let i := ctx.paramDeclIdx
let d := ctx.paramDecls[i]!
(d, { ctx with paramDeclIdx := ctx.paramDeclIdx + 1 })
private def throwWrongArgCount (ctx : Context) (tooMany : Bool) : M α := do
let numExpectedArgs :=
(if ctx.explicit then ctx.paramDecls else ctx.paramDecls.filter (·.2.isExplicit)).size
-- If we have too few arguments because we skipped invalid named args, show that error instead
if !tooMany && !ctx.namedArgs.isEmpty then checkNamedArgs
let argKind := if ctx.explicit then "" else "explicit "
let argWord := if numExpectedArgs == 1 then "argument" else "arguments"
let discrepancyKind := if tooMany then "Too many" else "Not enough"
let mut msg := m!"Invalid pattern: {discrepancyKind} arguments to `{ctx.funId}`; \
expected {numExpectedArgs} {argKind}{argWord}"
if !tooMany then
msg := msg ++ .hint' "To ignore all remaining arguments, use the ellipsis notation `..`"
throwError msg
where
checkNamedArgs := do
let mut ctx := ctx
let mut remainingNames : Std.HashSet Name := {}
-- If there were too few (unnamed) arguments, we may not have processed the parameters that
-- match the outstanding named arguments, so some names in `namedArgs` may be valid
while !isDone ctx do
let ((name, _), ctx') := getNextParam ctx
ctx := ctx'
if let some idx := ctx'.namedArgs.findFinIdx? fun namedArg => namedArg.name == name then
ctx := { ctx with namedArgs := ctx.namedArgs.eraseIdx idx
usedNames := ctx.usedNames.insert name }
if h : !ctx.namedArgs.isEmpty then
throwInvalidNamedArgs ctx h
private def finalize (ctx : Context) : M Syntax := do
if ctx.args.isEmpty then
if h : !ctx.namedArgs.isEmpty then
throwInvalidNamedArgs ctx h
else
let fStx ← `(@$(ctx.funId):ident)
return Syntax.mkApp fStx ctx.newArgs
else
throwWrongArgCount ctx true
private def isNextArgAccessible (ctx : Context) : Bool :=
let i := ctx.paramDeclIdx
match ctx.ctorVal? with
| some ctorVal => i ≥ ctorVal.numParams -- For constructor applications only fields are accessible
| none =>
if h : i < ctx.paramDecls.size then
-- For `[match_pattern]` applications, only explicit parameters are accessible.
let d := ctx.paramDecls[i]
d.2.isExplicit
else
false
private def processVar (idStx : Syntax) : M Syntax := do
unless idStx.isIdent do
throwErrorAt idStx "Invalid pattern variable: Identifier expected, but found{indentD idStx}"
let id := idStx.getId
unless id.eraseMacroScopes.isAtomic do
throwError "Invalid pattern variable: Variable name must be atomic, but `{id}` has multiple components"
if (← get).found.contains id then
throwError "Invalid pattern variable: Variable name `{id}` was already used"
modify fun s => { s with vars := s.vars.push idStx, found := s.found.insert id }
return idStx
private def samePatternsVariables (startingAt : Nat) (s₁ s₂ : State) : Bool := Id.run do
if h₁ : s₁.vars.size = s₂.vars.size then
for h₂ : i in startingAt...s₁.vars.size do
if s₁.vars[i] != s₂.vars[i] then
return false
true
else
false
open TSyntax.Compat in
partial def collect (stx : Syntax) : M Syntax := withRef stx <| withFreshMacroScope do
let k := stx.getKind
if k == identKind then
processId stx
else if k == ``Lean.Parser.Term.app then
processCtorApp stx
else if k == ``Lean.Parser.Term.anonymousCtor then
let elems ← stx[1].getArgs.mapSepElemsM collect
return stx.setArg 1 <| mkNullNode elems
else if k == ``Lean.Parser.Term.dotIdent then
-- TODO: validate that `stx` corresponds to a valid constructor or match pattern
return stx
else if k == ``Lean.Parser.Term.hole then
`(.( $stx ))
else if k == ``Lean.Parser.Term.syntheticHole then
`(.( $stx ))
else if k == ``Lean.Parser.Term.typeAscription then
-- Ignore type term
let t := stx[1]
let t ← collect t
return stx.setArg 1 t
else if k == ``Lean.Parser.Term.explicitUniv then
processCtor stx[0]
else if k == ``Lean.Parser.Term.explicit then
processCtor stx
else if k == ``Lean.Parser.Term.namedPattern then
/- Recall that
```
def namedPattern := check... >> trailing_parser "@" >> optional (atomic (ident >> ":")) >> termParser
```
-/
let id := stx[0]
discard <| processVar id
let h ← if stx[2].isNone then
`(h)
else
pure stx[2][0]
let pat := stx[3]
let pat ← collect pat
discard <| processVar h
``(_root_.namedPattern $id $pat $h)
else if k == ``Lean.Parser.Term.binop then
/-
We support `binop%` syntax in patterns because we
wanted to support `x+1` in patterns.
Recall that the `binop%` syntax was added to improve elaboration of some binary operators: `+` is one of them.
Recall that `HAdd.hAdd` is marked as `[match_pattern]`
TODO for a distant future: make this whole procedure extensible.
-/
-- Check whether the `binop%` operator is marked with `[match_pattern]`,
-- We must check that otherwise Lean will accept operators that are not tagged with this annotation.
let some (.const fName _) ← resolveId? stx[1] "pattern"
| throwCtorExpected none
unless hasMatchPatternAttribute (← getEnv) fName do
throwCtorExpected none
let lhs ← collect stx[2]
let rhs ← collect stx[3]
return stx.setArg 2 lhs |>.setArg 3 rhs
else if k == ``Lean.Parser.Term.unop then
let arg ← collect stx[2]
return stx.setArg 2 arg
else if k == ``Lean.Parser.Term.inaccessible then
return stx
else if k == strLitKind then
return stx
else if k == numLitKind then
return stx
else if k == scientificLitKind then
return stx
else if k == charLitKind then
return stx
else if k == ``Lean.Parser.Term.quotedName || k == ``Lean.Parser.Term.doubleQuotedName then
return stx
else if k == choiceKind then
/- Remark: If there are `Term.structInst` alternatives, we keep only them. This is a hack to get rid of
Set-like notation in patterns. Recall that in Mathlib `{a, b}` can be a set with two elements or the
structure instance `{ a := a, b := b }`. Possible alternative solution: add a `pattern` category, or at least register
the `Syntax` node kinds that are allowed in patterns. -/
let args :=
let args := stx.getArgs
if args.any (·.isOfKind ``Parser.Term.structInst) then
args.filter (·.isOfKind ``Parser.Term.structInst)
else
args
let stateSaved ← get
let arg0 ← collect args[0]!
let stateNew ← get
let mut argsNew := #[arg0]
for arg in args[1...*] do
set stateSaved
argsNew := argsNew.push (← collect arg)
unless samePatternsVariables stateSaved.vars.size stateNew (← get) do
throwError "Invalid pattern: Overloaded notation is only allowed when all alternatives have the same set of pattern variables"
set stateNew
return mkNode choiceKind argsNew
else match stx with
| `({ $[$srcs?,* with]? $fields,* $[..%$ell?]? $[: $ty?]? }) =>
if let some srcs := srcs? then
throwErrorAt (mkNullNode srcs) "Invalid struct instance pattern: `with` is not allowed in patterns"
let fields ← fields.getElems.mapM fun
| `(Parser.Term.structInstField| $lval:structInstLVal := $val) => do
let newVal ← collect val
`(Parser.Term.structInstField| $lval:structInstLVal := $newVal)
| _ => throwInvalidPattern -- `structInstField` should be expanded at this point
`({ $[$srcs?,* with]? $fields,* $[..%$ell?]? $[: $ty?]? })
| _ => throwInvalidPattern
where
processCtorApp (stx : Syntax) : M Syntax := do
let (f, namedArgs, args, ellipsis) ← expandApp stx
if f.getKind == ``Parser.Term.dotIdent then
let namedArgsNew ← namedArgs.mapM fun
-- We must ensure that `ref[1]` remains original to allow named-argument hints
| { ref, name, val := Arg.stx arg } => withRef ref do `(Lean.Parser.Term.namedArgument| ($(ref[1]) := $(← collect arg)))
| _ => unreachable!
let mut argsNew ← args.mapM fun | Arg.stx arg => collect arg | _ => unreachable!
if ellipsis then
argsNew := argsNew.push (mkNode ``Parser.Term.ellipsis #[mkAtomFrom stx ".."])
return Syntax.mkApp f (namedArgsNew ++ argsNew)
else
processCtorAppCore f namedArgs args ellipsis
processCtor (stx : Syntax) : M Syntax := do
processCtorAppCore stx #[] #[] false
/-- Check whether `stx` is a pattern variable or constructor-like (i.e., constructor or constant tagged with `[match_pattern]` attribute) -/
processId (stx : Syntax) : M Syntax := do
match (← resolveId? stx "pattern") with
| none => processVar stx
| some f => match f with
| Expr.const fName _ =>
match (← getEnv).find? fName with
| some (ConstantInfo.ctorInfo _) => processCtor stx
| some _ =>
if hasMatchPatternAttribute (← getEnv) fName then
processCtor stx
else
processVar stx
| none => throwCtorExpected (some stx)
| _ => processVar stx
pushNewArg (accessible : Bool) (ctx : Context) (arg : Arg) : M Context := do
match arg with
| Arg.stx stx =>
let stx ← if accessible then collect stx else pure stx
return { ctx with newArgs := ctx.newArgs.push stx }
| _ => unreachable!
processExplicitArg (accessible : Bool) (ctx : Context) : M Context := do
match ctx.args with
| [] =>
if ctx.ellipsis then
pushNewArg accessible ctx (Arg.stx (← `(_)))
else
throwWrongArgCount ctx false
| arg::args =>
pushNewArg accessible { ctx with args := args } arg
processImplicitArg (accessible : Bool) (ctx : Context) : M Context := do
if ctx.explicit then
processExplicitArg accessible ctx
else
pushNewArg accessible ctx (Arg.stx (← `(_)))
processCtorAppContext (ctx : Context) : M Syntax := do
if isDone ctx then
finalize ctx
else
let accessible := isNextArgAccessible ctx
let (d, ctx) := getNextParam ctx
match ctx.namedArgs.findFinIdx? fun namedArg => namedArg.name == d.1 with
| some idx =>
let arg := ctx.namedArgs[idx]
let ctx := { ctx with namedArgs := ctx.namedArgs.eraseIdx idx
usedNames := ctx.usedNames.insert arg.name }
let ctx ← pushNewArg accessible ctx arg.val
processCtorAppContext ctx
| none =>
let ctx ← match d.2 with
| BinderInfo.implicit => processImplicitArg accessible ctx
| BinderInfo.strictImplicit => processImplicitArg accessible ctx
| BinderInfo.instImplicit => processImplicitArg accessible ctx
| _ => processExplicitArg accessible ctx
processCtorAppContext ctx
processCtorAppCore (f : Syntax) (namedArgs : Array NamedArg) (args : Array Arg) (ellipsis : Bool) : M Syntax := do
let args := args.toList
let (fId, explicit) ← match f with
| `($fId:ident) => pure (fId, false)
| `(@$fId:ident) => pure (fId, true)
| _ =>
throwError "Invalid pattern: Expected an identifier in function position, but found{indentD f}"
let some (Expr.const fName _) ← resolveId? fId "pattern" (withInfo := true) | throwCtorExpected (some fId)
let fInfo ← getConstInfo fName
let paramDecls ← forallTelescopeReducing fInfo.type fun xs _ => xs.mapM fun x => do
let d ← getFVarLocalDecl x
return (d.userName, d.binderInfo)
match fInfo with
| ConstantInfo.ctorInfo val =>
processCtorAppContext
{ funId := fId, explicit := explicit, ctorVal? := val, paramDecls := paramDecls, namedArgs := namedArgs, args := args, ellipsis := ellipsis }
| _ =>
if hasMatchPatternAttribute (← getEnv) fName then
processCtorAppContext
{ funId := fId, explicit := explicit, ctorVal? := none, paramDecls := paramDecls, namedArgs := namedArgs, args := args, ellipsis := ellipsis }
else
throwCtorExpected (some fId)
def main (alt : MatchAltView) : M MatchAltView := do
let patterns ← alt.patterns.mapM fun p => do
trace[Elab.match] "collecting variables at pattern: {p}"
collect p
return { alt with patterns := patterns }
end CollectPatternVars
/--
Collect pattern variables occurring in the `match`-alternative object views.
It also returns the updated views.
-/
def collectPatternVars (alt : MatchAltView) : TermElabM (Array PatternVar × MatchAltView) := do
let (alt, s) ← (CollectPatternVars.main alt).run {}
return (s.vars, alt)
/--
Return the pattern variables in the given pattern.
Remark: this method is not used by the main `match` elaborator, but in the precheck hook and other macros (e.g., at `Do.lean`).
-/
def getPatternVars (patternStx : Syntax) : TermElabM (Array PatternVar) := do
let patternStx ← liftMacroM <| expandMacros patternStx
let (_, s) ← (CollectPatternVars.collect patternStx).run {}
return s.vars
/--
Return the pattern variables occurring in the given patterns.
This method is used in the `match` and `do` notation elaborators
-/
def getPatternsVars (patterns : Array Syntax) : TermElabM (Array PatternVar) := do
let collect : CollectPatternVars.M Unit := do
for pattern in patterns do
discard <| CollectPatternVars.collect (← liftMacroM <| expandMacros pattern)
let (_, s) ← collect.run {}
return s.vars
def getPatternVarNames (pvars : Array PatternVar) : Array Name :=
pvars.map fun x => x.getId
end Lean.Elab.Term