leanprover / leanprover/lean4

bug: metavariable context being rolled back in simp

Open
#5,028 0 comments 5 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug P-low
Dominant language
Lean
Stars
9.2k
Forks
990
Avg merge
1d 17h
Merged PRs (30d)
175

Description

This seems to be the underlying cause of leanprover-community/mathlib4#15785 and leanprover-community/aesop#153 . Unfortunately, since it involves the metaprogramming API to simp, it is difficult to give a small reproduction. The example below uses a minimalistic simp wrapper which uses a pre method to replace occurrences of G α with Nat.zero. Importantly, while doing so it creates and instantiates a universe metavariable, and something in the main simp loop seems to forget that it is instantiated, presumably rolling back the metavariable context while still holding on to the expressions generated in that context, leading to panics and unsolved metavariables in the resulting proofs.

import Lean

axiom F (s : Nat) (f : Nat → Nat) : Nat
@[congr] axiom F_congr {s₁ s₂ : Nat} {f : Nat → Nat} (h : s₁ = s₂) : F s₁ f = F s₂ f
axiom G.{u} : Sort u → Nat
axiom G_zero (α) : G α = Nat.zero

theorem foo : F (G True) (fun x => x) ≤ F (G True) id := by
  open Lean Meta Elab Tactic in run_tac
    let g ← getMainGoal
    let ctx := {
      simpTheorems := #[← Elab.Tactic.simpOnlyBuiltins.foldlM (·.addConst ·) {}]
      congrTheorems := ← getSimpCongrTheorems }
    let pre e := do
      if e.isAppOfArity ``G 1 then
        let u ← mkFreshLevelMVar
        let α := e.appArg!
        guard <| ← isDefEq (← inferType α) (.sort u)
        let pf := Expr.app (.const ``G_zero [u]) α
        -- let pf ← instantiateMVars pf
        logInfo <| repr pf
        logInfo pf
        pure <| .done { expr := .const ``Nat.zero [], proof? := pf }
      else
        pure .continue
    let tgt ← g.getType
    let (res, _) ← Simp.main tgt ctx (methods := { pre })
    logInfo res.proof?
    replaceMainGoal [← applySimpResultToTarget g tgt res]
  apply Nat.le_refl

-- invalid occurrence of universe level 'u_1' at 'foo', it does not occur at the declaration type,
-- nor it is explicit universe level provided by the user, occurring at expression
--   G.{u_1} True
-- at declaration body
--   Eq.mpr (id (congr (congrArg LE.le (F_congr (G_zero True))) (congrArg (fun (x : Nat) ↦ F x id) (G_zero True))))
--     (Nat.le_refl (F Nat.zero fun (x : Nat) ↦ x))

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Run the embedded Lean reproduction and inspect the custom pre method, Simp.main, and applySimpResultToTarget flow. Trace how the universe metavariable created by mkFreshLevelMVar is handled during simplification. Done means the example no longer panics or produces unsolved metavariables or an invalid universe level.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.