simp only [Option.some_bind] -> maximum recursion depth has been reached

[tobiasgrosser]

Prerequisites

Please put an X between the brackets as you perform the following steps:

• Check that your issue is not already filed:
  https://github.com/leanprover/lean4/issues
• Reduce the issue to a minimal, self-contained, reproducible test case.
  Avoid dependencies to Mathlib or Batteries.
• Test your test case against the latest nightly release, for example on
  https://live.lean-lang.org/#project=lean-nightly
  (You can also use the settings there to switch to “Lean nightly”)

Description

theorem extracted_1 (e : Option (BitVec 32)) :
  none =
    Option.bind e fun x =>
      if x ≥ 32 then none
      else
        (some ((BitVec.ofInt 32 (-33)).sshiftRight x.toNat)).bind fun y =>
          if y = 0#32 then none else some 0#32 := by
  simp only [Option.some_bind]
/-
tactic 'simp' failed, nested error:
maximum recursion depth has been reached
use `set_option maxRecDepth <num>` to increase limit
use `set_option diagnostics true` to get diagnostic information
-/

Context

I checked with @hargoniX and this seems to be a bug.

Steps to Reproduce

1. Copy into live.lean-lang.org
2. Observe the error

Expected behavior: No error recursion error

Actual behavior: Either simp successfully terminating or reporting that it could not find a simp-lemma to apply

Versions

Lean 4.14.0-nightly-2024-11-03
Target: x86_64-unknown-linux-gnu

Further information

On our dataset, this (or a similar) simp error fires 82 times.

Impact

Add 👍 to issues you consider important. If others are impacted by this issue, please ask them to add 👍 to it.

[Kha]

Brief inspection: seems to be a complex isDefEq after application of the simp theorem

  [Meta.Tactic.simp.rewrite] Option.some_bind:1000, (some ((BitVec.ofInt 32 (-33)).sshiftRight x.toNat)).bind fun y =>
      if y = 0#32 then none
      else some 0#32 ==> if (BitVec.ofInt 32 (-33)).sshiftRight x.toNat = 0#32 then none else some 0#32 
  [Meta.Tactic.simp.unify] eq_self:1000, failed to unify
      ?a = ?a
    with
      (BitVec.ofInt 32 (-33)).sshiftRight x.toNat = 0#32 
  [Meta.Tactic.simp.congr] ite_congr not modified 
  [Meta.isDefEq] [0.031529] 💥️ ?h₃ =?= fun a => Eq.refl (if (BitVec.ofInt 32 (-33)).sshiftRight x.toNat = 0#32 then none else some 0#32) ▶

seal BitVec.sshiftRight turns it into a (kernel) deep recursion detected

[tobiasgrosser]

Thank you for investigating. Let me know if I can help in some way to get this resolved.

[nomeata]

Fallout from #5479 maybe? Maybe that defeq check needs to run at reduced transparency? (But this being in the simplifier isn't the transparency already reduced?)

[tobiasgrosser]

Brief inspection: seems to be a complex isDefEq after application of the simp theorem

  [Meta.Tactic.simp.rewrite] Option.some_bind:1000, (some ((BitVec.ofInt 32 (-33)).sshiftRight x.toNat)).bind fun y =>
      if y = 0#32 then none
      else some 0#32 ==> if (BitVec.ofInt 32 (-33)).sshiftRight x.toNat = 0#32 then none else some 0#32 
  [Meta.Tactic.simp.unify] eq_self:1000, failed to unify
      ?a = ?a
    with
      (BitVec.ofInt 32 (-33)).sshiftRight x.toNat = 0#32 
  [Meta.Tactic.simp.congr] ite_congr not modified 
  [Meta.isDefEq] [0.031529] 💥️ ?h₃ =?= fun a => Eq.refl (if (BitVec.ofInt 32 (-33)).sshiftRight x.toNat = 0#32 then none else some 0#32) ▶

seal BitVec.sshiftRight turns it into a (kernel) deep recursion detected

We get the same error in #5724, where this is due to the kernel trying to reduce a rfl lemma.

[tobiasgrosser]

We see kernel timeouts about 300 times, which is around 10% of our test cases, so getting kernel issues fixed would help us to get these down, which indeed would be super helpful.

[nomeata]

Ok, not due to #5479 likely, and maybe just a duplicate of #5724: The following avoids the problem:

def Option.some_bind' := (fun () => @Option.some_bind) ()

theorem extracted_1 (e : Option (BitVec 32)) :
  none =
    Option.bind e fun x =>
      if x ≥ 32 then none
      else
        (some ((BitVec.ofInt 32 (-33)).sshiftRight x.toNat)).bind fun y =>
          if y = 0#32 then none else some 0#32 := by
  simp only [Option.some_bind']

This redefinition of the lemma makes it a non-rfl lemma, so we effectively get the effect of Leo’s #4595 and the kernel is happy.

[nomeata]

It’s still somewhat surprising that this is an elab-time timeout, and not (just) a kernel-time timeout, so more debugging to be done.

We’ll probably going to merge #4595 (off by default) so that in these cases you can at least set a flag and hopefully make progress in your work, and maybe it can be on by default eventually.

[tobiasgrosser]

It’s still somewhat surprising that this is an elab-time timeout, and not (just) a kernel-time timeout, so more debugging to be done.

We’ll probably going to merge #4595 (off by default) so that in these cases you can at least set a flag and hopefully make progress in your work, and maybe it can be on by default eventually.

Merging #4595 would be incredibly useful. This would also allow us to gather data at a bit wider scale, which can then potentially inform a more complete solution.