leanprover / leanprover/lean4

Equation compiler fails to prove that match is exhaustive

Open
#5,181 2 comments 0 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

Prerequisites

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

Description

In this code

def g (x : Nat) (hx : x = 0 ∨ x = 1) : Nat :=
  match x with
  | 0 => 0
  | 1 => 1

we get an error message missing cases: (Nat.succ (Nat.succ _)), _. On the other hand, in the code

def g (x : Nat) (hx : x = 0 ∨ x = 1) : Nat :=
  match x with
  | 0 => 0
  | 1 => 1
  | x + 20 => False.elim (by omega)

(which doesn't handle the case (Nat.succ (Nat.succ _)) either), there is no error message.

Steps to Reproduce
  1. Copy the above code into live.lean-lang.org

Expected behavior: Both snippets should produce no error message.

Actual behavior: Error message in the first snippet.

Versions

4.12.0-nightly-2024-08-26 on live.lean-lang.org

Impact

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

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

Start by reproducing both snippets in live.lean-lang.org using the reported Lean nightly version, then trace the equation compiler's exhaustiveness-checking entry point. Done means the first snippet no longer reports a missing case while preserving correct exhaustiveness diagnostics for genuinely incomplete matches.

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
Active
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.