grind explodes on a simple example with `Array.range`
Nobody has claimed this yet.
- 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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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