vstd/resource/impls/
seq.rs

1use super::super::super::modes::*;
2use super::super::super::prelude::*;
3use super::super::Loc;
4use super::super::imap::*;
5
6verus! {
7
8broadcast use super::super::super::group_vstd_default;
9
10pub open spec fn seq_to_map<V>(s: Seq<V>, off: int) -> IMap<int, V> {
11    IMap::new(|i: int| off <= i < off + s.len(), |i: int| s[i - off])
12}
13
14/** An implementation of a resource for owning a subrange of a sequence.
15
16`GhostSeqAuth<T>` represents authoritative ownership of the entire
17sequence, and `GhostSubseq<T>` represents client ownership of some
18subrange of that sequence.  Updating the authoritative `GhostSeqAuth<T>`
19requires a `GhostSubseq<T>` covering the relevant positions.
20`GhostSubseq<K, T>`s can be combined or split.
21
22### Example
23
24```
25fn example_use() {
26    let tracked (mut auth, mut sub) = GhostSeqAuth::new(seq![0u64, 1u64, 2u64, 3u64, 4u64, 5u64], 0);
27
28    // Split the subsequence into a multiple subseqs.
29    let tracked sub2 = sub.split(3);
30
31    // In general, we might need to call agree() to establish the fact that
32    // a subseq has the same values as the auth seq.  Here, Verus doesn't need
33    // agree because it can track where both the auth and subseq came from.
34    proof { sub.agree(&auth); }
35    proof { sub2.agree(&auth); }
36
37    assert(sub[0] == auth[0]);
38    assert(sub2[0] == auth[3]);
39
40    // Update the sequence using ownership of subseqs.
41    // The update() method on GhostSubseq updates the entire subrange.
42    proof { sub.update(&mut auth, seq![10u64, 11u64, 12u64]); }
43    assert(auth[0] == 10u64);
44    assert(sub[0] == 10u64);
45
46    // The update_subrange_with() method on GhostSeqAuth allows updating
47    // arbitrary parts of a subseq's subrange.
48    proof { auth.update_subrange_with(&mut sub2, 4, seq![24u64, 25u64]); }
49    assert(auth[3] == 3u64);
50    assert(auth[4] == 24u64);
51    assert(sub2[1] == 24u64);
52
53    // Not shown in this simple example is the main use case of this resource:
54    // maintaining an invariant between GhostSeqAuth<V> and some exec-mode
55    // shared state with a seq view (e.g., the contents of a file or a disk),
56    // which states that the Seq<V> view of GhostSeqAuth<V> is the same as the
57    // view of the state (e.g., file or disk contents), and then handing out a
58    // GhostSubseq<V> to different clients that might need to operate on
59    // different subranges of the shared state (e.g., different concurrent
60    // transactions that operate on different parts of the file/disk).
61}
62```
63*/
64
65pub tracked struct GhostSeqAuth<V> {
66    ghost off: nat,
67    ghost len: nat,
68    auth: GhostIMapAuth<int, V>,
69}
70
71pub tracked struct GhostSubseq<V> {
72    ghost off: nat,
73    ghost len: nat,
74    frac: GhostISubmap<int, V>,
75}
76
77impl<V> GhostSeqAuth<V> {
78    #[verifier::type_invariant]
79    spec fn inv(self) -> bool {
80        &&& self.auth@.dom() =~= ISet::new(|i: int| self.off <= i < self.off + self.len)
81    }
82
83    pub closed spec fn id(self) -> Loc {
84        self.auth.id()
85    }
86
87    pub closed spec fn view(self) -> Seq<V> {
88        Seq::new(self.len, |i: int| self.auth@[self.off + i])
89    }
90
91    pub open spec fn len(self) -> nat {
92        self@.len()
93    }
94
95    pub open spec fn spec_index(self, idx: int) -> V
96        recommends
97            0 <= idx < self.len(),
98    {
99        self@[idx]
100    }
101
102    pub closed spec fn off(self) -> nat {
103        self.off
104    }
105
106    pub open spec fn subrange_abs(self, start_inclusive: int, end_exclusive: int) -> Seq<V>
107        recommends
108            self.off() <= start_inclusive <= end_exclusive <= self.off() + self@.len(),
109    {
110        self@[start_inclusive - self.off()..end_exclusive - self.off()]
111    }
112
113    pub proof fn new(s: Seq<V>, off: nat) -> (tracked result: (GhostSeqAuth<V>, GhostSubseq<V>))
114        ensures
115            result.0.off() == off,
116            result.0@ =~= s,
117            result.1.id() == result.0.id(),
118            result.1.off() == off,
119            result.1@ =~= s,
120    {
121        let tracked (mauth, mfrac) = GhostIMapAuth::<int, V>::new(seq_to_map(s, off as int));
122        let tracked auth = GhostSeqAuth { off: off, len: s.len(), auth: mauth };
123        let tracked frac = GhostSubseq { off: off, len: s.len(), frac: mfrac };
124        (auth, frac)
125    }
126
127    pub proof fn dummy() -> (tracked result: Self) {
128        let tracked (auth, subseq) = Self::new(Seq::empty(), 0);
129        auth
130    }
131
132    pub proof fn agree(tracked self: &GhostSeqAuth<V>, tracked frac: &GhostSubseq<V>)
133        requires
134            self.id() == frac.id(),
135        ensures
136            frac@.len() > 0 ==> {
137                &&& frac@ =~= self@[frac.off() - self.off()..frac.off() - self.off() + frac@.len()]
138                &&& frac.off() >= self.off()
139                &&& frac.off() + frac@.len() <= self.off() + self@.len()
140            },
141    {
142        frac.agree(self)
143    }
144
145    pub proof fn update_subrange_with(
146        tracked self: &mut GhostSeqAuth<V>,
147        tracked frac: &mut GhostSubseq<V>,
148        off: int,
149        v: Seq<V>,
150    )
151        requires
152            old(self).id() == old(frac).id(),
153            old(frac).off() <= off,
154            off + v.len() <= old(frac).off() + old(frac)@.len(),
155        ensures
156            final(self).id() == old(self).id(),
157            final(frac).id() == old(frac).id(),
158            final(frac).off() == old(frac).off(),
159            final(self)@ =~= old(self)@.update_subrange_with(off - final(self).off(), v),
160            final(frac)@ =~= old(frac)@.update_subrange_with(off - final(frac).off(), v),
161            final(self).off() == old(self).off(),
162            final(frac).off() == old(frac).off(),
163    {
164        let tracked mut mid = frac.split(off - frac.off());
165        let tracked mut end = mid.split(v.len() as int);
166        mid.update(self, v);
167        frac.combine(mid);
168        frac.combine(end);
169    }
170}
171
172impl<V> GhostSubseq<V> {
173    #[verifier::type_invariant]
174    spec fn inv(self) -> bool {
175        &&& self.frac@.dom() =~= ISet::new(|i: int| self.off <= i < self.off + self.len)
176    }
177
178    pub closed spec fn view(self) -> Seq<V> {
179        Seq::new(self.len, |i: int| self.frac@[self.off + i])
180    }
181
182    pub open spec fn len(self) -> nat {
183        self@.len()
184    }
185
186    pub open spec fn spec_index(self, idx: int) -> V
187        recommends
188            0 <= idx < self.len(),
189    {
190        self@[idx]
191    }
192
193    pub open spec fn subrange_abs(self, start_inclusive: int, end_exclusive: int) -> Seq<V>
194        recommends
195            self.off() <= start_inclusive <= end_exclusive <= self.off() + self@.len(),
196    {
197        self@[start_inclusive - self.off()..end_exclusive - self.off()]
198    }
199
200    pub closed spec fn off(self) -> nat {
201        self.off
202    }
203
204    pub closed spec fn id(self) -> Loc {
205        self.frac.id()
206    }
207
208    pub proof fn agree(tracked self: &GhostSubseq<V>, tracked auth: &GhostSeqAuth<V>)
209        requires
210            self.id() == auth.id(),
211        ensures
212            self@.len() > 0 ==> {
213                &&& self@ =~= auth@[self.off() - auth.off()..self.off() - auth.off() + self@.len()]
214                &&& self.off() >= auth.off()
215                &&& self.off() + self@.len() <= auth.off() + auth@.len()
216            },
217    {
218        use_type_invariant(self);
219        use_type_invariant(auth);
220
221        self.frac.agree(&auth.auth);
222
223        if self@.len() > 0 {
224            assert(self.frac@.contains_key(self.off as int));
225            assert(auth.auth@.contains_key(self.off as int));
226
227            assert(self.frac@.contains_key(self.off + self.len - 1));
228            assert(auth.auth@.contains_key(self.off + self.len - 1));
229            assert(self.off - auth.off + self.len - 1 < auth@.len());
230
231            assert forall|i: int| 0 <= i < self.len implies #[trigger] self.frac@[self.off + i]
232                == auth@[self.off - auth.off + i] by {
233                assert(self.frac@.contains_key(self.off + i));
234                assert(auth.auth@.contains_key(self.off + i));
235            };
236        }
237    }
238
239    pub proof fn agree_map(tracked self: &GhostSubseq<V>, tracked auth: &GhostIMapAuth<int, V>)
240        requires
241            self.id() == auth.id(),
242        ensures
243            forall|i|
244                0 <= i < self@.len() ==> #[trigger] auth@.contains_key(self.off() + i)
245                    && auth@[self.off() + i] == self@[i],
246    {
247        use_type_invariant(self);
248
249        self.frac.agree(&auth);
250
251        assert forall|i: int| 0 <= i < self.len implies #[trigger] auth@.contains_key(self.off + i)
252            && self.frac@[self.off + i] == auth@[self.off + i] by {
253            assert(self.frac@.contains_key(self.off + i));
254        };
255    }
256
257    pub proof fn update(
258        tracked self: &mut GhostSubseq<V>,
259        tracked auth: &mut GhostSeqAuth<V>,
260        v: Seq<V>,
261    )
262        requires
263            old(self).id() == old(auth).id(),
264            v.len() == old(self)@.len(),
265        ensures
266            final(self).id() == final(auth).id(),
267            final(self).off() == old(self).off(),
268            final(auth).id() == old(auth).id(),
269            final(self)@ =~= v,
270            final(auth)@ =~= old(auth)@.update_subrange_with(
271                final(self).off() - final(auth).off(),
272                v,
273            ),
274            final(self).off() == old(self).off(),
275            final(auth).off() == old(auth).off(),
276    {
277        use_type_invariant(&*self);
278        use_type_invariant(&*auth);
279
280        self.update_map(&mut auth.auth, v);
281    }
282
283    pub proof fn update_map(
284        tracked self: &mut GhostSubseq<V>,
285        tracked auth: &mut GhostIMapAuth<int, V>,
286        v: Seq<V>,
287    )
288        requires
289            old(self).id() == old(auth).id(),
290            v.len() == old(self)@.len(),
291        ensures
292            final(self).id() == final(auth).id(),
293            final(self).off() == old(self).off(),
294            final(auth).id() == old(auth).id(),
295            final(self)@ =~= v,
296            final(auth)@ =~= IMap::new(
297                |i: int| old(auth)@.contains_key(i),
298                |i: int|
299                    if final(self).off() <= i < final(self).off() + v.len() {
300                        v[i - final(self).off()]
301                    } else {
302                        old(auth)@[i]
303                    },
304            ),
305    {
306        use_type_invariant(&*self);
307
308        let vmap = seq_to_map(v, self.off as int);
309        assert(self.frac@.dom() == vmap.dom());
310        self.frac.agree(auth);
311        self.frac.update(auth, vmap);
312    }
313
314    pub proof fn split(tracked self: &mut GhostSubseq<V>, n: int) -> (tracked result: GhostSubseq<
315        V,
316    >)
317        requires
318            0 <= n <= old(self)@.len(),
319        ensures
320            final(self).id() == old(self).id(),
321            final(self).off() == old(self).off(),
322            result.id() == final(self).id(),
323            result.off() == old(self).off() + n,
324            final(self)@ =~= old(self)@[0..n],
325            result@ =~= old(self)@[n..old(self)@.len()],
326    {
327        let tracked mut mself = Self::dummy();
328        tracked_swap(self, &mut mself);
329
330        use_type_invariant(&mself);
331        let tracked mut mselffrac = mself.frac;
332
333        let tracked mfrac = mselffrac.split(
334            ISet::new(|i: int| mself.off + n <= i < mself.off + mself.len),
335        );
336        let tracked result = GhostSubseq {
337            off: (mself.off + n) as nat,
338            len: (mself.len - n) as nat,
339            frac: mfrac,
340        };
341
342        *self = Self { off: mself.off, len: n as nat, frac: mselffrac };
343        result
344    }
345
346    pub proof fn combine(tracked self: &mut GhostSubseq<V>, tracked r: GhostSubseq<V>)
347        requires
348            r.id() == old(self).id(),
349            r.off() == old(self).off() + old(self)@.len(),
350        ensures
351            final(self).id() == old(self).id(),
352            final(self)@ =~= old(self)@ + r@,
353            final(self).off() == old(self).off(),
354    {
355        let tracked mut mself = Self::dummy();
356        tracked_swap(self, &mut mself);
357
358        use_type_invariant(&mself);
359        use_type_invariant(&r);
360        let tracked mut mselffrac = mself.frac;
361
362        mselffrac.combine(r.frac);
363        *self = Self { frac: mselffrac, off: mself.off, len: mself.len + r.len };
364    }
365
366    pub proof fn disjoint(tracked &mut self, tracked other: &GhostSubseq<V>)
367        requires
368            old(self).id() == other.id(),
369        ensures
370            final(self).id() == old(self).id(),
371            final(self).off() == old(self).off(),
372            final(self)@ == old(self)@,
373            final(self)@.len() == 0 || other@.len() == 0 || final(self).off() + final(self)@.len()
374                <= other.off() || other.off() + other@.len() <= final(self).off(),
375    {
376        use_type_invariant(&*self);
377        use_type_invariant(other);
378
379        self.frac.disjoint(&other.frac);
380        assert(self@.len() == 0 || self.frac@.contains_key(self.off() as int));
381        assert(other@.len() == 0 || other.frac@.contains_key(other.off() as int));
382    }
383
384    pub proof fn dummy() -> (tracked result: Self) {
385        let tracked (auth, subseq) = GhostSeqAuth::<V>::new(Seq::empty(), 0);
386        subseq
387    }
388
389    // Helper to lift GhostISubmap into GhostSubseq.
390    pub proof fn new(off: nat, len: nat, tracked f: GhostISubmap<int, V>) -> (tracked result:
391        GhostSubseq<V>)
392        requires
393            f@.dom() == ISet::new(|i: int| off <= i < off + len),
394        ensures
395            result.id() == f.id(),
396            result.off() == off,
397            result@ == Seq::new(len, |i| f@[off + i]),
398    {
399        GhostSubseq { off: off, len: len, frac: f }
400    }
401}
402
403} // verus!
vstd/resource/impls/seq.rs

vstd/resource/impls/
seq.rs
