blob: 1b824ef014efb4f66d9b8c79ccaf3715a3fb391c [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
-/
module
prelude
public import Lean.Meta.Closure
public import Lean.Meta.Tactic.Contradiction
public import Lean.Meta.GeneralizeTelescope
public import Lean.Meta.Match.Basic
public import Lean.Meta.Match.MatcherApp.Basic
public import Lean.Meta.Match.MVarRenaming
public import Lean.Meta.Match.MVarRenaming
import Lean.Meta.Match.SimpH
import Lean.Meta.Match.SolveOverlap
import Lean.Meta.HasNotBit
import Lean.Meta.Match.CaseArraySizes
import Lean.Meta.Match.CaseValues
import Lean.Meta.Match.NamedPatterns
/-!
This module implements the backend of match compilation. The elaborator has already elaborated
the patterns and the the expected type of the matcher is known.
The match compilation task is represented as a `Problem`, which is then processed interatively by
the `process` function. It has various “moves” which it tries in a particular order, to make progress
on the problem, possibly splitting it.
The high-level overview of moves are
* If no variables are left, process as leaf
* If there is an alternative, solve its constraints
* Else use `contradiction` to prove completeness of the match
* Process “independent prefixes” of patterns. These are patterns that can be processed without
affecting the aother alternatives, and without side effects in the sense of updating the `mvarId`.
These are
- variable patterns; substitute
- inaccessible patterns; add equality constraints
- as-patterns: substitute value and equality
After thes have been processed, we use `.inaccessible x` where `x` is the variable being matched
to mark them as “done”.
* If all patterns start with “done”, drop the first variable
* The first alt has only “done” patterns, drop remaining alts (they're overlapped)
* If the first alternative has its first refutable pattern not at the front, move it to the front.
* If we have both constructor and value patterns, expand the values to constructors.
* If next pattern is not a variable, but an expression, then
- if it is a constructor, behave a bit as if we just did a case split
- else move it to constraints
* If we have constructor patterns, or no alternatives, split by constructor
Use sparse splitting if not all constructors are present
* If match is empty (no alts), drop the variable
* If we have value patterns (e.g. strings), split by value
* If we have array literal patterns, split by array
If we reach this point, the match is not supported.
If only nat value patterns exist, we expand them for better error messages.
Throw error.
-/
public section
namespace Lean.Meta.Match
register_builtin_option backward.match.sparseCases : Bool := {
defValue := true
descr := "if true (the default), generate and use sparse case constructs when splitting inductive
types. In some cases this will prevent Lean from noticing that a match statement is complete
because it performs less case-splitting for the unreachable case. In this case, give explicit
patterns to perform the deeper split with `by contradiction` as the right-hand side.
,"
}
register_builtin_option backward.match.rowMajor : Bool := {
defValue := true
descr := "If true (the default), match compilation will split the discrimnants based \
on position of the first constructor pattern in the first alternative. If false, \
it splits them from left to right, which can lead to unnecessary code bloat."
}
private def mkIncorrectNumberOfPatternsMsg [ToMessageData α]
(discrepancyKind : String) (expected actual : Nat) (pats : List α) :=
let patternsMsg := MessageData.joinSep (pats.map toMessageData) ", "
m!"{discrepancyKind} patterns in match alternative: Expected {expected}, \
but found {actual}:{indentD patternsMsg}"
/--
Throws an error indicating that the alternative at `ref` contains an unexpected number of patterns.
Remark: we allow `α` to be arbitrary because this error may be thrown before or after elaborating
pattern syntax.
-/
def throwIncorrectNumberOfPatternsAt [ToMessageData α]
(ref : Syntax) (discrepancyKind : String) (expected actual : Nat) (pats : List α)
: MetaM Unit := do
throwErrorAt ref (mkIncorrectNumberOfPatternsMsg discrepancyKind expected actual pats)
/--
Logs an error indicating that the alternative at `ref` contains an unexpected number of patterns.
Remark: we allow `α` to be arbitrary because this error may be thrown before or after elaborating
pattern syntax.
-/
def logIncorrectNumberOfPatternsAt [ToMessageData α]
(ref : Syntax) (discrepancyKind : String) (expected actual : Nat) (pats : List α)
: MetaM Unit :=
logErrorAt ref (mkIncorrectNumberOfPatternsMsg discrepancyKind expected actual pats)
/-- The number of patterns in each AltLHS must be equal to the number of discriminants. -/
private def checkNumPatterns (numDiscrs : Nat) (lhss : List AltLHS) : MetaM Unit := do
for lhs in lhss do
let doThrow (kind : String) := withExistingLocalDecls lhs.fvarDecls do
throwIncorrectNumberOfPatternsAt lhs.ref kind numDiscrs lhs.patterns.length
(lhs.patterns.map Pattern.toMessageData)
if lhs.patterns.length < numDiscrs then
doThrow "Not enough"
else if lhs.patterns.length > numDiscrs then
-- This case should be impossible, as an alternative with too many patterns will cause an
-- error to be thrown in `Lean.Elab.Term.elabPatterns`
doThrow "Too many"
/--
Execute `k hs` where `hs` contains new equalities `h : lhs[i] = rhs[i]` for each `discrInfos[i] = some h`.
Assume `lhs.size == rhs.size == discrInfos.size`
-/
private partial def withEqs (lhs rhs : Array Expr) (discrInfos : Array DiscrInfo) (k : Array Expr → MetaM α) : MetaM α := do
go 0 #[]
where
go (i : Nat) (hs : Array Expr) : MetaM α := do
if i < lhs.size then
if let some hName := discrInfos[i]!.hName? then
withLocalDeclD hName (← mkEqHEq lhs[i]! rhs[i]!) fun h =>
go (i+1) (hs.push h)
else
go (i+1) hs
else
k hs
/-- Given a list of `AltLHS`, create a minor premise for each one, convert them into `Alt`, and then execute `k` -/
private def withAlts {α} (motive : Expr) (discrs : Array Expr) (discrInfos : Array DiscrInfo)
(lhss : List AltLHS) (isSplitter : Option Overlaps)
(k : List Alt → Array Expr → Array AltParamInfo → MetaM α) : MetaM α :=
loop lhss [] #[] #[] #[]
where
mkSplitterHyps (idx : Nat) (lhs : AltLHS) (notAlts : Array Expr) : MetaM (Array Expr × Array Nat) := do
withExistingLocalDecls lhs.fvarDecls do
let patterns ← lhs.patterns.toArray.mapM (Pattern.toExpr · (annotate := true))
let mut hs := #[]
let mut notAltIdxs := #[]
for overlappingIdx in isSplitter.get!.overlapping idx do
let notAlt := notAlts[overlappingIdx]!
let h ← instantiateForall notAlt patterns
if let some h ← simpH? h patterns.size then
notAltIdxs := notAltIdxs.push overlappingIdx
hs := hs.push h
trace[Meta.Match.debug] "hs for {lhs.ref}: {hs}"
return (hs, notAltIdxs)
mkMinorType (xs : Array Expr) (lhs : AltLHS) (notAltHs : Array Expr): MetaM Expr :=
withExistingLocalDecls lhs.fvarDecls do
let args ← lhs.patterns.toArray.mapM (Pattern.toExpr · (annotate := true))
let minorType := mkAppN motive args
withEqs discrs args discrInfos fun eqs => do
let minorType ← mkForallFVars eqs minorType
let minorType ← mkArrowN notAltHs minorType
mkForallFVars xs minorType
mkNotAlt (xs : Array Expr) (lhs : AltLHS) : MetaM Expr := do
withExistingLocalDecls lhs.fvarDecls do
let mut notAlt := mkConst ``False
for discr in discrs.reverse, pattern in lhs.patterns.reverse do
notAlt ← mkArrow (← mkEqHEq discr (← pattern.toExpr)) notAlt
notAlt ← mkForallFVars (discrs ++ xs) notAlt
return notAlt
loop (lhss : List AltLHS) (alts : List Alt) (minors : Array Expr) (altInfos : Array AltParamInfo) (notAlts : Array Expr) : MetaM α := do
match lhss with
| [] => k alts.reverse minors altInfos
| lhs::lhss =>
let idx := alts.length
let xs := lhs.fvarDecls.toArray.map LocalDecl.toExpr
let (notAltHs, notAltIdxs) ← if isSplitter.isSome then mkSplitterHyps idx lhs notAlts else pure (#[], #[])
let minorType ← mkMinorType xs lhs notAltHs
let notAlt ← mkNotAlt xs lhs
let hasParams := !xs.isEmpty || !notAltHs.isEmpty || discrInfos.any fun info => info.hName?.isSome
let minorType := if hasParams then minorType else mkSimpleThunkType minorType
let minorName := (`h).appendIndexAfter (idx+1)
trace[Meta.Match.debug] "minor premise {minorName} : {minorType}"
withLocalDeclD minorName minorType fun minor => do
let rhs := if hasParams then mkAppN minor xs else mkApp minor (mkConst `Unit.unit)
let minors := minors.push minor
let altInfos := altInfos.push { numFields := xs.size, numOverlaps := notAltHs.size, hasUnitThunk := !hasParams }
let fvarDecls ← lhs.fvarDecls.mapM instantiateLocalDeclMVars
let alt := { ref := lhs.ref, idx := idx, rhs := rhs, fvarDecls := fvarDecls, patterns := lhs.patterns, cnstrs := [], notAltIdxs := notAltIdxs }
let alts := alt :: alts
loop lhss alts minors altInfos (notAlts.push notAlt)
structure State where
/-- Used alternatives -/
used : Std.HashSet Nat := {} -- used alternatives
/--
Overlapped alternatives.
Stored as ordered pairs `(overlapping,overlapped) ∈ overlaps`.
Used during splitter generation to avoid going through all pairs of patterns.
-/
overlaps : Overlaps := {}
counterExamples : List (List Example) := []
/-- Return true if the given (sub-)problem has been solved. -/
private def isDone (p : Problem) : Bool :=
p.vars.isEmpty
/-- Return true if the next element on the `p.vars` list is a variable. -/
private def isNextVar (p : Problem) : Bool :=
match p.vars with
| .fvar _ :: _ => true
| _ => false
private def hasCtorPattern (p : Problem) : Bool :=
p.alts.any fun alt => match alt.patterns with
| .ctor .. :: _ => true
| _ => false
private def hasValPattern (p : Problem) : Bool :=
p.alts.any fun alt => match alt.patterns with
| .val _ :: _ => true
| _ => false
private def hasInaccessiblePattern (p : Problem) : Bool :=
p.alts.any fun alt => match alt.patterns with
| .inaccessible _ :: _ => true
| _ => false
private def hasNatValPattern (p : Problem) : MetaM Bool :=
p.alts.anyM fun alt => do
match alt.patterns with
| .val v :: _ => return (← getNatValue? v).isSome
| _ => return false
private def hasIntValPattern (p : Problem) : MetaM Bool :=
p.alts.anyM fun alt => do
match alt.patterns with
| .val v :: _ => return (← getIntValue? v).isSome
| _ => return false
private def hasVarPattern (p : Problem) : Bool :=
p.alts.any fun alt => match alt.patterns with
| .var _ :: _ => true
| _ => false
private def hasArrayLitPattern (p : Problem) : Bool :=
p.alts.any fun alt => match alt.patterns with
| .arrayLit .. :: _ => true
| _ => false
private def getInductiveVal? (x : Expr) : MetaM (Option InductiveVal) := do
let xType ← inferType x
let xType ← whnfD xType
match xType.getAppFn with
| Expr.const constName _ =>
let cinfo ← getConstInfo constName
match cinfo with
| ConstantInfo.inductInfo val => return some val
| _ => return none
| _ => return none
def isCurrVarInductive (p : Problem) : MetaM Bool := do
match p.vars with
| [] => return false
| x::_ => withGoalOf p do
let val? ← getInductiveVal? x
return val?.isSome
private def isConstructorTransition (p : Problem) : MetaM Bool := do
return (← isCurrVarInductive p)
&& (hasCtorPattern p || p.alts.isEmpty)
&& p.alts.all fun alt => match alt.patterns with
| .ctor .. :: _ => true
| .inaccessible _ :: _ => true -- should be a done pattern by now
| _ => false
private def isValueTransition (p : Problem) : Bool :=
hasValPattern p && hasInaccessiblePattern p &&
p.alts.all fun alt => match alt.patterns with
| .val _ :: _ => true
| .inaccessible _ :: _ => true -- should be a done pattern by now
| _ => false
private def isValueOnlyTransitionCore (p : Problem) (isValue : Expr → MetaM Bool) : MetaM Bool := do
if hasVarPattern p then return false
if !hasValPattern p then return false
p.alts.allM fun alt => do
match alt.patterns with
| .val v :: _ => isValue v
| .ctor .. :: _ => return true
| _ => return false
private def isFinValueTransition (p : Problem) : MetaM Bool :=
isValueOnlyTransitionCore p fun e => return (← getFinValue? e).isSome
private def isBitVecValueTransition (p : Problem) : MetaM Bool :=
isValueOnlyTransitionCore p fun e => return (← getBitVecValue? e).isSome
private def isArrayLitTransition (p : Problem) : Bool :=
hasArrayLitPattern p && hasInaccessiblePattern p &&
p.alts.all fun alt => match alt.patterns with
| .arrayLit .. :: _ => true
| .inaccessible _ :: _ => true -- should be a done pattern by now
| _ => false
private def hasCtor (p : Problem) : Bool :=
!isNextVar p ||
p.alts.any fun alt => match alt.patterns with
| .ctor .. :: _ => true
| _ => false
private def isNatValueTransition (p : Problem) : MetaM Bool := do
return (← hasNatValPattern p) && hasCtor p
/--
Predicate for testing whether we need to expand `Int` value patterns into constructors.
There are two cases:
- We have constructor patterns. Example:
```
| 0, ...
| Int.toVal p, ...
...
```
- We don't have the `else`-case (i.e., inaccessible pattern). This can happen
when the non-value cases are unreachable.
-/
private def isIntValueTransition (p : Problem) : MetaM Bool := do
unless (← hasIntValPattern p) do return false
return hasCtor p || !hasInaccessiblePattern p
/--
If constraint is of the form `e ≋ x` where `x` is a free variable, reorient it
as `x ≋ e` If
- `x` is an `alt`-local declaration
- `e` is not a free variable.
-/
private def reorientCnstrs (alt : Alt) : Alt :=
let cnstrs := alt.cnstrs.map fun (lhs, rhs) =>
if rhs.isFVar && alt.isLocalDecl rhs.fvarId! then
(rhs, lhs)
else if !lhs.isFVar && rhs.isFVar then
(rhs, lhs)
else
(lhs, rhs)
{ alt with cnstrs }
/--
Remove constraints of the form `lhs ≋ rhs` where `lhs` and `rhs` are definitionally equal,
or `lhs` is a free variable.
Dropping unsolved constraints where `lhs` is a free variable seems unsound, but simply leads to later
errors about the type of the alternative not matching the goal type, which is arguably a bit more
user-friendly than showing possibly match-compilation-internal variable names.
-/
private def filterTrivialCnstrs (alt : Alt) : MetaM Alt := do
let cnstrs ← withExistingLocalDecls alt.fvarDecls do
alt.cnstrs.filterM fun (lhs, rhs) => do
if (← isDefEqGuarded lhs rhs) then
return false
else if lhs.isFVar then
return false
else
return true
return { alt with cnstrs }
/--
Find an alternative constraint of the form `x ≋ e` where `x` is an alternative
local declarations, and `x` and `e` have definitionally equal types.
Then, replace `x` with `e` in the alternative, and return it.
Return `none` if the alternative does not contain a constraint of this form.
-/
private def solveSomeLocalFVarIdCnstr? (alt : Alt) : MetaM (Option Alt) :=
withExistingLocalDecls alt.fvarDecls do
let (some (fvarId, val), cnstrs) ← go alt.cnstrs | return none
trace[Meta.Match.match] "found cnstr to solve {mkFVar fvarId} ↦ {val}"
return some <| { alt with cnstrs }.replaceFVarId fvarId val
where
go (cnstrs : List (Expr × Expr)) := do
match cnstrs with
| [] => return (none, [])
| (lhs, rhs) :: cnstrs =>
if lhs.isFVar && alt.isLocalDecl lhs.fvarId! then
if !(← dependsOn rhs lhs.fvarId!) && (← isDefEqGuarded (← inferType lhs) (← inferType rhs)) then
return (some (lhs.fvarId!, rhs), cnstrs)
let (p, cnstrs) ← go cnstrs
return (p, (lhs, rhs) :: cnstrs)
/--
Solve pending alternative constraints and overlap assumptions.
If all constraints can be solved perform assignment `mvarId := alt.rhs`, else throw error.
-/
private partial def solveCnstrs (mvarId : MVarId) (alt : Alt) : StateRefT State MetaM Unit := do
go (reorientCnstrs alt)
where
go (alt : Alt) : StateRefT State MetaM Unit := do
match (← solveSomeLocalFVarIdCnstr? alt) with
| some alt => go alt
| none =>
let alt ← filterTrivialCnstrs alt
if alt.cnstrs.isEmpty then
mvarId.withContext do
let eType ← inferType alt.rhs
let (notAltsMVarIds, _, eType) ← forallMetaBoundedTelescope eType alt.notAltIdxs.size
unless notAltsMVarIds.size = alt.notAltIdxs.size do
throwErrorAt alt.ref "Incorrect number of overlap hypotheses in the right-hand-side, expected {alt.notAltIdxs.size}:{indentExpr eType}"
let targetType ← mvarId.getType
unless (← isDefEqGuarded targetType eType) do
trace[Meta.Match.match] "assignGoalOf failed {eType} =?= {targetType}"
throwErrorAt alt.ref "Dependent elimination failed: Type mismatch when solving this alternative: it {← mkHasTypeButIsExpectedMsg eType targetType}"
for notAltMVarId in notAltsMVarIds do
solveOverlap notAltMVarId.mvarId!
mvarId.assign (mkAppN alt.rhs notAltsMVarIds)
modify fun s => { s with used := s.used.insert alt.idx }
else
trace[Meta.Match.match] "alt has unsolved cnstrs:\n{← alt.toMessageData}"
let mut msg := m!"Dependent match elimination failed: Could not solve constraints"
for (lhs, rhs) in alt.cnstrs do
msg := msg ++ m!"\n {lhs} ≋ {rhs}"
throwErrorAt alt.ref msg
private def isCtorIdxHasNotBit? (e : Expr) : Option FVarId := do
let ctorIdxApp ← isHasNotBit? e
guard ctorIdxApp.isApp
guard ctorIdxApp.getAppFn.isConst
guard <| (`ctorIdx).isSuffixOf ctorIdxApp.getAppFn.constName! -- This should be an env extension maybe
guard ctorIdxApp.appArg!.isFVar
return ctorIdxApp.appArg!.fvarId!
private partial def contradiction (mvarId : MVarId) : MetaM Bool := do
mvarId.withContext do
withTraceNode `Meta.Match.match (msg := (return m!"{exceptBoolEmoji ·} Match.contradiction")) do
trace[Meta.Match.match] m!"Match.contradiction:\n{mvarId}"
if (← mvarId.contradictionCore {}) then
trace[Meta.Match.match] "Contradiction found!"
return true
else
-- Try harder by splitting `ctorIdx x ≠ 23` assumptions
for localDecl in (← getLCtx) do
if let some fvarId := isCtorIdxHasNotBit? localDecl.type then
trace[Meta.Match.match] "splitting ctorIdx assumption {localDecl.type}"
let subgoals ← mvarId.cases fvarId
-- NB: do not use `allM`, we want to process all cases to not leave
-- unsolved metavariables behind.
let allDone ← subgoals.mapM (contradiction ·.mvarId)
return allDone.all id
mvarId.admit
return false
/--
Try to solve the problem by using the first alternative whose pending constraints can be resolved.
-/
private def processLeaf (p : Problem) : StateRefT State MetaM Unit :=
p.mvarId.withContext do
trace[Meta.Match.match] "local context at processLeaf:\n{(← mkFreshTypeMVar).mvarId!}"
go p.alts
where
go (alts : List Alt) : StateRefT State MetaM Unit := do
match alts with
| [] =>
let mvarId ← p.mvarId.exfalso
/- TODO: allow users to configure which tactic is used to close leaves. -/
if (← contradiction mvarId) then
trace[Meta.Match.match] "contradiction succeeded"
else
trace[Meta.Match.match] "contradiction failed, missing alternative"
modify fun s => { s with counterExamples := p.examples :: s.counterExamples }
| alt :: overlapped =>
solveCnstrs p.mvarId alt
for otherAlt in overlapped do
modify fun s => { s with overlaps := s.overlaps.insert alt.idx otherAlt.idx }
trace[Meta.Match.match] "leaf closed"
/-!
Note that we decided to store pending constraints to address issues exposed by #1279 and #1361.
Here is a simplified version of the example on this issue (see test: `1279_simplified.lean`)
```lean
inductive Arrow : Type → Type → Type 1
| id : Arrow a a
| unit : Arrow Unit Unit
| comp : Arrow β γ → Arrow α β → Arrow α γ
deriving Repr
def Arrow.compose (f : Arrow β γ) (g : Arrow α β) : Arrow α γ :=
match f, g with
| id, g => g
| f, id => f
| f, g => comp f g
```
The initial state for the `match`-expression above is
```lean
[Meta.Match.match] remaining variables: [β✝:(Type), γ✝:(Type), f✝:(Arrow β✝ γ✝), g✝:(Arrow α β✝)]
alternatives:
[β:(Type), g:(Arrow α β)] |- [β, .(β), (Arrow.id .(β)), g] => h_1 β g
[γ:(Type), f:(Arrow α γ)] |- [.(α), γ, f, (Arrow.id .(α))] => h_2 γ f
[β:(Type), γ:(Type), f:(Arrow β γ), g:(Arrow α β)] |- [β, γ, f, g] => h_3 β γ f g
```
The first step is a variable-transition which replaces `β` with `β✝` in the first and third alternatives.
The constraint `β✝ ≋ α` in the second alternative used to be discarded. We now store it at the
alternative `cnstrs` field.
-/
private def inLocalDecls (localDecls : List LocalDecl) (fvarId : FVarId) : Bool :=
localDecls.any fun d => d.fvarId == fvarId
private def hasRecursiveType (x : Expr) : MetaM Bool := do
match (← getInductiveVal? x) with
| some val => return val.isRec
| _ => return false
private def hasNonTrivialExample (p : Problem) : Bool :=
p.examples.any fun | Example.underscore => false | _ => true
private def throwCasesException (p : Problem) (ex : Exception) : MetaM α := do
match ex with
| .error ref msg =>
let exampleMsg :=
if hasNonTrivialExample p then m!" after processing{indentD <| examplesToMessageData p.examples}" else ""
throw <| Exception.error ref <| msg.composePreservingKind <| m!"{exampleMsg}\n" ++
"the dependent pattern matcher can solve the following kinds of equations\n" ++
"- <var> = <term> and <term> = <var>\n" ++
"- <term> = <term> where the terms are definitionally equal\n" ++
"- <constructor> = <constructor>, examples: List.cons x xs = List.cons y ys, and List.cons x xs = List.nil"
| _ => throw ex
private def collectCtors (p : Problem) : Array Name :=
p.alts.foldl (init := #[]) fun ctors alt =>
match alt.patterns with
| .ctor n _ _ _ :: _ => if ctors.contains n then ctors else ctors.push n
| _ => ctors
private def processConstructor (p : Problem) : MetaM (Array Problem) := do
trace[Meta.Match.match] "constructor step"
let x :: xs := p.vars | unreachable!
let interestingCtors? ←
-- We use a sparse case analysis only if there is at least one non-constructor pattern,
-- but not just because there are constructors missing (in that case we benefit from
-- the eager split in ruling out constructors by type or by a more explicit error message)
if backward.match.sparseCases.get (← getOptions) && hasInaccessiblePattern p then
let ctors := collectCtors p
trace[Meta.Match.match] "using sparse cases: {ctors}"
pure (some ctors)
else
pure none
let subgoals? ← commitWhenSome? do
let subgoals ←
try
p.mvarId.cases x.fvarId! (interestingCtors? := interestingCtors?)
catch ex =>
if p.alts.isEmpty then
/- If we have no alternatives and dependent pattern matching fails, then a "missing cases" error is better than a "stuck" error message. -/
return none
else
throwCasesException p ex
if subgoals.isEmpty then
/- Easy case: we have solved problem `p` since there are no subgoals -/
return some #[]
else if !p.alts.isEmpty then
return some subgoals
else do
let isRec ← withGoalOf p <| hasRecursiveType x
/- If there are no alternatives and the type of the current variable is recursive, we do NOT consider
a constructor-transition to avoid nontermination.
TODO: implement a more general approach if this is not sufficient in practice -/
if isRec then
return none
else
return some subgoals
let some subgoals := subgoals? | return #[{ p with vars := xs }]
subgoals.mapM fun subgoal => subgoal.mvarId.withContext do
-- withTraceNode `Meta.Match.match (msg := (return m!"{exceptEmoji ·} case {subgoal.ctorName}")) do
if let some ctorName := subgoal.ctorName then
-- A normal constructor case
let subst := subgoal.subst
let fields := subgoal.fields.toList
let newVars := fields ++ xs
let newVars := newVars.map fun x => x.applyFVarSubst subst
let subex := Example.ctor ctorName <| fields.map fun field => match field with
| .fvar fvarId => Example.var fvarId
| _ => Example.underscore -- This case can happen due to dependent elimination
let examples := p.examples.map <| Example.replaceFVarId x.fvarId! subex
let examples := examples.map <| Example.applyFVarSubst subst
let newAlts := p.alts.filter fun alt => match alt.patterns with
| .ctor n .. :: _ => n == ctorName
| .inaccessible _ :: _ => true
| _ => unreachable!
let newAlts := newAlts.map fun alt => alt.applyFVarSubst subst
let newAlts ← newAlts.mapM fun alt => do
match alt.patterns with
| .ctor _ _ _ fieldPats :: ps => return { alt with patterns := fieldPats ++ ps }
| .inaccessible _ :: ps => return { alt with patterns := fields.map .inaccessible ++ ps }
| _ => unreachable!
return { p with mvarId := subgoal.mvarId, vars := newVars, alts := newAlts, examples := examples }
else
-- A catch-all case
let subst := subgoal.subst
trace[Meta.Match.match] "constructor catch-all case"
let examples := p.examples.map <| Example.applyFVarSubst subst
let newVars := p.vars.map fun x => x.applyFVarSubst subst
let newAlts := p.alts.filter fun alt => match alt.patterns with
| .ctor .. :: _ => false
| _ => true
let newAlts := newAlts.map fun alt => alt.applyFVarSubst subst
return { p with mvarId := subgoal.mvarId, alts := newAlts, vars := newVars, examples := examples }
private def processNonVariable (p : Problem) : MetaM Problem := withGoalOf p do
let x :: xs := p.vars | unreachable!
if let some (ctorVal, xArgs) ← withTransparency .default <| constructorApp'? x then
if hasCtorPattern p then
let xFields := xArgs.extract ctorVal.numParams xArgs.size
let alts ← p.alts.filterMapM fun alt => do
match alt.patterns with
| .ctor ctorName _ _ fields :: ps =>
if ctorName != ctorVal.name then
return none
else
return some { alt with patterns := fields ++ ps }
| .inaccessible _ :: ps =>
return some { alt with patterns := xFields.toList.map .inaccessible ++ ps }
| _ => unreachable!
return { p with alts := alts, vars := xFields.toList ++ xs }
let alts ← p.alts.mapM fun alt => do
match alt.patterns with
| .inaccessible _ :: ps => return { alt with patterns := ps }
| p :: ps => return { alt with patterns := ps, cnstrs := (x, ← p.toExpr) :: alt.cnstrs }
| _ => unreachable!
return { p with alts := alts, vars := xs }
private def collectValues (p : Problem) : Array Expr :=
p.alts.foldl (init := #[]) fun values alt =>
match alt.patterns with
| .val v :: _ => if values.contains v then values else values.push v
| _ => values
private def isFirstPatternInaccessible (alt : Alt) : Bool :=
match alt.patterns with
| .inaccessible _ :: _ => true
| _ => false
private def Pattern.isRefutable : Pattern → Bool
| .var _ => false
| .inaccessible _ => false
| .as _ p _ => p.isRefutable
| .arrayLit .. => true
| .ctor .. => true
| .val .. => true
private def triviallyComplete (p : Problem) : Bool :=
!p.alts.isEmpty && p.alts.getLast!.patterns.all (!·.isRefutable)
private def processValue (p : Problem) : MetaM (Array Problem) := do
trace[Meta.Match.match] "value step"
let x :: xs := p.vars | unreachable!
let values := collectValues p
let needHyps := !triviallyComplete p || p.alts.any (!·.notAltIdxs.isEmpty)
let subgoals ← caseValues p.mvarId x.fvarId! values (needHyps := needHyps)
subgoals.mapIdxM fun i subgoal => do
trace[Meta.Match.match] "processValue subgoal\n{MessageData.ofGoal subgoal.mvarId}"
if h : i < values.size then
let value := values[i]
-- (x = value) branch
let subst := subgoal.subst
trace[Meta.Match.match] "processValue subst: {subst.map.toList.map fun p => mkFVar p.1}, {subst.map.toList.map fun p => p.2}"
let examples := p.examples.map <| Example.replaceFVarId x.fvarId! (Example.val value)
let examples := examples.map <| Example.applyFVarSubst subst
let newAlts := p.alts.filter fun alt => match alt.patterns with
| .val v :: _ => v == value
| .inaccessible _ :: _ => true
| _ => unreachable!
let newAlts := newAlts.map fun alt => alt.applyFVarSubst subst
let newAlts := newAlts.map fun alt => match alt.patterns with
| .val _ :: ps => { alt with patterns := ps }
| .inaccessible _ :: ps => { alt with patterns := ps }
| _ => unreachable!
let newVars := xs.map fun x => x.applyFVarSubst subst
return { p with mvarId := subgoal.mvarId, vars := newVars, alts := newAlts, examples := examples }
else
-- else branch for value
let newAlts := p.alts.filter isFirstPatternInaccessible
return { p with mvarId := subgoal.mvarId, alts := newAlts, vars := x::xs }
private def collectArraySizes (p : Problem) : Array Nat :=
p.alts.foldl (init := #[]) fun sizes alt =>
match alt.patterns with
| .arrayLit _ ps :: _ => let sz := ps.length; if sizes.contains sz then sizes else sizes.push sz
| _ => sizes
private def processArrayLit (p : Problem) : MetaM (Array Problem) := do
trace[Meta.Match.match] "array literal step"
let x :: xs := p.vars | unreachable!
let sizes := collectArraySizes p
let subgoals ← caseArraySizes p.mvarId x.fvarId! sizes
subgoals.mapIdxM fun i subgoal => do
if h : i < sizes.size then
let size := sizes[i]
let subst := subgoal.subst
let elems := subgoal.elems.toList
let newVars := elems.map mkFVar ++ xs
let newVars := newVars.map fun x => x.applyFVarSubst subst
let subex := Example.arrayLit <| elems.map Example.var
let examples := p.examples.map <| Example.replaceFVarId x.fvarId! subex
let examples := examples.map <| Example.applyFVarSubst subst
let newAlts := p.alts.filter fun alt => match alt.patterns with
| .arrayLit _ ps :: _ => ps.length == size
| .inaccessible _ :: _ => true
| _ => unreachable!
let newAlts := newAlts.map fun alt => alt.applyFVarSubst subst
let newAlts := newAlts.map fun alt =>
match alt.patterns with
| .arrayLit _ pats :: ps => { alt with patterns := pats ++ ps }
| .inaccessible _ :: ps =>
let patterns := elems.map (fun elem => .inaccessible (mkFVar elem)) ++ ps
{ alt with patterns }
| _ => unreachable!
return { p with mvarId := subgoal.mvarId, vars := newVars, alts := newAlts, examples := examples }
else
-- else branch
let newAlts := p.alts.filter isFirstPatternInaccessible
return { p with mvarId := subgoal.mvarId, alts := newAlts, vars := x::xs }
private def expandNatValuePattern (p : Problem) : MetaM Problem := do
let alts ← p.alts.mapM fun alt => do
match alt.patterns with
| .val n :: ps =>
match (← getNatValue? n) with
| some 0 => return { alt with patterns := .ctor ``Nat.zero [] [] [] :: ps }
| some (n+1) => return { alt with patterns := .ctor ``Nat.succ [] [] [.val (toExpr n)] :: ps }
| _ => return alt
| _ => return alt
return { p with alts := alts }
private def expandIntValuePattern (p : Problem) : MetaM Problem := do
let alts ← p.alts.mapM fun alt => do
match alt.patterns with
| .val n :: ps =>
match (← getIntValue? n) with
| some i =>
if i >= 0 then
return { alt with patterns := .ctor ``Int.ofNat [] [] [.val (toExpr i.toNat)] :: ps }
else
return { alt with patterns := .ctor ``Int.negSucc [] [] [.val (toExpr (-(i + 1)).toNat)] :: ps }
| _ => return alt
| _ => return alt
return { p with alts := alts }
private def expandFinValuePattern (p : Problem) : MetaM Problem := do
let alts ← p.alts.mapM fun alt => do
let .val n :: ps := alt.patterns | return alt
let some ⟨n, v⟩ ← getFinValue? n | return alt
let p ← mkLt (toExpr v.val) (toExpr n)
let h ← mkDecideProof p
return { alt with patterns := .ctor ``Fin.mk [] [toExpr n] [.val (toExpr v.val), .inaccessible h] :: ps }
return { p with alts := alts }
private def expandBitVecValuePattern (p : Problem) : MetaM Problem := do
let alts ← p.alts.mapM fun alt => do
let .val n :: ps := alt.patterns | return alt
let some ⟨_, v⟩ ← getBitVecValue? n | return alt
return { alt with patterns := .ctor ``BitVec.ofFin [] [] [.val (toExpr v.toFin)] :: ps }
return { p with alts := alts }
private def traceStep (msg : String) : StateRefT State MetaM Unit := do
trace[Meta.Match.match] "{msg} step"
private def traceState (p : Problem) : MetaM Unit :=
withGoalOf p (traceM `Meta.Match.match p.toMessageData)
private def throwNonSupported (p : Problem) : MetaM Unit :=
withGoalOf p do
let msg ← p.toMessageData
throwError "Failed to compile pattern matching: Stuck at{indentD msg}"
private def checkNextPatternTypes (p : Problem) : MetaM Unit := do
match p.vars with
| [] => return ()
| x::_ => withGoalOf p do
for alt in p.alts do
withRef alt.ref do
withExistingLocalDecls alt.fvarDecls do
match alt.patterns with
| [] => return ()
| p::_ =>
let e ← p.toExpr
let xType ← inferType x
let eType ← inferType e
unless (← isDefEq xType eType) do
throwError "Type mismatch in pattern: Pattern{indentExpr e}\n{← mkHasTypeButIsExpectedMsg eType xType}"
private def List.moveToFront [Inhabited α] (as : List α) (i : Nat) : List α :=
let rec loop : (as : List α) → (i : Nat) → α × List α
| [], _ => unreachable!
| a::as, 0 => (a, as)
| a::as, i+1 =>
let (b, bs) := loop as i
(b, a::bs)
let (b, bs) := loop as i
b :: bs
/-- Move variable `#i` to the beginning of the to-do list `p.vars`. -/
private def moveToFront (p : Problem) (i : Nat) : Problem :=
if i == 0 then
p
else if i < p.vars.length then
{ p with
vars := List.moveToFront p.vars i
alts := p.alts.map fun alt => { alt with patterns := List.moveToFront alt.patterns i }
}
else
p
/--
Returns the index of the first pattern in the first alternative that is refutable
(i.e. not a variable or inaccessible pattern). We want to handle these first
so that the generated code branches in the order suggested by the user's code.
-/
private def firstRefutablePattern (p : Problem) : Option Nat :=
match p.alts with
| alt:: _ => alt.patterns.findIdx? (·.isRefutable)
| _ => none
def isExFalsoTransition (p : Problem) : MetaM Bool := do
if p.alts.isEmpty then
withGoalOf p do
let targetType ← p.mvarId.getType
return !targetType.isFalse
else
return false
def processExFalso (p : Problem) : MetaM Problem := do
let mvarId' ← p.mvarId.exfalso
return { p with mvarId := mvarId' }
/--
Does any alternative have a pattern that can be independently handled (variable, inaccessible,
as-pattern) before any refutable pattern?
-/
def hasIndependentPatterns (p : Problem) : Bool :=
p.alts.any fun alt => Id.run do
for v in p.vars, p in alt.patterns do
match p with
| .inaccessible e =>
if e == v then
-- Skip inaccessible pattern that's are equal to the variable, these are “done”
continue
else
return true
| .var .. | .as .. => return true
| .ctor .. | .val .. | .arrayLit .. => return false
return false
def processIndependentPatterns (p : Problem) : MetaM Problem := withGoalOf p do
let alts' ← p.alts.mapM fun alt => do
-- We process only one pattern at a time, for code simplicity and better tracing
-- of the main loop
let mut donePrefix := 0
for var in p.vars, pat in alt.patterns do
match pat with
| .inaccessible e =>
if e == var then
donePrefix := donePrefix + 1
else
break
| _ => break
match alt.patterns.drop donePrefix with
| [] =>
-- All done here
return alt
| pat :: remainingPats =>
let v := p.vars[donePrefix]!
match pat with
| .inaccessible e =>
trace[Meta.Match.match] "processing inaccessible pattern"
let patterns := (p.vars.take (donePrefix + 1)).map .inaccessible ++ remainingPats
let cnstrs := (v, e) :: alt.cnstrs
return { alt with patterns, cnstrs }
| .var fvarId =>
trace[Meta.Match.match] "processing variable pattern"
let patterns := (p.vars.take (donePrefix + 1)).map .inaccessible ++ remainingPats
let alt' ← withExistingLocalDecls alt.fvarDecls do
if (← isDefEqGuarded (← fvarId.getType) (← inferType v)) then
return { alt with patterns }.replaceFVarId fvarId v
else
let cnstrs := (mkFVar fvarId, v) :: alt.cnstrs
return { alt with patterns, cnstrs }
return alt'
| .as fvarId pat h =>
let patterns := (p.vars.take donePrefix).map .inaccessible ++ [pat] ++ remainingPats
/- We used to use eagerly check the types here (using what was called `checkAndReplaceFVarId`),
but `x` and `fvarId` can have different types when dependent types are being used.
Let's consider the repro for issue #471
```
inductive vec : Nat → Type
| nil : vec 0
| cons : Int → vec n → vec n.succ
def vec_len : vec n → Nat
| vec.nil => 0
| x@(vec.cons h t) => vec_len t + 1
```
we reach the state
```
[Meta.Match.match] remaining variables: [x✝:(vec n✝)]
alternatives:
[n:(Nat), x:(vec (Nat.succ n)), h:(Int), t:(vec n)] |- [x@(vec.cons n h t)] => h_1 n x h t
[x✝:(vec n✝)] |- [x✝] => h_2 n✝ x✝
```
The variables `x✝:(vec n✝)` and `x:(vec (Nat.succ n))` have different types, but we perform the substitution anyway,
because we claim the "discrepancy" will be corrected after we process the pattern `(vec.cons n h t)`.
The right-hand-side is temporarily type incorrect, but we claim this is fine because it will be type correct again after
we the pattern `(vec.cons n h t)`. TODO: try to find a cleaner solution.
-/
let r ← mkEqRefl v
return { alt with patterns }.replaceFVarId fvarId v |>.replaceFVarId h r
| .ctor .. | .val .. | .arrayLit .. =>
return alt
return { p with alts := alts' }
private def isFirstVarDoneTransition (p : Problem) : Bool := Id.run do
if p.alts.isEmpty then
return false
let x :: _ := p.vars | unreachable!
return p.alts.all fun alt => Id.run do
let p :: _ := alt.patterns | unreachable!
return match p with
| .inaccessible e => e == x
| _ => false
private def processFirstVarDone (p : Problem) : Problem :=
{ p with
vars := p.vars.tail!
alts := p.alts.map fun alt => { alt with patterns := alt.patterns.tail! } }
private def tracedForM (xs : Array α) (process : α → StateRefT State MetaM Unit) : StateRefT State MetaM Unit :=
if xs.size > 1 then
for x in xs, i in [:xs.size] do
withTraceNode `Meta.Match.match (msg := (return m!"{exceptEmoji ·} subgoal {i+1}/{xs.size}")) do
process x
else
for x in xs do
process x
private partial def process (p : Problem) : StateRefT State MetaM Unit := do
traceState p
if isDone p then
traceStep ("leaf")
processLeaf p
return
if (← isExFalsoTransition p) then
traceStep ("ex falso")
let p ← processExFalso p
process p
return
if hasIndependentPatterns p then
traceStep ("processing independent prefixes of patterns")
let p ← processIndependentPatterns p
process p
return
if isFirstVarDoneTransition p then
traceStep ("first var done")
let p := processFirstVarDone p
process p
return
if backward.match.rowMajor.get (← getOptions) then
match firstRefutablePattern p with
| some i =>
if i > 0 then
traceStep ("move var to front")
process (moveToFront p i)
return
| none =>
if let alt::(overlapped@(_::_)) := p.alts then
traceStep ("drop all but first alt")
-- all patterns in first alternative are irrefutable, we can drop all other alts
let p := { p with alts := [alt] }
for otherAlt in overlapped do
modify fun s => { s with overlaps := s.overlaps.insert alt.idx otherAlt.idx }
process p
return
if (← isNatValueTransition p) then
traceStep ("nat value to constructor")
process (← expandNatValuePattern p)
return
if (← isIntValueTransition p) then
traceStep ("int value to constructor")
process (← expandIntValuePattern p)
return
if (← isFinValueTransition p) then
traceStep ("fin value to constructor")
process (← expandFinValuePattern p)
return
if (← isBitVecValueTransition p) then
traceStep ("bitvec value to constructor")
process (← expandBitVecValuePattern p)
return
if !isNextVar p then
traceStep ("non variable")
let p ← processNonVariable p
process p
return
if (← isConstructorTransition p) then
let ps ← processConstructor p
tracedForM ps process
return
if p.alts.isEmpty then
-- Note that for inductive types, `isConstructorTransition` does something on empty matches
-- For all others, drop the variable here
traceStep ("empty match transition")
let p := { p with vars := p.vars.tail! }
process p
return
if isValueTransition p then
let ps ← processValue p
tracedForM ps process
return
if isArrayLitTransition p then
let ps ← processArrayLit p
tracedForM ps process
return
if (← hasNatValPattern p) then
-- This branch is reachable when `p`, for example, is just values without an else-alternative.
-- We added it just to get better error messages.
traceStep ("nat value to constructor")
process (← expandNatValuePattern p)
return
checkNextPatternTypes p
throwNonSupported p
private def getUElimPos? (matcherLevels : List Level) (uElim : Level) : MetaM (Option Nat) :=
if uElim == levelZero then
return none
else match matcherLevels.idxOf? uElim with
| none => throwError "Dependent match elimination failed: Universe level not found"
| some pos => return some pos
/- See comment at `mkMatcher` before `mkAuxDefinition` -/
register_builtin_option bootstrap.genMatcherCode : Bool := {
defValue := true
descr := "disable code generation for auxiliary matcher function"
}
private structure MatcherKey where
value : Expr
compile : Bool
-- When a matcher is created in a private context and thus may contain private references, we must
-- not reuse it in an exported context.
isPrivate : Bool
deriving BEq, Hashable
private builtin_initialize matcherExt : EnvExtension (PHashMap MatcherKey Name) ←
registerEnvExtension (pure {}) (asyncMode := .local) -- mere cache, keep it local
/-- Similar to `mkAuxDefinition`, but uses the cache `matcherExt`.
It also returns an Boolean that indicates whether a new matcher function was added to the environment or not. -/
def mkMatcherAuxDefinition (name : Name) (type : Expr) (value : Expr) (isSplitter : Bool) : MetaM (Expr × Option (MatcherInfo → MetaM Unit)) := do
trace[Meta.Match.debug] "{name} : {type} := {value}"
let compile := bootstrap.genMatcherCode.get (← getOptions)
let result ← Closure.mkValueTypeClosure type value (zetaDelta := false)
let env ← getEnv
let mkMatcherConst name :=
mkAppN (mkConst name result.levelArgs.toList) result.exprArgs
let key := { value := result.value, compile, isPrivate := env.header.isModule && isPrivateName name }
let mut nameNew? := none
unless isSplitter do
nameNew? := (matcherExt.getState env).find? key
if nameNew?.isNone && key.isPrivate then
-- private contexts may reuse public matchers
nameNew? := (matcherExt.getState env).find? { key with isPrivate := false }
match nameNew? with
| some nameNew => return (mkMatcherConst nameNew, none)
| none =>
let decl := Declaration.defnDecl (← mkDefinitionValInferringUnsafe name result.levelParams.toList
result.type result.value .abbrev)
trace[Meta.Match.debug] "{name} : {result.type} := {result.value}"
let addMatcher : MatcherInfo → MetaM Unit := fun mi => do
-- matcher bodies should always be exported, if not private anyway
withExporting do
addDecl decl
unless isSplitter do
modifyEnv fun env => matcherExt.modifyState env fun s => s.insert key name
addMatcherInfo name mi
setInlineAttribute name
enableRealizationsForConst name
if compile then
compileDecl decl
return (mkMatcherConst name, some addMatcher)
structure MkMatcherInput where
matcherName : Name
matchType : Expr
discrInfos : Array DiscrInfo
lhss : List AltLHS
isSplitter : Option Overlaps := none
def MkMatcherInput.numDiscrs (m : MkMatcherInput) :=
m.discrInfos.size
def MkMatcherInput.collectFVars (m : MkMatcherInput) : StateRefT CollectFVars.State MetaM Unit := do
m.matchType.collectFVars
m.lhss.forM fun alt => alt.collectFVars
def MkMatcherInput.collectDependencies (m : MkMatcherInput) : MetaM FVarIdSet := do
let (_, s) ← m.collectFVars |>.run {}
let s ← s.addDependencies
return s.fvarSet
/--
Auxiliary method used at `mkMatcher`. It executes `k` in a local context that contains only
the local declarations `m` depends on. This is important because otherwise dependent elimination
may "refine" the types of unnecessary declarations and accidentally introduce unnecessary dependencies
in the auto-generated auxiliary declaration. Note that this is not just an optimization because the
unnecessary dependencies may prevent the termination checker from succeeding. For an example,
see issue #1237.
-/
def withCleanLCtxFor (m : MkMatcherInput) (k : MetaM α) : MetaM α := do
let s ← m.collectDependencies
let lctx ← getLCtx
let lctx := lctx.foldr (init := lctx) fun localDecl lctx =>
if s.contains localDecl.fvarId then lctx else lctx.erase localDecl.fvarId
let localInstances := (← getLocalInstances).filter fun localInst => s.contains localInst.fvar.fvarId!
withLCtx lctx localInstances k
/--
Create a dependent matcher for `matchType` where `matchType` is of the form
`(a_1 : A_1) -> (a_2 : A_2[a_1]) -> ... -> (a_n : A_n[a_1, a_2, ... a_{n-1}]) -> B[a_1, ..., a_n]`
where `n = numDiscrs`, and the `lhss` are the left-hand-sides of the `match`-expression alternatives.
Each `AltLHS` has a list of local declarations and a list of patterns.
The number of patterns must be the same in each `AltLHS`.
The generated matcher has the structure described at `MatcherInfo`. The motive argument is of the form
`(motive : (a_1 : A_1) -> (a_2 : A_2[a_1]) -> ... -> (a_n : A_n[a_1, a_2, ... a_{n-1}]) -> Sort v)`
where `v` is a universe parameter or 0 if `B[a_1, ..., a_n]` is a proposition.
-/
def mkMatcher (input : MkMatcherInput) : MetaM MatcherResult := withCleanLCtxFor input do
let {matcherName, matchType, discrInfos, lhss, isSplitter} := input
let numDiscrs := discrInfos.size
checkNumPatterns numDiscrs lhss
forallBoundedTelescope matchType numDiscrs fun discrs matchTypeBody => do
/- We generate an matcher that can eliminate using different motives with different universe levels.
`uElim` is the universe level the caller wants to eliminate to.
If it is not levelZero, we create a matcher that can eliminate in any universe level.
This is useful for implementing `MatcherApp.addArg` because it may have to change the universe level. -/
let uElim ← getLevel matchTypeBody
let uElimGen ← if uElim == levelZero then pure levelZero else mkFreshLevelMVar
let mkMatcher (type val : Expr) (altInfos : Array AltParamInfo) (s : State) : MetaM MatcherResult := do
trace[Meta.Match.debug] "matcher value: {val}\ntype: {type}"
/- The option `bootstrap.gen_matcher_code` is a helper hack. It is useful, for example,
for compiling `src/Init/Data/Int`. It is needed because the compiler uses `Int.decLt`
for generating code for `Int.casesOn` applications, but `Int.casesOn` is used to
give the reference implementation for
```
@[extern "lean_int_neg"] def neg (n : @& Int) : Int :=
match n with
| ofNat n => negOfNat n
| negSucc n => succ n
```
which is defined **before** `Int.decLt` -/
let (matcher, addMatcher) ← mkMatcherAuxDefinition matcherName type val (isSplitter := input.isSplitter.isSome)
trace[Meta.Match.debug] "matcher levels: {matcher.getAppFn.constLevels!}, uElim: {uElimGen}"
let uElimPos? ← getUElimPos? matcher.getAppFn.constLevels! uElimGen
discard <| isLevelDefEq uElimGen uElim
let addMatcher :=
match addMatcher with
| some addMatcher => addMatcher <|
{ numParams := matcher.getAppNumArgs
altInfos
discrInfos
numDiscrs
uElimPos?
overlaps := s.overlaps
}
| none => pure ()
trace[Meta.Match.debug] "matcher: {matcher}"
let unusedAltIdxs := lhss.length.fold (init := []) fun i _ r =>
if s.used.contains i then r else i::r
return {
matcher,
counterExamples := s.counterExamples,
unusedAltIdxs := unusedAltIdxs.reverse,
addMatcher
}
let motiveType ← mkForallFVars discrs (mkSort uElimGen)
trace[Meta.Match.debug] "motiveType: {motiveType}"
withLocalDeclD `motive motiveType fun motive => do
if discrInfos.any fun info => info.hName?.isSome then
forallBoundedTelescope matchType numDiscrs fun discrs' _ => do
let (mvarType, isEqMask) ← withEqs discrs discrs' discrInfos fun eqs => do
let mvarType ← mkForallFVars eqs (mkAppN motive discrs')
let isEqMask ← eqs.mapM fun eq => return (← inferType eq).isEq
return (mvarType, isEqMask)
trace[Meta.Match.debug] "target: {mvarType}"
withAlts motive discrs discrInfos lhss isSplitter fun alts minors altInfos => do
let mvar ← mkFreshExprMVar mvarType
trace[Meta.Match.debug] "goal\n{mvar.mvarId!}"
let examples := discrs'.toList.map fun discr => Example.var discr.fvarId!
let (_, s) ← (process { mvarId := mvar.mvarId!, vars := discrs'.toList, alts := alts, examples := examples }).run {}
let val ← mkLambdaFVars discrs' mvar
trace[Meta.Match.debug] "matcher\nvalue: {val}\ntype: {← inferType val}"
let mut rfls := #[]
let mut isEqMaskIdx := 0
for discr in discrs, info in discrInfos do
if info.hName?.isSome then
if isEqMask[isEqMaskIdx]! then
rfls := rfls.push (← mkEqRefl discr)
else
rfls := rfls.push (← mkHEqRefl discr)
isEqMaskIdx := isEqMaskIdx + 1
let val := mkAppN (mkAppN val discrs) rfls
let args := #[motive] ++ discrs ++ minors
let val ← mkLambdaFVars args val
let type ← mkForallFVars args (mkAppN motive discrs)
mkMatcher type val altInfos s
else
let mvarType := mkAppN motive discrs
trace[Meta.Match.debug] "target: {mvarType}"
withAlts motive discrs discrInfos lhss isSplitter fun alts minors altInfos => do
let mvar ← mkFreshExprMVar mvarType
let examples := discrs.toList.map fun discr => Example.var discr.fvarId!
let (_, s) ← (process { mvarId := mvar.mvarId!, vars := discrs.toList, alts := alts, examples := examples }).run {}
let args := #[motive] ++ discrs ++ minors
let type ← mkForallFVars args mvarType
let val ← mkLambdaFVars args mvar
mkMatcher type val altInfos s
def getMkMatcherInputInContext (matcherApp : MatcherApp) (unfoldNamed : Bool) : MetaM MkMatcherInput := do
let matcherName := matcherApp.matcherName
let some matcherInfo ← getMatcherInfo? matcherName
| throwError "Internal error during match expression elaboration: Could not find a matcher named `{matcherName}`"
let matcherConst ← getConstVal matcherName
let matcherType ← instantiateTypeLevelParams matcherConst matcherApp.matcherLevels.toList
let matcherType ← instantiateForall matcherType <| matcherApp.params ++ #[matcherApp.motive]
let matchType ← do
let u :=
if let some idx := matcherInfo.uElimPos?
then mkLevelParam matcherConst.levelParams.toArray[idx]!
else levelZero
forallBoundedTelescope matcherType (some matcherInfo.numDiscrs) fun discrs _ => do
mkForallFVars discrs (mkConst ``PUnit [u])
let matcherType ← instantiateForall matcherType matcherApp.discrs
let lhss ← forallBoundedTelescope matcherType (some matcherApp.alts.size) fun alts _ =>
alts.mapM fun alt => do
let ty ← inferType alt
let ty ← if unfoldNamed then unfoldNamedPattern ty else pure ty
forallTelescope ty fun xs body => do
let xs ← xs.filterM fun x => dependsOn body x.fvarId!
body.withApp fun _ args => do
let ctx ← getLCtx
let localDecls := xs.map ctx.getFVar!
let patterns ← args.mapM Match.toPattern
return {
ref := Syntax.missing
fvarDecls := localDecls.toList
patterns := patterns.toList : Match.AltLHS }
return { matcherName, matchType, discrInfos := matcherInfo.discrInfos, lhss := lhss.toList }
def withMkMatcherInput (matcherName : Name) (unfoldNamed : Bool) (k : MkMatcherInput → MetaM α) : MetaM α := do
let some matcherInfo ← getMatcherInfo? matcherName
| throwError "withMkMatcherInput: {.ofConstName matcherName} is not a matcher"
let matcherConst ← getConstInfo matcherName
forallBoundedTelescope matcherConst.type matcherInfo.arity fun xs _ => do
let matcherApp ← mkConstWithLevelParams matcherConst.name
let matcherApp := mkAppN matcherApp xs
let some matcherApp ← matchMatcherApp? matcherApp
| throwError "withMkMatcherInput: {.ofConstName matcherName} does not produce a matcher application"
let mkMatcherInput ← getMkMatcherInputInContext matcherApp unfoldNamed
k mkMatcherInput
end Match
builtin_initialize
registerTraceClass `Meta.Match.match
registerTraceClass `Meta.Match.debug
registerTraceClass `Meta.Match.unify
end Lean.Meta