mirror of
https://github.com/leanprover/lean4.git
synced 2026-03-27 15:24:17 +00:00
Compare commits
46 Commits
hbv/inline
...
v4.29.0
| Author | SHA1 | Date | |
|---|---|---|---|
|
|
98dc76e3c0 | ||
|
|
58db58cad3 | ||
|
|
d9764d755f | ||
|
|
6f69c914f4 | ||
|
|
513160ea59 | ||
|
|
dc8c5e9984 | ||
|
|
38bfb46cd0 | ||
|
|
f5d7f18743 | ||
|
|
2ce5c19116 | ||
|
|
ee890fd1e5 | ||
|
|
b191f74011 | ||
|
|
ab91146423 | ||
|
|
66b444c62a | ||
|
|
d7ebdca954 | ||
|
|
d4c15567af | ||
|
|
09b2b0cdf4 | ||
|
|
9cc7aa8902 | ||
|
|
0bbadfa02a | ||
|
|
04d3ba35de | ||
|
|
b1ce232903 | ||
|
|
0b6cf8e962 | ||
|
|
00659f8e60 | ||
|
|
da0bdb2e07 | ||
|
|
596d13f6d4 | ||
|
|
ef26f95ee6 | ||
|
|
ed910f9b59 | ||
|
|
1c667a8279 | ||
|
|
847c32c0df | ||
|
|
b83c0eefc3 | ||
|
|
1a612b77f6 | ||
|
|
1c61ba6420 | ||
|
|
51cdf26936 | ||
|
|
82f6653bca | ||
|
|
e8ebee6001 | ||
|
|
95583d74bd | ||
|
|
b9bfacd2da | ||
|
|
4962edfada | ||
|
|
86a8eb0051 | ||
|
|
5d86aa4032 | ||
|
|
fd226c813d | ||
|
|
ca43b60947 | ||
|
|
6979644c23 | ||
|
|
52032bde9c | ||
|
|
2152eddfb4 | ||
|
|
83e54b65b6 | ||
|
|
d155c86f9c |
@@ -121,6 +121,42 @@ The nightly build system uses branches and tags across two repositories:
|
||||
|
||||
When a nightly succeeds with mathlib, all three should point to the same commit. Don't confuse these: branches are in the main lean4 repo, dated tags are in lean4-nightly.
|
||||
|
||||
## CI Failures: Investigate Immediately
|
||||
|
||||
**CRITICAL: If the checklist reports `❌ CI: X check(s) failing` for any PR, investigate immediately.**
|
||||
|
||||
Do NOT:
|
||||
- Report it as "CI in progress" or "some checks pending"
|
||||
- Wait for the remaining checks to finish before investigating
|
||||
- Assume it's a transient failure without checking
|
||||
|
||||
DO:
|
||||
1. Run `gh pr checks <number> --repo <owner>/<repo>` to see which specific check failed
|
||||
2. Run `gh run view <run-id> --repo <owner>/<repo> --log-failed` to see the failure output
|
||||
3. Diagnose the failure and report clearly to the user: what failed and why
|
||||
4. Propose a fix if one is obvious (e.g., subverso version mismatch, transient elan install error)
|
||||
|
||||
The checklist now distinguishes `❌ X check(s) failing, Y still in progress` from `🔄 Y check(s) in progress`.
|
||||
Any `❌` in CI status requires immediate investigation — do not move on.
|
||||
|
||||
## Waiting for CI or Merges
|
||||
|
||||
Use `gh pr checks --watch` to block until a PR's CI checks complete (no polling needed).
|
||||
Run these as background bash commands so you get notified when they finish:
|
||||
|
||||
```bash
|
||||
# Watch CI, then check merge state
|
||||
gh pr checks <number> --repo <owner>/<repo> --watch && gh pr view <number> --repo <owner>/<repo> --json state --jq '.state'
|
||||
```
|
||||
|
||||
For multiple PRs, launch one background command per PR in parallel. When each completes,
|
||||
you'll be notified automatically via a task-notification. Do NOT use sleep-based polling
|
||||
loops — `--watch` is event-driven and exits as soon as checks finish.
|
||||
|
||||
Note: `gh pr checks --watch` exits as soon as ALL checks complete (pass or fail). If some checks
|
||||
fail while others are still running, `--watch` will continue until everything settles, then exit
|
||||
with a non-zero code. So a background `--watch` finishing = all checks done; check which failed.
|
||||
|
||||
## Error Handling
|
||||
|
||||
**CRITICAL**: If something goes wrong or a command fails:
|
||||
|
||||
6
.github/workflows/build-template.yml
vendored
6
.github/workflows/build-template.yml
vendored
@@ -66,16 +66,10 @@ jobs:
|
||||
brew install ccache tree zstd coreutils gmp libuv
|
||||
if: runner.os == 'macOS'
|
||||
- name: Checkout
|
||||
if: (!endsWith(matrix.os, '-with-cache'))
|
||||
uses: actions/checkout@v6
|
||||
with:
|
||||
# the default is to use a virtual merge commit between the PR and master: just use the PR
|
||||
ref: ${{ github.event.pull_request.head.sha }}
|
||||
- name: Namespace Checkout
|
||||
if: endsWith(matrix.os, '-with-cache')
|
||||
uses: namespacelabs/nscloud-checkout-action@v8
|
||||
with:
|
||||
ref: ${{ github.event.pull_request.head.sha }}
|
||||
- name: Open Nix shell once
|
||||
run: true
|
||||
if: runner.os == 'Linux'
|
||||
|
||||
32
.github/workflows/ci.yml
vendored
32
.github/workflows/ci.yml
vendored
@@ -163,6 +163,34 @@ jobs:
|
||||
|
||||
echo "Version validation passed: $TAG_MAJOR.$TAG_MINOR.$TAG_PATCH"
|
||||
|
||||
# Also check stage0/src/CMakeLists.txt — the stage0 compiler stamps .olean
|
||||
# headers with its baked-in version, so a mismatch produces .olean files
|
||||
# with the wrong version in the release tarball.
|
||||
STAGE0_MAJOR=$(grep -E "^set\(LEAN_VERSION_MAJOR " stage0/src/CMakeLists.txt | grep -oE '[0-9]+')
|
||||
STAGE0_MINOR=$(grep -E "^set\(LEAN_VERSION_MINOR " stage0/src/CMakeLists.txt | grep -oE '[0-9]+')
|
||||
|
||||
STAGE0_ERRORS=""
|
||||
if [[ "$STAGE0_MAJOR" != "$TAG_MAJOR" ]]; then
|
||||
STAGE0_ERRORS+="LEAN_VERSION_MAJOR: expected $TAG_MAJOR, found $STAGE0_MAJOR\n"
|
||||
fi
|
||||
if [[ "$STAGE0_MINOR" != "$TAG_MINOR" ]]; then
|
||||
STAGE0_ERRORS+="LEAN_VERSION_MINOR: expected $TAG_MINOR, found $STAGE0_MINOR\n"
|
||||
fi
|
||||
|
||||
if [[ -n "$STAGE0_ERRORS" ]]; then
|
||||
echo "::error::Version mismatch between tag and stage0/src/CMakeLists.txt"
|
||||
echo ""
|
||||
echo "Tag ${{ steps.set-release.outputs.RELEASE_TAG }} expects version $TAG_MAJOR.$TAG_MINOR.$TAG_PATCH"
|
||||
echo "But stage0/src/CMakeLists.txt has mismatched values:"
|
||||
echo -e "$STAGE0_ERRORS"
|
||||
echo ""
|
||||
echo "The stage0 compiler stamps .olean headers with its baked-in version."
|
||||
echo "Run 'make update-stage0' to rebuild stage0 with the correct version, then re-tag."
|
||||
exit 1
|
||||
fi
|
||||
|
||||
echo "stage0 version validation passed: $STAGE0_MAJOR.$STAGE0_MINOR"
|
||||
|
||||
# 0: PRs without special label
|
||||
# 1: PRs with `merge-ci` label, merge queue checks, master commits
|
||||
# 2: nightlies
|
||||
@@ -275,8 +303,8 @@ jobs:
|
||||
// Always run on large if available, more reliable regarding timeouts
|
||||
"os": large ? "nscloud-ubuntu-22.04-amd64-16x32-with-cache" : "ubuntu-latest",
|
||||
"enabled": level >= 2,
|
||||
// do not fail nightlies on this for now
|
||||
"secondary": level <= 2,
|
||||
// do not fail releases/nightlies on this for now
|
||||
"secondary": true,
|
||||
"test": true,
|
||||
// turn off custom allocator & symbolic functions to make LSAN do its magic
|
||||
"CMAKE_PRESET": "sanitize",
|
||||
|
||||
@@ -11,7 +11,7 @@ IMPORTANT: Keep this documentation up-to-date when modifying the script's behavi
|
||||
What this script does:
|
||||
1. Validates preliminary Lean4 release infrastructure:
|
||||
- Checks that the release branch (releases/vX.Y.0) exists
|
||||
- Verifies CMake version settings are correct
|
||||
- Verifies CMake version settings are correct (both src/ and stage0/)
|
||||
- Confirms the release tag exists
|
||||
- Validates the release page exists on GitHub (created automatically by CI after tag push)
|
||||
- Checks the release notes page on lean-lang.org (updated while bumping the `reference-manual` repository)
|
||||
@@ -326,6 +326,42 @@ def check_cmake_version(repo_url, branch, version_major, version_minor, github_t
|
||||
print(f" ✅ CMake version settings are correct in {cmake_file_path}")
|
||||
return True
|
||||
|
||||
def check_stage0_version(repo_url, branch, version_major, version_minor, github_token):
|
||||
"""Verify that stage0/src/CMakeLists.txt has the same version as src/CMakeLists.txt.
|
||||
|
||||
The stage0 pre-built binaries stamp .olean headers with their baked-in version.
|
||||
If stage0 has a different version (e.g. from a 'begin development cycle' bump),
|
||||
the release tarball will contain .olean files with the wrong version.
|
||||
"""
|
||||
stage0_cmake = "stage0/src/CMakeLists.txt"
|
||||
content = get_branch_content(repo_url, branch, stage0_cmake, github_token)
|
||||
if content is None:
|
||||
print(f" ❌ Could not retrieve {stage0_cmake} from {branch}")
|
||||
return False
|
||||
|
||||
errors = []
|
||||
for line in content.splitlines():
|
||||
stripped = line.strip()
|
||||
if stripped.startswith("set(LEAN_VERSION_MAJOR "):
|
||||
actual = stripped.split()[-1].rstrip(")")
|
||||
if actual != str(version_major):
|
||||
errors.append(f"LEAN_VERSION_MAJOR: expected {version_major}, found {actual}")
|
||||
elif stripped.startswith("set(LEAN_VERSION_MINOR "):
|
||||
actual = stripped.split()[-1].rstrip(")")
|
||||
if actual != str(version_minor):
|
||||
errors.append(f"LEAN_VERSION_MINOR: expected {version_minor}, found {actual}")
|
||||
|
||||
if errors:
|
||||
print(f" ❌ stage0 version mismatch in {stage0_cmake}:")
|
||||
for error in errors:
|
||||
print(f" {error}")
|
||||
print(f" The stage0 compiler stamps .olean headers with its baked-in version.")
|
||||
print(f" Run `make update-stage0` to rebuild stage0 with the correct version.")
|
||||
return False
|
||||
|
||||
print(f" ✅ stage0 version matches in {stage0_cmake}")
|
||||
return True
|
||||
|
||||
def extract_org_repo_from_url(repo_url):
|
||||
"""Extract the 'org/repo' part from a GitHub URL."""
|
||||
if repo_url.startswith("https://github.com/"):
|
||||
@@ -441,7 +477,10 @@ def get_pr_ci_status(repo_url, pr_number, github_token):
|
||||
conclusions = [run['conclusion'] for run in check_runs if run.get('status') == 'completed']
|
||||
in_progress = [run for run in check_runs if run.get('status') in ['queued', 'in_progress']]
|
||||
|
||||
failed = sum(1 for c in conclusions if c in ['failure', 'timed_out', 'action_required'])
|
||||
if in_progress:
|
||||
if failed > 0:
|
||||
return "failure", f"{failed} check(s) failing, {len(in_progress)} still in progress"
|
||||
return "pending", f"{len(in_progress)} check(s) in progress"
|
||||
|
||||
if not conclusions:
|
||||
@@ -450,7 +489,6 @@ def get_pr_ci_status(repo_url, pr_number, github_token):
|
||||
if all(c == 'success' for c in conclusions):
|
||||
return "success", f"All {len(conclusions)} checks passed"
|
||||
|
||||
failed = sum(1 for c in conclusions if c in ['failure', 'timed_out', 'action_required'])
|
||||
if failed > 0:
|
||||
return "failure", f"{failed} check(s) failed"
|
||||
|
||||
@@ -680,6 +718,9 @@ def main():
|
||||
# Check CMake version settings
|
||||
if not check_cmake_version(lean_repo_url, branch_name, version_major, version_minor, github_token):
|
||||
lean4_success = False
|
||||
# Check that stage0 version matches (stage0 stamps .olean headers with its version)
|
||||
if not check_stage0_version(lean_repo_url, branch_name, version_major, version_minor, github_token):
|
||||
lean4_success = False
|
||||
|
||||
# Check for tag and release page
|
||||
if not tag_exists(lean_repo_url, toolchain, github_token):
|
||||
@@ -965,14 +1006,15 @@ def main():
|
||||
# Find the actual minor version in CMakeLists.txt
|
||||
for line in cmake_lines:
|
||||
if line.strip().startswith("set(LEAN_VERSION_MINOR "):
|
||||
actual_minor = int(line.split()[-1].rstrip(")"))
|
||||
m = re.search(r'set\(LEAN_VERSION_MINOR\s+(\d+)', line)
|
||||
actual_minor = int(m.group(1)) if m else 0
|
||||
version_minor_correct = actual_minor >= next_minor
|
||||
break
|
||||
else:
|
||||
version_minor_correct = False
|
||||
|
||||
is_release_correct = any(
|
||||
l.strip().startswith("set(LEAN_VERSION_IS_RELEASE 0)")
|
||||
re.match(r'set\(LEAN_VERSION_IS_RELEASE\s+0[\s)]', l.strip())
|
||||
for l in cmake_lines
|
||||
)
|
||||
|
||||
|
||||
@@ -14,13 +14,6 @@ repositories:
|
||||
bump-branch: true
|
||||
dependencies: []
|
||||
|
||||
- name: lean4checker
|
||||
url: https://github.com/leanprover/lean4checker
|
||||
toolchain-tag: true
|
||||
stable-branch: true
|
||||
branch: master
|
||||
dependencies: []
|
||||
|
||||
- name: quote4
|
||||
url: https://github.com/leanprover-community/quote4
|
||||
toolchain-tag: true
|
||||
|
||||
@@ -479,6 +479,25 @@ def execute_release_steps(repo, version, config):
|
||||
print(blue("Updating lakefile.toml..."))
|
||||
run_command(f'perl -pi -e \'s/"v4\\.[0-9]+(\\.[0-9]+)?(-rc[0-9]+)?"/"' + version + '"/g\' lakefile.*', cwd=repo_path)
|
||||
run_command("lake update", cwd=repo_path, stream_output=True)
|
||||
elif repo_name == "verso":
|
||||
# verso has nested Lake projects in test-projects/ that each have their own
|
||||
# lake-manifest.json with a subverso pin. After updating the root manifest via
|
||||
# `lake update`, sync the de-modulized subverso rev into all sub-manifests.
|
||||
# The sub-projects use an old toolchain (v4.21.0) that doesn't support module/prelude
|
||||
# syntax, so they need the de-modulized version (tagged no-modules/<root-rev>).
|
||||
# The "SubVerso version consistency" CI check accepts either the root or de-modulized rev.
|
||||
run_command("lake update", cwd=repo_path, stream_output=True)
|
||||
print(blue("Syncing de-modulized subverso rev to test-project sub-manifests..."))
|
||||
sync_script = (
|
||||
'ROOT_REV=$(jq -r \'.packages[] | select(.name == "subverso") | .rev\' lake-manifest.json); '
|
||||
'SUBVERSO_URL=$(jq -r \'.packages[] | select(.name == "subverso") | .url\' lake-manifest.json); '
|
||||
'DEMOD_REV=$(git ls-remote "$SUBVERSO_URL" "refs/tags/no-modules/$ROOT_REV" | awk \'{print $1}\'); '
|
||||
'find test-projects -name lake-manifest.json -print0 | while IFS= read -r -d \'\' f; do '
|
||||
'jq --arg rev "$DEMOD_REV" \'.packages |= map(if .name == "subverso" then .rev = $rev else . end)\' "$f" > /tmp/lm_tmp.json && mv /tmp/lm_tmp.json "$f"; '
|
||||
'done'
|
||||
)
|
||||
run_command(sync_script, cwd=repo_path)
|
||||
print(green("Synced de-modulized subverso rev to all test-project sub-manifests"))
|
||||
elif dependencies:
|
||||
run_command(f'perl -pi -e \'s/"v4\\.[0-9]+(\\.[0-9]+)?(-rc[0-9]+)?"/"' + version + '"/g\' lakefile.*', cwd=repo_path)
|
||||
run_command("lake update", cwd=repo_path, stream_output=True)
|
||||
|
||||
@@ -10,9 +10,9 @@ endif()
|
||||
include(ExternalProject)
|
||||
project(LEAN CXX C)
|
||||
set(LEAN_VERSION_MAJOR 4)
|
||||
set(LEAN_VERSION_MINOR 30)
|
||||
set(LEAN_VERSION_MINOR 29)
|
||||
set(LEAN_VERSION_PATCH 0)
|
||||
set(LEAN_VERSION_IS_RELEASE 0) # This number is 1 in the release revision, and 0 otherwise.
|
||||
set(LEAN_VERSION_IS_RELEASE 1) # This number is 1 in the release revision, and 0 otherwise.
|
||||
set(LEAN_SPECIAL_VERSION_DESC "" CACHE STRING "Additional version description like 'nightly-2018-03-11'")
|
||||
set(LEAN_VERSION_STRING "${LEAN_VERSION_MAJOR}.${LEAN_VERSION_MINOR}.${LEAN_VERSION_PATCH}")
|
||||
if(LEAN_SPECIAL_VERSION_DESC)
|
||||
|
||||
@@ -69,9 +69,11 @@ theorem em (p : Prop) : p ∨ ¬p :=
|
||||
theorem exists_true_of_nonempty {α : Sort u} : Nonempty α → ∃ _ : α, True
|
||||
| ⟨x⟩ => ⟨x, trivial⟩
|
||||
|
||||
@[implicit_reducible]
|
||||
noncomputable def inhabited_of_nonempty {α : Sort u} (h : Nonempty α) : Inhabited α :=
|
||||
⟨choice h⟩
|
||||
|
||||
@[implicit_reducible]
|
||||
noncomputable def inhabited_of_exists {α : Sort u} {p : α → Prop} (h : ∃ x, p x) : Inhabited α :=
|
||||
inhabited_of_nonempty (Exists.elim h (fun w _ => ⟨w⟩))
|
||||
|
||||
@@ -81,6 +83,7 @@ noncomputable scoped instance (priority := low) propDecidable (a : Prop) : Decid
|
||||
| Or.inl h => ⟨isTrue h⟩
|
||||
| Or.inr h => ⟨isFalse h⟩
|
||||
|
||||
@[implicit_reducible]
|
||||
noncomputable def decidableInhabited (a : Prop) : Inhabited (Decidable a) where
|
||||
default := inferInstance
|
||||
|
||||
|
||||
@@ -49,6 +49,7 @@ instance : Monad Id where
|
||||
/--
|
||||
The identity monad has a `bind` operator.
|
||||
-/
|
||||
@[implicit_reducible]
|
||||
def hasBind : Bind Id :=
|
||||
inferInstance
|
||||
|
||||
@@ -58,7 +59,7 @@ Runs a computation in the identity monad.
|
||||
This function is the identity function. Because its parameter has type `Id α`, it causes
|
||||
`do`-notation in its arguments to use the `Monad Id` instance.
|
||||
-/
|
||||
@[always_inline, inline, expose]
|
||||
@[always_inline, inline, expose, implicit_reducible]
|
||||
protected def run (x : Id α) : α := x
|
||||
|
||||
instance [OfNat α n] : OfNat (Id α) n :=
|
||||
|
||||
@@ -72,11 +72,11 @@ public instance [Monad m] [LawfulMonad m] [MonadAttach m] [LawfulMonadAttach m]
|
||||
|
||||
public instance [Monad m] [MonadAttach m] [LawfulMonad m] [WeaklyLawfulMonadAttach m] :
|
||||
WeaklyLawfulMonadAttach (StateRefT' ω σ m) :=
|
||||
inferInstanceAs (WeaklyLawfulMonadAttach (ReaderT _ _))
|
||||
inferInstanceAs (WeaklyLawfulMonadAttach (ReaderT (ST.Ref ω σ) m))
|
||||
|
||||
public instance [Monad m] [MonadAttach m] [LawfulMonad m] [LawfulMonadAttach m] :
|
||||
LawfulMonadAttach (StateRefT' ω σ m) :=
|
||||
inferInstanceAs (LawfulMonadAttach (ReaderT _ _))
|
||||
inferInstanceAs (LawfulMonadAttach (ReaderT (ST.Ref ω σ) m))
|
||||
|
||||
section
|
||||
|
||||
|
||||
@@ -103,11 +103,11 @@ namespace StateRefT'
|
||||
instance {ω σ : Type} {m : Type → Type} [Monad m] : LawfulMonadLift m (StateRefT' ω σ m) where
|
||||
monadLift_pure _ := by
|
||||
simp only [MonadLift.monadLift, pure]
|
||||
unfold StateRefT'.lift ReaderT.pure
|
||||
unfold StateRefT'.lift instMonad._aux_5 ReaderT.pure
|
||||
simp only
|
||||
monadLift_bind _ _ := by
|
||||
simp only [MonadLift.monadLift, bind]
|
||||
unfold StateRefT'.lift ReaderT.bind
|
||||
unfold StateRefT'.lift instMonad._aux_13 ReaderT.bind
|
||||
simp only
|
||||
|
||||
end StateRefT'
|
||||
|
||||
@@ -629,6 +629,7 @@ export Bool (cond_eq_if cond_eq_ite xor and or not)
|
||||
This should not be turned on globally as an instance because it degrades performance in Mathlib,
|
||||
but may be used locally.
|
||||
-/
|
||||
@[implicit_reducible]
|
||||
def boolPredToPred : Coe (α → Bool) (α → Prop) where
|
||||
coe r := fun a => Eq (r a) true
|
||||
|
||||
|
||||
@@ -62,7 +62,7 @@ instance ltTrichotomous : Std.Trichotomous (· < · : Char → Char → Prop) wh
|
||||
trichotomous _ _ h₁ h₂ := Char.le_antisymm (by simpa using h₂) (by simpa using h₁)
|
||||
|
||||
@[deprecated ltTrichotomous (since := "2025-10-27")]
|
||||
def notLTAntisymm : Std.Antisymm (¬ · < · : Char → Char → Prop) where
|
||||
theorem notLTAntisymm : Std.Antisymm (¬ · < · : Char → Char → Prop) where
|
||||
antisymm := Char.ltTrichotomous.trichotomous
|
||||
|
||||
instance ltAsymm : Std.Asymm (· < · : Char → Char → Prop) where
|
||||
@@ -73,7 +73,7 @@ instance leTotal : Std.Total (· ≤ · : Char → Char → Prop) where
|
||||
|
||||
-- This instance is useful while setting up instances for `String`.
|
||||
@[deprecated ltAsymm (since := "2025-08-01")]
|
||||
def notLTTotal : Std.Total (¬ · < · : Char → Char → Prop) where
|
||||
theorem notLTTotal : Std.Total (¬ · < · : Char → Char → Prop) where
|
||||
total := fun x y => by simpa using Char.le_total y x
|
||||
|
||||
@[simp] theorem ofNat_toNat (c : Char) : Char.ofNat c.toNat = c := by
|
||||
|
||||
@@ -168,6 +168,13 @@ instance Map.instIterator {α β γ : Type w} {m : Type w → Type w'} {n : Type
|
||||
Iterator (Map α m n lift f) n γ :=
|
||||
inferInstanceAs <| Iterator (FilterMap α m n lift _) n γ
|
||||
|
||||
theorem Map.instIterator_eq_filterMapInstIterator {α β γ : Type w} {m : Type w → Type w'}
|
||||
{n : Type w → Type w''} [Monad n]
|
||||
[Iterator α m β] {lift : ⦃α : Type w⦄ → m α → n α} {f : β → PostconditionT n γ} :
|
||||
Map.instIterator (α := α) (β := β) (γ := γ) (m := m) (n := n) (lift := lift) (f := f) =
|
||||
FilterMap.instIterator :=
|
||||
rfl
|
||||
|
||||
private def FilterMap.instFinitenessRelation {α β γ : Type w} {m : Type w → Type w'}
|
||||
{n : Type w → Type w''} [Monad n] [Iterator α m β] {lift : ⦃α : Type w⦄ → m α → n α}
|
||||
{f : β → PostconditionT n (Option γ)} [Finite α m] :
|
||||
|
||||
@@ -362,8 +362,7 @@ def Flatten.instProductivenessRelation [Monad m] [Iterator α m (IterM (α := α
|
||||
case innerDone =>
|
||||
apply Flatten.productiveRel_of_right₂
|
||||
|
||||
@[no_expose]
|
||||
public def Flatten.instProductive [Monad m] [Iterator α m (IterM (α := α₂) m β)] [Iterator α₂ m β]
|
||||
public theorem Flatten.instProductive [Monad m] [Iterator α m (IterM (α := α₂) m β)] [Iterator α₂ m β]
|
||||
[Finite α m] [Productive α₂ m] : Productive (Flatten α α₂ β m) m :=
|
||||
.of_productivenessRelation instProductivenessRelation
|
||||
|
||||
|
||||
@@ -35,7 +35,7 @@ A `ForIn'` instance for iterators. Its generic membership relation is not easy t
|
||||
so this is not marked as `instance`. This way, more convenient instances can be built on top of it
|
||||
or future library improvements will make it more comfortable.
|
||||
-/
|
||||
@[always_inline, inline]
|
||||
@[always_inline, inline, expose, implicit_reducible]
|
||||
def Iter.instForIn' {α : Type w} {β : Type w} {n : Type x → Type x'} [Monad n]
|
||||
[Iterator α Id β] [IteratorLoop α Id n] :
|
||||
ForIn' n (Iter (α := α) β) β ⟨fun it out => it.IsPlausibleIndirectOutput out⟩ where
|
||||
@@ -53,7 +53,7 @@ instance (α : Type w) (β : Type w) (n : Type x → Type x') [Monad n]
|
||||
/--
|
||||
An implementation of `for h : ... in ... do ...` notation for partial iterators.
|
||||
-/
|
||||
@[always_inline, inline]
|
||||
@[always_inline, inline, expose, implicit_reducible]
|
||||
def Iter.Partial.instForIn' {α : Type w} {β : Type w} {n : Type x → Type x'} [Monad n]
|
||||
[Iterator α Id β] [IteratorLoop α Id n] :
|
||||
ForIn' n (Iter.Partial (α := α) β) β ⟨fun it out => it.it.IsPlausibleIndirectOutput out⟩ where
|
||||
@@ -71,7 +71,7 @@ instance (α : Type w) (β : Type w) (n : Type x → Type x') [Monad n]
|
||||
A `ForIn'` instance for iterators that is guaranteed to terminate after finitely many steps.
|
||||
It is not marked as an instance because the membership predicate is difficult to work with.
|
||||
-/
|
||||
@[always_inline, inline]
|
||||
@[always_inline, inline, expose, implicit_reducible]
|
||||
def Iter.Total.instForIn' {α : Type w} {β : Type w} {n : Type x → Type x'} [Monad n]
|
||||
[Iterator α Id β] [IteratorLoop α Id n] [Finite α Id] :
|
||||
ForIn' n (Iter.Total (α := α) β) β ⟨fun it out => it.it.IsPlausibleIndirectOutput out⟩ where
|
||||
|
||||
@@ -159,7 +159,7 @@ This is the default implementation of the `IteratorLoop` class.
|
||||
It simply iterates through the iterator using `IterM.step`. For certain iterators, more efficient
|
||||
implementations are possible and should be used instead.
|
||||
-/
|
||||
@[always_inline, inline, expose]
|
||||
@[always_inline, inline, expose, implicit_reducible]
|
||||
def IteratorLoop.defaultImplementation {α : Type w} {m : Type w → Type w'} {n : Type x → Type x'}
|
||||
[Monad n] [Iterator α m β] :
|
||||
IteratorLoop α m n where
|
||||
@@ -211,7 +211,7 @@ theorem IteratorLoop.wellFounded_of_productive {α β : Type w} {m : Type w →
|
||||
/--
|
||||
This `ForIn'`-style loop construct traverses a finite iterator using an `IteratorLoop` instance.
|
||||
-/
|
||||
@[always_inline, inline]
|
||||
@[always_inline, inline, expose, implicit_reducible]
|
||||
def IteratorLoop.finiteForIn' {m : Type w → Type w'} {n : Type x → Type x'}
|
||||
{α : Type w} {β : Type w} [Iterator α m β] [IteratorLoop α m n] [Monad n]
|
||||
(lift : ∀ γ δ, (γ → n δ) → m γ → n δ) :
|
||||
@@ -224,7 +224,7 @@ A `ForIn'` instance for iterators. Its generic membership relation is not easy t
|
||||
so this is not marked as `instance`. This way, more convenient instances can be built on top of it
|
||||
or future library improvements will make it more comfortable.
|
||||
-/
|
||||
@[always_inline, inline]
|
||||
@[always_inline, inline, expose, implicit_reducible]
|
||||
def IterM.instForIn' {m : Type w → Type w'} {n : Type w → Type w''}
|
||||
{α : Type w} {β : Type w} [Iterator α m β] [IteratorLoop α m n] [Monad n]
|
||||
[MonadLiftT m n] :
|
||||
@@ -239,7 +239,7 @@ instance IterM.instForInOfIteratorLoop {m : Type w → Type w'} {n : Type w →
|
||||
instForInOfForIn'
|
||||
|
||||
/-- Internal implementation detail of the iterator library. -/
|
||||
@[always_inline, inline]
|
||||
@[always_inline, inline, expose, implicit_reducible]
|
||||
def IterM.Partial.instForIn' {m : Type w → Type w'} {n : Type w → Type w''}
|
||||
{α : Type w} {β : Type w} [Iterator α m β] [IteratorLoop α m n] [MonadLiftT m n] [Monad n] :
|
||||
ForIn' n (IterM.Partial (α := α) m β) β ⟨fun it out => it.it.IsPlausibleIndirectOutput out⟩ where
|
||||
@@ -247,7 +247,7 @@ def IterM.Partial.instForIn' {m : Type w → Type w'} {n : Type w → Type w''}
|
||||
haveI := @IterM.instForIn'; forIn' it.it init f
|
||||
|
||||
/-- Internal implementation detail of the iterator library. -/
|
||||
@[always_inline, inline]
|
||||
@[always_inline, inline, expose, implicit_reducible]
|
||||
def IterM.Total.instForIn' {m : Type w → Type w'} {n : Type w → Type w''}
|
||||
{α : Type w} {β : Type w} [Iterator α m β] [IteratorLoop α m n] [MonadLiftT m n] [Monad n]
|
||||
[Finite α m] :
|
||||
|
||||
@@ -70,7 +70,7 @@ theorem LawfulMonadLiftFunction.lift_seqRight [LawfulMonad m] [LawfulMonad n]
|
||||
abbrev idToMonad [Monad m] ⦃α : Type u⦄ (x : Id α) : m α :=
|
||||
pure x.run
|
||||
|
||||
def LawfulMonadLiftFunction.idToMonad [Monad m] [LawfulMonad m] :
|
||||
theorem LawfulMonadLiftFunction.idToMonad [LawfulMonad m] :
|
||||
LawfulMonadLiftFunction (m := Id) (n := m) idToMonad where
|
||||
lift_pure := by simp [Internal.idToMonad]
|
||||
lift_bind := by simp [Internal.idToMonad]
|
||||
@@ -95,7 +95,7 @@ instance [LawfulMonadLiftBindFunction (n := n) (fun _ _ f x => lift x >>= f)] [L
|
||||
simpa using LawfulMonadLiftBindFunction.liftBind_bind (n := n)
|
||||
(liftBind := fun _ _ f x => lift x >>= f) (β := β) (γ := γ) (δ := γ) pure x g
|
||||
|
||||
def LawfulMonadLiftBindFunction.id [Monad m] [LawfulMonad m] :
|
||||
theorem LawfulMonadLiftBindFunction.id [LawfulMonad m] :
|
||||
LawfulMonadLiftBindFunction (m := Id) (n := m) (fun _ _ f x => f x.run) where
|
||||
liftBind_pure := by simp
|
||||
liftBind_bind := by simp
|
||||
|
||||
@@ -702,18 +702,16 @@ theorem IterM.toList_map {α β β' : Type w} {m : Type w → Type w'} [Monad m]
|
||||
(it : IterM (α := α) m β) :
|
||||
(it.map f).toList = (fun x => x.map f) <$> it.toList := by
|
||||
rw [← List.filterMap_eq_map, ← toList_filterMap]
|
||||
let t := type_of% (it.map f)
|
||||
let t' := type_of% (it.filterMap (some ∘ f))
|
||||
simp only [map, mapWithPostcondition, InternalCombinators.map, filterMap,
|
||||
filterMapWithPostcondition, InternalCombinators.filterMap]
|
||||
unfold Map
|
||||
congr
|
||||
· simp [Map]
|
||||
· simp [Map.instIterator, inferInstanceAs]
|
||||
· simp
|
||||
· rw [Map.instIterator_eq_filterMapInstIterator]
|
||||
congr
|
||||
simp
|
||||
· simp only [map, mapWithPostcondition, InternalCombinators.map, Function.comp_apply, filterMap,
|
||||
filterMapWithPostcondition, InternalCombinators.filterMap]
|
||||
congr
|
||||
· simp [Map]
|
||||
· simp
|
||||
· simp
|
||||
· simp
|
||||
|
||||
@[simp]
|
||||
theorem IterM.toList_filter {α : Type w} {m : Type w → Type w'} [Monad m] [LawfulMonad m]
|
||||
|
||||
@@ -32,7 +32,7 @@ theorem Iter.forIn'_eq {α β : Type w} [Iterator α Id β] [Finite α Id]
|
||||
IterM.DefaultConsumers.forIn' (n := m) (fun _ _ f x => f x.run) γ (fun _ _ _ => True)
|
||||
it.toIterM init _ (fun _ => id)
|
||||
(fun out h acc => return ⟨← f out (Iter.isPlausibleIndirectOutput_iff_isPlausibleIndirectOutput_toIterM.mpr h) acc, trivial⟩) := by
|
||||
simp +instances only [instForIn', ForIn'.forIn', IteratorLoop.finiteForIn']
|
||||
simp +instances only [ForIn'.forIn']
|
||||
have : ∀ a b c, f a b c = (Subtype.val <$> (⟨·, trivial⟩) <$> f a b c) := by simp
|
||||
simp +singlePass only [this]
|
||||
rw [hl.lawful (fun _ _ f x => f x.run) (wf := IteratorLoop.wellFounded_of_finite)]
|
||||
@@ -81,7 +81,7 @@ theorem Iter.forIn'_eq_forIn'_toIterM {α β : Type w} [Iterator α Id β]
|
||||
letI : ForIn' m (IterM (α := α) Id β) β _ := IterM.instForIn'
|
||||
ForIn'.forIn' it.toIterM init
|
||||
(fun out h acc => f out (isPlausibleIndirectOutput_iff_isPlausibleIndirectOutput_toIterM.mpr h) acc) := by
|
||||
simp +instances [ForIn'.forIn', Iter.instForIn', IterM.instForIn', monadLift]
|
||||
simp +instances [ForIn'.forIn', monadLift]
|
||||
|
||||
theorem Iter.forIn_eq_forIn_toIterM {α β : Type w} [Iterator α Id β]
|
||||
[Finite α Id] {m : Type w → Type w''} [Monad m] [LawfulMonad m]
|
||||
@@ -395,7 +395,7 @@ theorem Iter.fold_eq_fold_toIterM {α β : Type w} {γ : Type w} [Iterator α Id
|
||||
[Finite α Id] [IteratorLoop α Id Id]
|
||||
{f : γ → β → γ} {init : γ} {it : Iter (α := α) β} :
|
||||
it.fold (init := init) f = (it.toIterM.fold (init := init) f).run := by
|
||||
rw [fold_eq_foldM, foldM_eq_foldM_toIterM, IterM.fold_eq_foldM]; rfl
|
||||
rw [fold_eq_foldM, foldM_eq_foldM_toIterM, IterM.fold_eq_foldM]
|
||||
|
||||
@[simp]
|
||||
theorem Iter.forIn_pure_yield_eq_fold {α β : Type w} {γ : Type x} [Iterator α Id β]
|
||||
|
||||
@@ -109,7 +109,7 @@ theorem IterM.forIn'_eq {α β : Type w} {m : Type w → Type w'} [Iterator α m
|
||||
letI : ForIn' n (IterM (α := α) m β) β _ := IterM.instForIn'
|
||||
ForIn'.forIn' (α := β) (m := n) it init f = IterM.DefaultConsumers.forIn' (n := n)
|
||||
(fun _ _ f x => monadLift x >>= f) γ (fun _ _ _ => True) it init _ (fun _ => id) (return ⟨← f · · ·, trivial⟩) := by
|
||||
simp +instances only [instForIn', ForIn'.forIn', IteratorLoop.finiteForIn']
|
||||
simp +instances only [ForIn'.forIn']
|
||||
have : f = (Subtype.val <$> (⟨·, trivial⟩) <$> f · · ·) := by simp
|
||||
rw [this, hl.lawful (fun _ _ f x => monadLift x >>= f) (wf := IteratorLoop.wellFounded_of_finite)]
|
||||
simp +instances [IteratorLoop.defaultImplementation]
|
||||
|
||||
@@ -32,14 +32,14 @@ def ToIterator.iter [ToIterator γ Id α β] (x : γ) : Iter (α := α) β :=
|
||||
ToIterator.iterM x |>.toIter
|
||||
|
||||
/-- Creates a monadic `ToIterator` instance. -/
|
||||
@[always_inline, inline, expose, instance_reducible]
|
||||
@[always_inline, inline, expose, implicit_reducible]
|
||||
def ToIterator.ofM (α : Type w)
|
||||
(iterM : γ → IterM (α := α) m β) :
|
||||
ToIterator γ m α β where
|
||||
iterMInternal x := iterM x
|
||||
|
||||
/-- Creates a pure `ToIterator` instance. -/
|
||||
@[always_inline, inline, expose, instance_reducible]
|
||||
@[always_inline, inline, expose, implicit_reducible]
|
||||
def ToIterator.of (α : Type w)
|
||||
(iter : γ → Iter (α := α) β) :
|
||||
ToIterator γ Id α β where
|
||||
|
||||
@@ -236,7 +236,6 @@ theorem getElem?_eq_some_iff {l : List α} : l[i]? = some a ↔ ∃ h : i < l.le
|
||||
· match i, h with
|
||||
| i + 1, h => simp [getElem?_eq_some_iff, Nat.succ_lt_succ_iff]
|
||||
|
||||
@[grind →]
|
||||
theorem getElem_of_getElem? {l : List α} : l[i]? = some a → ∃ h : i < l.length, l[i] = a :=
|
||||
getElem?_eq_some_iff.mp
|
||||
|
||||
|
||||
@@ -481,13 +481,13 @@ protected theorem maxIdxOn_nil_eq_iff_false [LE β] [DecidableLE β] {f : α →
|
||||
@[simp]
|
||||
protected theorem maxIdxOn_singleton [LE β] [DecidableLE β] {x : α} {f : α → β} :
|
||||
[x].maxIdxOn f (of_decide_eq_false rfl) = 0 :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.minIdxOn_singleton
|
||||
|
||||
@[simp]
|
||||
protected theorem maxIdxOn_lt_length [LE β] [DecidableLE β] {f : α → β} {xs : List α}
|
||||
(h : xs ≠ []) : xs.maxIdxOn f h < xs.length :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.minIdxOn_lt_length h
|
||||
|
||||
protected theorem maxIdxOn_le_of_apply_getElem_le_apply_maxOn [LE β] [DecidableLE β] [IsLinearPreorder β]
|
||||
@@ -495,7 +495,7 @@ protected theorem maxIdxOn_le_of_apply_getElem_le_apply_maxOn [LE β] [Decidable
|
||||
{k : Nat} (hi : k < xs.length) (hle : f (xs.maxOn f h) ≤ f xs[k]) :
|
||||
xs.maxIdxOn f h ≤ k := by
|
||||
simp only [List.maxIdxOn_eq_minIdxOn, List.maxOn_eq_minOn] at hle ⊢
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
exact List.minIdxOn_le_of_apply_getElem_le_apply_minOn h hi (by simpa [LE.le_opposite_iff] using hle)
|
||||
|
||||
protected theorem apply_maxOn_lt_apply_getElem_of_lt_maxIdxOn [LE β] [DecidableLE β] [LT β] [IsLinearPreorder β]
|
||||
@@ -513,7 +513,7 @@ protected theorem getElem_maxIdxOn [LE β] [DecidableLE β] [IsLinearPreorder β
|
||||
{f : α → β} {xs : List α} (h : xs ≠ []) :
|
||||
xs[xs.maxIdxOn f h] = xs.maxOn f h := by
|
||||
simp only [List.maxIdxOn_eq_minIdxOn, List.maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
exact List.getElem_minIdxOn h
|
||||
|
||||
protected theorem le_maxIdxOn_of_apply_getElem_lt_apply_getElem [LE β] [DecidableLE β] [LT β]
|
||||
@@ -562,14 +562,14 @@ protected theorem maxIdxOn_cons
|
||||
else if f (xs.maxOn f h) ≤ f x then 0
|
||||
else (xs.maxIdxOn f h) + 1 := by
|
||||
simp only [List.maxIdxOn_eq_minIdxOn, List.maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa [LE.le_opposite_iff] using List.minIdxOn_cons (f := f)
|
||||
|
||||
protected theorem maxIdxOn_eq_zero_iff [LE β] [DecidableLE β] [IsLinearPreorder β]
|
||||
{xs : List α} {f : α → β} (h : xs ≠ []) :
|
||||
xs.maxIdxOn f h = 0 ↔ ∀ x ∈ xs, f x ≤ f (xs.head h) := by
|
||||
simp only [List.maxIdxOn_eq_minIdxOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa [LE.le_opposite_iff] using List.minIdxOn_eq_zero_iff h (f := f)
|
||||
|
||||
protected theorem maxIdxOn_append [LE β] [DecidableLE β] [IsLinearPreorder β]
|
||||
@@ -580,26 +580,26 @@ protected theorem maxIdxOn_append [LE β] [DecidableLE β] [IsLinearPreorder β]
|
||||
else
|
||||
xs.length + ys.maxIdxOn f hys := by
|
||||
simp only [List.maxIdxOn_eq_minIdxOn, List.maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa [LE.le_opposite_iff] using List.minIdxOn_append hxs hys (f := f)
|
||||
|
||||
protected theorem left_le_maxIdxOn_append [LE β] [DecidableLE β] [IsLinearPreorder β]
|
||||
{xs ys : List α} {f : α → β} (h : xs ≠ []) :
|
||||
xs.maxIdxOn f h ≤ (xs ++ ys).maxIdxOn f (by simp [h]) :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.left_le_minIdxOn_append h
|
||||
|
||||
protected theorem maxIdxOn_take_le [LE β] [DecidableLE β] [IsLinearPreorder β]
|
||||
{xs : List α} {f : α → β} {i : Nat} (h : xs.take i ≠ []) :
|
||||
(xs.take i).maxIdxOn f h ≤ xs.maxIdxOn f (List.ne_nil_of_take_ne_nil h) :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.minIdxOn_take_le h
|
||||
|
||||
@[simp]
|
||||
protected theorem maxIdxOn_replicate [LE β] [DecidableLE β] [Refl (α := β) (· ≤ ·)]
|
||||
{n : Nat} {a : α} {f : α → β} (h : replicate n a ≠ []) :
|
||||
(replicate n a).maxIdxOn f h = 0 :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.minIdxOn_replicate h
|
||||
|
||||
@[simp]
|
||||
|
||||
@@ -297,13 +297,13 @@ protected theorem maxOn_cons
|
||||
(x :: xs).maxOn f (by exact of_decide_eq_false rfl) =
|
||||
if h : xs = [] then x else maxOn f x (xs.maxOn f h) := by
|
||||
simp only [maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
exact List.minOn_cons (f := f)
|
||||
|
||||
protected theorem maxOn_cons_cons [LE β] [DecidableLE β] {a b : α} {l : List α} {f : α → β} :
|
||||
(a :: b :: l).maxOn f (by simp) = (maxOn f a b :: l).maxOn f (by simp) := by
|
||||
simp only [List.maxOn_eq_minOn, maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
exact List.minOn_cons_cons
|
||||
|
||||
@[simp]
|
||||
@@ -334,51 +334,51 @@ protected theorem maxOn_id [Max α] [LE α] [DecidableLE α] [LawfulOrderLeftLea
|
||||
{xs : List α} (h : xs ≠ []) :
|
||||
xs.maxOn id h = xs.max h := by
|
||||
simp only [List.maxOn_eq_minOn]
|
||||
letI : LE α := (inferInstanceAs (LE α)).opposite
|
||||
letI : Min α := (inferInstanceAs (Max α)).oppositeMin
|
||||
letI : LE α := (inferInstance : LE α).opposite
|
||||
letI : Min α := (inferInstance : Max α).oppositeMin
|
||||
simpa only [List.max_eq_min] using List.minOn_id h
|
||||
|
||||
@[simp]
|
||||
protected theorem maxOn_mem [LE β] [DecidableLE β] {xs : List α}
|
||||
{f : α → β} {h : xs ≠ []} : xs.maxOn f h ∈ xs :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.minOn_mem (f := f)
|
||||
|
||||
protected theorem le_apply_maxOn_of_mem [LE β] [DecidableLE β] [IsLinearPreorder β]
|
||||
{xs : List α} {f : α → β} {y : α} (hx : y ∈ xs) :
|
||||
f y ≤ f (xs.maxOn f (List.ne_nil_of_mem hx)) := by
|
||||
rw [List.maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa [LE.le_opposite_iff] using List.apply_minOn_le_of_mem (f := f) hx
|
||||
|
||||
protected theorem apply_maxOn_le_iff [LE β] [DecidableLE β] [IsLinearPreorder β] {xs : List α}
|
||||
{f : α → β} (h : xs ≠ []) {b : β} :
|
||||
f (xs.maxOn f h) ≤ b ↔ ∀ x ∈ xs, f x ≤ b := by
|
||||
rw [List.maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa [LE.le_opposite_iff] using List.le_apply_minOn_iff (f := f) h
|
||||
|
||||
protected theorem le_apply_maxOn_iff [LE β] [DecidableLE β] [IsLinearPreorder β] {xs : List α}
|
||||
{f : α → β} (h : xs ≠ []) {b : β} :
|
||||
b ≤ f (xs.maxOn f h) ↔ ∃ x ∈ xs, b ≤ f x := by
|
||||
rw [List.maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa [LE.le_opposite_iff] using List.apply_minOn_le_iff (f := f) h
|
||||
|
||||
protected theorem apply_maxOn_lt_iff
|
||||
[LE β] [DecidableLE β] [LT β] [IsLinearPreorder β] [LawfulOrderLT β]
|
||||
{xs : List α} {f : α → β} (h : xs ≠ []) {b : β} :
|
||||
f (xs.maxOn f h) < b ↔ ∀ x ∈ xs, f x < b := by
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LT β := (inferInstanceAs (LT β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
letI : LT β := (inferInstance : LT β).opposite
|
||||
simpa [LT.lt_opposite_iff] using List.lt_apply_minOn_iff (f := f) h
|
||||
|
||||
protected theorem lt_apply_maxOn_iff
|
||||
[LE β] [DecidableLE β] [LT β] [IsLinearPreorder β] [LawfulOrderLT β]
|
||||
{xs : List α} {f : α → β} (h : xs ≠ []) {b : β} :
|
||||
b < f (xs.maxOn f h) ↔ ∃ x ∈ xs, b < f x := by
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LT β := (inferInstanceAs (LT β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
letI : LT β := (inferInstance : LT β).opposite
|
||||
simpa [LT.lt_opposite_iff] using List.apply_minOn_lt_iff (f := f) h
|
||||
|
||||
protected theorem apply_maxOn_le_apply_maxOn_of_subset [LE β] [DecidableLE β]
|
||||
@@ -386,14 +386,14 @@ protected theorem apply_maxOn_le_apply_maxOn_of_subset [LE β] [DecidableLE β]
|
||||
haveI : xs ≠ [] := by intro h; rw [h] at hxs; simp_all [subset_nil]
|
||||
f (ys.maxOn f hys) ≤ f (xs.maxOn f this) := by
|
||||
rw [List.maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa [LE.le_opposite_iff] using List.apply_minOn_le_apply_minOn_of_subset (f := f) hxs hys
|
||||
|
||||
protected theorem apply_maxOn_take_le [LE β] [DecidableLE β] [IsLinearPreorder β]
|
||||
{xs : List α} {f : α → β} {i : Nat} (h : xs.take i ≠ []) :
|
||||
f ((xs.take i).maxOn f h) ≤ f (xs.maxOn f (List.ne_nil_of_take_ne_nil h)) := by
|
||||
rw [List.maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa [LE.le_opposite_iff] using List.le_apply_minOn_take (f := f) h
|
||||
|
||||
protected theorem le_apply_maxOn_append_left [LE β] [DecidableLE β] [IsLinearPreorder β]
|
||||
@@ -401,7 +401,7 @@ protected theorem le_apply_maxOn_append_left [LE β] [DecidableLE β] [IsLinearP
|
||||
f (xs.maxOn f h) ≤
|
||||
f ((xs ++ ys).maxOn f (append_ne_nil_of_left_ne_nil h ys)) := by
|
||||
rw [List.maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa [LE.le_opposite_iff] using List.apply_minOn_append_le_left (f := f) h
|
||||
|
||||
protected theorem le_apply_maxOn_append_right [LE β] [DecidableLE β] [IsLinearPreorder β]
|
||||
@@ -409,7 +409,7 @@ protected theorem le_apply_maxOn_append_right [LE β] [DecidableLE β] [IsLinear
|
||||
f (ys.maxOn f h) ≤
|
||||
f ((xs ++ ys).maxOn f (append_ne_nil_of_right_ne_nil xs h)) := by
|
||||
rw [List.maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa [LE.le_opposite_iff] using List.apply_minOn_append_le_right (f := f) h
|
||||
|
||||
@[simp]
|
||||
@@ -417,21 +417,21 @@ protected theorem maxOn_append [LE β] [DecidableLE β] [IsLinearPreorder β] {x
|
||||
{f : α → β} (hxs : xs ≠ []) (hys : ys ≠ []) :
|
||||
(xs ++ ys).maxOn f (by simp [hxs]) = maxOn f (xs.maxOn f hxs) (ys.maxOn f hys) := by
|
||||
simp only [List.maxOn_eq_minOn, maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa [LE.le_opposite_iff] using List.minOn_append (f := f) hxs hys
|
||||
|
||||
protected theorem maxOn_eq_head [LE β] [DecidableLE β] [IsLinearPreorder β] {xs : List α}
|
||||
{f : α → β} (h : xs ≠ []) (h' : ∀ x ∈ xs, f x ≤ f (xs.head h)) :
|
||||
xs.maxOn f h = xs.head h := by
|
||||
rw [List.maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa [LE.le_opposite_iff] using List.minOn_eq_head (f := f) h (by simpa [LE.le_opposite_iff] using h')
|
||||
|
||||
protected theorem max_map
|
||||
[LE β] [DecidableLE β] [Max β] [IsLinearPreorder β] [LawfulOrderLeftLeaningMax β] {xs : List α}
|
||||
{f : α → β} (h : xs ≠ []) : (xs.map f).max (by simpa) = f (xs.maxOn f h) := by
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : Min β := (inferInstanceAs (Max β)).oppositeMin
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
letI : Min β := (inferInstance : Max β).oppositeMin
|
||||
simpa [List.max_eq_min] using List.min_map (f := f) h
|
||||
|
||||
protected theorem maxOn_eq_max [Max α] [LE α] [DecidableLE α] [LawfulOrderLeftLeaningMax α]
|
||||
@@ -458,7 +458,7 @@ protected theorem max_map_eq_max [Max α] [LE α] [DecidableLE α] [LawfulOrderL
|
||||
protected theorem maxOn_replicate [LE β] [DecidableLE β] [IsLinearPreorder β]
|
||||
{n : Nat} {a : α} {f : α → β} (h : replicate n a ≠ []) :
|
||||
(replicate n a).maxOn f h = a :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.minOn_replicate (f := f) h
|
||||
|
||||
/-! # minOn? -/
|
||||
@@ -579,7 +579,7 @@ protected theorem maxOn?_nil [LE β] [DecidableLE β] {f : α → β} :
|
||||
protected theorem maxOn?_cons_eq_some_maxOn
|
||||
[LE β] [DecidableLE β] {f : α → β} {x : α} {xs : List α} :
|
||||
(x :: xs).maxOn? f = some ((x :: xs).maxOn f (fun h => nomatch h)) :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.minOn?_cons_eq_some_minOn
|
||||
|
||||
protected theorem maxOn?_cons
|
||||
@@ -588,7 +588,7 @@ protected theorem maxOn?_cons
|
||||
have : maxOn f x = (letI : LE β := LE.opposite inferInstance; minOn f x) := by
|
||||
ext; simp only [maxOn_eq_minOn]
|
||||
simp only [List.maxOn?_eq_minOn?, this]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
exact List.minOn?_cons
|
||||
|
||||
@[simp]
|
||||
@@ -599,8 +599,8 @@ protected theorem maxOn?_singleton [LE β] [DecidableLE β] {x : α} {f : α →
|
||||
@[simp]
|
||||
protected theorem maxOn?_id [Max α] [LE α] [DecidableLE α] [LawfulOrderLeftLeaningMax α]
|
||||
{xs : List α} : xs.maxOn? id = xs.max? := by
|
||||
letI : LE α := (inferInstanceAs (LE α)).opposite
|
||||
letI : Min α := (inferInstanceAs (Max α)).oppositeMin
|
||||
letI : LE α := (inferInstance : LE α).opposite
|
||||
letI : Min α := (inferInstance : Max α).oppositeMin
|
||||
simpa only [List.maxOn?_eq_minOn?, List.max?_eq_min?] using List.minOn?_id (α := α)
|
||||
|
||||
protected theorem maxOn?_eq_if
|
||||
@@ -610,7 +610,7 @@ protected theorem maxOn?_eq_if
|
||||
some (xs.maxOn f h)
|
||||
else
|
||||
none :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.minOn?_eq_if
|
||||
|
||||
@[simp]
|
||||
@@ -620,55 +620,55 @@ protected theorem isSome_maxOn?_iff [LE β] [DecidableLE β] {f : α → β} {xs
|
||||
|
||||
protected theorem maxOn_eq_get_maxOn? [LE β] [DecidableLE β] {f : α → β} {xs : List α}
|
||||
(h : xs ≠ []) : xs.maxOn f h = (xs.maxOn? f).get (List.isSome_maxOn?_iff.mpr h) :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.minOn_eq_get_minOn? (f := f) h
|
||||
|
||||
protected theorem maxOn?_eq_some_maxOn [LE β] [DecidableLE β] {f : α → β} {xs : List α}
|
||||
(h : xs ≠ []) : xs.maxOn? f = some (xs.maxOn f h) :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.minOn?_eq_some_minOn (f := f) h
|
||||
|
||||
@[simp]
|
||||
protected theorem get_maxOn? [LE β] [DecidableLE β] {f : α → β} {xs : List α}
|
||||
(h : xs ≠ []) : (xs.maxOn? f).get (List.isSome_maxOn?_iff.mpr h) = xs.maxOn f h :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.get_minOn? (f := f) h
|
||||
|
||||
protected theorem maxOn_eq_of_maxOn?_eq_some
|
||||
[LE β] [DecidableLE β] {f : α → β} {xs : List α} {x : α} (h : xs.maxOn? f = some x) :
|
||||
xs.maxOn f (List.isSome_maxOn?_iff.mp (Option.isSome_of_eq_some h)) = x :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.minOn_eq_of_minOn?_eq_some (f := f) h
|
||||
|
||||
protected theorem isSome_maxOn?_of_mem
|
||||
[LE β] [DecidableLE β] {f : α → β} {xs : List α} {x : α} (h : x ∈ xs) :
|
||||
(xs.maxOn? f).isSome :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.isSome_minOn?_of_mem (f := f) h
|
||||
|
||||
protected theorem le_apply_get_maxOn?_of_mem
|
||||
[LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β} {xs : List α} {x : α} (h : x ∈ xs) :
|
||||
f x ≤ f ((xs.maxOn? f).get (List.isSome_maxOn?_of_mem h)) := by
|
||||
simp only [List.maxOn?_eq_minOn?]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa [LE.le_opposite_iff] using List.apply_get_minOn?_le_of_mem (f := f) h
|
||||
|
||||
protected theorem maxOn?_mem [LE β] [DecidableLE β] {xs : List α}
|
||||
{f : α → β} (h : xs.maxOn? f = some a) : a ∈ xs :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.minOn?_mem (f := f) h
|
||||
|
||||
protected theorem maxOn?_replicate [LE β] [DecidableLE β] [IsLinearPreorder β]
|
||||
{n : Nat} {a : α} {f : α → β} :
|
||||
(replicate n a).maxOn? f = if n = 0 then none else some a :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.minOn?_replicate
|
||||
|
||||
@[simp]
|
||||
protected theorem maxOn?_replicate_of_pos [LE β] [DecidableLE β] [IsLinearPreorder β]
|
||||
{n : Nat} {a : α} {f : α → β} (h : 0 < n) :
|
||||
(replicate n a).maxOn? f = some a :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
List.minOn?_replicate_of_pos (f := f) h
|
||||
|
||||
@[simp]
|
||||
@@ -678,7 +678,7 @@ protected theorem maxOn?_append [LE β] [DecidableLE β] [IsLinearPreorder β]
|
||||
have : maxOn f = (letI : LE β := LE.opposite inferInstance; minOn f) := by
|
||||
ext; simp only [maxOn_eq_minOn]
|
||||
simp only [List.maxOn?_eq_minOn?, this]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
exact List.minOn?_append xs ys f
|
||||
|
||||
end List
|
||||
|
||||
@@ -478,7 +478,7 @@ instance : Std.Trichotomous (. < . : Nat → Nat → Prop) where
|
||||
|
||||
set_option linter.missingDocs false in
|
||||
@[deprecated Nat.instTrichotomousLt (since := "2025-10-27")]
|
||||
def Nat.instAntisymmNotLt : Std.Antisymm (¬ . < . : Nat → Nat → Prop) where
|
||||
theorem Nat.instAntisymmNotLt : Std.Antisymm (¬ . < . : Nat → Nat → Prop) where
|
||||
antisymm := Nat.instTrichotomousLt.trichotomous
|
||||
|
||||
protected theorem add_le_add_left {n m : Nat} (h : n ≤ m) (k : Nat) : k + n ≤ k + m :=
|
||||
|
||||
@@ -147,7 +147,7 @@ public theorem LawfulOrderMin.of_min_le {α : Type u} [Min α] [LE α]
|
||||
This lemma characterizes in terms of `LE α` when a `Max α` instance "behaves like a supremum
|
||||
operator".
|
||||
-/
|
||||
public def LawfulOrderSup.of_le {α : Type u} [Max α] [LE α]
|
||||
public theorem LawfulOrderSup.of_le {α : Type u} [Max α] [LE α]
|
||||
(max_le_iff : ∀ a b c : α, max a b ≤ c ↔ a ≤ c ∧ b ≤ c) : LawfulOrderSup α where
|
||||
max_le_iff := max_le_iff
|
||||
|
||||
@@ -159,7 +159,7 @@ instances.
|
||||
|
||||
The produced instance entails `LawfulOrderSup α` and `MaxEqOr α`.
|
||||
-/
|
||||
public def LawfulOrderMax.of_max_le_iff {α : Type u} [Max α] [LE α]
|
||||
public theorem LawfulOrderMax.of_max_le_iff {α : Type u} [Max α] [LE α]
|
||||
(max_le_iff : ∀ a b c : α, max a b ≤ c ↔ a ≤ c ∧ b ≤ c := by exact LawfulOrderInf.le_min_iff)
|
||||
(max_eq_or : ∀ a b : α, max a b = a ∨ max a b = b := by exact MaxEqOr.max_eq_or) :
|
||||
LawfulOrderMax α where
|
||||
@@ -196,7 +196,7 @@ Creates a *total* `LE α` instance from an `LT α` instance.
|
||||
|
||||
This only makes sense for asymmetric `LT α` instances (see `Std.Asymm`).
|
||||
-/
|
||||
@[inline]
|
||||
@[inline, implicit_reducible, expose]
|
||||
public def _root_.LE.ofLT (α : Type u) [LT α] : LE α where
|
||||
le a b := ¬ b < a
|
||||
|
||||
@@ -208,7 +208,7 @@ public instance LawfulOrderLT.of_lt {α : Type u} [LT α] [i : Asymm (α := α)
|
||||
haveI := LE.ofLT α
|
||||
LawfulOrderLT α :=
|
||||
letI := LE.ofLT α
|
||||
{ lt_iff a b := by simp +instances [LE.ofLT, LE.le]; apply Asymm.asymm }
|
||||
{ lt_iff a b := by simp +instances [LE.le]; apply Asymm.asymm }
|
||||
|
||||
/--
|
||||
If an `LT α` instance is asymmetric and its negation is transitive, then `LE.ofLT α` represents a
|
||||
@@ -253,7 +253,7 @@ public theorem LawfulOrderInf.of_lt {α : Type u} [Min α] [LT α]
|
||||
letI := LE.ofLT α
|
||||
{ le_min_iff a b c := by
|
||||
open Classical in
|
||||
simp +instances only [LE.ofLT, LE.le]
|
||||
simp +instances only [LE.le]
|
||||
simp [← not_or, Decidable.not_iff_not]
|
||||
simpa [Decidable.imp_iff_not_or] using min_lt_iff a b c }
|
||||
|
||||
@@ -276,14 +276,14 @@ public theorem LawfulOrderMin.of_lt {α : Type u} [Min α] [LT α]
|
||||
This lemma characterizes in terms of `LT α` when a `Max α` instance
|
||||
"behaves like an supremum operator" with respect to `LE.ofLT α`.
|
||||
-/
|
||||
public def LawfulOrderSup.of_lt {α : Type u} [Max α] [LT α]
|
||||
public theorem LawfulOrderSup.of_lt {α : Type u} [Max α] [LT α]
|
||||
(lt_max_iff : ∀ a b c : α, c < max a b ↔ c < a ∨ c < b) :
|
||||
haveI := LE.ofLT α
|
||||
LawfulOrderSup α :=
|
||||
letI := LE.ofLT α
|
||||
{ max_le_iff a b c := by
|
||||
open Classical in
|
||||
simp +instances only [LE.ofLT, LE.le]
|
||||
simp +instances only [LE.le]
|
||||
simp [← not_or, Decidable.not_iff_not]
|
||||
simpa [Decidable.imp_iff_not_or] using lt_max_iff a b c }
|
||||
|
||||
@@ -293,7 +293,7 @@ Derives a `LawfulOrderMax α` instance for `LE.ofLT` from two properties involvi
|
||||
|
||||
The produced instance entails `LawfulOrderSup α` and `MaxEqOr α`.
|
||||
-/
|
||||
public def LawfulOrderMax.of_lt {α : Type u} [Max α] [LT α]
|
||||
public theorem LawfulOrderMax.of_lt {α : Type u} [Max α] [LT α]
|
||||
(lt_max_iff : ∀ a b c : α, c < max a b ↔ c < a ∨ c < b)
|
||||
(max_eq_or : ∀ a b : α, max a b = a ∨ max a b = b) :
|
||||
haveI := LE.ofLT α
|
||||
|
||||
@@ -26,7 +26,7 @@ public def _root_.LE.ofOrd (α : Type u) [Ord α] : LE α where
|
||||
/--
|
||||
Creates an `DecidableLE α` instance using a well-behaved `Ord α` instance.
|
||||
-/
|
||||
@[inline, expose]
|
||||
@[inline, expose, implicit_reducible]
|
||||
public def _root_.DecidableLE.ofOrd (α : Type u) [LE α] [Ord α] [LawfulOrderOrd α] :
|
||||
DecidableLE α :=
|
||||
fun a b => match h : (compare a b).isLE with
|
||||
@@ -93,7 +93,7 @@ grind_pattern compare_ne_eq => compare a b, Ordering.eq where
|
||||
/--
|
||||
Creates a `DecidableLT α` instance using a well-behaved `Ord α` instance.
|
||||
-/
|
||||
@[inline, expose]
|
||||
@[inline, expose, implicit_reducible]
|
||||
public def _root_.DecidableLT.ofOrd (α : Type u) [LE α] [LT α] [Ord α] [LawfulOrderOrd α]
|
||||
[LawfulOrderLT α] :
|
||||
DecidableLT α :=
|
||||
|
||||
@@ -39,8 +39,8 @@ public theorem minOn_id [Min α] [LE α] [DecidableLE α] [LawfulOrderLeftLeanin
|
||||
|
||||
public theorem maxOn_id [Max α] [LE α] [DecidableLE α] [LawfulOrderLeftLeaningMax α] {x y : α} :
|
||||
maxOn id x y = max x y := by
|
||||
letI : LE α := (inferInstanceAs (LE α)).opposite
|
||||
letI : Min α := (inferInstanceAs (Max α)).oppositeMin
|
||||
letI : LE α := (inferInstance : LE α).opposite
|
||||
letI : Min α := (inferInstance : Max α).oppositeMin
|
||||
simp [maxOn, minOn_id, Max.min_oppositeMin, this]
|
||||
|
||||
public theorem minOn_eq_or [LE β] [DecidableLE β] {f : α → β} {x y : α} :
|
||||
@@ -168,32 +168,32 @@ public theorem maxOn_eq_right_of_lt
|
||||
[LE β] [DecidableLE β] [LT β] [Total (α := β) (· ≤ ·)] [LawfulOrderLT β]
|
||||
{f : α → β} {x y : α} (h : f x < f y) :
|
||||
maxOn f x y = y :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LT β := (inferInstanceAs (LT β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
letI : LT β := (inferInstance : LT β).opposite
|
||||
minOn_eq_right_of_lt (h := by simpa [LT.lt_opposite_iff] using h) ..
|
||||
|
||||
public theorem left_le_apply_maxOn [le : LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β}
|
||||
{x y : α} : f x ≤ f (maxOn f x y) := by
|
||||
rw [maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa only [LE.le_opposite_iff] using apply_minOn_le_left (f := f) ..
|
||||
|
||||
public theorem right_le_apply_maxOn [LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β}
|
||||
{x y : α} : f y ≤ f (maxOn f x y) := by
|
||||
rw [maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa only [LE.le_opposite_iff] using apply_minOn_le_right (f := f)
|
||||
|
||||
public theorem apply_maxOn_le_iff [LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β}
|
||||
{x y : α} {b : β} :
|
||||
f (maxOn f x y) ≤ b ↔ f x ≤ b ∧ f y ≤ b := by
|
||||
rw [maxOn_eq_minOn]
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
simpa only [LE.le_opposite_iff] using le_apply_minOn_iff (f := f)
|
||||
|
||||
public theorem maxOn_assoc [LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β}
|
||||
{x y z : α} : maxOn f (maxOn f x y) z = maxOn f x (maxOn f y z) :=
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
minOn_assoc (f := f)
|
||||
|
||||
public instance [LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β} :
|
||||
@@ -203,8 +203,8 @@ public instance [LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β} :
|
||||
|
||||
public theorem max_apply [LE β] [DecidableLE β] [Max β] [LawfulOrderLeftLeaningMax β]
|
||||
{f : α → β} {x y : α} : max (f x) (f y) = f (maxOn f x y) := by
|
||||
letI : LE β := (inferInstanceAs (LE β)).opposite
|
||||
letI : Min β := (inferInstanceAs (Max β)).oppositeMin
|
||||
letI : LE β := (inferInstance : LE β).opposite
|
||||
letI : Min β := (inferInstance : Max β).oppositeMin
|
||||
simpa [Max.min_oppositeMin] using min_apply (f := f)
|
||||
|
||||
public theorem apply_maxOn [LE β] [DecidableLE β] [Max β] [LawfulOrderLeftLeaningMax β]
|
||||
|
||||
@@ -44,7 +44,7 @@ def min' [LE α] [DecidableLE α] (a b : α) : α :=
|
||||
|
||||
open scoped Std.OppositeOrderInstances in
|
||||
def max' [LE α] [DecidableLE α] (a b : α) : α :=
|
||||
letI : LE α := (inferInstanceAs (LE α)).opposite
|
||||
letI : LE α := (inferInstance : LE α).opposite
|
||||
-- `DecidableLE` for the opposite order is derived automatically via `OppositeOrderInstances`
|
||||
min' a b
|
||||
```
|
||||
@@ -52,7 +52,8 @@ def max' [LE α] [DecidableLE α] (a b : α) : α :=
|
||||
Without the `open scoped` command, Lean would not find the required {lit}`DecidableLE α`
|
||||
instance for the opposite order.
|
||||
-/
|
||||
@[implicit_reducible] def LE.opposite (le : LE α) : LE α where
|
||||
@[implicit_reducible]
|
||||
def LE.opposite (le : LE α) : LE α where
|
||||
le a b := b ≤ a
|
||||
|
||||
theorem LE.opposite_def {le : LE α} :
|
||||
@@ -89,6 +90,7 @@ example [LE α] [LT α] [Std.LawfulOrderLT α] [Std.IsLinearOrder α] {x y : α}
|
||||
Without the `open scoped` command, Lean would not find the {lit}`LawfulOrderLT α`
|
||||
and {lit}`IsLinearOrder α` instances for the opposite order that are required by {name}`not_le`.
|
||||
-/
|
||||
@[implicit_reducible]
|
||||
def LT.opposite (lt : LT α) : LT α where
|
||||
lt a b := b < a
|
||||
|
||||
@@ -125,6 +127,7 @@ example [LE α] [DecidableLE α] [Min α] [Std.LawfulOrderLeftLeaningMin α] {a
|
||||
Without the `open scoped` command, Lean would not find the {lit}`LawfulOrderLeftLeaningMax α`
|
||||
instance for the opposite order that is required by {name}`max_eq_if`.
|
||||
-/
|
||||
@[implicit_reducible]
|
||||
def Min.oppositeMax (min : Min α) : Max α where
|
||||
max a b := Min.min a b
|
||||
|
||||
@@ -161,6 +164,7 @@ example [LE α] [DecidableLE α] [Max α] [Std.LawfulOrderLeftLeaningMax α] {a
|
||||
Without the `open scoped` command, Lean would not find the {lit}`LawfulOrderLeftLeaningMin α`
|
||||
instance for the opposite order that is required by {name}`min_eq_if`.
|
||||
-/
|
||||
@[implicit_reducible]
|
||||
def Max.oppositeMin (max : Max α) : Min α where
|
||||
min a b := Max.max a b
|
||||
|
||||
|
||||
@@ -47,7 +47,7 @@ public instance instLawfulOrderBEqOfDecidableLE {α : Type u} [LE α] [Decidable
|
||||
beq_iff_le_and_ge := by simp [BEq.beq]
|
||||
|
||||
/-- If `LT` can be characterized in terms of a decidable `LE`, then `LT` is decidable either. -/
|
||||
@[expose, instance_reducible]
|
||||
@[inline, expose, implicit_reducible]
|
||||
public def decidableLTOfLE {α : Type u} [LE α] {_ : LT α} [DecidableLE α] [LawfulOrderLT α] :
|
||||
DecidableLT α :=
|
||||
fun a b =>
|
||||
@@ -171,7 +171,7 @@ automatically. If it fails, it is necessary to provide some of the fields manual
|
||||
* Other proof obligations, namely `le_refl` and `le_trans`, can be omitted if `Refl` and `Trans`
|
||||
instances can be synthesized.
|
||||
-/
|
||||
@[expose, implicit_reducible]
|
||||
@[inline, expose, implicit_reducible]
|
||||
public def PreorderPackage.ofLE (α : Type u)
|
||||
(args : Packages.PreorderOfLEArgs α := by exact {}) : PreorderPackage α where
|
||||
toLE := args.le
|
||||
@@ -256,7 +256,7 @@ automatically. If it fails, it is necessary to provide some of the fields manual
|
||||
* Other proof obligations, namely `le_refl`, `le_trans` and `le_antisymm`, can be omitted if `Refl`,
|
||||
`Trans` and `Antisymm` instances can be synthesized.
|
||||
-/
|
||||
@[expose, implicit_reducible]
|
||||
@[inline, expose, implicit_reducible]
|
||||
public def PartialOrderPackage.ofLE (α : Type u)
|
||||
(args : Packages.PartialOrderOfLEArgs α := by exact {}) : PartialOrderPackage α where
|
||||
toPreorderPackage := .ofLE α args.toPreorderOfLEArgs
|
||||
@@ -385,7 +385,7 @@ automatically. If it fails, it is necessary to provide some of the fields manual
|
||||
* Other proof obligations, namely `le_total` and `le_trans`, can be omitted if `Total` and `Trans`
|
||||
instances can be synthesized.
|
||||
-/
|
||||
@[expose, implicit_reducible]
|
||||
@[inline, expose, implicit_reducible]
|
||||
public def LinearPreorderPackage.ofLE (α : Type u)
|
||||
(args : Packages.LinearPreorderOfLEArgs α := by exact {}) : LinearPreorderPackage α where
|
||||
toPreorderPackage := .ofLE α args.toPreorderOfLEArgs
|
||||
@@ -487,7 +487,7 @@ automatically. If it fails, it is necessary to provide some of the fields manual
|
||||
* Other proof obligations, namely `le_total`, `le_trans` and `le_antisymm`, can be omitted if
|
||||
`Total`, `Trans` and `Antisymm` instances can be synthesized.
|
||||
-/
|
||||
@[expose, implicit_reducible]
|
||||
@[inline, expose, implicit_reducible]
|
||||
public def LinearOrderPackage.ofLE (α : Type u)
|
||||
(args : Packages.LinearOrderOfLEArgs α := by exact {}) : LinearOrderPackage α where
|
||||
toLinearPreorderPackage := .ofLE α args.toLinearPreorderOfLEArgs
|
||||
@@ -647,7 +647,7 @@ automatically. If it fails, it is necessary to provide some of the fields manual
|
||||
* Other proof obligations, for example `transOrd`, can be omitted if a matching instance can be
|
||||
synthesized.
|
||||
-/
|
||||
@[expose, instance_reducible]
|
||||
@[inline, expose, implicit_reducible]
|
||||
public def LinearPreorderPackage.ofOrd (α : Type u)
|
||||
(args : Packages.LinearPreorderOfOrdArgs α := by exact {}) : LinearPreorderPackage α :=
|
||||
letI := args.ord
|
||||
@@ -793,7 +793,7 @@ automatically. If it fails, it is necessary to provide some of the fields manual
|
||||
* Other proof obligations, such as `transOrd`, can be omitted if matching instances can be
|
||||
synthesized.
|
||||
-/
|
||||
@[expose, instance_reducible]
|
||||
@[inline, expose, implicit_reducible]
|
||||
public def LinearOrderPackage.ofOrd (α : Type u)
|
||||
(args : Packages.LinearOrderOfOrdArgs α := by exact {}) : LinearOrderPackage α :=
|
||||
-- set_option backward.isDefEq.respectTransparency false in
|
||||
|
||||
@@ -597,8 +597,7 @@ instance Iterator.instLawfulIteratorLoop [UpwardEnumerable α] [LE α] [Decidabl
|
||||
LawfulIteratorLoop (Rxc.Iterator α) Id n where
|
||||
lawful := by
|
||||
intro lift instLawfulMonadLiftFunction γ it init Pl wf f
|
||||
simp +instances only [IteratorLoop.defaultImplementation, IteratorLoop.forIn,
|
||||
IterM.DefaultConsumers.forIn'_eq_wf Pl wf]
|
||||
simp +instances only [IteratorLoop.forIn, IterM.DefaultConsumers.forIn'_eq_wf Pl wf]
|
||||
rw [IterM.DefaultConsumers.forIn'.wf]
|
||||
split; rotate_left
|
||||
· simp only [IterM.step_eq,
|
||||
@@ -1173,8 +1172,7 @@ instance Iterator.instLawfulIteratorLoop [UpwardEnumerable α] [LT α] [Decidabl
|
||||
LawfulIteratorLoop (Rxo.Iterator α) Id n where
|
||||
lawful := by
|
||||
intro lift instLawfulMonadLiftFunction γ it init Pl wf f
|
||||
simp +instances only [IteratorLoop.defaultImplementation, IteratorLoop.forIn,
|
||||
IterM.DefaultConsumers.forIn'_eq_wf Pl wf]
|
||||
simp +instances only [IteratorLoop.forIn, IterM.DefaultConsumers.forIn'_eq_wf Pl wf]
|
||||
rw [IterM.DefaultConsumers.forIn'.wf]
|
||||
split; rotate_left
|
||||
· simp [IterM.step_eq, Monadic.step, Internal.LawfulMonadLiftBindFunction.liftBind_pure (liftBind := lift)]
|
||||
@@ -1639,8 +1637,7 @@ instance Iterator.instLawfulIteratorLoop [UpwardEnumerable α]
|
||||
LawfulIteratorLoop (Rxi.Iterator α) Id n where
|
||||
lawful := by
|
||||
intro lift instLawfulMonadLiftFunction γ it init Pl wf f
|
||||
simp +instances only [IteratorLoop.defaultImplementation, IteratorLoop.forIn,
|
||||
IterM.DefaultConsumers.forIn'_eq_wf Pl wf]
|
||||
simp +instances only [IteratorLoop.forIn, IterM.DefaultConsumers.forIn'_eq_wf Pl wf]
|
||||
rw [IterM.DefaultConsumers.forIn'.wf]
|
||||
split; rotate_left
|
||||
· simp [Monadic.step_eq_step, Monadic.step, Internal.LawfulMonadLiftBindFunction.liftBind_pure]
|
||||
|
||||
@@ -438,6 +438,7 @@ protected theorem UpwardEnumerable.le_iff {α : Type u} [LE α] [UpwardEnumerabl
|
||||
[LawfulUpwardEnumerableLE α] {a b : α} : a ≤ b ↔ UpwardEnumerable.LE a b :=
|
||||
LawfulUpwardEnumerableLE.le_iff a b
|
||||
|
||||
@[expose, implicit_reducible]
|
||||
def UpwardEnumerable.instLETransOfLawfulUpwardEnumerableLE {α : Type u} [LE α]
|
||||
[UpwardEnumerable α] [LawfulUpwardEnumerable α] [LawfulUpwardEnumerableLE α] :
|
||||
Trans (α := α) (· ≤ ·) (· ≤ ·) (· ≤ ·) where
|
||||
@@ -502,12 +503,13 @@ protected theorem UpwardEnumerable.lt_succ_iff {α : Type u} [UpwardEnumerable
|
||||
← succMany?_eq_some_iff_succMany] at hn
|
||||
exact ⟨n, hn⟩
|
||||
|
||||
@[expose, implicit_reducible]
|
||||
def UpwardEnumerable.instLTTransOfLawfulUpwardEnumerableLT {α : Type u} [LT α]
|
||||
[UpwardEnumerable α] [LawfulUpwardEnumerable α] [LawfulUpwardEnumerableLT α] :
|
||||
Trans (α := α) (· < ·) (· < ·) (· < ·) where
|
||||
trans := by simpa [UpwardEnumerable.lt_iff] using @UpwardEnumerable.lt_trans
|
||||
|
||||
def UpwardEnumerable.instLawfulOrderLTOfLawfulUpwardEnumerableLT {α : Type u} [LT α] [LE α]
|
||||
theorem UpwardEnumerable.instLawfulOrderLTOfLawfulUpwardEnumerableLT {α : Type u} [LT α] [LE α]
|
||||
[UpwardEnumerable α] [LawfulUpwardEnumerable α] [LawfulUpwardEnumerableLT α]
|
||||
[LawfulUpwardEnumerableLE α] :
|
||||
LawfulOrderLT α where
|
||||
|
||||
@@ -245,7 +245,7 @@ the given {name}`ForwardPattern` instance.
|
||||
It is sometimes possible to give a more efficient implementation; see {name}`ToForwardSearcher`
|
||||
for more details.
|
||||
-/
|
||||
@[inline]
|
||||
@[inline, implicit_reducible]
|
||||
def defaultImplementation [ForwardPattern pat] :
|
||||
ToForwardSearcher pat (DefaultForwardSearcher pat) where
|
||||
toSearcher := DefaultForwardSearcher.iter pat
|
||||
@@ -450,7 +450,7 @@ the given {name}`BackwardPattern` instance.
|
||||
It is sometimes possible to give a more efficient implementation; see {name}`ToBackwardSearcher`
|
||||
for more details.
|
||||
-/
|
||||
@[inline]
|
||||
@[inline, implicit_reducible]
|
||||
def defaultImplementation [BackwardPattern pat] :
|
||||
ToBackwardSearcher pat (DefaultBackwardSearcher pat) where
|
||||
toSearcher := DefaultBackwardSearcher.iter pat
|
||||
|
||||
@@ -828,7 +828,6 @@ grind_pattern Vector.getElem?_eq_none => xs[i]? where
|
||||
theorem getElem?_eq_some_iff {xs : Vector α n} : xs[i]? = some b ↔ ∃ h : i < n, xs[i] = b :=
|
||||
_root_.getElem?_eq_some_iff
|
||||
|
||||
@[grind →]
|
||||
theorem getElem_of_getElem? {xs : Vector α n} : xs[i]? = some a → ∃ h : i < n, xs[i] = a :=
|
||||
getElem?_eq_some_iff.mp
|
||||
|
||||
|
||||
@@ -47,6 +47,7 @@ Creates a `TypeName` instance.
|
||||
For safety, it is required that the constant `typeName` is definitionally equal
|
||||
to `α`.
|
||||
-/
|
||||
@[implicit_reducible]
|
||||
unsafe def TypeName.mk (α : Type u) (typeName : Name) : TypeName α :=
|
||||
⟨unsafeCast typeName⟩
|
||||
|
||||
|
||||
@@ -266,6 +266,7 @@ export NoNatZeroDivisors (no_nat_zero_divisors)
|
||||
namespace NoNatZeroDivisors
|
||||
|
||||
/-- Alternative constructor for `NoNatZeroDivisors` when we have an `IntModule`. -/
|
||||
@[implicit_reducible]
|
||||
def mk' {α} [IntModule α]
|
||||
(eq_zero_of_mul_eq_zero : ∀ (k : Nat) (a : α), k ≠ 0 → k • a = 0 → a = 0) :
|
||||
NoNatZeroDivisors α where
|
||||
|
||||
@@ -501,6 +501,7 @@ private theorem mk'_aux {x y : Nat} (p : Nat) (h : y ≤ x) :
|
||||
omega
|
||||
|
||||
/-- Alternative constructor when `α` is a `Ring`. -/
|
||||
@[implicit_reducible]
|
||||
def mk' (p : Nat) (α : Type u) [Ring α]
|
||||
(ofNat_eq_zero_iff : ∀ (x : Nat), OfNat.ofNat (α := α) x = 0 ↔ x % p = 0) : IsCharP α p where
|
||||
ofNat_ext_iff {x y} := by
|
||||
|
||||
@@ -330,7 +330,7 @@ theorem toQ_inj [AddRightCancel α] {a b : α} : toQ a = toQ b → a = b := by
|
||||
obtain ⟨k, h₁⟩ := h₁
|
||||
exact AddRightCancel.add_right_cancel a b k h₁
|
||||
|
||||
instance [Semiring α] [AddRightCancel α] [NoNatZeroDivisors α] : NoNatZeroDivisors (OfSemiring.Q α) where
|
||||
instance (priority := high) [Semiring α] [AddRightCancel α] [NoNatZeroDivisors α] : NoNatZeroDivisors (OfSemiring.Q α) where
|
||||
no_nat_zero_divisors := by
|
||||
intro k a b h₁ h₂
|
||||
replace h₂ : mul (natCast k) a = mul (natCast k) b := h₂
|
||||
@@ -346,7 +346,7 @@ instance [Semiring α] [AddRightCancel α] [NoNatZeroDivisors α] : NoNatZeroDiv
|
||||
replace h₂ := NoNatZeroDivisors.no_nat_zero_divisors k (a₁ + b₂) (a₂ + b₁) h₁ h₂
|
||||
apply Quot.sound; simp [r]; exists 0; simp [h₂]
|
||||
|
||||
instance {p} [Semiring α] [AddRightCancel α] [IsCharP α p] : IsCharP (OfSemiring.Q α) p where
|
||||
instance (priority := high) {p} [Semiring α] [AddRightCancel α] [IsCharP α p] : IsCharP (OfSemiring.Q α) p where
|
||||
ofNat_ext_iff := by
|
||||
intro x y
|
||||
constructor
|
||||
@@ -366,7 +366,7 @@ instance {p} [Semiring α] [AddRightCancel α] [IsCharP α p] : IsCharP (OfSemir
|
||||
apply Quot.sound
|
||||
exists 0; simp [← Semiring.ofNat_eq_natCast, this]
|
||||
|
||||
instance [LE α] [IsPreorder α] [OrderedAdd α] : LE (OfSemiring.Q α) where
|
||||
instance (priority := high) [LE α] [IsPreorder α] [OrderedAdd α] : LE (OfSemiring.Q α) where
|
||||
le a b := Q.liftOn₂ a b (fun (a, b) (c, d) => a + d ≤ b + c)
|
||||
(by intro (a₁, b₁) (a₂, b₂) (a₃, b₃) (a₄, b₄)
|
||||
simp; intro k₁ h₁ k₂ h₂
|
||||
@@ -382,14 +382,14 @@ instance [LE α] [IsPreorder α] [OrderedAdd α] : LE (OfSemiring.Q α) where
|
||||
rw [this]; clear this
|
||||
rw [← OrderedAdd.add_le_left_iff])
|
||||
|
||||
instance [LE α] [IsPreorder α] [OrderedAdd α] : LT (OfSemiring.Q α) where
|
||||
instance (priority := high) [LE α] [IsPreorder α] [OrderedAdd α] : LT (OfSemiring.Q α) where
|
||||
lt a b := a ≤ b ∧ ¬b ≤ a
|
||||
|
||||
@[local simp] theorem mk_le_mk [LE α] [IsPreorder α] [OrderedAdd α] {a₁ a₂ b₁ b₂ : α} :
|
||||
Q.mk (a₁, a₂) ≤ Q.mk (b₁, b₂) ↔ a₁ + b₂ ≤ a₂ + b₁ := by
|
||||
rfl
|
||||
|
||||
instance [LE α] [IsPreorder α] [OrderedAdd α] : IsPreorder (OfSemiring.Q α) where
|
||||
instance (priority := high) [LE α] [IsPreorder α] [OrderedAdd α] : IsPreorder (OfSemiring.Q α) where
|
||||
le_refl a := by
|
||||
obtain ⟨⟨a₁, a₂⟩⟩ := a
|
||||
change Q.mk _ ≤ Q.mk _
|
||||
@@ -424,7 +424,7 @@ theorem toQ_le [LE α] [IsPreorder α] [OrderedAdd α] {a b : α} : toQ a ≤ to
|
||||
theorem toQ_lt [LE α] [LT α] [LawfulOrderLT α] [IsPreorder α] [OrderedAdd α] {a b : α} : toQ a < toQ b ↔ a < b := by
|
||||
simp [lt_iff_le_and_not_ge]
|
||||
|
||||
instance [LE α] [IsPreorder α] [OrderedAdd α] : OrderedAdd (OfSemiring.Q α) where
|
||||
instance (priority := high) [LE α] [IsPreorder α] [OrderedAdd α] : OrderedAdd (OfSemiring.Q α) where
|
||||
add_le_left_iff := by
|
||||
intro a b c
|
||||
obtain ⟨⟨a₁, a₂⟩⟩ := a
|
||||
@@ -438,7 +438,7 @@ instance [LE α] [IsPreorder α] [OrderedAdd α] : OrderedAdd (OfSemiring.Q α)
|
||||
rw [← OrderedAdd.add_le_left_iff]
|
||||
|
||||
-- This perhaps works in more generality than `ExistsAddOfLT`?
|
||||
instance [LE α] [LT α] [LawfulOrderLT α] [IsPreorder α] [OrderedRing α] [ExistsAddOfLT α] : OrderedRing (OfSemiring.Q α) where
|
||||
instance (priority := high) [LE α] [LT α] [LawfulOrderLT α] [IsPreorder α] [OrderedRing α] [ExistsAddOfLT α] : OrderedRing (OfSemiring.Q α) where
|
||||
zero_lt_one := by
|
||||
rw [← toQ_ofNat, ← toQ_ofNat, toQ_lt]
|
||||
exact OrderedRing.zero_lt_one
|
||||
@@ -511,7 +511,16 @@ def ofCommSemiring : CommRing (OfSemiring.Q α) :=
|
||||
{ OfSemiring.ofSemiring with
|
||||
mul_comm := mul_comm }
|
||||
|
||||
attribute [instance] ofCommSemiring
|
||||
attribute [instance high] ofCommSemiring
|
||||
instance (priority := high) [CommRing (OfSemiring.Q α)] : Add (OfSemiring.Q α) := by infer_instance
|
||||
instance (priority := high) [CommRing (OfSemiring.Q α)] : Sub (OfSemiring.Q α) := by infer_instance
|
||||
instance (priority := high) [CommRing (OfSemiring.Q α)] : Mul (OfSemiring.Q α) := by infer_instance
|
||||
instance (priority := high) [CommRing (OfSemiring.Q α)] : Neg (OfSemiring.Q α) := by infer_instance
|
||||
instance (priority := high) [CommRing (OfSemiring.Q α)] : OfNat (OfSemiring.Q α) n := by infer_instance
|
||||
attribute [local instance] Semiring.natCast Ring.intCast
|
||||
instance (priority := high) [CommRing (OfSemiring.Q α)] : NatCast (OfSemiring.Q α) := by infer_instance
|
||||
instance (priority := high) [CommRing (OfSemiring.Q α)] : IntCast (OfSemiring.Q α) := by infer_instance
|
||||
instance (priority := high) [CommRing (OfSemiring.Q α)] : HPow (OfSemiring.Q α) Nat (OfSemiring.Q α) := by infer_instance
|
||||
|
||||
/-
|
||||
Remark: `↑a` is notation for `OfSemiring.toQ a`.
|
||||
|
||||
@@ -223,6 +223,7 @@ theorem natCast_div_of_dvd {x y : Nat} (h : y ∣ x) (w : (y : α) ≠ 0) :
|
||||
mul_inv_cancel w, Semiring.mul_one]
|
||||
|
||||
-- This is expensive as an instance. Let's see what breaks without it.
|
||||
@[implicit_reducible]
|
||||
def noNatZeroDivisors.ofIsCharPZero [IsCharP α 0] : NoNatZeroDivisors α := NoNatZeroDivisors.mk' <| by
|
||||
intro a b h w
|
||||
have := IsCharP.natCast_eq_zero_iff (α := α) 0 a
|
||||
|
||||
@@ -15,6 +15,7 @@ public section
|
||||
namespace Lean.Grind
|
||||
|
||||
/-- A `ToInt` instance on a semiring preserves powers if it preserves numerals and multiplication. -/
|
||||
@[implicit_reducible]
|
||||
def ToInt.pow_of_semiring [Semiring α] [ToInt α I] [ToInt.OfNat α I] [ToInt.Mul α I]
|
||||
(h₁ : I.isFinite) : ToInt.Pow α I where
|
||||
toInt_pow x n := by
|
||||
|
||||
@@ -350,6 +350,7 @@ theorem wrap_toInt (I : IntInterval) [ToInt α I] (x : α) :
|
||||
|
||||
/-- Construct a `ToInt.Sub` instance from a `ToInt.Add` and `ToInt.Neg` instance and
|
||||
a `sub_eq_add_neg` assumption. -/
|
||||
@[implicit_reducible]
|
||||
def Sub.of_sub_eq_add_neg {α : Type u} [_root_.Add α] [_root_.Neg α] [_root_.Sub α]
|
||||
(sub_eq_add_neg : ∀ x y : α, x - y = x + -y)
|
||||
{I : IntInterval} (h : I.isFinite) [ToInt α I] [Add α I] [Neg α I] : ToInt.Sub α I where
|
||||
|
||||
@@ -954,7 +954,7 @@ theorem monotone_readerTRun [PartialOrder γ]
|
||||
instance [inst : PartialOrder (m α)] : PartialOrder (StateRefT' ω σ m α) := instOrderPi
|
||||
instance [inst : CCPO (m α)] : CCPO (StateRefT' ω σ m α) := instCCPOPi
|
||||
instance [Monad m] [∀ α, PartialOrder (m α)] [MonoBind m] : MonoBind (StateRefT' ω σ m) :=
|
||||
inferInstanceAs (MonoBind (ReaderT _ _))
|
||||
inferInstanceAs (MonoBind (ReaderT (ST.Ref ω σ) m))
|
||||
|
||||
@[partial_fixpoint_monotone]
|
||||
theorem monotone_stateRefT'Run [PartialOrder γ]
|
||||
|
||||
@@ -910,6 +910,8 @@ When messages contain autogenerated names (e.g., metavariables like `?m.47`), th
|
||||
differ between runs or Lean versions. Use `set_option pp.mvars.anonymous false` to replace
|
||||
anonymous metavariables with `?_` while preserving user-named metavariables like `?a`.
|
||||
Alternatively, `set_option pp.mvars false` replaces all metavariables with `?_`.
|
||||
Similarly, `set_option pp.fvars.anonymous false` replaces loose free variable names like
|
||||
`_fvar.22` with `_fvar._`.
|
||||
|
||||
For example, `#guard_msgs (error, drop all) in cmd` means to check errors and drop
|
||||
everything else.
|
||||
|
||||
@@ -102,18 +102,23 @@ example : foo.default = (default, default) :=
|
||||
abbrev inferInstance {α : Sort u} [i : α] : α := i
|
||||
|
||||
set_option checkBinderAnnotations false in
|
||||
/-- `inferInstanceAs α` synthesizes a value of any target type by typeclass
|
||||
inference. This is just like `inferInstance` except that `α` is given
|
||||
explicitly instead of being inferred from the target type. It is especially
|
||||
useful when the target type is some `α'` which is definitionally equal to `α`,
|
||||
but the instance we are looking for is only registered for `α` (because
|
||||
typeclass search does not unfold most definitions, but definitional equality
|
||||
does.) Example:
|
||||
/-- `inferInstanceAs α` synthesizes an instance of type `α`, transporting it from a
|
||||
definitionally equal type if necessary. This is useful when `α` is definitionally equal to
|
||||
some `α'` for which instances are registered, as it prevents leaking the definition's RHS
|
||||
at lower transparencies.
|
||||
|
||||
`inferInstanceAs` requires an expected type from context. If you just need to synthesize an
|
||||
instance without transporting between types, use `inferInstance` instead.
|
||||
|
||||
Example:
|
||||
```
|
||||
#check inferInstanceAs (Inhabited Nat) -- Inhabited Nat
|
||||
def D := Nat
|
||||
instance : Inhabited D := inferInstanceAs (Inhabited Nat)
|
||||
```
|
||||
|
||||
See `Lean.Meta.WrapInstance` for details.
|
||||
-/
|
||||
abbrev inferInstanceAs (α : Sort u) [i : α] : α := i
|
||||
abbrev «inferInstanceAs» (α : Sort u) [i : α] : α := i
|
||||
|
||||
set_option bootstrap.inductiveCheckResultingUniverse false in
|
||||
/--
|
||||
@@ -1281,7 +1286,7 @@ export Max (max)
|
||||
Constructs a `Max` instance from a decidable `≤` operation.
|
||||
-/
|
||||
-- Marked inline so that `min x y + max x y` can be optimized to a single branch.
|
||||
@[inline]
|
||||
@[inline, implicit_reducible]
|
||||
def maxOfLe [LE α] [DecidableRel (@LE.le α _)] : Max α where
|
||||
max x y := ite (LE.le x y) y x
|
||||
|
||||
@@ -1298,7 +1303,7 @@ export Min (min)
|
||||
Constructs a `Min` instance from a decidable `≤` operation.
|
||||
-/
|
||||
-- Marked inline so that `min x y + max x y` can be optimized to a single branch.
|
||||
@[inline]
|
||||
@[inline, implicit_reducible]
|
||||
def minOfLe [LE α] [DecidableRel (@LE.le α _)] : Min α where
|
||||
min x y := ite (LE.le x y) x y
|
||||
|
||||
|
||||
@@ -272,6 +272,7 @@ Creates a `MonadStateOf` instance from a reference cell.
|
||||
This allows programs written against the [state monad](lean-manual://section/state-monads) API to
|
||||
be executed using a mutable reference cell to track the state.
|
||||
-/
|
||||
@[implicit_reducible]
|
||||
def Ref.toMonadStateOf (r : Ref σ α) : MonadStateOf α m where
|
||||
get := r.get
|
||||
set := r.set
|
||||
|
||||
@@ -169,7 +169,7 @@ def addDecl (decl : Declaration) (forceExpose := false) : CoreM Unit :=
|
||||
where
|
||||
doAdd := do
|
||||
profileitM Exception "type checking" (← getOptions) do
|
||||
withTraceNode `Kernel (return m!"{exceptEmoji ·} typechecking declarations {decl.getTopLevelNames}") do
|
||||
withTraceNode `Kernel (fun _ => return m!"typechecking declarations {decl.getTopLevelNames}") do
|
||||
warnIfUsesSorry decl
|
||||
try
|
||||
let env ← (← getEnv).addDeclAux (← getOptions) decl (← read).cancelTk?
|
||||
|
||||
@@ -49,7 +49,7 @@ structure CompilerM.Context where
|
||||
abbrev CompilerM := ReaderT CompilerM.Context $ StateRefT CompilerM.State CoreM
|
||||
|
||||
@[always_inline]
|
||||
instance : Monad CompilerM := let i := inferInstanceAs (Monad CompilerM); { pure := i.pure, bind := i.bind }
|
||||
instance : Monad CompilerM := let i : Monad CompilerM := inferInstance; { pure := i.pure, bind := i.bind }
|
||||
|
||||
@[inline] def withPhase (phase : Phase) (x : CompilerM α) : CompilerM α :=
|
||||
withReader (fun ctx => { ctx with phase }) x
|
||||
|
||||
@@ -106,6 +106,7 @@ private def getLitAux (fvarId : FVarId) (ofNat : Nat → α) (ofNatName : Name)
|
||||
let some natLit ← getLit fvarId | return none
|
||||
return ofNat natLit
|
||||
|
||||
@[implicit_reducible]
|
||||
def mkNatWrapperInstance (ofNat : Nat → α) (ofNatName : Name) (toNat : α → Nat) : Literal α where
|
||||
getLit := (getLitAux · ofNat ofNatName)
|
||||
mkLit x := do
|
||||
@@ -114,6 +115,7 @@ def mkNatWrapperInstance (ofNat : Nat → α) (ofNatName : Name) (toNat : α →
|
||||
|
||||
instance : Literal Char := mkNatWrapperInstance Char.ofNat ``Char.ofNat Char.toNat
|
||||
|
||||
@[implicit_reducible]
|
||||
def mkUIntInstance (matchLit : LitValue → Option α) (litValueCtor : α → LitValue) : Literal α where
|
||||
getLit fvarId := do
|
||||
let some (.lit litVal) ← findLetValue? (pu := .pure) fvarId | return none
|
||||
|
||||
@@ -62,11 +62,24 @@ def inlineCandidate? (e : LetValue .pure) : SimpM (Option InlineCandidateInfo) :
|
||||
if !decl.inlineIfReduceAttr && decl.recursive then return false
|
||||
if mustInline then return true
|
||||
/-
|
||||
We don't inline instances tagged with `[inline]/[always_inline]/[inline_if_reduce]` at the base phase
|
||||
We assume that at the base phase these annotations are for the instance methods that have been lambda lifted.
|
||||
We don't inline instances tagged with `[inline]/[always_inline]/[inline_if_reduce]` at the base phase.
|
||||
We assume that at the base phase these annotations are for the instance methods that will be lambda lifted during the base phase.
|
||||
Reason: we eagerly lambda lift local functions occurring at instances before saving their code at
|
||||
the end of the base phase. The goal is to make them cheap to inline in actual code.
|
||||
By inlining their definitions we would be just generating extra work for the lambda lifter.
|
||||
-/
|
||||
if (← inBasePhase) then
|
||||
if (← isImplicitReducible decl.name) then
|
||||
/-
|
||||
We claim it is correct to use `Meta.isInstance` because
|
||||
1. `shouldInline` is called during LCNF compilation, which runs at `addDecl` time
|
||||
2. Any instance referenced in the code was found by type class resolution during elaboration
|
||||
3. For TC resolution to find it, the scope was active during elaboration
|
||||
4. LCNF compilation happens before the scope changes
|
||||
|
||||
We don't want to use `isImplicitReducible` because some `instanceReducible` declarations are
|
||||
**not** instances.
|
||||
-/
|
||||
if (← Meta.isInstance decl.name) then
|
||||
unless decl.name == ``instDecidableEqBool do
|
||||
/-
|
||||
TODO: remove this hack after we refactor `Decidable` as suggested by Gabriel.
|
||||
|
||||
@@ -78,7 +78,7 @@ structure State where
|
||||
abbrev SimpM := ReaderT Context $ StateRefT State DiscrM
|
||||
|
||||
@[always_inline]
|
||||
instance : Monad SimpM := let i := inferInstanceAs (Monad SimpM); { pure := i.pure, bind := i.bind }
|
||||
instance : Monad SimpM := let i : Monad SimpM := inferInstance; { pure := i.pure, bind := i.bind }
|
||||
|
||||
instance : MonadFVarSubst SimpM .pure false where
|
||||
getSubst := return (← get).subst
|
||||
|
||||
@@ -256,7 +256,7 @@ abbrev CoreM := ReaderT Context <| StateRefT State (EIO Exception)
|
||||
-- Make the compiler generate specialized `pure`/`bind` so we do not have to optimize through the
|
||||
-- whole monad stack at every use site. May eventually be covered by `deriving`.
|
||||
@[always_inline]
|
||||
instance : Monad CoreM := let i := inferInstanceAs (Monad CoreM); { pure := i.pure, bind := i.bind }
|
||||
instance : Monad CoreM := let i : Monad CoreM := inferInstance; { pure := i.pure, bind := i.bind }
|
||||
|
||||
instance : Inhabited (CoreM α) where
|
||||
default := fun _ _ => throw default
|
||||
|
||||
@@ -224,7 +224,7 @@ instance : Coe JsonNumber RequestID := ⟨RequestID.num⟩
|
||||
| RequestID.num _, RequestID.str _ => true
|
||||
| _, _ /- str < *, num < null, null < null -/ => false
|
||||
|
||||
@[expose] def RequestID.ltProp : LT RequestID :=
|
||||
@[expose, implicit_reducible] def RequestID.ltProp : LT RequestID :=
|
||||
⟨fun a b => RequestID.lt a b = true⟩
|
||||
|
||||
instance : LT RequestID :=
|
||||
|
||||
@@ -7,6 +7,7 @@ module
|
||||
|
||||
prelude
|
||||
public import Lean.Meta.Diagnostics
|
||||
public import Lean.Meta.WrapInstance
|
||||
public import Lean.Elab.Open
|
||||
public import Lean.Elab.SetOption
|
||||
public import Lean.Elab.Eval
|
||||
@@ -313,6 +314,34 @@ private def mkSilentAnnotationIfHole (e : Expr) : TermElabM Expr := do
|
||||
return val
|
||||
| _ => panic! "resolveId? returned an unexpected expression"
|
||||
|
||||
@[builtin_term_elab Lean.Parser.Term.inferInstanceAs] def elabInferInstanceAs : TermElab := fun stx expectedType? => do
|
||||
-- The type argument is the last child (works for both `inferInstanceAs T` and `inferInstanceAs <| T`)
|
||||
let typeStx := stx[stx.getNumArgs - 1]!
|
||||
if !backward.inferInstanceAs.wrap.get (← getOptions) then
|
||||
return (← elabTerm (← `(_root_.inferInstanceAs $(⟨typeStx⟩))) expectedType?)
|
||||
|
||||
let some expectedType ← tryPostponeIfHasMVars? expectedType? |
|
||||
throwError (m!"`inferInstanceAs` failed, expected type contains metavariables{indentD expectedType?}" ++
|
||||
.note "`inferInstanceAs` requires full knowledge of the expected (\"target\") type to do its \
|
||||
instance translation. If you do not intend to transport instances between two types, \
|
||||
consider using `inferInstance` or `(inferInstance : expectedType)` instead.")
|
||||
let type ← withSynthesize (postpone := .yes) <| elabType typeStx
|
||||
-- Unify with expected type to resolve metavariables (e.g., `_` placeholders)
|
||||
discard <| isDefEq type expectedType
|
||||
let type ← instantiateMVars type
|
||||
-- Rebuild type with fresh synthetic mvars for instance-implicit args, so that
|
||||
-- synthesis is not influenced by the expected type's instance choices.
|
||||
let type ← abstractInstImplicitArgs type
|
||||
let inst ← synthInstance type
|
||||
let inst ← if backward.inferInstanceAs.wrap.get (← getOptions) then
|
||||
-- Wrap instance so its type matches the expected type exactly.
|
||||
let logCompileErrors := !(← read).isNoncomputableSection && !(← read).declName?.any (Lean.isNoncomputable (← getEnv))
|
||||
let isMeta := (← read).declName?.any (isMarkedMeta (← getEnv))
|
||||
withNewMCtxDepth <| wrapInstance inst expectedType (logCompileErrors := logCompileErrors) (isMeta := isMeta)
|
||||
else
|
||||
pure inst
|
||||
ensureHasType expectedType? inst
|
||||
|
||||
@[builtin_term_elab clear] def elabClear : TermElab := fun stx expectedType? => do
|
||||
let some (.fvar fvarId) ← isLocalIdent? stx[1]
|
||||
| throwErrorAt stx[1] "not in scope"
|
||||
@@ -383,11 +412,13 @@ private opaque evalFilePath (stx : Syntax) : TermElabM System.FilePath
|
||||
let name ← mkAuxDeclName `_private
|
||||
withoutExporting do
|
||||
let e ← elabTermAndSynthesize e expectedType?
|
||||
let compile := !(← read).isNoncomputableSection && !(← read).declName?.any (Lean.isNoncomputable (← getEnv))
|
||||
let e ← mkAuxDefinitionFor (compile := compile) name e
|
||||
if compile then
|
||||
-- Inline as changing visibility should not affect run time.
|
||||
setInlineAttribute name
|
||||
let e ← mkAuxDefinitionFor (compile := false) name e
|
||||
-- Inline as changing visibility should not affect run time.
|
||||
setInlineAttribute name
|
||||
if (← read).declName?.any (isMarkedMeta (← getEnv)) then
|
||||
modifyEnv (markMeta · name)
|
||||
let logCompileErrors := !(← read).isNoncomputableSection && !(← read).declName?.any (Lean.isNoncomputable (← getEnv))
|
||||
compileDecls (logErrors := logCompileErrors) #[name]
|
||||
return e
|
||||
else
|
||||
elabTerm e expectedType?
|
||||
|
||||
@@ -71,7 +71,7 @@ whole monad stack at every use site. May eventually be covered by `deriving`.
|
||||
Remark: see comment at TermElabM
|
||||
-/
|
||||
@[always_inline]
|
||||
instance : Monad CommandElabM := let i := inferInstanceAs (Monad CommandElabM); { pure := i.pure, bind := i.bind }
|
||||
instance : Monad CommandElabM := let i : Monad CommandElabM := inferInstance; { pure := i.pure, bind := i.bind }
|
||||
|
||||
/--
|
||||
Like `Core.tryCatchRuntimeEx`; runtime errors are generally used to abort term elaboration, so we do
|
||||
@@ -666,7 +666,8 @@ private def mkTermContext (ctx : Context) (s : State) : CommandElabM Term.Contex
|
||||
return {
|
||||
macroStack := ctx.macroStack
|
||||
sectionVars := sectionVars
|
||||
isNoncomputableSection := scope.isNoncomputable }
|
||||
isNoncomputableSection := scope.isNoncomputable
|
||||
isMetaSection := scope.isMeta }
|
||||
|
||||
/--
|
||||
Lift the `TermElabM` monadic action `x` into a `CommandElabM` monadic action.
|
||||
|
||||
@@ -8,6 +8,8 @@ module
|
||||
prelude
|
||||
public import Lean.Elab.App
|
||||
public import Lean.Elab.DeclNameGen
|
||||
import Lean.Compiler.NoncomputableAttr
|
||||
import Lean.Meta.WrapInstance
|
||||
|
||||
public section
|
||||
|
||||
@@ -173,7 +175,8 @@ We prevent `classStx` from referring to these local variables; instead it's expe
|
||||
This function can handle being run from within a nontrivial local context,
|
||||
and it uses `mkValueTypeClosure` to construct the final instance.
|
||||
-/
|
||||
def processDefDeriving (view : DerivingClassView) (decl : Expr) : TermElabM Unit := do
|
||||
def processDefDeriving (view : DerivingClassView) (decl : Expr) (isNoncomputable := false)
|
||||
(cmdRef? : Option Syntax := none) : TermElabM Unit := do
|
||||
let { cls := classStx, hasExpose := _ /- todo? -/, .. } := view
|
||||
let decl ← whnfCore decl
|
||||
let .const declName _ := decl.getAppFn
|
||||
@@ -185,7 +188,8 @@ def processDefDeriving (view : DerivingClassView) (decl : Expr) : TermElabM Unit
|
||||
let ConstantInfo.defnInfo info ← getConstInfo declName
|
||||
| throwError "Failed to delta derive instance, `{.ofConstName declName}` is not a definition."
|
||||
let value := info.value.beta decl.getAppArgs
|
||||
let result : Closure.MkValueTypeClosureResult ←
|
||||
let (result, preNormValue, instName) ←
|
||||
show TermElabM (Closure.MkValueTypeClosureResult × Expr × Name) from
|
||||
-- Assumption: users intend delta deriving to apply to the body of a definition, even if in the source code
|
||||
-- the function is written as a lambda expression.
|
||||
-- Furthermore, we don't use `forallTelescope` because users want to derive instances for monads.
|
||||
@@ -208,19 +212,47 @@ def processDefDeriving (view : DerivingClassView) (decl : Expr) : TermElabM Unit
|
||||
-- We don't reduce because of abbreviations such as `DecidableEq`
|
||||
forallTelescope classExpr fun _ classExpr => do
|
||||
let result ← mkInst classExpr declName decl value
|
||||
Closure.mkValueTypeClosure result.instType result.instVal (zetaDelta := true)
|
||||
-- Save the pre-wrapping value for the noncomputable check below,
|
||||
-- since `wrapInstance` may inline noncomputable constants.
|
||||
let preNormClosure ← Closure.mkValueTypeClosure result.instType result.instVal (zetaDelta := true)
|
||||
-- Compute instance name early so `wrapInstance` can use it for aux def naming.
|
||||
let env ← getEnv
|
||||
let mut instName := (← getCurrNamespace) ++ (← NameGen.mkBaseNameWithSuffix "inst" preNormClosure.type)
|
||||
instName ← liftMacroM <| mkUnusedBaseName instName
|
||||
if isPrivateName declName then
|
||||
instName := mkPrivateName env instName
|
||||
let isMeta := (← read).declName?.any (isMarkedMeta (← getEnv))
|
||||
let inst ← if backward.inferInstanceAs.wrap.get (← getOptions) then
|
||||
withDeclNameForAuxNaming instName <| withNewMCtxDepth <|
|
||||
wrapInstance result.instVal result.instType
|
||||
(logCompileErrors := false) -- covered by noncomputable check below
|
||||
(isMeta := isMeta)
|
||||
else
|
||||
pure result.instVal
|
||||
let closure ← Closure.mkValueTypeClosure result.instType inst (zetaDelta := true)
|
||||
return (closure, preNormClosure.value, instName)
|
||||
finally
|
||||
Core.setMessageLog (msgLog ++ (← Core.getMessageLog))
|
||||
let env ← getEnv
|
||||
let mut instName := (← getCurrNamespace) ++ (← NameGen.mkBaseNameWithSuffix "inst" result.type)
|
||||
-- We don't have a facility to let users override derived names, so make an unused name if needed.
|
||||
instName ← liftMacroM <| mkUnusedBaseName instName
|
||||
-- Make the instance private if the declaration is private.
|
||||
if isPrivateName declName then
|
||||
instName := mkPrivateName env instName
|
||||
let hints := ReducibilityHints.regular (getMaxHeight env result.value + 1)
|
||||
let decl ← mkDefinitionValInferringUnsafe instName result.levelParams.toList result.type result.value hints
|
||||
addAndCompile (logCompileErrors := !(← read).isNoncomputableSection) <| Declaration.defnDecl decl
|
||||
-- Pre-check: if the instance value depends on noncomputable definitions and the user didn't write
|
||||
-- `noncomputable`, give an actionable error with a `Try this:` suggestion.
|
||||
unless isNoncomputable || (← read).isNoncomputableSection || (← isProp result.type) do
|
||||
let noncompRef? := preNormValue.foldConsts none fun n acc =>
|
||||
acc <|> if Lean.isNoncomputable (asyncMode := .local) env n then some n else none
|
||||
if let some noncompRef := noncompRef? then
|
||||
if let some cmdRef := cmdRef? then
|
||||
if let some origText := cmdRef.reprint then
|
||||
let newText := (origText.replace "deriving instance " "deriving noncomputable instance ").trimAscii
|
||||
logInfoAt cmdRef m!"Try this: {newText}"
|
||||
throwError "failed to derive instance because it depends on \
|
||||
`{.ofConstName noncompRef}`, which is noncomputable"
|
||||
if isNoncomputable || (← read).isNoncomputableSection then
|
||||
addDecl <| Declaration.defnDecl decl
|
||||
modifyEnv (addNoncomputable · instName)
|
||||
else
|
||||
addAndCompile <| Declaration.defnDecl decl
|
||||
trace[Elab.Deriving] "Derived instance `{.ofConstName instName}`"
|
||||
registerInstance instName AttributeKind.global (eval_prio default)
|
||||
addDeclarationRangesFromSyntax instName (← getRef)
|
||||
@@ -284,8 +316,8 @@ def DerivingClassView.applyHandlers (view : DerivingClassView) (declNames : Arra
|
||||
withRef view.ref do
|
||||
applyDerivingHandlers (setExpose := view.hasExpose) (← liftCoreM <| view.getClassName) declNames
|
||||
|
||||
private def elabDefDeriving (classes : Array DerivingClassView) (decls : Array Syntax) :
|
||||
CommandElabM Unit := runTermElabM fun _ => do
|
||||
private def elabDefDeriving (classes : Array DerivingClassView) (decls : Array Syntax)
|
||||
(isNoncomputable := false) (cmdRef? : Option Syntax := none) : CommandElabM Unit := runTermElabM fun _ => do
|
||||
for decl in decls do
|
||||
withRef decl <| withLogging do
|
||||
let declExpr ←
|
||||
@@ -304,11 +336,12 @@ private def elabDefDeriving (classes : Array DerivingClassView) (decls : Array S
|
||||
for cls in classes do
|
||||
withLogging do
|
||||
withTraceNode `Elab.Deriving (fun _ => return m!"running delta deriving handler for `{cls.cls}` and definition `{declExpr}`") do
|
||||
Term.processDefDeriving cls declExpr
|
||||
Term.processDefDeriving cls declExpr (isNoncomputable := isNoncomputable) (cmdRef? := cmdRef?)
|
||||
|
||||
|
||||
@[builtin_command_elab «deriving»] def elabDeriving : CommandElab
|
||||
| `(deriving instance $[$classes],* for $[$decls],*) => do
|
||||
| stx@`(deriving $[noncomputable%$ncTk?]? instance $[$classes],* for $[$decls],*) => do
|
||||
let isNoncomputable := ncTk?.isSome
|
||||
let classes ← liftCoreM <| classes.mapM DerivingClassView.ofSyntax
|
||||
let decls : Array Syntax := decls
|
||||
if decls.all Syntax.isIdent then
|
||||
@@ -316,13 +349,18 @@ private def elabDefDeriving (classes : Array DerivingClassView) (decls : Array S
|
||||
-- If any of the declarations are definitions, then we commit to delta deriving.
|
||||
let infos ← declNames.mapM getConstInfo
|
||||
if infos.any (·.isDefinition) then
|
||||
elabDefDeriving classes decls
|
||||
elabDefDeriving classes decls (isNoncomputable := isNoncomputable) (cmdRef? := stx)
|
||||
else
|
||||
-- Otherwise, we commit to using deriving handlers.
|
||||
for cls in classes do
|
||||
cls.applyHandlers declNames
|
||||
if isNoncomputable then
|
||||
withScope (fun sc => { sc with isNoncomputable := true }) do
|
||||
for cls in classes do
|
||||
cls.applyHandlers declNames
|
||||
else
|
||||
for cls in classes do
|
||||
cls.applyHandlers declNames
|
||||
else
|
||||
elabDefDeriving classes decls
|
||||
elabDefDeriving classes decls (isNoncomputable := isNoncomputable) (cmdRef? := stx)
|
||||
| _ => throwUnsupportedSyntax
|
||||
|
||||
builtin_initialize
|
||||
|
||||
@@ -19,11 +19,12 @@ private def deriveTypeNameInstance (declNames : Array Name) : CommandElabM Bool
|
||||
let cinfo ← getConstInfo declName
|
||||
unless cinfo.levelParams.isEmpty do
|
||||
throwError m!"{.ofConstName declName} has universe level parameters"
|
||||
elabCommand <| ← withFreshMacroScope `(
|
||||
unsafe def instImpl : TypeName @$(mkCIdent declName) := .mk _ $(quote declName)
|
||||
@[implemented_by instImpl] opaque inst : TypeName @$(mkCIdent declName)
|
||||
instance : TypeName @$(mkCIdent declName) := inst
|
||||
)
|
||||
withScope (fun scope => { scope with opts := scope.opts.setBool `warn.classDefReducibility false }) do
|
||||
elabCommand <| ← withFreshMacroScope `(
|
||||
unsafe def instImpl : TypeName @$(mkCIdent declName) := .mk _ $(quote declName)
|
||||
@[implemented_by instImpl] opaque inst : TypeName @$(mkCIdent declName)
|
||||
instance : TypeName @$(mkCIdent declName) := inst
|
||||
)
|
||||
return true
|
||||
|
||||
initialize
|
||||
|
||||
@@ -7,7 +7,7 @@ module
|
||||
prelude
|
||||
|
||||
public import Lean.Elab.DocString
|
||||
import Lean.Elab.DocString.Builtin.Parsing
|
||||
public import Lean.Elab.DocString.Builtin.Parsing
|
||||
|
||||
namespace Lean.Doc
|
||||
open Lean.Parser
|
||||
|
||||
@@ -1184,6 +1184,11 @@ private def checkAllDeclNamesDistinct (preDefs : Array PreDefinition) : TermElab
|
||||
structure AsyncBodyInfo where
|
||||
deriving TypeName
|
||||
|
||||
register_builtin_option warn.classDefReducibility : Bool := {
|
||||
defValue := true
|
||||
descr := "warn when a `def` of class type is not marked `@[reducible]` or `@[implicit_reducible]`"
|
||||
}
|
||||
|
||||
register_builtin_option warn.exposeOnPrivate : Bool := {
|
||||
defValue := true
|
||||
descr := "warn about uses of `@[expose]` on private declarations"
|
||||
@@ -1225,9 +1230,11 @@ where
|
||||
-- Now that we have elaborated types, default data instances to `[implicit_reducible]`. This
|
||||
-- should happen before attribute application as `[instance]` will check for it.
|
||||
for header in headers do
|
||||
if header.kind == .instance && !header.modifiers.anyAttr (·.name matches `reducible | `irreducible) then
|
||||
if !(← isProp header.type) then
|
||||
setReducibilityStatus header.declName .implicitReducible
|
||||
-- TODO: remove `instance_reducible once the alias is deprecated
|
||||
if !header.modifiers.anyAttr (·.name matches `reducible | `implicit_reducible | `instance_reducible | `irreducible) then
|
||||
if header.kind == .instance then
|
||||
if !(← isProp header.type) then
|
||||
setReducibilityStatus header.declName .implicitReducible
|
||||
|
||||
if let (#[view], #[declId]) := (views, expandedDeclIds) then
|
||||
if Elab.async.get (← getOptions) && view.kind.isTheorem &&
|
||||
@@ -1237,6 +1244,18 @@ where
|
||||
elabAsync headers[0]! view declId
|
||||
else elabSync headers
|
||||
else elabSync headers
|
||||
|
||||
-- Warn about class-typed `def`s that aren't marked with a reducibility attribute.
|
||||
-- This check runs after elaboration so that attributes applied by other attributes
|
||||
-- (e.g. `to_additive (attr := implicit_reducible)`) are accounted for.
|
||||
for header in headers do
|
||||
if header.kind == .def then
|
||||
if warn.classDefReducibility.get (← getOptions) &&
|
||||
(← isClass? header.type).isSome /-TODO-/ &&
|
||||
!header.type.getForallBody.getAppFn.constName? matches ``Decidable | ``DecidableEq | ``Setoid then
|
||||
let status ← getReducibilityStatus header.declName
|
||||
unless status matches .reducible | .implicitReducible | .irreducible do
|
||||
logWarning m!"Definition `{header.declName}` of class type must be marked with `@[reducible]` or `@[implicit_reducible]`"
|
||||
for view in views, declId in expandedDeclIds do
|
||||
-- NOTE: this should be the full `ref`, and thus needs to be done after any snapshotting
|
||||
-- that depends only on a part of the ref
|
||||
|
||||
@@ -10,6 +10,7 @@ public import Lean.Compiler.NoncomputableAttr
|
||||
public import Lean.Util.NumApps
|
||||
public import Lean.Meta.Eqns
|
||||
public import Lean.Elab.RecAppSyntax
|
||||
public import Lean.Meta.WrapInstance
|
||||
public import Lean.Elab.DefView
|
||||
|
||||
public section
|
||||
|
||||
@@ -56,7 +56,7 @@ def unfoldLHS (declName : Name) (mvarId : MVarId) : MetaM MVarId := mvarId.withC
|
||||
deltaLHS mvarId
|
||||
|
||||
private partial def mkEqnProof (declName : Name) (type : Expr) : MetaM Expr := do
|
||||
withTraceNode `Elab.definition.eqns (return m!"{exceptEmoji ·} proving:{indentExpr type}") do
|
||||
withTraceNode `Elab.definition.eqns (fun _ => return m!"proving:{indentExpr type}") do
|
||||
withNewMCtxDepth do
|
||||
let main ← mkFreshExprSyntheticOpaqueMVar type
|
||||
let (_, mvarId) ← main.mvarId!.intros
|
||||
@@ -78,7 +78,7 @@ private partial def mkEqnProof (declName : Name) (type : Expr) : MetaM Expr := d
|
||||
recursion and structural recursion can and should use this too.
|
||||
-/
|
||||
go (mvarId : MVarId) : MetaM Unit := do
|
||||
withTraceNode `Elab.definition.eqns (return m!"{exceptEmoji ·} step:\n{MessageData.ofGoal mvarId}") do
|
||||
withTraceNode `Elab.definition.eqns (fun _ => return m!"step:\n{MessageData.ofGoal mvarId}") do
|
||||
if (← tryURefl mvarId) then
|
||||
return ()
|
||||
else if (← tryContradiction mvarId) then
|
||||
|
||||
@@ -118,7 +118,7 @@ private def withBelowDict [Inhabited α] (below : Expr) (numIndParams : Nat)
|
||||
The dictionary is built using the `PProd` (`And` for inductive predicates).
|
||||
We keep searching it until we find `C recArg`, where `C` is the auxiliary fresh variable created at `withBelowDict`. -/
|
||||
partial def toBelow (below : Expr) (numIndParams : Nat) (positions : Positions) (fnIndex : Nat) (recArg : Expr) : MetaM Expr := do
|
||||
withTraceNode `Elab.definition.structural (return m!"{exceptEmoji ·} searching IH for {recArg} in {←inferType below}") do
|
||||
withTraceNode `Elab.definition.structural (fun _ => return m!"searching IH for {recArg} in {←inferType below}") do
|
||||
withBelowDict below numIndParams positions fun Cs belowDict =>
|
||||
toBelowAux Cs[fnIndex]! belowDict recArg below
|
||||
|
||||
|
||||
@@ -73,7 +73,7 @@ Creates the proof of the unfolding theorem for `declName` with type `type`. It
|
||||
is solved using `rfl` or `contradiction`.
|
||||
-/
|
||||
partial def mkProof (declName : Name) (type : Expr) : MetaM Expr := do
|
||||
withTraceNode `Elab.definition.structural.eqns (return m!"{exceptEmoji ·} proving:{indentExpr type}") do
|
||||
withTraceNode `Elab.definition.structural.eqns (fun _ => return m!"proving:{indentExpr type}") do
|
||||
prependError m!"failed to generate equational theorem for `{.ofConstName declName}`" do
|
||||
withNewMCtxDepth do
|
||||
let main ← mkFreshExprSyntheticOpaqueMVar type
|
||||
@@ -83,7 +83,7 @@ partial def mkProof (declName : Name) (type : Expr) : MetaM Expr := do
|
||||
instantiateMVars main
|
||||
where
|
||||
goUnfold (mvarId : MVarId) : MetaM Unit := do
|
||||
withTraceNode `Elab.definition.structural.eqns (return m!"{exceptEmoji ·} goUnfold:\n{MessageData.ofGoal mvarId}") do
|
||||
withTraceNode `Elab.definition.structural.eqns (fun _ => return m!"goUnfold:\n{MessageData.ofGoal mvarId}") do
|
||||
let mvarId' ← mvarId.withContext do
|
||||
-- This should now be headed by `.brecOn`
|
||||
let goal ← mvarId.getType
|
||||
@@ -110,7 +110,7 @@ where
|
||||
go mvarId'
|
||||
|
||||
go (mvarId : MVarId) : MetaM Unit := do
|
||||
withTraceNode `Elab.definition.structural.eqns (return m!"{exceptEmoji ·} step:\n{MessageData.ofGoal mvarId}") do
|
||||
withTraceNode `Elab.definition.structural.eqns (fun _ => return m!"step:\n{MessageData.ofGoal mvarId}") do
|
||||
if (← tryURefl mvarId) then
|
||||
trace[Elab.definition.structural.eqns] "tryURefl succeeded"
|
||||
return ()
|
||||
|
||||
@@ -53,7 +53,7 @@ So we create a unfold equation generator that aliases an existing private `eq_de
|
||||
wherever the current module expects it.
|
||||
-/
|
||||
def copyPrivateUnfoldTheorem : GetUnfoldEqnFn := fun declName => do
|
||||
withTraceNode `ReservedNameAction (pure m!"{exceptOptionEmoji ·} copyPrivateUnfoldTheorem running for {declName}") do
|
||||
withTraceNode `ReservedNameAction (fun _ => pure m!"copyPrivateUnfoldTheorem running for {declName}") do
|
||||
let name := mkEqLikeNameFor (← getEnv) declName unfoldThmSuffix
|
||||
if let some mod ← findModuleOf? declName then
|
||||
let unfoldName' := mkPrivateNameCore mod (.str (privateToUserName declName) unfoldThmSuffix)
|
||||
|
||||
@@ -1572,6 +1572,16 @@ def elabStructureCommand : InductiveElabDescr where
|
||||
if fieldInfo.kind.isInCtor then
|
||||
enableRealizationsForConst fieldInfo.declName
|
||||
if view.isClass then
|
||||
-- Set implicitReducible on subobject projections to class parents.
|
||||
-- mkProjections defers reducibility to addParentInstances, but
|
||||
-- addParentInstances only handles direct parents. Subobject fields
|
||||
-- for non-direct parents (grandparents promoted to constructor
|
||||
-- subobjects during diamond flattening) also need implicitReducible
|
||||
-- to be unfoldable at .instances transparency.
|
||||
for fieldInfo in fieldInfos do
|
||||
if let .subobject parentName := fieldInfo.kind then
|
||||
if isClass (← getEnv) parentName then
|
||||
setReducibilityStatus fieldInfo.declName .implicitReducible
|
||||
addParentInstances parentInfos
|
||||
-- Add field docstrings here (after @[class] attribute is applied)
|
||||
-- so that Verso docstrings can use the class.
|
||||
|
||||
@@ -63,7 +63,7 @@ See comment at `Monad TermElabM`
|
||||
-/
|
||||
@[always_inline]
|
||||
instance : Monad TacticM :=
|
||||
let i := inferInstanceAs (Monad TacticM);
|
||||
let i : Monad TacticM := inferInstance;
|
||||
{ pure := i.pure, bind := i.bind }
|
||||
|
||||
instance : Inhabited (TacticM α) where
|
||||
|
||||
@@ -155,7 +155,7 @@ where
|
||||
.hint' m!"Reduction got stuck on `▸` ({.ofConstName ``Eq.rec}), \
|
||||
which suggests that one of the `{.ofConstName ``Decidable}` instances is defined using tactics such as `rw` or `simp`. \
|
||||
To avoid tactics, make use of functions such as \
|
||||
`{.ofConstName ``inferInstanceAs}` or `{.ofConstName ``decidable_of_decidable_of_iff}` \
|
||||
`{.ofConstName `inferInstanceAs}` or `{.ofConstName ``decidable_of_decidable_of_iff}` \
|
||||
to alter a proposition."
|
||||
else if reason.isAppOf ``Classical.choice then
|
||||
.hint' m!"Reduction got stuck on `{.ofConstName ``Classical.choice}`, \
|
||||
|
||||
@@ -64,7 +64,7 @@ def SavedState.restore (b : SavedState) (restoreInfo := false) : GrindTacticM Un
|
||||
|
||||
@[always_inline]
|
||||
instance : Monad GrindTacticM :=
|
||||
let i := inferInstanceAs (Monad GrindTacticM)
|
||||
let i : Monad GrindTacticM := inferInstance
|
||||
{ pure := i.pure, bind := i.bind }
|
||||
|
||||
instance : Inhabited (GrindTacticM α) where
|
||||
|
||||
@@ -38,7 +38,7 @@ def proveEqUsing (s : SimpTheorems) (a b : Expr) : MetaM (Option Simp.Result) :=
|
||||
|
||||
/-- Proves `a = b` by simplifying using move and squash lemmas. -/
|
||||
def proveEqUsingDown (a b : Expr) : MetaM (Option Simp.Result) := do
|
||||
withTraceNode `Tactic.norm_cast (return m!"{exceptOptionEmoji ·} proving: {← mkEq a b}") do
|
||||
withTraceNode `Tactic.norm_cast (fun _ => return m!"proving: {← mkEq a b}") do
|
||||
proveEqUsing (← normCastExt.down.getTheorems) a b
|
||||
|
||||
/-- Constructs the expression `(e : ty)`. -/
|
||||
@@ -97,9 +97,8 @@ def splittingProcedure (expr : Expr) : MetaM Simp.Result := do
|
||||
|
||||
let msg := m!"splitting {expr}"
|
||||
let msg
|
||||
| .error _ => return m!"{bombEmoji} {msg}"
|
||||
| .ok r => return if r.expr == expr then m!"{crossEmoji} {msg}" else
|
||||
m!"{checkEmoji} {msg} to {r.expr}"
|
||||
| .error _ => return msg
|
||||
| .ok r => return if r.expr == expr then msg else m!"{msg} to {r.expr}"
|
||||
withTraceNode `Tactic.norm_cast msg do
|
||||
|
||||
try
|
||||
@@ -140,7 +139,7 @@ Discharging function used during simplification in the "squash" step.
|
||||
-- TODO: normCast takes a list of expressions to use as lemmas for the discharger
|
||||
-- TODO: a tactic to print the results the discharger fails to prove
|
||||
def prove (e : Expr) : SimpM (Option Expr) := do
|
||||
withTraceNode `Tactic.norm_cast (return m!"{exceptOptionEmoji ·} discharging: {e}") do
|
||||
withTraceNode `Tactic.norm_cast (fun _ => return m!"discharging: {e}") do
|
||||
return (← findLocalDeclWithType? e).map mkFVar
|
||||
|
||||
/--
|
||||
|
||||
@@ -309,6 +309,8 @@ structure Context where
|
||||
heedElabAsElim : Bool := true
|
||||
/-- Noncomputable sections automatically add the `noncomputable` modifier to any declaration we cannot generate code for. -/
|
||||
isNoncomputableSection : Bool := false
|
||||
/-- `true` when inside a `meta section`. -/
|
||||
isMetaSection : Bool := false
|
||||
/-- When `true` we skip TC failures. We use this option when processing patterns. -/
|
||||
ignoreTCFailures : Bool := false
|
||||
/-- `true` when elaborating patterns. It affects how we elaborate named holes. -/
|
||||
@@ -371,7 +373,7 @@ whole monad stack at every use site. May eventually be covered by `deriving`.
|
||||
-/
|
||||
@[always_inline]
|
||||
instance : Monad TermElabM :=
|
||||
let i := inferInstanceAs (Monad TermElabM)
|
||||
let i : Monad TermElabM := inferInstance
|
||||
{ pure := i.pure, bind := i.bind }
|
||||
|
||||
open Meta
|
||||
|
||||
@@ -28,6 +28,15 @@ namespace KeyedDeclsAttribute
|
||||
-- could be a parameter as well, but right now it's all names
|
||||
abbrev Key := Name
|
||||
|
||||
def evalIdentKey (stx : Syntax) : AttrM Key := do
|
||||
let stx ← Attribute.Builtin.getIdent stx
|
||||
let kind := stx.getId
|
||||
if (← getEnv).contains kind then
|
||||
recordExtraModUseFromDecl (isMeta := false) kind
|
||||
if (← Elab.getInfoState).enabled then
|
||||
Elab.addConstInfo stx kind none
|
||||
pure kind
|
||||
|
||||
/--
|
||||
`KeyedDeclsAttribute` definition.
|
||||
|
||||
@@ -41,14 +50,7 @@ structure Def (γ : Type) where
|
||||
descr : String
|
||||
valueTypeName : Name
|
||||
/-- Convert `Syntax` into a `Key`, the default implementation expects an identifier. -/
|
||||
evalKey (builtin : Bool) (stx : Syntax) : AttrM Key := private_decl% (do
|
||||
let stx ← Attribute.Builtin.getIdent stx
|
||||
let kind := stx.getId
|
||||
if (← getEnv).contains kind then
|
||||
recordExtraModUseFromDecl (isMeta := false) kind
|
||||
if (← Elab.getInfoState).enabled then
|
||||
Elab.addConstInfo stx kind none
|
||||
pure kind)
|
||||
evalKey (builtin : Bool) (stx : Syntax) : AttrM Key := evalIdentKey stx
|
||||
onAdded (builtin : Bool) (declName : Name) (key : Key) : AttrM Unit := pure ()
|
||||
deriving Inhabited
|
||||
|
||||
|
||||
@@ -129,7 +129,7 @@ def hasParam (u : Level) : Bool :=
|
||||
|
||||
end Level
|
||||
|
||||
@[expose] def levelZero :=
|
||||
@[expose, implicit_reducible] def levelZero :=
|
||||
Level.zero
|
||||
|
||||
def mkLevelMVar (mvarId : LMVarId) :=
|
||||
@@ -213,7 +213,7 @@ def isAlwaysZero : Level → Bool
|
||||
| max l₁ l₂ => isAlwaysZero l₁ && isAlwaysZero l₂
|
||||
| imax _ l₂ => isAlwaysZero l₂
|
||||
|
||||
@[expose] def ofNat : Nat → Level
|
||||
@[expose, implicit_reducible] def ofNat : Nat → Level
|
||||
| 0 => levelZero
|
||||
| n+1 => mkLevelSucc (ofNat n)
|
||||
|
||||
|
||||
@@ -66,9 +66,29 @@ structure NamingContext where
|
||||
currNamespace : Name
|
||||
openDecls : List OpenDecl
|
||||
|
||||
/-- Structured result status of a trace node action, produced by `withTraceNode` and
|
||||
`withTraceNodeBefore` and included in the `TraceData` of trace messages. Either
|
||||
`.success` (✅️), `.failure` (❌️), or `.error` (💥️).
|
||||
|
||||
This is used both to render emojis in trace messages and to allow more
|
||||
robust inspection of trace logs via metaprogramming.
|
||||
|
||||
See also `Except.toTraceResult` for converting an `Except ε α` to a `TraceResult`. -/
|
||||
inductive TraceResult where
|
||||
/-- The traced action succeeded (✅️, `checkEmoji`). -/
|
||||
| success
|
||||
/-- The traced action failed (❌️, `crossEmoji`). -/
|
||||
| failure
|
||||
/-- An exception was thrown during the traced action (💥️, `bombEmoji`). -/
|
||||
| error
|
||||
deriving Inhabited, BEq, Repr
|
||||
|
||||
structure TraceData where
|
||||
/-- Trace class, e.g. `Elab.step`. -/
|
||||
cls : Name
|
||||
/-- Structured success/failure result set by `withTraceNode`/`withTraceNodeBefore`.
|
||||
`none` for trace nodes not created by these functions (e.g. `addTrace`, diagnostic nodes). -/
|
||||
result? : Option TraceResult := none
|
||||
/-- Start time in seconds; 0 if unknown to avoid `Option` allocation. -/
|
||||
startTime : Float := 0
|
||||
/-- Stop time in seconds; 0 if unknown to avoid `Option` allocation. -/
|
||||
|
||||
@@ -27,6 +27,7 @@ public import Lean.Meta.Match
|
||||
public import Lean.Meta.ReduceEval
|
||||
public import Lean.Meta.Closure
|
||||
public import Lean.Meta.AbstractNestedProofs
|
||||
public import Lean.Meta.WrapInstance
|
||||
public import Lean.Meta.LetToHave
|
||||
public import Lean.Meta.ForEachExpr
|
||||
public import Lean.Meta.Transform
|
||||
|
||||
@@ -87,8 +87,13 @@ partial def visit (e : Expr) : M Expr := do
|
||||
lctx := lctx.modifyLocalDecl xFVarId fun _ => localDecl
|
||||
withLCtx lctx localInstances k
|
||||
checkCache { val := e : ExprStructEq } fun _ => do
|
||||
if (← isNonTrivialProof e) then
|
||||
/- Ensure proofs nested in type are also abstracted -/
|
||||
if (← isNonTrivialProof e) && !e.hasSorry then
|
||||
/- Ensure proofs nested in type are also abstracted.
|
||||
We skip abstraction for proofs containing `sorry` to avoid generating extra
|
||||
"declaration uses sorry" warnings for auxiliary theorems: one per abstracted proof
|
||||
instead of a single warning for the main declaration. Additionally, the `zetaDelta`
|
||||
expansion in `mkAuxTheorem` can inline let-bound sorry values, causing warnings
|
||||
even for proofs that only transitively reference sorry-containing definitions. -/
|
||||
abstractProof e (← read).cache visit
|
||||
else match e with
|
||||
| .lam ..
|
||||
|
||||
@@ -341,8 +341,7 @@ private def mkFun (constName : Name) : MetaM (Expr × Expr) := do
|
||||
|
||||
private def withAppBuilderTrace [ToMessageData α] [ToMessageData β]
|
||||
(f : α) (xs : β) (k : MetaM Expr) : MetaM Expr :=
|
||||
let emoji | .ok .. => checkEmoji | .error .. => crossEmoji
|
||||
withTraceNode `Meta.appBuilder (return m!"{emoji ·} f: {f}, xs: {xs}") do
|
||||
withTraceNode `Meta.appBuilder (fun _ => return m!"f: {f}, xs: {xs}") do
|
||||
try
|
||||
let res ← k
|
||||
trace[Meta.appBuilder.result] res
|
||||
|
||||
@@ -564,7 +564,7 @@ abbrev MetaM := ReaderT Context $ StateRefT State CoreM
|
||||
-- Make the compiler generate specialized `pure`/`bind` so we do not have to optimize through the
|
||||
-- whole monad stack at every use site. May eventually be covered by `deriving`.
|
||||
@[always_inline]
|
||||
instance : Monad MetaM := let i := inferInstanceAs (Monad MetaM); { pure := i.pure, bind := i.bind }
|
||||
instance : Monad MetaM := let i : Monad MetaM := inferInstance; { pure := i.pure, bind := i.bind }
|
||||
|
||||
instance : Inhabited (MetaM α) where
|
||||
default := fun _ _ => default
|
||||
|
||||
@@ -329,8 +329,8 @@ where
|
||||
Throw an exception if `e` is not type correct.
|
||||
-/
|
||||
def check (e : Expr) : MetaM Unit :=
|
||||
withTraceNode `Meta.check (fun res =>
|
||||
return m!"{if res.isOk then checkEmoji else crossEmoji} {e}") do
|
||||
withTraceNode `Meta.check (fun _ =>
|
||||
return m!"{e}") do
|
||||
try
|
||||
withTransparency TransparencyMode.all $ checkAux e
|
||||
catch ex =>
|
||||
|
||||
@@ -431,7 +431,8 @@ end Closure
|
||||
A "closure" is computed, and a term of the form `name.{u_1 ... u_n} t_1 ... t_m` is
|
||||
returned where `u_i`s are universe parameters and metavariables `type` and `value` depend on,
|
||||
and `t_j`s are free and meta variables `type` and `value` depend on. -/
|
||||
def mkAuxDefinition (name : Name) (type : Expr) (value : Expr) (zetaDelta : Bool := false) (compile : Bool := true) : MetaM Expr := do
|
||||
def mkAuxDefinition (name : Name) (type : Expr) (value : Expr) (zetaDelta : Bool := false)
|
||||
(compile : Bool := true) (logCompileErrors : Bool := true) : MetaM Expr := do
|
||||
let result ← Closure.mkValueTypeClosure type value zetaDelta
|
||||
let env ← getEnv
|
||||
let hints := ReducibilityHints.regular (getMaxHeight env result.value + 1)
|
||||
@@ -439,14 +440,16 @@ def mkAuxDefinition (name : Name) (type : Expr) (value : Expr) (zetaDelta : Bool
|
||||
result.type result.value hints)
|
||||
addDecl decl
|
||||
if compile then
|
||||
compileDecl decl
|
||||
compileDecl decl (logErrors := logCompileErrors)
|
||||
return mkAppN (mkConst name result.levelArgs.toList) result.exprArgs
|
||||
|
||||
/-- Similar to `mkAuxDefinition`, but infers the type of `value`. -/
|
||||
def mkAuxDefinitionFor (name : Name) (value : Expr) (zetaDelta : Bool := false) (compile := true) : MetaM Expr := do
|
||||
def mkAuxDefinitionFor (name : Name) (value : Expr) (zetaDelta : Bool := false)
|
||||
(compile := true) (logCompileErrors : Bool := true) : MetaM Expr := do
|
||||
let type ← inferType value
|
||||
let type := type.headBeta
|
||||
mkAuxDefinition name type value (zetaDelta := zetaDelta) (compile := compile)
|
||||
(logCompileErrors := logCompileErrors)
|
||||
|
||||
/--
|
||||
Create an auxiliary theorem with the given name, type and value. It is similar to `mkAuxDefinition`.
|
||||
|
||||
@@ -304,7 +304,7 @@ def getUnfoldEqnFor? (declName : Name) (nonRec := false) : MetaM (Option Name) :
|
||||
|
||||
builtin_initialize
|
||||
registerReservedNameAction fun name => do
|
||||
withTraceNode `ReservedNameAction (pure m!"{exceptBoolEmoji ·} Lean.Meta.Eqns reserved name action for {name}") do
|
||||
withTraceNode `ReservedNameAction (fun _ => pure m!"Lean.Meta.Eqns reserved name action for {name}") do
|
||||
if let some (declName, suffix) := declFromEqLikeName (← getEnv) name then
|
||||
if name == mkEqLikeNameFor (← getEnv) declName suffix then
|
||||
if isEqnReservedNameSuffix suffix then
|
||||
|
||||
@@ -319,7 +319,7 @@ the first `nrealParams` are parameters and the remaining are motives.
|
||||
public partial def mkBelowMatcher (matcherApp : MatcherApp) (belowParams : Array Expr) (nrealParams : Nat)
|
||||
(ctx : RecursionContext) (transformAlt : RecursionContext → Expr → MetaM Expr) :
|
||||
MetaM (Option (Expr × MetaM Unit)) :=
|
||||
withTraceNode `Meta.IndPredBelow.match (return m!"{exceptEmoji ·} {matcherApp.toExpr} and {belowParams}") do
|
||||
withTraceNode `Meta.IndPredBelow.match (fun _ => return m!"{matcherApp.toExpr} and {belowParams}") do
|
||||
let mut input ← getMkMatcherInputInContext matcherApp (unfoldNamed := false)
|
||||
let mut discrs := matcherApp.discrs
|
||||
let mut matchTypeAdd := #[] -- #[(discrIdx, ), ...]
|
||||
@@ -448,7 +448,7 @@ where
|
||||
StateRefT (Array NewDecl) MetaM (Pattern × Pattern) := do
|
||||
match originalPattern with
|
||||
| .ctor ctorName us params fields =>
|
||||
withTraceNode `Meta.IndPredBelow.match (return m!"{exceptEmoji ·} pattern {← originalPattern.toExpr} to {belowIndName}") do
|
||||
withTraceNode `Meta.IndPredBelow.match (fun _ => return m!"pattern {← originalPattern.toExpr} to {belowIndName}") do
|
||||
let ctorInfo ← getConstInfoCtor ctorName
|
||||
let shortCtorName := ctorName.replacePrefix ctorInfo.induct .anonymous
|
||||
let belowCtor ← getConstInfoCtor (belowIndName ++ shortCtorName)
|
||||
|
||||
@@ -107,7 +107,7 @@ def mkInjectiveTheoremNameFor (ctorName : Name) : Name :=
|
||||
|
||||
private def mkInjectiveTheorem (ctorVal : ConstructorVal) : MetaM Unit := do
|
||||
let name := mkInjectiveTheoremNameFor ctorVal.name
|
||||
withTraceNode `Meta.injective (msg := (return m!"{exceptEmoji ·} generating `{name}`")) do
|
||||
withTraceNode `Meta.injective (msg := (fun _ => return m!"generating `{name}`")) do
|
||||
let some type ← mkInjectiveTheoremType? ctorVal
|
||||
| return ()
|
||||
trace[Meta.injective] "type: {type}"
|
||||
@@ -164,7 +164,7 @@ private def mkInjectiveEqTheoremValue (ctorVal : ConstructorVal) (targetType : E
|
||||
|
||||
private def mkInjectiveEqTheorem (ctorVal : ConstructorVal) : MetaM Unit := do
|
||||
let name := mkInjectiveEqTheoremNameFor ctorVal.name
|
||||
withTraceNode `Meta.injective (msg := (return m!"{exceptEmoji ·} generating `{name}`")) do
|
||||
withTraceNode `Meta.injective (msg := (fun _ => return m!"generating `{name}`")) do
|
||||
let some type ← mkInjectiveEqTheoremType? ctorVal
|
||||
| return ()
|
||||
trace[Meta.injective] "type: {type}"
|
||||
@@ -186,7 +186,7 @@ register_builtin_option genInjectivity : Bool := {
|
||||
|
||||
def mkInjectiveTheorems (declName : Name) : MetaM Unit := do
|
||||
if (← getEnv).contains ``Eq.propIntro && genInjectivity.get (← getOptions) && !(← isInductivePredicate declName) then
|
||||
withTraceNode `Meta.injective (return m!"{exceptEmoji ·} {declName}") do
|
||||
withTraceNode `Meta.injective (fun _ => return m!"{declName}") do
|
||||
let info ← getConstInfoInduct declName
|
||||
unless info.isUnsafe do
|
||||
-- We need to reset the local context here because `solveEqOfCtorEq` uses
|
||||
|
||||
@@ -396,8 +396,8 @@ private partial def visitProj (e : Expr) (structName : Name) (idx : Nat) (struct
|
||||
return { expr := e.updateProj! struct, type? := lastFieldTy }
|
||||
|
||||
private partial def visit (e : Expr) : M Result := do
|
||||
withTraceNode `Meta.letToHave.debug (fun res =>
|
||||
return m!"{if res.isOk then checkEmoji else crossEmoji} visit (check := {(← read).check}){indentExpr e}") do
|
||||
withTraceNode `Meta.letToHave.debug (fun _ =>
|
||||
return m!"visit (check := {(← read).check}){indentExpr e}") do
|
||||
match e with
|
||||
| .bvar .. => throwError "unexpected bound variable {e}"
|
||||
| .fvar .. => visitFVar e
|
||||
@@ -415,8 +415,8 @@ end
|
||||
|
||||
private def main (e : Expr) : MetaM Expr := do
|
||||
Prod.fst <$> withTraceNode `Meta.letToHave (fun
|
||||
| .ok (_, msg) => pure m!"{checkEmoji} {msg}"
|
||||
| .error ex => pure m!"{crossEmoji} {ex.toMessageData}") do
|
||||
| .ok (_, msg) => pure msg
|
||||
| .error ex => pure ex.toMessageData) do
|
||||
if hasDepLet e then
|
||||
withTrackingZetaDelta <|
|
||||
withTransparency TransparencyMode.all <|
|
||||
|
||||
@@ -132,7 +132,7 @@ mutual
|
||||
partial def isLevelDefEqAuxImpl : Level → Level → MetaM Bool
|
||||
| Level.succ lhs, Level.succ rhs => isLevelDefEqAux lhs rhs
|
||||
| lhs, rhs =>
|
||||
withTraceNode `Meta.isLevelDefEq (return m!"{exceptBoolEmoji ·} {lhs} =?= {rhs}") do
|
||||
withTraceNode `Meta.isLevelDefEq (fun _ => return m!"{lhs} =?= {rhs}") do
|
||||
if lhs.getLevelOffset == rhs.getLevelOffset then
|
||||
return lhs.getOffset == rhs.getOffset
|
||||
else
|
||||
|
||||
@@ -431,7 +431,7 @@ private def isCtorIdxHasNotBit? (e : Expr) : Option FVarId := do
|
||||
|
||||
private partial def contradiction (mvarId : MVarId) : MetaM Bool := do
|
||||
mvarId.withContext do
|
||||
withTraceNode `Meta.Match.match (msg := (return m!"{exceptBoolEmoji ·} Match.contradiction")) do
|
||||
withTraceNode `Meta.Match.match (msg := (fun _ => return m!"Match.contradiction")) do
|
||||
trace[Meta.Match.match] m!"Match.contradiction:\n{mvarId}"
|
||||
if (← mvarId.contradictionCore {}) then
|
||||
trace[Meta.Match.match] "Contradiction found!"
|
||||
@@ -937,7 +937,7 @@ private def processFirstVarDone (p : Problem) : Problem :=
|
||||
private def tracedForM (xs : Array α) (process : α → StateRefT State MetaM Unit) : StateRefT State MetaM Unit :=
|
||||
if xs.size > 1 then
|
||||
for x in xs, i in [:xs.size] do
|
||||
withTraceNode `Meta.Match.match (msg := (return m!"{exceptEmoji ·} subgoal {i+1}/{xs.size}")) do
|
||||
withTraceNode `Meta.Match.match (msg := (fun _ => return m!"subgoal {i+1}/{xs.size}")) do
|
||||
process x
|
||||
else
|
||||
for x in xs do
|
||||
@@ -1097,7 +1097,8 @@ def mkMatcherAuxDefinition (name : Name) (type : Expr) (value : Expr) (isSplitte
|
||||
unless isSplitter do
|
||||
modifyEnv fun env => matcherExt.modifyState env fun s => s.insert key name
|
||||
addMatcherInfo name mi
|
||||
setInlineAttribute name
|
||||
if compile then
|
||||
setInlineAttribute name
|
||||
enableRealizationsForConst name
|
||||
if compile then
|
||||
compileDecl decl
|
||||
|
||||
@@ -232,7 +232,7 @@ where go baseName splitterName := withConfig (fun c => { c with etaStruct := .no
|
||||
assert! matchInfo.altInfos == splitterAltInfos
|
||||
-- This match statement does not need a splitter, we can use itself for that.
|
||||
-- (We still have to generate a declaration to satisfy the realizable constant)
|
||||
addAndCompile (logCompileErrors := false) <| Declaration.defnDecl {
|
||||
let decl := Declaration.defnDecl {
|
||||
name := splitterName
|
||||
levelParams := constInfo.levelParams
|
||||
type := constInfo.type
|
||||
@@ -240,7 +240,9 @@ where go baseName splitterName := withConfig (fun c => { c with etaStruct := .no
|
||||
hints := .abbrev
|
||||
safety := .safe
|
||||
}
|
||||
addDecl decl
|
||||
setInlineAttribute splitterName
|
||||
compileDecl (logErrors := false) decl
|
||||
let result := { eqnNames, splitterName, splitterMatchInfo }
|
||||
registerMatchEqns matchDeclName result
|
||||
|
||||
|
||||
@@ -96,7 +96,7 @@ def rwMatcher (altIdx : Nat) (e : Expr) : MetaM Simp.Result := do
|
||||
return { expr := e }
|
||||
let eqnThm := eqns[altIdx]!
|
||||
try
|
||||
withTraceNode `Meta.Match.debug (pure m!"{exceptEmoji ·} rewriting with {.ofConstName eqnThm} in{indentExpr e}") do
|
||||
withTraceNode `Meta.Match.debug (fun _ => pure m!"rewriting with {.ofConstName eqnThm} in{indentExpr e}") do
|
||||
let eqProof := mkAppN (mkConst eqnThm e.getAppFn.constLevels!) e.getAppArgs
|
||||
let (hyps, _, eqType) ← forallMetaTelescope (← inferType eqProof)
|
||||
trace[Meta.Match.debug] "eqProof has type{indentExpr eqType}"
|
||||
|
||||
@@ -28,7 +28,7 @@ public def reduceSparseCasesOn (mvarId : MVarId) : MetaM (Array MVarId) := do
|
||||
lhs.withApp fun f xs => do
|
||||
let .const matchDeclName _ := f | throwError "Not a const application"
|
||||
let some sparseCasesOnInfo ← getSparseCasesOnInfo matchDeclName | throwError "Not a sparse casesOn application"
|
||||
withTraceNode `Meta.Match.matchEqs (msg := (return m!"{exceptEmoji ·} splitSparseCasesOn")) do
|
||||
withTraceNode `Meta.Match.matchEqs (msg := (fun _ => return m!"splitSparseCasesOn")) do
|
||||
if xs.size < sparseCasesOnInfo.arity then
|
||||
throwError "Not enough arguments for sparse casesOn application"
|
||||
let majorIdx := sparseCasesOnInfo.majorPos
|
||||
@@ -52,7 +52,7 @@ public def splitSparseCasesOn (mvarId : MVarId) : MetaM (Array MVarId) := do
|
||||
lhs.withApp fun f xs => do
|
||||
let .const matchDeclName _ := f | throwError "Not a const application"
|
||||
let some sparseCasesOnInfo ← getSparseCasesOnInfo matchDeclName | throwError "Not a sparse casesOn application"
|
||||
withTraceNode `Meta.Match.matchEqs (msg := (return m!"{exceptEmoji ·} splitSparseCasesOn")) do
|
||||
withTraceNode `Meta.Match.matchEqs (msg := (fun _ => return m!"splitSparseCasesOn")) do
|
||||
try
|
||||
trace[Meta.Match.matchEqs] "splitSparseCasesOn running on\n{mvarId}"
|
||||
if xs.size < sparseCasesOnInfo.arity then
|
||||
|
||||
@@ -351,8 +351,8 @@ def tryResolve (mvar : Expr) (inst : Instance) : MetaM (Option (MetavarContext
|
||||
let localInsts ← getLocalInstances
|
||||
forallTelescopeReducing mvarType fun xs mvarTypeBody => do
|
||||
let { subgoals, instVal, instTypeBody } ← getSubgoals lctx localInsts xs inst
|
||||
withTraceNode `Meta.synthInstance.tryResolve (withMCtx (← getMCtx) do
|
||||
return m!"{exceptOptionEmoji ·} {← instantiateMVars mvarTypeBody} ≟ {← instantiateMVars instTypeBody}") do
|
||||
withTraceNode `Meta.synthInstance.tryResolve (fun _ => do withMCtx (← getMCtx) do
|
||||
return m!"{← instantiateMVars mvarTypeBody} ≟ {← instantiateMVars instTypeBody}") do
|
||||
if (← isDefEq mvarTypeBody instTypeBody) then
|
||||
/-
|
||||
We set `etaReduce := true`.
|
||||
@@ -425,7 +425,7 @@ def addAnswer (cNode : ConsumerNode) : SynthM Unit := do
|
||||
trace[Meta.synthInstance.answer] "{crossEmoji} {← instantiateMVars (← inferType cNode.mvar)}{Format.line}(size: {cNode.size} ≥ {(← read).maxResultSize})"
|
||||
else
|
||||
withTraceNode `Meta.synthInstance.answer
|
||||
(fun _ => return m!"{checkEmoji} {← instantiateMVars (← inferType cNode.mvar)}") do
|
||||
(fun _ => return m!"{← instantiateMVars (← inferType cNode.mvar)}") do
|
||||
let answer ← mkAnswer cNode
|
||||
-- Remark: `answer` does not contain assignable or assigned metavariables.
|
||||
let key := cNode.key
|
||||
@@ -573,8 +573,8 @@ def generate : SynthM Unit := do
|
||||
modify fun s => { s with generatorStack := s.generatorStack.pop }
|
||||
return
|
||||
discard do withMCtx mctx do
|
||||
withTraceNode `Meta.synthInstance
|
||||
(return m!"{exceptOptionEmoji ·} apply {inst.val} to {← instantiateMVars (← inferType mvar)}") do
|
||||
withTraceNode `Meta.synthInstance.apply
|
||||
(fun _ => return m!"apply {inst.val} to {← instantiateMVars (← inferType mvar)}") do
|
||||
modifyTop fun gNode => { gNode with currInstanceIdx := idx }
|
||||
if let some (mctx, subgoals) ← tryResolve mvar inst then
|
||||
consume { key, mvar, subgoals, mctx, size := 0 }
|
||||
@@ -875,7 +875,7 @@ def synthInstanceCore? (type : Expr) (maxResultSize? : Option Nat := none) : Met
|
||||
let opts ← getOptions
|
||||
let maxResultSize := maxResultSize?.getD (synthInstance.maxSize.get opts)
|
||||
withTraceNode `Meta.synthInstance
|
||||
(return m!"{exceptOptionEmoji ·} {← instantiateMVars type}") do
|
||||
(fun _ => return m!"{← instantiateMVars type}") do
|
||||
withConfig (fun config => { config with isDefEqStuckEx := true, transparency := TransparencyMode.instances,
|
||||
foApprox := true, ctxApprox := true, constApprox := false, univApprox := false }) do
|
||||
withInTypeClassResolution do
|
||||
@@ -982,6 +982,7 @@ register_builtin_option trace.Meta.synthInstance : Bool := {
|
||||
|
||||
builtin_initialize
|
||||
registerTraceClass `Meta.synthPending
|
||||
registerTraceClass `Meta.synthInstance.apply (inherited := true)
|
||||
registerTraceClass `Meta.synthInstance.instances (inherited := true)
|
||||
registerTraceClass `Meta.synthInstance.tryResolve (inherited := true)
|
||||
registerTraceClass `Meta.synthInstance.answer (inherited := true)
|
||||
|
||||
@@ -110,25 +110,25 @@ private def run (goals : List MVarId) (n : Nat) (curr acc : List MVarId) : MetaM
|
||||
cfg.proc goals curr
|
||||
catch e =>
|
||||
withTraceNode trace
|
||||
(return m!"{exceptEmoji ·} BacktrackConfig.proc failed: {e.toMessageData}") do
|
||||
(fun _ => return m!"BacktrackConfig.proc failed: {e.toMessageData}") do
|
||||
throw e
|
||||
match procResult? with
|
||||
| some curr' => run goals n curr' acc
|
||||
| none =>
|
||||
match curr with
|
||||
-- If there are no active goals, return the accumulated goals.
|
||||
| [] => withTraceNode trace (return m!"{exceptEmoji ·} success!") do
|
||||
| [] => withTraceNode trace (fun _ => return m!"success!") do
|
||||
return acc.reverse
|
||||
| g :: gs =>
|
||||
-- Discard any goals which have already been assigned.
|
||||
if ← g.isAssigned then
|
||||
withTraceNode trace (return m!"{exceptEmoji ·} discarding already assigned goal {g}") do
|
||||
withTraceNode trace (fun _ => return m!"discarding already assigned goal {g}") do
|
||||
run goals (n+1) gs acc
|
||||
else
|
||||
withTraceNode trace
|
||||
-- Note: the `addMessageContextFull` ensures we show the goal using the mvar context before
|
||||
-- the `do` block below runs, potentially unifying mvars in the goal.
|
||||
(return m!"{exceptEmoji ·} working on: {← addMessageContextFull g}")
|
||||
(fun _ => return m!"working on: {← addMessageContextFull g}")
|
||||
do
|
||||
-- Check if we should suspend the search here:
|
||||
if (← cfg.suspend g) then
|
||||
|
||||
@@ -287,7 +287,7 @@ fails.
|
||||
partial def foldAndCollect (oldIH newIH : FVarId) (isRecCall : Expr → Option Expr) (e : Expr) : M Expr := withoutExporting do
|
||||
unless e.containsFVar oldIH do
|
||||
return e
|
||||
withTraceNode `Meta.FunInd (pure m!"{exceptEmoji ·} foldAndCollect ({mkFVar oldIH} → {mkFVar newIH})::{indentExpr e}") do
|
||||
withTraceNode `Meta.FunInd (fun _ => pure m!"foldAndCollect ({mkFVar oldIH} → {mkFVar newIH})::{indentExpr e}") do
|
||||
|
||||
let e' ← id do
|
||||
if let some matcherApp ← matchMatcherApp? e (alsoCasesOn := true) then
|
||||
@@ -496,7 +496,7 @@ def M2.branch {α} (act : M2 α) : M2 α :=
|
||||
/-- Base case of `buildInductionBody`: Construct a case for the final induction hypothesis. -/
|
||||
def buildInductionCase (oldIH newIH : FVarId) (isRecCall : Expr → Option Expr) (toErase toClear : Array FVarId)
|
||||
(goal : Expr) (e : Expr) : M2 Expr := do
|
||||
withTraceNode `Meta.FunInd (pure m!"{exceptEmoji ·} buildInductionCase:{indentExpr e}") do
|
||||
withTraceNode `Meta.FunInd (fun _ => pure m!"buildInductionCase:{indentExpr e}") do
|
||||
let _e' ← foldAndCollect oldIH newIH isRecCall e
|
||||
let IHs : Array Expr ← M.ask
|
||||
let IHs ← deduplicateIHs IHs
|
||||
@@ -611,7 +611,7 @@ as `MVars` as it goes.
|
||||
partial def buildInductionBody (toErase toClear : Array FVarId) (goal : Expr)
|
||||
(oldIH newIH : FVarId) (isRecCall : Expr → Option Expr) (e : Expr) : M2 Expr := do
|
||||
withTraceNode `Meta.FunInd
|
||||
(pure m!"{exceptEmoji ·} buildInductionBody: {oldIH.name} → {newIH.name}\ngoal: {goal}:{indentExpr e}") do
|
||||
(fun _ => pure m!"buildInductionBody: {oldIH.name} → {newIH.name}\ngoal: {goal}:{indentExpr e}") do
|
||||
|
||||
-- if-then-else cause case split:
|
||||
match_expr e with
|
||||
|
||||
@@ -223,11 +223,6 @@ def mkHeartbeatCheck (leavePercent : Nat) : MetaM (MetaM Bool) := do
|
||||
else do
|
||||
return (← getRemainingHeartbeats) < hbThreshold
|
||||
|
||||
private def librarySearchEmoji : Except ε (Option α) → String
|
||||
| .error _ => bombEmoji
|
||||
| .ok (some _) => crossEmoji
|
||||
| .ok none => checkEmoji
|
||||
|
||||
/--
|
||||
Interleave x y interleaves the elements of x and y until one is empty and then returns
|
||||
final elements in other list.
|
||||
@@ -291,8 +286,6 @@ def librarySearchSymm (searchFn : CandidateFinder) (goal : MVarId) : MetaM (Arra
|
||||
else
|
||||
pure $ l1.map (coreGoalCtx, ·)
|
||||
|
||||
private def emoji (e : Except ε α) := if e.toBool then checkEmoji else crossEmoji
|
||||
|
||||
/-- Create lemma from name and mod. -/
|
||||
def mkLibrarySearchLemma (lem : Name) (mod : DeclMod) : MetaM Expr := do
|
||||
let lem ← mkConstWithFreshMVarLevels lem
|
||||
@@ -319,7 +312,7 @@ private def librarySearchLemma (cfg : ApplyConfig) (act : List MVarId → MetaM
|
||||
let ((goal, mctx), (name, mod)) := cand
|
||||
let ppMod (mod : DeclMod) : MessageData :=
|
||||
match mod with | .none => "" | .mp => " with mp" | .mpr => " with mpr"
|
||||
withTraceNode `Tactic.librarySearch (return m!"{emoji ·} trying {name}{ppMod mod} ") do
|
||||
withTraceNode `Tactic.librarySearch (fun _ => return m!"trying {name}{ppMod mod} ") do
|
||||
setMCtx mctx
|
||||
let lem ← mkLibrarySearchLemma name mod
|
||||
let newGoals ← goal.apply lem cfg
|
||||
@@ -371,7 +364,7 @@ private def librarySearch' (goal : MVarId)
|
||||
(includeStar : Bool := true)
|
||||
(collectAll : Bool := false) :
|
||||
MetaM (Option (Array (List MVarId × MetavarContext))) := do
|
||||
withTraceNode `Tactic.librarySearch (return m!"{librarySearchEmoji ·} {← goal.getType}") do
|
||||
withTraceNode `Tactic.librarySearch (fun _ => return m!"{← goal.getType}") do
|
||||
profileitM Exception "librarySearch" (← getOptions) do
|
||||
let cfg : ApplyConfig := { allowSynthFailures := true }
|
||||
let shouldAbort ← mkHeartbeatCheck leavePercentHeartbeats
|
||||
|
||||
@@ -434,7 +434,7 @@ but if `Config.letToHave` is enabled then we attempt to transform it into a `hav
|
||||
If that does not change it, then it is only `dsimp`ed.
|
||||
-/
|
||||
def simpLet (e : Expr) : SimpM Result := do
|
||||
withTraceNode `Debug.Meta.Tactic.simp (return m!"{exceptEmoji ·} let{indentExpr e}") do
|
||||
withTraceNode `Debug.Meta.Tactic.simp (fun _ => return m!"let{indentExpr e}") do
|
||||
assert! e.isLet
|
||||
/-
|
||||
Recall: `simpLet` is called after `reduceStep` is applied, so `simpLet` is not responsible for zeta reduction.
|
||||
|
||||
@@ -54,7 +54,7 @@ def applyTactics (cfg : ApplyConfig := {}) (transparency : TransparencyMode := .
|
||||
(lemmas : List Expr) (g : MVarId) : MetaM (Lean.Meta.Iterator (List Lean.MVarId)) := do
|
||||
pure <|
|
||||
(← Meta.Iterator.ofList lemmas).filterMapM (fun e => observing? do
|
||||
withTraceNode `Meta.Tactic.solveByElim (return m!"{exceptEmoji ·} trying to apply: {e}") do
|
||||
withTraceNode `Meta.Tactic.solveByElim (fun _ => return m!"trying to apply: {e}") do
|
||||
let goals ← withTransparency transparency (g.apply e cfg)
|
||||
-- When we call `apply` interactively, `Lean.Elab.Tactic.evalApplyLikeTactic`
|
||||
-- deals with closing new typeclass goals by calling
|
||||
|
||||
@@ -114,7 +114,7 @@ where
|
||||
|
||||
tryCandidate candidate : MetaM Bool :=
|
||||
withTraceNode `Meta.isDefEq.hint
|
||||
(return m!"{exceptBoolEmoji ·} hint {candidate} at {t} =?= {s}") do
|
||||
(fun _ => return m!"hint {candidate} at {t} =?= {s}") do
|
||||
checkpointDefEq do
|
||||
let cinfo ← getConstInfo candidate
|
||||
let us ← cinfo.levelParams.mapM fun _ => mkFreshLevelMVar
|
||||
|
||||
@@ -348,7 +348,7 @@ mutual
|
||||
unless projInfo.fromClass do return none
|
||||
-- First check whether `e`s instance is stuck.
|
||||
if let some major := args[projInfo.numParams]? then
|
||||
if let some mvarId ← getStuckMVar? major then
|
||||
if let some mvarId ← getStuckMVar? (← whnf major) then
|
||||
return mvarId
|
||||
/-
|
||||
Then, recurse on the explicit arguments
|
||||
@@ -366,7 +366,7 @@ mutual
|
||||
else if let some auxInfo ← getAuxParentProjectionInfo? fName then
|
||||
unless auxInfo.fromClass do return none
|
||||
if let some major := args[auxInfo.numParams]? then
|
||||
if let some mvarId ← getStuckMVar? major then
|
||||
if let some mvarId ← getStuckMVar? (← whnf major) then
|
||||
return mvarId
|
||||
return none
|
||||
else
|
||||
|
||||
192
src/Lean/Meta/WrapInstance.lean
Normal file
192
src/Lean/Meta/WrapInstance.lean
Normal file
@@ -0,0 +1,192 @@
|
||||
/-
|
||||
Copyright (c) 2026 Lean FRO, LLC. All rights reserved.
|
||||
Released under Apache 2.0 license as described in the file LICENSE.
|
||||
Authors: Authors: Eric Wieser, Kyle Miller, Jovan Gerbscheid, Kim Morrison, Sebastian Ullrich
|
||||
-/
|
||||
module
|
||||
|
||||
prelude
|
||||
public import Lean.Meta.Closure
|
||||
public import Lean.Meta.SynthInstance
|
||||
public import Lean.Meta.CtorRecognizer
|
||||
|
||||
public section
|
||||
|
||||
/-!
|
||||
# Instance Wrapping
|
||||
|
||||
Both `inferInstanceAs` and the default `deriving` handler wrap instance bodies to ensure
|
||||
that when deriving or inferring an instance for a semireducible type definition, the
|
||||
definition's RHS is not leaked when reduced at lower than semireducible transparency.
|
||||
|
||||
## Algorithm
|
||||
|
||||
Given an instance `i : I` and expected type `I'` (where `I'` must be mvar-free),
|
||||
`wrapInstance` constructs a result instance as follows, executing all steps at
|
||||
`instances` transparency:
|
||||
|
||||
1. If `I'` is not a class, return `i` unchanged.
|
||||
2. If `I'` is a proposition, wrap `i` in an auxiliary theorem of type `I'` and return it
|
||||
(controlled by `backward.inferInstanceAs.wrap.instances`).
|
||||
3. Reduce `i` to whnf.
|
||||
4. If `i` is not a constructor application: if the type of `i` is already defeq to `I'`,
|
||||
return `i`; otherwise wrap it in an auxiliary definition of type `I'` and return it
|
||||
(controlled by `backward.inferInstanceAs.wrap.instances`).
|
||||
5. Otherwise, for `i = ctor a₁ ... aₙ` with `ctor : C ?p₁ ... ?pₙ`:
|
||||
- Unify `C ?p₁ ... ?pₙ` with `I'`.
|
||||
- Return a new application `ctor a₁' ... aₙ' : I'` where each `aᵢ'` is constructed as:
|
||||
- If the field type is a proposition: assign directly if types are defeq, otherwise
|
||||
wrap in an auxiliary theorem.
|
||||
- If the field type is a class: first try to reuse an existing synthesized instance
|
||||
for the target type (controlled by `backward.inferInstanceAs.wrap.reuseSubInstances`);
|
||||
if that fails, recurse with source instance `aᵢ` and expected type `?pᵢ`.
|
||||
- Otherwise (data field): assign directly if types are defeq, otherwise wrap in an
|
||||
auxiliary definition to fix the type (controlled by `backward.inferInstanceAs.wrap.data`).
|
||||
|
||||
## Options
|
||||
|
||||
- `backward.inferInstanceAs.wrap`: master switch for wrapping in both `inferInstanceAs`
|
||||
and the default `deriving` handler
|
||||
- `backward.inferInstanceAs.wrap.reuseSubInstances`: reuse existing instances for sub-instance
|
||||
fields to avoid non-defeq instance diamonds
|
||||
- `backward.inferInstanceAs.wrap.instances`: wrap non-reducible instances in auxiliary
|
||||
definitions
|
||||
- `backward.inferInstanceAs.wrap.data`: wrap data fields in auxiliary definitions
|
||||
-/
|
||||
|
||||
namespace Lean.Meta
|
||||
|
||||
register_builtin_option backward.inferInstanceAs.wrap : Bool := {
|
||||
defValue := true
|
||||
descr := "wrap instance bodies in `inferInstanceAs` and the default `deriving` handler"
|
||||
}
|
||||
|
||||
register_builtin_option backward.inferInstanceAs.wrap.reuseSubInstances : Bool := {
|
||||
defValue := true
|
||||
descr := "when recursing into sub-instances, reuse existing instances for the target type instead of re-wrapping them, which can be important to avoid non-defeq instance diamonds"
|
||||
}
|
||||
|
||||
register_builtin_option backward.inferInstanceAs.wrap.instances : Bool := {
|
||||
defValue := true
|
||||
descr := "wrap non-reducible instances in auxiliary definitions to fix their types"
|
||||
}
|
||||
|
||||
register_builtin_option backward.inferInstanceAs.wrap.data : Bool := {
|
||||
defValue := true
|
||||
descr := "wrap data fields in auxiliary definitions to fix their types"
|
||||
}
|
||||
|
||||
builtin_initialize registerTraceClass `Meta.wrapInstance
|
||||
|
||||
/--
|
||||
Rebuild a type application with fresh synthetic metavariables for instance-implicit arguments.
|
||||
Non-instance-implicit arguments are assigned from the original application's arguments.
|
||||
If the function is over-applied, extra arguments are preserved.
|
||||
-/
|
||||
def abstractInstImplicitArgs (type : Expr) : MetaM Expr := do
|
||||
let fn := type.getAppFn
|
||||
let args := type.getAppArgs
|
||||
let (mvars, bis, _) ← forallMetaTelescope (← inferType fn)
|
||||
for i in [:mvars.size] do
|
||||
unless bis[i]!.isInstImplicit do
|
||||
mvars[i]!.mvarId!.assign args[i]!
|
||||
let args := mvars ++ args.drop mvars.size
|
||||
instantiateMVars (mkAppN fn args)
|
||||
|
||||
/--
|
||||
Wrap an instance value so its type matches the expected type exactly.
|
||||
See the module docstring for the full algorithm specification.
|
||||
-/
|
||||
partial def wrapInstance (inst expectedType : Expr) (compile : Bool := true)
|
||||
(logCompileErrors : Bool := true) (isMeta : Bool := false) : MetaM Expr := withTransparency .instances do
|
||||
withTraceNode `Meta.wrapInstance
|
||||
(fun _ => return m!"type: {expectedType}") do
|
||||
let some className ← isClass? expectedType
|
||||
| return inst
|
||||
trace[Meta.wrapInstance] "class is {className}"
|
||||
|
||||
if ← isProp expectedType then
|
||||
if backward.inferInstanceAs.wrap.instances.get (← getOptions) then
|
||||
return (← mkAuxTheorem expectedType inst (zetaDelta := true))
|
||||
else
|
||||
return inst
|
||||
|
||||
-- Try to reduce it to a constructor.
|
||||
let inst ← whnf inst
|
||||
inst.withApp fun f args => do
|
||||
let some (.ctorInfo ci) ← f.constName?.mapM getConstInfo
|
||||
| do
|
||||
trace[Meta.wrapInstance] "did not reduce to constructor application, returning/wrapping as is: {inst}"
|
||||
if backward.inferInstanceAs.wrap.instances.get (← getOptions) then
|
||||
let instType ← inferType inst
|
||||
if ← isDefEq expectedType instType then
|
||||
return inst
|
||||
else
|
||||
let name ← mkAuxDeclName
|
||||
let wrapped ← mkAuxDefinition name expectedType inst (compile := false)
|
||||
setReducibilityStatus name .implicitReducible
|
||||
if isMeta then modifyEnv (markMeta · name)
|
||||
if compile then
|
||||
compileDecls (logErrors := logCompileErrors) #[name]
|
||||
enableRealizationsForConst name
|
||||
return wrapped
|
||||
else
|
||||
return inst
|
||||
let (mvars, _, cls) ← forallMetaTelescope (← inferType f)
|
||||
if h₁ : args.size ≠ mvars.size then
|
||||
throwError "wrapInstance: incorrect number of arguments for \
|
||||
constructor application `{f}`: {args}"
|
||||
else
|
||||
unless ← isDefEq expectedType cls do
|
||||
throwError "wrapInstance: `{expectedType}` does not unify with the conclusion of \
|
||||
`{.ofConstName ci.name}`"
|
||||
for h₂ : i in ci.numParams...args.size do
|
||||
have : i < mvars.size := by
|
||||
simp only [ne_eq, Decidable.not_not] at h₁
|
||||
rw [← h₁]
|
||||
get_elem_tactic
|
||||
let mvarId := mvars[i].mvarId!
|
||||
let mvarDecl ← mvarId.getDecl
|
||||
let argExpectedType ← instantiateMVars mvarDecl.type
|
||||
let arg := args[i]
|
||||
if ← isProp argExpectedType then
|
||||
let argType ← inferType arg
|
||||
if ← isDefEq argExpectedType argType then
|
||||
mvarId.assign arg
|
||||
else
|
||||
trace[Meta.wrapInstance] "proof field {i} does not have expected type {argExpectedType} but {argType}, wrapping in auxiliary theorem: {arg}"
|
||||
mvarId.assign (← mkAuxTheorem argExpectedType arg (zetaDelta := true))
|
||||
-- Recurse into instance arguments of the constructor
|
||||
else if (← isClass? argExpectedType).isSome then
|
||||
if backward.inferInstanceAs.wrap.reuseSubInstances.get (← getOptions) then
|
||||
-- Reuse existing instance for the target type if any. This is especially important when recursing
|
||||
-- as it guarantees subinstances of overlapping instances are defeq under more than just
|
||||
-- semireducible transparency.
|
||||
try
|
||||
if let .some new ← trySynthInstance argExpectedType then
|
||||
trace[Meta.wrapInstance] "using existing instance {new}"
|
||||
mvarId.assign new
|
||||
continue
|
||||
catch _ => pure ()
|
||||
|
||||
mvarId.assign (← wrapInstance arg argExpectedType (compile := compile)
|
||||
(logCompileErrors := logCompileErrors) (isMeta := isMeta))
|
||||
else
|
||||
-- For data fields, assign directly or wrap in aux def to fix types.
|
||||
if backward.inferInstanceAs.wrap.data.get (← getOptions) then
|
||||
let argType ← inferType arg
|
||||
if ← isDefEq argExpectedType argType then
|
||||
mvarId.assign arg
|
||||
else
|
||||
let name ← mkAuxDeclName
|
||||
mvarId.assign (← mkAuxDefinition name argExpectedType arg (compile := false))
|
||||
setInlineAttribute name
|
||||
if isMeta then modifyEnv (markMeta · name)
|
||||
if compile then
|
||||
compileDecls (logErrors := logCompileErrors) #[name]
|
||||
enableRealizationsForConst name
|
||||
else
|
||||
mvarId.assign arg
|
||||
return mkAppN f (← mvars.mapM instantiateMVars)
|
||||
|
||||
end Lean.Meta
|
||||
@@ -186,7 +186,7 @@ def derivingClass := leading_parser
|
||||
optional ("@[" >> nonReservedSymbol "expose" >> "]") >> withForbidden "for" termParser
|
||||
def derivingClasses := sepBy1 derivingClass ", "
|
||||
def optDefDeriving :=
|
||||
optional (ppDedent ppLine >> atomic ("deriving " >> notSymbol "instance") >> derivingClasses)
|
||||
optional (ppDedent ppLine >> atomic ("deriving " >> notSymbol "instance" >> notSymbol "noncomputable") >> derivingClasses)
|
||||
def definition := leading_parser
|
||||
"def " >> recover declId skipUntilWsOrDelim >> ppIndent optDeclSig >> declVal >> optDefDeriving
|
||||
def «theorem» := leading_parser
|
||||
@@ -207,7 +207,7 @@ def ctor := leading_parser
|
||||
atomic (optional docComment >> "\n| ") >>
|
||||
ppGroup (declModifiers true >> rawIdent >> optDeclSig)
|
||||
def optDeriving := leading_parser
|
||||
optional (ppLine >> atomic ("deriving " >> notSymbol "instance") >> derivingClasses)
|
||||
optional (ppLine >> atomic ("deriving " >> notSymbol "instance" >> notSymbol "noncomputable") >> derivingClasses)
|
||||
def computedField := leading_parser
|
||||
declModifiers true >> ident >> " : " >> termParser >> Term.matchAlts
|
||||
def computedFields := leading_parser
|
||||
@@ -280,7 +280,7 @@ def «structure» := leading_parser
|
||||
(«abbrev» <|> definition <|> «theorem» <|> «opaque» <|> «instance» <|> «axiom» <|> «example» <|>
|
||||
«inductive» <|> «coinductive» <|> classInductive <|> «structure»)
|
||||
@[builtin_command_parser] def «deriving» := leading_parser
|
||||
"deriving " >> "instance " >> derivingClasses >> " for " >> sepBy1 (recover termParser skip) ", "
|
||||
"deriving " >> optional "noncomputable " >> "instance " >> derivingClasses >> " for " >> sepBy1 (recover termParser skip) ", "
|
||||
def sectionHeader := leading_parser
|
||||
optional ("@[" >> nonReservedSymbol "expose" >> "] ") >>
|
||||
optional ("public ") >>
|
||||
|
||||
@@ -774,6 +774,19 @@ In particular, it is like a unary operation with a fixed parameter `b`, where on
|
||||
@[builtin_term_parser] def noImplicitLambda := leading_parser
|
||||
"no_implicit_lambda% " >> termParser maxPrec
|
||||
/--
|
||||
`inferInstanceAs α` synthesizes an instance of type `α`, transporting it from a
|
||||
definitionally equal type if necessary. This is useful when `α` is definitionally equal to
|
||||
some `α'` for which instances are registered, as it prevents leaking the definition's RHS
|
||||
at lower transparencies.
|
||||
|
||||
`inferInstanceAs` requires an expected type from context. If you just need to synthesize an
|
||||
instance without transporting between types, use `inferInstance` instead.
|
||||
|
||||
See `Lean.Meta.WrapInstance` for details.
|
||||
-/
|
||||
@[builtin_term_parser] def «inferInstanceAs» := leading_parser
|
||||
"inferInstanceAs" >> (((" $ " <|> " <| ") >> termParser minPrec) <|> (ppSpace >> termParser argPrec))
|
||||
/--
|
||||
`value_of% x` elaborates to the value of `x`, which can be a local or global definition.
|
||||
-/
|
||||
@[builtin_term_parser] def valueOf := leading_parser
|
||||
|
||||
@@ -47,8 +47,12 @@ def delabFVar : Delab := do
|
||||
let l ← fvarId.getDecl
|
||||
maybeAddBlockImplicit (mkIdent l.userName)
|
||||
catch _ =>
|
||||
-- loose free variable, use internal name
|
||||
maybeAddBlockImplicit <| mkIdent (fvarId.name.replacePrefix `_uniq `_fvar)
|
||||
-- loose free variable
|
||||
if ← getPPOption getPPFVarsAnonymous then
|
||||
-- use internal name like `_fvar.22`
|
||||
maybeAddBlockImplicit <| mkIdent (fvarId.name.replacePrefix `_uniq `_fvar)
|
||||
else
|
||||
maybeAddBlockImplicit <| mkIdent `_fvar._
|
||||
|
||||
-- loose bound variable, use pseudo syntax
|
||||
@[builtin_delab bvar]
|
||||
|
||||
Some files were not shown because too many files have changed in this diff Show More
Reference in New Issue
Block a user