leanprover / leanprover/lean4

grind explodes on a simple example with `Array.range`

Open
#15,183 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

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

Description

Description

The following grind call timeouts due to an explosion of applied lemmas:

example (n : Nat) : (Array.range (n + 1)).drop n = #[n] := by
  grind

deactivating two grind patterns removes the timeout:

example (n : Nat) : (Array.range (n + 1)).drop n = #[n] := by
  grind [-Array.range'_append, -Array.range'_append_1]

Here is the grind diagnostics of the exploding grind:

[diag] Diagnostics ▼
  [reduction] unfolded declarations (max: 194611, num: 19): ▼
    [] Array.ofFn ↦ 194611 
    [] Array.range ↦ 190157 
    [] List.rec ↦ 128301 
    [] Nat.rec ↦ 100075 
    [] Add.add ↦ 63713 
    [] HAdd.hAdd ↦ 63713 
    [] HSub.hSub ↦ 32616 
    [] Sub.sub ↦ 32616 
    [] Array.extract ↦ 7907 
    [] Array.ofFn.go✝ ↦ 4781 
    [] Array.range' ↦ 4454 
    [] Append.append ↦ 598 
    [] HAppend.hAppend ↦ 598 
    [] Array.append ↦ 557 
    [] Array.foldl ↦ 557 
    [] Array.foldlM ↦ 557 
    [] OfNat.ofNat ↦ 338 
    [] LE.le ↦ 314 
    [] NatCast.natCast ↦ 90 
  [reduction] unfolded reducible declarations (max: 392221, num: 11): ▼
    [] Array.toList ↦ 392221 
    [] Nat.casesOn ↦ 380208 
    [] List.casesOn ↦ 195797 
    [] Decidable.casesOn ↦ 1614 
    [] Bool.casesOn ↦ 1352 
    [] Nat.cast ↦ 997 
    [] optParam ↦ 593 
    [] List.toArray ↦ 408 
    [] outParam ↦ 56 
    [] Array.take ↦ 30 
    [] List.extract ↦ 30 
Steps to Reproduce

Here is a live.lean-lang.org link:
https://live.lean-lang.org/#codez=KYDwhgtgDgNsAEAKAdvAXPAcmALgSnSQEEAnEsATwDpzkBzBFeAangEY88qATEgeyjxUAXngBiANrIAuulEAjCgCh48OiQCWybvAC0unBojA%2BAVxxKloSLEaoM2fIUSly1WgySpWHLrwFC8KKSMnLwiipqmtrwErqulDRg9MAA5AD6YFBQwNoANHoJ7skMGVk52uls0kpAA

Versions

This fails in lean version v4.35.0-rc1 and v4.34.0

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 the linked live.lean-lang.org example with Lean v4.35.0-rc1 or v4.34. Compare the diagnostics with and without -Array.range'_append and -Array.range'_append_1; done means the simple grind call no longer times out or explodes in applied lemmas.

Written by the indexing model from the issue text.

Assessment

Domain
tooling
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.