vstd/proph.rs
1#![allow(unused_variables)]
2
3use super::prelude::*;
4
5verus! {
6
7/// A "prophecy variable" that predicts some value of type T.
8///
9/// A prophecy can be allocated by calling [`Prophecy::<T>::new()`] in exec mode.
10/// The result is a prophecy variable whose view is an arbitrary value of type T.
11///
12/// A prophecy can be resolved by calling [`Prophecy::<T>::resolve()`] in exec mode.
13/// This call ensures that the view of the prophecy variable is equal to the value
14/// passed to `resolve()`. This call (and in particular, its argument v) must be
15/// exec-mode to avoid circular dependency on the value of the prophecy variable.
16/// The value cannot have _any_ "ghost content" (not even via `Ghost`);
17/// hence the `T: Structural` trait bound.
18///
19/// We make an informal soundness argument based on the paper
20/// [_The Future is Ours: Prophecy Variables in Separation Logic_](https://plv.mpi-sws.org/prophecies/paper.pdf).
21/// The argument goes as follows:
22/// For any execution of the program, there is some sequence of calls to `resolve()`,
23/// whose values do not depend on spec- or proof-mode values. Those values can be
24/// plugged into the arbitrary ghost values chosen by `new()`, for the corresponding
25/// prophecy variables, to justify the proof accompanying the program. Since both
26/// `new()` and `resolve()` are exec-mode, there is no ambiguity about which `new()`
27/// call corresponds to a particular `resolve()` value.
28pub struct Prophecy<T> {
29 v: Ghost<T>,
30}
31
32impl<T> Prophecy<T> where T: Structural {
33 /// The prophecized value.
34 pub closed spec fn view(self) -> T {
35 self.v@
36 }
37
38 /// Allocate a new prophecy variable.
39 #[inline(always)]
40 pub exec fn new() -> (result: Self) {
41 Prophecy::<T> { v: Ghost(arbitrary()) }
42 }
43
44 /// Resolve the prophecy variable to a concrete value.
45 /// This consumes `self`, so it can only be called once.
46 #[inline(always)]
47 #[verifier::external_body]
48 pub exec fn resolve(self, v: &T)
49 ensures
50 self@ == v,
51 {
52 }
53}
54
55} // verus!