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@.subrange(i as int, j as int),
113{
114    &slice[i..j]
115}
116
117#[verifier::external_trait_specification]
118#[verifier::external_trait_extension(SliceIndexSpec via SliceIndexSpecImpl)]
119#[verifier::external_trait_private_bound(core::slice::index::private_slice_index::Sealed)]
120pub trait ExSliceIndex<T> where T: ?Sized {
121    type ExternalTraitSpecificationFor: SliceIndex<T>;
122
123    type Output: ?Sized;
124
125    spec fn index_req(&self, slice: &T) -> bool;
126
127    fn index(self, slice: &T) -> &Self::Output
128        requires
129            self.index_req(slice),
130    ;
131}
132
133pub assume_specification<T, I>[ <[T]>::get::<I> ](slice: &[T], i: I) -> (b: Option<
134    &<I as SliceIndex<[T]>>::Output,
135>) where I: SliceIndex<[T]>
136    returns
137        spec_slice_get(slice, i),
138;
139
140pub uninterp spec fn spec_slice_get<T: ?Sized, I: SliceIndex<T>>(val: &T, idx: I) -> Option<
141    &<I as SliceIndex<T>>::Output,
142>;
143
144pub broadcast axiom fn axiom_slice_get_usize<T>(v: &[T], i: usize)
145    ensures
146        i < v.len() ==> #[trigger] spec_slice_get(v, i) == Some(&v[i as int]),
147        i >= v.len() ==> spec_slice_get(v, i).is_none(),
148;
149
150pub broadcast axiom fn axiom_slice_ext_equal<T>(a1: &[T], a2: &[T])
151    ensures
152        #[trigger] (a1 =~= a2) <==> (a1.len() == a2.len() && forall|i: int|
153            0 <= i < a1.len() ==> a1[i] == a2[i]),
154;
155
156#[verifier::external_body]
157#[cfg_attr(verus_keep_ghost, rustc_diagnostic_item = "verus::vstd::slice::spec_slice_update")]
158pub uninterp spec fn spec_slice_update<T>(slice: &[T], i: int, t: T) -> &[T];
159
160pub broadcast axiom fn axiom_spec_slice_update<T>(slice: &[T], i: int, t: T)
161    ensures
162        0 <= i < spec_slice_len(slice) ==> (#[trigger] spec_slice_update(slice, i, t)@)
163            == slice@.update(i, t),
164;
165
166#[verifier::external_body]
167#[cfg_attr(verus_keep_ghost, rustc_diagnostic_item = "verus::vstd::slice::spec_slice_index")]
168pub uninterp spec fn spec_slice_index<T>(slice: &[T], i: int) -> T;
169
170pub broadcast axiom fn axiom_spec_slice_index<T>(slice: &[T], i: int)
171    ensures
172        0 <= i < spec_slice_len(slice) ==> (#[trigger] spec_slice_index(slice, i)) == slice@[i],
173;
174
175pub broadcast axiom fn axiom_slice_has_resolved<T>(slice: &[T], i: int)
176    ensures
177        0 <= i < spec_slice_len(slice) ==> #[trigger] has_resolved_unsized::<[T]>(slice)
178            ==> has_resolved(#[trigger] slice@[i]),
179;
180
181pub broadcast group group_slice_axioms {
182    axiom_spec_len,
183    axiom_slice_get_usize,
184    axiom_slice_ext_equal,
185    axiom_spec_slice_update,
186    axiom_spec_slice_index,
187    axiom_slice_has_resolved,
188}
189
190} // verus!
vstd/slice.rs

vstd/
slice.rs
