These release notes describe a release candidate, not the final release. They may be incomplete and are subject to change.
Lean 4.37.0-rc1 (2026-11-18)
For this release, 370 changes landed. In addition to the 71 feature additions and 159 fixes listed below, there were 7 refactoring changes, 1 documentation improvement, 108 performance improvements, 4 improvements to the test suite, and 20 other changes.
Language
#16533 changes
registerReservedNamePredicateto take two functions: a test on the last component of the name, and the predicate itself. A name is a candidate for being reserved only if its last component passes the test.#16531 fixes an "environment already contains" import error when two modules realize the same
matchcongruence equation.#16512 fixes a bug wherein loose bvars where not always checked for in inductive declarations. This issue looks benign, and does not lead to an apparent proof of false.
#16519 makes the generation of
matchequations faster for amatchwith many alternatives and a catch-all. Thebig_match_stringbenchmark with 128 alternatives is about 14% faster (#16313).#16505 makes each congruence equation
f.match_1.congr_eq_iof amatchbe generated on demand, independently of the other ones. It fixes a performance regression from #16502 for amatchwith many alternatives where only a few match equations are not proved byrfl, for example literals or constructors followed by a catch-all:big_match_nat_splitandbig_match_partialare 18% and 7% faster. Referring tof.match_1.congr_eq_iby name also generates only that theorem.#16503 makes the kernel type check a constant created by a nested realization only once. For example, the equation theorems of a function request the equations of its
match, and the kernel checked each of those theorems twice, or three times when they requested further theorems themselves. Generating the equations of aString → Natfunction with 128 literal alternatives is about 25% faster. It also fixes repeated error messages: a kernel error in such a constant was reported once per nesting level, and is now reported once.#16501 adds the option
shiftLeft.threshold(default: 65536).whnf,simp, andgrindno longer evaluate a left shift of literals when the shift amount is above this threshold, and report a warning instead, as they already do for exponents aboveexponentiation.threshold. Previously, a shift amount of 2^32 or more aborted the Lean process withINTERNAL PANIC: Nat.shiftl exponent is too big, e.g., inexample : (1 <<< 4294967296 : Nat) = 0 := by simp.cbvand the compiler use the same bound as a constant.#16404 makes the
doelaborator reject afinallyblock that reassigns amutvariable in scope at thetry. The error names the reassigned variables:A `finally` block cannot reassign the `mut` variable `s`.
#16482 turns the
csimpCoretest, which checks that declarations replaced bycsimparenoncomputable, into a linter.#16480 makes equation theorems of nonrecursive definitions faster to type check when the definition is a
matchon literals. For aString → Natfunction with 128Stringliteral alternatives, generating its equation theorems, whichsimp [f]andcbvneed, takes 15.5s instead of 25.7s.#15856 adds an optional starting position to
Lean.Parser.parseHeader, allowing tools such as Verso to parse module headers inside a larger source file while preserving source locations.#16477 makes generating the equations of a
matchfaster when a discriminant is annotated withh :and the patterns are values. Formatch h : s withand 64Stringliteral alternatives, it takes 0.40s instead of 1.50s.#16476 makes the proofs that two
Stringliterals are different cheaper to check, improving on #16474. For two literals that share a prefix of 512 characters, the kernel checks the proof in 3.5ms instead of 4.4ms.#16474 makes the proofs that two
Stringliterals are different faster to build and to check. These proofs are used bysimp,cbv, and the equations ofmatchexpressions withStringpatterns. For two literals that share a prefix of 64 characters, the kernel checks the proof in 0.60ms instead of 1.85ms.#16465 makes generating the equations of a
matchwith many value patterns faster. For amatchwith two discriminants and 64 alternatives such as| "name", 0 => ..followed by a catch-all, it takes 0.38s instead of 1.16s.#16460 makes generating the equations of a
matchwith many alternatives faster when the patterns contain literals nested in constructors, e.g.,| some "a" => ... For 32 alternatives of this form, generating thematchequations takes 0.53s instead of 1.45s.#16354 speeds up the generation of equation lemmas for definitions that
matchonStringliterals. With 64 literal patterns, generation used to hit the heartbeat limit.#16408 makes elaborating large
mutualblocks defined by well-founded recursion faster. Cleaning up the termination proof goals no longer takes time proportional to the number of functions in the block, which used to make elaborating the whole block quadratic. As a side effect, the functional induction principle of a function with a nested recursive call, such asf (f x), no longer contains a duplicate induction hypothesis for the inner call; proofs that name the hypotheses of such a case positionally need to drop one name.#16422 simplifies the result type of the function that packs a
mutualblock defined by well-founded recursion: where both branches of a case split on the packed argument have the same non-dependent result type, the case split is omitted. If all functions have the same result type, the packed function now has that type, as the docstring ofArgsPacker.Mutual.uncurryTypealready promised. Previously this type was a case split over all functions of the block, which appeared in the motive of every case split in the definition and its unfolding lemma and made type checking large blocks slow.#16409 packs the arguments of a
mutualblock defined by well-founded recursion into a balanced tree ofPSumtypes instead of a right-nested chain. The nesting depth of packed arguments and of the case splits that take them apart becomes logarithmic in the number of functions, which makes elaborating and type checking large blocks much cheaper. Blocks of up to three functions are packed as before.#16320 fixes a segfault when
withImportModulesis called a second time in one process and the imported module imports another package root, a regression from #15291.#16279 fixes
Expr.hasLooseBVar,Expr.liftLooseBVars,Expr.lowerLooseBVars, task priorities and the kernel's handling of the number of parameters of an inductive declaration, which silently truncated values of2^32and above to 32 bits. For example, the kernel accepted an inductive declaration withnumParams := 2^32and recordednumParams = 0, and a task with priority2^32 - 1ran synchronously in the caller rather than on a dedicated thread.#15889 makes type class resolution reuse cached results much more often. A result is shared by all local contexts that agree on the local instances of the classes its search consulted, and declaring or erasing an instance only invalidates the results whose search consulted the instance's class. Building all of Mathlib takes about 2.7% less wall-clock time, and about 6.7% less time in type class resolution.
#16273 makes
set_option maxRecDepth 0mean "no limit" in the compiler and in macro expansion, and makes hugemaxRecDepthvalues act as unlimited in the kernel instead of wrapping around to a small limit. Previously,maxRecDepth 0was stricter than e.g.maxRecDepth 10000, and values such as2^60could reject shallow declarations.#16235 makes the equation lemmas
f.eq_<i>keep thehaves andlets of the right-hand side when they split amatchbelow them, instead of inlining their values into each equation. Inlining duplicated the values, exponentially for nestedhaves, and lost the sharing of the join points thatdonotation introduces, whichvcgen +jp [f]needs (#16122). The generated equations are otherwise the same: inlining thehaves gives back the previous equations.#16252 fixes a kernel error
unknown constant 'f.match_1.eq_1'when generating equation lemmas whose statements contain cast proofs, as happens when amatchon a literal is reduced under a dependent argument. Definitions whose body eliminates an empty type now get one equation lemma stating the unfolded definition, instead of none.#16219 fixes timeouts when comparing distinct
Float/Float32literals, for example while generating the equation lemmas of amatchon float literals. Unifying such literals used to unfold the float model on both sides in lockstep.#16215 fixes
matchonFloatandFloat32literal patterns treating literals that denote the same value (such as5and5.0, or16777216and16777217asFloat32) as different patterns, which could cause a matching alternative to be skipped. Such overlapping alternatives are now also reported as redundant.#16208 makes the equation lemmas
f.eq_<i>keep thehaves andlets at the root of the right-hand side, unless they must be zeta-reduced to split amatch. For a definition without amatch,f.eq_1is now the same asf.eq_def.#16138 makes
Kernel.Environment.replayadd the constants used in the types of all members of a mutual inductive block before adding the block. Previously only the dependencies of the member through which replay reached the block, and those of the constructors, were added, so a valid export could be rejected withunknown constant, depending on hash order.#16132 speeds up type class resolution for classes with many instances.
#16105 ports the macro used for long list to a term elaborator instead. The term elaborator mimicks the logic of the previous macro but executes it noticeably faster than before.
#16091 avoids using an mvar for the type of a numlit when the type is known.
#16078 improves the performance of elaborating long list literals.
#16047 fixes equation lemmas of structurally recursive functions whose
rflproof was very expensive for the kernel to check. For example, generatingf.eq_2for the following definition failed with kernel deep recursion, andcbv,rw [f.eq_2], andsimp [f]failed with it:def f : Nat → Nat → Nat | 0, x => x | n+1, x => f n ((x * 1103515245) % 5)
#16046 fixes quadratic elaboration behavior for large string-literal equalities such as
theorem t : s = String.ofList l := rfl.#15959 changes the parser of
returnto allow the term afterreturnto start on a later line.#15968 speeds up
Environment.hasUnsafe, whichmkAuxTheoremruns on the type and value of every auxiliary theorem, such as each proof produced bygrind. Imported constants are now read from the imported constant map, which is computed once per traversal. Before,findAsync?wrapped each of them in anAsyncConstantInfo, allocating the wrapper, twoTasks and aConstantVal.#15955 adds the
@[vcgen_simp]attribute, which collectsSym.simptheorems for thevcgentactic.#15951 makes normalization for the TC cache fail if a local instance is not a free variable.
#15855 adds a
mkInstanceNameOfTypefor determining the fully qualified name of an instance and makes delta deriving use it.#15898 makes
@[deprecated]onsyntax,macro,elab,notationand the mixfix commands deprecate the declared syntax, likedeprecated_syntax.#15942 speeds up lookups of attribute and environment-extension data for imported declarations, such as reducibility status, tag attributes, parametric attributes and
MapDeclarationExtension.find?. These lookups run very frequently during elaboration, and their results are unchanged.#15921 speeds up
Expr.consumeTypeAnnotations, which the elaborator calls on the expected type of each application argument.#15920 speeds up
Expr.cleanupAnnotations, whichmatch_exprandlet_exprcall on the discriminant and after every argument they peel.#15897 ensures that the rules for macros which are deprecated are themselves not linted for deprecated declarations.
#15806 allows users of the
deprecated_syntaxcommand to optionally specify a syntax transformation to produce a suggested replacement that will then be available as a code action.#15879 makes notations, macros and other checked quotations (
``(…)) report deprecated constants where they are defined, in addition to every place they are used.#15858 changes many places that erase free variables from the local instances to use the same functions,
LocalInstance.eraseandLocalInstance.eraseAll(a new function), and makes them not rely on the fact thatfvaris a free variable. Local instances which are not free variables are useful e.g. for the new deriving framework (#15320) but should not be used in code that may revert or clear free variables.#15863 makes the elaboration of terms with many postponed type class problems, such as long arithmetic expressions over numerals, take linear instead of quadratic time. For example,
def bla : Nat := 2 ^ 3 * 8 + 2 ^ 3 * 8 + ...with 80 summands now spends 65 ms in type class inference instead of 2.95 s.#15824 fixes
dsimpandsimpunfolding a function defined by mutual structural recursion when amatcharound a recursive call to another function of the group does not reduce. The resulting proof was accepted by the elaborator but rejected by the kernel.#15737 fixes
fun_casesandfun_inductionfor amatchwhose discriminant appears in the type of another variable in the goal.#15813 makes the "deprecated syntax" linter report in places it previously missed.
#15371 expands the condition for which the major of a recursor can be eta-expanded. Namely, subsingleton structures such as
Andshould be eta-expanded in this situation.#15103 ensures
is_def_eq_proof_irrelruns before reducing any potential proofs inis_def_eq_corerather than after. This is already the order in which things run in the elaborator, so no need for any changes there.#15373 eta-expands partial constructor applications.
#15682 fixes
mkBindUnlessPureto only run the continuation once, making sure that usingpure ()doesn't elaborate everything afterwards twice.#15740 makes name resolution treat auxiliary local declarations (recursive references to the definition being elaborated,
let recandwhere) like the global declarations they represent, for both more consistent semantics and faster lookups.#15738 fixes a
(kernel) unknown constanterror for structurally recursive definitions where a recursive call appears as amatchdiscriminant and an alternative of thatmatchalso recurses. Such definitions are now compiled using structural recursion.#15318 adds a
getEntriesWithKeysfunction toDiscrTreethat can be used to get all entries inside of aDiscrTreethat have a specific key sequence.#15710 fixes the functional induction and cases principles for functions that match with a named pattern on a literal or a constructor without arguments (e.g.
n@5orb@true), which were previously rejected by the kernel.
Library
#16487 bakes monotonicity into
Lean.Order.PredTrans.PredTrans.mk f hbuilds a transformer from a functionfand a proofhthatfis monotone,PredTrans.applyapplies it, andPredTrans.apply_monostates its monotonicity. TheWPclass now carries onlytranssince monotonicity is baked in.#16497 fixes the bad performance on
Std.Http.Header.Name.ofString?andHeader.Value.ofString?.#16417 fixes twelve cases where the HTTP/1.1 client, the server or the URI printer did not follow RFC 9110, RFC 9112 or RFC 3986.
#16418 reimplements
IO.Process.spawnand the operations onIO.Process.Child. This fixes a number of bugs on all platforms, makes spawning much faster in processes that use a lot of memory, and makesspawnthrow an error if the command cannot be started.#16441 makes all functions that later receive a
csimplemmanoncomputable, to ensure that the slow versions are never used.#16429 makes the
Std.Httpserver keep reading a client's upload before closing the connection when it rejects the request from its head alone, such as a413for a declared body overmaxBodySizeor a400for conflictingContent-Lengthfields. Previously the client could get a connection reset while still sending its body, and lose the response.#16426 makes closing a TCP socket on Windows cancel all pending writes, whichever thread issued them, as it already does on other platforms. Before this, a write to a peer that does not read could keep the socket open indefinitely if a different thread had issued it.
#16400 fixes several
Std.Httpbugs:A 2xx response to
CONNECThas no framing fields or content and closes the connection.closeinConnectionwins overkeep-alivefor every HTTP version, and empty list elements are accepted.HTTP/1.0 requests are sent with
Content-Length, and an HTTP/1.0 response with a transfer coding becomes a 500.Request-target limits derive from
maxUriLength, an overlong request line gets 414, and trailing CRLF at EOF is not a second request.Chunk extensions with obs-text are ignored instead of failing the request, and leading zeros don't count toward the chunk-size limit.
URI.Configdefaults are raised, and padded ports and 253-character hosts with a trailing dot parse.:in a username is encoded, and aRequestTargetdrops userinfo and the fragment.Status.isServerErrorcovers 600–999.waitShutdownwakes every waiter, and reads stop atmaximumRecvSizewhile a response streams.The server lingers after an early response, a failing
onFailureno longer skips cleanup, and late response bodies are closed.Body.Stream.closekeeps accepted bytes, and a cancelledreadAllthrows. AI Assisted (Claude)
#16366 adds
Std.Async.Watchdog, which enforces deadlines on a sequence of waits with a single background timer and cancels aCancellationContextwith.deadlinewhen a wait outlives its deadline.#16380 makes the HTTP/1.1 server report truncated request bodies to handlers and end connections whose peer stops reading. It adds
Config.writeTimeout(default 30 seconds) andcloseon TCP sockets.#16373 fixes the HTTP/1.1 server closing a keep-alive connection right after a slow response write finishes.
#16372 fixes the
Substring.Raw.splitOnfunction which did not properly backtrack.#16371 fixes a number of typos and factual errors in the docstrings for
Stringfunctions.#16362 makes an HTTP/1.0 request gets an HTTP/1.1 status line, a 205 response carries no content, the error responses the server writes itself carry a
Datefield and a shorttext/plainexplanation, and a request with an unrecognized method or with a transfer coding other thanchunkedgets 501 instead of 400 or reaching the handler still coded.#16360 revamps input and output handling for processes as seen in
Process.outputandProcess.run.#16328 fixes how
Std.Httpparses and prints URIs, request targets andHostvalues, and howdecideRedirectresolves and follows redirects. Query values may contain=, aLocation: /redirect goes to the root, and a printed URI reads back as the same URI.decideRedirectno longer takes theonlySafeRedirectsandresponseVersionparameters.#16322 makes the HTTP/1.1 server continue with the next request while a response is still being written, instead of waiting for each socket write, which makes pipelined and keep-alive requests about 15–30% faster.
#16358 makes
Process.Child.killsendSIGTERMorSIGKILLdepending on a new parameterforcedefaulting totrue(i.e.SIGKILL).#15532 marks
Dyadic.toRatas a coercion, and tags various lemmas withnorm_cast.#16282 fixes HTTP/1.1 message parsing, framing and connection handling in the client and server, and a few small
Std.HttpAPI issues.#16080 makes
Std.Http's HTTP/1.1 server answer a request whose request-target exceedsmaxUriLengthwith414 URI Too Longhowever the request line is split into reads. A read that ended between bytemaxStartLineLengthand the parser'smaxUriLengthcheck gave400 Bad Request.#15841 makes
Std.Http's HTTP/1.1 parser wait for more input, instead of failing the message, when a read ends inside a chunk extension or a trailer field.#16258 fixes many cases where
Std.Timecould not parse the text it formatted with the same pattern, includingaaaa(#16247) andBat night (#16248). It also makesPlainDate.formatandPlainDateTime.formatuse theirlocaleargument, keeps non-zero seconds in zone offsets, and correctsMonth.Ordinal.toDaysandPlainDate.ofWallTimebefore 1970.#16266 makes building and editing
Std.Http.Headersseveral times faster by keeping header entries in an array that lookups scan.#16079 makes
Std.Http's URI and Host parsers read a host name that begins with an IPv4 address, such as1.2.3.4-x.example, as a name, instead of rejecting it.#16265 changes the encoding of HTTP structures to raw ByteArrays.
#15892 makes the
String-keyedURI.Queryoperations (get,getD,find?,findAll,contains,eraseandset) find a query parameter by its decoded name, so a parameter is found whichever valid percent-encoding it arrived in. Previously, a name a browser percent-encoded, such asa%3Abfor a form field nameda:b, could not be looked up as"a:b", andsetadded a duplicate parameter instead of replacing it.#15254 preserves literal
+characters in HTTP query keys and values by encoding them as%2B, so they remain distinct from spaces. For a query received asa+b=1,get "a+b"now returnsnone; useget "a b"for that space-containing name, or senda%2Bbto represent a literal plus.#15323 adds
withIsExclusive a k h, which runskon whetherais exclusive at runtime and is logicallyk false; the proofh : k true = k falsekeeps it sound. It lets safe code take different paths depending on sharing, for example to skip caching values that are referenced from at most one (owning) location.#16225 makes
Core.transformpreserve sharing of unchanged application nodes. Other expressions already remained shared before.#16217 adds
wf_preprocesslemmas for the various higher-orderOptionfunctions.#15269 speeds up leading- and trailing-zero counting on bitvectors, including kernel reduction, while preserving support in
bv_decide. Proofs that unfold these operations should instead useBitVec.clz_eq_clzAuxRecorBitVec.ctz_eq_reverse_clzto recover their previous definitions.#15265 adds
Nat.trailingZerosand makes trailing-zero counting forNatandIntefficient for arbitrary-precision values, speeding up dyadic normalization. Both operations return zero on zero, andInt.trailingZerosagrees with the natural-number operation onnatAbs.#16116 adds
Vector.modifyto update an element with a function, returning the vector unchanged when the index is out of bounds.#16119 fixes
GenericFormat.parsefor patterns that rejected or misread whatGenericFormat.formatwrites with the same pattern, and adds*and/byNatandIntscalars to theStd.Timeunit offsets andDuration.OandOOOOnow accept a bareGMT,xxxxxaccepts offsets without seconds, andZ,ZZandZZZaccept offsets with seconds.PlainTime.toTime12Hourno longer writes an hour that is off by one, such as04:00:00 PMfor 15:00.k,Kandywith a BC era now parse to the correct hour or year instead of silently returning a wrong value.#15997 makes
JsonNumber.toStringwrite a zero mantissa as0whatever the exponent. With an exponent above 10 it wrote0.e-k, which is not JSON, soJson.compressoutput for such a number did not read back withJson.parse.#15996 makes
Json.parsefail with a parse error on arrays and objects nested more than 10,000 levels deep, instead of overflowing the stack and aborting the process.#16113 makes kernel reduction of
String.toListon a string literal take time linear in its length. Previously,decide +kernelons.toList.length = 400took about 8 s, and literals of a few thousand characters hit the kernel's recursion limit.#15160 adds
Nat.extendedGcd, returning a gcd and signed Bézout coefficients together with correctness and simplification lemmas.#15077 adds
UInt64.mulMod,UInt64.powMod, andUInt64.invMod?for fixed-width modular arithmetic without overflowing intermediate products.powModaccepts an arbitraryNatexponent, andinvMod?returnsnonefor a zero modulus or noncoprime inputs.#15885 adds
IO.FS.renameIfNewwhich performs an atomic rename and errors if the destination already exists.#16099 removes the instances
instInhabitedForallandinstInhabitedForallOfMonad.#16095 introduces
Lean.UnionFindas a compiler internal union find data structure. It features rank-based merging, path splitting, and efficient tracking of equivalence class members via cyclic pointers.#16053 adds benchmarks for many parts of Std.HTTP, from encoding, body streams, handlers, and the H1 machine to server and client behavior over TCP.
#16022 speeds up
Json.compress,Json.prettyandJson.escapeon strings that contain non-ASCII characters, with unchanged output.#15952 adds the missing order instances for
Char, namelyMin/Maxand the associated lawfulness properties.#15936 ensures that CXXFLAGS is passed to CaDiCaL's kitten component. This is necessary since the CaDiCaL 3.0 upgrade as it now includes kitten, a subsolver written in C.
#15653 fixes several libuv-backed system and network functions:
osGetPriority,osSetPriority,osGetGroupandgetGroupthrowIO.Error.invalidArgumentfor a process or group id that does not fit the operating system's id type, instead of truncating it and acting on a different process or group.osGetGroupnow takes aNatinstead of aUInt64.osGetGroupthrowsIO.Error.unsupportedOperationon Windows for every id.osGetPasswddecides whether the group id is missing from the group id itself rather than from the user id.IPv6 addresses are converted correctly on big-endian hosts.
IPv6Addr.ofStringrejects a%zone suffix instead of silently dropping it.getProcessTitlereturns titles of 512 bytes or more, and fails withENOBUFSinstead of exhausting memory when the process arguments were never set up, as in theleanbinary.osGetenvreturnsnonefor a name with an=after its first character instead of the value of the variable named by its prefix. Windows variables such as=C:are still found.IO.Process.Child.pidno longer leaks theChildobject.The libuv runtime sources no longer use
using namespace stdin headers, give their file-local helpers internal linkage, and declare the timer functions on all builds.
#15294 adds union/intersection emptiness distributivity lemmas:
-- isEmpty_union_inter / isEmpty_inter_union ((m₁ ∪ m₂) ∩ m₃).isEmpty = ((m₁ ∩ m₃).isEmpty && (m₂ ∩ m₃).isEmpty) (m₁ ∩ (m₂ ∪ m₃)).isEmpty = ((m₁ ∩ m₂).isEmpty && (m₁ ∩ m₃).isEmpty) -- union_inter_equiv_empty_iff / inter_union_equiv_empty_iff ((m₁ ∪ m₂) ∩ m₃) ~m ∅ ↔ (m₁ ∩ m₃) ~m ∅ ∧ (m₂ ∩ m₃) ~m ∅ (m₁ ∩ (m₂ ∪ m₃)) ~m ∅ ↔ (m₁ ∩ m₂) ~m ∅ ∧ (m₁ ∩ m₃) ~m ∅ -- union_inter_eq_empty_iff / inter_union_eq_empty_iff (extensional variants) (m₁ ∪ m₂) ∩ m₃ = ∅ ↔ m₁ ∩ m₃ = ∅ ∧ m₂ ∩ m₃ = ∅ m₁ ∩ (m₂ ∪ m₃) = ∅ ↔ m₁ ∩ m₂ = ∅ ∧ m₁ ∩ m₃ = ∅
#15562 makes
grindterminate on goals that take theminof two identicalList.findIdxterms by givingList.min_findIdx_findIdxan explicitgrind_pattern. It is instantiated only for distinct predicates and only on terms of low generation.#14753 makes
vcgen … with finishprove that a loop measure decreases when the measure lands in a pair or a nested pair of well-founded types. For example, awhileloop that countsidown and resetsjcloses with.ofMeasure fun (i, j) => (i, j)andwith finish.#15317 adds
Bool.dand, the dependent version ofBool.and, andOrdering.dthen, the dependent version ofOrdering.then, along with new lemmas both for the non-dependent and for the dependent versions. Additionally, it adds aDecidableinstance that's useful for case distinction in proofs about functions likeOrdering.dthen. These primitives will be useful for implementing the newBEq/Ord/DecidableEqderiving handlers in #14929.#15603 adds
owned_refa helper that owns lean objects and helps avoiding hundreds oflean_incandlean_decinside the LibUV codebase#15711 adds order instances on
String.Slice.#14892 redefines
WellFounded.fix,WellFounded.fixFandWellFounded.recursionso that they no longer eliminate an accessibility proof into data, and addsAcc.rec',Acc.recOn',Acc.ndrec'andAcc.ndrecOn'for code that needs to do so itself. Fixpoint equations and compiled code are unchanged, andAcc.recis untouched. The one visible change is that well-founded definitions now depend onClassical.choice, which#print axiomsreports.#15598 introduces the
uv_buf_tarray for TCP and UDP sends on the stack, and makes send and recv fail with an invalid-argument error for a buffer size of 4 GiB or more, instead of letting the length wrap to 32 bits.#15680 makes
WPMonad.withFrameClosureuniverse polymorphic. It now accepts a monadm : Type v → Type wand a resourceR : Type tin any universe, for exampleStateT (ULift.{1} Nat) Id.
Tactics
#16532 makes
simpfaster on terms with long projection chains, such as the ones in the proof of the unfold theorem (f.eq_def) of a function defined by structural recursion over a large nested inductive type.#16507 makes
vcgen [f]linear in the number of join points off. Making the spec for the unfold equation offzeta-reduced its right-hand side, the whole program, which copied each join point into all its jumps. For a chain of 16ifs that reassign a mutable variable,vcgen +jp [chain]now takes 28 ms instead of 3.2 s.#16525 changes how the
grindcommutative ring solver picks the basis equation used to simplify a monomial. It now uses the equation with the fewest terms among those whose leading monomial divides the monomial. This keeps intermediate polynomials smaller on some problems. On the ring tests and benchmarks the output is unchanged and the total instruction count drops by 0.5%, withgrind_ring_59.3% faster.#16504 fixes process aborts with
INTERNAL PANIC: Nat.pow exponent is too biginsimp,grind,cbv,bv_decideandbv_normalize. They happened on goals containing aBitVecliteral of width2^32or more, such asexample (x : BitVec 5000000000) : 1#5000000000 = x := by simp, and on powers with an exponent of2^32or more whenexponentiation.thresholdwas raised above2^32. These terms are now left unevaluated. The examples from #15786 now pass.#16499 improves
grind's ring solver on commutative rings that do not implementNoNatZeroDivisors, where it can now derive equalities it could not derive before. Example:example [CommRing α] (x y : α) (h₁ : 2*x = y) (h₂ : 3*x = y + 1) : x = 1 := by grobner
#16468 adds a new tactic called
eprfor solving EPR problems using a BitVec encoding combined withbv_decide. This tactic will be particularly useful for applications in protocol verifiers such as Veil.#16456 implements Z3-style instantiation sets for MBQI based model-checking.
#16455 introduces a Paradox-style union-find based subsort analysis to
bv_decide's EPR support. It operates in two steps:Infer subsorts using a normal union-find algorithm and at the same time detect (non)-monotone sorts using the syntactic positive equality criterion.
For all monotone sorts that have more than one syntactic subsort do split them up into actual subsorts in the EPR problem.
#16453 implements some symmetry breaking for the EPR encoding used in
bv_decide, we provide 3 different modes:off, no symmetry breaking, provide the minimum sound encoding. That is, every sort element gets assigned aBitVecvariable that is unconstrained besides the maximum sort cardinality.simple, the default. Instead of leaving them unconstrained we say that the bitvec encoding of elementa_imust be<= i. This is similar to one of Paradox's symmetry breakers introduced in "New Techniques that Improve MACE-style Finite Model Finding"full. This introduces as much symmetry breaking as possible, in addition tosimplethis introduces the fact that ifa_i != ithen alla_jwithj > iwill also havea_j != i.
#16452 introduces a basic EPR solver to
bv_decide. It detects type parameters that act like EPR sorts, encodes them into a BitVec representation and finally solves the problem using a naive MBQI loop. Follow up work will provide a convenient top level tactic for this.#16484 makes
vcgen +jpstate the equation of a join-point parameter once, above the disjunction over the jumps, if every jump passes the same term for it. For a join point that many jumps reach in the same statet, the join hypothesis is nows = t ∧ (d₁ ∨ … ∨ dₙ), so each disjunctdᵢhas one equation fewer.#16414 fixes a stack overflow in
sym =>whenapplyunifies a metavariable with a term that contains it. For example,apply Eq.reflon the goal?n = ?n * ?nused to assign?n := ?n * ?n, and now fails with "rule is not applicable".#16346 adds the config options
simpMaxStepsandsimpMaxDischargeDepthtovcgen. They setmaxStepsandmaxDischargeDepthof everySym.simprun of the simp step, as the fields of aregister_sym_simpvariant do. The defaults are those ofSym.Simp.Config.#16316 improves
cbvhandling of match equations. Previouslycbv, when encountering match expressions would try first to use matcher equations usingSymmachinery for theorem rewrite, with no discharger enabled, before falling back towhnf. Now, we try a discharger that can deal with overlap hypotheses, by applyingcbvto each of the arguments of the overlaph hypothesis. Literals nested inside constructor pattterns, still fall back towhnf, sinceSym.simphas no simproc for constructor injectivity yet.#16341 fixes the
grindinternal error "linarith term has not been internalized" on negative numerals such as-1 : T, whereTunfolds toIntand has an orderedIntModuleinstance but noCommRinginstance.#16319 changes the proofs produced by
lia,grind, and theNatoffset simprocs so that the kernel no longer has to evaluate their arithmetic atoms. Before, for goals containing terms such as(x + 4294967295) % 4294967296, the kernel ran in unaryNatarithmetic and failed to check the proofs in practice. Closes #16311.#16310 makes
vcgenkeep its goals maximally shared, and runs thevcgenandmvcgentests withsym.debugset, so the test suite catches a change that breaks aSymMinvariant.#16291 adds the attribute
@[vcgen_rintro], which tellsvcgenhow to destructure a binder while it introduces the binders of a goal, like a fixedrintropattern. For example, with#16303 makes
vcgenkeep the value of aletorhavein the program as written, as before #16292, so thatvcgen +jpis as fast as before. For example,have x := 0 + k; pure (x + x)leavesx : Nat := 0 + kin the VC undervcgen simp [Nat.zero_add].#16292 makes
vcgenstep past aletorhaveat the head of the right-hand side of an entailmentpre ⊑ rhs. A spec such as#16298 fixes
grind linarithfailing with the internal error "structure is not a preorder" on≤and<facts over types with an order but noOrderedAddinstance, such asFin nandBitVec w. For example,(x : Fin 3) (h : x < x) : Falseis now proved bygrind_linarith, and the satisfiable(x y : Fin 3) (h₁ : x < y) (h₂ : y + 1 < x + 1) : Falsenow fails with a regulargrindfailure message.#16297 fixes a kernel type mismatch on
eq_of_dvd_edivin proofs produced byliaandgrind, for goals such asx % 3 ≤ 2 * x % 3 → 4 * x % 3 ≤ 2 * x % 3.#16294 fixes the internal error
mkNoConfusion: No manifest constructorsincontradictionon hypotheses such ash : 0 + 0 = 1.#16261 makes
vcgenreport an error when the goal is aStd.Dotriple or entailment, and whenStd.WPis not imported. The error message comes with a hint what to do. TheStd.Doerror asks the user to restate the goal with the definitions fromStd.WP, and to addimport Std.WPwhen it is missing.#16280 makes
vcgenrewrite amatchon a string literal discriminant in its verification conditions, e.g.match "done" with | "start" => False | "done" => True | _ => Falsereduces toTrue.#16264 fixes a kernel error in the
Sym.simp-based arithmetic normalizer on types of characteristic1, such asFin 1. The normalizer now leaves these types as written.#16263 fixes a
grind.debugpanic incheckEqcon goals such asx = 1 → -x = -1forInt8,Int16,Int32, andInt64.#16226 changes
bv_normalizeto explicitly eliminateBitVec.castvia equational rewriting withBitVec.cast_eqas opposed torfl. Michael Tautschnig noticed that eliminating viarflforces the kernel to evaluate the term being cast which is potentially expensive.#16181 changes
vcgenso thatreduceHead?substitutes an assigned metavariable at the head of a term and beta-reduces, andinstantiateGoal?reduces the head of the entailment with it, so a goal whose right-hand side holds unassigned metavariables below the head is no longer instantiated in full at every step. Another consequence is that amatchpostcondition applied to a constructor yields one verification condition per conjunct, which renumbers thecase vcNtags of such goals.#16241 fixes
sym =>tactics that failed or made no progress on goals mentioning metavariables assigned after the goal was created, e.g., byapplyor by solving a sibling goal. This affectedintro,apply,simp,dsimp,let_to_have,lift_lets, and local instance registration.#16222 uses a CaDiCaL terminator based on a Lean
BaseIO Boolcallback for incremental solves instead of spawning a second thread that kills the solving process if it takes too long.#16069 introduces a generic incremental bitvector solver into bv_decide. For now this is only used to feed the BitVec component of the CEGAR loop but it will have additional applications in the future.
#16212 fixes
vcgen +jpfor a join point nested in a branch of another join point. Before, such a program failed with "vcgen +jp: unexpected binder" or "vcgen +jp: missing witness".#16221 disables CaDiCaL's lucky pass in incremental mode. At the beginning of each incremental solve it visits the whole problem trying an all true/all false assignment. This is quadratic if we sequence many incremental solves.
#16102 adds the lattice simplifications of
simpandgrind normto the@[vcgen_simp]set, sovcgenstates verification conditions at carrierPropwith∧,∨,∃,∀and→in place of⊓,⊔,⨆,⨅and⊑. The set also eliminates the index of a supremum when an equation determines it. For example, from the preconditionfun s => s = 3, the postconditionfun _ s => ⨆ n : Nat, ⌜s = n⌝ ⊓ ⌜n < 5⌝leaves no verification condition, and the postconditionfun _ _ => ⨆ n : Nat, ⌜n < 5⌝leaves∃ n, n < 5.#16216 makes the join point hypotheses of
vcgen +jpsmaller. For two sequentialifs that modify the state, the hypothesis of the second join point is nowb 0 = true ∧ s = s₀ + 1 ∨ ¬b 0 = true ∧ s = s₀ + 2. Before, it also contained the equationx = (PUnit.unit, s₀ + 1).fstfor the result of the firstif.#16192 makes
vcgeninstantiate assigned metavariables in hypothesis types before introducing them to the local context. This results in more Sym term sharing and more reliablevcgenoperation in general.#16207 fixes a panic and a kernel error in
grindwith the new normalizer (backward.grind.normalizer false) when the local context contains alet-variable, as in(h : a * b = c) : let x := a * b; x = cafterintro x.#16204 fixes
grindfailing on goals that mix a cast fromNatand a cast fromIntinto the same ring, such as(m : Int) (k : Nat) (h : m = k) : (m : R) = (k : R). With the new normalizer (backward.grind.normalizer false) this also affected goals written as(m : R) = ((k : Int) : R), because the normalizer rewrites((k : Int) : R)to(k : R).#16203 makes
Symhandleletandhavedeclarations. Backward rules (sym => apply,vcgenspecs and unfold rules) now keep thehaves of their hypotheses in the new goals instead of copying the values into every use. Matching and unification now unfoldlets andhaves in the goal instead of failing or reporting "unexpected let-declaration term". As a result,vcgen +jp [f.eq_def]shares the join points off: withnsequentialifs it produces 2 goals instead of 2ⁿ⁺¹ (part of #16122). Ahavein the program can now appear in a verification condition as a let-variable.#16199 introduces a cache for bitblasting of boolean substructure in bv_decide. Note that at the bit/AIG level this was already being cached but we never the less repeatedly traversed the expressions before. This has so far not been an issue as our problems mostly consisted of BitVec expressions which is not necessarily the case anymore.
#16193 fixes a kernel error in
grindonmatchexpressions with overlapping patterns where a literal in the discriminant meets a pattern variable, e.g.p (3, false)withpdefined bymatch s with | (_, true) => 0 | _ => 1.#16167 fixes
grindfailing to prove(m : R) = (k : R)for a ringRsuch asZMod nwhen the facts forcem = kbutliadoes not derive it, e.g., fromm ≤ k,k ≤ m + 1and2 ∣ k - m. This fixes a Mathlib regression introduced by #16161.#16165 makes the
Sym.Arithnormalizer pushNatandIntcasts through+,*and powers with a literal exponent, and forIntalso through-, negation and casts fromNat. As a result,(m + n) • x = m • x + n • xand((m * n : Nat) : R) = ((n * m : Nat) : R)are now proved bySym.simpwitharith, and by thegrindnormalizer. TruncatedNatsubtraction, division and remainder are still treated as atoms.#16164 fixes
sym => dsimptiming out on large, deeply nested terms thatsym => simphandles quickly.#16163 makes
Sym.simpreduce amatchwhose discriminant is a value such as aString,NatorCharliteral, e.g.match "b" with | "a" => 1 | "b" => 2 | _ => 3. This affectssym => simpand theSym.simp-basedgrindnormalizer, which previously left such terms unchanged.#16162 fixes
Sympattern matching (used bySym.simp,Sym.dsimpandapplyinsymmode) for theorems whose universe variables first occur inside amaxlevel, such as rewriting@id (α × β) pwithid_prod {α : Type u} {β : Type v} (p : α × β) : @id (α × β) p = pwhenβ : Type (max v w). Previously, the matcher guessed the universe variables by splitting themaxargument by argument, and failed when a later occurrence such asProd.{u, v}required different values.#16161 fixes
grindmodel-based theory combination making useless case splits onx = yforNatterms such as3 * x,x / 3andx % 3, which it treated as nonlinear because onlyIntnumerals were recognized.#16159 makes the
Sym.simp-basedgrindnormalizer handle integer powers with a literal exponent in a field. For example,2 ^ (-1 : Int)becomes2⁻¹anda ^ (2 : Int)becomesa ^ 2, so they take part in the polynomial normal form. The legacy normalizer only evaluates a numeral power inside⁻¹or/.#16158 fixes universe level unification in
Sym, which could assign a universe level metavariable to a level containing itself (causing a stack overflow) or overwrite an existing assignment (leaving universe metavariables in the proof).#16157 fixes
grindwith theSym.simpnormalizer on goals that use/in a field of nonzero characteristic. For example,a / c = b → b = a * c⁻¹over[Field α] [IsCharP α 7]now closes, as it does with the legacy normalizer.#16156 makes the
Sym.simparithmetic normalizer, used bysym => simpand theSym.simp-basedgrindnormalizer, prove groundNat,IntandRatsubterms such as2 ^ 64or the2 + 3ina + (2 + 3)byrflinstead of a ring-reflection certificate, which reduces kernel checking time.#16152 reduces the fixed cost of every
grindandliacall by about 25 µs.#16147 replaces the
grindoptionsplitswithbranches, which limits the total number of branches that case splitting may create during a proof search (default 1024). Previously,grind,lia, and the related tactics allowed at most 9 case splits along each branch of the search, so a goal with a long chain of cheap case splits failed even when its proof was tiny. For example, a hypothesisx ≤ 0 ∨ 100 ≤ x ∨ x = 2 ∨ x = 4 ∨ … ∨ x = 36whose disjuncts are each refuted immediately needed 17 case splits in a row and exceeded the limit. Such goals are now proved with the default configuration, while the total amount of case splitting stays bounded.#16143 makes
lia(andgrind) assert the linear bounds that hold in every disjunct of a disjunction, instead of finding them by case splitting. For example,(b = true ∧ y = x + 1) ∨ (b = false ∧ y = x + 2)impliesx + 1 ≤ yandy ≤ x + 2. Goals produced byvcgen +jp(#16122) carry one such disjunction per join point. On them,liaexplored all 2ⁿ cases and failed forn ≥ 10at thesplitsthreshold. It now solves them in time linear inn.#16141 fixes an exponential slowdown in
grindon terms whose types are equal only modulo the E-graph, such asFin (a.set! i v).sizeandFin a.size, or the bounds proofsj < (a.set! i v).sizeandj < a.sizein array accesses.#16131 makes
rwand other tactics based onkabstractfaster on goals with shared subterms.#16130 makes
rwfaster on large goals by type checking only the parts of the motive that depend on the rewritten occurrences.#16129 speeds up
grindon goals with many nested case splits. Building the proof of a case split no longer traverses the proofs of the case splits below it.#16124 fixes a kernel "loose bound variables" error in
sym =>when twohaveorletexpressions differ only in their type.#16118 adds support for propositional variables in bv_decide even when they are not wrapped in
decide p = true.#16106 makes
vcgendischarge the hypotheses of conditional theorems in its simp set. The simp set (@[vcgen_simp]andvcgen simp [...]) now rewrites with the dischargerSym.Simp.dischargeSimpSelf. Example:Mem.loadInt_storeInt (hw : n ≤ 2 ^ w) : (m.storeInt a n v).loadInt a n = some (Int.ofBytes (Int.toBytes n v)). At a call sitenandware literals, and ground evaluation proves8 ≤ 2 ^ 64.#16114 fixes an
unknown free variableerror whenliacloses a subgoal ofcases_nextingrindinteractive mode, e.g.,grind => cases_next; all_goals finish.#16112 fixes an internal
grinderror ("term has not been internalized") caused by structure eta.#16094 makes
vcgenleave out a lifted equationx = tafter it substitutestforx, when no other hypothesis mentionsx. The equation then carries no information, and the verification conditions no longer show it. For example, the verification condition of a program that throws"x"against the postconditionfun e => e = "x" ∨ e = "y"was#16093 lets a
@[frameproc]name a theoremframesThm?that provesWP.Frames op x F Pfor every programx, frameFand guardP.vcgendischarges the frame condition of each framed call with that theorem, so the frame condition no longer becomes a verification condition.#16092 makes
try?treat a candidate tactic that exceeds the maximum recursion depth as having failed, as it already did for the heartbeat limit, instead of aborting with that error. For example,impossible by decideon a goal quantifying overUInt64hits the recursion limit and previously made the wholetry?call fail.#16085 reduces the time
grindspends in its order solver when many terms are related by fixed offsets, such as numerals in an ordered ring. Addingnnumerals used to take time cubic innand now takes quadratic time. For example, a goal with 300 hypothesesyₖ = koverIntnow takes 0.44 s instead of 1.86 s.#16075 makes the
grindfailure message reported without+verboselist the thresholds that were reached, as configuration items the user can raise. For example,lianow fails with`lia` has failed after reaching the threshold `(splits := 9)`, use `+verbose` to obtain diagnostic information. This applies toinstances,ematch,splits,gen,ringSteps, andliaSteps, and to all tactics built ongrind, such aslia,grind_order,grind_linarith, andgrobner.#16073 shortens the error message reported when
grindfails without+verbose. Instead of printing the failing goal, the message is now`<tactic>` has failed, use `+verbose` to obtain diagnostic information, where<tactic>is the tactic the user invoked (e.g.,lia,grind_order,grind_linarith,grobner,sym) rather than alwaysgrind. With+verbose, the goal and diagnostics are still reported, and the header also names the invoked tactic.#16072 fixes a
grindpanic inmkCongrDefaultProofwhen usingFunction.Injectivehypotheses together with case splits (#16059).#16056 fixes
grind?andfinish?dropping case-splits from their generated scripts when the proof does not use the case-split, but the rest of the script does. For example, a case-split may introduce a term that E-matching uses later. The scripts then failed to replay, andgrind?dropped theorems from itsgrind onlysuggestions.#16050 fixes
grind?generating a· donestep for a case-split alternative thatgrindcloses while introducing its hypotheses. The step failed when the script was replayed, which also madegrind?drop theorems from itsgrind onlysuggestions.#16057 makes
grind?check each suggested tactic before showing it. Previously, only the generatedgrind =>script was checked, and it was suggested even when the check failed. Suggestions that do not close the goal are now reported in a warning instead of being suggested, and if none of them works,grind?suggestsgrindwith the original configuration and parameters.try?uses the same check for thegrind onlysuggestions it shows.#16054 fixes
grind?suggestinggrind only [...]calls that fail because they need more E-matching rounds than theematchlimit allows. The search that found the proof may have performed more rounds because case-splits reset the round counter, even when those case-splits were not needed by the proof and were removed from the generated script. The suggestions now set theematchlimit, e.g.,grind (ematch := 6) only [...], when the generated script performs more rounds between case-splits than the limit.#16052 fixes
instantiate only [!thm]ignoring the!modifier whenthmis already registered as agrindtheorem, and using its registered patterns instead of the minimal indexable ones. Generated scripts using!thmthen failed to replay, andgrind?droppedthmfrom itsgrind onlysuggestions.#16051 fixes
grind?andfinish?dropping solver steps such asringandliathat make progress without closing the goal or propagating facts. Later steps may depend on that progress, so the generated script failed to replay, andgrind?also dropped theorems from itsgrind onlysuggestions.#16048 fixes
grind?producing scripts that pick the wrong case-split when local variables are shadowed, which also made it drop theorems from itsgrind onlysuggestions.#16042 fixes
grind?dropping[grind inj]theorems from itsgrind onlysuggestions, which then failed when pasted.#16041 fixes anchors such as
#c0c6ingrind only [...]being parsed as terms when a#prefix notation is in scope, which madegrind?suggestions fail. A#notation applied to a hexadecimal identifier can still be written with parentheses, e.g.grind only [(#ab)].#16040 fixes
instantiate only [...]never firing instances of theorems registered withgrind_pattern ... where guard ..., which madegrind?drop such theorems from its suggestions.#15961 makes
vcgensimplify the verification conditions it produces, together with the hypotheses and program states along the way. By default, it uses the theorems tagged@[vcgen_simp]and evaluates ground terms such as41 + 1, so that(a, b).snd = 7becomesb = 7and a branch whose condition evaluates toFalsecloses at once.vcgen simp [thm, h, *]adds theorems for one call and replacessimplifying_assumptions [...].vcgen -simpturns simplification off.#15999 makes kernel checking of
Sym.simp's arithmetic normalization and ofgrind's ring solver proofs much cheaper over few variables. Polynomial identities are checked by evaluating both sides at one point, instead of normalizing them in the kernel.#15995 makes kernel checking of
Sym.simp's arithmetic normal forms and identities, and ofgrind's Gröbner chains, cheaper. It uses polynomials whose monomials are packed into natural numbers (Grind.CommRing.PPoly, in the new fileInit/Grind/Ring/Packed.lean).#15990 makes kernel checking of
Sym.simparithmetic normalization much cheaper for terms with large products, such as(a + b + c + d + e) ^ 7 = (a + b + c + d + e) ^ 3 * (a + b + c + d + e) ^ 4.#15988 makes kernel checking of
Sym.simparithmetic relations and identities cheaper.#15986 makes kernel checking of
Sym.simparithmetic normalization much cheaper for long sums and large polynomials.#15984 speeds up kernel checking of the certificates produced by the
arithsimproc ofSym.simp, and adds benchmarks for the simproc.#15983 makes kernel checking of
cutsatproofs and of thesimp +arithsteps thatgrinduses to normalize hypotheses cheaper. On theliabenchmarks, kernel checking becomes 38–46% cheaper.#15981 makes kernel checking of
grind's semiring, field andlinarithproofs cheaper. It replaces definitions that the kernel reduces throughbrecOn, structural recursion or derivedBEqinstances with recursor-based ones.#15967 makes
lia,grindandSym.simp'sarithsimproc cheaper by answering the algebraic structure queries ofSym.Arithclassification forIntandNatfrom a table, without type class resolution. Eachgrindgoal classified these types again, issuing about 20 queries that the instance cache did not carry over between goals.#15970 makes kernel checking of
grind ringproofs much cheaper, especially for long Gröbner basis derivations.#15969 makes
grindring proofs smaller by building the expression of each distinct monomial and coefficient once.#15944 speeds up kernel checking of ring and field certificates produced by
grindandSym.simp.#15943 makes the kernel check the certificates of the
grindring solver and of theSym.simparithmetic normalizer about twice as fast. It also adds benchmarks for them undertests/ring_perf.#15934 optimizes literal recognition and improves
grindsupport for rational and signed fixed-width integer literals.#15926 makes
grindand its variants such asliainvoke only the solvers that the configuration enables. Each solver extension declares when it is enabled, andgrindcomputes the active solvers once per run, instead of calling every solver and letting each one check its own flag.#15924 speeds up
liaon goals that containa / kora % kfor a numeralk.#15922 makes
grindandliause the core instances forOfNat Int n,OfNat Nat n, andDecidableof≤,<, and=overIntandNatwithout running type class resolution when canonicalizing terms.#15917 makes the kernel check the remaining
liacertificates faster, including those for divisibility constraints, Cooper resolution, and constant folding. They now evaluate recursor-based versions of the operations they still unfolded throughmatch,decide, or fuel. Theorems that take user hypotheses now state them withExpr.denote_k, so matching a hypothesis no longer unfoldsExpr.denote.Init.Data.Int.Kernelgains versions of-,/,%,^,natAbs,toNat,gcd,lcm, andbmod.#15914 makes
liaadd the linear facts it derives fora / kanda % kwithout running them through thesimp-based preprocessor. These facts are linear combinations thatlianormalizes itself.#15912 makes
grind'smarkNestedSubsingletonspreprocessing step reuse the core cache for instantiated constant types instead of instantiating the type of every application head again.#15913 fixes
grindignoring hypotheses such as∀ n, v = f n → False, wheref nis not a pattern. The equivalent∀ n, ¬ v = f nworked.#15911 makes the kernel check
liacertificates faster. Certificates now evaluate versions of polynomial normalization andIntarithmetic written with recursors, so the kernel no longer unfoldsmatchand structural recursion. TheIntversions live in the new moduleInit.Data.Int.Kernelfor reuse.#15910 makes the
NatandIntlinear-constraint parsers used bysimp_arith,grind, andliacheck that a comparison is overNat(resp.Int) before testing its instance. Before,Simp.Arith.Nat.ToLinear.toLinearCnstr?matchedLE.le _ i a band calledDefEq.isInstLENat ion every comparison, so eachIntcomparison paid a failingisDefEqIagainstinstLENat;Simp.Arith.Int.ToLinear.leCnstr?anddvdCnstr?had the same problem withNatcomparisons.#15909 fixes
grindmissing amatch-expression condition when a constructor for a nested subterm arrives after the outer merge. For example, givenh : ∀ n, v = .lit (.nat n) → False,grindclosed the goal froml = .nat mandv = .lit lonly when the facts arrived in that order. The same issue prevented conditions ofmatchequations from becoming true, e.g.,f v = 2forfwith the alternatives.lit (.nat _) => 1 | _ => 2, givenv = .lit landl = .str sfrom a case split.#15906 changes the default of the
grindoptionverbosetofalse, which also applies tolia,cutsat,grind_linarith,grind_order, andgrobner. Failures now show only the remaining goal and the hintuse+verboseto obtain diagnostic information. Collecting and printing diagnostics took about 38% of the time spent on easy failingliagoals.#15905 makes
lia(cutsat) prove a constraint once, in the goal where it was stored, instead of once in every branch below it. On goals with manygrindcase splits,liais up to 2.8x faster in elaboration and up to 200x faster in the kernel.#15891 fixes a panic in
vcgenunderset_option sym.debug true. The panic occurred whenevervcgensubstituted a preconditionx = t.#15884 makes the
Sym.simp-basedgrindnormalizer (backward.grind.normalizer := false) cancel the common part of both sides of aNatsubtraction, as the legacy normalizer does withNat.reduceSubDiff:n + 1 - 1becomesn,n + 2 - 1becomesn + 1, and3 - (n + 1)becomes2 - n. Common monomials are cancelled too, son + k - kbecomesnandx * y + 3 - (x * y + z + 1)becomes2 - z.#15874 fixes a
grind.debuginvariant violation incheckEqcon goals such as(p && p && q) = (p && q).#15873 fixes a
grind.debuginternal error on groundRatarithmetic such as(3 : Rat) * 2 = 6.#15872 fixes
grindproducing a proof the kernel rejects (decide (1 = 1) = false) when the same literal occurs at definitionally equal but syntactically different types, such as(1 : BitVec w)and(1 : BitVec 32)for@[implicit_reducible] def w : Nat := 32.#15862 fixes the internal
grinderror "term has not been internalized" on anHEqfact whose sides are proofs ofBitVec,UInt8, orFinequations, e.g.,p ≍ True.introwithp : a = 1. Such facts are also created bygrindwhen it splits amatchwith a proof discriminant.#15860 fixes a kernel error in
grindwhen aBitVecwidth orFinbound is a definition, e.g.,x : BitVec Wwithdef W : Nat := 4.#15854 fixes
grind?suggesting agrind only [...]call that drops a premise used in the proof, together with a generated tactic script that fails to close the goal. This happened when the goal contains several case-split candidates that differ only in hidden variables, such as thew✝s introduced by function extensionality.#15852 fixes a kernel type error in proofs produced by
grindwhen goals contain heterogeneous arithmetic applications such asc * xswithc : Natandxs : Vector Nat n.#15851 fixes a stack overflow in
grindwhen amatch-expression condition refers to a term in a cyclic equivalence class, such asas = a :: as.#15850 fixes a
grindproof that the kernel rejected when the goal involves a ring of characteristic1, such asFin 1. Disequalities in such rings now close the goal directly.#15847 fixes the
grind.debuginternal error "internalizereached an application whose arguments are still being internalized" on casts such as((n - m : Nat) : Int).#7942 updates to Cadical 3.0.1. While mixed on our checked in benchmarks, on SMT-LIB this was measured to be a general net-positive:
config status total solved sat unsat best timeout memout error uniq dis time_cpu memory no_kernel_new_cadical ee 46191 45195 17882 27313 17892 595 395 6 0 0 1077161.8 17933756.1 kernel_new_cadical ee 46191 45159 17890 27269 5220 642 380 10 7 0 1245494.4 27242333.1 no_kernel_old_cadical ee 46191 45141 17827 27314 18892 664 381 5 11 0 1187605.0 18032921.3 kernel_old_cadical ee 46191 45097 17833 27264 3950 715 367 12 3 0 1366219.3 27300968.9
#15838 makes
liaeliminate equations whose coefficients are all non-unit as in the Omega test, instead of a solved form scaled by the smallest coefficient. Chains of such equations, as produced by/and%definitions, no longer yield bounds with coefficients in the thousands and Cooper splits with as many cases.#15837 fixes a panic in the
liamodel search when a bound mentions a variable created after the first case split: the bound tightening indexed the divisibility constraints of the level-0 snapshot with that variable.#15836 fixes an internal
grinderror (mkEqProofinvoked with terms of different types) and missed solver equalities in equivalence classes merged viaHEq(e.g.,Fin nandFin mterms related bycast).#15835 makes
liareorder its variables instead of enumerating a Cooper case split with many cases, which fixes goals such as a three-limb counter increment that previously needed a2^32-way split.#15833 fixes a regression from #15827 where
liaenumerated all cases of a Cooper split although the untightened bounds refuted every case at once.#15832 makes
liaStepsalso bound the cases enumerated by Cooper and disequality splits inlia, so that a long enumeration stops at the threshold instead of producing a proof the kernel rejects.#15831 fixes a panic and infinite loop in
grind'sliamodel search.#15830 fixes a kernel error and missed proofs in
liawhen an integer term or inequality occurs in a dependent position, where thegrindpreprocessor cannot normalize it.#15829 fixes
grindkernel errors and internal errors when proving equalities between terms that contain binders, such as the preconditions of a function unfolded withgrind [f].#15827 makes
liasolve goals with large-modulus divisibility constraints, such as65536 ∣ 10 * x ⊢ 32768 ∣ x, without a Cooper case split per residue.#15826 fixes
liaexhaustingliaStepson goals where its rational model search looped on a divisibility constraint.#15825 fixes
grindproducing a proof the kernel rejects (decide (4 = 4) = false) when a numeral is written asOfNat.ofNat 4.#15823 fixes
grindproducing proofs that the kernel rejects when the sameFloatorFloat32value is written in different ways, such as2and2.0.#14398 implements
vcgen +jp, which verifies the code after anifor amatchonce instead of once per branch. Without+jp,vcgencopies that code into every branch, sokconsecutive splits give2ᵏcopies of it and its VCs. With+jp, VC generation grows linearly ink. The VCs of the shared code receive a hypothesis that states what each branch knows at its end, for example(n > 0 ∧ x = 1) ∨ (¬n > 0 ∧ x = 2).#15819 fixes a kernel error in
grindwhen it combines equations between constant functions and an equivalence class contains more than one lambda.#15812 fixes
liafailures on goals that mix/and%by the same power of two, such ast % 64 ≤ (64 * t + y) % 4096 / 64, whereomegasucceeds andliaexceededliaSteps.#15804 adds the
grindoptionmaxChar(default0). TheSym.simp-based normalizer now puts arithmetic terms in normal form only over types whose characteristic is unknown or at mostmaxChar, so terms overBitVec,Fin n,UIntN, andIntNare left as written by default, as the legacy normalizer does. Before,x - yoverBitVec 64becamex + 18446744073709551615 * y, which hid the subtraction from[grind =]rules keyed onx - yand from the translation ofBitVec/UIntNterms intoNat.#15803 fixes a
grindincompleteness where a lambda that occurs as an argument of two different functions never gets a function extensionality case split for the second one. For example,f (fun x => k x a) = f (fun x => k x b)witha = bnow closes even whenfun x => k x aalso occurs in a hypothesisg (fun x => k x a).#15802 makes
grindlearnp vfrom a term⟨v, h⟩ : {x // p x}, so facts about subtypes are usable even when the type of the stored proofhis only definitionally equal top v. For example, afterSubtype.forallnormalizes∀ x : {b // R a b}, q xto∀ b (h : R a b), q ⟨b, h⟩, the instance for⟨b, hab⟩withhab : diag R a bis now discharged.#15796 makes
vcgensubstitute a pure preconditionx = ton a local variablexinto the rest of the goal. The hypothesisx = tstays in the local context. For example, if the postcondition of a calllet r ← gsaysr = 41, then a spec forf 41applies to the next callf r. Verification conditions now showtwhere they showedxbefore. This feature is important to support for Iris' HeapLang example.#15773 fixes a
maxRecDepthfailure ofgrindwith theSym.simpnormalizer on hypotheses such asdecide (rc ≤ Int32.minValue + c) = false, and makes the normalizer produce the standard instance after rewriting underdecide.#15772 makes
grindwith theSym.simpnormalizer evaluateUSize.toNat nfor a numeraln < 2^32, so goals such as0 < (0x10000 : USize).toNatare closed as they are with the legacy normalizer.#15770 fixes
grindfailures with theSym.simpnormalizer on hypotheses such as(let j := k; fun s => s.2 = j) (a, b), a shape produced bymvcgenframes.#15767 fixes a kernel error of
grindwith theSym.simpnormalizer on goals such asi ≠ 0fori : BitVec (id 32).#15766 fixes a kernel error of
grindwith theSym.simpnormalizer on hypotheses such asa ≠ 1/2over a field of characteristic zero.#15765 fixes a kernel error of
grindwith theSym.simpnormalizer on goals such asz / (-0) = 0over a field.#15764 makes
simp +arithreport no change on anIntterm that is already in normal form, and makes bothgrindnormalizers keep an equation between a numeral and an atom in the orientation it was written, also when the numeral side is an expression such as2 * 3 - 7or(3 : Fin 5) + 4.#15763 makes
simp +arithand bothgrindnormalizers write the equationsx + -1 * y = 0andx + k = 0asx = yandx = -k. These were the documented normal forms, but inputs already of the shapep = 0were left alone, sox + 5 = 0andx + -1 * y = 0stayed as they were while2 * x = 2 * ybecamex = y.#15760 fixes a
simploop on a dependent∀ (h : p), q hwithp : Propwhen simplifyingpreturns a proof but leaves the term unchanged. This happens, for example, withsimp +arithwhenpcontainsIntarithmetic that is already in normal form, and it madegrindandliahitmaxRecDepthon hypotheses such as∀ (k : ℕ) (x : X k), …afterSubtype.forallbecame agrindnormalization rule.#15753 makes the
Sym.simp-basedgrindnormalizer (backward.grind.normalizer := false) eta-reduce the lambda arguments of an application before their bodies are simplified, soid (fun x => Nat.succ x) = id Nat.succcloses: the lambda becomesNat.succinstead offun x => x + 1, which nothing could relate to the unappliedNat.succ. The legacy normalizer closed such goals througheq_selfup to definitional equality, whichSym.simpdoes not use.#15725 removes the rebuild of the
Sym.simpnormalization theorem set on every pattern normalization ingrind. Withbackward.grind.normalizer := false, every[grind]attribute application and every theorem referenced byinstantiate/finishpaid a full conversion of the[grind norm]set (grind_ite_tracetimed out).#15748 adds
Subtype.forallandSubtype.existsto thegrindnormalization rules, so a hypothesis∀ α : {a // p a}, q αbecomes∀ a, p a → q ⟨a, _⟩. Sincegrindsplits subtype binders eagerly, the goal never containsSubtype.valterms, and the original E-matching patternSubtype.val ?αof such a hypothesis could not be instantiated.#15745 fixes
grindnot introducing the hypotheses of an implication or universal quantifier when the goal type is wrapped inExpr.mdata, as it is after ahave(noImplicitLambda). The goal was negated as a whole instead, so a hypothesis¬(p → q)reached the normalizer and the solvers.#15703 fixes a
grindfailure with theSym.simpnormalizer (backward.grind.normalizer false) on goals such as the one ingrind_9216: a negated existential¬∃ a, (p a ∨ q a) ∧ ∃ b, r a bmust become two universally quantified facts, one per disjunct, so that each gets its own E-matching pattern.Sym.simpleft it as a single∀ a b, …with a disjunction in the body.#15701 fixes a
grindfailure, "error while initializing arithmetic operators", triggered by theSym.simpnormalizer (backward.grind.normalizer false) on a semiring whose synthesizedNatCastinstance is not reducibly defeq to thenatCastfield of itsGrind.Semiringinstance, even when the goal contains no casts.
Compiler
#16520 fixes various file descriptor leaks and makes
io.cppmore resistant againsterrnobeing changed byclose.#14954 speeds up
Nat.shiftLefton small values by computing the result directly on machine words instead of always going through GMP, which removes three heap allocations per shift and makes7 <<< 4roughly as cheap as the other nativeNatoperations.#16515 fixes a segfault when throwing
IO.Error.unexpectedEofinmain.#16510 implements special support in the compiler for emitting Nat literals between 2^32 and 2^64 (support for up to 2^32 is pre-existing).
#16357 bumps the libuv version to 1.53.0 across all platforms.
#16376 makes
LEAN_STACK_SIZE_KBalso apply to the libuv event loop thread.#16363 updates OpenSSL to the latest available version on every platform.
#15586 adds a
Runtime.deepCopyoperation. It traverses an object graph, copying everything along the way.#16276 fixes a memory leak in compiled code when a string or large
Natliteral that is not extracted as a closed term, for example underset_option compiler.extract_closed false, is passed to a join point whose parameter is only read.#15779 makes
IO.appPathwork in PID namespaces that share their parent's/procmount, such as sandboxes and rootless containers.#16251 makes violations of linearity markers optionally print backtraces.
#16213 checks allocation failures inside of the olean compactor. In doing so it also allocates the buffer with Lean's allocator as opposed to fixing it to
malloc.#16195 makes the default thread stack size 8MB on all 32-bit targets, not only on Emscripten, fixing a regression from #12971. A 32-bit process does not have the address space for 1GB per thread, so spawning tasks aborts with
failed to create thread: Resource temporarily unavailable.#16211 fixes compilation of pattern matching on USize.
#16137 fixes the exit code of
leanon 32-bit targets such as WebAssembly (wasm32) and i386 after options like--version,--helpand--deps, after an unknown option or an invalid argument, when called without a file name, and after--run. In these casesleanexited with a code derived from a heap address instead of 0, 1 or the exit code of the program'smain; a run that processes a file without--runwas not affected, because it ends withIO.Process.exit.#16090 fixes eight FFI functions whose definitions took one parameter more, or one fewer, than the generated C passes. On WebAssembly, unless both Lean's C++ code and the generated C were compiled with LTO, wasm-ld reported a
function signature mismatchfor each, and calls to them trapped. Every Lean program contains calls to two of them,lean_io_create_tempfileandlean_io_create_tempdir, behindIO.FS.createTempFileandIO.FS.createTempDir; theLeanlibrary calls the other six.#16153 makes the IR interpreter evaluate
USize,UInt64andArray.uget/usetprimitives in place instead of calling their boxed native wrappers. A full Mathlib build executes 3.7% fewer instructions.#16148 speeds up the IR interpreter's callee lookup. Mathlib: -1.8% instructions in total, up to -8.5% on individual files.
#16049 fixes quadratic compilation behavior for large list literals.
#16023 makes
isExclusiveUnsafesafe to call with scalars and marks bothisExclusiveUnsafeandptrAddrUnsafeasnever_extract. We say that scalars are unique as they, by definition, cannot be shared.#15950 fixes a small number of issues in the non-GMP mpz implementation.
#15816 fixes the scalar fields of static objects, such as the hashes of name literals, on 32-bit targets such as wasm32-wasip1 and i686, by choosing the form of
LEAN_SCALAR_PTR_LITERALby pointer size instead of byLEAN_EMSCRIPTEN.#15890 makes evaluating a thunk that is shared between threads, or reachable from the imported environment, no longer count toward the heartbeats of the thread that forces it. Which thread first forces such a thunk depends on scheduling, so counting its evaluation made heartbeat counts, and thus
maxHeartbeatserrors, nondeterministic. Evaluating a thread-local thunk still counts as before.#15774 upgrades LLVM from 23.1.1 to 23.1.3. Incidentally it's also the first LLVM upgrade to use our new LLVM builds based on RHEL. This makes it compatible with older glibc releases than before.
FFI
#15957 deletes the unused and unsafe
lean_utf8_strlenfunction, which can read past a NUL-terminated buffer on truncated UTF-8 input.#15980 removes the obsolete
lean_string_datadeclaration and its C++ wrapper from thesrcheaders. The function implementation had been removed, but not the declaration.
Server
#16314 replaces the earlier distinction between text tokens found in docstring and non-docstring Verso content with the consistent use of the
documentationmodifer for all markup tokens that occur in docstrings. This makes it easier for editors to match a wider variety of themes.#15550 adds an
#htmlcommand that displays HTML values in the infoview (as widget messages).#13674 adds semantic tokens for Markdown and Verso that correspond to those available in editor themes for Markdown. With a small update to editors, docstrings can be consistently formatted without needing to reimplement either complex parser client-side.
#15846 adds folding range support for proofs that serve as the body of a declaration.
Lake
#16514 passes
LEAN_NUM_THREADSto relevant Lean based child processes of comparator.#16351 adds the package configuration option
downloadCacheService. Lake uses this service as the default for alake cache getof the package. Even without alake cache get, if the artifact cache is enabled, Lake will automatically download outputs and artifacts from the service on demand during a package build.#16475 ensures the target
ltarfile is removed beforeleantaris run. Theltarmay be read-only if restored from the cache, in which caseleantarwill fail to overwrite it on Windows.#16471 prevents current fetches from overriding jobs in the build store and ensures that fetches always obtain the same job from the build store.
#16470 fixes an issue where new build outputs could be associated with a stale trace if a build output new artifacts, failed, and then its source changes where reverted. Lake now always removes the trace before running a build action.
#16472 fixes a few places where errors where not properly wrapped into the job associated with a facet.
#16461 ensures downloaded artifacts are written to the cache automatically. In particular, on-demand artifacts now use a temporary file for their download before being stored as their final name (as
lake cache getdownloads already do).#16457 makes a module build fail if its source file changed while the build was running (i.e., between import calculation and the end of elaboration). This mitigates the chance of concurrent edits leading to a invalid builds. For example, previously, editing a file while a build was running could lead to a trace which mapped the unedited file to the edited file's build results, producing a poisoned build store.
#16439 fixes a bug where Lake would keep outdated
.hashfiles when unpacking.ltararchives because it did not clear the hashes along with the artifacts before unpacking. To avoid such mistakes in the future,clearOutputArtifactsandclearIROutputArtifactsnow delete the hashes along with the artifacts.#16086 changes Lake's build store to use a
Std.Mutexinstead of aIO.Reffor mutation.#16302 adds the ability to specify Lake cache services from within a package via a new
cache_serviceTOML table or Lean DSL declaration. These services can then be used vialake cache get --service. Uploading (i.e.,putorput-unstaged) does not support package-specified services . There can only be one service per name, and a package's services take precedence over their dependencies. Services configured in the system configuration take precedence over all package-specified services.#15861 makes file writes to the cache atomic. Previously, a racing reader could observe a partially written artifact.
#16121 fixes an issue with
CacheMap.writeFilewhere it would truncate the file before locking it.#14725 makes
lake cache getandlake cache putretry a transfer that fails in a transient way, such as a dropped connection or a corrupted download. Previously, one such failure made the whole command fail. Lake now attempts each transfer at most 3 times.#15805 computes Lake's transitive import closure first from a single snapshot of the build store, falling back to the real build store only when an artifact is missing. This decreases contention on the main build store, whose fetches otherwise must be atomic.
#16096 adds more explicit documentation on the assumptions and guarantees provided by comparator.
#16083 adds a new Lake benchmark that measures the performance of computing module setups. This computation walks the transitive import graph and thus scales with the size of the import closure. Experiments have shown this to be a significant bottleneck for scalability in projects with thousands of modules.
#15894 fixes
lake update --keep-toolchainso that a revision pinned in the root package's ownrequiretakes priority over one locked in another dependency's manifest, as it already does without the flag. Previously, the root's entry could be replaced by the dependency's older revision and marked as inherited.#16019 introduces support for a
--jsonflag onlake comparatorandlake check. When passed the commands will print one final JSON report to stdout instead of reporting continous progress. The JSON format is versioned and should be easily machine consumable. The format itself is specified by theToJsonandFromJsoninstances on the typesLakeComparatorReportandLakeCheckReport.#15775 forces definition holes in comparator to either be a
sorryor a lambda with asorrybody. This forces challenges to be in a more canonical form where a challenge can never rely on a definition hole having a particular value already.#15762 makes
lake checkcheck the project's axioms before running the kernels, aslake comparatoralready does. Previously, with--paranoid, a project using a non-standard axiom (e.g. vianative_decide) was rejected only by an external checker, sometimes with an obscure failure such as ananodapanic, and the report naming the unpermitted axiom was never shown.
Other
#16473 updates bundled
lean-beamwith speculative profiling and improvements to Lean language server compatibility, cancellation, and error reporting.#16349 improves the error message when Lean fails to load a .olean because of e.g. the memory mapping limit on Linux.
#16107 fixes a quadratic slowdown in the kernel when checking terms that contain long chains of the same application, such as
"ff…f" = String.ofList (List.replicate n 'f').#14362 makes importing modules substantially cheaper by replacing the imported-constants hash maps, which every import rebuilt from scratch, with per-module prefix trees that are written into the oleans and merged lazily on first access. On Mathlib, the build takes 3.0% less wall-clock time, importing all of Mathlib 3.4% less CPU time and 128 MB less memory, and the time spent importing during the build drops by 36%, at the cost of 1.1% larger olean files.
#15853 makes
Kernel.Environment.replayaddString.ofListandChar.ofNat(if present) before any other constant. The kernel unfolds string literals toString.ofList [Char.ofNat n, …], but these constants are not syntactic dependencies of a declaration that reduces a string literal. So replay, which orders declarations only by their syntactic dependencies, could check such a declaration first and wrongly reject it, for exampletheorem t1 : "abc" ++ "def" = "abcdef" := by decide