Skip to content

[Merged by Bors] - feat(Linter): port unused Decidable* instance hypothesis linter#31142

Closed
thorimur wants to merge 56 commits intoleanprover-community:masterfrom
thorimur:unusedDecidable-linter
Closed

[Merged by Bors] - feat(Linter): port unused Decidable* instance hypothesis linter#31142
thorimur wants to merge 56 commits intoleanprover-community:masterfrom
thorimur:unusedDecidable-linter

Conversation

@thorimur
Copy link
Copy Markdown
Contributor

@thorimur thorimur commented Nov 1, 2025

This PR ports the decidableClassical linter from mathlib3 which detects Decidable* instances in the type of a theorem that are unused in the remainder of the type, and can therefore be replaced with classical in the proof.

Prior art: #10235, by @urkud. This is an open pull request from over a year ago that has slowed down, but fulfills a similar purpose. There is a major difference: #10235 contributes an env_linter that does not run interactively, while the current PR is a syntax linter that runs while editing.

In this PR, we lint only user-written theorems (including theorems, lemmas, and instances of Prop classes) by looking for elaborated declarations in the infotree. This opens us up to better logging and try-this suggestions. (While this PR is written with future expansion in mind, these tasks require developing the meta API a bit further and are left to subsequent PRs.)

The infrastructure here is generic to unused instances in the remainder of a type, and can easily be used to write the other FinType, Encodable, etc. linters.

We rename the linter from decidableClassical to unusedDecidableInType with the intention of naming all future related linters according to the same pattern.

This PR does not turn the linter on; it is off by default. Turning the linter on is performed in #31747.

Discussed in part on Zulip here.

In recognition of the work on #10235, and its influence on this PR:

Co-authored-by: Yury Kudryashov urkud@urkud.name


Open in Gitpod

@github-actions github-actions bot added the t-linter Linter label Nov 1, 2025
@github-actions
Copy link
Copy Markdown

github-actions bot commented Nov 1, 2025

PR summary b3cf7a02d3

Import changes for modified files

No significant changes to the import graph

Import changes for all files
Files Import difference
Mathlib.Tactic.Linter.UnusedInstancesInType (new file) 1

Declarations diff

+ Foo
+ Parameter
+ Uses
+ _root_.Lean.ConstantVal.onUnusedInstancesWhere
+ _root_.Lean.Name.unusedInstancesMsg
+ _root_.Lean.Syntax.logUnusedInstancesInTheoremsWhere
+ bar
+ findConstValOfKind?
+ findConstValWithKind?
+ findTheoremConstVal?
+ foo
+ fooSorry
+ fooUsing
+ fooUsing₁
+ fooUsing₂
+ fooUsing₂'
+ fooUsing₂''
+ fooUsing₃
+ foo₂
+ foo₃
+ foo₄
+ getDeclsByBody
+ getTheorems
+ instance : ToMessageData Parameter
+ isDecidableVariant
+ unusedDecidableInType

You can run this locally as follows
## summary with just the declaration names:
./scripts/declarations_diff.sh <optional_commit>

## more verbose report:
./scripts/declarations_diff.sh long <optional_commit>

The doc-module for script/declarations_diff.sh contains some details about this script.


No changes to technical debt.

You can run this locally as

./scripts/technical-debt-metrics.sh pr_summary
  • The relative value is the weighted sum of the differences with weight given by the inverse of the current value of the statistic.
  • The absolute value is the relative value divided by the total sum of the inverses of the current values (i.e. the weighted average of the differences).

@thorimur thorimur force-pushed the unusedDecidable-linter branch from 6bdaa74 to 91aeeb9 Compare November 14, 2025 00:38
@mathlib4-dependent-issues-bot mathlib4-dependent-issues-bot added the blocked-by-other-PR This PR depends on another PR (this label is automatically managed by a bot) label Nov 14, 2025
@github-actions github-actions bot added the large-import Automatically added label for PRs with a significant increase in transitive imports label Nov 16, 2025
@thorimur thorimur force-pushed the unusedDecidable-linter branch 2 times, most recently from 1bdccd2 to aece211 Compare November 16, 2025 22:48
@thorimur thorimur force-pushed the unusedDecidable-linter branch from aece211 to 83f39b6 Compare November 16, 2025 22:49
@thorimur thorimur marked this pull request as ready for review November 16, 2025 22:51
@thorimur thorimur added the t-meta Tactics, attributes or user commands label Nov 16, 2025
@thorimur
Copy link
Copy Markdown
Contributor Author

thorimur commented Nov 24, 2025

Quick question @kim-em : I realized the private annotations were holdovers, since I'm not in a public section. In be160c5 I removed these, and made only the option declaration itself public, but I'm cargo culting there. Is this sensible?

EDIT: discussed it a bit with @grunweg; we agree it's sensible to have the option declaration itself as public API accessible to other metaprograms; still curious what you think.

@adomani
Copy link
Copy Markdown
Contributor

adomani commented Nov 24, 2025

I know from the discussion on Zulip that you did some extensive benchmarking, so maybe my suggestion is not really needed. However, I expect that most lemmas in mathlib should not even be eligible for this linter, since there is neither an active variable [DecidableWhatever ...] in scope, nor is there an explicit [DecidableWhatever ...] in the type signature.

This check simply requires accessing the currently available variables in the scope and traversing (part of) the syntax of the command. These look like substantially cheaper checks than traversing the infotrees and for most of the commands, these would be the only needed checks.

Would it make sense to implement them? Or are there already early exits in the linter that take something like this into account?

@thorimur
Copy link
Copy Markdown
Contributor Author

I know from the discussion on Zulip that you did some extensive benchmarking, so maybe my suggestion is not really needed. However, I expect that most lemmas in mathlib should not even be eligible for this linter, since there is neither an active variable [DecidableWhatever ...] in scope, nor is there an explicit [DecidableWhatever ...] in the type signature.

This check simply requires accessing the currently available variables in the scope and traversing (part of) the syntax of the command. These look like substantially cheaper checks than traversing the infotrees and for most of the commands, these would be the only needed checks.

Would it make sense to implement them? Or are there already early exits in the linter that take something like this into account?

No no, this is certainly very welcome! :) I haven't yet focused on performance optimizations in the infotree (or earlier!) part of the linter, but I certainly plan to in subsequent PRs, especially since this linter architecture will also handle Fintype, Encodable, etc. instances.

I think that an early exit of the kind you mention is a good idea! I'm trying to think of cases where it would early-exit when it shouldn't, but can't. I'd like to test this thoroughly to be sure there are no false negatives, so I will try it in that subsequent performance-oriented PR. :)

(Note: there are also some minor performance improvements we could make to the infotree search itself; collectNodesBottomUp does a bit too much work for our purposes, so I'll try that too.)

@thorimur
Copy link
Copy Markdown
Contributor Author

Okay, I think all comments are resolved (or promised to be resolved in future versions! 😁), and I think making the option declaration public is such a minor change that it's easy to fix later if it's wrong. So, I'm going to pull the trigger on this in an hour or so, barring any further comments. :)

@thorimur
Copy link
Copy Markdown
Contributor Author

bors r+

mathlib-bors bot pushed a commit that referenced this pull request Nov 25, 2025
…1142)

This PR ports the `decidableClassical` linter from mathlib3 which detects `Decidable*` instances in the type of a theorem that are unused in the remainder of the type, and can therefore be replaced with `classical` in the proof.

Prior art: #10235, by @urkud. This is an open pull request from over a year ago that has slowed down, but fulfills a similar purpose. There is a major difference: #10235 contributes an `env_linter` that does not run interactively, while the current PR is a syntax linter that runs while editing.

In this PR, we lint only user-written theorems (including `theorem`s, `lemma`s, and `instance`s of `Prop` classes) by looking for elaborated declarations in the infotree. This opens us up to better logging and try-this suggestions. (While this PR is written with future expansion in mind, these tasks require developing the meta API a bit further and are left to subsequent PRs.)

The infrastructure here is generic to unused instances in the remainder of a type, and can easily be used to write the other `FinType`, `Encodable`, etc. linters.

We rename the linter from `decidableClassical` to `unusedDecidableInType` with the intention of naming all future related linters according to the same pattern.

This PR does *not* turn the linter on; it is off by default. Turning the linter on is performed in #31747.

Discussed in part on Zulip [here](https://leanprover.zulipchat.com/#narrow/channel/287929-mathlib4/topic/Unused.20Decidable.20Instances.20linter/with/558333633).

In recognition of the work on #10235, and its influence on this PR:

Co-authored-by: Yury Kudryashov urkud@urkud.name
Co-authored-by: thorimur <thomasmurrills@gmail.com>
@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Nov 25, 2025

Pull request successfully merged into master.

Build succeeded:

@mathlib-bors mathlib-bors bot changed the title feat(Linter): port unused Decidable* instance hypothesis linter [Merged by Bors] - feat(Linter): port unused Decidable* instance hypothesis linter Nov 25, 2025
@mathlib-bors mathlib-bors bot closed this Nov 25, 2025
mathlib-bors bot pushed a commit that referenced this pull request Nov 29, 2025
This PR turns on the `unusedDecidableInType` syntax linter (#31142) after fixing the remaining violations in #31831, #31934, and #32153.

This also imports the linter into Mathlib.Init and adds the linter to the Mathlib standard set. Given that classicality is embedded in Lean, this is probably the behavior downstream repos who use the mathlib standard set want; if they are specifically constructive repos, the linter can always be turned off in the lakefile.

We exempt the entirety of [Mathlib/Data/Fintype/Quotient.lean](https://github.com/leanprover-community/mathlib4/pull/31747/files#diff-9591d2f3828bee189ea954bc33586ce451536bf00792362f7cdca4f5a8551207), [Mathlib/Order/Heyting/Regular.lean](https://github.com/leanprover-community/mathlib4/pull/31747/files#diff-af85d99e5d2f5561fe837f662f179c58f1ebe2a4ed0432a15260199883850c50), [Mathlib/Logic/Encodable/Basic.lean](https://github.com/leanprover-community/mathlib4/pull/31747/files#diff-db01c9a2d4726fe7ca0e6eb18a7cd485b5a9c6b26ba422dfbe501dcebef3cf77) and a declaration in [Mathlib/Computability/Halting.lean](https://github.com/leanprover-community/mathlib4/pull/31747/files#diff-d47323ee8b4b2321052b4be93715f8b2f3f840f76ec441d8bf75c834b8665b32) since constructivity is desired there. We also exempt `dec_em'`, which is a variant of `Decidable.em` but with the disjuncts reversed.

Many prior violations have already been fixed through the use of #10235, hence the small number of violations picked up by the syntax linter.

Co-authored-by: thorimur <thomasmurrills@gmail.com>
Co-authored-by: Michael Rothgang <rothgang@math.uni-bonn.de>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

delegated This pull request has been delegated to the PR author (or occasionally another non-maintainer). t-linter Linter t-meta Tactics, attributes or user commands

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants