perf: bound expression comparisons in the type inference cache (#16046)

This PR fixes quadratic elaboration behavior for large string-literal
equalities such as `theorem t : s = String.ofList l := rfl`.

The type inference cache uses structural expression equality. When a
lookup encounters a separately allocated copy of a cached expression,
matching hashes are followed by a traversal to establish equality. For
large expressions, this traversal can cost substantially more than
computing the type. Repeated comparisons of growing intermediate
expressions accumulate quadratic work. Matchers and string-literal
conversion expose the problem, but the underlying issue is structural
equality during cache lookup.

Introduce budgeted expression comparisons returning equal, unequal, or
exhausted, and a persistent cache storing one candidate per full hash.
Locate candidates without structural expression comparison, then
validate them using budgeted equality. On exhaustion, evict the
candidate and return a cache miss, allowing type inference to compute
and cache the result. This preserves inexpensive structural cache hits
while avoiding repeated large traversals.

Use budget 64 for the `MetaM` type inference cache. Retain the existing
WHNF, definitional-equality, unit-like, and kernel caches. The
comparison follows the existing recursive equality implementation and
accounts for string and metadata payloads; names, universe levels, and
natural-number literals retain ordinary equality. Pointer sharing can
affect whether a comparison exhausts its budget, so the operation breaks
referential transparency and is exposed through `BaseIO`.

The following measurements count user-mode instructions for the complete
Lean invocation, including declaration generation, elaboration,
attribute validation, and kernel checking. Before and after use
identical inputs and matching recursion limits, with one Lean worker
pinned to the same CPU. The recursion limit is 100,000 at the two
smaller sizes and 1,000,000 at the two larger sizes.

For `:= rfl`:

| String length | Before | After |
|---:|---:|---:|
| 8,192 | 60,047,586,140 | 45,086,604,920 |
| 16,384 | 149,553,658,274 | 88,574,754,680 |
| 32,768 | 422,108,821,130 | 176,832,509,126 |
| 65,536 | 1,341,360,340,506 | 355,894,892,690 |

For `:= (rfl)`:

| String length | Before | After |
|---:|---:|---:|
| 8,192 | 35,435,242,280 | 20,452,849,927 |
| 16,384 | 99,980,150,815 | 38,982,426,197 |
| 32,768 | 321,950,232,826 | 76,311,678,593 |
| 65,536 | 1,138,411,788,117 | 152,127,218,091 |

At 65,536 characters, the change reduces instructions for bare `rfl` by
73.5%. Doubling from 32,768 increases instructions 3.18× before and
2.01× after. The removed work grows 4.02× on that doubling, consistent
with eliminating the quadratic component over the measured range.

Bare `:= rfl` and parenthesized `:= (rfl)` share the same ordinary
term-elaboration path: infer `rfl`'s implicit arguments using the
expected type, then check the resulting proof's type against that
expected type again. Bare `:= rfl` additionally triggers automatic
`@[defeq]` inference. Its validator performs another equality check with
fresh caches and smart unfolding disabled. Parentheses suppress this
automatic attribute. The tactic form `:= by rfl` performs one
substantive equality check and constructs an `Eq.refl` proof; it also
avoids the automatic attribute.

Parentheses alone leave the original cache problem largely intact. The
additional attribute-validation cost remains approximately unchanged:
202.9 billion instructions before and 203.8 billion after at 65,536
characters. This PR preserves the existing elaboration and
attribute-validation behavior while removing the observed quadratic
cache overhead.

A complete Mathlib build passes all 8,662 modules, using
96,577,405,692,077 instructions, compared with 96,446,853,181,169
before: +0.135% in one run per configuration. All reported instruction
counters have 100% coverage. Regression tests cover budget exhaustion,
pointer sharing, binder-sensitive and binder-insensitive equality,
metadata payloads, hash collisions, persistent cache snapshots, and
scaling with and without matchers.

AI assistance: Codex.

Closes #15985
14 files changed