Struct GhostSeqAuth

Source
pub struct GhostSeqAuth<V> { /* private fields */ }
Expand description

An implementation of a resource for owning a subrange of a sequence.

GhostSeqAuth<T> represents authoritative ownership of the entire sequence, and GhostSubseq<T> represents client ownership of some subrange of that sequence. Updating the authoritative GhostSeqAuth<T> requires a GhostSubseq<T> covering the relevant positions. GhostSubseq<K, T>s can be combined or split.

§Example

fn example_use() {
    let tracked (mut auth, mut sub) = GhostSeqAuth::new(seq![0u64, 1u64, 2u64, 3u64, 4u64, 5u64], 0);

    // Split the subsequence into a multiple subseqs.
    let tracked sub2 = sub.split(3);

    // In general, we might need to call agree() to establish the fact that
    // a subseq has the same values as the auth seq.  Here, Verus doesn't need
    // agree because it can track where both the auth and subseq came from.
    proof { sub.agree(&auth); }
    proof { sub2.agree(&auth); }

    assert(sub[0] == auth[0]);
    assert(sub2[0] == auth[3]);

    // Update the sequence using ownership of subseqs.
    // The update() method on GhostSubseq updates the entire subrange.
    proof { sub.update(&mut auth, seq![10u64, 11u64, 12u64]); }
    assert(auth[0] == 10u64);
    assert(sub[0] == 10u64);

    // The update_subrange_with() method on GhostSeqAuth allows updating
    // arbitrary parts of a subseq's subrange.
    proof { auth.update_subrange_with(&mut sub2, 4, seq![24u64, 25u64]); }
    assert(auth[3] == 3u64);
    assert(auth[4] == 24u64);
    assert(sub2[1] == 24u64);

    // Not shown in this simple example is the main use case of this resource:
    // maintaining an invariant between GhostSeqAuth<V> and some exec-mode
    // shared state with a seq view (e.g., the contents of a file or a disk),
    // which states that the Seq<V> view of GhostSeqAuth<V> is the same as the
    // view of the state (e.g., file or disk contents), and then handing out a
    // GhostSubseq<V> to different clients that might need to operate on
    // different subranges of the shared state (e.g., different concurrent
    // transactions that operate on different parts of the file/disk).
}

Implementations§

Source§

impl<V> GhostSeqAuth<V>

Source

pub closed spec fn id(self) -> int

Source

pub closed spec fn view(self) -> Seq<V>

Source

pub open spec fn len(self) -> nat

{ self@.len() }
Source

pub open spec fn spec_index(self, idx: int) -> V

recommends
0 <= idx < self.len(),
{ self@[idx] }
Source

pub closed spec fn off(self) -> nat

Source

pub open spec fn subrange_abs(self, start_inclusive: int, end_exclusive: int) -> Seq<V>

recommends
self.off() <= start_inclusive <= end_exclusive <= self.off() + self@.len(),
{ self@.subrange(start_inclusive - self.off(), end_exclusive - self.off()) }
Source

pub proof fn new(s: Seq<V>, off: nat) -> tracked result : (GhostSeqAuth<V>, GhostSubseq<V>)

ensures
result.0.off() == off,
result.0@ =~= s,
result.1.id() == result.0.id(),
result.1.off() == off,
result.1@ =~= s,
Source

pub proof fn dummy() -> tracked result : Self

Source

pub proof fn agree(tracked self: &GhostSeqAuth<V>, tracked frac: &GhostSubseq<V>)

requires
self.id() == frac.id(),
ensures
frac@.len() > 0
    ==> {
        &&& frac@
            =~= self@
                .subrange(
                    frac.off() as int - self.off(),
                    frac.off() - self.off() + frac@.len() as int,
                )
        &&& frac.off() >= self.off()
        &&& frac.off() + frac@.len() <= self.off() + self@.len()

    },
Source

pub proof fn update_subrange_with(tracked self: &mut GhostSeqAuth<V>, tracked frac: &mut GhostSubseq<V>, off: int, v: Seq<V>, )

requires
old(self).id() == old(frac).id(),
old(frac).off() <= off,
off + v.len() <= old(frac).off() + old(frac)@.len(),
ensures
self.id() == old(self).id(),
frac.id() == old(frac).id(),
frac.off() == old(frac).off(),
self@ =~= old(self)@.update_subrange_with(off - self.off(), v),
frac@ =~= old(frac)@.update_subrange_with(off - frac.off(), v),
self.off() == old(self).off(),
frac.off() == old(frac).off(),

Auto Trait Implementations§

§

impl<V> Freeze for GhostSeqAuth<V>

§

impl<V> RefUnwindSafe for GhostSeqAuth<V>
where V: RefUnwindSafe,

§

impl<V> Send for GhostSeqAuth<V>
where V: Send,

§

impl<V> Sync for GhostSeqAuth<V>
where V: Sync,

§

impl<V> Unpin for GhostSeqAuth<V>
where V: Unpin,

§

impl<V> UnwindSafe for GhostSeqAuth<V>
where V: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.