fix: decide inductive predicates up to universe normalization This PR makes the inductive checker test a resulting universe for zero up to normalization, so that `Sort (imax 1 0)` and `Sort 0` describe the same inductive type. The two spellings previously disagreed on whether a constructor field may carry data, on whether the recursor eliminates only into `Prop`, and on whether the type is a K-like reduction target. Only declarations produced with metaprogramming are affected, since the elaborator normalizes levels before the kernel sees them. `nanoda` decides all three semantically, so it and the kernel disagreed on these declarations. It derives recursors and checks them against the export rather than trusting it, so a disagreement about the elimination level makes it reject an export the kernel accepted. This widens what the kernel accepts, but it is not a soundness fix: the syntactic tests all erred in the restrictive direction, rejecting declarations that are in fact sound.
diff --git a/src/kernel/inductive.cpp b/src/kernel/inductive.cpp index 04bee7d..140a916 100644 --- a/src/kernel/inductive.cpp +++ b/src/kernel/inductive.cpp
@@ -436,7 +436,7 @@ // the sort is ok IF // 1- its level is <= inductive datatype level, OR // 2- is an inductive predicate - if (!(is_geq(m_result_level, sort_level(s)) || is_zero(m_result_level))) { + if (!(is_geq(m_result_level, sort_level(s)) || normalizes_to_zero(m_result_level))) { throw kernel_exception(m_env, sstream() << "universe level of type_of(arg #" << (i + 1) << ") " << "of '" << n << "' is too big for the corresponding inductive datatype"); } @@ -514,7 +514,7 @@ expr fvar = mk_local_decl_for(type); if (i >= m_nparams) { expr s = tc().ensure_type(binding_domain(type)); - if (!is_zero(sort_level(s))) { + if (!normalizes_to_zero(sort_level(s))) { /* Current argument is not in Prop (i.e., condition 1 failed). We save it in to_check to be able to try condition 2 above. */ to_check.push_back(fvar); @@ -554,7 +554,7 @@ In the following for-loop we check if the intro rule has 0 fields. */ m_K_target = m_ind_types.size() == 1 && /* It is not a mutual declaration (for simplicity, we don't gain anything by supporting K in mutual declarations. */ - is_zero(m_result_level) && /* It is an inductive predicate. */ + normalizes_to_zero(m_result_level) && /* It is an inductive predicate. */ length(m_ind_types[0].get_cnstrs()) == 1; /* Inductive datatype has only one constructor. */ if (!m_K_target) return;
diff --git a/tests/elab/kernelImaxPropInductive.lean b/tests/elab/kernelImaxPropInductive.lean new file mode 100644 index 0000000..22d2386 --- /dev/null +++ b/tests/elab/kernelImaxPropInductive.lean
@@ -0,0 +1,41 @@ +import Lean.CoreM +import Lean.AddDecl + +/-! +The inductive checker must decide "is this an inductive predicate?" up to level +normalization, so that `Sort (imax 1 0)` and `Sort 0` are treated identically. +-/ + +open Lean + +private def imaxProp : Expr := .sort (.imax (.succ .zero) .zero) + +-- A data field is allowed because the type is an inductive predicate. +#eval show CoreM Unit from + addDecl <| .inductDecl [] 0 [ + { name := `KIPData + type := imaxProp + ctors := [{ name := `KIPData.mk + type := .forallE `b (.const ``Bool []) (.const `KIPData []) .default }] } + ] false + +-- Nullary single constructor, once as `Sort (imax 1 0)` and once as `Sort 0`. +#eval show CoreM Unit from do + addDecl <| .inductDecl [] 0 [ + { name := `KIPUnit, type := imaxProp + ctors := [{ name := `KIPUnit.mk, type := .const `KIPUnit [] }] }] false + addDecl <| .inductDecl [] 0 [ + { name := `KIPUnit0, type := .sort .zero + ctors := [{ name := `KIPUnit0.mk, type := .const `KIPUnit0 [] }] }] false + +-- The data field keeps the recursor in `Prop`; it is not an index. +#eval show CoreM Unit from do + let .recInfo v ← getConstInfo `KIPData.rec | throwError "not a recursor" + unless v.levelParams.isEmpty do throwError "expected `Prop`-only elimination" + +-- Both spellings agree on K-like reduction and on the elimination level. +#eval show CoreM Unit from do + let .recInfo v ← getConstInfo `KIPUnit.rec | throwError "not a recursor" + let .recInfo v0 ← getConstInfo `KIPUnit0.rec | throwError "not a recursor" + unless v.k == v0.k && v.levelParams.length == v0.levelParams.length do + throwError "kernel treats `Sort (imax 1 0)` differently from `Sort 0`"