blob: d18ab6d9ca6e008f55f461f5d974eeda6c37694d [file]
/-
Copyright (c) 2019 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Leonardo de Moura
-/
prelude
import Lean.Meta.InferType
import Lean.Meta.Sorry
/-!
This is not the Kernel type checker, but an auxiliary method for checking
whether terms produced by tactics and `isDefEq` are type correct.
-/
namespace Lean.Meta
private def ensureType (e : Expr) : MetaM Unit := do
discard <| getLevel e
private def checkConstant (constName : Name) (us : List Level) : MetaM Unit := do
let cinfo ← getConstInfo constName
unless us.length == cinfo.levelParams.length do
throwIncorrectNumberOfLevels constName us
private def getFunctionDomain (f : Expr) : MetaM (Expr × BinderInfo) := do
let fType ← inferType f
let fType ← whnfD fType
match fType with
| Expr.forallE _ d _ c => return (d, c)
| _ => throwFunctionExpected f
/--
Given two expressions `a` and `b`, this method tries to annotate terms with `pp.explicit := true`
and other `pp` options to expose "implicit" differences.
For example, suppose `a` and `b` are of the form
```lean
@HashMap Nat Nat eqInst hasInst1
@HashMap Nat Nat eqInst hasInst2
```
By default, the pretty printer formats both of them as `HashMap Nat Nat`.
So, counterintuitive error messages such as
```lean
error: application type mismatch
HashMap.insert m
argument
m
has type
HashMap Nat Nat
but is expected to have type
HashMap Nat Nat
```
would be produced.
By adding `pp.explicit := true`, we can generate the more informative error
```lean
error: application type mismatch
HashMap.insert m
argument
m
has type
@HashMap Nat Nat eqInst hasInst1
but is expected to have type
@HashMap Nat Nat eqInst hasInst2
```
Remark: this method implements simple heuristics; we should extend it as we find other counterintuitive
error messages.
-/
partial def addPPExplicitToExposeDiff (a b : Expr) : MetaM (Expr × Expr) := do
if (← getOptions).getBool `pp.all false || (← getOptions).getBool `pp.explicit false then
return (a, b)
else
-- We want to be able to assign metavariables to work out what why `isDefEq` failed,
-- but we don't want these assignments to leak out of the function.
-- Note: we shouldn't instantiate mvars in `visit` to prevent leakage.
withoutModifyingState do
visit (← instantiateMVars a) (← instantiateMVars b)
where
visit (a b : Expr) : MetaM (Expr × Expr) := do
try
match a, b with
| .mdata _ a', _ =>
let (a', b) ← visit a' b
return (a.updateMData! a', b)
| _, .mdata _ b' =>
let (a, b') ← visit a b'
return (a, b.updateMData! b')
| .app .., .app .. =>
if a.getAppNumArgs != b.getAppNumArgs then
return (a, b)
else if a.getAppFn'.isMVar || b.getAppFn'.isMVar then
-- This is a failed higher-order unification. Do not proceed to `isDefEq`.
return (a, b)
else if !(← isDefEq a.getAppFn b.getAppFn) then
let (fa, fb) ← visit a.getAppFn b.getAppFn
return (mkAppN fa a.getAppArgs, mkAppN fb b.getAppArgs)
else
-- The function might be "overapplied", so we can't use `forallBoundedTelescope`.
-- That is to say, the arity might depend on the values of the arguments.
-- We look for the first explicit argument that is different.
-- Otherwise we look for the first implicit argument.
-- We try `isDefEq` on all arguments to get discretionary mvar assigments.
let mut as := a.getAppArgs
let mut bs := b.getAppArgs
let mut aFnType ← inferType a.getAppFn
let mut bFnType ← inferType b.getAppFn
let mut firstExplicitDiff? := none
let mut firstImplicitDiff? := none
for i in [0:as.size] do
unless aFnType.isForall do aFnType ← withTransparency .all <| whnf aFnType
unless bFnType.isForall do bFnType ← withTransparency .all <| whnf bFnType
-- These pattern matches are expected to succeed:
let .forallE _ _ abody abi := aFnType | return (a, b)
let .forallE _ _ bbody bbi := bFnType | return (a, b)
aFnType := abody.instantiate1 as[i]!
bFnType := bbody.instantiate1 bs[i]!
unless (← isDefEq as[i]! bs[i]!) do
if abi.isExplicit && bbi.isExplicit then
firstExplicitDiff? := firstExplicitDiff? <|> some i
else
firstImplicitDiff? := firstImplicitDiff? <|> some i
-- Some special cases
let fn? : Option Name :=
match a.getAppFn, b.getAppFn with
| .const ca .., .const cb .. => if ca == cb then ca else none
| _, _ => none
if fn? == ``OfNat.ofNat && as.size ≥ 3 && firstImplicitDiff? == some 0 then
-- Even if there is an explicit diff, it is better to see that the type is different.
return (a.setPPNumericTypes true, b.setPPNumericTypes true)
if fn? == ``sorryAx then
-- If these are `sorry`s with differing source positions, make sure the delaborator shows the positions.
if let some { module? := moda? } := isLabeledSorry? a then
if let some { module? := modb? } := isLabeledSorry? b then
if moda? != modb? then
return (a.setOption `pp.sorrySource true, b.setOption `pp.sorrySource true)
-- General case
if let some i := firstExplicitDiff? <|> firstImplicitDiff? then
let (ai, bi) ← visit as[i]! bs[i]!
as := as.set! i ai
bs := bs.set! i bi
let a := mkAppN a.getAppFn as
let b := mkAppN b.getAppFn bs
if firstExplicitDiff?.isSome then
return (a, b)
else
return (a.setPPExplicit true, b.setPPExplicit true)
| .forallE na ta ba bia, .forallE nb tb bb bib =>
if !(← isDefEq ta tb) then
let (ta, tb) ← visit ta tb
let a := Expr.forallE na ta ba bia
let b := Expr.forallE nb tb bb bib
return (a.setPPPiBinderTypes true, b.setPPPiBinderTypes true)
else
-- Then bodies must not be defeq.
withLocalDeclD na ta fun arg => do
let (ba', bb') ← visit (ba.instantiate1 arg) (bb.instantiate1 arg)
return (Expr.forallE na ta (ba'.abstract #[arg]) bia, Expr.forallE nb tb (bb'.abstract #[arg]) bib)
| .lam na ta ba bia, .lam nb tb bb bib =>
if !(← isDefEq ta tb) then
let (ta, tb) ← visit ta tb
let a := Expr.lam na ta ba bia
let b := Expr.lam nb tb bb bib
return (a.setPPFunBinderTypes true, b.setPPFunBinderTypes true)
else
-- Then bodies must not be defeq.
withLocalDeclD na ta fun arg => do
let (ba', bb') ← visit (ba.instantiate1 arg) (bb.instantiate1 arg)
return (Expr.lam na ta (ba'.abstract #[arg]) bia, Expr.lam nb tb (bb'.abstract #[arg]) bib)
| _, _ => return (a, b)
catch _ =>
return (a, b)
def throwLetTypeMismatchMessage {α} (fvarId : FVarId) : MetaM α := do
let lctx ← getLCtx
match lctx.find? fvarId with
| some (LocalDecl.ldecl _ _ _ t v _ _) => do
let vType ← inferType v
let (vType, t) ← addPPExplicitToExposeDiff vType t
throwError "invalid let declaration, term{indentExpr v}\nhas type{indentExpr vType}\nbut is expected to have type{indentExpr t}"
| _ => unreachable!
/--
Return error message "has type{givenType}\nbut is expected to have type{expectedType}"
-/
def mkHasTypeButIsExpectedMsg (givenType expectedType : Expr) : MetaM MessageData := do
try
let givenTypeType ← inferType givenType
let expectedTypeType ← inferType expectedType
let (givenType, expectedType) ← addPPExplicitToExposeDiff givenType expectedType
let (givenTypeType, expectedTypeType) ← addPPExplicitToExposeDiff givenTypeType expectedTypeType
return m!"has type{indentD m!"{givenType} : {givenTypeType}"}\nbut is expected to have type{indentD m!"{expectedType} : {expectedTypeType}"}"
catch _ =>
let (givenType, expectedType) ← addPPExplicitToExposeDiff givenType expectedType
return m!"has type{indentExpr givenType}\nbut is expected to have type{indentExpr expectedType}"
def throwAppTypeMismatch (f a : Expr) : MetaM α := do
let (expectedType, binfo) ← getFunctionDomain f
let mut e := mkApp f a
unless binfo.isExplicit do
e := e.setAppPPExplicit
let aType ← inferType a
throwError "application type mismatch{indentExpr e}\nargument{indentExpr a}\n{← mkHasTypeButIsExpectedMsg aType expectedType}"
def checkApp (f a : Expr) : MetaM Unit := do
let fType ← inferType f
let fType ← whnf fType
match fType with
| Expr.forallE _ d _ _ =>
let aType ← inferType a
unless (← isDefEq d aType) do
throwAppTypeMismatch f a
| _ => throwFunctionExpected (mkApp f a)
def checkProj (structName : Name) (idx : Nat) (e : Expr) : MetaM Unit := do
let structType ← whnf (← inferType e)
let projType ← inferType (mkProj structName idx e)
if (← isProp structType) && !(← isProp projType) then
throwError "invalid projection{indentExpr (mkProj structName idx e)}\nfrom type{indentExpr structType}"
private partial def checkAux (e : Expr) : MetaM Unit := do
check e |>.run
where
check (e : Expr) : MonadCacheT ExprStructEq Unit MetaM Unit :=
checkCache { val := e : ExprStructEq } fun _ => do
match e with
| .forallE .. => checkForall e
| .lam .. => checkLambdaLet e
| .letE .. => checkLambdaLet e
| .const c lvls => checkConstant c lvls
| .app f a => check f; check a; checkApp f a
| .mdata _ e => check e
| .proj s i e => check e; checkProj s i e
| _ => return ()
checkLambdaLet (e : Expr) : MonadCacheT ExprStructEq Unit MetaM Unit :=
lambdaLetTelescope e fun xs b => do
xs.forM fun x => do
let xDecl ← getFVarLocalDecl x;
match xDecl with
| .cdecl (type := t) .. =>
ensureType t
check t
| .ldecl (type := t) (value := v) .. =>
ensureType t
check t
let vType ← inferType v
unless (← isDefEq t vType) do throwLetTypeMismatchMessage x.fvarId!
check v
check b
checkForall (e : Expr) : MonadCacheT ExprStructEq Unit MetaM Unit :=
forallTelescope e fun xs b => do
xs.forM fun x => do
let xDecl ← getFVarLocalDecl x
ensureType xDecl.type
check xDecl.type
ensureType b
check b
/--
Throw an exception if `e` is not type correct.
-/
def check (e : Expr) : MetaM Unit :=
withTraceNode `Meta.check (fun res =>
return m!"{if res.isOk then checkEmoji else crossEmoji} {e}") do
try
withTransparency TransparencyMode.all $ checkAux e
catch ex =>
trace[Meta.check] ex.toMessageData
throw ex
/--
Return true if `e` is type correct.
-/
def isTypeCorrect (e : Expr) : MetaM Bool := do
try
check e
pure true
catch _ =>
pure false
builtin_initialize
registerTraceClass `Meta.check
end Lean.Meta