soroban_env_host/host/
metered_vector.rs

1use crate::{
2    budget::{AsBudget, Budget},
3    host::{declared_size::DeclaredSizeForMetering, MeteredClone},
4    xdr::{ContractCostType, ScErrorCode, ScErrorType},
5    Compare, Error, Host, HostError,
6};
7
8use std::{cmp::Ordering, ops::Range};
9
10const VEC_OOB: Error = Error::from_type_and_code(ScErrorType::Object, ScErrorCode::IndexBounds);
11
12#[derive(Clone)]
13pub struct MeteredVector<A> {
14    pub(crate) vec: Vec<A>,
15}
16
17impl<A> Default for MeteredVector<A> {
18    fn default() -> Self {
19        Self {
20            vec: Default::default(),
21        }
22    }
23}
24
25impl<T> std::hash::Hash for MeteredVector<T>
26where
27    T: std::hash::Hash,
28{
29    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
30        self.vec.hash(state);
31    }
32}
33
34impl<A> MeteredVector<A>
35where
36    A: DeclaredSizeForMetering,
37{
38    fn charge_access(&self, count: usize, budget: &Budget) -> Result<(), HostError> {
39        budget.charge(
40            ContractCostType::MemCpy,
41            Some(A::DECLARED_SIZE.saturating_mul(count as u64)),
42        )
43    }
44
45    fn charge_scan(&self, budget: &Budget) -> Result<(), HostError> {
46        budget.charge(
47            ContractCostType::MemCpy,
48            Some(A::DECLARED_SIZE.saturating_mul(self.vec.len() as u64)),
49        )
50    }
51
52    // Charge binary search includes accessing number of entries expected for
53    // finding an entry. Cost of comparison is charged separately and not covered here.
54    fn charge_binsearch(&self, budget: &Budget) -> Result<(), HostError> {
55        let mag = 64u32.saturating_sub((self.vec.len() as u64).leading_zeros());
56        budget.charge(
57            ContractCostType::MemCpy,
58            Some(A::DECLARED_SIZE.saturating_mul((1 + mag) as u64)),
59        )
60    }
61}
62
63impl<A> MeteredVector<A>
64where
65    A: MeteredClone,
66{
67    // Constructs a empty new `MeteredVector`.
68    pub fn new() -> Self {
69        Self { vec: Vec::new() }
70    }
71
72    // Constructs a new, empty `MeteredVector` with at least the specified capacity.
73    // This is purely used for the cost calibration of allocating host memory.
74    // Do *not* use it for construction, since `MeteredVector` is immutable,
75    // the allocation will be wasted.
76    #[cfg(feature = "bench")]
77    pub fn with_capacity(capacity: usize, budget: &Budget) -> Result<Self, HostError> {
78        super::metered_clone::charge_heap_alloc::<A>(capacity as u64, budget)?;
79        Self::from_vec(Vec::with_capacity(capacity))
80    }
81
82    // No meter charge, assuming allocation cost has been covered by the caller from the outside.
83    pub fn from_vec(vec: Vec<A>) -> Result<Self, HostError> {
84        if u32::try_from(vec.len()).is_err() {
85            Err(VEC_OOB.into())
86        } else {
87            Ok(Self { vec })
88        }
89    }
90
91    pub fn as_slice(&self) -> &[A] {
92        self.vec.as_slice()
93    }
94
95    pub fn as_mut_slice(&mut self) -> &mut [A] {
96        self.vec.as_mut_slice()
97    }
98
99    // This doesn't take ExactSizeIterator since that is not implemented for Chain
100    // (see https://github.com/rust-lang/rust/issues/34433) but it only works
101    // with iterators that report an exact size_hint, and it constructs a new
102    // Vec from that iterator with a single allocation-and-copy.
103    pub fn from_exact_iter<I: Iterator<Item = A>>(
104        iter: I,
105        budget: &Budget,
106    ) -> Result<Self, HostError> {
107        let _span = tracy_span!("new vec");
108        if let (_, Some(sz)) = iter.size_hint() {
109            if u32::try_from(sz).is_err() {
110                Err(VEC_OOB.into())
111            } else {
112                // It's possible we temporarily go over-budget here before charging, but
113                // only by the cost of temporarily allocating twice the size of our largest
114                // possible object. In exchange we get to batch all charges associated with
115                // the clone into one (when A::IS_SHALLOW==true).
116                let vec: Vec<A> = iter.collect();
117                vec.charge_deep_clone(budget)?;
118                Self::from_vec(vec)
119            }
120        } else {
121            // This is a logic error, we should never get here.
122            Err((ScErrorType::Object, ScErrorCode::InternalError).into())
123        }
124    }
125
126    pub fn set(&self, index: usize, value: A, budget: &Budget) -> Result<Self, HostError> {
127        let mut new = self.metered_clone(budget)?;
128        new.charge_access(1, budget)?;
129        let cell: Result<&mut A, HostError> = new.vec.get_mut(index).ok_or_else(|| VEC_OOB.into());
130        *(cell?) = value;
131        Ok(new)
132    }
133
134    pub fn get(&self, index: usize, budget: &Budget) -> Result<&A, HostError> {
135        self.charge_access(1, budget)?;
136        self.vec.get(index).ok_or_else(|| VEC_OOB.into())
137    }
138
139    pub fn len(&self) -> usize {
140        self.vec.len()
141    }
142
143    pub fn push_front(&self, value: A, budget: &Budget) -> Result<Self, HostError> {
144        if self.len() == u32::MAX as usize {
145            Err(VEC_OOB.into())
146        } else {
147            let iter = [value].into_iter().chain(self.vec.iter().cloned());
148            Self::from_exact_iter(iter, budget)
149        }
150    }
151
152    pub fn pop_front(&self, budget: &Budget) -> Result<Self, HostError> {
153        if self.vec.is_empty() {
154            Err(VEC_OOB.into())
155        } else {
156            let iter = self.vec.iter().skip(1).cloned();
157            Self::from_exact_iter(iter, budget)
158        }
159    }
160
161    pub fn push_back(&self, value: A, budget: &Budget) -> Result<Self, HostError> {
162        if self.len() == u32::MAX as usize {
163            Err(VEC_OOB.into())
164        } else {
165            let iter = self.vec.iter().cloned().chain([value]);
166            Self::from_exact_iter(iter, budget)
167        }
168    }
169
170    fn err_oob() -> HostError {
171        VEC_OOB.into()
172    }
173
174    fn add_or_err(x: usize, y: usize) -> Result<usize, HostError> {
175        let sz = x.checked_add(y).ok_or_else(|| Self::err_oob())?;
176        if u32::try_from(sz).is_err() {
177            Err(Self::err_oob())
178        } else {
179            Ok(sz)
180        }
181    }
182
183    fn sub_or_err(x: usize, y: usize) -> Result<usize, HostError> {
184        x.checked_sub(y).ok_or_else(|| Self::err_oob())
185    }
186
187    pub fn pop_back(&self, budget: &Budget) -> Result<Self, HostError> {
188        if self.vec.is_empty() {
189            Err(VEC_OOB.into())
190        } else {
191            let count = Self::sub_or_err(self.vec.len(), 1)?;
192            let iter = self.vec.iter().take(count).cloned();
193            Self::from_exact_iter(iter, budget)
194        }
195    }
196
197    pub fn remove(&self, idx: usize, budget: &Budget) -> Result<Self, HostError> {
198        if idx >= self.vec.len() || idx == usize::MAX - 1 {
199            Err(VEC_OOB.into())
200        } else {
201            // [0, 1, 2]
202            // del 1 => take(1) + skip(2)
203            let skip = Self::add_or_err(idx, 1)?;
204            let init = self.vec.iter().take(idx).cloned();
205            let fini = self.vec.iter().skip(skip).cloned();
206            Self::from_exact_iter(init.chain(fini), budget)
207        }
208    }
209
210    pub fn front(&self, budget: &Budget) -> Result<&A, HostError> {
211        self.charge_access(1, budget)?;
212        self.vec.first().ok_or_else(|| VEC_OOB.into())
213    }
214
215    pub fn back(&self, budget: &Budget) -> Result<&A, HostError> {
216        self.charge_access(1, budget)?;
217        self.vec.last().ok_or_else(|| VEC_OOB.into())
218    }
219
220    pub fn insert(&self, index: usize, value: A, budget: &Budget) -> Result<Self, HostError> {
221        if self.vec.len() == u32::MAX as usize {
222            return Err(VEC_OOB.into());
223        }
224        let len = self.vec.len();
225        if index > len {
226            Err(VEC_OOB.into())
227        } else if index == len {
228            self.push_back(value, budget)
229        } else if index == 0 {
230            self.push_front(value, budget)
231        } else {
232            let init = self.vec.iter().take(index).cloned();
233            let fini = self.vec.iter().skip(index).cloned();
234            let iter = init.chain([value]).chain(fini);
235            Self::from_exact_iter(iter, budget)
236        }
237    }
238
239    pub fn append(&self, other: &Self, budget: &Budget) -> Result<Self, HostError> {
240        Self::add_or_err(self.len(), other.len())?;
241        let iter = self.vec.iter().cloned().chain(other.vec.iter().cloned());
242        Self::from_exact_iter(iter, budget)
243    }
244
245    pub fn slice(&self, range: Range<usize>, budget: &Budget) -> Result<Self, HostError> {
246        match self.vec.get(range) {
247            Some(slice) => Self::from_exact_iter(slice.iter().cloned(), budget),
248            None => Err(VEC_OOB.into()),
249        }
250    }
251
252    pub fn first_index_of<F>(&self, f: F, budget: &Budget) -> Result<Option<usize>, HostError>
253    where
254        F: Fn(&A) -> Result<Ordering, HostError>,
255    {
256        self.charge_scan(budget)?;
257        // this is similar logic to `iter.position(f)` but is fallible
258        for (i, val) in self.vec.iter().enumerate() {
259            if f(val)? == Ordering::Equal {
260                return Ok(Some(i));
261            }
262        }
263        Ok(None)
264    }
265
266    pub fn last_index_of<F>(&self, f: F, budget: &Budget) -> Result<Option<usize>, HostError>
267    where
268        F: Fn(&A) -> Result<Ordering, HostError>,
269    {
270        self.charge_scan(budget)?;
271        // this is similar logic to `iter.rposition(f)` but is fallible
272        for (i, val) in self.vec.iter().enumerate().rev() {
273            if f(val)? == Ordering::Equal {
274                return Ok(Some(i));
275            }
276        }
277        Ok(None)
278    }
279
280    pub fn binary_search_by<F>(
281        &self,
282        mut cmp: F,
283        budget: &Budget,
284    ) -> Result<Result<usize, usize>, HostError>
285    where
286        F: FnMut(&A) -> Result<Ordering, HostError>,
287    {
288        self.charge_binsearch(budget)?;
289        let mut err: Option<HostError> = None;
290        let res = binary_search_by_pre_rust_182(self.vec.as_slice(), |probe| {
291            // We've already hit an error, return Ordering::Equal
292            // to terminate search asap.
293            if err.is_some() {
294                return Ordering::Equal;
295            }
296            match cmp(probe) {
297                Ok(ord) => ord,
298                Err(he) => {
299                    err = Some(he);
300                    Ordering::Equal
301                }
302            }
303        });
304        match err {
305            Some(he) => Err(he),
306            None => Ok(res),
307        }
308    }
309
310    pub fn iter(&self) -> std::slice::Iter<'_, A> {
311        self.vec.iter()
312    }
313
314    pub fn to_vec(&self, budget: &Budget) -> Result<Vec<A>, HostError> {
315        self.vec.metered_clone(budget)
316    }
317}
318
319impl<A> DeclaredSizeForMetering for MeteredVector<A>
320where
321    A: DeclaredSizeForMetering,
322{
323    const DECLARED_SIZE: u64 = <Vec<A> as DeclaredSizeForMetering>::DECLARED_SIZE;
324}
325
326impl<A> MeteredClone for MeteredVector<A>
327where
328    A: MeteredClone,
329{
330    fn charge_for_substructure(&self, budget: impl AsBudget) -> Result<(), HostError> {
331        self.vec.charge_for_substructure(budget)
332    }
333}
334
335impl<Elt: MeteredClone> Compare<MeteredVector<Elt>> for Budget
336where
337    Budget: Compare<Elt, Error = HostError>,
338{
339    type Error = HostError;
340
341    fn compare(
342        &self,
343        a: &MeteredVector<Elt>,
344        b: &MeteredVector<Elt>,
345    ) -> Result<Ordering, Self::Error> {
346        // Here covers the cost of accessing number of map entries. The cost of
347        // comparing entries is covered by the `compare` call below.
348        self.as_budget().charge(
349            ContractCostType::MemCpy,
350            Some(Elt::DECLARED_SIZE.saturating_mul(a.vec.len().min(b.vec.len()) as u64)),
351        )?;
352        <Self as Compare<Vec<Elt>>>::compare(self, &a.vec, &b.vec)
353    }
354}
355
356impl<Elt: MeteredClone> Compare<MeteredVector<Elt>> for Host
357where
358    Host: Compare<Elt, Error = HostError>,
359{
360    type Error = HostError;
361
362    fn compare(
363        &self,
364        a: &MeteredVector<Elt>,
365        b: &MeteredVector<Elt>,
366    ) -> Result<Ordering, Self::Error> {
367        // Here covers the cost of accessing number of map entries. The cost of
368        // comparing entries is covered by the `compare` call below.
369        self.as_budget().charge(
370            ContractCostType::MemCpy,
371            Some(Elt::DECLARED_SIZE.saturating_mul(a.vec.len().min(b.vec.len()) as u64)),
372        )?;
373        <Self as Compare<Vec<Elt>>>::compare(self, &a.vec, &b.vec)
374    }
375}
376
377/// This is a copy of implementation of Rust stdlib `binary_search_by` function
378/// pre-Rust-1.82 with a minor modifications.
379///
380/// We cannot rely on the standard library implementation as it might change and
381/// thus change the observed metering as well. Thus we are just using the same
382/// hardcoded implementation.
383///
384/// The code is copied from the following file revision:
385/// https://github.com/rust-lang/rust/blob/8f7af88b33771ab5ec92a2a767a97a068f2ea17b/library/core/src/slice/mod.rs#L2769
386/// Modifications are no-op: switched &self to an explicit `slice` argument,
387/// removed assertions and unsafe blocks.
388pub(crate) fn binary_search_by_pre_rust_182<F, T>(slice: &[T], mut f: F) -> Result<usize, usize>
389where
390    F: FnMut(&T) -> std::cmp::Ordering,
391{
392    // INVARIANTS:
393    // - 0 <= left <= left + size = right <= self.len()
394    // - f returns Less for everything in self[..left]
395    // - f returns Greater for everything in self[right..]
396    let mut size = slice.len();
397    let mut left = 0;
398    let mut right = size;
399    while left < right {
400        let mid = left + size / 2;
401
402        // SAFETY: the while condition means `size` is strictly positive, so
403        // `size/2 < size`. Thus `left + size/2 < left + size`, which
404        // coupled with the `left + size <= self.len()` invariant means
405        // we have `left + size/2 < self.len()`, and this is in-bounds.
406        let cmp = f(slice.get(mid).unwrap());
407
408        // This control flow produces conditional moves, which results in
409        // fewer branches and instructions than if/else or matching on
410        // cmp::Ordering.
411        // This is x86 asm for u8: https://rust.godbolt.org/z/698eYffTx.
412        left = if cmp == std::cmp::Ordering::Less {
413            mid + 1
414        } else {
415            left
416        };
417        right = if cmp == std::cmp::Ordering::Greater {
418            mid
419        } else {
420            right
421        };
422        if cmp == std::cmp::Ordering::Equal {
423            return Ok(mid);
424        }
425
426        size = right - left;
427    }
428    Err(left)
429}
soroban_env_host/host/metered_vector.rs

soroban_env_host/host/
metered_vector.rs
