Assume loop conditions in loop bodies with sound loop havoc - #320
Open
CatarinaGamboa wants to merge 3 commits into
Open
CatarinaGamboa wants to merge 3 commits into
CatarinaGamboa wants to merge 3 commits into
Conversation
The condition of a while/for loop is now assumed in its body as a path
condition, like the condition of an if, so `while (n > 0) use(n)` verifies.
Loops were previously checked as if the body ran exactly once with the
pre-loop values, and the for update was visited before the body. To keep
the new assumption sound, a loop is now checked for one arbitrary
iteration:
- variables written in the loop are havocked (keep only their declared
refinement, which every write re-checks) before the loop and after it;
- for loops visit init, condition, body, then update;
- do-while does not assume the condition in the body;
- path conditions added inside a loop (its condition, `if (..) break;`)
are dropped after it;
- conditions that write variables (e.g. `(n = read()) > 0`) assume nothing.
Also drop path conditions on a variable when it is incremented or
decremented (`i++`), as already done for assignments: before,
`if (i < 10) { i++; use(i); }` wrongly assumed `i < 10` for the new value.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Review fixes for the loop-condition change (#306): - a continue reaches the for update without the rest of the body, so when the body has one, the update no longer sees the body's path conditions or assignments (`for (..; ..; use(n)) { if (n <= 0) continue; ... }` was accepted) - a loop also changes fields (through any call) and the state of objects it calls state-changing methods on; these are now havocked too, since the assumed condition could otherwise combine with their stale values (accepted programs that main rejected) - drop the null check on the condition, dead since null literals carry no information (#311) - move the i++ path-condition fix out (it is not needed for loops and is a separate pre-existing bug in if branches) Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
rcosta358
approved these changes
Oct 2, 2026
rcosta358
left a comment
Collaborator
There was a problem hiding this comment.
Really liked the havoc approach!
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Problem
The verifier checked a loop body using values from before the loop. It could miss errors in later iterations and carry one iteration's facts past the loop. It also checked a
forupdate before the body.Example
Here
x0,x1, etc. are symbolic versions of the same Java variable:x1 = 1is reachable: the successive loop-entry values are 3, 2, then 1. The previous verifier checked the body using the initial value 3 and accepted the program. The freshx1keeps onlyx's declared refinement, so this later iteration is now checked.Change
whileorforguard in the body when it has no direct variable writes.forinitialization, condition, body, and update in execution order; account forcontinue. Handledoand for-each loops conservatively.!guardafter exit, sincebreakcan leave while the guard is true. This loses precision but avoids an invalid assumption.Tests cover later iterations, guard facts, loop order,
continue,break, fields, and typestate.mvn testpasses.Known existing limit: alias and
thistypestate changes can still be accepted incorrectly. This PR addresses the loop reasoning above; it does not establish soundness for those cases.Fixes #306.