chore: update Authors: line in BitVec files

* Replaces the unused `Lean.PrettyPrinter.ppConst` with
`MessageData.ofConst` (which similarly avoids an unnecessary `@`) and
that further generates a hover for the constant

* Uses this in `TryThis.addRewriteSuggestion`, so that `rw?` suggestions
don't have unnecessary `@`s.

* Add `MessageData.signature`, as a wrapper around
`PrettyPrinter.signature`, using the same machinery to generate hovers
for constants, improving the hover behaviour in #check so that we get
second order pop-up for constants in the signature. (Not sure how to
write tests for second order hovers, so there is no test for this.)

.github/workflows/copyright-header.yml

@@ -10,7 +10,7 @@ jobs:
 
     - name: Verify .lean files start with a copyright header.
       run: |
-        FILES=$(find . -type d \( -path "./tests" -o -path "./doc" -o -path "./src/lake/examples" -o -path "./src/lake/tests" -o -path "./build" -o -path "./nix" \) -prune -o -type f -name "*.lean" -exec perl -ne 'BEGIN { $/ = undef; } print "$ARGV\n" if !m{\A/-\nCopyright}; exit;' {} \;)
+        FILES=$(find ./src -type d \( -path "./src/lake/examples" -o -path "./src/lake/tests" \) -prune -o -type f -name "*.lean" -exec perl -ne 'BEGIN { $/ = undef; } print "$ARGV\n" if !m{\A/-\nCopyright}; exit;' {} \;)
         if [ -n "$FILES" ]; then
           echo "Found .lean files which do not have a copyright header:"
           echo "$FILES"

.github/workflows/pr-release.yml

@@ -150,7 +150,7 @@ jobs:
             git -C lean4.git log -10 origin/master
 
             git -C lean4.git fetch origin nightly-with-mathlib 
-            NIGHTLY_WITH_MATHLIB_SHA="$(git -C lean4.git rev-parse "nightly-with-mathlib")"
+            NIGHTLY_WITH_MATHLIB_SHA="$(git -C lean4.git rev-parse "origin/nightly-with-mathlib")"
             MESSAGE="- ❗ Std/Mathlib CI will not be attempted unless your PR branches off the \`nightly-with-mathlib\` branch. Try \`git rebase $MERGE_BASE_SHA --onto $NIGHTLY_WITH_MATHLIB_SHA\`."
           fi
 

CODEOWNERS

@@ -21,3 +21,23 @@
 /src/Lean/Server/ @mhuisi
 /src/Lean/Widget/ @Vtec234
 /src/runtime/io.cpp @joehendrix
+/src/Lean/Elab/Tactic/RCases.lean @digama0
+/src/Init/RCases.lean @digama0
+/src/Lean/Elab/Tactic/Ext.lean @digama0
+/src/Init/Ext.lean @digama0
+/src/Lean/Elab/Tactic/Simpa.lean @digama0
+/src/Lean/Elab/Tactic/NormCast.lean @digama0
+/src/Lean/Meta/Tactic/NormCast.lean @digama0
+/src/Lean/Meta/Tactic/TryThis.lean @digama0
+/src/Lean/Elab/Tactic/SimpTrace.lean @digama0
+/src/Lean/Elab/Tactic/NoMatch.lean @digama0
+/src/Lean/Elab/Tactic/ShowTerm.lean @digama0
+/src/Lean/Elab/Tactic/Repeat.lean @digama0
+/src/Lean/Meta/Tactic/Repeat.lean @digama0
+/src/Lean/Meta/CoeAttr.lean @digama0
+/src/Lean/Elab/GuardMsgs.lean @digama0
+/src/Lean/Elab/Tactic/Guard.lean @digama0
+/src/Init/Guard.lean @digama0
+/src/Lean/Server/CodeActions/ @digama0
+/src/Init/Data/Array/Subarray.lean @david-christiansen
+

RELEASES.md

@@ -21,7 +21,7 @@ v4.8.0 (development in progress)
 
 * Importing two different files containing proofs of the same theorem is no longer considered an error. This feature is particularly useful for theorems that are automatically generated on demand (e.g., equational theorems).
 
-* Funcitonal induction principles.
+* Functional induction principles.
 
   Derived from the definition of a (possibly mutually) recursive function, a **functional induction principle** is created that is tailored to proofs about that function.
 
@@ -57,6 +57,15 @@ v4.8.0 (development in progress)
   ```
   is recognized without having to say `termination_by arr.size - i`.
 
+* Shorter instances names. There is a new algorithm for generating names for anonymous instances.
+  Across Std and Mathlib, the median ratio between lengths of new names and of old names is about 72%.
+  With the old algorithm, the longest name was 1660 characters, and now the longest name is 202 characters.
+  The new algorithm's 95th percentile name length is 67 characters, versus 278 for the old algorithm.
+  While the new algorithm produces names that are 1.2% less unique,
+  it avoids cross-project collisions by adding a module-based suffix
+  when it does not refer to declarations from the same "project" (modules that share the same root).
+  PR [#3089](https://github.com/leanprover/lean4/pull/3089).
+
 * Attribute `@[pp_using_anonymous_constructor]` to make structures pretty print like `⟨x, y, z⟩`
   rather than `{a := x, b := y, c := z}`.
   This attribute is applied to `Sigma`, `PSigma`, `PProd`, `Subtype`, `And`, and `Fin`.
@@ -80,8 +89,19 @@ v4.8.0 (development in progress)
   Gives custom eliminators for `Nat` so that `induction` and `cases` put goal states into terms of `0` and `n + 1`
   rather than `Nat.zero` and `Nat.succ n`.
   Added option `tactic.customEliminators` to control whether to use custom eliminators.
-  [#3629](https://github.com/leanprover/lean4/pull/3629) and
-  [#3655](https://github.com/leanprover/lean4/pull/3655).
+  Added a hack for `rcases`/`rintro`/`obtain` to use the custom eliminator for `Nat`.
+  [#3629](https://github.com/leanprover/lean4/pull/3629),
+  [#3655](https://github.com/leanprover/lean4/pull/3655), and
+  [#3747](https://github.com/leanprover/lean4/pull/3747).
+
+* The `#guard_msgs` command now has options to change whitespace normalization and sensitivity to message ordering.
+  For example, `#guard_msgs (whitespace := lax) in cmd` collapses whitespace before checking messages,
+  and `#guard_msgs (ordering := sorted) in cmd` sorts the messages in lexicographic order before checking.
+  PR [#3883](https://github.com/leanprover/lean4/pull/3883).
+
+* The `#guard_msgs` command now supports showing a diff between the expected and actual outputs. This feature is currently
+  disabled by default, but can be enabled with `set_option guard_msgs.diff true`. Depending on user feedback, this option
+  may default to `true` in a future version of Lean.
 
 Breaking changes:
 
@@ -112,6 +132,12 @@ fact.def :
 
 * The coercion from `String` to `Name` was removed. Previously, it was `Name.mkSimple`, which does not separate strings at dots, but experience showed that this is not always the desired coercion. For the previous behavior, manually insert a call to `Name.mkSimple`.
 
+* The `Subarray` fields `as`, `h₁` and `h₂` have been renamed to `array`, `start_le_stop`, and `stop_le_array_size`, respectively. This more closely follows standard Lean conventions. Deprecated aliases for the field projections were added; these will be removed in a future release.
+
+* The change to the instance name algorithm (described above) can break projects that made use of the auto-generated names.
+
+* `Option.toMonad` has been renamed to `Option.getM` and the unneeded `[Monad m]` instance argument has been removed.
+
 v4.7.0
 ---------
 

doc/dev/release_checklist.md

@@ -21,7 +21,7 @@ We'll use `v4.6.0` as the intended release version as a running example.
   - Reconcile discrepancies in the `v4.6.0` section,
     usually via copy and paste and a commit to `releases/v4.6.0`.
 - `git tag v4.6.0`
-- `git push origin v4.6.0`
+- `git push $REMOTE v4.6.0`, where `$REMOTE` is the upstream Lean repository (e.g., `origin`, `upstream`)
 - Now wait, while CI runs.
   - You can monitor this at `https://github.com/leanprover/lean4/actions/workflows/ci.yml`,
     looking for the `v4.6.0` tag.
@@ -34,48 +34,76 @@ We'll use `v4.6.0` as the intended release version as a running example.
     (e.g. `v4.6.0-rc1`), and quickly sanity check.
 - Next, we will move a curated list of downstream repos to the latest stable release.
   - For each of the repositories listed below:
-    - Make a PR to `master`/`main` changing the toolchain to `v4.6.0`.
-      The PR title should be "chore: bump toolchain to v4.6.0".
-      Since the `v4.6.0` release should be functionally identical to the last release candidate,
-      which the repository should already be on, this PR is a no-op besides changing the toolchain.
-    - Once this is merged, create the tag `v4.6.0` from `master`/`main` and push it.
-    - Merge the tag `v4.6.0` into the stable branch.
+    - Make a PR to `master`/`main` changing the toolchain to `v4.6.0`
+      - Update the toolchain file
+      - In the Lakefile, if there are dependencies on specific version tags of dependencies that you've already pushed as part of this process, update them to the new tag.
+        If they depend on `main` or `master`, don't change this; you've just updated the dependency, so it will work and be saved in the manifest
+      - Run `lake update`
+      - The PR title should be "chore: bump toolchain to v4.6.0".
+    - Merge the PR once CI completes.
+    - Create the tag `v4.6.0` from `master`/`main` and push it.
+    - Merge the tag `v4.6.0` into the `stable` branch and push it.
   - We do this for the repositories:
     - [lean4checker](https://github.com/leanprover/lean4checker)
-      - `lean4checker` uses a different version tagging scheme: use `toolchain/v4.6.0` rather than `v4.6.0`.
-    - [Std](https://github.com/leanprover-community/repl)
+      - No dependencies
+      - Note: `lean4checker` uses a different version tagging scheme: use `toolchain/v4.6.0` rather than `v4.6.0`.
+      - Toolchain bump PR
+      - Create and push the tag
+      - Merge the tag into `stable`
+    - [Std](https://github.com/leanprover-community/std4)
+      - No dependencies
+      - Toolchain bump PR
+      - Create and push the tag
+      - Merge the tag into `stable`
     - [ProofWidgets4](https://github.com/leanprover-community/ProofWidgets4)
-      - `ProofWidgets` uses a sequential version tagging scheme, e.g. `v0.0.29`,
-        which does not refer to the toolchain being used.
-      - Make a new release in this sequence after merging the toolchain bump PR.
-      - `ProofWidgets` does not maintain a `stable` branch.
+      - Dependencies: `Std`
+      - Note on versions and branches:
+        - `ProofWidgets` uses a sequential version tagging scheme, e.g. `v0.0.29`,
+          which does not refer to the toolchain being used.
+        - Make a new release in this sequence after merging the toolchain bump PR.
+        - `ProofWidgets` does not maintain a `stable` branch.
+      - Toolchain bump PR
+      - Create and push the tag, following the version convention of the repository
     - [Aesop](https://github.com/leanprover-community/aesop)
+      - Dependencies: `Std`
+      - Toolchain bump PR including updated Lake manifest
+      - Create and push the tag
+      - Merge the tag into `stable`
+    - [doc-gen4](https://github.com/leanprover/doc-gen4)
+      - Dependencies: exist, but they're not part of the release workflow
+      - Toolchain bump PR including updated Lake manifest
+      - Create and push the tag
+      - There is no `stable` branch; skip this step
+    - [import-graph](https://github.com/leanprover-community/import-graph)
+      - Toolchain bump PR including updated Lake manifest
+      - Create and push the tag
+      - There is no `stable` branch; skip this step
     - [Mathlib](https://github.com/leanprover-community/mathlib4)
-      - In addition to updating the `lean-toolchain` and `lakefile.lean`,
-        in `.github/workflows/build.yml.in` in the `lean4checker` section update the line
-        `git checkout toolchain/v4.6.0` to the appropriate tag,
-        and then run `.github/workflows/mk_build_yml.sh`.
+      - Dependencies: `Aesop`, `ProofWidgets4`, `lean4checker`, `Std`, `doc-gen4`, `import-graph`
+      - Toolchain bump PR notes:
+        - In addition to updating the `lean-toolchain` and `lakefile.lean`,
+          in `.github/workflows/build.yml.in` in the `lean4checker` section update the line
+          `git checkout toolchain/v4.6.0` to the appropriate tag,
+          and then run `.github/workflows/mk_build_yml.sh`. Coordinate with
+          a Mathlib maintainer to get this merged.
+        - Push the PR branch to the main Mathlib repository rather than a fork, or CI may not work reliably
+        - Create and push the tag
+        - Create a new branch from the tag, push it, and open a pull request against `stable`.
+          Coordinate with a Mathlib maintainer to get this merged.
     - [REPL](https://github.com/leanprover-community/repl)
+      - Dependencies: `Mathlib` (for test code)
       - Note that there are two copies of `lean-toolchain`/`lakefile.lean`:
-        in the root, and in `test/Mathlib/`.
-  - Note that there are dependencies between these packages:
-    you should update the lakefile so that you are using the `v4.6.0` tag of upstream repositories
-    (or the sequential tag for `ProofWidgets4`), and run `lake update` before committing.
-  - This means that this process is sequential; each repository must have its bump PR merged,
-    and the new tag pushed, before you can make the PR for the downstream repositories.
-    - `lean4checker` has no dependencies
-    - `Std` has no dependencies
-    - `Aesop` depends on `Std`
-    - `ProofWidgets4` depends on `Std`
-    - `Mathlib` depends on `Aesop`, `ProofWidgets4`, and `lean4checker` (and transitively on `Std`)
-    - `REPL` depends on `Mathlib` (this dependency is only for testing).
+        in the root, and in `test/Mathlib/`. Edit both, and run `lake update` in both directories.
+      - Toolchain bump PR including updated Lake manifest
+      - Create and push the tag
+      - Merge the tag into `stable`
 - Merge the release announcement PR for the Lean website - it will be deployed automatically
 - Finally, make an announcement!
   This should go in https://leanprover.zulipchat.com/#narrow/stream/113486-announce, with topic `v4.6.0`.
   Please see previous announcements for suggested language.
   You will want a few bullet points for main topics from the release notes.
   Link to the blog post from the Zulip announcement.
-  Please also make sure that whoever is handling social media knows the release is out.
+- Make sure that whoever is handling social media knows the release is out.
 
 ## Optimistic(?) time estimates:
 - Initial checks and push the tag: 30 minutes.

script/collideProfiles.lean

@@ -0,0 +1,28 @@
+import Lean.Util.Profiler
+
+/-!
+
+Usage:
+```sh
+lean --run ./script/collideProfiles.lean **/*.lean.json ... > merged.json
+```
+
+Merges multiple `trace.profiler.output` profiles into a single one while deduplicating samples with
+the same stack. This is useful for building cumulative profiles of medium-to-large projects because
+Firefox Profiler cannot handle hundreds of tracks and the deduplication will also ensure that the
+profile is small enough for uploading.
+
+As ordering of samples is not meaningful after this transformation, only "Call Tree" and "Flame
+Graph" are useful for such profiles.
+-/
+
+open Lean
+
+def main (args : List String) : IO Unit := do
+  let profiles ← args.toArray.mapM fun path => do
+    let json ← IO.FS.readFile ⟨path⟩
+    let profile ← IO.ofExcept $ Json.parse json
+    IO.ofExcept <| fromJson? profile
+  -- NOTE: `collide` should not be interpreted
+  let profile := Firefox.Profile.collide profiles
+  IO.println <| Json.compress <| toJson profile

src/Init/Control/Basic.lean

@@ -20,8 +20,29 @@ def Functor.discard {f : Type u → Type v} {α : Type u} [Functor f] (x : f α)
 
 export Functor (discard)
 
+/--
+An `Alternative` functor is an `Applicative` functor that can "fail" or be "empty"
+and a binary operation `<|>` that “collects values” or finds the “left-most success”.
+
+Important instances include
+* `Option`, where `failure := none` and `<|>` returns the left-most `some`.
+* Parser combinators typically provide an `Applicative` instance for error-handling and
+  backtracking.
+  
+Error recovery and state can interact subtly. For example, the implementation of `Alternative` for `OptionT (StateT σ Id)` keeps modifications made to the state while recovering from failure, while `StateT σ (OptionT Id)` discards them.
+-/
+-- NB: List instance is in mathlib. Once upstreamed, add
+-- * `List`, where `failure` is the empty list and `<|>` concatenates.
 class Alternative (f : Type u → Type v) extends Applicative f : Type (max (u+1) v) where
+  /--
+  Produces an empty collection or recoverable failure.  The `<|>` operator collects values or recovers
+  from failures. See `Alternative` for more details.
+  -/
   failure : {α : Type u} → f α
+  /--
+  Depending on the `Alternative` instance, collects values or recovers from `failure`s by
+  returning the leftmost success. Can be written using the `<|>` operator syntax.
+  -/
   orElse  : {α : Type u} → f α → (Unit → f α) → f α
 
 instance (f : Type u → Type v) (α : Type u) [Alternative f] : OrElse (f α) := ⟨Alternative.orElse⟩
@@ -30,9 +51,15 @@ variable {f : Type u → Type v} [Alternative f] {α : Type u}
 
 export Alternative (failure)
 
+/--
+If the proposition `p` is true, does nothing, else fails (using `failure`).
+-/
 @[always_inline, inline] def guard {f : Type → Type v} [Alternative f] (p : Prop) [Decidable p] : f Unit :=
   if p then pure () else failure
 
+/--
+Returns `some x` if `f` succeeds with value `x`, else returns `none`.
+-/
 @[always_inline, inline] def optional (x : f α) : f (Option α) :=
   some <$> x <|> pure none
 

src/Init/Control/Lawful/Basic.lean

@@ -12,6 +12,15 @@ open Function
 @[simp] theorem monadLift_self [Monad m] (x : m α) : monadLift x = x :=
   rfl
 
+/--
+The `Functor` typeclass only contains the operations of a functor.
+`LawfulFunctor` further asserts that these operations satisfy the laws of a functor,
+including the preservation of the identity and composition laws:
+```
+id <$> x = x
+(h ∘ g) <$> x = h <$> g <$> x
+```
+-/
 class LawfulFunctor (f : Type u → Type v) [Functor f] : Prop where
   map_const          : (Functor.mapConst : α → f β → f α) = Functor.map ∘ const β
   id_map   (x : f α) : id <$> x = x
@@ -24,6 +33,16 @@ attribute [simp] id_map
 @[simp] theorem id_map' [Functor m] [LawfulFunctor m] (x : m α) : (fun a => a) <$> x = x :=
   id_map x
 
+/--
+The `Applicative` typeclass only contains the operations of an applicative functor.
+`LawfulApplicative` further asserts that these operations satisfy the laws of an applicative functor:
+```
+pure id <*> v = v
+pure (·∘·) <*> u <*> v <*> w = u <*> (v <*> w)
+pure f <*> pure x = pure (f x)
+u <*> pure y = pure (· y) <*> u
+```
+-/
 class LawfulApplicative (f : Type u → Type v) [Applicative f] extends LawfulFunctor f : Prop where
   seqLeft_eq  (x : f α) (y : f β)     : x <* y = const β <$> x <*> y
   seqRight_eq (x : f α) (y : f β)     : x *> y = const α id <$> x <*> y
@@ -42,6 +61,18 @@ attribute [simp] map_pure seq_pure
 @[simp] theorem pure_id_seq [Applicative f] [LawfulApplicative f] (x : f α) : pure id <*> x = x := by
   simp [pure_seq]
 
+/--
+The `Monad` typeclass only contains the operations of a monad.
+`LawfulMonad` further asserts that these operations satisfy the laws of a monad,
+including associativity and identity laws for `bind`:
+```
+pure x >>= f = f x
+x >>= pure = x
+x >>= f >>= g = x >>= (fun x => f x >>= g)
+```
+
+`LawfulMonad.mk'` is an alternative constructor containing useful defaults for many fields.
+-/
 class LawfulMonad (m : Type u → Type v) [Monad m] extends LawfulApplicative m : Prop where
   bind_pure_comp (f : α → β) (x : m α) : x >>= (fun a => pure (f a)) = f <$> x
   bind_map       {α β : Type u} (f : m (α → β)) (x : m α) : f >>= (. <$> x) = f <*> x

src/Init/Control/Lawful/Instances.lean

@@ -235,13 +235,13 @@ end StateT
 
 instance : LawfulMonad (EStateM ε σ) := .mk'
   (id_map := fun x => funext <| fun s => by
-    dsimp only [EStateM.instMonadEStateM, EStateM.map]
+    dsimp only [EStateM.instMonad, EStateM.map]
     match x s with
     | .ok _ _ => rfl
     | .error _ _ => rfl)
   (pure_bind := fun _ _ => rfl)
   (bind_assoc := fun x _ _ => funext <| fun s => by
-    dsimp only [EStateM.instMonadEStateM, EStateM.bind]
+    dsimp only [EStateM.instMonad, EStateM.bind]
     match x s with
     | .ok _ _ => rfl
     | .error _ _ => rfl)

src/Init/Data.lean

@@ -14,6 +14,7 @@ import Init.Data.String
 import Init.Data.List
 import Init.Data.Int
 import Init.Data.Array
+import Init.Data.Array.Subarray.Split
 import Init.Data.ByteArray
 import Init.Data.FloatArray
 import Init.Data.Fin

src/Init/Data/Array/Subarray.lean

@@ -9,25 +9,40 @@ import Init.Data.Array.Basic
 universe u v w
 
 structure Subarray (α : Type u)  where
-  as : Array α
+  array : Array α
   start : Nat
   stop : Nat
-  h₁ : start ≤ stop
-  h₂ : stop ≤ as.size
+  start_le_stop : start ≤ stop
+  stop_le_array_size : stop ≤ array.size
+
+@[deprecated Subarray.array]
+abbrev Subarray.as (s : Subarray α) : Array α := s.array
+
+@[deprecated Subarray.start_le_stop]
+theorem Subarray.h₁ (s : Subarray α) : s.start ≤ s.stop := s.start_le_stop
+
+@[deprecated Subarray.stop_le_array_size]
+theorem Subarray.h₂ (s : Subarray α) : s.stop ≤ s.as.size := s.stop_le_array_size
 
 namespace Subarray
 
 def size (s : Subarray α) : Nat :=
   s.stop - s.start
 
+theorem size_le_array_size {s : Subarray α} : s.size ≤ s.array.size := by
+  let {array, start, stop, start_le_stop, stop_le_array_size} := s
+  simp [size]
+  apply Nat.le_trans (Nat.sub_le stop start)
+  assumption
+
 def get (s : Subarray α) (i : Fin s.size) : α :=
-  have : s.start + i.val < s.as.size := by
-   apply Nat.lt_of_lt_of_le _ s.h₂
+  have : s.start + i.val < s.array.size := by
+   apply Nat.lt_of_lt_of_le _ s.stop_le_array_size
    have := i.isLt
    simp [size] at this
    rw [Nat.add_comm]
    exact Nat.add_lt_of_lt_sub this
-  s.as[s.start + i.val]
+  s.array[s.start + i.val]
 
 instance : GetElem (Subarray α) Nat α fun xs i => i < xs.size where
   getElem xs i h := xs.get ⟨i, h⟩
@@ -42,7 +57,7 @@ abbrev get! [Inhabited α] (s : Subarray α) (i : Nat) : α :=
 
 def popFront (s : Subarray α) : Subarray α :=
   if h : s.start < s.stop then
-    { s with start := s.start + 1, h₁ := Nat.le_of_lt_succ (Nat.add_lt_add_right h 1) }
+    { s with start := s.start + 1, start_le_stop := Nat.le_of_lt_succ (Nat.add_lt_add_right h 1) }
   else
     s
 
@@ -50,7 +65,7 @@ def popFront (s : Subarray α) : Subarray α :=
   let sz := USize.ofNat s.stop
   let rec @[specialize] loop (i : USize) (b : β) : m β := do
     if i < sz then
-      let a := s.as.uget i lcProof
+      let a := s.array.uget i lcProof
       match (← f a b) with
       | ForInStep.done  b => pure b
       | ForInStep.yield b => loop (i+1) b
@@ -68,27 +83,27 @@ instance : ForIn m (Subarray α) α where
 
 @[inline]
 def foldlM {α : Type u} {β : Type v} {m : Type v → Type w} [Monad m] (f : β → α → m β) (init : β) (as : Subarray α) : m β :=
-  as.as.foldlM f (init := init) (start := as.start) (stop := as.stop)
+  as.array.foldlM f (init := init) (start := as.start) (stop := as.stop)
 
 @[inline]
 def foldrM {α : Type u} {β : Type v} {m : Type v → Type w} [Monad m] (f : α → β → m β) (init : β) (as : Subarray α) : m β :=
-  as.as.foldrM f (init := init) (start := as.stop) (stop := as.start)
+  as.array.foldrM f (init := init) (start := as.stop) (stop := as.start)
 
 @[inline]
 def anyM {α : Type u} {m : Type → Type w} [Monad m] (p : α → m Bool) (as : Subarray α) : m Bool :=
-  as.as.anyM p (start := as.start) (stop := as.stop)
+  as.array.anyM p (start := as.start) (stop := as.stop)
 
 @[inline]
 def allM {α : Type u} {m : Type → Type w} [Monad m] (p : α → m Bool) (as : Subarray α) : m Bool :=
-  as.as.allM p (start := as.start) (stop := as.stop)
+  as.array.allM p (start := as.start) (stop := as.stop)
 
 @[inline]
 def forM {α : Type u} {m : Type v → Type w} [Monad m] (f : α → m PUnit) (as : Subarray α) : m PUnit :=
-  as.as.forM f (start := as.start) (stop := as.stop)
+  as.array.forM f (start := as.start) (stop := as.stop)
 
 @[inline]
 def forRevM {α : Type u} {m : Type v → Type w} [Monad m] (f : α → m PUnit) (as : Subarray α) : m PUnit :=
-  as.as.forRevM f (start := as.stop) (stop := as.start)
+  as.array.forRevM f (start := as.stop) (stop := as.start)
 
 @[inline]
 def foldl {α : Type u} {β : Type v} (f : β → α → β) (init : β) (as : Subarray α) : β :=
@@ -135,15 +150,25 @@ variable {α : Type u}
 
 def toSubarray (as : Array α) (start : Nat := 0) (stop : Nat := as.size) : Subarray α :=
   if h₂ : stop ≤ as.size then
-     if h₁ : start ≤ stop then
-       { as := as, start := start, stop := stop, h₁ := h₁, h₂ := h₂ }
-     else
-       { as := as, start := stop, stop := stop, h₁ := Nat.le_refl _, h₂ := h₂ }
+    if h₁ : start ≤ stop then
+      { array := as, start := start, stop := stop,
+        start_le_stop := h₁, stop_le_array_size := h₂ }
+    else
+      { array := as, start := stop, stop := stop,
+        start_le_stop := Nat.le_refl _, stop_le_array_size := h₂ }
   else
-     if h₁ : start ≤ as.size then
-       { as := as, start := start, stop := as.size, h₁ := h₁, h₂ := Nat.le_refl _ }
-     else
-       { as := as, start := as.size, stop := as.size, h₁ := Nat.le_refl _, h₂ := Nat.le_refl _ }
+    if h₁ : start ≤ as.size then
+      { array := as,
+        start := start,
+        stop := as.size,
+        start_le_stop := h₁,
+        stop_le_array_size := Nat.le_refl _ }
+    else
+      { array := as,
+        start := as.size,
+        stop := as.size,
+        start_le_stop := Nat.le_refl _,
+        stop_le_array_size := Nat.le_refl _ }
 
 @[coe]
 def ofSubarray (s : Subarray α) : Array α := Id.run do

src/Init/Data/Array/Subarray/Split.lean

@@ -0,0 +1,71 @@
+/-
+Copyright (c) 2024 Lean FRO, LLC. All rights reserved.
+Released under Apache 2.0 license as described in the file LICENSE.
+Authors: David Thrane Christiansen
+-/
+
+prelude
+import Init.Data.Array.Basic
+import Init.Data.Array.Subarray
+import Init.Omega
+
+/-
+This module contains splitting operations on subarrays that crucially rely on `omega` for proof
+automation. Placing them in another module breaks an import cycle, because `omega` itself uses the
+array library.
+-/
+
+namespace Subarray
+/--
+Splits a subarray into two parts.
+-/
+def split (s : Subarray α) (i : Fin s.size.succ) : (Subarray α × Subarray α) :=
+  let ⟨i', isLt⟩ := i
+  have := s.start_le_stop
+  have := s.stop_le_array_size
+  have : i' ≤ s.stop - s.start := Nat.lt_succ.mp isLt
+  have : s.start + i' ≤ s.stop := by omega
+  have : s.start + i' ≤ s.array.size := by omega
+  have : s.start + i' ≤ s.stop := by
+    simp only [size] at isLt
+    omega
+  let pre := {s with
+    stop := s.start + i',
+    start_le_stop := by omega,
+    stop_le_array_size := by assumption
+  }
+  let post := {s with
+    start := s.start + i'
+    start_le_stop := by assumption
+  }
+  (pre, post)
+
+/--
+Removes the first `i` elements of the subarray. If there are `i` or fewer elements, the resulting
+subarray is empty.
+-/
+def drop (arr : Subarray α) (i : Nat) : Subarray α where
+  array := arr.array
+  start := min (arr.start + i) arr.stop
+  stop := arr.stop
+  start_le_stop := by
+    rw [Nat.min_def]
+    split <;> simp only [Nat.le_refl, *]
+  stop_le_array_size := arr.stop_le_array_size
+
+/--
+Keeps only the first `i` elements of the subarray. If there are `i` or fewer elements, the resulting
+subarray is empty.
+-/
+def take (arr : Subarray α) (i : Nat) : Subarray α where
+  array := arr.array
+  start := arr.start
+  stop := min (arr.start + i) arr.stop
+  start_le_stop := by
+    have := arr.start_le_stop
+    rw [Nat.min_def]
+    split <;> omega
+  stop_le_array_size := by
+    have := arr.stop_le_array_size
+    rw [Nat.min_def]
+    split <;> omega

src/Init/Data/BitVec/Basic.lean

@@ -1,7 +1,7 @@
 /-
 Copyright (c) 2024 Lean FRO, LLC. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
-Authors: Joe Hendrix, Wojciech Nawrocki, Leonardo de Moura, Mario Carneiro, Alex Keizer
+Authors: Joe Hendrix, Wojciech Nawrocki, Leonardo de Moura, Mario Carneiro, Alex Keizer, Harun Khan, Abdalrhman M Mohamed
 -/
 prelude
 import Init.Data.Fin.Basic
@@ -34,7 +34,7 @@ structure BitVec (w : Nat) where
   O(1), because we use `Fin` as the internal representation of a bitvector. -/
   toFin : Fin (2^w)
 
-@[deprecated] abbrev Std.BitVec := _root_.BitVec
+@[deprecated] protected abbrev Std.BitVec := _root_.BitVec
 
 -- We manually derive the `DecidableEq` instances for `BitVec` because
 -- we want to have builtin support for bit-vector literals, and we

src/Init/Data/BitVec/Lemmas.lean

@@ -1,7 +1,7 @@
 /-
 Copyright (c) 2023 Lean FRO, LLC. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
-Authors: Joe Hendrix
+Authors: Joe Hendrix, Harun Khan, Alex Keizer, Abdalrhman M Mohamed,
 -/
 prelude
 import Init.Data.Bool
@@ -817,9 +817,13 @@ Definition of bitvector addition as a nat.
   .ofFin x + y = .ofFin (x + y.toFin) := rfl
 @[simp] theorem add_ofFin (x : BitVec n) (y : Fin (2^n)) :
   x + .ofFin y = .ofFin (x.toFin + y) := rfl
-@[simp] theorem ofNat_add_ofNat {n} (x y : Nat) : x#n + y#n = (x + y)#n := by
+
+theorem ofNat_add {n} (x y : Nat) : (x + y)#n = x#n + y#n := by
   apply eq_of_toNat_eq ; simp [BitVec.ofNat]
 
+theorem ofNat_add_ofNat {n} (x y : Nat) : x#n + y#n = (x + y)#n :=
+  (ofNat_add x y).symm
+
 protected theorem add_assoc (x y z : BitVec n) : x + y + z = x + (y + z) := by
   apply eq_of_toNat_eq ; simp [Nat.add_assoc]
 
@@ -835,6 +839,15 @@ theorem truncate_add (x y : BitVec w) (h : i ≤ w) :
   have dvd : 2^i ∣ 2^w := Nat.pow_dvd_pow _ h
   simp [bv_toNat, h, Nat.mod_mod_of_dvd _ dvd]
 
+@[simp, bv_toNat] theorem toInt_add (x y : BitVec w) :
+  (x + y).toInt = (x.toInt + y.toInt).bmod (2^w) := by
+  simp [toInt_eq_toNat_bmod]
+
+theorem ofInt_add {n} (x y : Int) : BitVec.ofInt n (x + y) =
+    BitVec.ofInt n x + BitVec.ofInt n y := by
+  apply eq_of_toInt_eq
+  simp
+
 /-! ### sub/neg -/
 
 theorem sub_def {n} (x y : BitVec n) : x - y = .ofNat n (x.toNat + (2^n - y.toNat)) := by rfl
@@ -911,6 +924,15 @@ instance : Std.Associative (fun (x y : BitVec w) => x * y) := ⟨BitVec.mul_asso
 instance : Std.LawfulCommIdentity (fun (x y : BitVec w) => x * y) (1#w) where
   right_id := BitVec.mul_one
 
+@[simp, bv_toNat] theorem toInt_mul (x y : BitVec w) :
+  (x * y).toInt = (x.toInt * y.toInt).bmod (2^w) := by
+  simp [toInt_eq_toNat_bmod]
+
+theorem ofInt_mul {n} (x y : Int) : BitVec.ofInt n (x * y) =
+    BitVec.ofInt n x * BitVec.ofInt n y := by
+  apply eq_of_toInt_eq
+  simp
+
 /-! ### le and lt -/
 
 @[bv_toNat] theorem le_def (x y : BitVec n) :

src/Init/Data/Fin/Basic.lean

@@ -13,17 +13,40 @@ namespace Fin
 instance coeToNat : CoeOut (Fin n) Nat :=
   ⟨fun v => v.val⟩
 
+/--
+From the empty type `Fin 0`, any desired result `α` can be derived. This is simlar to `Empty.elim`.
+-/
 def elim0.{u} {α : Sort u} : Fin 0 → α
   | ⟨_, h⟩ => absurd h (not_lt_zero _)
 
+/--
+Returns the successor of the argument.
+
+The bound in the result type is increased:
+```
+(2 : Fin 3).succ = (3 : Fin 4)
+```
+This differs from addition, which wraps around:
+```
+(2 : Fin 3) + 1 = (0 : Fin 3)
+```
+-/
 def succ : Fin n → Fin n.succ
   | ⟨i, h⟩ => ⟨i+1, Nat.succ_lt_succ h⟩
 
 variable {n : Nat}
 
+/--
+Returns `a` modulo `n + 1` as a `Fin n.succ`.
+-/
 protected def ofNat {n : Nat} (a : Nat) : Fin n.succ :=
   ⟨a % (n+1), Nat.mod_lt _ (Nat.zero_lt_succ _)⟩
 
+/--
+Returns `a` modulo `n` as a `Fin n`.
+
+The assumption `n > 0` ensures that `Fin n` is nonempty.
+-/
 protected def ofNat' {n : Nat} (a : Nat) (h : n > 0) : Fin n :=
   ⟨a % n, Nat.mod_lt _ h⟩
 
@@ -33,12 +56,15 @@ private theorem mlt {b : Nat} : {a : Nat} → a < n → b % n < n
     have : n > 0 := Nat.lt_trans (Nat.zero_lt_succ _) h;
     Nat.mod_lt _ this
 
+/-- Addition modulo `n` -/
 protected def add : Fin n → Fin n → Fin n
   | ⟨a, h⟩, ⟨b, _⟩ => ⟨(a + b) % n, mlt h⟩
 
+/-- Multiplication modulo `n` -/
 protected def mul : Fin n → Fin n → Fin n
   | ⟨a, h⟩, ⟨b, _⟩ => ⟨(a * b) % n, mlt h⟩
 
+/-- Subtraction modulo `n` -/
 protected def sub : Fin n → Fin n → Fin n
   | ⟨a, h⟩, ⟨b, _⟩ => ⟨(a + (n - b)) % n, mlt h⟩
 

src/Init/Data/Int/Basic.lean

@@ -100,7 +100,7 @@ protected def neg (n : @& Int) : Int :=
   ```
 -/
 @[default_instance mid]
-instance : Neg Int where
+instance instNegInt : Neg Int where
   neg := Int.neg
 
 /-- Subtraction of two natural numbers. -/
@@ -173,13 +173,13 @@ inductive NonNeg : Int → Prop where
 /-- Definition of `a ≤ b`, encoded as `b - a ≥ 0`. -/
 protected def le (a b : Int) : Prop := NonNeg (b - a)
 
-instance : LE Int where
+instance instLEInt : LE Int where
   le := Int.le
 
 /-- Definition of `a < b`, encoded as `a + 1 ≤ b`. -/
 protected def lt (a b : Int) : Prop := (a + 1) ≤ b
 
-instance : LT Int where
+instance instLTInt : LT Int where
   lt := Int.lt
 
 set_option bootstrap.genMatcherCode false in

src/Init/Data/Int/DivModLemmas.lean

@@ -1054,19 +1054,39 @@ theorem emod_add_bmod_congr (x : Int) (n : Nat) : Int.bmod (x%n + y) n = Int.bmo
   simp [Int.emod_def, Int.sub_eq_add_neg]
   rw [←Int.mul_neg, Int.add_right_comm,  Int.bmod_add_mul_cancel]
 
+@[simp]
+theorem emod_mul_bmod_congr (x : Int) (n : Nat) : Int.bmod (x%n * y) n = Int.bmod (x * y) n := by
+  simp [Int.emod_def, Int.sub_eq_add_neg]
+  rw [←Int.mul_neg, Int.add_mul, Int.mul_assoc, Int.bmod_add_mul_cancel]
+
 @[simp]
 theorem bmod_add_bmod_congr : Int.bmod (Int.bmod x n + y) n = Int.bmod (x + y) n := by
+  rw [bmod_def x n]
+  split
+  case inl p =>
+    simp only [emod_add_bmod_congr]
+  case inr p =>
+    rw [Int.sub_eq_add_neg, Int.add_right_comm, ←Int.sub_eq_add_neg]
+    simp
+
+@[simp] theorem add_bmod_bmod : Int.bmod (x + Int.bmod y n) n = Int.bmod (x + y) n := by
+  rw [Int.add_comm x, Int.bmod_add_bmod_congr, Int.add_comm y]
+
+@[simp]
+theorem bmod_mul_bmod : Int.bmod (Int.bmod x n * y) n = Int.bmod (x * y) n := by
   rw [bmod_def x n]
   split
   case inl p =>
     simp
   case inr p =>
-    rw [Int.sub_eq_add_neg, Int.add_right_comm, ←Int.sub_eq_add_neg]
+    rw [Int.sub_mul, Int.sub_eq_add_neg, ← Int.mul_neg]
     simp
 
-@[simp]
-theorem add_bmod_bmod : Int.bmod (x + Int.bmod y n) n = Int.bmod (x + y) n := by
-  rw [Int.add_comm x, Int.bmod_add_bmod_congr, Int.add_comm y]
+@[simp] theorem mul_bmod_bmod : Int.bmod (x * Int.bmod y n) n = Int.bmod (x * y) n := by
+  rw [Int.mul_comm x, bmod_mul_bmod, Int.mul_comm x]
+
+theorem add_bmod (a b : Int) (n : Nat) : (a + b).bmod n = (a.bmod n + b.bmod n).bmod n := by
+  simp
 
 theorem emod_bmod {x : Int} {m : Nat} : bmod (x % m) m = bmod x m := by
   simp [bmod]

src/Init/Data/List/BasicAux.lean

@@ -12,60 +12,139 @@ namespace List
 /-! The following functions can't be defined at `Init.Data.List.Basic`, because they depend on `Init.Util`,
    and `Init.Util` depends on `Init.Data.List.Basic`. -/
 
-def get! [Inhabited α] : List α → Nat → α
+/--
+Returns the `i`-th element in the list (zero-based).
+
+If the index is out of bounds (`i ≥ as.length`), this function panics when executed, and returns
+`default`. See `get?` and `getD` for safer alternatives.
+-/
+def get! [Inhabited α] : (as : List α) → (i : Nat) → α
   | a::_,  0   => a
   | _::as, n+1 => get! as n
   | _,     _   => panic! "invalid index"
 
-def get? : List α → Nat → Option α
+/--
+Returns the `i`-th element in the list (zero-based).
+
+If the index is out of bounds (`i ≥ as.length`), this function returns `none`.
+Also see `get`, `getD` and `get!`.
+-/
+def get? : (as : List α) → (i : Nat) → Option α
   | a::_,  0   => some a
   | _::as, n+1 => get? as n
   | _,     _   => none
 
-def getD (as : List α) (idx : Nat) (a₀ : α) : α :=
-  (as.get? idx).getD a₀
+/--
+Returns the `i`-th element in the list (zero-based).
 
+If the index is out of bounds (`i ≥ as.length`), this function returns `fallback`.
+See also `get?` and `get!`.
+-/
+def getD (as : List α) (i : Nat) (fallback : α) : α :=
+  (as.get? i).getD fallback
+
+/--
+Returns the first element in the list.
+
+If the list is empty, this function panics when executed, and returns `default`.
+See `head` and `headD` for safer alternatives.
+-/
 def head! [Inhabited α] : List α → α
   | []   => panic! "empty list"
   | a::_ => a
 
+/--
+Returns the first element in the list.
+
+If the list is empty, this function returns `none`.
+Also see `headD` and `head!`.
+-/
 def head? : List α → Option α
   | []   => none
   | a::_ => some a
 
-def headD : List α → α → α
-  | [],   a₀ => a₀
+/--
+Returns the first element in the list.
+
+If the list is empty, this function returns `fallback`.
+Also see `head?` and `head!`.
+-/
+def headD : (as : List α) → (fallback : α) → α
+  | [],   fallback => fallback
   | a::_, _  => a
 
+/--
+Returns the first element of a non-empty list.
+-/
 def head : (as : List α) → as ≠ [] → α
   | a::_, _ => a
 
+/--
+Drops the first element of the list.
+
+If the list is empty, this function panics when executed, and returns the empty list.
+See `tail` and `tailD` for safer alternatives.
+-/
 def tail! : List α → List α
   | []    => panic! "empty list"
   | _::as => as
 
+/--
+Drops the first element of the list.
+
+If the list is empty, this function returns `none`.
+Also see `tailD` and `tail!`.
+-/
 def tail? : List α → Option (List α)
   | []    => none
   | _::as => some as
 
-def tailD : List α → List α → List α
-  | [],   as₀ => as₀
-  | _::as, _  => as
+/--
+Drops the first element of the list.
 
+If the list is empty, this function returns `fallback`.
+Also see `head?` and `head!`.
+-/
+def tailD (list fallback : List α) : List α :=
+  match list with
+  | [] => fallback
+  | _ :: tl => tl
+
+/--
+Returns the last element of a non-empty list.
+-/
 def getLast : ∀ (as : List α), as ≠ [] → α
   | [],       h => absurd rfl h
   | [a],      _ => a
   | _::b::as, _ => getLast (b::as) (fun h => List.noConfusion h)
 
+/--
+Returns the last element in the list.
+
+If the list is empty, this function panics when executed, and returns `default`.
+See `getLast` and `getLastD` for safer alternatives.
+-/
 def getLast! [Inhabited α] : List α → α
   | []    => panic! "empty list"
   | a::as => getLast (a::as) (fun h => List.noConfusion h)
 
+/--
+Returns the last element in the list.
+
+If the list is empty, this function returns `none`.
+Also see `getLastD` and `getLast!`.
+-/
 def getLast? : List α → Option α
   | []    => none
   | a::as => some (getLast (a::as) (fun h => List.noConfusion h))
 
-def getLastD : List α → α → α
+/--
+Returns the last element in the list.
+
+If the list is empty, this function returns `fallback`.
+Also see `getLast?` and `getLast!`.
+-/
+def getLastD : (as : List α) → (fallback : α) → α
   | [],   a₀ => a₀
   | a::as, _ => getLast (a::as) (fun h => List.noConfusion h)
 

src/Init/Data/List/Control.lean

@@ -40,6 +40,13 @@ Finally, we rarely use `mapM` with something that is not a `Monad`.
 Users that want to use `mapM` with `Applicative` should use `mapA` instead.
 -/
 
+/--
+Applies the monadic action `f` on every element in the list, left-to-right, and returns the list of
+results.
+
+See `List.forM` for the variant that discards the results.
+See `List.mapA` for the variant that works with `Applicative`.
+-/
 @[inline]
 def mapM {m : Type u → Type v} [Monad m] {α : Type w} {β : Type u} (f : α → m β) (as : List α) : m (List β) :=
   let rec @[specialize] loop
@@ -47,17 +54,42 @@ def mapM {m : Type u → Type v} [Monad m] {α : Type w} {β : Type u} (f : α
     | a :: as, bs => do loop as ((← f a)::bs)
   loop as []
 
+/--
+Applies the applicative action `f` on every element in the list, left-to-right, and returns the list of
+results.
+
+NB: If `m` is also a `Monad`, then using `mapM` can be more efficient.
+
+See `List.forA` for the variant that discards the results.
+See `List.mapM` for the variant that works with `Monad`.
+
+**Warning**: this function is not tail-recursive, meaning that it may fail with a stack overflow on long lists.
+-/
 @[specialize]
 def mapA {m : Type u → Type v} [Applicative m] {α : Type w} {β : Type u} (f : α → m β) : List α → m (List β)
   | []    => pure []
   | a::as => List.cons <$> f a <*> mapA f as
 
+/--
+Applies the monadic action `f` on every element in the list, left-to-right.
+
+See `List.mapM` for the variant that collects results.
+See `List.forA` for the variant that works with `Applicative`.
+-/
 @[specialize]
 protected def forM {m : Type u → Type v} [Monad m] {α : Type w} (as : List α) (f : α → m PUnit) : m PUnit :=
   match as with
   | []      => pure ⟨⟩
   | a :: as => do f a; List.forM as f
 
+/--
+Applies the applicative action `f` on every element in the list, left-to-right.
+
+NB: If `m` is also a `Monad`, then using `forM` can be more efficient.
+
+See `List.mapA` for the variant that collects results.
+See `List.forM` for the variant that works with `Monad`.
+-/
 @[specialize]
 def forA {m : Type u → Type v} [Applicative m] {α : Type w} (as : List α) (f : α → m PUnit) : m PUnit :=
   match as with
@@ -71,15 +103,27 @@ def filterAuxM {m : Type → Type v} [Monad m] {α : Type} (f : α → m Bool) :
     let b ← f h
     filterAuxM f t (cond b (h :: acc) acc)
 
+/--
+Applies the monadic predicate `p` on every element in the list, left-to-right, and returns those
+elements `x` for which `p x` returns `true`.
+-/
 @[inline]
-def filterM {m : Type → Type v} [Monad m] {α : Type} (f : α → m Bool) (as : List α) : m (List α) := do
-  let as ← filterAuxM f as []
+def filterM {m : Type → Type v} [Monad m] {α : Type} (p : α → m Bool) (as : List α) : m (List α) := do
+  let as ← filterAuxM p as []
   pure as.reverse
 
+/--
+Applies the monadic predicate `p` on every element in the list, right-to-left, and returns those
+elements `x` for which `p x` returns `true`.
+-/
 @[inline]
-def filterRevM {m : Type → Type v} [Monad m] {α : Type} (f : α → m Bool) (as : List α) : m (List α) :=
-  filterAuxM f as.reverse []
+def filterRevM {m : Type → Type v} [Monad m] {α : Type} (p : α → m Bool) (as : List α) : m (List α) :=
+  filterAuxM p as.reverse []
 
+/--
+Applies the monadic function `f` on every element `x` in the list, left-to-right, and returns those
+results `y` for which `f x` returns `some y`.
+-/
 @[inline]
 def filterMapM {m : Type u → Type v} [Monad m] {α β : Type u} (f : α → m (Option β)) (as : List α) : m (List β) :=
   let rec @[specialize] loop
@@ -90,6 +134,16 @@ def filterMapM {m : Type u → Type v} [Monad m] {α β : Type u} (f : α → m
       | some b => loop as (b::bs)
   loop as.reverse []
 
+/--
+Folds a monadic function over a list from left to right:
+```
+foldlM f x₀ [a, b, c] = do
+  let x₁ ← f x₀ a
+  let x₂ ← f x₁ b
+  let x₃ ← f x₂ c
+  pure x₃
+```
+-/
 @[specialize]
 protected def foldlM {m : Type u → Type v} [Monad m] {s : Type u} {α : Type w} : (f : s → α → m s) → (init : s) → List α → m s
   | _, s, []      => pure s
@@ -97,10 +151,26 @@ protected def foldlM {m : Type u → Type v} [Monad m] {s : Type u} {α : Type w
     let s' ← f s a
     List.foldlM f s' as
 
+/--
+Folds a monadic function over a list from right to left:
+```
+foldrM f x₀ [a, b, c] = do
+  let x₁ ← f c x₀
+  let x₂ ← f b x₁
+  let x₃ ← f a x₂
+  pure x₃
+```
+-/
 @[inline]
 def foldrM {m : Type u → Type v} [Monad m] {s : Type u} {α : Type w} (f : α → s → m s) (init : s) (l : List α) : m s :=
   l.reverse.foldlM (fun s a => f a s) init
 
+/--
+Maps `f` over the list and collects the results with `<|>`.
+```
+firstM f [a, b, c] = f a <|> f b <|> f c <|> failure
+```
+-/
 @[specialize]
 def firstM {m : Type u → Type v} [Alternative m] {α : Type w} {β : Type u} (f : α → m β) : List α → m β
   | []    => failure

src/Init/Data/Nat/Div.lean

@@ -28,7 +28,7 @@ protected def div (x y : @& Nat) : Nat :=
     0
 decreasing_by apply div_rec_lemma; assumption
 
-instance : Div Nat := ⟨Nat.div⟩
+instance instDiv : Div Nat := ⟨Nat.div⟩
 
 theorem div_eq (x y : Nat) : x / y = if 0 < y ∧ y ≤ x then (x - y) / y + 1 else 0 := by
   show Nat.div x y = _
@@ -90,7 +90,7 @@ protected def mod : @& Nat → @& Nat → Nat
   | 0, _ => 0
   | x@(_ + 1), y => Nat.modCore x y
 
-instance : Mod Nat := ⟨Nat.mod⟩
+instance instMod : Mod Nat := ⟨Nat.mod⟩
 
 protected theorem modCore_eq_mod (x y : Nat) : Nat.modCore x y = x % y := by
   cases x with

src/Init/Data/Nat/Gcd.lean

@@ -10,6 +10,24 @@ import Init.RCases
 
 namespace Nat
 
+/--
+Computes the greatest common divisor of two natural numbers.
+
+This reference implementation via the Euclidean algorithm
+is overridden in both the kernel and the compiler to efficiently
+evaluate using the "bignum" representation (see `Nat`).
+The definition provided here is the logical model
+(and it is soundness-critical that they coincide).
+
+The GCD of two natural numbers is the largest natural number
+that divides both arguments.
+In particular, the GCD of a number and `0` is the number itself:
+```
+example : Nat.gcd 10 15 = 5 := rfl
+example : Nat.gcd 0 5 = 5 := rfl
+example : Nat.gcd 7 0 = 7 := rfl
+```
+-/
 @[extern "lean_nat_gcd"]
 def gcd (m n : @& Nat) : Nat :=
   if m = 0 then

src/Init/Data/Option/Basic.lean

@@ -13,29 +13,38 @@ namespace Option
 deriving instance DecidableEq for Option
 deriving instance BEq for Option
 
-def toMonad [Monad m] [Alternative m] : Option α → m α
+/-- Lifts an optional value to any `Alternative`, sending `none` to `failure`. -/
+def getM [Alternative m] : Option α → m α
   | none     => failure
   | some a   => pure a
 
+@[deprecated getM] def toMonad [Monad m] [Alternative m] : Option α → m α :=
+  getM
+
 @[inline] def toBool : Option α → Bool
   | some _ => true
   | none   => false
 
+/-- Returns `true` on `some x` and `false` on `none`. -/
 @[inline] def isSome : Option α → Bool
   | some _ => true
   | none   => false
 
+/-- Returns `true` on `none` and `false` on `some x`. -/
 @[inline] def isNone : Option α → Bool
   | some _ => false
   | none   => true
 
+/--
+`x?.isEqSome y` is equivalent to `x? == some y`, but avoids an allocation.
+-/
 @[inline] def isEqSome [BEq α] : Option α → α → Bool
   | some a, b => a == b
   | none,   _ => false
 
 @[inline] protected def bind : Option α → (α → Option β) → Option β
   | none,   _ => none
-  | some a, b => b a
+  | some a, f => f a
 
 /-- Runs `f` on `o`'s value, if any, and returns its result, or else returns `none`.  -/
 @[inline] protected def bindM [Monad m] (f : α → m (Option β)) (o : Option α) : m (Option β) := do
@@ -44,6 +53,10 @@ def toMonad [Monad m] [Alternative m] : Option α → m α
   else
     return none
 
+/--
+Runs a monadic function `f` on an optional value.
+If the optional value is `none` the function is not called.
+-/
 @[inline] protected def mapM [Monad m] (f : α → m β) (o : Option α) : m (Option β) := do
   if let some a := o then
     return some (← f a)
@@ -53,18 +66,24 @@ def toMonad [Monad m] [Alternative m] : Option α → m α
 theorem map_id : (Option.map id : Option α → Option α) = id :=
   funext (fun o => match o with | none => rfl | some _ => rfl)
 
+/-- Keeps an optional value only if it satisfies the predicate `p`. -/
 @[always_inline, inline] protected def filter (p : α → Bool) : Option α → Option α
   | some a => if p a then some a else none
   | none   => none
 
+/-- Checks that an optional value satisfies a predicate `p` or is `none`. -/
 @[always_inline, inline] protected def all (p : α → Bool) : Option α → Bool
   | some a => p a
   | none   => true
 
+/-- Checks that an optional value is not `none` and the value satisfies a predicate `p`. -/
 @[always_inline, inline] protected def any (p : α → Bool) : Option α → Bool
   | some a => p a
   | none   => false
 
+/--
+Implementation of `OrElse`'s `<|>` syntax for `Option`.
+-/
 @[always_inline, macro_inline] protected def orElse : Option α → (Unit → Option α) → Option α
   | some a, _ => some a
   | none,   b => b ()

src/Init/Data/Ord.lean

@@ -114,7 +114,18 @@ by `cmp₂` to break the tie.
 @[inline] def compareLex (cmp₁ cmp₂ : α → β → Ordering) (a : α) (b : β) : Ordering :=
   (cmp₁ a b).then (cmp₂ a b)
 
+/--
+`Ord α` provides a computable total order on `α`, in terms of the
+`compare : α → α → Ordering` function.
+
+Typically instances will be transitive, reflexive, and antisymmetric,
+but this is not enforced by the typeclass.
+
+There is a derive handler, so appending `deriving Ord` to an inductive type or structure
+will attempt to create an `Ord` instance.
+-/
 class Ord (α : Type u) where
+  /-- Compare two elements in `α` using the comparator contained in an `[Ord α]` instance. -/
   compare : α → α → Ordering
 
 export Ord (compare)

src/Init/Data/Repr.lean

@@ -13,11 +13,24 @@ open Sum Subtype Nat
 
 open Std
 
+/--
+A typeclass that specifies the standard way of turning values of some type into `Format`.
+
+When rendered this `Format` should be as close as possible to something that can be parsed as the
+input value.
+-/
 class Repr (α : Type u) where
+  /--
+  Turn a value of type `α` into `Format` at a given precedence. The precedence value can be used
+  to avoid parentheses if they are not necessary.
+  -/
   reprPrec : α → Nat → Format
 
 export Repr (reprPrec)
 
+/--
+Turn `a` into `Format` using its `Repr` instance. The precedence level is initially set to 0.
+-/
 abbrev repr [Repr α] (a : α) : Format :=
   reprPrec a 0
 
@@ -103,6 +116,11 @@ instance {p : α → Prop} [Repr α] : Repr (Subtype p) where
 
 namespace Nat
 
+/-
+We have pure functions for calculating the decimal representation of a `Nat` (`toDigits`), but also
+a fast variant that handles small numbers (`USize`) via C code (`lean_string_of_usize`).
+-/
+
 def digitChar (n : Nat) : Char :=
   if n = 0 then '0' else
   if n = 1 then '1' else
@@ -133,6 +151,20 @@ def toDigitsCore (base : Nat) : Nat → Nat → List Char → List Char
 def toDigits (base : Nat) (n : Nat) : List Char :=
   toDigitsCore base (n+1) n []
 
+@[extern "lean_string_of_usize"]
+protected def _root_.USize.repr (n : @& USize) : String :=
+  (toDigits 10 n.toNat).asString
+
+/-- We statically allocate and memoize reprs for small natural numbers. -/
+private def reprArray : Array String := Id.run do
+  List.range 128 |>.map (·.toUSize.repr) |> Array.mk
+
+private def reprFast (n : Nat) : String :=
+  if h : n < 128 then Nat.reprArray.get ⟨n, h⟩ else
+  if h : n < USize.size then (USize.ofNatCore n h).repr
+  else (toDigits 10 n).asString
+
+@[implemented_by reprFast]
 protected def repr (n : Nat) : String :=
   (toDigits 10 n).asString
 
@@ -162,6 +194,32 @@ def toSuperDigits (n : Nat) : List Char :=
 def toSuperscriptString (n : Nat) : String :=
   (toSuperDigits n).asString
 
+def subDigitChar (n : Nat) : Char :=
+  if n = 0 then '₀' else
+  if n = 1 then '₁' else
+  if n = 2 then '₂' else
+  if n = 3 then '₃' else
+  if n = 4 then '₄' else
+  if n = 5 then '₅' else
+  if n = 6 then '₆' else
+  if n = 7 then '₇' else
+  if n = 8 then '₈' else
+  if n = 9 then '₉' else
+  '*'
+
+partial def toSubDigitsAux : Nat → List Char → List Char
+  | n, ds =>
+    let d  := subDigitChar <| n % 10;
+    let n' := n / 10;
+    if n' = 0 then d::ds
+    else toSubDigitsAux n' (d::ds)
+
+def toSubDigits (n : Nat) : List Char :=
+  toSubDigitsAux n []
+
+def toSubscriptString (n : Nat) : String :=
+  (toSubDigits n).asString
+
 end Nat
 
 instance : Repr Nat where

src/Init/Data/Stream.lean

@@ -94,7 +94,8 @@ instance : Stream (Subarray α) α where
   next? s :=
     if h : s.start < s.stop then
       have : s.start + 1 ≤ s.stop := Nat.succ_le_of_lt h
-      some (s.as.get ⟨s.start, Nat.lt_of_lt_of_le h s.h₂⟩, { s with start := s.start + 1, h₁ := this })
+      some (s.as.get ⟨s.start, Nat.lt_of_lt_of_le h s.stop_le_array_size⟩,
+        { s with start := s.start + 1, start_le_stop := this })
     else
       none
 

src/Init/MetaTypes.lean

@@ -68,38 +68,106 @@ namespace Simp
 
 def defaultMaxSteps := 100000
 
+/--
+The configuration for `simp`.
+Passed to `simp` using, for example, the `simp (config := {contextual := true})` syntax.
+
+See also `Lean.Meta.Simp.neutralConfig`.
+-/
 structure Config where
+  /--
+  The maximum number of subexpressions to visit when performing simplification.
+  The default is 100000.
+  -/
   maxSteps          : Nat  := defaultMaxSteps
+  /--
+  When simp discharges side conditions for conditional lemmas, it can recursively apply simplification.
+  The `maxDischargeDepth` (default: 2) is the maximum recursion depth when recursively applying simplification to side conditions.
+  -/
   maxDischargeDepth : Nat  := 2
+  /--
+  When `contextual` is true (default: `false`) and simplification encounters an implication `p → q`
+  it includes `p` as an additional simp lemma when simplifying `q`.
+  -/
   contextual        : Bool := false
+  /--
+  When true (default: `true`) then the simplifier caches the result of simplifying each subexpression, if possible.
+  -/
   memoize           : Bool := true
+  /--
+  When `singlePass` is `true` (default: `false`), the simplifier runs through a single round of simplification,
+  which consists of running pre-methods, recursing using congruence lemmas, and then running post-methods.
+  Otherwise, when it is `false`, it iteratively applies this simplification procedure.
+  -/
   singlePass        : Bool := false
-  /-- `let x := v; e[x]` reduces to `e[v]`. -/
+  /--
+  When `true` (default: `true`), performs zeta reduction of let expressions.
+  That is, `let x := v; e[x]` reduces to `e[v]`.
+  See also `zetaDelta`.
+  -/
   zeta              : Bool := true
+  /--
+  When `true` (default: `true`), performs beta reduction of applications of `fun` expressions.
+  That is, `(fun x => e[x]) v` reduces to `e[v]`.
+  -/
   beta              : Bool := true
+  /--
+  TODO (currently unimplemented). When `true` (default: `true`), performs eta reduction for `fun` expressions.
+  That is, `(fun x => f x)` reduces to `f`.
+  -/
   eta               : Bool := true
+  /--
+  Configures how to determine definitional equality between two structure instances.
+  See documentation for `Lean.Meta.EtaStructMode`.
+  -/
   etaStruct         : EtaStructMode := .all
+  /--
+  When `true` (default: `true`), reduces `match` expressions applied to constructors.
+  -/
   iota              : Bool := true
+  /--
+  When `true` (default: `true`), reduces projections of structure constructors.
+  -/
   proj              : Bool := true
+  /--
+  When `true` (default: `false`), rewrites a proposition `p` to `True` or `False` by inferring
+  a `Decidable p` instance and reducing it.
+  -/
   decide            : Bool := false
+  /--  When `true` (default: `false`), simplifies simple arithmetic expressions. -/
   arith             : Bool := false
+  /--
+  When `true` (default: `false`), unfolds definitions.
+  This can be enabled using the `simp!` syntax.
+  -/
   autoUnfold        : Bool := false
   /--
-    If `dsimp := true`, then switches to `dsimp` on dependent arguments where there is no congruence theorem that allows
-    `simp` to visit them. If `dsimp := false`, then argument is not visited.
+  When `true` (default: `true`) then switches to `dsimp` on dependent arguments
+  if there is no congruence theorem that would allow `simp` to visit them.
+  When `dsimp` is `false`, then the argument is not visited.
   -/
   dsimp             : Bool := true
-  /-- If `failIfUnchanged := true`, then calls to `simp`, `dsimp`, or `simp_all`
-  will fail if they do not make progress. -/
+  /--
+  If `failIfUnchanged` is `true` (default: `true`), then calls to `simp`, `dsimp`, or `simp_all`
+  will fail if they do not make progress.
+  -/
   failIfUnchanged   : Bool := true
-  /-- If `ground := true`, then ground terms are reduced. A term is ground when
-  it does not contain free or meta variables. Reduction is interrupted at a function application `f ...`
-  if `f` is marked to not be unfolded. -/
+  /--
+  If `ground` is `true` (default: `false`), then ground terms are reduced.
+  A term is ground when it does not contain free or meta variables.
+  Reduction is interrupted at a function application `f ...` if `f` is marked to not be unfolded.
+  Ground term reduction applies `@[seval]` lemmas.
+  -/
   ground            : Bool := false
-  /-- If `unfoldPartialApp := true`, then calls to `simp`, `dsimp`, or `simp_all`
-  will unfold even partial applications of `f` when we request `f` to be unfolded. -/
+  /--
+  If `unfoldPartialApp` is `true` (default: `false`), then calls to `simp`, `dsimp`, or `simp_all`
+  will unfold even partial applications of `f` when we request `f` to be unfolded.
+  -/
   unfoldPartialApp  : Bool := false
-  /-- Given a local context containing entry `x : t := e`, free variable `x` reduces to `e`. -/
+  /--
+  When `true` (default: `false`), local definitions are unfolded.
+  That is, given a local context containing entry `x : t := e`, the free variable `x` reduces to `e`.
+  -/
   zetaDelta         : Bool := false
   deriving Inhabited, BEq
 
@@ -107,6 +175,9 @@ structure Config where
 structure ConfigCtx extends Config where
   contextual := true
 
+/--
+A neutral configuration for `simp`, turning off all reductions and other built-in simplifications.
+-/
 def neutralConfig : Simp.Config := {
   zeta              := false
   beta              := false

src/Init/Notation.lean

@@ -552,15 +552,52 @@ except that it doesn't print an empty diagnostic.
 -/
 syntax (name := runMeta) "run_meta " doSeq : command
 
-/-- Element that can be part of a `#guard_msgs` specification. -/
-syntax guardMsgsSpecElt := &"drop"? (&"info" <|> &"warning" <|> &"error" <|> &"all")
+set_option linter.missingDocs false in
+syntax guardMsgsFilterSeverity := &"info" <|> &"warning" <|> &"error" <|> &"all"
 
-/-- Specification for `#guard_msgs` command. -/
+/--
+A message filter specification for `#guard_msgs`.
+- `info`, `warning`, `error`: capture messages with the given severity level.
+- `all`: capture all messages (the default).
+- `drop info`, `drop warning`, `drop error`: drop messages with the given severity level.
+- `drop all`: drop every message.
+These filters are processed in left-to-right order.
+-/
+syntax guardMsgsFilter := &"drop"? guardMsgsFilterSeverity
+
+set_option linter.missingDocs false in
+syntax guardMsgsWhitespaceArg := &"exact" <|> &"normalized" <|> &"lax"
+
+/--
+Whitespace handling for `#guard_msgs`:
+- `whitespace := exact` requires an exact whitespace match.
+- `whitespace := normalized` converts all newline characters to a space before matching
+  (the default). This allows breaking long lines.
+- `whitespace := lax` collapses whitespace to a single space before matching.
+In all cases, leading and trailing whitespace is trimmed before matching.
+-/
+syntax guardMsgsWhitespace := &"whitespace" " := " guardMsgsWhitespaceArg
+
+set_option linter.missingDocs false in
+syntax guardMsgsOrderingArg := &"exact" <|> &"sorted"
+
+/--
+Message ordering for `#guard_msgs`:
+- `ordering := exact` uses the exact ordering of the messages (the default).
+- `ordering := sorted` sorts the messages in lexicographic order.
+  This helps with testing commands that are non-deterministic in their ordering.
+-/
+syntax guardMsgsOrdering := &"ordering" " := " guardMsgsOrderingArg
+
+set_option linter.missingDocs false in
+syntax guardMsgsSpecElt := guardMsgsFilter <|> guardMsgsWhitespace <|> guardMsgsOrdering
+
+set_option linter.missingDocs false in
 syntax guardMsgsSpec := "(" guardMsgsSpecElt,* ")"
 
 /--
-`#guard_msgs` captures the messages generated by another command and checks that they
-match the contents of the docstring attached to the `#guard_msgs` command.
+`/-- ... -/ #guard_msgs in cmd` captures the messages generated by the command `cmd`
+and checks that they match the contents of the docstring.
 
 Basic example:
 ```lean
@@ -570,10 +607,10 @@ error: unknown identifier 'x'
 #guard_msgs in
 example : α := x
 ```
-This checks that there is such an error and then consumes the message entirely.
+This checks that there is such an error and then consumes the message.
 
-By default, the command intercepts all messages, but there is a way to specify which types
-of messages to consider. For example, we can select only warnings:
+By default, the command captures all messages, but the filter condition can be adjusted.
+For example, we can select only warnings:
 ```lean
 /--
 warning: declaration uses 'sorry'
@@ -586,29 +623,37 @@ or only errors
 #guard_msgs(error) in
 example : α := sorry
 ```
-In this last example, since the message is not intercepted there is a warning on `sorry`.
+In the previous example, since warnings are not captured there is a warning on `sorry`.
 We can drop the warning completely with
 ```lean
 #guard_msgs(error, drop warning) in
 example : α := sorry
 ```
 
-Syntax description:
+In general, `#guard_msgs` accepts a comma-separated list of configuration clauses in parentheses:
 ```
-#guard_msgs (drop? info|warning|error|all,*)? in cmd
+#guard_msgs (configElt,*) in cmd
 ```
+By default, the configuration list is `(all, whitespace := normalized, ordering := exact)`.
 
-If there is no specification, `#guard_msgs` intercepts all messages.
-Otherwise, if there is one, the specification is considered in left-to-right order, and the first
-that applies chooses the outcome of the message:
-- `info`, `warning`, `error`: intercept a message with the given severity level.
-- `all`: intercept any message (so `#guard_msgs in cmd` and `#guard_msgs (all) in cmd`
-  are equivalent).
-- `drop info`, `drop warning`, `drop error`: intercept a message with the given severity
-  level and then drop it. These messages are not checked.
-- `drop all`: intercept a message and drop it.
+Message filters (processed in left-to-right order):
+- `info`, `warning`, `error`: capture messages with the given severity level.
+- `all`: capture all messages (the default).
+- `drop info`, `drop warning`, `drop error`: drop messages with the given severity level.
+- `drop all`: drop every message.
 
-For example, `#guard_msgs (error, drop all) in cmd` means to check warnings and then drop
+Whitespace handling (after trimming leading and trailing whitespace):
+- `whitespace := exact` requires an exact whitespace match.
+- `whitespace := normalized` converts all newline characters to a space before matching
+  (the default). This allows breaking long lines.
+- `whitespace := lax` collapses whitespace to a single space before matching.
+
+Message ordering:
+- `ordering := exact` uses the exact ordering of the messages (the default).
+- `ordering := sorted` sorts the messages in lexicographic order.
+  This helps with testing commands that are non-deterministic in their ordering.
+
+For example, `#guard_msgs (error, drop all) in cmd` means to check warnings and drop
 everything else.
 -/
 syntax (name := guardMsgsCmd)

src/Init/Prelude.lean

@@ -477,6 +477,8 @@ and `Prod.snd p` respectively. You can also write `p.fst` and `p.snd`.
 For more information: [Constructors with Arguments](https://lean-lang.org/theorem_proving_in_lean4/inductive_types.html?highlight=Prod#constructors-with-arguments)
 -/
 structure Prod (α : Type u) (β : Type v) where
+  /-- Constructs a pair from two terms. -/
+  mk ::
   /-- The first projection out of a pair. if `p : α × β` then `p.1 : α`. -/
   fst : α
   /-- The second projection out of a pair. if `p : α × β` then `p.2 : β`. -/
@@ -1096,7 +1098,7 @@ class OfNat (α : Type u) (_ : Nat) where
   ofNat : α
 
 @[default_instance 100] /- low prio -/
-instance (n : Nat) : OfNat Nat n where
+instance instOfNatNat (n : Nat) : OfNat Nat n where
   ofNat := n
 
 /-- `LE α` is the typeclass which supports the notation `x ≤ y` where `x y : α`.-/
@@ -1430,31 +1432,31 @@ class ShiftRight (α : Type u) where
   shiftRight : α → α → α
 
 @[default_instance]
-instance [Add α] : HAdd α α α where
+instance instHAdd [Add α] : HAdd α α α where
   hAdd a b := Add.add a b
 
 @[default_instance]
-instance [Sub α] : HSub α α α where
+instance instHSub [Sub α] : HSub α α α where
   hSub a b := Sub.sub a b
 
 @[default_instance]
-instance [Mul α] : HMul α α α where
+instance instHMul [Mul α] : HMul α α α where
   hMul a b := Mul.mul a b
 
 @[default_instance]
-instance [Div α] : HDiv α α α where
+instance instHDiv [Div α] : HDiv α α α where
   hDiv a b := Div.div a b
 
 @[default_instance]
-instance [Mod α] : HMod α α α where
+instance instHMod [Mod α] : HMod α α α where
   hMod a b := Mod.mod a b
 
 @[default_instance]
-instance [Pow α β] : HPow α β α where
+instance instHPow [Pow α β] : HPow α β α where
   hPow a b := Pow.pow a b
 
 @[default_instance]
-instance [NatPow α] : Pow α Nat where
+instance instPowNat [NatPow α] : Pow α Nat where
   pow a n := NatPow.pow a n
 
 @[default_instance]
@@ -1521,7 +1523,7 @@ protected def Nat.add : (@& Nat) → (@& Nat) → Nat
   | a, Nat.zero   => a
   | a, Nat.succ b => Nat.succ (Nat.add a b)
 
-instance : Add Nat where
+instance instAddNat : Add Nat where
   add := Nat.add
 
 /- We mark the following definitions as pattern to make sure they can be used in recursive equations,
@@ -1541,7 +1543,7 @@ protected def Nat.mul : (@& Nat) → (@& Nat) → Nat
   | _, 0          => 0
   | a, Nat.succ b => Nat.add (Nat.mul a b) a
 
-instance : Mul Nat where
+instance instMulNat : Mul Nat where
   mul := Nat.mul
 
 set_option bootstrap.genMatcherCode false in
@@ -1557,7 +1559,7 @@ protected def Nat.pow (m : @& Nat) : (@& Nat) → Nat
   | 0      => 1
   | succ n => Nat.mul (Nat.pow m n) m
 
-instance : NatPow Nat := ⟨Nat.pow⟩
+instance instNatPowNat : NatPow Nat := ⟨Nat.pow⟩
 
 set_option bootstrap.genMatcherCode false in
 /--
@@ -1634,14 +1636,14 @@ protected inductive Nat.le (n : Nat) : Nat → Prop
   /-- If `n ≤ m`, then `n ≤ m + 1`. -/
   | step {m} : Nat.le n m → Nat.le n (succ m)
 
-instance : LE Nat where
+instance instLENat : LE Nat where
   le := Nat.le
 
 /-- The strict less than relation on natural numbers is defined as `n < m := n + 1 ≤ m`. -/
 protected def Nat.lt (n m : Nat) : Prop :=
   Nat.le (succ n) m
 
-instance : LT Nat where
+instance instLTNat : LT Nat where
   lt := Nat.lt
 
 theorem Nat.not_succ_le_zero : ∀ (n : Nat), LE.le (succ n) 0 → False
@@ -1793,7 +1795,7 @@ protected def Nat.sub : (@& Nat) → (@& Nat) → Nat
   | a, 0      => a
   | a, succ b => pred (Nat.sub a b)
 
-instance : Sub Nat where
+instance instSubNat : Sub Nat where
   sub := Nat.sub
 
 /--
@@ -1820,6 +1822,8 @@ It is the "canonical type with `n` elements".
 -/
 @[pp_using_anonymous_constructor]
 structure Fin (n : Nat) where
+  /-- Creates a `Fin n` from `i : Nat` and a proof that `i < n`. -/
+  mk ::
   /-- If `i : Fin n`, then `i.val : ℕ` is the described number. It can also be
   written as `i.1` or just `i` when the target type is known. -/
   val  : Nat
@@ -3357,7 +3361,7 @@ protected def seqRight (x : EStateM ε σ α) (y : Unit → EStateM ε σ β) :
   | Result.error e s => Result.error e s
 
 @[always_inline]
-instance : Monad (EStateM ε σ) where
+instance instMonad : Monad (EStateM ε σ) where
   bind     := EStateM.bind
   pure     := EStateM.pure
   map      := EStateM.map

src/Init/System/IO.lean

@@ -311,6 +311,8 @@ Note that EOF does not actually close a stream, so further reads may block and r
   -/
   getLine : IO String
   putStr  : String → IO Unit
+  /-- Returns true if a stream refers to a Windows console or Unix terminal. -/
+  isTty   : BaseIO Bool
   deriving Inhabited
 
 open FS
@@ -360,6 +362,9 @@ Will succeed even if no lock has been acquired.
 -/
 @[extern "lean_io_prim_handle_unlock"] opaque unlock (h : @& Handle) : IO Unit
 
+/-- Returns true if a handle refers to a Windows console or Unix terminal. -/
+@[extern "lean_io_prim_handle_is_tty"] opaque isTty (h : @& Handle) : BaseIO Bool
+
 @[extern "lean_io_prim_handle_flush"] opaque flush (h : @& Handle) : IO Unit
 /-- Rewinds the read/write cursor to the beginning of the handle. -/
 @[extern "lean_io_prim_handle_rewind"] opaque rewind (h : @& Handle) : IO Unit
@@ -743,36 +748,37 @@ namespace FS
 namespace Stream
 
 @[export lean_stream_of_handle]
-def ofHandle (h : Handle) : Stream := {
-  flush   := Handle.flush h,
-  read    := Handle.read h,
-  write   := Handle.write h,
-  getLine := Handle.getLine h,
-  putStr  := Handle.putStr h,
-}
+def ofHandle (h : Handle) : Stream where
+  flush   := Handle.flush h
+  read    := Handle.read h
+  write   := Handle.write h
+  getLine := Handle.getLine h
+  putStr  := Handle.putStr h
+  isTty   := Handle.isTty h
 
 structure Buffer where
   data : ByteArray := ByteArray.empty
   pos  : Nat := 0
 
-def ofBuffer (r : Ref Buffer) : Stream := {
-  flush   := pure (),
+def ofBuffer (r : Ref Buffer) : Stream where
+  flush   := pure ()
   read    := fun n => r.modifyGet fun b =>
     let data := b.data.extract b.pos (b.pos + n.toNat)
-    (data, { b with pos := b.pos + data.size }),
+    (data, { b with pos := b.pos + data.size })
   write   := fun data => r.modify fun b =>
     -- set `exact` to `false` so that repeatedly writing to the stream does not impose quadratic run time
-    { b with data := data.copySlice 0 b.data b.pos data.size false, pos := b.pos + data.size },
+    { b with data := data.copySlice 0 b.data b.pos data.size false, pos := b.pos + data.size }
   getLine := r.modifyGet fun b =>
     let pos := match b.data.findIdx? (start := b.pos) fun u => u == 0 || u = '\n'.toNat.toUInt8 with
       -- include '\n', but not '\0'
       | some pos => if b.data.get! pos == 0 then pos else pos + 1
       | none     => b.data.size
-    (String.fromUTF8Unchecked <| b.data.extract b.pos pos, { b with pos := pos }),
+    (String.fromUTF8Unchecked <| b.data.extract b.pos pos, { b with pos := pos })
   putStr  := fun s => r.modify fun b =>
     let data := s.toUTF8
-    { b with data := data.copySlice 0 b.data b.pos data.size false, pos := b.pos + data.size },
-}
+    { b with data := data.copySlice 0 b.data b.pos data.size false, pos := b.pos + data.size }
+  isTty   := pure false
+
 end Stream
 
 /-- Run action with `stdin` emptied and `stdout+stderr` captured into a `String`. -/
@@ -802,7 +808,7 @@ class Eval (α : Type u) where
   -- We take `Unit → α` instead of `α` because ‵α` may contain effectful debugging primitives (e.g., `dbg_trace`)
   eval : (Unit → α) → (hideUnit : Bool := true) → IO Unit
 
-instance [ToString α] : Eval α where
+instance instEval [ToString α] : Eval α where
   eval a _ := IO.println (toString (a ()))
 
 instance [Repr α] : Eval α where

src/Init/WF.lean

@@ -9,7 +9,18 @@ import Init.Data.Nat.Basic
 
 universe u v
 
+/--
+`Acc` is the accessibility predicate. Given some relation `r` (e.g. `<`) and a value `x`,
+`Acc r x` means that `x` is accessible through `r`:
+
+`x` is accessible if there exists no infinite sequence `... < y₂ < y₁ < y₀ < x`.
+-/
 inductive Acc {α : Sort u} (r : α → α → Prop) : α → Prop where
+  /--
+  A value is accessible if for all `y` such that `r y x`, `y` is also accessible.
+  Note that if there exists no `y` such that `r y x`, then `x` is accessible. Such an `x` is called a
+  _base case_.
+  -/
   | intro (x : α) (h : (y : α) → r y x → Acc r y) : Acc r x
 
 noncomputable abbrev Acc.ndrec.{u1, u2} {α : Sort u2} {r : α → α → Prop} {C : α → Sort u1}
@@ -31,6 +42,14 @@ def inv {x y : α} (h₁ : Acc r x) (h₂ : r y x) : Acc r y :=
 
 end Acc
 
+/--
+A relation `r` is `WellFounded` if all elements of `α` are accessible within `r`.
+If a relation is `WellFounded`, it does not allow for an infinite descent along the relation.
+
+If the arguments of the recursive calls in a function definition decrease according to
+a well founded relation, then the function terminates.
+Well-founded relations are sometimes called _Artinian_ or said to satisfy the “descending chain condition”.
+-/
 inductive WellFounded {α : Sort u} (r : α → α → Prop) : Prop where
   | intro (h : ∀ a, Acc r a) : WellFounded r
 

src/Lean/Compiler/Main.lean

@@ -12,7 +12,8 @@ Run the code generation pipeline for all declarations in `declNames`
 that fulfill the requirements of `shouldGenerateCode`.
 -/
 def compile (declNames : Array Name) : CoreM Unit := do profileitM Exception "compiler new" (← getOptions) do
-  discard <| LCNF.compile declNames
+  withTraceNode `Compiler (fun _ => return m!"compiling: {declNames}") do
+    discard <| LCNF.compile declNames
 
 builtin_initialize
   registerTraceClass `Compiler

src/Lean/CoreM.lean

@@ -177,6 +177,13 @@ instance : MonadTrace CoreM where
 def restore (b : State) : CoreM Unit :=
   modify fun s => { s with env := b.env, messages := b.messages, infoState := b.infoState }
 
+/--
+Restores full state including sources for unique identifiers. Only intended for incremental reuse
+between elaboration runs, not for backtracking within a single run.
+-/
+def restoreFull (b : State) : CoreM Unit :=
+  set b
+
 private def mkFreshNameImp (n : Name) : CoreM Name := do
   let fresh ← modifyGet fun s => (s.nextMacroScope, { s with nextMacroScope := s.nextMacroScope + 1 })
   return addMacroScope (← getEnv).mainModule n fresh
@@ -245,6 +252,13 @@ def resetMessageLog : CoreM Unit :=
 def getMessageLog : CoreM MessageLog :=
   return (← get).messages
 
+/--
+Returns the current log and then resets its messages but does NOT reset `MessageLog.hadErrors`. Used
+for incremental reporting during elaboration of a single command.
+-/
+def getAndEmptyMessageLog : CoreM MessageLog :=
+  modifyGet fun log => ({ log with msgs := {} }, log)
+
 instance : MonadLog CoreM where
   getRef      := getRef
   getFileMap  := return (← read).fileMap
@@ -330,10 +344,13 @@ opaque compileDeclsNew (declNames : List Name) : CoreM Unit
 
 def compileDecl (decl : Declaration) : CoreM Unit := do
   let opts ← getOptions
+  let decls := Compiler.getDeclNamesForCodeGen decl
   if compiler.enableNew.get opts then
-    compileDeclsNew (Compiler.getDeclNamesForCodeGen decl)
-  match (← getEnv).compileDecl opts decl with
-  | Except.ok env   => setEnv env
+    compileDeclsNew decls
+  let res ← withTraceNode `compiler (fun _ => return m!"compiling old: {decls}") do
+    return (← getEnv).compileDecl opts decl
+  match res with
+  | Except.ok env => setEnv env
   | Except.error (KernelException.other msg) =>
     checkUnsupported decl -- Generate nicer error message for unsupported recursors and axioms
     throwError msg

src/Lean/Data/HashMap.lean

@@ -122,7 +122,7 @@ def expand [Hashable α] (size : Nat) (buckets : HashMapBucket α β) : HashMapI
     let ⟨i, h⟩ := mkIdx (hash a) buckets.property
     let bkt    := buckets.val[i]
     if let some b := bkt.find? a then
-      (m, some b)
+      (⟨size, buckets⟩, some b)
     else
       let size'    := size + 1
       let buckets' := buckets.update i (AssocList.cons a b bkt) h
@@ -137,8 +137,10 @@ def erase [BEq α] [Hashable α] (m : HashMapImp α β) (a : α) : HashMapImp α
   | ⟨ size, buckets ⟩ =>
     let ⟨i, h⟩ := mkIdx (hash a) buckets.property
     let bkt    := buckets.val[i]
-    if bkt.contains a then ⟨size - 1, buckets.update i (bkt.erase a) h⟩
-    else m
+    if bkt.contains a then
+      ⟨size - 1, buckets.update i (bkt.erase a) h⟩
+    else
+      ⟨size, buckets⟩
 
 inductive WellFormed [BEq α] [Hashable α] : HashMapImp α β → Prop where
   | mkWff          : ∀ n,                    WellFormed (mkHashMapImp n)

src/Lean/Data/HashSet.lean

@@ -112,8 +112,10 @@ def erase [BEq α] [Hashable α] (m : HashSetImp α) (a : α) : HashSetImp α :=
   | ⟨ size, buckets ⟩ =>
     let ⟨i, h⟩ := mkIdx (hash a) buckets.property
     let bkt    := buckets.val[i]
-    if bkt.contains a then ⟨size - 1, buckets.update i (bkt.erase a) h⟩
-    else m
+    if bkt.contains a then
+      ⟨size - 1, buckets.update i (bkt.erase a) h⟩
+    else
+      ⟨size, buckets⟩
 
 inductive WellFormed [BEq α] [Hashable α] : HashSetImp α → Prop where
   | mkWff     : ∀ n,                  WellFormed (mkHashSetImp n)

src/Lean/Data/Lsp/LanguageFeatures.lean

@@ -324,7 +324,7 @@ inductive SemanticTokenType where
   | decorator
   -- Extensions
   | leanSorryLike
-  deriving ToJson, FromJson
+  deriving ToJson, FromJson, BEq, Hashable
 
 -- must be in the same order as the constructors
 def SemanticTokenType.names : Array String :=

src/Lean/Elab/App.lean

@@ -1194,6 +1194,17 @@ private def addLValArg (baseName : Name) (fullName : Name) (e : Expr) (args : Ar
           argIdx := argIdx + 1
     throwError "invalid field notation, function '{fullName}' does not have argument with type ({baseName} ...) that can be used, it must be explicit or implicit with a unique name"
 
+/-- Adds the `TermInfo` for the field of a projection. See `Lean.Parser.Term.identProjKind`. -/
+private def addProjTermInfo
+    (stx            : Syntax)
+    (e              : Expr)
+    (expectedType?  : Option Expr := none)
+    (lctx?          : Option LocalContext := none)
+    (elaborator     : Name := Name.anonymous)
+    (isBinder force : Bool := false)
+    : TermElabM Expr :=
+  addTermInfo (Syntax.node .none Parser.Term.identProjKind #[stx]) e expectedType? lctx? elaborator isBinder force
+
 private def elabAppLValsAux (namedArgs : Array NamedArg) (args : Array Arg) (expectedType? : Option Expr) (explicit ellipsis : Bool)
     (f : Expr) (lvals : List LVal) : TermElabM Expr :=
   let rec loop : Expr → List LVal → TermElabM Expr
@@ -1214,7 +1225,7 @@ private def elabAppLValsAux (namedArgs : Array NamedArg) (args : Array Arg) (exp
         if isPrivateNameFromImportedModule (← getEnv) info.projFn then
           throwError "field '{fieldName}' from structure '{structName}' is private"
         let projFn ← mkConst info.projFn
-        let projFn ← addTermInfo lval.getRef projFn
+        let projFn ← addProjTermInfo lval.getRef projFn
         if lvals.isEmpty then
           let namedArgs ← addNamedArg namedArgs { name := `self, val := Arg.expr f }
           elabAppArgs projFn namedArgs args expectedType? explicit ellipsis
@@ -1226,7 +1237,7 @@ private def elabAppLValsAux (namedArgs : Array NamedArg) (args : Array Arg) (exp
     | LValResolution.const baseStructName structName constName =>
       let f ← if baseStructName != structName then mkBaseProjections baseStructName structName f else pure f
       let projFn ← mkConst constName
-      let projFn ← addTermInfo lval.getRef projFn
+      let projFn ← addProjTermInfo lval.getRef projFn
       if lvals.isEmpty then
         let projFnType ← inferType projFn
         let (args, namedArgs) ← addLValArg baseStructName constName f args namedArgs projFnType
@@ -1235,7 +1246,7 @@ private def elabAppLValsAux (namedArgs : Array NamedArg) (args : Array Arg) (exp
         let f ← elabAppArgs projFn #[] #[Arg.expr f] (expectedType? := none) (explicit := false) (ellipsis := false)
         loop f lvals
     | LValResolution.localRec baseName fullName fvar =>
-      let fvar ← addTermInfo lval.getRef fvar
+      let fvar ← addProjTermInfo lval.getRef fvar
       if lvals.isEmpty then
         let fvarType ← inferType fvar
         let (args, namedArgs) ← addLValArg baseName fullName f args namedArgs fvarType

src/Lean/Elab/BuiltinCommand.lean

@@ -119,64 +119,6 @@ private partial def elabChoiceAux (cmds : Array Syntax) (i : Nat) : CommandElabM
 @[builtin_command_elab choice] def elabChoice : CommandElab := fun stx =>
   elabChoiceAux stx.getArgs 0
 
-/-- Declares one or more universe variables.
-
-`universe u v`
-
-`Prop`, `Type`, `Type u` and `Sort u` are types that classify other types, also known as
-*universes*. In `Type u` and `Sort u`, the variable `u` stands for the universe's *level*, and a
-universe at level `u` can only classify universes that are at levels lower than `u`. For more
-details on type universes, please refer to [the relevant chapter of Theorem Proving in Lean][tpil
-universes].
-
-Just as type arguments allow polymorphic definitions to be used at many different types, universe
-parameters, represented by universe variables, allow a definition to be used at any required level.
-While Lean mostly handles universe levels automatically, declaring them explicitly can provide more
-control when writing signatures. The `universe` keyword allows the declared universe variables to be
-used in a collection of definitions, and Lean will ensure that these definitions use them
-consistently.
-
-[tpil universes]: https://lean-lang.org/theorem_proving_in_lean4/dependent_type_theory.html#types-as-objects
-(Type universes on Theorem Proving in Lean)
-
-```lean
-/- Explicit type-universe parameter. -/
-def id₁.{u} (α : Type u) (a : α) := a
-
-/- Implicit type-universe parameter, equivalent to `id₁`.
-  Requires option `autoImplicit true`, which is the default. -/
-def id₂ (α : Type u) (a : α) := a
-
-/- Explicit standalone universe variable declaration, equivalent to `id₁` and `id₂`. -/
-universe u
-def id₃ (α : Type u) (a : α) := a
-```
-
-On a more technical note, using a universe variable only in the right-hand side of a definition
-causes an error if the universe has not been declared previously.
-
-```lean
-def L₁.{u} := List (Type u)
-
--- def L₂ := List (Type u) -- error: `unknown universe level 'u'`
-
-universe u
-def L₃ := List (Type u)
-```
-
-## Examples
-
-```lean
-universe u v w
-
-structure Pair (α : Type u) (β : Type v) : Type (max u v) where
-  a : α
-  b : β
-
-#check Pair.{v, w}
--- Pair : Type v → Type w → Type (max v w)
-```
--/
 @[builtin_command_elab «universe»] def elabUniverse : CommandElab := fun n => do
   n[1].forArgsM addUnivLevel
 
@@ -185,30 +127,6 @@ structure Pair (α : Type u) (β : Type v) : Type (max u v) where
   | Except.ok env   => setEnv env
   | Except.error ex => throwError (ex.toMessageData (← getOptions))
 
-/-- Adds names from other namespaces to the current namespace.
-
-The command `export Some.Namespace (name₁ name₂)` makes `name₁` and `name₂`:
-
-- visible in the current namespace without prefix `Some.Namespace`, like `open`, and
-- visible from outside the current namespace `N` as `N.name₁` and `N.name₂`.
-
-## Examples
-
-```lean
-namespace Morning.Sky
-  def star := "venus"
-end Morning.Sky
-
-namespace Evening.Sky
-  export Morning.Sky (star)
-  -- `star` is now in scope
-  #check star
-end Evening.Sky
-
--- `star` is visible in `Evening.Sky`
-#check Evening.Sky.star
-```
--/
 @[builtin_command_elab «export»] def elabExport : CommandElab := fun stx => do
   let `(export $ns ($ids*)) := stx | throwUnsupportedSyntax
   let nss ← resolveNamespace ns
@@ -223,118 +141,6 @@ end Evening.Sky
     aliases := aliases.push (currNamespace ++ id, declName)
   modify fun s => { s with env := aliases.foldl (init := s.env) fun env p => addAlias env p.1 p.2 }
 
-/-- Makes names from other namespaces visible without writing the namespace prefix.
-
-Names that are made available with `open` are visible within the current `section` or `namespace`
-block. This makes referring to (type) definitions and theorems easier, but note that it can also
-make [scoped instances], notations, and attributes from a different namespace available.
-
-The `open` command can be used in a few different ways:
-
-* `open Some.Namespace.Path1 Some.Namespace.Path2` makes all non-protected names in
-  `Some.Namespace.Path1` and `Some.Namespace.Path2` available without the prefix, so that
-  `Some.Namespace.Path1.x` and `Some.Namespace.Path2.y` can be referred to by writing only `x` and
-  `y`.
-
-* `open Some.Namespace.Path hiding def1 def2` opens all non-protected names in `Some.Namespace.Path`
-  except `def1` and `def2`.
-
-* `open Some.Namespace.Path (def1 def2)` only makes `Some.Namespace.Path.def1` and
-  `Some.Namespace.Path.def2` available without the full prefix, so `Some.Namespace.Path.def3` would
-  be unaffected.
-
-  This works even if `def1` and `def2` are `protected`.
-
-* `open Some.Namespace.Path renaming def1 → def1', def2 → def2'` same as `open Some.Namespace.Path
-  (def1 def2)` but `def1`/`def2`'s names are changed to `def1'`/`def2'`.
-
-  This works even if `def1` and `def2` are `protected`.
-
-* `open scoped Some.Namespace.Path1 Some.Namespace.Path2` **only** opens [scoped instances],
-  notations, and attributes from `Namespace1` and `Namespace2`; it does **not** make any other name
-  available.
-
-* `open <any of the open shapes above> in` makes the names `open`-ed visible only in the next
-  command or expression.
-
-[scoped instance]: https://lean-lang.org/theorem_proving_in_lean4/type_classes.html#scoped-instances
-(Scoped instances in Theorem Proving in Lean)
-
-
-## Examples
-
-```lean
-/-- SKI combinators https://en.wikipedia.org/wiki/SKI_combinator_calculus -/
-namespace Combinator.Calculus
-  def I (a : α) : α := a
-  def K (a : α) : β → α := fun _ => a
-  def S (x : α → β → γ) (y : α → β) (z : α) : γ := x z (y z)
-end Combinator.Calculus
-
-section
-  -- open everything under `Combinator.Calculus`, *i.e.* `I`, `K` and `S`,
-  -- until the section ends
-  open Combinator.Calculus
-
-  theorem SKx_eq_K : S K x = I := rfl
-end
-
--- open everything under `Combinator.Calculus` only for the next command (the next `theorem`, here)
-open Combinator.Calculus in
-theorem SKx_eq_K' : S K x = I := rfl
-
-section
-  -- open only `S` and `K` under `Combinator.Calculus`
-  open Combinator.Calculus (S K)
-
-  theorem SKxy_eq_y : S K x y = y := rfl
-
-  -- `I` is not in scope, we have to use its full path
-  theorem SKxy_eq_Iy : S K x y = Combinator.Calculus.I y := rfl
-end
-
-section
-  open Combinator.Calculus
-    renaming
-      I → identity,
-      K → konstant
-
-  #check identity
-  #check konstant
-end
-
-section
-  open Combinator.Calculus
-    hiding S
-
-  #check I
-  #check K
-end
-
-section
-  namespace Demo
-    inductive MyType
-    | val
-
-    namespace N1
-      scoped infix:68 " ≋ " => BEq.beq
-
-      scoped instance : BEq MyType where
-        beq _ _ := true
-
-      def Alias := MyType
-    end N1
-  end Demo
-
-  -- bring `≋` and the instance in scope, but not `Alias`
-  open scoped Demo.N1
-
-  #check Demo.MyType.val == Demo.MyType.val
-  #check Demo.MyType.val ≋ Demo.MyType.val
-  -- #check Alias -- unknown identifier 'Alias'
-end
-```
--/
 @[builtin_command_elab «open»] def elabOpen : CommandElab
   | `(open $decl:openDecl) => do
     let openDecls ← elabOpenDecl decl
@@ -420,102 +226,6 @@ private def replaceBinderAnnotation (binder : TSyntax ``Parser.Term.bracketedBin
   else
     return #[binder]
 
-/-- Declares one or more typed variables, or modifies whether already-declared variables are
-implicit.
-
-Introduces variables that can be used in definitions within the same `namespace` or `section` block.
-When a definition mentions a variable, Lean will add it as an argument of the definition. The
-`variable` command is also able to add typeclass parameters. This is useful in particular when
-writing many definitions that have parameters in common (see below for an example).
-
-Variable declarations have the same flexibility as regular function paramaters. In particular they
-can be [explicit, implicit][binder docs], or [instance implicit][tpil classes] (in which case they
-can be anonymous). This can be changed, for instance one can turn explicit variable `x` into an
-implicit one with `variable {x}`. Note that currently, you should avoid changing how variables are
-bound and declare new variables at the same time; see [issue 2789] for more on this topic.
-
-See [*Variables and Sections* from Theorem Proving in Lean][tpil vars] for a more detailed
-discussion.
-
-[tpil vars]: https://lean-lang.org/theorem_proving_in_lean4/dependent_type_theory.html#variables-and-sections
-(Variables and Sections on Theorem Proving in Lean)
-[tpil classes]: https://lean-lang.org/theorem_proving_in_lean4/type_classes.html
-(Type classes on Theorem Proving in Lean)
-[binder docs]: https://leanprover-community.github.io/mathlib4_docs/Lean/Expr.html#Lean.BinderInfo
-(Documentation for the BinderInfo type)
-[issue 2789]: https://github.com/leanprover/lean4/issues/2789
-(Issue 2789 on github)
-
-## Examples
-
-```lean
-section
-  variable
-    {α : Type u}      -- implicit
-    (a : α)           -- explicit
-    [instBEq : BEq α] -- instance implicit, named
-    [Hashable α]      -- instance implicit, anonymous
-
-  def isEqual (b : α) : Bool :=
-    a == b
-
-  #check isEqual
-  -- isEqual.{u} {α : Type u} (a : α) [instBEq : BEq α] (b : α) : Bool
-
-  variable
-    {a} -- `a` is implicit now
-
-  def eqComm {b : α} := a == b ↔ b == a
-
-  #check eqComm
-  -- eqComm.{u} {α : Type u} {a : α} [instBEq : BEq α] {b : α} : Prop
-end
-```
-
-The following shows a typical use of `variable` to factor out definition arguments:
-
-```lean
-variable (Src : Type)
-
-structure Logger where
-  trace : List (Src × String)
-#check Logger
--- Logger (Src : Type) : Type
-
-namespace Logger
-  -- switch `Src : Type` to be implicit until the `end Logger`
-  variable {Src}
-
-  def empty : Logger Src where
-    trace := []
-  #check empty
-  -- Logger.empty {Src : Type} : Logger Src
-
-  variable (log : Logger Src)
-
-  def len :=
-    log.trace.length
-  #check len
-  -- Logger.len {Src : Type} (log : Logger Src) : Nat
-
-  variable (src : Src) [BEq Src]
-
-  -- at this point all of `log`, `src`, `Src` and the `BEq` instance can all become arguments
-
-  def filterSrc :=
-    log.trace.filterMap
-      fun (src', str') => if src' == src then some str' else none
-  #check filterSrc
-  -- Logger.filterSrc {Src : Type} (log : Logger Src) (src : Src) [inst✝ : BEq Src] : List String
-
-  def lenSrc :=
-    log.filterSrc src |>.length
-  #check lenSrc
-  -- Logger.lenSrc {Src : Type} (log : Logger Src) (src : Src) [inst✝ : BEq Src] : Nat
-end Logger
-```
-
--/
 @[builtin_command_elab «variable»] def elabVariable : CommandElab
   | `(variable $binders*) => do
     -- Try to elaborate `binders` for sanity checking
@@ -538,10 +248,7 @@ def elabCheckCore (ignoreStuckTC : Bool) : CommandElab
       try
         for c in (← realizeGlobalConstWithInfos term) do
           addCompletionInfo <| .id term id.getId (danglingDot := false) {} none
-          logInfoAt tk <| .ofPPFormat { pp := fun
-            | some ctx => ctx.runMetaM <| PrettyPrinter.ppSignature c
-            | none     => return f!"{c}"  -- should never happen
-          }
+          logInfoAt tk <| .signature c
           return
       catch _ => pure ()  -- identifier might not be a constant but constant + projection
     let e ← Term.elabTerm term none

src/Lean/Elab/Command.lean

@@ -7,6 +7,7 @@ prelude
 import Lean.Elab.Binders
 import Lean.Elab.SyntheticMVars
 import Lean.Elab.SetOption
+import Lean.Language.Basic
 
 namespace Lean.Elab.Command
 
@@ -30,7 +31,6 @@ structure State where
   scopes         : List Scope := [{ header := "" }]
   nextMacroScope : Nat := firstFrontendMacroScope + 1
   maxRecDepth    : Nat
-  nextInstIdx    : Nat := 1 -- for generating anonymous instance names
   ngen           : NameGenerator := {}
   infoState      : InfoState := {}
   traceState     : TraceState := {}
@@ -45,6 +45,16 @@ structure Context where
   currMacroScope : MacroScope := firstFrontendMacroScope
   ref            : Syntax := Syntax.missing
   tacticCache?   : Option (IO.Ref Tactic.Cache)
+  /--
+  Snapshot for incremental reuse and reporting of command elaboration. Currently unused in Lean
+  itself.
+
+  Definitely resolved in `Language.Lean.process.doElab`.
+
+  Invariant: if the bundle's `old?` is set, the context and state at the beginning of current and
+  old elaboration are identical.
+  -/
+  snap?          : Option (Language.SnapshotBundle Language.DynamicSnapshot)
 
 abbrev CommandElabCoreM (ε) := ReaderT Context $ StateRefT State $ EIO ε
 abbrev CommandElabM := CommandElabCoreM Exception
@@ -147,10 +157,13 @@ private def addTraceAsMessagesCore (ctx : Context) (log : MessageLog) (traceStat
 
 private def addTraceAsMessages : CommandElabM Unit := do
   let ctx ← read
-  modify fun s => { s with
-    messages          := addTraceAsMessagesCore ctx s.messages s.traceState
-    traceState.traces := {}
-  }
+  -- do not add trace messages if `trace.profiler.output` is set as it would be redundant and
+  -- pretty printing the trace messages is expensive
+  if trace.profiler.output.get? (← getOptions) |>.isNone then
+    modify fun s => { s with
+      messages          := addTraceAsMessagesCore ctx s.messages s.traceState
+      traceState.traces := {}
+    }
 
 def liftCoreM (x : CoreM α) : CommandElabM α := do
   let s ← get
@@ -207,7 +220,8 @@ def runLinters (stx : Syntax) : CommandElabM Unit := do
       let linters ← lintersRef.get
       unless linters.isEmpty do
         for linter in linters do
-          withTraceNode `Elab.lint (fun _ => return m!"running linter: {linter.name}") do
+          withTraceNode `Elab.lint (fun _ => return m!"running linter: {linter.name}")
+              (tag := linter.name.toString) do
             let savedState ← get
             try
               linter.run stx
@@ -279,7 +293,9 @@ partial def elabCommand (stx : Syntax) : CommandElabM Unit := do
         -- list of commands => elaborate in order
         -- The parser will only ever return a single command at a time, but syntax quotations can return multiple ones
         args.forM elabCommand
-      else withTraceNode `Elab.command (fun _ => return stx) do
+      else withTraceNode `Elab.command (fun _ => return stx) (tag :=
+        -- special case: show actual declaration kind for `declaration` commands
+        (if stx.isOfKind ``Parser.Command.declaration then stx[1] else stx).getKind.toString) do
         let s ← get
         match (← liftMacroM <| expandMacroImpl? s.env stx) with
         | some (decl, stxNew?) =>
@@ -515,6 +531,7 @@ def liftCommandElabM (cmd : CommandElabM α) : CoreM α := do
       fileMap := ← getFileMap
       ref := ← getRef
       tacticCache? := none
+      snap? := none
     } |>.run {
       env := ← getEnv
       maxRecDepth := ← getMaxRecDepth

src/Lean/Elab/DeclNameGen.lean

@@ -0,0 +1,256 @@
+/-
+Copyright (c) 2024 Lean FRO, LLC. All rights reserved.
+Released under Apache 2.0 license as described in the file LICENSE.
+Authors: Kyle Miller
+-/
+prelude
+import Lean.Elab.Command
+
+/-!
+# Name generator for declarations
+
+This module provides functionality to generate a name for a declaration using its binders and its type.
+This is used to generate names for anonymous instances.
+
+It uses heuristics to generate an informative but terse name given its namespace, supplied binders, and type.
+It tries to make these relatively unique,
+and it uses suffixes derived from the module to ensure cross-project uniqueness
+when the instance doesn't refer to anything defined in the current project.
+
+The name generator can be thought of as a kind of pretty printer, rendering an expression in textual form.
+The general structure of this generator is
+1. `Lean.Elab.Command.NameGen.winnowExpr` takes an expression and re-uses `Expr` as a data structure
+   to record the "Syntax"-like structure.
+2. `Lean.Elab.Command.NameGen.mkBaseNameCore` formats the result of that as a string.
+   It actually does a bit more computation than that, since it further removes duplicate expressions,
+   reporting only the first occurrence of each subexpression.
+-/
+
+namespace Lean.Elab.Command
+
+open Meta
+
+namespace NameGen
+
+/--
+If `e` is an application of a projection to a parent structure, returns the term being projected.
+-/
+private def getParentProjArg (e : Expr) : MetaM (Option Expr) := do
+  let .const c@(.str _ field) _ := e.getAppFn | return none
+  let env ← getEnv
+  let some info := env.getProjectionFnInfo? c | return none
+  unless e.getAppNumArgs == info.numParams + 1 do return none
+  let some (.ctorInfo cVal) := env.find? info.ctorName | return none
+  if isSubobjectField? env cVal.induct (Name.mkSimple field) |>.isNone then return none
+  return e.appArg!
+
+/--
+Strips out universes and arguments we decide are unnecessary for naming.
+The resulting expression can have loose fvars and be mangled in other ways.
+Expressions can also be replaced by `.bvar 0` if they shouldn't be mentioned.
+-/
+private partial def winnowExpr (e : Expr) : MetaM Expr := do
+  let rec visit (e : Expr) : MonadCacheT Expr Expr MetaM Expr := checkCache e fun _ => do
+    if ← isProof e then
+      return .bvar 0
+    match e with
+    | .app .. =>
+      if let some e' ← getParentProjArg e then
+        return (← visit e')
+      e.withApp fun f args => do
+        -- Visit only the explicit arguments to `f` and also its type (and type family) arguments.
+        -- The reason we visit type arguments is so that, for example, `Decidable (_ < _)` has
+        -- a chance to insert type information. Type families are for reporting things such as type constructors and monads.
+        let mut fty ← inferType f
+        let mut j := 0
+        let mut e' ← visit f
+        for i in [0:args.size] do
+          unless fty.isForall do
+            fty ← withTransparency .all <| whnf <| fty.instantiateRevRange j i args
+            j := i
+          let .forallE _ _ fty' bi := fty | failure
+          fty := fty'
+          let arg := args[i]!
+          if ← pure bi.isExplicit <||> (pure !arg.isSort <&&> isTypeFormer arg) then
+            unless (← isProof arg) do
+              e' := .app e' (← visit arg)
+        return e'
+    | .forallE n ty body bi =>
+      withLocalDecl n bi ty fun arg => do
+        -- In a dependent forall the body implies `ty`, so we won't mention it.
+        let ty' ← if body.hasLooseBVars then pure (.bvar 0) else visit ty
+        return .forallE n ty' (← visit (body.instantiate1 arg)) bi
+    | .lam n ty body bi =>
+      if let some e := Expr.etaExpandedStrict? e then
+        visit e
+      else
+        withLocalDecl n bi ty fun arg => do
+          -- Don't record the `.lam` since `ty` should be recorded elsewhere in the expression.
+          visit (body.instantiate1 arg)
+    | .letE _n _t v b _ => visit (b.instantiate1 v)
+    | .sort .. =>
+      if e.isProp then return .sort levelZero
+      else if e.isType then return .sort levelOne
+      else return .sort (.param `u)
+    | .const name .. => return .const name []
+    | .mdata _ e' => visit e'
+    | _ => return .bvar 0
+  visit e |>.run
+
+/--
+State for name generation.
+-/
+private structure MkNameState where
+  /-- Keeps track of expressions already visited so that we do not include them again. -/
+  seen : ExprSet := {}
+  /-- Keeps track of constants that appear in the generated name. -/
+  consts : NameSet := {}
+
+/--
+Monad for name generation.
+-/
+private abbrev MkNameM := StateRefT MkNameState MetaM
+
+/--
+Core algorithm for generating a name. The provided expression should be a winnowed expression.
+
+- `omitTopForall` if true causes "Forall" to not be included if the binding type results in an empty string.
+-/
+private def mkBaseNameCore (e : Expr) (omitTopForall : Bool := false) : MkNameM String :=
+  visit e omitTopForall
+where
+  visit (e : Expr) (omitTopForall : Bool := false) : MkNameM String := do
+    if (← get).seen.contains e then
+      return ""
+    else
+      let s ← visit' e omitTopForall
+      modify fun st => {st with seen := st.seen.insert e}
+      return s
+  visit' (e : Expr) (omitTopForall : Bool) : MkNameM String := do
+    match e with
+    | .const name .. =>
+      modify (fun st => {st with consts := st.consts.insert name})
+      return match name.eraseMacroScopes with
+              | .str _ str => str.capitalize
+              | _ => ""
+    | .app f x => (· ++ ·) <$> visit f <*> visit x
+    | .forallE _ ty body _ =>
+      let sty ← visit ty
+      if omitTopForall && sty == "" then
+        visit body true
+      else
+        ("Forall" ++ sty ++ ·) <$> visit body
+    | .sort .zero => return "Prop"
+    | .sort (.succ _) => return "Type"
+    | .sort _ => return "Sort"
+    | _ => return ""
+
+/--
+Generate a name, while naming the top-level foralls using "Of".
+The provided expression should be a winnowed expression.
+-/
+private partial def mkBaseNameAux (e : Expr) : MkNameM String := do
+  let (foralls, sb) ← visit e
+  return sb ++ String.join foralls
+where
+  visit (e : Expr) : MkNameM (List String × String) := do
+    match e with
+    | .forallE _ ty body _ =>
+      let (foralls, sb) ← visit body
+      let st ← mkBaseNameCore ty (omitTopForall := true)
+      if st == "" then
+        return (foralls, sb)
+      else
+        return (("Of" ++ st) :: foralls, sb)
+    | _ => return ([], ← mkBaseNameCore e)
+
+/--
+Adds all prefixes of `ns` as seen constants.
+-/
+private def visitNamespace (ns : Name) : MkNameM Unit := do
+  match ns with
+  | .anonymous => pure ()
+  | .num ns' _ => visitNamespace ns'
+  | .str ns' _ =>
+    let env ← getEnv
+    if env.contains ns then
+      modify fun st => {st with seen := st.seen.insert (.const ns []), consts := st.consts.insert ns}
+    visitNamespace ns'
+
+/--
+Given an expression, generates a "base name" for a declaration.
+The top-level foralls in `e` are treated as being binders, so use the `...Of...` naming convention.
+The current namespace is used to seed the seen expressions with each prefix of the namespace that's a global constant.
+
+Collects all constants that contribute to the name in the `MkInstM` state.
+This can be used to decide whether to further transform the generated name;
+in particular, this enables checking whether the generated name mentions declarations
+from the current module or project.
+-/
+def mkBaseName (e : Expr) : MkNameM String := do
+  let e ← instantiateMVars e
+  visitNamespace (← getCurrNamespace)
+  mkBaseNameAux (← winnowExpr e)
+
+/--
+Converts a module name into a suffix. Includes a leading `_`,
+so for example `Lean.Elab.DefView` becomes `_lean_elab_defView`.
+-/
+private def moduleToSuffix : Name → String
+  | .anonymous => ""
+  | .num n _ => moduleToSuffix n
+  | .str n s => moduleToSuffix n ++ "_" ++ s.decapitalize
+
+/--
+Uses heuristics to generate an informative but terse base name for a term of the given type, using `mkBaseName`.
+Makes use of the current namespace.
+It tries to make these names relatively unique ecosystem-wide,
+and it adds suffixes using the current module if the resulting name doesn't refer to anything defined in this module.
+-/
+def mkBaseNameWithSuffix (pre : String) (type : Expr) : MetaM String := do
+  let (name, st) ← mkBaseName type |>.run {}
+  let name := pre ++ name
+  let project := (← getMainModule).getRoot
+  -- Collect the modules for each constant that appeared.
+  let modules ← st.consts.foldM (init := Array.mkEmpty st.consts.size) fun mods name => return mods.push (← findModuleOf? name)
+  -- We can avoid adding the suffix if the instance refers to module-local names.
+  let isModuleLocal := modules.any Option.isNone
+  -- We can also avoid adding the full module suffix if the instance refers to "project"-local names.
+  let isProjectLocal := isModuleLocal || modules.any fun mod? => mod?.map (·.getRoot) == project
+  if !isProjectLocal then
+    return s!"{name}{moduleToSuffix project}"
+  else
+    return name
+
+/--
+Elaborates the binders and type and then uses `mkBaseNameWithSuffix` to generate a name.
+Furthermore, uses `mkUnusedBaseName` on the result.
+-/
+def mkBaseNameWithSuffix' (pre : String) (binders : Array Syntax) (type : Syntax) : TermElabM Name := do
+  let name ←
+    try
+      Term.withAutoBoundImplicit <| Term.elabBinders binders fun binds => Term.withoutErrToSorry do
+        let ty ← mkForallFVars binds (← Term.elabType type)
+        mkBaseNameWithSuffix pre ty
+    catch _ =>
+      pure pre
+  liftMacroM <| mkUnusedBaseName <| Name.mkSimple name
+
+end NameGen
+
+/--
+Generates an instance name for a declaration that has the given binders and type.
+It tries to make these names relatively unique ecosystem-wide.
+
+Note that this elaborates the binders and the type.
+This means that when elaborating an instance declaration, we elaborate these twice.
+-/
+def mkInstanceName (binders : Array Syntax) (type : Syntax) : CommandElabM Name := do
+  let savedState ← get
+  try
+    -- Unfortunately we can't include any of the binders from `runTermElabM` since, without
+    -- elaborating the body of the instance, we have no idea which of these binders are
+    -- actually used.
+    runTermElabM fun _ => NameGen.mkBaseNameWithSuffix' "inst" binders type
+  finally
+    set savedState

src/Lean/Elab/DeclUtil.lean

@@ -54,14 +54,6 @@ def expandDeclSig (stx : Syntax) : Syntax × Syntax :=
   let typeSpec := stx[1]
   (binders, typeSpec[1])
 
-def mkFreshInstanceName (env : Environment) (nextIdx : Nat) : Name :=
-  (env.mainModule ++ `_instance).appendIndexAfter nextIdx
-
-def isFreshInstanceName (name : Name) : Bool :=
-  match name with
-  | .str _ s => "_instance".isPrefixOf s
-  | _        => false
-
 /--
   Sort the given list of `usedParams` using the following order:
   - If it is an explicit level `allUserParams`, then use user given order.

src/Lean/Elab/Declaration.lean

@@ -353,14 +353,14 @@ def elabMutual : CommandElab := fun stx => do
     for builtin simprocs.
     -/
     let declNames ←
-       try
-         realizeGlobalConst ident
-       catch _ =>
-         let name := ident.getId.eraseMacroScopes
-         if (← Simp.isBuiltinSimproc name) then
-           pure [name]
-         else
-           throwUnknownConstant name
+      try
+        realizeGlobalConstWithInfos ident
+      catch _ =>
+        let name := ident.getId.eraseMacroScopes
+        if (← Simp.isBuiltinSimproc name) then
+          pure [name]
+        else
+          throwUnknownConstant name
     let declName ← ensureNonAmbiguous ident declNames
     Term.applyAttributes declName attrs
     for attrName in toErase do

src/Lean/Elab/DefView.lean

@@ -4,8 +4,8 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Leonardo de Moura, Sebastian Ullrich
 -/
 prelude
-import Lean.Meta.ForEachExpr
 import Lean.Elab.Command
+import Lean.Elab.DeclNameGen
 import Lean.Elab.DeclUtil
 
 namespace Lean.Elab
@@ -66,41 +66,6 @@ def mkDefViewOfTheorem (modifiers : Modifiers) (stx : Syntax) : DefView :=
   { ref := stx, kind := DefKind.theorem, modifiers,
     declId := stx[1], binders, type? := some type, value := stx[3] }
 
-def mkFreshInstanceName : CommandElabM Name := do
-  let s ← get
-  let idx := s.nextInstIdx
-  modify fun s => { s with nextInstIdx := s.nextInstIdx + 1 }
-  return Lean.Elab.mkFreshInstanceName s.env idx
-
-/--
-  Generate a name for an instance with the given type.
-  Note that we elaborate the type twice. Once for producing the name, and another when elaborating the declaration. -/
-def mkInstanceName (binders : Array Syntax) (type : Syntax) : CommandElabM Name := do
-  let savedState ← get
-  try
-    let result ← runTermElabM fun _ => Term.withAutoBoundImplicit <| Term.elabBinders binders fun _ => Term.withoutErrToSorry do
-      let type ← instantiateMVars (← Term.elabType type)
-      let ref ← IO.mkRef ""
-      Meta.forEachExpr type fun e => do
-        if e.isForall then ref.modify (· ++ "ForAll")
-        else if e.isProp then ref.modify (· ++ "Prop")
-        else if e.isType then ref.modify (· ++ "Type")
-        else if e.isSort then ref.modify (· ++ "Sort")
-        else if e.isConst then
-          match e.constName!.eraseMacroScopes with
-          | .str _ str =>
-              if str.front.isLower then
-                ref.modify (· ++ str.capitalize)
-              else
-                ref.modify (· ++ str)
-          | _ => pure ()
-      ref.get
-    set savedState
-    liftMacroM <| mkUnusedBaseName <| Name.mkSimple ("inst" ++ result)
-  catch _ =>
-    set savedState
-    mkFreshInstanceName
-
 def mkDefViewOfInstance (modifiers : Modifiers) (stx : Syntax) : CommandElabM DefView := do
   -- leading_parser Term.attrKind >> "instance " >> optNamedPrio >> optional declId >> declSig >> declVal
   let attrKind        ← liftMacroM <| toAttributeKind stx[0]
@@ -109,9 +74,14 @@ def mkDefViewOfInstance (modifiers : Modifiers) (stx : Syntax) : CommandElabM De
   let (binders, type) := expandDeclSig stx[4]
   let modifiers       := modifiers.addAttribute { kind := attrKind, name := `instance, stx := attrStx }
   let declId ← match stx[3].getOptional? with
-    | some declId => pure declId
+    | some declId =>
+      if ← isTracingEnabledFor `Elab.instance.mkInstanceName then
+        let id ← mkInstanceName binders.getArgs type
+        trace[Elab.instance.mkInstanceName] "generated {(← getCurrNamespace) ++ id} for {declId}"
+      pure declId
     | none        =>
       let id ← mkInstanceName binders.getArgs type
+      trace[Elab.instance.mkInstanceName] "generated {(← getCurrNamespace) ++ id}"
       pure <| mkNode ``Parser.Command.declId #[mkIdentFrom stx id, mkNullNode]
   return {
     ref := stx, kind := DefKind.def, modifiers := modifiers,
@@ -166,6 +136,7 @@ def mkDefView (modifiers : Modifiers) (stx : Syntax) : CommandElabM DefView :=
     throwError "unexpected kind of definition"
 
 builtin_initialize registerTraceClass `Elab.definition
+builtin_initialize registerTraceClass `Elab.instance.mkInstanceName
 
 end Command
 end Lean.Elab

src/Lean/Elab/Deriving/Ord.lean

@@ -49,10 +49,7 @@ where
             let b := mkIdent (← mkFreshUserName `b)
             ctorArgs1 := ctorArgs1.push a
             ctorArgs2 := ctorArgs2.push b
-            rhsCont := fun rhs => `(match compare $a $b with
-              | Ordering.lt => Ordering.lt
-              | Ordering.gt => Ordering.gt
-              | Ordering.eq => $rhs) >>= rhsCont
+            rhsCont := fun rhs => `(Ordering.then (compare $a $b) $rhs) >>= rhsCont
         let lPat ← `(@$(mkIdent ctorName):ident $ctorArgs1:term*)
         let rPat ← `(@$(mkIdent ctorName):ident $ctorArgs2:term*)
         let patterns := indPatterns ++ #[lPat, rPat]

src/Lean/Elab/Frontend.lean

@@ -7,6 +7,7 @@ prelude
 import Lean.Language.Lean
 import Lean.Util.Profile
 import Lean.Server.References
+import Lean.Util.Profiler
 
 namespace Lean.Elab.Frontend
 
@@ -32,6 +33,7 @@ def setCommandState (commandState : Command.State) : FrontendM Unit :=
     fileName     := ctx.inputCtx.fileName
     fileMap      := ctx.inputCtx.fileMap
     tacticCache? := none
+    snap?        := none
   }
   match (← liftM <| EIO.toIO' <| (x cmdCtx).run s.commandState) with
   | Except.error e      => throw <| IO.Error.userError s!"unexpected internal error: {← e.toMessageData.toString}"
@@ -108,6 +110,7 @@ def runFrontend
     (trustLevel : UInt32 := 0)
     (ileanFileName? : Option String := none)
     : IO (Environment × Bool) := do
+  let startTime := (← IO.monoNanosNow).toFloat / 1000000000
   let inputCtx := Parser.mkInputContext input fileName
   -- TODO: replace with `#lang` processing
   if /- Lean #lang? -/ true then
@@ -119,6 +122,7 @@ def runFrontend
     let (env, messages) ← processHeader (leakEnv := true) header opts messages inputCtx trustLevel
     let env := env.setMainModule mainModuleName
     let mut commandState := Command.mkState env messages opts
+    let elabStartTime := (← IO.monoNanosNow).toFloat / 1000000000
 
     if ileanFileName?.isSome then
       -- Collect InfoTrees so we can later extract and export their info to the ilean file
@@ -135,6 +139,19 @@ def runFrontend
       let ilean := { module := mainModuleName, references : Lean.Server.Ilean }
       IO.FS.writeFile ileanFileName $ Json.compress $ toJson ilean
 
+    if let some out := trace.profiler.output.get? opts then
+      let traceState := s.commandState.traceState
+      -- importing does not happen in an elaboration monad, add now
+      let traceState := { traceState with
+        traces := #[{
+          ref := .missing,
+          msg := .trace { cls := `Import, startTime, stopTime := elabStartTime }
+            (.ofFormat "importing") #[]
+        }].toPArray' ++ traceState.traces
+      }
+      let profile ← Firefox.Profile.export mainModuleName.toString startTime traceState opts
+      IO.FS.writeFile ⟨out⟩ <| Json.compress <| toJson profile
+
     return (s.commandState.env, !s.commandState.messages.hasErrors)
 
   let ctx := { inputCtx with mainModuleName, opts, trustLevel }

src/Lean/Elab/GuardMsgs.lean

@@ -4,6 +4,8 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kyle Miller
 -/
 prelude
+import Lean.Elab.Notation
+import Lean.Util.Diff
 import Lean.Server.CodeActions.Attr
 
 /-! `#guard_msgs` command for testing commands
@@ -14,6 +16,12 @@ See the docstring on the `#guard_msgs` command.
 
 open Lean Parser.Tactic Elab Command
 
+register_builtin_option guard_msgs.diff : Bool := {
+  defValue := false
+  descr := "When true, show a diff between expected and actual messages if they don't match. "
+}
+
+
 namespace Lean.Elab.Tactic.GuardMsgs
 
 /-- Gives a string representation of a message without source position information.
@@ -40,31 +48,55 @@ inductive SpecResult
   /-- Do not capture the message. -/
   | passthrough
 
+/-- The method to use when normalizing whitespace, after trimming. -/
+inductive WhitespaceMode
+  /-- Exact equality. -/
+  | exact
+  /-- Equality after normalizing newlines into spaces. -/
+  | normalized
+  /-- Equality after collapsing whitespace into single spaces. -/
+  | lax
+
+/-- Method to use when combining multiple messages. -/
+inductive MessageOrdering
+  /-- Use the exact ordering of the produced messages. -/
+  | exact
+  /-- Sort the produced messages. -/
+  | sorted
+
 /-- Parses a `guardMsgsSpec`.
 - No specification: check everything.
 - With a specification: interpret the spec, and if nothing applies pass it through. -/
 def parseGuardMsgsSpec (spec? : Option (TSyntax ``guardMsgsSpec)) :
-    CommandElabM (Message → SpecResult) := do
-  if let some spec := spec? then
-    match spec with
-    | `(guardMsgsSpec| ($[$elts:guardMsgsSpecElt],*)) => do
-      let mut p : Message → SpecResult := fun _ => .passthrough
-      let pushP (s : MessageSeverity) (drop : Bool) (p : Message → SpecResult)
-          (msg : Message) : SpecResult :=
-        if msg.severity == s then if drop then .drop else .check
-        else p msg
-      for elt in elts.reverse do
-        match elt with
-        | `(guardMsgsSpecElt| $[drop%$drop?]? info)    => p := pushP .information drop?.isSome p
-        | `(guardMsgsSpecElt| $[drop%$drop?]? warning) => p := pushP .warning drop?.isSome p
-        | `(guardMsgsSpecElt| $[drop%$drop?]? error)   => p := pushP .error drop?.isSome p
-        | `(guardMsgsSpecElt| $[drop%$drop?]? all) =>
-          p := fun _ => if drop?.isSome then .drop else .check
-        | _ => throwErrorAt elt "Invalid #guard_msgs specification element"
-      return p
-    | _ => throwErrorAt spec "Invalid #guard_msgs specification"
-  else
-    return fun _ => .check
+    CommandElabM (WhitespaceMode × MessageOrdering × (Message → SpecResult)) := do
+  let elts ←
+    if let some spec := spec? then
+      match spec with
+      | `(guardMsgsSpec| ($[$elts:guardMsgsSpecElt],*)) => pure elts
+      | _ => throwUnsupportedSyntax
+    else
+      pure #[]
+  let mut whitespace : WhitespaceMode := .normalized
+  let mut ordering : MessageOrdering := .exact
+  let mut p? : Option (Message → SpecResult) := none
+  let pushP (s : MessageSeverity) (drop : Bool) (p? : Option (Message → SpecResult))
+      (msg : Message) : SpecResult :=
+    let p := p?.getD fun _ => .passthrough
+    if msg.severity == s then if drop then .drop else .check
+    else p msg
+  for elt in elts.reverse do
+    match elt with
+    | `(guardMsgsSpecElt| $[drop%$drop?]? info)     => p? := pushP .information drop?.isSome p?
+    | `(guardMsgsSpecElt| $[drop%$drop?]? warning)  => p? := pushP .warning drop?.isSome p?
+    | `(guardMsgsSpecElt| $[drop%$drop?]? error)    => p? := pushP .error drop?.isSome p?
+    | `(guardMsgsSpecElt| $[drop%$drop?]? all)      => p? := some fun _ => if drop?.isSome then .drop else .check
+    | `(guardMsgsSpecElt| whitespace := exact)      => whitespace := .exact
+    | `(guardMsgsSpecElt| whitespace := normalized) => whitespace := .normalized
+    | `(guardMsgsSpecElt| whitespace := lax)        => whitespace := .lax
+    | `(guardMsgsSpecElt| ordering := exact)        => ordering := .exact
+    | `(guardMsgsSpecElt| ordering := sorted)       => ordering := .sorted
+    | _ => throwUnsupportedSyntax
+  return (whitespace, ordering, p?.getD fun _ => .check)
 
 /-- An info tree node corresponding to a failed `#guard_msgs` invocation,
 used for code action support. -/
@@ -86,16 +118,27 @@ def removeTrailingWhitespaceMarker (s : String) : String :=
   s.replace "⏎\n" "\n"
 
 /--
-Strings are compared up to newlines, to allow users to break long lines.
+Applies a whitespace normalization mode.
 -/
-def equalUpToNewlines (exp res : String) : Bool :=
-  exp.replace "\n" " " == res.replace "\n" " "
+def WhitespaceMode.apply (mode : WhitespaceMode) (s : String) : String :=
+  match mode with
+  | .exact => s
+  | .normalized => s.replace "\n" " "
+  | .lax => String.intercalate " " <| (s.split Char.isWhitespace).filter (!·.isEmpty)
+
+/--
+Applies a message ordering mode.
+-/
+def MessageOrdering.apply (mode : MessageOrdering) (msgs : List String) : List String :=
+  match mode with
+  | .exact => msgs
+  | .sorted => msgs |>.toArray.qsort (· < ·) |>.toList
 
 @[builtin_command_elab Lean.guardMsgsCmd] def elabGuardMsgs : CommandElab
   | `(command| $[$dc?:docComment]? #guard_msgs%$tk $(spec?)? in $cmd) => do
     let expected : String := (← dc?.mapM (getDocStringText ·)).getD ""
         |>.trim |> removeTrailingWhitespaceMarker
-    let specFn ← parseGuardMsgsSpec spec?
+    let (whitespace, ordering, specFn) ← parseGuardMsgsSpec spec?
     let initMsgs ← modifyGet fun st => (st.messages, { st with messages := {} })
     elabCommandTopLevel cmd
     let msgs := (← get).messages
@@ -106,14 +149,21 @@ def equalUpToNewlines (exp res : String) : Bool :=
       | .check       => toCheck := toCheck.add msg
       | .drop        => pure ()
       | .passthrough => toPassthrough := toPassthrough.add msg
-    let res := "---\n".intercalate (← toCheck.toList.mapM (messageToStringWithoutPos ·)) |>.trim
-    if equalUpToNewlines expected res then
+    let strings ← toCheck.toList.mapM (messageToStringWithoutPos ·)
+    let strings := ordering.apply strings
+    let res := "---\n".intercalate strings |>.trim
+    if whitespace.apply expected == whitespace.apply res then
       -- Passed. Only put toPassthrough messages back on the message log
       modify fun st => { st with messages := initMsgs ++ toPassthrough }
     else
       -- Failed. Put all the messages back on the message log and add an error
       modify fun st => { st with messages := initMsgs ++ msgs }
-      logErrorAt tk m!"❌ Docstring on `#guard_msgs` does not match generated message:\n\n{res}"
+      let feedback :=
+        if (← getOptions).getBool `guard_msgs.diff false then
+          let diff := Diff.diff (expected.split (· == '\n')).toArray (res.split (· == '\n')).toArray
+          Diff.linesToString diff
+        else res
+      logErrorAt tk m!"❌ Docstring on `#guard_msgs` does not match generated message:\n\n{feedback}"
       pushInfoLeaf (.ofCustomInfo { stx := ← getRef, value := Dynamic.mk (GuardMsgFailure.mk res) })
   | _ => throwUnsupportedSyntax
 

src/Lean/Elab/PreDefinition/Basic.lean

@@ -7,6 +7,7 @@ prelude
 import Lean.Compiler.NoncomputableAttr
 import Lean.Util.CollectLevelParams
 import Lean.Meta.AbstractNestedProofs
+import Lean.Meta.ForEachExpr
 import Lean.Elab.RecAppSyntax
 import Lean.Elab.DefView
 import Lean.Elab.PreDefinition.WF.TerminationHint

src/Lean/Elab/Tactic/Basic.lean

@@ -147,7 +147,7 @@ partial def evalTactic (stx : Syntax) : TacticM Unit := do
       if k == nullKind then
         -- Macro writers create a sequence of tactics `t₁ ... tₙ` using `mkNullNode #[t₁, ..., tₙ]`
         stx.getArgs.forM evalTactic
-      else withTraceNode `Elab.step (fun _ => return stx) do
+      else withTraceNode `Elab.step (fun _ => return stx) (tag := stx.getKind.toString) do
         let evalFns := tacticElabAttribute.getEntries (← getEnv) stx.getKind
         let macros  := macroAttribute.getEntries (← getEnv) stx.getKind
         if evalFns.isEmpty && macros.isEmpty then

src/Lean/Elab/Tactic/Omega/Frontend.lean

@@ -526,6 +526,82 @@ def cases₂ (mvarId : MVarId) (p : Expr) (hName : Name := `h) :
     | throwError "'cases' tactic failed, unexpected new hypothesis"
   return ((s₁.mvarId, f₁), (s₂.mvarId, f₂))
 
+/--
+Helpful error message when omega cannot find a solution
+-/
+def formatErrorMessage (p : Problem) : OmegaM MessageData := do
+  if p.possible then
+    if p.isEmpty then
+      return m!"it is false"
+    else
+      let as ← atoms
+      let mask ← mentioned p.constraints
+      let names ← varNames mask
+      return m!"a possible counterexample may satisfy the constraints\n" ++
+        m!"{prettyConstraints names p.constraints}\nwhere\n{prettyAtoms names as mask}"
+  else
+    -- formatErrorMessage should not be used in this case
+    return "it is trivially solvable"
+where
+  varNameOf (i : Nat) : String :=
+    let c : Char := .ofNat ('a'.toNat + (i % 26))
+    let suffix := if i < 26 then "" else s!"_{i / 26}"
+    s!"{c}{suffix}"
+
+  inScope (s : String) : MetaM Bool := do
+    let n := .mkSimple s
+    if (← resolveGlobalName n).isEmpty then
+      if ((← getLCtx).findFromUserName? n).isNone then
+        return false
+    return true
+
+  -- Assign ascending names a, b, c, …, z, a1 … to all atoms mentioned according to the mask
+  -- but avoid names in the local or global scope
+  varNames (mask : Array Bool) : MetaM (Array String) := do
+    let mut names := #[]
+    let mut next := 0
+    for h : i in [:mask.size] do
+      if mask[i] then
+        while ← inScope (varNameOf next) do next := next + 1
+        names := names.push (varNameOf next)
+        next := next + 1
+      else
+        names := names.push "(masked)"
+    return names
+
+  prettyConstraints (names : Array String) (constraints : HashMap Coeffs Fact) : String :=
+    constraints.toList
+      |>.map (fun ⟨coeffs, ⟨_, cst, _⟩⟩ => "  " ++ prettyConstraint (prettyCoeffs names coeffs) cst)
+      |> "\n".intercalate
+
+  prettyConstraint (e : String) : Constraint → String
+    | ⟨none, none⟩ => s!"{e} is unconstrained" -- should not happen in error messages
+    | ⟨none, some y⟩ => s!"{e} ≤ {y}"
+    | ⟨some x, none⟩ => s!"{e} ≥ {x}"
+    | ⟨some x, some y⟩ =>
+      if y < x then "∅" else -- should not happen in error messages
+      s!"{x} ≤ {e} ≤ {y}"
+
+  prettyCoeffs (names : Array String) (coeffs : Coeffs) : String :=
+    coeffs.toList.enum
+      |>.filter (fun (_,c) => c ≠ 0)
+      |>.enum
+      |>.map (fun (j, (i,c)) =>
+        (if j > 0 then if c > 0 then " + " else " - " else if c > 0 then "" else "- ") ++
+        (if Int.natAbs c = 1 then names[i]! else s!"{c.natAbs}*{names[i]!}"))
+      |> String.join
+
+  mentioned (constraints : HashMap Coeffs Fact) : OmegaM (Array Bool) := do
+    let initMask := Array.mkArray (← getThe State).atoms.size false
+    return constraints.fold (init := initMask) fun mask coeffs _ =>
+      coeffs.enum.foldl (init := mask) fun mask (i, c) =>
+        if c = 0 then mask else mask.set! i true
+
+  prettyAtoms (names : Array String) (atoms : Array Expr) (mask : Array Bool) : MessageData :=
+    (Array.zip names atoms).toList.enum
+      |>.filter (fun (i, _) => mask.getD i false)
+      |>.map (fun (_, (n, a)) => m!" {n} := {a}")
+      |> m!"\n".joinSep
 
 mutual
 
@@ -535,7 +611,7 @@ call `omegaImpl` in both branches.
 -/
 partial def splitDisjunction (m : MetaProblem) (g : MVarId) : OmegaM Unit := g.withContext do
   match m.disjunctions with
-    | [] => throwError "omega did not find a contradiction:\n{m.problem}"
+    | [] => throwError "omega could not prove the goal:\n{← formatErrorMessage m.problem}"
     | h :: t =>
       trace[omega] "Case splitting on {← inferType h}"
       let ctx ← getMCtx

src/Lean/Elab/Tactic/RCases.lean

@@ -348,7 +348,7 @@ partial def rcasesCore (g : MVarId) (fs : FVarSubst) (clears : Array FVarId) (e
           pure ([(n, ps)], #[⟨⟨g, #[mkFVar v], fs'⟩, n⟩])
       | ConstantInfo.inductInfo info, _ => do
         let (altVarNames, r) ← processConstructors pat.ref info.numParams #[] info.ctors pat.asAlts
-        (r, ·) <$> g.cases e.fvarId! altVarNames
+        (r, ·) <$> g.cases e.fvarId! altVarNames (useNatCasesAuxOn := true)
       | _, _ => failK ()
     (·.2) <$> subgoals.foldlM (init := (r, a)) fun (r, a) ⟨goal, ctorName⟩ => do
       let rec

src/Lean/Elab/Term.lean

@@ -261,6 +261,14 @@ def SavedState.restore (s : SavedState) (restoreInfo : Bool := false) : TermElab
   unless restoreInfo do
     setInfoState infoState
 
+/--
+Restores full state including sources for unique identifiers. Only intended for incremental reuse
+between elaboration runs, not for backtracking within a single run.
+-/
+def SavedState.restoreFull (s : SavedState) : TermElabM Unit := do
+  s.meta.restoreFull
+  set s.elab
+
 instance : MonadBacktrack SavedState TermElabM where
   saveState      := Term.saveState
   restoreState b := b.restore
@@ -1379,7 +1387,8 @@ where
 private partial def elabTermAux (expectedType? : Option Expr) (catchExPostpone : Bool) (implicitLambda : Bool) : Syntax → TermElabM Expr
   | .missing => mkSyntheticSorryFor expectedType?
   | stx => withFreshMacroScope <| withIncRecDepth do
-    withTraceNode `Elab.step (fun _ => return m!"expected type: {expectedType?}, term\n{stx}") do
+    withTraceNode `Elab.step (fun _ => return m!"expected type: {expectedType?}, term\n{stx}")
+      (tag := stx.getKind.toString) do
     checkSystem "elaborator"
     let env ← getEnv
     let result ← match (← liftMacroM (expandMacroImpl? env stx)) with
@@ -1757,6 +1766,7 @@ builtin_initialize
   registerTraceClass `Elab.postpone
   registerTraceClass `Elab.coe
   registerTraceClass `Elab.debug
+  registerTraceClass `Elab.reuse
 
 export Term (TermElabM)
 

src/Lean/Expr.lean

@@ -2025,43 +2025,43 @@ def mkIff (p q : Expr) : Expr := mkApp2 (mkConst ``Iff) p q
 /-! Constants for Nat typeclasses. -/
 namespace Nat
 
-def natType : Expr := mkConst ``Nat
+protected def mkType : Expr := mkConst ``Nat
 
-def instAdd : Expr := mkConst ``instAddNat
-def instHAdd : Expr := mkApp2 (mkConst ``instHAdd [levelZero]) natType instAdd
+def mkInstAdd : Expr := mkConst ``instAddNat
+def mkInstHAdd : Expr := mkApp2 (mkConst ``instHAdd [levelZero]) Nat.mkType mkInstAdd
 
-def instSub : Expr := mkConst ``instSubNat
-def instHSub : Expr := mkApp2 (mkConst ``instHSub [levelZero]) natType instSub
+def mkInstSub : Expr := mkConst ``instSubNat
+def mkInstHSub : Expr := mkApp2 (mkConst ``instHSub [levelZero]) Nat.mkType mkInstSub
 
-def instMul : Expr := mkConst ``instMulNat
-def instHMul : Expr := mkApp2 (mkConst ``instHMul [levelZero]) natType instMul
+def mkInstMul : Expr := mkConst ``instMulNat
+def mkInstHMul : Expr := mkApp2 (mkConst ``instHMul [levelZero]) Nat.mkType mkInstMul
 
-def instDiv : Expr := mkConst ``Nat.instDivNat
-def instHDiv : Expr := mkApp2 (mkConst ``instHDiv [levelZero]) natType instDiv
+def mkInstDiv : Expr := mkConst ``Nat.instDiv
+def mkInstHDiv : Expr := mkApp2 (mkConst ``instHDiv [levelZero]) Nat.mkType mkInstDiv
 
-def instMod : Expr := mkConst ``Nat.instModNat
-def instHMod : Expr := mkApp2 (mkConst ``instHMod [levelZero]) natType instMod
+def mkInstMod : Expr := mkConst ``Nat.instMod
+def mkInstHMod : Expr := mkApp2 (mkConst ``instHMod [levelZero]) Nat.mkType mkInstMod
 
-def instNatPow : Expr := mkConst ``instNatPowNat
-def instPow  : Expr := mkApp2 (mkConst ``instPowNat [levelZero]) natType instNatPow
-def instHPow : Expr := mkApp3 (mkConst ``instHPow [levelZero, levelZero]) natType natType instPow
+def mkInstNatPow : Expr := mkConst ``instNatPowNat
+def mkInstPow  : Expr := mkApp2 (mkConst ``instPowNat [levelZero]) Nat.mkType mkInstNatPow
+def mkInstHPow : Expr := mkApp3 (mkConst ``instHPow [levelZero, levelZero]) Nat.mkType Nat.mkType mkInstPow
 
-def instLT : Expr := mkConst ``instLTNat
-def instLE : Expr := mkConst ``instLENat
+def mkInstLT : Expr := mkConst ``instLTNat
+def mkInstLE : Expr := mkConst ``instLENat
 
 end Nat
 
 private def natAddFn : Expr :=
   let nat := mkConst ``Nat
-  mkApp4 (mkConst ``HAdd.hAdd [0, 0, 0]) nat nat nat Nat.instHAdd
+  mkApp4 (mkConst ``HAdd.hAdd [0, 0, 0]) nat nat nat Nat.mkInstHAdd
 
 private def natSubFn : Expr :=
   let nat := mkConst ``Nat
-  mkApp4 (mkConst ``HSub.hSub [0, 0, 0]) nat nat nat Nat.instHSub
+  mkApp4 (mkConst ``HSub.hSub [0, 0, 0]) nat nat nat Nat.mkInstHSub
 
 private def natMulFn : Expr :=
   let nat := mkConst ``Nat
-  mkApp4 (mkConst ``HMul.hMul [0, 0, 0]) nat nat nat Nat.instHMul
+  mkApp4 (mkConst ``HMul.hMul [0, 0, 0]) nat nat nat Nat.mkInstHMul
 
 /-- Given `a : Nat`, returns `Nat.succ a` -/
 def mkNatSucc (a : Expr) : Expr :=
@@ -2080,7 +2080,7 @@ def mkNatMul (a b : Expr) : Expr :=
   mkApp2 natMulFn a b
 
 private def natLEPred : Expr :=
-  mkApp2 (mkConst ``LE.le [0]) (mkConst ``Nat) Nat.instLE
+  mkApp2 (mkConst ``LE.le [0]) (mkConst ``Nat) Nat.mkInstLE
 
 /-- Given `a b : Nat`, return `a ≤ b` -/
 def mkNatLE (a b : Expr) : Expr :=

src/Lean/Language/Basic.lean

@@ -9,6 +9,7 @@ Authors: Sebastian Ullrich
 -/
 
 prelude
+import Init.System.Promise
 import Lean.Message
 import Lean.Parser.Types
 
@@ -58,23 +59,26 @@ deriving Inhabited
 -- cursor position. This may require starting the tasks suspended (e.g. in `Thunk`). The server may
 -- also need more dependency information for this in order to avoid priority inversion.
 structure SnapshotTask (α : Type) where
-  /-- Range that is marked as being processed by the server while the task is running. -/
-  range : String.Range
+  /--
+  Range that is marked as being processed by the server while the task is running. If `none`,
+  the range of the outer task if some or else the entire file is reported.
+  -/
+  range? : Option String.Range
   /-- Underlying task producing the snapshot. -/
   task : Task α
 deriving Nonempty
 
 /-- Creates a snapshot task from a reporting range and a `BaseIO` action. -/
-def SnapshotTask.ofIO (range : String.Range) (act : BaseIO α) : BaseIO (SnapshotTask α) := do
+def SnapshotTask.ofIO (range? : Option String.Range) (act : BaseIO α) : BaseIO (SnapshotTask α) := do
   return {
-    range
+    range?
     task := (← BaseIO.asTask act)
   }
 
 /-- Creates a finished snapshot task. -/
 def SnapshotTask.pure (a : α) : SnapshotTask α where
   -- irrelevant when already finished
-  range := default
+  range? := none
   task := .pure a
 
 /--
@@ -84,23 +88,26 @@ def SnapshotTask.cancel (t : SnapshotTask α) : BaseIO Unit :=
   IO.cancel t.task
 
 /-- Transforms a task's output without changing the reporting range. -/
-def SnapshotTask.map (t : SnapshotTask α) (f : α → β) (range : String.Range := t.range)
+def SnapshotTask.map (t : SnapshotTask α) (f : α → β) (range? : Option String.Range := t.range?)
     (sync := false) : SnapshotTask β :=
-  { range, task := t.task.map (sync := sync) f }
+  { range?, task := t.task.map (sync := sync) f }
 
 /--
   Chains two snapshot tasks. The range is taken from the first task if not specified; the range of
   the second task is discarded. -/
 def SnapshotTask.bind (t : SnapshotTask α) (act : α → SnapshotTask β)
-    (range : String.Range := t.range) (sync := false) : SnapshotTask β :=
-  { range, task := t.task.bind (sync := sync) (act · |>.task) }
+    (range? : Option String.Range := t.range?) (sync := false) : SnapshotTask β :=
+  { range?, task := t.task.bind (sync := sync) (act · |>.task) }
 
 /--
   Chains two snapshot tasks. The range is taken from the first task if not specified; the range of
   the second task is discarded. -/
 def SnapshotTask.bindIO (t : SnapshotTask α) (act : α → BaseIO (SnapshotTask β))
-    (range : String.Range := t.range) (sync := false) : BaseIO (SnapshotTask β) :=
-  return { range, task := (← BaseIO.bindTask (sync := sync) t.task fun a => (·.task) <$> (act a)) }
+    (range? : Option String.Range := t.range?) (sync := false) : BaseIO (SnapshotTask β) :=
+  return {
+    range?
+    task := (← BaseIO.bindTask (sync := sync) t.task fun a => (·.task) <$> (act a))
+  }
 
 /-- Synchronously waits on the result of the task. -/
 def SnapshotTask.get (t : SnapshotTask α) : α :=
@@ -110,6 +117,40 @@ def SnapshotTask.get (t : SnapshotTask α) : α :=
 def SnapshotTask.get? (t : SnapshotTask α) : BaseIO (Option α) :=
   return if (← IO.hasFinished t.task) then some t.task.get else none
 
+/--
+Arbitrary value paired with a syntax that should be inspected when considering the value for reuse.
+-/
+structure SyntaxGuarded (α : Type) where
+  /-- Syntax to be inspected for reuse. -/
+  stx : Syntax
+  /-- Potentially reusable value. -/
+  val : α
+
+/--
+Pair of (optional) old snapshot task usable for incremental reuse and new snapshot promise for
+incremental reporting. Inside the elaborator, we build snapshots by carrying such bundles and then
+checking if we can reuse `old?` if set or else redoing the corresponding elaboration step. In either
+case, we derive new bundles for nested snapshots, if any, and finally `resolve` `new` to the result.
+
+Note that failing to `resolve` a created promise will block the language server indefinitely!
+Corresponding `IO.Promise.new` calls should come with a "definitely resolved in ..." comment
+explaining how this is avoided in each case.
+
+In the future, the 1-element history `old?` may be replaced with a global cache indexed by strong
+hashes but the promise will still need to be passed through the elaborator.
+-/
+structure SnapshotBundle (α : Type) where
+  /--
+  Snapshot task of corresponding elaboration in previous document version if any, paired with its
+  old syntax to be considered for reuse. Should be set to `none` as soon as reuse can be ruled out.
+  -/
+  old? : Option (SyntaxGuarded (SnapshotTask α))
+  /--
+  Promise of snapshot value for the current document. When resolved, the language server will
+  report its result even before the current elaborator invocation has finished.
+  -/
+  new  : IO.Promise α
+
 /--
   Tree of snapshots where each snapshot comes with an array of asynchronous further subtrees. Used
   for asynchronously collecting information about the entirety of snapshots in the language server.
@@ -118,7 +159,7 @@ def SnapshotTask.get? (t : SnapshotTask α) : BaseIO (Option α) :=
 inductive SnapshotTree where
   /-- Creates a snapshot tree node. -/
   | mk (element : Snapshot) (children : Array (SnapshotTask SnapshotTree))
-deriving Nonempty
+deriving Inhabited
 
 /-- The immediately available element of the snapshot tree node. -/
 abbrev SnapshotTree.element : SnapshotTree → Snapshot
@@ -135,6 +176,39 @@ class ToSnapshotTree (α : Type) where
   toSnapshotTree : α → SnapshotTree
 export ToSnapshotTree (toSnapshotTree)
 
+instance [ToSnapshotTree α] : ToSnapshotTree (Option α) where
+  toSnapshotTree
+    | some a => toSnapshotTree a
+    | none   => default
+
+/-- Snapshot type without child nodes. -/
+structure SnapshotLeaf extends Snapshot
+deriving Nonempty, TypeName
+
+instance : ToSnapshotTree SnapshotLeaf where
+  toSnapshotTree s := SnapshotTree.mk s.toSnapshot #[]
+
+/-- Arbitrary snapshot type, used for extensibility. -/
+structure DynamicSnapshot where
+  /-- Concrete snapshot value as `Dynamic`. -/
+  val  : Dynamic
+  /-- Snapshot tree retrieved from `val` before erasure. -/
+  tree : SnapshotTree
+deriving Nonempty
+
+instance : ToSnapshotTree DynamicSnapshot where
+  toSnapshotTree s := s.tree
+
+/-- Creates a `DynamicSnapshot` from a typed snapshot value. -/
+def DynamicSnapshot.ofTyped [TypeName α] [ToSnapshotTree α] (val : α) : DynamicSnapshot where
+  val := .mk val
+  tree := ToSnapshotTree.toSnapshotTree val
+
+/-- Returns the original snapshot value if it is of the given type. -/
+def DynamicSnapshot.toTyped? (α : Type) [TypeName α] (snap : DynamicSnapshot) :
+    Option α :=
+  snap.val.get? α
+
 /--
   Option for printing end position of each message in addition to start position. Used for testing
   message ranges in the test suite. -/
@@ -187,7 +261,7 @@ Creates snapshot message log from non-interactive message log, also allocating a
 that can be used by the server to memorize interactive diagnostics derived from the log.
 -/
 def Snapshot.Diagnostics.ofMessageLog (msgLog : Lean.MessageLog) :
-    ProcessingM Snapshot.Diagnostics := do
+    BaseIO Snapshot.Diagnostics := do
   return { msgLog, interactiveDiagsRef? := some (← IO.mkRef none) }
 
 /-- Creates diagnostics from a single error message that should span the whole file. -/

src/Lean/Language/Lean.lean

@@ -58,6 +58,51 @@ exist currently and likely it could at best be approximated by e.g. "furthest `t
 we remain at "go two commands up" at this point.
 -/
 
+/-!
+# Note [Incremental Command Elaboration]
+
+Because of Lean's use of persistent data structures, incremental reuse of fully elaborated commands
+is easy because we can simply snapshot the entire state after each command and then restart
+elaboration using the stored state at the point of change. However, incrementality within
+elaboration of a single command such as between tactic steps is much harder because we cannot simply
+return from those points to the language processor in a way that we can later resume from there.
+Instead, we exchange the need for continuations with some limited mutability: by allocating an
+`IO.Promise` "cell" in the language processor, we can both pass it to the elaborator to eventually
+fill it using `Promise.resolve` as well as convert it to a `Task` that will wait on that resolution
+using `Promise.result` and return it as part of the command snapshot created by the language
+processor. The elaborator can then create new promises itself and store their `result` when
+resolving an outer promise to create an arbitrary tree of promise-backed snapshot tasks. Thus, we
+can enable incremental reporting and reuse inside the elaborator using the same snapshot tree data
+structures as outside without having to change the elaborator's control flow.
+
+While ideally we would decide what can be reused during command elaboration using strong hashes over
+the state and inputs, currently we rely on simpler syntactic checks: if all the syntax inspected up
+to a certain point is unchanged, we can assume that the old state can be reused.  The central
+`SnapshotBundle` type passed inwards through the elaborator for this purpose combines the following
+data:
+* the `IO.Promise` to be resolved to an elaborator snapshot (whose type depends on the specific
+  elaborator part we're in, e.g. `)
+* if there was a previous run:
+  * a `SnapshotTask` holding the corresponding snapshot of the run
+  * the relevant `Syntax` of the previous run to be compared before any reuse
+
+Note that as we do not wait for the previous run to finish before starting to elaborate the next
+one, the `SnapshotTask` task may not be finished yet. Indeed, if we do find that we can reuse the
+contained state, we will want to explicitly wait for it instead of redoing the work. On the other
+hand, the `Syntax` is not surrounded by a task so that we can immediately access it for comparisons,
+even if the snapshot task may, eventually, give access to the same syntax tree.
+
+TODO: tactic examples
+
+While it is generally true that we can provide incremental reporting even without reuse, we
+generally want to avoid that when it would be confusing/annoying, e.g. when a tactic block is run
+multiple times because otherwise the progress bar would snap back and forth multiple times. For this
+purpose, we can disable both incremental modes using `Term.withoutTacticIncrementality`, assuming we
+opted into incrementality because of other parts of the combinator. `induction` is an example of
+this because there are some induction alternatives that are run multiple times, so we disable all of
+incrementality for them.
+-/
+
 set_option linter.missingDocs true
 
 namespace Lean.Language.Lean
@@ -84,34 +129,31 @@ register_builtin_option showPartialSyntaxErrors : Bool := {
 
 /-! The hierarchy of Lean snapshot types -/
 
-/-- Final state of processing of a command. -/
-structure CommandFinishedSnapshot extends Snapshot where
+/-- Snapshot after elaboration of the entire command. -/
+structure CommandFinishedSnapshot extends Language.Snapshot where
   /-- Resulting elaboration state. -/
   cmdState : Command.State
 deriving Nonempty
 instance : ToSnapshotTree CommandFinishedSnapshot where
   toSnapshotTree s := ⟨s.toSnapshot, #[]⟩
 
-/--
-  State after processing a command's signature and before executing its tactic body, if any. Other
-  commands should immediately proceed to `finished`. -/
--- TODO: tactics
-structure CommandSignatureProcessedSnapshot extends Snapshot where
-  /-- State after processing is finished. -/
-  finishedSnap : SnapshotTask CommandFinishedSnapshot
-deriving Nonempty
-instance : ToSnapshotTree CommandSignatureProcessedSnapshot where
-  toSnapshotTree s := ⟨s.toSnapshot, #[s.finishedSnap.map (sync := true) toSnapshotTree]⟩
-
 /-- State after a command has been parsed. -/
 structure CommandParsedSnapshotData extends Snapshot where
   /-- Syntax tree of the command. -/
   stx : Syntax
   /-- Resulting parser state. -/
   parserState : Parser.ModuleParserState
-  /-- Signature processing task. -/
-  sigSnap : SnapshotTask CommandSignatureProcessedSnapshot
+  /--
+  Snapshot for incremental reporting and reuse during elaboration, type dependent on specific
+  elaborator.
+   -/
+  elabSnap : SnapshotTask DynamicSnapshot
+  /-- State after processing is finished. -/
+  finishedSnap : SnapshotTask CommandFinishedSnapshot
+  /-- Cache for `save`; to be replaced with incrementality. -/
+  tacticCache : IO.Ref Tactic.Cache
 deriving Nonempty
+
 /-- State after a command has been parsed. -/
 -- workaround for lack of recursive structures
 inductive CommandParsedSnapshot where
@@ -123,22 +165,23 @@ deriving Nonempty
 abbrev CommandParsedSnapshot.data : CommandParsedSnapshot → CommandParsedSnapshotData
   | mk data _ => data
 /-- Next command, unless this is a terminal command. -/
--- It would be really nice to not make this depend on `sig.finished` where possible
 abbrev CommandParsedSnapshot.next? : CommandParsedSnapshot →
     Option (SnapshotTask CommandParsedSnapshot)
   | mk _ next? => next?
 partial instance : ToSnapshotTree CommandParsedSnapshot where
   toSnapshotTree := go where
     go s := ⟨s.data.toSnapshot,
-      #[s.data.sigSnap.map (sync := true) toSnapshotTree] |>
+      #[s.data.elabSnap.map (sync := true) toSnapshotTree,
+        s.data.finishedSnap.map (sync := true) toSnapshotTree] |>
         pushOpt (s.next?.map (·.map (sync := true) go))⟩
 
+
 /-- Cancels all significant computations from this snapshot onwards. -/
 partial def CommandParsedSnapshot.cancel (snap : CommandParsedSnapshot) : BaseIO Unit := do
-  -- This is the only relevant computation right now
-  -- TODO: cancel additional elaboration tasks if we add them without switching to implicit
-  -- cancellation
-  snap.data.sigSnap.cancel
+  -- This is the only relevant computation right now, everything else is promises
+  -- TODO: cancel additional elaboration tasks (which will be tricky with `DynamicSnapshot`) if we
+  -- add them without switching to implicit cancellation
+  snap.data.finishedSnap.cancel
   if let some next := snap.next? then
     -- recurse on next command (which may have been spawned just before we cancelled above)
     let _ ← IO.mapTask (sync := true) (·.cancel) next.task
@@ -308,7 +351,7 @@ where
   processHeader (stx : Syntax) (parserState : Parser.ModuleParserState) :
       LeanProcessingM (SnapshotTask HeaderProcessedSnapshot) := do
     let ctx ← read
-    SnapshotTask.ofIO ⟨0, ctx.input.endPos⟩ <|
+    SnapshotTask.ofIO (some ⟨0, ctx.input.endPos⟩) <|
     ReaderT.run (r := ctx) <|  -- re-enter reader in new task
     withHeaderExceptions (α := HeaderProcessedSnapshot) ({ · with result? := none }) do
       let opts ← match (← setupImports stx) with
@@ -362,16 +405,16 @@ where
       -- is not `Inhabited`
       return .pure <| .mk (nextCmdSnap? := none) {
         diagnostics := .empty, stx := .missing, parserState
-        sigSnap := .pure {
-          diagnostics := .empty
-          finishedSnap := .pure { diagnostics := .empty, cmdState } } }
+        elabSnap := .pure <| .ofTyped { diagnostics := .empty : SnapshotLeaf }
+        finishedSnap := .pure { diagnostics := .empty, cmdState }
+        tacticCache := (← IO.mkRef {})
+      }
 
     let unchanged old : BaseIO CommandParsedSnapshot :=
       -- when syntax is unchanged, reuse command processing task as is
       if let some oldNext := old.next? then
         return .mk (data := old.data)
-          (nextCmdSnap? := (← old.data.sigSnap.bindIO (sync := true) fun oldSig =>
-            oldSig.finishedSnap.bindIO (sync := true) fun oldFinished =>
+          (nextCmdSnap? := (← old.data.finishedSnap.bindIO (sync := true) fun oldFinished =>
               -- also wait on old command parse snapshot as parsing is cheap and may allow for
               -- elaboration reuse
               oldNext.bindIO (sync := true) fun oldNext => do
@@ -384,7 +427,7 @@ where
         if (← isBeforeEditPos nextCom.data.parserState.pos) then
           return .pure (← unchanged old)
 
-    SnapshotTask.ofIO ⟨parserState.pos, ctx.input.endPos⟩ do
+    SnapshotTask.ofIO (some ⟨parserState.pos, ctx.input.endPos⟩) do
       let beginPos := parserState.pos
       let scope := cmdState.scopes.head!
       let pmctx := {
@@ -401,21 +444,31 @@ where
         -- on first change, make sure to cancel all further old tasks
         old.cancel
 
-      let sigSnap ← processCmdSignature stx cmdState msgLog.hasErrors beginPos ctx
+      -- definitely resolved in `doElab` task
+      let elabPromise ← IO.Promise.new
+      let tacticCache ← old?.map (·.data.tacticCache) |>.getDM (IO.mkRef {})
+      let finishedSnap ←
+        doElab stx cmdState msgLog.hasErrors beginPos
+          { old? := old?.map fun old => ⟨old.data.stx, old.data.elabSnap⟩, new := elabPromise }
+          tacticCache
+          ctx
+
       let next? ← if Parser.isTerminalCommand stx then pure none
         -- for now, wait on "command finished" snapshot before parsing next command
-        else some <$> (sigSnap.bind (·.finishedSnap)).bindIO fun finished =>
+        else some <$> finishedSnap.bindIO fun finished =>
           parseCmd none parserState finished.cmdState ctx
       return .mk (nextCmdSnap? := next?) {
-        diagnostics := (← Snapshot.Diagnostics.ofMessageLog msgLog ctx.toProcessingContext)
+        diagnostics := (← Snapshot.Diagnostics.ofMessageLog msgLog)
         stx
         parserState
-        sigSnap
+        elabSnap := { range? := finishedSnap.range?, task := elabPromise.result }
+        finishedSnap
+        tacticCache
       }
 
-  processCmdSignature (stx : Syntax) (cmdState : Command.State) (hasParseError : Bool)
-      (beginPos : String.Pos) :
-      LeanProcessingM (SnapshotTask CommandSignatureProcessedSnapshot) := do
+  doElab (stx : Syntax) (cmdState : Command.State) (hasParseError : Bool) (beginPos : String.Pos)
+      (snap : SnapshotBundle DynamicSnapshot) (tacticCache : IO.Ref Tactic.Cache) :
+      LeanProcessingM (SnapshotTask CommandFinishedSnapshot) := do
     let ctx ← read
 
     -- signature elaboration task; for now, does full elaboration
@@ -423,13 +476,26 @@ where
     SnapshotTask.ofIO (stx.getRange?.getD ⟨beginPos, beginPos⟩) do
       let scope := cmdState.scopes.head!
       let cmdStateRef ← IO.mkRef { cmdState with messages := .empty }
-      let cmdCtx : Elab.Command.Context := { ctx with cmdPos := beginPos, tacticCache? := none }
+      /-
+      The same snapshot may be executed by different tasks. So, to make sure `elabCommandTopLevel`
+      has exclusive access to the cache, we create a fresh reference here. Before this change, the
+      following `tacticCache.modify` would reset the tactic post cache while another snapshot was
+      still using it.
+      -/
+      let tacticCacheNew ← IO.mkRef (← tacticCache.get)
+      let cmdCtx : Elab.Command.Context := { ctx with
+        cmdPos       := beginPos
+        tacticCache? := some tacticCacheNew
+        snap?        := some snap
+      }
       let (output, _) ←
         IO.FS.withIsolatedStreams (isolateStderr := stderrAsMessages.get scope.opts) do
           liftM (m := BaseIO) do
             Elab.Command.catchExceptions
               (getResetInfoTrees *> Elab.Command.elabCommandTopLevel stx)
               cmdCtx cmdStateRef
+      let postNew := (← tacticCacheNew.get).post
+      tacticCache.modify fun _ => { pre := postNew, post := {} }
       let cmdState ← cmdStateRef.get
       let mut messages := cmdState.messages
       -- `stx.hasMissing` should imply `hasParseError`, but the latter should be cheaper to check in
@@ -449,14 +515,12 @@ where
           data     := output
         }
       let cmdState := { cmdState with messages }
+      -- definitely resolve eventually
+      snap.new.resolve <| .ofTyped { diagnostics := .empty : SnapshotLeaf }
       return {
-        diagnostics := .empty
-        finishedSnap := .pure {
-          diagnostics :=
-            (← Snapshot.Diagnostics.ofMessageLog cmdState.messages ctx.toProcessingContext)
-          infoTree? := some cmdState.infoState.trees[0]!
-          cmdState
-        }
+        diagnostics := (← Snapshot.Diagnostics.ofMessageLog cmdState.messages)
+        infoTree? := some cmdState.infoState.trees[0]!
+        cmdState
       }
 
 /-- Waits for and returns final environment, if importing was successful. -/
@@ -468,6 +532,6 @@ where goCmd snap :=
   if let some next := snap.next? then
     goCmd next.get
   else
-    snap.data.sigSnap.get.finishedSnap.get.cmdState.env
+    snap.data.finishedSnap.get.cmdState.env
 
 end Lean

src/Lean/Linter/UnusedVariables.lean

@@ -255,6 +255,10 @@ builtin_initialize addBuiltinUnusedVariablesIgnoreFn (fun _ stack opts =>
     (stx.isOfKind ``Lean.Parser.Term.matchAlt && pos == 1) ||
     (stx.isOfKind ``Lean.Parser.Tactic.inductionAltLHS && pos == 2))
 
+/-- `#guard_msgs in cmd` itself runs linters in `cmd` (via `elabCommandTopLevel`), so do not run them again. -/
+builtin_initialize addBuiltinUnusedVariablesIgnoreFn (fun _ stack _ =>
+    stack.any fun (stx, _) => stx.isOfKind ``Lean.guardMsgsCmd)
+
 /-- Get the current list of `IgnoreFunction`s. -/
 def getUnusedVariablesIgnoreFns : CommandElabM (Array IgnoreFunction) := do
   return (unusedVariablesIgnoreFnsExt.getState (← getEnv)).2

src/Lean/Linter/Util.lean

@@ -14,7 +14,8 @@ open Lean.Elab
 
 def logLint [Monad m] [MonadLog m] [AddMessageContext m] [MonadOptions m]
     (linterOption : Lean.Option Bool) (stx : Syntax) (msg : MessageData) : m Unit :=
-  logWarningAt stx (.tagged linterOption.name m!"{msg} [{linterOption.name}]")
+  let disable := m!"note: this linter can be disabled with `set_option {linterOption.name} false`"
+  logWarningAt stx (.tagged linterOption.name m!"{msg}\n{disable}")
 
 /-- If `linterOption` is true, print a linter warning message at the position determined by `stx`.
 -/

src/Lean/Message.lean

@@ -46,6 +46,18 @@ structure PPFormat where
   /-- Searches for synthetic sorries in original input. Used to filter out certain messages. -/
   hasSyntheticSorry : MetavarContext → Bool := fun _ => false
 
+structure TraceData where
+  /-- Trace class, e.g. `Elab.step`. -/
+  cls       : Name
+  /-- 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. -/
+  stopTime  : Float := startTime
+  /-- Whether trace node defaults to collapsed in the infoview. -/
+  collapsed : Bool := true
+  /-- Optional tag shown in `trace.profiler.output` output after the trace class name. -/
+  tag       : String := ""
+
 /-- Structured message data. We use it for reporting errors, trace messages, etc. -/
 inductive MessageData where
   /-- Eagerly formatted text. We inspect this in various hacks, so it is not immediately subsumed by `ofPPFormat`. -/
@@ -65,7 +77,7 @@ inductive MessageData where
   /-- Tagged sections. `Name` should be viewed as a "kind", and is used by `MessageData` inspector functions.
     Example: an inspector that tries to find "definitional equality failures" may look for the tag "DefEqFailure". -/
   | tagged            : Name → MessageData → MessageData
-  | trace (cls : Name) (msg : MessageData) (children : Array MessageData) (collapsed : Bool)
+  | trace (data : TraceData) (msg : MessageData) (children : Array MessageData)
   deriving Inhabited
 
 namespace MessageData
@@ -90,7 +102,7 @@ partial def hasTag : MessageData → Bool
   | group msg               => hasTag msg
   | compose msg₁ msg₂       => hasTag msg₁ || hasTag msg₂
   | tagged n msg            => p n || hasTag msg
-  | trace cls msg msgs _    => p cls || hasTag msg || msgs.any hasTag
+  | trace data msg msgs     => p data.cls || hasTag msg || msgs.any hasTag
   | _                       => false
 
 /-- An empty message. -/
@@ -133,7 +145,7 @@ where
   | group msg               => visit mctx? msg
   | compose msg₁ msg₂       => visit mctx? msg₁ || visit mctx? msg₂
   | tagged _ msg            => visit mctx? msg
-  | trace _ msg msgs _      => visit mctx? msg || msgs.any (visit mctx?)
+  | trace _ msg msgs        => visit mctx? msg || msgs.any (visit mctx?)
   | _                       => false
 
 partial def formatAux : NamingContext → Option MessageDataContext → MessageData → IO Format
@@ -147,8 +159,11 @@ partial def formatAux : NamingContext → Option MessageDataContext → MessageD
   | nCtx, ctx,       nest n d                 => Format.nest n <$> formatAux nCtx ctx d
   | nCtx, ctx,       compose d₁ d₂            => return (← formatAux nCtx ctx d₁) ++ (← formatAux nCtx ctx d₂)
   | nCtx, ctx,       group d                  => Format.group <$> formatAux nCtx ctx d
-  | nCtx, ctx,       trace cls header children _ => do
-    let msg := f!"[{cls}] {(← formatAux nCtx ctx header).nest 2}"
+  | nCtx, ctx,       trace data header children => do
+    let mut msg := f!"[{data.cls}]"
+    if data.startTime != 0 then
+      msg := f!"{msg} [{data.stopTime - data.startTime}]"
+    msg := f!"{msg} {(← formatAux nCtx ctx header).nest 2}"
     let children ← children.mapM (formatAux nCtx ctx)
     return .nest 2 (.joinSep (msg::children.toList) "\n")
 

src/Lean/Meta/AppBuilder.lean

@@ -164,7 +164,7 @@ def mkHEqTrans (h₁ h₂ : Expr) : MetaM Expr := do
     | none, _ => throwAppBuilderException ``HEq.trans ("heterogeneous equality proof expected" ++ hasTypeMsg h₁ hType₁)
     | _, none => throwAppBuilderException ``HEq.trans ("heterogeneous equality proof expected" ++ hasTypeMsg h₂ hType₂)
 
-/-- Given `h : Eq a b`, returns a proof of `HEq a b`. -/
+/-- Given `h : HEq a b` where `a` and `b` have the same type, returns a proof of `Eq a b`. -/
 def mkEqOfHEq (h : Expr) : MetaM Expr := do
   let hType ← infer h
   match hType.heq? with
@@ -174,7 +174,7 @@ def mkEqOfHEq (h : Expr) : MetaM Expr := do
     let u ← getLevel α
     return mkApp4 (mkConst ``eq_of_heq [u]) α a b h
   | _ =>
-    throwAppBuilderException ``HEq.trans m!"heterogeneous equality proof expected{indentExpr h}"
+    throwAppBuilderException ``eq_of_heq m!"heterogeneous equality proof expected{indentExpr h}"
 
 /--
 If `e` is `@Eq.refl α a`, return `a`.
@@ -189,7 +189,7 @@ def isRefl? (e : Expr) : Option Expr := do
 If `e` is `@congrArg α β a b f h`, return `α`, `f` and `h`.
 Also works if `e` can be turned into such an application (e.g. `congrFun`).
 -/
-def congrArg? (e : Expr) : MetaM (Option (Expr × Expr × Expr )) := do
+def congrArg? (e : Expr) : MetaM (Option (Expr × Expr × Expr)) := do
   if e.isAppOfArity ``congrArg 6 then
     let #[α, _β, _a, _b, f, h] := e.getAppArgs | unreachable!
     return some (α, f, h)

src/Lean/Meta/Basic.lean

@@ -301,6 +301,44 @@ structure Context where
     Note that we do not cache results at `whnf` when `canUnfold?` is not `none`. -/
   canUnfold?        : Option (Config → ConstantInfo → CoreM Bool) := none
 
+/--
+The `MetaM` monad is a core component of Lean's metaprogramming framework, facilitating the
+construction and manipulation of expressions (`Lean.Expr`) within Lean.
+
+It builds on top of `CoreM` and additionally provides:
+- A `LocalContext` for managing free variables.
+- A `MetavarContext` for managing metavariables.
+- A `Cache` for caching results of the key `MetaM` operations.
+
+The key operations provided by `MetaM` are:
+- `inferType`, which attempts to automatically infer the type of a given expression.
+- `whnf`, which reduces an expression to the point where the outermost part is no longer reducible
+  but the inside may still contain unreduced expression.
+- `isDefEq`, which determines whether two expressions are definitionally equal, possibly assigning
+  meta variables in the process.
+- `forallTelescope` and `lambdaTelescope`, which make it possible to automatically move into
+  (nested) binders while updating the local context.
+
+The following is a small example that demonstrates how to obtain and manipulate the type of a
+`Fin` expression:
+```
+import Lean
+
+open Lean Meta
+
+def getFinBound (e : Expr) : MetaM (Option Expr) := do
+  let type ← whnf (← inferType e)
+  let_expr Fin bound := type | return none
+  return bound
+
+def a : Fin 100 := 42
+
+run_meta
+  match ← getFinBound (.const ``a []) with
+  | some limit => IO.println (← ppExpr limit)
+  | none => IO.println "no limit found"
+```
+-/
 abbrev MetaM  := ReaderT Context $ StateRefT State CoreM
 
 -- Make the compiler generate specialized `pure`/`bind` so we do not have to optimize through the
@@ -333,6 +371,14 @@ def SavedState.restore (b : SavedState) : MetaM Unit := do
   Core.restore b.core
   modify fun s => { s with mctx := b.meta.mctx, zetaDeltaFVarIds := b.meta.zetaDeltaFVarIds, postponed := b.meta.postponed }
 
+/--
+Restores full state including sources for unique identifiers. Only intended for incremental reuse
+between elaboration runs, not for backtracking within a single run.
+-/
+def SavedState.restoreFull (b : SavedState) : MetaM Unit := do
+  Core.restoreFull b.core
+  set b.meta
+
 instance : MonadBacktrack SavedState MetaM where
   saveState      := Meta.saveState
   restoreState s := s.restore

src/Lean/Meta/Canonicalizer.lean

@@ -84,8 +84,8 @@ private partial def mkKey (e : Expr) : CanonM Key := do
     let key ← match e with
       | .sort .. | .fvar .. | .bvar .. | .lit .. =>
         pure { e := (← shareCommon e) }
-      | .const n ls =>
-        pure { e := (← shareCommon (.const n (List.replicate ls.length levelZero))) }
+      | .const n _ =>
+        pure { e := (← shareCommon (.const n [])) }
       | .mvar .. =>
         -- We instantiate assigned metavariables because the
         -- pretty-printer also instantiates them.
@@ -94,7 +94,7 @@ private partial def mkKey (e : Expr) : CanonM Key := do
         else mkKey eNew
       | .mdata _ a => mkKey a
       | .app .. =>
-        let f := (← mkKey e.getAppFn).e
+        let f := e.getAppFn
         if f.isMVar then
           let eNew ← instantiateMVars e
           unless eNew == e do
@@ -109,7 +109,8 @@ private partial def mkKey (e : Expr) : CanonM Key := do
               pure (mkSort 0) -- some dummy value for erasing implicit
           else
             pure (← mkKey arg).e
-        pure { e := (← shareCommon (mkAppN f args)) }
+        let f' := (← mkKey f).e
+        pure { e := (← shareCommon (mkAppN f' args)) }
       | .lam n t b i =>
         pure { e := (← shareCommon (.lam n (← mkKey t).e (← mkKey b).e i)) }
       | .forallE n t b i =>

src/Lean/Meta/NatInstTesters.lean

@@ -24,10 +24,10 @@ def isInstMulNat (e : Expr) : MetaM Bool := do
   let_expr instMulNat ← e | return false
   return true
 def isInstDivNat (e : Expr) : MetaM Bool := do
-  let_expr Nat.instDivNat ← e | return false
+  let_expr Nat.instDiv ← e | return false
   return true
 def isInstModNat (e : Expr) : MetaM Bool := do
-  let_expr Nat.instModNat ← e | return false
+  let_expr Nat.instMod ← e | return false
   return true
 def isInstNatPowNat (e : Expr) : MetaM Bool := do
   let_expr instNatPowNat ← e | return false

src/Lean/Meta/Offset.lean

@@ -87,8 +87,8 @@ partial def isOffset? (e : Expr) : OptionT MetaM (Expr × Nat) := do
     let (s, k) ← getOffset a
     return (s, k+1)
   | Nat.add a b => add a b
-  | Add.add _ i a b => guard (← matchesInstance i Nat.instAdd); add a b
-  | HAdd.hAdd _ _ _ i a b => guard (← matchesInstance i Nat.instHAdd); add a b
+  | Add.add _ i a b => guard (← matchesInstance i Nat.mkInstAdd); add a b
+  | HAdd.hAdd _ _ _ i a b => guard (← matchesInstance i Nat.mkInstHAdd); add a b
   | _ => failure
 
 end

src/Lean/Meta/Tactic/Cases.lean

@@ -222,15 +222,17 @@ private def unifyCasesEqs (numEqs : Nat) (subgoals : Array CasesSubgoal) : MetaM
       }
 
 private def inductionCasesOn (mvarId : MVarId) (majorFVarId : FVarId) (givenNames : Array AltVarNames) (ctx : Context)
-    : MetaM (Array CasesSubgoal) := mvarId.withContext do
+    (useNatCasesAuxOn : Bool := false) : MetaM (Array CasesSubgoal) := mvarId.withContext do
   let majorType ← inferType (mkFVar majorFVarId)
   let (us, params) ← getInductiveUniverseAndParams majorType
-  let casesOn := mkCasesOnName ctx.inductiveVal.name
+  let mut casesOn := mkCasesOnName ctx.inductiveVal.name
+  if useNatCasesAuxOn && ctx.inductiveVal.name == ``Nat && (← getEnv).contains ``Nat.casesAuxOn then
+    casesOn := ``Nat.casesAuxOn
   let ctors   := ctx.inductiveVal.ctors.toArray
   let s ← mvarId.induction majorFVarId casesOn givenNames
   return toCasesSubgoals s ctors majorFVarId us params
 
-def cases (mvarId : MVarId) (majorFVarId : FVarId) (givenNames : Array AltVarNames := #[]) : MetaM (Array CasesSubgoal) := do
+def cases (mvarId : MVarId) (majorFVarId : FVarId) (givenNames : Array AltVarNames := #[]) (useNatCasesAuxOn : Bool := false) : MetaM (Array CasesSubgoal) := do
   try
     mvarId.withContext do
       mvarId.checkNotAssigned `cases
@@ -243,7 +245,7 @@ def cases (mvarId : MVarId) (majorFVarId : FVarId) (givenNames : Array AltVarNam
            allow callers to specify whether they want the `FVarSubst` or not. -/
         if ctx.inductiveVal.numIndices == 0 then
           -- Simple case
-          inductionCasesOn mvarId majorFVarId givenNames ctx
+          inductionCasesOn mvarId majorFVarId givenNames ctx (useNatCasesAuxOn := useNatCasesAuxOn)
         else
           let s₁ ← generalizeIndices mvarId majorFVarId
           trace[Meta.Tactic.cases] "after generalizeIndices\n{MessageData.ofGoal s₁.mvarId}"
@@ -258,9 +260,14 @@ end Cases
 /--
 Apply `casesOn` using the free variable `majorFVarId` as the major premise (aka discriminant).
 `givenNames` contains user-facing names for each alternative.
+
+- `useNatCasesAuxOn` is a temporary hack for the `rcases` family of tactics.
+  Do not use it, as it is subject to removal.
+  It enables using `Nat.casesAuxOn` instead of `Nat.casesOn`,
+  which causes case splits on `n : Nat` to be represented as `0` and `n' + 1` rather than as `Nat.zero` and `Nat.succ n'`.
 -/
-def _root_.Lean.MVarId.cases (mvarId : MVarId) (majorFVarId : FVarId) (givenNames : Array AltVarNames := #[]) : MetaM (Array CasesSubgoal) :=
-  Cases.cases mvarId majorFVarId givenNames
+def _root_.Lean.MVarId.cases (mvarId : MVarId) (majorFVarId : FVarId) (givenNames : Array AltVarNames := #[]) (useNatCasesAuxOn : Bool := false) : MetaM (Array CasesSubgoal) :=
+  Cases.cases mvarId majorFVarId givenNames (useNatCasesAuxOn := useNatCasesAuxOn)
 
 @[deprecated MVarId.cases]
 def cases (mvarId : MVarId) (majorFVarId : FVarId) (givenNames : Array AltVarNames := #[]) : MetaM (Array CasesSubgoal) :=

src/Lean/Meta/Tactic/FunInd.lean

@@ -943,10 +943,17 @@ def deriveInduction (name : Name) : MetaM Unit := do
 
 def isFunInductName (env : Environment) (name : Name) : Bool := Id.run do
   let .str p s := name | return false
-  unless s = "induct" do return false
-  if (WF.eqnInfoExt.find? env p).isSome then return true
-  if (Structural.eqnInfoExt.find? env p).isSome then return true
-  return false
+  match s with
+  | "induct" =>
+    if (WF.eqnInfoExt.find? env p).isSome then return true
+    if (Structural.eqnInfoExt.find? env p).isSome then return true
+    return false
+  | "mutual_induct" =>
+    if let some eqnInfo := WF.eqnInfoExt.find? env p then
+      if h : eqnInfo.declNames.size > 1 then
+        return eqnInfo.declNames[0] = p
+    return false
+  | _ => return false
 
 builtin_initialize
   registerReservedNamePredicate isFunInductName

src/Lean/Meta/Tactic/Simp/BuiltinSimprocs/Nat.lean

@@ -76,14 +76,14 @@ private inductive NatOffset where
 private partial def NatOffset.asOffset (e : Expr) : Meta.SimpM (Option (Expr × Nat)) := do
   if e.isAppOfArity ``HAdd.hAdd 6 then
     let inst := e.appFn!.appFn!.appArg!
-    unless ← matchesInstance inst Nat.instHAdd do return none
+    unless ← matchesInstance inst Nat.mkInstHAdd do return none
     let b := e.appFn!.appArg!
     let o := e.appArg!
     let some n ← Nat.fromExpr? o | return none
     pure (some (b, n))
   else if e.isAppOfArity ``Add.add 4 then
     let inst := e.appFn!.appFn!.appArg!
-    unless ← matchesInstance inst Nat.instAdd do return none
+    unless ← matchesInstance inst Nat.mkInstAdd do return none
     let b := e.appFn!.appArg!
     let some n ← Nat.fromExpr? e.appArg! | return none
     pure (some (b, n))

src/Lean/Meta/Tactic/TryThis.lean

@@ -567,9 +567,10 @@ def addRewriteSuggestion (ref : Syntax) (rules : List (Expr × Bool))
   -- thus giving more information in the hovers.
   -- Perhaps in future we will have a better way to attach elaboration information to
   -- `Syntax` embedded in a `MessageData`.
+  let toMessageData (e : Expr) : MessageData := if e.isConst then .ofConst e else .ofExpr e
   let mut tacMsg :=
     let rulesMsg := MessageData.sbracket <| MessageData.joinSep
-      (rules.map fun ⟨e, symm⟩ => (if symm then "← " else "") ++ m!"{e}") ", "
+      (rules.map fun ⟨e, symm⟩ => (if symm then "← " else "") ++ toMessageData e) ", "
     if let some loc := loc? then
       m!"rw {rulesMsg} at {loc}"
     else

src/Lean/MetavarContext.lean

@@ -620,6 +620,22 @@ def instantiateMVarsCore (mctx : MetavarContext) (e : Expr) : Expr × MetavarCon
     instantiateExprMVars e
   runST fun _ => instantiate e |>.run |>.run mctx
 
+/-
+Substitutes assigned metavariables in `e` with their assigned value according to the
+`MetavarContext`, recursively.
+
+Example:
+```
+run_meta do
+  let mvar1 ← mkFreshExprMVar (mkConst `Nat)
+  let e := (mkConst `Nat.succ).app mvar1
+  -- e is `Nat.succ ?m.773`, `?m.773` is unassigned
+  mvar1.mvarId!.assign (mkNatLit 42)
+  -- e is `Nat.succ ?m.773`, `?m.773` is assigned to `42`
+  let e' ← instantiateMVars e
+  -- e' is `Nat.succ 42`, `?m.773` is assigned to `42`
+```
+-/
 def instantiateMVars [Monad m] [MonadMCtx m] (e : Expr) : m Expr := do
   if !e.hasMVar then
     return e

src/Lean/Parser/Command.lean

@@ -44,6 +44,11 @@ match against a quotation in a command kind's elaborator). -/
 @[builtin_term_parser low] def quot := leading_parser
   "`(" >> withoutPosition (incQuotDepth (many1Unbox commandParser)) >> ")"
 
+/--
+`/-! <text> -/` defines a *module docstring* that can be displayed by documentation generation
+tools. The string is associated with the corresponding position in the file. It can be used
+multiple times in the same file.
+-/
 @[builtin_command_parser]
 def moduleDoc := leading_parser ppDedent <|
   "/-!" >> commentBody >> ppLine
@@ -146,7 +151,7 @@ is an instance of a general family of type constructions known as inductive type
 It is remarkable that it is possible to construct a substantial edifice of mathematics
 based on nothing more than the type universes, dependent arrow types, and inductive types;
 everything else follows from those.
-Intuitively, an inductive type is built up from a specified list of constructor.
+Intuitively, an inductive type is built up from a specified list of constructors.
 For example, `List α` is the list of elements of type `α`, and is defined as follows:
 ```
 inductive List (α : Type u) where
@@ -209,8 +214,162 @@ def «structure»          := leading_parser
   "namespace " >> checkColGt >> ident
 @[builtin_command_parser] def «end»          := leading_parser
   "end" >> optional (ppSpace >> checkColGt >> ident)
+/-- Declares one or more typed variables, or modifies whether already-declared variables are
+implicit.
+
+Introduces variables that can be used in definitions within the same `namespace` or `section` block.
+When a definition mentions a variable, Lean will add it as an argument of the definition. The
+`variable` command is also able to add typeclass parameters. This is useful in particular when
+writing many definitions that have parameters in common (see below for an example).
+
+Variable declarations have the same flexibility as regular function paramaters. In particular they
+can be [explicit, implicit][binder docs], or [instance implicit][tpil classes] (in which case they
+can be anonymous). This can be changed, for instance one can turn explicit variable `x` into an
+implicit one with `variable {x}`. Note that currently, you should avoid changing how variables are
+bound and declare new variables at the same time; see [issue 2789] for more on this topic.
+
+See [*Variables and Sections* from Theorem Proving in Lean][tpil vars] for a more detailed
+discussion.
+
+[tpil vars]: https://lean-lang.org/theorem_proving_in_lean4/dependent_type_theory.html#variables-and-sections
+(Variables and Sections on Theorem Proving in Lean)
+[tpil classes]: https://lean-lang.org/theorem_proving_in_lean4/type_classes.html
+(Type classes on Theorem Proving in Lean)
+[binder docs]: https://leanprover-community.github.io/mathlib4_docs/Lean/Expr.html#Lean.BinderInfo
+(Documentation for the BinderInfo type)
+[issue 2789]: https://github.com/leanprover/lean4/issues/2789
+(Issue 2789 on github)
+
+## Examples
+
+```lean
+section
+  variable
+    {α : Type u}      -- implicit
+    (a : α)           -- explicit
+    [instBEq : BEq α] -- instance implicit, named
+    [Hashable α]      -- instance implicit, anonymous
+
+  def isEqual (b : α) : Bool :=
+    a == b
+
+  #check isEqual
+  -- isEqual.{u} {α : Type u} (a : α) [instBEq : BEq α] (b : α) : Bool
+
+  variable
+    {a} -- `a` is implicit now
+
+  def eqComm {b : α} := a == b ↔ b == a
+
+  #check eqComm
+  -- eqComm.{u} {α : Type u} {a : α} [instBEq : BEq α] {b : α} : Prop
+end
+```
+
+The following shows a typical use of `variable` to factor out definition arguments:
+
+```lean
+variable (Src : Type)
+
+structure Logger where
+  trace : List (Src × String)
+#check Logger
+-- Logger (Src : Type) : Type
+
+namespace Logger
+  -- switch `Src : Type` to be implicit until the `end Logger`
+  variable {Src}
+
+  def empty : Logger Src where
+    trace := []
+  #check empty
+  -- Logger.empty {Src : Type} : Logger Src
+
+  variable (log : Logger Src)
+
+  def len :=
+    log.trace.length
+  #check len
+  -- Logger.len {Src : Type} (log : Logger Src) : Nat
+
+  variable (src : Src) [BEq Src]
+
+  -- at this point all of `log`, `src`, `Src` and the `BEq` instance can all become arguments
+
+  def filterSrc :=
+    log.trace.filterMap
+      fun (src', str') => if src' == src then some str' else none
+  #check filterSrc
+  -- Logger.filterSrc {Src : Type} (log : Logger Src) (src : Src) [inst✝ : BEq Src] : List String
+
+  def lenSrc :=
+    log.filterSrc src |>.length
+  #check lenSrc
+  -- Logger.lenSrc {Src : Type} (log : Logger Src) (src : Src) [inst✝ : BEq Src] : Nat
+end Logger
+```
+
+-/
 @[builtin_command_parser] def «variable»     := leading_parser
   "variable" >> many1 (ppSpace >> checkColGt >> Term.bracketedBinder)
+/-- Declares one or more universe variables.
+
+`universe u v`
+
+`Prop`, `Type`, `Type u` and `Sort u` are types that classify other types, also known as
+*universes*. In `Type u` and `Sort u`, the variable `u` stands for the universe's *level*, and a
+universe at level `u` can only classify universes that are at levels lower than `u`. For more
+details on type universes, please refer to [the relevant chapter of Theorem Proving in Lean][tpil
+universes].
+
+Just as type arguments allow polymorphic definitions to be used at many different types, universe
+parameters, represented by universe variables, allow a definition to be used at any required level.
+While Lean mostly handles universe levels automatically, declaring them explicitly can provide more
+control when writing signatures. The `universe` keyword allows the declared universe variables to be
+used in a collection of definitions, and Lean will ensure that these definitions use them
+consistently.
+
+[tpil universes]: https://lean-lang.org/theorem_proving_in_lean4/dependent_type_theory.html#types-as-objects
+(Type universes on Theorem Proving in Lean)
+
+```lean
+/- Explicit type-universe parameter. -/
+def id₁.{u} (α : Type u) (a : α) := a
+
+/- Implicit type-universe parameter, equivalent to `id₁`.
+  Requires option `autoImplicit true`, which is the default. -/
+def id₂ (α : Type u) (a : α) := a
+
+/- Explicit standalone universe variable declaration, equivalent to `id₁` and `id₂`. -/
+universe u
+def id₃ (α : Type u) (a : α) := a
+```
+
+On a more technical note, using a universe variable only in the right-hand side of a definition
+causes an error if the universe has not been declared previously.
+
+```lean
+def L₁.{u} := List (Type u)
+
+-- def L₂ := List (Type u) -- error: `unknown universe level 'u'`
+
+universe u
+def L₃ := List (Type u)
+```
+
+## Examples
+
+```lean
+universe u v w
+
+structure Pair (α : Type u) (β : Type v) : Type (max u v) where
+  a : α
+  b : β
+
+#check Pair.{v, w}
+-- Pair : Type v → Type w → Type (max v w)
+```
+-/
 @[builtin_command_parser] def «universe»     := leading_parser
   "universe" >> many1 (ppSpace >> checkColGt >> ident)
 @[builtin_command_parser] def check          := leading_parser
@@ -242,6 +401,30 @@ def eraseAttr := leading_parser
   "attribute " >> "[" >>
     withoutPosition (sepBy1 (eraseAttr <|> Term.attrInstance) ", ") >>
   "]" >> many1 (ppSpace >> ident)
+/-- Adds names from other namespaces to the current namespace.
+
+The command `export Some.Namespace (name₁ name₂)` makes `name₁` and `name₂`:
+
+- visible in the current namespace without prefix `Some.Namespace`, like `open`, and
+- visible from outside the current namespace `N` as `N.name₁` and `N.name₂`.
+
+## Examples
+
+```lean
+namespace Morning.Sky
+  def star := "venus"
+end Morning.Sky
+
+namespace Evening.Sky
+  export Morning.Sky (star)
+  -- `star` is now in scope
+  #check star
+end Evening.Sky
+
+-- `star` is visible in `Evening.Sky`
+#check Evening.Sky.star
+```
+-/
 @[builtin_command_parser] def «export»       := leading_parser
   "export " >> ident >> " (" >> many1 ident >> ")"
 @[builtin_command_parser] def «import»       := leading_parser
@@ -262,6 +445,118 @@ def openScoped       := leading_parser
 def openDecl         :=
   withAntiquot (mkAntiquot "openDecl" `Lean.Parser.Command.openDecl (isPseudoKind := true)) <|
     openHiding <|> openRenaming <|> openOnly <|> openSimple <|> openScoped
+/-- Makes names from other namespaces visible without writing the namespace prefix.
+
+Names that are made available with `open` are visible within the current `section` or `namespace`
+block. This makes referring to (type) definitions and theorems easier, but note that it can also
+make [scoped instances], notations, and attributes from a different namespace available.
+
+The `open` command can be used in a few different ways:
+
+* `open Some.Namespace.Path1 Some.Namespace.Path2` makes all non-protected names in
+  `Some.Namespace.Path1` and `Some.Namespace.Path2` available without the prefix, so that
+  `Some.Namespace.Path1.x` and `Some.Namespace.Path2.y` can be referred to by writing only `x` and
+  `y`.
+
+* `open Some.Namespace.Path hiding def1 def2` opens all non-protected names in `Some.Namespace.Path`
+  except `def1` and `def2`.
+
+* `open Some.Namespace.Path (def1 def2)` only makes `Some.Namespace.Path.def1` and
+  `Some.Namespace.Path.def2` available without the full prefix, so `Some.Namespace.Path.def3` would
+  be unaffected.
+
+  This works even if `def1` and `def2` are `protected`.
+
+* `open Some.Namespace.Path renaming def1 → def1', def2 → def2'` same as `open Some.Namespace.Path
+  (def1 def2)` but `def1`/`def2`'s names are changed to `def1'`/`def2'`.
+
+  This works even if `def1` and `def2` are `protected`.
+
+* `open scoped Some.Namespace.Path1 Some.Namespace.Path2` **only** opens [scoped instances],
+  notations, and attributes from `Namespace1` and `Namespace2`; it does **not** make any other name
+  available.
+
+* `open <any of the open shapes above> in` makes the names `open`-ed visible only in the next
+  command or expression.
+
+[scoped instance]: https://lean-lang.org/theorem_proving_in_lean4/type_classes.html#scoped-instances
+(Scoped instances in Theorem Proving in Lean)
+
+
+## Examples
+
+```lean
+/-- SKI combinators https://en.wikipedia.org/wiki/SKI_combinator_calculus -/
+namespace Combinator.Calculus
+  def I (a : α) : α := a
+  def K (a : α) : β → α := fun _ => a
+  def S (x : α → β → γ) (y : α → β) (z : α) : γ := x z (y z)
+end Combinator.Calculus
+
+section
+  -- open everything under `Combinator.Calculus`, *i.e.* `I`, `K` and `S`,
+  -- until the section ends
+  open Combinator.Calculus
+
+  theorem SKx_eq_K : S K x = I := rfl
+end
+
+-- open everything under `Combinator.Calculus` only for the next command (the next `theorem`, here)
+open Combinator.Calculus in
+theorem SKx_eq_K' : S K x = I := rfl
+
+section
+  -- open only `S` and `K` under `Combinator.Calculus`
+  open Combinator.Calculus (S K)
+
+  theorem SKxy_eq_y : S K x y = y := rfl
+
+  -- `I` is not in scope, we have to use its full path
+  theorem SKxy_eq_Iy : S K x y = Combinator.Calculus.I y := rfl
+end
+
+section
+  open Combinator.Calculus
+    renaming
+      I → identity,
+      K → konstant
+
+  #check identity
+  #check konstant
+end
+
+section
+  open Combinator.Calculus
+    hiding S
+
+  #check I
+  #check K
+end
+
+section
+  namespace Demo
+    inductive MyType
+    | val
+
+    namespace N1
+      scoped infix:68 " ≋ " => BEq.beq
+
+      scoped instance : BEq MyType where
+        beq _ _ := true
+
+      def Alias := MyType
+    end N1
+  end Demo
+
+  -- bring `≋` and the instance in scope, but not `Alias`
+  open scoped Demo.N1
+
+  #check Demo.MyType.val == Demo.MyType.val
+  #check Demo.MyType.val ≋ Demo.MyType.val
+  -- #check Alias -- unknown identifier 'Alias'
+end
+```
+-/
 @[builtin_command_parser] def «open»    := leading_parser
   withPosition ("open" >> openDecl)
 

src/Lean/Parser/Extension.lean

@@ -498,13 +498,13 @@ private def BuiltinParserAttribute.add (attrName : Name) (catName : Name)
 The parsing tables for builtin parsers are "stored" in the extracted source code.
 -/
 def registerBuiltinParserAttribute (attrName declName : Name)
-    (behavior := LeadingIdentBehavior.default) : IO Unit := do
+    (behavior := LeadingIdentBehavior.default) (ref : Name := by exact decl_name%) : IO Unit := do
   let .str ``Lean.Parser.Category s := declName
     | throw (IO.userError "`declName` should be in Lean.Parser.Category")
   let catName := Name.mkSimple s
   addBuiltinParserCategory catName declName behavior
   registerBuiltinAttribute {
-    ref             := declName
+    ref             := ref
     name            := attrName
     descr           := "Builtin parser"
     add             := fun declName stx kind => liftM $ BuiltinParserAttribute.add attrName catName declName stx kind

src/Lean/Parser/Term.lean

@@ -266,29 +266,49 @@ open Lean.PrettyPrinter Parenthesizer Syntax.MonadTraverser in
     term.parenthesizer prec
     visitToken
 
-def explicitBinder (requireType := false) := ppGroup $ leading_parser
+/--
+Explicit binder, like `(x y : A)` or `(x y)`.
+Default values can be specified using `(x : A := v)` syntax, and tactics using `(x : A := by tac)`.
+-/
+def explicitBinder (requireType := false) := leading_parser ppGroup <|
   "(" >> withoutPosition (many1 binderIdent >> binderType requireType >> optional (binderTactic <|> binderDefault)) >> ")"
 /--
-Implicit binder. In regular applications without `@`, it is automatically inserted
-and solved by unification whenever all explicit parameters before it are specified.
+Implicit binder, like `{x y : A}` or `{x y}`.
+In regular applications, whenever all parameters before it have been specified,
+then a `_` placeholder is automatically inserted for this parameter.
+Implicit parameters should be able to be determined from the other arguments and the return type
+by unification.
+
+In `@` explicit mode, implicit binders behave like explicit binders.
 -/
-def implicitBinder (requireType := false) := ppGroup $ leading_parser
+def implicitBinder (requireType := false) := leading_parser ppGroup <|
   "{" >> withoutPosition (many1 binderIdent >> binderType requireType) >> "}"
 def strictImplicitLeftBracket := atomic (group (symbol "{" >> "{")) <|> "⦃"
 def strictImplicitRightBracket := atomic (group (symbol "}" >> "}")) <|> "⦄"
 /--
-Strict-implicit binder. In contrast to `{ ... }` regular implicit binders,
-a strict-implicit binder is inserted automatically only when at least one subsequent
-explicit parameter is specified.
+Strict-implicit binder, like `⦃x y : A⦄` or `⦃x y⦄`.
+In contrast to `{ ... }` implicit binders, strict-implicit binders do not automatically insert
+a `_` placeholder until at least one subsequent explicit parameter is specified.
+Do *not* use strict-implicit binders unless there is a subsequent explicit parameter.
+Assuming this rule is followed, for fully applied expressions implicit and strict-implicit binders have the same behavior.
+
+Example: If `h : ∀ ⦃x : A⦄, x ∈ s → p x` and `hs : y ∈ s`,
+then `h` by itself elaborates to itself without inserting `_` for the `x : A` parameter,
+and `h hs` has type `p y`.
+In contrast, if `h' : ∀ {x : A}, x ∈ s → p x`, then `h` by itself elaborates to have type `?m ∈ s → p ?m`
+with `?m` a fresh metavariable.
 -/
-def strictImplicitBinder (requireType := false) := ppGroup <| leading_parser
+def strictImplicitBinder (requireType := false) := leading_parser ppGroup <|
   strictImplicitLeftBracket >> many1 binderIdent >>
   binderType requireType >> strictImplicitRightBracket
 /--
-Instance-implicit binder. In regular applications without `@`, it is automatically inserted
-and solved by typeclass inference of the specified class.
+Instance-implicit binder, like `[C]` or `[inst : C]`.
+In regular applications without `@` explicit mode, it is automatically inserted
+and solved for by typeclass inference for the specified class `C`.
+In `@` explicit mode, if `_` is used for an an instance-implicit parameter, then it is still solved for by typeclass inference;
+use `(_)` to inhibit this and have it be solved for by unification instead, like an implicit argument.
 -/
-def instBinder := ppGroup <| leading_parser
+def instBinder := leading_parser ppGroup <|
   "[" >> withoutPosition (optIdent >> termParser) >> "]"
 /-- A `bracketedBinder` matches any kind of binder group that uses some kind of brackets:
 * An explicit binder like `(x y : A)`
@@ -746,6 +766,17 @@ is short for accessing the `i`-th field (1-indexed) of `e` if it is of a structu
 @[builtin_term_parser] def arrow    := trailing_parser
   checkPrec 25 >> unicodeSymbol " → " " -> " >> termParser 25
 
+/--
+Syntax kind for syntax nodes representing the field of a projection in the `InfoTree`.
+Specifically, the `InfoTree` node for a projection `s.f` contains a child `InfoTree` node
+with syntax ``(Syntax.node .none identProjKind #[`f])``.
+
+This is necessary because projection syntax cannot always be detected purely syntactically
+(`s.f` may refer to either the identifier `s.f` or a projection `s.f` depending on
+the available context).
+-/
+def identProjKind := `Lean.Parser.Term.identProj
+
 def isIdent (stx : Syntax) : Bool :=
   -- antiquotations should also be allowed where an identifier is expected
   stx.isAntiquot || stx.isIdent

src/Lean/PrettyPrinter.lean

@@ -46,9 +46,6 @@ def ppExprWithInfos (e : Expr) (optsPerPos : Delaborator.OptionsPerPos := {}) (d
     let fmt ← ppTerm stx
     return ⟨fmt, infos⟩
 
-def ppConst (e : Expr) : MetaM Format := do
-  ppUsing e fun e => return (← delabCore e (delab := Delaborator.delabConst)).1
-
 @[export lean_pp_expr]
 def ppExprLegacy (env : Environment) (mctx : MetavarContext) (lctx : LocalContext) (opts : Options) (e : Expr) : IO Format :=
   Prod.fst <$> ((ppExpr e).run' { lctx := lctx } { mctx := mctx }).toIO { options := opts, fileName := "<PrettyPrinter>", fileMap := default } { env := env }
@@ -75,8 +72,8 @@ private partial def noContext : MessageData → MessageData
   | MessageData.group msg  => MessageData.group (noContext msg)
   | MessageData.compose msg₁ msg₂ => MessageData.compose (noContext msg₁) (noContext msg₂)
   | MessageData.tagged tag msg => MessageData.tagged tag (noContext msg)
-  | MessageData.trace cls header children collapsed =>
-    MessageData.trace cls (noContext header) (children.map noContext) collapsed
+  | MessageData.trace data header children =>
+    MessageData.trace data (noContext header) (children.map noContext)
   | msg => msg
 
 -- strip context (including environments with registered pretty printers) to prevent infinite recursion when pretty printing pretty printer error
@@ -101,4 +98,37 @@ unsafe def registerParserCompilers : IO Unit := do
   ParserCompiler.registerParserCompiler ⟨`formatter, formatterAttribute, combinatorFormatterAttribute⟩
 
 end PrettyPrinter
+
+namespace MessageData
+
+open Lean PrettyPrinter Delaborator
+
+/--
+Turns a `MetaM FormatWithInfos` into a `MessageData` using `.ofPPFormat` and running the monadic value in the given context.
+Uses the `pp.tagAppFns` option to annotate constants with terminfo, which is necessary for seeing the type on mouse hover.
+-/
+def ofFormatWithInfos
+    (fmt : MetaM FormatWithInfos)
+    (noContext : Unit → Format := fun _ => "<no context, could not generate MessageData>") : MessageData :=
+  .ofPPFormat
+  { pp := fun
+      | some ctx => ctx.runMetaM <| withOptions (pp.tagAppFns.set · true) fmt
+      | none => return noContext () }
+
+/-- Pretty print a const expression using `delabConst` and generate terminfo.
+This function avoids inserting `@` if the constant is for a function whose first
+argument is implicit, which is what the default `toMessageData` for `Expr` does.
+Panics if `e` is not a constant. -/
+def ofConst (e : Expr) : MessageData :=
+  if e.isConst then
+    .ofFormatWithInfos (PrettyPrinter.ppExprWithInfos (delab := delabConst) e) fun _ => f!"{e}"
+  else
+    panic! "not a constant"
+
+/-- Generates `MessageData` for a declaration `c` as `c.{<levels>} <params> : <type>`, with terminfo. -/
+def signature (c : Name) : MessageData :=
+  .ofFormatWithInfos (PrettyPrinter.ppSignature c) fun _ => f!"{c}"
+
+end MessageData
+
 end Lean

src/Lean/ReservedNameAction.lean

@@ -67,12 +67,18 @@ def realizeGlobalConstNoOverloadCore (n : Name) : CoreM Name := do
 
 /--
 Similar to `resolveGlobalConst`, but also executes reserved name actions.
+
+Consider using `realizeGlobalConstWithInfo` if you want the syntax to show the resulting name's info
+on hover.
 -/
 def realizeGlobalConst (stx : Syntax) : CoreM (List Name) :=
   withRef stx do preprocessSyntaxAndResolve stx realizeGlobalConstCore
 
 /--
 Similar to `realizeGlobalConstNoOverload`, but also executes reserved name actions.
+
+Consider using `realizeGlobalConstNoOverloadWithInfo` if you want the syntax to show the resulting
+name's info on hover.
 -/
 def realizeGlobalConstNoOverload (id : Syntax) : CoreM Name := do
   ensureNonAmbiguous id (← realizeGlobalConst id)

src/Lean/ResolveName.lean

@@ -289,7 +289,7 @@ def filterFieldList [Monad m] [MonadError m] (n : Name) (cs : List (Name × List
   if cs.isEmpty then throwUnknownConstant n
   return cs.map (·.1)
 
-/-- Given a name `n`, return a list of possible interpretations for global constants.
+/-- Given a name `n`, returns a list of possible interpretations for global constants.
 
 Similar to `resolveGlobalName`, but discard any candidate whose `fieldList` is not empty.
 For identifiers taken from syntax, use `resolveGlobalConst` instead, which respects preresolved names. -/
@@ -320,11 +320,14 @@ def preprocessSyntaxAndResolve [Monad m] [MonadResolveName m] [MonadEnv m] [Mona
   | _ => throwErrorAt stx s!"expected identifier"
 
 /--
-Interpret the syntax `n` as an identifier for a global constant, and return a list of resolved
+Interprets the syntax `n` as an identifier for a global constant, and returns a list of resolved
 constant names that it could be referring to based on the currently open namespaces.
 This should be used instead of `resolveGlobalConstCore` for identifiers taken from syntax
 because `Syntax` objects may have names that have already been resolved.
 
+Consider using `realizeGlobalConst` if you need to handle reserved names, and
+`realizeGlobalConstWithInfo` if you want the syntax to show the resulting name's info on hover.
+
 ## Example:
 ```
 def Boo.x   := 1
@@ -345,7 +348,7 @@ def resolveGlobalConst [Monad m] [MonadResolveName m] [MonadEnv m] [MonadError m
   preprocessSyntaxAndResolve stx resolveGlobalConstCore
 
 /--
-Given a list of names produced by `resolveGlobalConst`, throw an error if the list does not contain
+Given a list of names produced by `resolveGlobalConst`, throws an error if the list does not contain
 exactly one element.
 Recall that `resolveGlobalConst` does not return empty lists.
 -/
@@ -355,9 +358,13 @@ def ensureNonAmbiguous [Monad m] [MonadError m] (id : Syntax) (cs : List Name) :
   | [c] => pure c
   | _   => throwErrorAt id s!"ambiguous identifier '{id}', possible interpretations: {cs.map mkConst}"
 
-/-- Interpret the syntax `n` as an identifier for a global constant, and return a resolved
+/-- Interprets the syntax `n` as an identifier for a global constant, and return a resolved
 constant name. If there are multiple possible interpretations it will throw.
 
+Consider using `realizeGlobalConstNoOverload` if you need to handle reserved names, and
+`realizeGlobalConstNoOverloadWithInfo` if you
+want the syntax to show the resulting name's info on hover.
+
 ## Example:
 ```
 def Boo.x   := 1

src/Lean/Server/FileWorker.lean

@@ -73,6 +73,11 @@ structure WorkerContext where
   maxDocVersionRef     : IO.Ref Int
   freshRequestIdRef    : IO.Ref Int
   /--
+  Channel that receives a message for every a `$/lean/fileProgress` notification, indicating whether
+  the notification suggests that the file is currently being processed.
+  -/
+  chanIsProcessing     : IO.Channel Bool
+  /--
   Diagnostics that are included in every single `textDocument/publishDiagnostics` notification.
   -/
   stickyDiagnosticsRef : IO.Ref StickyDiagnostics
@@ -223,7 +228,8 @@ This option can only be set on the command line, not in the lakefile or via `set
       | t::ts => do
         let mut st := st
         unless (← IO.hasFinished t.task) do
-          ctx.chanOut.send <| mkFileProgressAtPosNotification doc.meta t.range.start
+          if let some range := t.range? then
+            ctx.chanOut.send <| mkFileProgressAtPosNotification doc.meta range.start
           if !st.hasBlocked then
             publishDiagnostics ctx doc
             st := { st with hasBlocked := true }
@@ -314,8 +320,9 @@ section Initialization
     catch _ => pure ()
     let maxDocVersionRef ← IO.mkRef 0
     let freshRequestIdRef ← IO.mkRef 0
+    let chanIsProcessing ← IO.Channel.new
     let stickyDiagnosticsRef ← IO.mkRef ∅
-    let chanOut ← mkLspOutputChannel maxDocVersionRef
+    let chanOut ← mkLspOutputChannel maxDocVersionRef chanIsProcessing
     let srcSearchPathPromise ← IO.Promise.new
 
     let processor := Language.Lean.process (setupImports meta chanOut srcSearchPathPromise)
@@ -333,6 +340,7 @@ section Initialization
       clientHasWidgets
       maxDocVersionRef
       freshRequestIdRef
+      chanIsProcessing
       cmdlineOpts := opts
       stickyDiagnosticsRef
     }
@@ -355,7 +363,7 @@ section Initialization
         the output FS stream after discarding outdated notifications. This is the only component of
         the worker with access to the output stream, so we can synchronize messages from parallel
         elaboration tasks here. -/
-    mkLspOutputChannel maxDocVersion : IO (IO.Channel JsonRpc.Message) := do
+    mkLspOutputChannel maxDocVersion chanIsProcessing : IO (IO.Channel JsonRpc.Message) := do
       let chanOut ← IO.Channel.new
       let _ ← chanOut.forAsync (prio := .dedicated) fun msg => do
         -- discard outdated notifications; note that in contrast to responses, notifications can
@@ -374,6 +382,9 @@ section Initialization
           -- note that because of `server.reportDelayMs`, we cannot simply set `maxDocVersion` here
           -- as that would allow outdated messages to be reported until the delay is over
         o.writeLspMessage msg |>.catchExceptions (fun _ => pure ())
+        if let .notification "$/lean/fileProgress" (some params) := msg then
+          if let some (params : LeanFileProgressParams) := fromJson? (toJson params) |>.toOption then
+            chanIsProcessing.send (! params.processing.isEmpty)
       return chanOut
 
     getImportClosure? (snap : Language.Lean.InitialSnapshot) : Array Name := Id.run do
@@ -667,6 +678,13 @@ def runRefreshTask : WorkerM (Task (Except IO.Error Unit)) := do
   let ctx ← read
   IO.asTask do
     while ! (←IO.checkCanceled) do
+      let pastProcessingStates ← ctx.chanIsProcessing.recvAllCurrent
+      if pastProcessingStates.isEmpty then
+        -- Processing progress has not changed since we last sent out a refresh request
+        -- => do not send out another one for now so that we do not make the client spam
+        --    semantic token requests while idle and already having received an up-to-date state
+        IO.sleep 1000
+        continue
       sendServerRequest ctx "workspace/semanticTokens/refresh" (none : Option Nat)
       IO.sleep 2000
 

src/Lean/Server/FileWorker/RequestHandling.lean

@@ -419,6 +419,9 @@ where
             return toDocumentSymbols text stxs (syms.push sym) stack
         toDocumentSymbols text stxs syms stack
 
+/--
+`SyntaxNodeKind`s for which the syntax node and its children receive no semantic highlighting.
+-/
 def noHighlightKinds : Array SyntaxNodeKind := #[
   -- usually have special highlighting by the client
   ``Lean.Parser.Term.sorry,
@@ -429,17 +432,8 @@ def noHighlightKinds : Array SyntaxNodeKind := #[
   ``Lean.Parser.Command.docComment,
   ``Lean.Parser.Command.moduleDoc]
 
-structure SemanticTokensContext where
-  beginPos : String.Pos
-  endPos?  : Option String.Pos
-  text     : FileMap
-  snap     : Snapshot
-
-structure SemanticTokensState where
-  data       : Array Nat
-  lastLspPos : Lsp.Position
-
 -- TODO: make extensible, or don't
+/-- Keywords for which a specific semantic token is provided. -/
 def keywordSemanticTokenMap : RBMap String SemanticTokenType compare :=
   RBMap.empty
     |>.insert "sorry" .leanSorryLike
@@ -447,7 +441,112 @@ def keywordSemanticTokenMap : RBMap String SemanticTokenType compare :=
     |>.insert "stop" .leanSorryLike
     |>.insert "#exit" .leanSorryLike
 
-partial def handleSemanticTokens (beginPos : String.Pos) (endPos? : Option String.Pos)
+/-- Semantic token information for a given `Syntax`. -/
+structure LeanSemanticToken where
+  /-- Syntax of the semantic token. -/
+  stx  : Syntax
+  /-- Type of the semantic token. -/
+  type : SemanticTokenType
+
+/-- Semantic token information with absolute LSP positions. -/
+structure AbsoluteLspSemanticToken where
+  /-- Start position of the semantic token. -/
+  pos     : Lsp.Position
+  /-- End position of the semantic token. -/
+  tailPos : Lsp.Position
+  /-- Start position of the semantic token. -/
+  type    : SemanticTokenType
+  deriving BEq, Hashable, FromJson, ToJson
+
+/--
+Given a set of `LeanSemanticToken`, computes the `AbsoluteLspSemanticToken` with absolute
+LSP position information for each token.
+-/
+def computeAbsoluteLspSemanticTokens
+    (text     : FileMap)
+    (beginPos : String.Pos)
+    (endPos?  : Option String.Pos)
+    (tokens   : Array LeanSemanticToken)
+    : Array AbsoluteLspSemanticToken :=
+  tokens.filterMap fun ⟨stx, type⟩ => do
+    let (pos, tailPos) := (← stx.getPos?, ← stx.getTailPos?)
+    guard <| beginPos <= pos && endPos?.all (pos < ·)
+    let (lspPos, lspTailPos) := (text.utf8PosToLspPos pos, text.utf8PosToLspPos tailPos)
+    return ⟨lspPos, lspTailPos, type⟩
+
+/-- Filters all duplicate semantic tokens with the same `pos`, `tailPos` and `type`. -/
+def filterDuplicateSemanticTokens (tokens : Array AbsoluteLspSemanticToken) : Array AbsoluteLspSemanticToken :=
+  tokens.groupByKey id |>.toArray.map (·.1)
+
+/--
+Given a set of `AbsoluteLspSemanticToken`, computes the LSP `SemanticTokens` data with
+token-relative positioning.
+See https://microsoft.github.io/language-server-protocol/specifications/lsp/3.17/specification/#textDocument_semanticTokens.
+-/
+def computeDeltaLspSemanticTokens (tokens : Array AbsoluteLspSemanticToken) : SemanticTokens := Id.run do
+  let tokens := tokens.qsort fun ⟨pos1, tailPos1, _⟩ ⟨pos2, tailPos2, _⟩ =>
+    pos1 < pos2 || pos1 == pos2 && tailPos1 <= tailPos2
+  let mut data : Array Nat := Array.mkEmpty (5*tokens.size)
+  let mut lastPos : Lsp.Position := ⟨0, 0⟩
+  for ⟨pos, tailPos, type⟩ in tokens do
+    let deltaLine := pos.line - lastPos.line
+    let deltaStart := pos.character - (if pos.line == lastPos.line then lastPos.character else 0)
+    let length := tailPos.character - pos.character
+    let tokenType := type.toNat
+    let tokenModifiers := 0
+    data := data ++ #[deltaLine, deltaStart, length, tokenType, tokenModifiers]
+    lastPos := pos
+  return { data }
+
+/--
+Collects all semantic tokens that can be deduced purely from `Syntax`
+without elaboration information.
+-/
+partial def collectSyntaxBasedSemanticTokens : (stx : Syntax) → Array LeanSemanticToken
+  | `($e.$id:ident)    =>
+    let tokens := collectSyntaxBasedSemanticTokens e
+    tokens.push ⟨id, SemanticTokenType.property⟩
+  | `($e |>.$field:ident) =>
+    let tokens := collectSyntaxBasedSemanticTokens e
+    tokens.push ⟨field, SemanticTokenType.property⟩
+  | stx => Id.run do
+    if noHighlightKinds.contains stx.getKind then
+      return #[]
+    let mut tokens :=
+      if stx.isOfKind choiceKind then
+        collectSyntaxBasedSemanticTokens stx[0]
+      else
+        stx.getArgs.map collectSyntaxBasedSemanticTokens |>.flatten
+    let Syntax.atom _ val := stx
+      | return tokens
+    let isRegularKeyword := val.length > 0 && val.front.isAlpha
+    let isHashKeyword := val.length > 1 && val.front == '#' && (val.get ⟨1⟩).isAlpha
+    if ! isRegularKeyword && ! isHashKeyword then
+      return tokens
+    return tokens.push ⟨stx, keywordSemanticTokenMap.findD val .keyword⟩
+
+/-- Collects all semantic tokens from the given `Elab.InfoTree`. -/
+def collectInfoBasedSemanticTokens (i : Elab.InfoTree) : Array LeanSemanticToken :=
+  List.toArray <| i.deepestNodes fun _ i _ => do
+    let .ofTermInfo ti := i
+      | none
+    let .original .. := ti.stx.getHeadInfo
+      | none
+    if let `($_:ident) := ti.stx then
+      if let Expr.fvar fvarId .. := ti.expr then
+        if let some localDecl := ti.lctx.find? fvarId then
+          -- Recall that `isAuxDecl` is an auxiliary declaration used to elaborate a recursive definition.
+          if localDecl.isAuxDecl then
+            if ti.isBinder then
+              return ⟨ti.stx, SemanticTokenType.function⟩
+          else if ! localDecl.isImplementationDetail then
+            return ⟨ti.stx, SemanticTokenType.variable⟩
+    if ti.stx.getKind == Parser.Term.identProjKind then
+      return ⟨ti.stx, SemanticTokenType.property⟩
+    none
+
+/-- Computes the semantic tokens in the range [beginPos, endPos?). -/
+def handleSemanticTokens (beginPos : String.Pos) (endPos? : Option String.Pos)
     : RequestM (RequestTask SemanticTokens) := do
   let doc ← readDoc
   match endPos? with
@@ -462,78 +561,25 @@ partial def handleSemanticTokens (beginPos : String.Pos) (endPos? : Option Strin
     let t := doc.cmdSnaps.waitUntil (·.endPos >= endPos)
     mapTask t fun (snaps, _) => run doc snaps
 where
-  run doc snaps : RequestM SemanticTokens :=
-    StateT.run' (s := { data := #[], lastLspPos := ⟨0, 0⟩ : SemanticTokensState }) do
-      for s in snaps do
-        if s.endPos <= beginPos then
-          continue
-        ReaderT.run (r := SemanticTokensContext.mk beginPos endPos? doc.meta.text s) <|
-          go s.stx
-      return { data := (← get).data }
-  go (stx : Syntax) := do
-    match stx with
-    | `($e.$id:ident)    => go e; addToken id SemanticTokenType.property
-    -- indistinguishable from next pattern
-    --| `(level|$id:ident) => addToken id SemanticTokenType.variable
-    | `($id:ident)       => highlightId id
-    | _ =>
-      if !noHighlightKinds.contains stx.getKind then
-        highlightKeyword stx
-        if stx.isOfKind choiceKind then
-          go stx[0]
-        else
-          stx.getArgs.forM go
-  highlightId (stx : Syntax) : ReaderT SemanticTokensContext (StateT SemanticTokensState RequestM) _ := do
-    if let some range := stx.getRange? then
-      let mut lastPos := range.start
-      for ti in (← read).snap.infoTree.deepestNodes (fun
-        | _, i@(Elab.Info.ofTermInfo ti), _ => match i.pos? with
-          | some ipos => if range.contains ipos then some ti else none
-          | _         => none
-        | _, _, _ => none) do
-        let pos := ti.stx.getPos?.get!
-        -- avoid reporting same position twice; the info node can occur multiple times if
-        -- e.g. the term is elaborated multiple times
-        if pos < lastPos then
-          continue
-        if let Expr.fvar fvarId .. := ti.expr then
-          if let some localDecl := ti.lctx.find? fvarId then
-            -- Recall that `isAuxDecl` is an auxiliary declaration used to elaborate a recursive definition.
-            if localDecl.isAuxDecl then
-              if ti.isBinder then
-                addToken ti.stx SemanticTokenType.function
-            else
-              addToken ti.stx SemanticTokenType.variable
-        else if ti.stx.getPos?.get! > lastPos then
-          -- any info after the start position: must be projection notation
-          addToken ti.stx SemanticTokenType.property
-          lastPos := ti.stx.getPos?.get!
-  highlightKeyword stx := do
-    if let Syntax.atom _ val := stx then
-      if (val.length > 0 && val.front.isAlpha) ||
-         -- Support for keywords of the form `#<alpha>...`
-         (val.length > 1 && val.front == '#' && (val.get ⟨1⟩).isAlpha) then
-        addToken stx (keywordSemanticTokenMap.findD val .keyword)
-  addToken stx type := do
-    let ⟨beginPos, endPos?, text, _⟩ ← read
-    if let (some pos, some tailPos) := (stx.getPos?, stx.getTailPos?) then
-      if beginPos <= pos && endPos?.all (pos < ·) then
-        let lspPos := (← get).lastLspPos
-        let lspPos' := text.utf8PosToLspPos pos
-        let deltaLine := lspPos'.line - lspPos.line
-        let deltaStart := lspPos'.character - (if lspPos'.line == lspPos.line then lspPos.character else 0)
-        let length := (text.utf8PosToLspPos tailPos).character - lspPos'.character
-        let tokenType := type.toNat
-        let tokenModifiers := 0
-        modify fun st => {
-          data := st.data ++ #[deltaLine, deltaStart, length, tokenType, tokenModifiers]
-          lastLspPos := lspPos'
-        }
+  run doc snaps : RequestM SemanticTokens := do
+    let mut leanSemanticTokens := #[]
+    for s in snaps do
+      if s.endPos <= beginPos then
+        continue
+      let syntaxBasedSemanticTokens := collectSyntaxBasedSemanticTokens s.stx
+      let infoBasedSemanticTokens := collectInfoBasedSemanticTokens s.infoTree
+      leanSemanticTokens := leanSemanticTokens ++ syntaxBasedSemanticTokens ++ infoBasedSemanticTokens
+    let absoluteLspSemanticTokens := computeAbsoluteLspSemanticTokens doc.meta.text beginPos endPos? leanSemanticTokens
+    let absoluteLspSemanticTokens := filterDuplicateSemanticTokens absoluteLspSemanticTokens
+    let semanticTokens := computeDeltaLspSemanticTokens absoluteLspSemanticTokens
+    return semanticTokens
 
+/-- Computes all semantic tokens for the document. -/
 def handleSemanticTokensFull (_ : SemanticTokensParams)
     : RequestM (RequestTask SemanticTokens) := do
   handleSemanticTokens 0 none
 
+/-- Computes the semantic tokens in the range provided by `p`. -/
 def handleSemanticTokensRange (p : SemanticTokensRangeParams)
     : RequestM (RequestTask SemanticTokens) := do
   let doc ← readDoc

src/Lean/Server/FileWorker/Utils.lean

@@ -42,9 +42,9 @@ private partial def mkCmdSnaps (initSnap : Language.Lean.InitialSnapshot) :
       mpState := headerParsed.parserState
       cmdState := headerSuccess.cmdState
     } <| .delayed <| headerSuccess.firstCmdSnap.task.bind go
-where go cmdParsed :=
-  cmdParsed.data.sigSnap.task.bind fun sig =>
-    sig.finishedSnap.task.map fun finished =>
+where
+  go cmdParsed :=
+    cmdParsed.data.finishedSnap.task.map fun finished =>
       .ok <| .cons {
         stx := cmdParsed.data.stx
         mpState := cmdParsed.data.parserState

src/Lean/Server/Snapshots.lean

@@ -58,6 +58,7 @@ def runCommandElabM (snap : Snapshot) (meta : DocumentMeta) (c : CommandElabM α
     fileName := meta.uri,
     fileMap := meta.text,
     tacticCache? := none
+    snap? := none
   }
   c.run ctx |>.run' snap.cmdState
 

src/Lean/Util/Diff.lean

@@ -0,0 +1,198 @@
+/-
+Copyright (c) 2024 Lean FRO, LLC. All rights reserved.
+Released under Apache 2.0 license as described in the file LICENSE.
+Authors: David Thrane Christiansen
+-/
+prelude
+import Init.Data
+import Lean.Data.HashMap
+import Init.Omega
+
+namespace Lean.Diff
+/--
+An action in an edit script to transform one source sequence into a target sequence.
+-/
+inductive Action where
+  /-- Insert the item into the source -/
+  | insert
+  /-- Delete the item from the source -/
+  | delete
+  /-- Leave the item in the source -/
+  | skip
+deriving Repr, BEq, Hashable, Repr
+
+instance : ToString Action where
+  toString
+    | .insert => "insert"
+    | .delete => "delete"
+    | .skip => "skip"
+
+/--
+Determines a prefix to show on a given line when printing diff results.
+
+For `delete`, the prefix is `"-"`, for `insert`, it is `"+"`, and for `skip` it is `" "`.
+-/
+def Action.linePrefix : (action : Action) → String
+  | .delete => "-"
+  | .insert => "+"
+  | .skip => " "
+
+/--
+A histogram entry consists of the number of times the element occurs in the left and right input
+arrays along with an index at which the element can be found, if applicable.
+-/
+structure Histogram.Entry (α : Type u) (lsize rsize : Nat) where
+  /-- How many times the element occurs in the left array -/
+  leftCount : Nat
+  /-- An index of the element in the left array, if applicable -/
+  leftIndex : Option (Fin lsize)
+  /-- Invariant: the count is non-zero iff there is a saved index -/
+  leftWF : leftCount = 0 ↔ leftIndex = none
+  /-- How many times the element occurs in the right array -/
+  rightCount : Nat
+  /-- An index of the element in the right array, if applicable -/
+  rightIndex : Option (Fin rsize)
+  /-- Invariant: the count is non-zero iff there is a saved index -/
+  rightWF : rightCount = 0 ↔ rightIndex = none
+
+/-- A histogram for arrays maps each element to a count and, if applicable, an index.-/
+def Histogram (α : Type u) (lsize rsize : Nat) [BEq α] [Hashable α] :=
+  Lean.HashMap α (Histogram.Entry α lsize rsize)
+
+
+section
+
+variable [BEq α] [Hashable α]
+
+/-- Add an element from the left array to a histogram -/
+def Histogram.addLeft (histogram : Histogram α lsize rsize) (index : Fin lsize) (val : α)
+    : Histogram α lsize rsize :=
+  match histogram.find? val with
+  | none => histogram.insert val {
+      leftCount := 1, leftIndex := some index,
+      leftWF := by simp,
+      rightCount := 0, rightIndex := none
+      rightWF := by simp
+    }
+  | some x => histogram.insert val {x with
+      leftCount := x.leftCount + 1, leftIndex := some index, leftWF := by simp
+    }
+
+/-- Add an element from the right array to a histogram -/
+def Histogram.addRight (histogram : Histogram α lsize rsize) (index : Fin rsize) (val : α)
+    : Histogram α lsize rsize :=
+  match histogram.find? val with
+  | none => histogram.insert val {
+      leftCount := 0, leftIndex := none,
+      leftWF := by simp,
+      rightCount := 1, rightIndex := some index,
+      rightWF := by simp
+    }
+  | some x => histogram.insert val {x with
+      rightCount := x.leftCount + 1, rightIndex := some index,
+      rightWF := by simp
+    }
+
+/-- Given two `Subarray`s, find their common prefix and return their differing suffixes -/
+def matchPrefix (left right : Subarray α) : Array α × Subarray α × Subarray α :=
+  let rec go (pref : Array α) : Array α × Subarray α × Subarray α :=
+    let i := pref.size
+    if _ : i < left.size ∧ i < right.size then
+      if left[i]'(by omega) == right[i]'(by omega) then
+        go <| pref.push <| left[i]'(by omega)
+      else (pref, left.drop pref.size, right.drop pref.size)
+    else (pref, left.drop pref.size, right.drop pref.size)
+  termination_by left.size - pref.size
+  go #[]
+
+
+/-- Given two `Subarray`s, find their common suffix and return their differing prefixes -/
+def matchSuffix (left right : Subarray α) : Subarray α × Subarray α × Array α :=
+  let rec go (i : Nat) : Subarray α × Subarray α × Array α :=
+    if _ : i < left.size ∧ i < right.size then
+      if left[left.size - i - 1]'(by omega) == right[right.size - i - 1]'(by omega) then
+        go i.succ
+      else
+        (left.take (left.size - i), right.take (right.size - i), (left.drop (left.size - i)).toArray)
+    else
+      (left.take (left.size - i), right.take (right.size - i), (left.drop (left.size - i)).toArray)
+    termination_by left.size - i
+  go 0
+
+/--
+Finds the least common subsequence of two arrays using a variant of jgit's histogram diff algorithm.
+
+Unlike jgit's implementation, this one does not perform a cutoff on histogram bucket sizes, nor does
+it fall back to the Myers diff algorithm. This means that it has quadratic worst-case complexity.
+Empirically, however, even quadratic cases of this implementation can handle hundreds of megabytes
+in a second or so, and it is intended to be used for short strings like error messages. Be
+cautious when applying it to larger workloads.
+-/
+partial def lcs (left right : Subarray α) : Array α := Id.run do
+  let (pref, left, right) := matchPrefix left right
+  let (left, right, suff) := matchSuffix left right
+  let mut hist : Histogram α left.size right.size := .empty
+  for h : i in [0:left.size] do
+    hist := hist.addLeft ⟨i, Membership.get_elem_helper h rfl⟩ left[i]
+  for h : i in [0:right.size] do
+    hist := hist.addRight ⟨i, Membership.get_elem_helper h rfl⟩ right[i]
+  let mut best := none
+  for (k, v) in hist.toList do
+    if let {leftCount := lc, leftIndex := some li, rightCount := rc, rightIndex := some ri, ..} := v then
+      match best with
+      | none =>
+        best := some ((lc + rc), k, li, ri)
+      | some (count, _) =>
+        if lc + rc < count then
+          best := some ((lc + rc), k, li, ri)
+  let some (_, v, li, ri) := best
+    | return pref ++ suff
+
+  let lefts := left.split ⟨li.val, by cases li; simp_arith; omega⟩
+  let rights := right.split ⟨ri.val, by cases ri; simp_arith; omega⟩
+
+  pref ++ lcs lefts.1 rights.1 ++ #[v] ++ lcs (lefts.2.drop 1) (rights.2.drop 1) ++ suff
+
+/--
+Computes an edit script to transform `left` into `right`.
+-/
+def diff [Inhabited α] (original edited : Array α) : Array (Action × α) :=
+  if h : ¬(0 < original.size) then
+    edited.map (.insert, ·)
+  else if h' : ¬(0 < edited.size) then
+    original.map (.delete, ·)
+  else Id.run do
+    have : original.size > 0 := by omega
+    have : edited.size > 0 := by omega
+    let mut out := #[]
+    let ds := lcs original.toSubarray edited.toSubarray
+    let mut i := 0
+    let mut j := 0
+    for d in ds do
+      while i < original.size && original[i]! != d do
+        out := out.push <| (.delete, original[i]!)
+        i := i.succ
+      while j < edited.size && edited[j]! != d do
+        out := out.push <| (.insert, edited[j]!)
+        j := j.succ
+      out := out.push <| (.skip, d)
+      i := i.succ
+      j := j.succ
+    while h : i < original.size do
+      out := out.push <| (.delete, original[i])
+      i := i.succ
+    while h : j < edited.size do
+      out := out.push <| (.insert, edited[j])
+      j := j.succ
+    out
+
+/-- Shows a line-by-line edit script with markers for added and removed lines. -/
+def linesToString [ToString α] (lines : Array (Action × α)) : String := Id.run do
+  let mut out : String := ""
+  for (act, line) in lines do
+    let lineStr := toString line
+    if lineStr == "" then
+      out := out ++ s!"{act.linePrefix}\n"
+    else
+      out := out ++ s!"{act.linePrefix} {lineStr}\n"
+  out

src/Lean/Util/Profiler.lean

@@ -0,0 +1,322 @@
+/-
+Copyright (c) 2024 Lean FRO, LLC. All rights reserved.
+Released under Apache 2.0 license as described in the file LICENSE.
+Authors: Sebastian Ullrich
+-/
+prelude
+import Lean.Util.Trace
+
+/-! `trace.profiler.output` Firefox Profiler integration -/
+
+namespace Lean.Firefox
+
+/-! Definitions from https://github.com/firefox-devtools/profiler/blob/main/src/types/profile.js -/
+
+abbrev Milliseconds := Float
+
+structure Category where
+  name : String
+  color : String
+  subcategories : Array String := #[]
+deriving FromJson, ToJson
+
+structure ProfileMeta where
+  interval : Milliseconds := 0  -- should be irrelevant with `tracing-ms`
+  startTime : Milliseconds
+  categories : Array Category := #[]
+  processType : Nat := 0
+  product : String := "lean"
+  preprocessedProfileVersion : Nat := 48
+  markerSchema : Array Json := #[]
+deriving FromJson, ToJson
+
+structure StackTable where
+  frame : Array Nat
+  «prefix» : Array (Option Nat)
+  category : Array Nat
+  subcategory : Array Nat
+  length : Nat
+deriving FromJson, ToJson
+
+structure SamplesTable where
+  stack : Array Nat
+  time : Array Milliseconds
+  weight : Array Milliseconds
+  weightType : String := "tracing-ms"
+  length : Nat
+deriving FromJson, ToJson
+
+structure FuncTable where
+  name : Array Nat
+  isJS : Array Json := #[]
+  relevantForJS : Array Json := #[]
+  resource : Array Int
+  fileName : Array (Option Nat)
+  lineNumber : Array (Option Nat)
+  columnNumber : Array (Option Nat)
+  length : Nat
+deriving FromJson, ToJson
+
+structure FrameTable where
+  func : Array Nat
+  inlineDepth : Array Json := #[]
+  innerWindowID : Array Json := #[]
+  length : Nat
+deriving FromJson, ToJson
+
+structure RawMarkerTable where
+  data : Array Json := #[]
+  name : Array Json := #[]
+  length : Nat := 0
+deriving FromJson, ToJson
+
+structure ResourceTable where
+  type : Array Json := #[]
+  length : Nat := 0
+deriving FromJson, ToJson
+
+structure Thread where
+  name : String
+  processType : String := "default"
+  isMainThread : Bool := true
+  samples : SamplesTable
+  markers: RawMarkerTable := {}
+  stackTable : StackTable
+  frameTable : FrameTable
+  resourceTable : ResourceTable := {}
+  stringArray : Array String
+  funcTable : FuncTable
+deriving FromJson, ToJson
+
+structure Profile where
+  meta : ProfileMeta
+  libs : Array Json := #[]
+  threads : Array Thread
+deriving FromJson, ToJson
+
+/-- Thread with maps necessary for computing max sharing indices -/
+structure ThreadWithMaps extends Thread where
+  stringMap : HashMap String Nat := {}
+  funcMap : HashMap Nat Nat := {}
+  stackMap : HashMap (Nat × Option Nat) Nat := {}
+  /-- Last timestamp encountered: stop time of preceding sibling, or else start time of parent.  -/
+  lastTime : Float := 0
+
+-- TODO: add others, dynamically?
+def categories : Array Category := #[
+  { name := "Other", color := "gray" },
+  { name := "Elab", color := "red" },
+  { name := "Meta", color := "yellow" }
+]
+
+private partial def addTrace (pp : Bool) (thread : ThreadWithMaps) (trace : MessageData) :
+    IO ThreadWithMaps :=
+  (·.2) <$> StateT.run (go none trace) thread
+where
+  go parentStackIdx? : _ → StateT ThreadWithMaps IO Unit
+    | .trace data msg children => do
+      if data.startTime == 0 then
+        return  -- no time data, skip
+      let mut funcName := data.cls.toString
+      if !data.tag.isEmpty then
+        funcName := s!"{funcName}: {data.tag}"
+      if pp then
+        funcName := s!"{funcName}: {← msg.format}"
+      let strIdx ← modifyGet fun thread =>
+        if let some idx := thread.stringMap.find? funcName then
+          (idx, thread)
+        else
+          (thread.stringMap.size, { thread with
+            stringArray := thread.stringArray.push funcName
+            stringMap := thread.stringMap.insert funcName thread.stringMap.size })
+      let category := categories.findIdx? (·.name == data.cls.getRoot.toString) |>.getD 0
+      let funcIdx ← modifyGet fun thread =>
+        if let some idx := thread.funcMap.find? strIdx then
+          (idx, thread)
+        else
+          (thread.funcMap.size, { thread with
+            funcTable := {
+              name := thread.funcTable.name.push strIdx
+              resource := thread.funcTable.resource.push (-1)
+              -- the following fields could be inferred from `Syntax` in the message
+              fileName := thread.funcTable.fileName.push none
+              lineNumber := thread.funcTable.lineNumber.push none
+              columnNumber := thread.funcTable.columnNumber.push none
+              length := thread.funcTable.length + 1
+            }
+            frameTable := {
+              func := thread.frameTable.func.push thread.funcMap.size
+              length := thread.frameTable.length + 1
+            }
+            funcMap := thread.funcMap.insert strIdx thread.funcMap.size })
+      let frameIdx := funcIdx
+      let stackIdx ← modifyGet fun thread =>
+        if let some idx := thread.stackMap.find? (frameIdx, parentStackIdx?) then
+          (idx, thread)
+        else
+          (thread.stackMap.size, { thread with
+            stackTable := {
+              frame := thread.stackTable.frame.push frameIdx
+              «prefix» := thread.stackTable.prefix.push parentStackIdx?
+              category := thread.stackTable.category.push category
+              subcategory := thread.stackTable.subcategory.push 0
+              length := thread.stackTable.length + 1
+            }
+            stackMap := thread.stackMap.insert (frameIdx, parentStackIdx?) thread.stackMap.size })
+      modify fun thread => { thread with lastTime := data.startTime }
+      for c in children do
+        if let some nextStart := getNextStart? c then
+          -- add run time slice between children/before first child
+          modify fun thread => { thread with samples := {
+            stack := thread.samples.stack.push stackIdx
+            time := thread.samples.time.push (thread.lastTime * 1000)
+            weight := thread.samples.weight.push ((nextStart - thread.lastTime) * 1000)
+            length := thread.samples.length + 1
+          } }
+          go (some stackIdx) c
+      -- add remaining slice after last child
+      modify fun thread => { thread with
+        lastTime := data.stopTime
+        samples := {
+          stack := thread.samples.stack.push stackIdx
+          time := thread.samples.time.push (thread.lastTime * 1000)
+          weight := thread.samples.weight.push ((data.stopTime - thread.lastTime) * 1000)
+          length := thread.samples.length + 1
+        } }
+    | .withContext _ msg => go parentStackIdx? msg
+    | _ => return
+  /-- Returns first `startTime` in the trace tree, if any. -/
+  getNextStart?
+    | .trace data _ children => do
+      if data.startTime != 0 then
+        return data.startTime
+      if let some startTime := children.findSome? getNextStart? then
+        return startTime
+      none
+    | .withContext _ msg => getNextStart? msg
+    | _ => none
+
+def Thread.new (name : String) : Thread := {
+  name
+  samples := { stack := #[], time := #[], weight := #[], length := 0 }
+  stackTable := { frame := #[], «prefix» := #[], category := #[], subcategory := #[], length := 0 }
+  frameTable := { func := #[], length := 0 }
+  stringArray := #[]
+  funcTable := {
+    name := #[], resource := #[], fileName := #[], lineNumber := #[], columnNumber := #[],
+    length := 0 }
+}
+
+def Profile.export (name : String) (startTime : Milliseconds) (traceState : TraceState)
+    (opts : Options) : IO Profile := do
+  let thread := Thread.new name
+  -- wrap entire trace up to current time in `runFrontend` node
+  let trace := .trace {
+    cls := `runFrontend, startTime, stopTime := (← IO.monoNanosNow).toFloat / 1000000000,
+    collapsed := true } "" (traceState.traces.toArray.map (·.msg))
+  let thread ← addTrace (Lean.trace.profiler.output.pp.get opts) { thread with } trace
+  return {
+    meta := { startTime, categories }
+    threads := #[thread.toThread]
+  }
+
+structure ThreadWithCollideMaps extends ThreadWithMaps where
+  /-- Max sharing map for samples -/
+  sampleMap : HashMap Nat Nat := {}
+
+/--
+Adds samples from `add` to `thread`, increasing the weight of existing samples with identical stacks
+instead of pushing new samples.
+-/
+private partial def collideThreads (thread : ThreadWithCollideMaps) (add : Thread) :
+    ThreadWithCollideMaps :=
+  StateT.run collideSamples thread |>.2
+where
+  collideSamples : StateM ThreadWithCollideMaps Unit := do
+    for oldSampleIdx in [0:add.samples.length] do
+      let oldStackIdx := add.samples.stack[oldSampleIdx]!
+      let stackIdx ← collideStacks oldStackIdx
+      modify fun thread =>
+        if let some idx := thread.sampleMap.find? stackIdx then
+          -- imperative to preserve linear use of arrays here!
+          let ⟨⟨⟨t1, t2, t3, samples, t5, t6, t7, t8, t9, t10⟩, o2, o3, o4, o5⟩, o6⟩ := thread
+          let ⟨s1, s2, weight, s3, s4⟩ := samples
+          let weight := weight.set! idx <| weight[idx]! + add.samples.weight[oldSampleIdx]!
+          let samples := ⟨s1, s2, weight, s3, s4⟩
+          ⟨⟨⟨t1, t2, t3, samples, t5, t6, t7, t8, t9, t10⟩, o2, o3, o4, o5⟩, o6⟩
+        else
+          -- imperative to preserve linear use of arrays here!
+          let ⟨⟨⟨t1, t2, t3, samples, t5, t6, t7, t8, t9, t10⟩, o2, o3, o4, o5⟩, sampleMap⟩ :=
+            thread
+          let ⟨stack, time, weight, _, length⟩ := samples
+          let samples := {
+              stack := stack.push stackIdx
+              time := time.push time.size.toFloat
+              weight := weight.push add.samples.weight[oldSampleIdx]!
+              length := length + 1
+            }
+          let sampleMap := sampleMap.insert stackIdx sampleMap.size
+          ⟨⟨⟨t1, t2, t3, samples, t5, t6, t7, t8, t9, t10⟩, o2, o3, o4, o5⟩, sampleMap⟩
+  collideStacks oldStackIdx : StateM ThreadWithCollideMaps Nat := do
+    let oldParentStackIdx? := add.stackTable.prefix[oldStackIdx]!
+    let parentStackIdx? ← oldParentStackIdx?.mapM (collideStacks ·)
+    let oldFrameIdx := add.stackTable.frame[oldStackIdx]!
+    let oldFuncIdx := add.frameTable.func[oldFrameIdx]!
+    let oldStrIdx := add.funcTable.name[oldFuncIdx]!
+    let strIdx ← getStrIdx add.stringArray[oldStrIdx]!
+    let funcIdx ← modifyGet fun thread =>
+      if let some idx := thread.funcMap.find? strIdx then
+        (idx, thread)
+      else
+        (thread.funcMap.size, { thread with
+          funcTable := {
+            name := thread.funcTable.name.push strIdx
+            resource := thread.funcTable.resource.push (-1)
+            fileName := thread.funcTable.fileName.push none
+            lineNumber := thread.funcTable.lineNumber.push none
+            columnNumber := thread.funcTable.columnNumber.push none
+            length := thread.funcTable.length + 1
+          }
+          frameTable := {
+            func := thread.frameTable.func.push thread.funcMap.size
+            length := thread.frameTable.length + 1
+          }
+          funcMap := thread.funcMap.insert strIdx thread.funcMap.size })
+    let frameIdx := funcIdx
+    modifyGet fun thread =>
+      if let some idx := thread.stackMap.find? (frameIdx, parentStackIdx?) then
+        (idx, thread)
+      else
+        (thread.stackMap.size,
+          let ⟨⟨⟨t1,t2, t3, t4, t5, stackTable, t7, t8, t9, t10⟩, o2, o3, stackMap, o5⟩, o6⟩ :=
+            thread
+          let { frame, «prefix», category, subcategory, length } := stackTable
+          let stackTable := {
+            frame := frame.push frameIdx
+            «prefix» := prefix.push parentStackIdx?
+            category := category.push add.stackTable.category[oldStackIdx]!
+            subcategory := subcategory.push add.stackTable.subcategory[oldStackIdx]!
+            length := length + 1
+          }
+          let stackMap := stackMap.insert (frameIdx, parentStackIdx?) stackMap.size
+          ⟨⟨⟨t1,t2, t3, t4, t5, stackTable, t7, t8, t9, t10⟩, o2, o3, stackMap, o5⟩, o6⟩)
+  getStrIdx (s : String) :=
+    modifyGet fun thread =>
+      if let some idx := thread.stringMap.find? s then
+        (idx, thread)
+      else
+        (thread.stringMap.size, { thread with
+          stringArray := thread.stringArray.push s
+          stringMap := thread.stringMap.insert s thread.stringMap.size })
+
+/--
+Merges given profiles such that samples with identical stacks are deduplicated by adding up their
+weights. Minimizes profile size while preserving per-stack timing information.
+-/
+def Profile.collide (ps : Array Profile) : Option Profile := do
+  let base ← ps[0]?
+  let thread := Thread.new "collided"
+  let thread := ps.map (·.threads) |>.flatten.foldl collideThreads { thread with }
+  return { base with threads := #[thread.toThread] }
+
+end Lean.Firefox

src/Lean/Util/Trace.lean

@@ -129,7 +129,7 @@ def addRawTrace (msg : MessageData) : m Unit := do
 def addTrace (cls : Name) (msg : MessageData) : m Unit := do
   let ref ← getRef
   let msg ← addMessageContext msg
-  modifyTraces (·.push { ref, msg := .trace (collapsed := false) cls msg #[] })
+  modifyTraces (·.push { ref, msg := .trace { collapsed := false, cls } msg #[] })
 
 @[inline] def trace (cls : Name) (msg : Unit → MessageData) : m Unit := do
   if (← isTracingEnabledFor cls) then
@@ -141,18 +141,18 @@ def addTrace (cls : Name) (msg : MessageData) : m Unit := do
     addTrace cls msg
 
 private def addTraceNode (oldTraces : PersistentArray TraceElem)
-    (cls : Name) (ref : Syntax) (msg : MessageData) (collapsed : Bool) : m Unit :=
+    (data : TraceData) (ref : Syntax) (msg : MessageData) : m Unit :=
   withRef ref do
-  let msg := .trace cls msg ((← getTraces).toArray.map (·.msg)) collapsed
+  let msg := .trace data msg ((← getTraces).toArray.map (·.msg))
   let msg ← addMessageContext msg
   modifyTraces fun _ =>
     oldTraces.push { ref, msg }
 
-def withSeconds [Monad m] [MonadLiftT BaseIO m] (act : m α) : m (α × Float) := do
+def withStartStopSeconds [Monad m] [MonadLiftT BaseIO m] (act : m α) : m (α × Float × Float) := do
   let start ← IO.monoNanosNow
   let a ← act
   let stop ← IO.monoNanosNow
-  return (a, (stop - start).toFloat / 1000000000)
+  return (a, start.toFloat / 1000000000, stop.toFloat / 1000000000)
 
 register_builtin_option trace.profiler : Bool := {
   defValue := false
@@ -166,6 +166,20 @@ register_builtin_option trace.profiler.threshold : Nat := {
   descr    := "threshold in milliseconds, traces below threshold will not be activated"
 }
 
+register_builtin_option trace.profiler.output : String := {
+  defValue := ""
+  group    := "profiler"
+  descr    :=
+    "output `trace.profiler` data in Firefox Profiler-compatible format to given file path"
+}
+
+register_builtin_option trace.profiler.output.pp : Bool := {
+  defValue := false
+  group    := "profiler"
+  descr    :=
+    "if false, limit text in exported trace nodes to trace class name and `TraceData.tag`, if any"
+}
+
 def trace.profiler.threshold.getSecs (o : Options) : Float :=
   (trace.profiler.threshold.get o).toFloat / 1000
 
@@ -208,31 +222,32 @@ instance [always : MonadAlwaysExcept ε m] [STWorld ω m] [BEq α] [Hashable α]
   except := let _ := always.except; inferInstance
 
 def withTraceNode [always : MonadAlwaysExcept ε m] [MonadLiftT BaseIO m] (cls : Name)
-    (msg : Except ε α → m MessageData) (k : m α) (collapsed := true) : m α := do
+    (msg : Except ε α → m MessageData) (k : m α) (collapsed := true) (tag := "") : m α := do
   let _ := always.except
   let opts ← getOptions
   let clsEnabled ← isTracingEnabledFor cls
   unless clsEnabled || trace.profiler.get opts do
     return (← k)
   let oldTraces ← getResetTraces
-  let (res, secs) ← withSeconds <| observing k
-  let aboveThresh := trace.profiler.get opts && secs > trace.profiler.threshold.getSecs opts
+  let (res, start, stop) ← withStartStopSeconds <| observing k
+  let aboveThresh := trace.profiler.get opts && stop - start > trace.profiler.threshold.getSecs opts
   unless clsEnabled || aboveThresh do
     modifyTraces (oldTraces ++ ·)
     return (← MonadExcept.ofExcept res)
   let ref ← getRef
   let mut m ← try msg res catch _ => pure m!"<exception thrown while producing trace node message>"
+  let mut data := { cls, collapsed, tag }
   if profiler.get opts || aboveThresh then
-    m := m!"[{secs}s] {m}"
-  addTraceNode oldTraces cls ref m collapsed
+    data := { data with startTime := start, stopTime := stop }
+  addTraceNode oldTraces data ref m
   MonadExcept.ofExcept res
 
 def withTraceNode' [MonadAlwaysExcept Exception m] [MonadLiftT BaseIO m] (cls : Name)
-    (k : m (α × MessageData)) (collapsed := true) : m α :=
+    (k : m (α × MessageData)) (collapsed := true) (tag := "") : m α :=
   let msg := fun
     | .ok (_, msg) => return msg
     | .error err => return err.toMessageData
-  Prod.fst <$> withTraceNode cls msg k collapsed
+  Prod.fst <$> withTraceNode cls msg k collapsed tag
 
 end
 
@@ -300,7 +315,7 @@ TODO: find better name for this function.
 -/
 def withTraceNodeBefore [MonadRef m] [AddMessageContext m] [MonadOptions m]
     [always : MonadAlwaysExcept ε m] [MonadLiftT BaseIO m] [ExceptToEmoji ε α] (cls : Name)
-    (msg : m MessageData) (k : m α) (collapsed := true) : m α := do
+    (msg : m MessageData) (k : m α) (collapsed := true) (tag := "") : m α := do
   let _ := always.except
   let opts ← getOptions
   let clsEnabled ← isTracingEnabledFor cls
@@ -310,15 +325,16 @@ def withTraceNodeBefore [MonadRef m] [AddMessageContext m] [MonadOptions m]
   let ref ← getRef
   -- make sure to preserve context *before* running `k`
   let msg ← withRef ref do addMessageContext (← msg)
-  let (res, secs) ← withSeconds <| observing k
-  let aboveThresh := trace.profiler.get opts && secs > trace.profiler.threshold.getSecs opts
+  let (res, start, stop) ← withStartStopSeconds <| observing k
+  let aboveThresh := trace.profiler.get opts && stop - start > trace.profiler.threshold.getSecs opts
   unless clsEnabled || aboveThresh do
     modifyTraces (oldTraces ++ ·)
     return (← MonadExcept.ofExcept res)
   let mut msg := m!"{ExceptToEmoji.toEmoji res} {msg}"
+  let mut data := { cls, collapsed, tag }
   if profiler.get opts || aboveThresh then
-    msg := m!"[{secs}s] {msg}"
-  addTraceNode oldTraces cls ref msg collapsed
+    data := { data with startTime := start, stopTime := stop }
+  addTraceNode oldTraces data ref msg
   MonadExcept.ofExcept res
 
 end Lean

src/Lean/Widget/InteractiveDiagnostic.lean

@@ -143,10 +143,10 @@ where
   | ctx,       nest n d                 => Format.nest n <$> go nCtx ctx d
   | ctx,       compose d₁ d₂            => do let d₁ ← go nCtx ctx d₁; let d₂ ← go nCtx ctx d₂; pure $ d₁ ++ d₂
   | ctx,       group d                  => Format.group <$> go nCtx ctx d
-  | ctx,       .trace cls header children collapsed => do
+  | ctx,       .trace data header children => do
     let header := (← go nCtx ctx header).nest 4
     let nodes ←
-      if collapsed && !children.isEmpty then
+      if data.collapsed && !children.isEmpty then
         let children := children.map fun child =>
           MessageData.withNamingContext nCtx <|
             match ctx with
@@ -154,11 +154,11 @@ where
             | none     => child
         let blockSize := ctx.bind (infoview.maxTraceChildren.get? ·.opts)
           |>.getD infoview.maxTraceChildren.defValue
-        let children := chopUpChildren cls blockSize children.toSubarray
+        let children := chopUpChildren data.cls blockSize children.toSubarray
         pure (.lazy children)
       else
         pure (.strict (← children.mapM (go nCtx ctx)))
-    let e := .trace cls header collapsed nodes
+    let e := .trace data.cls header data.collapsed nodes
     return .tag (← pushEmbed e) ".\n"
 
   /-- Recursively moves child nodes after the first `blockSize` into a new "more" node. -/
@@ -167,7 +167,7 @@ where
     if children.size > blockSize + 1 then  -- + 1 to make idempotent
       let more := chopUpChildren cls blockSize children[blockSize:]
       children[:blockSize].toArray.push <|
-        .trace (collapsed := true) cls
+        .trace { collapsed := true, cls }
           f!"{children.size - blockSize} more entries..." more
     else children
 

src/include/lean/lean.h

@@ -1044,6 +1044,7 @@ LEAN_EXPORT bool lean_string_lt(b_lean_obj_arg s1, b_lean_obj_arg s2);
 static inline uint8_t lean_string_dec_eq(b_lean_obj_arg s1, b_lean_obj_arg s2) { return lean_string_eq(s1, s2); }
 static inline uint8_t lean_string_dec_lt(b_lean_obj_arg s1, b_lean_obj_arg s2) { return lean_string_lt(s1, s2); }
 LEAN_EXPORT uint64_t lean_string_hash(b_lean_obj_arg);
+LEAN_EXPORT lean_obj_res lean_string_of_usize(size_t);
 
 /* Thunks */
 

src/runtime/io.cpp

@@ -302,11 +302,7 @@ extern "C" LEAN_EXPORT obj_res lean_io_prim_handle_mk(b_obj_arg filename, uint8
 #ifdef LEAN_WINDOWS
 
 static inline HANDLE win_handle(FILE * fp) {
-#ifdef q4_WCE
-    return (HANDLE)_fileno(fp);
-#else
     return (HANDLE)_get_osfhandle(_fileno(fp));
-#endif
 }
 
 /* Handle.lock : (@& Handle) → (exclusive : Bool) → IO Unit */
@@ -391,13 +387,41 @@ extern "C" LEAN_EXPORT obj_res lean_io_prim_handle_unlock(b_obj_arg h, obj_arg /
 
 #endif
 
+/* Handle.isTty : (@& Handle) → BaseIO Bool */
+extern "C" LEAN_EXPORT obj_res lean_io_prim_handle_is_tty(b_obj_arg h, obj_arg /* w */) {
+    FILE * fp = io_get_handle(h);
+#ifdef LEAN_WINDOWS
+    /*
+    On Windows, there are two approaches for detecting a console.
+    1)  _isatty(_fileno(fp)) != 0
+        This checks whether the file descriptor is a *character device*,
+        not just a terminal (unlike Unix's isatty). Thus, it produces a false
+        positive in some edge cases (such as NUL).
+        https://stackoverflow.com/q/3648711
+    2)  GetConsoleMode(win_handle(fp), &mode) != 0
+        Errors if the handle is not a console. Unfortunately, this produces
+        a false negative for a terminal emulator like MSYS/Cygwin's Mintty,
+        which is not implemented as a Windows-recognized console on
+        old Windows versions (e.g., pre-Windows 10, pre-ConPTY).
+        https://github.com/msys2/MINGW-packages/issues/14087
+    We choose to use GetConsoleMode as that seems like the more modern approach,
+    and Lean does not support pre-Windows 10.
+    */
+    DWORD mode;
+    return io_result_mk_ok(box(GetConsoleMode(win_handle(fp), &mode) != 0));
+#else
+    // We ignore errors for consistency with Windows.
+    return io_result_mk_ok(box(isatty(fileno(fp))));
+#endif
+}
+
 /* Handle.isEof : (@& Handle) → BaseIO Bool */
 extern "C" LEAN_EXPORT obj_res lean_io_prim_handle_is_eof(b_obj_arg h, obj_arg /* w */) {
     FILE * fp = io_get_handle(h);
     return io_result_mk_ok(box(std::feof(fp) != 0));
 }
 
-/* Handle.flush : (@& Handle) → IO Bool */
+/* Handle.flush : (@& Handle) → IO Unit */
 extern "C" LEAN_EXPORT obj_res lean_io_prim_handle_flush(b_obj_arg h, obj_arg /* w */) {
     FILE * fp = io_get_handle(h);
     if (!std::fflush(fp)) {

src/runtime/object.cpp

@@ -1629,6 +1629,10 @@ object * mk_string(std::string const & s) {
     return lean_mk_string_from_bytes(s.data(), s.size());
 }
 
+object * mk_ascii_string(std::string const & s) {
+    return lean_mk_string_core(s.data(), s.size(), s.size());
+}
+
 std::string string_to_std(b_obj_arg o) {
     lean_assert(string_size(o) > 0);
     return std::string(w_string_cstr(o), lean_string_size(o) - 1);
@@ -1999,6 +2003,10 @@ extern "C" LEAN_EXPORT uint64 lean_string_hash(b_obj_arg s) {
     return hash_str(sz, (unsigned char const *) str, 11);
 }
 
+extern "C" LEAN_EXPORT obj_res lean_string_of_usize(size_t n) {
+    return mk_ascii_string(std::to_string(n));
+}
+
 // =======================================
 // ByteArray & FloatArray