Skip to content

SMT preprocessing throws on Nat-valued fields over a Fin n domain #173

Closed

Description

@Qubut

At rev 5744772 with veil.smt.trust false, SMT preprocessing throws, rather than returning a verdict, on action-preservation goals of a module with Nat-valued fields over a Fin n domain:

  • incorrect number of universe levels Nat.cast
  • an application type mismatch in the Int.toNat_of_nonneg congruence

Example invariant that triggers it: ∀ id : Fin maxId, coverage id ≤ 3, with function coverage : Fin maxId → Nat and actions that set coverage id to a value in 0..3.

All 16 action-preservation goals of a 4-action, 4-invariant module throw this way. The same goals close in Lean with prove_veil_invariant_goal … using wp by grind, so they are valid. The initialisation goals go through SMT without error.

A minimal reproducer is the module above. I can reduce it further if that helps.

Activity

  1. dranov commented on Nov 10, 2026

    @dranov
    Collaborator

    @Qubut This is an issue in lean-smt, on which we depend.

    I had a PR a while ago, but it seems to have fallen through the cracks: ufmg-smite/lean-smt#229

    If this is a blocker for you, I recommend reviving that line of work upstream.

  2. Qubut commented on Nov 11, 2026

    @Qubut
    Author

    Thanks for the pointer. I ported lean-smt#229 (4513f21) onto the lean-smt revision this Veil pin uses (verse-lab/lean-smt v4.35.0-veil-no-mathlib at 293dab6) and reran the module. It fixes the first error but not the second, so these goals still fail.

    Port. The cherry-pick conflicts with the fork's module/EmbeddingConfig changes in Smt.lean and Smt/Preprocess/Embedding.lean. I kept the fork's config and gated the PR's isFinType by embedNat, and converted the new files to module. Smt and Veil then build.

    Result. 15 action-preservation goals with veil_smt (the 16th is closed by the weakest precondition alone):

    • 293dab6: 15 × incorrect number of universe levels Nat.cast
    • 293dab6 + #229: 15 × an application type mismatch in implies_congr_ctx

    Minimal case (patched build):

    theorem b3 (n : Nat) (p : Fin n → Bool) : ∀ i : Fin n, p i = true → (i : Nat) < n := by smt
    Application type mismatch: The argument
      fun a => Eq.trans Smt.Preprocess.Embedding.forall_fin_as_int._simp_1 (forall_congr fun x => forall_prop_domain_congr (congrArg (And (0 ≤ x)) (congrArg (LT.lt x) (Int.toNat_of_nonneg a))) fun h => ...
    has type
      ∀ (a : f ≥ 0), (∀ (f_1 : Fin f.toNat → Bool) (i : Fin f.toNat), f_1 i = true → ¬↑i < f.toNat → False) = ∀ (a_1 : Fin f.toNat → Prop) (a_2 : Int) (a_3 : 0 ≤ a_2 ∧ a_2 < f), a_1 (Smt.Preprocess.Embedding.ofIntFin f.toNat a_2 ⋯) → ¬a_2 < f → False
    but is expected to have type
      f ≥ 0 → ?q₁ = ?q₂
    in the application
      implies_congr_ctx (Eq.refl (f ≥ 0)) fun a => ...
    

    The PR's own tests use literal bounds (Fin 4), and those pass. With a symbolic bound, the rewrite of ↑(f.toNat) to f by Int.toNat_of_nonneg uses the nonnegativity hypothesis a that the Nat embedding introduces. The cast of the ofIntFin proof argument then mentions a, and the congruence implies_congr_ctx cannot take a right-hand side that depends on it. This is read from the error, not confirmed in the code.

    Related cases on the same patched build:

    • (n : Nat) (x : Fin n) : (x : Nat) < n passes;
    • (n) (p : Fin n → Bool) : ∀ i : Fin n, p i = p i gives cvc5 … Symbol 'n' not declared as a type;
    • (n) (c : Fin n → Nat) : ∀ i : Fin n, c i ≤ c i gives cannot translate #0.

    I'll try a fix for symbolic bounds in lean-smt and report back here.

  3. Qubut commented on Nov 11, 2026

    @Qubut
    Author

    Opened a PR for this: verse-lab/lean-smt#4. It ports #229 to the veil branch and also handles Fin n when n is a variable. With it my module above goes through veil_smt with trust off.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions