Topic · Loop invariant

What is a loop invariant, and how do I keep it true in CI?

Gist

A loop invariant is a property true before and after every iteration. Proof fails proof verify-lemma --solver z3,cvc5 --tags reqproof_proof ./... unless each // reqproof:invariant on the Go discharges establishment, preservation, and use.

proof verify-lemma --solver z3,cvc5 --tags reqproof_proof ./...

Keep go test if you already exercise the loop. Keep Wikipedia if you already teach the glossary. Keep Dafny or SPARK if you already write a verification language. Keep Jama if you author shalls. Proof will not count a green unit test as those three obligations. Jama still authors.

01 · The green loop is not the invariant

A unit test that walked the slice once is not a proof the property held on every iteration.

The accumulator returned a non-negative sum on the fixture. The suite still reads green. The index bound was never stated. An off-by-one on a longer slice is still SAT.

Wikipedia, Cornell CS 2112, GeeksforGeeks, and Stack Overflow define the same act: a condition that holds immediately before and immediately after every iteration. That sits next to Hoare logic on the glossary. Proof does not replace that act. It asks a narrower question: if you wrote a lemma over a production for, did you name the property at the loop's top, and did Z3 or cvc5 discharge the three obligations, or only run the fixture once?

The motivating miss is mechanical. SumPositive walks a slice and adds the positives. The test feeds []int{1, 2, 3} and asserts the sum is 6. Review is performed. The audit reports clean. The translator still cannot reason about the loop. Without // reqproof:invariant it surfaces E_FOR_LOOP_NO_INVARIANT. With a weak invariant it returns SAT and a counterexample. A green fixture never saw that model.

The command is deterministic. It does not call a model. It does not invent the invariant. It refuses a silent pass when a lemma body contains a for and the three Hoare obligations are missing or SAT.

proof verify-lemma --solver z3,cvc5 --tags reqproof_proof ./...
proof help loop-invariants

The first command is the lemma gate. The second is the directive grammar. Green coverage after a loop that never named 0 <= i && i <= len(items) is how the index stayed unproved.

02 · The exhibit

Same accumulator. A green fixture, or these three obligations.

sum_nonneg still claims SumPositive(items) >= 0. The loop never named the bound. Click the tabs.

CI / fixture

  • Input []int{1, 2, 3} → 6
  • Credit sum_nonneg marked covered via go test
  • Loop no // reqproof:invariant, E_FOR_LOOP_NO_INVARIANT if you ask Z3
Suite closed

These three obligations

No establishment. No preservation. No use. The solver never saw the loop's top.

No invariant

CI / fixture

Still the three positives. Still a green log. Keep the unit test.

Keep the fixture

Proof

  • Ask establishment ∧ preservation ∧ use on SumPositive
  • Out PROVED (z3) or SAT with a model, never a silent skip
A green walk is not those three

Same accumulator. A green fixture, or these three obligations. Click the tabs.

What the record lists What Proof actually does What a green cell is not
Unit test Keep it. A lemma still wants a fixture that can fail for a reason you can read Not establishment. One walk is not every iteration.
Directive // reqproof:invariant <expr> on the for, combined with implicit AND if you write several Not a comment the compiler ignores. Without it the translator emits E_FOR_LOOP_NO_INVARIANT.
Establishment The invariant holds at entry, under pre-loop bindings and the init clause Not a postcondition you wrote after the closing brace.
Preservation inv ∧ cond ⇒ inv' after one body step. SAT here is a counterexample, not a skip Not k-induction. Kind2 still owns traces.
Use On exit, the solver may assume invariant and ¬cond. UNSAT means all three plus the lemma hold Not a proof of the rest of the program. Jama still authors.

The directive looks like this on the production function:

// reqproof:lemma sum_nonneg func(items []int) bool {
//   return SumPositive(items) >= 0
// }
func SumPositive(items []int) int {
    sum := 0
    for i := 0; i < len(items); i++ {
        // reqproof:invariant sum >= 0
        // reqproof:invariant 0 <= i
        // reqproof:invariant i <= len(items)
        if items[i] > 0 {
            sum = sum + items[i]
        }
    }
    return sum
}

3-clause for and while-form are supported. Range-form is collected and then rejected with a clear error. Nested loops, map iteration, break, continue, and early return are not yet supported. goto, defer, go, and channel sends are rejected at scan time.

We have not run Dafny, SPARK, Frama-C, and Proof on the same frozen corpus, and we have not scored this lemma as a proof of the rest of the program. The loss is named, not scored.

03 · The honest loss

A PROVED lemma is not a loop-invariant generator.

The command refuses a silent pass. Proof will not pretend that a green fixture is establishment, or that a Go comment is Dafny.

go test still owns the fixture. Wikipedia still owns the glossary. Dafny, SPARK, and Frama-C still win at a verification language with a type system for this. Jama still authors the shall. Proof stores the lemma next to the Go and fails a silent pass when the for has no invariant, or when any of the three obligations is SAT. It does not invent the expression. It does not implement k-induction. You cannot set k.

Proof is not Dafny. It is not SPARK. It is not Why3. Jama still authors. VectorCAST or LDRA still win at a qualified C toolchain.

A Z3 lemma on a function without a loop still lives on Z3 / Kind2 on one function. Kind2's base-plus-step engine still lives on k-induction. Index panics without a loop still live on proof verify-safety, not this H1.

04 · Nearby questions

What people type next.

What is a loop invariant? A property true before and after every iteration. Wikipedia and Cornell still win that glossary. proof verify-lemma is the Hoare floor after you named the property on the Go.

Is Proof an alternative to Dafny or SPARK? No. Keep the verification language if you already write one. Proof checks a Go lemma with an explicit invariant. Jama still authors.

Does a green unit test count? No. One walk of the slice is the fixture. Establishment, preservation, and use are the lemma.

Is this k-induction? No. That H1 lives on k-induction. Proof asks Kind2. Proof does not implement k-induction, and you cannot set k.

How do I prove a function with Z3 when there is no loop? That H1 lives on Z3 / Kind2 on one function. This page is the loop's three obligations, not that cluster.