Compare commits

...

3 Commits

Author SHA1 Message Date
Mac Malone
8156373037 fix: pass CMake Lake args to the Lake make build (#13410)
This PR fixes a bug in #13294 where the Lake arguments were not actually
passed to the Lake make build.
2026-04-14 22:07:29 +00:00
Sebastian Graf
75487a1bf8 fix: universe normalization in getDecLevel (#13391)
This PR adds level instantiation and normalization in `getDecLevel` and
`getDecLevel?` before calling `decLevel`.

`getLevel` can return levels with uninstantiated metavariables or
un-normalized structure, such as `max ?u ?v` where the metavariables
have already been assigned. After instantiation and normalization (via
`normalizeLevel`), a level like `max ?u ?v` (with `?u := 1, ?v := 0`)
simplifies to `1 = succ 0`, which `decLevel` can decrement. Without this
step, `decLevel` sees `max ?u ?v`, tries to decrement both arms, fails
on a zero-valued arm, and reports "invalid universe level".

Concretely, this fixes `for` loops with `mut` variables of
sort-polymorphic type (e.g. `PProd Nat True`) where the state tuple's
universe level ends up as an uninstantiated `max`.

The expected-output change in `doNotation1.lean` is because the `for`
loop's unit type now resolves to `Unit` instead of `PUnit` due to the
improved level handling.
2026-04-14 21:27:22 +00:00
Henrik Böving
559f6c0ae7 perf: specialize qsort properly onto the lt function (#13409) 2026-04-14 19:57:30 +00:00
6 changed files with 26 additions and 9 deletions

View File

@@ -118,6 +118,7 @@ option(USE_LAKE "Use Lake instead of lean.mk for building core libs from languag
option(USE_LAKE_CACHE "Use the Lake artifact cache for stage 1 builds (requires USE_LAKE)" OFF)
set(LEAN_EXTRA_OPTS "" CACHE STRING "extra options to lean (via lake or make)")
set(LEAN_EXTRA_LAKE_OPTS "" CACHE STRING "extra options to lake")
set(LEAN_EXTRA_MAKE_OPTS "" CACHE STRING "extra options to leanmake")
set(LEANC_CC ${CMAKE_C_COMPILER} CACHE STRING "C compiler to use in `leanc`")
@@ -127,7 +128,7 @@ string(APPEND LEAN_EXTRA_OPTS " -Dbackward.do.legacy=false")
# option used by the CI to fail on warnings
option(WFAIL "Fail build if warnings are emitted by Lean" ON)
if(WFAIL MATCHES "ON")
string(APPEND LAKE_EXTRA_ARGS " --wfail")
string(APPEND LEAN_EXTRA_LAKE_OPTS " --wfail")
string(APPEND LEAN_EXTRA_MAKE_OPTS " -DwarningAsError=true")
endif()

View File

@@ -33,6 +33,7 @@ if necessary so that the middle (pivot) element is at index `hi`.
We then iterate from `k = lo` to `k = hi`, with a pointer `i` starting at `lo`, and
swapping each element which is less than the pivot to position `i`, and then incrementing `i`.
-/
@[inline]
def qpartition {n} (as : Vector α n) (lt : α α Bool) (lo hi : Nat) (w : lo hi := by omega)
(hlo : lo < n := by omega) (hhi : hi < n := by omega) : {m : Nat // lo m m hi} × Vector α n :=
let mid := (lo + hi) / 2
@@ -44,7 +45,7 @@ def qpartition {n} (as : Vector α n) (lt : αα → Bool) (lo hi : Nat) (w
-- elements in `[i, k)` are greater than or equal to `pivot`,
-- elements in `[k, hi)` are unexamined,
-- while `as[hi]` is (by definition) the pivot.
let rec loop (as : Vector α n) (i k : Nat)
let rec @[specialize] loop (as : Vector α n) (i k : Nat)
(ilo : lo i := by omega) (ik : i k := by omega) (w : k hi := by omega) :=
if h : k < hi then
if lt as[k] pivot then

View File

@@ -69,12 +69,16 @@ def decLevel (u : Level) : MetaM Level := do
/-- This method is useful for inferring universe level parameters for function that take arguments such as `{α : Type u}`.
Recall that `Type u` is `Sort (u+1)` in Lean. Thus, given `α`, we must infer its universe level,
and then decrement 1 to obtain `u`. -/
instantiate and normalize it, and then decrement 1 to obtain `u`. -/
def getDecLevel (type : Expr) : MetaM Level := do
decLevel ( getLevel type)
let l getLevel type
let l normalizeLevel l
decLevel l
def getDecLevel? (type : Expr) : MetaM (Option Level) := do
decLevel? ( getLevel type)
let l getLevel type
let l normalizeLevel l
decLevel? l
builtin_initialize
registerTraceClass `Meta.isLevelDefEq.step

View File

@@ -54,7 +54,7 @@ ifeq "${USE_LAKE}" "ON"
# build in parallel
Init:
${PREV_STAGE}/bin/lake build -f ${CMAKE_BINARY_DIR}/lakefile.toml $(LAKE_EXTRA_ARGS)
${PREV_STAGE}/bin/lake build -f ${CMAKE_BINARY_DIR}/lakefile.toml ${LEAN_EXTRA_LAKE_OPTS} $(LAKE_EXTRA_ARGS)
Std Lean Lake Leanc LeanChecker LeanIR: Init

View File

@@ -0,0 +1,11 @@
/-!
Test that `for` loops with `mut` variables of sort-polymorphic type (e.g. `PProd`) work correctly.
`PProd Nat True : Sort (max 1 0)` has a `Prop` component, so `getDecLevel` must see the fully
instantiated and normalized level `1` rather than `max ?u ?v` with unresolved metavariables.
-/
def foo : Unit := Id.run do
let mut x : PProd Nat True := 0, trivial
for _ in [true] do
x := 0, trivial
break

View File

@@ -49,7 +49,7 @@ doNotation1.lean:78:21-78:31: error: typeclass instance problem is stuck
Note: Lean will not try to resolve this typeclass instance problem because the type argument to `ToString` is a metavariable. This argument must be fully determined before Lean will try to resolve the typeclass.
Hint: Adding type annotations and supplying implicit arguments to functions can give Lean more information for typeclass resolution. For example, if you have a variable `x` that you intend to be a `Nat`, but Lean reports it as having an unresolved type like `?m`, replacing `x` with `(x : Nat)` can get typeclass resolution un-stuck.
doNotation1.lean:82:0-83:9: error: Type mismatch. `for` loops have result type PUnit, but the rest of the `do` sequence expected List (Nat × Nat).
doNotation1.lean:82:0-83:9: error: Type mismatch. `for` loops have result type Unit, but the rest of the `do` sequence expected List (Nat × Nat).
doNotation1.lean:83:7-83:9: error: Application type mismatch: The argument
()
has type
@@ -59,8 +59,8 @@ but is expected to have type
in the application
pure ()
doNotation1.lean:82:0-83:9: error: Type mismatch
PUnit.unit
()
has type
PUnit
Unit
but is expected to have type
List (Nat × Nat)