| /- | |
| Copyright (c) 2020 Microsoft Corporation. All rights reserved. | |
| Released under Apache 2.0 license as described in the file LICENSE. | |
| Authors: Leonardo de Moura | |
| -/ | |
| import Lean.Util.CollectLevelParams | |
| import Lean.Util.Recognizers | |
| import Lean.Compiler.ExternAttr | |
| import Lean.Meta.Check | |
| import Lean.Meta.Closure | |
| import Lean.Meta.Tactic.Cases | |
| import Lean.Meta.Tactic.Contradiction | |
| import Lean.Meta.GeneralizeTelescope | |
| import Lean.Meta.Match.Basic | |
| import Lean.Meta.Match.MVarRenaming | |
| import Lean.Meta.Match.CaseValues | |
| namespace Lean.Meta.Match | |
| /- The number of patterns in each AltLHS must be equal to majors.length -/ | |
| private def checkNumPatterns (majors : Array Expr) (lhss : List AltLHS) : MetaM Unit := do | |
| let num := majors.size | |
| if lhss.any fun lhs => lhs.patterns.length != num then | |
| throwError "incorrect number of patterns" | |
| /- 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) (lhss : List AltLHS) (k : List Alt → Array (Expr × Nat) → MetaM α) : MetaM α := | |
| loop lhss [] #[] | |
| where | |
| mkMinorType (xs : Array Expr) (lhs : AltLHS) : MetaM Expr := | |
| withExistingLocalDecls lhs.fvarDecls do | |
| let args ← lhs.patterns.toArray.mapM (Pattern.toExpr · (annotate := true)) | |
| let minorType := mkAppN motive args | |
| mkForallFVars xs minorType | |
| loop (lhss : List AltLHS) (alts : List Alt) (minors : Array (Expr × Nat)) : MetaM α := do | |
| match lhss with | |
| | [] => k alts.reverse minors | |
| | lhs::lhss => | |
| let xs := lhs.fvarDecls.toArray.map LocalDecl.toExpr | |
| let minorType ← mkMinorType xs lhs | |
| let (minorType, minorNumParams) := if !xs.isEmpty then (minorType, xs.size) else (mkSimpleThunkType minorType, 1) | |
| let idx := alts.length | |
| let minorName := (`h).appendIndexAfter (idx+1) | |
| trace[Meta.Match.debug] "minor premise {minorName} : {minorType}" | |
| withLocalDeclD minorName minorType fun minor => do | |
| let rhs := if xs.isEmpty then mkApp minor (mkConst `Unit.unit) else mkAppN minor xs | |
| let minors := minors.push (minor, minorNumParams) | |
| let fvarDecls ← lhs.fvarDecls.mapM instantiateLocalDeclMVars | |
| let alts := { ref := lhs.ref, idx := idx, rhs := rhs, fvarDecls := fvarDecls, patterns := lhs.patterns : Alt } :: alts | |
| loop lhss alts minors | |
| def assignGoalOf (p : Problem) (e : Expr) : MetaM Unit := | |
| withGoalOf p (assignExprMVar p.mvarId e) | |
| structure State where | |
| used : Std.HashSet Nat := {} -- used alternatives | |
| 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 | |
| | Expr.fvar _ _ :: _ => true | |
| | _ => false | |
| private def hasAsPattern (p : Problem) : Bool := | |
| p.alts.any fun alt => match alt.patterns with | |
| | Pattern.as _ _ :: _ => true | |
| | _ => false | |
| private def hasCtorPattern (p : Problem) : Bool := | |
| p.alts.any fun alt => match alt.patterns with | |
| | Pattern.ctor _ _ _ _ :: _ => true | |
| | _ => false | |
| private def hasValPattern (p : Problem) : Bool := | |
| p.alts.any fun alt => match alt.patterns with | |
| | Pattern.val _ :: _ => true | |
| | _ => false | |
| private def hasNatValPattern (p : Problem) : Bool := | |
| p.alts.any fun alt => match alt.patterns with | |
| | Pattern.val v :: _ => v.isNatLit | |
| | _ => false | |
| private def hasVarPattern (p : Problem) : Bool := | |
| p.alts.any fun alt => match alt.patterns with | |
| | Pattern.var _ :: _ => true | |
| | _ => false | |
| private def hasArrayLitPattern (p : Problem) : Bool := | |
| p.alts.any fun alt => match alt.patterns with | |
| | Pattern.arrayLit _ _ :: _ => true | |
| | _ => false | |
| private def isVariableTransition (p : Problem) : Bool := | |
| p.alts.all fun alt => match alt.patterns with | |
| | Pattern.inaccessible _ :: _ => true | |
| | Pattern.var _ :: _ => true | |
| | _ => false | |
| private def isConstructorTransition (p : Problem) : Bool := | |
| (hasCtorPattern p || p.alts.isEmpty) | |
| && p.alts.all fun alt => match alt.patterns with | |
| | Pattern.ctor _ _ _ _ :: _ => true | |
| | Pattern.var _ :: _ => true | |
| | Pattern.inaccessible _ :: _ => true | |
| | _ => false | |
| private def isValueTransition (p : Problem) : Bool := | |
| hasVarPattern p && hasValPattern p | |
| && p.alts.all fun alt => match alt.patterns with | |
| | Pattern.val _ :: _ => true | |
| | Pattern.var _ :: _ => true | |
| | _ => false | |
| private def isArrayLitTransition (p : Problem) : Bool := | |
| hasArrayLitPattern p && hasVarPattern p | |
| && p.alts.all fun alt => match alt.patterns with | |
| | Pattern.arrayLit _ _ :: _ => true | |
| | Pattern.var _ :: _ => true | |
| | _ => false | |
| private def isNatValueTransition (p : Problem) : Bool := | |
| hasNatValPattern p | |
| && (!isNextVar p || | |
| p.alts.any fun alt => match alt.patterns with | |
| | Pattern.ctor _ _ _ _ :: _ => true | |
| | Pattern.inaccessible _ :: _ => true | |
| | _ => false) | |
| private def processSkipInaccessible (p : Problem) : Problem := | |
| match p.vars with | |
| | [] => unreachable! | |
| | x :: xs => do | |
| let alts := p.alts.map fun alt => match alt.patterns with | |
| | Pattern.inaccessible _ :: ps => { alt with patterns := ps } | |
| | _ => unreachable! | |
| { p with alts := alts, vars := xs } | |
| private def processLeaf (p : Problem) : StateRefT State MetaM Unit := | |
| match p.alts with | |
| | [] => do | |
| trace[Meta.Match.match] "missing alternative" | |
| admit p.mvarId | |
| modify fun s => { s with counterExamples := p.examples :: s.counterExamples } | |
| | alt :: _ => do | |
| -- TODO: check whether we have unassigned metavars in rhs | |
| liftM $ assignGoalOf p alt.rhs | |
| modify fun s => { s with used := s.used.insert alt.idx } | |
| private def processAsPattern (p : Problem) : MetaM Problem := | |
| match p.vars with | |
| | [] => unreachable! | |
| | x :: xs => withGoalOf p do | |
| let alts ← p.alts.mapM fun alt => match alt.patterns with | |
| | Pattern.as fvarId p :: ps => { alt with patterns := p :: ps }.checkAndReplaceFVarId fvarId x | |
| | _ => pure alt | |
| pure { p with alts := alts } | |
| private def processVariable (p : Problem) : MetaM Problem := | |
| match p.vars with | |
| | [] => unreachable! | |
| | x :: xs => withGoalOf p do | |
| let alts ← p.alts.mapM fun alt => match alt.patterns with | |
| | Pattern.inaccessible _ :: ps => pure { alt with patterns := ps } | |
| | Pattern.var fvarId :: ps => { alt with patterns := ps }.checkAndReplaceFVarId fvarId x | |
| | _ => unreachable! | |
| pure { p with alts := alts, vars := xs } | |
| private def throwInductiveTypeExpected {α} (e : Expr) : MetaM α := do | |
| let t ← inferType e | |
| throwError "failed to compile pattern matching, inductive type expected{indentExpr e}\nhas type{indentExpr t}" | |
| private def inLocalDecls (localDecls : List LocalDecl) (fvarId : FVarId) : Bool := | |
| localDecls.any fun d => d.fvarId == fvarId | |
| namespace Unify | |
| structure Context where | |
| altFVarDecls : List LocalDecl | |
| structure State where | |
| fvarSubst : FVarSubst := {} | |
| abbrev M := ReaderT Context $ StateRefT State MetaM | |
| def isAltVar (fvarId : FVarId) : M Bool := do | |
| return inLocalDecls (← read).altFVarDecls fvarId | |
| def expandIfVar (e : Expr) : M Expr := do | |
| match e with | |
| | Expr.fvar _ _ => return (← get).fvarSubst.apply e | |
| | _ => return e | |
| def occurs (fvarId : FVarId) (v : Expr) : Bool := | |
| Option.isSome $ v.find? fun e => match e with | |
| | Expr.fvar fvarId' _ => fvarId == fvarId' | |
| | _=> false | |
| def assign (fvarId : FVarId) (v : Expr) : M Bool := do | |
| if occurs fvarId v then | |
| trace[Meta.Match.unify] "assign occurs check failed, {mkFVar fvarId} := {v}" | |
| pure false | |
| else | |
| let ctx ← read | |
| if (← isAltVar fvarId) then | |
| trace[Meta.Match.unify] "{mkFVar fvarId} := {v}" | |
| modify fun s => { s with fvarSubst := s.fvarSubst.insert fvarId v } | |
| pure true | |
| else | |
| trace[Meta.Match.unify] "assign failed variable is not local, {mkFVar fvarId} := {v}" | |
| pure false | |
| partial def unify (a : Expr) (b : Expr) : M Bool := do | |
| trace[Meta.Match.unify] "{a} =?= {b}" | |
| if (← isDefEq a b) then | |
| pure true | |
| else | |
| let a' ← whnfD (← expandIfVar a) | |
| let b' ← whnfD (← expandIfVar b) | |
| if a != a' || b != b' then | |
| unify a' b' | |
| else match a, b with | |
| | Expr.fvar aFvarId _, Expr.fvar bFVarId _ => assign aFvarId b <||> assign bFVarId a | |
| | Expr.fvar aFvarId _, b => assign aFvarId b | |
| | a, Expr.fvar bFVarId _ => assign bFVarId a | |
| | Expr.app aFn aArg _, Expr.app bFn bArg _ => unify aFn bFn <&&> unify aArg bArg | |
| | _, _ => pure false | |
| end Unify | |
| private def unify? (altFVarDecls : List LocalDecl) (a b : Expr) : MetaM (Option FVarSubst) := do | |
| let a ← instantiateMVars a | |
| let b ← instantiateMVars b | |
| let (b, s) ← Unify.unify a b { altFVarDecls := altFVarDecls} |>.run {} | |
| if b then | |
| pure s.fvarSubst | |
| else | |
| trace[Meta.Match.unify] "failed to unify {a} =?= {b}" | |
| pure none | |
| private def expandVarIntoCtor? (alt : Alt) (fvarId : FVarId) (ctorName : Name) : MetaM (Option Alt) := | |
| withExistingLocalDecls alt.fvarDecls do | |
| let env ← getEnv | |
| let ldecl ← getLocalDecl fvarId | |
| let expectedType ← inferType (mkFVar fvarId) | |
| let expectedType ← whnfD expectedType | |
| let (ctorLevels, ctorParams) ← getInductiveUniverseAndParams expectedType | |
| let ctor := mkAppN (mkConst ctorName ctorLevels) ctorParams | |
| let ctorType ← inferType ctor | |
| forallTelescopeReducing ctorType fun ctorFields resultType => do | |
| let ctor := mkAppN ctor ctorFields | |
| let alt := alt.replaceFVarId fvarId ctor | |
| let ctorFieldDecls ← ctorFields.mapM fun ctorField => getLocalDecl ctorField.fvarId! | |
| let newAltDecls := ctorFieldDecls.toList ++ alt.fvarDecls | |
| let subst? ← unify? newAltDecls resultType expectedType | |
| match subst? with | |
| | none => pure none | |
| | some subst => | |
| let newAltDecls := newAltDecls.filter fun d => !subst.contains d.fvarId -- remove declarations that were assigned | |
| let newAltDecls := newAltDecls.map fun d => d.applyFVarSubst subst -- apply substitution to remaining declaration types | |
| let patterns := alt.patterns.map fun p => p.applyFVarSubst subst | |
| let rhs := subst.apply alt.rhs | |
| let ctorFieldPatterns := ctorFields.toList.map fun ctorField => match subst.get ctorField.fvarId! with | |
| | e@(Expr.fvar fvarId _) => if inLocalDecls newAltDecls fvarId then Pattern.var fvarId else Pattern.inaccessible e | |
| | e => Pattern.inaccessible e | |
| pure $ some { alt with fvarDecls := newAltDecls, rhs := rhs, patterns := ctorFieldPatterns ++ patterns } | |
| 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 => pure (some val) | |
| | _ => pure none | |
| | _ => pure none | |
| private def hasRecursiveType (x : Expr) : MetaM Bool := do | |
| match (← getInductiveVal? x) with | |
| | some val => pure val.isRec | |
| | _ => pure false | |
| /- Given `alt` s.t. the next pattern is an inaccessible pattern `e`, | |
| try to normalize `e` into a constructor application. | |
| If it is not a constructor, throw an error. | |
| Otherwise, if it is a constructor application of `ctorName`, | |
| update the next patterns with the fields of the constructor. | |
| Otherwise, return none. -/ | |
| def processInaccessibleAsCtor (alt : Alt) (ctorName : Name) : MetaM (Option Alt) := do | |
| let env ← getEnv | |
| match alt.patterns with | |
| | p@(Pattern.inaccessible e) :: ps => | |
| trace[Meta.Match.match] "inaccessible in ctor step {e}" | |
| withExistingLocalDecls alt.fvarDecls do | |
| -- Try to push inaccessible annotations. | |
| let e ← whnfD e | |
| match e.constructorApp? env with | |
| | some (ctorVal, ctorArgs) => | |
| if ctorVal.name == ctorName then | |
| let fields := ctorArgs.extract ctorVal.numParams ctorArgs.size | |
| let fields := fields.toList.map Pattern.inaccessible | |
| pure $ some { alt with patterns := fields ++ ps } | |
| else | |
| pure none | |
| | _ => throwErrorAt alt.ref "dependent match elimination failed, inaccessible pattern found{indentD p.toMessageData}\nconstructor expected" | |
| | _ => unreachable! | |
| 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 | |
| | Exception.error ref msg => | |
| let exampleMsg := | |
| if hasNonTrivialExample p then m!" after processing{indentD <| examplesToMessageData p.examples}" else "" | |
| throw <| Exception.error ref <| m!"{msg}{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 processConstructor (p : Problem) : MetaM (Array Problem) := do | |
| trace[Meta.Match.match] "constructor step" | |
| let env ← getEnv | |
| match p.vars with | |
| | [] => unreachable! | |
| | x :: xs => do | |
| let subgoals? ← commitWhenSome? do | |
| let subgoals ← | |
| try | |
| cases p.mvarId x.fvarId! | |
| catch ex => | |
| if p.alts.isEmpty then | |
| /- If we have no alternatives and dependent pattern matching fails, then a "missing cases" error is bettern 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 -/ | |
| pure (some #[]) | |
| else if !p.alts.isEmpty then | |
| pure (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 pure none | |
| else pure (some subgoals) | |
| match subgoals? with | |
| | none => pure #[{ p with vars := xs }] | |
| | some subgoals => | |
| subgoals.mapM fun subgoal => withMVarContext subgoal.mvarId do | |
| 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 subgoal.ctorName $ fields.map fun field => match field with | |
| | Expr.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 | |
| | Pattern.ctor n _ _ _ :: _ => n == subgoal.ctorName | |
| | Pattern.var _ :: _ => true | |
| | Pattern.inaccessible _ :: _ => true | |
| | _ => false | |
| let newAlts := newAlts.map fun alt => alt.applyFVarSubst subst | |
| let newAlts ← newAlts.filterMapM fun alt => match alt.patterns with | |
| | Pattern.ctor _ _ _ fields :: ps => pure $ some { alt with patterns := fields ++ ps } | |
| | Pattern.var fvarId :: ps => expandVarIntoCtor? { alt with patterns := ps } fvarId subgoal.ctorName | |
| | Pattern.inaccessible _ :: _ => processInaccessibleAsCtor alt subgoal.ctorName | |
| | _ => unreachable! | |
| pure { mvarId := subgoal.mvarId, vars := newVars, alts := newAlts, examples := examples } | |
| private def processNonVariable (p : Problem) : MetaM Problem := | |
| match p.vars with | |
| | [] => unreachable! | |
| | x :: xs => withGoalOf p do | |
| let x ← whnfD x | |
| let env ← getEnv | |
| match x.constructorApp? env with | |
| | some (ctorVal, xArgs) => | |
| let alts ← p.alts.filterMapM fun alt => match alt.patterns with | |
| | Pattern.ctor n _ _ fields :: ps => | |
| if n != ctorVal.name then | |
| pure none | |
| else | |
| pure $ some { alt with patterns := fields ++ ps } | |
| | Pattern.inaccessible _ :: _ => processInaccessibleAsCtor alt ctorVal.name | |
| | p :: _ => throwError "failed to compile pattern matching, inaccessible pattern or constructor expected{indentD p.toMessageData}" | |
| | _ => unreachable! | |
| let xFields := xArgs.extract ctorVal.numParams xArgs.size | |
| pure { p with alts := alts, vars := xFields.toList ++ xs } | |
| | none => | |
| let alts ← p.alts.filterMapM fun alt => match alt.patterns with | |
| | Pattern.inaccessible e :: ps => do | |
| if (← isDefEq x e) then | |
| pure $ some { alt with patterns := ps } | |
| else | |
| pure none | |
| | p :: _ => throwError "failed to compile pattern matching, unexpected pattern{indentD p.toMessageData}\ndiscriminant{indentExpr x}" | |
| | _ => unreachable! | |
| pure { p with alts := alts, vars := xs } | |
| private def collectValues (p : Problem) : Array Expr := | |
| p.alts.foldl (init := #[]) fun values alt => | |
| match alt.patterns with | |
| | Pattern.val v :: _ => if values.contains v then values else values.push v | |
| | _ => values | |
| private def isFirstPatternVar (alt : Alt) : Bool := | |
| match alt.patterns with | |
| | Pattern.var _ :: _ => true | |
| | _ => false | |
| private def processValue (p : Problem) : MetaM (Array Problem) := do | |
| trace[Meta.Match.match] "value step" | |
| match p.vars with | |
| | [] => unreachable! | |
| | x :: xs => do | |
| let values := collectValues p | |
| let subgoals ← caseValues p.mvarId x.fvarId! values | |
| subgoals.mapIdxM fun i subgoal => do | |
| if h : i.val < values.size then | |
| let value := values.get ⟨i, h⟩ | |
| -- (x = value) branch | |
| let subst := subgoal.subst | |
| 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 | |
| | Pattern.val v :: _ => v == value | |
| | Pattern.var _ :: _ => true | |
| | _ => false | |
| let newAlts := newAlts.map fun alt => alt.applyFVarSubst subst | |
| let newAlts := newAlts.map fun alt => match alt.patterns with | |
| | Pattern.val _ :: ps => { alt with patterns := ps } | |
| | Pattern.var fvarId :: ps => | |
| let alt := { alt with patterns := ps } | |
| alt.replaceFVarId fvarId value | |
| | _ => unreachable! | |
| let newVars := xs.map fun x => x.applyFVarSubst subst | |
| pure { mvarId := subgoal.mvarId, vars := newVars, alts := newAlts, examples := examples } | |
| else | |
| -- else branch for value | |
| let newAlts := p.alts.filter isFirstPatternVar | |
| pure { 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 | |
| | Pattern.arrayLit _ ps :: _ => let sz := ps.length; if sizes.contains sz then sizes else sizes.push sz | |
| | _ => sizes | |
| private def expandVarIntoArrayLit (alt : Alt) (fvarId : FVarId) (arrayElemType : Expr) (arraySize : Nat) : MetaM Alt := | |
| withExistingLocalDecls alt.fvarDecls do | |
| let fvarDecl ← getLocalDecl fvarId | |
| let varNamePrefix := fvarDecl.userName | |
| let rec loop | |
| | n+1, newVars => | |
| withLocalDeclD (varNamePrefix.appendIndexAfter (n+1)) arrayElemType fun x => | |
| loop n (newVars.push x) | |
| | 0, newVars => do | |
| let arrayLit ← mkArrayLit arrayElemType newVars.toList | |
| let alt := alt.replaceFVarId fvarId arrayLit | |
| let newDecls ← newVars.toList.mapM fun newVar => getLocalDecl newVar.fvarId! | |
| let newPatterns := newVars.toList.map fun newVar => Pattern.var newVar.fvarId! | |
| pure { alt with fvarDecls := newDecls ++ alt.fvarDecls, patterns := newPatterns ++ alt.patterns } | |
| loop arraySize #[] | |
| private def processArrayLit (p : Problem) : MetaM (Array Problem) := do | |
| trace[Meta.Match.match] "array literal step" | |
| match p.vars with | |
| | [] => unreachable! | |
| | x :: xs => do | |
| let sizes := collectArraySizes p | |
| let subgoals ← caseArraySizes p.mvarId x.fvarId! sizes | |
| subgoals.mapIdxM fun i subgoal => do | |
| if h : i.val < sizes.size then | |
| let size := sizes.get! 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 | |
| | Pattern.arrayLit _ ps :: _ => ps.length == size | |
| | Pattern.var _ :: _ => true | |
| | _ => false | |
| let newAlts := newAlts.map fun alt => alt.applyFVarSubst subst | |
| let newAlts ← newAlts.mapM fun alt => match alt.patterns with | |
| | Pattern.arrayLit _ pats :: ps => pure { alt with patterns := pats ++ ps } | |
| | Pattern.var fvarId :: ps => do | |
| let α ← getArrayArgType <| subst.apply x | |
| expandVarIntoArrayLit { alt with patterns := ps } fvarId α size | |
| | _ => unreachable! | |
| pure { mvarId := subgoal.mvarId, vars := newVars, alts := newAlts, examples := examples } | |
| else do | |
| -- else branch | |
| let newAlts := p.alts.filter isFirstPatternVar | |
| pure { p with mvarId := subgoal.mvarId, alts := newAlts, vars := x::xs } | |
| private def expandNatValuePattern (p : Problem) : Problem := do | |
| let alts := p.alts.map fun alt => match alt.patterns with | |
| | Pattern.val (Expr.lit (Literal.natVal 0) _) :: ps => { alt with patterns := Pattern.ctor `Nat.zero [] [] [] :: ps } | |
| | Pattern.val (Expr.lit (Literal.natVal (n+1)) _) :: ps => { alt with patterns := Pattern.ctor `Nat.succ [] [] [Pattern.val (mkNatLit n)] :: ps } | |
| | _ => alt | |
| { p with alts := alts } | |
| private def traceStep (msg : String) : StateRefT State MetaM Unit := | |
| 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}" | |
| def isCurrVarInductive (p : Problem) : MetaM Bool := do | |
| match p.vars with | |
| | [] => pure false | |
| | x::_ => withGoalOf p do | |
| let val? ← getInductiveVal? x | |
| pure val?.isSome | |
| 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 | |
| match alt.patterns with | |
| | [] => pure () | |
| | p::_ => | |
| let e ← p.toExpr | |
| let xType ← inferType x | |
| let eType ← inferType e | |
| unless (← isDefEq xType eType) do | |
| throwError "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 := do | |
| if i == 0 then | |
| p | |
| else if h : i < p.vars.length then | |
| let x := p.vars.get i h | |
| return { p with | |
| vars := List.moveToFront p.vars i | |
| alts := p.alts.map fun alt => { alt with patterns := List.moveToFront alt.patterns i } | |
| } | |
| else | |
| p | |
| private partial def process (p : Problem) : StateRefT State MetaM Unit := | |
| search 0 | |
| where | |
| /- If `p.vars` is empty, then we are done. Otherwise, we process `p.vars[0]`. -/ | |
| tryToProcess (p : Problem) : StateRefT State MetaM Unit := withIncRecDepth do | |
| traceState p | |
| let isInductive ← liftM $ isCurrVarInductive p | |
| if isDone p then | |
| processLeaf p | |
| else if hasAsPattern p then | |
| traceStep ("as-pattern") | |
| let p ← processAsPattern p | |
| process p | |
| else if isNatValueTransition p then | |
| traceStep ("nat value to constructor") | |
| process (expandNatValuePattern p) | |
| else if !isNextVar p then | |
| traceStep ("non variable") | |
| let p ← processNonVariable p | |
| process p | |
| else if isInductive && isConstructorTransition p then | |
| let ps ← processConstructor p | |
| ps.forM process | |
| else if isVariableTransition p then | |
| traceStep ("variable") | |
| let p ← processVariable p | |
| process p | |
| else if isValueTransition p then | |
| let ps ← processValue p | |
| ps.forM process | |
| else if isArrayLitTransition p then | |
| let ps ← processArrayLit p | |
| ps.forM process | |
| else 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) | |
| else | |
| checkNextPatternTypes p | |
| throwNonSupported p | |
| /- Return `true` if `type` does not depend on the first `i` elements in `xs` -/ | |
| checkVarDeps (xs : List Expr) (i : Nat) (type : Expr) : MetaM Bool := do | |
| match i, xs with | |
| | 0, _ => return true | |
| | _, [] => unreachable! | |
| | i+1, x::xs => | |
| if x.isFVar then | |
| if (← dependsOn type x.fvarId!) then | |
| return false | |
| checkVarDeps xs i type | |
| /-- | |
| Auxiliary method for `search`. Find next variable to "try". | |
| `i` is the position of the variable s.t. `tryToProcess` failed. | |
| We only consider variables that do not depend on other variables at `p.vars`. -/ | |
| findNext (i : Nat) : MetaM (Option Nat) := do | |
| if h : i < p.vars.length then | |
| let x := p.vars.get i h | |
| if (← checkVarDeps p.vars i (← inferType x)) then | |
| return i | |
| else | |
| findNext (i+1) | |
| else | |
| return none | |
| /-- | |
| Auxiliary method for trying the next variable to process. | |
| It moves variable `#i` to the front of the to-do list and invokes `tryToProcess`. | |
| Note that for non-dependent elimination, variable `#0` always work. | |
| If variable `#i` fails, we use `findNext` to select the next variable to try. | |
| Remark: the "missing cases" error is not considered a failure. -/ | |
| search (i : Nat) : StateRefT State MetaM Unit := do | |
| let s₁ ← getThe Meta.State | |
| let s₂ ← get | |
| let p' := moveToFront p i | |
| try | |
| tryToProcess p' | |
| catch ex => | |
| match (← withGoalOf p <| findNext (i+1)) with | |
| | none => throw ex | |
| | some j => | |
| trace[Meta.Match.match] "failed with #{i}, trying #{j}{indentD ex.toMessageData}" | |
| set s₁; set s₂; search j | |
| private def getUElimPos? (matcherLevels : List Level) (uElim : Level) : MetaM (Option Nat) := | |
| if uElim == levelZero then | |
| return none | |
| else match matcherLevels.toArray.indexOf? uElim with | |
| | none => throwError "dependent match elimination failed, universe level not found" | |
| | some pos => return some pos.val | |
| /- See comment at `mkMatcher` before `mkAuxDefinition` -/ | |
| register_builtin_option bootstrap.genMatcherCode : Bool := { | |
| defValue := true | |
| group := "bootstrap" | |
| descr := "disable code generation for auxiliary matcher function" | |
| } | |
| builtin_initialize matcherExt : EnvExtension (Std.PHashMap (Expr × Bool) Name) ← registerEnvExtension (pure {}) | |
| /- 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) : MetaM (Bool × Expr) := do | |
| trace[Meta.debug] "{name} : {type} := {value}" | |
| let compile := bootstrap.genMatcherCode.get (← getOptions) | |
| let result ← Closure.mkValueTypeClosure type value (zeta := false) | |
| let env ← getEnv | |
| match (matcherExt.getState env).find? (result.value, compile) with | |
| | some nameNew => return (false, mkAppN (mkConst nameNew result.levelArgs.toList) result.exprArgs) | |
| | none => | |
| let decl := Declaration.defnDecl { | |
| name := name, | |
| levelParams := result.levelParams.toList, | |
| type := result.type, | |
| value := result.value, | |
| hints := ReducibilityHints.regular (getMaxHeight env result.value + 1), | |
| safety := if env.hasUnsafe result.type || env.hasUnsafe result.value then DefinitionSafety.unsafe else DefinitionSafety.safe | |
| } | |
| trace[Meta.debug] "{name} : {result.type} := {result.value}" | |
| addDecl decl | |
| if compile then | |
| compileDecl decl | |
| modifyEnv fun env => matcherExt.modifyState env fun s => s.insert (result.value, compile) name | |
| return (true, mkAppN (mkConst name result.levelArgs.toList) result.exprArgs) | |
| /- | |
| 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 (matcherName : Name) (matchType : Expr) (numDiscrs : Nat) (lhss : List AltLHS) : MetaM MatcherResult := | |
| forallBoundedTelescope matchType numDiscrs fun majors matchTypeBody => do | |
| checkNumPatterns majors lhss | |
| /- 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 motiveType ← mkForallFVars majors (mkSort uElimGen) | |
| withLocalDeclD `motive motiveType fun motive => do | |
| trace[Meta.Match.debug] "motiveType: {motiveType}" | |
| let mvarType := mkAppN motive majors | |
| trace[Meta.Match.debug] "target: {mvarType}" | |
| withAlts motive lhss fun alts minors => do | |
| let mvar ← mkFreshExprMVar mvarType | |
| let examples := majors.toList.map fun major => Example.var major.fvarId! | |
| let (_, s) ← (process { mvarId := mvar.mvarId!, vars := majors.toList, alts := alts, examples := examples }).run {} | |
| let args := #[motive] ++ majors ++ minors.map Prod.fst | |
| let type ← mkForallFVars args mvarType | |
| let val ← mkLambdaFVars args mvar | |
| 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 (isNewMatcher, matcher) ← mkMatcherAuxDefinition matcherName type val | |
| trace[Meta.Match.debug] "matcher levels: {matcher.getAppFn.constLevels!}, uElim: {uElimGen}" | |
| let uElimPos? ← getUElimPos? matcher.getAppFn.constLevels! uElimGen | |
| discard <| isLevelDefEq uElimGen uElim | |
| if isNewMatcher then | |
| addMatcherInfo matcherName { numParams := matcher.getAppNumArgs, numDiscrs := numDiscrs, altNumParams := minors.map Prod.snd, uElimPos? := uElimPos? } | |
| setInlineAttribute matcherName | |
| 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 | |
| pure { matcher := matcher, counterExamples := s.counterExamples, unusedAltIdxs := unusedAltIdxs.reverse } | |
| end Match | |
| /- Auxiliary function for MatcherApp.addArg -/ | |
| private partial def updateAlts (typeNew : Expr) (altNumParams : Array Nat) (alts : Array Expr) (i : Nat) : MetaM (Array Nat × Array Expr) := do | |
| if h : i < alts.size then | |
| let alt := alts.get ⟨i, h⟩ | |
| let numParams := altNumParams[i] | |
| let typeNew ← whnfD typeNew | |
| match typeNew with | |
| | Expr.forallE n d b _ => | |
| let alt ← forallBoundedTelescope d (some numParams) fun xs d => do | |
| let alt ← try instantiateLambda alt xs catch _ => throwError "unexpected matcher application, insufficient number of parameters in alternative" | |
| forallBoundedTelescope d (some 1) fun x d => do | |
| let alt ← mkLambdaFVars x alt -- x is the new argument we are adding to the alternative | |
| let alt ← mkLambdaFVars xs alt | |
| pure alt | |
| updateAlts (b.instantiate1 alt) (altNumParams.set! i (numParams+1)) (alts.set ⟨i, h⟩ alt) (i+1) | |
| | _ => throwError "unexpected type at MatcherApp.addArg" | |
| else | |
| pure (altNumParams, alts) | |
| /- Given | |
| - matcherApp `match_i As (fun xs => motive[xs]) discrs (fun ys_1 => (alt_1 : motive (C_1[ys_1])) ... (fun ys_n => (alt_n : motive (C_n[ys_n]) remaining`, and | |
| - expression `e : B[discrs]`, | |
| Construct the term | |
| `match_i As (fun xs => B[xs] -> motive[xs]) discrs (fun ys_1 (y : B[C_1[ys_1]]) => alt_1) ... (fun ys_n (y : B[C_n[ys_n]]) => alt_n) e remaining`, and | |
| We use `kabstract` to abstract the discriminants from `B[discrs]`. | |
| This method assumes | |
| - the `matcherApp.motive` is a lambda abstraction where `xs.size == discrs.size` | |
| - each alternative is a lambda abstraction where `ys_i.size == matcherApp.altNumParams[i]` | |
| -/ | |
| def MatcherApp.addArg (matcherApp : MatcherApp) (e : Expr) : MetaM MatcherApp := | |
| lambdaTelescope matcherApp.motive fun motiveArgs motiveBody => do | |
| unless motiveArgs.size == matcherApp.discrs.size do | |
| -- This error can only happen if someone implemented a transformation that rewrites the motive created by `mkMatcher`. | |
| throwError "unexpected matcher application, motive must be lambda expression with #{matcherApp.discrs.size} arguments" | |
| let eType ← inferType e | |
| let eTypeAbst ← matcherApp.discrs.size.foldRevM (init := eType) fun i eTypeAbst => do | |
| let motiveArg := motiveArgs[i] | |
| let discr := matcherApp.discrs[i] | |
| let eTypeAbst ← kabstract eTypeAbst discr | |
| pure $ eTypeAbst.instantiate1 motiveArg | |
| let motiveBody ← mkArrow eTypeAbst motiveBody | |
| let matcherLevels ← match matcherApp.uElimPos? with | |
| | none => pure matcherApp.matcherLevels | |
| | some pos => | |
| let uElim ← getLevel motiveBody | |
| pure $ matcherApp.matcherLevels.set! pos uElim | |
| let motive ← mkLambdaFVars motiveArgs motiveBody | |
| -- Construct `aux` `match_i As (fun xs => B[xs] → motive[xs]) discrs`, and infer its type `auxType`. | |
| -- We use `auxType` to infer the type `B[C_i[ys_i]]` of the new argument in each alternative. | |
| let aux := mkAppN (mkConst matcherApp.matcherName matcherLevels.toList) matcherApp.params | |
| let aux := mkApp aux motive | |
| let aux := mkAppN aux matcherApp.discrs | |
| check aux | |
| unless (← isTypeCorrect aux) do | |
| throwError "failed to add argument to matcher application, type error when constructing the new motive" | |
| let auxType ← inferType aux | |
| let (altNumParams, alts) ← updateAlts auxType matcherApp.altNumParams matcherApp.alts 0 | |
| pure { matcherApp with | |
| matcherLevels := matcherLevels, | |
| motive := motive, | |
| alts := alts, | |
| altNumParams := altNumParams, | |
| remaining := #[e] ++ matcherApp.remaining | |
| } | |
| builtin_initialize | |
| registerTraceClass `Meta.Match.match | |
| registerTraceClass `Meta.Match.debug | |
| registerTraceClass `Meta.Match.unify | |
| end Lean.Meta |