Skip to content
master
Switch branches/tags
Code

Latest commit

888: use `old` in trigger for direct array assignments r=vakaras a=Pointerbender

This PR experiments with addressing 2 things:

1. It implements the suggested work-around for #877 together with a regression test (the test suite indicated no regressions locally).
2. The `selection_sort.rs` test case was updated to use this fix in order to remove the auxiliary `set` function (#819).

Some notes apply to the approach chosen to make `selection_sort.rs` verify:

* A "dummy" `body_invariant!(a[0] <= a[i]);` was added to the outer and inner loops in order to correctly trigger the quantifiers.
* A change was made in `prusti-viper/src/encoder/foldunfold/mod.rs` to prevent Prusti from running into an encoder error when the `old` expresion was only present in the trigger, but not in the quantifier body. Without this change, `selection_sort.rs` will complain about a fold-unfold error. Since access predicates are not needed when the `old` expression is only present in the trigger, this should be sound (but please do double check this during the peer review).
* Without the auxiliary `set` function, the verification time roughly doubled, but it is still well within the `-Pverification_deadline=180` compiler parameter. Execution time now hovers around ~2 minutes on my PC.

If the chosen approach sounds good, then this PR can be merged. I'm still a bit suspicious about why the `set` function yields better performance, I could look into this deeper with some guidance (possibly in a separate PR if that makes more sense). For now I came up empty-handed for what could be causing this performance regression (if this happens to be related to how Viper gives hints to Z3 based on the Viper/Silver syntax, then my current experience may not be of much help, but am willing to learn more!).

Thanks!

p.s. Issue #877 can be left open for now in case we want to file a bug report with the Viper back-end developers to investigate the `old` trigger issue. I posted a ~30 lines example there that hopefully is small enough to investigate.

Co-authored-by: Pointerbender <pointerbender@gmail.com>
7ddc914

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
vir
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Prusti

Test Test on crates Deploy Test coverage Project chat

Prusti is a prototype verifier for Rust, built upon the Viper verification infrastructure.

By default Prusti verifies absence of integer overflows and panics by proving that statements such as unreachable!() and panic!() are unreachable. Overflow checking can be disabled with a configuration flag, treating all integers as unbounded. In Prusti, the functional behaviour of a function can be specified by using annotations, among which are preconditions, postconditions, and loop invariants. The tool checks them, reporting error messages when the code does not adhere to the provided specification.

For a tutorial and more information, check out the user guide.

Using Prusti

The easiest way to try out Prusti is by using the "Prusti Assistant" extension for VS Code.

Alternatively, if you wish to use Prusti from the command line there are three options:

  • Download the precompiled binaries for Ubuntu, Windows, or MacOS from a GitHub release.
  • Compile from the source code, by installing rustup, running ./x.py setup and then ./x.py build --release.
  • Build a Docker image from Dockerfile.

All three options provide the prusti-rustc and cargo-prusti programs that can be used analogously to, respectively, rustc and cargo check. For more detailed instructions, refer to the user guide and to the developer guide.

Do you still have questions? Open an issue or contact us on Zulip.