vstd/
slice.rs

1#![allow(unused_imports)]
2use super::prelude::*;
3use super::seq::*;
4use super::view::*;
5use core::slice::SliceIndex;
6
7#[cfg(verus_keep_ghost)]
8#[cfg(feature = "alloc")]
9pub use super::std_specs::vec::VecAdditionalSpecFns;
10
11verus! {
12
13impl<T> View for [T] {
14    type V = Seq<T>;
15
16    uninterp spec fn view(&self) -> Seq<T>;
17}
18
19impl<T: DeepView> DeepView for [T] {
20    type V = Seq<T::V>;
21
22    open spec fn deep_view(&self) -> Seq<T::V> {
23        let v = self.view();
24        Seq::new(v.len(), |i: int| v[i].deep_view())
25    }
26}
27
28pub trait SliceAdditionalSpecFns<T>: View<V = Seq<T>> {
29    spec fn spec_index(&self, i: int) -> T
30        recommends
31            0 <= i < self.view().len(),
32    ;
33}
34
35impl<T> SliceAdditionalSpecFns<T> for [T] {
36    #[verifier::inline]
37    open spec fn spec_index(&self, i: int) -> T {
38        self.view().index(i)
39    }
40}
41
42#[verifier::external]
43pub trait SliceAdditionalExecFns<T> {
44    #[cfg_attr(not(verus_verify_core), deprecated = "use `slice[i] = value` instead")]
45    fn set(&mut self, idx: usize, t: T);
46}
47
48impl<T> SliceAdditionalExecFns<T> for [T] {
49    #[verifier::external_body]
50    fn set(&mut self, idx: usize, t: T)
51        requires
52            0 <= idx < old(self)@.len(),
53        ensures
54            final(self)@ == old(self)@.update(idx as int, t),
55    {
56        self[idx] = t;
57    }
58}
59
60#[verifier::external_body]
61#[cfg_attr(verus_keep_ghost, rustc_diagnostic_item = "verus::vstd::slice::slice_index_get")]
62pub exec fn slice_index_get<T>(slice: &[T], i: usize) -> (out: &T)
63    requires
64        0 <= i < slice.view().len(),
65    ensures
66        *out == slice@.index(i as int),
67{
68    &slice[i]
69}
70
71////// Len (with autospec)
72#[cfg_attr(all(verus_keep_ghost), rustc_diagnostic_item = "verus::vstd::slice::spec_slice_len")]
73pub uninterp spec fn spec_slice_len<T>(slice: &[T]) -> usize;
74
75// This axiom is slightly better than defining spec_slice_len to just be `slice@.len() as usize`
76// (the axiom also shows that slice@.len() is in-bounds for usize)
77pub broadcast axiom fn axiom_spec_len<T>(slice: &[T])
78    ensures
79        #[trigger] spec_slice_len(slice) == slice@.len(),
80;
81
82#[verifier::allow_in_spec]
83pub assume_specification<T>[ <[T]>::len ](slice: &[T]) -> (len: usize)
84    returns
85        spec_slice_len(slice),
86    opens_invariants none
87    no_unwind
88;
89
90pub open spec fn spec_slice_is_empty<T>(slice: &[T]) -> bool {
91    slice@.len() == 0
92}
93
94#[verifier::when_used_as_spec(spec_slice_is_empty)]
95pub assume_specification<T>[ <[T]>::is_empty ](slice: &[T]) -> (b: bool)
96    ensures
97        b <==> slice@.len() == 0,
98    opens_invariants none
99    no_unwind
100;
101
102#[cfg(feature = "alloc")]
103#[verifier::external_body]
104pub exec fn slice_to_vec<T: Copy>(slice: &[T]) -> (out: alloc::vec::Vec<T>)
105    ensures
106        out@ == slice@,
107{
108    slice.to_vec()
109}
110
111#[verifier::external_body]
112pub exec fn slice_subrange<T, 'a>(slice: &'a [T], i: usize, j: usize) -> (out: &'a [T])
113    requires
114        0 <= i <= j <= slice@.len(),
115    ensures
116        out@ == slice@[i..j],
117{
118    &slice[i..j]
119}
120
121#[verifier::external_trait_specification]
122#[verifier::external_trait_extension(SliceIndexSpec via SliceIndexSpecImpl)]
123pub trait ExSliceIndex<T> where T: ?Sized {
124    type ExternalTraitSpecificationFor: SliceIndex<T>;
125
126    type Output: ?Sized;
127
128    spec fn in_bounds(&self, slice: &T) -> bool;
129
130    spec fn index_postcondition(&self, slice: &T, r: &Self::Output) -> bool;
131
132    spec fn index_mut_postcondition(
133        &self,
134        old_slice: &T,
135        final_slice: &T,
136        immediate_output: &Self::Output,
137        final_output: &Self::Output,
138    ) -> bool;
139
140    fn index(self, slice: &T) -> (r: &Self::Output)
141        requires
142            self.in_bounds(slice),
143        ensures
144            self.index_postcondition(slice, r),
145    ;
146
147    fn index_mut(self, slice: &mut T) -> (r: &mut Self::Output)
148        requires
149            self.in_bounds(slice),
150        ensures
151            self.index_mut_postcondition(&*old(slice), &*final(slice), r, &*final(r)),
152    ;
153
154    fn get(self, slice: &T) -> (r: Option<&Self::Output>)
155        ensures
156            match r {
157                None => !self.in_bounds(slice),
158                Some(x) => self.in_bounds(slice) && self.index_postcondition(slice, x),
159            },
160    ;
161
162    fn get_mut(self, slice: &mut T) -> (r: Option<&mut Self::Output>)
163        ensures
164            match r {
165                None => !self.in_bounds(old(slice)) && &*final(slice) == &*old(slice),
166                Some(x) => {
167                    &&& self.in_bounds(old(slice))
168                    &&& self.index_mut_postcondition(&*old(slice), &*final(slice), x, &*final(x))
169                },
170            },
171    ;
172}
173
174pub broadcast axiom fn axiom_slice_ext_equal<T>(a1: &[T], a2: &[T])
175    ensures
176        #[trigger] (a1 =~= a2) <==> (a1.len() == a2.len() && forall|i: int|
177            0 <= i < a1.len() ==> a1[i] == a2[i]),
178;
179
180#[verifier::external_body]
181#[cfg_attr(verus_keep_ghost, rustc_diagnostic_item = "verus::vstd::slice::spec_slice_update")]
182pub uninterp spec fn spec_slice_update<T>(slice: &[T], i: int, t: T) -> &[T];
183
184pub broadcast axiom fn axiom_spec_slice_update<T>(slice: &[T], i: int, t: T)
185    ensures
186        0 <= i < spec_slice_len(slice) ==> (#[trigger] spec_slice_update(slice, i, t)@)
187            == slice@.update(i, t),
188;
189
190#[verifier::external_body]
191#[cfg_attr(verus_keep_ghost, rustc_diagnostic_item = "verus::vstd::slice::spec_slice_index")]
192pub uninterp spec fn spec_slice_index<T>(slice: &[T], i: int) -> T;
193
194pub broadcast axiom fn axiom_spec_slice_index<T>(slice: &[T], i: int)
195    ensures
196        0 <= i < spec_slice_len(slice) ==> (#[trigger] spec_slice_index(slice, i)) == slice@[i],
197;
198
199pub broadcast axiom fn axiom_slice_has_resolved<T>(slice: &[T], i: int)
200    ensures
201        0 <= i < spec_slice_len(slice) ==> #[trigger] has_resolved_unsized::<[T]>(slice)
202            ==> has_resolved(#[trigger] slice@[i]),
203;
204
205/// We axiomatize that a slice can decrease to its corresponding sequence.
206pub broadcast axiom fn axiom_slice_decreases_to_seq<T>(s: &[T])
207    ensures
208        #[trigger] (decreases_to!(s => s@)),
209;
210
211/// A slice can decrease to any of its elements, obtained by indexing.
212pub broadcast proof fn lemma_slice_index_decreases<T>(s: &[T], i: int)
213    requires
214        0 <= i < s@.len(),
215    ensures
216        #[trigger] (decreases_to!(s => s@[i])),
217{
218    axiom_slice_decreases_to_seq(s);
219    lemma_seq_index_decreases(s@, i);
220}
221
222pub axiom fn mut_ref_slice_len_eq<T>(tracked slice: &&mut [T])
223    ensures
224        old(*slice).len() == final(*slice).len(),
225;
226
227pub broadcast group group_slice_axioms {
228    axiom_spec_len,
229    axiom_slice_ext_equal,
230    axiom_spec_slice_update,
231    axiom_spec_slice_index,
232    axiom_slice_has_resolved,
233    axiom_slice_decreases_to_seq,
234    lemma_slice_index_decreases,
235}
236
237pub axiom fn tracked_borrow<T>(tracked s: &[T], i: int) -> (tracked t: &T)
238    requires
239        0 <= i < s.len(),
240    ensures
241        t == s[i],
242;
243
244pub axiom fn tracked_borrow_mut<T>(tracked s: &mut [T], i: int) -> (tracked t: &mut T)
245    requires
246        0 <= i < s.len(),
247    ensures
248        *t == old(s)[i],
249        final(s)@ == old(s)@.update(i, *final(t)),
250;
251
252} // verus!
vstd/slice.rs

vstd/
slice.rs
