Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[Bug][Prover] loop invariants of for loops are not intuitive #15022

Open
rahxephon89 opened this issue Oct 20, 2024 · 0 comments
Open

[Bug][Prover] loop invariants of for loops are not intuitive #15022

rahxephon89 opened this issue Oct 20, 2024 · 0 comments
Labels
bug Something isn't working move-prover stale-exempt Prevents issues from being automatically marked and closed as stale

Comments

@rahxephon89
Copy link
Contributor

🐛 Bug

loop1 and loop2 are functionally equivalent but the loop invariant in the for loop cannot be proved because of the way how it is rewritten into a while loop. To avoid confusion for users, we need to improve documentation.

      fun loop1 (xs: &vector<u8>): vector<u8> {
        let r = vector<u8>[];
        for (
            i in 0..vector::length(xs)
            spec { invariant i == len(r); } // cannot be proved because of how i it is updated
        )
        {
            vector::push_back(&mut r, *vector::borrow(xs, i));
        };
        r
    }

    fun loop2 (xs: &vector<u8>): vector<u8> {
        let r = vector<u8>[];
        let i = 0;
        while ({
            spec { invariant i == len(r); }; // can be proved
            i < vector::length(xs)
        })
        {
            vector::push_back(&mut r, *vector::borrow(xs, i));
            i = i + 1
        };
        r
    }
@rahxephon89 rahxephon89 added bug Something isn't working move-prover labels Oct 20, 2024
@brmataptos brmataptos added the stale-exempt Prevents issues from being automatically marked and closed as stale label Oct 31, 2024
@brmataptos brmataptos moved this from 🆕 New to For Grabs in Move Language and Runtime Nov 14, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working move-prover stale-exempt Prevents issues from being automatically marked and closed as stale
Projects
Status: For Grabs
Development

No branches or pull requests

2 participants