leanprover / leanprover/lean4

Pattern matching on Fin n breaks exhaustivity for n > 15

Open
#9,292 5 comments 3 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

Pattern matching on numbers of Fin n breaks down for n > 15.

Context
def toBase16 : Fin 16 -> Char
| 0 => '0' | 1 => '1'
| 2 => '2' | 3 => '3'
| 4 => '4' | 5 => '5'
| 6 => '6' | 7 => '7'
| 8 => '8' | 9 => '9'
| 10 => 'A' | 11 => 'B'
| 12 => 'C' | 13 => 'D'
| 14 => 'E' | 15 => 'F'
Steps to Reproduce

Run the above code on Lean Nightly.

Actual behavior: The following error message occurs, despite all cases being covered:

Missing cases:
(Fin.mk (Nat.succ (Nat.succ (Nat.succ (Nat.succ (Nat.succ (Nat.succ (Nat.succ (Nat.succ (Nat.succ (Nat.succ (Nat.succ (Nat.succ (Nat.succ (Nat.succ (Nat.succ (Nat.succ _)))))))))))))))) _)

Expected behavior: The code should compile. For reference, all of the following code compiles without issue:

def toBase2 : Fin 2 -> Char
| 0 => '0' | 1 => '1'

def toBase10 : Fin 10 -> Char
| 0 => '0' | 1 => '1'
| 2 => '2' | 3 => '3'
| 4 => '4' | 5 => '5'
| 6 => '6' | 7 => '7'
| 8 => '8' | 9 => '9'

def toBase15 : Fin 15 -> Char
| 0 => '0' | 1 => '1'
| 2 => '2' | 3 => '3'
| 4 => '4' | 5 => '5'
| 6 => '6' | 7 => '7'
| 8 => '8' | 9 => '9'
| 10 => 'A' | 11 => 'B'
| 12 => 'C' | 13 => 'D'
| 14 => 'E'
Versions

Lean 4.22.0-rc3

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 with the minimal Fin 16 pattern-matching example in the issue and run it against Lean nightly, then compare it with the compiling Fin 15 and Fin 10 examples. The fix is done when the Fin 16 definition compiles without a false missing-cases error and exhaustivity checking remains correct.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.