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;
87
88pub open spec fn spec_slice_is_empty<T>(slice: &[T]) -> bool {
89    slice@.len() == 0
90}
91
92#[verifier::when_used_as_spec(spec_slice_is_empty)]
93pub assume_specification<T>[ <[T]>::is_empty ](slice: &[T]) -> (b: bool)
94    ensures
95        b <==> slice@.len() == 0,
96;
97
98#[cfg(feature = "alloc")]
99#[verifier::external_body]
100pub exec fn slice_to_vec<T: Copy>(slice: &[T]) -> (out: alloc::vec::Vec<T>)
101    ensures
102        out@ == slice@,
103{
104    slice.to_vec()
105}
106
107#[verifier::external_body]
108pub exec fn slice_subrange<T, 'a>(slice: &'a [T], i: usize, j: usize) -> (out: &'a [T])
109    requires
110        0 <= i <= j <= slice@.len(),
111    ensures
112        out@ == slice@[i..j],
113{
114    &slice[i..j]
115}
116
117#[verifier::external_trait_specification]
118#[verifier::external_trait_extension(SliceIndexSpec via SliceIndexSpecImpl)]
119pub trait ExSliceIndex<T> where T: ?Sized {
120    type ExternalTraitSpecificationFor: SliceIndex<T>;
121
122    type Output: ?Sized;
123
124    spec fn in_bounds(&self, slice: &T) -> bool;
125
126    spec fn index_postcondition(&self, slice: &T, r: &Self::Output) -> bool;
127
128    spec fn index_mut_postcondition(
129        &self,
130        old_slice: &T,
131        final_slice: &T,
132        immediate_output: &Self::Output,
133        final_output: &Self::Output,
134    ) -> bool;
135
136    fn index(self, slice: &T) -> (r: &Self::Output)
137        requires
138            self.in_bounds(slice),
139        ensures
140            self.index_postcondition(slice, r),
141    ;
142
143    fn index_mut(self, slice: &mut T) -> (r: &mut Self::Output)
144        requires
145            self.in_bounds(slice),
146        ensures
147            self.index_mut_postcondition(&*old(slice), &*final(slice), r, &*final(r)),
148    ;
149
150    fn get(self, slice: &T) -> (r: Option<&Self::Output>)
151        ensures
152            match r {
153                None => !self.in_bounds(slice),
154                Some(x) => self.in_bounds(slice) && self.index_postcondition(slice, x),
155            },
156    ;
157
158    fn get_mut(self, slice: &mut T) -> (r: Option<&mut Self::Output>)
159        ensures
160            match r {
161                None => !self.in_bounds(old(slice)) && &*final(slice) == &*old(slice),
162                Some(x) => {
163                    &&& self.in_bounds(old(slice))
164                    &&& self.index_mut_postcondition(&*old(slice), &*final(slice), x, &*final(x))
165                },
166            },
167    ;
168}
169
170pub broadcast axiom fn axiom_slice_ext_equal<T>(a1: &[T], a2: &[T])
171    ensures
172        #[trigger] (a1 =~= a2) <==> (a1.len() == a2.len() && forall|i: int|
173            0 <= i < a1.len() ==> a1[i] == a2[i]),
174;
175
176#[verifier::external_body]
177#[cfg_attr(verus_keep_ghost, rustc_diagnostic_item = "verus::vstd::slice::spec_slice_update")]
178pub uninterp spec fn spec_slice_update<T>(slice: &[T], i: int, t: T) -> &[T];
179
180pub broadcast axiom fn axiom_spec_slice_update<T>(slice: &[T], i: int, t: T)
181    ensures
182        0 <= i < spec_slice_len(slice) ==> (#[trigger] spec_slice_update(slice, i, t)@)
183            == slice@.update(i, t),
184;
185
186#[verifier::external_body]
187#[cfg_attr(verus_keep_ghost, rustc_diagnostic_item = "verus::vstd::slice::spec_slice_index")]
188pub uninterp spec fn spec_slice_index<T>(slice: &[T], i: int) -> T;
189
190pub broadcast axiom fn axiom_spec_slice_index<T>(slice: &[T], i: int)
191    ensures
192        0 <= i < spec_slice_len(slice) ==> (#[trigger] spec_slice_index(slice, i)) == slice@[i],
193;
194
195pub broadcast axiom fn axiom_slice_has_resolved<T>(slice: &[T], i: int)
196    ensures
197        0 <= i < spec_slice_len(slice) ==> #[trigger] has_resolved_unsized::<[T]>(slice)
198            ==> has_resolved(#[trigger] slice@[i]),
199;
200
201/// We axiomatize that a slice can decrease to its corresponding sequence.
202pub broadcast axiom fn axiom_slice_decreases_to_seq<T>(s: &[T])
203    ensures
204        #[trigger] (decreases_to!(s => s@)),
205;
206
207/// A slice can decrease to any of its elements, obtained by indexing.
208pub broadcast proof fn lemma_slice_index_decreases<T>(s: &[T], i: int)
209    requires
210        0 <= i < s@.len(),
211    ensures
212        #[trigger] (decreases_to!(s => s@[i])),
213{
214    axiom_slice_decreases_to_seq(s);
215    lemma_seq_index_decreases(s@, i);
216}
217
218pub axiom fn mut_ref_slice_len_eq<T>(tracked slice: &&mut [T])
219    ensures
220        old(*slice).len() == final(*slice).len(),
221;
222
223pub broadcast group group_slice_axioms {
224    axiom_spec_len,
225    axiom_slice_ext_equal,
226    axiom_spec_slice_update,
227    axiom_spec_slice_index,
228    axiom_slice_has_resolved,
229    axiom_slice_decreases_to_seq,
230    lemma_slice_index_decreases,
231}
232
233pub axiom fn tracked_borrow<T>(tracked s: &[T], i: int) -> (tracked t: &T)
234    requires
235        0 <= i < s.len(),
236    ensures
237        t == s[i],
238;
239
240pub axiom fn tracked_borrow_mut<T>(tracked s: &mut [T], i: int) -> (tracked t: &mut T)
241    requires
242        0 <= i < s.len(),
243    ensures
244        *t == old(s)[i],
245        final(s)@ == old(s)@.update(i, *final(t)),
246;
247
248} // verus!
vstd/slice.rs

vstd/
slice.rs
